include/urcu/rculfhash.h

   1 // SPDX-FileCopyrightText: 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   2 // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
   3 //
   4 // SPDX-License-Identifier: LGPL-2.1-or-later
   5
   6 #ifndef _URCU_RCULFHASH_H
   7 #define _URCU_RCULFHASH_H
   8
   9 /*
  10  * Userspace RCU library - Lock-Free RCU Hash Table
  11  *
  12  * For use with URCU_API_MAP (API mapping of liburcu), include this file
  13  * _after_ including your URCU flavor.
  14  */
  15
  16 #include <urcu/config.h>
  17 #include <stdint.h>
  18 #include <pthread.h>
  19 #include <urcu/compiler.h>
  20
  21 #ifdef __cplusplus
  22 extern "C" {
  23 #endif
  24
  25 struct cds_lfht;
  26
  27 /*
  28  * cds_lfht_node: Contains the next pointers and reverse-hash
  29  * value required for lookup and traversal of the hash table.
  30  *
  31  * struct cds_lfht_node should be aligned on 8-bytes boundaries because
  32  * the three lower bits are used as flags. It is worth noting that the
  33  * information contained within these three bits could be represented on
  34  * two bits by re-using the same bit for REMOVAL_OWNER_FLAG and
  35  * BUCKET_FLAG. This can be done if we ensure that no iterator nor
  36  * updater check the BUCKET_FLAG after it detects that the REMOVED_FLAG
  37  * is set. Given the minimum size of struct cds_lfht_node is 8 bytes on
  38  * 32-bit architectures, we choose to go for simplicity and reserve
  39  * three bits.
  40  *
  41  * struct cds_lfht_node can be embedded into a structure (as a field).
  42  * caa_container_of() can be used to get the structure from the struct
  43  * cds_lfht_node after a lookup.
  44  *
  45  * The structure which embeds it typically holds the key (or key-value
  46  * pair) of the object. The caller code is responsible for calculation
  47  * of the hash value for cds_lfht APIs.
  48  */
  49 struct cds_lfht_node {
  50         struct cds_lfht_node *next;     /* ptr | REMOVAL_OWNER_FLAG | BUCKET_FLAG | REMOVED_FLAG */
  51         unsigned long reverse_hash;
  52 } __attribute__((aligned(8)));
  53
  54 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
  55 struct cds_lfht_iter {
  56         struct cds_lfht_node *node, *next;
  57         /*
  58          * For debugging purposes, build both API users and rculfhash
  59          * library with CDS_LFHT_ITER_DEBUG defined. This enables extra
  60          * consistency checks for calls to a cds_lfht_next() or
  61          * cds_lfht_next_duplicate() after the iterator has been
  62          * re-purposed to iterate on a different hash table. This is a
  63          * common programming mistake when performing hash table lookup
  64          * nested in a hash table traversal.
  65          */
  66 #ifdef CONFIG_CDS_LFHT_ITER_DEBUG
  67         struct cds_lfht *lfht;
  68 #endif
  69 };
  70
  71 static inline
  72 struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter)
  73 {
  74         return iter->node;
  75 }
  76
  77 struct rcu_flavor_struct;
  78
  79 /*
  80  * Caution !
  81  * Ensure reader and writer threads are registered as urcu readers.
  82  */
  83
  84 typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, const void *key);
  85
  86 /*
  87  * cds_lfht_node_init - initialize a hash table node
  88  * @node: the node to initialize.
  89  *
  90  * This function is kept to be eventually used for debugging purposes
  91  * (detection of memory corruption).
  92  */
  93 static inline
  94 void cds_lfht_node_init(struct cds_lfht_node *node __attribute__((unused)))
  95 {
  96 }
  97
  98 /*
  99  * cds_lfht_node_init_deleted - initialize a hash table node to "removed" state
 100  * @node: the node to initialize.
 101  *
 102  * Initialize the node such that cds_lfht_is_node_deleted() can be used
 103  * on the node before it is added to a hash table.
 104  */
 105 extern
 106 void cds_lfht_node_init_deleted(struct cds_lfht_node *node);
 107
 108 /*
 109  * Hash table creation flags.
 110  */
 111 enum {
 112         CDS_LFHT_AUTO_RESIZE = (1U << 0),
 113         CDS_LFHT_ACCOUNTING = (1U << 1),
 114 };
 115
 116 struct cds_lfht_mm_type {
 117         struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets,
 118                         unsigned long max_nr_buckets);
 119         void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order);
 120         void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order);
 121         struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
 122                         unsigned long index);
 123 };
 124
 125 extern const struct cds_lfht_mm_type cds_lfht_mm_order;
 126 extern const struct cds_lfht_mm_type cds_lfht_mm_chunk;
 127 extern const struct cds_lfht_mm_type cds_lfht_mm_mmap;
 128
 129 /*
 130  * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
 131  */
 132 extern
 133 struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 134                         unsigned long min_nr_alloc_buckets,
 135                         unsigned long max_nr_buckets,
 136                         int flags,
 137                         const struct cds_lfht_mm_type *mm,
 138                         const struct rcu_flavor_struct *flavor,
 139                         pthread_attr_t *attr);
 140
 141 /*
 142  * cds_lfht_new_flavor - allocate a hash table tied to a RCU flavor.
 143  * @init_size: number of buckets to allocate initially. Must be power of two.
 144  * @min_nr_alloc_buckets: the minimum number of allocated buckets.
 145  *                        (must be power of two)
 146  * @max_nr_buckets: the maximum number of hash table buckets allowed.
 147  *                  (must be power of two, 0 is accepted, means
 148  *                  "infinite")
 149  * @flavor: flavor of liburcu to use to synchronize the hash table
 150  * @flags: hash table creation flags (can be combined with bitwise or: '|').
 151  *           0: no flags.
 152  *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
 153  *           CDS_LFHT_ACCOUNTING: count the number of node addition
 154  *                                and removal in the table
 155  * @attr: optional resize worker thread attributes. NULL for default.
 156  *
 157  * Return NULL on error.
 158  * Note: the RCU flavor must be already included before the hash table header.
 159  *
 160  * The programmer is responsible for ensuring that resize operation has a
 161  * priority equal to hash table updater threads. It should be performed by
 162  * specifying the appropriate priority in the pthread "attr" argument, and,
 163  * for CDS_LFHT_AUTO_RESIZE, by ensuring that call_rcu worker threads also have
 164  * this priority level. Having lower priority for call_rcu and resize threads
 165  * does not pose any correctness issue, but the resize operations could be
 166  * starved by updates, thus leading to long hash table bucket chains.
 167  * Threads calling cds_lfht_new are NOT required to be registered RCU
 168  * read-side threads. It can be called very early. (e.g. before RCU is
 169  * initialized)
 170  */
 171 static inline
 172 struct cds_lfht *cds_lfht_new_flavor(unsigned long init_size,
 173                         unsigned long min_nr_alloc_buckets,
 174                         unsigned long max_nr_buckets,
 175                         int flags,
 176                         const struct rcu_flavor_struct *flavor,
 177                         pthread_attr_t *attr)
 178 {
 179         return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets,
 180                         flags, NULL, flavor, attr);
 181 }
 182
 183
 184 #ifdef URCU_API_MAP
 185 /*
 186  * cds_lfht_new - allocate a hash table.
 187  * @init_size: number of buckets to allocate initially. Must be power of two.
 188  * @min_nr_alloc_buckets: the minimum number of allocated buckets.
 189  *                        (must be power of two)
 190  * @max_nr_buckets: the maximum number of hash table buckets allowed.
 191  *                  (must be power of two, 0 is accepted, means
 192  *                  "infinite")
 193  * @flags: hash table creation flags (can be combined with bitwise or: '|').
 194  *           0: no flags.
 195  *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
 196  *           CDS_LFHT_ACCOUNTING: count the number of node addition
 197  *                                and removal in the table
 198  * @attr: optional resize worker thread attributes. NULL for default.
 199  *
 200  * Return NULL on error.
 201  * Note: the RCU flavor must be already included before the hash table header.
 202  *
 203  * The programmer is responsible for ensuring that resize operation has a
 204  * priority equal to hash table updater threads. It should be performed by
 205  * specifying the appropriate priority in the pthread "attr" argument, and,
 206  * for CDS_LFHT_AUTO_RESIZE, by ensuring that call_rcu worker threads also have
 207  * this priority level. Having lower priority for call_rcu and resize threads
 208  * does not pose any correctness issue, but the resize operations could be
 209  * starved by updates, thus leading to long hash table bucket chains.
 210  * Threads calling cds_lfht_new are NOT required to be registered RCU
 211  * read-side threads. It can be called very early. (e.g. before RCU is
 212  * initialized)
 213  */
 214 static inline
 215 struct cds_lfht *cds_lfht_new(unsigned long init_size,
 216                         unsigned long min_nr_alloc_buckets,
 217                         unsigned long max_nr_buckets,
 218                         int flags,
 219                         pthread_attr_t *attr)
 220 {
 221         return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets,
 222                         flags, NULL, &rcu_flavor, attr);
 223 }
 224 #endif /* URCU_API_MAP */
 225
 226 /*
 227  * cds_lfht_destroy - destroy a hash table.
 228  * @ht: the hash table to destroy.
 229  * @attr: (output) resize worker thread attributes, as received by cds_lfht_new.
 230  *        The caller will typically want to free this pointer if dynamically
 231  *        allocated. The attr point can be NULL if the caller does not
 232  *        need to be informed of the value passed to cds_lfht_new().
 233  *
 234  * Return 0 on success, negative error value on error.
 235
 236  * Threads calling this API need to be registered RCU read-side threads.
 237  *
 238  * Prior to liburcu 0.10:
 239  * - cds_lfht_destroy should *not* be called from a RCU read-side
 240  *   critical section. It should *not* be called from a call_rcu thread
 241  *   context neither.
 242  *
 243  * Starting from liburcu 0.10, rculfhash implements its own worker
 244  * thread to handle resize operations, which removes the above RCU
 245  * read-side critical section requirement on cds_lfht_destroy.
 246  */
 247 extern
 248 int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr);
 249
 250 /*
 251  * cds_lfht_count_nodes - count the number of nodes in the hash table.
 252  * @ht: the hash table.
 253  * @split_count_before: sample the node count split-counter before traversal.
 254  * @count: traverse the hash table, count the number of nodes observed.
 255  * @split_count_after: sample the node count split-counter after traversal.
 256  *
 257  * Call with rcu_read_lock held.
 258  * Threads calling this API need to be registered RCU read-side threads.
 259  */
 260 extern
 261 void cds_lfht_count_nodes(struct cds_lfht *ht,
 262                 long *split_count_before,
 263                 unsigned long *count,
 264                 long *split_count_after);
 265
 266 /*
 267  * cds_lfht_lookup - lookup a node by key.
 268  * @ht: the hash table.
 269  * @hash: the key hash.
 270  * @match: the key match function.
 271  * @key: the current node key.
 272  * @iter: node, if found (output). *iter->node set to NULL if not found.
 273  *
 274  * Call with rcu_read_lock held.
 275  * Threads calling this API need to be registered RCU read-side threads.
 276  * This function acts as a rcu_dereference() to read the node pointer.
 277  */
 278 extern
 279 void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 280                 cds_lfht_match_fct match, const void *key,
 281                 struct cds_lfht_iter *iter);
 282
 283 /*
 284  * cds_lfht_next_duplicate - get the next item with same key, after iterator.
 285  * @ht: the hash table.
 286  * @match: the key match function.
 287  * @key: the current node key.
 288  * @iter: input: current iterator.
 289  *        output: node, if found. *iter->node set to NULL if not found.
 290  *
 291  * Uses an iterator initialized by a lookup or traversal. Important: the
 292  * iterator _needs_ to be initialized before calling
 293  * cds_lfht_next_duplicate.
 294  * Sets *iter-node to the following node with same key.
 295  * Sets *iter->node to NULL if no following node exists with same key.
 296  * RCU read-side lock must be held across cds_lfht_lookup and
 297  * cds_lfht_next calls, and also between cds_lfht_next calls using the
 298  * node returned by a previous cds_lfht_next.
 299  * Call with rcu_read_lock held.
 300  * Threads calling this API need to be registered RCU read-side threads.
 301  * This function acts as a rcu_dereference() to read the node pointer.
 302  */
 303 extern
 304 void cds_lfht_next_duplicate(struct cds_lfht *ht,
 305                 cds_lfht_match_fct match, const void *key,
 306                 struct cds_lfht_iter *iter);
 307
 308 /*
 309  * cds_lfht_first - get the first node in the table.
 310  * @ht: the hash table.
 311  * @iter: First node, if exists (output). *iter->node set to NULL if not found.
 312  *
 313  * Output in "*iter". *iter->node set to NULL if table is empty.
 314  * Call with rcu_read_lock held.
 315  * Threads calling this API need to be registered RCU read-side threads.
 316  * This function acts as a rcu_dereference() to read the node pointer.
 317  */
 318 extern
 319 void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 320
 321 /*
 322  * cds_lfht_next - get the next node in the table.
 323  * @ht: the hash table.
 324  * @iter: input: current iterator.
 325  *        output: next node, if exists. *iter->node set to NULL if not found.
 326  *
 327  * Input/Output in "*iter". *iter->node set to NULL if *iter was
 328  * pointing to the last table node.
 329  * Call with rcu_read_lock held.
 330  * Threads calling this API need to be registered RCU read-side threads.
 331  * This function acts as a rcu_dereference() to read the node pointer.
 332  */
 333 extern
 334 void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 335
 336 /*
 337  * cds_lfht_add - add a node to the hash table.
 338  * @ht: the hash table.
 339  * @hash: the key hash.
 340  * @node: the node to add.
 341  *
 342  * This function supports adding redundant keys into the table.
 343  * Call with rcu_read_lock held.
 344  * Threads calling this API need to be registered RCU read-side threads.
 345  * This function issues a full memory barrier before and after its
 346  * atomic commit.
 347  */
 348 extern
 349 void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 350                 struct cds_lfht_node *node);
 351
 352 /*
 353  * cds_lfht_add_unique - add a node to hash table, if key is not present.
 354  * @ht: the hash table.
 355  * @hash: the node's hash.
 356  * @match: the key match function.
 357  * @key: the node's key.
 358  * @node: the node to try adding.
 359  *
 360  * Return the node added upon success.
 361  * Return the unique node already present upon failure. If
 362  * cds_lfht_add_unique fails, the node passed as parameter should be
 363  * freed by the caller. In this case, the caller does NOT need to wait
 364  * for a grace period before freeing or re-using the node.
 365  * Call with rcu_read_lock held.
 366  * Threads calling this API need to be registered RCU read-side threads.
 367  *
 368  * The semantic of this function is that if only this function is used
 369  * to add keys into the table, no duplicated keys should ever be
 370  * observable in the table. The same guarantee apply for combination of
 371  * add_unique and add_replace (see below).
 372  *
 373  * Upon success, this function issues a full memory barrier before and
 374  * after its atomic commit. Upon failure, this function acts like a
 375  * simple lookup operation: it acts as a rcu_dereference() to read the
 376  * node pointer. The failure case does not guarantee any other memory
 377  * barrier.
 378  */
 379 extern
 380 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 381                 unsigned long hash,
 382                 cds_lfht_match_fct match,
 383                 const void *key,
 384                 struct cds_lfht_node *node);
 385
 386 /*
 387  * cds_lfht_add_replace - replace or add a node within hash table.
 388  * @ht: the hash table.
 389  * @hash: the node's hash.
 390  * @match: the key match function.
 391  * @key: the node's key.
 392  * @node: the node to add.
 393  *
 394  * Return the node replaced upon success. If no node matching the key
 395  * was present, return NULL, which also means the operation succeeded.
 396  * This replacement operation should never fail.
 397  * Call with rcu_read_lock held.
 398  * Threads calling this API need to be registered RCU read-side threads.
 399  * After successful replacement, a grace period must be waited for before
 400  * freeing or re-using the memory reserved for the returned node.
 401  *
 402  * The semantic of replacement vs lookups and traversals is the
 403  * following: if lookups and traversals are performed between a key
 404  * unique insertion and its removal, we guarantee that the lookups and
 405  * traversals will always find exactly one instance of the key if it is
 406  * replaced concurrently with the lookups.
 407  *
 408  * Providing this semantic allows us to ensure that replacement-only
 409  * schemes will never generate duplicated keys. It also allows us to
 410  * guarantee that a combination of add_replace and add_unique updates
 411  * will never generate duplicated keys.
 412  *
 413  * This function issues a full memory barrier before and after its
 414  * atomic commit.
 415  */
 416 extern
 417 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
 418                 unsigned long hash,
 419                 cds_lfht_match_fct match,
 420                 const void *key,
 421                 struct cds_lfht_node *node);
 422
 423 /*
 424  * cds_lfht_replace - replace a node pointed to by iter within hash table.
 425  * @ht: the hash table.
 426  * @old_iter: the iterator position of the node to replace.
 427  * @hash: the node's hash.
 428  * @match: the key match function.
 429  * @key: the node's key.
 430  * @new_node: the new node to use as replacement.
 431  *
 432  * Return 0 if replacement is successful, negative value otherwise.
 433  * Replacing a NULL old node or an already removed node will fail with
 434  * -ENOENT.
 435  * If the hash or value of the node to replace and the new node differ,
 436  * this function returns -EINVAL without proceeding to the replacement.
 437  * Old node can be looked up with cds_lfht_lookup and cds_lfht_next.
 438  * RCU read-side lock must be held between lookup and replacement.
 439  * Call with rcu_read_lock held.
 440  * Threads calling this API need to be registered RCU read-side threads.
 441  * After successful replacement, a grace period must be waited for before
 442  * freeing or re-using the memory reserved for the old node (which can
 443  * be accessed with cds_lfht_iter_get_node).
 444  *
 445  * The semantic of replacement vs lookups is the same as
 446  * cds_lfht_add_replace().
 447  *
 448  * Upon success, this function issues a full memory barrier before and
 449  * after its atomic commit. Upon failure, this function does not issue
 450  * any memory barrier.
 451  */
 452 extern
 453 int cds_lfht_replace(struct cds_lfht *ht,
 454                 struct cds_lfht_iter *old_iter,
 455                 unsigned long hash,
 456                 cds_lfht_match_fct match,
 457                 const void *key,
 458                 struct cds_lfht_node *new_node);
 459
 460 /*
 461  * cds_lfht_del - remove node pointed to by iterator from hash table.
 462  * @ht: the hash table.
 463  * @node: the node to delete.
 464  *
 465  * Return 0 if the node is successfully removed, negative value
 466  * otherwise.
 467  * Deleting a NULL node or an already removed node will fail with a
 468  * negative value.
 469  * Node can be looked up with cds_lfht_lookup and cds_lfht_next,
 470  * followed by use of cds_lfht_iter_get_node.
 471  * RCU read-side lock must be held between lookup and removal.
 472  * Call with rcu_read_lock held.
 473  * Threads calling this API need to be registered RCU read-side threads.
 474  * After successful removal, a grace period must be waited for before
 475  * freeing or re-using the memory reserved for old node (which can be
 476  * accessed with cds_lfht_iter_get_node).
 477  * Upon success, this function issues a full memory barrier before and
 478  * after its atomic commit. Upon failure, this function does not issue
 479  * any memory barrier.
 480  */
 481 extern
 482 int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node);
 483
 484 /*
 485  * cds_lfht_is_node_deleted - query whether a node is removed from hash table.
 486  *
 487  * Return non-zero if the node is deleted from the hash table, 0
 488  * otherwise.
 489  * Node can be looked up with cds_lfht_lookup and cds_lfht_next,
 490  * followed by use of cds_lfht_iter_get_node.
 491  * RCU read-side lock must be held between lookup and call to this
 492  * function.
 493  * Call with rcu_read_lock held.
 494  * Threads calling this API need to be registered RCU read-side threads.
 495  * This function does not issue any memory barrier.
 496  */
 497 extern
 498 int cds_lfht_is_node_deleted(const struct cds_lfht_node *node);
 499
 500 /*
 501  * cds_lfht_resize - Force a hash table resize
 502  * @ht: the hash table.
 503  * @new_size: update to this hash table size.
 504  *
 505  * Threads calling this API need to be registered RCU read-side threads.
 506  * This function does not (necessarily) issue memory barriers.
 507  * cds_lfht_resize should *not* be called from a RCU read-side critical
 508  * section.
 509  */
 510 extern
 511 void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 512
 513 /*
 514  * Note: it is safe to perform element removal (del), replacement, or
 515  * any hash table update operation during any of the following hash
 516  * table traversals.
 517  * These functions act as rcu_dereference() to read the node pointers.
 518  */
 519 #define cds_lfht_for_each(ht, iter, node)                               \
 520         for (cds_lfht_first(ht, iter),                                  \
 521                         node = cds_lfht_iter_get_node(iter);            \
 522                 node != NULL;                                           \
 523                 cds_lfht_next(ht, iter),                                \
 524                         node = cds_lfht_iter_get_node(iter))
 525
 526 #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)   \
 527         for (cds_lfht_lookup(ht, hash, match, key, iter),               \
 528                         node = cds_lfht_iter_get_node(iter);            \
 529                 node != NULL;                                           \
 530                 cds_lfht_next_duplicate(ht, match, key, iter),          \
 531                         node = cds_lfht_iter_get_node(iter))
 532
 533 #define cds_lfht_entry(ptr, type, member)                               \
 534         caa_container_of_check_null(ptr, type, member)
 535
 536 #define cds_lfht_for_each_entry(ht, iter, pos, member)                  \
 537         for (cds_lfht_first(ht, iter),                                  \
 538                         pos = cds_lfht_entry(cds_lfht_iter_get_node(iter), \
 539                                 __typeof__(*(pos)), member);            \
 540                 pos != NULL;                                            \
 541                 cds_lfht_next(ht, iter),                                \
 542                         pos = cds_lfht_entry(cds_lfht_iter_get_node(iter), \
 543                                 __typeof__(*(pos)), member))
 544
 545 #define cds_lfht_for_each_entry_duplicate(ht, hash, match, key,         \
 546                                 iter, pos, member)                      \
 547         for (cds_lfht_lookup(ht, hash, match, key, iter),               \
 548                         pos = cds_lfht_entry(cds_lfht_iter_get_node(iter), \
 549                                 __typeof__(*(pos)), member);            \
 550                 pos != NULL;                                            \
 551                 cds_lfht_next_duplicate(ht, match, key, iter),          \
 552                         pos = cds_lfht_entry(cds_lfht_iter_get_node(iter), \
 553                                 __typeof__(*(pos)), member))
 554
 555 #ifdef __cplusplus
 556 }
 557 #endif
 558
 559 #endif /* _URCU_RCULFHASH_H */