mpe's tech blog

Kernel Live Patching for ppc64le

As part of the 4.6 and 4.7 development cycles, several of us from IBM & SUSE finally got all the pieces lined up to enable kernel live patching for ppc64le.

If you're not familiar with kernel live patching, there's a pretty good write-up at Wikipedia. But the basic idea is that you can, without rebooting, replace one function in the kernel with a new version of that function (or something else entirely). Typically you do this because there is a bug in the original version of the function, and this allows you to fix or mitigate that bug.

If you think that sounds like it could be tricky, then you're right.

FTRACE_WITH_REGS

Live patching is implemented on top of ftrace, which is Linux's mechanism for attaching trace functions to other functions. Although powerpc has had ftrace support for ~8 years, we didn't have support for a particular feature of ftrace, called FTRACE_WITH_REGS.

So the first step on the way to live patching support was to implement support for FTRACE_WITH_REGS.

The way ftrace is implemented is that we build the kernel with some special GCC flags. These tell GCC to generate calls to a special function, _mcount, at the beginning of every function. Typically these calls are nop'ed out, but when ftrace is enabled those call sites are patched to call into ftrace and do something interesting.

In order to support FTRACE_WITH_REGS we first needed to tell GCC to use a different calling sequence for the _mcount calls. This is called -mprofile-kernel, and was the brainchild of Anton Blanchard & Alan Modra.

Using -mprofile-kernel tells GCC to use a very minimal calling sequence when calling _mcount. This has two advantages, firstly it imposes very little overhead when the _mcount calls are nop'ed out, and secondly it means the register state is not perturbed before calling ftrace - which is exactly what we need for FTRACE_WITH_REGS.

This is an example of the code generated for a call to _mcount using the standard mcount ABI, as you can see it involves an mflr, several stores and the creation of a stack frame (stdu):

c00000000000b560 <match_dev_by_uuid>:
c00000000000b560:       ed 00 4c 3c     addis   r2,r12,237
c00000000000b564:       a0 d6 42 38     addi    r2,r2,-10592
c00000000000b568:       a6 02 08 7c     mflr    r0
c00000000000b56c:       f0 ff c1 fb     std     r30,-16(r1)
c00000000000b570:       f8 ff e1 fb     std     r31,-8(r1)
c00000000000b574:       10 00 01 f8     std     r0,16(r1)
c00000000000b578:       d1 ff 21 f8     stdu    r1,-48(r1)
c00000000000b57c:       78 1b 7e 7c     mr      r30,r3
c00000000000b580:       78 23 9f 7c     mr      r31,r4
c00000000000b584:       d9 e7 ff 4b     bl      c000000000009d5c <_mcount>
c00000000000b588:       00 00 00 60     nop

Example calling sequence with -mprofile-kernel, the sequence is reduced to just the mflr, std and bl:

c00000000000b710 <match_dev_by_uuid>:
c00000000000b710:    ea 00 4c 3c     addis   r2,r12,234
c00000000000b714:    f0 d4 42 38     addi    r2,r2,-11024
c00000000000b718:    a6 02 08 7c     mflr    r0
c00000000000b71c:    10 00 01 f8     std     r0,16(r1)
c00000000000b720:    3d e6 ff 4b     bl      c000000000009d5c <_mcount>

In addition to telling GCC to use -mprofile-kernel we also needed a new implementation of ftrace_caller(), which is the function called in place of _mcount when ftrace is enabled. Due to the way it's called, ie. during the prolog of another function, ftrace_caller() has to be carefully hand written in assembler.

To keep things interesting we also had to deal with the fact that old toolchains don't implement -mprofile-kernel correctly, although they do accept the flag. Furthermore there is both a 4 instruction sequence, or in newer toolchains an optimised 3 instruction sequence.

This work was done largely by Torsten Duwe of SUSE, with some initial work by Vojtech Pavlik, and some assistance from me on the module code.

Understanding the TOC & entry points

The TOC or "Table Of Contents", is an area in memory where a program's global data is placed. When code references a global variable, the compiler generates instructions to load that variable from the TOC relative to the TOC pointer, which is expected to be in r2.

On ppc64le, functions typically have two entry points. The first, called the "global entry point", is found at the start of the function's text, and will setup the TOC pointer based on the location of the function, which must be passed in r12. It is the responsibility of the caller to have saved its TOC value somewhere prior to the call.

The second entry point, called the "local entry point", skips over the first two instructions which do the TOC pointer setup, ie. it's at +8 from the start of the function text. In this case the caller needn't save its TOC, because it knows it will not be modified.

An example function, with both global and local entry points:

c000000000d1467c <exit_dns_resolver>:
c000000000d1467c:    19 00 4c 3c     addis   r2,r12,25
c000000000d14680:    84 45 42 38     addi    r2,r2,17796
c000000000d14684:    a6 02 08 7c     mflr    r0

On entry to the global entry point r12 must hold the address of the function, ie. c000000000d1467c. Given that, we can calculate that r2 will have the value c000000000d1467c + 1638400 + 17796 = c000000000ea8c00.

If we enter at the local entry point c000000000d14684, then r2 must already hold the value c000000000ea8c00. This then allows code inside the function to use c000000000ea8c00 as the base address of any loads or stores to or from global variables.

The determination about which entry point to use is made at link time. If the linker can determine that the caller and callee share the same TOC, aka. the function call is "local", then it will generate a call to the local entry point. Calls via a function pointer always use the global entry point.

The last thing we need to know about the TOC pointer is that the instructions to setup the TOC pointer can be omitted entirely, if the function accesses no globals at all, eg:

c00000000065c8e0 <int_to_scsilun>:
c00000000065c8e0:    a6 02 08 7c     mflr    r0
c00000000065c8e4:    10 00 01 f8     std     r0,16(r1)
c00000000065c8e8:    75 d4 9a 4b     bl      c000000000009d5c <_mcount>
c00000000065c8ec:    a6 02 08 7c     mflr    r0

Live patch calling sequence

When you "apply" a live patch, what you're actually doing is loading a module with a new function in it, and diverting calls from the old version of the function to the new version.

To try and get a handle on things, let's give these functions names. We'll call the caller A, this is code somewhere in the kernel or a module which wants to call a function B. But we are live patching B with a new function P (the "patch"). In order to get from B to P we go via the ftrace code, which we'll call F. On the return path we come from P back to F and then to A. eg:

 +---------+           +---------+           +---------+           +---------+
 |         |     +-----+---------+---------->|         |     +---->|         |
 |  A      |     |     |  B      |           |  F      |     |     |  P      |
 |         |     |     |         |           |         +-----+     |         |
 |         +-----+     |         |           |         |<----+     |         |
 |         |<----+     |         |           |         |     |     |         |
 |         |     |     |         |           |         |     |     |         |
 | K / M1  |     |     | K / M2  |     +-----+ Kernel  |     +-----+ Mod3    |
 +---------+     |     +---------+     |     +---------+           +---------+
                 |                     |
                 +---------------------+

The arrow that passes straight through B is meant to indicate that we don't really execute any of the body code in B. However we do execute the prolog and the _mcount calling sequence.

The K / M1 annotation is meant to show that A may be either built-in to the kernel, or a module M1. Similarly B may be either built-in to the kernel, or a module M2, and M1 may or may not equal M2. F is always built-in to the kernel, and P is typically in a new module M3.

Whose TOC?

Looking at our example calling sequence above, A -> B -> F, when we get into F (ie. ftrace_caller()), what value does the TOC pointer have?

We can eliminate one possibility straight away: it's not the TOC pointer for F. Because ftrace_caller() is not a normal function, callers don't setup r12 to hold its entry point, and so it can't do a normal global entry point style TOC setup.

It should be the TOC pointer for B, because the call to _mcount (actually ftrace_caller()) is made after the TOC pointer is setup. But as we discussed above, the TOC pointer can be omitted if B doesn't need to use the TOC.

So we don't know whether we have A or B's TOC pointer in r2, and we also don't know whether that is a module's TOC pointer or the kernel's.

Luckily we have one thing in our favour. At all times we have a pointer in r13 which points to a per-cpu structure called the paca which contains the value of the kernel's TOC pointer. This means in ftrace_caller() we can save whatever value was in r2 and load the kernel's TOC pointer into r2, which then allows the ftrace code to access kernel globals.

Local calls that become global

As we described above, the linker decides at link time whether calls to a function are local or global, and calls the appropriate entry point. However live patching breaks this logic, by retrospectively diverting the call from A to B, which may have been local, to a call to P.

The patch function P is always in a newly loaded module, and in the common case the caller A will not be in that same module. So we must always call the global entry point of P.

If P needs to use its TOC then its global entry point will do the required TOC pointer setup, and TOC accesses in P will work just fine.

So what's the problem? P will do the TOC pointer setup, but it will not save the existing TOC pointer - that is up to the caller A. But A didn't save the TOC, because it knew it was calling a local function which shared the same TOC pointer.

The end result is that P will clobber A's TOC pointer, and on return to A the TOC pointer will be incorrect and the code will either crash or silently corrupt data.

Solution? Save the TOC pointer in F

So the problem we have is that A is not saving its TOC pointer, because it rightly doesn't think it needs to, but then P is clobbering the TOC pointer, because it rightly doesn't think it needs to save it.

Hopefully the obvious solution is that F needs to save A's TOC pointer before calling P. The question is where does it save it?

The obvious answer is "on the stack", because that's normally where functions save values before calling other functions, in fact that's basically the entire purpose of the stack.

This was our initial solution, in F we create a stack frame, save the TOC pointer and LR, then branch and link to P. On the return path P returns to F, which restores LR and the TOC pointer from the stack, deallocates its stack frame, and returns to A.

For the simple case this works fine, and it passed a surprising amount of testing. Luckily Torsten reminded us that it doesn't work if B needs some of its arguments passed on the stack.

For a typical function all the arguments are passed in registers. However in some cases some of the parameters must be passed on the stack, for example if the function takes more than 8 arguments, or is a varargs function. Crucially these parameters will be saved in the callers stack frame, ie. A's stack frame, and B will know that it can find them there.

Because P shares the same function prototype as B, it too will expect to find its parameters in A's stack frame. But because of live patching we have inserted a new stack frame in between, ie. F's stack frame.

                                                                +-----------------+
                                                                |                 |
                                                                | A's stack frame |
                                                                |                 |
                                                                |                 |
                                                                | +-------------+ |
                    +-----------------+                         | |             | |
                    |                 |                         | | Parameters  | |
                    | A's stack frame |                         | |             | |
                    |                 |                         | +-------------+ |
                    |                 |                         +-----------------+
                    | +-------------+ |                +------->|                 |
                    | |             | |                |        | F's stack frame |
           +------->| | Parameters  | |                |        |                 |
           |        | |             | |                |        |                 |
           |        | +-------------+ |        Wrong   |        |                 |
  Known    |        +-----------------+                |        +-----------------+
  offset   |        |                 |                |        |                 |
  from SP  |        | B's stack frame |                |        | P's stack frame |
           |        |                 |                |        |                 |
SP ------> +------+ +-----------------+     SP ------> +------+ +-----------------+

We could solve this by forcing all patch functions to be hand-written so that they know about this difference in stack layout. However that would seriously limit the usefulness of live patching, as all patches would have to be hand-written specifically for powerpc.

The solution: You need a stack in your stack

At this point we know F needs to save state between A and P, but it can't save that state on the stack. Where else could we put it?

After considering a few possibilities, all of which were unappealing, I proposed that we create a new "live patching" stack. That is, when F needs to save state before calling P, it allocates a stack frame on the livepatch stack, and stores its state there. It can then call P without perturbing the offset from P's stack frame to the parameters potentially stored in A's stack frame.

Additionally I proposed that we place the live patch stack in the existing stack, along with the existing thread_info:

+-------------------+
|                   |
|   Regular Stack   |  High addresses
|                   |
|         +         |
|         |         |
|         v         |
|                   |
|                   |
|      .......      |
|                   |
|                   |
|         ^         |
|         |         |
|         +         |
|                   |
|  Livepatch Stack  |
|                   |
+-------------------+
|                   |
|    thread info    |  Low addresses
|                   |
+-------------------+

The key point is that the livepatch stack grows upwards from just above the thread_info, whereas the regular stack grows down from the top of the stack.

The advantage of this is there are no extra allocations required, and there are no synchronisation problems, ie. the livepatch stack always exists if the thread exists, and it is not shared between threads.

The one downside is that it consumes stack space, meaning a kernel with a live patch enabled will use more stack space than one without. However in practice the kernel runs with a large overhead of free stack space, precisely because running out of stack space is already fatal. Hopefully in the medium term we can improve the kernel's handling of stack exhaustion, and at that point we can revisit separating the livepatch stack from the regular stack.

The final piece of the puzzle is the code that runs in F between A and P. If you've made it this far you should be pretty comfortable just reading the code, reproduced below:

livepatch_handler:
        CURRENT_THREAD_INFO(r12, r1)

        /* Save stack pointer into r0 */
        mr      r0, r1

        /* Allocate 3 x 8 bytes */
        ld      r1, TI_livepatch_sp(r12)
        addi    r1, r1, 24
        std     r1, TI_livepatch_sp(r12)

        /* Save toc & real LR on livepatch stack */
        std     r2,  -24(r1)
        mflr    r12
        std     r12, -16(r1)

        /* Store stack end marker */
        lis     r12, STACK_END_MAGIC@h
        ori     r12, r12, STACK_END_MAGIC@l
        std     r12, -8(r1)

        /* Restore real stack pointer */
        mr      r1, r0

        /* Put ctr in r12 for global entry and branch there */
        mfctr   r12
        bctrl

        /*
         * Now we are returning from the patched function to the original
         * caller A. We are free to use r0 and r12, and we can use r2 until we
         * restore it.
         */

        CURRENT_THREAD_INFO(r12, r1)

        /* Save stack pointer into r0 */
        mr      r0, r1

        ld      r1, TI_livepatch_sp(r12)

        /* Check stack marker hasn't been trashed */
        lis     r2,  STACK_END_MAGIC@h
        ori     r2,  r2, STACK_END_MAGIC@l
        ld      r12, -8(r1)
1:      tdne    r12, r2
        EMIT_BUG_ENTRY 1b, __FILE__, __LINE__ - 1, 0

        /* Restore LR & toc from livepatch stack */
        ld      r12, -16(r1)
        mtlr    r12
        ld      r2,  -24(r1)

        /* Pop livepatch stack frame */
        CURRENT_THREAD_INFO(r12, r0)
        subi    r1, r1, 24
        std     r1, TI_livepatch_sp(r12)

        /* Restore real stack pointer */
        mr      r1, r0

        /* Return to original caller of live patched function */
        blr

The end result

The ftrace changes were merged into 4.6, and the rest of the live patching support was merged into 4.7. This means in 4.7 you can enable CONFIG_LIVEPATCH and start patching your kernel. It's likely some distros will also backport the changes into older kernels.

In total the diffstat wasn't all that impressive:

 25 files changed, 778 insertions(+), 140 deletions(-)

But hopefully this article has made some of the complexity of the implementation clear.

Big thanks to everyone who helped write the code and/or did reviews:

  • Torsten Duwe
  • Vojtech Pavlik
  • Petr Mladek
  • Jiri Kosina
  • Miroslav Benes
  • Josh Poimboeuf
  • Balbir Singh
  • Kamalesh Babulal

2016 kernel