rhashtable.h 38 KB

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