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 static
 300 uint8_t ja_linear_node_get_nr_child(const struct rcu_ja_type *type,
 301                 struct rcu_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 rcu_ja_node_flag *ja_linear_node_get_nth(const struct rcu_ja_type *type,
 314                 struct rcu_ja_node *node,
 315                 uint8_t n)
 316 {
 317         uint8_t nr_child;
 318         uint8_t *values;
 319         struct rcu_ja_node_flag **pointers;
 320         struct rcu_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 rcu_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 rcu_ja_node_flag *ja_linear_node_get_ith_pos(const struct rcu_ja_type *type,
 345                 struct rcu_ja_node *node,
 346                 uint8_t i,
 347                 uint8_t *v,
 348                 struct rcu_ja_node_flag **iter)
 349 {
 350         uint8_t *values;
 351         struct rcu_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 rcu_ja_node_flag **) align_ptr_size(&values[type->max_linear_child]);
 359         *iter = pointers[i];
 360 }
 361
 362 static
 363 struct rcu_ja_node_flag *ja_pool_node_get_nth(const struct rcu_ja_type *type,
 364                 struct rcu_ja_node *node,
 365                 uint8_t n)
 366 {
 367         struct rcu_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 rcu_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 rcu_ja_node *ja_pool_node_get_ith_pool(const struct rcu_ja_type *type,
 381                 struct rcu_ja_node *node,
 382                 uint8_t i)
 383 {
 384         assert(type->type_class == RCU_JA_POOL);
 385         return (struct rcu_ja_node *)
 386                 &node->u.data[(unsigned int) i << type->pool_size_order];
 387 }
 388
 389 static
 390 struct rcu_ja_node_flag *ja_pigeon_node_get_nth(const struct rcu_ja_type *type,
 391                 struct rcu_ja_node *node,
 392                 uint8_t n)
 393 {
 394         assert(type->type_class == RCU_JA_PIGEON);
 395         return rcu_dereference(((struct rcu_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 rcu_ja_node_flag *ja_node_get_nth(struct rcu_ja_node_flag *node_flag,
 404                 uint8_t n)
 405 {
 406         unsigned int type_index;
 407         struct rcu_ja_node *node;
 408         const struct rcu_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 static
 429 unsigned int ja_get_nr_child(struct rcu_ja_shadow_node *shadow_node)
 430 {
 431         return shadow_node->nr_child;
 432 }
 433
 434 static
 435 int ja_linear_node_set_nth(const struct rcu_ja_type *type,
 436                 struct rcu_ja_node *node,
 437                 struct rcu_ja_shadow_node *shadow_node,
 438                 uint8_t n,
 439                 struct rcu_ja_node_flag *child_node_flag)
 440 {
 441         uint8_t nr_child;
 442         uint8_t *values, *nr_child_ptr;
 443         struct rcu_ja_node_flag **pointers;
 444         unsigned int i;
 445
 446         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 447
 448         nr_child_ptr = &node->u.data[0];
 449         nr_child = *nr_child_ptr;
 450         assert(nr_child <= type->max_linear_child);
 451         assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
 452
 453         values = &node->u.data[1];
 454         for (i = 0; i < nr_child; i++) {
 455                 if (values[i] == n)
 456                         return -EEXIST;
 457         }
 458         if (nr_child >= type->max_linear_child) {
 459                 /* No space left in this node type */
 460                 return -ENOSPC;
 461         }
 462         pointers = (struct rcu_ja_node_flag **) align_ptr_size(&values[type->max_linear_child]);
 463         assert(pointers[nr_child] == NULL);
 464         rcu_assign_pointer(pointers[nr_child], child_node_flag);
 465         CMM_STORE_SHARED(values[nr_child], n);
 466         cmm_smp_wmb();  /* write value and pointer before nr_child */
 467         CMM_STORE_SHARED(*nr_child_ptr, nr_child + 1);
 468         shadow_node->nr_child++;
 469         return 0;
 470 }
 471
 472 static
 473 int ja_pool_node_set_nth(const struct rcu_ja_type *type,
 474                 struct rcu_ja_node *node,
 475                 struct rcu_ja_shadow_node *shadow_node,
 476                 uint8_t n,
 477                 struct rcu_ja_node_flag *child_node_flag)
 478 {
 479         struct rcu_ja_node *linear;
 480
 481         assert(type->type_class == RCU_JA_POOL);
 482         linear = (struct rcu_ja_node *)
 483                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 484         return ja_linear_node_set_nth(type, linear, shadow_node,
 485                         n, child_node_flag);
 486 }
 487
 488 static
 489 int ja_pigeon_node_set_nth(const struct rcu_ja_type *type,
 490                 struct rcu_ja_node *node,
 491                 struct rcu_ja_shadow_node *shadow_node,
 492                 uint8_t n,
 493                 struct rcu_ja_node_flag *child_node_flag)
 494 {
 495         struct rcu_ja_node_flag **ptr;
 496
 497         assert(type->type_class == RCU_JA_PIGEON);
 498         ptr = &((struct rcu_ja_node_flag **) node->u.data)[n];
 499         if (*ptr != NULL)
 500                 return -EEXIST;
 501         rcu_assign_pointer(*ptr, child_node_flag);
 502         shadow_node->nr_child++;
 503         return 0;
 504 }
 505
 506 /*
 507  * _ja_node_set_nth: set nth item within a node. Return an error
 508  * (negative error value) if it is already there.
 509  * TODO: exclusive access on node.
 510  */
 511 static
 512 int _ja_node_set_nth(const struct rcu_ja_type *type,
 513                 struct rcu_ja_node *node,
 514                 struct rcu_ja_shadow_node *shadow_node,
 515                 uint8_t n,
 516                 struct rcu_ja_node_flag *child_node_flag)
 517 {
 518         switch (type->type_class) {
 519         case RCU_JA_LINEAR:
 520                 return ja_linear_node_set_nth(type, node, shadow_node, n,
 521                                 child_node_flag);
 522         case RCU_JA_POOL:
 523                 return ja_pool_node_set_nth(type, node, shadow_node, n,
 524                                 child_node_flag);
 525         case RCU_JA_PIGEON:
 526                 return ja_pigeon_node_set_nth(type, node, shadow_node, n,
 527                                 child_node_flag);
 528         case RCU_JA_NULL:
 529                 return -ENOSPC;
 530         default:
 531                 assert(0);
 532                 return -EINVAL;
 533         }
 534
 535         return 0;
 536 }
 537
 538 /*
 539  * ja_node_recompact_add: recompact a node, adding a new child.
 540  * TODO: for pool type, take selection bit(s) into account.
 541  */
 542 static
 543 int ja_node_recompact_add(struct rcu_ja *ja,
 544                 unsigned int old_type_index,
 545                 const struct rcu_ja_type *old_type,
 546                 struct rcu_ja_node *old_node,
 547                 struct rcu_ja_shadow_node **shadow_node,
 548                 struct rcu_ja_node_flag **old_node_flag, uint8_t n,
 549                 struct rcu_ja_node_flag *child_node_flag)
 550 {
 551         unsigned int new_type_index;
 552         struct rcu_ja_node *new_node;
 553         const struct rcu_ja_type *new_type;
 554         struct rcu_ja_node_flag *new_node_flag;
 555         int ret;
 556
 557         if (*shadow_node == NULL) {
 558                 new_type_index = 0;
 559         } else {
 560                 new_type_index = old_type_index + 1;
 561         }
 562         new_type = &ja_types[new_type_index];
 563         new_node = alloc_rcu_ja_node(new_type);
 564         if (!new_node)
 565                 return -ENOMEM;
 566         new_node_flag = ja_node_flag(new_node, new_type_index);
 567
 568         ret = rcuja_shadow_set(ja->ht, new_node, *shadow_node);
 569         if (ret)
 570                 return ret;
 571
 572         if (*shadow_node == NULL) {
 573                 *shadow_node = rcuja_shadow_lookup_lock(ja->ht, new_node);
 574                 assert(*shadow_node);
 575         }
 576
 577         /*
 578          * We need to clear nr_child, because it will be re-incremented
 579          * by _ja_node_set_nth().
 580          */
 581         (*shadow_node)->nr_child = 0;
 582
 583         assert(old_type->type_class != RCU_JA_PIGEON);
 584         switch (old_type->type_class) {
 585         case RCU_JA_LINEAR:
 586         {
 587                 uint8_t nr_child =
 588                         ja_linear_node_get_nr_child(old_type, old_node);
 589                 unsigned int i;
 590
 591                 for (i = 0; i < nr_child; i++) {
 592                         struct rcu_ja_node_flag *iter;
 593                         uint8_t v;
 594
 595                         ja_linear_node_get_ith_pos(old_type, old_node, i, &v, &iter);
 596                         if (!iter)
 597                                 continue;
 598                         ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 599                                         v, iter);
 600                         assert(!ret);
 601                 }
 602                 break;
 603         }
 604         case RCU_JA_POOL:
 605         {
 606                 unsigned int pool_nr;
 607
 608                 for (pool_nr = 0; pool_nr < (1U << old_type->nr_pool_order); pool_nr++) {
 609                         struct rcu_ja_node *pool =
 610                                 ja_pool_node_get_ith_pool(old_type,
 611                                         old_node, pool_nr);
 612                         uint8_t nr_child =
 613                                 ja_linear_node_get_nr_child(old_type, pool);
 614                         unsigned int j;
 615
 616                         for (j = 0; j < nr_child; j++) {
 617                                 struct rcu_ja_node_flag *iter;
 618                                 uint8_t v;
 619
 620                                 ja_linear_node_get_ith_pos(old_type, pool,
 621                                                 j, &v, &iter);
 622                                 if (!iter)
 623                                         continue;
 624                                 ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 625                                                 v, iter);
 626                                 assert(!ret);
 627                         }
 628                 }
 629                 break;
 630         }
 631         case RCU_JA_PIGEON:
 632         default:
 633                 assert(0);
 634                 return -EINVAL;
 635         }
 636
 637         /* add node */
 638         ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
 639                         n, child_node_flag);
 640         assert(!ret);
 641         /* Replace the old node with the new recompacted one */
 642         rcu_assign_pointer(*old_node_flag, new_node_flag);
 643         ret = rcuja_shadow_clear(ja->ht, old_node,
 644                         RCUJA_SHADOW_CLEAR_FREE_NODE);
 645         assert(!ret);
 646         return 0;
 647 }
 648
 649 static
 650 int ja_node_set_nth(struct rcu_ja *ja,
 651                 struct rcu_ja_node_flag **node_flag, uint8_t n,
 652                 struct rcu_ja_node_flag *child_node_flag)
 653 {
 654         int ret;
 655         unsigned int type_index;
 656         const struct rcu_ja_type *type;
 657         struct rcu_ja_node *node;
 658         struct rcu_ja_shadow_node *shadow_node = NULL;
 659
 660         node = ja_node_ptr(*node_flag);
 661         type_index = ja_node_type(*node_flag);
 662         type = &ja_types[type_index];
 663         if (node != NULL) {
 664                 shadow_node = rcuja_shadow_lookup_lock(ja->ht, node);
 665                 assert(shadow_node);
 666         }
 667         ret = _ja_node_set_nth(type, node, shadow_node,
 668                         n, child_node_flag);
 669         if (ret == -ENOSPC) {
 670                 /* Not enough space in node, need to recompact. */
 671                 ret = ja_node_recompact_add(ja, type_index, type, node,
 672                                 &shadow_node, node_flag, n, child_node_flag);
 673                 /* recompact always leave shadow_node locked */
 674         }
 675         rcuja_shadow_unlock(shadow_node);
 676         return ret;
 677 }