Livepatch vs LTO

Livepatch vs LTO

[Josh Poimboeuf]

Hi all,

On IRC, Peter expressed some concern about -flive-patching, specifically
that the flag isn't compatible with LTO.

The upstream kernel currently doesn't support LTO, but Android is using
it with LLVM:

  https://source.android.com/devices/tech/debug/kcfi

And there seems to be progress being made in that direction for
upstream.

Live patching has at least the following issues with LTO:

- For source-based patch generation (klp-convert and friends), the GCC
  manual says that -flive-patching is incompatible with LTO.  Does
  anybody know if that's a hard incompatibility, or can it be fixed?

  Also, what about the performance implications of this flag with LTO?
  Might they become more pronounced?

  Also I wonder if -fdump-ipa-clones works with LTO?

  I also wonder about the future of source-based patch generation with
  LLVM.  Will it also have -flive-patching and -fdump-ipa-clones flags?

- For binary-based patch generation (kpatch-build), we currently diff
  objects at a per-compilation-unit level.  That would have to be
  changed to work on vmlinux.o instead.

- Objtool would also have to be changed to work on vmlinux.o.  It's
  currently not optimized for large files, and the per-.o whitelisting
  would need to be fixed.  And there may be other issues lurking.

Also, thinking about objtool in this context has given me another idea,
which might allow us to get rid of the use of -flive-patching and
-fdump-ipa-clones altogether (which are both nasty and way too
compiler-dependent):

Since objtool is already reading every function in the kernel, it could
create a checksum associated with each function, based on all the
instructions (both within the function and any alternatives or other
special sections it relies on).  The function checksums could be written
to a file.

Then, when a patch file is applied and the kernel rebuilt, the checksum
files could be compared to determine exactly which functions have
changed at a binary level.

Thoughts?  Any reasons why that wouldn't work?

And, if we wanted to take the idea even further, objtool could have the
ability to write the changed functions to a new object file.  Voila, we
now pretty much have kpatch-build :-)  (Though whether this is better
than source-based patch generation is certainly an open question.)

-- 
Josh

Re: Livepatch vs LTO

[Joe Lawrence]

On 4/25/19 11:26 AM, Josh Poimboeuf wrote:
> Hi all,
> 
> On IRC, Peter expressed some concern about -flive-patching, specifically
> that the flag isn't compatible with LTO.
> 
> The upstream kernel currently doesn't support LTO, but Android is using
> it with LLVM:
> 
>    https://source.android.com/devices/tech/debug/kcfi
> 
> And there seems to be progress being made in that direction for
> upstream.
> 
> Live patching has at least the following issues with LTO:
> 
> - For source-based patch generation (klp-convert and friends), the GCC
>    manual says that -flive-patching is incompatible with LTO.  Does
>    anybody know if that's a hard incompatibility, or can it be fixed?
> 
>    Also, what about the performance implications of this flag with LTO?
>    Might they become more pronounced?
> 
>    Also I wonder if -fdump-ipa-clones works with LTO?
> 
>    I also wonder about the future of source-based patch generation with
>    LLVM.  Will it also have -flive-patching and -fdump-ipa-clones flags?
> 
> - For binary-based patch generation (kpatch-build), we currently diff
>    objects at a per-compilation-unit level.  That would have to be
>    changed to work on vmlinux.o instead.
> 
> - Objtool would also have to be changed to work on vmlinux.o.  It's
>    currently not optimized for large files, and the per-.o whitelisting
>    would need to be fixed.  And there may be other issues lurking.
> 
> Also, thinking about objtool in this context has given me another idea,
> which might allow us to get rid of the use of -flive-patching and
> -fdump-ipa-clones altogether (which are both nasty and way too
> compiler-dependent):

Would objtool work around these issues because it would (pending the 
above changes) operate on post-LTO object files?

> Since objtool is already reading every function in the kernel, it could
> create a checksum associated with each function, based on all the
> instructions (both within the function and any alternatives or other
> special sections it relies on).  The function checksums could be written
> to a file.
> 
> Then, when a patch file is applied and the kernel rebuilt, the checksum
> files could be compared to determine exactly which functions have
> changed at a binary level.
> 
> Thoughts?  Any reasons why that wouldn't work?

This is an interesting option.  Keep in mind, like kpatch-build, it 
would detect changes as a result of source code line number positioning, 
ie WARN_* or might_sleep macros that kpatch-build currently detects and 
chooses to ignore.  Not a big deal, but warts like this start 
introducing more instruction decoding into the process.

Also, I think a klp-convert type script would still be needed to create 
livepatch symbols and their corresponding sections and relocations, 
right?  However, we might not need manual symbol <obj, pos> annotations 
to pull this off since presumably the object will have already 
built/linked.  I think.

I've only just started looking at klp-convert and asm alternatives, but 
maybe this would also help determine the alteratives-relocation to 
klp_object relationship that we will need if we want klp-convert to 
create klp.arch sections.

> And, if we wanted to take the idea even further, objtool could have the
> ability to write the changed functions to a new object file.  Voila, we
> now pretty much have kpatch-build :-)  (Though whether this is better
> than source-based patch generation is certainly an open question.)

Porting objtool to new arches is probably easier than kpatch-build at least.

-- Joe

Re: Livepatch vs LTO

[Josh Poimboeuf]

On Thu, Apr 25, 2019 at 02:22:23PM -0400, Joe Lawrence wrote:
> On 4/25/19 11:26 AM, Josh Poimboeuf wrote:
> > Hi all,
> > 
> > On IRC, Peter expressed some concern about -flive-patching, specifically
> > that the flag isn't compatible with LTO.
> > 
> > The upstream kernel currently doesn't support LTO, but Android is using
> > it with LLVM:
> > 
> >    https://source.android.com/devices/tech/debug/kcfi
> > 
> > And there seems to be progress being made in that direction for
> > upstream.
> > 
> > Live patching has at least the following issues with LTO:
> > 
> > - For source-based patch generation (klp-convert and friends), the GCC
> >    manual says that -flive-patching is incompatible with LTO.  Does
> >    anybody know if that's a hard incompatibility, or can it be fixed?
> > 
> >    Also, what about the performance implications of this flag with LTO?
> >    Might they become more pronounced?
> > 
> >    Also I wonder if -fdump-ipa-clones works with LTO?
> > 
> >    I also wonder about the future of source-based patch generation with
> >    LLVM.  Will it also have -flive-patching and -fdump-ipa-clones flags?
> > 
> > - For binary-based patch generation (kpatch-build), we currently diff
> >    objects at a per-compilation-unit level.  That would have to be
> >    changed to work on vmlinux.o instead.
> > 
> > - Objtool would also have to be changed to work on vmlinux.o.  It's
> >    currently not optimized for large files, and the per-.o whitelisting
> >    would need to be fixed.  And there may be other issues lurking.
> > 
> > Also, thinking about objtool in this context has given me another idea,
> > which might allow us to get rid of the use of -flive-patching and
> > -fdump-ipa-clones altogether (which are both nasty and way too
> > compiler-dependent):
> 
> Would objtool work around these issues because it would (pending the above
> changes) operate on post-LTO object files?

No, my idea below would work either way (LTO or not).

With the current approach of objtool running per .o file, it could
create a function checksum file per .o file.

With objtool running once on vmlinux.o, it would instead just make one
big function checksum file for vmlinux.o, plus one per kernel module.

> > Since objtool is already reading every function in the kernel, it could
> > create a checksum associated with each function, based on all the
> > instructions (both within the function and any alternatives or other
> > special sections it relies on).  The function checksums could be written
> > to a file.
> > 
> > Then, when a patch file is applied and the kernel rebuilt, the checksum
> > files could be compared to determine exactly which functions have
> > changed at a binary level.
> > 
> > Thoughts?  Any reasons why that wouldn't work?
> 
> This is an interesting option.  Keep in mind, like kpatch-build, it would
> detect changes as a result of source code line number positioning, ie WARN_*
> or might_sleep macros that kpatch-build currently detects and chooses to
> ignore.  Not a big deal, but warts like this start introducing more
> instruction decoding into the process.

True.

> Also, I think a klp-convert type script would still be needed to create
> livepatch symbols and their corresponding sections and relocations, right?

Right.  Unless we did the option I mentioned below where objtool would
become a full kpatch-build replacement.

> However, we might not need manual symbol <obj, pos> annotations to pull this
> off since presumably the object will have already built/linked.  I think.

Actually I'm not sure about that.  Even when analyzing vmlinux.o, the
object hasn't been fully linked so the final addresses aren't known.

> I've only just started looking at klp-convert and asm alternatives, but
> maybe this would also help determine the alteratives-relocation to
> klp_object relationship that we will need if we want klp-convert to create
> klp.arch sections.

TBH, I'm a bit behind on that discussion :-)

> > And, if we wanted to take the idea even further, objtool could have the
> > ability to write the changed functions to a new object file.  Voila, we
> > now pretty much have kpatch-build :-)  (Though whether this is better
> > than source-based patch generation is certainly an open question.)
> 
> Porting objtool to new arches is probably easier than kpatch-build at least.

Yeah.  And there's really a lot of overlap between the two, so it could
potentially be a decent option.

-- 
Josh

Re: Livepatch vs LTO

[Miroslav Benes]

[ adding CCs ]

On Thu, 25 Apr 2019, Josh Poimboeuf wrote:

> Hi all,
> 
> On IRC, Peter expressed some concern about -flive-patching, specifically
> that the flag isn't compatible with LTO.
> 
> The upstream kernel currently doesn't support LTO, but Android is using
> it with LLVM:
> 
>   https://source.android.com/devices/tech/debug/kcfi
> 
> And there seems to be progress being made in that direction for
> upstream.
> 
> Live patching has at least the following issues with LTO:
> 
> - For source-based patch generation (klp-convert and friends), the GCC
>   manual says that -flive-patching is incompatible with LTO.  Does
>   anybody know if that's a hard incompatibility, or can it be fixed?

Honza could know more. It was either that LTO by itself complicates 
things for live patching, or that LTO adds more optimizations which are 
potentially unsafe.

>   Also, what about the performance implications of this flag with LTO?
>   Might they become more pronounced?

It could. Theoretically. The scope for optimizations would be much 
broader.

>   Also I wonder if -fdump-ipa-clones works with LTO?

It should. According to Martin, there is (almost) nothing special about 
LTO. Optimization infrastructure is the same, only the scope is not 
limited to one translation unit.

>   I also wonder about the future of source-based patch generation with
>   LLVM.  Will it also have -flive-patching and -fdump-ipa-clones flags?

Honestly no idea.

> - For binary-based patch generation (kpatch-build), we currently diff
>   objects at a per-compilation-unit level.  That would have to be
>   changed to work on vmlinux.o instead.
> 
> - Objtool would also have to be changed to work on vmlinux.o.  It's
>   currently not optimized for large files, and the per-.o whitelisting
>   would need to be fixed.  And there may be other issues lurking.
> 
> Also, thinking about objtool in this context has given me another idea,
> which might allow us to get rid of the use of -flive-patching and
> -fdump-ipa-clones altogether (which are both nasty and way too
> compiler-dependent):
> 
> Since objtool is already reading every function in the kernel, it could
> create a checksum associated with each function, based on all the
> instructions (both within the function and any alternatives or other
> special sections it relies on).  The function checksums could be written
> to a file.
> 
> Then, when a patch file is applied and the kernel rebuilt, the checksum
> files could be compared to determine exactly which functions have
> changed at a binary level.
> 
> Thoughts?  Any reasons why that wouldn't work?

I think it could work. If nothing else, it would give us the information 
we look for.
 
> And, if we wanted to take the idea even further, objtool could have the
> ability to write the changed functions to a new object file.  Voila, we
> now pretty much have kpatch-build :-)  (Though whether this is better
> than source-based patch generation is certainly an open question.)

...worth of discussion.

Miroslav

Re: Livepatch vs LTO

[Jan Hubicka]

> [ adding CCs ]
> 
> On Thu, 25 Apr 2019, Josh Poimboeuf wrote:
> 
> > Hi all,
> > 
> > On IRC, Peter expressed some concern about -flive-patching, specifically
> > that the flag isn't compatible with LTO.
> > 
> > The upstream kernel currently doesn't support LTO, but Android is using
> > it with LLVM:
> > 
> >   https://source.android.com/devices/tech/debug/kcfi
> > 
> > And there seems to be progress being made in that direction for
> > upstream.
> > 
> > Live patching has at least the following issues with LTO:
> > 
> > - For source-based patch generation (klp-convert and friends), the GCC
> >   manual says that -flive-patching is incompatible with LTO.  Does
> >   anybody know if that's a hard incompatibility, or can it be fixed?
> 
> Honza could know more. It was either that LTO by itself complicates 
> things for live patching, or that LTO adds more optimizations which are 
> potentially unsafe.

The original patch, by Oracle, was disabling inlining of everyting else
than static functions and later it was strenghtened to disable all the
other inter-procedural optimization as well. With LTO this does not make
that much of sense because, based on linker resolution file, GCC will
turn non-static functions to static when it knows that non-LTO code will
not bind to it.  To make this work we would need to track what was
static originally and what not. But doing so would still prevent most of
LTO transforms because it is all about cross-module inlining and 
propagation and that all needs to be forbidden for this mode of live
patching to make sense.

So basically -flto -flive-patching=inline-only-static would be pretty
much equivalent of -ffunction-sections -fdata-section and enabling
removal of dead sections in the linker. Just slower at compile time.

The clone tracking logic is more compatible with LTO becuase it does not
prevent most optimizations.  I guess it could work and we probably want
to add support for it incrementally.
> 
> >   Also, what about the performance implications of this flag with LTO?
> >   Might they become more pronounced?
> 
> It could. Theoretically. The scope for optimizations would be much 
> broader.
> 
> >   Also I wonder if -fdump-ipa-clones works with LTO?
> 
> It should. According to Martin, there is (almost) nothing special about 
> LTO. Optimization infrastructure is the same, only the scope is not 
> limited to one translation unit.

Yes, you will likely get considerably more clones and inline copies to
care about while doing the live patch.  I would be interested to know
how well it work in practice. No idea if that would be a problem.

Honza

Re: Livepatch vs LTO

[Josh Poimboeuf]

On Fri, Apr 26, 2019 at 11:00:48AM +0200, Miroslav Benes wrote:
> > - For binary-based patch generation (kpatch-build), we currently diff
> >   objects at a per-compilation-unit level.  That would have to be
> >   changed to work on vmlinux.o instead.
> > 
> > - Objtool would also have to be changed to work on vmlinux.o.  It's
> >   currently not optimized for large files, and the per-.o whitelisting
> >   would need to be fixed.  And there may be other issues lurking.
> > 
> > Also, thinking about objtool in this context has given me another idea,
> > which might allow us to get rid of the use of -flive-patching and
> > -fdump-ipa-clones altogether (which are both nasty and way too
> > compiler-dependent):
> > 
> > Since objtool is already reading every function in the kernel, it could
> > create a checksum associated with each function, based on all the
> > instructions (both within the function and any alternatives or other
> > special sections it relies on).  The function checksums could be written
> > to a file.
> > 
> > Then, when a patch file is applied and the kernel rebuilt, the checksum
> > files could be compared to determine exactly which functions have
> > changed at a binary level.
> > 
> > Thoughts?  Any reasons why that wouldn't work?
> 
> I think it could work. If nothing else, it would give us the information 
> we look for.

I'm gone next week but after that I'll start looking at implementing
this.

> > And, if we wanted to take the idea even further, objtool could have the
> > ability to write the changed functions to a new object file.  Voila, we
> > now pretty much have kpatch-build :-)  (Though whether this is better
> > than source-based patch generation is certainly an open question.)
> 
> ...worth of discussion.

When I get some free time I might prototype something to see what it
would look like.

-- 
Josh