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 12 children, 8 to 64 bytes */
  35                         /* 64-bit: 1 to 14 children, 16 to 128 bytes */
  36         RCU_JA_BITMAP = 1,      /* Type B */
  37                         /* 32-bit: 13 to 120 children, 128 to 512 bytes */
  38                         /* 64-bit: 15 to 124 children, 256 to 1024 bytes */
  39         RCU_JA_PIGEON = 2,      /* Type C */
  40                         /* 32-bit: 121 to 256 children, 1024 bytes */
  41                         /* 64-bit: 125 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 };
  51
  52 /*
  53  * Number of least significant pointer bits reserved to represent the
  54  * child type.
  55  */
  56 #define JA_TYPE_BITS    3
  57 #define JA_TYPE_MAX_NR  (1U << JA_TYPE_BITS)
  58 #define JA_TYPE_MASK    (JA_TYPE_MAX_NR - 1)
  59 #define JA_PTR_MASK     (~JA_TYPE_MASK)
  60
  61 #define JA_ENTRY_PER_NODE       256UL
  62
  63 /*
  64  * Iteration on the array to find the right node size for the number of
  65  * children stops when it reaches .max_child == 256 (this is the largest
  66  * possible node size, which contains 256 children).
  67  * The min_child overlaps with the previous max_child to provide an
  68  * hysteresis loop to reallocation for patterns of cyclic add/removal
  69  * within the same node.
  70  * The node the index within the following arrays is represented on 3
  71  * bits. It identifies the node type, min/max number of children, and
  72  * the size order.
  73  */
  74
  75 #if (CAA_BITS_PER_LONG < 64)
  76 /* 32-bit pointers */
  77 const struct rcu_ja_type ja_types[] = {
  78         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 1, .order = 3, },
  79         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 3, .order = 4, },
  80         { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = 6, .order = 5, },
  81         { .type_class = RCU_JA_LINEAR, .min_child = 4, .max_child = 12, .order = 6, },
  82
  83         { .type_class = RCU_JA_BITMAP, .min_child = 10, .max_child = 24, .order = 7, },
  84         { .type_class = RCU_JA_BITMAP, .min_child = 20, .max_child = 56, .order = 8, },
  85         { .type_class = RCU_JA_BITMAP, .min_child = 46, .max_child = 120, .order = 9, },
  86
  87         { .type_class = RCU_JA_PIGEON, .min_child = 100, .max_child = 256, .order = 10, },
  88 };
  89 CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR);
  90 #else /* !(CAA_BITS_PER_LONG < 64) */
  91 /* 64-bit pointers */
  92 const struct rcu_ja_type ja_types[] = {
  93         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 1, .order = 4, },
  94         { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 3, .order = 5, },
  95         { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = 7, .order = 6, },
  96         { .type_class = RCU_JA_LINEAR, .min_child = 5, .max_child = 14, .order = 7, },
  97
  98         { .type_class = RCU_JA_BITMAP, .min_child = 10, .max_child = 28, .order = 8, },
  99         { .type_class = RCU_JA_BITMAP, .min_child = 22, .max_child = 60, .order = 9, },
 100         { .type_class = RCU_JA_BITMAP, .min_child = 49, .max_child = 124, .order = 10, },
 101
 102         { .type_class = RCU_JA_PIGEON, .min_child = 102, .max_child = 256, .order = 11, },
 103 };
 104 CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR);
 105 #endif /* !(BITS_PER_LONG < 64) */
 106
 107 /*
 108  * The rcu_ja_node starts with a byte counting the number of children in
 109  * the node. Then, the node-specific data is placed.
 110  * TODO: where should we put the mutex for the node ?
 111  *  -> mutex could be a 0-value node count.
 112  * TODO: where do we keep nr children for pigeon ?
 113  */
 114 struct rcu_ja_node {
 115         char data[];
 116 };
 117
 118 /* Never declared. Opaque type used to store flagged node pointers. */
 119 struct rcu_ja_node_flag;
 120
 121 static
 122 struct rcu_ja_node_flag *ja_node_flag(struct rcu_ja_node *node, unsigned int type)
 123 {
 124         assert(type < JA_TYPE_NR);
 125         return (struct rcu_ja_node_flag *) (((unsigned long) node) | type);
 126 }
 127
 128 static
 129 unsigned int ja_node_type(struct rcu_ja_node_flag *node)
 130 {
 131         unsigned int type;
 132
 133         type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
 134         assert(type < JA_TYPE_NR);
 135         return type;
 136 }
 137
 138 static
 139 struct rcu_ja_node *ja_node_ptr(struct rcu_ja_node_flag *node)
 140 {
 141         return (struct rcu_ja_node *) (((unsigned long) node) | JA_PTR_MASK);
 142 }
 143
 144 struct rcu_ja_node *alloc_rcu_ja_node(struct rcu_ja_type *ja_type)
 145 {
 146         return zmalloc(1 << ja_type->node_order);
 147 }
 148
 149 void free_rcu_ja_node(struct rcu_ja_node *node)
 150 {
 151         free(node);
 152 }
 153
 154 /* The bitmap for 256 entries is always 32 bytes */
 155 #define CHAR_BIT_SHIFT  3UL
 156 #define CHAR_BIT_MASK   ((1UL << CHAR_BIT_SHIFT) - 1)
 157 #if (CHAR_BIT != (1UL << CHAR_BIT_SHIFT))
 158 #error "char size not supported."
 159 #endif
 160
 161 #define ULONG_BIT_MASK  (CAA_BITS_PER_LONG - 1)
 162
 163 #define JA_BITMAP_BITS  JA_ENTRY_PER_NODE
 164 #define JA_BITMAP_LEN   (JA_BITMAP_BITS / CHAR_BIT)
 165
 166 #define __JA_ALIGN_MASK(v, mask)        (((v) + (mask)) & ~(mask))
 167 #define JA_ALIGN(v, align)              __JA_ALIGN_MASK(v, (typeof(v)) (align) - 1)
 168 #define __JA_FLOOR_MASK(v, mask)        ((v) & ~(mask))
 169 #define JA_FLOOR(v, align)              __JA_FLOOR_MASK(v, (typeof(v)) (align) - 1)
 170
 171 static
 172 char *align_ptr_size(char *ptr)
 173 {
 174         return JA_ALIGN(ptr, sizeof(ptr));
 175 }
 176
 177 static
 178 struct rcu_ja_node_flag *ja_linear_node_get_nth(const struct rcu_ja_type *type,
 179                                         struct rcu_ja_node *node,
 180                                         uint8_t n)
 181 {
 182         uint8_t nr_child;
 183         uint8_t *values;
 184         struct rcu_ja_node_flag *pointers;
 185         struct rcu_ja_node_flag *ptr;
 186         unsigned int i;
 187
 188         assert(type->type_class == RCU_JA_LINEAR);
 189
 190         nr_child = node->data[0];
 191         cmm_smp_rmb();  /* read nr_child before values */
 192         assert(nr_child <= type->max_child);
 193         assert(nr_child >= type->min_child);
 194
 195         values = &node[1];
 196         for (i = 0; i < nr_child; i++) {
 197                 if (values[i] == n)
 198                         break;
 199         }
 200         if (i >= nr_child)
 201                 return NULL;
 202         cmm_smp_rmb();  /* read values before pointer */
 203         pointers = align_ptr_size(&values[nr_child]);
 204         ptr = pointers[i];
 205         assert(ja_node_ptr(ptr) != NULL);
 206         return ptr;
 207 }
 208
 209 #if 0
 210 /*
 211  * Count hweight. Expect most bits to be 0.  Algorithm from
 212  * Wegner (1960): count those in n steps (n being the number of
 213  * hot bits). Ref.: Wegner, Peter (1960), "A technique for
 214  * counting ones in a binary computer", Communications of the
 215  * ACM 3 (5): 322, doi:10.1145/367236.367286.
 216  */
 217 static
 218 unsigned int ja_hweight_uchar(unsigned char value)
 219 {
 220         unsigned int count = 0;
 221
 222         for (; value; count++)
 223                 value &= value - 1;
 224         return count;
 225 }
 226 #endif //0
 227
 228 #if (CAA_BITS_PER_LONG < 64)
 229 static
 230 unsigned int ja_hweight_ulong(unsigned long value)
 231 {
 232         unsigned long r;
 233
 234         r = value;
 235         r = r - ((r >> 1) & 0x55555555);
 236         r = (r & 0x33333333) + ((r >> 2) & 0x33333333);
 237         r += r >> 4;
 238         r &= 0x0F0F0F0F;
 239         r += r >> 8;
 240         r += r >> 16;
 241         r &= 0x000000FF;
 242         return r;
 243 }
 244 #else /* !(CAA_BITS_PER_LONG < 64) */
 245 static
 246 unsigned int ja_hweight_ulong(unsigned long value)
 247 {
 248         unsigned long r;
 249
 250         r = value;
 251         r = r - ((r >> 1) & 0x5555555555555555UL);
 252         r = (r & 0x3333333333333333UL) + ((r >> 2) & 0x3333333333333333UL);
 253         r += r >> 4;
 254         r &= 0x0F0F0F0F0F0F0F0FUL;
 255         r += r >> 8;
 256         r += r >> 16;
 257         r += r >> 32;
 258         r &= 0x00000000000000FFUL;
 259         return r;
 260 }
 261 #endif /* !(BITS_PER_LONG < 64) */
 262
 263 static
 264 struct rcu_ja_node_flag *ja_bitmap_node_get_nth(const struct rcu_ja_type *type,
 265                                         struct rcu_ja_node *node,
 266                                         uint8_t n)
 267 {
 268         uint8_t *bitmap;
 269         uint8_t byte_nr;
 270         struct rcu_ja_node_flag *pointers;
 271         struct rcu_ja_node_flag *ptr;
 272         unsigned int count;
 273
 274         assert(type->type_class == RCU_JA_BITMAP);
 275
 276         bitmap = &node->data[0];
 277         /*
 278          * Check if n is hot in the bitmap. If yes, count the hweight
 279          * prior to n, including n, to get the pointer index.
 280          * The bitmap goes from least significant (0) to most
 281          * significant (255) as bytes increase.
 282          */
 283         byte_nr = n >> CHAR_BIT_SHIFT;
 284         if (bitmap[byte_nr] & (1U << (n & CHAR_BIT_MASK))) {
 285                 uint8_t byte_iter;
 286                 unsigned long v;
 287
 288                 count = 0;
 289                 /* Count entire ulong prior to the one containing n */
 290                 for (byte_iter = 0; byte_iter < JA_FLOOR(byte_nr, sizeof(unsigned long));
 291                                 byte_iter += sizeof(unsigned long)) {
 292                         v = *((unsigned long *) &bitmap[byte_iter]);
 293                         count += ja_hweight_ulong(v);
 294                 }
 295                 /*
 296                  * Read only the bits prior to and including n within
 297                  * the ulong containing n. ja_bitfield_read_le goes from
 298                  * less significant to most significant as bytes
 299                  * increase.
 300                  */
 301                 ja_bitfield_read_le(
 302                         (unsigned long *) &bitmap[JA_FLOOR(byte_nr, sizeof(unsigned long))],
 303                         unsigned long, 0, (n & ULONG_BIT_MASK) + 1,
 304                         &v);
 305                 count += ja_hweight_ulong(v);
 306         } else {
 307                 return NULL;
 308         }
 309
 310         assert(count <= type->max_child);
 311         assert(count >= type->min_child);
 312
 313         cmm_smp_rmb();  /* read bitmap before pointers */
 314         pointers = &bitmap[JA_BITMAP_LEN];
 315         ptr = pointers[count - 1];
 316         assert(ja_node_ptr(ptr) != NULL);
 317         return ptr;
 318 }
 319
 320 static
 321 struct rcu_ja_node_flag *ja_pigeon_node_get_nth(const struct rcu_ja_type *type,
 322                                         struct rcu_ja_node *node,
 323                                         uint8_t n)
 324 {
 325         assert(type->type_class == RCU_JA_PIGEON);
 326         return ((struct rcu_ja_node_flag *) node->data)[n];
 327 }
 328
 329 /* ja_node_get_nth: get nth item from a node */
 330 static
 331 struct rcu_ja_node_flag *ja_node_get_nth(struct rcu_ja_node_flag *node_flag,
 332                                         uint8_t n)
 333 {
 334         unsigned int type_index;
 335         struct rcu_ja_node *node;
 336         const struct rcu_ja_type *type;
 337
 338         node_flag = rcu_dereference(node_flag);
 339         node = ja_node_ptr(node_flag);
 340         assert(node != NULL);
 341         type_index = ja_node_type(node_flag);
 342         type = &ja_types[type_index];
 343
 344         switch (type->type_class) {
 345         case RCU_JA_LINEAR:
 346                 return ja_linear_node_get_nth(type, node, n);
 347         case RCU_JA_BITMAP:
 348                 return ja_bitmap_node_get_nth(type, node, n);
 349         case RCU_JA_PIGEON:
 350                 return ja_pigeon_node_get_nth(type, node, n);
 351         default:
 352                 assert(0);
 353                 return (void *) -1UL;
 354         }
 355 }
 356
 357 /*
 358  * ja_node_set_nth: set nth item within a node. asserts that it is not
 359  * there yet.
 360  */
 361