1 | #ifndef JEMALLOC_INTERNAL_RTREE_CTX_H |
2 | #define JEMALLOC_INTERNAL_RTREE_CTX_H |
3 | |
4 | /* |
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. |
13 | * |
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 |
19 | * cache. |
20 | */ |
21 | #define RTREE_CTX_NCACHE 16 |
22 | #define RTREE_CTX_NCACHE_L2 8 |
23 | |
24 | /* Needed for initialization only. */ |
25 | #define RTREE_LEAFKEY_INVALID ((uintptr_t)1) |
26 | #define RTREE_CTX_CACHE_ELM_INVALID {RTREE_LEAFKEY_INVALID, NULL} |
27 | |
28 | #define RTREE_CTX_INIT_ELM_1 RTREE_CTX_CACHE_ELM_INVALID |
29 | #define RTREE_CTX_INIT_ELM_2 RTREE_CTX_INIT_ELM_1, RTREE_CTX_INIT_ELM_1 |
30 | #define RTREE_CTX_INIT_ELM_4 RTREE_CTX_INIT_ELM_2, RTREE_CTX_INIT_ELM_2 |
31 | #define RTREE_CTX_INIT_ELM_8 RTREE_CTX_INIT_ELM_4, RTREE_CTX_INIT_ELM_4 |
32 | #define RTREE_CTX_INIT_ELM_16 RTREE_CTX_INIT_ELM_8, RTREE_CTX_INIT_ELM_8 |
33 | |
34 | #define _RTREE_CTX_INIT_ELM_DATA(n) RTREE_CTX_INIT_ELM_##n |
35 | #define RTREE_CTX_INIT_ELM_DATA(n) _RTREE_CTX_INIT_ELM_DATA(n) |
36 | |
37 | /* |
38 | * Static initializer (to invalidate the cache entries) is required because the |
39 | * free fastpath may access the rtree cache before a full tsd initialization. |
40 | */ |
41 | #define RTREE_CTX_INITIALIZER {{RTREE_CTX_INIT_ELM_DATA(RTREE_CTX_NCACHE)}, \ |
42 | {RTREE_CTX_INIT_ELM_DATA(RTREE_CTX_NCACHE_L2)}} |
43 | |
44 | typedef struct rtree_leaf_elm_s rtree_leaf_elm_t; |
45 | |
46 | typedef struct rtree_ctx_cache_elm_s rtree_ctx_cache_elm_t; |
47 | struct rtree_ctx_cache_elm_s { |
48 | uintptr_t leafkey; |
49 | rtree_leaf_elm_t *leaf; |
50 | }; |
51 | |
52 | typedef struct rtree_ctx_s rtree_ctx_t; |
53 | struct rtree_ctx_s { |
54 | /* Direct mapped cache. */ |
55 | rtree_ctx_cache_elm_t cache[RTREE_CTX_NCACHE]; |
56 | /* L2 LRU cache. */ |
57 | rtree_ctx_cache_elm_t l2_cache[RTREE_CTX_NCACHE_L2]; |
58 | }; |
59 | |
60 | void rtree_ctx_data_init(rtree_ctx_t *ctx); |
61 | |
62 | #endif /* JEMALLOC_INTERNAL_RTREE_CTX_H */ |
63 | |