[redis.git] / deps / jemalloc.orig / include / jemalloc / internal / rtree.h

/*
 * This radix tree implementation is tailored to the singular purpose of
 * tracking which chunks are currently owned by jemalloc.  This functionality
 * is mandatory for OS X, where jemalloc must be able to respond to object
 * ownership queries.
 *
 *******************************************************************************
 */
#ifdef JEMALLOC_H_TYPES

typedef struct rtree_s rtree_t;

/*
 * Size of each radix tree node (must be a power of 2).  This impacts tree
 * depth.
 */
#if (LG_SIZEOF_PTR == 2)
#  define RTREE_NODESIZE (1U << 14)
#else
#  define RTREE_NODESIZE CACHELINE
#endif

#endif /* JEMALLOC_H_TYPES */
/******************************************************************************/
#ifdef JEMALLOC_H_STRUCTS

struct rtree_s {
	malloc_mutex_t	mutex;
	void		**root;
	unsigned	height;
	unsigned	level2bits[1]; /* Dynamically sized. */
};

#endif /* JEMALLOC_H_STRUCTS */
/******************************************************************************/
#ifdef JEMALLOC_H_EXTERNS

rtree_t	*rtree_new(unsigned bits);

#endif /* JEMALLOC_H_EXTERNS */
/******************************************************************************/
#ifdef JEMALLOC_H_INLINES

#ifndef JEMALLOC_ENABLE_INLINE
#ifndef JEMALLOC_DEBUG
void	*rtree_get_locked(rtree_t *rtree, uintptr_t key);
#endif
void	*rtree_get(rtree_t *rtree, uintptr_t key);
bool	rtree_set(rtree_t *rtree, uintptr_t key, void *val);
#endif

#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_RTREE_C_))
#define	RTREE_GET_GENERATE(f)						\
/* The least significant bits of the key are ignored. */		\
JEMALLOC_INLINE void *							\
f(rtree_t *rtree, uintptr_t key)					\
{									\
	void *ret;							\
	uintptr_t subkey;						\
	unsigned i, lshift, height, bits;				\
	void **node, **child;						\
									\
	RTREE_LOCK(&rtree->mutex);					\
	for (i = lshift = 0, height = rtree->height, node = rtree->root;\
	    i < height - 1;						\
	    i++, lshift += bits, node = child) {			\
		bits = rtree->level2bits[i];				\
		subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR + \
		    3)) - bits);					\
		child = (void**)node[subkey];				\
		if (child == NULL) {					\
			RTREE_UNLOCK(&rtree->mutex);			\
			return (NULL);					\
		}							\
	}								\
									\
	/*								\
	 * node is a leaf, so it contains values rather than node	\
	 * pointers.							\
	 */								\
	bits = rtree->level2bits[i];					\
	subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) -	\
	    bits);							\
	ret = node[subkey];						\
	RTREE_UNLOCK(&rtree->mutex);					\
									\
	RTREE_GET_VALIDATE						\
	return (ret);							\
}

#ifdef JEMALLOC_DEBUG
#  define RTREE_LOCK(l)		malloc_mutex_lock(l)
#  define RTREE_UNLOCK(l)	malloc_mutex_unlock(l)
#  define RTREE_GET_VALIDATE
RTREE_GET_GENERATE(rtree_get_locked)
#  undef RTREE_LOCK
#  undef RTREE_UNLOCK
#  undef RTREE_GET_VALIDATE
#endif

#define	RTREE_LOCK(l)
#define	RTREE_UNLOCK(l)
#ifdef JEMALLOC_DEBUG
   /*
    * Suppose that it were possible for a jemalloc-allocated chunk to be
    * munmap()ped, followed by a different allocator in another thread re-using
    * overlapping virtual memory, all without invalidating the cached rtree
    * value.  The result would be a false positive (the rtree would claim that
    * jemalloc owns memory that it had actually discarded).  This scenario
    * seems impossible, but the following assertion is a prudent sanity check.
    */
#  define RTREE_GET_VALIDATE						\
	assert(rtree_get_locked(rtree, key) == ret);
#else
#  define RTREE_GET_VALIDATE
#endif
RTREE_GET_GENERATE(rtree_get)
#undef RTREE_LOCK
#undef RTREE_UNLOCK
#undef RTREE_GET_VALIDATE

JEMALLOC_INLINE bool
rtree_set(rtree_t *rtree, uintptr_t key, void *val)
{
	uintptr_t subkey;
	unsigned i, lshift, height, bits;
	void **node, **child;

	malloc_mutex_lock(&rtree->mutex);
	for (i = lshift = 0, height = rtree->height, node = rtree->root;
	    i < height - 1;
	    i++, lshift += bits, node = child) {
		bits = rtree->level2bits[i];
		subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) -
		    bits);
		child = (void**)node[subkey];
		if (child == NULL) {
			child = (void**)base_alloc(sizeof(void *) <<
			    rtree->level2bits[i+1]);
			if (child == NULL) {
				malloc_mutex_unlock(&rtree->mutex);
				return (true);
			}
			memset(child, 0, sizeof(void *) <<
			    rtree->level2bits[i+1]);
			node[subkey] = child;
		}
	}

	/* node is a leaf, so it contains values rather than node pointers. */
	bits = rtree->level2bits[i];
	subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) - bits);
	node[subkey] = val;
	malloc_mutex_unlock(&rtree->mutex);

	return (false);
}
#endif

#endif /* JEMALLOC_H_INLINES */
/******************************************************************************/
Commit	Line	Data
4934f93d	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
	11	typedef 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
	27	struct 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
	38	rtree_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
	46	void rtree_get_locked(rtree_t rtree, uintptr_t key);
	47	#endif
	48	void rtree_get(rtree_t rtree, uintptr_t key);
	49	bool 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. */ \
	55	JEMALLOC_INLINE void * \
	56	f(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
95	RTREE_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
117	RTREE_GET_GENERATE(rtree_get)
118	#undef RTREE_LOCK
119	#undef RTREE_UNLOCK
120	#undef RTREE_GET_VALIDATE
121
122	JEMALLOC_INLINE bool
123	rtree_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	/******************************************************************************/