NAME
hashalloc, hashfree – allocate and free kernel hash tables
SYNOPSIS
#include <sys/malloc.h>
#include <sys/hash.h>
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), 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).
- 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) or Concurrency-kit (CK) type.
- HASH_HEAD_LIST
-
queue(3) LIST_HEAD
- HASH_HEAD_CK_LIST
-
Concurrency-kit CK_LIST_HEAD
- HASH_HEAD_SLIST
-
queue(3) SLIST_HEAD
- HASH_HEAD_CK_SLIST
-
Concurrency-kit CK_SLIST_HEAD
- HASH_HEAD_STAILQ
-
queue(3) STAILQ_HEAD
- HASH_HEAD_CK_STAILQ
-
Concurrency-kit CK_STAILQ_HEAD
- HASH_HEAD_TAILQ
-
queue(3) TAILQ_HEAD
Default is HASH_HEAD_LIST.
- lock
-
Synchronization:
- lopts
-
Options passed to mtx_init(9), rw_init(9), sx_init(9), rm_init(9) 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
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 ⟨[email protected]⟩