test rculfhash: add/remove/random support (with SIGUSR1)
[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
df44348d 105#include "config.h"
2ed95849 106#include <urcu.h>
abc490a1 107#include <urcu-call-rcu.h>
a42cc659
MD
108#include <urcu/arch.h>
109#include <urcu/uatomic.h>
674f7a69 110#include <urcu/jhash.h>
a42cc659 111#include <urcu/compiler.h>
abc490a1 112#include <urcu/rculfhash.h>
5e28c532 113#include <stdio.h>
464a1ec9 114#include <pthread.h>
44395fb7 115
f9830efd 116#ifdef DEBUG
f0c29ed7 117#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
f9830efd 118#else
e753ff5a 119#define dbg_printf(fmt, args...)
f9830efd
MD
120#endif
121
f8994aee
MD
122/*
123 * Per-CPU split-counters lazily update the global counter each 1024
124 * addition/removal. It automatically keeps track of resize required.
125 * We use the bucket length as indicator for need to expand for small
126 * tables and machines lacking per-cpu data suppport.
127 */
128#define COUNT_COMMIT_ORDER 10
6ea6bc67
MD
129#define CHAIN_LEN_TARGET 1
130#define CHAIN_LEN_RESIZE_THRESHOLD 3
2ed95849 131
abc490a1
MD
132#ifndef max
133#define max(a, b) ((a) > (b) ? (a) : (b))
134#endif
2ed95849 135
d95bd160
MD
136/*
137 * The removed flag needs to be updated atomically with the pointer.
138 * The dummy flag does not require to be updated atomically with the
139 * pointer, but it is added as a pointer low bit flag to save space.
140 */
d37166c6 141#define REMOVED_FLAG (1UL << 0)
f5596c94
MD
142#define DUMMY_FLAG (1UL << 1)
143#define FLAGS_MASK ((1UL << 2) - 1)
d37166c6 144
df44348d 145struct ht_items_count {
3171717f 146 unsigned long add, remove;
df44348d
MD
147} __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
148
395270b6 149struct rcu_table {
abc490a1 150 unsigned long size; /* always a power of 2 */
f9830efd 151 unsigned long resize_target;
11519af6 152 int resize_initiated;
abc490a1 153 struct rcu_head head;
14044b37 154 struct _cds_lfht_node *tbl[0];
395270b6
MD
155};
156
14044b37 157struct cds_lfht {
395270b6 158 struct rcu_table *t; /* shared */
14044b37
MD
159 cds_lfht_hash_fct hash_fct;
160 cds_lfht_compare_fct compare_fct;
732ad076 161 unsigned long hash_seed;
464a1ec9 162 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
33c7c748 163 unsigned int in_progress_resize, in_progress_destroy;
14044b37 164 void (*cds_lfht_call_rcu)(struct rcu_head *head,
abc490a1 165 void (*func)(struct rcu_head *head));
df44348d
MD
166 unsigned long count; /* global approximate item count */
167 struct ht_items_count *percpu_count; /* per-cpu item count */
2ed95849
MD
168};
169
abc490a1
MD
170struct rcu_resize_work {
171 struct rcu_head head;
14044b37 172 struct cds_lfht *ht;
abc490a1 173};
2ed95849 174
abc490a1
MD
175/*
176 * Algorithm to reverse bits in a word by lookup table, extended to
177 * 64-bit words.
f9830efd 178 * Source:
abc490a1 179 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
f9830efd 180 * Originally from Public Domain.
abc490a1
MD
181 */
182
183static const uint8_t BitReverseTable256[256] =
2ed95849 184{
abc490a1
MD
185#define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
186#define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
187#define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
188 R6(0), R6(2), R6(1), R6(3)
189};
190#undef R2
191#undef R4
192#undef R6
2ed95849 193
abc490a1
MD
194static
195uint8_t bit_reverse_u8(uint8_t v)
196{
197 return BitReverseTable256[v];
198}
ab7d5fc6 199
abc490a1
MD
200static __attribute__((unused))
201uint32_t bit_reverse_u32(uint32_t v)
202{
203 return ((uint32_t) bit_reverse_u8(v) << 24) |
204 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
205 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
206 ((uint32_t) bit_reverse_u8(v >> 24));
2ed95849
MD
207}
208
abc490a1
MD
209static __attribute__((unused))
210uint64_t bit_reverse_u64(uint64_t v)
2ed95849 211{
abc490a1
MD
212 return ((uint64_t) bit_reverse_u8(v) << 56) |
213 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
214 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
215 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
216 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
217 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
218 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
219 ((uint64_t) bit_reverse_u8(v >> 56));
220}
221
222static
223unsigned long bit_reverse_ulong(unsigned long v)
224{
225#if (CAA_BITS_PER_LONG == 32)
226 return bit_reverse_u32(v);
227#else
228 return bit_reverse_u64(v);
229#endif
230}
231
f9830efd 232/*
24365af7
MD
233 * fls: returns the position of the most significant bit.
234 * Returns 0 if no bit is set, else returns the position of the most
235 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
f9830efd 236 */
24365af7
MD
237#if defined(__i386) || defined(__x86_64)
238static inline
239unsigned int fls_u32(uint32_t x)
f9830efd 240{
24365af7
MD
241 int r;
242
243 asm("bsrl %1,%0\n\t"
244 "jnz 1f\n\t"
245 "movl $-1,%0\n\t"
246 "1:\n\t"
247 : "=r" (r) : "rm" (x));
248 return r + 1;
249}
250#define HAS_FLS_U32
251#endif
252
253#if defined(__x86_64)
254static inline
255unsigned int fls_u64(uint64_t x)
256{
257 long r;
258
259 asm("bsrq %1,%0\n\t"
260 "jnz 1f\n\t"
261 "movq $-1,%0\n\t"
262 "1:\n\t"
263 : "=r" (r) : "rm" (x));
264 return r + 1;
265}
266#define HAS_FLS_U64
267#endif
268
269#ifndef HAS_FLS_U64
270static __attribute__((unused))
271unsigned int fls_u64(uint64_t x)
272{
273 unsigned int r = 64;
274
275 if (!x)
276 return 0;
277
278 if (!(x & 0xFFFFFFFF00000000ULL)) {
279 x <<= 32;
280 r -= 32;
281 }
282 if (!(x & 0xFFFF000000000000ULL)) {
283 x <<= 16;
284 r -= 16;
285 }
286 if (!(x & 0xFF00000000000000ULL)) {
287 x <<= 8;
288 r -= 8;
289 }
290 if (!(x & 0xF000000000000000ULL)) {
291 x <<= 4;
292 r -= 4;
293 }
294 if (!(x & 0xC000000000000000ULL)) {
295 x <<= 2;
296 r -= 2;
297 }
298 if (!(x & 0x8000000000000000ULL)) {
299 x <<= 1;
300 r -= 1;
301 }
302 return r;
303}
304#endif
305
306#ifndef HAS_FLS_U32
307static __attribute__((unused))
308unsigned int fls_u32(uint32_t x)
309{
310 unsigned int r = 32;
f9830efd 311
24365af7
MD
312 if (!x)
313 return 0;
314 if (!(x & 0xFFFF0000U)) {
315 x <<= 16;
316 r -= 16;
317 }
318 if (!(x & 0xFF000000U)) {
319 x <<= 8;
320 r -= 8;
321 }
322 if (!(x & 0xF0000000U)) {
323 x <<= 4;
324 r -= 4;
325 }
326 if (!(x & 0xC0000000U)) {
327 x <<= 2;
328 r -= 2;
329 }
330 if (!(x & 0x80000000U)) {
331 x <<= 1;
332 r -= 1;
333 }
334 return r;
335}
336#endif
337
338unsigned int fls_ulong(unsigned long x)
f9830efd 339{
24365af7
MD
340#if (CAA_BITS_PER_lONG == 32)
341 return fls_u32(x);
342#else
343 return fls_u64(x);
344#endif
345}
f9830efd 346
24365af7
MD
347int get_count_order_u32(uint32_t x)
348{
349 int order;
350
351 order = fls_u32(x) - 1;
352 if (x & (x - 1))
353 order++;
354 return order;
355}
356
357int get_count_order_ulong(unsigned long x)
358{
359 int order;
360
361 order = fls_ulong(x) - 1;
362 if (x & (x - 1))
363 order++;
364 return order;
f9830efd
MD
365}
366
367static
14044b37 368void cds_lfht_resize_lazy(struct cds_lfht *ht, struct rcu_table *t, int growth);
f9830efd 369
df44348d
MD
370/*
371 * If the sched_getcpu() and sysconf(_SC_NPROCESSORS_CONF) calls are
372 * available, then we support hash table item accounting.
373 * In the unfortunate event the number of CPUs reported would be
374 * inaccurate, we use modulo arithmetic on the number of CPUs we got.
375 */
df44348d
MD
376#if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF)
377
f8994aee
MD
378static
379void cds_lfht_resize_lazy_count(struct cds_lfht *ht, struct rcu_table *t,
380 unsigned long count);
381
df44348d
MD
382static long nr_cpus_mask = -1;
383
384static
385struct ht_items_count *alloc_per_cpu_items_count(void)
386{
387 struct ht_items_count *count;
388
389 switch (nr_cpus_mask) {
390 case -2:
391 return NULL;
392 case -1:
393 {
394 long maxcpus;
395
396 maxcpus = sysconf(_SC_NPROCESSORS_CONF);
397 if (maxcpus <= 0) {
398 nr_cpus_mask = -2;
399 return NULL;
400 }
401 /*
402 * round up number of CPUs to next power of two, so we
403 * can use & for modulo.
404 */
405 maxcpus = 1UL << get_count_order_ulong(maxcpus);
406 nr_cpus_mask = maxcpus - 1;
407 }
408 /* Fall-through */
409 default:
410 return calloc(nr_cpus_mask + 1, sizeof(*count));
411 }
412}
413
414static
415void free_per_cpu_items_count(struct ht_items_count *count)
416{
417 free(count);
418}
419
420static
421int ht_get_cpu(void)
422{
423 int cpu;
424
425 assert(nr_cpus_mask >= 0);
426 cpu = sched_getcpu();
427 if (unlikely(cpu < 0))
428 return cpu;
429 else
430 return cpu & nr_cpus_mask;
431}
432
433static
3171717f 434void ht_count_add(struct cds_lfht *ht, struct rcu_table *t)
df44348d 435{
3171717f 436 unsigned long percpu_count;
df44348d
MD
437 int cpu;
438
439 if (unlikely(!ht->percpu_count))
3171717f 440 return;
df44348d
MD
441 cpu = ht_get_cpu();
442 if (unlikely(cpu < 0))
3171717f
MD
443 return;
444 percpu_count = uatomic_add_return(&ht->percpu_count[cpu].add, 1);
df44348d
MD
445 if (unlikely(!(percpu_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))) {
446 unsigned long count;
447
448 dbg_printf("add percpu %lu\n", percpu_count);
449 count = uatomic_add_return(&ht->count,
450 1UL << COUNT_COMMIT_ORDER);
451 /* If power of 2 */
452 if (!(count & (count - 1))) {
f8994aee
MD
453 if ((count >> CHAIN_LEN_RESIZE_THRESHOLD)
454 < t->size)
455 return;
456 dbg_printf("add set global %lu\n", count);
457 cds_lfht_resize_lazy_count(ht, t,
6ea6bc67 458 count >> (CHAIN_LEN_TARGET - 1));
df44348d
MD
459 }
460 }
461}
462
463static
464void ht_count_remove(struct cds_lfht *ht, struct rcu_table *t)
465{
466 unsigned long percpu_count;
3171717f 467 int cpu;
df44348d 468
3171717f
MD
469 if (unlikely(!ht->percpu_count))
470 return;
471 cpu = ht_get_cpu();
472 if (unlikely(cpu < 0))
473 return;
474 percpu_count = uatomic_add_return(&ht->percpu_count[cpu].remove, -1);
df44348d
MD
475 if (unlikely(!(percpu_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))) {
476 unsigned long count;
477
478 dbg_printf("remove percpu %lu\n", percpu_count);
479 count = uatomic_add_return(&ht->count,
3171717f 480 -(1UL << COUNT_COMMIT_ORDER));
df44348d
MD
481 /* If power of 2 */
482 if (!(count & (count - 1))) {
f8994aee
MD
483 if ((count >> CHAIN_LEN_RESIZE_THRESHOLD)
484 >= t->size)
485 return;
486 dbg_printf("remove set global %lu\n", count);
487 cds_lfht_resize_lazy_count(ht, t,
6ea6bc67 488 count >> (CHAIN_LEN_TARGET - 1));
df44348d
MD
489 }
490 }
491}
492
493#else /* #if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF) */
494
495static const long nr_cpus_mask = -1;
496
497static
498struct ht_items_count *alloc_per_cpu_items_count(void)
499{
500 return NULL;
501}
502
503static
504void free_per_cpu_items_count(struct ht_items_count *count)
505{
506}
507
508static
f8994aee 509void ht_count_add(struct cds_lfht *ht, struct rcu_table *t)
df44348d
MD
510{
511}
512
513static
f8994aee 514void ht_count_remove(struct cds_lfht *ht, struct rcu_table *t)
df44348d
MD
515{
516}
517
518#endif /* #else #if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF) */
519
520
f9830efd 521static
14044b37 522void check_resize(struct cds_lfht *ht, struct rcu_table *t,
f9830efd
MD
523 uint32_t chain_len)
524{
f8994aee
MD
525 unsigned long count;
526
527 count = uatomic_read(&ht->count);
528 /*
529 * Use bucket-local length for small table expand and for
530 * environments lacking per-cpu data support.
531 */
532 if (count >= (1UL << COUNT_COMMIT_ORDER))
533 return;
24365af7 534 if (chain_len > 100)
f0c29ed7 535 dbg_printf("WARNING: large chain length: %u.\n",
24365af7 536 chain_len);
3390d470 537 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
14044b37 538 cds_lfht_resize_lazy(ht, t,
01370f0b 539 get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1)));
f9830efd
MD
540}
541
abc490a1 542static
14044b37 543struct cds_lfht_node *clear_flag(struct cds_lfht_node *node)
abc490a1 544{
14044b37 545 return (struct cds_lfht_node *) (((unsigned long) node) & ~FLAGS_MASK);
abc490a1
MD
546}
547
548static
14044b37 549int is_removed(struct cds_lfht_node *node)
abc490a1 550{
d37166c6 551 return ((unsigned long) node) & REMOVED_FLAG;
abc490a1
MD
552}
553
554static
14044b37 555struct cds_lfht_node *flag_removed(struct cds_lfht_node *node)
abc490a1 556{
14044b37 557 return (struct cds_lfht_node *) (((unsigned long) node) | REMOVED_FLAG);
abc490a1
MD
558}
559
f5596c94 560static
14044b37 561int is_dummy(struct cds_lfht_node *node)
f5596c94
MD
562{
563 return ((unsigned long) node) & DUMMY_FLAG;
564}
565
566static
14044b37 567struct cds_lfht_node *flag_dummy(struct cds_lfht_node *node)
f5596c94 568{
14044b37 569 return (struct cds_lfht_node *) (((unsigned long) node) | DUMMY_FLAG);
f5596c94
MD
570}
571
abc490a1 572static
f9830efd 573unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
abc490a1
MD
574{
575 unsigned long old1, old2;
576
577 old1 = uatomic_read(ptr);
578 do {
579 old2 = old1;
580 if (old2 >= v)
f9830efd 581 return old2;
abc490a1 582 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
f9830efd 583 return v;
abc490a1
MD
584}
585
273399de
MD
586/*
587 * Remove all logically deleted nodes from a bucket up to a certain node key.
588 */
589static
14044b37 590void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node)
273399de 591{
14044b37 592 struct cds_lfht_node *iter_prev, *iter, *next, *new_next;
273399de
MD
593
594 for (;;) {
595 iter_prev = dummy;
596 /* We can always skip the dummy node initially */
cc4fcb10
MD
597 iter = rcu_dereference(iter_prev->p.next);
598 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
273399de 599 for (;;) {
a2974903 600 if (unlikely(!clear_flag(iter)))
479c8a32 601 return;
76412f24 602 if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
273399de 603 return;
cc4fcb10 604 next = rcu_dereference(clear_flag(iter)->p.next);
76412f24 605 if (likely(is_removed(next)))
273399de 606 break;
b453eae1 607 iter_prev = clear_flag(iter);
273399de
MD
608 iter = next;
609 }
610 assert(!is_removed(iter));
f5596c94
MD
611 if (is_dummy(iter))
612 new_next = flag_dummy(clear_flag(next));
613 else
614 new_next = clear_flag(next);
615 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de
MD
616 }
617}
618
abc490a1 619static
14044b37
MD
620struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, struct rcu_table *t,
621 struct cds_lfht_node *node, int unique, int dummy)
abc490a1 622{
14044b37 623 struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
f5596c94 624 *dummy_node;
14044b37 625 struct _cds_lfht_node *lookup;
24365af7 626 unsigned long hash, index, order;
abc490a1 627
18117871 628 if (!t->size) {
f5596c94
MD
629 assert(dummy);
630 node->p.next = flag_dummy(NULL);
18117871
MD
631 return node; /* Initial first add (head) */
632 }
cc4fcb10 633 hash = bit_reverse_ulong(node->p.reverse_hash);
abc490a1 634 for (;;) {
f9830efd 635 uint32_t chain_len = 0;
abc490a1 636
11519af6
MD
637 /*
638 * iter_prev points to the non-removed node prior to the
639 * insert location.
11519af6 640 */
24365af7
MD
641 index = hash & (t->size - 1);
642 order = get_count_order_ulong(index + 1);
643 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
14044b37 644 iter_prev = (struct cds_lfht_node *) lookup;
11519af6 645 /* We can always skip the dummy node initially */
cc4fcb10
MD
646 iter = rcu_dereference(iter_prev->p.next);
647 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
abc490a1 648 for (;;) {
a2974903 649 if (unlikely(!clear_flag(iter)))
273399de 650 goto insert;
76412f24 651 if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
273399de 652 goto insert;
cc4fcb10 653 next = rcu_dereference(clear_flag(iter)->p.next);
76412f24 654 if (unlikely(is_removed(next)))
9dba85be 655 goto gc_node;
e43f23f8 656 if (unique
1b81fe1a 657 && !is_dummy(next)
e43f23f8
MD
658 && !ht->compare_fct(node->key, node->key_len,
659 clear_flag(iter)->key,
660 clear_flag(iter)->key_len))
18117871 661 return clear_flag(iter);
11519af6 662 /* Only account for identical reverse hash once */
24365af7
MD
663 if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
664 && !is_dummy(next))
11519af6
MD
665 check_resize(ht, t, ++chain_len);
666 iter_prev = clear_flag(iter);
273399de 667 iter = next;
abc490a1 668 }
273399de 669 insert:
7ec59d3b 670 assert(node != clear_flag(iter));
11519af6 671 assert(!is_removed(iter_prev));
f000907d 672 assert(iter_prev != node);
f5596c94 673 if (!dummy)
1b81fe1a 674 node->p.next = clear_flag(iter);
f5596c94 675 else
1b81fe1a 676 node->p.next = flag_dummy(clear_flag(iter));
f5596c94
MD
677 if (is_dummy(iter))
678 new_node = flag_dummy(node);
679 else
680 new_node = node;
cc4fcb10 681 if (uatomic_cmpxchg(&iter_prev->p.next, iter,
f5596c94 682 new_node) != iter)
273399de 683 continue; /* retry */
11519af6 684 else
273399de 685 goto gc_end;
9dba85be
MD
686 gc_node:
687 assert(!is_removed(iter));
f5596c94
MD
688 if (is_dummy(iter))
689 new_next = flag_dummy(clear_flag(next));
690 else
691 new_next = clear_flag(next);
692 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de 693 /* retry */
464a1ec9 694 }
273399de
MD
695gc_end:
696 /* Garbage collect logically removed nodes in the bucket */
24365af7
MD
697 index = hash & (t->size - 1);
698 order = get_count_order_ulong(index + 1);
699 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
14044b37
MD
700 dummy_node = (struct cds_lfht_node *) lookup;
701 _cds_lfht_gc_bucket(dummy_node, node);
18117871 702 return node;
abc490a1 703}
464a1ec9 704
abc490a1 705static
14044b37
MD
706int _cds_lfht_remove(struct cds_lfht *ht, struct rcu_table *t,
707 struct cds_lfht_node *node)
abc490a1 708{
14044b37
MD
709 struct cds_lfht_node *dummy, *next, *old;
710 struct _cds_lfht_node *lookup;
abc490a1 711 int flagged = 0;
24365af7 712 unsigned long hash, index, order;
5e28c532 713
7ec59d3b 714 /* logically delete the node */
cc4fcb10 715 old = rcu_dereference(node->p.next);
7ec59d3b
MD
716 do {
717 next = old;
76412f24 718 if (unlikely(is_removed(next)))
7ec59d3b 719 goto end;
1b81fe1a 720 assert(!is_dummy(next));
cc4fcb10 721 old = uatomic_cmpxchg(&node->p.next, next,
7ec59d3b
MD
722 flag_removed(next));
723 } while (old != next);
724
725 /* We performed the (logical) deletion. */
726 flagged = 1;
727
728 /*
729 * Ensure that the node is not visible to readers anymore: lookup for
273399de
MD
730 * the node, and remove it (along with any other logically removed node)
731 * if found.
11519af6 732 */
cc4fcb10 733 hash = bit_reverse_ulong(node->p.reverse_hash);
24365af7
MD
734 index = hash & (t->size - 1);
735 order = get_count_order_ulong(index + 1);
736 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
14044b37
MD
737 dummy = (struct cds_lfht_node *) lookup;
738 _cds_lfht_gc_bucket(dummy, node);
2ed95849 739end:
11519af6
MD
740 /*
741 * Only the flagging action indicated that we (and no other)
742 * removed the node from the hash.
743 */
7ec59d3b 744 if (flagged) {
cc4fcb10 745 assert(is_removed(rcu_dereference(node->p.next)));
11519af6 746 return 0;
7ec59d3b 747 } else
11519af6 748 return -ENOENT;
abc490a1 749}
2ed95849 750
abc490a1 751static
14044b37 752void init_table(struct cds_lfht *ht, struct rcu_table *t,
24365af7
MD
753 unsigned long first_order, unsigned long len_order)
754{
755 unsigned long i, end_order;
756
f0c29ed7 757 dbg_printf("init table: first_order %lu end_order %lu\n",
24365af7
MD
758 first_order, first_order + len_order);
759 end_order = first_order + len_order;
760 t->size = !first_order ? 0 : (1UL << (first_order - 1));
761 for (i = first_order; i < end_order; i++) {
762 unsigned long j, len;
763
764 len = !i ? 1 : 1UL << (i - 1);
f0c29ed7 765 dbg_printf("init order %lu len: %lu\n", i, len);
14044b37 766 t->tbl[i] = calloc(len, sizeof(struct _cds_lfht_node));
24365af7 767 for (j = 0; j < len; j++) {
f0c29ed7 768 dbg_printf("init entry: i %lu j %lu hash %lu\n",
24365af7 769 i, j, !i ? 0 : (1UL << (i - 1)) + j);
14044b37
MD
770 struct cds_lfht_node *new_node =
771 (struct cds_lfht_node *) &t->tbl[i][j];
24365af7
MD
772 new_node->p.reverse_hash =
773 bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
14044b37 774 (void) _cds_lfht_add(ht, t, new_node, 0, 1);
33c7c748
MD
775 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
776 break;
24365af7
MD
777 }
778 /* Update table size */
779 t->size = !i ? 1 : (1UL << i);
f0c29ed7 780 dbg_printf("init new size: %lu\n", t->size);
33c7c748
MD
781 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
782 break;
abc490a1 783 }
24365af7 784 t->resize_target = t->size;
11519af6 785 t->resize_initiated = 0;
2ed95849
MD
786}
787
14044b37
MD
788struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
789 cds_lfht_compare_fct compare_fct,
790 unsigned long hash_seed,
791 unsigned long init_size,
792 void (*cds_lfht_call_rcu)(struct rcu_head *head,
793 void (*func)(struct rcu_head *head)))
abc490a1 794{
14044b37 795 struct cds_lfht *ht;
24365af7 796 unsigned long order;
abc490a1 797
8129be4e 798 /* init_size must be power of two */
49619ea0 799 if (init_size && (init_size & (init_size - 1)))
8129be4e 800 return NULL;
14044b37 801 ht = calloc(1, sizeof(struct cds_lfht));
abc490a1 802 ht->hash_fct = hash_fct;
732ad076
MD
803 ht->compare_fct = compare_fct;
804 ht->hash_seed = hash_seed;
14044b37 805 ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
848d4088 806 ht->in_progress_resize = 0;
df44348d 807 ht->percpu_count = alloc_per_cpu_items_count();
abc490a1
MD
808 /* this mutex should not nest in read-side C.S. */
809 pthread_mutex_init(&ht->resize_mutex, NULL);
24365af7 810 order = get_count_order_ulong(max(init_size, 1)) + 1;
14044b37
MD
811 ht->t = calloc(1, sizeof(struct cds_lfht)
812 + (order * sizeof(struct _cds_lfht_node *)));
abc490a1 813 ht->t->size = 0;
f000907d 814 pthread_mutex_lock(&ht->resize_mutex);
24365af7 815 init_table(ht, ht->t, 0, order);
f000907d 816 pthread_mutex_unlock(&ht->resize_mutex);
abc490a1
MD
817 return ht;
818}
819
14044b37 820struct cds_lfht_node *cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len)
2ed95849 821{
395270b6 822 struct rcu_table *t;
14044b37
MD
823 struct cds_lfht_node *node, *next;
824 struct _cds_lfht_node *lookup;
24365af7 825 unsigned long hash, reverse_hash, index, order;
2ed95849 826
732ad076 827 hash = ht->hash_fct(key, key_len, ht->hash_seed);
abc490a1 828 reverse_hash = bit_reverse_ulong(hash);
464a1ec9 829
395270b6 830 t = rcu_dereference(ht->t);
24365af7
MD
831 index = hash & (t->size - 1);
832 order = get_count_order_ulong(index + 1);
833 lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)];
f0c29ed7 834 dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n",
24365af7 835 hash, index, order, index & ((1UL << (order - 1)) - 1));
14044b37 836 node = (struct cds_lfht_node *) lookup;
2ed95849 837 for (;;) {
abc490a1
MD
838 if (unlikely(!node))
839 break;
cc4fcb10 840 if (unlikely(node->p.reverse_hash > reverse_hash)) {
abc490a1
MD
841 node = NULL;
842 break;
2ed95849 843 }
1b81fe1a
MD
844 next = rcu_dereference(node->p.next);
845 if (likely(!is_removed(next))
846 && !is_dummy(next)
49c2e2d6 847 && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
273399de 848 break;
2ed95849 849 }
1b81fe1a 850 node = clear_flag(next);
2ed95849 851 }
1b81fe1a 852 assert(!node || !is_dummy(rcu_dereference(node->p.next)));
abc490a1
MD
853 return node;
854}
e0ba718a 855
a481e5ff
MD
856struct cds_lfht_node *cds_lfht_next(struct cds_lfht *ht,
857 struct cds_lfht_node *node)
858{
859 struct cds_lfht_node *next;
860 unsigned long reverse_hash;
861 void *key;
862 size_t key_len;
863
864 reverse_hash = node->p.reverse_hash;
865 key = node->key;
866 key_len = node->key_len;
867 next = rcu_dereference(node->p.next);
868 node = clear_flag(next);
869
870 for (;;) {
871 if (unlikely(!node))
872 break;
873 if (unlikely(node->p.reverse_hash > reverse_hash)) {
874 node = NULL;
875 break;
876 }
877 next = rcu_dereference(node->p.next);
878 if (likely(!is_removed(next))
879 && !is_dummy(next)
880 && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
881 break;
882 }
883 node = clear_flag(next);
884 }
885 assert(!node || !is_dummy(rcu_dereference(node->p.next)));
886 return node;
887}
888
14044b37 889void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
abc490a1
MD
890{
891 struct rcu_table *t;
49c2e2d6 892 unsigned long hash;
ab7d5fc6 893
49c2e2d6 894 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 895 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
2ed95849 896
abc490a1 897 t = rcu_dereference(ht->t);
14044b37 898 (void) _cds_lfht_add(ht, t, node, 0, 0);
df44348d 899 ht_count_add(ht, t);
3eca1b8c
MD
900}
901
14044b37
MD
902struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
903 struct cds_lfht_node *node)
3eca1b8c
MD
904{
905 struct rcu_table *t;
49c2e2d6 906 unsigned long hash;
df44348d 907 struct cds_lfht_node *ret;
3eca1b8c 908
49c2e2d6 909 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 910 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
3eca1b8c
MD
911
912 t = rcu_dereference(ht->t);
df44348d
MD
913 ret = _cds_lfht_add(ht, t, node, 1, 0);
914 if (ret != node)
915 ht_count_add(ht, t);
916 return ret;
2ed95849
MD
917}
918
14044b37 919int cds_lfht_remove(struct cds_lfht *ht, struct cds_lfht_node *node)
2ed95849 920{
abc490a1 921 struct rcu_table *t;
df44348d 922 int ret;
abc490a1
MD
923
924 t = rcu_dereference(ht->t);
df44348d
MD
925 ret = _cds_lfht_remove(ht, t, node);
926 if (!ret)
927 ht_count_remove(ht, t);
928 return ret;
2ed95849 929}
ab7d5fc6 930
abc490a1 931static
14044b37 932int cds_lfht_delete_dummy(struct cds_lfht *ht)
674f7a69 933{
395270b6 934 struct rcu_table *t;
14044b37
MD
935 struct cds_lfht_node *node;
936 struct _cds_lfht_node *lookup;
24365af7 937 unsigned long order, i;
674f7a69 938
abc490a1
MD
939 t = ht->t;
940 /* Check that the table is empty */
24365af7 941 lookup = &t->tbl[0][0];
14044b37 942 node = (struct cds_lfht_node *) lookup;
abc490a1 943 do {
1b81fe1a
MD
944 node = clear_flag(node)->p.next;
945 if (!is_dummy(node))
abc490a1 946 return -EPERM;
273399de 947 assert(!is_removed(node));
a2974903 948 } while (clear_flag(node));
abc490a1 949 /* Internal sanity check: all nodes left should be dummy */
24365af7
MD
950 for (order = 0; order < get_count_order_ulong(t->size) + 1; order++) {
951 unsigned long len;
952
953 len = !order ? 1 : 1UL << (order - 1);
954 for (i = 0; i < len; i++) {
f0c29ed7 955 dbg_printf("delete order %lu i %lu hash %lu\n",
24365af7
MD
956 order, i,
957 bit_reverse_ulong(t->tbl[order][i].reverse_hash));
958 assert(is_dummy(t->tbl[order][i].next));
959 }
960 free(t->tbl[order]);
674f7a69 961 }
abc490a1 962 return 0;
674f7a69
MD
963}
964
965/*
966 * Should only be called when no more concurrent readers nor writers can
967 * possibly access the table.
968 */
14044b37 969int cds_lfht_destroy(struct cds_lfht *ht)
674f7a69 970{
5e28c532
MD
971 int ret;
972
848d4088 973 /* Wait for in-flight resize operations to complete */
33c7c748 974 CMM_STORE_SHARED(ht->in_progress_destroy, 1);
848d4088
MD
975 while (uatomic_read(&ht->in_progress_resize))
976 poll(NULL, 0, 100); /* wait for 100ms */
14044b37 977 ret = cds_lfht_delete_dummy(ht);
abc490a1
MD
978 if (ret)
979 return ret;
395270b6 980 free(ht->t);
df44348d 981 free_per_cpu_items_count(ht->percpu_count);
674f7a69 982 free(ht);
5e28c532 983 return ret;
674f7a69
MD
984}
985
14044b37 986void cds_lfht_count_nodes(struct cds_lfht *ht,
273399de
MD
987 unsigned long *count,
988 unsigned long *removed)
989{
990 struct rcu_table *t;
14044b37
MD
991 struct cds_lfht_node *node, *next;
992 struct _cds_lfht_node *lookup;
24365af7 993 unsigned long nr_dummy = 0;
273399de
MD
994
995 *count = 0;
996 *removed = 0;
997
998 t = rcu_dereference(ht->t);
24365af7
MD
999 /* Count non-dummy nodes in the table */
1000 lookup = &t->tbl[0][0];
14044b37 1001 node = (struct cds_lfht_node *) lookup;
273399de 1002 do {
cc4fcb10 1003 next = rcu_dereference(node->p.next);
273399de 1004 if (is_removed(next)) {
1b81fe1a 1005 assert(!is_dummy(next));
273399de 1006 (*removed)++;
1b81fe1a 1007 } else if (!is_dummy(next))
273399de 1008 (*count)++;
24365af7
MD
1009 else
1010 (nr_dummy)++;
273399de
MD
1011 node = clear_flag(next);
1012 } while (node);
f0c29ed7 1013 dbg_printf("number of dummy nodes: %lu\n", nr_dummy);
273399de
MD
1014}
1015
abc490a1 1016static
14044b37 1017void cds_lfht_free_table_cb(struct rcu_head *head)
abc490a1
MD
1018{
1019 struct rcu_table *t =
1020 caa_container_of(head, struct rcu_table, head);
1021 free(t);
1022}
1023
1024/* called with resize mutex held */
1025static
14044b37 1026void _do_cds_lfht_resize(struct cds_lfht *ht)
464a1ec9 1027{
24365af7 1028 unsigned long new_size, old_size, old_order, new_order;
395270b6 1029 struct rcu_table *new_t, *old_t;
464a1ec9 1030
395270b6
MD
1031 old_t = ht->t;
1032 old_size = old_t->size;
24365af7 1033 old_order = get_count_order_ulong(old_size) + 1;
464a1ec9 1034
f9830efd 1035 new_size = CMM_LOAD_SHARED(old_t->resize_target);
abc490a1 1036 if (old_size == new_size)
464a1ec9 1037 return;
24365af7 1038 new_order = get_count_order_ulong(new_size) + 1;
df44348d 1039 printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
df03fab8 1040 old_size, old_order, new_size, new_order);
14044b37
MD
1041 new_t = malloc(sizeof(struct cds_lfht)
1042 + (new_order * sizeof(struct _cds_lfht_node *)));
f000907d
MD
1043 assert(new_size > old_size);
1044 memcpy(&new_t->tbl, &old_t->tbl,
14044b37 1045 old_order * sizeof(struct _cds_lfht_node *));
24365af7 1046 init_table(ht, new_t, old_order, new_order - old_order);
f000907d
MD
1047 /* Changing table and size atomically wrt lookups */
1048 rcu_assign_pointer(ht->t, new_t);
14044b37 1049 ht->cds_lfht_call_rcu(&old_t->head, cds_lfht_free_table_cb);
464a1ec9
MD
1050}
1051
abc490a1 1052static
f9830efd
MD
1053unsigned long resize_target_update(struct rcu_table *t,
1054 int growth_order)
464a1ec9 1055{
f9830efd
MD
1056 return _uatomic_max(&t->resize_target,
1057 t->size << growth_order);
464a1ec9
MD
1058}
1059
14044b37 1060void cds_lfht_resize(struct cds_lfht *ht, int growth)
464a1ec9 1061{
f9830efd
MD
1062 struct rcu_table *t = rcu_dereference(ht->t);
1063 unsigned long target_size;
1064
f0c29ed7
MD
1065 if (growth < 0) {
1066 /*
1067 * Silently refuse to shrink hash table. (not supported)
1068 */
1069 dbg_printf("shrinking hash table not supported.\n");
1070 return;
1071 }
1072
f9830efd
MD
1073 target_size = resize_target_update(t, growth);
1074 if (t->size < target_size) {
11519af6 1075 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd 1076 pthread_mutex_lock(&ht->resize_mutex);
14044b37 1077 _do_cds_lfht_resize(ht);
f9830efd
MD
1078 pthread_mutex_unlock(&ht->resize_mutex);
1079 }
abc490a1 1080}
464a1ec9 1081
abc490a1
MD
1082static
1083void do_resize_cb(struct rcu_head *head)
1084{
1085 struct rcu_resize_work *work =
1086 caa_container_of(head, struct rcu_resize_work, head);
14044b37 1087 struct cds_lfht *ht = work->ht;
abc490a1
MD
1088
1089 pthread_mutex_lock(&ht->resize_mutex);
14044b37 1090 _do_cds_lfht_resize(ht);
abc490a1
MD
1091 pthread_mutex_unlock(&ht->resize_mutex);
1092 free(work);
848d4088
MD
1093 cmm_smp_mb(); /* finish resize before decrement */
1094 uatomic_dec(&ht->in_progress_resize);
464a1ec9
MD
1095}
1096
abc490a1 1097static
14044b37 1098void cds_lfht_resize_lazy(struct cds_lfht *ht, struct rcu_table *t, int growth)
ab7d5fc6 1099{
abc490a1 1100 struct rcu_resize_work *work;
f9830efd 1101 unsigned long target_size;
abc490a1 1102
f9830efd 1103 target_size = resize_target_update(t, growth);
11519af6 1104 if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
848d4088
MD
1105 uatomic_inc(&ht->in_progress_resize);
1106 cmm_smp_mb(); /* increment resize count before calling it */
f9830efd
MD
1107 work = malloc(sizeof(*work));
1108 work->ht = ht;
14044b37 1109 ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
11519af6 1110 CMM_STORE_SHARED(t->resize_initiated, 1);
f9830efd 1111 }
ab7d5fc6 1112}
3171717f 1113
f8994aee
MD
1114#if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF)
1115
1116static
1117unsigned long resize_target_update_count(struct rcu_table *t,
1118 unsigned long count)
1119{
88d05815 1120 return uatomic_set(&t->resize_target, count);
f8994aee
MD
1121}
1122
3171717f
MD
1123static
1124void cds_lfht_resize_lazy_count(struct cds_lfht *ht, struct rcu_table *t,
1125 unsigned long count)
1126{
1127 struct rcu_resize_work *work;
1128 unsigned long target_size;
1129
1130 target_size = resize_target_update_count(t, count);
1131 if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
1132 uatomic_inc(&ht->in_progress_resize);
1133 cmm_smp_mb(); /* increment resize count before calling it */
1134 work = malloc(sizeof(*work));
1135 work->ht = ht;
1136 ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
1137 CMM_STORE_SHARED(t->resize_initiated, 1);
1138 }
1139}
f8994aee
MD
1140
1141#endif
This page took 0.130945 seconds and 4 git commands to generate.