Re: [PATCH 2/2] Futex non-page-pinning fix
From: Jamie Lokier
Date: Sun Aug 31 2003 - 19:37:02 EST
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/