• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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