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