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