projects / userspace-rcu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
rcuja: implement lookup_lower_equal
[userspace-rcu.git] / rcuja / rcuja.c
1 /*
2 * rcuja/rcuja.c
3 *
4 * Userspace RCU library - RCU Judy Array
5 *
6 * Copyright 2012 - 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
21 */
22
23 #define _LGPL_SOURCE
24 #include <stdint.h>
25 #include <errno.h>
26 #include <limits.h>
27 #include <string.h>
28 #include <urcu/rcuja.h>
29 #include <urcu/compiler.h>
30 #include <urcu/arch.h>
31 #include <assert.h>
32 #include <urcu-pointer.h>
33 #include <urcu/uatomic.h>
34 #include <stdint.h>
35
36 #include "rcuja-internal.h"
37 #include "bitfield.h"
38
39 #ifndef abs
40 #define abs_int(a) ((int) (a) > 0 ? (int) (a) : -((int) (a)))
41 #endif
42
43 enum cds_ja_type_class {
44 RCU_JA_LINEAR = 0, /* Type A */
45 /* 32-bit: 1 to 25 children, 8 to 128 bytes */
46 /* 64-bit: 1 to 28 children, 16 to 256 bytes */
47 RCU_JA_POOL = 1, /* Type B */
48 /* 32-bit: 26 to 100 children, 256 to 512 bytes */
49 /* 64-bit: 29 to 112 children, 512 to 1024 bytes */
50 RCU_JA_PIGEON = 2, /* Type C */
51 /* 32-bit: 101 to 256 children, 1024 bytes */
52 /* 64-bit: 113 to 256 children, 2048 bytes */
53 /* Leaf nodes are implicit from their height in the tree */
54 RCU_JA_NR_TYPES,
55
56 RCU_JA_NULL, /* not an encoded type, but keeps code regular */
57 };
58
59 struct cds_ja_type {
60 enum cds_ja_type_class type_class;
61 uint16_t min_child; /* minimum number of children: 1 to 256 */
62 uint16_t max_child; /* maximum number of children: 1 to 256 */
63 uint16_t max_linear_child; /* per-pool max nr. children: 1 to 256 */
64 uint16_t order; /* node size is (1 << order), in bytes */
65 uint16_t nr_pool_order; /* number of pools */
66 uint16_t pool_size_order; /* pool size */
67 };
68
69 /*
70 * Iteration on the array to find the right node size for the number of
71 * children stops when it reaches .max_child == 256 (this is the largest
72 * possible node size, which contains 256 children).
73 * The min_child overlaps with the previous max_child to provide an
74 * hysteresis loop to reallocation for patterns of cyclic add/removal
75 * within the same node.
76 * The node the index within the following arrays is represented on 3
77 * bits. It identifies the node type, min/max number of children, and
78 * the size order.
79 * The max_child values for the RCU_JA_POOL below result from
80 * statistical approximation: over million populations, the max_child
81 * covers between 97% and 99% of the populations generated. Therefore, a
82 * fallback should exist to cover the rare extreme population unbalance
83 * cases, but it will not have a major impact on speed nor space
84 * consumption, since those are rare cases.
85 */
86
87 #if (CAA_BITS_PER_LONG < 64)
88 /* 32-bit pointers */
89 enum {
90 ja_type_0_max_child = 1,
91 ja_type_1_max_child = 3,
92 ja_type_2_max_child = 6,
93 ja_type_3_max_child = 12,
94 ja_type_4_max_child = 25,
95 ja_type_5_max_child = 48,
96 ja_type_6_max_child = 92,
97 ja_type_7_max_child = 256,
98 ja_type_8_max_child = 0, /* NULL */
99 };
100
101 enum {
102 ja_type_0_max_linear_child = 1,
103 ja_type_1_max_linear_child = 3,
104 ja_type_2_max_linear_child = 6,
105 ja_type_3_max_linear_child = 12,
106 ja_type_4_max_linear_child = 25,
107 ja_type_5_max_linear_child = 24,
108 ja_type_6_max_linear_child = 23,
109 };
110
111 enum {
112 ja_type_5_nr_pool_order = 1,
113 ja_type_6_nr_pool_order = 2,
114 };
115
116 const struct cds_ja_type ja_types[] = {
117 { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_0_max_child, .max_linear_child = ja_type_0_max_linear_child, .order = 3, },
118 { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_1_max_child, .max_linear_child = ja_type_1_max_linear_child, .order = 4, },
119 { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = ja_type_2_max_child, .max_linear_child = ja_type_2_max_linear_child, .order = 5, },
120 { .type_class = RCU_JA_LINEAR, .min_child = 4, .max_child = ja_type_3_max_child, .max_linear_child = ja_type_3_max_linear_child, .order = 6, },
121 { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = ja_type_4_max_child, .max_linear_child = ja_type_4_max_linear_child, .order = 7, },
122
123 /* Pools may fill sooner than max_child */
124 { .type_class = RCU_JA_POOL, .min_child = 20, .max_child = ja_type_5_max_child, .max_linear_child = ja_type_5_max_linear_child, .order = 8, .nr_pool_order = ja_type_5_nr_pool_order, .pool_size_order = 7, },
125 { .type_class = RCU_JA_POOL, .min_child = 45, .max_child = ja_type_6_max_child, .max_linear_child = ja_type_6_max_linear_child, .order = 9, .nr_pool_order = ja_type_6_nr_pool_order, .pool_size_order = 7, },
126
127 /*
128 * Upon node removal below min_child, if child pool is filled
129 * beyond capacity, we roll back to pigeon.
130 */
131 { .type_class = RCU_JA_PIGEON, .min_child = 83, .max_child = ja_type_7_max_child, .order = 10, },
132
133 { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, },
134 };
135 #else /* !(CAA_BITS_PER_LONG < 64) */
136 /* 64-bit pointers */
137 enum {
138 ja_type_0_max_child = 1,
139 ja_type_1_max_child = 3,
140 ja_type_2_max_child = 7,
141 ja_type_3_max_child = 14,
142 ja_type_4_max_child = 28,
143 ja_type_5_max_child = 54,
144 ja_type_6_max_child = 104,
145 ja_type_7_max_child = 256,
146 ja_type_8_max_child = 256,
147 };
148
149 enum {
150 ja_type_0_max_linear_child = 1,
151 ja_type_1_max_linear_child = 3,
152 ja_type_2_max_linear_child = 7,
153 ja_type_3_max_linear_child = 14,
154 ja_type_4_max_linear_child = 28,
155 ja_type_5_max_linear_child = 27,
156 ja_type_6_max_linear_child = 26,
157 };
158
159 enum {
160 ja_type_5_nr_pool_order = 1,
161 ja_type_6_nr_pool_order = 2,
162 };
163
164 const struct cds_ja_type ja_types[] = {
165 { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_0_max_child, .max_linear_child = ja_type_0_max_linear_child, .order = 4, },
166 { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_1_max_child, .max_linear_child = ja_type_1_max_linear_child, .order = 5, },
167 { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = ja_type_2_max_child, .max_linear_child = ja_type_2_max_linear_child, .order = 6, },
168 { .type_class = RCU_JA_LINEAR, .min_child = 5, .max_child = ja_type_3_max_child, .max_linear_child = ja_type_3_max_linear_child, .order = 7, },
169 { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = ja_type_4_max_child, .max_linear_child = ja_type_4_max_linear_child, .order = 8, },
170
171 /* Pools may fill sooner than max_child. */
172 { .type_class = RCU_JA_POOL, .min_child = 22, .max_child = ja_type_5_max_child, .max_linear_child = ja_type_5_max_linear_child, .order = 9, .nr_pool_order = ja_type_5_nr_pool_order, .pool_size_order = 8, },
173 { .type_class = RCU_JA_POOL, .min_child = 51, .max_child = ja_type_6_max_child, .max_linear_child = ja_type_6_max_linear_child, .order = 10, .nr_pool_order = ja_type_6_nr_pool_order, .pool_size_order = 8, },
174
175 /*
176 * Upon node removal below min_child, if child pool is filled
177 * beyond capacity, we roll back to pigeon.
178 */
179 { .type_class = RCU_JA_PIGEON, .min_child = 95, .max_child = ja_type_7_max_child, .order = 11, },
180
181 { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, },
182 };
183 #endif /* !(BITS_PER_LONG < 64) */
184
185 static inline __attribute__((unused))
186 void static_array_size_check(void)
187 {
188 CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) < JA_TYPE_MAX_NR);
189 }
190
191 /*
192 * The cds_ja_node contains the compressed node data needed for
193 * read-side. For linear and pool node configurations, it starts with a
194 * byte counting the number of children in the node. Then, the
195 * node-specific data is placed.
196 * The node mutex, if any is needed, protecting concurrent updated of
197 * each node is placed in a separate hash table indexed by node address.
198 * For the pigeon configuration, the number of children is also kept in
199 * a separate hash table, indexed by node address, because it is only
200 * required for updates.
201 */
202
203 #define DECLARE_LINEAR_NODE(index) \
204 struct { \
205 uint8_t nr_child; \
206 uint8_t child_value[ja_type_## index ##_max_linear_child]; \
207 struct cds_ja_inode_flag *child_ptr[ja_type_## index ##_max_linear_child]; \
208 }
209
210 #define DECLARE_POOL_NODE(index) \
211 struct { \
212 struct { \
213 uint8_t nr_child; \
214 uint8_t child_value[ja_type_## index ##_max_linear_child]; \
215 struct cds_ja_inode_flag *child_ptr[ja_type_## index ##_max_linear_child]; \
216 } linear[1U << ja_type_## index ##_nr_pool_order]; \
217 }
218
219 struct cds_ja_inode {
220 union {
221 /* Linear configuration */
222 DECLARE_LINEAR_NODE(0) conf_0;
223 DECLARE_LINEAR_NODE(1) conf_1;
224 DECLARE_LINEAR_NODE(2) conf_2;
225 DECLARE_LINEAR_NODE(3) conf_3;
226 DECLARE_LINEAR_NODE(4) conf_4;
227
228 /* Pool configuration */
229 DECLARE_POOL_NODE(5) conf_5;
230 DECLARE_POOL_NODE(6) conf_6;
231
232 /* Pigeon configuration */
233 struct {
234 struct cds_ja_inode_flag *child[ja_type_7_max_child];
235 } conf_7;
236 /* data aliasing nodes for computed accesses */
237 uint8_t data[sizeof(struct cds_ja_inode_flag *) * ja_type_7_max_child];
238 } u;
239 };
240
241 enum ja_recompact {
242 JA_RECOMPACT_ADD_SAME,
243 JA_RECOMPACT_ADD_NEXT,
244 JA_RECOMPACT_DEL,
245 };
246
247 static
248 struct cds_ja_inode *_ja_node_mask_ptr(struct cds_ja_inode_flag *node)
249 {
250 return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK);
251 }
252
253 unsigned long ja_node_type(struct cds_ja_inode_flag *node)
254 {
255 unsigned long type;
256
257 if (_ja_node_mask_ptr(node) == NULL) {
258 return NODE_INDEX_NULL;
259 }
260 type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
261 assert(type < (1UL << JA_TYPE_BITS));
262 return type;
263 }
264
265 struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node)
266 {
267 unsigned long type_index = ja_node_type(node);
268 const struct cds_ja_type *type;
269
270 type = &ja_types[type_index];
271 switch (type->type_class) {
272 case RCU_JA_LINEAR:
273 case RCU_JA_PIGEON: /* fall-through */
274 case RCU_JA_NULL: /* fall-through */
275 default: /* fall-through */
276 return _ja_node_mask_ptr(node);
277 case RCU_JA_POOL:
278 switch (type->nr_pool_order) {
279 case 1:
280 return (struct cds_ja_inode *) (((unsigned long) node) & ~(JA_POOL_1D_MASK | JA_TYPE_MASK));
281 case 2:
282 return (struct cds_ja_inode *) (((unsigned long) node) & ~(JA_POOL_2D_MASK | JA_POOL_1D_MASK | JA_TYPE_MASK));
283 default:
284 assert(0);
285 }
286 }
287 }
288
289 static
290 struct cds_ja_inode *alloc_cds_ja_node(struct cds_ja *ja,
291 const struct cds_ja_type *ja_type)
292 {
293 size_t len = 1U << ja_type->order;
294 void *p;
295 int ret;
296
297 ret = posix_memalign(&p, len, len);
298 if (ret || !p) {
299 return NULL;
300 }
301 memset(p, 0, len);
302 uatomic_inc(&ja->nr_nodes_allocated);
303 return p;
304 }
305
306 void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node)
307 {
308 free(node);
309 if (node)
310 uatomic_inc(&ja->nr_nodes_freed);
311 }
312
313 #define __JA_ALIGN_MASK(v, mask) (((v) + (mask)) & ~(mask))
314 #define JA_ALIGN(v, align) __JA_ALIGN_MASK(v, (typeof(v)) (align) - 1)
315 #define __JA_FLOOR_MASK(v, mask) ((v) & ~(mask))
316 #define JA_FLOOR(v, align) __JA_FLOOR_MASK(v, (typeof(v)) (align) - 1)
317
318 static
319 uint8_t *align_ptr_size(uint8_t *ptr)
320 {
321 return (uint8_t *) JA_ALIGN((unsigned long) ptr, sizeof(void *));
322 }
323
324 static
325 uint8_t ja_linear_node_get_nr_child(const struct cds_ja_type *type,
326 struct cds_ja_inode *node)
327 {
328 assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
329 return rcu_dereference(node->u.data[0]);
330 }
331
332 /*
333 * The order in which values and pointers are does does not matter: if
334 * a value is missing, we return NULL. If a value is there, but its
335 * associated pointers is still NULL, we return NULL too.
336 */
337 static
338 struct cds_ja_inode_flag *ja_linear_node_get_nth(const struct cds_ja_type *type,
339 struct cds_ja_inode *node,
340 struct cds_ja_inode_flag ***node_flag_ptr,
341 uint8_t n)
342 {
343 uint8_t nr_child;
344 uint8_t *values;
345 struct cds_ja_inode_flag **pointers;
346 struct cds_ja_inode_flag *ptr;
347 unsigned int i;
348
349 assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
350
351 nr_child = ja_linear_node_get_nr_child(type, node);
352 cmm_smp_rmb(); /* read nr_child before values and pointers */
353 assert(nr_child <= type->max_linear_child);
354 assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
355
356 values = &node->u.data[1];
357 for (i = 0; i < nr_child; i++) {
358 if (CMM_LOAD_SHARED(values[i]) == n)
359 break;
360 }
361 if (i >= nr_child) {
362 if (caa_unlikely(node_flag_ptr))
363 *node_flag_ptr = NULL;
364 return NULL;
365 }
366 pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
367 ptr = rcu_dereference(pointers[i]);
368 if (caa_unlikely(node_flag_ptr))
369 *node_flag_ptr = &pointers[i];
370 return ptr;
371 }
372
373 static
374 struct cds_ja_inode_flag *ja_linear_node_get_left(const struct cds_ja_type *type,
375 struct cds_ja_inode *node,
376 unsigned int n)
377 {
378 uint8_t nr_child;
379 uint8_t *values;
380 struct cds_ja_inode_flag **pointers;
381 struct cds_ja_inode_flag *ptr;
382 unsigned int i, match_idx;
383 int match_v = -1;
384
385 assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
386
387 nr_child = ja_linear_node_get_nr_child(type, node);
388 cmm_smp_rmb(); /* read nr_child before values and pointers */
389 assert(nr_child <= type->max_linear_child);
390 assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
391
392 values = &node->u.data[1];
393 for (i = 0; i < nr_child; i++) {
394 unsigned int v;
395
396 v = CMM_LOAD_SHARED(values[i]);
397 if (v < n && (int) v > match_v) {
398 match_v = v;
399 match_idx = i;
400 }
401 }
402 if (match_v < 0) {
403 return NULL;
404 }
405 pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
406 ptr = rcu_dereference(pointers[match_idx]);
407 return ptr;
408 }
409
410 static
411 void ja_linear_node_get_ith_pos(const struct cds_ja_type *type,
412 struct cds_ja_inode *node,
413 uint8_t i,
414 uint8_t *v,
415 struct cds_ja_inode_flag **iter)
416 {
417 uint8_t *values;
418 struct cds_ja_inode_flag **pointers;
419
420 assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
421 assert(i < ja_linear_node_get_nr_child(type, node));
422
423 values = &node->u.data[1];
424 *v = values[i];
425 pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
426 *iter = pointers[i];
427 }
428
429 static
430 struct cds_ja_inode_flag *ja_pool_node_get_nth(const struct cds_ja_type *type,
431 struct cds_ja_inode *node,
432 struct cds_ja_inode_flag *node_flag,
433 struct cds_ja_inode_flag ***node_flag_ptr,
434 uint8_t n)
435 {
436 struct cds_ja_inode *linear;
437
438 assert(type->type_class == RCU_JA_POOL);
439
440 switch (type->nr_pool_order) {
441 case 1:
442 {
443 unsigned long bitsel, index;
444
445 bitsel = ja_node_pool_1d_bitsel(node_flag);
446 assert(bitsel < CHAR_BIT);
447 index = ((unsigned long) n >> bitsel) & 0x1;
448 linear = (struct cds_ja_inode *) &node->u.data[index << type->pool_size_order];
449 break;
450 }
451 case 2:
452 {
453 unsigned long bitsel[2], index[2], rindex;
454
455 ja_node_pool_2d_bitsel(node_flag, bitsel);
456 assert(bitsel[0] < CHAR_BIT);
457 assert(bitsel[1] < CHAR_BIT);
458 index[0] = ((unsigned long) n >> bitsel[0]) & 0x1;
459 index[0] <<= 1;
460 index[1] = ((unsigned long) n >> bitsel[1]) & 0x1;
461 rindex = index[0] | index[1];
462 linear = (struct cds_ja_inode *) &node->u.data[rindex << type->pool_size_order];
463 break;
464 }
465 default:
466 linear = NULL;
467 assert(0);
468 }
469 return ja_linear_node_get_nth(type, linear, node_flag_ptr, n);
470 }
471
472 static
473 struct cds_ja_inode *ja_pool_node_get_ith_pool(const struct cds_ja_type *type,
474 struct cds_ja_inode *node,
475 uint8_t i)
476 {
477 assert(type->type_class == RCU_JA_POOL);
478 return (struct cds_ja_inode *)
479 &node->u.data[(unsigned int) i << type->pool_size_order];
480 }
481
482 static
483 struct cds_ja_inode_flag *ja_pool_node_get_left(const struct cds_ja_type *type,
484 struct cds_ja_inode *node,
485 unsigned int n)
486 {
487 unsigned int pool_nr;
488 int match_v = -1;
489 struct cds_ja_inode_flag *match_node_flag = NULL;
490
491 assert(type->type_class == RCU_JA_POOL);
492
493 for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
494 struct cds_ja_inode *pool =
495 ja_pool_node_get_ith_pool(type,
496 node, pool_nr);
497 uint8_t nr_child =
498 ja_linear_node_get_nr_child(type, pool);
499 unsigned int j;
500
501 for (j = 0; j < nr_child; j++) {
502 struct cds_ja_inode_flag *iter;
503 uint8_t v;
504
505 ja_linear_node_get_ith_pos(type, pool,
506 j, &v, &iter);
507 if (!iter)
508 continue;
509 if (v < n && (int) v > match_v) {
510 match_v = v;
511 match_node_flag = iter;
512 }
513 }
514 }
515 return match_node_flag;
516 }
517
518 static
519 struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type,
520 struct cds_ja_inode *node,
521 struct cds_ja_inode_flag ***node_flag_ptr,
522 uint8_t n)
523 {
524 struct cds_ja_inode_flag **child_node_flag_ptr;
525 struct cds_ja_inode_flag *child_node_flag;
526
527 assert(type->type_class == RCU_JA_PIGEON);
528 child_node_flag_ptr = &((struct cds_ja_inode_flag **) node->u.data)[n];
529 child_node_flag = rcu_dereference(*child_node_flag_ptr);
530 dbg_printf("ja_pigeon_node_get_nth child_node_flag_ptr %p\n",
531 child_node_flag_ptr);
532 if (caa_unlikely(node_flag_ptr))
533 *node_flag_ptr = child_node_flag_ptr;
534 return child_node_flag;
535 }
536
537 static
538 struct cds_ja_inode_flag *ja_pigeon_node_get_left(const struct cds_ja_type *type,
539 struct cds_ja_inode *node,
540 unsigned int n)
541 {
542 struct cds_ja_inode_flag **child_node_flag_ptr;
543 struct cds_ja_inode_flag *child_node_flag;
544 int i;
545
546 assert(type->type_class == RCU_JA_PIGEON);
547
548 /* n - 1 is first value left of n */
549 for (i = n - 1; i >= 0; i--) {
550 child_node_flag_ptr = &((struct cds_ja_inode_flag **) node->u.data)[i];
551 child_node_flag = rcu_dereference(*child_node_flag_ptr);
552 if (child_node_flag) {
553 dbg_printf("ja_pigeon_node_get_left child_node_flag %p\n",
554 child_node_flag);
555 return child_node_flag;
556 }
557 }
558 return NULL;
559 }
560
561 static
562 struct cds_ja_inode_flag *ja_pigeon_node_get_ith_pos(const struct cds_ja_type *type,
563 struct cds_ja_inode *node,
564 uint8_t i)
565 {
566 return ja_pigeon_node_get_nth(type, node, NULL, i);
567 }
568
569 /*
570 * ja_node_get_nth: get nth item from a node.
571 * node_flag is already rcu_dereference'd.
572 */
573 static
574 struct cds_ja_inode_flag *ja_node_get_nth(struct cds_ja_inode_flag *node_flag,
575 struct cds_ja_inode_flag ***node_flag_ptr,
576 uint8_t n)
577 {
578 unsigned int type_index;
579 struct cds_ja_inode *node;
580 const struct cds_ja_type *type;
581
582 node = ja_node_ptr(node_flag);
583 assert(node != NULL);
584 type_index = ja_node_type(node_flag);
585 type = &ja_types[type_index];
586
587 switch (type->type_class) {
588 case RCU_JA_LINEAR:
589 return ja_linear_node_get_nth(type, node,
590 node_flag_ptr, n);
591 case RCU_JA_POOL:
592 return ja_pool_node_get_nth(type, node, node_flag,
593 node_flag_ptr, n);
594 case RCU_JA_PIGEON:
595 return ja_pigeon_node_get_nth(type, node,
596 node_flag_ptr, n);
597 default:
598 assert(0);
599 return (void *) -1UL;
600 }
601 }
602
603 static
604 struct cds_ja_inode_flag *ja_node_get_left(struct cds_ja_inode_flag *node_flag,
605 unsigned int n)
606 {
607 unsigned int type_index;
608 struct cds_ja_inode *node;
609 const struct cds_ja_type *type;
610
611 node = ja_node_ptr(node_flag);
612 assert(node != NULL);
613 type_index = ja_node_type(node_flag);
614 type = &ja_types[type_index];
615
616 switch (type->type_class) {
617 case RCU_JA_LINEAR:
618 return ja_linear_node_get_left(type, node, n);
619 case RCU_JA_POOL:
620 return ja_pool_node_get_left(type, node, n);
621 case RCU_JA_PIGEON:
622 return ja_pigeon_node_get_left(type, node, n);
623 default:
624 assert(0);
625 return (void *) -1UL;
626 }
627 }
628
629 static
630 struct cds_ja_inode_flag *ja_node_get_rightmost(struct cds_ja_inode_flag *node_flag)
631 {
632 return ja_node_get_left(node_flag, JA_ENTRY_PER_NODE);
633 }
634
635 static
636 int ja_linear_node_set_nth(const struct cds_ja_type *type,
637 struct cds_ja_inode *node,
638 struct cds_ja_shadow_node *shadow_node,
639 uint8_t n,
640 struct cds_ja_inode_flag *child_node_flag)
641 {
642 uint8_t nr_child;
643 uint8_t *values, *nr_child_ptr;
644 struct cds_ja_inode_flag **pointers;
645 unsigned int i, unused = 0;
646
647 assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
648
649 nr_child_ptr = &node->u.data[0];
650 dbg_printf("linear set nth: n %u, nr_child_ptr %p\n",
651 (unsigned int) n, nr_child_ptr);
652 nr_child = *nr_child_ptr;
653 assert(nr_child <= type->max_linear_child);
654
655 values = &node->u.data[1];
656 pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
657 /* Check if node value is already populated */
658 for (i = 0; i < nr_child; i++) {
659 if (values[i] == n) {
660 if (pointers[i])
661 return -EEXIST;
662 else
663 break;
664 } else {
665 if (!pointers[i])
666 unused++;
667 }
668 }
669 if (i == nr_child && nr_child >= type->max_linear_child) {
670 if (unused)
671 return -ERANGE; /* recompact node */
672 else
673 return -ENOSPC; /* No space left in this node type */
674 }
675
676 assert(pointers[i] == NULL);
677 rcu_assign_pointer(pointers[i], child_node_flag);
678 /* If we expanded the nr_child, increment it */
679 if (i == nr_child) {
680 CMM_STORE_SHARED(values[nr_child], n);
681 /* write pointer and value before nr_child */
682 cmm_smp_wmb();
683 CMM_STORE_SHARED(*nr_child_ptr, nr_child + 1);
684 }
685 shadow_node->nr_child++;
686 dbg_printf("linear set nth: %u child, shadow: %u child, for node %p shadow %p\n",
687 (unsigned int) CMM_LOAD_SHARED(*nr_child_ptr),
688 (unsigned int) shadow_node->nr_child,
689 node, shadow_node);
690
691 return 0;
692 }
693
694 static
695 int ja_pool_node_set_nth(const struct cds_ja_type *type,
696 struct cds_ja_inode *node,
697 struct cds_ja_inode_flag *node_flag,
698 struct cds_ja_shadow_node *shadow_node,
699 uint8_t n,
700 struct cds_ja_inode_flag *child_node_flag)
701 {
702 struct cds_ja_inode *linear;
703
704 assert(type->type_class == RCU_JA_POOL);
705
706 switch (type->nr_pool_order) {
707 case 1:
708 {
709 unsigned long bitsel, index;
710
711 bitsel = ja_node_pool_1d_bitsel(node_flag);
712 assert(bitsel < CHAR_BIT);
713 index = ((unsigned long) n >> bitsel) & 0x1;
714 linear = (struct cds_ja_inode *) &node->u.data[index << type->pool_size_order];
715 break;
716 }
717 case 2:
718 {
719 unsigned long bitsel[2], index[2], rindex;
720
721 ja_node_pool_2d_bitsel(node_flag, bitsel);
722 assert(bitsel[0] < CHAR_BIT);
723 assert(bitsel[1] < CHAR_BIT);
724 index[0] = ((unsigned long) n >> bitsel[0]) & 0x1;
725 index[0] <<= 1;
726 index[1] = ((unsigned long) n >> bitsel[1]) & 0x1;
727 rindex = index[0] | index[1];
728 linear = (struct cds_ja_inode *) &node->u.data[rindex << type->pool_size_order];
729 break;
730 }
731 default:
732 linear = NULL;
733 assert(0);
734 }
735
736 return ja_linear_node_set_nth(type, linear, shadow_node,
737 n, child_node_flag);
738 }
739
740 static
741 int ja_pigeon_node_set_nth(const struct cds_ja_type *type,
742 struct cds_ja_inode *node,
743 struct cds_ja_shadow_node *shadow_node,
744 uint8_t n,
745 struct cds_ja_inode_flag *child_node_flag)
746 {
747 struct cds_ja_inode_flag **ptr;
748
749 assert(type->type_class == RCU_JA_PIGEON);
750 ptr = &((struct cds_ja_inode_flag **) node->u.data)[n];
751 if (*ptr)
752 return -EEXIST;
753 rcu_assign_pointer(*ptr, child_node_flag);
754 shadow_node->nr_child++;
755 return 0;
756 }
757
758 /*
759 * _ja_node_set_nth: set nth item within a node. Return an error
760 * (negative error value) if it is already there.
761 */
762 static
763 int _ja_node_set_nth(const struct cds_ja_type *type,
764 struct cds_ja_inode *node,
765 struct cds_ja_inode_flag *node_flag,
766 struct cds_ja_shadow_node *shadow_node,
767 uint8_t n,
768 struct cds_ja_inode_flag *child_node_flag)
769 {
770 switch (type->type_class) {
771 case RCU_JA_LINEAR:
772 return ja_linear_node_set_nth(type, node, shadow_node, n,
773 child_node_flag);
774 case RCU_JA_POOL:
775 return ja_pool_node_set_nth(type, node, node_flag, shadow_node, n,
776 child_node_flag);
777 case RCU_JA_PIGEON:
778 return ja_pigeon_node_set_nth(type, node, shadow_node, n,
779 child_node_flag);
780 case RCU_JA_NULL:
781 return -ENOSPC;
782 default:
783 assert(0);
784 return -EINVAL;
785 }
786
787 return 0;
788 }
789
790 static
791 int ja_linear_node_clear_ptr(const struct cds_ja_type *type,
792 struct cds_ja_inode *node,
793 struct cds_ja_shadow_node *shadow_node,
794 struct cds_ja_inode_flag **node_flag_ptr)
795 {
796 uint8_t nr_child;
797 uint8_t *nr_child_ptr;
798
799 assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
800
801 nr_child_ptr = &node->u.data[0];
802 nr_child = *nr_child_ptr;
803 assert(nr_child <= type->max_linear_child);
804
805 if (type->type_class == RCU_JA_LINEAR) {
806 assert(!shadow_node->fallback_removal_count);
807 if (shadow_node->nr_child <= type->min_child) {
808 /* We need to try recompacting the node */
809 return -EFBIG;
810 }
811 }
812 dbg_printf("linear clear ptr: nr_child_ptr %p\n", nr_child_ptr);
813 assert(*node_flag_ptr != NULL);
814 rcu_assign_pointer(*node_flag_ptr, NULL);
815 /*
816 * Value and nr_child are never changed (would cause ABA issue).
817 * Instead, we leave the pointer to NULL and recompact the node
818 * once in a while. It is allowed to set a NULL pointer to a new
819 * value without recompaction though.
820 * Only update the shadow node accounting.
821 */
822 shadow_node->nr_child--;
823 dbg_printf("linear clear ptr: %u child, shadow: %u child, for node %p shadow %p\n",
824 (unsigned int) CMM_LOAD_SHARED(*nr_child_ptr),
825 (unsigned int) shadow_node->nr_child,
826 node, shadow_node);
827 return 0;
828 }
829
830 static
831 int ja_pool_node_clear_ptr(const struct cds_ja_type *type,
832 struct cds_ja_inode *node,
833 struct cds_ja_inode_flag *node_flag,
834 struct cds_ja_shadow_node *shadow_node,
835 struct cds_ja_inode_flag **node_flag_ptr,
836 uint8_t n)
837 {
838 struct cds_ja_inode *linear;
839
840 assert(type->type_class == RCU_JA_POOL);
841
842 if (shadow_node->fallback_removal_count) {
843 shadow_node->fallback_removal_count--;
844 } else {
845 /* We should try recompacting the node */
846 if (shadow_node->nr_child <= type->min_child)
847 return -EFBIG;
848 }
849
850 switch (type->nr_pool_order) {
851 case 1:
852 {
853 unsigned long bitsel, index;
854
855 bitsel = ja_node_pool_1d_bitsel(node_flag);
856 assert(bitsel < CHAR_BIT);
857 index = ((unsigned long) n >> bitsel) & type->nr_pool_order;
858 linear = (struct cds_ja_inode *) &node->u.data[index << type->pool_size_order];
859 break;
860 }
861 case 2:
862 {
863 unsigned long bitsel[2], index[2], rindex;
864
865 ja_node_pool_2d_bitsel(node_flag, bitsel);
866 assert(bitsel[0] < CHAR_BIT);
867 assert(bitsel[1] < CHAR_BIT);
868 index[0] = ((unsigned long) n >> bitsel[0]) & 0x1;
869 index[0] <<= 1;
870 index[1] = ((unsigned long) n >> bitsel[1]) & 0x1;
871 rindex = index[0] | index[1];
872 linear = (struct cds_ja_inode *) &node->u.data[rindex << type->pool_size_order];
873 break;
874 }
875 default:
876 linear = NULL;
877 assert(0);
878 }
879
880 return ja_linear_node_clear_ptr(type, linear, shadow_node, node_flag_ptr);
881 }
882
883 static
884 int ja_pigeon_node_clear_ptr(const struct cds_ja_type *type,
885 struct cds_ja_inode *node,
886 struct cds_ja_shadow_node *shadow_node,
887 struct cds_ja_inode_flag **node_flag_ptr)
888 {
889 assert(type->type_class == RCU_JA_PIGEON);
890
891 if (shadow_node->fallback_removal_count) {
892 shadow_node->fallback_removal_count--;
893 } else {
894 /* We should try recompacting the node */
895 if (shadow_node->nr_child <= type->min_child)
896 return -EFBIG;
897 }
898 dbg_printf("ja_pigeon_node_clear_ptr: clearing ptr: %p\n", *node_flag_ptr);
899 rcu_assign_pointer(*node_flag_ptr, NULL);
900 shadow_node->nr_child--;
901 return 0;
902 }
903
904 /*
905 * _ja_node_clear_ptr: clear ptr item within a node. Return an error
906 * (negative error value) if it is not found (-ENOENT).
907 */
908 static
909 int _ja_node_clear_ptr(const struct cds_ja_type *type,
910 struct cds_ja_inode *node,
911 struct cds_ja_inode_flag *node_flag,
912 struct cds_ja_shadow_node *shadow_node,
913 struct cds_ja_inode_flag **node_flag_ptr,
914 uint8_t n)
915 {
916 switch (type->type_class) {
917 case RCU_JA_LINEAR:
918 return ja_linear_node_clear_ptr(type, node, shadow_node, node_flag_ptr);
919 case RCU_JA_POOL:
920 return ja_pool_node_clear_ptr(type, node, node_flag, shadow_node, node_flag_ptr, n);
921 case RCU_JA_PIGEON:
922 return ja_pigeon_node_clear_ptr(type, node, shadow_node, node_flag_ptr);
923 case RCU_JA_NULL:
924 return -ENOENT;
925 default:
926 assert(0);
927 return -EINVAL;
928 }
929
930 return 0;
931 }
932
933 /*
934 * Calculate bit distribution. Returns the bit (0 to 7) that splits the
935 * distribution in two sub-distributions containing as much elements one
936 * compared to the other.
937 */
938 static
939 unsigned int ja_node_sum_distribution_1d(enum ja_recompact mode,
940 struct cds_ja *ja,
941 unsigned int type_index,
942 const struct cds_ja_type *type,
943 struct cds_ja_inode *node,
944 struct cds_ja_shadow_node *shadow_node,
945 uint8_t n,
946 struct cds_ja_inode_flag *child_node_flag,
947 struct cds_ja_inode_flag **nullify_node_flag_ptr)
948 {
949 uint8_t nr_one[JA_BITS_PER_BYTE];
950 unsigned int bitsel = 0, bit_i, overall_best_distance = UINT_MAX;
951 unsigned int distrib_nr_child = 0;
952
953 memset(nr_one, 0, sizeof(nr_one));
954
955 switch (type->type_class) {
956 case RCU_JA_LINEAR:
957 {
958 uint8_t nr_child =
959 ja_linear_node_get_nr_child(type, node);
960 unsigned int i;
961
962 for (i = 0; i < nr_child; i++) {
963 struct cds_ja_inode_flag *iter;
964 uint8_t v;
965
966 ja_linear_node_get_ith_pos(type, node, i, &v, &iter);
967 if (!iter)
968 continue;
969 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
970 continue;
971 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
972 if (v & (1U << bit_i))
973 nr_one[bit_i]++;
974 }
975 distrib_nr_child++;
976 }
977 break;
978 }
979 case RCU_JA_POOL:
980 {
981 unsigned int pool_nr;
982
983 for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
984 struct cds_ja_inode *pool =
985 ja_pool_node_get_ith_pool(type,
986 node, pool_nr);
987 uint8_t nr_child =
988 ja_linear_node_get_nr_child(type, pool);
989 unsigned int j;
990
991 for (j = 0; j < nr_child; j++) {
992 struct cds_ja_inode_flag *iter;
993 uint8_t v;
994
995 ja_linear_node_get_ith_pos(type, pool,
996 j, &v, &iter);
997 if (!iter)
998 continue;
999 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1000 continue;
1001 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1002 if (v & (1U << bit_i))
1003 nr_one[bit_i]++;
1004 }
1005 distrib_nr_child++;
1006 }
1007 }
1008 break;
1009 }
1010 case RCU_JA_PIGEON:
1011 {
1012 unsigned int i;
1013
1014 assert(mode == JA_RECOMPACT_DEL);
1015 for (i = 0; i < JA_ENTRY_PER_NODE; i++) {
1016 struct cds_ja_inode_flag *iter;
1017
1018 iter = ja_pigeon_node_get_ith_pos(type, node, i);
1019 if (!iter)
1020 continue;
1021 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1022 continue;
1023 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1024 if (i & (1U << bit_i))
1025 nr_one[bit_i]++;
1026 }
1027 distrib_nr_child++;
1028 }
1029 break;
1030 }
1031 case RCU_JA_NULL:
1032 assert(mode == JA_RECOMPACT_ADD_NEXT);
1033 break;
1034 default:
1035 assert(0);
1036 break;
1037 }
1038
1039 if (mode == JA_RECOMPACT_ADD_NEXT || mode == JA_RECOMPACT_ADD_SAME) {
1040 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1041 if (n & (1U << bit_i))
1042 nr_one[bit_i]++;
1043 }
1044 distrib_nr_child++;
1045 }
1046
1047 /*
1048 * The best bit selector is that for which the number of ones is
1049 * closest to half of the number of children in the
1050 * distribution. We calculate the distance using the double of
1051 * the sub-distribution sizes to eliminate truncation error.
1052 */
1053 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1054 unsigned int distance_to_best;
1055
1056 distance_to_best = abs_int((nr_one[bit_i] << 1U) - distrib_nr_child);
1057 if (distance_to_best < overall_best_distance) {
1058 overall_best_distance = distance_to_best;
1059 bitsel = bit_i;
1060 }
1061 }
1062 dbg_printf("1 dimension pool bit selection: (%u)\n", bitsel);
1063 return bitsel;
1064 }
1065
1066 /*
1067 * Calculate bit distribution in two dimensions. Returns the two bits
1068 * (each 0 to 7) that splits the distribution in four sub-distributions
1069 * containing as much elements one compared to the other.
1070 */
1071 static
1072 void ja_node_sum_distribution_2d(enum ja_recompact mode,
1073 struct cds_ja *ja,
1074 unsigned int type_index,
1075 const struct cds_ja_type *type,
1076 struct cds_ja_inode *node,
1077 struct cds_ja_shadow_node *shadow_node,
1078 uint8_t n,
1079 struct cds_ja_inode_flag *child_node_flag,
1080 struct cds_ja_inode_flag **nullify_node_flag_ptr,
1081 unsigned int *_bitsel)
1082 {
1083 uint8_t nr_2d_11[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE],
1084 nr_2d_10[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE],
1085 nr_2d_01[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE],
1086 nr_2d_00[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE];
1087 unsigned int bitsel[2] = { 0, 1 };
1088 unsigned int bit_i, bit_j;
1089 int overall_best_distance = INT_MAX;
1090 unsigned int distrib_nr_child = 0;
1091
1092 memset(nr_2d_11, 0, sizeof(nr_2d_11));
1093 memset(nr_2d_10, 0, sizeof(nr_2d_10));
1094 memset(nr_2d_01, 0, sizeof(nr_2d_01));
1095 memset(nr_2d_00, 0, sizeof(nr_2d_00));
1096
1097 switch (type->type_class) {
1098 case RCU_JA_LINEAR:
1099 {
1100 uint8_t nr_child =
1101 ja_linear_node_get_nr_child(type, node);
1102 unsigned int i;
1103
1104 for (i = 0; i < nr_child; i++) {
1105 struct cds_ja_inode_flag *iter;
1106 uint8_t v;
1107
1108 ja_linear_node_get_ith_pos(type, node, i, &v, &iter);
1109 if (!iter)
1110 continue;
1111 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1112 continue;
1113 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1114 for (bit_j = 0; bit_j < bit_i; bit_j++) {
1115 if ((v & (1U << bit_i)) && (v & (1U << bit_j))) {
1116 nr_2d_11[bit_i][bit_j]++;
1117 }
1118 if ((v & (1U << bit_i)) && !(v & (1U << bit_j))) {
1119 nr_2d_10[bit_i][bit_j]++;
1120 }
1121 if (!(v & (1U << bit_i)) && (v & (1U << bit_j))) {
1122 nr_2d_01[bit_i][bit_j]++;
1123 }
1124 if (!(v & (1U << bit_i)) && !(v & (1U << bit_j))) {
1125 nr_2d_00[bit_i][bit_j]++;
1126 }
1127 }
1128 }
1129 distrib_nr_child++;
1130 }
1131 break;
1132 }
1133 case RCU_JA_POOL:
1134 {
1135 unsigned int pool_nr;
1136
1137 for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
1138 struct cds_ja_inode *pool =
1139 ja_pool_node_get_ith_pool(type,
1140 node, pool_nr);
1141 uint8_t nr_child =
1142 ja_linear_node_get_nr_child(type, pool);
1143 unsigned int j;
1144
1145 for (j = 0; j < nr_child; j++) {
1146 struct cds_ja_inode_flag *iter;
1147 uint8_t v;
1148
1149 ja_linear_node_get_ith_pos(type, pool,
1150 j, &v, &iter);
1151 if (!iter)
1152 continue;
1153 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1154 continue;
1155 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1156 for (bit_j = 0; bit_j < bit_i; bit_j++) {
1157 if ((v & (1U << bit_i)) && (v & (1U << bit_j))) {
1158 nr_2d_11[bit_i][bit_j]++;
1159 }
1160 if ((v & (1U << bit_i)) && !(v & (1U << bit_j))) {
1161 nr_2d_10[bit_i][bit_j]++;
1162 }
1163 if (!(v & (1U << bit_i)) && (v & (1U << bit_j))) {
1164 nr_2d_01[bit_i][bit_j]++;
1165 }
1166 if (!(v & (1U << bit_i)) && !(v & (1U << bit_j))) {
1167 nr_2d_00[bit_i][bit_j]++;
1168 }
1169 }
1170 }
1171 distrib_nr_child++;
1172 }
1173 }
1174 break;
1175 }
1176 case RCU_JA_PIGEON:
1177 {
1178 unsigned int i;
1179
1180 assert(mode == JA_RECOMPACT_DEL);
1181 for (i = 0; i < JA_ENTRY_PER_NODE; i++) {
1182 struct cds_ja_inode_flag *iter;
1183
1184 iter = ja_pigeon_node_get_ith_pos(type, node, i);
1185 if (!iter)
1186 continue;
1187 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1188 continue;
1189 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1190 for (bit_j = 0; bit_j < bit_i; bit_j++) {
1191 if ((i & (1U << bit_i)) && (i & (1U << bit_j))) {
1192 nr_2d_11[bit_i][bit_j]++;
1193 }
1194 if ((i & (1U << bit_i)) && !(i & (1U << bit_j))) {
1195 nr_2d_10[bit_i][bit_j]++;
1196 }
1197 if (!(i & (1U << bit_i)) && (i & (1U << bit_j))) {
1198 nr_2d_01[bit_i][bit_j]++;
1199 }
1200 if (!(i & (1U << bit_i)) && !(i & (1U << bit_j))) {
1201 nr_2d_00[bit_i][bit_j]++;
1202 }
1203 }
1204 }
1205 distrib_nr_child++;
1206 }
1207 break;
1208 }
1209 case RCU_JA_NULL:
1210 assert(mode == JA_RECOMPACT_ADD_NEXT);
1211 break;
1212 default:
1213 assert(0);
1214 break;
1215 }
1216
1217 if (mode == JA_RECOMPACT_ADD_NEXT || mode == JA_RECOMPACT_ADD_SAME) {
1218 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1219 for (bit_j = 0; bit_j < bit_i; bit_j++) {
1220 if ((n & (1U << bit_i)) && (n & (1U << bit_j))) {
1221 nr_2d_11[bit_i][bit_j]++;
1222 }
1223 if ((n & (1U << bit_i)) && !(n & (1U << bit_j))) {
1224 nr_2d_10[bit_i][bit_j]++;
1225 }
1226 if (!(n & (1U << bit_i)) && (n & (1U << bit_j))) {
1227 nr_2d_01[bit_i][bit_j]++;
1228 }
1229 if (!(n & (1U << bit_i)) && !(n & (1U << bit_j))) {
1230 nr_2d_00[bit_i][bit_j]++;
1231 }
1232 }
1233 }
1234 distrib_nr_child++;
1235 }
1236
1237 /*
1238 * The best bit selector is that for which the number of nodes
1239 * in each sub-class is closest to one-fourth of the number of
1240 * children in the distribution. We calculate the distance using
1241 * 4 times the size of the sub-distribution to eliminate
1242 * truncation error.
1243 */
1244 for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
1245 for (bit_j = 0; bit_j < bit_i; bit_j++) {
1246 int distance_to_best[4];
1247
1248 distance_to_best[0] = (nr_2d_11[bit_i][bit_j] << 2U) - distrib_nr_child;
1249 distance_to_best[1] = (nr_2d_10[bit_i][bit_j] << 2U) - distrib_nr_child;
1250 distance_to_best[2] = (nr_2d_01[bit_i][bit_j] << 2U) - distrib_nr_child;
1251 distance_to_best[3] = (nr_2d_00[bit_i][bit_j] << 2U) - distrib_nr_child;
1252
1253 /* Consider worse distance above best */
1254 if (distance_to_best[1] > 0 && distance_to_best[1] > distance_to_best[0])
1255 distance_to_best[0] = distance_to_best[1];
1256 if (distance_to_best[2] > 0 && distance_to_best[2] > distance_to_best[0])
1257 distance_to_best[0] = distance_to_best[2];
1258 if (distance_to_best[3] > 0 && distance_to_best[3] > distance_to_best[0])
1259 distance_to_best[0] = distance_to_best[3];
1260
1261 /*
1262 * If our worse distance is better than overall,
1263 * we become new best candidate.
1264 */
1265 if (distance_to_best[0] < overall_best_distance) {
1266 overall_best_distance = distance_to_best[0];
1267 bitsel[0] = bit_i;
1268 bitsel[1] = bit_j;
1269 }
1270 }
1271 }
1272
1273 dbg_printf("2 dimensions pool bit selection: (%u,%u)\n", bitsel[0], bitsel[1]);
1274
1275 /* Return our bit selection */
1276 _bitsel[0] = bitsel[0];
1277 _bitsel[1] = bitsel[1];
1278 }
1279
1280 static
1281 unsigned int find_nearest_type_index(unsigned int type_index,
1282 unsigned int nr_nodes)
1283 {
1284 const struct cds_ja_type *type;
1285
1286 assert(type_index != NODE_INDEX_NULL);
1287 if (nr_nodes == 0)
1288 return NODE_INDEX_NULL;
1289 for (;;) {
1290 type = &ja_types[type_index];
1291 if (nr_nodes < type->min_child)
1292 type_index--;
1293 else if (nr_nodes > type->max_child)
1294 type_index++;
1295 else
1296 break;
1297 }
1298 return type_index;
1299 }
1300
1301 /*
1302 * ja_node_recompact_add: recompact a node, adding a new child.
1303 * Return 0 on success, -EAGAIN if need to retry, or other negative
1304 * error value otherwise.
1305 */
1306 static
1307 int ja_node_recompact(enum ja_recompact mode,
1308 struct cds_ja *ja,
1309 unsigned int old_type_index,
1310 const struct cds_ja_type *old_type,
1311 struct cds_ja_inode *old_node,
1312 struct cds_ja_shadow_node *shadow_node,
1313 struct cds_ja_inode_flag **old_node_flag_ptr, uint8_t n,
1314 struct cds_ja_inode_flag *child_node_flag,
1315 struct cds_ja_inode_flag **nullify_node_flag_ptr,
1316 int level)
1317 {
1318 unsigned int new_type_index;
1319 struct cds_ja_inode *new_node;
1320 struct cds_ja_shadow_node *new_shadow_node = NULL;
1321 const struct cds_ja_type *new_type;
1322 struct cds_ja_inode_flag *new_node_flag, *old_node_flag;
1323 int ret;
1324 int fallback = 0;
1325
1326 old_node_flag = *old_node_flag_ptr;
1327
1328 /*
1329 * Need to find nearest type index even for ADD_SAME, because
1330 * this recompaction, when applied to linear nodes, will garbage
1331 * collect dummy (NULL) entries, and can therefore cause a few
1332 * linear representations to be skipped.
1333 */
1334 switch (mode) {
1335 case JA_RECOMPACT_ADD_SAME:
1336 new_type_index = find_nearest_type_index(old_type_index,
1337 shadow_node->nr_child + 1);
1338 dbg_printf("Recompact for node with %u children\n",
1339 shadow_node->nr_child + 1);
1340 break;
1341 case JA_RECOMPACT_ADD_NEXT:
1342 if (!shadow_node || old_type_index == NODE_INDEX_NULL) {
1343 new_type_index = 0;
1344 dbg_printf("Recompact for NULL\n");
1345 } else {
1346 new_type_index = find_nearest_type_index(old_type_index,
1347 shadow_node->nr_child + 1);
1348 dbg_printf("Recompact for node with %u children\n",
1349 shadow_node->nr_child + 1);
1350 }
1351 break;
1352 case JA_RECOMPACT_DEL:
1353 new_type_index = find_nearest_type_index(old_type_index,
1354 shadow_node->nr_child - 1);
1355 dbg_printf("Recompact for node with %u children\n",
1356 shadow_node->nr_child - 1);
1357 break;
1358 default:
1359 assert(0);
1360 }
1361
1362 retry: /* for fallback */
1363 dbg_printf("Recompact from type %d to type %d\n",
1364 old_type_index, new_type_index);
1365 new_type = &ja_types[new_type_index];
1366 if (new_type_index != NODE_INDEX_NULL) {
1367 new_node = alloc_cds_ja_node(ja, new_type);
1368 if (!new_node)
1369 return -ENOMEM;
1370
1371 if (new_type->type_class == RCU_JA_POOL) {
1372 switch (new_type->nr_pool_order) {
1373 case 1:
1374 {
1375 unsigned int node_distrib_bitsel;
1376
1377 node_distrib_bitsel =
1378 ja_node_sum_distribution_1d(mode, ja,
1379 old_type_index, old_type,
1380 old_node, shadow_node,
1381 n, child_node_flag,
1382 nullify_node_flag_ptr);
1383 assert(!((unsigned long) new_node & JA_POOL_1D_MASK));
1384 new_node_flag = ja_node_flag_pool_1d(new_node,
1385 new_type_index, node_distrib_bitsel);
1386 break;
1387 }
1388 case 2:
1389 {
1390 unsigned int node_distrib_bitsel[2];
1391
1392 ja_node_sum_distribution_2d(mode, ja,
1393 old_type_index, old_type,
1394 old_node, shadow_node,
1395 n, child_node_flag,
1396 nullify_node_flag_ptr,
1397 node_distrib_bitsel);
1398 assert(!((unsigned long) new_node & JA_POOL_1D_MASK));
1399 assert(!((unsigned long) new_node & JA_POOL_2D_MASK));
1400 new_node_flag = ja_node_flag_pool_2d(new_node,
1401 new_type_index, node_distrib_bitsel);
1402 break;
1403 }
1404 default:
1405 assert(0);
1406 }
1407 } else {
1408 new_node_flag = ja_node_flag(new_node, new_type_index);
1409 }
1410
1411 dbg_printf("Recompact inherit lock from %p\n", shadow_node);
1412 new_shadow_node = rcuja_shadow_set(ja->ht, new_node_flag, shadow_node, ja, level);
1413 if (!new_shadow_node) {
1414 free_cds_ja_node(ja, new_node);
1415 return -ENOMEM;
1416 }
1417 if (fallback)
1418 new_shadow_node->fallback_removal_count =
1419 JA_FALLBACK_REMOVAL_COUNT;
1420 } else {
1421 new_node = NULL;
1422 new_node_flag = NULL;
1423 }
1424
1425 assert(mode != JA_RECOMPACT_ADD_NEXT || old_type->type_class != RCU_JA_PIGEON);
1426
1427 if (new_type_index == NODE_INDEX_NULL)
1428 goto skip_copy;
1429
1430 switch (old_type->type_class) {
1431 case RCU_JA_LINEAR:
1432 {
1433 uint8_t nr_child =
1434 ja_linear_node_get_nr_child(old_type, old_node);
1435 unsigned int i;
1436
1437 for (i = 0; i < nr_child; i++) {
1438 struct cds_ja_inode_flag *iter;
1439 uint8_t v;
1440
1441 ja_linear_node_get_ith_pos(old_type, old_node, i, &v, &iter);
1442 if (!iter)
1443 continue;
1444 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1445 continue;
1446 ret = _ja_node_set_nth(new_type, new_node, new_node_flag,
1447 new_shadow_node,
1448 v, iter);
1449 if (new_type->type_class == RCU_JA_POOL && ret) {
1450 goto fallback_toosmall;
1451 }
1452 assert(!ret);
1453 }
1454 break;
1455 }
1456 case RCU_JA_POOL:
1457 {
1458 unsigned int pool_nr;
1459
1460 for (pool_nr = 0; pool_nr < (1U << old_type->nr_pool_order); pool_nr++) {
1461 struct cds_ja_inode *pool =
1462 ja_pool_node_get_ith_pool(old_type,
1463 old_node, pool_nr);
1464 uint8_t nr_child =
1465 ja_linear_node_get_nr_child(old_type, pool);
1466 unsigned int j;
1467
1468 for (j = 0; j < nr_child; j++) {
1469 struct cds_ja_inode_flag *iter;
1470 uint8_t v;
1471
1472 ja_linear_node_get_ith_pos(old_type, pool,
1473 j, &v, &iter);
1474 if (!iter)
1475 continue;
1476 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1477 continue;
1478 ret = _ja_node_set_nth(new_type, new_node, new_node_flag,
1479 new_shadow_node,
1480 v, iter);
1481 if (new_type->type_class == RCU_JA_POOL
1482 && ret) {
1483 goto fallback_toosmall;
1484 }
1485 assert(!ret);
1486 }
1487 }
1488 break;
1489 }
1490 case RCU_JA_NULL:
1491 assert(mode == JA_RECOMPACT_ADD_NEXT);
1492 break;
1493 case RCU_JA_PIGEON:
1494 {
1495 unsigned int i;
1496
1497 assert(mode == JA_RECOMPACT_DEL);
1498 for (i = 0; i < JA_ENTRY_PER_NODE; i++) {
1499 struct cds_ja_inode_flag *iter;
1500
1501 iter = ja_pigeon_node_get_ith_pos(old_type, old_node, i);
1502 if (!iter)
1503 continue;
1504 if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
1505 continue;
1506 ret = _ja_node_set_nth(new_type, new_node, new_node_flag,
1507 new_shadow_node,
1508 i, iter);
1509 if (new_type->type_class == RCU_JA_POOL && ret) {
1510 goto fallback_toosmall;
1511 }
1512 assert(!ret);
1513 }
1514 break;
1515 }
1516 default:
1517 assert(0);
1518 ret = -EINVAL;
1519 goto end;
1520 }
1521 skip_copy:
1522
1523 if (mode == JA_RECOMPACT_ADD_NEXT || mode == JA_RECOMPACT_ADD_SAME) {
1524 /* add node */
1525 ret = _ja_node_set_nth(new_type, new_node, new_node_flag,
1526 new_shadow_node,
1527 n, child_node_flag);
1528 if (new_type->type_class == RCU_JA_POOL && ret) {
1529 goto fallback_toosmall;
1530 }
1531 assert(!ret);
1532 }
1533
1534 if (fallback) {
1535 dbg_printf("Using fallback for %u children, node type index: %u, mode %s\n",
1536 new_shadow_node->nr_child, old_type_index, mode == JA_RECOMPACT_ADD_NEXT ? "add_next" :
1537 (mode == JA_RECOMPACT_DEL ? "del" : "add_same"));
1538 uatomic_inc(&ja->node_fallback_count_distribution[new_shadow_node->nr_child]);
1539 }
1540
1541 /* Return pointer to new recompacted node through old_node_flag_ptr */
1542 *old_node_flag_ptr = new_node_flag;
1543 if (old_node) {
1544 int flags;
1545
1546 flags = RCUJA_SHADOW_CLEAR_FREE_NODE;
1547 /*
1548 * It is OK to free the lock associated with a node
1549 * going to NULL, since we are holding the parent lock.
1550 * This synchronizes removal with re-add of that node.
1551 */
1552 if (new_type_index == NODE_INDEX_NULL)
1553 flags |= RCUJA_SHADOW_CLEAR_FREE_LOCK;
1554 ret = rcuja_shadow_clear(ja->ht, old_node_flag, shadow_node,
1555 flags);
1556 assert(!ret);
1557 }
1558
1559 ret = 0;
1560 end:
1561 return ret;
1562
1563 fallback_toosmall:
1564 /* fallback if next pool is too small */
1565 assert(new_shadow_node);
1566 ret = rcuja_shadow_clear(ja->ht, new_node_flag, new_shadow_node,
1567 RCUJA_SHADOW_CLEAR_FREE_NODE);
1568 assert(!ret);
1569
1570 switch (mode) {
1571 case JA_RECOMPACT_ADD_SAME:
1572 /*
1573 * JA_RECOMPACT_ADD_SAME is only triggered if a linear
1574 * node within a pool has unused entries. It should
1575 * therefore _never_ be too small.
1576 */
1577 assert(0);
1578
1579 /* Fall-through */
1580 case JA_RECOMPACT_ADD_NEXT:
1581 {
1582 const struct cds_ja_type *next_type;
1583
1584 /*
1585 * Recompaction attempt on add failed. Should only
1586 * happen if target node type is pool. Caused by
1587 * hard-to-split distribution. Recompact using the next
1588 * distribution size.
1589 */
1590 assert(new_type->type_class == RCU_JA_POOL);
1591 next_type = &ja_types[new_type_index + 1];
1592 /*
1593 * Try going to the next pool size if our population
1594 * fits within its range. This is not flagged as a
1595 * fallback.
1596 */
1597 if (shadow_node->nr_child + 1 >= next_type->min_child
1598 && shadow_node->nr_child + 1 <= next_type->max_child) {
1599 new_type_index++;
1600 goto retry;
1601 } else {
1602 new_type_index++;
1603 dbg_printf("Add fallback to type %d\n", new_type_index);
1604 uatomic_inc(&ja->nr_fallback);
1605 fallback = 1;
1606 goto retry;
1607 }
1608 break;
1609 }
1610 case JA_RECOMPACT_DEL:
1611 /*
1612 * Recompaction attempt on delete failed. Should only
1613 * happen if target node type is pool. This is caused by
1614 * a hard-to-split distribution. Recompact on same node
1615 * size, but flag current node as "fallback" to ensure
1616 * we don't attempt recompaction before some activity
1617 * has reshuffled our node.
1618 */
1619 assert(new_type->type_class == RCU_JA_POOL);
1620 new_type_index = old_type_index;
1621 dbg_printf("Delete fallback keeping type %d\n", new_type_index);
1622 uatomic_inc(&ja->nr_fallback);
1623 fallback = 1;
1624 goto retry;
1625 default:
1626 assert(0);
1627 return -EINVAL;
1628 }
1629
1630 /*
1631 * Last resort fallback: pigeon.
1632 */
1633 new_type_index = (1UL << JA_TYPE_BITS) - 1;
1634 dbg_printf("Fallback to type %d\n", new_type_index);
1635 uatomic_inc(&ja->nr_fallback);
1636 fallback = 1;
1637 goto retry;
1638 }
1639
1640 /*
1641 * Return 0 on success, -EAGAIN if need to retry, or other negative
1642 * error value otherwise.
1643 */
1644 static
1645 int ja_node_set_nth(struct cds_ja *ja,
1646 struct cds_ja_inode_flag **node_flag, uint8_t n,
1647 struct cds_ja_inode_flag *child_node_flag,
1648 struct cds_ja_shadow_node *shadow_node,
1649 int level)
1650 {
1651 int ret;
1652 unsigned int type_index;
1653 const struct cds_ja_type *type;
1654 struct cds_ja_inode *node;
1655
1656 dbg_printf("ja_node_set_nth for n=%u, node %p, shadow %p\n",
1657 (unsigned int) n, ja_node_ptr(*node_flag), shadow_node);
1658
1659 node = ja_node_ptr(*node_flag);
1660 type_index = ja_node_type(*node_flag);
1661 type = &ja_types[type_index];
1662 ret = _ja_node_set_nth(type, node, *node_flag, shadow_node,
1663 n, child_node_flag);
1664 switch (ret) {
1665 case -ENOSPC:
1666 /* Not enough space in node, need to recompact to next type. */
1667 ret = ja_node_recompact(JA_RECOMPACT_ADD_NEXT, ja, type_index, type, node,
1668 shadow_node, node_flag, n, child_node_flag, NULL, level);
1669 break;
1670 case -ERANGE:
1671 /* Node needs to be recompacted. */
1672 ret = ja_node_recompact(JA_RECOMPACT_ADD_SAME, ja, type_index, type, node,
1673 shadow_node, node_flag, n, child_node_flag, NULL, level);
1674 break;
1675 }
1676 return ret;
1677 }
1678
1679 /*
1680 * Return 0 on success, -EAGAIN if need to retry, or other negative
1681 * error value otherwise.
1682 */
1683 static
1684 int ja_node_clear_ptr(struct cds_ja *ja,
1685 struct cds_ja_inode_flag **node_flag_ptr, /* Pointer to location to nullify */
1686 struct cds_ja_inode_flag **parent_node_flag_ptr, /* Address of parent ptr in its parent */
1687 struct cds_ja_shadow_node *shadow_node, /* of parent */
1688 uint8_t n, int level)
1689 {
1690 int ret;
1691 unsigned int type_index;
1692 const struct cds_ja_type *type;
1693 struct cds_ja_inode *node;
1694
1695 dbg_printf("ja_node_clear_ptr for node %p, shadow %p, target ptr %p\n",
1696 ja_node_ptr(*parent_node_flag_ptr), shadow_node, node_flag_ptr);
1697
1698 node = ja_node_ptr(*parent_node_flag_ptr);
1699 type_index = ja_node_type(*parent_node_flag_ptr);
1700 type = &ja_types[type_index];
1701 ret = _ja_node_clear_ptr(type, node, *parent_node_flag_ptr, shadow_node, node_flag_ptr, n);
1702 if (ret == -EFBIG) {
1703 /* Should try recompaction. */
1704 ret = ja_node_recompact(JA_RECOMPACT_DEL, ja, type_index, type, node,
1705 shadow_node, parent_node_flag_ptr, n, NULL,
1706 node_flag_ptr, level);
1707 }
1708 return ret;
1709 }
1710
1711 struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key)
1712 {
1713 unsigned int tree_depth, i;
1714 struct cds_ja_inode_flag *node_flag;
1715 struct cds_hlist_head head = { NULL };
1716
1717 if (caa_unlikely(key > ja->key_max))
1718 return head;
1719 tree_depth = ja->tree_depth;
1720 node_flag = rcu_dereference(ja->root);
1721
1722 /* level 0: root node */
1723 if (!ja_node_ptr(node_flag))
1724 return head;
1725
1726 for (i = 1; i < tree_depth; i++) {
1727 uint8_t iter_key;
1728
1729 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - i - 1)));
1730 node_flag = ja_node_get_nth(node_flag, NULL, iter_key);
1731 dbg_printf("cds_ja_lookup iter key lookup %u finds node_flag %p\n",
1732 (unsigned int) iter_key, node_flag);
1733 if (!ja_node_ptr(node_flag))
1734 return head;
1735 }
1736
1737 /* Last level lookup succeded. We got an actual match. */
1738 head.next = (struct cds_hlist_node *) node_flag;
1739 return head;
1740 }
1741
1742 struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key)
1743 {
1744 int tree_depth, level;
1745 struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH];
1746 struct cds_hlist_head head = { NULL };
1747
1748 if (caa_unlikely(key > ja->key_max || !key))
1749 return head;
1750
1751 memset(cur_node_depth, 0, sizeof(cur_node_depth));
1752 tree_depth = ja->tree_depth;
1753 node_flag = rcu_dereference(ja->root);
1754 cur_node_depth[0] = node_flag;
1755
1756 /* level 0: root node */
1757 if (!ja_node_ptr(node_flag))
1758 return head;
1759
1760 for (level = 1; level < tree_depth; level++) {
1761 uint8_t iter_key;
1762
1763 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1)));
1764 node_flag = ja_node_get_nth(node_flag, NULL, iter_key);
1765 if (!ja_node_ptr(node_flag))
1766 break;
1767 cur_node_depth[level] = node_flag;
1768 dbg_printf("cds_ja_lookup iter key lookup %u finds node_flag %p\n",
1769 (unsigned int) iter_key, node_flag);
1770 }
1771
1772 if (level == tree_depth) {
1773 /* Last level lookup succeded. We got an equal match. */
1774 head.next = (struct cds_hlist_node *) node_flag;
1775 return head;
1776 }
1777
1778 /*
1779 * Find highest value left of current node.
1780 * Current node is cur_node_depth[level].
1781 * Start at current level. If we cannot find any key left of
1782 * ours, go one level up, seek highest value left of current
1783 * (recursively), and when we find one, get the rightmost child
1784 * of its rightmost child (recursively).
1785 */
1786 for (; level > 0; level--) {
1787 uint8_t iter_key;
1788
1789 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1)));
1790 node_flag = ja_node_get_left(cur_node_depth[level - 1],
1791 iter_key);
1792 /* If found left sibling, find rightmost child. */
1793 if (ja_node_ptr(node_flag))
1794 break;
1795 }
1796
1797 if (!level) {
1798 /* Reached the root and could not find a left sibling. */
1799 return head;
1800 }
1801
1802 level++;
1803 /* Find rightmost child of rightmost child (recursively). */
1804 for (; level < tree_depth; level++) {
1805 node_flag = ja_node_get_rightmost(node_flag);
1806 /* If found left sibling, find rightmost child. */
1807 if (!ja_node_ptr(node_flag))
1808 break;
1809 }
1810
1811 if (level == tree_depth) {
1812 /* Last level lookup succeded. We got a "lower than" match. */
1813 head.next = (struct cds_hlist_node *) node_flag;
1814 return head;
1815 }
1816
1817 /* No match */
1818 return head;
1819 }
1820
1821 /*
1822 * We reached an unpopulated node. Create it and the children we need,
1823 * and then attach the entire branch to the current node. This may
1824 * trigger recompaction of the current node. Locks needed: node lock
1825 * (for add), and, possibly, parent node lock (to update pointer due to
1826 * node recompaction).
1827 *
1828 * First take node lock, check if recompaction is needed, then take
1829 * parent lock (if needed). Then we can proceed to create the new
1830 * branch. Publish the new branch, and release locks.
1831 * TODO: we currently always take the parent lock even when not needed.
1832 */
1833 static
1834 int ja_attach_node(struct cds_ja *ja,
1835 struct cds_ja_inode_flag **attach_node_flag_ptr,
1836 struct cds_ja_inode_flag *attach_node_flag,
1837 struct cds_ja_inode_flag *parent_attach_node_flag,
1838 struct cds_ja_inode_flag **old_node_flag_ptr,
1839 struct cds_ja_inode_flag *old_node_flag,
1840 uint64_t key,
1841 unsigned int level,
1842 struct cds_ja_node *child_node)
1843 {
1844 struct cds_ja_shadow_node *shadow_node = NULL,
1845 *parent_shadow_node = NULL;
1846 struct cds_hlist_head head;
1847 struct cds_ja_inode_flag *iter_node_flag, *iter_dest_node_flag;
1848 int ret, i;
1849 struct cds_ja_inode_flag *created_nodes[JA_MAX_DEPTH];
1850 int nr_created_nodes = 0;
1851
1852 dbg_printf("Attach node at level %u (old_node_flag %p, attach_node_flag_ptr %p attach_node_flag %p, parent_attach_node_flag %p)\n",
1853 level, old_node_flag, attach_node_flag_ptr, attach_node_flag, parent_attach_node_flag);
1854
1855 assert(!old_node_flag);
1856 if (attach_node_flag) {
1857 shadow_node = rcuja_shadow_lookup_lock(ja->ht, attach_node_flag);
1858 if (!shadow_node) {
1859 ret = -EAGAIN;
1860 goto end;
1861 }
1862 }
1863 if (parent_attach_node_flag) {
1864 parent_shadow_node = rcuja_shadow_lookup_lock(ja->ht,
1865 parent_attach_node_flag);
1866 if (!parent_shadow_node) {
1867 ret = -EAGAIN;
1868 goto unlock_shadow;
1869 }
1870 }
1871
1872 if (old_node_flag_ptr && ja_node_ptr(*old_node_flag_ptr)) {
1873 /*
1874 * Target node has been updated between RCU lookup and
1875 * lock acquisition. We need to re-try lookup and
1876 * attach.
1877 */
1878 ret = -EAGAIN;
1879 goto unlock_parent;
1880 }
1881
1882 /*
1883 * Perform a lookup query to handle the case where
1884 * old_node_flag_ptr is NULL. We cannot use it to check if the
1885 * node has been populated between RCU lookup and mutex
1886 * acquisition.
1887 */
1888 if (!old_node_flag_ptr) {
1889 uint8_t iter_key;
1890 struct cds_ja_inode_flag *lookup_node_flag;
1891 struct cds_ja_inode_flag **lookup_node_flag_ptr;
1892
1893 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - level)));
1894 lookup_node_flag = ja_node_get_nth(attach_node_flag,
1895 &lookup_node_flag_ptr,
1896 iter_key);
1897 if (lookup_node_flag) {
1898 ret = -EEXIST;
1899 goto unlock_parent;
1900 }
1901 }
1902
1903 if (attach_node_flag_ptr && ja_node_ptr(*attach_node_flag_ptr) !=
1904 ja_node_ptr(attach_node_flag)) {
1905 /*
1906 * Target node has been updated between RCU lookup and
1907 * lock acquisition. We need to re-try lookup and
1908 * attach.
1909 */
1910 ret = -EAGAIN;
1911 goto unlock_parent;
1912 }
1913
1914 /* Create new branch, starting from bottom */
1915 CDS_INIT_HLIST_HEAD(&head);
1916 cds_hlist_add_head_rcu(&child_node->list, &head);
1917 iter_node_flag = (struct cds_ja_inode_flag *) head.next;
1918
1919 for (i = ja->tree_depth - 1; i >= (int) level; i--) {
1920 uint8_t iter_key;
1921
1922 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - i - 1)));
1923 dbg_printf("branch creation level %d, key %u\n",
1924 i, (unsigned int) iter_key);
1925 iter_dest_node_flag = NULL;
1926 ret = ja_node_set_nth(ja, &iter_dest_node_flag,
1927 iter_key,
1928 iter_node_flag,
1929 NULL, i);
1930 if (ret) {
1931 dbg_printf("branch creation error %d\n", ret);
1932 goto check_error;
1933 }
1934 created_nodes[nr_created_nodes++] = iter_dest_node_flag;
1935 iter_node_flag = iter_dest_node_flag;
1936 }
1937 assert(level > 0);
1938
1939 /* Publish branch */
1940 if (level == 1) {
1941 /*
1942 * Attaching to root node.
1943 */
1944 rcu_assign_pointer(ja->root, iter_node_flag);
1945 } else {
1946 uint8_t iter_key;
1947
1948 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - level)));
1949 dbg_printf("publish branch at level %d, key %u\n",
1950 level - 1, (unsigned int) iter_key);
1951 /* We need to use set_nth on the previous level. */
1952 iter_dest_node_flag = attach_node_flag;
1953 ret = ja_node_set_nth(ja, &iter_dest_node_flag,
1954 iter_key,
1955 iter_node_flag,
1956 shadow_node, level - 1);
1957 if (ret) {
1958 dbg_printf("branch publish error %d\n", ret);
1959 goto check_error;
1960 }
1961 /*
1962 * Attach branch
1963 */
1964 rcu_assign_pointer(*attach_node_flag_ptr, iter_dest_node_flag);
1965 }
1966
1967 /* Success */
1968 ret = 0;
1969
1970 check_error:
1971 if (ret) {
1972 for (i = 0; i < nr_created_nodes; i++) {
1973 int tmpret;
1974 int flags;
1975
1976 flags = RCUJA_SHADOW_CLEAR_FREE_LOCK;
1977 if (i)
1978 flags |= RCUJA_SHADOW_CLEAR_FREE_NODE;
1979 tmpret = rcuja_shadow_clear(ja->ht,
1980 created_nodes[i],
1981 NULL,
1982 flags);
1983 assert(!tmpret);
1984 }
1985 }
1986 unlock_parent:
1987 if (parent_shadow_node)
1988 rcuja_shadow_unlock(parent_shadow_node);
1989 unlock_shadow:
1990 if (shadow_node)
1991 rcuja_shadow_unlock(shadow_node);
1992 end:
1993 return ret;
1994 }
1995
1996 /*
1997 * Lock the parent containing the hlist head pointer, and add node to list of
1998 * duplicates. Failure can happen if concurrent update changes the
1999 * parent before we get the lock. We return -EAGAIN in that case.
2000 * Return 0 on success, negative error value on failure.
2001 */
2002 static
2003 int ja_chain_node(struct cds_ja *ja,
2004 struct cds_ja_inode_flag *parent_node_flag,
2005 struct cds_ja_inode_flag **node_flag_ptr,
2006 struct cds_ja_inode_flag *node_flag,
2007 struct cds_ja_node *node)
2008 {
2009 struct cds_ja_shadow_node *shadow_node;
2010 int ret = 0;
2011
2012 shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag);
2013 if (!shadow_node) {
2014 return -EAGAIN;
2015 }
2016 if (ja_node_ptr(*node_flag_ptr) != ja_node_ptr(node_flag)) {
2017 ret = -EAGAIN;
2018 goto end;
2019 }
2020 cds_hlist_add_head_rcu(&node->list, (struct cds_hlist_head *) node_flag_ptr);
2021 end:
2022 rcuja_shadow_unlock(shadow_node);
2023 return ret;
2024 }
2025
2026 static
2027 int _cds_ja_add(struct cds_ja *ja, uint64_t key,
2028 struct cds_ja_node *new_node,
2029 struct cds_ja_node **unique_node_ret)
2030 {
2031 unsigned int tree_depth, i;
2032 struct cds_ja_inode_flag *attach_node_flag,
2033 *parent_node_flag,
2034 *parent2_node_flag,
2035 *node_flag,
2036 *parent_attach_node_flag;
2037 struct cds_ja_inode_flag **attach_node_flag_ptr,
2038 **parent_node_flag_ptr,
2039 **node_flag_ptr;
2040 int ret;
2041
2042 if (caa_unlikely(key > ja->key_max)) {
2043 return -EINVAL;
2044 }
2045 tree_depth = ja->tree_depth;
2046
2047 retry:
2048 dbg_printf("cds_ja_add attempt: key %" PRIu64 ", node %p\n",
2049 key, new_node);
2050 parent2_node_flag = NULL;
2051 parent_node_flag =
2052 (struct cds_ja_inode_flag *) &ja->root; /* Use root ptr address as key for mutex */
2053 parent_node_flag_ptr = NULL;
2054 node_flag = rcu_dereference(ja->root);
2055 node_flag_ptr = &ja->root;
2056
2057 /* Iterate on all internal levels */
2058 for (i = 1; i < tree_depth; i++) {
2059 uint8_t iter_key;
2060
2061 if (!ja_node_ptr(node_flag))
2062 break;
2063 dbg_printf("cds_ja_add iter parent2_node_flag %p parent_node_flag %p node_flag_ptr %p node_flag %p\n",
2064 parent2_node_flag, parent_node_flag, node_flag_ptr, node_flag);
2065 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - i - 1)));
2066 parent2_node_flag = parent_node_flag;
2067 parent_node_flag = node_flag;
2068 parent_node_flag_ptr = node_flag_ptr;
2069 node_flag = ja_node_get_nth(node_flag,
2070 &node_flag_ptr,
2071 iter_key);
2072 }
2073
2074 /*
2075 * We reached either bottom of tree or internal NULL node,
2076 * simply add node to last internal level, or chain it if key is
2077 * already present.
2078 */
2079 if (!ja_node_ptr(node_flag)) {
2080 dbg_printf("cds_ja_add NULL parent2_node_flag %p parent_node_flag %p node_flag_ptr %p node_flag %p\n",
2081 parent2_node_flag, parent_node_flag, node_flag_ptr, node_flag);
2082
2083 attach_node_flag = parent_node_flag;
2084 attach_node_flag_ptr = parent_node_flag_ptr;
2085 parent_attach_node_flag = parent2_node_flag;
2086
2087 ret = ja_attach_node(ja, attach_node_flag_ptr,
2088 attach_node_flag,
2089 parent_attach_node_flag,
2090 node_flag_ptr,
2091 node_flag,
2092 key, i, new_node);
2093 } else {
2094 if (unique_node_ret) {
2095 *unique_node_ret = (struct cds_ja_node *) ja_node_ptr(node_flag);
2096 return -EEXIST;
2097 }
2098
2099 dbg_printf("cds_ja_add duplicate parent2_node_flag %p parent_node_flag %p node_flag_ptr %p node_flag %p\n",
2100 parent2_node_flag, parent_node_flag, node_flag_ptr, node_flag);
2101
2102 attach_node_flag = node_flag;
2103 attach_node_flag_ptr = node_flag_ptr;
2104 parent_attach_node_flag = parent_node_flag;
2105
2106 ret = ja_chain_node(ja,
2107 parent_attach_node_flag,
2108 attach_node_flag_ptr,
2109 attach_node_flag,
2110 new_node);
2111 }
2112 if (ret == -EAGAIN || ret == -EEXIST)
2113 goto retry;
2114
2115 return ret;
2116 }
2117
2118 int cds_ja_add(struct cds_ja *ja, uint64_t key,
2119 struct cds_ja_node *new_node)
2120 {
2121 return _cds_ja_add(ja, key, new_node, NULL);
2122 }
2123
2124 struct cds_ja_node *cds_ja_add_unique(struct cds_ja *ja, uint64_t key,
2125 struct cds_ja_node *new_node)
2126 {
2127 int ret;
2128 struct cds_ja_node *ret_node;
2129
2130 ret = _cds_ja_add(ja, key, new_node, &ret_node);
2131 if (ret == -EEXIST)
2132 return ret_node;
2133 else
2134 return new_node;
2135 }
2136
2137 /*
2138 * Note: there is no need to lookup the pointer address associated with
2139 * each node's nth item after taking the lock: it's already been done by
2140 * cds_ja_del while holding the rcu read-side lock, and our node rules
2141 * ensure that when a match value -> pointer is found in a node, it is
2142 * _NEVER_ changed for that node without recompaction, and recompaction
2143 * reallocates the node.
2144 * However, when a child is removed from "linear" nodes, its pointer
2145 * is set to NULL. We therefore check, while holding the locks, if this
2146 * pointer is NULL, and return -ENOENT to the caller if it is the case.
2147 */
2148 static
2149 int ja_detach_node(struct cds_ja *ja,
2150 struct cds_ja_inode_flag **snapshot,
2151 struct cds_ja_inode_flag ***snapshot_ptr,
2152 uint8_t *snapshot_n,
2153 int nr_snapshot,
2154 uint64_t key,
2155 struct cds_ja_node *node)
2156 {
2157 struct cds_ja_shadow_node *shadow_nodes[JA_MAX_DEPTH];
2158 struct cds_ja_inode_flag **node_flag_ptr = NULL,
2159 *parent_node_flag = NULL,
2160 **parent_node_flag_ptr = NULL;
2161 struct cds_ja_inode_flag *iter_node_flag;
2162 int ret, i, nr_shadow = 0, nr_clear = 0, nr_branch = 0;
2163 uint8_t n = 0;
2164
2165 assert(nr_snapshot == ja->tree_depth + 1);
2166
2167 /*
2168 * From the last internal level node going up, get the node
2169 * lock, check if the node has only one child left. If it is the
2170 * case, we continue iterating upward. When we reach a node
2171 * which has more that one child left, we lock the parent, and
2172 * proceed to the node deletion (removing its children too).
2173 */
2174 for (i = nr_snapshot - 2; i >= 1; i--) {
2175 struct cds_ja_shadow_node *shadow_node;
2176
2177 shadow_node = rcuja_shadow_lookup_lock(ja->ht,
2178 snapshot[i]);
2179 if (!shadow_node) {
2180 ret = -EAGAIN;
2181 goto end;
2182 }
2183 shadow_nodes[nr_shadow++] = shadow_node;
2184
2185 /*
2186 * Check if node has been removed between RCU
2187 * lookup and lock acquisition.
2188 */
2189 assert(snapshot_ptr[i + 1]);
2190 if (ja_node_ptr(*snapshot_ptr[i + 1])
2191 != ja_node_ptr(snapshot[i + 1])) {
2192 ret = -ENOENT;
2193 goto end;
2194 }
2195
2196 assert(shadow_node->nr_child > 0);
2197 if (shadow_node->nr_child == 1 && i > 1)
2198 nr_clear++;
2199 nr_branch++;
2200 if (shadow_node->nr_child > 1 || i == 1) {
2201 /* Lock parent and break */
2202 shadow_node = rcuja_shadow_lookup_lock(ja->ht,
2203 snapshot[i - 1]);
2204 if (!shadow_node) {
2205 ret = -EAGAIN;
2206 goto end;
2207 }
2208 shadow_nodes[nr_shadow++] = shadow_node;
2209
2210 /*
2211 * Check if node has been removed between RCU
2212 * lookup and lock acquisition.
2213 */
2214 assert(snapshot_ptr[i]);
2215 if (ja_node_ptr(*snapshot_ptr[i])
2216 != ja_node_ptr(snapshot[i])) {
2217 ret = -ENOENT;
2218 goto end;
2219 }
2220
2221 node_flag_ptr = snapshot_ptr[i + 1];
2222 n = snapshot_n[i + 1];
2223 parent_node_flag_ptr = snapshot_ptr[i];
2224 parent_node_flag = snapshot[i];
2225
2226 if (i > 1) {
2227 /*
2228 * Lock parent's parent, in case we need
2229 * to recompact parent.
2230 */
2231 shadow_node = rcuja_shadow_lookup_lock(ja->ht,
2232 snapshot[i - 2]);
2233 if (!shadow_node) {
2234 ret = -EAGAIN;
2235 goto end;
2236 }
2237 shadow_nodes[nr_shadow++] = shadow_node;
2238
2239 /*
2240 * Check if node has been removed between RCU
2241 * lookup and lock acquisition.
2242 */
2243 assert(snapshot_ptr[i - 1]);
2244 if (ja_node_ptr(*snapshot_ptr[i - 1])
2245 != ja_node_ptr(snapshot[i - 1])) {
2246 ret = -ENOENT;
2247 goto end;
2248 }
2249 }
2250
2251 break;
2252 }
2253 }
2254
2255 /*
2256 * At this point, we want to delete all nodes that are about to
2257 * be removed from shadow_nodes (except the last one, which is
2258 * either the root or the parent of the upmost node with 1
2259 * child). OK to free lock here, because RCU read lock is held,
2260 * and free only performed in call_rcu.
2261 */
2262
2263 for (i = 0; i < nr_clear; i++) {
2264 ret = rcuja_shadow_clear(ja->ht,
2265 shadow_nodes[i]->node_flag,
2266 shadow_nodes[i],
2267 RCUJA_SHADOW_CLEAR_FREE_NODE
2268 | RCUJA_SHADOW_CLEAR_FREE_LOCK);
2269 assert(!ret);
2270 }
2271
2272 iter_node_flag = parent_node_flag;
2273 /* Remove from parent */
2274 ret = ja_node_clear_ptr(ja,
2275 node_flag_ptr, /* Pointer to location to nullify */
2276 &iter_node_flag, /* Old new parent ptr in its parent */
2277 shadow_nodes[nr_branch - 1], /* of parent */
2278 n, nr_branch - 1);
2279 if (ret)
2280 goto end;
2281
2282 dbg_printf("ja_detach_node: publish %p instead of %p\n",
2283 iter_node_flag, *parent_node_flag_ptr);
2284 /* Update address of parent ptr in its parent */
2285 rcu_assign_pointer(*parent_node_flag_ptr, iter_node_flag);
2286
2287 end:
2288 for (i = 0; i < nr_shadow; i++)
2289 rcuja_shadow_unlock(shadow_nodes[i]);
2290 return ret;
2291 }
2292
2293 static
2294 int ja_unchain_node(struct cds_ja *ja,
2295 struct cds_ja_inode_flag *parent_node_flag,
2296 struct cds_ja_inode_flag **node_flag_ptr,
2297 struct cds_ja_inode_flag *node_flag,
2298 struct cds_ja_node *node)
2299 {
2300 struct cds_ja_shadow_node *shadow_node;
2301 struct cds_hlist_node *hlist_node;
2302 struct cds_hlist_head hlist_head;
2303 int ret = 0, count = 0, found = 0;
2304
2305 shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag);
2306 if (!shadow_node)
2307 return -EAGAIN;
2308 if (ja_node_ptr(*node_flag_ptr) != ja_node_ptr(node_flag)) {
2309 ret = -EAGAIN;
2310 goto end;
2311 }
2312 hlist_head.next = (struct cds_hlist_node *) ja_node_ptr(node_flag);
2313 /*
2314 * Retry if another thread removed all but one of duplicates
2315 * since check (this check was performed without lock).
2316 * Ensure that the node we are about to remove is still in the
2317 * list (while holding lock).
2318 */
2319 cds_hlist_for_each_rcu(hlist_node, &hlist_head) {
2320 if (count == 0) {
2321 /* FIXME: currently a work-around */
2322 hlist_node->prev = (struct cds_hlist_node *) node_flag_ptr;
2323 }
2324 count++;
2325 if (hlist_node == &node->list)
2326 found++;
2327 }
2328 assert(found <= 1);
2329 if (!found || count == 1) {
2330 ret = -EAGAIN;
2331 goto end;
2332 }
2333 cds_hlist_del_rcu(&node->list);
2334 /*
2335 * Validate that we indeed removed the node from linked list.
2336 */
2337 assert(ja_node_ptr(*node_flag_ptr) != (struct cds_ja_inode *) node);
2338 end:
2339 rcuja_shadow_unlock(shadow_node);
2340 return ret;
2341 }
2342
2343 /*
2344 * Called with RCU read lock held.
2345 */
2346 int cds_ja_del(struct cds_ja *ja, uint64_t key,
2347 struct cds_ja_node *node)
2348 {
2349 unsigned int tree_depth, i;
2350 struct cds_ja_inode_flag *snapshot[JA_MAX_DEPTH];
2351 struct cds_ja_inode_flag **snapshot_ptr[JA_MAX_DEPTH];
2352 uint8_t snapshot_n[JA_MAX_DEPTH];
2353 struct cds_ja_inode_flag *node_flag;
2354 struct cds_ja_inode_flag **prev_node_flag_ptr,
2355 **node_flag_ptr;
2356 int nr_snapshot;
2357 int ret;
2358
2359 if (caa_unlikely(key > ja->key_max))
2360 return -EINVAL;
2361 tree_depth = ja->tree_depth;
2362
2363 retry:
2364 nr_snapshot = 0;
2365 dbg_printf("cds_ja_del attempt: key %" PRIu64 ", node %p\n",
2366 key, node);
2367
2368 /* snapshot for level 0 is only for shadow node lookup */
2369 snapshot_n[0] = 0;
2370 snapshot_n[1] = 0;
2371 snapshot_ptr[nr_snapshot] = NULL;
2372 snapshot[nr_snapshot++] = (struct cds_ja_inode_flag *) &ja->root;
2373 node_flag = rcu_dereference(ja->root);
2374 prev_node_flag_ptr = &ja->root;
2375 node_flag_ptr = &ja->root;
2376
2377 /* Iterate on all internal levels */
2378 for (i = 1; i < tree_depth; i++) {
2379 uint8_t iter_key;
2380
2381 dbg_printf("cds_ja_del iter node_flag %p\n",
2382 node_flag);
2383 if (!ja_node_ptr(node_flag)) {
2384 return -ENOENT;
2385 }
2386 iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - i - 1)));
2387 snapshot_n[nr_snapshot + 1] = iter_key;
2388 snapshot_ptr[nr_snapshot] = prev_node_flag_ptr;
2389 snapshot[nr_snapshot++] = node_flag;
2390 node_flag = ja_node_get_nth(node_flag,
2391 &node_flag_ptr,
2392 iter_key);
2393 if (node_flag)
2394 prev_node_flag_ptr = node_flag_ptr;
2395 dbg_printf("cds_ja_del iter key lookup %u finds node_flag %p, prev_node_flag_ptr %p\n",
2396 (unsigned int) iter_key, node_flag,
2397 prev_node_flag_ptr);
2398 }
2399 /*
2400 * We reached bottom of tree, try to find the node we are trying
2401 * to remove. Fail if we cannot find it.
2402 */
2403 if (!ja_node_ptr(node_flag)) {
2404 dbg_printf("cds_ja_del: no node found for key %" PRIu64 "\n",
2405 key);
2406 return -ENOENT;
2407 } else {
2408 struct cds_hlist_head hlist_head;
2409 struct cds_hlist_node *hlist_node;
2410 struct cds_ja_node *entry, *match = NULL;
2411 int count = 0;
2412
2413 hlist_head.next =
2414 (struct cds_hlist_node *) ja_node_ptr(node_flag);
2415 cds_hlist_for_each_entry_rcu(entry,
2416 hlist_node,
2417 &hlist_head,
2418 list) {
2419 dbg_printf("cds_ja_del: compare %p with entry %p\n", node, entry);
2420 if (entry == node)
2421 match = entry;
2422 count++;
2423 }
2424 if (!match) {
2425 dbg_printf("cds_ja_del: no node match for node %p key %" PRIu64 "\n", node, key);
2426 return -ENOENT;
2427 }
2428 assert(count > 0);
2429 if (count == 1) {
2430 /*
2431 * Removing last of duplicates. Last snapshot
2432 * does not have a shadow node (external leafs).
2433 */
2434 snapshot_ptr[nr_snapshot] = prev_node_flag_ptr;
2435 snapshot[nr_snapshot++] = node_flag;
2436 ret = ja_detach_node(ja, snapshot, snapshot_ptr,
2437 snapshot_n, nr_snapshot, key, node);
2438 } else {
2439 ret = ja_unchain_node(ja, snapshot[nr_snapshot - 1],
2440 node_flag_ptr, node_flag, match);
2441 }
2442 }
2443 /*
2444 * Explanation of -ENOENT handling: caused by concurrent delete
2445 * between RCU lookup and actual removal. Need to re-do the
2446 * lookup and removal attempt.
2447 */
2448 if (ret == -EAGAIN || ret == -ENOENT)
2449 goto retry;
2450 return ret;
2451 }
2452
2453 struct cds_ja *_cds_ja_new(unsigned int key_bits,
2454 const struct rcu_flavor_struct *flavor)
2455 {
2456 struct cds_ja *ja;
2457 int ret;
2458 struct cds_ja_shadow_node *root_shadow_node;
2459
2460 ja = calloc(sizeof(*ja), 1);
2461 if (!ja)
2462 goto ja_error;
2463
2464 switch (key_bits) {
2465 case 8:
2466 case 16:
2467 case 24:
2468 case 32:
2469 case 40:
2470 case 48:
2471 case 56:
2472 ja->key_max = (1ULL << key_bits) - 1;
2473 break;
2474 case 64:
2475 ja->key_max = UINT64_MAX;
2476 break;
2477 default:
2478 goto check_error;
2479 }
2480
2481 /* ja->root is NULL */
2482 /* tree_depth 0 is for pointer to root node */
2483 ja->tree_depth = (key_bits >> JA_LOG2_BITS_PER_BYTE) + 1;
2484 assert(ja->tree_depth <= JA_MAX_DEPTH);
2485 ja->ht = rcuja_create_ht(flavor);
2486 if (!ja->ht)
2487 goto ht_error;
2488
2489 /*
2490 * Note: we should not free this node until judy array destroy.
2491 */
2492 root_shadow_node = rcuja_shadow_set(ja->ht,
2493 (struct cds_ja_inode_flag *) &ja->root,
2494 NULL, ja, 0);
2495 if (!root_shadow_node) {
2496 ret = -ENOMEM;
2497 goto ht_node_error;
2498 }
2499
2500 return ja;
2501
2502 ht_node_error:
2503 ret = rcuja_delete_ht(ja->ht);
2504 assert(!ret);
2505 ht_error:
2506 check_error:
2507 free(ja);
2508 ja_error:
2509 return NULL;
2510 }
2511
2512 /*
2513 * Called from RCU read-side CS.
2514 */
2515 __attribute__((visibility("protected")))
2516 void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node,
2517 struct cds_ja_inode_flag *node_flag,
2518 void (*free_node_cb)(struct rcu_head *head))
2519 {
2520 const struct rcu_flavor_struct *flavor;
2521 unsigned int type_index;
2522 struct cds_ja_inode *node;
2523 const struct cds_ja_type *type;
2524
2525 flavor = cds_lfht_rcu_flavor(shadow_node->ja->ht);
2526 node = ja_node_ptr(node_flag);
2527 assert(node != NULL);
2528 type_index = ja_node_type(node_flag);
2529 type = &ja_types[type_index];
2530
2531 switch (type->type_class) {
2532 case RCU_JA_LINEAR:
2533 {
2534 uint8_t nr_child =
2535 ja_linear_node_get_nr_child(type, node);
2536 unsigned int i;
2537
2538 for (i = 0; i < nr_child; i++) {
2539 struct cds_ja_inode_flag *iter;
2540 struct cds_hlist_head head;
2541 struct cds_ja_node *entry;
2542 struct cds_hlist_node *pos, *tmp;
2543 uint8_t v;
2544
2545 ja_linear_node_get_ith_pos(type, node, i, &v, &iter);
2546 if (!iter)
2547 continue;
2548 head.next = (struct cds_hlist_node *) iter;
2549 cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) {
2550 flavor->update_call_rcu(&entry->head, free_node_cb);
2551 }
2552 }
2553 break;
2554 }
2555 case RCU_JA_POOL:
2556 {
2557 unsigned int pool_nr;
2558
2559 for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
2560 struct cds_ja_inode *pool =
2561 ja_pool_node_get_ith_pool(type, node, pool_nr);
2562 uint8_t nr_child =
2563 ja_linear_node_get_nr_child(type, pool);
2564 unsigned int j;
2565
2566 for (j = 0; j < nr_child; j++) {
2567 struct cds_ja_inode_flag *iter;
2568 struct cds_hlist_head head;
2569 struct cds_ja_node *entry;
2570 struct cds_hlist_node *pos, *tmp;
2571 uint8_t v;
2572
2573 ja_linear_node_get_ith_pos(type, pool, j, &v, &iter);
2574 if (!iter)
2575 continue;
2576 head.next = (struct cds_hlist_node *) iter;
2577 cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) {
2578 flavor->update_call_rcu(&entry->head, free_node_cb);
2579 }
2580 }
2581 }
2582 break;
2583 }
2584 case RCU_JA_NULL:
2585 break;
2586 case RCU_JA_PIGEON:
2587 {
2588 unsigned int i;
2589
2590 for (i = 0; i < JA_ENTRY_PER_NODE; i++) {
2591 struct cds_ja_inode_flag *iter;
2592 struct cds_hlist_head head;
2593 struct cds_ja_node *entry;
2594 struct cds_hlist_node *pos, *tmp;
2595
2596 iter = ja_pigeon_node_get_ith_pos(type, node, i);
2597 if (!iter)
2598 continue;
2599 head.next = (struct cds_hlist_node *) iter;
2600 cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) {
2601 flavor->update_call_rcu(&entry->head, free_node_cb);
2602 }
2603 }
2604 break;
2605 }
2606 default:
2607 assert(0);
2608 }
2609 }
2610
2611 static
2612 void print_debug_fallback_distribution(struct cds_ja *ja)
2613 {
2614 int i;
2615
2616 fprintf(stderr, "Fallback node distribution:\n");
2617 for (i = 0; i < JA_ENTRY_PER_NODE; i++) {
2618 if (!ja->node_fallback_count_distribution[i])
2619 continue;
2620 fprintf(stderr, " %3u: %4lu\n",
2621 i, ja->node_fallback_count_distribution[i]);
2622 }
2623 }
2624
2625 static
2626 int ja_final_checks(struct cds_ja *ja)
2627 {
2628 double fallback_ratio;
2629 unsigned long na, nf, nr_fallback;
2630 int ret = 0;
2631
2632 fallback_ratio = (double) uatomic_read(&ja->nr_fallback);
2633 fallback_ratio /= (double) uatomic_read(&ja->nr_nodes_allocated);
2634 nr_fallback = uatomic_read(&ja->nr_fallback);
2635 if (nr_fallback)
2636 fprintf(stderr,
2637 "[warning] RCU Judy Array used %lu fallback node(s) (ratio: %g)\n",
2638 uatomic_read(&ja->nr_fallback),
2639 fallback_ratio);
2640
2641 na = uatomic_read(&ja->nr_nodes_allocated);
2642 nf = uatomic_read(&ja->nr_nodes_freed);
2643 dbg_printf("Nodes allocated: %lu, Nodes freed: %lu.\n", na, nf);
2644 if (nr_fallback)
2645 print_debug_fallback_distribution(ja);
2646
2647 if (na != nf) {
2648 fprintf(stderr, "[error] Judy array leaked %ld nodes. Allocated: %lu, freed: %lu.\n",
2649 (long) na - nf, na, nf);
2650 ret = -1;
2651 }
2652 return ret;
2653 }
2654
2655 /*
2656 * There should be no more concurrent add to the judy array while it is
2657 * being destroyed (ensured by the caller).
2658 */
2659 int cds_ja_destroy(struct cds_ja *ja,
2660 void (*free_node_cb)(struct rcu_head *head))
2661 {
2662 const struct rcu_flavor_struct *flavor;
2663 int ret;
2664
2665 flavor = cds_lfht_rcu_flavor(ja->ht);
2666 rcuja_shadow_prune(ja->ht,
2667 RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK,
2668 free_node_cb);
2669 flavor->thread_offline();
2670 ret = rcuja_delete_ht(ja->ht);
2671 if (ret)
2672 return ret;
2673
2674 /* Wait for in-flight call_rcu free to complete. */
2675 flavor->barrier();
2676
2677 flavor->thread_online();
2678 ret = ja_final_checks(ja);
2679 free(ja);
2680 return ret;
2681 }
Userspace RCU (urcu) for Linux
This page took 0.098106 seconds and 5 git commands to generate.