4 * Userspace RCU library - RCU Judy Array
6 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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.
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.
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
24 #include <urcu/rcuja.h>
25 #include "rcuja-internal.h"
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 */
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 */
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).
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, },
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, },
61 { .type
= RCU_JA_PIGEON
, .max_nr_child
= 256, .node_order
= 10, },
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, },
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, },
74 { .type
= RCU_JA_PIGEON
, .max_nr_child
= 256, .node_order
= 11, },
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 ?
88 struct rcu_ja_node
*create_rcu_ja_node(struct rcu_ja_type_select
*sel
)
90 return zmalloc(1 << sel
->node_order
);
93 void free_rcu_ja_node(struct rcu_ja_node
*node
)