[RFC] GCC support for live-patching

[Qing Zhao <qing dot zhao at oracle dot com>]

Hi,

After more detailed study of GCC’s IPA optimizations, further study of the current available kernel live patching schemes and 
other live-patching user’s request, I came up with the following initial proposal in GCC to mainly support live-patching users who
manually create patches. 

Please take a look at the writeup, and let me know your opinions and suggestions.

thanks a lot.

Qing

===========

options to help live patching in GCC

Qing Zhao

10/17/2018
================================================

0. The proposal:

Provide two first class options in GCC to help live-patching users
who manually generate patches. 

A. an option to control GCC's IPA optimizations to provide a safe 
compilation for live-patching purpose. At the same time, provides
multiple-level control of patch code-size and run time performance 
tradeoff. 

-fease-live-patching={none|only-inline-static|inline|inline-clone}

When -fease-live-patching specified without any value, the default value
is "inline-clone". 

B. an option to compute the impacted function lists and dump them for
live-patching users.  

-flive-patching-list={func_name|all}{,dump_func_name}

This option guides the compiler to compute the list of impacted routines for
live patching. It only has effect when it is combined with -fease-live-patching.

when -flive-patching-list is specified without any value, the default value is
"all", i.e, compute the lists of impacted routines for all routines and dump 
them into stdout.

Please see more details of these two options in section 3. Details of the proposal.


1. A study of Kernel live patching schemes.

Three major kernel live patching tools:  https://lwn.net/Articles/734765/

* ksplice:   http://www.ksplice.com/doc/ksplice.pdf
* kpatch:    https://lwn.net/Articles/597123/
            https://github.com/dynup/kpatch
* kGraft:    
https://pdfs.semanticscholar.org/presentation/af4c/895aa3fef0cc2b501317aaec9d91ba2d704c.pdf

In the above, ksplice and kpatch can automatically generate binary patches 
as following:

   * a collection of tools which convert a source diff patch to a patch
module. They work by compiling the kernel both with and without the source
patch, comparing the binaries, and generating a binary patch module which 
includes new binary versions of the functions to be replaced.

on the other hand, kGraft offers a way to create patches entirely by hand. 
The source of the patch is a single C file, easy to review, easy to
maintain. 

In addition to kGraft, there are other live patching tools that prefer
creating patches by hand for the similar reason. 

The compiler support is mainly for the above live patching tools that create 
patches entirely by hand. the major purpose is:

 * control patch code size and debug complexity;
 * keep good run time performance;

2. the major problems of compiler in live patching:

For the live patching schemes that create patches by hand, when patching 
one function, there might a list of functions that will be impacted by 
this patched function due to compiler optimization/analyses (mainly IPA
optimization/analyses), a complete patch will include the patched function
and all impacted functions. Usually, there are two major factors to be
considered in such live patching schemes:

 * patch code size, one major factor is the length of the list 
of impacted functions;
 * run time performance.

If we want to control the patch code size, to make the list of impacted 
functions minimum, we have to disable corresponding compiler optimizations 
as much as possible.

On the other hand, in order to keep good run time performance, we need to 
keep the compiler optimization as much as possible. 

So, there should be some tradeoff between these two factors. 

The following are two major categories of compiler optimizations 
we should considered:

 A. compiler optimizations/analyses that extract ipa info from
a routine's body, and use such info to guide other optimization.

Since the body of the routine might be changed for live patching, 
the ipa info extracted from the body of the routine also changes,
as a result, all the routines that directly or indirectly utilize 
the ipa info from this routine are in the list of the impacted 
routines.  

Most of the IPA analyses and optimization belong to this category. 

Although theoretically the impacted routine list from such ipa 
phases could be computed, the list might be huge. Such huge list
of impacted routine might explode the patch code size too much. 

Therefore, it might be more pratical to just completely disable such
ipa optimizations/analyses.

 B. Inlining, and all optimizaitons that internally create clone. 
for example, cloning, ipa-sra, partial inlining, etc.
We can track the effect and impacted routine of such optimization 
easily. 
Such kind of optimization could be kept, but the compiler
should provide the list of impacted functions if a routine need to 
be patched.

There is patch code size explosion potential even with only enabling
inlining and cloning for live patching. Users need a way to control 
the inlining and cloning in order to control the code size explosion 
and complexity of debugging.

3. Details of the proposal:

What should GCC provide to live-patching users who manually create
patches? 

A. an option to control GCC's IPA optimizations to provide a safe 
compilation for live-patching purpose. At the same time, provides
multiple levels of patch code-size and run time performance tradeoff. 

-fease-live-patching={none|only-inline-static|inline|inline-clone}

-fease-live-patching=none

  Disable all ipa optimizations/analyses in GCC.  As a result, any
routine can be patched independently without impacting other routines.

-fease-live-patching=only-inline-static

  Only enable inlining of static functions, disable all other IPA 
optimizations/analyses. As a result, when patching a static routine,
all its callers need to be patches as well.

-fease-live-patching=inline

  Only enable inlining, disable all other IPA optimization/analyses.
As a result, when patching a routine, all its callers need to be patches
as well.

-fease-live-patching=inline-clone

  Only enable inlining and all optimizations that internally create clone,
for example, cloning, ipa-sra, partial inlining, etc; disable all 
other IPA optimizations/analyses.
  As a result, when patching a routine, all its callers and its clones'
callers need to be patched as well. 

When -fease-live-patching specified without any value, the default value
is "inline-clone". 

B. an option to compute the impacted function lists and dump them for
live-patching users.  

-flive-patching-list={func_name|all}{,dump_func_name}

This option guides the compiler to compute the list of impacted routines for
live patching. It only has effect when it is combined with -fease-live-patching.

-flive-patching-list=func_name

compute the list of impacted routines for the routine "func_name" and dump it
into stdout.

-flive-patching-list=all

compute the list of impacted routines for all routines and dump them 
into stdout.

-flive-patching-list=func_name,dump_func_name

compute the list of impacted routines for the routine "func_name" and dump it
into the file "dump_func_name".

-flive-patching-list=all,dump_func_name

compute the list of impacted routines for all routines and dump them 
into the file "dump_func_name".

when -flive-patching-list is specified without any value, the default value is
"all", i.e, compute the lists of impacted routines for all rourints and dump 
them into stdout.