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