git.sesse.net Git - bcachefs-tools-debian/blob - linux/time_stats.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include <linux/eytzinger.h>
   4 #include <linux/jiffies.h>
   5 #include <linux/module.h>
   6 #include <linux/percpu.h>
   7 #include <linux/preempt.h>
   8 #include <linux/time.h>
   9 #include <linux/time_stats.h>
  10 #include <linux/spinlock.h>
  11
  12 static const struct time_unit time_units[] = {
  13         { "ns",         1                },
  14         { "us",         NSEC_PER_USEC    },
  15         { "ms",         NSEC_PER_MSEC    },
  16         { "s",          NSEC_PER_SEC     },
  17         { "m",          (u64) NSEC_PER_SEC * 60},
  18         { "h",          (u64) NSEC_PER_SEC * 3600},
  19         { "d",          (u64) NSEC_PER_SEC * 3600 * 24},
  20         { "w",          (u64) NSEC_PER_SEC * 3600 * 24 * 7},
  21         { "y",          (u64) NSEC_PER_SEC * ((3600 * 24 * 7 * 365) + (3600 * (24 / 4) * 7))}, /* 365.25d */
  22         { "eon",        U64_MAX          },
  23 };
  24
  25 const struct time_unit *pick_time_units(u64 ns)
  26 {
  27         const struct time_unit *u;
  28
  29         for (u = time_units;
  30              u + 1 < time_units + ARRAY_SIZE(time_units) &&
  31              ns >= u[1].nsecs << 1;
  32              u++)
  33                 ;
  34
  35         return u;
  36 }
  37 EXPORT_SYMBOL_GPL(pick_time_units);
  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 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 __time_stats_clear_buffer(struct 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 EXPORT_SYMBOL_GPL(__time_stats_clear_buffer);
 112
 113 static noinline void time_stats_clear_buffer(struct time_stats *stats,
 114                                              struct time_stat_buffer *b)
 115 {
 116         unsigned long flags;
 117
 118         spin_lock_irqsave(&stats->lock, flags);
 119         __time_stats_clear_buffer(stats, b);
 120         spin_unlock_irqrestore(&stats->lock, flags);
 121 }
 122
 123 void __time_stats_update(struct time_stats *stats, u64 start, u64 end)
 124 {
 125         unsigned long flags;
 126
 127         if (!stats->buffer) {
 128                 spin_lock_irqsave(&stats->lock, flags);
 129                 time_stats_update_one(stats, start, end);
 130
 131                 if (mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT) < 32 &&
 132                     stats->duration_stats.n > 1024)
 133                         stats->buffer =
 134                                 alloc_percpu_gfp(struct time_stat_buffer,
 135                                                  GFP_ATOMIC);
 136                 spin_unlock_irqrestore(&stats->lock, flags);
 137         } else {
 138                 struct time_stat_buffer *b;
 139
 140                 preempt_disable();
 141                 b = this_cpu_ptr(stats->buffer);
 142
 143                 BUG_ON(b->nr >= ARRAY_SIZE(b->entries));
 144                 b->entries[b->nr++] = (struct time_stat_buffer_entry) {
 145                         .start = start,
 146                         .end = end
 147                 };
 148
 149                 if (unlikely(b->nr == ARRAY_SIZE(b->entries)))
 150                         time_stats_clear_buffer(stats, b);
 151                 preempt_enable();
 152         }
 153 }
 154 EXPORT_SYMBOL_GPL(__time_stats_update);
 155
 156 #include <linux/seq_buf.h>
 157
 158 static void seq_buf_time_units_aligned(struct seq_buf *out, u64 ns)
 159 {
 160         const struct time_unit *u = pick_time_units(ns);
 161
 162         seq_buf_printf(out, "%8llu %s", div64_u64(ns, u->nsecs), u->name);
 163 }
 164
 165 static inline u64 time_stats_lifetime(const struct time_stats *stats)
 166 {
 167         return local_clock() - stats->start_time;
 168 }
 169
 170 void time_stats_to_seq_buf(struct seq_buf *out, struct time_stats *stats,
 171                 const char *epoch_name, unsigned int flags)
 172 {
 173         struct quantiles *quantiles = time_stats_to_quantiles(stats);
 174         s64 f_mean = 0, d_mean = 0;
 175         u64 f_stddev = 0, d_stddev = 0;
 176         u64 lifetime = time_stats_lifetime(stats);
 177
 178         if (stats->buffer) {
 179                 int cpu;
 180
 181                 spin_lock_irq(&stats->lock);
 182                 for_each_possible_cpu(cpu)
 183                         __time_stats_clear_buffer(stats, per_cpu_ptr(stats->buffer, cpu));
 184                 spin_unlock_irq(&stats->lock);
 185         }
 186
 187         if (stats->freq_stats.n) {
 188                 /* avoid divide by zero */
 189                 f_mean = mean_and_variance_get_mean(stats->freq_stats);
 190                 f_stddev = mean_and_variance_get_stddev(stats->freq_stats);
 191                 d_mean = mean_and_variance_get_mean(stats->duration_stats);
 192                 d_stddev = mean_and_variance_get_stddev(stats->duration_stats);
 193         } else if (flags & TIME_STATS_PRINT_NO_ZEROES) {
 194                 /* unless we didn't want zeroes anyway */
 195                 return;
 196         }
 197
 198         seq_buf_printf(out, "count: %llu\n", stats->duration_stats.n);
 199         seq_buf_printf(out, "lifetime: ");
 200         seq_buf_time_units_aligned(out, lifetime);
 201         seq_buf_printf(out, "\n");
 202
 203         seq_buf_printf(out, "                       since %-12s recent\n", epoch_name);
 204
 205         seq_buf_printf(out, "duration of events\n");
 206
 207         seq_buf_printf(out, "  min:                     ");
 208         seq_buf_time_units_aligned(out, stats->min_duration);
 209         seq_buf_printf(out, "\n");
 210
 211         seq_buf_printf(out, "  max:                     ");
 212         seq_buf_time_units_aligned(out, stats->max_duration);
 213         seq_buf_printf(out, "\n");
 214
 215         seq_buf_printf(out, "  total:                   ");
 216         seq_buf_time_units_aligned(out, stats->total_duration);
 217         seq_buf_printf(out, "\n");
 218
 219         seq_buf_printf(out, "  mean:                    ");
 220         seq_buf_time_units_aligned(out, d_mean);
 221         seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT));
 222         seq_buf_printf(out, "\n");
 223
 224         seq_buf_printf(out, "  stddev:                  ");
 225         seq_buf_time_units_aligned(out, d_stddev);
 226         seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT));
 227         seq_buf_printf(out, "\n");
 228
 229         seq_buf_printf(out, "time between events\n");
 230
 231         seq_buf_printf(out, "  min:                     ");
 232         seq_buf_time_units_aligned(out, stats->min_freq);
 233         seq_buf_printf(out, "\n");
 234
 235         seq_buf_printf(out, "  max:                     ");
 236         seq_buf_time_units_aligned(out, stats->max_freq);
 237         seq_buf_printf(out, "\n");
 238
 239         seq_buf_printf(out, "  mean:                    ");
 240         seq_buf_time_units_aligned(out, f_mean);
 241         seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT));
 242         seq_buf_printf(out, "\n");
 243
 244         seq_buf_printf(out, "  stddev:                  ");
 245         seq_buf_time_units_aligned(out, f_stddev);
 246         seq_buf_time_units_aligned(out, mean_and_variance_weighted_get_stddev(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT));
 247         seq_buf_printf(out, "\n");
 248
 249         if (quantiles) {
 250                 int i = eytzinger0_first(NR_QUANTILES);
 251                 const struct time_unit *u =
 252                         pick_time_units(quantiles->entries[i].m);
 253                 u64 last_q = 0;
 254
 255                 seq_buf_printf(out, "quantiles (%s):\t", u->name);
 256                 eytzinger0_for_each(i, NR_QUANTILES) {
 257                         bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1;
 258
 259                         u64 q = max(quantiles->entries[i].m, last_q);
 260                         seq_buf_printf(out, "%llu ", div_u64(q, u->nsecs));
 261                         if (is_last)
 262                                 seq_buf_printf(out, "\n");
 263                         last_q = q;
 264                 }
 265         }
 266 }
 267 EXPORT_SYMBOL_GPL(time_stats_to_seq_buf);
 268
 269 void time_stats_to_json(struct seq_buf *out, struct time_stats *stats,
 270                 const char *epoch_name, unsigned int flags)
 271 {
 272         struct quantiles *quantiles = time_stats_to_quantiles(stats);
 273         s64 f_mean = 0, d_mean = 0;
 274         u64 f_stddev = 0, d_stddev = 0;
 275
 276         if (stats->buffer) {
 277                 int cpu;
 278
 279                 spin_lock_irq(&stats->lock);
 280                 for_each_possible_cpu(cpu)
 281                         __time_stats_clear_buffer(stats, per_cpu_ptr(stats->buffer, cpu));
 282                 spin_unlock_irq(&stats->lock);
 283         }
 284
 285         if (stats->freq_stats.n) {
 286                 /* avoid divide by zero */
 287                 f_mean = mean_and_variance_get_mean(stats->freq_stats);
 288                 f_stddev = mean_and_variance_get_stddev(stats->freq_stats);
 289                 d_mean = mean_and_variance_get_mean(stats->duration_stats);
 290                 d_stddev = mean_and_variance_get_stddev(stats->duration_stats);
 291         } else if (flags & TIME_STATS_PRINT_NO_ZEROES) {
 292                 /* unless we didn't want zeroes anyway */
 293                 return;
 294         }
 295
 296         seq_buf_printf(out, "{\n");
 297         seq_buf_printf(out, "  \"epoch\":       \"%s\",\n", epoch_name);
 298         seq_buf_printf(out, "  \"count\":       %llu,\n", stats->duration_stats.n);
 299
 300         seq_buf_printf(out, "  \"duration_ns\": {\n");
 301         seq_buf_printf(out, "    \"min\":       %llu,\n", stats->min_duration);
 302         seq_buf_printf(out, "    \"max\":       %llu,\n", stats->max_duration);
 303         seq_buf_printf(out, "    \"total\":     %llu,\n", stats->total_duration);
 304         seq_buf_printf(out, "    \"mean\":      %llu,\n", d_mean);
 305         seq_buf_printf(out, "    \"stddev\":    %llu\n", d_stddev);
 306         seq_buf_printf(out, "  },\n");
 307
 308         d_mean = mean_and_variance_weighted_get_mean(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT);
 309         d_stddev = mean_and_variance_weighted_get_stddev(stats->duration_stats_weighted, TIME_STATS_MV_WEIGHT);
 310
 311         seq_buf_printf(out, "  \"duration_ewma_ns\": {\n");
 312         seq_buf_printf(out, "    \"mean\":      %llu,\n", d_mean);
 313         seq_buf_printf(out, "    \"stddev\":    %llu\n", d_stddev);
 314         seq_buf_printf(out, "  },\n");
 315
 316         seq_buf_printf(out, "  \"frequency_ns\": {\n");
 317         seq_buf_printf(out, "    \"min\":       %llu,\n", stats->min_freq);
 318         seq_buf_printf(out, "    \"max\":       %llu,\n", stats->max_freq);
 319         seq_buf_printf(out, "    \"mean\":      %llu,\n", f_mean);
 320         seq_buf_printf(out, "    \"stddev\":    %llu\n", f_stddev);
 321         seq_buf_printf(out, "  },\n");
 322
 323         f_mean = mean_and_variance_weighted_get_mean(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT);
 324         f_stddev = mean_and_variance_weighted_get_stddev(stats->freq_stats_weighted, TIME_STATS_MV_WEIGHT);
 325
 326         seq_buf_printf(out, "  \"frequency_ewma_ns\": {\n");
 327         seq_buf_printf(out, "    \"mean\":      %llu,\n", f_mean);
 328         seq_buf_printf(out, "    \"stddev\":    %llu\n", f_stddev);
 329
 330         if (quantiles) {
 331                 u64 last_q = 0;
 332
 333                 /* close frequency_ewma_ns but signal more items */
 334                 seq_buf_printf(out, "  },\n");
 335
 336                 seq_buf_printf(out, "  \"quantiles_ns\": [\n");
 337                 eytzinger0_for_each(i, NR_QUANTILES) {
 338                         bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1;
 339
 340                         u64 q = max(quantiles->entries[i].m, last_q);
 341                         seq_buf_printf(out, "    %llu", q);
 342                         if (!is_last)
 343                                 seq_buf_printf(out, ", ");
 344                         last_q = q;
 345                 }
 346                 seq_buf_printf(out, "  ]\n");
 347         } else {
 348                 /* close frequency_ewma_ns without dumping further */
 349                 seq_buf_printf(out, "  }\n");
 350         }
 351
 352         seq_buf_printf(out, "}\n");
 353 }
 354 EXPORT_SYMBOL_GPL(time_stats_to_json);
 355
 356 void time_stats_exit(struct time_stats *stats)
 357 {
 358         free_percpu(stats->buffer);
 359 }
 360 EXPORT_SYMBOL_GPL(time_stats_exit);
 361
 362 void time_stats_init(struct time_stats *stats)
 363 {
 364         memset(stats, 0, sizeof(*stats));
 365         stats->min_duration = U64_MAX;
 366         stats->min_freq = U64_MAX;
 367         stats->start_time = local_clock();
 368         spin_lock_init(&stats->lock);
 369 }
 370 EXPORT_SYMBOL_GPL(time_stats_init);
 371
 372 MODULE_AUTHOR("Kent Overstreet");
 373 MODULE_LICENSE("GPL");