X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=libcfs%2Flibcfs%2Fhash.c;h=61fffb3c36637827adc42f34dd80960e48992610;hb=d10200a80770f0029d1d665af954187b9ad883df;hp=504ed557cccf94c2726e2159923c6b0b38855536;hpb=502c141440b4e6a75a1162d25ba98315abe7ca4e;p=fs%2Flustre-release.git diff --git a/libcfs/libcfs/hash.c b/libcfs/libcfs/hash.c index 504ed55..61fffb3 100644 --- a/libcfs/libcfs/hash.c +++ b/libcfs/libcfs/hash.c @@ -15,11 +15,7 @@ * * You should have received a copy of the GNU General Public License * version 2 along with this program; If not, see - * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf - * - * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, - * CA 95054 USA or visit www.sun.com if you need additional information or - * have any questions. + * http://www.gnu.org/licenses/gpl-2.0.html * * GPL HEADER END */ @@ -27,7 +23,7 @@ * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved. * Use is subject to license terms. * - * Copyright (c) 2011, 2014, Intel Corporation. + * Copyright (c) 2011, 2016, Intel Corporation. */ /* * This file is part of Lustre, http://www.lustre.org/ @@ -108,6 +104,7 @@ */ #include +#include #include #if CFS_HASH_DEBUG_LEVEL >= CFS_HASH_DEBUG_1 @@ -681,25 +678,6 @@ cfs_hash_bd_peek_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd, } EXPORT_SYMBOL(cfs_hash_bd_peek_locked); -struct hlist_node * -cfs_hash_bd_findadd_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd, - const void *key, struct hlist_node *hnode, - int noref) -{ - return cfs_hash_bd_lookup_intent(hs, bd, key, hnode, - CFS_HS_LOOKUP_IT_ADD | - (!noref * CFS_HS_LOOKUP_MASK_REF)); -} - -struct hlist_node * -cfs_hash_bd_finddel_locked(struct cfs_hash *hs, struct cfs_hash_bd *bd, - const void *key, struct hlist_node *hnode) -{ - /* hnode can be NULL, we find the first item with @key */ - return cfs_hash_bd_lookup_intent(hs, bd, key, hnode, - CFS_HS_LOOKUP_IT_FINDDEL); -} - static void cfs_hash_multi_bd_lock(struct cfs_hash *hs, struct cfs_hash_bd *bds, unsigned n, int excl) @@ -965,10 +943,10 @@ cfs_hash_buckets_realloc(struct cfs_hash *hs, struct cfs_hash_bucket **old_bkts, * @flags - CFS_HASH_REHASH enable synamic hash resizing * - CFS_HASH_SORT enable chained hash sort */ -static int cfs_hash_rehash_worker(cfs_workitem_t *wi); +static int cfs_hash_rehash_worker(struct cfs_workitem *wi); #if CFS_HASH_DEBUG_LEVEL >= CFS_HASH_DEBUG_1 -static int cfs_hash_dep_print(cfs_workitem_t *wi) +static int cfs_hash_dep_print(struct cfs_workitem *wi) { struct cfs_hash *hs = container_of(wi, struct cfs_hash, hs_dep_wi); int dep; @@ -1038,7 +1016,7 @@ cfs_hash_create(char *name, unsigned cur_bits, unsigned max_bits, LASSERT(ops->hs_object); LASSERT(ops->hs_keycmp); LASSERT(ops->hs_get != NULL); - LASSERT(ops->hs_put_locked != NULL); + LASSERT(ops->hs_put != NULL || ops->hs_put_locked != NULL); if ((flags & CFS_HASH_REHASH) != 0) flags |= CFS_HASH_COUNTER; /* must have counter */ @@ -1250,23 +1228,23 @@ cfs_hash_find_or_add(struct cfs_hash *hs, const void *key, struct cfs_hash_bd bds[2]; int bits = 0; - LASSERT(hlist_unhashed(hnode)); + LASSERTF(hlist_unhashed(hnode), "hnode = %p\n", hnode); - cfs_hash_lock(hs, 0); - cfs_hash_dual_bd_get_and_lock(hs, key, bds, 1); + cfs_hash_lock(hs, 0); + cfs_hash_dual_bd_get_and_lock(hs, key, bds, 1); - cfs_hash_key_validate(hs, key, hnode); - ehnode = cfs_hash_dual_bd_findadd_locked(hs, bds, key, - hnode, noref); - cfs_hash_dual_bd_unlock(hs, bds, 1); + cfs_hash_key_validate(hs, key, hnode); + ehnode = cfs_hash_dual_bd_findadd_locked(hs, bds, key, + hnode, noref); + cfs_hash_dual_bd_unlock(hs, bds, 1); - if (ehnode == hnode) /* new item added */ - bits = cfs_hash_rehash_bits(hs); - cfs_hash_unlock(hs, 0); - if (bits > 0) - cfs_hash_rehash(hs, cfs_hash_rehash_inline(hs)); + if (ehnode == hnode) /* new item added */ + bits = cfs_hash_rehash_bits(hs); + cfs_hash_unlock(hs, 0); + if (bits > 0) + cfs_hash_rehash(hs, cfs_hash_rehash_inline(hs)); - return ehnode; + return ehnode; } /** @@ -1586,74 +1564,101 @@ EXPORT_SYMBOL(cfs_hash_size_get); */ static int cfs_hash_for_each_relax(struct cfs_hash *hs, cfs_hash_for_each_cb_t func, - void *data) + void *data, int start) { struct hlist_node *hnode; - struct hlist_node *tmp; + struct hlist_node *next = NULL; struct cfs_hash_bd bd; __u32 version; int count = 0; int stop_on_change; - int rc; - int i; + int has_put_locked; + int rc = 0; + int i, end = -1; ENTRY; stop_on_change = cfs_hash_with_rehash_key(hs) || - !cfs_hash_with_no_itemref(hs) || - hs->hs_ops->hs_put_locked == NULL; + !cfs_hash_with_no_itemref(hs); + has_put_locked = hs->hs_ops->hs_put_locked != NULL; cfs_hash_lock(hs, 0); +again: LASSERT(!cfs_hash_is_rehashing(hs)); cfs_hash_for_each_bucket(hs, &bd, i) { struct hlist_head *hhead; + if (i < start) + continue; + else if (end > 0 && i >= end) + break; + cfs_hash_bd_lock(hs, &bd, 0); version = cfs_hash_bd_version_get(&bd); cfs_hash_bd_for_each_hlist(hs, &bd, hhead) { - for (hnode = hhead->first; hnode != NULL;) { - cfs_hash_bucket_validate(hs, &bd, hnode); - cfs_hash_get(hs, hnode); + hnode = hhead->first; + if (hnode == NULL) + continue; + cfs_hash_get(hs, hnode); + for (; hnode != NULL; hnode = next) { + cfs_hash_bucket_validate(hs, &bd, hnode); + next = hnode->next; + if (next != NULL) + cfs_hash_get(hs, next); cfs_hash_bd_unlock(hs, &bd, 0); cfs_hash_unlock(hs, 0); rc = func(hs, &bd, hnode, data); - if (stop_on_change) + if (stop_on_change || !has_put_locked) cfs_hash_put(hs, hnode); + cond_resched(); count++; cfs_hash_lock(hs, 0); cfs_hash_bd_lock(hs, &bd, 0); - if (!stop_on_change) { - tmp = hnode->next; - cfs_hash_put_locked(hs, hnode); - hnode = tmp; - } else { /* bucket changed? */ - if (version != - cfs_hash_bd_version_get(&bd)) - break; - /* safe to continue because no change */ - hnode = hnode->next; - } + if (stop_on_change) { + if (version != + cfs_hash_bd_version_get(&bd)) + rc = -EINTR; + } else if (has_put_locked) { + cfs_hash_put_locked(hs, hnode); + } if (rc) /* callback wants to break iteration */ break; } - if (rc) /* callback wants to break iteration */ + if (next != NULL) { + if (has_put_locked) { + cfs_hash_put_locked(hs, next); + next = NULL; + } break; + } else if (rc != 0) { + break; + } } cfs_hash_bd_unlock(hs, &bd, 0); + if (next != NULL && !has_put_locked) { + cfs_hash_put(hs, next); + next = NULL; + } if (rc) /* callback wants to break iteration */ break; } - cfs_hash_unlock(hs, 0); - return count; + if (start > 0 && rc == 0) { + end = start; + start = 0; + goto again; + } + + cfs_hash_unlock(hs, 0); + return count; } int cfs_hash_for_each_nolock(struct cfs_hash *hs, - cfs_hash_for_each_cb_t func, void *data) + cfs_hash_for_each_cb_t func, void *data, int start) { ENTRY; @@ -1667,11 +1672,11 @@ cfs_hash_for_each_nolock(struct cfs_hash *hs, hs->hs_ops->hs_put_locked == NULL)) RETURN(-EOPNOTSUPP); - cfs_hash_for_each_enter(hs); - cfs_hash_for_each_relax(hs, func, data); - cfs_hash_for_each_exit(hs); + cfs_hash_for_each_enter(hs); + cfs_hash_for_each_relax(hs, func, data, start); + cfs_hash_for_each_exit(hs); - RETURN(0); + RETURN(0); } EXPORT_SYMBOL(cfs_hash_for_each_nolock); @@ -1701,13 +1706,13 @@ cfs_hash_for_each_empty(struct cfs_hash *hs, hs->hs_ops->hs_put_locked == NULL)) return -EOPNOTSUPP; - cfs_hash_for_each_enter(hs); - while (cfs_hash_for_each_relax(hs, func, data)) { - CDEBUG(D_INFO, "Try to empty hash: %s, loop: %u\n", - hs->hs_name, i++); - } - cfs_hash_for_each_exit(hs); - RETURN(0); + cfs_hash_for_each_enter(hs); + while (cfs_hash_for_each_relax(hs, func, data, 0)) { + CDEBUG(D_INFO, "Try to empty hash: %s, loop: %u\n", + hs->hs_name, i++); + } + cfs_hash_for_each_exit(hs); + RETURN(0); } EXPORT_SYMBOL(cfs_hash_for_each_empty); @@ -1883,7 +1888,7 @@ cfs_hash_rehash_bd(struct cfs_hash *hs, struct cfs_hash_bd *old) } static int -cfs_hash_rehash_worker(cfs_workitem_t *wi) +cfs_hash_rehash_worker(struct cfs_workitem *wi) { struct cfs_hash *hs = container_of(wi, struct cfs_hash, hs_rehash_wi); @@ -2031,13 +2036,10 @@ void cfs_hash_rehash_key(struct cfs_hash *hs, const void *old_key, } EXPORT_SYMBOL(cfs_hash_rehash_key); -int cfs_hash_debug_header(struct seq_file *m) +void cfs_hash_debug_header(struct seq_file *m) { - return seq_printf(m, "%-*s%6s%6s%6s%6s%6s%6s%6s%7s%8s%8s%8s%s\n", - CFS_HASH_BIGNAME_LEN, - "name", "cur", "min", "max", "theta", "t-min", "t-max", - "flags", "rehash", "count", "maxdep", "maxdepb", - " distribution"); + seq_printf(m, "%-*s cur min max theta t-min t-max flags rehash count maxdep maxdepb distribution\n", + CFS_HASH_BIGNAME_LEN, "name"); } EXPORT_SYMBOL(cfs_hash_debug_header); @@ -2065,31 +2067,28 @@ cfs_hash_full_nbkt(struct cfs_hash *hs) CFS_HASH_RH_NBKT(hs) : CFS_HASH_NBKT(hs); } -int cfs_hash_debug_str(struct cfs_hash *hs, struct seq_file *m) +void cfs_hash_debug_str(struct cfs_hash *hs, struct seq_file *m) { - int dist[8] = { 0, }; - int maxdep = -1; - int maxdepb = -1; - int total = 0; - int c = 0; - int theta; - int i; + int dist[8] = { 0, }; + int maxdep = -1; + int maxdepb = -1; + int total = 0; + int theta; + int i; cfs_hash_lock(hs, 0); theta = __cfs_hash_theta(hs); - c += seq_printf(m, "%-*s ", CFS_HASH_BIGNAME_LEN, hs->hs_name); - c += seq_printf(m, "%5d ", 1 << hs->hs_cur_bits); - c += seq_printf(m, "%5d ", 1 << hs->hs_min_bits); - c += seq_printf(m, "%5d ", 1 << hs->hs_max_bits); - c += seq_printf(m, "%d.%03d ", __cfs_hash_theta_int(theta), - __cfs_hash_theta_frac(theta)); - c += seq_printf(m, "%d.%03d ", __cfs_hash_theta_int(hs->hs_min_theta), - __cfs_hash_theta_frac(hs->hs_min_theta)); - c += seq_printf(m, "%d.%03d ", __cfs_hash_theta_int(hs->hs_max_theta), - __cfs_hash_theta_frac(hs->hs_max_theta)); - c += seq_printf(m, " 0x%02x ", hs->hs_flags); - c += seq_printf(m, "%6d ", hs->hs_rehash_count); + seq_printf(m, "%-*s %5d %5d %5d %d.%03d %d.%03d %d.%03d 0x%02x %6d ", + CFS_HASH_BIGNAME_LEN, hs->hs_name, + 1 << hs->hs_cur_bits, 1 << hs->hs_min_bits, + 1 << hs->hs_max_bits, + __cfs_hash_theta_int(theta), __cfs_hash_theta_frac(theta), + __cfs_hash_theta_int(hs->hs_min_theta), + __cfs_hash_theta_frac(hs->hs_min_theta), + __cfs_hash_theta_int(hs->hs_max_theta), + __cfs_hash_theta_frac(hs->hs_max_theta), + hs->hs_flags, hs->hs_rehash_count); /* * The distribution is a summary of the chained hash depth in @@ -2114,17 +2113,14 @@ int cfs_hash_debug_str(struct cfs_hash *hs, struct seq_file *m) maxdepb = ffz(~maxdep); } total += bd.bd_bucket->hsb_count; - dist[min(fls(bd.bd_bucket->hsb_count/max(theta,1)),7)]++; + dist[min(fls(bd.bd_bucket->hsb_count / max(theta, 1)), 7)]++; cfs_hash_bd_unlock(hs, &bd, 0); } - c += seq_printf(m, "%7d ", total); - c += seq_printf(m, "%7d ", maxdep); - c += seq_printf(m, "%7d ", maxdepb); + seq_printf(m, "%7d %7d %7d ", total, maxdep, maxdepb); for (i = 0; i < 8; i++) - c += seq_printf(m, "%d%c", dist[i], (i == 7) ? '\n' : '/'); + seq_printf(m, "%d%c", dist[i], (i == 7) ? '\n' : '/'); cfs_hash_unlock(hs, 0); - return c; } EXPORT_SYMBOL(cfs_hash_debug_str);