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
457static inline unsigned
458cfs_hash_id(struct cfs_hash *hs, const void *key, unsigned mask)
459{
460 return hs->hs_ops->hs_hash(hs, key, mask);
461}
462
463static inline void *
464cfs_hash_key(struct cfs_hash *hs, struct hlist_node *hnode)
465{
466 return hs->hs_ops->hs_key(hnode);
467}
468
469static inline void
470cfs_hash_keycpy(struct cfs_hash *hs, struct hlist_node *hnode, void *key)
471{
472 if (hs->hs_ops->hs_keycpy)
473 hs->hs_ops->hs_keycpy(hnode, key);
474}
475
476
477
478
479static inline int
480cfs_hash_keycmp(struct cfs_hash *hs, const void *key, struct hlist_node *hnode)
481{
482 return hs->hs_ops->hs_keycmp(key, hnode);
483}
484
485static inline void *
486cfs_hash_object(struct cfs_hash *hs, struct hlist_node *hnode)
487{
488 return hs->hs_ops->hs_object(hnode);
489}
490
491static inline void
492cfs_hash_get(struct cfs_hash *hs, struct hlist_node *hnode)
493{
494 return hs->hs_ops->hs_get(hs, hnode);
495}
496
497static inline void
498cfs_hash_put_locked(struct cfs_hash *hs, struct hlist_node *hnode)
499{
500 return hs->hs_ops->hs_put_locked(hs, hnode);
501}
502
503static inline void
504cfs_hash_put(struct cfs_hash *hs, struct hlist_node *hnode)
505{
506 return hs->hs_ops->hs_put(hs, hnode);
507}
508
509static inline void
510cfs_hash_exit(struct cfs_hash *hs, struct hlist_node *hnode)
511{
512 if (hs->hs_ops->hs_exit)
513 hs->hs_ops->hs_exit(hs, hnode);
514}
515
516static inline void cfs_hash_lock(struct cfs_hash *hs, int excl)
517{
518 hs->hs_lops->hs_lock(&hs->hs_lock, excl);
519}
520
521static inline void cfs_hash_unlock(struct cfs_hash *hs, int excl)
522{
523 hs->hs_lops->hs_unlock(&hs->hs_lock, excl);
524}
525
526static inline int cfs_hash_dec_and_lock(struct cfs_hash *hs,
527 atomic_t *condition)
528{
529 LASSERT(cfs_hash_with_no_bktlock(hs));
530 return atomic_dec_and_lock(condition, &hs->hs_lock.spin);
531}
532
533static inline void cfs_hash_bd_lock(struct cfs_hash *hs,
534 struct cfs_hash_bd *bd, int excl)
535{
536 hs->hs_lops->hs_bkt_lock(&bd->bd_bucket->hsb_lock, excl);
537}
538
539static inline void cfs_hash_bd_unlock(struct cfs_hash *hs,
540 struct cfs_hash_bd *bd, int excl)
541{
542 hs->hs_lops->hs_bkt_unlock(&bd->bd_bucket->hsb_lock, excl);
543}
544
545
546
547
548
549void cfs_hash_bd_get(struct cfs_hash *hs, const void *key, struct cfs_hash_bd *bd);
550
551static inline void cfs_hash_bd_get_and_lock(struct cfs_hash *hs, const void *key,
552 struct cfs_hash_bd *bd, int excl)
553{
554 cfs_hash_bd_get(hs, key, bd);
555 cfs_hash_bd_lock(hs, bd, excl);
556}
557
558static inline unsigned cfs_hash_bd_index_get(struct cfs_hash *hs, struct cfs_hash_bd *bd)
559{
560 return bd->bd_offset | (bd->bd_bucket->hsb_index << hs->hs_bkt_bits);
561}
562
563static inline void cfs_hash_bd_index_set(struct cfs_hash *hs,
564 unsigned index, struct cfs_hash_bd *bd)
565{
566 bd->bd_bucket = hs->hs_buckets[index >> hs->hs_bkt_bits];
567 bd->bd_offset = index & (CFS_HASH_BKT_NHLIST(hs) - 1U);
568}
569
570static inline void *
571cfs_hash_bd_extra_get(struct cfs_hash *hs, struct cfs_hash_bd *bd)
572{
573 return (void *)bd->bd_bucket +
574 cfs_hash_bkt_size(hs) - hs->hs_extra_bytes;
575}
576
577static inline __u32
578cfs_hash_bd_version_get(struct cfs_hash_bd *bd)
579{
580
581 return bd->bd_bucket->hsb_version;
582}
583
584static inline __u32
585cfs_hash_bd_count_get(struct cfs_hash_bd *bd)
586{
587
588 return bd->bd_bucket->hsb_count;
589}
590
591static inline int
592cfs_hash_bd_depmax_get(struct cfs_hash_bd *bd)
593{
594 return bd->bd_bucket->hsb_depmax;
595}
596
597static inline int
598cfs_hash_bd_compare(struct cfs_hash_bd *bd1, struct cfs_hash_bd *bd2)
599{
600 if (bd1->bd_bucket->hsb_index != bd2->bd_bucket->hsb_index)
601 return bd1->bd_bucket->hsb_index - bd2->bd_bucket->hsb_index;
602
603 if (bd1->bd_offset != bd2->bd_offset)
604 return bd1->bd_offset - bd2->bd_offset;
605
606 return 0;
607}
608
609void cfs_hash_bd_add_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd,
610 struct hlist_node *hnode);
611void cfs_hash_bd_del_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd,
612 struct hlist_node *hnode);
613void cfs_hash_bd_move_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd_old,
614 struct cfs_hash_bd *bd_new, struct hlist_node *hnode);
615
616static inline int cfs_hash_bd_dec_and_lock(struct cfs_hash *hs, struct cfs_hash_bd *bd,
617 atomic_t *condition)
618{
619 LASSERT(cfs_hash_with_spin_bktlock(hs));
620 return atomic_dec_and_lock(condition,
621 &bd->bd_bucket->hsb_lock.spin);
622}
623
624static inline struct hlist_head *cfs_hash_bd_hhead(struct cfs_hash *hs,
625 struct cfs_hash_bd *bd)
626{
627 return hs->hs_hops->hop_hhead(hs, bd);
628}
629
630struct hlist_node *cfs_hash_bd_lookup_locked(struct cfs_hash *hs,
631 struct cfs_hash_bd *bd, const void *key);
632struct hlist_node *cfs_hash_bd_peek_locked(struct cfs_hash *hs,
633 struct cfs_hash_bd *bd, const void *key);
634struct hlist_node *cfs_hash_bd_findadd_locked(struct cfs_hash *hs,
635 struct cfs_hash_bd *bd, const void *key,
636 struct hlist_node *hnode,
637 int insist_add);
638struct hlist_node *cfs_hash_bd_finddel_locked(struct cfs_hash *hs,
639 struct cfs_hash_bd *bd, const void *key,
640 struct hlist_node *hnode);
641
642
643
644
645
646void cfs_hash_dual_bd_get(struct cfs_hash *hs, const void *key, struct cfs_hash_bd *bds);
647void cfs_hash_dual_bd_lock(struct cfs_hash *hs, struct cfs_hash_bd *bds, int excl);
648void cfs_hash_dual_bd_unlock(struct cfs_hash *hs, struct cfs_hash_bd *bds, int excl);
649
650static inline void cfs_hash_dual_bd_get_and_lock(struct cfs_hash *hs, const void *key,
651 struct cfs_hash_bd *bds, int excl)
652{
653 cfs_hash_dual_bd_get(hs, key, bds);
654 cfs_hash_dual_bd_lock(hs, bds, excl);
655}
656
657struct hlist_node *cfs_hash_dual_bd_lookup_locked(struct cfs_hash *hs,
658 struct cfs_hash_bd *bds,
659 const void *key);
660struct hlist_node *cfs_hash_dual_bd_findadd_locked(struct cfs_hash *hs,
661 struct cfs_hash_bd *bds,
662 const void *key,
663 struct hlist_node *hnode,
664 int insist_add);
665struct hlist_node *cfs_hash_dual_bd_finddel_locked(struct cfs_hash *hs,
666 struct cfs_hash_bd *bds,
667 const void *key,
668 struct hlist_node *hnode);
669
670
671struct cfs_hash *cfs_hash_create(char *name, unsigned cur_bits, unsigned max_bits,
672 unsigned bkt_bits, unsigned extra_bytes,
673 unsigned min_theta, unsigned max_theta,
674 cfs_hash_ops_t *ops, unsigned flags);
675
676struct cfs_hash *cfs_hash_getref(struct cfs_hash *hs);
677void cfs_hash_putref(struct cfs_hash *hs);
678
679
680void cfs_hash_add(struct cfs_hash *hs, const void *key,
681 struct hlist_node *hnode);
682int cfs_hash_add_unique(struct cfs_hash *hs, const void *key,
683 struct hlist_node *hnode);
684void *cfs_hash_findadd_unique(struct cfs_hash *hs, const void *key,
685 struct hlist_node *hnode);
686
687
688void *cfs_hash_del(struct cfs_hash *hs, const void *key, struct hlist_node *hnode);
689void *cfs_hash_del_key(struct cfs_hash *hs, const void *key);
690
691
692#define CFS_HASH_LOOP_HOG 1024
693
694typedef int (*cfs_hash_for_each_cb_t)(struct cfs_hash *hs, struct cfs_hash_bd *bd,
695 struct hlist_node *node, void *data);
696void *cfs_hash_lookup(struct cfs_hash *hs, const void *key);
697void cfs_hash_for_each(struct cfs_hash *hs, cfs_hash_for_each_cb_t, void *data);
698void cfs_hash_for_each_safe(struct cfs_hash *hs, cfs_hash_for_each_cb_t, void *data);
699int cfs_hash_for_each_nolock(struct cfs_hash *hs,
700 cfs_hash_for_each_cb_t, void *data);
701int cfs_hash_for_each_empty(struct cfs_hash *hs,
702 cfs_hash_for_each_cb_t, void *data);
703void cfs_hash_for_each_key(struct cfs_hash *hs, const void *key,
704 cfs_hash_for_each_cb_t, void *data);
705typedef int (*cfs_hash_cond_opt_cb_t)(void *obj, void *data);
706void cfs_hash_cond_del(struct cfs_hash *hs, cfs_hash_cond_opt_cb_t, void *data);
707
708void cfs_hash_hlist_for_each(struct cfs_hash *hs, unsigned hindex,
709 cfs_hash_for_each_cb_t, void *data);
710int cfs_hash_is_empty(struct cfs_hash *hs);
711__u64 cfs_hash_size_get(struct cfs_hash *hs);
712
713
714
715
716
717void cfs_hash_rehash_cancel_locked(struct cfs_hash *hs);
718void cfs_hash_rehash_cancel(struct cfs_hash *hs);
719int cfs_hash_rehash(struct cfs_hash *hs, int do_rehash);
720void cfs_hash_rehash_key(struct cfs_hash *hs, const void *old_key,
721 void *new_key, struct hlist_node *hnode);
722
723#if CFS_HASH_DEBUG_LEVEL > CFS_HASH_DEBUG_1
724
725static inline void
726cfs_hash_key_validate(struct cfs_hash *hs, const void *key,
727 struct hlist_node *hnode)
728{
729 LASSERT(cfs_hash_keycmp(hs, key, hnode));
730}
731
732
733static inline void
734cfs_hash_bucket_validate(struct cfs_hash *hs, struct cfs_hash_bd *bd,
735 struct hlist_node *hnode)
736{
737 struct cfs_hash_bd bds[2];
738
739 cfs_hash_dual_bd_get(hs, cfs_hash_key(hs, hnode), bds);
740 LASSERT(bds[0].bd_bucket == bd->bd_bucket ||
741 bds[1].bd_bucket == bd->bd_bucket);
742}
743
744#else
745
746static inline void
747cfs_hash_key_validate(struct cfs_hash *hs, const void *key,
748 struct hlist_node *hnode) {}
749
750static inline void
751cfs_hash_bucket_validate(struct cfs_hash *hs, struct cfs_hash_bd *bd,
752 struct hlist_node *hnode) {}
753
754#endif
755
756#define CFS_HASH_THETA_BITS 10
757#define CFS_HASH_MIN_THETA (1U << (CFS_HASH_THETA_BITS - 1))
758#define CFS_HASH_MAX_THETA (1U << (CFS_HASH_THETA_BITS + 1))
759
760
761static inline int __cfs_hash_theta_int(int theta)
762{
763 return (theta >> CFS_HASH_THETA_BITS);
764}
765
766
767static inline int __cfs_hash_theta_frac(int theta)
768{
769 return ((theta * 1000) >> CFS_HASH_THETA_BITS) -
770 (__cfs_hash_theta_int(theta) * 1000);
771}
772
773static inline int __cfs_hash_theta(struct cfs_hash *hs)
774{
775 return (atomic_read(&hs->hs_count) <<
776 CFS_HASH_THETA_BITS) >> hs->hs_cur_bits;
777}
778
779static inline void __cfs_hash_set_theta(struct cfs_hash *hs, int min, int max)
780{
781 LASSERT(min < max);
782 hs->hs_min_theta = (__u16)min;
783 hs->hs_max_theta = (__u16)max;
784}
785
786
787struct seq_file;
788void cfs_hash_debug_header(struct seq_file *m);
789void cfs_hash_debug_str(struct cfs_hash *hs, struct seq_file *m);
790
791
792
793
794static inline unsigned
795cfs_hash_djb2_hash(const void *key, size_t size, unsigned mask)
796{
797 unsigned i, hash = 5381;
798
799 LASSERT(key != NULL);
800
801 for (i = 0; i < size; i++)
802 hash = hash * 33 + ((char *)key)[i];
803
804 return (hash & mask);
805}
806
807
808
809
810static inline unsigned
811cfs_hash_u32_hash(const __u32 key, unsigned mask)
812{
813 return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
814}
815
816
817
818
819static inline unsigned
820cfs_hash_u64_hash(const __u64 key, unsigned mask)
821{
822 return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
823}
824
825
826#define cfs_hash_for_each_bd(bds, n, i) \
827 for (i = 0; i < n && (bds)[i].bd_bucket != NULL; i++)
828
829
830#define cfs_hash_for_each_bucket(hs, bd, pos) \
831 for (pos = 0; \
832 pos < CFS_HASH_NBKT(hs) && \
833 ((bd)->bd_bucket = (hs)->hs_buckets[pos]) != NULL; pos++)
834
835
836#define cfs_hash_bd_for_each_hlist(hs, bd, hlist) \
837 for ((bd)->bd_offset = 0; \
838 (bd)->bd_offset < CFS_HASH_BKT_NHLIST(hs) && \
839 (hlist = cfs_hash_bd_hhead(hs, bd)) != NULL; \
840 (bd)->bd_offset++)
841
842
843#endif
844