slab: Use a hashtable when looking up bufctls
authorBarret Rhoden <brho@cs.berkeley.edu>
Sun, 30 Oct 2016 23:59:53 +0000 (19:59 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 29 Nov 2016 16:27:40 +0000 (11:27 -0500)
commitdf9eb617c8ff352ba365e177aeb8cda85bd746d5
tree12ed1dc4404234b241e779446aed6f2be61c4a0b
parenta96136dce08befae3e85942f5eeb6d931fac12a9
slab: Use a hashtable when looking up bufctls

It only took 7 years or so to take care of that TODO.  Note that this is
probably slower than the old approach, which was instant.  Similar to
the arena, we use hash_helper and roll our own hash table, especially
due to allocation issues when we grow the table.

Aside from being necessary for NO_TOUCH slabs, this will save a lot of
memory when it comes to fragmentation when we use slabs for arenas.
Consider kpages_arena, which will have qcaches of pages.  That will be
pulling from slabs of 1 - 8 pages.  The one-page slab allocator will
need to have obj_size = PGSIZE and align = PGSIZE.  If we don't use the
hash and instead have the uintptr_t blob per object, we'd need two pages
per one-page-object, essentially wasting half of our memory.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/slab.h
kern/src/slab.c