1 #ifndef JEMALLOC_INTERNAL_CACHE_BIN_H
2 #define JEMALLOC_INTERNAL_CACHE_BIN_H
3
4 #include "jemalloc/internal/ql.h"
5
6 /*
7 * The cache_bins are the mechanism that the tcache and the arena use to
8 * communicate. The tcache fills from and flushes to the arena by passing a
9 * cache_bin_t to fill/flush. When the arena needs to pull stats from the
10 * tcaches associated with it, it does so by iterating over its
11 * cache_bin_array_descriptor_t objects and reading out per-bin stats it
12 * contains. This makes it so that the arena need not know about the existence
13 * of the tcache at all.
14 */
15
16
17 /*
18 * The count of the number of cached allocations in a bin. We make this signed
19 * so that negative numbers can encode "invalid" states (e.g. a low water mark
20 * of -1 for a cache that has been depleted).
21 */
22 typedef int32_t cache_bin_sz_t;
23
24 typedef struct cache_bin_stats_s cache_bin_stats_t;
25 struct cache_bin_stats_s {
26 /*
27 * Number of allocation requests that corresponded to the size of this
28 * bin.
29 */
30 uint64_t nrequests;
31 };
32
33 /*
34 * Read-only information associated with each element of tcache_t's tbins array
35 * is stored separately, mainly to reduce memory usage.
36 */
37 typedef struct cache_bin_info_s cache_bin_info_t;
38 struct cache_bin_info_s {
39 /* Upper limit on ncached. */
40 cache_bin_sz_t ncached_max;
41 };
42
43 typedef struct cache_bin_s cache_bin_t;
44 struct cache_bin_s {
45 /* Min # cached since last GC. */
46 cache_bin_sz_t low_water;
47 /* # of cached objects. */
48 cache_bin_sz_t ncached;
49 /* Removing this variable make the cache_t structure fit in a single page. */
50 #if defined(ANDROID_ENABLE_TCACHE_STATS)
51 /*
52 * ncached and stats are both modified frequently. Let's keep them
53 * close so that they have a higher chance of being on the same
54 * cacheline, thus less write-backs.
55 */
56 cache_bin_stats_t tstats;
57 #endif
58 /*
59 * Stack of available objects.
60 *
61 * To make use of adjacent cacheline prefetch, the items in the avail
62 * stack goes to higher address for newer allocations. avail points
63 * just above the available space, which means that
64 * avail[-ncached, ... -1] are available items and the lowest item will
65 * be allocated first.
66 */
67 void **avail;
68 };
69
70 typedef struct cache_bin_array_descriptor_s cache_bin_array_descriptor_t;
71 struct cache_bin_array_descriptor_s {
72 /*
73 * The arena keeps a list of the cache bins associated with it, for
74 * stats collection.
75 */
76 ql_elm(cache_bin_array_descriptor_t) link;
77 /* Pointers to the tcache bins. */
78 cache_bin_t *bins_small;
79 cache_bin_t *bins_large;
80 };
81
82 static inline void
cache_bin_array_descriptor_init(cache_bin_array_descriptor_t * descriptor,cache_bin_t * bins_small,cache_bin_t * bins_large)83 cache_bin_array_descriptor_init(cache_bin_array_descriptor_t *descriptor,
84 cache_bin_t *bins_small, cache_bin_t *bins_large) {
85 ql_elm_new(descriptor, link);
86 descriptor->bins_small = bins_small;
87 descriptor->bins_large = bins_large;
88 }
89
90 JEMALLOC_ALWAYS_INLINE void *
cache_bin_alloc_easy(cache_bin_t * bin,bool * success)91 cache_bin_alloc_easy(cache_bin_t *bin, bool *success) {
92 void *ret;
93
94 if (unlikely(bin->ncached == 0)) {
95 bin->low_water = -1;
96 *success = false;
97 return NULL;
98 }
99 /*
100 * success (instead of ret) should be checked upon the return of this
101 * function. We avoid checking (ret == NULL) because there is never a
102 * null stored on the avail stack (which is unknown to the compiler),
103 * and eagerly checking ret would cause pipeline stall (waiting for the
104 * cacheline).
105 */
106 *success = true;
107 ret = *(bin->avail - bin->ncached);
108 bin->ncached--;
109
110 if (unlikely(bin->ncached < bin->low_water)) {
111 bin->low_water = bin->ncached;
112 }
113
114 return ret;
115 }
116
117 #endif /* JEMALLOC_INTERNAL_CACHE_BIN_H */
118