[PATCH] dump_stack() based on prologue code analysis

[PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

Instead of dump all possible address in the stack, unwind the stack
frame based on prologue code analysis, as like as get_chan() does.
While the code analysis might fail for some reason, there is a new
kernel option "raw_show_trace" to disable this feature.

Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>

diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index 7ab67f7..8f1a5fe 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -281,7 +281,7 @@ static struct mips_frame_info {
 } *schedule_frame, mfinfo[64];
 static int mfinfo_num;
 
-static int __init get_frame_info(struct mips_frame_info *info)
+static int get_frame_info(struct mips_frame_info *info)
 {
 	int i;
 	void *func = info->func;
@@ -329,12 +329,6 @@ #endif
 				ip->i_format.simmediate / sizeof(long);
 		}
 	}
-	if (info->pc_offset == -1 || info->frame_size == 0) {
-		if (func == schedule)
-			printk("Can't analyze prologue code at %p\n", func);
-		info->pc_offset = -1;
-		info->frame_size = 0;
-	}
 
 	return 0;
 }
@@ -367,8 +361,17 @@ #else
 	mfinfo[0].func = schedule;
 	schedule_frame = &mfinfo[0];
 #endif
-	for (i = 0; i < ARRAY_SIZE(mfinfo) && mfinfo[i].func; i++)
-		get_frame_info(&mfinfo[i]);
+	for (i = 0; i < ARRAY_SIZE(mfinfo) && mfinfo[i].func; i++) {
+		struct mips_frame_info *info = &mfinfo[i];
+		get_frame_info(info);
+		if (info->pc_offset < 0 || info->frame_size == 0) {
+			if (info->func == schedule)
+				printk("Can't analyze prologue code at %p\n",
+				       info->func);
+			info->pc_offset = -1;
+			info->frame_size = 0;
+		}
+	}
 
 	mfinfo_num = i;
 	return 0;
@@ -437,3 +440,41 @@ #endif
 	return pc;
 }
 
+#ifdef CONFIG_KALLSYMS
+/* used by show_frametrace() */
+unsigned long unwind_stack(struct task_struct *task,
+			   unsigned long **sp, unsigned long pc)
+{
+	unsigned long stack_page;
+	struct mips_frame_info info;
+	char *modname;
+	char namebuf[KSYM_NAME_LEN + 1];
+	unsigned long size, ofs;
+
+	stack_page = (unsigned long)task_stack_page(task);
+	if (!stack_page)
+		return 0;
+
+	if (!kallsyms_lookup(pc, &size, &ofs, &modname, namebuf))
+		return 0;
+	if (ofs == 0)
+		return 0;
+
+	info.func = (void *)(pc - ofs);
+	info.func_size = ofs;	/* analyze from start to ofs */
+	get_frame_info(&info);
+	if (info.pc_offset < 0 || !info.frame_size) {
+		/* leaf? */
+		*sp += info.frame_size / sizeof(long);
+		return 0;
+	}
+	if ((unsigned long)*sp < stack_page ||
+	    (unsigned long)*sp + info.frame_size / sizeof(long) >
+	    stack_page + THREAD_SIZE - 32)
+		return 0;
+
+	pc = (*sp)[info.pc_offset];
+	*sp += info.frame_size / sizeof(long);
+	return pc;
+}
+#endif
diff --git a/arch/mips/kernel/traps.c b/arch/mips/kernel/traps.c
index c6f7046..bf36fcc 100644
--- a/arch/mips/kernel/traps.c
+++ b/arch/mips/kernel/traps.c
@@ -98,24 +98,53 @@ #endif
 	printk("\n");
 }
 
+#ifdef CONFIG_KALLSYMS
+static int raw_show_trace;
+static int __init set_raw_show_trace(char *str)
+{
+	raw_show_trace = 1;
+	return 1;
+}
+__setup("raw_show_trace", set_raw_show_trace);
+
+extern unsigned long unwind_stack(struct task_struct *task,
+				  unsigned long **sp, unsigned long pc);
+static void show_frametrace(struct task_struct *task, struct pt_regs *regs)
+{
+	const int field = 2 * sizeof(unsigned long);
+	unsigned long *stack = (long *)regs->regs[29];
+	unsigned long pc = regs->cp0_epc;
+	int top = 1;
+
+	if (raw_show_trace || !__kernel_text_address(pc)) {
+		show_trace(stack);
+		return;
+	}
+	printk("Call Trace:\n");
+	while (__kernel_text_address(pc)) {
+		printk(" [<%0*lx>] ", field, pc);
+		print_symbol("%s\n", pc);
+		pc = unwind_stack(task, &stack, pc);
+		if (top && pc == 0)
+			pc = regs->regs[31];	/* leaf? */
+		top = 0;
+	}
+	printk("\n");
+}
+#else
+#define show_frametrace(task, r) show_trace((long *)(r)->regs[29]);
+#endif
+
 /*
  * This routine abuses get_user()/put_user() to reference pointers
  * with at least a bit of error checking ...
  */
-void show_stack(struct task_struct *task, unsigned long *sp)
+static void show_stacktrace(struct task_struct *task, struct pt_regs *regs)
 {
 	const int field = 2 * sizeof(unsigned long);
 	long stackdata;
 	int i;
-	unsigned long *stack;
-
-	if (!sp) {
-		if (task && task != current)
-			sp = (unsigned long *) task->thread.reg29;
-		else
-			sp = (unsigned long *) &sp;
-	}
-	stack = sp;
+	unsigned long *sp = (unsigned long *)regs->regs[29];
 
 	printk("Stack :");
 	i = 0;
@@ -136,7 +165,44 @@ void show_stack(struct task_struct *task
 		i++;
 	}
 	printk("\n");
-	show_trace(stack);
+	show_frametrace(task, regs);
+}
+
+static noinline void dump_stack_top(struct pt_regs *regs)
+{
+	__asm__ __volatile__(
+		"1: la $2, 1b\n\t"
+#ifdef CONFIG_64BIT
+		"sd $2, %0\n\t"
+		"sd $29, %1\n\t"
+		"sd $31, %2\n\t"
+#else
+		"sw $2, %0\n\t"
+		"sw $29, %1\n\t"
+		"sw $31, %2\n\t"
+#endif
+		: "=m" (regs->cp0_epc),
+		"=m" (regs->regs[29]), "=m" (regs->regs[31])
+		: : "memory");
+}
+
+void show_stack(struct task_struct *task, unsigned long *sp)
+{
+	struct pt_regs regs;
+	if (sp) {
+		regs.regs[29] = (unsigned long)sp;
+		regs.regs[31] = 0;
+		regs.cp0_epc = 0;
+	} else {
+		if (task && task != current) {
+			regs.regs[29] = task->thread.reg29;
+			regs.regs[31] = 0;
+			regs.cp0_epc = task->thread.reg31;
+		} else {
+			dump_stack_top(&regs);
+		}
+	}
+	show_stacktrace(task, &regs);
 }
 
 /*
@@ -146,6 +212,14 @@ void dump_stack(void)
 {
 	unsigned long stack;
 
+#ifdef CONFIG_KALLSYMS
+	if (!raw_show_trace) {
+		struct pt_regs regs;
+		dump_stack_top(&regs);
+		show_frametrace(current, &regs);
+		return;
+	}
+#endif
 	show_trace(&stack);
 }
 
@@ -265,7 +339,7 @@ void show_registers(struct pt_regs *regs
 	print_modules();
 	printk("Process %s (pid: %d, threadinfo=%p, task=%p)\n",
 	        current->comm, current->pid, current_thread_info(), current);
-	show_stack(current, (long *) regs->regs[29]);
+	show_stacktrace(current, regs);
 	show_code((unsigned int *) regs->cp0_epc);
 	printk("\n");
 }

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

Hi Atsushi ;)

Atsushi Nemoto wrote:
> Instead of dump all possible address in the stack, unwind the stack
> frame based on prologue code analysis, as like as get_chan() does.
> While the code analysis might fail for some reason, there is a new
> kernel option "raw_show_trace" to disable this feature.
> 
> Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>
> 
> diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
> index 7ab67f7..8f1a5fe 100644
> --- a/arch/mips/kernel/process.c
> +++ b/arch/mips/kernel/process.c
> @@ -281,7 +281,7 @@ static struct mips_frame_info {
>  } *schedule_frame, mfinfo[64];
>  static int mfinfo_num;
>  
> -static int __init get_frame_info(struct mips_frame_info *info)
> +static int get_frame_info(struct mips_frame_info *info)
>  {
>  	int i;
>  	void *func = info->func;
> @@ -329,12 +329,6 @@ #endif
>  				ip->i_format.simmediate / sizeof(long);
>  		}
>  	}
> -	if (info->pc_offset == -1 || info->frame_size == 0) {
> -		if (func == schedule)
> -			printk("Can't analyze prologue code at %p\n", func);
> -		info->pc_offset = -1;
> -		info->frame_size = 0;
> -	}
>  
>  	return 0;
>  }
> @@ -367,8 +361,17 @@ #else
>  	mfinfo[0].func = schedule;
>  	schedule_frame = &mfinfo[0];
>  #endif
> -	for (i = 0; i < ARRAY_SIZE(mfinfo) && mfinfo[i].func; i++)
> -		get_frame_info(&mfinfo[i]);
> +	for (i = 0; i < ARRAY_SIZE(mfinfo) && mfinfo[i].func; i++) {
> +		struct mips_frame_info *info = &mfinfo[i];
> +		get_frame_info(info);
> +		if (info->pc_offset < 0 || info->frame_size == 0) {
> +			if (info->func == schedule)

This can't happen since "schedule" is not a leaf function. Something I'm
missing here but I would have said:

			if (func != schedule)

instead, no ?

> +				printk("Can't analyze prologue code at %p\n",
> +				       info->func);
> +			info->pc_offset = -1;
> +			info->frame_size = 0;
> +		}
> +	}
>  
>  	mfinfo_num = i;
>  	return 0;
> @@ -437,3 +440,41 @@ #endif
>  	return pc;
>  }
>  
> +#ifdef CONFIG_KALLSYMS
> +/* used by show_frametrace() */
> +unsigned long unwind_stack(struct task_struct *task,
> +			   unsigned long **sp, unsigned long pc)
> +{
> +	unsigned long stack_page;
> +	struct mips_frame_info info;
> +	char *modname;
> +	char namebuf[KSYM_NAME_LEN + 1];
> +	unsigned long size, ofs;
> +
> +	stack_page = (unsigned long)task_stack_page(task);
> +	if (!stack_page)
> +		return 0;
> +
> +	if (!kallsyms_lookup(pc, &size, &ofs, &modname, namebuf))
> +		return 0;
> +	if (ofs == 0)
> +		return 0;
> +
> +	info.func = (void *)(pc - ofs);
> +	info.func_size = ofs;	/* analyze from start to ofs */
> +	get_frame_info(&info);
> +	if (info.pc_offset < 0 || !info.frame_size) {
> +		/* leaf? */

for leaf case, can't we simply do this test:

	if (info.pc_offset < 0) {

IOW, can a leaf function move sp ? I would say yes...

BTW why not let this logic inside get_frame_info() ? Hence this function
could return:

	if (info.frame_size && info.pc_offset > 0) /* nested */
		return 0;
	if (info.pc_offset < 0) /* leaf */
		return 1;
	/* prologue seems boggus... */
	printk("Can't analyze prologue code at %p\n", info->func);
	return -1;

> +		*sp += info.frame_size / sizeof(long);
> +		return 0;

why not returning:
		return regs->regs[31];

and removes the leaf detection logic in show_frametrace() ?

> +	}
> +	if ((unsigned long)*sp < stack_page ||
> +	    (unsigned long)*sp + info.frame_size / sizeof(long) >
> +	    stack_page + THREAD_SIZE - 32)
> +		return 0;
> +
> +	pc = (*sp)[info.pc_offset];
> +	*sp += info.frame_size / sizeof(long);
> +	return pc;

why not directly doing:

	return (*sp)[info.pc_offset];

and remove:

	pc = (*sp)[info.pc_offset];

> +}
> +#endif
> diff --git a/arch/mips/kernel/traps.c b/arch/mips/kernel/traps.c
> index c6f7046..bf36fcc 100644
> --- a/arch/mips/kernel/traps.c
> +++ b/arch/mips/kernel/traps.c
> @@ -98,24 +98,53 @@ #endif
>  	printk("\n");
>  }
>  
> +#ifdef CONFIG_KALLSYMS
> +static int raw_show_trace;
> +static int __init set_raw_show_trace(char *str)
> +{
> +	raw_show_trace = 1;
> +	return 1;
> +}
> +__setup("raw_show_trace", set_raw_show_trace);
> +
> +extern unsigned long unwind_stack(struct task_struct *task,
> +				  unsigned long **sp, unsigned long pc);
> +static void show_frametrace(struct task_struct *task, struct pt_regs *regs)
> +{
> +	const int field = 2 * sizeof(unsigned long);
> +	unsigned long *stack = (long *)regs->regs[29];

why not calling that "sp" ?

> +	unsigned long pc = regs->cp0_epc;
> +	int top = 1;
> +
> +	if (raw_show_trace || !__kernel_text_address(pc)) {
> +		show_trace(stack);
> +		return;
> +	}
> +	printk("Call Trace:\n");
> +	while (__kernel_text_address(pc)) {
> +		printk(" [<%0*lx>] ", field, pc);
> +		print_symbol("%s\n", pc);
> +		pc = unwind_stack(task, &stack, pc);
> +		if (top && pc == 0)
> +			pc = regs->regs[31];	/* leaf? */
> +		top = 0;
> +	}
> +	printk("\n");
> +}
> +#else
> +#define show_frametrace(task, r) show_trace((long *)(r)->regs[29]);
> +#endif
> +
>  /*
>   * This routine abuses get_user()/put_user() to reference pointers
>   * with at least a bit of error checking ...
>   */
> -void show_stack(struct task_struct *task, unsigned long *sp)
> +static void show_stacktrace(struct task_struct *task, struct pt_regs *regs)
>  {
>  	const int field = 2 * sizeof(unsigned long);
>  	long stackdata;
>  	int i;
> -	unsigned long *stack;
> -
> -	if (!sp) {
> -		if (task && task != current)
> -			sp = (unsigned long *) task->thread.reg29;
> -		else
> -			sp = (unsigned long *) &sp;
> -	}
> -	stack = sp;
> +	unsigned long *sp = (unsigned long *)regs->regs[29];
>  
>  	printk("Stack :");
>  	i = 0;
> @@ -136,7 +165,44 @@ void show_stack(struct task_struct *task
>  		i++;
>  	}
>  	printk("\n");
> -	show_trace(stack);
> +	show_frametrace(task, regs);
> +}
> +
> +static noinline void dump_stack_top(struct pt_regs *regs)

This sounds weird, you're actually dumping v0, ra, and sp, no ?
If so "dump_stack_top" seems not be appropriate, does it ?

> +{
> +	__asm__ __volatile__(
> +		"1: la $2, 1b\n\t"
> +#ifdef CONFIG_64BIT
> +		"sd $2, %0\n\t"
> +		"sd $29, %1\n\t"
> +		"sd $31, %2\n\t"
> +#else
> +		"sw $2, %0\n\t"
> +		"sw $29, %1\n\t"
> +		"sw $31, %2\n\t"
> +#endif
> +		: "=m" (regs->cp0_epc),
> +		"=m" (regs->regs[29]), "=m" (regs->regs[31])
> +		: : "memory");
> +}
> +
> +void show_stack(struct task_struct *task, unsigned long *sp)
> +{
> +	struct pt_regs regs;
> +	if (sp) {
> +		regs.regs[29] = (unsigned long)sp;
> +		regs.regs[31] = 0;
> +		regs.cp0_epc = 0;
> +	} else {
> +		if (task && task != current) {
> +			regs.regs[29] = task->thread.reg29;
> +			regs.regs[31] = 0;
> +			regs.cp0_epc = task->thread.reg31;
> +		} else {
> +			dump_stack_top(&regs);
> +		}
> +	}
> +	show_stacktrace(task, &regs);
>  }
>  
>  /*
> @@ -146,6 +212,14 @@ void dump_stack(void)
>  {
>  	unsigned long stack;
>  
> +#ifdef CONFIG_KALLSYMS
> +	if (!raw_show_trace) {
> +		struct pt_regs regs;
> +		dump_stack_top(&regs);
> +		show_frametrace(current, &regs);
> +		return;
> +	}
> +#endif
>  	show_trace(&stack);
>  }
>  
> @@ -265,7 +339,7 @@ void show_registers(struct pt_regs *regs
>  	print_modules();
>  	printk("Process %s (pid: %d, threadinfo=%p, task=%p)\n",
>  	        current->comm, current->pid, current_thread_info(), current);
> -	show_stack(current, (long *) regs->regs[29]);
> +	show_stacktrace(current, regs);
>  	show_code((unsigned int *) regs->cp0_epc);
>  	printk("\n");
>  }
> 
> 

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

one more comment,

2006/7/27, Franck Bui-Huu <vagabon.xyz@gmail.com>:
> Hi Atsushi ;)
>
> Atsushi Nemoto wrote:
> > +unsigned long unwind_stack(struct task_struct *task,
> > +                        unsigned long **sp, unsigned long pc)
> > +{
> > +     unsigned long stack_page;
> > +     struct mips_frame_info info;
> > +     char *modname;
> > +     char namebuf[KSYM_NAME_LEN + 1];
> > +     unsigned long size, ofs;
> > +
> > +     stack_page = (unsigned long)task_stack_page(task);
> > +     if (!stack_page)
> > +             return 0;
> > +
> > +     if (!kallsyms_lookup(pc, &size, &ofs, &modname, namebuf))
> > +             return 0;
> > +     if (ofs == 0)
> > +             return 0;
> > +
> > +     info.func = (void *)(pc - ofs);
> > +     info.func_size = ofs;   /* analyze from start to ofs */

in get_frame_info(), there is the following condition to stop the
prologue analysis

		if (info->func_size && i >= info->func_size / 4)
			break;

Setting info.func_size = ofs may trigger this stop condition very
early, specially if "ofs" is small...I would simply remove this
condition since it's very empirical and IMHO not very usefull.

> > +     get_frame_info(&info);
> > +     if (info.pc_offset < 0 || !info.frame_size) {
> > +             /* leaf? */
>
> for leaf case, can't we simply do this test:
>
>         if (info.pc_offset < 0) {

-- 
               Franck

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

Franck Bui-Huu wrote:
> one more comment,
> 

argh, your patch is already applied ! No room for comments
on MIPS...BTW, are these patches going to be included in
a 2.6.18-rcX release ?

Anyways, I'll send to you a patch on top of yours including
my changes if you agree with them.

Thanks
		Franck

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

On Fri, 28 Jul 2006 10:16:18 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
> argh, your patch is already applied ! No room for comments
> on MIPS...BTW, are these patches going to be included in
> a 2.6.18-rcX release ?

Unfortunately, not applied yet.  Comments are welcome even if already
applied.  We can send a new patch anyway.  Nothing is too late :-)

---
Atsushi Nemoto

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

On Thu, 27 Jul 2006 21:03:07 +0200, "Franck Bui-Huu" <vagabon.xyz@gmail.com> wrote:
> > > +     info.func = (void *)(pc - ofs);
> > > +     info.func_size = ofs;   /* analyze from start to ofs */
> 
> in get_frame_info(), there is the following condition to stop the
> prologue analysis
> 
> 		if (info->func_size && i >= info->func_size / 4)
> 			break;
> 
> Setting info.func_size = ofs may trigger this stop condition very
> early, specially if "ofs" is small...I would simply remove this
> condition since it's very empirical and IMHO not very usefull.

Yes, that is what I wanted.  Imagine if a exception happened on first
place on non-leaf function.  In this case, we must assume the function
is leaf since RA is not saved to the stack.

---
Atsushi Nemoto

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

Atsushi Nemoto wrote:
> On Thu, 27 Jul 2006 21:03:07 +0200, "Franck Bui-Huu" <vagabon.xyz@gmail.com> wrote:
>>>> +     info.func = (void *)(pc - ofs);
>>>> +     info.func_size = ofs;   /* analyze from start to ofs */
>> in get_frame_info(), there is the following condition to stop the
>> prologue analysis
>>
>> 		if (info->func_size && i >= info->func_size / 4)
>> 			break;
>>
>> Setting info.func_size = ofs may trigger this stop condition very
>> early, specially if "ofs" is small...I would simply remove this
>> condition since it's very empirical and IMHO not very usefull.
> 
> Yes, that is what I wanted.  Imagine if a exception happened on first
> place on non-leaf function.  In this case, we must assume the function
> is leaf since RA is not saved to the stack.
> 

The only case I can imagine is when sp is corrupted which is unlikely.
However an exception can occure just after a prologue of a nested
function which is more likely. In that case you will assume wrongly
that the function was a leaf one.

I don't think we gain more than we loose with this test. Maybe we can
just leave

 		if (i >= info->func_size)
 			break;

for safety purpose.

		Franck

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

On Mon, 31 Jul 2006 11:15:50 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
> > Yes, that is what I wanted.  Imagine if a exception happened on first
> > place on non-leaf function.  In this case, we must assume the function
> > is leaf since RA is not saved to the stack.
> 
> The only case I can imagine is when sp is corrupted which is unlikely.

Modern gcc somtimes do amazing optimization ;-)

> However an exception can occure just after a prologue of a nested
> function which is more likely. In that case you will assume wrongly
> that the function was a leaf one.

Why?  get_frame_info() should detect frame_size and pc_offset for that
case.

Is your objection against "info->func_size / 4" part?  the "4" comes
from size of a instruction.

Well, using "4" instead of "sizeof(union mips_instruction)" or
"sizeof(*ip)" was my old fault...

---
Atsushi Nemoto

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

Atsushi Nemoto wrote:
> On Mon, 31 Jul 2006 11:15:50 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
>>> Yes, that is what I wanted.  Imagine if a exception happened on first
>>> place on non-leaf function.  In this case, we must assume the function
>>> is leaf since RA is not saved to the stack.
>> The only case I can imagine is when sp is corrupted which is unlikely.
> 
> Modern gcc somtimes do amazing optimization ;-)
> 
>> However an exception can occure just after a prologue of a nested
>> function which is more likely. In that case you will assume wrongly
>> that the function was a leaf one.
> 
> Why?  get_frame_info() should detect frame_size and pc_offset for that
> case.
> 
> Is your objection against "info->func_size / 4" part?  the "4" comes
> from size of a instruction.
>

OK. I missed that, sorry.

> Well, using "4" instead of "sizeof(union mips_instruction)" or
> "sizeof(*ip)" was my old fault...

Well could we use "sizeof(union mips_instruction)" so nobody won't
make the same mistake ?

 		if (i >= info->func_size / sizeof(union mips_instruction))
 			break;

BTW I omit the first condition "info->func_size != 0" because
normally a func has a no null size. If it has we should stop
right now.

We should also test this condition _before_ testing that "*ip" is
a jal instruction, shouldn't we ?

		Franck

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

On Mon, 31 Jul 2006 16:32:52 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
> Well could we use "sizeof(union mips_instruction)" so nobody won't
> make the same mistake ?
> 
>  		if (i >= info->func_size / sizeof(union mips_instruction))
>  			break;

Indeed.

> BTW I omit the first condition "info->func_size != 0" because
> normally a func has a no null size. If it has we should stop
> right now.
 
Yes.  I can not remember why "info->func_size != 0" is there...

> We should also test this condition _before_ testing that "*ip" is
> a jal instruction, shouldn't we ?

Yes, and we can hold the condition indo the "for" statement.


Subject: [PATCH] make get_frame_info() more readable.

Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>

diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index 8709a46..949efaf 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -286,18 +286,17 @@ static int get_frame_info(struct mips_fr
 	int i;
 	void *func = info->func;
 	union mips_instruction *ip = (union mips_instruction *)func;
+	int max_insns =
+		min(128UL, info->func_size / sizeof(union mips_instruction));
 	info->pc_offset = -1;
 	info->frame_size = 0;
-	for (i = 0; i < 128; i++, ip++) {
+	for (i = 0; i < max_insns; i++, ip++) {
 		/* if jal, jalr, jr, stop. */
 		if (ip->j_format.opcode == jal_op ||
 		    (ip->r_format.opcode == spec_op &&
 		     (ip->r_format.func == jalr_op ||
 		      ip->r_format.func == jr_op)))
 			break;
-
-		if (info->func_size && i >= info->func_size / 4)
-			break;
 		if (
 #ifdef CONFIG_32BIT
 		    ip->i_format.opcode == addiu_op &&

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

Atsushi Nemoto wrote:
> 
> Subject: [PATCH] make get_frame_info() more readable.
> 
> Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>
> 
> diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
> index 8709a46..949efaf 100644
> --- a/arch/mips/kernel/process.c
> +++ b/arch/mips/kernel/process.c
> @@ -286,18 +286,17 @@ static int get_frame_info(struct mips_fr
>  	int i;
>  	void *func = info->func;
>  	union mips_instruction *ip = (union mips_instruction *)func;

while you're at it, (union mips_instruction *) cast is useless and "func"
local too. Just write 

	union mips_instruction *ip = info->func;

is more readable, IMHO.

		Franck

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

On Mon, 31 Jul 2006 17:51:22 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
> while you're at it, (union mips_instruction *) cast is useless and "func"
> local too. Just write 
> 
> 	union mips_instruction *ip = info->func;
> 
> is more readable, IMHO.

Indeed.  Revised.


Subject: [PATCH] make get_frame_info() more readable.

Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>

diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index 8709a46..cd99bc8 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -284,20 +284,18 @@ static int mfinfo_num;
 static int get_frame_info(struct mips_frame_info *info)
 {
 	int i;
-	void *func = info->func;
-	union mips_instruction *ip = (union mips_instruction *)func;
+	union mips_instruction *ip = info->func;
+	int max_insns =
+		min(128UL, info->func_size / sizeof(union mips_instruction));
 	info->pc_offset = -1;
 	info->frame_size = 0;
-	for (i = 0; i < 128; i++, ip++) {
+	for (i = 0; i < max_insns; i++, ip++) {
 		/* if jal, jalr, jr, stop. */
 		if (ip->j_format.opcode == jal_op ||
 		    (ip->r_format.opcode == spec_op &&
 		     (ip->r_format.func == jalr_op ||
 		      ip->r_format.func == jr_op)))
 			break;
-
-		if (info->func_size && i >= info->func_size / 4)
-			break;
 		if (
 #ifdef CONFIG_32BIT
 		    ip->i_format.opcode == addiu_op &&

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

Hi, Franck.  Thank you for detailed review.

On Thu, 27 Jul 2006 16:33:08 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
> > +		if (info->pc_offset < 0 || info->frame_size == 0) {
> > +			if (info->func == schedule)
> 
> This can't happen since "schedule" is not a leaf function. Something I'm
> missing here but I would have said:
> 
> 			if (func != schedule)
> 
> instead, no ?

This "if (info->func == schedule)" condition is originally in current
get_frame_info().  And it was added to report "Can't analyze" message
only for schedule() function.  This is because we can get at least
somewhat worth results for thread_saved_pc() and get_wchan() if the
frame information for the schedule() could be analyzed.  The frame
information for other functions just make get_wchan()'s result better.

> > +	if (info.pc_offset < 0 || !info.frame_size) {
> > +		/* leaf? */
> 
> for leaf case, can't we simply do this test:
> 
> 	if (info.pc_offset < 0) {
> 
> IOW, can a leaf function move sp ? I would say yes...

Normally, we can omit "!info.frame_size".  But as I wrote in other
mail, I think it is hard to make perfect get_frame_info().  We should
handle any wired result from get_frame_info().

> BTW why not let this logic inside get_frame_info() ? Hence this function
> could return:
> 
> 	if (info.frame_size && info.pc_offset > 0) /* nested */
> 		return 0;
> 	if (info.pc_offset < 0) /* leaf */
> 		return 1;
> 	/* prologue seems boggus... */
> 	printk("Can't analyze prologue code at %p\n", info->func);
> 	return -1;

Indeed.  I'll make new patch.  But I think put printk() in
get_frame_info() not good because now I want to use it for
show_trace().  I don't want to see the "Can't analyze" message in oops
log.

> > +		*sp += info.frame_size / sizeof(long);
> > +		return 0;
> 
> why not returning:
> 		return regs->regs[31];
> 
> and removes the leaf detection logic in show_frametrace() ?

Because unwind_stack() does not have "regs" argument.  The RA
information is only needed for leaf (i.e. top on stack trace) and
unwind_stack() is used for any level of stack, so I think it is better
to handle the leaf case in show_frametrace().

> > +	pc = (*sp)[info.pc_offset];
> > +	*sp += info.frame_size / sizeof(long);
> > +	return pc;
> 
> why not directly doing:
> 
> 	return (*sp)[info.pc_offset];
> 
> and remove:
> 
> 	pc = (*sp)[info.pc_offset];

This is wrong.  The *sp must be modified before return.

> > +	unsigned long *stack = (long *)regs->regs[29];
> 
> why not calling that "sp" ?

Just because show_trace() named it "stack" :-)

---
Atsushi Nemoto

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

Atsushi Nemoto wrote:
> Hi, Franck.  Thank you for detailed review.
> 
> On Thu, 27 Jul 2006 16:33:08 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
>>> +	unsigned long *stack = (long *)regs->regs[29];
>> why not calling that "sp" ?
> 
> Just because show_trace() named it "stack" :-)
> 

nothing is too late ;)

		Franck

Re: [PATCH] dump_stack() based on prologue code analysis

[David Daney]

Atsushi Nemoto wrote:
> Instead of dump all possible address in the stack, unwind the stack
> frame based on prologue code analysis, as like as get_chan() does.
> While the code analysis might fail for some reason, there is a new
> kernel option "raw_show_trace" to disable this feature.
> 
> Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>

Let me start by saying I have not analyzed how all this code works, but 
I have done something similar in user space.

Since the kernel ABI does not use gp, many functions may not have a 
prolog (especially when compiled with newer versions of GCC).  In the 
user space case, most leaf functions have no prolog.  For the kernel I 
would imagine that many non-leaf functions (simple non-leaf functions 
that do only a tail call) would also not have a prolog.

I would be worried that many stack traces would become less useful.

If this were conditional on -fno-omit-frame-pointer, then I think it 
would be a good idea.

David Daney.

Re: [PATCH] dump_stack() based on prologue code analysis

[Thiemo Seufer]

David Daney wrote:
> Atsushi Nemoto wrote:
> >Instead of dump all possible address in the stack, unwind the stack
> >frame based on prologue code analysis, as like as get_chan() does.
> >While the code analysis might fail for some reason, there is a new
> >kernel option "raw_show_trace" to disable this feature.
> >
> >Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>
> 
> Let me start by saying I have not analyzed how all this code works, but 
> I have done something similar in user space.
> 
> Since the kernel ABI does not use gp, many functions may not have a 
> prolog (especially when compiled with newer versions of GCC).  In the 
> user space case, most leaf functions have no prolog.  For the kernel I 
> would imagine that many non-leaf functions (simple non-leaf functions 
> that do only a tail call) would also not have a prolog.

Non-leaves have to save/restore $31 somewhere, so there should be a
prologue.


Thiemo

Re: [PATCH] dump_stack() based on prologue code analysis

[David Daney]

Thiemo Seufer wrote:
> David Daney wrote:
> 
>>Atsushi Nemoto wrote:
>>
>>>Instead of dump all possible address in the stack, unwind the stack
>>>frame based on prologue code analysis, as like as get_chan() does.
>>>While the code analysis might fail for some reason, there is a new
>>>kernel option "raw_show_trace" to disable this feature.
>>>
>>>Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>
>>
>>Let me start by saying I have not analyzed how all this code works, but 
>>I have done something similar in user space.
>>
>>Since the kernel ABI does not use gp, many functions may not have a 
>>prolog (especially when compiled with newer versions of GCC).  In the 
>>user space case, most leaf functions have no prolog.  For the kernel I 
>>would imagine that many non-leaf functions (simple non-leaf functions 
>>that do only a tail call) would also not have a prolog.
> 
> 
> Non-leaves have to save/restore $31 somewhere, so there should be a
> prologue.

OK, good point.

But there is still the leaf function problem.

David Daney.

Re: [PATCH] dump_stack() based on prologue code analysis

[Franck Bui-Huu]

2006/7/27, Thiemo Seufer <ths@networkno.de>:
> David Daney wrote:
> > Atsushi Nemoto wrote:
> > >Instead of dump all possible address in the stack, unwind the stack
> > >frame based on prologue code analysis, as like as get_chan() does.
> > >While the code analysis might fail for some reason, there is a new
> > >kernel option "raw_show_trace" to disable this feature.
> > >
> > >Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>
> >
> > Let me start by saying I have not analyzed how all this code works, but
> > I have done something similar in user space.
> >
> > Since the kernel ABI does not use gp, many functions may not have a
> > prolog (especially when compiled with newer versions of GCC).  In the
> > user space case, most leaf functions have no prolog.  For the kernel I
> > would imagine that many non-leaf functions (simple non-leaf functions
> > that do only a tail call) would also not have a prolog.
>
> Non-leaves have to save/restore $31 somewhere, so there should be a
> prologue.
>

That's no always true. Consider this simple example:

void foo_wrapper(int a, int b)
{
        /* doing some checkings */
        [...];
        foo(a,b);
}

void foo(int a, intb)
{
        [...];
}

In foo_wrapper(), gcc will generate a "j" instruction (well I guess)
because once foo() is called and is finished, there's no needs to
return back to foo_wrapper(). In that case, foo_wrapper() won't have a
prologue.

But is it really needed to show that foo_wrapper() has been called
before foo() ? The backtrace given by oops is for the first debug
intervention. They don't give a very accurate backtrace but it's
enough to understand what's going on in most cases.

BTW, the same exists with inlined functions. Gcc can inlined function
that are not been marked inlined and these functions won't appear in
any traces...

-- 
               Franck

Re: [PATCH] dump_stack() based on prologue code analysis

[Thiemo Seufer]

Franck Bui-Huu wrote:
> 2006/7/27, Thiemo Seufer <ths@networkno.de>:
> >David Daney wrote:
> >> Atsushi Nemoto wrote:
> >> >Instead of dump all possible address in the stack, unwind the stack
> >> >frame based on prologue code analysis, as like as get_chan() does.
> >> >While the code analysis might fail for some reason, there is a new
> >> >kernel option "raw_show_trace" to disable this feature.
> >> >
> >> >Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>
> >>
> >> Let me start by saying I have not analyzed how all this code works, but
> >> I have done something similar in user space.
> >>
> >> Since the kernel ABI does not use gp, many functions may not have a
> >> prolog (especially when compiled with newer versions of GCC).  In the
> >> user space case, most leaf functions have no prolog.  For the kernel I
> >> would imagine that many non-leaf functions (simple non-leaf functions
> >> that do only a tail call) would also not have a prolog.
> >
> >Non-leaves have to save/restore $31 somewhere, so there should be a
> >prologue.
> >
> 
> That's no always true. Consider this simple example:
> 
> void foo_wrapper(int a, int b)
> {
>        /* doing some checkings */
>        [...];
>        foo(a,b);
> }
> 
> void foo(int a, intb)
> {
>        [...];
> }
> 
> In foo_wrapper(), gcc will generate a "j" instruction (well I guess)
> because once foo() is called and is finished, there's no needs to
> return back to foo_wrapper(). In that case, foo_wrapper() won't have a
> prologue.

Well, with tail call optimisation it isn't a true nested function any
more, the compiler can even reorder and/or combine functions in more
creative ways.

IOW, binary analysis can't be expected to provide full accuracy, but
we can live with a reasonable approximation, I think.


Thiemo

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

On Thu, 27 Jul 2006 20:12:45 +0100, Thiemo Seufer <ths@networkno.de> wrote:
> IOW, binary analysis can't be expected to provide full accuracy, but
> we can live with a reasonable approximation, I think.

Yes, this is a starting point.

The patch (and current mips get_wchan() implementation) tries to do is
what I used to do to analyze stack dump by hand.

1. Determine PC and SP.
2. Disassemble a function containing the PC address.
3. If the function is leaf, make use RA for new PC.
4. Otherwise, obtain saved RA from stack and use it for new PC.
5. Calculate new SP by undoing "addiu sp,sp,-imm".
6. Back to (2).

While it is hard to make the get_frame_info() perfect, this approach
might fail sometimes.  But it can work well for most case, and if it
did well we can get very good stack trace than current one (which may
contain so many false entries).

If you wanted to know the difference, please try ALT-SYSRQ-T (or
BREAK-T for serial console) with and without this patch :-)

---
Atsushi Nemoto

Re: [PATCH] dump_stack() based on prologue code analysis

[David Daney]

Atsushi Nemoto wrote:
> On Thu, 27 Jul 2006 20:12:45 +0100, Thiemo Seufer <ths@networkno.de> wrote:
> 
>>IOW, binary analysis can't be expected to provide full accuracy, but
>>we can live with a reasonable approximation, I think.
> 
> 
> Yes, this is a starting point.
> 
> The patch (and current mips get_wchan() implementation) tries to do is
> what I used to do to analyze stack dump by hand.
> 
> 1. Determine PC and SP.
> 2. Disassemble a function containing the PC address.
> 3. If the function is leaf, make use RA for new PC.

This was always the tricky part for me.  How do you know if the function 
is a leaf?

.
.
.
David Daney

Re: [PATCH] dump_stack() based on prologue code analysis

[Nigel Stephens]

David Daney wrote:
> Atsushi Nemoto wrote:
>> On Thu, 27 Jul 2006 20:12:45 +0100, Thiemo Seufer <ths@networkno.de> 
>> wrote:
>>
>>> IOW, binary analysis can't be expected to provide full accuracy, but
>>> we can live with a reasonable approximation, I think.
>>
>>
>> Yes, this is a starting point.
>>
>> The patch (and current mips get_wchan() implementation) tries to do is
>> what I used to do to analyze stack dump by hand.
>>
>> 1. Determine PC and SP.
>> 2. Disassemble a function containing the PC address.
>> 3. If the function is leaf, make use RA for new PC.
>
> This was always the tricky part for me.  How do you know if the 
> function is a leaf?
>

I think that if you cannot find a store instruction which saves RA to 
the stack -- either because it's a real leaf and there is no such store, 
or because the PC hasn't yet reached the store instruction -- then in 
both cases it can be treated as a leaf.

Nigel

Re: [PATCH] dump_stack() based on prologue code analysis

[David Daney]

Nigel Stephens wrote:
> 
> 
> David Daney wrote:
> 
>> Atsushi Nemoto wrote:
>>
>>> On Thu, 27 Jul 2006 20:12:45 +0100, Thiemo Seufer <ths@networkno.de> 
>>> wrote:
>>>
>>>> IOW, binary analysis can't be expected to provide full accuracy, but
>>>> we can live with a reasonable approximation, I think.
>>>
>>>
>>>
>>> Yes, this is a starting point.
>>>
>>> The patch (and current mips get_wchan() implementation) tries to do is
>>> what I used to do to analyze stack dump by hand.
>>>
>>> 1. Determine PC and SP.
>>> 2. Disassemble a function containing the PC address.
>>> 3. If the function is leaf, make use RA for new PC.
>>
>>
>> This was always the tricky part for me.  How do you know if the 
>> function is a leaf?
>>
> 
> I think that if you cannot find a store instruction which saves RA to 
> the stack -- either because it's a real leaf and there is no such store, 
> or because the PC hasn't yet reached the store instruction -- then in 
> both cases it can be treated as a leaf.

Presumably you are walking the code back from the PC until you find the 
prolog.  How would you tell if you had gone past the beginning of a leaf 
function?  If you find a j $31 you might assume that it was the end of 
the previous function.

But that does not work if you are in a function that has multiple return 
points.  On encountering a j $31 you have no way of telling if you are 
in a leaf function or a non-leaf function with multiple return points.

I may be missing something here, if you know of a failure-proof manner 
to detect leaf functions I would appreciate hearing what it is.

Thanks,
David Daney.

Re: [PATCH] dump_stack() based on prologue code analysis

[Thiemo Seufer]

David Daney wrote:
> Nigel Stephens wrote:
> >
> >
> >David Daney wrote:
> >
> >>Atsushi Nemoto wrote:
> >>
> >>>On Thu, 27 Jul 2006 20:12:45 +0100, Thiemo Seufer <ths@networkno.de> 
> >>>wrote:
> >>>
> >>>>IOW, binary analysis can't be expected to provide full accuracy, but
> >>>>we can live with a reasonable approximation, I think.
> >>>
> >>>
> >>>
> >>>Yes, this is a starting point.
> >>>
> >>>The patch (and current mips get_wchan() implementation) tries to do is
> >>>what I used to do to analyze stack dump by hand.
> >>>
> >>>1. Determine PC and SP.
> >>>2. Disassemble a function containing the PC address.
> >>>3. If the function is leaf, make use RA for new PC.
> >>
> >>
> >>This was always the tricky part for me.  How do you know if the 
> >>function is a leaf?
> >>
> >
> >I think that if you cannot find a store instruction which saves RA to 
> >the stack -- either because it's a real leaf and there is no such store, 
> >or because the PC hasn't yet reached the store instruction -- then in 
> >both cases it can be treated as a leaf.
> 
> Presumably you are walking the code back from the PC until you find the 
> prolog.  How would you tell if you had gone past the beginning of a leaf 
> function?  If you find a j $31 you might assume that it was the end of 
> the previous function.
> 
> But that does not work if you are in a function that has multiple return 
> points.  On encountering a j $31 you have no way of telling if you are 
> in a leaf function or a non-leaf function with multiple return points.

... or in a fragment of a single return function which was moved out
of the hot path, after the return point.


Thiemo

Re: [PATCH] dump_stack() based on prologue code analysis

[Atsushi Nemoto]

On Fri, 28 Jul 2006 11:32:23 -0700, David Daney <ddaney@avtrex.com> wrote:
> >> This was always the tricky part for me.  How do you know if the 
> >> function is a leaf?
> > 
> > I think that if you cannot find a store instruction which saves RA to 
> > the stack -- either because it's a real leaf and there is no such store, 
> > or because the PC hasn't yet reached the store instruction -- then in 
> > both cases it can be treated as a leaf.

Right.

> Presumably you are walking the code back from the PC until you find the 
> prolog.  How would you tell if you had gone past the beginning of a leaf 
> function?  If you find a j $31 you might assume that it was the end of 
> the previous function.

I think you are misunderstanding here.

What the get_frame_info() doing is just searching "sw $ra, ofs($sp)"
and "addiu sp,sp,-imm" instructions from beginning of the function.
We can obtain the start address and size of the function by
kallsyms_lookup().  This is why those stuff depend on CONFIG_KALLSYMS.

> I may be missing something here, if you know of a failure-proof manner 
> to detect leaf functions I would appreciate hearing what it is.

I have no good idea to do it without CONFIG_KALL_SYMS.
I suppose there is no silver bullet here...

---
Atsushi Nemoto