path: root/sys/kern/subr_hash.c

/*-
 * 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.
 * All or some portions of this file are derived from material licensed
 * to the University of California by American Telephone and Telegraph
 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
 * the permission of UNIX System Laboratories, Inc.
 *
 * 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.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 */

#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) - 1; 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)
{

	return ((flags & HASH_NOWAIT) ? M_NOWAIT : M_WAITOK);
}

/*
 * General routine to allocate a hash table with control of memory flags.
 */
void *
hashinit_flags(int elements, struct malloc_type *type, u_long *hashmask,
    int flags)
{
	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);
}

/*
 * Allocate and initialize a hash table with default flag: may sleep.
 */
void *
hashinit(int elements, struct malloc_type *type, u_long *hashmask)
{

	return (hashinit_flags(elements, type, hashmask, HASH_WAITOK));
}

void
hashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask)
{
	struct hashalloc_args args = {
		.size = hashmask + 1,
		.mtype = type,
	};

	hashfree(vhashtbl, &args);
}

/*
 * General routine to allocate a prime number sized hash table with control of
 * memory flags.
 */
void *
phashinit_flags(int elements, struct malloc_type *type, u_long *nentries, int flags)
{
	struct hashalloc_args args = {
		.size = elements,
		.mtype = type,
		.type = HASH_TYPE_PRIME,
		.mflags = hash_mflags(flags),
	};
	void *rv;

	rv = hashalloc(&args);
	if (rv != NULL)
		*nentries = args.size;
	return (rv);
}

/*
 * Allocate and initialize a prime number sized hash table with default flag:
 * may sleep.
 */
void *
phashinit(int elements, struct malloc_type *type, u_long *nentries)
{

	return (phashinit_flags(elements, type, nentries, HASH_WAITOK));
}