1.\" 2.\" Copyright (c) 2026 Gleb Smirnoff <glebius@FreeBSD.org> 3.\" All rights reserved. 4.\" 5.\" Redistribution and use in source and binary forms, with or without 6.\" modification, are permitted provided that the following conditions 7.\" are met: 8.\" 1. Redistributions of source code must retain the above copyright 9.\" notice, this list of conditions and the following disclaimer. 10.\" 2. Redistributions in binary form must reproduce the above copyright 11.\" notice, this list of conditions and the following disclaimer in the 12.\" documentation and/or other materials provided with the distribution. 13.\" 14.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24.\" SUCH DAMAGE. 25.\" 26.Dd April 12, 2026 27.Dt HASHALLOC 9 28.Os 29.Sh NAME 30.Nm hashalloc , 31.Nm hashfree 32.Nd allocate and free kernel hash tables 33.Sh SYNOPSIS 34.In sys/malloc.h 35.In sys/hash.h 36.Ft void * 37.Fn hashalloc "struct hashalloc_args *args" 38.Ft void 39.Fn hashfree "void *table" "struct hashalloc_args *args" 40.Sh DESCRIPTION 41The 42.Fn hashalloc 43and 44.Fn hashfree 45functions provide a flexible kernel programming interface (KPI) for allocating 46and freeing hash tables with configurable bucket headers. 47.Pp 48.Pp 49.Fn hashalloc 50allocates memory for a hash table according to the parameters 51specified in the 52.Fa args 53structure. 54It computes an appropriate number of buckets (adjusting 55.Fa args->size 56as needed based on the requested 57.Fa type ) , 58allocates memory using 59.Xr malloc 9 , 60initializes each bucket's queue header (e.g., 61.Vt LIST_HEAD , 62.Vt TAILQ_HEAD , 63etc.), and, if requested, initializes per-bucket locks. 64The returned memory allocation can be used as an array of header structures 65that start with initialized list header of the requested type followed by 66initialized lock of requested type. 67.Pp 68.Fn hashfree 69frees a hash table previously allocated by 70.Fn hashalloc . 71.Pp 72Both functions require the caller to pass the same (or equivalent) 73.Fa struct hashalloc_args 74that specifies the desired configuration of the hash table and has the 75following members: 76.Bd -literal -offset indent 77struct hashalloc_args { 78 /* Required arguments */ 79 size_t size; /* in: desired buckets, out: allocated */ 80 int mflags; /* malloc(9) flags */ 81 struct malloc_type *mtype; /* malloc(9) type */ 82 /* Optional arguments */ 83 size_t hdrsize; /* bucket header size; 0 = auto */ 84 enum { 85 HASH_TYPE_POWER2, 86 HASH_TYPE_PRIME, 87 } type; /* default HASH_TYPE_POWER2 */ 88 enum { 89 HASH_HEAD_LIST, 90 HASH_HEAD_CK_LIST, 91 HASH_HEAD_SLIST, 92 HASH_HEAD_CK_SLIST, 93 HASH_HEAD_STAILQ, 94 HASH_HEAD_CK_STAILQ, 95 HASH_HEAD_TAILQ, 96 } head; /* default HASH_HEAD_LIST */ 97 enum { 98 HASH_LOCK_NONE, 99 HASH_LOCK_MTX, 100 HASH_LOCK_RWLOCK, 101 HASH_LOCK_SX, 102 HASH_LOCK_RMLOCK, 103 HASH_LOCK_RMSLOCK, 104 } lock; /* default HASH_LOCK_NONE */ 105 int lopts; /* lock init options */ 106 const char *lname; /* lock name */ 107 int (*ctor)(void *); /* bucket constructor */ 108 void (*dtor)(void *); /* bucket destructor */ 109 /* Returned arguments */ 110 int error; /* error code in case of failure */ 111}; 112.Ed 113.Pp 114Argument members 115.Fa size , 116.Fa mflags 117and 118.Fa mtype 119are required for the 120.Fn hashalloc . 121The argument 122.Fa size , 123as filled by earlier call to 124.Fn hashalloc , 125and 126.Fa mtype 127are required for the 128.Fn hashfree . 129The rest of arguments are optional and have reasonable defaults. 130A hash table that was allocated with a non-default allocation arguments shall 131pass the same arguments to 132.Fn hashfree . 133The structure shall be initialized with sparse C99 initializer as it may 134contain opaque extension members. 135The structure may be allocated on the stack of a caller. 136.Bl -tag -width ".Fa hdrsize" 137.It Fa size 138Desired number of buckets for 139.Fn hashalloc . 140Upon a successful return 141.Fn hashalloc 142sets this member to the actual number allocated 143(may be rounded up to power-of-2 or nearest prime). 144The value returned by 145.Fn hashalloc 146shall be later supplied to the 147.Fn hashfree . 148.It Fa mflags , Fa mtype 149Passed directly to 150.Xr malloc 9 . 151.It Fa hdrsize 152Optional member that allows the caller to set a different (increased) size 153of a bucket header. 154.It Fa type 155Bucket count policy: 156.Bl -tag -width ".Dv HASH_TYPE_POWER2" 157.It Dv HASH_TYPE_POWER2 158Rounded up to largest power of two less than or equal to argument 159.Fa size . 160.It Dv HASH_TYPE_PRIME 161Sized to the largest prime number less than or equal to argument 162.Fa size . 163.El 164.Pp 165Default is 166.Dv HASH_TYPE_POWER2 . 167.It Fa head 168Queue header type for each bucket, a 169.Xr queue 3 170or 171Concurrency-kit (CK) type. 172.Bl -tag -width ".Dv HASH_HEAD_CK_STAILQ" 173.It Dv HASH_HEAD_LIST 174.Xr queue 3 175.Fd LIST_HEAD 176.It Dv HASH_HEAD_CK_LIST 177Concurrency-kit 178.Fd CK_LIST_HEAD 179.It Dv HASH_HEAD_SLIST 180.Xr queue 3 181.Fd SLIST_HEAD 182.It Dv HASH_HEAD_CK_SLIST 183Concurrency-kit 184.Fd CK_SLIST_HEAD 185.It Dv HASH_HEAD_STAILQ 186.Xr queue 3 187.Fd STAILQ_HEAD 188.It Dv HASH_HEAD_CK_STAILQ 189Concurrency-kit 190.Fd CK_STAILQ_HEAD 191.It Dv HASH_HEAD_TAILQ 192.Xr queue 3 193.Fd TAILQ_HEAD 194.El 195.Pp 196Default is 197.Dv HASH_HEAD_LIST . 198.It Fa lock 199Synchronization: 200.Bl -tag -width ".Dv HASH_LOCK_RWLOCK" 201.It Dv HASH_LOCK_NONE 202No per-bucket lock. 203.It Dv HASH_LOCK_MTX 204Per-bucket 205.Xr mutex 9 . 206.It Dv HASH_LOCK_RWLOCK 207Per-bucket 208.Xr rwlock 9 . 209.It Dv HASH_LOCK_SX 210Per-bucket 211.Xr sx 9 . 212.It Dv HASH_LOCK_RMLOCK 213Per-bucket 214.Xr rmlock 9 . 215.It Dv HASH_LOCK_RMSLOCK 216Per-bucket sleepable (rms) 217.Xr rmlock 9 . 218.El 219.Pp 220Default is 221.Dv HASH_LOCK_NONE . 222.It Fa lopts 223Options passed to 224.Xr mtx_init 9 , 225.Xr rw_init 9 , 226.Xr sx_init 9 , 227.Xr rm_init 9 228or 229.Xr rms_init 9 230(if locking is enabled). 231.It Fa lname 232Lock name. 233This member is required unless 234.Fa lock 235is 236.Dv HASH_LOCK_NONE . 237.It Fa ctor 238Optional constructor to be called by 239.Fn hashalloc 240for each bucket after list header and lock initialization. 241May fail with error code, yielding in a failure of 242.Fn hashalloc . 243.It Fa dtor 244Optional destructor to be called by 245.Fn hashfree 246for each bucket before lock destructors and list emptyness checks. 247.El 248.Sh RETURN VALUES 249.Fn hashalloc 250returns a pointer to the allocated and initialized hash table on success, or 251.Dv NULL 252on memory allocation failure or constructor failure. 253The 254.Fa error 255member of 256.Fa args 257is set to appropriate error code. 258When 259.Fa mflags 260in 261.Fa args 262contain the 263.Va M_WAITOK 264flag and the 265.Fa ctor 266is either NULL or never fails, then 267.Fn hashalloc 268never fails. 269.Sh EXAMPLES 270A simple mutex-protected hash table using TAILQ buckets: 271.Bd -literal -offset indent 272struct bucket { 273 TAILQ_HEAD(, foo) head; 274 struct mtx lock; 275} *table; 276 277struct hashalloc_args args = { 278 .size = 9000, 279 .mflags = M_WAITOK, 280 .mtype = M_FOO, 281 .head = HASH_HEAD_TAILQ, 282 .lock = HASH_LOCK_MTX, 283 .lopts = MTX_DEF, 284 .lname = "bucket of foo", 285}; 286 287table = hashalloc(&args); 288/* Use table as array of struct bucket ... */ 289mtx_lock(&table[hash].lock); 290TAILQ_INSERT_HEAD(&table[hash].head, foo, next); 291 292/* Later */ 293hashfree(table, &args); 294.Ed 295.Sh SEE ALSO 296.Xr malloc 9 , 297.Xr mutex 9 , 298.Xr rmlock 9 , 299.Xr rwlock 9 , 300.Xr sx 9 , 301.Xr queue 3 302.Sh HISTORY 303The 304.Nm 305KPI first appeared in 306.Fx 16.0 . 307It supersedes older interface 308.Fn hashinit , 309that was available since 310.Bx 4.4 , 311by offering greater control over the hash table structure and locking 312strategy. 313.Sh AUTHORS 314.An Gleb Smirnoff Aq Mt glebius@FreeBSD.org 315