1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#ifndef __LIBCFS_HASH_H__
43#define __LIBCFS_HASH_H__
44
45
46
47
48
49
50
51
52
53
54
55#define CFS_GOLDEN_RATIO_PRIME_32 0x9e370001UL
56
57#define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
58
59
60
61
62
63
64
65
66#include <linux/hash.h>
67
68
69#define CFS_HASH_DEBUG_NONE 0
70
71
72#define CFS_HASH_DEBUG_1 1
73
74#define CFS_HASH_DEBUG_2 2
75
76#define CFS_HASH_DEBUG_LEVEL CFS_HASH_DEBUG_NONE
77
78struct cfs_hash_ops;
79struct cfs_hash_lock_ops;
80struct cfs_hash_hlist_ops;
81
82union cfs_hash_lock {
83 rwlock_t rw;
84 spinlock_t spin;
85};
86
87
88
89
90
91
92
93
94
95
96
97
98struct cfs_hash_bucket {
99 union cfs_hash_lock hsb_lock;
100 __u32 hsb_count;
101 __u32 hsb_version;
102 unsigned int hsb_index;
103 int hsb_depmax;
104 long hsb_head[0];
105};
106
107
108
109
110struct cfs_hash_bd {
111 struct cfs_hash_bucket *bd_bucket;
112 unsigned int bd_offset;
113};
114
115#define CFS_HASH_NAME_LEN 16
116#define CFS_HASH_BIGNAME_LEN 64
117
118#define CFS_HASH_BKT_BITS 3
119#define CFS_HASH_BITS_MAX 30
120#define CFS_HASH_BITS_MIN CFS_HASH_BKT_BITS
121
122
123
124
125enum cfs_hash_tag {
126
127
128
129
130
131
132
133
134 CFS_HASH_NO_LOCK = 1 << 0,
135
136 CFS_HASH_NO_BKTLOCK = 1 << 1,
137
138 CFS_HASH_RW_BKTLOCK = 1 << 2,
139
140 CFS_HASH_SPIN_BKTLOCK = 1 << 3,
141
142 CFS_HASH_ADD_TAIL = 1 << 4,
143
144 CFS_HASH_NO_ITEMREF = 1 << 5,
145
146 CFS_HASH_BIGNAME = 1 << 6,
147
148 CFS_HASH_COUNTER = 1 << 7,
149
150 CFS_HASH_REHASH_KEY = 1 << 8,
151
152 CFS_HASH_REHASH = 1 << 9,
153
154 CFS_HASH_SHRINK = 1 << 10,
155
156 CFS_HASH_ASSERT_EMPTY = 1 << 11,
157
158 CFS_HASH_DEPTH = 1 << 12,
159
160
161
162
163 CFS_HASH_NBLK_CHANGE = 1 << 13,
164
165
166};
167
168
169#define CFS_HASH_DEFAULT (CFS_HASH_RW_BKTLOCK | \
170 CFS_HASH_COUNTER | CFS_HASH_REHASH)
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211struct cfs_hash {
212
213
214 union cfs_hash_lock hs_lock;
215
216 struct cfs_hash_ops *hs_ops;
217
218 struct cfs_hash_lock_ops *hs_lops;
219
220 struct cfs_hash_hlist_ops *hs_hops;
221
222 struct cfs_hash_bucket **hs_buckets;
223
224 atomic_t hs_count;
225
226 __u16 hs_flags;
227
228 __u16 hs_extra_bytes;
229
230 __u8 hs_iterating;
231
232 __u8 hs_exiting;
233
234 __u8 hs_cur_bits;
235
236 __u8 hs_min_bits;
237
238 __u8 hs_max_bits;
239
240 __u8 hs_rehash_bits;
241
242 __u8 hs_bkt_bits;
243
244 __u16 hs_min_theta;
245
246 __u16 hs_max_theta;
247
248 __u32 hs_rehash_count;
249
250 __u32 hs_iterators;
251
252 cfs_workitem_t hs_rehash_wi;
253
254 atomic_t hs_refcount;
255
256 struct cfs_hash_bucket **hs_rehash_buckets;
257#if CFS_HASH_DEBUG_LEVEL >= CFS_HASH_DEBUG_1
258
259 spinlock_t hs_dep_lock;
260
261 unsigned int hs_dep_max;
262
263 unsigned int hs_dep_bkt;
264
265 unsigned int hs_dep_off;
266
267 unsigned int hs_dep_bits;
268
269 cfs_workitem_t hs_dep_wi;
270#endif
271
272 char hs_name[0];
273};
274
275typedef struct cfs_hash_lock_ops {
276
277 void (*hs_lock)(union cfs_hash_lock *lock, int exclusive);
278
279 void (*hs_unlock)(union cfs_hash_lock *lock, int exclusive);
280
281 void (*hs_bkt_lock)(union cfs_hash_lock *lock, int exclusive);
282
283 void (*hs_bkt_unlock)(union cfs_hash_lock *lock, int exclusive);
284} cfs_hash_lock_ops_t;
285
286typedef struct cfs_hash_hlist_ops {
287
288 struct hlist_head *(*hop_hhead)(struct cfs_hash *hs, struct cfs_hash_bd *bd);
289
290 int (*hop_hhead_size)(struct cfs_hash *hs);
291
292 int (*hop_hnode_add)(struct cfs_hash *hs,
293 struct cfs_hash_bd *bd, struct hlist_node *hnode);
294
295 int (*hop_hnode_del)(struct cfs_hash *hs,
296 struct cfs_hash_bd *bd, struct hlist_node *hnode);
297} cfs_hash_hlist_ops_t;
298
299typedef struct cfs_hash_ops {
300
301 unsigned (*hs_hash)(struct cfs_hash *hs, const void *key, unsigned mask);
302
303 void * (*hs_key)(struct hlist_node *hnode);
304
305 void (*hs_keycpy)(struct hlist_node *hnode, void *key);
306
307
308
309
310 int (*hs_keycmp)(const void *key, struct hlist_node *hnode);
311
312 void * (*hs_object)(struct hlist_node *hnode);
313
314 void (*hs_get)(struct cfs_hash *hs, struct hlist_node *hnode);
315
316 void (*hs_put)(struct cfs_hash *hs, struct hlist_node *hnode);
317
318 void (*hs_put_locked)(struct cfs_hash *hs, struct hlist_node *hnode);
319
320 void (*hs_exit)(struct cfs_hash *hs, struct hlist_node *hnode);
321} cfs_hash_ops_t;
322
323
324#define CFS_HASH_NBKT(hs) \
325 (1U << ((hs)->hs_cur_bits - (hs)->hs_bkt_bits))
326
327
328#define CFS_HASH_RH_NBKT(hs) \
329 (1U << ((hs)->hs_rehash_bits - (hs)->hs_bkt_bits))
330
331
332#define CFS_HASH_BKT_NHLIST(hs) (1U << (hs)->hs_bkt_bits)
333
334
335#define CFS_HASH_NHLIST(hs) (1U << (hs)->hs_cur_bits)
336
337
338#define CFS_HASH_RH_NHLIST(hs) (1U << (hs)->hs_rehash_bits)
339
340static inline int
341cfs_hash_with_no_lock(struct cfs_hash *hs)
342{
343
344 return (hs->hs_flags & CFS_HASH_NO_LOCK) != 0;
345}
346
347static inline int
348cfs_hash_with_no_bktlock(struct cfs_hash *hs)
349{
350
351 return (hs->hs_flags & CFS_HASH_NO_BKTLOCK) != 0;
352}
353
354static inline int
355cfs_hash_with_rw_bktlock(struct cfs_hash *hs)
356{
357
358 return (hs->hs_flags & CFS_HASH_RW_BKTLOCK) != 0;
359}
360
361static inline int
362cfs_hash_with_spin_bktlock(struct cfs_hash *hs)
363{
364
365 return (hs->hs_flags & CFS_HASH_SPIN_BKTLOCK) != 0;
366}
367
368static inline int
369cfs_hash_with_add_tail(struct cfs_hash *hs)
370{
371 return (hs->hs_flags & CFS_HASH_ADD_TAIL) != 0;
372}
373
374static inline int
375cfs_hash_with_no_itemref(struct cfs_hash *hs)
376{
377
378
379
380 return (hs->hs_flags & CFS_HASH_NO_ITEMREF) != 0;
381}
382
383static inline int
384cfs_hash_with_bigname(struct cfs_hash *hs)
385{
386 return (hs->hs_flags & CFS_HASH_BIGNAME) != 0;
387}
388
389static inline int
390cfs_hash_with_counter(struct cfs_hash *hs)
391{
392 return (hs->hs_flags & CFS_HASH_COUNTER) != 0;
393}
394
395static inline int
396cfs_hash_with_rehash(struct cfs_hash *hs)
397{
398 return (hs->hs_flags & CFS_HASH_REHASH) != 0;
399}
400
401static inline int
402cfs_hash_with_rehash_key(struct cfs_hash *hs)
403{
404 return (hs->hs_flags & CFS_HASH_REHASH_KEY) != 0;
405}
406
407static inline int
408cfs_hash_with_shrink(struct cfs_hash *hs)
409{
410 return (hs->hs_flags & CFS_HASH_SHRINK) != 0;
411}
412
413static inline int
414cfs_hash_with_assert_empty(struct cfs_hash *hs)
415{
416 return (hs->hs_flags & CFS_HASH_ASSERT_EMPTY) != 0;
417}
418
419static inline int
420cfs_hash_with_depth(struct cfs_hash *hs)
421{
422 return (hs->hs_flags & CFS_HASH_DEPTH) != 0;
423}
424
425static inline int
426cfs_hash_with_nblk_change(struct cfs_hash *hs)
427{
428 return (hs->hs_flags & CFS_HASH_NBLK_CHANGE) != 0;
429}
430
431static inline int
432cfs_hash_is_exiting(struct cfs_hash *hs)
433{
434 return hs->hs_exiting;
435}
436
437static inline int
438cfs_hash_is_rehashing(struct cfs_hash *hs)
439{
440 return hs->hs_rehash_bits != 0;
441}
442
443static inline int
444cfs_hash_is_iterating(struct cfs_hash *hs)
445{
446 return hs->hs_iterating || hs->hs_iterators != 0;
447}
448
449static inline int
450cfs_hash_bkt_size(struct cfs_hash *hs)
451{
452 return offsetof(struct cfs_hash_bucket, hsb_head[0]) +
453 hs->hs_hops->hop_hhead_size(hs) * CFS_HASH_BKT_NHLIST(hs) +
454 hs->hs_extra_bytes;
455}
456
457#define CFS_HOP(hs, op) (hs)->hs_ops->hs_ ## op
458
459static inline unsigned
460cfs_hash_id(struct cfs_hash *hs, const void *key, unsigned mask)
461{
462 return CFS_HOP(hs, hash)(hs, key, mask);
463}
464
465static inline void *
466cfs_hash_key(struct cfs_hash *hs, struct hlist_node *hnode)
467{
468 return CFS_HOP(hs, key)(hnode);
469}
470
471static inline void
472cfs_hash_keycpy(struct cfs_hash *hs, struct hlist_node *hnode, void *key)
473{
474 if (CFS_HOP(hs, keycpy) != NULL)
475 CFS_HOP(hs, keycpy)(hnode, key);
476}
477
478
479
480
481static inline int
482cfs_hash_keycmp(struct cfs_hash *hs, const void *key, struct hlist_node *hnode)
483{
484 return CFS_HOP(hs, keycmp)(key, hnode);
485}
486
487static inline void *
488cfs_hash_object(struct cfs_hash *hs, struct hlist_node *hnode)
489{
490 return CFS_HOP(hs, object)(hnode);
491}
492
493static inline void
494cfs_hash_get(struct cfs_hash *hs, struct hlist_node *hnode)
495{
496 return CFS_HOP(hs, get)(hs, hnode);
497}
498
499static inline void
500cfs_hash_put_locked(struct cfs_hash *hs, struct hlist_node *hnode)
501{
502 LASSERT(CFS_HOP(hs, put_locked) != NULL);
503
504 return CFS_HOP(hs, put_locked)(hs, hnode);
505}
506
507static inline void
508cfs_hash_put(struct cfs_hash *hs, struct hlist_node *hnode)
509{
510 LASSERT(CFS_HOP(hs, put) != NULL);
511
512 return CFS_HOP(hs, put)(hs, hnode);
513}
514
515static inline void
516cfs_hash_exit(struct cfs_hash *hs, struct hlist_node *hnode)
517{
518 if (CFS_HOP(hs, exit))
519 CFS_HOP(hs, exit)(hs, hnode);
520}
521
522static inline void cfs_hash_lock(struct cfs_hash *hs, int excl)
523{
524 hs->hs_lops->hs_lock(&hs->hs_lock, excl);
525}
526
527static inline void cfs_hash_unlock(struct cfs_hash *hs, int excl)
528{
529 hs->hs_lops->hs_unlock(&hs->hs_lock, excl);
530}
531
532static inline int cfs_hash_dec_and_lock(struct cfs_hash *hs,
533 atomic_t *condition)
534{
535 LASSERT(cfs_hash_with_no_bktlock(hs));
536 return atomic_dec_and_lock(condition, &hs->hs_lock.spin);
537}
538
539static inline void cfs_hash_bd_lock(struct cfs_hash *hs,
540 struct cfs_hash_bd *bd, int excl)
541{
542 hs->hs_lops->hs_bkt_lock(&bd->bd_bucket->hsb_lock, excl);
543}
544
545static inline void cfs_hash_bd_unlock(struct cfs_hash *hs,
546 struct cfs_hash_bd *bd, int excl)
547{
548 hs->hs_lops->hs_bkt_unlock(&bd->bd_bucket->hsb_lock, excl);
549}
550
551
552
553
554
555void cfs_hash_bd_get(struct cfs_hash *hs, const void *key, struct cfs_hash_bd *bd);
556
557static inline void cfs_hash_bd_get_and_lock(struct cfs_hash *hs, const void *key,
558 struct cfs_hash_bd *bd, int excl)
559{
560 cfs_hash_bd_get(hs, key, bd);
561 cfs_hash_bd_lock(hs, bd, excl);
562}
563
564static inline unsigned cfs_hash_bd_index_get(struct cfs_hash *hs, struct cfs_hash_bd *bd)
565{
566 return bd->bd_offset | (bd->bd_bucket->hsb_index << hs->hs_bkt_bits);
567}
568
569static inline void cfs_hash_bd_index_set(struct cfs_hash *hs,
570 unsigned index, struct cfs_hash_bd *bd)
571{
572 bd->bd_bucket = hs->hs_buckets[index >> hs->hs_bkt_bits];
573 bd->bd_offset = index & (CFS_HASH_BKT_NHLIST(hs) - 1U);
574}
575
576static inline void *
577cfs_hash_bd_extra_get(struct cfs_hash *hs, struct cfs_hash_bd *bd)
578{
579 return (void *)bd->bd_bucket +
580 cfs_hash_bkt_size(hs) - hs->hs_extra_bytes;
581}
582
583static inline __u32
584cfs_hash_bd_version_get(struct cfs_hash_bd *bd)
585{
586
587 return bd->bd_bucket->hsb_version;
588}
589
590static inline __u32
591cfs_hash_bd_count_get(struct cfs_hash_bd *bd)
592{
593
594 return bd->bd_bucket->hsb_count;
595}
596
597static inline int
598cfs_hash_bd_depmax_get(struct cfs_hash_bd *bd)
599{
600 return bd->bd_bucket->hsb_depmax;
601}
602
603static inline int
604cfs_hash_bd_compare(struct cfs_hash_bd *bd1, struct cfs_hash_bd *bd2)
605{
606 if (bd1->bd_bucket->hsb_index != bd2->bd_bucket->hsb_index)
607 return bd1->bd_bucket->hsb_index - bd2->bd_bucket->hsb_index;
608
609 if (bd1->bd_offset != bd2->bd_offset)
610 return bd1->bd_offset - bd2->bd_offset;
611
612 return 0;
613}
614
615void cfs_hash_bd_add_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd,
616 struct hlist_node *hnode);
617void cfs_hash_bd_del_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd,
618 struct hlist_node *hnode);
619void cfs_hash_bd_move_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd_old,
620 struct cfs_hash_bd *bd_new, struct hlist_node *hnode);
621
622static inline int cfs_hash_bd_dec_and_lock(struct cfs_hash *hs, struct cfs_hash_bd *bd,
623 atomic_t *condition)
624{
625 LASSERT(cfs_hash_with_spin_bktlock(hs));
626 return atomic_dec_and_lock(condition,
627 &bd->bd_bucket->hsb_lock.spin);
628}
629
630static inline struct hlist_head *cfs_hash_bd_hhead(struct cfs_hash *hs,
631 struct cfs_hash_bd *bd)
632{
633 return hs->hs_hops->hop_hhead(hs, bd);
634}
635
636struct hlist_node *cfs_hash_bd_lookup_locked(struct cfs_hash *hs,
637 struct cfs_hash_bd *bd, const void *key);
638struct hlist_node *cfs_hash_bd_peek_locked(struct cfs_hash *hs,
639 struct cfs_hash_bd *bd, const void *key);
640struct hlist_node *cfs_hash_bd_findadd_locked(struct cfs_hash *hs,
641 struct cfs_hash_bd *bd, const void *key,
642 struct hlist_node *hnode,
643 int insist_add);
644struct hlist_node *cfs_hash_bd_finddel_locked(struct cfs_hash *hs,
645 struct cfs_hash_bd *bd, const void *key,
646 struct hlist_node *hnode);
647
648
649
650
651
652void cfs_hash_dual_bd_get(struct cfs_hash *hs, const void *key, struct cfs_hash_bd *bds);
653void cfs_hash_dual_bd_lock(struct cfs_hash *hs, struct cfs_hash_bd *bds, int excl);
654void cfs_hash_dual_bd_unlock(struct cfs_hash *hs, struct cfs_hash_bd *bds, int excl);
655
656static inline void cfs_hash_dual_bd_get_and_lock(struct cfs_hash *hs, const void *key,
657 struct cfs_hash_bd *bds, int excl)
658{
659 cfs_hash_dual_bd_get(hs, key, bds);
660 cfs_hash_dual_bd_lock(hs, bds, excl);
661}
662
663struct hlist_node *cfs_hash_dual_bd_lookup_locked(struct cfs_hash *hs,
664 struct cfs_hash_bd *bds,
665 const void *key);
666struct hlist_node *cfs_hash_dual_bd_findadd_locked(struct cfs_hash *hs,
667 struct cfs_hash_bd *bds,
668 const void *key,
669 struct hlist_node *hnode,
670 int insist_add);
671struct hlist_node *cfs_hash_dual_bd_finddel_locked(struct cfs_hash *hs,
672 struct cfs_hash_bd *bds,
673 const void *key,
674 struct hlist_node *hnode);
675
676
677struct cfs_hash *cfs_hash_create(char *name, unsigned cur_bits, unsigned max_bits,
678 unsigned bkt_bits, unsigned extra_bytes,
679 unsigned min_theta, unsigned max_theta,
680 cfs_hash_ops_t *ops, unsigned flags);
681
682struct cfs_hash *cfs_hash_getref(struct cfs_hash *hs);
683void cfs_hash_putref(struct cfs_hash *hs);
684
685
686void cfs_hash_add(struct cfs_hash *hs, const void *key,
687 struct hlist_node *hnode);
688int cfs_hash_add_unique(struct cfs_hash *hs, const void *key,
689 struct hlist_node *hnode);
690void *cfs_hash_findadd_unique(struct cfs_hash *hs, const void *key,
691 struct hlist_node *hnode);
692
693
694void *cfs_hash_del(struct cfs_hash *hs, const void *key, struct hlist_node *hnode);
695void *cfs_hash_del_key(struct cfs_hash *hs, const void *key);
696
697
698#define CFS_HASH_LOOP_HOG 1024
699
700typedef int (*cfs_hash_for_each_cb_t)(struct cfs_hash *hs, struct cfs_hash_bd *bd,
701 struct hlist_node *node, void *data);
702void *cfs_hash_lookup(struct cfs_hash *hs, const void *key);
703void cfs_hash_for_each(struct cfs_hash *hs, cfs_hash_for_each_cb_t, void *data);
704void cfs_hash_for_each_safe(struct cfs_hash *hs, cfs_hash_for_each_cb_t, void *data);
705int cfs_hash_for_each_nolock(struct cfs_hash *hs,
706 cfs_hash_for_each_cb_t, void *data);
707int cfs_hash_for_each_empty(struct cfs_hash *hs,
708 cfs_hash_for_each_cb_t, void *data);
709void cfs_hash_for_each_key(struct cfs_hash *hs, const void *key,
710 cfs_hash_for_each_cb_t, void *data);
711typedef int (*cfs_hash_cond_opt_cb_t)(void *obj, void *data);
712void cfs_hash_cond_del(struct cfs_hash *hs, cfs_hash_cond_opt_cb_t, void *data);
713
714void cfs_hash_hlist_for_each(struct cfs_hash *hs, unsigned hindex,
715 cfs_hash_for_each_cb_t, void *data);
716int cfs_hash_is_empty(struct cfs_hash *hs);
717__u64 cfs_hash_size_get(struct cfs_hash *hs);
718
719
720
721
722
723void cfs_hash_rehash_cancel_locked(struct cfs_hash *hs);
724void cfs_hash_rehash_cancel(struct cfs_hash *hs);
725int cfs_hash_rehash(struct cfs_hash *hs, int do_rehash);
726void cfs_hash_rehash_key(struct cfs_hash *hs, const void *old_key,
727 void *new_key, struct hlist_node *hnode);
728
729#if CFS_HASH_DEBUG_LEVEL > CFS_HASH_DEBUG_1
730
731static inline void
732cfs_hash_key_validate(struct cfs_hash *hs, const void *key,
733 struct hlist_node *hnode)
734{
735 LASSERT(cfs_hash_keycmp(hs, key, hnode));
736}
737
738
739static inline void
740cfs_hash_bucket_validate(struct cfs_hash *hs, struct cfs_hash_bd *bd,
741 struct hlist_node *hnode)
742{
743 struct cfs_hash_bd bds[2];
744
745 cfs_hash_dual_bd_get(hs, cfs_hash_key(hs, hnode), bds);
746 LASSERT(bds[0].bd_bucket == bd->bd_bucket ||
747 bds[1].bd_bucket == bd->bd_bucket);
748}
749
750#else
751
752static inline void
753cfs_hash_key_validate(struct cfs_hash *hs, const void *key,
754 struct hlist_node *hnode) {}
755
756static inline void
757cfs_hash_bucket_validate(struct cfs_hash *hs, struct cfs_hash_bd *bd,
758 struct hlist_node *hnode) {}
759
760#endif
761
762#define CFS_HASH_THETA_BITS 10
763#define CFS_HASH_MIN_THETA (1U << (CFS_HASH_THETA_BITS - 1))
764#define CFS_HASH_MAX_THETA (1U << (CFS_HASH_THETA_BITS + 1))
765
766
767static inline int __cfs_hash_theta_int(int theta)
768{
769 return (theta >> CFS_HASH_THETA_BITS);
770}
771
772
773static inline int __cfs_hash_theta_frac(int theta)
774{
775 return ((theta * 1000) >> CFS_HASH_THETA_BITS) -
776 (__cfs_hash_theta_int(theta) * 1000);
777}
778
779static inline int __cfs_hash_theta(struct cfs_hash *hs)
780{
781 return (atomic_read(&hs->hs_count) <<
782 CFS_HASH_THETA_BITS) >> hs->hs_cur_bits;
783}
784
785static inline void __cfs_hash_set_theta(struct cfs_hash *hs, int min, int max)
786{
787 LASSERT(min < max);
788 hs->hs_min_theta = (__u16)min;
789 hs->hs_max_theta = (__u16)max;
790}
791
792
793struct seq_file;
794int cfs_hash_debug_header(struct seq_file *m);
795int cfs_hash_debug_str(struct cfs_hash *hs, struct seq_file *m);
796
797
798
799
800static inline unsigned
801cfs_hash_djb2_hash(const void *key, size_t size, unsigned mask)
802{
803 unsigned i, hash = 5381;
804
805 LASSERT(key != NULL);
806
807 for (i = 0; i < size; i++)
808 hash = hash * 33 + ((char *)key)[i];
809
810 return (hash & mask);
811}
812
813
814
815
816static inline unsigned
817cfs_hash_u32_hash(const __u32 key, unsigned mask)
818{
819 return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
820}
821
822
823
824
825static inline unsigned
826cfs_hash_u64_hash(const __u64 key, unsigned mask)
827{
828 return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
829}
830
831
832#define cfs_hash_for_each_bd(bds, n, i) \
833 for (i = 0; i < n && (bds)[i].bd_bucket != NULL; i++)
834
835
836#define cfs_hash_for_each_bucket(hs, bd, pos) \
837 for (pos = 0; \
838 pos < CFS_HASH_NBKT(hs) && \
839 ((bd)->bd_bucket = (hs)->hs_buckets[pos]) != NULL; pos++)
840
841
842#define cfs_hash_bd_for_each_hlist(hs, bd, hlist) \
843 for ((bd)->bd_offset = 0; \
844 (bd)->bd_offset < CFS_HASH_BKT_NHLIST(hs) && \
845 (hlist = cfs_hash_bd_hhead(hs, bd)) != NULL; \
846 (bd)->bd_offset++)
847
848
849#endif
850