1// SPDX-License-Identifier: GPL-2.0
2
3#include <linux/jiffies.h>
4#include <linux/module.h>
5#include <linux/percpu.h>
6#include <linux/preempt.h>
7#include <linux/time.h>
8#include <linux/spinlock.h>
9
10#include "eytzinger.h"
11#include "time_stats.h"
12
13static const struct time_unit time_units[] = {
14	{ "ns",		1		 },
15	{ "us",		NSEC_PER_USEC	 },
16	{ "ms",		NSEC_PER_MSEC	 },
17	{ "s",		NSEC_PER_SEC	 },
18	{ "m",          (u64) NSEC_PER_SEC * 60},
19	{ "h",          (u64) NSEC_PER_SEC * 3600},
20	{ "d",          (u64) NSEC_PER_SEC * 3600 * 24},
21	{ "w",          (u64) NSEC_PER_SEC * 3600 * 24 * 7},
22	{ "y",          (u64) NSEC_PER_SEC * ((3600 * 24 * 7 * 365) + (3600 * (24 / 4) * 7))}, /* 365.25d */
23	{ "eon",        U64_MAX          },
24};
25
26const struct time_unit *bch2_pick_time_units(u64 ns)
27{
28	const struct time_unit *u;
29
30	for (u = time_units;
31	     u + 1 < time_units + ARRAY_SIZE(time_units) &&
32	     ns >= u[1].nsecs << 1;
33	     u++)
34		;
35
36	return u;
37}
38
39static void quantiles_update(struct quantiles *q, u64 v)
40{
41	unsigned i = 0;
42
43	while (i < ARRAY_SIZE(q->entries)) {
44		struct quantile_entry *e = q->entries + i;
45
46		if (unlikely(!e->step)) {
47			e->m = v;
48			e->step = max_t(unsigned, v / 2, 1024);
49		} else if (e->m > v) {
50			e->m = e->m >= e->step
51				? e->m - e->step
52				: 0;
53		} else if (e->m < v) {
54			e->m = e->m + e->step > e->m
55				? e->m + e->step
56				: U32_MAX;
57		}
58
59		if ((e->m > v ? e->m - v : v - e->m) < e->step)
60			e->step = max_t(unsigned, e->step / 2, 1);
61
62		if (v >= e->m)
63			break;
64
65		i = eytzinger0_child(i, v > e->m);
66	}
67}
68
69static inline void time_stats_update_one(struct bch2_time_stats *stats,
70					      u64 start, u64 end)
71{
72	u64 duration, freq;
73	bool initted = stats->last_event != 0;
74
75	if (time_after64(end, start)) {
76		struct quantiles *quantiles = time_stats_to_quantiles(stats);
77
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;
85
86		if (quantiles)
87			quantiles_update(quantiles, duration);
88	}
89
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);
97	}
98
99	stats->last_event = end;
100}
101
102void __bch2_time_stats_clear_buffer(struct bch2_time_stats *stats,
103				    struct time_stat_buffer *b)
104{
105	for (struct time_stat_buffer_entry *i = b->entries;
106	     i < b->entries + ARRAY_SIZE(b->entries);
107	     i++)
108		time_stats_update_one(stats, i->start, i->end);
109	b->nr = 0;
110}
111
112static noinline void time_stats_clear_buffer(struct bch2_time_stats *stats,
113					     struct time_stat_buffer *b)
114{
115	unsigned long flags;
116
117	spin_lock_irqsave(&stats->lock, flags);
118	__bch2_time_stats_clear_buffer(stats, b);
119	spin_unlock_irqrestore(&stats->lock, flags);
120}
121
122void __bch2_time_stats_update(struct bch2_time_stats *stats, u64 start, u64 end)
123{
124	unsigned long flags;
125
126	if (!stats->buffer) {
127		spin_lock_irqsave(&stats->lock, flags);
128		time_stats_update_one(stats, start, end);
129
130		if (mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT) < 32 &&
131		    stats->duration_stats.n > 1024)
132			stats->buffer =
133				alloc_percpu_gfp(struct time_stat_buffer,
134						 GFP_ATOMIC);
135		spin_unlock_irqrestore(&stats->lock, flags);
136	} else {
137		struct time_stat_buffer *b;
138
139		preempt_disable();
140		b = this_cpu_ptr(stats->buffer);
141
142		BUG_ON(b->nr >= ARRAY_SIZE(b->entries));
143		b->entries[b->nr++] = (struct time_stat_buffer_entry) {
144			.start = start,
145			.end = end
146		};
147
148		if (unlikely(b->nr == ARRAY_SIZE(b->entries)))
149			time_stats_clear_buffer(stats, b);
150		preempt_enable();
151	}
152}
153
154void bch2_time_stats_exit(struct bch2_time_stats *stats)
155{
156	free_percpu(stats->buffer);
157}
158
159void bch2_time_stats_init(struct bch2_time_stats *stats)
160{
161	memset(stats, 0, sizeof(*stats));
162	stats->min_duration = U64_MAX;
163	stats->min_freq = U64_MAX;
164	spin_lock_init(&stats->lock);
165}
166