rtree.h revision 7427525c28d58c423a68930160e3b0fe577fe953 
1/*
2 * This radix tree implementation is tailored to the singular purpose of
3 * tracking which chunks are currently owned by jemalloc.  This functionality
4 * is mandatory for OS X, where jemalloc must be able to respond to object
5 * ownership queries.
6 *
7 *******************************************************************************
8 */
9#ifdef JEMALLOC_H_TYPES
10
11typedef struct rtree_s rtree_t;
12
13/*
14 * Size of each radix tree node (must be a power of 2).  This impacts tree
15 * depth.
16 */
17#if (LG_SIZEOF_PTR == 2)
18#  define RTREE_NODESIZE (1U << 14)
19#else
20#  define RTREE_NODESIZE CACHELINE
21#endif
22
23#endif /* JEMALLOC_H_TYPES */
24/******************************************************************************/
25#ifdef JEMALLOC_H_STRUCTS
26
27struct rtree_s {
28	malloc_mutex_t	mutex;
29	void		**root;
30	unsigned	height;
31	unsigned	level2bits[1]; /* Dynamically sized. */
32};
33
34#endif /* JEMALLOC_H_STRUCTS */
35/******************************************************************************/
36#ifdef JEMALLOC_H_EXTERNS
37
38rtree_t	*rtree_new(unsigned bits);
39
40#endif /* JEMALLOC_H_EXTERNS */
41/******************************************************************************/
42#ifdef JEMALLOC_H_INLINES
43
44#ifndef JEMALLOC_ENABLE_INLINE
45#ifndef JEMALLOC_DEBUG
46void	*rtree_get_locked(rtree_t *rtree, uintptr_t key);
47#endif
48void	*rtree_get(rtree_t *rtree, uintptr_t key);
49bool	rtree_set(rtree_t *rtree, uintptr_t key, void *val);
50#endif
51
52#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_RTREE_C_))
53#define	RTREE_GET_GENERATE(f)						\
54/* The least significant bits of the key are ignored. */		\
55JEMALLOC_INLINE void *							\
56f(rtree_t *rtree, uintptr_t key)					\
57{									\
58	void *ret;							\
59	uintptr_t subkey;						\
60	unsigned i, lshift, height, bits;				\
61	void **node, **child;						\
62									\
63	RTREE_LOCK(&rtree->mutex);					\
64	for (i = lshift = 0, height = rtree->height, node = rtree->root;\
65	    i < height - 1;						\
66	    i++, lshift += bits, node = child) {			\
67		bits = rtree->level2bits[i];				\
68		subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR + \
69		    3)) - bits);					\
70		child = (void**)node[subkey];				\
71		if (child == NULL) {					\
72			RTREE_UNLOCK(&rtree->mutex);			\
73			return (NULL);					\
74		}							\
75	}								\
76									\
77	/*								\
78	 * node is a leaf, so it contains values rather than node	\
79	 * pointers.							\
80	 */								\
81	bits = rtree->level2bits[i];					\
82	subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) -	\
83	    bits);							\
84	ret = node[subkey];						\
85	RTREE_UNLOCK(&rtree->mutex);					\
86									\
87	RTREE_GET_VALIDATE						\
88	return (ret);							\
89}
90
91#ifdef JEMALLOC_DEBUG
92#  define RTREE_LOCK(l)		malloc_mutex_lock(l)
93#  define RTREE_UNLOCK(l)	malloc_mutex_unlock(l)
94#  define RTREE_GET_VALIDATE
95RTREE_GET_GENERATE(rtree_get_locked)
96#  undef RTREE_LOCK
97#  undef RTREE_UNLOCK
98#  undef RTREE_GET_VALIDATE
99#endif
100
101#define	RTREE_LOCK(l)
102#define	RTREE_UNLOCK(l)
103#ifdef JEMALLOC_DEBUG
104   /*
105    * Suppose that it were possible for a jemalloc-allocated chunk to be
106    * munmap()ped, followed by a different allocator in another thread re-using
107    * overlapping virtual memory, all without invalidating the cached rtree
108    * value.  The result would be a false positive (the rtree would claim that
109    * jemalloc owns memory that it had actually discarded).  This scenario
110    * seems impossible, but the following assertion is a prudent sanity check.
111    */
112#  define RTREE_GET_VALIDATE						\
113	assert(rtree_get_locked(rtree, key) == ret);
114#else
115#  define RTREE_GET_VALIDATE
116#endif
117RTREE_GET_GENERATE(rtree_get)
118#undef RTREE_LOCK
119#undef RTREE_UNLOCK
120#undef RTREE_GET_VALIDATE
121
122JEMALLOC_INLINE bool
123rtree_set(rtree_t *rtree, uintptr_t key, void *val)
124{
125	uintptr_t subkey;
126	unsigned i, lshift, height, bits;
127	void **node, **child;
128
129	malloc_mutex_lock(&rtree->mutex);
130	for (i = lshift = 0, height = rtree->height, node = rtree->root;
131	    i < height - 1;
132	    i++, lshift += bits, node = child) {
133		bits = rtree->level2bits[i];
134		subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) -
135		    bits);
136		child = (void**)node[subkey];
137		if (child == NULL) {
138			child = (void**)base_alloc(sizeof(void *) <<
139			    rtree->level2bits[i+1]);
140			if (child == NULL) {
141				malloc_mutex_unlock(&rtree->mutex);
142				return (true);
143			}
144			memset(child, 0, sizeof(void *) <<
145			    rtree->level2bits[i+1]);
146			node[subkey] = child;
147		}
148	}
149
150	/* node is a leaf, so it contains values rather than node pointers. */
151	bits = rtree->level2bits[i];
152	subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) - bits);
153	node[subkey] = val;
154	malloc_mutex_unlock(&rtree->mutex);
155
156	return (false);
157}
158#endif
159
160#endif /* JEMALLOC_H_INLINES */
161/******************************************************************************/
162