RCU hash table API documentation
[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
e753ff5a
MD
23/*
24 * Based on the following articles:
25 * - Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free
26 * extensible hash tables. J. ACM 53, 3 (May 2006), 379-405.
27 * - Michael, M. M. High performance dynamic lock-free hash tables
28 * and list-based sets. In Proceedings of the fourteenth annual ACM
29 * symposium on Parallel algorithms and architectures, ACM Press,
30 * (2002), 73-82.
31 *
32 * Some specificities of this Lock-Free Expandable RCU Hash Table
33 * implementation:
34 *
35 * - RCU read-side critical section allows readers to perform hash
36 * table lookups and use the returned objects safely by delaying
37 * memory reclaim of a grace period.
38 * - Add and remove operations are lock-free, and do not need to
39 * allocate memory. They need to be executed within RCU read-side
40 * critical section to ensure the objects they read are valid and to
41 * deal with the cmpxchg ABA problem.
42 * - add and add_unique operations are supported. add_unique checks if
43 * the node key already exists in the hash table. It ensures no key
44 * duplicata exists.
45 * - The resize operation executes concurrently with add/remove/lookup.
46 * - Hash table nodes are contained within a split-ordered list. This
47 * list is ordered by incrementing reversed-bits-hash value.
48 * - An index of dummy nodes is kept. These dummy nodes are the hash
49 * table "buckets", and they are also chained together in the
50 * split-ordered list, which allows recursive expansion.
51 * - The resize operation only allows expanding the hash table.
52 * It is triggered either through an API call or automatically by
53 * detecting long chains in the add operation.
54 * - Resize operation initiated by long chain detection is executed by a
55 * call_rcu thread, which keeps lock-freedom of add and remove.
56 * - Resize operations are protected by a mutex.
57 * - The removal operation is split in two parts: first, a "removed"
58 * flag is set in the next pointer within the node to remove. Then,
59 * a "garbage collection" is performed in the bucket containing the
60 * removed node (from the start of the bucket up to the removed node).
61 * All encountered nodes with "removed" flag set in their next
62 * pointers are removed from the linked-list. If the cmpxchg used for
63 * removal fails (due to concurrent garbage-collection or concurrent
64 * add), we retry from the beginning of the bucket. This ensures that
65 * the node with "removed" flag set is removed from the hash table
66 * (not visible to lookups anymore) before the RCU read-side critical
67 * section held across removal ends. Furthermore, this ensures that
68 * the node with "removed" flag set is removed from the linked-list
69 * before its memory is reclaimed. Only the thread which removal
70 * successfully set the "removed" flag (with a cmpxchg) into a node's
71 * next pointer is considered to have succeeded its removal (and thus
72 * owns the node to reclaim). Because we garbage-collect starting from
73 * an invariant node (the start-of-bucket dummy node) up to the
74 * "removed" node (or find a reverse-hash that is higher), we are sure
75 * that a successful traversal of the chain leads to a chain that is
76 * present in the linked-list (the start node is never removed) and
77 * that is does not contain the "removed" node anymore, even if
78 * concurrent delete/add operations are changing the structure of the
79 * list concurrently.
29e669f6
MD
80 * - The add operation performs gargage collection of buckets if it
81 * encounters nodes with removed flag set in the bucket where it wants
82 * to add its new node. This ensures lock-freedom of add operation by
83 * helping the remover unlink nodes from the list rather than to wait
84 * for it do to so.
e753ff5a
MD
85 * - A RCU "order table" indexed by log2(hash index) is copied and
86 * expanded by the resize operation. This order table allows finding
87 * the "dummy node" tables.
88 * - There is one dummy node table per hash index order. The size of
89 * each dummy node table is half the number of hashes contained in
90 * this order.
91 * - call_rcu is used to garbage-collect the old order table.
92 * - The per-order dummy node tables contain a compact version of the
93 * hash table nodes. These tables are invariant after they are
94 * populated into the hash table.
95 */
96
2ed95849
MD
97#define _LGPL_SOURCE
98#include <stdlib.h>
e0ba718a
MD
99#include <errno.h>
100#include <assert.h>
101#include <stdio.h>
abc490a1 102#include <stdint.h>
f000907d 103#include <string.h>
e0ba718a 104
2ed95849 105#include <urcu.h>
abc490a1 106#include <urcu-call-rcu.h>
a42cc659
MD
107#include <urcu/arch.h>
108#include <urcu/uatomic.h>
674f7a69 109#include <urcu/jhash.h>
a42cc659 110#include <urcu/compiler.h>
abc490a1 111#include <urcu/rculfhash.h>
5e28c532 112#include <stdio.h>
464a1ec9 113#include <pthread.h>
44395fb7 114
f9830efd 115#ifdef DEBUG
f0c29ed7 116#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
f9830efd 117#else
e753ff5a 118#define dbg_printf(fmt, args...)
f9830efd
MD
119#endif
120
01370f0b
MD
121#define CHAIN_LEN_TARGET 4
122#define CHAIN_LEN_RESIZE_THRESHOLD 8
2ed95849 123
abc490a1
MD
124#ifndef max
125#define max(a, b) ((a) > (b) ? (a) : (b))
126#endif
2ed95849 127
d95bd160
MD
128/*
129 * The removed flag needs to be updated atomically with the pointer.
130 * The dummy flag does not require to be updated atomically with the
131 * pointer, but it is added as a pointer low bit flag to save space.
132 */
d37166c6 133#define REMOVED_FLAG (1UL << 0)
f5596c94
MD
134#define DUMMY_FLAG (1UL << 1)
135#define FLAGS_MASK ((1UL << 2) - 1)
d37166c6 136
395270b6 137struct rcu_table {
abc490a1 138 unsigned long size; /* always a power of 2 */
f9830efd 139 unsigned long resize_target;
11519af6 140 int resize_initiated;
abc490a1 141 struct rcu_head head;
24365af7 142 struct _rcu_ht_node *tbl[0];
395270b6
MD
143};
144
2ed95849 145struct rcu_ht {
395270b6 146 struct rcu_table *t; /* shared */
2ed95849 147 ht_hash_fct hash_fct;
732ad076
MD
148 ht_compare_fct compare_fct;
149 unsigned long hash_seed;
464a1ec9 150 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
33c7c748 151 unsigned int in_progress_resize, in_progress_destroy;
abc490a1
MD
152 void (*ht_call_rcu)(struct rcu_head *head,
153 void (*func)(struct rcu_head *head));
2ed95849
MD
154};
155
abc490a1
MD
156struct rcu_resize_work {
157 struct rcu_head head;
2ed95849 158 struct rcu_ht *ht;
abc490a1 159};
2ed95849 160
abc490a1
MD
161/*
162 * Algorithm to reverse bits in a word by lookup table, extended to
163 * 64-bit words.
f9830efd 164 * Source:
abc490a1 165 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
f9830efd 166 * Originally from Public Domain.
abc490a1
MD
167 */
168
169static const uint8_t BitReverseTable256[256] =
2ed95849 170{
abc490a1
MD
171#define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
172#define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
173#define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
174 R6(0), R6(2), R6(1), R6(3)
175};
176#undef R2
177#undef R4
178#undef R6
2ed95849 179
abc490a1
MD
180static
181uint8_t bit_reverse_u8(uint8_t v)
182{
183 return BitReverseTable256[v];
184}
ab7d5fc6 185
abc490a1
MD
186static __attribute__((unused))
187uint32_t bit_reverse_u32(uint32_t v)
188{
189 return ((uint32_t) bit_reverse_u8(v) << 24) |
190 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
191 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
192 ((uint32_t) bit_reverse_u8(v >> 24));
2ed95849
MD
193}
194
abc490a1
MD
195static __attribute__((unused))
196uint64_t bit_reverse_u64(uint64_t v)
2ed95849 197{
abc490a1
MD
198 return ((uint64_t) bit_reverse_u8(v) << 56) |
199 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
200 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
201 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
202 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
203 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
204 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
205 ((uint64_t) bit_reverse_u8(v >> 56));
206}
207
208static
209unsigned long bit_reverse_ulong(unsigned long v)
210{
211#if (CAA_BITS_PER_LONG == 32)
212 return bit_reverse_u32(v);
213#else
214 return bit_reverse_u64(v);
215#endif
216}
217
f9830efd 218/*
24365af7
MD
219 * fls: returns the position of the most significant bit.
220 * Returns 0 if no bit is set, else returns the position of the most
221 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
f9830efd 222 */
24365af7
MD
223#if defined(__i386) || defined(__x86_64)
224static inline
225unsigned int fls_u32(uint32_t x)
f9830efd 226{
24365af7
MD
227 int r;
228
229 asm("bsrl %1,%0\n\t"
230 "jnz 1f\n\t"
231 "movl $-1,%0\n\t"
232 "1:\n\t"
233 : "=r" (r) : "rm" (x));
234 return r + 1;
235}
236#define HAS_FLS_U32
237#endif
238
239#if defined(__x86_64)
240static inline
241unsigned int fls_u64(uint64_t x)
242{
243 long r;
244
245 asm("bsrq %1,%0\n\t"
246 "jnz 1f\n\t"
247 "movq $-1,%0\n\t"
248 "1:\n\t"
249 : "=r" (r) : "rm" (x));
250 return r + 1;
251}
252#define HAS_FLS_U64
253#endif
254
255#ifndef HAS_FLS_U64
256static __attribute__((unused))
257unsigned int fls_u64(uint64_t x)
258{
259 unsigned int r = 64;
260
261 if (!x)
262 return 0;
263
264 if (!(x & 0xFFFFFFFF00000000ULL)) {
265 x <<= 32;
266 r -= 32;
267 }
268 if (!(x & 0xFFFF000000000000ULL)) {
269 x <<= 16;
270 r -= 16;
271 }
272 if (!(x & 0xFF00000000000000ULL)) {
273 x <<= 8;
274 r -= 8;
275 }
276 if (!(x & 0xF000000000000000ULL)) {
277 x <<= 4;
278 r -= 4;
279 }
280 if (!(x & 0xC000000000000000ULL)) {
281 x <<= 2;
282 r -= 2;
283 }
284 if (!(x & 0x8000000000000000ULL)) {
285 x <<= 1;
286 r -= 1;
287 }
288 return r;
289}
290#endif
291
292#ifndef HAS_FLS_U32
293static __attribute__((unused))
294unsigned int fls_u32(uint32_t x)
295{
296 unsigned int r = 32;
f9830efd 297
24365af7
MD
298 if (!x)
299 return 0;
300 if (!(x & 0xFFFF0000U)) {
301 x <<= 16;
302 r -= 16;
303 }
304 if (!(x & 0xFF000000U)) {
305 x <<= 8;
306 r -= 8;
307 }
308 if (!(x & 0xF0000000U)) {
309 x <<= 4;
310 r -= 4;
311 }
312 if (!(x & 0xC0000000U)) {
313 x <<= 2;
314 r -= 2;
315 }
316 if (!(x & 0x80000000U)) {
317 x <<= 1;
318 r -= 1;
319 }
320 return r;
321}
322#endif
323
324unsigned int fls_ulong(unsigned long x)
f9830efd 325{
24365af7
MD
326#if (CAA_BITS_PER_lONG == 32)
327 return fls_u32(x);
328#else
329 return fls_u64(x);
330#endif
331}
f9830efd 332
24365af7
MD
333int get_count_order_u32(uint32_t x)
334{
335 int order;
336
337 order = fls_u32(x) - 1;
338 if (x & (x - 1))
339 order++;
340 return order;
341}
342
343int get_count_order_ulong(unsigned long x)
344{
345 int order;
346
347 order = fls_ulong(x) - 1;
348 if (x & (x - 1))
349 order++;
350 return order;
f9830efd
MD
351}
352
353static
354void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth);
355
356static
357void check_resize(struct rcu_ht *ht, struct rcu_table *t,
358 uint32_t chain_len)
359{
24365af7 360 if (chain_len > 100)
f0c29ed7 361 dbg_printf("WARNING: large chain length: %u.\n",
24365af7 362 chain_len);
3390d470
MD
363 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
364 ht_resize_lazy(ht, t,
01370f0b 365 get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1)));
f9830efd
MD
366}
367
abc490a1
MD
368static
369struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
370{
d37166c6 371 return (struct rcu_ht_node *) (((unsigned long) node) & ~FLAGS_MASK);
abc490a1
MD
372}
373
374static
375int is_removed(struct rcu_ht_node *node)
376{
d37166c6 377 return ((unsigned long) node) & REMOVED_FLAG;
abc490a1
MD
378}
379
380static
381struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
382{
d37166c6 383 return (struct rcu_ht_node *) (((unsigned long) node) | REMOVED_FLAG);
abc490a1
MD
384}
385
f5596c94
MD
386static
387int is_dummy(struct rcu_ht_node *node)
388{
389 return ((unsigned long) node) & DUMMY_FLAG;
390}
391
392static
393struct rcu_ht_node *flag_dummy(struct rcu_ht_node *node)
394{
395 return (struct rcu_ht_node *) (((unsigned long) node) | DUMMY_FLAG);
396}
397
abc490a1 398static
f9830efd 399unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
abc490a1
MD
400{
401 unsigned long old1, old2;
402
403 old1 = uatomic_read(ptr);
404 do {
405 old2 = old1;
406 if (old2 >= v)
f9830efd 407 return old2;
abc490a1 408 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
f9830efd 409 return v;
abc490a1
MD
410}
411
273399de
MD
412/*
413 * Remove all logically deleted nodes from a bucket up to a certain node key.
414 */
415static
416void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
417{
f5596c94 418 struct rcu_ht_node *iter_prev, *iter, *next, *new_next;
273399de
MD
419
420 for (;;) {
421 iter_prev = dummy;
422 /* We can always skip the dummy node initially */
cc4fcb10
MD
423 iter = rcu_dereference(iter_prev->p.next);
424 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
273399de 425 for (;;) {
a2974903 426 if (unlikely(!clear_flag(iter)))
479c8a32 427 return;
76412f24 428 if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
273399de 429 return;
cc4fcb10 430 next = rcu_dereference(clear_flag(iter)->p.next);
76412f24 431 if (likely(is_removed(next)))
273399de 432 break;
b453eae1 433 iter_prev = clear_flag(iter);
273399de
MD
434 iter = next;
435 }
436 assert(!is_removed(iter));
f5596c94
MD
437 if (is_dummy(iter))
438 new_next = flag_dummy(clear_flag(next));
439 else
440 new_next = clear_flag(next);
441 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de
MD
442 }
443}
444
abc490a1 445static
18117871 446struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t,
f5596c94 447 struct rcu_ht_node *node, int unique, int dummy)
abc490a1 448{
f5596c94
MD
449 struct rcu_ht_node *iter_prev, *iter, *next, *new_node, *new_next,
450 *dummy_node;
24365af7
MD
451 struct _rcu_ht_node *lookup;
452 unsigned long hash, index, order;
abc490a1 453
18117871 454 if (!t->size) {
f5596c94
MD
455 assert(dummy);
456 node->p.next = flag_dummy(NULL);
18117871
MD
457 return node; /* Initial first add (head) */
458 }
cc4fcb10 459 hash = bit_reverse_ulong(node->p.reverse_hash);
abc490a1 460 for (;;) {
f9830efd 461 uint32_t chain_len = 0;
abc490a1 462
11519af6
MD
463 /*
464 * iter_prev points to the non-removed node prior to the
465 * insert location.
11519af6 466 */
24365af7
MD
467 index = hash & (t->size - 1);
468 order = get_count_order_ulong(index + 1);
469 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
470 iter_prev = (struct rcu_ht_node *) lookup;
11519af6 471 /* We can always skip the dummy node initially */
cc4fcb10
MD
472 iter = rcu_dereference(iter_prev->p.next);
473 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
abc490a1 474 for (;;) {
a2974903 475 if (unlikely(!clear_flag(iter)))
273399de 476 goto insert;
76412f24 477 if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
273399de 478 goto insert;
cc4fcb10 479 next = rcu_dereference(clear_flag(iter)->p.next);
76412f24 480 if (unlikely(is_removed(next)))
9dba85be 481 goto gc_node;
e43f23f8 482 if (unique
1b81fe1a 483 && !is_dummy(next)
e43f23f8
MD
484 && !ht->compare_fct(node->key, node->key_len,
485 clear_flag(iter)->key,
486 clear_flag(iter)->key_len))
18117871 487 return clear_flag(iter);
11519af6 488 /* Only account for identical reverse hash once */
24365af7
MD
489 if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
490 && !is_dummy(next))
11519af6
MD
491 check_resize(ht, t, ++chain_len);
492 iter_prev = clear_flag(iter);
273399de 493 iter = next;
abc490a1 494 }
273399de 495 insert:
7ec59d3b 496 assert(node != clear_flag(iter));
11519af6 497 assert(!is_removed(iter_prev));
f000907d 498 assert(iter_prev != node);
f5596c94 499 if (!dummy)
1b81fe1a 500 node->p.next = clear_flag(iter);
f5596c94 501 else
1b81fe1a 502 node->p.next = flag_dummy(clear_flag(iter));
f5596c94
MD
503 if (is_dummy(iter))
504 new_node = flag_dummy(node);
505 else
506 new_node = node;
cc4fcb10 507 if (uatomic_cmpxchg(&iter_prev->p.next, iter,
f5596c94 508 new_node) != iter)
273399de 509 continue; /* retry */
11519af6 510 else
273399de 511 goto gc_end;
9dba85be
MD
512 gc_node:
513 assert(!is_removed(iter));
f5596c94
MD
514 if (is_dummy(iter))
515 new_next = flag_dummy(clear_flag(next));
516 else
517 new_next = clear_flag(next);
518 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de 519 /* retry */
464a1ec9 520 }
273399de
MD
521gc_end:
522 /* Garbage collect logically removed nodes in the bucket */
24365af7
MD
523 index = hash & (t->size - 1);
524 order = get_count_order_ulong(index + 1);
525 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
526 dummy_node = (struct rcu_ht_node *) lookup;
f5596c94 527 _ht_gc_bucket(dummy_node, node);
18117871 528 return node;
abc490a1 529}
464a1ec9 530
abc490a1
MD
531static
532int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
533{
273399de 534 struct rcu_ht_node *dummy, *next, *old;
24365af7 535 struct _rcu_ht_node *lookup;
abc490a1 536 int flagged = 0;
24365af7 537 unsigned long hash, index, order;
5e28c532 538
7ec59d3b 539 /* logically delete the node */
cc4fcb10 540 old = rcu_dereference(node->p.next);
7ec59d3b
MD
541 do {
542 next = old;
76412f24 543 if (unlikely(is_removed(next)))
7ec59d3b 544 goto end;
1b81fe1a 545 assert(!is_dummy(next));
cc4fcb10 546 old = uatomic_cmpxchg(&node->p.next, next,
7ec59d3b
MD
547 flag_removed(next));
548 } while (old != next);
549
550 /* We performed the (logical) deletion. */
551 flagged = 1;
552
553 /*
554 * Ensure that the node is not visible to readers anymore: lookup for
273399de
MD
555 * the node, and remove it (along with any other logically removed node)
556 * if found.
11519af6 557 */
cc4fcb10 558 hash = bit_reverse_ulong(node->p.reverse_hash);
24365af7
MD
559 index = hash & (t->size - 1);
560 order = get_count_order_ulong(index + 1);
561 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
562 dummy = (struct rcu_ht_node *) lookup;
273399de 563 _ht_gc_bucket(dummy, node);
2ed95849 564end:
11519af6
MD
565 /*
566 * Only the flagging action indicated that we (and no other)
567 * removed the node from the hash.
568 */
7ec59d3b 569 if (flagged) {
cc4fcb10 570 assert(is_removed(rcu_dereference(node->p.next)));
11519af6 571 return 0;
7ec59d3b 572 } else
11519af6 573 return -ENOENT;
abc490a1 574}
2ed95849 575
abc490a1
MD
576static
577void init_table(struct rcu_ht *ht, struct rcu_table *t,
24365af7
MD
578 unsigned long first_order, unsigned long len_order)
579{
580 unsigned long i, end_order;
581
f0c29ed7 582 dbg_printf("init table: first_order %lu end_order %lu\n",
24365af7
MD
583 first_order, first_order + len_order);
584 end_order = first_order + len_order;
585 t->size = !first_order ? 0 : (1UL << (first_order - 1));
586 for (i = first_order; i < end_order; i++) {
587 unsigned long j, len;
588
589 len = !i ? 1 : 1UL << (i - 1);
f0c29ed7 590 dbg_printf("init order %lu len: %lu\n", i, len);
24365af7
MD
591 t->tbl[i] = calloc(len, sizeof(struct _rcu_ht_node));
592 for (j = 0; j < len; j++) {
f0c29ed7 593 dbg_printf("init entry: i %lu j %lu hash %lu\n",
24365af7
MD
594 i, j, !i ? 0 : (1UL << (i - 1)) + j);
595 struct rcu_ht_node *new_node =
596 (struct rcu_ht_node *) &t->tbl[i][j];
597 new_node->p.reverse_hash =
598 bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
599 (void) _ht_add(ht, t, new_node, 0, 1);
33c7c748
MD
600 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
601 break;
24365af7
MD
602 }
603 /* Update table size */
604 t->size = !i ? 1 : (1UL << i);
f0c29ed7 605 dbg_printf("init new size: %lu\n", t->size);
33c7c748
MD
606 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
607 break;
abc490a1 608 }
24365af7 609 t->resize_target = t->size;
11519af6 610 t->resize_initiated = 0;
2ed95849
MD
611}
612
abc490a1 613struct rcu_ht *ht_new(ht_hash_fct hash_fct,
732ad076
MD
614 ht_compare_fct compare_fct,
615 unsigned long hash_seed,
abc490a1
MD
616 unsigned long init_size,
617 void (*ht_call_rcu)(struct rcu_head *head,
618 void (*func)(struct rcu_head *head)))
619{
620 struct rcu_ht *ht;
24365af7 621 unsigned long order;
abc490a1
MD
622
623 ht = calloc(1, sizeof(struct rcu_ht));
624 ht->hash_fct = hash_fct;
732ad076
MD
625 ht->compare_fct = compare_fct;
626 ht->hash_seed = hash_seed;
f000907d 627 ht->ht_call_rcu = ht_call_rcu;
848d4088 628 ht->in_progress_resize = 0;
abc490a1
MD
629 /* this mutex should not nest in read-side C.S. */
630 pthread_mutex_init(&ht->resize_mutex, NULL);
24365af7 631 order = get_count_order_ulong(max(init_size, 1)) + 1;
abc490a1 632 ht->t = calloc(1, sizeof(struct rcu_table)
24365af7 633 + (order * sizeof(struct _rcu_ht_node *)));
abc490a1 634 ht->t->size = 0;
f000907d 635 pthread_mutex_lock(&ht->resize_mutex);
24365af7 636 init_table(ht, ht->t, 0, order);
f000907d 637 pthread_mutex_unlock(&ht->resize_mutex);
abc490a1
MD
638 return ht;
639}
640
732ad076 641struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
2ed95849 642{
395270b6 643 struct rcu_table *t;
1b81fe1a 644 struct rcu_ht_node *node, *next;
24365af7
MD
645 struct _rcu_ht_node *lookup;
646 unsigned long hash, reverse_hash, index, order;
2ed95849 647
732ad076 648 hash = ht->hash_fct(key, key_len, ht->hash_seed);
abc490a1 649 reverse_hash = bit_reverse_ulong(hash);
464a1ec9 650
395270b6 651 t = rcu_dereference(ht->t);
24365af7
MD
652 index = hash & (t->size - 1);
653 order = get_count_order_ulong(index + 1);
654 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
f0c29ed7 655 dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n",
24365af7
MD
656 hash, index, order, index & ((1UL << (order - 1)) - 1));
657 node = (struct rcu_ht_node *) lookup;
2ed95849 658 for (;;) {
abc490a1
MD
659 if (unlikely(!node))
660 break;
cc4fcb10 661 if (unlikely(node->p.reverse_hash > reverse_hash)) {
abc490a1
MD
662 node = NULL;
663 break;
2ed95849 664 }
1b81fe1a
MD
665 next = rcu_dereference(node->p.next);
666 if (likely(!is_removed(next))
667 && !is_dummy(next)
49c2e2d6 668 && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
273399de 669 break;
2ed95849 670 }
1b81fe1a 671 node = clear_flag(next);
2ed95849 672 }
1b81fe1a 673 assert(!node || !is_dummy(rcu_dereference(node->p.next)));
abc490a1
MD
674 return node;
675}
e0ba718a 676
f000907d 677void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
abc490a1
MD
678{
679 struct rcu_table *t;
49c2e2d6 680 unsigned long hash;
ab7d5fc6 681
49c2e2d6 682 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 683 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
2ed95849 684
abc490a1 685 t = rcu_dereference(ht->t);
f5596c94 686 (void) _ht_add(ht, t, node, 0, 0);
3eca1b8c
MD
687}
688
18117871 689struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
3eca1b8c
MD
690{
691 struct rcu_table *t;
49c2e2d6 692 unsigned long hash;
3eca1b8c 693
49c2e2d6 694 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 695 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
3eca1b8c
MD
696
697 t = rcu_dereference(ht->t);
f5596c94 698 return _ht_add(ht, t, node, 1, 0);
2ed95849
MD
699}
700
abc490a1 701int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
2ed95849 702{
abc490a1
MD
703 struct rcu_table *t;
704
705 t = rcu_dereference(ht->t);
abc490a1 706 return _ht_remove(ht, t, node);
2ed95849 707}
ab7d5fc6 708
abc490a1
MD
709static
710int ht_delete_dummy(struct rcu_ht *ht)
674f7a69 711{
395270b6 712 struct rcu_table *t;
abc490a1 713 struct rcu_ht_node *node;
24365af7
MD
714 struct _rcu_ht_node *lookup;
715 unsigned long order, i;
674f7a69 716
abc490a1
MD
717 t = ht->t;
718 /* Check that the table is empty */
24365af7
MD
719 lookup = &t->tbl[0][0];
720 node = (struct rcu_ht_node *) lookup;
abc490a1 721 do {
1b81fe1a
MD
722 node = clear_flag(node)->p.next;
723 if (!is_dummy(node))
abc490a1 724 return -EPERM;
273399de 725 assert(!is_removed(node));
a2974903 726 } while (clear_flag(node));
abc490a1 727 /* Internal sanity check: all nodes left should be dummy */
24365af7
MD
728 for (order = 0; order < get_count_order_ulong(t->size) + 1; order++) {
729 unsigned long len;
730
731 len = !order ? 1 : 1UL << (order - 1);
732 for (i = 0; i < len; i++) {
f0c29ed7 733 dbg_printf("delete order %lu i %lu hash %lu\n",
24365af7
MD
734 order, i,
735 bit_reverse_ulong(t->tbl[order][i].reverse_hash));
736 assert(is_dummy(t->tbl[order][i].next));
737 }
738 free(t->tbl[order]);
674f7a69 739 }
abc490a1 740 return 0;
674f7a69
MD
741}
742
743/*
744 * Should only be called when no more concurrent readers nor writers can
745 * possibly access the table.
746 */
5e28c532 747int ht_destroy(struct rcu_ht *ht)
674f7a69 748{
5e28c532
MD
749 int ret;
750
848d4088 751 /* Wait for in-flight resize operations to complete */
33c7c748 752 CMM_STORE_SHARED(ht->in_progress_destroy, 1);
848d4088
MD
753 while (uatomic_read(&ht->in_progress_resize))
754 poll(NULL, 0, 100); /* wait for 100ms */
abc490a1
MD
755 ret = ht_delete_dummy(ht);
756 if (ret)
757 return ret;
395270b6 758 free(ht->t);
674f7a69 759 free(ht);
5e28c532 760 return ret;
674f7a69
MD
761}
762
273399de
MD
763void ht_count_nodes(struct rcu_ht *ht,
764 unsigned long *count,
765 unsigned long *removed)
766{
767 struct rcu_table *t;
768 struct rcu_ht_node *node, *next;
24365af7
MD
769 struct _rcu_ht_node *lookup;
770 unsigned long nr_dummy = 0;
273399de
MD
771
772 *count = 0;
773 *removed = 0;
774
775 t = rcu_dereference(ht->t);
24365af7
MD
776 /* Count non-dummy nodes in the table */
777 lookup = &t->tbl[0][0];
778 node = (struct rcu_ht_node *) lookup;
273399de 779 do {
cc4fcb10 780 next = rcu_dereference(node->p.next);
273399de 781 if (is_removed(next)) {
1b81fe1a 782 assert(!is_dummy(next));
273399de 783 (*removed)++;
1b81fe1a 784 } else if (!is_dummy(next))
273399de 785 (*count)++;
24365af7
MD
786 else
787 (nr_dummy)++;
273399de
MD
788 node = clear_flag(next);
789 } while (node);
f0c29ed7 790 dbg_printf("number of dummy nodes: %lu\n", nr_dummy);
273399de
MD
791}
792
abc490a1
MD
793static
794void ht_free_table_cb(struct rcu_head *head)
795{
796 struct rcu_table *t =
797 caa_container_of(head, struct rcu_table, head);
798 free(t);
799}
800
801/* called with resize mutex held */
802static
803void _do_ht_resize(struct rcu_ht *ht)
464a1ec9 804{
24365af7 805 unsigned long new_size, old_size, old_order, new_order;
395270b6 806 struct rcu_table *new_t, *old_t;
464a1ec9 807
395270b6
MD
808 old_t = ht->t;
809 old_size = old_t->size;
24365af7 810 old_order = get_count_order_ulong(old_size) + 1;
464a1ec9 811
f9830efd 812 new_size = CMM_LOAD_SHARED(old_t->resize_target);
abc490a1 813 if (old_size == new_size)
464a1ec9 814 return;
24365af7 815 new_order = get_count_order_ulong(new_size) + 1;
f0c29ed7 816 dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
df03fab8 817 old_size, old_order, new_size, new_order);
f000907d 818 new_t = malloc(sizeof(struct rcu_table)
24365af7 819 + (new_order * sizeof(struct _rcu_ht_node *)));
f000907d
MD
820 assert(new_size > old_size);
821 memcpy(&new_t->tbl, &old_t->tbl,
24365af7
MD
822 old_order * sizeof(struct _rcu_ht_node *));
823 init_table(ht, new_t, old_order, new_order - old_order);
f000907d
MD
824 /* Changing table and size atomically wrt lookups */
825 rcu_assign_pointer(ht->t, new_t);
826 ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
464a1ec9
MD
827}
828
abc490a1 829static
f9830efd
MD
830unsigned long resize_target_update(struct rcu_table *t,
831 int growth_order)
464a1ec9 832{
f9830efd
MD
833 return _uatomic_max(&t->resize_target,
834 t->size << growth_order);
464a1ec9
MD
835}
836
464a1ec9
MD
837void ht_resize(struct rcu_ht *ht, int growth)
838{
f9830efd
MD
839 struct rcu_table *t = rcu_dereference(ht->t);
840 unsigned long target_size;
841
f0c29ed7
MD
842 if (growth < 0) {
843 /*
844 * Silently refuse to shrink hash table. (not supported)
845 */
846 dbg_printf("shrinking hash table not supported.\n");
847 return;
848 }
849
f9830efd
MD
850 target_size = resize_target_update(t, growth);
851 if (t->size < target_size) {
11519af6 852 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd
MD
853 pthread_mutex_lock(&ht->resize_mutex);
854 _do_ht_resize(ht);
855 pthread_mutex_unlock(&ht->resize_mutex);
856 }
abc490a1 857}
464a1ec9 858
abc490a1
MD
859static
860void do_resize_cb(struct rcu_head *head)
861{
862 struct rcu_resize_work *work =
863 caa_container_of(head, struct rcu_resize_work, head);
864 struct rcu_ht *ht = work->ht;
865
866 pthread_mutex_lock(&ht->resize_mutex);
867 _do_ht_resize(ht);
868 pthread_mutex_unlock(&ht->resize_mutex);
869 free(work);
848d4088
MD
870 cmm_smp_mb(); /* finish resize before decrement */
871 uatomic_dec(&ht->in_progress_resize);
464a1ec9
MD
872}
873
abc490a1 874static
f000907d 875void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth)
ab7d5fc6 876{
abc490a1 877 struct rcu_resize_work *work;
f9830efd 878 unsigned long target_size;
abc490a1 879
f9830efd 880 target_size = resize_target_update(t, growth);
11519af6 881 if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
848d4088
MD
882 uatomic_inc(&ht->in_progress_resize);
883 cmm_smp_mb(); /* increment resize count before calling it */
f9830efd
MD
884 work = malloc(sizeof(*work));
885 work->ht = ht;
886 ht->ht_call_rcu(&work->head, do_resize_cb);
11519af6 887 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd 888 }
ab7d5fc6 889}
This page took 0.108181 seconds and 4 git commands to generate.