rtree.h revision 20f1fc95adb35ea63dc61f47f2b0ffbd37d39f32
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * This radix tree implementation is tailored to the singular purpose of 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * tracking which chunks are currently owned by jemalloc. This functionality 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * is mandatory for OS X, where jemalloc must be able to respond to object 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ownership queries. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ******************************************************************************* 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef JEMALLOC_H_TYPES 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct rtree_s rtree_t; 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)/* 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Size of each radix tree node (must be a power of 2). This impacts tree 15424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) * depth. 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if (LG_SIZEOF_PTR == 2) 18eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch# define RTREE_NODESIZE (1U << 14) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define RTREE_NODESIZE CACHELINE 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* JEMALLOC_H_TYPES */ 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/******************************************************************************/ 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef JEMALLOC_H_STRUCTS 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct rtree_s { 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) malloc_mutex_t mutex; 29116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void **root; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned height; 31558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch unsigned level2bits[1]; /* Dynamically sized. */ 32558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch}; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* JEMALLOC_H_STRUCTS */ 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/******************************************************************************/ 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef JEMALLOC_H_EXTERNS 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)rtree_t *rtree_new(unsigned bits); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void rtree_prefork(rtree_t *rtree); 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void rtree_postfork_parent(rtree_t *rtree); 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void rtree_postfork_child(rtree_t *rtree); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* JEMALLOC_H_EXTERNS */ 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/******************************************************************************/ 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef JEMALLOC_H_INLINES 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef JEMALLOC_ENABLE_INLINE 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef JEMALLOC_DEBUG 49f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)void *rtree_get_locked(rtree_t *rtree, uintptr_t key); 50f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#endif 51f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)void *rtree_get(rtree_t *rtree, uintptr_t key); 52f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)bool rtree_set(rtree_t *rtree, uintptr_t key, void *val); 53f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#endif 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_RTREE_C_)) 56a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)#define RTREE_GET_GENERATE(f) \ 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* The least significant bits of the key are ignored. */ \ 58d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)JEMALLOC_INLINE void * \ 59d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)f(rtree_t *rtree, uintptr_t key) \ 60a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles){ \ 61d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) void *ret; \ 6268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) uintptr_t subkey; \ 6368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned i, lshift, height, bits; \ 6468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) void **node, **child; \ 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) \ 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RTREE_LOCK(&rtree->mutex); \ 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = lshift = 0, height = rtree->height, node = rtree->root;\ 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i < height - 1; \ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i++, lshift += bits, node = child) { \ 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bits = rtree->level2bits[i]; \ 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR + \ 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3)) - bits); \ 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) child = (void**)node[subkey]; \ 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (child == NULL) { \ 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RTREE_UNLOCK(&rtree->mutex); \ 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (NULL); \ 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } \ 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } \ 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) \ 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* \ 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * node is a leaf, so it contains values rather than node \ 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * pointers. \ 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ \ 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bits = rtree->level2bits[i]; \ 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) - \ 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bits); \ 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = node[subkey]; \ 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RTREE_UNLOCK(&rtree->mutex); \ 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) \ 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RTREE_GET_VALIDATE \ 91558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch return (ret); \ 92558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch} 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 94558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch#ifdef JEMALLOC_DEBUG 95558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch# define RTREE_LOCK(l) malloc_mutex_lock(l) 96558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch# define RTREE_UNLOCK(l) malloc_mutex_unlock(l) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define RTREE_GET_VALIDATE 98558790d6acca3451cf3a6b497803a5f07d0bec58Ben MurdochRTREE_GET_GENERATE(rtree_get_locked) 99558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch# undef RTREE_LOCK 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# undef RTREE_UNLOCK 10168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)# undef RTREE_GET_VALIDATE 10268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)#endif 10368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 104116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#define RTREE_LOCK(l) 105a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)#define RTREE_UNLOCK(l) 106a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)#ifdef JEMALLOC_DEBUG 10768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) /* 10868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) * Suppose that it were possible for a jemalloc-allocated chunk to be 10968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) * munmap()ped, followed by a different allocator in another thread re-using 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * overlapping virtual memory, all without invalidating the cached rtree 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * value. The result would be a false positive (the rtree would claim that 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * jemalloc owns memory that it had actually discarded). This scenario 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * seems impossible, but the following assertion is a prudent sanity check. 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define RTREE_GET_VALIDATE \ 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(rtree_get_locked(rtree, key) == ret); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define RTREE_GET_VALIDATE 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RTREE_GET_GENERATE(rtree_get) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef RTREE_LOCK 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef RTREE_UNLOCK 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef RTREE_GET_VALIDATE 124f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)JEMALLOC_INLINE bool 126116680a4aac90f2aa7413d9095a592090648e557Ben Murdochrtree_set(rtree_t *rtree, uintptr_t key, void *val) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 128558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch uintptr_t subkey; 129a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) unsigned i, lshift, height, bits; 130a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void **node, **child; 13168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) malloc_mutex_lock(&rtree->mutex); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = lshift = 0, height = rtree->height, node = rtree->root; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i < height - 1; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i++, lshift += bits, node = child) { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bits = rtree->level2bits[i]; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) subkey = (key << lshift) >> ((ZU(1) << (LG_SIZEOF_PTR+3)) - 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bits); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 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