xSplice prototype

xSplice prototype

[Ross Lagerwall]

Hi all,

I've gone ahead and implemented a bunch of xSplice stuff based on 
Konrad's xsplice branch. It is sitting in my github repository:
https://github.com/rosslagerwall/xen tagged prototype-v1
This is obviously prototype code, but please try it out. You'll also 
need this tool to build patches: 
https://github.com/rosslagerwall/xsplice-build tagged prototype-v1


Much of the work is implementing a basic version of the Linux kernel 
module loader. So the code does:
* Loading of xsplice modules.
* Copying allocated sections into a new executable region of memory.
* Resolving symbols.
* Applying relocations.
* Patching of altinstructions.
* Special handling of bug frames and exception tables.
* Unloading of xsplice modules.

The other main bit of this work is applying and reverting the patches 
safely. As implemented, the code is patched with each CPU waiting in the 
return-to-guest path (i.e. with no stack) which appears to be the safest 
way of patching. It should mean that stack checking is not required.

All of the following should work:
* Applying patches safely.
* Reverting patches safely.
* Replacing patches safely (e.g. reverting any applied patches and 
applying a new patch).
* Bug frames as part of modules. This means adding or changing WARN, 
ASSERT, BUG, and run_in_exception_handler works correctly. Line number 
only changes _are ignored_.
* Exception tables as part of modules. E.g. wrmsr_safe and copy_to_user 
work correctly when used in a patch module.
* Hook load and unload functions which run at patch apply and revert 
time respectively.
* Shadow variables. A minimal bit of infrastructure to attach a new 
variable to an existing data structure.


Limitations
===========
The above is enough to fully implement an update system where multiple 
source patches are combined (using combinediff) and built into a single 
binary which then atomically replaces any existing loaded patches (this 
is why I added a REPLACE operation). This is the approach used by kPatch 
and kGraft. Multiple completely independent patches can also be loaded 
but unexpected interactions may occur.

As it stands, the patches are statically linked which means that 
independent patches cannot be linked against one another (e.g. if one 
introduces a new symbol). Using the combinediff approach above fixes this.

Backtraces containing functions from a patch module do not show the 
symbol name.

There is no checking that a patch which is loaded is built for the 
correct hypervisor.

Binary patching works at the function level.


Design thoughts
===============
Combining patches at the source level is relatively easy. Multiple 
binary patches applied at runtime is tricky. I'm not convinced that it 
is necessarily a good idea. Based on the discussion so far, the sanest 
way of doing this that I can think of is:
* Each hypervisor has an embedded build id.
* Each binary patch has an embedded build id.
* The hypervisor should expose its build id and the build id of every 
loaded binary patch.
* Each binary patch specifies one or more build ids on which it depends. 
These build ids can be either a hypervisor build id or another patch 
build id. The dependencies could either identified automatically or by a 
developer.
* The userspace tool enforces dependency management (user can optionally 
force patch apply). I don't see any reason to involve the
hypervisor for dependency management.
Implementing this scheme will require dynamically linking the binary 
patches.

The CHECK phase seems unnecessary to me. I would think that any safety 
checking that needs to be done would be done atomically at the point of 
patch apply (or revert). Given the implemented system of applying 
patches, I'm not sure if any safety checking need be done at all.


Testing
=======
In case it's not clear what the workflow is, here is a sample transcript:

$ mkdir ~/work
$ cd ~/work
$ git clone git://github.com/rosslagerwall/xen.git
$ cd xen
$ git checkout prototype-v1
$ # Build a debug Xen and tools (including misc/xen-xsplice), install on 
a host and reboot

$ # Write a patch
$ git diff > ~/work/test1.patch
$ git reset --hard
$ # Write another patch
$ git diff > ~/work/test2.patch
$ git reset --hard
$ # Write another patch
$ git diff > ~/work/test3.patch
$ git reset --hard

$ cd ~/work
$ git clone git://github.com/rosslagerwall/xsplice-build.git
$ cd xsplice-build
$ git checkout prototype-v1
$ make
$ ./xsplice-build -s ~/work/xen -p ~/work/test1.patch -o out1 
--xen-debug --debug
$ ./xsplice-build -s ~/work/xen -p ~/work/test2.patch -o out2 
--xen-debug --debug
$ ./xsplice-build -s ~/work/xen -p ~/work/test3.patch -o out3 
--xen-debug --debug
$ # copy out*/test*.xsplice onto the host


On the host:
# xen-xsplice upload test1 test1.xsplice
# xen-xsplice upload test2 test2.xsplice
# xen-xsplice upload test3 test3.xsplice
# xen-xsplice check test1
# xen-xsplice check test2
# xen-xsplice check test3

# xen-xsplice apply test1
# # Verify test1 is applied
# xen-xsplice apply test2
# # Verify test2 is also applied
# xen-xsplice replace test3
# # Verify test3 is applied and test1 and test2 are not
# xen-xsplice revert test3
# # Verify test3 is not applied

# xen-xsplice unload test1
# xen-xsplice unload test2
# xen-xsplice unload test3

Thanks,
-- 
Ross Lagerwall

Re: xSplice prototype

[Konrad Rzeszutek Wilk]

On Fri, Oct 23, 2015 at 04:28:25PM +0100, Ross Lagerwall wrote:
> Hi all,
> 
> I've gone ahead and implemented a bunch of xSplice stuff based on Konrad's
> xsplice branch. It is sitting in my github repository:
> https://github.com/rosslagerwall/xen tagged prototype-v1
> This is obviously prototype code, but please try it out. You'll also need
> this tool to build patches: https://github.com/rosslagerwall/xsplice-build
> tagged prototype-v1
> 

Fantastic!!!

I should take vacation more often :-)

> 
> Much of the work is implementing a basic version of the Linux kernel module
> loader. So the code does:
> * Loading of xsplice modules.
> * Copying allocated sections into a new executable region of memory.
> * Resolving symbols.
> * Applying relocations.
> * Patching of altinstructions.
> * Special handling of bug frames and exception tables.
> * Unloading of xsplice modules.
> 
> The other main bit of this work is applying and reverting the patches
> safely. As implemented, the code is patched with each CPU waiting in the
> return-to-guest path (i.e. with no stack) which appears to be the safest way
> of patching. It should mean that stack checking is not required.
> 
> All of the following should work:
> * Applying patches safely.
> * Reverting patches safely.
> * Replacing patches safely (e.g. reverting any applied patches and applying
> a new patch).
> * Bug frames as part of modules. This means adding or changing WARN, ASSERT,
> BUG, and run_in_exception_handler works correctly. Line number only changes
> _are ignored_.
> * Exception tables as part of modules. E.g. wrmsr_safe and copy_to_user work
> correctly when used in a patch module.
> * Hook load and unload functions which run at patch apply and revert time
> respectively.

OK, we (me) should then also update the design document to mention that.

> * Shadow variables. A minimal bit of infrastructure to attach a new variable
> to an existing data structure.
> 
> 
> Limitations
> ===========
> The above is enough to fully implement an update system where multiple
> source patches are combined (using combinediff) and built into a single
> binary which then atomically replaces any existing loaded patches (this is
> why I added a REPLACE operation). This is the approach used by kPatch and
> kGraft. Multiple completely independent patches can also be loaded but
> unexpected interactions may occur.
> 
> As it stands, the patches are statically linked which means that independent
> patches cannot be linked against one another (e.g. if one introduces a new
> symbol). Using the combinediff approach above fixes this.
> 
> Backtraces containing functions from a patch module do not show the symbol
> name.
> 
> There is no checking that a patch which is loaded is built for the correct
> hypervisor.

Hehe.. bugs? What bugs!?
> 
> Binary patching works at the function level.
> 
> 
> Design thoughts
> ===============
> Combining patches at the source level is relatively easy. Multiple binary
> patches applied at runtime is tricky. I'm not convinced that it is
> necessarily a good idea. Based on the discussion so far, the sanest way of
> doing this that I can think of is:
> * Each hypervisor has an embedded build id.
> * Each binary patch has an embedded build id.
> * The hypervisor should expose its build id and the build id of every loaded
> binary patch.
> * Each binary patch specifies one or more build ids on which it depends.
> These build ids can be either a hypervisor build id or another patch build
> id. The dependencies could either identified automatically or by a
> developer.
> * The userspace tool enforces dependency management (user can optionally
> force patch apply). I don't see any reason to involve the
> hypervisor for dependency management.
> Implementing this scheme will require dynamically linking the binary
> patches.
> 
> The CHECK phase seems unnecessary to me. I would think that any safety
> checking that needs to be done would be done atomically at the point of
> patch apply (or revert). Given the implemented system of applying patches,
> I'm not sure if any safety checking need be done at all.

It was added as a way to do signature checking and any other type
of checking that needed to be done. And which may take quite a while
to get done - hence doing it asynchronously.


We have a meeting this Monday (Oct 26th) @ 10AM on the #xsplice channel.

And in which we can disucss the 'combining patches' part, the build-id, the
logging mechanism, and other things you had encountered and have thoughts on.

Again, thank you for doing this!
> 
> 
> Testing
> =======
> In case it's not clear what the workflow is, here is a sample transcript:
> 
> $ mkdir ~/work
> $ cd ~/work
> $ git clone git://github.com/rosslagerwall/xen.git
> $ cd xen
> $ git checkout prototype-v1
> $ # Build a debug Xen and tools (including misc/xen-xsplice), install on a
> host and reboot
> 
> $ # Write a patch
> $ git diff > ~/work/test1.patch
> $ git reset --hard
> $ # Write another patch
> $ git diff > ~/work/test2.patch
> $ git reset --hard
> $ # Write another patch
> $ git diff > ~/work/test3.patch
> $ git reset --hard
> 
> $ cd ~/work
> $ git clone git://github.com/rosslagerwall/xsplice-build.git
> $ cd xsplice-build
> $ git checkout prototype-v1
> $ make
> $ ./xsplice-build -s ~/work/xen -p ~/work/test1.patch -o out1 --xen-debug
> --debug
> $ ./xsplice-build -s ~/work/xen -p ~/work/test2.patch -o out2 --xen-debug
> --debug
> $ ./xsplice-build -s ~/work/xen -p ~/work/test3.patch -o out3 --xen-debug
> --debug
> $ # copy out*/test*.xsplice onto the host
> 
> 
> On the host:
> # xen-xsplice upload test1 test1.xsplice
> # xen-xsplice upload test2 test2.xsplice
> # xen-xsplice upload test3 test3.xsplice
> # xen-xsplice check test1
> # xen-xsplice check test2
> # xen-xsplice check test3
> 
> # xen-xsplice apply test1
> # # Verify test1 is applied
> # xen-xsplice apply test2
> # # Verify test2 is also applied
> # xen-xsplice replace test3
> # # Verify test3 is applied and test1 and test2 are not
> # xen-xsplice revert test3
> # # Verify test3 is not applied
> 
> # xen-xsplice unload test1
> # xen-xsplice unload test2
> # xen-xsplice unload test3
> 
> Thanks,
> -- 
> Ross Lagerwall

Re: xSplice prototype

[Ross Lagerwall]

On 10/23/2015 05:23 PM, Konrad Rzeszutek Wilk wrote:
> On Fri, Oct 23, 2015 at 04:28:25PM +0100, Ross Lagerwall wrote:
>> Limitations
>> ===========
>> The above is enough to fully implement an update system where multiple
>> source patches are combined (using combinediff) and built into a single
>> binary which then atomically replaces any existing loaded patches (this is
>> why I added a REPLACE operation). This is the approach used by kPatch and
>> kGraft. Multiple completely independent patches can also be loaded but
>> unexpected interactions may occur.
>>
>> As it stands, the patches are statically linked which means that independent
>> patches cannot be linked against one another (e.g. if one introduces a new
>> symbol). Using the combinediff approach above fixes this.
>>
>> Backtraces containing functions from a patch module do not show the symbol
>> name.
>>
>> There is no checking that a patch which is loaded is built for the correct
>> hypervisor.
>
> Hehe.. bugs? What bugs!?

Of course there are no bugs :-)

>>
>> Binary patching works at the function level.
>>
>>
>> Design thoughts
>> ===============
>> Combining patches at the source level is relatively easy. Multiple binary
>> patches applied at runtime is tricky. I'm not convinced that it is
>> necessarily a good idea. Based on the discussion so far, the sanest way of
>> doing this that I can think of is:
>> * Each hypervisor has an embedded build id.
>> * Each binary patch has an embedded build id.
>> * The hypervisor should expose its build id and the build id of every loaded
>> binary patch.
>> * Each binary patch specifies one or more build ids on which it depends.
>> These build ids can be either a hypervisor build id or another patch build
>> id. The dependencies could either identified automatically or by a
>> developer.
>> * The userspace tool enforces dependency management (user can optionally
>> force patch apply). I don't see any reason to involve the
>> hypervisor for dependency management.
>> Implementing this scheme will require dynamically linking the binary
>> patches.
>>
>> The CHECK phase seems unnecessary to me. I would think that any safety
>> checking that needs to be done would be done atomically at the point of
>> patch apply (or revert). Given the implemented system of applying patches,
>> I'm not sure if any safety checking need be done at all.
>
> It was added as a way to do signature checking and any other type
> of checking that needed to be done. And which may take quite a while
> to get done - hence doing it asynchronously.

OK. There are many things that need to be done to load an xSplice 
module, almost all of which are dependent on the size of the module and 
may also fail (e.g. resolving symbols, performing relocations, copying 
allocated sections, etc). I think signature checking should be as part 
of the load procedure, and if that needs to be done asynchronously, then 
so be it. The nice thing about doing signature checking at load time is 
that (if it's implemented as per Linux's signature checking) once the 
load phase is complete, the original uploaded payload can be freed from 
memory. It might be handy to think of the load procedure as equivalent 
to a basic version of the Linux kernel module loader (which is pretty 
much what I did when implementing it).

And while I remember, I think the REVERTED state is unnecessary. It 
seems exactly equivalent to the LOADED state, which is just confusing.

>
>
> We have a meeting this Monday (Oct 26th) @ 10AM on the #xsplice channel.
>
> And in which we can disucss the 'combining patches' part, the build-id, the
> logging mechanism, and other things you had encountered and have thoughts on.
>

Sure, we can discuss these items.

-- 
Ross Lagerwall

Re: xSplice prototype

[Konrad Rzeszutek Wilk]

On Mon, Oct 26, 2015 at 08:35:30AM +0000, Ross Lagerwall wrote:
> On 10/23/2015 05:23 PM, Konrad Rzeszutek Wilk wrote:
> >On Fri, Oct 23, 2015 at 04:28:25PM +0100, Ross Lagerwall wrote:
> >>Limitations
> >>===========
> >>The above is enough to fully implement an update system where multiple
> >>source patches are combined (using combinediff) and built into a single
> >>binary which then atomically replaces any existing loaded patches (this is
> >>why I added a REPLACE operation). This is the approach used by kPatch and
> >>kGraft. Multiple completely independent patches can also be loaded but
> >>unexpected interactions may occur.
> >>
> >>As it stands, the patches are statically linked which means that independent
> >>patches cannot be linked against one another (e.g. if one introduces a new
> >>symbol). Using the combinediff approach above fixes this.
> >>
> >>Backtraces containing functions from a patch module do not show the symbol
> >>name.
> >>
> >>There is no checking that a patch which is loaded is built for the correct
> >>hypervisor.
> >
> >Hehe.. bugs? What bugs!?
> 
> Of course there are no bugs :-)
> 
> >>
> >>Binary patching works at the function level.
> >>
> >>
> >>Design thoughts
> >>===============
> >>Combining patches at the source level is relatively easy. Multiple binary
> >>patches applied at runtime is tricky. I'm not convinced that it is
> >>necessarily a good idea. Based on the discussion so far, the sanest way of
> >>doing this that I can think of is:
> >>* Each hypervisor has an embedded build id.
> >>* Each binary patch has an embedded build id.
> >>* The hypervisor should expose its build id and the build id of every loaded
> >>binary patch.
> >>* Each binary patch specifies one or more build ids on which it depends.
> >>These build ids can be either a hypervisor build id or another patch build
> >>id. The dependencies could either identified automatically or by a
> >>developer.
> >>* The userspace tool enforces dependency management (user can optionally
> >>force patch apply). I don't see any reason to involve the
> >>hypervisor for dependency management.
> >>Implementing this scheme will require dynamically linking the binary
> >>patches.
> >>
> >>The CHECK phase seems unnecessary to me. I would think that any safety
> >>checking that needs to be done would be done atomically at the point of
> >>patch apply (or revert). Given the implemented system of applying patches,
> >>I'm not sure if any safety checking need be done at all.
> >
> >It was added as a way to do signature checking and any other type
> >of checking that needed to be done. And which may take quite a while
> >to get done - hence doing it asynchronously.
> 
> OK. There are many things that need to be done to load an xSplice module,
> almost all of which are dependent on the size of the module and may also
> fail (e.g. resolving symbols, performing relocations, copying allocated
> sections, etc). I think signature checking should be as part of the load
> procedure, and if that needs to be done asynchronously, then so be it. The
> nice thing about doing signature checking at load time is that (if it's
> implemented as per Linux's signature checking) once the load phase is
> complete, the original uploaded payload can be freed from memory. It might
> be handy to think of the load procedure as equivalent to a basic version of
> the Linux kernel module loader (which is pretty much what I did when
> implementing it).
> 
> And while I remember, I think the REVERTED state is unnecessary. It seems
> exactly equivalent to the LOADED state, which is just confusing.

Perhaps it should just move automatically from REVERT to LOADED? You have
to do some action to trigger it to unload.

And perhaps 'UNLOAD' is better than 'REVERT' ?

> 
> >
> >
> >We have a meeting this Monday (Oct 26th) @ 10AM on the #xsplice channel.
> >
> >And in which we can disucss the 'combining patches' part, the build-id, the
> >logging mechanism, and other things you had encountered and have thoughts on.
> >
> 
> Sure, we can discuss these items.

We didn't get to discuss all of them. Let me write up the minutes and send
them shorlty.

> 
> -- 
> Ross Lagerwall

Re: xSplice prototype

[Ross Lagerwall]

On 10/26/2015 03:03 PM, Konrad Rzeszutek Wilk wrote:
> On Mon, Oct 26, 2015 at 08:35:30AM +0000, Ross Lagerwall wrote:
>>>
>>> It was added as a way to do signature checking and any other type
>>> of checking that needed to be done. And which may take quite a while
>>> to get done - hence doing it asynchronously.
>>
>> OK. There are many things that need to be done to load an xSplice module,
>> almost all of which are dependent on the size of the module and may also
>> fail (e.g. resolving symbols, performing relocations, copying allocated
>> sections, etc). I think signature checking should be as part of the load
>> procedure, and if that needs to be done asynchronously, then so be it. The
>> nice thing about doing signature checking at load time is that (if it's
>> implemented as per Linux's signature checking) once the load phase is
>> complete, the original uploaded payload can be freed from memory. It might
>> be handy to think of the load procedure as equivalent to a basic version of
>> the Linux kernel module loader (which is pretty much what I did when
>> implementing it).
>>
>> And while I remember, I think the REVERTED state is unnecessary. It seems
>> exactly equivalent to the LOADED state, which is just confusing.
>
> Perhaps it should just move automatically from REVERT to LOADED? You have
> to do some action to trigger it to unload.
>
> And perhaps 'UNLOAD' is better than 'REVERT' ?
>

I think separating the actions from the state makes it clearer. So for 
example (ignoring CHECK for now), there are 2 states:
     LOADED, APPLIED
and 4 actions:
     LOAD paired with UNLOAD
     APPLY paired with REVERT

LOAD loads the payload
APPLY moves the payload from LOADED to APPLIED
REVERT moves the payload from APPLIED to LOADED
UNLOAD removes the payload from the hypervisor completely

Does this make sense?

-- 
Ross Lagerwall

Re: xSplice prototype

[Boos, Robert]

(Replacing dslutz@verizon.com with rboos@verizon.com since dslutz is no longer at Verizon.)

________________________________________
From: Ross Lagerwall [ross.lagerwall@citrix.com]
Sent: Monday, October 26, 2015 1:03 PM
To: Konrad Rzeszutek Wilk
Cc: elena.ufimtseva@oracle.com; hanweidong@huawei.com; jbeulich@suse.com; john.liuqiming@huawei.com; paul.voccio@rackspace.com; kurt.hackel@oracle.com; daniel.kiper@oracle.com; major.hayden@rackspace.com; liuyingdong@huawei.com; aliguori@amazon.com; xen-devel@lists.xenproject.org; lars.kurth@citrix.com; steven.wilson@rackspace.com; ian.campbell@citrix.com; peter.huangpeng@huawei.com; msw@amazon.com; xiantao.zxt@alibaba-inc.com; rick.harris@rackspace.com; boris.ostrovsky@oracle.com; jinsong.liu@alibaba-inc.com; amesserl@rackspace.com; mpohlack@amazon.com; dslutz@verizon.com; fanhenglong@huawei.com; andrew.cooper3@citrix.com
Subject: Re: [Xen-devel] xSplice prototype

On 10/26/2015 03:03 PM, Konrad Rzeszutek Wilk wrote:
> On Mon, Oct 26, 2015 at 08:35:30AM +0000, Ross Lagerwall wrote:
>>>
>>> It was added as a way to do signature checking and any other type
>>> of checking that needed to be done. And which may take quite a while
>>> to get done - hence doing it asynchronously.
>>
>> OK. There are many things that need to be done to load an xSplice module,
>> almost all of which are dependent on the size of the module and may also
>> fail (e.g. resolving symbols, performing relocations, copying allocated
>> sections, etc). I think signature checking should be as part of the load
>> procedure, and if that needs to be done asynchronously, then so be it. The
>> nice thing about doing signature checking at load time is that (if it's
>> implemented as per Linux's signature checking) once the load phase is
>> complete, the original uploaded payload can be freed from memory. It might
>> be handy to think of the load procedure as equivalent to a basic version of
>> the Linux kernel module loader (which is pretty much what I did when
>> implementing it).
>>
>> And while I remember, I think the REVERTED state is unnecessary. It seems
>> exactly equivalent to the LOADED state, which is just confusing.
>
> Perhaps it should just move automatically from REVERT to LOADED? You have
> to do some action to trigger it to unload.
>
> And perhaps 'UNLOAD' is better than 'REVERT' ?
>

I think separating the actions from the state makes it clearer. So for
example (ignoring CHECK for now), there are 2 states:
     LOADED, APPLIED
and 4 actions:
     LOAD paired with UNLOAD
     APPLY paired with REVERT

LOAD loads the payload
APPLY moves the payload from LOADED to APPLIED
REVERT moves the payload from APPLIED to LOADED
UNLOAD removes the payload from the hypervisor completely

Does this make sense?

--
Ross Lagerwall