HASHALLOC(9)

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:

    HASH_LOCK_NONE
        No per-bucket lock.

    HASH_LOCK_MTX
        Per-bucket mutex(9).

    HASH_LOCK_RWLOCK
        Per-bucket rwlock(9).

    HASH_LOCK_SX
        Per-bucket sx(9).

    HASH_LOCK_RMLOCK
        Per-bucket rmlock(9).

    HASH_LOCK_RMSLOCK
        Per-bucket sleepable (rms) rmlock(9).

    Default is HASH_LOCK_NONE.

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
malloc(9), mutex(9), rmlock(9), rwlock(9), sx(9), queue(3)

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>