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