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 };
  44
  45 struct rcu_ja_type {
  46         enum rcu_ja_type_class type_class;
  47         uint16_t min_child;     /* minimum number of children: 1 to 256 */
  48         uint16_t max_child;     /* maximum number of children: 1 to 256 */
  49         uint16_t order;         /* node size is (1 << order), in bytes */
  50         uint16_t nr_pool_order;         /* number of pools */
  51         uint16_t pool_size_order;       /* pool size */
  52 };
  53
  54 /*
  55  * Number of least significant pointer bits reserved to represent the
  56  * child type.
  57  */
  58 #define JA_TYPE_BITS    3
  59 #define JA_TYPE_MAX_NR  (1U << JA_TYPE_BITS)
  60 #define JA_TYPE_MASK    (JA_TYPE_MAX_NR - 1)
  61 #define JA_PTR_MASK     (~JA_TYPE_MASK)
  62
  63 #define JA_ENTRY_PER_NODE       256UL
  64
  65 /*
  66  * Iteration on the array to find the right node size for the number of
  67  * children stops when it reaches .max_child == 256 (this is the largest
  68  * possible node size, which contains 256 children).
  69  * The min_child overlaps with the previous max_child to provide an
  70  * hysteresis loop to reallocation for patterns of cyclic add/removal
  71  * within the same node.
  72  * The node the index within the following arrays is represented on 3
  73  * bits. It identifies the node type, min/max number of children, and
  74  * the size order.
  75  */
  76
  77 #if (CAA_BITS_PER_LONG < 64)
  78 /* 32-bit pointers */
  79 const struct rcu_ja_type ja_types[] = {
  80         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 1, .order = 3, },
  81         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 3, .order = 4, },
  82         { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = 6, .order = 5, },
  83         { .type_class = RCU_JA_LINEAR, .min_child = 4, .max_child = 12, .order = 6, },
  84         { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = 25, .order = 7, },
  85
  86         /* Pools may fill sooner than max_child */
  87         { .type_class = RCU_JA_POOL, .min_child = 20, .max_child = 50, .order = 8, .nr_pool_order = 1, .pool_size_order = 7, },
  88         { .type_class = RCU_JA_POOL, .min_child = 42, .max_child = 100, .order = 9, .nr_pool_order = 2, .pool_size_order = 7, },
  89
  90         /* TODO: Upon downsize, if at least one pool is filled, we need to keep pigeon */
  91         { .type_class = RCU_JA_PIGEON, .min_child = 90, .max_child = 256, .order = 10, },
  92 };
  93 CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR);
  94 #else /* !(CAA_BITS_PER_LONG < 64) */
  95 /* 64-bit pointers */
  96 const struct rcu_ja_type ja_types[] = {
  97         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 1, .order = 4, },
  98         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 3, .order = 5, },
  99         { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = 7, .order = 6, },
 100         { .type_class = RCU_JA_LINEAR, .min_child = 5, .max_child = 14, .order = 7, },
 101         { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = 28, .order = 8, },
 102
 103         /* Pools may fill sooner than max_child */
 104         { .type_class = RCU_JA_POOL, .min_child = 22, .max_child = 56, .order = 9, .nr_pool_order = 1, .pool_size_order = 8, },
 105         { .type_class = RCU_JA_POOL, .min_child = 44, .max_child = 112, .order = 10, .nr_pool_order = 2, .pool_size_order = 8, },
 106
 107         /* TODO: Upon downsize, if at least one pool is filled, we need to keep pigeon */
 108         { .type_class = RCU_JA_PIGEON, .min_child = 100, .max_child = 256, .order = 11, },
 109 };
 110 CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR);
 111 #endif /* !(BITS_PER_LONG < 64) */
 112
 113 /*
 114  * The rcu_ja_node starts with a byte counting the number of children in
 115  * the node. Then, the node-specific data is placed.
 116  * TODO: where should we put the mutex for the node ?
 117  *  -> mutex could be a 0-value node count.
 118  * TODO: where do we keep nr children for pigeon ?
 119  */
 120 struct rcu_ja_node {
 121         char data[];
 122 };
 123
 124 /* Never declared. Opaque type used to store flagged node pointers. */
 125 struct rcu_ja_node_flag;
 126
 127 static
 128 struct rcu_ja_node_flag *ja_node_flag(struct rcu_ja_node *node, unsigned int type)
 129 {
 130         assert(type < JA_TYPE_NR);
 131         return (struct rcu_ja_node_flag *) (((unsigned long) node) | type);
 132 }
 133
 134 static
 135 unsigned int ja_node_type(struct rcu_ja_node_flag *node)
 136 {
 137         unsigned int type;
 138
 139         type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
 140         assert(type < JA_TYPE_NR);
 141         return type;
 142 }
 143
 144 static
 145 struct rcu_ja_node *ja_node_ptr(struct rcu_ja_node_flag *node)
 146 {
 147         return (struct rcu_ja_node *) (((unsigned long) node) | JA_PTR_MASK);
 148 }
 149
 150 struct rcu_ja_node *alloc_rcu_ja_node(struct rcu_ja_type *ja_type)
 151 {
 152         return zmalloc(1 << ja_type->node_order);
 153 }
 154
 155 void free_rcu_ja_node(struct rcu_ja_node *node)
 156 {
 157         free(node);
 158 }
 159
 160 #define __JA_ALIGN_MASK(v, mask)        (((v) + (mask)) & ~(mask))
 161 #define JA_ALIGN(v, align)              __JA_ALIGN_MASK(v, (typeof(v)) (align) - 1)
 162 #define __JA_FLOOR_MASK(v, mask)        ((v) & ~(mask))
 163 #define JA_FLOOR(v, align)              __JA_FLOOR_MASK(v, (typeof(v)) (align) - 1)
 164
 165 static
 166 char *align_ptr_size(char *ptr)
 167 {
 168         return JA_ALIGN(ptr, sizeof(ptr));
 169 }
 170
 171 static
 172 struct rcu_ja_node_flag *ja_linear_node_get_nth(const struct rcu_ja_type *type,
 173                                         struct rcu_ja_node *node,
 174                                         uint8_t n)
 175 {
 176         uint8_t nr_child;
 177         uint8_t *values;
 178         struct rcu_ja_node_flag *pointers;
 179         struct rcu_ja_node_flag *ptr;
 180         unsigned int i;
 181
 182         assert(!type || type->type_class == RCU_JA_LINEAR);
 183
 184         nr_child = node->data[0];
 185         cmm_smp_rmb();  /* read nr_child before values */
 186         assert(!type || nr_child <= type->max_child);
 187         assert(!type || nr_child >= type->min_child);
 188
 189         values = &node[1];
 190         for (i = 0; i < nr_child; i++) {
 191                 if (values[i] == n)
 192                         break;
 193         }
 194         if (i >= nr_child)
 195                 return NULL;
 196         cmm_smp_rmb();  /* read values before pointer */
 197         pointers = align_ptr_size(&values[nr_child]);
 198         ptr = pointers[i];
 199         assert(ja_node_ptr(ptr) != NULL);
 200         return ptr;
 201 }
 202
 203 static
 204 struct rcu_ja_node_flag *ja_pool_node_get_nth(const struct rcu_ja_type *type,
 205                                         struct rcu_ja_node *node,
 206                                         uint8_t n)
 207 {
 208         struct rcu_ja_node_flag *ptr;
 209         struct rcu_ja_node *linear;
 210
 211         assert(type->type_class == RCU_JA_POOL);
 212         linear = (struct rcu_ja_node *)
 213                 &node->data[(n >> (CHAR_BIT - type->nr_pool_order)) << type->pool_size_order];
 214         return ja_linear_node_get_nth(NULL, linear, n);
 215 }
 216
 217 static
 218 struct rcu_ja_node_flag *ja_pigeon_node_get_nth(const struct rcu_ja_type *type,
 219                                         struct rcu_ja_node *node,
 220                                         uint8_t n)
 221 {
 222         assert(type->type_class == RCU_JA_PIGEON);
 223         return ((struct rcu_ja_node_flag *) node->data)[n];
 224 }
 225
 226 /* ja_node_get_nth: get nth item from a node */
 227 static
 228 struct rcu_ja_node_flag *ja_node_get_nth(struct rcu_ja_node_flag *node_flag,
 229                                         uint8_t n)
 230 {
 231         unsigned int type_index;
 232         struct rcu_ja_node *node;
 233         const struct rcu_ja_type *type;
 234
 235         node_flag = rcu_dereference(node_flag);
 236         node = ja_node_ptr(node_flag);
 237         assert(node != NULL);
 238         type_index = ja_node_type(node_flag);
 239         type = &ja_types[type_index];
 240
 241         switch (type->type_class) {
 242         case RCU_JA_LINEAR:
 243                 return ja_linear_node_get_nth(type, node, n);
 244         case RCU_JA_POOL:
 245                 return ja_pool_node_get_nth(type, node, n);
 246         case RCU_JA_PIGEON:
 247                 return ja_pigeon_node_get_nth(type, node, n);
 248         default:
 249                 assert(0);
 250                 return (void *) -1UL;
 251         }
 252 }
 253
 254 /*
 255  * ja_node_set_nth: set nth item within a node. asserts that it is not
 256  * there yet.
 257  */
 258