Home | History | Annotate | Download | only in src 
      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(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
     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
     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 *
     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 *
    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 *
    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