include/urcu/rculfhash.h

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