rculfhash test: make teardown more verbose and faster
[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
24365af7 41//#define DEBUG /* Test */
f9830efd
MD
42
43#ifdef DEBUG
44#define dbg_printf(args...) printf(args)
45#else
46#define dbg_printf(args...)
47#endif
48
01370f0b
MD
49#define CHAIN_LEN_TARGET 4
50#define CHAIN_LEN_RESIZE_THRESHOLD 8
2ed95849 51
abc490a1
MD
52#ifndef max
53#define max(a, b) ((a) > (b) ? (a) : (b))
54#endif
2ed95849 55
d95bd160
MD
56/*
57 * The removed flag needs to be updated atomically with the pointer.
58 * The dummy flag does not require to be updated atomically with the
59 * pointer, but it is added as a pointer low bit flag to save space.
60 */
d37166c6 61#define REMOVED_FLAG (1UL << 0)
f5596c94
MD
62#define DUMMY_FLAG (1UL << 1)
63#define FLAGS_MASK ((1UL << 2) - 1)
d37166c6 64
395270b6 65struct rcu_table {
abc490a1 66 unsigned long size; /* always a power of 2 */
f9830efd 67 unsigned long resize_target;
11519af6 68 int resize_initiated;
abc490a1 69 struct rcu_head head;
24365af7 70 struct _rcu_ht_node *tbl[0];
395270b6
MD
71};
72
2ed95849 73struct rcu_ht {
395270b6 74 struct rcu_table *t; /* shared */
2ed95849 75 ht_hash_fct hash_fct;
732ad076
MD
76 ht_compare_fct compare_fct;
77 unsigned long hash_seed;
464a1ec9 78 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
33c7c748 79 unsigned int in_progress_resize, in_progress_destroy;
abc490a1
MD
80 void (*ht_call_rcu)(struct rcu_head *head,
81 void (*func)(struct rcu_head *head));
2ed95849
MD
82};
83
abc490a1
MD
84struct rcu_resize_work {
85 struct rcu_head head;
2ed95849 86 struct rcu_ht *ht;
abc490a1 87};
2ed95849 88
abc490a1
MD
89/*
90 * Algorithm to reverse bits in a word by lookup table, extended to
91 * 64-bit words.
f9830efd 92 * Source:
abc490a1 93 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
f9830efd 94 * Originally from Public Domain.
abc490a1
MD
95 */
96
97static const uint8_t BitReverseTable256[256] =
2ed95849 98{
abc490a1
MD
99#define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
100#define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
101#define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
102 R6(0), R6(2), R6(1), R6(3)
103};
104#undef R2
105#undef R4
106#undef R6
2ed95849 107
abc490a1
MD
108static
109uint8_t bit_reverse_u8(uint8_t v)
110{
111 return BitReverseTable256[v];
112}
ab7d5fc6 113
abc490a1
MD
114static __attribute__((unused))
115uint32_t bit_reverse_u32(uint32_t v)
116{
117 return ((uint32_t) bit_reverse_u8(v) << 24) |
118 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
119 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
120 ((uint32_t) bit_reverse_u8(v >> 24));
2ed95849
MD
121}
122
abc490a1
MD
123static __attribute__((unused))
124uint64_t bit_reverse_u64(uint64_t v)
2ed95849 125{
abc490a1
MD
126 return ((uint64_t) bit_reverse_u8(v) << 56) |
127 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
128 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
129 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
130 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
131 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
132 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
133 ((uint64_t) bit_reverse_u8(v >> 56));
134}
135
136static
137unsigned long bit_reverse_ulong(unsigned long v)
138{
139#if (CAA_BITS_PER_LONG == 32)
140 return bit_reverse_u32(v);
141#else
142 return bit_reverse_u64(v);
143#endif
144}
145
f9830efd 146/*
24365af7
MD
147 * fls: returns the position of the most significant bit.
148 * Returns 0 if no bit is set, else returns the position of the most
149 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
f9830efd 150 */
24365af7
MD
151#if defined(__i386) || defined(__x86_64)
152static inline
153unsigned int fls_u32(uint32_t x)
f9830efd 154{
24365af7
MD
155 int r;
156
157 asm("bsrl %1,%0\n\t"
158 "jnz 1f\n\t"
159 "movl $-1,%0\n\t"
160 "1:\n\t"
161 : "=r" (r) : "rm" (x));
162 return r + 1;
163}
164#define HAS_FLS_U32
165#endif
166
167#if defined(__x86_64)
168static inline
169unsigned int fls_u64(uint64_t x)
170{
171 long r;
172
173 asm("bsrq %1,%0\n\t"
174 "jnz 1f\n\t"
175 "movq $-1,%0\n\t"
176 "1:\n\t"
177 : "=r" (r) : "rm" (x));
178 return r + 1;
179}
180#define HAS_FLS_U64
181#endif
182
183#ifndef HAS_FLS_U64
184static __attribute__((unused))
185unsigned int fls_u64(uint64_t x)
186{
187 unsigned int r = 64;
188
189 if (!x)
190 return 0;
191
192 if (!(x & 0xFFFFFFFF00000000ULL)) {
193 x <<= 32;
194 r -= 32;
195 }
196 if (!(x & 0xFFFF000000000000ULL)) {
197 x <<= 16;
198 r -= 16;
199 }
200 if (!(x & 0xFF00000000000000ULL)) {
201 x <<= 8;
202 r -= 8;
203 }
204 if (!(x & 0xF000000000000000ULL)) {
205 x <<= 4;
206 r -= 4;
207 }
208 if (!(x & 0xC000000000000000ULL)) {
209 x <<= 2;
210 r -= 2;
211 }
212 if (!(x & 0x8000000000000000ULL)) {
213 x <<= 1;
214 r -= 1;
215 }
216 return r;
217}
218#endif
219
220#ifndef HAS_FLS_U32
221static __attribute__((unused))
222unsigned int fls_u32(uint32_t x)
223{
224 unsigned int r = 32;
f9830efd 225
24365af7
MD
226 if (!x)
227 return 0;
228 if (!(x & 0xFFFF0000U)) {
229 x <<= 16;
230 r -= 16;
231 }
232 if (!(x & 0xFF000000U)) {
233 x <<= 8;
234 r -= 8;
235 }
236 if (!(x & 0xF0000000U)) {
237 x <<= 4;
238 r -= 4;
239 }
240 if (!(x & 0xC0000000U)) {
241 x <<= 2;
242 r -= 2;
243 }
244 if (!(x & 0x80000000U)) {
245 x <<= 1;
246 r -= 1;
247 }
248 return r;
249}
250#endif
251
252unsigned int fls_ulong(unsigned long x)
f9830efd 253{
24365af7
MD
254#if (CAA_BITS_PER_lONG == 32)
255 return fls_u32(x);
256#else
257 return fls_u64(x);
258#endif
259}
f9830efd 260
24365af7
MD
261int get_count_order_u32(uint32_t x)
262{
263 int order;
264
265 order = fls_u32(x) - 1;
266 if (x & (x - 1))
267 order++;
268 return order;
269}
270
271int get_count_order_ulong(unsigned long x)
272{
273 int order;
274
275 order = fls_ulong(x) - 1;
276 if (x & (x - 1))
277 order++;
278 return order;
f9830efd
MD
279}
280
281static
282void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth);
283
284static
285void check_resize(struct rcu_ht *ht, struct rcu_table *t,
286 uint32_t chain_len)
287{
24365af7
MD
288 if (chain_len > 100)
289 dbg_printf("rculfhash: WARNING: large chain length: %u.\n",
290 chain_len);
3390d470
MD
291 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
292 ht_resize_lazy(ht, t,
01370f0b 293 get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1)));
f9830efd
MD
294}
295
abc490a1
MD
296static
297struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
298{
d37166c6 299 return (struct rcu_ht_node *) (((unsigned long) node) & ~FLAGS_MASK);
abc490a1
MD
300}
301
302static
303int is_removed(struct rcu_ht_node *node)
304{
d37166c6 305 return ((unsigned long) node) & REMOVED_FLAG;
abc490a1
MD
306}
307
308static
309struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
310{
d37166c6 311 return (struct rcu_ht_node *) (((unsigned long) node) | REMOVED_FLAG);
abc490a1
MD
312}
313
f5596c94
MD
314static
315int is_dummy(struct rcu_ht_node *node)
316{
317 return ((unsigned long) node) & DUMMY_FLAG;
318}
319
320static
321struct rcu_ht_node *flag_dummy(struct rcu_ht_node *node)
322{
323 return (struct rcu_ht_node *) (((unsigned long) node) | DUMMY_FLAG);
324}
325
abc490a1 326static
f9830efd 327unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
abc490a1
MD
328{
329 unsigned long old1, old2;
330
331 old1 = uatomic_read(ptr);
332 do {
333 old2 = old1;
334 if (old2 >= v)
f9830efd 335 return old2;
abc490a1 336 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
f9830efd 337 return v;
abc490a1
MD
338}
339
273399de
MD
340/*
341 * Remove all logically deleted nodes from a bucket up to a certain node key.
342 */
343static
344void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
345{
f5596c94 346 struct rcu_ht_node *iter_prev, *iter, *next, *new_next;
273399de
MD
347
348 for (;;) {
349 iter_prev = dummy;
350 /* We can always skip the dummy node initially */
cc4fcb10
MD
351 iter = rcu_dereference(iter_prev->p.next);
352 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
273399de 353 for (;;) {
a2974903 354 if (unlikely(!clear_flag(iter)))
479c8a32 355 return;
cc4fcb10 356 if (clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)
273399de 357 return;
cc4fcb10 358 next = rcu_dereference(clear_flag(iter)->p.next);
273399de
MD
359 if (is_removed(next))
360 break;
b453eae1 361 iter_prev = clear_flag(iter);
273399de
MD
362 iter = next;
363 }
364 assert(!is_removed(iter));
f5596c94
MD
365 if (is_dummy(iter))
366 new_next = flag_dummy(clear_flag(next));
367 else
368 new_next = clear_flag(next);
369 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de
MD
370 }
371}
372
abc490a1 373static
18117871 374struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t,
f5596c94 375 struct rcu_ht_node *node, int unique, int dummy)
abc490a1 376{
f5596c94
MD
377 struct rcu_ht_node *iter_prev, *iter, *next, *new_node, *new_next,
378 *dummy_node;
24365af7
MD
379 struct _rcu_ht_node *lookup;
380 unsigned long hash, index, order;
abc490a1 381
18117871 382 if (!t->size) {
f5596c94
MD
383 assert(dummy);
384 node->p.next = flag_dummy(NULL);
18117871
MD
385 return node; /* Initial first add (head) */
386 }
cc4fcb10 387 hash = bit_reverse_ulong(node->p.reverse_hash);
abc490a1 388 for (;;) {
f9830efd 389 uint32_t chain_len = 0;
abc490a1 390
11519af6
MD
391 /*
392 * iter_prev points to the non-removed node prior to the
393 * insert location.
11519af6 394 */
24365af7
MD
395 index = hash & (t->size - 1);
396 order = get_count_order_ulong(index + 1);
397 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
398 iter_prev = (struct rcu_ht_node *) lookup;
11519af6 399 /* We can always skip the dummy node initially */
cc4fcb10
MD
400 iter = rcu_dereference(iter_prev->p.next);
401 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
abc490a1 402 for (;;) {
a2974903 403 if (unlikely(!clear_flag(iter)))
273399de 404 goto insert;
cc4fcb10 405 if (clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)
273399de 406 goto insert;
cc4fcb10 407 next = rcu_dereference(clear_flag(iter)->p.next);
273399de 408 if (is_removed(next))
9dba85be 409 goto gc_node;
e43f23f8 410 if (unique
1b81fe1a 411 && !is_dummy(next)
e43f23f8
MD
412 && !ht->compare_fct(node->key, node->key_len,
413 clear_flag(iter)->key,
414 clear_flag(iter)->key_len))
18117871 415 return clear_flag(iter);
11519af6 416 /* Only account for identical reverse hash once */
24365af7
MD
417 if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
418 && !is_dummy(next))
11519af6
MD
419 check_resize(ht, t, ++chain_len);
420 iter_prev = clear_flag(iter);
273399de 421 iter = next;
abc490a1 422 }
273399de 423 insert:
7ec59d3b 424 assert(node != clear_flag(iter));
11519af6 425 assert(!is_removed(iter_prev));
f000907d 426 assert(iter_prev != node);
f5596c94 427 if (!dummy)
1b81fe1a 428 node->p.next = clear_flag(iter);
f5596c94 429 else
1b81fe1a 430 node->p.next = flag_dummy(clear_flag(iter));
f5596c94
MD
431 if (is_dummy(iter))
432 new_node = flag_dummy(node);
433 else
434 new_node = node;
cc4fcb10 435 if (uatomic_cmpxchg(&iter_prev->p.next, iter,
f5596c94 436 new_node) != iter)
273399de 437 continue; /* retry */
11519af6 438 else
273399de 439 goto gc_end;
9dba85be
MD
440 gc_node:
441 assert(!is_removed(iter));
f5596c94
MD
442 if (is_dummy(iter))
443 new_next = flag_dummy(clear_flag(next));
444 else
445 new_next = clear_flag(next);
446 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de 447 /* retry */
464a1ec9 448 }
273399de
MD
449gc_end:
450 /* Garbage collect logically removed nodes in the bucket */
24365af7
MD
451 index = hash & (t->size - 1);
452 order = get_count_order_ulong(index + 1);
453 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
454 dummy_node = (struct rcu_ht_node *) lookup;
f5596c94 455 _ht_gc_bucket(dummy_node, node);
18117871 456 return node;
abc490a1 457}
464a1ec9 458
abc490a1
MD
459static
460int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
461{
273399de 462 struct rcu_ht_node *dummy, *next, *old;
24365af7 463 struct _rcu_ht_node *lookup;
abc490a1 464 int flagged = 0;
24365af7 465 unsigned long hash, index, order;
5e28c532 466
7ec59d3b 467 /* logically delete the node */
cc4fcb10 468 old = rcu_dereference(node->p.next);
7ec59d3b
MD
469 do {
470 next = old;
471 if (is_removed(next))
472 goto end;
1b81fe1a 473 assert(!is_dummy(next));
cc4fcb10 474 old = uatomic_cmpxchg(&node->p.next, next,
7ec59d3b
MD
475 flag_removed(next));
476 } while (old != next);
477
478 /* We performed the (logical) deletion. */
479 flagged = 1;
480
481 /*
482 * Ensure that the node is not visible to readers anymore: lookup for
273399de
MD
483 * the node, and remove it (along with any other logically removed node)
484 * if found.
11519af6 485 */
cc4fcb10 486 hash = bit_reverse_ulong(node->p.reverse_hash);
24365af7
MD
487 index = hash & (t->size - 1);
488 order = get_count_order_ulong(index + 1);
489 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
490 dummy = (struct rcu_ht_node *) lookup;
273399de 491 _ht_gc_bucket(dummy, node);
2ed95849 492end:
11519af6
MD
493 /*
494 * Only the flagging action indicated that we (and no other)
495 * removed the node from the hash.
496 */
7ec59d3b 497 if (flagged) {
cc4fcb10 498 assert(is_removed(rcu_dereference(node->p.next)));
11519af6 499 return 0;
7ec59d3b 500 } else
11519af6 501 return -ENOENT;
abc490a1 502}
2ed95849 503
abc490a1
MD
504static
505void init_table(struct rcu_ht *ht, struct rcu_table *t,
24365af7
MD
506 unsigned long first_order, unsigned long len_order)
507{
508 unsigned long i, end_order;
509
510 dbg_printf("rculfhash: init table: first_order %lu end_order %lu\n",
511 first_order, first_order + len_order);
512 end_order = first_order + len_order;
513 t->size = !first_order ? 0 : (1UL << (first_order - 1));
514 for (i = first_order; i < end_order; i++) {
515 unsigned long j, len;
516
517 len = !i ? 1 : 1UL << (i - 1);
518 dbg_printf("rculfhash: init order %lu len: %lu\n", i, len);
519 t->tbl[i] = calloc(len, sizeof(struct _rcu_ht_node));
520 for (j = 0; j < len; j++) {
521 dbg_printf("rculfhash: init entry: i %lu j %lu hash %lu\n",
522 i, j, !i ? 0 : (1UL << (i - 1)) + j);
523 struct rcu_ht_node *new_node =
524 (struct rcu_ht_node *) &t->tbl[i][j];
525 new_node->p.reverse_hash =
526 bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
527 (void) _ht_add(ht, t, new_node, 0, 1);
33c7c748
MD
528 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
529 break;
24365af7
MD
530 }
531 /* Update table size */
532 t->size = !i ? 1 : (1UL << i);
533 dbg_printf("rculfhash: init new size: %lu\n", t->size);
33c7c748
MD
534 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
535 break;
abc490a1 536 }
24365af7 537 t->resize_target = t->size;
11519af6 538 t->resize_initiated = 0;
2ed95849
MD
539}
540
abc490a1 541struct rcu_ht *ht_new(ht_hash_fct hash_fct,
732ad076
MD
542 ht_compare_fct compare_fct,
543 unsigned long hash_seed,
abc490a1
MD
544 unsigned long init_size,
545 void (*ht_call_rcu)(struct rcu_head *head,
546 void (*func)(struct rcu_head *head)))
547{
548 struct rcu_ht *ht;
24365af7 549 unsigned long order;
abc490a1
MD
550
551 ht = calloc(1, sizeof(struct rcu_ht));
552 ht->hash_fct = hash_fct;
732ad076
MD
553 ht->compare_fct = compare_fct;
554 ht->hash_seed = hash_seed;
f000907d 555 ht->ht_call_rcu = ht_call_rcu;
848d4088 556 ht->in_progress_resize = 0;
abc490a1
MD
557 /* this mutex should not nest in read-side C.S. */
558 pthread_mutex_init(&ht->resize_mutex, NULL);
24365af7 559 order = get_count_order_ulong(max(init_size, 1)) + 1;
abc490a1 560 ht->t = calloc(1, sizeof(struct rcu_table)
24365af7 561 + (order * sizeof(struct _rcu_ht_node *)));
abc490a1 562 ht->t->size = 0;
f000907d 563 pthread_mutex_lock(&ht->resize_mutex);
24365af7 564 init_table(ht, ht->t, 0, order);
f000907d 565 pthread_mutex_unlock(&ht->resize_mutex);
abc490a1
MD
566 return ht;
567}
568
732ad076 569struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
2ed95849 570{
395270b6 571 struct rcu_table *t;
1b81fe1a 572 struct rcu_ht_node *node, *next;
24365af7
MD
573 struct _rcu_ht_node *lookup;
574 unsigned long hash, reverse_hash, index, order;
2ed95849 575
732ad076 576 hash = ht->hash_fct(key, key_len, ht->hash_seed);
abc490a1 577 reverse_hash = bit_reverse_ulong(hash);
464a1ec9 578
395270b6 579 t = rcu_dereference(ht->t);
24365af7
MD
580 index = hash & (t->size - 1);
581 order = get_count_order_ulong(index + 1);
582 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
583 dbg_printf("rculfhash: lookup hash %lu index %lu order %lu aridx %lu\n",
584 hash, index, order, index & ((1UL << (order - 1)) - 1));
585 node = (struct rcu_ht_node *) lookup;
2ed95849 586 for (;;) {
abc490a1
MD
587 if (unlikely(!node))
588 break;
cc4fcb10 589 if (unlikely(node->p.reverse_hash > reverse_hash)) {
abc490a1
MD
590 node = NULL;
591 break;
2ed95849 592 }
1b81fe1a
MD
593 next = rcu_dereference(node->p.next);
594 if (likely(!is_removed(next))
595 && !is_dummy(next)
49c2e2d6 596 && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
273399de 597 break;
2ed95849 598 }
1b81fe1a 599 node = clear_flag(next);
2ed95849 600 }
1b81fe1a 601 assert(!node || !is_dummy(rcu_dereference(node->p.next)));
abc490a1
MD
602 return node;
603}
e0ba718a 604
f000907d 605void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
abc490a1
MD
606{
607 struct rcu_table *t;
49c2e2d6 608 unsigned long hash;
ab7d5fc6 609
49c2e2d6 610 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 611 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
2ed95849 612
abc490a1 613 t = rcu_dereference(ht->t);
f5596c94 614 (void) _ht_add(ht, t, node, 0, 0);
3eca1b8c
MD
615}
616
18117871 617struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
3eca1b8c
MD
618{
619 struct rcu_table *t;
49c2e2d6 620 unsigned long hash;
3eca1b8c 621
49c2e2d6 622 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 623 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
3eca1b8c
MD
624
625 t = rcu_dereference(ht->t);
f5596c94 626 return _ht_add(ht, t, node, 1, 0);
2ed95849
MD
627}
628
abc490a1 629int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
2ed95849 630{
abc490a1
MD
631 struct rcu_table *t;
632
633 t = rcu_dereference(ht->t);
abc490a1 634 return _ht_remove(ht, t, node);
2ed95849 635}
ab7d5fc6 636
abc490a1
MD
637static
638int ht_delete_dummy(struct rcu_ht *ht)
674f7a69 639{
395270b6 640 struct rcu_table *t;
abc490a1 641 struct rcu_ht_node *node;
24365af7
MD
642 struct _rcu_ht_node *lookup;
643 unsigned long order, i;
674f7a69 644
abc490a1
MD
645 t = ht->t;
646 /* Check that the table is empty */
24365af7
MD
647 lookup = &t->tbl[0][0];
648 node = (struct rcu_ht_node *) lookup;
abc490a1 649 do {
1b81fe1a
MD
650 node = clear_flag(node)->p.next;
651 if (!is_dummy(node))
abc490a1 652 return -EPERM;
273399de 653 assert(!is_removed(node));
a2974903 654 } while (clear_flag(node));
abc490a1 655 /* Internal sanity check: all nodes left should be dummy */
24365af7
MD
656 for (order = 0; order < get_count_order_ulong(t->size) + 1; order++) {
657 unsigned long len;
658
659 len = !order ? 1 : 1UL << (order - 1);
660 for (i = 0; i < len; i++) {
661 dbg_printf("rculfhash: delete order %lu i %lu hash %lu\n",
662 order, i,
663 bit_reverse_ulong(t->tbl[order][i].reverse_hash));
664 assert(is_dummy(t->tbl[order][i].next));
665 }
666 free(t->tbl[order]);
674f7a69 667 }
abc490a1 668 return 0;
674f7a69
MD
669}
670
671/*
672 * Should only be called when no more concurrent readers nor writers can
673 * possibly access the table.
674 */
5e28c532 675int ht_destroy(struct rcu_ht *ht)
674f7a69 676{
5e28c532
MD
677 int ret;
678
848d4088 679 /* Wait for in-flight resize operations to complete */
33c7c748 680 CMM_STORE_SHARED(ht->in_progress_destroy, 1);
848d4088
MD
681 while (uatomic_read(&ht->in_progress_resize))
682 poll(NULL, 0, 100); /* wait for 100ms */
abc490a1
MD
683 ret = ht_delete_dummy(ht);
684 if (ret)
685 return ret;
395270b6 686 free(ht->t);
674f7a69 687 free(ht);
5e28c532 688 return ret;
674f7a69
MD
689}
690
273399de
MD
691void ht_count_nodes(struct rcu_ht *ht,
692 unsigned long *count,
693 unsigned long *removed)
694{
695 struct rcu_table *t;
696 struct rcu_ht_node *node, *next;
24365af7
MD
697 struct _rcu_ht_node *lookup;
698 unsigned long nr_dummy = 0;
273399de
MD
699
700 *count = 0;
701 *removed = 0;
702
703 t = rcu_dereference(ht->t);
24365af7
MD
704 /* Count non-dummy nodes in the table */
705 lookup = &t->tbl[0][0];
706 node = (struct rcu_ht_node *) lookup;
273399de 707 do {
cc4fcb10 708 next = rcu_dereference(node->p.next);
273399de 709 if (is_removed(next)) {
1b81fe1a 710 assert(!is_dummy(next));
273399de 711 (*removed)++;
1b81fe1a 712 } else if (!is_dummy(next))
273399de 713 (*count)++;
24365af7
MD
714 else
715 (nr_dummy)++;
273399de
MD
716 node = clear_flag(next);
717 } while (node);
24365af7 718 dbg_printf("rculfhash: number of dummy nodes: %lu\n", nr_dummy);
273399de
MD
719}
720
abc490a1
MD
721static
722void ht_free_table_cb(struct rcu_head *head)
723{
724 struct rcu_table *t =
725 caa_container_of(head, struct rcu_table, head);
726 free(t);
727}
728
729/* called with resize mutex held */
730static
731void _do_ht_resize(struct rcu_ht *ht)
464a1ec9 732{
24365af7 733 unsigned long new_size, old_size, old_order, new_order;
395270b6 734 struct rcu_table *new_t, *old_t;
464a1ec9 735
395270b6
MD
736 old_t = ht->t;
737 old_size = old_t->size;
24365af7 738 old_order = get_count_order_ulong(old_size) + 1;
464a1ec9 739
f9830efd 740 new_size = CMM_LOAD_SHARED(old_t->resize_target);
abc490a1 741 if (old_size == new_size)
464a1ec9 742 return;
24365af7 743 new_order = get_count_order_ulong(new_size) + 1;
df03fab8
MD
744 printf("rculfhash: resize from %lu (order %lu) to %lu (order %lu) buckets\n",
745 old_size, old_order, new_size, new_order);
f000907d 746 new_t = malloc(sizeof(struct rcu_table)
24365af7 747 + (new_order * sizeof(struct _rcu_ht_node *)));
f000907d
MD
748 assert(new_size > old_size);
749 memcpy(&new_t->tbl, &old_t->tbl,
24365af7
MD
750 old_order * sizeof(struct _rcu_ht_node *));
751 init_table(ht, new_t, old_order, new_order - old_order);
f000907d
MD
752 /* Changing table and size atomically wrt lookups */
753 rcu_assign_pointer(ht->t, new_t);
754 ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
464a1ec9
MD
755}
756
abc490a1 757static
f9830efd
MD
758unsigned long resize_target_update(struct rcu_table *t,
759 int growth_order)
464a1ec9 760{
f9830efd
MD
761 return _uatomic_max(&t->resize_target,
762 t->size << growth_order);
464a1ec9
MD
763}
764
464a1ec9
MD
765void ht_resize(struct rcu_ht *ht, int growth)
766{
f9830efd
MD
767 struct rcu_table *t = rcu_dereference(ht->t);
768 unsigned long target_size;
769
770 target_size = resize_target_update(t, growth);
771 if (t->size < target_size) {
11519af6 772 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd
MD
773 pthread_mutex_lock(&ht->resize_mutex);
774 _do_ht_resize(ht);
775 pthread_mutex_unlock(&ht->resize_mutex);
776 }
abc490a1 777}
464a1ec9 778
abc490a1
MD
779static
780void do_resize_cb(struct rcu_head *head)
781{
782 struct rcu_resize_work *work =
783 caa_container_of(head, struct rcu_resize_work, head);
784 struct rcu_ht *ht = work->ht;
785
786 pthread_mutex_lock(&ht->resize_mutex);
787 _do_ht_resize(ht);
788 pthread_mutex_unlock(&ht->resize_mutex);
789 free(work);
848d4088
MD
790 cmm_smp_mb(); /* finish resize before decrement */
791 uatomic_dec(&ht->in_progress_resize);
464a1ec9
MD
792}
793
abc490a1 794static
f000907d 795void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth)
ab7d5fc6 796{
abc490a1 797 struct rcu_resize_work *work;
f9830efd 798 unsigned long target_size;
abc490a1 799
f9830efd 800 target_size = resize_target_update(t, growth);
11519af6 801 if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
848d4088
MD
802 uatomic_inc(&ht->in_progress_resize);
803 cmm_smp_mb(); /* increment resize count before calling it */
f9830efd
MD
804 work = malloc(sizeof(*work));
805 work->ht = ht;
806 ht->ht_call_rcu(&work->head, do_resize_cb);
11519af6 807 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd 808 }
ab7d5fc6 809}
This page took 0.103983 seconds and 4 git commands to generate.