Re: [PATCH 2/2] Futex non-page-pinning fix

[Jamie Lokier]

Rusty Russell wrote:
> Walking a 256 entry hash table isn't free even if it's empty.  Example
> patch below.

You can avoid walking the whole hash table.  Instead of this:

     (page, offset) -> list of futexes at (p,o)

You can use a two-level map like this:

     (page) -> (offset) -> list of futexes at (p,o)

Or you can use two one-level maps, like this:

     (page) -> list of futexes at (p)
     (page, offset) -> list of futexes at (p,o)

Either of these gives you the list of futexes give then page in
O(list_size).  They also mean you don't need the page->flags bit to
get O(1) for a page with no futexes, but it's probably a good
optimisation anyway.

-- Jamie
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/