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