Re: [RFC PATCH 00/17] objtool: add base support for arm64

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Josh Poimboeuf]

Ard,

Sorry, I was late to the party, attempting to reply to the entire thread
at once.  Also, adding the live-patching ML.

I agree with a lot of your concerns.  Reverse engineering the control
flow of the compiled binary is kind of ridiculous.  I was always
surprised that it works.  I still am!  But I think it's more robust than
you give it credit for.

Most of the existing code just works, with (annual) tweaks for new
compiler versions.  In fact now it works well with both GCC and Clang,
across several versions.  Soon it will work with LTO.

It has grown many uses beyond stack validation: ORC, static calls,
retpolines validation, noinstr validation, SMAP validation.  It has
found a *lot* of compiler bugs.  And there will probably be more use
cases when we get vmlinux validation running fast enough.

But there is indeed a maintenance burden.  I often ask myself if it's
worth it.  So far the answer has been yes :-)  Particularly because it
has influenced many positive changes to the kernel.  And it helps now
that even more people are contributing and adding useful features.

But you should definitely think twice before letting it loose on your
arch, especially if you have some other way to ensure reliable stack
metadata, and if you don't have a need for the other objtool features.


Regarding your other proposals:

1) I'm doubtful we can ever rely on the toolchain to ensure reliable
   unwind metadata, because:

   a) most of the problems are in asm and inline-asm; good luck getting
      the toolchain to care about those.

   b) the toolchain is fragile; do we want to entrust the integrity of
      live patching to the compiler's frame pointer generation (or other
      unwind metadata) without having some sort of checking mechanism?


2) The shadow stack idea sounds promising -- how hard would it be to
   make a prototype reliable unwinder?


More comments below:


On Thu, Jan 21, 2021 at 12:48:43PM +0100, Ard Biesheuvel wrote:
> On Thu, 21 Jan 2021 at 12:23, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > On Thu, Jan 21, 2021 at 12:08:23PM +0100, Ard Biesheuvel wrote:
> > > On Thu, 21 Jan 2021 at 11:26, Julien Thierry <jthierry@redhat.com> wrote:
> >
> > > > I'm not familiar with toolcahin code models, but would this approach be
> > > > able to validate assembly code (either inline or in assembly files?)
> > > >
> > >
> > > No, it would not. But those files are part of the code base, and can
> > > be reviewed and audited.
> >
> > x86 has a long history if failing at exactly that.
> 
> That's a fair point. But on the flip side, maintaining objtool does
> not look like it has been a walk in the park either.

I think you missed Peter's point: it's not that it's *hard* for humans
to continuously review/audit all asm and inline-asm; it's just not
feasible to do it 100% correctly, 100% of the time.

Like any other code, objtool requires maintenance, but its analysis is
orders of magnitude more robust than any human.

> What i am especially concerned about is things like 3193c0836f20,
> where we actually have to disable certain compiler optimizations
> because they interfere with objtool's ability to understand the
> resulting object code. Correctness and performance are challenging
> enough as requirements for generated code.

Well, you managed to find the worst case scenario.  I think that's the
only time we ever had to do that.  Please don't think that's normal, or
even a generally realistic concern.  Objtool tries really hard to stay
out of the way.

Long term we really want to prevent that type of thing with the help of
annotations from compiler plugins, similar to what Julien did here.

Yes, it would mean two objtool compiler plugins (GCC and Clang), but it
would ease the objtool maintenance burden and risk in many ways.  And
prevent situations like that commit you found.  It may sound fragile,
but it will actually make things simpler overall: less reverse
engineering of GCC switch jump tables and __noreturn functions is a good
thing.

> Mind you, I am not saying it is not worth it *for x86*, where there is
> a lot of other stuff going on. But on arm64, we don't care about ORC,
> about -fomit-frame-pointer, about retpolines or about any of the other
> things objtool enables.
> 
> On arm64, all it currently seems to provide is a way to capture the
> call stack accurately, and given that it needs a GCC plugin for this
> (which needs to be maintained as well, which is non-trivial, and also
> bars us from using objtool with Clang builds), my current position is
> simply that opening this can of worms at this point is just not worth
> it.

As far as GCC plugins go, it looks pretty basic to me.  Also this
doesn't *at all* prevent Clang from being used for live patching.  If
anybody actually tries running Julien's patches on a Clang-built kernel,
it might just work.  But if not, and the switch tables turn out to be
unparseable like on GCC, we could have a Clang plugin.  As I mentioned,
we'll probably end up having one anyway for x86.

-- 
Josh

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Mark Brown]

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

On Thu, Jan 21, 2021 at 12:54:52PM -0600, Josh Poimboeuf wrote:

> 2) The shadow stack idea sounds promising -- how hard would it be to
>    make a prototype reliable unwinder?

In theory it doesn't look too hard and I can't see a particular reason
not to try doing this - there's going to be edge cases but hopefully for
reliable stack trace they're all in areas where we would be happy to
just decide the stack isn't reliable anyway, things like nesting which
allocates separate shadow stacks for each nested level for example.
I'll take a look.

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

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Ard Biesheuvel]

On Fri, 22 Jan 2021 at 18:44, Mark Brown <broonie@kernel.org> wrote:
>
> On Thu, Jan 21, 2021 at 12:54:52PM -0600, Josh Poimboeuf wrote:
>
> > 2) The shadow stack idea sounds promising -- how hard would it be to
> >    make a prototype reliable unwinder?
>
> In theory it doesn't look too hard and I can't see a particular reason
> not to try doing this - there's going to be edge cases but hopefully for
> reliable stack trace they're all in areas where we would be happy to
> just decide the stack isn't reliable anyway, things like nesting which
> allocates separate shadow stacks for each nested level for example.
> I'll take a look.

This reminds me - a while ago, I had a stab at writing a rudimentary
GCC plugin that pushes/pops return addresses to a shadow call stack
pointed to by x18 [0]
I am by no means suggesting that we should rely on a GCC plugin for
this, only that it does seem rather straight-forward for the compiler
to manage a stack with return addresses like that (although the devil
is probably in the details, as usual)

[0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=arm64-scs-gcc

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Madhavan T. Venkataraman]

Hi,

I sent this suggestion to linux-arm-kernel in response to the Reliable Stacktrace RFC from Mark Brown
and Mark Rutland. I am repeating it here for two reasons:

- It involves objtool.

- There are many more recipients in this thread that may be interested in this topic.

Please let me know if this suggestion is acceptable. If it is not, please let me know why.
Thanks.

Also, I apologize to all of you who have received this more than once.

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

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Madhavan T. Venkataraman]

On 1/22/21 11:43 AM, Mark Brown wrote:
> On Thu, Jan 21, 2021 at 12:54:52PM -0600, Josh Poimboeuf wrote:
> 
>> 2) The shadow stack idea sounds promising -- how hard would it be to
>>    make a prototype reliable unwinder?
> 
> In theory it doesn't look too hard and I can't see a particular reason
> not to try doing this - there's going to be edge cases but hopefully for
> reliable stack trace they're all in areas where we would be happy to
> just decide the stack isn't reliable anyway, things like nesting which
> allocates separate shadow stacks for each nested level for example.
> I'll take a look.
> 

I am a new comer to this discussion and I am learning. Just have some
questions. Pardon me if they are obvious or if they have already been
asked and answered.

Doesn't Clang already have support for a shadow stack implementation for ARM64?
We could take a look at how Clang does it.

Will there not be a significant performance hit? May be, some of it can be
mitigated by using a parallel shadow stack rather than a compact one.

Are there any longjmp style situations in the kernel where the stack is
unwound by several frames? In these cases, the shadow stack must be unwound
accordingly.

Madhavan

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

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Ard Biesheuvel]

On Fri, 22 Jan 2021 at 22:15, Madhavan T. Venkataraman
<madvenka@linux.microsoft.com> wrote:
>
>
>
> On 1/22/21 11:43 AM, Mark Brown wrote:
> > On Thu, Jan 21, 2021 at 12:54:52PM -0600, Josh Poimboeuf wrote:
> >
> >> 2) The shadow stack idea sounds promising -- how hard would it be to
> >>    make a prototype reliable unwinder?
> >
> > In theory it doesn't look too hard and I can't see a particular reason
> > not to try doing this - there's going to be edge cases but hopefully for
> > reliable stack trace they're all in areas where we would be happy to
> > just decide the stack isn't reliable anyway, things like nesting which
> > allocates separate shadow stacks for each nested level for example.
> > I'll take a look.
> >
>
> I am a new comer to this discussion and I am learning. Just have some
> questions. Pardon me if they are obvious or if they have already been
> asked and answered.
>
> Doesn't Clang already have support for a shadow stack implementation for ARM64?
> We could take a look at how Clang does it.
>
> Will there not be a significant performance hit? May be, some of it can be
> mitigated by using a parallel shadow stack rather than a compact one.
>
> Are there any longjmp style situations in the kernel where the stack is
> unwound by several frames? In these cases, the shadow stack must be unwound
> accordingly.
>

Hello Madhavan,

Let's discuss the details of shadow call stacks on a separate thread,
instead of further hijacking Julien's series.

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Madhavan T. Venkataraman]

On 1/22/21 3:43 PM, Ard Biesheuvel wrote:
> On Fri, 22 Jan 2021 at 22:15, Madhavan T. Venkataraman
> <madvenka@linux.microsoft.com> wrote:
>>
>>
>>
>> On 1/22/21 11:43 AM, Mark Brown wrote:
>>> On Thu, Jan 21, 2021 at 12:54:52PM -0600, Josh Poimboeuf wrote:
>>>
>>>> 2) The shadow stack idea sounds promising -- how hard would it be to
>>>>    make a prototype reliable unwinder?
>>>
>>> In theory it doesn't look too hard and I can't see a particular reason
>>> not to try doing this - there's going to be edge cases but hopefully for
>>> reliable stack trace they're all in areas where we would be happy to
>>> just decide the stack isn't reliable anyway, things like nesting which
>>> allocates separate shadow stacks for each nested level for example.
>>> I'll take a look.
>>>
>>
>> I am a new comer to this discussion and I am learning. Just have some
>> questions. Pardon me if they are obvious or if they have already been
>> asked and answered.
>>
>> Doesn't Clang already have support for a shadow stack implementation for ARM64?
>> We could take a look at how Clang does it.
>>
>> Will there not be a significant performance hit? May be, some of it can be
>> mitigated by using a parallel shadow stack rather than a compact one.
>>
>> Are there any longjmp style situations in the kernel where the stack is
>> unwound by several frames? In these cases, the shadow stack must be unwound
>> accordingly.
>>
> 
> Hello Madhavan,
> 
> Let's discuss the details of shadow call stacks on a separate thread,
> instead of further hijacking Julien's series.
> 

OK. Sounds good.

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Josh Poimboeuf]

On Fri, Jan 22, 2021 at 10:43:09PM +0100, Ard Biesheuvel wrote:
> On Fri, 22 Jan 2021 at 22:15, Madhavan T. Venkataraman <madvenka@linux.microsoft.com> wrote:
> > On 1/22/21 11:43 AM, Mark Brown wrote:
> > > On Thu, Jan 21, 2021 at 12:54:52PM -0600, Josh Poimboeuf wrote:
> > >
> > >> 2) The shadow stack idea sounds promising -- how hard would it be to
> > >>    make a prototype reliable unwinder?
> > >
> > > In theory it doesn't look too hard and I can't see a particular reason
> > > not to try doing this - there's going to be edge cases but hopefully for
> > > reliable stack trace they're all in areas where we would be happy to
> > > just decide the stack isn't reliable anyway, things like nesting which
> > > allocates separate shadow stacks for each nested level for example.
> > > I'll take a look.
> > >
> >
> > I am a new comer to this discussion and I am learning. Just have some
> > questions. Pardon me if they are obvious or if they have already been
> > asked and answered.
> >
> > Doesn't Clang already have support for a shadow stack implementation for ARM64?
> > We could take a look at how Clang does it.
> >
> > Will there not be a significant performance hit? May be, some of it can be
> > mitigated by using a parallel shadow stack rather than a compact one.
> >
> > Are there any longjmp style situations in the kernel where the stack is
> > unwound by several frames? In these cases, the shadow stack must be unwound
> > accordingly.
> >
> 
> Hello Madhavan,
> 
> Let's discuss the details of shadow call stacks on a separate thread,
> instead of further hijacking Julien's series.

It's quite relevant to this thread.  There's no need to consider merging
Julien's patches if you have a better approach.  Why not discuss it
here?  I'm also interested in the answers to Madhavan's questions.

-- 
Josh

Re: [RFC PATCH 00/17] objtool: add base support for arm64

[Madhavan T. Venkataraman]

On 1/22/21 11:43 AM, Mark Brown wrote:
> On Thu, Jan 21, 2021 at 12:54:52PM -0600, Josh Poimboeuf wrote:
> 
>> 2) The shadow stack idea sounds promising -- how hard would it be to
>>    make a prototype reliable unwinder?
> 
> In theory it doesn't look too hard and I can't see a particular reason
> not to try doing this - there's going to be edge cases but hopefully for
> reliable stack trace they're all in areas where we would be happy to
> just decide the stack isn't reliable anyway, things like nesting which
> allocates separate shadow stacks for each nested level for example.
> I'll take a look.
> 

I am a new comer to this discussion and I am learning. Just have some
questions. Pardon me if they are obvious or if they have already been
asked and answered.

Doesn't Clang already have support for a shadow stack implementation for ARM64?
We could take a look at how Clang does it.

Will there not be a significant performance hit? May be, some of it can be
mitigated by using a parallel shadow stack rather than a compact one.

Are there any longjmp style situations in the kernel where the stack is
unwound by several frames? In these cases, the shadow stack must be unwound
accordingly.

Madhavan

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