2 * Resizable, Scalable, Concurrent Hash Table
4 * Copyright (c) 2015 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/cache.h>
22 #include <linux/compiler.h>
23 #include <linux/err.h>
24 #include <linux/errno.h>
25 #include <linux/jhash.h>
26 #include <linux/workqueue.h>
27 #include <linux/mutex.h>
28 #include <linux/spinlock.h>
29 #include <linux/rcupdate.h>
31 #define RHT_BASE_BITS 4
32 #define RHT_HASH_BITS 27
33 #define RHT_BASE_SHIFT RHT_HASH_BITS
34 #define RHT_HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
37 struct rhash_head __rcu *next;
44 unsigned int locks_mask;
46 struct list_head walkers;
49 struct bucket_table __rcu *future_tbl;
51 struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp;
54 struct rhashtable_compare_arg {
55 struct rhashtable *ht;
59 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
60 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
61 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
64 struct rhashtable_params {
69 unsigned int insecure_max_entries;
70 unsigned int max_size;
71 unsigned int min_size;
73 bool insecure_elasticity;
74 bool automatic_shrinking;
77 rht_obj_hashfn_t obj_hashfn;
78 rht_obj_cmpfn_t obj_cmpfn;
82 struct bucket_table __rcu *tbl;
85 unsigned int elasticity;
86 struct rhashtable_params p;
87 struct work_struct run_work;
92 struct rhashtable_walker {
93 struct list_head list;
94 struct bucket_table *tbl;
97 #define NULLS_MARKER(value) (1UL | (((long)value) << 1))
99 static inline unsigned long rht_marker(const struct rhashtable *ht, u32 hash)
101 return NULLS_MARKER(ht->p.nulls_base + hash);
104 #define INIT_RHT_NULLS_HEAD(ptr, ht, hash) \
105 ((ptr) = (typeof(ptr)) rht_marker(ht, hash))
107 static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
109 return ((unsigned long) ptr & 1);
112 static inline void *rht_obj(const struct rhashtable *ht,
113 const struct rhash_head *he)
115 return (char *)he - ht->p.head_offset;
118 static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
121 return (hash >> RHT_HASH_RESERVED_SPACE) & (tbl->size - 1);
124 static inline unsigned int rht_key_hashfn(
125 struct rhashtable *ht, const struct bucket_table *tbl,
126 const void *key, const struct rhashtable_params params)
130 /* params must be equal to ht->p if it isn't constant. */
131 if (!__builtin_constant_p(params.key_len))
132 hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd);
133 else if (params.key_len) {
134 unsigned int key_len = params.key_len;
137 hash = params.hashfn(key, key_len, tbl->hash_rnd);
138 else if (key_len & (sizeof(u32) - 1))
139 hash = jhash(key, key_len, tbl->hash_rnd);
141 hash = jhash2(key, key_len / sizeof(u32),
144 unsigned int key_len = ht->p.key_len;
147 hash = params.hashfn(key, key_len, tbl->hash_rnd);
149 hash = jhash(key, key_len, tbl->hash_rnd);
152 return rht_bucket_index(tbl, hash);
155 static inline unsigned int rht_head_hashfn(
156 struct rhashtable *ht, const struct bucket_table *tbl,
157 const struct rhash_head *he, const struct rhashtable_params params)
159 const char *ptr = rht_obj(ht, he);
161 return likely(params.obj_hashfn) ?
162 rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
165 rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
168 static inline bool rht_grow_above_75(const struct rhashtable *ht,
169 const struct bucket_table *tbl)
171 /* Expand table when exceeding 75% load */
172 return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
173 (!ht->p.max_size || tbl->size < ht->p.max_size);
176 static inline bool rht_shrink_below_30(const struct rhashtable *ht,
177 const struct bucket_table *tbl)
179 /* Shrink table beneath 30% load */
180 return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
181 tbl->size > ht->p.min_size;
184 static inline bool rht_grow_above_100(const struct rhashtable *ht,
185 const struct bucket_table *tbl)
187 return atomic_read(&ht->nelems) > tbl->size &&
188 (!ht->p.max_size || tbl->size < ht->p.max_size);
191 static inline bool rht_grow_above_max(const struct rhashtable *ht,
192 const struct bucket_table *tbl)
194 return ht->p.insecure_max_entries &&
195 atomic_read(&ht->nelems) >= ht->p.insecure_max_entries;
198 static inline spinlock_t *rht_bucket_lock(const struct bucket_table *tbl,
201 return &tbl->locks[hash & tbl->locks_mask];
204 int rhashtable_insert_rehash(struct rhashtable *, struct bucket_table *);
205 struct bucket_table *rhashtable_insert_slow(struct rhashtable *,
208 struct bucket_table *);
210 int rhashtable_init(struct rhashtable *, const struct rhashtable_params *);
211 void rhashtable_destroy(struct rhashtable *);
213 #define rht_dereference(p, ht) rcu_dereference(p)
214 #define rht_dereference_rcu(p, ht) rcu_dereference(p)
215 #define rht_dereference_bucket(p, tbl, hash) rcu_dereference(p)
216 #define rht_dereference_bucket_rcu(p, tbl, hash) rcu_dereference(p)
218 #define rht_entry(tpos, pos, member) \
219 ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
221 #define rht_for_each_continue(pos, head, tbl, hash) \
222 for (pos = rht_dereference_bucket(head, tbl, hash); \
223 !rht_is_a_nulls(pos); \
224 pos = rht_dereference_bucket((pos)->next, tbl, hash))
226 #define rht_for_each(pos, tbl, hash) \
227 rht_for_each_continue(pos, (tbl)->buckets[hash], tbl, hash)
229 #define rht_for_each_rcu_continue(pos, head, tbl, hash) \
230 for (({barrier(); }), \
231 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
232 !rht_is_a_nulls(pos); \
233 pos = rcu_dereference_raw(pos->next))
235 #define rht_for_each_rcu(pos, tbl, hash) \
236 rht_for_each_rcu_continue(pos, (tbl)->buckets[hash], tbl, hash)
238 #define rht_for_each_entry_rcu_continue(tpos, pos, head, tbl, hash, member) \
239 for (({barrier(); }), \
240 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
241 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
242 pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
244 #define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \
245 rht_for_each_entry_rcu_continue(tpos, pos, (tbl)->buckets[hash],\
248 static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
251 struct rhashtable *ht = arg->ht;
252 const char *ptr = obj;
254 return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
257 static inline void *rhashtable_lookup_fast(
258 struct rhashtable *ht, const void *key,
259 const struct rhashtable_params params)
261 struct rhashtable_compare_arg arg = {
265 const struct bucket_table *tbl;
266 struct rhash_head *he;
271 tbl = rht_dereference_rcu(ht->tbl, ht);
273 hash = rht_key_hashfn(ht, tbl, key, params);
274 rht_for_each_rcu(he, tbl, hash) {
275 if (params.obj_cmpfn ?
276 params.obj_cmpfn(&arg, rht_obj(ht, he)) :
277 rhashtable_compare(&arg, rht_obj(ht, he)))
280 return rht_obj(ht, he);
283 /* Ensure we see any new tables. */
286 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
294 static inline int __rhashtable_insert_fast(
295 struct rhashtable *ht, const void *key, struct rhash_head *obj,
296 const struct rhashtable_params params)
298 struct rhashtable_compare_arg arg = {
302 struct bucket_table *tbl, *new_tbl;
303 struct rhash_head *head;
305 unsigned int elasticity;
312 tbl = rht_dereference_rcu(ht->tbl, ht);
314 /* All insertions must grab the oldest table containing
315 * the hashed bucket that is yet to be rehashed.
318 hash = rht_head_hashfn(ht, tbl, obj, params);
319 lock = rht_bucket_lock(tbl, hash);
322 if (tbl->rehash <= hash)
325 spin_unlock_bh(lock);
326 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
329 new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
330 if (unlikely(new_tbl)) {
331 tbl = rhashtable_insert_slow(ht, key, obj, new_tbl);
332 if (!IS_ERR_OR_NULL(tbl))
340 if (unlikely(rht_grow_above_max(ht, tbl)))
343 if (unlikely(rht_grow_above_100(ht, tbl))) {
345 spin_unlock_bh(lock);
346 err = rhashtable_insert_rehash(ht, tbl);
355 elasticity = ht->elasticity;
356 rht_for_each(head, tbl, hash) {
358 unlikely(!(params.obj_cmpfn ?
359 params.obj_cmpfn(&arg, rht_obj(ht, head)) :
360 rhashtable_compare(&arg, rht_obj(ht, head)))))
368 head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
370 RCU_INIT_POINTER(obj->next, head);
372 rcu_assign_pointer(tbl->buckets[hash], obj);
374 atomic_inc(&ht->nelems);
375 if (rht_grow_above_75(ht, tbl))
376 schedule_work(&ht->run_work);
379 spin_unlock_bh(lock);
385 static inline int rhashtable_lookup_insert_fast(
386 struct rhashtable *ht, struct rhash_head *obj,
387 const struct rhashtable_params params)
389 const char *key = rht_obj(ht, obj);
391 BUG_ON(ht->p.obj_hashfn);
393 return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj,
397 static inline int __rhashtable_remove_fast(
398 struct rhashtable *ht, struct bucket_table *tbl,
399 struct rhash_head *obj, const struct rhashtable_params params)
401 struct rhash_head __rcu **pprev;
402 struct rhash_head *he;
407 hash = rht_head_hashfn(ht, tbl, obj, params);
408 lock = rht_bucket_lock(tbl, hash);
412 pprev = &tbl->buckets[hash];
413 rht_for_each(he, tbl, hash) {
419 rcu_assign_pointer(*pprev, obj->next);
424 spin_unlock_bh(lock);
429 static inline int rhashtable_remove_fast(
430 struct rhashtable *ht, struct rhash_head *obj,
431 const struct rhashtable_params params)
433 struct bucket_table *tbl;
438 tbl = rht_dereference_rcu(ht->tbl, ht);
440 /* Because we have already taken (and released) the bucket
441 * lock in old_tbl, if we find that future_tbl is not yet
442 * visible then that guarantees the entry to still be in
443 * the old tbl if it exists.
445 while ((err = __rhashtable_remove_fast(ht, tbl, obj, params)) &&
446 (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
452 atomic_dec(&ht->nelems);
453 if (unlikely(ht->p.automatic_shrinking &&
454 rht_shrink_below_30(ht, tbl)))
455 schedule_work(&ht->run_work);
463 #endif /* _LINUX_RHASHTABLE_H */