X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=libcfs%2Flibcfs%2Fhash.c;h=dda925c403d687323962142da3a95446bdb0925e;hb=6b9d24502b3cb7cf67df1f63d265436238cfb2de;hp=1ea6bf4f73c758aa4c4beb65acfd1dff94eb1edd;hpb=7d818af6449c9005b2dd7cb213d38d6ad61bf178;p=fs%2Flustre-release.git diff --git a/libcfs/libcfs/hash.c b/libcfs/libcfs/hash.c index 1ea6bf4..dda925c 100644 --- a/libcfs/libcfs/hash.c +++ b/libcfs/libcfs/hash.c @@ -1,6 +1,4 @@ -/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*- - * vim:expandtab:shiftwidth=8:tabstop=8: - * +/* * GPL HEADER START * * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. @@ -28,6 +26,8 @@ /* * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved. * Use is subject to license terms. + * + * Copyright (c) 2011, 2013, Intel Corporation. */ /* * This file is part of Lustre, http://www.lustre.org/ @@ -110,11 +110,13 @@ #include #if CFS_HASH_DEBUG_LEVEL >= CFS_HASH_DEBUG_1 -static unsigned int warn_on_depth = 0; +static unsigned int warn_on_depth = 8; CFS_MODULE_PARM(warn_on_depth, "i", uint, 0644, "warning when hash depth is high."); #endif +struct cfs_wi_sched *cfs_sched_rehash; + static inline void cfs_hash_nl_lock(cfs_hash_lock_t *lock, int exclusive) {} @@ -124,31 +126,31 @@ cfs_hash_nl_unlock(cfs_hash_lock_t *lock, int exclusive) {} static inline void cfs_hash_spin_lock(cfs_hash_lock_t *lock, int exclusive) { - cfs_spin_lock(&lock->spin); + spin_lock(&lock->spin); } static inline void cfs_hash_spin_unlock(cfs_hash_lock_t *lock, int exclusive) { - cfs_spin_unlock(&lock->spin); + spin_unlock(&lock->spin); } static inline void cfs_hash_rw_lock(cfs_hash_lock_t *lock, int exclusive) { - if (!exclusive) - cfs_read_lock(&lock->rw); - else - cfs_write_lock(&lock->rw); + if (!exclusive) + read_lock(&lock->rw); + else + write_lock(&lock->rw); } static inline void cfs_hash_rw_unlock(cfs_hash_lock_t *lock, int exclusive) { - if (!exclusive) - cfs_read_unlock(&lock->rw); - else - cfs_write_unlock(&lock->rw); + if (!exclusive) + read_unlock(&lock->rw); + else + write_unlock(&lock->rw); } /** No lock hash */ @@ -208,15 +210,15 @@ static cfs_hash_lock_ops_t cfs_hash_nr_bkt_rw_lops = static void cfs_hash_lock_setup(cfs_hash_t *hs) { - if (cfs_hash_with_no_lock(hs)) { - hs->hs_lops = &cfs_hash_nl_lops; + if (cfs_hash_with_no_lock(hs)) { + hs->hs_lops = &cfs_hash_nl_lops; - } else if (cfs_hash_with_no_bktlock(hs)) { - hs->hs_lops = &cfs_hash_nbl_lops; - cfs_spin_lock_init(&hs->hs_lock.spin); + } else if (cfs_hash_with_no_bktlock(hs)) { + hs->hs_lops = &cfs_hash_nbl_lops; + spin_lock_init(&hs->hs_lock.spin); - } else if (cfs_hash_with_rehash(hs)) { - cfs_rwlock_init(&hs->hs_lock.rw); + } else if (cfs_hash_with_rehash(hs)) { + rwlock_init(&hs->hs_lock.rw); if (cfs_hash_with_rw_bktlock(hs)) hs->hs_lops = &cfs_hash_bkt_rw_lops; @@ -239,37 +241,37 @@ cfs_hash_lock_setup(cfs_hash_t *hs) * new element is always added to head of hlist */ typedef struct { - cfs_hlist_head_t hh_head; /**< entries list */ + struct hlist_head hh_head; /**< entries list */ } cfs_hash_head_t; static int cfs_hash_hh_hhead_size(cfs_hash_t *hs) { - return sizeof(cfs_hash_head_t); + return sizeof(cfs_hash_head_t); } -static cfs_hlist_head_t * +static struct hlist_head * cfs_hash_hh_hhead(cfs_hash_t *hs, cfs_hash_bd_t *bd) { - cfs_hash_head_t *head = (cfs_hash_head_t *)&bd->bd_bucket->hsb_head[0]; + cfs_hash_head_t *head = (cfs_hash_head_t *)&bd->bd_bucket->hsb_head[0]; - return &head[bd->bd_offset].hh_head; + return &head[bd->bd_offset].hh_head; } static int cfs_hash_hh_hnode_add(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - cfs_hlist_add_head(hnode, cfs_hash_hh_hhead(hs, bd)); - return -1; /* unknown depth */ + hlist_add_head(hnode, cfs_hash_hh_hhead(hs, bd)); + return -1; /* unknown depth */ } static int cfs_hash_hh_hnode_del(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - cfs_hlist_del_init(hnode); - return -1; /* unknown depth */ + hlist_del_init(hnode); + return -1; /* unknown depth */ } /** @@ -277,43 +279,43 @@ cfs_hash_hh_hnode_del(cfs_hash_t *hs, cfs_hash_bd_t *bd, * new element is always added to head of hlist */ typedef struct { - cfs_hlist_head_t hd_head; /**< entries list */ - unsigned int hd_depth; /**< list length */ + struct hlist_head hd_head; /**< entries list */ + unsigned int hd_depth; /**< list length */ } cfs_hash_head_dep_t; static int cfs_hash_hd_hhead_size(cfs_hash_t *hs) { - return sizeof(cfs_hash_head_dep_t); + return sizeof(cfs_hash_head_dep_t); } -static cfs_hlist_head_t * +static struct hlist_head * cfs_hash_hd_hhead(cfs_hash_t *hs, cfs_hash_bd_t *bd) { - cfs_hash_head_dep_t *head; + cfs_hash_head_dep_t *head; - head = (cfs_hash_head_dep_t *)&bd->bd_bucket->hsb_head[0]; - return &head[bd->bd_offset].hd_head; + head = (cfs_hash_head_dep_t *)&bd->bd_bucket->hsb_head[0]; + return &head[bd->bd_offset].hd_head; } static int cfs_hash_hd_hnode_add(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - cfs_hash_head_dep_t *hh = container_of(cfs_hash_hd_hhead(hs, bd), - cfs_hash_head_dep_t, hd_head); - cfs_hlist_add_head(hnode, &hh->hd_head); - return ++hh->hd_depth; + cfs_hash_head_dep_t *hh = container_of(cfs_hash_hd_hhead(hs, bd), + cfs_hash_head_dep_t, hd_head); + hlist_add_head(hnode, &hh->hd_head); + return ++hh->hd_depth; } static int cfs_hash_hd_hnode_del(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - cfs_hash_head_dep_t *hh = container_of(cfs_hash_hd_hhead(hs, bd), - cfs_hash_head_dep_t, hd_head); - cfs_hlist_del_init(hnode); - return --hh->hd_depth; + cfs_hash_head_dep_t *hh = container_of(cfs_hash_hd_hhead(hs, bd), + cfs_hash_head_dep_t, hd_head); + hlist_del_init(hnode); + return --hh->hd_depth; } /** @@ -321,53 +323,53 @@ cfs_hash_hd_hnode_del(cfs_hash_t *hs, cfs_hash_bd_t *bd, * new element is always added to tail of hlist */ typedef struct { - cfs_hlist_head_t dh_head; /**< entries list */ - cfs_hlist_node_t *dh_tail; /**< the last entry */ + struct hlist_head dh_head; /**< entries list */ + struct hlist_node *dh_tail; /**< the last entry */ } cfs_hash_dhead_t; static int cfs_hash_dh_hhead_size(cfs_hash_t *hs) { - return sizeof(cfs_hash_dhead_t); + return sizeof(cfs_hash_dhead_t); } -static cfs_hlist_head_t * +static struct hlist_head * cfs_hash_dh_hhead(cfs_hash_t *hs, cfs_hash_bd_t *bd) { - cfs_hash_dhead_t *head; + cfs_hash_dhead_t *head; - head = (cfs_hash_dhead_t *)&bd->bd_bucket->hsb_head[0]; - return &head[bd->bd_offset].dh_head; + head = (cfs_hash_dhead_t *)&bd->bd_bucket->hsb_head[0]; + return &head[bd->bd_offset].dh_head; } static int cfs_hash_dh_hnode_add(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - cfs_hash_dhead_t *dh = container_of(cfs_hash_dh_hhead(hs, bd), - cfs_hash_dhead_t, dh_head); + cfs_hash_dhead_t *dh = container_of(cfs_hash_dh_hhead(hs, bd), + cfs_hash_dhead_t, dh_head); - if (dh->dh_tail != NULL) /* not empty */ - cfs_hlist_add_after(dh->dh_tail, hnode); - else /* empty list */ - cfs_hlist_add_head(hnode, &dh->dh_head); - dh->dh_tail = hnode; - return -1; /* unknown depth */ + if (dh->dh_tail != NULL) /* not empty */ + hlist_add_after(dh->dh_tail, hnode); + else /* empty list */ + hlist_add_head(hnode, &dh->dh_head); + dh->dh_tail = hnode; + return -1; /* unknown depth */ } static int cfs_hash_dh_hnode_del(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnd) + struct hlist_node *hnd) { - cfs_hash_dhead_t *dh = container_of(cfs_hash_dh_hhead(hs, bd), - cfs_hash_dhead_t, dh_head); + cfs_hash_dhead_t *dh = container_of(cfs_hash_dh_hhead(hs, bd), + cfs_hash_dhead_t, dh_head); - if (hnd->next == NULL) { /* it's the tail */ - dh->dh_tail = (hnd->pprev == &dh->dh_head.first) ? NULL : - container_of(hnd->pprev, cfs_hlist_node_t, next); - } - cfs_hlist_del_init(hnd); - return -1; /* unknown depth */ + if (hnd->next == NULL) { /* it's the tail */ + dh->dh_tail = (hnd->pprev == &dh->dh_head.first) ? NULL : + container_of(hnd->pprev, struct hlist_node, next); + } + hlist_del_init(hnd); + return -1; /* unknown depth */ } /** @@ -375,54 +377,54 @@ cfs_hash_dh_hnode_del(cfs_hash_t *hs, cfs_hash_bd_t *bd, * new element is always added to tail of hlist */ typedef struct { - cfs_hlist_head_t dd_head; /**< entries list */ - cfs_hlist_node_t *dd_tail; /**< the last entry */ - unsigned int dd_depth; /**< list length */ + struct hlist_head dd_head; /**< entries list */ + struct hlist_node *dd_tail; /**< the last entry */ + unsigned int dd_depth; /**< list length */ } cfs_hash_dhead_dep_t; static int cfs_hash_dd_hhead_size(cfs_hash_t *hs) { - return sizeof(cfs_hash_dhead_dep_t); + return sizeof(cfs_hash_dhead_dep_t); } -static cfs_hlist_head_t * +static struct hlist_head * cfs_hash_dd_hhead(cfs_hash_t *hs, cfs_hash_bd_t *bd) { - cfs_hash_dhead_dep_t *head; + cfs_hash_dhead_dep_t *head; - head = (cfs_hash_dhead_dep_t *)&bd->bd_bucket->hsb_head[0]; - return &head[bd->bd_offset].dd_head; + head = (cfs_hash_dhead_dep_t *)&bd->bd_bucket->hsb_head[0]; + return &head[bd->bd_offset].dd_head; } static int cfs_hash_dd_hnode_add(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - cfs_hash_dhead_dep_t *dh = container_of(cfs_hash_dd_hhead(hs, bd), - cfs_hash_dhead_dep_t, dd_head); + cfs_hash_dhead_dep_t *dh = container_of(cfs_hash_dd_hhead(hs, bd), + cfs_hash_dhead_dep_t, dd_head); - if (dh->dd_tail != NULL) /* not empty */ - cfs_hlist_add_after(dh->dd_tail, hnode); - else /* empty list */ - cfs_hlist_add_head(hnode, &dh->dd_head); - dh->dd_tail = hnode; - return ++dh->dd_depth; + if (dh->dd_tail != NULL) /* not empty */ + hlist_add_after(dh->dd_tail, hnode); + else /* empty list */ + hlist_add_head(hnode, &dh->dd_head); + dh->dd_tail = hnode; + return ++dh->dd_depth; } static int cfs_hash_dd_hnode_del(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnd) + struct hlist_node *hnd) { - cfs_hash_dhead_dep_t *dh = container_of(cfs_hash_dd_hhead(hs, bd), - cfs_hash_dhead_dep_t, dd_head); + cfs_hash_dhead_dep_t *dh = container_of(cfs_hash_dd_hhead(hs, bd), + cfs_hash_dhead_dep_t, dd_head); - if (hnd->next == NULL) { /* it's the tail */ - dh->dd_tail = (hnd->pprev == &dh->dd_head.first) ? NULL : - container_of(hnd->pprev, cfs_hlist_node_t, next); - } - cfs_hlist_del_init(hnd); - return --dh->dd_depth; + if (hnd->next == NULL) { /* it's the tail */ + dh->dd_tail = (hnd->pprev == &dh->dd_head.first) ? NULL : + container_of(hnd->pprev, struct hlist_node, next); + } + hlist_del_init(hnd); + return --dh->dd_depth; } static cfs_hash_hlist_ops_t cfs_hash_hh_hops = { @@ -490,7 +492,7 @@ cfs_hash_bd_get(cfs_hash_t *hs, const void *key, cfs_hash_bd_t *bd) hs->hs_rehash_bits, key, bd); } } -CFS_EXPORT_SYMBOL(cfs_hash_bd_get); +EXPORT_SYMBOL(cfs_hash_bd_get); static inline void cfs_hash_bd_dep_record(cfs_hash_t *hs, cfs_hash_bd_t *bd, int dep_cur) @@ -504,61 +506,61 @@ cfs_hash_bd_dep_record(cfs_hash_t *hs, cfs_hash_bd_t *bd, int dep_cur) max(warn_on_depth, hs->hs_dep_max) >= dep_cur)) return; - cfs_spin_lock(&hs->hs_dep_lock); - hs->hs_dep_max = dep_cur; - hs->hs_dep_bkt = bd->bd_bucket->hsb_index; - hs->hs_dep_off = bd->bd_offset; - hs->hs_dep_bits = hs->hs_cur_bits; - cfs_spin_unlock(&hs->hs_dep_lock); + spin_lock(&hs->hs_dep_lock); + hs->hs_dep_max = dep_cur; + hs->hs_dep_bkt = bd->bd_bucket->hsb_index; + hs->hs_dep_off = bd->bd_offset; + hs->hs_dep_bits = hs->hs_cur_bits; + spin_unlock(&hs->hs_dep_lock); - cfs_wi_schedule(&hs->hs_dep_wi); + cfs_wi_schedule(cfs_sched_rehash, &hs->hs_dep_wi); # endif } void cfs_hash_bd_add_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - int rc; + int rc; - rc = hs->hs_hops->hop_hnode_add(hs, bd, hnode); - cfs_hash_bd_dep_record(hs, bd, rc); - bd->bd_bucket->hsb_version++; - if (unlikely(bd->bd_bucket->hsb_version == 0)) - bd->bd_bucket->hsb_version++; - bd->bd_bucket->hsb_count++; + rc = hs->hs_hops->hop_hnode_add(hs, bd, hnode); + cfs_hash_bd_dep_record(hs, bd, rc); + bd->bd_bucket->hsb_version++; + if (unlikely(bd->bd_bucket->hsb_version == 0)) + bd->bd_bucket->hsb_version++; + bd->bd_bucket->hsb_count++; - if (cfs_hash_with_counter(hs)) - cfs_atomic_inc(&hs->hs_count); - if (!cfs_hash_with_no_itemref(hs)) - cfs_hash_get(hs, hnode); + if (cfs_hash_with_counter(hs)) + atomic_inc(&hs->hs_count); + if (!cfs_hash_with_no_itemref(hs)) + cfs_hash_get(hs, hnode); } -CFS_EXPORT_SYMBOL(cfs_hash_bd_add_locked); +EXPORT_SYMBOL(cfs_hash_bd_add_locked); void cfs_hash_bd_del_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - hs->hs_hops->hop_hnode_del(hs, bd, hnode); + hs->hs_hops->hop_hnode_del(hs, bd, hnode); - LASSERT(bd->bd_bucket->hsb_count > 0); - bd->bd_bucket->hsb_count--; - bd->bd_bucket->hsb_version++; - if (unlikely(bd->bd_bucket->hsb_version == 0)) - bd->bd_bucket->hsb_version++; + LASSERT(bd->bd_bucket->hsb_count > 0); + bd->bd_bucket->hsb_count--; + bd->bd_bucket->hsb_version++; + if (unlikely(bd->bd_bucket->hsb_version == 0)) + bd->bd_bucket->hsb_version++; - if (cfs_hash_with_counter(hs)) { - LASSERT(cfs_atomic_read(&hs->hs_count) > 0); - cfs_atomic_dec(&hs->hs_count); - } - if (!cfs_hash_with_no_itemref(hs)) - cfs_hash_put_locked(hs, hnode); + if (cfs_hash_with_counter(hs)) { + LASSERT(atomic_read(&hs->hs_count) > 0); + atomic_dec(&hs->hs_count); + } + if (!cfs_hash_with_no_itemref(hs)) + cfs_hash_put_locked(hs, hnode); } -CFS_EXPORT_SYMBOL(cfs_hash_bd_del_locked); +EXPORT_SYMBOL(cfs_hash_bd_del_locked); void cfs_hash_bd_move_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd_old, - cfs_hash_bd_t *bd_new, cfs_hlist_node_t *hnode) + cfs_hash_bd_t *bd_new, struct hlist_node *hnode) { cfs_hash_bucket_t *obkt = bd_old->bd_bucket; cfs_hash_bucket_t *nbkt = bd_new->bd_bucket; @@ -583,7 +585,7 @@ cfs_hash_bd_move_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd_old, if (unlikely(nbkt->hsb_version == 0)) nbkt->hsb_version++; } -CFS_EXPORT_SYMBOL(cfs_hash_bd_move_locked); +EXPORT_SYMBOL(cfs_hash_bd_move_locked); enum { /** always set, for sanity (avoid ZERO intent) */ @@ -613,23 +615,23 @@ typedef enum cfs_hash_lookup_intent { CFS_HS_LOOKUP_MASK_DEL) } cfs_hash_lookup_intent_t; -static cfs_hlist_node_t * +static struct hlist_node * cfs_hash_bd_lookup_intent(cfs_hash_t *hs, cfs_hash_bd_t *bd, - const void *key, cfs_hlist_node_t *hnode, - cfs_hash_lookup_intent_t intent) + const void *key, struct hlist_node *hnode, + cfs_hash_lookup_intent_t intent) { - cfs_hlist_head_t *hhead = cfs_hash_bd_hhead(hs, bd); - cfs_hlist_node_t *ehnode; - cfs_hlist_node_t *match; - int intent_add = (intent & CFS_HS_LOOKUP_MASK_ADD) != 0; + struct hlist_head *hhead = cfs_hash_bd_hhead(hs, bd); + struct hlist_node *ehnode; + struct hlist_node *match; + int intent_add = (intent & CFS_HS_LOOKUP_MASK_ADD) != 0; - /* with this function, we can avoid a lot of useless refcount ops, - * which are expensive atomic operations most time. */ - match = intent_add ? NULL : hnode; - cfs_hlist_for_each(ehnode, hhead) { - if (!cfs_hash_keycmp(hs, key, ehnode)) - continue; + /* with this function, we can avoid a lot of useless refcount ops, + * which are expensive atomic operations most time. */ + match = intent_add ? NULL : hnode; + hlist_for_each(ehnode, hhead) { + if (!cfs_hash_keycmp(hs, key, ehnode)) + continue; if (match != NULL && match != ehnode) /* can't match */ continue; @@ -654,34 +656,42 @@ cfs_hash_bd_lookup_intent(cfs_hash_t *hs, cfs_hash_bd_t *bd, return hnode; } -cfs_hlist_node_t * +struct hlist_node * cfs_hash_bd_lookup_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd, const void *key) { - return cfs_hash_bd_lookup_intent(hs, bd, key, NULL, - CFS_HS_LOOKUP_IT_FIND); + return cfs_hash_bd_lookup_intent(hs, bd, key, NULL, + CFS_HS_LOOKUP_IT_FIND); +} +EXPORT_SYMBOL(cfs_hash_bd_lookup_locked); + +struct hlist_node * +cfs_hash_bd_peek_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd, const void *key) +{ + return cfs_hash_bd_lookup_intent(hs, bd, key, NULL, + CFS_HS_LOOKUP_IT_PEEK); } -CFS_EXPORT_SYMBOL(cfs_hash_bd_lookup_locked); +EXPORT_SYMBOL(cfs_hash_bd_peek_locked); -cfs_hlist_node_t * +struct hlist_node * cfs_hash_bd_findadd_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd, - const void *key, cfs_hlist_node_t *hnode, + 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)); + return cfs_hash_bd_lookup_intent(hs, bd, key, hnode, + CFS_HS_LOOKUP_IT_ADD | + (!noref * CFS_HS_LOOKUP_MASK_REF)); } -CFS_EXPORT_SYMBOL(cfs_hash_bd_findadd_locked); +EXPORT_SYMBOL(cfs_hash_bd_findadd_locked); -cfs_hlist_node_t * +struct hlist_node * cfs_hash_bd_finddel_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd, - const void *key, cfs_hlist_node_t *hnode) + 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); + /* 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); } -CFS_EXPORT_SYMBOL(cfs_hash_bd_finddel_locked); +EXPORT_SYMBOL(cfs_hash_bd_finddel_locked); static void cfs_hash_multi_bd_lock(cfs_hash_t *hs, cfs_hash_bd_t *bds, @@ -721,30 +731,30 @@ cfs_hash_multi_bd_unlock(cfs_hash_t *hs, cfs_hash_bd_t *bds, } } -static cfs_hlist_node_t * +static struct hlist_node * cfs_hash_multi_bd_lookup_locked(cfs_hash_t *hs, cfs_hash_bd_t *bds, - unsigned n, const void *key) + unsigned n, const void *key) { - cfs_hlist_node_t *ehnode; - unsigned i; + struct hlist_node *ehnode; + unsigned i; - cfs_hash_for_each_bd(bds, n, i) { - ehnode = cfs_hash_bd_lookup_intent(hs, &bds[i], key, NULL, - CFS_HS_LOOKUP_IT_FIND); - if (ehnode != NULL) - return ehnode; - } - return NULL; + cfs_hash_for_each_bd(bds, n, i) { + ehnode = cfs_hash_bd_lookup_intent(hs, &bds[i], key, NULL, + CFS_HS_LOOKUP_IT_FIND); + if (ehnode != NULL) + return ehnode; + } + return NULL; } -static cfs_hlist_node_t * +static struct hlist_node * cfs_hash_multi_bd_findadd_locked(cfs_hash_t *hs, - cfs_hash_bd_t *bds, unsigned n, const void *key, - cfs_hlist_node_t *hnode, int noref) + cfs_hash_bd_t *bds, unsigned n, const void *key, + struct hlist_node *hnode, int noref) { - cfs_hlist_node_t *ehnode; - int intent; - unsigned i; + struct hlist_node *ehnode; + int intent; + unsigned i; LASSERT(hnode != NULL); intent = CFS_HS_LOOKUP_IT_PEEK | (!noref * CFS_HS_LOOKUP_MASK_REF); @@ -768,21 +778,21 @@ cfs_hash_multi_bd_findadd_locked(cfs_hash_t *hs, return hnode; } -static cfs_hlist_node_t * +static struct hlist_node * cfs_hash_multi_bd_finddel_locked(cfs_hash_t *hs, cfs_hash_bd_t *bds, - unsigned n, const void *key, - cfs_hlist_node_t *hnode) + unsigned n, const void *key, + struct hlist_node *hnode) { - cfs_hlist_node_t *ehnode; - unsigned i; + struct hlist_node *ehnode; + unsigned i; - cfs_hash_for_each_bd(bds, n, i) { - ehnode = cfs_hash_bd_lookup_intent(hs, &bds[i], key, hnode, - CFS_HS_LOOKUP_IT_FINDDEL); - if (ehnode != NULL) - return ehnode; - } - return NULL; + cfs_hash_for_each_bd(bds, n, i) { + ehnode = cfs_hash_bd_lookup_intent(hs, &bds[i], key, hnode, + CFS_HS_LOOKUP_IT_FINDDEL); + if (ehnode != NULL) + return ehnode; + } + return NULL; } static void @@ -830,47 +840,47 @@ cfs_hash_dual_bd_get(cfs_hash_t *hs, const void *key, cfs_hash_bd_t *bds) cfs_hash_bd_order(&bds[0], &bds[1]); } -CFS_EXPORT_SYMBOL(cfs_hash_dual_bd_get); +EXPORT_SYMBOL(cfs_hash_dual_bd_get); void cfs_hash_dual_bd_lock(cfs_hash_t *hs, cfs_hash_bd_t *bds, int excl) { cfs_hash_multi_bd_lock(hs, bds, 2, excl); } -CFS_EXPORT_SYMBOL(cfs_hash_dual_bd_lock); +EXPORT_SYMBOL(cfs_hash_dual_bd_lock); void cfs_hash_dual_bd_unlock(cfs_hash_t *hs, cfs_hash_bd_t *bds, int excl) { cfs_hash_multi_bd_unlock(hs, bds, 2, excl); } -CFS_EXPORT_SYMBOL(cfs_hash_dual_bd_unlock); +EXPORT_SYMBOL(cfs_hash_dual_bd_unlock); -cfs_hlist_node_t * +struct hlist_node * cfs_hash_dual_bd_lookup_locked(cfs_hash_t *hs, cfs_hash_bd_t *bds, const void *key) { return cfs_hash_multi_bd_lookup_locked(hs, bds, 2, key); } -CFS_EXPORT_SYMBOL(cfs_hash_dual_bd_lookup_locked); +EXPORT_SYMBOL(cfs_hash_dual_bd_lookup_locked); -cfs_hlist_node_t * +struct hlist_node * cfs_hash_dual_bd_findadd_locked(cfs_hash_t *hs, cfs_hash_bd_t *bds, - const void *key, cfs_hlist_node_t *hnode, - int noref) + const void *key, struct hlist_node *hnode, + int noref) { - return cfs_hash_multi_bd_findadd_locked(hs, bds, 2, key, - hnode, noref); + return cfs_hash_multi_bd_findadd_locked(hs, bds, 2, key, + hnode, noref); } -CFS_EXPORT_SYMBOL(cfs_hash_dual_bd_findadd_locked); +EXPORT_SYMBOL(cfs_hash_dual_bd_findadd_locked); -cfs_hlist_node_t * +struct hlist_node * cfs_hash_dual_bd_finddel_locked(cfs_hash_t *hs, cfs_hash_bd_t *bds, - const void *key, cfs_hlist_node_t *hnode) + const void *key, struct hlist_node *hnode) { - return cfs_hash_multi_bd_finddel_locked(hs, bds, 2, key, hnode); + return cfs_hash_multi_bd_finddel_locked(hs, bds, 2, key, hnode); } -CFS_EXPORT_SYMBOL(cfs_hash_dual_bd_finddel_locked); +EXPORT_SYMBOL(cfs_hash_dual_bd_finddel_locked); static void cfs_hash_buckets_free(cfs_hash_bucket_t **buckets, @@ -912,9 +922,9 @@ cfs_hash_buckets_realloc(cfs_hash_t *hs, cfs_hash_bucket_t **old_bkts, min(old_size, new_size) * sizeof(*old_bkts)); } - for (i = old_size; i < new_size; i++) { - cfs_hlist_head_t *hhead; - cfs_hash_bd_t bd; + for (i = old_size; i < new_size; i++) { + struct hlist_head *hhead; + cfs_hash_bd_t bd; LIBCFS_ALLOC(new_bkts[i], cfs_hash_bkt_size(hs)); if (new_bkts[i] == NULL) { @@ -923,25 +933,25 @@ cfs_hash_buckets_realloc(cfs_hash_t *hs, cfs_hash_bucket_t **old_bkts, return NULL; } - new_bkts[i]->hsb_index = i; - new_bkts[i]->hsb_version = 1; /* shouldn't be zero */ - new_bkts[i]->hsb_depmax = -1; /* unknown */ - bd.bd_bucket = new_bkts[i]; - cfs_hash_bd_for_each_hlist(hs, &bd, hhead) - CFS_INIT_HLIST_HEAD(hhead); + new_bkts[i]->hsb_index = i; + new_bkts[i]->hsb_version = 1; /* shouldn't be zero */ + new_bkts[i]->hsb_depmax = -1; /* unknown */ + bd.bd_bucket = new_bkts[i]; + cfs_hash_bd_for_each_hlist(hs, &bd, hhead) + INIT_HLIST_HEAD(hhead); if (cfs_hash_with_no_lock(hs) || cfs_hash_with_no_bktlock(hs)) continue; - if (cfs_hash_with_rw_bktlock(hs)) - cfs_rwlock_init(&new_bkts[i]->hsb_lock.rw); - else if (cfs_hash_with_spin_bktlock(hs)) - cfs_spin_lock_init(&new_bkts[i]->hsb_lock.spin); - else - LBUG(); /* invalid use-case */ - } - return new_bkts; + if (cfs_hash_with_rw_bktlock(hs)) + rwlock_init(&new_bkts[i]->hsb_lock.rw); + else if (cfs_hash_with_spin_bktlock(hs)) + spin_lock_init(&new_bkts[i]->hsb_lock.spin); + else + LBUG(); /* invalid use-case */ + } + return new_bkts; } /** @@ -958,46 +968,45 @@ static int cfs_hash_rehash_worker(cfs_workitem_t *wi); #if CFS_HASH_DEBUG_LEVEL >= CFS_HASH_DEBUG_1 static int cfs_hash_dep_print(cfs_workitem_t *wi) { - cfs_hash_t *hs = container_of(wi, cfs_hash_t, hs_dep_wi); - int dep; - int bkt; - int off; - int bits; - - cfs_spin_lock(&hs->hs_dep_lock); - dep = hs->hs_dep_max; - bkt = hs->hs_dep_bkt; - off = hs->hs_dep_off; - bits = hs->hs_dep_bits; - cfs_spin_unlock(&hs->hs_dep_lock); - - LCONSOLE_WARN("#### HASH %s (bits: %d): max depth %d at bucket %d/%d\n", - hs->hs_name, bits, dep, bkt, off); - cfs_spin_lock(&hs->hs_dep_lock); - hs->hs_dep_bits = 0; /* mark as workitem done */ - cfs_spin_unlock(&hs->hs_dep_lock); - return 0; + cfs_hash_t *hs = container_of(wi, cfs_hash_t, hs_dep_wi); + int dep; + int bkt; + int off; + int bits; + + spin_lock(&hs->hs_dep_lock); + dep = hs->hs_dep_max; + bkt = hs->hs_dep_bkt; + off = hs->hs_dep_off; + bits = hs->hs_dep_bits; + spin_unlock(&hs->hs_dep_lock); + + LCONSOLE_WARN("#### HASH %s (bits: %d): max depth %d at bucket %d/%d\n", + hs->hs_name, bits, dep, bkt, off); + spin_lock(&hs->hs_dep_lock); + hs->hs_dep_bits = 0; /* mark as workitem done */ + spin_unlock(&hs->hs_dep_lock); + return 0; } static void cfs_hash_depth_wi_init(cfs_hash_t *hs) { - cfs_spin_lock_init(&hs->hs_dep_lock); - cfs_wi_init(&hs->hs_dep_wi, hs, - cfs_hash_dep_print, CFS_WI_SCHED_ANY); + spin_lock_init(&hs->hs_dep_lock); + cfs_wi_init(&hs->hs_dep_wi, hs, cfs_hash_dep_print); } static void cfs_hash_depth_wi_cancel(cfs_hash_t *hs) { - if (cfs_wi_cancel(&hs->hs_dep_wi)) - return; + if (cfs_wi_deschedule(cfs_sched_rehash, &hs->hs_dep_wi)) + return; - cfs_spin_lock(&hs->hs_dep_lock); - while (hs->hs_dep_bits != 0) { - cfs_spin_unlock(&hs->hs_dep_lock); - cfs_cond_resched(); - cfs_spin_lock(&hs->hs_dep_lock); - } - cfs_spin_unlock(&hs->hs_dep_lock); + spin_lock(&hs->hs_dep_lock); + while (hs->hs_dep_bits != 0) { + spin_unlock(&hs->hs_dep_lock); + cond_resched(); + spin_lock(&hs->hs_dep_lock); + } + spin_unlock(&hs->hs_dep_lock); } #else /* CFS_HASH_DEBUG_LEVEL < CFS_HASH_DEBUG_1 */ @@ -1047,15 +1056,14 @@ cfs_hash_create(char *name, unsigned cur_bits, unsigned max_bits, if (hs == NULL) RETURN(NULL); - strncpy(hs->hs_name, name, len); - hs->hs_name[len - 1] = '\0'; - hs->hs_flags = flags; + strlcpy(hs->hs_name, name, len); + hs->hs_flags = flags; - cfs_atomic_set(&hs->hs_refcount, 1); - cfs_atomic_set(&hs->hs_count, 0); + atomic_set(&hs->hs_refcount, 1); + atomic_set(&hs->hs_count, 0); - cfs_hash_lock_setup(hs); - cfs_hash_hlist_setup(hs); + cfs_hash_lock_setup(hs); + cfs_hash_hlist_setup(hs); hs->hs_cur_bits = (__u8)cur_bits; hs->hs_min_bits = (__u8)cur_bits; @@ -1065,8 +1073,7 @@ cfs_hash_create(char *name, unsigned cur_bits, unsigned max_bits, hs->hs_ops = ops; hs->hs_extra_bytes = extra_bytes; hs->hs_rehash_bits = 0; - cfs_wi_init(&hs->hs_rehash_wi, hs, - cfs_hash_rehash_worker, CFS_WI_SCHED_ANY); + cfs_wi_init(&hs->hs_rehash_wi, hs, cfs_hash_rehash_worker); cfs_hash_depth_wi_init(hs); if (cfs_hash_with_rehash(hs)) @@ -1080,7 +1087,7 @@ cfs_hash_create(char *name, unsigned cur_bits, unsigned max_bits, LIBCFS_FREE(hs, offsetof(cfs_hash_t, hs_name[len])); RETURN(NULL); } -CFS_EXPORT_SYMBOL(cfs_hash_create); +EXPORT_SYMBOL(cfs_hash_create); /** * Cleanup libcfs hash @hs. @@ -1088,15 +1095,15 @@ CFS_EXPORT_SYMBOL(cfs_hash_create); static void cfs_hash_destroy(cfs_hash_t *hs) { - cfs_hlist_node_t *hnode; - cfs_hlist_node_t *pos; - cfs_hash_bd_t bd; - int i; - ENTRY; + struct hlist_node *hnode; + struct hlist_node *pos; + cfs_hash_bd_t bd; + int i; + ENTRY; - LASSERT(hs != NULL); - LASSERT(!cfs_hash_is_exiting(hs) && - !cfs_hash_is_iterating(hs)); + LASSERT(hs != NULL); + LASSERT(!cfs_hash_is_exiting(hs) && + !cfs_hash_is_iterating(hs)); /** * prohibit further rehashes, don't need any lock because @@ -1111,56 +1118,56 @@ cfs_hash_destroy(cfs_hash_t *hs) LASSERT(hs->hs_buckets != NULL && hs->hs_rehash_buckets == NULL); - cfs_hash_for_each_bucket(hs, &bd, i) { - cfs_hlist_head_t *hhead; + cfs_hash_for_each_bucket(hs, &bd, i) { + struct hlist_head *hhead; - LASSERT(bd.bd_bucket != NULL); - /* no need to take this lock, just for consistent code */ - cfs_hash_bd_lock(hs, &bd, 1); + LASSERT(bd.bd_bucket != NULL); + /* no need to take this lock, just for consistent code */ + cfs_hash_bd_lock(hs, &bd, 1); cfs_hash_bd_for_each_hlist(hs, &bd, hhead) { - cfs_hlist_for_each_safe(hnode, pos, hhead) { - LASSERTF(!cfs_hash_with_assert_empty(hs), - "hash %s bucket %u(%u) is not " - " empty: %u items left\n", - hs->hs_name, bd.bd_bucket->hsb_index, - bd.bd_offset, bd.bd_bucket->hsb_count); - /* can't assert key valicate, because we - * can interrupt rehash */ - cfs_hash_bd_del_locked(hs, &bd, hnode); - cfs_hash_exit(hs, hnode); - } - } - LASSERT(bd.bd_bucket->hsb_count == 0); - cfs_hash_bd_unlock(hs, &bd, 1); - cfs_cond_resched(); - } - - LASSERT(cfs_atomic_read(&hs->hs_count) == 0); - - cfs_hash_buckets_free(hs->hs_buckets, cfs_hash_bkt_size(hs), - 0, CFS_HASH_NBKT(hs)); - i = cfs_hash_with_bigname(hs) ? - CFS_HASH_BIGNAME_LEN : CFS_HASH_NAME_LEN; - LIBCFS_FREE(hs, offsetof(cfs_hash_t, hs_name[i])); - - EXIT; + hlist_for_each_safe(hnode, pos, hhead) { + LASSERTF(!cfs_hash_with_assert_empty(hs), + "hash %s bucket %u(%u) is not " + " empty: %u items left\n", + hs->hs_name, bd.bd_bucket->hsb_index, + bd.bd_offset, bd.bd_bucket->hsb_count); + /* can't assert key valicate, because we + * can interrupt rehash */ + cfs_hash_bd_del_locked(hs, &bd, hnode); + cfs_hash_exit(hs, hnode); + } + } + LASSERT(bd.bd_bucket->hsb_count == 0); + cfs_hash_bd_unlock(hs, &bd, 1); + cond_resched(); + } + + LASSERT(atomic_read(&hs->hs_count) == 0); + + cfs_hash_buckets_free(hs->hs_buckets, cfs_hash_bkt_size(hs), + 0, CFS_HASH_NBKT(hs)); + i = cfs_hash_with_bigname(hs) ? + CFS_HASH_BIGNAME_LEN : CFS_HASH_NAME_LEN; + LIBCFS_FREE(hs, offsetof(cfs_hash_t, hs_name[i])); + + EXIT; } cfs_hash_t *cfs_hash_getref(cfs_hash_t *hs) { - if (cfs_atomic_inc_not_zero(&hs->hs_refcount)) - return hs; - return NULL; + if (atomic_inc_not_zero(&hs->hs_refcount)) + return hs; + return NULL; } -CFS_EXPORT_SYMBOL(cfs_hash_getref); +EXPORT_SYMBOL(cfs_hash_getref); void cfs_hash_putref(cfs_hash_t *hs) { - if (hs && cfs_atomic_dec_and_test(&hs->hs_refcount)) - cfs_hash_destroy(hs); + if (atomic_dec_and_test(&hs->hs_refcount)) + cfs_hash_destroy(hs); } -CFS_EXPORT_SYMBOL(cfs_hash_putref); +EXPORT_SYMBOL(cfs_hash_putref); static inline int cfs_hash_rehash_bits(cfs_hash_t *hs) @@ -1202,8 +1209,8 @@ cfs_hash_rehash_bits(cfs_hash_t *hs) static inline int cfs_hash_rehash_inline(cfs_hash_t *hs) { - return !cfs_hash_with_nblk_change(hs) && - cfs_atomic_read(&hs->hs_count) < CFS_HASH_LOOP_HOG; + return !cfs_hash_with_nblk_change(hs) && + atomic_read(&hs->hs_count) < CFS_HASH_LOOP_HOG; } /** @@ -1211,12 +1218,12 @@ cfs_hash_rehash_inline(cfs_hash_t *hs) * ops->hs_get function will be called when the item is added. */ void -cfs_hash_add(cfs_hash_t *hs, const void *key, cfs_hlist_node_t *hnode) +cfs_hash_add(cfs_hash_t *hs, const void *key, struct hlist_node *hnode) { cfs_hash_bd_t bd; int bits; - LASSERT(cfs_hlist_unhashed(hnode)); + LASSERT(hlist_unhashed(hnode)); cfs_hash_lock(hs, 0); cfs_hash_bd_get_and_lock(hs, key, &bd, 1); @@ -1231,17 +1238,17 @@ cfs_hash_add(cfs_hash_t *hs, const void *key, cfs_hlist_node_t *hnode) if (bits > 0) cfs_hash_rehash(hs, cfs_hash_rehash_inline(hs)); } -CFS_EXPORT_SYMBOL(cfs_hash_add); +EXPORT_SYMBOL(cfs_hash_add); -static cfs_hlist_node_t * +static struct hlist_node * cfs_hash_find_or_add(cfs_hash_t *hs, const void *key, - cfs_hlist_node_t *hnode, int noref) + struct hlist_node *hnode, int noref) { - cfs_hlist_node_t *ehnode; - cfs_hash_bd_t bds[2]; - int bits = 0; + struct hlist_node *ehnode; + cfs_hash_bd_t bds[2]; + int bits = 0; - LASSERT(cfs_hlist_unhashed(hnode)); + LASSERT(hlist_unhashed(hnode)); cfs_hash_lock(hs, 0); cfs_hash_dual_bd_get_and_lock(hs, key, bds, 1); @@ -1266,12 +1273,12 @@ cfs_hash_find_or_add(cfs_hash_t *hs, const void *key, * Returns 0 on success or -EALREADY on key collisions. */ int -cfs_hash_add_unique(cfs_hash_t *hs, const void *key, cfs_hlist_node_t *hnode) +cfs_hash_add_unique(cfs_hash_t *hs, const void *key, struct hlist_node *hnode) { - return cfs_hash_find_or_add(hs, key, hnode, 1) != hnode ? - -EALREADY : 0; + return cfs_hash_find_or_add(hs, key, hnode, 1) != hnode ? + -EALREADY : 0; } -CFS_EXPORT_SYMBOL(cfs_hash_add_unique); +EXPORT_SYMBOL(cfs_hash_add_unique); /** * Add item @hnode to libcfs hash @hs using @key. If this @key @@ -1281,13 +1288,13 @@ CFS_EXPORT_SYMBOL(cfs_hash_add_unique); */ void * cfs_hash_findadd_unique(cfs_hash_t *hs, const void *key, - cfs_hlist_node_t *hnode) + struct hlist_node *hnode) { - hnode = cfs_hash_find_or_add(hs, key, hnode, 0); + hnode = cfs_hash_find_or_add(hs, key, hnode, 0); - return cfs_hash_object(hs, hnode); + return cfs_hash_object(hs, hnode); } -CFS_EXPORT_SYMBOL(cfs_hash_findadd_unique); +EXPORT_SYMBOL(cfs_hash_findadd_unique); /** * Delete item @hnode from the libcfs hash @hs using @key. The @key @@ -1297,7 +1304,7 @@ CFS_EXPORT_SYMBOL(cfs_hash_findadd_unique); * on the removed object. */ void * -cfs_hash_del(cfs_hash_t *hs, const void *key, cfs_hlist_node_t *hnode) +cfs_hash_del(cfs_hash_t *hs, const void *key, struct hlist_node *hnode) { void *obj = NULL; int bits = 0; @@ -1306,10 +1313,15 @@ cfs_hash_del(cfs_hash_t *hs, const void *key, cfs_hlist_node_t *hnode) cfs_hash_lock(hs, 0); cfs_hash_dual_bd_get_and_lock(hs, key, bds, 1); - if (bds[1].bd_bucket == NULL && hnode != NULL) - cfs_hash_bd_del_locked(hs, &bds[0], hnode); - else - hnode = cfs_hash_dual_bd_finddel_locked(hs, bds, key, hnode); + /* NB: do nothing if @hnode is not in hash table */ + if (hnode == NULL || !hlist_unhashed(hnode)) { + if (bds[1].bd_bucket == NULL && hnode != NULL) { + cfs_hash_bd_del_locked(hs, &bds[0], hnode); + } else { + hnode = cfs_hash_dual_bd_finddel_locked(hs, bds, + key, hnode); + } + } if (hnode != NULL) { obj = cfs_hash_object(hs, hnode); @@ -1323,7 +1335,7 @@ cfs_hash_del(cfs_hash_t *hs, const void *key, cfs_hlist_node_t *hnode) return obj; } -CFS_EXPORT_SYMBOL(cfs_hash_del); +EXPORT_SYMBOL(cfs_hash_del); /** * Delete item given @key in libcfs hash @hs. The first @key found in @@ -1336,7 +1348,7 @@ cfs_hash_del_key(cfs_hash_t *hs, const void *key) { return cfs_hash_del(hs, key, NULL); } -CFS_EXPORT_SYMBOL(cfs_hash_del_key); +EXPORT_SYMBOL(cfs_hash_del_key); /** * Lookup an item using @key in the libcfs hash @hs and return it. @@ -1350,7 +1362,7 @@ void * cfs_hash_lookup(cfs_hash_t *hs, const void *key) { void *obj = NULL; - cfs_hlist_node_t *hnode; + struct hlist_node *hnode; cfs_hash_bd_t bds[2]; cfs_hash_lock(hs, 0); @@ -1365,7 +1377,7 @@ cfs_hash_lookup(cfs_hash_t *hs, const void *key) return obj; } -CFS_EXPORT_SYMBOL(cfs_hash_lookup); +EXPORT_SYMBOL(cfs_hash_lookup); static void cfs_hash_for_each_enter(cfs_hash_t *hs) @@ -1396,22 +1408,22 @@ cfs_hash_for_each_enter(cfs_hash_t *hs) static void cfs_hash_for_each_exit(cfs_hash_t *hs) { - int remained; - int bits; + int remained; + int bits; - if (!cfs_hash_with_rehash(hs)) - return; - cfs_hash_lock(hs, 1); - remained = --hs->hs_iterators; - bits = cfs_hash_rehash_bits(hs); - cfs_hash_unlock(hs, 1); - /* NB: it's race on cfs_has_t::hs_iterating, see above */ - if (remained == 0) - hs->hs_iterating = 0; - if (bits > 0) { - cfs_hash_rehash(hs, cfs_atomic_read(&hs->hs_count) < - CFS_HASH_LOOP_HOG); - } + if (!cfs_hash_with_rehash(hs)) + return; + cfs_hash_lock(hs, 1); + remained = --hs->hs_iterators; + bits = cfs_hash_rehash_bits(hs); + cfs_hash_unlock(hs, 1); + /* NB: it's race on cfs_has_t::hs_iterating, see above */ + if (remained == 0) + hs->hs_iterating = 0; + if (bits > 0) { + cfs_hash_rehash(hs, atomic_read(&hs->hs_count) < + CFS_HASH_LOOP_HOG); + } } /** @@ -1426,56 +1438,56 @@ cfs_hash_for_each_exit(cfs_hash_t *hs) */ static __u64 cfs_hash_for_each_tight(cfs_hash_t *hs, cfs_hash_for_each_cb_t func, - void *data, int remove_safe) -{ - cfs_hlist_node_t *hnode; - cfs_hlist_node_t *pos; - cfs_hash_bd_t bd; - __u64 count = 0; - int excl = !!remove_safe; - int loop = 0; - int i; - ENTRY; - - cfs_hash_for_each_enter(hs); - - cfs_hash_lock(hs, 0); - LASSERT(!cfs_hash_is_rehashing(hs)); - - cfs_hash_for_each_bucket(hs, &bd, i) { - cfs_hlist_head_t *hhead; - - cfs_hash_bd_lock(hs, &bd, excl); - if (func == NULL) { /* only glimpse size */ - count += bd.bd_bucket->hsb_count; - cfs_hash_bd_unlock(hs, &bd, excl); - continue; - } - - cfs_hash_bd_for_each_hlist(hs, &bd, hhead) { - cfs_hlist_for_each_safe(hnode, pos, hhead) { - cfs_hash_bucket_validate(hs, &bd, hnode); - count++; - loop++; - if (func(hs, &bd, hnode, data)) { - cfs_hash_bd_unlock(hs, &bd, excl); - goto out; - } - } - } - cfs_hash_bd_unlock(hs, &bd, excl); - if (loop < CFS_HASH_LOOP_HOG) - continue; - loop = 0; - cfs_hash_unlock(hs, 0); - cfs_cond_resched(); - cfs_hash_lock(hs, 0); - } + void *data, int remove_safe) +{ + struct hlist_node *hnode; + struct hlist_node *pos; + cfs_hash_bd_t bd; + __u64 count = 0; + int excl = !!remove_safe; + int loop = 0; + int i; + ENTRY; + + cfs_hash_for_each_enter(hs); + + cfs_hash_lock(hs, 0); + LASSERT(!cfs_hash_is_rehashing(hs)); + + cfs_hash_for_each_bucket(hs, &bd, i) { + struct hlist_head *hhead; + + cfs_hash_bd_lock(hs, &bd, excl); + if (func == NULL) { /* only glimpse size */ + count += bd.bd_bucket->hsb_count; + cfs_hash_bd_unlock(hs, &bd, excl); + continue; + } + + cfs_hash_bd_for_each_hlist(hs, &bd, hhead) { + hlist_for_each_safe(hnode, pos, hhead) { + cfs_hash_bucket_validate(hs, &bd, hnode); + count++; + loop++; + if (func(hs, &bd, hnode, data)) { + cfs_hash_bd_unlock(hs, &bd, excl); + goto out; + } + } + } + cfs_hash_bd_unlock(hs, &bd, excl); + if (loop < CFS_HASH_LOOP_HOG) + continue; + loop = 0; + cfs_hash_unlock(hs, 0); + cond_resched(); + cfs_hash_lock(hs, 0); + } out: - cfs_hash_unlock(hs, 0); + cfs_hash_unlock(hs, 0); - cfs_hash_for_each_exit(hs); - RETURN(count); + cfs_hash_for_each_exit(hs); + RETURN(count); } typedef struct { @@ -1485,7 +1497,7 @@ typedef struct { static int cfs_hash_cond_del_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode, void *data) + struct hlist_node *hnode, void *data) { cfs_hash_cond_arg_t *cond = data; @@ -1509,7 +1521,7 @@ cfs_hash_cond_del(cfs_hash_t *hs, cfs_hash_cond_opt_cb_t func, void *data) cfs_hash_for_each_tight(hs, cfs_hash_cond_del_locked, &arg, 1); } -CFS_EXPORT_SYMBOL(cfs_hash_cond_del); +EXPORT_SYMBOL(cfs_hash_cond_del); void cfs_hash_for_each(cfs_hash_t *hs, @@ -1517,7 +1529,7 @@ cfs_hash_for_each(cfs_hash_t *hs, { cfs_hash_for_each_tight(hs, func, data, 0); } -CFS_EXPORT_SYMBOL(cfs_hash_for_each); +EXPORT_SYMBOL(cfs_hash_for_each); void cfs_hash_for_each_safe(cfs_hash_t *hs, @@ -1525,14 +1537,14 @@ cfs_hash_for_each_safe(cfs_hash_t *hs, { cfs_hash_for_each_tight(hs, func, data, 1); } -CFS_EXPORT_SYMBOL(cfs_hash_for_each_safe); +EXPORT_SYMBOL(cfs_hash_for_each_safe); static int cfs_hash_peek(cfs_hash_t *hs, cfs_hash_bd_t *bd, - cfs_hlist_node_t *hnode, void *data) + struct hlist_node *hnode, void *data) { - *(int *)data = 0; - return 1; /* return 1 to break the loop */ + *(int *)data = 0; + return 1; /* return 1 to break the loop */ } int @@ -1543,16 +1555,16 @@ cfs_hash_is_empty(cfs_hash_t *hs) cfs_hash_for_each_tight(hs, cfs_hash_peek, &empty, 0); return empty; } -CFS_EXPORT_SYMBOL(cfs_hash_is_empty); +EXPORT_SYMBOL(cfs_hash_is_empty); __u64 cfs_hash_size_get(cfs_hash_t *hs) { - return cfs_hash_with_counter(hs) ? - cfs_atomic_read(&hs->hs_count) : - cfs_hash_for_each_tight(hs, NULL, NULL, 0); + return cfs_hash_with_counter(hs) ? + atomic_read(&hs->hs_count) : + cfs_hash_for_each_tight(hs, NULL, NULL, 0); } -CFS_EXPORT_SYMBOL(cfs_hash_size_get); +EXPORT_SYMBOL(cfs_hash_size_get); /* * cfs_hash_for_each_relax: @@ -1572,8 +1584,8 @@ CFS_EXPORT_SYMBOL(cfs_hash_size_get); static int cfs_hash_for_each_relax(cfs_hash_t *hs, cfs_hash_for_each_cb_t func, void *data) { - cfs_hlist_node_t *hnode; - cfs_hlist_node_t *tmp; + struct hlist_node *hnode; + struct hlist_node *tmp; cfs_hash_bd_t bd; __u32 version; int count = 0; @@ -1588,8 +1600,8 @@ cfs_hash_for_each_relax(cfs_hash_t *hs, cfs_hash_for_each_cb_t func, void *data) cfs_hash_lock(hs, 0); LASSERT(!cfs_hash_is_rehashing(hs)); - cfs_hash_for_each_bucket(hs, &bd, i) { - cfs_hlist_head_t *hhead; + cfs_hash_for_each_bucket(hs, &bd, i) { + struct hlist_head *hhead; cfs_hash_bd_lock(hs, &bd, 0); version = cfs_hash_bd_version_get(&bd); @@ -1601,11 +1613,11 @@ cfs_hash_for_each_relax(cfs_hash_t *hs, cfs_hash_for_each_cb_t func, void *data) cfs_hash_bd_unlock(hs, &bd, 0); cfs_hash_unlock(hs, 0); - rc = func(hs, &bd, hnode, data); - if (stop_on_change) - cfs_hash_put(hs, hnode); - cfs_cond_resched(); - count++; + rc = func(hs, &bd, hnode, data); + if (stop_on_change) + cfs_hash_put(hs, hnode); + cond_resched(); + count++; cfs_hash_lock(hs, 0); cfs_hash_bd_lock(hs, &bd, 0); @@ -1653,7 +1665,7 @@ cfs_hash_for_each_nolock(cfs_hash_t *hs, RETURN(0); } -CFS_EXPORT_SYMBOL(cfs_hash_for_each_nolock); +EXPORT_SYMBOL(cfs_hash_for_each_nolock); /** * For each hash bucket in the libcfs hash @hs call the passed callback @@ -1689,36 +1701,36 @@ cfs_hash_for_each_empty(cfs_hash_t *hs, cfs_hash_for_each_exit(hs); RETURN(0); } -CFS_EXPORT_SYMBOL(cfs_hash_for_each_empty); +EXPORT_SYMBOL(cfs_hash_for_each_empty); void cfs_hash_hlist_for_each(cfs_hash_t *hs, unsigned hindex, - cfs_hash_for_each_cb_t func, void *data) + cfs_hash_for_each_cb_t func, void *data) { - cfs_hlist_head_t *hhead; - cfs_hlist_node_t *hnode; - cfs_hash_bd_t bd; + struct hlist_head *hhead; + struct hlist_node *hnode; + cfs_hash_bd_t bd; cfs_hash_for_each_enter(hs); cfs_hash_lock(hs, 0); if (hindex >= CFS_HASH_NHLIST(hs)) goto out; - cfs_hash_bd_index_set(hs, hindex, &bd); + cfs_hash_bd_index_set(hs, hindex, &bd); - cfs_hash_bd_lock(hs, &bd, 0); - hhead = cfs_hash_bd_hhead(hs, &bd); - cfs_hlist_for_each(hnode, hhead) { - if (func(hs, &bd, hnode, data)) - break; - } - cfs_hash_bd_unlock(hs, &bd, 0); - out: - cfs_hash_unlock(hs, 0); - cfs_hash_for_each_exit(hs); + cfs_hash_bd_lock(hs, &bd, 0); + hhead = cfs_hash_bd_hhead(hs, &bd); + hlist_for_each(hnode, hhead) { + if (func(hs, &bd, hnode, data)) + break; + } + cfs_hash_bd_unlock(hs, &bd, 0); +out: + cfs_hash_unlock(hs, 0); + cfs_hash_for_each_exit(hs); } -CFS_EXPORT_SYMBOL(cfs_hash_hlist_for_each); +EXPORT_SYMBOL(cfs_hash_hlist_for_each); /* * For each item in the libcfs hash @hs which matches the @key call @@ -1728,33 +1740,33 @@ CFS_EXPORT_SYMBOL(cfs_hash_hlist_for_each); */ void cfs_hash_for_each_key(cfs_hash_t *hs, const void *key, - cfs_hash_for_each_cb_t func, void *data) + cfs_hash_for_each_cb_t func, void *data) { - cfs_hlist_node_t *hnode; - cfs_hash_bd_t bds[2]; - unsigned i; + struct hlist_node *hnode; + cfs_hash_bd_t bds[2]; + unsigned i; - cfs_hash_lock(hs, 0); + cfs_hash_lock(hs, 0); - cfs_hash_dual_bd_get_and_lock(hs, key, bds, 0); + cfs_hash_dual_bd_get_and_lock(hs, key, bds, 0); - cfs_hash_for_each_bd(bds, 2, i) { - cfs_hlist_head_t *hlist = cfs_hash_bd_hhead(hs, &bds[i]); + cfs_hash_for_each_bd(bds, 2, i) { + struct hlist_head *hlist = cfs_hash_bd_hhead(hs, &bds[i]); - cfs_hlist_for_each(hnode, hlist) { - cfs_hash_bucket_validate(hs, &bds[i], hnode); + hlist_for_each(hnode, hlist) { + cfs_hash_bucket_validate(hs, &bds[i], hnode); - if (cfs_hash_keycmp(hs, key, hnode)) { - if (func(hs, &bds[i], hnode, data)) - break; - } - } - } + if (cfs_hash_keycmp(hs, key, hnode)) { + if (func(hs, &bds[i], hnode, data)) + break; + } + } + } - cfs_hash_dual_bd_unlock(hs, bds, 0); - cfs_hash_unlock(hs, 0); + cfs_hash_dual_bd_unlock(hs, bds, 0); + cfs_hash_unlock(hs, 0); } -CFS_EXPORT_SYMBOL(cfs_hash_for_each_key); +EXPORT_SYMBOL(cfs_hash_for_each_key); /** * Rehash the libcfs hash @hs to the given @bits. This can be used @@ -1779,22 +1791,22 @@ cfs_hash_rehash_cancel_locked(cfs_hash_t *hs) if (!cfs_hash_is_rehashing(hs)) return; - if (cfs_wi_cancel(&hs->hs_rehash_wi)) { + if (cfs_wi_deschedule(cfs_sched_rehash, &hs->hs_rehash_wi)) { hs->hs_rehash_bits = 0; return; } for (i = 2; cfs_hash_is_rehashing(hs); i++) { - cfs_hash_unlock(hs, 1); - /* raise console warning while waiting too long */ - CDEBUG(IS_PO2(i >> 3) ? D_WARNING : D_INFO, - "hash %s is still rehashing, rescheded %d\n", - hs->hs_name, i - 1); - cfs_cond_resched(); - cfs_hash_lock(hs, 1); - } + cfs_hash_unlock(hs, 1); + /* raise console warning while waiting too long */ + CDEBUG(IS_PO2(i >> 3) ? D_WARNING : D_INFO, + "hash %s is still rehashing, rescheded %d\n", + hs->hs_name, i - 1); + cond_resched(); + cfs_hash_lock(hs, 1); + } } -CFS_EXPORT_SYMBOL(cfs_hash_rehash_cancel_locked); +EXPORT_SYMBOL(cfs_hash_rehash_cancel_locked); void cfs_hash_rehash_cancel(cfs_hash_t *hs) @@ -1803,7 +1815,7 @@ cfs_hash_rehash_cancel(cfs_hash_t *hs) cfs_hash_rehash_cancel_locked(hs); cfs_hash_unlock(hs, 1); } -CFS_EXPORT_SYMBOL(cfs_hash_rehash_cancel); +EXPORT_SYMBOL(cfs_hash_rehash_cancel); int cfs_hash_rehash(cfs_hash_t *hs, int do_rehash) @@ -1823,7 +1835,7 @@ cfs_hash_rehash(cfs_hash_t *hs, int do_rehash) hs->hs_rehash_bits = rc; if (!do_rehash) { /* launch and return */ - cfs_wi_schedule(&hs->hs_rehash_wi); + cfs_wi_schedule(cfs_sched_rehash, &hs->hs_rehash_wi); cfs_hash_unlock(hs, 1); return 0; } @@ -1833,37 +1845,36 @@ cfs_hash_rehash(cfs_hash_t *hs, int do_rehash) return cfs_hash_rehash_worker(&hs->hs_rehash_wi); } -CFS_EXPORT_SYMBOL(cfs_hash_rehash); +EXPORT_SYMBOL(cfs_hash_rehash); static int cfs_hash_rehash_bd(cfs_hash_t *hs, cfs_hash_bd_t *old) { - cfs_hash_bd_t new; - cfs_hlist_head_t *hhead; - cfs_hlist_node_t *hnode; - cfs_hlist_node_t *pos; - void *key; - int c = 0; - - /* hold cfs_hash_lock(hs, 1), so don't need any bucket lock */ - cfs_hash_bd_for_each_hlist(hs, old, hhead) { - cfs_hlist_for_each_safe(hnode, pos, hhead) { - key = cfs_hash_key(hs, hnode); - LASSERT(key != NULL); - /* Validate hnode is in the correct bucket. */ - cfs_hash_bucket_validate(hs, old, hnode); - /* - * Delete from old hash bucket; move to new bucket. - * ops->hs_key must be defined. - */ - cfs_hash_bd_from_key(hs, hs->hs_rehash_buckets, - hs->hs_rehash_bits, key, &new); - cfs_hash_bd_move_locked(hs, old, &new, hnode); - c++; - } - } - - return c; + cfs_hash_bd_t new; + struct hlist_head *hhead; + struct hlist_node *hnode; + struct hlist_node *pos; + void *key; + int c = 0; + + /* hold cfs_hash_lock(hs, 1), so don't need any bucket lock */ + cfs_hash_bd_for_each_hlist(hs, old, hhead) { + hlist_for_each_safe(hnode, pos, hhead) { + key = cfs_hash_key(hs, hnode); + LASSERT(key != NULL); + /* Validate hnode is in the correct bucket. */ + cfs_hash_bucket_validate(hs, old, hnode); + /* + * Delete from old hash bucket; move to new bucket. + * ops->hs_key must be defined. + */ + cfs_hash_bd_from_key(hs, hs->hs_rehash_buckets, + hs->hs_rehash_bits, key, &new); + cfs_hash_bd_move_locked(hs, old, &new, hnode); + c++; + } + } + return c; } static int @@ -1938,11 +1949,11 @@ cfs_hash_rehash_worker(cfs_workitem_t *wi) continue; } - count = 0; - cfs_hash_unlock(hs, 1); - cfs_cond_resched(); - cfs_hash_lock(hs, 1); - } + count = 0; + cfs_hash_unlock(hs, 1); + cond_resched(); + cfs_hash_lock(hs, 1); + } hs->hs_rehash_count++; @@ -1953,8 +1964,8 @@ cfs_hash_rehash_worker(cfs_workitem_t *wi) hs->hs_cur_bits = hs->hs_rehash_bits; out: hs->hs_rehash_bits = 0; - if (rc == -ESRCH) - cfs_wi_exit(wi); /* never be scheduled again */ + if (rc == -ESRCH) /* never be scheduled again */ + cfs_wi_exit(cfs_sched_rehash, wi); bsize = cfs_hash_bkt_size(hs); cfs_hash_unlock(hs, 1); /* can't refer to @hs anymore because it could be destroyed */ @@ -1962,8 +1973,8 @@ cfs_hash_rehash_worker(cfs_workitem_t *wi) cfs_hash_buckets_free(bkts, bsize, new_size, old_size); if (rc != 0) CDEBUG(D_INFO, "early quit of of rehashing: %d\n", rc); - /* cfs_workitem require us to always return 0 */ - return 0; + /* return 1 only if cfs_wi_exit is called */ + return rc == -ESRCH; } /** @@ -1977,13 +1988,13 @@ cfs_hash_rehash_worker(cfs_workitem_t *wi) * not be called. */ void cfs_hash_rehash_key(cfs_hash_t *hs, const void *old_key, - void *new_key, cfs_hlist_node_t *hnode) + void *new_key, struct hlist_node *hnode) { cfs_hash_bd_t bds[3]; cfs_hash_bd_t old_bds[2]; cfs_hash_bd_t new_bd; - LASSERT(!cfs_hlist_unhashed(hnode)); + LASSERT(!hlist_unhashed(hnode)); cfs_hash_lock(hs, 0); @@ -2007,13 +2018,14 @@ void cfs_hash_rehash_key(cfs_hash_t *hs, const void *old_key, } /* overwrite key inside locks, otherwise may screw up with * other operations, i.e: rehash */ - cfs_hash_keycpy(hs, new_key, hnode); + cfs_hash_keycpy(hs, hnode, new_key); cfs_hash_multi_bd_unlock(hs, bds, 3, 1); cfs_hash_unlock(hs, 0); } -CFS_EXPORT_SYMBOL(cfs_hash_rehash_key); +EXPORT_SYMBOL(cfs_hash_rehash_key); +#ifndef HAVE_ONLY_PROCFS_SEQ int cfs_hash_debug_header(char *str, int size) { return snprintf(str, size, "%-*s%6s%6s%6s%6s%6s%6s%6s%7s%8s%8s%8s%s\n", @@ -2022,7 +2034,18 @@ int cfs_hash_debug_header(char *str, int size) "flags", "rehash", "count", "maxdep", "maxdepb", " distribution"); } -CFS_EXPORT_SYMBOL(cfs_hash_debug_header); +EXPORT_SYMBOL(cfs_hash_debug_header); +#endif + +int cfs_hash_debug_header_seq(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"); +} +EXPORT_SYMBOL(cfs_hash_debug_header_seq); static cfs_hash_bucket_t ** cfs_hash_full_bkts(cfs_hash_t *hs) @@ -2048,6 +2071,7 @@ cfs_hash_full_nbkt(cfs_hash_t *hs) CFS_HASH_RH_NBKT(hs) : CFS_HASH_NBKT(hs); } +#ifndef HAVE_ONLY_PROCFS_SEQ int cfs_hash_debug_str(cfs_hash_t *hs, char *str, int size) { int dist[8] = { 0, }; @@ -2102,11 +2126,11 @@ int cfs_hash_debug_str(cfs_hash_t *hs, char *str, int size) if (maxdep < bd.bd_bucket->hsb_depmax) { maxdep = bd.bd_bucket->hsb_depmax; #ifdef __KERNEL__ - maxdepb = cfs_ffz(~maxdep); + maxdepb = ffz(~maxdep); #endif } total += bd.bd_bucket->hsb_count; - dist[min(__cfs_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); } @@ -2121,4 +2145,71 @@ int cfs_hash_debug_str(cfs_hash_t *hs, char *str, int size) return c; } -CFS_EXPORT_SYMBOL(cfs_hash_debug_str); +EXPORT_SYMBOL(cfs_hash_debug_str); +#endif + +int cfs_hash_debug_str_seq(cfs_hash_t *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; + + 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); + + /* + * The distribution is a summary of the chained hash depth in + * each of the libcfs hash buckets. Each buckets hsb_count is + * divided by the hash theta value and used to generate a + * histogram of the hash distribution. A uniform hash will + * result in all hash buckets being close to the average thus + * only the first few entries in the histogram will be non-zero. + * If you hash function results in a non-uniform hash the will + * be observable by outlier bucks in the distribution histogram. + * + * Uniform hash distribution: 128/128/0/0/0/0/0/0 + * Non-Uniform hash distribution: 128/125/0/0/0/0/2/1 + */ + for (i = 0; i < cfs_hash_full_nbkt(hs); i++) { + cfs_hash_bd_t bd; + + bd.bd_bucket = cfs_hash_full_bkts(hs)[i]; + cfs_hash_bd_lock(hs, &bd, 0); + if (maxdep < bd.bd_bucket->hsb_depmax) { + maxdep = bd.bd_bucket->hsb_depmax; +#ifdef __KERNEL__ + maxdepb = ffz(~maxdep); +#endif + } + total += bd.bd_bucket->hsb_count; + 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); + for (i = 0; i < 8; i++) + c += seq_printf(m, "%d%c", dist[i], (i == 7) ? '\n' : '/'); + + cfs_hash_unlock(hs, 0); + return c; +} +EXPORT_SYMBOL(cfs_hash_debug_str_seq);