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 #include <stdint.h>
  33
  34 #include "rcuja-internal.h"
  35 #include "bitfield.h"
  36
  37 enum cds_ja_type_class {
  38         RCU_JA_LINEAR = 0,      /* Type A */
  39                         /* 32-bit: 1 to 25 children, 8 to 128 bytes */
  40                         /* 64-bit: 1 to 28 children, 16 to 256 bytes */
  41         RCU_JA_POOL = 1,        /* Type B */
  42                         /* 32-bit: 26 to 100 children, 256 to 512 bytes */
  43                         /* 64-bit: 29 to 112 children, 512 to 1024 bytes */
  44         RCU_JA_PIGEON = 2,      /* Type C */
  45                         /* 32-bit: 101 to 256 children, 1024 bytes */
  46                         /* 64-bit: 113 to 256 children, 2048 bytes */
  47         /* Leaf nodes are implicit from their height in the tree */
  48         RCU_JA_NR_TYPES,
  49
  50         RCU_JA_NULL,    /* not an encoded type, but keeps code regular */
  51 };
  52
  53 struct cds_ja_type {
  54         enum cds_ja_type_class type_class;
  55         uint16_t min_child;             /* minimum number of children: 1 to 256 */
  56         uint16_t max_child;             /* maximum number of children: 1 to 256 */
  57         uint16_t max_linear_child;      /* per-pool max nr. children: 1 to 256 */
  58         uint16_t order;                 /* node size is (1 << order), in bytes */
  59         uint16_t nr_pool_order;         /* number of pools */
  60         uint16_t pool_size_order;       /* pool size */
  61 };
  62
  63 /*
  64  * Number of least significant pointer bits reserved to represent the
  65  * child type.
  66  */
  67 #define JA_TYPE_BITS    3
  68 #define JA_TYPE_MAX_NR  (1UL << JA_TYPE_BITS)
  69 #define JA_TYPE_MASK    (JA_TYPE_MAX_NR - 1)
  70 #define JA_PTR_MASK     (~JA_TYPE_MASK)
  71
  72 #define JA_ENTRY_PER_NODE       256UL
  73 #define JA_BITS_PER_BYTE        3
  74
  75 #define JA_MAX_DEPTH    5       /* Maximum depth, including leafs */
  76
  77 /*
  78  * Entry for NULL node is at index 8 of the table. It is never encoded
  79  * in flags.
  80  */
  81 #define NODE_INDEX_NULL         8
  82
  83 /*
  84  * Iteration on the array to find the right node size for the number of
  85  * children stops when it reaches .max_child == 256 (this is the largest
  86  * possible node size, which contains 256 children).
  87  * The min_child overlaps with the previous max_child to provide an
  88  * hysteresis loop to reallocation for patterns of cyclic add/removal
  89  * within the same node.
  90  * The node the index within the following arrays is represented on 3
  91  * bits. It identifies the node type, min/max number of children, and
  92  * the size order.
  93  * The max_child values for the RCU_JA_POOL below result from
  94  * statistical approximation: over million populations, the max_child
  95  * covers between 97% and 99% of the populations generated. Therefore, a
  96  * fallback should exist to cover the rare extreme population unbalance
  97  * cases, but it will not have a major impact on speed nor space
  98  * consumption, since those are rare cases.
  99  */
 100
 101 #if (CAA_BITS_PER_LONG < 64)
 102 /* 32-bit pointers */
 103 enum {
 104         ja_type_0_max_child = 1,
 105         ja_type_1_max_child = 3,
 106         ja_type_2_max_child = 6,
 107         ja_type_3_max_child = 12,
 108         ja_type_4_max_child = 25,
 109         ja_type_5_max_child = 48,
 110         ja_type_6_max_child = 92,
 111         ja_type_7_max_child = 256,
 112         ja_type_8_max_child = 0,        /* NULL */
 113 };
 114
 115 enum {
 116         ja_type_0_max_linear_child = 1,
 117         ja_type_1_max_linear_child = 3,
 118         ja_type_2_max_linear_child = 6,
 119         ja_type_3_max_linear_child = 12,
 120         ja_type_4_max_linear_child = 25,
 121         ja_type_5_max_linear_child = 24,
 122         ja_type_6_max_linear_child = 23,
 123 };
 124
 125 enum {
 126         ja_type_5_nr_pool_order = 1,
 127         ja_type_6_nr_pool_order = 2,
 128 };
 129
 130 const struct cds_ja_type ja_types[] = {
 131         { .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, },
 132         { .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, },
 133         { .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, },
 134         { .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, },
 135         { .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, },
 136
 137         /* Pools may fill sooner than max_child */
 138         { .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, },
 139         { .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, },
 140
 141         /*
 142          * TODO: Upon node removal below min_child, if child pool is
 143          * filled beyond capacity, we need to roll back to pigeon.
 144          */
 145         { .type_class = RCU_JA_PIGEON, .min_child = 89, .max_child = ja_type_7_max_child, .order = 10, },
 146
 147         { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, },
 148 };
 149 #else /* !(CAA_BITS_PER_LONG < 64) */
 150 /* 64-bit pointers */
 151 enum {
 152         ja_type_0_max_child = 1,
 153         ja_type_1_max_child = 3,
 154         ja_type_2_max_child = 7,
 155         ja_type_3_max_child = 14,
 156         ja_type_4_max_child = 28,
 157         ja_type_5_max_child = 54,
 158         ja_type_6_max_child = 104,
 159         ja_type_7_max_child = 256,
 160         ja_type_8_max_child = 256,
 161 };
 162
 163 enum {
 164         ja_type_0_max_linear_child = 1,
 165         ja_type_1_max_linear_child = 3,
 166         ja_type_2_max_linear_child = 7,
 167         ja_type_3_max_linear_child = 14,
 168         ja_type_4_max_linear_child = 28,
 169         ja_type_5_max_linear_child = 27,
 170         ja_type_6_max_linear_child = 26,
 171 };
 172
 173 enum {
 174         ja_type_5_nr_pool_order = 1,
 175         ja_type_6_nr_pool_order = 2,
 176 };
 177
 178 const struct cds_ja_type ja_types[] = {
 179         { .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, },
 180         { .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, },
 181         { .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, },
 182         { .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, },
 183         { .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, },
 184
 185         /* Pools may fill sooner than max_child. */
 186         { .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, },
 187         { .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, },
 188
 189         /*
 190          * TODO: Upon node removal below min_child, if child pool is
 191          * filled beyond capacity, we need to roll back to pigeon.
 192          */
 193         { .type_class = RCU_JA_PIGEON, .min_child = 101, .max_child = ja_type_7_max_child, .order = 11, },
 194
 195         { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, },
 196 };
 197 #endif /* !(BITS_PER_LONG < 64) */
 198
 199 static inline __attribute__((unused))
 200 void static_array_size_check(void)
 201 {
 202         CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) < JA_TYPE_MAX_NR);
 203 }
 204
 205 /*
 206  * The cds_ja_node contains the compressed node data needed for
 207  * read-side. For linear and pool node configurations, it starts with a
 208  * byte counting the number of children in the node.  Then, the
 209  * node-specific data is placed.
 210  * The node mutex, if any is needed, protecting concurrent updated of
 211  * each node is placed in a separate hash table indexed by node address.
 212  * For the pigeon configuration, the number of children is also kept in
 213  * a separate hash table, indexed by node address, because it is only
 214  * required for updates.
 215  */
 216
 217 #define DECLARE_LINEAR_NODE(index)                                                              \
 218         struct {                                                                                \
 219                 uint8_t nr_child;                                                               \
 220                 uint8_t child_value[ja_type_## index ##_max_linear_child];                      \
 221                 struct cds_ja_inode_flag *child_ptr[ja_type_## index ##_max_linear_child];      \
 222         }
 223
 224 #define DECLARE_POOL_NODE(index)                                                                \
 225         struct {                                                                                \
 226                 struct {                                                                        \
 227                         uint8_t nr_child;                                                       \
 228                         uint8_t child_value[ja_type_## index ##_max_linear_child];              \
 229                         struct cds_ja_inode_flag *child_ptr[ja_type_## index ##_max_linear_child]; \
 230                 } linear[1U << ja_type_## index ##_nr_pool_order];                              \
 231         }
 232
 233 struct cds_ja_inode {
 234         union {
 235                 /* Linear configuration */
 236                 DECLARE_LINEAR_NODE(0) conf_0;
 237                 DECLARE_LINEAR_NODE(1) conf_1;
 238                 DECLARE_LINEAR_NODE(2) conf_2;
 239                 DECLARE_LINEAR_NODE(3) conf_3;
 240                 DECLARE_LINEAR_NODE(4) conf_4;
 241
 242                 /* Pool configuration */
 243                 DECLARE_POOL_NODE(5) conf_5;
 244                 DECLARE_POOL_NODE(6) conf_6;
 245
 246                 /* Pigeon configuration */
 247                 struct {
 248                         struct cds_ja_inode_flag *child[ja_type_7_max_child];
 249                 } conf_7;
 250                 /* data aliasing nodes for computed accesses */
 251                 uint8_t data[sizeof(struct cds_ja_inode_flag *) * ja_type_7_max_child];
 252         } u;
 253 };
 254
 255 static
 256 struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node,
 257                 unsigned long type)
 258 {
 259         assert(type < (1UL << JA_TYPE_BITS));
 260         return (struct cds_ja_inode_flag *) (((unsigned long) node) | type);
 261 }
 262
 263 static
 264 struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node)
 265 {
 266         return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK);
 267 }
 268
 269 static
 270 unsigned long ja_node_type(struct cds_ja_inode_flag *node)
 271 {
 272         unsigned long type;
 273
 274         if (ja_node_ptr(node) == NULL) {
 275                 return NODE_INDEX_NULL;
 276         }
 277         type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
 278         assert(type < (1UL << JA_TYPE_BITS));
 279         return type;
 280 }
 281
 282 struct cds_ja_inode *alloc_cds_ja_node(const struct cds_ja_type *ja_type)
 283 {
 284         return calloc(1U << ja_type->order, sizeof(char));
 285 }
 286
 287 void free_cds_ja_node(struct cds_ja_inode *node)
 288 {
 289         free(node);
 290 }
 291
 292 #define __JA_ALIGN_MASK(v, mask)        (((v) + (mask)) & ~(mask))
 293 #define JA_ALIGN(v, align)              __JA_ALIGN_MASK(v, (typeof(v)) (align) - 1)
 294 #define __JA_FLOOR_MASK(v, mask)        ((v) & ~(mask))
 295 #define JA_FLOOR(v, align)              __JA_FLOOR_MASK(v, (typeof(v)) (align) - 1)
 296
 297 static
 298 uint8_t *align_ptr_size(uint8_t *ptr)
 299 {
 300         return (uint8_t *) JA_ALIGN((unsigned long) ptr, sizeof(void *));
 301 }
 302
 303 static
 304 uint8_t ja_linear_node_get_nr_child(const struct cds_ja_type *type,
 305                 struct cds_ja_inode *node)
 306 {
 307         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 308         return CMM_LOAD_SHARED(node->u.data[0]);
 309 }
 310
 311 /*
 312  * The order in which values and pointers are does does not matter: if
 313  * a value is missing, we return NULL. If a value is there, but its
 314  * associated pointers is still NULL, we return NULL too.
 315  */
 316 static
 317 struct cds_ja_inode_flag *ja_linear_node_get_nth(const struct cds_ja_type *type,
 318                 struct cds_ja_inode *node,
 319                 struct cds_ja_inode_flag ***child_node_flag_ptr,
 320                 uint8_t n)
 321 {
 322         uint8_t nr_child;
 323         uint8_t *values;
 324         struct cds_ja_inode_flag **pointers;
 325         struct cds_ja_inode_flag *ptr;
 326         unsigned int i;
 327
 328         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 329
 330         nr_child = ja_linear_node_get_nr_child(type, node);
 331         cmm_smp_rmb();  /* read nr_child before values and pointers */
 332         assert(nr_child <= type->max_linear_child);
 333         assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child);
 334
 335         values = &node->u.data[1];
 336         for (i = 0; i < nr_child; i++) {
 337                 if (CMM_LOAD_SHARED(values[i]) == n)
 338                         break;
 339         }
 340         if (i >= nr_child)
 341                 return NULL;
 342         pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
 343         if (caa_unlikely(child_node_flag_ptr))
 344                 *child_node_flag_ptr = &pointers[i];
 345         ptr = rcu_dereference(pointers[i]);
 346         assert(ja_node_ptr(ptr) != NULL);
 347         return ptr;
 348 }
 349
 350 static
 351 void ja_linear_node_get_ith_pos(const struct cds_ja_type *type,
 352                 struct cds_ja_inode *node,
 353                 uint8_t i,
 354                 uint8_t *v,
 355                 struct cds_ja_inode_flag **iter)
 356 {
 357         uint8_t *values;
 358         struct cds_ja_inode_flag **pointers;
 359
 360         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 361         assert(i < ja_linear_node_get_nr_child(type, node));
 362
 363         values = &node->u.data[1];
 364         *v = values[i];
 365         pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
 366         *iter = pointers[i];
 367 }
 368
 369 static
 370 struct cds_ja_inode_flag *ja_pool_node_get_nth(const struct cds_ja_type *type,
 371                 struct cds_ja_inode *node,
 372                 struct cds_ja_inode_flag ***child_node_flag_ptr,
 373                 uint8_t n)
 374 {
 375         struct cds_ja_inode *linear;
 376
 377         assert(type->type_class == RCU_JA_POOL);
 378         /*
 379          * TODO: currently, we select the pool by highest bits. We
 380          * should support various encodings.
 381          */
 382         linear = (struct cds_ja_inode *)
 383                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 384         return ja_linear_node_get_nth(type, linear, child_node_flag_ptr, n);
 385 }
 386
 387 static
 388 struct cds_ja_inode *ja_pool_node_get_ith_pool(const struct cds_ja_type *type,
 389                 struct cds_ja_inode *node,
 390                 uint8_t i)
 391 {
 392         assert(type->type_class == RCU_JA_POOL);
 393         return (struct cds_ja_inode *)
 394                 &node->u.data[(unsigned int) i << type->pool_size_order];
 395 }
 396
 397 static
 398 struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type,
 399                 struct cds_ja_inode *node,
 400                 struct cds_ja_inode_flag ***child_node_flag_ptr,
 401                 uint8_t n)
 402 {
 403         struct cds_ja_inode_flag **child_node_flag;
 404
 405         assert(type->type_class == RCU_JA_PIGEON);
 406         child_node_flag = &((struct cds_ja_inode_flag **) node->u.data)[n];
 407         if (caa_unlikely(child_node_flag_ptr))
 408                 *child_node_flag_ptr = child_node_flag;
 409         return rcu_dereference(*child_node_flag);
 410 }
 411
 412 /*
 413  * ja_node_get_nth: get nth item from a node.
 414  * node_flag is already rcu_dereference'd.
 415  */
 416 static
 417 struct cds_ja_inode_flag * ja_node_get_nth(struct cds_ja_inode_flag *node_flag,
 418                 struct cds_ja_inode_flag ***child_node_flag_ptr,
 419                 uint8_t n)
 420 {
 421         unsigned int type_index;
 422         struct cds_ja_inode *node;
 423         const struct cds_ja_type *type;
 424
 425         node = ja_node_ptr(node_flag);
 426         assert(node != NULL);
 427         type_index = ja_node_type(node_flag);
 428         type = &ja_types[type_index];
 429
 430         switch (type->type_class) {
 431         case RCU_JA_LINEAR:
 432                 return ja_linear_node_get_nth(type, node,
 433                                 child_node_flag_ptr, n);
 434         case RCU_JA_POOL:
 435                 return ja_pool_node_get_nth(type, node,
 436                                 child_node_flag_ptr, n);
 437         case RCU_JA_PIGEON:
 438                 return ja_pigeon_node_get_nth(type, node,
 439                                 child_node_flag_ptr, n);
 440         default:
 441                 assert(0);
 442                 return (void *) -1UL;
 443         }
 444 }
 445
 446 /*
 447  * TODO: use ja_get_nr_child to monitor limits triggering shrink
 448  * recompaction.
 449  * Also use ja_get_nr_child to make the difference between resize and
 450  * pool change of compaction bit(s).
 451  */
 452 static
 453 unsigned int ja_get_nr_child(struct cds_ja_shadow_node *shadow_node)
 454 {
 455         return shadow_node->nr_child;
 456 }
 457
 458 static
 459 int ja_linear_node_set_nth(const struct cds_ja_type *type,
 460                 struct cds_ja_inode *node,
 461                 struct cds_ja_shadow_node *shadow_node,
 462                 uint8_t n,
 463                 struct cds_ja_inode_flag *child_node_flag)
 464 {
 465         uint8_t nr_child;
 466         uint8_t *values, *nr_child_ptr;
 467         struct cds_ja_inode_flag **pointers;
 468         unsigned int i;
 469
 470         assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL);
 471
 472         nr_child_ptr = &node->u.data[0];
 473         dbg_printf("linear set nth: nr_child_ptr %p\n", nr_child_ptr);
 474         nr_child = *nr_child_ptr;
 475         assert(nr_child <= type->max_linear_child);
 476
 477         values = &node->u.data[1];
 478         for (i = 0; i < nr_child; i++) {
 479                 if (values[i] == n)
 480                         return -EEXIST;
 481         }
 482         if (nr_child >= type->max_linear_child) {
 483                 /* No space left in this node type */
 484                 return -ENOSPC;
 485         }
 486         pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]);
 487         assert(pointers[nr_child] == NULL);
 488         rcu_assign_pointer(pointers[nr_child], child_node_flag);
 489         CMM_STORE_SHARED(values[nr_child], n);
 490         cmm_smp_wmb();  /* write value and pointer before nr_child */
 491         CMM_STORE_SHARED(*nr_child_ptr, nr_child + 1);
 492         shadow_node->nr_child++;
 493         dbg_printf("linear set nth: %u child, shadow: %u child, for node %p shadow %p\n",
 494                 (unsigned int) CMM_LOAD_SHARED(*nr_child_ptr),
 495                 (unsigned int) shadow_node->nr_child,
 496                 node, shadow_node);
 497
 498         return 0;
 499 }
 500
 501 static
 502 int ja_pool_node_set_nth(const struct cds_ja_type *type,
 503                 struct cds_ja_inode *node,
 504                 struct cds_ja_shadow_node *shadow_node,
 505                 uint8_t n,
 506                 struct cds_ja_inode_flag *child_node_flag)
 507 {
 508         struct cds_ja_inode *linear;
 509
 510         assert(type->type_class == RCU_JA_POOL);
 511         linear = (struct cds_ja_inode *)
 512                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 513         return ja_linear_node_set_nth(type, linear, shadow_node,
 514                         n, child_node_flag);
 515 }
 516
 517 static
 518 int ja_pigeon_node_set_nth(const struct cds_ja_type *type,
 519                 struct cds_ja_inode *node,
 520                 struct cds_ja_shadow_node *shadow_node,
 521                 uint8_t n,
 522                 struct cds_ja_inode_flag *child_node_flag)
 523 {
 524         struct cds_ja_inode_flag **ptr;
 525
 526         assert(type->type_class == RCU_JA_PIGEON);
 527         ptr = &((struct cds_ja_inode_flag **) node->u.data)[n];
 528         if (*ptr)
 529                 return -EEXIST;
 530         rcu_assign_pointer(*ptr, child_node_flag);
 531         shadow_node->nr_child++;
 532         return 0;
 533 }
 534
 535 /*
 536  * _ja_node_set_nth: set nth item within a node. Return an error
 537  * (negative error value) if it is already there.
 538  * TODO: exclusive access on node.
 539  */
 540 static
 541 int _ja_node_set_nth(const struct cds_ja_type *type,
 542                 struct cds_ja_inode *node,
 543                 struct cds_ja_shadow_node *shadow_node,
 544                 uint8_t n,
 545                 struct cds_ja_inode_flag *child_node_flag)
 546 {
 547         switch (type->type_class) {
 548         case RCU_JA_LINEAR:
 549                 return ja_linear_node_set_nth(type, node, shadow_node, n,
 550                                 child_node_flag);
 551         case RCU_JA_POOL:
 552                 return ja_pool_node_set_nth(type, node, shadow_node, n,
 553                                 child_node_flag);
 554         case RCU_JA_PIGEON:
 555                 return ja_pigeon_node_set_nth(type, node, shadow_node, n,
 556                                 child_node_flag);
 557         case RCU_JA_NULL:
 558                 return -ENOSPC;
 559         default:
 560                 assert(0);
 561                 return -EINVAL;
 562         }
 563
 564         return 0;
 565 }
 566
 567 /*
 568  * ja_node_recompact_add: recompact a node, adding a new child.
 569  * TODO: for pool type, take selection bit(s) into account.
 570  * Return 0 on success, -ENOENT if need to retry, or other negative
 571  * error value otherwise.
 572  */
 573 static
 574 int ja_node_recompact_add(struct cds_ja *ja,
 575                 unsigned int old_type_index,
 576                 const struct cds_ja_type *old_type,
 577                 struct cds_ja_inode *old_node,
 578                 struct cds_ja_shadow_node *shadow_node,
 579                 struct cds_ja_inode_flag **old_node_flag, uint8_t n,
 580                 struct cds_ja_inode_flag *child_node_flag)
 581 {
 582         unsigned int new_type_index;
 583         struct cds_ja_inode *new_node;
 584         const struct cds_ja_type *new_type;
 585         struct cds_ja_inode_flag *new_node_flag;
 586         int new_shadow = 0;
 587         int ret;
 588
 589         if (!shadow_node || old_type_index == NODE_INDEX_NULL) {
 590                 new_type_index = 0;
 591         } else {
 592                 new_type_index = old_type_index + 1;
 593         }
 594         dbg_printf("Recompact to type %d\n", new_type_index);
 595
 596         new_type = &ja_types[new_type_index];
 597         new_node = alloc_cds_ja_node(new_type);
 598         if (!new_node)
 599                 return -ENOMEM;
 600         new_node_flag = ja_node_flag(new_node, new_type_index);
 601
 602         dbg_printf("Recompact inherit lock from %p\n", shadow_node);
 603         ret = rcuja_shadow_set(ja->ht, new_node, shadow_node);
 604         if (ret) {
 605                 free(new_node);
 606                 return ret;
 607         }
 608
 609         if (!shadow_node) {
 610                 shadow_node = rcuja_shadow_lookup_lock(ja->ht, new_node);
 611                 assert(shadow_node);
 612                 new_shadow = 1;
 613         }
 614
 615         /*
 616          * We need to clear nr_child, because it will be re-incremented
 617          * by _ja_node_set_nth().
 618          */
 619         shadow_node->nr_child = 0;
 620
 621         assert(old_type->type_class != RCU_JA_PIGEON);
 622         switch (old_type->type_class) {
 623         case RCU_JA_LINEAR:
 624         {
 625                 uint8_t nr_child =
 626                         ja_linear_node_get_nr_child(old_type, old_node);
 627                 unsigned int i;
 628
 629                 for (i = 0; i < nr_child; i++) {
 630                         struct cds_ja_inode_flag *iter;
 631                         uint8_t v;
 632
 633                         ja_linear_node_get_ith_pos(old_type, old_node, i, &v, &iter);
 634                         if (!iter)
 635                                 continue;
 636                         ret = _ja_node_set_nth(new_type, new_node, shadow_node,
 637                                         v, iter);
 638                         assert(!ret);
 639                 }
 640                 break;
 641         }
 642         case RCU_JA_POOL:
 643         {
 644                 unsigned int pool_nr;
 645
 646                 for (pool_nr = 0; pool_nr < (1U << old_type->nr_pool_order); pool_nr++) {
 647                         struct cds_ja_inode *pool =
 648                                 ja_pool_node_get_ith_pool(old_type,
 649                                         old_node, pool_nr);
 650                         uint8_t nr_child =
 651                                 ja_linear_node_get_nr_child(old_type, pool);
 652                         unsigned int j;
 653
 654                         for (j = 0; j < nr_child; j++) {
 655                                 struct cds_ja_inode_flag *iter;
 656                                 uint8_t v;
 657
 658                                 ja_linear_node_get_ith_pos(old_type, pool,
 659                                                 j, &v, &iter);
 660                                 if (!iter)
 661                                         continue;
 662                                 ret = _ja_node_set_nth(new_type, new_node, shadow_node,
 663                                                 v, iter);
 664                                 assert(!ret);
 665                         }
 666                 }
 667                 break;
 668         }
 669         case RCU_JA_NULL:
 670                 /* Nothing to copy */
 671                 break;
 672         case RCU_JA_PIGEON:
 673         default:
 674                 assert(0);
 675                 ret = -EINVAL;
 676                 goto unlock_new_shadow;
 677         }
 678
 679         /* add node */
 680         ret = _ja_node_set_nth(new_type, new_node, shadow_node,
 681                         n, child_node_flag);
 682         assert(!ret);
 683         /* Return pointer to new recompacted new through old_node_flag */
 684         *old_node_flag = new_node_flag;
 685         if (old_node) {
 686                 ret = rcuja_shadow_clear(ja->ht, old_node, shadow_node,
 687                                 RCUJA_SHADOW_CLEAR_FREE_NODE);
 688                 assert(!ret);
 689         }
 690
 691         ret = 0;
 692
 693 unlock_new_shadow:
 694         if (new_shadow)
 695                 rcuja_shadow_unlock(shadow_node);
 696         return ret;
 697 }
 698
 699 /*
 700  * Return 0 on success, -ENOENT if need to retry, or other negative
 701  * error value otherwise.
 702  */
 703 static
 704 int ja_node_set_nth(struct cds_ja *ja,
 705                 struct cds_ja_inode_flag **node_flag, uint8_t n,
 706                 struct cds_ja_inode_flag *child_node_flag,
 707                 struct cds_ja_shadow_node *shadow_node)
 708 {
 709         int ret;
 710         unsigned int type_index;
 711         const struct cds_ja_type *type;
 712         struct cds_ja_inode *node;
 713
 714         dbg_printf("ja_node_set_nth for n=%u, node %p, shadow %p\n",
 715                 (unsigned int) n, ja_node_ptr(*node_flag), shadow_node);
 716
 717         node = ja_node_ptr(*node_flag);
 718         type_index = ja_node_type(*node_flag);
 719         type = &ja_types[type_index];
 720         ret = _ja_node_set_nth(type, node, shadow_node,
 721                         n, child_node_flag);
 722         if (ret == -ENOSPC) {
 723                 /* Not enough space in node, need to recompact. */
 724                 ret = ja_node_recompact_add(ja, type_index, type, node,
 725                                 shadow_node, node_flag, n, child_node_flag);
 726         }
 727         return ret;
 728 }
 729
 730 struct cds_hlist_head *cds_ja_lookup(struct cds_ja *ja, uint64_t key)
 731 {
 732         unsigned int tree_depth, i;
 733         struct cds_ja_inode_flag *node_flag;
 734
 735         if (caa_unlikely(key > ja->key_max))
 736                 return NULL;
 737         tree_depth = ja->tree_depth;
 738         node_flag = rcu_dereference(ja->root);
 739
 740         /* level 0: root node */
 741         if (!ja_node_ptr(node_flag))
 742                 return NULL;
 743
 744         for (i = 1; i < tree_depth; i++) {
 745                 node_flag = ja_node_get_nth(node_flag, NULL,
 746                         (unsigned char) key);
 747                 if (!ja_node_ptr(node_flag))
 748                         return NULL;
 749                 key >>= JA_BITS_PER_BYTE;
 750         }
 751
 752         /* Last level lookup succeded. We got an actual match. */
 753         return (struct cds_hlist_head *) node_flag;
 754 }
 755
 756 /*
 757  * We reached an unpopulated node. Create it and the children we need,
 758  * and then attach the entire branch to the current node. This may
 759  * trigger recompaction of the current node.  Locks needed: node lock
 760  * (for add), and, possibly, parent node lock (to update pointer due to
 761  * node recompaction).
 762  *
 763  * First take node lock, check if recompaction is needed, then take
 764  * parent lock (if needed).  Then we can proceed to create the new
 765  * branch. Publish the new branch, and release locks.
 766  * TODO: we currently always take the parent lock even when not needed.
 767  */
 768 static
 769 int ja_attach_node(struct cds_ja *ja,
 770                 struct cds_ja_inode_flag **node_flag_ptr,
 771                 struct cds_ja_inode_flag *node_flag,
 772                 struct cds_ja_inode_flag *parent_node_flag,
 773                 uint64_t key,
 774                 unsigned int depth,
 775                 struct cds_ja_node *child_node)
 776 {
 777         struct cds_ja_shadow_node *shadow_node = NULL,
 778                         *parent_shadow_node = NULL;
 779         struct cds_ja_inode *node = ja_node_ptr(node_flag);
 780         struct cds_ja_inode *parent_node = ja_node_ptr(parent_node_flag);
 781         struct cds_hlist_head head;
 782         struct cds_ja_inode_flag *iter_node_flag, *iter_dest_node_flag;
 783         int ret, i;
 784         struct cds_ja_inode_flag *created_nodes[JA_MAX_DEPTH];
 785         int nr_created_nodes = 0;
 786
 787         dbg_printf("Attach node at depth %u\n", depth);
 788
 789         assert(node);
 790         shadow_node = rcuja_shadow_lookup_lock(ja->ht, node);
 791         if (!shadow_node) {
 792                 ret = -ENOENT;
 793                 goto end;
 794         }
 795         if (parent_node) {
 796                 parent_shadow_node = rcuja_shadow_lookup_lock(ja->ht,
 797                                                 parent_node);
 798                 if (!parent_shadow_node) {
 799                         ret = -ENOENT;
 800                         goto unlock_shadow;
 801                 }
 802         }
 803
 804         /* Create new branch, starting from bottom */
 805         CDS_INIT_HLIST_HEAD(&head);
 806         cds_hlist_add_head_rcu(&child_node->list, &head);
 807         iter_node_flag = (struct cds_ja_inode_flag *) head.next;
 808
 809         /* Create shadow node for the leaf node */
 810         dbg_printf("leaf shadow node creation\n");
 811         ret = rcuja_shadow_set(ja->ht, ja_node_ptr(iter_node_flag), NULL);
 812         if (ret)
 813                 goto check_error;
 814         created_nodes[nr_created_nodes++] = iter_node_flag;
 815
 816         for (i = ja->tree_depth - 1; i >= (int) depth; i--) {
 817                 dbg_printf("branch creation level %d, key %" PRIu64 "\n",
 818                                 i, key >> (JA_BITS_PER_BYTE * (i - 2)));
 819                 iter_dest_node_flag = NULL;
 820                 ret = ja_node_set_nth(ja, &iter_dest_node_flag,
 821                         key >> (JA_BITS_PER_BYTE * (i - 2)),
 822                         iter_node_flag,
 823                         NULL);
 824                 if (ret)
 825                         goto check_error;
 826                 created_nodes[nr_created_nodes++] = iter_dest_node_flag;
 827                 iter_node_flag = iter_dest_node_flag;
 828         }
 829
 830         if (depth > 1) {
 831                 /* We need to use set_nth on the previous level. */
 832                 iter_dest_node_flag = node_flag;
 833                 ret = ja_node_set_nth(ja, &iter_dest_node_flag,
 834                         key >> (JA_BITS_PER_BYTE * (depth - 2)),
 835                         iter_node_flag,
 836                         shadow_node);
 837                 if (ret)
 838                         goto check_error;
 839                 created_nodes[nr_created_nodes++] = iter_dest_node_flag;
 840                 iter_node_flag = iter_dest_node_flag;
 841         }
 842
 843         /* Publish new branch */
 844         dbg_printf("Publish branch %p, replacing %p\n",
 845                 iter_node_flag, *node_flag_ptr);
 846         rcu_assign_pointer(*node_flag_ptr, iter_node_flag);
 847
 848         /* Success */
 849         ret = 0;
 850
 851 check_error:
 852         if (ret) {
 853                 for (i = 0; i < nr_created_nodes; i++) {
 854                         int tmpret;
 855                         int flags;
 856
 857                         flags = RCUJA_SHADOW_CLEAR_FREE_LOCK;
 858                         if (i)
 859                                 flags |= RCUJA_SHADOW_CLEAR_FREE_NODE;
 860                         tmpret = rcuja_shadow_clear(ja->ht,
 861                                         ja_node_ptr(created_nodes[i]),
 862                                         NULL,
 863                                         flags);
 864                         assert(!tmpret);
 865                 }
 866         }
 867         if (parent_shadow_node)
 868                 rcuja_shadow_unlock(parent_shadow_node);
 869 unlock_shadow:
 870         if (shadow_node)
 871                 rcuja_shadow_unlock(shadow_node);
 872 end:
 873         return ret;
 874 }
 875
 876 /*
 877  * Lock the hlist head shadow node mutex, and add node to list of
 878  * duplicates. Failure can happen if concurrent removal removes the last
 879  * node with same key before we get the lock.
 880  * Return 0 on success, negative error value on failure.
 881  */
 882 static
 883 int ja_chain_node(struct cds_ja *ja,
 884                 struct cds_hlist_head *head,
 885                 struct cds_ja_node *node)
 886 {
 887         struct cds_ja_shadow_node *shadow_node;
 888
 889         shadow_node = rcuja_shadow_lookup_lock(ja->ht,
 890                 (struct cds_ja_inode *) head);
 891         if (!shadow_node)
 892                 return -ENOENT;
 893         cds_hlist_add_head_rcu(&node->list, head);
 894         rcuja_shadow_unlock(shadow_node);
 895         return 0;
 896 }
 897
 898 int cds_ja_add(struct cds_ja *ja, uint64_t key,
 899                 struct cds_ja_node *new_node)
 900 {
 901         unsigned int tree_depth, i;
 902         uint64_t iter_key;
 903         struct cds_ja_inode_flag **node_flag_ptr;       /* in parent */
 904         struct cds_ja_inode_flag *node_flag,
 905                 *parent_node_flag,
 906                 *parent2_node_flag;
 907         int ret;
 908
 909         if (caa_unlikely(key > ja->key_max))
 910                 return -EINVAL;
 911         tree_depth = ja->tree_depth;
 912
 913 retry:
 914         dbg_printf("cds_ja_add attempt: key %" PRIu64 ", node %p\n",
 915                 key, new_node);
 916         iter_key = key;
 917         parent2_node_flag = NULL;
 918         parent_node_flag =
 919                 (struct cds_ja_inode_flag *) &ja->root; /* Use root ptr address as key for mutex */
 920         node_flag_ptr = &ja->root;
 921         node_flag = rcu_dereference(*node_flag_ptr);
 922
 923         /* Iterate on all internal levels */
 924         for (i = 1; i < tree_depth; i++) {
 925                 if (!ja_node_ptr(node_flag)) {
 926                         ret = ja_attach_node(ja, node_flag_ptr,
 927                                         parent_node_flag, parent2_node_flag,
 928                                         key, i, new_node);
 929                         if (ret == -ENOENT || ret == -EEXIST)
 930                                 goto retry;
 931                         else
 932                                 goto end;
 933                 }
 934                 parent2_node_flag = parent_node_flag;
 935                 parent_node_flag = node_flag;
 936                 node_flag = ja_node_get_nth(node_flag,
 937                         &node_flag_ptr,
 938                         (unsigned char) iter_key);
 939                 iter_key >>= JA_BITS_PER_BYTE;
 940         }
 941
 942         /*
 943          * We reached bottom of tree, simply add node to last internal
 944          * level, or chain it if key is already present.
 945          */
 946         if (!ja_node_ptr(node_flag)) {
 947                 ret = ja_attach_node(ja, node_flag_ptr, parent_node_flag,
 948                                 parent2_node_flag, key, i, new_node);
 949         } else {
 950                 ret = ja_chain_node(ja,
 951                         (struct cds_hlist_head *) ja_node_ptr(node_flag),
 952                         new_node);
 953         }
 954         if (ret == -ENOENT)
 955                 goto retry;
 956 end:
 957         return ret;
 958 }
 959
 960 struct cds_ja *_cds_ja_new(unsigned int key_bits,
 961                 const struct rcu_flavor_struct *flavor)
 962 {
 963         struct cds_ja *ja;
 964         int ret;
 965
 966         ja = calloc(sizeof(*ja), 1);
 967         if (!ja)
 968                 goto ja_error;
 969
 970         switch (key_bits) {
 971         case 8:
 972                 ja->key_max = UINT8_MAX;
 973                 break;
 974         case 16:
 975                 ja->key_max = UINT16_MAX;
 976                 break;
 977         case 32:
 978                 ja->key_max = UINT32_MAX;
 979                 break;
 980         case 64:
 981                 ja->key_max = UINT64_MAX;
 982                 break;
 983         default:
 984                 goto check_error;
 985         }
 986
 987         /* ja->root is NULL */
 988         /* tree_depth 0 is for pointer to root node */
 989         ja->tree_depth = (key_bits >> JA_BITS_PER_BYTE) + 1;
 990         assert(ja->tree_depth <= JA_MAX_DEPTH);
 991         ja->ht = rcuja_create_ht(flavor);
 992         if (!ja->ht)
 993                 goto ht_error;
 994
 995         /*
 996          * Note: we should not free this node until judy array destroy.
 997          */
 998         ret = rcuja_shadow_set(ja->ht,
 999                         ja_node_ptr((struct cds_ja_inode_flag *) &ja->root),
1000                         NULL);
1001         if (ret)
1002                 goto ht_node_error;
1003
1004         return ja;
1005
1006 ht_node_error:
1007         ret = rcuja_delete_ht(ja->ht);
1008         assert(!ret);
1009 ht_error:
1010 check_error:
1011         free(ja);
1012 ja_error:
1013         return NULL;
1014 }
1015
1016 /*
1017  * There should be no more concurrent add to the judy array while it is
1018  * being destroyed (ensured by the caller).
1019  */
1020 int cds_ja_destroy(struct cds_ja *ja)
1021 {
1022         int ret;
1023
1024         rcuja_shadow_prune(ja->ht,
1025                 RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK);
1026         ret = rcuja_delete_ht(ja->ht);
1027         if (ret)
1028                 return ret;
1029         free(ja);
1030         return 0;
1031 }