RFC: callee saved register verifier

Project Infrastructure LLVM Dev List Archives
1

Hi,

This is a proposal to introduce a mechanism to LLVM that uses runtime
instrumentation to verify that a call target preserves all of the
registers it says it does. Internally, we have a diverse set of
calling conventions for runtime functions that get called from LLVM
compiled code, and having some sort of validation mechanism will give
us more confidence in selecting aggressive calling conventions for
these.

The general idea is this: before every call store a cookie in all the
registers that the call is supposed to preserve, and after the call
returns, assert that the supposedly callee saved registers weren't
clobbered. So for a call target that respects the C calling
convention, we'll generate something like:

   movabsq $0xCA5FCA5FCA5FCA5F, %rbp
   movabsq $0xCA5FCA5FCA5FCA5F, %rbx # can also be movq %rbp, %rbx etc.
   movabsq $0xCA5FCA5FCA5FCA5F, %r12
   movabsq $0xCA5FCA5FCA5FCA5F, %r13
   movabsq $0xCA5FCA5FCA5FCA5F, %r14
   movabsq $0xCA5FCA5FCA5FCA5F, %r15
   callq foo
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq %rax, %rbp
   jne .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq %rax, %rbx
   jne .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq %rax, %r12
   jne .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq %rax, %r13
   jne .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq %rax, %r14
   jne .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq %rax, %r15
   jne .LBB1_5

The 0xCA5FCA5FCA5FCA5F cookie was selected arbitrarily, but in general
it can be anything that the call target is unlikely to clobber a CSR
with (so it shouldn't be 0, 1, -1 etc.).

This isn't intended to be fast, but is something you turn on in a slow
"validate corner cases" mode. I think for this to be practical we'll
need to be able to switch this on and off per calling convention,
since I suspect doing this for every call will be impractically slow,
even for a validation run.

Does the general idea sound reasonable?

Note: the focus here is **not** verifying the register allocator or
any other part of _LLVM_, but to verify that e.g. a custom calling
convention that says that a call target preserves %r10 actually does
preserve %r10. This is the compiler enforcing a contract, just at a
very low level.

Implementation wise, I have a rough prototype that works by running a
MachineFunctionPass before register allocation that emits the
necessary MachineInstrs / control flow to make this happen. Is that a
right way to solve the problem? If so, I'll clean up what I have and
put it up for review on llvm-commits. If there are better ways to do
this, then I'm happy to hear them.

-- Sanjoy

2

Hi Sanjay,

Hi,

This is a proposal to introduce a mechanism to LLVM that uses runtime
instrumentation to verify that a call target preserves all of the
registers it says it does. Internally, we have a diverse set of
calling conventions for runtime functions that get called from LLVM
compiled code, and having some sort of validation mechanism will give
us more confidence in selecting aggressive calling conventions for
these.

The general idea is this: before every call store a cookie in all the
registers that the call is supposed to preserve, and after the call
returns, assert that the supposedly callee saved registers weren't
clobbered. So for a call target that respects the C calling
convention, we'll generate something like:

movabsq $0xCA5FCA5FCA5FCA5F, %rbp
movabsq $0xCA5FCA5FCA5FCA5F, %rbx # can also be movq %rbp, %rbx etc.
movabsq $0xCA5FCA5FCA5FCA5F, %r12
movabsq $0xCA5FCA5FCA5FCA5F, %r13
movabsq $0xCA5FCA5FCA5FCA5F, %r14
movabsq $0xCA5FCA5FCA5FCA5F, %r15
callq foo
movabsq $0xCA5FCA5FCA5FCA5F, %rax
cmpq %rax, %rbp
jne .LBB1_5
movabsq $0xCA5FCA5FCA5FCA5F, %rax
cmpq %rax, %rbx
jne .LBB1_5
movabsq $0xCA5FCA5FCA5FCA5F, %rax
cmpq %rax, %r12
jne .LBB1_5
movabsq $0xCA5FCA5FCA5FCA5F, %rax
cmpq %rax, %r13
jne .LBB1_5
movabsq $0xCA5FCA5FCA5FCA5F, %rax
cmpq %rax, %r14
jne .LBB1_5
movabsq $0xCA5FCA5FCA5FCA5F, %rax
cmpq %rax, %r15
jne .LBB1_5

The 0xCA5FCA5FCA5FCA5F cookie was selected arbitrarily, but in general
it can be anything that the call target is unlikely to clobber a CSR
with (so it shouldn't be 0, 1, -1 etc.).

This isn't intended to be fast, but is something you turn on in a slow
"validate corner cases" mode. I think for this to be practical we'll
need to be able to switch this on and off per calling convention,
since I suspect doing this for every call will be impractically slow,
even for a validation run.

Does the general idea sound reasonable?

The solution definitely solves your problems, I just wonder in what “corner case” mode this even makes sense.

Note: the focus here is **not** verifying the register allocator or
any other part of _LLVM_, but to verify that e.g. a custom calling
convention that says that a call target preserves %r10 actually does
preserve %r10. This is the compiler enforcing a contract, just at a
very low level.

You mean with code generated by another compiler/handwritten, because otherwise, this is pretty easy to verify in the machine verifier :).
(We probably do not verify that though, but we should.)
Thus, could you elaborate on the use cases.

Implementation wise, I have a rough prototype that works by running a
MachineFunctionPass before register allocation that emits the
necessary MachineInstrs / control flow to make this happen. Is that a
right way to solve the problem?

I’d say yes, assuming the use cases do not involve llvm, otherwise the verifier approach seems preferable to me.

If so, I'll clean up what I have and
put it up for review on llvm-commits. If there are better ways to do
this, then I'm happy to hear them.

-- Sanjoy

Cheers,
-Quentin

3

Hi Sanjay,

>
> Hi,
>
> This is a proposal to introduce a mechanism to LLVM that uses runtime
> instrumentation to verify that a call target preserves all of the
> registers it says it does. Internally, we have a diverse set of
> calling conventions for runtime functions that get called from LLVM
> compiled code, and having some sort of validation mechanism will give
> us more confidence in selecting aggressive calling conventions for
> these.
>
> The general idea is this: before every call store a cookie in all the
> registers that the call is supposed to preserve, and after the call
> returns, assert that the supposedly callee saved registers weren't
> clobbered. So for a call target that respects the C calling
> convention, we'll generate something like:
>
> movabsq $0xCA5FCA5FCA5FCA5F, %rbp
> movabsq $0xCA5FCA5FCA5FCA5F, %rbx # can also be movq %rbp, %rbx etc.
> movabsq $0xCA5FCA5FCA5FCA5F, %r12
> movabsq $0xCA5FCA5FCA5FCA5F, %r13
> movabsq $0xCA5FCA5FCA5FCA5F, %r14
> movabsq $0xCA5FCA5FCA5FCA5F, %r15
> callq foo
> movabsq $0xCA5FCA5FCA5FCA5F, %rax
> cmpq %rax, %rbp
> jne .LBB1_5
> movabsq $0xCA5FCA5FCA5FCA5F, %rax
> cmpq %rax, %rbx
> jne .LBB1_5
> movabsq $0xCA5FCA5FCA5FCA5F, %rax
> cmpq %rax, %r12
> jne .LBB1_5
> movabsq $0xCA5FCA5FCA5FCA5F, %rax
> cmpq %rax, %r13
> jne .LBB1_5
> movabsq $0xCA5FCA5FCA5FCA5F, %rax
> cmpq %rax, %r14
> jne .LBB1_5
> movabsq $0xCA5FCA5FCA5FCA5F, %rax
> cmpq %rax, %r15
> jne .LBB1_5
>
>
> The 0xCA5FCA5FCA5FCA5F cookie was selected arbitrarily, but in general
> it can be anything that the call target is unlikely to clobber a CSR
> with (so it shouldn't be 0, 1, -1 etc.).
>
> This isn't intended to be fast, but is something you turn on in a slow
> "validate corner cases" mode. I think for this to be practical we'll
> need to be able to switch this on and off per calling convention,
> since I suspect doing this for every call will be impractically slow,
> even for a validation run.
>
> Does the general idea sound reasonable?

The solution definitely solves your problems, I just wonder in what
“corner case” mode this even makes sense.

Yeah, that's sort of what I'd be wondering too.

It seems like if the compiler does the right thing for existing calling
conventions - I hope our architecture is such that changing the set of
callee save registers reflects on both sides (both the caller - relying on
them to be saved, and the caller implementing that guarantee). So I
wouldn't expect making weird/random calling conventions to be likely to
have any new/interesting bugs here.

But perhaps the architecture doesn't & can't work that way?

4

Hi Quentin,

Thanks for the quick response!

Quentin Colombet wrote:
>
> You mean with code generated by another compiler/handwritten,
> because otherwise, this is pretty easy to verify in the machine
> verifier :).
>
> (We probably do not verify that though, but we should.)
> Thus, could you elaborate on the use cases.

The runtime functions in question are usually hand-written assembly,
or generated from another ("tier-1") JIT.

I expect this to be more useful when calling into hand-written
assembly routines than when calling into other-compiler-generated
code, since hand-written assembly tends to be more prone to the kind
of mistakes I'm verifying against (accidentally clobbering a CSR on a
rarely taken path).

So far we've not seen any bugs around _LLVM_ failing to obey a calling
convention, so (as yet! :slight_smile: ) I'm not too worried around LLVM
miscompiling due to some exotic calling convention.

Thanks!
-- Sanjoy

>
>>
>> Implementation wise, I have a rough prototype that works by running a
>> MachineFunctionPass before register allocation that emits the
>> necessary MachineInstrs / control flow to make this happen. Is that a
>> right way to solve the problem?
>
> I’d say yes, assuming the use cases do not involve llvm, otherwise the verifier approach seems preferable to me.

5

More importantly, the runtime needs to have a mode that forcibly clobbers all caller-save registers, which I’m sure you’re already doing.

You could do this after regalloc and verify only the callee-save registers that are not already live to avoid slowdowns due to spilling. Your approach sounds like it would work ok in practice though.

Andy

6

Hi David,

David Blaikie wrote:
> Yeah, that's sort of what I'd be wondering too.
>
> It seems like if the compiler does the right thing for existing calling
> conventions - I hope our architecture is such that changing the set of
> callee save registers reflects on both sides (both the caller - relying
> on them to be saved, and the caller implementing that guarantee). So I
> wouldn't expect making weird/random calling conventions to be likely to
> have any new/interesting bugs here.

Yes, so far we've not had any issues with LLVM upholding its side of
the deal when it comes to calling conventions. Humans tend to be
more prone to making mistakes, unfortunately. :slight_smile:

>
> But perhaps the architecture doesn't & can't work that way?

The intention is to add verification at call-sites that call into a
hand-written stub from LLVM generated code.

-- Sanjoy

7

I’ve seen this done in the past without compiler support (for the case of handwritten or JIT’d, etc functions that need checking).

It worked something like this:

1. Pass calls to the risky functions through a macro/template or such.
2. In release mode, this turns into a no-op. In debug mode, this sends the calls through a handwritten asm wrapper that sets all the callee-save registers to random values, then calls the function.
3. When the function returns, the wrapper checks the registers are the same, and if they’re not, bails to exit() and prints the invalid registers.

This took a few dozen lines of code and worked entirely within the language, so it didn’t need compiler support.

—escha

8

Hi Escha,

escha@apple.com wrote:

I’ve seen this done in the past without compiler support (for the case of handwritten or JIT’d, etc functions that need checking).

It worked something like this:

1. Pass calls to the risky functions through a macro/template or such.
2. In release mode, this turns into a no-op. In debug mode, this sends the calls through a handwritten asm wrapper that sets all the callee-save registers to random values, then calls the function.
3. When the function returns, the wrapper checks the registers are the same, and if they’re not, bails to exit() and prints the invalid registers.

This took a few dozen lines of code and worked entirely within the language, so it didn’t need compiler support.

That's certainly a design point, but assert in the compiler has some
advantages:

  - It is more scalable -- I don't have to add the verification code
    for each new calling convention. To have LLVM take advantage of a
    new calling convention, we have to codify knowledge of the calling
    convention in LLVM anyway, and it is better to re-use the
    information as much as possible.

  - Since the scheme works directly off of the calling convention as
    encoded in LLVM, it will catch bugs in the specification on the
    LLVM side (e.g. marking a function declaration with an incorrect
    calling convention should fail noisily).

The overarching point is that I'd rather have a single source of truth
(the calling convention as specified in LLVM) and assert on that.

-- Sanjoy

9

This is up for review at http://reviews.llvm.org/D21115