1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3 * erofs-utils/include/erofs/hashtable.h
4 *
5 * Original code taken from 'linux/include/linux/hash{,table}.h'
6 */
7 #ifndef __EROFS_HASHTABLE_H
8 #define __EROFS_HASHTABLE_H
9
10 /*
11 * Fast hashing routine for ints, longs and pointers.
12 * (C) 2002 Nadia Yvette Chambers, IBM
13 */
14
15 /*
16 * Statically sized hash table implementation
17 * (C) 2012 Sasha Levin <levinsasha928@gmail.com>
18 */
19
20 #include "defs.h"
21
22 /*
23 * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and
24 * fs/inode.c. It's not actually prime any more (the previous primes
25 * were actively bad for hashing), but the name remains.
26 */
27 #if BITS_PER_LONG == 32
28 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32
29 #define hash_long(val, bits) hash_32(val, bits)
30 #elif BITS_PER_LONG == 64
31 #define hash_long(val, bits) hash_64(val, bits)
32 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64
33 #else
34 #error Wordsize not 32 or 64
35 #endif
36
37 /*
38 * This hash multiplies the input by a large odd number and takes the
39 * high bits. Since multiplication propagates changes to the most
40 * significant end only, it is essential that the high bits of the
41 * product be used for the hash value.
42 *
43 * Chuck Lever verified the effectiveness of this technique:
44 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
45 *
46 * Although a random odd number will do, it turns out that the golden
47 * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
48 * properties. (See Knuth vol 3, section 6.4, exercise 9.)
49 *
50 * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,
51 * which is very slightly easier to multiply by and makes no
52 * difference to the hash distribution.
53 */
54 #define GOLDEN_RATIO_32 0x61C88647
55 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
56
57 struct hlist_head {
58 struct hlist_node *first;
59 };
60
61 struct hlist_node {
62 struct hlist_node *next, **pprev;
63 };
64
65 /*
66 * Architectures might want to move the poison pointer offset
67 * into some well-recognized area such as 0xdead000000000000,
68 * that is also not mappable by user-space exploits:
69 */
70 #ifdef CONFIG_ILLEGAL_POINTER_VALUE
71 # define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
72 #else
73 # define POISON_POINTER_DELTA 0
74 #endif
75
76 /*
77 * These are non-NULL pointers that will result in page faults
78 * under normal circumstances, used to verify that nobody uses
79 * non-initialized list entries.
80 */
81 #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
82 #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
83
84 /*
85 * Double linked lists with a single pointer list head.
86 * Mostly useful for hash tables where the two pointer list head is
87 * too wasteful.
88 * You lose the ability to access the tail in O(1).
89 */
90
91 #define HLIST_HEAD_INIT { .first = NULL }
92 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
93 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
INIT_HLIST_NODE(struct hlist_node * h)94 static inline void INIT_HLIST_NODE(struct hlist_node *h)
95 {
96 h->next = NULL;
97 h->pprev = NULL;
98 }
99
hlist_unhashed(const struct hlist_node * h)100 static inline int hlist_unhashed(const struct hlist_node *h)
101 {
102 return !h->pprev;
103 }
104
hlist_empty(const struct hlist_head * h)105 static inline int hlist_empty(const struct hlist_head *h)
106 {
107 return !h->first;
108 }
109
__hlist_del(struct hlist_node * n)110 static inline void __hlist_del(struct hlist_node *n)
111 {
112 struct hlist_node *next = n->next;
113 struct hlist_node **pprev = n->pprev;
114
115 *pprev = next;
116 if (next)
117 next->pprev = pprev;
118 }
119
hlist_del(struct hlist_node * n)120 static inline void hlist_del(struct hlist_node *n)
121 {
122 __hlist_del(n);
123 n->next = LIST_POISON1;
124 n->pprev = LIST_POISON2;
125 }
126
hlist_del_init(struct hlist_node * n)127 static inline void hlist_del_init(struct hlist_node *n)
128 {
129 if (!hlist_unhashed(n)) {
130 __hlist_del(n);
131 INIT_HLIST_NODE(n);
132 }
133 }
134
hlist_add_head(struct hlist_node * n,struct hlist_head * h)135 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
136 {
137 struct hlist_node *first = h->first;
138
139 n->next = first;
140 if (first)
141 first->pprev = &n->next;
142 h->first = n;
143 n->pprev = &h->first;
144 }
145
146 /* next must be != NULL */
hlist_add_before(struct hlist_node * n,struct hlist_node * next)147 static inline void hlist_add_before(struct hlist_node *n,
148 struct hlist_node *next)
149 {
150 n->pprev = next->pprev;
151 n->next = next;
152 next->pprev = &n->next;
153 *(n->pprev) = n;
154 }
155
hlist_add_behind(struct hlist_node * n,struct hlist_node * prev)156 static inline void hlist_add_behind(struct hlist_node *n,
157 struct hlist_node *prev)
158 {
159 n->next = prev->next;
160 prev->next = n;
161 n->pprev = &prev->next;
162
163 if (n->next)
164 n->next->pprev = &n->next;
165 }
166
167 /* after that we'll appear to be on some hlist and hlist_del will work */
hlist_add_fake(struct hlist_node * n)168 static inline void hlist_add_fake(struct hlist_node *n)
169 {
170 n->pprev = &n->next;
171 }
172
173 /*
174 * Move a list from one list head to another. Fixup the pprev
175 * reference of the first entry if it exists.
176 */
hlist_move_list(struct hlist_head * old,struct hlist_head * new)177 static inline void hlist_move_list(struct hlist_head *old,
178 struct hlist_head *new)
179 {
180 new->first = old->first;
181 if (new->first)
182 new->first->pprev = &new->first;
183 old->first = NULL;
184 }
185
186 #define hlist_entry(ptr, type, member) container_of(ptr, type, member)
187
188 #define hlist_for_each(pos, head) \
189 for (pos = (head)->first; pos; pos = pos->next)
190
191 #define hlist_for_each_safe(pos, n, head) \
192 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
193 pos = n)
194
195 #define hlist_entry_safe(ptr, type, member) \
196 ({ typeof(ptr) ____ptr = (ptr); \
197 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
198 })
199
200 /**
201 * hlist_for_each_entry - iterate over list of given type
202 * @pos:the type * to use as a loop cursor.
203 * @head:the head for your list.
204 * @member:the name of the hlist_node within the struct.
205 */
206 #define hlist_for_each_entry(pos, head, member) \
207 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
208 pos; \
209 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
210
211 /**
212 * hlist_for_each_entry_continue
213 * iterate over a hlist continuing after current point
214 * @pos:the type * to use as a loop cursor.
215 * @member:the name of the hlist_node within the struct.
216 */
217 #define hlist_for_each_entry_continue(pos, member) \
218 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
219 pos; \
220 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
221
222 /**
223 * hlist_for_each_entry_from
224 * iterate over a hlist continuing from current point
225 * @pos: the type * to use as a loop cursor.
226 * @member: the name of the hlist_node within the struct.
227 */
228 #define hlist_for_each_entry_from(pos, member) \
229 for (; pos; \
230 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
231
232 /**
233 * hlist_for_each_entry_safe
234 * iterate over list of given type safe against removal of list entry
235 * @pos:the type * to use as a loop cursor.
236 * @n:another &struct hlist_node to use as temporary storage
237 * @head:the head for your list.
238 * @member:the name of the hlist_node within the struct.
239 */
240 #define hlist_for_each_entry_safe(pos, n, head, member) \
241 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
242 pos && ({ n = pos->member.next; 1; }); \
243 pos = hlist_entry_safe(n, typeof(*pos), member))
244
__hash_32(u32 val)245 static inline u32 __hash_32(u32 val)
246 {
247 return val * GOLDEN_RATIO_32;
248 }
249
hash_32(u32 val,unsigned int bits)250 static inline u32 hash_32(u32 val, unsigned int bits)
251 {
252 /* High bits are more random, so use them. */
253 return __hash_32(val) >> (32 - bits);
254 }
255
hash_64(u64 val,unsigned int bits)256 static __always_inline u32 hash_64(u64 val, unsigned int bits)
257 {
258 #if BITS_PER_LONG == 64
259 /* 64x64-bit multiply is efficient on all 64-bit processors */
260 return val * GOLDEN_RATIO_64 >> (64 - bits);
261 #else
262 /* Hash 64 bits using only 32x32-bit multiply. */
263 return hash_32((u32)val ^ __hash_32(val >> 32), bits);
264 #endif
265 }
266
267 /**
268 * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
269 * @n - parameter
270 *
271 * constant-capable log of base 2 calculation
272 * - this can be used to initialise global variables from constant data, hence
273 * the massive ternary operator construction
274 *
275 * selects the appropriately-sized optimised version depending on sizeof(n)
276 */
277 #define ilog2(n) \
278 ( \
279 (n) & (1ULL << 63) ? 63 : \
280 (n) & (1ULL << 62) ? 62 : \
281 (n) & (1ULL << 61) ? 61 : \
282 (n) & (1ULL << 60) ? 60 : \
283 (n) & (1ULL << 59) ? 59 : \
284 (n) & (1ULL << 58) ? 58 : \
285 (n) & (1ULL << 57) ? 57 : \
286 (n) & (1ULL << 56) ? 56 : \
287 (n) & (1ULL << 55) ? 55 : \
288 (n) & (1ULL << 54) ? 54 : \
289 (n) & (1ULL << 53) ? 53 : \
290 (n) & (1ULL << 52) ? 52 : \
291 (n) & (1ULL << 51) ? 51 : \
292 (n) & (1ULL << 50) ? 50 : \
293 (n) & (1ULL << 49) ? 49 : \
294 (n) & (1ULL << 48) ? 48 : \
295 (n) & (1ULL << 47) ? 47 : \
296 (n) & (1ULL << 46) ? 46 : \
297 (n) & (1ULL << 45) ? 45 : \
298 (n) & (1ULL << 44) ? 44 : \
299 (n) & (1ULL << 43) ? 43 : \
300 (n) & (1ULL << 42) ? 42 : \
301 (n) & (1ULL << 41) ? 41 : \
302 (n) & (1ULL << 40) ? 40 : \
303 (n) & (1ULL << 39) ? 39 : \
304 (n) & (1ULL << 38) ? 38 : \
305 (n) & (1ULL << 37) ? 37 : \
306 (n) & (1ULL << 36) ? 36 : \
307 (n) & (1ULL << 35) ? 35 : \
308 (n) & (1ULL << 34) ? 34 : \
309 (n) & (1ULL << 33) ? 33 : \
310 (n) & (1ULL << 32) ? 32 : \
311 (n) & (1ULL << 31) ? 31 : \
312 (n) & (1ULL << 30) ? 30 : \
313 (n) & (1ULL << 29) ? 29 : \
314 (n) & (1ULL << 28) ? 28 : \
315 (n) & (1ULL << 27) ? 27 : \
316 (n) & (1ULL << 26) ? 26 : \
317 (n) & (1ULL << 25) ? 25 : \
318 (n) & (1ULL << 24) ? 24 : \
319 (n) & (1ULL << 23) ? 23 : \
320 (n) & (1ULL << 22) ? 22 : \
321 (n) & (1ULL << 21) ? 21 : \
322 (n) & (1ULL << 20) ? 20 : \
323 (n) & (1ULL << 19) ? 19 : \
324 (n) & (1ULL << 18) ? 18 : \
325 (n) & (1ULL << 17) ? 17 : \
326 (n) & (1ULL << 16) ? 16 : \
327 (n) & (1ULL << 15) ? 15 : \
328 (n) & (1ULL << 14) ? 14 : \
329 (n) & (1ULL << 13) ? 13 : \
330 (n) & (1ULL << 12) ? 12 : \
331 (n) & (1ULL << 11) ? 11 : \
332 (n) & (1ULL << 10) ? 10 : \
333 (n) & (1ULL << 9) ? 9 : \
334 (n) & (1ULL << 8) ? 8 : \
335 (n) & (1ULL << 7) ? 7 : \
336 (n) & (1ULL << 6) ? 6 : \
337 (n) & (1ULL << 5) ? 5 : \
338 (n) & (1ULL << 4) ? 4 : \
339 (n) & (1ULL << 3) ? 3 : \
340 (n) & (1ULL << 2) ? 2 : \
341 (n) & (1ULL << 1) ? 1 : 0 \
342 )
343
344 #define DEFINE_HASHTABLE(name, bits) \
345 struct hlist_head name[1 << (bits)] = \
346 { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
347
348 #define DECLARE_HASHTABLE(name, bits) \
349 struct hlist_head name[1 << (bits)]
350
351 #define HASH_SIZE(name) (ARRAY_SIZE(name))
352 #define HASH_BITS(name) ilog2(HASH_SIZE(name))
353
354 /* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels*/
355 #define hash_min(val, bits) \
356 (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
357
__hash_init(struct hlist_head * ht,unsigned int sz)358 static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
359 {
360 unsigned int i;
361
362 for (i = 0; i < sz; i++)
363 INIT_HLIST_HEAD(&ht[i]);
364 }
365
366 /**
367 * hash_init - initialize a hash table
368 * @hashtable: hashtable to be initialized
369 *
370 * Calculates the size of the hashtable from the given parameter, otherwise
371 * same as hash_init_size.
372 *
373 * This has to be a macro since HASH_BITS() will not work on pointers since
374 * it calculates the size during preprocessing.
375 */
376 #define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
377
378 /**
379 * hash_add - add an object to a hashtable
380 * @hashtable: hashtable to add to
381 * @node: the &struct hlist_node of the object to be added
382 * @key: the key of the object to be added
383 */
384 #define hash_add(hashtable, node, key) \
385 hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
386
387 /**
388 * hash_hashed - check whether an object is in any hashtable
389 * @node: the &struct hlist_node of the object to be checked
390 */
hash_hashed(struct hlist_node * node)391 static inline bool hash_hashed(struct hlist_node *node)
392 {
393 return !hlist_unhashed(node);
394 }
395
__hash_empty(struct hlist_head * ht,unsigned int sz)396 static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
397 {
398 unsigned int i;
399
400 for (i = 0; i < sz; i++)
401 if (!hlist_empty(&ht[i]))
402 return false;
403
404 return true;
405 }
406
407 /**
408 * hash_empty - check whether a hashtable is empty
409 * @hashtable: hashtable to check
410 *
411 * This has to be a macro since HASH_BITS() will not work on pointers since
412 * it calculates the size during preprocessing.
413 */
414 #define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
415
416 /**
417 * hash_del - remove an object from a hashtable
418 * @node: &struct hlist_node of the object to remove
419 */
hash_del(struct hlist_node * node)420 static inline void hash_del(struct hlist_node *node)
421 {
422 hlist_del_init(node);
423 }
424
425 /**
426 * hash_for_each - iterate over a hashtable
427 * @name: hashtable to iterate
428 * @bkt: integer to use as bucket loop cursor
429 * @obj: the type * to use as a loop cursor for each entry
430 * @member: the name of the hlist_node within the struct
431 */
432 #define hash_for_each(name, bkt, obj, member) \
433 for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
434 (bkt)++)\
435 hlist_for_each_entry(obj, &name[bkt], member)
436
437 /**
438 * hash_for_each_safe - iterate over a hashtable safe against removal of
439 * hash entry
440 * @name: hashtable to iterate
441 * @bkt: integer to use as bucket loop cursor
442 * @tmp: a &struct used for temporary storage
443 * @obj: the type * to use as a loop cursor for each entry
444 * @member: the name of the hlist_node within the struct
445 */
446 #define hash_for_each_safe(name, bkt, tmp, obj, member) \
447 for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
448 (bkt)++)\
449 hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
450
451 /**
452 * hash_for_each_possible - iterate over all possible objects hashing to the
453 * same bucket
454 * @name: hashtable to iterate
455 * @obj: the type * to use as a loop cursor for each entry
456 * @member: the name of the hlist_node within the struct
457 * @key: the key of the objects to iterate over
458 */
459 #define hash_for_each_possible(name, obj, member, key) \
460 hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
461
462 #endif
463