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 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 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 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_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_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 358static inline struct rhash_head *__rht_ptr( 359 struct rhash_lock_head *p, struct rhash_lock_head __rcu *const *bkt) 360{ 361 return (struct rhash_head *) 362 ((unsigned long)p & ~BIT(0) ?: 363 (unsigned long)RHT_NULLS_MARKER(bkt)); 364} 365 366/* 367 * Where 'bkt' is a bucket and might be locked: 368 * rht_ptr_rcu() dereferences that pointer and clears the lock bit. 369 * rht_ptr() dereferences in a context where the bucket is locked. 370 * rht_ptr_exclusive() dereferences in a context where exclusive 371 * access is guaranteed, such as when destroying the table. 372 */ 373static inline struct rhash_head *rht_ptr_rcu( 374 struct rhash_lock_head __rcu *const *bkt) 375{ 376 return __rht_ptr(rcu_dereference(*bkt), bkt); 377} 378 379static inline struct rhash_head *rht_ptr( 380 struct rhash_lock_head __rcu *const *bkt, 381 struct bucket_table *tbl, 382 unsigned int hash) 383{ 384 return __rht_ptr(rht_dereference_bucket(*bkt, tbl, hash), bkt); 385} 386 387static inline struct rhash_head *rht_ptr_exclusive( 388 struct rhash_lock_head __rcu *const *bkt) 389{ 390 return __rht_ptr(rcu_dereference_protected(*bkt, 1), bkt); 391} 392 393static inline void rht_assign_locked(struct rhash_lock_head __rcu **bkt, 394 struct rhash_head *obj) 395{ 396 if (rht_is_a_nulls(obj)) 397 obj = NULL; 398 rcu_assign_pointer(*bkt, (void *)((unsigned long)obj | BIT(0))); 399} 400 401static inline void rht_assign_unlock(struct bucket_table *tbl, 402 struct rhash_lock_head __rcu **bkt, 403 struct rhash_head *obj, 404 unsigned long flags) 405{ 406 if (rht_is_a_nulls(obj)) 407 obj = NULL; 408 lock_map_release(&tbl->dep_map); 409 rcu_assign_pointer(*bkt, (void *)obj); 410 preempt_enable(); 411 __release(bitlock); 412 local_irq_restore(flags); 413} 414 415/** 416 * rht_for_each_from - iterate over hash chain from given head 417 * @pos: the &struct rhash_head to use as a loop cursor. 418 * @head: the &struct rhash_head to start from 419 * @tbl: the &struct bucket_table 420 * @hash: the hash value / bucket index 421 */ 422#define rht_for_each_from(pos, head, tbl, hash) \ 423 for (pos = head; \ 424 !rht_is_a_nulls(pos); \ 425 pos = rht_dereference_bucket((pos)->next, tbl, hash)) 426 427/** 428 * rht_for_each - iterate over hash chain 429 * @pos: the &struct rhash_head to use as a loop cursor. 430 * @tbl: the &struct bucket_table 431 * @hash: the hash value / bucket index 432 */ 433#define rht_for_each(pos, tbl, hash) \ 434 rht_for_each_from(pos, rht_ptr(rht_bucket(tbl, hash), tbl, hash), \ 435 tbl, hash) 436 437/** 438 * rht_for_each_entry_from - iterate over hash chain from given head 439 * @tpos: the type * to use as a loop cursor. 440 * @pos: the &struct rhash_head to use as a loop cursor. 441 * @head: the &struct rhash_head to start from 442 * @tbl: the &struct bucket_table 443 * @hash: the hash value / bucket index 444 * @member: name of the &struct rhash_head within the hashable struct. 445 */ 446#define rht_for_each_entry_from(tpos, pos, head, tbl, hash, member) \ 447 for (pos = head; \ 448 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \ 449 pos = rht_dereference_bucket((pos)->next, tbl, hash)) 450 451/** 452 * rht_for_each_entry - iterate over hash chain of given type 453 * @tpos: the type * to use as a loop cursor. 454 * @pos: the &struct rhash_head to use as a loop cursor. 455 * @tbl: the &struct bucket_table 456 * @hash: the hash value / bucket index 457 * @member: name of the &struct rhash_head within the hashable struct. 458 */ 459#define rht_for_each_entry(tpos, pos, tbl, hash, member) \ 460 rht_for_each_entry_from(tpos, pos, \ 461 rht_ptr(rht_bucket(tbl, hash), tbl, hash), \ 462 tbl, hash, member) 463 464/** 465 * rht_for_each_entry_safe - safely iterate over hash chain of given type 466 * @tpos: the type * to use as a loop cursor. 467 * @pos: the &struct rhash_head to use as a loop cursor. 468 * @next: the &struct rhash_head to use as next in loop cursor. 469 * @tbl: the &struct bucket_table 470 * @hash: the hash value / bucket index 471 * @member: name of the &struct rhash_head within the hashable struct. 472 * 473 * This hash chain list-traversal primitive allows for the looped code to 474 * remove the loop cursor from the list. 475 */ 476#define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member) \ 477 for (pos = rht_ptr(rht_bucket(tbl, hash), tbl, hash), \ 478 next = !rht_is_a_nulls(pos) ? \ 479 rht_dereference_bucket(pos->next, tbl, hash) : NULL; \ 480 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \ 481 pos = next, \ 482 next = !rht_is_a_nulls(pos) ? \ 483 rht_dereference_bucket(pos->next, tbl, hash) : NULL) 484 485/** 486 * rht_for_each_rcu_from - iterate over rcu hash chain from given head 487 * @pos: the &struct rhash_head to use as a loop cursor. 488 * @head: the &struct rhash_head to start from 489 * @tbl: the &struct bucket_table 490 * @hash: the hash value / bucket index 491 * 492 * This hash chain list-traversal primitive may safely run concurrently with 493 * the _rcu mutation primitives such as rhashtable_insert() as long as the 494 * traversal is guarded by rcu_read_lock(). 495 */ 496#define rht_for_each_rcu_from(pos, head, tbl, hash) \ 497 for (({barrier(); }), \ 498 pos = head; \ 499 !rht_is_a_nulls(pos); \ 500 pos = rcu_dereference_raw(pos->next)) 501 502/** 503 * rht_for_each_rcu - iterate over rcu hash chain 504 * @pos: the &struct rhash_head to use as a loop cursor. 505 * @tbl: the &struct bucket_table 506 * @hash: the hash value / bucket index 507 * 508 * This hash chain list-traversal primitive may safely run concurrently with 509 * the _rcu mutation primitives such as rhashtable_insert() as long as the 510 * traversal is guarded by rcu_read_lock(). 511 */ 512#define rht_for_each_rcu(pos, tbl, hash) \ 513 for (({barrier(); }), \ 514 pos = rht_ptr_rcu(rht_bucket(tbl, hash)); \ 515 !rht_is_a_nulls(pos); \ 516 pos = rcu_dereference_raw(pos->next)) 517 518/** 519 * rht_for_each_entry_rcu_from - iterated over rcu hash chain from given head 520 * @tpos: the type * to use as a loop cursor. 521 * @pos: the &struct rhash_head to use as a loop cursor. 522 * @head: the &struct rhash_head to start from 523 * @tbl: the &struct bucket_table 524 * @hash: the hash value / bucket index 525 * @member: name of the &struct rhash_head within the hashable struct. 526 * 527 * This hash chain list-traversal primitive may safely run concurrently with 528 * the _rcu mutation primitives such as rhashtable_insert() as long as the 529 * traversal is guarded by rcu_read_lock(). 530 */ 531#define rht_for_each_entry_rcu_from(tpos, pos, head, tbl, hash, member) \ 532 for (({barrier(); }), \ 533 pos = head; \ 534 (!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \ 535 pos = rht_dereference_bucket_rcu(pos->next, tbl, hash)) 536 537/** 538 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type 539 * @tpos: the type * to use as a loop cursor. 540 * @pos: the &struct rhash_head to use as a loop cursor. 541 * @tbl: the &struct bucket_table 542 * @hash: the hash value / bucket index 543 * @member: name of the &struct rhash_head within the hashable struct. 544 * 545 * This hash chain list-traversal primitive may safely run concurrently with 546 * the _rcu mutation primitives such as rhashtable_insert() as long as the 547 * traversal is guarded by rcu_read_lock(). 548 */ 549#define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \ 550 rht_for_each_entry_rcu_from(tpos, pos, \ 551 rht_ptr_rcu(rht_bucket(tbl, hash)), \ 552 tbl, hash, member) 553 554/** 555 * rhl_for_each_rcu - iterate over rcu hash table list 556 * @pos: the &struct rlist_head to use as a loop cursor. 557 * @list: the head of the list 558 * 559 * This hash chain list-traversal primitive should be used on the 560 * list returned by rhltable_lookup. 561 */ 562#define rhl_for_each_rcu(pos, list) \ 563 for (pos = list; pos; pos = rcu_dereference_raw(pos->next)) 564 565/** 566 * rhl_for_each_entry_rcu - iterate over rcu hash table list of given type 567 * @tpos: the type * to use as a loop cursor. 568 * @pos: the &struct rlist_head to use as a loop cursor. 569 * @list: the head of the list 570 * @member: name of the &struct rlist_head within the hashable struct. 571 * 572 * This hash chain list-traversal primitive should be used on the 573 * list returned by rhltable_lookup. 574 */ 575#define rhl_for_each_entry_rcu(tpos, pos, list, member) \ 576 for (pos = list; pos && rht_entry(tpos, pos, member); \ 577 pos = rcu_dereference_raw(pos->next)) 578 579static inline int rhashtable_compare(struct rhashtable_compare_arg *arg, 580 const void *obj) 581{ 582 struct rhashtable *ht = arg->ht; 583 const char *ptr = obj; 584 585 return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len); 586} 587 588/* Internal function, do not use. */ 589static inline struct rhash_head *__rhashtable_lookup( 590 struct rhashtable *ht, const void *key, 591 const struct rhashtable_params params) 592{ 593 struct rhashtable_compare_arg arg = { 594 .ht = ht, 595 .key = key, 596 }; 597 struct rhash_lock_head __rcu *const *bkt; 598 struct bucket_table *tbl; 599 struct rhash_head *he; 600 unsigned int hash; 601 602 tbl = rht_dereference_rcu(ht->tbl, ht); 603restart: 604 hash = rht_key_hashfn(ht, tbl, key, params); 605 bkt = rht_bucket(tbl, hash); 606 do { 607 rht_for_each_rcu_from(he, rht_ptr_rcu(bkt), tbl, hash) { 608 if (params.obj_cmpfn ? 609 params.obj_cmpfn(&arg, rht_obj(ht, he)) : 610 rhashtable_compare(&arg, rht_obj(ht, he))) 611 continue; 612 return he; 613 } 614 /* An object might have been moved to a different hash chain, 615 * while we walk along it - better check and retry. 616 */ 617 } while (he != RHT_NULLS_MARKER(bkt)); 618 619 /* Ensure we see any new tables. */ 620 smp_rmb(); 621 622 tbl = rht_dereference_rcu(tbl->future_tbl, ht); 623 if (unlikely(tbl)) 624 goto restart; 625 626 return NULL; 627} 628 629/** 630 * rhashtable_lookup - search hash table 631 * @ht: hash table 632 * @key: the pointer to the key 633 * @params: hash table parameters 634 * 635 * Computes the hash value for the key and traverses the bucket chain looking 636 * for a entry with an identical key. The first matching entry is returned. 637 * 638 * This must only be called under the RCU read lock. 639 * 640 * Returns the first entry on which the compare function returned true. 641 */ 642static inline void *rhashtable_lookup( 643 struct rhashtable *ht, const void *key, 644 const struct rhashtable_params params) 645{ 646 struct rhash_head *he = __rhashtable_lookup(ht, key, params); 647 648 return he ? rht_obj(ht, he) : NULL; 649} 650 651/** 652 * rhashtable_lookup_fast - search hash table, without RCU read lock 653 * @ht: hash table 654 * @key: the pointer to the key 655 * @params: hash table parameters 656 * 657 * Computes the hash value for the key and traverses the bucket chain looking 658 * for a entry with an identical key. The first matching entry is returned. 659 * 660 * Only use this function when you have other mechanisms guaranteeing 661 * that the object won't go away after the RCU read lock is released. 662 * 663 * Returns the first entry on which the compare function returned true. 664 */ 665static inline void *rhashtable_lookup_fast( 666 struct rhashtable *ht, const void *key, 667 const struct rhashtable_params params) 668{ 669 void *obj; 670 671 rcu_read_lock(); 672 obj = rhashtable_lookup(ht, key, params); 673 rcu_read_unlock(); 674 675 return obj; 676} 677 678/** 679 * rhltable_lookup - search hash list table 680 * @hlt: hash table 681 * @key: the pointer to the key 682 * @params: hash table parameters 683 * 684 * Computes the hash value for the key and traverses the bucket chain looking 685 * for a entry with an identical key. All matching entries are returned 686 * in a list. 687 * 688 * This must only be called under the RCU read lock. 689 * 690 * Returns the list of entries that match the given key. 691 */ 692static inline struct rhlist_head *rhltable_lookup( 693 struct rhltable *hlt, const void *key, 694 const struct rhashtable_params params) 695{ 696 struct rhash_head *he = __rhashtable_lookup(&hlt->ht, key, params); 697 698 return he ? container_of(he, struct rhlist_head, rhead) : NULL; 699} 700 701/* Internal function, please use rhashtable_insert_fast() instead. This 702 * function returns the existing element already in hashes in there is a clash, 703 * otherwise it returns an error via ERR_PTR(). 704 */ 705static inline void *__rhashtable_insert_fast( 706 struct rhashtable *ht, const void *key, struct rhash_head *obj, 707 const struct rhashtable_params params, bool rhlist) 708{ 709 struct rhashtable_compare_arg arg = { 710 .ht = ht, 711 .key = key, 712 }; 713 struct rhash_lock_head __rcu **bkt; 714 struct rhash_head __rcu **pprev; 715 struct bucket_table *tbl; 716 struct rhash_head *head; 717 unsigned long flags; 718 unsigned int hash; 719 int elasticity; 720 void *data; 721 722 rcu_read_lock(); 723 724 tbl = rht_dereference_rcu(ht->tbl, ht); 725 hash = rht_head_hashfn(ht, tbl, obj, params); 726 elasticity = RHT_ELASTICITY; 727 bkt = rht_bucket_insert(ht, tbl, hash); 728 data = ERR_PTR(-ENOMEM); 729 if (!bkt) 730 goto out; 731 pprev = NULL; 732 flags = rht_lock(tbl, bkt); 733 734 if (unlikely(rcu_access_pointer(tbl->future_tbl))) { 735slow_path: 736 rht_unlock(tbl, bkt, flags); 737 rcu_read_unlock(); 738 return rhashtable_insert_slow(ht, key, obj); 739 } 740 741 rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) { 742 struct rhlist_head *plist; 743 struct rhlist_head *list; 744 745 elasticity--; 746 if (!key || 747 (params.obj_cmpfn ? 748 params.obj_cmpfn(&arg, rht_obj(ht, head)) : 749 rhashtable_compare(&arg, rht_obj(ht, head)))) { 750 pprev = &head->next; 751 continue; 752 } 753 754 data = rht_obj(ht, head); 755 756 if (!rhlist) 757 goto out_unlock; 758 759 760 list = container_of(obj, struct rhlist_head, rhead); 761 plist = container_of(head, struct rhlist_head, rhead); 762 763 RCU_INIT_POINTER(list->next, plist); 764 head = rht_dereference_bucket(head->next, tbl, hash); 765 RCU_INIT_POINTER(list->rhead.next, head); 766 if (pprev) { 767 rcu_assign_pointer(*pprev, obj); 768 rht_unlock(tbl, bkt, flags); 769 } else 770 rht_assign_unlock(tbl, bkt, obj, flags); 771 data = NULL; 772 goto out; 773 } 774 775 if (elasticity <= 0) 776 goto slow_path; 777 778 data = ERR_PTR(-E2BIG); 779 if (unlikely(rht_grow_above_max(ht, tbl))) 780 goto out_unlock; 781 782 if (unlikely(rht_grow_above_100(ht, tbl))) 783 goto slow_path; 784 785 /* Inserting at head of list makes unlocking free. */ 786 head = rht_ptr(bkt, tbl, hash); 787 788 RCU_INIT_POINTER(obj->next, head); 789 if (rhlist) { 790 struct rhlist_head *list; 791 792 list = container_of(obj, struct rhlist_head, rhead); 793 RCU_INIT_POINTER(list->next, NULL); 794 } 795 796 atomic_inc(&ht->nelems); 797 rht_assign_unlock(tbl, bkt, obj, flags); 798 799 if (rht_grow_above_75(ht, tbl)) 800 schedule_work(&ht->run_work); 801 802 data = NULL; 803out: 804 rcu_read_unlock(); 805 806 return data; 807 808out_unlock: 809 rht_unlock(tbl, bkt, flags); 810 goto out; 811} 812 813/** 814 * rhashtable_insert_fast - insert object into hash table 815 * @ht: hash table 816 * @obj: pointer to hash head inside object 817 * @params: hash table parameters 818 * 819 * Will take the per bucket bitlock to protect against mutual mutations 820 * on the same bucket. Multiple insertions may occur in parallel unless 821 * they map to the same bucket. 822 * 823 * It is safe to call this function from atomic context. 824 * 825 * Will trigger an automatic deferred table resizing if residency in the 826 * table grows beyond 70%. 827 */ 828static inline int rhashtable_insert_fast( 829 struct rhashtable *ht, struct rhash_head *obj, 830 const struct rhashtable_params params) 831{ 832 void *ret; 833 834 ret = __rhashtable_insert_fast(ht, NULL, obj, params, false); 835 if (IS_ERR(ret)) 836 return PTR_ERR(ret); 837 838 return ret == NULL ? 0 : -EEXIST; 839} 840 841/** 842 * rhltable_insert_key - insert object into hash list table 843 * @hlt: hash list table 844 * @key: the pointer to the key 845 * @list: pointer to hash list head inside object 846 * @params: hash table parameters 847 * 848 * Will take the per bucket bitlock to protect against mutual mutations 849 * on the same bucket. Multiple insertions may occur in parallel unless 850 * they map to the same bucket. 851 * 852 * It is safe to call this function from atomic context. 853 * 854 * Will trigger an automatic deferred table resizing if residency in the 855 * table grows beyond 70%. 856 */ 857static inline int rhltable_insert_key( 858 struct rhltable *hlt, const void *key, struct rhlist_head *list, 859 const struct rhashtable_params params) 860{ 861 return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead, 862 params, true)); 863} 864 865/** 866 * rhltable_insert - insert object into hash list table 867 * @hlt: hash list table 868 * @list: pointer to hash list head inside object 869 * @params: hash table parameters 870 * 871 * Will take the per bucket bitlock to protect against mutual mutations 872 * on the same bucket. Multiple insertions may occur in parallel unless 873 * they map to the same bucket. 874 * 875 * It is safe to call this function from atomic context. 876 * 877 * Will trigger an automatic deferred table resizing if residency in the 878 * table grows beyond 70%. 879 */ 880static inline int rhltable_insert( 881 struct rhltable *hlt, struct rhlist_head *list, 882 const struct rhashtable_params params) 883{ 884 const char *key = rht_obj(&hlt->ht, &list->rhead); 885 886 key += params.key_offset; 887 888 return rhltable_insert_key(hlt, key, list, params); 889} 890 891/** 892 * rhashtable_lookup_insert_fast - lookup and insert object into hash table 893 * @ht: hash table 894 * @obj: pointer to hash head inside object 895 * @params: hash table parameters 896 * 897 * This lookup function may only be used for fixed key hash table (key_len 898 * parameter set). It will BUG() if used inappropriately. 899 * 900 * It is safe to call this function from atomic context. 901 * 902 * Will trigger an automatic deferred table resizing if residency in the 903 * table grows beyond 70%. 904 */ 905static inline int rhashtable_lookup_insert_fast( 906 struct rhashtable *ht, struct rhash_head *obj, 907 const struct rhashtable_params params) 908{ 909 const char *key = rht_obj(ht, obj); 910 void *ret; 911 912 BUG_ON(ht->p.obj_hashfn); 913 914 ret = __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params, 915 false); 916 if (IS_ERR(ret)) 917 return PTR_ERR(ret); 918 919 return ret == NULL ? 0 : -EEXIST; 920} 921 922/** 923 * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table 924 * @ht: hash table 925 * @obj: pointer to hash head inside object 926 * @params: hash table parameters 927 * 928 * Just like rhashtable_lookup_insert_fast(), but this function returns the 929 * object if it exists, NULL if it did not and the insertion was successful, 930 * and an ERR_PTR otherwise. 931 */ 932static inline void *rhashtable_lookup_get_insert_fast( 933 struct rhashtable *ht, struct rhash_head *obj, 934 const struct rhashtable_params params) 935{ 936 const char *key = rht_obj(ht, obj); 937 938 BUG_ON(ht->p.obj_hashfn); 939 940 return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params, 941 false); 942} 943 944/** 945 * rhashtable_lookup_insert_key - search and insert object to hash table 946 * with explicit key 947 * @ht: hash table 948 * @key: key 949 * @obj: pointer to hash head inside object 950 * @params: hash table parameters 951 * 952 * Lookups may occur in parallel with hashtable mutations and resizing. 953 * 954 * Will trigger an automatic deferred table resizing if residency in the 955 * table grows beyond 70%. 956 * 957 * Returns zero on success. 958 */ 959static inline int rhashtable_lookup_insert_key( 960 struct rhashtable *ht, const void *key, struct rhash_head *obj, 961 const struct rhashtable_params params) 962{ 963 void *ret; 964 965 BUG_ON(!ht->p.obj_hashfn || !key); 966 967 ret = __rhashtable_insert_fast(ht, key, obj, params, false); 968 if (IS_ERR(ret)) 969 return PTR_ERR(ret); 970 971 return ret == NULL ? 0 : -EEXIST; 972} 973 974/** 975 * rhashtable_lookup_get_insert_key - lookup and insert object into hash table 976 * @ht: hash table 977 * @key: key 978 * @obj: pointer to hash head inside object 979 * @params: hash table parameters 980 * 981 * Just like rhashtable_lookup_insert_key(), but this function returns the 982 * object if it exists, NULL if it does not and the insertion was successful, 983 * and an ERR_PTR otherwise. 984 */ 985static inline void *rhashtable_lookup_get_insert_key( 986 struct rhashtable *ht, const void *key, struct rhash_head *obj, 987 const struct rhashtable_params params) 988{ 989 BUG_ON(!ht->p.obj_hashfn || !key); 990 991 return __rhashtable_insert_fast(ht, key, obj, params, false); 992} 993 994/* Internal function, please use rhashtable_remove_fast() instead */ 995static inline int __rhashtable_remove_fast_one( 996 struct rhashtable *ht, struct bucket_table *tbl, 997 struct rhash_head *obj, const struct rhashtable_params params, 998 bool rhlist) 999{ 1000 struct rhash_lock_head __rcu **bkt; 1001 struct rhash_head __rcu **pprev; 1002 struct rhash_head *he; 1003 unsigned long flags; 1004 unsigned int hash; 1005 int err = -ENOENT; 1006 1007 hash = rht_head_hashfn(ht, tbl, obj, params); 1008 bkt = rht_bucket_var(tbl, hash); 1009 if (!bkt) 1010 return -ENOENT; 1011 pprev = NULL; 1012 flags = rht_lock(tbl, bkt); 1013 1014 rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) { 1015 struct rhlist_head *list; 1016 1017 list = container_of(he, struct rhlist_head, rhead); 1018 1019 if (he != obj) { 1020 struct rhlist_head __rcu **lpprev; 1021 1022 pprev = &he->next; 1023 1024 if (!rhlist) 1025 continue; 1026 1027 do { 1028 lpprev = &list->next; 1029 list = rht_dereference_bucket(list->next, 1030 tbl, hash); 1031 } while (list && obj != &list->rhead); 1032 1033 if (!list) 1034 continue; 1035 1036 list = rht_dereference_bucket(list->next, tbl, hash); 1037 RCU_INIT_POINTER(*lpprev, list); 1038 err = 0; 1039 break; 1040 } 1041 1042 obj = rht_dereference_bucket(obj->next, tbl, hash); 1043 err = 1; 1044 1045 if (rhlist) { 1046 list = rht_dereference_bucket(list->next, tbl, hash); 1047 if (list) { 1048 RCU_INIT_POINTER(list->rhead.next, obj); 1049 obj = &list->rhead; 1050 err = 0; 1051 } 1052 } 1053 1054 if (pprev) { 1055 rcu_assign_pointer(*pprev, obj); 1056 rht_unlock(tbl, bkt, flags); 1057 } else { 1058 rht_assign_unlock(tbl, bkt, obj, flags); 1059 } 1060 goto unlocked; 1061 } 1062 1063 rht_unlock(tbl, bkt, flags); 1064unlocked: 1065 if (err > 0) { 1066 atomic_dec(&ht->nelems); 1067 if (unlikely(ht->p.automatic_shrinking && 1068 rht_shrink_below_30(ht, tbl))) 1069 schedule_work(&ht->run_work); 1070 err = 0; 1071 } 1072 1073 return err; 1074} 1075 1076/* Internal function, please use rhashtable_remove_fast() instead */ 1077static inline int __rhashtable_remove_fast( 1078 struct rhashtable *ht, struct rhash_head *obj, 1079 const struct rhashtable_params params, bool rhlist) 1080{ 1081 struct bucket_table *tbl; 1082 int err; 1083 1084 rcu_read_lock(); 1085 1086 tbl = rht_dereference_rcu(ht->tbl, ht); 1087 1088 /* Because we have already taken (and released) the bucket 1089 * lock in old_tbl, if we find that future_tbl is not yet 1090 * visible then that guarantees the entry to still be in 1091 * the old tbl if it exists. 1092 */ 1093 while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params, 1094 rhlist)) && 1095 (tbl = rht_dereference_rcu(tbl->future_tbl, ht))) 1096 ; 1097 1098 rcu_read_unlock(); 1099 1100 return err; 1101} 1102 1103/** 1104 * rhashtable_remove_fast - remove object from hash table 1105 * @ht: hash table 1106 * @obj: pointer to hash head inside object 1107 * @params: hash table parameters 1108 * 1109 * Since the hash chain is single linked, the removal operation needs to 1110 * walk the bucket chain upon removal. The removal operation is thus 1111 * considerable slow if the hash table is not correctly sized. 1112 * 1113 * Will automatically shrink the table if permitted when residency drops 1114 * below 30%. 1115 * 1116 * Returns zero on success, -ENOENT if the entry could not be found. 1117 */ 1118static inline int rhashtable_remove_fast( 1119 struct rhashtable *ht, struct rhash_head *obj, 1120 const struct rhashtable_params params) 1121{ 1122 return __rhashtable_remove_fast(ht, obj, params, false); 1123} 1124 1125/** 1126 * rhltable_remove - remove object from hash list table 1127 * @hlt: hash list table 1128 * @list: pointer to hash list head inside object 1129 * @params: hash table parameters 1130 * 1131 * Since the hash chain is single linked, the removal operation needs to 1132 * walk the bucket chain upon removal. The removal operation is thus 1133 * considerable slow if the hash table is not correctly sized. 1134 * 1135 * Will automatically shrink the table if permitted when residency drops 1136 * below 30% 1137 * 1138 * Returns zero on success, -ENOENT if the entry could not be found. 1139 */ 1140static inline int rhltable_remove( 1141 struct rhltable *hlt, struct rhlist_head *list, 1142 const struct rhashtable_params params) 1143{ 1144 return __rhashtable_remove_fast(&hlt->ht, &list->rhead, params, true); 1145} 1146 1147/* Internal function, please use rhashtable_replace_fast() instead */ 1148static inline int __rhashtable_replace_fast( 1149 struct rhashtable *ht, struct bucket_table *tbl, 1150 struct rhash_head *obj_old, struct rhash_head *obj_new, 1151 const struct rhashtable_params params) 1152{ 1153 struct rhash_lock_head __rcu **bkt; 1154 struct rhash_head __rcu **pprev; 1155 struct rhash_head *he; 1156 unsigned long flags; 1157 unsigned int hash; 1158 int err = -ENOENT; 1159 1160 /* Minimally, the old and new objects must have same hash 1161 * (which should mean identifiers are the same). 1162 */ 1163 hash = rht_head_hashfn(ht, tbl, obj_old, params); 1164 if (hash != rht_head_hashfn(ht, tbl, obj_new, params)) 1165 return -EINVAL; 1166 1167 bkt = rht_bucket_var(tbl, hash); 1168 if (!bkt) 1169 return -ENOENT; 1170 1171 pprev = NULL; 1172 flags = rht_lock(tbl, bkt); 1173 1174 rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) { 1175 if (he != obj_old) { 1176 pprev = &he->next; 1177 continue; 1178 } 1179 1180 rcu_assign_pointer(obj_new->next, obj_old->next); 1181 if (pprev) { 1182 rcu_assign_pointer(*pprev, obj_new); 1183 rht_unlock(tbl, bkt, flags); 1184 } else { 1185 rht_assign_unlock(tbl, bkt, obj_new, flags); 1186 } 1187 err = 0; 1188 goto unlocked; 1189 } 1190 1191 rht_unlock(tbl, bkt, flags); 1192 1193unlocked: 1194 return err; 1195} 1196 1197/** 1198 * rhashtable_replace_fast - replace an object in hash table 1199 * @ht: hash table 1200 * @obj_old: pointer to hash head inside object being replaced 1201 * @obj_new: pointer to hash head inside object which is new 1202 * @params: hash table parameters 1203 * 1204 * Replacing an object doesn't affect the number of elements in the hash table 1205 * or bucket, so we don't need to worry about shrinking or expanding the 1206 * table here. 1207 * 1208 * Returns zero on success, -ENOENT if the entry could not be found, 1209 * -EINVAL if hash is not the same for the old and new objects. 1210 */ 1211static inline int rhashtable_replace_fast( 1212 struct rhashtable *ht, struct rhash_head *obj_old, 1213 struct rhash_head *obj_new, 1214 const struct rhashtable_params params) 1215{ 1216 struct bucket_table *tbl; 1217 int err; 1218 1219 rcu_read_lock(); 1220 1221 tbl = rht_dereference_rcu(ht->tbl, ht); 1222 1223 /* Because we have already taken (and released) the bucket 1224 * lock in old_tbl, if we find that future_tbl is not yet 1225 * visible then that guarantees the entry to still be in 1226 * the old tbl if it exists. 1227 */ 1228 while ((err = __rhashtable_replace_fast(ht, tbl, obj_old, 1229 obj_new, params)) && 1230 (tbl = rht_dereference_rcu(tbl->future_tbl, ht))) 1231 ; 1232 1233 rcu_read_unlock(); 1234 1235 return err; 1236} 1237 1238/** 1239 * rhltable_walk_enter - Initialise an iterator 1240 * @hlt: Table to walk over 1241 * @iter: Hash table Iterator 1242 * 1243 * This function prepares a hash table walk. 1244 * 1245 * Note that if you restart a walk after rhashtable_walk_stop you 1246 * may see the same object twice. Also, you may miss objects if 1247 * there are removals in between rhashtable_walk_stop and the next 1248 * call to rhashtable_walk_start. 1249 * 1250 * For a completely stable walk you should construct your own data 1251 * structure outside the hash table. 1252 * 1253 * This function may be called from any process context, including 1254 * non-preemptable context, but cannot be called from softirq or 1255 * hardirq context. 1256 * 1257 * You must call rhashtable_walk_exit after this function returns. 1258 */ 1259static inline void rhltable_walk_enter(struct rhltable *hlt, 1260 struct rhashtable_iter *iter) 1261{ 1262 return rhashtable_walk_enter(&hlt->ht, iter); 1263} 1264 1265/** 1266 * rhltable_free_and_destroy - free elements and destroy hash list table 1267 * @hlt: the hash list table to destroy 1268 * @free_fn: callback to release resources of element 1269 * @arg: pointer passed to free_fn 1270 * 1271 * See documentation for rhashtable_free_and_destroy. 1272 */ 1273static inline void rhltable_free_and_destroy(struct rhltable *hlt, 1274 void (*free_fn)(void *ptr, 1275 void *arg), 1276 void *arg) 1277{ 1278 return rhashtable_free_and_destroy(&hlt->ht, free_fn, arg); 1279} 1280 1281static inline void rhltable_destroy(struct rhltable *hlt) 1282{ 1283 return rhltable_free_and_destroy(hlt, NULL, NULL); 1284} 1285 1286#endif /* _LINUX_RHASHTABLE_H */ 1287