hashalloc9

Usage

Overview

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);