Messages in this thread | | | Date | Mon, 1 Sep 2003 01:35:04 +0100 | From | Jamie Lokier <> | Subject | Re: [PATCH 2/2] Futex non-page-pinning fix |
| |
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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |