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

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

[Dave Martin]

As reported by Ji Zhang, [1] 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 [1] 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] [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/stacktrace.h | 48 ++++++++++++++++++++++++++++++-------
 arch/arm64/kernel/process.c         |  6 +----
 arch/arm64/kernel/stacktrace.c      | 16 ++++++++-----
 arch/arm64/kernel/time.c            |  6 +----
 arch/arm64/kernel/traps.c           | 21 +++++++---------
 5 files changed, 60 insertions(+), 37 deletions(-)

-- 
2.1.4

[RFC PATCH 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>
---
 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 1/3] arm64: stacktrace: Constify stacktrace.h functions

[Mark Rutland]

On Fri, Apr 20, 2018 at 11:46:17AM +0100, Dave Martin wrote:
> 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>

FWIW:

Acked-by: Mark Rutland <mark.rutland@arm.com>

Mark.

> ---
>  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 2/3] arm64: stacktrace: Factor out backtrace initialisation

[Dave Martin]

Some common code is required by each stacktrace user to initialised
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>
---
 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 ba964da..3910af4 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 2/3] arm64: stacktrace: Factor out backtrace initialisation

[Mark Rutland]

On Fri, Apr 20, 2018 at 11:46:18AM +0100, Dave Martin wrote:
> Some common code is required by each stacktrace user to initialised
> 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>

Looks like a nice cleanup.

Acked-by: Mark Rutland <mark.rutland@arm.com>

Mark.

> ---
>  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 ba964da..3910af4 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 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 set of valid stacks for
   the context forms a strict hierarchy (e.g., a frame on the task
   stack cannot have an ancestor frame on the IRQ stack because
   task context cannot preempt IRQ handlers etc.)

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.  The stack identifier is represented by an enum
sorted into the correct order for checking stack transition
validity by a simple numeric comparison.  A field stack_id is added
to struct stackframe to track the result of this for the frame.

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

Now that frames can be mapped to a strict lexical order on the
stack id and frame address, forward progress should be guaranteed.

Backtracing now terminates whenever the next frame violates this
order, with kernel entry (with fp == 0 && pc == 0) as a special
case of this.

Reported-by: Ji Zhang <ji.zhang@mediatek.com>
Signed-off-by: Dave Martin <Dave.Martin@arm.com>

---

The assumption that we can place the possible stacks (task, IRQ,
overflow, SDEI) in a strict order is based on a quick review of
entry.S, but I may have this wrong... in which case the approach
proposed in this patch may need tweaking (or may not work at all).
---
 arch/arm64/include/asm/stacktrace.h | 35 +++++++++++++++++++++++++++--------
 arch/arm64/kernel/stacktrace.c      | 16 ++++++++++------
 2 files changed, 37 insertions(+), 14 deletions(-)

diff --git a/arch/arm64/include/asm/stacktrace.h b/arch/arm64/include/asm/stacktrace.h
index c9bef22..fe97ff1 100644
--- a/arch/arm64/include/asm/stacktrace.h
+++ b/arch/arm64/include/asm/stacktrace.h
@@ -24,9 +24,26 @@
 #include <asm/ptrace.h>
 #include <asm/sdei.h>
 
+/*
+ * Set of stacks that a given task may execute on.
+ *
+ * This must be sorted so that if entry A appears before entry B, the
+ * context corresponding to A cannot preempt the context corresponding
+ * to B.  This property is used by the unwinder to verify forward
+ * progress by means of a numeric comparison on this enum.
+ */
+enum arm64_stack_id {
+	ARM64_STACK_NONE,
+	ARM64_STACK_TASK,
+	ARM64_STACK_IRQ,
+	ARM64_STACK_OVERFLOW,
+	ARM64_STACK_SDEI,
+};
+
 struct stackframe {
 	unsigned long fp;
 	unsigned long pc;
+	enum arm64_stack_id stack_id;
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 	int graph;
 #endif
@@ -77,21 +94,22 @@ 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;
+		goto bad;
 	if (on_irq_stack(sp))
-		return true;
+		return ARM64_STACK_IRQ;
 	if (on_overflow_stack(sp))
-		return true;
+		return ARM64_STACK_OVERFLOW;
 	if (on_sdei_stack(sp))
-		return true;
+		return ARM64_STACK_SDEI;
 
-	return false;
+bad:
+	return ARM64_STACK_NONE;
 }
 
 static inline void start_backtrace(struct stackframe *frame,
@@ -100,6 +118,7 @@ static inline void start_backtrace(struct stackframe *frame,
 {
 	frame->fp = fp;
 	frame->pc = pc;
+	frame->stack_id = identify_stack(tsk, fp);
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 	frame.graph = tsk->curr_ret_stack;
 #endif
diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index d5718a0..518ac57 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,12 +77,14 @@ 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 > stack_id ||
+	    (frame->stack_id == stack_id && frame->fp <= fp))
 		return -EINVAL;
 
 	return 0;
-- 
2.1.4

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

[Mark Rutland]

On Fri, Apr 20, 2018 at 11:46:19AM +0100, 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 set of valid stacks for
>    the context forms a strict hierarchy (e.g., a frame on the task
>    stack cannot have an ancestor frame on the IRQ stack because
>    task context cannot preempt IRQ handlers etc.)
> 
> 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.  The stack identifier is represented by an enum
> sorted into the correct order for checking stack transition
> validity by a simple numeric comparison.  A field stack_id is added
> to struct stackframe to track the result of this for the frame.
> 
> Now that it is easy to check whether two successive frames are on
> the same stack, it is easy to add a check for strictly increasing
> frame address, to avoid looping around the same stack.
> 
> Now that frames can be mapped to a strict lexical order on the
> stack id and frame address, forward progress should be guaranteed.
> 
> Backtracing now terminates whenever the next frame violates this
> order, with kernel entry (with fp == 0 && pc == 0) as a special
> case of this.
> 
> Reported-by: Ji Zhang <ji.zhang@mediatek.com>
> Signed-off-by: Dave Martin <Dave.Martin@arm.com>
> 
> ---
> 
> The assumption that we can place the possible stacks (task, IRQ,
> overflow, SDEI) in a strict order is based on a quick review of
> entry.S, but I may have this wrong... in which case the approach
> proposed in this patch may need tweaking (or may not work at all).

We have a partial ordering where we can transition between stacks:

	task -> irq -> {overflow,sdei}

The only problem that I'm aware of is that you could go either way:

	overflow -> sdei
	sdei -> overflow

In either case, there's a fatal error, and it would be very nice to get
the most reliable stacktrace possible rather than terminating early.

The only way I'd thought to avoid that was to keep track of the last SP
we saw per-stack to avoid a lexical ordering, e.g.

struct stackframe {

	...

	/* assume we init these to 0 before unwinding */
	unsigned long last_task_fp;
	unsigned long last_irq_fp;
	unsigned long last_ovf_fp;
	unsigned long last_sdei_fp;
};

... and corresponding when we unwind a frame, do something like:

	if (on_task_stack(task, sp) {
		if (sp < frame->last_task_fp)
			<fail>
		frame->last_task_fp = sp;
	} else if (on_irq_stack(sp)) {
		if (sp < frame->last_irq_fp)
			<fail>
		frame->last_irq_fp = sp;
	} else (...) {
		...
	}
			
Thanks,
Mark.

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

[Dave Martin]

On Fri, Apr 20, 2018 at 11:58:14AM +0100, Mark Rutland wrote:
> On Fri, Apr 20, 2018 at 11:46:19AM +0100, 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 set of valid stacks for
> >    the context forms a strict hierarchy (e.g., a frame on the task
> >    stack cannot have an ancestor frame on the IRQ stack because
> >    task context cannot preempt IRQ handlers etc.)
> > 
> > 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.  The stack identifier is represented by an enum
> > sorted into the correct order for checking stack transition
> > validity by a simple numeric comparison.  A field stack_id is added
> > to struct stackframe to track the result of this for the frame.
> > 
> > Now that it is easy to check whether two successive frames are on
> > the same stack, it is easy to add a check for strictly increasing
> > frame address, to avoid looping around the same stack.
> > 
> > Now that frames can be mapped to a strict lexical order on the
> > stack id and frame address, forward progress should be guaranteed.
> > 
> > Backtracing now terminates whenever the next frame violates this
> > order, with kernel entry (with fp == 0 && pc == 0) as a special
> > case of this.
> > 
> > Reported-by: Ji Zhang <ji.zhang@mediatek.com>
> > Signed-off-by: Dave Martin <Dave.Martin@arm.com>
> > 
> > ---
> > 
> > The assumption that we can place the possible stacks (task, IRQ,
> > overflow, SDEI) in a strict order is based on a quick review of
> > entry.S, but I may have this wrong... in which case the approach
> > proposed in this patch may need tweaking (or may not work at all).
> 
> We have a partial ordering where we can transition between stacks:
> 
> 	task -> irq -> {overflow,sdei}
> 
> The only problem that I'm aware of is that you could go either way:
> 
> 	overflow -> sdei
> 	sdei -> overflow

> In either case, there's a fatal error, and it would be very nice to get
> the most reliable stacktrace possible rather than terminating early.

Agreed, where we must choose between a possibly-incomplete backtrace or
a possibly-incorrect backtrace, we should probably err on the side of
completeness.

To what extent do we claim to cope with recursive stack overflows?
We could get something like

task -> overflow -> irq -> overflow -> sdei -> overflow

(We can also take a single nested SDE, but if the sdei stack already
overflowed I think we're basically dead if that happens here, unless
SDEI checks for this and continues on the overflow stack if that
happens).

> The only way I'd thought to avoid that was to keep track of the last SP
> we saw per-stack to avoid a lexical ordering, e.g.
> 
> struct stackframe {
> 
> 	...
> 
> 	/* assume we init these to 0 before unwinding */
> 	unsigned long last_task_fp;
> 	unsigned long last_irq_fp;
> 	unsigned long last_ovf_fp;
> 	unsigned long last_sdei_fp;
> };

But possibly we only need to track ovf and sdei here, unless I'm
misunderstanding.

If that's right perhaps my approach can be tweaked rather then being
completely unusable, but I'll need to have a think.

> 
> ... and corresponding when we unwind a frame, do something like:
> 
> 	if (on_task_stack(task, sp) {
> 		if (sp < frame->last_task_fp)
> 			<fail>
> 		frame->last_task_fp = sp;
> 	} else if (on_irq_stack(sp)) {
> 		if (sp < frame->last_irq_fp)
> 			<fail>
> 		frame->last_irq_fp = sp;
> 	} else (...) {
> 		...
> 	}

I guess.  I think mine is nicer (of course), but also brokener for
now...

Cheers
---Dave

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

[Mark Rutland]

On Fri, Apr 20, 2018 at 12:19:50PM +0100, Dave Martin wrote:
> On Fri, Apr 20, 2018 at 11:58:14AM +0100, Mark Rutland wrote:
> > On Fri, Apr 20, 2018 at 11:46:19AM +0100, Dave Martin wrote:
> > > The assumption that we can place the possible stacks (task, IRQ,
> > > overflow, SDEI) in a strict order is based on a quick review of
> > > entry.S, but I may have this wrong... in which case the approach
> > > proposed in this patch may need tweaking (or may not work at all).
> > 
> > We have a partial ordering where we can transition between stacks:
> > 
> > 	task -> irq -> {overflow,sdei}
> > 
> > The only problem that I'm aware of is that you could go either way:
> > 
> > 	overflow -> sdei
> > 	sdei -> overflow
> 
> > In either case, there's a fatal error, and it would be very nice to get
> > the most reliable stacktrace possible rather than terminating early.
> 
> Agreed, where we must choose between a possibly-incomplete backtrace or
> a possibly-incorrect backtrace, we should probably err on the side of
> completeness.
> 
> To what extent do we claim to cope with recursive stack overflows?

We don't claim to handle this at all.

If we overflow on the overflow stack, we'll try to reuse the overflow
stack, and things go badly.

We *could* add a per-cpu flag to say already-overflowed, and go into a
WFI loop upon a recursive overflow, but we can't do something reliably
fatal in this case.

> We could get something like
> 
> task -> overflow -> irq -> overflow -> sdei -> overflow

We only transition task -> irq, and not overflow -> irq.

In irq_stack_entry, we only transition to the IRQ stack if we're on a
task stack, so we can't have overflow -> irq.

I believe that the worst case is something like:

task -> irq -> overflow -> sdei -> overflow.

... but at that point we're very much dead, and can't reliably unwind
past the SDEI stack.

We could have flags saying if we've hit a particular stack before, and
when transitioning, abort if we've already been on that stack.

> (We can also take a single nested SDE, but if the sdei stack already
> overflowed I think we're basically dead if that happens here, unless
> SDEI checks for this and continues on the overflow stack if that
> happens).

The overflow handler won't return to the first SDE stack, so that's
fatal, but not much worse than taking a regular SDE while on the
overflow stack.

IIUC to take a nested SDE, the first has to be a normal SDE, and the
second a critical SDE. With VMAP_STACK, those use separate stacks, and
thus the second SDE shouldn't corrupt the contest of the first.

Without VMAP_STACK, the overflow isn't handled reliably anyhow.

Thanks,
Mark.