1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 only,
10 * as published by the Free Software Foundation.
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License version 2 for more details (a copy is included
16 * in the LICENSE file that accompanied this code).
18 * You should have received a copy of the GNU General Public License
19 * version 2 along with this program; If not, see
20 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
29 * Copyright 2008 Sun Microsystems, Inc. All rights reserved
30 * Use is subject to license terms.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
36 * lustre/obdclass/class_hash.c
38 * Implement a hash class for hash process in lustre system.
40 * Author: YuZhangyong <yzy@clusterfs.com>
42 * 2008-08-15: Brian Behlendorf <behlendorf1@llnl.gov>
43 * - Simplified API and improved documentation
44 * - Added per-hash feature flags:
45 * * LH_DEBUG additional validation
46 * * LH_REHASH dynamic rehashing
47 * - Added per-hash statistics
48 * - General performance enhancements
52 #include <liblustre.h>
56 #include <class_hash.h>
59 lh_read_lock(lustre_hash_t *lh)
61 if ((lh->lh_flags & LH_REHASH) != 0)
62 read_lock(&lh->lh_rwlock);
66 lh_read_unlock(lustre_hash_t *lh)
68 if ((lh->lh_flags & LH_REHASH) != 0)
69 read_unlock(&lh->lh_rwlock);
73 lh_write_lock(lustre_hash_t *lh)
75 if ((lh->lh_flags & LH_REHASH) != 0)
76 write_lock(&lh->lh_rwlock);
80 lh_write_unlock(lustre_hash_t *lh)
82 if ((lh->lh_flags & LH_REHASH) != 0)
83 write_unlock(&lh->lh_rwlock);
87 * Initialize new lustre hash, where:
88 * @name - Descriptive hash name
89 * @cur_bits - Initial hash table size, in bits
90 * @max_bits - Maximum allowed hash table resize, in bits
91 * @ops - Registered hash table operations
92 * @flags - LH_REHASH enable synamic hash resizing
93 * - LH_SORT enable chained hash sort
96 lustre_hash_init(char *name, unsigned int cur_bits, unsigned int max_bits,
97 lustre_hash_ops_t *ops, int flags)
103 LASSERT(name != NULL);
104 LASSERT(ops != NULL);
106 LASSERT(cur_bits > 0);
107 LASSERT(max_bits >= cur_bits);
108 LASSERT(max_bits < 31);
110 LIBCFS_ALLOC_PTR(lh);
114 strncpy(lh->lh_name, name, sizeof(lh->lh_name));
115 lh->lh_name[sizeof(lh->lh_name) - 1] = '\0';
116 atomic_set(&lh->lh_rehash_count, 0);
117 atomic_set(&lh->lh_count, 0);
118 rwlock_init(&lh->lh_rwlock);
119 lh->lh_cur_bits = cur_bits;
120 lh->lh_cur_mask = (1 << cur_bits) - 1;
121 lh->lh_min_bits = cur_bits;
122 lh->lh_max_bits = max_bits;
123 /* XXX: need to fixup lustre_hash_rehash_bits() before this can be
124 * anything other than 0.5 and 2.0 */
125 lh->lh_min_theta = 1 << (LH_THETA_BITS - 1);
126 lh->lh_max_theta = 1 << (LH_THETA_BITS + 1);
128 lh->lh_flags = flags;
129 if (cur_bits != max_bits && (lh->lh_flags & LH_REHASH) == 0)
130 CERROR("Rehash is disabled for %s, ignore max_bits %d\n",
134 __lustre_hash_set_theta(lh, 500, 2000);
136 LIBCFS_ALLOC(lh->lh_buckets, sizeof(*lh->lh_buckets) << lh->lh_cur_bits);
137 if (!lh->lh_buckets) {
142 for (i = 0; i <= lh->lh_cur_mask; i++) {
143 LIBCFS_ALLOC(lh->lh_buckets[i], sizeof(lustre_hash_bucket_t));
144 if (lh->lh_buckets[i] == NULL) {
145 lustre_hash_exit(lh);
149 INIT_HLIST_HEAD(&lh->lh_buckets[i]->lhb_head);
150 rwlock_init(&lh->lh_buckets[i]->lhb_rwlock);
151 atomic_set(&lh->lh_buckets[i]->lhb_count, 0);
156 EXPORT_SYMBOL(lustre_hash_init);
159 * Cleanup lustre hash @lh.
162 lustre_hash_exit(lustre_hash_t *lh)
164 lustre_hash_bucket_t *lhb;
165 struct hlist_node *hnode;
166 struct hlist_node *pos;
174 lh_for_each_bucket(lh, lhb, i) {
178 write_lock(&lhb->lhb_rwlock);
179 hlist_for_each_safe(hnode, pos, &(lhb->lhb_head)) {
180 __lustre_hash_bucket_validate(lh, lhb, hnode);
181 __lustre_hash_bucket_del(lh, lhb, hnode);
185 LASSERTF(hlist_empty(&(lhb->lhb_head)),
186 "hash bucket %d from %s is not empty\n", i, lh->lh_name);
187 LASSERTF(atomic_read(&lhb->lhb_count) == 0,
188 "hash bucket %d from %s has #entries > 0 (%d)\n", i,
189 lh->lh_name, atomic_read(&lhb->lhb_count));
190 write_unlock(&lhb->lhb_rwlock);
191 LIBCFS_FREE_PTR(lhb);
194 LASSERTF(atomic_read(&lh->lh_count) == 0,
195 "hash %s still has #entries > 0 (%d)\n", lh->lh_name,
196 atomic_read(&lh->lh_count));
199 LIBCFS_FREE(lh->lh_buckets, sizeof(*lh->lh_buckets) << lh->lh_cur_bits);
203 EXPORT_SYMBOL(lustre_hash_exit);
205 static inline unsigned int lustre_hash_rehash_bits(lustre_hash_t *lh)
207 if (!(lh->lh_flags & LH_REHASH))
210 /* XXX: need to handle case with max_theta != 2.0
211 * and the case with min_theta != 0.5 */
212 if ((lh->lh_cur_bits < lh->lh_max_bits) &&
213 (__lustre_hash_theta(lh) > lh->lh_max_theta))
214 return lh->lh_cur_bits + 1;
216 if ((lh->lh_cur_bits > lh->lh_min_bits) &&
217 (__lustre_hash_theta(lh) < lh->lh_min_theta))
218 return lh->lh_cur_bits - 1;
224 * Add item @hnode to lustre hash @lh using @key. The registered
225 * ops->lh_get function will be called when the item is added.
228 lustre_hash_add(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
230 lustre_hash_bucket_t *lhb;
235 __lustre_hash_key_validate(lh, key, hnode);
238 i = lh_hash(lh, key, lh->lh_cur_mask);
239 lhb = lh->lh_buckets[i];
240 LASSERT(i <= lh->lh_cur_mask);
241 LASSERT(hlist_unhashed(hnode));
243 write_lock(&lhb->lhb_rwlock);
244 __lustre_hash_bucket_add(lh, lhb, hnode);
245 write_unlock(&lhb->lhb_rwlock);
247 bits = lustre_hash_rehash_bits(lh);
250 lustre_hash_rehash(lh, bits);
254 EXPORT_SYMBOL(lustre_hash_add);
256 static struct hlist_node *
257 lustre_hash_findadd_unique_hnode(lustre_hash_t *lh, void *key,
258 struct hlist_node *hnode)
261 struct hlist_node *ehnode;
262 lustre_hash_bucket_t *lhb;
266 __lustre_hash_key_validate(lh, key, hnode);
269 i = lh_hash(lh, key, lh->lh_cur_mask);
270 lhb = lh->lh_buckets[i];
271 LASSERT(i <= lh->lh_cur_mask);
272 LASSERT(hlist_unhashed(hnode));
274 write_lock(&lhb->lhb_rwlock);
275 ehnode = __lustre_hash_bucket_lookup(lh, lhb, key);
279 __lustre_hash_bucket_add(lh, lhb, hnode);
281 bits = lustre_hash_rehash_bits(lh);
283 write_unlock(&lhb->lhb_rwlock);
286 lustre_hash_rehash(lh, bits);
292 * Add item @hnode to lustre hash @lh using @key. The registered
293 * ops->lh_get function will be called if the item was added.
294 * Returns 0 on success or -EALREADY on key collisions.
297 lustre_hash_add_unique(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
299 struct hlist_node *ehnode;
302 ehnode = lustre_hash_findadd_unique_hnode(lh, key, hnode);
303 if (ehnode != hnode) {
309 EXPORT_SYMBOL(lustre_hash_add_unique);
312 * Add item @hnode to lustre hash @lh using @key. If this @key
313 * already exists in the hash then ops->lh_get will be called on the
314 * conflicting entry and that entry will be returned to the caller.
315 * Otherwise ops->lh_get is called on the item which was added.
318 lustre_hash_findadd_unique(lustre_hash_t *lh, void *key,
319 struct hlist_node *hnode)
321 struct hlist_node *ehnode;
325 ehnode = lustre_hash_findadd_unique_hnode(lh, key, hnode);
326 obj = lh_get(lh, ehnode);
330 EXPORT_SYMBOL(lustre_hash_findadd_unique);
333 * Delete item @hnode from the lustre hash @lh using @key. The @key
334 * is required to ensure the correct hash bucket is locked since there
335 * is no direct linkage from the item to the bucket. The object
336 * removed from the hash will be returned and obs->lh_put is called
337 * on the removed object.
340 lustre_hash_del(lustre_hash_t *lh, void *key, struct hlist_node *hnode)
342 lustre_hash_bucket_t *lhb;
347 __lustre_hash_key_validate(lh, key, hnode);
350 i = lh_hash(lh, key, lh->lh_cur_mask);
351 lhb = lh->lh_buckets[i];
352 LASSERT(i <= lh->lh_cur_mask);
354 write_lock(&lhb->lhb_rwlock);
355 LASSERT(!hlist_unhashed(hnode));
356 obj = __lustre_hash_bucket_del(lh, lhb, hnode);
357 write_unlock(&lhb->lhb_rwlock);
362 EXPORT_SYMBOL(lustre_hash_del);
365 * Delete item from the lustre hash @lh when @func return true.
366 * The write lock being hold during loop for each bucket to avoid
367 * any object be reference.
370 lustre_hash_cond_del(lustre_hash_t *lh, lh_cond_opt_cb func, void *data)
372 lustre_hash_bucket_t *lhb;
373 struct hlist_node *hnode;
374 struct hlist_node *pos;
381 lh_for_each_bucket(lh, lhb, i) {
385 write_lock(&lhb->lhb_rwlock);
386 hlist_for_each_safe(hnode, pos, &(lhb->lhb_head)) {
387 __lustre_hash_bucket_validate(lh, lhb, hnode);
388 if (func(lh_get(lh, hnode), data))
389 __lustre_hash_bucket_del(lh, lhb, hnode);
390 (void)lh_put(lh, hnode);
392 write_unlock(&lhb->lhb_rwlock);
398 EXPORT_SYMBOL(lustre_hash_cond_del);
401 * Delete item given @key in lustre hash @lh. The first @key found in
402 * the hash will be removed, if the key exists multiple times in the hash
403 * @lh this function must be called once per key. The removed object
404 * will be returned and ops->lh_put is called on the removed object.
407 lustre_hash_del_key(lustre_hash_t *lh, void *key)
409 struct hlist_node *hnode;
410 lustre_hash_bucket_t *lhb;
416 i = lh_hash(lh, key, lh->lh_cur_mask);
417 lhb = lh->lh_buckets[i];
418 LASSERT(i <= lh->lh_cur_mask);
420 write_lock(&lhb->lhb_rwlock);
421 hnode = __lustre_hash_bucket_lookup(lh, lhb, key);
423 obj = __lustre_hash_bucket_del(lh, lhb, hnode);
425 write_unlock(&lhb->lhb_rwlock);
430 EXPORT_SYMBOL(lustre_hash_del_key);
433 * Lookup an item using @key in the lustre hash @lh and return it.
434 * If the @key is found in the hash lh->lh_get() is called and the
435 * matching objects is returned. It is the callers responsibility
436 * to call the counterpart ops->lh_put using the lh_put() macro
437 * when when finished with the object. If the @key was not found
438 * in the hash @lh NULL is returned.
441 lustre_hash_lookup(lustre_hash_t *lh, void *key)
443 struct hlist_node *hnode;
444 lustre_hash_bucket_t *lhb;
450 i = lh_hash(lh, key, lh->lh_cur_mask);
451 lhb = lh->lh_buckets[i];
452 LASSERT(i <= lh->lh_cur_mask);
454 read_lock(&lhb->lhb_rwlock);
455 hnode = __lustre_hash_bucket_lookup(lh, lhb, key);
457 obj = lh_get(lh, hnode);
459 read_unlock(&lhb->lhb_rwlock);
464 EXPORT_SYMBOL(lustre_hash_lookup);
467 * For each item in the lustre hash @lh call the passed callback @func
468 * and pass to it as an argument each hash item and the private @data.
469 * Before each callback ops->lh_get will be called, and after each
470 * callback ops->lh_put will be called. Finally, during the callback
471 * the bucket lock is held so the callback must never sleep.
474 lustre_hash_for_each(lustre_hash_t *lh, lh_for_each_cb func, void *data)
476 struct hlist_node *hnode;
477 lustre_hash_bucket_t *lhb;
483 lh_for_each_bucket(lh, lhb, i) {
484 read_lock(&lhb->lhb_rwlock);
485 hlist_for_each(hnode, &(lhb->lhb_head)) {
486 __lustre_hash_bucket_validate(lh, lhb, hnode);
487 obj = lh_get(lh, hnode);
489 (void)lh_put(lh, hnode);
491 read_unlock(&lhb->lhb_rwlock);
497 EXPORT_SYMBOL(lustre_hash_for_each);
500 * For each item in the lustre hash @lh call the passed callback @func
501 * and pass to it as an argument each hash item and the private @data.
502 * Before each callback ops->lh_get will be called, and after each
503 * callback ops->lh_put will be called. During the callback the
504 * bucket lock will not be held will allows for the current item
505 * to be removed from the hash during the callback. However, care
506 * should be taken to prevent other callers from operating on the
507 * hash concurrently or list corruption may occur.
510 lustre_hash_for_each_safe(lustre_hash_t *lh, lh_for_each_cb func, void *data)
512 struct hlist_node *hnode;
513 struct hlist_node *pos;
514 lustre_hash_bucket_t *lhb;
520 lh_for_each_bucket(lh, lhb, i) {
521 read_lock(&lhb->lhb_rwlock);
522 hlist_for_each_safe(hnode, pos, &(lhb->lhb_head)) {
523 __lustre_hash_bucket_validate(lh, lhb, hnode);
524 obj = lh_get(lh, hnode);
525 read_unlock(&lhb->lhb_rwlock);
527 read_lock(&lhb->lhb_rwlock);
528 (void)lh_put(lh, hnode);
530 read_unlock(&lhb->lhb_rwlock);
535 EXPORT_SYMBOL(lustre_hash_for_each_safe);
538 * For each hash bucket in the lustre hash @lh call the passed callback
539 * @func until all the hash buckets are empty. The passed callback @func
540 * or the previously registered callback lh->lh_put must remove the item
541 * from the hash. You may either use the lustre_hash_del() or hlist_del()
542 * functions. No rwlocks will be held during the callback @func it is
543 * safe to sleep if needed. This function will not terminate until the
544 * hash is empty. Note it is still possible to concurrently add new
545 * items in to the hash. It is the callers responsibility to ensure
546 * the required locking is in place to prevent concurrent insertions.
549 lustre_hash_for_each_empty(lustre_hash_t *lh, lh_for_each_cb func, void *data)
551 struct hlist_node *hnode;
552 lustre_hash_bucket_t *lhb;
553 lustre_hash_bucket_t **lhb_last = NULL;
560 /* If the hash table has changed since we last held lh_rwlock,
561 * we need to start traversing the list from the start. */
562 if (lh->lh_buckets != lhb_last) {
564 lhb_last = lh->lh_buckets;
566 lh_for_each_bucket_restart(lh, lhb, i) {
567 write_lock(&lhb->lhb_rwlock);
568 while (!hlist_empty(&lhb->lhb_head)) {
569 hnode = lhb->lhb_head.first;
570 __lustre_hash_bucket_validate(lh, lhb, hnode);
571 obj = lh_get(lh, hnode);
572 write_unlock(&lhb->lhb_rwlock);
575 (void)lh_put(lh, hnode);
579 write_unlock(&lhb->lhb_rwlock);
584 EXPORT_SYMBOL(lustre_hash_for_each_empty);
587 * For each item in the lustre hash @lh which matches the @key call
588 * the passed callback @func and pass to it as an argument each hash
589 * item and the private @data. Before each callback ops->lh_get will
590 * be called, and after each callback ops->lh_put will be called.
591 * Finally, during the callback the bucket lock is held so the
592 * callback must never sleep.
595 lustre_hash_for_each_key(lustre_hash_t *lh, void *key,
596 lh_for_each_cb func, void *data)
598 struct hlist_node *hnode;
599 lustre_hash_bucket_t *lhb;
604 i = lh_hash(lh, key, lh->lh_cur_mask);
605 lhb = lh->lh_buckets[i];
606 LASSERT(i <= lh->lh_cur_mask);
608 read_lock(&lhb->lhb_rwlock);
609 hlist_for_each(hnode, &(lhb->lhb_head)) {
610 __lustre_hash_bucket_validate(lh, lhb, hnode);
612 if (!lh_compare(lh, key, hnode))
615 func(lh_get(lh, hnode), data);
616 (void)lh_put(lh, hnode);
619 read_unlock(&lhb->lhb_rwlock);
624 EXPORT_SYMBOL(lustre_hash_for_each_key);
627 * Rehash the lustre hash @lh to the given @bits. This can be used
628 * to grow the hash size when excessive chaining is detected, or to
629 * shrink the hash when it is larger than needed. When the LH_REHASH
630 * flag is set in @lh the lustre hash may be dynamically rehashed
631 * during addition or removal if the hash's theta value exceeds
632 * either the lh->lh_min_theta or lh->max_theta values. By default
633 * these values are tuned to keep the chained hash depth small, and
634 * this approach assumes a reasonably uniform hashing function. The
635 * theta thresholds for @lh are tunable via lustre_hash_set_theta().
638 lustre_hash_rehash(lustre_hash_t *lh, int bits)
640 struct hlist_node *hnode;
641 struct hlist_node *pos;
642 lustre_hash_bucket_t **lh_buckets;
643 lustre_hash_bucket_t **rehash_buckets;
644 lustre_hash_bucket_t *lh_lhb;
645 lustre_hash_bucket_t *rehash_lhb;
650 int mask = (1 << bits) - 1;
655 LASSERT(!in_interrupt());
657 LASSERT((lh->lh_flags & LH_REHASH) != 0);
659 LIBCFS_ALLOC(rehash_buckets, sizeof(*rehash_buckets) << bits);
663 for (i = 0; i <= mask; i++) {
664 LIBCFS_ALLOC(rehash_buckets[i], sizeof(*rehash_buckets[i]));
665 if (rehash_buckets[i] == NULL)
666 GOTO(free, rc = -ENOMEM);
668 INIT_HLIST_HEAD(&rehash_buckets[i]->lhb_head);
669 rwlock_init(&rehash_buckets[i]->lhb_rwlock);
670 atomic_set(&rehash_buckets[i]->lhb_count, 0);
676 * Early return for multiple concurrent racing callers,
677 * ensure we only trigger the rehash if it is still needed.
679 theta = __lustre_hash_theta(lh);
680 if ((theta >= lh->lh_min_theta) && (theta <= lh->lh_max_theta)) {
682 GOTO(free, rc = -EALREADY);
685 lh_bits = lh->lh_cur_bits;
686 lh_buckets = lh->lh_buckets;
687 lh_mask = (1 << lh_bits) - 1;
689 lh->lh_cur_bits = bits;
690 lh->lh_cur_mask = (1 << bits) - 1;
691 lh->lh_buckets = rehash_buckets;
692 atomic_inc(&lh->lh_rehash_count);
694 for (i = 0; i <= lh_mask; i++) {
695 lh_lhb = lh_buckets[i];
697 write_lock(&lh_lhb->lhb_rwlock);
698 hlist_for_each_safe(hnode, pos, &(lh_lhb->lhb_head)) {
699 key = lh_key(lh, hnode);
703 * Validate hnode is in the correct bucket.
705 if (unlikely(lh->lh_flags & LH_DEBUG))
706 LASSERT(lh_hash(lh, key, lh_mask) == i);
709 * Delete from old hash bucket.
712 LASSERT(atomic_read(&lh_lhb->lhb_count) > 0);
713 atomic_dec(&lh_lhb->lhb_count);
716 * Add to rehash bucket, ops->lh_key must be defined.
718 rehash_lhb = rehash_buckets[lh_hash(lh, key, mask)];
719 hlist_add_head(hnode, &(rehash_lhb->lhb_head));
720 atomic_inc(&rehash_lhb->lhb_count);
723 LASSERT(hlist_empty(&(lh_lhb->lhb_head)));
724 LASSERT(atomic_read(&lh_lhb->lhb_count) == 0);
725 write_unlock(&lh_lhb->lhb_rwlock);
729 rehash_buckets = lh_buckets;
734 LIBCFS_FREE(rehash_buckets[i], sizeof(*rehash_buckets[i]));
735 LIBCFS_FREE(rehash_buckets, sizeof(*rehash_buckets) << bits);
739 EXPORT_SYMBOL(lustre_hash_rehash);
742 * Rehash the object referenced by @hnode in the lustre hash @lh. The
743 * @old_key must be provided to locate the objects previous location
744 * in the hash, and the @new_key will be used to reinsert the object.
745 * Use this function instead of a lustre_hash_add() + lustre_hash_del()
746 * combo when it is critical that there is no window in time where the
747 * object is missing from the hash. When an object is being rehashed
748 * the registered lh_get() and lh_put() functions will not be called.
750 void lustre_hash_rehash_key(lustre_hash_t *lh, void *old_key, void *new_key,
751 struct hlist_node *hnode)
753 lustre_hash_bucket_t *old_lhb;
754 lustre_hash_bucket_t *new_lhb;
759 __lustre_hash_key_validate(lh, new_key, hnode);
760 LASSERT(!hlist_unhashed(hnode));
764 i = lh_hash(lh, old_key, lh->lh_cur_mask);
765 old_lhb = lh->lh_buckets[i];
766 LASSERT(i <= lh->lh_cur_mask);
768 j = lh_hash(lh, new_key, lh->lh_cur_mask);
769 new_lhb = lh->lh_buckets[j];
770 LASSERT(j <= lh->lh_cur_mask);
772 if (i < j) { /* write_lock ordering */
773 write_lock(&old_lhb->lhb_rwlock);
774 write_lock(&new_lhb->lhb_rwlock);
776 write_lock(&new_lhb->lhb_rwlock);
777 write_lock(&old_lhb->lhb_rwlock);
778 } else { /* do nothing */
785 * Migrate item between hash buckets without calling
786 * the lh_get() and lh_put() callback functions.
789 LASSERT(atomic_read(&old_lhb->lhb_count) > 0);
790 atomic_dec(&old_lhb->lhb_count);
791 hlist_add_head(hnode, &(new_lhb->lhb_head));
792 atomic_inc(&new_lhb->lhb_count);
794 write_unlock(&new_lhb->lhb_rwlock);
795 write_unlock(&old_lhb->lhb_rwlock);
800 EXPORT_SYMBOL(lustre_hash_rehash_key);
802 int lustre_hash_debug_header(char *str, int size)
804 return snprintf(str, size,
805 "%-*s%6s%6s%6s%6s%6s%6s%6s%7s%6s%s\n", LUSTRE_MAX_HASH_NAME,
806 "name", "cur", "min", "max", "theta", "t-min", "t-max",
807 "flags", "rehash", "count", " distribution");
809 EXPORT_SYMBOL(lustre_hash_debug_header);
811 int lustre_hash_debug_str(lustre_hash_t *lh, char *str, int size)
813 lustre_hash_bucket_t *lhb;
817 int dist[8] = { 0, };
819 if (str == NULL || size == 0)
823 theta = __lustre_hash_theta(lh);
825 c += snprintf(str + c, size - c, "%-*s ",
826 LUSTRE_MAX_HASH_NAME, lh->lh_name);
827 c += snprintf(str + c, size - c, "%5d ", 1 << lh->lh_cur_bits);
828 c += snprintf(str + c, size - c, "%5d ", 1 << lh->lh_min_bits);
829 c += snprintf(str + c, size - c, "%5d ", 1 << lh->lh_max_bits);
830 c += snprintf(str + c, size - c, "%d.%03d ",
831 __lustre_hash_theta_int(theta),
832 __lustre_hash_theta_frac(theta));
833 c += snprintf(str + c, size - c, "%d.%03d ",
834 __lustre_hash_theta_int(lh->lh_min_theta),
835 __lustre_hash_theta_frac(lh->lh_min_theta));
836 c += snprintf(str + c, size - c, "%d.%03d ",
837 __lustre_hash_theta_int(lh->lh_max_theta),
838 __lustre_hash_theta_frac(lh->lh_max_theta));
839 c += snprintf(str + c, size - c, " 0x%02x ", lh->lh_flags);
840 c += snprintf(str + c, size - c, "%6d ",
841 atomic_read(&lh->lh_rehash_count));
842 c += snprintf(str + c, size - c, "%5d ",
843 atomic_read(&lh->lh_count));
846 * The distribution is a summary of the chained hash depth in
847 * each of the lustre hash buckets. Each buckets lhb_count is
848 * divided by the hash theta value and used to generate a
849 * histogram of the hash distribution. A uniform hash will
850 * result in all hash buckets being close to the average thus
851 * only the first few entries in the histogram will be non-zero.
852 * If you hash function results in a non-uniform hash the will
853 * be observable by outlier bucks in the distribution histogram.
855 * Uniform hash distribution: 128/128/0/0/0/0/0/0
856 * Non-Uniform hash distribution: 128/125/0/0/0/0/2/1
858 lh_for_each_bucket(lh, lhb, i)
859 dist[min(__fls(atomic_read(&lhb->lhb_count)/max(theta,1)),7)]++;
861 for (i = 0; i < 8; i++)
862 c += snprintf(str + c, size - c, "%d%c", dist[i],
863 (i == 7) ? '\n' : '/');
869 EXPORT_SYMBOL(lustre_hash_debug_str);