[PATCH 0/2] MIPS: oprofile: callgraph support

[PATCH 0/2] MIPS: oprofile: callgraph support

[Gergely Kis]

From: Daniel Kalmar <kalmard@homejinni.com>

These patches add callgraph/backtrace support to oprofile on MIPS.

Stack unwinding is done by code examination. For kernelspace, the
already existing unwind function is utilized that uses kallsyms to
quickly find the beginning of functions. For userspace a new function
was added that examines code at and before the pc.

Daniel Kalmar (2):
  MIPS: Add unwind_stack_by_address to support unwinding from any
    kernel code address
  MIPS: oprofile: Add callgraph support

 arch/mips/include/asm/stacktrace.h |    4 +
 arch/mips/kernel/process.c         |   18 +++-
 arch/mips/oprofile/Makefile        |    2 +-
 arch/mips/oprofile/backtrace.c     |  173 ++++++++++++++++++++++++++++++++++++
 arch/mips/oprofile/common.c        |    1 +
 arch/mips/oprofile/op_impl.h       |    2 +
 6 files changed, 194 insertions(+), 6 deletions(-)
 create mode 100644 arch/mips/oprofile/backtrace.c

[PATCH 1/2] MIPS: Add new unwind_stack variant

[Gergely Kis]

From: Daniel Kalmar <kalmard@homejinni.com>

The unwind_stack_by_address variant supports unwinding based
on any kernel code address.
This symbol is also exported so it can be called from modules.

Signed-off-by: Daniel Kalmar <kalmard@homejinni.com>
Signed-off-by: Gergely Kis <gergely@homejinni.com>
---
 arch/mips/include/asm/stacktrace.h |    4 ++++
 arch/mips/kernel/process.c         |   18 +++++++++++++-----
 2 files changed, 17 insertions(+), 5 deletions(-)

diff --git a/arch/mips/include/asm/stacktrace.h b/arch/mips/include/asm/stacktrace.h
index 0bf8281..780ee2c 100644
--- a/arch/mips/include/asm/stacktrace.h
+++ b/arch/mips/include/asm/stacktrace.h
@@ -7,6 +7,10 @@
 extern int raw_show_trace;
 extern unsigned long unwind_stack(struct task_struct *task, unsigned long *sp,
 				  unsigned long pc, unsigned long *ra);
+extern unsigned long unwind_stack_by_address(unsigned long stack_page,
+					     unsigned long *sp,
+					     unsigned long pc,
+					     unsigned long *ra);
 #else
 #define raw_show_trace 1
 static inline unsigned long unwind_stack(struct task_struct *task,
diff --git a/arch/mips/kernel/process.c b/arch/mips/kernel/process.c
index d2112d3..0acb274 100644
--- a/arch/mips/kernel/process.c
+++ b/arch/mips/kernel/process.c
@@ -373,18 +373,18 @@ unsigned long thread_saved_pc(struct task_struct *tsk)
 
 
 #ifdef CONFIG_KALLSYMS
-/* used by show_backtrace() */
-unsigned long unwind_stack(struct task_struct *task, unsigned long *sp,
-			   unsigned long pc, unsigned long *ra)
+/* generic stack unwinding function */
+unsigned long notrace unwind_stack_by_address(unsigned long stack_page,
+					      unsigned long *sp,
+					      unsigned long pc,
+					      unsigned long *ra)
 {
-	unsigned long stack_page;
 	struct mips_frame_info info;
 	unsigned long size, ofs;
 	int leaf;
 	extern void ret_from_irq(void);
 	extern void ret_from_exception(void);
 
-	stack_page = (unsigned long)task_stack_page(task);
 	if (!stack_page)
 		return 0;
 
@@ -443,6 +443,14 @@ unsigned long unwind_stack(struct task_struct *task, unsigned long *sp,
 	*ra = 0;
 	return __kernel_text_address(pc) ? pc : 0;
 }
+EXPORT_SYMBOL(unwind_stack_by_address);
+
+/* 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 = (unsigned long)task_stack_page(task);
+	return unwind_stack_by_address(stack_page, sp, pc, ra);
+}
 #endif
 
 /*
-- 
1.7.0.4

[PATCH 2/2] MIPS: oprofile: Add callgraph support

[Gergely Kis]

From: Daniel Kalmar <kalmard@homejinni.com>

Stack unwinding is done by code examination. For kernelspace, the
already existing unwind function is utilized that uses kallsyms to
quickly find the beginning of functions. For userspace a new function
was added that examines code at and before the pc.

Signed-off-by: Daniel Kalmar <kalmard@homejinni.com>
Signed-off-by: Gergely Kis <gergely@homejinni.com>
---
 arch/mips/oprofile/Makefile    |    2 +-
 arch/mips/oprofile/backtrace.c |  173 ++++++++++++++++++++++++++++++++++++++++
 arch/mips/oprofile/common.c    |    1 +
 arch/mips/oprofile/op_impl.h   |    2 +
 4 files changed, 177 insertions(+), 1 deletions(-)
 create mode 100644 arch/mips/oprofile/backtrace.c

diff --git a/arch/mips/oprofile/Makefile b/arch/mips/oprofile/Makefile
index 4b9d704..29f2f13 100644
--- a/arch/mips/oprofile/Makefile
+++ b/arch/mips/oprofile/Makefile
@@ -8,7 +8,7 @@ DRIVER_OBJS = $(addprefix ../../../drivers/oprofile/, \
 		oprofilefs.o oprofile_stats.o \
 		timer_int.o )
 
-oprofile-y				:= $(DRIVER_OBJS) common.o
+oprofile-y				:= $(DRIVER_OBJS) common.o backtrace.o
 
 oprofile-$(CONFIG_CPU_MIPS32)		+= op_model_mipsxx.o
 oprofile-$(CONFIG_CPU_MIPS64)		+= op_model_mipsxx.o
diff --git a/arch/mips/oprofile/backtrace.c b/arch/mips/oprofile/backtrace.c
new file mode 100644
index 0000000..d508e9e
--- /dev/null
+++ b/arch/mips/oprofile/backtrace.c
@@ -0,0 +1,173 @@
+#include <linux/oprofile.h>
+#include <linux/sched.h>
+#include <linux/mm.h>
+#include <linux/uaccess.h>
+#include <asm/ptrace.h>
+#include <asm/stacktrace.h>
+#include <linux/stacktrace.h>
+#include <linux/kernel.h>
+#include <asm/sections.h>
+#include <asm/inst.h>
+
+struct stackframe {
+	unsigned long sp;
+	unsigned long pc;
+	unsigned long ra;
+};
+
+static inline int get_mem(unsigned long addr, unsigned long *result)
+{
+	unsigned long *address = (unsigned long *) addr;
+	if (!access_ok(VERIFY_READ, addr, sizeof(unsigned long)))
+		return -1;
+	if (__copy_from_user_inatomic(result, address, sizeof(unsigned long)))
+		return -3;
+	return 0;
+}
+
+/*
+ * These two instruction helpers were taken from process.c
+ */
+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_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;
+}
+
+/*
+ * Looks for specific instructions that mark the end of a function.
+ * This usually means we ran into the code area of the previous function.
+ */
+static inline int is_end_of_function_marker(union mips_instruction *ip)
+{
+	/* jr ra */
+	if (ip->r_format.func == jr_op && ip->r_format.rs == 31)
+		return 1;
+	/* lui gp */
+	if (ip->i_format.opcode == lui_op && ip->i_format.rt == 28)
+		return 1;
+	return 0;
+}
+
+/*
+ * TODO for userspace stack unwinding:
+ * - handle cases where the stack is adjusted inside a function
+ *     (generally doesn't happen)
+ * - find optimal value for max_instr_check
+ * - try to find a way to handle leaf functions
+ */
+
+static inline int unwind_user_frame(struct stackframe *old_frame,
+				    const unsigned int max_instr_check)
+{
+	struct stackframe new_frame = *old_frame;
+	off_t ra_offset = 0;
+	size_t stack_size = 0;
+	unsigned long addr;
+
+	if (old_frame->pc == 0 || old_frame->sp == 0 || old_frame->ra == 0)
+		return -9;
+
+	for (addr = new_frame.pc; (addr + max_instr_check > new_frame.pc)
+		&& (!ra_offset || !stack_size); --addr) {
+		union mips_instruction ip;
+
+		if (get_mem(addr, (unsigned long *) &ip))
+			return -11;
+
+		if (is_sp_move_ins(&ip)) {
+			int stack_adjustment = ip.i_format.simmediate;
+			if (stack_adjustment > 0)
+				/* This marks the end of the previous function,
+				   which means we overran. */
+				break;
+			stack_size = (unsigned) stack_adjustment;
+		} else if (is_ra_save_ins(&ip)) {
+			int ra_slot = ip.i_format.simmediate;
+			if (ra_slot < 0)
+				/* This shouldn't happen. */
+				break;
+			ra_offset = ra_slot;
+		} else if (is_end_of_function_marker(&ip))
+			break;
+	}
+
+	if (!ra_offset || !stack_size)
+		return -1;
+
+	if (ra_offset) {
+		new_frame.ra = old_frame->sp + ra_offset;
+		if (get_mem(new_frame.ra, &(new_frame.ra)))
+			return -13;
+	}
+
+	if (stack_size) {
+		new_frame.sp = old_frame->sp + stack_size;
+		if (get_mem(new_frame.sp, &(new_frame.sp)))
+			return -14;
+	}
+
+	if (new_frame.sp > old_frame->sp)
+		return -2;
+
+	new_frame.pc = old_frame->ra;
+	*old_frame = new_frame;
+
+	return 0;
+}
+
+static inline void do_user_backtrace(unsigned long low_addr,
+				     struct stackframe *frame,
+				     unsigned int depth) {
+	const unsigned int max_instr_check = 512;
+	const unsigned long high_addr = low_addr + THREAD_SIZE;
+
+	while (depth-- && !unwind_user_frame(frame, max_instr_check)) {
+		oprofile_add_trace(frame->ra);
+		if (frame->sp < low_addr || frame->sp > high_addr)
+			break;
+	}
+}
+
+#ifndef CONFIG_KALLSYMS
+static inline void do_kernel_backtrace(unsigned long low_addr,
+				       struct stackframe *frame,
+				       unsigned int depth) { }
+#else
+static inline void do_kernel_backtrace(unsigned long low_addr,
+				       struct stackframe *frame,
+				       unsigned int depth) {
+	while (depth-- && frame->pc) {
+		frame->pc = unwind_stack_by_address(low_addr,
+						    &(frame->sp),
+						    frame->pc,
+						    &(frame->ra));
+		oprofile_add_trace(frame->ra);
+	}
+}
+#endif
+
+void notrace op_mips_backtrace(struct pt_regs *const regs, unsigned int depth)
+{
+	struct stackframe frame = { .sp = regs->regs[29],
+				    .pc = regs->cp0_epc,
+				    .ra = regs->regs[31] };
+	const int userspace = user_mode(regs);
+	const unsigned long low_addr = ALIGN(frame.sp, THREAD_SIZE);
+
+	if (userspace)
+		do_user_backtrace(low_addr, &frame, depth);
+	else
+		do_kernel_backtrace(low_addr, &frame, depth);
+}
diff --git a/arch/mips/oprofile/common.c b/arch/mips/oprofile/common.c
index f9eb1ab..d1f2d4c 100644
--- a/arch/mips/oprofile/common.c
+++ b/arch/mips/oprofile/common.c
@@ -115,6 +115,7 @@ int __init oprofile_arch_init(struct oprofile_operations *ops)
 	ops->start		= op_mips_start;
 	ops->stop		= op_mips_stop;
 	ops->cpu_type		= lmodel->cpu_type;
+	ops->backtrace		= op_mips_backtrace;
 
 	printk(KERN_INFO "oprofile: using %s performance monitoring.\n",
 	       lmodel->cpu_type);
diff --git a/arch/mips/oprofile/op_impl.h b/arch/mips/oprofile/op_impl.h
index f04b54f..7c2da27 100644
--- a/arch/mips/oprofile/op_impl.h
+++ b/arch/mips/oprofile/op_impl.h
@@ -36,4 +36,6 @@ struct op_mips_model {
 	unsigned char num_counters;
 };
 
+void op_mips_backtrace(struct pt_regs * const regs, unsigned int depth);
+
 #endif
-- 
1.7.0.4

Re: [PATCH 0/2] MIPS: oprofile: callgraph support

[Robert Richter]

On 13.05.11 08:38:03, Gergely Kis wrote:
> From: Daniel Kalmar <kalmard@homejinni.com>
> 
> These patches add callgraph/backtrace support to oprofile on MIPS.
> 
> Stack unwinding is done by code examination. For kernelspace, the
> already existing unwind function is utilized that uses kallsyms to
> quickly find the beginning of functions. For userspace a new function
> was added that examines code at and before the pc.
> 
> Daniel Kalmar (2):
>   MIPS: Add unwind_stack_by_address to support unwinding from any
>     kernel code address
>   MIPS: oprofile: Add callgraph support
> 
>  arch/mips/include/asm/stacktrace.h |    4 +
>  arch/mips/kernel/process.c         |   18 +++-
>  arch/mips/oprofile/Makefile        |    2 +-
>  arch/mips/oprofile/backtrace.c     |  173 ++++++++++++++++++++++++++++++++++++
>  arch/mips/oprofile/common.c        |    1 +
>  arch/mips/oprofile/op_impl.h       |    2 +
>  6 files changed, 194 insertions(+), 6 deletions(-)
>  create mode 100644 arch/mips/oprofile/backtrace.c

Daniel and Gergely,

the patches look good so far. I fixed the coding style to have the
opening brace of functions at the beginning of the next line. After
the MIPS maintainer's ack I will apply them to the oprofile tree.

Thanks for your contribution.

Ralf,

please ack.

Thanks,

-Robert

-- 
Advanced Micro Devices, Inc.
Operating System Research Center

Re: [PATCH 0/2] MIPS: oprofile: callgraph support

[Gergely Kis]

Dear Ralf,

Did you have a chance to look at our oprofile callgraph patch?

Thank you,
Gergely

On Tue, May 24, 2011 at 10:42 AM, Robert Richter <robert.richter@amd.com> wrote:
> On 13.05.11 08:38:03, Gergely Kis wrote:
>> From: Daniel Kalmar <kalmard@homejinni.com>
>>
>> These patches add callgraph/backtrace support to oprofile on MIPS.
>>
>> Stack unwinding is done by code examination. For kernelspace, the
>> already existing unwind function is utilized that uses kallsyms to
>> quickly find the beginning of functions. For userspace a new function
>> was added that examines code at and before the pc.
>>
>> Daniel Kalmar (2):
>>   MIPS: Add unwind_stack_by_address to support unwinding from any
>>     kernel code address
>>   MIPS: oprofile: Add callgraph support
>>
>>  arch/mips/include/asm/stacktrace.h |    4 +
>>  arch/mips/kernel/process.c         |   18 +++-
>>  arch/mips/oprofile/Makefile        |    2 +-
>>  arch/mips/oprofile/backtrace.c     |  173 ++++++++++++++++++++++++++++++++++++
>>  arch/mips/oprofile/common.c        |    1 +
>>  arch/mips/oprofile/op_impl.h       |    2 +
>>  6 files changed, 194 insertions(+), 6 deletions(-)
>>  create mode 100644 arch/mips/oprofile/backtrace.c
>
> Daniel and Gergely,
>
> the patches look good so far. I fixed the coding style to have the
> opening brace of functions at the beginning of the next line. After
> the MIPS maintainer's ack I will apply them to the oprofile tree.
>
> Thanks for your contribution.
>
> Ralf,
>
> please ack.
>
> Thanks,
>
> -Robert
>
> --
> Advanced Micro Devices, Inc.
> Operating System Research Center
>
>

Re: [PATCH 0/2] MIPS: oprofile: callgraph support

[Robert Richter]

On 24.05.11 10:42:50, Robert Richter wrote:
> On 13.05.11 08:38:03, Gergely Kis wrote:
> > From: Daniel Kalmar <kalmard@homejinni.com>
> > 
> > These patches add callgraph/backtrace support to oprofile on MIPS.
> > 
> > Stack unwinding is done by code examination. For kernelspace, the
> > already existing unwind function is utilized that uses kallsyms to
> > quickly find the beginning of functions. For userspace a new function
> > was added that examines code at and before the pc.
> > 
> > Daniel Kalmar (2):
> >   MIPS: Add unwind_stack_by_address to support unwinding from any
> >     kernel code address
> >   MIPS: oprofile: Add callgraph support
> > 
> >  arch/mips/include/asm/stacktrace.h |    4 +
> >  arch/mips/kernel/process.c         |   18 +++-
> >  arch/mips/oprofile/Makefile        |    2 +-
> >  arch/mips/oprofile/backtrace.c     |  173 ++++++++++++++++++++++++++++++++++++
> >  arch/mips/oprofile/common.c        |    1 +
> >  arch/mips/oprofile/op_impl.h       |    2 +
> >  6 files changed, 194 insertions(+), 6 deletions(-)
> >  create mode 100644 arch/mips/oprofile/backtrace.c

If there are no objections I will apply the patches next week to the
oprofile tree.

Thanks, 

-Robert

-- 
Advanced Micro Devices, Inc.
Operating System Research Center

Re: [PATCH 0/2] MIPS: oprofile: callgraph support

[Robert Richter]

On 10.06.11 14:35:57, Robert Richter wrote:
> On 24.05.11 10:42:50, Robert Richter wrote:
> > On 13.05.11 08:38:03, Gergely Kis wrote:
> > > From: Daniel Kalmar <kalmard@homejinni.com>
> > > 
> > > These patches add callgraph/backtrace support to oprofile on MIPS.
> > > 
> > > Stack unwinding is done by code examination. For kernelspace, the
> > > already existing unwind function is utilized that uses kallsyms to
> > > quickly find the beginning of functions. For userspace a new function
> > > was added that examines code at and before the pc.
> > > 
> > > Daniel Kalmar (2):
> > >   MIPS: Add unwind_stack_by_address to support unwinding from any
> > >     kernel code address
> > >   MIPS: oprofile: Add callgraph support
> > > 
> > >  arch/mips/include/asm/stacktrace.h |    4 +
> > >  arch/mips/kernel/process.c         |   18 +++-
> > >  arch/mips/oprofile/Makefile        |    2 +-
> > >  arch/mips/oprofile/backtrace.c     |  173 ++++++++++++++++++++++++++++++++++++
> > >  arch/mips/oprofile/common.c        |    1 +
> > >  arch/mips/oprofile/op_impl.h       |    2 +
> > >  6 files changed, 194 insertions(+), 6 deletions(-)
> > >  create mode 100644 arch/mips/oprofile/backtrace.c
> 
> If there are no objections I will apply the patches next week to the
> oprofile tree.

Applied to oprofile/core. Thanks Daniel.

-Robert

-- 
Advanced Micro Devices, Inc.
Operating System Research Center