HASHINIT(9)

💖 HASHINIT(9) — managing kernel hash tables 💖

Hey bestie, welcome to HASHINIT(9) from the Kernel Developer's Manual — yes, the actual kernel developer's manual, we're in the big leagues now 🎀 This one's all about making, using, and (carefully!) destroying hash tables inside the kernel. Settle in, it's giving very much "small page, big consequences" energy.

---

✨ NAME ✨

hashinit, hashinit_flags, hashdestroy, phashinit, phashinit_flags — the little family that manages kernel hash tables 🔥

---

🌸 SYNOPSIS 🌸

#include <sys/malloc.h>
#include <sys/systm.h>
#include <sys/queue.h>

void *
hashinit(int nelements, struct malloc_type *type, u_long *hashmask);

void
hashinit_flags(int nelements, struct malloc_type *type,
    u_long *hashmask, int flags);

void
hashdestroy(void *hashtbl, struct malloc_type *type, u_long hashmask);

void *
phashinit(int nelements, struct malloc_type *type, u_long *nentries);

phashinit_flags(int nelements, struct malloc_type *type,
    u_long *nentries, int flags);

Like, look at that function family portrait 🫶 it's literally all there.

---

💅 DESCRIPTION 💅

Okay so hashinit(), hashinit_flags(), phashinit() and phashinit_flags() all do the same basic thing: they allocate space for hash tables whose size is given by the argument nelements. Coordinated queen behavior.

Here's the tea on each one ☕:

• hashinit() allocates hash tables sized to the largest power of two less than or equal to the argument nelements. Powers of two, so clean, so binary, we stan.
• phashinit() allocates hash tables sized to the largest prime number less than or equal to the argument nelements. Primes really said "let me distribute these buckets evenly, bestie."
• hashinit_flags() operates like hashinit() but also accepts an additional argument flags which controls various options during allocation.
• phashinit_flags() operates like phashinit() but also accepts an additional argument flags which controls various options during allocation.

The allocated hash tables are contiguous arrays of LIST_HEAD(3) entries, allocated using malloc(9), and initialized using LIST_INIT(3). The malloc arena to be used for allocation is pointed to by the argument type. Contiguous! Initialized! Arena-directed! The whole package honestly 💖

Now the destruction side, because every icon needs its exit:

hashdestroy() frees the space occupied by the hash table pointed to by argument hashtbl. Argument type determines the malloc arena to use when freeing space. The argument hashmask should be the bit mask returned by the call to hashinit() that allocated the hash table — like, you have to give it back the receipt, no cap 🧾

The argument flags must be used with one of the following values:

• HASH_NOWAIT — Any malloc performed by the hashinit_flags() and phashinit_flags() function will not be allowed to wait, and therefore may fail 😭
• HASH_WAITOK — Any malloc performed by hashinit_flags() and phashinit_flags() function is allowed to wait for memory. This is also the behavior of hashinit() and phashinit(). Very "patient queen" of them.

---

🧚 IMPLEMENTATION NOTES 🧚

The largest prime hash value chosen by phashinit() is 32749. That's it, that's the note, but it's an iconic number and I won't hear otherwise ⭐

---

🦋 RETURN VALUES 🦋

• hashinit() returns a pointer to an allocated hash table and sets the location pointed to by hashmask to the bit mask to be used for computing the correct slot in the hash table 🔥 (pointer + mask, the classic duo)
• phashinit() returns a pointer to an allocated hash table and sets the location pointed to by nentries to the number of rows in the hash table 🌈

---

👑 EXAMPLES 👑

A typical example is shown below:

...
static LIST_HEAD(foo, foo) *footable;
static u_long foomask;
...
footable = hashinit(32, M_FOO, &foomask);

So here we allocate a hash table with 32 entries from the malloc arena pointed to by M_FOO. The mask for the allocated hash table is returned in foomask. A subsequent call to hashdestroy() uses the value in foomask:

...
hashdestroy(footable, M_FOO, foomask);

See how it all comes back around? The mask you got goin' out is the mask you use comin' back in. Circular economy, we love to see it ♻️💜

---

💀 DIAGNOSTICS 💀

• The hashinit() and phashinit() functions will panic if argument nelements is less than or equal to zero. So like... don't do that 🙈
• The hashdestroy() function will panic if the hash table pointed to by hashtbl is not empty. Empty it first, bestie, I'm begging.

Fr fr, these are kernel panics. Not a little error message, not a warning — the whole system goes down. Treat nelements and your empty-check with the respect they deserve 👑

---

🍓 SEE ALSO 🍓

LIST_HEAD(3), malloc(9) — go read these next, they're the supporting cast and they ATE 💅

---

🎀 BUGS 🎀

There is no phashdestroy() function 😭 and using hashdestroy() to free a hash table allocated by phashinit() usually has grave consequences. Grave! Consequences! I cannot stress this enough — the prime-sized table and the power-of-two destruction path are NOT a match made in heaven, they're a match made in ☠️

---

okay that's the whole page, you're officially hash-table-literate, go forth and allocate responsibly ✨

<div>From the fine folks behind Debian, dated April 29, 2016 — mwah, thanks for the docs, love u, bye 🫶💖</div>