d2912cb15bdda (Thomas Gleixner 2019-06-04 10:11:33 +0200 1) // SPDX-License-Identifier: GPL-2.0-only
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 2) /*
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 3) * Resizable, Scalable, Concurrent Hash Table
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 4) *
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 5) * Copyright (c) 2015 Herbert Xu <herbert@gondor.apana.org.au>
a5ec68e3b8f2c (Thomas Graf 2015-02-05 02:03:32 +0100 6) * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 7) * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 8) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 9) * Code partially derived from nft_hash
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 10) * Rewritten with rehash code from br_multicast plus single list
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 11) * pointer as suggested by Josh Triplett
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 12) */
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 13)
07ee0722bf941 (Herbert Xu 2015-05-15 11:30:47 +0800 14) #include <linux/atomic.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 15) #include <linux/kernel.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 16) #include <linux/init.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 17) #include <linux/log2.h>
5beb5c90c1f54 (Eric Dumazet 2015-02-26 07:20:34 -0800 18) #include <linux/sched.h>
b2d091031075a (Ingo Molnar 2017-02-04 01:27:20 +0100 19) #include <linux/rculist.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 20) #include <linux/slab.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 21) #include <linux/vmalloc.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 22) #include <linux/mm.h>
87545899b52f9 (Daniel Borkmann 2014-12-10 16:33:11 +0100 23) #include <linux/jhash.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 24) #include <linux/random.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 25) #include <linux/rhashtable.h>
61d7b097738c9 (Stephen Rothwell 2015-02-09 14:04:03 +1100 26) #include <linux/err.h>
6d7954130c8d7 (Hauke Mehrtens 2015-06-06 22:07:23 +0200 27) #include <linux/export.h>
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 28)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 29) #define HASH_DEFAULT_SIZE 64UL
c2e213cff701f (Herbert Xu 2015-03-18 20:01:16 +1100 30) #define HASH_MIN_SIZE 4U
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 31)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 32) union nested_table {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 33) union nested_table __rcu *table;
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 34) struct rhash_lock_head __rcu *bucket;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 35) };
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 36)
988dfbd795cf0 (Herbert Xu 2015-03-10 09:27:55 +1100 37) static u32 head_hashfn(struct rhashtable *ht,
8d24c0b43125e (Thomas Graf 2015-01-02 23:00:14 +0100 38) const struct bucket_table *tbl,
8d24c0b43125e (Thomas Graf 2015-01-02 23:00:14 +0100 39) const struct rhash_head *he)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 40) {
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 41) return rht_head_hashfn(ht, tbl, he, ht->p);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 42) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 43)
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 44) #ifdef CONFIG_PROVE_LOCKING
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 45) #define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 46)
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 47) int lockdep_rht_mutex_is_held(struct rhashtable *ht)
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 48) {
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 49) return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 50) }
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 51) EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 52)
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 53) int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 54) {
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 55) if (!debug_locks)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 56) return 1;
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 57) if (unlikely(tbl->nest))
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 58) return 1;
ca0b709d1a07b (NeilBrown 2019-04-12 11:52:08 +1000 59) return bit_spin_is_locked(0, (unsigned long *)&tbl->buckets[hash]);
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 60) }
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 61) EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 62) #else
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 63) #define ASSERT_RHT_MUTEX(HT)
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 64) #endif
a03eaec0df52a (Thomas Graf 2015-02-05 02:03:34 +0100 65)
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 66) static inline union nested_table *nested_table_top(
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 67) const struct bucket_table *tbl)
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 68) {
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 69) /* The top-level bucket entry does not need RCU protection
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 70) * because it's set at the same time as tbl->nest.
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 71) */
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 72) return (void *)rcu_dereference_protected(tbl->buckets[0], 1);
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 73) }
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 74)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 75) static void nested_table_free(union nested_table *ntbl, unsigned int size)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 76) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 77) const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 78) const unsigned int len = 1 << shift;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 79) unsigned int i;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 80)
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 81) ntbl = rcu_dereference_protected(ntbl->table, 1);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 82) if (!ntbl)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 83) return;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 84)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 85) if (size > len) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 86) size >>= shift;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 87) for (i = 0; i < len; i++)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 88) nested_table_free(ntbl + i, size);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 89) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 90)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 91) kfree(ntbl);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 92) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 93)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 94) static void nested_bucket_table_free(const struct bucket_table *tbl)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 95) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 96) unsigned int size = tbl->size >> tbl->nest;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 97) unsigned int len = 1 << tbl->nest;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 98) union nested_table *ntbl;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 99) unsigned int i;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 100)
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 101) ntbl = nested_table_top(tbl);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 102)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 103) for (i = 0; i < len; i++)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 104) nested_table_free(ntbl + i, size);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 105)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 106) kfree(ntbl);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 107) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 108)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 109) static void bucket_table_free(const struct bucket_table *tbl)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 110) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 111) if (tbl->nest)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 112) nested_bucket_table_free(tbl);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 113)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 114) kvfree(tbl);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 115) }
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 116)
9d901bc05153b (Herbert Xu 2015-03-14 13:57:23 +1100 117) static void bucket_table_free_rcu(struct rcu_head *head)
9d901bc05153b (Herbert Xu 2015-03-14 13:57:23 +1100 118) {
9d901bc05153b (Herbert Xu 2015-03-14 13:57:23 +1100 119) bucket_table_free(container_of(head, struct bucket_table, rcu));
9d901bc05153b (Herbert Xu 2015-03-14 13:57:23 +1100 120) }
9d901bc05153b (Herbert Xu 2015-03-14 13:57:23 +1100 121)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 122) static union nested_table *nested_table_alloc(struct rhashtable *ht,
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 123) union nested_table __rcu **prev,
5af68ef7333c8 (NeilBrown 2018-06-18 12:52:50 +1000 124) bool leaf)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 125) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 126) union nested_table *ntbl;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 127) int i;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 128)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 129) ntbl = rcu_dereference(*prev);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 130) if (ntbl)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 131) return ntbl;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 132)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 133) ntbl = kzalloc(PAGE_SIZE, GFP_ATOMIC);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 134)
5af68ef7333c8 (NeilBrown 2018-06-18 12:52:50 +1000 135) if (ntbl && leaf) {
5af68ef7333c8 (NeilBrown 2018-06-18 12:52:50 +1000 136) for (i = 0; i < PAGE_SIZE / sizeof(ntbl[0]); i++)
9b4f64a227b6f (NeilBrown 2018-06-18 12:52:50 +1000 137) INIT_RHT_NULLS_HEAD(ntbl[i].bucket);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 138) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 139)
e9458a4e337db (Herbert Xu 2019-05-16 15:19:48 +0800 140) if (cmpxchg((union nested_table **)prev, NULL, ntbl) == NULL)
7a41c294c1463 (NeilBrown 2019-04-02 10:07:45 +1100 141) return ntbl;
7a41c294c1463 (NeilBrown 2019-04-02 10:07:45 +1100 142) /* Raced with another thread. */
7a41c294c1463 (NeilBrown 2019-04-02 10:07:45 +1100 143) kfree(ntbl);
7a41c294c1463 (NeilBrown 2019-04-02 10:07:45 +1100 144) return rcu_dereference(*prev);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 145) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 146)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 147) static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht,
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 148) size_t nbuckets,
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 149) gfp_t gfp)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 150) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 151) const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 152) struct bucket_table *tbl;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 153) size_t size;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 154)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 155) if (nbuckets < (1 << (shift + 1)))
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 156) return NULL;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 157)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 158) size = sizeof(*tbl) + sizeof(tbl->buckets[0]);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 159)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 160) tbl = kzalloc(size, gfp);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 161) if (!tbl)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 162) return NULL;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 163)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 164) if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets,
5af68ef7333c8 (NeilBrown 2018-06-18 12:52:50 +1000 165) false)) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 166) kfree(tbl);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 167) return NULL;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 168) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 169)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 170) tbl->nest = (ilog2(nbuckets) - 1) % shift + 1;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 171)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 172) return tbl;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 173) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 174)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 175) static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
b9ecfdaa1090b (Herbert Xu 2015-03-24 00:50:27 +1100 176) size_t nbuckets,
b9ecfdaa1090b (Herbert Xu 2015-03-24 00:50:27 +1100 177) gfp_t gfp)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 178) {
eb6d1abf1bd8b (Daniel Borkmann 2015-02-20 00:53:38 +0100 179) struct bucket_table *tbl = NULL;
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 180) size_t size;
f89bd6f87a53c (Thomas Graf 2015-01-02 23:00:21 +0100 181) int i;
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 182) static struct lock_class_key __key;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 183)
c252aa3e8ed3a (Gustavo A. R. Silva 2019-04-11 18:43:06 -0500 184) tbl = kvzalloc(struct_size(tbl, buckets, nbuckets), gfp);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 185)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 186) size = nbuckets;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 187)
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 188) if (tbl == NULL && (gfp & ~__GFP_NOFAIL) != GFP_KERNEL) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 189) tbl = nested_bucket_table_alloc(ht, nbuckets, gfp);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 190) nbuckets = 0;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 191) }
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 192)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 193) if (tbl == NULL)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 194) return NULL;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 195)
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 196) lockdep_init_map(&tbl->dep_map, "rhashtable_bucket", &__key, 0);
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 197)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 198) tbl->size = size;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 199)
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 200) rcu_head_init(&tbl->rcu);
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 201) INIT_LIST_HEAD(&tbl->walkers);
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 202)
d48ad080ec010 (Jason A. Donenfeld 2017-06-07 22:47:13 -0400 203) tbl->hash_rnd = get_random_u32();
5269b53da4d43 (Herbert Xu 2015-03-14 13:57:22 +1100 204)
f89bd6f87a53c (Thomas Graf 2015-01-02 23:00:21 +0100 205) for (i = 0; i < nbuckets; i++)
9b4f64a227b6f (NeilBrown 2018-06-18 12:52:50 +1000 206) INIT_RHT_NULLS_HEAD(tbl->buckets[i]);
f89bd6f87a53c (Thomas Graf 2015-01-02 23:00:21 +0100 207)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 208) return tbl;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 209) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 210)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 211) static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 212) struct bucket_table *tbl)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 213) {
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 214) struct bucket_table *new_tbl;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 215)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 216) do {
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 217) new_tbl = tbl;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 218) tbl = rht_dereference_rcu(tbl->future_tbl, ht);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 219) } while (tbl);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 220)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 221) return new_tbl;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 222) }
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 223)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 224) static int rhashtable_rehash_one(struct rhashtable *ht,
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 225) struct rhash_lock_head __rcu **bkt,
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 226) unsigned int old_hash)
a5ec68e3b8f2c (Thomas Graf 2015-02-05 02:03:32 +0100 227) {
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 228) struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
c0690016a73fe (NeilBrown 2018-06-18 12:52:50 +1000 229) struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 230) int err = -EAGAIN;
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 231) struct rhash_head *head, *next, *entry;
e4edbe3c1f44c (NeilBrown 2019-04-12 11:52:07 +1000 232) struct rhash_head __rcu **pprev = NULL;
299e5c32a37a6 (Thomas Graf 2015-03-24 14:18:17 +0100 233) unsigned int new_hash;
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 234)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 235) if (new_tbl->nest)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 236) goto out;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 237)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 238) err = -ENOENT;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 239)
adc6a3ab192eb (NeilBrown 2019-04-12 11:52:08 +1000 240) rht_for_each_from(entry, rht_ptr(bkt, old_tbl, old_hash),
adc6a3ab192eb (NeilBrown 2019-04-12 11:52:08 +1000 241) old_tbl, old_hash) {
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 242) err = 0;
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 243) next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 244)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 245) if (rht_is_a_nulls(next))
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 246) break;
a5ec68e3b8f2c (Thomas Graf 2015-02-05 02:03:32 +0100 247)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 248) pprev = &entry->next;
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 249) }
a5ec68e3b8f2c (Thomas Graf 2015-02-05 02:03:32 +0100 250)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 251) if (err)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 252) goto out;
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 253)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 254) new_hash = head_hashfn(ht, new_tbl, entry);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 255)
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 256) rht_lock_nested(new_tbl, &new_tbl->buckets[new_hash], SINGLE_DEPTH_NESTING);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 257)
adc6a3ab192eb (NeilBrown 2019-04-12 11:52:08 +1000 258) head = rht_ptr(new_tbl->buckets + new_hash, new_tbl, new_hash);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 259)
7def0f952eccd (Dmitriy Vyukov 2015-09-22 10:51:52 +0200 260) RCU_INIT_POINTER(entry->next, head);
a5ec68e3b8f2c (Thomas Graf 2015-02-05 02:03:32 +0100 261)
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 262) rht_assign_unlock(new_tbl, &new_tbl->buckets[new_hash], entry);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 263)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 264) if (pprev)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 265) rcu_assign_pointer(*pprev, next);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 266) else
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 267) /* Need to preserved the bit lock. */
f4712b46a529c (NeilBrown 2019-04-12 11:52:08 +1000 268) rht_assign_locked(bkt, next);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 269)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 270) out:
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 271) return err;
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 272) }
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 273)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 274) static int rhashtable_rehash_chain(struct rhashtable *ht,
299e5c32a37a6 (Thomas Graf 2015-03-24 14:18:17 +0100 275) unsigned int old_hash)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 276) {
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 277) struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 278) struct rhash_lock_head __rcu **bkt = rht_bucket_var(old_tbl, old_hash);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 279) int err;
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 280)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 281) if (!bkt)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 282) return 0;
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 283) rht_lock(old_tbl, bkt);
a5ec68e3b8f2c (Thomas Graf 2015-02-05 02:03:32 +0100 284)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 285) while (!(err = rhashtable_rehash_one(ht, bkt, old_hash)))
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 286) ;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 287)
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 288) if (err == -ENOENT)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 289) err = 0;
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 290) rht_unlock(old_tbl, bkt);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 291)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 292) return err;
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 293) }
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 294)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 295) static int rhashtable_rehash_attach(struct rhashtable *ht,
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 296) struct bucket_table *old_tbl,
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 297) struct bucket_table *new_tbl)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 298) {
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 299) /* Make insertions go into the new, empty table right away. Deletions
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 300) * and lookups will be attempted in both tables until we synchronize.
0ad66449aa3cb (NeilBrown 2018-06-18 12:52:50 +1000 301) * As cmpxchg() provides strong barriers, we do not need
0ad66449aa3cb (NeilBrown 2018-06-18 12:52:50 +1000 302) * rcu_assign_pointer().
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 303) */
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 304)
e9458a4e337db (Herbert Xu 2019-05-16 15:19:48 +0800 305) if (cmpxchg((struct bucket_table **)&old_tbl->future_tbl, NULL,
e9458a4e337db (Herbert Xu 2019-05-16 15:19:48 +0800 306) new_tbl) != NULL)
0ad66449aa3cb (NeilBrown 2018-06-18 12:52:50 +1000 307) return -EEXIST;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 308)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 309) return 0;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 310) }
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 311)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 312) static int rhashtable_rehash_table(struct rhashtable *ht)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 313) {
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 314) struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 315) struct bucket_table *new_tbl;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 316) struct rhashtable_walker *walker;
299e5c32a37a6 (Thomas Graf 2015-03-24 14:18:17 +0100 317) unsigned int old_hash;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 318) int err;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 319)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 320) new_tbl = rht_dereference(old_tbl->future_tbl, ht);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 321) if (!new_tbl)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 322) return 0;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 323)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 324) for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 325) err = rhashtable_rehash_chain(ht, old_hash);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 326) if (err)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 327) return err;
ae6da1f503abb (Eric Dumazet 2018-03-31 12:58:48 -0700 328) cond_resched();
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 329) }
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 330)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 331) /* Publish the new table pointer. */
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 332) rcu_assign_pointer(ht->tbl, new_tbl);
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 333)
ba7c95ea3870f (Herbert Xu 2015-03-24 09:53:17 +1100 334) spin_lock(&ht->lock);
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 335) list_for_each_entry(walker, &old_tbl->walkers, list)
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 336) walker->tbl = NULL;
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 337)
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 338) /* Wait for readers. All new readers will see the new
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 339) * table, and thus no references to the old table will
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 340) * remain.
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 341) * We do this inside the locked region so that
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 342) * rhashtable_walk_stop() can use rcu_head_after_call_rcu()
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 343) * to check if it should not re-link the table.
aa34a6cb04788 (Herbert Xu 2015-03-11 09:43:48 +1100 344) */
9d901bc05153b (Herbert Xu 2015-03-14 13:57:23 +1100 345) call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 346) spin_unlock(&ht->lock);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 347)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 348) return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 349) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 350)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 351) static int rhashtable_rehash_alloc(struct rhashtable *ht,
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 352) struct bucket_table *old_tbl,
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 353) unsigned int size)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 354) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 355) struct bucket_table *new_tbl;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 356) int err;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 357)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 358) ASSERT_RHT_MUTEX(ht);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 359)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 360) new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 361) if (new_tbl == NULL)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 362) return -ENOMEM;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 363)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 364) err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 365) if (err)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 366) bucket_table_free(new_tbl);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 367)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 368) return err;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 369) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 370)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 371) /**
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 372) * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 373) * @ht: the hash table to shrink
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 374) *
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 375) * This function shrinks the hash table to fit, i.e., the smallest
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 376) * size would not cause it to expand right away automatically.
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 377) *
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 378) * The caller must ensure that no concurrent resizing occurs by holding
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 379) * ht->mutex.
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 380) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 381) * The caller must ensure that no concurrent table mutations take place.
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 382) * It is however valid to have concurrent lookups if they are RCU protected.
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 383) *
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 384) * It is valid to have concurrent insertions and deletions protected by per
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 385) * bucket locks or concurrent RCU protected lookups and traversals.
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 386) */
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 387) static int rhashtable_shrink(struct rhashtable *ht)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 388) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 389) struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
12311959ecf8a (Vegard Nossum 2016-08-12 20:10:44 +0200 390) unsigned int nelems = atomic_read(&ht->nelems);
12311959ecf8a (Vegard Nossum 2016-08-12 20:10:44 +0200 391) unsigned int size = 0;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 392)
12311959ecf8a (Vegard Nossum 2016-08-12 20:10:44 +0200 393) if (nelems)
12311959ecf8a (Vegard Nossum 2016-08-12 20:10:44 +0200 394) size = roundup_pow_of_two(nelems * 3 / 2);
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 395) if (size < ht->p.min_size)
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 396) size = ht->p.min_size;
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 397)
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 398) if (old_tbl->size <= size)
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 399) return 0;
18093d1c0d1e0 (Herbert Xu 2015-03-24 00:50:25 +1100 400)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 401) if (rht_dereference(old_tbl->future_tbl, ht))
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 402) return -EEXIST;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 403)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 404) return rhashtable_rehash_alloc(ht, old_tbl, size);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 405) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 406)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 407) static void rht_deferred_worker(struct work_struct *work)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 408) {
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 409) struct rhashtable *ht;
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 410) struct bucket_table *tbl;
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 411) int err = 0;
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 412)
57699a40b4f26 (Ying Xue 2015-01-16 11:13:09 +0800 413) ht = container_of(work, struct rhashtable, run_work);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 414) mutex_lock(&ht->mutex);
28134a53d624a (Herbert Xu 2015-02-04 07:33:22 +1100 415)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 416) tbl = rht_dereference(ht->tbl, ht);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 417) tbl = rhashtable_last_table(ht, tbl);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 418)
a5b6846f9e1a0 (Daniel Borkmann 2015-03-12 15:28:40 +0100 419) if (rht_grow_above_75(ht, tbl))
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 420) err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2);
b5e2c150ac914 (Thomas Graf 2015-03-24 20:42:19 +0000 421) else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 422) err = rhashtable_shrink(ht);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 423) else if (tbl->nest)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 424) err = rhashtable_rehash_alloc(ht, tbl, tbl->size);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 425)
408f13ef358aa (Herbert Xu 2019-03-21 09:39:52 +0800 426) if (!err || err == -EEXIST) {
408f13ef358aa (Herbert Xu 2019-03-21 09:39:52 +0800 427) int nerr;
408f13ef358aa (Herbert Xu 2019-03-21 09:39:52 +0800 428)
408f13ef358aa (Herbert Xu 2019-03-21 09:39:52 +0800 429) nerr = rhashtable_rehash_table(ht);
408f13ef358aa (Herbert Xu 2019-03-21 09:39:52 +0800 430) err = err ?: nerr;
408f13ef358aa (Herbert Xu 2019-03-21 09:39:52 +0800 431) }
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 432)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 433) mutex_unlock(&ht->mutex);
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 434)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 435) if (err)
b824478b2145b (Herbert Xu 2015-03-24 00:50:26 +1100 436) schedule_work(&ht->run_work);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 437) }
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 438)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 439) static int rhashtable_insert_rehash(struct rhashtable *ht,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 440) struct bucket_table *tbl)
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 441) {
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 442) struct bucket_table *old_tbl;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 443) struct bucket_table *new_tbl;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 444) unsigned int size;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 445) int err;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 446)
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 447) old_tbl = rht_dereference_rcu(ht->tbl, ht);
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 448)
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 449) size = tbl->size;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 450)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 451) err = -EBUSY;
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 452)
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 453) if (rht_grow_above_75(ht, tbl))
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 454) size *= 2;
a87b9ebf17096 (Thomas Graf 2015-04-22 09:41:46 +0200 455) /* Do not schedule more than one rehash */
a87b9ebf17096 (Thomas Graf 2015-04-22 09:41:46 +0200 456) else if (old_tbl != tbl)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 457) goto fail;
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 458)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 459) err = -ENOMEM;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 460)
93f976b5190df (Davidlohr Bueso 2018-08-21 22:01:45 -0700 461) new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC | __GFP_NOWARN);
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 462) if (new_tbl == NULL)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 463) goto fail;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 464)
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 465) err = rhashtable_rehash_attach(ht, tbl, new_tbl);
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 466) if (err) {
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 467) bucket_table_free(new_tbl);
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 468) if (err == -EEXIST)
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 469) err = 0;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 470) } else
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 471) schedule_work(&ht->run_work);
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 472)
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 473) return err;
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 474)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 475) fail:
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 476) /* Do not fail the insert if someone else did a rehash. */
c0690016a73fe (NeilBrown 2018-06-18 12:52:50 +1000 477) if (likely(rcu_access_pointer(tbl->future_tbl)))
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 478) return 0;
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 479)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 480) /* Schedule async rehash to retry allocation in process context. */
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 481) if (err == -ENOMEM)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 482) schedule_work(&ht->run_work);
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 483)
3cf92222a39cc (Herbert Xu 2015-12-03 20:41:29 +0800 484) return err;
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 485) }
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 486)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 487) static void *rhashtable_lookup_one(struct rhashtable *ht,
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 488) struct rhash_lock_head __rcu **bkt,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 489) struct bucket_table *tbl, unsigned int hash,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 490) const void *key, struct rhash_head *obj)
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 491) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 492) struct rhashtable_compare_arg arg = {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 493) .ht = ht,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 494) .key = key,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 495) };
e4edbe3c1f44c (NeilBrown 2019-04-12 11:52:07 +1000 496) struct rhash_head __rcu **pprev = NULL;
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 497) struct rhash_head *head;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 498) int elasticity;
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 499)
5f8ddeab10ce4 (Florian Westphal 2017-04-16 02:55:09 +0200 500) elasticity = RHT_ELASTICITY;
adc6a3ab192eb (NeilBrown 2019-04-12 11:52:08 +1000 501) rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 502) struct rhlist_head *list;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 503) struct rhlist_head *plist;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 504)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 505) elasticity--;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 506) if (!key ||
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 507) (ht->p.obj_cmpfn ?
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 508) ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
d3dcf8eb61553 (Paul Blakey 2018-03-04 17:29:48 +0200 509) rhashtable_compare(&arg, rht_obj(ht, head)))) {
d3dcf8eb61553 (Paul Blakey 2018-03-04 17:29:48 +0200 510) pprev = &head->next;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 511) continue;
d3dcf8eb61553 (Paul Blakey 2018-03-04 17:29:48 +0200 512) }
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 513)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 514) if (!ht->rhlist)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 515) return rht_obj(ht, head);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 516)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 517) list = container_of(obj, struct rhlist_head, rhead);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 518) plist = container_of(head, struct rhlist_head, rhead);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 519)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 520) RCU_INIT_POINTER(list->next, plist);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 521) head = rht_dereference_bucket(head->next, tbl, hash);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 522) RCU_INIT_POINTER(list->rhead.next, head);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 523) if (pprev)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 524) rcu_assign_pointer(*pprev, obj);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 525) else
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 526) /* Need to preserve the bit lock */
f4712b46a529c (NeilBrown 2019-04-12 11:52:08 +1000 527) rht_assign_locked(bkt, obj);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 528)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 529) return NULL;
5ca8cc5bf11fa (Pablo Neira Ayuso 2016-08-24 12:31:31 +0200 530) }
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 531)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 532) if (elasticity <= 0)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 533) return ERR_PTR(-EAGAIN);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 534)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 535) return ERR_PTR(-ENOENT);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 536) }
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 537)
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 538) static struct bucket_table *rhashtable_insert_one(
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 539) struct rhashtable *ht, struct rhash_lock_head __rcu **bkt,
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 540) struct bucket_table *tbl, unsigned int hash, struct rhash_head *obj,
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 541) void *data)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 542) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 543) struct bucket_table *new_tbl;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 544) struct rhash_head *head;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 545)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 546) if (!IS_ERR_OR_NULL(data))
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 547) return ERR_PTR(-EEXIST);
07ee0722bf941 (Herbert Xu 2015-05-15 11:30:47 +0800 548)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 549) if (PTR_ERR(data) != -EAGAIN && PTR_ERR(data) != -ENOENT)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 550) return ERR_CAST(data);
ccd57b1bd3246 (Herbert Xu 2015-03-24 00:50:28 +1100 551)
c0690016a73fe (NeilBrown 2018-06-18 12:52:50 +1000 552) new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 553) if (new_tbl)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 554) return new_tbl;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 555)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 556) if (PTR_ERR(data) != -ENOENT)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 557) return ERR_CAST(data);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 558)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 559) if (unlikely(rht_grow_above_max(ht, tbl)))
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 560) return ERR_PTR(-E2BIG);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 561)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 562) if (unlikely(rht_grow_above_100(ht, tbl)))
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 563) return ERR_PTR(-EAGAIN);
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 564)
adc6a3ab192eb (NeilBrown 2019-04-12 11:52:08 +1000 565) head = rht_ptr(bkt, tbl, hash);
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 566)
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 567) RCU_INIT_POINTER(obj->next, head);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 568) if (ht->rhlist) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 569) struct rhlist_head *list;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 570)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 571) list = container_of(obj, struct rhlist_head, rhead);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 572) RCU_INIT_POINTER(list->next, NULL);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 573) }
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 574)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 575) /* bkt is always the head of the list, so it holds
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 576) * the lock, which we need to preserve
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 577) */
f4712b46a529c (NeilBrown 2019-04-12 11:52:08 +1000 578) rht_assign_locked(bkt, obj);
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 579)
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 580) atomic_inc(&ht->nelems);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 581) if (rht_grow_above_75(ht, tbl))
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 582) schedule_work(&ht->run_work);
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 583)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 584) return NULL;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 585) }
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 586)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 587) static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 588) struct rhash_head *obj)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 589) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 590) struct bucket_table *new_tbl;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 591) struct bucket_table *tbl;
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 592) struct rhash_lock_head __rcu **bkt;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 593) unsigned int hash;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 594) void *data;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 595)
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 596) new_tbl = rcu_dereference(ht->tbl);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 597)
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 598) do {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 599) tbl = new_tbl;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 600) hash = rht_head_hashfn(ht, tbl, obj, ht->p);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 601) if (rcu_access_pointer(tbl->future_tbl))
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 602) /* Failure is OK */
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 603) bkt = rht_bucket_var(tbl, hash);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 604) else
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 605) bkt = rht_bucket_insert(ht, tbl, hash);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 606) if (bkt == NULL) {
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 607) new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 608) data = ERR_PTR(-EAGAIN);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 609) } else {
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 610) rht_lock(tbl, bkt);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 611) data = rhashtable_lookup_one(ht, bkt, tbl,
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 612) hash, key, obj);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 613) new_tbl = rhashtable_insert_one(ht, bkt, tbl,
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 614) hash, obj, data);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 615) if (PTR_ERR(new_tbl) != -EEXIST)
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 616) data = ERR_CAST(new_tbl);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 617)
149212f07856b (NeilBrown 2019-04-02 10:07:45 +1100 618) rht_unlock(tbl, bkt);
8f0db018006a4 (NeilBrown 2019-04-02 10:07:45 +1100 619) }
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 620) } while (!IS_ERR_OR_NULL(new_tbl));
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 621)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 622) if (PTR_ERR(data) == -EAGAIN)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 623) data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?:
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 624) -EAGAIN);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 625)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 626) return data;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 627) }
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 628)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 629) void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 630) struct rhash_head *obj)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 631) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 632) void *data;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 633)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 634) do {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 635) rcu_read_lock();
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 636) data = rhashtable_try_insert(ht, key, obj);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 637) rcu_read_unlock();
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 638) } while (PTR_ERR(data) == -EAGAIN);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 639)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 640) return data;
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 641) }
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 642) EXPORT_SYMBOL_GPL(rhashtable_insert_slow);
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 643)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 644) /**
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 645) * rhashtable_walk_enter - Initialise an iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 646) * @ht: Table to walk over
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 647) * @iter: Hash table Iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 648) *
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 649) * This function prepares a hash table walk.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 650) *
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 651) * Note that if you restart a walk after rhashtable_walk_stop you
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 652) * may see the same object twice. Also, you may miss objects if
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 653) * there are removals in between rhashtable_walk_stop and the next
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 654) * call to rhashtable_walk_start.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 655) *
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 656) * For a completely stable walk you should construct your own data
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 657) * structure outside the hash table.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 658) *
82266e98dd4d8 (NeilBrown 2018-04-24 08:29:13 +1000 659) * This function may be called from any process context, including
82266e98dd4d8 (NeilBrown 2018-04-24 08:29:13 +1000 660) * non-preemptable context, but cannot be called from softirq or
82266e98dd4d8 (NeilBrown 2018-04-24 08:29:13 +1000 661) * hardirq context.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 662) *
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 663) * You must call rhashtable_walk_exit after this function returns.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 664) */
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 665) void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 666) {
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 667) iter->ht = ht;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 668) iter->p = NULL;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 669) iter->slot = 0;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 670) iter->skip = 0;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 671) iter->end_of_table = 0;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 672)
c6ff5268293ef (Herbert Xu 2015-12-16 16:45:54 +0800 673) spin_lock(&ht->lock);
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 674) iter->walker.tbl =
179ccc0a73641 (Herbert Xu 2015-12-19 10:45:28 +0800 675) rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 676) list_add(&iter->walker.list, &iter->walker.tbl->walkers);
c6ff5268293ef (Herbert Xu 2015-12-16 16:45:54 +0800 677) spin_unlock(&ht->lock);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 678) }
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 679) EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 680)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 681) /**
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 682) * rhashtable_walk_exit - Free an iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 683) * @iter: Hash table Iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 684) *
6c4128f658571 (Herbert Xu 2019-02-14 22:03:27 +0800 685) * This function frees resources allocated by rhashtable_walk_enter.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 686) */
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 687) void rhashtable_walk_exit(struct rhashtable_iter *iter)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 688) {
c6ff5268293ef (Herbert Xu 2015-12-16 16:45:54 +0800 689) spin_lock(&iter->ht->lock);
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 690) if (iter->walker.tbl)
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 691) list_del(&iter->walker.list);
c6ff5268293ef (Herbert Xu 2015-12-16 16:45:54 +0800 692) spin_unlock(&iter->ht->lock);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 693) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 694) EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 695)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 696) /**
97a6ec4ac021f (Tom Herbert 2017-12-04 10:31:41 -0800 697) * rhashtable_walk_start_check - Start a hash table walk
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 698) * @iter: Hash table iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 699) *
0647169cf9aa4 (Andreas Gruenbacher 2017-09-19 12:41:37 +0200 700) * Start a hash table walk at the current iterator position. Note that we take
0647169cf9aa4 (Andreas Gruenbacher 2017-09-19 12:41:37 +0200 701) * the RCU lock in all cases including when we return an error. So you must
0647169cf9aa4 (Andreas Gruenbacher 2017-09-19 12:41:37 +0200 702) * always call rhashtable_walk_stop to clean up.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 703) *
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 704) * Returns zero if successful.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 705) *
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 706) * Returns -EAGAIN if resize event occured. Note that the iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 707) * will rewind back to the beginning and you may use it immediately
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 708) * by calling rhashtable_walk_next.
97a6ec4ac021f (Tom Herbert 2017-12-04 10:31:41 -0800 709) *
97a6ec4ac021f (Tom Herbert 2017-12-04 10:31:41 -0800 710) * rhashtable_walk_start is defined as an inline variant that returns
97a6ec4ac021f (Tom Herbert 2017-12-04 10:31:41 -0800 711) * void. This is preferred in cases where the caller would ignore
97a6ec4ac021f (Tom Herbert 2017-12-04 10:31:41 -0800 712) * resize events and always continue.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 713) */
97a6ec4ac021f (Tom Herbert 2017-12-04 10:31:41 -0800 714) int rhashtable_walk_start_check(struct rhashtable_iter *iter)
db4374f48a6c3 (Thomas Graf 2015-03-16 10:42:27 +0100 715) __acquires(RCU)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 716) {
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 717) struct rhashtable *ht = iter->ht;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 718) bool rhlist = ht->rhlist;
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 719)
c6ff5268293ef (Herbert Xu 2015-12-16 16:45:54 +0800 720) rcu_read_lock();
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 721)
c6ff5268293ef (Herbert Xu 2015-12-16 16:45:54 +0800 722) spin_lock(&ht->lock);
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 723) if (iter->walker.tbl)
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 724) list_del(&iter->walker.list);
c6ff5268293ef (Herbert Xu 2015-12-16 16:45:54 +0800 725) spin_unlock(&ht->lock);
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 726)
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 727) if (iter->end_of_table)
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 728) return 0;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 729) if (!iter->walker.tbl) {
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 730) iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);
b41cc04b662ac (NeilBrown 2018-04-24 08:29:13 +1000 731) iter->slot = 0;
b41cc04b662ac (NeilBrown 2018-04-24 08:29:13 +1000 732) iter->skip = 0;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 733) return -EAGAIN;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 734) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 735)
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 736) if (iter->p && !rhlist) {
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 737) /*
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 738) * We need to validate that 'p' is still in the table, and
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 739) * if so, update 'skip'
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 740) */
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 741) struct rhash_head *p;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 742) int skip = 0;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 743) rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 744) skip++;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 745) if (p == iter->p) {
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 746) iter->skip = skip;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 747) goto found;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 748) }
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 749) }
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 750) iter->p = NULL;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 751) } else if (iter->p && rhlist) {
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 752) /* Need to validate that 'list' is still in the table, and
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 753) * if so, update 'skip' and 'p'.
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 754) */
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 755) struct rhash_head *p;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 756) struct rhlist_head *list;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 757) int skip = 0;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 758) rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 759) for (list = container_of(p, struct rhlist_head, rhead);
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 760) list;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 761) list = rcu_dereference(list->next)) {
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 762) skip++;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 763) if (list == iter->list) {
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 764) iter->p = p;
c643ecf354e25 (Rishabh Bhatnagar 2018-07-02 09:35:34 -0700 765) iter->skip = skip;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 766) goto found;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 767) }
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 768) }
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 769) }
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 770) iter->p = NULL;
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 771) }
5d240a8936f6a (NeilBrown 2018-04-24 08:29:13 +1000 772) found:
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 773) return 0;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 774) }
97a6ec4ac021f (Tom Herbert 2017-12-04 10:31:41 -0800 775) EXPORT_SYMBOL_GPL(rhashtable_walk_start_check);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 776)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 777) /**
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 778) * __rhashtable_walk_find_next - Find the next element in a table (or the first
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 779) * one in case of a new walk).
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 780) *
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 781) * @iter: Hash table iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 782) *
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 783) * Returns the found object or NULL when the end of the table is reached.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 784) *
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 785) * Returns -EAGAIN if resize event occurred.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 786) */
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 787) static void *__rhashtable_walk_find_next(struct rhashtable_iter *iter)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 788) {
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 789) struct bucket_table *tbl = iter->walker.tbl;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 790) struct rhlist_head *list = iter->list;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 791) struct rhashtable *ht = iter->ht;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 792) struct rhash_head *p = iter->p;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 793) bool rhlist = ht->rhlist;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 794)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 795) if (!tbl)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 796) return NULL;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 797)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 798) for (; iter->slot < tbl->size; iter->slot++) {
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 799) int skip = iter->skip;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 800)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 801) rht_for_each_rcu(p, tbl, iter->slot) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 802) if (rhlist) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 803) list = container_of(p, struct rhlist_head,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 804) rhead);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 805) do {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 806) if (!skip)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 807) goto next;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 808) skip--;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 809) list = rcu_dereference(list->next);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 810) } while (list);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 811)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 812) continue;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 813) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 814) if (!skip)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 815) break;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 816) skip--;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 817) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 818)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 819) next:
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 820) if (!rht_is_a_nulls(p)) {
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 821) iter->skip++;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 822) iter->p = p;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 823) iter->list = list;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 824) return rht_obj(ht, rhlist ? &list->rhead : p);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 825) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 826)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 827) iter->skip = 0;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 828) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 829)
142b942a75cb1 (Phil Sutter 2015-07-06 15:51:20 +0200 830) iter->p = NULL;
142b942a75cb1 (Phil Sutter 2015-07-06 15:51:20 +0200 831)
d88252f9bb74d (Herbert Xu 2015-03-24 00:50:19 +1100 832) /* Ensure we see any new tables. */
d88252f9bb74d (Herbert Xu 2015-03-24 00:50:19 +1100 833) smp_rmb();
d88252f9bb74d (Herbert Xu 2015-03-24 00:50:19 +1100 834)
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 835) iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht);
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 836) if (iter->walker.tbl) {
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 837) iter->slot = 0;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 838) iter->skip = 0;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 839) return ERR_PTR(-EAGAIN);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 840) } else {
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 841) iter->end_of_table = true;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 842) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 843)
c936a79fc01ef (Thomas Graf 2015-05-05 02:22:53 +0200 844) return NULL;
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 845) }
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 846)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 847) /**
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 848) * rhashtable_walk_next - Return the next object and advance the iterator
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 849) * @iter: Hash table iterator
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 850) *
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 851) * Note that you must call rhashtable_walk_stop when you are finished
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 852) * with the walk.
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 853) *
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 854) * Returns the next object or NULL when the end of the table is reached.
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 855) *
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 856) * Returns -EAGAIN if resize event occurred. Note that the iterator
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 857) * will rewind back to the beginning and you may continue to use it.
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 858) */
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 859) void *rhashtable_walk_next(struct rhashtable_iter *iter)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 860) {
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 861) struct rhlist_head *list = iter->list;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 862) struct rhashtable *ht = iter->ht;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 863) struct rhash_head *p = iter->p;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 864) bool rhlist = ht->rhlist;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 865)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 866) if (p) {
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 867) if (!rhlist || !(list = rcu_dereference(list->next))) {
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 868) p = rcu_dereference(p->next);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 869) list = container_of(p, struct rhlist_head, rhead);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 870) }
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 871) if (!rht_is_a_nulls(p)) {
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 872) iter->skip++;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 873) iter->p = p;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 874) iter->list = list;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 875) return rht_obj(ht, rhlist ? &list->rhead : p);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 876) }
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 877)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 878) /* At the end of this slot, switch to next one and then find
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 879) * next entry from that point.
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 880) */
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 881) iter->skip = 0;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 882) iter->slot++;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 883) }
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 884)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 885) return __rhashtable_walk_find_next(iter);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 886) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 887) EXPORT_SYMBOL_GPL(rhashtable_walk_next);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 888)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 889) /**
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 890) * rhashtable_walk_peek - Return the next object but don't advance the iterator
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 891) * @iter: Hash table iterator
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 892) *
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 893) * Returns the next object or NULL when the end of the table is reached.
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 894) *
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 895) * Returns -EAGAIN if resize event occurred. Note that the iterator
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 896) * will rewind back to the beginning and you may continue to use it.
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 897) */
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 898) void *rhashtable_walk_peek(struct rhashtable_iter *iter)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 899) {
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 900) struct rhlist_head *list = iter->list;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 901) struct rhashtable *ht = iter->ht;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 902) struct rhash_head *p = iter->p;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 903)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 904) if (p)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 905) return rht_obj(ht, ht->rhlist ? &list->rhead : p);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 906)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 907) /* No object found in current iter, find next one in the table. */
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 908)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 909) if (iter->skip) {
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 910) /* A nonzero skip value points to the next entry in the table
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 911) * beyond that last one that was found. Decrement skip so
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 912) * we find the current value. __rhashtable_walk_find_next
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 913) * will restore the original value of skip assuming that
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 914) * the table hasn't changed.
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 915) */
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 916) iter->skip--;
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 917) }
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 918)
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 919) return __rhashtable_walk_find_next(iter);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 920) }
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 921) EXPORT_SYMBOL_GPL(rhashtable_walk_peek);
2db54b475ae91 (Tom Herbert 2017-12-04 10:31:42 -0800 922)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 923) /**
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 924) * rhashtable_walk_stop - Finish a hash table walk
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 925) * @iter: Hash table iterator
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 926) *
0647169cf9aa4 (Andreas Gruenbacher 2017-09-19 12:41:37 +0200 927) * Finish a hash table walk. Does not reset the iterator to the start of the
0647169cf9aa4 (Andreas Gruenbacher 2017-09-19 12:41:37 +0200 928) * hash table.
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 929) */
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 930) void rhashtable_walk_stop(struct rhashtable_iter *iter)
db4374f48a6c3 (Thomas Graf 2015-03-16 10:42:27 +0100 931) __releases(RCU)
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 932) {
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 933) struct rhashtable *ht;
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 934) struct bucket_table *tbl = iter->walker.tbl;
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 935)
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 936) if (!tbl)
963ecbd41a102 (Herbert Xu 2015-03-15 21:12:04 +1100 937) goto out;
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 938)
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 939) ht = iter->ht;
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 940)
ba7c95ea3870f (Herbert Xu 2015-03-24 09:53:17 +1100 941) spin_lock(&ht->lock);
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 942) if (rcu_head_after_call_rcu(&tbl->rcu, bucket_table_free_rcu))
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 943) /* This bucket table is being freed, don't re-link it. */
246779dd090bd (Herbert Xu 2016-08-18 16:50:56 +0800 944) iter->walker.tbl = NULL;
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 945) else
4feb7c7a4fbb8 (NeilBrown 2019-03-21 14:42:40 +1100 946) list_add(&iter->walker.list, &tbl->walkers);
ba7c95ea3870f (Herbert Xu 2015-03-24 09:53:17 +1100 947) spin_unlock(&ht->lock);
eddee5ba34eb6 (Herbert Xu 2015-03-14 13:57:20 +1100 948)
963ecbd41a102 (Herbert Xu 2015-03-15 21:12:04 +1100 949) out:
963ecbd41a102 (Herbert Xu 2015-03-15 21:12:04 +1100 950) rcu_read_unlock();
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 951) }
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 952) EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
f2dba9c6ff0d9 (Herbert Xu 2015-02-04 07:33:23 +1100 953)
488fb86ee91d3 (Herbert Xu 2015-03-20 21:56:59 +1100 954) static size_t rounded_hashtable_size(const struct rhashtable_params *params)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 955) {
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 956) size_t retsize;
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 957)
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 958) if (params->nelem_hint)
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 959) retsize = max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 960) (unsigned long)params->min_size);
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 961) else
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 962) retsize = max(HASH_DEFAULT_SIZE,
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 963) (unsigned long)params->min_size);
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 964)
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 965) return retsize;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 966) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 967)
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 968) static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 969) {
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 970) return jhash2(key, length, seed);
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 971) }
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 972)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 973) /**
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 974) * rhashtable_init - initialize a new hash table
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 975) * @ht: hash table to be initialized
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 976) * @params: configuration parameters
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 977) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 978) * Initializes a new hash table based on the provided configuration
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 979) * parameters. A table can be configured either with a variable or
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 980) * fixed length key:
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 981) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 982) * Configuration Example 1: Fixed length keys
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 983) * struct test_obj {
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 984) * int key;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 985) * void * my_member;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 986) * struct rhash_head node;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 987) * };
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 988) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 989) * struct rhashtable_params params = {
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 990) * .head_offset = offsetof(struct test_obj, node),
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 991) * .key_offset = offsetof(struct test_obj, key),
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 992) * .key_len = sizeof(int),
87545899b52f9 (Daniel Borkmann 2014-12-10 16:33:11 +0100 993) * .hashfn = jhash,
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 994) * };
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 995) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 996) * Configuration Example 2: Variable length keys
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 997) * struct test_obj {
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 998) * [...]
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 999) * struct rhash_head node;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1000) * };
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1001) *
49f7b33e63fec (Patrick McHardy 2015-03-25 13:07:45 +0000 1002) * u32 my_hash_fn(const void *data, u32 len, u32 seed)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1003) * {
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1004) * struct test_obj *obj = data;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1005) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1006) * return [... hash ...];
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1007) * }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1008) *
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1009) * struct rhashtable_params params = {
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1010) * .head_offset = offsetof(struct test_obj, node),
87545899b52f9 (Daniel Borkmann 2014-12-10 16:33:11 +0100 1011) * .hashfn = jhash,
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1012) * .obj_hashfn = my_hash_fn,
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1013) * };
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1014) */
488fb86ee91d3 (Herbert Xu 2015-03-20 21:56:59 +1100 1015) int rhashtable_init(struct rhashtable *ht,
488fb86ee91d3 (Herbert Xu 2015-03-20 21:56:59 +1100 1016) const struct rhashtable_params *params)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1017) {
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1018) struct bucket_table *tbl;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1019) size_t size;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1020)
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1021) if ((!params->key_len && !params->obj_hashfn) ||
02fd97c3d4a8a (Herbert Xu 2015-03-20 21:57:00 +1100 1022) (params->obj_hashfn && !params->obj_cmpfn))
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1023) return -EINVAL;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1024)
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1025) memset(ht, 0, sizeof(*ht));
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1026) mutex_init(&ht->mutex);
ba7c95ea3870f (Herbert Xu 2015-03-24 09:53:17 +1100 1027) spin_lock_init(&ht->lock);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1028) memcpy(&ht->p, params, sizeof(*params));
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1029)
a998f712f77ea (Thomas Graf 2015-03-19 22:31:13 +0000 1030) if (params->min_size)
a998f712f77ea (Thomas Graf 2015-03-19 22:31:13 +0000 1031) ht->p.min_size = roundup_pow_of_two(params->min_size);
a998f712f77ea (Thomas Graf 2015-03-19 22:31:13 +0000 1032)
6d684e54690ca (Herbert Xu 2017-04-27 13:44:51 +0800 1033) /* Cap total entries at 2^31 to avoid nelems overflow. */
6d684e54690ca (Herbert Xu 2017-04-27 13:44:51 +0800 1034) ht->max_elems = 1u << 31;
2d2ab658d2deb (Herbert Xu 2017-04-28 14:10:48 +0800 1035)
2d2ab658d2deb (Herbert Xu 2017-04-28 14:10:48 +0800 1036) if (params->max_size) {
2d2ab658d2deb (Herbert Xu 2017-04-28 14:10:48 +0800 1037) ht->p.max_size = rounddown_pow_of_two(params->max_size);
2d2ab658d2deb (Herbert Xu 2017-04-28 14:10:48 +0800 1038) if (ht->p.max_size < ht->max_elems / 2)
2d2ab658d2deb (Herbert Xu 2017-04-28 14:10:48 +0800 1039) ht->max_elems = ht->p.max_size * 2;
2d2ab658d2deb (Herbert Xu 2017-04-28 14:10:48 +0800 1040) }
6d684e54690ca (Herbert Xu 2017-04-27 13:44:51 +0800 1041)
48e75b430670e (Florian Westphal 2017-05-01 22:18:01 +0200 1042) ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
a998f712f77ea (Thomas Graf 2015-03-19 22:31:13 +0000 1043)
107d01f5ba10f (Davidlohr Bueso 2018-07-16 13:26:13 -0700 1044) size = rounded_hashtable_size(&ht->p);
3a324606bbabf (Herbert Xu 2015-12-16 18:13:14 +0800 1045)
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1046) ht->key_len = ht->p.key_len;
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1047) if (!params->hashfn) {
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1048) ht->p.hashfn = jhash;
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1049)
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1050) if (!(ht->key_len & (sizeof(u32) - 1))) {
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1051) ht->key_len /= sizeof(u32);
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1052) ht->p.hashfn = rhashtable_jhash2;
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1053) }
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1054) }
31ccde2dacea8 (Herbert Xu 2015-03-24 00:50:21 +1100 1055)
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1056) /*
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1057) * This is api initialization and thus we need to guarantee the
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1058) * initial rhashtable allocation. Upon failure, retry with the
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1059) * smallest possible size with __GFP_NOFAIL semantics.
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1060) */
b9ecfdaa1090b (Herbert Xu 2015-03-24 00:50:27 +1100 1061) tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1062) if (unlikely(tbl == NULL)) {
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1063) size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1064) tbl = bucket_table_alloc(ht, size, GFP_KERNEL | __GFP_NOFAIL);
2d22ecf6db1c3 (Davidlohr Bueso 2018-08-21 22:01:48 -0700 1065) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1066)
545a148e43bed (Ying Xue 2015-01-07 13:41:57 +0800 1067) atomic_set(&ht->nelems, 0);
a5b6846f9e1a0 (Daniel Borkmann 2015-03-12 15:28:40 +0100 1068)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1069) RCU_INIT_POINTER(ht->tbl, tbl);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1070)
4c4b52d9b2df4 (Daniel Borkmann 2015-02-25 16:31:54 +0100 1071) INIT_WORK(&ht->run_work, rht_deferred_worker);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1072)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1073) return 0;
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1074) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1075) EXPORT_SYMBOL_GPL(rhashtable_init);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1076)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1077) /**
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1078) * rhltable_init - initialize a new hash list table
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1079) * @hlt: hash list table to be initialized
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1080) * @params: configuration parameters
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1081) *
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1082) * Initializes a new hash list table.
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1083) *
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1084) * See documentation for rhashtable_init.
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1085) */
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1086) int rhltable_init(struct rhltable *hlt, const struct rhashtable_params *params)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1087) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1088) int err;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1089)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1090) err = rhashtable_init(&hlt->ht, params);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1091) hlt->ht.rhlist = true;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1092) return err;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1093) }
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1094) EXPORT_SYMBOL_GPL(rhltable_init);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1095)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1096) static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1097) void (*free_fn)(void *ptr, void *arg),
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1098) void *arg)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1099) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1100) struct rhlist_head *list;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1101)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1102) if (!ht->rhlist) {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1103) free_fn(rht_obj(ht, obj), arg);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1104) return;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1105) }
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1106)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1107) list = container_of(obj, struct rhlist_head, rhead);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1108) do {
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1109) obj = &list->rhead;
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1110) list = rht_dereference(list->next, ht);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1111) free_fn(rht_obj(ht, obj), arg);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1112) } while (list);
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1113) }
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1114)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1115) /**
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1116) * rhashtable_free_and_destroy - free elements and destroy hash table
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1117) * @ht: the hash table to destroy
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1118) * @free_fn: callback to release resources of element
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1119) * @arg: pointer passed to free_fn
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1120) *
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1121) * Stops an eventual async resize. If defined, invokes free_fn for each
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1122) * element to releasal resources. Please note that RCU protected
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1123) * readers may still be accessing the elements. Releasing of resources
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1124) * must occur in a compatible manner. Then frees the bucket array.
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1125) *
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1126) * This function will eventually sleep to wait for an async resize
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1127) * to complete. The caller is responsible that no further write operations
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1128) * occurs in parallel.
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1129) */
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1130) void rhashtable_free_and_destroy(struct rhashtable *ht,
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1131) void (*free_fn)(void *ptr, void *arg),
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1132) void *arg)
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1133) {
0026129c86292 (Taehee Yoo 2018-07-08 11:55:51 +0900 1134) struct bucket_table *tbl, *next_tbl;
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1135) unsigned int i;
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1136)
4c4b52d9b2df4 (Daniel Borkmann 2015-02-25 16:31:54 +0100 1137) cancel_work_sync(&ht->run_work);
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1138)
57699a40b4f26 (Ying Xue 2015-01-16 11:13:09 +0800 1139) mutex_lock(&ht->mutex);
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1140) tbl = rht_dereference(ht->tbl, ht);
0026129c86292 (Taehee Yoo 2018-07-08 11:55:51 +0900 1141) restart:
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1142) if (free_fn) {
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1143) for (i = 0; i < tbl->size; i++) {
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1144) struct rhash_head *pos, *next;
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1145)
ae6da1f503abb (Eric Dumazet 2018-03-31 12:58:48 -0700 1146) cond_resched();
adc6a3ab192eb (NeilBrown 2019-04-12 11:52:08 +1000 1147) for (pos = rht_ptr_exclusive(rht_bucket(tbl, i)),
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1148) next = !rht_is_a_nulls(pos) ?
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1149) rht_dereference(pos->next, ht) : NULL;
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1150) !rht_is_a_nulls(pos);
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1151) pos = next,
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1152) next = !rht_is_a_nulls(pos) ?
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1153) rht_dereference(pos->next, ht) : NULL)
ca26893f05e86 (Herbert Xu 2016-09-19 19:00:09 +0800 1154) rhashtable_free_one(ht, pos, free_fn, arg);
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1155) }
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1156) }
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1157)
0026129c86292 (Taehee Yoo 2018-07-08 11:55:51 +0900 1158) next_tbl = rht_dereference(tbl->future_tbl, ht);
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1159) bucket_table_free(tbl);
0026129c86292 (Taehee Yoo 2018-07-08 11:55:51 +0900 1160) if (next_tbl) {
0026129c86292 (Taehee Yoo 2018-07-08 11:55:51 +0900 1161) tbl = next_tbl;
0026129c86292 (Taehee Yoo 2018-07-08 11:55:51 +0900 1162) goto restart;
0026129c86292 (Taehee Yoo 2018-07-08 11:55:51 +0900 1163) }
97defe1ecf868 (Thomas Graf 2015-01-02 23:00:20 +0100 1164) mutex_unlock(&ht->mutex);
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1165) }
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1166) EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1167)
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1168) void rhashtable_destroy(struct rhashtable *ht)
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1169) {
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1170) return rhashtable_free_and_destroy(ht, NULL, NULL);
6b6f302ceda7a (Thomas Graf 2015-03-24 14:18:20 +0100 1171) }
7e1e77636e360 (Thomas Graf 2014-08-02 11:47:44 +0200 1172) EXPORT_SYMBOL_GPL(rhashtable_destroy);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1173)
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 1174) struct rhash_lock_head __rcu **__rht_bucket_nested(
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 1175) const struct bucket_table *tbl, unsigned int hash)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1176) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1177) const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1178) unsigned int index = hash & ((1 << tbl->nest) - 1);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1179) unsigned int size = tbl->size >> tbl->nest;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1180) unsigned int subhash = hash;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1181) union nested_table *ntbl;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1182)
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 1183) ntbl = nested_table_top(tbl);
c4d2603dac3a5 (Herbert Xu 2017-02-25 22:39:50 +0800 1184) ntbl = rht_dereference_bucket_rcu(ntbl[index].table, tbl, hash);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1185) subhash >>= tbl->nest;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1186)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1187) while (ntbl && size > (1 << shift)) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1188) index = subhash & ((1 << shift) - 1);
c4d2603dac3a5 (Herbert Xu 2017-02-25 22:39:50 +0800 1189) ntbl = rht_dereference_bucket_rcu(ntbl[index].table,
c4d2603dac3a5 (Herbert Xu 2017-02-25 22:39:50 +0800 1190) tbl, hash);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1191) size >>= shift;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1192) subhash >>= shift;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1193) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1194)
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1195) if (!ntbl)
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1196) return NULL;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1197)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1198) return &ntbl[subhash].bucket;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1199)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1200) }
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1201) EXPORT_SYMBOL_GPL(__rht_bucket_nested);
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1202)
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 1203) struct rhash_lock_head __rcu **rht_bucket_nested(
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 1204) const struct bucket_table *tbl, unsigned int hash)
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1205) {
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 1206) static struct rhash_lock_head __rcu *rhnull;
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1207)
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1208) if (!rhnull)
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1209) INIT_RHT_NULLS_HEAD(rhnull);
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1210) return __rht_bucket_nested(tbl, hash) ?: &rhnull;
ff302db965b57 (NeilBrown 2019-04-02 10:07:45 +1100 1211) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1212) EXPORT_SYMBOL_GPL(rht_bucket_nested);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1213)
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 1214) struct rhash_lock_head __rcu **rht_bucket_nested_insert(
ce9b362bf6db5 (Herbert Xu 2020-07-24 20:14:34 +1000 1215) struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1216) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1217) const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1218) unsigned int index = hash & ((1 << tbl->nest) - 1);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1219) unsigned int size = tbl->size >> tbl->nest;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1220) union nested_table *ntbl;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1221)
4a3084aaa88e7 (Herbert Xu 2020-06-03 18:12:43 +1000 1222) ntbl = nested_table_top(tbl);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1223) hash >>= tbl->nest;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1224) ntbl = nested_table_alloc(ht, &ntbl[index].table,
5af68ef7333c8 (NeilBrown 2018-06-18 12:52:50 +1000 1225) size <= (1 << shift));
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1226)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1227) while (ntbl && size > (1 << shift)) {
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1228) index = hash & ((1 << shift) - 1);
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1229) size >>= shift;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1230) hash >>= shift;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1231) ntbl = nested_table_alloc(ht, &ntbl[index].table,
5af68ef7333c8 (NeilBrown 2018-06-18 12:52:50 +1000 1232) size <= (1 << shift));
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1233) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1234)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1235) if (!ntbl)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1236) return NULL;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1237)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1238) return &ntbl[hash].bucket;
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1239)
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1240) }
da20420f83ea0 (Herbert Xu 2017-02-11 19:26:47 +0800 1241) EXPORT_SYMBOL_GPL(rht_bucket_nested_insert);
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags