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 /* disable automatic switching to percpu mode */
14 #define TIME_STATS_NONPCPU ((unsigned long) 1)
15
16 static const struct time_unit time_units[] = {
17 { "ns", 1 },
18 { "us", NSEC_PER_USEC },
19 { "ms", NSEC_PER_MSEC },
20 { "s", NSEC_PER_SEC },
21 { "m", (u64) NSEC_PER_SEC * 60},
22 { "h", (u64) NSEC_PER_SEC * 3600},
23 { "d", (u64) NSEC_PER_SEC * 3600 * 24},
24 { "w", (u64) NSEC_PER_SEC * 3600 * 24 * 7},
25 { "y", (u64) NSEC_PER_SEC * ((3600 * 24 * 7 * 365) + (3600 * (24 / 4) * 7))}, /* 365.25d */
26 { "eon", U64_MAX },
27 };
28
bch2_pick_time_units(u64 ns)29 const struct time_unit *bch2_pick_time_units(u64 ns)
30 {
31 const struct time_unit *u;
32
33 for (u = time_units;
34 u + 1 < time_units + ARRAY_SIZE(time_units) &&
35 ns >= u[1].nsecs << 1;
36 u++)
37 ;
38
39 return u;
40 }
41
quantiles_update(struct quantiles * q,u64 v)42 static void quantiles_update(struct quantiles *q, u64 v)
43 {
44 unsigned i = 0;
45
46 while (i < ARRAY_SIZE(q->entries)) {
47 struct quantile_entry *e = q->entries + i;
48
49 if (unlikely(!e->step)) {
50 e->m = v;
51 e->step = max_t(unsigned, v / 2, 1024);
52 } else if (e->m > v) {
53 e->m = e->m >= e->step
54 ? e->m - e->step
55 : 0;
56 } else if (e->m < v) {
57 e->m = e->m + e->step > e->m
58 ? e->m + e->step
59 : U32_MAX;
60 }
61
62 if ((e->m > v ? e->m - v : v - e->m) < e->step)
63 e->step = max_t(unsigned, e->step / 2, 1);
64
65 if (v >= e->m)
66 break;
67
68 i = eytzinger0_child(i, v > e->m);
69 }
70 }
71
time_stats_update_one(struct bch2_time_stats * stats,u64 start,u64 end)72 static inline void time_stats_update_one(struct bch2_time_stats *stats,
73 u64 start, u64 end)
74 {
75 u64 duration, freq;
76 bool initted = stats->last_event != 0;
77
78 if (time_after64(end, start)) {
79 struct quantiles *quantiles = time_stats_to_quantiles(stats);
80
81 duration = end - start;
82 mean_and_variance_update(&stats->duration_stats, duration);
83 mean_and_variance_weighted_update(&stats->duration_stats_weighted,
84 duration, initted, TIME_STATS_MV_WEIGHT);
85 stats->max_duration = max(stats->max_duration, duration);
86 stats->min_duration = min(stats->min_duration, duration);
87 stats->total_duration += duration;
88
89 if (quantiles)
90 quantiles_update(quantiles, duration);
91 }
92
93 if (stats->last_event && time_after64(end, stats->last_event)) {
94 freq = end - stats->last_event;
95 mean_and_variance_update(&stats->freq_stats, freq);
96 mean_and_variance_weighted_update(&stats->freq_stats_weighted,
97 freq, initted, TIME_STATS_MV_WEIGHT);
98 stats->max_freq = max(stats->max_freq, freq);
99 stats->min_freq = min(stats->min_freq, freq);
100 }
101
102 stats->last_event = end;
103 }
104
__bch2_time_stats_clear_buffer(struct bch2_time_stats * stats,struct time_stat_buffer * b)105 void __bch2_time_stats_clear_buffer(struct bch2_time_stats *stats,
106 struct time_stat_buffer *b)
107 {
108 for (struct time_stat_buffer_entry *i = b->entries;
109 i < b->entries + ARRAY_SIZE(b->entries);
110 i++)
111 time_stats_update_one(stats, i->start, i->end);
112 b->nr = 0;
113 }
114
time_stats_clear_buffer(struct bch2_time_stats * stats,struct time_stat_buffer * b)115 static noinline void time_stats_clear_buffer(struct bch2_time_stats *stats,
116 struct time_stat_buffer *b)
117 {
118 unsigned long flags;
119
120 spin_lock_irqsave(&stats->lock, flags);
121 __bch2_time_stats_clear_buffer(stats, b);
122 spin_unlock_irqrestore(&stats->lock, flags);
123 }
124
__bch2_time_stats_update(struct bch2_time_stats * stats,u64 start,u64 end)125 void __bch2_time_stats_update(struct bch2_time_stats *stats, u64 start, u64 end)
126 {
127 unsigned long flags;
128
129 if ((unsigned long) stats->buffer <= TIME_STATS_NONPCPU) {
130 spin_lock_irqsave(&stats->lock, flags);
131 time_stats_update_one(stats, start, end);
132
133 if (!stats->buffer &&
134 mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT) < 32 &&
135 stats->duration_stats.n > 1024)
136 stats->buffer =
137 alloc_percpu_gfp(struct time_stat_buffer,
138 GFP_ATOMIC);
139 spin_unlock_irqrestore(&stats->lock, flags);
140 } else {
141 struct time_stat_buffer *b;
142
143 preempt_disable();
144 b = this_cpu_ptr(stats->buffer);
145
146 BUG_ON(b->nr >= ARRAY_SIZE(b->entries));
147 b->entries[b->nr++] = (struct time_stat_buffer_entry) {
148 .start = start,
149 .end = end
150 };
151
152 if (unlikely(b->nr == ARRAY_SIZE(b->entries)))
153 time_stats_clear_buffer(stats, b);
154 preempt_enable();
155 }
156 }
157
bch2_time_stats_reset(struct bch2_time_stats * stats)158 void bch2_time_stats_reset(struct bch2_time_stats *stats)
159 {
160 spin_lock_irq(&stats->lock);
161 unsigned offset = offsetof(struct bch2_time_stats, min_duration);
162 memset((void *) stats + offset, 0, sizeof(*stats) - offset);
163
164 if ((unsigned long) stats->buffer > TIME_STATS_NONPCPU) {
165 int cpu;
166 for_each_possible_cpu(cpu)
167 per_cpu_ptr(stats->buffer, cpu)->nr = 0;
168 }
169 spin_unlock_irq(&stats->lock);
170 }
171
bch2_time_stats_exit(struct bch2_time_stats * stats)172 void bch2_time_stats_exit(struct bch2_time_stats *stats)
173 {
174 if ((unsigned long) stats->buffer > TIME_STATS_NONPCPU)
175 free_percpu(stats->buffer);
176 stats->buffer = NULL;
177 }
178
bch2_time_stats_init(struct bch2_time_stats * stats)179 void bch2_time_stats_init(struct bch2_time_stats *stats)
180 {
181 memset(stats, 0, sizeof(*stats));
182 stats->min_duration = U64_MAX;
183 stats->min_freq = U64_MAX;
184 spin_lock_init(&stats->lock);
185 }
186
bch2_time_stats_init_no_pcpu(struct bch2_time_stats * stats)187 void bch2_time_stats_init_no_pcpu(struct bch2_time_stats *stats)
188 {
189 bch2_time_stats_init(stats);
190 stats->buffer = (struct time_stat_buffer __percpu *) TIME_STATS_NONPCPU;
191 }
192