--- name: "hashalloc" section: "9" platform: "freebsd" package: "base" version: "16.0-CURRENT-20261027-61c70dc16a79" release: "FreeBSD 16.0-CURRENT (2026-10-27)" platforms: ["freebsd"] url: "https://new.carta.tech/hashalloc" --- # hashalloc(9) allocate and free kernel hash tables ## NAME **hashalloc**, **hashfree** – allocate and free kernel hash tables ## SYNOPSIS **#include \** **#include \** *void* *\**\ **hashalloc**(*struct hashalloc\_args \*args*); *void*\ **hashfree**(*void \*table*, *struct hashalloc\_args \*args*); ## DESCRIPTION The **hashalloc**() and **hashfree**() functions provide a flexible kernel programming interface (KPI) for allocating and freeing hash tables with configurable bucket headers. **hashalloc**() allocates memory for a hash table according to the parameters specified in the *args* structure. It computes an appropriate number of buckets (adjusting *args-\>size* as needed based on the requested *type*), allocates memory using [malloc(9)](/malloc/9.md), initializes each bucket's queue header (e.g., *LIST\_HEAD*, *TAILQ\_HEAD*, etc.), and, if requested, initializes per-bucket locks. The returned memory allocation can be used as an array of header structures that start with initialized list header of the requested type followed by initialized lock of requested type. **hashfree**() frees a hash table previously allocated by **hashalloc**(). Both functions require the caller to pass the same (or equivalent) *struct*, *hashalloc\_args* that specifies the desired configuration of the hash table and has the following members: ``` struct hashalloc_args { /* Required arguments */ size_t size; /* in: desired buckets, out: allocated */ int mflags; /* malloc(9) flags */ struct malloc_type *mtype; /* malloc(9) type */ /* Optional arguments */ size_t hdrsize; /* bucket header size; 0 = auto */ enum { HASH_TYPE_POWER2, HASH_TYPE_PRIME, } type; /* default HASH_TYPE_POWER2 */ enum { HASH_HEAD_LIST, HASH_HEAD_CK_LIST, HASH_HEAD_SLIST, HASH_HEAD_CK_SLIST, HASH_HEAD_STAILQ, HASH_HEAD_CK_STAILQ, HASH_HEAD_TAILQ, } head; /* default HASH_HEAD_LIST */ enum { HASH_LOCK_NONE, HASH_LOCK_MTX, HASH_LOCK_RWLOCK, HASH_LOCK_SX, HASH_LOCK_RMLOCK, HASH_LOCK_RMSLOCK, } lock; /* default HASH_LOCK_NONE */ int lopts; /* lock init options */ const char *lname; /* lock name */ int (*ctor)(void *); /* bucket constructor */ void (*dtor)(void *); /* bucket destructor */ /* Returned arguments */ int error; /* error code in case of failure */ }; ``` Argument members *size*, *mflags* and *mtype* are required for the **hashalloc**(). The argument *size*, as filled by earlier call to **hashalloc**(), and *mtype* are required for the **hashfree**(). The rest of arguments are optional and have reasonable defaults. A hash table that was allocated with a non-default allocation arguments shall pass the same arguments to **hashfree**(). The structure shall be initialized with sparse C99 initializer as it may contain opaque extension members. The structure may be allocated on the stack of a caller. - *size* Desired number of buckets for **hashalloc**(). Upon a successful return **hashalloc**() sets this member to the actual number allocated (may be rounded up to power-of-2 or nearest prime). The value returned by **hashalloc**() shall be later supplied to the **hashfree**(). - *mflags*, *mtype* Passed directly to [malloc(9)](/malloc/9.md). - *hdrsize* Optional member that allows the caller to set a different (increased) size of a bucket header. - *type* Bucket count policy: - HASH\_TYPE\_POWER2 Rounded up to largest power of two less than or equal to argument *size*. - HASH\_TYPE\_PRIME Sized to the largest prime number less than or equal to argument *size*. Default is HASH\_TYPE\_POWER2. - *head* Queue header type for each bucket, a [queue(3)](/queue/3.md) or Concurrency-kit (CK) type. - HASH\_HEAD\_LIST [queue(3)](/queue/3.md) **LIST\_HEAD** - HASH\_HEAD\_CK\_LIST Concurrency-kit **CK\_LIST\_HEAD** - HASH\_HEAD\_SLIST [queue(3)](/queue/3.md) **SLIST\_HEAD** - HASH\_HEAD\_CK\_SLIST Concurrency-kit **CK\_SLIST\_HEAD** - HASH\_HEAD\_STAILQ [queue(3)](/queue/3.md) **STAILQ\_HEAD** - HASH\_HEAD\_CK\_STAILQ Concurrency-kit **CK\_STAILQ\_HEAD** - HASH\_HEAD\_TAILQ [queue(3)](/queue/3.md) **TAILQ\_HEAD** Default is HASH\_HEAD\_LIST. - *lock* Synchronization: - HASH\_LOCK\_NONE No per-bucket lock. - HASH\_LOCK\_MTX Per-bucket [mutex(9)](/mutex/9.md). - HASH\_LOCK\_RWLOCK Per-bucket [rwlock(9)](/rwlock/9.md). - HASH\_LOCK\_SX Per-bucket [sx(9)](/sx/9.md). - HASH\_LOCK\_RMLOCK Per-bucket [rmlock(9)](/rmlock/9.md). - HASH\_LOCK\_RMSLOCK Per-bucket sleepable (rms) [rmlock(9)](/rmlock/9.md). Default is HASH\_LOCK\_NONE. - *lopts* Options passed to [mtx\_init(9)](/mtx_init/9.md), [rw\_init(9)](/rw_init/9.md), [sx\_init(9)](/sx_init/9.md), [rm\_init(9)](/rm_init/9.md) or rms\_init(9) (if locking is enabled). - *lname* Lock name. This member is required unless *lock* is HASH\_LOCK\_NONE. - *ctor* Optional constructor to be called by **hashalloc**() for each bucket after list header and lock initialization. May fail with error code, yielding in a failure of **hashalloc**(). - *dtor* Optional destructor to be called by **hashfree**() for each bucket before lock destructors and list emptyness checks. ## RETURN VALUES **hashalloc**() returns a pointer to the allocated and initialized hash table on success, or NULL on memory allocation failure or constructor failure. The *error* member of *args* is set to appropriate error code. When *mflags* in *args* contain the *M\_WAITOK* flag and the *ctor* is either NULL or never fails, then **hashalloc**() never fails. ## EXAMPLES A simple mutex-protected hash table using TAILQ buckets: ``` struct bucket { TAILQ_HEAD(, foo) head; struct mtx lock; } *table; struct hashalloc_args args = { .size = 9000, .mflags = M_WAITOK, .mtype = M_FOO, .head = HASH_HEAD_TAILQ, .lock = HASH_LOCK_MTX, .lopts = MTX_DEF, .lname = "bucket of foo", }; table = hashalloc(&args); /* Use table as array of struct bucket ... */ mtx_lock(&table[hash].lock); TAILQ_INSERT_HEAD(&table[hash].head, foo, next); /* Later */ hashfree(table, &args); ``` ## SEE ALSO [queue(3)](/queue/3.md), [malloc(9)](/malloc/9.md), [mutex(9)](/mutex/9.md), [rmlock(9)](/rmlock/9.md), [rwlock(9)](/rwlock/9.md), [sx(9)](/sx/9.md) ## HISTORY The **hashalloc** KPI first appeared in FreeBSD 16.0. It supersedes older interface **hashinit**(), that was available since 4.4BSD, by offering greater control over the hash table structure and locking strategy. ## AUTHORS Gleb Smirnoff ⟨*glebius@FreeBSD.org*⟩