arm64: Implement reliable stack trace

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 <[email protected]>

---
 arch/arm64/kernel/stacktrace.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

arch/arm64/kernel/stacktrace.c +1 -1

index 0fb42129b469..ad20981dfda4 100644
@@ -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;

Signature · 1 line

2.20.1

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 <[email protected]>

---
 arch/arm64/Kconfig             |  1 +
 arch/arm64/kernel/stacktrace.c | 42 ++++++++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+)

arch/arm64/Kconfig +1 -0

index d1ba52e4b976..026f69515a86 100644
@@ -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

arch/arm64/kernel/stacktrace.c +1 -0

index ad20981dfda4..795b2c14481d 100644
@@ -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>

arch/arm64/kernel/stacktrace.c +11 -0

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

Signature · 1 line

2.20.1

Quoted 6 lines · Mark Brown

+/*
+ * 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".

Quoted 8 lines

arch/arm64/kernel/stacktrace.c +8 -0

+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),

arch/arm64/kernel/stacktrace.c void arch_stack_walk(stack_trace_consume_fn consume_entry, void *cookie, · line 234

Quoted 5 lines

arch/arm64/kernel/stacktrace.c +5 -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.

arch/arm64/kernel/stacktrace.c +14 -0

+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) {

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

Quoted 2 lines · Miroslav Benes

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?

Quoted 7 lines · Mark Brown

Quoted 2 lines · Miroslav Benes

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.

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

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.

Hi,

Quoted 7 lines

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.

Quoted 5 lines

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
"

Quoted 4 lines · Miroslav Benes

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).

Quoted 10 lines

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.

Quoted 16 lines · Mark Rutland

Quoted 14 lines · Miroslav Benes

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
"

Quoted 3 lines

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.

Quoted 4 lines

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.

Quoted 4 lines

Quoted 4 lines

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.

Quoted 10 lines · Mark Rutland

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.

Quoted 3 lines

... 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.

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.

[email protected] would also be a good idea for this one.

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

Quoted 2 lines

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.

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.

Quoted 17 lines

Quoted 2 lines

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).

Quoted 1 line

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.

Quoted 5 lines · Mark Brown

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.

Quoted 7 lines · Josh Poimboeuf

Quoted 5 lines · Mark Brown

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.

Quoted 3 lines

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?

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(-)

Quoted 21 lines · 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

Quoted 8 lines

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?

Quoted 2 lines · Madhavan T. Venkataraman

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.

Quoted 2 lines

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.

Quoted 21 lines · 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

Quoted 8 lines

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?

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

Quoted 13 lines · Madhavan T. Venkataraman

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

Quoted 8 lines

- 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?

Quoted 5 lines

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.

Quoted 8 lines

- 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?

Quoted 8 lines

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?

Quoted 6 lines

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.

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.

- 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.

Quoted 2 lines · Josh Poimboeuf

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.

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.

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.

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

Quoted 12 lines

Quoted 12 lines

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

Quoted 5 lines

Quoted 5 lines

- 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?

Quoted 11 lines

Quoted 10 lines

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.

Quoted 7 lines

Quoted 3 lines

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?

Quoted 8 lines

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.

Quoted 13 lines · Josh Poimboeuf

Quoted 8 lines

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).

Quoted 8 lines

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
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Quoted 16 lines · Josh Poimboeuf

Quoted 8 lines

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:

Quoted 5 lines

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.

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;

Quoted 1 line · Madhavan T. Venkataraman

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.

Quoted 9 lines · Mark Rutland

Quoted 1 line · Madhavan T. Venkataraman

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.

Hi Madhavan,

Quoted 23 lines · Madhavan T. Venkataraman

Quoted 21 lines · Josh Poimboeuf

Quoted 8 lines

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.

Quoted 1 line

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).

Quoted 6 lines

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.

Quoted 2 lines

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.

Quoted 8 lines

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.

Quoted 3 lines

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.

Quoted 2 lines

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.

Quoted 16 lines

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

Quoted 6 lines

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.

[...]

Quoted 13 lines

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;

Quoted 2 lines

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.

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.

Quoted 3 lines

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.

Quoted 7 lines

Quoted 3 lines

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?

Quoted 4 lines

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.

Quoted 4 lines · Madhavan T. Venkataraman

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.

Quoted 11 lines

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.

Quoted 7 lines

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.

Quoted 4 lines

Quoted 3 lines

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

Quoted 9 lines

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.

Quoted 2 lines

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.

Quoted 8 lines

Quoted 7 lines

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 5 lines

Quoted 4 lines

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.

Quoted 5 lines

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.

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

Quoted 4 lines

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

Quoted 9 lines

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?

Quoted 30 lines · Mark Rutland

Quoted 11 lines · Madhavan T. Venkataraman

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

Quoted 6 lines

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

Quoted 1 line

... 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.

Quoted 19 lines

[...]

Quoted 15 lines

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;

Quoted 4 lines

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.

Quoted 7 lines

Quoted 4 lines

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.

Quoted 2 lines

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).

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.

Quoted 5 lines · Mark Rutland

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.

Quoted 3 lines

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.

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.

Quoted 6 lines · Madhavan T. Venkataraman

Quoted 5 lines · Mark Rutland

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.

Quoted 6 lines

Quoted 3 lines

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.

[...]

Quoted 35 lines

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

Quoted 1 line

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.

Quoted 8 lines

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.

Quoted 10 lines

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.

Quoted 1 line

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.

Quoted 4 lines · Mark Rutland

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.

Quoted 6 lines

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.

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.

Quoted 2 lines

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

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

Quoted 6 lines

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.

Quoted 1 line

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.

Quoted 20 lines

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.

Quoted 1 line

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.

Quoted 7 lines

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.

Quoted 5 lines

- 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?

Quoted 8 lines

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?

Quoted 6 lines

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?