OSCL-LXR linux-6.0.1/​lib/​rhashtable.c	Source navigation Diff markup Identifier search General search
	Version: linux-6.0.1 spark-3.0.0 hadoop-3.2.0-src hadoop-3.3.0-src spark-2.4.7 linux-4.15.13 hadoop-2.7.4-src Revert   Change

 // SPDX-License-Identifier: GPL-2.0-only
 /*
  * Resizable, Scalable, Concurrent Hash Table
  *
  * Copyright (c) 2015 Herbert Xu <herbert@gondor.apana.org.au>
  * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
  *
  * Code partially derived from nft_hash
  * Rewritten with rehash code from br_multicast plus single list
  * pointer as suggested by Josh Triplett
  */
 
 #include <linux/atomic.h>
 #include <linux/kernel.h>
 #include <linux/init.h>
 #include <linux/log2.h>
 #include <linux/sched.h>
 #include <linux/rculist.h>
 #include <linux/slab.h>
 #include <linux/vmalloc.h>
 #include <linux/mm.h>
 #include <linux/jhash.h>
 #include <linux/random.h>
 #include <linux/rhashtable.h>
 #include <linux/err.h>
 #include <linux/export.h>
 
 #define HASH_DEFAULT_SIZE   64UL
 #define HASH_MIN_SIZE       4U
 
 union nested_table {
     union nested_table __rcu *table;
     struct rhash_lock_head __rcu *bucket;
 };
 
 static u32 head_hashfn(struct rhashtable *ht,
                const struct bucket_table *tbl,
                const struct rhash_head *he)
 {
     return rht_head_hashfn(ht, tbl, he, ht->p);
 }
 
 #ifdef CONFIG_PROVE_LOCKING
 #define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
 
 int lockdep_rht_mutex_is_held(struct rhashtable *ht)
 {
     return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
 }
 EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
 
 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
 {
     if (!debug_locks)
         return 1;
     if (unlikely(tbl->nest))
         return 1;
     return bit_spin_is_locked(0, (unsigned long *)&tbl->buckets[hash]);
 }
 EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
 #else
 #define ASSERT_RHT_MUTEX(HT)
 #endif
 
 static inline union nested_table *nested_table_top(
     const struct bucket_table *tbl)
 {
     /* The top-level bucket entry does not need RCU protection
      * because it's set at the same time as tbl->nest.
      */
     return (void *)rcu_dereference_protected(tbl->buckets[0], 1);
 }
 
 static void nested_table_free(union nested_table *ntbl, unsigned int size)
 {
     const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
     const unsigned int len = 1 << shift;
     unsigned int i;
 
     ntbl = rcu_dereference_protected(ntbl->table, 1);
     if (!ntbl)
         return;
 
     if (size > len) {
         size >>= shift;
         for (i = 0; i < len; i++)
             nested_table_free(ntbl + i, size);
     }
 
     kfree(ntbl);
 }
 
 static void nested_bucket_table_free(const struct bucket_table *tbl)
 {
     unsigned int size = tbl->size >> tbl->nest;
     unsigned int len = 1 << tbl->nest;
     union nested_table *ntbl;
     unsigned int i;
 
     ntbl = nested_table_top(tbl);
 
     for (i = 0; i < len; i++)
         nested_table_free(ntbl + i, size);
 
     kfree(ntbl);
 }
 
 static void bucket_table_free(const struct bucket_table *tbl)
 {
     if (tbl->nest)
         nested_bucket_table_free(tbl);
 
     kvfree(tbl);
 }
 
 static void bucket_table_free_rcu(struct rcu_head *head)
 {
     bucket_table_free(container_of(head, struct bucket_table, rcu));
 }
 
 static union nested_table *nested_table_alloc(struct rhashtable *ht,
                           union nested_table __rcu **prev,
                           bool leaf)
 {
     union nested_table *ntbl;
     int i;
 
     ntbl = rcu_dereference(*prev);
     if (ntbl)
         return ntbl;
 
     ntbl = kzalloc(PAGE_SIZE, GFP_ATOMIC);
 
     if (ntbl && leaf) {
         for (i = 0; i < PAGE_SIZE / sizeof(ntbl[0]); i++)
             INIT_RHT_NULLS_HEAD(ntbl[i].bucket);
     }
 
     if (cmpxchg((union nested_table **)prev, NULL, ntbl) == NULL)
         return ntbl;
     /* Raced with another thread. */
     kfree(ntbl);
     return rcu_dereference(*prev);
 }
 
 static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht,
                               size_t nbuckets,
                               gfp_t gfp)
 {
     const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
     struct bucket_table *tbl;
     size_t size;
 
     if (nbuckets < (1 << (shift + 1)))
         return NULL;
 
     size = sizeof(*tbl) + sizeof(tbl->buckets[0]);
 
     tbl = kzalloc(size, gfp);
     if (!tbl)
         return NULL;
 
     if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets,
                 false)) {
         kfree(tbl);
         return NULL;
     }
 
     tbl->nest = (ilog2(nbuckets) - 1) % shift + 1;
 
     return tbl;
 }
 
 static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
                            size_t nbuckets,
                            gfp_t gfp)
 {
     struct bucket_table *tbl = NULL;
     size_t size;
     int i;
     static struct lock_class_key __key;
 
     tbl = kvzalloc(struct_size(tbl, buckets, nbuckets), gfp);
 
     size = nbuckets;
 
     if (tbl == NULL && (gfp & ~__GFP_NOFAIL) != GFP_KERNEL) {
         tbl = nested_bucket_table_alloc(ht, nbuckets, gfp);
         nbuckets = 0;
     }
 
     if (tbl == NULL)
         return NULL;
 
     lockdep_init_map(&tbl->dep_map, "rhashtable_bucket", &__key, 0);
 
     tbl->size = size;
 
     rcu_head_init(&tbl->rcu);
     INIT_LIST_HEAD(&tbl->walkers);
 
     tbl->hash_rnd = get_random_u32();
 
     for (i = 0; i < nbuckets; i++)
         INIT_RHT_NULLS_HEAD(tbl->buckets[i]);
 
     return tbl;
 }
 
 static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
                           struct bucket_table *tbl)
 {
     struct bucket_table *new_tbl;
 
     do {
         new_tbl = tbl;
         tbl = rht_dereference_rcu(tbl->future_tbl, ht);
     } while (tbl);
 
     return new_tbl;
 }
 
 static int rhashtable_rehash_one(struct rhashtable *ht,
                  struct rhash_lock_head __rcu **bkt,
                  unsigned int old_hash)
 {
     struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
     struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl);
     int err = -EAGAIN;
     struct rhash_head *head, *next, *entry;
     struct rhash_head __rcu **pprev = NULL;
     unsigned int new_hash;
 
     if (new_tbl->nest)
         goto out;
 
     err = -ENOENT;
 
     rht_for_each_from(entry, rht_ptr(bkt, old_tbl, old_hash),
               old_tbl, old_hash) {
         err = 0;
         next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
 
         if (rht_is_a_nulls(next))
             break;
 
         pprev = &entry->next;
     }
 
     if (err)
         goto out;
 
     new_hash = head_hashfn(ht, new_tbl, entry);
 
     rht_lock_nested(new_tbl, &new_tbl->buckets[new_hash], SINGLE_DEPTH_NESTING);
 
     head = rht_ptr(new_tbl->buckets + new_hash, new_tbl, new_hash);
 
     RCU_INIT_POINTER(entry->next, head);
 
     rht_assign_unlock(new_tbl, &new_tbl->buckets[new_hash], entry);
 
     if (pprev)
         rcu_assign_pointer(*pprev, next);
     else
         /* Need to preserved the bit lock. */
         rht_assign_locked(bkt, next);
 
 out:
     return err;
 }
 
 static int rhashtable_rehash_chain(struct rhashtable *ht,
                     unsigned int old_hash)
 {
     struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
     struct rhash_lock_head __rcu **bkt = rht_bucket_var(old_tbl, old_hash);
     int err;
 
     if (!bkt)
         return 0;
     rht_lock(old_tbl, bkt);
 
     while (!(err = rhashtable_rehash_one(ht, bkt, old_hash)))
         ;
 
     if (err == -ENOENT)
         err = 0;
     rht_unlock(old_tbl, bkt);
 
     return err;
 }
 
 static int rhashtable_rehash_attach(struct rhashtable *ht,
                     struct bucket_table *old_tbl,
                     struct bucket_table *new_tbl)
 {
     /* Make insertions go into the new, empty table right away. Deletions
      * and lookups will be attempted in both tables until we synchronize.
      * As cmpxchg() provides strong barriers, we do not need
      * rcu_assign_pointer().
      */
 
     if (cmpxchg((struct bucket_table **)&old_tbl->future_tbl, NULL,
             new_tbl) != NULL)
         return -EEXIST;
 
     return 0;
 }
 
 static int rhashtable_rehash_table(struct rhashtable *ht)
 {
     struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
     struct bucket_table *new_tbl;
     struct rhashtable_walker *walker;
     unsigned int old_hash;
     int err;
 
     new_tbl = rht_dereference(old_tbl->future_tbl, ht);
     if (!new_tbl)
         return 0;
 
     for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
         err = rhashtable_rehash_chain(ht, old_hash);
         if (err)
             return err;
         cond_resched();
     }
 
     /* Publish the new table pointer. */
     rcu_assign_pointer(ht->tbl, new_tbl);
 
     spin_lock(&ht->lock);
     list_for_each_entry(walker, &old_tbl->walkers, list)
         walker->tbl = NULL;
 
     /* Wait for readers. All new readers will see the new
      * table, and thus no references to the old table will
      * remain.
      * We do this inside the locked region so that
      * rhashtable_walk_stop() can use rcu_head_after_call_rcu()
      * to check if it should not re-link the table.
      */
     call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
     spin_unlock(&ht->lock);
 
     return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
 }
 
 static int rhashtable_rehash_alloc(struct rhashtable *ht,
                    struct bucket_table *old_tbl,
                    unsigned int size)
 {
     struct bucket_table *new_tbl;
     int err;
 
     ASSERT_RHT_MUTEX(ht);
 
     new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
     if (new_tbl == NULL)
         return -ENOMEM;
 
     err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
     if (err)
         bucket_table_free(new_tbl);
 
     return err;
 }
 
 /**
  * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
  * @ht:     the hash table to shrink
  *
  * This function shrinks the hash table to fit, i.e., the smallest
  * size would not cause it to expand right away automatically.
  *
  * The caller must ensure that no concurrent resizing occurs by holding
  * ht->mutex.
  *
  * The caller must ensure that no concurrent table mutations take place.
  * It is however valid to have concurrent lookups if they are RCU protected.
  *
  * It is valid to have concurrent insertions and deletions protected by per
  * bucket locks or concurrent RCU protected lookups and traversals.
  */
 static int rhashtable_shrink(struct rhashtable *ht)
 {
     struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
     unsigned int nelems = atomic_read(&ht->nelems);
     unsigned int size = 0;
 
     if (nelems)
         size = roundup_pow_of_two(nelems * 3 / 2);
     if (size < ht->p.min_size)
         size = ht->p.min_size;
 
     if (old_tbl->size <= size)
         return 0;
 
     if (rht_dereference(old_tbl->future_tbl, ht))
         return -EEXIST;
 
     return rhashtable_rehash_alloc(ht, old_tbl, size);
 }
 
 static void rht_deferred_worker(struct work_struct *work)
 {
     struct rhashtable *ht;
     struct bucket_table *tbl;
     int err = 0;
 
     ht = container_of(work, struct rhashtable, run_work);
     mutex_lock(&ht->mutex);
 
     tbl = rht_dereference(ht->tbl, ht);
     tbl = rhashtable_last_table(ht, tbl);
 
     if (rht_grow_above_75(ht, tbl))
         err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2);
     else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
         err = rhashtable_shrink(ht);
     else if (tbl->nest)
         err = rhashtable_rehash_alloc(ht, tbl, tbl->size);
 
     if (!err || err == -EEXIST) {
         int nerr;
 
         nerr = rhashtable_rehash_table(ht);
         err = err ?: nerr;
     }
 
     mutex_unlock(&ht->mutex);
 
     if (err)
         schedule_work(&ht->run_work);
 }
 
 static int rhashtable_insert_rehash(struct rhashtable *ht,
                     struct bucket_table *tbl)
 {
     struct bucket_table *old_tbl;
     struct bucket_table *new_tbl;
     unsigned int size;
     int err;
 
     old_tbl = rht_dereference_rcu(ht->tbl, ht);
 
     size = tbl->size;
 
     err = -EBUSY;
 
     if (rht_grow_above_75(ht, tbl))
         size *= 2;
     /* Do not schedule more than one rehash */
     else if (old_tbl != tbl)
         goto fail;
 
     err = -ENOMEM;
 
     new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC | __GFP_NOWARN);
     if (new_tbl == NULL)
         goto fail;
 
     err = rhashtable_rehash_attach(ht, tbl, new_tbl);
     if (err) {
         bucket_table_free(new_tbl);
         if (err == -EEXIST)
             err = 0;
     } else
         schedule_work(&ht->run_work);
 
     return err;
 
 fail:
     /* Do not fail the insert if someone else did a rehash. */
     if (likely(rcu_access_pointer(tbl->future_tbl)))
         return 0;
 
     /* Schedule async rehash to retry allocation in process context. */
     if (err == -ENOMEM)
         schedule_work(&ht->run_work);
 
     return err;
 }
 
 static void *rhashtable_lookup_one(struct rhashtable *ht,
                    struct rhash_lock_head __rcu **bkt,
                    struct bucket_table *tbl, unsigned int hash,
                    const void *key, struct rhash_head *obj)
 {
     struct rhashtable_compare_arg arg = {
         .ht = ht,
         .key = key,
     };
     struct rhash_head __rcu **pprev = NULL;
     struct rhash_head *head;
     int elasticity;
 
     elasticity = RHT_ELASTICITY;
     rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {
         struct rhlist_head *list;
         struct rhlist_head *plist;
 
         elasticity--;
         if (!key ||
             (ht->p.obj_cmpfn ?
              ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
              rhashtable_compare(&arg, rht_obj(ht, head)))) {
             pprev = &head->next;
             continue;
         }
 
         if (!ht->rhlist)
             return rht_obj(ht, head);
 
         list = container_of(obj, struct rhlist_head, rhead);
         plist = container_of(head, struct rhlist_head, rhead);
 
         RCU_INIT_POINTER(list->next, plist);
         head = rht_dereference_bucket(head->next, tbl, hash);
         RCU_INIT_POINTER(list->rhead.next, head);
         if (pprev)
             rcu_assign_pointer(*pprev, obj);
         else
             /* Need to preserve the bit lock */
             rht_assign_locked(bkt, obj);
 
         return NULL;
     }
 
     if (elasticity <= 0)
         return ERR_PTR(-EAGAIN);
 
     return ERR_PTR(-ENOENT);
 }
 
 static struct bucket_table *rhashtable_insert_one(
     struct rhashtable *ht, struct rhash_lock_head __rcu **bkt,
     struct bucket_table *tbl, unsigned int hash, struct rhash_head *obj,
     void *data)
 {
     struct bucket_table *new_tbl;
     struct rhash_head *head;
 
     if (!IS_ERR_OR_NULL(data))
         return ERR_PTR(-EEXIST);
 
     if (PTR_ERR(data) != -EAGAIN && PTR_ERR(data) != -ENOENT)
         return ERR_CAST(data);
 
     new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
     if (new_tbl)
         return new_tbl;
 
     if (PTR_ERR(data) != -ENOENT)
         return ERR_CAST(data);
 
     if (unlikely(rht_grow_above_max(ht, tbl)))
         return ERR_PTR(-E2BIG);
 
     if (unlikely(rht_grow_above_100(ht, tbl)))
         return ERR_PTR(-EAGAIN);
 
     head = rht_ptr(bkt, tbl, hash);
 
     RCU_INIT_POINTER(obj->next, head);
     if (ht->rhlist) {
         struct rhlist_head *list;
 
         list = container_of(obj, struct rhlist_head, rhead);
         RCU_INIT_POINTER(list->next, NULL);
     }
 
     /* bkt is always the head of the list, so it holds
      * the lock, which we need to preserve
      */
     rht_assign_locked(bkt, obj);
 
     atomic_inc(&ht->nelems);
     if (rht_grow_above_75(ht, tbl))
         schedule_work(&ht->run_work);
 
     return NULL;
 }
 
 static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
                    struct rhash_head *obj)
 {
     struct bucket_table *new_tbl;
     struct bucket_table *tbl;
     struct rhash_lock_head __rcu **bkt;
     unsigned int hash;
     void *data;
 
     new_tbl = rcu_dereference(ht->tbl);
 
     do {
         tbl = new_tbl;
         hash = rht_head_hashfn(ht, tbl, obj, ht->p);
         if (rcu_access_pointer(tbl->future_tbl))
             /* Failure is OK */
             bkt = rht_bucket_var(tbl, hash);
         else
             bkt = rht_bucket_insert(ht, tbl, hash);
         if (bkt == NULL) {
             new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
             data = ERR_PTR(-EAGAIN);
         } else {
             rht_lock(tbl, bkt);
             data = rhashtable_lookup_one(ht, bkt, tbl,
                              hash, key, obj);
             new_tbl = rhashtable_insert_one(ht, bkt, tbl,
                             hash, obj, data);
             if (PTR_ERR(new_tbl) != -EEXIST)
                 data = ERR_CAST(new_tbl);
 
             rht_unlock(tbl, bkt);
         }
     } while (!IS_ERR_OR_NULL(new_tbl));
 
     if (PTR_ERR(data) == -EAGAIN)
         data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?:
                    -EAGAIN);
 
     return data;
 }
 
 void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
                  struct rhash_head *obj)
 {
     void *data;
 
     do {
         rcu_read_lock();
         data = rhashtable_try_insert(ht, key, obj);
         rcu_read_unlock();
     } while (PTR_ERR(data) == -EAGAIN);
 
     return data;
 }
 EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
 
 /**
  * rhashtable_walk_enter - Initialise an iterator
  * @ht:     Table to walk over
  * @iter:   Hash table Iterator
  *
  * This function prepares a hash table walk.
  *
  * Note that if you restart a walk after rhashtable_walk_stop you
  * may see the same object twice.  Also, you may miss objects if
  * there are removals in between rhashtable_walk_stop and the next
  * call to rhashtable_walk_start.
  *
  * For a completely stable walk you should construct your own data
  * structure outside the hash table.
  *
  * This function may be called from any process context, including
  * non-preemptable context, but cannot be called from softirq or
  * hardirq context.
  *
  * You must call rhashtable_walk_exit after this function returns.
  */
 void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)
 {
     iter->ht = ht;
     iter->p = NULL;
     iter->slot = 0;
     iter->skip = 0;
     iter->end_of_table = 0;
 
     spin_lock(&ht->lock);
     iter->walker.tbl =
         rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
     list_add(&iter->walker.list, &iter->walker.tbl->walkers);
     spin_unlock(&ht->lock);
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
 
 /**
  * rhashtable_walk_exit - Free an iterator
  * @iter:   Hash table Iterator
  *
  * This function frees resources allocated by rhashtable_walk_enter.
  */
 void rhashtable_walk_exit(struct rhashtable_iter *iter)
 {
     spin_lock(&iter->ht->lock);
     if (iter->walker.tbl)
         list_del(&iter->walker.list);
     spin_unlock(&iter->ht->lock);
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
 
 /**
  * rhashtable_walk_start_check - Start a hash table walk
  * @iter:   Hash table iterator
  *
  * Start a hash table walk at the current iterator position.  Note that we take
  * the RCU lock in all cases including when we return an error.  So you must
  * always call rhashtable_walk_stop to clean up.
  *
  * Returns zero if successful.
  *
  * Returns -EAGAIN if resize event occurred.  Note that the iterator
  * will rewind back to the beginning and you may use it immediately
  * by calling rhashtable_walk_next.
  *
  * rhashtable_walk_start is defined as an inline variant that returns
  * void. This is preferred in cases where the caller would ignore
  * resize events and always continue.
  */
 int rhashtable_walk_start_check(struct rhashtable_iter *iter)
     __acquires(RCU)
 {
     struct rhashtable *ht = iter->ht;
     bool rhlist = ht->rhlist;
 
     rcu_read_lock();
 
     spin_lock(&ht->lock);
     if (iter->walker.tbl)
         list_del(&iter->walker.list);
     spin_unlock(&ht->lock);
 
     if (iter->end_of_table)
         return 0;
     if (!iter->walker.tbl) {
         iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);
         iter->slot = 0;
         iter->skip = 0;
         return -EAGAIN;
     }
 
     if (iter->p && !rhlist) {
         /*
          * We need to validate that 'p' is still in the table, and
          * if so, update 'skip'
          */
         struct rhash_head *p;
         int skip = 0;
         rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
             skip++;
             if (p == iter->p) {
                 iter->skip = skip;
                 goto found;
             }
         }
         iter->p = NULL;
     } else if (iter->p && rhlist) {
         /* Need to validate that 'list' is still in the table, and
          * if so, update 'skip' and 'p'.
          */
         struct rhash_head *p;
         struct rhlist_head *list;
         int skip = 0;
         rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
             for (list = container_of(p, struct rhlist_head, rhead);
                  list;
                  list = rcu_dereference(list->next)) {
                 skip++;
                 if (list == iter->list) {
                     iter->p = p;
                     iter->skip = skip;
                     goto found;
                 }
             }
         }
         iter->p = NULL;
     }
 found:
     return 0;
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_start_check);
 
 /**
  * __rhashtable_walk_find_next - Find the next element in a table (or the first
  * one in case of a new walk).
  *
  * @iter:   Hash table iterator
  *
  * Returns the found object or NULL when the end of the table is reached.
  *
  * Returns -EAGAIN if resize event occurred.
  */
 static void *__rhashtable_walk_find_next(struct rhashtable_iter *iter)
 {
     struct bucket_table *tbl = iter->walker.tbl;
     struct rhlist_head *list = iter->list;
     struct rhashtable *ht = iter->ht;
     struct rhash_head *p = iter->p;
     bool rhlist = ht->rhlist;
 
     if (!tbl)
         return NULL;
 
     for (; iter->slot < tbl->size; iter->slot++) {
         int skip = iter->skip;
 
         rht_for_each_rcu(p, tbl, iter->slot) {
             if (rhlist) {
                 list = container_of(p, struct rhlist_head,
                             rhead);
                 do {
                     if (!skip)
                         goto next;
                     skip--;
                     list = rcu_dereference(list->next);
                 } while (list);
 
                 continue;
             }
             if (!skip)
                 break;
             skip--;
         }
 
 next:
         if (!rht_is_a_nulls(p)) {
             iter->skip++;
             iter->p = p;
             iter->list = list;
             return rht_obj(ht, rhlist ? &list->rhead : p);
         }
 
         iter->skip = 0;
     }
 
     iter->p = NULL;
 
     /* Ensure we see any new tables. */
     smp_rmb();
 
     iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht);
     if (iter->walker.tbl) {
         iter->slot = 0;
         iter->skip = 0;
         return ERR_PTR(-EAGAIN);
     } else {
         iter->end_of_table = true;
     }
 
     return NULL;
 }
 
 /**
  * rhashtable_walk_next - Return the next object and advance the iterator
  * @iter:   Hash table iterator
  *
  * Note that you must call rhashtable_walk_stop when you are finished
  * with the walk.
  *
  * Returns the next object or NULL when the end of the table is reached.
  *
  * Returns -EAGAIN if resize event occurred.  Note that the iterator
  * will rewind back to the beginning and you may continue to use it.
  */
 void *rhashtable_walk_next(struct rhashtable_iter *iter)
 {
     struct rhlist_head *list = iter->list;
     struct rhashtable *ht = iter->ht;
     struct rhash_head *p = iter->p;
     bool rhlist = ht->rhlist;
 
     if (p) {
         if (!rhlist || !(list = rcu_dereference(list->next))) {
             p = rcu_dereference(p->next);
             list = container_of(p, struct rhlist_head, rhead);
         }
         if (!rht_is_a_nulls(p)) {
             iter->skip++;
             iter->p = p;
             iter->list = list;
             return rht_obj(ht, rhlist ? &list->rhead : p);
         }
 
         /* At the end of this slot, switch to next one and then find
          * next entry from that point.
          */
         iter->skip = 0;
         iter->slot++;
     }
 
     return __rhashtable_walk_find_next(iter);
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_next);
 
 /**
  * rhashtable_walk_peek - Return the next object but don't advance the iterator
  * @iter:   Hash table iterator
  *
  * Returns the next object or NULL when the end of the table is reached.
  *
  * Returns -EAGAIN if resize event occurred.  Note that the iterator
  * will rewind back to the beginning and you may continue to use it.
  */
 void *rhashtable_walk_peek(struct rhashtable_iter *iter)
 {
     struct rhlist_head *list = iter->list;
     struct rhashtable *ht = iter->ht;
     struct rhash_head *p = iter->p;
 
     if (p)
         return rht_obj(ht, ht->rhlist ? &list->rhead : p);
 
     /* No object found in current iter, find next one in the table. */
 
     if (iter->skip) {
         /* A nonzero skip value points to the next entry in the table
          * beyond that last one that was found. Decrement skip so
          * we find the current value. __rhashtable_walk_find_next
          * will restore the original value of skip assuming that
          * the table hasn't changed.
          */
         iter->skip--;
     }
 
     return __rhashtable_walk_find_next(iter);
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_peek);
 
 /**
  * rhashtable_walk_stop - Finish a hash table walk
  * @iter:   Hash table iterator
  *
  * Finish a hash table walk.  Does not reset the iterator to the start of the
  * hash table.
  */
 void rhashtable_walk_stop(struct rhashtable_iter *iter)
     __releases(RCU)
 {
     struct rhashtable *ht;
     struct bucket_table *tbl = iter->walker.tbl;
 
     if (!tbl)
         goto out;
 
     ht = iter->ht;
 
     spin_lock(&ht->lock);
     if (rcu_head_after_call_rcu(&tbl->rcu, bucket_table_free_rcu))
         /* This bucket table is being freed, don't re-link it. */
         iter->walker.tbl = NULL;
     else
         list_add(&iter->walker.list, &tbl->walkers);
     spin_unlock(&ht->lock);
 
 out:
     rcu_read_unlock();
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
 
 static size_t rounded_hashtable_size(const struct rhashtable_params *params)
 {
     size_t retsize;
 
     if (params->nelem_hint)
         retsize = max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
                   (unsigned long)params->min_size);
     else
         retsize = max(HASH_DEFAULT_SIZE,
                   (unsigned long)params->min_size);
 
     return retsize;
 }
 
 static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
 {
     return jhash2(key, length, seed);
 }
 
 /**
  * rhashtable_init - initialize a new hash table
  * @ht:     hash table to be initialized
  * @params: configuration parameters
  *
  * Initializes a new hash table based on the provided configuration
  * parameters. A table can be configured either with a variable or
  * fixed length key:
  *
  * Configuration Example 1: Fixed length keys
  * struct test_obj {
  *  int         key;
  *  void *          my_member;
  *  struct rhash_head   node;
  * };
  *
  * struct rhashtable_params params = {
  *  .head_offset = offsetof(struct test_obj, node),
  *  .key_offset = offsetof(struct test_obj, key),
  *  .key_len = sizeof(int),
  *  .hashfn = jhash,
  * };
  *
  * Configuration Example 2: Variable length keys
  * struct test_obj {
  *  [...]
  *  struct rhash_head   node;
  * };
  *
  * u32 my_hash_fn(const void *data, u32 len, u32 seed)
  * {
  *  struct test_obj *obj = data;
  *
  *  return [... hash ...];
  * }
  *
  * struct rhashtable_params params = {
  *  .head_offset = offsetof(struct test_obj, node),
  *  .hashfn = jhash,
  *  .obj_hashfn = my_hash_fn,
  * };
  */
 int rhashtable_init(struct rhashtable *ht,
             const struct rhashtable_params *params)
 {
     struct bucket_table *tbl;
     size_t size;
 
     if ((!params->key_len && !params->obj_hashfn) ||
         (params->obj_hashfn && !params->obj_cmpfn))
         return -EINVAL;
 
     memset(ht, 0, sizeof(*ht));
     mutex_init(&ht->mutex);
     spin_lock_init(&ht->lock);
     memcpy(&ht->p, params, sizeof(*params));
 
     if (params->min_size)
         ht->p.min_size = roundup_pow_of_two(params->min_size);
 
     /* Cap total entries at 2^31 to avoid nelems overflow. */
     ht->max_elems = 1u << 31;
 
     if (params->max_size) {
         ht->p.max_size = rounddown_pow_of_two(params->max_size);
         if (ht->p.max_size < ht->max_elems / 2)
             ht->max_elems = ht->p.max_size * 2;
     }
 
     ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
 
     size = rounded_hashtable_size(&ht->p);
 
     ht->key_len = ht->p.key_len;
     if (!params->hashfn) {
         ht->p.hashfn = jhash;
 
         if (!(ht->key_len & (sizeof(u32) - 1))) {
             ht->key_len /= sizeof(u32);
             ht->p.hashfn = rhashtable_jhash2;
         }
     }
 
     /*
      * This is api initialization and thus we need to guarantee the
      * initial rhashtable allocation. Upon failure, retry with the
      * smallest possible size with __GFP_NOFAIL semantics.
      */
     tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
     if (unlikely(tbl == NULL)) {
         size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
         tbl = bucket_table_alloc(ht, size, GFP_KERNEL | __GFP_NOFAIL);
     }
 
     atomic_set(&ht->nelems, 0);
 
     RCU_INIT_POINTER(ht->tbl, tbl);
 
     INIT_WORK(&ht->run_work, rht_deferred_worker);
 
     return 0;
 }
 EXPORT_SYMBOL_GPL(rhashtable_init);
 
 /**
  * rhltable_init - initialize a new hash list table
  * @hlt:    hash list table to be initialized
  * @params: configuration parameters
  *
  * Initializes a new hash list table.
  *
  * See documentation for rhashtable_init.
  */
 int rhltable_init(struct rhltable *hlt, const struct rhashtable_params *params)
 {
     int err;
 
     err = rhashtable_init(&hlt->ht, params);
     hlt->ht.rhlist = true;
     return err;
 }
 EXPORT_SYMBOL_GPL(rhltable_init);
 
 static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,
                 void (*free_fn)(void *ptr, void *arg),
                 void *arg)
 {
     struct rhlist_head *list;
 
     if (!ht->rhlist) {
         free_fn(rht_obj(ht, obj), arg);
         return;
     }
 
     list = container_of(obj, struct rhlist_head, rhead);
     do {
         obj = &list->rhead;
         list = rht_dereference(list->next, ht);
         free_fn(rht_obj(ht, obj), arg);
     } while (list);
 }
 
 /**
  * rhashtable_free_and_destroy - free elements and destroy hash table
  * @ht:     the hash table to destroy
  * @free_fn:    callback to release resources of element
  * @arg:    pointer passed to free_fn
  *
  * Stops an eventual async resize. If defined, invokes free_fn for each
  * element to releasal resources. Please note that RCU protected
  * readers may still be accessing the elements. Releasing of resources
  * must occur in a compatible manner. Then frees the bucket array.
  *
  * This function will eventually sleep to wait for an async resize
  * to complete. The caller is responsible that no further write operations
  * occurs in parallel.
  */
 void rhashtable_free_and_destroy(struct rhashtable *ht,
                  void (*free_fn)(void *ptr, void *arg),
                  void *arg)
 {
     struct bucket_table *tbl, *next_tbl;
     unsigned int i;
 
     cancel_work_sync(&ht->run_work);
 
     mutex_lock(&ht->mutex);
     tbl = rht_dereference(ht->tbl, ht);
 restart:
     if (free_fn) {
         for (i = 0; i < tbl->size; i++) {
             struct rhash_head *pos, *next;
 
             cond_resched();
             for (pos = rht_ptr_exclusive(rht_bucket(tbl, i)),
                  next = !rht_is_a_nulls(pos) ?
                     rht_dereference(pos->next, ht) : NULL;
                  !rht_is_a_nulls(pos);
                  pos = next,
                  next = !rht_is_a_nulls(pos) ?
                     rht_dereference(pos->next, ht) : NULL)
                 rhashtable_free_one(ht, pos, free_fn, arg);
         }
     }
 
     next_tbl = rht_dereference(tbl->future_tbl, ht);
     bucket_table_free(tbl);
     if (next_tbl) {
         tbl = next_tbl;
         goto restart;
     }
     mutex_unlock(&ht->mutex);
 }
 EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
 
 void rhashtable_destroy(struct rhashtable *ht)
 {
     return rhashtable_free_and_destroy(ht, NULL, NULL);
 }
 EXPORT_SYMBOL_GPL(rhashtable_destroy);
 
 struct rhash_lock_head __rcu **__rht_bucket_nested(
     const struct bucket_table *tbl, unsigned int hash)
 {
     const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
     unsigned int index = hash & ((1 << tbl->nest) - 1);
     unsigned int size = tbl->size >> tbl->nest;
     unsigned int subhash = hash;
     union nested_table *ntbl;
 
     ntbl = nested_table_top(tbl);
     ntbl = rht_dereference_bucket_rcu(ntbl[index].table, tbl, hash);
     subhash >>= tbl->nest;
 
     while (ntbl && size > (1 << shift)) {
         index = subhash & ((1 << shift) - 1);
         ntbl = rht_dereference_bucket_rcu(ntbl[index].table,
                           tbl, hash);
         size >>= shift;
         subhash >>= shift;
     }
 
     if (!ntbl)
         return NULL;
 
     return &ntbl[subhash].bucket;
 
 }
 EXPORT_SYMBOL_GPL(__rht_bucket_nested);
 
 struct rhash_lock_head __rcu **rht_bucket_nested(
     const struct bucket_table *tbl, unsigned int hash)
 {
     static struct rhash_lock_head __rcu *rhnull;
 
     if (!rhnull)
         INIT_RHT_NULLS_HEAD(rhnull);
     return __rht_bucket_nested(tbl, hash) ?: &rhnull;
 }
 EXPORT_SYMBOL_GPL(rht_bucket_nested);
 
 struct rhash_lock_head __rcu **rht_bucket_nested_insert(
     struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)
 {
     const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
     unsigned int index = hash & ((1 << tbl->nest) - 1);
     unsigned int size = tbl->size >> tbl->nest;
     union nested_table *ntbl;
 
     ntbl = nested_table_top(tbl);
     hash >>= tbl->nest;
     ntbl = nested_table_alloc(ht, &ntbl[index].table,
                   size <= (1 << shift));
 
     while (ntbl && size > (1 << shift)) {
         index = hash & ((1 << shift) - 1);
         size >>= shift;
         hash >>= shift;
         ntbl = nested_table_alloc(ht, &ntbl[index].table,
                       size <= (1 << shift));
     }
 
     if (!ntbl)
         return NULL;
 
     return &ntbl[hash].bucket;
 
 }
 EXPORT_SYMBOL_GPL(rht_bucket_nested_insert);

This page was automatically generated by the 2.1.0 LXR engine. The LXR team