17e1e7763SThomas Graf /* 27e1e7763SThomas Graf * Resizable, Scalable, Concurrent Hash Table 37e1e7763SThomas Graf * 402fd97c3SHerbert Xu * Copyright (c) 2015 Herbert Xu <herbert@gondor.apana.org.au> 5a5ec68e3SThomas Graf * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch> 67e1e7763SThomas Graf * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net> 77e1e7763SThomas Graf * 87e1e7763SThomas Graf * Code partially derived from nft_hash 902fd97c3SHerbert Xu * Rewritten with rehash code from br_multicast plus single list 1002fd97c3SHerbert Xu * pointer as suggested by Josh Triplett 117e1e7763SThomas Graf * 127e1e7763SThomas Graf * This program is free software; you can redistribute it and/or modify 137e1e7763SThomas Graf * it under the terms of the GNU General Public License version 2 as 147e1e7763SThomas Graf * published by the Free Software Foundation. 157e1e7763SThomas Graf */ 167e1e7763SThomas Graf 1707ee0722SHerbert Xu #include <linux/atomic.h> 187e1e7763SThomas Graf #include <linux/kernel.h> 197e1e7763SThomas Graf #include <linux/init.h> 207e1e7763SThomas Graf #include <linux/log2.h> 215beb5c90SEric Dumazet #include <linux/sched.h> 22b2d09103SIngo Molnar #include <linux/rculist.h> 237e1e7763SThomas Graf #include <linux/slab.h> 247e1e7763SThomas Graf #include <linux/vmalloc.h> 257e1e7763SThomas Graf #include <linux/mm.h> 2687545899SDaniel Borkmann #include <linux/jhash.h> 277e1e7763SThomas Graf #include <linux/random.h> 287e1e7763SThomas Graf #include <linux/rhashtable.h> 2961d7b097SStephen Rothwell #include <linux/err.h> 306d795413SHauke Mehrtens #include <linux/export.h> 310eb71a9dSNeilBrown #include <linux/rhashtable.h> 327e1e7763SThomas Graf 337e1e7763SThomas Graf #define HASH_DEFAULT_SIZE 64UL 34c2e213cfSHerbert Xu #define HASH_MIN_SIZE 4U 354cf0b354SFlorian Westphal #define BUCKET_LOCKS_PER_CPU 32UL 3697defe1eSThomas Graf 37da20420fSHerbert Xu union nested_table { 38da20420fSHerbert Xu union nested_table __rcu *table; 39da20420fSHerbert Xu struct rhash_head __rcu *bucket; 40da20420fSHerbert Xu }; 41da20420fSHerbert Xu 42988dfbd7SHerbert Xu static u32 head_hashfn(struct rhashtable *ht, 438d24c0b4SThomas Graf const struct bucket_table *tbl, 448d24c0b4SThomas Graf const struct rhash_head *he) 457e1e7763SThomas Graf { 4602fd97c3SHerbert Xu return rht_head_hashfn(ht, tbl, he, ht->p); 477e1e7763SThomas Graf } 487e1e7763SThomas Graf 49a03eaec0SThomas Graf #ifdef CONFIG_PROVE_LOCKING 50a03eaec0SThomas Graf #define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT)) 51a03eaec0SThomas Graf 52a03eaec0SThomas Graf int lockdep_rht_mutex_is_held(struct rhashtable *ht) 53a03eaec0SThomas Graf { 54a03eaec0SThomas Graf return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1; 55a03eaec0SThomas Graf } 56a03eaec0SThomas Graf EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held); 57a03eaec0SThomas Graf 58a03eaec0SThomas Graf int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash) 59a03eaec0SThomas Graf { 6002fd97c3SHerbert Xu spinlock_t *lock = rht_bucket_lock(tbl, hash); 61a03eaec0SThomas Graf 62a03eaec0SThomas Graf return (debug_locks) ? lockdep_is_held(lock) : 1; 63a03eaec0SThomas Graf } 64a03eaec0SThomas Graf EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held); 65a03eaec0SThomas Graf #else 66a03eaec0SThomas Graf #define ASSERT_RHT_MUTEX(HT) 67a03eaec0SThomas Graf #endif 68a03eaec0SThomas Graf 69da20420fSHerbert Xu static void nested_table_free(union nested_table *ntbl, unsigned int size) 70da20420fSHerbert Xu { 71da20420fSHerbert Xu const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *)); 72da20420fSHerbert Xu const unsigned int len = 1 << shift; 73da20420fSHerbert Xu unsigned int i; 74da20420fSHerbert Xu 75da20420fSHerbert Xu ntbl = rcu_dereference_raw(ntbl->table); 76da20420fSHerbert Xu if (!ntbl) 77da20420fSHerbert Xu return; 78da20420fSHerbert Xu 79da20420fSHerbert Xu if (size > len) { 80da20420fSHerbert Xu size >>= shift; 81da20420fSHerbert Xu for (i = 0; i < len; i++) 82da20420fSHerbert Xu nested_table_free(ntbl + i, size); 83da20420fSHerbert Xu } 84da20420fSHerbert Xu 85da20420fSHerbert Xu kfree(ntbl); 86da20420fSHerbert Xu } 87da20420fSHerbert Xu 88da20420fSHerbert Xu static void nested_bucket_table_free(const struct bucket_table *tbl) 89da20420fSHerbert Xu { 90da20420fSHerbert Xu unsigned int size = tbl->size >> tbl->nest; 91da20420fSHerbert Xu unsigned int len = 1 << tbl->nest; 92da20420fSHerbert Xu union nested_table *ntbl; 93da20420fSHerbert Xu unsigned int i; 94da20420fSHerbert Xu 95da20420fSHerbert Xu ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]); 96da20420fSHerbert Xu 97da20420fSHerbert Xu for (i = 0; i < len; i++) 98da20420fSHerbert Xu nested_table_free(ntbl + i, size); 99da20420fSHerbert Xu 100da20420fSHerbert Xu kfree(ntbl); 101da20420fSHerbert Xu } 102da20420fSHerbert Xu 10397defe1eSThomas Graf static void bucket_table_free(const struct bucket_table *tbl) 10497defe1eSThomas Graf { 105da20420fSHerbert Xu if (tbl->nest) 106da20420fSHerbert Xu nested_bucket_table_free(tbl); 107da20420fSHerbert Xu 10864e0cd0dSTom Herbert free_bucket_spinlocks(tbl->locks); 10997defe1eSThomas Graf kvfree(tbl); 11097defe1eSThomas Graf } 11197defe1eSThomas Graf 1129d901bc0SHerbert Xu static void bucket_table_free_rcu(struct rcu_head *head) 1139d901bc0SHerbert Xu { 1149d901bc0SHerbert Xu bucket_table_free(container_of(head, struct bucket_table, rcu)); 1159d901bc0SHerbert Xu } 1169d901bc0SHerbert Xu 117da20420fSHerbert Xu static union nested_table *nested_table_alloc(struct rhashtable *ht, 118da20420fSHerbert Xu union nested_table __rcu **prev, 1195af68ef7SNeilBrown bool leaf) 120da20420fSHerbert Xu { 121da20420fSHerbert Xu union nested_table *ntbl; 122da20420fSHerbert Xu int i; 123da20420fSHerbert Xu 124da20420fSHerbert Xu ntbl = rcu_dereference(*prev); 125da20420fSHerbert Xu if (ntbl) 126da20420fSHerbert Xu return ntbl; 127da20420fSHerbert Xu 128da20420fSHerbert Xu ntbl = kzalloc(PAGE_SIZE, GFP_ATOMIC); 129da20420fSHerbert Xu 1305af68ef7SNeilBrown if (ntbl && leaf) { 1315af68ef7SNeilBrown for (i = 0; i < PAGE_SIZE / sizeof(ntbl[0]); i++) 1329b4f64a2SNeilBrown INIT_RHT_NULLS_HEAD(ntbl[i].bucket); 133da20420fSHerbert Xu } 134da20420fSHerbert Xu 135da20420fSHerbert Xu rcu_assign_pointer(*prev, ntbl); 136da20420fSHerbert Xu 137da20420fSHerbert Xu return ntbl; 138da20420fSHerbert Xu } 139da20420fSHerbert Xu 140da20420fSHerbert Xu static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht, 141da20420fSHerbert Xu size_t nbuckets, 142da20420fSHerbert Xu gfp_t gfp) 143da20420fSHerbert Xu { 144da20420fSHerbert Xu const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *)); 145da20420fSHerbert Xu struct bucket_table *tbl; 146da20420fSHerbert Xu size_t size; 147da20420fSHerbert Xu 148da20420fSHerbert Xu if (nbuckets < (1 << (shift + 1))) 149da20420fSHerbert Xu return NULL; 150da20420fSHerbert Xu 151da20420fSHerbert Xu size = sizeof(*tbl) + sizeof(tbl->buckets[0]); 152da20420fSHerbert Xu 153da20420fSHerbert Xu tbl = kzalloc(size, gfp); 154da20420fSHerbert Xu if (!tbl) 155da20420fSHerbert Xu return NULL; 156da20420fSHerbert Xu 157da20420fSHerbert Xu if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets, 1585af68ef7SNeilBrown false)) { 159da20420fSHerbert Xu kfree(tbl); 160da20420fSHerbert Xu return NULL; 161da20420fSHerbert Xu } 162da20420fSHerbert Xu 163da20420fSHerbert Xu tbl->nest = (ilog2(nbuckets) - 1) % shift + 1; 164da20420fSHerbert Xu 165da20420fSHerbert Xu return tbl; 166da20420fSHerbert Xu } 167da20420fSHerbert Xu 16897defe1eSThomas Graf static struct bucket_table *bucket_table_alloc(struct rhashtable *ht, 169b9ecfdaaSHerbert Xu size_t nbuckets, 170b9ecfdaaSHerbert Xu gfp_t gfp) 1717e1e7763SThomas Graf { 172eb6d1abfSDaniel Borkmann struct bucket_table *tbl = NULL; 17364e0cd0dSTom Herbert size_t size, max_locks; 174f89bd6f8SThomas Graf int i; 1757e1e7763SThomas Graf 1767e1e7763SThomas Graf size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]); 17712e8fd6fSMichal Hocko if (gfp != GFP_KERNEL) 178b9ecfdaaSHerbert Xu tbl = kzalloc(size, gfp | __GFP_NOWARN | __GFP_NORETRY); 17912e8fd6fSMichal Hocko else 18012e8fd6fSMichal Hocko tbl = kvzalloc(size, gfp); 181da20420fSHerbert Xu 182da20420fSHerbert Xu size = nbuckets; 183da20420fSHerbert Xu 184da20420fSHerbert Xu if (tbl == NULL && gfp != GFP_KERNEL) { 185da20420fSHerbert Xu tbl = nested_bucket_table_alloc(ht, nbuckets, gfp); 186da20420fSHerbert Xu nbuckets = 0; 187da20420fSHerbert Xu } 1887e1e7763SThomas Graf if (tbl == NULL) 1897e1e7763SThomas Graf return NULL; 1907e1e7763SThomas Graf 191da20420fSHerbert Xu tbl->size = size; 1927e1e7763SThomas Graf 19364e0cd0dSTom Herbert max_locks = size >> 1; 19464e0cd0dSTom Herbert if (tbl->nest) 19564e0cd0dSTom Herbert max_locks = min_t(size_t, max_locks, 1U << tbl->nest); 19664e0cd0dSTom Herbert 19764e0cd0dSTom Herbert if (alloc_bucket_spinlocks(&tbl->locks, &tbl->locks_mask, max_locks, 19864e0cd0dSTom Herbert ht->p.locks_mul, gfp) < 0) { 19997defe1eSThomas Graf bucket_table_free(tbl); 20097defe1eSThomas Graf return NULL; 2017e1e7763SThomas Graf } 2027e1e7763SThomas Graf 203eddee5baSHerbert Xu INIT_LIST_HEAD(&tbl->walkers); 204eddee5baSHerbert Xu 205d48ad080SJason A. Donenfeld tbl->hash_rnd = get_random_u32(); 2065269b53dSHerbert Xu 207f89bd6f8SThomas Graf for (i = 0; i < nbuckets; i++) 2089b4f64a2SNeilBrown INIT_RHT_NULLS_HEAD(tbl->buckets[i]); 209f89bd6f8SThomas Graf 21097defe1eSThomas Graf return tbl; 2117e1e7763SThomas Graf } 2127e1e7763SThomas Graf 213b824478bSHerbert Xu static struct bucket_table *rhashtable_last_table(struct rhashtable *ht, 214b824478bSHerbert Xu struct bucket_table *tbl) 215b824478bSHerbert Xu { 216b824478bSHerbert Xu struct bucket_table *new_tbl; 217b824478bSHerbert Xu 218b824478bSHerbert Xu do { 219b824478bSHerbert Xu new_tbl = tbl; 220b824478bSHerbert Xu tbl = rht_dereference_rcu(tbl->future_tbl, ht); 221b824478bSHerbert Xu } while (tbl); 222b824478bSHerbert Xu 223b824478bSHerbert Xu return new_tbl; 224b824478bSHerbert Xu } 225b824478bSHerbert Xu 226299e5c32SThomas Graf static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash) 227a5ec68e3SThomas Graf { 228aa34a6cbSHerbert Xu struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); 229b824478bSHerbert Xu struct bucket_table *new_tbl = rhashtable_last_table(ht, 230b824478bSHerbert Xu rht_dereference_rcu(old_tbl->future_tbl, ht)); 231da20420fSHerbert Xu struct rhash_head __rcu **pprev = rht_bucket_var(old_tbl, old_hash); 232da20420fSHerbert Xu int err = -EAGAIN; 233aa34a6cbSHerbert Xu struct rhash_head *head, *next, *entry; 234aa34a6cbSHerbert Xu spinlock_t *new_bucket_lock; 235299e5c32SThomas Graf unsigned int new_hash; 236a5ec68e3SThomas Graf 237da20420fSHerbert Xu if (new_tbl->nest) 238da20420fSHerbert Xu goto out; 239da20420fSHerbert Xu 240da20420fSHerbert Xu err = -ENOENT; 241da20420fSHerbert Xu 242aa34a6cbSHerbert Xu rht_for_each(entry, old_tbl, old_hash) { 243aa34a6cbSHerbert Xu err = 0; 244aa34a6cbSHerbert Xu next = rht_dereference_bucket(entry->next, old_tbl, old_hash); 245a5ec68e3SThomas Graf 246aa34a6cbSHerbert Xu if (rht_is_a_nulls(next)) 2477e1e7763SThomas Graf break; 24897defe1eSThomas Graf 249aa34a6cbSHerbert Xu pprev = &entry->next; 2507e1e7763SThomas Graf } 2517e1e7763SThomas Graf 252aa34a6cbSHerbert Xu if (err) 253aa34a6cbSHerbert Xu goto out; 25497defe1eSThomas Graf 255aa34a6cbSHerbert Xu new_hash = head_hashfn(ht, new_tbl, entry); 256a5ec68e3SThomas Graf 25702fd97c3SHerbert Xu new_bucket_lock = rht_bucket_lock(new_tbl, new_hash); 258aa34a6cbSHerbert Xu 2598f2484bdSHerbert Xu spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING); 260aa34a6cbSHerbert Xu head = rht_dereference_bucket(new_tbl->buckets[new_hash], 261aa34a6cbSHerbert Xu new_tbl, new_hash); 262aa34a6cbSHerbert Xu 263aa34a6cbSHerbert Xu RCU_INIT_POINTER(entry->next, head); 264aa34a6cbSHerbert Xu 265aa34a6cbSHerbert Xu rcu_assign_pointer(new_tbl->buckets[new_hash], entry); 266aa34a6cbSHerbert Xu spin_unlock(new_bucket_lock); 267aa34a6cbSHerbert Xu 268aa34a6cbSHerbert Xu rcu_assign_pointer(*pprev, next); 269aa34a6cbSHerbert Xu 270aa34a6cbSHerbert Xu out: 271aa34a6cbSHerbert Xu return err; 27297defe1eSThomas Graf } 27397defe1eSThomas Graf 274da20420fSHerbert Xu static int rhashtable_rehash_chain(struct rhashtable *ht, 275299e5c32SThomas Graf unsigned int old_hash) 27697defe1eSThomas Graf { 277aa34a6cbSHerbert Xu struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); 278aa34a6cbSHerbert Xu spinlock_t *old_bucket_lock; 279da20420fSHerbert Xu int err; 2807cd10db8SThomas Graf 28102fd97c3SHerbert Xu old_bucket_lock = rht_bucket_lock(old_tbl, old_hash); 282aa34a6cbSHerbert Xu 283aa34a6cbSHerbert Xu spin_lock_bh(old_bucket_lock); 284da20420fSHerbert Xu while (!(err = rhashtable_rehash_one(ht, old_hash))) 285aa34a6cbSHerbert Xu ; 286da20420fSHerbert Xu 287da20420fSHerbert Xu if (err == -ENOENT) { 28863d512d0SHerbert Xu old_tbl->rehash++; 289da20420fSHerbert Xu err = 0; 290da20420fSHerbert Xu } 291aa34a6cbSHerbert Xu spin_unlock_bh(old_bucket_lock); 292da20420fSHerbert Xu 293da20420fSHerbert Xu return err; 294aa34a6cbSHerbert Xu } 295aa34a6cbSHerbert Xu 296b824478bSHerbert Xu static int rhashtable_rehash_attach(struct rhashtable *ht, 297b824478bSHerbert Xu struct bucket_table *old_tbl, 298aa34a6cbSHerbert Xu struct bucket_table *new_tbl) 299aa34a6cbSHerbert Xu { 300aa34a6cbSHerbert Xu /* Make insertions go into the new, empty table right away. Deletions 301aa34a6cbSHerbert Xu * and lookups will be attempted in both tables until we synchronize. 302*0ad66449SNeilBrown * As cmpxchg() provides strong barriers, we do not need 303*0ad66449SNeilBrown * rcu_assign_pointer(). 304aa34a6cbSHerbert Xu */ 305aa34a6cbSHerbert Xu 306*0ad66449SNeilBrown if (cmpxchg(&old_tbl->future_tbl, NULL, new_tbl) != NULL) 307*0ad66449SNeilBrown return -EEXIST; 308b824478bSHerbert Xu 309b824478bSHerbert Xu return 0; 310b824478bSHerbert Xu } 311b824478bSHerbert Xu 312b824478bSHerbert Xu static int rhashtable_rehash_table(struct rhashtable *ht) 313b824478bSHerbert Xu { 314b824478bSHerbert Xu struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); 315b824478bSHerbert Xu struct bucket_table *new_tbl; 316b824478bSHerbert Xu struct rhashtable_walker *walker; 317299e5c32SThomas Graf unsigned int old_hash; 318da20420fSHerbert Xu int err; 319b824478bSHerbert Xu 320b824478bSHerbert Xu new_tbl = rht_dereference(old_tbl->future_tbl, ht); 321b824478bSHerbert Xu if (!new_tbl) 322b824478bSHerbert Xu return 0; 323b824478bSHerbert Xu 324da20420fSHerbert Xu for (old_hash = 0; old_hash < old_tbl->size; old_hash++) { 325da20420fSHerbert Xu err = rhashtable_rehash_chain(ht, old_hash); 326da20420fSHerbert Xu if (err) 327da20420fSHerbert Xu return err; 328ae6da1f5SEric Dumazet cond_resched(); 329da20420fSHerbert Xu } 330aa34a6cbSHerbert Xu 331aa34a6cbSHerbert Xu /* Publish the new table pointer. */ 332aa34a6cbSHerbert Xu rcu_assign_pointer(ht->tbl, new_tbl); 333aa34a6cbSHerbert Xu 334ba7c95eaSHerbert Xu spin_lock(&ht->lock); 335eddee5baSHerbert Xu list_for_each_entry(walker, &old_tbl->walkers, list) 336eddee5baSHerbert Xu walker->tbl = NULL; 337ba7c95eaSHerbert Xu spin_unlock(&ht->lock); 338eddee5baSHerbert Xu 339aa34a6cbSHerbert Xu /* Wait for readers. All new readers will see the new 340aa34a6cbSHerbert Xu * table, and thus no references to the old table will 341aa34a6cbSHerbert Xu * remain. 342aa34a6cbSHerbert Xu */ 3439d901bc0SHerbert Xu call_rcu(&old_tbl->rcu, bucket_table_free_rcu); 344b824478bSHerbert Xu 345b824478bSHerbert Xu return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0; 3467e1e7763SThomas Graf } 3477e1e7763SThomas Graf 348da20420fSHerbert Xu static int rhashtable_rehash_alloc(struct rhashtable *ht, 349da20420fSHerbert Xu struct bucket_table *old_tbl, 350da20420fSHerbert Xu unsigned int size) 3517e1e7763SThomas Graf { 352da20420fSHerbert Xu struct bucket_table *new_tbl; 353b824478bSHerbert Xu int err; 3547e1e7763SThomas Graf 3557e1e7763SThomas Graf ASSERT_RHT_MUTEX(ht); 3567e1e7763SThomas Graf 357da20420fSHerbert Xu new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL); 3587e1e7763SThomas Graf if (new_tbl == NULL) 3597e1e7763SThomas Graf return -ENOMEM; 3607e1e7763SThomas Graf 361b824478bSHerbert Xu err = rhashtable_rehash_attach(ht, old_tbl, new_tbl); 362b824478bSHerbert Xu if (err) 363b824478bSHerbert Xu bucket_table_free(new_tbl); 364b824478bSHerbert Xu 365b824478bSHerbert Xu return err; 3667e1e7763SThomas Graf } 3677e1e7763SThomas Graf 3687e1e7763SThomas Graf /** 3697e1e7763SThomas Graf * rhashtable_shrink - Shrink hash table while allowing concurrent lookups 3707e1e7763SThomas Graf * @ht: the hash table to shrink 3717e1e7763SThomas Graf * 37218093d1cSHerbert Xu * This function shrinks the hash table to fit, i.e., the smallest 37318093d1cSHerbert Xu * size would not cause it to expand right away automatically. 3747e1e7763SThomas Graf * 37597defe1eSThomas Graf * The caller must ensure that no concurrent resizing occurs by holding 37697defe1eSThomas Graf * ht->mutex. 37797defe1eSThomas Graf * 3787e1e7763SThomas Graf * The caller must ensure that no concurrent table mutations take place. 3797e1e7763SThomas Graf * It is however valid to have concurrent lookups if they are RCU protected. 38097defe1eSThomas Graf * 38197defe1eSThomas Graf * It is valid to have concurrent insertions and deletions protected by per 38297defe1eSThomas Graf * bucket locks or concurrent RCU protected lookups and traversals. 3837e1e7763SThomas Graf */ 384b824478bSHerbert Xu static int rhashtable_shrink(struct rhashtable *ht) 3857e1e7763SThomas Graf { 386da20420fSHerbert Xu struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); 38712311959SVegard Nossum unsigned int nelems = atomic_read(&ht->nelems); 38812311959SVegard Nossum unsigned int size = 0; 3897e1e7763SThomas Graf 39012311959SVegard Nossum if (nelems) 39112311959SVegard Nossum size = roundup_pow_of_two(nelems * 3 / 2); 39218093d1cSHerbert Xu if (size < ht->p.min_size) 39318093d1cSHerbert Xu size = ht->p.min_size; 39418093d1cSHerbert Xu 39518093d1cSHerbert Xu if (old_tbl->size <= size) 39618093d1cSHerbert Xu return 0; 39718093d1cSHerbert Xu 398b824478bSHerbert Xu if (rht_dereference(old_tbl->future_tbl, ht)) 399b824478bSHerbert Xu return -EEXIST; 400b824478bSHerbert Xu 401da20420fSHerbert Xu return rhashtable_rehash_alloc(ht, old_tbl, size); 4027e1e7763SThomas Graf } 4037e1e7763SThomas Graf 40497defe1eSThomas Graf static void rht_deferred_worker(struct work_struct *work) 40597defe1eSThomas Graf { 40697defe1eSThomas Graf struct rhashtable *ht; 40797defe1eSThomas Graf struct bucket_table *tbl; 408b824478bSHerbert Xu int err = 0; 40997defe1eSThomas Graf 41057699a40SYing Xue ht = container_of(work, struct rhashtable, run_work); 41197defe1eSThomas Graf mutex_lock(&ht->mutex); 41228134a53SHerbert Xu 41397defe1eSThomas Graf tbl = rht_dereference(ht->tbl, ht); 414b824478bSHerbert Xu tbl = rhashtable_last_table(ht, tbl); 41597defe1eSThomas Graf 416a5b6846fSDaniel Borkmann if (rht_grow_above_75(ht, tbl)) 417da20420fSHerbert Xu err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2); 418b5e2c150SThomas Graf else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl)) 419da20420fSHerbert Xu err = rhashtable_shrink(ht); 420da20420fSHerbert Xu else if (tbl->nest) 421da20420fSHerbert Xu err = rhashtable_rehash_alloc(ht, tbl, tbl->size); 422b824478bSHerbert Xu 423da20420fSHerbert Xu if (!err) 424b824478bSHerbert Xu err = rhashtable_rehash_table(ht); 425b824478bSHerbert Xu 42697defe1eSThomas Graf mutex_unlock(&ht->mutex); 427b824478bSHerbert Xu 428b824478bSHerbert Xu if (err) 429b824478bSHerbert Xu schedule_work(&ht->run_work); 43097defe1eSThomas Graf } 43197defe1eSThomas Graf 432ca26893fSHerbert Xu static int rhashtable_insert_rehash(struct rhashtable *ht, 4333cf92222SHerbert Xu struct bucket_table *tbl) 434ccd57b1bSHerbert Xu { 435ccd57b1bSHerbert Xu struct bucket_table *old_tbl; 436ccd57b1bSHerbert Xu struct bucket_table *new_tbl; 437ccd57b1bSHerbert Xu unsigned int size; 438ccd57b1bSHerbert Xu int err; 439ccd57b1bSHerbert Xu 440ccd57b1bSHerbert Xu old_tbl = rht_dereference_rcu(ht->tbl, ht); 441ccd57b1bSHerbert Xu 442ccd57b1bSHerbert Xu size = tbl->size; 443ccd57b1bSHerbert Xu 4443cf92222SHerbert Xu err = -EBUSY; 4453cf92222SHerbert Xu 446ccd57b1bSHerbert Xu if (rht_grow_above_75(ht, tbl)) 447ccd57b1bSHerbert Xu size *= 2; 448a87b9ebfSThomas Graf /* Do not schedule more than one rehash */ 449a87b9ebfSThomas Graf else if (old_tbl != tbl) 4503cf92222SHerbert Xu goto fail; 4513cf92222SHerbert Xu 4523cf92222SHerbert Xu err = -ENOMEM; 453ccd57b1bSHerbert Xu 454ccd57b1bSHerbert Xu new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC); 4553cf92222SHerbert Xu if (new_tbl == NULL) 4563cf92222SHerbert Xu goto fail; 457ccd57b1bSHerbert Xu 458ccd57b1bSHerbert Xu err = rhashtable_rehash_attach(ht, tbl, new_tbl); 459ccd57b1bSHerbert Xu if (err) { 460ccd57b1bSHerbert Xu bucket_table_free(new_tbl); 461ccd57b1bSHerbert Xu if (err == -EEXIST) 462ccd57b1bSHerbert Xu err = 0; 463ccd57b1bSHerbert Xu } else 464ccd57b1bSHerbert Xu schedule_work(&ht->run_work); 465ccd57b1bSHerbert Xu 466ccd57b1bSHerbert Xu return err; 4673cf92222SHerbert Xu 4683cf92222SHerbert Xu fail: 4693cf92222SHerbert Xu /* Do not fail the insert if someone else did a rehash. */ 4703cf92222SHerbert Xu if (likely(rcu_dereference_raw(tbl->future_tbl))) 4713cf92222SHerbert Xu return 0; 4723cf92222SHerbert Xu 4733cf92222SHerbert Xu /* Schedule async rehash to retry allocation in process context. */ 4743cf92222SHerbert Xu if (err == -ENOMEM) 4753cf92222SHerbert Xu schedule_work(&ht->run_work); 4763cf92222SHerbert Xu 4773cf92222SHerbert Xu return err; 478ccd57b1bSHerbert Xu } 479ccd57b1bSHerbert Xu 480ca26893fSHerbert Xu static void *rhashtable_lookup_one(struct rhashtable *ht, 481ca26893fSHerbert Xu struct bucket_table *tbl, unsigned int hash, 482ca26893fSHerbert Xu const void *key, struct rhash_head *obj) 48302fd97c3SHerbert Xu { 484ca26893fSHerbert Xu struct rhashtable_compare_arg arg = { 485ca26893fSHerbert Xu .ht = ht, 486ca26893fSHerbert Xu .key = key, 487ca26893fSHerbert Xu }; 488ca26893fSHerbert Xu struct rhash_head __rcu **pprev; 48902fd97c3SHerbert Xu struct rhash_head *head; 490ca26893fSHerbert Xu int elasticity; 49102fd97c3SHerbert Xu 4925f8ddeabSFlorian Westphal elasticity = RHT_ELASTICITY; 493da20420fSHerbert Xu pprev = rht_bucket_var(tbl, hash); 494da20420fSHerbert Xu rht_for_each_continue(head, *pprev, tbl, hash) { 495ca26893fSHerbert Xu struct rhlist_head *list; 496ca26893fSHerbert Xu struct rhlist_head *plist; 49702fd97c3SHerbert Xu 498ca26893fSHerbert Xu elasticity--; 499ca26893fSHerbert Xu if (!key || 500ca26893fSHerbert Xu (ht->p.obj_cmpfn ? 501ca26893fSHerbert Xu ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) : 502d3dcf8ebSPaul Blakey rhashtable_compare(&arg, rht_obj(ht, head)))) { 503d3dcf8ebSPaul Blakey pprev = &head->next; 504ca26893fSHerbert Xu continue; 505d3dcf8ebSPaul Blakey } 506ca26893fSHerbert Xu 507ca26893fSHerbert Xu if (!ht->rhlist) 508ca26893fSHerbert Xu return rht_obj(ht, head); 509ca26893fSHerbert Xu 510ca26893fSHerbert Xu list = container_of(obj, struct rhlist_head, rhead); 511ca26893fSHerbert Xu plist = container_of(head, struct rhlist_head, rhead); 512ca26893fSHerbert Xu 513ca26893fSHerbert Xu RCU_INIT_POINTER(list->next, plist); 514ca26893fSHerbert Xu head = rht_dereference_bucket(head->next, tbl, hash); 515ca26893fSHerbert Xu RCU_INIT_POINTER(list->rhead.next, head); 516ca26893fSHerbert Xu rcu_assign_pointer(*pprev, obj); 517ca26893fSHerbert Xu 518ca26893fSHerbert Xu return NULL; 5195ca8cc5bSPablo Neira Ayuso } 52002fd97c3SHerbert Xu 521ca26893fSHerbert Xu if (elasticity <= 0) 522ca26893fSHerbert Xu return ERR_PTR(-EAGAIN); 523ca26893fSHerbert Xu 524ca26893fSHerbert Xu return ERR_PTR(-ENOENT); 525ca26893fSHerbert Xu } 526ca26893fSHerbert Xu 527ca26893fSHerbert Xu static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht, 528ca26893fSHerbert Xu struct bucket_table *tbl, 529ca26893fSHerbert Xu unsigned int hash, 530ca26893fSHerbert Xu struct rhash_head *obj, 531ca26893fSHerbert Xu void *data) 532ca26893fSHerbert Xu { 533da20420fSHerbert Xu struct rhash_head __rcu **pprev; 534ca26893fSHerbert Xu struct bucket_table *new_tbl; 535ca26893fSHerbert Xu struct rhash_head *head; 536ca26893fSHerbert Xu 537ca26893fSHerbert Xu if (!IS_ERR_OR_NULL(data)) 538ca26893fSHerbert Xu return ERR_PTR(-EEXIST); 539ca26893fSHerbert Xu 540ca26893fSHerbert Xu if (PTR_ERR(data) != -EAGAIN && PTR_ERR(data) != -ENOENT) 541ca26893fSHerbert Xu return ERR_CAST(data); 542ca26893fSHerbert Xu 543ca26893fSHerbert Xu new_tbl = rcu_dereference(tbl->future_tbl); 544ca26893fSHerbert Xu if (new_tbl) 545ca26893fSHerbert Xu return new_tbl; 546ca26893fSHerbert Xu 547ca26893fSHerbert Xu if (PTR_ERR(data) != -ENOENT) 548ca26893fSHerbert Xu return ERR_CAST(data); 549ca26893fSHerbert Xu 55007ee0722SHerbert Xu if (unlikely(rht_grow_above_max(ht, tbl))) 551ca26893fSHerbert Xu return ERR_PTR(-E2BIG); 55207ee0722SHerbert Xu 553ca26893fSHerbert Xu if (unlikely(rht_grow_above_100(ht, tbl))) 554ca26893fSHerbert Xu return ERR_PTR(-EAGAIN); 55502fd97c3SHerbert Xu 556da20420fSHerbert Xu pprev = rht_bucket_insert(ht, tbl, hash); 557da20420fSHerbert Xu if (!pprev) 558da20420fSHerbert Xu return ERR_PTR(-ENOMEM); 559da20420fSHerbert Xu 560da20420fSHerbert Xu head = rht_dereference_bucket(*pprev, tbl, hash); 56102fd97c3SHerbert Xu 56202fd97c3SHerbert Xu RCU_INIT_POINTER(obj->next, head); 563ca26893fSHerbert Xu if (ht->rhlist) { 564ca26893fSHerbert Xu struct rhlist_head *list; 565ca26893fSHerbert Xu 566ca26893fSHerbert Xu list = container_of(obj, struct rhlist_head, rhead); 567ca26893fSHerbert Xu RCU_INIT_POINTER(list->next, NULL); 568ca26893fSHerbert Xu } 56902fd97c3SHerbert Xu 570da20420fSHerbert Xu rcu_assign_pointer(*pprev, obj); 57102fd97c3SHerbert Xu 57202fd97c3SHerbert Xu atomic_inc(&ht->nelems); 573ca26893fSHerbert Xu if (rht_grow_above_75(ht, tbl)) 574ca26893fSHerbert Xu schedule_work(&ht->run_work); 57502fd97c3SHerbert Xu 5763cf92222SHerbert Xu return NULL; 577ca26893fSHerbert Xu } 578ca26893fSHerbert Xu 579ca26893fSHerbert Xu static void *rhashtable_try_insert(struct rhashtable *ht, const void *key, 580ca26893fSHerbert Xu struct rhash_head *obj) 581ca26893fSHerbert Xu { 582ca26893fSHerbert Xu struct bucket_table *new_tbl; 583ca26893fSHerbert Xu struct bucket_table *tbl; 584ca26893fSHerbert Xu unsigned int hash; 585ca26893fSHerbert Xu spinlock_t *lock; 586ca26893fSHerbert Xu void *data; 587ca26893fSHerbert Xu 588ca26893fSHerbert Xu tbl = rcu_dereference(ht->tbl); 589ca26893fSHerbert Xu 590ca26893fSHerbert Xu /* All insertions must grab the oldest table containing 591ca26893fSHerbert Xu * the hashed bucket that is yet to be rehashed. 592ca26893fSHerbert Xu */ 593ca26893fSHerbert Xu for (;;) { 594ca26893fSHerbert Xu hash = rht_head_hashfn(ht, tbl, obj, ht->p); 595ca26893fSHerbert Xu lock = rht_bucket_lock(tbl, hash); 596ca26893fSHerbert Xu spin_lock_bh(lock); 597ca26893fSHerbert Xu 598ca26893fSHerbert Xu if (tbl->rehash <= hash) 599ca26893fSHerbert Xu break; 600ca26893fSHerbert Xu 601ca26893fSHerbert Xu spin_unlock_bh(lock); 602ca26893fSHerbert Xu tbl = rcu_dereference(tbl->future_tbl); 603ca26893fSHerbert Xu } 604ca26893fSHerbert Xu 605ca26893fSHerbert Xu data = rhashtable_lookup_one(ht, tbl, hash, key, obj); 606ca26893fSHerbert Xu new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data); 607ca26893fSHerbert Xu if (PTR_ERR(new_tbl) != -EEXIST) 608ca26893fSHerbert Xu data = ERR_CAST(new_tbl); 609ca26893fSHerbert Xu 610ca26893fSHerbert Xu while (!IS_ERR_OR_NULL(new_tbl)) { 611ca26893fSHerbert Xu tbl = new_tbl; 612ca26893fSHerbert Xu hash = rht_head_hashfn(ht, tbl, obj, ht->p); 613ca26893fSHerbert Xu spin_lock_nested(rht_bucket_lock(tbl, hash), 614ca26893fSHerbert Xu SINGLE_DEPTH_NESTING); 615ca26893fSHerbert Xu 616ca26893fSHerbert Xu data = rhashtable_lookup_one(ht, tbl, hash, key, obj); 617ca26893fSHerbert Xu new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data); 618ca26893fSHerbert Xu if (PTR_ERR(new_tbl) != -EEXIST) 619ca26893fSHerbert Xu data = ERR_CAST(new_tbl); 620ca26893fSHerbert Xu 621ca26893fSHerbert Xu spin_unlock(rht_bucket_lock(tbl, hash)); 622ca26893fSHerbert Xu } 623ca26893fSHerbert Xu 624ca26893fSHerbert Xu spin_unlock_bh(lock); 625ca26893fSHerbert Xu 626ca26893fSHerbert Xu if (PTR_ERR(data) == -EAGAIN) 627ca26893fSHerbert Xu data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?: 628ca26893fSHerbert Xu -EAGAIN); 629ca26893fSHerbert Xu 630ca26893fSHerbert Xu return data; 631ca26893fSHerbert Xu } 632ca26893fSHerbert Xu 633ca26893fSHerbert Xu void *rhashtable_insert_slow(struct rhashtable *ht, const void *key, 634ca26893fSHerbert Xu struct rhash_head *obj) 635ca26893fSHerbert Xu { 636ca26893fSHerbert Xu void *data; 637ca26893fSHerbert Xu 638ca26893fSHerbert Xu do { 639ca26893fSHerbert Xu rcu_read_lock(); 640ca26893fSHerbert Xu data = rhashtable_try_insert(ht, key, obj); 641ca26893fSHerbert Xu rcu_read_unlock(); 642ca26893fSHerbert Xu } while (PTR_ERR(data) == -EAGAIN); 643ca26893fSHerbert Xu 644ca26893fSHerbert Xu return data; 64502fd97c3SHerbert Xu } 64602fd97c3SHerbert Xu EXPORT_SYMBOL_GPL(rhashtable_insert_slow); 64702fd97c3SHerbert Xu 648f2dba9c6SHerbert Xu /** 649246779ddSHerbert Xu * rhashtable_walk_enter - Initialise an iterator 650f2dba9c6SHerbert Xu * @ht: Table to walk over 651f2dba9c6SHerbert Xu * @iter: Hash table Iterator 652f2dba9c6SHerbert Xu * 653f2dba9c6SHerbert Xu * This function prepares a hash table walk. 654f2dba9c6SHerbert Xu * 655f2dba9c6SHerbert Xu * Note that if you restart a walk after rhashtable_walk_stop you 656f2dba9c6SHerbert Xu * may see the same object twice. Also, you may miss objects if 657f2dba9c6SHerbert Xu * there are removals in between rhashtable_walk_stop and the next 658f2dba9c6SHerbert Xu * call to rhashtable_walk_start. 659f2dba9c6SHerbert Xu * 660f2dba9c6SHerbert Xu * For a completely stable walk you should construct your own data 661f2dba9c6SHerbert Xu * structure outside the hash table. 662f2dba9c6SHerbert Xu * 66382266e98SNeilBrown * This function may be called from any process context, including 66482266e98SNeilBrown * non-preemptable context, but cannot be called from softirq or 66582266e98SNeilBrown * hardirq context. 666f2dba9c6SHerbert Xu * 667246779ddSHerbert Xu * You must call rhashtable_walk_exit after this function returns. 668f2dba9c6SHerbert Xu */ 669246779ddSHerbert Xu void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter) 670f2dba9c6SHerbert Xu { 671f2dba9c6SHerbert Xu iter->ht = ht; 672f2dba9c6SHerbert Xu iter->p = NULL; 673f2dba9c6SHerbert Xu iter->slot = 0; 674f2dba9c6SHerbert Xu iter->skip = 0; 6752db54b47STom Herbert iter->end_of_table = 0; 676f2dba9c6SHerbert Xu 677c6ff5268SHerbert Xu spin_lock(&ht->lock); 678246779ddSHerbert Xu iter->walker.tbl = 679179ccc0aSHerbert Xu rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock)); 680246779ddSHerbert Xu list_add(&iter->walker.list, &iter->walker.tbl->walkers); 681c6ff5268SHerbert Xu spin_unlock(&ht->lock); 682f2dba9c6SHerbert Xu } 683246779ddSHerbert Xu EXPORT_SYMBOL_GPL(rhashtable_walk_enter); 684f2dba9c6SHerbert Xu 685f2dba9c6SHerbert Xu /** 686f2dba9c6SHerbert Xu * rhashtable_walk_exit - Free an iterator 687f2dba9c6SHerbert Xu * @iter: Hash table Iterator 688f2dba9c6SHerbert Xu * 689f2dba9c6SHerbert Xu * This function frees resources allocated by rhashtable_walk_init. 690f2dba9c6SHerbert Xu */ 691f2dba9c6SHerbert Xu void rhashtable_walk_exit(struct rhashtable_iter *iter) 692f2dba9c6SHerbert Xu { 693c6ff5268SHerbert Xu spin_lock(&iter->ht->lock); 694246779ddSHerbert Xu if (iter->walker.tbl) 695246779ddSHerbert Xu list_del(&iter->walker.list); 696c6ff5268SHerbert Xu spin_unlock(&iter->ht->lock); 697f2dba9c6SHerbert Xu } 698f2dba9c6SHerbert Xu EXPORT_SYMBOL_GPL(rhashtable_walk_exit); 699f2dba9c6SHerbert Xu 700f2dba9c6SHerbert Xu /** 70197a6ec4aSTom Herbert * rhashtable_walk_start_check - Start a hash table walk 702f2dba9c6SHerbert Xu * @iter: Hash table iterator 703f2dba9c6SHerbert Xu * 7040647169cSAndreas Gruenbacher * Start a hash table walk at the current iterator position. Note that we take 7050647169cSAndreas Gruenbacher * the RCU lock in all cases including when we return an error. So you must 7060647169cSAndreas Gruenbacher * always call rhashtable_walk_stop to clean up. 707f2dba9c6SHerbert Xu * 708f2dba9c6SHerbert Xu * Returns zero if successful. 709f2dba9c6SHerbert Xu * 710f2dba9c6SHerbert Xu * Returns -EAGAIN if resize event occured. Note that the iterator 711f2dba9c6SHerbert Xu * will rewind back to the beginning and you may use it immediately 712f2dba9c6SHerbert Xu * by calling rhashtable_walk_next. 71397a6ec4aSTom Herbert * 71497a6ec4aSTom Herbert * rhashtable_walk_start is defined as an inline variant that returns 71597a6ec4aSTom Herbert * void. This is preferred in cases where the caller would ignore 71697a6ec4aSTom Herbert * resize events and always continue. 717f2dba9c6SHerbert Xu */ 71897a6ec4aSTom Herbert int rhashtable_walk_start_check(struct rhashtable_iter *iter) 719db4374f4SThomas Graf __acquires(RCU) 720f2dba9c6SHerbert Xu { 721eddee5baSHerbert Xu struct rhashtable *ht = iter->ht; 7225d240a89SNeilBrown bool rhlist = ht->rhlist; 723eddee5baSHerbert Xu 724f2dba9c6SHerbert Xu rcu_read_lock(); 725f2dba9c6SHerbert Xu 726c6ff5268SHerbert Xu spin_lock(&ht->lock); 727246779ddSHerbert Xu if (iter->walker.tbl) 728246779ddSHerbert Xu list_del(&iter->walker.list); 729c6ff5268SHerbert Xu spin_unlock(&ht->lock); 730eddee5baSHerbert Xu 7315d240a89SNeilBrown if (iter->end_of_table) 7325d240a89SNeilBrown return 0; 7335d240a89SNeilBrown if (!iter->walker.tbl) { 734246779ddSHerbert Xu iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht); 735b41cc04bSNeilBrown iter->slot = 0; 736b41cc04bSNeilBrown iter->skip = 0; 737f2dba9c6SHerbert Xu return -EAGAIN; 738f2dba9c6SHerbert Xu } 739f2dba9c6SHerbert Xu 7405d240a89SNeilBrown if (iter->p && !rhlist) { 7415d240a89SNeilBrown /* 7425d240a89SNeilBrown * We need to validate that 'p' is still in the table, and 7435d240a89SNeilBrown * if so, update 'skip' 7445d240a89SNeilBrown */ 7455d240a89SNeilBrown struct rhash_head *p; 7465d240a89SNeilBrown int skip = 0; 7475d240a89SNeilBrown rht_for_each_rcu(p, iter->walker.tbl, iter->slot) { 7485d240a89SNeilBrown skip++; 7495d240a89SNeilBrown if (p == iter->p) { 7505d240a89SNeilBrown iter->skip = skip; 7515d240a89SNeilBrown goto found; 7525d240a89SNeilBrown } 7535d240a89SNeilBrown } 7545d240a89SNeilBrown iter->p = NULL; 7555d240a89SNeilBrown } else if (iter->p && rhlist) { 7565d240a89SNeilBrown /* Need to validate that 'list' is still in the table, and 7575d240a89SNeilBrown * if so, update 'skip' and 'p'. 7585d240a89SNeilBrown */ 7595d240a89SNeilBrown struct rhash_head *p; 7605d240a89SNeilBrown struct rhlist_head *list; 7615d240a89SNeilBrown int skip = 0; 7625d240a89SNeilBrown rht_for_each_rcu(p, iter->walker.tbl, iter->slot) { 7635d240a89SNeilBrown for (list = container_of(p, struct rhlist_head, rhead); 7645d240a89SNeilBrown list; 7655d240a89SNeilBrown list = rcu_dereference(list->next)) { 7665d240a89SNeilBrown skip++; 7675d240a89SNeilBrown if (list == iter->list) { 7685d240a89SNeilBrown iter->p = p; 7695d240a89SNeilBrown skip = skip; 7705d240a89SNeilBrown goto found; 7715d240a89SNeilBrown } 7725d240a89SNeilBrown } 7735d240a89SNeilBrown } 7745d240a89SNeilBrown iter->p = NULL; 7755d240a89SNeilBrown } 7765d240a89SNeilBrown found: 777f2dba9c6SHerbert Xu return 0; 778f2dba9c6SHerbert Xu } 77997a6ec4aSTom Herbert EXPORT_SYMBOL_GPL(rhashtable_walk_start_check); 780f2dba9c6SHerbert Xu 781f2dba9c6SHerbert Xu /** 7822db54b47STom Herbert * __rhashtable_walk_find_next - Find the next element in a table (or the first 7832db54b47STom Herbert * one in case of a new walk). 7842db54b47STom Herbert * 785f2dba9c6SHerbert Xu * @iter: Hash table iterator 786f2dba9c6SHerbert Xu * 7872db54b47STom Herbert * Returns the found object or NULL when the end of the table is reached. 788f2dba9c6SHerbert Xu * 7892db54b47STom Herbert * Returns -EAGAIN if resize event occurred. 790f2dba9c6SHerbert Xu */ 7912db54b47STom Herbert static void *__rhashtable_walk_find_next(struct rhashtable_iter *iter) 792f2dba9c6SHerbert Xu { 793246779ddSHerbert Xu struct bucket_table *tbl = iter->walker.tbl; 794ca26893fSHerbert Xu struct rhlist_head *list = iter->list; 795f2dba9c6SHerbert Xu struct rhashtable *ht = iter->ht; 796f2dba9c6SHerbert Xu struct rhash_head *p = iter->p; 797ca26893fSHerbert Xu bool rhlist = ht->rhlist; 798f2dba9c6SHerbert Xu 7992db54b47STom Herbert if (!tbl) 8002db54b47STom Herbert return NULL; 801f2dba9c6SHerbert Xu 802f2dba9c6SHerbert Xu for (; iter->slot < tbl->size; iter->slot++) { 803f2dba9c6SHerbert Xu int skip = iter->skip; 804f2dba9c6SHerbert Xu 805f2dba9c6SHerbert Xu rht_for_each_rcu(p, tbl, iter->slot) { 806ca26893fSHerbert Xu if (rhlist) { 807ca26893fSHerbert Xu list = container_of(p, struct rhlist_head, 808ca26893fSHerbert Xu rhead); 809ca26893fSHerbert Xu do { 810ca26893fSHerbert Xu if (!skip) 811ca26893fSHerbert Xu goto next; 812ca26893fSHerbert Xu skip--; 813ca26893fSHerbert Xu list = rcu_dereference(list->next); 814ca26893fSHerbert Xu } while (list); 815ca26893fSHerbert Xu 816ca26893fSHerbert Xu continue; 817ca26893fSHerbert Xu } 818f2dba9c6SHerbert Xu if (!skip) 819f2dba9c6SHerbert Xu break; 820f2dba9c6SHerbert Xu skip--; 821f2dba9c6SHerbert Xu } 822f2dba9c6SHerbert Xu 823f2dba9c6SHerbert Xu next: 824f2dba9c6SHerbert Xu if (!rht_is_a_nulls(p)) { 825f2dba9c6SHerbert Xu iter->skip++; 826f2dba9c6SHerbert Xu iter->p = p; 827ca26893fSHerbert Xu iter->list = list; 828ca26893fSHerbert Xu return rht_obj(ht, rhlist ? &list->rhead : p); 829f2dba9c6SHerbert Xu } 830f2dba9c6SHerbert Xu 831f2dba9c6SHerbert Xu iter->skip = 0; 832f2dba9c6SHerbert Xu } 833f2dba9c6SHerbert Xu 834142b942aSPhil Sutter iter->p = NULL; 835142b942aSPhil Sutter 836d88252f9SHerbert Xu /* Ensure we see any new tables. */ 837d88252f9SHerbert Xu smp_rmb(); 838d88252f9SHerbert Xu 839246779ddSHerbert Xu iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht); 840246779ddSHerbert Xu if (iter->walker.tbl) { 841eddee5baSHerbert Xu iter->slot = 0; 842eddee5baSHerbert Xu iter->skip = 0; 843eddee5baSHerbert Xu return ERR_PTR(-EAGAIN); 8442db54b47STom Herbert } else { 8452db54b47STom Herbert iter->end_of_table = true; 846eddee5baSHerbert Xu } 847eddee5baSHerbert Xu 848c936a79fSThomas Graf return NULL; 849f2dba9c6SHerbert Xu } 8502db54b47STom Herbert 8512db54b47STom Herbert /** 8522db54b47STom Herbert * rhashtable_walk_next - Return the next object and advance the iterator 8532db54b47STom Herbert * @iter: Hash table iterator 8542db54b47STom Herbert * 8552db54b47STom Herbert * Note that you must call rhashtable_walk_stop when you are finished 8562db54b47STom Herbert * with the walk. 8572db54b47STom Herbert * 8582db54b47STom Herbert * Returns the next object or NULL when the end of the table is reached. 8592db54b47STom Herbert * 8602db54b47STom Herbert * Returns -EAGAIN if resize event occurred. Note that the iterator 8612db54b47STom Herbert * will rewind back to the beginning and you may continue to use it. 8622db54b47STom Herbert */ 8632db54b47STom Herbert void *rhashtable_walk_next(struct rhashtable_iter *iter) 8642db54b47STom Herbert { 8652db54b47STom Herbert struct rhlist_head *list = iter->list; 8662db54b47STom Herbert struct rhashtable *ht = iter->ht; 8672db54b47STom Herbert struct rhash_head *p = iter->p; 8682db54b47STom Herbert bool rhlist = ht->rhlist; 8692db54b47STom Herbert 8702db54b47STom Herbert if (p) { 8712db54b47STom Herbert if (!rhlist || !(list = rcu_dereference(list->next))) { 8722db54b47STom Herbert p = rcu_dereference(p->next); 8732db54b47STom Herbert list = container_of(p, struct rhlist_head, rhead); 8742db54b47STom Herbert } 8752db54b47STom Herbert if (!rht_is_a_nulls(p)) { 8762db54b47STom Herbert iter->skip++; 8772db54b47STom Herbert iter->p = p; 8782db54b47STom Herbert iter->list = list; 8792db54b47STom Herbert return rht_obj(ht, rhlist ? &list->rhead : p); 8802db54b47STom Herbert } 8812db54b47STom Herbert 8822db54b47STom Herbert /* At the end of this slot, switch to next one and then find 8832db54b47STom Herbert * next entry from that point. 8842db54b47STom Herbert */ 8852db54b47STom Herbert iter->skip = 0; 8862db54b47STom Herbert iter->slot++; 8872db54b47STom Herbert } 8882db54b47STom Herbert 8892db54b47STom Herbert return __rhashtable_walk_find_next(iter); 8902db54b47STom Herbert } 891f2dba9c6SHerbert Xu EXPORT_SYMBOL_GPL(rhashtable_walk_next); 892f2dba9c6SHerbert Xu 893f2dba9c6SHerbert Xu /** 8942db54b47STom Herbert * rhashtable_walk_peek - Return the next object but don't advance the iterator 8952db54b47STom Herbert * @iter: Hash table iterator 8962db54b47STom Herbert * 8972db54b47STom Herbert * Returns the next object or NULL when the end of the table is reached. 8982db54b47STom Herbert * 8992db54b47STom Herbert * Returns -EAGAIN if resize event occurred. Note that the iterator 9002db54b47STom Herbert * will rewind back to the beginning and you may continue to use it. 9012db54b47STom Herbert */ 9022db54b47STom Herbert void *rhashtable_walk_peek(struct rhashtable_iter *iter) 9032db54b47STom Herbert { 9042db54b47STom Herbert struct rhlist_head *list = iter->list; 9052db54b47STom Herbert struct rhashtable *ht = iter->ht; 9062db54b47STom Herbert struct rhash_head *p = iter->p; 9072db54b47STom Herbert 9082db54b47STom Herbert if (p) 9092db54b47STom Herbert return rht_obj(ht, ht->rhlist ? &list->rhead : p); 9102db54b47STom Herbert 9112db54b47STom Herbert /* No object found in current iter, find next one in the table. */ 9122db54b47STom Herbert 9132db54b47STom Herbert if (iter->skip) { 9142db54b47STom Herbert /* A nonzero skip value points to the next entry in the table 9152db54b47STom Herbert * beyond that last one that was found. Decrement skip so 9162db54b47STom Herbert * we find the current value. __rhashtable_walk_find_next 9172db54b47STom Herbert * will restore the original value of skip assuming that 9182db54b47STom Herbert * the table hasn't changed. 9192db54b47STom Herbert */ 9202db54b47STom Herbert iter->skip--; 9212db54b47STom Herbert } 9222db54b47STom Herbert 9232db54b47STom Herbert return __rhashtable_walk_find_next(iter); 9242db54b47STom Herbert } 9252db54b47STom Herbert EXPORT_SYMBOL_GPL(rhashtable_walk_peek); 9262db54b47STom Herbert 9272db54b47STom Herbert /** 928f2dba9c6SHerbert Xu * rhashtable_walk_stop - Finish a hash table walk 929f2dba9c6SHerbert Xu * @iter: Hash table iterator 930f2dba9c6SHerbert Xu * 9310647169cSAndreas Gruenbacher * Finish a hash table walk. Does not reset the iterator to the start of the 9320647169cSAndreas Gruenbacher * hash table. 933f2dba9c6SHerbert Xu */ 934f2dba9c6SHerbert Xu void rhashtable_walk_stop(struct rhashtable_iter *iter) 935db4374f4SThomas Graf __releases(RCU) 936f2dba9c6SHerbert Xu { 937eddee5baSHerbert Xu struct rhashtable *ht; 938246779ddSHerbert Xu struct bucket_table *tbl = iter->walker.tbl; 939eddee5baSHerbert Xu 940eddee5baSHerbert Xu if (!tbl) 941963ecbd4SHerbert Xu goto out; 942eddee5baSHerbert Xu 943eddee5baSHerbert Xu ht = iter->ht; 944eddee5baSHerbert Xu 945ba7c95eaSHerbert Xu spin_lock(&ht->lock); 946c4db8848SHerbert Xu if (tbl->rehash < tbl->size) 947246779ddSHerbert Xu list_add(&iter->walker.list, &tbl->walkers); 948eddee5baSHerbert Xu else 949246779ddSHerbert Xu iter->walker.tbl = NULL; 950ba7c95eaSHerbert Xu spin_unlock(&ht->lock); 951eddee5baSHerbert Xu 952963ecbd4SHerbert Xu out: 953963ecbd4SHerbert Xu rcu_read_unlock(); 954f2dba9c6SHerbert Xu } 955f2dba9c6SHerbert Xu EXPORT_SYMBOL_GPL(rhashtable_walk_stop); 956f2dba9c6SHerbert Xu 957488fb86eSHerbert Xu static size_t rounded_hashtable_size(const struct rhashtable_params *params) 9587e1e7763SThomas Graf { 95994000176SYing Xue return max(roundup_pow_of_two(params->nelem_hint * 4 / 3), 960e2e21c1cSHerbert Xu (unsigned long)params->min_size); 9617e1e7763SThomas Graf } 9627e1e7763SThomas Graf 96331ccde2dSHerbert Xu static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed) 96431ccde2dSHerbert Xu { 96531ccde2dSHerbert Xu return jhash2(key, length, seed); 96631ccde2dSHerbert Xu } 96731ccde2dSHerbert Xu 9687e1e7763SThomas Graf /** 9697e1e7763SThomas Graf * rhashtable_init - initialize a new hash table 9707e1e7763SThomas Graf * @ht: hash table to be initialized 9717e1e7763SThomas Graf * @params: configuration parameters 9727e1e7763SThomas Graf * 9737e1e7763SThomas Graf * Initializes a new hash table based on the provided configuration 9747e1e7763SThomas Graf * parameters. A table can be configured either with a variable or 9757e1e7763SThomas Graf * fixed length key: 9767e1e7763SThomas Graf * 9777e1e7763SThomas Graf * Configuration Example 1: Fixed length keys 9787e1e7763SThomas Graf * struct test_obj { 9797e1e7763SThomas Graf * int key; 9807e1e7763SThomas Graf * void * my_member; 9817e1e7763SThomas Graf * struct rhash_head node; 9827e1e7763SThomas Graf * }; 9837e1e7763SThomas Graf * 9847e1e7763SThomas Graf * struct rhashtable_params params = { 9857e1e7763SThomas Graf * .head_offset = offsetof(struct test_obj, node), 9867e1e7763SThomas Graf * .key_offset = offsetof(struct test_obj, key), 9877e1e7763SThomas Graf * .key_len = sizeof(int), 98887545899SDaniel Borkmann * .hashfn = jhash, 9897e1e7763SThomas Graf * }; 9907e1e7763SThomas Graf * 9917e1e7763SThomas Graf * Configuration Example 2: Variable length keys 9927e1e7763SThomas Graf * struct test_obj { 9937e1e7763SThomas Graf * [...] 9947e1e7763SThomas Graf * struct rhash_head node; 9957e1e7763SThomas Graf * }; 9967e1e7763SThomas Graf * 99749f7b33eSPatrick McHardy * u32 my_hash_fn(const void *data, u32 len, u32 seed) 9987e1e7763SThomas Graf * { 9997e1e7763SThomas Graf * struct test_obj *obj = data; 10007e1e7763SThomas Graf * 10017e1e7763SThomas Graf * return [... hash ...]; 10027e1e7763SThomas Graf * } 10037e1e7763SThomas Graf * 10047e1e7763SThomas Graf * struct rhashtable_params params = { 10057e1e7763SThomas Graf * .head_offset = offsetof(struct test_obj, node), 100687545899SDaniel Borkmann * .hashfn = jhash, 10077e1e7763SThomas Graf * .obj_hashfn = my_hash_fn, 10087e1e7763SThomas Graf * }; 10097e1e7763SThomas Graf */ 1010488fb86eSHerbert Xu int rhashtable_init(struct rhashtable *ht, 1011488fb86eSHerbert Xu const struct rhashtable_params *params) 10127e1e7763SThomas Graf { 10137e1e7763SThomas Graf struct bucket_table *tbl; 10147e1e7763SThomas Graf size_t size; 10157e1e7763SThomas Graf 10167e1e7763SThomas Graf size = HASH_DEFAULT_SIZE; 10177e1e7763SThomas Graf 101831ccde2dSHerbert Xu if ((!params->key_len && !params->obj_hashfn) || 101902fd97c3SHerbert Xu (params->obj_hashfn && !params->obj_cmpfn)) 10207e1e7763SThomas Graf return -EINVAL; 10217e1e7763SThomas Graf 102297defe1eSThomas Graf memset(ht, 0, sizeof(*ht)); 102397defe1eSThomas Graf mutex_init(&ht->mutex); 1024ba7c95eaSHerbert Xu spin_lock_init(&ht->lock); 102597defe1eSThomas Graf memcpy(&ht->p, params, sizeof(*params)); 102697defe1eSThomas Graf 1027a998f712SThomas Graf if (params->min_size) 1028a998f712SThomas Graf ht->p.min_size = roundup_pow_of_two(params->min_size); 1029a998f712SThomas Graf 10306d684e54SHerbert Xu /* Cap total entries at 2^31 to avoid nelems overflow. */ 10316d684e54SHerbert Xu ht->max_elems = 1u << 31; 10322d2ab658SHerbert Xu 10332d2ab658SHerbert Xu if (params->max_size) { 10342d2ab658SHerbert Xu ht->p.max_size = rounddown_pow_of_two(params->max_size); 10356d684e54SHerbert Xu if (ht->p.max_size < ht->max_elems / 2) 10366d684e54SHerbert Xu ht->max_elems = ht->p.max_size * 2; 10372d2ab658SHerbert Xu } 10386d684e54SHerbert Xu 103948e75b43SFlorian Westphal ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE); 1040a998f712SThomas Graf 10413a324606SHerbert Xu if (params->nelem_hint) 10423a324606SHerbert Xu size = rounded_hashtable_size(&ht->p); 10433a324606SHerbert Xu 104497defe1eSThomas Graf if (params->locks_mul) 104597defe1eSThomas Graf ht->p.locks_mul = roundup_pow_of_two(params->locks_mul); 104697defe1eSThomas Graf else 104797defe1eSThomas Graf ht->p.locks_mul = BUCKET_LOCKS_PER_CPU; 104897defe1eSThomas Graf 104931ccde2dSHerbert Xu ht->key_len = ht->p.key_len; 105031ccde2dSHerbert Xu if (!params->hashfn) { 105131ccde2dSHerbert Xu ht->p.hashfn = jhash; 105231ccde2dSHerbert Xu 105331ccde2dSHerbert Xu if (!(ht->key_len & (sizeof(u32) - 1))) { 105431ccde2dSHerbert Xu ht->key_len /= sizeof(u32); 105531ccde2dSHerbert Xu ht->p.hashfn = rhashtable_jhash2; 105631ccde2dSHerbert Xu } 105731ccde2dSHerbert Xu } 105831ccde2dSHerbert Xu 1059b9ecfdaaSHerbert Xu tbl = bucket_table_alloc(ht, size, GFP_KERNEL); 10607e1e7763SThomas Graf if (tbl == NULL) 10617e1e7763SThomas Graf return -ENOMEM; 10627e1e7763SThomas Graf 1063545a148eSYing Xue atomic_set(&ht->nelems, 0); 1064a5b6846fSDaniel Borkmann 10657e1e7763SThomas Graf RCU_INIT_POINTER(ht->tbl, tbl); 10667e1e7763SThomas Graf 106757699a40SYing Xue INIT_WORK(&ht->run_work, rht_deferred_worker); 106897defe1eSThomas Graf 10697e1e7763SThomas Graf return 0; 10707e1e7763SThomas Graf } 10717e1e7763SThomas Graf EXPORT_SYMBOL_GPL(rhashtable_init); 10727e1e7763SThomas Graf 10737e1e7763SThomas Graf /** 1074ca26893fSHerbert Xu * rhltable_init - initialize a new hash list table 1075ca26893fSHerbert Xu * @hlt: hash list table to be initialized 1076ca26893fSHerbert Xu * @params: configuration parameters 1077ca26893fSHerbert Xu * 1078ca26893fSHerbert Xu * Initializes a new hash list table. 1079ca26893fSHerbert Xu * 1080ca26893fSHerbert Xu * See documentation for rhashtable_init. 1081ca26893fSHerbert Xu */ 1082ca26893fSHerbert Xu int rhltable_init(struct rhltable *hlt, const struct rhashtable_params *params) 1083ca26893fSHerbert Xu { 1084ca26893fSHerbert Xu int err; 1085ca26893fSHerbert Xu 1086ca26893fSHerbert Xu err = rhashtable_init(&hlt->ht, params); 1087ca26893fSHerbert Xu hlt->ht.rhlist = true; 1088ca26893fSHerbert Xu return err; 1089ca26893fSHerbert Xu } 1090ca26893fSHerbert Xu EXPORT_SYMBOL_GPL(rhltable_init); 1091ca26893fSHerbert Xu 1092ca26893fSHerbert Xu static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj, 1093ca26893fSHerbert Xu void (*free_fn)(void *ptr, void *arg), 1094ca26893fSHerbert Xu void *arg) 1095ca26893fSHerbert Xu { 1096ca26893fSHerbert Xu struct rhlist_head *list; 1097ca26893fSHerbert Xu 1098ca26893fSHerbert Xu if (!ht->rhlist) { 1099ca26893fSHerbert Xu free_fn(rht_obj(ht, obj), arg); 1100ca26893fSHerbert Xu return; 1101ca26893fSHerbert Xu } 1102ca26893fSHerbert Xu 1103ca26893fSHerbert Xu list = container_of(obj, struct rhlist_head, rhead); 1104ca26893fSHerbert Xu do { 1105ca26893fSHerbert Xu obj = &list->rhead; 1106ca26893fSHerbert Xu list = rht_dereference(list->next, ht); 1107ca26893fSHerbert Xu free_fn(rht_obj(ht, obj), arg); 1108ca26893fSHerbert Xu } while (list); 1109ca26893fSHerbert Xu } 1110ca26893fSHerbert Xu 1111ca26893fSHerbert Xu /** 11126b6f302cSThomas Graf * rhashtable_free_and_destroy - free elements and destroy hash table 11137e1e7763SThomas Graf * @ht: the hash table to destroy 11146b6f302cSThomas Graf * @free_fn: callback to release resources of element 11156b6f302cSThomas Graf * @arg: pointer passed to free_fn 11167e1e7763SThomas Graf * 11176b6f302cSThomas Graf * Stops an eventual async resize. If defined, invokes free_fn for each 11186b6f302cSThomas Graf * element to releasal resources. Please note that RCU protected 11196b6f302cSThomas Graf * readers may still be accessing the elements. Releasing of resources 11206b6f302cSThomas Graf * must occur in a compatible manner. Then frees the bucket array. 11216b6f302cSThomas Graf * 11226b6f302cSThomas Graf * This function will eventually sleep to wait for an async resize 11236b6f302cSThomas Graf * to complete. The caller is responsible that no further write operations 11246b6f302cSThomas Graf * occurs in parallel. 11257e1e7763SThomas Graf */ 11266b6f302cSThomas Graf void rhashtable_free_and_destroy(struct rhashtable *ht, 11276b6f302cSThomas Graf void (*free_fn)(void *ptr, void *arg), 11286b6f302cSThomas Graf void *arg) 11297e1e7763SThomas Graf { 1130da20420fSHerbert Xu struct bucket_table *tbl; 11316b6f302cSThomas Graf unsigned int i; 113297defe1eSThomas Graf 113357699a40SYing Xue cancel_work_sync(&ht->run_work); 113457699a40SYing Xue 113597defe1eSThomas Graf mutex_lock(&ht->mutex); 11366b6f302cSThomas Graf tbl = rht_dereference(ht->tbl, ht); 11376b6f302cSThomas Graf if (free_fn) { 11386b6f302cSThomas Graf for (i = 0; i < tbl->size; i++) { 11396b6f302cSThomas Graf struct rhash_head *pos, *next; 11406b6f302cSThomas Graf 1141ae6da1f5SEric Dumazet cond_resched(); 1142da20420fSHerbert Xu for (pos = rht_dereference(*rht_bucket(tbl, i), ht), 11436b6f302cSThomas Graf next = !rht_is_a_nulls(pos) ? 11446b6f302cSThomas Graf rht_dereference(pos->next, ht) : NULL; 11456b6f302cSThomas Graf !rht_is_a_nulls(pos); 11466b6f302cSThomas Graf pos = next, 11476b6f302cSThomas Graf next = !rht_is_a_nulls(pos) ? 11486b6f302cSThomas Graf rht_dereference(pos->next, ht) : NULL) 1149ca26893fSHerbert Xu rhashtable_free_one(ht, pos, free_fn, arg); 11506b6f302cSThomas Graf } 11516b6f302cSThomas Graf } 11526b6f302cSThomas Graf 11536b6f302cSThomas Graf bucket_table_free(tbl); 115497defe1eSThomas Graf mutex_unlock(&ht->mutex); 11557e1e7763SThomas Graf } 11566b6f302cSThomas Graf EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy); 11576b6f302cSThomas Graf 11586b6f302cSThomas Graf void rhashtable_destroy(struct rhashtable *ht) 11596b6f302cSThomas Graf { 11606b6f302cSThomas Graf return rhashtable_free_and_destroy(ht, NULL, NULL); 11616b6f302cSThomas Graf } 11627e1e7763SThomas Graf EXPORT_SYMBOL_GPL(rhashtable_destroy); 1163da20420fSHerbert Xu 1164da20420fSHerbert Xu struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl, 1165da20420fSHerbert Xu unsigned int hash) 1166da20420fSHerbert Xu { 1167da20420fSHerbert Xu const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *)); 1168da20420fSHerbert Xu static struct rhash_head __rcu *rhnull = 1169da20420fSHerbert Xu (struct rhash_head __rcu *)NULLS_MARKER(0); 1170da20420fSHerbert Xu unsigned int index = hash & ((1 << tbl->nest) - 1); 1171da20420fSHerbert Xu unsigned int size = tbl->size >> tbl->nest; 1172da20420fSHerbert Xu unsigned int subhash = hash; 1173da20420fSHerbert Xu union nested_table *ntbl; 1174da20420fSHerbert Xu 1175da20420fSHerbert Xu ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]); 1176c4d2603dSHerbert Xu ntbl = rht_dereference_bucket_rcu(ntbl[index].table, tbl, hash); 1177da20420fSHerbert Xu subhash >>= tbl->nest; 1178da20420fSHerbert Xu 1179da20420fSHerbert Xu while (ntbl && size > (1 << shift)) { 1180da20420fSHerbert Xu index = subhash & ((1 << shift) - 1); 1181c4d2603dSHerbert Xu ntbl = rht_dereference_bucket_rcu(ntbl[index].table, 1182c4d2603dSHerbert Xu tbl, hash); 1183da20420fSHerbert Xu size >>= shift; 1184da20420fSHerbert Xu subhash >>= shift; 1185da20420fSHerbert Xu } 1186da20420fSHerbert Xu 1187da20420fSHerbert Xu if (!ntbl) 1188da20420fSHerbert Xu return &rhnull; 1189da20420fSHerbert Xu 1190da20420fSHerbert Xu return &ntbl[subhash].bucket; 1191da20420fSHerbert Xu 1192da20420fSHerbert Xu } 1193da20420fSHerbert Xu EXPORT_SYMBOL_GPL(rht_bucket_nested); 1194da20420fSHerbert Xu 1195da20420fSHerbert Xu struct rhash_head __rcu **rht_bucket_nested_insert(struct rhashtable *ht, 1196da20420fSHerbert Xu struct bucket_table *tbl, 1197da20420fSHerbert Xu unsigned int hash) 1198da20420fSHerbert Xu { 1199da20420fSHerbert Xu const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *)); 1200da20420fSHerbert Xu unsigned int index = hash & ((1 << tbl->nest) - 1); 1201da20420fSHerbert Xu unsigned int size = tbl->size >> tbl->nest; 1202da20420fSHerbert Xu union nested_table *ntbl; 1203da20420fSHerbert Xu 1204da20420fSHerbert Xu ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]); 1205da20420fSHerbert Xu hash >>= tbl->nest; 1206da20420fSHerbert Xu ntbl = nested_table_alloc(ht, &ntbl[index].table, 12075af68ef7SNeilBrown size <= (1 << shift)); 1208da20420fSHerbert Xu 1209da20420fSHerbert Xu while (ntbl && size > (1 << shift)) { 1210da20420fSHerbert Xu index = hash & ((1 << shift) - 1); 1211da20420fSHerbert Xu size >>= shift; 1212da20420fSHerbert Xu hash >>= shift; 1213da20420fSHerbert Xu ntbl = nested_table_alloc(ht, &ntbl[index].table, 12145af68ef7SNeilBrown size <= (1 << shift)); 1215da20420fSHerbert Xu } 1216da20420fSHerbert Xu 1217da20420fSHerbert Xu if (!ntbl) 1218da20420fSHerbert Xu return NULL; 1219da20420fSHerbert Xu 1220da20420fSHerbert Xu return &ntbl[hash].bucket; 1221da20420fSHerbert Xu 1222da20420fSHerbert Xu } 1223da20420fSHerbert Xu EXPORT_SYMBOL_GPL(rht_bucket_nested_insert); 1224