[PATCH 0/2] tracing/arm: Fix the stack tracer when LR is saved after local storage

[PATCH 0/2] tracing/arm: Fix the stack tracer when LR is saved after local storage

[Steven Rostedt]

As arm64 saves the link register after a function's local variables are
stored, it causes the max stack tracer to be off by one in its output
of which function has the bloated stack frame.

The first patch fixes this by creating a ARCH_RET_ADDR_BEFORE_LOCAL_VARS
define that an achitecture (arm64) may set in asm/ftrace.h, and this
will cause the stack tracer to make the shift.

As it has been proven that the stack tracer isn't the most trivial
algorithm to understand by staring at the code, the second patch adds
comments to the code to explain the algorithm with and without the
ARCH_RET_ADDR_BEFORE_LOCAL_VARS.

Hmm, should this be sent to stable (and for inclusion now?)

-- Steve

Steven Rostedt (VMware) (2):
      tracing/arm64: Have max stack tracer handle the case of return address after data
      tracing: Document the stack trace algorithm in the comments

----
 arch/arm64/include/asm/ftrace.h |   1 +
 kernel/trace/trace_stack.c      | 112 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 113 insertions(+)

[PATCH 1/2] tracing/arm64: Have max stack tracer handle the case of return address after data

[Steven Rostedt]

From: "Steven Rostedt (VMware)" <rostedt@goodmis.org>

Most archs (well at least x86) store the function call return address on the
stack before storing the local variables for the function. The max stack
tracer depends on this in its algorithm to display the stack size of each
function it finds in the back trace.

Some archs (arm64), may store the return address (from its link register)
just before calling a nested function. There's no reason to save the link
register on leaf functions, as it wont be updated. This breaks the algorithm
of the max stack tracer.

Add a new define ARCH_RET_ADDR_AFTER_LOCAL_VARS that an architecture may set
if it stores the return address (link register) after it stores the
function's local variables, and have the stack trace shift the values of the
mapped stack size to the appropriate functions.

Link: 20190802094103.163576-1-jiping.ma2@windriver.com

Reported-by: Jiping Ma <jiping.ma2@windriver.com>
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
 arch/arm64/include/asm/ftrace.h |  1 +
 kernel/trace/trace_stack.c      | 14 ++++++++++++++
 2 files changed, 15 insertions(+)

diff --git a/arch/arm64/include/asm/ftrace.h b/arch/arm64/include/asm/ftrace.h
index 5ab5200b2bdc..13a4832cfb00 100644
--- a/arch/arm64/include/asm/ftrace.h
+++ b/arch/arm64/include/asm/ftrace.h
@@ -13,6 +13,7 @@
 #define HAVE_FUNCTION_GRAPH_FP_TEST
 #define MCOUNT_ADDR		((unsigned long)_mcount)
 #define MCOUNT_INSN_SIZE	AARCH64_INSN_SIZE
+#define ARCH_RET_ADDR_AFTER_LOCAL_VARS 1
 
 #ifndef __ASSEMBLY__
 #include <linux/compat.h>
diff --git a/kernel/trace/trace_stack.c b/kernel/trace/trace_stack.c
index 5d16f73898db..40e4a88eea8f 100644
--- a/kernel/trace/trace_stack.c
+++ b/kernel/trace/trace_stack.c
@@ -158,6 +158,20 @@ static void check_stack(unsigned long ip, unsigned long *stack)
 			i++;
 	}
 
+#ifdef ARCH_RET_ADDR_AFTER_LOCAL_VARS
+	/*
+	 * Some archs will store the link register before calling
+	 * nested functions. This means the saved return address
+	 * comes after the local storage, and we need to shift
+	 * for that.
+	 */
+	if (x > 1) {
+		memmove(&stack_trace_index[0], &stack_trace_index[1],
+			sizeof(stack_trace_index[0]) * (x - 1));
+		x--;
+	}
+#endif
+
 	stack_trace_nr_entries = x;
 
 	if (task_stack_end_corrupted(current)) {
-- 
2.20.1

[PATCH 2/2] tracing: Document the stack trace algorithm in the comments

[Steven Rostedt]

From: "Steven Rostedt (VMware)" <rostedt@goodmis.org>

As the max stack tracer algorithm is not that easy to understand from the
code, add comments that explain the algorithm and mentions how
ARCH_RET_ADDR_AFTER_LOCAL_VARS affects it.

Link: http://lkml.kernel.org/r/20190806123455.487ac02b@gandalf.local.home

Suggested-by: Joel Fernandes <joel@joelfernandes.org>
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
 kernel/trace/trace_stack.c | 98 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 98 insertions(+)

diff --git a/kernel/trace/trace_stack.c b/kernel/trace/trace_stack.c
index 40e4a88eea8f..7a9a62834af9 100644
--- a/kernel/trace/trace_stack.c
+++ b/kernel/trace/trace_stack.c
@@ -53,6 +53,104 @@ static void print_max_stack(void)
 	}
 }
 
+/*
+ * The stack tracer looks for a maximum stack at each call from a function. It
+ * registers a callback from ftrace, and in that callback it examines the stack
+ * size. It determines the stack size from the variable passed in, which is the
+ * address of a local variable in the stack_trace_call() callback function.
+ * The stack size is calculated by the address of the local variable to the top
+ * of the current stack. If that size is smaller than the currently saved max
+ * stack size, nothing more is done.
+ *
+ * If the size of the stack is greater than the maximum recorded size, then the
+ * following algorithm takes place.
+ *
+ * For architectures (like x86) that store the function's return address before
+ * saving the function's local variables, the stack will look something like
+ * this:
+ *
+ *   [ top of stack ]
+ *    0: sys call entry frame
+ *   10: return addr to entry code
+ *   11: start of sys_foo frame
+ *   20: return addr to sys_foo
+ *   21: start of kernel_func_bar frame
+ *   30: return addr to kernel_func_bar
+ *   31: [ do trace stack here ]
+ *
+ * The save_stack_trace() is called returning all the functions it finds in the
+ * current stack. Which would be (from the bottom of the stack to the top):
+ *
+ *   return addr to kernel_func_bar
+ *   return addr to sys_foo
+ *   return addr to entry code
+ *
+ * Now to figure out how much each of these functions' local variable size is,
+ * a search of the stack is made to find these values. When a match is made, it
+ * is added to the stack_dump_trace[] array. The offset into the stack is saved
+ * in the stack_trace_index[] array. The above example would show:
+ *
+ *        stack_dump_trace[]        |   stack_trace_index[]
+ *        ------------------        +   -------------------
+ *  return addr to kernel_func_bar  |          30
+ *  return addr to sys_foo          |          20
+ *  return addr to entry            |          10
+ *
+ * The print_max_stack() function above, uses these values to print the size of
+ * each function's portion of the stack.
+ *
+ *  for (i = 0; i < nr_entries; i++) {
+ *     size = i == nr_entries - 1 ? stack_trace_index[i] :
+ *                    stack_trace_index[i] - stack_trace_index[i+1]
+ *     print "%d %d %d %s\n", i, stack_trace_index[i], size, stack_dump_trace[i]);
+ *  }
+ *
+ * The above shows
+ *
+ *     depth size  location
+ *     ----- ----  --------
+ *  0    30   10   kernel_func_bar
+ *  1    20   10   sys_foo
+ *  2    10   10   entry code
+ *
+ * Now for architectures that might save the return address after the functions
+ * local variables (saving the link register before calling nested functions),
+ * this will cause the stack to look a little different:
+ *
+ * [ top of stack ]
+ *  0: sys call entry frame
+ * 10: start of sys_foo_frame
+ * 19: return addr to entry code << lr saved before calling kernel_func_bar
+ * 20: start of kernel_func_bar frame
+ * 29: return addr to sys_foo_frame << lr saved before calling next function
+ * 30: [ do trace stack here ]
+ *
+ * Although the functions returned by save_stack_trace() may be the same, the
+ * placement in the stack will be different. Using the same algorithm as above
+ * would yield:
+ *
+ *        stack_dump_trace[]        |   stack_trace_index[]
+ *        ------------------        +   -------------------
+ *  return addr to kernel_func_bar  |          30
+ *  return addr to sys_foo          |          29
+ *  return addr to entry            |          19
+ *
+ * Where the mapping is off by one:
+ *
+ *   kernel_func_bar stack frame size is 29 - 19 not 30 - 29!
+ *
+ * To fix this, if the architecture sets ARCH_RET_ADDR_AFTER_LOCAL_VARS the
+ * values in stack_trace_index[] are shifted by one to and the number of
+ * stack trace entries is decremented by one.
+ *
+ *        stack_dump_trace[]        |   stack_trace_index[]
+ *        ------------------        +   -------------------
+ *  return addr to kernel_func_bar  |          20
+ *  return addr to sys_foo          |          19
+ *
+ * Although the entry function is not displayed, the first function (sys_foo)
+ * will still include the stack size of it.
+ */
 static void check_stack(unsigned long ip, unsigned long *stack)
 {
 	unsigned long this_size, flags; unsigned long *p, *top, *start;
-- 
2.20.1

Re: [PATCH 2/2] tracing: Document the stack trace algorithm in the comments

[Steven Rostedt]

On Wed, 07 Aug 2019 12:34:03 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> From: "Steven Rostedt (VMware)" <rostedt@goodmis.org>

> + * To fix this, if the architecture sets ARCH_RET_ADDR_AFTER_LOCAL_VARS the
> + * values in stack_trace_index[] are shifted by one to and the number of
> + * stack trace entries is decremented by one.
> + *
> + *        stack_dump_trace[]        |   stack_trace_index[]
> + *        ------------------        +   -------------------
> + *  return addr to kernel_func_bar  |          20

That should have been 29, not 20. I'll update it.

-- Steve


> + *  return addr to sys_foo          |          19
> + *
> + * Although the entry function is not displayed, the first function (sys_foo)
> + * will still include the stack size of it.
> + */
>  static void check_stack(unsigned long ip, unsigned long *stack)
>  {
>  	unsigned long this_size, flags; unsigned long *p, *top, *start;

Re: [PATCH 0/2] tracing/arm: Fix the stack tracer when LR is saved after local storage

[Mark Rutland]

Hi Steve,

On Wed, Aug 07, 2019 at 12:34:01PM -0400, Steven Rostedt wrote:
> As arm64 saves the link register after a function's local variables are
> stored, it causes the max stack tracer to be off by one in its output
> of which function has the bloated stack frame.

For reference, it's a bit more complex than that. :/

Our procedure call standard (the AAPCS) says that the frame record may
be placed anywhere within a stackframe, so we don't have a guarantee as
to where the saved lr will fall w.r.t local variables.

Today, GCC happens to create the stack frame by creating the stack
record, so the LR is saved at a lower addresss than the local variables.

However, I am aware that there are reasons why a compiler may choose to
place the frame record at a different locations, e.g. using pointer
authentication to provide an implicit stack canary, so this could change
in future, or potentially differ across functions.

Maybe that's a bridge we'll have to cross in future.

Thanks,
Mark.

> 
> The first patch fixes this by creating a ARCH_RET_ADDR_BEFORE_LOCAL_VARS
> define that an achitecture (arm64) may set in asm/ftrace.h, and this
> will cause the stack tracer to make the shift.
> 
> As it has been proven that the stack tracer isn't the most trivial
> algorithm to understand by staring at the code, the second patch adds
> comments to the code to explain the algorithm with and without the
> ARCH_RET_ADDR_BEFORE_LOCAL_VARS.
> 
> Hmm, should this be sent to stable (and for inclusion now?)
> 
> -- Steve
> 
> Steven Rostedt (VMware) (2):
>       tracing/arm64: Have max stack tracer handle the case of return address after data
>       tracing: Document the stack trace algorithm in the comments
> 
> ----
>  arch/arm64/include/asm/ftrace.h |   1 +
>  kernel/trace/trace_stack.c      | 112 ++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 113 insertions(+)

Re: [PATCH 0/2] tracing/arm: Fix the stack tracer when LR is saved after local storage

[Steven Rostedt]

On Wed, 7 Aug 2019 18:08:14 +0100
Mark Rutland <mark.rutland@arm.com> wrote:

> Hi Steve,
> 
> On Wed, Aug 07, 2019 at 12:34:01PM -0400, Steven Rostedt wrote:
> > As arm64 saves the link register after a function's local variables are
> > stored, it causes the max stack tracer to be off by one in its output
> > of which function has the bloated stack frame.  
> 
> For reference, it's a bit more complex than that. :/

Yeah, I know it is. ;-)

> 
> Our procedure call standard (the AAPCS) says that the frame record may
> be placed anywhere within a stackframe, so we don't have a guarantee as
> to where the saved lr will fall w.r.t local variables.

Yep.

> 
> Today, GCC happens to create the stack frame by creating the stack
> record, so the LR is saved at a lower addresss than the local variables.

Which is what breaks the current algorithm (without this update).

> 
> However, I am aware that there are reasons why a compiler may choose to
> place the frame record at a different locations, e.g. using pointer
> authentication to provide an implicit stack canary, so this could change
> in future, or potentially differ across functions.
> 
> Maybe that's a bridge we'll have to cross in future.

OK, how about I update the change log and add a comment that states
that this can change. But even if it does, it wont break anything but
show the wrong stack size, which is usually only important for us
kernel developers anyway ;-)

Let me send a v2.

-- Steve