1 #ifndef JEMALLOC_INTERNAL_TICKER_H 2 #define JEMALLOC_INTERNAL_TICKER_H 3 4 #include "jemalloc/internal/prng.h" 5 #include "jemalloc/internal/util.h" 6 7 /** 8 * A ticker makes it easy to count-down events until some limit. You 9 * ticker_init the ticker to trigger every nticks events. You then notify it 10 * that an event has occurred with calls to ticker_tick (or that nticks events 11 * have occurred with a call to ticker_ticks), which will return true (and reset 12 * the counter) if the countdown hit zero. 13 */ 14 typedef struct ticker_s ticker_t; 15 struct ticker_s { 16 int32_t tick; 17 int32_t nticks; 18 }; 19 20 static inline void 21 ticker_init(ticker_t *ticker, int32_t nticks) { 22 ticker->tick = nticks; 23 ticker->nticks = nticks; 24 } 25 26 static inline void 27 ticker_copy(ticker_t *ticker, const ticker_t *other) { 28 *ticker = *other; 29 } 30 31 static inline int32_t 32 ticker_read(const ticker_t *ticker) { 33 return ticker->tick; 34 } 35 36 /* 37 * Not intended to be a public API. Unfortunately, on x86, neither gcc nor 38 * clang seems smart enough to turn 39 * ticker->tick -= nticks; 40 * if (unlikely(ticker->tick < 0)) { 41 * fixup ticker 42 * return true; 43 * } 44 * return false; 45 * into 46 * subq %nticks_reg, (%ticker_reg) 47 * js fixup ticker 48 * 49 * unless we force "fixup ticker" out of line. In that case, gcc gets it right, 50 * but clang now does worse than before. So, on x86 with gcc, we force it out 51 * of line, but otherwise let the inlining occur. Ordinarily this wouldn't be 52 * worth the hassle, but this is on the fast path of both malloc and free (via 53 * tcache_event). 54 */ 55 #if defined(__GNUC__) && !defined(__clang__) \ 56 && (defined(__x86_64__) || defined(__i386__)) 57 JEMALLOC_NOINLINE 58 #endif 59 static bool 60 ticker_fixup(ticker_t *ticker) { 61 ticker->tick = ticker->nticks; 62 return true; 63 } 64 65 static inline bool 66 ticker_ticks(ticker_t *ticker, int32_t nticks) { 67 ticker->tick -= nticks; 68 if (unlikely(ticker->tick < 0)) { 69 return ticker_fixup(ticker); 70 } 71 return false; 72 } 73 74 static inline bool 75 ticker_tick(ticker_t *ticker) { 76 return ticker_ticks(ticker, 1); 77 } 78 79 /* 80 * Try to tick. If ticker would fire, return true, but rely on 81 * slowpath to reset ticker. 82 */ 83 static inline bool 84 ticker_trytick(ticker_t *ticker) { 85 --ticker->tick; 86 if (unlikely(ticker->tick < 0)) { 87 return true; 88 } 89 return false; 90 } 91 92 /* 93 * The ticker_geom_t is much like the ticker_t, except that instead of ticker 94 * having a constant countdown, it has an approximate one; each tick has 95 * approximately a 1/nticks chance of triggering the count. 96 * 97 * The motivation is in triggering arena decay. With a naive strategy, each 98 * thread would maintain a ticker per arena, and check if decay is necessary 99 * each time that the arena's ticker fires. This has two costs: 100 * - Since under reasonable assumptions both threads and arenas can scale 101 * linearly with the number of CPUs, maintaining per-arena data in each thread 102 * scales quadratically with the number of CPUs. 103 * - These tickers are often a cache miss down tcache flush pathways. 104 * 105 * By giving each tick a 1/nticks chance of firing, we still maintain the same 106 * average number of ticks-until-firing per arena, with only a single ticker's 107 * worth of metadata. 108 */ 109 110 /* See ticker.c for an explanation of these constants. */ 111 #define TICKER_GEOM_NBITS 6 112 #define TICKER_GEOM_MUL 61 113 extern const uint8_t ticker_geom_table[1 << TICKER_GEOM_NBITS]; 114 115 /* Not actually any different from ticker_t; just for type safety. */ 116 typedef struct ticker_geom_s ticker_geom_t; 117 struct ticker_geom_s { 118 int32_t tick; 119 int32_t nticks; 120 }; 121 122 /* 123 * Just pick the average delay for the first counter. We're more concerned with 124 * the behavior over long periods of time rather than the exact timing of the 125 * initial ticks. 126 */ 127 #define TICKER_GEOM_INIT(nticks) {nticks, nticks} 128 129 static inline void 130 ticker_geom_init(ticker_geom_t *ticker, int32_t nticks) { 131 /* 132 * Make sure there's no overflow possible. This shouldn't really be a 133 * problem for reasonable nticks choices, which are all static and 134 * relatively small. 135 */ 136 assert((uint64_t)nticks * (uint64_t)255 / (uint64_t)TICKER_GEOM_MUL 137 <= (uint64_t)INT32_MAX); 138 ticker->tick = nticks; 139 ticker->nticks = nticks; 140 } 141 142 static inline int32_t 143 ticker_geom_read(const ticker_geom_t *ticker) { 144 return ticker->tick; 145 } 146 147 /* Same deal as above. */ 148 #if defined(__GNUC__) && !defined(__clang__) \ 149 && (defined(__x86_64__) || defined(__i386__)) 150 JEMALLOC_NOINLINE 151 #endif 152 static bool 153 ticker_geom_fixup(ticker_geom_t *ticker, uint64_t *prng_state) { 154 uint64_t idx = prng_lg_range_u64(prng_state, TICKER_GEOM_NBITS); 155 ticker->tick = (uint32_t)( 156 (uint64_t)ticker->nticks * (uint64_t)ticker_geom_table[idx] 157 / (uint64_t)TICKER_GEOM_MUL); 158 return true; 159 } 160 161 static inline bool 162 ticker_geom_ticks(ticker_geom_t *ticker, uint64_t *prng_state, int32_t nticks) { 163 ticker->tick -= nticks; 164 if (unlikely(ticker->tick < 0)) { 165 return ticker_geom_fixup(ticker, prng_state); 166 } 167 return false; 168 } 169 170 static inline bool 171 ticker_geom_tick(ticker_geom_t *ticker, uint64_t *prng_state) { 172 return ticker_geom_ticks(ticker, prng_state, 1); 173 } 174 175 #endif /* JEMALLOC_INTERNAL_TICKER_H */ 176