HASH(9)

💖 HASH(9) — the kernel's hashing besties 💖

okay so this is a page from the Kernel Developer's Manual (section 9, kernel dev girlies 🫶) and it's literally all about the general kernel hashing functions. no cap, these are the little guys that turn your data into a cute 32-bit number so the kernel can find stuff fast. slay.

---

✨ NAME ✨

hash, hash32, hash32_buf, hash32_str, hash32_strn, hash32_stre, hash32_strne, jenkins_hash, jenkins_hash32, murmur3_32_hash, murmur3_32_hash32 — general kernel hashing functions 💅

---

🌸 SYNOPSIS 🌸

#include <sys/hash.h>

uint32_t
hash32_buf(const void *buf, size_t len, uint32_t hash);

uint32_t
hash32_str(const void *buf, uint32_t hash);

uint32_t
hash32_strn(const void *buf, size_t len, uint32_t hash);

uint32_t
hash32_stre(const void *buf, int end, const char **ep, uint32_t hash);

uint32_t
hash32_strne(const void *buf, size_t len, int end, const char **ep,
    uint32_t hash);

uint32_t
jenkins_hash(const void *buf, size_t len, uint32_t hash);

uint32_t
jenkins_hash32(const uint32_t *buf, size_t count, uint32_t hash);

uint32_t
murmur3_32_hash(const void *buf, size_t len, uint32_t hash);

uint32_t
murmur3_32_hash32(const uint32_t *buf, size_t count, uint32_t hash);

---

🦋 DESCRIPTION 🦋

so the hash32() girlies exist to give the kernel a consistent and general interface to a decent hashing algorithm. iconic behaviour honestly. these functions can hash ASCII NUL terminated strings and blocks of memory, so they're flexible fr fr. ✨

quick vocab check bestie, don't skip this:

• a len argument = the length of the buffer in bytes.
• a count argument = the length of the buffer in 32-bit words.

okay now the cast, one by one 👑

• hash32_buf() — the general buffer hashing function, the main character. buf is where the data lives, len is the length of the buffer in bytes, and hash is how you extend an existing hash — or you just pass in the initial value HASHINIT to start a brand new hash. 🎀
• hash32_str() — hashes a NUL terminated string that you pass in buf, starting from the initial hash value given in hash.
• hash32_strn() — literally the same vibe as hash32_str() except it also takes a len argument, which is the maximal length of the expected string. so it knows when to stop. boundaries, we love her. 💅
• hash32_stre() and hash32_strne() — these two are helper functions the kernel uses to hash pathname components. the extra plot twist: they have an additional termination condition, and they stop when they find a character given by end in the string being hashed. and if the argument ep is not NULL, it gets set to the point in the buffer at which the hash function terminated hashing. so cute, it tells you where it stopped. 🥺
• jenkins_hash() — same semantics as hash32_buf(), but it brings a more advanced hashing algorithm with better distribution. glow up. 🔥
• jenkins_hash32() — same hashing algorithm as jenkins_hash(), but it only works on uint32_t sized arrays, which makes it simpler and faster. it takes an array of uint32_t values as its first argument and the size of that array as the second argument. efficient queen. ⚡
• murmur3_32_hash() and murmur3_32_hash32() — similar to jenkins_hash() and jenkins_hash32(), but they implement the 32-bit version of MurmurHash3. the new girls on the block. 🌈

---

💜 RETURN VALUES 💜

the hash32() functions return a 32 bit hash value of the buffer or string. that's it, that's the whole return value. simple, clean, stunning. ✨

---

🎀 EXAMPLES 🎀

here's a little sample situation for you bestie, look how it all comes together:

      LIST_HEAD(head, cache) *hashtbl = NULL;
      u_long mask = 0;

      void
      sample_init(void)
      {

              hashtbl = hashinit(numwanted, type, flags, &mask);
      }

      void
      sample_use(char *str, int len)
      {
              uint32_t hash;

              hash = hash32_str(str, HASHINIT);
              hash = hash32_buf(&len, sizeof(len), hash);
              hashtbl[hash & mask] = len;
      }

see how HASHINIT kicks off the hash and then it gets extended? that's the extend-an-existing-hash moment we talked about. ate. 💅

---

👀 SEE ALSO 👀

• free(9)
• hashinit(9)
• malloc(9)

go read those too, iykyk. 📚

---

💀 LIMITATIONS 💀

okay bestie, real talk, this is the part where we keep it honest:

the hash32() functions are only 32 bit functions. they will prove to give poor 64 bit performance, especially for the top 32 bits. 😭

at the current time, this is not seen as a great limitation, because these hash values are usually used to index into an array. so it's lowkey fine.

but — should these hash values be used for other means, this limitation should be revisited. 👀 noted.

---

🌸 HISTORY 🌸

the lore, because you know i love the lore:

• the hash functions first appeared in NetBSD 1.6.
• the current implementation of hash32 functions was first committed to OpenBSD 3.2, and later imported to FreeBSD 6.1.
• the jenkins_hash functions were added in FreeBSD 10.0.
• the murmur3_32_hash functions were added in FreeBSD 10.1.

a whole timeline, we love a glow-up arc. ⭐

---

👑 AUTHORS 👑

giving credit where credit is due, periodt:

• the hash32 functions were written by Tobias Weingartner.
• the jenkins_hash functions were written by Bob Jenkins.
• the murmur3_32_hash functions were written by Dag-Erling Smørgrav <des@FreeBSD.org>.

---

and that's the whole page bestie!! 💖 this one came from the Debian crew and it's dated June 30, 2015 — so if you're reading this way later, just know the info is giving vintage in the cutest way. 🫶 go hash something responsibly. ✨🦋🎀