urcu/annotate: Add CMM annotation
[userspace-rcu.git] / src / rculfhash.c
1 // SPDX-FileCopyrightText: 2010-2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
2 // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
3 //
4 // SPDX-License-Identifier: LGPL-2.1-or-later
5
6 /*
7 * Userspace RCU library - Lock-Free Resizable RCU Hash Table
8 */
9
10 /*
11 * Based on the following articles:
12 * - Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free
13 * extensible hash tables. J. ACM 53, 3 (May 2006), 379-405.
14 * - Michael, M. M. High performance dynamic lock-free hash tables
15 * and list-based sets. In Proceedings of the fourteenth annual ACM
16 * symposium on Parallel algorithms and architectures, ACM Press,
17 * (2002), 73-82.
18 *
19 * Some specificities of this Lock-Free Resizable RCU Hash Table
20 * implementation:
21 *
22 * - RCU read-side critical section allows readers to perform hash
23 * table lookups, as well as traversals, and use the returned objects
24 * safely by allowing memory reclaim to take place only after a grace
25 * period.
26 * - Add and remove operations are lock-free, and do not need to
27 * allocate memory. They need to be executed within RCU read-side
28 * critical section to ensure the objects they read are valid and to
29 * deal with the cmpxchg ABA problem.
30 * - add and add_unique operations are supported. add_unique checks if
31 * the node key already exists in the hash table. It ensures not to
32 * populate a duplicate key if the node key already exists in the hash
33 * table.
34 * - The resize operation executes concurrently with
35 * add/add_unique/add_replace/remove/lookup/traversal.
36 * - Hash table nodes are contained within a split-ordered list. This
37 * list is ordered by incrementing reversed-bits-hash value.
38 * - An index of bucket nodes is kept. These bucket nodes are the hash
39 * table "buckets". These buckets are internal nodes that allow to
40 * perform a fast hash lookup, similarly to a skip list. These
41 * buckets are chained together in the split-ordered list, which
42 * allows recursive expansion by inserting new buckets between the
43 * existing buckets. The split-ordered list allows adding new buckets
44 * between existing buckets as the table needs to grow.
45 * - The resize operation for small tables only allows expanding the
46 * hash table. It is triggered automatically by detecting long chains
47 * in the add operation.
48 * - The resize operation for larger tables (and available through an
49 * API) allows both expanding and shrinking the hash table.
50 * - Split-counters are used to keep track of the number of
51 * nodes within the hash table for automatic resize triggering.
52 * - Resize operation initiated by long chain detection is executed by a
53 * worker thread, which keeps lock-freedom of add and remove.
54 * - Resize operations are protected by a mutex.
55 * - The removal operation is split in two parts: first, a "removed"
56 * flag is set in the next pointer within the node to remove. Then,
57 * a "garbage collection" is performed in the bucket containing the
58 * removed node (from the start of the bucket up to the removed node).
59 * All encountered nodes with "removed" flag set in their next
60 * pointers are removed from the linked-list. If the cmpxchg used for
61 * removal fails (due to concurrent garbage-collection or concurrent
62 * add), we retry from the beginning of the bucket. This ensures that
63 * the node with "removed" flag set is removed from the hash table
64 * (not visible to lookups anymore) before the RCU read-side critical
65 * section held across removal ends. Furthermore, this ensures that
66 * the node with "removed" flag set is removed from the linked-list
67 * before its memory is reclaimed. After setting the "removal" flag,
68 * only the thread which removal is the first to set the "removal
69 * owner" flag (with an xchg) into a node's next pointer is considered
70 * to have succeeded its removal (and thus owns the node to reclaim).
71 * Because we garbage-collect starting from an invariant node (the
72 * start-of-bucket bucket node) up to the "removed" node (or find a
73 * reverse-hash that is higher), we are sure that a successful
74 * traversal of the chain leads to a chain that is present in the
75 * linked-list (the start node is never removed) and that it does not
76 * contain the "removed" node anymore, even if concurrent delete/add
77 * operations are changing the structure of the list concurrently.
78 * - The add operations perform garbage collection of buckets if they
79 * encounter nodes with removed flag set in the bucket where they want
80 * to add their new node. This ensures lock-freedom of add operation by
81 * helping the remover unlink nodes from the list rather than to wait
82 * for it do to so.
83 * - There are three memory backends for the hash table buckets: the
84 * "order table", the "chunks", and the "mmap".
85 * - These bucket containers contain a compact version of the hash table
86 * nodes.
87 * - The RCU "order table":
88 * - has a first level table indexed by log2(hash index) which is
89 * copied and expanded by the resize operation. This order table
90 * allows finding the "bucket node" tables.
91 * - There is one bucket node table per hash index order. The size of
92 * each bucket node table is half the number of hashes contained in
93 * this order (except for order 0).
94 * - The RCU "chunks" is best suited for close interaction with a page
95 * allocator. It uses a linear array as index to "chunks" containing
96 * each the same number of buckets.
97 * - The RCU "mmap" memory backend uses a single memory map to hold
98 * all buckets.
99 * - synchronize_rcu is used to garbage-collect the old bucket node table.
100 *
101 * Ordering Guarantees:
102 *
103 * To discuss these guarantees, we first define "read" operation as any
104 * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate,
105 * cds_lfht_first, cds_lfht_next operation, as well as
106 * cds_lfht_add_unique (failure).
107 *
108 * We define "read traversal" operation as any of the following
109 * group of operations
110 * - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate
111 * (and/or cds_lfht_next, although less common).
112 * - cds_lfht_add_unique (failure) followed by iteration with
113 * cds_lfht_next_duplicate (and/or cds_lfht_next, although less
114 * common).
115 * - cds_lfht_first followed iteration with cds_lfht_next (and/or
116 * cds_lfht_next_duplicate, although less common).
117 *
118 * We define "write" operations as any of cds_lfht_add, cds_lfht_replace,
119 * cds_lfht_add_unique (success), cds_lfht_add_replace, cds_lfht_del.
120 *
121 * When cds_lfht_add_unique succeeds (returns the node passed as
122 * parameter), it acts as a "write" operation. When cds_lfht_add_unique
123 * fails (returns a node different from the one passed as parameter), it
124 * acts as a "read" operation. A cds_lfht_add_unique failure is a
125 * cds_lfht_lookup "read" operation, therefore, any ordering guarantee
126 * referring to "lookup" imply any of "lookup" or cds_lfht_add_unique
127 * (failure).
128 *
129 * We define "prior" and "later" node as nodes observable by reads and
130 * read traversals respectively before and after a write or sequence of
131 * write operations.
132 *
133 * Hash-table operations are often cascaded, for example, the pointer
134 * returned by a cds_lfht_lookup() might be passed to a cds_lfht_next(),
135 * whose return value might in turn be passed to another hash-table
136 * operation. This entire cascaded series of operations must be enclosed
137 * by a pair of matching rcu_read_lock() and rcu_read_unlock()
138 * operations.
139 *
140 * The following ordering guarantees are offered by this hash table:
141 *
142 * A.1) "read" after "write": if there is ordering between a write and a
143 * later read, then the read is guaranteed to see the write or some
144 * later write.
145 * A.2) "read traversal" after "write": given that there is dependency
146 * ordering between reads in a "read traversal", if there is
147 * ordering between a write and the first read of the traversal,
148 * then the "read traversal" is guaranteed to see the write or
149 * some later write.
150 * B.1) "write" after "read": if there is ordering between a read and a
151 * later write, then the read will never see the write.
152 * B.2) "write" after "read traversal": given that there is dependency
153 * ordering between reads in a "read traversal", if there is
154 * ordering between the last read of the traversal and a later
155 * write, then the "read traversal" will never see the write.
156 * C) "write" while "read traversal": if a write occurs during a "read
157 * traversal", the traversal may, or may not, see the write.
158 * D.1) "write" after "write": if there is ordering between a write and
159 * a later write, then the later write is guaranteed to see the
160 * effects of the first write.
161 * D.2) Concurrent "write" pairs: The system will assign an arbitrary
162 * order to any pair of concurrent conflicting writes.
163 * Non-conflicting writes (for example, to different keys) are
164 * unordered.
165 * E) If a grace period separates a "del" or "replace" operation
166 * and a subsequent operation, then that subsequent operation is
167 * guaranteed not to see the removed item.
168 * F) Uniqueness guarantee: given a hash table that does not contain
169 * duplicate items for a given key, there will only be one item in
170 * the hash table after an arbitrary sequence of add_unique and/or
171 * add_replace operations. Note, however, that a pair of
172 * concurrent read operations might well access two different items
173 * with that key.
174 * G.1) If a pair of lookups for a given key are ordered (e.g. by a
175 * memory barrier), then the second lookup will return the same
176 * node as the previous lookup, or some later node.
177 * G.2) A "read traversal" that starts after the end of a prior "read
178 * traversal" (ordered by memory barriers) is guaranteed to see the
179 * same nodes as the previous traversal, or some later nodes.
180 * G.3) Concurrent "read" pairs: concurrent reads are unordered. For
181 * example, if a pair of reads to the same key run concurrently
182 * with an insertion of that same key, the reads remain unordered
183 * regardless of their return values. In other words, you cannot
184 * rely on the values returned by the reads to deduce ordering.
185 *
186 * Progress guarantees:
187 *
188 * * Reads are wait-free. These operations always move forward in the
189 * hash table linked list, and this list has no loop.
190 * * Writes are lock-free. Any retry loop performed by a write operation
191 * is triggered by progress made within another update operation.
192 *
193 * Bucket node tables:
194 *
195 * hash table hash table the last all bucket node tables
196 * order size bucket node 0 1 2 3 4 5 6(index)
197 * table size
198 * 0 1 1 1
199 * 1 2 1 1 1
200 * 2 4 2 1 1 2
201 * 3 8 4 1 1 2 4
202 * 4 16 8 1 1 2 4 8
203 * 5 32 16 1 1 2 4 8 16
204 * 6 64 32 1 1 2 4 8 16 32
205 *
206 * When growing/shrinking, we only focus on the last bucket node table
207 * which size is (!order ? 1 : (1 << (order -1))).
208 *
209 * Example for growing/shrinking:
210 * grow hash table from order 5 to 6: init the index=6 bucket node table
211 * shrink hash table from order 6 to 5: fini the index=6 bucket node table
212 *
213 * A bit of ascii art explanation:
214 *
215 * The order index is the off-by-one compared to the actual power of 2
216 * because we use index 0 to deal with the 0 special-case.
217 *
218 * This shows the nodes for a small table ordered by reversed bits:
219 *
220 * bits reverse
221 * 0 000 000
222 * 4 100 001
223 * 2 010 010
224 * 6 110 011
225 * 1 001 100
226 * 5 101 101
227 * 3 011 110
228 * 7 111 111
229 *
230 * This shows the nodes in order of non-reversed bits, linked by
231 * reversed-bit order.
232 *
233 * order bits reverse
234 * 0 0 000 000
235 * 1 | 1 001 100 <-
236 * 2 | | 2 010 010 <- |
237 * | | | 3 011 110 | <- |
238 * 3 -> | | | 4 100 001 | |
239 * -> | | 5 101 101 |
240 * -> | 6 110 011
241 * -> 7 111 111
242 */
243
244 #define _LGPL_SOURCE
245 #include <stdlib.h>
246 #include <errno.h>
247 #include <stdio.h>
248 #include <stdint.h>
249 #include <string.h>
250 #include <sched.h>
251 #include <unistd.h>
252
253 #include "compat-getcpu.h"
254 #include <urcu/assert.h>
255 #include <urcu/pointer.h>
256 #include <urcu/call-rcu.h>
257 #include <urcu/flavor.h>
258 #include <urcu/arch.h>
259 #include <urcu/uatomic.h>
260 #include <urcu/compiler.h>
261 #include <urcu/rculfhash.h>
262 #include <urcu/static/urcu-signal-nr.h>
263 #include <stdio.h>
264 #include <pthread.h>
265 #include <signal.h>
266 #include "rculfhash-internal.h"
267 #include "workqueue.h"
268 #include "urcu-die.h"
269 #include "urcu-utils.h"
270 #include "compat-smp.h"
271
272 /*
273 * Split-counters lazily update the global counter each 1024
274 * addition/removal. It automatically keeps track of resize required.
275 * We use the bucket length as indicator for need to expand for small
276 * tables and machines lacking per-cpu data support.
277 */
278 #define COUNT_COMMIT_ORDER 10
279 #define DEFAULT_SPLIT_COUNT_MASK 0xFUL
280 #define CHAIN_LEN_TARGET 1
281 #define CHAIN_LEN_RESIZE_THRESHOLD 3
282
283 /*
284 * Define the minimum table size.
285 */
286 #define MIN_TABLE_ORDER 0
287 #define MIN_TABLE_SIZE (1UL << MIN_TABLE_ORDER)
288
289 /*
290 * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
291 */
292 #define MIN_PARTITION_PER_THREAD_ORDER 12
293 #define MIN_PARTITION_PER_THREAD (1UL << MIN_PARTITION_PER_THREAD_ORDER)
294
295 /*
296 * The removed flag needs to be updated atomically with the pointer.
297 * It indicates that no node must attach to the node scheduled for
298 * removal, and that node garbage collection must be performed.
299 * The bucket flag does not require to be updated atomically with the
300 * pointer, but it is added as a pointer low bit flag to save space.
301 * The "removal owner" flag is used to detect which of the "del"
302 * operation that has set the "removed flag" gets to return the removed
303 * node to its caller. Note that the replace operation does not need to
304 * iteract with the "removal owner" flag, because it validates that
305 * the "removed" flag is not set before performing its cmpxchg.
306 */
307 #define REMOVED_FLAG (1UL << 0)
308 #define BUCKET_FLAG (1UL << 1)
309 #define REMOVAL_OWNER_FLAG (1UL << 2)
310 #define FLAGS_MASK ((1UL << 3) - 1)
311
312 /* Value of the end pointer. Should not interact with flags. */
313 #define END_VALUE NULL
314
315 /*
316 * ht_items_count: Split-counters counting the number of node addition
317 * and removal in the table. Only used if the CDS_LFHT_ACCOUNTING flag
318 * is set at hash table creation.
319 *
320 * These are free-running counters, never reset to zero. They count the
321 * number of add/remove, and trigger every (1 << COUNT_COMMIT_ORDER)
322 * operations to update the global counter. We choose a power-of-2 value
323 * for the trigger to deal with 32 or 64-bit overflow of the counter.
324 */
325 struct ht_items_count {
326 unsigned long add, del;
327 } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
328
329 /*
330 * resize_work: Contains arguments passed to worker thread
331 * responsible for performing lazy resize.
332 */
333 struct resize_work {
334 struct urcu_work work;
335 struct cds_lfht *ht;
336 };
337
338 /*
339 * partition_resize_work: Contains arguments passed to worker threads
340 * executing the hash table resize on partitions of the hash table
341 * assigned to each processor's worker thread.
342 */
343 struct partition_resize_work {
344 pthread_t thread_id;
345 struct cds_lfht *ht;
346 unsigned long i, start, len;
347 void (*fct)(struct cds_lfht *ht, unsigned long i,
348 unsigned long start, unsigned long len);
349 };
350
351 static struct urcu_workqueue *cds_lfht_workqueue;
352
353 /*
354 * Mutex ensuring mutual exclusion between workqueue initialization and
355 * fork handlers. cds_lfht_fork_mutex nests inside call_rcu_mutex.
356 */
357 static pthread_mutex_t cds_lfht_fork_mutex = PTHREAD_MUTEX_INITIALIZER;
358
359 static struct urcu_atfork cds_lfht_atfork;
360
361 /*
362 * atfork handler nesting counters. Handle being registered to many urcu
363 * flavors, thus being possibly invoked more than once in the
364 * pthread_atfork list of callbacks.
365 */
366 static int cds_lfht_workqueue_atfork_nesting;
367
368 static void __attribute__((destructor)) cds_lfht_exit(void);
369 static void cds_lfht_init_worker(const struct rcu_flavor_struct *flavor);
370
371 #ifdef CONFIG_CDS_LFHT_ITER_DEBUG
372
373 static
374 void cds_lfht_iter_debug_set_ht(struct cds_lfht *ht, struct cds_lfht_iter *iter)
375 {
376 iter->lfht = ht;
377 }
378
379 #define cds_lfht_iter_debug_assert(...) urcu_posix_assert(__VA_ARGS__)
380
381 #else
382
383 static
384 void cds_lfht_iter_debug_set_ht(struct cds_lfht *ht __attribute__((unused)),
385 struct cds_lfht_iter *iter __attribute__((unused)))
386 {
387 }
388
389 #define cds_lfht_iter_debug_assert(...)
390
391 #endif
392
393 /*
394 * Algorithm to reverse bits in a word by lookup table, extended to
395 * 64-bit words.
396 * Source:
397 * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
398 * Originally from Public Domain.
399 */
400
401 static const uint8_t BitReverseTable256[256] =
402 {
403 #define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64
404 #define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
405 #define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
406 R6(0), R6(2), R6(1), R6(3)
407 };
408 #undef R2
409 #undef R4
410 #undef R6
411
412 static
413 uint8_t bit_reverse_u8(uint8_t v)
414 {
415 return BitReverseTable256[v];
416 }
417
418 #if (CAA_BITS_PER_LONG == 32)
419 static
420 uint32_t bit_reverse_u32(uint32_t v)
421 {
422 return ((uint32_t) bit_reverse_u8(v) << 24) |
423 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
424 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
425 ((uint32_t) bit_reverse_u8(v >> 24));
426 }
427 #else
428 static
429 uint64_t bit_reverse_u64(uint64_t v)
430 {
431 return ((uint64_t) bit_reverse_u8(v) << 56) |
432 ((uint64_t) bit_reverse_u8(v >> 8) << 48) |
433 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
434 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
435 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
436 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
437 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
438 ((uint64_t) bit_reverse_u8(v >> 56));
439 }
440 #endif
441
442 static
443 unsigned long bit_reverse_ulong(unsigned long v)
444 {
445 #if (CAA_BITS_PER_LONG == 32)
446 return bit_reverse_u32(v);
447 #else
448 return bit_reverse_u64(v);
449 #endif
450 }
451
452 /*
453 * fls: returns the position of the most significant bit.
454 * Returns 0 if no bit is set, else returns the position of the most
455 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
456 */
457 #if defined(URCU_ARCH_X86)
458 static inline
459 unsigned int fls_u32(uint32_t x)
460 {
461 int r;
462
463 __asm__ ("bsrl %1,%0\n\t"
464 "jnz 1f\n\t"
465 "movl $-1,%0\n\t"
466 "1:\n\t"
467 : "=r" (r) : "rm" (x));
468 return r + 1;
469 }
470 #define HAS_FLS_U32
471 #endif
472
473 #if defined(URCU_ARCH_AMD64)
474 static inline
475 unsigned int fls_u64(uint64_t x)
476 {
477 long r;
478
479 __asm__ ("bsrq %1,%0\n\t"
480 "jnz 1f\n\t"
481 "movq $-1,%0\n\t"
482 "1:\n\t"
483 : "=r" (r) : "rm" (x));
484 return r + 1;
485 }
486 #define HAS_FLS_U64
487 #endif
488
489 #ifndef HAS_FLS_U64
490 static __attribute__((unused))
491 unsigned int fls_u64(uint64_t x)
492 {
493 unsigned int r = 64;
494
495 if (!x)
496 return 0;
497
498 if (!(x & 0xFFFFFFFF00000000ULL)) {
499 x <<= 32;
500 r -= 32;
501 }
502 if (!(x & 0xFFFF000000000000ULL)) {
503 x <<= 16;
504 r -= 16;
505 }
506 if (!(x & 0xFF00000000000000ULL)) {
507 x <<= 8;
508 r -= 8;
509 }
510 if (!(x & 0xF000000000000000ULL)) {
511 x <<= 4;
512 r -= 4;
513 }
514 if (!(x & 0xC000000000000000ULL)) {
515 x <<= 2;
516 r -= 2;
517 }
518 if (!(x & 0x8000000000000000ULL)) {
519 x <<= 1;
520 r -= 1;
521 }
522 return r;
523 }
524 #endif
525
526 #ifndef HAS_FLS_U32
527 static __attribute__((unused))
528 unsigned int fls_u32(uint32_t x)
529 {
530 unsigned int r = 32;
531
532 if (!x)
533 return 0;
534 if (!(x & 0xFFFF0000U)) {
535 x <<= 16;
536 r -= 16;
537 }
538 if (!(x & 0xFF000000U)) {
539 x <<= 8;
540 r -= 8;
541 }
542 if (!(x & 0xF0000000U)) {
543 x <<= 4;
544 r -= 4;
545 }
546 if (!(x & 0xC0000000U)) {
547 x <<= 2;
548 r -= 2;
549 }
550 if (!(x & 0x80000000U)) {
551 x <<= 1;
552 r -= 1;
553 }
554 return r;
555 }
556 #endif
557
558 unsigned int cds_lfht_fls_ulong(unsigned long x)
559 {
560 #if (CAA_BITS_PER_LONG == 32)
561 return fls_u32(x);
562 #else
563 return fls_u64(x);
564 #endif
565 }
566
567 /*
568 * Return the minimum order for which x <= (1UL << order).
569 * Return -1 if x is 0.
570 */
571 static
572 int cds_lfht_get_count_order_u32(uint32_t x)
573 {
574 if (!x)
575 return -1;
576
577 return fls_u32(x - 1);
578 }
579
580 /*
581 * Return the minimum order for which x <= (1UL << order).
582 * Return -1 if x is 0.
583 */
584 int cds_lfht_get_count_order_ulong(unsigned long x)
585 {
586 if (!x)
587 return -1;
588
589 return cds_lfht_fls_ulong(x - 1);
590 }
591
592 static
593 void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth);
594
595 static
596 void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
597 unsigned long count);
598
599 static void mutex_lock(pthread_mutex_t *mutex)
600 {
601 int ret;
602
603 #ifndef DISTRUST_SIGNALS_EXTREME
604 ret = pthread_mutex_lock(mutex);
605 if (ret)
606 urcu_die(ret);
607 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
608 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
609 if (ret != EBUSY && ret != EINTR)
610 urcu_die(ret);
611 if (CMM_LOAD_SHARED(URCU_TLS(rcu_reader).need_mb)) {
612 uatomic_store(&URCU_TLS(rcu_reader).need_mb, 0, CMM_SEQ_CST);
613 }
614 (void) poll(NULL, 0, 10);
615 }
616 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
617 }
618
619 static void mutex_unlock(pthread_mutex_t *mutex)
620 {
621 int ret;
622
623 ret = pthread_mutex_unlock(mutex);
624 if (ret)
625 urcu_die(ret);
626 }
627
628 static long nr_cpus_mask = -1;
629 static long split_count_mask = -1;
630 static int split_count_order = -1;
631
632 static void ht_init_nr_cpus_mask(void)
633 {
634 long maxcpus;
635
636 maxcpus = get_possible_cpus_array_len();
637 if (maxcpus <= 0) {
638 nr_cpus_mask = -2;
639 return;
640 }
641 /*
642 * round up number of CPUs to next power of two, so we
643 * can use & for modulo.
644 */
645 maxcpus = 1UL << cds_lfht_get_count_order_ulong(maxcpus);
646 nr_cpus_mask = maxcpus - 1;
647 }
648
649 static
650 void alloc_split_items_count(struct cds_lfht *ht)
651 {
652 if (nr_cpus_mask == -1) {
653 ht_init_nr_cpus_mask();
654 if (nr_cpus_mask < 0)
655 split_count_mask = DEFAULT_SPLIT_COUNT_MASK;
656 else
657 split_count_mask = nr_cpus_mask;
658 split_count_order =
659 cds_lfht_get_count_order_ulong(split_count_mask + 1);
660 }
661
662 urcu_posix_assert(split_count_mask >= 0);
663
664 if (ht->flags & CDS_LFHT_ACCOUNTING) {
665 ht->split_count = calloc(split_count_mask + 1,
666 sizeof(struct ht_items_count));
667 urcu_posix_assert(ht->split_count);
668 } else {
669 ht->split_count = NULL;
670 }
671 }
672
673 static
674 void free_split_items_count(struct cds_lfht *ht)
675 {
676 poison_free(ht->split_count);
677 }
678
679 static
680 int ht_get_split_count_index(unsigned long hash)
681 {
682 int cpu;
683
684 urcu_posix_assert(split_count_mask >= 0);
685 cpu = urcu_sched_getcpu();
686 if (caa_unlikely(cpu < 0))
687 return hash & split_count_mask;
688 else
689 return cpu & split_count_mask;
690 }
691
692 static
693 void ht_count_add(struct cds_lfht *ht, unsigned long size, unsigned long hash)
694 {
695 unsigned long split_count, count;
696 int index;
697
698 if (caa_unlikely(!ht->split_count))
699 return;
700 index = ht_get_split_count_index(hash);
701 split_count = uatomic_add_return(&ht->split_count[index].add, 1);
702 if (caa_likely(split_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))
703 return;
704 /* Only if number of add multiple of 1UL << COUNT_COMMIT_ORDER */
705
706 dbg_printf("add split count %lu\n", split_count);
707 count = uatomic_add_return(&ht->count,
708 1UL << COUNT_COMMIT_ORDER);
709 if (caa_likely(count & (count - 1)))
710 return;
711 /* Only if global count is power of 2 */
712
713 if ((count >> CHAIN_LEN_RESIZE_THRESHOLD) < size)
714 return;
715 dbg_printf("add set global %lu\n", count);
716 cds_lfht_resize_lazy_count(ht, size,
717 count >> (CHAIN_LEN_TARGET - 1));
718 }
719
720 static
721 void ht_count_del(struct cds_lfht *ht, unsigned long size, unsigned long hash)
722 {
723 unsigned long split_count, count;
724 int index;
725
726 if (caa_unlikely(!ht->split_count))
727 return;
728 index = ht_get_split_count_index(hash);
729 split_count = uatomic_add_return(&ht->split_count[index].del, 1);
730 if (caa_likely(split_count & ((1UL << COUNT_COMMIT_ORDER) - 1)))
731 return;
732 /* Only if number of deletes multiple of 1UL << COUNT_COMMIT_ORDER */
733
734 dbg_printf("del split count %lu\n", split_count);
735 count = uatomic_add_return(&ht->count,
736 -(1UL << COUNT_COMMIT_ORDER));
737 if (caa_likely(count & (count - 1)))
738 return;
739 /* Only if global count is power of 2 */
740
741 if ((count >> CHAIN_LEN_RESIZE_THRESHOLD) >= size)
742 return;
743 dbg_printf("del set global %lu\n", count);
744 /*
745 * Don't shrink table if the number of nodes is below a
746 * certain threshold.
747 */
748 if (count < (1UL << COUNT_COMMIT_ORDER) * (split_count_mask + 1))
749 return;
750 cds_lfht_resize_lazy_count(ht, size,
751 count >> (CHAIN_LEN_TARGET - 1));
752 }
753
754 static
755 void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len)
756 {
757 unsigned long count;
758
759 if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
760 return;
761 count = uatomic_read(&ht->count);
762 /*
763 * Use bucket-local length for small table expand and for
764 * environments lacking per-cpu data support.
765 */
766 if (count >= (1UL << (COUNT_COMMIT_ORDER + split_count_order)))
767 return;
768 if (chain_len > 100)
769 dbg_printf("WARNING: large chain length: %u.\n",
770 chain_len);
771 if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD) {
772 int growth;
773
774 /*
775 * Ideal growth calculated based on chain length.
776 */
777 growth = cds_lfht_get_count_order_u32(chain_len
778 - (CHAIN_LEN_TARGET - 1));
779 if ((ht->flags & CDS_LFHT_ACCOUNTING)
780 && (size << growth)
781 >= (1UL << (COUNT_COMMIT_ORDER
782 + split_count_order))) {
783 /*
784 * If ideal growth expands the hash table size
785 * beyond the "small hash table" sizes, use the
786 * maximum small hash table size to attempt
787 * expanding the hash table. This only applies
788 * when node accounting is available, otherwise
789 * the chain length is used to expand the hash
790 * table in every case.
791 */
792 growth = COUNT_COMMIT_ORDER + split_count_order
793 - cds_lfht_get_count_order_ulong(size);
794 if (growth <= 0)
795 return;
796 }
797 cds_lfht_resize_lazy_grow(ht, size, growth);
798 }
799 }
800
801 static
802 struct cds_lfht_node *clear_flag(struct cds_lfht_node *node)
803 {
804 return (struct cds_lfht_node *) (((unsigned long) node) & ~FLAGS_MASK);
805 }
806
807 static
808 int is_removed(const struct cds_lfht_node *node)
809 {
810 return ((unsigned long) node) & REMOVED_FLAG;
811 }
812
813 static
814 int is_bucket(struct cds_lfht_node *node)
815 {
816 return ((unsigned long) node) & BUCKET_FLAG;
817 }
818
819 static
820 struct cds_lfht_node *flag_bucket(struct cds_lfht_node *node)
821 {
822 return (struct cds_lfht_node *) (((unsigned long) node) | BUCKET_FLAG);
823 }
824
825 static
826 int is_removal_owner(struct cds_lfht_node *node)
827 {
828 return ((unsigned long) node) & REMOVAL_OWNER_FLAG;
829 }
830
831 static
832 struct cds_lfht_node *flag_removed(struct cds_lfht_node *node)
833 {
834 return (struct cds_lfht_node *) (((unsigned long) node) | REMOVED_FLAG);
835 }
836
837 static
838 struct cds_lfht_node *flag_removal_owner(struct cds_lfht_node *node)
839 {
840 return (struct cds_lfht_node *) (((unsigned long) node) | REMOVAL_OWNER_FLAG);
841 }
842
843 static
844 struct cds_lfht_node *flag_removed_or_removal_owner(struct cds_lfht_node *node)
845 {
846 return (struct cds_lfht_node *) (((unsigned long) node) | REMOVED_FLAG | REMOVAL_OWNER_FLAG);
847 }
848
849 static
850 struct cds_lfht_node *get_end(void)
851 {
852 return (struct cds_lfht_node *) END_VALUE;
853 }
854
855 static
856 int is_end(struct cds_lfht_node *node)
857 {
858 return clear_flag(node) == (struct cds_lfht_node *) END_VALUE;
859 }
860
861 static
862 unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
863 unsigned long v)
864 {
865 unsigned long old1, old2;
866
867 old1 = uatomic_read(ptr);
868 do {
869 old2 = old1;
870 if (old2 >= v) {
871 cmm_smp_mb();
872 return old2;
873 }
874 } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
875 return old2;
876 }
877
878 static
879 void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
880 {
881 return ht->mm->alloc_bucket_table(ht, order);
882 }
883
884 /*
885 * cds_lfht_free_bucket_table() should be called with decreasing order.
886 * When cds_lfht_free_bucket_table(0) is called, it means the whole
887 * lfht is destroyed.
888 */
889 static
890 void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
891 {
892 return ht->mm->free_bucket_table(ht, order);
893 }
894
895 static inline
896 struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
897 {
898 return ht->bucket_at(ht, index);
899 }
900
901 static inline
902 struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
903 unsigned long hash)
904 {
905 urcu_posix_assert(size > 0);
906 return bucket_at(ht, hash & (size - 1));
907 }
908
909 /*
910 * Remove all logically deleted nodes from a bucket up to a certain node key.
911 */
912 static
913 void _cds_lfht_gc_bucket(struct cds_lfht_node *bucket, struct cds_lfht_node *node)
914 {
915 struct cds_lfht_node *iter_prev, *iter, *next, *new_next;
916
917 urcu_posix_assert(!is_bucket(bucket));
918 urcu_posix_assert(!is_removed(bucket));
919 urcu_posix_assert(!is_removal_owner(bucket));
920 urcu_posix_assert(!is_bucket(node));
921 urcu_posix_assert(!is_removed(node));
922 urcu_posix_assert(!is_removal_owner(node));
923 for (;;) {
924 iter_prev = bucket;
925 /* We can always skip the bucket node initially */
926 iter = rcu_dereference(iter_prev->next);
927 urcu_posix_assert(!is_removed(iter));
928 urcu_posix_assert(!is_removal_owner(iter));
929 urcu_posix_assert(iter_prev->reverse_hash <= node->reverse_hash);
930 /*
931 * We should never be called with bucket (start of chain)
932 * and logically removed node (end of path compression
933 * marker) being the actual same node. This would be a
934 * bug in the algorithm implementation.
935 */
936 urcu_posix_assert(bucket != node);
937 for (;;) {
938 if (caa_unlikely(is_end(iter)))
939 return;
940 if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
941 return;
942 next = rcu_dereference(clear_flag(iter)->next);
943 if (caa_likely(is_removed(next)))
944 break;
945 iter_prev = clear_flag(iter);
946 iter = next;
947 }
948 urcu_posix_assert(!is_removed(iter));
949 urcu_posix_assert(!is_removal_owner(iter));
950 if (is_bucket(iter))
951 new_next = flag_bucket(clear_flag(next));
952 else
953 new_next = clear_flag(next);
954 (void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
955 }
956 }
957
958 static
959 int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
960 struct cds_lfht_node *old_node,
961 struct cds_lfht_node *old_next,
962 struct cds_lfht_node *new_node)
963 {
964 struct cds_lfht_node *bucket, *ret_next;
965
966 if (!old_node) /* Return -ENOENT if asked to replace NULL node */
967 return -ENOENT;
968
969 urcu_posix_assert(!is_removed(old_node));
970 urcu_posix_assert(!is_removal_owner(old_node));
971 urcu_posix_assert(!is_bucket(old_node));
972 urcu_posix_assert(!is_removed(new_node));
973 urcu_posix_assert(!is_removal_owner(new_node));
974 urcu_posix_assert(!is_bucket(new_node));
975 urcu_posix_assert(new_node != old_node);
976 for (;;) {
977 /* Insert after node to be replaced */
978 if (is_removed(old_next)) {
979 /*
980 * Too late, the old node has been removed under us
981 * between lookup and replace. Fail.
982 */
983 return -ENOENT;
984 }
985 urcu_posix_assert(old_next == clear_flag(old_next));
986 urcu_posix_assert(new_node != old_next);
987 /*
988 * REMOVAL_OWNER flag is _NEVER_ set before the REMOVED
989 * flag. It is either set atomically at the same time
990 * (replace) or after (del).
991 */
992 urcu_posix_assert(!is_removal_owner(old_next));
993 new_node->next = old_next;
994 /*
995 * Here is the whole trick for lock-free replace: we add
996 * the replacement node _after_ the node we want to
997 * replace by atomically setting its next pointer at the
998 * same time we set its removal flag. Given that
999 * the lookups/get next use an iterator aware of the
1000 * next pointer, they will either skip the old node due
1001 * to the removal flag and see the new node, or use
1002 * the old node, but will not see the new one.
1003 * This is a replacement of a node with another node
1004 * that has the same value: we are therefore not
1005 * removing a value from the hash table. We set both the
1006 * REMOVED and REMOVAL_OWNER flags atomically so we own
1007 * the node after successful cmpxchg.
1008 */
1009 ret_next = uatomic_cmpxchg(&old_node->next,
1010 old_next, flag_removed_or_removal_owner(new_node));
1011 if (ret_next == old_next)
1012 break; /* We performed the replacement. */
1013 old_next = ret_next;
1014 }
1015
1016 /*
1017 * Ensure that the old node is not visible to readers anymore:
1018 * lookup for the node, and remove it (along with any other
1019 * logically removed node) if found.
1020 */
1021 bucket = lookup_bucket(ht, size, bit_reverse_ulong(old_node->reverse_hash));
1022 _cds_lfht_gc_bucket(bucket, new_node);
1023
1024 urcu_posix_assert(is_removed(CMM_LOAD_SHARED(old_node->next)));
1025 return 0;
1026 }
1027
1028 /*
1029 * A non-NULL unique_ret pointer uses the "add unique" (or uniquify) add
1030 * mode. A NULL unique_ret allows creation of duplicate keys.
1031 */
1032 static
1033 void _cds_lfht_add(struct cds_lfht *ht,
1034 unsigned long hash,
1035 cds_lfht_match_fct match,
1036 const void *key,
1037 unsigned long size,
1038 struct cds_lfht_node *node,
1039 struct cds_lfht_iter *unique_ret,
1040 int bucket_flag)
1041 {
1042 struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
1043 *return_node;
1044 struct cds_lfht_node *bucket;
1045
1046 urcu_posix_assert(!is_bucket(node));
1047 urcu_posix_assert(!is_removed(node));
1048 urcu_posix_assert(!is_removal_owner(node));
1049 bucket = lookup_bucket(ht, size, hash);
1050 for (;;) {
1051 uint32_t chain_len = 0;
1052
1053 /*
1054 * iter_prev points to the non-removed node prior to the
1055 * insert location.
1056 */
1057 iter_prev = bucket;
1058 /* We can always skip the bucket node initially */
1059 iter = rcu_dereference(iter_prev->next);
1060 urcu_posix_assert(iter_prev->reverse_hash <= node->reverse_hash);
1061 for (;;) {
1062 if (caa_unlikely(is_end(iter)))
1063 goto insert;
1064 if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
1065 goto insert;
1066
1067 /* bucket node is the first node of the identical-hash-value chain */
1068 if (bucket_flag && clear_flag(iter)->reverse_hash == node->reverse_hash)
1069 goto insert;
1070
1071 next = rcu_dereference(clear_flag(iter)->next);
1072 if (caa_unlikely(is_removed(next)))
1073 goto gc_node;
1074
1075 /* uniquely add */
1076 if (unique_ret
1077 && !is_bucket(next)
1078 && clear_flag(iter)->reverse_hash == node->reverse_hash) {
1079 struct cds_lfht_iter d_iter = {
1080 .node = node,
1081 .next = iter,
1082 #ifdef CONFIG_CDS_LFHT_ITER_DEBUG
1083 .lfht = ht,
1084 #endif
1085 };
1086
1087 /*
1088 * uniquely adding inserts the node as the first
1089 * node of the identical-hash-value node chain.
1090 *
1091 * This semantic ensures no duplicated keys
1092 * should ever be observable in the table
1093 * (including traversing the table node by
1094 * node by forward iterations)
1095 */
1096 cds_lfht_next_duplicate(ht, match, key, &d_iter);
1097 if (!d_iter.node)
1098 goto insert;
1099
1100 *unique_ret = d_iter;
1101 return;
1102 }
1103
1104 /* Only account for identical reverse hash once */
1105 if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash
1106 && !is_bucket(next))
1107 check_resize(ht, size, ++chain_len);
1108 iter_prev = clear_flag(iter);
1109 iter = next;
1110 }
1111
1112 insert:
1113 urcu_posix_assert(node != clear_flag(iter));
1114 urcu_posix_assert(!is_removed(iter_prev));
1115 urcu_posix_assert(!is_removal_owner(iter_prev));
1116 urcu_posix_assert(!is_removed(iter));
1117 urcu_posix_assert(!is_removal_owner(iter));
1118 urcu_posix_assert(iter_prev != node);
1119 if (!bucket_flag)
1120 node->next = clear_flag(iter);
1121 else
1122 node->next = flag_bucket(clear_flag(iter));
1123 if (is_bucket(iter))
1124 new_node = flag_bucket(node);
1125 else
1126 new_node = node;
1127 if (uatomic_cmpxchg(&iter_prev->next, iter,
1128 new_node) != iter) {
1129 continue; /* retry */
1130 } else {
1131 return_node = node;
1132 goto end;
1133 }
1134
1135 gc_node:
1136 urcu_posix_assert(!is_removed(iter));
1137 urcu_posix_assert(!is_removal_owner(iter));
1138 if (is_bucket(iter))
1139 new_next = flag_bucket(clear_flag(next));
1140 else
1141 new_next = clear_flag(next);
1142 (void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
1143 /* retry */
1144 }
1145 end:
1146 if (unique_ret) {
1147 unique_ret->node = return_node;
1148 /* unique_ret->next left unset, never used. */
1149 }
1150 }
1151
1152 static
1153 int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
1154 struct cds_lfht_node *node)
1155 {
1156 struct cds_lfht_node *bucket, *next;
1157 struct cds_lfht_node **node_next;
1158
1159 if (!node) /* Return -ENOENT if asked to delete NULL node */
1160 return -ENOENT;
1161
1162 /* logically delete the node */
1163 urcu_posix_assert(!is_bucket(node));
1164 urcu_posix_assert(!is_removed(node));
1165 urcu_posix_assert(!is_removal_owner(node));
1166
1167 /*
1168 * We are first checking if the node had previously been
1169 * logically removed (this check is not atomic with setting the
1170 * logical removal flag). Return -ENOENT if the node had
1171 * previously been removed.
1172 */
1173 next = CMM_LOAD_SHARED(node->next); /* next is not dereferenced */
1174 if (caa_unlikely(is_removed(next)))
1175 return -ENOENT;
1176 urcu_posix_assert(!is_bucket(next));
1177 /*
1178 * The del operation semantic guarantees a full memory barrier
1179 * before the uatomic_or atomic commit of the deletion flag.
1180 *
1181 * We set the REMOVED_FLAG unconditionally. Note that there may
1182 * be more than one concurrent thread setting this flag.
1183 * Knowing which wins the race will be known after the garbage
1184 * collection phase, stay tuned!
1185 *
1186 * NOTE: The node_next variable is present to avoid breaking
1187 * strict-aliasing rules.
1188 */
1189 node_next = &node->next;
1190 uatomic_or_mo(node_next, REMOVED_FLAG, CMM_RELEASE);
1191
1192 /* We performed the (logical) deletion. */
1193
1194 /*
1195 * Ensure that the node is not visible to readers anymore: lookup for
1196 * the node, and remove it (along with any other logically removed node)
1197 * if found.
1198 */
1199 bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
1200 _cds_lfht_gc_bucket(bucket, node);
1201
1202 urcu_posix_assert(is_removed(CMM_LOAD_SHARED(node->next)));
1203 /*
1204 * Last phase: atomically exchange node->next with a version
1205 * having "REMOVAL_OWNER_FLAG" set. If the returned node->next
1206 * pointer did _not_ have "REMOVAL_OWNER_FLAG" set, we now own
1207 * the node and win the removal race.
1208 * It is interesting to note that all "add" paths are forbidden
1209 * to change the next pointer starting from the point where the
1210 * REMOVED_FLAG is set, so here using a read, followed by a
1211 * xchg() suffice to guarantee that the xchg() will ever only
1212 * set the "REMOVAL_OWNER_FLAG" (or change nothing if the flag
1213 * was already set).
1214 */
1215 if (!is_removal_owner(uatomic_xchg(&node->next,
1216 flag_removal_owner(uatomic_load(&node->next, CMM_RELAXED)))))
1217 return 0;
1218 else
1219 return -ENOENT;
1220 }
1221
1222 static
1223 void *partition_resize_thread(void *arg)
1224 {
1225 struct partition_resize_work *work = arg;
1226
1227 work->ht->flavor->register_thread();
1228 work->fct(work->ht, work->i, work->start, work->len);
1229 work->ht->flavor->unregister_thread();
1230 return NULL;
1231 }
1232
1233 static
1234 void partition_resize_helper(struct cds_lfht *ht, unsigned long i,
1235 unsigned long len,
1236 void (*fct)(struct cds_lfht *ht, unsigned long i,
1237 unsigned long start, unsigned long len))
1238 {
1239 unsigned long partition_len, start = 0;
1240 struct partition_resize_work *work;
1241 int ret;
1242 unsigned long thread, nr_threads;
1243 sigset_t newmask, oldmask;
1244
1245 urcu_posix_assert(nr_cpus_mask != -1);
1246 if (nr_cpus_mask < 0 || len < 2 * MIN_PARTITION_PER_THREAD)
1247 goto fallback;
1248
1249 /*
1250 * Note: nr_cpus_mask + 1 is always power of 2.
1251 * We spawn just the number of threads we need to satisfy the minimum
1252 * partition size, up to the number of CPUs in the system.
1253 */
1254 if (nr_cpus_mask > 0) {
1255 nr_threads = min_t(unsigned long, nr_cpus_mask + 1,
1256 len >> MIN_PARTITION_PER_THREAD_ORDER);
1257 } else {
1258 nr_threads = 1;
1259 }
1260 partition_len = len >> cds_lfht_get_count_order_ulong(nr_threads);
1261 work = calloc(nr_threads, sizeof(*work));
1262 if (!work) {
1263 dbg_printf("error allocating for resize, single-threading\n");
1264 goto fallback;
1265 }
1266
1267 ret = sigfillset(&newmask);
1268 urcu_posix_assert(!ret);
1269 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
1270 urcu_posix_assert(!ret);
1271
1272 for (thread = 0; thread < nr_threads; thread++) {
1273 work[thread].ht = ht;
1274 work[thread].i = i;
1275 work[thread].len = partition_len;
1276 work[thread].start = thread * partition_len;
1277 work[thread].fct = fct;
1278 ret = pthread_create(&(work[thread].thread_id),
1279 ht->caller_resize_attr ? &ht->resize_attr : NULL,
1280 partition_resize_thread, &work[thread]);
1281 if (ret == EAGAIN) {
1282 /*
1283 * Out of resources: wait and join the threads
1284 * we've created, then handle leftovers.
1285 */
1286 dbg_printf("error spawning for resize, single-threading\n");
1287 start = work[thread].start;
1288 len -= start;
1289 nr_threads = thread;
1290 break;
1291 }
1292 urcu_posix_assert(!ret);
1293 }
1294
1295 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
1296 urcu_posix_assert(!ret);
1297
1298 for (thread = 0; thread < nr_threads; thread++) {
1299 ret = pthread_join(work[thread].thread_id, NULL);
1300 urcu_posix_assert(!ret);
1301 }
1302 free(work);
1303
1304 /*
1305 * A pthread_create failure above will either lead in us having
1306 * no threads to join or starting at a non-zero offset,
1307 * fallback to single thread processing of leftovers.
1308 */
1309 if (start == 0 && nr_threads > 0)
1310 return;
1311 fallback:
1312 fct(ht, i, start, len);
1313 }
1314
1315 /*
1316 * Holding RCU read lock to protect _cds_lfht_add against memory
1317 * reclaim that could be performed by other worker threads (ABA
1318 * problem).
1319 *
1320 * When we reach a certain length, we can split this population phase over
1321 * many worker threads, based on the number of CPUs available in the system.
1322 * This should therefore take care of not having the expand lagging behind too
1323 * many concurrent insertion threads by using the scheduler's ability to
1324 * schedule bucket node population fairly with insertions.
1325 */
1326 static
1327 void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
1328 unsigned long start, unsigned long len)
1329 {
1330 unsigned long j, size = 1UL << (i - 1);
1331
1332 urcu_posix_assert(i > MIN_TABLE_ORDER);
1333 ht->flavor->read_lock();
1334 for (j = size + start; j < size + start + len; j++) {
1335 struct cds_lfht_node *new_node = bucket_at(ht, j);
1336
1337 urcu_posix_assert(j >= size && j < (size << 1));
1338 dbg_printf("init populate: order %lu index %lu hash %lu\n",
1339 i, j, j);
1340 new_node->reverse_hash = bit_reverse_ulong(j);
1341 _cds_lfht_add(ht, j, NULL, NULL, size, new_node, NULL, 1);
1342 }
1343 ht->flavor->read_unlock();
1344 }
1345
1346 static
1347 void init_table_populate(struct cds_lfht *ht, unsigned long i,
1348 unsigned long len)
1349 {
1350 partition_resize_helper(ht, i, len, init_table_populate_partition);
1351 }
1352
1353 static
1354 void init_table(struct cds_lfht *ht,
1355 unsigned long first_order, unsigned long last_order)
1356 {
1357 unsigned long i;
1358
1359 dbg_printf("init table: first_order %lu last_order %lu\n",
1360 first_order, last_order);
1361 urcu_posix_assert(first_order > MIN_TABLE_ORDER);
1362 for (i = first_order; i <= last_order; i++) {
1363 unsigned long len;
1364
1365 len = 1UL << (i - 1);
1366 dbg_printf("init order %lu len: %lu\n", i, len);
1367
1368 /* Stop expand if the resize target changes under us */
1369 if (CMM_LOAD_SHARED(ht->resize_target) < (1UL << i))
1370 break;
1371
1372 cds_lfht_alloc_bucket_table(ht, i);
1373
1374 /*
1375 * Set all bucket nodes reverse hash values for a level and
1376 * link all bucket nodes into the table.
1377 */
1378 init_table_populate(ht, i, len);
1379
1380 /*
1381 * Update table size.
1382 *
1383 * Populate data before RCU size.
1384 */
1385 uatomic_store(&ht->size, 1UL << i, CMM_RELEASE);
1386
1387 dbg_printf("init new size: %lu\n", 1UL << i);
1388 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
1389 break;
1390 }
1391 }
1392
1393 /*
1394 * Holding RCU read lock to protect _cds_lfht_remove against memory
1395 * reclaim that could be performed by other worker threads (ABA
1396 * problem).
1397 * For a single level, we logically remove and garbage collect each node.
1398 *
1399 * As a design choice, we perform logical removal and garbage collection on a
1400 * node-per-node basis to simplify this algorithm. We also assume keeping good
1401 * cache locality of the operation would overweight possible performance gain
1402 * that could be achieved by batching garbage collection for multiple levels.
1403 * However, this would have to be justified by benchmarks.
1404 *
1405 * Concurrent removal and add operations are helping us perform garbage
1406 * collection of logically removed nodes. We guarantee that all logically
1407 * removed nodes have been garbage-collected (unlinked) before work
1408 * enqueue is invoked to free a hole level of bucket nodes (after a
1409 * grace period).
1410 *
1411 * Logical removal and garbage collection can therefore be done in batch
1412 * or on a node-per-node basis, as long as the guarantee above holds.
1413 *
1414 * When we reach a certain length, we can split this removal over many worker
1415 * threads, based on the number of CPUs available in the system. This should
1416 * take care of not letting resize process lag behind too many concurrent
1417 * updater threads actively inserting into the hash table.
1418 */
1419 static
1420 void remove_table_partition(struct cds_lfht *ht, unsigned long i,
1421 unsigned long start, unsigned long len)
1422 {
1423 unsigned long j, size = 1UL << (i - 1);
1424
1425 urcu_posix_assert(i > MIN_TABLE_ORDER);
1426 ht->flavor->read_lock();
1427 for (j = size + start; j < size + start + len; j++) {
1428 struct cds_lfht_node *fini_bucket = bucket_at(ht, j);
1429 struct cds_lfht_node *parent_bucket = bucket_at(ht, j - size);
1430 struct cds_lfht_node **fini_bucket_next;
1431
1432 urcu_posix_assert(j >= size && j < (size << 1));
1433 dbg_printf("remove entry: order %lu index %lu hash %lu\n",
1434 i, j, j);
1435 /* Set the REMOVED_FLAG to freeze the ->next for gc.
1436 *
1437 * NOTE: The fini_bucket_next variable is present to
1438 * avoid breaking strict-aliasing rules.
1439 */
1440 fini_bucket_next = &fini_bucket->next;
1441 uatomic_or(fini_bucket_next, REMOVED_FLAG);
1442 _cds_lfht_gc_bucket(parent_bucket, fini_bucket);
1443 }
1444 ht->flavor->read_unlock();
1445 }
1446
1447 static
1448 void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
1449 {
1450 partition_resize_helper(ht, i, len, remove_table_partition);
1451 }
1452
1453 /*
1454 * fini_table() is never called for first_order == 0, which is why
1455 * free_by_rcu_order == 0 can be used as criterion to know if free must
1456 * be called.
1457 */
1458 static
1459 void fini_table(struct cds_lfht *ht,
1460 unsigned long first_order, unsigned long last_order)
1461 {
1462 unsigned long free_by_rcu_order = 0, i;
1463
1464 dbg_printf("fini table: first_order %lu last_order %lu\n",
1465 first_order, last_order);
1466 urcu_posix_assert(first_order > MIN_TABLE_ORDER);
1467 for (i = last_order; i >= first_order; i--) {
1468 unsigned long len;
1469
1470 len = 1UL << (i - 1);
1471 dbg_printf("fini order %ld len: %lu\n", i, len);
1472
1473 /* Stop shrink if the resize target changes under us */
1474 if (CMM_LOAD_SHARED(ht->resize_target) > (1UL << (i - 1)))
1475 break;
1476
1477 cmm_smp_wmb(); /* populate data before RCU size */
1478 CMM_STORE_SHARED(ht->size, 1UL << (i - 1));
1479
1480 /*
1481 * We need to wait for all add operations to reach Q.S. (and
1482 * thus use the new table for lookups) before we can start
1483 * releasing the old bucket nodes. Otherwise their lookup will
1484 * return a logically removed node as insert position.
1485 */
1486 ht->flavor->update_synchronize_rcu();
1487 if (free_by_rcu_order)
1488 cds_lfht_free_bucket_table(ht, free_by_rcu_order);
1489
1490 /*
1491 * Set "removed" flag in bucket nodes about to be removed.
1492 * Unlink all now-logically-removed bucket node pointers.
1493 * Concurrent add/remove operation are helping us doing
1494 * the gc.
1495 */
1496 remove_table(ht, i, len);
1497
1498 free_by_rcu_order = i;
1499
1500 dbg_printf("fini new size: %lu\n", 1UL << i);
1501 if (CMM_LOAD_SHARED(ht->in_progress_destroy))
1502 break;
1503 }
1504
1505 if (free_by_rcu_order) {
1506 ht->flavor->update_synchronize_rcu();
1507 cds_lfht_free_bucket_table(ht, free_by_rcu_order);
1508 }
1509 }
1510
1511 /*
1512 * Never called with size < 1.
1513 */
1514 static
1515 void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
1516 {
1517 struct cds_lfht_node *prev, *node;
1518 unsigned long order, len, i;
1519 int bucket_order;
1520
1521 cds_lfht_alloc_bucket_table(ht, 0);
1522
1523 dbg_printf("create bucket: order 0 index 0 hash 0\n");
1524 node = bucket_at(ht, 0);
1525 node->next = flag_bucket(get_end());
1526 node->reverse_hash = 0;
1527
1528 bucket_order = cds_lfht_get_count_order_ulong(size);
1529 urcu_posix_assert(bucket_order >= 0);
1530
1531 for (order = 1; order < (unsigned long) bucket_order + 1; order++) {
1532 len = 1UL << (order - 1);
1533 cds_lfht_alloc_bucket_table(ht, order);
1534
1535 for (i = 0; i < len; i++) {
1536 /*
1537 * Now, we are trying to init the node with the
1538 * hash=(len+i) (which is also a bucket with the
1539 * index=(len+i)) and insert it into the hash table,
1540 * so this node has to be inserted after the bucket
1541 * with the index=(len+i)&(len-1)=i. And because there
1542 * is no other non-bucket node nor bucket node with
1543 * larger index/hash inserted, so the bucket node
1544 * being inserted should be inserted directly linked
1545 * after the bucket node with index=i.
1546 */
1547 prev = bucket_at(ht, i);
1548 node = bucket_at(ht, len + i);
1549
1550 dbg_printf("create bucket: order %lu index %lu hash %lu\n",
1551 order, len + i, len + i);
1552 node->reverse_hash = bit_reverse_ulong(len + i);
1553
1554 /* insert after prev */
1555 urcu_posix_assert(is_bucket(prev->next));
1556 node->next = prev->next;
1557 prev->next = flag_bucket(node);
1558 }
1559 }
1560 }
1561
1562 #if (CAA_BITS_PER_LONG > 32)
1563 /*
1564 * For 64-bit architectures, with max number of buckets small enough not to
1565 * use the entire 64-bit memory mapping space (and allowing a fair number of
1566 * hash table instances), use the mmap allocator, which is faster. Otherwise,
1567 * fallback to the order allocator.
1568 */
1569 static
1570 const struct cds_lfht_mm_type *get_mm_type(unsigned long max_nr_buckets)
1571 {
1572 if (max_nr_buckets && max_nr_buckets <= (1ULL << 32))
1573 return &cds_lfht_mm_mmap;
1574 else
1575 return &cds_lfht_mm_order;
1576 }
1577 #else
1578 /*
1579 * For 32-bit architectures, use the order allocator.
1580 */
1581 static
1582 const struct cds_lfht_mm_type *get_mm_type(
1583 unsigned long max_nr_buckets __attribute__((unused)))
1584 {
1585 return &cds_lfht_mm_order;
1586 }
1587 #endif
1588
1589 void cds_lfht_node_init_deleted(struct cds_lfht_node *node)
1590 {
1591 cds_lfht_node_init(node);
1592 node->next = flag_removed(NULL);
1593 }
1594
1595 struct cds_lfht *_cds_lfht_new(unsigned long init_size,
1596 unsigned long min_nr_alloc_buckets,
1597 unsigned long max_nr_buckets,
1598 int flags,
1599 const struct cds_lfht_mm_type *mm,
1600 const struct rcu_flavor_struct *flavor,
1601 pthread_attr_t *attr)
1602 {
1603 struct cds_lfht *ht;
1604 unsigned long order;
1605
1606 /* min_nr_alloc_buckets must be power of two */
1607 if (!min_nr_alloc_buckets || (min_nr_alloc_buckets & (min_nr_alloc_buckets - 1)))
1608 return NULL;
1609
1610 /* init_size must be power of two */
1611 if (!init_size || (init_size & (init_size - 1)))
1612 return NULL;
1613
1614 /*
1615 * Memory management plugin default.
1616 */
1617 if (!mm)
1618 mm = get_mm_type(max_nr_buckets);
1619
1620 /* max_nr_buckets == 0 for order based mm means infinite */
1621 if (mm == &cds_lfht_mm_order && !max_nr_buckets)
1622 max_nr_buckets = 1UL << (MAX_TABLE_ORDER - 1);
1623
1624 /* max_nr_buckets must be power of two */
1625 if (!max_nr_buckets || (max_nr_buckets & (max_nr_buckets - 1)))
1626 return NULL;
1627
1628 if (flags & CDS_LFHT_AUTO_RESIZE)
1629 cds_lfht_init_worker(flavor);
1630
1631 min_nr_alloc_buckets = max(min_nr_alloc_buckets, MIN_TABLE_SIZE);
1632 init_size = max(init_size, MIN_TABLE_SIZE);
1633 max_nr_buckets = max(max_nr_buckets, min_nr_alloc_buckets);
1634 init_size = min(init_size, max_nr_buckets);
1635
1636 ht = mm->alloc_cds_lfht(min_nr_alloc_buckets, max_nr_buckets);
1637 urcu_posix_assert(ht);
1638 urcu_posix_assert(ht->mm == mm);
1639 urcu_posix_assert(ht->bucket_at == mm->bucket_at);
1640
1641 ht->flags = flags;
1642 ht->flavor = flavor;
1643 ht->caller_resize_attr = attr;
1644 if (attr)
1645 ht->resize_attr = *attr;
1646 alloc_split_items_count(ht);
1647 /* this mutex should not nest in read-side C.S. */
1648 pthread_mutex_init(&ht->resize_mutex, NULL);
1649 order = cds_lfht_get_count_order_ulong(init_size);
1650 ht->resize_target = 1UL << order;
1651 cds_lfht_create_bucket(ht, 1UL << order);
1652 ht->size = 1UL << order;
1653 return ht;
1654 }
1655
1656 void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
1657 cds_lfht_match_fct match, const void *key,
1658 struct cds_lfht_iter *iter)
1659 {
1660 struct cds_lfht_node *node, *next, *bucket;
1661 unsigned long reverse_hash, size;
1662
1663 cds_lfht_iter_debug_set_ht(ht, iter);
1664
1665 reverse_hash = bit_reverse_ulong(hash);
1666
1667 /*
1668 * Use load acquire instead of rcu_dereference because there is no
1669 * dependency between the table size and the dereference of the bucket
1670 * content.
1671 *
1672 * This acquire is paired with the store release in init_table().
1673 */
1674 size = uatomic_load(&ht->size, CMM_ACQUIRE);
1675 bucket = lookup_bucket(ht, size, hash);
1676 /* We can always skip the bucket node initially */
1677 node = rcu_dereference(bucket->next);
1678 node = clear_flag(node);
1679 for (;;) {
1680 if (caa_unlikely(is_end(node))) {
1681 node = next = NULL;
1682 break;
1683 }
1684 if (caa_unlikely(node->reverse_hash > reverse_hash)) {
1685 node = next = NULL;
1686 break;
1687 }
1688 next = rcu_dereference(node->next);
1689 urcu_posix_assert(node == clear_flag(node));
1690 if (caa_likely(!is_removed(next))
1691 && !is_bucket(next)
1692 && node->reverse_hash == reverse_hash
1693 && caa_likely(match(node, key))) {
1694 break;
1695 }
1696 node = clear_flag(next);
1697 }
1698 urcu_posix_assert(!node || !is_bucket(CMM_LOAD_SHARED(node->next)));
1699 iter->node = node;
1700 iter->next = next;
1701 }
1702
1703 void cds_lfht_next_duplicate(struct cds_lfht *ht __attribute__((unused)),
1704 cds_lfht_match_fct match,
1705 const void *key, struct cds_lfht_iter *iter)
1706 {
1707 struct cds_lfht_node *node, *next;
1708 unsigned long reverse_hash;
1709
1710 cds_lfht_iter_debug_assert(ht == iter->lfht);
1711 node = iter->node;
1712 reverse_hash = node->reverse_hash;
1713 next = iter->next;
1714 node = clear_flag(next);
1715
1716 for (;;) {
1717 if (caa_unlikely(is_end(node))) {
1718 node = next = NULL;
1719 break;
1720 }
1721 if (caa_unlikely(node->reverse_hash > reverse_hash)) {
1722 node = next = NULL;
1723 break;
1724 }
1725 next = rcu_dereference(node->next);
1726 if (caa_likely(!is_removed(next))
1727 && !is_bucket(next)
1728 && caa_likely(match(node, key))) {
1729 break;
1730 }
1731 node = clear_flag(next);
1732 }
1733 urcu_posix_assert(!node || !is_bucket(uatomic_load(&node->next, CMM_RELAXED)));
1734 iter->node = node;
1735 iter->next = next;
1736 }
1737
1738 void cds_lfht_next(struct cds_lfht *ht __attribute__((unused)),
1739 struct cds_lfht_iter *iter)
1740 {
1741 struct cds_lfht_node *node, *next;
1742
1743 cds_lfht_iter_debug_assert(ht == iter->lfht);
1744 node = clear_flag(iter->next);
1745 for (;;) {
1746 if (caa_unlikely(is_end(node))) {
1747 node = next = NULL;
1748 break;
1749 }
1750 next = rcu_dereference(node->next);
1751 if (caa_likely(!is_removed(next))
1752 && !is_bucket(next)) {
1753 break;
1754 }
1755 node = clear_flag(next);
1756 }
1757 urcu_posix_assert(!node || !is_bucket(uatomic_load(&node->next, CMM_RELAXED)));
1758 iter->node = node;
1759 iter->next = next;
1760 }
1761
1762 void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
1763 {
1764 cds_lfht_iter_debug_set_ht(ht, iter);
1765 /*
1766 * Get next after first bucket node. The first bucket node is the
1767 * first node of the linked list.
1768 */
1769 iter->next = uatomic_load(&bucket_at(ht, 0)->next, CMM_CONSUME);
1770 cds_lfht_next(ht, iter);
1771 }
1772
1773 void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
1774 struct cds_lfht_node *node)
1775 {
1776 unsigned long size;
1777
1778 node->reverse_hash = bit_reverse_ulong(hash);
1779 size = uatomic_load(&ht->size, CMM_ACQUIRE);
1780 _cds_lfht_add(ht, hash, NULL, NULL, size, node, NULL, 0);
1781 ht_count_add(ht, size, hash);
1782 }
1783
1784 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
1785 unsigned long hash,
1786 cds_lfht_match_fct match,
1787 const void *key,
1788 struct cds_lfht_node *node)
1789 {
1790 unsigned long size;
1791 struct cds_lfht_iter iter;
1792
1793 node->reverse_hash = bit_reverse_ulong(hash);
1794 size = uatomic_load(&ht->size, CMM_ACQUIRE);
1795 _cds_lfht_add(ht, hash, match, key, size, node, &iter, 0);
1796 if (iter.node == node)
1797 ht_count_add(ht, size, hash);
1798 return iter.node;
1799 }
1800
1801 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
1802 unsigned long hash,
1803 cds_lfht_match_fct match,
1804 const void *key,
1805 struct cds_lfht_node *node)
1806 {
1807 unsigned long size;
1808 struct cds_lfht_iter iter;
1809
1810 node->reverse_hash = bit_reverse_ulong(hash);
1811 size = uatomic_load(&ht->size, CMM_ACQUIRE);
1812 for (;;) {
1813 _cds_lfht_add(ht, hash, match, key, size, node, &iter, 0);
1814 if (iter.node == node) {
1815 ht_count_add(ht, size, hash);
1816 return NULL;
1817 }
1818
1819 if (!_cds_lfht_replace(ht, size, iter.node, iter.next, node))
1820 return iter.node;
1821 }
1822 }
1823
1824 int cds_lfht_replace(struct cds_lfht *ht,
1825 struct cds_lfht_iter *old_iter,
1826 unsigned long hash,
1827 cds_lfht_match_fct match,
1828 const void *key,
1829 struct cds_lfht_node *new_node)
1830 {
1831 unsigned long size;
1832
1833 new_node->reverse_hash = bit_reverse_ulong(hash);
1834 if (!old_iter->node)
1835 return -ENOENT;
1836 if (caa_unlikely(old_iter->node->reverse_hash != new_node->reverse_hash))
1837 return -EINVAL;
1838 if (caa_unlikely(!match(old_iter->node, key)))
1839 return -EINVAL;
1840 size = uatomic_load(&ht->size, CMM_ACQUIRE);
1841 return _cds_lfht_replace(ht, size, old_iter->node, old_iter->next,
1842 new_node);
1843 }
1844
1845 int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node)
1846 {
1847 unsigned long size;
1848 int ret;
1849
1850 size = uatomic_load(&ht->size, CMM_ACQUIRE);
1851 ret = _cds_lfht_del(ht, size, node);
1852 if (!ret) {
1853 unsigned long hash;
1854
1855 hash = bit_reverse_ulong(node->reverse_hash);
1856 ht_count_del(ht, size, hash);
1857 }
1858 return ret;
1859 }
1860
1861 int cds_lfht_is_node_deleted(const struct cds_lfht_node *node)
1862 {
1863 return is_removed(CMM_LOAD_SHARED(node->next));
1864 }
1865
1866 static
1867 bool cds_lfht_is_empty(struct cds_lfht *ht)
1868 {
1869 struct cds_lfht_node *node, *next;
1870 bool empty = true;
1871 bool was_online;
1872
1873 was_online = ht->flavor->read_ongoing();
1874 if (!was_online) {
1875 ht->flavor->thread_online();
1876 ht->flavor->read_lock();
1877 }
1878 /* Check that the table is empty */
1879 node = bucket_at(ht, 0);
1880 do {
1881 next = rcu_dereference(node->next);
1882 if (!is_bucket(next)) {
1883 empty = false;
1884 break;
1885 }
1886 node = clear_flag(next);
1887 } while (!is_end(node));
1888 if (!was_online) {
1889 ht->flavor->read_unlock();
1890 ht->flavor->thread_offline();
1891 }
1892 return empty;
1893 }
1894
1895 static
1896 int cds_lfht_delete_bucket(struct cds_lfht *ht)
1897 {
1898 struct cds_lfht_node *node;
1899 unsigned long order, i, size;
1900
1901 /* Check that the table is empty */
1902 node = bucket_at(ht, 0);
1903 do {
1904 node = clear_flag(node)->next;
1905 if (!is_bucket(node))
1906 return -EPERM;
1907 urcu_posix_assert(!is_removed(node));
1908 urcu_posix_assert(!is_removal_owner(node));
1909 } while (!is_end(node));
1910 /*
1911 * size accessed without rcu_dereference because hash table is
1912 * being destroyed.
1913 */
1914 size = ht->size;
1915 /* Internal sanity check: all nodes left should be buckets */
1916 for (i = 0; i < size; i++) {
1917 node = bucket_at(ht, i);
1918 dbg_printf("delete bucket: index %lu expected hash %lu hash %lu\n",
1919 i, i, bit_reverse_ulong(node->reverse_hash));
1920 urcu_posix_assert(is_bucket(node->next));
1921 }
1922
1923 for (order = cds_lfht_get_count_order_ulong(size); (long)order >= 0; order--)
1924 cds_lfht_free_bucket_table(ht, order);
1925
1926 return 0;
1927 }
1928
1929 static
1930 void do_auto_resize_destroy_cb(struct urcu_work *work)
1931 {
1932 struct cds_lfht *ht = caa_container_of(work, struct cds_lfht, destroy_work);
1933 int ret;
1934
1935 ht->flavor->register_thread();
1936 ret = cds_lfht_delete_bucket(ht);
1937 if (ret)
1938 urcu_die(-ret);
1939 free_split_items_count(ht);
1940 ret = pthread_mutex_destroy(&ht->resize_mutex);
1941 if (ret)
1942 urcu_die(ret);
1943 ht->flavor->unregister_thread();
1944 poison_free(ht);
1945 }
1946
1947 /*
1948 * Should only be called when no more concurrent readers nor writers can
1949 * possibly access the table.
1950 */
1951 int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)
1952 {
1953 int ret;
1954
1955 if (ht->flags & CDS_LFHT_AUTO_RESIZE) {
1956 /*
1957 * Perform error-checking for emptiness before queuing
1958 * work, so we can return error to the caller. This runs
1959 * concurrently with ongoing resize.
1960 */
1961 if (!cds_lfht_is_empty(ht))
1962 return -EPERM;
1963 /* Cancel ongoing resize operations. */
1964 uatomic_store(&ht->in_progress_destroy, 1, CMM_RELAXED);
1965 if (attr) {
1966 *attr = ht->caller_resize_attr;
1967 ht->caller_resize_attr = NULL;
1968 }
1969 /*
1970 * Queue destroy work after prior queued resize
1971 * operations. Given there are no concurrent writers
1972 * accessing the hash table at this point, no resize
1973 * operations can be queued after this destroy work.
1974 */
1975 urcu_workqueue_queue_work(cds_lfht_workqueue,
1976 &ht->destroy_work, do_auto_resize_destroy_cb);
1977 return 0;
1978 }
1979 ret = cds_lfht_delete_bucket(ht);
1980 if (ret)
1981 return ret;
1982 free_split_items_count(ht);
1983 if (attr)
1984 *attr = ht->caller_resize_attr;
1985 ret = pthread_mutex_destroy(&ht->resize_mutex);
1986 if (ret)
1987 ret = -EBUSY;
1988 poison_free(ht);
1989 return ret;
1990 }
1991
1992 void cds_lfht_count_nodes(struct cds_lfht *ht,
1993 long *approx_before,
1994 unsigned long *count,
1995 long *approx_after)
1996 {
1997 struct cds_lfht_node *node, *next;
1998 unsigned long nr_bucket = 0, nr_removed = 0;
1999
2000 *approx_before = 0;
2001 if (ht->split_count) {
2002 int i;
2003
2004 for (i = 0; i < split_count_mask + 1; i++) {
2005 *approx_before += uatomic_read(&ht->split_count[i].add);
2006 *approx_before -= uatomic_read(&ht->split_count[i].del);
2007 }
2008 }
2009
2010 *count = 0;
2011
2012 /* Count non-bucket nodes in the table */
2013 node = bucket_at(ht, 0);
2014 do {
2015 next = rcu_dereference(node->next);
2016 if (is_removed(next)) {
2017 if (!is_bucket(next))
2018 (nr_removed)++;
2019 else
2020 (nr_bucket)++;
2021 } else if (!is_bucket(next))
2022 (*count)++;
2023 else
2024 (nr_bucket)++;
2025 node = clear_flag(next);
2026 } while (!is_end(node));
2027 dbg_printf("number of logically removed nodes: %lu\n", nr_removed);
2028 dbg_printf("number of bucket nodes: %lu\n", nr_bucket);
2029 *approx_after = 0;
2030 if (ht->split_count) {
2031 int i;
2032
2033 for (i = 0; i < split_count_mask + 1; i++) {
2034 *approx_after += uatomic_read(&ht->split_count[i].add);
2035 *approx_after -= uatomic_read(&ht->split_count[i].del);
2036 }
2037 }
2038 }
2039
2040 /* called with resize mutex held */
2041 static
2042 void _do_cds_lfht_grow(struct cds_lfht *ht,
2043 unsigned long old_size, unsigned long new_size)
2044 {
2045 unsigned long old_order, new_order;
2046
2047 old_order = cds_lfht_get_count_order_ulong(old_size);
2048 new_order = cds_lfht_get_count_order_ulong(new_size);
2049 dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
2050 old_size, old_order, new_size, new_order);
2051 urcu_posix_assert(new_size > old_size);
2052 init_table(ht, old_order + 1, new_order);
2053 }
2054
2055 /* called with resize mutex held */
2056 static
2057 void _do_cds_lfht_shrink(struct cds_lfht *ht,
2058 unsigned long old_size, unsigned long new_size)
2059 {
2060 unsigned long old_order, new_order;
2061
2062 new_size = max(new_size, MIN_TABLE_SIZE);
2063 old_order = cds_lfht_get_count_order_ulong(old_size);
2064 new_order = cds_lfht_get_count_order_ulong(new_size);
2065 dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
2066 old_size, old_order, new_size, new_order);
2067 urcu_posix_assert(new_size < old_size);
2068
2069 /* Remove and unlink all bucket nodes to remove. */
2070 fini_table(ht, new_order + 1, old_order);
2071 }
2072
2073
2074 /* called with resize mutex held */
2075 static
2076 void _do_cds_lfht_resize(struct cds_lfht *ht)
2077 {
2078 unsigned long new_size, old_size;
2079
2080 /*
2081 * Resize table, re-do if the target size has changed under us.
2082 */
2083 do {
2084 if (uatomic_load(&ht->in_progress_destroy, CMM_RELAXED))
2085 break;
2086
2087 uatomic_store(&ht->resize_initiated, 1, CMM_RELAXED);
2088
2089 old_size = ht->size;
2090 new_size = uatomic_load(&ht->resize_target, CMM_RELAXED);
2091 if (old_size < new_size)
2092 _do_cds_lfht_grow(ht, old_size, new_size);
2093 else if (old_size > new_size)
2094 _do_cds_lfht_shrink(ht, old_size, new_size);
2095
2096 uatomic_store(&ht->resize_initiated, 0, CMM_RELAXED);
2097 /* write resize_initiated before read resize_target */
2098 cmm_smp_mb();
2099 } while (ht->size != uatomic_load(&ht->resize_target, CMM_RELAXED));
2100 }
2101
2102 static
2103 unsigned long resize_target_grow(struct cds_lfht *ht, unsigned long new_size)
2104 {
2105 return _uatomic_xchg_monotonic_increase(&ht->resize_target, new_size);
2106 }
2107
2108 static
2109 void resize_target_update_count(struct cds_lfht *ht,
2110 unsigned long count)
2111 {
2112 count = max(count, MIN_TABLE_SIZE);
2113 count = min(count, ht->max_nr_buckets);
2114 uatomic_set(&ht->resize_target, count);
2115 }
2116
2117 void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size)
2118 {
2119 resize_target_update_count(ht, new_size);
2120
2121 /*
2122 * Set flags has early as possible even in contention case.
2123 */
2124 uatomic_store(&ht->resize_initiated, 1, CMM_RELAXED);
2125
2126 mutex_lock(&ht->resize_mutex);
2127 _do_cds_lfht_resize(ht);
2128 mutex_unlock(&ht->resize_mutex);
2129 }
2130
2131 static
2132 void do_resize_cb(struct urcu_work *work)
2133 {
2134 struct resize_work *resize_work =
2135 caa_container_of(work, struct resize_work, work);
2136 struct cds_lfht *ht = resize_work->ht;
2137
2138 ht->flavor->register_thread();
2139 mutex_lock(&ht->resize_mutex);
2140 _do_cds_lfht_resize(ht);
2141 mutex_unlock(&ht->resize_mutex);
2142 ht->flavor->unregister_thread();
2143 poison_free(work);
2144 }
2145
2146 static
2147 void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
2148 {
2149 struct resize_work *work;
2150
2151 /*
2152 * Store to resize_target is before read resize_initiated as guaranteed
2153 * by either cmpxchg or _uatomic_xchg_monotonic_increase.
2154 */
2155 if (!uatomic_load(&ht->resize_initiated, CMM_RELAXED)) {
2156 if (uatomic_load(&ht->in_progress_destroy, CMM_RELAXED)) {
2157 return;
2158 }
2159 work = malloc(sizeof(*work));
2160 if (work == NULL) {
2161 dbg_printf("error allocating resize work, bailing out\n");
2162 return;
2163 }
2164 work->ht = ht;
2165 urcu_workqueue_queue_work(cds_lfht_workqueue,
2166 &work->work, do_resize_cb);
2167 uatomic_store(&ht->resize_initiated, 1, CMM_RELAXED);
2168 }
2169 }
2170
2171 static
2172 void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth)
2173 {
2174 unsigned long target_size = size << growth;
2175
2176 target_size = min(target_size, ht->max_nr_buckets);
2177 if (resize_target_grow(ht, target_size) >= target_size)
2178 return;
2179
2180 __cds_lfht_resize_lazy_launch(ht);
2181 }
2182
2183 /*
2184 * We favor grow operations over shrink. A shrink operation never occurs
2185 * if a grow operation is queued for lazy execution. A grow operation
2186 * cancels any pending shrink lazy execution.
2187 */
2188 static
2189 void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
2190 unsigned long count)
2191 {
2192 if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
2193 return;
2194 count = max(count, MIN_TABLE_SIZE);
2195 count = min(count, ht->max_nr_buckets);
2196 if (count == size)
2197 return; /* Already the right size, no resize needed */
2198 if (count > size) { /* lazy grow */
2199 if (resize_target_grow(ht, count) >= count)
2200 return;
2201 } else { /* lazy shrink */
2202 for (;;) {
2203 unsigned long s;
2204
2205 s = uatomic_cmpxchg(&ht->resize_target, size, count);
2206 if (s == size)
2207 break; /* no resize needed */
2208 if (s > size)
2209 return; /* growing is/(was just) in progress */
2210 if (s <= count)
2211 return; /* some other thread do shrink */
2212 size = s;
2213 }
2214 }
2215 __cds_lfht_resize_lazy_launch(ht);
2216 }
2217
2218 static void cds_lfht_before_fork(void *priv __attribute__((unused)))
2219 {
2220 if (cds_lfht_workqueue_atfork_nesting++)
2221 return;
2222 mutex_lock(&cds_lfht_fork_mutex);
2223 if (!cds_lfht_workqueue)
2224 return;
2225 urcu_workqueue_pause_worker(cds_lfht_workqueue);
2226 }
2227
2228 static void cds_lfht_after_fork_parent(void *priv __attribute__((unused)))
2229 {
2230 if (--cds_lfht_workqueue_atfork_nesting)
2231 return;
2232 if (!cds_lfht_workqueue)
2233 goto end;
2234 urcu_workqueue_resume_worker(cds_lfht_workqueue);
2235 end:
2236 mutex_unlock(&cds_lfht_fork_mutex);
2237 }
2238
2239 static void cds_lfht_after_fork_child(void *priv __attribute__((unused)))
2240 {
2241 if (--cds_lfht_workqueue_atfork_nesting)
2242 return;
2243 if (!cds_lfht_workqueue)
2244 goto end;
2245 urcu_workqueue_create_worker(cds_lfht_workqueue);
2246 end:
2247 mutex_unlock(&cds_lfht_fork_mutex);
2248 }
2249
2250 static struct urcu_atfork cds_lfht_atfork = {
2251 .before_fork = cds_lfht_before_fork,
2252 .after_fork_parent = cds_lfht_after_fork_parent,
2253 .after_fork_child = cds_lfht_after_fork_child,
2254 };
2255
2256 static void cds_lfht_init_worker(const struct rcu_flavor_struct *flavor)
2257 {
2258 flavor->register_rculfhash_atfork(&cds_lfht_atfork);
2259
2260 mutex_lock(&cds_lfht_fork_mutex);
2261 if (!cds_lfht_workqueue)
2262 cds_lfht_workqueue = urcu_workqueue_create(0, -1, NULL,
2263 NULL, NULL, NULL, NULL, NULL, NULL, NULL);
2264 mutex_unlock(&cds_lfht_fork_mutex);
2265 }
2266
2267 static void cds_lfht_exit(void)
2268 {
2269 mutex_lock(&cds_lfht_fork_mutex);
2270 if (cds_lfht_workqueue) {
2271 urcu_workqueue_flush_queued_work(cds_lfht_workqueue);
2272 urcu_workqueue_destroy(cds_lfht_workqueue);
2273 cds_lfht_workqueue = NULL;
2274 }
2275 mutex_unlock(&cds_lfht_fork_mutex);
2276 }
This page took 0.075813 seconds and 4 git commands to generate.