[PATCH 0/2] ARM: enable dumping stacks for CONFIG_SMP

[PATCH 0/2] ARM: enable dumping stacks for CONFIG_SMP

[Colin Cross]

This topic has come up before, see
http://comments.gmane.org/gmane.linux.ports.arm.kernel/102458
for the previous discussion.

SMP is now the norm for new ARM systems, and the limitation that
CONFIG_STACKTRACE doesn't work for tasks besides 'current' causes
problems.  The particular case I'm dealing with is automated
debugging information collected from /proc/<pid>/stack when
userspace detects a process is not responding.

Dumping stacktraces is currently disabled due to the worry that the
task may be running on another CPU and that the unwinder may be
unstable when presented with a stack that is being modified.  I have
attempted to harden the frame pointer based unwinder and the unwind
table based unwinder against invalid stacks.  I separated the two
into individual patches, as I expect the patch to the table unwinder
to be more controversial than the frame pointer unwinder.

Even without the hardening, unwinding a stack for a running process
is not completely untested.  When CONFIG_ARM_UNWIND is enabled,
sysrq-t calls unwind_backtrace for all tasks including running ones.
In addition, any callers to unwind_frame with preemption enabled,
including proc_pid_stack, could see a modified stack even on a UP
system (pointed out by Rabin Vincent the last time this topic came
up).

 arch/arm/kernel/stacktrace.c |   24 +++++++++++++-----------
 arch/arm/kernel/unwind.c     |   31 +++++++++++++++++++++++++++----
 2 files changed, 40 insertions(+), 15 deletions(-)

[PATCH 1/2] ARM: stacktrace: enable dumping stacks for SMP && FRAME_POINTER

[Colin Cross]

Dumping stacktraces is currently disabled in ARM SMP for all tasks
except the current task due to the worry that the task may be running
on another CPU and that the unwinder may be unstable when presented
with a stack that is being modified.

Unwinding with CONFIG_FRAME_POINTER is fairly simple compared to
when CONFIG_ARM_UNWIND is set.  The next frame's FP and SP registers
are read from the stack and can be validated against the current
values to ensure that they do not leave the stack and make progress
towards the upper end of the stack.  This guarantees that accesses
do not fault and that execution is bounded.

Add additional validations to unwind_frame and enable dumping
stacktraces when CONFIG_SMP is set if CONFIG_FRAME_POINTER is set.

Signed-off-by: Colin Cross <ccross@android.com>
---
 arch/arm/kernel/stacktrace.c |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)

diff --git a/arch/arm/kernel/stacktrace.c b/arch/arm/kernel/stacktrace.c
index 00f79e5..45e6b7e 100644
--- a/arch/arm/kernel/stacktrace.c
+++ b/arch/arm/kernel/stacktrace.c
@@ -34,11 +34,24 @@ int notrace unwind_frame(struct stackframe *frame)
 	if (fp < (low + 12) || fp + 4 >= high)
 		return -EINVAL;
 
+	if (fp % 4 != 0)
+		return -EINVAL;
+
 	/* restore the registers from the stack frame */
 	frame->fp = *(unsigned long *)(fp - 12);
 	frame->sp = *(unsigned long *)(fp - 8);
 	frame->pc = *(unsigned long *)(fp - 4);
 
+	/*
+	 * ensure the next stack pointer is above this one to guarantee
+	 * bounded execution
+	 */
+	if (frame->sp < fp || frame->sp > high)
+		return -EINVAL;
+
+	if (frame->sp % 4 != 0)
+		return -EINVAL;
+
 	return 0;
 }
 #endif
@@ -92,7 +105,8 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
 	data.skip = trace->skip;
 
 	if (tsk != current) {
-#ifdef CONFIG_SMP
+#if defined(CONFIG_SMP) || \
+	(defined(CONFIG_FRAME_POINTER) && !defined(CONFIG_ARM_UNWIND))
 		/*
 		 * What guarantees do we have here that 'tsk' is not
 		 * running on another CPU?  For now, ignore it as we
-- 
1.7.7.3

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Colin Cross]

Unwinding with CONFIG_ARM_UNWIND is much more complicated than
unwinding with CONFIG_FRAME_POINTER, but there are only a few points
that require validation in order to avoid faults or infinite loops.
Avoiding faults is easy by adding checks to verify that all accesses
relative to the frame's stack pointer remain inside the stack.

When CONFIG_FRAME_POINTER is not set it is possible for two frames to
have the same SP, so there is no way to avoid repeated calls to
unwind_frame continuing forever.

Signed-off-by: Colin Cross <ccross@android.com>
---
 arch/arm/kernel/stacktrace.c |   12 ------------
 arch/arm/kernel/unwind.c     |   31 +++++++++++++++++++++++++++----
 2 files changed, 27 insertions(+), 16 deletions(-)

diff --git a/arch/arm/kernel/stacktrace.c b/arch/arm/kernel/stacktrace.c
index 45e6b7e..f51dd68 100644
--- a/arch/arm/kernel/stacktrace.c
+++ b/arch/arm/kernel/stacktrace.c
@@ -105,23 +105,11 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
 	data.skip = trace->skip;
 
 	if (tsk != current) {
-#if defined(CONFIG_SMP) || \
-	(defined(CONFIG_FRAME_POINTER) && !defined(CONFIG_ARM_UNWIND))
-		/*
-		 * What guarantees do we have here that 'tsk' is not
-		 * running on another CPU?  For now, ignore it as we
-		 * can't guarantee we won't explode.
-		 */
-		if (trace->nr_entries < trace->max_entries)
-			trace->entries[trace->nr_entries++] = ULONG_MAX;
-		return;
-#else
 		data.no_sched_functions = 1;
 		frame.fp = thread_saved_fp(tsk);
 		frame.sp = thread_saved_sp(tsk);
 		frame.lr = 0;		/* recovered from the stack */
 		frame.pc = thread_saved_pc(tsk);
-#endif
 	} else {
 		register unsigned long current_sp asm ("sp");
 
diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
 00df012..b3a09ad 100644
--- a/arch/arm/kernel/unwind.c
+++ b/arch/arm/kernel/unwind.c
@@ -98,6 +98,16 @@ enum regs {
 	(unsigned long)(ptr) + offset;			\
 })
 
+static bool valid_stack_addr(unsigned long sp, unsigned long *vsp)
+{
+	unsigned long low;
+	unsigned long high;
+
+	low = round_down(sp, THREAD_SIZE) + sizeof(struct thread_info);
+	high = ALIGN(sp, THREAD_SIZE);
+	return ((unsigned long)vsp >= low && (unsigned long)vsp < high);
+}
+
 /*
  * Binary search in the unwind index. The entries are
  * guaranteed to be sorted in ascending order by the linker.
@@ -241,6 +251,7 @@ static unsigned long unwind_get_byte(struct unwind_ctrl_block *ctrl)
 static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 {
 	unsigned long insn = unwind_get_byte(ctrl);
+	unsigned long orig_sp = ctrl->vrs[SP];
 
 	pr_debug("%s: insn = %08lx\n", __func__, insn);
 
@@ -264,8 +275,11 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 		/* pop R4-R15 according to mask */
 		load_sp = mask & (1 << (13 - 4));
 		while (mask) {
-			if (mask & 1)
+			if (mask & 1) {
+				if (!valid_stack_addr(orig_sp, vsp))
+					return -URC_FAILURE;
 				ctrl->vrs[reg] = *vsp++;
+			}
 			mask >>= 1;
 			reg++;
 		}
@@ -279,10 +293,16 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 		int reg;
 
 		/* pop R4-R[4+bbb] */
-		for (reg = 4; reg <= 4 + (insn & 7); reg++)
+		for (reg = 4; reg <= 4 + (insn & 7); reg++) {
+			if (!valid_stack_addr(orig_sp, vsp))
+				return -URC_FAILURE;
 			ctrl->vrs[reg] = *vsp++;
-		if (insn & 0x80)
+		}
+		if (insn & 0x80) {
+			if (!valid_stack_addr(orig_sp, vsp))
+				return -URC_FAILURE;
 			ctrl->vrs[14] = *vsp++;
+		}
 		ctrl->vrs[SP] = (unsigned long)vsp;
 	} else if (insn == 0xb0) {
 		if (ctrl->vrs[PC] == 0)
@@ -302,8 +322,11 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 
 		/* pop R0-R3 according to mask */
 		while (mask) {
-			if (mask & 1)
+			if (mask & 1) {
+				if (!valid_stack_addr(orig_sp, vsp))
+					return -URC_FAILURE;
 				ctrl->vrs[reg] = *vsp++;
+			}
 			mask >>= 1;
 			reg++;
 		}
-- 
1.7.7.3

[PATCH 0/2] ARM: enable dumping stacks for CONFIG_SMP

[Colin Cross]

On Sun, Aug 26, 2012 at 3:46 PM, Colin Cross <ccross@android.com> wrote:
> This topic has come up before, see
> http://comments.gmane.org/gmane.linux.ports.arm.kernel/102458
> for the previous discussion.
>
> SMP is now the norm for new ARM systems, and the limitation that
> CONFIG_STACKTRACE doesn't work for tasks besides 'current' causes
> problems.  The particular case I'm dealing with is automated
> debugging information collected from /proc/<pid>/stack when
> userspace detects a process is not responding.
>
> Dumping stacktraces is currently disabled due to the worry that the
> task may be running on another CPU and that the unwinder may be
> unstable when presented with a stack that is being modified.  I have
> attempted to harden the frame pointer based unwinder and the unwind
> table based unwinder against invalid stacks.  I separated the two
> into individual patches, as I expect the patch to the table unwinder
> to be more controversial than the frame pointer unwinder.
>
> Even without the hardening, unwinding a stack for a running process
> is not completely untested.  When CONFIG_ARM_UNWIND is enabled,
> sysrq-t calls unwind_backtrace for all tasks including running ones.
> In addition, any callers to unwind_frame with preemption enabled,
> including proc_pid_stack, could see a modified stack even on a UP
> system (pointed out by Rabin Vincent the last time this topic came
> up).
>
>  arch/arm/kernel/stacktrace.c |   24 +++++++++++++-----------
>  arch/arm/kernel/unwind.c     |   31 +++++++++++++++++++++++++++----
>  2 files changed, 40 insertions(+), 15 deletions(-)

I sent this series during Plumbers travel season, so maybe it got
missed.  Any comments?  Enabling stack traces at least for the
CONFIG_ARM_UNWIND=n case would be very helpful for automated bug
report collection.

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Laura Abbott]

Hi,

On 8/26/2012 3:46 PM, Colin Cross wrote:
> Unwinding with CONFIG_ARM_UNWIND is much more complicated than
> unwinding with CONFIG_FRAME_POINTER, but there are only a few points
> that require validation in order to avoid faults or infinite loops.
> Avoiding faults is easy by adding checks to verify that all accesses
> relative to the frame's stack pointer remain inside the stack.
>
> When CONFIG_FRAME_POINTER is not set it is possible for two frames to
> have the same SP, so there is no way to avoid repeated calls to
> unwind_frame continuing forever.
>
> Signed-off-by: Colin Cross <ccross@android.com>
> ---

This is a feature we've wanted for a long time. I ran some test with 
repeated catting of stacks with processes dying and the results looked good.

You can add a Tested-by: Laura Abbott <lauraa@codeaurora.org>

Laura

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted by The Linux Foundation

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Russell King - ARM Linux]

On Sun, Aug 26, 2012 at 03:46:56PM -0700, Colin Cross wrote:
> Unwinding with CONFIG_ARM_UNWIND is much more complicated than
> unwinding with CONFIG_FRAME_POINTER, but there are only a few points
> that require validation in order to avoid faults or infinite loops.
> Avoiding faults is easy by adding checks to verify that all accesses
> relative to the frame's stack pointer remain inside the stack.
> 
> When CONFIG_FRAME_POINTER is not set it is possible for two frames to
> have the same SP, so there is no way to avoid repeated calls to
> unwind_frame continuing forever.

So here you admit that this patch can cause the unwinder to loop forever,
which would provide no way out of that.  Why do you think this patch is
suitable for mainline with such a problem?

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Dave Martin]

On Fri, Oct 12, 2012 at 10:08:07AM +0100, Russell King - ARM Linux wrote:
> On Sun, Aug 26, 2012 at 03:46:56PM -0700, Colin Cross wrote:
> > Unwinding with CONFIG_ARM_UNWIND is much more complicated than
> > unwinding with CONFIG_FRAME_POINTER, but there are only a few points
> > that require validation in order to avoid faults or infinite loops.
> > Avoiding faults is easy by adding checks to verify that all accesses
> > relative to the frame's stack pointer remain inside the stack.
> > 
> > When CONFIG_FRAME_POINTER is not set it is possible for two frames to
> > have the same SP, so there is no way to avoid repeated calls to
> > unwind_frame continuing forever.
> 
> So here you admit that this patch can cause the unwinder to loop forever,
> which would provide no way out of that.  Why do you think this patch is
> suitable for mainline with such a problem?

With CONFIG_FRAME_POINTER we have a straightforward definition of
progress: the sp must increase per frame, and cannot increase beyond the
limit of the tasks stack.  We get this property from the fact that
each frame record consumes actual space on the stack.  If we parse a
frame record which does not both increase the sp and provide a frame
address greater than that sp, we know that frame is garbage and we must
stop.


With CONFIG_ARM_UNWIND, we have no straightforward definition of
progress.  However, sp must _normally_ still increase, because compiler-
generated non-leaf functions must store the lr somewhere, and the
compiler always uses the stack.  Even if lr is stashed in r4, an ABI
compliant would then have needed to save r4 on the stack beforehand.

We can assume that we will never parse a garbage unwind table because of
the way the table lookup works (though we may parse a valid table which
has nothing whatever to do with the code that was executing in the case
of a corrupted stack).  So we only need to worry about what the unwind
tables will look like for valid functions.

Nonetheless, tail-call-optimised and manually-annotated functions may
have unusual frames which don't consume any stack.  Stackless tail-
call-optimised functions shouldn't be a problem, since their frames
are completely missing from the backtrace and won't dump us into a loop.
Stackless assembler functions are overwhelmingly likely to be leaf
functions, giving us just one stackless frame.


Would it make sense if we place some small sanity limit on the number
of frames the unwinder will process with the same sp before giving up?

Cheers
---Dave

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Colin Cross]

On Fri, Oct 12, 2012 at 3:02 AM, Dave Martin <dave.martin@linaro.org> wrote:
> On Fri, Oct 12, 2012 at 10:08:07AM +0100, Russell King - ARM Linux wrote:
>> On Sun, Aug 26, 2012 at 03:46:56PM -0700, Colin Cross wrote:
>> > Unwinding with CONFIG_ARM_UNWIND is much more complicated than
>> > unwinding with CONFIG_FRAME_POINTER, but there are only a few points
>> > that require validation in order to avoid faults or infinite loops.
>> > Avoiding faults is easy by adding checks to verify that all accesses
>> > relative to the frame's stack pointer remain inside the stack.
>> >
>> > When CONFIG_FRAME_POINTER is not set it is possible for two frames to
>> > have the same SP, so there is no way to avoid repeated calls to
>> > unwind_frame continuing forever.
>>
>> So here you admit that this patch can cause the unwinder to loop forever,
>> which would provide no way out of that.  Why do you think this patch is
>> suitable for mainline with such a problem?
>
> With CONFIG_FRAME_POINTER we have a straightforward definition of
> progress: the sp must increase per frame, and cannot increase beyond the
> limit of the tasks stack.  We get this property from the fact that
> each frame record consumes actual space on the stack.  If we parse a
> frame record which does not both increase the sp and provide a frame
> address greater than that sp, we know that frame is garbage and we must
> stop.
>
>
> With CONFIG_ARM_UNWIND, we have no straightforward definition of
> progress.  However, sp must _normally_ still increase, because compiler-
> generated non-leaf functions must store the lr somewhere, and the
> compiler always uses the stack.  Even if lr is stashed in r4, an ABI
> compliant would then have needed to save r4 on the stack beforehand.
>
> We can assume that we will never parse a garbage unwind table because of
> the way the table lookup works (though we may parse a valid table which
> has nothing whatever to do with the code that was executing in the case
> of a corrupted stack).  So we only need to worry about what the unwind
> tables will look like for valid functions.
>
> Nonetheless, tail-call-optimised and manually-annotated functions may
> have unusual frames which don't consume any stack.  Stackless tail-
> call-optimised functions shouldn't be a problem, since their frames
> are completely missing from the backtrace and won't dump us into a loop.
> Stackless assembler functions are overwhelmingly likely to be leaf
> functions, giving us just one stackless frame.
>
>
> Would it make sense if we place some small sanity limit on the number
> of frames the unwinder will process with the same sp before giving up?

About half the callers to unwind_frame end up limiting the number of
frames they will follow before giving up, so I wasn't sure if I should
put an arbitrary limit in unwind_frame or just make sure all callers
are bounded.  Your idea of limiting same sp frames instead of total
frames sounds better.  I can send a new patch that adds a new field to
struct stackframe (which will need to be initialized everywhere, the
struct is usually on the stack) and limits the recursion.  Any
suggestion on the recursion limit?  I would never expect to see a real
situation with more than a few, but on the other hand parsing the
frames should be pretty fast so a high number (100?) shouldn't cause
any user visible effect.

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Dave Martin]

On Mon, Oct 15, 2012 at 07:15:31PM -0700, Colin Cross wrote:
> On Fri, Oct 12, 2012 at 3:02 AM, Dave Martin <dave.martin@linaro.org> wrote:
> > On Fri, Oct 12, 2012 at 10:08:07AM +0100, Russell King - ARM Linux wrote:
> >> On Sun, Aug 26, 2012 at 03:46:56PM -0700, Colin Cross wrote:
> >> > Unwinding with CONFIG_ARM_UNWIND is much more complicated than
> >> > unwinding with CONFIG_FRAME_POINTER, but there are only a few points
> >> > that require validation in order to avoid faults or infinite loops.
> >> > Avoiding faults is easy by adding checks to verify that all accesses
> >> > relative to the frame's stack pointer remain inside the stack.
> >> >
> >> > When CONFIG_FRAME_POINTER is not set it is possible for two frames to
> >> > have the same SP, so there is no way to avoid repeated calls to
> >> > unwind_frame continuing forever.
> >>
> >> So here you admit that this patch can cause the unwinder to loop forever,
> >> which would provide no way out of that.  Why do you think this patch is
> >> suitable for mainline with such a problem?
> >
> > With CONFIG_FRAME_POINTER we have a straightforward definition of
> > progress: the sp must increase per frame, and cannot increase beyond the
> > limit of the tasks stack.  We get this property from the fact that
> > each frame record consumes actual space on the stack.  If we parse a
> > frame record which does not both increase the sp and provide a frame
> > address greater than that sp, we know that frame is garbage and we must
> > stop.
> >
> >
> > With CONFIG_ARM_UNWIND, we have no straightforward definition of
> > progress.  However, sp must _normally_ still increase, because compiler-
> > generated non-leaf functions must store the lr somewhere, and the
> > compiler always uses the stack.  Even if lr is stashed in r4, an ABI
> > compliant would then have needed to save r4 on the stack beforehand.
> >
> > We can assume that we will never parse a garbage unwind table because of
> > the way the table lookup works (though we may parse a valid table which
> > has nothing whatever to do with the code that was executing in the case
> > of a corrupted stack).  So we only need to worry about what the unwind
> > tables will look like for valid functions.
> >
> > Nonetheless, tail-call-optimised and manually-annotated functions may
> > have unusual frames which don't consume any stack.  Stackless tail-
> > call-optimised functions shouldn't be a problem, since their frames
> > are completely missing from the backtrace and won't dump us into a loop.
> > Stackless assembler functions are overwhelmingly likely to be leaf
> > functions, giving us just one stackless frame.
> >
> >
> > Would it make sense if we place some small sanity limit on the number
> > of frames the unwinder will process with the same sp before giving up?
> 
> About half the callers to unwind_frame end up limiting the number of
> frames they will follow before giving up, so I wasn't sure if I should
> put an arbitrary limit in unwind_frame or just make sure all callers
> are bounded.  Your idea of limiting same sp frames instead of total
> frames sounds better.  I can send a new patch that adds a new field to
> struct stackframe (which will need to be initialized everywhere, the
> struct is usually on the stack) and limits the recursion.  Any
> suggestion on the recursion limit?  I would never expect to see a real
> situation with more than a few, but on the other hand parsing the
> frames should be pretty fast so a high number (100?) shouldn't cause
> any user visible effect.

Talking to some tools guys about this, it sounds like there really
shouldn't be any stackless frame except for the leaf frame.  If there are
stackless functions they will probably not be visible in the frame chain
at all.  So it might make sense to have a pretty small limit.  Maybe it
could even be 1.  Cartainly a small number.

We should also add a check for whether the current and frame and previous
frame appear identical and abort if that's the case, if we don't do that
already.

Cheers
---Dave

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Russell King - ARM Linux]

On Tue, Oct 16, 2012 at 11:12:01AM +0100, Dave Martin wrote:
> On Mon, Oct 15, 2012 at 07:15:31PM -0700, Colin Cross wrote:
> > About half the callers to unwind_frame end up limiting the number of
> > frames they will follow before giving up, so I wasn't sure if I should
> > put an arbitrary limit in unwind_frame or just make sure all callers
> > are bounded.  Your idea of limiting same sp frames instead of total
> > frames sounds better.  I can send a new patch that adds a new field to
> > struct stackframe (which will need to be initialized everywhere, the
> > struct is usually on the stack) and limits the recursion.  Any
> > suggestion on the recursion limit?  I would never expect to see a real
> > situation with more than a few, but on the other hand parsing the
> > frames should be pretty fast so a high number (100?) shouldn't cause
> > any user visible effect.
> 
> Talking to some tools guys about this, it sounds like there really
> shouldn't be any stackless frame except for the leaf frame.  If there are
> stackless functions they will probably not be visible in the frame chain
> at all.  So it might make sense to have a pretty small limit.  Maybe it
> could even be 1.  Cartainly a small number.
> 
> We should also add a check for whether the current and frame and previous
> frame appear identical and abort if that's the case, if we don't do that
> already.

The case that actually worries me is not the "end up looping for ever"
case, but the effects of having the stack change while the unwinder is
reading from it - for example:

                /* pop R4-R15 according to mask */
                load_sp = mask & (1 << (13 - 4));
                while (mask) {
                        if (mask & 1)
                                ctrl->vrs[reg] = *vsp++;
                        mask >>= 1;
                        reg++;
                }

Remember that for a running thread, the stack will be changing all the
time while another CPU tries to read it to do the unwind, and also
remember that the bottom of stack isn't really known.  All you have is
the snapshot of the registers when the thread was last stopped by the
scheduler, and that state probably isn't valid.

So what you're asking is for the unwinder to produce a backtrace from
a kernel stack which is possibly changing beneath it from an unknown
current state.

This doesn't sound like a particularly bright thing to be doing...

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Dave Martin]

On Tue, Oct 16, 2012 at 11:55:04AM +0100, Russell King - ARM Linux wrote:
> On Tue, Oct 16, 2012 at 11:12:01AM +0100, Dave Martin wrote:
> > On Mon, Oct 15, 2012 at 07:15:31PM -0700, Colin Cross wrote:
> > > About half the callers to unwind_frame end up limiting the number of
> > > frames they will follow before giving up, so I wasn't sure if I should
> > > put an arbitrary limit in unwind_frame or just make sure all callers
> > > are bounded.  Your idea of limiting same sp frames instead of total
> > > frames sounds better.  I can send a new patch that adds a new field to
> > > struct stackframe (which will need to be initialized everywhere, the
> > > struct is usually on the stack) and limits the recursion.  Any
> > > suggestion on the recursion limit?  I would never expect to see a real
> > > situation with more than a few, but on the other hand parsing the
> > > frames should be pretty fast so a high number (100?) shouldn't cause
> > > any user visible effect.
> > 
> > Talking to some tools guys about this, it sounds like there really
> > shouldn't be any stackless frame except for the leaf frame.  If there are
> > stackless functions they will probably not be visible in the frame chain
> > at all.  So it might make sense to have a pretty small limit.  Maybe it
> > could even be 1.  Cartainly a small number.
> > 
> > We should also add a check for whether the current and frame and previous
> > frame appear identical and abort if that's the case, if we don't do that
> > already.
> 
> The case that actually worries me is not the "end up looping for ever"
> case, but the effects of having the stack change while the unwinder is
> reading from it - for example:
> 
>                 /* pop R4-R15 according to mask */
>                 load_sp = mask & (1 << (13 - 4));
>                 while (mask) {
>                         if (mask & 1)
>                                 ctrl->vrs[reg] = *vsp++;
>                         mask >>= 1;
>                         reg++;
>                 }
> 
> Remember that for a running thread, the stack will be changing all the
> time while another CPU tries to read it to do the unwind, and also
> remember that the bottom of stack isn't really known.  All you have is
> the snapshot of the registers when the thread was last stopped by the
> scheduler, and that state probably isn't valid.

So long as the unwinder enforces continuous progress towards a fixed
limit, sooner or later the supposed bottom of the stack will be reached,
or the unwinder will encounter something which is recognised as garbage
and stop.

This the best we can hope for if trying to print a backtrace for a
thread without stopping it...  which admittedly seems quite a dodgy
thing to attempt.

Colin, what are the scenarios when we want to backtrace a thread while
it is actually running?

> So what you're asking is for the unwinder to produce a backtrace from
> a kernel stack which is possibly changing beneath it from an unknown
> current state.
> 
> This doesn't sound like a particularly bright thing to be doing...

Nonetheless, the changes are relevant to normal stack dumping too, since
when we take a fault the sp or stack may be corrupted, even if the
thread in question is stopped.  Being more robust against infinte loops
etc., still seems like a good idea ?

Cheers
---Dave

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Colin Cross]

On Tue, Oct 16, 2012 at 3:55 AM, Russell King - ARM Linux
<linux@arm.linux.org.uk> wrote:
> On Tue, Oct 16, 2012 at 11:12:01AM +0100, Dave Martin wrote:
>> On Mon, Oct 15, 2012 at 07:15:31PM -0700, Colin Cross wrote:
>> > About half the callers to unwind_frame end up limiting the number of
>> > frames they will follow before giving up, so I wasn't sure if I should
>> > put an arbitrary limit in unwind_frame or just make sure all callers
>> > are bounded.  Your idea of limiting same sp frames instead of total
>> > frames sounds better.  I can send a new patch that adds a new field to
>> > struct stackframe (which will need to be initialized everywhere, the
>> > struct is usually on the stack) and limits the recursion.  Any
>> > suggestion on the recursion limit?  I would never expect to see a real
>> > situation with more than a few, but on the other hand parsing the
>> > frames should be pretty fast so a high number (100?) shouldn't cause
>> > any user visible effect.
>>
>> Talking to some tools guys about this, it sounds like there really
>> shouldn't be any stackless frame except for the leaf frame.  If there are
>> stackless functions they will probably not be visible in the frame chain
>> at all.  So it might make sense to have a pretty small limit.  Maybe it
>> could even be 1.  Cartainly a small number.
>>
>> We should also add a check for whether the current and frame and previous
>> frame appear identical and abort if that's the case, if we don't do that
>> already.
>
> The case that actually worries me is not the "end up looping for ever"
> case, but the effects of having the stack change while the unwinder is
> reading from it - for example:
>
>                 /* pop R4-R15 according to mask */
>                 load_sp = mask & (1 << (13 - 4));
>                 while (mask) {
>                         if (mask & 1)
>                                 ctrl->vrs[reg] = *vsp++;
>                         mask >>= 1;
>                         reg++;
>                 }
>
> Remember that for a running thread, the stack will be changing all the
> time while another CPU tries to read it to do the unwind, and also
> remember that the bottom of stack isn't really known.  All you have is
> the snapshot of the registers when the thread was last stopped by the
> scheduler, and that state probably isn't valid.

If the snapshot of the registers when the thread was last stopped
includes an sp that points somewhere in two contiguous pages of low
memory, I don't see a problem.  From the sp we can get the bounds of
the stack (see the valid_stack_addr function I added), and we can make
sure the unwinder never dereferences anything outside of that stack,
so it will never fault.  We can also make sure that the sp stays
within that stack between frames, and moves in the right direction, so
it will never loop (except for the leaf-node sp issue, which Dave
Martin's idea will address).

> So what you're asking is for the unwinder to produce a backtrace from
> a kernel stack which is possibly changing beneath it from an unknown
> current state.

I don't think the stack changing is relevant.  With my modifications,
the unwinder can handle an invalid value at any place in the stack
without looping or crashing, and it doesn't matter if it is invalid
due to changing or permanent stack corruption.  The worst it will do
is produce a partial stack trace that ends with an invalid value.  For
example:

shell@:/ # dd if=/dev/urandom of=/dev/null bs=1000000 count=1000000 &
[1] 2709
130|shell@:/ # while true; do cat /proc/2709/stack; echo ---; done
[<c00084d4>] gic_handle_irq+0x24/0x58
[<c000e580>] __irq_svc+0x40/0x70
[<ffffffff>] 0xffffffff
---
[<00000099>] 0x99
[<ffffffff>] 0xffffffff
---
[<c0039728>] irq_exit+0x7c/0x98
[<c000f888>] handle_IRQ+0x50/0xac
[<c00084d4>] gic_handle_irq+0x24/0x58
[<00000014>] 0x14
[<ffffffff>] 0xffffffff
---
[<c087ac40>] rcu_preempt_state+0x0/0x140
[<ffffffff>] 0xffffffff
---
[<c00084d4>] gic_handle_irq+0x24/0x58
[<c000e580>] __irq_svc+0x40/0x70
[<ffffffff>] 0xffffffff
---
[<60000013>] 0x60000013
[<ffffffff>] 0xffffffff
---
[<d79ce000>] 0xd79ce000
[<ffffffff>] 0xffffffff

> This doesn't sound like a particularly bright thing to be doing...

As discussed previously, this already happens, has anyone ever
reported it as a problem?  Sysrq-t dumps all stacks by calling
dump_backtrace(), which bypasses the check for tsk == current.  And
any caller to unwind_backtrace with preemption on can see a changing
stack, even on UP.

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Colin Cross]

On Tue, Oct 16, 2012 at 5:26 AM, Dave Martin <dave.martin@linaro.org> wrote:
> On Tue, Oct 16, 2012 at 11:55:04AM +0100, Russell King - ARM Linux wrote:
>> On Tue, Oct 16, 2012 at 11:12:01AM +0100, Dave Martin wrote:
>> > On Mon, Oct 15, 2012 at 07:15:31PM -0700, Colin Cross wrote:
>> > > About half the callers to unwind_frame end up limiting the number of
>> > > frames they will follow before giving up, so I wasn't sure if I should
>> > > put an arbitrary limit in unwind_frame or just make sure all callers
>> > > are bounded.  Your idea of limiting same sp frames instead of total
>> > > frames sounds better.  I can send a new patch that adds a new field to
>> > > struct stackframe (which will need to be initialized everywhere, the
>> > > struct is usually on the stack) and limits the recursion.  Any
>> > > suggestion on the recursion limit?  I would never expect to see a real
>> > > situation with more than a few, but on the other hand parsing the
>> > > frames should be pretty fast so a high number (100?) shouldn't cause
>> > > any user visible effect.
>> >
>> > Talking to some tools guys about this, it sounds like there really
>> > shouldn't be any stackless frame except for the leaf frame.  If there are
>> > stackless functions they will probably not be visible in the frame chain
>> > at all.  So it might make sense to have a pretty small limit.  Maybe it
>> > could even be 1.  Cartainly a small number.
>> >
>> > We should also add a check for whether the current and frame and previous
>> > frame appear identical and abort if that's the case, if we don't do that
>> > already.
>>
>> The case that actually worries me is not the "end up looping for ever"
>> case, but the effects of having the stack change while the unwinder is
>> reading from it - for example:
>>
>>                 /* pop R4-R15 according to mask */
>>                 load_sp = mask & (1 << (13 - 4));
>>                 while (mask) {
>>                         if (mask & 1)
>>                                 ctrl->vrs[reg] = *vsp++;
>>                         mask >>= 1;
>>                         reg++;
>>                 }
>>
>> Remember that for a running thread, the stack will be changing all the
>> time while another CPU tries to read it to do the unwind, and also
>> remember that the bottom of stack isn't really known.  All you have is
>> the snapshot of the registers when the thread was last stopped by the
>> scheduler, and that state probably isn't valid.
>
> So long as the unwinder enforces continuous progress towards a fixed
> limit, sooner or later the supposed bottom of the stack will be reached,
> or the unwinder will encounter something which is recognised as garbage
> and stop.
>
> This the best we can hope for if trying to print a backtrace for a
> thread without stopping it...  which admittedly seems quite a dodgy
> thing to attempt.
>
> Colin, what are the scenarios when we want to backtrace a thread while
> it is actually running?

There is no case where I want a backtrace from a running thread other
than current, but there is no way to guarantee that the thread won't
start running unless we stick it in the freezer, which has other
problems.  The main use case is dumping /proc/pid/stack for all
threads in the process when the thread is deadlocked.  Most likely
none of them will be running, and if they are running I don't care
about the stack.

If the unwinder is made safe against running tasks,
save_stack_trace_tsk could print an error if the task is running
(because it has no idea when it will stop running), then capture the
stack and test that the thread is still not running and the number of
context switches on the task hasn't increased, otherwise retry.  That
way we'll get an error from a running task, but still be able to dump
blocked tasks that are not current.  It still relies on being able to
call unwind_frame on a possibly invalid stack.

>> So what you're asking is for the unwinder to produce a backtrace from
>> a kernel stack which is possibly changing beneath it from an unknown
>> current state.
>>
>> This doesn't sound like a particularly bright thing to be doing...
>
> Nonetheless, the changes are relevant to normal stack dumping too, since
> when we take a fault the sp or stack may be corrupted, even if the
> thread in question is stopped.  Being more robust against infinte loops
> etc., still seems like a good idea ?

I can split out the unwind_frame hardening from the
save_stack_trace_tsk part if you only want that part, and I'll put the
save_stack_trace_tsk chunk in the Android tree.

[PATCH 2/2] ARM: unwind: enable dumping stacks for SMP && ARM_UNWIND

[Dave Martin]

On Tue, Oct 16, 2012 at 02:30:20PM -0700, Colin Cross wrote:
> On Tue, Oct 16, 2012 at 3:55 AM, Russell King - ARM Linux
> <linux@arm.linux.org.uk> wrote:
> > On Tue, Oct 16, 2012 at 11:12:01AM +0100, Dave Martin wrote:
> >> On Mon, Oct 15, 2012 at 07:15:31PM -0700, Colin Cross wrote:
> >> > About half the callers to unwind_frame end up limiting the number of
> >> > frames they will follow before giving up, so I wasn't sure if I should
> >> > put an arbitrary limit in unwind_frame or just make sure all callers
> >> > are bounded.  Your idea of limiting same sp frames instead of total
> >> > frames sounds better.  I can send a new patch that adds a new field to
> >> > struct stackframe (which will need to be initialized everywhere, the
> >> > struct is usually on the stack) and limits the recursion.  Any
> >> > suggestion on the recursion limit?  I would never expect to see a real
> >> > situation with more than a few, but on the other hand parsing the
> >> > frames should be pretty fast so a high number (100?) shouldn't cause
> >> > any user visible effect.
> >>
> >> Talking to some tools guys about this, it sounds like there really
> >> shouldn't be any stackless frame except for the leaf frame.  If there are
> >> stackless functions they will probably not be visible in the frame chain
> >> at all.  So it might make sense to have a pretty small limit.  Maybe it
> >> could even be 1.  Cartainly a small number.
> >>
> >> We should also add a check for whether the current and frame and previous
> >> frame appear identical and abort if that's the case, if we don't do that
> >> already.
> >
> > The case that actually worries me is not the "end up looping for ever"
> > case, but the effects of having the stack change while the unwinder is
> > reading from it - for example:
> >
> >                 /* pop R4-R15 according to mask */
> >                 load_sp = mask & (1 << (13 - 4));
> >                 while (mask) {
> >                         if (mask & 1)
> >                                 ctrl->vrs[reg] = *vsp++;
> >                         mask >>= 1;
> >                         reg++;
> >                 }
> >
> > Remember that for a running thread, the stack will be changing all the
> > time while another CPU tries to read it to do the unwind, and also
> > remember that the bottom of stack isn't really known.  All you have is
> > the snapshot of the registers when the thread was last stopped by the
> > scheduler, and that state probably isn't valid.
> 
> If the snapshot of the registers when the thread was last stopped
> includes an sp that points somewhere in two contiguous pages of low
> memory, I don't see a problem.  From the sp we can get the bounds of
> the stack (see the valid_stack_addr function I added), and we can make
> sure the unwinder never dereferences anything outside of that stack,
> so it will never fault.  We can also make sure that the sp stays
> within that stack between frames, and moves in the right direction, so
> it will never loop (except for the leaf-node sp issue, which Dave
> Martin's idea will address).
> 
> > So what you're asking is for the unwinder to produce a backtrace from
> > a kernel stack which is possibly changing beneath it from an unknown
> > current state.
> 
> I don't think the stack changing is relevant.  With my modifications,
> the unwinder can handle an invalid value at any place in the stack
> without looping or crashing, and it doesn't matter if it is invalid
> due to changing or permanent stack corruption.  The worst it will do
> is produce a partial stack trace that ends with an invalid value.  For
> example:
> 
> shell@:/ # dd if=/dev/urandom of=/dev/null bs=1000000 count=1000000 &
> [1] 2709
> 130|shell@:/ # while true; do cat /proc/2709/stack; echo ---; done
> [<c00084d4>] gic_handle_irq+0x24/0x58
> [<c000e580>] __irq_svc+0x40/0x70
> [<ffffffff>] 0xffffffff
> ---
> [<00000099>] 0x99
> [<ffffffff>] 0xffffffff
> ---
> [<c0039728>] irq_exit+0x7c/0x98
> [<c000f888>] handle_IRQ+0x50/0xac
> [<c00084d4>] gic_handle_irq+0x24/0x58
> [<00000014>] 0x14
> [<ffffffff>] 0xffffffff
> ---
> [<c087ac40>] rcu_preempt_state+0x0/0x140
> [<ffffffff>] 0xffffffff
> ---
> [<c00084d4>] gic_handle_irq+0x24/0x58
> [<c000e580>] __irq_svc+0x40/0x70
> [<ffffffff>] 0xffffffff
> ---
> [<60000013>] 0x60000013
> [<ffffffff>] 0xffffffff
> ---
> [<d79ce000>] 0xd79ce000
> [<ffffffff>] 0xffffffff
> 
> > This doesn't sound like a particularly bright thing to be doing...
> 
> As discussed previously, this already happens, has anyone ever
> reported it as a problem?  Sysrq-t dumps all stacks by calling
> dump_backtrace(), which bypasses the check for tsk == current.  And
> any caller to unwind_backtrace with preemption on can see a changing
> stack, even on UP.

I think I agree with that view: so long as we are just adding robustness
against garbage stacks I think the proposed changes are useful anyway.
A changing stack is just one kind of garbage.  We don't have to guarantee
a sensible backtrace in that case, so long as the unwinder executes
safely and doesn't loop.

Cheers
---Dave