1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2022 NVIDIA corporation & affiliates. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice unmodified, this list of conditions, and the following 11 * disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 * 27 * $FreeBSD$ 28 */ 29 30 #ifndef _LINUXKPI_LINUX_HASHTABLE_H 31 #define _LINUXKPI_LINUX_HASHTABLE_H 32 33 #include <sys/param.h> 34 #include <sys/systm.h> 35 36 #include <linux/hash.h> 37 #include <linux/kernel.h> 38 #include <linux/list.h> 39 #include <linux/log2.h> 40 #include <linux/rcupdate.h> 41 #include <linux/rculist.h> 42 43 #include <ck_queue.h> 44 45 struct lkpi_hash_entry { 46 CK_LIST_ENTRY(lkpi_hash_entry) entry; 47 }; 48 49 struct lkpi_hash_head { 50 CK_LIST_HEAD(, lkpi_hash_entry) head; 51 }; 52 53 #define DEFINE_HASHTABLE(name, bits) \ 54 struct lkpi_hash_head name[1UL << (bits)] 55 56 #define DEFINE_READ_MOSTLY_HASHTABLE(name, bits) \ 57 struct lkpi_hash_head name[1UL << (bits)] __read_mostly 58 59 #define DECLARE_HASHTABLE(name, bits) \ 60 struct lkpi_hash_head name[1UL << (bits)] 61 62 #define HASH_SIZE(name) ARRAY_SIZE(name) 63 #define HASH_BITS(name) ilog2(HASH_SIZE(name)) 64 65 #define hash_min(...) \ 66 hash_long(__VA_ARGS__) 67 68 static inline void 69 __hash_init(struct lkpi_hash_head *ht, unsigned long size) 70 { 71 unsigned long x; 72 73 for (x = 0; x != size; x++) 74 CK_LIST_INIT(&ht[x].head); 75 } 76 77 #define hash_init(ht) \ 78 __hash_init(ht, HASH_SIZE(ht)) 79 80 #define hash_add(...) \ 81 hash_add_rcu(__VA_ARGS__) 82 83 static inline void 84 __hash_node_type_assert(struct hlist_node *node) 85 { 86 /* 87 * Unfortunately Linux doesn't have an own type for the hash 88 * table node entries. The purpose of this function is simply 89 * to check the type of the passed argument. 90 */ 91 CTASSERT(sizeof(struct lkpi_hash_entry) == sizeof(*node)); 92 } 93 94 #define hash_add_rcu(ht, node, key) do { \ 95 struct lkpi_hash_head *__head = &(ht)[hash_min(key, HASH_BITS(ht))]; \ 96 __hash_node_type_assert(node); \ 97 KASSERT(((struct lkpi_hash_entry *)(node))->entry.cle_prev == NULL, \ 98 ("node is already on list or was not zeroed")); \ 99 CK_LIST_INSERT_HEAD(&__head->head, \ 100 (struct lkpi_hash_entry *)(node), entry); \ 101 } while (0) 102 103 static inline bool 104 hash_hashed(struct hlist_node *node) 105 { 106 return (((struct lkpi_hash_entry *)node)->entry.cle_prev != NULL); 107 } 108 109 static inline bool 110 __hash_empty(struct lkpi_hash_head *ht, unsigned long size) 111 { 112 unsigned long x; 113 114 for (x = 0; x != size; x++) { 115 if (!CK_LIST_EMPTY(&ht[x].head)) 116 return (false); 117 } 118 return (true); 119 } 120 121 #define hash_empty(ht) \ 122 __hash_empty(ht, HASH_SIZE(ht)) 123 124 #define hash_del(...) \ 125 hash_del_rcu(__VA_ARGS__) 126 127 static inline void 128 hash_del_rcu(struct hlist_node *node) 129 { 130 CK_LIST_REMOVE((struct lkpi_hash_entry *)node, entry); 131 memset(node, 0, sizeof(*node)); 132 } 133 134 #define __hash_first(ht, type, member) ({ \ 135 const struct lkpi_hash_entry *__first = CK_LIST_FIRST(&(ht)->head); \ 136 __hash_node_type_assert(&((type *)0)->member); \ 137 (__first != NULL ? container_of((const void *)__first, type, member) : NULL); \ 138 }) 139 140 #define __hash_next(obj, type, member) ({ \ 141 const struct lkpi_hash_entry *__next = \ 142 CK_LIST_NEXT((struct lkpi_hash_entry *)&(obj)->member, entry); \ 143 __hash_node_type_assert(&(obj)->member); \ 144 (__next != NULL ? container_of((const void *)__next, type, member) : NULL); \ 145 }) 146 147 #define hash_for_each(...) \ 148 hash_for_each_rcu(__VA_ARGS__) 149 150 #define hash_for_each_rcu(name, bkt, obj, member) \ 151 for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \ 152 (bkt) != HASH_SIZE(name); (bkt)++) \ 153 for ((obj) = __hash_first(&(name)[bkt], \ 154 __typeof(*(obj)), member); \ 155 (obj) != NULL; \ 156 (obj) = __hash_next(obj, \ 157 __typeof(*(obj)), member)) 158 159 #define hash_for_each_safe(name, bkt, tmp, obj, member) \ 160 for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \ 161 (bkt) != HASH_SIZE(name); (bkt)++) \ 162 for ((obj) = __hash_first(&(name)[bkt], \ 163 __typeof(*(obj)), member); \ 164 (obj) != NULL && ((tmp) = &__hash_next(obj, \ 165 __typeof(*(obj)), member)->member, 1); \ 166 (obj) = container_of(tmp, __typeof(*(obj)), member)) 167 168 #define hash_for_each_possible(...) \ 169 hash_for_each_possible_rcu(__VA_ARGS__) 170 171 #define hash_for_each_possible_rcu_notrace(...) \ 172 hash_for_each_possible_rcu(__VA_ARGS__) 173 174 #define hash_for_each_possible_rcu(name, obj, member, key) \ 175 for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \ 176 __typeof(*(obj)), member); \ 177 (obj) != NULL; \ 178 (obj) = __hash_next(obj, __typeof(*(obj)), member)) 179 180 #define hash_for_each_possible_safe(name, obj, tmp, member, key) \ 181 for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \ 182 __typeof(*(obj)), member); \ 183 (obj) != NULL && ((tmp) = &__hash_next(obj, \ 184 __typeof(*(obj)), member)->member, 1); \ 185 (obj) = container_of(tmp, __typeof(*(obj)), member)) 186 187 #endif /* _LINUXKPI_LINUX_HASHTABLE_H */ 188