contrib/jemalloc/include/jemalloc/internal/cache_bin.h

   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 */