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 void rtree_prefork(rtree_t *rtree); 40 void rtree_postfork_parent(rtree_t *rtree); 41 void 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 49 void *rtree_get_locked(rtree_t *rtree, uintptr_t key); 50 #endif 51 void *rtree_get(rtree_t *rtree, uintptr_t key); 52 bool 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. */ \ 58 JEMALLOC_INLINE void * \ 59 f(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 98 RTREE_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 120 RTREE_GET_GENERATE(rtree_get) 121 #undef RTREE_LOCK 122 #undef RTREE_UNLOCK 123 #undef RTREE_GET_VALIDATE 124 125 JEMALLOC_INLINE bool 126 rtree_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