1 #include "jemalloc/internal/jemalloc_preamble.h" 2 #include "jemalloc/internal/jemalloc_internal_includes.h" 3 4 #include "jemalloc/internal/assert.h" 5 #include "jemalloc/internal/mutex.h" 6 7 /* 8 * Only the most significant bits of keys passed to rtree_{read,write}() are 9 * used. 10 */ 11 bool 12 rtree_new(rtree_t *rtree, base_t *base, bool zeroed) { 13 #ifdef JEMALLOC_JET 14 if (!zeroed) { 15 memset(rtree, 0, sizeof(rtree_t)); /* Clear root. */ 16 } 17 #else 18 assert(zeroed); 19 #endif 20 rtree->base = base; 21 22 if (malloc_mutex_init(&rtree->init_lock, "rtree", WITNESS_RANK_RTREE, 23 malloc_mutex_rank_exclusive)) { 24 return true; 25 } 26 27 return false; 28 } 29 30 static rtree_node_elm_t * 31 rtree_node_alloc(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 32 return (rtree_node_elm_t *)base_alloc(tsdn, rtree->base, 33 nelms * sizeof(rtree_node_elm_t), CACHELINE); 34 } 35 36 static rtree_leaf_elm_t * 37 rtree_leaf_alloc(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 38 return (rtree_leaf_elm_t *)base_alloc(tsdn, rtree->base, 39 nelms * sizeof(rtree_leaf_elm_t), CACHELINE); 40 } 41 42 static rtree_node_elm_t * 43 rtree_node_init(tsdn_t *tsdn, rtree_t *rtree, unsigned level, 44 atomic_p_t *elmp) { 45 malloc_mutex_lock(tsdn, &rtree->init_lock); 46 /* 47 * If *elmp is non-null, then it was initialized with the init lock 48 * held, so we can get by with 'relaxed' here. 49 */ 50 rtree_node_elm_t *node = atomic_load_p(elmp, ATOMIC_RELAXED); 51 if (node == NULL) { 52 node = rtree_node_alloc(tsdn, rtree, ZU(1) << 53 rtree_levels[level].bits); 54 if (node == NULL) { 55 malloc_mutex_unlock(tsdn, &rtree->init_lock); 56 return NULL; 57 } 58 /* 59 * Even though we hold the lock, a later reader might not; we 60 * need release semantics. 61 */ 62 atomic_store_p(elmp, node, ATOMIC_RELEASE); 63 } 64 malloc_mutex_unlock(tsdn, &rtree->init_lock); 65 66 return node; 67 } 68 69 static rtree_leaf_elm_t * 70 rtree_leaf_init(tsdn_t *tsdn, rtree_t *rtree, atomic_p_t *elmp) { 71 malloc_mutex_lock(tsdn, &rtree->init_lock); 72 /* 73 * If *elmp is non-null, then it was initialized with the init lock 74 * held, so we can get by with 'relaxed' here. 75 */ 76 rtree_leaf_elm_t *leaf = atomic_load_p(elmp, ATOMIC_RELAXED); 77 if (leaf == NULL) { 78 leaf = rtree_leaf_alloc(tsdn, rtree, ZU(1) << 79 rtree_levels[RTREE_HEIGHT-1].bits); 80 if (leaf == NULL) { 81 malloc_mutex_unlock(tsdn, &rtree->init_lock); 82 return NULL; 83 } 84 /* 85 * Even though we hold the lock, a later reader might not; we 86 * need release semantics. 87 */ 88 atomic_store_p(elmp, leaf, ATOMIC_RELEASE); 89 } 90 malloc_mutex_unlock(tsdn, &rtree->init_lock); 91 92 return leaf; 93 } 94 95 static bool 96 rtree_node_valid(rtree_node_elm_t *node) { 97 return ((uintptr_t)node != (uintptr_t)0); 98 } 99 100 static bool 101 rtree_leaf_valid(rtree_leaf_elm_t *leaf) { 102 return ((uintptr_t)leaf != (uintptr_t)0); 103 } 104 105 static rtree_node_elm_t * 106 rtree_child_node_tryread(rtree_node_elm_t *elm, bool dependent) { 107 rtree_node_elm_t *node; 108 109 if (dependent) { 110 node = (rtree_node_elm_t *)atomic_load_p(&elm->child, 111 ATOMIC_RELAXED); 112 } else { 113 node = (rtree_node_elm_t *)atomic_load_p(&elm->child, 114 ATOMIC_ACQUIRE); 115 } 116 117 assert(!dependent || node != NULL); 118 return node; 119 } 120 121 static rtree_node_elm_t * 122 rtree_child_node_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm, 123 unsigned level, bool dependent) { 124 rtree_node_elm_t *node; 125 126 node = rtree_child_node_tryread(elm, dependent); 127 if (!dependent && unlikely(!rtree_node_valid(node))) { 128 node = rtree_node_init(tsdn, rtree, level + 1, &elm->child); 129 } 130 assert(!dependent || node != NULL); 131 return node; 132 } 133 134 static rtree_leaf_elm_t * 135 rtree_child_leaf_tryread(rtree_node_elm_t *elm, bool dependent) { 136 rtree_leaf_elm_t *leaf; 137 138 if (dependent) { 139 leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child, 140 ATOMIC_RELAXED); 141 } else { 142 leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child, 143 ATOMIC_ACQUIRE); 144 } 145 146 assert(!dependent || leaf != NULL); 147 return leaf; 148 } 149 150 static rtree_leaf_elm_t * 151 rtree_child_leaf_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm, 152 unsigned level, bool dependent) { 153 rtree_leaf_elm_t *leaf; 154 155 leaf = rtree_child_leaf_tryread(elm, dependent); 156 if (!dependent && unlikely(!rtree_leaf_valid(leaf))) { 157 leaf = rtree_leaf_init(tsdn, rtree, &elm->child); 158 } 159 assert(!dependent || leaf != NULL); 160 return leaf; 161 } 162 163 rtree_leaf_elm_t * 164 rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 165 uintptr_t key, bool dependent, bool init_missing) { 166 rtree_node_elm_t *node; 167 rtree_leaf_elm_t *leaf; 168 #if RTREE_HEIGHT > 1 169 node = rtree->root; 170 #else 171 leaf = rtree->root; 172 #endif 173 174 if (config_debug) { 175 uintptr_t leafkey = rtree_leafkey(key); 176 for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) { 177 assert(rtree_ctx->cache[i].leafkey != leafkey); 178 } 179 for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) { 180 assert(rtree_ctx->l2_cache[i].leafkey != leafkey); 181 } 182 } 183 184 #define RTREE_GET_CHILD(level) { \ 185 assert(level < RTREE_HEIGHT-1); \ 186 if (level != 0 && !dependent && \ 187 unlikely(!rtree_node_valid(node))) { \ 188 return NULL; \ 189 } \ 190 uintptr_t subkey = rtree_subkey(key, level); \ 191 if (level + 2 < RTREE_HEIGHT) { \ 192 node = init_missing ? \ 193 rtree_child_node_read(tsdn, rtree, \ 194 &node[subkey], level, dependent) : \ 195 rtree_child_node_tryread(&node[subkey], \ 196 dependent); \ 197 } else { \ 198 leaf = init_missing ? \ 199 rtree_child_leaf_read(tsdn, rtree, \ 200 &node[subkey], level, dependent) : \ 201 rtree_child_leaf_tryread(&node[subkey], \ 202 dependent); \ 203 } \ 204 } 205 /* 206 * Cache replacement upon hard lookup (i.e. L1 & L2 rtree cache miss): 207 * (1) evict last entry in L2 cache; (2) move the collision slot from L1 208 * cache down to L2; and 3) fill L1. 209 */ 210 #define RTREE_GET_LEAF(level) { \ 211 assert(level == RTREE_HEIGHT-1); \ 212 if (!dependent && unlikely(!rtree_leaf_valid(leaf))) { \ 213 return NULL; \ 214 } \ 215 if (RTREE_CTX_NCACHE_L2 > 1) { \ 216 memmove(&rtree_ctx->l2_cache[1], \ 217 &rtree_ctx->l2_cache[0], \ 218 sizeof(rtree_ctx_cache_elm_t) * \ 219 (RTREE_CTX_NCACHE_L2 - 1)); \ 220 } \ 221 size_t slot = rtree_cache_direct_map(key); \ 222 rtree_ctx->l2_cache[0].leafkey = \ 223 rtree_ctx->cache[slot].leafkey; \ 224 rtree_ctx->l2_cache[0].leaf = \ 225 rtree_ctx->cache[slot].leaf; \ 226 uintptr_t leafkey = rtree_leafkey(key); \ 227 rtree_ctx->cache[slot].leafkey = leafkey; \ 228 rtree_ctx->cache[slot].leaf = leaf; \ 229 uintptr_t subkey = rtree_subkey(key, level); \ 230 return &leaf[subkey]; \ 231 } 232 if (RTREE_HEIGHT > 1) { 233 RTREE_GET_CHILD(0) 234 } 235 if (RTREE_HEIGHT > 2) { 236 RTREE_GET_CHILD(1) 237 } 238 if (RTREE_HEIGHT > 3) { 239 for (unsigned i = 2; i < RTREE_HEIGHT-1; i++) { 240 RTREE_GET_CHILD(i) 241 } 242 } 243 RTREE_GET_LEAF(RTREE_HEIGHT-1) 244 #undef RTREE_GET_CHILD 245 #undef RTREE_GET_LEAF 246 not_reached(); 247 } 248 249 void 250 rtree_ctx_data_init(rtree_ctx_t *ctx) { 251 for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) { 252 rtree_ctx_cache_elm_t *cache = &ctx->cache[i]; 253 cache->leafkey = RTREE_LEAFKEY_INVALID; 254 cache->leaf = NULL; 255 } 256 for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) { 257 rtree_ctx_cache_elm_t *cache = &ctx->l2_cache[i]; 258 cache->leafkey = RTREE_LEAFKEY_INVALID; 259 cache->leaf = NULL; 260 } 261 } 262