1 // SPDX-License-Identifier: GPL-2.0
3 #include <linux/eytzinger.h>
4 #include <linux/jiffies.h>
5 #include <linux/module.h>
6 #include <linux/percpu.h>
7 #include <linux/preempt.h>
8 #include <linux/time.h>
9 #include <linux/time_stats.h>
10 #include <linux/spinlock.h>
12 static const struct time_unit time_units[] = {
14 { "us", NSEC_PER_USEC },
15 { "ms", NSEC_PER_MSEC },
16 { "s", NSEC_PER_SEC },
17 { "m", (u64) NSEC_PER_SEC * 60},
18 { "h", (u64) NSEC_PER_SEC * 3600},
19 { "d", (u64) NSEC_PER_SEC * 3600 * 24},
20 { "w", (u64) NSEC_PER_SEC * 3600 * 24 * 7},
21 { "y", (u64) NSEC_PER_SEC * ((3600 * 24 * 7 * 365) + (3600 * (24 / 4) * 7))}, /* 365.25d */
25 const struct time_unit *pick_time_units(u64 ns)
27 const struct time_unit *u;
30 u + 1 < time_units + ARRAY_SIZE(time_units) &&
31 ns >= u[1].nsecs << 1;
37 EXPORT_SYMBOL_GPL(pick_time_units);
39 static void quantiles_update(struct quantiles *q, u64 v)
43 while (i < ARRAY_SIZE(q->entries)) {
44 struct quantile_entry *e = q->entries + i;
46 if (unlikely(!e->step)) {
48 e->step = max_t(unsigned, v / 2, 1024);
49 } else if (e->m > v) {
50 e->m = e->m >= e->step
53 } else if (e->m < v) {
54 e->m = e->m + e->step > e->m
59 if ((e->m > v ? e->m - v : v - e->m) < e->step)
60 e->step = max_t(unsigned, e->step / 2, 1);
65 i = eytzinger0_child(i, v > e->m);
69 static inline void time_stats_update_one(struct time_stats *stats,
73 bool initted = stats->last_event != 0;
75 if (time_after64(end, start)) {
76 struct quantiles *quantiles = time_stats_to_quantiles(stats);
78 duration = end - start;
79 mean_and_variance_update(&stats->duration_stats, duration);
80 mean_and_variance_weighted_update(&stats->duration_stats_weighted,
81 duration, initted, TIME_STATS_MV_WEIGHT);
82 stats->max_duration = max(stats->max_duration, duration);
83 stats->min_duration = min(stats->min_duration, duration);
84 stats->total_duration += duration;
87 quantiles_update(quantiles, duration);
90 if (stats->last_event && time_after64(end, stats->last_event)) {
91 freq = end - stats->last_event;
92 mean_and_variance_update(&stats->freq_stats, freq);
93 mean_and_variance_weighted_update(&stats->freq_stats_weighted,
94 freq, initted, TIME_STATS_MV_WEIGHT);
95 stats->max_freq = max(stats->max_freq, freq);
96 stats->min_freq = min(stats->min_freq, freq);
99 stats->last_event = end;
102 void __time_stats_clear_buffer(struct time_stats *stats,
103 struct time_stat_buffer *b)
105 for (struct time_stat_buffer_entry *i = b->entries;
106 i < b->entries + ARRAY_SIZE(b->entries);
108 time_stats_update_one(stats, i->start, i->end);
111 EXPORT_SYMBOL_GPL(__time_stats_clear_buffer);
113 static noinline void time_stats_clear_buffer(struct time_stats *stats,
114 struct time_stat_buffer *b)
118 spin_lock_irqsave(&stats->lock, flags);
119 __time_stats_clear_buffer(stats, b);
120 spin_unlock_irqrestore(&stats->lock, flags);
123 void __time_stats_update(struct time_stats *stats, u64 start, u64 end)
127 if (!stats->buffer) {
128 spin_lock_irqsave(&stats->lock, flags);
129 time_stats_update_one(stats, start, end);
131 if (mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT) < 32 &&
132 stats->duration_stats.n > 1024)
134 alloc_percpu_gfp(struct time_stat_buffer,
136 spin_unlock_irqrestore(&stats->lock, flags);
138 struct time_stat_buffer *b;
141 b = this_cpu_ptr(stats->buffer);
143 BUG_ON(b->nr >= ARRAY_SIZE(b->entries));
144 b->entries[b->nr++] = (struct time_stat_buffer_entry) {
149 if (unlikely(b->nr == ARRAY_SIZE(b->entries)))
150 time_stats_clear_buffer(stats, b);
154 EXPORT_SYMBOL_GPL(__time_stats_update);
156 #include <linux/seq_buf.h>
158 static void seq_buf_time_units_aligned(struct seq_buf *out, u64 ns)
160 const struct time_unit *u = pick_time_units(ns);
162 seq_buf_printf(out, "%8llu %s", div64_u64(ns, u->nsecs), u->name);
165 static inline u64 time_stats_lifetime(const struct time_stats *stats)
167 return local_clock() - stats->start_time;
170 void time_stats_to_seq_buf(struct seq_buf *out, struct time_stats *stats,
171 const char *epoch_name, unsigned int flags)
173 struct quantiles *quantiles = time_stats_to_quantiles(stats);
174 s64 f_mean = 0, d_mean = 0;
175 u64 f_stddev = 0, d_stddev = 0;
176 u64 lifetime = time_stats_lifetime(stats);
181 spin_lock_irq(&stats->lock);
182 for_each_possible_cpu(cpu)
183 __time_stats_clear_buffer(stats, per_cpu_ptr(stats->buffer, cpu));
184 spin_unlock_irq(&stats->lock);
187 if (stats->freq_stats.n) {
188 /* avoid divide by zero */
189 f_mean = mean_and_variance_get_mean(stats->freq_stats);
190 f_stddev = mean_and_variance_get_stddev(stats->freq_stats);
191 d_mean = mean_and_variance_get_mean(stats->duration_stats);
192 d_stddev = mean_and_variance_get_stddev(stats->duration_stats);
193 } else if (flags & TIME_STATS_PRINT_NO_ZEROES) {
194 /* unless we didn't want zeroes anyway */
198 seq_buf_printf(out, "count: %llu\n", stats->duration_stats.n);
199 seq_buf_printf(out, "lifetime: ");
200 seq_buf_time_units_aligned(out, lifetime);
201 seq_buf_printf(out, "\n");
203 seq_buf_printf(out, " since %-12s recent\n", epoch_name);
205 seq_buf_printf(out, "duration of events\n");
207 seq_buf_printf(out, " min: ");
208 seq_buf_time_units_aligned(out, stats->min_duration);
209 seq_buf_printf(out, "\n");
211 seq_buf_printf(out, " max: ");
212 seq_buf_time_units_aligned(out, stats->max_duration);
213 seq_buf_printf(out, "\n");
215 seq_buf_printf(out, " total: ");
216 seq_buf_time_units_aligned(out, stats->total_duration);
217 seq_buf_printf(out, "\n");
219 seq_buf_printf(out, " mean: ");
220 seq_buf_time_units_aligned(out, d_mean);
221 seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT));
222 seq_buf_printf(out, "\n");
224 seq_buf_printf(out, " stddev: ");
225 seq_buf_time_units_aligned(out, d_stddev);
226 seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT));
227 seq_buf_printf(out, "\n");
229 seq_buf_printf(out, "time between events\n");
231 seq_buf_printf(out, " min: ");
232 seq_buf_time_units_aligned(out, stats->min_freq);
233 seq_buf_printf(out, "\n");
235 seq_buf_printf(out, " max: ");
236 seq_buf_time_units_aligned(out, stats->max_freq);
237 seq_buf_printf(out, "\n");
239 seq_buf_printf(out, " mean: ");
240 seq_buf_time_units_aligned(out, f_mean);
241 seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT));
242 seq_buf_printf(out, "\n");
244 seq_buf_printf(out, " stddev: ");
245 seq_buf_time_units_aligned(out, f_stddev);
246 seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT));
247 seq_buf_printf(out, "\n");
250 int i = eytzinger0_first(NR_QUANTILES);
251 const struct time_unit *u =
252 pick_time_units(quantiles->entries[i].m);
255 seq_buf_printf(out, "quantiles (%s):\t", u->name);
256 eytzinger0_for_each(i, NR_QUANTILES) {
257 bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1;
259 u64 q = max(quantiles->entries[i].m, last_q);
260 seq_buf_printf(out, "%llu ", div_u64(q, u->nsecs));
262 seq_buf_printf(out, "\n");
267 EXPORT_SYMBOL_GPL(time_stats_to_seq_buf);
269 void time_stats_to_json(struct seq_buf *out, struct time_stats *stats,
270 const char *epoch_name, unsigned int flags)
272 struct quantiles *quantiles = time_stats_to_quantiles(stats);
273 s64 f_mean = 0, d_mean = 0;
274 u64 f_stddev = 0, d_stddev = 0;
279 spin_lock_irq(&stats->lock);
280 for_each_possible_cpu(cpu)
281 __time_stats_clear_buffer(stats, per_cpu_ptr(stats->buffer, cpu));
282 spin_unlock_irq(&stats->lock);
285 if (stats->freq_stats.n) {
286 /* avoid divide by zero */
287 f_mean = mean_and_variance_get_mean(stats->freq_stats);
288 f_stddev = mean_and_variance_get_stddev(stats->freq_stats);
289 d_mean = mean_and_variance_get_mean(stats->duration_stats);
290 d_stddev = mean_and_variance_get_stddev(stats->duration_stats);
291 } else if (flags & TIME_STATS_PRINT_NO_ZEROES) {
292 /* unless we didn't want zeroes anyway */
296 seq_buf_printf(out, "{\n");
297 seq_buf_printf(out, " \"epoch\": \"%s\",\n", epoch_name);
298 seq_buf_printf(out, " \"count\": %llu,\n", stats->duration_stats.n);
300 seq_buf_printf(out, " \"duration_ns\": {\n");
301 seq_buf_printf(out, " \"min\": %llu,\n", stats->min_duration);
302 seq_buf_printf(out, " \"max\": %llu,\n", stats->max_duration);
303 seq_buf_printf(out, " \"total\": %llu,\n", stats->total_duration);
304 seq_buf_printf(out, " \"mean\": %llu,\n", d_mean);
305 seq_buf_printf(out, " \"stddev\": %llu\n", d_stddev);
306 seq_buf_printf(out, " },\n");
308 d_mean = mean_and_variance_weighted_get_mean(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT);
309 d_stddev = mean_and_variance_weighted_get_stddev(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT);
311 seq_buf_printf(out, " \"duration_ewma_ns\": {\n");
312 seq_buf_printf(out, " \"mean\": %llu,\n", d_mean);
313 seq_buf_printf(out, " \"stddev\": %llu\n", d_stddev);
314 seq_buf_printf(out, " },\n");
316 seq_buf_printf(out, " \"frequency_ns\": {\n");
317 seq_buf_printf(out, " \"min\": %llu,\n", stats->min_freq);
318 seq_buf_printf(out, " \"max\": %llu,\n", stats->max_freq);
319 seq_buf_printf(out, " \"mean\": %llu,\n", f_mean);
320 seq_buf_printf(out, " \"stddev\": %llu\n", f_stddev);
321 seq_buf_printf(out, " },\n");
323 f_mean = mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT);
324 f_stddev = mean_and_variance_weighted_get_stddev(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT);
326 seq_buf_printf(out, " \"frequency_ewma_ns\": {\n");
327 seq_buf_printf(out, " \"mean\": %llu,\n", f_mean);
328 seq_buf_printf(out, " \"stddev\": %llu\n", f_stddev);
333 /* close frequency_ewma_ns but signal more items */
334 seq_buf_printf(out, " },\n");
336 seq_buf_printf(out, " \"quantiles_ns\": [\n");
337 eytzinger0_for_each(i, NR_QUANTILES) {
338 bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1;
340 u64 q = max(quantiles->entries[i].m, last_q);
341 seq_buf_printf(out, " %llu", q);
343 seq_buf_printf(out, ", ");
346 seq_buf_printf(out, " ]\n");
348 /* close frequency_ewma_ns without dumping further */
349 seq_buf_printf(out, " }\n");
352 seq_buf_printf(out, "}\n");
354 EXPORT_SYMBOL_GPL(time_stats_to_json);
356 void time_stats_exit(struct time_stats *stats)
358 free_percpu(stats->buffer);
360 EXPORT_SYMBOL_GPL(time_stats_exit);
362 void time_stats_init(struct time_stats *stats)
364 memset(stats, 0, sizeof(*stats));
365 stats->min_duration = U64_MAX;
366 stats->min_freq = U64_MAX;
367 stats->start_time = local_clock();
368 spin_lock_init(&stats->lock);
370 EXPORT_SYMBOL_GPL(time_stats_init);
372 MODULE_AUTHOR("Kent Overstreet");
373 MODULE_LICENSE("GPL");