10657f12acd43eb2082a71230341449eca648bc9bJason Evans#define JEMALLOC_RTREE_C_ 22dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans#include "jemalloc/internal/jemalloc_internal.h" 32dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 42dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evansrtree_t * 5b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansrtree_new(unsigned bits, rtree_alloc_t *alloc, rtree_dalloc_t *dalloc) 62dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans{ 72dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans rtree_t *ret; 8b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans unsigned bits_per_level, bits_in_leaf, height, i; 92dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 10b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3)); 11b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 122aa7fed9c983d8dcde7c0cacf1b024c966758b88Richard Diamond bits_per_level = jemalloc_ffs(pow2_ceil((RTREE_NODESIZE / sizeof(void *)))) - 1; 132aa7fed9c983d8dcde7c0cacf1b024c966758b88Richard Diamond bits_in_leaf = jemalloc_ffs(pow2_ceil((RTREE_NODESIZE / sizeof(uint8_t)))) - 1; 14b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans if (bits > bits_in_leaf) { 15b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans height = 1 + (bits - bits_in_leaf) / bits_per_level; 16b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans if ((height-1) * bits_per_level + bits_in_leaf != bits) 17b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans height++; 18b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans } else { 19b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans height = 1; 20b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans } 21b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans assert((height-1) * bits_per_level + bits_in_leaf >= bits); 222dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 23b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans ret = (rtree_t*)alloc(offsetof(rtree_t, level2bits) + 24c2fc8c8b3afbd15ec3e8ed4ca38667ec0a01ade8Jason Evans (sizeof(unsigned) * height)); 252dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans if (ret == NULL) 262dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans return (NULL); 27c2fc8c8b3afbd15ec3e8ed4ca38667ec0a01ade8Jason Evans memset(ret, 0, offsetof(rtree_t, level2bits) + (sizeof(unsigned) * 28c2fc8c8b3afbd15ec3e8ed4ca38667ec0a01ade8Jason Evans height)); 292dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 30b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans ret->alloc = alloc; 31b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans ret->dalloc = dalloc; 32819d11be068e3f86e31db0956f5a0b29d9971e7fJason Evans if (malloc_mutex_init(&ret->mutex)) { 33b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans if (dalloc != NULL) 34b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans dalloc(ret); 35819d11be068e3f86e31db0956f5a0b29d9971e7fJason Evans return (NULL); 36819d11be068e3f86e31db0956f5a0b29d9971e7fJason Evans } 372dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans ret->height = height; 38b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans if (height > 1) { 39b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans if ((height-1) * bits_per_level + bits_in_leaf > bits) { 40b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans ret->level2bits[0] = (bits - bits_in_leaf) % 41b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans bits_per_level; 42b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans } else 43b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans ret->level2bits[0] = bits_per_level; 44b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans for (i = 1; i < height-1; i++) 45b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans ret->level2bits[i] = bits_per_level; 46b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans ret->level2bits[height-1] = bits_in_leaf; 47b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans } else 48b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans ret->level2bits[0] = bits; 492dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 50b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans ret->root = (void**)alloc(sizeof(void *) << ret->level2bits[0]); 512dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans if (ret->root == NULL) { 52b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans if (dalloc != NULL) 53b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans dalloc(ret); 542dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans return (NULL); 552dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans } 562dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans memset(ret->root, 0, sizeof(void *) << ret->level2bits[0]); 572dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 582dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans return (ret); 592dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans} 6020f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 61b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansstatic void 62b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansrtree_delete_subtree(rtree_t *rtree, void **node, unsigned level) 63b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans{ 64b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 65b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans if (level < rtree->height - 1) { 66b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans size_t nchildren, i; 67b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 68b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans nchildren = ZU(1) << rtree->level2bits[level]; 69b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans for (i = 0; i < nchildren; i++) { 70b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans void **child = (void **)node[i]; 71b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans if (child != NULL) 72b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans rtree_delete_subtree(rtree, child, level + 1); 73b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans } 74b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans } 75b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans rtree->dalloc(node); 76b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans} 77b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 78b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansvoid 79b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansrtree_delete(rtree_t *rtree) 80b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans{ 81b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 82b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans rtree_delete_subtree(rtree, rtree->root, 0); 83b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans rtree->dalloc(rtree); 84b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans} 85b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 8620f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evansvoid 8720f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evansrtree_prefork(rtree_t *rtree) 8820f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans{ 8920f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 9020f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans malloc_mutex_prefork(&rtree->mutex); 9120f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans} 9220f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 9320f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evansvoid 9420f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evansrtree_postfork_parent(rtree_t *rtree) 9520f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans{ 9620f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 9720f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans malloc_mutex_postfork_parent(&rtree->mutex); 9820f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans} 9920f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 10020f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evansvoid 10120f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evansrtree_postfork_child(rtree_t *rtree) 10220f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans{ 10320f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 10420f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans malloc_mutex_postfork_child(&rtree->mutex); 10520f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans} 106