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