rculfhash: fix add unique
[urcu.git] / rculfhash.c
CommitLineData
5e28c532 1/*
abc490a1
MD
2 * rculfhash.c
3 *
4 * Userspace RCU library - Lock-Free Expandable RCU Hash Table
5 *
6 * Copyright 2010-2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
5e28c532
MD
21 */
22
2ed95849
MD
23#define _LGPL_SOURCE
24#include <stdlib.h>
e0ba718a
MD
25#include <errno.h>
26#include <assert.h>
27#include <stdio.h>
abc490a1 28#include <stdint.h>
f000907d 29#include <string.h>
e0ba718a 30
2ed95849 31#include <urcu.h>
abc490a1 32#include <urcu-call-rcu.h>
a42cc659
MD
33#include <urcu/arch.h>
34#include <urcu/uatomic.h>
674f7a69 35#include <urcu/jhash.h>
a42cc659 36#include <urcu/compiler.h>
abc490a1 37#include <urcu/rculfhash.h>
5e28c532 38#include <stdio.h>
464a1ec9 39#include <pthread.h>
44395fb7 40
f9830efd
MD
41#define DEBUG /* Test */
42
43#ifdef DEBUG
44#define dbg_printf(args...) printf(args)
45#else
46#define dbg_printf(args...)
47#endif
48
65e8e729
MD
49#define CHAIN_LEN_TARGET 1
50#define CHAIN_LEN_RESIZE_THRESHOLD 2
2ed95849 51
abc490a1
MD
52#ifndef max
53#define max(a, b) ((a) > (b) ? (a) : (b))
54#endif
2ed95849 55
395270b6 56struct rcu_table {
abc490a1 57 unsigned long size; /* always a power of 2 */
f9830efd 58 unsigned long resize_target;
11519af6 59 int resize_initiated;
abc490a1 60 struct rcu_head head;
395270b6
MD
61 struct rcu_ht_node *tbl[0];
62};
63
2ed95849 64struct rcu_ht {
395270b6 65 struct rcu_table *t; /* shared */
2ed95849 66 ht_hash_fct hash_fct;
732ad076
MD
67 ht_compare_fct compare_fct;
68 unsigned long hash_seed;
464a1ec9 69 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
abc490a1
MD
70 void (*ht_call_rcu)(struct rcu_head *head,
71 void (*func)(struct rcu_head *head));
2ed95849
MD
72};
73
abc490a1
MD
74struct rcu_resize_work {
75 struct rcu_head head;
2ed95849 76 struct rcu_ht *ht;
abc490a1 77};
2ed95849 78
abc490a1
MD
79/*
80 * Algorithm to reverse bits in a word by lookup table, extended to
81 * 64-bit words.
f9830efd 82 * Source:
abc490a1 83 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
f9830efd 84 * Originally from Public Domain.
abc490a1
MD
85 */
86
87static const uint8_t BitReverseTable256[256] =
2ed95849 88{
abc490a1
MD
89#define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
90#define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
91#define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
92 R6(0), R6(2), R6(1), R6(3)
93};
94#undef R2
95#undef R4
96#undef R6
2ed95849 97
abc490a1
MD
98static
99uint8_t bit_reverse_u8(uint8_t v)
100{
101 return BitReverseTable256[v];
102}
ab7d5fc6 103
abc490a1
MD
104static __attribute__((unused))
105uint32_t bit_reverse_u32(uint32_t v)
106{
107 return ((uint32_t) bit_reverse_u8(v) << 24) |
108 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
109 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
110 ((uint32_t) bit_reverse_u8(v >> 24));
2ed95849
MD
111}
112
abc490a1
MD
113static __attribute__((unused))
114uint64_t bit_reverse_u64(uint64_t v)
2ed95849 115{
abc490a1
MD
116 return ((uint64_t) bit_reverse_u8(v) << 56) |
117 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
118 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
119 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
120 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
121 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
122 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
123 ((uint64_t) bit_reverse_u8(v >> 56));
124}
125
126static
127unsigned long bit_reverse_ulong(unsigned long v)
128{
129#if (CAA_BITS_PER_LONG == 32)
130 return bit_reverse_u32(v);
131#else
132 return bit_reverse_u64(v);
133#endif
134}
135
f9830efd
MD
136/*
137 * Algorithm to find the log2 of a 32-bit unsigned integer.
138 * source: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
139 * Originally from Public Domain.
140 */
141static const char LogTable256[256] =
142{
143#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
144 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
145 LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
146 LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
147};
148
149uint32_t log2_u32(uint32_t v)
150{
151 uint32_t t, tt;
152
153 if ((tt = (v >> 16)))
154 return (t = (tt >> 8))
155 ? 24 + LogTable256[t]
156 : 16 + LogTable256[tt];
157 else
158 return (t = (v >> 8))
159 ? 8 + LogTable256[t]
160 : LogTable256[v];
161}
162
163static
164void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth);
165
166static
167void check_resize(struct rcu_ht *ht, struct rcu_table *t,
168 uint32_t chain_len)
169{
3390d470
MD
170 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
171 ht_resize_lazy(ht, t,
65e8e729 172 log2_u32(chain_len - CHAIN_LEN_TARGET - 1));
f9830efd
MD
173}
174
abc490a1
MD
175static
176struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
177{
178 return (struct rcu_ht_node *) (((unsigned long) node) & ~0x1);
179}
180
181static
182int is_removed(struct rcu_ht_node *node)
183{
184 return ((unsigned long) node) & 0x1;
185}
186
187static
188struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
189{
190 return (struct rcu_ht_node *) (((unsigned long) node) | 0x1);
191}
192
193static
f9830efd 194unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
abc490a1
MD
195{
196 unsigned long old1, old2;
197
198 old1 = uatomic_read(ptr);
199 do {
200 old2 = old1;
201 if (old2 >= v)
f9830efd 202 return old2;
abc490a1 203 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
f9830efd 204 return v;
abc490a1
MD
205}
206
273399de
MD
207/*
208 * Remove all logically deleted nodes from a bucket up to a certain node key.
209 */
210static
211void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
212{
213 struct rcu_ht_node *iter_prev, *iter, *next;
214
215 for (;;) {
216 iter_prev = dummy;
217 /* We can always skip the dummy node initially */
218 iter = rcu_dereference(iter_prev->next);
219 assert(iter_prev->reverse_hash <= node->reverse_hash);
273399de 220 for (;;) {
479c8a32
MD
221 if (unlikely(!iter))
222 return;
273399de
MD
223 if (clear_flag(iter)->reverse_hash > node->reverse_hash)
224 return;
225 next = rcu_dereference(clear_flag(iter)->next);
226 if (is_removed(next))
227 break;
273399de
MD
228 iter_prev = iter;
229 iter = next;
230 }
231 assert(!is_removed(iter));
232 (void) uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next));
233 }
234}
235
abc490a1 236static
3eca1b8c
MD
237int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
238 int unique)
abc490a1 239{
273399de 240 struct rcu_ht_node *iter_prev, *dummy, *iter, *next;
49c2e2d6 241 unsigned long hash;
abc490a1 242
f000907d 243 if (!t->size)
3eca1b8c 244 return 0;
49c2e2d6 245 hash = bit_reverse_ulong(node->reverse_hash);
abc490a1 246 for (;;) {
f9830efd 247 uint32_t chain_len = 0;
abc490a1 248
11519af6
MD
249 /*
250 * iter_prev points to the non-removed node prior to the
251 * insert location.
11519af6 252 */
49c2e2d6 253 iter_prev = rcu_dereference(t->tbl[hash & (t->size - 1)]);
11519af6 254 /* We can always skip the dummy node initially */
273399de 255 iter = rcu_dereference(iter_prev->next);
abc490a1
MD
256 assert(iter_prev->reverse_hash <= node->reverse_hash);
257 for (;;) {
273399de
MD
258 if (unlikely(!iter))
259 goto insert;
11519af6 260 if (clear_flag(iter)->reverse_hash > node->reverse_hash)
273399de
MD
261 goto insert;
262 next = rcu_dereference(clear_flag(iter)->next);
263 if (is_removed(next))
9dba85be 264 goto gc_node;
e43f23f8
MD
265 if (unique
266 && !clear_flag(iter)->dummy
267 && !ht->compare_fct(node->key, node->key_len,
268 clear_flag(iter)->key,
269 clear_flag(iter)->key_len))
270 return -EEXIST;
11519af6
MD
271 /* Only account for identical reverse hash once */
272 if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash)
273 check_resize(ht, t, ++chain_len);
274 iter_prev = clear_flag(iter);
273399de 275 iter = next;
abc490a1 276 }
273399de 277 insert:
7ec59d3b 278 assert(node != clear_flag(iter));
11519af6 279 assert(!is_removed(iter_prev));
f000907d 280 assert(iter_prev != node);
11519af6 281 node->next = iter;
273399de
MD
282 if (uatomic_cmpxchg(&iter_prev->next, iter,
283 node) != iter)
284 continue; /* retry */
11519af6 285 else
273399de 286 goto gc_end;
9dba85be
MD
287 gc_node:
288 assert(!is_removed(iter));
289 (void) uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next));
273399de 290 /* retry */
464a1ec9 291 }
273399de
MD
292gc_end:
293 /* Garbage collect logically removed nodes in the bucket */
49c2e2d6 294 dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
273399de 295 _ht_gc_bucket(dummy, node);
3eca1b8c 296 return 0;
abc490a1 297}
464a1ec9 298
abc490a1
MD
299static
300int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
301{
273399de 302 struct rcu_ht_node *dummy, *next, *old;
abc490a1 303 int flagged = 0;
49c2e2d6 304 unsigned long hash;
5e28c532 305
7ec59d3b
MD
306 /* logically delete the node */
307 old = rcu_dereference(node->next);
308 do {
309 next = old;
310 if (is_removed(next))
311 goto end;
273399de 312 assert(!node->dummy);
7ec59d3b
MD
313 old = uatomic_cmpxchg(&node->next, next,
314 flag_removed(next));
315 } while (old != next);
316
317 /* We performed the (logical) deletion. */
318 flagged = 1;
319
320 /*
321 * Ensure that the node is not visible to readers anymore: lookup for
273399de
MD
322 * the node, and remove it (along with any other logically removed node)
323 * if found.
11519af6 324 */
49c2e2d6
MD
325 hash = bit_reverse_ulong(node->reverse_hash);
326 dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
273399de 327 _ht_gc_bucket(dummy, node);
2ed95849 328end:
11519af6
MD
329 /*
330 * Only the flagging action indicated that we (and no other)
331 * removed the node from the hash.
332 */
7ec59d3b
MD
333 if (flagged) {
334 assert(is_removed(rcu_dereference(node->next)));
11519af6 335 return 0;
7ec59d3b 336 } else
11519af6 337 return -ENOENT;
abc490a1 338}
2ed95849 339
abc490a1
MD
340static
341void init_table(struct rcu_ht *ht, struct rcu_table *t,
342 unsigned long first, unsigned long len)
343{
344 unsigned long i, end;
345
346 end = first + len;
347 for (i = first; i < end; i++) {
348 /* Update table size when power of two */
349 if (i != 0 && !(i & (i - 1)))
350 t->size = i;
351 t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
352 t->tbl[i]->dummy = 1;
abc490a1 353 t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
3eca1b8c 354 (void) _ht_add(ht, t, t->tbl[i], 0);
abc490a1 355 }
f9830efd 356 t->resize_target = t->size = end;
11519af6 357 t->resize_initiated = 0;
2ed95849
MD
358}
359
abc490a1 360struct rcu_ht *ht_new(ht_hash_fct hash_fct,
732ad076
MD
361 ht_compare_fct compare_fct,
362 unsigned long hash_seed,
abc490a1
MD
363 unsigned long init_size,
364 void (*ht_call_rcu)(struct rcu_head *head,
365 void (*func)(struct rcu_head *head)))
366{
367 struct rcu_ht *ht;
368
369 ht = calloc(1, sizeof(struct rcu_ht));
370 ht->hash_fct = hash_fct;
732ad076
MD
371 ht->compare_fct = compare_fct;
372 ht->hash_seed = hash_seed;
f000907d 373 ht->ht_call_rcu = ht_call_rcu;
abc490a1
MD
374 /* this mutex should not nest in read-side C.S. */
375 pthread_mutex_init(&ht->resize_mutex, NULL);
376 ht->t = calloc(1, sizeof(struct rcu_table)
377 + (max(init_size, 1) * sizeof(struct rcu_ht_node *)));
378 ht->t->size = 0;
f000907d 379 pthread_mutex_lock(&ht->resize_mutex);
abc490a1 380 init_table(ht, ht->t, 0, max(init_size, 1));
f000907d 381 pthread_mutex_unlock(&ht->resize_mutex);
abc490a1
MD
382 return ht;
383}
384
732ad076 385struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
2ed95849 386{
395270b6 387 struct rcu_table *t;
abc490a1
MD
388 struct rcu_ht_node *node;
389 unsigned long hash, reverse_hash;
2ed95849 390
732ad076 391 hash = ht->hash_fct(key, key_len, ht->hash_seed);
abc490a1 392 reverse_hash = bit_reverse_ulong(hash);
464a1ec9 393
395270b6 394 t = rcu_dereference(ht->t);
abc490a1 395 node = rcu_dereference(t->tbl[hash & (t->size - 1)]);
2ed95849 396 for (;;) {
abc490a1
MD
397 if (unlikely(!node))
398 break;
dd4505e0 399 if (unlikely(node->reverse_hash > reverse_hash)) {
abc490a1
MD
400 node = NULL;
401 break;
2ed95849 402 }
49c2e2d6
MD
403 if (likely(!is_removed(rcu_dereference(node->next)))
404 && !node->dummy
405 && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
273399de 406 break;
2ed95849 407 }
abc490a1 408 node = clear_flag(rcu_dereference(node->next));
2ed95849 409 }
273399de 410 assert(!node || !node->dummy);
abc490a1
MD
411 return node;
412}
e0ba718a 413
f000907d 414void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
abc490a1
MD
415{
416 struct rcu_table *t;
49c2e2d6 417 unsigned long hash;
ab7d5fc6 418
49c2e2d6
MD
419 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
420 node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
2ed95849 421
abc490a1 422 t = rcu_dereference(ht->t);
3eca1b8c
MD
423 (void) _ht_add(ht, t, node, 0);
424}
425
426int ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
427{
428 struct rcu_table *t;
49c2e2d6 429 unsigned long hash;
3eca1b8c 430
49c2e2d6
MD
431 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
432 node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
3eca1b8c
MD
433
434 t = rcu_dereference(ht->t);
435 return _ht_add(ht, t, node, 1);
2ed95849
MD
436}
437
abc490a1 438int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
2ed95849 439{
abc490a1
MD
440 struct rcu_table *t;
441
442 t = rcu_dereference(ht->t);
abc490a1 443 return _ht_remove(ht, t, node);
2ed95849 444}
ab7d5fc6 445
abc490a1
MD
446static
447int ht_delete_dummy(struct rcu_ht *ht)
674f7a69 448{
395270b6 449 struct rcu_table *t;
abc490a1
MD
450 struct rcu_ht_node *node;
451 unsigned long i;
674f7a69 452
abc490a1
MD
453 t = ht->t;
454 /* Check that the table is empty */
455 node = t->tbl[0];
456 do {
457 if (!node->dummy)
458 return -EPERM;
459 node = node->next;
273399de 460 assert(!is_removed(node));
abc490a1
MD
461 } while (node);
462 /* Internal sanity check: all nodes left should be dummy */
395270b6 463 for (i = 0; i < t->size; i++) {
abc490a1
MD
464 assert(t->tbl[i]->dummy);
465 free(t->tbl[i]);
674f7a69 466 }
abc490a1 467 return 0;
674f7a69
MD
468}
469
470/*
471 * Should only be called when no more concurrent readers nor writers can
472 * possibly access the table.
473 */
5e28c532 474int ht_destroy(struct rcu_ht *ht)
674f7a69 475{
5e28c532
MD
476 int ret;
477
abc490a1
MD
478 ret = ht_delete_dummy(ht);
479 if (ret)
480 return ret;
395270b6 481 free(ht->t);
674f7a69 482 free(ht);
5e28c532 483 return ret;
674f7a69
MD
484}
485
273399de
MD
486void ht_count_nodes(struct rcu_ht *ht,
487 unsigned long *count,
488 unsigned long *removed)
489{
490 struct rcu_table *t;
491 struct rcu_ht_node *node, *next;
492
493 *count = 0;
494 *removed = 0;
495
496 t = rcu_dereference(ht->t);
497 /* Check that the table is empty */
498 node = rcu_dereference(t->tbl[0]);
499 do {
500 next = rcu_dereference(node->next);
501 if (is_removed(next)) {
502 assert(!node->dummy);
503 (*removed)++;
504 } else if (!node->dummy)
505 (*count)++;
506 node = clear_flag(next);
507 } while (node);
508}
509
abc490a1
MD
510static
511void ht_free_table_cb(struct rcu_head *head)
512{
513 struct rcu_table *t =
514 caa_container_of(head, struct rcu_table, head);
515 free(t);
516}
517
518/* called with resize mutex held */
519static
520void _do_ht_resize(struct rcu_ht *ht)
464a1ec9 521{
abc490a1 522 unsigned long new_size, old_size;
395270b6 523 struct rcu_table *new_t, *old_t;
464a1ec9 524
395270b6
MD
525 old_t = ht->t;
526 old_size = old_t->size;
464a1ec9 527
f9830efd
MD
528 new_size = CMM_LOAD_SHARED(old_t->resize_target);
529 dbg_printf("rculfhash: resize from %lu to %lu buckets\n",
530 old_size, new_size);
abc490a1 531 if (old_size == new_size)
464a1ec9 532 return;
f000907d 533 new_t = malloc(sizeof(struct rcu_table)
abc490a1 534 + (new_size * sizeof(struct rcu_ht_node *)));
f000907d
MD
535 assert(new_size > old_size);
536 memcpy(&new_t->tbl, &old_t->tbl,
537 old_size * sizeof(struct rcu_ht_node *));
538 init_table(ht, new_t, old_size, new_size - old_size);
f000907d
MD
539 /* Changing table and size atomically wrt lookups */
540 rcu_assign_pointer(ht->t, new_t);
541 ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
464a1ec9
MD
542}
543
abc490a1 544static
f9830efd
MD
545unsigned long resize_target_update(struct rcu_table *t,
546 int growth_order)
464a1ec9 547{
f9830efd
MD
548 return _uatomic_max(&t->resize_target,
549 t->size << growth_order);
464a1ec9
MD
550}
551
464a1ec9
MD
552void ht_resize(struct rcu_ht *ht, int growth)
553{
f9830efd
MD
554 struct rcu_table *t = rcu_dereference(ht->t);
555 unsigned long target_size;
556
557 target_size = resize_target_update(t, growth);
558 if (t->size < target_size) {
11519af6 559 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd
MD
560 pthread_mutex_lock(&ht->resize_mutex);
561 _do_ht_resize(ht);
562 pthread_mutex_unlock(&ht->resize_mutex);
563 }
abc490a1 564}
464a1ec9 565
abc490a1
MD
566static
567void do_resize_cb(struct rcu_head *head)
568{
569 struct rcu_resize_work *work =
570 caa_container_of(head, struct rcu_resize_work, head);
571 struct rcu_ht *ht = work->ht;
572
573 pthread_mutex_lock(&ht->resize_mutex);
574 _do_ht_resize(ht);
575 pthread_mutex_unlock(&ht->resize_mutex);
576 free(work);
464a1ec9
MD
577}
578
abc490a1 579static
f000907d 580void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth)
ab7d5fc6 581{
abc490a1 582 struct rcu_resize_work *work;
f9830efd 583 unsigned long target_size;
abc490a1 584
f9830efd 585 target_size = resize_target_update(t, growth);
11519af6 586 if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
f9830efd
MD
587 work = malloc(sizeof(*work));
588 work->ht = ht;
589 ht->ht_call_rcu(&work->head, do_resize_cb);
11519af6 590 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd 591 }
ab7d5fc6 592}
This page took 0.081029 seconds and 4 git commands to generate.