[PATCH v8 0/5] tracing: Add stack trace deduplication for the ring buffer

[Li Pengfei <ljdlns1987@gmail.com>]

From: Pengfei Li <lipengfei28@xiaomi.com>

Hi Steven, Masami,

With options/stackmap set, ftrace records a 64-bit cookie (map
generation << 32 | slot) instead of a full stack. A stack stored in the
map is kept once per generation and exported as text in stack_map, with
counters in stack_map_stat. A stack the map cannot store is recorded in
full as before; a stack recorded while RCU is not watching is discarded.
A cookie only resolves against stack_map records of the same generation.

Use case: long tracing on phones, e.g. slab allocations with stacks from
early boot on, where the ring buffer and the storage are small and the
buffer fills with the same stacks over and over. With
trace_options=stackmap, stacks are deduplicated from tracefs
initialization on.

Measured on QEMU arm64 (4 CPUs, buffer_size_kb=512 per CPU),
kmem_cache_alloc with options/stacktrace, the same fixed workload in
both runs (100 rounds of 500 open()/close() of /proc/self/stat):

                  events retained   retained bytes/event
  stackmap off           4,867             107.4
  stackmap on           10,552              49.8

Bytes/event is the ring buffer data kept divided by the events kept, not
the size of one event. The gain depends on how often stacks repeat. This
measures retention only, not the CPU cost of the hash lookup; I only have
QEMU here, where timing numbers would not mean much.

This series is the core, the recording path, the statistics, the
documentation and a selftest. The binary export from v7 will carry the
generation in its header, so I would like the core and the cookie format
to settle first; the binary export, its parser and the capacity boot
parameter will follow as a separate series.

I used an LLM for a lot of this, the code and tests as well as the
comments and changelogs. The design is mine, and I went over every
change and the test results myself. After your v7 review I went through
the comments and changelogs again and cut most of them.

Design notes
============

- The hash table is modeled on tracing_map, the map behind hist
  triggers. The documentation lists where it differs: the slot index is
  the cookie, an insert that meets an unpublished element records the
  stack in full instead of spinning, and the map can be reset while
  tracing runs.
- Only the top level trace array is supported. A map per instance would
  multiply the memory, and boot-mapped instances could not resolve
  cookies against the running kernel's map.
- The capacity is fixed at 16384 stacks; stack_map_stat shows when that
  is too small. A boot parameter for the size comes with the follow-up.
- Turning the option off keeps the map, so the trace already in the
  buffer can still be resolved; writing "free" releases it. free waits
  until the stack_map files opened on the old map are closed, so a reader
  that started before it reads a complete map.
- The trace output prints the cookie, not the stack, including in
  ftrace_dump_on_oops. Printing the stack from the map when the trace is
  read could be added later, since the map is kept after the option is
  turned off.
- Elements have a fixed size, so an insert only takes one atomic index
  increment; a variable-size pool would need an allocator usable from
  NMI.

Changes since v7
================

- Record a u64 cookie (generation, slot); the trace prints
  "<stack_id N gen G>" and stack_map records print the generation.
- Drop rcu_tasks_rude: a stack recorded while RCU is not watching is
  discarded, and reset and free only use synchronize_rcu() (Steven).
- Use a mutex instead of an rwsem for the readers (Steven).
- Move the hot path into record_stackmap() and the tracefs setup into a
  helper, with stubs instead of #ifdefs; name the init state enum (Steven).
- Trim the comments and changelogs (Steven).
- Capitalize the subjects (Steven), and use the "tracing:" prefix.
- Reset is "echo 0 > stack_map" only, and stack_map uses the " => "
  frame format of <stack trace>.
- stack_map_stat has one field per line, adds generation and capacity,
  drops table_size and success_rate, and renames drops to fallbacks,
  since those stacks are recorded in full, not lost.
- The map is allocated when the option is enabled at runtime; with
  trace_options=stackmap it is allocated during tracefs initialization.
  It stays allocated when the option is disabled, until "free" is written
  to stack_map.
- The map holds at most one copy of a stack per generation. If another
  context is inserting the same stack, that stack is recorded in full
  instead of waiting.
- Binary export, parser and capacity boot parameter split out, see above.
- RFC dropped.

v7: https://lore.kernel.org/linux-trace-kernel/20260912083753.3426176-1-lipengfei28@xiaomi.com/

Known limitations
=================

- Top level trace array only.
- Fixed capacity of 16384 stacks, about 8.6 MiB on 64-bit while allocated.
- Kernel stacks only.

Testing
=======

- Each patch builds on x86_64, and on arm32 with and without
  CONFIG_FTRACE_STACKMAP.
- QEMU arm64, with and without KASAN and lockdep: the selftest in patch
  5, boot with trace_options=stackmap,stacktrace, and a 60 s stress run
  of tracing with resets, stack_map and stack_map_stat readers, and free
  with and without an open reader. No warnings.
- Function tracer with func_stack_trace: every cookie in the trace
  resolves against stack_map. Filling all 16384 elements: fallbacks
  grow, the remaining stacks are recorded in full, every cookie still
  resolves, and a reset empties the map.

Based on 4539944e5151 ("Merge tag 'liveupdate-fixes-2026-07-22' ...").

Pengfei Li (5):
  tracing: Add lock-free stackmap for stack trace deduplication
  tracing: Use the stackmap from the ftrace stack recording path
  tracing: Add stackmap statistics interface
  Documentation: tracing: Document the ftrace stackmap
  selftests/ftrace: Add a stackmap basic functionality test

 Documentation/trace/ftrace-stackmap.rst       | 192 +++++++
 Documentation/trace/ftrace.rst                |   6 +
 Documentation/trace/index.rst                 |   1 +
 kernel/trace/Kconfig                          |  13 +
 kernel/trace/Makefile                         |   1 +
 kernel/trace/trace.c                          | 132 ++++-
 kernel/trace/trace.h                          |  15 +
 kernel/trace/trace_entries.h                  |  16 +
 kernel/trace/trace_functions_graph.c          |   1 +
 kernel/trace/trace_output.c                   |  24 +
 kernel/trace/trace_selftest.c                 |   1 +
 kernel/trace/trace_stackmap.c                 | 495 ++++++++++++++++++
 kernel/trace/trace_stackmap.h                 |  23 +
 .../ftrace/test.d/ftrace/stackmap-basic.tc    | 222 ++++++++
 14 files changed, 1139 insertions(+), 3 deletions(-)
 create mode 100644 Documentation/trace/ftrace-stackmap.rst
 create mode 100644 kernel/trace/trace_stackmap.c
 create mode 100644 kernel/trace/trace_stackmap.h
 create mode 100644 tools/testing/selftests/ftrace/test.d/ftrace/stackmap-basic.tc


base-commit: 4539944e515183668109bdf4d0c3d7d228383d88
-- 
2.34.1