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 #include <stdint.h>
  24 #include <limits.h>
  25 #include <urcu/rcuja.h>
  26 #include <urcu/compiler.h>
  27 #include <urcu/arch.h>
  28 #include <assert.h>
  29 #include "rcuja-internal.h"
  30 #include "bitfield.h"
  31
  32 enum rcu_ja_type_class {
  33         RCU_JA_LINEAR = 0,      /* Type A */
  34                         /* 32-bit: 1 to 25 children, 8 to 128 bytes */
  35                         /* 64-bit: 1 to 28 children, 16 to 256 bytes */
  36         RCU_JA_POOL = 1,        /* Type B */
  37                         /* 32-bit: 26 to 100 children, 256 to 512 bytes */
  38                         /* 64-bit: 29 to 112 children, 512 to 1024 bytes */
  39         RCU_JA_PIGEON = 2,      /* Type C */
  40                         /* 32-bit: 101 to 256 children, 1024 bytes */
  41                         /* 64-bit: 113 to 256 children, 2048 bytes */
  42         /* Leaf nodes are implicit from their height in the tree */
  43         RCU_JA_NR_TYPES,
  44 };
  45
  46 struct rcu_ja_type {
  47         enum rcu_ja_type_class type_class;
  48         uint16_t min_child;     /* minimum number of children: 1 to 256 */
  49         uint16_t max_child;     /* maximum number of children: 1 to 256 */
  50         uint16_t order;         /* node size is (1 << order), in bytes */
  51         uint16_t nr_pool_order;         /* number of pools */
  52         uint16_t pool_size_order;       /* pool size */
  53 };
  54
  55 /*
  56  * Number of least significant pointer bits reserved to represent the
  57  * child type.
  58  */
  59 #define JA_TYPE_BITS    3
  60 #define JA_TYPE_MAX_NR  (1U << JA_TYPE_BITS)
  61 #define JA_TYPE_MASK    (JA_TYPE_MAX_NR - 1)
  62 #define JA_PTR_MASK     (~JA_TYPE_MASK)
  63
  64 #define JA_ENTRY_PER_NODE       256UL
  65
  66 /*
  67  * Iteration on the array to find the right node size for the number of
  68  * children stops when it reaches .max_child == 256 (this is the largest
  69  * possible node size, which contains 256 children).
  70  * The min_child overlaps with the previous max_child to provide an
  71  * hysteresis loop to reallocation for patterns of cyclic add/removal
  72  * within the same node.
  73  * The node the index within the following arrays is represented on 3
  74  * bits. It identifies the node type, min/max number of children, and
  75  * the size order.
  76  * The max_child values for the RCU_JA_POOL below result from
  77  * statistical approximation: over million populations, the max_child
  78  * covers between 97% and 99% of the populations generated. Therefore, a
  79  * fallback should exist to cover the rare extreme population unbalance
  80  * cases, but it will not have a major impact on speed nor space
  81  * consumption, since those are rare cases.
  82  */
  83
  84 #if (CAA_BITS_PER_LONG < 64)
  85 /* 32-bit pointers */
  86 enum {
  87         ja_type_0_max_child = 1,
  88         ja_type_1_max_child = 3,
  89         ja_type_2_max_child = 6,
  90         ja_type_3_max_child = 12,
  91         ja_type_4_max_child = 25,
  92         ja_type_5_max_child = 48,
  93         ja_type_6_max_child = 92,
  94         ja_type_7_max_child = 256,
  95 };
  96
  97 enum {
  98         ja_type_5_nr_pool_order = 1,
  99         ja_type_6_nr_pool_order = 2,
 100 };
 101
 102 const struct rcu_ja_type ja_types[] = {
 103         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_0_max_child, .order = 3, },
 104         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_1_max_child, .order = 4, },
 105         { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = ja_type_2_max_child, .order = 5, },
 106         { .type_class = RCU_JA_LINEAR, .min_child = 4, .max_child = ja_type_3_max_child, .order = 6, },
 107         { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = ja_type_4_max_child, .order = 7, },
 108
 109         /* Pools may fill sooner than max_child */
 110         { .type_class = RCU_JA_POOL, .min_child = 20, .max_child = ja_type_5_max_child, .order = 8, .nr_pool_order = ja_type_5_nr_pool_order, .pool_size_order = 7, },
 111         { .type_class = RCU_JA_POOL, .min_child = 45, .max_child = ja_type_6_max_child, .order = 9, .nr_pool_order = ja_type_6_nr_pool_order, .pool_size_order = 7, },
 112
 113         /*
 114          * TODO: Upon node removal below min_child, if child pool is
 115          * filled beyond capacity, we need to roll back to pigeon.
 116          */
 117         { .type_class = RCU_JA_PIGEON, .min_child = 89, .max_child = ja_type_7_max_child, .order = 10, },
 118 };
 119 #else /* !(CAA_BITS_PER_LONG < 64) */
 120 /* 64-bit pointers */
 121 enum {
 122         ja_type_0_max_child = 1,
 123         ja_type_1_max_child = 3,
 124         ja_type_2_max_child = 7,
 125         ja_type_3_max_child = 14,
 126         ja_type_4_max_child = 28,
 127         ja_type_5_max_child = 54,
 128         ja_type_6_max_child = 104,
 129         ja_type_7_max_child = 256,
 130 };
 131
 132 enum {
 133         ja_type_5_nr_pool_order = 1,
 134         ja_type_6_nr_pool_order = 2,
 135 };
 136
 137 const struct rcu_ja_type ja_types[] = {
 138         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_0_max_child, .order = 4, },
 139         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = ja_type_1_max_child, .order = 5, },
 140         { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = ja_type_2_max_child, .order = 6, },
 141         { .type_class = RCU_JA_LINEAR, .min_child = 5, .max_child = ja_type_3_max_child, .order = 7, },
 142         { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = ja_type_4_max_child, .order = 8, },
 143
 144         /* Pools may fill sooner than max_child. */
 145         { .type_class = RCU_JA_POOL, .min_child = 22, .max_child = ja_type_5_max_child, .order = 9, .nr_pool_order = ja_type_5_nr_pool_order, .pool_size_order = 8, },
 146         { .type_class = RCU_JA_POOL, .min_child = 51, .max_child = ja_type_6_max_child, .order = 10, .nr_pool_order = ja_type_6_nr_pool_order, .pool_size_order = 8, },
 147
 148         /*
 149          * TODO: Upon node removal below min_child, if child pool is
 150          * filled beyond capacity, we need to roll back to pigeon.
 151          */
 152         { .type_class = RCU_JA_PIGEON, .min_child = 101, .max_child = ja_type_7_max_child, .order = 11, },
 153 };
 154 #endif /* !(BITS_PER_LONG < 64) */
 155
 156 static inline __attribute__((unused))
 157 void static_array_size_check(void)
 158 {
 159         CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR);
 160 }
 161
 162 /* Never declared. Opaque type used to store flagged node pointers. */
 163 struct rcu_ja_node_flag;
 164
 165 /*
 166  * The rcu_ja_node contains the compressed node data needed for
 167  * read-side. For linear and pool node configurations, it starts with a
 168  * byte counting the number of children in the node.  Then, the
 169  * node-specific data is placed.
 170  * The node mutex, if any is needed, protecting concurrent updated of
 171  * each node is placed in a separate hash table indexed by node address.
 172  * For the pigeon configuration, the number of children is also kept in
 173  * a separate hash table, indexed by node address, because it is only
 174  * required for updates.
 175  */
 176
 177 #define DECLARE_LINEAR_NODE(index)                                                                      \
 178                 struct {                                                                                \
 179                         uint8_t nr_child;                                                               \
 180                         uint8_t child_value[ja_type_## index ##_max_child];                             \
 181                         struct rcu_ja_node_flag *child_ptr[ja_type_## index ##_max_child];                      \
 182                 }
 183
 184 #define DECLARE_POOL_NODE(index)                                                                        \
 185                 struct {                                                                                \
 186                         struct {                                                                        \
 187                                 uint8_t nr_child;                                                       \
 188                                 uint8_t child_value[ja_type_## index ##_max_child >> ja_type_## index ##_nr_pool_order]; \
 189                                 struct rcu_ja_node_flag *child_ptr[ja_type_## index ##_max_child >> ja_type_## index ##_nr_pool_order]; \
 190                         } linear[1U << ja_type_## index ##_nr_pool_order];                              \
 191                 }
 192
 193 struct rcu_ja_node {
 194         union {
 195                 /* Linear configuration */
 196                 DECLARE_LINEAR_NODE(0) conf_0;
 197                 DECLARE_LINEAR_NODE(1) conf_1;
 198                 DECLARE_LINEAR_NODE(2) conf_2;
 199                 DECLARE_LINEAR_NODE(3) conf_3;
 200                 DECLARE_LINEAR_NODE(4) conf_4;
 201
 202                 /* Pool configuration */
 203                 DECLARE_POOL_NODE(5) conf_5;
 204                 DECLARE_POOL_NODE(6) conf_6;
 205
 206                 /* Pigeon configuration */
 207                 struct {
 208                         struct rcu_ja_node_flag *child[ja_type_7_max_child];
 209                 } conf_7;
 210                 /* data aliasing nodes for computed accesses */
 211                 uint8_t data[sizeof(struct rcu_ja_node_flag *) * ja_type_7_max_child];
 212         } u;
 213 };
 214
 215 static
 216 struct rcu_ja_node_flag *ja_node_flag(struct rcu_ja_node *node, unsigned int type)
 217 {
 218         assert(type < RCU_JA_NR_TYPES);
 219         return (struct rcu_ja_node_flag *) (((unsigned long) node) | type);
 220 }
 221
 222 static
 223 unsigned int ja_node_type(struct rcu_ja_node_flag *node)
 224 {
 225         unsigned int type;
 226
 227         type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
 228         assert(type < RCU_JA_NR_TYPES);
 229         return type;
 230 }
 231
 232 static
 233 struct rcu_ja_node *ja_node_ptr(struct rcu_ja_node_flag *node)
 234 {
 235         return (struct rcu_ja_node *) (((unsigned long) node) | JA_PTR_MASK);
 236 }
 237
 238 struct rcu_ja_node *alloc_rcu_ja_node(struct rcu_ja_type *ja_type)
 239 {
 240         return calloc(1U << ja_type->order, sizeof(char));
 241 }
 242
 243 void free_rcu_ja_node(struct rcu_ja_node *node)
 244 {
 245         free(node);
 246 }
 247
 248 #define __JA_ALIGN_MASK(v, mask)        (((v) + (mask)) & ~(mask))
 249 #define JA_ALIGN(v, align)              __JA_ALIGN_MASK(v, (typeof(v)) (align) - 1)
 250 #define __JA_FLOOR_MASK(v, mask)        ((v) & ~(mask))
 251 #define JA_FLOOR(v, align)              __JA_FLOOR_MASK(v, (typeof(v)) (align) - 1)
 252
 253 static
 254 uint8_t *align_ptr_size(uint8_t *ptr)
 255 {
 256         return (uint8_t *) JA_ALIGN((unsigned long) ptr, sizeof(void *));
 257 }
 258
 259 static
 260 struct rcu_ja_node_flag *ja_linear_node_get_nth(const struct rcu_ja_type *type,
 261                                         struct rcu_ja_node *node,
 262                                         uint8_t n)
 263 {
 264         uint8_t nr_child;
 265         uint8_t *values;
 266         struct rcu_ja_node_flag **pointers;
 267         struct rcu_ja_node_flag *ptr;
 268         unsigned int i;
 269
 270         assert(!type || type->type_class == RCU_JA_LINEAR);
 271
 272         nr_child = node->u.data[0];
 273         cmm_smp_rmb();  /* read nr_child before values */
 274         assert(!type || nr_child <= type->max_child);
 275         assert(!type || nr_child >= type->min_child);
 276
 277         values = &node->u.data[1];
 278         for (i = 0; i < nr_child; i++) {
 279                 if (values[i] == n)
 280                         break;
 281         }
 282         if (i >= nr_child)
 283                 return NULL;
 284         cmm_smp_rmb();  /* read values before pointer */
 285         pointers = (struct rcu_ja_node_flag **) align_ptr_size(&values[nr_child]);
 286         ptr = pointers[i];
 287         assert(ja_node_ptr(ptr) != NULL);
 288         return ptr;
 289 }
 290
 291 static
 292 struct rcu_ja_node_flag *ja_pool_node_get_nth(const struct rcu_ja_type *type,
 293                                         struct rcu_ja_node *node,
 294                                         uint8_t n)
 295 {
 296         struct rcu_ja_node *linear;
 297
 298         assert(type->type_class == RCU_JA_POOL);
 299         linear = (struct rcu_ja_node *)
 300                 &node->u.data[((unsigned long) n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 301         return ja_linear_node_get_nth(NULL, linear, n);
 302 }
 303
 304 static
 305 struct rcu_ja_node_flag *ja_pigeon_node_get_nth(const struct rcu_ja_type *type,
 306                                         struct rcu_ja_node *node,
 307                                         uint8_t n)
 308 {
 309         assert(type->type_class == RCU_JA_PIGEON);
 310         return ((struct rcu_ja_node_flag **) node->u.data)[n];
 311 }
 312
 313 /* ja_node_get_nth: get nth item from a node */
 314 static
 315 struct rcu_ja_node_flag *ja_node_get_nth(struct rcu_ja_node_flag *node_flag,
 316                                         uint8_t n)
 317 {
 318         unsigned int type_index;
 319         struct rcu_ja_node *node;
 320         const struct rcu_ja_type *type;
 321
 322         node_flag = rcu_dereference(node_flag);
 323         node = ja_node_ptr(node_flag);
 324         assert(node != NULL);
 325         type_index = ja_node_type(node_flag);
 326         type = &ja_types[type_index];
 327
 328         switch (type->type_class) {
 329         case RCU_JA_LINEAR:
 330                 return ja_linear_node_get_nth(type, node, n);
 331         case RCU_JA_POOL:
 332                 return ja_pool_node_get_nth(type, node, n);
 333         case RCU_JA_PIGEON:
 334                 return ja_pigeon_node_get_nth(type, node, n);
 335         default:
 336                 assert(0);
 337                 return (void *) -1UL;
 338         }
 339 }
 340
 341 /*
 342  * ja_node_set_nth: set nth item within a node. asserts that it is not
 343  * there yet.
 344  */
 345