rhashtable.c 29.7 KB
Newer Older
1 2 3
/*
 * 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 7 8
 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
 *
 * Code partially derived from nft_hash
9 10
 * Rewritten with rehash code from br_multicast plus single list
 * pointer as suggested by Josh Triplett
11 12 13 14 15 16
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */

17
#include <linux/atomic.h>
18 19 20
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/log2.h>
E
Eric Dumazet 已提交
21
#include <linux/sched.h>
22
#include <linux/rculist.h>
23 24 25
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/mm.h>
26
#include <linux/jhash.h>
27 28
#include <linux/random.h>
#include <linux/rhashtable.h>
29
#include <linux/err.h>
30
#include <linux/export.h>
31 32

#define HASH_DEFAULT_SIZE	64UL
33
#define HASH_MIN_SIZE		4U
34
#define BUCKET_LOCKS_PER_CPU	32UL
35

H
Herbert Xu 已提交
36 37 38 39 40
union nested_table {
	union nested_table __rcu *table;
	struct rhash_head __rcu *bucket;
};

41
static u32 head_hashfn(struct rhashtable *ht,
42 43
		       const struct bucket_table *tbl,
		       const struct rhash_head *he)
44
{
45
	return rht_head_hashfn(ht, tbl, he, ht->p);
46 47
}

48 49 50 51 52 53 54 55 56 57 58
#ifdef CONFIG_PROVE_LOCKING
#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))

int lockdep_rht_mutex_is_held(struct rhashtable *ht)
{
	return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
}
EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);

int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
{
59
	spinlock_t *lock = rht_bucket_lock(tbl, hash);
60 61 62 63 64 65 66 67

	return (debug_locks) ? lockdep_is_held(lock) : 1;
}
EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
#else
#define ASSERT_RHT_MUTEX(HT)
#endif

H
Herbert Xu 已提交
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
static void nested_table_free(union nested_table *ntbl, unsigned int size)
{
	const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
	const unsigned int len = 1 << shift;
	unsigned int i;

	ntbl = rcu_dereference_raw(ntbl->table);
	if (!ntbl)
		return;

	if (size > len) {
		size >>= shift;
		for (i = 0; i < len; i++)
			nested_table_free(ntbl + i, size);
	}

	kfree(ntbl);
}

static void nested_bucket_table_free(const struct bucket_table *tbl)
{
	unsigned int size = tbl->size >> tbl->nest;
	unsigned int len = 1 << tbl->nest;
	union nested_table *ntbl;
	unsigned int i;

	ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);

	for (i = 0; i < len; i++)
		nested_table_free(ntbl + i, size);

	kfree(ntbl);
}

102 103
static void bucket_table_free(const struct bucket_table *tbl)
{
H
Herbert Xu 已提交
104 105 106
	if (tbl->nest)
		nested_bucket_table_free(tbl);

107
	free_bucket_spinlocks(tbl->locks);
108 109 110
	kvfree(tbl);
}

111 112 113 114 115
static void bucket_table_free_rcu(struct rcu_head *head)
{
	bucket_table_free(container_of(head, struct bucket_table, rcu));
}

H
Herbert Xu 已提交
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
static union nested_table *nested_table_alloc(struct rhashtable *ht,
					      union nested_table __rcu **prev,
					      unsigned int shifted,
					      unsigned int nhash)
{
	union nested_table *ntbl;
	int i;

	ntbl = rcu_dereference(*prev);
	if (ntbl)
		return ntbl;

	ntbl = kzalloc(PAGE_SIZE, GFP_ATOMIC);

	if (ntbl && shifted) {
		for (i = 0; i < PAGE_SIZE / sizeof(ntbl[0].bucket); i++)
			INIT_RHT_NULLS_HEAD(ntbl[i].bucket, ht,
					    (i << shifted) | nhash);
	}

	rcu_assign_pointer(*prev, ntbl);

	return ntbl;
}

static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht,
						      size_t nbuckets,
						      gfp_t gfp)
{
	const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
	struct bucket_table *tbl;
	size_t size;

	if (nbuckets < (1 << (shift + 1)))
		return NULL;

	size = sizeof(*tbl) + sizeof(tbl->buckets[0]);

	tbl = kzalloc(size, gfp);
	if (!tbl)
		return NULL;

	if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets,
				0, 0)) {
		kfree(tbl);
		return NULL;
	}

	tbl->nest = (ilog2(nbuckets) - 1) % shift + 1;

	return tbl;
}

169
static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
170 171
					       size_t nbuckets,
					       gfp_t gfp)
172
{
173
	struct bucket_table *tbl = NULL;
174
	size_t size, max_locks;
175
	int i;
176 177

	size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
178
	if (gfp != GFP_KERNEL)
179
		tbl = kzalloc(size, gfp | __GFP_NOWARN | __GFP_NORETRY);
180 181
	else
		tbl = kvzalloc(size, gfp);
H
Herbert Xu 已提交
182 183 184 185 186 187 188

	size = nbuckets;

	if (tbl == NULL && gfp != GFP_KERNEL) {
		tbl = nested_bucket_table_alloc(ht, nbuckets, gfp);
		nbuckets = 0;
	}
189 190 191
	if (tbl == NULL)
		return NULL;

H
Herbert Xu 已提交
192
	tbl->size = size;
193

194 195 196 197 198 199
	max_locks = size >> 1;
	if (tbl->nest)
		max_locks = min_t(size_t, max_locks, 1U << tbl->nest);

	if (alloc_bucket_spinlocks(&tbl->locks, &tbl->locks_mask, max_locks,
				   ht->p.locks_mul, gfp) < 0) {
200 201 202
		bucket_table_free(tbl);
		return NULL;
	}
203

204 205
	INIT_LIST_HEAD(&tbl->walkers);

206
	tbl->hash_rnd = get_random_u32();
207

208 209 210
	for (i = 0; i < nbuckets; i++)
		INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);

211
	return tbl;
212 213
}

214 215 216 217 218 219 220 221 222 223 224 225 226
static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,
						  struct bucket_table *tbl)
{
	struct bucket_table *new_tbl;

	do {
		new_tbl = tbl;
		tbl = rht_dereference_rcu(tbl->future_tbl, ht);
	} while (tbl);

	return new_tbl;
}

227
static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
228
{
229
	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
230 231
	struct bucket_table *new_tbl = rhashtable_last_table(ht,
		rht_dereference_rcu(old_tbl->future_tbl, ht));
H
Herbert Xu 已提交
232 233
	struct rhash_head __rcu **pprev = rht_bucket_var(old_tbl, old_hash);
	int err = -EAGAIN;
234 235
	struct rhash_head *head, *next, *entry;
	spinlock_t *new_bucket_lock;
236
	unsigned int new_hash;
237

H
Herbert Xu 已提交
238 239 240 241 242
	if (new_tbl->nest)
		goto out;

	err = -ENOENT;

243 244 245 246 247 248
	rht_for_each(entry, old_tbl, old_hash) {
		err = 0;
		next = rht_dereference_bucket(entry->next, old_tbl, old_hash);

		if (rht_is_a_nulls(next))
			break;
249

250 251
		pprev = &entry->next;
	}
252

253 254
	if (err)
		goto out;
255

256
	new_hash = head_hashfn(ht, new_tbl, entry);
257

258
	new_bucket_lock = rht_bucket_lock(new_tbl, new_hash);
259

260
	spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
261 262
	head = rht_dereference_bucket(new_tbl->buckets[new_hash],
				      new_tbl, new_hash);
263

264
	RCU_INIT_POINTER(entry->next, head);
265

266 267
	rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
	spin_unlock(new_bucket_lock);
268

269
	rcu_assign_pointer(*pprev, next);
270

271 272 273
out:
	return err;
}
274

H
Herbert Xu 已提交
275
static int rhashtable_rehash_chain(struct rhashtable *ht,
276
				    unsigned int old_hash)
277 278 279
{
	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
	spinlock_t *old_bucket_lock;
H
Herbert Xu 已提交
280
	int err;
281

282
	old_bucket_lock = rht_bucket_lock(old_tbl, old_hash);
283

284
	spin_lock_bh(old_bucket_lock);
H
Herbert Xu 已提交
285
	while (!(err = rhashtable_rehash_one(ht, old_hash)))
286
		;
H
Herbert Xu 已提交
287 288 289 290 291

	if (err == -ENOENT) {
		old_tbl->rehash++;
		err = 0;
	}
292
	spin_unlock_bh(old_bucket_lock);
H
Herbert Xu 已提交
293 294

	return err;
295 296
}

297 298 299
static int rhashtable_rehash_attach(struct rhashtable *ht,
				    struct bucket_table *old_tbl,
				    struct bucket_table *new_tbl)
300
{
301 302 303 304 305 306 307 308
	/* Protect future_tbl using the first bucket lock. */
	spin_lock_bh(old_tbl->locks);

	/* Did somebody beat us to it? */
	if (rcu_access_pointer(old_tbl->future_tbl)) {
		spin_unlock_bh(old_tbl->locks);
		return -EEXIST;
	}
309

310 311 312
	/* Make insertions go into the new, empty table right away. Deletions
	 * and lookups will be attempted in both tables until we synchronize.
	 */
313
	rcu_assign_pointer(old_tbl->future_tbl, new_tbl);
314

315 316 317 318 319 320 321 322 323 324
	spin_unlock_bh(old_tbl->locks);

	return 0;
}

static int rhashtable_rehash_table(struct rhashtable *ht)
{
	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
	struct bucket_table *new_tbl;
	struct rhashtable_walker *walker;
325
	unsigned int old_hash;
H
Herbert Xu 已提交
326
	int err;
327 328 329 330 331

	new_tbl = rht_dereference(old_tbl->future_tbl, ht);
	if (!new_tbl)
		return 0;

H
Herbert Xu 已提交
332 333 334 335
	for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
		err = rhashtable_rehash_chain(ht, old_hash);
		if (err)
			return err;
E
Eric Dumazet 已提交
336
		cond_resched();
H
Herbert Xu 已提交
337
	}
338 339 340 341

	/* Publish the new table pointer. */
	rcu_assign_pointer(ht->tbl, new_tbl);

342
	spin_lock(&ht->lock);
343 344
	list_for_each_entry(walker, &old_tbl->walkers, list)
		walker->tbl = NULL;
345
	spin_unlock(&ht->lock);
346

347 348 349 350
	/* Wait for readers. All new readers will see the new
	 * table, and thus no references to the old table will
	 * remain.
	 */
351
	call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
352 353

	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
354 355
}

H
Herbert Xu 已提交
356 357 358
static int rhashtable_rehash_alloc(struct rhashtable *ht,
				   struct bucket_table *old_tbl,
				   unsigned int size)
359
{
H
Herbert Xu 已提交
360
	struct bucket_table *new_tbl;
361
	int err;
362 363 364

	ASSERT_RHT_MUTEX(ht);

H
Herbert Xu 已提交
365
	new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
366 367 368
	if (new_tbl == NULL)
		return -ENOMEM;

369 370 371 372 373
	err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);
	if (err)
		bucket_table_free(new_tbl);

	return err;
374 375 376 377 378 379
}

/**
 * rhashtable_shrink - Shrink hash table while allowing concurrent lookups
 * @ht:		the hash table to shrink
 *
H
Herbert Xu 已提交
380 381
 * This function shrinks the hash table to fit, i.e., the smallest
 * size would not cause it to expand right away automatically.
382
 *
383 384 385
 * The caller must ensure that no concurrent resizing occurs by holding
 * ht->mutex.
 *
386 387
 * The caller must ensure that no concurrent table mutations take place.
 * It is however valid to have concurrent lookups if they are RCU protected.
388 389 390
 *
 * It is valid to have concurrent insertions and deletions protected by per
 * bucket locks or concurrent RCU protected lookups and traversals.
391
 */
392
static int rhashtable_shrink(struct rhashtable *ht)
393
{
H
Herbert Xu 已提交
394
	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
395 396
	unsigned int nelems = atomic_read(&ht->nelems);
	unsigned int size = 0;
397

398 399
	if (nelems)
		size = roundup_pow_of_two(nelems * 3 / 2);
H
Herbert Xu 已提交
400 401 402 403 404 405
	if (size < ht->p.min_size)
		size = ht->p.min_size;

	if (old_tbl->size <= size)
		return 0;

406 407 408
	if (rht_dereference(old_tbl->future_tbl, ht))
		return -EEXIST;

H
Herbert Xu 已提交
409
	return rhashtable_rehash_alloc(ht, old_tbl, size);
410 411
}

412 413 414 415
static void rht_deferred_worker(struct work_struct *work)
{
	struct rhashtable *ht;
	struct bucket_table *tbl;
416
	int err = 0;
417

418
	ht = container_of(work, struct rhashtable, run_work);
419
	mutex_lock(&ht->mutex);
420

421
	tbl = rht_dereference(ht->tbl, ht);
422
	tbl = rhashtable_last_table(ht, tbl);
423

424
	if (rht_grow_above_75(ht, tbl))
H
Herbert Xu 已提交
425
		err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2);
426
	else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
H
Herbert Xu 已提交
427 428 429
		err = rhashtable_shrink(ht);
	else if (tbl->nest)
		err = rhashtable_rehash_alloc(ht, tbl, tbl->size);
430

H
Herbert Xu 已提交
431 432
	if (!err)
		err = rhashtable_rehash_table(ht);
433

434
	mutex_unlock(&ht->mutex);
435 436 437

	if (err)
		schedule_work(&ht->run_work);
438 439
}

H
Herbert Xu 已提交
440 441
static int rhashtable_insert_rehash(struct rhashtable *ht,
				    struct bucket_table *tbl)
442 443 444 445 446 447 448 449 450 451
{
	struct bucket_table *old_tbl;
	struct bucket_table *new_tbl;
	unsigned int size;
	int err;

	old_tbl = rht_dereference_rcu(ht->tbl, ht);

	size = tbl->size;

452 453
	err = -EBUSY;

454 455
	if (rht_grow_above_75(ht, tbl))
		size *= 2;
456 457
	/* Do not schedule more than one rehash */
	else if (old_tbl != tbl)
458 459 460
		goto fail;

	err = -ENOMEM;
461 462

	new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC);
463 464
	if (new_tbl == NULL)
		goto fail;
465 466 467 468 469 470 471 472 473 474

	err = rhashtable_rehash_attach(ht, tbl, new_tbl);
	if (err) {
		bucket_table_free(new_tbl);
		if (err == -EEXIST)
			err = 0;
	} else
		schedule_work(&ht->run_work);

	return err;
475 476 477 478 479 480 481 482 483 484 485

fail:
	/* Do not fail the insert if someone else did a rehash. */
	if (likely(rcu_dereference_raw(tbl->future_tbl)))
		return 0;

	/* Schedule async rehash to retry allocation in process context. */
	if (err == -ENOMEM)
		schedule_work(&ht->run_work);

	return err;
486 487
}

H
Herbert Xu 已提交
488 489 490
static void *rhashtable_lookup_one(struct rhashtable *ht,
				   struct bucket_table *tbl, unsigned int hash,
				   const void *key, struct rhash_head *obj)
491
{
H
Herbert Xu 已提交
492 493 494 495 496
	struct rhashtable_compare_arg arg = {
		.ht = ht,
		.key = key,
	};
	struct rhash_head __rcu **pprev;
497
	struct rhash_head *head;
H
Herbert Xu 已提交
498
	int elasticity;
499

500
	elasticity = RHT_ELASTICITY;
H
Herbert Xu 已提交
501 502
	pprev = rht_bucket_var(tbl, hash);
	rht_for_each_continue(head, *pprev, tbl, hash) {
H
Herbert Xu 已提交
503 504 505 506 507 508 509
		struct rhlist_head *list;
		struct rhlist_head *plist;

		elasticity--;
		if (!key ||
		    (ht->p.obj_cmpfn ?
		     ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
510 511
		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
			pprev = &head->next;
H
Herbert Xu 已提交
512
			continue;
513
		}
H
Herbert Xu 已提交
514 515 516 517 518 519 520 521 522 523 524 525 526

		if (!ht->rhlist)
			return rht_obj(ht, head);

		list = container_of(obj, struct rhlist_head, rhead);
		plist = container_of(head, struct rhlist_head, rhead);

		RCU_INIT_POINTER(list->next, plist);
		head = rht_dereference_bucket(head->next, tbl, hash);
		RCU_INIT_POINTER(list->rhead.next, head);
		rcu_assign_pointer(*pprev, obj);

		return NULL;
527
	}
528

H
Herbert Xu 已提交
529 530 531 532 533 534 535 536 537 538 539 540
	if (elasticity <= 0)
		return ERR_PTR(-EAGAIN);

	return ERR_PTR(-ENOENT);
}

static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht,
						  struct bucket_table *tbl,
						  unsigned int hash,
						  struct rhash_head *obj,
						  void *data)
{
H
Herbert Xu 已提交
541
	struct rhash_head __rcu **pprev;
H
Herbert Xu 已提交
542 543 544 545 546
	struct bucket_table *new_tbl;
	struct rhash_head *head;

	if (!IS_ERR_OR_NULL(data))
		return ERR_PTR(-EEXIST);
547

H
Herbert Xu 已提交
548 549
	if (PTR_ERR(data) != -EAGAIN && PTR_ERR(data) != -ENOENT)
		return ERR_CAST(data);
550

H
Herbert Xu 已提交
551 552 553 554 555 556 557 558 559 560 561 562
	new_tbl = rcu_dereference(tbl->future_tbl);
	if (new_tbl)
		return new_tbl;

	if (PTR_ERR(data) != -ENOENT)
		return ERR_CAST(data);

	if (unlikely(rht_grow_above_max(ht, tbl)))
		return ERR_PTR(-E2BIG);

	if (unlikely(rht_grow_above_100(ht, tbl)))
		return ERR_PTR(-EAGAIN);
563

H
Herbert Xu 已提交
564 565 566 567 568
	pprev = rht_bucket_insert(ht, tbl, hash);
	if (!pprev)
		return ERR_PTR(-ENOMEM);

	head = rht_dereference_bucket(*pprev, tbl, hash);
569 570

	RCU_INIT_POINTER(obj->next, head);
H
Herbert Xu 已提交
571 572 573 574 575 576
	if (ht->rhlist) {
		struct rhlist_head *list;

		list = container_of(obj, struct rhlist_head, rhead);
		RCU_INIT_POINTER(list->next, NULL);
	}
577

H
Herbert Xu 已提交
578
	rcu_assign_pointer(*pprev, obj);
579 580

	atomic_inc(&ht->nelems);
H
Herbert Xu 已提交
581 582
	if (rht_grow_above_75(ht, tbl))
		schedule_work(&ht->run_work);
583

H
Herbert Xu 已提交
584 585
	return NULL;
}
586

H
Herbert Xu 已提交
587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652
static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
				   struct rhash_head *obj)
{
	struct bucket_table *new_tbl;
	struct bucket_table *tbl;
	unsigned int hash;
	spinlock_t *lock;
	void *data;

	tbl = rcu_dereference(ht->tbl);

	/* All insertions must grab the oldest table containing
	 * the hashed bucket that is yet to be rehashed.
	 */
	for (;;) {
		hash = rht_head_hashfn(ht, tbl, obj, ht->p);
		lock = rht_bucket_lock(tbl, hash);
		spin_lock_bh(lock);

		if (tbl->rehash <= hash)
			break;

		spin_unlock_bh(lock);
		tbl = rcu_dereference(tbl->future_tbl);
	}

	data = rhashtable_lookup_one(ht, tbl, hash, key, obj);
	new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data);
	if (PTR_ERR(new_tbl) != -EEXIST)
		data = ERR_CAST(new_tbl);

	while (!IS_ERR_OR_NULL(new_tbl)) {
		tbl = new_tbl;
		hash = rht_head_hashfn(ht, tbl, obj, ht->p);
		spin_lock_nested(rht_bucket_lock(tbl, hash),
				 SINGLE_DEPTH_NESTING);

		data = rhashtable_lookup_one(ht, tbl, hash, key, obj);
		new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data);
		if (PTR_ERR(new_tbl) != -EEXIST)
			data = ERR_CAST(new_tbl);

		spin_unlock(rht_bucket_lock(tbl, hash));
	}

	spin_unlock_bh(lock);

	if (PTR_ERR(data) == -EAGAIN)
		data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?:
			       -EAGAIN);

	return data;
}

void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
			     struct rhash_head *obj)
{
	void *data;

	do {
		rcu_read_lock();
		data = rhashtable_try_insert(ht, key, obj);
		rcu_read_unlock();
	} while (PTR_ERR(data) == -EAGAIN);

	return data;
653 654 655
}
EXPORT_SYMBOL_GPL(rhashtable_insert_slow);

656
/**
657
 * rhashtable_walk_enter - Initialise an iterator
658 659 660 661 662 663 664 665 666 667 668 669 670
 * @ht:		Table to walk over
 * @iter:	Hash table Iterator
 *
 * This function prepares a hash table walk.
 *
 * Note that if you restart a walk after rhashtable_walk_stop you
 * may see the same object twice.  Also, you may miss objects if
 * there are removals in between rhashtable_walk_stop and the next
 * call to rhashtable_walk_start.
 *
 * For a completely stable walk you should construct your own data
 * structure outside the hash table.
 *
671 672 673
 * This function may be called from any process context, including
 * non-preemptable context, but cannot be called from softirq or
 * hardirq context.
674
 *
675
 * You must call rhashtable_walk_exit after this function returns.
676
 */
677
void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)
678 679 680 681 682
{
	iter->ht = ht;
	iter->p = NULL;
	iter->slot = 0;
	iter->skip = 0;
T
Tom Herbert 已提交
683
	iter->end_of_table = 0;
684

685
	spin_lock(&ht->lock);
686
	iter->walker.tbl =
687
		rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
688
	list_add(&iter->walker.list, &iter->walker.tbl->walkers);
689
	spin_unlock(&ht->lock);
690
}
691
EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
692 693 694 695 696 697 698 699 700

/**
 * rhashtable_walk_exit - Free an iterator
 * @iter:	Hash table Iterator
 *
 * This function frees resources allocated by rhashtable_walk_init.
 */
void rhashtable_walk_exit(struct rhashtable_iter *iter)
{
701
	spin_lock(&iter->ht->lock);
702 703
	if (iter->walker.tbl)
		list_del(&iter->walker.list);
704
	spin_unlock(&iter->ht->lock);
705 706 707 708
}
EXPORT_SYMBOL_GPL(rhashtable_walk_exit);

/**
709
 * rhashtable_walk_start_check - Start a hash table walk
710 711
 * @iter:	Hash table iterator
 *
712 713 714
 * Start a hash table walk at the current iterator position.  Note that we take
 * the RCU lock in all cases including when we return an error.  So you must
 * always call rhashtable_walk_stop to clean up.
715 716 717 718 719 720
 *
 * Returns zero if successful.
 *
 * Returns -EAGAIN if resize event occured.  Note that the iterator
 * will rewind back to the beginning and you may use it immediately
 * by calling rhashtable_walk_next.
721 722 723 724
 *
 * rhashtable_walk_start is defined as an inline variant that returns
 * void. This is preferred in cases where the caller would ignore
 * resize events and always continue.
725
 */
726
int rhashtable_walk_start_check(struct rhashtable_iter *iter)
727
	__acquires(RCU)
728
{
729
	struct rhashtable *ht = iter->ht;
730
	bool rhlist = ht->rhlist;
731

732
	rcu_read_lock();
733

734
	spin_lock(&ht->lock);
735 736
	if (iter->walker.tbl)
		list_del(&iter->walker.list);
737
	spin_unlock(&ht->lock);
738

739 740 741
	if (iter->end_of_table)
		return 0;
	if (!iter->walker.tbl) {
742
		iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);
743 744
		iter->slot = 0;
		iter->skip = 0;
745 746 747
		return -EAGAIN;
	}

748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776
	if (iter->p && !rhlist) {
		/*
		 * We need to validate that 'p' is still in the table, and
		 * if so, update 'skip'
		 */
		struct rhash_head *p;
		int skip = 0;
		rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
			skip++;
			if (p == iter->p) {
				iter->skip = skip;
				goto found;
			}
		}
		iter->p = NULL;
	} else if (iter->p && rhlist) {
		/* Need to validate that 'list' is still in the table, and
		 * if so, update 'skip' and 'p'.
		 */
		struct rhash_head *p;
		struct rhlist_head *list;
		int skip = 0;
		rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
			for (list = container_of(p, struct rhlist_head, rhead);
			     list;
			     list = rcu_dereference(list->next)) {
				skip++;
				if (list == iter->list) {
					iter->p = p;
777
					iter->skip = skip;
778 779 780 781 782 783 784
					goto found;
				}
			}
		}
		iter->p = NULL;
	}
found:
785 786
	return 0;
}
787
EXPORT_SYMBOL_GPL(rhashtable_walk_start_check);
788 789

/**
T
Tom Herbert 已提交
790 791 792
 * __rhashtable_walk_find_next - Find the next element in a table (or the first
 * one in case of a new walk).
 *
793 794
 * @iter:	Hash table iterator
 *
T
Tom Herbert 已提交
795
 * Returns the found object or NULL when the end of the table is reached.
796
 *
T
Tom Herbert 已提交
797
 * Returns -EAGAIN if resize event occurred.
798
 */
T
Tom Herbert 已提交
799
static void *__rhashtable_walk_find_next(struct rhashtable_iter *iter)
800
{
801
	struct bucket_table *tbl = iter->walker.tbl;
H
Herbert Xu 已提交
802
	struct rhlist_head *list = iter->list;
803 804
	struct rhashtable *ht = iter->ht;
	struct rhash_head *p = iter->p;
H
Herbert Xu 已提交
805
	bool rhlist = ht->rhlist;
806

T
Tom Herbert 已提交
807 808
	if (!tbl)
		return NULL;
809 810 811 812 813

	for (; iter->slot < tbl->size; iter->slot++) {
		int skip = iter->skip;

		rht_for_each_rcu(p, tbl, iter->slot) {
H
Herbert Xu 已提交
814 815 816 817 818 819 820 821 822 823 824 825
			if (rhlist) {
				list = container_of(p, struct rhlist_head,
						    rhead);
				do {
					if (!skip)
						goto next;
					skip--;
					list = rcu_dereference(list->next);
				} while (list);

				continue;
			}
826 827 828 829 830 831 832 833 834
			if (!skip)
				break;
			skip--;
		}

next:
		if (!rht_is_a_nulls(p)) {
			iter->skip++;
			iter->p = p;
H
Herbert Xu 已提交
835 836
			iter->list = list;
			return rht_obj(ht, rhlist ? &list->rhead : p);
837 838 839 840 841
		}

		iter->skip = 0;
	}

842 843
	iter->p = NULL;

844 845 846
	/* Ensure we see any new tables. */
	smp_rmb();

847 848
	iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht);
	if (iter->walker.tbl) {
849 850 851
		iter->slot = 0;
		iter->skip = 0;
		return ERR_PTR(-EAGAIN);
T
Tom Herbert 已提交
852 853
	} else {
		iter->end_of_table = true;
854 855
	}

T
Thomas Graf 已提交
856
	return NULL;
857
}
T
Tom Herbert 已提交
858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898

/**
 * rhashtable_walk_next - Return the next object and advance the iterator
 * @iter:	Hash table iterator
 *
 * Note that you must call rhashtable_walk_stop when you are finished
 * with the walk.
 *
 * Returns the next object or NULL when the end of the table is reached.
 *
 * Returns -EAGAIN if resize event occurred.  Note that the iterator
 * will rewind back to the beginning and you may continue to use it.
 */
void *rhashtable_walk_next(struct rhashtable_iter *iter)
{
	struct rhlist_head *list = iter->list;
	struct rhashtable *ht = iter->ht;
	struct rhash_head *p = iter->p;
	bool rhlist = ht->rhlist;

	if (p) {
		if (!rhlist || !(list = rcu_dereference(list->next))) {
			p = rcu_dereference(p->next);
			list = container_of(p, struct rhlist_head, rhead);
		}
		if (!rht_is_a_nulls(p)) {
			iter->skip++;
			iter->p = p;
			iter->list = list;
			return rht_obj(ht, rhlist ? &list->rhead : p);
		}

		/* At the end of this slot, switch to next one and then find
		 * next entry from that point.
		 */
		iter->skip = 0;
		iter->slot++;
	}

	return __rhashtable_walk_find_next(iter);
}
899 900
EXPORT_SYMBOL_GPL(rhashtable_walk_next);

T
Tom Herbert 已提交
901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934
/**
 * rhashtable_walk_peek - Return the next object but don't advance the iterator
 * @iter:	Hash table iterator
 *
 * Returns the next object or NULL when the end of the table is reached.
 *
 * Returns -EAGAIN if resize event occurred.  Note that the iterator
 * will rewind back to the beginning and you may continue to use it.
 */
void *rhashtable_walk_peek(struct rhashtable_iter *iter)
{
	struct rhlist_head *list = iter->list;
	struct rhashtable *ht = iter->ht;
	struct rhash_head *p = iter->p;

	if (p)
		return rht_obj(ht, ht->rhlist ? &list->rhead : p);

	/* No object found in current iter, find next one in the table. */

	if (iter->skip) {
		/* A nonzero skip value points to the next entry in the table
		 * beyond that last one that was found. Decrement skip so
		 * we find the current value. __rhashtable_walk_find_next
		 * will restore the original value of skip assuming that
		 * the table hasn't changed.
		 */
		iter->skip--;
	}

	return __rhashtable_walk_find_next(iter);
}
EXPORT_SYMBOL_GPL(rhashtable_walk_peek);

935 936 937 938
/**
 * rhashtable_walk_stop - Finish a hash table walk
 * @iter:	Hash table iterator
 *
939 940
 * Finish a hash table walk.  Does not reset the iterator to the start of the
 * hash table.
941 942
 */
void rhashtable_walk_stop(struct rhashtable_iter *iter)
943
	__releases(RCU)
944
{
945
	struct rhashtable *ht;
946
	struct bucket_table *tbl = iter->walker.tbl;
947 948

	if (!tbl)
949
		goto out;
950 951 952

	ht = iter->ht;

953
	spin_lock(&ht->lock);
954
	if (tbl->rehash < tbl->size)
955
		list_add(&iter->walker.list, &tbl->walkers);
956
	else
957
		iter->walker.tbl = NULL;
958
	spin_unlock(&ht->lock);
959

960 961
out:
	rcu_read_unlock();
962 963 964
}
EXPORT_SYMBOL_GPL(rhashtable_walk_stop);

965
static size_t rounded_hashtable_size(const struct rhashtable_params *params)
966
{
967
	return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
968
		   (unsigned long)params->min_size);
969 970
}

971 972 973 974 975
static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
{
	return jhash2(key, length, seed);
}

976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995
/**
 * rhashtable_init - initialize a new hash table
 * @ht:		hash table to be initialized
 * @params:	configuration parameters
 *
 * Initializes a new hash table based on the provided configuration
 * parameters. A table can be configured either with a variable or
 * fixed length key:
 *
 * Configuration Example 1: Fixed length keys
 * struct test_obj {
 *	int			key;
 *	void *			my_member;
 *	struct rhash_head	node;
 * };
 *
 * struct rhashtable_params params = {
 *	.head_offset = offsetof(struct test_obj, node),
 *	.key_offset = offsetof(struct test_obj, key),
 *	.key_len = sizeof(int),
996
 *	.hashfn = jhash,
997
 *	.nulls_base = (1U << RHT_BASE_SHIFT),
998 999 1000 1001 1002 1003 1004 1005
 * };
 *
 * Configuration Example 2: Variable length keys
 * struct test_obj {
 *	[...]
 *	struct rhash_head	node;
 * };
 *
1006
 * u32 my_hash_fn(const void *data, u32 len, u32 seed)
1007 1008 1009 1010 1011 1012 1013 1014
 * {
 *	struct test_obj *obj = data;
 *
 *	return [... hash ...];
 * }
 *
 * struct rhashtable_params params = {
 *	.head_offset = offsetof(struct test_obj, node),
1015
 *	.hashfn = jhash,
1016 1017 1018
 *	.obj_hashfn = my_hash_fn,
 * };
 */
1019 1020
int rhashtable_init(struct rhashtable *ht,
		    const struct rhashtable_params *params)
1021 1022 1023 1024 1025 1026
{
	struct bucket_table *tbl;
	size_t size;

	size = HASH_DEFAULT_SIZE;

1027
	if ((!params->key_len && !params->obj_hashfn) ||
1028
	    (params->obj_hashfn && !params->obj_cmpfn))
1029 1030
		return -EINVAL;

1031 1032 1033
	if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
		return -EINVAL;

1034 1035
	memset(ht, 0, sizeof(*ht));
	mutex_init(&ht->mutex);
1036
	spin_lock_init(&ht->lock);
1037 1038
	memcpy(&ht->p, params, sizeof(*params));

1039 1040 1041
	if (params->min_size)
		ht->p.min_size = roundup_pow_of_two(params->min_size);

1042 1043
	/* Cap total entries at 2^31 to avoid nelems overflow. */
	ht->max_elems = 1u << 31;
1044 1045 1046 1047 1048 1049

	if (params->max_size) {
		ht->p.max_size = rounddown_pow_of_two(params->max_size);
		if (ht->p.max_size < ht->max_elems / 2)
			ht->max_elems = ht->p.max_size * 2;
	}
1050

1051
	ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);
1052

1053 1054 1055
	if (params->nelem_hint)
		size = rounded_hashtable_size(&ht->p);

1056 1057 1058 1059 1060
	if (params->locks_mul)
		ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
	else
		ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;

1061 1062 1063 1064 1065 1066 1067 1068 1069 1070
	ht->key_len = ht->p.key_len;
	if (!params->hashfn) {
		ht->p.hashfn = jhash;

		if (!(ht->key_len & (sizeof(u32) - 1))) {
			ht->key_len /= sizeof(u32);
			ht->p.hashfn = rhashtable_jhash2;
		}
	}

1071
	tbl = bucket_table_alloc(ht, size, GFP_KERNEL);
1072 1073 1074
	if (tbl == NULL)
		return -ENOMEM;

1075
	atomic_set(&ht->nelems, 0);
1076

1077 1078
	RCU_INIT_POINTER(ht->tbl, tbl);

1079
	INIT_WORK(&ht->run_work, rht_deferred_worker);
1080

1081 1082 1083 1084
	return 0;
}
EXPORT_SYMBOL_GPL(rhashtable_init);

H
Herbert Xu 已提交
1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126
/**
 * rhltable_init - initialize a new hash list table
 * @hlt:	hash list table to be initialized
 * @params:	configuration parameters
 *
 * Initializes a new hash list table.
 *
 * See documentation for rhashtable_init.
 */
int rhltable_init(struct rhltable *hlt, const struct rhashtable_params *params)
{
	int err;

	/* No rhlist NULLs marking for now. */
	if (params->nulls_base)
		return -EINVAL;

	err = rhashtable_init(&hlt->ht, params);
	hlt->ht.rhlist = true;
	return err;
}
EXPORT_SYMBOL_GPL(rhltable_init);

static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,
				void (*free_fn)(void *ptr, void *arg),
				void *arg)
{
	struct rhlist_head *list;

	if (!ht->rhlist) {
		free_fn(rht_obj(ht, obj), arg);
		return;
	}

	list = container_of(obj, struct rhlist_head, rhead);
	do {
		obj = &list->rhead;
		list = rht_dereference(list->next, ht);
		free_fn(rht_obj(ht, obj), arg);
	} while (list);
}

1127
/**
1128
 * rhashtable_free_and_destroy - free elements and destroy hash table
1129
 * @ht:		the hash table to destroy
1130 1131
 * @free_fn:	callback to release resources of element
 * @arg:	pointer passed to free_fn
1132
 *
1133 1134 1135 1136 1137 1138 1139 1140
 * Stops an eventual async resize. If defined, invokes free_fn for each
 * element to releasal resources. Please note that RCU protected
 * readers may still be accessing the elements. Releasing of resources
 * must occur in a compatible manner. Then frees the bucket array.
 *
 * This function will eventually sleep to wait for an async resize
 * to complete. The caller is responsible that no further write operations
 * occurs in parallel.
1141
 */
1142 1143 1144
void rhashtable_free_and_destroy(struct rhashtable *ht,
				 void (*free_fn)(void *ptr, void *arg),
				 void *arg)
1145
{
1146
	struct bucket_table *tbl, *next_tbl;
1147
	unsigned int i;
1148

1149
	cancel_work_sync(&ht->run_work);
1150

1151
	mutex_lock(&ht->mutex);
1152
	tbl = rht_dereference(ht->tbl, ht);
1153
restart:
1154 1155 1156 1157
	if (free_fn) {
		for (i = 0; i < tbl->size; i++) {
			struct rhash_head *pos, *next;

E
Eric Dumazet 已提交
1158
			cond_resched();
H
Herbert Xu 已提交
1159
			for (pos = rht_dereference(*rht_bucket(tbl, i), ht),
1160 1161 1162 1163 1164 1165
			     next = !rht_is_a_nulls(pos) ?
					rht_dereference(pos->next, ht) : NULL;
			     !rht_is_a_nulls(pos);
			     pos = next,
			     next = !rht_is_a_nulls(pos) ?
					rht_dereference(pos->next, ht) : NULL)
H
Herbert Xu 已提交
1166
				rhashtable_free_one(ht, pos, free_fn, arg);
1167 1168 1169
		}
	}

1170
	next_tbl = rht_dereference(tbl->future_tbl, ht);
1171
	bucket_table_free(tbl);
1172 1173 1174 1175
	if (next_tbl) {
		tbl = next_tbl;
		goto restart;
	}
1176
	mutex_unlock(&ht->mutex);
1177
}
1178 1179 1180 1181 1182 1183
EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);

void rhashtable_destroy(struct rhashtable *ht)
{
	return rhashtable_free_and_destroy(ht, NULL, NULL);
}
1184
EXPORT_SYMBOL_GPL(rhashtable_destroy);
H
Herbert Xu 已提交
1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197

struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
					    unsigned int hash)
{
	const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
	static struct rhash_head __rcu *rhnull =
		(struct rhash_head __rcu *)NULLS_MARKER(0);
	unsigned int index = hash & ((1 << tbl->nest) - 1);
	unsigned int size = tbl->size >> tbl->nest;
	unsigned int subhash = hash;
	union nested_table *ntbl;

	ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
1198
	ntbl = rht_dereference_bucket_rcu(ntbl[index].table, tbl, hash);
H
Herbert Xu 已提交
1199 1200 1201 1202
	subhash >>= tbl->nest;

	while (ntbl && size > (1 << shift)) {
		index = subhash & ((1 << shift) - 1);
1203 1204
		ntbl = rht_dereference_bucket_rcu(ntbl[index].table,
						  tbl, hash);
H
Herbert Xu 已提交
1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252
		size >>= shift;
		subhash >>= shift;
	}

	if (!ntbl)
		return &rhnull;

	return &ntbl[subhash].bucket;

}
EXPORT_SYMBOL_GPL(rht_bucket_nested);

struct rhash_head __rcu **rht_bucket_nested_insert(struct rhashtable *ht,
						   struct bucket_table *tbl,
						   unsigned int hash)
{
	const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
	unsigned int index = hash & ((1 << tbl->nest) - 1);
	unsigned int size = tbl->size >> tbl->nest;
	union nested_table *ntbl;
	unsigned int shifted;
	unsigned int nhash;

	ntbl = (union nested_table *)rcu_dereference_raw(tbl->buckets[0]);
	hash >>= tbl->nest;
	nhash = index;
	shifted = tbl->nest;
	ntbl = nested_table_alloc(ht, &ntbl[index].table,
				  size <= (1 << shift) ? shifted : 0, nhash);

	while (ntbl && size > (1 << shift)) {
		index = hash & ((1 << shift) - 1);
		size >>= shift;
		hash >>= shift;
		nhash |= index << shifted;
		shifted += shift;
		ntbl = nested_table_alloc(ht, &ntbl[index].table,
					  size <= (1 << shift) ? shifted : 0,
					  nhash);
	}

	if (!ntbl)
		return NULL;

	return &ntbl[hash].bucket;

}
EXPORT_SYMBOL_GPL(rht_bucket_nested_insert);