Home | History | Annotate | Line # | Download | only in internal 
      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 	if (unlikely(bin->ncached == 0)) {
     92 		bin->low_water = -1;
     93 		*success = false;
     94 		return NULL;
     95 	}
     96 	/*
     97 	 * success (instead of ret) should be checked upon the return of this
     98 	 * function.  We avoid checking (ret == NULL) because there is never a
     99 	 * null stored on the avail stack (which is unknown to the compiler),
    100 	 * and eagerly checking ret would cause pipeline stall (waiting for the
    101 	 * cacheline).
    102 	 */
    103 	*success = true;
    104 	ret = *(bin->avail - bin->ncached);
    105 	bin->ncached--;
    106 
    107 	if (unlikely(bin->ncached < bin->low_water)) {
    108 		bin->low_water = bin->ncached;
    109 	}
    110 
    111 	return ret;
    112 }
    113 
    114 #endif /* JEMALLOC_INTERNAL_CACHE_BIN_H */
    115