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, 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(&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
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, i->start, 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(&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(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
154 void bch2_time_stats_exit(struct bch2_time_stats *stats)
155 {
156 free_percpu(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
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.