Make the 32 bit Frame Pointer backtracer fall back to traditional

Make the 32 bit Frame Pointer backtracer fall back to traditional

[Arjan van de Ven]

Subject: Make the 32 bit Frame Pointer backtracer fall back to traditional
From: Arjan van de Ven <arjan@linux.intel.com>

The 32 bit Frame Pointer backtracer code checks if the EBP is valid
to do a backtrace; however currently on a failure it just gives up
and prints nothing. That's not very nice; we can do better and still
print a decent backtrace. 

This patch changes the backtracer to fall back to the non-framepointer
backtracer if the EBP value isn't within the expected range; so on weird
stack corruption cases we get at least something out...

Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>

---
 arch/x86/kernel/traps_32.c |   43 ++++++++++++++++++++++---------------------
 1 file changed, 22 insertions(+), 21 deletions(-)

Index: linux-2.6.24-rc7/arch/x86/kernel/traps_32.c
===================================================================
--- linux-2.6.24-rc7.orig/arch/x86/kernel/traps_32.c
+++ linux-2.6.24-rc7/arch/x86/kernel/traps_32.c
@@ -119,26 +119,28 @@ static inline unsigned long print_contex
 {
 #ifdef	CONFIG_FRAME_POINTER
 	struct stack_frame *frame = (struct stack_frame *)ebp;
-	while (valid_stack_ptr(tinfo, frame, sizeof(*frame))) {
-		struct stack_frame *next;
-		unsigned long addr;
-
-		addr = frame->return_address;
-		if (__kernel_text_address(addr))
-			ops->address(data, addr);
-		/*
-		 * break out of recursive entries (such as
-		 * end_of_stack_stop_unwind_function). Also,
-		 * we can never allow a frame pointer to
-		 * move downwards!
-		 */
-		next = frame->next_frame;
-		ebp = (unsigned long) next;
-		if (next <= frame)
-			break;
-		frame = next;
-	}
-#else
+	if (valid_stack_ptr(tinfo, frame, sizeof(*frame)))
+		while (valid_stack_ptr(tinfo, frame, sizeof(*frame))) {
+			struct stack_frame *next;
+			unsigned long addr;
+
+			addr = frame->return_address;
+			if (__kernel_text_address(addr))
+				ops->address(data, addr);
+			/*
+			 * break out of recursive entries (such as
+			 * end_of_stack_stop_unwind_function). Also,
+			 * we can never allow a frame pointer to
+			 * move downwards!
+			 */
+			next = frame->next_frame;
+			ebp = (unsigned long) next;
+			if (next <= frame)
+				break;
+			frame = next;
+		}
+	else
+#endif
 	while (valid_stack_ptr(tinfo, stack, sizeof(*stack))) {
 		unsigned long addr;
 
@@ -146,7 +148,6 @@ static inline unsigned long print_contex
 		if (__kernel_text_address(addr))
 			ops->address(data, addr);
 	}
-#endif
 	return ebp;
 }
 

-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Harvey Harrison]

On Wed, 2008-01-09 at 22:05 -0800, Arjan van de Ven wrote:
> Subject: Make the 32 bit Frame Pointer backtracer fall back to traditional
> From: Arjan van de Ven <arjan@linux.intel.com>
> 
> The 32 bit Frame Pointer backtracer code checks if the EBP is valid
> to do a backtrace; however currently on a failure it just gives up
> and prints nothing. That's not very nice; we can do better and still
> print a decent backtrace. 
> 
> This patch changes the backtracer to fall back to the non-framepointer
> backtracer if the EBP value isn't within the expected range; so on weird
> stack corruption cases we get at least something out...
> 

Arjan, I've been doing some work on traps_32.c porting over the
oops_begin()/oops_end()/_die() arrangement from traps_64.c and
then use it in unifying some more parts of fault.c.

If you have other work in this area, I'll hold off until your stuff
goes in...feel free to send me any work in progress stuff and I can
try to coordinate with you.

Harvey

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Ingo Molnar]

* Arjan van de Ven <arjan@infradead.org> wrote:

> Subject: Make the 32 bit Frame Pointer backtracer fall back to traditional
> From: Arjan van de Ven <arjan@linux.intel.com>
> 
> The 32 bit Frame Pointer backtracer code checks if the EBP is valid to 
> do a backtrace; however currently on a failure it just gives up and 
> prints nothing. That's not very nice; we can do better and still print 
> a decent backtrace.
> 
> This patch changes the backtracer to fall back to the non-framepointer 
> backtracer if the EBP value isn't within the expected range; so on 
> weird stack corruption cases we get at least something out...

thanks, applied. Another nice catch!

	Ingo

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Ingo Molnar]

* Harvey Harrison <harvey.harrison@gmail.com> wrote:

> On Wed, 2008-01-09 at 22:05 -0800, Arjan van de Ven wrote:
> > Subject: Make the 32 bit Frame Pointer backtracer fall back to traditional
> > From: Arjan van de Ven <arjan@linux.intel.com>
> > 
> > The 32 bit Frame Pointer backtracer code checks if the EBP is valid
> > to do a backtrace; however currently on a failure it just gives up
> > and prints nothing. That's not very nice; we can do better and still
> > print a decent backtrace. 
> > 
> > This patch changes the backtracer to fall back to the non-framepointer
> > backtracer if the EBP value isn't within the expected range; so on weird
> > stack corruption cases we get at least something out...
> > 
> 
> Arjan, I've been doing some work on traps_32.c porting over the 
> oops_begin()/oops_end()/_die() arrangement from traps_64.c and then 
> use it in unifying some more parts of fault.c.

i've got that applied and it did not seem to interact with Arjan's code.

> If you have other work in this area, I'll hold off until your stuff 
> goes in...feel free to send me any work in progress stuff and I can 
> try to coordinate with you.

i'll yell if anything clashes.

	Ingo

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Arjan van de Ven]

On Thu, 10 Jan 2008 13:46:06 +0100
Ingo Molnar <mingo@elte.hu> wrote:

> > Arjan, I've been doing some work on traps_32.c porting over the 
> > oops_begin()/oops_end()/_die() arrangement from traps_64.c and then 
> > use it in unifying some more parts of fault.c.
> 
> i've got that applied and it did not seem to interact with Arjan's
> code.
> 
> > If you have other work in this area, I'll hold off until your stuff 
> > goes in...feel free to send me any work in progress stuff and I can 
> > try to coordinate with you.
> 
> i'll yell if anything clashes.


I have a few outstanding things but just go ahead; if you get there first I'll
resolve conflicts, if I get there first.. you'll have to ;-) It's not a big deal,
I'm trying to keep my changes to these areas really self contained small steps
because of the fragility (and because it's just a good idea in general), so any
clashes should also be easy to resolve either way

-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Linus Torvalds]

On Wed, 9 Jan 2008, Arjan van de Ven wrote:
>
> +	if (valid_stack_ptr(tinfo, frame, sizeof(*frame)))
> +		while (valid_stack_ptr(tinfo, frame, sizeof(*frame))) {

Why?

Why not just make this something like the appended instead?

This is *totally* untested, but the basic notion is very simple: start off 
using the frame pointer until it is no longer valid (for any reason - 
whether the return address is corrupt, or the next frame info is bad), and 
update the stack pointer a you go.

When we've run out of frame pointers, we then scan any remaining stack the 
oldfashioned way, regardless of what happened. No unnecessary conditionals 
that will just mean that we don't show enough of the stack if *part* of it 
is corrupt.

The code is simpler and more robust (assuming it works - as mentioned, I 
didn't actually test it, so there may be some stupid thinko there).

		Linus

---
 arch/x86/kernel/traps_32.c |   27 +++++++++++++++------------
 1 files changed, 15 insertions(+), 12 deletions(-)

diff --git a/arch/x86/kernel/traps_32.c b/arch/x86/kernel/traps_32.c
index c88bbff..36714d7 100644
--- a/arch/x86/kernel/traps_32.c
+++ b/arch/x86/kernel/traps_32.c
@@ -107,6 +107,11 @@ static inline int valid_stack_ptr(struct thread_info *tinfo, void *p, unsigned s
 		p <= (void *)tinfo + THREAD_SIZE - size;
 }
 
+static inline int valid_frame_ptr(struct thread_info *tinfo, void *stack, void *p, unsigned size)
+{
+	return p >= stack && valid_stack_ptr(tinfo, p, size);
+}
+
 /* The form of the top of the frame on the stack */
 struct stack_frame {
 	struct stack_frame *next_frame;
@@ -119,24 +124,23 @@ static inline unsigned long print_context_stack(struct thread_info *tinfo,
 {
 #ifdef	CONFIG_FRAME_POINTER
 	struct stack_frame *frame = (struct stack_frame *)ebp;
-	while (valid_stack_ptr(tinfo, frame, sizeof(*frame))) {
-		struct stack_frame *next;
+	while (valid_frame_ptr(tinfo, stack, frame, sizeof(*frame))) {
 		unsigned long addr;
 
 		addr = frame->return_address;
+		if (!__kernel_text_address(addr))
+			break;
 		ops->address(data, addr);
+
 		/*
-		 * break out of recursive entries (such as
-		 * end_of_stack_stop_unwind_function). Also,
-		 * we can never allow a frame pointer to
-		 * move downwards!
+		 * Update the stack pointer to past the return
+		 * address we just printed out, and try the next
+		 * frame..
 		 */
-		next = frame->next_frame;
-		if (next <= frame)
-			break;
-		frame = next;
+		stack = 1+&frame->return_address;
+		frame = frame->next_frame;
 	}
-#else
+#endif
 	while (valid_stack_ptr(tinfo, stack, sizeof(*stack))) {
 		unsigned long addr;
 
@@ -144,7 +148,6 @@ static inline unsigned long print_context_stack(struct thread_info *tinfo,
 		if (__kernel_text_address(addr))
 			ops->address(data, addr);
 	}
-#endif
 	return ebp;
 }
 

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Arjan van de Ven]

On Thu, 10 Jan 2008 08:36:57 -0800 (PST)
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 
> 
> On Wed, 9 Jan 2008, Arjan van de Ven wrote:
> >
> > +	if (valid_stack_ptr(tinfo, frame, sizeof(*frame)))
> > +		while (valid_stack_ptr(tinfo, frame,
> > sizeof(*frame))) {
> 
> Why?
> 
> Why not just make this something like the appended instead?
> 
> This is *totally* untested, but the basic notion is very simple:
> start off using the frame pointer until it is no longer valid (for
> any reason - whether the return address is corrupt, or the next frame
> info is bad), and update the stack pointer a you go.
> 
> When we've run out of frame pointers, we then scan any remaining
> stack the oldfashioned way, regardless of what happened. No
> unnecessary conditionals that will just mean that we don't show
> enough of the stack if *part* of it is corrupt.
> 
> The code is simpler and more robust (assuming it works - as
> mentioned, I didn't actually test it, so there may be some stupid
> thinko there).
> 

there's still a bug in it (not updating EBP) and I need to check how 
it reacts if you have 2 stacks, and you're at the end of the first stack,
and EBP now jumps to the second stack (correctly).

Anyway I'll test this after (or maybe during) my meeting, and fix the EBP return bug
and see how to deal with the 2 stack issue

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Arjan van de Ven]

On Thu, 10 Jan 2008 08:36:57 -0800 (PST)
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 
> 
> On Wed, 9 Jan 2008, Arjan van de Ven wrote:
> >
> > +	if (valid_stack_ptr(tinfo, frame, sizeof(*frame)))
> > +		while (valid_stack_ptr(tinfo, frame,
> > sizeof(*frame))) {
> 
> Why?
> 
> Why not just make this something like the appended instead?


ok having poked at this a ton more (and thought about it during a bori^long meeting),
your approach is really hard to make work nicely with things like irq stacks.
HOWEVER, we can do even better! (well in my tired opinion anyway)

What I like most so far is the following idea: We walk the stack using BOTH methods,
and just mark the entries we find as either "reliable as per stack frames" or as "unreliable".
This way we walk the entire stack, get all the data no matter how corrupt EBP or the frames end up,
yet we do get an indication on which parts are probably noise for the case of a reliable stack
frame setup.

I coded it, it's not all that bad, the output looks like:

Pid: 0, comm: swapper Not tainted 2.6.24-rc7 #17
 [<c0405d6c>] show_trace_log_lvl+0x1a/0x2f
 [<c04066d6>] show_trace+0x12/0x14  
 [<c0406f47>] dump_stack+0x6a/0x70
 [<e01f6028>] backtrace_test_timer+0x23/0x25 [backtracetest]
 [<c0426f07>] run_timer_softirq+0x11b/0x17c
 [<e01f6005>] .backtrace_test_timer+0x0/0x25 [backtracetest]
 [<c043b2e0>] .trace_hardirqs_on+0x101/0x13b
 [<e01f6005>] .backtrace_test_timer+0x0/0x25 [backtracetest]
 [<c04243ac>] __do_softirq+0x42/0x94
 [<c04070a0>] do_softirq+0x50/0xb6
 [<c0453f3c>] .handle_edge_irq+0x0/0xfa
 [<c04242a9>] irq_exit+0x37/0x67
 [<c04071a0>] do_IRQ+0x9a/0xaf
 [<c04057da>] common_interrupt+0x2e/0x34
 [<c041007b>] .write_watchdog_counter32+0x5/0x48
 [<c0523371>] .acpi_idle_enter_simple+0x167/0x1da
 [<c05807fe>] cpuidle_idle_call+0x52/0x78
 [<c04034f3>] cpu_idle+0x46/0x60
 [<c05fbbd3>] rest_init+0x43/0x45
 [<c070aa3d>] start_kernel+0x279/0x27f
 [<c070a327>] .unknown_bootoption+0x0/0x1a4
 =======================

where I used a "." to indicate potentially-unreliable (this I'm not very happy with, but I can print anything I want on either side of the function; ideas welcome).

The code is relatively simple as well, it looks more or less like this:

@@ -119,24 +119,31 @@ static inline unsigned long print_contex
 {
 #ifdef CONFIG_FRAME_POINTER
        struct stack_frame *frame = (struct stack_frame *)ebp;
+
+       /*
+        * if EBP is "deeper" into the stack than the actual stack pointer,
+        * we need to rewind the stack pointer a little to start at the
+        * first stack frame, but only if EBP is in this stack frame.  
+        */
+       if (stack > (unsigned long *) ebp)
+                       && valid_stack_ptr(tinfo, frame, sizeof(*frame)) {
+               stack = (unsigned long *) ebp;
+       }
+
+       while (valid_stack_ptr(tinfo, stack, sizeof(*stack))) {
                unsigned long addr;
 
+               addr = *stack;
+               if (__kernel_text_address(addr)) {
+                       if ((unsigned long) stack == ebp + 4) {
+				/* we have a stack frame based hit */
+                               ops->address(data, addr, 1);   
+                               frame = frame->next_frame;     
+                               ebp = (unsigned long) frame;   
+                       } else {
+				/* 
+				 * it looks like a kernel function, but
+				 * it doesn't match a stack frame,
+				 * print it as unreliable
+				 */
+                               ops->address(data, addr, 0);
+                       }
+               }
+               stack++;
        }


I need to go clean up the patch and split it up into 2 pieces (one for the capability to print unreliable trace entries, and the second the chunk above to actually walk the stack). I'm also going to try to remove some of the casts
in the code.

What do you think of this approach instead of your proposal?

-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Olaf Dietsche]

Arjan van de Ven <arjan@infradead.org> writes:

> I coded it, it's not all that bad, the output looks like:
>
> Pid: 0, comm: swapper Not tainted 2.6.24-rc7 #17
>  [<c0405d6c>] show_trace_log_lvl+0x1a/0x2f
>  [<c04066d6>] show_trace+0x12/0x14  
>  [<c0406f47>] dump_stack+0x6a/0x70
>  [<e01f6028>] backtrace_test_timer+0x23/0x25 [backtracetest]
>  [<c0426f07>] run_timer_softirq+0x11b/0x17c
>  [<e01f6005>] .backtrace_test_timer+0x0/0x25 [backtracetest]
>  [<c043b2e0>] .trace_hardirqs_on+0x101/0x13b
>  [<e01f6005>] .backtrace_test_timer+0x0/0x25 [backtracetest]
>  [<c04243ac>] __do_softirq+0x42/0x94
>  [<c04070a0>] do_softirq+0x50/0xb6
>  [<c0453f3c>] .handle_edge_irq+0x0/0xfa
>  [<c04242a9>] irq_exit+0x37/0x67
>  [<c04071a0>] do_IRQ+0x9a/0xaf
>  [<c04057da>] common_interrupt+0x2e/0x34
>  [<c041007b>] .write_watchdog_counter32+0x5/0x48
>  [<c0523371>] .acpi_idle_enter_simple+0x167/0x1da
>  [<c05807fe>] cpuidle_idle_call+0x52/0x78
>  [<c04034f3>] cpu_idle+0x46/0x60
>  [<c05fbbd3>] rest_init+0x43/0x45
>  [<c070aa3d>] start_kernel+0x279/0x27f
>  [<c070a327>] .unknown_bootoption+0x0/0x1a4
>  =======================
>
> where I used a "." to indicate potentially-unreliable (this I'm not
> very happy with, but I can print anything I want on either side of
> the function; ideas welcome).

Maybe question marks?

Regards, Olaf.

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Linus Torvalds]

On Thu, 10 Jan 2008, Arjan van de Ven wrote:
> 
> What do you think of this approach instead of your proposal?

Looks ok to me. I get the feeling that we *should* be able to make the

	#ifdef CONFIG_FRAME_POINTER
	..

thing be a bit cleaner with this (since you have the non-frame-pointer 
thing inside the loop as well), and use one common routine for it all, 
with just certain helper functions always retuning a NULL or something for 
the non-frame-pointer thing.

In other words, I *think* the non-frame-pointer case should always be 
doable as a "series of single-word unverified frames", but if that kind of 
cleanup doesn't work, I certainly don't hate your patch either..

(I also wonder if we should limit the number of entries we print out. 
Sometimes the stack frame ends up being so deep that we lose the 
*important* stuff. I think it might be good idea to have some rule like 
"the first 5 entries go to the screen, the rest will be KERN_DEBUG and 
only go to the logs by default" - so a "dmesg" would show it all, but if 
the machine is hung, the screen won't have been scrolled away from all 
the other things by a long backtrace!)

		Linus

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Arjan van de Ven]

On Fri, 11 Jan 2008 11:41:40 -0800 (PST)
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 
> 
> On Thu, 10 Jan 2008, Arjan van de Ven wrote:
> > 
> > What do you think of this approach instead of your proposal?
> 
> Looks ok to me. I get the feeling that we *should* be able to make the
> 
> 	#ifdef CONFIG_FRAME_POINTER
> 	..
> 
> thing be a bit cleaner with this (since you have the
> non-frame-pointer thing inside the loop as well), and use one common
> routine for it all, with just certain helper functions always
> retuning a NULL or something for the non-frame-pointer thing.

ok I'll try that; I'm also trying some other cleanups
(right now we pick "ebp" and the stack pointer at different levels
in the call chain, so it gets a tad messy)

> 
> (I also wonder if we should limit the number of entries we print out. 
> Sometimes the stack frame ends up being so deep that we lose the 
> *important* stuff. I think it might be good idea to have some rule
> like "the first 5 entries go to the screen, the rest will be
> KERN_DEBUG and only go to the logs by default" - so a "dmesg" would
> show it all, but if the machine is hung, the screen won't have been
> scrolled away from all the other things by a long backtrace!)

that's... a ton more tricky, and realistically needs the patch
to make show_stack take a level argument in the first place.
(I have that done, it's just touching like 125+ files, so
I shelved it as "probably not important enough");


-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: Make the 32 bit Frame Pointer backtracer fall back to traditional

[Theodore Tso]

On Fri, Jan 11, 2008 at 11:41:40AM -0800, Linus Torvalds wrote:
> 
> (I also wonder if we should limit the number of entries we print out. 
> Sometimes the stack frame ends up being so deep that we lose the 
> *important* stuff. I think it might be good idea to have some rule like 
> "the first 5 entries go to the screen, the rest will be KERN_DEBUG and 
> only go to the logs by default" - so a "dmesg" would show it all, but if 
> the machine is hung, the screen won't have been scrolled away from all 
> the other things by a long backtrace!)

What might be useful is the first 5 and last 5.  Sometimes if you have
a very deep call chain, the what was the original system call or
interrupt which got the kernel deep into la-la land can often be
useful.  Just a thought.

					- Ted