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 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 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 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 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 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 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 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 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 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 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