From: Suren Baghdasaryan <[email protected]>
To: [email protected]
Cc: [email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected],
[email protected], [email protected],
[email protected], [email protected],
[email protected], [email protected]
Subject: [RFC PATCH 25/30] lib/time_stats: New library for statistics on events
Date: Tue, 30 Aug 2022 14:49:14 -0700 [thread overview]
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
From: Kent Overstreet <[email protected]>
This adds a small new library for tracking statistics on events that
have a duration, i.e. a start and end time.
- number of events
- rate/frequency
- average duration
- max duration
- duration quantiles
This code comes from bcachefs, and originally bcache: the next patch
will be converting bcache to use this version, and a subsequent patch
will be using code_tagging to instrument all wait_event() calls in the
kernel.
Signed-off-by: Kent Overstreet <[email protected]>
---
include/linux/time_stats.h | 44 +++++++
lib/Kconfig | 3 +
lib/Makefile | 1 +
lib/time_stats.c | 236 +++++++++++++++++++++++++++++++++++++
4 files changed, 284 insertions(+)
create mode 100644 include/linux/time_stats.h
create mode 100644 lib/time_stats.c
diff --git a/include/linux/time_stats.h b/include/linux/time_stats.h
new file mode 100644
index 000000000000..7ae929e6f836
--- /dev/null
+++ b/include/linux/time_stats.h
@@ -0,0 +1,44 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef _LINUX_TIMESTATS_H
+#define _LINUX_TIMESTATS_H
+
+#include <linux/spinlock_types.h>
+#include <linux/types.h>
+
+#define NR_QUANTILES 15
+
+struct quantiles {
+ struct quantile_entry {
+ u64 m;
+ u64 step;
+ } entries[NR_QUANTILES];
+};
+
+struct time_stat_buffer {
+ unsigned int nr;
+ struct time_stat_buffer_entry {
+ u64 start;
+ u64 end;
+ } entries[32];
+};
+
+struct time_stats {
+ spinlock_t lock;
+ u64 count;
+ /* all fields are in nanoseconds */
+ u64 average_duration;
+ u64 average_frequency;
+ u64 max_duration;
+ u64 last_event;
+ struct quantiles quantiles;
+
+ struct time_stat_buffer __percpu *buffer;
+};
+
+struct seq_buf;
+void time_stats_update(struct time_stats *stats, u64 start);
+void time_stats_to_text(struct seq_buf *out, struct time_stats *stats);
+void time_stats_exit(struct time_stats *stats);
+
+#endif /* _LINUX_TIMESTATS_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index fc6dbc425728..884fd9f2f06d 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -744,3 +744,6 @@ config ASN1_ENCODER
config POLYNOMIAL
tristate
+
+config TIME_STATS
+ bool
diff --git a/lib/Makefile b/lib/Makefile
index 489ea000c528..e54392011f5e 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -232,6 +232,7 @@ obj-$(CONFIG_ALLOC_TAGGING) += alloc_tag.o
obj-$(CONFIG_PAGE_ALLOC_TAGGING) += pgalloc_tag.o
obj-$(CONFIG_CODETAG_FAULT_INJECTION) += dynamic_fault.o
+obj-$(CONFIG_TIME_STATS) += time_stats.o
lib-$(CONFIG_GENERIC_BUG) += bug.o
diff --git a/lib/time_stats.c b/lib/time_stats.c
new file mode 100644
index 000000000000..30362364fdd2
--- /dev/null
+++ b/lib/time_stats.c
@@ -0,0 +1,236 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <linux/gfp.h>
+#include <linux/jiffies.h>
+#include <linux/kernel.h>
+#include <linux/ktime.h>
+#include <linux/percpu.h>
+#include <linux/seq_buf.h>
+#include <linux/spinlock.h>
+#include <linux/time_stats.h>
+#include <linux/timekeeping.h>
+
+static inline unsigned int eytzinger1_child(unsigned int i, unsigned int child)
+{
+ return (i << 1) + child;
+}
+
+static inline unsigned int eytzinger1_right_child(unsigned int i)
+{
+ return eytzinger1_child(i, 1);
+}
+
+static inline unsigned int eytzinger1_next(unsigned int i, unsigned int size)
+{
+ if (eytzinger1_right_child(i) <= size) {
+ i = eytzinger1_right_child(i);
+
+ i <<= __fls(size + 1) - __fls(i);
+ i >>= i > size;
+ } else {
+ i >>= ffz(i) + 1;
+ }
+
+ return i;
+}
+
+static inline unsigned int eytzinger0_child(unsigned int i, unsigned int child)
+{
+ return (i << 1) + 1 + child;
+}
+
+static inline unsigned int eytzinger0_first(unsigned int size)
+{
+ return rounddown_pow_of_two(size) - 1;
+}
+
+static inline unsigned int eytzinger0_next(unsigned int i, unsigned int size)
+{
+ return eytzinger1_next(i + 1, size) - 1;
+}
+
+#define eytzinger0_for_each(_i, _size) \
+ for ((_i) = eytzinger0_first((_size)); \
+ (_i) != -1; \
+ (_i) = eytzinger0_next((_i), (_size)))
+
+#define ewma_add(ewma, val, weight) \
+({ \
+ typeof(ewma) _ewma = (ewma); \
+ typeof(weight) _weight = (weight); \
+ \
+ (((_ewma << _weight) - _ewma) + (val)) >> _weight; \
+})
+
+static void quantiles_update(struct quantiles *q, u64 v)
+{
+ unsigned int i = 0;
+
+ while (i < ARRAY_SIZE(q->entries)) {
+ struct quantile_entry *e = q->entries + i;
+
+ if (unlikely(!e->step)) {
+ e->m = v;
+ e->step = max_t(unsigned int, v / 2, 1024);
+ } else if (e->m > v) {
+ e->m = e->m >= e->step
+ ? e->m - e->step
+ : 0;
+ } else if (e->m < v) {
+ e->m = e->m + e->step > e->m
+ ? e->m + e->step
+ : U32_MAX;
+ }
+
+ if ((e->m > v ? e->m - v : v - e->m) < e->step)
+ e->step = max_t(unsigned int, e->step / 2, 1);
+
+ if (v >= e->m)
+ break;
+
+ i = eytzinger0_child(i, v > e->m);
+ }
+}
+
+static void time_stats_update_one(struct time_stats *stats,
+ u64 start, u64 end)
+{
+ u64 duration, freq;
+
+ duration = time_after64(end, start)
+ ? end - start : 0;
+ freq = time_after64(end, stats->last_event)
+ ? end - stats->last_event : 0;
+
+ stats->count++;
+
+ stats->average_duration = stats->average_duration
+ ? ewma_add(stats->average_duration, duration, 6)
+ : duration;
+
+ stats->average_frequency = stats->average_frequency
+ ? ewma_add(stats->average_frequency, freq, 6)
+ : freq;
+
+ stats->max_duration = max(stats->max_duration, duration);
+
+ stats->last_event = end;
+
+ quantiles_update(&stats->quantiles, duration);
+}
+
+void time_stats_update(struct time_stats *stats, u64 start)
+{
+ u64 end = ktime_get_ns();
+ unsigned long flags;
+
+ if (!stats->buffer) {
+ spin_lock_irqsave(&stats->lock, flags);
+ time_stats_update_one(stats, start, end);
+
+ if (stats->average_frequency < 32 &&
+ stats->count > 1024)
+ stats->buffer =
+ alloc_percpu_gfp(struct time_stat_buffer,
+ GFP_ATOMIC);
+ spin_unlock_irqrestore(&stats->lock, flags);
+ } else {
+ struct time_stat_buffer_entry *i;
+ struct time_stat_buffer *b;
+
+ preempt_disable();
+ b = this_cpu_ptr(stats->buffer);
+
+ BUG_ON(b->nr >= ARRAY_SIZE(b->entries));
+ b->entries[b->nr++] = (struct time_stat_buffer_entry) {
+ .start = start,
+ .end = end
+ };
+
+ if (b->nr == ARRAY_SIZE(b->entries)) {
+ spin_lock_irqsave(&stats->lock, flags);
+ for (i = b->entries;
+ i < b->entries + ARRAY_SIZE(b->entries);
+ i++)
+ time_stats_update_one(stats, i->start, i->end);
+ spin_unlock_irqrestore(&stats->lock, flags);
+
+ b->nr = 0;
+ }
+
+ preempt_enable();
+ }
+}
+EXPORT_SYMBOL(time_stats_update);
+
+static const struct time_unit {
+ const char *name;
+ u32 nsecs;
+} time_units[] = {
+ { "ns", 1 },
+ { "us", NSEC_PER_USEC },
+ { "ms", NSEC_PER_MSEC },
+ { "sec", NSEC_PER_SEC },
+};
+
+static const struct time_unit *pick_time_units(u64 ns)
+{
+ const struct time_unit *u;
+
+ for (u = time_units;
+ u + 1 < time_units + ARRAY_SIZE(time_units) &&
+ ns >= u[1].nsecs << 1;
+ u++)
+ ;
+
+ return u;
+}
+
+static void pr_time_units(struct seq_buf *out, u64 ns)
+{
+ const struct time_unit *u = pick_time_units(ns);
+
+ seq_buf_printf(out, "%llu %s", div_u64(ns, u->nsecs), u->name);
+}
+
+void time_stats_to_text(struct seq_buf *out, struct time_stats *stats)
+{
+ const struct time_unit *u;
+ u64 freq = READ_ONCE(stats->average_frequency);
+ u64 q, last_q = 0;
+ int i;
+
+ seq_buf_printf(out, "count: %llu\n", stats->count);
+ seq_buf_printf(out, "rate: %llu/sec\n",
+ freq ? div64_u64(NSEC_PER_SEC, freq) : 0);
+ seq_buf_printf(out, "frequency: ");
+ pr_time_units(out, freq);
+ seq_buf_putc(out, '\n');
+
+ seq_buf_printf(out, "avg duration: ");
+ pr_time_units(out, stats->average_duration);
+ seq_buf_putc(out, '\n');
+
+ seq_buf_printf(out, "max duration: ");
+ pr_time_units(out, stats->max_duration);
+ seq_buf_putc(out, '\n');
+
+ i = eytzinger0_first(NR_QUANTILES);
+ u = pick_time_units(stats->quantiles.entries[i].m);
+ seq_buf_printf(out, "quantiles (%s): ", u->name);
+ eytzinger0_for_each(i, NR_QUANTILES) {
+ q = max(stats->quantiles.entries[i].m, last_q);
+ seq_buf_printf(out, "%llu ", div_u64(q, u->nsecs));
+ last_q = q;
+ }
+
+ seq_buf_putc(out, '\n');
+}
+EXPORT_SYMBOL_GPL(time_stats_to_text);
+
+void time_stats_exit(struct time_stats *stats)
+{
+ free_percpu(stats->buffer);
+ stats->buffer = NULL;
+}
+EXPORT_SYMBOL_GPL(time_stats_exit);
--
2.37.2.672.g94769d06f0-goog
next prev parent reply other threads:[~2022-08-30 21:53 UTC|newest]
Thread overview: 138+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-08-30 21:48 [RFC PATCH 00/30] Code tagging framework and applications Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 01/30] kernel/module: move find_kallsyms_symbol_value declaration Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 02/30] lib/string_helpers: Drop space in string_get_size's output Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 03/30] Lazy percpu counters Suren Baghdasaryan
2022-08-31 10:02 ` Mel Gorman
2022-08-31 15:37 ` Suren Baghdasaryan
2022-08-31 16:20 ` Kent Overstreet
2022-09-01 6:51 ` Peter Zijlstra
2022-09-01 14:32 ` Kent Overstreet
2022-09-01 14:48 ` Steven Rostedt
2022-09-01 15:43 ` Kent Overstreet
2022-09-01 18:59 ` Peter Zijlstra
2022-08-30 21:48 ` [RFC PATCH 04/30] scripts/kallysms: Always include __start and __stop symbols Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 05/30] lib: code tagging framework Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 06/30] lib: code tagging module support Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 07/30] lib: add support for allocation tagging Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 08/30] lib: introduce page " Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 09/30] change alloc_pages name in dma_map_ops to avoid name conflicts Suren Baghdasaryan
2022-08-30 21:48 ` [RFC PATCH 10/30] mm: enable page allocation tagging for __get_free_pages and alloc_pages Suren Baghdasaryan
2022-08-31 10:11 ` Mel Gorman
2022-08-31 15:45 ` Suren Baghdasaryan
2022-08-31 15:52 ` Suren Baghdasaryan
2022-08-31 17:46 ` Kent Overstreet
2022-09-01 1:07 ` Suren Baghdasaryan
2022-09-01 7:41 ` Peter Zijlstra
2022-08-30 21:49 ` [RFC PATCH 11/30] mm: introduce slabobj_ext to support slab object extensions Suren Baghdasaryan
2022-09-01 23:35 ` Roman Gushchin
2022-09-02 0:23 ` Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 12/30] mm: introduce __GFP_NO_OBJ_EXT flag to selectively prevent slabobj_ext creation Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 13/30] mm/slab: introduce SLAB_NO_OBJ_EXT to avoid obj_ext creation Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 14/30] mm: prevent slabobj_ext allocations for slabobj_ext and kmem_cache objects Suren Baghdasaryan
2022-09-01 23:40 ` Roman Gushchin
2022-09-02 0:24 ` Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 15/30] lib: introduce slab allocation tagging Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 16/30] mm: enable slab allocation tagging for kmalloc and friends Suren Baghdasaryan
2022-09-01 23:50 ` Roman Gushchin
2022-08-30 21:49 ` [RFC PATCH 17/30] lib/string.c: strsep_no_empty() Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 18/30] codetag: add codetag query helper functions Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 19/30] move stack capture functionality into a separate function for reuse Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 20/30] lib: introduce support for storing code tag context Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 21/30] lib: implement context capture support for page and slab allocators Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 22/30] Code tagging based fault injection Suren Baghdasaryan
2022-08-31 1:51 ` Randy Dunlap
2022-08-31 15:56 ` Suren Baghdasaryan
2022-08-31 10:37 ` Dmitry Vyukov
2022-08-31 15:51 ` Suren Baghdasaryan
2022-08-31 17:30 ` Kent Overstreet
2022-09-01 8:43 ` Dmitry Vyukov
2022-08-30 21:49 ` [RFC PATCH 23/30] timekeeping: Add a missing include Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 24/30] wait: Clean up waitqueue_entry initialization Suren Baghdasaryan
2022-08-30 21:49 ` Suren Baghdasaryan [this message]
2022-08-30 21:49 ` [RFC PATCH 26/30] bcache: Convert to lib/time_stats Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 27/30] Code tagging based latency tracking Suren Baghdasaryan
2022-08-31 1:53 ` Randy Dunlap
2022-08-31 15:55 ` Suren Baghdasaryan
2022-09-01 7:11 ` Peter Zijlstra
2022-09-01 14:43 ` Kent Overstreet
2022-09-01 21:38 ` Steven Rostedt
2022-09-01 21:46 ` Steven Rostedt
2022-09-01 21:54 ` Kent Overstreet
2022-09-01 22:34 ` Steven Rostedt
2022-09-01 22:55 ` Kent Overstreet
2022-09-02 0:23 ` Steven Rostedt
2022-09-02 1:35 ` Kent Overstreet
2022-09-02 1:59 ` Steven Rostedt
2022-08-30 21:49 ` [RFC PATCH 28/30] Improved symbolic error names Suren Baghdasaryan
2022-09-01 23:19 ` Joe Perches
2022-09-01 23:26 ` Kent Overstreet
2022-08-30 21:49 ` [RFC PATCH 29/30] dyndbg: Convert to code tagging Suren Baghdasaryan
2022-08-30 21:49 ` [RFC PATCH 30/30] MAINTAINERS: Add entries for code tagging & related Suren Baghdasaryan
2022-08-31 7:38 ` [RFC PATCH 00/30] Code tagging framework and applications Peter Zijlstra
2022-08-31 8:42 ` Kent Overstreet
2022-08-31 10:19 ` Mel Gorman
2022-08-31 10:47 ` Michal Hocko
2022-08-31 15:28 ` Suren Baghdasaryan
2022-08-31 16:48 ` Suren Baghdasaryan
2022-08-31 19:01 ` Kent Overstreet
2022-08-31 20:56 ` Yosry Ahmed
2022-08-31 21:38 ` Suren Baghdasaryan
2022-09-01 22:27 ` Roman Gushchin
2022-09-01 22:37 ` Kent Overstreet
2022-09-01 22:53 ` Roman Gushchin
2022-09-01 23:36 ` Suren Baghdasaryan
2022-09-02 0:17 ` Kent Overstreet
2022-09-02 1:04 ` Roman Gushchin
2022-09-02 1:16 ` Kent Overstreet
2022-09-02 12:02 ` Jens Axboe
2022-09-02 19:48 ` Kent Overstreet
2022-09-02 19:53 ` Jens Axboe
2022-09-02 20:05 ` Kent Overstreet
2022-09-02 20:23 ` Jens Axboe
2022-09-01 7:18 ` Michal Hocko
2022-09-01 15:33 ` Suren Baghdasaryan
2022-09-01 19:15 ` Michal Hocko
2022-09-01 19:39 ` Suren Baghdasaryan
2022-09-01 20:15 ` Kent Overstreet
2022-09-05 8:49 ` Michal Hocko
2022-09-05 23:46 ` Kent Overstreet
2022-09-06 7:23 ` Michal Hocko
2022-09-06 18:20 ` Kent Overstreet
2022-09-07 11:00 ` Michal Hocko
2022-09-07 13:04 ` Kent Overstreet
2022-09-07 13:45 ` Steven Rostedt
2022-09-08 6:35 ` Kent Overstreet
2022-09-08 6:49 ` Suren Baghdasaryan
2022-09-08 7:07 ` Kent Overstreet
2022-09-08 7:12 ` Michal Hocko
2022-09-08 7:29 ` Kent Overstreet
2022-09-08 7:47 ` Michal Hocko
2022-09-05 1:32 ` Suren Baghdasaryan
2022-09-05 8:12 ` Michal Hocko
2022-09-05 8:58 ` Marco Elver
2022-09-05 18:07 ` Suren Baghdasaryan
2022-09-05 18:03 ` Suren Baghdasaryan
2022-09-06 8:01 ` Michal Hocko
2022-09-06 15:35 ` Suren Baghdasaryan
2022-09-05 15:07 ` Steven Rostedt
2022-09-05 18:08 ` Suren Baghdasaryan
2022-09-05 20:42 ` Kent Overstreet
2022-09-05 22:16 ` Steven Rostedt
2022-09-05 23:50 ` Kent Overstreet
2022-09-01 8:05 ` David Hildenbrand
2022-09-01 14:23 ` Kent Overstreet
2022-09-01 15:07 ` David Hildenbrand
2022-09-01 15:39 ` Suren Baghdasaryan
2022-09-01 15:48 ` Kent Overstreet
2022-08-31 15:59 ` Kent Overstreet
2022-09-01 7:05 ` Peter Zijlstra
2022-09-01 7:36 ` Daniel Bristot de Oliveira
2022-09-01 7:42 ` Peter Zijlstra
2022-09-01 11:05 ` Mel Gorman
2022-09-01 16:31 ` Kent Overstreet
2022-09-01 7:00 ` Peter Zijlstra
2022-09-01 14:29 ` Kent Overstreet
2022-09-05 18:44 ` Nadav Amit
2022-09-05 19:16 ` Steven Rostedt
2022-09-01 4:52 ` Oscar Salvador
2022-09-01 5:05 ` Suren Baghdasaryan
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
[email protected] \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox