1 #define JEMALLOC_RTREE_C_ 2 #include "jemalloc/internal/jemalloc_internal.h" 3 4 static unsigned hmin(unsigned ha,unsigned hb)5 hmin(unsigned ha, unsigned hb) 6 { 7 8 return (ha < hb ? ha : hb); 9 } 10 11 /* Only the most significant bits of keys passed to rtree_[gs]et() are used. */ 12 bool rtree_new(rtree_t * rtree,unsigned bits,rtree_node_alloc_t * alloc,rtree_node_dalloc_t * dalloc)13 rtree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc, 14 rtree_node_dalloc_t *dalloc) 15 { 16 unsigned bits_in_leaf, height, i; 17 18 assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3)); 19 20 bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL 21 : (bits % RTREE_BITS_PER_LEVEL); 22 if (bits > bits_in_leaf) { 23 height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL; 24 if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits) 25 height++; 26 } else 27 height = 1; 28 assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits); 29 30 rtree->alloc = alloc; 31 rtree->dalloc = dalloc; 32 rtree->height = height; 33 34 /* Root level. */ 35 rtree->levels[0].subtree = NULL; 36 rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL : 37 bits_in_leaf; 38 rtree->levels[0].cumbits = rtree->levels[0].bits; 39 /* Interior levels. */ 40 for (i = 1; i < height-1; i++) { 41 rtree->levels[i].subtree = NULL; 42 rtree->levels[i].bits = RTREE_BITS_PER_LEVEL; 43 rtree->levels[i].cumbits = rtree->levels[i-1].cumbits + 44 RTREE_BITS_PER_LEVEL; 45 } 46 /* Leaf level. */ 47 if (height > 1) { 48 rtree->levels[height-1].subtree = NULL; 49 rtree->levels[height-1].bits = bits_in_leaf; 50 rtree->levels[height-1].cumbits = bits; 51 } 52 53 /* Compute lookup table to be used by rtree_start_level(). */ 54 for (i = 0; i < RTREE_HEIGHT_MAX; i++) { 55 rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height - 56 1); 57 } 58 59 return (false); 60 } 61 62 static void rtree_delete_subtree(rtree_t * rtree,rtree_node_elm_t * node,unsigned level)63 rtree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level) 64 { 65 66 if (level + 1 < rtree->height) { 67 size_t nchildren, i; 68 69 nchildren = ZU(1) << rtree->levels[level].bits; 70 for (i = 0; i < nchildren; i++) { 71 rtree_node_elm_t *child = node[i].child; 72 if (child != NULL) 73 rtree_delete_subtree(rtree, child, level + 1); 74 } 75 } 76 rtree->dalloc(node); 77 } 78 79 void rtree_delete(rtree_t * rtree)80 rtree_delete(rtree_t *rtree) 81 { 82 unsigned i; 83 84 for (i = 0; i < rtree->height; i++) { 85 rtree_node_elm_t *subtree = rtree->levels[i].subtree; 86 if (subtree != NULL) 87 rtree_delete_subtree(rtree, subtree, i); 88 } 89 } 90 91 static rtree_node_elm_t * rtree_node_init(rtree_t * rtree,unsigned level,rtree_node_elm_t ** elmp)92 rtree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp) 93 { 94 rtree_node_elm_t *node; 95 96 if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) { 97 /* 98 * Another thread is already in the process of initializing. 99 * Spin-wait until initialization is complete. 100 */ 101 do { 102 CPU_SPINWAIT; 103 node = atomic_read_p((void **)elmp); 104 } while (node == RTREE_NODE_INITIALIZING); 105 } else { 106 node = rtree->alloc(ZU(1) << rtree->levels[level].bits); 107 if (node == NULL) 108 return (NULL); 109 atomic_write_p((void **)elmp, node); 110 } 111 112 return (node); 113 } 114 115 rtree_node_elm_t * rtree_subtree_read_hard(rtree_t * rtree,unsigned level)116 rtree_subtree_read_hard(rtree_t *rtree, unsigned level) 117 { 118 119 return (rtree_node_init(rtree, level, &rtree->levels[level].subtree)); 120 } 121 122 rtree_node_elm_t * rtree_child_read_hard(rtree_t * rtree,rtree_node_elm_t * elm,unsigned level)123 rtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level) 124 { 125 126 return (rtree_node_init(rtree, level, &elm->child)); 127 } 128