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 28 #ifndef _LINUXKPI_LINUX_HASHTABLE_H 29 #define _LINUXKPI_LINUX_HASHTABLE_H 30 31 #include <sys/param.h> 32 #include <sys/systm.h> 33 34 #include <linux/hash.h> 35 #include <linux/kernel.h> 36 #include <linux/list.h> 37 #include <linux/log2.h> 38 #include <linux/rcupdate.h> 39 #include <linux/rculist.h> 40 41 #include <ck_queue.h> 42 43 struct lkpi_hash_entry { 44 CK_LIST_ENTRY(lkpi_hash_entry) entry; 45 }; 46 47 struct lkpi_hash_head { 48 CK_LIST_HEAD(, lkpi_hash_entry) head; 49 }; 50 51 #define DEFINE_HASHTABLE(name, bits) \ 52 struct lkpi_hash_head name[1UL << (bits)] 53 54 #define DEFINE_READ_MOSTLY_HASHTABLE(name, bits) \ 55 struct lkpi_hash_head name[1UL << (bits)] __read_mostly 56 57 #define DECLARE_HASHTABLE(name, bits) \ 58 struct lkpi_hash_head name[1UL << (bits)] 59 60 #define HASH_SIZE(name) ARRAY_SIZE(name) 61 #define HASH_BITS(name) ilog2(HASH_SIZE(name)) 62 63 #define hash_min(...) \ 64 hash_long(__VA_ARGS__) 65 66 static inline void 67 __hash_init(struct lkpi_hash_head *ht, unsigned long size) 68 { 69 unsigned long x; 70 71 for (x = 0; x != size; x++) 72 CK_LIST_INIT(&ht[x].head); 73 } 74 75 #define hash_init(ht) \ 76 __hash_init(ht, HASH_SIZE(ht)) 77 78 #define hash_add(...) \ 79 hash_add_rcu(__VA_ARGS__) 80 81 static inline void 82 __hash_node_type_assert(struct hlist_node *node) 83 { 84 /* 85 * Unfortunately Linux doesn't have an own type for the hash 86 * table node entries. The purpose of this function is simply 87 * to check the type of the passed argument. 88 */ 89 CTASSERT(sizeof(struct lkpi_hash_entry) == sizeof(*node)); 90 } 91 92 #define hash_add_rcu(ht, node, key) do { \ 93 struct lkpi_hash_head *__head = &(ht)[hash_min(key, HASH_BITS(ht))]; \ 94 __hash_node_type_assert(node); \ 95 KASSERT(((struct lkpi_hash_entry *)(node))->entry.cle_prev == NULL, \ 96 ("node is already on list or was not zeroed")); \ 97 CK_LIST_INSERT_HEAD(&__head->head, \ 98 (struct lkpi_hash_entry *)(node), entry); \ 99 } while (0) 100 101 static inline bool 102 hash_hashed(struct hlist_node *node) 103 { 104 return (((struct lkpi_hash_entry *)node)->entry.cle_prev != NULL); 105 } 106 107 static inline bool 108 __hash_empty(struct lkpi_hash_head *ht, unsigned long size) 109 { 110 unsigned long x; 111 112 for (x = 0; x != size; x++) { 113 if (!CK_LIST_EMPTY(&ht[x].head)) 114 return (false); 115 } 116 return (true); 117 } 118 119 #define hash_empty(ht) \ 120 __hash_empty(ht, HASH_SIZE(ht)) 121 122 #define hash_del(...) \ 123 hash_del_rcu(__VA_ARGS__) 124 125 static inline void 126 hash_del_rcu(struct hlist_node *node) 127 { 128 CK_LIST_REMOVE((struct lkpi_hash_entry *)node, entry); 129 memset(node, 0, sizeof(*node)); 130 } 131 132 #define __hash_first(ht, type, member) ({ \ 133 const struct lkpi_hash_entry *__first = CK_LIST_FIRST(&(ht)->head); \ 134 __hash_node_type_assert(&((type *)0)->member); \ 135 (__first != NULL ? container_of((const void *)__first, type, member) : NULL); \ 136 }) 137 138 #define __hash_next(obj, type, member) ({ \ 139 const struct lkpi_hash_entry *__next = \ 140 CK_LIST_NEXT((struct lkpi_hash_entry *)&(obj)->member, entry); \ 141 __hash_node_type_assert(&(obj)->member); \ 142 (__next != NULL ? container_of((const void *)__next, type, member) : NULL); \ 143 }) 144 145 #define hash_for_each(...) \ 146 hash_for_each_rcu(__VA_ARGS__) 147 148 #define hash_for_each_rcu(name, bkt, obj, member) \ 149 for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \ 150 (bkt) != HASH_SIZE(name); (bkt)++) \ 151 for ((obj) = __hash_first(&(name)[bkt], \ 152 __typeof(*(obj)), member); \ 153 (obj) != NULL; \ 154 (obj) = __hash_next(obj, \ 155 __typeof(*(obj)), member)) 156 157 #define hash_for_each_safe(name, bkt, tmp, obj, member) \ 158 for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \ 159 (bkt) != HASH_SIZE(name); (bkt)++) \ 160 for ((obj) = __hash_first(&(name)[bkt], \ 161 __typeof(*(obj)), member); \ 162 (obj) != NULL && ((tmp) = &__hash_next(obj, \ 163 __typeof(*(obj)), member)->member, 1); \ 164 (obj) = container_of(tmp, __typeof(*(obj)), member)) 165 166 #define hash_for_each_possible(...) \ 167 hash_for_each_possible_rcu(__VA_ARGS__) 168 169 #define hash_for_each_possible_rcu_notrace(...) \ 170 hash_for_each_possible_rcu(__VA_ARGS__) 171 172 #define hash_for_each_possible_rcu(name, obj, member, key) \ 173 for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \ 174 __typeof(*(obj)), member); \ 175 (obj) != NULL; \ 176 (obj) = __hash_next(obj, __typeof(*(obj)), member)) 177 178 #define hash_for_each_possible_safe(name, obj, tmp, member, key) \ 179 for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \ 180 __typeof(*(obj)), member); \ 181 (obj) != NULL && ((tmp) = &__hash_next(obj, \ 182 __typeof(*(obj)), member)->member, 1); \ 183 (obj) = container_of(tmp, __typeof(*(obj)), member)) 184 185 #endif /* _LINUXKPI_LINUX_HASHTABLE_H */ 186