• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_LG_NCACHE 4
22 #define RTREE_CTX_NCACHE (1 << RTREE_CTX_LG_NCACHE)
23 #define RTREE_CTX_NCACHE_L2 8
24 
25 /*
26  * Zero initializer required for tsd initialization only.  Proper initialization
27  * done via rtree_ctx_data_init().
28  */
29 #define RTREE_CTX_ZERO_INITIALIZER {{{0}}, {{0}}}
30 
31 
32 typedef struct rtree_leaf_elm_s rtree_leaf_elm_t;
33 
34 typedef struct rtree_ctx_cache_elm_s rtree_ctx_cache_elm_t;
35 struct rtree_ctx_cache_elm_s {
36 	uintptr_t		leafkey;
37 	rtree_leaf_elm_t	*leaf;
38 };
39 
40 typedef struct rtree_ctx_s rtree_ctx_t;
41 struct rtree_ctx_s {
42 	/* Direct mapped cache. */
43 	rtree_ctx_cache_elm_t	cache[RTREE_CTX_NCACHE];
44 	/* L2 LRU cache. */
45 	rtree_ctx_cache_elm_t	l2_cache[RTREE_CTX_NCACHE_L2];
46 };
47 
48 void rtree_ctx_data_init(rtree_ctx_t *ctx);
49 
50 #endif /* JEMALLOC_INTERNAL_RTREE_CTX_H */
51