blob: dbcbcc59aa92e77de6c1c6065b403c0fa7d0dd15 [file] [log] [blame]
Thomas Graf7e1e7762014-08-02 11:47:44 +02001/*
2 * Resizable, Scalable, Concurrent Hash Table
3 *
Herbert Xudc0ee262015-03-20 21:57:06 +11004 * Copyright (c) 2015 Herbert Xu <herbert@gondor.apana.org.au>
Thomas Grafb5e2c152015-03-24 20:42:19 +00005 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
Thomas Graf7e1e7762014-08-02 11:47:44 +02006 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
7 *
Thomas Graf7e1e7762014-08-02 11:47:44 +02008 * Code partially derived from nft_hash
Herbert Xudc0ee262015-03-20 21:57:06 +11009 * Rewritten with rehash code from br_multicast plus single list
10 * pointer as suggested by Josh Triplett
Thomas Graf7e1e7762014-08-02 11:47:44 +020011 *
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.
15 */
16
17#ifndef _LINUX_RHASHTABLE_H
18#define _LINUX_RHASHTABLE_H
19
Herbert Xuf2dba9c2015-02-04 07:33:23 +110020#include <linux/compiler.h>
Herbert Xu6626af62015-03-20 18:18:45 -040021#include <linux/errno.h>
Herbert Xu31ccde22015-03-24 00:50:21 +110022#include <linux/jhash.h>
Thomas Graff89bd6f2015-01-02 23:00:21 +010023#include <linux/list_nulls.h>
Thomas Graf97defe12015-01-02 23:00:20 +010024#include <linux/workqueue.h>
Ying Xue86b35b62015-01-04 15:25:09 +080025#include <linux/mutex.h>
Herbert Xu02fd97c2015-03-20 21:57:00 +110026#include <linux/rcupdate.h>
Thomas Graf7e1e7762014-08-02 11:47:44 +020027
Thomas Graff89bd6f2015-01-02 23:00:21 +010028/*
29 * The end of the chain is marked with a special nulls marks which has
30 * the following format:
31 *
32 * +-------+-----------------------------------------------------+-+
33 * | Base | Hash |1|
34 * +-------+-----------------------------------------------------+-+
35 *
36 * Base (4 bits) : Reserved to distinguish between multiple tables.
37 * Specified via &struct rhashtable_params.nulls_base.
38 * Hash (27 bits): Full hash (unmasked) of first element added to bucket
39 * 1 (1 bit) : Nulls marker (always set)
40 *
41 * The remaining bits of the next pointer remain unused for now.
42 */
43#define RHT_BASE_BITS 4
44#define RHT_HASH_BITS 27
45#define RHT_BASE_SHIFT RHT_HASH_BITS
46
Herbert Xu02fd97c2015-03-20 21:57:00 +110047/* Base bits plus 1 bit for nulls marker */
48#define RHT_HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
49
Thomas Graf7e1e7762014-08-02 11:47:44 +020050struct rhash_head {
Thomas Graf5300fdc2014-08-13 16:38:29 +020051 struct rhash_head __rcu *next;
Thomas Graf7e1e7762014-08-02 11:47:44 +020052};
53
Thomas Graf97defe12015-01-02 23:00:20 +010054/**
55 * struct bucket_table - Table of hash buckets
56 * @size: Number of hash buckets
Herbert Xu63d512d2015-03-14 13:57:24 +110057 * @rehash: Current bucket being rehashed
Herbert Xu988dfbd2015-03-10 09:27:55 +110058 * @hash_rnd: Random seed to fold into hash
Thomas Graf97defe12015-01-02 23:00:20 +010059 * @locks_mask: Mask to apply before accessing locks[]
60 * @locks: Array of spinlocks protecting individual buckets
Herbert Xueddee5ba2015-03-14 13:57:20 +110061 * @walkers: List of active walkers
Herbert Xu9d901bc2015-03-14 13:57:23 +110062 * @rcu: RCU structure for freeing the table
Herbert Xuc4db8842015-03-14 13:57:25 +110063 * @future_tbl: Table under construction during rehashing
Thomas Graf97defe12015-01-02 23:00:20 +010064 * @buckets: size * hash buckets
65 */
Thomas Graf7e1e7762014-08-02 11:47:44 +020066struct bucket_table {
Herbert Xu63d512d2015-03-14 13:57:24 +110067 unsigned int size;
68 unsigned int rehash;
Herbert Xu988dfbd2015-03-10 09:27:55 +110069 u32 hash_rnd;
Eric Dumazetb9ebafb2015-02-20 06:48:57 -080070 unsigned int locks_mask;
71 spinlock_t *locks;
Herbert Xueddee5ba2015-03-14 13:57:20 +110072 struct list_head walkers;
Herbert Xu9d901bc2015-03-14 13:57:23 +110073 struct rcu_head rcu;
Eric Dumazetb9ebafb2015-02-20 06:48:57 -080074
Herbert Xuc4db8842015-03-14 13:57:25 +110075 struct bucket_table __rcu *future_tbl;
76
Eric Dumazetb9ebafb2015-02-20 06:48:57 -080077 struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp;
Thomas Graf7e1e7762014-08-02 11:47:44 +020078};
79
Herbert Xu02fd97c2015-03-20 21:57:00 +110080/**
81 * struct rhashtable_compare_arg - Key for the function rhashtable_compare
82 * @ht: Hash table
83 * @key: Key to compare against
84 */
85struct rhashtable_compare_arg {
86 struct rhashtable *ht;
87 const void *key;
88};
89
Thomas Graf7e1e7762014-08-02 11:47:44 +020090typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
Patrick McHardy49f7b332015-03-25 13:07:45 +000091typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
Herbert Xu02fd97c2015-03-20 21:57:00 +110092typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
93 const void *obj);
Thomas Graf7e1e7762014-08-02 11:47:44 +020094
95struct rhashtable;
96
97/**
98 * struct rhashtable_params - Hash table construction parameters
99 * @nelem_hint: Hint on number of elements, should be 75% of desired size
100 * @key_len: Length of key
101 * @key_offset: Offset of key in struct to be hashed
102 * @head_offset: Offset of rhash_head in struct to be hashed
Herbert Xuc2e213c2015-03-18 20:01:16 +1100103 * @max_size: Maximum size while expanding
104 * @min_size: Minimum size while shrinking
Thomas Graff89bd6f2015-01-02 23:00:21 +0100105 * @nulls_base: Base value to generate nulls marker
Herbert Xuccd57b12015-03-24 00:50:28 +1100106 * @insecure_elasticity: Set to true to disable chain length checks
Thomas Grafb5e2c152015-03-24 20:42:19 +0000107 * @automatic_shrinking: Enable automatic shrinking of tables
Thomas Graf97defe12015-01-02 23:00:20 +0100108 * @locks_mul: Number of bucket locks to allocate per cpu (default: 128)
Herbert Xu31ccde22015-03-24 00:50:21 +1100109 * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200110 * @obj_hashfn: Function to hash object
Herbert Xu02fd97c2015-03-20 21:57:00 +1100111 * @obj_cmpfn: Function to compare key with object
Thomas Graf7e1e7762014-08-02 11:47:44 +0200112 */
113struct rhashtable_params {
114 size_t nelem_hint;
115 size_t key_len;
116 size_t key_offset;
117 size_t head_offset;
Herbert Xuc2e213c2015-03-18 20:01:16 +1100118 unsigned int max_size;
119 unsigned int min_size;
Thomas Graff89bd6f2015-01-02 23:00:21 +0100120 u32 nulls_base;
Herbert Xuccd57b12015-03-24 00:50:28 +1100121 bool insecure_elasticity;
Thomas Grafb5e2c152015-03-24 20:42:19 +0000122 bool automatic_shrinking;
Thomas Graf97defe12015-01-02 23:00:20 +0100123 size_t locks_mul;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200124 rht_hashfn_t hashfn;
125 rht_obj_hashfn_t obj_hashfn;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100126 rht_obj_cmpfn_t obj_cmpfn;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200127};
128
129/**
130 * struct rhashtable - Hash table handle
131 * @tbl: Bucket table
132 * @nelems: Number of elements in table
Herbert Xu31ccde22015-03-24 00:50:21 +1100133 * @key_len: Key length for hashfn
Herbert Xuccd57b12015-03-24 00:50:28 +1100134 * @elasticity: Maximum chain length before rehash
Thomas Graf7e1e7762014-08-02 11:47:44 +0200135 * @p: Configuration parameters
Thomas Graf97defe12015-01-02 23:00:20 +0100136 * @run_work: Deferred worker to expand/shrink asynchronously
137 * @mutex: Mutex to protect current/future table swapping
Herbert Xuba7c95e2015-03-24 09:53:17 +1100138 * @lock: Spin lock to protect walker list
Thomas Graf7e1e7762014-08-02 11:47:44 +0200139 */
140struct rhashtable {
141 struct bucket_table __rcu *tbl;
Thomas Graf97defe12015-01-02 23:00:20 +0100142 atomic_t nelems;
Herbert Xu31ccde22015-03-24 00:50:21 +1100143 unsigned int key_len;
Herbert Xuccd57b12015-03-24 00:50:28 +1100144 unsigned int elasticity;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200145 struct rhashtable_params p;
Ying Xue57699a42015-01-16 11:13:09 +0800146 struct work_struct run_work;
Thomas Graf97defe12015-01-02 23:00:20 +0100147 struct mutex mutex;
Herbert Xuba7c95e2015-03-24 09:53:17 +1100148 spinlock_t lock;
Thomas Graf7e1e7762014-08-02 11:47:44 +0200149};
150
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100151/**
152 * struct rhashtable_walker - Hash table walker
153 * @list: List entry on list of walkers
Herbert Xueddee5ba2015-03-14 13:57:20 +1100154 * @tbl: The table that we were walking over
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100155 */
156struct rhashtable_walker {
157 struct list_head list;
Herbert Xueddee5ba2015-03-14 13:57:20 +1100158 struct bucket_table *tbl;
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100159};
160
161/**
162 * struct rhashtable_iter - Hash table iterator, fits into netlink cb
163 * @ht: Table to iterate through
164 * @p: Current pointer
165 * @walker: Associated rhashtable walker
166 * @slot: Current slot
167 * @skip: Number of entries to skip in slot
168 */
169struct rhashtable_iter {
170 struct rhashtable *ht;
171 struct rhash_head *p;
172 struct rhashtable_walker *walker;
173 unsigned int slot;
174 unsigned int skip;
175};
176
Thomas Graff89bd6f2015-01-02 23:00:21 +0100177static inline unsigned long rht_marker(const struct rhashtable *ht, u32 hash)
178{
179 return NULLS_MARKER(ht->p.nulls_base + hash);
180}
181
182#define INIT_RHT_NULLS_HEAD(ptr, ht, hash) \
183 ((ptr) = (typeof(ptr)) rht_marker(ht, hash))
184
185static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
186{
187 return ((unsigned long) ptr & 1);
188}
189
190static inline unsigned long rht_get_nulls_value(const struct rhash_head *ptr)
191{
192 return ((unsigned long) ptr) >> 1;
193}
194
Herbert Xu02fd97c2015-03-20 21:57:00 +1100195static inline void *rht_obj(const struct rhashtable *ht,
196 const struct rhash_head *he)
197{
198 return (char *)he - ht->p.head_offset;
199}
200
201static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
202 unsigned int hash)
203{
204 return (hash >> RHT_HASH_RESERVED_SPACE) & (tbl->size - 1);
205}
206
207static inline unsigned int rht_key_hashfn(
208 struct rhashtable *ht, const struct bucket_table *tbl,
209 const void *key, const struct rhashtable_params params)
210{
Thomas Graf299e5c32015-03-24 14:18:17 +0100211 unsigned int hash;
Herbert Xude91b252015-03-24 00:50:20 +1100212
Herbert Xu31ccde22015-03-24 00:50:21 +1100213 /* params must be equal to ht->p if it isn't constant. */
214 if (!__builtin_constant_p(params.key_len))
215 hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd);
216 else if (params.key_len) {
Thomas Graf299e5c32015-03-24 14:18:17 +0100217 unsigned int key_len = params.key_len;
Herbert Xu31ccde22015-03-24 00:50:21 +1100218
219 if (params.hashfn)
220 hash = params.hashfn(key, key_len, tbl->hash_rnd);
221 else if (key_len & (sizeof(u32) - 1))
222 hash = jhash(key, key_len, tbl->hash_rnd);
223 else
224 hash = jhash2(key, key_len / sizeof(u32),
225 tbl->hash_rnd);
226 } else {
Thomas Graf299e5c32015-03-24 14:18:17 +0100227 unsigned int key_len = ht->p.key_len;
Herbert Xu31ccde22015-03-24 00:50:21 +1100228
229 if (params.hashfn)
230 hash = params.hashfn(key, key_len, tbl->hash_rnd);
231 else
232 hash = jhash(key, key_len, tbl->hash_rnd);
233 }
234
235 return rht_bucket_index(tbl, hash);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100236}
237
238static inline unsigned int rht_head_hashfn(
239 struct rhashtable *ht, const struct bucket_table *tbl,
240 const struct rhash_head *he, const struct rhashtable_params params)
241{
242 const char *ptr = rht_obj(ht, he);
243
244 return likely(params.obj_hashfn) ?
Patrick McHardy49f7b332015-03-25 13:07:45 +0000245 rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
246 ht->p.key_len,
247 tbl->hash_rnd)) :
Herbert Xu02fd97c2015-03-20 21:57:00 +1100248 rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
249}
250
251/**
252 * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
253 * @ht: hash table
254 * @tbl: current table
255 */
256static inline bool rht_grow_above_75(const struct rhashtable *ht,
257 const struct bucket_table *tbl)
258{
259 /* Expand table when exceeding 75% load */
260 return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
261 (!ht->p.max_size || tbl->size < ht->p.max_size);
262}
263
264/**
265 * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
266 * @ht: hash table
267 * @tbl: current table
268 */
269static inline bool rht_shrink_below_30(const struct rhashtable *ht,
270 const struct bucket_table *tbl)
271{
272 /* Shrink table beneath 30% load */
273 return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
274 tbl->size > ht->p.min_size;
275}
276
Herbert Xuccd57b12015-03-24 00:50:28 +1100277/**
278 * rht_grow_above_100 - returns true if nelems > table-size
279 * @ht: hash table
280 * @tbl: current table
281 */
282static inline bool rht_grow_above_100(const struct rhashtable *ht,
283 const struct bucket_table *tbl)
284{
Johannes Berg1d8dc3d2015-04-23 16:38:43 +0200285 return atomic_read(&ht->nelems) > tbl->size &&
286 (!ht->p.max_size || tbl->size < ht->p.max_size);
Herbert Xuccd57b12015-03-24 00:50:28 +1100287}
288
Herbert Xu02fd97c2015-03-20 21:57:00 +1100289/* The bucket lock is selected based on the hash and protects mutations
290 * on a group of hash buckets.
291 *
292 * A maximum of tbl->size/2 bucket locks is allocated. This ensures that
293 * a single lock always covers both buckets which may both contains
294 * entries which link to the same bucket of the old table during resizing.
295 * This allows to simplify the locking as locking the bucket in both
296 * tables during resize always guarantee protection.
297 *
298 * IMPORTANT: When holding the bucket lock of both the old and new table
299 * during expansions and shrinking, the old bucket lock must always be
300 * acquired first.
301 */
302static inline spinlock_t *rht_bucket_lock(const struct bucket_table *tbl,
303 unsigned int hash)
304{
305 return &tbl->locks[hash & tbl->locks_mask];
306}
307
Thomas Graf7e1e7762014-08-02 11:47:44 +0200308#ifdef CONFIG_PROVE_LOCKING
Thomas Graf97defe12015-01-02 23:00:20 +0100309int lockdep_rht_mutex_is_held(struct rhashtable *ht);
Thomas Graf88d6ed12015-01-02 23:00:16 +0100310int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200311#else
Thomas Graf97defe12015-01-02 23:00:20 +0100312static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200313{
314 return 1;
315}
Thomas Graf88d6ed12015-01-02 23:00:16 +0100316
317static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
318 u32 hash)
319{
320 return 1;
321}
Thomas Graf7e1e7762014-08-02 11:47:44 +0200322#endif /* CONFIG_PROVE_LOCKING */
323
Herbert Xu488fb86e2015-03-20 21:56:59 +1100324int rhashtable_init(struct rhashtable *ht,
325 const struct rhashtable_params *params);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200326
Herbert Xu02fd97c2015-03-20 21:57:00 +1100327int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
328 struct rhash_head *obj,
329 struct bucket_table *old_tbl);
Herbert Xuccd57b12015-03-24 00:50:28 +1100330int rhashtable_insert_rehash(struct rhashtable *ht);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200331
Herbert Xuf2dba9c2015-02-04 07:33:23 +1100332int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter);
333void rhashtable_walk_exit(struct rhashtable_iter *iter);
334int rhashtable_walk_start(struct rhashtable_iter *iter) __acquires(RCU);
335void *rhashtable_walk_next(struct rhashtable_iter *iter);
336void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
337
Thomas Graf6b6f3022015-03-24 14:18:20 +0100338void rhashtable_free_and_destroy(struct rhashtable *ht,
339 void (*free_fn)(void *ptr, void *arg),
340 void *arg);
Thomas Graf97defe12015-01-02 23:00:20 +0100341void rhashtable_destroy(struct rhashtable *ht);
Thomas Graf7e1e7762014-08-02 11:47:44 +0200342
343#define rht_dereference(p, ht) \
344 rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
345
346#define rht_dereference_rcu(p, ht) \
347 rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))
348
Thomas Graf88d6ed12015-01-02 23:00:16 +0100349#define rht_dereference_bucket(p, tbl, hash) \
350 rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200351
Thomas Graf88d6ed12015-01-02 23:00:16 +0100352#define rht_dereference_bucket_rcu(p, tbl, hash) \
353 rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
354
355#define rht_entry(tpos, pos, member) \
356 ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
357
358/**
359 * rht_for_each_continue - continue iterating over hash chain
360 * @pos: the &struct rhash_head to use as a loop cursor.
361 * @head: the previous &struct rhash_head to continue from
362 * @tbl: the &struct bucket_table
363 * @hash: the hash value / bucket index
364 */
365#define rht_for_each_continue(pos, head, tbl, hash) \
366 for (pos = rht_dereference_bucket(head, tbl, hash); \
Thomas Graff89bd6f2015-01-02 23:00:21 +0100367 !rht_is_a_nulls(pos); \
Thomas Graf88d6ed12015-01-02 23:00:16 +0100368 pos = rht_dereference_bucket((pos)->next, tbl, hash))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200369
370/**
371 * rht_for_each - iterate over hash chain
Thomas Graf88d6ed12015-01-02 23:00:16 +0100372 * @pos: the &struct rhash_head to use as a loop cursor.
373 * @tbl: the &struct bucket_table
374 * @hash: the hash value / bucket index
Thomas Graf7e1e7762014-08-02 11:47:44 +0200375 */
Thomas Graf88d6ed12015-01-02 23:00:16 +0100376#define rht_for_each(pos, tbl, hash) \
377 rht_for_each_continue(pos, (tbl)->buckets[hash], tbl, hash)
378
379/**
380 * rht_for_each_entry_continue - continue iterating over hash chain
381 * @tpos: the type * to use as a loop cursor.
382 * @pos: the &struct rhash_head to use as a loop cursor.
383 * @head: the previous &struct rhash_head to continue from
384 * @tbl: the &struct bucket_table
385 * @hash: the hash value / bucket index
386 * @member: name of the &struct rhash_head within the hashable struct.
387 */
388#define rht_for_each_entry_continue(tpos, pos, head, tbl, hash, member) \
389 for (pos = rht_dereference_bucket(head, tbl, hash); \
Thomas Graff89bd6f2015-01-02 23:00:21 +0100390 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
Thomas Graf88d6ed12015-01-02 23:00:16 +0100391 pos = rht_dereference_bucket((pos)->next, tbl, hash))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200392
393/**
394 * rht_for_each_entry - iterate over hash chain of given type
Thomas Graf88d6ed12015-01-02 23:00:16 +0100395 * @tpos: the type * to use as a loop cursor.
396 * @pos: the &struct rhash_head to use as a loop cursor.
397 * @tbl: the &struct bucket_table
398 * @hash: the hash value / bucket index
399 * @member: name of the &struct rhash_head within the hashable struct.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200400 */
Thomas Graf88d6ed12015-01-02 23:00:16 +0100401#define rht_for_each_entry(tpos, pos, tbl, hash, member) \
402 rht_for_each_entry_continue(tpos, pos, (tbl)->buckets[hash], \
403 tbl, hash, member)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200404
405/**
406 * rht_for_each_entry_safe - safely iterate over hash chain of given type
Thomas Graf88d6ed12015-01-02 23:00:16 +0100407 * @tpos: the type * to use as a loop cursor.
408 * @pos: the &struct rhash_head to use as a loop cursor.
409 * @next: the &struct rhash_head to use as next in loop cursor.
410 * @tbl: the &struct bucket_table
411 * @hash: the hash value / bucket index
412 * @member: name of the &struct rhash_head within the hashable struct.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200413 *
414 * This hash chain list-traversal primitive allows for the looped code to
415 * remove the loop cursor from the list.
416 */
Thomas Graf88d6ed12015-01-02 23:00:16 +0100417#define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member) \
418 for (pos = rht_dereference_bucket((tbl)->buckets[hash], tbl, hash), \
Thomas Graff89bd6f2015-01-02 23:00:21 +0100419 next = !rht_is_a_nulls(pos) ? \
420 rht_dereference_bucket(pos->next, tbl, hash) : NULL; \
421 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
Patrick McHardy607954b2015-01-21 11:12:13 +0000422 pos = next, \
423 next = !rht_is_a_nulls(pos) ? \
424 rht_dereference_bucket(pos->next, tbl, hash) : NULL)
Thomas Graf88d6ed12015-01-02 23:00:16 +0100425
426/**
427 * rht_for_each_rcu_continue - continue iterating over rcu hash chain
428 * @pos: the &struct rhash_head to use as a loop cursor.
429 * @head: the previous &struct rhash_head to continue from
430 * @tbl: the &struct bucket_table
431 * @hash: the hash value / bucket index
432 *
433 * This hash chain list-traversal primitive may safely run concurrently with
434 * the _rcu mutation primitives such as rhashtable_insert() as long as the
435 * traversal is guarded by rcu_read_lock().
436 */
437#define rht_for_each_rcu_continue(pos, head, tbl, hash) \
438 for (({barrier(); }), \
439 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
Thomas Graff89bd6f2015-01-02 23:00:21 +0100440 !rht_is_a_nulls(pos); \
Thomas Graf88d6ed12015-01-02 23:00:16 +0100441 pos = rcu_dereference_raw(pos->next))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200442
443/**
444 * rht_for_each_rcu - iterate over rcu hash chain
Thomas Graf88d6ed12015-01-02 23:00:16 +0100445 * @pos: the &struct rhash_head to use as a loop cursor.
446 * @tbl: the &struct bucket_table
447 * @hash: the hash value / bucket index
Thomas Graf7e1e7762014-08-02 11:47:44 +0200448 *
449 * This hash chain list-traversal primitive may safely run concurrently with
Thomas Graf88d6ed12015-01-02 23:00:16 +0100450 * the _rcu mutation primitives such as rhashtable_insert() as long as the
Thomas Graf7e1e7762014-08-02 11:47:44 +0200451 * traversal is guarded by rcu_read_lock().
452 */
Thomas Graf88d6ed12015-01-02 23:00:16 +0100453#define rht_for_each_rcu(pos, tbl, hash) \
454 rht_for_each_rcu_continue(pos, (tbl)->buckets[hash], tbl, hash)
455
456/**
457 * rht_for_each_entry_rcu_continue - continue iterating over rcu hash chain
458 * @tpos: the type * to use as a loop cursor.
459 * @pos: the &struct rhash_head to use as a loop cursor.
460 * @head: the previous &struct rhash_head to continue from
461 * @tbl: the &struct bucket_table
462 * @hash: the hash value / bucket index
463 * @member: name of the &struct rhash_head within the hashable struct.
464 *
465 * This hash chain list-traversal primitive may safely run concurrently with
466 * the _rcu mutation primitives such as rhashtable_insert() as long as the
467 * traversal is guarded by rcu_read_lock().
468 */
469#define rht_for_each_entry_rcu_continue(tpos, pos, head, tbl, hash, member) \
470 for (({barrier(); }), \
471 pos = rht_dereference_bucket_rcu(head, tbl, hash); \
Thomas Graff89bd6f2015-01-02 23:00:21 +0100472 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
Thomas Graf88d6ed12015-01-02 23:00:16 +0100473 pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
Thomas Graf7e1e7762014-08-02 11:47:44 +0200474
475/**
476 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
Thomas Graf88d6ed12015-01-02 23:00:16 +0100477 * @tpos: the type * to use as a loop cursor.
478 * @pos: the &struct rhash_head to use as a loop cursor.
479 * @tbl: the &struct bucket_table
480 * @hash: the hash value / bucket index
481 * @member: name of the &struct rhash_head within the hashable struct.
Thomas Graf7e1e7762014-08-02 11:47:44 +0200482 *
483 * This hash chain list-traversal primitive may safely run concurrently with
Thomas Graf88d6ed12015-01-02 23:00:16 +0100484 * the _rcu mutation primitives such as rhashtable_insert() as long as the
Thomas Graf7e1e7762014-08-02 11:47:44 +0200485 * traversal is guarded by rcu_read_lock().
486 */
Thomas Graf88d6ed12015-01-02 23:00:16 +0100487#define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \
488 rht_for_each_entry_rcu_continue(tpos, pos, (tbl)->buckets[hash],\
489 tbl, hash, member)
Thomas Graf7e1e7762014-08-02 11:47:44 +0200490
Herbert Xu02fd97c2015-03-20 21:57:00 +1100491static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
492 const void *obj)
493{
494 struct rhashtable *ht = arg->ht;
495 const char *ptr = obj;
496
497 return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
498}
499
500/**
501 * rhashtable_lookup_fast - search hash table, inlined version
502 * @ht: hash table
503 * @key: the pointer to the key
504 * @params: hash table parameters
505 *
506 * Computes the hash value for the key and traverses the bucket chain looking
507 * for a entry with an identical key. The first matching entry is returned.
508 *
509 * Returns the first entry on which the compare function returned true.
510 */
511static inline void *rhashtable_lookup_fast(
512 struct rhashtable *ht, const void *key,
513 const struct rhashtable_params params)
514{
515 struct rhashtable_compare_arg arg = {
516 .ht = ht,
517 .key = key,
518 };
519 const struct bucket_table *tbl;
520 struct rhash_head *he;
Thomas Graf299e5c32015-03-24 14:18:17 +0100521 unsigned int hash;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100522
523 rcu_read_lock();
524
525 tbl = rht_dereference_rcu(ht->tbl, ht);
526restart:
527 hash = rht_key_hashfn(ht, tbl, key, params);
528 rht_for_each_rcu(he, tbl, hash) {
529 if (params.obj_cmpfn ?
530 params.obj_cmpfn(&arg, rht_obj(ht, he)) :
531 rhashtable_compare(&arg, rht_obj(ht, he)))
532 continue;
533 rcu_read_unlock();
534 return rht_obj(ht, he);
535 }
536
537 /* Ensure we see any new tables. */
538 smp_rmb();
539
540 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
541 if (unlikely(tbl))
542 goto restart;
543 rcu_read_unlock();
544
545 return NULL;
546}
547
Thomas Grafac833bd2015-03-24 14:18:18 +0100548/* Internal function, please use rhashtable_insert_fast() instead */
Herbert Xu02fd97c2015-03-20 21:57:00 +1100549static inline int __rhashtable_insert_fast(
550 struct rhashtable *ht, const void *key, struct rhash_head *obj,
551 const struct rhashtable_params params)
552{
553 struct rhashtable_compare_arg arg = {
554 .ht = ht,
555 .key = key,
556 };
Herbert Xu02fd97c2015-03-20 21:57:00 +1100557 struct bucket_table *tbl, *new_tbl;
558 struct rhash_head *head;
559 spinlock_t *lock;
Thomas Graf299e5c32015-03-24 14:18:17 +0100560 unsigned int elasticity;
561 unsigned int hash;
Herbert Xuccd57b12015-03-24 00:50:28 +1100562 int err;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100563
Herbert Xuccd57b12015-03-24 00:50:28 +1100564restart:
Herbert Xu02fd97c2015-03-20 21:57:00 +1100565 rcu_read_lock();
566
567 tbl = rht_dereference_rcu(ht->tbl, ht);
Herbert Xu02fd97c2015-03-20 21:57:00 +1100568
Herbert Xub8244782015-03-24 00:50:26 +1100569 /* All insertions must grab the oldest table containing
570 * the hashed bucket that is yet to be rehashed.
Herbert Xu02fd97c2015-03-20 21:57:00 +1100571 */
Herbert Xub8244782015-03-24 00:50:26 +1100572 for (;;) {
573 hash = rht_head_hashfn(ht, tbl, obj, params);
574 lock = rht_bucket_lock(tbl, hash);
575 spin_lock_bh(lock);
576
577 if (tbl->rehash <= hash)
578 break;
579
580 spin_unlock_bh(lock);
581 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
582 }
583
Herbert Xu02fd97c2015-03-20 21:57:00 +1100584 new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
585 if (unlikely(new_tbl)) {
586 err = rhashtable_insert_slow(ht, key, obj, new_tbl);
Herbert Xuccd57b12015-03-24 00:50:28 +1100587 if (err == -EAGAIN)
588 goto slow_path;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100589 goto out;
590 }
591
Herbert Xuccd57b12015-03-24 00:50:28 +1100592 if (unlikely(rht_grow_above_100(ht, tbl))) {
593slow_path:
594 spin_unlock_bh(lock);
Herbert Xuccd57b12015-03-24 00:50:28 +1100595 err = rhashtable_insert_rehash(ht);
Thomas Graf58be8a52015-03-24 14:18:16 +0100596 rcu_read_unlock();
Herbert Xuccd57b12015-03-24 00:50:28 +1100597 if (err)
598 return err;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100599
Herbert Xuccd57b12015-03-24 00:50:28 +1100600 goto restart;
601 }
602
603 err = -EEXIST;
604 elasticity = ht->elasticity;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100605 rht_for_each(head, tbl, hash) {
Herbert Xuccd57b12015-03-24 00:50:28 +1100606 if (key &&
607 unlikely(!(params.obj_cmpfn ?
Herbert Xu02fd97c2015-03-20 21:57:00 +1100608 params.obj_cmpfn(&arg, rht_obj(ht, head)) :
609 rhashtable_compare(&arg, rht_obj(ht, head)))))
610 goto out;
Herbert Xuccd57b12015-03-24 00:50:28 +1100611 if (!--elasticity)
612 goto slow_path;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100613 }
614
Herbert Xu02fd97c2015-03-20 21:57:00 +1100615 err = 0;
616
617 head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
618
619 RCU_INIT_POINTER(obj->next, head);
620
621 rcu_assign_pointer(tbl->buckets[hash], obj);
622
623 atomic_inc(&ht->nelems);
624 if (rht_grow_above_75(ht, tbl))
625 schedule_work(&ht->run_work);
626
627out:
628 spin_unlock_bh(lock);
629 rcu_read_unlock();
630
631 return err;
632}
633
634/**
635 * rhashtable_insert_fast - insert object into hash table
636 * @ht: hash table
637 * @obj: pointer to hash head inside object
638 * @params: hash table parameters
639 *
640 * Will take a per bucket spinlock to protect against mutual mutations
641 * on the same bucket. Multiple insertions may occur in parallel unless
642 * they map to the same bucket lock.
643 *
644 * It is safe to call this function from atomic context.
645 *
646 * Will trigger an automatic deferred table resizing if the size grows
647 * beyond the watermark indicated by grow_decision() which can be passed
648 * to rhashtable_init().
649 */
650static inline int rhashtable_insert_fast(
651 struct rhashtable *ht, struct rhash_head *obj,
652 const struct rhashtable_params params)
653{
654 return __rhashtable_insert_fast(ht, NULL, obj, params);
655}
656
657/**
658 * rhashtable_lookup_insert_fast - lookup and insert object into hash table
659 * @ht: hash table
660 * @obj: pointer to hash head inside object
661 * @params: hash table parameters
662 *
663 * Locks down the bucket chain in both the old and new table if a resize
664 * is in progress to ensure that writers can't remove from the old table
665 * and can't insert to the new table during the atomic operation of search
666 * and insertion. Searches for duplicates in both the old and new table if
667 * a resize is in progress.
668 *
669 * This lookup function may only be used for fixed key hash table (key_len
670 * parameter set). It will BUG() if used inappropriately.
671 *
672 * It is safe to call this function from atomic context.
673 *
674 * Will trigger an automatic deferred table resizing if the size grows
675 * beyond the watermark indicated by grow_decision() which can be passed
676 * to rhashtable_init().
677 */
678static inline int rhashtable_lookup_insert_fast(
679 struct rhashtable *ht, struct rhash_head *obj,
680 const struct rhashtable_params params)
681{
682 const char *key = rht_obj(ht, obj);
683
684 BUG_ON(ht->p.obj_hashfn);
685
686 return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj,
687 params);
688}
689
690/**
691 * rhashtable_lookup_insert_key - search and insert object to hash table
692 * with explicit key
693 * @ht: hash table
694 * @key: key
695 * @obj: pointer to hash head inside object
696 * @params: hash table parameters
697 *
698 * Locks down the bucket chain in both the old and new table if a resize
699 * is in progress to ensure that writers can't remove from the old table
700 * and can't insert to the new table during the atomic operation of search
701 * and insertion. Searches for duplicates in both the old and new table if
702 * a resize is in progress.
703 *
704 * Lookups may occur in parallel with hashtable mutations and resizing.
705 *
706 * Will trigger an automatic deferred table resizing if the size grows
707 * beyond the watermark indicated by grow_decision() which can be passed
708 * to rhashtable_init().
709 *
710 * Returns zero on success.
711 */
712static inline int rhashtable_lookup_insert_key(
713 struct rhashtable *ht, const void *key, struct rhash_head *obj,
714 const struct rhashtable_params params)
715{
716 BUG_ON(!ht->p.obj_hashfn || !key);
717
718 return __rhashtable_insert_fast(ht, key, obj, params);
719}
720
Thomas Grafac833bd2015-03-24 14:18:18 +0100721/* Internal function, please use rhashtable_remove_fast() instead */
Herbert Xu02fd97c2015-03-20 21:57:00 +1100722static inline int __rhashtable_remove_fast(
723 struct rhashtable *ht, struct bucket_table *tbl,
724 struct rhash_head *obj, const struct rhashtable_params params)
725{
726 struct rhash_head __rcu **pprev;
727 struct rhash_head *he;
728 spinlock_t * lock;
Thomas Graf299e5c32015-03-24 14:18:17 +0100729 unsigned int hash;
Herbert Xu02fd97c2015-03-20 21:57:00 +1100730 int err = -ENOENT;
731
732 hash = rht_head_hashfn(ht, tbl, obj, params);
733 lock = rht_bucket_lock(tbl, hash);
734
735 spin_lock_bh(lock);
736
737 pprev = &tbl->buckets[hash];
738 rht_for_each(he, tbl, hash) {
739 if (he != obj) {
740 pprev = &he->next;
741 continue;
742 }
743
744 rcu_assign_pointer(*pprev, obj->next);
745 err = 0;
746 break;
747 }
748
749 spin_unlock_bh(lock);
750
751 return err;
752}
753
754/**
755 * rhashtable_remove_fast - remove object from hash table
756 * @ht: hash table
757 * @obj: pointer to hash head inside object
758 * @params: hash table parameters
759 *
760 * Since the hash chain is single linked, the removal operation needs to
761 * walk the bucket chain upon removal. The removal operation is thus
762 * considerable slow if the hash table is not correctly sized.
763 *
764 * Will automatically shrink the table via rhashtable_expand() if the
765 * shrink_decision function specified at rhashtable_init() returns true.
766 *
767 * Returns zero on success, -ENOENT if the entry could not be found.
768 */
769static inline int rhashtable_remove_fast(
770 struct rhashtable *ht, struct rhash_head *obj,
771 const struct rhashtable_params params)
772{
773 struct bucket_table *tbl;
774 int err;
775
776 rcu_read_lock();
777
778 tbl = rht_dereference_rcu(ht->tbl, ht);
779
780 /* Because we have already taken (and released) the bucket
781 * lock in old_tbl, if we find that future_tbl is not yet
782 * visible then that guarantees the entry to still be in
783 * the old tbl if it exists.
784 */
785 while ((err = __rhashtable_remove_fast(ht, tbl, obj, params)) &&
786 (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
787 ;
788
789 if (err)
790 goto out;
791
792 atomic_dec(&ht->nelems);
Thomas Grafb5e2c152015-03-24 20:42:19 +0000793 if (unlikely(ht->p.automatic_shrinking &&
794 rht_shrink_below_30(ht, tbl)))
Herbert Xu02fd97c2015-03-20 21:57:00 +1100795 schedule_work(&ht->run_work);
796
797out:
798 rcu_read_unlock();
799
800 return err;
801}
802
Thomas Graf7e1e7762014-08-02 11:47:44 +0200803#endif /* _LINUX_RHASHTABLE_H */