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