Commit | Line | Data |
---|---|---|
db61f215 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 (C) 2000 - 2002 Hewlett-Packard Company | |
10 | * Copyright 2012-2013 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
11 | * | |
12 | * This library is free software; you can redistribute it and/or | |
13 | * modify it under the terms of the GNU Lesser General Public | |
14 | * License as published by the Free Software Foundation; either | |
15 | * version 2.1 of the License, or (at your option) any later version. | |
16 | * | |
17 | * This library is distributed in the hope that it will be useful, | |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | * Lesser General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU Lesser General Public | |
23 | * License along with this library; if not, write to the Free Software | |
24 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
25 | */ | |
26 | ||
27 | #include <pthread.h> | |
28 | #include <stdio.h> | |
29 | #include <inttypes.h> | |
30 | #include <unistd.h> | |
31 | #include <urcu/rculfhash.h> | |
32 | ||
33 | /* | |
34 | * Number of least significant pointer bits reserved to represent the | |
35 | * child type. | |
36 | */ | |
37 | #define JA_TYPE_BITS 3 | |
38 | #define JA_TYPE_MAX_NR (1UL << JA_TYPE_BITS) | |
39 | #define JA_TYPE_MASK (JA_TYPE_MAX_NR - 1) | |
40 | #define JA_PTR_MASK (~JA_TYPE_MASK) | |
41 | ||
42 | #define JA_ENTRY_PER_NODE 256UL | |
43 | #define JA_LOG2_BITS_PER_BYTE 3U | |
44 | #define JA_BITS_PER_BYTE (1U << JA_LOG2_BITS_PER_BYTE) | |
45 | ||
46 | #define JA_POOL_1D_MASK ((JA_BITS_PER_BYTE - 1) << JA_TYPE_BITS) | |
47 | #define JA_POOL_2D_MASK (JA_POOL_1D_MASK << JA_LOG2_BITS_PER_BYTE) | |
48 | ||
49 | #define JA_MAX_DEPTH 9 /* Maximum depth, including leafs */ | |
50 | ||
51 | /* | |
52 | * Entry for NULL node is at index 8 of the table. It is never encoded | |
53 | * in flags. | |
54 | */ | |
55 | #define NODE_INDEX_NULL 8 | |
56 | ||
57 | /* | |
58 | * Number of removals needed on a fallback node before we try to shrink | |
59 | * it. | |
60 | */ | |
61 | #define JA_FALLBACK_REMOVAL_COUNT 8 | |
62 | ||
63 | /* Never declared. Opaque type used to store flagged node pointers. */ | |
64 | struct cds_ja_inode_flag; | |
65 | struct cds_ja_inode; | |
66 | ||
67 | /* | |
68 | * Shadow node contains mutex and call_rcu head associated with a node. | |
69 | */ | |
70 | struct cds_ja_shadow_node { | |
71 | struct cds_lfht_node ht_node; /* hash table node */ | |
72 | struct cds_ja_inode_flag *node_flag; /* reverse mapping and hash table key */ | |
73 | /* | |
74 | * mutual exclusion on all nodes belonging to the same tree | |
75 | * position (e.g. both nodes before and after recompaction | |
76 | * use the same lock). | |
77 | */ | |
78 | pthread_mutex_t *lock; | |
79 | unsigned int nr_child; /* number of children in node */ | |
80 | struct rcu_head head; /* for deferred node and shadow node reclaim */ | |
81 | int fallback_removal_count; /* removals left keeping fallback */ | |
82 | int level; /* level in the tree */ | |
83 | struct cds_ja *ja; /* toplevel judy array */ | |
84 | }; | |
85 | ||
86 | struct cds_ja { | |
87 | struct cds_ja_inode_flag *root; | |
88 | unsigned int tree_depth; | |
89 | uint64_t key_max; | |
90 | /* | |
91 | * We use a hash table to associate node keys to their | |
92 | * respective shadow node. This helps reducing lookup hot path | |
93 | * cache footprint, especially for very small nodes. | |
94 | */ | |
95 | struct cds_lfht *ht; | |
96 | unsigned long nr_fallback; /* Number of fallback nodes used */ | |
97 | ||
98 | /* For debugging */ | |
99 | unsigned long node_fallback_count_distribution[JA_ENTRY_PER_NODE]; | |
100 | unsigned long nr_nodes_allocated, nr_nodes_freed; | |
101 | }; | |
102 | ||
103 | static inline | |
104 | struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node, | |
105 | unsigned long type) | |
106 | { | |
107 | assert(type < (1UL << JA_TYPE_BITS)); | |
108 | return (struct cds_ja_inode_flag *) (((unsigned long) node) | type); | |
109 | } | |
110 | ||
111 | static inline | |
112 | struct cds_ja_inode_flag *ja_node_flag_pool_1d(struct cds_ja_inode *node, | |
113 | unsigned long type, unsigned long bitsel) | |
114 | { | |
115 | assert(type < (1UL << JA_TYPE_BITS)); | |
116 | assert(bitsel < JA_BITS_PER_BYTE); | |
117 | return (struct cds_ja_inode_flag *) (((unsigned long) node) | (bitsel << JA_TYPE_BITS) | type); | |
118 | } | |
119 | ||
120 | static inline | |
121 | struct cds_ja_inode_flag *ja_node_flag_pool_2d(struct cds_ja_inode *node, | |
122 | unsigned long type, unsigned int bitsel[2]) | |
123 | { | |
124 | assert(type < (1UL << JA_TYPE_BITS)); | |
125 | assert(bitsel[0] < JA_BITS_PER_BYTE); | |
126 | assert(bitsel[1] < JA_BITS_PER_BYTE); | |
127 | return (struct cds_ja_inode_flag *) (((unsigned long) node) | (bitsel[0] << (JA_TYPE_BITS + JA_LOG2_BITS_PER_BYTE)) | (bitsel[1] << JA_TYPE_BITS) | type); | |
128 | } | |
129 | ||
130 | static inline | |
131 | unsigned long ja_node_pool_1d_bitsel(struct cds_ja_inode_flag *node) | |
132 | { | |
133 | return ((unsigned long) node & JA_POOL_1D_MASK) >> JA_TYPE_BITS; | |
134 | } | |
135 | ||
136 | static inline | |
137 | void ja_node_pool_2d_bitsel(struct cds_ja_inode_flag *node, unsigned long *bits) | |
138 | { | |
139 | bits[0] = ((unsigned long) node & JA_POOL_2D_MASK) >> (JA_TYPE_BITS + JA_LOG2_BITS_PER_BYTE); | |
140 | bits[1] = ((unsigned long) node & JA_POOL_1D_MASK) >> JA_TYPE_BITS; | |
141 | } | |
142 | ||
143 | /* Hardcoded pool indexes for fast path */ | |
144 | #define RCU_JA_POOL_IDX_5 5 | |
145 | #define RCU_JA_POOL_IDX_6 6 | |
146 | static inline | |
147 | struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) | |
148 | { | |
149 | unsigned long v, type_idx; | |
150 | ||
151 | if (!node) | |
152 | return NULL; /* RCU_JA_NULL */ | |
153 | v = (unsigned long) node; | |
154 | type_idx = v & JA_TYPE_MASK; | |
155 | ||
156 | switch (type_idx) { | |
157 | case RCU_JA_POOL_IDX_5: | |
158 | v &= ~(JA_POOL_1D_MASK | JA_TYPE_MASK); | |
159 | break; | |
160 | case RCU_JA_POOL_IDX_6: | |
161 | v &= ~(JA_POOL_2D_MASK | JA_POOL_1D_MASK | JA_TYPE_MASK); | |
162 | break; | |
163 | default: | |
164 | /* RCU_JA_LINEAR or RCU_JA_PIGEON */ | |
165 | v &= JA_PTR_MASK; | |
166 | break; | |
167 | } | |
168 | return (struct cds_ja_inode *) v; | |
169 | } | |
170 | ||
171 | __attribute__((visibility("protected"))) | |
172 | unsigned long ja_node_type(struct cds_ja_inode_flag *node); | |
173 | ||
174 | __attribute__((visibility("protected"))) | |
175 | void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, | |
176 | struct cds_ja_inode_flag *node_flag); | |
177 | ||
178 | __attribute__((visibility("protected"))) | |
179 | struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, | |
180 | struct cds_ja_inode_flag *node_flag); | |
181 | ||
182 | __attribute__((visibility("protected"))) | |
183 | void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node); | |
184 | ||
185 | __attribute__((visibility("protected"))) | |
186 | struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, | |
187 | struct cds_ja_inode_flag *new_node_flag, | |
188 | struct cds_ja_shadow_node *inherit_from, | |
189 | struct cds_ja *ja, int level); | |
190 | ||
191 | /* rcuja_shadow_clear flags */ | |
192 | enum { | |
193 | RCUJA_SHADOW_CLEAR_FREE_NODE = (1U << 0), | |
194 | RCUJA_SHADOW_CLEAR_FREE_LOCK = (1U << 1), | |
195 | }; | |
196 | ||
197 | __attribute__((visibility("protected"))) | |
198 | int rcuja_shadow_clear(struct cds_lfht *ht, | |
199 | struct cds_ja_inode_flag *node_flag, | |
200 | struct cds_ja_shadow_node *shadow_node, | |
201 | unsigned int flags); | |
202 | ||
203 | __attribute__((visibility("protected"))) | |
204 | void rcuja_shadow_prune(struct cds_lfht *ht, | |
205 | unsigned int flags); | |
206 | ||
207 | __attribute__((visibility("protected"))) | |
208 | struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor); | |
209 | ||
210 | __attribute__((visibility("protected"))) | |
211 | int rcuja_delete_ht(struct cds_lfht *ht); | |
212 | ||
213 | __attribute__((visibility("protected"))) | |
214 | void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node); | |
215 | ||
216 | /* | |
217 | * Iterate through duplicates returned by cds_ja_lookup*() | |
218 | * Receives a struct cds_ja_node * as parameter, which is used as start | |
219 | * of duplicate list and loop cursor. | |
220 | */ | |
221 | #define cds_ja_for_each_duplicate(pos) \ | |
222 | for (; (pos) != NULL; (pos) = (pos)->next) | |
223 | ||
224 | //#define DEBUG | |
225 | //#define DEBUG_COUNTERS | |
226 | ||
227 | #ifdef __linux__ | |
228 | #include <syscall.h> | |
229 | #endif | |
230 | ||
231 | #if defined(_syscall0) | |
232 | _syscall0(pid_t, gettid) | |
233 | #elif defined(__NR_gettid) | |
234 | static inline pid_t gettid(void) | |
235 | { | |
236 | return syscall(__NR_gettid); | |
237 | } | |
238 | #else | |
239 | #warning "use pid as tid" | |
240 | static inline pid_t gettid(void) | |
241 | { | |
242 | return getpid(); | |
243 | } | |
244 | #endif | |
245 | ||
246 | #ifdef DEBUG | |
247 | #define dbg_printf(fmt, args...) \ | |
248 | fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \ | |
249 | (unsigned long) gettid(), __func__, \ | |
250 | __FILE__, __LINE__, ## args) | |
251 | ||
252 | #else | |
253 | #define dbg_printf(fmt, args...) \ | |
254 | do { \ | |
255 | /* do nothing but check printf format */ \ | |
256 | if (0) \ | |
257 | fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \ | |
258 | (unsigned long) gettid(), __func__, \ | |
259 | __FILE__, __LINE__, ## args); \ | |
260 | } while (0) | |
261 | #endif | |
262 | ||
263 | #ifdef DEBUG_COUNTERS | |
264 | static inline | |
265 | int ja_debug_counters(void) | |
266 | { | |
267 | return 1; | |
268 | } | |
269 | #else | |
270 | static inline | |
271 | int ja_debug_counters(void) | |
272 | { | |
273 | return 0; | |
274 | } | |
275 | #endif | |
276 | ||
277 | #endif /* _URCU_RCUJA_INTERNAL_H */ |