[PATCH v7 0/6] arm64: ftrace: fix incorrect output from stack tracer

[PATCH v7 0/6] arm64: ftrace: fix incorrect output from stack tracer

[AKASHI Takahiro]

This is the seventh patch series to fix ftrace-based stack tracer on
arm64. The original issue was reported by Jungseok[1], and then I found
more issues[2].

We don't have to care about the original issue any more because the root
cause (patch "ARM64: unwind: Fix PC calculation") has been reverted in
v4.3.

Among the issues in [2], this patchset will address
- II-1(slurping stack)
- II-2(differences between x86 and arm64) and
- II-4(functions under function_graph tracer).
but not
- II-3(interrupted frame):
  Recent discussions[3] about introducing a dedicated interrupt stack
  suggests that we can avoid walking through from interrupt stack to
  process stack.
  (Please note that, even on x86, interrupt stack is not supported by
  stack tracer.)

  So recent interrupt-stack patch[4] is a prerequisite here.

- II-5(leaf function):
  I don't remember why I thought this was a problem, but anyhow "-pg"
  seems to disable omit-leaf-stack-frame.

Consequently, this patch series can now be partitioned into two almost
indepedent sets, function_graph-related patch 1-3 and stack tracer
specific patch 4-6.

patch1 is a proactive improvement of function_graph tracer. 
patch2 and 3 correspond to II-4(functions under function_graph tracer).
patch4, 5 and 6 correspond to II-1(slurping stack) and II-2(differences
between x86 and arm64).
patch6 is a function prologue analyzer test. This won't attest
the correctness of the functionality, but it can be used for sanity check
that all the traced functions are properly analyzed.

I tested the code with v4.4-rc4 + Jungseok's/James' patch v7[4].


Changes from v6:
- fixed dump_stacktrace() to show correct stack traces under function graph
  tracer.(patch 3) Fix in previous version was not complete.
- fixed 'eret' instruction encoding and changed some functions' names
  for consistency.(patch 4)
- added OK/NG field in function prologue test results.(patch 6)

Changes from v5:
- removed a patch ("ftrace: allow arch-specific stack tracer")
  which is already in v4.4-rc1
- handle a "return_to_handler" entry in call stack lists in more commonr
  way by fixing such entries in unwind_frame(). This will cover all
  the cases, a) stack tracer, b) perf call graph and c) dump_backtrace.
  (patch 2, 3)
- fixed aarch64_insn_is_eret(). Thanks to Jungseok. (patch 4)
- removed some hunks (offseting AARCH64_INSN_SIZE) due to having reverted
  a patch ("ARM64: unwind: Fix PC calculation") (patch 3)
- fixed function prologue analyzer on big-endian kernel. Thanks to Yalin.
  (patch 5)
- fixed a stack size of the top function in stack tracer's output
  (its size was reported 16 bytes bigger than actual size due to
   mishandled ftrace_caller.) (patch 3)

Changes from v4:
- removed a patch("arm64: ftrace: adjust callsite addresses examined
		by stack tracer")
- added a function prologue analyzer test(patch 6)

Changes from v3:
- fixed build errors/warnings reported by kbuild test robot
- addressed Steven's comments around check_stack()
- removed a patch ("arm64: ftrace: allow for tracing leaf functions")
  I don't remember why I thought this was necessary, but anyhow "-pg" seems
  to disable omit-leaf-stack-frame.

[1] http://lists.infradead.org/pipermail/linux-arm-kernel/2015-July/354126.html
[2] http://lists.infradead.org/pipermail/linux-arm-kernel/2015-September/369316.html
[3] http://lists.infradead.org/pipermail/linux-arm-kernel/2015-September/368003.html
[4] http://lists.infradead.org/pipermail/linux-arm-kernel/2015-November/385337.html

AKASHI Takahiro (6):
  arm64: ftrace: modify a stack frame in a safe way
  arm64: pass a task parameter to unwind_frame()
  arm64: ftrace: fix a stack tracer's output under function graph
    tracer
  arm64: insn: add instruction decoders for ldp/stp and add/sub
  arm64: ftrace: add arch-specific stack tracer
  arm64: ftrace: add a test of function prologue analyzer

 arch/arm64/include/asm/ftrace.h     |    4 +-
 arch/arm64/include/asm/insn.h       |   18 +++
 arch/arm64/include/asm/stacktrace.h |   13 +-
 arch/arm64/kernel/ftrace.c          |   75 +++++++++-
 arch/arm64/kernel/insn.c            |  128 +++++++++++++++--
 arch/arm64/kernel/perf_callchain.c  |    5 +-
 arch/arm64/kernel/process.c         |    5 +-
 arch/arm64/kernel/return_address.c  |    5 +-
 arch/arm64/kernel/stacktrace.c      |  268 ++++++++++++++++++++++++++++++++++-
 arch/arm64/kernel/time.c            |    5 +-
 arch/arm64/kernel/traps.c           |   28 +++-
 11 files changed, 518 insertions(+), 36 deletions(-)

-- 
1.7.9.5

[PATCH v7 1/6] arm64: ftrace: modify a stack frame in a safe way

[AKASHI Takahiro]

Function graph tracer modifies a return address (LR) in a stack frame by
calling ftrace_prepare_return() in a traced function's function prologue.
The current code does this modification before preserving an original
address at ftrace_push_return_trace() and there is always a small window
of inconsistency when an interrupt occurs.

This doesn't matter, as far as an interrupt stack is introduced, because
stack tracer won't be invoked in an interrupt context. But it would be
better to proactively minimize such a window by moving the LR modification
after ftrace_push_return_trace().

Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 arch/arm64/kernel/ftrace.c |   11 ++++-------
 1 file changed, 4 insertions(+), 7 deletions(-)

diff --git a/arch/arm64/kernel/ftrace.c b/arch/arm64/kernel/ftrace.c
index c851be7..314f82d 100644
--- a/arch/arm64/kernel/ftrace.c
+++ b/arch/arm64/kernel/ftrace.c
@@ -125,23 +125,20 @@ void prepare_ftrace_return(unsigned long *parent, unsigned long self_addr,
 	 * on other archs. It's unlikely on AArch64.
 	 */
 	old = *parent;
-	*parent = return_hooker;
 
 	trace.func = self_addr;
 	trace.depth = current->curr_ret_stack + 1;
 
 	/* Only trace if the calling function expects to */
-	if (!ftrace_graph_entry(&trace)) {
-		*parent = old;
+	if (!ftrace_graph_entry(&trace))
 		return;
-	}
 
 	err = ftrace_push_return_trace(old, self_addr, &trace.depth,
 				       frame_pointer);
-	if (err == -EBUSY) {
-		*parent = old;
+	if (err == -EBUSY)
 		return;
-	}
+	else
+		*parent = return_hooker;
 }
 
 #ifdef CONFIG_DYNAMIC_FTRACE
-- 
1.7.9.5

[PATCH v7 2/6] arm64: pass a task parameter to unwind_frame()

[AKASHI Takahiro]

Function graph tracer modifies a return address (LR) in a stack frame
to hook a function's return. This will result in many useless entries
(return_to_handler) showing up in a call stack list.
We will fix this problem in a later patch ("arm64: ftrace: fix a stack
tracer's output under function graph tracer"). But since real return
addresses are saved in ret_stack[] array in struct task_struct,
unwind functions need to be notified of, in addition to a stack pointer
address, which task is being traced in order to find out real return
addresses.

This patch extends unwind functions' interfaces by adding an extra
argument of a pointer to task_struct.

Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 arch/arm64/include/asm/stacktrace.h |    6 ++++--
 arch/arm64/kernel/perf_callchain.c  |    2 +-
 arch/arm64/kernel/process.c         |    2 +-
 arch/arm64/kernel/return_address.c  |    2 +-
 arch/arm64/kernel/stacktrace.c      |    8 ++++----
 arch/arm64/kernel/time.c            |    2 +-
 arch/arm64/kernel/traps.c           |    2 +-
 7 files changed, 13 insertions(+), 11 deletions(-)

diff --git a/arch/arm64/include/asm/stacktrace.h b/arch/arm64/include/asm/stacktrace.h
index 7318f6d..6fb61c5 100644
--- a/arch/arm64/include/asm/stacktrace.h
+++ b/arch/arm64/include/asm/stacktrace.h
@@ -16,14 +16,16 @@
 #ifndef __ASM_STACKTRACE_H
 #define __ASM_STACKTRACE_H
 
+struct task_struct;
+
 struct stackframe {
 	unsigned long fp;
 	unsigned long sp;
 	unsigned long pc;
 };
 
-extern int unwind_frame(struct stackframe *frame);
-extern void walk_stackframe(struct stackframe *frame,
+extern int unwind_frame(struct task_struct *tsk, struct stackframe *frame);
+extern void walk_stackframe(struct task_struct *tsk, struct stackframe *frame,
 			    int (*fn)(struct stackframe *, void *), void *data);
 
 #endif	/* __ASM_STACKTRACE_H */
diff --git a/arch/arm64/kernel/perf_callchain.c b/arch/arm64/kernel/perf_callchain.c
index 3aa7483..797220d 100644
--- a/arch/arm64/kernel/perf_callchain.c
+++ b/arch/arm64/kernel/perf_callchain.c
@@ -165,7 +165,7 @@ void perf_callchain_kernel(struct perf_callchain_entry *entry,
 	frame.sp = regs->sp;
 	frame.pc = regs->pc;
 
-	walk_stackframe(&frame, callchain_trace, entry);
+	walk_stackframe(current, &frame, callchain_trace, entry);
 }
 
 unsigned long perf_instruction_pointer(struct pt_regs *regs)
diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index f75b540..98bf546 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -348,7 +348,7 @@ unsigned long get_wchan(struct task_struct *p)
 	do {
 		if (frame.sp < stack_page ||
 		    frame.sp >= stack_page + THREAD_SIZE ||
-		    unwind_frame(&frame))
+		    unwind_frame(p, &frame))
 			return 0;
 		if (!in_sched_functions(frame.pc))
 			return frame.pc;
diff --git a/arch/arm64/kernel/return_address.c b/arch/arm64/kernel/return_address.c
index 6c4fd28..07b37ac 100644
--- a/arch/arm64/kernel/return_address.c
+++ b/arch/arm64/kernel/return_address.c
@@ -44,7 +44,7 @@ void *return_address(unsigned int level)
 	frame.sp = current_stack_pointer;
 	frame.pc = (unsigned long)return_address; /* dummy */
 
-	walk_stackframe(&frame, save_return_addr, &data);
+	walk_stackframe(current, &frame, save_return_addr, &data);
 
 	if (!data.level)
 		return data.addr;
diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index a159851..9c7acf8 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -36,7 +36,7 @@
  *	ldp	x29, x30, [sp]
  *	add	sp, sp, #0x10
  */
-int notrace unwind_frame(struct stackframe *frame)
+int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 {
 	unsigned long high, low;
 	unsigned long fp = frame->fp;
@@ -78,7 +78,7 @@ int notrace unwind_frame(struct stackframe *frame)
 	return 0;
 }
 
-void notrace walk_stackframe(struct stackframe *frame,
+void notrace walk_stackframe(struct task_struct *tsk, struct stackframe *frame,
 		     int (*fn)(struct stackframe *, void *), void *data)
 {
 	while (1) {
@@ -86,7 +86,7 @@ void notrace walk_stackframe(struct stackframe *frame,
 
 		if (fn(frame, data))
 			break;
-		ret = unwind_frame(frame);
+		ret = unwind_frame(tsk, frame);
 		if (ret < 0)
 			break;
 	}
@@ -138,7 +138,7 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
 		frame.pc = (unsigned long)save_stack_trace_tsk;
 	}
 
-	walk_stackframe(&frame, save_trace, &data);
+	walk_stackframe(tsk, &frame, save_trace, &data);
 	if (trace->nr_entries < trace->max_entries)
 		trace->entries[trace->nr_entries++] = ULONG_MAX;
 }
diff --git a/arch/arm64/kernel/time.c b/arch/arm64/kernel/time.c
index 13339b6..6e5c521 100644
--- a/arch/arm64/kernel/time.c
+++ b/arch/arm64/kernel/time.c
@@ -53,7 +53,7 @@ unsigned long profile_pc(struct pt_regs *regs)
 	frame.sp = regs->sp;
 	frame.pc = regs->pc;
 	do {
-		int ret = unwind_frame(&frame);
+		int ret = unwind_frame(NULL, &frame);
 		if (ret < 0)
 			return 0;
 	} while (in_lock_functions(frame.pc));
diff --git a/arch/arm64/kernel/traps.c b/arch/arm64/kernel/traps.c
index cdfa2f9..da45224 100644
--- a/arch/arm64/kernel/traps.c
+++ b/arch/arm64/kernel/traps.c
@@ -177,7 +177,7 @@ static void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk)
 		int ret;
 
 		dump_backtrace_entry(where);
-		ret = unwind_frame(&frame);
+		ret = unwind_frame(tsk, &frame);
 		if (ret < 0)
 			break;
 		stack = frame.sp;
-- 
1.7.9.5

[PATCH v7 3/6] arm64: ftrace: fix a stack tracer's output under function graph tracer

[AKASHI Takahiro]

Function graph tracer modifies a return address (LR) in a stack frame
to hook a function return. This will result in many useless entries
(return_to_handler) showing up in
 a) a stack tracer's output
 b) perf call graph (with perf record -g)
 c) dump_backtrace (at panic et al.)

For example, in case of a),
  $ echo function_graph > /sys/kernel/debug/tracing/current_tracer
  $ echo 1 > /proc/sys/kernel/stack_trace_enabled
  $ cat /sys/kernel/debug/tracing/stack_trace
        Depth    Size   Location    (54 entries)
        -----    ----   --------
  0)     4504      16   gic_raise_softirq+0x28/0x150
  1)     4488      80   smp_cross_call+0x38/0xb8
  2)     4408      48   return_to_handler+0x0/0x40
  3)     4360      32   return_to_handler+0x0/0x40
  ...

In case of b),
  $ echo function_graph > /sys/kernel/debug/tracing/current_tracer
  $ perf record -e mem:XXX:x -ag -- sleep 10
  $ perf report
                  ...
                  |          |          |--0.22%-- 0x550f8
                  |          |          |          0x10888
                  |          |          |          el0_svc_naked
                  |          |          |          sys_openat
                  |          |          |          return_to_handler
                  |          |          |          return_to_handler
                  ...

In case of c),
  $ echo function_graph > /sys/kernel/debug/tracing/current_tracer
  $ echo c > /proc/sysrq-trigger
  ...
  Call trace:
  [<ffffffc00044d3ac>] sysrq_handle_crash+0x24/0x30
  [<ffffffc000092250>] return_to_handler+0x0/0x40
  [<ffffffc000092250>] return_to_handler+0x0/0x40
  ...

This patch replaces such entries with real addresses preserved in
current->ret_stack[] at unwind_frame(). This way, we can cover all
the cases.

Reviewed-by: Jungseok Lee <jungseoklee85@gmail.com>
Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 arch/arm64/include/asm/ftrace.h     |    2 ++
 arch/arm64/include/asm/stacktrace.h |    3 +++
 arch/arm64/kernel/perf_callchain.c  |    3 +++
 arch/arm64/kernel/process.c         |    3 +++
 arch/arm64/kernel/return_address.c  |    3 +++
 arch/arm64/kernel/stacktrace.c      |   17 +++++++++++++++++
 arch/arm64/kernel/time.c            |    3 +++
 arch/arm64/kernel/traps.c           |   26 ++++++++++++++++++++------
 8 files changed, 54 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/include/asm/ftrace.h b/arch/arm64/include/asm/ftrace.h
index c5534fa..3c60f37 100644
--- a/arch/arm64/include/asm/ftrace.h
+++ b/arch/arm64/include/asm/ftrace.h
@@ -28,6 +28,8 @@ struct dyn_arch_ftrace {
 
 extern unsigned long ftrace_graph_call;
 
+extern void return_to_handler(void);
+
 static inline unsigned long ftrace_call_adjust(unsigned long addr)
 {
 	/*
diff --git a/arch/arm64/include/asm/stacktrace.h b/arch/arm64/include/asm/stacktrace.h
index 6fb61c5..801a16db 100644
--- a/arch/arm64/include/asm/stacktrace.h
+++ b/arch/arm64/include/asm/stacktrace.h
@@ -22,6 +22,9 @@ struct stackframe {
 	unsigned long fp;
 	unsigned long sp;
 	unsigned long pc;
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	unsigned int graph;
+#endif
 };
 
 extern int unwind_frame(struct task_struct *tsk, struct stackframe *frame);
diff --git a/arch/arm64/kernel/perf_callchain.c b/arch/arm64/kernel/perf_callchain.c
index 797220d..ff46654 100644
--- a/arch/arm64/kernel/perf_callchain.c
+++ b/arch/arm64/kernel/perf_callchain.c
@@ -164,6 +164,9 @@ void perf_callchain_kernel(struct perf_callchain_entry *entry,
 	frame.fp = regs->regs[29];
 	frame.sp = regs->sp;
 	frame.pc = regs->pc;
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	frame.graph = current->curr_ret_stack;
+#endif
 
 	walk_stackframe(current, &frame, callchain_trace, entry);
 }
diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index 98bf546..88d742b 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -344,6 +344,9 @@ unsigned long get_wchan(struct task_struct *p)
 	frame.fp = thread_saved_fp(p);
 	frame.sp = thread_saved_sp(p);
 	frame.pc = thread_saved_pc(p);
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	frame.graph = p->curr_ret_stack;
+#endif
 	stack_page = (unsigned long)task_stack_page(p);
 	do {
 		if (frame.sp < stack_page ||
diff --git a/arch/arm64/kernel/return_address.c b/arch/arm64/kernel/return_address.c
index 07b37ac..1718706 100644
--- a/arch/arm64/kernel/return_address.c
+++ b/arch/arm64/kernel/return_address.c
@@ -43,6 +43,9 @@ void *return_address(unsigned int level)
 	frame.fp = (unsigned long)__builtin_frame_address(0);
 	frame.sp = current_stack_pointer;
 	frame.pc = (unsigned long)return_address; /* dummy */
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	frame.graph = current->curr_ret_stack;
+#endif
 
 	walk_stackframe(current, &frame, save_return_addr, &data);
 
diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index 9c7acf8..0a39049 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -17,6 +17,7 @@
  */
 #include <linux/kernel.h>
 #include <linux/export.h>
+#include <linux/ftrace.h>
 #include <linux/sched.h>
 #include <linux/stacktrace.h>
 
@@ -66,6 +67,19 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 	frame->fp = *(unsigned long *)(fp);
 	frame->pc = *(unsigned long *)(fp + 8);
 
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	if (tsk && tsk->ret_stack &&
+			(frame->pc == (unsigned long)return_to_handler)) {
+		/*
+		 * This is a case where function graph tracer has
+		 * modified a return address (LR) in a stack frame
+		 * to hook a function return.
+		 * So replace it to an original value.
+		 */
+		frame->pc = tsk->ret_stack[frame->graph--].ret;
+	}
+#endif /* CONFIG_FUNCTION_GRAPH_TRACER */
+
 	/*
 	 * Check whether we are going to walk through from interrupt stack
 	 * to task stack.
@@ -137,6 +151,9 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
 		frame.sp = current_stack_pointer;
 		frame.pc = (unsigned long)save_stack_trace_tsk;
 	}
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	frame.graph = tsk->curr_ret_stack;
+#endif
 
 	walk_stackframe(tsk, &frame, save_trace, &data);
 	if (trace->nr_entries < trace->max_entries)
diff --git a/arch/arm64/kernel/time.c b/arch/arm64/kernel/time.c
index 6e5c521..5977969 100644
--- a/arch/arm64/kernel/time.c
+++ b/arch/arm64/kernel/time.c
@@ -52,6 +52,9 @@ unsigned long profile_pc(struct pt_regs *regs)
 	frame.fp = regs->regs[29];
 	frame.sp = regs->sp;
 	frame.pc = regs->pc;
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	frame.graph = -1; /* no task info */
+#endif
 	do {
 		int ret = unwind_frame(NULL, &frame);
 		if (ret < 0)
diff --git a/arch/arm64/kernel/traps.c b/arch/arm64/kernel/traps.c
index da45224..f140029 100644
--- a/arch/arm64/kernel/traps.c
+++ b/arch/arm64/kernel/traps.c
@@ -147,17 +147,14 @@ static void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk)
 {
 	struct stackframe frame;
 	unsigned long _irq_stack_ptr = per_cpu(irq_stack_ptr, smp_processor_id());
+	int skip;
 
 	pr_debug("%s(regs = %p tsk = %p)\n", __func__, regs, tsk);
 
 	if (!tsk)
 		tsk = current;
 
-	if (regs) {
-		frame.fp = regs->regs[29];
-		frame.sp = regs->sp;
-		frame.pc = regs->pc;
-	} else if (tsk == current) {
+	if (tsk == current) {
 		frame.fp = (unsigned long)__builtin_frame_address(0);
 		frame.sp = current_stack_pointer;
 		frame.pc = (unsigned long)dump_backtrace;
@@ -169,14 +166,31 @@ static void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk)
 		frame.sp = thread_saved_sp(tsk);
 		frame.pc = thread_saved_pc(tsk);
 	}
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	frame.graph = tsk->curr_ret_stack;
+#endif
 
+	skip = (regs ? 1 : 0);
 	pr_emerg("Call trace:\n");
 	while (1) {
 		unsigned long where = frame.pc;
 		unsigned long stack;
 		int ret;
 
-		dump_backtrace_entry(where);
+		/* skip until specified stack frame */
+		if (!skip)
+			dump_backtrace_entry(where);
+		else if (frame.fp == regs->regs[29]) {
+			skip = 0;
+			/*
+			 * Mostly, this is the case where this function is
+			 * called in panic/abort. As exception handler's
+			 * stack frame does not contain the corresponding pc
+			 * at which an exception has taken place, use regs->pc
+			 * instead.
+			 */
+			dump_backtrace_entry(regs->pc);
+		}
 		ret = unwind_frame(tsk, &frame);
 		if (ret < 0)
 			break;
-- 
1.7.9.5

[PATCH v7 4/6] arm64: insn: add instruction decoders for ldp/stp and add/sub

[AKASHI Takahiro]

Once a function prologue analyzer is implemented, it can be utilized to
make the output from ftrace-based stack tracer more precise, especially
stack usage for each function. But the current insn routines
lacks support for some instructions, including stp, add, sub and mov to
parse a function prologue.

This patch adds decoders against such instructions. Those decoders are
used solely by stack tracer for now, but generic enough for other uses.

Reviewed-by: Jungseok Lee <jungseoklee85@gmail.com>
Tested-by: Jungseok Lee <jungseoklee85@gmail.com>
Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 arch/arm64/include/asm/insn.h |   18 ++++++
 arch/arm64/kernel/insn.c      |  128 ++++++++++++++++++++++++++++++++++++++---
 2 files changed, 138 insertions(+), 8 deletions(-)

diff --git a/arch/arm64/include/asm/insn.h b/arch/arm64/include/asm/insn.h
index 30e50eb..6fca8b0 100644
--- a/arch/arm64/include/asm/insn.h
+++ b/arch/arm64/include/asm/insn.h
@@ -161,6 +161,8 @@ enum aarch64_insn_size_type {
 enum aarch64_insn_ldst_type {
 	AARCH64_INSN_LDST_LOAD_REG_OFFSET,
 	AARCH64_INSN_LDST_STORE_REG_OFFSET,
+	AARCH64_INSN_LDST_LOAD_PAIR_REG_OFFSET,
+	AARCH64_INSN_LDST_STORE_PAIR_REG_OFFSET,
 	AARCH64_INSN_LDST_LOAD_PAIR_PRE_INDEX,
 	AARCH64_INSN_LDST_STORE_PAIR_PRE_INDEX,
 	AARCH64_INSN_LDST_LOAD_PAIR_POST_INDEX,
@@ -225,6 +227,8 @@ static __always_inline u32 aarch64_insn_get_##abbr##_value(void) \
 
 __AARCH64_INSN_FUNCS(str_reg,	0x3FE0EC00, 0x38206800)
 __AARCH64_INSN_FUNCS(ldr_reg,	0x3FE0EC00, 0x38606800)
+__AARCH64_INSN_FUNCS(stp_reg,	0x7FC00000, 0x29000000)
+__AARCH64_INSN_FUNCS(ldp_reg,	0x7FC00000, 0x29400000)
 __AARCH64_INSN_FUNCS(stp_post,	0x7FC00000, 0x28800000)
 __AARCH64_INSN_FUNCS(ldp_post,	0x7FC00000, 0x28C00000)
 __AARCH64_INSN_FUNCS(stp_pre,	0x7FC00000, 0x29800000)
@@ -277,6 +281,7 @@ __AARCH64_INSN_FUNCS(hint,	0xFFFFF01F, 0xD503201F)
 __AARCH64_INSN_FUNCS(br,	0xFFFFFC1F, 0xD61F0000)
 __AARCH64_INSN_FUNCS(blr,	0xFFFFFC1F, 0xD63F0000)
 __AARCH64_INSN_FUNCS(ret,	0xFFFFFC1F, 0xD65F0000)
+__AARCH64_INSN_FUNCS(eret,	0xFFFFFFFF, 0xD69F03E0)
 
 #undef	__AARCH64_INSN_FUNCS
 
@@ -370,6 +375,19 @@ bool aarch32_insn_is_wide(u32 insn);
 u32 aarch32_insn_extract_reg_num(u32 insn, int offset);
 u32 aarch32_insn_mcr_extract_opc2(u32 insn);
 u32 aarch32_insn_mcr_extract_crm(u32 insn);
+int aarch64_insn_extract_add_sub_imm(u32 insn,
+				     enum aarch64_insn_register *dst,
+				     enum aarch64_insn_register *src,
+				     int *imm,
+				     enum aarch64_insn_variant *variant,
+				     enum aarch64_insn_adsb_type *type);
+int aarch64_insn_extract_load_store_pair(u32 insn,
+					 enum aarch64_insn_register *reg1,
+					 enum aarch64_insn_register *reg2,
+					 enum aarch64_insn_register *base,
+					 int *offset,
+					 enum aarch64_insn_variant *variant,
+					 enum aarch64_insn_ldst_type *type);
 #endif /* __ASSEMBLY__ */
 
 #endif	/* __ASM_INSN_H */
diff --git a/arch/arm64/kernel/insn.c b/arch/arm64/kernel/insn.c
index c08b9ad..99d6e57 100644
--- a/arch/arm64/kernel/insn.c
+++ b/arch/arm64/kernel/insn.c
@@ -33,6 +33,7 @@
 #include <asm/insn.h>
 
 #define AARCH64_INSN_SF_BIT	BIT(31)
+#define AARCH64_INSN_S_BIT	BIT(29)
 #define AARCH64_INSN_N_BIT	BIT(22)
 
 static int aarch64_insn_encoding_class[] = {
@@ -388,17 +389,10 @@ u32 __kprobes aarch64_insn_encode_immediate(enum aarch64_insn_imm_type type,
 	return insn;
 }
 
-static u32 aarch64_insn_encode_register(enum aarch64_insn_register_type type,
-					u32 insn,
-					enum aarch64_insn_register reg)
+static int aarch64_insn_get_reg_shift(enum aarch64_insn_register_type type)
 {
 	int shift;
 
-	if (reg < AARCH64_INSN_REG_0 || reg > AARCH64_INSN_REG_SP) {
-		pr_err("%s: unknown register encoding %d\n", __func__, reg);
-		return 0;
-	}
-
 	switch (type) {
 	case AARCH64_INSN_REGTYPE_RT:
 	case AARCH64_INSN_REGTYPE_RD:
@@ -415,6 +409,26 @@ static u32 aarch64_insn_encode_register(enum aarch64_insn_register_type type,
 		shift = 16;
 		break;
 	default:
+		shift = -1;
+		break;
+	}
+
+	return shift;
+}
+
+static u32 aarch64_insn_encode_register(enum aarch64_insn_register_type type,
+					u32 insn,
+					enum aarch64_insn_register reg)
+{
+	int shift;
+
+	if (reg < AARCH64_INSN_REG_0 || reg > AARCH64_INSN_REG_SP) {
+		pr_err("%s: unknown register encoding %d\n", __func__, reg);
+		return 0;
+	}
+
+	shift = aarch64_insn_get_reg_shift(type);
+	if (shift < 0) {
 		pr_err("%s: unknown register type encoding %d\n", __func__,
 		       type);
 		return 0;
@@ -632,6 +646,12 @@ u32 aarch64_insn_gen_load_store_pair(enum aarch64_insn_register reg1,
 	int shift;
 
 	switch (type) {
+	case AARCH64_INSN_LDST_LOAD_PAIR_REG_OFFSET:
+		insn = aarch64_insn_get_ldp_reg_value();
+		break;
+	case AARCH64_INSN_LDST_STORE_PAIR_REG_OFFSET:
+		insn = aarch64_insn_get_stp_reg_value();
+		break;
 	case AARCH64_INSN_LDST_LOAD_PAIR_PRE_INDEX:
 		insn = aarch64_insn_get_ldp_pre_value();
 		break;
@@ -1141,3 +1161,95 @@ u32 aarch32_insn_mcr_extract_crm(u32 insn)
 {
 	return insn & CRM_MASK;
 }
+
+static enum aarch64_insn_register aarch64_insn_decode_reg_num(u32 insn,
+				enum aarch64_insn_register_type type)
+{
+	int shift;
+
+	shift = aarch64_insn_get_reg_shift(type);
+	if (shift < 0) {
+		pr_err("%s: unknown register type decoding %d\n", __func__,
+		       type);
+		return ~0L;
+	}
+
+	return (insn >> shift) & 0x1f;
+}
+
+int aarch64_insn_extract_add_sub_imm(u32 insn,
+				     enum aarch64_insn_register *dst,
+				     enum aarch64_insn_register *src,
+				     int *imm,
+				     enum aarch64_insn_variant *variant,
+				     enum aarch64_insn_adsb_type *type)
+{
+	int shift;
+
+	if (aarch64_insn_is_add_imm(insn))
+		*type =	((insn) & AARCH64_INSN_S_BIT) ?
+				AARCH64_INSN_ADSB_ADD_SETFLAGS :
+				AARCH64_INSN_ADSB_ADD;
+	else if (aarch64_insn_is_sub_imm(insn))
+		*type =	((insn) & AARCH64_INSN_S_BIT) ?
+				AARCH64_INSN_ADSB_SUB_SETFLAGS :
+				AARCH64_INSN_ADSB_SUB;
+	else
+		return -EINVAL;
+
+	*variant = (insn & AARCH64_INSN_SF_BIT) ? AARCH64_INSN_VARIANT_64BIT :
+					AARCH64_INSN_VARIANT_32BIT;
+
+	*dst = aarch64_insn_decode_reg_num(insn, AARCH64_INSN_REGTYPE_RD);
+
+	*src = aarch64_insn_decode_reg_num(insn, AARCH64_INSN_REGTYPE_RN);
+
+	*imm = (int)aarch64_insn_decode_immediate(AARCH64_INSN_IMM_12, insn);
+	shift = (insn >> 22) & 0x3;
+	if (shift == 0x1)
+		*imm <<= 12;
+	else if (shift != 0x0)
+		return -EINVAL;
+
+	return 0;
+}
+
+int aarch64_insn_extract_load_store_pair(u32 insn,
+					 enum aarch64_insn_register *reg1,
+					 enum aarch64_insn_register *reg2,
+					 enum aarch64_insn_register *base,
+					 int *offset,
+					 enum aarch64_insn_variant *variant,
+					 enum aarch64_insn_ldst_type *type)
+{
+	u64 imm;
+
+	if (aarch64_insn_is_stp_reg(insn))
+		*type = AARCH64_INSN_LDST_STORE_PAIR_REG_OFFSET;
+	else if (aarch64_insn_is_stp_post(insn))
+		*type = AARCH64_INSN_LDST_STORE_PAIR_POST_INDEX;
+	else if (aarch64_insn_is_stp_pre(insn))
+		*type = AARCH64_INSN_LDST_STORE_PAIR_PRE_INDEX;
+	else if (aarch64_insn_is_ldp_reg(insn))
+		*type = AARCH64_INSN_LDST_LOAD_PAIR_REG_OFFSET;
+	else if (aarch64_insn_is_ldp_post(insn))
+		*type = AARCH64_INSN_LDST_LOAD_PAIR_POST_INDEX;
+	else if (aarch64_insn_is_ldp_pre(insn))
+		*type = AARCH64_INSN_LDST_LOAD_PAIR_PRE_INDEX;
+	else
+		return -EINVAL;
+
+	*variant = (insn & AARCH64_INSN_S_BIT) ? AARCH64_INSN_VARIANT_64BIT :
+				AARCH64_INSN_VARIANT_32BIT;
+
+	*reg1 = aarch64_insn_decode_reg_num(insn, AARCH64_INSN_REGTYPE_RT);
+
+	*reg2 = aarch64_insn_decode_reg_num(insn, AARCH64_INSN_REGTYPE_RT2);
+
+	*base = aarch64_insn_decode_reg_num(insn, AARCH64_INSN_REGTYPE_RN);
+
+	imm = aarch64_insn_decode_immediate(AARCH64_INSN_IMM_7, insn);
+	*offset = (int)(sign_extend64(imm, 6) * 8);
+
+	return 0;
+}
-- 
1.7.9.5

[PATCH v7 5/6] arm64: ftrace: add arch-specific stack tracer

[AKASHI Takahiro]

Background and issues on generic check_stack():
1) slurping stack

    Assume that a given function A was invoked, and it was invoked again in
    another context, then it called another function B which allocated
    a large size of local variables on the stack, but it has not modified
    the variable(s) yet.
    When stack tracer, check_stack(), examines the stack looking for B,
    then A, we may have a chance to accidentally find a stale, not current,
    stack frame for A because the old frame might reside on the memory for
    the variable which has not been overwritten.

    (issue) The stack_trace output may have stale entries.

2) differences between x86 and arm64

    On x86, "call" instruction automatically pushes a return address on
    the top of the stack and decrements a stack pointer. Then child
    function allocates its local variables on the stack.

    On arm64, a child function is responsible for allocating memory for
    local variables as well as a stack frame, and explicitly pushes
    a return address (LR) and old frame pointer in its function prologue
    *after* decreasing a stack pointer.

    Generic check_stack() recogizes 'idxB,' which is the next address of
    the location where 'fpB' is found, in the picture below as an estimated
    stack pointer. This seems to fine with x86, but on arm64, 'idxB' is
    not appropriate just because it contains child function's "local
    variables."
    We should instead use spB, if possible, for better interpretation of
    func_B's stack usage.

LOW      |  ...   |
fpA      +--------+   func_A (pcA, fpA, spA)
         |  fpB   |
    idxB + - - - -+
         |  pcB   |
         |  ... <----------- static local variables in func_A
         |  ...   |             and extra function args to func_A
spB      + - - - -+
         |  ... <----------- dynamically allocated variables in func_B
fpB      +--------+   func_B (pcB, fpB, spB)
         |  fpC   |
    idxC + - - - -+
         |  pcC   |
         |  ... <----------- static local variables in func_B
         |  ...   |             and extra function args to func_B
spC      + - - - -+
         |  ...   |
fpC      +--------+   func_C (pcC, fpC, spC)
HIGH     |        |

    (issue) Stack size for a function in stack_trace output is inaccurate,
            or rather wrong.  It looks as if <Size> field is one-line
	    offset against <Location>.

                Depth    Size   Location    (49 entries)
                -----    ----   --------
         40)     1416      64   path_openat+0x128/0xe00       -> 176
         41)     1352     176   do_filp_open+0x74/0xf0        -> 256
         42)     1176     256   do_open_execat+0x74/0x1c8     -> 80
         43)      920      80   open_exec+0x3c/0x70           -> 32
         44)      840      32   load_elf_binary+0x294/0x10c8

Implementation on arm64:
So we want to have our own stack tracer, check_stack().
Our approach is uniqeue in the following points:
* analyze a function prologue of a traced function to estimate a more
  accurate stack pointer value, replacing naive '<child's fp> + 0x10.'
* use walk_stackframe(), instead of slurping stack contents as orignal
  check_stack() does, to identify a stack frame and a stack index (height)
  for every callsite.

Regarding a function prologue analyzer, there is no guarantee that we can
handle all the possible patterns of function prologue as gcc does not use
any fixed templates to generate them. 'Instruction scheduling' is another
issue here.
Nevertheless, this analyzer will certainly cover almost all the cases
in the current kernel image and give us useful information on stack
pointer usages.

    pos = analyze_function_prologue(unsigned long pc,
				    unsigned long *size,
				    unsigned long *size2);

	pos:   indicates a relative position of callsite of mcount() in
	       a function prologue, and should be zero if an analyzer has
	       successfully parsed a function prologue and reached to
	       a location where fp is properly updated.
	size:  a offset from a parent's fp at the end of function prologue
	size2: an offset against sp at the end of function prologue

So presumably,
    <new sp> = <old fp> + <size>
    <new fp> = <new sp> - <size2>

Please note that this patch utilizes a function prologue solely for
stack tracer, and does not affect any behaviors of other existing unwind
functions.

Reviewed-by: Jungseok Lee <jungseoklee85@gmail.com>
Tested-by: Jungseok Lee <jungseoklee85@gmail.com>
Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 arch/arm64/include/asm/ftrace.h     |    2 +-
 arch/arm64/include/asm/stacktrace.h |    4 +
 arch/arm64/kernel/ftrace.c          |   64 ++++++++++++
 arch/arm64/kernel/stacktrace.c      |  190 ++++++++++++++++++++++++++++++++++-
 4 files changed, 256 insertions(+), 4 deletions(-)

diff --git a/arch/arm64/include/asm/ftrace.h b/arch/arm64/include/asm/ftrace.h
index 3c60f37..6795219 100644
--- a/arch/arm64/include/asm/ftrace.h
+++ b/arch/arm64/include/asm/ftrace.h
@@ -26,7 +26,7 @@ struct dyn_arch_ftrace {
 	/* No extra data needed for arm64 */
 };
 
-extern unsigned long ftrace_graph_call;
+extern u32 ftrace_graph_call;
 
 extern void return_to_handler(void);
 
diff --git a/arch/arm64/include/asm/stacktrace.h b/arch/arm64/include/asm/stacktrace.h
index 801a16db..0eee008 100644
--- a/arch/arm64/include/asm/stacktrace.h
+++ b/arch/arm64/include/asm/stacktrace.h
@@ -30,5 +30,9 @@ struct stackframe {
 extern int unwind_frame(struct task_struct *tsk, struct stackframe *frame);
 extern void walk_stackframe(struct task_struct *tsk, struct stackframe *frame,
 			    int (*fn)(struct stackframe *, void *), void *data);
+#ifdef CONFIG_STACK_TRACER
+struct stack_trace;
+extern void save_stack_trace_sp(struct stack_trace *trace, unsigned long *sp);
+#endif
 
 #endif	/* __ASM_STACKTRACE_H */
diff --git a/arch/arm64/kernel/ftrace.c b/arch/arm64/kernel/ftrace.c
index 314f82d..102ed59 100644
--- a/arch/arm64/kernel/ftrace.c
+++ b/arch/arm64/kernel/ftrace.c
@@ -9,6 +9,7 @@
  * published by the Free Software Foundation.
  */
 
+#include <linux/bug.h>
 #include <linux/ftrace.h>
 #include <linux/swab.h>
 #include <linux/uaccess.h>
@@ -16,6 +17,7 @@
 #include <asm/cacheflush.h>
 #include <asm/ftrace.h>
 #include <asm/insn.h>
+#include <asm/stacktrace.h>
 
 #ifdef CONFIG_DYNAMIC_FTRACE
 /*
@@ -173,3 +175,65 @@ int ftrace_disable_ftrace_graph_caller(void)
 }
 #endif /* CONFIG_DYNAMIC_FTRACE */
 #endif /* CONFIG_FUNCTION_GRAPH_TRACER */
+
+#ifdef CONFIG_STACK_TRACER
+static unsigned long stack_trace_sp[STACK_TRACE_ENTRIES];
+static unsigned long raw_stack_trace_max_size;
+
+void check_stack(unsigned long ip, unsigned long *stack)
+{
+	unsigned long this_size, flags;
+	unsigned long top;
+	int i, j;
+
+	this_size = ((unsigned long)stack) & (THREAD_SIZE-1);
+	this_size = THREAD_SIZE - this_size;
+
+	if (this_size <= raw_stack_trace_max_size)
+		return;
+
+	/* we do not handle an interrupt stack yet */
+	if (!object_is_on_stack(stack))
+		return;
+
+	local_irq_save(flags);
+	arch_spin_lock(&stack_trace_max_lock);
+
+	/* check again */
+	if (this_size <= raw_stack_trace_max_size)
+		goto out;
+
+	/* find out stack frames */
+	stack_trace_max.nr_entries = 0;
+	stack_trace_max.skip = 0;
+	save_stack_trace_sp(&stack_trace_max, stack_trace_sp);
+	stack_trace_max.nr_entries--; /* for the last entry ('-1') */
+
+	/* calculate a stack index for each function */
+	top = ((unsigned long)stack & ~(THREAD_SIZE-1)) + THREAD_SIZE;
+	for (i = 0; i < stack_trace_max.nr_entries; i++)
+		stack_trace_index[i] = top - stack_trace_sp[i];
+	raw_stack_trace_max_size = this_size;
+
+	/* Skip over the overhead of the stack tracer itself */
+	for (i = 0; i < stack_trace_max.nr_entries; i++)
+		if (stack_trace_max.entries[i] == ip)
+			break;
+
+	stack_trace_max.nr_entries -= i;
+	for (j = 0; j < stack_trace_max.nr_entries; j++) {
+		stack_trace_index[j] = stack_trace_index[j + i];
+		stack_trace_max.entries[j] = stack_trace_max.entries[j + i];
+	}
+	stack_trace_max_size = stack_trace_index[0];
+
+	if (task_stack_end_corrupted(current)) {
+		WARN(1, "task stack is corrupted.\n");
+		stack_trace_print();
+	}
+
+ out:
+	arch_spin_unlock(&stack_trace_max_lock);
+	local_irq_restore(flags);
+}
+#endif /* CONFIG_STACK_TRACER */
diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index 0a39049..1d18bc4 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -24,6 +24,149 @@
 #include <asm/irq.h>
 #include <asm/stacktrace.h>
 
+#ifdef CONFIG_STACK_TRACER
+/*
+ * This function parses a function prologue of a traced function and
+ * determines its stack size.
+ * A return value indicates a location of @pc in a function prologue.
+ * @return value:
+ * <case 1>                       <case 1'>
+ * 1:
+ *     sub sp, sp, #XX            sub sp, sp, #XX
+ * 2:
+ *     stp x29, x30, [sp, #YY]    stp x29, x30, [sp, #--ZZ]!
+ * 3:
+ *     add x29, sp, #YY           mov x29, sp
+ * 0:
+ *
+ * <case 2>
+ * 1:
+ *     stp x29, x30, [sp, #-XX]!
+ * 3:
+ *     mov x29, sp
+ * 0:
+ *
+ * @size: sp offset from calller's sp (XX or XX + ZZ)
+ * @size2: fp offset from new sp (YY or 0)
+ */
+static int analyze_function_prologue(unsigned long pc,
+		unsigned long *size, unsigned long *size2)
+{
+	unsigned long offset;
+	u32 *addr, insn;
+	int pos = -1;
+	enum aarch64_insn_register src, dst, reg1, reg2, base;
+	int imm;
+	enum aarch64_insn_variant variant;
+	enum aarch64_insn_adsb_type adsb_type;
+	enum aarch64_insn_ldst_type ldst_type;
+
+	*size = *size2 = 0;
+
+	if (!pc)
+		goto out;
+
+	if (unlikely(!kallsyms_lookup_size_offset(pc, NULL, &offset)))
+		goto out;
+
+	addr = (u32 *)(pc - offset);
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	if (addr == (u32 *)ftrace_graph_caller)
+#ifdef CONFIG_DYNAMIC_FTRACE
+		addr = (u32 *)ftrace_caller;
+#else
+		addr = (u32 *)_mcount;
+#endif
+	else
+#endif
+#ifdef CONFIG_DYNAMIC_FTRACE
+	if (addr == (u32 *)ftrace_call)
+		addr = (u32 *)ftrace_caller;
+#ifdef CONFIG_FUNCTION_GRAPH_TRACER
+	else if (addr == &ftrace_graph_call)
+		addr = (u32 *)ftrace_caller;
+#endif
+#endif
+
+	insn = le32_to_cpu(*addr);
+	pos = 1;
+
+	/* analyze a function prologue */
+	while ((unsigned long)addr < pc) {
+		if (aarch64_insn_is_branch_imm(insn) ||
+		    aarch64_insn_is_br(insn) ||
+		    aarch64_insn_is_blr(insn) ||
+		    aarch64_insn_is_ret(insn) ||
+		    aarch64_insn_is_eret(insn))
+			/* exiting a basic block */
+			goto out;
+
+		if (aarch64_insn_decode_add_sub_imm(insn, &dst, &src,
+					&imm, &variant, &adsb_type)) {
+			if ((adsb_type == AARCH64_INSN_ADSB_SUB) &&
+				(dst == AARCH64_INSN_REG_SP) &&
+				(src == AARCH64_INSN_REG_SP)) {
+				/*
+				 * Starting the following sequence:
+				 *   sub sp, sp, #xx
+				 *   stp x29, x30, [sp, #yy]
+				 *   add x29, sp, #yy
+				 */
+				WARN_ON(pos != 1);
+				pos = 2;
+				*size += imm;
+			} else if ((adsb_type == AARCH64_INSN_ADSB_ADD) &&
+				(dst == AARCH64_INSN_REG_29) &&
+				(src == AARCH64_INSN_REG_SP)) {
+				/*
+				 *   add x29, sp, #yy
+				 * or
+				 *   mov x29, sp
+				 */
+				WARN_ON(pos != 3);
+				pos = 0;
+				*size2 = imm;
+
+				break;
+			}
+		} else if (aarch64_insn_decode_load_store_pair(insn,
+					&reg1, &reg2, &base, &imm,
+					&variant, &ldst_type)) {
+			if ((ldst_type ==
+				AARCH64_INSN_LDST_STORE_PAIR_PRE_INDEX) &&
+			    (reg1 == AARCH64_INSN_REG_29) &&
+			    (reg2 == AARCH64_INSN_REG_30) &&
+			    (base == AARCH64_INSN_REG_SP)) {
+				/*
+				 * Starting the following sequence:
+				 *   stp x29, x30, [sp, #-xx]!
+				 *   mov x29, sp
+				 */
+				WARN_ON(!((pos == 1) || (pos == 2)));
+				pos = 3;
+				*size += -imm;
+			} else if ((ldst_type ==
+				AARCH64_INSN_LDST_STORE_PAIR) &&
+			    (reg1 == AARCH64_INSN_REG_29) &&
+			    (reg2 == AARCH64_INSN_REG_30) &&
+			    (base == AARCH64_INSN_REG_SP)) {
+				/*
+				 *   stp x29, x30, [sp, #yy]
+				 */
+				WARN_ON(pos != 2);
+				pos = 3;
+			}
+		}
+
+		addr++;
+		insn = le32_to_cpu(*addr);
+	}
+
+out:
+	return pos;
+}
+#endif
+
 /*
  * AArch64 PCS assigns the frame pointer to x29.
  *
@@ -112,6 +255,9 @@ struct stack_trace_data {
 	struct stack_trace *trace;
 	unsigned int no_sched_functions;
 	unsigned int skip;
+#ifdef CONFIG_STACK_TRACER
+	unsigned long *sp;
+#endif
 };
 
 static int save_trace(struct stackframe *frame, void *d)
@@ -127,18 +273,42 @@ static int save_trace(struct stackframe *frame, void *d)
 		return 0;
 	}
 
+#ifdef CONFIG_STACK_TRACER
+	if (data->sp) {
+		if (trace->nr_entries) {
+			unsigned long child_pc, sp_off, fp_off;
+			int pos;
+
+			child_pc = trace->entries[trace->nr_entries - 1];
+			pos = analyze_function_prologue(child_pc,
+					&sp_off, &fp_off);
+			/*
+			 * frame->sp - 0x10 is actually a child's fp.
+			 * See above.
+			 */
+			data->sp[trace->nr_entries] = (pos < 0 ? frame->sp :
+					(frame->sp - 0x10) + sp_off - fp_off);
+		} else {
+			data->sp[0] = frame->sp;
+		}
+	}
+#endif
 	trace->entries[trace->nr_entries++] = addr;
 
 	return trace->nr_entries >= trace->max_entries;
 }
 
-void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
+static void __save_stack_trace_tsk(struct task_struct *tsk,
+		struct stack_trace *trace, unsigned long *stack_dump_sp)
 {
 	struct stack_trace_data data;
 	struct stackframe frame;
 
 	data.trace = trace;
 	data.skip = trace->skip;
+#ifdef CONFIG_STACK_TRACER
+	data.sp = stack_dump_sp;
+#endif
 
 	if (tsk != current) {
 		data.no_sched_functions = 1;
@@ -149,7 +319,8 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
 		data.no_sched_functions = 0;
 		frame.fp = (unsigned long)__builtin_frame_address(0);
 		frame.sp = current_stack_pointer;
-		frame.pc = (unsigned long)save_stack_trace_tsk;
+		asm("1:");
+		asm("ldr %0, =1b" : "=r" (frame.pc));
 	}
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 	frame.graph = tsk->curr_ret_stack;
@@ -160,9 +331,22 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
 		trace->entries[trace->nr_entries++] = ULONG_MAX;
 }
 
+void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
+{
+	__save_stack_trace_tsk(tsk, trace, NULL);
+}
+
 void save_stack_trace(struct stack_trace *trace)
 {
-	save_stack_trace_tsk(current, trace);
+	__save_stack_trace_tsk(current, trace, NULL);
 }
 EXPORT_SYMBOL_GPL(save_stack_trace);
+
+#ifdef CONFIG_STACK_TRACER
+void save_stack_trace_sp(struct stack_trace *trace,
+					unsigned long *stack_dump_sp)
+{
+	__save_stack_trace_tsk(current, trace, stack_dump_sp);
+}
+#endif /* CONFIG_STACK_TRACER */
 #endif
-- 
1.7.9.5

[PATCH v7 6/6] arm64: ftrace: add a test of function prologue analyzer

[AKASHI Takahiro]

The patch ("arm64: ftrace: add arch-specific stack tracer") introduced
a function prologue analyzer.

Given that there is no fixed template for a function prologue, at least
on gcc for aarch64, a function prologue analyzer may be rather heuristic.

So this patch allows us to run a basic test in boot time by executing
an analyzer against all the *traceable* functions. The test can be turned
on and off with a kernel command line option,
function_prologue_analyzer_test.

For function_prologue_analyzer_test=2, the output looks like:

       po sp    fp       symbol
       == ==    ==       ======
    0: 0  0x040 0x000 OK gic_handle_irq+0x20/0xa4
    1: 0  0x040 0x000 OK gic_handle_irq+0x34/0x114
    2: 0  0x030 0x000 OK run_init_process+0x14/0x48
    3: 0  0x020 0x000 OK try_to_run_init_process+0x14/0x58
    4: 0  0x080 0x000 OK do_one_initcall+0x1c/0x194
    ...
22959: 0  0x020 0x000 OK tty_lock_slave+0x14/0x3c
22960: 0  0x020 0x000 OK tty_unlock_slave+0x14/0x3c
function prologue analyzer test: 0 errors

Here,
    pos = analyze_function_prologue(unsigned long pc,
				    unsigned long *size,
				    unsigned long *size2);
	pos   -> "po"
	size  -> "sp"
	size2 -> "fp"

and the last line shows the number of possible errors in the result.

For function_prologue_analyzer_test=1, only the last line will be shown.

Reviewed-by: Jungseok Lee <jungseoklee85@gmail.com>
Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 arch/arm64/kernel/stacktrace.c |   59 ++++++++++++++++++++++++++++++++++++++--
 1 file changed, 56 insertions(+), 3 deletions(-)

diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index 1d18bc4..acbca22 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -18,6 +18,7 @@
 #include <linux/kernel.h>
 #include <linux/export.h>
 #include <linux/ftrace.h>
+#include <linux/kallsyms.h>
 #include <linux/sched.h>
 #include <linux/stacktrace.h>
 
@@ -101,7 +102,7 @@ static int analyze_function_prologue(unsigned long pc,
 			/* exiting a basic block */
 			goto out;
 
-		if (aarch64_insn_decode_add_sub_imm(insn, &dst, &src,
+		if (!aarch64_insn_extract_add_sub_imm(insn, &dst, &src,
 					&imm, &variant, &adsb_type)) {
 			if ((adsb_type == AARCH64_INSN_ADSB_SUB) &&
 				(dst == AARCH64_INSN_REG_SP) &&
@@ -129,7 +130,7 @@ static int analyze_function_prologue(unsigned long pc,
 
 				break;
 			}
-		} else if (aarch64_insn_decode_load_store_pair(insn,
+		} else if (!aarch64_insn_extract_load_store_pair(insn,
 					&reg1, &reg2, &base, &imm,
 					&variant, &ldst_type)) {
 			if ((ldst_type ==
@@ -146,7 +147,7 @@ static int analyze_function_prologue(unsigned long pc,
 				pos = 3;
 				*size += -imm;
 			} else if ((ldst_type ==
-				AARCH64_INSN_LDST_STORE_PAIR) &&
+				AARCH64_INSN_LDST_STORE_PAIR_REG_OFFSET) &&
 			    (reg1 == AARCH64_INSN_REG_29) &&
 			    (reg2 == AARCH64_INSN_REG_30) &&
 			    (base == AARCH64_INSN_REG_SP)) {
@@ -348,5 +349,57 @@ void save_stack_trace_sp(struct stack_trace *trace,
 {
 	__save_stack_trace_tsk(current, trace, stack_dump_sp);
 }
+
+static int start_analyzer_test __initdata;
+
+static int __init enable_analyzer_test(char *str)
+{
+	get_option(&str, &start_analyzer_test);
+	return 0;
+}
+early_param("function_prologue_analyzer_test", enable_analyzer_test);
+
+static void __init do_test_function_prologue_analyzer(void)
+{
+	extern unsigned long __start_mcount_loc[];
+	extern unsigned long __stop_mcount_loc[];
+	unsigned long count, i, errors;
+	int print_once;
+
+	count = __stop_mcount_loc - __start_mcount_loc;
+	errors = print_once = 0;
+	for (i = 0; i < count; i++) {
+		unsigned long addr, sp_off, fp_off;
+		int pos;
+		bool check;
+		char buf[60];
+
+		addr = __start_mcount_loc[i];
+		pos = analyze_function_prologue(addr, &sp_off, &fp_off);
+		check = ((pos != 0) || !sp_off || (sp_off <= fp_off));
+		if (check)
+			errors++;
+		if (check || (start_analyzer_test > 1)) {
+			if (!print_once) {
+				pr_debug("       po sp    fp       symbol\n");
+				pr_debug("       == ==    ==    == ======\n");
+				print_once++;
+			}
+			sprint_symbol(buf, addr);
+			pr_debug("%5ld: %d  0x%03lx 0x%03lx %s %s\n",
+					i, pos, sp_off, fp_off,
+					check ? "NG" : "OK", buf);
+		}
+	}
+	pr_debug("function prologue analyzer test: %ld errors\n", errors);
+}
+
+static int __init test_function_prologue_analyzer(void)
+{
+	if (start_analyzer_test)
+		do_test_function_prologue_analyzer();
+	return 0;
+}
+late_initcall(test_function_prologue_analyzer);
 #endif /* CONFIG_STACK_TRACER */
 #endif
-- 
1.7.9.5

[PATCH v7 5/6] arm64: ftrace: add arch-specific stack tracer

[Will Deacon]

Hi Akashi,

On Tue, Dec 15, 2015 at 05:33:43PM +0900, AKASHI Takahiro wrote:
> Background and issues on generic check_stack():
> 1) slurping stack
> 
>     Assume that a given function A was invoked, and it was invoked again in
>     another context, then it called another function B which allocated
>     a large size of local variables on the stack, but it has not modified
>     the variable(s) yet.
>     When stack tracer, check_stack(), examines the stack looking for B,
>     then A, we may have a chance to accidentally find a stale, not current,
>     stack frame for A because the old frame might reside on the memory for
>     the variable which has not been overwritten.
> 
>     (issue) The stack_trace output may have stale entries.
> 
> 2) differences between x86 and arm64
> 
>     On x86, "call" instruction automatically pushes a return address on
>     the top of the stack and decrements a stack pointer. Then child
>     function allocates its local variables on the stack.
> 
>     On arm64, a child function is responsible for allocating memory for
>     local variables as well as a stack frame, and explicitly pushes
>     a return address (LR) and old frame pointer in its function prologue
>     *after* decreasing a stack pointer.
> 
>     Generic check_stack() recogizes 'idxB,' which is the next address of
>     the location where 'fpB' is found, in the picture below as an estimated
>     stack pointer. This seems to fine with x86, but on arm64, 'idxB' is
>     not appropriate just because it contains child function's "local
>     variables."
>     We should instead use spB, if possible, for better interpretation of
>     func_B's stack usage.
> 
> LOW      |  ...   |
> fpA      +--------+   func_A (pcA, fpA, spA)
>          |  fpB   |
>     idxB + - - - -+
>          |  pcB   |
>          |  ... <----------- static local variables in func_A
>          |  ...   |             and extra function args to func_A
> spB      + - - - -+
>          |  ... <----------- dynamically allocated variables in func_B
> fpB      +--------+   func_B (pcB, fpB, spB)
>          |  fpC   |
>     idxC + - - - -+
>          |  pcC   |
>          |  ... <----------- static local variables in func_B
>          |  ...   |             and extra function args to func_B
> spC      + - - - -+
>          |  ...   |
> fpC      +--------+   func_C (pcC, fpC, spC)
> HIGH     |        |
> 
>     (issue) Stack size for a function in stack_trace output is inaccurate,
>             or rather wrong.  It looks as if <Size> field is one-line
> 	    offset against <Location>.
> 
>                 Depth    Size   Location    (49 entries)
>                 -----    ----   --------
>          40)     1416      64   path_openat+0x128/0xe00       -> 176
>          41)     1352     176   do_filp_open+0x74/0xf0        -> 256
>          42)     1176     256   do_open_execat+0x74/0x1c8     -> 80
>          43)      920      80   open_exec+0x3c/0x70           -> 32
>          44)      840      32   load_elf_binary+0x294/0x10c8
> 
> Implementation on arm64:
> So we want to have our own stack tracer, check_stack().
> Our approach is uniqeue in the following points:
> * analyze a function prologue of a traced function to estimate a more
>   accurate stack pointer value, replacing naive '<child's fp> + 0x10.'
> * use walk_stackframe(), instead of slurping stack contents as orignal
>   check_stack() does, to identify a stack frame and a stack index (height)
>   for every callsite.
> 
> Regarding a function prologue analyzer, there is no guarantee that we can
> handle all the possible patterns of function prologue as gcc does not use
> any fixed templates to generate them. 'Instruction scheduling' is another
> issue here.

Have you run this past any of the GCC folks? It would be good to at least
make them aware of the heuristics you're using and the types of prologue
that we can handle. They even have suggestions to improve on your approach
(e.g. using -fstack-usage).

> +static void __save_stack_trace_tsk(struct task_struct *tsk,
> +		struct stack_trace *trace, unsigned long *stack_dump_sp)
>  {
>  	struct stack_trace_data data;
>  	struct stackframe frame;
>  
>  	data.trace = trace;
>  	data.skip = trace->skip;
> +#ifdef CONFIG_STACK_TRACER
> +	data.sp = stack_dump_sp;
> +#endif
>  
>  	if (tsk != current) {
>  		data.no_sched_functions = 1;
> @@ -149,7 +319,8 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
>  		data.no_sched_functions = 0;
>  		frame.fp = (unsigned long)__builtin_frame_address(0);
>  		frame.sp = current_stack_pointer;
> -		frame.pc = (unsigned long)save_stack_trace_tsk;
> +		asm("1:");
> +		asm("ldr %0, =1b" : "=r" (frame.pc));

This looks extremely fragile. Does the original code not work?

Will

[PATCH v7 0/6] arm64: ftrace: fix incorrect output from stack tracer

[Will Deacon]

On Tue, Dec 15, 2015 at 05:33:38PM +0900, AKASHI Takahiro wrote:
> This is the seventh patch series to fix ftrace-based stack tracer on
> arm64. The original issue was reported by Jungseok[1], and then I found
> more issues[2].
> 
> We don't have to care about the original issue any more because the root
> cause (patch "ARM64: unwind: Fix PC calculation") has been reverted in
> v4.3.

I've queued the first three patches, but I'm going to hold off on the
prologue analyser until you've got some feedback from the GCC guys.

Will

[PATCH v7 5/6] arm64: ftrace: add arch-specific stack tracer

[AKASHI Takahiro]

On 12/21/2015 09:04 PM, Will Deacon wrote:
> Hi Akashi,
>
> On Tue, Dec 15, 2015 at 05:33:43PM +0900, AKASHI Takahiro wrote:
>> Background and issues on generic check_stack():
>> 1) slurping stack
>>
>>      Assume that a given function A was invoked, and it was invoked again in
>>      another context, then it called another function B which allocated
>>      a large size of local variables on the stack, but it has not modified
>>      the variable(s) yet.
>>      When stack tracer, check_stack(), examines the stack looking for B,
>>      then A, we may have a chance to accidentally find a stale, not current,
>>      stack frame for A because the old frame might reside on the memory for
>>      the variable which has not been overwritten.
>>
>>      (issue) The stack_trace output may have stale entries.
>>
>> 2) differences between x86 and arm64
>>
>>      On x86, "call" instruction automatically pushes a return address on
>>      the top of the stack and decrements a stack pointer. Then child
>>      function allocates its local variables on the stack.
>>
>>      On arm64, a child function is responsible for allocating memory for
>>      local variables as well as a stack frame, and explicitly pushes
>>      a return address (LR) and old frame pointer in its function prologue
>>      *after* decreasing a stack pointer.
>>
>>      Generic check_stack() recogizes 'idxB,' which is the next address of
>>      the location where 'fpB' is found, in the picture below as an estimated
>>      stack pointer. This seems to fine with x86, but on arm64, 'idxB' is
>>      not appropriate just because it contains child function's "local
>>      variables."
>>      We should instead use spB, if possible, for better interpretation of
>>      func_B's stack usage.
>>
>> LOW      |  ...   |
>> fpA      +--------+   func_A (pcA, fpA, spA)
>>           |  fpB   |
>>      idxB + - - - -+
>>           |  pcB   |
>>           |  ... <----------- static local variables in func_A
>>           |  ...   |             and extra function args to func_A
>> spB      + - - - -+
>>           |  ... <----------- dynamically allocated variables in func_B
>> fpB      +--------+   func_B (pcB, fpB, spB)
>>           |  fpC   |
>>      idxC + - - - -+
>>           |  pcC   |
>>           |  ... <----------- static local variables in func_B
>>           |  ...   |             and extra function args to func_B
>> spC      + - - - -+
>>           |  ...   |
>> fpC      +--------+   func_C (pcC, fpC, spC)
>> HIGH     |        |
>>
>>      (issue) Stack size for a function in stack_trace output is inaccurate,
>>              or rather wrong.  It looks as if <Size> field is one-line
>> 	    offset against <Location>.
>>
>>                  Depth    Size   Location    (49 entries)
>>                  -----    ----   --------
>>           40)     1416      64   path_openat+0x128/0xe00       -> 176
>>           41)     1352     176   do_filp_open+0x74/0xf0        -> 256
>>           42)     1176     256   do_open_execat+0x74/0x1c8     -> 80
>>           43)      920      80   open_exec+0x3c/0x70           -> 32
>>           44)      840      32   load_elf_binary+0x294/0x10c8
>>
>> Implementation on arm64:
>> So we want to have our own stack tracer, check_stack().
>> Our approach is uniqeue in the following points:
>> * analyze a function prologue of a traced function to estimate a more
>>    accurate stack pointer value, replacing naive '<child's fp> + 0x10.'
>> * use walk_stackframe(), instead of slurping stack contents as orignal
>>    check_stack() does, to identify a stack frame and a stack index (height)
>>    for every callsite.
>>
>> Regarding a function prologue analyzer, there is no guarantee that we can
>> handle all the possible patterns of function prologue as gcc does not use
>> any fixed templates to generate them. 'Instruction scheduling' is another
>> issue here.
>
> Have you run this past any of the GCC folks?  It would be good to at least
> make them aware of the heuristics you're using and the types of prologue
> that we can handle. They even have suggestions to improve on your approach
> (e.g. using -fstack-usage).

Yeah, I can, but do you mind my including you in CC?
'cause I don't know what kind of comments you are expecting.

>> +static void __save_stack_trace_tsk(struct task_struct *tsk,
>> +		struct stack_trace *trace, unsigned long *stack_dump_sp)
>>   {
>>   	struct stack_trace_data data;
>>   	struct stackframe frame;
>>
>>   	data.trace = trace;
>>   	data.skip = trace->skip;
>> +#ifdef CONFIG_STACK_TRACER
>> +	data.sp = stack_dump_sp;
>> +#endif
>>
>>   	if (tsk != current) {
>>   		data.no_sched_functions = 1;
>> @@ -149,7 +319,8 @@ void save_stack_trace_tsk(struct task_struct *tsk, struct stack_trace *trace)
>>   		data.no_sched_functions = 0;
>>   		frame.fp = (unsigned long)__builtin_frame_address(0);
>>   		frame.sp = current_stack_pointer;
>> -		frame.pc = (unsigned long)save_stack_trace_tsk;
>> +		asm("1:");
>> +		asm("ldr %0, =1b" : "=r" (frame.pc));
>
> This looks extremely fragile. Does the original code not work?

My function prologue analyzer will fail because frame.pc points
to the first instruction of a function.
Otherwise, everything is fine.

Thanks,
-Takahiro AKASHI


> Will
>

[PATCH v7 5/6] arm64: ftrace: add arch-specific stack tracer

[Will Deacon]

On Tue, Dec 22, 2015 at 03:41:03PM +0900, AKASHI Takahiro wrote:
> On 12/21/2015 09:04 PM, Will Deacon wrote:
> >On Tue, Dec 15, 2015 at 05:33:43PM +0900, AKASHI Takahiro wrote:
> >>Regarding a function prologue analyzer, there is no guarantee that we can
> >>handle all the possible patterns of function prologue as gcc does not use
> >>any fixed templates to generate them. 'Instruction scheduling' is another
> >>issue here.
> >
> >Have you run this past any of the GCC folks?  It would be good to at least
> >make them aware of the heuristics you're using and the types of prologue
> >that we can handle. They even have suggestions to improve on your approach
> >(e.g. using -fstack-usage).
> 
> Yeah, I can, but do you mind my including you in CC?
> 'cause I don't know what kind of comments you are expecting.

Sure, I'd be interested to be on Cc. I suspect they will say "we don't
guarantee frame layout, why can't you use -fstack-usage?", to which I
don't have a good answer.

Basically, I don't think a heuristic-based unwinder is supportable in
the long-term, so we need a plan to have unwinding support when building
under future compilers without having to pile more heuristics into this
code. If we have a plan that the compiler guys sign up to, then I'm ok
merging something like you have already as a stop-gap.

Make sense?

Will