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 rcu_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 rcu_ja_type {
  53         enum rcu_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 rcu_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 rcu_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 rcu_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 rcu_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 rcu_ja_node_flag *child_ptr[ja_type_## index ##_max_linear_child]; \
 226                 } linear[1U << ja_type_## index ##_nr_pool_order];                              \
 227         }
 228
 229 struct rcu_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 rcu_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 rcu_ja_node_flag *) * ja_type_7_max_child];
 248         } u;
 249 };
 250
 251 static
 252 struct rcu_ja_node_flag *ja_node_flag(struct rcu_ja_node *node,
 253                 unsigned int type)
 254 {
 255         assert(type < RCU_JA_NR_TYPES);
 256         return (struct rcu_ja_node_flag *) (((unsigned long) node) | type);
 257 }
 258
 259 static
 260 struct rcu_ja_node *ja_node_ptr(struct rcu_ja_node_flag *node)
 261 {
 262         return (struct rcu_ja_node *) (((unsigned long) node) | JA_PTR_MASK);
 263 }
 264
 265 static
 266 unsigned int ja_node_type(struct rcu_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 rcu_ja_node *alloc_rcu_ja_node(const struct rcu_ja_type *ja_type)
 279 {
 280         return calloc(1U << ja_type->order, sizeof(char));
 281 }
 282
 283 void free_rcu_ja_node(struct rcu_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 /*
 300  * The order in which values and pointers are does does not matter: if
 301  * a value is missing, we return NULL. If a value is there, but its
 302  * associated pointers is still NULL, we return NULL too.
 303  */
 304 static
 305 struct rcu_ja_node_flag *ja_linear_node_get_nth(const struct rcu_ja_type *type,
 306                 struct rcu_ja_node *node,
 307                 uint8_t n)
 308 {
 309         uint8_t nr_child;
 310         uint8_t *values;
 311         struct rcu_ja_node_flag **pointers;
 312         struct rcu_ja_node_flag *ptr;
 313         unsigned int i;
 314
 315         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 316
 317         nr_child = CMM_LOAD_SHARED(node->u.data[0]);
 318         cmm_smp_rmb();  /* read nr_child before values and pointers */
 319         assert(nr_child <= type->max_linear_child);
 320         assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
 321
 322         values = &node->u.data[1];
 323         for (i = 0; i < nr_child; i++) {
 324                 if (CMM_LOAD_SHARED(values[i]) == n)
 325                         break;
 326         }
 327         if (i >= nr_child)
 328                 return NULL;
 329         pointers = (struct rcu_ja_node_flag **) align_ptr_size(&values[type->max_linear_child]);
 330         ptr = rcu_dereference(pointers[i]);
 331         assert(ja_node_ptr(ptr) != NULL);
 332         return ptr;
 333 }
 334
 335 static
 336 struct rcu_ja_node_flag *ja_pool_node_get_nth(const struct rcu_ja_type *type,
 337                 struct rcu_ja_node *node,
 338                 uint8_t n)
 339 {
 340         struct rcu_ja_node *linear;
 341
 342         assert(type->type_class == RCU_JA_POOL);
 343         /*
 344          * TODO: currently, we select the pool by highest bits. We
 345          * should support various encodings.
 346          */
 347         linear = (struct rcu_ja_node *)
 348                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 349         return ja_linear_node_get_nth(type, linear, n);
 350 }
 351
 352 static
 353 struct rcu_ja_node_flag *ja_pigeon_node_get_nth(const struct rcu_ja_type *type,
 354                 struct rcu_ja_node *node,
 355                 uint8_t n)
 356 {
 357         assert(type->type_class == RCU_JA_PIGEON);
 358         return rcu_dereference(((struct rcu_ja_node_flag **) node->u.data)[n]);
 359 }
 360
 361 /*
 362  * ja_node_get_nth: get nth item from a node.
 363  * node_flag is already rcu_dereference'd.
 364  */
 365 static
 366 struct rcu_ja_node_flag *ja_node_get_nth(struct rcu_ja_node_flag *node_flag,
 367                 uint8_t n)
 368 {
 369         unsigned int type_index;
 370         struct rcu_ja_node *node;
 371         const struct rcu_ja_type *type;
 372
 373         node = ja_node_ptr(node_flag);
 374         assert(node != NULL);
 375         type_index = ja_node_type(node_flag);
 376         type = &ja_types[type_index];
 377
 378         switch (type->type_class) {
 379         case RCU_JA_LINEAR:
 380                 return ja_linear_node_get_nth(type, node, n);
 381         case RCU_JA_POOL:
 382                 return ja_pool_node_get_nth(type, node, n);
 383         case RCU_JA_PIGEON:
 384                 return ja_pigeon_node_get_nth(type, node, n);
 385         default:
 386                 assert(0);
 387                 return (void *) -1UL;
 388         }
 389 }
 390
 391 static
 392 unsigned int ja_get_nr_child(struct rcu_ja_shadow_node *shadow_node)
 393 {
 394         return shadow_node->nr_child;
 395 }
 396
 397 static
 398 int ja_linear_node_set_nth(const struct rcu_ja_type *type,
 399                 struct rcu_ja_node *node,
 400                 struct rcu_ja_shadow_node *shadow_node,
 401                 uint8_t n,
 402                 struct rcu_ja_node_flag *child_node_flag)
 403 {
 404         uint8_t nr_child;
 405         uint8_t *values, *nr_child_ptr;
 406         struct rcu_ja_node_flag **pointers;
 407         unsigned int i;
 408
 409         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 410
 411         nr_child_ptr = &node->u.data[0];
 412         nr_child = *nr_child_ptr;
 413         assert(nr_child <= type->max_linear_child);
 414         assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
 415
 416         values = &node->u.data[1];
 417         for (i = 0; i < nr_child; i++) {
 418                 if (values[i] == n)
 419                         return -EEXIST;
 420         }
 421         if (nr_child >= type->max_linear_child) {
 422                 /* No space left in this node type */
 423                 return -ENOSPC;
 424         }
 425         pointers = (struct rcu_ja_node_flag **) align_ptr_size(&values[type->max_linear_child]);
 426         assert(pointers[nr_child] == NULL);
 427         rcu_assign_pointer(pointers[nr_child], child_node_flag);
 428         CMM_STORE_SHARED(values[nr_child], n);
 429         cmm_smp_wmb();  /* write value and pointer before nr_child */
 430         CMM_STORE_SHARED(*nr_child_ptr, nr_child + 1);
 431         shadow_node->nr_child++;
 432         return 0;
 433 }
 434
 435 static
 436 int ja_pool_node_set_nth(const struct rcu_ja_type *type,
 437                 struct rcu_ja_node *node,
 438                 struct rcu_ja_shadow_node *shadow_node,
 439                 uint8_t n,
 440                 struct rcu_ja_node_flag *child_node_flag)
 441 {
 442         struct rcu_ja_node *linear;
 443
 444         assert(type->type_class == RCU_JA_POOL);
 445         linear = (struct rcu_ja_node *)
 446                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 447         return ja_linear_node_set_nth(type, linear, shadow_node,
 448                         n, child_node_flag);
 449 }
 450
 451 static
 452 int ja_pigeon_node_set_nth(const struct rcu_ja_type *type,
 453                 struct rcu_ja_node *node,
 454                 struct rcu_ja_shadow_node *shadow_node,
 455                 uint8_t n,
 456                 struct rcu_ja_node_flag *child_node_flag)
 457 {
 458         struct rcu_ja_node_flag **ptr;
 459
 460         assert(type->type_class == RCU_JA_PIGEON);
 461         ptr = &((struct rcu_ja_node_flag **) node->u.data)[n];
 462         if (*ptr != NULL)
 463                 return -EEXIST;
 464         rcu_assign_pointer(*ptr, child_node_flag);
 465         shadow_node->nr_child++;
 466         return 0;
 467 }
 468
 469 /*
 470  * _ja_node_set_nth: set nth item within a node. Return an error
 471  * (negative error value) if it is already there.
 472  * TODO: exclusive access on node.
 473  */
 474 static
 475 int _ja_node_set_nth(const struct rcu_ja_type *type,
 476                 struct rcu_ja_node *node,
 477                 struct rcu_ja_shadow_node *shadow_node,
 478                 uint8_t n,
 479                 struct rcu_ja_node_flag *child_node_flag)
 480 {
 481         switch (type->type_class) {
 482         case RCU_JA_LINEAR:
 483                 return ja_linear_node_set_nth(type, node, shadow_node, n,
 484                                 child_node_flag);
 485         case RCU_JA_POOL:
 486                 return ja_pool_node_set_nth(type, node, shadow_node, n,
 487                                 child_node_flag);
 488         case RCU_JA_PIGEON:
 489                 return ja_pigeon_node_set_nth(type, node, shadow_node, n,
 490                                 child_node_flag);
 491         case RCU_JA_NULL:
 492                 return -ENOSPC;
 493         default:
 494                 assert(0);
 495                 return -EINVAL;
 496         }
 497
 498         return 0;
 499 }
 500
 501 /*
 502  * ja_node_recompact_add: recompact a node, adding a new child.
 503  * TODO: for pool type, take selection bit(s) into account.
 504  */
 505 static
 506 int ja_node_recompact_add(struct rcu_ja *ja,
 507                 unsigned int old_type_index,
 508                 const struct rcu_ja_type *old_type,
 509                 struct rcu_ja_node *old_node,
 510                 struct rcu_ja_shadow_node **shadow_node,
 511                 struct rcu_ja_node_flag **old_node_flag, uint8_t n,
 512                 struct rcu_ja_node_flag *child_node_flag)
 513 {
 514         unsigned int new_type_index;
 515         struct rcu_ja_node *new_node;
 516         const struct rcu_ja_type *new_type;
 517         struct rcu_ja_node_flag *new_node_flag;
 518         unsigned int i;
 519         int ret;
 520
 521         if (*shadow_node == NULL) {
 522                 new_type_index = 0;
 523         } else {
 524                 new_type_index = old_type_index + 1;
 525         }
 526         new_type = &ja_types[new_type_index];
 527         new_node = alloc_rcu_ja_node(new_type);
 528         if (!new_node)
 529                 return -ENOMEM;
 530         new_node_flag = ja_node_flag(new_node, new_type_index);
 531
 532         ret = rcuja_shadow_set(ja->ht, new_node, *shadow_node);
 533         if (ret)
 534                 return ret;
 535
 536         if (*shadow_node == NULL) {
 537                 *shadow_node = rcuja_shadow_lookup_lock(ja->ht, new_node);
 538                 assert(*shadow_node);
 539         }
 540
 541         (*shadow_node)->nr_child = 0;
 542         for (i = 0; i < old_type->max_child; i++) {
 543                 struct rcu_ja_node_flag *iter;
 544
 545                 iter = ja_node_get_nth(*old_node_flag, i);
 546                 if (!iter)
 547                         continue;
 548                 ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 549                                 i, iter);
 550                 assert(!ret);
 551         }
 552         /* add node */
 553         ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 554                         n, child_node_flag);
 555         assert(!ret);
 556         /* Replace the old node with the new recompacted one */
 557         rcu_assign_pointer(*old_node_flag, new_node_flag);
 558         ret = rcuja_shadow_clear(ja->ht, old_node,
 559                         RCUJA_SHADOW_CLEAR_FREE_NODE);
 560         assert(!ret);
 561         return 0;
 562 }
 563
 564 static
 565 int ja_node_set_nth(struct rcu_ja *ja,
 566                 struct rcu_ja_node_flag **node_flag, uint8_t n,
 567                 struct rcu_ja_node_flag *child_node_flag)
 568 {
 569         int ret;
 570         unsigned int type_index;
 571         const struct rcu_ja_type *type;
 572         struct rcu_ja_node *node;
 573         struct rcu_ja_shadow_node *shadow_node = NULL;
 574
 575         node = ja_node_ptr(*node_flag);
 576         type_index = ja_node_type(*node_flag);
 577         type = &ja_types[type_index];
 578         if (node != NULL) {
 579                 shadow_node = rcuja_shadow_lookup_lock(ja->ht, node);
 580                 assert(shadow_node);
 581         }
 582         ret = _ja_node_set_nth(type, node, shadow_node,
 583                         n, child_node_flag);
 584         if (ret == -ENOSPC) {
 585                 /* Not enough space in node, need to recompact. */
 586                 ret = ja_node_recompact_add(ja, type_index, type, node,
 587                                 &shadow_node, node_flag, n, child_node_flag);
 588                 /* recompact always leave shadow_node locked */
 589         }
 590         rcuja_shadow_unlock(shadow_node);
 591         return ret;
 592 }