aboutsummaryrefslogtreecommitdiffstats
path: root/include/linux/rhashtable.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/linux/rhashtable.h')
-rw-r--r--include/linux/rhashtable.h308
1 files changed, 231 insertions, 77 deletions
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index b93fd89b2e5e..58851275fed9 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -18,16 +18,45 @@
18#ifndef _LINUX_RHASHTABLE_H 18#ifndef _LINUX_RHASHTABLE_H
19#define _LINUX_RHASHTABLE_H 19#define _LINUX_RHASHTABLE_H
20 20
21#include <linux/rculist.h> 21#include <linux/compiler.h>
22#include <linux/list_nulls.h>
23#include <linux/workqueue.h>
24#include <linux/mutex.h>
25
26/*
27 * The end of the chain is marked with a special nulls marks which has
28 * the following format:
29 *
30 * +-------+-----------------------------------------------------+-+
31 * | Base | Hash |1|
32 * +-------+-----------------------------------------------------+-+
33 *
34 * Base (4 bits) : Reserved to distinguish between multiple tables.
35 * Specified via &struct rhashtable_params.nulls_base.
36 * Hash (27 bits): Full hash (unmasked) of first element added to bucket
37 * 1 (1 bit) : Nulls marker (always set)
38 *
39 * The remaining bits of the next pointer remain unused for now.
40 */
41#define RHT_BASE_BITS 4
42#define RHT_HASH_BITS 27
43#define RHT_BASE_SHIFT RHT_HASH_BITS
22 44
23struct rhash_head { 45struct rhash_head {
24 struct rhash_head __rcu *next; 46 struct rhash_head __rcu *next;
25}; 47};
26 48
27#define INIT_HASH_HEAD(ptr) ((ptr)->next = NULL) 49/**
28 50 * struct bucket_table - Table of hash buckets
51 * @size: Number of hash buckets
52 * @locks_mask: Mask to apply before accessing locks[]
53 * @locks: Array of spinlocks protecting individual buckets
54 * @buckets: size * hash buckets
55 */
29struct bucket_table { 56struct bucket_table {
30 size_t size; 57 size_t size;
58 unsigned int locks_mask;
59 spinlock_t *locks;
31 struct rhash_head __rcu *buckets[]; 60 struct rhash_head __rcu *buckets[];
32}; 61};
33 62
@@ -45,11 +74,16 @@ struct rhashtable;
45 * @hash_rnd: Seed to use while hashing 74 * @hash_rnd: Seed to use while hashing
46 * @max_shift: Maximum number of shifts while expanding 75 * @max_shift: Maximum number of shifts while expanding
47 * @min_shift: Minimum number of shifts while shrinking 76 * @min_shift: Minimum number of shifts while shrinking
77 * @nulls_base: Base value to generate nulls marker
78 * @locks_mul: Number of bucket locks to allocate per cpu (default: 128)
48 * @hashfn: Function to hash key 79 * @hashfn: Function to hash key
49 * @obj_hashfn: Function to hash object 80 * @obj_hashfn: Function to hash object
50 * @grow_decision: If defined, may return true if table should expand 81 * @grow_decision: If defined, may return true if table should expand
51 * @shrink_decision: If defined, may return true if table should shrink 82 * @shrink_decision: If defined, may return true if table should shrink
52 * @mutex_is_held: Must return true if protecting mutex is held 83 *
84 * Note: when implementing the grow and shrink decision function, min/max
85 * shift must be enforced, otherwise, resizing watermarks they set may be
86 * useless.
53 */ 87 */
54struct rhashtable_params { 88struct rhashtable_params {
55 size_t nelem_hint; 89 size_t nelem_hint;
@@ -59,36 +93,95 @@ struct rhashtable_params {
59 u32 hash_rnd; 93 u32 hash_rnd;
60 size_t max_shift; 94 size_t max_shift;
61 size_t min_shift; 95 size_t min_shift;
96 u32 nulls_base;
97 size_t locks_mul;
62 rht_hashfn_t hashfn; 98 rht_hashfn_t hashfn;
63 rht_obj_hashfn_t obj_hashfn; 99 rht_obj_hashfn_t obj_hashfn;
64 bool (*grow_decision)(const struct rhashtable *ht, 100 bool (*grow_decision)(const struct rhashtable *ht,
65 size_t new_size); 101 size_t new_size);
66 bool (*shrink_decision)(const struct rhashtable *ht, 102 bool (*shrink_decision)(const struct rhashtable *ht,
67 size_t new_size); 103 size_t new_size);
68#ifdef CONFIG_PROVE_LOCKING
69 int (*mutex_is_held)(void *parent);
70 void *parent;
71#endif
72}; 104};
73 105
74/** 106/**
75 * struct rhashtable - Hash table handle 107 * struct rhashtable - Hash table handle
76 * @tbl: Bucket table 108 * @tbl: Bucket table
109 * @future_tbl: Table under construction during expansion/shrinking
77 * @nelems: Number of elements in table 110 * @nelems: Number of elements in table
78 * @shift: Current size (1 << shift) 111 * @shift: Current size (1 << shift)
79 * @p: Configuration parameters 112 * @p: Configuration parameters
113 * @run_work: Deferred worker to expand/shrink asynchronously
114 * @mutex: Mutex to protect current/future table swapping
115 * @walkers: List of active walkers
116 * @being_destroyed: True if table is set up for destruction
80 */ 117 */
81struct rhashtable { 118struct rhashtable {
82 struct bucket_table __rcu *tbl; 119 struct bucket_table __rcu *tbl;
83 size_t nelems; 120 struct bucket_table __rcu *future_tbl;
84 size_t shift; 121 atomic_t nelems;
122 atomic_t shift;
85 struct rhashtable_params p; 123 struct rhashtable_params p;
124 struct work_struct run_work;
125 struct mutex mutex;
126 struct list_head walkers;
127 bool being_destroyed;
128};
129
130/**
131 * struct rhashtable_walker - Hash table walker
132 * @list: List entry on list of walkers
133 * @resize: Resize event occured
134 */
135struct rhashtable_walker {
136 struct list_head list;
137 bool resize;
86}; 138};
87 139
140/**
141 * struct rhashtable_iter - Hash table iterator, fits into netlink cb
142 * @ht: Table to iterate through
143 * @p: Current pointer
144 * @walker: Associated rhashtable walker
145 * @slot: Current slot
146 * @skip: Number of entries to skip in slot
147 */
148struct rhashtable_iter {
149 struct rhashtable *ht;
150 struct rhash_head *p;
151 struct rhashtable_walker *walker;
152 unsigned int slot;
153 unsigned int skip;
154};
155
156static inline unsigned long rht_marker(const struct rhashtable *ht, u32 hash)
157{
158 return NULLS_MARKER(ht->p.nulls_base + hash);
159}
160
161#define INIT_RHT_NULLS_HEAD(ptr, ht, hash) \
162 ((ptr) = (typeof(ptr)) rht_marker(ht, hash))
163
164static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
165{
166 return ((unsigned long) ptr & 1);
167}
168
169static inline unsigned long rht_get_nulls_value(const struct rhash_head *ptr)
170{
171 return ((unsigned long) ptr) >> 1;
172}
173
88#ifdef CONFIG_PROVE_LOCKING 174#ifdef CONFIG_PROVE_LOCKING
89int lockdep_rht_mutex_is_held(const struct rhashtable *ht); 175int lockdep_rht_mutex_is_held(struct rhashtable *ht);
176int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
90#else 177#else
91static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht) 178static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
179{
180 return 1;
181}
182
183static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
184 u32 hash)
92{ 185{
93 return 1; 186 return 1;
94} 187}
@@ -96,13 +189,8 @@ static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
96 189
97int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params); 190int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
98 191
99u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
100u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
101
102void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node); 192void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node);
103bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node); 193bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node);
104void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
105 struct rhash_head __rcu **pprev);
106 194
107bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size); 195bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size);
108bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size); 196bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size);
@@ -110,11 +198,23 @@ bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size);
110int rhashtable_expand(struct rhashtable *ht); 198int rhashtable_expand(struct rhashtable *ht);
111int rhashtable_shrink(struct rhashtable *ht); 199int rhashtable_shrink(struct rhashtable *ht);
112 200
113void *rhashtable_lookup(const struct rhashtable *ht, const void *key); 201void *rhashtable_lookup(struct rhashtable *ht, const void *key);
114void *rhashtable_lookup_compare(const struct rhashtable *ht, u32 hash, 202void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
115 bool (*compare)(void *, void *), void *arg); 203 bool (*compare)(void *, void *), void *arg);
116 204
117void rhashtable_destroy(const struct rhashtable *ht); 205bool rhashtable_lookup_insert(struct rhashtable *ht, struct rhash_head *obj);
206bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
207 struct rhash_head *obj,
208 bool (*compare)(void *, void *),
209 void *arg);
210
211int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter);
212void rhashtable_walk_exit(struct rhashtable_iter *iter);
213int rhashtable_walk_start(struct rhashtable_iter *iter) __acquires(RCU);
214void *rhashtable_walk_next(struct rhashtable_iter *iter);
215void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
216
217void rhashtable_destroy(struct rhashtable *ht);
118 218
119#define rht_dereference(p, ht) \ 219#define rht_dereference(p, ht) \
120 rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht)) 220 rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
@@ -122,92 +222,146 @@ void rhashtable_destroy(const struct rhashtable *ht);
122#define rht_dereference_rcu(p, ht) \ 222#define rht_dereference_rcu(p, ht) \
123 rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht)) 223 rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))
124 224
125#define rht_entry(ptr, type, member) container_of(ptr, type, member) 225#define rht_dereference_bucket(p, tbl, hash) \
126#define rht_entry_safe(ptr, type, member) \ 226 rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
127({ \ 227
128 typeof(ptr) __ptr = (ptr); \ 228#define rht_dereference_bucket_rcu(p, tbl, hash) \
129 __ptr ? rht_entry(__ptr, type, member) : NULL; \ 229 rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
130})
131 230
132#define rht_next_entry_safe(pos, ht, member) \ 231#define rht_entry(tpos, pos, member) \
133({ \ 232 ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
134 pos ? rht_entry_safe(rht_dereference((pos)->member.next, ht), \ 233
135 typeof(*(pos)), member) : NULL; \ 234/**
136}) 235 * rht_for_each_continue - continue iterating over hash chain
236 * @pos: the &struct rhash_head to use as a loop cursor.
237 * @head: the previous &struct rhash_head to continue from
238 * @tbl: the &struct bucket_table
239 * @hash: the hash value / bucket index
240 */
241#define rht_for_each_continue(pos, head, tbl, hash) \
242 for (pos = rht_dereference_bucket(head, tbl, hash); \
243 !rht_is_a_nulls(pos); \
244 pos = rht_dereference_bucket((pos)->next, tbl, hash))
137 245
138/** 246/**
139 * rht_for_each - iterate over hash chain 247 * rht_for_each - iterate over hash chain
140 * @pos: &struct rhash_head to use as a loop cursor. 248 * @pos: the &struct rhash_head to use as a loop cursor.
141 * @head: head of the hash chain (struct rhash_head *) 249 * @tbl: the &struct bucket_table
142 * @ht: pointer to your struct rhashtable 250 * @hash: the hash value / bucket index
143 */ 251 */
144#define rht_for_each(pos, head, ht) \ 252#define rht_for_each(pos, tbl, hash) \
145 for (pos = rht_dereference(head, ht); \ 253 rht_for_each_continue(pos, (tbl)->buckets[hash], tbl, hash)
146 pos; \ 254
147 pos = rht_dereference((pos)->next, ht)) 255/**
256 * rht_for_each_entry_continue - continue iterating over hash chain
257 * @tpos: the type * to use as a loop cursor.
258 * @pos: the &struct rhash_head to use as a loop cursor.
259 * @head: the previous &struct rhash_head to continue from
260 * @tbl: the &struct bucket_table
261 * @hash: the hash value / bucket index
262 * @member: name of the &struct rhash_head within the hashable struct.
263 */
264#define rht_for_each_entry_continue(tpos, pos, head, tbl, hash, member) \
265 for (pos = rht_dereference_bucket(head, tbl, hash); \
266 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
267 pos = rht_dereference_bucket((pos)->next, tbl, hash))
148 268
149/** 269/**
150 * rht_for_each_entry - iterate over hash chain of given type 270 * rht_for_each_entry - iterate over hash chain of given type
151 * @pos: type * to use as a loop cursor. 271 * @tpos: the type * to use as a loop cursor.
152 * @head: head of the hash chain (struct rhash_head *) 272 * @pos: the &struct rhash_head to use as a loop cursor.
153 * @ht: pointer to your struct rhashtable 273 * @tbl: the &struct bucket_table
154 * @member: name of the rhash_head within the hashable struct. 274 * @hash: the hash value / bucket index
275 * @member: name of the &struct rhash_head within the hashable struct.
155 */ 276 */
156#define rht_for_each_entry(pos, head, ht, member) \ 277#define rht_for_each_entry(tpos, pos, tbl, hash, member) \
157 for (pos = rht_entry_safe(rht_dereference(head, ht), \ 278 rht_for_each_entry_continue(tpos, pos, (tbl)->buckets[hash], \
158 typeof(*(pos)), member); \ 279 tbl, hash, member)
159 pos; \
160 pos = rht_next_entry_safe(pos, ht, member))
161 280
162/** 281/**
163 * rht_for_each_entry_safe - safely iterate over hash chain of given type 282 * rht_for_each_entry_safe - safely iterate over hash chain of given type
164 * @pos: type * to use as a loop cursor. 283 * @tpos: the type * to use as a loop cursor.
165 * @n: type * to use for temporary next object storage 284 * @pos: the &struct rhash_head to use as a loop cursor.
166 * @head: head of the hash chain (struct rhash_head *) 285 * @next: the &struct rhash_head to use as next in loop cursor.
167 * @ht: pointer to your struct rhashtable 286 * @tbl: the &struct bucket_table
168 * @member: name of the rhash_head within the hashable struct. 287 * @hash: the hash value / bucket index
288 * @member: name of the &struct rhash_head within the hashable struct.
169 * 289 *
170 * This hash chain list-traversal primitive allows for the looped code to 290 * This hash chain list-traversal primitive allows for the looped code to
171 * remove the loop cursor from the list. 291 * remove the loop cursor from the list.
172 */ 292 */
173#define rht_for_each_entry_safe(pos, n, head, ht, member) \ 293#define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member) \
174 for (pos = rht_entry_safe(rht_dereference(head, ht), \ 294 for (pos = rht_dereference_bucket((tbl)->buckets[hash], tbl, hash), \
175 typeof(*(pos)), member), \ 295 next = !rht_is_a_nulls(pos) ? \
176 n = rht_next_entry_safe(pos, ht, member); \ 296 rht_dereference_bucket(pos->next, tbl, hash) : NULL; \
177 pos; \ 297 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
178 pos = n, \ 298 pos = next, \
179 n = rht_next_entry_safe(pos, ht, member)) 299 next = !rht_is_a_nulls(pos) ? \
300 rht_dereference_bucket(pos->next, tbl, hash) : NULL)
301
302/**
303 * rht_for_each_rcu_continue - continue iterating over rcu hash chain
304 * @pos: the &struct rhash_head to use as a loop cursor.
305 * @head: the previous &struct rhash_head to continue from
306 * @tbl: the &struct bucket_table
307 * @hash: the hash value / bucket index
308 *
309 * This hash chain list-traversal primitive may safely run concurrently with
310 * the _rcu mutation primitives such as rhashtable_insert() as long as the
311 * traversal is guarded by rcu_read_lock().
312 */
313#define rht_for_each_rcu_continue(pos, head, tbl, hash) \
314 for (({barrier(); }), \
315 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
316 !rht_is_a_nulls(pos); \
317 pos = rcu_dereference_raw(pos->next))
180 318
181/** 319/**
182 * rht_for_each_rcu - iterate over rcu hash chain 320 * rht_for_each_rcu - iterate over rcu hash chain
183 * @pos: &struct rhash_head to use as a loop cursor. 321 * @pos: the &struct rhash_head to use as a loop cursor.
184 * @head: head of the hash chain (struct rhash_head *) 322 * @tbl: the &struct bucket_table
185 * @ht: pointer to your struct rhashtable 323 * @hash: the hash value / bucket index
324 *
325 * This hash chain list-traversal primitive may safely run concurrently with
326 * the _rcu mutation primitives such as rhashtable_insert() as long as the
327 * traversal is guarded by rcu_read_lock().
328 */
329#define rht_for_each_rcu(pos, tbl, hash) \
330 rht_for_each_rcu_continue(pos, (tbl)->buckets[hash], tbl, hash)
331
332/**
333 * rht_for_each_entry_rcu_continue - continue iterating over rcu hash chain
334 * @tpos: the type * to use as a loop cursor.
335 * @pos: the &struct rhash_head to use as a loop cursor.
336 * @head: the previous &struct rhash_head to continue from
337 * @tbl: the &struct bucket_table
338 * @hash: the hash value / bucket index
339 * @member: name of the &struct rhash_head within the hashable struct.
186 * 340 *
187 * This hash chain list-traversal primitive may safely run concurrently with 341 * This hash chain list-traversal primitive may safely run concurrently with
188 * the _rcu fkht mutation primitives such as rht_insert() as long as the 342 * the _rcu mutation primitives such as rhashtable_insert() as long as the
189 * traversal is guarded by rcu_read_lock(). 343 * traversal is guarded by rcu_read_lock().
190 */ 344 */
191#define rht_for_each_rcu(pos, head, ht) \ 345#define rht_for_each_entry_rcu_continue(tpos, pos, head, tbl, hash, member) \
192 for (pos = rht_dereference_rcu(head, ht); \ 346 for (({barrier(); }), \
193 pos; \ 347 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
194 pos = rht_dereference_rcu((pos)->next, ht)) 348 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
349 pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
195 350
196/** 351/**
197 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type 352 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
198 * @pos: type * to use as a loop cursor. 353 * @tpos: the type * to use as a loop cursor.
199 * @head: head of the hash chain (struct rhash_head *) 354 * @pos: the &struct rhash_head to use as a loop cursor.
200 * @member: name of the rhash_head within the hashable struct. 355 * @tbl: the &struct bucket_table
356 * @hash: the hash value / bucket index
357 * @member: name of the &struct rhash_head within the hashable struct.
201 * 358 *
202 * This hash chain list-traversal primitive may safely run concurrently with 359 * This hash chain list-traversal primitive may safely run concurrently with
203 * the _rcu fkht mutation primitives such as rht_insert() as long as the 360 * the _rcu mutation primitives such as rhashtable_insert() as long as the
204 * traversal is guarded by rcu_read_lock(). 361 * traversal is guarded by rcu_read_lock().
205 */ 362 */
206#define rht_for_each_entry_rcu(pos, head, member) \ 363#define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \
207 for (pos = rht_entry_safe(rcu_dereference_raw(head), \ 364 rht_for_each_entry_rcu_continue(tpos, pos, (tbl)->buckets[hash],\
208 typeof(*(pos)), member); \ 365 tbl, hash, member)
209 pos; \
210 pos = rht_entry_safe(rcu_dereference_raw((pos)->member.next), \
211 typeof(*(pos)), member))
212 366
213#endif /* _LINUX_RHASHTABLE_H */ 367#endif /* _LINUX_RHASHTABLE_H */