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  * Include this file _after_ including your URCU flavor.
  27  */
  28
  29 #include <stdint.h>
  30 #include <urcu/compiler.h>
  31 #include <urcu-call-rcu.h>
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 /*
  38  * cds_lfht_node: Contains the next pointers and reverse-hash
  39  * value required for lookup and traversal of the hash table.
  40  *
  41  * struct cds_lfht_node should be aligned on 4-bytes boundaries because
  42  * the two lower bits are used as flags.
  43  *
  44  * struct cds_lfht_node can be embedded into a structure (as a field).
  45  * caa_container_of() can be used to get the structure from the struct
  46  * cds_lfht_node after a lookup.
  47  *
  48  * The structure which embeds it typically holds the key (or key-value
  49  * pair) of the object. The caller code is responsible for calculation
  50  * of the hash value for cds_lfht APIs.
  51  */
  52 struct cds_lfht_node {
  53         struct cds_lfht_node *next;     /* ptr | BUCKET_FLAG | REMOVED_FLAG */
  54         unsigned long reverse_hash;
  55 } __attribute__((aligned(4)));
  56
  57 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
  58 struct cds_lfht_iter {
  59         struct cds_lfht_node *node, *next;
  60 };
  61
  62 static inline
  63 struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter)
  64 {
  65         return iter->node;
  66 }
  67
  68 struct cds_lfht;
  69
  70 /*
  71  * Caution !
  72  * Ensure reader and writer threads are registered as urcu readers.
  73  */
  74
  75 typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, const void *key);
  76
  77 /*
  78  * cds_lfht_node_init - initialize a hash table node
  79  * @node: the node to initialize.
  80  *
  81  * This function is kept to be eventually used for debugging purposes
  82  * (detection of memory corruption).
  83  */
  84 static inline
  85 void cds_lfht_node_init(struct cds_lfht_node *node)
  86 {
  87 }
  88
  89 /*
  90  * Hash table creation flags.
  91  */
  92 enum {
  93         CDS_LFHT_AUTO_RESIZE = (1U << 0),
  94         CDS_LFHT_ACCOUNTING = (1U << 1),
  95 };
  96
  97 /*
  98  * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
  99  */
 100 struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 101                         unsigned long min_nr_alloc_buckets,
 102                         unsigned long max_nr_buckets,
 103                         int flags,
 104                         void (*cds_lfht_call_rcu)(struct rcu_head *head,
 105                                 void (*func)(struct rcu_head *head)),
 106                         void (*cds_lfht_synchronize_rcu)(void),
 107                         void (*cds_lfht_rcu_read_lock)(void),
 108                         void (*cds_lfht_rcu_read_unlock)(void),
 109                         void (*cds_lfht_rcu_thread_offline)(void),
 110                         void (*cds_lfht_rcu_thread_online)(void),
 111                         void (*cds_lfht_rcu_register_thread)(void),
 112                         void (*cds_lfht_rcu_unregister_thread)(void),
 113                         pthread_attr_t *attr);
 114
 115 /*
 116  * cds_lfht_new - allocate a hash table.
 117  * @init_size: number of buckets to allocate initially. Must be power of two.
 118  * @min_nr_alloc_buckets: the minimum number of allocated buckets.
 119  *                        (must be power of two)
 120  * @max_nr_buckets: the maximum number of hash table buckets allowed.
 121  *                  (must be power of two)
 122  * @flags: hash table creation flags (can be combined with bitwise or: '|').
 123  *           0: no flags.
 124  *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
 125  *           CDS_LFHT_ACCOUNTING: count the number of node addition
 126  *                                and removal in the table
 127  * @attr: optional resize worker thread attributes. NULL for default.
 128  *
 129  * Return NULL on error.
 130  * Note: the RCU flavor must be already included before the hash table header.
 131  *
 132  * The programmer is responsible for ensuring that resize operation has a
 133  * priority equal to hash table updater threads. It should be performed by
 134  * specifying the appropriate priority in the pthread "attr" argument, and,
 135  * for CDS_LFHT_AUTO_RESIZE, by ensuring that call_rcu worker threads also have
 136  * this priority level. Having lower priority for call_rcu and resize threads
 137  * does not pose any correctness issue, but the resize operations could be
 138  * starved by updates, thus leading to long hash table bucket chains.
 139  * Threads calling this API are NOT required to be registered RCU read-side
 140  * threads. It can be called very early.(before rcu is initialized ...etc.)
 141  */
 142 static inline
 143 struct cds_lfht *cds_lfht_new(unsigned long init_size,
 144                         unsigned long min_nr_alloc_buckets,
 145                         unsigned long max_nr_buckets,
 146                         int flags,
 147                         pthread_attr_t *attr)
 148 {
 149         return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags,
 150                         call_rcu, synchronize_rcu, rcu_read_lock,
 151                         rcu_read_unlock, rcu_thread_offline,
 152                         rcu_thread_online, rcu_register_thread,
 153                         rcu_unregister_thread, attr);
 154 }
 155
 156 /*
 157  * cds_lfht_destroy - destroy a hash table.
 158  * @ht: the hash table to destroy.
 159  * @attr: (output) resize worker thread attributes, as received by cds_lfht_new.
 160  *        The caller will typically want to free this pointer if dynamically
 161  *        allocated. The attr point can be NULL if the caller does not
 162  *        need to be informed of the value passed to cds_lfht_new().
 163  *
 164  * Return 0 on success, negative error value on error.
 165  * Threads calling this API need to be registered RCU read-side threads.
 166  */
 167 int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr);
 168
 169 /*
 170  * cds_lfht_count_nodes - count the number of nodes in the hash table.
 171  * @ht: the hash table.
 172  * @split_count_before: Sample the node count split-counter before traversal.
 173  * @count: Traverse the hash table, count the number of nodes observed.
 174  * @removed: Number of logically removed nodes observed during traversal.
 175  * @split_count_after: Sample the node count split-counter after traversal.
 176  *
 177  * Call with rcu_read_lock held.
 178  * Threads calling this API need to be registered RCU read-side threads.
 179  */
 180 void cds_lfht_count_nodes(struct cds_lfht *ht,
 181                 long *split_count_before,
 182                 unsigned long *count,
 183                 unsigned long *removed,
 184                 long *split_count_after);
 185
 186 /*
 187  * cds_lfht_lookup - lookup a node by key.
 188  * @ht: the hash table.
 189  * @hash: the key hash.
 190  * @match: the key match function.
 191  * @key: the current node key.
 192  * @iter: Node, if found (output). *iter->node set to NULL if not found.
 193  *
 194  * Call with rcu_read_lock held.
 195  * Threads calling this API need to be registered RCU read-side threads.
 196  */
 197 void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 198                 cds_lfht_match_fct match, const void *key,
 199                 struct cds_lfht_iter *iter);
 200
 201 /*
 202  * cds_lfht_next_duplicate - get the next item with same key (after a lookup).
 203  * @ht: the hash table.
 204  * @match: the key match function.
 205  * @key: the current node key.
 206  * @iter: Node, if found (output). *iter->node set to NULL if not found.
 207  *
 208  * Uses an iterator initialized by a lookup.
 209  * Sets *iter-node to the following node with same key.
 210  * Sets *iter->node to NULL if no following node exists with same key.
 211  * RCU read-side lock must be held across cds_lfht_lookup and
 212  * cds_lfht_next calls, and also between cds_lfht_next calls using the
 213  * node returned by a previous cds_lfht_next.
 214  * Call with rcu_read_lock held.
 215  * Threads calling this API need to be registered RCU read-side threads.
 216  */
 217 void cds_lfht_next_duplicate(struct cds_lfht *ht,
 218                 cds_lfht_match_fct match, const void *key,
 219                 struct cds_lfht_iter *iter);
 220
 221 /*
 222  * cds_lfht_first - get the first node in the table.
 223  * @ht: the hash table.
 224  * @iter: First node, if exists (output). *iter->node set to NULL if not found.
 225  *
 226  * Output in "*iter". *iter->node set to NULL if table is empty.
 227  * Call with rcu_read_lock held.
 228  * Threads calling this API need to be registered RCU read-side threads.
 229  */
 230 void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 231
 232 /*
 233  * cds_lfht_next - get the next node in the table.
 234  * @ht: the hash table.
 235  * @iter: Next node, if exists (output). *iter->node set to NULL if not found.
 236  *
 237  * Input/Output in "*iter". *iter->node set to NULL if *iter was
 238  * pointing to the last table node.
 239  * Call with rcu_read_lock held.
 240  * Threads calling this API need to be registered RCU read-side threads.
 241  */
 242 void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 243
 244 /*
 245  * cds_lfht_add - add a node to the hash table.
 246  * @ht: the hash table.
 247  * @hash: the key hash.
 248  * @node: the node to add.
 249  *
 250  * This function supports adding redundant keys into the table.
 251  * Call with rcu_read_lock held.
 252  * Threads calling this API need to be registered RCU read-side threads.
 253  */
 254 void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 255                 struct cds_lfht_node *node);
 256
 257 /*
 258  * cds_lfht_add_unique - add a node to hash table, if key is not present.
 259  * @ht: the hash table.
 260  * @hash: the node's hash.
 261  * @match: the key match function.
 262  * @key: the node's key.
 263  * @node: the node to try adding.
 264  *
 265  * Return the node added upon success.
 266  * Return the unique node already present upon failure. If
 267  * cds_lfht_add_unique fails, the node passed as parameter should be
 268  * freed by the caller.
 269  * Call with rcu_read_lock held.
 270  * Threads calling this API need to be registered RCU read-side threads.
 271  *
 272  * The semantic of this function is that if only this function is used
 273  * to add keys into the table, no duplicated keys should ever be
 274  * observable in the table. The same guarantee apply for combination of
 275  * add_unique and add_replace (see below).
 276  */
 277 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 278                 unsigned long hash,
 279                 cds_lfht_match_fct match,
 280                 const void *key,
 281                 struct cds_lfht_node *node);
 282
 283 /*
 284  * cds_lfht_add_replace - replace or add a node within hash table.
 285  * @ht: the hash table.
 286  * @hash: the node's hash.
 287  * @match: the key match function.
 288  * @key: the node's key.
 289  * @node: the node to add.
 290  *
 291  * Return the node replaced upon success. If no node matching the key
 292  * was present, return NULL, which also means the operation succeeded.
 293  * This replacement operation should never fail.
 294  * Call with rcu_read_lock held.
 295  * Threads calling this API need to be registered RCU read-side threads.
 296  * After successful replacement, a grace period must be waited for before
 297  * freeing the memory reserved for the returned node.
 298  *
 299  * The semantic of replacement vs lookups is the following: if lookups
 300  * are performed between a key unique insertion and its removal, we
 301  * guarantee that the lookups and get next will always find exactly one
 302  * instance of the key if it is replaced concurrently with the lookups.
 303  *
 304  * Providing this semantic allows us to ensure that replacement-only
 305  * schemes will never generate duplicated keys. It also allows us to
 306  * guarantee that a combination of add_replace and add_unique updates
 307  * will never generate duplicated keys.
 308  */
 309 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
 310                 unsigned long hash,
 311                 cds_lfht_match_fct match,
 312                 const void *key,
 313                 struct cds_lfht_node *node);
 314
 315 /*
 316  * cds_lfht_replace - replace a node pointer to by iter within hash table.
 317  * @ht: the hash table.
 318  * @old_iter: the iterator position of the node to replace.
 319  * @now_node: the new node to try using for replacement.
 320  *
 321  * Return 0 if replacement is successful, negative value otherwise.
 322  * Replacing a NULL old node or an already removed node will fail with a
 323  * negative value.
 324  * Old node can be looked up with cds_lfht_lookup and cds_lfht_next.
 325  * RCU read-side lock must be held between lookup and replacement.
 326  * Call with rcu_read_lock held.
 327  * Threads calling this API need to be registered RCU read-side threads.
 328  * After successful replacement, a grace period must be waited for before
 329  * freeing the memory reserved for the old node (which can be accessed
 330  * with cds_lfht_iter_get_node).
 331  *
 332  * The semantic of replacement vs lookups is the following: if lookups
 333  * are performed between a key unique insertion and its removal, we
 334  * guarantee that the lookups and get next will always find exactly one
 335  * instance of the key if it is replaced concurrently with the lookups.
 336  *
 337  * Providing this semantic allows us to ensure that replacement-only
 338  * schemes will never generate duplicated keys. It also allows us to
 339  * guarantee that a combination of add_replace and add_unique updates
 340  * will never generate duplicated keys.
 341  */
 342 int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,
 343                 struct cds_lfht_node *new_node);
 344
 345 /*
 346  * cds_lfht_del - remove node pointed to by iterator from hash table.
 347  * @ht: the hash table.
 348  * @iter: the iterator position of the node to delete.
 349  *
 350  * Return 0 if the node is successfully removed, negative value
 351  * otherwise.
 352  * Replacing a NULL node or an already removed node will fail with a
 353  * negative value.
 354  * Node can be looked up with cds_lfht_lookup and cds_lfht_next.
 355  * cds_lfht_iter_get_node.
 356  * RCU read-side lock must be held between lookup and removal.
 357  * Call with rcu_read_lock held.
 358  * Threads calling this API need to be registered RCU read-side threads.
 359  * After successful removal, a grace period must be waited for before
 360  * freeing the memory reserved for old node (which can be accessed with
 361  * cds_lfht_iter_get_node).
 362  */
 363 int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 364
 365 /*
 366  * cds_lfht_resize - Force a hash table resize
 367  * @ht: the hash table.
 368  * @new_size: update to this hash table size.
 369  *
 370  * Threads calling this API need to be registered RCU read-side threads.
 371  */
 372 void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 373
 374 /*
 375  * Note: cds_lfht_for_each are safe for element removal during
 376  * iteration.
 377  */
 378 #define cds_lfht_for_each(ht, iter, node)                               \
 379         for (cds_lfht_first(ht, iter),                                  \
 380                         node = cds_lfht_iter_get_node(iter);            \
 381                 node != NULL;                                           \
 382                 cds_lfht_next(ht, iter),                                \
 383                         node = cds_lfht_iter_get_node(iter))
 384
 385 #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)   \
 386         for (cds_lfht_lookup(ht, hash, match, key, iter),               \
 387                         node = cds_lfht_iter_get_node(iter);            \
 388                 node != NULL;                                           \
 389                 cds_lfht_next_duplicate(ht, match, key, iter),          \
 390                         node = cds_lfht_iter_get_node(iter))
 391
 392 #define cds_lfht_for_each_entry(ht, iter, pos, member)                  \
 393         for (cds_lfht_first(ht, iter),                                  \
 394                         pos = caa_container_of(cds_lfht_iter_get_node(iter), \
 395                                         typeof(*(pos)), member);        \
 396                 &(pos)->member != NULL;                                 \
 397                 cds_lfht_next(ht, iter),                                \
 398                         pos = caa_container_of(cds_lfht_iter_get_node(iter), \
 399                                         typeof(*(pos)), member))
 400
 401 #define cds_lfht_for_each_entry_duplicate(ht, hash, match, key,         \
 402                                 iter, pos, member)                      \
 403         for (cds_lfht_lookup(ht, hash, match, key, iter),               \
 404                         pos = caa_container_of(cds_lfht_iter_get_node(iter), \
 405                                         typeof(*(pos)), member);        \
 406                 &(pos)->member != NULL;                                 \
 407                 cds_lfht_next_duplicate(ht, match, key, iter),          \
 408                         pos = caa_container_of(cds_lfht_iter_get_node(iter), \
 409                                         typeof(*(pos)), member))
 410
 411 #ifdef __cplusplus
 412 }
 413 #endif
 414
 415 #endif /* _URCU_RCULFHASH_H */