1#include "jemalloc/internal/jemalloc_preamble.h"
2#include "jemalloc/internal/jemalloc_internal_includes.h"
3
4#include "jemalloc/internal/assert.h"
5#include "jemalloc/internal/mutex.h"
6
7/*
8 * Only the most significant bits of keys passed to rtree_{read,write}() are
9 * used.
10 */
11bool
12rtree_new(rtree_t *rtree, base_t *base, bool zeroed) {
13#ifdef JEMALLOC_JET
14 if (!zeroed) {
15 memset(rtree, 0, sizeof(rtree_t)); /* Clear root. */
16 }
17#else
18 assert(zeroed);
19#endif
20 rtree->base = base;
21
22 if (malloc_mutex_init(&rtree->init_lock, "rtree", WITNESS_RANK_RTREE,
23 malloc_mutex_rank_exclusive)) {
24 return true;
25 }
26
27 return false;
28}
29
30static rtree_node_elm_t *
31rtree_node_alloc(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) {
32 return (rtree_node_elm_t *)base_alloc(tsdn, rtree->base,
33 nelms * sizeof(rtree_node_elm_t), CACHELINE);
34}
35
36static rtree_leaf_elm_t *
37rtree_leaf_alloc(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) {
38 return (rtree_leaf_elm_t *)base_alloc(tsdn, rtree->base,
39 nelms * sizeof(rtree_leaf_elm_t), CACHELINE);
40}
41
42static rtree_node_elm_t *
43rtree_node_init(tsdn_t *tsdn, rtree_t *rtree, unsigned level,
44 atomic_p_t *elmp) {
45 malloc_mutex_lock(tsdn, &rtree->init_lock);
46 /*
47 * If *elmp is non-null, then it was initialized with the init lock
48 * held, so we can get by with 'relaxed' here.
49 */
50 rtree_node_elm_t *node = atomic_load_p(elmp, ATOMIC_RELAXED);
51 if (node == NULL) {
52 node = rtree_node_alloc(tsdn, rtree, ZU(1) <<
53 rtree_levels[level].bits);
54 if (node == NULL) {
55 malloc_mutex_unlock(tsdn, &rtree->init_lock);
56 return NULL;
57 }
58 /*
59 * Even though we hold the lock, a later reader might not; we
60 * need release semantics.
61 */
62 atomic_store_p(elmp, node, ATOMIC_RELEASE);
63 }
64 malloc_mutex_unlock(tsdn, &rtree->init_lock);
65
66 return node;
67}
68
69static rtree_leaf_elm_t *
70rtree_leaf_init(tsdn_t *tsdn, rtree_t *rtree, atomic_p_t *elmp) {
71 malloc_mutex_lock(tsdn, &rtree->init_lock);
72 /*
73 * If *elmp is non-null, then it was initialized with the init lock
74 * held, so we can get by with 'relaxed' here.
75 */
76 rtree_leaf_elm_t *leaf = atomic_load_p(elmp, ATOMIC_RELAXED);
77 if (leaf == NULL) {
78 leaf = rtree_leaf_alloc(tsdn, rtree, ZU(1) <<
79 rtree_levels[RTREE_HEIGHT-1].bits);
80 if (leaf == NULL) {
81 malloc_mutex_unlock(tsdn, &rtree->init_lock);
82 return NULL;
83 }
84 /*
85 * Even though we hold the lock, a later reader might not; we
86 * need release semantics.
87 */
88 atomic_store_p(elmp, leaf, ATOMIC_RELEASE);
89 }
90 malloc_mutex_unlock(tsdn, &rtree->init_lock);
91
92 return leaf;
93}
94
95static bool
96rtree_node_valid(rtree_node_elm_t *node) {
97 return ((uintptr_t)node != (uintptr_t)0);
98}
99
100static bool
101rtree_leaf_valid(rtree_leaf_elm_t *leaf) {
102 return ((uintptr_t)leaf != (uintptr_t)0);
103}
104
105static rtree_node_elm_t *
106rtree_child_node_tryread(rtree_node_elm_t *elm, bool dependent) {
107 rtree_node_elm_t *node;
108
109 if (dependent) {
110 node = (rtree_node_elm_t *)atomic_load_p(&elm->child,
111 ATOMIC_RELAXED);
112 } else {
113 node = (rtree_node_elm_t *)atomic_load_p(&elm->child,
114 ATOMIC_ACQUIRE);
115 }
116
117 assert(!dependent || node != NULL);
118 return node;
119}
120
121static rtree_node_elm_t *
122rtree_child_node_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm,
123 unsigned level, bool dependent) {
124 rtree_node_elm_t *node;
125
126 node = rtree_child_node_tryread(elm, dependent);
127 if (!dependent && unlikely(!rtree_node_valid(node))) {
128 node = rtree_node_init(tsdn, rtree, level + 1, &elm->child);
129 }
130 assert(!dependent || node != NULL);
131 return node;
132}
133
134static rtree_leaf_elm_t *
135rtree_child_leaf_tryread(rtree_node_elm_t *elm, bool dependent) {
136 rtree_leaf_elm_t *leaf;
137
138 if (dependent) {
139 leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child,
140 ATOMIC_RELAXED);
141 } else {
142 leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child,
143 ATOMIC_ACQUIRE);
144 }
145
146 assert(!dependent || leaf != NULL);
147 return leaf;
148}
149
150static rtree_leaf_elm_t *
151rtree_child_leaf_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm,
152 unsigned level, bool dependent) {
153 rtree_leaf_elm_t *leaf;
154
155 leaf = rtree_child_leaf_tryread(elm, dependent);
156 if (!dependent && unlikely(!rtree_leaf_valid(leaf))) {
157 leaf = rtree_leaf_init(tsdn, rtree, &elm->child);
158 }
159 assert(!dependent || leaf != NULL);
160 return leaf;
161}
162
163rtree_leaf_elm_t *
164rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
165 uintptr_t key, bool dependent, bool init_missing) {
166 rtree_node_elm_t *node;
167 rtree_leaf_elm_t *leaf;
168#if RTREE_HEIGHT > 1
169 node = rtree->root;
170#else
171 leaf = rtree->root;
172#endif
173
174 if (config_debug) {
175 uintptr_t leafkey = rtree_leafkey(key);
176 for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) {
177 assert(rtree_ctx->cache[i].leafkey != leafkey);
178 }
179 for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) {
180 assert(rtree_ctx->l2_cache[i].leafkey != leafkey);
181 }
182 }
183
184#define RTREE_GET_CHILD(level) { \
185 assert(level < RTREE_HEIGHT-1); \
186 if (level != 0 && !dependent && \
187 unlikely(!rtree_node_valid(node))) { \
188 return NULL; \
189 } \
190 uintptr_t subkey = rtree_subkey(key, level); \
191 if (level + 2 < RTREE_HEIGHT) { \
192 node = init_missing ? \
193 rtree_child_node_read(tsdn, rtree, \
194 &node[subkey], level, dependent) : \
195 rtree_child_node_tryread(&node[subkey], \
196 dependent); \
197 } else { \
198 leaf = init_missing ? \
199 rtree_child_leaf_read(tsdn, rtree, \
200 &node[subkey], level, dependent) : \
201 rtree_child_leaf_tryread(&node[subkey], \
202 dependent); \
203 } \
204 }
205 /*
206 * Cache replacement upon hard lookup (i.e. L1 & L2 rtree cache miss):
207 * (1) evict last entry in L2 cache; (2) move the collision slot from L1
208 * cache down to L2; and 3) fill L1.
209 */
210#define RTREE_GET_LEAF(level) { \
211 assert(level == RTREE_HEIGHT-1); \
212 if (!dependent && unlikely(!rtree_leaf_valid(leaf))) { \
213 return NULL; \
214 } \
215 if (RTREE_CTX_NCACHE_L2 > 1) { \
216 memmove(&rtree_ctx->l2_cache[1], \
217 &rtree_ctx->l2_cache[0], \
218 sizeof(rtree_ctx_cache_elm_t) * \
219 (RTREE_CTX_NCACHE_L2 - 1)); \
220 } \
221 size_t slot = rtree_cache_direct_map(key); \
222 rtree_ctx->l2_cache[0].leafkey = \
223 rtree_ctx->cache[slot].leafkey; \
224 rtree_ctx->l2_cache[0].leaf = \
225 rtree_ctx->cache[slot].leaf; \
226 uintptr_t leafkey = rtree_leafkey(key); \
227 rtree_ctx->cache[slot].leafkey = leafkey; \
228 rtree_ctx->cache[slot].leaf = leaf; \
229 uintptr_t subkey = rtree_subkey(key, level); \
230 return &leaf[subkey]; \
231 }
232 if (RTREE_HEIGHT > 1) {
233 RTREE_GET_CHILD(0)
234 }
235 if (RTREE_HEIGHT > 2) {
236 RTREE_GET_CHILD(1)
237 }
238 if (RTREE_HEIGHT > 3) {
239 for (unsigned i = 2; i < RTREE_HEIGHT-1; i++) {
240 RTREE_GET_CHILD(i)
241 }
242 }
243 RTREE_GET_LEAF(RTREE_HEIGHT-1)
244#undef RTREE_GET_CHILD
245#undef RTREE_GET_LEAF
246 not_reached();
247}
248
249void
250rtree_ctx_data_init(rtree_ctx_t *ctx) {
251 for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) {
252 rtree_ctx_cache_elm_t *cache = &ctx->cache[i];
253 cache->leafkey = RTREE_LEAFKEY_INVALID;
254 cache->leaf = NULL;
255 }
256 for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) {
257 rtree_ctx_cache_elm_t *cache = &ctx->l2_cache[i];
258 cache->leafkey = RTREE_LEAFKEY_INVALID;
259 cache->leaf = NULL;
260 }
261}
262