1a4bd5210SJason Evans #define JEMALLOC_RTREE_C_ 2a4bd5210SJason Evans #include "jemalloc/internal/jemalloc_internal.h" 3a4bd5210SJason Evans 4a4bd5210SJason Evans rtree_t * 5a4bd5210SJason Evans rtree_new(unsigned bits) 6a4bd5210SJason Evans { 7a4bd5210SJason Evans rtree_t *ret; 8a4bd5210SJason Evans unsigned bits_per_level, height, i; 9a4bd5210SJason Evans 10a4bd5210SJason Evans bits_per_level = ffs(pow2_ceil((RTREE_NODESIZE / sizeof(void *)))) - 1; 11a4bd5210SJason Evans height = bits / bits_per_level; 12a4bd5210SJason Evans if (height * bits_per_level != bits) 13a4bd5210SJason Evans height++; 14a4bd5210SJason Evans assert(height * bits_per_level >= bits); 15a4bd5210SJason Evans 16a4bd5210SJason Evans ret = (rtree_t*)base_alloc(offsetof(rtree_t, level2bits) + 17a4bd5210SJason Evans (sizeof(unsigned) * height)); 18a4bd5210SJason Evans if (ret == NULL) 19a4bd5210SJason Evans return (NULL); 20a4bd5210SJason Evans memset(ret, 0, offsetof(rtree_t, level2bits) + (sizeof(unsigned) * 21a4bd5210SJason Evans height)); 22a4bd5210SJason Evans 23a4bd5210SJason Evans if (malloc_mutex_init(&ret->mutex)) { 24a4bd5210SJason Evans /* Leak the rtree. */ 25a4bd5210SJason Evans return (NULL); 26a4bd5210SJason Evans } 27a4bd5210SJason Evans ret->height = height; 28a4bd5210SJason Evans if (bits_per_level * height > bits) 29a4bd5210SJason Evans ret->level2bits[0] = bits % bits_per_level; 30a4bd5210SJason Evans else 31a4bd5210SJason Evans ret->level2bits[0] = bits_per_level; 32a4bd5210SJason Evans for (i = 1; i < height; i++) 33a4bd5210SJason Evans ret->level2bits[i] = bits_per_level; 34a4bd5210SJason Evans 35a4bd5210SJason Evans ret->root = (void**)base_alloc(sizeof(void *) << ret->level2bits[0]); 36a4bd5210SJason Evans if (ret->root == NULL) { 37a4bd5210SJason Evans /* 38a4bd5210SJason Evans * We leak the rtree here, since there's no generic base 39a4bd5210SJason Evans * deallocation. 40a4bd5210SJason Evans */ 41a4bd5210SJason Evans return (NULL); 42a4bd5210SJason Evans } 43a4bd5210SJason Evans memset(ret->root, 0, sizeof(void *) << ret->level2bits[0]); 44a4bd5210SJason Evans 45a4bd5210SJason Evans return (ret); 46a4bd5210SJason Evans } 47*82872ac0SJason Evans 48*82872ac0SJason Evans void 49*82872ac0SJason Evans rtree_prefork(rtree_t *rtree) 50*82872ac0SJason Evans { 51*82872ac0SJason Evans 52*82872ac0SJason Evans malloc_mutex_prefork(&rtree->mutex); 53*82872ac0SJason Evans } 54*82872ac0SJason Evans 55*82872ac0SJason Evans void 56*82872ac0SJason Evans rtree_postfork_parent(rtree_t *rtree) 57*82872ac0SJason Evans { 58*82872ac0SJason Evans 59*82872ac0SJason Evans malloc_mutex_postfork_parent(&rtree->mutex); 60*82872ac0SJason Evans } 61*82872ac0SJason Evans 62*82872ac0SJason Evans void 63*82872ac0SJason Evans rtree_postfork_child(rtree_t *rtree) 64*82872ac0SJason Evans { 65*82872ac0SJason Evans 66*82872ac0SJason Evans malloc_mutex_postfork_child(&rtree->mutex); 67*82872ac0SJason Evans } 68