2 * Resizable, Scalable, Concurrent Hash Table
4 * Copyright (c) 2015-2016 Herbert Xu <herbert@gondor.apana.org.au>
5 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
6 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
8 * Code partially derived from nft_hash
9 * Rewritten with rehash code from br_multicast plus single list
10 * pointer as suggested by Josh Triplett
12 * This program is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License version 2 as
14 * published by the Free Software Foundation.
17 #ifndef _LINUX_RHASHTABLE_H
18 #define _LINUX_RHASHTABLE_H
20 #include <linux/atomic.h>
21 #include <linux/compiler.h>
22 #include <linux/err.h>
23 #include <linux/errno.h>
24 #include <linux/jhash.h>
25 #include <linux/list_nulls.h>
26 #include <linux/workqueue.h>
27 #include <linux/mutex.h>
28 #include <linux/rculist.h>
31 * The end of the chain is marked with a special nulls marks which has
32 * the following format:
34 * +-------+-----------------------------------------------------+-+
36 * +-------+-----------------------------------------------------+-+
38 * Base (4 bits) : Reserved to distinguish between multiple tables.
39 * Specified via &struct rhashtable_params.nulls_base.
40 * Hash (27 bits): Full hash (unmasked) of first element added to bucket
41 * 1 (1 bit) : Nulls marker (always set)
43 * The remaining bits of the next pointer remain unused for now.
45 #define RHT_BASE_BITS 4
46 #define RHT_HASH_BITS 27
47 #define RHT_BASE_SHIFT RHT_HASH_BITS
49 /* Base bits plus 1 bit for nulls marker */
50 #define RHT_HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
52 /* Maximum chain length before rehash
54 * The maximum (not average) chain length grows with the size of the hash
55 * table, at a rate of (log N)/(log log N).
57 * The value of 16 is selected so that even if the hash table grew to
58 * 2^32 you would not expect the maximum chain length to exceed it
59 * unless we are under attack (or extremely unlucky).
61 * As this limit is only to detect attacks, we don't need to set it to a
62 * lower value as you'd need the chain length to vastly exceed 16 to have
63 * any real effect on the system.
65 #define RHT_ELASTICITY 16u
68 struct rhash_head __rcu *next;
72 struct rhash_head rhead;
73 struct rhlist_head __rcu *next;
77 * struct bucket_table - Table of hash buckets
78 * @size: Number of hash buckets
79 * @nest: Number of bits of first-level nested table.
80 * @rehash: Current bucket being rehashed
81 * @hash_rnd: Random seed to fold into hash
82 * @locks_mask: Mask to apply before accessing locks[]
83 * @locks: Array of spinlocks protecting individual buckets
84 * @walkers: List of active walkers
85 * @rcu: RCU structure for freeing the table
86 * @future_tbl: Table under construction during rehashing
87 * @ntbl: Nested table used when out of memory.
88 * @buckets: size * hash buckets
95 unsigned int locks_mask;
97 struct list_head walkers;
100 struct bucket_table __rcu *future_tbl;
102 struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp;
106 * struct rhashtable_compare_arg - Key for the function rhashtable_compare
108 * @key: Key to compare against
110 struct rhashtable_compare_arg {
111 struct rhashtable *ht;
115 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
116 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
117 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
123 * struct rhashtable_params - Hash table construction parameters
124 * @nelem_hint: Hint on number of elements, should be 75% of desired size
125 * @key_len: Length of key
126 * @key_offset: Offset of key in struct to be hashed
127 * @head_offset: Offset of rhash_head in struct to be hashed
128 * @max_size: Maximum size while expanding
129 * @min_size: Minimum size while shrinking
130 * @locks_mul: Number of bucket locks to allocate per cpu (default: 32)
131 * @automatic_shrinking: Enable automatic shrinking of tables
132 * @nulls_base: Base value to generate nulls marker
133 * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
134 * @obj_hashfn: Function to hash object
135 * @obj_cmpfn: Function to compare key with object
137 struct rhashtable_params {
142 unsigned int max_size;
144 bool automatic_shrinking;
148 rht_obj_hashfn_t obj_hashfn;
149 rht_obj_cmpfn_t obj_cmpfn;
153 * struct rhashtable - Hash table handle
155 * @nelems: Number of elements in table
156 * @key_len: Key length for hashfn
157 * @p: Configuration parameters
158 * @max_elems: Maximum number of elements in table
159 * @rhlist: True if this is an rhltable
160 * @run_work: Deferred worker to expand/shrink asynchronously
161 * @mutex: Mutex to protect current/future table swapping
162 * @lock: Spin lock to protect walker list
165 struct bucket_table __rcu *tbl;
167 unsigned int key_len;
168 struct rhashtable_params p;
169 unsigned int max_elems;
171 struct work_struct run_work;
177 * struct rhltable - Hash table with duplicate objects in a list
178 * @ht: Underlying rhtable
181 struct rhashtable ht;
185 * struct rhashtable_walker - Hash table walker
186 * @list: List entry on list of walkers
187 * @tbl: The table that we were walking over
189 struct rhashtable_walker {
190 struct list_head list;
191 struct bucket_table *tbl;
195 * struct rhashtable_iter - Hash table iterator
196 * @ht: Table to iterate through
197 * @p: Current pointer
198 * @list: Current hash list pointer
199 * @walker: Associated rhashtable walker
200 * @slot: Current slot
201 * @skip: Number of entries to skip in slot
203 struct rhashtable_iter {
204 struct rhashtable *ht;
205 struct rhash_head *p;
206 struct rhlist_head *list;
207 struct rhashtable_walker walker;
212 static inline unsigned long rht_marker(const struct rhashtable *ht, u32 hash)
214 return NULLS_MARKER(ht->p.nulls_base + hash);
217 #define INIT_RHT_NULLS_HEAD(ptr, ht, hash) \
218 ((ptr) = (typeof(ptr)) rht_marker(ht, hash))
220 static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
222 return ((unsigned long) ptr & 1);
225 static inline unsigned long rht_get_nulls_value(const struct rhash_head *ptr)
227 return ((unsigned long) ptr) >> 1;
230 static inline void *rht_obj(const struct rhashtable *ht,
231 const struct rhash_head *he)
233 return (char *)he - ht->p.head_offset;
236 static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
239 return (hash >> RHT_HASH_RESERVED_SPACE) & (tbl->size - 1);
242 static inline unsigned int rht_key_hashfn(
243 struct rhashtable *ht, const struct bucket_table *tbl,
244 const void *key, const struct rhashtable_params params)
248 /* params must be equal to ht->p if it isn't constant. */
249 if (!__builtin_constant_p(params.key_len))
250 hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd);
251 else if (params.key_len) {
252 unsigned int key_len = params.key_len;
255 hash = params.hashfn(key, key_len, tbl->hash_rnd);
256 else if (key_len & (sizeof(u32) - 1))
257 hash = jhash(key, key_len, tbl->hash_rnd);
259 hash = jhash2(key, key_len / sizeof(u32),
262 unsigned int key_len = ht->p.key_len;
265 hash = params.hashfn(key, key_len, tbl->hash_rnd);
267 hash = jhash(key, key_len, tbl->hash_rnd);
270 return rht_bucket_index(tbl, hash);
273 static inline unsigned int rht_head_hashfn(
274 struct rhashtable *ht, const struct bucket_table *tbl,
275 const struct rhash_head *he, const struct rhashtable_params params)
277 const char *ptr = rht_obj(ht, he);
279 return likely(params.obj_hashfn) ?
280 rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
283 rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
287 * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
289 * @tbl: current table
291 static inline bool rht_grow_above_75(const struct rhashtable *ht,
292 const struct bucket_table *tbl)
294 /* Expand table when exceeding 75% load */
295 return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
296 (!ht->p.max_size || tbl->size < ht->p.max_size);
300 * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
302 * @tbl: current table
304 static inline bool rht_shrink_below_30(const struct rhashtable *ht,
305 const struct bucket_table *tbl)
307 /* Shrink table beneath 30% load */
308 return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
309 tbl->size > ht->p.min_size;
313 * rht_grow_above_100 - returns true if nelems > table-size
315 * @tbl: current table
317 static inline bool rht_grow_above_100(const struct rhashtable *ht,
318 const struct bucket_table *tbl)
320 return atomic_read(&ht->nelems) > tbl->size &&
321 (!ht->p.max_size || tbl->size < ht->p.max_size);
325 * rht_grow_above_max - returns true if table is above maximum
327 * @tbl: current table
329 static inline bool rht_grow_above_max(const struct rhashtable *ht,
330 const struct bucket_table *tbl)
332 return atomic_read(&ht->nelems) >= ht->max_elems;
335 /* The bucket lock is selected based on the hash and protects mutations
336 * on a group of hash buckets.
338 * A maximum of tbl->size/2 bucket locks is allocated. This ensures that
339 * a single lock always covers both buckets which may both contains
340 * entries which link to the same bucket of the old table during resizing.
341 * This allows to simplify the locking as locking the bucket in both
342 * tables during resize always guarantee protection.
344 * IMPORTANT: When holding the bucket lock of both the old and new table
345 * during expansions and shrinking, the old bucket lock must always be
348 static inline spinlock_t *rht_bucket_lock(const struct bucket_table *tbl,
351 return &tbl->locks[hash & tbl->locks_mask];
354 #ifdef CONFIG_PROVE_LOCKING
355 int lockdep_rht_mutex_is_held(struct rhashtable *ht);
356 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
358 static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
363 static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
368 #endif /* CONFIG_PROVE_LOCKING */
370 int rhashtable_init(struct rhashtable *ht,
371 const struct rhashtable_params *params);
372 int rhltable_init(struct rhltable *hlt,
373 const struct rhashtable_params *params);
375 void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
376 struct rhash_head *obj);
378 void rhashtable_walk_enter(struct rhashtable *ht,
379 struct rhashtable_iter *iter);
380 void rhashtable_walk_exit(struct rhashtable_iter *iter);
381 int rhashtable_walk_start(struct rhashtable_iter *iter) __acquires(RCU);
382 void *rhashtable_walk_next(struct rhashtable_iter *iter);
383 void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
385 void rhashtable_free_and_destroy(struct rhashtable *ht,
386 void (*free_fn)(void *ptr, void *arg),
388 void rhashtable_destroy(struct rhashtable *ht);
390 struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
392 struct rhash_head __rcu **rht_bucket_nested_insert(struct rhashtable *ht,
393 struct bucket_table *tbl,
396 #define rht_dereference(p, ht) \
397 rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
399 #define rht_dereference_rcu(p, ht) \
400 rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))
402 #define rht_dereference_bucket(p, tbl, hash) \
403 rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
405 #define rht_dereference_bucket_rcu(p, tbl, hash) \
406 rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
408 #define rht_entry(tpos, pos, member) \
409 ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
411 static inline struct rhash_head __rcu *const *rht_bucket(
412 const struct bucket_table *tbl, unsigned int hash)
414 return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) :
418 static inline struct rhash_head __rcu **rht_bucket_var(
419 struct bucket_table *tbl, unsigned int hash)
421 return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) :
425 static inline struct rhash_head __rcu **rht_bucket_insert(
426 struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)
428 return unlikely(tbl->nest) ? rht_bucket_nested_insert(ht, tbl, hash) :
433 * rht_for_each_continue - continue iterating over hash chain
434 * @pos: the &struct rhash_head to use as a loop cursor.
435 * @head: the previous &struct rhash_head to continue from
436 * @tbl: the &struct bucket_table
437 * @hash: the hash value / bucket index
439 #define rht_for_each_continue(pos, head, tbl, hash) \
440 for (pos = rht_dereference_bucket(head, tbl, hash); \
441 !rht_is_a_nulls(pos); \
442 pos = rht_dereference_bucket((pos)->next, tbl, hash))
445 * rht_for_each - iterate over hash chain
446 * @pos: the &struct rhash_head to use as a loop cursor.
447 * @tbl: the &struct bucket_table
448 * @hash: the hash value / bucket index
450 #define rht_for_each(pos, tbl, hash) \
451 rht_for_each_continue(pos, *rht_bucket(tbl, hash), tbl, hash)
454 * rht_for_each_entry_continue - continue iterating over hash chain
455 * @tpos: the type * to use as a loop cursor.
456 * @pos: the &struct rhash_head to use as a loop cursor.
457 * @head: the previous &struct rhash_head to continue from
458 * @tbl: the &struct bucket_table
459 * @hash: the hash value / bucket index
460 * @member: name of the &struct rhash_head within the hashable struct.
462 #define rht_for_each_entry_continue(tpos, pos, head, tbl, hash, member) \
463 for (pos = rht_dereference_bucket(head, tbl, hash); \
464 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
465 pos = rht_dereference_bucket((pos)->next, tbl, hash))
468 * rht_for_each_entry - iterate over hash chain of given type
469 * @tpos: the type * to use as a loop cursor.
470 * @pos: the &struct rhash_head to use as a loop cursor.
471 * @tbl: the &struct bucket_table
472 * @hash: the hash value / bucket index
473 * @member: name of the &struct rhash_head within the hashable struct.
475 #define rht_for_each_entry(tpos, pos, tbl, hash, member) \
476 rht_for_each_entry_continue(tpos, pos, *rht_bucket(tbl, hash), \
480 * rht_for_each_entry_safe - safely iterate over hash chain of given type
481 * @tpos: the type * to use as a loop cursor.
482 * @pos: the &struct rhash_head to use as a loop cursor.
483 * @next: the &struct rhash_head to use as next in loop cursor.
484 * @tbl: the &struct bucket_table
485 * @hash: the hash value / bucket index
486 * @member: name of the &struct rhash_head within the hashable struct.
488 * This hash chain list-traversal primitive allows for the looped code to
489 * remove the loop cursor from the list.
491 #define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member) \
492 for (pos = rht_dereference_bucket(*rht_bucket(tbl, hash), tbl, hash), \
493 next = !rht_is_a_nulls(pos) ? \
494 rht_dereference_bucket(pos->next, tbl, hash) : NULL; \
495 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
497 next = !rht_is_a_nulls(pos) ? \
498 rht_dereference_bucket(pos->next, tbl, hash) : NULL)
501 * rht_for_each_rcu_continue - continue iterating over rcu hash chain
502 * @pos: the &struct rhash_head to use as a loop cursor.
503 * @head: the previous &struct rhash_head to continue from
504 * @tbl: the &struct bucket_table
505 * @hash: the hash value / bucket index
507 * This hash chain list-traversal primitive may safely run concurrently with
508 * the _rcu mutation primitives such as rhashtable_insert() as long as the
509 * traversal is guarded by rcu_read_lock().
511 #define rht_for_each_rcu_continue(pos, head, tbl, hash) \
512 for (({barrier(); }), \
513 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
514 !rht_is_a_nulls(pos); \
515 pos = rcu_dereference_raw(pos->next))
518 * rht_for_each_rcu - iterate over rcu hash chain
519 * @pos: the &struct rhash_head to use as a loop cursor.
520 * @tbl: the &struct bucket_table
521 * @hash: the hash value / bucket index
523 * This hash chain list-traversal primitive may safely run concurrently with
524 * the _rcu mutation primitives such as rhashtable_insert() as long as the
525 * traversal is guarded by rcu_read_lock().
527 #define rht_for_each_rcu(pos, tbl, hash) \
528 rht_for_each_rcu_continue(pos, *rht_bucket(tbl, hash), tbl, hash)
531 * rht_for_each_entry_rcu_continue - continue iterating over rcu hash chain
532 * @tpos: the type * to use as a loop cursor.
533 * @pos: the &struct rhash_head to use as a loop cursor.
534 * @head: the previous &struct rhash_head to continue from
535 * @tbl: the &struct bucket_table
536 * @hash: the hash value / bucket index
537 * @member: name of the &struct rhash_head within the hashable struct.
539 * This hash chain list-traversal primitive may safely run concurrently with
540 * the _rcu mutation primitives such as rhashtable_insert() as long as the
541 * traversal is guarded by rcu_read_lock().
543 #define rht_for_each_entry_rcu_continue(tpos, pos, head, tbl, hash, member) \
544 for (({barrier(); }), \
545 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
546 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
547 pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
550 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
551 * @tpos: the type * to use as a loop cursor.
552 * @pos: the &struct rhash_head to use as a loop cursor.
553 * @tbl: the &struct bucket_table
554 * @hash: the hash value / bucket index
555 * @member: name of the &struct rhash_head within the hashable struct.
557 * This hash chain list-traversal primitive may safely run concurrently with
558 * the _rcu mutation primitives such as rhashtable_insert() as long as the
559 * traversal is guarded by rcu_read_lock().
561 #define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \
562 rht_for_each_entry_rcu_continue(tpos, pos, *rht_bucket(tbl, hash), \
566 * rhl_for_each_rcu - iterate over rcu hash table list
567 * @pos: the &struct rlist_head to use as a loop cursor.
568 * @list: the head of the list
570 * This hash chain list-traversal primitive should be used on the
571 * list returned by rhltable_lookup.
573 #define rhl_for_each_rcu(pos, list) \
574 for (pos = list; pos; pos = rcu_dereference_raw(pos->next))
577 * rhl_for_each_entry_rcu - iterate over rcu hash table list of given type
578 * @tpos: the type * to use as a loop cursor.
579 * @pos: the &struct rlist_head to use as a loop cursor.
580 * @list: the head of the list
581 * @member: name of the &struct rlist_head within the hashable struct.
583 * This hash chain list-traversal primitive should be used on the
584 * list returned by rhltable_lookup.
586 #define rhl_for_each_entry_rcu(tpos, pos, list, member) \
587 for (pos = list; pos && rht_entry(tpos, pos, member); \
588 pos = rcu_dereference_raw(pos->next))
590 static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
593 struct rhashtable *ht = arg->ht;
594 const char *ptr = obj;
596 return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
599 /* Internal function, do not use. */
600 static inline struct rhash_head *__rhashtable_lookup(
601 struct rhashtable *ht, const void *key,
602 const struct rhashtable_params params)
604 struct rhashtable_compare_arg arg = {
608 struct bucket_table *tbl;
609 struct rhash_head *he;
612 tbl = rht_dereference_rcu(ht->tbl, ht);
614 hash = rht_key_hashfn(ht, tbl, key, params);
615 rht_for_each_rcu(he, tbl, hash) {
616 if (params.obj_cmpfn ?
617 params.obj_cmpfn(&arg, rht_obj(ht, he)) :
618 rhashtable_compare(&arg, rht_obj(ht, he)))
623 /* Ensure we see any new tables. */
626 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
634 * rhashtable_lookup - search hash table
636 * @key: the pointer to the key
637 * @params: hash table parameters
639 * Computes the hash value for the key and traverses the bucket chain looking
640 * for a entry with an identical key. The first matching entry is returned.
642 * This must only be called under the RCU read lock.
644 * Returns the first entry on which the compare function returned true.
646 static inline void *rhashtable_lookup(
647 struct rhashtable *ht, const void *key,
648 const struct rhashtable_params params)
650 struct rhash_head *he = __rhashtable_lookup(ht, key, params);
652 return he ? rht_obj(ht, he) : NULL;
656 * rhashtable_lookup_fast - search hash table, without RCU read lock
658 * @key: the pointer to the key
659 * @params: hash table parameters
661 * Computes the hash value for the key and traverses the bucket chain looking
662 * for a entry with an identical key. The first matching entry is returned.
664 * Only use this function when you have other mechanisms guaranteeing
665 * that the object won't go away after the RCU read lock is released.
667 * Returns the first entry on which the compare function returned true.
669 static inline void *rhashtable_lookup_fast(
670 struct rhashtable *ht, const void *key,
671 const struct rhashtable_params params)
676 obj = rhashtable_lookup(ht, key, params);
683 * rhltable_lookup - search hash list table
685 * @key: the pointer to the key
686 * @params: hash table parameters
688 * Computes the hash value for the key and traverses the bucket chain looking
689 * for a entry with an identical key. All matching entries are returned
692 * This must only be called under the RCU read lock.
694 * Returns the list of entries that match the given key.
696 static inline struct rhlist_head *rhltable_lookup(
697 struct rhltable *hlt, const void *key,
698 const struct rhashtable_params params)
700 struct rhash_head *he = __rhashtable_lookup(&hlt->ht, key, params);
702 return he ? container_of(he, struct rhlist_head, rhead) : NULL;
705 /* Internal function, please use rhashtable_insert_fast() instead. This
706 * function returns the existing element already in hashes in there is a clash,
707 * otherwise it returns an error via ERR_PTR().
709 static inline void *__rhashtable_insert_fast(
710 struct rhashtable *ht, const void *key, struct rhash_head *obj,
711 const struct rhashtable_params params, bool rhlist)
713 struct rhashtable_compare_arg arg = {
717 struct rhash_head __rcu **pprev;
718 struct bucket_table *tbl;
719 struct rhash_head *head;
727 tbl = rht_dereference_rcu(ht->tbl, ht);
728 hash = rht_head_hashfn(ht, tbl, obj, params);
729 lock = rht_bucket_lock(tbl, hash);
732 if (unlikely(rht_dereference_bucket(tbl->future_tbl, tbl, hash))) {
734 spin_unlock_bh(lock);
736 return rhashtable_insert_slow(ht, key, obj);
739 elasticity = RHT_ELASTICITY;
740 pprev = rht_bucket_insert(ht, tbl, hash);
741 data = ERR_PTR(-ENOMEM);
745 rht_for_each_continue(head, *pprev, tbl, hash) {
746 struct rhlist_head *plist;
747 struct rhlist_head *list;
752 params.obj_cmpfn(&arg, rht_obj(ht, head)) :
753 rhashtable_compare(&arg, rht_obj(ht, head)))) {
758 data = rht_obj(ht, head);
764 list = container_of(obj, struct rhlist_head, rhead);
765 plist = container_of(head, struct rhlist_head, rhead);
767 RCU_INIT_POINTER(list->next, plist);
768 head = rht_dereference_bucket(head->next, tbl, hash);
769 RCU_INIT_POINTER(list->rhead.next, head);
770 rcu_assign_pointer(*pprev, obj);
778 data = ERR_PTR(-E2BIG);
779 if (unlikely(rht_grow_above_max(ht, tbl)))
782 if (unlikely(rht_grow_above_100(ht, tbl)))
785 head = rht_dereference_bucket(*pprev, tbl, hash);
787 RCU_INIT_POINTER(obj->next, head);
789 struct rhlist_head *list;
791 list = container_of(obj, struct rhlist_head, rhead);
792 RCU_INIT_POINTER(list->next, NULL);
795 rcu_assign_pointer(*pprev, obj);
797 atomic_inc(&ht->nelems);
798 if (rht_grow_above_75(ht, tbl))
799 schedule_work(&ht->run_work);
805 spin_unlock_bh(lock);
812 * rhashtable_insert_fast - insert object into hash table
814 * @obj: pointer to hash head inside object
815 * @params: hash table parameters
817 * Will take a per bucket spinlock to protect against mutual mutations
818 * on the same bucket. Multiple insertions may occur in parallel unless
819 * they map to the same bucket lock.
821 * It is safe to call this function from atomic context.
823 * Will trigger an automatic deferred table resizing if the size grows
824 * beyond the watermark indicated by grow_decision() which can be passed
825 * to rhashtable_init().
827 static inline int rhashtable_insert_fast(
828 struct rhashtable *ht, struct rhash_head *obj,
829 const struct rhashtable_params params)
833 ret = __rhashtable_insert_fast(ht, NULL, obj, params, false);
837 return ret == NULL ? 0 : -EEXIST;
841 * rhltable_insert_key - insert object into hash list table
842 * @hlt: hash list table
843 * @key: the pointer to the key
844 * @list: pointer to hash list head inside object
845 * @params: hash table parameters
847 * Will take a per bucket spinlock to protect against mutual mutations
848 * on the same bucket. Multiple insertions may occur in parallel unless
849 * they map to the same bucket lock.
851 * It is safe to call this function from atomic context.
853 * Will trigger an automatic deferred table resizing if the size grows
854 * beyond the watermark indicated by grow_decision() which can be passed
855 * to rhashtable_init().
857 static inline int rhltable_insert_key(
858 struct rhltable *hlt, const void *key, struct rhlist_head *list,
859 const struct rhashtable_params params)
861 return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
866 * rhltable_insert - insert object into hash list table
867 * @hlt: hash list table
868 * @list: pointer to hash list head inside object
869 * @params: hash table parameters
871 * Will take a per bucket spinlock to protect against mutual mutations
872 * on the same bucket. Multiple insertions may occur in parallel unless
873 * they map to the same bucket lock.
875 * It is safe to call this function from atomic context.
877 * Will trigger an automatic deferred table resizing if the size grows
878 * beyond the watermark indicated by grow_decision() which can be passed
879 * to rhashtable_init().
881 static inline int rhltable_insert(
882 struct rhltable *hlt, struct rhlist_head *list,
883 const struct rhashtable_params params)
885 const char *key = rht_obj(&hlt->ht, &list->rhead);
887 key += params.key_offset;
889 return rhltable_insert_key(hlt, key, list, params);
893 * rhashtable_lookup_insert_fast - lookup and insert object into hash table
895 * @obj: pointer to hash head inside object
896 * @params: hash table parameters
898 * Locks down the bucket chain in both the old and new table if a resize
899 * is in progress to ensure that writers can't remove from the old table
900 * and can't insert to the new table during the atomic operation of search
901 * and insertion. Searches for duplicates in both the old and new table if
902 * a resize is in progress.
904 * This lookup function may only be used for fixed key hash table (key_len
905 * parameter set). It will BUG() if used inappropriately.
907 * It is safe to call this function from atomic context.
909 * Will trigger an automatic deferred table resizing if the size grows
910 * beyond the watermark indicated by grow_decision() which can be passed
911 * to rhashtable_init().
913 static inline int rhashtable_lookup_insert_fast(
914 struct rhashtable *ht, struct rhash_head *obj,
915 const struct rhashtable_params params)
917 const char *key = rht_obj(ht, obj);
920 BUG_ON(ht->p.obj_hashfn);
922 ret = __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
927 return ret == NULL ? 0 : -EEXIST;
931 * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
933 * @obj: pointer to hash head inside object
934 * @params: hash table parameters
936 * Just like rhashtable_lookup_insert_fast(), but this function returns the
937 * object if it exists, NULL if it did not and the insertion was successful,
938 * and an ERR_PTR otherwise.
940 static inline void *rhashtable_lookup_get_insert_fast(
941 struct rhashtable *ht, struct rhash_head *obj,
942 const struct rhashtable_params params)
944 const char *key = rht_obj(ht, obj);
946 BUG_ON(ht->p.obj_hashfn);
948 return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
953 * rhashtable_lookup_insert_key - search and insert object to hash table
957 * @obj: pointer to hash head inside object
958 * @params: hash table parameters
960 * Locks down the bucket chain in both the old and new table if a resize
961 * is in progress to ensure that writers can't remove from the old table
962 * and can't insert to the new table during the atomic operation of search
963 * and insertion. Searches for duplicates in both the old and new table if
964 * a resize is in progress.
966 * Lookups may occur in parallel with hashtable mutations and resizing.
968 * Will trigger an automatic deferred table resizing if the size grows
969 * beyond the watermark indicated by grow_decision() which can be passed
970 * to rhashtable_init().
972 * Returns zero on success.
974 static inline int rhashtable_lookup_insert_key(
975 struct rhashtable *ht, const void *key, struct rhash_head *obj,
976 const struct rhashtable_params params)
980 BUG_ON(!ht->p.obj_hashfn || !key);
982 ret = __rhashtable_insert_fast(ht, key, obj, params, false);
986 return ret == NULL ? 0 : -EEXIST;
990 * rhashtable_lookup_get_insert_key - lookup and insert object into hash table
992 * @obj: pointer to hash head inside object
993 * @params: hash table parameters
994 * @data: pointer to element data already in hashes
996 * Just like rhashtable_lookup_insert_key(), but this function returns the
997 * object if it exists, NULL if it does not and the insertion was successful,
998 * and an ERR_PTR otherwise.
1000 static inline void *rhashtable_lookup_get_insert_key(
1001 struct rhashtable *ht, const void *key, struct rhash_head *obj,
1002 const struct rhashtable_params params)
1004 BUG_ON(!ht->p.obj_hashfn || !key);
1006 return __rhashtable_insert_fast(ht, key, obj, params, false);
1009 /* Internal function, please use rhashtable_remove_fast() instead */
1010 static inline int __rhashtable_remove_fast_one(
1011 struct rhashtable *ht, struct bucket_table *tbl,
1012 struct rhash_head *obj, const struct rhashtable_params params,
1015 struct rhash_head __rcu **pprev;
1016 struct rhash_head *he;
1021 hash = rht_head_hashfn(ht, tbl, obj, params);
1022 lock = rht_bucket_lock(tbl, hash);
1026 pprev = rht_bucket_var(tbl, hash);
1027 rht_for_each_continue(he, *pprev, tbl, hash) {
1028 struct rhlist_head *list;
1030 list = container_of(he, struct rhlist_head, rhead);
1033 struct rhlist_head __rcu **lpprev;
1041 lpprev = &list->next;
1042 list = rht_dereference_bucket(list->next,
1044 } while (list && obj != &list->rhead);
1049 list = rht_dereference_bucket(list->next, tbl, hash);
1050 RCU_INIT_POINTER(*lpprev, list);
1055 obj = rht_dereference_bucket(obj->next, tbl, hash);
1059 list = rht_dereference_bucket(list->next, tbl, hash);
1061 RCU_INIT_POINTER(list->rhead.next, obj);
1067 rcu_assign_pointer(*pprev, obj);
1071 spin_unlock_bh(lock);
1074 atomic_dec(&ht->nelems);
1075 if (unlikely(ht->p.automatic_shrinking &&
1076 rht_shrink_below_30(ht, tbl)))
1077 schedule_work(&ht->run_work);
1084 /* Internal function, please use rhashtable_remove_fast() instead */
1085 static inline int __rhashtable_remove_fast(
1086 struct rhashtable *ht, struct rhash_head *obj,
1087 const struct rhashtable_params params, bool rhlist)
1089 struct bucket_table *tbl;
1094 tbl = rht_dereference_rcu(ht->tbl, ht);
1096 /* Because we have already taken (and released) the bucket
1097 * lock in old_tbl, if we find that future_tbl is not yet
1098 * visible then that guarantees the entry to still be in
1099 * the old tbl if it exists.
1101 while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params,
1103 (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1112 * rhashtable_remove_fast - remove object from hash table
1114 * @obj: pointer to hash head inside object
1115 * @params: hash table parameters
1117 * Since the hash chain is single linked, the removal operation needs to
1118 * walk the bucket chain upon removal. The removal operation is thus
1119 * considerable slow if the hash table is not correctly sized.
1121 * Will automatically shrink the table via rhashtable_expand() if the
1122 * shrink_decision function specified at rhashtable_init() returns true.
1124 * Returns zero on success, -ENOENT if the entry could not be found.
1126 static inline int rhashtable_remove_fast(
1127 struct rhashtable *ht, struct rhash_head *obj,
1128 const struct rhashtable_params params)
1130 return __rhashtable_remove_fast(ht, obj, params, false);
1134 * rhltable_remove - remove object from hash list table
1135 * @hlt: hash list table
1136 * @list: pointer to hash list head inside object
1137 * @params: hash table parameters
1139 * Since the hash chain is single linked, the removal operation needs to
1140 * walk the bucket chain upon removal. The removal operation is thus
1141 * considerable slow if the hash table is not correctly sized.
1143 * Will automatically shrink the table via rhashtable_expand() if the
1144 * shrink_decision function specified at rhashtable_init() returns true.
1146 * Returns zero on success, -ENOENT if the entry could not be found.
1148 static inline int rhltable_remove(
1149 struct rhltable *hlt, struct rhlist_head *list,
1150 const struct rhashtable_params params)
1152 return __rhashtable_remove_fast(&hlt->ht, &list->rhead, params, true);
1155 /* Internal function, please use rhashtable_replace_fast() instead */
1156 static inline int __rhashtable_replace_fast(
1157 struct rhashtable *ht, struct bucket_table *tbl,
1158 struct rhash_head *obj_old, struct rhash_head *obj_new,
1159 const struct rhashtable_params params)
1161 struct rhash_head __rcu **pprev;
1162 struct rhash_head *he;
1167 /* Minimally, the old and new objects must have same hash
1168 * (which should mean identifiers are the same).
1170 hash = rht_head_hashfn(ht, tbl, obj_old, params);
1171 if (hash != rht_head_hashfn(ht, tbl, obj_new, params))
1174 lock = rht_bucket_lock(tbl, hash);
1178 pprev = rht_bucket_var(tbl, hash);
1179 rht_for_each_continue(he, *pprev, tbl, hash) {
1180 if (he != obj_old) {
1185 rcu_assign_pointer(obj_new->next, obj_old->next);
1186 rcu_assign_pointer(*pprev, obj_new);
1191 spin_unlock_bh(lock);
1197 * rhashtable_replace_fast - replace an object in hash table
1199 * @obj_old: pointer to hash head inside object being replaced
1200 * @obj_new: pointer to hash head inside object which is new
1201 * @params: hash table parameters
1203 * Replacing an object doesn't affect the number of elements in the hash table
1204 * or bucket, so we don't need to worry about shrinking or expanding the
1207 * Returns zero on success, -ENOENT if the entry could not be found,
1208 * -EINVAL if hash is not the same for the old and new objects.
1210 static inline int rhashtable_replace_fast(
1211 struct rhashtable *ht, struct rhash_head *obj_old,
1212 struct rhash_head *obj_new,
1213 const struct rhashtable_params params)
1215 struct bucket_table *tbl;
1220 tbl = rht_dereference_rcu(ht->tbl, ht);
1222 /* Because we have already taken (and released) the bucket
1223 * lock in old_tbl, if we find that future_tbl is not yet
1224 * visible then that guarantees the entry to still be in
1225 * the old tbl if it exists.
1227 while ((err = __rhashtable_replace_fast(ht, tbl, obj_old,
1228 obj_new, params)) &&
1229 (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1237 /* Obsolete function, do not use in new code. */
1238 static inline int rhashtable_walk_init(struct rhashtable *ht,
1239 struct rhashtable_iter *iter, gfp_t gfp)
1241 rhashtable_walk_enter(ht, iter);
1246 * rhltable_walk_enter - Initialise an iterator
1247 * @hlt: Table to walk over
1248 * @iter: Hash table Iterator
1250 * This function prepares a hash table walk.
1252 * Note that if you restart a walk after rhashtable_walk_stop you
1253 * may see the same object twice. Also, you may miss objects if
1254 * there are removals in between rhashtable_walk_stop and the next
1255 * call to rhashtable_walk_start.
1257 * For a completely stable walk you should construct your own data
1258 * structure outside the hash table.
1260 * This function may sleep so you must not call it from interrupt
1261 * context or with spin locks held.
1263 * You must call rhashtable_walk_exit after this function returns.
1265 static inline void rhltable_walk_enter(struct rhltable *hlt,
1266 struct rhashtable_iter *iter)
1268 return rhashtable_walk_enter(&hlt->ht, iter);
1272 * rhltable_free_and_destroy - free elements and destroy hash list table
1273 * @hlt: the hash list table to destroy
1274 * @free_fn: callback to release resources of element
1275 * @arg: pointer passed to free_fn
1277 * See documentation for rhashtable_free_and_destroy.
1279 static inline void rhltable_free_and_destroy(struct rhltable *hlt,
1280 void (*free_fn)(void *ptr,
1284 return rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);
1287 static inline void rhltable_destroy(struct rhltable *hlt)
1289 return rhltable_free_and_destroy(hlt, NULL, NULL);
1292 #endif /* _LINUX_RHASHTABLE_H */