Date: Sun, 12 Apr 2026 17:39:57 +0000 From: Gleb Smirnoff <glebius@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: abf68d1cf025 - main - hash(9): introduce hashalloc()/hashfree() KPI Message-ID: <69dbd8ed.305f6.3b01202@gitrepo.freebsd.org>
index | next in thread | raw e-mail
The branch main has been updated by glebius: URL: https://cgit.FreeBSD.org/src/commit/?id=abf68d1cf02550c3c0341f5bb90be0d34f655a15 commit abf68d1cf02550c3c0341f5bb90be0d34f655a15 Author: Gleb Smirnoff <glebius@FreeBSD.org> AuthorDate: 2026-04-12 17:25:51 +0000 Commit: Gleb Smirnoff <glebius@FreeBSD.org> CommitDate: 2026-04-12 17:25:51 +0000 hash(9): introduce hashalloc()/hashfree() KPI This is a more extendable version than traditional hashinit(9). It allows different kinds of slot headers with optional locks. Implement traditional hashinit()/hashdestroy() on top of it. Reviewed by: pouria, gallatin Differential Revision: https://reviews.freebsd.org/D55904 --- share/man/man9/Makefile | 2 + share/man/man9/hashalloc.9 | 314 +++++++++++++++++++++++++++++++++++ share/man/man9/hashinit.9 | 9 +- sys/kern/subr_hash.c | 406 +++++++++++++++++++++++++++++++++++++++------ sys/sys/hash.h | 37 +++++ 5 files changed, 712 insertions(+), 56 deletions(-) diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile index 31a3f886d0f3..29c822c10eb2 100644 --- a/share/man/man9/Makefile +++ b/share/man/man9/Makefile @@ -174,6 +174,7 @@ MAN= accept_filter.9 \ gone_in.9 \ hardclock.9 \ hash.9 \ + hashalloc.9 \ hashinit.9 \ hexdump.9 \ hhook.9 \ @@ -1216,6 +1217,7 @@ MLINKS+=hash.9 hash32.9 \ hash.9 hash32_strne.9 \ hash.9 jenkins_hash.9 \ hash.9 jenkins_hash32.9 +MLINKS+=hashalloc.9 hashfree.9 MLINKS+=hashinit.9 hashdestroy.9 \ hashinit.9 hashinit_flags.9 \ hashinit.9 phashinit.9 diff --git a/share/man/man9/hashalloc.9 b/share/man/man9/hashalloc.9 new file mode 100644 index 000000000000..c68444bf05ed --- /dev/null +++ b/share/man/man9/hashalloc.9 @@ -0,0 +1,314 @@ +.\" +.\" Copyright (c) 2026 Gleb Smirnoff <glebius@FreeBSD.org> +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.Dd April 12, 2026 +.Dt HASHALLOC 9 +.Os +.Sh NAME +.Nm hashalloc , +.Nm hashfree +.Nd allocate and free kernel hash tables +.Sh SYNOPSIS +.In sys/malloc.h +.In sys/hash.h +.Ft void * +.Fn hashalloc "struct hashalloc_args *args" +.Ft void +.Fn hashfree "void *table" "struct hashalloc_args *args" +.Sh DESCRIPTION +The +.Fn hashalloc +and +.Fn hashfree +functions provide a flexible kernel programming interface (KPI) for allocating +and freeing hash tables with configurable bucket headers. +.Pp +.Pp +.Fn hashalloc +allocates memory for a hash table according to the parameters +specified in the +.Fa args +structure. +It computes an appropriate number of buckets (adjusting +.Fa args->size +as needed based on the requested +.Fa type ) , +allocates memory using +.Xr malloc 9 , +initializes each bucket's queue header (e.g., +.Vt LIST_HEAD , +.Vt 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. +.Pp +.Fn hashfree +frees a hash table previously allocated by +.Fn hashalloc . +.Pp +Both functions require the caller to pass the same (or equivalent) +.Fa struct hashalloc_args +that specifies the desired configuration of the hash table and has the +following members: +.Bd -literal -offset indent +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 */ +}; +.Ed +.Pp +Argument members +.Fa size , +.Fa mflags +and +.Fa mtype +are required for the +.Fn hashalloc . +The argument +.Fa size , +as filled by earlier call to +.Fn hashalloc , +and +.Fa mtype +are required for the +.Fn 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 +.Fn 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. +.Bl -tag -width ".Fa hdrsize" +.It Fa size +Desired number of buckets for +.Fn hashalloc . +Upon a successful return +.Fn hashalloc +sets this member to the actual number allocated +(may be rounded up to power-of-2 or nearest prime). +The value returned by +.Fn hashalloc +shall be later supplied to the +.Fn hashfree . +.It Fa mflags , Fa mtype +Passed directly to +.Xr malloc 9 . +.It Fa hdrsize +Optional member that allows the caller to set a different (increased) size +of a bucket header. +.It Fa type +Bucket count policy: +.Bl -tag -width ".Dv HASH_TYPE_POWER2" +.It Dv HASH_TYPE_POWER2 +Rounded up to largest power of two less than or equal to argument +.Fa size . +.It Dv HASH_TYPE_PRIME +Sized to the largest prime number less than or equal to argument +.Fa size . +.El +.Pp +Default is +.Dv HASH_TYPE_POWER2 . +.It Fa head +Queue header type for each bucket, a +.Xr queue 3 +or +Concurrency-kit (CK) type. +.Bl -tag -width ".Dv HASH_HEAD_CK_STAILQ" +.It Dv HASH_HEAD_LIST +.Xr queue 3 +.Fd LIST_HEAD +.It Dv HASH_HEAD_CK_LIST +Concurrency-kit +.Fd CK_LIST_HEAD +.It Dv HASH_HEAD_SLIST +.Xr queue 3 +.Fd SLIST_HEAD +.It Dv HASH_HEAD_CK_SLIST +Concurrency-kit +.Fd CK_SLIST_HEAD +.It Dv HASH_HEAD_STAILQ +.Xr queue 3 +.Fd STAILQ_HEAD +.It Dv HASH_HEAD_CK_STAILQ +Concurrency-kit +.Fd CK_STAILQ_HEAD +.It Dv HASH_HEAD_TAILQ +.Xr queue 3 +.Fd TAILQ_HEAD +.El +.Pp +Default is +.Dv HASH_HEAD_LIST . +.It Fa lock +Synchronization: +.Bl -tag -width ".Dv HASH_LOCK_RWLOCK" +.It Dv HASH_LOCK_NONE +No per-bucket lock. +.It Dv HASH_LOCK_MTX +Per-bucket +.Xr mutex 9 . +.It Dv HASH_LOCK_RWLOCK +Per-bucket +.Xr rwlock 9 . +.It Dv HASH_LOCK_SX +Per-bucket +.Xr sx 9 . +.It Dv HASH_LOCK_RMLOCK +Per-bucket +.Xr rmlock 9 . +.It Dv HASH_LOCK_RMSLOCK +Per-bucket sleepable (rms) +.Xr rmlock 9 . +.El +.Pp +Default is +.Dv HASH_LOCK_NONE . +.It Fa lopts +Options passed to +.Xr mtx_init 9 , +.Xr rw_init 9 , +.Xr sx_init 9 , +.Xr rm_init 9 +or +.Xr rms_init 9 +(if locking is enabled). +.It Fa lname +Lock name. +This member is required unless +.Fa lock +is +.Dv HASH_LOCK_NONE . +.It Fa ctor +Optional constructor to be called by +.Fn hashalloc +for each bucket after list header and lock initialization. +May fail with error code, yielding in a failure of +.Fn hashalloc . +.It Fa dtor +Optional destructor to be called by +.Fn hashfree +for each bucket before lock destructors and list emptyness checks. +.El +.Sh RETURN VALUES +.Fn hashalloc +returns a pointer to the allocated and initialized hash table on success, or +.Dv NULL +on memory allocation failure or constructor failure. +The +.Fa error +member of +.Fa args +is set to appropriate error code. +When +.Fa mflags +in +.Fa args +contain the +.Va M_WAITOK +flag and the +.Fa ctor +is either NULL or never fails, then +.Fn hashalloc +never fails. +.Sh EXAMPLES +A simple mutex-protected hash table using TAILQ buckets: +.Bd -literal -offset indent +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); +.Ed +.Sh SEE ALSO +.Xr malloc 9 , +.Xr mutex 9 , +.Xr rmlock 9 , +.Xr rwlock 9 , +.Xr sx 9 , +.Xr queue 3 +.Sh HISTORY +The +.Nm +KPI first appeared in +.Fx 16.0 . +It supersedes older interface +.Fn hashinit , +that was available since +.Bx 4.4 , +by offering greater control over the hash table structure and locking +strategy. +.Sh AUTHORS +.An Gleb Smirnoff Aq Mt glebius@FreeBSD.org diff --git a/share/man/man9/hashinit.9 b/share/man/man9/hashinit.9 index 7d2f75d58d03..8c6a3888efe8 100644 --- a/share/man/man9/hashinit.9 +++ b/share/man/man9/hashinit.9 @@ -23,7 +23,7 @@ .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE .\" POSSIBILITY OF SUCH DAMAGE. .\" -.Dd April 29, 2016 +.Dd March 17, 2026 .Dt HASHINIT 9 .Os .Sh NAME @@ -44,6 +44,12 @@ .Ft "void *" .Fn phashinit "int nelements" "struct malloc_type *type" "u_long *nentries" .Fn phashinit_flags "int nelements" "struct malloc_type *type" "u_long *nentries" "int flags" +.Sh WARNING +This KPI is obsolete and scheduled for removal in +.Fx 17 . +Use +.Xr hashalloc 9 +instead. .Sh DESCRIPTION The .Fn hashinit , @@ -178,6 +184,7 @@ pointed to by .Fa hashtbl is not empty. .Sh SEE ALSO +.Xr hashalloc 9 , .Xr LIST_HEAD 3 , .Xr malloc 9 .Sh BUGS diff --git a/sys/kern/subr_hash.c b/sys/kern/subr_hash.c index 23bb205909b1..a9dada7b4eb6 100644 --- a/sys/kern/subr_hash.c +++ b/sys/kern/subr_hash.c @@ -1,6 +1,7 @@ /*- * SPDX-License-Identifier: BSD-3-Clause * + * Copyright (c) 2026 Gleb Smirnoff <glebius@FreeBSD.org> * Copyright (c) 1982, 1986, 1991, 1993 * The Regents of the University of California. All rights reserved. * (c) UNIX System Laboratories, Inc. @@ -37,6 +38,329 @@ #include <sys/param.h> #include <sys/systm.h> #include <sys/malloc.h> +#include <sys/ck.h> +#include <sys/queue.h> +#include <sys/mutex.h> +#include <sys/rmlock.h> +#include <sys/rwlock.h> +#include <sys/sx.h> +#include <sys/hash.h> + +#define ASSERT_NOPAD(head, lock) _Static_assert( \ + sizeof(head ## _HEAD(, foo)) + sizeof(struct lock) == \ + sizeof(struct { head ## _HEAD(, foo) h; struct lock l; }), \ + "Structure of " #head "_HEAD and " #lock " has padding") +ASSERT_NOPAD(LIST, mtx); +ASSERT_NOPAD(CK_LIST, mtx); +ASSERT_NOPAD(SLIST, mtx); +ASSERT_NOPAD(CK_SLIST, mtx); +ASSERT_NOPAD(STAILQ, mtx); +ASSERT_NOPAD(CK_STAILQ, mtx); +ASSERT_NOPAD(TAILQ, mtx); +ASSERT_NOPAD(LIST, rwlock); +ASSERT_NOPAD(CK_LIST, rwlock); +ASSERT_NOPAD(SLIST, rwlock); +ASSERT_NOPAD(CK_SLIST, rwlock); +ASSERT_NOPAD(STAILQ, rwlock); +ASSERT_NOPAD(CK_STAILQ, rwlock); +ASSERT_NOPAD(TAILQ, rwlock); +ASSERT_NOPAD(LIST, sx); +ASSERT_NOPAD(CK_LIST, sx); +ASSERT_NOPAD(SLIST, sx); +ASSERT_NOPAD(CK_SLIST, sx); +ASSERT_NOPAD(STAILQ, sx); +ASSERT_NOPAD(CK_STAILQ, sx); +ASSERT_NOPAD(TAILQ, sx); +ASSERT_NOPAD(LIST, rmlock); +ASSERT_NOPAD(CK_LIST, rmlock); +ASSERT_NOPAD(SLIST, rmlock); +ASSERT_NOPAD(CK_SLIST, rmlock); +ASSERT_NOPAD(STAILQ, rmlock); +ASSERT_NOPAD(CK_STAILQ, rmlock); +ASSERT_NOPAD(TAILQ, rmlock); +ASSERT_NOPAD(LIST, rmslock); +ASSERT_NOPAD(CK_LIST, rmslock); +ASSERT_NOPAD(SLIST, rmslock); +ASSERT_NOPAD(CK_SLIST, rmslock); +ASSERT_NOPAD(STAILQ, rmslock); +ASSERT_NOPAD(CK_STAILQ, rmslock); +ASSERT_NOPAD(TAILQ, rmslock); +#undef ASSERT_NOPAD + +static inline void +hashalloc_sizes(struct hashalloc_args *args, size_t *hdrsize, size_t *loffset) +{ + switch (args->head) { + case HASH_HEAD_LIST: + *loffset = sizeof(LIST_HEAD(, foo)); + break; + case HASH_HEAD_CK_LIST: + *loffset = sizeof(CK_LIST_HEAD(, foo)); + break; + case HASH_HEAD_SLIST: + *loffset = sizeof(SLIST_HEAD(, foo)); + break; + case HASH_HEAD_CK_SLIST: + *loffset = sizeof(CK_SLIST_HEAD(, foo)); + break; + case HASH_HEAD_STAILQ: + *loffset = sizeof(STAILQ_HEAD(, foo)); + break; + case HASH_HEAD_CK_STAILQ: + *loffset = sizeof(CK_STAILQ_HEAD(, foo)); + break; + case HASH_HEAD_TAILQ: + *loffset = sizeof(TAILQ_HEAD(, foo)); + break; + } + + switch (args->lock) { + case HASH_LOCK_NONE: + *hdrsize = *loffset; + break; + case HASH_LOCK_MTX: + *hdrsize = *loffset + sizeof(struct mtx); + break; + case HASH_LOCK_RWLOCK: + *hdrsize = *loffset + sizeof(struct rwlock); + break; + case HASH_LOCK_SX: + *hdrsize = *loffset + sizeof(struct sx); + break; + case HASH_LOCK_RMLOCK: + *hdrsize = *loffset + sizeof(struct rmlock); + break; + case HASH_LOCK_RMSLOCK: + *hdrsize = *loffset + sizeof(struct rmslock); + break; + } + + if (args->hdrsize > 0) { + MPASS(args->hdrsize >= *hdrsize); + *hdrsize = args->hdrsize; + } else + args->hdrsize = *hdrsize; +} + +void * +hashalloc(struct hashalloc_args *args) +{ + static const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, + 1531, 2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, + 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; + void *mem; + size_t size, hdrsize, loffset; + u_int i; + + MPASS(args->version == 0); + MPASS(args->size > 0); + + switch (args->type) { + case HASH_TYPE_POWER2: + for (size = 1; size <= args->size; size <<= 1) + continue; + size >>= 1; + break; + case HASH_TYPE_PRIME: + for (i = nitems(primes); args->size < primes[i]; i--) + ; + size = primes[i]; + break; + } + + hashalloc_sizes(args, &hdrsize, &loffset); + + mem = malloc(size * hdrsize, args->mtype, args->mflags); + if (mem == NULL) { + args->error = ENOMEM; + return (NULL); + } + + switch (args->lock) { + case HASH_LOCK_NONE: + break; + case HASH_LOCK_MTX: + MPASS(args->lname != NULL); + if ((args->mflags & M_ZERO) == 0) + args->lopts |= MTX_NEW; + break; + case HASH_LOCK_RWLOCK: + MPASS(args->lname != NULL); + if ((args->mflags & M_ZERO) == 0) + args->lopts |= RW_NEW; + break; + case HASH_LOCK_SX: + MPASS(args->lname != NULL); + if ((args->mflags & M_ZERO) == 0) + args->lopts |= SX_NEW; + break; + case HASH_LOCK_RMLOCK: + MPASS(args->lname != NULL); + if ((args->mflags & M_ZERO) == 0) + args->lopts |= RM_NEW; + break; + case HASH_LOCK_RMSLOCK: + MPASS(args->lname != NULL); + break; + } + + for (i = 0; i < size; i++) { + void *slot; + + slot = (char *)mem + i * hdrsize; + switch (args->head) { + case HASH_HEAD_LIST: + LIST_INIT((LIST_HEAD(, foo) *)slot); + break; + case HASH_HEAD_CK_LIST: + CK_LIST_INIT((CK_LIST_HEAD(, foo) *)slot); + break; + case HASH_HEAD_SLIST: + SLIST_INIT((SLIST_HEAD(, foo) *)slot); + break; + case HASH_HEAD_CK_SLIST: + CK_SLIST_INIT((CK_SLIST_HEAD(, foo) *)slot); + break; + case HASH_HEAD_STAILQ: + STAILQ_INIT((STAILQ_HEAD(, foo) *)slot); + break; + case HASH_HEAD_CK_STAILQ: + CK_STAILQ_INIT((CK_STAILQ_HEAD(, foo) *)slot); + break; + case HASH_HEAD_TAILQ: + TAILQ_INIT((TAILQ_HEAD(, foo) *)slot); + break; + } + + slot = (char *)slot + loffset; + switch (args->lock) { + case HASH_LOCK_NONE: + break; + case HASH_LOCK_MTX: + mtx_init((struct mtx *)slot, args->lname, NULL, + args->lopts); + break; + case HASH_LOCK_RWLOCK: + rw_init_flags((struct rwlock *)slot, args->lname, + args->lopts); + break; + case HASH_LOCK_SX: + sx_init_flags((struct sx *)slot, args->lname, + args->lopts); + break; + case HASH_LOCK_RMLOCK: + rm_init_flags((struct rmlock *)slot, args->lname, + args->lopts); + break; + case HASH_LOCK_RMSLOCK: + rms_init((struct rmslock *)slot, args->lname); + break; + } + + if (args->ctor != NULL) { + slot = (char *)mem + i * hdrsize; + if ((args->error = args->ctor(slot)) != 0) { + slot = (char *)slot + loffset; + switch (args->lock) { + case HASH_LOCK_NONE: + break; + case HASH_LOCK_MTX: + mtx_destroy((struct mtx *)slot); + break; + case HASH_LOCK_RWLOCK: + rw_destroy((struct rwlock *)slot); + break; + case HASH_LOCK_SX: + sx_destroy((struct sx *)slot); + break; + case HASH_LOCK_RMLOCK: + rm_destroy((struct rmlock *)slot); + break; + case HASH_LOCK_RMSLOCK: + rms_destroy((struct rmslock *)slot); + break; + } + args->size = i; + hashfree(mem, args); + return (NULL); + } + } + } + + args->size = size; + return (mem); +} + +void +hashfree(void *mem, struct hashalloc_args *args) +{ + size_t hdrsize, loffset; + + if (__predict_false(mem == NULL)) + return; + + hashalloc_sizes(args, &hdrsize, &loffset); + + for (u_int i = 0; i < args->size; i++) { +#ifdef INVARIANTS + static const char msg[] = + "%s: hashtbl %p not empty (malloc type %s)"; +#endif +#define HPASS(exp) KASSERT(exp, (msg, __func__, mem, args->mtype->ks_shortdesc)) + void *slot; + + slot = (char *)mem + i * hdrsize; + if (args->dtor != NULL) + args->dtor(slot); + switch (args->head) { + case HASH_HEAD_LIST: + HPASS(LIST_EMPTY((LIST_HEAD(, foo) *)slot)); + break; + case HASH_HEAD_CK_LIST: + HPASS(CK_LIST_EMPTY((CK_LIST_HEAD(, foo) *)slot)); + break; + case HASH_HEAD_SLIST: + HPASS(SLIST_EMPTY((SLIST_HEAD(, foo) *)slot)); + break; + case HASH_HEAD_CK_SLIST: + HPASS(CK_SLIST_EMPTY((CK_SLIST_HEAD(, foo) *)slot)); + break; + case HASH_HEAD_STAILQ: + HPASS(STAILQ_EMPTY((STAILQ_HEAD(, foo) *)slot)); + break; + case HASH_HEAD_CK_STAILQ: + HPASS(CK_STAILQ_EMPTY((CK_STAILQ_HEAD(, foo) *)slot)); + break; + case HASH_HEAD_TAILQ: + HPASS(TAILQ_EMPTY((TAILQ_HEAD(, foo) *)slot)); + break; + } +#undef HPASS + + slot = (char *)slot + loffset; + switch (args->lock) { + case HASH_LOCK_NONE: + break; + case HASH_LOCK_MTX: + mtx_destroy((struct mtx *)slot); + break; + case HASH_LOCK_RWLOCK: + rw_destroy((struct rwlock *)slot); + break; + case HASH_LOCK_SX: + sx_destroy((struct sx *)slot); + break; + case HASH_LOCK_RMLOCK: + rm_destroy((struct rmlock *)slot); + break; + case HASH_LOCK_RMSLOCK: + rms_destroy((struct rmslock *)slot); + break; + } + } + + free(mem, args->mtype); +} static __inline int hash_mflags(int flags) @@ -52,26 +376,17 @@ void * hashinit_flags(int elements, struct malloc_type *type, u_long *hashmask, int flags) { - long hashsize, i; - LIST_HEAD(generic, generic) *hashtbl; - - KASSERT(elements > 0, ("%s: bad elements", __func__)); - /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */ - KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT), - ("Bad flags (0x%x) passed to hashinit_flags", flags)); - - for (hashsize = 1; hashsize <= elements; hashsize <<= 1) - continue; - hashsize >>= 1; - - hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, - hash_mflags(flags)); - if (hashtbl != NULL) { - for (i = 0; i < hashsize; i++) - LIST_INIT(&hashtbl[i]); - *hashmask = hashsize - 1; - } - return (hashtbl); + struct hashalloc_args args = { + .size = elements, + .mtype = type, + .mflags = hash_mflags(flags), + }; + void *rv; + + rv = hashalloc(&args); + if (rv != NULL) + *hashmask = args.size - 1; + return (rv); } /* @@ -87,20 +402,14 @@ hashinit(int elements, struct malloc_type *type, u_long *hashmask) void hashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask) { - LIST_HEAD(generic, generic) *hashtbl, *hp; + struct hashalloc_args args = { + .size = hashmask + 1, + .mtype = type, + }; - hashtbl = vhashtbl; - for (hp = hashtbl; hp <= &hashtbl[hashmask]; hp++) - KASSERT(LIST_EMPTY(hp), ("%s: hashtbl %p not empty " - "(malloc type %s)", __func__, hashtbl, type->ks_shortdesc)); - free(hashtbl, type); + hashfree(vhashtbl, &args); } -static const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, - 2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, - 6653, 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; -#define NPRIMES nitems(primes) - /* * General routine to allocate a prime number sized hash table with control of * memory flags. @@ -108,31 +417,18 @@ static const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, void * phashinit_flags(int elements, struct malloc_type *type, u_long *nentries, int flags) { - long hashsize, i; - LIST_HEAD(generic, generic) *hashtbl; - - KASSERT(elements > 0, ("%s: bad elements", __func__)); - /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */ - KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT), - ("Bad flags (0x%x) passed to phashinit_flags", flags)); - - for (i = 1, hashsize = primes[1]; hashsize <= elements;) { - i++; - if (i == NPRIMES) - break; - hashsize = primes[i]; - } - hashsize = primes[i - 1]; - - hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, - hash_mflags(flags)); - if (hashtbl == NULL) - return (NULL); + struct hashalloc_args args = { + .size = elements, + .mtype = type, + .type = HASH_TYPE_PRIME, + .mflags = hash_mflags(flags), + }; + void *rv; - for (i = 0; i < hashsize; i++) - LIST_INIT(&hashtbl[i]); - *nentries = hashsize; - return (hashtbl); + rv = hashalloc(&args); + if (rv != NULL) + *nentries = args.size; + return (rv); } /* diff --git a/sys/sys/hash.h b/sys/sys/hash.h index ac4bb35d70e9..5266632b1339 100644 --- a/sys/sys/hash.h +++ b/sys/sys/hash.h @@ -121,6 +121,43 @@ hash32_strne(const void *buf, size_t len, int end, const char **ep, } #ifdef _KERNEL +struct hashalloc_args { + u_int version; /* for extendability, now 0 */ + int error; /* out: error on failure */ + size_t size; /* in: wanted, out: allocated */ + size_t hdrsize; /* size of bucket header, 0 = auto */ + enum { + HASH_TYPE_POWER2 = 0, + HASH_TYPE_PRIME, + } type; + enum { + HASH_HEAD_LIST = 0, + HASH_HEAD_CK_LIST, + HASH_HEAD_SLIST, + HASH_HEAD_CK_SLIST, + HASH_HEAD_STAILQ, + HASH_HEAD_CK_STAILQ, + HASH_HEAD_TAILQ, + } head; + enum { + HASH_LOCK_NONE = 0, + HASH_LOCK_MTX, + HASH_LOCK_RWLOCK, + HASH_LOCK_SX, + HASH_LOCK_RMLOCK, + HASH_LOCK_RMSLOCK, + } lock; + int mflags; /* malloc(9) flags */ + int lopts; /* lock opts */ + struct malloc_type *mtype; /* malloc(9) type */ + const char *lname; /* lock name */ + int (*ctor)(void *); /* bucket constructor */ + void (*dtor)(void *); /* bucket destructor */ +}; + +void *hashalloc(struct hashalloc_args *); +void hashfree(void *, struct hashalloc_args *); + /* * Hashing function from Bob Jenkins. Implementation in libkern/jenkins_hash.c. */home | help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?69dbd8ed.305f6.3b01202>