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 */
14typedef struct ticker_s ticker_t;
15struct ticker_s {
16 int32_t tick;
17 int32_t nticks;
18};
19
20static inline void
21ticker_init(ticker_t *ticker, int32_t nticks) {
22 ticker->tick = nticks;
23 ticker->nticks = nticks;
24}
25
26static inline void
27ticker_copy(ticker_t *ticker, const ticker_t *other) {
28 *ticker = *other;
29}
30
31static inline int32_t
32ticker_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__))
57JEMALLOC_NOINLINE
58#endif
59static bool
60ticker_fixup(ticker_t *ticker) {
61 ticker->tick = ticker->nticks;
62 return true;
63}
64
65static inline bool
66ticker_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
74static inline bool
75ticker_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 */
83static inline bool
84ticker_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
113extern const uint8_t ticker_geom_table[1 << TICKER_GEOM_NBITS];
114
115/* Not actually any different from ticker_t; just for type safety. */
116typedef struct ticker_geom_s ticker_geom_t;
117struct 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
129static inline void
130ticker_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
142static inline int32_t
143ticker_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__))
150JEMALLOC_NOINLINE
151#endif
152static bool
153ticker_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
161static inline bool
162ticker_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
170static inline bool
171ticker_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