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 <urcu/rcuja.h>
  25 #include "rcuja-internal.h"
  26
  27 enum rcu_ja_child_type {
  28         RCU_JA_LINEAR = 0,      /* Type A */
  29                         /* 32-bit: 1 to 12 children, 8 to 64 bytes */
  30                         /* 64-bit: 1 to 14 children, 16 to 128 bytes */
  31         RCU_JA_BITMAP = 1,      /* Type B */
  32                         /* 32-bit: 13 to 120 children, 128 to 512 bytes */
  33                         /* 64-bit: 15 to 124 children, 256 to 1024 bytes */
  34         RCU_JA_PIGEON = 2,      /* Type C */
  35                         /* 32-bit: 121 to 256 children, 1024 bytes */
  36                         /* 64-bit: 125 to 256 children, 2048 bytes */
  37         /* Leaf nodes are implicit from their height in the tree */
  38 };
  39
  40 struct rcu_ja_type_select {
  41         enum rcu_ja_child_type type;
  42         uint16_t max_nr_child;  /* 1 to 256 */
  43         uint16_t node_order;    /* node size is (1 << node_order), in bytes */
  44 };
  45
  46 /*
  47  * Iteration on the array to find the right node size for the number of
  48  * children stops when it reaches max_nr_child == 0 (this is the largest
  49  * possible node size, which contains 256 children).
  50  */
  51 const struct rcu_ja_type_select ja_select_u32[] = {
  52         { .type = RCU_JA_LINEAR, .max_nr_child = 1, .node_order = 3, },
  53         { .type = RCU_JA_LINEAR, .max_nr_child = 3, .node_order = 4, },
  54         { .type = RCU_JA_LINEAR, .max_nr_child = 6, .node_order = 5, },
  55         { .type = RCU_JA_LINEAR, .max_nr_child = 12, .node_order = 6, },
  56
  57         { .type = RCU_JA_BITMAP, .max_nr_child = 24, .node_order = 7, },
  58         { .type = RCU_JA_BITMAP, .max_nr_child = 56, .node_order = 8, },
  59         { .type = RCU_JA_BITMAP, .max_nr_child = 120, .node_order = 9, },
  60
  61         { .type = RCU_JA_PIGEON, .max_nr_child = 256, .node_order = 10, },
  62 };
  63
  64 const struct rcu_ja_type_select ja_select_u64[] = {
  65         { .type = RCU_JA_LINEAR, .max_nr_child = 1, .node_order = 4, },
  66         { .type = RCU_JA_LINEAR, .max_nr_child = 3, .node_order = 5, },
  67         { .type = RCU_JA_LINEAR, .max_nr_child = 7, .node_order = 6, },
  68         { .type = RCU_JA_LINEAR, .max_nr_child = 14, .node_order = 7, },
  69
  70         { .type = RCU_JA_BITMAP, .max_nr_child = 28, .node_order = 8, },
  71         { .type = RCU_JA_BITMAP, .max_nr_child = 60, .node_order = 9, },
  72         { .type = RCU_JA_BITMAP, .max_nr_child = 124, .node_order = 10, },
  73
  74         { .type = RCU_JA_PIGEON, .max_nr_child = 256, .node_order = 11, },
  75 };
  76
  77 /*
  78  * The rcu_ja_node starts with a byte counting the number of children in
  79  * the node. Then, the node-specific data is placed.
  80  * TODO: where should we put the mutex for the node ?
  81  *  -> mutex could be a 0-value node count.
  82  * TODO: where do we keep nr children for pigeon ?
  83  */
  84 struct rcu_ja_node {
  85         char data[];
  86 };
  87
  88 struct rcu_ja_node *create_rcu_ja_node(struct rcu_ja_type_select *sel)
  89 {
  90         return zmalloc(1 << sel->node_order);
  91 }
  92
  93 void free_rcu_ja_node(struct rcu_ja_node *node)
  94 {
  95         free(node);
  96 }
  97
  98
  99