[RFC PATCH v2 0/3] arm64: stacktrace: Improve robustness and ensure termination of backtraces

[RFC PATCH v2 0/3] arm64: stacktrace: Improve robustness and ensure termination of backtraces

[Dave Martin]

This is an update to the previous RFC. [1]

Major changes since RFC v1:

 * Remove assumptions about a strict hierachy of the different stacks. [*]

 * Visited stacks are now tracked using a bitmap in struct stackframe
   to prevent cycling.

 * Still untested.

Comments welcome.

[*] For those interested, I think valid backtraces are as follows.
Nodes in [] are the starting points for the backtrace (depending on
which stack the initial FP points to).  Valid transitions are upwards
and leftwards.  Validity is transitive (so, [sde] -> [task] is allowed
for example).

   [task]---[irq]----sde-----sdec
       \      \         \       \
        `------ ovf     ovf    [ovf]
                   \       \
                    [sde]---[sdec]

(ovf = overflow stack; sde = normal SDEI stack;
sdec = critical SDEI stack).

(It's the overflow stack that complicates this picture.)


Sadly, this ends up a lot more complex to express in the code than
seems reasonable if coded longhand.  A table-driven approach could be
a lot cleaner, but nobody is going to enjoy maintaining the table of
transitions :P

Failing this, this series should at least ensure termination after a
finite number of frames.  The chance of a randomly corrupted stack
frame linking to a frame address that is also on a valid stack is
minimal in practice anyway.


Original blurb:

As reported by Ji Zhang, [2] arm64's backtracer currently has limited
protection against stack corruption.  In particular, it is possible to
cycle between stacks.  It is also possible to cycle on a single stack
because the same-stack and different-stack cases of the transition to
the next frame are not distinguished, meaning that it is not
straightforward to check that the frame address is moving in the
correct direction.  Both of these can result in infinite backtrace
loops.

This series attempts to build on the approach in [2] to ensure forward
progress and eventual termination of any backtrace.

It makes some assumptions, particularly about which stack transitions
are valid -- so feedback from anybody who is familiar with arm64
kernel stack management would be very useful here.

This series is also completely untested!  It builds.

[1] [RFC PATCH 0/3] arm64: stacktrace: Improve robustness and ensure termination of backtraces
http://lists.infradead.org/pipermail/linux-arm-kernel/2018-April/572685.html

[2] [PATCH] arm64: avoid potential infinity loop in dump_backtrace
http://lists.infradead.org/pipermail/linux-arm-kernel/2018-April/572579.html

Dave Martin (3):
  arm64: stacktrace: Constify stacktrace.h functions
  arm64: stacktrace: Factor out backtrace initialisation
  arm64: stacktrace: Prevent looping and invalid stack transitions

 arch/arm64/include/asm/sdei.h       | 13 +++++++------
 arch/arm64/include/asm/stackid.h    | 22 +++++++++++++++++++++
 arch/arm64/include/asm/stacktrace.h | 38 ++++++++++++++++++++++++++++---------
 arch/arm64/kernel/process.c         |  6 +-----
 arch/arm64/kernel/sdei.c            | 12 ++++++++----
 arch/arm64/kernel/stacktrace.c      | 30 +++++++++++++++++++++++------
 arch/arm64/kernel/time.c            |  6 +-----
 arch/arm64/kernel/traps.c           | 21 ++++++++------------
 8 files changed, 100 insertions(+), 48 deletions(-)
 create mode 100644 arch/arm64/include/asm/stackid.h

-- 
2.1.4

[RFC PATCH v2 1/3] arm64: stacktrace: Constify stacktrace.h functions

[Dave Martin]

on_accessible_stack() and on_task_stack() shouldn't (and don't)
modify their task argument, so it can be const.

This patch adds the appropriate modifiers.

No functional change.

Signed-off-by: Dave Martin <Dave.Martin@arm.com>
Acked-by: Mark Rutland <mark.rutland@arm.com>
---
 arch/arm64/include/asm/stacktrace.h | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/arch/arm64/include/asm/stacktrace.h b/arch/arm64/include/asm/stacktrace.h
index 902f9ed..63c0379 100644
--- a/arch/arm64/include/asm/stacktrace.h
+++ b/arch/arm64/include/asm/stacktrace.h
@@ -50,7 +50,8 @@ static inline bool on_irq_stack(unsigned long sp)
 	return (low <= sp && sp < high);
 }
 
-static inline bool on_task_stack(struct task_struct *tsk, unsigned long sp)
+static inline bool on_task_stack(struct task_struct const *tsk,
+				 unsigned long sp)
 {
 	unsigned long low = (unsigned long)task_stack_page(tsk);
 	unsigned long high = low + THREAD_SIZE;
@@ -76,7 +77,8 @@ static inline bool on_overflow_stack(unsigned long sp) { return false; }
  * We can only safely access per-cpu stacks from current in a non-preemptible
  * context.
  */
-static inline bool on_accessible_stack(struct task_struct *tsk, unsigned long sp)
+static inline bool on_accessible_stack(struct task_struct const *tsk,
+				       unsigned long sp)
 {
 	if (on_task_stack(tsk, sp))
 		return true;
-- 
2.1.4

[RFC PATCH v2 2/3] arm64: stacktrace: Factor out backtrace initialisation

[Dave Martin]

Some common code is required by each stacktrace user to initialise
struct stackframe before the first call to unwind_frame().

In preparation for adding to the common code, this patch factors it
out into a separate function start_backtrace(), and modifies the
stacktrace callers appropriately.

No functional change.

Signed-off-by: Dave Martin <Dave.Martin@arm.com>
Acked-by: Mark Rutland <mark.rutland@arm.com>
---
 arch/arm64/include/asm/stacktrace.h | 11 +++++++++++
 arch/arm64/kernel/process.c         |  6 +-----
 arch/arm64/kernel/time.c            |  6 +-----
 arch/arm64/kernel/traps.c           | 21 ++++++++-------------
 4 files changed, 21 insertions(+), 23 deletions(-)

diff --git a/arch/arm64/include/asm/stacktrace.h b/arch/arm64/include/asm/stacktrace.h
index 63c0379..c9bef22 100644
--- a/arch/arm64/include/asm/stacktrace.h
+++ b/arch/arm64/include/asm/stacktrace.h
@@ -94,4 +94,15 @@ static inline bool on_accessible_stack(struct task_struct const *tsk,
 	return false;
 }
 
+static inline void start_backtrace(struct stackframe *frame,
+			    struct task_struct const *tsk,
+			    unsigned long fp, unsigned long pc)
+{
+	frame->fp = fp;
+	frame->pc = pc;
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	frame.graph = tsk->curr_ret_stack;
+#endif
+}
+
 #endif	/* __ASM_STACKTRACE_H */
diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index f08a2ed..59b418c 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -452,11 +452,7 @@ unsigned long get_wchan(struct task_struct *p)
 	if (!stack_page)
 		return 0;
 
-	frame.fp = thread_saved_fp(p);
-	frame.pc = thread_saved_pc(p);
-#ifdef CONFIG_FUNCTION_GRAPH_TRACER
-	frame.graph = p->curr_ret_stack;
-#endif
+	start_backtrace(&frame, p, thread_saved_fp(p), thread_saved_pc(p));
 	do {
 		if (unwind_frame(p, &frame))
 			goto out;
diff --git a/arch/arm64/kernel/time.c b/arch/arm64/kernel/time.c
index f258636..83f08c7 100644
--- a/arch/arm64/kernel/time.c
+++ b/arch/arm64/kernel/time.c
@@ -49,11 +49,7 @@ unsigned long profile_pc(struct pt_regs *regs)
 	if (!in_lock_functions(regs->pc))
 		return regs->pc;
 
-	frame.fp = regs->regs[29];
-	frame.pc = regs->pc;
-#ifdef CONFIG_FUNCTION_GRAPH_TRACER
-	frame.graph = current->curr_ret_stack;
-#endif
+	start_backtrace(&frame, current, regs->regs[29], regs->pc);
 	do {
 		int ret = unwind_frame(NULL, &frame);
 		if (ret < 0)
diff --git a/arch/arm64/kernel/traps.c b/arch/arm64/kernel/traps.c
index 1cb2749..40591cf 100644
--- a/arch/arm64/kernel/traps.c
+++ b/arch/arm64/kernel/traps.c
@@ -111,19 +111,14 @@ void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk)
 	if (!try_get_task_stack(tsk))
 		return;
 
-	if (tsk == current) {
-		frame.fp = (unsigned long)__builtin_frame_address(0);
-		frame.pc = (unsigned long)dump_backtrace;
-	} else {
-		/*
-		 * task blocked in __switch_to
-		 */
-		frame.fp = thread_saved_fp(tsk);
-		frame.pc = thread_saved_pc(tsk);
-	}
-#ifdef CONFIG_FUNCTION_GRAPH_TRACER
-	frame.graph = tsk->curr_ret_stack;
-#endif
+	if (tsk == current)
+		start_backtrace(&frame, tsk,
+				(unsigned long)__builtin_frame_address(0),
+				(unsigned long)dump_backtrace);
+	else /* task blocked in __switch_to */
+		start_backtrace(&frame, tsk,
+				thread_saved_fp(tsk),
+				thread_saved_pc(tsk));
 
 	skip = !!regs;
 	printk("Call trace:\n");
-- 
2.1.4

[RFC PATCH v2 3/3] arm64: stacktrace: Prevent looping and invalid stack transitions

[Dave Martin]

In the event of stack corruption, backtraces may loop indefinitely
or wander off into memory that is not a valid stack for the context
being backtraced.

This patch makes backtracing more robust against stack corruption,
by taking two things into account:

 * while staying on the same stack, the frame address must strictly
   increase from each frame to its ancestor;

 * when transitioning to another stack, the destination stack must
   be a stack that has not been visited already.

on_accessible_stack() is converted to a more expressive helper
identify_stack() that also tells the caller _which_ stack the task
appears to be on.  A field stack_id is added to struct stackframe
to track the result of this for the frame, along with a bitmap
stacks_used that records which stacks have been visited by the
backtrace.

Now that it is easy to check whether two successive frames are on
the same stack, it becomes straightfowrard to add a check for
strictly increasing frame address, to avoid looping around the same
stack: this patch adds that too.

This patch does not attempt to catch invalid transitions such as
from the task stack to the IRQ stack.  It turns out that the way
the overflow stack is used makes this complicated.  Nonetheless,
the number of frames parsed before the backtracer terminates should
now be guaranteed to be finite.

Reported-by: Ji Zhang <ji.zhang@mediatek.com>
Signed-off-by: Dave Martin <Dave.Martin@arm.com>
---
 arch/arm64/include/asm/sdei.h       | 13 +++++++------
 arch/arm64/include/asm/stackid.h    | 22 ++++++++++++++++++++++
 arch/arm64/include/asm/stacktrace.h | 29 ++++++++++++++++++-----------
 arch/arm64/kernel/sdei.c            | 12 ++++++++----
 arch/arm64/kernel/stacktrace.c      | 30 ++++++++++++++++++++++++------
 5 files changed, 79 insertions(+), 27 deletions(-)
 create mode 100644 arch/arm64/include/asm/stackid.h

diff --git a/arch/arm64/include/asm/sdei.h b/arch/arm64/include/asm/sdei.h
index e073e68..5b56cfd 100644
--- a/arch/arm64/include/asm/sdei.h
+++ b/arch/arm64/include/asm/sdei.h
@@ -15,6 +15,7 @@
 #include <linux/preempt.h>
 #include <linux/types.h>
 
+#include <asm/stackid.h>
 #include <asm/virt.h>
 
 extern unsigned long sdei_exit_mode;
@@ -40,17 +41,17 @@ asmlinkage unsigned long __sdei_handler(struct pt_regs *regs,
 unsigned long sdei_arch_get_entry_point(int conduit);
 #define sdei_arch_get_entry_point(x)	sdei_arch_get_entry_point(x)
 
-bool _on_sdei_stack(unsigned long sp);
-static inline bool on_sdei_stack(unsigned long sp)
+enum arm64_stack_id _identify_sdei_stack(unsigned long sp);
+static inline enum arm64_stack_id identify_sdei_stack(unsigned long sp)
 {
 	if (!IS_ENABLED(CONFIG_VMAP_STACK))
-		return false;
+		return ARM64_STACK_NONE;
 	if (!IS_ENABLED(CONFIG_ARM_SDE_INTERFACE))
-		return false;
+		return ARM64_STACK_NONE;
 	if (in_nmi())
-		return _on_sdei_stack(sp);
+		return _identify_sdei_stack(sp);
 
-	return false;
+	return ARM64_STACK_NONE;
 }
 
 #endif /* __ASSEMBLY__ */
diff --git a/arch/arm64/include/asm/stackid.h b/arch/arm64/include/asm/stackid.h
new file mode 100644
index 0000000..3c4aefc
--- /dev/null
+++ b/arch/arm64/include/asm/stackid.h
@@ -0,0 +1,22 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * arch/arm64/include/asm/stackid.h: Stack identification
+ *
+ * Copyright 2018 Arm Limited
+ * Author: Dave Martin <Dave.Martin@arm.com>
+ */
+#ifndef __ASM_STACKID_H
+#define __ASM_STACKID_H
+
+/* Set of stacks that a given task may execute on. */
+enum arm64_stack_id {
+	ARM64_STACK_TASK = 0,
+	ARM64_STACK_IRQ,
+	ARM64_STACK_OVERFLOW,
+	ARM64_STACK_SDEI_NORMAL,
+	ARM64_STACK_SDEI_CRITICAL,
+	__NR_ARM64_STACKS,
+	ARM64_STACK_NONE = __NR_ARM64_STACKS,
+};
+
+#endif /* ! __ASM_STACKID_H */
diff --git a/arch/arm64/include/asm/stacktrace.h b/arch/arm64/include/asm/stacktrace.h
index c9bef22..f06a76a 100644
--- a/arch/arm64/include/asm/stacktrace.h
+++ b/arch/arm64/include/asm/stacktrace.h
@@ -16,6 +16,7 @@
 #ifndef __ASM_STACKTRACE_H
 #define __ASM_STACKTRACE_H
 
+#include <linux/bitmap.h>
 #include <linux/percpu.h>
 #include <linux/sched.h>
 #include <linux/sched/task_stack.h>
@@ -23,10 +24,13 @@
 #include <asm/memory.h>
 #include <asm/ptrace.h>
 #include <asm/sdei.h>
+#include <asm/stackid.h>
 
 struct stackframe {
 	unsigned long fp;
 	unsigned long pc;
+	DECLARE_BITMAP(stacks_used, __NR_ARM64_STACKS);
+	enum arm64_stack_id stack_id;
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 	int graph;
 #endif
@@ -77,21 +81,18 @@ static inline bool on_overflow_stack(unsigned long sp) { return false; }
  * We can only safely access per-cpu stacks from current in a non-preemptible
  * context.
  */
-static inline bool on_accessible_stack(struct task_struct const *tsk,
-				       unsigned long sp)
+static enum arm64_stack_id identify_stack(struct task_struct const *tsk,
+					  unsigned long sp)
 {
 	if (on_task_stack(tsk, sp))
-		return true;
+		return ARM64_STACK_TASK;
 	if (tsk != current || preemptible())
-		return false;
+		return ARM64_STACK_NONE;
 	if (on_irq_stack(sp))
-		return true;
+		return ARM64_STACK_IRQ;
 	if (on_overflow_stack(sp))
-		return true;
-	if (on_sdei_stack(sp))
-		return true;
-
-	return false;
+		return ARM64_STACK_OVERFLOW;
+	return identify_sdei_stack(sp);
 }
 
 static inline void start_backtrace(struct stackframe *frame,
@@ -100,8 +101,14 @@ static inline void start_backtrace(struct stackframe *frame,
 {
 	frame->fp = fp;
 	frame->pc = pc;
+	bitmap_zero(frame->stacks_used, __NR_ARM64_STACKS);
+
+	frame->stack_id = identify_stack(tsk, fp);
+	if (frame->stack_id != ARM64_STACK_NONE)
+		set_bit(frame->stack_id, frame->stacks_used);
+
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
-	frame.graph = tsk->curr_ret_stack;
+	frame->graph = tsk->curr_ret_stack;
 #endif
 }
 
diff --git a/arch/arm64/kernel/sdei.c b/arch/arm64/kernel/sdei.c
index 6b8d90d..93665b0 100644
--- a/arch/arm64/kernel/sdei.c
+++ b/arch/arm64/kernel/sdei.c
@@ -13,6 +13,7 @@
 #include <asm/mmu.h>
 #include <asm/ptrace.h>
 #include <asm/sections.h>
+#include <asm/stackid.h>
 #include <asm/sysreg.h>
 #include <asm/vmap_stack.h>
 
@@ -88,23 +89,26 @@ static int init_sdei_stacks(void)
 	return err;
 }
 
-bool _on_sdei_stack(unsigned long sp)
+enum arm64_stack_id _identify_sdei_stack(unsigned long sp)
 {
 	unsigned long low, high;
 
 	if (!IS_ENABLED(CONFIG_VMAP_STACK))
-		return false;
+		return ARM64_STACK_NONE;
 
 	low = (unsigned long)raw_cpu_read(sdei_stack_critical_ptr);
 	high = low + SDEI_STACK_SIZE;
 
 	if (low <= sp && sp < high)
-		return true;
+		return ARM64_STACK_SDEI_CRITICAL;
 
 	low = (unsigned long)raw_cpu_read(sdei_stack_normal_ptr);
 	high = low + SDEI_STACK_SIZE;
 
-	return (low <= sp && sp < high);
+	if (low <= sp && sp < high)
+		return ARM64_STACK_SDEI_NORMAL;
+
+	return ARM64_STACK_NONE;
 }
 
 unsigned long sdei_arch_get_entry_point(int conduit)
diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index d5718a0..a5e0547 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -43,6 +43,7 @@
 int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 {
 	unsigned long fp = frame->fp;
+	enum arm64_stack_id stack_id = frame->stack_id;
 
 	if (fp & 0xf)
 		return -EINVAL;
@@ -50,11 +51,12 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 	if (!tsk)
 		tsk = current;
 
-	if (!on_accessible_stack(tsk, fp))
+	if (stack_id == ARM64_STACK_NONE)
 		return -EINVAL;
 
 	frame->fp = READ_ONCE_NOCHECK(*(unsigned long *)(fp));
 	frame->pc = READ_ONCE_NOCHECK(*(unsigned long *)(fp + 8));
+	frame->stack_id = identify_stack(tsk, frame->fp);
 
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 	if (tsk->ret_stack &&
@@ -75,14 +77,30 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 #endif /* CONFIG_FUNCTION_GRAPH_TRACER */
 
 	/*
-	 * Frames created upon entry from EL0 have NULL FP and PC values, so
-	 * don't bother reporting these. Frames created by __noreturn functions
-	 * might have a valid FP even if PC is bogus, so only terminate where
-	 * both are NULL.
+	 * Terminate when the next frame isn't on any valid stack for
+	 * tsk.  As a special case, frames created upon entry from EL0
+	 * have NULL FP and PC values, so will terminate here also.
+	 * Frames created by __noreturn functions might have a valid FP
+	 * even if PC is bogus, so only terminate where FP is invalid.
 	 */
-	if (!frame->fp && !frame->pc)
+	if (frame->stack_id == ARM64_STACK_NONE)
 		return -EINVAL;
 
+	/*
+	 * Reject attempts to recurse back onto a stack that has been
+	 * visited already:
+	 */
+	if (test_bit(frame->stack_id, frame->stacks_used))
+		return -EINVAL;
+
+	/* Verify forward progress while on the same stack: */
+	if (frame->stack_id == stack_id) {
+		if (frame->fp <= fp)
+			return -EINVAL;
+	}
+
+	set_bit(frame->stack_id, frame->stacks_used);
+
 	return 0;
 }
 
-- 
2.1.4

[RFC PATCH v2 3/3] arm64: stacktrace: Prevent looping and invalid stack transitions

[James Morse]

Hi Dave,

On 23/04/18 18:07, Dave Martin wrote:
> In the event of stack corruption, backtraces may loop indefinitely
> or wander off into memory that is not a valid stack for the context
> being backtraced.
> 
> This patch makes backtracing more robust against stack corruption,
> by taking two things into account:
> 
>  * while staying on the same stack, the frame address must strictly
>    increase from each frame to its ancestor;
> 
>  * when transitioning to another stack, the destination stack must
>    be a stack that has not been visited already.
> 
> on_accessible_stack() is converted to a more expressive helper
> identify_stack() that also tells the caller _which_ stack the task
> appears to be on.  A field stack_id is added to struct stackframe
> to track the result of this for the frame, along with a bitmap
> stacks_used that records which stacks have been visited by the
> backtrace.
> 
> Now that it is easy to check whether two successive frames are on
> the same stack, it becomes straightfowrard to add a check for
> strictly increasing frame address, to avoid looping around the same
> stack: this patch adds that too.
> 
> This patch does not attempt to catch invalid transitions such as
> from the task stack to the IRQ stack.  It turns out that the way
> the overflow stack is used makes this complicated.  Nonetheless,
> the number of frames parsed before the backtracer terminates should
> now be guaranteed to be finite.

Sounds like a good idea, I gave this a quick spin with SDEI...

With this series on top of the SDEI test goo:
[51497.386354] CPU: 0 PID: 0 Comm: swapper/0 Not tainted
4.17.0-rc2-00023-g144855c44b20-dirty #9721
[51497.386366] Call trace:
[51497.386409]  dump_backtrace+0x0/0x1b8


Without this series:
[275604.647803] CPU: 0 PID: 0 Comm: swapper/0 Not tainted
4.17.0-rc2-00018-gcf83397e1eaf-dirty #9722
[275604.647814] Call trace:
[275604.647857]  dump_backtrace+0x0/0x190
[275604.647900]  show_stack+0x14/0x20
[275604.647938]  dump_stack+0xac/0xe4
[275604.647972]  __sdei_handler+0x184/0x1d0
[275604.648009]  __sdei_asm_handler+0xbc/0x130
[275604.648050]  cpu_do_idle+0x8/0xc
[275604.648085]  default_idle_call+0x1c/0x38
[275604.648115]  do_idle+0x1bc/0x270
[275604.648147]  cpu_startup_entry+0x24/0x28
[275604.648189]  rest_init+0x24c/0x260
[275604.648226]  start_kernel+0x3b8/0x3cc


(please forgive the timestamps, the FVP thinks its a time machine)


> diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
> index d5718a0..a5e0547 100644
> --- a/arch/arm64/kernel/stacktrace.c
> +++ b/arch/arm64/kernel/stacktrace.c
> @@ -75,14 +77,30 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
>  #endif /* CONFIG_FUNCTION_GRAPH_TRACER */
>  
>  	/*
> -	 * Frames created upon entry from EL0 have NULL FP and PC values, so
> -	 * don't bother reporting these. Frames created by __noreturn functions
> -	 * might have a valid FP even if PC is bogus, so only terminate where
> -	 * both are NULL.
> +	 * Terminate when the next frame isn't on any valid stack for
> +	 * tsk.  As a special case, frames created upon entry from EL0
> +	 * have NULL FP and PC values, so will terminate here also.
> +	 * Frames created by __noreturn functions might have a valid FP
> +	 * even if PC is bogus, so only terminate where FP is invalid.
>  	 */
> -	if (!frame->fp && !frame->pc)
> +	if (frame->stack_id == ARM64_STACK_NONE)
>  		return -EINVAL;


> +	/*
> +	 * Reject attempts to recurse back onto a stack that has been
> +	 * visited already:
> +	 */
> +	if (test_bit(frame->stack_id, frame->stacks_used))
> +		return -EINVAL;

Won't this happen for every frame? So we only get one frame per stack.
Could we move this into some special handling for stepping between stacks?


> +
> +	/* Verify forward progress while on the same stack: */
> +	if (frame->stack_id == stack_id) {
> +		if (frame->fp <= fp)
> +			return -EINVAL;
> +	}
> +
> +	set_bit(frame->stack_id, frame->stacks_used);
> +
>  	return 0;
>  }


Thanks,

James

[RFC PATCH v2 3/3] arm64: stacktrace: Prevent looping and invalid stack transitions

[Dave Martin]

On Fri, Apr 27, 2018 at 12:23:21PM +0100, James Morse wrote:
> Hi Dave,
> 
> On 23/04/18 18:07, Dave Martin wrote:
> > In the event of stack corruption, backtraces may loop indefinitely
> > or wander off into memory that is not a valid stack for the context
> > being backtraced.
> > 
> > This patch makes backtracing more robust against stack corruption,
> > by taking two things into account:
> > 
> >  * while staying on the same stack, the frame address must strictly
> >    increase from each frame to its ancestor;
> > 
> >  * when transitioning to another stack, the destination stack must
> >    be a stack that has not been visited already.
> > 
> > on_accessible_stack() is converted to a more expressive helper
> > identify_stack() that also tells the caller _which_ stack the task
> > appears to be on.  A field stack_id is added to struct stackframe
> > to track the result of this for the frame, along with a bitmap
> > stacks_used that records which stacks have been visited by the
> > backtrace.
> > 
> > Now that it is easy to check whether two successive frames are on
> > the same stack, it becomes straightfowrard to add a check for
> > strictly increasing frame address, to avoid looping around the same
> > stack: this patch adds that too.
> > 
> > This patch does not attempt to catch invalid transitions such as
> > from the task stack to the IRQ stack.  It turns out that the way
> > the overflow stack is used makes this complicated.  Nonetheless,
> > the number of frames parsed before the backtracer terminates should
> > now be guaranteed to be finite.
> 
> Sounds like a good idea, I gave this a quick spin with SDEI...
> 
> With this series on top of the SDEI test goo:
> [51497.386354] CPU: 0 PID: 0 Comm: swapper/0 Not tainted
> 4.17.0-rc2-00023-g144855c44b20-dirty #9721
> [51497.386366] Call trace:
> [51497.386409]  dump_backtrace+0x0/0x1b8
> 
> 
> Without this series:
> [275604.647803] CPU: 0 PID: 0 Comm: swapper/0 Not tainted
> 4.17.0-rc2-00018-gcf83397e1eaf-dirty #9722
> [275604.647814] Call trace:
> [275604.647857]  dump_backtrace+0x0/0x190
> [275604.647900]  show_stack+0x14/0x20
> [275604.647938]  dump_stack+0xac/0xe4
> [275604.647972]  __sdei_handler+0x184/0x1d0
> [275604.648009]  __sdei_asm_handler+0xbc/0x130
> [275604.648050]  cpu_do_idle+0x8/0xc
> [275604.648085]  default_idle_call+0x1c/0x38
> [275604.648115]  do_idle+0x1bc/0x270
> [275604.648147]  cpu_startup_entry+0x24/0x28
> [275604.648189]  rest_init+0x24c/0x260
> [275604.648226]  start_kernel+0x3b8/0x3cc
> 
> 
> (please forgive the timestamps, the FVP thinks its a time machine)
> 
> 
> > diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
> > index d5718a0..a5e0547 100644
> > --- a/arch/arm64/kernel/stacktrace.c
> > +++ b/arch/arm64/kernel/stacktrace.c
> > @@ -75,14 +77,30 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
> >  #endif /* CONFIG_FUNCTION_GRAPH_TRACER */
> >  
> >  	/*
> > -	 * Frames created upon entry from EL0 have NULL FP and PC values, so
> > -	 * don't bother reporting these. Frames created by __noreturn functions
> > -	 * might have a valid FP even if PC is bogus, so only terminate where
> > -	 * both are NULL.
> > +	 * Terminate when the next frame isn't on any valid stack for
> > +	 * tsk.  As a special case, frames created upon entry from EL0
> > +	 * have NULL FP and PC values, so will terminate here also.
> > +	 * Frames created by __noreturn functions might have a valid FP
> > +	 * even if PC is bogus, so only terminate where FP is invalid.
> >  	 */
> > -	if (!frame->fp && !frame->pc)
> > +	if (frame->stack_id == ARM64_STACK_NONE)
> >  		return -EINVAL;
> 
> 
> > +	/*
> > +	 * Reject attempts to recurse back onto a stack that has been
> > +	 * visited already:
> > +	 */
> > +	if (test_bit(frame->stack_id, frame->stacks_used))
> > +		return -EINVAL;
> 
> Won't this happen for every frame? So we only get one frame per stack.
> Could we move this into some special handling for stepping between stacks?

D'oh... that check is only supposed to happen on a stack switch.

> > +
> > +	/* Verify forward progress while on the same stack: */
> > +	if (frame->stack_id == stack_id) {
> > +		if (frame->fp <= fp)
> > +			return -EINVAL;
> > +	}

Can you try adding

	else {
		if (test_bit(frame->stack_id, frame->stacks_used))
			return -EINVAL;
	}

(and removing that above)

Cheers
---Dave