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