10657f12acd43eb2082a71230341449eca648bc9bJason Evans#define JEMALLOC_RTREE_C_ 22dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans#include "jemalloc/internal/jemalloc_internal.h" 32dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisstatic unsigned 583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrishmin(unsigned ha, unsigned hb) 62dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans{ 783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris return (ha < hb ? ha : hb); 983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris} 1083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 1183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/* Only the most significant bits of keys passed to rtree_[gs]et() are used. */ 1283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisbool 1383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisrtree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc, 1483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree_node_dalloc_t *dalloc) 1583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris{ 1683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris unsigned bits_in_leaf, height, i; 172dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 18b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3)); 19b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 2083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL 2183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris : (bits % RTREE_BITS_PER_LEVEL); 22b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans if (bits > bits_in_leaf) { 2383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL; 2483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits) 25b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans height++; 2683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris } else 27b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans height = 1; 2883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits); 2983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 3083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->alloc = alloc; 3183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->dalloc = dalloc; 3283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->height = height; 3383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 3483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris /* Root level. */ 3583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[0].subtree = NULL; 3683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL : 3783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris bits_in_leaf; 3883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[0].cumbits = rtree->levels[0].bits; 3983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris /* Interior levels. */ 4083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris for (i = 1; i < height-1; i++) { 4183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[i].subtree = NULL; 4283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[i].bits = RTREE_BITS_PER_LEVEL; 4383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[i].cumbits = rtree->levels[i-1].cumbits + 4483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris RTREE_BITS_PER_LEVEL; 45b954bc5d3a65966df0ce7801cd6102542b5e894bJason Evans } 4683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris /* Leaf level. */ 4775929a97332565c3b987986f35652b6d5d275d3cNicolas Geoffray if (height > 1) { 4883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[height-1].subtree = NULL; 4983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[height-1].bits = bits_in_leaf; 5083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->levels[height-1].cumbits = bits; 5183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris } 522dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 5383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris /* Compute lookup table to be used by rtree_start_level(). */ 5483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris for (i = 0; i < RTREE_HEIGHT_MAX; i++) { 5583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height - 5683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 1); 572dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans } 582dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans 5983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris return (false); 602dbecf1f6267fae7a161b9c39cfd4d04ce168a29Jason Evans} 6120f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 62b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansstatic void 6383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisrtree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level) 64b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans{ 65b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 6683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris if (level + 1 < rtree->height) { 67b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans size_t nchildren, i; 68b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 6983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris nchildren = ZU(1) << rtree->levels[level].bits; 70b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans for (i = 0; i < nchildren; i++) { 7183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree_node_elm_t *child = node[i].child; 72b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans if (child != NULL) 73b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans rtree_delete_subtree(rtree, child, level + 1); 74b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans } 75b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans } 76b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans rtree->dalloc(node); 77b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans} 78b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 79b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansvoid 80b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evansrtree_delete(rtree_t *rtree) 81b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans{ 8283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris unsigned i; 83b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 8483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris for (i = 0; i < rtree->height; i++) { 8583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree_node_elm_t *subtree = rtree->levels[i].subtree; 8683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris if (subtree != NULL) 8783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree_delete_subtree(rtree, subtree, i); 8883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris } 89b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans} 90b980cc774a9ccb208a82f4e9ccdcc695d06a960aJason Evans 9183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisstatic rtree_node_elm_t * 9283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisrtree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp) 9320f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans{ 9483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris rtree_node_elm_t *node; 9583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 9683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) { 9783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris /* 9883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Another thread is already in the process of initializing. 9983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Spin-wait until initialization is complete. 10083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris */ 10183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris do { 10283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris CPU_SPINWAIT; 10383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris node = atomic_read_p((void **)elmp); 10483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris } while (node == RTREE_NODE_INITIALIZING); 10583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris } else { 10683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris node = rtree->alloc(ZU(1) << rtree->levels[level].bits); 10783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris if (node == NULL) 10883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris return (NULL); 10983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris atomic_write_p((void **)elmp, node); 11083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris } 11120f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 11283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris return (node); 11320f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans} 11420f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 11583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisrtree_node_elm_t * 11683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisrtree_subtree_read_hard(rtree_t *rtree, unsigned level) 11720f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans{ 11820f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 11983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris return (rtree_node_init(rtree, level, &rtree->levels[level].subtree)); 12020f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans} 12120f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 12283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisrtree_node_elm_t * 12383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferrisrtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level) 12420f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans{ 12520f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans 12683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris return (rtree_node_init(rtree, level, &elm->child)); 12720f1fc95adb35ea63dc61f47f2b0ffbd37d39f32Jason Evans} 128