Page MenuHomeFreeBSD
Files F152373354

D55904.id174388.diff
No OneTemporary
Actions

D55904.id174388.diff
View Options

diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -174,6 +174,7 @@
gone_in.9 \
hardclock.9 \
hash.9 \
+ hashalloc.9 \
hashinit.9 \
hexdump.9 \
hhook.9 \
@@ -1216,6 +1217,7 @@
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
--- /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 March 17, 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 contiguous 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
--- 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 @@
.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
--- 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,327 @@
#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_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_NONE:
+ case HASH_LOCK_RMSLOCK:
+ 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 +374,17 @@
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 +400,14 @@
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 +415,18 @@
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
--- a/sys/sys/hash.h
+++ b/sys/sys/hash.h
@@ -121,6 +121,43 @@
}
#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.
*/

File Metadata

Mime Type
text/plain
Expires
Wed, Apr 15, 12:57 PM (1 h, 52 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31540169
Default Alt Text
D55904.id174388.diff (21 KB)

Event Timeline