kasan, arm64, scs, stacktrace: collect stack traces from Shadow Call Stack

From: Andrey Konovalov <[email protected]>

Add a new interface stack_trace_save_shadow() for collecting stack traces by copying frames from the Shadow Call Stack.

Collecting stack traces this way is significantly faster: boot time of a defconfig build with KASAN enabled gets descreased by ~30%.

The few patches following this one add an implementation of stack_trace_save_shadow() for arm64.

The implementation of the added interface is not meant to use stack_trace_consume_fn to avoid making a function call for each collected frame to further improve performance.

...

include/linux/stacktrace.h +1 -0

@@ -108,4 +111,16 @@ static inline int stack_trace_save_tsk_reliable(struct task_struct *tsk,
 }
 #endif
 
+#if defined(CONFIG_STACKTRACE) && defined(CONFIG_HAVE_SHADOW_STACKTRACE)

Quoted 21 lines · On Wed, 23 Mar 2022 16:32:52 +0100 [email protected] wrote:

From: Andrey Konovalov <[email protected]>

Add a new interface stack_trace_save_shadow() for collecting stack traces by copying frames from the Shadow Call Stack.

Collecting stack traces this way is significantly faster: boot time of a defconfig build with KASAN enabled gets descreased by ~30%.

The few patches following this one add an implementation of stack_trace_save_shadow() for arm64.

The implementation of the added interface is not meant to use stack_trace_consume_fn to avoid making a function call for each collected frame to further improve performance.

...

(quoted diff) +0 -0

@@ -108,4 +111,16 @@ static inline int stack_trace_save_tsk_reliable(struct task_struct *tsk,
 }
 #endif
 

include/linux/stacktrace.h static inline int stack_trace_save_tsk_reliable(struct task_struct *tsk, · line 124

Quoted 11 lines

include/linux/stacktrace.h +11 -0

+#if defined(CONFIG_STACKTRACE) && defined(CONFIG_HAVE_SHADOW_STACKTRACE)
+int stack_trace_save_shadow(unsigned long *store, unsigned int size,
+                         unsigned int skipnr);
+#else
+static inline int stack_trace_save_shadow(unsigned long *store,
+                                       unsigned int size,
+                                       unsigned int skipnr)
+{
+     return -ENOSYS;
+}
+#endif

checkpatch sayeth "WARNING: ENOSYS means 'invalid syscall nr' and nothing else".

checkpatch also picked up a typo in a changelog. Useful thing to run, is checkpatch.

From: Andrey Konovalov <[email protected]>

Add a new interface stack_trace_save_shadow() for collecting stack traces by copying frames from the Shadow Call Stack.

Collecting stack traces this way is significantly faster: boot time of a defconfig build with KASAN enabled gets descreased by ~30%.

The few patches following this one add an implementation of stack_trace_save_shadow() for arm64.

The implementation of the added interface is not meant to use stack_trace_consume_fn to avoid making a function call for each collected frame to further improve performance.

Signed-off-by Andrey Konovalov <[email protected]>

---
 arch/Kconfig               |  6 ++++++
 include/linux/stacktrace.h | 15 +++++++++++++++
 kernel/stacktrace.c        | 21 +++++++++++++++++++++
 3 files changed, 42 insertions(+)

arch/Kconfig +6 -0

index e12a4268c01d..207c1679c53a 100644
@@ -1041,6 +1041,12 @@ config HAVE_RELIABLE_STACKTRACE
 	  arch_stack_walk_reliable() function which only returns a stack trace
 	  if it can guarantee the trace is reliable.
 
+config HAVE_SHADOW_STACKTRACE
+	bool
+	help
+	  If this is set, the architecture provides the arch_stack_walk_shadow()
+	  function, which collects the stack trace from the shadow call stack.
+
 config HAVE_ARCH_HASH
 	bool
 	default n

include/linux/stacktrace.h +15 -0

index 97455880ac41..b74d1e42e157 100644
@@ -60,6 +60,9 @@ int arch_stack_walk_reliable(stack_trace_consume_fn consume_entry, void *cookie,
 
 void arch_stack_walk_user(stack_trace_consume_fn consume_entry, void *cookie,
 			  const struct pt_regs *regs);
+
+int arch_stack_walk_shadow(unsigned long *store, unsigned int size,
+			   unsigned int skipnr);
 #endif /* CONFIG_ARCH_STACKWALK */
 
 #ifdef CONFIG_STACKTRACE

@@ -108,4 +111,16 @@ static inline int stack_trace_save_tsk_reliable(struct task_struct *tsk,
 }
 #endif
 
+#if defined(CONFIG_STACKTRACE) && defined(CONFIG_HAVE_SHADOW_STACKTRACE)
+int stack_trace_save_shadow(unsigned long *store, unsigned int size,
+			    unsigned int skipnr);
+#else
+static inline int stack_trace_save_shadow(unsigned long *store,
+					  unsigned int size,
+					  unsigned int skipnr)
+{
+	return -ENOSYS;
+}
+#endif
+
 #endif /* __LINUX_STACKTRACE_H */

kernel/stacktrace.c +10 -0

index 9ed5ce989415..fe305861fd55 100644
@@ -237,6 +237,27 @@ unsigned int stack_trace_save_user(unsigned long *store, unsigned int size)
 }
 #endif
 
+#ifdef CONFIG_HAVE_SHADOW_STACKTRACE
+/**
+ * stack_trace_save_shadow - Save a stack trace based on shadow call stack
+ * @store:	Pointer to the storage array
+ * @size:	Size of the storage array
+ * @skipnr:	Number of entries to skip at the start of the stack trace
+ *
+ * Return: Number of trace entries stored.
+ */
+int stack_trace_save_shadow(unsigned long *store, unsigned int size,

kernel/stacktrace.c +1 -0

+
 #else /* CONFIG_ARCH_STACKWALK */
 
 /*

Signature · 1 line

2.25.1

Quoted 3 lines

Collecting stack traces this way is significantly faster: boot time of a defconfig build with KASAN enabled gets descreased by ~30%.

Hmm... just to check, do ou know if that's just because of hte linear copy, or because we're skipping other work we have to do in the regular stacktrace?

Quoted 3 lines

The implementation of the added interface is not meant to use stack_trace_consume_fn to avoid making a function call for each collected frame to further improve performance.

... because we could easily provide an inline-optimized stack copy *without* having to write a distinct unwinder, and I'd *really* like to avoid having a bunch of distinct unwinders for arm64, as it really hinders maintenance. We're working on fixing/improving the arm64 unwinder for things like RELIABLE_STACKTRACE, and I know that some of that work is non-trivial to make work with an SCS-based unwind rather than an FP-based unwind, and/or will undermine the saving anyway.

Quoted 8 lines

kernel/stacktrace.c +8 -0

+int stack_trace_save_shadow(unsigned long *store, unsigned int size,
+                         unsigned int skipnr)
+{
+     /*
+      * Do not use stack_trace_consume_fn to avoid making a function
+      * call for each collected frame to improve performance.
+      * Skip + 1 frame to skip stack_trace_save_shadow.
+      */

kernel/stacktrace.c unsigned int stack_trace_save_user(unsigned long *store, unsigned int size) · line 259

Quoted 3 lines

kernel/stacktrace.c +3 -0

+     return arch_stack_walk_shadow(store, size, skipnr + 1);
+}
+#endif

If we really need this, can we make it an __always_inline in a header so that we can avoid the skip? Generally the skipping is problematic due to inlining/outlining and LTO, and I'd like to avoid adding more of it unnecessarily.

From: Andrey Konovalov <[email protected]>

When an interrupt happens, the current Shadow Call Stack (SCS) pointer is switched to a per-interrupt one stored in a per-CPU variable. The old pointer is then saved on the normal stack and restored when the interrupt is handled.

To collect the current stack trace based on SCS when the interrupt is being handled, we need to know the SCS pointers that belonged to the task and potentially other interrupts that were interrupted.

Instead of trying to retrieve the SCS pointers from the stack, change interrupt handlers (for hard IRQ, Normal and Critical SDEI) to save the previous SCS pointer in a per-CPU variable.

Note that interrupts stack. A task can be interrupted by a hard IRQ, which then can interrupted by a normal SDEI, etc. This is handled by using a separate per-CPU variable for each interrupt type.

Also reset the saved SCS pointer when exiting the interrupt. This allows checking whether we should include any interrupt frames when collecting the stack trace. While we could use in_hardirq(), there seems to be no easy way to check whether we are in an SDEI handler. Directly checking the per-CPU variables for being non-zero is more resilient.

Also expose both the the added saved SCS variables and the existing SCS base variables in arch/arm64/include/asm/scs.h so that the stack trace collection impementation can use them.

Signed-off-by Andrey Konovalov <[email protected]>

---
 arch/arm64/include/asm/assembler.h | 12 ++++++++++++
 arch/arm64/include/asm/scs.h       | 13 ++++++++++++-
 arch/arm64/kernel/entry.S          | 28 ++++++++++++++++++++++++----
 arch/arm64/kernel/irq.c            |  4 +---
 arch/arm64/kernel/sdei.c           |  5 ++---
 5 files changed, 51 insertions(+), 11 deletions(-)

arch/arm64/include/asm/assembler.h +12 -0

index 8c5a61aeaf8e..ca018e981d13 100644
@@ -270,6 +270,18 @@ alternative_endif
 	ldr	\dst, [\dst, \tmp]
 	.endm
 
+	/*
+	 * @src: Register whose value gets stored in sym
+	 * @sym: The name of the per-cpu variable
+	 * @tmp0: Scratch register
+	 * @tmp1: Another scratch register
+	 */
+	.macro str_this_cpu src, sym, tmp0, tmp1
+	adr_l	\tmp0, \sym
+	get_this_cpu_offset \tmp1
+	str	\src, [\tmp0, \tmp1]
+	.endm
+
 /*
  * vma_vm_mm - get mm pointer from vma pointer (vma->vm_mm)
  */

arch/arm64/include/asm/scs.h +12 -1

index 8297bccf0784..2bb2b32f787b 100644
@@ -24,6 +24,17 @@
 	.endm
 #endif /* CONFIG_SHADOW_CALL_STACK */
 
-#endif /* __ASSEMBLY __ */
+#else /* __ASSEMBLY__ */
+
+#include <linux/percpu.h>
+
+DECLARE_PER_CPU(unsigned long *, irq_shadow_call_stack_ptr);
+DECLARE_PER_CPU(unsigned long *, irq_shadow_call_stack_saved_ptr);
+DECLARE_PER_CPU(unsigned long *, sdei_shadow_call_stack_normal_ptr);
+DECLARE_PER_CPU(unsigned long *, sdei_shadow_call_stack_normal_saved_ptr);
+DECLARE_PER_CPU(unsigned long *, sdei_shadow_call_stack_critical_ptr);
+DECLARE_PER_CPU(unsigned long *, sdei_shadow_call_stack_critical_saved_ptr);
+
+#endif /* __ASSEMBLY__ */
 
 #endif /* _ASM_SCS_H */

arch/arm64/kernel/entry.S +24 -4

index ede028dee81b..1c62fecda172 100644
@@ -880,7 +880,8 @@ NOKPROBE(ret_from_fork)
  */
 SYM_FUNC_START(call_on_irq_stack)
 #ifdef CONFIG_SHADOW_CALL_STACK
-	stp	scs_sp, xzr, [sp, #-16]!
+	/* Save the current SCS pointer and load the per-IRQ one. */
+	str_this_cpu scs_sp, irq_shadow_call_stack_saved_ptr, x15, x17
 	ldr_this_cpu scs_sp, irq_shadow_call_stack_ptr, x17
 #endif
 	/* Create a frame record to save our LR and SP (implicit in FP) */

@@ -902,7 +903,9 @@ SYM_FUNC_START(call_on_irq_stack)
 	mov	sp, x29
 	ldp	x29, x30, [sp], #16
 #ifdef CONFIG_SHADOW_CALL_STACK
-	ldp	scs_sp, xzr, [sp], #16
+	/* Restore saved SCS pointer and reset the saved value. */
+	ldr_this_cpu scs_sp, irq_shadow_call_stack_saved_ptr, x17
+	str_this_cpu xzr, irq_shadow_call_stack_saved_ptr, x15, x17
 #endif
 	ret
 SYM_FUNC_END(call_on_irq_stack)

@@ -1024,11 +1027,16 @@ SYM_CODE_START(__sdei_asm_handler)
 #endif
 
 #ifdef CONFIG_SHADOW_CALL_STACK
-	/* Use a separate shadow call stack for normal and critical events */
+	/*
+	 * Use a separate shadow call stack for normal and critical events.
+	 * Save the current SCS pointer and load the per-SDEI one.
+	 */
 	cbnz	w4, 3f
+	str_this_cpu src=scs_sp, sym=sdei_shadow_call_stack_normal_saved_ptr, tmp0=x5, tmp1=x6
 	ldr_this_cpu dst=scs_sp, sym=sdei_shadow_call_stack_normal_ptr, tmp=x6
 	b	4f
-3:	ldr_this_cpu dst=scs_sp, sym=sdei_shadow_call_stack_critical_ptr, tmp=x6
+3:	str_this_cpu src=scs_sp, sym=sdei_shadow_call_stack_critical_saved_ptr, tmp0=x5, tmp1=x6
+	ldr_this_cpu dst=scs_sp, sym=sdei_shadow_call_stack_critical_ptr, tmp=x6
 4:
 #endif
 

@@ -1062,6 +1070,18 @@ SYM_CODE_START(__sdei_asm_handler)
 	ldp	lr, x1, [x4, #SDEI_EVENT_INTREGS + S_LR]
 	mov	sp, x1
 
+#ifdef CONFIG_SHADOW_CALL_STACK
+	/* Restore saved SCS pointer and reset the saved value. */
+	ldrb	w5, [x4, #SDEI_EVENT_PRIORITY]
+	cbnz	w5, 5f
+	ldr_this_cpu dst=scs_sp, sym=sdei_shadow_call_stack_normal_saved_ptr, tmp=x6
+	str_this_cpu src=xzr, sym=sdei_shadow_call_stack_normal_saved_ptr, tmp0=x5, tmp1=x6
+	b	6f
+5:	ldr_this_cpu dst=scs_sp, sym=sdei_shadow_call_stack_critical_saved_ptr, tmp=x6
+	str_this_cpu src=xzr, sym=sdei_shadow_call_stack_critical_saved_ptr, tmp0=x5, tmp1=x6
+6:
+#endif
+
 	mov	x1, x0			// address to complete_and_resume
 	/* x0 = (x0 <= SDEI_EV_FAILED) ?
 	 * EVENT_COMPLETE:EVENT_COMPLETE_AND_RESUME

arch/arm64/kernel/irq.c +1 -3

index bda49430c9ea..4199f900714a 100644
@@ -28,11 +28,9 @@ DEFINE_PER_CPU(struct nmi_ctx, nmi_contexts);
 
 DEFINE_PER_CPU(unsigned long *, irq_stack_ptr);
 
-
-DECLARE_PER_CPU(unsigned long *, irq_shadow_call_stack_ptr);
-
 #ifdef CONFIG_SHADOW_CALL_STACK
 DEFINE_PER_CPU(unsigned long *, irq_shadow_call_stack_ptr);
+DEFINE_PER_CPU(unsigned long *, irq_shadow_call_stack_saved_ptr);
 #endif
 
 static void init_irq_scs(void)

arch/arm64/kernel/sdei.c +2 -3

index d20620a1c51a..269adcb9e854 100644
@@ -39,12 +39,11 @@ DEFINE_PER_CPU(unsigned long *, sdei_stack_normal_ptr);
 DEFINE_PER_CPU(unsigned long *, sdei_stack_critical_ptr);
 #endif
 
-DECLARE_PER_CPU(unsigned long *, sdei_shadow_call_stack_normal_ptr);
-DECLARE_PER_CPU(unsigned long *, sdei_shadow_call_stack_critical_ptr);
-
 #ifdef CONFIG_SHADOW_CALL_STACK
 DEFINE_PER_CPU(unsigned long *, sdei_shadow_call_stack_normal_ptr);
+DEFINE_PER_CPU(unsigned long *, sdei_shadow_call_stack_normal_saved_ptr);
 DEFINE_PER_CPU(unsigned long *, sdei_shadow_call_stack_critical_ptr);
+DEFINE_PER_CPU(unsigned long *, sdei_shadow_call_stack_critical_saved_ptr);
 #endif
 
 static void _free_sdei_stack(unsigned long * __percpu *ptr, int cpu)

Signature · 1 line

2.25.1

Quoted 2 lines · On Wed, Mar 23, 2022 at 04:32:53PM +0100, [email protected] wrote:

From: Andrey Konovalov <[email protected]>

Quoted 3 lines

Instead of trying to retrieve the SCS pointers from the stack, change interrupt handlers (for hard IRQ, Normal and Critical SDEI) to save the previous SCS pointer in a per-CPU variable.

I'm *really* not keen on *always* poking this in the entry code for the uncommon case of unwind. It complicates the entry code and means we're always paying a cost for potentially no benefit. At a high-level, I don't think this is the right approach.

For the regular unwinder, I want to rework things such that we can identify exception boundaries and look into the regs (e.g. so that we can recover the PC+LR+FP and avoid duplicating part of this in a frame record), and I'd much prefer that we did the same here.

From: Andrey Konovalov <[email protected]>

Implement the stack_trace_save_shadow() interface that collects stack traces based on the Shadow Call Stack (SCS) for arm64.

The implementation walks through available SCS pointers (the per-task one and the per-interrupt-type ones) and copies the frames.

Note that the frame of the interrupted function is not included into the stack trace, as it is not yet saved on the SCS when an interrupt happens.

Signed-off-by Andrey Konovalov <[email protected]>

---
 arch/arm64/Kconfig             |  1 +
 arch/arm64/kernel/stacktrace.c | 83 ++++++++++++++++++++++++++++++++++
 2 files changed, 84 insertions(+)

arch/arm64/Kconfig +1 -0

index a659e238f196..d89cecf6c923 100644
@@ -201,6 +201,7 @@ config ARM64
 	select MMU_GATHER_RCU_TABLE_FREE
 	select HAVE_RSEQ
 	select HAVE_RUST
+	select HAVE_SHADOW_STACKTRACE
 	select HAVE_STACKPROTECTOR
 	select HAVE_SYSCALL_TRACEPOINTS
 	select HAVE_KPROBES

arch/arm64/kernel/stacktrace.c +37 -0

index e4103e085681..89daa710d91b 100644
@@ -12,9 +12,11 @@
 #include <linux/sched/debug.h>
 #include <linux/sched/task_stack.h>
 #include <linux/stacktrace.h>
+#include <linux/scs.h>
 
 #include <asm/irq.h>
 #include <asm/pointer_auth.h>
+#include <asm/scs.h>
 #include <asm/stack_pointer.h>
 #include <asm/stacktrace.h>
 

@@ -210,3 +212,84 @@ noinline notrace void arch_stack_walk(stack_trace_consume_fn consume_entry,
 
 	walk_stackframe(task, &frame, consume_entry, cookie);
 }
+
+static const struct {
+	unsigned long ** __percpu saved;
+	unsigned long ** __percpu base;
+} scs_parts[] = {
+#ifdef CONFIG_ARM_SDE_INTERFACE
+	{
+		.saved = &sdei_shadow_call_stack_critical_saved_ptr,
+		.base = &sdei_shadow_call_stack_critical_ptr,
+	},
+	{
+		.saved = &sdei_shadow_call_stack_normal_saved_ptr,
+		.base = &sdei_shadow_call_stack_normal_ptr,
+	},
+#endif /* CONFIG_ARM_SDE_INTERFACE */
+	{
+		.saved = &irq_shadow_call_stack_saved_ptr,
+		.base = &irq_shadow_call_stack_ptr,
+	},
+};
+
+static inline bool walk_shadow_stack_part(
+				unsigned long *scs_top, unsigned long *scs_base,
+				unsigned long *store, unsigned int size,
+				unsigned int *skipnr, unsigned int *len)
+{
+	unsigned long *frame;
+
+	for (frame = scs_top; frame >= scs_base; frame--) {
+		if (*skipnr > 0) {
+			(*skipnr)--;
+			continue;
+		}
+		/*
+		 * Do not leak PTR_AUTH tags in stack traces.

arch/arm64/kernel/stacktrace.c +5 -0

+
+	/* The top SCS slot is empty. */
+	scs_top -= 1;
+
+	/* Handle SDEI and hardirq frames. */

arch/arm64/kernel/stacktrace.c +9 -0

+
+	/* Handle task and softirq frames. */
+	scs_base = task_scs(current);
+	walk_shadow_stack_part(scs_top, scs_base, store, size, &skipnr, &len);
+
+out:
+	preempt_enable();
+	return len;
+}

Signature · 1 line

2.25.1

This doesn't do any of the trampoline repatinting (e.g. for kretprobes or ftrace graph caller) that the regular unwinder does, so if either of those are in use this is going to produce bogus results.

arch/arm64/kernel/stacktrace.c noinline notrace void arch_stack_walk(stack_trace_consume_fn consume_entry, · line 268

Quoted 8 lines

arch/arm64/kernel/stacktrace.c +8 -0

+noinline notrace int arch_stack_walk_shadow(unsigned long *store,
+                                         unsigned int size,
+                                         unsigned int skipnr)
+{
+     unsigned long *scs_top, *scs_base, *scs_next;
+     unsigned int len = 0, part;
+
+     preempt_disable();

This doesn't look necessary; it's certinaly not needed for the regular unwinder.

Critically, in the common case of unwinding just the task stack, we don't need to look at any of the per-cpu stacks, and so there's no need to disable preemption. See the stack nesting logic in the regular unwinder.

If we *do* need to unwind per-cpu stacks, we figure that out and verify our countext *at* the transition point.

arch/arm64/kernel/stacktrace.c noinline notrace void arch_stack_walk(stack_trace_consume_fn consume_entry, · line 271

Quoted 3 lines

arch/arm64/kernel/stacktrace.c +3 -0

+
+     /* Get the SCS pointer. */
+     asm volatile("mov %0, x18" : "=&r" (scs_top));

Does the compiler guarantee where this happens relative to any prologue manipulation of x18?

This seems like something we should be using a compilar intrinsic for, or have a wrapper that passes this in if necessary.

Quoted 11 lines

arch/arm64/kernel/stacktrace.c +11 -0

+
+     /* The top SCS slot is empty. */
+     scs_top -= 1;
+
+     /* Handle SDEI and hardirq frames. */
+     for (part = 0; part < ARRAY_SIZE(scs_parts); part++) {
+             scs_next = *this_cpu_ptr(scs_parts[part].saved);
+             if (scs_next) {
+                     scs_base = *this_cpu_ptr(scs_parts[part].base);
+                     if (walk_shadow_stack_part(scs_top, scs_base, store,
+                                                size, &skipnr, &len))

arch/arm64/kernel/stacktrace.c noinline notrace void arch_stack_walk(stack_trace_consume_fn consume_entry, · line 286

Quoted 4 lines

arch/arm64/kernel/stacktrace.c +4 -0

+                             goto out;
+                     scs_top = scs_next;
+             }
+     }

We have a number of portential stack nesting orders (and may need to introduce more stacks in future), so I think we need to be more careful with this. The regular unwinder handles that dynamically.

From: Andrey Konovalov <[email protected]>

Now that stack_trace_save_shadow() is implemented by arm64, use it whenever CONFIG_HAVE_SHADOW_STACKTRACE is enabled. This improves the boot time of a defconfig build by ~30% for all KASAN modes.

Signed-off-by Andrey Konovalov <[email protected]>

---
 mm/kasan/common.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

mm/kasan/common.c +0 -0

index d9079ec11f31..8d9d35c6562b 100644

mm/kasan/common.c +4 -1

+               size = stack_trace_save_shadow(entries, ARRAY_SIZE(entries), 0);
+       else
+               size = stack_trace_save(entries, ARRAY_SIZE(entries), 0);
+       return __stack_depot_save(entries, size, flags, can_alloc);
 }
 
 void kasan_set_track(struct kasan_track *track, gfp_t flags)
--

2.25.1

mm/kasan/common.c line 36

Quoted 11 lines

mm/kasan/common.c +1 -1

index d9079ec11f31..8d9d35c6562b 100644
@@ -33,10 +33,13 @@
 depot_stack_handle_t kasan_save_stack(gfp_t flags, bool can_alloc)
 {
        unsigned long entries[KASAN_STACK_DEPTH];
-       unsigned int nr_entries;
+       unsigned int size;

Why did this variable name change?

mm/kasan/common.c line 38

Quoted 3 lines

mm/kasan/common.c +1 -2

-       nr_entries = stack_trace_save(entries, ARRAY_SIZE(entries), 0);
-       return __stack_depot_save(entries, nr_entries, flags, can_alloc);
+       if (IS_ENABLED(CONFIG_HAVE_SHADOW_STACKTRACE))

Would it be more reliable to check the return-code? I.e. do:

int size;

  size = stack_trace_save_shadow(...)
  if (size < 0)
    size = stack_trace_save(...);

From: Andrey Konovalov <[email protected]>

kasan, arm64, scs, stacktrace: collect stack traces from Shadow Call Stack

Currently, KASAN always uses the normal stack trace collection routines, which rely on the unwinder, when saving alloc and free stack traces.

Instead of invoking the unwinder, collect the stack trace by copying frames from the Shadow Call Stack whenever it is enabled. This reduces boot time by 30% for all KASAN modes when Shadow Call Stack is enabled.

Stack staces are collected from the Shadow Call Stack via a new stack_trace_save_shadow() interface.

Note that the frame of the interrupted function is not included into the stack trace, as it is not yet saved on the SCS when an interrupt happens.

---

To deal with this last thing, we could save the interrupted frame address in another per-CPU variable. I'll look into implementing this for v3.

I decided to postpone the changes to stack depot that avoid copying frames twice until a planned upcoming update for stack depot.

Changes v1->v2:
- Provide a kernel-wide stack_trace_save_shadow() interface for collecting stack traces from shadow stack.
- Use ptrauth_strip_insn_pac() and READ_ONCE_NOCHECK, see the comments.
- Get SCS pointer from x18, as per-task value is meant to save the SCS value on CPU switches.
- Collect stack frames from SDEI and IRQ contexts.

Quoted 8 lines

Changes v1->v2:
- Provide a kernel-wide stack_trace_save_shadow() interface for collecting stack traces from shadow stack.
- Use ptrauth_strip_insn_pac() and READ_ONCE_NOCHECK, see the comments.
- Get SCS pointer from x18, as per-task value is meant to save the SCS value on CPU switches.
- Collect stack frames from SDEI and IRQ contexts.

Do any of these new changes introduce new (noticeable) overhead (in particular patch 2)?

Quoted 9 lines · Marco Elver

Quoted 8 lines

Changes v1->v2:
- Provide a kernel-wide stack_trace_save_shadow() interface for collecting stack traces from shadow stack.
- Use ptrauth_strip_insn_pac() and READ_ONCE_NOCHECK, see the comments.
- Get SCS pointer from x18, as per-task value is meant to save the SCS value on CPU switches.
- Collect stack frames from SDEI and IRQ contexts.

Quoted 2 lines

Do any of these new changes introduce new (noticeable) overhead (in particular patch 2)?

I'll measure the overheads and include the results into v3. Thanks!

From: Andrey Konovalov <[email protected]>

kasan, arm64, scs, stacktrace: collect stack traces from Shadow Call Stack

Currently, KASAN always uses the normal stack trace collection routines, which rely on the unwinder, when saving alloc and free stack traces.

Instead of invoking the unwinder, collect the stack trace by copying frames from the Shadow Call Stack whenever it is enabled. This reduces boot time by 30% for all KASAN modes when Shadow Call Stack is enabled.

Stack staces are collected from the Shadow Call Stack via a new stack_trace_save_shadow() interface.

Note that the frame of the interrupted function is not included into the stack trace, as it is not yet saved on the SCS when an interrupt happens.

---

To deal with this last thing, we could save the interrupted frame address in another per-CPU variable. I'll look into implementing this for v3.

I decided to postpone the changes to stack depot that avoid copying frames twice until a planned upcoming update for stack depot.

Changes v1->v2:
- Provide a kernel-wide stack_trace_save_shadow() interface for collecting stack traces from shadow stack.
- Use ptrauth_strip_insn_pac() and READ_ONCE_NOCHECK, see the comments.
- Get SCS pointer from x18, as per-task value is meant to save the SCS value on CPU switches.
- Collect stack frames from SDEI and IRQ contexts.

Andrey Konovalov (4):
stacktrace: add interface based on shadow call stack arm64, scs: save scs_sp values per-cpu when switching stacks
arm64: implement stack_trace_save_shadow
kasan: use stack_trace_save_shadow

 arch/Kconfig                       |  6 +++
 arch/arm64/Kconfig                 |  1 +
 arch/arm64/include/asm/assembler.h | 12 +++++
 arch/arm64/include/asm/scs.h       | 13 ++++-
 arch/arm64/kernel/entry.S          | 28 ++++++++--
 arch/arm64/kernel/irq.c            |  4 +-
 arch/arm64/kernel/sdei.c           |  5 +-
 arch/arm64/kernel/stacktrace.c     | 83 ++++++++++++++++++++++++++++++
 include/linux/stacktrace.h         | 15 ++++++
 kernel/stacktrace.c                | 21 ++++++++
 mm/kasan/common.c                  |  9 ++--
 11 files changed, 183 insertions(+), 14 deletions(-)

Signature · 1 line

2.25.1

Quoted 7 lines · On Wed, Mar 23, 2022 at 04:32:51PM +0100, [email protected] wrote:

From: Andrey Konovalov <[email protected]>

kasan, arm64, scs, stacktrace: collect stack traces from Shadow Call Stack

Currently, KASAN always uses the normal stack trace collection routines, which rely on the unwinder, when saving alloc and free stack traces.

Quoted 3 lines

Instead of invoking the unwinder, collect the stack trace by copying frames from the Shadow Call Stack whenever it is enabled. This reduces boot time by 30% for all KASAN modes when Shadow Call Stack is enabled.

That is an impressive number. TBH, I'm shocked that this has *that* much of an improvement, and I suspect this means we're doing something unnecssarily expensive in the regular unwinder.

I've had a quick look into this, to see what we could do to improve the regular unwinder, but I can't reproduce that 30% number.

In local testing the worst can I could get to was 6-13% (with both the stacktrace *and* stackdepot logic hacked out entirely).

I'm testing with clang 13.0.0 from the llvm.org binary releases, with defconfig
+ SHADOW_CALL_STACK + KASAN_<option>, using a very recent snapshot of mainline (commit d888c83fcec75194a8a48ccd283953bdba7b2550). I'm booting a KVM-accelerated QEMU VM on ThunderX2 with "init=/sbin/reboot -- -f" in the kernel bootargs, timing the whole run from the outside with "perf stat --null".

The 6% figure is if I count boot as a whole including VM startup and teardown (i.e. an under-estimate of the proportion), the 13% figure is if I subtract a baseline timing from a run without KASAN (i.e. an over-estimate of the proportion).

Could you let me know how you're measuring this, and which platform+config you're using?

I'll have a play with some configs in case there's a pathological configuration, but if you could let me know how/what you're testing that'd be a great help.

Quoted 13 lines · Mark Rutland

I've had a quick look into this, to see what we could do to improve the regular unwinder, but I can't reproduce that 30% number.

In local testing the worst can I could get to was 6-13% (with both the stacktrace *and* stackdepot logic hacked out entirely).

I'm testing with clang 13.0.0 from the llvm.org binary releases, with defconfig
+ SHADOW_CALL_STACK + KASAN_<option>, using a very recent snapshot of mainline (commit d888c83fcec75194a8a48ccd283953bdba7b2550). I'm booting a KVM-accelerated QEMU VM on ThunderX2 with "init=/sbin/reboot -- -f" in the kernel bootargs, timing the whole run from the outside with "perf stat --null".

Quoted 4 lines

The 6% figure is if I count boot as a whole including VM startup and teardown (i.e. an under-estimate of the proportion), the 13% figure is if I subtract a baseline timing from a run without KASAN (i.e. an over-estimate of the proportion).

I think this is the reason for the limited improvement that you observe. If you measure the time throughout VM startup and teardown, you include the time required for userspace apps, which is irrelevant.

I measure boot time until a certain point during kernel boot. E.g., with the attached config, I measure the time until test_meminit start running.

It takes 6 seconds for the kernel to reach test_meminit as is, and 4 seconds with kasan_save_stack() commented out. Only commenting out __stack_depot_save() gives 5.9 seconds, so stack_trace_save() is the slow part.

Quoted 2 lines

Could you let me know how you're measuring this, and which platform+config you're using?

I've attached the config that I use. It's essentially defconfig + SCS
+ KASAN + maybe a few other options.

Quoted 3 lines

I'll have a play with some configs in case there's a pathological configuration, but if you could let me know how/what you're testing that'd be a great help.

I'm afraid from local testing (atop v5.18-rc1), with your config, I still can't get anywhere near your figures. I've tried to match toolchain versions with what was in your .config file, so I'm using clang 12.0.0 from the llvm.org binary releases, and binutils from the kernel.org crosstool 11.1.0 release.

I took baselines with defconfig and defconfig + SHADOW_CALL_STACK, with console output completely suppressed with 'quiet loglevel=0':

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-defconfig/Image
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-defconfig/Image -append
|  loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        0.512626031 seconds time elapsed                                          ( +-  0.26% )
|
| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-defconfig+scs/Image
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-defconfig+scs/Image -append
|  loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        0.523245952 seconds time elapsed                                          ( +-  0.18% )

Then I tried the same with your config, without your patches:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image -append
|  loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        1.994692366 seconds time elapsed                                          ( +-  0.05% )

Then with your config, without your patches, with the stacktrace hacked out:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image
| -append loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        1.861823869 seconds time elapsed                                          ( +-  0.05% )

If I use those number to estimate the proportion of time spent stacktracing, with the baseline SCS number discounted to remove the hypervisor+VMM overheads, I get:

        (1.994692366 - 0.523245952) - (1.861823869 - 0.523245952)
        ---------------------------------------------------------  = 0.09029788358
        (1.994692366 - 0.523245952)

So roughly 9% when I try to maximize that figure. When actually poking hardware and doing real work, that figure goes down. For example, if just using "quiet":

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -q -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image > /dev/null
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image -append
| loglevel=9 earlycon panic=-1 quiet' (50 runs):
|
|        4.653286475 seconds time elapsed                                          ( +-  0.06% )

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -q -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image > /dev/null
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image
|  -append loglevel=9 earlycon panic=-1 quiet' (50 runs):
|
|        4.585750154 seconds time elapsed                                          ( +-  0.05% )

Which gives an estimate of:

        (4.653286475 - 0.523245952) - (4.585750154 - 0.523245952)
        ---------------------------------------------------------  = 0.01635245964
        (4.653286475 - 0.523245952)

... or ~1.6% time spent backtracing:

FWIW, applying your patches do show some benefit, but not as drastic as I was expecting:

With console output suprressed:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image
| -append loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        1.920300410 seconds time elapsed                                          ( +-  0.05% )

... down from ~9% to ~4%

With console output merely reduced:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -q -k ~/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image > /dev/null
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image
| -append loglevel=9 earlycon panic=-1 quiet' (50 runs):
|
|        4.611277833 seconds time elapsed                                          ( +-  0.04% )

... down from 1.6% to 0.6%

Given the above I still think we need to understand this a bit better before we consider pursuing the SCS unwinder, given the issues I laid out in my prior mails.

My hope is that we can improve the regular unwinder or other code such that this becomes moot. I'm aware of a few things we could try, but given it's very easy to sink a lot of time and effort into this, I'd like to first get some more details, as above.

Quoted 123 lines · Mark Rutland

I'm afraid from local testing (atop v5.18-rc1), with your config, I still can't get anywhere near your figures. I've tried to match toolchain versions with what was in your .config file, so I'm using clang 12.0.0 from the llvm.org binary releases, and binutils from the kernel.org crosstool 11.1.0 release.

I took baselines with defconfig and defconfig + SHADOW_CALL_STACK, with console output completely suppressed with 'quiet loglevel=0':

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-defconfig/Image
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-defconfig/Image -append
|  loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        0.512626031 seconds time elapsed                                          ( +-  0.26% )
|
| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-defconfig+scs/Image
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-defconfig+scs/Image -append
|  loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        0.523245952 seconds time elapsed                                          ( +-  0.18% )

Then I tried the same with your config, without your patches:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image -append
|  loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        1.994692366 seconds time elapsed                                          ( +-  0.05% )

Then with your config, without your patches, with the stacktrace hacked out:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image
| -append loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        1.861823869 seconds time elapsed                                          ( +-  0.05% )

If I use those number to estimate the proportion of time spent stacktracing, with the baseline SCS number discounted to remove the hypervisor+VMM overheads, I get:

        (1.994692366 - 0.523245952) - (1.861823869 - 0.523245952)
        ---------------------------------------------------------  = 0.09029788358
        (1.994692366 - 0.523245952)

So roughly 9% when I try to maximize that figure. When actually poking hardware and doing real work, that figure goes down. For example, if just using "quiet":

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -q -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image > /dev/null
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config/Image -append
| loglevel=9 earlycon panic=-1 quiet' (50 runs):
|
|        4.653286475 seconds time elapsed                                          ( +-  0.06% )

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -q -k ~/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image > /dev/null
|
|  Performance counter stats for
|  '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
|  -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
|  /home/mark/kernel-images/andrey-unwind-v5.18-rc1-andrey.config-nostacktrace/Image
|  -append loglevel=9 earlycon panic=-1 quiet' (50 runs):
|
|        4.585750154 seconds time elapsed                                          ( +-  0.05% )

Which gives an estimate of:

        (4.653286475 - 0.523245952) - (4.585750154 - 0.523245952)
        ---------------------------------------------------------  = 0.01635245964
        (4.653286475 - 0.523245952)

... or ~1.6% time spent backtracing:

FWIW, applying your patches do show some benefit, but not as drastic as I was expecting:

With console output suprressed:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -s -k ~/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image
| -append loglevel=9 earlycon panic=-1 quiet loglevel=0' (50 runs):
|
|        1.920300410 seconds time elapsed                                          ( +-  0.05% )

... down from ~9% to ~4%

With console output merely reduced:

| [mark@gravadlaks:~/repro]% taskset -c 64 ./vmboot.sh --perf-trials 50 -q -k ~/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image > /dev/null
|
|  Performance counter stats for
| '/home/mark/.opt/apps/qemu/bin/qemu-system-aarch64 -m 2048 -smp 1 -nographic
| -no-reboot -machine virt,accel=kvm,gic-version=host -cpu host -kernel
| /home/mark/kernel-images/andrey-unwind-v5.18-rc1+scs-unwind-andrey.config/Image
| -append loglevel=9 earlycon panic=-1 quiet' (50 runs):
|
|        4.611277833 seconds time elapsed                                          ( +-  0.04% )

... down from 1.6% to 0.6%

Quoted 7 lines

Given the above I still think we need to understand this a bit better before we consider pursuing the SCS unwinder, given the issues I laid out in my prior mails.

My hope is that we can improve the regular unwinder or other code such that this becomes moot. I'm aware of a few things we could try, but given it's very easy to sink a lot of time and effort into this, I'd like to first get some more details, as above.

Hi Mark,

I'm about to publish v3, where I'll include a detailed description of how I measured the performance.

Perhaps we see different performance numbers because you're using KVM-enabled VM on an Arm host and I'm using QEMU on x86-64 host.

Although, it's suspicious that the difference is so drastic.

I'll try to get my hands on some Arm hardware in the next few days and do the measurements there.

This new version also will not be making any changes to the entry code, as these changes add unwanted additional slowdown. That would be great, if you could check the performance impact of v3 with your setup.

That is an impressive number. TBH, I'm shocked that this has *that* much of an improvement, and I suspect this means we're doing something unnecssarily expensive in the regular unwinder.

I've given some specific comments on patches, but a a high-level, I don't want to add yet another unwind mechanism. For maintenance and correctness reasons, we've spent the last few years consolidating various unwinders, which this unfortunately goes against.

I see that there are number of cases this unwinder will fall afoul of (e.g. kretprobes and ftrace graph trampolines), and making those work correctly will require changes elsewhere (e.g. as we rely upon a snapshot of the FP to disambiguate cases today).

I'm also very much not keen on having to stash things in the entry assembly for this distinct unwinder.

Going forward, I'm also planning on making changes to the way we unwind across exception boundaries (e.g. to report the LR and FP), and as that depends on finding the pt_regs based on the FP, that's not going to work with SCS.

So at a high level, I don't want to add an SCS based unwinder.

However, I'm very much open to how we could improve the standard unwinder to be faster, which would be more generally beneficial. I can see that there are some things we could reasonably do with simple refactoring.