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 | */ |
11 | bool |
12 | rtree_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 | |
30 | static rtree_node_elm_t * |
31 | rtree_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 | |
36 | static rtree_leaf_elm_t * |
37 | rtree_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 | |
42 | static rtree_node_elm_t * |
43 | rtree_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 | |
69 | static rtree_leaf_elm_t * |
70 | rtree_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 | |
95 | static bool |
96 | rtree_node_valid(rtree_node_elm_t *node) { |
97 | return ((uintptr_t)node != (uintptr_t)0); |
98 | } |
99 | |
100 | static bool |
101 | rtree_leaf_valid(rtree_leaf_elm_t *leaf) { |
102 | return ((uintptr_t)leaf != (uintptr_t)0); |
103 | } |
104 | |
105 | static rtree_node_elm_t * |
106 | rtree_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 | |
121 | static rtree_node_elm_t * |
122 | rtree_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 | |
134 | static rtree_leaf_elm_t * |
135 | rtree_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 | |
150 | static rtree_leaf_elm_t * |
151 | rtree_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 | |
163 | rtree_leaf_elm_t * |
164 | rtree_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 | |
249 | void |
250 | rtree_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 | |