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