Something went wrong. Try again.
(I'm so sorry!) Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel os linux
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365// 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/irq_work.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>#include <linux/workqueue.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_atomic(const struct bucket_table *tbl){ if (tbl->nest) nested_bucket_table_free(tbl);
kvfree_atomic(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 = alloc_hooks_tag(ht->alloc_tag, kmalloc_noprof(PAGE_SIZE, GFP_ATOMIC|__GFP_ZERO));
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 = alloc_hooks_tag(ht->alloc_tag, kmalloc_noprof(size, gfp|__GFP_ZERO)); 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;
tbl = alloc_hooks_tag(ht->alloc_tag, kvmalloc_node_align_noprof(struct_size(tbl, buckets, nbuckets), 1, gfp|__GFP_ZERO, NUMA_NO_NODE));
size = nbuckets;
if (tbl == NULL && !gfpflags_allow_blocking(gfp)) { tbl = nested_bucket_table_alloc(ht, nbuckets, gfp); nbuckets = 0; }
if (tbl == NULL) return NULL;
#ifdef CONFIG_LOCKDEP lockdep_init_map(&tbl->dep_map, "rhashtable_bucket", ht->lockdep_key, 0);#endif
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; unsigned long flags;
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);
flags = 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, flags);
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); unsigned long flags; int err;
if (!bkt) return 0; flags = rht_lock(old_tbl, bkt);
while (!(err = rhashtable_rehash_one(ht, bkt, old_hash))) ;
if (err == -ENOENT) err = 0; rht_unlock(old_tbl, bkt, flags);
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) __must_hold(&ht->mutex){ 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) __must_hold(&ht->mutex){ 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);
/* * Re-arm via @run_work, not @run_irq_work. * rhashtable_free_and_destroy() drains async work as irq_work_sync() * followed by cancel_work_sync(). If this site queued irq_work while * cancel_work_sync() was waiting for us, irq_work_sync() would already * have returned and the stale irq_work could fire post-teardown. * cancel_work_sync() natively handles self-requeue on @run_work. */ if (err) schedule_work(&ht->run_work);}
/* * Insert-path callers can run under a raw spinlock (e.g. an insecure_elasticity * user). Calling schedule_work() under that lock records caller_lock -> * pool->lock -> pi_lock -> rq->__lock, closing a locking cycle if any of * these is acquired in the reverse direction elsewhere. Bounce through * irq_work so the schedule_work() runs with the caller's lock no longer held. */static void rht_deferred_irq_work(struct irq_work *irq_work){ struct rhashtable *ht = container_of(irq_work, struct rhashtable, run_irq_work);
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_atomic(new_tbl); if (err == -EEXIST) err = 0; } else irq_work_queue(&ht->run_irq_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) irq_work_queue(&ht->run_irq_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), ht->p))) { 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 && !ht->p.insecure_elasticity) 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)) && !ht->p.insecure_elasticity) 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);
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 long flags; 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 { bool inserted;
flags = 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); inserted = data && !new_tbl; if (inserted) atomic_inc(&ht->nelems); if (PTR_ERR(new_tbl) != -EEXIST) data = ERR_CAST(new_tbl);
rht_unlock(tbl, bkt, flags);
if (inserted && rht_grow_above_75(ht, tbl)) irq_work_queue(&ht->run_irq_work); } } 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);
/* Scan one element forward from prev_key's position in @tbl. * Returns first rhash_head whose bucket > prev_key's bucket, or the * element immediately after prev_key inside prev_key's bucket. * Returns the first element if prev_key is NULL, NULL when @tbl is * exhausted, or ERR_PTR(-ENOENT) if prev_key is not found in @tbl. */static struct rhash_head *__rhashtable_next_in_table( struct rhashtable *ht, struct bucket_table *tbl, const void *prev_key){ struct rhashtable_compare_arg arg = { .ht = ht, .key = prev_key }; const struct rhashtable_params params = ht->p; struct rhash_head *he; unsigned int b = 0; bool found = false;
if (prev_key) { b = rht_key_hashfn(ht, tbl, prev_key, params); rht_for_each_rcu(he, tbl, b) { bool match = params.obj_cmpfn ? !params.obj_cmpfn(&arg, rht_obj(ht, he)) : !rhashtable_compare(&arg, rht_obj(ht, he), params); if (found) { if (match) continue; return he; } if (match) found = true; } if (!found) return ERR_PTR(-ENOENT); b++; }
for (; b < tbl->size; b++) rht_for_each_rcu(he, tbl, b) return he; return NULL;}
/** * rhashtable_next_key - return next element after a given key * @ht: hash table * @prev_key: pointer to previous key, or NULL for the first element * * WARNING: this walk is highly unstable. Unlike rhashtable_walk_*(), * it cannot detect a concurrent resize or rehash, so a full iteration * is NOT guaranteed to terminate under adversarial or sustained * rehashing. Callers MUST tolerate skipped and duplicated elements and * SHOULD bound their loop externally. * * Returns the next element in best-effort iteration order, walking the * @tbl chain (including any future_tbl in flight). Caller must hold RCU. * * Pass @prev_key == NULL to obtain the first element. To iterate, set * @prev_key to the key of the previously returned element on each call, * and stop when NULL is returned. * * Best-effort semantics: * - Across the tbl->future_tbl chain, an element being migrated may * transiently appear in both tables and be observed twice. * - Concurrent inserts may or may not be observed. * - Termination of a full iteration loop is NOT guaranteed under * adversarial continuous rehash; callers MUST tolerate skips and * repeats and SHOULD bound their loop externally. * - Behavior on tables that contain duplicate keys is undefined: * duplicates may be skipped, repeated, or trap the walk in a * cycle. Callers requiring duplicate-key iteration must use * rhashtable_walk_*() instead. * - rhltable instances are not supported and return * ERR_PTR(-EOPNOTSUPP). * - If prev_key was concurrently deleted and is not present in any * in-flight table, returns ERR_PTR(-ENOENT). * * Returns entry of the next element, or NULL when iteration is exhausted, * or ERR_PTR(-ENOENT) if prev_key is not found, or * ERR_PTR(-EOPNOTSUPP) if @ht is an rhltable. */void *rhashtable_next_key(struct rhashtable *ht, const void *prev_key){ struct bucket_table *tbl; struct rhash_head *he;
if (unlikely(ht->rhlist)) return ERR_PTR(-EOPNOTSUPP);
tbl = rht_dereference_rcu(ht->tbl, ht); do { he = __rhashtable_next_in_table(ht, tbl, prev_key); if (!IS_ERR_OR_NULL(he)) return rht_obj(ht, he); if (!he) prev_key = NULL; /* See any new future_tbl attached during a rehash. */ smp_rmb(); tbl = rht_dereference_rcu(tbl->future_tbl, ht); } while (tbl); return he; /* NULL or -ENOENT */}EXPORT_SYMBOL_GPL(rhashtable_next_key);
/** * 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-preemptible 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_shared(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; iter->p = NULL; 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){ 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);}
int __rhashtable_init_noprof(struct rhashtable *ht, const struct rhashtable_params *params, struct rhashtable_lockdep_keys *keys){ 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_with_key(&ht->mutex, &keys->mutex_key); spin_lock_init(&ht->lock); lockdep_set_class(&ht->lock, &keys->lock_key);#ifdef CONFIG_LOCKDEP ht->lockdep_key = &keys->bucket_key;#endif memcpy(&ht->p, params, sizeof(*params));
alloc_tag_record(ht->alloc_tag);
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); init_irq_work(&ht->run_irq_work, rht_deferred_irq_work);
return 0;}EXPORT_SYMBOL_GPL(__rhashtable_init_noprof);
int __rhltable_init_noprof(struct rhltable *hlt, const struct rhashtable_params *params, struct rhashtable_lockdep_keys *keys){ int err;
err = __rhashtable_init_noprof(&hlt->ht, params, keys); hlt->ht.rhlist = true; return err;}EXPORT_SYMBOL_GPL(__rhltable_init_noprof);
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 = rcu_dereference_raw(list->next); 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. * * After cancel_work_sync() has returned, the deferred rehash worker is * quiesced and, per the contract above, no other concurrent access to the * rhashtable is possible. The tables are therefore owned exclusively by * this function and can be walked without ht->mutex held. */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;
irq_work_sync(&ht->run_irq_work); cancel_work_sync(&ht->run_work);
/* * Do NOT take ht->mutex here. The rehash worker establishes * ht->mutex -> fs_reclaim via GFP_KERNEL bucket allocation under * the mutex; callers on the reclaim path (e.g. simple_xattr_ht_free() * from evict() under the dcache shrinker for shmem/kernfs/pidfs * inodes) would otherwise close a circular dependency * fs_reclaim -> ht->mutex. */ tbl = rcu_dereference_raw(ht->tbl);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) ? rcu_dereference_raw(pos->next) : NULL; !rht_is_a_nulls(pos); pos = next, next = !rht_is_a_nulls(pos) ? rcu_dereference_raw(pos->next) : NULL) rhashtable_free_one(ht, pos, free_fn, arg); } }
next_tbl = rcu_dereference_raw(tbl->future_tbl); bucket_table_free(tbl); if (next_tbl) { tbl = next_tbl; goto restart; }}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);