rtree.h revision 20f1fc95adb35ea63dc61f47f2b0ffbd37d39f32
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); 39void rtree_prefork(rtree_t *rtree); 40void rtree_postfork_parent(rtree_t *rtree); 41void rtree_postfork_child(rtree_t *rtree); 42 43#endif /* JEMALLOC_H_EXTERNS */ 44/******************************************************************************/ 45#ifdef JEMALLOC_H_INLINES 46 47#ifndef JEMALLOC_ENABLE_INLINE 48#ifndef JEMALLOC_DEBUG 49void *rtree_get_locked(rtree_t *rtree, uintptr_t key); 50#endif 51void *rtree_get(rtree_t *rtree, uintptr_t key); 52bool rtree_set(rtree_t *rtree, uintptr_t key, void *val); 53#endif 54 55#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_RTREE_C_)) 56#define RTREE_GET_GENERATE(f) \ 57/* The least significant bits of the key are ignored. */ \ 58JEMALLOC_INLINE void * \ 59f(rtree_t *rtree, uintptr_t key) \ 60{ \ 61 void *ret; \ 62 uintptr_t subkey; \ 63 unsigned i, lshift, height, bits; \ 64 void **node, **child; \ 65 \ 66 RTREE_LOCK(&rtree->mutex); \ 67 for (i = lshift = 0, height = rtree->height, node = rtree->root;\ 68 i < height - 1; \ 69 i++, lshift += bits, node = child) { \ 70 bits = rtree->level2bits[i]; \ 71 subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR + \ 72 3)) - bits); \ 73 child = (void**)node[subkey]; \ 74 if (child == NULL) { \ 75 RTREE_UNLOCK(&rtree->mutex); \ 76 return (NULL); \ 77 } \ 78 } \ 79 \ 80 /* \ 81 * node is a leaf, so it contains values rather than node \ 82 * pointers. \ 83 */ \ 84 bits = rtree->level2bits[i]; \ 85 subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) - \ 86 bits); \ 87 ret = node[subkey]; \ 88 RTREE_UNLOCK(&rtree->mutex); \ 89 \ 90 RTREE_GET_VALIDATE \ 91 return (ret); \ 92} 93 94#ifdef JEMALLOC_DEBUG 95# define RTREE_LOCK(l) malloc_mutex_lock(l) 96# define RTREE_UNLOCK(l) malloc_mutex_unlock(l) 97# define RTREE_GET_VALIDATE 98RTREE_GET_GENERATE(rtree_get_locked) 99# undef RTREE_LOCK 100# undef RTREE_UNLOCK 101# undef RTREE_GET_VALIDATE 102#endif 103 104#define RTREE_LOCK(l) 105#define RTREE_UNLOCK(l) 106#ifdef JEMALLOC_DEBUG 107 /* 108 * Suppose that it were possible for a jemalloc-allocated chunk to be 109 * munmap()ped, followed by a different allocator in another thread re-using 110 * overlapping virtual memory, all without invalidating the cached rtree 111 * value. The result would be a false positive (the rtree would claim that 112 * jemalloc owns memory that it had actually discarded). This scenario 113 * seems impossible, but the following assertion is a prudent sanity check. 114 */ 115# define RTREE_GET_VALIDATE \ 116 assert(rtree_get_locked(rtree, key) == ret); 117#else 118# define RTREE_GET_VALIDATE 119#endif 120RTREE_GET_GENERATE(rtree_get) 121#undef RTREE_LOCK 122#undef RTREE_UNLOCK 123#undef RTREE_GET_VALIDATE 124 125JEMALLOC_INLINE bool 126rtree_set(rtree_t *rtree, uintptr_t key, void *val) 127{ 128 uintptr_t subkey; 129 unsigned i, lshift, height, bits; 130 void **node, **child; 131 132 malloc_mutex_lock(&rtree->mutex); 133 for (i = lshift = 0, height = rtree->height, node = rtree->root; 134 i < height - 1; 135 i++, lshift += bits, node = child) { 136 bits = rtree->level2bits[i]; 137 subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) - 138 bits); 139 child = (void**)node[subkey]; 140 if (child == NULL) { 141 child = (void**)base_alloc(sizeof(void *) << 142 rtree->level2bits[i+1]); 143 if (child == NULL) { 144 malloc_mutex_unlock(&rtree->mutex); 145 return (true); 146 } 147 memset(child, 0, sizeof(void *) << 148 rtree->level2bits[i+1]); 149 node[subkey] = child; 150 } 151 } 152 153 /* node is a leaf, so it contains values rather than node pointers. */ 154 bits = rtree->level2bits[i]; 155 subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) - bits); 156 node[subkey] = val; 157 malloc_mutex_unlock(&rtree->mutex); 158 159 return (false); 160} 161#endif 162 163#endif /* JEMALLOC_H_INLINES */ 164/******************************************************************************/ 165