[RFC PATCH 0/3] arm64: Implement reliable stack trace

[RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

This patch series aims to implement reliable stacktrace for arm64. 
Reliable stacktrace exists mainly to support live patching, it provides
a version of stacktrace that checks for consistency problems in the
traces it generates and provides an error code to callers indicating if
any problems were detected.      

This is a first cut of support for arm64, I've not really even started
testing it meaningfully at this point.  The main thing I'm looking for
here is that I'm not sure if there are any more potential indicators of
unrelabile stacks that I'm missing tests for or anything about the
interfaces that I've misunderstood.

There's more work that can be done here, mainly that we could sync our
unwinder more with what's done on S/390 and x86 which should if nothing
else help with keeping up to date with generic changes, but this should 
be what's needed to allow reliable stack trace.

Mark Brown (2):
  arm64: stacktrace: Report when we reach the end of the stack
  arm64: stacktrace: Implement reliable stacktrace

Mark Rutland (1):
  arm64: remove EL0 exception frame record

 arch/arm64/Kconfig             |  1 +
 arch/arm64/kernel/entry.S      | 10 +++----
 arch/arm64/kernel/stacktrace.c | 55 ++++++++++++++++++++++++++++------
 3 files changed, 52 insertions(+), 14 deletions(-)

-- 
2.20.1


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[RFC PATCH 1/3] arm64: remove EL0 exception frame record

[Mark Brown]

From: Mark Rutland <mark.rutland@arm.com>

When entering an exception from EL0, the entry code creates a synthetic
frame record with a NULL PC. This was used by the code introduced in
commit:

  7326749801396105 ("arm64: unwind: reference pt_regs via embedded stack frame")

... to discover exception entries on the stack and dump the associated
pt_regs. Since the NULL PC was undesirable for the stacktrace, we added
a special case to unwind_frame() to prevent the NULL PC from being
logged.

Since commit:

  a25ffd3a6302a678 ("arm64: traps: Don't print stack or raw PC/LR values in backtraces")

... we no longer try to dump the pt_regs as part of a stacktrace, and
hence no longer need the synthetic exception record.

This patch removes the synthetic exception record and the associated
special case in unwind_frame(). Instead, EL0 exceptions set the FP to
NULL, as is the case for other terminal records (e.g. when a kernel
thread starts). The synthetic record for exceptions from EL1 is
retrained as this has useful unwind information for the interrupted
context.

To make the terminal case a bit clearer, an explicit check is added to
the start of unwind_frame(). This would otherwise be caught implicitly
by the on_accessible_stack() checks.

Reported-by: Mark Brown <broonie@kernel.org>
Signed-off-by: Mark Rutland <mark.rutland@arm.com>
Signed-off-by: Mark Brown <broonie@kernel.org>
---
 arch/arm64/kernel/entry.S      | 10 +++++-----
 arch/arm64/kernel/stacktrace.c | 13 ++++---------
 2 files changed, 9 insertions(+), 14 deletions(-)

diff --git a/arch/arm64/kernel/entry.S b/arch/arm64/kernel/entry.S
index 55af8b504b65..f7220e9c8520 100644
--- a/arch/arm64/kernel/entry.S
+++ b/arch/arm64/kernel/entry.S
@@ -202,16 +202,16 @@ alternative_cb_end
 	stp	lr, x21, [sp, #S_LR]
 
 	/*
-	 * In order to be able to dump the contents of struct pt_regs at the
-	 * time the exception was taken (in case we attempt to walk the call
-	 * stack later), chain it together with the stack frames.
+	 * For exceptions from EL0, terminate the callchain here.
+	 * For exceptions from EL1, create a synthetic frame record so the
+	 * interrupted code shows up in the backtrace.
 	 */
 	.if \el == 0
-	stp	xzr, xzr, [sp, #S_STACKFRAME]
+	mov	x29, xzr
 	.else
 	stp	x29, x22, [sp, #S_STACKFRAME]
-	.endif
 	add	x29, sp, #S_STACKFRAME
+	.endif
 
 #ifdef CONFIG_ARM64_SW_TTBR0_PAN
 alternative_if_not ARM64_HAS_PAN
diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index fa56af1a59c3..0fb42129b469 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -44,6 +44,10 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 	unsigned long fp = frame->fp;
 	struct stack_info info;
 
+	/* Terminal record; nothing to unwind */
+	if (!fp)
+		return -EINVAL;
+
 	if (fp & 0xf)
 		return -EINVAL;
 
@@ -104,15 +108,6 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 
 	frame->pc = ptrauth_strip_insn_pac(frame->pc);
 
-	/*
-	 * Frames created upon entry from EL0 have NULL FP and PC values, so
-	 * don't bother reporting these. Frames created by __noreturn functions
-	 * might have a valid FP even if PC is bogus, so only terminate where
-	 * both are NULL.
-	 */
-	if (!frame->fp && !frame->pc)
-		return -EINVAL;
-
 	return 0;
 }
 NOKPROBE_SYMBOL(unwind_frame);
-- 
2.20.1


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[RFC PATCH 2/3] arm64: stacktrace: Report when we reach the end of the stack

[Mark Brown]

Currently the arm64 unwinder code returns -EINVAL whenever it can't find
the next stack frame, not distinguishing between cases where the stack has
been corrupted or is otherwise in a state it shouldn't be and cases
where we have reached the end of the stack. At the minute none of the
callers care what error code is returned but this will be important for
reliable stack trace which needs to be sure that the stack is intact.

Change to return -ENOENT in the case where we reach the bottom of the
stack. The error codes from this function are only used in kernel, this
particular code is chosen as we are indicating that we know there is no
frame there.

Signed-off-by: Mark Brown <broonie@kernel.org>
---
 arch/arm64/kernel/stacktrace.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index 0fb42129b469..ad20981dfda4 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -46,7 +46,7 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
 
 	/* Terminal record; nothing to unwind */
 	if (!fp)
-		return -EINVAL;
+		return -ENOENT;
 
 	if (fp & 0xf)
 		return -EINVAL;
-- 
2.20.1


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

[RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Mark Brown]

Live patching has a consistency model which requires that the
architecture provide a reliable stack trace interface which specifically
indicates that the stack has been fully walked and that it is reliable
and consistent. This is done by providing arch_stack_walk_reliable(), a
variant of arch_stack_walk() which should verify that the stack has
these properties and return an error if not.

The arm64 unwinder is already reasonably thorough in verifying the stack
as it walks it and reports errors but we additionally check that
we do not see any kretprobe trampolines on the stack. Since the unwinder
is able to resolve function graph tracer probes transparently we do not
reject those.

Signed-off-by: Mark Brown <broonie@kernel.org>
---
 arch/arm64/Kconfig             |  1 +
 arch/arm64/kernel/stacktrace.c | 42 ++++++++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+)

diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig
index d1ba52e4b976..026f69515a86 100644
--- a/arch/arm64/Kconfig
+++ b/arch/arm64/Kconfig
@@ -174,6 +174,7 @@ config ARM64
 	select HAVE_FUNCTION_ARG_ACCESS_API
 	select HAVE_FUTEX_CMPXCHG if FUTEX
 	select MMU_GATHER_RCU_TABLE_FREE
+	select HAVE_RELIABLE_STACKTRACE
 	select HAVE_RSEQ
 	select HAVE_STACKPROTECTOR
 	select HAVE_SYSCALL_TRACEPOINTS
diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
index ad20981dfda4..795b2c14481d 100644
--- a/arch/arm64/kernel/stacktrace.c
+++ b/arch/arm64/kernel/stacktrace.c
@@ -14,6 +14,7 @@
 #include <linux/stacktrace.h>
 
 #include <asm/irq.h>
+#include <asm/kprobes.h>
 #include <asm/pointer_auth.h>
 #include <asm/stack_pointer.h>
 #include <asm/stacktrace.h>
@@ -212,4 +213,45 @@ void arch_stack_walk(stack_trace_consume_fn consume_entry, void *cookie,
 	walk_stackframe(task, &frame, consume_entry, cookie);
 }
 
+/*
+ * This function returns an error if it detects any unreliable features of the
+ * stack.  Otherwise it guarantees that the stack trace is reliable.
+ *
+ * If the task is not 'current', the caller *must* ensure the task is inactive.
+ */
+int arch_stack_walk_reliable(stack_trace_consume_fn consume_entry,
+			     void *cookie, struct task_struct *task)
+{
+	struct stackframe frame;
+
+	if (task == current)
+		start_backtrace(&frame,
+				(unsigned long)__builtin_frame_address(0),
+				(unsigned long)arch_stack_walk_reliable);
+	else
+		start_backtrace(&frame, thread_saved_fp(task),
+				thread_saved_pc(task));
+
+	while (1) {
+		int ret;
+
+#ifdef CONFIG_KPROBES
+		/*
+		 * Mark stacktraces with kretprobed functions on them
+		 * as unreliable.
+		 */
+		if (frame.pc == (unsigned long)kretprobe_trampoline)
+			return -EINVAL;
+#endif
+
+		if (!consume_entry(cookie, frame.pc))
+			return -EINVAL;
+		ret = unwind_frame(task, &frame);
+		if (ret == -ENOENT)
+			return 0;
+		if (ret < 0)
+			return ret;
+	}
+}
+
 #endif
-- 
2.20.1


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 486 bytes --]

On Mon, Oct 12, 2020 at 06:26:05PM +0100, Mark Brown wrote:

> +#ifdef CONFIG_KPROBES
> +		/*
> +		 * Mark stacktraces with kretprobed functions on them
> +		 * as unreliable.
> +		 */
> +		if (frame.pc == (unsigned long)kretprobe_trampoline)
> +			return -EINVAL;
> +#endif

Sorry, I forgot to say in the cover letter that this needs to have
handling for PAC adding, I was looking at how the trace code handles PAC
more generally and this is only an RFC so didn't finish that bit off.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 2/3] arm64: stacktrace: Report when we reach the end of the stack

[Mark Rutland]

On Mon, Oct 12, 2020 at 06:26:04PM +0100, Mark Brown wrote:
> Currently the arm64 unwinder code returns -EINVAL whenever it can't find
> the next stack frame, not distinguishing between cases where the stack has
> been corrupted or is otherwise in a state it shouldn't be and cases
> where we have reached the end of the stack. At the minute none of the
> callers care what error code is returned but this will be important for
> reliable stack trace which needs to be sure that the stack is intact.
> 
> Change to return -ENOENT in the case where we reach the bottom of the
> stack. The error codes from this function are only used in kernel, this
> particular code is chosen as we are indicating that we know there is no
> frame there.
> 
> Signed-off-by: Mark Brown <broonie@kernel.org>

Acked-by: Mark Rutland <mark.rutland@arm.com>

Mark.

> ---
>  arch/arm64/kernel/stacktrace.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
> index 0fb42129b469..ad20981dfda4 100644
> --- a/arch/arm64/kernel/stacktrace.c
> +++ b/arch/arm64/kernel/stacktrace.c
> @@ -46,7 +46,7 @@ int notrace unwind_frame(struct task_struct *tsk, struct stackframe *frame)
>  
>  	/* Terminal record; nothing to unwind */
>  	if (!fp)
> -		return -EINVAL;
> +		return -ENOENT;
>  
>  	if (fp & 0xf)
>  		return -EINVAL;
> -- 
> 2.20.1
> 

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Mark Rutland]

On Mon, Oct 12, 2020 at 06:26:05PM +0100, Mark Brown wrote:
> Live patching has a consistency model which requires that the
> architecture provide a reliable stack trace interface which specifically
> indicates that the stack has been fully walked and that it is reliable
> and consistent. This is done by providing arch_stack_walk_reliable(), a
> variant of arch_stack_walk() which should verify that the stack has
> these properties and return an error if not.
> 
> The arm64 unwinder is already reasonably thorough in verifying the stack
> as it walks it and reports errors but we additionally check that
> we do not see any kretprobe trampolines on the stack. Since the unwinder
> is able to resolve function graph tracer probes transparently we do not
> reject those.
> 
> Signed-off-by: Mark Brown <broonie@kernel.org>
> ---
>  arch/arm64/Kconfig             |  1 +
>  arch/arm64/kernel/stacktrace.c | 42 ++++++++++++++++++++++++++++++++++
>  2 files changed, 43 insertions(+)
> 
> diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig
> index d1ba52e4b976..026f69515a86 100644
> --- a/arch/arm64/Kconfig
> +++ b/arch/arm64/Kconfig
> @@ -174,6 +174,7 @@ config ARM64
>  	select HAVE_FUNCTION_ARG_ACCESS_API
>  	select HAVE_FUTEX_CMPXCHG if FUTEX
>  	select MMU_GATHER_RCU_TABLE_FREE
> +	select HAVE_RELIABLE_STACKTRACE
>  	select HAVE_RSEQ
>  	select HAVE_STACKPROTECTOR
>  	select HAVE_SYSCALL_TRACEPOINTS
> diff --git a/arch/arm64/kernel/stacktrace.c b/arch/arm64/kernel/stacktrace.c
> index ad20981dfda4..795b2c14481d 100644
> --- a/arch/arm64/kernel/stacktrace.c
> +++ b/arch/arm64/kernel/stacktrace.c
> @@ -14,6 +14,7 @@
>  #include <linux/stacktrace.h>
>  
>  #include <asm/irq.h>
> +#include <asm/kprobes.h>
>  #include <asm/pointer_auth.h>
>  #include <asm/stack_pointer.h>
>  #include <asm/stacktrace.h>
> @@ -212,4 +213,45 @@ void arch_stack_walk(stack_trace_consume_fn consume_entry, void *cookie,
>  	walk_stackframe(task, &frame, consume_entry, cookie);
>  }
>  
> +/*
> + * This function returns an error if it detects any unreliable features of the
> + * stack.  Otherwise it guarantees that the stack trace is reliable.
> + *
> + * If the task is not 'current', the caller *must* ensure the task is inactive.
> + */

Is the caller responsible for pinning a non-current task's stack? e.g.
in dump_backtrace() we do that with try_get_task_stack(). If so, it
might be worth making the comment say "the task is inactive and its
stack is pinned".

> +int arch_stack_walk_reliable(stack_trace_consume_fn consume_entry,
> +			     void *cookie, struct task_struct *task)
> +{
> +	struct stackframe frame;
> +
> +	if (task == current)
> +		start_backtrace(&frame,
> +				(unsigned long)__builtin_frame_address(0),
> +				(unsigned long)arch_stack_walk_reliable);
> +	else
> +		start_backtrace(&frame, thread_saved_fp(task),
> +				thread_saved_pc(task));
> +

Codestyle nit: as these spread over multiple lines the if-else clauses
should have braces.

> +	while (1) {
> +		int ret;
> +
> +#ifdef CONFIG_KPROBES
> +		/*
> +		 * Mark stacktraces with kretprobed functions on them
> +		 * as unreliable.
> +		 */
> +		if (frame.pc == (unsigned long)kretprobe_trampoline)
> +			return -EINVAL;
> +#endif

I'm going to reply separately on this -- I think the check isn't quite
sufficient, and there's a larger semantic problem, so I'll write that up
with the livepatch and arch maintainers on Cc.

Otherwise, (modulo pac stripping) this looks about right to me.

Thanks,
Mark.

> +
> +		if (!consume_entry(cookie, frame.pc))
> +			return -EINVAL;
> +		ret = unwind_frame(task, &frame);
> +		if (ret == -ENOENT)
> +			return 0;
> +		if (ret < 0)
> +			return ret;
> +	}
> +}
> +
>  #endif
> -- 
> 2.20.1
> 

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 1514 bytes --]

On Tue, Oct 13, 2020 at 12:42:30PM +0100, Mark Rutland wrote:
> On Mon, Oct 12, 2020 at 06:26:05PM +0100, Mark Brown wrote:

> > +/*
> > + * This function returns an error if it detects any unreliable features of the
> > + * stack.  Otherwise it guarantees that the stack trace is reliable.
> > + *
> > + * If the task is not 'current', the caller *must* ensure the task is inactive.
> > + */

> Is the caller responsible for pinning a non-current task's stack? e.g.
> in dump_backtrace() we do that with try_get_task_stack(). If so, it
> might be worth making the comment say "the task is inactive and its
> stack is pinned".

Yes, this is done in the generic code by stack_trace_save_reliable()
which should be the only user of this function.  TBH we should probably
move this comment to the prototype in the header rather than duplicating
it in each architecture as is currently done, I was being a bit lazy
there.

> > +int arch_stack_walk_reliable(stack_trace_consume_fn consume_entry,
> > +			     void *cookie, struct task_struct *task)
> > +{
> > +	struct stackframe frame;
> > +
> > +	if (task == current)
> > +		start_backtrace(&frame,
> > +				(unsigned long)__builtin_frame_address(0),
> > +				(unsigned long)arch_stack_walk_reliable);
> > +	else
> > +		start_backtrace(&frame, thread_saved_fp(task),
> > +				thread_saved_pc(task));
> > +

> Codestyle nit: as these spread over multiple lines the if-else clauses
> should have braces.

Usage appears to be a bit varied there for single statements :/

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Miroslav Benes]

On Mon, 12 Oct 2020, Mark Brown wrote:

> +int arch_stack_walk_reliable(stack_trace_consume_fn consume_entry,
> +			     void *cookie, struct task_struct *task)
> +{
> +	struct stackframe frame;
> +
> +	if (task == current)
> +		start_backtrace(&frame,
> +				(unsigned long)__builtin_frame_address(0),
> +				(unsigned long)arch_stack_walk_reliable);
> +	else
> +		start_backtrace(&frame, thread_saved_fp(task),
> +				thread_saved_pc(task));
> +
> +	while (1) {
> +		int ret;
> +
> +#ifdef CONFIG_KPROBES
> +		/*
> +		 * Mark stacktraces with kretprobed functions on them
> +		 * as unreliable.
> +		 */
> +		if (frame.pc == (unsigned long)kretprobe_trampoline)
> +			return -EINVAL;
> +#endif

I think it would be nice to check if frame.pc is a valid text address here
before it is consumed next.

> +		if (!consume_entry(cookie, frame.pc))
> +			return -EINVAL;
> +		ret = unwind_frame(task, &frame);
> +		if (ret == -ENOENT)
> +			return 0;
> +		if (ret < 0)
> +			return ret;
> +	}
> +}

Miroslav

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Miroslav Benes]

Hi,

On Mon, 12 Oct 2020, Mark Brown wrote:

> This patch series aims to implement reliable stacktrace for arm64. 
> Reliable stacktrace exists mainly to support live patching, it provides
> a version of stacktrace that checks for consistency problems in the
> traces it generates and provides an error code to callers indicating if
> any problems were detected.      
> 
> This is a first cut of support for arm64, I've not really even started
> testing it meaningfully at this point.  The main thing I'm looking for
> here is that I'm not sure if there are any more potential indicators of
> unrelabile stacks that I'm missing tests for or anything about the
> interfaces that I've misunderstood.

I'll just copy an excerpt from my notes about the required guarantees. 
Written by Josh (CCed, he has better idea about the problem than me 
anyway).

"
The unwinder needs to be able to detect all stack corruption and return
an error.
[ But note that we don't need to worry about unwinding a task's stack
while the task is running, which can be a common source of
"corruption".  For livepatch we make sure every task is blocked
(except when checking the current task). ]

It also needs to:
- detect preemption / page fault frames and return an error
- only return success if it reaches the end of the task stack; for user
  tasks, that means the syscall barrier; for kthreads/idle tasks, that
  means finding a defined thread entry point
- make sure it can't get into a recursive loop
- make sure each return address is a valid text address
- properly detect generated code hacks like function graph tracing and
  kretprobes
"

Miroslav

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

On Thu, Oct 15, 2020 at 03:39:37PM +0200, Miroslav Benes wrote:
> Hi,

Hi all,

> On Mon, 12 Oct 2020, Mark Brown wrote:
> 
> > This patch series aims to implement reliable stacktrace for arm64. 
> > Reliable stacktrace exists mainly to support live patching, it provides
> > a version of stacktrace that checks for consistency problems in the
> > traces it generates and provides an error code to callers indicating if
> > any problems were detected.      
> > 
> > This is a first cut of support for arm64, I've not really even started
> > testing it meaningfully at this point.  The main thing I'm looking for
> > here is that I'm not sure if there are any more potential indicators of
> > unrelabile stacks that I'm missing tests for or anything about the
> > interfaces that I've misunderstood.
> 
> I'll just copy an excerpt from my notes about the required guarantees. 
> Written by Josh (CCed, he has better idea about the problem than me 
> anyway).
> 
> "
> The unwinder needs to be able to detect all stack corruption and return
> an error.
> [ But note that we don't need to worry about unwinding a task's stack
> while the task is running, which can be a common source of
> "corruption".  For livepatch we make sure every task is blocked
> (except when checking the current task). ]
> 
> It also needs to:
> - detect preemption / page fault frames and return an error
> - only return success if it reaches the end of the task stack; for user
>   tasks, that means the syscall barrier; for kthreads/idle tasks, that
>   means finding a defined thread entry point
> - make sure it can't get into a recursive loop
> - make sure each return address is a valid text address
> - properly detect generated code hacks like function graph tracing and
>   kretprobes
> "

It would be great if we could put something like the above into the
kernel tree, either under Documentation/ or in a comment somewhere for
the reliable stacktrace functions.

AFAICT, existing architectures don't always handle all of the above in
arch_stack_walk_reliable(). For example, it looks like x86 assumes
unwiding through exceptions is reliable for !CONFIG_FRAME_POINTER, but I
think this might not always be true.

I was planning to send a mail once I've finished writing a test, but
IIUC there are some windows where ftrace/kretprobes detection/repainting
may not work, e.g. if preempted after ftrace_return_to_handler()
decrements curr_ret_stack, but before the arch termpoline asm restores
the original return addr. So we might need something like an
in_return_trampoline() to detect and report that reliably.

Thanks,
Mark.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 1619 bytes --]

On Thu, Oct 15, 2020 at 03:16:12PM +0100, Mark Rutland wrote:
> On Thu, Oct 15, 2020 at 03:39:37PM +0200, Miroslav Benes wrote:

> > I'll just copy an excerpt from my notes about the required guarantees. 
> > Written by Josh (CCed, he has better idea about the problem than me 
> > anyway).

> > It also needs to:
> > - detect preemption / page fault frames and return an error
> > - only return success if it reaches the end of the task stack; for user
> >   tasks, that means the syscall barrier; for kthreads/idle tasks, that
> >   means finding a defined thread entry point
> > - make sure it can't get into a recursive loop
> > - make sure each return address is a valid text address
> > - properly detect generated code hacks like function graph tracing and
> >   kretprobes
> > "

> It would be great if we could put something like the above into the
> kernel tree, either under Documentation/ or in a comment somewhere for
> the reliable stacktrace functions.

Yes, please - the expecations are quite hard to follow at the minute,
implementing it involves quite a bit of guesswork and cargo culting to
figure out what the APIs are supposed to do.

> AFAICT, existing architectures don't always handle all of the above in
> arch_stack_walk_reliable(). For example, it looks like x86 assumes
> unwiding through exceptions is reliable for !CONFIG_FRAME_POINTER, but I
> think this might not always be true.

I certainly wouldn't have inferred the list from what's there :/  The
searching for a defined thread entry point for example isn't entirely
visible in the implementations.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 309 bytes --]

On Thu, Oct 15, 2020 at 03:33:44PM +0200, Miroslav Benes wrote:

> I think it would be nice to check if frame.pc is a valid text address here
> before it is consumed next.

I'm wondering if it might be better to do have the generic code do this
in consume_entry() or something, it doesn't seem arch specific?

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

I can't see the original patch.  Can the original poster (Mark B?) add
me to Cc on the next version?

It's also good practice to add lkml as well.  That way, those of us not
copied can at least find the patch in the archives.

live-patching@vger.kernel.org would also be a good idea for this one.

On Thu, Oct 15, 2020 at 04:49:51PM +0100, Mark Brown wrote:
> On Thu, Oct 15, 2020 at 03:16:12PM +0100, Mark Rutland wrote:
> > On Thu, Oct 15, 2020 at 03:39:37PM +0200, Miroslav Benes wrote:
> 
> > > I'll just copy an excerpt from my notes about the required guarantees. 
> > > Written by Josh (CCed, he has better idea about the problem than me 
> > > anyway).
> 
> > > It also needs to:
> > > - detect preemption / page fault frames and return an error
> > > - only return success if it reaches the end of the task stack; for user
> > >   tasks, that means the syscall barrier; for kthreads/idle tasks, that
> > >   means finding a defined thread entry point
> > > - make sure it can't get into a recursive loop
> > > - make sure each return address is a valid text address
> > > - properly detect generated code hacks like function graph tracing and
> > >   kretprobes
> > > "
> 
> > It would be great if we could put something like the above into the
> > kernel tree, either under Documentation/ or in a comment somewhere for
> > the reliable stacktrace functions.
> 
> Yes, please - the expecations are quite hard to follow at the minute,
> implementing it involves quite a bit of guesswork and cargo culting to
> figure out what the APIs are supposed to do.

Documentation is indeed long overdue.  I suppose everyone's looking at
me.  I can do that, but my bandwidth's limited for at least a few weeks.

[ Currently in week 4 of traveling cross-country with a camper
  ("caravan" in British-speak?), National Lampoon vacation style. ]

If by cargo culting, you mean reverse engineering the requirements due
to lack of documentation, that's fair.

Otherwise, if you see anything that doesn't make sense or that can be
improved, let me know.

> > AFAICT, existing architectures don't always handle all of the above in
> > arch_stack_walk_reliable(). For example, it looks like x86 assumes
> > unwiding through exceptions is reliable for !CONFIG_FRAME_POINTER, but I
> > think this might not always be true.

Why not?

What else are the existing arches missing from the above list?

> I certainly wouldn't have inferred the list from what's there :/

Fair, presumably because of missing documentation.

> The searching for a defined thread entry point for example isn't
> entirely visible in the implementations.

For now I'll speak only of x86, because I don't quite remember how
powerpc does it.

For thread entry points, aka the "end" of the stack:

- For ORC, the end of the stack is either pt_regs, or -- when unwinding
  from kthreads, idle tasks, or irqs/exceptions in entry code --
  UNWIND_HINT_EMPTY (found by the unwinder's check for orc->end.

  [ Admittedly the implementation needs to be cleaned up a bit.  EMPTY
    is too broad and needs to be split into UNDEFINED and ENTRY. ]

- For frame pointers, by convention, the end of the stack for all tasks
  is a defined stack offset: end of stack page - sizeof(pt_regs).

And yes, all that needs to be documented.

-- 
Josh

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

I can't see the original patch.  Can the original poster (Mark B?) add
me to Cc on the next version?

It's also good practice to add lkml as well.  That way, those of us not
copied can at least find the patch in the archives.

live-patching@vger.kernel.org would also be a good idea for this one.

On Thu, Oct 15, 2020 at 04:49:51PM +0100, Mark Brown wrote:
> On Thu, Oct 15, 2020 at 03:16:12PM +0100, Mark Rutland wrote:
> > On Thu, Oct 15, 2020 at 03:39:37PM +0200, Miroslav Benes wrote:
> 
> > > I'll just copy an excerpt from my notes about the required guarantees. 
> > > Written by Josh (CCed, he has better idea about the problem than me 
> > > anyway).
> 
> > > It also needs to:
> > > - detect preemption / page fault frames and return an error
> > > - only return success if it reaches the end of the task stack; for user
> > >   tasks, that means the syscall barrier; for kthreads/idle tasks, that
> > >   means finding a defined thread entry point
> > > - make sure it can't get into a recursive loop
> > > - make sure each return address is a valid text address
> > > - properly detect generated code hacks like function graph tracing and
> > >   kretprobes
> > > "
> 
> > It would be great if we could put something like the above into the
> > kernel tree, either under Documentation/ or in a comment somewhere for
> > the reliable stacktrace functions.
> 
> Yes, please - the expecations are quite hard to follow at the minute,
> implementing it involves quite a bit of guesswork and cargo culting to
> figure out what the APIs are supposed to do.

Documentation is indeed long overdue.  I suppose everyone's looking at
me.  I can do that, but my bandwidth's limited for at least a few weeks.

[ Currently in week 4 of traveling cross-country with a camper
  ("caravan" in British-speak?), National Lampoon vacation style. ]

If by cargo culting, you mean reverse engineering the requirements due
to lack of documentation, that's fair.

Otherwise, if you see anything that doesn't make sense or that can be
improved, let me know.

> > AFAICT, existing architectures don't always handle all of the above in
> > arch_stack_walk_reliable(). For example, it looks like x86 assumes
> > unwiding through exceptions is reliable for !CONFIG_FRAME_POINTER, but I
> > think this might not always be true.

Why not?

What else are the existing arches missing from the above list?

> I certainly wouldn't have inferred the list from what's there :/

Fair, presumably because of missing documentation.

> The searching for a defined thread entry point for example isn't
> entirely visible in the implementations.

For now I'll speak only of x86, because I don't quite remember how
powerpc does it.

For thread entry points, aka the "end" of the stack:

- For ORC, the end of the stack is either pt_regs, or -- when unwinding
  from kthreads, idle tasks, or irqs/exceptions in entry code --
  UNWIND_HINT_EMPTY (found by the unwinder's check for orc->end.

  [ Admittedly the implementation needs to be cleaned up a bit.  EMPTY
    is too broad and needs to be split into UNDEFINED and ENTRY. ]

- For frame pointers, by convention, the end of the stack for all tasks
  is a defined stack offset: end of stack page - sizeof(pt_regs).

And yes, all that needs to be documented.

-- 
Josh


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Miroslav Benes]

On Thu, 15 Oct 2020, Mark Brown wrote:

> On Thu, Oct 15, 2020 at 03:33:44PM +0200, Miroslav Benes wrote:
> 
> > I think it would be nice to check if frame.pc is a valid text address here
> > before it is consumed next.
> 
> I'm wondering if it might be better to do have the generic code do this
> in consume_entry() or something, it doesn't seem arch specific?

Maybe. There is currently no special consume_entry() for the reliable 
interface, but I think there is no reason not to introduce one.

On the other hand, both x86 and s390x currently solve it in 
unwind_get_return_address() which is a part of the unwinding 
infrastructure and it would not fit well with the above.

powerpc solves it independently in __save_stack_trace_tsk_reliable() loop, 
which does not use consume_entry() and new stuff at all.

So I don't know if it is worth it.

Miroslav

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

Hi Josh,

On Thu, Oct 15, 2020 at 04:29:31PM -0500, Josh Poimboeuf wrote:
> > > AFAICT, existing architectures don't always handle all of the above in
> > > arch_stack_walk_reliable(). For example, it looks like x86 assumes
> > > unwiding through exceptions is reliable for !CONFIG_FRAME_POINTER, but I
> > > think this might not always be true.
> 
> Why not?

Mark B's reply dropped this, but the next paragraph covered that:

| I was planning to send a mail once I've finished writing a test, but
| IIUC there are some windows where ftrace/kretprobes
| detection/repainting may not work, e.g. if preempted after
| ftrace_return_to_handler() decrements curr_ret_stack, but before the
| arch trampoline asm restores the original return addr. So we might
| need something like an in_return_trampoline() to detect and report
| that reliably.

... so e.g. for a callchain A->B->C, where C is instrumented there are
windows where B might be missing from the trace, but the trace is
reported as reliable.

I'll start a new thread on this (with a more fleshed-out example), with
the full set of livepatch folk, lkml, etc. I just want to write a test
case first, since it's entirely possible something I've missed is
catching this already.

Thanks,
Mark.

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

Hi Josh,

On Thu, Oct 15, 2020 at 04:29:31PM -0500, Josh Poimboeuf wrote:
> > > AFAICT, existing architectures don't always handle all of the above in
> > > arch_stack_walk_reliable(). For example, it looks like x86 assumes
> > > unwiding through exceptions is reliable for !CONFIG_FRAME_POINTER, but I
> > > think this might not always be true.
> 
> Why not?

Mark B's reply dropped this, but the next paragraph covered that:

| I was planning to send a mail once I've finished writing a test, but
| IIUC there are some windows where ftrace/kretprobes
| detection/repainting may not work, e.g. if preempted after
| ftrace_return_to_handler() decrements curr_ret_stack, but before the
| arch trampoline asm restores the original return addr. So we might
| need something like an in_return_trampoline() to detect and report
| that reliably.

... so e.g. for a callchain A->B->C, where C is instrumented there are
windows where B might be missing from the trace, but the trace is
reported as reliable.

I'll start a new thread on this (with a more fleshed-out example), with
the full set of livepatch folk, lkml, etc. I just want to write a test
case first, since it's entirely possible something I've missed is
catching this already.

Thanks,
Mark.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1: Type: text/plain, Size: 2355 bytes --]

On Thu, Oct 15, 2020 at 04:29:31PM -0500, Josh Poimboeuf wrote:
> I can't see the original patch.  Can the original poster (Mark B?) add
> me to Cc on the next version?

https://lore.kernel.org/linux-arm-kernel/20201012172605.10715-1-broonie@kernel.org/

> It's also good practice to add lkml as well.  That way, those of us not
> copied can at least find the patch in the archives.

> live-patching@vger.kernel.org would also be a good idea for this one.

Sorry about that.  I don't know if it's worth including a K: pattern for
arch_stack_walk_reliable() in the livepatch entry in MAINTAINERS?

> If by cargo culting, you mean reverse engineering the requirements due
> to lack of documentation, that's fair.

Yes, exactly - just copying the existing implementations and hoping that
it's sensible/relevant and covers everything that's needed.  It's not
entirely clear what a reliable stacktrace is expected to do that a
normal stacktrace doesn't do beyond returning an error code.

> > The searching for a defined thread entry point for example isn't
> > entirely visible in the implementations.

> For now I'll speak only of x86, because I don't quite remember how
> powerpc does it.

> For thread entry points, aka the "end" of the stack:

> - For ORC, the end of the stack is either pt_regs, or -- when unwinding
>   from kthreads, idle tasks, or irqs/exceptions in entry code --
>   UNWIND_HINT_EMPTY (found by the unwinder's check for orc->end.

>   [ Admittedly the implementation needs to be cleaned up a bit.  EMPTY
>     is too broad and needs to be split into UNDEFINED and ENTRY. ]

> - For frame pointers, by convention, the end of the stack for all tasks
>   is a defined stack offset: end of stack page - sizeof(pt_regs).

> And yes, all that needs to be documented.

Ah, I'd have interpreted "defined thread entry point" as meaning
expecting to find specific functions appering at the end of the stack
rather than meaning positively identifying the end of the stack - for
arm64 we use a NULL frame pointer to indicate this in all situations.
In that case that's one bit that is already clear.

From the list Miroslav posted the bits I wouldn't have inferred were:

 - Detecting preemption/page faults
 - Preventing recursive loops
 - Verifying that return addresses are text addresses

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 2355 bytes --]

On Thu, Oct 15, 2020 at 04:29:31PM -0500, Josh Poimboeuf wrote:
> I can't see the original patch.  Can the original poster (Mark B?) add
> me to Cc on the next version?

https://lore.kernel.org/linux-arm-kernel/20201012172605.10715-1-broonie@kernel.org/

> It's also good practice to add lkml as well.  That way, those of us not
> copied can at least find the patch in the archives.

> live-patching@vger.kernel.org would also be a good idea for this one.

Sorry about that.  I don't know if it's worth including a K: pattern for
arch_stack_walk_reliable() in the livepatch entry in MAINTAINERS?

> If by cargo culting, you mean reverse engineering the requirements due
> to lack of documentation, that's fair.

Yes, exactly - just copying the existing implementations and hoping that
it's sensible/relevant and covers everything that's needed.  It's not
entirely clear what a reliable stacktrace is expected to do that a
normal stacktrace doesn't do beyond returning an error code.

> > The searching for a defined thread entry point for example isn't
> > entirely visible in the implementations.

> For now I'll speak only of x86, because I don't quite remember how
> powerpc does it.

> For thread entry points, aka the "end" of the stack:

> - For ORC, the end of the stack is either pt_regs, or -- when unwinding
>   from kthreads, idle tasks, or irqs/exceptions in entry code --
>   UNWIND_HINT_EMPTY (found by the unwinder's check for orc->end.

>   [ Admittedly the implementation needs to be cleaned up a bit.  EMPTY
>     is too broad and needs to be split into UNDEFINED and ENTRY. ]

> - For frame pointers, by convention, the end of the stack for all tasks
>   is a defined stack offset: end of stack page - sizeof(pt_regs).

> And yes, all that needs to be documented.

Ah, I'd have interpreted "defined thread entry point" as meaning
expecting to find specific functions appering at the end of the stack
rather than meaning positively identifying the end of the stack - for
arm64 we use a NULL frame pointer to indicate this in all situations.
In that case that's one bit that is already clear.

From the list Miroslav posted the bits I wouldn't have inferred were:

 - Detecting preemption/page faults
 - Preventing recursive loops
 - Verifying that return addresses are text addresses

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 3/3] arm64: stacktrace: Implement reliable stacktrace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 822 bytes --]

On Fri, Oct 16, 2020 at 12:13:14PM +0200, Miroslav Benes wrote:
> On Thu, 15 Oct 2020, Mark Brown wrote:
> > On Thu, Oct 15, 2020 at 03:33:44PM +0200, Miroslav Benes wrote:

> > > I think it would be nice to check if frame.pc is a valid text address here
> > > before it is consumed next.

> > I'm wondering if it might be better to do have the generic code do this
> > in consume_entry() or something, it doesn't seem arch specific?

> Maybe. There is currently no special consume_entry() for the reliable 
> interface, but I think there is no reason not to introduce one.

...[Existing implementations handle it]...

> So I don't know if it is worth it.

My thinking was that it's not a huge cost even if it's redundant for the
existing implementations and it's one less thing that people could miss.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Fri, Oct 16, 2020 at 01:15:34PM +0100, Mark Brown wrote:
> 
> Yes, exactly - just copying the existing implementations and hoping that
> it's sensible/relevant and covers everything that's needed.  It's not
> entirely clear what a reliable stacktrace is expected to do that a
> normal stacktrace doesn't do beyond returning an error code.

While in the end there may not be much of a difference between normal
and reliable stacktraces beyond returning an error code, it still
requires beefing up the unwinder's error detection abilities.

> > > The searching for a defined thread entry point for example isn't
> > > entirely visible in the implementations.
> 
> > For now I'll speak only of x86, because I don't quite remember how
> > powerpc does it.
> 
> > For thread entry points, aka the "end" of the stack:
> 
> > - For ORC, the end of the stack is either pt_regs, or -- when unwinding
> >   from kthreads, idle tasks, or irqs/exceptions in entry code --
> >   UNWIND_HINT_EMPTY (found by the unwinder's check for orc->end.
> 
> >   [ Admittedly the implementation needs to be cleaned up a bit.  EMPTY
> >     is too broad and needs to be split into UNDEFINED and ENTRY. ]
> 
> > - For frame pointers, by convention, the end of the stack for all tasks
> >   is a defined stack offset: end of stack page - sizeof(pt_regs).
> 
> > And yes, all that needs to be documented.
> 
> Ah, I'd have interpreted "defined thread entry point" as meaning
> expecting to find specific functions appering at the end of the stack
> rather than meaning positively identifying the end of the stack - for
> arm64 we use a NULL frame pointer to indicate this in all situations.
> In that case that's one bit that is already clear.

I think a NULL frame pointer isn't going to be robust enough.  For
example NULL could easily be introduced by a corrupt stack, or by asm
frame pointer misuse.

-- 
Josh

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Fri, Oct 16, 2020 at 01:15:34PM +0100, Mark Brown wrote:
> 
> Yes, exactly - just copying the existing implementations and hoping that
> it's sensible/relevant and covers everything that's needed.  It's not
> entirely clear what a reliable stacktrace is expected to do that a
> normal stacktrace doesn't do beyond returning an error code.

While in the end there may not be much of a difference between normal
and reliable stacktraces beyond returning an error code, it still
requires beefing up the unwinder's error detection abilities.

> > > The searching for a defined thread entry point for example isn't
> > > entirely visible in the implementations.
> 
> > For now I'll speak only of x86, because I don't quite remember how
> > powerpc does it.
> 
> > For thread entry points, aka the "end" of the stack:
> 
> > - For ORC, the end of the stack is either pt_regs, or -- when unwinding
> >   from kthreads, idle tasks, or irqs/exceptions in entry code --
> >   UNWIND_HINT_EMPTY (found by the unwinder's check for orc->end.
> 
> >   [ Admittedly the implementation needs to be cleaned up a bit.  EMPTY
> >     is too broad and needs to be split into UNDEFINED and ENTRY. ]
> 
> > - For frame pointers, by convention, the end of the stack for all tasks
> >   is a defined stack offset: end of stack page - sizeof(pt_regs).
> 
> > And yes, all that needs to be documented.
> 
> Ah, I'd have interpreted "defined thread entry point" as meaning
> expecting to find specific functions appering at the end of the stack
> rather than meaning positively identifying the end of the stack - for
> arm64 we use a NULL frame pointer to indicate this in all situations.
> In that case that's one bit that is already clear.

I think a NULL frame pointer isn't going to be robust enough.  For
example NULL could easily be introduced by a corrupt stack, or by asm
frame pointer misuse.

-- 
Josh


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

On Fri, Oct 16, 2020 at 12:14:31PM +0100, Mark Rutland wrote:
> Mark B's reply dropped this, but the next paragraph covered that:
> 
> | I was planning to send a mail once I've finished writing a test, but
> | IIUC there are some windows where ftrace/kretprobes
> | detection/repainting may not work, e.g. if preempted after
> | ftrace_return_to_handler() decrements curr_ret_stack, but before the
> | arch trampoline asm restores the original return addr. So we might
> | need something like an in_return_trampoline() to detect and report
> | that reliably.
> 
> ... so e.g. for a callchain A->B->C, where C is instrumented there are
> windows where B might be missing from the trace, but the trace is
> reported as reliable.

I'd missed a couple of details, and I think I see how each existing
architecture prevents this case now.

Josh, just to confirm the x86 case, am I right in thinking that the ORC
unwinder will refuse to unwind from the return_to_handler and
kretprobe_trampoline asm? IIRC objtool shouldn't build unwind info for
those as return_to_handler is marked with SYM_CODE_{START,END}() and
kretprobe_trampoline is marked with STACK_FRAME_NON_STANDARD().

Both powerpc and s390 refuse to reliably unwind through exceptions, so
they can rely on function call boundaries to keep the callchain in a
sane state.

Thanks,
Mark.

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

On Fri, Oct 16, 2020 at 12:14:31PM +0100, Mark Rutland wrote:
> Mark B's reply dropped this, but the next paragraph covered that:
> 
> | I was planning to send a mail once I've finished writing a test, but
> | IIUC there are some windows where ftrace/kretprobes
> | detection/repainting may not work, e.g. if preempted after
> | ftrace_return_to_handler() decrements curr_ret_stack, but before the
> | arch trampoline asm restores the original return addr. So we might
> | need something like an in_return_trampoline() to detect and report
> | that reliably.
> 
> ... so e.g. for a callchain A->B->C, where C is instrumented there are
> windows where B might be missing from the trace, but the trace is
> reported as reliable.

I'd missed a couple of details, and I think I see how each existing
architecture prevents this case now.

Josh, just to confirm the x86 case, am I right in thinking that the ORC
unwinder will refuse to unwind from the return_to_handler and
kretprobe_trampoline asm? IIRC objtool shouldn't build unwind info for
those as return_to_handler is marked with SYM_CODE_{START,END}() and
kretprobe_trampoline is marked with STACK_FRAME_NON_STANDARD().

Both powerpc and s390 refuse to reliably unwind through exceptions, so
they can rely on function call boundaries to keep the callchain in a
sane state.

Thanks,
Mark.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1: Type: text/plain, Size: 773 bytes --]

On Mon, Oct 19, 2020 at 06:41:55PM -0500, Josh Poimboeuf wrote:
> On Fri, Oct 16, 2020 at 01:15:34PM +0100, Mark Brown wrote:

> > Ah, I'd have interpreted "defined thread entry point" as meaning
> > expecting to find specific functions appering at the end of the stack
> > rather than meaning positively identifying the end of the stack - for
> > arm64 we use a NULL frame pointer to indicate this in all situations.
> > In that case that's one bit that is already clear.

> I think a NULL frame pointer isn't going to be robust enough.  For
> example NULL could easily be introduced by a corrupt stack, or by asm
> frame pointer misuse.

Is it just the particular poison value that you're concerned about here
or are you looking for additional checks of some other kind?

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 773 bytes --]

On Mon, Oct 19, 2020 at 06:41:55PM -0500, Josh Poimboeuf wrote:
> On Fri, Oct 16, 2020 at 01:15:34PM +0100, Mark Brown wrote:

> > Ah, I'd have interpreted "defined thread entry point" as meaning
> > expecting to find specific functions appering at the end of the stack
> > rather than meaning positively identifying the end of the stack - for
> > arm64 we use a NULL frame pointer to indicate this in all situations.
> > In that case that's one bit that is already clear.

> I think a NULL frame pointer isn't going to be robust enough.  For
> example NULL could easily be introduced by a corrupt stack, or by asm
> frame pointer misuse.

Is it just the particular poison value that you're concerned about here
or are you looking for additional checks of some other kind?

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Tue, Oct 20, 2020 at 11:03:52AM +0100, Mark Rutland wrote:
> On Fri, Oct 16, 2020 at 12:14:31PM +0100, Mark Rutland wrote:
> > Mark B's reply dropped this, but the next paragraph covered that:
> > 
> > | I was planning to send a mail once I've finished writing a test, but
> > | IIUC there are some windows where ftrace/kretprobes
> > | detection/repainting may not work, e.g. if preempted after
> > | ftrace_return_to_handler() decrements curr_ret_stack, but before the
> > | arch trampoline asm restores the original return addr. So we might
> > | need something like an in_return_trampoline() to detect and report
> > | that reliably.
> > 
> > ... so e.g. for a callchain A->B->C, where C is instrumented there are
> > windows where B might be missing from the trace, but the trace is
> > reported as reliable.
> 
> I'd missed a couple of details, and I think I see how each existing
> architecture prevents this case now.
> 
> Josh, just to confirm the x86 case, am I right in thinking that the ORC
> unwinder will refuse to unwind from the return_to_handler and
> kretprobe_trampoline asm? IIRC objtool shouldn't build unwind info for
> those as return_to_handler is marked with SYM_CODE_{START,END}() and
> kretprobe_trampoline is marked with STACK_FRAME_NON_STANDARD().

Hm, return_to_handler() actually looks like a bug.  UNWIND_HINT_EMPTY
sets end=1, which causes the ORC unwinder to treat it like entry code
(end of the stack).  So while it does stop the unwind, it fails to
report an error.

This would be fixed by the idea I previously mentioned, changing
UNWIND_HINT_EMPTY -> UNWIND_HINT_UNDEFINED (end=0) for the non-entry
cases.  I'll need to work up some patches.

> Both powerpc and s390 refuse to reliably unwind through exceptions, so
> they can rely on function call boundaries to keep the callchain in a
> sane state.

Yes, and also true for x86 frame pointers.

-- 
Josh

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Tue, Oct 20, 2020 at 11:03:52AM +0100, Mark Rutland wrote:
> On Fri, Oct 16, 2020 at 12:14:31PM +0100, Mark Rutland wrote:
> > Mark B's reply dropped this, but the next paragraph covered that:
> > 
> > | I was planning to send a mail once I've finished writing a test, but
> > | IIUC there are some windows where ftrace/kretprobes
> > | detection/repainting may not work, e.g. if preempted after
> > | ftrace_return_to_handler() decrements curr_ret_stack, but before the
> > | arch trampoline asm restores the original return addr. So we might
> > | need something like an in_return_trampoline() to detect and report
> > | that reliably.
> > 
> > ... so e.g. for a callchain A->B->C, where C is instrumented there are
> > windows where B might be missing from the trace, but the trace is
> > reported as reliable.
> 
> I'd missed a couple of details, and I think I see how each existing
> architecture prevents this case now.
> 
> Josh, just to confirm the x86 case, am I right in thinking that the ORC
> unwinder will refuse to unwind from the return_to_handler and
> kretprobe_trampoline asm? IIRC objtool shouldn't build unwind info for
> those as return_to_handler is marked with SYM_CODE_{START,END}() and
> kretprobe_trampoline is marked with STACK_FRAME_NON_STANDARD().

Hm, return_to_handler() actually looks like a bug.  UNWIND_HINT_EMPTY
sets end=1, which causes the ORC unwinder to treat it like entry code
(end of the stack).  So while it does stop the unwind, it fails to
report an error.

This would be fixed by the idea I previously mentioned, changing
UNWIND_HINT_EMPTY -> UNWIND_HINT_UNDEFINED (end=0) for the non-entry
cases.  I'll need to work up some patches.

> Both powerpc and s390 refuse to reliably unwind through exceptions, so
> they can rely on function call boundaries to keep the callchain in a
> sane state.

Yes, and also true for x86 frame pointers.

-- 
Josh


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Tue, Oct 20, 2020 at 04:39:13PM +0100, Mark Brown wrote:
> On Mon, Oct 19, 2020 at 06:41:55PM -0500, Josh Poimboeuf wrote:
> > On Fri, Oct 16, 2020 at 01:15:34PM +0100, Mark Brown wrote:
> 
> > > Ah, I'd have interpreted "defined thread entry point" as meaning
> > > expecting to find specific functions appering at the end of the stack
> > > rather than meaning positively identifying the end of the stack - for
> > > arm64 we use a NULL frame pointer to indicate this in all situations.
> > > In that case that's one bit that is already clear.
> 
> > I think a NULL frame pointer isn't going to be robust enough.  For
> > example NULL could easily be introduced by a corrupt stack, or by asm
> > frame pointer misuse.
> 
> Is it just the particular poison value that you're concerned about here
> or are you looking for additional checks of some other kind?

You just need to know you've conclusively reached the user entry point
on the stack, without missing any functions.

A sufficiently unique poison value might be ok.  Though, defining a
certain stack offset as the "end" seems more robust.

-- 
Josh

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Tue, Oct 20, 2020 at 04:39:13PM +0100, Mark Brown wrote:
> On Mon, Oct 19, 2020 at 06:41:55PM -0500, Josh Poimboeuf wrote:
> > On Fri, Oct 16, 2020 at 01:15:34PM +0100, Mark Brown wrote:
> 
> > > Ah, I'd have interpreted "defined thread entry point" as meaning
> > > expecting to find specific functions appering at the end of the stack
> > > rather than meaning positively identifying the end of the stack - for
> > > arm64 we use a NULL frame pointer to indicate this in all situations.
> > > In that case that's one bit that is already clear.
> 
> > I think a NULL frame pointer isn't going to be robust enough.  For
> > example NULL could easily be introduced by a corrupt stack, or by asm
> > frame pointer misuse.
> 
> Is it just the particular poison value that you're concerned about here
> or are you looking for additional checks of some other kind?

You just need to know you've conclusively reached the user entry point
on the stack, without missing any functions.

A sufficiently unique poison value might be ok.  Though, defining a
certain stack offset as the "end" seems more robust.

-- 
Josh


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 10/12/20 12:26 PM, Mark Brown wrote:
> This patch series aims to implement reliable stacktrace for arm64. 
> Reliable stacktrace exists mainly to support live patching, it provides
> a version of stacktrace that checks for consistency problems in the
> traces it generates and provides an error code to callers indicating if
> any problems were detected.      
> 
> This is a first cut of support for arm64, I've not really even started
> testing it meaningfully at this point.  The main thing I'm looking for
> here is that I'm not sure if there are any more potential indicators of
> unrelabile stacks that I'm missing tests for or anything about the
> interfaces that I've misunderstood.
> 
> There's more work that can be done here, mainly that we could sync our
> unwinder more with what's done on S/390 and x86 which should if nothing
> else help with keeping up to date with generic changes, but this should 
> be what's needed to allow reliable stack trace.
> 
> Mark Brown (2):
>   arm64: stacktrace: Report when we reach the end of the stack
>   arm64: stacktrace: Implement reliable stacktrace
> 
> Mark Rutland (1):
>   arm64: remove EL0 exception frame record
> 
>  arch/arm64/Kconfig             |  1 +
>  arch/arm64/kernel/entry.S      | 10 +++----
>  arch/arm64/kernel/stacktrace.c | 55 ++++++++++++++++++++++++++++------
>  3 files changed, 52 insertions(+), 14 deletions(-)
> 

This is mostly a question to improve my understanding of the current ARM64
unwinder.

Currently, ARM64 defines different stack types - task stack, IRQ stack, etc.
When it unwinds, it appears to unwind only the currently active stack.
Specifically, if an interrupt has happened and the IRQ stack is the one that
is active, only the IRQ stack is unwound. The task stack is not. Is this
accurate?

My question is - for live patching, we would need to look at the task stack
as well, right? May be, we need to pass a flag to the unwinder to check the
task stack in addition to the active task?

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

On Wed, Jan 27, 2021 at 08:02:41AM -0600, Madhavan T. Venkataraman wrote:
> 
> 
> On 10/12/20 12:26 PM, Mark Brown wrote:
> > This patch series aims to implement reliable stacktrace for arm64. 
> > Reliable stacktrace exists mainly to support live patching, it provides
> > a version of stacktrace that checks for consistency problems in the
> > traces it generates and provides an error code to callers indicating if
> > any problems were detected.      
> > 
> > This is a first cut of support for arm64, I've not really even started
> > testing it meaningfully at this point.  The main thing I'm looking for
> > here is that I'm not sure if there are any more potential indicators of
> > unrelabile stacks that I'm missing tests for or anything about the
> > interfaces that I've misunderstood.
> > 
> > There's more work that can be done here, mainly that we could sync our
> > unwinder more with what's done on S/390 and x86 which should if nothing
> > else help with keeping up to date with generic changes, but this should 
> > be what's needed to allow reliable stack trace.
> > 
> > Mark Brown (2):
> >   arm64: stacktrace: Report when we reach the end of the stack
> >   arm64: stacktrace: Implement reliable stacktrace
> > 
> > Mark Rutland (1):
> >   arm64: remove EL0 exception frame record
> > 
> >  arch/arm64/Kconfig             |  1 +
> >  arch/arm64/kernel/entry.S      | 10 +++----
> >  arch/arm64/kernel/stacktrace.c | 55 ++++++++++++++++++++++++++++------
> >  3 files changed, 52 insertions(+), 14 deletions(-)
> > 
> 
> This is mostly a question to improve my understanding of the current ARM64
> unwinder.
> 
> Currently, ARM64 defines different stack types - task stack, IRQ stack, etc.
> When it unwinds, it appears to unwind only the currently active stack.

The current (unreliable) unwinder will unwind across stack changes. That
detects stack transiations and will happily unwind across multiple
stacks so long as these do not loop.

However, where a backtrace crosses an exception boundary, there are
cases where this could in theory omit an entry from the backtrace
because. The LR and FP are only guaranteed to be in a consistent state
at function call boudaries, and since exceptions can be taken in the
middle of functions (or trampolines which transiently place these in an
inconsistent state) we cannot reliably backtrace across exception
boundaries (which may or may not involve a change of stack), unless we
had additional metadata and/or guarantees from compilers on how these
are manipulated.

Where we change stack without an exception boundary, we can reliably
unwind.

> Specifically, if an interrupt has happened and the IRQ stack is the one that
> is active, only the IRQ stack is unwound. The task stack is not. Is this
> accurate?

The existing (unreliable) unwinder will unwind this case. The last frame
record on the IRQ stack will point to a frame record on the task stack,
and the unwinder will determine this can be safely accessed via the
on_accessible_stack() check. It will subsequently reject any frame
records on the IRQ stack (i.e. loops).

> My question is - for live patching, we would need to look at the task stack
> as well, right?

Ideally, we would be able to do this, but currently we cannot safely do
so. IIUC this means that live patching is still possible, but is
potentially much slower to apply updates.

> May be, we need to pass a flag to the unwinder to check the
> task stack in addition to the active task?

The logic to unwind across stack and exception boundaries already
exists, but to make this reliable we will need more invasive work,
potentially changing trampolines and/or adding metadata for these,
perhaps requiring objtool and/or toolchain changes.

Thanks,
Mark.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 1240 bytes --]

On Wed, Jan 27, 2021 at 04:40:56PM +0000, Mark Rutland wrote:
> On Wed, Jan 27, 2021 at 08:02:41AM -0600, Madhavan T. Venkataraman wrote:

> > My question is - for live patching, we would need to look at the task stack
> > as well, right?

> Ideally, we would be able to do this, but currently we cannot safely do
> so. IIUC this means that live patching is still possible, but is
> potentially much slower to apply updates.

That's my understanding, we should just retry until we find the stack to
be reliable.

> > May be, we need to pass a flag to the unwinder to check the
> > task stack in addition to the active task?

> The logic to unwind across stack and exception boundaries already
> exists, but to make this reliable we will need more invasive work,
> potentially changing trampolines and/or adding metadata for these,
> perhaps requiring objtool and/or toolchain changes.

This also requires additional work for shadow call stacks if we end up
using them since we always use a separate shadow call stack for
interrupts rather than nesting on the task shadow call stack, with the
code I've got locally we should just detect that the shadow and task
stacks aren't in sync and report that we can't generate a reliable
stacktrace.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 1/27/21 8:02 AM, Madhavan T. Venkataraman wrote:
> 
> 
> On 10/12/20 12:26 PM, Mark Brown wrote:
>> This patch series aims to implement reliable stacktrace for arm64. 
>> Reliable stacktrace exists mainly to support live patching, it provides
>> a version of stacktrace that checks for consistency problems in the
>> traces it generates and provides an error code to callers indicating if
>> any problems were detected.      
>>
>> This is a first cut of support for arm64, I've not really even started
>> testing it meaningfully at this point.  The main thing I'm looking for
>> here is that I'm not sure if there are any more potential indicators of
>> unrelabile stacks that I'm missing tests for or anything about the
>> interfaces that I've misunderstood.
>>
>> There's more work that can be done here, mainly that we could sync our
>> unwinder more with what's done on S/390 and x86 which should if nothing
>> else help with keeping up to date with generic changes, but this should 
>> be what's needed to allow reliable stack trace.
>>
>> Mark Brown (2):
>>   arm64: stacktrace: Report when we reach the end of the stack
>>   arm64: stacktrace: Implement reliable stacktrace
>>
>> Mark Rutland (1):
>>   arm64: remove EL0 exception frame record
>>
>>  arch/arm64/Kconfig             |  1 +
>>  arch/arm64/kernel/entry.S      | 10 +++----
>>  arch/arm64/kernel/stacktrace.c | 55 ++++++++++++++++++++++++++++------
>>  3 files changed, 52 insertions(+), 14 deletions(-)
>>
> 
> This is mostly a question to improve my understanding of the current ARM64
> unwinder.
> 
> Currently, ARM64 defines different stack types - task stack, IRQ stack, etc.
> When it unwinds, it appears to unwind only the currently active stack.
> Specifically, if an interrupt has happened and the IRQ stack is the one that
> is active, only the IRQ stack is unwound. The task stack is not. Is this
> accurate?
> 
> My question is - for live patching, we would need to look at the task stack
> as well, right? May be, we need to pass a flag to the unwinder to check the
> task stack in addition to the active task?

Typo - I meant to say "active stack" at the end of the question.
Sorry about that.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 10/12/20 12:26 PM, Mark Brown wrote:
> This patch series aims to implement reliable stacktrace for arm64. 
> Reliable stacktrace exists mainly to support live patching, it provides
> a version of stacktrace that checks for consistency problems in the
> traces it generates and provides an error code to callers indicating if
> any problems were detected.      
> 
> This is a first cut of support for arm64, I've not really even started
> testing it meaningfully at this point.  The main thing I'm looking for
> here is that I'm not sure if there are any more potential indicators of
> unrelabile stacks that I'm missing tests for or anything about the
> interfaces that I've misunderstood.
> 
> There's more work that can be done here, mainly that we could sync our
> unwinder more with what's done on S/390 and x86 which should if nothing
> else help with keeping up to date with generic changes, but this should 
> be what's needed to allow reliable stack trace.
> 
> Mark Brown (2):
>   arm64: stacktrace: Report when we reach the end of the stack
>   arm64: stacktrace: Implement reliable stacktrace
> 
> Mark Rutland (1):
>   arm64: remove EL0 exception frame record
> 
>  arch/arm64/Kconfig             |  1 +
>  arch/arm64/kernel/entry.S      | 10 +++----
>  arch/arm64/kernel/stacktrace.c | 55 ++++++++++++++++++++++++++++------
>  3 files changed, 52 insertions(+), 14 deletions(-)
> 

FP and no-FP functions
=====================

I have a suggestion for objtool and the unwinder for ARM64.

IIUC, objtool is responsible for walking all the code paths (except unreachable
and ignored ones) and making sure that every function has proper frame pointer
code (prolog, epilog, etc). If a function is found to not have it, the kernel
build is failed. Is this understanding correct?

If so, can we take a different approach for ARM64?

Instead of failing the kernel build, can we just mark the functions as:

	FP	Functions that have proper FP code
	no-FP	Functions that don't

May be, we can add an "FP" flag in the symbol table entry for this.

Then, the unwinder can check the functions it encounters in the stack trace and
inform the caller if it found any no-FP functions. The caller of the unwinder can
decide what he wants to do with that information.

	- the caller can ignore it

	- the caller can print the stack trace with a warning that no-FP functions
	  were found

	- if the caller is livepatch, the caller can retry until the no-FP functions
	  disappear from the stack trace. This way, we can have live patching even
	  when some of the functions in the kernel are no-FP.

Does this make any sense? Is this acceptable? What are the pitfalls?

If we can do this, the unwinder could detect cases such as:

- If gcc thinks that a function is a leaf function but the function contains
  inline assembly code that calls another function.

- If a call to a function bounces through some intermediate code such as a
  trampoline.

- etc.

For specific no-FP functions, the unwinder might be able to deduce the original
caller. In these cases, the stack trace would still be reliable. For all the others,
the stack trace would be considered unreliable.

Compiler instead of objtool
===========================

If the above suggestion is acceptable, I have another suggestion.

It is a lot of work for every new architecture to add frame pointer verification
support in objtool. Can we get some help from the compiler?

The compiler knows which C functions it generates the FP prolog and epilog for. It can
mark those functions as FP. As for assembly functions, kernel developers could manually
annotate functions that have proper FP code. The compiler/assembler would mark them
as FP. Only a small subset of assembly functions would even have FP prolog and epilog.

Is this acceptable? What are the pitfalls?

This can be implemented easily for all architectures for which the compiler generates
FP code.

Can this be implemented using a GCC plugin? I know squat about GCC plugins.

Thanks!

Madhavan





_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 5226 bytes --]

On Wed, Jan 27, 2021 at 01:54:21PM -0600, Madhavan T. Venkataraman wrote:

Copying in Julien and Josh for the objtool stuff.  I'm replying here but
I'm not 100% up to speed yet so take what I say with a grain of salt.

> FP and no-FP functions
> =====================

This terminology is a bit confusing to me, I keep expanding FP to
floating point here.  Perhaps stack maintanance?

> I have a suggestion for objtool and the unwinder for ARM64.
> 
> IIUC, objtool is responsible for walking all the code paths (except unreachable
> and ignored ones) and making sure that every function has proper frame pointer
> code (prolog, epilog, etc). If a function is found to not have it, the kernel
> build is failed. Is this understanding correct?

Roughly, AIUI.

> If so, can we take a different approach for ARM64?

This feels like something that should just be a stack protector feature
rather than something that an individual architecture should be striking
out on its own with.

> Instead of failing the kernel build, can we just mark the functions as:

> 	FP	Functions that have proper FP code
> 	no-FP	Functions that don't

> May be, we can add an "FP" flag in the symbol table entry for this.

> Then, the unwinder can check the functions it encounters in the stack trace and
> inform the caller if it found any no-FP functions. The caller of the unwinder can
> decide what he wants to do with that information.
> 
> 	- the caller can ignore it
> 
> 	- the caller can print the stack trace with a warning that no-FP functions
> 	  were found
> 
> 	- if the caller is livepatch, the caller can retry until the no-FP functions
> 	  disappear from the stack trace. This way, we can have live patching even
> 	  when some of the functions in the kernel are no-FP.
> 
> Does this make any sense? Is this acceptable? What are the pitfalls?

One downside of this would be that we'd need some way of figuring out if
we've got enough of the kernel covered to be actually useful for
livepatch, and it does mean that we'll have some percentage of code
where the debugging uses for unwinding will be impacted.

It does seem like it's broadly the distinction between the existing
standard and reliable stacktrace interfaces but pushed into the
callback, however reliable stacktrace is going to also perform
additional checks like looking for conditions that might leave things in
an inconsistent state (eg, finding probes or interrupts being taken) so
the distinction isn't just in the binary but also other runtime
conditions.  Reliable stacktrace can also make assumptions that the task
is not currently running unless it is the task doing the trace.  

There was actually until very recently a flag on the callback that is
provided to arch_stack_walk() which indicated if things were supposed to
be reliable but there were no users and nothing ever changed the value,
there was something in a comment or changelog somewhere which said that
this had been for the benefit of printk() but the user had never been
merged.  That sounds a lot like what you're suggesting.

> If we can do this, the unwinder could detect cases such as:

> - If gcc thinks that a function is a leaf function but the function contains
>   inline assembly code that calls another function.

> - If a call to a function bounces through some intermediate code such as a
>   trampoline.

> - etc.

> For specific no-FP functions, the unwinder might be able to deduce the original
> caller. In these cases, the stack trace would still be reliable. For all the others,
> the stack trace would be considered unreliable.

I'm not entirely sure I see the distinction from the current situation
here?

> Compiler instead of objtool
> ===========================
> 
> If the above suggestion is acceptable, I have another suggestion.
> 
> It is a lot of work for every new architecture to add frame pointer verification
> support in objtool. Can we get some help from the compiler?
> 
> The compiler knows which C functions it generates the FP prolog and epilog for. It can
> mark those functions as FP. As for assembly functions, kernel developers could manually
> annotate functions that have proper FP code. The compiler/assembler would mark them
> as FP. Only a small subset of assembly functions would even have FP prolog and epilog.

> Is this acceptable? What are the pitfalls?

If we're trusting the compiler we can probably just do that without any
explicit support from the compiler - it should be doing the standard
stuff unless we explicitly ask it to and if it isn't then it might be a
result of a mismatch in assumptions rather than a deliberate decision to
do something non-standard.  My understanding with objtool is that a big
part of the idea is to provide a static check that the binary we end up
with matches the assumptions that we are making so the fact that it's a
separate implementation is important.

> This can be implemented easily for all architectures for which the compiler generates
> FP code.
> 
> Can this be implemented using a GCC plugin? I know squat about GCC plugins.
> 
> Thanks!
> 
> Madhavan
> 
> 
> 
> 

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

Hi all,

I know this is an old patch set, but I'm not able to see the context,
because I'm not subcribed to the ML.  For future patch sets can you also
add live-patching and lkml?

Are we still considering the shadow stack thing?  Just wondering why
we're talking about objtool again.

On Thu, Jan 28, 2021 at 02:22:50PM +0000, Mark Brown wrote:
> On Wed, Jan 27, 2021 at 01:54:21PM -0600, Madhavan T. Venkataraman wrote:
> > Instead of failing the kernel build, can we just mark the functions as:
> 
> > 	FP	Functions that have proper FP code
> > 	no-FP	Functions that don't
> 
> > May be, we can add an "FP" flag in the symbol table entry for this.
> 
> > Then, the unwinder can check the functions it encounters in the stack trace and
> > inform the caller if it found any no-FP functions. The caller of the unwinder can
> > decide what he wants to do with that information.
> > 
> > 	- the caller can ignore it
> > 
> > 	- the caller can print the stack trace with a warning that no-FP functions
> > 	  were found
> > 
> > 	- if the caller is livepatch, the caller can retry until the no-FP functions
> > 	  disappear from the stack trace. This way, we can have live patching even
> > 	  when some of the functions in the kernel are no-FP.
> > 
> > Does this make any sense? Is this acceptable? What are the pitfalls?

Why not just fix the reported no-FP functions?

> > If we can do this, the unwinder could detect cases such as:
> 
> > - If gcc thinks that a function is a leaf function but the function contains
> >   inline assembly code that calls another function.
> 
> > - If a call to a function bounces through some intermediate code such as a
> >   trampoline.
> 
> > - etc.
> 
> > For specific no-FP functions, the unwinder might be able to deduce the original
> > caller. In these cases, the stack trace would still be reliable. For all the others,
> > the stack trace would be considered unreliable.
> 
> I'm not entirely sure I see the distinction from the current situation
> here?
> 
> > Compiler instead of objtool
> > ===========================
> > 
> > If the above suggestion is acceptable, I have another suggestion.
> > 
> > It is a lot of work for every new architecture to add frame pointer verification
> > support in objtool. Can we get some help from the compiler?
> > 
> > The compiler knows which C functions it generates the FP prolog and epilog for. It can
> > mark those functions as FP. As for assembly functions, kernel developers could manually
> > annotate functions that have proper FP code. The compiler/assembler would mark them
> > as FP. Only a small subset of assembly functions would even have FP prolog and epilog.
> 
> > Is this acceptable? What are the pitfalls?
> 
> If we're trusting the compiler we can probably just do that without any
> explicit support from the compiler - it should be doing the standard
> stuff unless we explicitly ask it to and if it isn't then it might be a
> result of a mismatch in assumptions rather than a deliberate decision to
> do something non-standard.  My understanding with objtool is that a big
> part of the idea is to provide a static check that the binary we end up
> with matches the assumptions that we are making so the fact that it's a
> separate implementation is important.

For C code, even if we trusted the compiler (which we don't), we still
have inline asm which the compiler doesn't have any visibility to, which
is more than capable of messing up frame pointers (we had several cases
of this in x86).

Getting the assembler to annotate which functions are FP could be
interesting but:

a) good luck getting the assembler folks to do that; they tend to be
   insistent on being ignorant of code semantics;

b) assembly often resembles spaghetti and the concept of a function is
   quite fluid; in fact many functions aren't annotated as such.

-- 
Josh


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 1/28/21 9:26 AM, Josh Poimboeuf wrote:
> 
> Hi all,
> 
> I know this is an old patch set, but I'm not able to see the context,
> because I'm not subcribed to the ML.  For future patch sets can you also
> add live-patching and lkml?
> 
> Are we still considering the shadow stack thing?  Just wondering why
> we're talking about objtool again.
> 

I think that we are still considering the shadow stack thing. No discussion
has happened. Based on my limited knowledge of shadow stacks, I think that
shadow stacks do not get rid of objtool.

Here is what I feel about shadow stacks. Please correct me if I am wrong.

Advantages
==========

The only advantage in shadow stacks that I can see is that stack corruption
will not prevent unwinding from happening (unless the shadow stack gets
corrupted somehow).

Issues common with frame pointers
=================================

- The compiler has to generate the prolog and epilog. If we cannot trust the
  compiler to generate these for frame pointers, can we trust it to
  generate these for the shadow stack? If we can't, we would need objtool
  anyway.

- The compiler would only generate shadow stack code for C functions.
  For assembly functions, it has to be done by hand. So, objtool has to
  check this anyway, right?

- Inline assembly in C functions can screw up the shadow stack just like
  it can screw up frame pointers. Again, objtool needs to check.

- Performance hit because of the extra overhead in the prolog and the
  epilog.

Issues unique to shadow stacks
==============================

- Performance hit because of the extra cache and memory footprint. There is
  a paper that says that the performance hit can be as high as 10%. Using
  a parallel shadow stack reduces the hit to about 3.5%. But then again,
  the characteristics for the kernel may be different.

- A separate register has to be reserved for holding the shadow stack
  pointer. The compiler (gcc) has to be changed to not use this register for
  other purposes. And we have to trust that there are no compiler bugs
  in this area. All assembly code that currently uses this register for
  anything needs to be reviewed and potentially changed. This includes
  all inline assembly code. BTW, I believe clang uses x18 for the shadow
  stack pointer register.

- Need to decide if we need a separate shadow stack for task, IRQ,
  overflow, etc. Or, use the same shadow stack. If it is the former,
  we use more memory and need to switch stacks. If it is the latter,
  we need to be aware of the boundaries between the different stack
  traces in the shadow stack.

- longjmp style situations require unwinding the shadow stack by several
  frames.

        - either unwind the shadow stack repeatedly until the return
          address matches with the original stack.

        - for userland code, the shadow stack pointer can be saved in
          setjmp and restored in longjmp. Something similar can be
          done in the kernel.

- Minor issue is the sizing of the shadow stack so there is no overflow.

Questions
=========

Do we have to worry about code that modifies the return address
of a function?

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 1/28/21 9:26 AM, Josh Poimboeuf wrote:
> 
> 
>>
>>> Then, the unwinder can check the functions it encounters in the stack trace and
>>> inform the caller if it found any no-FP functions. The caller of the unwinder can
>>> decide what he wants to do with that information.
>>>
>>> 	- the caller can ignore it
>>>
>>> 	- the caller can print the stack trace with a warning that no-FP functions
>>> 	  were found
>>>
>>> 	- if the caller is livepatch, the caller can retry until the no-FP functions
>>> 	  disappear from the stack trace. This way, we can have live patching even
>>> 	  when some of the functions in the kernel are no-FP.
>>>
>>> Does this make any sense? Is this acceptable? What are the pitfalls?
> 
> Why not just fix the reported no-FP functions?

I was not sure if all warnings can be fixed. For instance, some performance critical
functions may not want the extra overhead of the prolog and epilog. Also, as you
mentioned elsewhere, assembly code is often spaghetti code with multiple labels
and functions sharing code, etc. I am not sure that these can easily be fixed.

To prevent objtool from rejecting these, we have to find some way for objtool to
ignore them so it does not generate any warnings. Is this not correct? For x86,
did guys manage to fix every single warning? I am not familiar with the history
of this. So, I am just assuming.

> 
>>> If we can do this, the unwinder could detect cases such as:
>>
>>> - If gcc thinks that a function is a leaf function but the function contains
>>>   inline assembly code that calls another function.
>>
>>> - If a call to a function bounces through some intermediate code such as a
>>>   trampoline.
>>
>>> - etc.
>>
>>> For specific no-FP functions, the unwinder might be able to deduce the original
>>> caller. In these cases, the stack trace would still be reliable. For all the others,
>>> the stack trace would be considered unreliable.
>>
>> I'm not entirely sure I see the distinction from the current situation
>> here?
>>

Sorry. I should have been clear. If there are no-FP functions that cannot really be
fixed to objtool's satisfaction and objtool is made to ignore them, they may
still show up on the stack and hide their callers.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 1/29/21 3:39 PM, Madhavan T. Venkataraman wrote:
> - A separate register has to be reserved for holding the shadow stack
>   pointer. The compiler (gcc) has to be changed to not use this register for
>   other purposes. And we have to trust that there are no compiler bugs
>   in this area. All assembly code that currently uses this register for
>   anything needs to be reviewed and potentially changed. This includes
>   all inline assembly code. BTW, I believe clang uses x18 for the shadow
>   stack pointer register.

Actually, if the stack and the shadow stack are allocated so that they are
adjacent or at a fixed distance from each other, we don't need a separate
register. We can compute parallel stack addresses from stack addresses by
a simple calculation.

So, this is not an issue.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 4392 bytes --]

On Fri, Jan 29, 2021 at 03:39:35PM -0600, Madhavan T. Venkataraman wrote:
> On 1/28/21 9:26 AM, Josh Poimboeuf wrote:

> > Are we still considering the shadow stack thing?  Just wondering why
> > we're talking about objtool again.

> I think that we are still considering the shadow stack thing. No discussion
> has happened. Based on my limited knowledge of shadow stacks, I think that
> shadow stacks do not get rid of objtool.

I have a slightly messy implementation for compiler generated functions
which I've not posted yet.

> Advantages
> ==========

> The only advantage in shadow stacks that I can see is that stack corruption
> will not prevent unwinding from happening (unless the shadow stack gets
> corrupted somehow).

One of the high level goals with reliable stacktrace is to determine if
we can trust the results of our unwinding, having a duplicate copy of
the function pointer information in the stack helps with this since we
can check that the normal and shadow stacks agree with each other.  This
means that stack corruption, race conditions or general cleverness would
need to result in the same changes being visible in both copies of the
stack so we're more likely to notice if something goes wrong.

> Issues common with frame pointers
> =================================

> - The compiler has to generate the prolog and epilog. If we cannot trust the
>   compiler to generate these for frame pointers, can we trust it to
>   generate these for the shadow stack? If we can't, we would need objtool
>   anyway.

Adding a static check with objtool will always add a degree of trust
that everything is right, though as Ard noted there's always a risk of
false positives too.  It may, however, be the case that there are enough
other checks that people are comfortable even without and we can I'm
sure find things that objtool misses - objtool doesn't mean we should
ignore other checks we can do.

> - The compiler would only generate shadow stack code for C functions.
>   For assembly functions, it has to be done by hand. So, objtool has to
>   check this anyway, right?

We already have annotations in place that allow us to insert prologues
and eplogues into assembly code so this is less intractible than it
might seem, though there's some faff to consider around early boot.
Even without doing this we can readily detect when the shadow stack
update has not been done and reject traces that have affected funtions.

> - Inline assembly in C functions can screw up the shadow stack just like
>   it can screw up frame pointers. Again, objtool needs to check.

As I mentioned above they'd need to change both stacks in the same
manner which is of course possible but harder.

> Issues unique to shadow stacks
> ==============================

> - Performance hit because of the extra cache and memory footprint. There is
>   a paper that says that the performance hit can be as high as 10%. Using
>   a parallel shadow stack reduces the hit to about 3.5%. But then again,
>   the characteristics for the kernel may be different.

10% definitely seems quite out there for the overhead - of course there
is some overhead but that doesn't seem realistic.

> - A separate register has to be reserved for holding the shadow stack
>   pointer. The compiler (gcc) has to be changed to not use this register for
>   other purposes. And we have to trust that there are no compiler bugs
>   in this area. All assembly code that currently uses this register for
>   anything needs to be reviewed and potentially changed. This includes
>   all inline assembly code. BTW, I believe clang uses x18 for the shadow
>   stack pointer register.

Please be aware that we have had shadow call stack support in mainline
since v5.8 when building with clang so if there are correctness problems
then we already have bugs regardless of what happens with reliable stack
trace and live patching.  This is an existing feature which we can use
to improve the robustness of reliable stack trace, it is not something
people are considering doing solely for reliable stack trace.

As you say arm64 uses x18 for the shadow call stack pointer, currently
only clang supports shadow call stacks but I'd be surprised to see GCC
pick up the feature and choose a different register.

> Do we have to worry about code that modifies the return address
> of a function?

Yes, that's definitely a concern.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 1/28/21 9:26 AM, Josh Poimboeuf wrote:
>> If we're trusting the compiler we can probably just do that without any
>> explicit support from the compiler - it should be doing the standard
>> stuff unless we explicitly ask it to and if it isn't then it might be a
>> result of a mismatch in assumptions rather than a deliberate decision to
>> do something non-standard.  My understanding with objtool is that a big
>> part of the idea is to provide a static check that the binary we end up
>> with matches the assumptions that we are making so the fact that it's a
>> separate implementation is important.
> For C code, even if we trusted the compiler (which we don't), we still
> have inline asm which the compiler doesn't have any visibility to, which
> is more than capable of messing up frame pointers (we had several cases
> of this in x86).
> 
> Getting the assembler to annotate which functions are FP could be
> interesting but:
> 
> a) good luck getting the assembler folks to do that; they tend to be
>    insistent on being ignorant of code semantics;
> 
> b) assembly often resembles spaghetti and the concept of a function is
>    quite fluid; in fact many functions aren't annotated as such.

OK. Before this whole discussion, I did not know that the compiler cannot be trusted.
So, it looks like objtool is definitely needed. However, I believe we can minimize
the work objtool does by using a shadow stack.

I read Mark Brown's response to my shadow stack email. I agree with him. The shadow
stack looks promising.

So, here is my suggestion for the shadow stack. This is just to start the discussion
on the shadow stack.

Prolog and epilog for C functions
=================================

Some shadow stack prolog and epilog are needed. Let us add a new option to the compiler
to generate extra no-ops at the beginning of a function for the prolog and just before
return for the epilog so some other entity such as objtool can add its own prolog and
epilog. This is so we don't have to trust the compiler and can maintain our own prolog
and epilog.

Objtool will check for the no-ops. If they are present, it will replace the no-ops with
the shadow stack prolog and epilog. It can also check the frame pointer prolog and
epilog.

Then, it will set a flag in the symbol table entry of the function to indicate that
the function has a proper prolog and epilog.

Prolog and epilog for assembly functions
========================================

The no-ops and frame pointer prolog and epilog can be added to assembly functions manually.
Objtool will process them as above.

Decoding
========

To do all this, objtool has to decode only the following instructions.

        - no-op
        - return instruction
	- store register pair in frame pointer prolog
	- load register pair in frame pointer epilog

This simplifies the objtool part a lot. AFAIK, all instructions in ARM64 are
32 bits wide. So, objtool does not have to decode an instruction to know its
length.

Objtool has to scan a function for the return instruction to know the location(s)
of the epilog.

I guess objtool still has to figure out unreachable code, alternatives and
all that sort of thing. But that logic is already there. Will alternatives
every contain the return instruction? If not, objtool can skip processing
alternatives.

Shadow stack
============

Allocation
----------

Allocate the shadow stack and the regular stack adjacent to each other
or at a fixed distance from each other (may be a guard page in-between?).
This is so the shadow stack can be accessed from any stack address using
a simple calculation.

Top of shadow stack
-------------------

We can either use a compact shadow stack or a parallel shadow stack.
There are trade-offs in each. In either case, we need to know where the
top of the shadow stack is.

We could designate a register for that. But then, we have to make sure that
the register is not used anywhere else. That is a problem.

The alternative is to reserve the first 8 bytes in the shadow stack for the
top of stack pointer.

Prolog
======

Push the previous frame pointer and link register (register that contains
the return address) on the shadow stack.

Epilog
======

Pop the shadow stack.

Scratch registers
=================

A couple of scratch registers have to be used for the prolog and epilog. Perhaps
x16 and x17 can be used? They are supposed to be caller-saved intra procedure call
scratch registers.

Unwinder logic
==============

The unwinder will walk the stack using frame pointers like it does
currently. As it unwinds the regular stack, it will also unwind the
shadow stack:

However, at each step, it needs to perform some additional checks:

        symbol = lookup symbol table entry for pc
        if (!symbol)
                return -EINVAL;

        if (symbol does not have proper prolog and epilog)
                return -EINVAL;

        Compare the information stored on the regular stack with
        that stored on the shadow stack.

        if (the info does not match)
                return -EINVAL;

        Success for this frame


longjmp style situations
========================

Let us say we unwind the regular stack by some number of frames. We need to
unwind the shadow stack as well. After unwinding the regular stack first,
we can just take the current frame pointer of the regular stack and locate
the entry on the shadow stack that matches with that and make that entry the
top of the shadow stack.

Summary
=======

I think a shadow stack will work perfectly for livepatch and will need only
a little help from objtool.

I don't know what the performance will be like though.

I have probably missed some corner cases. Please comment.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

I just reread Mark Brown's email where he said Clang has had this for a while and
there seem to be no issues and GCC will probably pick up the feature as well.
In light of that, this proposal is not needed.

So, please ignore the proposal.

Thanks.

Madhavan

On 2/1/21 9:21 AM, Madhavan T. Venkataraman wrote:
> 
> 
> On 1/28/21 9:26 AM, Josh Poimboeuf wrote:
>>> If we're trusting the compiler we can probably just do that without any
>>> explicit support from the compiler - it should be doing the standard
>>> stuff unless we explicitly ask it to and if it isn't then it might be a
>>> result of a mismatch in assumptions rather than a deliberate decision to
>>> do something non-standard.  My understanding with objtool is that a big
>>> part of the idea is to provide a static check that the binary we end up
>>> with matches the assumptions that we are making so the fact that it's a
>>> separate implementation is important.
>> For C code, even if we trusted the compiler (which we don't), we still
>> have inline asm which the compiler doesn't have any visibility to, which
>> is more than capable of messing up frame pointers (we had several cases
>> of this in x86).
>>
>> Getting the assembler to annotate which functions are FP could be
>> interesting but:
>>
>> a) good luck getting the assembler folks to do that; they tend to be
>>    insistent on being ignorant of code semantics;
>>
>> b) assembly often resembles spaghetti and the concept of a function is
>>    quite fluid; in fact many functions aren't annotated as such.
> 
> OK. Before this whole discussion, I did not know that the compiler cannot be trusted.
> So, it looks like objtool is definitely needed. However, I believe we can minimize
> the work objtool does by using a shadow stack.
> 
> I read Mark Brown's response to my shadow stack email. I agree with him. The shadow
> stack looks promising.
> 
> So, here is my suggestion for the shadow stack. This is just to start the discussion
> on the shadow stack.
> 
> Prolog and epilog for C functions
> =================================
> 
> Some shadow stack prolog and epilog are needed. Let us add a new option to the compiler
> to generate extra no-ops at the beginning of a function for the prolog and just before
> return for the epilog so some other entity such as objtool can add its own prolog and
> epilog. This is so we don't have to trust the compiler and can maintain our own prolog
> and epilog.
> 
> Objtool will check for the no-ops. If they are present, it will replace the no-ops with
> the shadow stack prolog and epilog. It can also check the frame pointer prolog and
> epilog.
> 
> Then, it will set a flag in the symbol table entry of the function to indicate that
> the function has a proper prolog and epilog.
> 
> Prolog and epilog for assembly functions
> ========================================
> 
> The no-ops and frame pointer prolog and epilog can be added to assembly functions manually.
> Objtool will process them as above.
> 
> Decoding
> ========
> 
> To do all this, objtool has to decode only the following instructions.
> 
>         - no-op
>         - return instruction
> 	- store register pair in frame pointer prolog
> 	- load register pair in frame pointer epilog
> 
> This simplifies the objtool part a lot. AFAIK, all instructions in ARM64 are
> 32 bits wide. So, objtool does not have to decode an instruction to know its
> length.
> 
> Objtool has to scan a function for the return instruction to know the location(s)
> of the epilog.
> 
> I guess objtool still has to figure out unreachable code, alternatives and
> all that sort of thing. But that logic is already there. Will alternatives
> every contain the return instruction? If not, objtool can skip processing
> alternatives.
> 
> Shadow stack
> ============
> 
> Allocation
> ----------
> 
> Allocate the shadow stack and the regular stack adjacent to each other
> or at a fixed distance from each other (may be a guard page in-between?).
> This is so the shadow stack can be accessed from any stack address using
> a simple calculation.
> 
> Top of shadow stack
> -------------------
> 
> We can either use a compact shadow stack or a parallel shadow stack.
> There are trade-offs in each. In either case, we need to know where the
> top of the shadow stack is.
> 
> We could designate a register for that. But then, we have to make sure that
> the register is not used anywhere else. That is a problem.
> 
> The alternative is to reserve the first 8 bytes in the shadow stack for the
> top of stack pointer.
> 
> Prolog
> ======
> 
> Push the previous frame pointer and link register (register that contains
> the return address) on the shadow stack.
> 
> Epilog
> ======
> 
> Pop the shadow stack.
> 
> Scratch registers
> =================
> 
> A couple of scratch registers have to be used for the prolog and epilog. Perhaps
> x16 and x17 can be used? They are supposed to be caller-saved intra procedure call
> scratch registers.
> 
> Unwinder logic
> ==============
> 
> The unwinder will walk the stack using frame pointers like it does
> currently. As it unwinds the regular stack, it will also unwind the
> shadow stack:
> 
> However, at each step, it needs to perform some additional checks:
> 
>         symbol = lookup symbol table entry for pc
>         if (!symbol)
>                 return -EINVAL;
> 
>         if (symbol does not have proper prolog and epilog)
>                 return -EINVAL;
> 
>         Compare the information stored on the regular stack with
>         that stored on the shadow stack.
> 
>         if (the info does not match)
>                 return -EINVAL;
> 
>         Success for this frame
> 
> 
> longjmp style situations
> ========================
> 
> Let us say we unwind the regular stack by some number of frames. We need to
> unwind the shadow stack as well. After unwinding the regular stack first,
> we can just take the current frame pointer of the regular stack and locate
> the entry on the shadow stack that matches with that and make that entry the
> top of the shadow stack.
> 
> Summary
> =======
> 
> I think a shadow stack will work perfectly for livepatch and will need only
> a little help from objtool.
> 
> I don't know what the performance will be like though.
> 
> I have probably missed some corner cases. Please comment.
> 
> Madhavan
> 
> _______________________________________________
> linux-arm-kernel mailing list
> linux-arm-kernel@lists.infradead.org
> http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
> 

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

Hi Madhavan,

On Mon, Feb 01, 2021 at 09:21:43AM -0600, Madhavan T. Venkataraman wrote:
> On 1/28/21 9:26 AM, Josh Poimboeuf wrote:
> >> If we're trusting the compiler we can probably just do that without any
> >> explicit support from the compiler - it should be doing the standard
> >> stuff unless we explicitly ask it to and if it isn't then it might be a
> >> result of a mismatch in assumptions rather than a deliberate decision to
> >> do something non-standard.  My understanding with objtool is that a big
> >> part of the idea is to provide a static check that the binary we end up
> >> with matches the assumptions that we are making so the fact that it's a
> >> separate implementation is important.
> > For C code, even if we trusted the compiler (which we don't), we still
> > have inline asm which the compiler doesn't have any visibility to, which
> > is more than capable of messing up frame pointers (we had several cases
> > of this in x86).
> > 
> > Getting the assembler to annotate which functions are FP could be
> > interesting but:
> > 
> > a) good luck getting the assembler folks to do that; they tend to be
> >    insistent on being ignorant of code semantics;
> > 
> > b) assembly often resembles spaghetti and the concept of a function is
> >    quite fluid; in fact many functions aren't annotated as such.
> 
> OK. Before this whole discussion, I did not know that the compiler cannot be trusted.

I think "the compiler cannot be trusted" is overly strong. We want to
*verify* that the compiler is doing what we expect, which might be more
than what it guarantees to do (and those expectations can change over
time), but it doesn't mean we should try to avoid the compiler wherever
possible.

For assembly I expect we'll need to do /some/ manual annotation (e.g.
for trampolines).

> So, it looks like objtool is definitely needed. However, I believe we can minimize
> the work objtool does by using a shadow stack.
> 
> I read Mark Brown's response to my shadow stack email. I agree with him. The shadow
> stack looks promising.
> 
> So, here is my suggestion for the shadow stack. This is just to start the discussion
> on the shadow stack.

Regarding unwinding, shadow stacks have the same problems as frame
records (considering exceptions/interrupts) in that the primary problem
is knowing *when* they are updated, and knowing *when* the LR is
valid or invalid or duplicated (in a frame record or shadow stack
entry).

Given that, I think that assuming we must use a shadow stack for
reliable unwinding would be jumping the gun.

> Prolog and epilog for C functions
> =================================
> 
> Some shadow stack prolog and epilog are needed. Let us add a new option to the compiler
> to generate extra no-ops at the beginning of a function for the prolog and just before
> return for the epilog so some other entity such as objtool can add its own prolog and
> epilog. This is so we don't have to trust the compiler and can maintain our own prolog
> and epilog.

Why wouldn't we ask the compiler to to this, and just check this in the
tooling?

... and if we can do that, why not just check the frame pointer
manipulation?

Note that functions can have multiple return paths, and there might not
be one epilogue. Also, today some functions can have special-cased
prologues for early checks, e.g.

| function:
| 	CBNZ	X0, _func
| 	RET
| 	STP	X29, X30, [SP, #-FRAME_SIZE]
| 	MOV	X29, X30
| 	...
| 	LDP	X29, X30, [SP], #FRAME_SIZE
| 	RET

... and forcing additional work in those could be detrimental.

> Objtool will check for the no-ops. If they are present, it will replace the no-ops with
> the shadow stack prolog and epilog. It can also check the frame pointer prolog and
> epilog.

I suspect this will interact poorly with patchable-function-entry, which
prefixes each instrumentable function with some NOPs.

> Then, it will set a flag in the symbol table entry of the function to indicate that
> the function has a proper prolog and epilog.

I think this boils down to having a prologue and epilogue check, which
seems sane.

> Prolog and epilog for assembly functions
> ========================================
> 
> The no-ops and frame pointer prolog and epilog can be added to assembly functions manually.
> Objtool will process them as above.
> 
> Decoding
> ========
> 
> To do all this, objtool has to decode only the following instructions.
> 
>         - no-op
>         - return instruction
> 	- store register pair in frame pointer prolog
> 	- load register pair in frame pointer epilog
> 
> This simplifies the objtool part a lot. AFAIK, all instructions in ARM64 are
> 32 bits wide. So, objtool does not have to decode an instruction to know its
> length.
> 
> Objtool has to scan a function for the return instruction to know the location(s)
> of the epilog.

That wouldn't be robust if you consider things like:

| func:
| 	STP	x29, x30, [SP, #-FRAME_SIZE]!
|	MOV	X29, SP
| 	B	__fake_ret
|	LDP	X29, X30, [SP], #FRAME_SIZE
|	RET
| __fake_ret:
| 	BL	x30

... which is the sort of thing we want objtool to catch.

[...]

> Unwinder logic
> ==============
> 
> The unwinder will walk the stack using frame pointers like it does
> currently. As it unwinds the regular stack, it will also unwind the
> shadow stack:
> 
> However, at each step, it needs to perform some additional checks:
> 
>         symbol = lookup symbol table entry for pc
>         if (!symbol)
>                 return -EINVAL;
> 
>         if (symbol does not have proper prolog and epilog)
>                 return -EINVAL;

I think at this point, we haven't gained anything from using a shadow
stack, and I'd much rather we used objtool to gather any metadata needed
to make unwinding reliable without mandating a shadow stack.

Thanks,
Mark.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 978 bytes --]

On Mon, Feb 01, 2021 at 04:02:25PM +0000, Mark Rutland wrote:
> On Mon, Feb 01, 2021 at 09:21:43AM -0600, Madhavan T. Venkataraman wrote:

> > OK. Before this whole discussion, I did not know that the compiler cannot be trusted.

> I think "the compiler cannot be trusted" is overly strong. We want to
> *verify* that the compiler is doing what we expect, which might be more
> than what it guarantees to do (and those expectations can change over
> time), but it doesn't mean we should try to avoid the compiler wherever
> possible.

Right, part of what objtool offers here is that it is a static checker
which has an independent implementation of the assumptions we have about
the generated code to that in the compiler - the fact that we've got two
implementations means we're more likely to notice any implementation
drift or unintended changes that affect those assumptions.  Moving code
generation into objtool would mean we were again relying on a single
implementation.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 2/1/21 10:02 AM, Mark Rutland wrote:
> Hi Madhavan,
> 
> On Mon, Feb 01, 2021 at 09:21:43AM -0600, Madhavan T. Venkataraman wrote:
>> On 1/28/21 9:26 AM, Josh Poimboeuf wrote:
>>>> If we're trusting the compiler we can probably just do that without any
>>>> explicit support from the compiler - it should be doing the standard
>>>> stuff unless we explicitly ask it to and if it isn't then it might be a
>>>> result of a mismatch in assumptions rather than a deliberate decision to
>>>> do something non-standard.  My understanding with objtool is that a big
>>>> part of the idea is to provide a static check that the binary we end up
>>>> with matches the assumptions that we are making so the fact that it's a
>>>> separate implementation is important.
>>> For C code, even if we trusted the compiler (which we don't), we still
>>> have inline asm which the compiler doesn't have any visibility to, which
>>> is more than capable of messing up frame pointers (we had several cases
>>> of this in x86).
>>>
>>> Getting the assembler to annotate which functions are FP could be
>>> interesting but:
>>>
>>> a) good luck getting the assembler folks to do that; they tend to be
>>>    insistent on being ignorant of code semantics;
>>>
>>> b) assembly often resembles spaghetti and the concept of a function is
>>>    quite fluid; in fact many functions aren't annotated as such.
>>
>> OK. Before this whole discussion, I did not know that the compiler cannot be trusted.
> 
> I think "the compiler cannot be trusted" is overly strong. We want to
> *verify* that the compiler is doing what we expect, which might be more
> than what it guarantees to do (and those expectations can change over
> time), but it doesn't mean we should try to avoid the compiler wherever
> possible.
> 

Agreed. My intent was also that if the compiler's implementation is not
performant, we could implement our own, if necessary. For instance, if
the compiler implements a compact stack and we want to implement a
parallel stack in the kernel for performance, the compiler's prolog and
epilog will not work for us.

But if we are happy with what the compiler is providing, I am fine
with it.

> For assembly I expect we'll need to do /some/ manual annotation (e.g.
> for trampolines).
> 
>> So, it looks like objtool is definitely needed. However, I believe we can minimize
>> the work objtool does by using a shadow stack.
>>
>> I read Mark Brown's response to my shadow stack email. I agree with him. The shadow
>> stack looks promising.
>>
>> So, here is my suggestion for the shadow stack. This is just to start the discussion
>> on the shadow stack.
> 
> Regarding unwinding, shadow stacks have the same problems as frame
> records (considering exceptions/interrupts) in that the primary problem
> is knowing *when* they are updated, and knowing *when* the LR is
> valid or invalid or duplicated (in a frame record or shadow stack
> entry).
> 

True. This is a problem for the unwinder in general.

So, I have a few questions from a livepatch perspective.

For livepatch, the kernel makes sure that task is not running when its stack is checked,
correct? The only possibility I can think of is that the task could have received an
interrupt and could have been preempted at the end of the interrupt. The interrupt
could have happened during the frame pointer prolog or epilog. Is this the problem case
for livepatch?

If the unwinder could check a flag in the task that indicates that the task was interrupted,
the unwinder could declare the stack trace unreliable. E.g., a (hacky) solution could
be to set and clear the flag in preempt_schedule_irq() which takes a task off a CPU
when it is preempted at the end of an interrupt. The flag would remain set while the task is not
on a CPU.

Similarly, for exceptions, can we set a flag in a task indicating that it is processing
an exception? Is there a top level exception handler where we can do this? Is there common
code that exception handlers use where we can set this? Or, can we deduce this from ptregs->pstate
that is saved for the task?

Mind you, the flag is advisory. If the unwinder has some way to unwind through an exception,
more power to it.

> Given that, I think that assuming we must use a shadow stack for
> reliable unwinding would be jumping the gun.
>

So, this is the problem I was considering. Let us say that a function properly sets up the
frame pointer at the beginning and properly restores it to the previous value when it
returns. But because of compiler bugs or some inline assembly code or other errant code,
the frame pointer gets modified in the middle of the function. Then, the function calls
another function. Then, the unwinder tries to unwind the stack. The unwinder has no
way of knowing that the frame pointer was modified. To tackle this problem, Objtool
has to laboriously walk all the code paths and track every modification to the stack and
the frame pointer. And, if there are frame modifications, it has to fail the kernel build.
Did I understand it correctly?

In these cases, the shadow stack can be used to unwind the stack. The shadow stack has
return addresses pushed on it. For livepatch purposes, this good enough.


>> Prolog and epilog for C functions
>> =================================
>>
>> Some shadow stack prolog and epilog are needed. Let us add a new option to the compiler
>> to generate extra no-ops at the beginning of a function for the prolog and just before
>> return for the epilog so some other entity such as objtool can add its own prolog and
>> epilog. This is so we don't have to trust the compiler and can maintain our own prolog
>> and epilog.
> 
> Why wouldn't we ask the compiler to to this, and just check this in the
> tooling?
> 
> ... and if we can do that, why not just check the frame pointer
> manipulation?
> 

I am fine with the compiler doing it and objtool checking it. I was just thinking
that the conventional compact shadow stack is not very performant based on studies.
While it may be OK for apps, it may not be OK for the kernel.

But this is something that we have to actually measure. May be, we can use Clang and
do an experiment to get some measurements.

> Note that functions can have multiple return paths, and there might not
> be one epilogue. Also, today some functions can have special-cased
> prologues for early checks, e.g.
> 
> | function:
> | 	CBNZ	X0, _func
> | 	RET
> | 	STP	X29, X30, [SP, #-FRAME_SIZE]
> | 	MOV	X29, X30
> | 	...
> | 	LDP	X29, X30, [SP], #FRAME_SIZE
> | 	RET
> 
> ... and forcing additional work in those could be detrimental.
> 

I did not say that there would only be one return instruction for a function.
But my bad. I forgot to include the branch instruction as something that also
has to be decoded so objtool can follow all the code paths within a function.
Anyway, whatever needs to be decoded to follow all the paths within a function
must be done.

>> Objtool will check for the no-ops. If they are present, it will replace the no-ops with
>> the shadow stack prolog and epilog. It can also check the frame pointer prolog and
>> epilog.
> 
> I suspect this will interact poorly with patchable-function-entry, which
> prefixes each instrumentable function with some NOPs.
> 

Objtool knows if the kernel was configured with tracing. The compiler inserts a fixed,
known number of no-ops for tracing purposes. So, why is it difficult for objtool to
find the prolog/epilog no-ops?

Mind you, I am already fine with the compiler generating the code.

>> Then, it will set a flag in the symbol table entry of the function to indicate that
>> the function has a proper prolog and epilog.
> 
> I think this boils down to having a prologue and epilogue check, which
> seems sane.
> 

Yes. That is fine.

>> Prolog and epilog for assembly functions
>> ========================================
>>
>> The no-ops and frame pointer prolog and epilog can be added to assembly functions manually.
>> Objtool will process them as above.
>>
>> Decoding
>> ========
>>
>> To do all this, objtool has to decode only the following instructions.
>>
>>         - no-op
>>         - return instruction
>> 	- store register pair in frame pointer prolog
>> 	- load register pair in frame pointer epilog
>>
>> This simplifies the objtool part a lot. AFAIK, all instructions in ARM64 are
>> 32 bits wide. So, objtool does not have to decode an instruction to know its
>> length.
>>
>> Objtool has to scan a function for the return instruction to know the location(s)
>> of the epilog.
> 
> That wouldn't be robust if you consider things like:
> 
> | func:
> | 	STP	x29, x30, [SP, #-FRAME_SIZE]!
> |	MOV	X29, SP
> | 	B	__fake_ret
> |	LDP	X29, X30, [SP], #FRAME_SIZE
> |	RET
> | __fake_ret:
> | 	BL	x30
> 
> ... which is the sort of thing we want objtool to catch.
> 

Objtool has to follow all the code paths to check every single possible return
as I mentioned above.

> [...]
> 
>> Unwinder logic
>> ==============
>>
>> The unwinder will walk the stack using frame pointers like it does
>> currently. As it unwinds the regular stack, it will also unwind the
>> shadow stack:
>>
>> However, at each step, it needs to perform some additional checks:
>>
>>         symbol = lookup symbol table entry for pc
>>         if (!symbol)
>>                 return -EINVAL;
>>
>>         if (symbol does not have proper prolog and epilog)
>>                 return -EINVAL;
> 
> I think at this point, we haven't gained anything from using a shadow
> stack, and I'd much rather we used objtool to gather any metadata needed
> to make unwinding reliable without mandating a shadow stack.
> 

I think we have gained something. Pushing the return addresses on the shadow stack
and using them to unwind means that objtool does not have to decode every single
instruction and track the changes to the stack and frame state. It also means
that the kernel build does not have to be failed when some frame modification is
detected by objtool.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 2/1/21 10:22 AM, Mark Brown wrote:
> On Mon, Feb 01, 2021 at 04:02:25PM +0000, Mark Rutland wrote:
>> On Mon, Feb 01, 2021 at 09:21:43AM -0600, Madhavan T. Venkataraman wrote:
> 
>>> OK. Before this whole discussion, I did not know that the compiler cannot be trusted.
> 
>> I think "the compiler cannot be trusted" is overly strong. We want to
>> *verify* that the compiler is doing what we expect, which might be more
>> than what it guarantees to do (and those expectations can change over
>> time), but it doesn't mean we should try to avoid the compiler wherever
>> possible.
> 
> Right, part of what objtool offers here is that it is a static checker
> which has an independent implementation of the assumptions we have about
> the generated code to that in the compiler - the fact that we've got two
> implementations means we're more likely to notice any implementation
> drift or unintended changes that affect those assumptions.  Moving code
> generation into objtool would mean we were again relying on a single
> implementation.
> 

Agreed. And I am fine with the compiler doing it and objtool checking it.
If we find that the compiler's implementation does not perform well
enough for the kernel, we can revisit this point.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

Sorry for the late reply.

On 1/28/21 8:22 AM, Mark Brown wrote:
> On Wed, Jan 27, 2021 at 01:54:21PM -0600, Madhavan T. Venkataraman wrote:
> 
> Copying in Julien and Josh for the objtool stuff.  I'm replying here but
> I'm not 100% up to speed yet so take what I say with a grain of salt.
> 
>> FP and no-FP functions
>> =====================
> 
> This terminology is a bit confusing to me, I keep expanding FP to
> floating point here.  Perhaps stack maintanance?
> 

I will just say frame pointer.

>> I have a suggestion for objtool and the unwinder for ARM64.
>>
>> IIUC, objtool is responsible for walking all the code paths (except unreachable
>> and ignored ones) and making sure that every function has proper frame pointer
>> code (prolog, epilog, etc). If a function is found to not have it, the kernel
>> build is failed. Is this understanding correct?
> 
> Roughly, AIUI.
> 
>> If so, can we take a different approach for ARM64?
> 
> This feels like something that should just be a stack protector feature
> rather than something that an individual architecture should be striking
> out on its own with.
> 

Yes, it is a stack feature. It may mean less work that objtool has to do
for reliable stack trace. I am not trying to eliminate objtool.


>> Instead of failing the kernel build, can we just mark the functions as:
> 
>> 	FP	Functions that have proper FP code
>> 	no-FP	Functions that don't
> 
>> May be, we can add an "FP" flag in the symbol table entry for this.
> 
>> Then, the unwinder can check the functions it encounters in the stack trace and
>> inform the caller if it found any no-FP functions. The caller of the unwinder can
>> decide what he wants to do with that information.
>>
>> 	- the caller can ignore it
>>
>> 	- the caller can print the stack trace with a warning that no-FP functions
>> 	  were found
>>
>> 	- if the caller is livepatch, the caller can retry until the no-FP functions
>> 	  disappear from the stack trace. This way, we can have live patching even
>> 	  when some of the functions in the kernel are no-FP.
>>
>> Does this make any sense? Is this acceptable? What are the pitfalls?
> 
> One downside of this would be that we'd need some way of figuring out if
> we've got enough of the kernel covered to be actually useful for
> livepatch, and it does mean that we'll have some percentage of code
> where the debugging uses for unwinding will be impacted.
> 

Agreed. I am not actually saying that no-frame pointer functions should not be
fixed. We should really fix them. But some may not be fixable because of their
nature. And, some may be deferred because of their complexity. That should not
be a show stopper for livepatch.

> It does seem like it's broadly the distinction between the existing
> standard and reliable stacktrace interfaces but pushed into the
> callback, however reliable stacktrace is going to also perform
> additional checks like looking for conditions that might leave things in
> an inconsistent state (eg, finding probes or interrupts being taken) so
> the distinction isn't just in the binary but also other runtime
> conditions.  Reliable stacktrace can also make assumptions that the task
> is not currently running unless it is the task doing the trace.  
> 

Agreed.

> There was actually until very recently a flag on the callback that is
> provided to arch_stack_walk() which indicated if things were supposed to
> be reliable but there were no users and nothing ever changed the value,
> there was something in a comment or changelog somewhere which said that
> this had been for the benefit of printk() but the user had never been
> merged.  That sounds a lot like what you're suggesting.
> 

I will take a look.

>> If we can do this, the unwinder could detect cases such as:
> 
>> - If gcc thinks that a function is a leaf function but the function contains
>>   inline assembly code that calls another function.
> 
>> - If a call to a function bounces through some intermediate code such as a
>>   trampoline.
> 
>> - etc.
> 
>> For specific no-FP functions, the unwinder might be able to deduce the original
>> caller. In these cases, the stack trace would still be reliable. For all the others,
>> the stack trace would be considered unreliable.
> 
> I'm not entirely sure I see the distinction from the current situation
> here?
> 

Currently, the unwinder does not know that a function that it encounters in the stack
trace is no-frame pointer. No-frame pointer functions hide their callers in the stack
trace. Objtool addresses that problem through static analysis.

I am proposing that we do this detection dynamically so we can do livepatching even
if the kernel has no-frame pointer functions.

>> Compiler instead of objtool
>> ===========================
>>
>> If the above suggestion is acceptable, I have another suggestion.
>>
>> It is a lot of work for every new architecture to add frame pointer verification
>> support in objtool. Can we get some help from the compiler?
>>
>> The compiler knows which C functions it generates the FP prolog and epilog for. It can
>> mark those functions as FP. As for assembly functions, kernel developers could manually
>> annotate functions that have proper FP code. The compiler/assembler would mark them
>> as FP. Only a small subset of assembly functions would even have FP prolog and epilog.
> 
>> Is this acceptable? What are the pitfalls?
> 
> If we're trusting the compiler we can probably just do that without any
> explicit support from the compiler - it should be doing the standard
> stuff unless we explicitly ask it to and if it isn't then it might be a
> result of a mismatch in assumptions rather than a deliberate decision to
> do something non-standard.  My understanding with objtool is that a big
> part of the idea is to provide a static check that the binary we end up
> with matches the assumptions that we are making so the fact that it's a
> separate implementation is important.
> 

Agreed. Static checks are necessary. I am only trying to see if the number
of static checks we have to do in objtool can be minimized. Also, should
every static check failure fail the kernel build?

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Mon, Feb 01, 2021 at 03:38:53PM -0600, Madhavan T. Venkataraman wrote:
> So, I have a few questions from a livepatch perspective.
> 
> For livepatch, the kernel makes sure that task is not running when its stack is checked,
> correct?

Correct.

> The only possibility I can think of is that the task could have received an
> interrupt and could have been preempted at the end of the interrupt. The interrupt
> could have happened during the frame pointer prolog or epilog. Is this the problem case
> for livepatch?
> 
> If the unwinder could check a flag in the task that indicates that the task was interrupted,
> the unwinder could declare the stack trace unreliable. E.g., a (hacky) solution could
> be to set and clear the flag in preempt_schedule_irq() which takes a task off a CPU
> when it is preempted at the end of an interrupt. The flag would remain set while the task is not
> on a CPU.
> 
> Similarly, for exceptions, can we set a flag in a task indicating that it is processing
> an exception? Is there a top level exception handler where we can do this? Is there common
> code that exception handlers use where we can set this? Or, can we deduce this from ptregs->pstate
> that is saved for the task?
> 
> Mind you, the flag is advisory. If the unwinder has some way to unwind through an exception,
> more power to it.

For x86 (frame pointers), entry code uses ENCODE_FRAME_POINTER, which
creates a special pt_regs frame.

When the reliable unwinder sees the encoded regs on the stack, it knows
it encountered some asynchronous event, like preemption, and it marks
the stack unreliable.

> > Given that, I think that assuming we must use a shadow stack for
> > reliable unwinding would be jumping the gun.
> >
> 
> So, this is the problem I was considering. Let us say that a function properly sets up the
> frame pointer at the beginning and properly restores it to the previous value when it
> returns. But because of compiler bugs or some inline assembly code or other errant code,
> the frame pointer gets modified in the middle of the function. Then, the function calls
> another function. Then, the unwinder tries to unwind the stack. The unwinder has no
> way of knowing that the frame pointer was modified. To tackle this problem, Objtool
> has to laboriously walk all the code paths and track every modification to the stack and
> the frame pointer. And, if there are frame modifications, it has to fail the kernel build.
> Did I understand it correctly?

Yes, though it generally warns instead of failing the build.  But we
keep the warnings to zero as best we can.

BTW, the most common inline asm frame pointer bug we saw on x86 was a
call instruction which got inserted by GCC before the prologue -- or
sometimes there was no prologue because it was otherwise considered a
leaf function.

> In these cases, the shadow stack can be used to unwind the stack. The shadow stack has
> return addresses pushed on it. For livepatch purposes, this good enough.

We try to fix every warning.  For the few warnings we whitelist instead
of fixing, we make sure it's not a risk for live patching.

> >> Objtool will check for the no-ops. If they are present, it will replace the no-ops with
> >> the shadow stack prolog and epilog. It can also check the frame pointer prolog and
> >> epilog.
> > 
> > I suspect this will interact poorly with patchable-function-entry, which
> > prefixes each instrumentable function with some NOPs.
> > 
> 
> Objtool knows if the kernel was configured with tracing. The compiler inserts a fixed,
> known number of no-ops for tracing purposes. So, why is it difficult for objtool to
> find the prolog/epilog no-ops?

Objtool tries to stay out of the code generation business.  Because then
who's going to validate objtool's code :-)

And the compiler already does a decent job at generating it.

> > I think at this point, we haven't gained anything from using a shadow
> > stack, and I'd much rather we used objtool to gather any metadata needed
> > to make unwinding reliable without mandating a shadow stack.
> > 
> 
> I think we have gained something. Pushing the return addresses on the shadow stack
> and using them to unwind means that objtool does not have to decode every single
> instruction and track the changes to the stack and frame state. It also means
> that the kernel build does not have to be failed when some frame modification is
> detected by objtool.

How do we know the kernel has full and accurate CFI coverage?

The original version of objtool was an awk script which basically just
crudely looked for the prologue/epilogue instructions.  It mostly
worked.

But it wasn't 100%, and these days the prologue isn't always at the
beginning, and the epilogue is usually buried in the middle.  And
sometimes there are more stack pushes/pops hidden outside of the formal
prologue/epilogue.  Not to mention asm code which does all kinds of
crazy things.  And other edge cases, like leaf functions which don't
require frame pointers, and alternatives patching/paravirt/etc which can
muck with the stack layout at runtime.  Eventually we realized a "full
coverage" objtool is the wisest approach.

Also, a simpler version of objtool isn't really an option on the x86
side, since we now have a lot of other features relying on its full
coverage.  Other than the decoder, most of the objtool logic is
arch-independent.

-- 
Josh


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 2/1/21 5:00 PM, Josh Poimboeuf wrote:
> On Mon, Feb 01, 2021 at 03:38:53PM -0600, Madhavan T. Venkataraman wrote:
>> So, I have a few questions from a livepatch perspective.
>>
>> For livepatch, the kernel makes sure that task is not running when its stack is checked,
>> correct?
> 
> Correct.
> 
>> The only possibility I can think of is that the task could have received an
>> interrupt and could have been preempted at the end of the interrupt. The interrupt
>> could have happened during the frame pointer prolog or epilog. Is this the problem case
>> for livepatch?
>>
>> If the unwinder could check a flag in the task that indicates that the task was interrupted,
>> the unwinder could declare the stack trace unreliable. E.g., a (hacky) solution could
>> be to set and clear the flag in preempt_schedule_irq() which takes a task off a CPU
>> when it is preempted at the end of an interrupt. The flag would remain set while the task is not
>> on a CPU.
>>
>> Similarly, for exceptions, can we set a flag in a task indicating that it is processing
>> an exception? Is there a top level exception handler where we can do this? Is there common
>> code that exception handlers use where we can set this? Or, can we deduce this from ptregs->pstate
>> that is saved for the task?
>>
>> Mind you, the flag is advisory. If the unwinder has some way to unwind through an exception,
>> more power to it.
> 
> For x86 (frame pointers), entry code uses ENCODE_FRAME_POINTER, which
> creates a special pt_regs frame.
> 
> When the reliable unwinder sees the encoded regs on the stack, it knows
> it encountered some asynchronous event, like preemption, and it marks
> the stack unreliable.
> 

Ok. Good to know.

>>> Given that, I think that assuming we must use a shadow stack for
>>> reliable unwinding would be jumping the gun.
>>>
>>
>> So, this is the problem I was considering. Let us say that a function properly sets up the
>> frame pointer at the beginning and properly restores it to the previous value when it
>> returns. But because of compiler bugs or some inline assembly code or other errant code,
>> the frame pointer gets modified in the middle of the function. Then, the function calls
>> another function. Then, the unwinder tries to unwind the stack. The unwinder has no
>> way of knowing that the frame pointer was modified. To tackle this problem, Objtool
>> has to laboriously walk all the code paths and track every modification to the stack and
>> the frame pointer. And, if there are frame modifications, it has to fail the kernel build.
>> Did I understand it correctly?
> 
> Yes, though it generally warns instead of failing the build.  But we
> keep the warnings to zero as best we can.
> 

ok.

> BTW, the most common inline asm frame pointer bug we saw on x86 was a
> call instruction which got inserted by GCC before the prologue -- or
> sometimes there was no prologue because it was otherwise considered a
> leaf function.
> 

ok.

>> In these cases, the shadow stack can be used to unwind the stack. The shadow stack has
>> return addresses pushed on it. For livepatch purposes, this good enough.
> 
> We try to fix every warning.  For the few warnings we whitelist instead
> of fixing, we make sure it's not a risk for live patching.
> 

ok.

>>>> Objtool will check for the no-ops. If they are present, it will replace the no-ops with
>>>> the shadow stack prolog and epilog. It can also check the frame pointer prolog and
>>>> epilog.
>>>
>>> I suspect this will interact poorly with patchable-function-entry, which
>>> prefixes each instrumentable function with some NOPs.
>>>
>>
>> Objtool knows if the kernel was configured with tracing. The compiler inserts a fixed,
>> known number of no-ops for tracing purposes. So, why is it difficult for objtool to
>> find the prolog/epilog no-ops?
> 
> Objtool tries to stay out of the code generation business.  Because then
> who's going to validate objtool's code :-)
> 
> And the compiler already does a decent job at generating it.
> 

The no-ops were just a wild idea of mine. I knew I would rue it as soon as I hit
the send button :-)

>>> I think at this point, we haven't gained anything from using a shadow
>>> stack, and I'd much rather we used objtool to gather any metadata needed
>>> to make unwinding reliable without mandating a shadow stack.
>>>
>>
>> I think we have gained something. Pushing the return addresses on the shadow stack
>> and using them to unwind means that objtool does not have to decode every single
>> instruction and track the changes to the stack and frame state. It also means
>> that the kernel build does not have to be failed when some frame modification is
>> detected by objtool.
> 
> How do we know the kernel has full and accurate CFI coverage?
> 

I need to study this before I can answer.

> The original version of objtool was an awk script which basically just
> crudely looked for the prologue/epilogue instructions.  It mostly
> worked.
> 
> But it wasn't 100%, and these days the prologue isn't always at the
> beginning, and the epilogue is usually buried in the middle.  And
> sometimes there are more stack pushes/pops hidden outside of the formal
> prologue/epilogue.  Not to mention asm code which does all kinds of
> crazy things.  And other edge cases, like leaf functions which don't
> require frame pointers, and alternatives patching/paravirt/etc which can
> muck with the stack layout at runtime.  Eventually we realized a "full
> coverage" objtool is the wisest approach.
> 

Yes. I studied the objtool code. It does a fantastic job for X86. I suspect
it took a lot of time and a lot of work to get it right. It is
just that adding complete static analysis for an arch is daunting and
time consuming. How would we ever prove to the community that we are
truly done?

I am attempting to define a way where we can say - if these conditions are
met, then the stack is reliable. Else, it is unreliable without having to
analyze all the different ways it can be unreliable. Easier said than
done!

> Also, a simpler version of objtool isn't really an option on the x86
> side, since we now have a lot of other features relying on its full
> coverage.  Other than the decoder, most of the objtool logic is
> arch-independent.
> 

ok.

Thanks for all the info. Appreciate it.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Josh Poimboeuf]

On Mon, Feb 01, 2021 at 08:29:52PM -0600, Madhavan T. Venkataraman wrote:
> The no-ops were just a wild idea of mine. I knew I would rue it as soon as I hit
> the send button :-)

That's ok, I like wild ideas :-)

> > The original version of objtool was an awk script which basically just
> > crudely looked for the prologue/epilogue instructions.  It mostly
> > worked.
> > 
> > But it wasn't 100%, and these days the prologue isn't always at the
> > beginning, and the epilogue is usually buried in the middle.  And
> > sometimes there are more stack pushes/pops hidden outside of the formal
> > prologue/epilogue.  Not to mention asm code which does all kinds of
> > crazy things.  And other edge cases, like leaf functions which don't
> > require frame pointers, and alternatives patching/paravirt/etc which can
> > muck with the stack layout at runtime.  Eventually we realized a "full
> > coverage" objtool is the wisest approach.
> > 
> 
> Yes. I studied the objtool code. It does a fantastic job for X86. I suspect
> it took a lot of time and a lot of work to get it right. It is
> just that adding complete static analysis for an arch is daunting and
> time consuming. How would we ever prove to the community that we are
> truly done?

Objtool makes sure to visit all instructions in the file.  Otherwise it
prints an "unreachable instruction" warning.  That's how we make sure to
get full coverage.

And most compiled code is pretty straightforward, so the static analysis
is mostly "just" a matter of monitoring stack operations and following
the branches.  Of course, the devil's in the details.

It gets battle-tested pretty well with randconfigs across a lot of
different compiler versions.  When it encounters some situation it
doesn't understand, it complains, and we hear about it.

Julien and Raphael already laid a lot of the groundwork for porting it
to new arches, so as you can see with Julien's latest series there's not
much to do beyond adding the instruction decoder, and then looking at
all the warnings.

Sometimes warnings are legit, and other times they mean something's
amiss with objtool.  But once the warnings are all gone, in my
experience it means objtool's working well.

-- 
Josh


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

On Mon, Feb 01, 2021 at 03:38:53PM -0600, Madhavan T. Venkataraman wrote:
> On 2/1/21 10:02 AM, Mark Rutland wrote:
> > On Mon, Feb 01, 2021 at 09:21:43AM -0600, Madhavan T. Venkataraman wrote:
> >> On 1/28/21 9:26 AM, Josh Poimboeuf wrote:
> >> Decoding
> >> ========
> >>
> >> To do all this, objtool has to decode only the following instructions.
> >>
> >>         - no-op
> >>         - return instruction
> >> 	- store register pair in frame pointer prolog
> >> 	- load register pair in frame pointer epilog
> >>
> >> This simplifies the objtool part a lot. AFAIK, all instructions in ARM64 are
> >> 32 bits wide. So, objtool does not have to decode an instruction to know its
> >> length.
> >>
> >> Objtool has to scan a function for the return instruction to know the location(s)
> >> of the epilog.
> > 
> > That wouldn't be robust if you consider things like:
> > 
> > | func:
> > | 	STP	x29, x30, [SP, #-FRAME_SIZE]!
> > |	MOV	X29, SP
> > | 	B	__fake_ret
> > |	LDP	X29, X30, [SP], #FRAME_SIZE
> > |	RET
> > | __fake_ret:
> > | 	BL	x30
> > 
> > ... which is the sort of thing we want objtool to catch.
> 
> Objtool has to follow all the code paths to check every single possible return
> as I mentioned above.

Here I was pointing out that in order to do so you need to decode and
reason about more than NOP, RET, STP, and LDP, and you need to reason
about the logical function of an instruction (e.g. here the last LDP is
emulating a RET).

> 
> > [...]
> > 
> >> Unwinder logic
> >> ==============
> >>
> >> The unwinder will walk the stack using frame pointers like it does
> >> currently. As it unwinds the regular stack, it will also unwind the
> >> shadow stack:
> >>
> >> However, at each step, it needs to perform some additional checks:
> >>
> >>         symbol = lookup symbol table entry for pc
> >>         if (!symbol)
> >>                 return -EINVAL;
> >>
> >>         if (symbol does not have proper prolog and epilog)
> >>                 return -EINVAL;
> > 
> > I think at this point, we haven't gained anything from using a shadow
> > stack, and I'd much rather we used objtool to gather any metadata needed
> > to make unwinding reliable without mandating a shadow stack.
> > 
> 
> I think we have gained something. Pushing the return addresses on the shadow stack
> and using them to unwind means that objtool does not have to decode every single
> instruction and track the changes to the stack and frame state.

I think that practically speaking it's necessary to track all potential
paths through functions that may alter the shadow stack or the shadow
stack pointer to ensure that the manipulation is well-balanced and that
the shadow stack pointer isn't corrupted.

Practically speaking, this requires decoding a significant number of
instructions, and tracing through all potential paths a function may
take.

Thanks,
Mark.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 2/2/21 4:05 AM, Mark Rutland wrote:
>>> I think at this point, we haven't gained anything from using a shadow
>>> stack, and I'd much rather we used objtool to gather any metadata needed
>>> to make unwinding reliable without mandating a shadow stack.
>>>
>> I think we have gained something. Pushing the return addresses on the shadow stack
>> and using them to unwind means that objtool does not have to decode every single
>> instruction and track the changes to the stack and frame state.
> I think that practically speaking it's necessary to track all potential
> paths through functions that may alter the shadow stack or the shadow
> stack pointer to ensure that the manipulation is well-balanced and that
> the shadow stack pointer isn't corrupted.
> 
> Practically speaking, this requires decoding a significant number of
> instructions, and tracing through all potential paths a function may
> take.

I am not sure why the shadow stack should be modified by any function.
It is a shadow stack. Functions are not supposed to be aware of it
(except for the prolog and epilog).

For C functions, the compiler would reserve the shadow stack pointer
register and not use it for anything other than prolog and epilog.

If the worry is that some kernel developer may unknowingly use the register
in assembly code and we need to catch this during kernel build, we can do it
using grep. The only code that is allowed to modify it is the macros that we
define for prolog and epilog. This can be done using a simple script.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 2/2/21 4:05 AM, Mark Rutland wrote:
>> Objtool has to follow all the code paths to check every single possible return
>> as I mentioned above.
> Here I was pointing out that in order to do so you need to decode and
> reason about more than NOP, RET, STP, and LDP, and you need to reason
> about the logical function of an instruction (e.g. here the last LDP is
> emulating a RET).
> 

Agreed. In addition to the instructions I pointed out, the other control transfer
instruction(s) like branches (but not calls) should be decoded.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Brown]

[-- Attachment #1.1: Type: text/plain, Size: 636 bytes --]

On Mon, Feb 01, 2021 at 03:59:50PM -0600, Madhavan T. Venkataraman wrote:

> Agreed. Static checks are necessary. I am only trying to see if the number
> of static checks we have to do in objtool can be minimized. Also, should
> every static check failure fail the kernel build?

At the end of the day this is like any other warning or error detection
check - it's a bit of a judgement call per problem detected which
depends on how confident we are in the accuracy of the static check (is
it prone to false positives?), how serious the issue identified is, how
reliant we are on the behaviour being checked for and so on.  

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 484 bytes --]

[-- Attachment #2: Type: text/plain, Size: 176 bytes --]

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 2/2/21 4:05 AM, Mark Rutland wrote:
> I think that practically speaking it's necessary to track all potential
> paths through functions that may alter the shadow stack or the shadow
> stack pointer to ensure that the manipulation is well-balanced and that
> the shadow stack pointer isn't corrupted.
> 
> Practically speaking, this requires decoding a significant number of
> instructions, and tracing through all potential paths a function may
> take.

I thought about it some more since you don't like the shadow stack that much.
I think I can achieve what I want with a simpler design without any shadow
stack and with better performance than a shadow stack. It needs a slightly
changed prolog and epilog. Please review this and comment.

In this design, I need 8 bytes of storage for recording the current frame pointer
address. Space at the bottom of the stack can be reserved for this easily.
I will use cur_fp to refer to the value at that memory location.

For this discussion, fp refers to the frame pointer register and sp refers to the
stack pointer register.

The goal is - even if a function modifies fp and/or does not restore sp to its
correct value at the end, the prolog and epilog should manage it so that everything
works. To do this, the current frame pointer address is stored in fp as well as cur_fp.
Even if fp is modified, cur_fp will still point to the correct frame address.

Prolog
=======

The original prolog is:

- Push fp and return address on the stack
- fp = sp


The new prolog is:

- Save cur_fp on the stack
- Push fp, return address on the stack
- fp = sp
- cur_fp = fp

Epilog
======

The original epilog is:

- Pop fp and return address

The new epilog is:

- sp = cur_fp
- Pop fp and return address
- Restore cur_fp from the stack


I think this is pretty simple.

Unwinder
========


The unwinder will start the stack walk from cur_fp instead of fp. At each frame,
it will use the saved cur_fp instead of the saved fp. 

Also, at each step, it can know if fp was actually changed by the function in
the frame. The unwinder can optionally issue warnings.


Compiler issue
===============

This solution is geared towards the kernel only. It assumes that the stack
has a fixed size and alignment so the bottom of the stack can be reached
from the current sp.

So, the compiler has to support two prologs and epilogs, one pair for apps
and one pair for the kernel.

Since this is just a tiny bit of code, I don't think this is a problem.

Finally, objtool can verify the prolog and epilog.

Is this general solution acceptable? We can always work out details.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Mark Rutland]

On Tue, Feb 02, 2021 at 05:32:32PM -0600, Madhavan T. Venkataraman wrote:
> On 2/2/21 4:05 AM, Mark Rutland wrote:
> > I think that practically speaking it's necessary to track all potential
> > paths through functions that may alter the shadow stack or the shadow
> > stack pointer to ensure that the manipulation is well-balanced and that
> > the shadow stack pointer isn't corrupted.
> > 
> > Practically speaking, this requires decoding a significant number of
> > instructions, and tracing through all potential paths a function may
> > take.
> 
> I thought about it some more since you don't like the shadow stack
> that much.

Just to be clear, what I was trying to get across was:

* Whatever we do, we want to verify at compile time that the kernel
  binary matches our expecations, and practically speaking this almost
  certainly means using objtool.

* The analysis that objtool will have to do is not made significantly
  simpler through the use of a shadow stack, as it still needs to track
  all paths though a function, etc.

I'm not averse to using a shadow stack (and clang's SCS is a useful
security feature), I just don't think that it helps much with
compile-time verification, and I don't see a strong reason to mandate it
for livepatching.

[...]

> The goal is - even if a function modifies fp and/or does not restore sp to its
> correct value at the end, the prolog and epilog should manage it so that everything
> works. To do this, the current frame pointer address is stored in fp as well as cur_fp.
> Even if fp is modified, cur_fp will still point to the correct frame address.
> 
> Prolog
> =======
> 
> The original prolog is:
> 
> - Push fp and return address on the stack
> - fp = sp
> 
> 
> The new prolog is:
> 
> - Save cur_fp on the stack
> - Push fp, return address on the stack
> - fp = sp
> - cur_fp = fp
> 
> Epilog
> ======
> 
> The original epilog is:
> 
> - Pop fp and return address
> 
> The new epilog is:
> 
> - sp = cur_fp
> - Pop fp and return address
> - Restore cur_fp from the stack
> 
> 
> I think this is pretty simple.

I'm afraid I don't understand the problem you're trying to solve here.
The epilog you propose is also unsound in the face of asynchronous
exceptions, so I suspect you haven't thought as hard about this as you
need to.

Even if the compiler uses a different prologue/epilogue sequence, we
still need to verify that the rest of the function does nothing to
undermine that.

I think this is merely different rather than simpler, and regardless
this would be an invasive change to compilers.

> Unwinder
> ========
> 
> The unwinder will start the stack walk from cur_fp instead of fp. At each frame,
> it will use the saved cur_fp instead of the saved fp. 
> 
> Also, at each step, it can know if fp was actually changed by the function in
> the frame. The unwinder can optionally issue warnings.

So this is just about aditional robustness?

I'm happy to use a shadow stack for /additional/ robustness, I just
don't think a shadow stack alone solves all the other issues that we
need compile time verification for, nor does it solve cases where we
might want metadata generated at compile time.

> Compiler issue
> ===============
> 
> This solution is geared towards the kernel only. It assumes that the stack
> has a fixed size and alignment so the bottom of the stack can be reached
> from the current sp.
> 
> So, the compiler has to support two prologs and epilogs, one pair for apps
> and one pair for the kernel.
> 
> Since this is just a tiny bit of code, I don't think this is a problem.

I suspect it's more compilated than that. Configuration differences like
this can easily double the necessary testing, and are liable to becomer
a maintenance burden, so I don't expect compiler folk are likely to want
to support this unless necessary.

At the moment, I don't think that this solves a real problem, and I
don't think that we need to change this.

In future, we might want to agree some constraints with toolchain folk
if we have specific concerns or pain points, but I don't think we've
actually enumerated those and why we can't solve them through over
means.

Thanks,
Mark.

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

On 2/3/21 10:53 AM, Mark Rutland wrote:
> On Tue, Feb 02, 2021 at 05:32:32PM -0600, Madhavan T. Venkataraman wrote:
>> On 2/2/21 4:05 AM, Mark Rutland wrote:
>>> I think that practically speaking it's necessary to track all potential
>>> paths through functions that may alter the shadow stack or the shadow
>>> stack pointer to ensure that the manipulation is well-balanced and that
>>> the shadow stack pointer isn't corrupted.
>>>
>>> Practically speaking, this requires decoding a significant number of
>>> instructions, and tracing through all potential paths a function may
>>> take.
>>
>> I thought about it some more since you don't like the shadow stack
>> that much.
> 
> Just to be clear, what I was trying to get across was:
> 
> * Whatever we do, we want to verify at compile time that the kernel
>   binary matches our expecations, and practically speaking this almost
>   certainly means using objtool.
> 
> * The analysis that objtool will have to do is not made significantly
>   simpler through the use of a shadow stack, as it still needs to track
>   all paths though a function, etc.
> 

Actually, traversing all the paths within a function is not the tough part, IMHO.
A subset of the instructions must be decoded. I think what is tough is decoding
every single instruction that can potentially use the stack and the frame pointer
registers, tracking the stack and frame state through all of that accurately and
finding violations - that is the real work.

I will study what Julien has implemented. If he has already done most of the work,
then this whole discussion is moot.

> I'm not averse to using a shadow stack (and clang's SCS is a useful
> security feature), I just don't think that it helps much with
> compile-time verification, and I don't see a strong reason to mandate it
> for livepatching.
> 

Actually, the security feature of shadow stacks is probably not useful for
the kernel. IIUC, the security feature is that the overwriting of the return
address through buffer overflow attacks can be avoided if there is a shadow
stack. That is not relevant to the kernel.

I still feel that making the prolog and epilog smarter can save a significant
amount of objtool work.

> [...]
> 
>> The goal is - even if a function modifies fp and/or does not restore sp to its
>> correct value at the end, the prolog and epilog should manage it so that everything
>> works. To do this, the current frame pointer address is stored in fp as well as cur_fp.
>> Even if fp is modified, cur_fp will still point to the correct frame address.
>>
>> Prolog
>> =======
>>
>> The original prolog is:
>>
>> - Push fp and return address on the stack
>> - fp = sp
>>
>>
>> The new prolog is:
>>
>> - Save cur_fp on the stack
>> - Push fp, return address on the stack
>> - fp = sp
>> - cur_fp = fp
>>
>> Epilog
>> ======
>>
>> The original epilog is:
>>
>> - Pop fp and return address
>>
>> The new epilog is:
>>
>> - sp = cur_fp
>> - Pop fp and return address
>> - Restore cur_fp from the stack
>>
>>
>> I think this is pretty simple.
> 
> I'm afraid I don't understand the problem you're trying to solve here.
> The epilog you propose is also unsound in the face of asynchronous
> exceptions, so I suspect you haven't thought as hard about this as you
> need to.
> 

Asynchronous exceptions are a problem even with the existing frame
pointer prolog and epilog. What is the extra problem that the new
prolog and epilog introduce? The only additional thing I am
introducing is the saving of the fp to a memory location and
restoring it. I am not sure I see how that can be a problem. But
if it is a problem, I would like to understand it. Can you elaborate?


> Even if the compiler uses a different prologue/epilogue sequence, we
> still need to verify that the rest of the function does nothing to
> undermine that.
> 

What can the function do to undermine that? The epilog already
handles the clobbering of the fp. It handles the case where a
function has pushed something on to the stack and has not
popped it.

The only other thing I can think of is a function clobbering the
cur_fp location itself. For that matter, a function can clobber
any location on the stack. Objtool will not be able to detect that.

But it is possible I have missed something. Can you elaborate?

> I think this is merely different rather than simpler, and regardless
> this would be an invasive change to compilers.
> 

It is a simpler change as compared to a shadow stack.

I believe all toolchain changes that have been done to specifically support
Linux kernel features have been invasive. Have they not?

>> Unwinder
>> ========
>>
>> The unwinder will start the stack walk from cur_fp instead of fp. At each frame,
>> it will use the saved cur_fp instead of the saved fp. 
>>
>> Also, at each step, it can know if fp was actually changed by the function in
>> the frame. The unwinder can optionally issue warnings.
> 
> So this is just about aditional robustness?
> 
> I'm happy to use a shadow stack for /additional/ robustness, I just
> don't think a shadow stack alone solves all the other issues that we
> need compile time verification for, nor does it solve cases where we
> might want metadata generated at compile time.
> 

I am only discussing reliable stack trace and objtool's part in it. I am cool
with all the other issues objtool tackles.

>> Compiler issue
>> ===============
>>
>> This solution is geared towards the kernel only. It assumes that the stack
>> has a fixed size and alignment so the bottom of the stack can be reached
>> from the current sp.
>>
>> So, the compiler has to support two prologs and epilogs, one pair for apps
>> and one pair for the kernel.
>>
>> Since this is just a tiny bit of code, I don't think this is a problem.
> 
> I suspect it's more compilated than that. Configuration differences like
> this can easily double the necessary testing, and are liable to becomer
> a maintenance burden, so I don't expect compiler folk are likely to want
> to support this unless necessary.
> 

I think this is pretty much true of any compiler change you request for the
Linux kernel.

> At the moment, I don't think that this solves a real problem, and I
> don't think that we need to change this.
> 

I do think it solves the problem of making the stack frame immune to
the function clobbering the frame pointer. That is totally relevant to
reliable stack trace.

Anyway, I think I will move on to other things (unless someone has an
interest this topic).

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Re: [RFC PATCH 0/3] arm64: Implement reliable stack trace

[Madhavan T. Venkataraman]

Hi Mark,

Could you please answer the two questions below? You are the expert.
Help me understand the exact problems. Even if the proposal is not
considered, I want to understand what is wrong with it.

On 2/3/21 1:03 PM, Madhavan T. Venkataraman wrote:
> 
> 
> On 2/3/21 10:53 AM, Mark Rutland wrote:

>> The epilog you propose is also unsound in the face of asynchronous
>> exceptions, so I suspect you haven't thought as hard about this as you
>> need to.
>>
> 

Can you elaborate? I understand that an exception can happen right in the
middle of the prolog or epilog. What extra problem is caused by the changed
prolog and epilog?

> 
> 
>> Even if the compiler uses a different prologue/epilogue sequence, we
>> still need to verify that the rest of the function does nothing to
>> undermine that.
>>

The epilog corrects the frame pointer even if it is modified by the
function. It also restores the stack pointer correctly even if the
function does not.

What else can go wrong?

Thanks in advance for the info.

Madhavan

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel