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