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