fs/bcachefs/time_stats.c

   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_reset(struct bch2_time_stats *stats)
 155 {
 156         spin_lock_irq(&stats->lock);
 157         unsigned offset = offsetof(struct bch2_time_stats, min_duration);
 158         memset((void *) stats + offset, 0, sizeof(*stats) - offset);
 159
 160         if (stats->buffer) {
 161                 int cpu;
 162                 for_each_possible_cpu(cpu)
 163                         per_cpu_ptr(stats->buffer, cpu)->nr = 0;
 164         }
 165         spin_unlock_irq(&stats->lock);
 166 }
 167
 168 void bch2_time_stats_exit(struct bch2_time_stats *stats)
 169 {
 170         free_percpu(stats->buffer);
 171 }
 172
 173 void bch2_time_stats_init(struct bch2_time_stats *stats)
 174 {
 175         memset(stats, 0, sizeof(*stats));
 176         stats->min_duration = U64_MAX;
 177         stats->min_freq = U64_MAX;
 178         spin_lock_init(&stats->lock);
 179 }