1 /*
2 * This radix tree implementation is tailored to the singular purpose of
3 * associating metadata with chunks that are currently owned by jemalloc.
4 *
5 *******************************************************************************
6 */
7 #ifdef JEMALLOC_H_TYPES
8
9 typedef struct rtree_node_elm_s rtree_node_elm_t;
10 typedef struct rtree_level_s rtree_level_t;
11 typedef struct rtree_s rtree_t;
12
13 /*
14 * RTREE_BITS_PER_LEVEL must be a power of two that is no larger than the
15 * machine address width.
16 */
17 #define LG_RTREE_BITS_PER_LEVEL 4
18 #define RTREE_BITS_PER_LEVEL (1U << LG_RTREE_BITS_PER_LEVEL)
19 /* Maximum rtree height. */
20 #define RTREE_HEIGHT_MAX \
21 ((1U << (LG_SIZEOF_PTR+3)) / RTREE_BITS_PER_LEVEL)
22
23 /* Used for two-stage lock-free node initialization. */
24 #define RTREE_NODE_INITIALIZING ((rtree_node_elm_t *)0x1)
25
26 /*
27 * The node allocation callback function's argument is the number of contiguous
28 * rtree_node_elm_t structures to allocate, and the resulting memory must be
29 * zeroed.
30 */
31 typedef rtree_node_elm_t *(rtree_node_alloc_t)(size_t);
32 typedef void (rtree_node_dalloc_t)(rtree_node_elm_t *);
33
34 #endif /* JEMALLOC_H_TYPES */
35 /******************************************************************************/
36 #ifdef JEMALLOC_H_STRUCTS
37
38 struct rtree_node_elm_s {
39 union {
40 void *pun;
41 rtree_node_elm_t *child;
42 extent_node_t *val;
43 };
44 };
45
46 struct rtree_level_s {
47 /*
48 * A non-NULL subtree points to a subtree rooted along the hypothetical
49 * path to the leaf node corresponding to key 0. Depending on what keys
50 * have been used to store to the tree, an arbitrary combination of
51 * subtree pointers may remain NULL.
52 *
53 * Suppose keys comprise 48 bits, and LG_RTREE_BITS_PER_LEVEL is 4.
54 * This results in a 3-level tree, and the leftmost leaf can be directly
55 * accessed via subtrees[2], the subtree prefixed by 0x0000 (excluding
56 * 0x00000000) can be accessed via subtrees[1], and the remainder of the
57 * tree can be accessed via subtrees[0].
58 *
59 * levels[0] : [<unused> | 0x0001******** | 0x0002******** | ...]
60 *
61 * levels[1] : [<unused> | 0x00000001**** | 0x00000002**** | ... ]
62 *
63 * levels[2] : [val(0x000000000000) | val(0x000000000001) | ...]
64 *
65 * This has practical implications on x64, which currently uses only the
66 * lower 47 bits of virtual address space in userland, thus leaving
67 * subtrees[0] unused and avoiding a level of tree traversal.
68 */
69 union {
70 void *subtree_pun;
71 rtree_node_elm_t *subtree;
72 };
73 /* Number of key bits distinguished by this level. */
74 unsigned bits;
75 /*
76 * Cumulative number of key bits distinguished by traversing to
77 * corresponding tree level.
78 */
79 unsigned cumbits;
80 };
81
82 struct rtree_s {
83 rtree_node_alloc_t *alloc;
84 rtree_node_dalloc_t *dalloc;
85 unsigned height;
86 /*
87 * Precomputed table used to convert from the number of leading 0 key
88 * bits to which subtree level to start at.
89 */
90 unsigned start_level[RTREE_HEIGHT_MAX];
91 rtree_level_t levels[RTREE_HEIGHT_MAX];
92 };
93
94 #endif /* JEMALLOC_H_STRUCTS */
95 /******************************************************************************/
96 #ifdef JEMALLOC_H_EXTERNS
97
98 bool rtree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc,
99 rtree_node_dalloc_t *dalloc);
100 void rtree_delete(rtree_t *rtree);
101 rtree_node_elm_t *rtree_subtree_read_hard(rtree_t *rtree,
102 unsigned level);
103 rtree_node_elm_t *rtree_child_read_hard(rtree_t *rtree,
104 rtree_node_elm_t *elm, unsigned level);
105
106 #endif /* JEMALLOC_H_EXTERNS */
107 /******************************************************************************/
108 #ifdef JEMALLOC_H_INLINES
109
110 #ifndef JEMALLOC_ENABLE_INLINE
111 unsigned rtree_start_level(rtree_t *rtree, uintptr_t key);
112 uintptr_t rtree_subkey(rtree_t *rtree, uintptr_t key, unsigned level);
113
114 bool rtree_node_valid(rtree_node_elm_t *node);
115 rtree_node_elm_t *rtree_child_tryread(rtree_node_elm_t *elm,
116 bool dependent);
117 rtree_node_elm_t *rtree_child_read(rtree_t *rtree, rtree_node_elm_t *elm,
118 unsigned level, bool dependent);
119 extent_node_t *rtree_val_read(rtree_t *rtree, rtree_node_elm_t *elm,
120 bool dependent);
121 void rtree_val_write(rtree_t *rtree, rtree_node_elm_t *elm,
122 const extent_node_t *val);
123 rtree_node_elm_t *rtree_subtree_tryread(rtree_t *rtree, unsigned level,
124 bool dependent);
125 rtree_node_elm_t *rtree_subtree_read(rtree_t *rtree, unsigned level,
126 bool dependent);
127
128 extent_node_t *rtree_get(rtree_t *rtree, uintptr_t key, bool dependent);
129 bool rtree_set(rtree_t *rtree, uintptr_t key, const extent_node_t *val);
130 #endif
131
132 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_RTREE_C_))
133 JEMALLOC_ALWAYS_INLINE unsigned
rtree_start_level(rtree_t * rtree,uintptr_t key)134 rtree_start_level(rtree_t *rtree, uintptr_t key)
135 {
136 unsigned start_level;
137
138 if (unlikely(key == 0))
139 return (rtree->height - 1);
140
141 start_level = rtree->start_level[lg_floor(key) >>
142 LG_RTREE_BITS_PER_LEVEL];
143 assert(start_level < rtree->height);
144 return (start_level);
145 }
146
147 JEMALLOC_ALWAYS_INLINE uintptr_t
rtree_subkey(rtree_t * rtree,uintptr_t key,unsigned level)148 rtree_subkey(rtree_t *rtree, uintptr_t key, unsigned level)
149 {
150
151 return ((key >> ((ZU(1) << (LG_SIZEOF_PTR+3)) -
152 rtree->levels[level].cumbits)) & ((ZU(1) <<
153 rtree->levels[level].bits) - 1));
154 }
155
156 JEMALLOC_ALWAYS_INLINE bool
rtree_node_valid(rtree_node_elm_t * node)157 rtree_node_valid(rtree_node_elm_t *node)
158 {
159
160 return ((uintptr_t)node > (uintptr_t)RTREE_NODE_INITIALIZING);
161 }
162
163 JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
rtree_child_tryread(rtree_node_elm_t * elm,bool dependent)164 rtree_child_tryread(rtree_node_elm_t *elm, bool dependent)
165 {
166 rtree_node_elm_t *child;
167
168 /* Double-checked read (first read may be stale. */
169 child = elm->child;
170 if (!dependent && !rtree_node_valid(child))
171 child = atomic_read_p(&elm->pun);
172 assert(!dependent || child != NULL);
173 return (child);
174 }
175
176 JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
rtree_child_read(rtree_t * rtree,rtree_node_elm_t * elm,unsigned level,bool dependent)177 rtree_child_read(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level,
178 bool dependent)
179 {
180 rtree_node_elm_t *child;
181
182 child = rtree_child_tryread(elm, dependent);
183 if (!dependent && unlikely(!rtree_node_valid(child)))
184 child = rtree_child_read_hard(rtree, elm, level);
185 assert(!dependent || child != NULL);
186 return (child);
187 }
188
189 JEMALLOC_ALWAYS_INLINE extent_node_t *
rtree_val_read(rtree_t * rtree,rtree_node_elm_t * elm,bool dependent)190 rtree_val_read(rtree_t *rtree, rtree_node_elm_t *elm, bool dependent)
191 {
192
193 if (dependent) {
194 /*
195 * Reading a val on behalf of a pointer to a valid allocation is
196 * guaranteed to be a clean read even without synchronization,
197 * because the rtree update became visible in memory before the
198 * pointer came into existence.
199 */
200 return (elm->val);
201 } else {
202 /*
203 * An arbitrary read, e.g. on behalf of ivsalloc(), may not be
204 * dependent on a previous rtree write, which means a stale read
205 * could result if synchronization were omitted here.
206 */
207 return (atomic_read_p(&elm->pun));
208 }
209 }
210
211 JEMALLOC_INLINE void
rtree_val_write(rtree_t * rtree,rtree_node_elm_t * elm,const extent_node_t * val)212 rtree_val_write(rtree_t *rtree, rtree_node_elm_t *elm, const extent_node_t *val)
213 {
214
215 atomic_write_p(&elm->pun, val);
216 }
217
218 JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
rtree_subtree_tryread(rtree_t * rtree,unsigned level,bool dependent)219 rtree_subtree_tryread(rtree_t *rtree, unsigned level, bool dependent)
220 {
221 rtree_node_elm_t *subtree;
222
223 /* Double-checked read (first read may be stale. */
224 subtree = rtree->levels[level].subtree;
225 if (!dependent && unlikely(!rtree_node_valid(subtree)))
226 subtree = atomic_read_p(&rtree->levels[level].subtree_pun);
227 assert(!dependent || subtree != NULL);
228 return (subtree);
229 }
230
231 JEMALLOC_ALWAYS_INLINE rtree_node_elm_t *
rtree_subtree_read(rtree_t * rtree,unsigned level,bool dependent)232 rtree_subtree_read(rtree_t *rtree, unsigned level, bool dependent)
233 {
234 rtree_node_elm_t *subtree;
235
236 subtree = rtree_subtree_tryread(rtree, level, dependent);
237 if (!dependent && unlikely(!rtree_node_valid(subtree)))
238 subtree = rtree_subtree_read_hard(rtree, level);
239 assert(!dependent || subtree != NULL);
240 return (subtree);
241 }
242
243 JEMALLOC_ALWAYS_INLINE extent_node_t *
rtree_get(rtree_t * rtree,uintptr_t key,bool dependent)244 rtree_get(rtree_t *rtree, uintptr_t key, bool dependent)
245 {
246 uintptr_t subkey;
247 unsigned start_level;
248 rtree_node_elm_t *node;
249
250 start_level = rtree_start_level(rtree, key);
251
252 node = rtree_subtree_tryread(rtree, start_level, dependent);
253 #define RTREE_GET_BIAS (RTREE_HEIGHT_MAX - rtree->height)
254 switch (start_level + RTREE_GET_BIAS) {
255 #define RTREE_GET_SUBTREE(level) \
256 case level: \
257 assert(level < (RTREE_HEIGHT_MAX-1)); \
258 if (!dependent && unlikely(!rtree_node_valid(node))) \
259 return (NULL); \
260 subkey = rtree_subkey(rtree, key, level - \
261 RTREE_GET_BIAS); \
262 node = rtree_child_tryread(&node[subkey], dependent); \
263 /* Fall through. */
264 #define RTREE_GET_LEAF(level) \
265 case level: \
266 assert(level == (RTREE_HEIGHT_MAX-1)); \
267 if (!dependent && unlikely(!rtree_node_valid(node))) \
268 return (NULL); \
269 subkey = rtree_subkey(rtree, key, level - \
270 RTREE_GET_BIAS); \
271 /* \
272 * node is a leaf, so it contains values rather than \
273 * child pointers. \
274 */ \
275 return (rtree_val_read(rtree, &node[subkey], \
276 dependent));
277 #if RTREE_HEIGHT_MAX > 1
278 RTREE_GET_SUBTREE(0)
279 #endif
280 #if RTREE_HEIGHT_MAX > 2
281 RTREE_GET_SUBTREE(1)
282 #endif
283 #if RTREE_HEIGHT_MAX > 3
284 RTREE_GET_SUBTREE(2)
285 #endif
286 #if RTREE_HEIGHT_MAX > 4
287 RTREE_GET_SUBTREE(3)
288 #endif
289 #if RTREE_HEIGHT_MAX > 5
290 RTREE_GET_SUBTREE(4)
291 #endif
292 #if RTREE_HEIGHT_MAX > 6
293 RTREE_GET_SUBTREE(5)
294 #endif
295 #if RTREE_HEIGHT_MAX > 7
296 RTREE_GET_SUBTREE(6)
297 #endif
298 #if RTREE_HEIGHT_MAX > 8
299 RTREE_GET_SUBTREE(7)
300 #endif
301 #if RTREE_HEIGHT_MAX > 9
302 RTREE_GET_SUBTREE(8)
303 #endif
304 #if RTREE_HEIGHT_MAX > 10
305 RTREE_GET_SUBTREE(9)
306 #endif
307 #if RTREE_HEIGHT_MAX > 11
308 RTREE_GET_SUBTREE(10)
309 #endif
310 #if RTREE_HEIGHT_MAX > 12
311 RTREE_GET_SUBTREE(11)
312 #endif
313 #if RTREE_HEIGHT_MAX > 13
314 RTREE_GET_SUBTREE(12)
315 #endif
316 #if RTREE_HEIGHT_MAX > 14
317 RTREE_GET_SUBTREE(13)
318 #endif
319 #if RTREE_HEIGHT_MAX > 15
320 RTREE_GET_SUBTREE(14)
321 #endif
322 #if RTREE_HEIGHT_MAX > 16
323 # error Unsupported RTREE_HEIGHT_MAX
324 #endif
325 RTREE_GET_LEAF(RTREE_HEIGHT_MAX-1)
326 #undef RTREE_GET_SUBTREE
327 #undef RTREE_GET_LEAF
328 default: not_reached();
329 }
330 #undef RTREE_GET_BIAS
331 not_reached();
332 }
333
334 JEMALLOC_INLINE bool
rtree_set(rtree_t * rtree,uintptr_t key,const extent_node_t * val)335 rtree_set(rtree_t *rtree, uintptr_t key, const extent_node_t *val)
336 {
337 uintptr_t subkey;
338 unsigned i, start_level;
339 rtree_node_elm_t *node, *child;
340
341 start_level = rtree_start_level(rtree, key);
342
343 node = rtree_subtree_read(rtree, start_level, false);
344 if (node == NULL)
345 return (true);
346 for (i = start_level; /**/; i++, node = child) {
347 subkey = rtree_subkey(rtree, key, i);
348 if (i == rtree->height - 1) {
349 /*
350 * node is a leaf, so it contains values rather than
351 * child pointers.
352 */
353 rtree_val_write(rtree, &node[subkey], val);
354 return (false);
355 }
356 assert(i + 1 < rtree->height);
357 child = rtree_child_read(rtree, &node[subkey], i, false);
358 if (child == NULL)
359 return (true);
360 }
361 not_reached();
362 }
363 #endif
364
365 #endif /* JEMALLOC_H_INLINES */
366 /******************************************************************************/
367