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 | |
13 | static 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 | |
26 | const 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 | |
39 | static 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, child: v > e->m); |
66 | } |
67 | } |
68 | |
69 | static 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(s: &stats->duration_stats, v: duration); |
80 | mean_and_variance_weighted_update(s: &stats->duration_stats_weighted, |
81 | v: 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(q: quantiles, v: 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(s: &stats->freq_stats, v: freq); |
93 | mean_and_variance_weighted_update(s: &stats->freq_stats_weighted, |
94 | v: 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 | |
102 | void __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, start: i->start, end: i->end); |
109 | b->nr = 0; |
110 | } |
111 | |
112 | static 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(lock: &stats->lock, flags); |
120 | } |
121 | |
122 | void __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(s: 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(lock: &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 | |
154 | void bch2_time_stats_exit(struct bch2_time_stats *stats) |
155 | { |
156 | free_percpu(pdata: stats->buffer); |
157 | } |
158 | |
159 | void 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 | |