Commit | Line | Data |
---|---|---|
61009379 MD |
1 | #ifndef _URCU_RCUJA_INTERNAL_H |
2 | #define _URCU_RCUJA_INTERNAL_H | |
3 | ||
4 | /* | |
5 | * rcuja/rcuja-internal.h | |
6 | * | |
7 | * Userspace RCU library - RCU Judy Array Internal Header | |
8 | * | |
9 | * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
10 | * | |
11 | * This library is free software; you can redistribute it and/or | |
12 | * modify it under the terms of the GNU Lesser General Public | |
13 | * License as published by the Free Software Foundation; either | |
14 | * version 2.1 of the License, or (at your option) any later version. | |
15 | * | |
16 | * This library is distributed in the hope that it will be useful, | |
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
19 | * Lesser General Public License for more details. | |
20 | * | |
21 | * You should have received a copy of the GNU Lesser General Public | |
22 | * License along with this library; if not, write to the Free Software | |
23 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
24 | */ | |
25 | ||
511b4dcc | 26 | #include <pthread.h> |
a2a7ff59 MD |
27 | #include <stdio.h> |
28 | #include <inttypes.h> | |
511b4dcc MD |
29 | #include <urcu/rculfhash.h> |
30 | ||
3d8fe307 MD |
31 | /* |
32 | * Number of least significant pointer bits reserved to represent the | |
33 | * child type. | |
34 | */ | |
35 | #define JA_TYPE_BITS 3 | |
36 | #define JA_TYPE_MAX_NR (1UL << JA_TYPE_BITS) | |
37 | #define JA_TYPE_MASK (JA_TYPE_MAX_NR - 1) | |
38 | #define JA_PTR_MASK (~JA_TYPE_MASK) | |
39 | ||
40 | #define JA_ENTRY_PER_NODE 256UL | |
41 | #define JA_LOG2_BITS_PER_BYTE 3U | |
42 | #define JA_BITS_PER_BYTE (1U << JA_LOG2_BITS_PER_BYTE) | |
43 | ||
44 | #define JA_MAX_DEPTH 9 /* Maximum depth, including leafs */ | |
45 | ||
46 | /* | |
47 | * Entry for NULL node is at index 8 of the table. It is never encoded | |
48 | * in flags. | |
49 | */ | |
50 | #define NODE_INDEX_NULL 8 | |
51 | ||
52 | /* | |
53 | * Number of removals needed on a fallback node before we try to shrink | |
54 | * it. | |
55 | */ | |
56 | #define JA_FALLBACK_REMOVAL_COUNT 8 | |
57 | ||
511b4dcc | 58 | /* Never declared. Opaque type used to store flagged node pointers. */ |
b4540e8a | 59 | struct cds_ja_inode_flag; |
3d8fe307 | 60 | struct cds_ja_inode; |
511b4dcc MD |
61 | |
62 | /* | |
63 | * Shadow node contains mutex and call_rcu head associated with a node. | |
64 | */ | |
d96bfb0d | 65 | struct cds_ja_shadow_node { |
d22c185b | 66 | struct cds_lfht_node ht_node; /* hash table node */ |
3d8fe307 | 67 | struct cds_ja_inode_flag *node_flag; /* reverse mapping and hash table key */ |
e1db2db5 MD |
68 | /* |
69 | * mutual exclusion on all nodes belonging to the same tree | |
70 | * position (e.g. both nodes before and after recompaction | |
71 | * use the same lock). | |
72 | */ | |
73 | pthread_mutex_t *lock; | |
74 | unsigned int nr_child; /* number of children in node */ | |
d22c185b | 75 | struct rcu_head head; /* for deferred node and shadow node reclaim */ |
f07b240f | 76 | int fallback_removal_count; /* removals left keeping fallback */ |
3d8fe307 MD |
77 | int level; /* level in the tree */ |
78 | struct cds_ja *ja; /* toplevel judy array */ | |
511b4dcc MD |
79 | }; |
80 | ||
d96bfb0d | 81 | struct cds_ja { |
b4540e8a MD |
82 | struct cds_ja_inode_flag *root; |
83 | unsigned int tree_depth; | |
84 | uint64_t key_max; | |
511b4dcc | 85 | /* |
e1db2db5 MD |
86 | * We use a hash table to associate node keys to their |
87 | * respective shadow node. This helps reducing lookup hot path | |
88 | * cache footprint, especially for very small nodes. | |
511b4dcc MD |
89 | */ |
90 | struct cds_lfht *ht; | |
f07b240f | 91 | unsigned long nr_fallback; /* Number of fallback nodes used */ |
511b4dcc | 92 | }; |
61009379 | 93 | |
3d8fe307 MD |
94 | static inline |
95 | struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node, | |
96 | unsigned long type) | |
97 | { | |
98 | assert(type < (1UL << JA_TYPE_BITS)); | |
99 | return (struct cds_ja_inode_flag *) (((unsigned long) node) | type); | |
100 | } | |
101 | ||
102 | static inline | |
103 | struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) | |
104 | { | |
105 | return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK); | |
106 | } | |
107 | ||
108 | static inline | |
109 | unsigned long ja_node_type(struct cds_ja_inode_flag *node) | |
110 | { | |
111 | unsigned long type; | |
112 | ||
113 | if (ja_node_ptr(node) == NULL) { | |
114 | return NODE_INDEX_NULL; | |
115 | } | |
116 | type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK); | |
117 | assert(type < (1UL << JA_TYPE_BITS)); | |
118 | return type; | |
119 | } | |
120 | ||
121 | __attribute__((visibility("protected"))) | |
122 | void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, | |
123 | struct cds_ja_inode_flag *node_flag, | |
124 | void (*free_node_cb)(struct rcu_head *head)); | |
125 | ||
25fde237 | 126 | __attribute__((visibility("protected"))) |
d96bfb0d | 127 | struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, |
3d8fe307 | 128 | struct cds_ja_inode_flag *node_flag); |
be9a7474 | 129 | |
25fde237 | 130 | __attribute__((visibility("protected"))) |
d96bfb0d | 131 | void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node); |
be9a7474 | 132 | |
25fde237 | 133 | __attribute__((visibility("protected"))) |
f07b240f | 134 | struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, |
3d8fe307 MD |
135 | struct cds_ja_inode_flag *new_node_flag, |
136 | struct cds_ja_shadow_node *inherit_from, | |
137 | struct cds_ja *ja); | |
e1db2db5 MD |
138 | |
139 | /* rcuja_shadow_clear flags */ | |
140 | enum { | |
141 | RCUJA_SHADOW_CLEAR_FREE_NODE = (1U << 0), | |
142 | RCUJA_SHADOW_CLEAR_FREE_LOCK = (1U << 1), | |
143 | }; | |
144 | ||
be9a7474 | 145 | __attribute__((visibility("protected"))) |
e1db2db5 | 146 | int rcuja_shadow_clear(struct cds_lfht *ht, |
3d8fe307 | 147 | struct cds_ja_inode_flag *node_flag, |
a2a7ff59 | 148 | struct cds_ja_shadow_node *shadow_node, |
e1db2db5 | 149 | unsigned int flags); |
be9a7474 MD |
150 | |
151 | __attribute__((visibility("protected"))) | |
152 | void rcuja_shadow_prune(struct cds_lfht *ht, | |
3d8fe307 MD |
153 | unsigned int flags, |
154 | void (*free_node_cb)(struct rcu_head *head)); | |
be9a7474 | 155 | |
25fde237 | 156 | __attribute__((visibility("protected"))) |
5eb692c0 | 157 | struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor); |
be9a7474 | 158 | |
25fde237 | 159 | __attribute__((visibility("protected"))) |
be9a7474 | 160 | int rcuja_delete_ht(struct cds_lfht *ht); |
25fde237 | 161 | |
1a0c0717 | 162 | //#define DEBUG |
a2a7ff59 MD |
163 | |
164 | #ifdef DEBUG | |
165 | #define dbg_printf(fmt, args...) printf("[debug rcuja] " fmt, ## args) | |
166 | #else | |
167 | #define dbg_printf(fmt, args...) \ | |
168 | do { \ | |
169 | /* do nothing but check printf format */ \ | |
170 | if (0) \ | |
171 | printf("[debug rcuja] " fmt, ## args); \ | |
172 | } while (0) | |
173 | #endif | |
174 | ||
61009379 | 175 | #endif /* _URCU_RCUJA_INTERNAL_H */ |