[PATCH 0/7] Improve prologue analysis code (take #2)

[PATCH 0/7] Improve prologue analysis code (take #2)

[Franck Bui-Huu]

This patch set clean up or improves this part of code. I splitted out
this into 7 patches to make the review easier.

This second try takes into account all feedbacks from Atsushi Nemoto.

		Franck

---
 arch/mips/kernel/process.c |  130 ++++++++++++++++++++++++--------------------
 arch/mips/kernel/traps.c   |   70 ++++++++++--------------
 2 files changed, 100 insertions(+), 100 deletions(-)

[PATCH 1/7] Make get_frame_info() more readable.

[Franck Bui-Huu]

Signed-off-by: Atsushi Nemoto <anemo@mba.ocn.ne.jp>
Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
 arch/mips/kernel/process.c |   67 ++++++++++++++++++++++++--------------------
 1 files changed, 36 insertions(+), 31 deletions(-)

diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index 8709a46..93d5432 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -281,48 +281,53 @@ static struct mips_frame_info {
 } *schedule_frame, mfinfo[64];
 static int mfinfo_num;
 
+static inline int is_ra_save_ins(union mips_instruction *ip)
+{
+	/* sw / sd $ra, offset($sp) */
+	return (ip->i_format.opcode == sw_op || ip->i_format.opcode == sd_op) &&
+		ip->i_format.rs == 29 &&
+		ip->i_format.rt == 31;
+}
+
+static inline int is_jal_jalr_jr_ins(union mips_instruction *ip)
+{
+	if (ip->j_format.opcode == jal_op)
+		return 1;
+	if (ip->r_format.opcode != spec_op)
+		return 0;
+	return ip->r_format.func == jalr_op || ip->r_format.func == jr_op;
+}
+
+static inline int is_sp_move_ins(union mips_instruction *ip)
+{
+	/* addiu/daddiu sp,sp,-imm */
+	if (ip->i_format.rs != 29 || ip->i_format.rt != 29)
+		return 0;
+	if (ip->i_format.opcode == addiu_op || ip->i_format.opcode == daddiu_op)
+		return 1;
+	return 0;
+}
+
 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 i, 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++) {
-		/* 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)
+	for (i = 0; i < max_insns; i++, ip++) {
+
+		if (is_jal_jalr_jr_ins(ip))
 			break;
-		if (
-#ifdef CONFIG_32BIT
-		    ip->i_format.opcode == addiu_op &&
-#endif
-#ifdef CONFIG_64BIT
-		    ip->i_format.opcode == daddiu_op &&
-#endif
-		    ip->i_format.rs == 29 &&
-		    ip->i_format.rt == 29) {
-			/* addiu/daddiu sp,sp,-imm */
+		if (is_sp_move_ins(ip)) {
 			if (info->frame_size)
 				continue;
 			info->frame_size = - ip->i_format.simmediate;
 		}
 
-		if (
-#ifdef CONFIG_32BIT
-		    ip->i_format.opcode == sw_op &&
-#endif
-#ifdef CONFIG_64BIT
-		    ip->i_format.opcode == sd_op &&
-#endif
-		    ip->i_format.rs == 29 &&
-		    ip->i_format.rt == 31) {
-			/* sw / sd $ra, offset($sp) */
+		if (is_ra_save_ins(ip)) {
 			if (info->pc_offset != -1)
 				continue;
 			info->pc_offset =
-- 
1.4.2.rc2

[PATCH 2/7] Remove unused MODULE_RANGE macro.

[Franck Bui-Huu]

Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
 arch/mips/kernel/traps.c |    5 -----
 1 files changed, 0 insertions(+), 5 deletions(-)

diff --git a/arch/mips/kernel/traps.c b/arch/mips/kernel/traps.c
index 7aa9dfc..4a11a3d 100644
--- a/arch/mips/kernel/traps.c
+++ b/arch/mips/kernel/traps.c
@@ -73,11 +73,6 @@ void (*board_nmi_handler_setup)(void);
 void (*board_ejtag_handler_setup)(void);
 void (*board_bind_eic_interrupt)(int irq, int regset);
 
-/*
- * These constant is for searching for possible module text segments.
- * MODULE_RANGE is a guess of how much space is likely to be vmalloced.
- */
-#define MODULE_RANGE (8*1024*1024)
 
 static void show_trace(unsigned long *stack)
 {
-- 
1.4.2.rc2

[PATCH 3/7] Miscellaneous cleanup in prologue analysis code

[Franck Bui-Huu]

We usually use backtrace term for dumping a call tree during
debug. Therefore this patch renames show_frametrace() into
show_backtrace() and show_trace() into show_raw_backtrace().

It also uses the new function print_ip_sym().

Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
 arch/mips/kernel/traps.c |   33 ++++++++++++++-------------------
 1 files changed, 14 insertions(+), 19 deletions(-)

diff --git a/arch/mips/kernel/traps.c b/arch/mips/kernel/traps.c
index 4a11a3d..549cbb8 100644
--- a/arch/mips/kernel/traps.c
+++ b/arch/mips/kernel/traps.c
@@ -74,21 +74,18 @@ void (*board_ejtag_handler_setup)(void);
 void (*board_bind_eic_interrupt)(int irq, int regset);
 
 
-static void show_trace(unsigned long *stack)
+static void show_raw_backtrace(unsigned long *sp)
 {
-	const int field = 2 * sizeof(unsigned long);
 	unsigned long addr;
 
 	printk("Call Trace:");
 #ifdef CONFIG_KALLSYMS
 	printk("\n");
 #endif
-	while (!kstack_end(stack)) {
-		addr = *stack++;
-		if (__kernel_text_address(addr)) {
-			printk(" [<%0*lx>] ", field, addr);
-			print_symbol("%s\n", addr);
-		}
+	while (!kstack_end(sp)) {
+		addr = *sp++;
+		if (__kernel_text_address(addr))
+			print_ip_sym(addr);
 	}
 	printk("\n");
 }
@@ -104,22 +101,20 @@ __setup("raw_show_trace", set_raw_show_t
 
 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)
+static void show_backtrace(struct task_struct *task, struct pt_regs *regs)
 {
-	const int field = 2 * sizeof(unsigned long);
-	unsigned long *stack = (long *)regs->regs[29];
+	unsigned long *sp = (long *)regs->regs[29];
 	unsigned long pc = regs->cp0_epc;
 	int top = 1;
 
 	if (raw_show_trace || !__kernel_text_address(pc)) {
-		show_trace(stack);
+		show_raw_backtrace(sp);
 		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);
+		print_ip_sym(pc);
+		pc = unwind_stack(task, &sp, pc);
 		if (top && pc == 0)
 			pc = regs->regs[31];	/* leaf? */
 		top = 0;
@@ -127,7 +122,7 @@ static void show_frametrace(struct task_
 	printk("\n");
 }
 #else
-#define show_frametrace(task, r) show_trace((long *)(r)->regs[29]);
+#define show_backtrace(task, r) show_raw_backtrace((long *)(r)->regs[29]);
 #endif
 
 /*
@@ -160,7 +155,7 @@ static void show_stacktrace(struct task_
 		i++;
 	}
 	printk("\n");
-	show_frametrace(task, regs);
+	show_backtrace(task, regs);
 }
 
 static noinline void prepare_frametrace(struct pt_regs *regs)
@@ -211,11 +206,11 @@ #ifdef CONFIG_KALLSYMS
 	if (!raw_show_trace) {
 		struct pt_regs regs;
 		prepare_frametrace(&regs);
-		show_frametrace(current, &regs);
+		show_backtrace(current, &regs);
 		return;
 	}
 #endif
-	show_trace(&stack);
+	show_raw_backtrace(&stack);
 }
 
 EXPORT_SYMBOL(dump_stack);
-- 
1.4.2.rc2

[PATCH 4/7] Make frame_info_init() more readable.

[Franck Bui-Huu]

Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
 arch/mips/kernel/process.c |   18 +++++++++---------
 1 files changed, 9 insertions(+), 9 deletions(-)

diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index 93d5432..da332d7 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -370,15 +370,15 @@ #else
 	mfinfo[0].func = schedule;
 	schedule_frame = &mfinfo[0];
 #endif
-	for (i = 0; i < ARRAY_SIZE(mfinfo) && mfinfo[i].func; i++) {
-		struct mips_frame_info *info = &mfinfo[i];
-		if (get_frame_info(info)) {
-			/* leaf or unknown */
-			if (info->func == schedule)
-				printk("Can't analyze prologue code at %p\n",
-				       info->func);
-		}
-	}
+	for (i = 0; i < ARRAY_SIZE(mfinfo) && mfinfo[i].func; i++)
+		get_frame_info(mfinfo + i);
+
+	/*
+	 * Without schedule() frame info, result given by
+	 * thread_saved_pc() and get_wchan() are not reliable.
+	 */
+	if (schedule_frame->pc_offset < 0)
+		printk("Can't analyze schedule() prologue at %p\n", schedule);
 
 	mfinfo_num = i;
 	return 0;
-- 
1.4.2.rc2

[PATCH 5/7] Simplify dump_stack()

[Franck Bui-Huu]

Make dump_stack() code not depend on CONFIG_KALLSYMS.

It also make prepare_frametrace() always inlined to get
less false entries reported by show_raw_backtrace().

Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
 arch/mips/kernel/traps.c |   20 +++++++++-----------
 1 files changed, 9 insertions(+), 11 deletions(-)

diff --git a/arch/mips/kernel/traps.c b/arch/mips/kernel/traps.c
index 549cbb8..303f008 100644
--- a/arch/mips/kernel/traps.c
+++ b/arch/mips/kernel/traps.c
@@ -158,7 +158,7 @@ static void show_stacktrace(struct task_
 	show_backtrace(task, regs);
 }
 
-static noinline void prepare_frametrace(struct pt_regs *regs)
+static __always_inline void prepare_frametrace(struct pt_regs *regs)
 {
 	__asm__ __volatile__(
 		"1: la $2, 1b\n\t"
@@ -200,17 +200,15 @@ void show_stack(struct task_struct *task
  */
 void dump_stack(void)
 {
-	unsigned long stack;
+	struct pt_regs regs;
 
-#ifdef CONFIG_KALLSYMS
-	if (!raw_show_trace) {
-		struct pt_regs regs;
-		prepare_frametrace(&regs);
-		show_backtrace(current, &regs);
-		return;
-	}
-#endif
-	show_raw_backtrace(&stack);
+	/*
+	 * Remove any garbage that may be in regs (specially func
+	 * addresses) to avoid show_raw_backtrace() to report them
+	 */
+	memset(&regs, 0, sizeof(regs));
+	prepare_frametrace(&regs);
+	show_backtrace(current, &regs);
 }
 
 EXPORT_SYMBOL(dump_stack);
-- 
1.4.2.rc2

[PATCH 6/7] Make get_frame_info() more robust

[Franck Bui-Huu]

Now get_frame_info() wants to detect move sp instruction first. It
assumes that the save ra in the stack instruction can't happen
before allocating frame size space into the stack.

Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
 arch/mips/kernel/process.c |   14 ++++++--------
 1 files changed, 6 insertions(+), 8 deletions(-)

diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index da332d7..309bfa4 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -321,17 +321,15 @@ static int get_frame_info(struct mips_fr
 
 		if (is_jal_jalr_jr_ins(ip))
 			break;
-		if (is_sp_move_ins(ip)) {
-			if (info->frame_size)
-				continue;
-			info->frame_size = - ip->i_format.simmediate;
+		if (!info->frame_size) {
+			if (is_sp_move_ins(ip))
+				info->frame_size = - ip->i_format.simmediate;
+			continue;
 		}
-
-		if (is_ra_save_ins(ip)) {
-			if (info->pc_offset != -1)
-				continue;
+		if (info->pc_offset == -1 && is_ra_save_ins(ip)) {
 			info->pc_offset =
 				ip->i_format.simmediate / sizeof(long);
+			break;
 		}
 	}
 	if (info->frame_size && info->pc_offset >= 0) /* nested */
-- 
1.4.2.rc2

[PATCH 7/7] Improve unwind_stack()

[Franck Bui-Huu]

This patch allows unwind_stack() to return ra for leaf function.
But it tries to detects cases where get_frame_info() wrongly
consider nested function as a leaf one.

It also pass 'unsinged long *sp' instead of 'unsigned long **sp'
as second parameter. The code looks cleaner.

Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
 arch/mips/kernel/process.c |   35 ++++++++++++++++++++++-------------
 arch/mips/kernel/traps.c   |   24 ++++++++++++------------
 2 files changed, 34 insertions(+), 25 deletions(-)

diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index 309bfa4..951bf9c 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -448,15 +448,16 @@ #endif
 }
 
 #ifdef CONFIG_KALLSYMS
-/* used by show_frametrace() */
-unsigned long unwind_stack(struct task_struct *task,
-			   unsigned long **sp, unsigned long pc)
+/* used by show_backtrace() */
+unsigned long unwind_stack(struct task_struct *task, unsigned long *sp,
+			   unsigned long pc, unsigned long ra)
 {
 	unsigned long stack_page;
 	struct mips_frame_info info;
 	char *modname;
 	char namebuf[KSYM_NAME_LEN + 1];
 	unsigned long size, ofs;
+	int leaf;
 
 	stack_page = (unsigned long)task_stack_page(task);
 	if (!stack_page)
@@ -469,18 +470,26 @@ unsigned long unwind_stack(struct task_s
 
 	info.func = (void *)(pc - ofs);
 	info.func_size = ofs;	/* analyze from start to ofs */
-	if (get_frame_info(&info)) {
-		/* leaf or unknown */
-		*sp += info.frame_size / sizeof(long);
+	leaf = get_frame_info(&info);
+	if (leaf < 0)
 		return 0;
-	}
-	if ((unsigned long)*sp < stack_page ||
-	    (unsigned long)*sp + info.frame_size / sizeof(long) >
-	    stack_page + THREAD_SIZE - 32)
+
+	if (*sp < stack_page ||
+	    *sp + info.frame_size > stack_page + THREAD_SIZE - 32)
 		return 0;
 
-	pc = (*sp)[info.pc_offset];
-	*sp += info.frame_size / sizeof(long);
-	return pc;
+	if (leaf)
+		/*
+		 * For some extreme cases, get_frame_info() can
+		 * consider wrongly a nested function as a leaf
+		 * one. In that cases avoid to return always the
+		 * same value.
+		 */
+		pc = pc != ra ? ra : 0;
+	else
+		pc = ((unsigned long *)(*sp))[info.pc_offset];
+
+	*sp += info.frame_size;
+	return __kernel_text_address(pc) ? pc : 0;
 }
 #endif
diff --git a/arch/mips/kernel/traps.c b/arch/mips/kernel/traps.c
index 303f008..ab77034 100644
--- a/arch/mips/kernel/traps.c
+++ b/arch/mips/kernel/traps.c
@@ -74,8 +74,9 @@ void (*board_ejtag_handler_setup)(void);
 void (*board_bind_eic_interrupt)(int irq, int regset);
 
 
-static void show_raw_backtrace(unsigned long *sp)
+static void show_raw_backtrace(unsigned long reg29)
 {
+	unsigned long *sp = (unsigned long *)reg29;
 	unsigned long addr;
 
 	printk("Call Trace:");
@@ -99,30 +100,29 @@ static int __init set_raw_show_trace(cha
 }
 __setup("raw_show_trace", set_raw_show_trace);
 
-extern unsigned long unwind_stack(struct task_struct *task,
-				  unsigned long **sp, unsigned long pc);
+extern unsigned long unwind_stack(struct task_struct *task, unsigned long *sp,
+				  unsigned long pc, unsigned long ra);
+
 static void show_backtrace(struct task_struct *task, struct pt_regs *regs)
 {
-	unsigned long *sp = (long *)regs->regs[29];
+	unsigned long sp = regs->regs[29];
+	unsigned long ra = regs->regs[31];
 	unsigned long pc = regs->cp0_epc;
-	int top = 1;
 
 	if (raw_show_trace || !__kernel_text_address(pc)) {
 		show_raw_backtrace(sp);
 		return;
 	}
 	printk("Call Trace:\n");
-	while (__kernel_text_address(pc)) {
+	do {
 		print_ip_sym(pc);
-		pc = unwind_stack(task, &sp, pc);
-		if (top && pc == 0)
-			pc = regs->regs[31];	/* leaf? */
-		top = 0;
-	}
+		pc = unwind_stack(task, &sp, pc, ra);
+		ra = 0;
+	} while (pc);
 	printk("\n");
 }
 #else
-#define show_backtrace(task, r) show_raw_backtrace((long *)(r)->regs[29]);
+#define show_backtrace(task, r) show_raw_backtrace((r)->regs[29]);
 #endif
 
 /*
-- 
1.4.2.rc2

Re: [PATCH 0/7] Improve prologue analysis code (take #2)

[Atsushi Nemoto]

On Thu,  3 Aug 2006 09:29:14 +0200, Franck Bui-Huu <vagabon.xyz@gmail.com> wrote:
> This patch set clean up or improves this part of code. I splitted out
> this into 7 patches to make the review easier.
> 
> This second try takes into account all feedbacks from Atsushi Nemoto.

Thanks for your good job.  All good for me.

Ralf, this patchset includes all floating patches from me.  Please
take this and drop mine.

---
Atsushi Nemoto

Re: [PATCH 0/7] Improve prologue analysis code (take #2)

[Ralf Baechle]

On Thu, Aug 03, 2006 at 09:29:14AM +0200, Franck Bui-Huu wrote:

> This patch set clean up or improves this part of code. I splitted out
> this into 7 patches to make the review easier.
> 
> This second try takes into account all feedbacks from Atsushi Nemoto.

Thanks, whole series queued.

  Ralf