rculfhash: help scheme: fix end node, insertion, and lookups
[urcu.git] / rculfhash.c
CommitLineData
5e28c532 1/*
abc490a1
MD
2 * rculfhash.c
3 *
1475579c 4 * Userspace RCU library - Lock-Free Resizable RCU Hash Table
abc490a1
MD
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 *
1475579c 32 * Some specificities of this Lock-Free Resizable RCU Hash Table
e753ff5a
MD
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.
1475579c
MD
51 * - The resize operation for small tables only allows expanding the hash table.
52 * It is triggered automatically by detecting long chains in the add
53 * operation.
54 * - The resize operation for larger tables (and available through an
55 * API) allows both expanding and shrinking the hash table.
56 * - Per-CPU Split-counters are used to keep track of the number of
57 * nodes within the hash table for automatic resize triggering.
e753ff5a
MD
58 * - Resize operation initiated by long chain detection is executed by a
59 * call_rcu thread, which keeps lock-freedom of add and remove.
60 * - Resize operations are protected by a mutex.
61 * - The removal operation is split in two parts: first, a "removed"
62 * flag is set in the next pointer within the node to remove. Then,
63 * a "garbage collection" is performed in the bucket containing the
64 * removed node (from the start of the bucket up to the removed node).
65 * All encountered nodes with "removed" flag set in their next
66 * pointers are removed from the linked-list. If the cmpxchg used for
67 * removal fails (due to concurrent garbage-collection or concurrent
68 * add), we retry from the beginning of the bucket. This ensures that
69 * the node with "removed" flag set is removed from the hash table
70 * (not visible to lookups anymore) before the RCU read-side critical
71 * section held across removal ends. Furthermore, this ensures that
72 * the node with "removed" flag set is removed from the linked-list
73 * before its memory is reclaimed. Only the thread which removal
74 * successfully set the "removed" flag (with a cmpxchg) into a node's
75 * next pointer is considered to have succeeded its removal (and thus
76 * owns the node to reclaim). Because we garbage-collect starting from
77 * an invariant node (the start-of-bucket dummy node) up to the
78 * "removed" node (or find a reverse-hash that is higher), we are sure
79 * that a successful traversal of the chain leads to a chain that is
80 * present in the linked-list (the start node is never removed) and
81 * that is does not contain the "removed" node anymore, even if
82 * concurrent delete/add operations are changing the structure of the
83 * list concurrently.
29e669f6
MD
84 * - The add operation performs gargage collection of buckets if it
85 * encounters nodes with removed flag set in the bucket where it wants
86 * to add its new node. This ensures lock-freedom of add operation by
87 * helping the remover unlink nodes from the list rather than to wait
88 * for it do to so.
e753ff5a
MD
89 * - A RCU "order table" indexed by log2(hash index) is copied and
90 * expanded by the resize operation. This order table allows finding
91 * the "dummy node" tables.
92 * - There is one dummy node table per hash index order. The size of
93 * each dummy node table is half the number of hashes contained in
94 * this order.
95 * - call_rcu is used to garbage-collect the old order table.
96 * - The per-order dummy node tables contain a compact version of the
97 * hash table nodes. These tables are invariant after they are
98 * populated into the hash table.
1475579c
MD
99 *
100 * A bit of ascii art explanation:
101 *
102 * Order index is the off-by-one compare to the actual power of 2 because
103 * we use index 0 to deal with the 0 special-case.
104 *
105 * This shows the nodes for a small table ordered by reversed bits:
106 *
107 * bits reverse
108 * 0 000 000
109 * 4 100 001
110 * 2 010 010
111 * 6 110 011
112 * 1 001 100
113 * 5 101 101
114 * 3 011 110
115 * 7 111 111
116 *
117 * This shows the nodes in order of non-reversed bits, linked by
118 * reversed-bit order.
119 *
120 * order bits reverse
121 * 0 0 000 000
122 * |
f6fdd688
MD
123 * 1 | 1 001 100 <- <-
124 * | | | |
125 * 2 | | 2 010 010 | |
126 * | | | 3 011 110 | <- |
127 * | | | | | | |
1475579c
MD
128 * 3 -> | | | 4 100 001 | |
129 * -> | | 5 101 101 |
130 * -> | 6 110 011
131 * -> 7 111 111
e753ff5a
MD
132 */
133
2ed95849
MD
134#define _LGPL_SOURCE
135#include <stdlib.h>
e0ba718a
MD
136#include <errno.h>
137#include <assert.h>
138#include <stdio.h>
abc490a1 139#include <stdint.h>
f000907d 140#include <string.h>
e0ba718a 141
df44348d 142#include "config.h"
2ed95849 143#include <urcu.h>
abc490a1 144#include <urcu-call-rcu.h>
a42cc659
MD
145#include <urcu/arch.h>
146#include <urcu/uatomic.h>
674f7a69 147#include <urcu/jhash.h>
a42cc659 148#include <urcu/compiler.h>
abc490a1 149#include <urcu/rculfhash.h>
5e28c532 150#include <stdio.h>
464a1ec9 151#include <pthread.h>
44395fb7 152
f9830efd 153#ifdef DEBUG
f0c29ed7 154#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
f9830efd 155#else
e753ff5a 156#define dbg_printf(fmt, args...)
f9830efd
MD
157#endif
158
f8994aee
MD
159/*
160 * Per-CPU split-counters lazily update the global counter each 1024
161 * addition/removal. It automatically keeps track of resize required.
162 * We use the bucket length as indicator for need to expand for small
163 * tables and machines lacking per-cpu data suppport.
164 */
165#define COUNT_COMMIT_ORDER 10
6ea6bc67
MD
166#define CHAIN_LEN_TARGET 1
167#define CHAIN_LEN_RESIZE_THRESHOLD 3
2ed95849 168
cd95516d 169/*
76a73da8 170 * Define the minimum table size.
cd95516d
MD
171 */
172#define MIN_TABLE_SIZE 128
173
4105056a
MD
174#if (CAA_BITS_PER_LONG == 32)
175#define MAX_TABLE_ORDER 32
176#else
177#define MAX_TABLE_ORDER 64
178#endif
179
180#ifndef min
181#define min(a, b) ((a) < (b) ? (a) : (b))
182#endif
183
abc490a1
MD
184#ifndef max
185#define max(a, b) ((a) > (b) ? (a) : (b))
186#endif
2ed95849 187
d95bd160
MD
188/*
189 * The removed flag needs to be updated atomically with the pointer.
190 * The dummy flag does not require to be updated atomically with the
191 * pointer, but it is added as a pointer low bit flag to save space.
192 */
d37166c6 193#define REMOVED_FLAG (1UL << 0)
f5596c94
MD
194#define DUMMY_FLAG (1UL << 1)
195#define FLAGS_MASK ((1UL << 2) - 1)
d37166c6 196
bb7b2f26
MD
197/* Value of the end pointer. Should not interact with flags. */
198#define END_VALUE 0x4
199
df44348d 200struct ht_items_count {
3171717f 201 unsigned long add, remove;
df44348d
MD
202} __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
203
1475579c
MD
204struct rcu_level {
205 struct rcu_head head;
206 struct _cds_lfht_node nodes[0];
207};
208
395270b6 209struct rcu_table {
4105056a 210 unsigned long size; /* always a power of 2, shared (RCU) */
f9830efd 211 unsigned long resize_target;
11519af6 212 int resize_initiated;
4105056a 213 struct rcu_level *tbl[MAX_TABLE_ORDER];
395270b6
MD
214};
215
14044b37 216struct cds_lfht {
4105056a 217 struct rcu_table t;
14044b37
MD
218 cds_lfht_hash_fct hash_fct;
219 cds_lfht_compare_fct compare_fct;
732ad076 220 unsigned long hash_seed;
b8af5011 221 int flags;
5f511391
MD
222 /*
223 * We need to put the work threads offline (QSBR) when taking this
224 * mutex, because we use synchronize_rcu within this mutex critical
225 * section, which waits on read-side critical sections, and could
226 * therefore cause grace-period deadlock if we hold off RCU G.P.
227 * completion.
228 */
464a1ec9 229 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
33c7c748 230 unsigned int in_progress_resize, in_progress_destroy;
14044b37 231 void (*cds_lfht_call_rcu)(struct rcu_head *head,
abc490a1 232 void (*func)(struct rcu_head *head));
1475579c 233 void (*cds_lfht_synchronize_rcu)(void);
01dbfa62
MD
234 void (*cds_lfht_rcu_read_lock)(void);
235 void (*cds_lfht_rcu_read_unlock)(void);
5f511391
MD
236 void (*cds_lfht_rcu_thread_offline)(void);
237 void (*cds_lfht_rcu_thread_online)(void);
df44348d
MD
238 unsigned long count; /* global approximate item count */
239 struct ht_items_count *percpu_count; /* per-cpu item count */
2ed95849
MD
240};
241
abc490a1
MD
242struct rcu_resize_work {
243 struct rcu_head head;
14044b37 244 struct cds_lfht *ht;
abc490a1 245};
2ed95849 246
76a73da8
MD
247static
248struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
249 unsigned long size,
250 struct cds_lfht_node *node,
251 int unique, int dummy);
252
abc490a1
MD
253/*
254 * Algorithm to reverse bits in a word by lookup table, extended to
255 * 64-bit words.
f9830efd 256 * Source:
abc490a1 257 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
f9830efd 258 * Originally from Public Domain.
abc490a1
MD
259 */
260
261static const uint8_t BitReverseTable256[256] =
2ed95849 262{
abc490a1
MD
263#define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
264#define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
265#define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
266 R6(0), R6(2), R6(1), R6(3)
267};
268#undef R2
269#undef R4
270#undef R6
2ed95849 271
abc490a1
MD
272static
273uint8_t bit_reverse_u8(uint8_t v)
274{
275 return BitReverseTable256[v];
276}
ab7d5fc6 277
abc490a1
MD
278static __attribute__((unused))
279uint32_t bit_reverse_u32(uint32_t v)
280{
281 return ((uint32_t) bit_reverse_u8(v) << 24) |
282 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
283 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
284 ((uint32_t) bit_reverse_u8(v >> 24));
2ed95849
MD
285}
286
abc490a1
MD
287static __attribute__((unused))
288uint64_t bit_reverse_u64(uint64_t v)
2ed95849 289{
abc490a1
MD
290 return ((uint64_t) bit_reverse_u8(v) << 56) |
291 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
292 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
293 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
294 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
295 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
296 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
297 ((uint64_t) bit_reverse_u8(v >> 56));
298}
299
300static
301unsigned long bit_reverse_ulong(unsigned long v)
302{
303#if (CAA_BITS_PER_LONG == 32)
304 return bit_reverse_u32(v);
305#else
306 return bit_reverse_u64(v);
307#endif
308}
309
f9830efd 310/*
24365af7
MD
311 * fls: returns the position of the most significant bit.
312 * Returns 0 if no bit is set, else returns the position of the most
313 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
f9830efd 314 */
24365af7
MD
315#if defined(__i386) || defined(__x86_64)
316static inline
317unsigned int fls_u32(uint32_t x)
f9830efd 318{
24365af7
MD
319 int r;
320
321 asm("bsrl %1,%0\n\t"
322 "jnz 1f\n\t"
323 "movl $-1,%0\n\t"
324 "1:\n\t"
325 : "=r" (r) : "rm" (x));
326 return r + 1;
327}
328#define HAS_FLS_U32
329#endif
330
331#if defined(__x86_64)
332static inline
333unsigned int fls_u64(uint64_t x)
334{
335 long r;
336
337 asm("bsrq %1,%0\n\t"
338 "jnz 1f\n\t"
339 "movq $-1,%0\n\t"
340 "1:\n\t"
341 : "=r" (r) : "rm" (x));
342 return r + 1;
343}
344#define HAS_FLS_U64
345#endif
346
347#ifndef HAS_FLS_U64
348static __attribute__((unused))
349unsigned int fls_u64(uint64_t x)
350{
351 unsigned int r = 64;
352
353 if (!x)
354 return 0;
355
356 if (!(x & 0xFFFFFFFF00000000ULL)) {
357 x <<= 32;
358 r -= 32;
359 }
360 if (!(x & 0xFFFF000000000000ULL)) {
361 x <<= 16;
362 r -= 16;
363 }
364 if (!(x & 0xFF00000000000000ULL)) {
365 x <<= 8;
366 r -= 8;
367 }
368 if (!(x & 0xF000000000000000ULL)) {
369 x <<= 4;
370 r -= 4;
371 }
372 if (!(x & 0xC000000000000000ULL)) {
373 x <<= 2;
374 r -= 2;
375 }
376 if (!(x & 0x8000000000000000ULL)) {
377 x <<= 1;
378 r -= 1;
379 }
380 return r;
381}
382#endif
383
384#ifndef HAS_FLS_U32
385static __attribute__((unused))
386unsigned int fls_u32(uint32_t x)
387{
388 unsigned int r = 32;
f9830efd 389
24365af7
MD
390 if (!x)
391 return 0;
392 if (!(x & 0xFFFF0000U)) {
393 x <<= 16;
394 r -= 16;
395 }
396 if (!(x & 0xFF000000U)) {
397 x <<= 8;
398 r -= 8;
399 }
400 if (!(x & 0xF0000000U)) {
401 x <<= 4;
402 r -= 4;
403 }
404 if (!(x & 0xC0000000U)) {
405 x <<= 2;
406 r -= 2;
407 }
408 if (!(x & 0x80000000U)) {
409 x <<= 1;
410 r -= 1;
411 }
412 return r;
413}
414#endif
415
416unsigned int fls_ulong(unsigned long x)
f9830efd 417{
24365af7
MD
418#if (CAA_BITS_PER_lONG == 32)
419 return fls_u32(x);
420#else
421 return fls_u64(x);
422#endif
423}
f9830efd 424
24365af7
MD
425int get_count_order_u32(uint32_t x)
426{
427 int order;
428
429 order = fls_u32(x) - 1;
430 if (x & (x - 1))
431 order++;
432 return order;
433}
434
435int get_count_order_ulong(unsigned long x)
436{
437 int order;
438
439 order = fls_ulong(x) - 1;
440 if (x & (x - 1))
441 order++;
442 return order;
f9830efd
MD
443}
444
98808fb1
MD
445#ifdef POISON_FREE
446#define poison_free(ptr) \
447 do { \
448 memset(ptr, 0x42, sizeof(*(ptr))); \
449 free(ptr); \
450 } while (0)
451#else
452#define poison_free(ptr) free(ptr)
453#endif
454
f9830efd 455static
4105056a 456void cds_lfht_resize_lazy(struct cds_lfht *ht, unsigned long size, int growth);
f9830efd 457
df44348d
MD
458/*
459 * If the sched_getcpu() and sysconf(_SC_NPROCESSORS_CONF) calls are
460 * available, then we support hash table item accounting.
461 * In the unfortunate event the number of CPUs reported would be
462 * inaccurate, we use modulo arithmetic on the number of CPUs we got.
463 */
df44348d
MD
464#if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF)
465
f8994aee 466static
4105056a 467void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
f8994aee
MD
468 unsigned long count);
469
df44348d
MD
470static long nr_cpus_mask = -1;
471
472static
473struct ht_items_count *alloc_per_cpu_items_count(void)
474{
475 struct ht_items_count *count;
476
477 switch (nr_cpus_mask) {
478 case -2:
479 return NULL;
480 case -1:
481 {
482 long maxcpus;
483
484 maxcpus = sysconf(_SC_NPROCESSORS_CONF);
485 if (maxcpus <= 0) {
486 nr_cpus_mask = -2;
487 return NULL;
488 }
489 /*
490 * round up number of CPUs to next power of two, so we
491 * can use & for modulo.
492 */
493 maxcpus = 1UL << get_count_order_ulong(maxcpus);
494 nr_cpus_mask = maxcpus - 1;
495 }
496 /* Fall-through */
497 default:
498 return calloc(nr_cpus_mask + 1, sizeof(*count));
499 }
500}
501
502static
503void free_per_cpu_items_count(struct ht_items_count *count)
504{
98808fb1 505 poison_free(count);
df44348d
MD
506}
507
508static
509int ht_get_cpu(void)
510{
511 int cpu;
512
513 assert(nr_cpus_mask >= 0);
514 cpu = sched_getcpu();
515 if (unlikely(cpu < 0))
516 return cpu;
517 else
518 return cpu & nr_cpus_mask;
519}
520
521static
4105056a 522void ht_count_add(struct cds_lfht *ht, unsigned long size)
df44348d 523{
3171717f 524 unsigned long percpu_count;
df44348d
MD
525 int cpu;
526
527 if (unlikely(!ht->percpu_count))
3171717f 528 return;
df44348d
MD
529 cpu = ht_get_cpu();
530 if (unlikely(cpu < 0))
3171717f
MD
531 return;
532 percpu_count = uatomic_add_return(&ht->percpu_count[cpu].add, 1);
df44348d
MD
533 if (unlikely(!(percpu_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))) {
534 unsigned long count;
535
536 dbg_printf("add percpu %lu\n", percpu_count);
537 count = uatomic_add_return(&ht->count,
538 1UL << COUNT_COMMIT_ORDER);
539 /* If power of 2 */
540 if (!(count & (count - 1))) {
4105056a 541 if ((count >> CHAIN_LEN_RESIZE_THRESHOLD) < size)
f8994aee
MD
542 return;
543 dbg_printf("add set global %lu\n", count);
4105056a 544 cds_lfht_resize_lazy_count(ht, size,
6ea6bc67 545 count >> (CHAIN_LEN_TARGET - 1));
df44348d
MD
546 }
547 }
548}
549
550static
4105056a 551void ht_count_remove(struct cds_lfht *ht, unsigned long size)
df44348d
MD
552{
553 unsigned long percpu_count;
3171717f 554 int cpu;
df44348d 555
3171717f
MD
556 if (unlikely(!ht->percpu_count))
557 return;
558 cpu = ht_get_cpu();
559 if (unlikely(cpu < 0))
560 return;
561 percpu_count = uatomic_add_return(&ht->percpu_count[cpu].remove, -1);
df44348d
MD
562 if (unlikely(!(percpu_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))) {
563 unsigned long count;
564
565 dbg_printf("remove percpu %lu\n", percpu_count);
566 count = uatomic_add_return(&ht->count,
3171717f 567 -(1UL << COUNT_COMMIT_ORDER));
df44348d
MD
568 /* If power of 2 */
569 if (!(count & (count - 1))) {
4105056a 570 if ((count >> CHAIN_LEN_RESIZE_THRESHOLD) >= size)
f8994aee
MD
571 return;
572 dbg_printf("remove set global %lu\n", count);
4105056a 573 cds_lfht_resize_lazy_count(ht, size,
6ea6bc67 574 count >> (CHAIN_LEN_TARGET - 1));
df44348d
MD
575 }
576 }
577}
578
579#else /* #if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF) */
580
581static const long nr_cpus_mask = -1;
582
583static
584struct ht_items_count *alloc_per_cpu_items_count(void)
585{
586 return NULL;
587}
588
589static
590void free_per_cpu_items_count(struct ht_items_count *count)
591{
592}
593
594static
4105056a 595void ht_count_add(struct cds_lfht *ht, unsigned long size)
df44348d
MD
596{
597}
598
599static
4105056a 600void ht_count_remove(struct cds_lfht *ht, unsigned long size)
df44348d
MD
601{
602}
603
604#endif /* #else #if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF) */
605
606
f9830efd 607static
4105056a 608void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len)
f9830efd 609{
f8994aee
MD
610 unsigned long count;
611
b8af5011
MD
612 if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
613 return;
f8994aee
MD
614 count = uatomic_read(&ht->count);
615 /*
616 * Use bucket-local length for small table expand and for
617 * environments lacking per-cpu data support.
618 */
619 if (count >= (1UL << COUNT_COMMIT_ORDER))
620 return;
24365af7 621 if (chain_len > 100)
f0c29ed7 622 dbg_printf("WARNING: large chain length: %u.\n",
24365af7 623 chain_len);
3390d470 624 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
4105056a 625 cds_lfht_resize_lazy(ht, size,
01370f0b 626 get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1)));
f9830efd
MD
627}
628
abc490a1 629static
14044b37 630struct cds_lfht_node *clear_flag(struct cds_lfht_node *node)
abc490a1 631{
14044b37 632 return (struct cds_lfht_node *) (((unsigned long) node) & ~FLAGS_MASK);
abc490a1
MD
633}
634
635static
14044b37 636int is_removed(struct cds_lfht_node *node)
abc490a1 637{
d37166c6 638 return ((unsigned long) node) & REMOVED_FLAG;
abc490a1
MD
639}
640
641static
14044b37 642struct cds_lfht_node *flag_removed(struct cds_lfht_node *node)
abc490a1 643{
14044b37 644 return (struct cds_lfht_node *) (((unsigned long) node) | REMOVED_FLAG);
abc490a1
MD
645}
646
f5596c94 647static
14044b37 648int is_dummy(struct cds_lfht_node *node)
f5596c94
MD
649{
650 return ((unsigned long) node) & DUMMY_FLAG;
651}
652
653static
14044b37 654struct cds_lfht_node *flag_dummy(struct cds_lfht_node *node)
f5596c94 655{
14044b37 656 return (struct cds_lfht_node *) (((unsigned long) node) | DUMMY_FLAG);
f5596c94 657}
bb7b2f26
MD
658
659static
660struct cds_lfht_node *get_end(void)
661{
662 return (struct cds_lfht_node *) END_VALUE;
663}
664
665static
666int is_end(struct cds_lfht_node *node)
667{
668 return clear_flag(node) == (struct cds_lfht_node *) END_VALUE;
669}
670
abc490a1 671static
f9830efd 672unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
abc490a1
MD
673{
674 unsigned long old1, old2;
675
676 old1 = uatomic_read(ptr);
677 do {
678 old2 = old1;
679 if (old2 >= v)
f9830efd 680 return old2;
abc490a1 681 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
f9830efd 682 return v;
abc490a1
MD
683}
684
1475579c
MD
685static
686void cds_lfht_free_level(struct rcu_head *head)
687{
688 struct rcu_level *l =
689 caa_container_of(head, struct rcu_level, head);
98808fb1 690 poison_free(l);
1475579c
MD
691}
692
273399de
MD
693/*
694 * Remove all logically deleted nodes from a bucket up to a certain node key.
695 */
696static
76a73da8 697int _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node)
273399de 698{
14044b37 699 struct cds_lfht_node *iter_prev, *iter, *next, *new_next;
273399de 700
c90201ac
MD
701 assert(!is_dummy(dummy));
702 assert(!is_removed(dummy));
703 assert(!is_dummy(node));
704 assert(!is_removed(node));
273399de
MD
705 for (;;) {
706 iter_prev = dummy;
707 /* We can always skip the dummy node initially */
cc4fcb10 708 iter = rcu_dereference(iter_prev->p.next);
76a73da8
MD
709 if (unlikely(iter == NULL)) {
710 /*
711 * We are executing concurrently with a hash table
712 * expand, so we see a dummy node with NULL next value.
713 * Help expand by linking this node into the list and
714 * retry.
715 */
716 return 1;
717 }
cc4fcb10 718 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
bd4db153
MD
719 /*
720 * We should never be called with dummy (start of chain)
721 * and logically removed node (end of path compression
722 * marker) being the actual same node. This would be a
723 * bug in the algorithm implementation.
724 */
725 assert(dummy != node);
273399de 726 for (;;) {
bb7b2f26
MD
727 assert(iter != NULL);
728 if (unlikely(is_end(iter)))
76a73da8 729 return 0;
76412f24 730 if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
76a73da8 731 return 0;
cc4fcb10 732 next = rcu_dereference(clear_flag(iter)->p.next);
76412f24 733 if (likely(is_removed(next)))
273399de 734 break;
b453eae1 735 iter_prev = clear_flag(iter);
273399de
MD
736 iter = next;
737 }
738 assert(!is_removed(iter));
f5596c94
MD
739 if (is_dummy(iter))
740 new_next = flag_dummy(clear_flag(next));
741 else
742 new_next = clear_flag(next);
bb7b2f26 743 assert(new_next != NULL);
f5596c94 744 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de 745 }
76a73da8 746 return 0;
273399de
MD
747}
748
abc490a1 749static
4105056a
MD
750struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
751 unsigned long size,
752 struct cds_lfht_node *node,
753 int unique, int dummy)
abc490a1 754{
14044b37 755 struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
f5596c94 756 *dummy_node;
14044b37 757 struct _cds_lfht_node *lookup;
24365af7 758 unsigned long hash, index, order;
bb7b2f26 759 int force_dummy = 0;
abc490a1 760
c90201ac
MD
761 assert(!is_dummy(node));
762 assert(!is_removed(node));
4105056a 763 if (!size) {
f5596c94 764 assert(dummy);
bb7b2f26 765 node->p.next = flag_dummy(get_end());
18117871
MD
766 return node; /* Initial first add (head) */
767 }
cc4fcb10 768 hash = bit_reverse_ulong(node->p.reverse_hash);
abc490a1 769 for (;;) {
f9830efd 770 uint32_t chain_len = 0;
abc490a1 771
11519af6
MD
772 /*
773 * iter_prev points to the non-removed node prior to the
774 * insert location.
11519af6 775 */
4105056a 776 index = hash & (size - 1);
24365af7 777 order = get_count_order_ulong(index + 1);
4105056a 778 lookup = &ht->t.tbl[order]->nodes[index & ((!order ? 0 : (1UL << (order - 1))) - 1)];
14044b37 779 iter_prev = (struct cds_lfht_node *) lookup;
11519af6 780 /* We can always skip the dummy node initially */
cc4fcb10 781 iter = rcu_dereference(iter_prev->p.next);
76a73da8
MD
782 if (unlikely(iter == NULL)) {
783 /*
784 * We are executing concurrently with a hash table
785 * expand, so we see a dummy node with NULL next value.
786 * Help expand by linking this node into the list and
787 * retry.
788 */
789 (void) _cds_lfht_add(ht, size >> 1, iter_prev, 0, 1);
790 continue; /* retry */
791 }
cc4fcb10 792 assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
abc490a1 793 for (;;) {
bb7b2f26 794 assert(iter != NULL);
76a73da8
MD
795 /*
796 * When adding a dummy node, we allow concurrent
797 * add/removal to help. If we find the dummy node in
798 * place, skip its insertion.
799 */
800 if (unlikely(dummy && clear_flag(iter) == node))
801 return node;
bb7b2f26 802 if (unlikely(is_end(iter)))
273399de 803 goto insert;
76412f24 804 if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
273399de 805 goto insert;
cc4fcb10 806 next = rcu_dereference(clear_flag(iter)->p.next);
76412f24 807 if (unlikely(is_removed(next)))
9dba85be 808 goto gc_node;
e43f23f8 809 if (unique
1b81fe1a 810 && !is_dummy(next)
e43f23f8
MD
811 && !ht->compare_fct(node->key, node->key_len,
812 clear_flag(iter)->key,
813 clear_flag(iter)->key_len))
18117871 814 return clear_flag(iter);
11519af6 815 /* Only account for identical reverse hash once */
24365af7
MD
816 if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
817 && !is_dummy(next))
4105056a 818 check_resize(ht, size, ++chain_len);
11519af6 819 iter_prev = clear_flag(iter);
273399de 820 iter = next;
abc490a1 821 }
273399de 822 insert:
7ec59d3b 823 assert(node != clear_flag(iter));
11519af6 824 assert(!is_removed(iter_prev));
c90201ac 825 assert(!is_removed(iter));
f000907d 826 assert(iter_prev != node);
bb7b2f26 827 if (!dummy) {
1b81fe1a 828 node->p.next = clear_flag(iter);
bb7b2f26
MD
829 } else {
830 /*
831 * Dummy node insertion is performed concurrently (help
832 * scheme). We try to link its next node, and if this
833 * succeeds, it _means_ it's us who link this dummy node
834 * into the table. force_dummy is set as soon as we
835 * succeed this cmpxchg within this function.
836 */
837 if (!force_dummy) {
838 if (uatomic_cmpxchg(&node->p.next, NULL,
839 flag_dummy(clear_flag(iter))) != NULL) {
840 return NULL;
841 }
842 force_dummy = 1;
843 } else {
844 node->p.next = flag_dummy(clear_flag(iter));
845 }
846 }
f5596c94
MD
847 if (is_dummy(iter))
848 new_node = flag_dummy(node);
849 else
850 new_node = node;
bb7b2f26 851 assert(new_node != NULL);
cc4fcb10 852 if (uatomic_cmpxchg(&iter_prev->p.next, iter,
f5596c94 853 new_node) != iter)
273399de 854 continue; /* retry */
11519af6 855 else
273399de 856 goto gc_end;
9dba85be
MD
857 gc_node:
858 assert(!is_removed(iter));
f5596c94
MD
859 if (is_dummy(iter))
860 new_next = flag_dummy(clear_flag(next));
861 else
862 new_next = clear_flag(next);
bb7b2f26 863 assert(new_next != NULL);
f5596c94 864 (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
273399de 865 /* retry */
464a1ec9 866 }
273399de
MD
867gc_end:
868 /* Garbage collect logically removed nodes in the bucket */
4105056a 869 index = hash & (size - 1);
24365af7 870 order = get_count_order_ulong(index + 1);
4105056a 871 lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))];
14044b37 872 dummy_node = (struct cds_lfht_node *) lookup;
76a73da8
MD
873 if (_cds_lfht_gc_bucket(dummy_node, node)) {
874 /* Help expand */
875 (void) _cds_lfht_add(ht, size >> 1, dummy_node, 0, 1);
876 goto gc_end; /* retry */
877 }
18117871 878 return node;
abc490a1 879}
464a1ec9 880
abc490a1 881static
4105056a
MD
882int _cds_lfht_remove(struct cds_lfht *ht, unsigned long size,
883 struct cds_lfht_node *node,
884 int dummy_removal)
abc490a1 885{
14044b37
MD
886 struct cds_lfht_node *dummy, *next, *old;
887 struct _cds_lfht_node *lookup;
abc490a1 888 int flagged = 0;
24365af7 889 unsigned long hash, index, order;
5e28c532 890
7ec59d3b 891 /* logically delete the node */
c90201ac
MD
892 assert(!is_dummy(node));
893 assert(!is_removed(node));
cc4fcb10 894 old = rcu_dereference(node->p.next);
7ec59d3b
MD
895 do {
896 next = old;
76412f24 897 if (unlikely(is_removed(next)))
7ec59d3b 898 goto end;
1475579c
MD
899 if (dummy_removal)
900 assert(is_dummy(next));
901 else
902 assert(!is_dummy(next));
bb7b2f26 903 assert(next != NULL);
cc4fcb10 904 old = uatomic_cmpxchg(&node->p.next, next,
7ec59d3b
MD
905 flag_removed(next));
906 } while (old != next);
907
908 /* We performed the (logical) deletion. */
909 flagged = 1;
910
911 /*
912 * Ensure that the node is not visible to readers anymore: lookup for
273399de
MD
913 * the node, and remove it (along with any other logically removed node)
914 * if found.
11519af6 915 */
76a73da8 916gc_retry:
cc4fcb10 917 hash = bit_reverse_ulong(node->p.reverse_hash);
4105056a
MD
918 assert(size > 0);
919 index = hash & (size - 1);
24365af7 920 order = get_count_order_ulong(index + 1);
4105056a 921 lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))];
14044b37 922 dummy = (struct cds_lfht_node *) lookup;
76a73da8
MD
923 if (_cds_lfht_gc_bucket(dummy, node)) {
924 /* Help expand */
925 (void) _cds_lfht_add(ht, size >> 1, dummy, 0, 1);
926 goto gc_retry; /* retry */
927 }
2ed95849 928end:
11519af6
MD
929 /*
930 * Only the flagging action indicated that we (and no other)
931 * removed the node from the hash.
932 */
7ec59d3b 933 if (flagged) {
cc4fcb10 934 assert(is_removed(rcu_dereference(node->p.next)));
11519af6 935 return 0;
7ec59d3b 936 } else
11519af6 937 return -ENOENT;
abc490a1 938}
2ed95849 939
4105056a
MD
940static
941void init_table_hash(struct cds_lfht *ht, unsigned long i,
942 unsigned long len)
943{
944 unsigned long j;
945
946 for (j = 0; j < len; j++) {
947 struct cds_lfht_node *new_node =
948 (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
949
950 dbg_printf("init hash entry: i %lu j %lu hash %lu\n",
951 i, j, !i ? 0 : (1UL << (i - 1)) + j);
952 new_node->p.reverse_hash =
953 bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
954 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
955 break;
956 }
957}
958
e8de508e
MD
959/*
960 * Holding RCU read lock to protect _cds_lfht_add against memory
961 * reclaim that could be performed by other call_rcu worker threads (ABA
962 * problem).
963 */
4105056a
MD
964static
965void init_table_link(struct cds_lfht *ht, unsigned long i, unsigned long len)
966{
967 unsigned long j;
968
5f511391 969 ht->cds_lfht_rcu_thread_online();
4105056a
MD
970 ht->cds_lfht_rcu_read_lock();
971 for (j = 0; j < len; j++) {
972 struct cds_lfht_node *new_node =
973 (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
974
975 dbg_printf("init link: i %lu j %lu hash %lu\n",
976 i, j, !i ? 0 : (1UL << (i - 1)) + j);
977 (void) _cds_lfht_add(ht, !i ? 0 : (1UL << (i - 1)),
978 new_node, 0, 1);
979 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
980 break;
981 }
982 ht->cds_lfht_rcu_read_unlock();
5f511391 983 ht->cds_lfht_rcu_thread_offline();
4105056a
MD
984}
985
abc490a1 986static
4105056a 987void init_table(struct cds_lfht *ht,
24365af7
MD
988 unsigned long first_order, unsigned long len_order)
989{
990 unsigned long i, end_order;
991
f0c29ed7 992 dbg_printf("init table: first_order %lu end_order %lu\n",
24365af7
MD
993 first_order, first_order + len_order);
994 end_order = first_order + len_order;
24365af7 995 for (i = first_order; i < end_order; i++) {
4105056a 996 unsigned long len;
24365af7
MD
997
998 len = !i ? 1 : 1UL << (i - 1);
f0c29ed7 999 dbg_printf("init order %lu len: %lu\n", i, len);
4d676753
MD
1000
1001 /* Stop expand if the resize target changes under us */
1002 if (CMM_LOAD_SHARED(ht->t.resize_target) < (!i ? 1 : (1UL << i)))
1003 break;
1004
4105056a 1005 ht->t.tbl[i] = calloc(1, sizeof(struct rcu_level)
1475579c 1006 + (len * sizeof(struct _cds_lfht_node)));
4105056a
MD
1007
1008 /* Set all dummy nodes reverse hash values for a level */
1009 init_table_hash(ht, i, len);
1010
76a73da8
MD
1011 /*
1012 * Update table size. At this point, concurrent add/remove see
1013 * dummy nodes with correctly initialized reverse hash value,
1014 * but with NULL next pointers. If they do, they can help us
1015 * link the dummy nodes into the list and retry.
1016 */
1017 cmm_smp_wmb(); /* populate data before RCU size */
1018 CMM_STORE_SHARED(ht->t.size, !i ? 1 : (1UL << i));
1019
4105056a
MD
1020 /*
1021 * Link all dummy nodes into the table. Concurrent
1022 * add/remove are helping us.
1023 */
1024 init_table_link(ht, i, len);
1025
4105056a
MD
1026 dbg_printf("init new size: %lu\n", !i ? 1 : (1UL << i));
1027 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
1028 break;
1029 }
1030}
1031
e8de508e
MD
1032/*
1033 * Holding RCU read lock to protect _cds_lfht_remove against memory
1034 * reclaim that could be performed by other call_rcu worker threads (ABA
1035 * problem).
1036 * For a single level, we logically remove and garbage collect each node.
1037 *
1038 * As a design choice, we perform logical removal and garbage collection on a
1039 * node-per-node basis to simplify this algorithm. We also assume keeping good
1040 * cache locality of the operation would overweight possible performance gain
1041 * that could be achieved by batching garbage collection for multiple levels.
1042 * However, this would have to be justified by benchmarks.
1043 *
1044 * Concurrent removal and add operations are helping us perform garbage
1045 * collection of logically removed nodes. We guarantee that all logically
1046 * removed nodes have been garbage-collected (unlinked) before call_rcu is
1047 * invoked to free a hole level of dummy nodes (after a grace period).
1048 *
1049 * Logical removal and garbage collection can therefore be done in batch or on a
1050 * node-per-node basis, as long as the guarantee above holds.
1051 */
4105056a
MD
1052static
1053void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
1054{
1055 unsigned long j;
1056
5f511391 1057 ht->cds_lfht_rcu_thread_online();
4105056a
MD
1058 ht->cds_lfht_rcu_read_lock();
1059 for (j = 0; j < len; j++) {
1060 struct cds_lfht_node *fini_node =
1061 (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
1062
1063 dbg_printf("remove entry: i %lu j %lu hash %lu\n",
1064 i, j, !i ? 0 : (1UL << (i - 1)) + j);
1065 fini_node->p.reverse_hash =
1066 bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
1067 (void) _cds_lfht_remove(ht, !i ? 0 : (1UL << (i - 1)),
1068 fini_node, 1);
33c7c748
MD
1069 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
1070 break;
abc490a1 1071 }
4105056a 1072 ht->cds_lfht_rcu_read_unlock();
5f511391 1073 ht->cds_lfht_rcu_thread_offline();
2ed95849
MD
1074}
1075
1475579c 1076static
4105056a 1077void fini_table(struct cds_lfht *ht,
1475579c
MD
1078 unsigned long first_order, unsigned long len_order)
1079{
1080 long i, end_order;
1081
1082 dbg_printf("fini table: first_order %lu end_order %lu\n",
1083 first_order, first_order + len_order);
1084 end_order = first_order + len_order;
1085 assert(first_order > 0);
1475579c 1086 for (i = end_order - 1; i >= first_order; i--) {
4105056a 1087 unsigned long len;
1475579c
MD
1088
1089 len = !i ? 1 : 1UL << (i - 1);
1090 dbg_printf("fini order %lu len: %lu\n", i, len);
4105056a 1091
4d676753
MD
1092 /* Stop shrink if the resize target changes under us */
1093 if (CMM_LOAD_SHARED(ht->t.resize_target) > (1UL << (i - 1)))
1094 break;
1095
1096 cmm_smp_wmb(); /* populate data before RCU size */
1097 CMM_STORE_SHARED(ht->t.size, 1UL << (i - 1));
1098
1099 /*
1100 * We need to wait for all add operations to reach Q.S. (and
1101 * thus use the new table for lookups) before we can start
1102 * releasing the old dummy nodes. Otherwise their lookup will
1103 * return a logically removed node as insert position.
1104 */
1105 ht->cds_lfht_synchronize_rcu();
1106
21263e21 1107 /*
4105056a
MD
1108 * Set "removed" flag in dummy nodes about to be removed.
1109 * Unlink all now-logically-removed dummy node pointers.
1110 * Concurrent add/remove operation are helping us doing
1111 * the gc.
21263e21 1112 */
4105056a
MD
1113 remove_table(ht, i, len);
1114
1115 ht->cds_lfht_call_rcu(&ht->t.tbl[i]->head, cds_lfht_free_level);
1116
1117 dbg_printf("fini new size: %lu\n", 1UL << i);
1475579c
MD
1118 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
1119 break;
1120 }
1475579c
MD
1121}
1122
14044b37
MD
1123struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
1124 cds_lfht_compare_fct compare_fct,
1125 unsigned long hash_seed,
1126 unsigned long init_size,
b8af5011 1127 int flags,
14044b37 1128 void (*cds_lfht_call_rcu)(struct rcu_head *head,
1475579c 1129 void (*func)(struct rcu_head *head)),
01dbfa62
MD
1130 void (*cds_lfht_synchronize_rcu)(void),
1131 void (*cds_lfht_rcu_read_lock)(void),
5f511391
MD
1132 void (*cds_lfht_rcu_read_unlock)(void),
1133 void (*cds_lfht_rcu_thread_offline)(void),
1134 void (*cds_lfht_rcu_thread_online)(void))
abc490a1 1135{
14044b37 1136 struct cds_lfht *ht;
24365af7 1137 unsigned long order;
abc490a1 1138
8129be4e 1139 /* init_size must be power of two */
49619ea0 1140 if (init_size && (init_size & (init_size - 1)))
8129be4e 1141 return NULL;
14044b37 1142 ht = calloc(1, sizeof(struct cds_lfht));
abc490a1 1143 ht->hash_fct = hash_fct;
732ad076
MD
1144 ht->compare_fct = compare_fct;
1145 ht->hash_seed = hash_seed;
14044b37 1146 ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
1475579c 1147 ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
01dbfa62
MD
1148 ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
1149 ht->cds_lfht_rcu_read_unlock = cds_lfht_rcu_read_unlock;
5f511391
MD
1150 ht->cds_lfht_rcu_thread_offline = cds_lfht_rcu_thread_offline;
1151 ht->cds_lfht_rcu_thread_online = cds_lfht_rcu_thread_online;
df44348d 1152 ht->percpu_count = alloc_per_cpu_items_count();
abc490a1
MD
1153 /* this mutex should not nest in read-side C.S. */
1154 pthread_mutex_init(&ht->resize_mutex, NULL);
cd95516d 1155 order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE)) + 1;
b8af5011 1156 ht->flags = flags;
5f511391 1157 ht->cds_lfht_rcu_thread_offline();
f000907d 1158 pthread_mutex_lock(&ht->resize_mutex);
4d676753 1159 ht->t.resize_target = 1UL << (order - 1);
4105056a 1160 init_table(ht, 0, order);
f000907d 1161 pthread_mutex_unlock(&ht->resize_mutex);
5f511391 1162 ht->cds_lfht_rcu_thread_online();
abc490a1
MD
1163 return ht;
1164}
1165
14044b37 1166struct cds_lfht_node *cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len)
2ed95849 1167{
bb7b2f26 1168 struct cds_lfht_node *node, *next, *dummy_node;
14044b37 1169 struct _cds_lfht_node *lookup;
4105056a 1170 unsigned long hash, reverse_hash, index, order, size;
2ed95849 1171
732ad076 1172 hash = ht->hash_fct(key, key_len, ht->hash_seed);
abc490a1 1173 reverse_hash = bit_reverse_ulong(hash);
464a1ec9 1174
bb7b2f26 1175restart:
4105056a
MD
1176 size = rcu_dereference(ht->t.size);
1177 index = hash & (size - 1);
24365af7 1178 order = get_count_order_ulong(index + 1);
4105056a 1179 lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1))) - 1)];
f0c29ed7 1180 dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n",
554c284e 1181 hash, index, order, index & (!order ? 0 : ((1UL << (order - 1)) - 1)));
bb7b2f26
MD
1182 dummy_node = (struct cds_lfht_node *) lookup;
1183 /* We can always skip the dummy node initially */
1184 node = rcu_dereference(dummy_node->p.next);
1185 if (unlikely(node == NULL)) {
1186 /*
1187 * We are executing concurrently with a hash table
1188 * expand, so we see a dummy node with NULL next value.
1189 * Help expand by linking this node into the list and
1190 * retry.
1191 */
1192 (void) _cds_lfht_add(ht, size >> 1, dummy_node, 0, 1);
1193 goto restart; /* retry */
1194 }
1195 node = clear_flag(node);
2ed95849 1196 for (;;) {
bb7b2f26
MD
1197 if (unlikely(is_end(node))) {
1198 node = NULL;
abc490a1 1199 break;
bb7b2f26 1200 }
cc4fcb10 1201 if (unlikely(node->p.reverse_hash > reverse_hash)) {
abc490a1
MD
1202 node = NULL;
1203 break;
2ed95849 1204 }
1b81fe1a
MD
1205 next = rcu_dereference(node->p.next);
1206 if (likely(!is_removed(next))
1207 && !is_dummy(next)
49c2e2d6 1208 && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
273399de 1209 break;
2ed95849 1210 }
1b81fe1a 1211 node = clear_flag(next);
2ed95849 1212 }
1b81fe1a 1213 assert(!node || !is_dummy(rcu_dereference(node->p.next)));
abc490a1
MD
1214 return node;
1215}
e0ba718a 1216
a481e5ff
MD
1217struct cds_lfht_node *cds_lfht_next(struct cds_lfht *ht,
1218 struct cds_lfht_node *node)
1219{
1220 struct cds_lfht_node *next;
1221 unsigned long reverse_hash;
1222 void *key;
1223 size_t key_len;
1224
1225 reverse_hash = node->p.reverse_hash;
1226 key = node->key;
1227 key_len = node->key_len;
1228 next = rcu_dereference(node->p.next);
1229 node = clear_flag(next);
1230
1231 for (;;) {
bb7b2f26
MD
1232 if (unlikely(is_end(node))) {
1233 node = NULL;
a481e5ff 1234 break;
bb7b2f26 1235 }
a481e5ff
MD
1236 if (unlikely(node->p.reverse_hash > reverse_hash)) {
1237 node = NULL;
1238 break;
1239 }
1240 next = rcu_dereference(node->p.next);
1241 if (likely(!is_removed(next))
1242 && !is_dummy(next)
1243 && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
1244 break;
1245 }
1246 node = clear_flag(next);
1247 }
1248 assert(!node || !is_dummy(rcu_dereference(node->p.next)));
1249 return node;
1250}
1251
14044b37 1252void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
abc490a1 1253{
4105056a 1254 unsigned long hash, size;
ab7d5fc6 1255
49c2e2d6 1256 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 1257 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
2ed95849 1258
4105056a
MD
1259 size = rcu_dereference(ht->t.size);
1260 (void) _cds_lfht_add(ht, size, node, 0, 0);
1261 ht_count_add(ht, size);
3eca1b8c
MD
1262}
1263
14044b37
MD
1264struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
1265 struct cds_lfht_node *node)
3eca1b8c 1266{
4105056a 1267 unsigned long hash, size;
df44348d 1268 struct cds_lfht_node *ret;
3eca1b8c 1269
49c2e2d6 1270 hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
cc4fcb10 1271 node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
3eca1b8c 1272
4105056a
MD
1273 size = rcu_dereference(ht->t.size);
1274 ret = _cds_lfht_add(ht, size, node, 1, 0);
df44348d 1275 if (ret != node)
4105056a 1276 ht_count_add(ht, size);
df44348d 1277 return ret;
2ed95849
MD
1278}
1279
14044b37 1280int cds_lfht_remove(struct cds_lfht *ht, struct cds_lfht_node *node)
2ed95849 1281{
4105056a 1282 unsigned long size;
df44348d 1283 int ret;
abc490a1 1284
4105056a
MD
1285 size = rcu_dereference(ht->t.size);
1286 ret = _cds_lfht_remove(ht, size, node, 0);
df44348d 1287 if (!ret)
4105056a 1288 ht_count_remove(ht, size);
df44348d 1289 return ret;
2ed95849 1290}
ab7d5fc6 1291
abc490a1 1292static
14044b37 1293int cds_lfht_delete_dummy(struct cds_lfht *ht)
674f7a69 1294{
14044b37
MD
1295 struct cds_lfht_node *node;
1296 struct _cds_lfht_node *lookup;
4105056a 1297 unsigned long order, i, size;
674f7a69 1298
abc490a1 1299 /* Check that the table is empty */
4105056a 1300 lookup = &ht->t.tbl[0]->nodes[0];
14044b37 1301 node = (struct cds_lfht_node *) lookup;
abc490a1 1302 do {
1b81fe1a
MD
1303 node = clear_flag(node)->p.next;
1304 if (!is_dummy(node))
abc490a1 1305 return -EPERM;
273399de 1306 assert(!is_removed(node));
bb7b2f26 1307 } while (!is_end(node));
4105056a
MD
1308 /*
1309 * size accessed without rcu_dereference because hash table is
1310 * being destroyed.
1311 */
1312 size = ht->t.size;
abc490a1 1313 /* Internal sanity check: all nodes left should be dummy */
4105056a 1314 for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
24365af7
MD
1315 unsigned long len;
1316
1317 len = !order ? 1 : 1UL << (order - 1);
1318 for (i = 0; i < len; i++) {
f0c29ed7 1319 dbg_printf("delete order %lu i %lu hash %lu\n",
24365af7 1320 order, i,
4105056a
MD
1321 bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
1322 assert(is_dummy(ht->t.tbl[order]->nodes[i].next));
24365af7 1323 }
4105056a 1324 poison_free(ht->t.tbl[order]);
674f7a69 1325 }
abc490a1 1326 return 0;
674f7a69
MD
1327}
1328
1329/*
1330 * Should only be called when no more concurrent readers nor writers can
1331 * possibly access the table.
1332 */
14044b37 1333int cds_lfht_destroy(struct cds_lfht *ht)
674f7a69 1334{
5e28c532
MD
1335 int ret;
1336
848d4088 1337 /* Wait for in-flight resize operations to complete */
33c7c748 1338 CMM_STORE_SHARED(ht->in_progress_destroy, 1);
848d4088
MD
1339 while (uatomic_read(&ht->in_progress_resize))
1340 poll(NULL, 0, 100); /* wait for 100ms */
14044b37 1341 ret = cds_lfht_delete_dummy(ht);
abc490a1
MD
1342 if (ret)
1343 return ret;
df44348d 1344 free_per_cpu_items_count(ht->percpu_count);
98808fb1 1345 poison_free(ht);
5e28c532 1346 return ret;
674f7a69
MD
1347}
1348
14044b37 1349void cds_lfht_count_nodes(struct cds_lfht *ht,
273399de
MD
1350 unsigned long *count,
1351 unsigned long *removed)
1352{
14044b37
MD
1353 struct cds_lfht_node *node, *next;
1354 struct _cds_lfht_node *lookup;
24365af7 1355 unsigned long nr_dummy = 0;
273399de
MD
1356
1357 *count = 0;
1358 *removed = 0;
1359
24365af7 1360 /* Count non-dummy nodes in the table */
4105056a 1361 lookup = &ht->t.tbl[0]->nodes[0];
14044b37 1362 node = (struct cds_lfht_node *) lookup;
273399de 1363 do {
cc4fcb10 1364 next = rcu_dereference(node->p.next);
273399de 1365 if (is_removed(next)) {
1b81fe1a 1366 assert(!is_dummy(next));
273399de 1367 (*removed)++;
1b81fe1a 1368 } else if (!is_dummy(next))
273399de 1369 (*count)++;
24365af7
MD
1370 else
1371 (nr_dummy)++;
273399de 1372 node = clear_flag(next);
bb7b2f26 1373 } while (!is_end(node));
f0c29ed7 1374 dbg_printf("number of dummy nodes: %lu\n", nr_dummy);
273399de
MD
1375}
1376
1475579c 1377/* called with resize mutex held */
abc490a1 1378static
4105056a 1379void _do_cds_lfht_grow(struct cds_lfht *ht,
1475579c 1380 unsigned long old_size, unsigned long new_size)
abc490a1 1381{
1475579c 1382 unsigned long old_order, new_order;
1475579c
MD
1383
1384 old_order = get_count_order_ulong(old_size) + 1;
1385 new_order = get_count_order_ulong(new_size) + 1;
1386 printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
1387 old_size, old_order, new_size, new_order);
1475579c 1388 assert(new_size > old_size);
4105056a 1389 init_table(ht, old_order, new_order - old_order);
abc490a1
MD
1390}
1391
1392/* called with resize mutex held */
1393static
4105056a 1394void _do_cds_lfht_shrink(struct cds_lfht *ht,
1475579c 1395 unsigned long old_size, unsigned long new_size)
464a1ec9 1396{
1475579c 1397 unsigned long old_order, new_order;
464a1ec9 1398
cd95516d 1399 new_size = max(new_size, MIN_TABLE_SIZE);
24365af7 1400 old_order = get_count_order_ulong(old_size) + 1;
24365af7 1401 new_order = get_count_order_ulong(new_size) + 1;
df44348d 1402 printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
df03fab8 1403 old_size, old_order, new_size, new_order);
1475579c 1404 assert(new_size < old_size);
1475579c 1405
4105056a
MD
1406 /* Remove and unlink all dummy nodes to remove. */
1407 fini_table(ht, new_order, old_order - new_order);
464a1ec9
MD
1408}
1409
1475579c
MD
1410
1411/* called with resize mutex held */
1412static
1413void _do_cds_lfht_resize(struct cds_lfht *ht)
1414{
1415 unsigned long new_size, old_size;
4105056a
MD
1416
1417 /*
1418 * Resize table, re-do if the target size has changed under us.
1419 */
1420 do {
1421 ht->t.resize_initiated = 1;
1422 old_size = ht->t.size;
1423 new_size = CMM_LOAD_SHARED(ht->t.resize_target);
1424 if (old_size < new_size)
1425 _do_cds_lfht_grow(ht, old_size, new_size);
1426 else if (old_size > new_size)
1427 _do_cds_lfht_shrink(ht, old_size, new_size);
1428 ht->t.resize_initiated = 0;
1429 /* write resize_initiated before read resize_target */
1430 cmm_smp_mb();
4d676753 1431 } while (ht->t.size != CMM_LOAD_SHARED(ht->t.resize_target));
1475579c
MD
1432}
1433
abc490a1 1434static
4105056a 1435unsigned long resize_target_update(struct cds_lfht *ht, unsigned long size,
f9830efd 1436 int growth_order)
464a1ec9 1437{
4105056a
MD
1438 return _uatomic_max(&ht->t.resize_target,
1439 size << growth_order);
464a1ec9
MD
1440}
1441
1475579c 1442static
4105056a 1443void resize_target_update_count(struct cds_lfht *ht,
b8af5011 1444 unsigned long count)
1475579c 1445{
cd95516d 1446 count = max(count, MIN_TABLE_SIZE);
4105056a 1447 uatomic_set(&ht->t.resize_target, count);
1475579c
MD
1448}
1449
1450void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size)
464a1ec9 1451{
4105056a
MD
1452 resize_target_update_count(ht, new_size);
1453 CMM_STORE_SHARED(ht->t.resize_initiated, 1);
5f511391 1454 ht->cds_lfht_rcu_thread_offline();
1475579c
MD
1455 pthread_mutex_lock(&ht->resize_mutex);
1456 _do_cds_lfht_resize(ht);
1457 pthread_mutex_unlock(&ht->resize_mutex);
5f511391 1458 ht->cds_lfht_rcu_thread_online();
abc490a1 1459}
464a1ec9 1460
abc490a1
MD
1461static
1462void do_resize_cb(struct rcu_head *head)
1463{
1464 struct rcu_resize_work *work =
1465 caa_container_of(head, struct rcu_resize_work, head);
14044b37 1466 struct cds_lfht *ht = work->ht;
abc490a1 1467
5f511391 1468 ht->cds_lfht_rcu_thread_offline();
abc490a1 1469 pthread_mutex_lock(&ht->resize_mutex);
14044b37 1470 _do_cds_lfht_resize(ht);
abc490a1 1471 pthread_mutex_unlock(&ht->resize_mutex);
5f511391 1472 ht->cds_lfht_rcu_thread_online();
98808fb1 1473 poison_free(work);
848d4088
MD
1474 cmm_smp_mb(); /* finish resize before decrement */
1475 uatomic_dec(&ht->in_progress_resize);
464a1ec9
MD
1476}
1477
abc490a1 1478static
4105056a 1479void cds_lfht_resize_lazy(struct cds_lfht *ht, unsigned long size, int growth)
ab7d5fc6 1480{
abc490a1 1481 struct rcu_resize_work *work;
f9830efd 1482 unsigned long target_size;
abc490a1 1483
4105056a
MD
1484 target_size = resize_target_update(ht, size, growth);
1485 /* Store resize_target before read resize_initiated */
1486 cmm_smp_mb();
1487 if (!CMM_LOAD_SHARED(ht->t.resize_initiated) && size < target_size) {
848d4088
MD
1488 uatomic_inc(&ht->in_progress_resize);
1489 cmm_smp_mb(); /* increment resize count before calling it */
f9830efd
MD
1490 work = malloc(sizeof(*work));
1491 work->ht = ht;
14044b37 1492 ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
4105056a 1493 CMM_STORE_SHARED(ht->t.resize_initiated, 1);
f9830efd 1494 }
ab7d5fc6 1495}
3171717f 1496
f8994aee
MD
1497#if defined(HAVE_SCHED_GETCPU) && defined(HAVE_SYSCONF)
1498
3171717f 1499static
4105056a 1500void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
3171717f
MD
1501 unsigned long count)
1502{
1503 struct rcu_resize_work *work;
3171717f 1504
b8af5011
MD
1505 if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
1506 return;
4105056a
MD
1507 resize_target_update_count(ht, count);
1508 /* Store resize_target before read resize_initiated */
1509 cmm_smp_mb();
1510 if (!CMM_LOAD_SHARED(ht->t.resize_initiated)) {
3171717f
MD
1511 uatomic_inc(&ht->in_progress_resize);
1512 cmm_smp_mb(); /* increment resize count before calling it */
1513 work = malloc(sizeof(*work));
1514 work->ht = ht;
1515 ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
4105056a 1516 CMM_STORE_SHARED(ht->t.resize_initiated, 1);
3171717f
MD
1517 }
1518}
f8994aee
MD
1519
1520#endif
This page took 0.174819 seconds and 4 git commands to generate.