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
44typedef struct rtree_leaf_elm_s rtree_leaf_elm_t;
45
46typedef struct rtree_ctx_cache_elm_s rtree_ctx_cache_elm_t;
47struct rtree_ctx_cache_elm_s {
48 uintptr_t leafkey;
49 rtree_leaf_elm_t *leaf;
50};
51
52typedef struct rtree_ctx_s rtree_ctx_t;
53struct 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
60void rtree_ctx_data_init(rtree_ctx_t *ctx);
61
62#endif /* JEMALLOC_INTERNAL_RTREE_CTX_H */
63