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
__hash_init(struct lkpi_hash_head * ht,unsigned long size)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
__hash_node_type_assert(struct hlist_node * node)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
hash_hashed(struct hlist_node * node)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
__hash_empty(struct lkpi_hash_head * ht,unsigned long size)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
hash_del_rcu(struct hlist_node * node)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