1 /*
2 * Copyright 2017 Advanced Micro Devices, Inc.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 *
22 */
23
24 #ifndef _LINUX_CHASH_H
25 #define _LINUX_CHASH_H
26
27 #include <linux/types.h>
28 #include <linux/hash.h>
29 #include <linux/bug.h>
30 #include <asm/bitsperlong.h>
31
32 #if BITS_PER_LONG == 32
33 # define _CHASH_LONG_SHIFT 5
34 #elif BITS_PER_LONG == 64
35 # define _CHASH_LONG_SHIFT 6
36 #else
37 # error "Unexpected BITS_PER_LONG"
38 #endif
39
40 struct __chash_table {
41 u8 bits;
42 u8 key_size;
43 unsigned int value_size;
44 u32 size_mask;
45 unsigned long *occup_bitmap, *valid_bitmap;
46 union {
47 u32 *keys32;
48 u64 *keys64;
49 };
50 u8 *values;
51
52 #ifdef CONFIG_CHASH_STATS
53 u64 hits, hits_steps, hits_time_ns;
54 u64 miss, miss_steps, miss_time_ns;
55 u64 relocs, reloc_dist;
56 #endif
57 };
58
59 #define __CHASH_BITMAP_SIZE(bits) \
60 (((1 << (bits)) + BITS_PER_LONG - 1) / BITS_PER_LONG)
61 #define __CHASH_ARRAY_SIZE(bits, size) \
62 ((((size) << (bits)) + sizeof(long) - 1) / sizeof(long))
63
64 #define __CHASH_DATA_SIZE(bits, key_size, value_size) \
65 (__CHASH_BITMAP_SIZE(bits) * 2 + \
66 __CHASH_ARRAY_SIZE(bits, key_size) + \
67 __CHASH_ARRAY_SIZE(bits, value_size))
68
69 #define STRUCT_CHASH_TABLE(bits, key_size, value_size) \
70 struct { \
71 struct __chash_table table; \
72 unsigned long data \
73 [__CHASH_DATA_SIZE(bits, key_size, value_size)];\
74 }
75
76 /**
77 * struct chash_table - Dynamically allocated closed hash table
78 *
79 * Use this struct for dynamically allocated hash tables (using
80 * chash_table_alloc and chash_table_free), where the size is
81 * determined at runtime.
82 */
83 struct chash_table {
84 struct __chash_table table;
85 unsigned long *data;
86 };
87
88 /**
89 * DECLARE_CHASH_TABLE - macro to declare a closed hash table
90 * @table: name of the declared hash table
91 * @bts: Table size will be 2^bits entries
92 * @key_sz: Size of hash keys in bytes, 4 or 8
93 * @val_sz: Size of data values in bytes, can be 0
94 *
95 * This declares the hash table variable with a static size.
96 *
97 * The closed hash table stores key-value pairs with low memory and
98 * lookup overhead. In operation it performs no dynamic memory
99 * management. The data being stored does not require any
100 * list_heads. The hash table performs best with small @val_sz and as
101 * long as some space (about 50%) is left free in the table. But the
102 * table can still work reasonably efficiently even when filled up to
103 * about 90%. If bigger data items need to be stored and looked up,
104 * store the pointer to it as value in the hash table.
105 *
106 * @val_sz may be 0. This can be useful when all the stored
107 * information is contained in the key itself and the fact that it is
108 * in the hash table (or not).
109 */
110 #define DECLARE_CHASH_TABLE(table, bts, key_sz, val_sz) \
111 STRUCT_CHASH_TABLE(bts, key_sz, val_sz) table
112
113 #ifdef CONFIG_CHASH_STATS
114 #define __CHASH_STATS_INIT(prefix), \
115 prefix.hits = 0, \
116 prefix.hits_steps = 0, \
117 prefix.hits_time_ns = 0, \
118 prefix.miss = 0, \
119 prefix.miss_steps = 0, \
120 prefix.miss_time_ns = 0, \
121 prefix.relocs = 0, \
122 prefix.reloc_dist = 0
123 #else
124 #define __CHASH_STATS_INIT(prefix)
125 #endif
126
127 #define __CHASH_TABLE_INIT(prefix, data, bts, key_sz, val_sz) \
128 prefix.bits = (bts), \
129 prefix.key_size = (key_sz), \
130 prefix.value_size = (val_sz), \
131 prefix.size_mask = ((1 << bts) - 1), \
132 prefix.occup_bitmap = &data[0], \
133 prefix.valid_bitmap = &data \
134 [__CHASH_BITMAP_SIZE(bts)], \
135 prefix.keys64 = (u64 *)&data \
136 [__CHASH_BITMAP_SIZE(bts) * 2], \
137 prefix.values = (u8 *)&data \
138 [__CHASH_BITMAP_SIZE(bts) * 2 + \
139 __CHASH_ARRAY_SIZE(bts, key_sz)] \
140 __CHASH_STATS_INIT(prefix)
141
142 /**
143 * DEFINE_CHASH_TABLE - macro to define and initialize a closed hash table
144 * @tbl: name of the declared hash table
145 * @bts: Table size will be 2^bits entries
146 * @key_sz: Size of hash keys in bytes, 4 or 8
147 * @val_sz: Size of data values in bytes, can be 0
148 *
149 * Note: the macro can be used for global and local hash table variables.
150 */
151 #define DEFINE_CHASH_TABLE(tbl, bts, key_sz, val_sz) \
152 DECLARE_CHASH_TABLE(tbl, bts, key_sz, val_sz) = { \
153 .table = { \
154 __CHASH_TABLE_INIT(, (tbl).data, bts, key_sz, val_sz) \
155 }, \
156 .data = {0} \
157 }
158
159 /**
160 * INIT_CHASH_TABLE - Initialize a hash table declared by DECLARE_CHASH_TABLE
161 * @tbl: name of the declared hash table
162 * @bts: Table size will be 2^bits entries
163 * @key_sz: Size of hash keys in bytes, 4 or 8
164 * @val_sz: Size of data values in bytes, can be 0
165 */
166 #define INIT_CHASH_TABLE(tbl, bts, key_sz, val_sz) \
167 __CHASH_TABLE_INIT(((tbl).table), (tbl).data, bts, key_sz, val_sz)
168
169 int chash_table_alloc(struct chash_table *table, u8 bits, u8 key_size,
170 unsigned int value_size, gfp_t gfp_mask);
171 void chash_table_free(struct chash_table *table);
172
173 /**
174 * chash_table_dump_stats - Dump statistics of a closed hash table
175 * @tbl: Pointer to the table structure
176 *
177 * Dumps some performance statistics of the table gathered in operation
178 * in the kernel log using pr_debug. If CONFIG_DYNAMIC_DEBUG is enabled,
179 * user must turn on messages for chash.c (file chash.c +p).
180 */
181 #ifdef CONFIG_CHASH_STATS
182 #define chash_table_dump_stats(tbl) __chash_table_dump_stats(&(*tbl).table)
183
184 void __chash_table_dump_stats(struct __chash_table *table);
185 #else
186 #define chash_table_dump_stats(tbl)
187 #endif
188
189 /**
190 * chash_table_reset_stats - Reset statistics of a closed hash table
191 * @tbl: Pointer to the table structure
192 */
193 #ifdef CONFIG_CHASH_STATS
194 #define chash_table_reset_stats(tbl) __chash_table_reset_stats(&(*tbl).table)
195
__chash_table_reset_stats(struct __chash_table * table)196 static inline void __chash_table_reset_stats(struct __chash_table *table)
197 {
198 (void)table __CHASH_STATS_INIT((*table));
199 }
200 #else
201 #define chash_table_reset_stats(tbl)
202 #endif
203
204 /**
205 * chash_table_copy_in - Copy a new value into the hash table
206 * @tbl: Pointer to the table structure
207 * @key: Key of the entry to add or update
208 * @value: Pointer to value to copy, may be NULL
209 *
210 * If @key already has an entry, its value is replaced. Otherwise a
211 * new entry is added. If @value is NULL, the value is left unchanged
212 * or uninitialized. Returns 1 if an entry already existed, 0 if a new
213 * entry was added or %-ENOMEM if there was no free space in the
214 * table.
215 */
216 #define chash_table_copy_in(tbl, key, value) \
217 __chash_table_copy_in(&(*tbl).table, key, value)
218
219 int __chash_table_copy_in(struct __chash_table *table, u64 key,
220 const void *value);
221
222 /**
223 * chash_table_copy_out - Copy a value out of the hash table
224 * @tbl: Pointer to the table structure
225 * @key: Key of the entry to find
226 * @value: Pointer to value to copy, may be NULL
227 *
228 * If @value is not NULL and the table has a non-0 value_size, the
229 * value at @key is copied to @value. Returns the slot index of the
230 * entry or %-EINVAL if @key was not found.
231 */
232 #define chash_table_copy_out(tbl, key, value) \
233 __chash_table_copy_out(&(*tbl).table, key, value, false)
234
235 int __chash_table_copy_out(struct __chash_table *table, u64 key,
236 void *value, bool remove);
237
238 /**
239 * chash_table_remove - Remove an entry from the hash table
240 * @tbl: Pointer to the table structure
241 * @key: Key of the entry to find
242 * @value: Pointer to value to copy, may be NULL
243 *
244 * If @value is not NULL and the table has a non-0 value_size, the
245 * value at @key is copied to @value. The entry is removed from the
246 * table. Returns the slot index of the removed entry or %-EINVAL if
247 * @key was not found.
248 */
249 #define chash_table_remove(tbl, key, value) \
250 __chash_table_copy_out(&(*tbl).table, key, value, true)
251
252 /*
253 * Low level iterator API used internally by the above functions.
254 */
255 struct chash_iter {
256 struct __chash_table *table;
257 unsigned long mask;
258 int slot;
259 };
260
261 /**
262 * CHASH_ITER_INIT - Initialize a hash table iterator
263 * @tbl: Pointer to hash table to iterate over
264 * @s: Initial slot number
265 */
266 #define CHASH_ITER_INIT(table, s) { \
267 table, \
268 1UL << ((s) & (BITS_PER_LONG - 1)), \
269 s \
270 }
271 /**
272 * CHASH_ITER_SET - Set hash table iterator to new slot
273 * @iter: Iterator
274 * @s: Slot number
275 */
276 #define CHASH_ITER_SET(iter, s) \
277 (iter).mask = 1UL << ((s) & (BITS_PER_LONG - 1)), \
278 (iter).slot = (s)
279 /**
280 * CHASH_ITER_INC - Increment hash table iterator
281 * @table: Hash table to iterate over
282 *
283 * Wraps around at the end.
284 */
285 #define CHASH_ITER_INC(iter) do { \
286 (iter).mask = (iter).mask << 1 | \
287 (iter).mask >> (BITS_PER_LONG - 1); \
288 (iter).slot = ((iter).slot + 1) & (iter).table->size_mask; \
289 } while (0)
290
chash_iter_is_valid(const struct chash_iter iter)291 static inline bool chash_iter_is_valid(const struct chash_iter iter)
292 {
293 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
294 return !!(iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &
295 iter.mask);
296 }
chash_iter_is_empty(const struct chash_iter iter)297 static inline bool chash_iter_is_empty(const struct chash_iter iter)
298 {
299 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
300 return !(iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &
301 iter.mask);
302 }
303
chash_iter_set_valid(const struct chash_iter iter)304 static inline void chash_iter_set_valid(const struct chash_iter iter)
305 {
306 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
307 iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] |= iter.mask;
308 iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] |= iter.mask;
309 }
chash_iter_set_invalid(const struct chash_iter iter)310 static inline void chash_iter_set_invalid(const struct chash_iter iter)
311 {
312 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
313 iter.table->valid_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &= ~iter.mask;
314 }
chash_iter_set_empty(const struct chash_iter iter)315 static inline void chash_iter_set_empty(const struct chash_iter iter)
316 {
317 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
318 iter.table->occup_bitmap[iter.slot >> _CHASH_LONG_SHIFT] &= ~iter.mask;
319 }
320
chash_iter_key32(const struct chash_iter iter)321 static inline u32 chash_iter_key32(const struct chash_iter iter)
322 {
323 BUG_ON(iter.table->key_size != 4);
324 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
325 return iter.table->keys32[iter.slot];
326 }
chash_iter_key64(const struct chash_iter iter)327 static inline u64 chash_iter_key64(const struct chash_iter iter)
328 {
329 BUG_ON(iter.table->key_size != 8);
330 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
331 return iter.table->keys64[iter.slot];
332 }
chash_iter_key(const struct chash_iter iter)333 static inline u64 chash_iter_key(const struct chash_iter iter)
334 {
335 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
336 return (iter.table->key_size == 4) ?
337 iter.table->keys32[iter.slot] : iter.table->keys64[iter.slot];
338 }
339
chash_iter_hash32(const struct chash_iter iter)340 static inline u32 chash_iter_hash32(const struct chash_iter iter)
341 {
342 BUG_ON(iter.table->key_size != 4);
343 return hash_32(chash_iter_key32(iter), iter.table->bits);
344 }
345
chash_iter_hash64(const struct chash_iter iter)346 static inline u32 chash_iter_hash64(const struct chash_iter iter)
347 {
348 BUG_ON(iter.table->key_size != 8);
349 return hash_64(chash_iter_key64(iter), iter.table->bits);
350 }
351
chash_iter_hash(const struct chash_iter iter)352 static inline u32 chash_iter_hash(const struct chash_iter iter)
353 {
354 return (iter.table->key_size == 4) ?
355 hash_32(chash_iter_key32(iter), iter.table->bits) :
356 hash_64(chash_iter_key64(iter), iter.table->bits);
357 }
358
chash_iter_value(const struct chash_iter iter)359 static inline void *chash_iter_value(const struct chash_iter iter)
360 {
361 BUG_ON((unsigned)iter.slot >= (1 << iter.table->bits));
362 return iter.table->values +
363 ((unsigned long)iter.slot * iter.table->value_size);
364 }
365
366 #endif /* _LINUX_CHASH_H */
367
