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 /* 50 * ncached and stats are both modified frequently. Let's keep them 51 * close so that they have a higher chance of being on the same 52 * cacheline, thus less write-backs. 53 */ 54 cache_bin_stats_t tstats; 55 /* 56 * Stack of available objects. 57 * 58 * To make use of adjacent cacheline prefetch, the items in the avail 59 * stack goes to higher address for newer allocations. avail points 60 * just above the available space, which means that 61 * avail[-ncached, ... -1] are available items and the lowest item will 62 * be allocated first. 63 */ 64 void **avail; 65 }; 66 67 typedef struct cache_bin_array_descriptor_s cache_bin_array_descriptor_t; 68 struct cache_bin_array_descriptor_s { 69 /* 70 * The arena keeps a list of the cache bins associated with it, for 71 * stats collection. 72 */ 73 ql_elm(cache_bin_array_descriptor_t) link; 74 /* Pointers to the tcache bins. */ 75 cache_bin_t *bins_small; 76 cache_bin_t *bins_large; 77 }; 78 79 static inline void 80 cache_bin_array_descriptor_init(cache_bin_array_descriptor_t *descriptor, 81 cache_bin_t *bins_small, cache_bin_t *bins_large) { 82 ql_elm_new(descriptor, link); 83 descriptor->bins_small = bins_small; 84 descriptor->bins_large = bins_large; 85 } 86 87 JEMALLOC_ALWAYS_INLINE void * 88 cache_bin_alloc_easy(cache_bin_t *bin, bool *success) { 89 void *ret; 90 91 bin->ncached--; 92 93 /* 94 * Check for both bin->ncached == 0 and ncached < low_water 95 * in a single branch. 96 */ 97 if (unlikely(bin->ncached <= bin->low_water)) { 98 bin->low_water = bin->ncached; 99 if (bin->ncached == -1) { 100 bin->ncached = 0; 101 *success = false; 102 return NULL; 103 } 104 } 105 106 /* 107 * success (instead of ret) should be checked upon the return of this 108 * function. We avoid checking (ret == NULL) because there is never a 109 * null stored on the avail stack (which is unknown to the compiler), 110 * and eagerly checking ret would cause pipeline stall (waiting for the 111 * cacheline). 112 */ 113 *success = true; 114 ret = *(bin->avail - (bin->ncached + 1)); 115 116 return ret; 117 } 118 119 JEMALLOC_ALWAYS_INLINE bool 120 cache_bin_dalloc_easy(cache_bin_t *bin, cache_bin_info_t *bin_info, void *ptr) { 121 if (unlikely(bin->ncached == bin_info->ncached_max)) { 122 return false; 123 } 124 assert(bin->ncached < bin_info->ncached_max); 125 bin->ncached++; 126 *(bin->avail - bin->ncached) = ptr; 127 128 return true; 129 } 130 131 #endif /* JEMALLOC_INTERNAL_CACHE_BIN_H */ 132