[PATCH v8 4/5] Documentation: tracing: Document the ftrace stackmap

[Li Pengfei <ljdlns1987@gmail.com>]

From: Pengfei Li <lipengfei28@xiaomi.com>

Describe how to use the stackmap, how reset and free behave, and how to
resolve a trace that spans resets. List the option in ftrace.rst.

Assisted-by: LLM
Signed-off-by: Pengfei Li <lipengfei28@xiaomi.com>
---
 Documentation/trace/ftrace-stackmap.rst | 192 ++++++++++++++++++++++++
 Documentation/trace/ftrace.rst          |   6 +
 Documentation/trace/index.rst           |   1 +
 3 files changed, 199 insertions(+)
 create mode 100644 Documentation/trace/ftrace-stackmap.rst

diff --git a/Documentation/trace/ftrace-stackmap.rst b/Documentation/trace/ftrace-stackmap.rst
new file mode 100644
index 000000000000..58af7c564b10
--- /dev/null
+++ b/Documentation/trace/ftrace-stackmap.rst
@@ -0,0 +1,192 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+======================
+Ftrace Stack Map
+======================
+
+:Author: Pengfei Li <lipengfei28@xiaomi.com>
+
+Overview
+========
+
+The ftrace stack map provides stack trace deduplication for the ftrace
+ring buffer. When enabled, instead of a full kernel stack trace event
+(typically 80-160 bytes) for each stack the map can store, ftrace writes a
+fixed-size event of 20-24 bytes, depending on the architecture, that holds
+a 64-bit cookie: the map generation in the high 32 bits and the slot index
+in the low 32. The full stacks are kept once in a separate hash table and
+exported via tracefs for userspace to resolve.
+
+It is similar to eBPF's ``BPF_MAP_TYPE_STACK_TRACE``.
+
+Configuration
+=============
+
+Enable ``CONFIG_FTRACE_STACKMAP=y`` in the kernel config.
+
+The map holds up to 16384 distinct stacks. It is allocated when the
+``stackmap`` option is first enabled; if the allocation fails, enabling
+the option fails with ``-ENOMEM``. The map stays allocated while the
+option is turned off, so a trace can still be resolved, until ``free``
+is written to ``stack_map``. On a 64-bit kernel the map takes about
+8.6 MiB.
+
+Usage
+=====
+
+Enable stack deduplication for event stacks::
+
+    echo 1 > /sys/kernel/tracing/options/stackmap
+    echo 1 > /sys/kernel/tracing/options/stacktrace
+    echo 1 > /sys/kernel/tracing/events/sched/sched_switch/enable
+
+The function tracer records stacks through its own option instead of
+``stacktrace``::
+
+    echo vfs_read > /sys/kernel/tracing/set_ftrace_filter
+    echo function > /sys/kernel/tracing/current_tracer
+    echo 1 > /sys/kernel/tracing/options/func_stack_trace
+
+The trace output will show ``<stack_id N gen G>`` instead of full stack
+traces, where N is the slot and G the map generation::
+
+    sh-1234 [006] d.h.. 123.456789: <stack_id 42 gen 1>
+
+Stacks are not always replaced. A stack deeper than 64 frames, a stack
+recorded before the map is allocated or during a reset, a stack that
+another context is inserting at the same moment, and a stack the map
+cannot store (element pool exhausted, probe limit, or ring buffer
+reservation failure) are recorded in full. A trace can therefore contain
+both ``<stack_id N gen G>`` records and full ``<stack trace>`` records.
+With the option enabled, a stack recorded where RCU is not watching is
+discarded.
+
+To view the actual stacks::
+
+    cat /sys/kernel/tracing/stack_map
+
+Output format::
+
+    stack_id 42 gen 1 ref 1337 depth 8
+     => schedule+0x48/0xc0
+     => schedule_timeout+0x1c/0x30
+     ...
+
+``ref`` is the number of times the stack was recorded as a cookie since
+the last reset. It is not decremented when events leave the ring buffer,
+and it saturates at ``INT_MAX``.
+
+To view statistics::
+
+    cat /sys/kernel/tracing/stack_map_stat
+
+Output::
+
+    generation: 1
+    entries: 2500
+    capacity: 16384
+    successes: 148923
+    fallbacks: 0
+
+``entries`` is the number of map elements reserved since the last reset;
+an insertion in progress can make it briefly exceed the number of records
+in ``stack_map``. ``successes`` is the number of stacks recorded as a
+cookie. ``fallbacks`` is the number of stacks the map could not store
+because the element pool was exhausted or the probe limit was reached;
+those are recorded in full instead. The other cases above are not
+counted. A growing
+``fallbacks`` count means the map is too small or too crowded; a reset
+makes room again. The file is empty while no map is allocated.
+
+To reset the stack map::
+
+    echo 0 > /sys/kernel/tracing/stack_map
+
+To release the map once the option is off::
+
+    echo 0 > /sys/kernel/tracing/options/stackmap
+    echo free > /sys/kernel/tracing/stack_map
+
+``free`` fails with ``-EBUSY`` while the option is enabled. A ``stack_map``
+file opened for reading before ``free`` keeps the old map. ``free`` blocks
+until all such files are closed, then releases the memory, so a process
+that has one open must close it first. If ``free`` is written through a
+file that is also open for reading, that file is not waited for: ``free``
+returns and the memory is released when that file is closed. If the writer
+is killed while it waits, the map has already been removed, and its memory
+is released when the last such file is closed.
+
+Reset clears the map without touching the trace buffer, and tracing does
+not have to be stopped. Reset and ``free`` both leave cookies in the trace
+buffer; the generation changes, so those cookies no longer match the map.
+A cookie only resolves against ``stack_map`` records of the same
+generation. The generation in a cookie is 32 bits. It only has to tell
+resets apart, and wraps after 2^32 resets and frees.
+
+To resolve a trace that spans resets, save ``stack_map`` before each
+reset. ``stack_map`` is not a snapshot of concurrent insertions: a read
+can include stacks inserted while it is in progress and can miss stacks
+inserted into slots it has already passed. A reader that spans a reset
+can get records of two generations across separate ``read()`` calls; the
+``gen`` field shows this. Stop tracing across the copy and the reset if
+every record must resolve.
+
+Boot-time activation
+====================
+
+The stackmap option can be enabled from the kernel command line::
+
+    trace_options=stackmap,stacktrace
+
+The map is then allocated when tracefs initializes. Stacks recorded before
+that are recorded in full. If the allocation fails, the option is turned
+off and a warning is printed.
+
+The stack_map files
+===================
+
+``stack_map`` (mode 0640) and ``stack_map_stat`` (mode 0440) exist when
+``CONFIG_FTRACE_STACKMAP`` is enabled, also before the map is allocated.
+While no map is allocated, both are empty. Writing ``0`` to ``stack_map``
+resets the map; writing ``free`` releases it.
+
+Design
+======
+
+The stack map is modeled after ``tracing_map.c`` (used by hist triggers):
+
+- **Lookup/Insert**: Lock-free via ``cmpxchg``, safe in NMI and IRQ context
+  where RCU is watching
+- **Memory**: Pre-allocated element pool, no allocation on the hot path
+- **Collision**: Linear probing with a 2x over-provisioned table; probe
+  length is bounded so worst-case insert/lookup is O(1)
+- **Scope**: Top level trace array only
+- **Hash**: 32-bit jhash with a per-map random seed; full ``memcmp``
+  confirms matches
+
+The map holds at most one copy of a stack per generation. When a lookup
+reaches a slot with the same hash whose element is not yet published,
+another context is inserting that stack, or another stack with the same
+hash. The lookup does not wait, because in NMI context it may have
+interrupted that insert, and it does not add a second copy; that one stack
+is recorded in full instead. A context that loses the ``cmpxchg`` for a
+free slot re-reads the slot for the same reason.
+
+Differences from ``tracing_map``
+--------------------------------
+
+The table, the element pool and the probing follow ``tracing_map``. The
+stack map differs where its callers differ:
+
+- ``tracing_map_clear()`` requires its caller to keep inserts out. The
+  stack map does this itself: new callers are kept out and admitted ones
+  are drained with RCU before the map is cleared, so a reset can be
+  written to ``stack_map`` while tracing is active.
+- An insert that meets an unpublished element of the same hash records
+  the stack in full, which loses nothing. ``tracing_map`` spins instead,
+  since a lost insert there is a lost histogram update.
+- Probing stops after 64 slots, so a slot claimed without an element can
+  stay claimed. ``tracing_map`` has no probe limit and releases such a
+  slot, so that its loop always reaches a free slot.
+- The cookie is the slot index, so it stays valid while the map is not
+  reset; ``tracing_map`` hands out element pointers.
diff --git a/Documentation/trace/ftrace.rst b/Documentation/trace/ftrace.rst
index 84f06bf0da9b..f90cf7575458 100644
--- a/Documentation/trace/ftrace.rst
+++ b/Documentation/trace/ftrace.rst
@@ -1396,6 +1396,12 @@ Here are the available options:
 	When set, a stack trace is recorded after any trace event
 	is recorded.
 
+  stackmap
+	When set, a recorded stack trace is replaced by a cookie that
+	refers to a single copy of the stack in the stack_map file.
+	Only for the top level trace array. See
+	Documentation/trace/ftrace-stackmap.rst.
+
   branch
 	Enable branch tracing with the tracer. This enables branch
 	tracer along with the currently set tracer. Enabling this
diff --git a/Documentation/trace/index.rst b/Documentation/trace/index.rst
index 5d9bf4694d5d..ac8b1141c23a 100644
--- a/Documentation/trace/index.rst
+++ b/Documentation/trace/index.rst
@@ -33,6 +33,7 @@ the Linux kernel.
    ftrace
    ftrace-design
    ftrace-uses
+   ftrace-stackmap
    kprobes
    kprobetrace
    fprobetrace
-- 
2.34.1