rhashtable.h

   1/* SPDX-License-Identifier: GPL-2.0 */
   2/*
   3 * Resizable, Scalable, Concurrent Hash Table
   4 *
   5 * Copyright (c) 2015-2016 Herbert Xu <herbert@gondor.apana.org.au>
   6 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
   7 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   8 *
   9 * Code partially derived from nft_hash
  10 * Rewritten with rehash code from br_multicast plus single list
  11 * pointer as suggested by Josh Triplett
  12 *
  13 * This program is free software; you can redistribute it and/or modify
  14 * it under the terms of the GNU General Public License version 2 as
  15 * published by the Free Software Foundation.
  16 */
  17
  18#ifndef _LINUX_RHASHTABLE_H
  19#define _LINUX_RHASHTABLE_H
  20
  21#include <linux/err.h>
  22#include <linux/errno.h>
  23#include <linux/jhash.h>
  24#include <linux/list_nulls.h>
  25#include <linux/workqueue.h>
  26#include <linux/rculist.h>
  27#include <linux/bit_spinlock.h>
  28
  29#include <linux/rhashtable-types.h>
  30/*
  31 * Objects in an rhashtable have an embedded struct rhash_head
  32 * which is linked into as hash chain from the hash table - or one
  33 * of two or more hash tables when the rhashtable is being resized.
  34 * The end of the chain is marked with a special nulls marks which has
  35 * the least significant bit set but otherwise stores the address of
  36 * the hash bucket.  This allows us to be sure we've found the end
  37 * of the right list.
  38 * The value stored in the hash bucket has BIT(0) used as a lock bit.
  39 * This bit must be atomically set before any changes are made to
  40 * the chain.  To avoid dereferencing this pointer without clearing
  41 * the bit first, we use an opaque 'struct rhash_lock_head *' for the
  42 * pointer stored in the bucket.  This struct needs to be defined so
  43 * that rcu_dereference() works on it, but it has no content so a
  44 * cast is needed for it to be useful.  This ensures it isn't
  45 * used by mistake with clearing the lock bit first.
  46 */
  47struct rhash_lock_head {};
  48
  49/* Maximum chain length before rehash
  50 *
  51 * The maximum (not average) chain length grows with the size of the hash
  52 * table, at a rate of (log N)/(log log N).
  53 *
  54 * The value of 16 is selected so that even if the hash table grew to
  55 * 2^32 you would not expect the maximum chain length to exceed it
  56 * unless we are under attack (or extremely unlucky).
  57 *
  58 * As this limit is only to detect attacks, we don't need to set it to a
  59 * lower value as you'd need the chain length to vastly exceed 16 to have
  60 * any real effect on the system.
  61 */
  62#define RHT_ELASTICITY	16u
  63
  64/**
  65 * struct bucket_table - Table of hash buckets
  66 * @size: Number of hash buckets
  67 * @nest: Number of bits of first-level nested table.
  68 * @rehash: Current bucket being rehashed
  69 * @hash_rnd: Random seed to fold into hash
  70 * @walkers: List of active walkers
  71 * @rcu: RCU structure for freeing the table
  72 * @future_tbl: Table under construction during rehashing
  73 * @ntbl: Nested table used when out of memory.
  74 * @buckets: size * hash buckets
  75 */
  76struct bucket_table {
  77	unsigned int		size;
  78	unsigned int		nest;
  79	u32			hash_rnd;
  80	struct list_head	walkers;
  81	struct rcu_head		rcu;
  82
  83	struct bucket_table __rcu *future_tbl;
  84
  85	struct lockdep_map	dep_map;
  86
  87	struct rhash_lock_head __rcu *buckets[] ____cacheline_aligned_in_smp;
  88};
  89
  90/*
  91 * NULLS_MARKER() expects a hash value with the low
  92 * bits mostly likely to be significant, and it discards
  93 * the msb.
  94 * We give it an address, in which the bottom bit is
  95 * always 0, and the msb might be significant.
  96 * So we shift the address down one bit to align with
  97 * expectations and avoid losing a significant bit.
  98 *
  99 * We never store the NULLS_MARKER in the hash table
 100 * itself as we need the lsb for locking.
 101 * Instead we store a NULL
 102 */
 103#define	RHT_NULLS_MARKER(ptr)	\
 104	((void *)NULLS_MARKER(((unsigned long) (ptr)) >> 1))
 105#define INIT_RHT_NULLS_HEAD(ptr)	\
 106	((ptr) = NULL)
 107
 108static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
 109{
 110	return ((unsigned long) ptr & 1);
 111}
 112
 113static inline void *rht_obj(const struct rhashtable *ht,
 114			    const struct rhash_head *he)
 115{
 116	return (char *)he - ht->p.head_offset;
 117}
 118
 119static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
 120					    unsigned int hash)
 121{
 122	return hash & (tbl->size - 1);
 123}
 124
 125static __always_inline unsigned int rht_key_get_hash(struct rhashtable *ht,
 126	const void *key, const struct rhashtable_params params,
 127	unsigned int hash_rnd)
 128{
 129	unsigned int hash;
 130
 131	/* params must be equal to ht->p if it isn't constant. */
 132	if (!__builtin_constant_p(params.key_len))
 133		hash = ht->p.hashfn(key, ht->key_len, hash_rnd);
 134	else if (params.key_len) {
 135		unsigned int key_len = params.key_len;
 136
 137		if (params.hashfn)
 138			hash = params.hashfn(key, key_len, hash_rnd);
 139		else if (key_len & (sizeof(u32) - 1))
 140			hash = jhash(key, key_len, hash_rnd);
 141		else
 142			hash = jhash2(key, key_len / sizeof(u32), hash_rnd);
 143	} else {
 144		unsigned int key_len = ht->p.key_len;
 145
 146		if (params.hashfn)
 147			hash = params.hashfn(key, key_len, hash_rnd);
 148		else
 149			hash = jhash(key, key_len, hash_rnd);
 150	}
 151
 152	return hash;
 153}
 154
 155static __always_inline unsigned int rht_key_hashfn(
 156	struct rhashtable *ht, const struct bucket_table *tbl,
 157	const void *key, const struct rhashtable_params params)
 158{
 159	unsigned int hash = rht_key_get_hash(ht, key, params, tbl->hash_rnd);
 160
 161	return rht_bucket_index(tbl, hash);
 162}
 163
 164static __always_inline unsigned int rht_head_hashfn(
 165	struct rhashtable *ht, const struct bucket_table *tbl,
 166	const struct rhash_head *he, const struct rhashtable_params params)
 167{
 168	const char *ptr = rht_obj(ht, he);
 169
 170	return likely(params.obj_hashfn) ?
 171	       rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
 172							    ht->p.key_len,
 173						       tbl->hash_rnd)) :
 174	       rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
 175}
 176
 177/**
 178 * rht_grow_above_75 - returns true if nelems > 0.75 * table-size
 179 * @ht:		hash table
 180 * @tbl:	current table
 181 */
 182static inline bool rht_grow_above_75(const struct rhashtable *ht,
 183				     const struct bucket_table *tbl)
 184{
 185	/* Expand table when exceeding 75% load */
 186	return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
 187	       (!ht->p.max_size || tbl->size < ht->p.max_size);
 188}
 189
 190/**
 191 * rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
 192 * @ht:		hash table
 193 * @tbl:	current table
 194 */
 195static inline bool rht_shrink_below_30(const struct rhashtable *ht,
 196				       const struct bucket_table *tbl)
 197{
 198	/* Shrink table beneath 30% load */
 199	return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
 200	       tbl->size > ht->p.min_size;
 201}
 202
 203/**
 204 * rht_grow_above_100 - returns true if nelems > table-size
 205 * @ht:		hash table
 206 * @tbl:	current table
 207 */
 208static inline bool rht_grow_above_100(const struct rhashtable *ht,
 209				      const struct bucket_table *tbl)
 210{
 211	return atomic_read(&ht->nelems) > tbl->size &&
 212		(!ht->p.max_size || tbl->size < ht->p.max_size);
 213}
 214
 215/**
 216 * rht_grow_above_max - returns true if table is above maximum
 217 * @ht:		hash table
 218 * @tbl:	current table
 219 */
 220static inline bool rht_grow_above_max(const struct rhashtable *ht,
 221				      const struct bucket_table *tbl)
 222{
 223	return atomic_read(&ht->nelems) >= ht->max_elems;
 224}
 225
 226#ifdef CONFIG_PROVE_LOCKING
 227int lockdep_rht_mutex_is_held(struct rhashtable *ht);
 228int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
 229#else
 230static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
 231{
 232	return 1;
 233}
 234
 235static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
 236					     u32 hash)
 237{
 238	return 1;
 239}
 240#endif /* CONFIG_PROVE_LOCKING */
 241
 242void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
 243			     struct rhash_head *obj);
 244
 245void rhashtable_walk_enter(struct rhashtable *ht,
 246			   struct rhashtable_iter *iter);
 247void rhashtable_walk_exit(struct rhashtable_iter *iter);
 248int rhashtable_walk_start_check(struct rhashtable_iter *iter) __acquires(RCU);
 249
 250static inline void rhashtable_walk_start(struct rhashtable_iter *iter)
 251{
 252	(void)rhashtable_walk_start_check(iter);
 253}
 254
 255void *rhashtable_walk_next(struct rhashtable_iter *iter);
 256void *rhashtable_walk_peek(struct rhashtable_iter *iter);
 257void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
 258
 259void rhashtable_free_and_destroy(struct rhashtable *ht,
 260				 void (*free_fn)(void *ptr, void *arg),
 261				 void *arg);
 262void rhashtable_destroy(struct rhashtable *ht);
 263
 264struct rhash_lock_head __rcu **rht_bucket_nested(
 265	const struct bucket_table *tbl, unsigned int hash);
 266struct rhash_lock_head __rcu **__rht_bucket_nested(
 267	const struct bucket_table *tbl, unsigned int hash);
 268struct rhash_lock_head __rcu **rht_bucket_nested_insert(
 269	struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash);
 270
 271#define rht_dereference(p, ht) \
 272	rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
 273
 274#define rht_dereference_rcu(p, ht) \
 275	rcu_dereference_all_check(p, lockdep_rht_mutex_is_held(ht))
 276
 277#define rht_dereference_bucket(p, tbl, hash) \
 278	rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
 279
 280#define rht_dereference_bucket_rcu(p, tbl, hash) \
 281	rcu_dereference_all_check(p, lockdep_rht_bucket_is_held(tbl, hash))
 282
 283#define rht_entry(tpos, pos, member) \
 284	({ tpos = container_of(pos, typeof(*tpos), member); 1; })
 285
 286static inline struct rhash_lock_head __rcu *const *rht_bucket(
 287	const struct bucket_table *tbl, unsigned int hash)
 288{
 289	return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) :
 290				     &tbl->buckets[hash];
 291}
 292
 293static inline struct rhash_lock_head __rcu **rht_bucket_var(
 294	struct bucket_table *tbl, unsigned int hash)
 295{
 296	return unlikely(tbl->nest) ? __rht_bucket_nested(tbl, hash) :
 297				     &tbl->buckets[hash];
 298}
 299
 300static inline struct rhash_lock_head __rcu **rht_bucket_insert(
 301	struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)
 302{
 303	return unlikely(tbl->nest) ? rht_bucket_nested_insert(ht, tbl, hash) :
 304				     &tbl->buckets[hash];
 305}
 306
 307/*
 308 * We lock a bucket by setting BIT(0) in the pointer - this is always
 309 * zero in real pointers.  The NULLS mark is never stored in the bucket,
 310 * rather we store NULL if the bucket is empty.
 311 * bit_spin_locks do not handle contention well, but the whole point
 312 * of the hashtable design is to achieve minimum per-bucket contention.
 313 * A nested hash table might not have a bucket pointer.  In that case
 314 * we cannot get a lock.  For remove and replace the bucket cannot be
 315 * interesting and doesn't need locking.
 316 * For insert we allocate the bucket if this is the last bucket_table,
 317 * and then take the lock.
 318 * Sometimes we unlock a bucket by writing a new pointer there.  In that
 319 * case we don't need to unlock, but we do need to reset state such as
 320 * local_bh. For that we have rht_assign_unlock().  As rcu_assign_pointer()
 321 * provides the same release semantics that bit_spin_unlock() provides,
 322 * this is safe.
 323 * When we write to a bucket without unlocking, we use rht_assign_locked().
 324 */
 325
 326static inline unsigned long rht_lock(struct bucket_table *tbl,
 327				     struct rhash_lock_head __rcu **bkt)
 328{
 329	unsigned long flags;
 330
 331	local_irq_save(flags);
 332	bit_spin_lock(0, (unsigned long *)bkt);
 333	lock_map_acquire(&tbl->dep_map);
 334	return flags;
 335}
 336
 337static inline unsigned long rht_lock_nested(struct bucket_table *tbl,
 338					struct rhash_lock_head __rcu **bucket,
 339					unsigned int subclass)
 340{
 341	unsigned long flags;
 342
 343	local_irq_save(flags);
 344	bit_spin_lock(0, (unsigned long *)bucket);
 345	lock_acquire_exclusive(&tbl->dep_map, subclass, 0, NULL, _THIS_IP_);
 346	return flags;
 347}
 348
 349static inline void rht_unlock(struct bucket_table *tbl,
 350			      struct rhash_lock_head __rcu **bkt,
 351			      unsigned long flags)
 352{
 353	lock_map_release(&tbl->dep_map);
 354	bit_spin_unlock(0, (unsigned long *)bkt);
 355	local_irq_restore(flags);
 356}
 357
 358enum rht_lookup_freq {
 359	RHT_LOOKUP_NORMAL,
 360	RHT_LOOKUP_LIKELY,
 361};
 362
 363static __always_inline struct rhash_head *__rht_ptr(
 364	struct rhash_lock_head *p, struct rhash_lock_head __rcu *const *bkt,
 365	const enum rht_lookup_freq freq)
 366{
 367	unsigned long p_val = (unsigned long)p & ~BIT(0);
 368
 369	BUILD_BUG_ON(!__builtin_constant_p(freq));
 370
 371	if (freq == RHT_LOOKUP_LIKELY)
 372		return (struct rhash_head *)
 373			(likely(p_val) ? p_val : (unsigned long)RHT_NULLS_MARKER(bkt));
 374	else
 375		return (struct rhash_head *)
 376			(p_val ?: (unsigned long)RHT_NULLS_MARKER(bkt));
 377}
 378
 379/*
 380 * Where 'bkt' is a bucket and might be locked:
 381 *   rht_ptr_rcu() dereferences that pointer and clears the lock bit.
 382 *   rht_ptr() dereferences in a context where the bucket is locked.
 383 *   rht_ptr_exclusive() dereferences in a context where exclusive
 384 *            access is guaranteed, such as when destroying the table.
 385 */
 386static __always_inline struct rhash_head *__rht_ptr_rcu(
 387	struct rhash_lock_head __rcu *const *bkt,
 388	const enum rht_lookup_freq freq)
 389{
 390	return __rht_ptr(rcu_dereference_all(*bkt), bkt, freq);
 391}
 392
 393static inline struct rhash_head *rht_ptr_rcu(
 394	struct rhash_lock_head __rcu *const *bkt)
 395{
 396	return __rht_ptr_rcu(bkt, RHT_LOOKUP_NORMAL);
 397}
 398
 399static inline struct rhash_head *rht_ptr(
 400	struct rhash_lock_head __rcu *const *bkt,
 401	struct bucket_table *tbl,
 402	unsigned int hash)
 403{
 404	return __rht_ptr(rht_dereference_bucket(*bkt, tbl, hash), bkt,
 405			 RHT_LOOKUP_NORMAL);
 406}
 407
 408static inline struct rhash_head *rht_ptr_exclusive(
 409	struct rhash_lock_head __rcu *const *bkt)
 410{
 411	return __rht_ptr(rcu_dereference_protected(*bkt, 1), bkt,
 412			 RHT_LOOKUP_NORMAL);
 413}
 414
 415static inline void rht_assign_locked(struct rhash_lock_head __rcu **bkt,
 416				     struct rhash_head *obj)
 417{
 418	if (rht_is_a_nulls(obj))
 419		obj = NULL;
 420	rcu_assign_pointer(*bkt, (void *)((unsigned long)obj | BIT(0)));
 421}
 422
 423static inline void rht_assign_unlock(struct bucket_table *tbl,
 424				     struct rhash_lock_head __rcu **bkt,
 425				     struct rhash_head *obj,
 426				     unsigned long flags)
 427{
 428	if (rht_is_a_nulls(obj))
 429		obj = NULL;
 430	lock_map_release(&tbl->dep_map);
 431	rcu_assign_pointer(*bkt, (void *)obj);
 432	preempt_enable();
 433	__release(bitlock);
 434	local_irq_restore(flags);
 435}
 436
 437/**
 438 * rht_for_each_from - iterate over hash chain from given head
 439 * @pos:	the &struct rhash_head to use as a loop cursor.
 440 * @head:	the &struct rhash_head to start from
 441 * @tbl:	the &struct bucket_table
 442 * @hash:	the hash value / bucket index
 443 */
 444#define rht_for_each_from(pos, head, tbl, hash) \
 445	for (pos = head;			\
 446	     !rht_is_a_nulls(pos);		\
 447	     pos = rht_dereference_bucket((pos)->next, tbl, hash))
 448
 449/**
 450 * rht_for_each - iterate over hash chain
 451 * @pos:	the &struct rhash_head to use as a loop cursor.
 452 * @tbl:	the &struct bucket_table
 453 * @hash:	the hash value / bucket index
 454 */
 455#define rht_for_each(pos, tbl, hash) \
 456	rht_for_each_from(pos, rht_ptr(rht_bucket(tbl, hash), tbl, hash),  \
 457			  tbl, hash)
 458
 459/**
 460 * rht_for_each_entry_from - iterate over hash chain from given head
 461 * @tpos:	the type * to use as a loop cursor.
 462 * @pos:	the &struct rhash_head to use as a loop cursor.
 463 * @head:	the &struct rhash_head to start from
 464 * @tbl:	the &struct bucket_table
 465 * @hash:	the hash value / bucket index
 466 * @member:	name of the &struct rhash_head within the hashable struct.
 467 */
 468#define rht_for_each_entry_from(tpos, pos, head, tbl, hash, member)	\
 469	for (pos = head;						\
 470	     (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);	\
 471	     pos = rht_dereference_bucket((pos)->next, tbl, hash))
 472
 473/**
 474 * rht_for_each_entry - iterate over hash chain of given type
 475 * @tpos:	the type * to use as a loop cursor.
 476 * @pos:	the &struct rhash_head to use as a loop cursor.
 477 * @tbl:	the &struct bucket_table
 478 * @hash:	the hash value / bucket index
 479 * @member:	name of the &struct rhash_head within the hashable struct.
 480 */
 481#define rht_for_each_entry(tpos, pos, tbl, hash, member)		\
 482	rht_for_each_entry_from(tpos, pos,				\
 483				rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
 484				tbl, hash, member)
 485
 486/**
 487 * rht_for_each_entry_safe - safely iterate over hash chain of given type
 488 * @tpos:	the type * to use as a loop cursor.
 489 * @pos:	the &struct rhash_head to use as a loop cursor.
 490 * @next:	the &struct rhash_head to use as next in loop cursor.
 491 * @tbl:	the &struct bucket_table
 492 * @hash:	the hash value / bucket index
 493 * @member:	name of the &struct rhash_head within the hashable struct.
 494 *
 495 * This hash chain list-traversal primitive allows for the looped code to
 496 * remove the loop cursor from the list.
 497 */
 498#define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member)	      \
 499	for (pos = rht_ptr(rht_bucket(tbl, hash), tbl, hash),		      \
 500	     next = !rht_is_a_nulls(pos) ?				      \
 501		       rht_dereference_bucket(pos->next, tbl, hash) : NULL;   \
 502	     (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);	      \
 503	     pos = next,						      \
 504	     next = !rht_is_a_nulls(pos) ?				      \
 505		       rht_dereference_bucket(pos->next, tbl, hash) : NULL)
 506
 507/**
 508 * rht_for_each_rcu_from - iterate over rcu hash chain from given head
 509 * @pos:	the &struct rhash_head to use as a loop cursor.
 510 * @head:	the &struct rhash_head to start from
 511 * @tbl:	the &struct bucket_table
 512 * @hash:	the hash value / bucket index
 513 *
 514 * This hash chain list-traversal primitive may safely run concurrently with
 515 * the _rcu mutation primitives such as rhashtable_insert() as long as the
 516 * traversal is guarded by rcu_read_lock().
 517 */
 518#define rht_for_each_rcu_from(pos, head, tbl, hash)			\
 519	for (({barrier(); }),						\
 520	     pos = head;						\
 521	     !rht_is_a_nulls(pos);					\
 522	     pos = rcu_dereference_all(pos->next))
 523
 524/**
 525 * rht_for_each_rcu - iterate over rcu hash chain
 526 * @pos:	the &struct rhash_head to use as a loop cursor.
 527 * @tbl:	the &struct bucket_table
 528 * @hash:	the hash value / bucket index
 529 *
 530 * This hash chain list-traversal primitive may safely run concurrently with
 531 * the _rcu mutation primitives such as rhashtable_insert() as long as the
 532 * traversal is guarded by rcu_read_lock().
 533 */
 534#define rht_for_each_rcu(pos, tbl, hash)			\
 535	for (({barrier(); }),					\
 536	     pos = rht_ptr_rcu(rht_bucket(tbl, hash));		\
 537	     !rht_is_a_nulls(pos);				\
 538	     pos = rcu_dereference_all(pos->next))
 539
 540/**
 541 * rht_for_each_entry_rcu_from - iterated over rcu hash chain from given head
 542 * @tpos:	the type * to use as a loop cursor.
 543 * @pos:	the &struct rhash_head to use as a loop cursor.
 544 * @head:	the &struct rhash_head to start from
 545 * @tbl:	the &struct bucket_table
 546 * @hash:	the hash value / bucket index
 547 * @member:	name of the &struct rhash_head within the hashable struct.
 548 *
 549 * This hash chain list-traversal primitive may safely run concurrently with
 550 * the _rcu mutation primitives such as rhashtable_insert() as long as the
 551 * traversal is guarded by rcu_read_lock().
 552 */
 553#define rht_for_each_entry_rcu_from(tpos, pos, head, tbl, hash, member) \
 554	for (({barrier(); }),						    \
 555	     pos = head;						    \
 556	     (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member);	    \
 557	     pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
 558
 559/**
 560 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
 561 * @tpos:	the type * to use as a loop cursor.
 562 * @pos:	the &struct rhash_head to use as a loop cursor.
 563 * @tbl:	the &struct bucket_table
 564 * @hash:	the hash value / bucket index
 565 * @member:	name of the &struct rhash_head within the hashable struct.
 566 *
 567 * This hash chain list-traversal primitive may safely run concurrently with
 568 * the _rcu mutation primitives such as rhashtable_insert() as long as the
 569 * traversal is guarded by rcu_read_lock().
 570 */
 571#define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member)		   \
 572	rht_for_each_entry_rcu_from(tpos, pos,				   \
 573				    rht_ptr_rcu(rht_bucket(tbl, hash)),	   \
 574				    tbl, hash, member)
 575
 576/**
 577 * rhl_for_each_rcu - iterate over rcu hash table list
 578 * @pos:	the &struct rlist_head to use as a loop cursor.
 579 * @list:	the head of the list
 580 *
 581 * This hash chain list-traversal primitive should be used on the
 582 * list returned by rhltable_lookup.
 583 */
 584#define rhl_for_each_rcu(pos, list)					\
 585	for (pos = list; pos; pos = rcu_dereference_all(pos->next))
 586
 587/**
 588 * rhl_for_each_entry_rcu - iterate over rcu hash table list of given type
 589 * @tpos:	the type * to use as a loop cursor.
 590 * @pos:	the &struct rlist_head to use as a loop cursor.
 591 * @list:	the head of the list
 592 * @member:	name of the &struct rlist_head within the hashable struct.
 593 *
 594 * This hash chain list-traversal primitive should be used on the
 595 * list returned by rhltable_lookup.
 596 */
 597#define rhl_for_each_entry_rcu(tpos, pos, list, member)			\
 598	for (pos = list; pos && rht_entry(tpos, pos, member);		\
 599	     pos = rcu_dereference_all(pos->next))
 600
 601static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
 602				     const void *obj)
 603{
 604	struct rhashtable *ht = arg->ht;
 605	const char *ptr = obj;
 606
 607	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
 608}
 609
 610/* Internal function, do not use. */
 611static __always_inline struct rhash_head *__rhashtable_lookup(
 612	struct rhashtable *ht, const void *key,
 613	const struct rhashtable_params params,
 614	const enum rht_lookup_freq freq)
 615{
 616	struct rhashtable_compare_arg arg = {
 617		.ht = ht,
 618		.key = key,
 619	};
 620	struct rhash_lock_head __rcu *const *bkt;
 621	struct bucket_table *tbl;
 622	struct rhash_head *he;
 623	unsigned int hash;
 624
 625	BUILD_BUG_ON(!__builtin_constant_p(freq));
 626	tbl = rht_dereference_rcu(ht->tbl, ht);
 627restart:
 628	hash = rht_key_hashfn(ht, tbl, key, params);
 629	bkt = rht_bucket(tbl, hash);
 630	do {
 631		rht_for_each_rcu_from(he, __rht_ptr_rcu(bkt, freq), tbl, hash) {
 632			if (params.obj_cmpfn ?
 633			    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
 634			    rhashtable_compare(&arg, rht_obj(ht, he)))
 635				continue;
 636			return he;
 637		}
 638		/* An object might have been moved to a different hash chain,
 639		 * while we walk along it - better check and retry.
 640		 */
 641	} while (he != RHT_NULLS_MARKER(bkt));
 642
 643	/* Ensure we see any new tables. */
 644	smp_rmb();
 645
 646	tbl = rht_dereference_rcu(tbl->future_tbl, ht);
 647	if (unlikely(tbl))
 648		goto restart;
 649
 650	return NULL;
 651}
 652
 653/**
 654 * rhashtable_lookup - search hash table
 655 * @ht:		hash table
 656 * @key:	the pointer to the key
 657 * @params:	hash table parameters
 658 *
 659 * Computes the hash value for the key and traverses the bucket chain looking
 660 * for an entry with an identical key. The first matching entry is returned.
 661 *
 662 * This must only be called under the RCU read lock.
 663 *
 664 * Returns the first entry on which the compare function returned true.
 665 */
 666static __always_inline void *rhashtable_lookup(
 667	struct rhashtable *ht, const void *key,
 668	const struct rhashtable_params params)
 669{
 670	struct rhash_head *he = __rhashtable_lookup(ht, key, params,
 671						    RHT_LOOKUP_NORMAL);
 672
 673	return he ? rht_obj(ht, he) : NULL;
 674}
 675
 676static __always_inline void *rhashtable_lookup_likely(
 677	struct rhashtable *ht, const void *key,
 678	const struct rhashtable_params params)
 679{
 680	struct rhash_head *he = __rhashtable_lookup(ht, key, params,
 681						    RHT_LOOKUP_LIKELY);
 682
 683	return likely(he) ? rht_obj(ht, he) : NULL;
 684}
 685
 686/**
 687 * rhashtable_lookup_fast - search hash table, without RCU read lock
 688 * @ht:		hash table
 689 * @key:	the pointer to the key
 690 * @params:	hash table parameters
 691 *
 692 * Computes the hash value for the key and traverses the bucket chain looking
 693 * for an entry with an identical key. The first matching entry is returned.
 694 *
 695 * Only use this function when you have other mechanisms guaranteeing
 696 * that the object won't go away after the RCU read lock is released.
 697 *
 698 * Returns the first entry on which the compare function returned true.
 699 */
 700static __always_inline void *rhashtable_lookup_fast(
 701	struct rhashtable *ht, const void *key,
 702	const struct rhashtable_params params)
 703{
 704	void *obj;
 705
 706	rcu_read_lock();
 707	obj = rhashtable_lookup(ht, key, params);
 708	rcu_read_unlock();
 709
 710	return obj;
 711}
 712
 713/**
 714 * rhltable_lookup - search hash list table
 715 * @hlt:	hash table
 716 * @key:	the pointer to the key
 717 * @params:	hash table parameters
 718 *
 719 * Computes the hash value for the key and traverses the bucket chain looking
 720 * for an entry with an identical key.  All matching entries are returned
 721 * in a list.
 722 *
 723 * This must only be called under the RCU read lock.
 724 *
 725 * Returns the list of entries that match the given key.
 726 */
 727static __always_inline struct rhlist_head *rhltable_lookup(
 728	struct rhltable *hlt, const void *key,
 729	const struct rhashtable_params params)
 730{
 731	struct rhash_head *he = __rhashtable_lookup(&hlt->ht, key, params,
 732						    RHT_LOOKUP_NORMAL);
 733
 734	return he ? container_of(he, struct rhlist_head, rhead) : NULL;
 735}
 736
 737static __always_inline struct rhlist_head *rhltable_lookup_likely(
 738	struct rhltable *hlt, const void *key,
 739	const struct rhashtable_params params)
 740{
 741	struct rhash_head *he = __rhashtable_lookup(&hlt->ht, key, params,
 742						    RHT_LOOKUP_LIKELY);
 743
 744	return likely(he) ? container_of(he, struct rhlist_head, rhead) : NULL;
 745}
 746
 747/* Internal function, please use rhashtable_insert_fast() instead. This
 748 * function returns the existing element already in hashes if there is a clash,
 749 * otherwise it returns an error via ERR_PTR().
 750 */
 751static __always_inline void *__rhashtable_insert_fast(
 752	struct rhashtable *ht, const void *key, struct rhash_head *obj,
 753	const struct rhashtable_params params, bool rhlist)
 754{
 755	struct rhashtable_compare_arg arg = {
 756		.ht = ht,
 757		.key = key,
 758	};
 759	struct rhash_lock_head __rcu **bkt;
 760	struct rhash_head __rcu **pprev;
 761	struct bucket_table *tbl;
 762	struct rhash_head *head;
 763	unsigned long flags;
 764	unsigned int hash;
 765	int elasticity;
 766	void *data;
 767
 768	rcu_read_lock();
 769
 770	tbl = rht_dereference_rcu(ht->tbl, ht);
 771	hash = rht_head_hashfn(ht, tbl, obj, params);
 772	elasticity = RHT_ELASTICITY;
 773	bkt = rht_bucket_insert(ht, tbl, hash);
 774	data = ERR_PTR(-ENOMEM);
 775	if (!bkt)
 776		goto out;
 777	pprev = NULL;
 778	flags = rht_lock(tbl, bkt);
 779
 780	if (unlikely(rcu_access_pointer(tbl->future_tbl))) {
 781slow_path:
 782		rht_unlock(tbl, bkt, flags);
 783		rcu_read_unlock();
 784		return rhashtable_insert_slow(ht, key, obj);
 785	}
 786
 787	rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {
 788		struct rhlist_head *plist;
 789		struct rhlist_head *list;
 790
 791		elasticity--;
 792		if (!key ||
 793		    (params.obj_cmpfn ?
 794		     params.obj_cmpfn(&arg, rht_obj(ht, head)) :
 795		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
 796			pprev = &head->next;
 797			continue;
 798		}
 799
 800		data = rht_obj(ht, head);
 801
 802		if (!rhlist)
 803			goto out_unlock;
 804
 805
 806		list = container_of(obj, struct rhlist_head, rhead);
 807		plist = container_of(head, struct rhlist_head, rhead);
 808
 809		RCU_INIT_POINTER(list->next, plist);
 810		head = rht_dereference_bucket(head->next, tbl, hash);
 811		RCU_INIT_POINTER(list->rhead.next, head);
 812		if (pprev) {
 813			rcu_assign_pointer(*pprev, obj);
 814			rht_unlock(tbl, bkt, flags);
 815		} else
 816			rht_assign_unlock(tbl, bkt, obj, flags);
 817		data = NULL;
 818		goto out;
 819	}
 820
 821	if (elasticity <= 0)
 822		goto slow_path;
 823
 824	data = ERR_PTR(-E2BIG);
 825	if (unlikely(rht_grow_above_max(ht, tbl)))
 826		goto out_unlock;
 827
 828	if (unlikely(rht_grow_above_100(ht, tbl)))
 829		goto slow_path;
 830
 831	/* Inserting at head of list makes unlocking free. */
 832	head = rht_ptr(bkt, tbl, hash);
 833
 834	RCU_INIT_POINTER(obj->next, head);
 835	if (rhlist) {
 836		struct rhlist_head *list;
 837
 838		list = container_of(obj, struct rhlist_head, rhead);
 839		RCU_INIT_POINTER(list->next, NULL);
 840	}
 841
 842	atomic_inc(&ht->nelems);
 843	rht_assign_unlock(tbl, bkt, obj, flags);
 844
 845	if (rht_grow_above_75(ht, tbl))
 846		schedule_work(&ht->run_work);
 847
 848	data = NULL;
 849out:
 850	rcu_read_unlock();
 851
 852	return data;
 853
 854out_unlock:
 855	rht_unlock(tbl, bkt, flags);
 856	goto out;
 857}
 858
 859/**
 860 * rhashtable_insert_fast - insert object into hash table
 861 * @ht:		hash table
 862 * @obj:	pointer to hash head inside object
 863 * @params:	hash table parameters
 864 *
 865 * Will take the per bucket bitlock to protect against mutual mutations
 866 * on the same bucket. Multiple insertions may occur in parallel unless
 867 * they map to the same bucket.
 868 *
 869 * It is safe to call this function from atomic context.
 870 *
 871 * Will trigger an automatic deferred table resizing if residency in the
 872 * table grows beyond 70%.
 873 */
 874static __always_inline int rhashtable_insert_fast(
 875	struct rhashtable *ht, struct rhash_head *obj,
 876	const struct rhashtable_params params)
 877{
 878	void *ret;
 879
 880	ret = __rhashtable_insert_fast(ht, NULL, obj, params, false);
 881	if (IS_ERR(ret))
 882		return PTR_ERR(ret);
 883
 884	return ret == NULL ? 0 : -EEXIST;
 885}
 886
 887/**
 888 * rhltable_insert_key - insert object into hash list table
 889 * @hlt:	hash list table
 890 * @key:	the pointer to the key
 891 * @list:	pointer to hash list head inside object
 892 * @params:	hash table parameters
 893 *
 894 * Will take the per bucket bitlock to protect against mutual mutations
 895 * on the same bucket. Multiple insertions may occur in parallel unless
 896 * they map to the same bucket.
 897 *
 898 * It is safe to call this function from atomic context.
 899 *
 900 * Will trigger an automatic deferred table resizing if residency in the
 901 * table grows beyond 70%.
 902 */
 903static __always_inline int rhltable_insert_key(
 904	struct rhltable *hlt, const void *key, struct rhlist_head *list,
 905	const struct rhashtable_params params)
 906{
 907	return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
 908						params, true));
 909}
 910
 911/**
 912 * rhltable_insert - insert object into hash list table
 913 * @hlt:	hash list table
 914 * @list:	pointer to hash list head inside object
 915 * @params:	hash table parameters
 916 *
 917 * Will take the per bucket bitlock to protect against mutual mutations
 918 * on the same bucket. Multiple insertions may occur in parallel unless
 919 * they map to the same bucket.
 920 *
 921 * It is safe to call this function from atomic context.
 922 *
 923 * Will trigger an automatic deferred table resizing if residency in the
 924 * table grows beyond 70%.
 925 */
 926static __always_inline int rhltable_insert(
 927	struct rhltable *hlt, struct rhlist_head *list,
 928	const struct rhashtable_params params)
 929{
 930	const char *key = rht_obj(&hlt->ht, &list->rhead);
 931
 932	key += params.key_offset;
 933
 934	return rhltable_insert_key(hlt, key, list, params);
 935}
 936
 937/**
 938 * rhashtable_lookup_insert_fast - lookup and insert object into hash table
 939 * @ht:		hash table
 940 * @obj:	pointer to hash head inside object
 941 * @params:	hash table parameters
 942 *
 943 * This lookup function may only be used for fixed key hash table (key_len
 944 * parameter set). It will BUG() if used inappropriately.
 945 *
 946 * It is safe to call this function from atomic context.
 947 *
 948 * Will trigger an automatic deferred table resizing if residency in the
 949 * table grows beyond 70%.
 950 */
 951static __always_inline int rhashtable_lookup_insert_fast(
 952	struct rhashtable *ht, struct rhash_head *obj,
 953	const struct rhashtable_params params)
 954{
 955	const char *key = rht_obj(ht, obj);
 956	void *ret;
 957
 958	BUG_ON(ht->p.obj_hashfn);
 959
 960	ret = __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
 961				       false);
 962	if (IS_ERR(ret))
 963		return PTR_ERR(ret);
 964
 965	return ret == NULL ? 0 : -EEXIST;
 966}
 967
 968/**
 969 * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
 970 * @ht:		hash table
 971 * @obj:	pointer to hash head inside object
 972 * @params:	hash table parameters
 973 *
 974 * Just like rhashtable_lookup_insert_fast(), but this function returns the
 975 * object if it exists, NULL if it did not and the insertion was successful,
 976 * and an ERR_PTR otherwise.
 977 */
 978static __always_inline void *rhashtable_lookup_get_insert_fast(
 979	struct rhashtable *ht, struct rhash_head *obj,
 980	const struct rhashtable_params params)
 981{
 982	const char *key = rht_obj(ht, obj);
 983
 984	BUG_ON(ht->p.obj_hashfn);
 985
 986	return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
 987					false);
 988}
 989
 990/**
 991 * rhashtable_lookup_insert_key - search and insert object to hash table
 992 *				  with explicit key
 993 * @ht:		hash table
 994 * @key:	key
 995 * @obj:	pointer to hash head inside object
 996 * @params:	hash table parameters
 997 *
 998 * Lookups may occur in parallel with hashtable mutations and resizing.
 999 *
1000 * Will trigger an automatic deferred table resizing if residency in the
1001 * table grows beyond 70%.
1002 *
1003 * Returns zero on success.
1004 */
1005static __always_inline int rhashtable_lookup_insert_key(
1006	struct rhashtable *ht, const void *key, struct rhash_head *obj,
1007	const struct rhashtable_params params)
1008{
1009	void *ret;
1010
1011	BUG_ON(!ht->p.obj_hashfn || !key);
1012
1013	ret = __rhashtable_insert_fast(ht, key, obj, params, false);
1014	if (IS_ERR(ret))
1015		return PTR_ERR(ret);
1016
1017	return ret == NULL ? 0 : -EEXIST;
1018}
1019
1020/**
1021 * rhashtable_lookup_get_insert_key - lookup and insert object into hash table
1022 * @ht:		hash table
1023 * @key:	key
1024 * @obj:	pointer to hash head inside object
1025 * @params:	hash table parameters
1026 *
1027 * Just like rhashtable_lookup_insert_key(), but this function returns the
1028 * object if it exists, NULL if it does not and the insertion was successful,
1029 * and an ERR_PTR otherwise.
1030 */
1031static __always_inline void *rhashtable_lookup_get_insert_key(
1032	struct rhashtable *ht, const void *key, struct rhash_head *obj,
1033	const struct rhashtable_params params)
1034{
1035	BUG_ON(!ht->p.obj_hashfn || !key);
1036
1037	return __rhashtable_insert_fast(ht, key, obj, params, false);
1038}
1039
1040/* Internal function, please use rhashtable_remove_fast() instead */
1041static __always_inline int __rhashtable_remove_fast_one(
1042	struct rhashtable *ht, struct bucket_table *tbl,
1043	struct rhash_head *obj, const struct rhashtable_params params,
1044	bool rhlist)
1045{
1046	struct rhash_lock_head __rcu **bkt;
1047	struct rhash_head __rcu **pprev;
1048	struct rhash_head *he;
1049	unsigned long flags;
1050	unsigned int hash;
1051	int err = -ENOENT;
1052
1053	hash = rht_head_hashfn(ht, tbl, obj, params);
1054	bkt = rht_bucket_var(tbl, hash);
1055	if (!bkt)
1056		return -ENOENT;
1057	pprev = NULL;
1058	flags = rht_lock(tbl, bkt);
1059
1060	rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
1061		struct rhlist_head *list;
1062
1063		list = container_of(he, struct rhlist_head, rhead);
1064
1065		if (he != obj) {
1066			struct rhlist_head __rcu **lpprev;
1067
1068			pprev = &he->next;
1069
1070			if (!rhlist)
1071				continue;
1072
1073			do {
1074				lpprev = &list->next;
1075				list = rht_dereference_bucket(list->next,
1076							      tbl, hash);
1077			} while (list && obj != &list->rhead);
1078
1079			if (!list)
1080				continue;
1081
1082			list = rht_dereference_bucket(list->next, tbl, hash);
1083			RCU_INIT_POINTER(*lpprev, list);
1084			err = 0;
1085			break;
1086		}
1087
1088		obj = rht_dereference_bucket(obj->next, tbl, hash);
1089		err = 1;
1090
1091		if (rhlist) {
1092			list = rht_dereference_bucket(list->next, tbl, hash);
1093			if (list) {
1094				RCU_INIT_POINTER(list->rhead.next, obj);
1095				obj = &list->rhead;
1096				err = 0;
1097			}
1098		}
1099
1100		if (pprev) {
1101			rcu_assign_pointer(*pprev, obj);
1102			rht_unlock(tbl, bkt, flags);
1103		} else {
1104			rht_assign_unlock(tbl, bkt, obj, flags);
1105		}
1106		goto unlocked;
1107	}
1108
1109	rht_unlock(tbl, bkt, flags);
1110unlocked:
1111	if (err > 0) {
1112		atomic_dec(&ht->nelems);
1113		if (unlikely(ht->p.automatic_shrinking &&
1114			     rht_shrink_below_30(ht, tbl)))
1115			schedule_work(&ht->run_work);
1116		err = 0;
1117	}
1118
1119	return err;
1120}
1121
1122/* Internal function, please use rhashtable_remove_fast() instead */
1123static __always_inline int __rhashtable_remove_fast(
1124	struct rhashtable *ht, struct rhash_head *obj,
1125	const struct rhashtable_params params, bool rhlist)
1126{
1127	struct bucket_table *tbl;
1128	int err;
1129
1130	rcu_read_lock();
1131
1132	tbl = rht_dereference_rcu(ht->tbl, ht);
1133
1134	/* Because we have already taken (and released) the bucket
1135	 * lock in old_tbl, if we find that future_tbl is not yet
1136	 * visible then that guarantees the entry to still be in
1137	 * the old tbl if it exists.
1138	 */
1139	while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params,
1140						   rhlist)) &&
1141	       (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1142		;
1143
1144	rcu_read_unlock();
1145
1146	return err;
1147}
1148
1149/**
1150 * rhashtable_remove_fast - remove object from hash table
1151 * @ht:		hash table
1152 * @obj:	pointer to hash head inside object
1153 * @params:	hash table parameters
1154 *
1155 * Since the hash chain is single linked, the removal operation needs to
1156 * walk the bucket chain upon removal. The removal operation is thus
1157 * considerable slow if the hash table is not correctly sized.
1158 *
1159 * Will automatically shrink the table if permitted when residency drops
1160 * below 30%.
1161 *
1162 * Returns zero on success, -ENOENT if the entry could not be found.
1163 */
1164static __always_inline int rhashtable_remove_fast(
1165	struct rhashtable *ht, struct rhash_head *obj,
1166	const struct rhashtable_params params)
1167{
1168	return __rhashtable_remove_fast(ht, obj, params, false);
1169}
1170
1171/**
1172 * rhltable_remove - remove object from hash list table
1173 * @hlt:	hash list table
1174 * @list:	pointer to hash list head inside object
1175 * @params:	hash table parameters
1176 *
1177 * Since the hash chain is single linked, the removal operation needs to
1178 * walk the bucket chain upon removal. The removal operation is thus
1179 * considerably slower if the hash table is not correctly sized.
1180 *
1181 * Will automatically shrink the table if permitted when residency drops
1182 * below 30%
1183 *
1184 * Returns zero on success, -ENOENT if the entry could not be found.
1185 */
1186static __always_inline int rhltable_remove(
1187	struct rhltable *hlt, struct rhlist_head *list,
1188	const struct rhashtable_params params)
1189{
1190	return __rhashtable_remove_fast(&hlt->ht, &list->rhead, params, true);
1191}
1192
1193/* Internal function, please use rhashtable_replace_fast() instead */
1194static __always_inline int __rhashtable_replace_fast(
1195	struct rhashtable *ht, struct bucket_table *tbl,
1196	struct rhash_head *obj_old, struct rhash_head *obj_new,
1197	const struct rhashtable_params params)
1198{
1199	struct rhash_lock_head __rcu **bkt;
1200	struct rhash_head __rcu **pprev;
1201	struct rhash_head *he;
1202	unsigned long flags;
1203	unsigned int hash;
1204	int err = -ENOENT;
1205
1206	/* Minimally, the old and new objects must have same hash
1207	 * (which should mean identifiers are the same).
1208	 */
1209	hash = rht_head_hashfn(ht, tbl, obj_old, params);
1210	if (hash != rht_head_hashfn(ht, tbl, obj_new, params))
1211		return -EINVAL;
1212
1213	bkt = rht_bucket_var(tbl, hash);
1214	if (!bkt)
1215		return -ENOENT;
1216
1217	pprev = NULL;
1218	flags = rht_lock(tbl, bkt);
1219
1220	rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
1221		if (he != obj_old) {
1222			pprev = &he->next;
1223			continue;
1224		}
1225
1226		rcu_assign_pointer(obj_new->next, obj_old->next);
1227		if (pprev) {
1228			rcu_assign_pointer(*pprev, obj_new);
1229			rht_unlock(tbl, bkt, flags);
1230		} else {
1231			rht_assign_unlock(tbl, bkt, obj_new, flags);
1232		}
1233		err = 0;
1234		goto unlocked;
1235	}
1236
1237	rht_unlock(tbl, bkt, flags);
1238
1239unlocked:
1240	return err;
1241}
1242
1243/**
1244 * rhashtable_replace_fast - replace an object in hash table
1245 * @ht:		hash table
1246 * @obj_old:	pointer to hash head inside object being replaced
1247 * @obj_new:	pointer to hash head inside object which is new
1248 * @params:	hash table parameters
1249 *
1250 * Replacing an object doesn't affect the number of elements in the hash table
1251 * or bucket, so we don't need to worry about shrinking or expanding the
1252 * table here.
1253 *
1254 * Returns zero on success, -ENOENT if the entry could not be found,
1255 * -EINVAL if hash is not the same for the old and new objects.
1256 */
1257static __always_inline int rhashtable_replace_fast(
1258	struct rhashtable *ht, struct rhash_head *obj_old,
1259	struct rhash_head *obj_new,
1260	const struct rhashtable_params params)
1261{
1262	struct bucket_table *tbl;
1263	int err;
1264
1265	rcu_read_lock();
1266
1267	tbl = rht_dereference_rcu(ht->tbl, ht);
1268
1269	/* Because we have already taken (and released) the bucket
1270	 * lock in old_tbl, if we find that future_tbl is not yet
1271	 * visible then that guarantees the entry to still be in
1272	 * the old tbl if it exists.
1273	 */
1274	while ((err = __rhashtable_replace_fast(ht, tbl, obj_old,
1275						obj_new, params)) &&
1276	       (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1277		;
1278
1279	rcu_read_unlock();
1280
1281	return err;
1282}
1283
1284/**
1285 * rhltable_walk_enter - Initialise an iterator
1286 * @hlt:	Table to walk over
1287 * @iter:	Hash table Iterator
1288 *
1289 * This function prepares a hash table walk.
1290 *
1291 * Note that if you restart a walk after rhashtable_walk_stop you
1292 * may see the same object twice.  Also, you may miss objects if
1293 * there are removals in between rhashtable_walk_stop and the next
1294 * call to rhashtable_walk_start.
1295 *
1296 * For a completely stable walk you should construct your own data
1297 * structure outside the hash table.
1298 *
1299 * This function may be called from any process context, including
1300 * non-preemptable context, but cannot be called from softirq or
1301 * hardirq context.
1302 *
1303 * You must call rhashtable_walk_exit after this function returns.
1304 */
1305static inline void rhltable_walk_enter(struct rhltable *hlt,
1306				       struct rhashtable_iter *iter)
1307{
1308	rhashtable_walk_enter(&hlt->ht, iter);
1309}
1310
1311/**
1312 * rhltable_free_and_destroy - free elements and destroy hash list table
1313 * @hlt:	the hash list table to destroy
1314 * @free_fn:	callback to release resources of element
1315 * @arg:	pointer passed to free_fn
1316 *
1317 * See documentation for rhashtable_free_and_destroy.
1318 */
1319static inline void rhltable_free_and_destroy(struct rhltable *hlt,
1320					     void (*free_fn)(void *ptr,
1321							     void *arg),
1322					     void *arg)
1323{
1324	rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);
1325}
1326
1327static inline void rhltable_destroy(struct rhltable *hlt)
1328{
1329	rhltable_free_and_destroy(hlt, NULL, NULL);
1330}
1331
1332#endif /* _LINUX_RHASHTABLE_H */