contrib/jemalloc/src/rtree.c

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