xref: /freebsd-src/sys/compat/linuxkpi/common/include/linux/hashtable.h (revision 7e77089dccd702eb767350a8bd3d20102c4fb591)

/*-
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2022 NVIDIA corporation & affiliates.
 *
 * 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 unmodified, 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 ``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 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.
 */

#ifndef _LINUXKPI_LINUX_HASHTABLE_H
#define	_LINUXKPI_LINUX_HASHTABLE_H

#include <sys/param.h>
#include <sys/systm.h>

#include <linux/hash.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/log2.h>
#include <linux/rcupdate.h>
#include <linux/rculist.h>

#include <ck_queue.h>

struct lkpi_hash_entry {
	CK_LIST_ENTRY(lkpi_hash_entry) entry;
};

struct lkpi_hash_head {
	CK_LIST_HEAD(, lkpi_hash_entry) head;
};

#define	DEFINE_HASHTABLE(name, bits) \
	struct lkpi_hash_head name[1UL << (bits)]

#define	DEFINE_READ_MOSTLY_HASHTABLE(name, bits) \
	struct lkpi_hash_head name[1UL << (bits)] __read_mostly

#define	DECLARE_HASHTABLE(name, bits) \
	struct lkpi_hash_head name[1UL << (bits)]

#define	HASH_SIZE(name) ARRAY_SIZE(name)
#define	HASH_BITS(name) ilog2(HASH_SIZE(name))

#define	hash_min(...) \
	hash_long(__VA_ARGS__)

static inline void
__hash_init(struct lkpi_hash_head *ht, unsigned long size)
{
	unsigned long x;

	for (x = 0; x != size; x++)
		CK_LIST_INIT(&ht[x].head);
}

#define	hash_init(ht) \
	__hash_init(ht, HASH_SIZE(ht))

#define	hash_add(...) \
	hash_add_rcu(__VA_ARGS__)

static inline void
__hash_node_type_assert(struct hlist_node *node)
{
	/*
	 * Unfortunately Linux doesn't have an own type for the hash
	 * table node entries. The purpose of this function is simply
	 * to check the type of the passed argument.
	 */
	CTASSERT(sizeof(struct lkpi_hash_entry) == sizeof(*node));
}

#define	hash_add_rcu(ht, node, key) do {				\
	struct lkpi_hash_head *__head = &(ht)[hash_min(key, HASH_BITS(ht))]; \
	__hash_node_type_assert(node); \
	CK_LIST_INSERT_HEAD(&__head->head, \
	    (struct lkpi_hash_entry *)(node), entry); \
} while (0)

static inline bool
hash_hashed(struct hlist_node *node)
{
	return (((struct lkpi_hash_entry *)node)->entry.cle_prev != NULL);
}

static inline bool
__hash_empty(struct lkpi_hash_head *ht, unsigned long size)
{
	unsigned long x;

	for (x = 0; x != size; x++) {
		if (!CK_LIST_EMPTY(&ht[x].head))
			return (false);
	}
	return (true);
}

#define	hash_empty(ht) \
	__hash_empty(ht, HASH_SIZE(ht))

#define	hash_del(...) \
	hash_del_rcu(__VA_ARGS__)

static inline void
hash_del_rcu(struct hlist_node *node)
{
	CK_LIST_REMOVE((struct lkpi_hash_entry *)node, entry);
	memset(node, 0, sizeof(*node));
}

#define	__hash_first(ht, type, member) ({ \
	const struct lkpi_hash_entry *__first = CK_LIST_FIRST(&(ht)->head); \
	__hash_node_type_assert(&((type *)0)->member); \
	(__first != NULL ? container_of((const void *)__first, type, member) : NULL); \
})

#define	__hash_next(obj, type, member) ({ \
	const struct lkpi_hash_entry *__next = \
	    CK_LIST_NEXT((struct lkpi_hash_entry *)&(obj)->member, entry); \
	__hash_node_type_assert(&(obj)->member); \
	(__next != NULL ? container_of((const void *)__next, type, member) : NULL); \
})

#define	hash_for_each(...) \
	hash_for_each_rcu(__VA_ARGS__)

#define	hash_for_each_rcu(name, bkt, obj, member) \
	for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \
	       (bkt) != HASH_SIZE(name); (bkt)++) \
		for ((obj) = __hash_first(&(name)[bkt], \
			__typeof(*(obj)), member); \
		     (obj) != NULL; \
		     (obj) = __hash_next(obj, \
			__typeof(*(obj)), member))

#define	hash_for_each_safe(name, bkt, tmp, obj, member) \
	for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \
	       (bkt) != HASH_SIZE(name); (bkt)++) \
		for ((obj) = __hash_first(&(name)[bkt], \
			__typeof(*(obj)), member); \
		     (obj) != NULL && ((tmp) = &__hash_next(obj, \
			__typeof(*(obj)), member)->member, 1); \
		     (obj) = container_of(tmp, __typeof(*(obj)), member))

#define	hash_for_each_possible(...) \
	hash_for_each_possible_rcu(__VA_ARGS__)

#define	hash_for_each_possible_rcu_notrace(...) \
	hash_for_each_possible_rcu(__VA_ARGS__)

#define	hash_for_each_possible_rcu(name, obj, member, key) \
	for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \
		__typeof(*(obj)), member); \
	     (obj) != NULL; \
	     (obj) = __hash_next(obj, __typeof(*(obj)), member))

#define	hash_for_each_possible_safe(name, obj, tmp, member, key) \
	for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \
		__typeof(*(obj)), member); \
	     (obj) != NULL && ((tmp) = &__hash_next(obj, \
		__typeof(*(obj)), member)->member, 1); \
	     (obj) = container_of(tmp, __typeof(*(obj)), member))

#endif					/* _LINUXKPI_LINUX_HASHTABLE_H */