1 #ifndef JEMALLOC_INTERNAL_RTREE_CTX_H
2 #define JEMALLOC_INTERNAL_RTREE_CTX_H
5 * Number of leafkey/leaf pairs to cache in L1 and L2 level respectively. Each
6 * entry supports an entire leaf, so the cache hit rate is typically high even
7 * with a small number of entries. In rare cases extent activity will straddle
8 * the boundary between two leaf nodes. Furthermore, an arena may use a
9 * combination of dss and mmap. Note that as memory usage grows past the amount
10 * that this cache can directly cover, the cache will become less effective if
11 * locality of reference is low, but the consequence is merely cache misses
12 * while traversing the tree nodes.
14 * The L1 direct mapped cache offers consistent and low cost on cache hit.
15 * However collision could affect hit rate negatively. This is resolved by
16 * combining with a L2 LRU cache, which requires linear search and re-ordering
17 * on access but suffers no collision. Note that, the cache will itself suffer
18 * cache misses if made overly large, plus the cost of linear search in the LRU
21 #define RTREE_CTX_LG_NCACHE 4
22 #define RTREE_CTX_NCACHE (1 << RTREE_CTX_LG_NCACHE)
23 #define RTREE_CTX_NCACHE_L2 8
26 * Zero initializer required for tsd initialization only. Proper initialization
27 * done via rtree_ctx_data_init().
29 #define RTREE_CTX_ZERO_INITIALIZER {{{0}}, {{0}}}
32 typedef struct rtree_leaf_elm_s rtree_leaf_elm_t;
34 typedef struct rtree_ctx_cache_elm_s rtree_ctx_cache_elm_t;
35 struct rtree_ctx_cache_elm_s {
37 rtree_leaf_elm_t *leaf;
40 typedef struct rtree_ctx_s rtree_ctx_t;
42 /* Direct mapped cache. */
43 rtree_ctx_cache_elm_t cache[RTREE_CTX_NCACHE];
45 rtree_ctx_cache_elm_t l2_cache[RTREE_CTX_NCACHE_L2];
48 void rtree_ctx_data_init(rtree_ctx_t *ctx);
50 #endif /* JEMALLOC_INTERNAL_RTREE_CTX_H */