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