1 #ifndef JEMALLOC_INTERNAL_RTREE_INLINES_H
2 #define JEMALLOC_INTERNAL_RTREE_INLINES_H
3
4 #ifndef JEMALLOC_ENABLE_INLINE
5 unsigned rtree_start_level(const rtree_t *rtree, uintptr_t key);
6 unsigned rtree_ctx_start_level(const rtree_t *rtree,
7 const rtree_ctx_t *rtree_ctx, uintptr_t key);
8 uintptr_t rtree_subkey(rtree_t *rtree, uintptr_t key, unsigned level);
9
10 bool rtree_node_valid(rtree_elm_t *node);
11 rtree_elm_t *rtree_child_tryread(rtree_elm_t *elm, bool dependent);
12 rtree_elm_t *rtree_child_read(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *elm,
13 unsigned level, bool dependent);
14 extent_t *rtree_elm_read(rtree_elm_t *elm, bool dependent);
15 void rtree_elm_write(rtree_elm_t *elm, const extent_t *extent);
16 rtree_elm_t *rtree_subtree_tryread(rtree_t *rtree, unsigned level,
17 bool dependent);
18 rtree_elm_t *rtree_subtree_read(tsdn_t *tsdn, rtree_t *rtree,
19 unsigned level, bool dependent);
20 rtree_elm_t *rtree_elm_lookup(tsdn_t *tsdn, rtree_t *rtree,
21 rtree_ctx_t *rtree_ctx, uintptr_t key, bool dependent, bool init_missing);
22
23 bool rtree_write(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
24 uintptr_t key, const extent_t *extent);
25 extent_t *rtree_read(tsdn_t *tsdn, rtree_t *rtree,
26 rtree_ctx_t *rtree_ctx, uintptr_t key, bool dependent);
27 rtree_elm_t *rtree_elm_acquire(tsdn_t *tsdn, rtree_t *rtree,
28 rtree_ctx_t *rtree_ctx, uintptr_t key, bool dependent, bool init_missing);
29 extent_t *rtree_elm_read_acquired(tsdn_t *tsdn, const rtree_t *rtree,
30 rtree_elm_t *elm);
31 void rtree_elm_write_acquired(tsdn_t *tsdn, const rtree_t *rtree,
32 rtree_elm_t *elm, const extent_t *extent);
33 void rtree_elm_release(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm);
34 void rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
35 uintptr_t key);
36 #endif
37
38 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_RTREE_C_))
39 JEMALLOC_ALWAYS_INLINE unsigned
rtree_start_level(const rtree_t * rtree,uintptr_t key)40 rtree_start_level(const rtree_t *rtree, uintptr_t key)
41 {
42 unsigned start_level;
43
44 if (unlikely(key == 0))
45 return (rtree->height - 1);
46
47 start_level = rtree->start_level[(lg_floor(key) + 1) >>
48 LG_RTREE_BITS_PER_LEVEL];
49 assert(start_level < rtree->height);
50 return (start_level);
51 }
52
53 JEMALLOC_ALWAYS_INLINE unsigned
rtree_ctx_start_level(const rtree_t * rtree,const rtree_ctx_t * rtree_ctx,uintptr_t key)54 rtree_ctx_start_level(const rtree_t *rtree, const rtree_ctx_t *rtree_ctx,
55 uintptr_t key)
56 {
57 unsigned start_level;
58 uintptr_t key_diff;
59
60 /* Compute the difference between old and new lookup keys. */
61 key_diff = key ^ rtree_ctx->key;
62 assert(key_diff != 0); /* Handled in rtree_elm_lookup(). */
63
64 /*
65 * Compute the last traversal path element at which the keys' paths
66 * are the same.
67 */
68 start_level = rtree->start_level[(lg_floor(key_diff) + 1) >>
69 LG_RTREE_BITS_PER_LEVEL];
70 assert(start_level < rtree->height);
71 return (start_level);
72 }
73
74 JEMALLOC_ALWAYS_INLINE uintptr_t
rtree_subkey(rtree_t * rtree,uintptr_t key,unsigned level)75 rtree_subkey(rtree_t *rtree, uintptr_t key, unsigned level)
76 {
77 return ((key >> ((ZU(1) << (LG_SIZEOF_PTR+3)) -
78 rtree->levels[level].cumbits)) & ((ZU(1) <<
79 rtree->levels[level].bits) - 1));
80 }
81
82 JEMALLOC_ALWAYS_INLINE bool
rtree_node_valid(rtree_elm_t * node)83 rtree_node_valid(rtree_elm_t *node)
84 {
85 return ((uintptr_t)node != (uintptr_t)0);
86 }
87
88 JEMALLOC_ALWAYS_INLINE rtree_elm_t *
rtree_child_tryread(rtree_elm_t * elm,bool dependent)89 rtree_child_tryread(rtree_elm_t *elm, bool dependent)
90 {
91 rtree_elm_t *child;
92
93 /* Double-checked read (first read may be stale). */
94 child = elm->child;
95 if (!dependent && !rtree_node_valid(child))
96 child = (rtree_elm_t *)atomic_read_p(&elm->pun);
97 assert(!dependent || child != NULL);
98 return (child);
99 }
100
101 JEMALLOC_ALWAYS_INLINE rtree_elm_t *
rtree_child_read(tsdn_t * tsdn,rtree_t * rtree,rtree_elm_t * elm,unsigned level,bool dependent)102 rtree_child_read(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *elm, unsigned level,
103 bool dependent)
104 {
105 rtree_elm_t *child;
106
107 child = rtree_child_tryread(elm, dependent);
108 if (!dependent && unlikely(!rtree_node_valid(child)))
109 child = rtree_child_read_hard(tsdn, rtree, elm, level);
110 assert(!dependent || child != NULL);
111 return (child);
112 }
113
114 JEMALLOC_ALWAYS_INLINE extent_t *
rtree_elm_read(rtree_elm_t * elm,bool dependent)115 rtree_elm_read(rtree_elm_t *elm, bool dependent)
116 {
117 extent_t *extent;
118
119 if (dependent) {
120 /*
121 * Reading a value on behalf of a pointer to a valid allocation
122 * is guaranteed to be a clean read even without
123 * synchronization, because the rtree update became visible in
124 * memory before the pointer came into existence.
125 */
126 extent = elm->extent;
127 } else {
128 /*
129 * An arbitrary read, e.g. on behalf of ivsalloc(), may not be
130 * dependent on a previous rtree write, which means a stale read
131 * could result if synchronization were omitted here.
132 */
133 extent = (extent_t *)atomic_read_p(&elm->pun);
134 }
135
136 /* Mask the lock bit. */
137 extent = (extent_t *)((uintptr_t)extent & ~((uintptr_t)0x1));
138
139 return (extent);
140 }
141
142 JEMALLOC_INLINE void
rtree_elm_write(rtree_elm_t * elm,const extent_t * extent)143 rtree_elm_write(rtree_elm_t *elm, const extent_t *extent)
144 {
145 atomic_write_p(&elm->pun, extent);
146 }
147
148 JEMALLOC_ALWAYS_INLINE rtree_elm_t *
rtree_subtree_tryread(rtree_t * rtree,unsigned level,bool dependent)149 rtree_subtree_tryread(rtree_t *rtree, unsigned level, bool dependent)
150 {
151 rtree_elm_t *subtree;
152
153 /* Double-checked read (first read may be stale). */
154 subtree = rtree->levels[level].subtree;
155 if (!dependent && unlikely(!rtree_node_valid(subtree))) {
156 subtree = (rtree_elm_t *)atomic_read_p(
157 &rtree->levels[level].subtree_pun);
158 }
159 assert(!dependent || subtree != NULL);
160 return (subtree);
161 }
162
163 JEMALLOC_ALWAYS_INLINE rtree_elm_t *
rtree_subtree_read(tsdn_t * tsdn,rtree_t * rtree,unsigned level,bool dependent)164 rtree_subtree_read(tsdn_t *tsdn, rtree_t *rtree, unsigned level, bool dependent)
165 {
166 rtree_elm_t *subtree;
167
168 subtree = rtree_subtree_tryread(rtree, level, dependent);
169 if (!dependent && unlikely(!rtree_node_valid(subtree)))
170 subtree = rtree_subtree_read_hard(tsdn, rtree, level);
171 assert(!dependent || subtree != NULL);
172 return (subtree);
173 }
174
175 JEMALLOC_ALWAYS_INLINE rtree_elm_t *
rtree_elm_lookup(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent,bool init_missing)176 rtree_elm_lookup(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
177 uintptr_t key, bool dependent, bool init_missing)
178 {
179 uintptr_t subkey;
180 unsigned start_level;
181 rtree_elm_t *node;
182
183 assert(!dependent || !init_missing);
184
185 if (dependent || init_missing) {
186 if (likely(rtree_ctx->valid)) {
187 if (key == rtree_ctx->key)
188 return (rtree_ctx->elms[rtree->height]);
189 else {
190 unsigned no_ctx_start_level =
191 rtree_start_level(rtree, key);
192 unsigned ctx_start_level;
193
194 if (likely(no_ctx_start_level <=
195 rtree_ctx->start_level && (ctx_start_level =
196 rtree_ctx_start_level(rtree, rtree_ctx,
197 key)) >= rtree_ctx->start_level)) {
198 start_level = ctx_start_level;
199 node = rtree_ctx->elms[ctx_start_level];
200 } else {
201 start_level = no_ctx_start_level;
202 node = init_missing ?
203 rtree_subtree_read(tsdn, rtree,
204 no_ctx_start_level, dependent) :
205 rtree_subtree_tryread(rtree,
206 no_ctx_start_level, dependent);
207 rtree_ctx->start_level =
208 no_ctx_start_level;
209 rtree_ctx->elms[no_ctx_start_level] =
210 node;
211 }
212 }
213 } else {
214 unsigned no_ctx_start_level = rtree_start_level(rtree,
215 key);
216
217 start_level = no_ctx_start_level;
218 node = init_missing ? rtree_subtree_read(tsdn, rtree,
219 no_ctx_start_level, dependent) :
220 rtree_subtree_tryread(rtree, no_ctx_start_level,
221 dependent);
222 rtree_ctx->valid = true;
223 rtree_ctx->start_level = no_ctx_start_level;
224 rtree_ctx->elms[no_ctx_start_level] = node;
225 }
226 rtree_ctx->key = key;
227 } else {
228 start_level = rtree_start_level(rtree, key);
229 node = init_missing ? rtree_subtree_read(tsdn, rtree,
230 start_level, dependent) : rtree_subtree_tryread(rtree,
231 start_level, dependent);
232 }
233
234 #define RTREE_GET_BIAS (RTREE_HEIGHT_MAX - rtree->height)
235 switch (start_level + RTREE_GET_BIAS) {
236 #define RTREE_GET_SUBTREE(level) \
237 case level: \
238 assert(level < (RTREE_HEIGHT_MAX-1)); \
239 if (!dependent && unlikely(!rtree_node_valid(node))) { \
240 if (init_missing) \
241 rtree_ctx->valid = false; \
242 return (NULL); \
243 } \
244 subkey = rtree_subkey(rtree, key, level - \
245 RTREE_GET_BIAS); \
246 node = init_missing ? rtree_child_read(tsdn, rtree, \
247 &node[subkey], level - RTREE_GET_BIAS, dependent) : \
248 rtree_child_tryread(&node[subkey], dependent); \
249 if (dependent || init_missing) { \
250 rtree_ctx->elms[level - RTREE_GET_BIAS + 1] = \
251 node; \
252 } \
253 /* Fall through. */
254 #define RTREE_GET_LEAF(level) \
255 case level: \
256 assert(level == (RTREE_HEIGHT_MAX-1)); \
257 if (!dependent && unlikely(!rtree_node_valid(node))) { \
258 if (init_missing) \
259 rtree_ctx->valid = false; \
260 return (NULL); \
261 } \
262 subkey = rtree_subkey(rtree, key, level - \
263 RTREE_GET_BIAS); \
264 /* \
265 * node is a leaf, so it contains values rather than \
266 * child pointers. \
267 */ \
268 node = &node[subkey]; \
269 if (dependent || init_missing) { \
270 rtree_ctx->elms[level - RTREE_GET_BIAS + 1] = \
271 node; \
272 } \
273 return (node);
274 #if RTREE_HEIGHT_MAX > 1
275 RTREE_GET_SUBTREE(0)
276 #endif
277 #if RTREE_HEIGHT_MAX > 2
278 RTREE_GET_SUBTREE(1)
279 #endif
280 #if RTREE_HEIGHT_MAX > 3
281 RTREE_GET_SUBTREE(2)
282 #endif
283 #if RTREE_HEIGHT_MAX > 4
284 RTREE_GET_SUBTREE(3)
285 #endif
286 #if RTREE_HEIGHT_MAX > 5
287 RTREE_GET_SUBTREE(4)
288 #endif
289 #if RTREE_HEIGHT_MAX > 6
290 RTREE_GET_SUBTREE(5)
291 #endif
292 #if RTREE_HEIGHT_MAX > 7
293 RTREE_GET_SUBTREE(6)
294 #endif
295 #if RTREE_HEIGHT_MAX > 8
296 RTREE_GET_SUBTREE(7)
297 #endif
298 #if RTREE_HEIGHT_MAX > 9
299 RTREE_GET_SUBTREE(8)
300 #endif
301 #if RTREE_HEIGHT_MAX > 10
302 RTREE_GET_SUBTREE(9)
303 #endif
304 #if RTREE_HEIGHT_MAX > 11
305 RTREE_GET_SUBTREE(10)
306 #endif
307 #if RTREE_HEIGHT_MAX > 12
308 RTREE_GET_SUBTREE(11)
309 #endif
310 #if RTREE_HEIGHT_MAX > 13
311 RTREE_GET_SUBTREE(12)
312 #endif
313 #if RTREE_HEIGHT_MAX > 14
314 RTREE_GET_SUBTREE(13)
315 #endif
316 #if RTREE_HEIGHT_MAX > 15
317 RTREE_GET_SUBTREE(14)
318 #endif
319 #if RTREE_HEIGHT_MAX > 16
320 # error Unsupported RTREE_HEIGHT_MAX
321 #endif
322 RTREE_GET_LEAF(RTREE_HEIGHT_MAX-1)
323 #undef RTREE_GET_SUBTREE
324 #undef RTREE_GET_LEAF
325 default: not_reached();
326 }
327 #undef RTREE_GET_BIAS
328 not_reached();
329 }
330
331 JEMALLOC_INLINE bool
rtree_write(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,const extent_t * extent)332 rtree_write(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
333 const extent_t *extent)
334 {
335 rtree_elm_t *elm;
336
337 assert(extent != NULL); /* Use rtree_clear() for this case. */
338 assert(((uintptr_t)extent & (uintptr_t)0x1) == (uintptr_t)0x0);
339
340 elm = rtree_elm_lookup(tsdn, rtree, rtree_ctx, key, false, true);
341 if (elm == NULL)
342 return (true);
343 assert(rtree_elm_read(elm, false) == NULL);
344 rtree_elm_write(elm, extent);
345
346 return (false);
347 }
348
349 JEMALLOC_ALWAYS_INLINE extent_t *
rtree_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent)350 rtree_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
351 bool dependent)
352 {
353 rtree_elm_t *elm;
354
355 elm = rtree_elm_lookup(tsdn, rtree, rtree_ctx, key, dependent, false);
356 if (elm == NULL)
357 return (NULL);
358
359 return (rtree_elm_read(elm, dependent));
360 }
361
362 JEMALLOC_INLINE rtree_elm_t *
rtree_elm_acquire(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent,bool init_missing)363 rtree_elm_acquire(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
364 uintptr_t key, bool dependent, bool init_missing)
365 {
366 rtree_elm_t *elm;
367
368 elm = rtree_elm_lookup(tsdn, rtree, rtree_ctx, key, dependent,
369 init_missing);
370 if (!dependent && elm == NULL)
371 return (NULL);
372 {
373 extent_t *extent;
374 void *s;
375
376 do {
377 extent = rtree_elm_read(elm, false);
378 /* The least significant bit serves as a lock. */
379 s = (void *)((uintptr_t)extent | (uintptr_t)0x1);
380 } while (atomic_cas_p(&elm->pun, (void *)extent, s));
381 }
382
383 if (config_debug)
384 rtree_elm_witness_acquire(tsdn, rtree, key, elm);
385
386 return (elm);
387 }
388
389 JEMALLOC_INLINE extent_t *
rtree_elm_read_acquired(tsdn_t * tsdn,const rtree_t * rtree,rtree_elm_t * elm)390 rtree_elm_read_acquired(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm)
391 {
392 extent_t *extent;
393
394 assert(((uintptr_t)elm->pun & (uintptr_t)0x1) == (uintptr_t)0x1);
395 extent = (extent_t *)((uintptr_t)elm->pun & ~((uintptr_t)0x1));
396 assert(((uintptr_t)extent & (uintptr_t)0x1) == (uintptr_t)0x0);
397
398 if (config_debug)
399 rtree_elm_witness_access(tsdn, rtree, elm);
400
401 return (extent);
402 }
403
404 JEMALLOC_INLINE void
rtree_elm_write_acquired(tsdn_t * tsdn,const rtree_t * rtree,rtree_elm_t * elm,const extent_t * extent)405 rtree_elm_write_acquired(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm,
406 const extent_t *extent)
407 {
408 assert(((uintptr_t)extent & (uintptr_t)0x1) == (uintptr_t)0x0);
409 assert(((uintptr_t)elm->pun & (uintptr_t)0x1) == (uintptr_t)0x1);
410
411 if (config_debug)
412 rtree_elm_witness_access(tsdn, rtree, elm);
413
414 elm->pun = (void *)((uintptr_t)extent | (uintptr_t)0x1);
415 assert(rtree_elm_read_acquired(tsdn, rtree, elm) == extent);
416 }
417
418 JEMALLOC_INLINE void
rtree_elm_release(tsdn_t * tsdn,const rtree_t * rtree,rtree_elm_t * elm)419 rtree_elm_release(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm)
420 {
421 rtree_elm_write(elm, rtree_elm_read_acquired(tsdn, rtree, elm));
422 if (config_debug)
423 rtree_elm_witness_release(tsdn, rtree, elm);
424 }
425
426 JEMALLOC_INLINE void
rtree_clear(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key)427 rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key)
428 {
429 rtree_elm_t *elm;
430
431 elm = rtree_elm_acquire(tsdn, rtree, rtree_ctx, key, true, false);
432 rtree_elm_write_acquired(tsdn, rtree, elm, NULL);
433 rtree_elm_release(tsdn, rtree, elm);
434 }
435 #endif
436
437 #endif /* JEMALLOC_INTERNAL_RTREE_INLINES_H */
438