rhashtable.c (18093d1c0d1e032142ee24825678b0a8977d74ba) rhashtable.c (b824478b2145be78ac19e1cf44e2b9036c7a9608)
1/*
2 * Resizable, Scalable, Concurrent Hash Table
3 *
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>
7 *
8 * Code partially derived from nft_hash

--- 122 unchanged lines hidden (view full) ---

131 get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
132
133 for (i = 0; i < nbuckets; i++)
134 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
135
136 return tbl;
137}
138
1/*
2 * Resizable, Scalable, Concurrent Hash Table
3 *
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>
7 *
8 * Code partially derived from nft_hash

--- 122 unchanged lines hidden (view full) ---

131 get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
132
133 for (i = 0; i < nbuckets; i++)
134 INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
135
136 return tbl;
137}
138
139static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
140 struct bucket_table *tbl)
141{
142 struct bucket_table *new_tbl;
143
144 do {
145 new_tbl = tbl;
146 tbl = rht_dereference_rcu(tbl->future_tbl, ht);
147 } while (tbl);
148
149 return new_tbl;
150}
151
139static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
140{
141 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
152static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
153{
154 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
142 struct bucket_table *new_tbl =
143 rht_dereference(old_tbl->future_tbl, ht) ?: old_tbl;
155 struct bucket_table *new_tbl = rhashtable_last_table(ht,
156 rht_dereference_rcu(old_tbl->future_tbl, ht));
144 struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
145 int err = -ENOENT;
146 struct rhash_head *head, *next, *entry;
147 spinlock_t *new_bucket_lock;
148 unsigned new_hash;
149
150 rht_for_each(entry, old_tbl, old_hash) {
151 err = 0;

--- 39 unchanged lines hidden (view full) ---

191
192 spin_lock_bh(old_bucket_lock);
193 while (!rhashtable_rehash_one(ht, old_hash))
194 ;
195 old_tbl->rehash++;
196 spin_unlock_bh(old_bucket_lock);
197}
198
157 struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
158 int err = -ENOENT;
159 struct rhash_head *head, *next, *entry;
160 spinlock_t *new_bucket_lock;
161 unsigned new_hash;
162
163 rht_for_each(entry, old_tbl, old_hash) {
164 err = 0;

--- 39 unchanged lines hidden (view full) ---

204
205 spin_lock_bh(old_bucket_lock);
206 while (!rhashtable_rehash_one(ht, old_hash))
207 ;
208 old_tbl->rehash++;
209 spin_unlock_bh(old_bucket_lock);
210}
211
199static void rhashtable_rehash(struct rhashtable *ht,
200 struct bucket_table *new_tbl)
212static int rhashtable_rehash_attach(struct rhashtable *ht,
213 struct bucket_table *old_tbl,
214 struct bucket_table *new_tbl)
201{
215{
202 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
203 struct rhashtable_walker *walker;
204 unsigned old_hash;
216 /* Protect future_tbl using the first bucket lock. */
217 spin_lock_bh(old_tbl->locks);
205
218
219 /* Did somebody beat us to it? */
220 if (rcu_access_pointer(old_tbl->future_tbl)) {
221 spin_unlock_bh(old_tbl->locks);
222 return -EEXIST;
223 }
224
206 /* Make insertions go into the new, empty table right away. Deletions
207 * and lookups will be attempted in both tables until we synchronize.
208 */
209 rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
210
211 /* Ensure the new table is visible to readers. */
212 smp_wmb();
213
225 /* Make insertions go into the new, empty table right away. Deletions
226 * and lookups will be attempted in both tables until we synchronize.
227 */
228 rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
229
230 /* Ensure the new table is visible to readers. */
231 smp_wmb();
232
233 spin_unlock_bh(old_tbl->locks);
234
235 return 0;
236}
237
238static int rhashtable_rehash_table(struct rhashtable *ht)
239{
240 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
241 struct bucket_table *new_tbl;
242 struct rhashtable_walker *walker;
243 unsigned old_hash;
244
245 new_tbl = rht_dereference(old_tbl->future_tbl, ht);
246 if (!new_tbl)
247 return 0;
248
214 for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
215 rhashtable_rehash_chain(ht, old_hash);
216
217 /* Publish the new table pointer. */
218 rcu_assign_pointer(ht->tbl, new_tbl);
219
220 list_for_each_entry(walker, &old_tbl->walkers, list)
221 walker->tbl = NULL;
222
223 /* Wait for readers. All new readers will see the new
224 * table, and thus no references to the old table will
225 * remain.
226 */
227 call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
249 for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
250 rhashtable_rehash_chain(ht, old_hash);
251
252 /* Publish the new table pointer. */
253 rcu_assign_pointer(ht->tbl, new_tbl);
254
255 list_for_each_entry(walker, &old_tbl->walkers, list)
256 walker->tbl = NULL;
257
258 /* Wait for readers. All new readers will see the new
259 * table, and thus no references to the old table will
260 * remain.
261 */
262 call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
263
264 return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
228}
229
230/**
231 * rhashtable_expand - Expand hash table while allowing concurrent lookups
232 * @ht: the hash table to expand
233 *
234 * A secondary bucket array is allocated and the hash entries are migrated.
235 *
236 * This function may only be called in a context where it is safe to call
237 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
238 *
239 * The caller must ensure that no concurrent resizing occurs by holding
240 * ht->mutex.
241 *
242 * It is valid to have concurrent insertions and deletions protected by per
243 * bucket locks or concurrent RCU protected lookups and traversals.
244 */
265}
266
267/**
268 * rhashtable_expand - Expand hash table while allowing concurrent lookups
269 * @ht: the hash table to expand
270 *
271 * A secondary bucket array is allocated and the hash entries are migrated.
272 *
273 * This function may only be called in a context where it is safe to call
274 * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
275 *
276 * The caller must ensure that no concurrent resizing occurs by holding
277 * ht->mutex.
278 *
279 * It is valid to have concurrent insertions and deletions protected by per
280 * bucket locks or concurrent RCU protected lookups and traversals.
281 */
245int rhashtable_expand(struct rhashtable *ht)
282static int rhashtable_expand(struct rhashtable *ht)
246{
247 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
283{
284 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
285 int err;
248
249 ASSERT_RHT_MUTEX(ht);
250
286
287 ASSERT_RHT_MUTEX(ht);
288
289 old_tbl = rhashtable_last_table(ht, old_tbl);
290
251 new_tbl = bucket_table_alloc(ht, old_tbl->size * 2);
252 if (new_tbl == NULL)
253 return -ENOMEM;
254
291 new_tbl = bucket_table_alloc(ht, old_tbl->size * 2);
292 if (new_tbl == NULL)
293 return -ENOMEM;
294
255 rhashtable_rehash(ht, new_tbl);
256 return 0;
295 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
296 if (err)
297 bucket_table_free(new_tbl);
298
299 return err;
257}
300}
258EXPORT_SYMBOL_GPL(rhashtable_expand);
259
260/**
261 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
262 * @ht: the hash table to shrink
263 *
264 * This function shrinks the hash table to fit, i.e., the smallest
265 * size would not cause it to expand right away automatically.
266 *
267 * The caller must ensure that no concurrent resizing occurs by holding
268 * ht->mutex.
269 *
270 * The caller must ensure that no concurrent table mutations take place.
271 * It is however valid to have concurrent lookups if they are RCU protected.
272 *
273 * It is valid to have concurrent insertions and deletions protected by per
274 * bucket locks or concurrent RCU protected lookups and traversals.
275 */
301
302/**
303 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
304 * @ht: the hash table to shrink
305 *
306 * This function shrinks the hash table to fit, i.e., the smallest
307 * size would not cause it to expand right away automatically.
308 *
309 * The caller must ensure that no concurrent resizing occurs by holding
310 * ht->mutex.
311 *
312 * The caller must ensure that no concurrent table mutations take place.
313 * It is however valid to have concurrent lookups if they are RCU protected.
314 *
315 * It is valid to have concurrent insertions and deletions protected by per
316 * bucket locks or concurrent RCU protected lookups and traversals.
317 */
276int rhashtable_shrink(struct rhashtable *ht)
318static int rhashtable_shrink(struct rhashtable *ht)
277{
278 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
279 unsigned size = roundup_pow_of_two(atomic_read(&ht->nelems) * 3 / 2);
319{
320 struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
321 unsigned size = roundup_pow_of_two(atomic_read(&ht->nelems) * 3 / 2);
322 int err;
280
281 ASSERT_RHT_MUTEX(ht);
282
283 if (size < ht->p.min_size)
284 size = ht->p.min_size;
285
286 if (old_tbl->size <= size)
287 return 0;
288
323
324 ASSERT_RHT_MUTEX(ht);
325
326 if (size < ht->p.min_size)
327 size = ht->p.min_size;
328
329 if (old_tbl->size <= size)
330 return 0;
331
332 if (rht_dereference(old_tbl->future_tbl, ht))
333 return -EEXIST;
334
289 new_tbl = bucket_table_alloc(ht, size);
290 if (new_tbl == NULL)
291 return -ENOMEM;
292
335 new_tbl = bucket_table_alloc(ht, size);
336 if (new_tbl == NULL)
337 return -ENOMEM;
338
293 rhashtable_rehash(ht, new_tbl);
294 return 0;
339 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
340 if (err)
341 bucket_table_free(new_tbl);
342
343 return err;
295}
344}
296EXPORT_SYMBOL_GPL(rhashtable_shrink);
297
298static void rht_deferred_worker(struct work_struct *work)
299{
300 struct rhashtable *ht;
301 struct bucket_table *tbl;
345
346static void rht_deferred_worker(struct work_struct *work)
347{
348 struct rhashtable *ht;
349 struct bucket_table *tbl;
350 int err = 0;
302
303 ht = container_of(work, struct rhashtable, run_work);
304 mutex_lock(&ht->mutex);
305 if (ht->being_destroyed)
306 goto unlock;
307
308 tbl = rht_dereference(ht->tbl, ht);
351
352 ht = container_of(work, struct rhashtable, run_work);
353 mutex_lock(&ht->mutex);
354 if (ht->being_destroyed)
355 goto unlock;
356
357 tbl = rht_dereference(ht->tbl, ht);
358 tbl = rhashtable_last_table(ht, tbl);
309
310 if (rht_grow_above_75(ht, tbl))
311 rhashtable_expand(ht);
312 else if (rht_shrink_below_30(ht, tbl))
313 rhashtable_shrink(ht);
359
360 if (rht_grow_above_75(ht, tbl))
361 rhashtable_expand(ht);
362 else if (rht_shrink_below_30(ht, tbl))
363 rhashtable_shrink(ht);
364
365 err = rhashtable_rehash_table(ht);
366
314unlock:
315 mutex_unlock(&ht->mutex);
367unlock:
368 mutex_unlock(&ht->mutex);
369
370 if (err)
371 schedule_work(&ht->run_work);
316}
317
318int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
319 struct rhash_head *obj,
320 struct bucket_table *tbl)
321{
322 struct rhash_head *head;
323 unsigned hash;
324 int err = -EEXIST;
325
372}
373
374int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
375 struct rhash_head *obj,
376 struct bucket_table *tbl)
377{
378 struct rhash_head *head;
379 unsigned hash;
380 int err = -EEXIST;
381
382 tbl = rhashtable_last_table(ht, tbl);
326 hash = head_hashfn(ht, tbl, obj);
327 spin_lock_nested(rht_bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);
328
329 if (key && rhashtable_lookup_fast(ht, key, ht->p))
330 goto exit;
331
332 err = 0;
333

--- 334 unchanged lines hidden --- 		383 hash = head_hashfn(ht, tbl, obj);
384 spin_lock_nested(rht_bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);
385
386 if (key && rhashtable_lookup_fast(ht, key, ht->p))
387 goto exit;
388
389 err = 0;
390

--- 334 unchanged lines hidden ---