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 <urcu/rcuja.h>
  28 #include <urcu/compiler.h>
  29 #include <urcu/arch.h>
  30 #include <assert.h>
  31 #include <urcu-pointer.h>
  32
  33 #include "rcuja-internal.h"
  34 #include "bitfield.h"
  35
  36 enum cds_ja_type_class {
  37         RCU_JA_LINEAR = 0,      /* Type A */
  38                         /* 32-bit: 1 to 25 children, 8 to 128 bytes */
  39                         /* 64-bit: 1 to 28 children, 16 to 256 bytes */
  40         RCU_JA_POOL = 1,        /* Type B */
  41                         /* 32-bit: 26 to 100 children, 256 to 512 bytes */
  42                         /* 64-bit: 29 to 112 children, 512 to 1024 bytes */
  43         RCU_JA_PIGEON = 2,      /* Type C */
  44                         /* 32-bit: 101 to 256 children, 1024 bytes */
  45                         /* 64-bit: 113 to 256 children, 2048 bytes */
  46         /* Leaf nodes are implicit from their height in the tree */
  47         RCU_JA_NR_TYPES,
  48
  49         RCU_JA_NULL,    /* not an encoded type, but keeps code regular */
  50 };
  51
  52 struct cds_ja_type {
  53         enum cds_ja_type_class type_class;
  54         uint16_t min_child;             /* minimum number of children: 1 to 256 */
  55         uint16_t max_child;             /* maximum number of children: 1 to 256 */
  56         uint16_t max_linear_child;      /* per-pool max nr. children: 1 to 256 */
  57         uint16_t order;                 /* node size is (1 << order), in bytes */
  58         uint16_t nr_pool_order;         /* number of pools */
  59         uint16_t pool_size_order;       /* pool size */
  60 };
  61
  62 /*
  63  * Number of least significant pointer bits reserved to represent the
  64  * child type.
  65  */
  66 #define JA_TYPE_BITS    3
  67 #define JA_TYPE_MAX_NR  (1U << JA_TYPE_BITS)
  68 #define JA_TYPE_MASK    (JA_TYPE_MAX_NR - 1)
  69 #define JA_PTR_MASK     (~JA_TYPE_MASK)
  70
  71 #define JA_ENTRY_PER_NODE       256UL
  72
  73 /*
  74  * Entry for NULL node is at index 8 of the table. It is never encoded
  75  * in flags.
  76  */
  77 #define NODE_INDEX_NULL         8
  78
  79 /*
  80  * Iteration on the array to find the right node size for the number of
  81  * children stops when it reaches .max_child == 256 (this is the largest
  82  * possible node size, which contains 256 children).
  83  * The min_child overlaps with the previous max_child to provide an
  84  * hysteresis loop to reallocation for patterns of cyclic add/removal
  85  * within the same node.
  86  * The node the index within the following arrays is represented on 3
  87  * bits. It identifies the node type, min/max number of children, and
  88  * the size order.
  89  * The max_child values for the RCU_JA_POOL below result from
  90  * statistical approximation: over million populations, the max_child
  91  * covers between 97% and 99% of the populations generated. Therefore, a
  92  * fallback should exist to cover the rare extreme population unbalance
  93  * cases, but it will not have a major impact on speed nor space
  94  * consumption, since those are rare cases.
  95  */
  96
  97 #if (CAA_BITS_PER_LONG < 64)
  98 /* 32-bit pointers */
  99 enum {
 100         ja_type_0_max_child = 1,
 101         ja_type_1_max_child = 3,
 102         ja_type_2_max_child = 6,
 103         ja_type_3_max_child = 12,
 104         ja_type_4_max_child = 25,
 105         ja_type_5_max_child = 48,
 106         ja_type_6_max_child = 92,
 107         ja_type_7_max_child = 256,
 108         ja_type_8_max_child = 0,        /* NULL */
 109 };
 110
 111 enum {
 112         ja_type_0_max_linear_child = 1,
 113         ja_type_1_max_linear_child = 3,
 114         ja_type_2_max_linear_child = 6,
 115         ja_type_3_max_linear_child = 12,
 116         ja_type_4_max_linear_child = 25,
 117         ja_type_5_max_linear_child = 24,
 118         ja_type_6_max_linear_child = 23,
 119 };
 120
 121 enum {
 122         ja_type_5_nr_pool_order = 1,
 123         ja_type_6_nr_pool_order = 2,
 124 };
 125
 126 const struct cds_ja_type ja_types[] = {
 127         { .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, },
 128         { .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, },
 129         { .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, },
 130         { .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, },
 131         { .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, },
 132
 133         /* Pools may fill sooner than max_child */
 134         { .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, },
 135         { .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, },
 136
 137         /*
 138          * TODO: Upon node removal below min_child, if child pool is
 139          * filled beyond capacity, we need to roll back to pigeon.
 140          */
 141         { .type_class = RCU_JA_PIGEON, .min_child = 89, .max_child = ja_type_7_max_child, .order = 10, },
 142
 143         { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, },
 144 };
 145 #else /* !(CAA_BITS_PER_LONG < 64) */
 146 /* 64-bit pointers */
 147 enum {
 148         ja_type_0_max_child = 1,
 149         ja_type_1_max_child = 3,
 150         ja_type_2_max_child = 7,
 151         ja_type_3_max_child = 14,
 152         ja_type_4_max_child = 28,
 153         ja_type_5_max_child = 54,
 154         ja_type_6_max_child = 104,
 155         ja_type_7_max_child = 256,
 156         ja_type_8_max_child = 256,
 157 };
 158
 159 enum {
 160         ja_type_0_max_linear_child = 1,
 161         ja_type_1_max_linear_child = 3,
 162         ja_type_2_max_linear_child = 7,
 163         ja_type_3_max_linear_child = 14,
 164         ja_type_4_max_linear_child = 28,
 165         ja_type_5_max_linear_child = 27,
 166         ja_type_6_max_linear_child = 26,
 167 };
 168
 169 enum {
 170         ja_type_5_nr_pool_order = 1,
 171         ja_type_6_nr_pool_order = 2,
 172 };
 173
 174 const struct cds_ja_type ja_types[] = {
 175         { .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, },
 176         { .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, },
 177         { .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, },
 178         { .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, },
 179         { .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, },
 180
 181         /* Pools may fill sooner than max_child. */
 182         { .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, },
 183         { .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, },
 184
 185         /*
 186          * TODO: Upon node removal below min_child, if child pool is
 187          * filled beyond capacity, we need to roll back to pigeon.
 188          */
 189         { .type_class = RCU_JA_PIGEON, .min_child = 101, .max_child = ja_type_7_max_child, .order = 11, },
 190
 191         { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, },
 192 };
 193 #endif /* !(BITS_PER_LONG < 64) */
 194
 195 static inline __attribute__((unused))
 196 void static_array_size_check(void)
 197 {
 198         CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) < JA_TYPE_MAX_NR);
 199 }
 200
 201 /*
 202  * The cds_ja_node contains the compressed node data needed for
 203  * read-side. For linear and pool node configurations, it starts with a
 204  * byte counting the number of children in the node.  Then, the
 205  * node-specific data is placed.
 206  * The node mutex, if any is needed, protecting concurrent updated of
 207  * each node is placed in a separate hash table indexed by node address.
 208  * For the pigeon configuration, the number of children is also kept in
 209  * a separate hash table, indexed by node address, because it is only
 210  * required for updates.
 211  */
 212
 213 #define DECLARE_LINEAR_NODE(index)                                                              \
 214         struct {                                                                                \
 215                 uint8_t nr_child;                                                               \
 216                 uint8_t child_value[ja_type_## index ##_max_linear_child];                      \
 217                 struct cds_ja_node_flag *child_ptr[ja_type_## index ##_max_linear_child];       \
 218         }
 219
 220 #define DECLARE_POOL_NODE(index)                                                                \
 221         struct {                                                                                \
 222                 struct {                                                                        \
 223                         uint8_t nr_child;                                                       \
 224                         uint8_t child_value[ja_type_## index ##_max_linear_child];              \
 225                         struct cds_ja_node_flag *child_ptr[ja_type_## index ##_max_linear_child]; \
 226                 } linear[1U << ja_type_## index ##_nr_pool_order];                              \
 227         }
 228
 229 struct cds_ja_node {
 230         union {
 231                 /* Linear configuration */
 232                 DECLARE_LINEAR_NODE(0) conf_0;
 233                 DECLARE_LINEAR_NODE(1) conf_1;
 234                 DECLARE_LINEAR_NODE(2) conf_2;
 235                 DECLARE_LINEAR_NODE(3) conf_3;
 236                 DECLARE_LINEAR_NODE(4) conf_4;
 237
 238                 /* Pool configuration */
 239                 DECLARE_POOL_NODE(5) conf_5;
 240                 DECLARE_POOL_NODE(6) conf_6;
 241
 242                 /* Pigeon configuration */
 243                 struct {
 244                         struct cds_ja_node_flag *child[ja_type_7_max_child];
 245                 } conf_7;
 246                 /* data aliasing nodes for computed accesses */
 247                 uint8_t data[sizeof(struct cds_ja_node_flag *) * ja_type_7_max_child];
 248         } u;
 249 };
 250
 251 static
 252 struct cds_ja_node_flag *ja_node_flag(struct cds_ja_node *node,
 253                 unsigned int type)
 254 {
 255         assert(type < RCU_JA_NR_TYPES);
 256         return (struct cds_ja_node_flag *) (((unsigned long) node) | type);
 257 }
 258
 259 static
 260 struct cds_ja_node *ja_node_ptr(struct cds_ja_node_flag *node)
 261 {
 262         return (struct cds_ja_node *) (((unsigned long) node) | JA_PTR_MASK);
 263 }
 264
 265 static
 266 unsigned int ja_node_type(struct cds_ja_node_flag *node)
 267 {
 268         unsigned int type;
 269
 270         if (ja_node_ptr(node) == NULL) {
 271                 return NODE_INDEX_NULL;
 272         }
 273         type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
 274         assert(type < RCU_JA_NR_TYPES);
 275         return type;
 276 }
 277
 278 struct cds_ja_node *alloc_cds_ja_node(const struct cds_ja_type *ja_type)
 279 {
 280         return calloc(1U << ja_type->order, sizeof(char));
 281 }
 282
 283 void free_cds_ja_node(struct cds_ja_node *node)
 284 {
 285         free(node);
 286 }
 287
 288 #define __JA_ALIGN_MASK(v, mask)        (((v) + (mask)) & ~(mask))
 289 #define JA_ALIGN(v, align)              __JA_ALIGN_MASK(v, (typeof(v)) (align) - 1)
 290 #define __JA_FLOOR_MASK(v, mask)        ((v) & ~(mask))
 291 #define JA_FLOOR(v, align)              __JA_FLOOR_MASK(v, (typeof(v)) (align) - 1)
 292
 293 static
 294 uint8_t *align_ptr_size(uint8_t *ptr)
 295 {
 296         return (uint8_t *) JA_ALIGN((unsigned long) ptr, sizeof(void *));
 297 }
 298
 299 static
 300 uint8_t ja_linear_node_get_nr_child(const struct cds_ja_type *type,
 301                 struct cds_ja_node *node)
 302 {
 303         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 304         return CMM_LOAD_SHARED(node->u.data[0]);
 305 }
 306
 307 /*
 308  * The order in which values and pointers are does does not matter: if
 309  * a value is missing, we return NULL. If a value is there, but its
 310  * associated pointers is still NULL, we return NULL too.
 311  */
 312 static
 313 struct cds_ja_node_flag *ja_linear_node_get_nth(const struct cds_ja_type *type,
 314                 struct cds_ja_node *node,
 315                 uint8_t n)
 316 {
 317         uint8_t nr_child;
 318         uint8_t *values;
 319         struct cds_ja_node_flag **pointers;
 320         struct cds_ja_node_flag *ptr;
 321         unsigned int i;
 322
 323         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 324
 325         nr_child = ja_linear_node_get_nr_child(type, node);
 326         cmm_smp_rmb();  /* read nr_child before values and pointers */
 327         assert(nr_child <= type->max_linear_child);
 328         assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
 329
 330         values = &node->u.data[1];
 331         for (i = 0; i < nr_child; i++) {
 332                 if (CMM_LOAD_SHARED(values[i]) == n)
 333                         break;
 334         }
 335         if (i >= nr_child)
 336                 return NULL;
 337         pointers = (struct cds_ja_node_flag **) align_ptr_size(&values[type->max_linear_child]);
 338         ptr = rcu_dereference(pointers[i]);
 339         assert(ja_node_ptr(ptr) != NULL);
 340         return ptr;
 341 }
 342
 343 static
 344 struct cds_ja_node_flag *ja_linear_node_get_ith_pos(const struct cds_ja_type *type,
 345                 struct cds_ja_node *node,
 346                 uint8_t i,
 347                 uint8_t *v,
 348                 struct cds_ja_node_flag **iter)
 349 {
 350         uint8_t *values;
 351         struct cds_ja_node_flag **pointers;
 352
 353         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 354         assert(i < ja_linear_node_get_nr_child(type, node));
 355
 356         values = &node->u.data[1];
 357         *v = values[i];
 358         pointers = (struct cds_ja_node_flag **) align_ptr_size(&values[type->max_linear_child]);
 359         *iter = pointers[i];
 360 }
 361
 362 static
 363 struct cds_ja_node_flag *ja_pool_node_get_nth(const struct cds_ja_type *type,
 364                 struct cds_ja_node *node,
 365                 uint8_t n)
 366 {
 367         struct cds_ja_node *linear;
 368
 369         assert(type->type_class == RCU_JA_POOL);
 370         /*
 371          * TODO: currently, we select the pool by highest bits. We
 372          * should support various encodings.
 373          */
 374         linear = (struct cds_ja_node *)
 375                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 376         return ja_linear_node_get_nth(type, linear, n);
 377 }
 378
 379 static
 380 struct cds_ja_node *ja_pool_node_get_ith_pool(const struct cds_ja_type *type,
 381                 struct cds_ja_node *node,
 382                 uint8_t i)
 383 {
 384         assert(type->type_class == RCU_JA_POOL);
 385         return (struct cds_ja_node *)
 386                 &node->u.data[(unsigned int) i << type->pool_size_order];
 387 }
 388
 389 static
 390 struct cds_ja_node_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type,
 391                 struct cds_ja_node *node,
 392                 uint8_t n)
 393 {
 394         assert(type->type_class == RCU_JA_PIGEON);
 395         return rcu_dereference(((struct cds_ja_node_flag **) node->u.data)[n]);
 396 }
 397
 398 /*
 399  * ja_node_get_nth: get nth item from a node.
 400  * node_flag is already rcu_dereference'd.
 401  */
 402 static
 403 struct cds_ja_node_flag *ja_node_get_nth(struct cds_ja_node_flag *node_flag,
 404                 uint8_t n)
 405 {
 406         unsigned int type_index;
 407         struct cds_ja_node *node;
 408         const struct cds_ja_type *type;
 409
 410         node = ja_node_ptr(node_flag);
 411         assert(node != NULL);
 412         type_index = ja_node_type(node_flag);
 413         type = &ja_types[type_index];
 414
 415         switch (type->type_class) {
 416         case RCU_JA_LINEAR:
 417                 return ja_linear_node_get_nth(type, node, n);
 418         case RCU_JA_POOL:
 419                 return ja_pool_node_get_nth(type, node, n);
 420         case RCU_JA_PIGEON:
 421                 return ja_pigeon_node_get_nth(type, node, n);
 422         default:
 423                 assert(0);
 424                 return (void *) -1UL;
 425         }
 426 }
 427
 428 /*
 429  * TODO: use ja_get_nr_child to monitor limits triggering shrink
 430  * recompaction.
 431  * Also use ja_get_nr_child to make the difference between resize and
 432  * pool change of compaction bit(s).
 433  */
 434 static
 435 unsigned int ja_get_nr_child(struct cds_ja_shadow_node *shadow_node)
 436 {
 437         return shadow_node->nr_child;
 438 }
 439
 440 static
 441 int ja_linear_node_set_nth(const struct cds_ja_type *type,
 442                 struct cds_ja_node *node,
 443                 struct cds_ja_shadow_node *shadow_node,
 444                 uint8_t n,
 445                 struct cds_ja_node_flag *child_node_flag)
 446 {
 447         uint8_t nr_child;
 448         uint8_t *values, *nr_child_ptr;
 449         struct cds_ja_node_flag **pointers;
 450         unsigned int i;
 451
 452         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 453
 454         nr_child_ptr = &node->u.data[0];
 455         nr_child = *nr_child_ptr;
 456         assert(nr_child <= type->max_linear_child);
 457         assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
 458
 459         values = &node->u.data[1];
 460         for (i = 0; i < nr_child; i++) {
 461                 if (values[i] == n)
 462                         return -EEXIST;
 463         }
 464         if (nr_child >= type->max_linear_child) {
 465                 /* No space left in this node type */
 466                 return -ENOSPC;
 467         }
 468         pointers = (struct cds_ja_node_flag **) align_ptr_size(&values[type->max_linear_child]);
 469         assert(pointers[nr_child] == NULL);
 470         rcu_assign_pointer(pointers[nr_child], child_node_flag);
 471         CMM_STORE_SHARED(values[nr_child], n);
 472         cmm_smp_wmb();  /* write value and pointer before nr_child */
 473         CMM_STORE_SHARED(*nr_child_ptr, nr_child + 1);
 474         shadow_node->nr_child++;
 475         return 0;
 476 }
 477
 478 static
 479 int ja_pool_node_set_nth(const struct cds_ja_type *type,
 480                 struct cds_ja_node *node,
 481                 struct cds_ja_shadow_node *shadow_node,
 482                 uint8_t n,
 483                 struct cds_ja_node_flag *child_node_flag)
 484 {
 485         struct cds_ja_node *linear;
 486
 487         assert(type->type_class == RCU_JA_POOL);
 488         linear = (struct cds_ja_node *)
 489                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 490         return ja_linear_node_set_nth(type, linear, shadow_node,
 491                         n, child_node_flag);
 492 }
 493
 494 static
 495 int ja_pigeon_node_set_nth(const struct cds_ja_type *type,
 496                 struct cds_ja_node *node,
 497                 struct cds_ja_shadow_node *shadow_node,
 498                 uint8_t n,
 499                 struct cds_ja_node_flag *child_node_flag)
 500 {
 501         struct cds_ja_node_flag **ptr;
 502
 503         assert(type->type_class == RCU_JA_PIGEON);
 504         ptr = &((struct cds_ja_node_flag **) node->u.data)[n];
 505         if (*ptr != NULL)
 506                 return -EEXIST;
 507         rcu_assign_pointer(*ptr, child_node_flag);
 508         shadow_node->nr_child++;
 509         return 0;
 510 }
 511
 512 /*
 513  * _ja_node_set_nth: set nth item within a node. Return an error
 514  * (negative error value) if it is already there.
 515  * TODO: exclusive access on node.
 516  */
 517 static
 518 int _ja_node_set_nth(const struct cds_ja_type *type,
 519                 struct cds_ja_node *node,
 520                 struct cds_ja_shadow_node *shadow_node,
 521                 uint8_t n,
 522                 struct cds_ja_node_flag *child_node_flag)
 523 {
 524         switch (type->type_class) {
 525         case RCU_JA_LINEAR:
 526                 return ja_linear_node_set_nth(type, node, shadow_node, n,
 527                                 child_node_flag);
 528         case RCU_JA_POOL:
 529                 return ja_pool_node_set_nth(type, node, shadow_node, n,
 530                                 child_node_flag);
 531         case RCU_JA_PIGEON:
 532                 return ja_pigeon_node_set_nth(type, node, shadow_node, n,
 533                                 child_node_flag);
 534         case RCU_JA_NULL:
 535                 return -ENOSPC;
 536         default:
 537                 assert(0);
 538                 return -EINVAL;
 539         }
 540
 541         return 0;
 542 }
 543
 544 /*
 545  * ja_node_recompact_add: recompact a node, adding a new child.
 546  * TODO: for pool type, take selection bit(s) into account.
 547  */
 548 static
 549 int ja_node_recompact_add(struct cds_ja *ja,
 550                 unsigned int old_type_index,
 551                 const struct cds_ja_type *old_type,
 552                 struct cds_ja_node *old_node,
 553                 struct cds_ja_shadow_node **shadow_node,
 554                 struct cds_ja_node_flag **old_node_flag, uint8_t n,
 555                 struct cds_ja_node_flag *child_node_flag)
 556 {
 557         unsigned int new_type_index;
 558         struct cds_ja_node *new_node;
 559         const struct cds_ja_type *new_type;
 560         struct cds_ja_node_flag *new_node_flag;
 561         int ret;
 562
 563         if (*shadow_node == NULL) {
 564                 new_type_index = 0;
 565         } else {
 566                 new_type_index = old_type_index + 1;
 567         }
 568         new_type = &ja_types[new_type_index];
 569         new_node = alloc_cds_ja_node(new_type);
 570         if (!new_node)
 571                 return -ENOMEM;
 572         new_node_flag = ja_node_flag(new_node, new_type_index);
 573
 574         ret = rcuja_shadow_set(ja->ht, new_node, *shadow_node);
 575         if (ret)
 576                 return ret;
 577
 578         if (*shadow_node == NULL) {
 579                 *shadow_node = rcuja_shadow_lookup_lock(ja->ht, new_node);
 580                 assert(*shadow_node);
 581         }
 582
 583         /*
 584          * We need to clear nr_child, because it will be re-incremented
 585          * by _ja_node_set_nth().
 586          */
 587         (*shadow_node)->nr_child = 0;
 588
 589         assert(old_type->type_class != RCU_JA_PIGEON);
 590         switch (old_type->type_class) {
 591         case RCU_JA_LINEAR:
 592         {
 593                 uint8_t nr_child =
 594                         ja_linear_node_get_nr_child(old_type, old_node);
 595                 unsigned int i;
 596
 597                 for (i = 0; i < nr_child; i++) {
 598                         struct cds_ja_node_flag *iter;
 599                         uint8_t v;
 600
 601                         ja_linear_node_get_ith_pos(old_type, old_node, i, &v, &iter);
 602                         if (!iter)
 603                                 continue;
 604                         ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 605                                         v, iter);
 606                         assert(!ret);
 607                 }
 608                 break;
 609         }
 610         case RCU_JA_POOL:
 611         {
 612                 unsigned int pool_nr;
 613
 614                 for (pool_nr = 0; pool_nr < (1U << old_type->nr_pool_order); pool_nr++) {
 615                         struct cds_ja_node *pool =
 616                                 ja_pool_node_get_ith_pool(old_type,
 617                                         old_node, pool_nr);
 618                         uint8_t nr_child =
 619                                 ja_linear_node_get_nr_child(old_type, pool);
 620                         unsigned int j;
 621
 622                         for (j = 0; j < nr_child; j++) {
 623                                 struct cds_ja_node_flag *iter;
 624                                 uint8_t v;
 625
 626                                 ja_linear_node_get_ith_pos(old_type, pool,
 627                                                 j, &v, &iter);
 628                                 if (!iter)
 629                                         continue;
 630                                 ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 631                                                 v, iter);
 632                                 assert(!ret);
 633                         }
 634                 }
 635                 break;
 636         }
 637         case RCU_JA_PIGEON:
 638         default:
 639                 assert(0);
 640                 return -EINVAL;
 641         }
 642
 643         /* add node */
 644         ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 645                         n, child_node_flag);
 646         assert(!ret);
 647         /* Replace the old node with the new recompacted one */
 648         rcu_assign_pointer(*old_node_flag, new_node_flag);
 649         ret = rcuja_shadow_clear(ja->ht, old_node,
 650                         RCUJA_SHADOW_CLEAR_FREE_NODE);
 651         assert(!ret);
 652         return 0;
 653 }
 654
 655 static
 656 int ja_node_set_nth(struct cds_ja *ja,
 657                 struct cds_ja_node_flag **node_flag, uint8_t n,
 658                 struct cds_ja_node_flag *child_node_flag)
 659 {
 660         int ret;
 661         unsigned int type_index;
 662         const struct cds_ja_type *type;
 663         struct cds_ja_node *node;
 664         struct cds_ja_shadow_node *shadow_node = NULL;
 665
 666         node = ja_node_ptr(*node_flag);
 667         type_index = ja_node_type(*node_flag);
 668         type = &ja_types[type_index];
 669         if (node != NULL) {
 670                 shadow_node = rcuja_shadow_lookup_lock(ja->ht, node);
 671                 assert(shadow_node);
 672         }
 673         ret = _ja_node_set_nth(type, node, shadow_node,
 674                         n, child_node_flag);
 675         if (ret == -ENOSPC) {
 676                 /* Not enough space in node, need to recompact. */
 677                 ret = ja_node_recompact_add(ja, type_index, type, node,
 678                                 &shadow_node, node_flag, n, child_node_flag);
 679                 /* recompact always leave shadow_node locked */
 680         }
 681         rcuja_shadow_unlock(shadow_node);
 682         return ret;
 683 }
 684
 685 struct cds_ja *_cds_ja_new(const struct rcu_flavor_struct *flavor)
 686 {
 687         struct cds_ja *ja;
 688
 689         ja = calloc(sizeof(*ja), 1);
 690         if (!ja)
 691                 goto ja_error;
 692         /* ja->root is NULL */
 693         ja->ht = rcuja_create_ht(flavor);
 694         if (!ja->ht)
 695                 goto ht_error;
 696         return ja;
 697
 698 ht_error:
 699         free(ja);
 700 ja_error:
 701         return NULL;
 702 }
 703
 704 /*
 705  * There should be no more concurrent add to the judy array while it is
 706  * being destroyed (ensured by the caller).
 707  */
 708 int cds_ja_destroy(struct cds_ja *ja)
 709 {
 710         rcuja_shadow_prune(ja->ht,
 711                 RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK);
 712         return rcuja_delete_ht(ja->ht);
 713 }