diff options
Diffstat (limited to 'Documentation/livepatch')
| -rw-r--r-- | Documentation/livepatch/callbacks.rst | 133 | ||||
| -rw-r--r-- | Documentation/livepatch/callbacks.txt | 605 | ||||
| -rw-r--r-- | Documentation/livepatch/cumulative-patches.rst | 102 | ||||
| -rw-r--r-- | Documentation/livepatch/index.rst | 21 | ||||
| -rw-r--r-- | Documentation/livepatch/livepatch.rst (renamed from Documentation/livepatch/livepatch.txt) | 230 | ||||
| -rw-r--r-- | Documentation/livepatch/module-elf-format.rst (renamed from Documentation/livepatch/module-elf-format.txt) | 353 | ||||
| -rw-r--r-- | Documentation/livepatch/shadow-vars.rst (renamed from Documentation/livepatch/shadow-vars.txt) | 65 |
7 files changed, 587 insertions, 922 deletions
diff --git a/Documentation/livepatch/callbacks.rst b/Documentation/livepatch/callbacks.rst new file mode 100644 index 000000000000..470944aa8658 --- /dev/null +++ b/Documentation/livepatch/callbacks.rst @@ -0,0 +1,133 @@ +====================== +(Un)patching Callbacks +====================== + +Livepatch (un)patch-callbacks provide a mechanism for livepatch modules +to execute callback functions when a kernel object is (un)patched. They +can be considered a **power feature** that **extends livepatching abilities** +to include: + + - Safe updates to global data + + - "Patches" to init and probe functions + + - Patching otherwise unpatchable code (i.e. assembly) + +In most cases, (un)patch callbacks will need to be used in conjunction +with memory barriers and kernel synchronization primitives, like +mutexes/spinlocks, or even stop_machine(), to avoid concurrency issues. + +1. Motivation +============= + +Callbacks differ from existing kernel facilities: + + - Module init/exit code doesn't run when disabling and re-enabling a + patch. + + - A module notifier can't stop a to-be-patched module from loading. + +Callbacks are part of the klp_object structure and their implementation +is specific to that klp_object. Other livepatch objects may or may not +be patched, irrespective of the target klp_object's current state. + +2. Callback types +================= + +Callbacks can be registered for the following livepatch actions: + + * Pre-patch + - before a klp_object is patched + + * Post-patch + - after a klp_object has been patched and is active + across all tasks + + * Pre-unpatch + - before a klp_object is unpatched (ie, patched code is + active), used to clean up post-patch callback + resources + + * Post-unpatch + - after a klp_object has been patched, all code has + been restored and no tasks are running patched code, + used to cleanup pre-patch callback resources + +3. How it works +=============== + +Each callback is optional, omitting one does not preclude specifying any +other. However, the livepatching core executes the handlers in +symmetry: pre-patch callbacks have a post-unpatch counterpart and +post-patch callbacks have a pre-unpatch counterpart. An unpatch +callback will only be executed if its corresponding patch callback was +executed. Typical use cases pair a patch handler that acquires and +configures resources with an unpatch handler tears down and releases +those same resources. + +A callback is only executed if its host klp_object is loaded. For +in-kernel vmlinux targets, this means that callbacks will always execute +when a livepatch is enabled/disabled. For patch target kernel modules, +callbacks will only execute if the target module is loaded. When a +module target is (un)loaded, its callbacks will execute only if the +livepatch module is enabled. + +The pre-patch callback, if specified, is expected to return a status +code (0 for success, -ERRNO on error). An error status code indicates +to the livepatching core that patching of the current klp_object is not +safe and to stop the current patching request. (When no pre-patch +callback is provided, the transition is assumed to be safe.) If a +pre-patch callback returns failure, the kernel's module loader will: + + - Refuse to load a livepatch, if the livepatch is loaded after + targeted code. + + or: + + - Refuse to load a module, if the livepatch was already successfully + loaded. + +No post-patch, pre-unpatch, or post-unpatch callbacks will be executed +for a given klp_object if the object failed to patch, due to a failed +pre_patch callback or for any other reason. + +If a patch transition is reversed, no pre-unpatch handlers will be run +(this follows the previously mentioned symmetry -- pre-unpatch callbacks +will only occur if their corresponding post-patch callback executed). + +If the object did successfully patch, but the patch transition never +started for some reason (e.g., if another object failed to patch), +only the post-unpatch callback will be called. + +4. Use cases +============ + +Sample livepatch modules demonstrating the callback API can be found in +samples/livepatch/ directory. These samples were modified for use in +kselftests and can be found in the lib/livepatch directory. + +Global data update +------------------ + +A pre-patch callback can be useful to update a global variable. For +example, 75ff39ccc1bd ("tcp: make challenge acks less predictable") +changes a global sysctl, as well as patches the tcp_send_challenge_ack() +function. + +In this case, if we're being super paranoid, it might make sense to +patch the data *after* patching is complete with a post-patch callback, +so that tcp_send_challenge_ack() could first be changed to read +sysctl_tcp_challenge_ack_limit with READ_ONCE. + +__init and probe function patches support +----------------------------------------- + +Although __init and probe functions are not directly livepatch-able, it +may be possible to implement similar updates via pre/post-patch +callbacks. + +The commit ``48900cb6af42 ("virtio-net: drop NETIF_F_FRAGLIST")`` change the way that +virtnet_probe() initialized its driver's net_device features. A +pre/post-patch callback could iterate over all such devices, making a +similar change to their hw_features value. (Client functions of the +value may need to be updated accordingly.) diff --git a/Documentation/livepatch/callbacks.txt b/Documentation/livepatch/callbacks.txt deleted file mode 100644 index c9776f48e458..000000000000 --- a/Documentation/livepatch/callbacks.txt +++ /dev/null @@ -1,605 +0,0 @@ -====================== -(Un)patching Callbacks -====================== - -Livepatch (un)patch-callbacks provide a mechanism for livepatch modules -to execute callback functions when a kernel object is (un)patched. They -can be considered a "power feature" that extends livepatching abilities -to include: - - - Safe updates to global data - - - "Patches" to init and probe functions - - - Patching otherwise unpatchable code (i.e. assembly) - -In most cases, (un)patch callbacks will need to be used in conjunction -with memory barriers and kernel synchronization primitives, like -mutexes/spinlocks, or even stop_machine(), to avoid concurrency issues. - -Callbacks differ from existing kernel facilities: - - - Module init/exit code doesn't run when disabling and re-enabling a - patch. - - - A module notifier can't stop a to-be-patched module from loading. - -Callbacks are part of the klp_object structure and their implementation -is specific to that klp_object. Other livepatch objects may or may not -be patched, irrespective of the target klp_object's current state. - -Callbacks can be registered for the following livepatch actions: - - * Pre-patch - before a klp_object is patched - - * Post-patch - after a klp_object has been patched and is active - across all tasks - - * Pre-unpatch - before a klp_object is unpatched (ie, patched code is - active), used to clean up post-patch callback - resources - - * Post-unpatch - after a klp_object has been patched, all code has - been restored and no tasks are running patched code, - used to cleanup pre-patch callback resources - -Each callback is optional, omitting one does not preclude specifying any -other. However, the livepatching core executes the handlers in -symmetry: pre-patch callbacks have a post-unpatch counterpart and -post-patch callbacks have a pre-unpatch counterpart. An unpatch -callback will only be executed if its corresponding patch callback was -executed. Typical use cases pair a patch handler that acquires and -configures resources with an unpatch handler tears down and releases -those same resources. - -A callback is only executed if its host klp_object is loaded. For -in-kernel vmlinux targets, this means that callbacks will always execute -when a livepatch is enabled/disabled. For patch target kernel modules, -callbacks will only execute if the target module is loaded. When a -module target is (un)loaded, its callbacks will execute only if the -livepatch module is enabled. - -The pre-patch callback, if specified, is expected to return a status -code (0 for success, -ERRNO on error). An error status code indicates -to the livepatching core that patching of the current klp_object is not -safe and to stop the current patching request. (When no pre-patch -callback is provided, the transition is assumed to be safe.) If a -pre-patch callback returns failure, the kernel's module loader will: - - - Refuse to load a livepatch, if the livepatch is loaded after - targeted code. - - or: - - - Refuse to load a module, if the livepatch was already successfully - loaded. - -No post-patch, pre-unpatch, or post-unpatch callbacks will be executed -for a given klp_object if the object failed to patch, due to a failed -pre_patch callback or for any other reason. - -If a patch transition is reversed, no pre-unpatch handlers will be run -(this follows the previously mentioned symmetry -- pre-unpatch callbacks -will only occur if their corresponding post-patch callback executed). - -If the object did successfully patch, but the patch transition never -started for some reason (e.g., if another object failed to patch), -only the post-unpatch callback will be called. - - -Example Use-cases -================= - -Update global data ------------------- - -A pre-patch callback can be useful to update a global variable. For -example, 75ff39ccc1bd ("tcp: make challenge acks less predictable") -changes a global sysctl, as well as patches the tcp_send_challenge_ack() -function. - -In this case, if we're being super paranoid, it might make sense to -patch the data *after* patching is complete with a post-patch callback, -so that tcp_send_challenge_ack() could first be changed to read -sysctl_tcp_challenge_ack_limit with READ_ONCE. - - -Support __init and probe function patches ------------------------------------------ - -Although __init and probe functions are not directly livepatch-able, it -may be possible to implement similar updates via pre/post-patch -callbacks. - -48900cb6af42 ("virtio-net: drop NETIF_F_FRAGLIST") change the way that -virtnet_probe() initialized its driver's net_device features. A -pre/post-patch callback could iterate over all such devices, making a -similar change to their hw_features value. (Client functions of the -value may need to be updated accordingly.) - - -Test cases -========== - -What follows is not an exhaustive test suite of every possible livepatch -pre/post-(un)patch combination, but a selection that demonstrates a few -important concepts. Each test case uses the kernel modules located in -the samples/livepatch/ and assumes that no livepatches are loaded at the -beginning of the test. - - -Test 1 ------- - -Test a combination of loading a kernel module and a livepatch that -patches a function in the first module. (Un)load the target module -before the livepatch module: - -- load target module -- load livepatch -- disable livepatch -- unload target module -- unload livepatch - -First load a target module: - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 34.475708] livepatch_callbacks_mod: livepatch_callbacks_mod_init - -On livepatch enable, before the livepatch transition starts, pre-patch -callbacks are executed for vmlinux and livepatch_callbacks_mod (those -klp_objects currently loaded). After klp_objects are patched according -to the klp_patch, their post-patch callbacks run and the transition -completes: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 36.503719] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 36.504213] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 36.504238] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 36.504721] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 36.505849] livepatch: 'livepatch_callbacks_demo': starting patching transition - [ 37.727133] livepatch: 'livepatch_callbacks_demo': completing patching transition - [ 37.727232] livepatch_callbacks_demo: post_patch_callback: vmlinux - [ 37.727860] livepatch_callbacks_demo: post_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 37.728792] livepatch: 'livepatch_callbacks_demo': patching complete - -Similarly, on livepatch disable, pre-patch callbacks run before the -unpatching transition starts. klp_objects are reverted, post-patch -callbacks execute and the transition completes: - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 38.510209] livepatch: 'livepatch_callbacks_demo': initializing unpatching transition - [ 38.510234] livepatch_callbacks_demo: pre_unpatch_callback: vmlinux - [ 38.510982] livepatch_callbacks_demo: pre_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 38.512209] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 39.711132] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 39.711210] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 39.711779] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 39.712735] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - % rmmod samples/livepatch/livepatch-callbacks-mod.ko - [ 42.534183] livepatch_callbacks_mod: livepatch_callbacks_mod_exit - - -Test 2 ------- - -This test is similar to the previous test, but (un)load the livepatch -module before the target kernel module. This tests the livepatch core's -module_coming handler: - -- load livepatch -- load target module -- disable livepatch -- unload livepatch -- unload target module - - -On livepatch enable, only pre/post-patch callbacks are executed for -currently loaded klp_objects, in this case, vmlinux: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 44.553328] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 44.553997] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 44.554049] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 44.554845] livepatch: 'livepatch_callbacks_demo': starting patching transition - [ 45.727128] livepatch: 'livepatch_callbacks_demo': completing patching transition - [ 45.727212] livepatch_callbacks_demo: post_patch_callback: vmlinux - [ 45.727961] livepatch: 'livepatch_callbacks_demo': patching complete - -When a targeted module is subsequently loaded, only its pre/post-patch -callbacks are executed: - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 46.560845] livepatch: applying patch 'livepatch_callbacks_demo' to loading module 'livepatch_callbacks_mod' - [ 46.561988] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 46.563452] livepatch_callbacks_demo: post_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 46.565495] livepatch_callbacks_mod: livepatch_callbacks_mod_init - -On livepatch disable, all currently loaded klp_objects' (vmlinux and -livepatch_callbacks_mod) pre/post-unpatch callbacks are executed: - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 48.568885] livepatch: 'livepatch_callbacks_demo': initializing unpatching transition - [ 48.568910] livepatch_callbacks_demo: pre_unpatch_callback: vmlinux - [ 48.569441] livepatch_callbacks_demo: pre_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 48.570502] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 49.759091] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 49.759171] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 49.759742] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 49.760690] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - % rmmod samples/livepatch/livepatch-callbacks-mod.ko - [ 52.592283] livepatch_callbacks_mod: livepatch_callbacks_mod_exit - - -Test 3 ------- - -Test loading the livepatch after a targeted kernel module, then unload -the kernel module before disabling the livepatch. This tests the -livepatch core's module_going handler: - -- load target module -- load livepatch -- unload target module -- disable livepatch -- unload livepatch - -First load a target module, then the livepatch: - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 54.607948] livepatch_callbacks_mod: livepatch_callbacks_mod_init - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 56.613919] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 56.614411] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 56.614436] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 56.614818] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 56.615656] livepatch: 'livepatch_callbacks_demo': starting patching transition - [ 57.759070] livepatch: 'livepatch_callbacks_demo': completing patching transition - [ 57.759147] livepatch_callbacks_demo: post_patch_callback: vmlinux - [ 57.759621] livepatch_callbacks_demo: post_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_LIVE] Normal state - [ 57.760307] livepatch: 'livepatch_callbacks_demo': patching complete - -When a target module is unloaded, the livepatch is only reverted from -that klp_object (livepatch_callbacks_mod). As such, only its pre and -post-unpatch callbacks are executed when this occurs: - - % rmmod samples/livepatch/livepatch-callbacks-mod.ko - [ 58.623409] livepatch_callbacks_mod: livepatch_callbacks_mod_exit - [ 58.623903] livepatch_callbacks_demo: pre_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_GOING] Going away - [ 58.624658] livepatch: reverting patch 'livepatch_callbacks_demo' on unloading module 'livepatch_callbacks_mod' - [ 58.625305] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_GOING] Going away - -When the livepatch is disabled, pre and post-unpatch callbacks are run -for the remaining klp_object, vmlinux: - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 60.638420] livepatch: 'livepatch_callbacks_demo': initializing unpatching transition - [ 60.638444] livepatch_callbacks_demo: pre_unpatch_callback: vmlinux - [ 60.638996] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 61.727088] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 61.727165] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 61.727985] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - - -Test 4 ------- - -This test is similar to the previous test, however the livepatch is -loaded first. This tests the livepatch core's module_coming and -module_going handlers: - -- load livepatch -- load target module -- unload target module -- disable livepatch -- unload livepatch - -First load the livepatch: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 64.661552] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 64.662147] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 64.662175] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 64.662850] livepatch: 'livepatch_callbacks_demo': starting patching transition - [ 65.695056] livepatch: 'livepatch_callbacks_demo': completing patching transition - [ 65.695147] livepatch_callbacks_demo: post_patch_callback: vmlinux - [ 65.695561] livepatch: 'livepatch_callbacks_demo': patching complete - -When a targeted kernel module is subsequently loaded, only its -pre/post-patch callbacks are executed: - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 66.669196] livepatch: applying patch 'livepatch_callbacks_demo' to loading module 'livepatch_callbacks_mod' - [ 66.669882] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 66.670744] livepatch_callbacks_demo: post_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 66.672873] livepatch_callbacks_mod: livepatch_callbacks_mod_init - -When the target module is unloaded, the livepatch is only reverted from -the livepatch_callbacks_mod klp_object. As such, only pre and -post-unpatch callbacks are executed when this occurs: - - % rmmod samples/livepatch/livepatch-callbacks-mod.ko - [ 68.680065] livepatch_callbacks_mod: livepatch_callbacks_mod_exit - [ 68.680688] livepatch_callbacks_demo: pre_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_GOING] Going away - [ 68.681452] livepatch: reverting patch 'livepatch_callbacks_demo' on unloading module 'livepatch_callbacks_mod' - [ 68.682094] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_GOING] Going away - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 70.689225] livepatch: 'livepatch_callbacks_demo': initializing unpatching transition - [ 70.689256] livepatch_callbacks_demo: pre_unpatch_callback: vmlinux - [ 70.689882] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 71.711080] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 71.711481] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 71.711988] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - - -Test 5 ------- - -A simple test of loading a livepatch without one of its patch target -klp_objects ever loaded (livepatch_callbacks_mod): - -- load livepatch -- disable livepatch -- unload livepatch - -Load the livepatch: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 74.711081] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 74.711595] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 74.711639] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 74.712272] livepatch: 'livepatch_callbacks_demo': starting patching transition - [ 75.743137] livepatch: 'livepatch_callbacks_demo': completing patching transition - [ 75.743219] livepatch_callbacks_demo: post_patch_callback: vmlinux - [ 75.743867] livepatch: 'livepatch_callbacks_demo': patching complete - -As expected, only pre/post-(un)patch handlers are executed for vmlinux: - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 76.716254] livepatch: 'livepatch_callbacks_demo': initializing unpatching transition - [ 76.716278] livepatch_callbacks_demo: pre_unpatch_callback: vmlinux - [ 76.716666] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 77.727089] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 77.727194] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 77.727907] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - - -Test 6 ------- - -Test a scenario where a vmlinux pre-patch callback returns a non-zero -status (ie, failure): - -- load target module -- load livepatch -ENODEV -- unload target module - -First load a target module: - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 80.740520] livepatch_callbacks_mod: livepatch_callbacks_mod_init - -Load the livepatch module, setting its 'pre_patch_ret' value to -19 -(-ENODEV). When its vmlinux pre-patch callback executed, this status -code will propagate back to the module-loading subsystem. The result is -that the insmod command refuses to load the livepatch module: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko pre_patch_ret=-19 - [ 82.747326] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 82.747743] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 82.747767] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 82.748237] livepatch: pre-patch callback failed for object 'vmlinux' - [ 82.748637] livepatch: failed to enable patch 'livepatch_callbacks_demo' - [ 82.749059] livepatch: 'livepatch_callbacks_demo': canceling transition, going to unpatch - [ 82.749060] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 82.749868] livepatch: 'livepatch_callbacks_demo': unpatching complete - [ 82.765809] insmod: ERROR: could not insert module samples/livepatch/livepatch-callbacks-demo.ko: No such device - - % rmmod samples/livepatch/livepatch-callbacks-mod.ko - [ 84.774238] livepatch_callbacks_mod: livepatch_callbacks_mod_exit - - -Test 7 ------- - -Similar to the previous test, setup a livepatch such that its vmlinux -pre-patch callback returns success. However, when a targeted kernel -module is later loaded, have the livepatch return a failing status code: - -- load livepatch -- setup -ENODEV -- load target module -- disable livepatch -- unload livepatch - -Load the livepatch, notice vmlinux pre-patch callback succeeds: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 86.787845] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 86.788325] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 86.788427] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 86.788821] livepatch: 'livepatch_callbacks_demo': starting patching transition - [ 87.711069] livepatch: 'livepatch_callbacks_demo': completing patching transition - [ 87.711143] livepatch_callbacks_demo: post_patch_callback: vmlinux - [ 87.711886] livepatch: 'livepatch_callbacks_demo': patching complete - -Set a trap so subsequent pre-patch callbacks to this livepatch will -return -ENODEV: - - % echo -19 > /sys/module/livepatch_callbacks_demo/parameters/pre_patch_ret - -The livepatch pre-patch callback for subsequently loaded target modules -will return failure, so the module loader refuses to load the kernel -module. Notice that no post-patch or pre/post-unpatch callbacks are -executed for this klp_object: - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 90.796976] livepatch: applying patch 'livepatch_callbacks_demo' to loading module 'livepatch_callbacks_mod' - [ 90.797834] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 90.798900] livepatch: pre-patch callback failed for object 'livepatch_callbacks_mod' - [ 90.799652] livepatch: patch 'livepatch_callbacks_demo' failed for module 'livepatch_callbacks_mod', refusing to load module 'livepatch_callbacks_mod' - [ 90.819737] insmod: ERROR: could not insert module samples/livepatch/livepatch-callbacks-mod.ko: No such device - -However, pre/post-unpatch callbacks run for the vmlinux klp_object: - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 92.823547] livepatch: 'livepatch_callbacks_demo': initializing unpatching transition - [ 92.823573] livepatch_callbacks_demo: pre_unpatch_callback: vmlinux - [ 92.824331] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 93.727128] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 93.727327] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 93.727861] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - - -Test 8 ------- - -Test loading multiple targeted kernel modules. This test-case is -mainly for comparing with the next test-case. - -- load busy target module (0s sleep), -- load livepatch -- load target module -- unload target module -- disable livepatch -- unload livepatch -- unload busy target module - - -Load a target "busy" kernel module which kicks off a worker function -that immediately exits: - - % insmod samples/livepatch/livepatch-callbacks-busymod.ko sleep_secs=0 - [ 96.910107] livepatch_callbacks_busymod: livepatch_callbacks_mod_init - [ 96.910600] livepatch_callbacks_busymod: busymod_work_func, sleeping 0 seconds ... - [ 96.913024] livepatch_callbacks_busymod: busymod_work_func exit - -Proceed with loading the livepatch and another ordinary target module, -notice that the post-patch callbacks are executed and the transition -completes quickly: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 98.917892] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 98.918426] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 98.918453] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 98.918955] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_busymod -> [MODULE_STATE_LIVE] Normal state - [ 98.923835] livepatch: 'livepatch_callbacks_demo': starting patching transition - [ 99.743104] livepatch: 'livepatch_callbacks_demo': completing patching transition - [ 99.743156] livepatch_callbacks_demo: post_patch_callback: vmlinux - [ 99.743679] livepatch_callbacks_demo: post_patch_callback: livepatch_callbacks_busymod -> [MODULE_STATE_LIVE] Normal state - [ 99.744616] livepatch: 'livepatch_callbacks_demo': patching complete - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 100.930955] livepatch: applying patch 'livepatch_callbacks_demo' to loading module 'livepatch_callbacks_mod' - [ 100.931668] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 100.932645] livepatch_callbacks_demo: post_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 100.934125] livepatch_callbacks_mod: livepatch_callbacks_mod_init - - % rmmod samples/livepatch/livepatch-callbacks-mod.ko - [ 102.942805] livepatch_callbacks_mod: livepatch_callbacks_mod_exit - [ 102.943640] livepatch_callbacks_demo: pre_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_GOING] Going away - [ 102.944585] livepatch: reverting patch 'livepatch_callbacks_demo' on unloading module 'livepatch_callbacks_mod' - [ 102.945455] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_GOING] Going away - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 104.953815] livepatch: 'livepatch_callbacks_demo': initializing unpatching transition - [ 104.953838] livepatch_callbacks_demo: pre_unpatch_callback: vmlinux - [ 104.954431] livepatch_callbacks_demo: pre_unpatch_callback: livepatch_callbacks_busymod -> [MODULE_STATE_LIVE] Normal state - [ 104.955426] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 106.719073] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 106.722633] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 106.723282] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_busymod -> [MODULE_STATE_LIVE] Normal state - [ 106.724279] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - % rmmod samples/livepatch/livepatch-callbacks-busymod.ko - [ 108.975660] livepatch_callbacks_busymod: livepatch_callbacks_mod_exit - - -Test 9 ------- - -A similar test as the previous one, but force the "busy" kernel module -to do longer work. - -The livepatching core will refuse to patch a task that is currently -executing a to-be-patched function -- the consistency model stalls the -current patch transition until this safety-check is met. Test a -scenario where one of a livepatch's target klp_objects sits on such a -function for a long time. Meanwhile, load and unload other target -kernel modules while the livepatch transition is in progress. - -- load busy target module (30s sleep) -- load livepatch -- load target module -- unload target module -- disable livepatch -- unload livepatch -- unload busy target module - - -Load the "busy" kernel module, this time make it do 30 seconds worth of -work: - - % insmod samples/livepatch/livepatch-callbacks-busymod.ko sleep_secs=30 - [ 110.993362] livepatch_callbacks_busymod: livepatch_callbacks_mod_init - [ 110.994059] livepatch_callbacks_busymod: busymod_work_func, sleeping 30 seconds ... - -Meanwhile, the livepatch is loaded. Notice that the patch transition -does not complete as the targeted "busy" module is sitting on a -to-be-patched function: - - % insmod samples/livepatch/livepatch-callbacks-demo.ko - [ 113.000309] livepatch: enabling patch 'livepatch_callbacks_demo' - [ 113.000764] livepatch: 'livepatch_callbacks_demo': initializing patching transition - [ 113.000791] livepatch_callbacks_demo: pre_patch_callback: vmlinux - [ 113.001289] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_busymod -> [MODULE_STATE_LIVE] Normal state - [ 113.005208] livepatch: 'livepatch_callbacks_demo': starting patching transition - -Load a second target module (this one is an ordinary idle kernel -module). Note that *no* post-patch callbacks will be executed while the -livepatch is still in transition: - - % insmod samples/livepatch/livepatch-callbacks-mod.ko - [ 115.012740] livepatch: applying patch 'livepatch_callbacks_demo' to loading module 'livepatch_callbacks_mod' - [ 115.013406] livepatch_callbacks_demo: pre_patch_callback: livepatch_callbacks_mod -> [MODULE_STATE_COMING] Full formed, running module_init - [ 115.015315] livepatch_callbacks_mod: livepatch_callbacks_mod_init - -Request an unload of the simple kernel module. The patch is still -transitioning, so its pre-unpatch callbacks are skipped: - - % rmmod samples/livepatch/livepatch-callbacks-mod.ko - [ 117.022626] livepatch_callbacks_mod: livepatch_callbacks_mod_exit - [ 117.023376] livepatch: reverting patch 'livepatch_callbacks_demo' on unloading module 'livepatch_callbacks_mod' - [ 117.024533] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_mod -> [MODULE_STATE_GOING] Going away - -Finally the livepatch is disabled. Since none of the patch's -klp_object's post-patch callbacks executed, the remaining klp_object's -pre-unpatch callbacks are skipped: - - % echo 0 > /sys/kernel/livepatch/livepatch_callbacks_demo/enabled - [ 119.035408] livepatch: 'livepatch_callbacks_demo': reversing transition from patching to unpatching - [ 119.035485] livepatch: 'livepatch_callbacks_demo': starting unpatching transition - [ 119.711166] livepatch: 'livepatch_callbacks_demo': completing unpatching transition - [ 119.714179] livepatch_callbacks_demo: post_unpatch_callback: vmlinux - [ 119.714653] livepatch_callbacks_demo: post_unpatch_callback: livepatch_callbacks_busymod -> [MODULE_STATE_LIVE] Normal state - [ 119.715437] livepatch: 'livepatch_callbacks_demo': unpatching complete - - % rmmod samples/livepatch/livepatch-callbacks-demo.ko - % rmmod samples/livepatch/livepatch-callbacks-busymod.ko - [ 141.279111] livepatch_callbacks_busymod: busymod_work_func exit - [ 141.279760] livepatch_callbacks_busymod: livepatch_callbacks_mod_exit diff --git a/Documentation/livepatch/cumulative-patches.rst b/Documentation/livepatch/cumulative-patches.rst new file mode 100644 index 000000000000..1931f318976a --- /dev/null +++ b/Documentation/livepatch/cumulative-patches.rst @@ -0,0 +1,102 @@ +=================================== +Atomic Replace & Cumulative Patches +=================================== + +There might be dependencies between livepatches. If multiple patches need +to do different changes to the same function(s) then we need to define +an order in which the patches will be installed. And function implementations +from any newer livepatch must be done on top of the older ones. + +This might become a maintenance nightmare. Especially when more patches +modified the same function in different ways. + +An elegant solution comes with the feature called "Atomic Replace". It allows +creation of so called "Cumulative Patches". They include all wanted changes +from all older livepatches and completely replace them in one transition. + +Usage +----- + +The atomic replace can be enabled by setting "replace" flag in struct klp_patch, +for example:: + + static struct klp_patch patch = { + .mod = THIS_MODULE, + .objs = objs, + .replace = true, + }; + +All processes are then migrated to use the code only from the new patch. +Once the transition is finished, all older patches are automatically +disabled. + +Ftrace handlers are transparently removed from functions that are no +longer modified by the new cumulative patch. + +As a result, the livepatch authors might maintain sources only for one +cumulative patch. It helps to keep the patch consistent while adding or +removing various fixes or features. + +Users could keep only the last patch installed on the system after +the transition to has finished. It helps to clearly see what code is +actually in use. Also the livepatch might then be seen as a "normal" +module that modifies the kernel behavior. The only difference is that +it can be updated at runtime without breaking its functionality. + + +Features +-------- + +The atomic replace allows: + + - Atomically revert some functions in a previous patch while + upgrading other functions. + + - Remove eventual performance impact caused by core redirection + for functions that are no longer patched. + + - Decrease user confusion about dependencies between livepatches. + + +Limitations: +------------ + + - Once the operation finishes, there is no straightforward way + to reverse it and restore the replaced patches atomically. + + A good practice is to set .replace flag in any released livepatch. + Then re-adding an older livepatch is equivalent to downgrading + to that patch. This is safe as long as the livepatches do _not_ do + extra modifications in (un)patching callbacks or in the module_init() + or module_exit() functions, see below. + + Also note that the replaced patch can be removed and loaded again + only when the transition was not forced. + + + - Only the (un)patching callbacks from the _new_ cumulative livepatch are + executed. Any callbacks from the replaced patches are ignored. + + In other words, the cumulative patch is responsible for doing any actions + that are necessary to properly replace any older patch. + + As a result, it might be dangerous to replace newer cumulative patches by + older ones. The old livepatches might not provide the necessary callbacks. + + This might be seen as a limitation in some scenarios. But it makes life + easier in many others. Only the new cumulative livepatch knows what + fixes/features are added/removed and what special actions are necessary + for a smooth transition. + + In any case, it would be a nightmare to think about the order of + the various callbacks and their interactions if the callbacks from all + enabled patches were called. + + + - There is no special handling of shadow variables. Livepatch authors + must create their own rules how to pass them from one cumulative + patch to the other. Especially that they should not blindly remove + them in module_exit() functions. + + A good practice might be to remove shadow variables in the post-unpatch + callback. It is called only when the livepatch is properly disabled. diff --git a/Documentation/livepatch/index.rst b/Documentation/livepatch/index.rst new file mode 100644 index 000000000000..edd291d51847 --- /dev/null +++ b/Documentation/livepatch/index.rst @@ -0,0 +1,21 @@ +:orphan: + +=================== +Kernel Livepatching +=================== + +.. toctree:: + :maxdepth: 1 + + livepatch + callbacks + cumulative-patches + module-elf-format + shadow-vars + +.. only:: subproject and html + + Indices + ======= + + * :ref:`genindex` diff --git a/Documentation/livepatch/livepatch.txt b/Documentation/livepatch/livepatch.rst index 2d7ed09dbd59..c2c598c4ead8 100644 --- a/Documentation/livepatch/livepatch.txt +++ b/Documentation/livepatch/livepatch.rst @@ -4,22 +4,22 @@ Livepatch This document outlines basic information about kernel livepatching. -Table of Contents: - -1. Motivation -2. Kprobes, Ftrace, Livepatching -3. Consistency model -4. Livepatch module - 4.1. New functions - 4.2. Metadata - 4.3. Livepatch module handling -5. Livepatch life-cycle - 5.1. Registration - 5.2. Enabling - 5.3. Disabling - 5.4. Unregistration -6. Sysfs -7. Limitations +.. Table of Contents: + + 1. Motivation + 2. Kprobes, Ftrace, Livepatching + 3. Consistency model + 4. Livepatch module + 4.1. New functions + 4.2. Metadata + 5. Livepatch life-cycle + 5.1. Loading + 5.2. Enabling + 5.3. Replacing + 5.4. Disabling + 5.5. Removing + 6. Sysfs + 7. Limitations 1. Motivation @@ -40,14 +40,14 @@ There are multiple mechanisms in the Linux kernel that are directly related to redirection of code execution; namely: kernel probes, function tracing, and livepatching: - + The kernel probes are the most generic. The code can be redirected by + - The kernel probes are the most generic. The code can be redirected by putting a breakpoint instruction instead of any instruction. - + The function tracer calls the code from a predefined location that is + - The function tracer calls the code from a predefined location that is close to the function entry point. This location is generated by the compiler using the '-pg' gcc option. - + Livepatching typically needs to redirect the code at the very beginning + - Livepatching typically needs to redirect the code at the very beginning of the function entry before the function parameters or the stack are in any way modified. @@ -143,9 +143,9 @@ without HAVE_RELIABLE_STACKTRACE are not considered fully supported by the kernel livepatching. The /sys/kernel/livepatch/<patch>/transition file shows whether a patch -is in transition. Only a single patch (the topmost patch on the stack) -can be in transition at a given time. A patch can remain in transition -indefinitely, if any of the tasks are stuck in the initial patch state. +is in transition. Only a single patch can be in transition at a given +time. A patch can remain in transition indefinitely, if any of the tasks +are stuck in the initial patch state. A transition can be reversed and effectively canceled by writing the opposite value to the /sys/kernel/livepatch/<patch>/enabled file while @@ -158,12 +158,11 @@ If a patch is in transition, this file shows 0 to indicate the task is unpatched and 1 to indicate it's patched. Otherwise, if no patch is in transition, it shows -1. Any tasks which are blocking the transition can be signaled with SIGSTOP and SIGCONT to force them to change their -patched state. This may be harmful to the system though. -/sys/kernel/livepatch/<patch>/signal attribute provides a better alternative. -Writing 1 to the attribute sends a fake signal to all remaining blocking -tasks. No proper signal is actually delivered (there is no data in signal -pending structures). Tasks are interrupted or woken up, and forced to change -their patched state. +patched state. This may be harmful to the system though. Sending a fake signal +to all remaining blocking tasks is a better alternative. No proper signal is +actually delivered (there is no data in signal pending structures). Tasks are +interrupted or woken up, and forced to change their patched state. The fake +signal is automatically sent every 15 seconds. Administrator can also affect a transition through /sys/kernel/livepatch/<patch>/force attribute. Writing 1 there clears @@ -250,7 +249,7 @@ The patch contains only functions that are really modified. But they might want to access functions or data from the original source file that may only be locally accessible. This can be solved by a special relocation section in the generated livepatch module, see -Documentation/livepatch/module-elf-format.txt for more details. +Documentation/livepatch/module-elf-format.rst for more details. 4.2. Metadata @@ -259,7 +258,7 @@ Documentation/livepatch/module-elf-format.txt for more details. The patch is described by several structures that split the information into three levels: - + struct klp_func is defined for each patched function. It describes + - struct klp_func is defined for each patched function. It describes the relation between the original and the new implementation of a particular function. @@ -276,7 +275,7 @@ into three levels: only for a particular object ( vmlinux or a kernel module ). Note that kallsyms allows for searching symbols according to the object name. - + struct klp_object defines an array of patched functions (struct + - struct klp_object defines an array of patched functions (struct klp_func) in the same object. Where the object is either vmlinux (NULL) or a module name. @@ -286,7 +285,7 @@ into three levels: only when they are available. - + struct klp_patch defines an array of patched objects (struct + - struct klp_patch defines an array of patched objects (struct klp_object). This structure handles all patched functions consistently and eventually, @@ -298,117 +297,112 @@ into three levels: see the "Consistency model" section. -4.3. Livepatch module handling ------------------------------- - -The usual behavior is that the new functions will get used when -the livepatch module is loaded. For this, the module init() function -has to register the patch (struct klp_patch) and enable it. See the -section "Livepatch life-cycle" below for more details about these -two operations. - -Module removal is only safe when there are no users of the underlying -functions. This is the reason why the force feature permanently disables -the removal. The forced tasks entered the functions but we cannot say -that they returned back. Therefore it cannot be decided when the -livepatch module can be safely removed. When the system is successfully -transitioned to a new patch state (patched/unpatched) without being -forced it is guaranteed that no task sleeps or runs in the old code. - - 5. Livepatch life-cycle ======================= -Livepatching defines four basic operations that define the life cycle of each -live patch: registration, enabling, disabling and unregistration. There are -several reasons why it is done this way. +Livepatching can be described by five basic operations: +loading, enabling, replacing, disabling, removing. -First, the patch is applied only when all patched symbols for already -loaded objects are found. The error handling is much easier if this -check is done before particular functions get redirected. +Where the replacing and the disabling operations are mutually +exclusive. They have the same result for the given patch but +not for the system. -Second, it might take some time until the entire system is migrated with -the hybrid consistency model being used. The patch revert might block -the livepatch module removal for too long. Therefore it is useful to -revert the patch using a separate operation that might be called -explicitly. But it does not make sense to remove all information until -the livepatch module is really removed. +5.1. Loading +------------ -5.1. Registration ------------------ +The only reasonable way is to enable the patch when the livepatch kernel +module is being loaded. For this, klp_enable_patch() has to be called +in the module_init() callback. There are two main reasons: -Each patch first has to be registered using klp_register_patch(). This makes -the patch known to the livepatch framework. Also it does some preliminary -computing and checks. +First, only the module has an easy access to the related struct klp_patch. -In particular, the patch is added into the list of known patches. The -addresses of the patched functions are found according to their names. -The special relocations, mentioned in the section "New functions", are -applied. The relevant entries are created under -/sys/kernel/livepatch/<name>. The patch is rejected when any operation -fails. +Second, the error code might be used to refuse loading the module when +the patch cannot get enabled. 5.2. Enabling ------------- -Registered patches might be enabled either by calling klp_enable_patch() or -by writing '1' to /sys/kernel/livepatch/<name>/enabled. The system will -start using the new implementation of the patched functions at this stage. +The livepatch gets enabled by calling klp_enable_patch() from +the module_init() callback. The system will start using the new +implementation of the patched functions at this stage. + +First, the addresses of the patched functions are found according to their +names. The special relocations, mentioned in the section "New functions", +are applied. The relevant entries are created under +/sys/kernel/livepatch/<name>. The patch is rejected when any above +operation fails. + +Second, livepatch enters into a transition state where tasks are converging +to the patched state. If an original function is patched for the first +time, a function specific struct klp_ops is created and an universal +ftrace handler is registered\ [#]_. This stage is indicated by a value of '1' +in /sys/kernel/livepatch/<name>/transition. For more information about +this process, see the "Consistency model" section. -When a patch is enabled, livepatch enters into a transition state where -tasks are converging to the patched state. This is indicated by a value -of '1' in /sys/kernel/livepatch/<name>/transition. Once all tasks have -been patched, the 'transition' value changes to '0'. For more -information about this process, see the "Consistency model" section. +Finally, once all tasks have been patched, the 'transition' value changes +to '0'. -If an original function is patched for the first time, a function -specific struct klp_ops is created and an universal ftrace handler is -registered. +.. [#] -Functions might be patched multiple times. The ftrace handler is registered -only once for the given function. Further patches just add an entry to the -list (see field `func_stack`) of the struct klp_ops. The last added -entry is chosen by the ftrace handler and becomes the active function -replacement. + Note that functions might be patched multiple times. The ftrace handler + is registered only once for a given function. Further patches just add + an entry to the list (see field `func_stack`) of the struct klp_ops. + The right implementation is selected by the ftrace handler, see + the "Consistency model" section. -Note that the patches might be enabled in a different order than they were -registered. + That said, it is highly recommended to use cumulative livepatches + because they help keeping the consistency of all changes. In this case, + functions might be patched two times only during the transition period. -5.3. Disabling +5.3. Replacing -------------- -Enabled patches might get disabled either by calling klp_disable_patch() or -by writing '0' to /sys/kernel/livepatch/<name>/enabled. At this stage -either the code from the previously enabled patch or even the original -code gets used. +All enabled patches might get replaced by a cumulative patch that +has the .replace flag set. -When a patch is disabled, livepatch enters into a transition state where -tasks are converging to the unpatched state. This is indicated by a -value of '1' in /sys/kernel/livepatch/<name>/transition. Once all tasks -have been unpatched, the 'transition' value changes to '0'. For more -information about this process, see the "Consistency model" section. +Once the new patch is enabled and the 'transition' finishes then +all the functions (struct klp_func) associated with the replaced +patches are removed from the corresponding struct klp_ops. Also +the ftrace handler is unregistered and the struct klp_ops is +freed when the related function is not modified by the new patch +and func_stack list becomes empty. -Here all the functions (struct klp_func) associated with the to-be-disabled +See Documentation/livepatch/cumulative-patches.rst for more details. + + +5.4. Disabling +-------------- + +Enabled patches might get disabled by writing '0' to +/sys/kernel/livepatch/<name>/enabled. + +First, livepatch enters into a transition state where tasks are converging +to the unpatched state. The system starts using either the code from +the previously enabled patch or even the original one. This stage is +indicated by a value of '1' in /sys/kernel/livepatch/<name>/transition. +For more information about this process, see the "Consistency model" +section. + +Second, once all tasks have been unpatched, the 'transition' value changes +to '0'. All the functions (struct klp_func) associated with the to-be-disabled patch are removed from the corresponding struct klp_ops. The ftrace handler is unregistered and the struct klp_ops is freed when the func_stack list becomes empty. -Patches must be disabled in exactly the reverse order in which they were -enabled. It makes the problem and the implementation much easier. +Third, the sysfs interface is destroyed. -5.4. Unregistration -------------------- - -Disabled patches might be unregistered by calling klp_unregister_patch(). -This can be done only when the patch is disabled and the code is no longer -used. It must be called before the livepatch module gets unloaded. +5.5. Removing +------------- -At this stage, all the relevant sys-fs entries are removed and the patch -is removed from the list of known patches. +Module removal is only safe when there are no users of functions provided +by the module. This is the reason why the force feature permanently +disables the removal. Only when the system is successfully transitioned +to a new patch state (patched/unpatched) without being forced it is +guaranteed that no task sleeps or runs in the old code. 6. Sysfs @@ -418,8 +412,8 @@ Information about the registered patches can be found under /sys/kernel/livepatch. The patches could be enabled and disabled by writing there. -/sys/kernel/livepatch/<patch>/signal and /sys/kernel/livepatch/<patch>/force -attributes allow administrator to affect a patching operation. +/sys/kernel/livepatch/<patch>/force attributes allow administrator to affect a +patching operation. See Documentation/ABI/testing/sysfs-kernel-livepatch for more details. @@ -429,7 +423,7 @@ See Documentation/ABI/testing/sysfs-kernel-livepatch for more details. The current Livepatch implementation has several limitations: - + Only functions that can be traced could be patched. + - Only functions that can be traced could be patched. Livepatch is based on the dynamic ftrace. In particular, functions implementing ftrace or the livepatch ftrace handler could not be @@ -439,7 +433,7 @@ The current Livepatch implementation has several limitations: - + Livepatch works reliably only when the dynamic ftrace is located at + - Livepatch works reliably only when the dynamic ftrace is located at the very beginning of the function. The function need to be redirected before the stack or the function @@ -453,7 +447,7 @@ The current Livepatch implementation has several limitations: this is handled on the ftrace level. - + Kretprobes using the ftrace framework conflict with the patched + - Kretprobes using the ftrace framework conflict with the patched functions. Both kretprobes and livepatches use a ftrace handler that modifies @@ -461,7 +455,7 @@ The current Livepatch implementation has several limitations: is rejected when the handler is already in use by the other. - + Kprobes in the original function are ignored when the code is + - Kprobes in the original function are ignored when the code is redirected to the new implementation. There is a work in progress to add warnings about this situation. diff --git a/Documentation/livepatch/module-elf-format.txt b/Documentation/livepatch/module-elf-format.rst index f21a5289a09c..2a591e6f8e6c 100644 --- a/Documentation/livepatch/module-elf-format.txt +++ b/Documentation/livepatch/module-elf-format.rst @@ -4,33 +4,21 @@ Livepatch module Elf format This document outlines the Elf format requirements that livepatch modules must follow. ------------------ -Table of Contents ------------------ -0. Background and motivation -1. Livepatch modinfo field -2. Livepatch relocation sections - 2.1 What are livepatch relocation sections? - 2.2 Livepatch relocation section format - 2.2.1 Required flags - 2.2.2 Required name format - 2.2.3 Example livepatch relocation section names - 2.2.4 Example `readelf --sections` output - 2.2.5 Example `readelf --relocs` output -3. Livepatch symbols - 3.1 What are livepatch symbols? - 3.2 A livepatch module's symbol table - 3.3 Livepatch symbol format - 3.3.1 Required flags - 3.3.2 Required name format - 3.3.3 Example livepatch symbol names - 3.3.4 Example `readelf --symbols` output -4. Architecture-specific sections -5. Symbol table and Elf section access - ----------------------------- -0. Background and motivation ----------------------------- + +.. Table of Contents + + 1. Background and motivation + 2. Livepatch modinfo field + 3. Livepatch relocation sections + 3.1 Livepatch relocation section format + 4. Livepatch symbols + 4.1 A livepatch module's symbol table + 4.2 Livepatch symbol format + 5. Architecture-specific sections + 6. Symbol table and Elf section access + +1. Background and motivation +============================ Formerly, livepatch required separate architecture-specific code to write relocations. However, arch-specific code to write relocations already @@ -52,8 +40,8 @@ relocation sections and symbols, which are described in this document. The Elf constants used to mark livepatch symbols and relocation sections were selected from OS-specific ranges according to the definitions from glibc. -0.1 Why does livepatch need to write its own relocations? ---------------------------------------------------------- +Why does livepatch need to write its own relocations? +----------------------------------------------------- A typical livepatch module contains patched versions of functions that can reference non-exported global symbols and non-included local symbols. Relocations referencing these types of symbols cannot be left in as-is @@ -72,13 +60,8 @@ relas reference are special livepatch symbols (see section 2 and 3). The arch-specific livepatch relocation code is replaced by a call to apply_relocate_add(). -================================ -PATCH MODULE FORMAT REQUIREMENTS -================================ - --------------------------- -1. Livepatch modinfo field --------------------------- +2. Livepatch modinfo field +========================== Livepatch modules are required to have the "livepatch" modinfo attribute. See the sample livepatch module in samples/livepatch/ for how this is done. @@ -87,22 +70,23 @@ Livepatch modules can be identified by users by using the 'modinfo' command and looking for the presence of the "livepatch" field. This field is also used by the kernel module loader to identify livepatch modules. -Example modinfo output: ------------------------ -% modinfo livepatch-meminfo.ko -filename: livepatch-meminfo.ko -livepatch: Y -license: GPL -depends: -vermagic: 4.3.0+ SMP mod_unload - --------------------------------- -2. Livepatch relocation sections --------------------------------- - -------------------------------------------- -2.1 What are livepatch relocation sections? -------------------------------------------- +Example: +-------- + +**Modinfo output:** + +:: + + % modinfo livepatch-meminfo.ko + filename: livepatch-meminfo.ko + livepatch: Y + license: GPL + depends: + vermagic: 4.3.0+ SMP mod_unload + +3. Livepatch relocation sections +================================ + A livepatch module manages its own Elf relocation sections to apply relocations to modules as well as to the kernel (vmlinux) at the appropriate time. For example, if a patch module patches a driver that is @@ -127,12 +111,9 @@ Every symbol referenced by a rela in a livepatch relocation section is a livepatch symbol. These must be resolved before livepatch can call apply_relocate_add(). See Section 3 for more information. ---------------------------------------- -2.2 Livepatch relocation section format ---------------------------------------- +3.1 Livepatch relocation section format +======================================= -2.2.1 Required flags --------------------- Livepatch relocation sections must be marked with the SHF_RELA_LIVEPATCH section flag. See include/uapi/linux/elf.h for the definition. The module loader recognizes this flag and will avoid applying those relocation sections @@ -140,28 +121,39 @@ at patch module load time. These sections must also be marked with SHF_ALLOC, so that the module loader doesn't discard them on module load (i.e. they will be copied into memory along with the other SHF_ALLOC sections). -2.2.2 Required name format --------------------------- -The name of a livepatch relocation section must conform to the following format: +The name of a livepatch relocation section must conform to the following +format:: -.klp.rela.objname.section_name -^ ^^ ^ ^ ^ -|________||_____| |__________| - [A] [B] [C] + .klp.rela.objname.section_name + ^ ^^ ^ ^ ^ + |________||_____| |__________| + [A] [B] [C] -[A] The relocation section name is prefixed with the string ".klp.rela." -[B] The name of the object (i.e. "vmlinux" or name of module) to - which the relocation section belongs follows immediately after the prefix. -[C] The actual name of the section to which this relocation section applies. +[A] + The relocation section name is prefixed with the string ".klp.rela." -2.2.3 Example livepatch relocation section names: -------------------------------------------------- -.klp.rela.ext4.text.ext4_attr_store -.klp.rela.vmlinux.text.cmdline_proc_show +[B] + The name of the object (i.e. "vmlinux" or name of module) to + which the relocation section belongs follows immediately after the prefix. + +[C] + The actual name of the section to which this relocation section applies. + +Examples: +--------- + +**Livepatch relocation section names:** + +:: + + .klp.rela.ext4.text.ext4_attr_store + .klp.rela.vmlinux.text.cmdline_proc_show + +**`readelf --sections` output for a patch +module that patches vmlinux and modules 9p, btrfs, ext4:** + +:: -2.2.4 Example `readelf --sections` output for a patch -module that patches vmlinux and modules 9p, btrfs, ext4: --------------------------------------------------------- Section Headers: [Nr] Name Type Address Off Size ES Flg Lk Inf Al [ snip ] @@ -175,31 +167,33 @@ module that patches vmlinux and modules 9p, btrfs, ext4: [ snip ] ^ ^ | | [*] [*] -[*] Livepatch relocation sections are SHT_RELA sections but with a few special -characteristics. Notice that they are marked SHF_ALLOC ("A") so that they will -not be discarded when the module is loaded into memory, as well as with the -SHF_RELA_LIVEPATCH flag ("o" - for OS-specific). - -2.2.5 Example `readelf --relocs` output for a patch module: ------------------------------------------------------------ -Relocation section '.klp.rela.btrfs.text.btrfs_feature_attr_show' at offset 0x2ba0 contains 4 entries: - Offset Info Type Symbol's Value Symbol's Name + Addend -000000000000001f 0000005e00000002 R_X86_64_PC32 0000000000000000 .klp.sym.vmlinux.printk,0 - 4 -0000000000000028 0000003d0000000b R_X86_64_32S 0000000000000000 .klp.sym.btrfs.btrfs_ktype,0 + 0 -0000000000000036 0000003b00000002 R_X86_64_PC32 0000000000000000 .klp.sym.btrfs.can_modify_feature.isra.3,0 - 4 -000000000000004c 0000004900000002 R_X86_64_PC32 0000000000000000 .klp.sym.vmlinux.snprintf,0 - 4 -[ snip ] ^ - | - [*] -[*] Every symbol referenced by a relocation is a livepatch symbol. - --------------------- -3. Livepatch symbols --------------------- - -------------------------------- -3.1 What are livepatch symbols? -------------------------------- + +[*] + Livepatch relocation sections are SHT_RELA sections but with a few special + characteristics. Notice that they are marked SHF_ALLOC ("A") so that they will + not be discarded when the module is loaded into memory, as well as with the + SHF_RELA_LIVEPATCH flag ("o" - for OS-specific). + +**`readelf --relocs` output for a patch module:** + +:: + + Relocation section '.klp.rela.btrfs.text.btrfs_feature_attr_show' at offset 0x2ba0 contains 4 entries: + Offset Info Type Symbol's Value Symbol's Name + Addend + 000000000000001f 0000005e00000002 R_X86_64_PC32 0000000000000000 .klp.sym.vmlinux.printk,0 - 4 + 0000000000000028 0000003d0000000b R_X86_64_32S 0000000000000000 .klp.sym.btrfs.btrfs_ktype,0 + 0 + 0000000000000036 0000003b00000002 R_X86_64_PC32 0000000000000000 .klp.sym.btrfs.can_modify_feature.isra.3,0 - 4 + 000000000000004c 0000004900000002 R_X86_64_PC32 0000000000000000 .klp.sym.vmlinux.snprintf,0 - 4 + [ snip ] ^ + | + [*] + +[*] + Every symbol referenced by a relocation is a livepatch symbol. + +4. Livepatch symbols +==================== + Livepatch symbols are symbols referred to by livepatch relocation sections. These are symbols accessed from new versions of functions for patched objects, whose addresses cannot be resolved by the module loader (because @@ -219,9 +213,8 @@ loader can identify and ignore them. Livepatch modules keep these symbols in their symbol tables, and the symbol table is made accessible through module->symtab. -------------------------------------- -3.2 A livepatch module's symbol table -------------------------------------- +4.1 A livepatch module's symbol table +===================================== Normally, a stripped down copy of a module's symbol table (containing only "core" symbols) is made available through module->symtab (See layout_symtab() in kernel/module.c). For livepatch modules, the symbol table copied into memory @@ -231,71 +224,82 @@ relocation section refer to their respective symbols with their symbol indices, and the original symbol indices (and thus the symtab ordering) must be preserved in order for apply_relocate_add() to find the right symbol. -For example, take this particular rela from a livepatch module: -Relocation section '.klp.rela.btrfs.text.btrfs_feature_attr_show' at offset 0x2ba0 contains 4 entries: - Offset Info Type Symbol's Value Symbol's Name + Addend -000000000000001f 0000005e00000002 R_X86_64_PC32 0000000000000000 .klp.sym.vmlinux.printk,0 - 4 - -This rela refers to the symbol '.klp.sym.vmlinux.printk,0', and the symbol index is encoded -in 'Info'. Here its symbol index is 0x5e, which is 94 in decimal, which refers to the -symbol index 94. -And in this patch module's corresponding symbol table, symbol index 94 refers to that very symbol: -[ snip ] -94: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.printk,0 -[ snip ] - ---------------------------- -3.3 Livepatch symbol format ---------------------------- - -3.3.1 Required flags --------------------- +For example, take this particular rela from a livepatch module::: + + Relocation section '.klp.rela.btrfs.text.btrfs_feature_attr_show' at offset 0x2ba0 contains 4 entries: + Offset Info Type Symbol's Value Symbol's Name + Addend + 000000000000001f 0000005e00000002 R_X86_64_PC32 0000000000000000 .klp.sym.vmlinux.printk,0 - 4 + + This rela refers to the symbol '.klp.sym.vmlinux.printk,0', and the symbol index is encoded + in 'Info'. Here its symbol index is 0x5e, which is 94 in decimal, which refers to the + symbol index 94. + And in this patch module's corresponding symbol table, symbol index 94 refers to that very symbol: + [ snip ] + 94: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.printk,0 + [ snip ] + +4.2 Livepatch symbol format +=========================== + Livepatch symbols must have their section index marked as SHN_LIVEPATCH, so that the module loader can identify them and not attempt to resolve them. See include/uapi/linux/elf.h for the actual definitions. -3.3.2 Required name format --------------------------- -Livepatch symbol names must conform to the following format: - -.klp.sym.objname.symbol_name,sympos -^ ^^ ^ ^ ^ ^ -|_______||_____| |_________| | - [A] [B] [C] [D] - -[A] The symbol name is prefixed with the string ".klp.sym." -[B] The name of the object (i.e. "vmlinux" or name of module) to - which the symbol belongs follows immediately after the prefix. -[C] The actual name of the symbol. -[D] The position of the symbol in the object (as according to kallsyms) - This is used to differentiate duplicate symbols within the same - object. The symbol position is expressed numerically (0, 1, 2...). - The symbol position of a unique symbol is 0. - -3.3.3 Example livepatch symbol names: -------------------------------------- -.klp.sym.vmlinux.snprintf,0 -.klp.sym.vmlinux.printk,0 -.klp.sym.btrfs.btrfs_ktype,0 - -3.3.4 Example `readelf --symbols` output for a patch module: ------------------------------------------------------------- -Symbol table '.symtab' contains 127 entries: - Num: Value Size Type Bind Vis Ndx Name - [ snip ] - 73: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.snprintf,0 - 74: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.capable,0 - 75: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.find_next_bit,0 - 76: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.si_swapinfo,0 - [ snip ] ^ - | - [*] -[*] Note that the 'Ndx' (Section index) for these symbols is SHN_LIVEPATCH (0xff20). - "OS" means OS-specific. - ---------------------------------- -4. Architecture-specific sections ---------------------------------- +Livepatch symbol names must conform to the following format:: + + .klp.sym.objname.symbol_name,sympos + ^ ^^ ^ ^ ^ ^ + |_______||_____| |_________| | + [A] [B] [C] [D] + +[A] + The symbol name is prefixed with the string ".klp.sym." + +[B] + The name of the object (i.e. "vmlinux" or name of module) to + which the symbol belongs follows immediately after the prefix. + +[C] + The actual name of the symbol. + +[D] + The position of the symbol in the object (as according to kallsyms) + This is used to differentiate duplicate symbols within the same + object. The symbol position is expressed numerically (0, 1, 2...). + The symbol position of a unique symbol is 0. + +Examples: +--------- + +**Livepatch symbol names:** + +:: + + .klp.sym.vmlinux.snprintf,0 + .klp.sym.vmlinux.printk,0 + .klp.sym.btrfs.btrfs_ktype,0 + +**`readelf --symbols` output for a patch module:** + +:: + + Symbol table '.symtab' contains 127 entries: + Num: Value Size Type Bind Vis Ndx Name + [ snip ] + 73: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.snprintf,0 + 74: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.capable,0 + 75: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.find_next_bit,0 + 76: 0000000000000000 0 NOTYPE GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.si_swapinfo,0 + [ snip ] ^ + | + [*] + +[*] + Note that the 'Ndx' (Section index) for these symbols is SHN_LIVEPATCH (0xff20). + "OS" means OS-specific. + +5. Architecture-specific sections +================================= Architectures may override arch_klp_init_object_loaded() to perform additional arch-specific tasks when a target module loads, such as applying arch-specific sections. On x86 for example, we must apply per-object @@ -304,20 +308,19 @@ These sections must be prefixed with ".klp.arch.$objname." so that they can be easily identified when iterating through a patch module's Elf sections (See arch/x86/kernel/livepatch.c for a complete example). --------------------------------------- -5. Symbol table and Elf section access --------------------------------------- +6. Symbol table and Elf section access +====================================== A livepatch module's symbol table is accessible through module->symtab. Since apply_relocate_add() requires access to a module's section headers, symbol table, and relocation section indices, Elf information is preserved for livepatch modules and is made accessible by the module loader through module->klp_info, which is a klp_modinfo struct. When a livepatch module loads, -this struct is filled in by the module loader. Its fields are documented below: - -struct klp_modinfo { - Elf_Ehdr hdr; /* Elf header */ - Elf_Shdr *sechdrs; /* Section header table */ - char *secstrings; /* String table for the section headers */ - unsigned int symndx; /* The symbol table section index */ -}; +this struct is filled in by the module loader. Its fields are documented below:: + + struct klp_modinfo { + Elf_Ehdr hdr; /* Elf header */ + Elf_Shdr *sechdrs; /* Section header table */ + char *secstrings; /* String table for the section headers */ + unsigned int symndx; /* The symbol table section index */ + }; diff --git a/Documentation/livepatch/shadow-vars.txt b/Documentation/livepatch/shadow-vars.rst index ecc09a7be5dd..c05715aeafa4 100644 --- a/Documentation/livepatch/shadow-vars.txt +++ b/Documentation/livepatch/shadow-vars.rst @@ -27,10 +27,13 @@ A hashtable references all shadow variables. These references are stored and retrieved through a <obj, id> pair. * The klp_shadow variable data structure encapsulates both tracking -meta-data and shadow-data: + meta-data and shadow-data: + - meta-data + - obj - pointer to parent object - id - data identifier + - data[] - storage for shadow data It is important to note that the klp_shadow_alloc() and @@ -47,31 +50,43 @@ to do actions that can be done only once when a new variable is allocated. * klp_shadow_alloc() - allocate and add a new shadow variable - search hashtable for <obj, id> pair + - if exists + - WARN and return NULL + - if <obj, id> doesn't already exist + - allocate a new shadow variable - initialize the variable using a custom constructor and data when provided - add <obj, id> to the global hashtable * klp_shadow_get_or_alloc() - get existing or alloc a new shadow variable - search hashtable for <obj, id> pair + - if exists + - return existing shadow variable + - if <obj, id> doesn't already exist + - allocate a new shadow variable - initialize the variable using a custom constructor and data when provided - add <obj, id> pair to the global hashtable * klp_shadow_free() - detach and free a <obj, id> shadow variable - find and remove a <obj, id> reference from global hashtable + - if found + - call destructor function if defined - free shadow variable * klp_shadow_free_all() - detach and free all <*, id> shadow variables - find and remove any <*, id> references from global hashtable + - if found + - call destructor function if defined - free shadow variable @@ -102,12 +117,12 @@ parent "goes live" (ie, any shadow variable get-API requests are made for this <obj, id> pair.) For commit 1d147bfa6429, when a parent sta_info structure is allocated, -allocate a shadow copy of the ps_lock pointer, then initialize it: +allocate a shadow copy of the ps_lock pointer, then initialize it:: -#define PS_LOCK 1 -struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata, - const u8 *addr, gfp_t gfp) -{ + #define PS_LOCK 1 + struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata, + const u8 *addr, gfp_t gfp) + { struct sta_info *sta; spinlock_t *ps_lock; @@ -123,10 +138,10 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata, ... When requiring a ps_lock, query the shadow variable API to retrieve one -for a specific struct sta_info: +for a specific struct sta_info::: -void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta) -{ + void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta) + { spinlock_t *ps_lock; /* sync with ieee80211_tx_h_unicast_ps_buf */ @@ -136,10 +151,10 @@ void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta) ... When the parent sta_info structure is freed, first free the shadow -variable: +variable:: -void sta_info_free(struct ieee80211_local *local, struct sta_info *sta) -{ + void sta_info_free(struct ieee80211_local *local, struct sta_info *sta) + { klp_shadow_free(sta, PS_LOCK, NULL); kfree(sta); ... @@ -155,19 +170,19 @@ these cases, the klp_shadow_get_or_alloc() call can be used to attach shadow variables to parents already in-flight. For commit 1d147bfa6429, a good spot to allocate a shadow spinlock is -inside ieee80211_sta_ps_deliver_wakeup(): +inside ieee80211_sta_ps_deliver_wakeup():: -int ps_lock_shadow_ctor(void *obj, void *shadow_data, void *ctor_data) -{ + int ps_lock_shadow_ctor(void *obj, void *shadow_data, void *ctor_data) + { spinlock_t *lock = shadow_data; spin_lock_init(lock); return 0; -} + } -#define PS_LOCK 1 -void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta) -{ + #define PS_LOCK 1 + void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta) + { spinlock_t *ps_lock; /* sync with ieee80211_tx_h_unicast_ps_buf */ @@ -200,10 +215,12 @@ suggests how to handle the parent object. ============= * https://github.com/dynup/kpatch -The livepatch implementation is based on the kpatch version of shadow -variables. + + The livepatch implementation is based on the kpatch version of shadow + variables. * http://files.mkgnu.net/files/dynamos/doc/papers/dynamos_eurosys_07.pdf -Dynamic and Adaptive Updates of Non-Quiescent Subsystems in Commodity -Operating System Kernels (Kritis Makris, Kyung Dong Ryu 2007) presented -a datatype update technique called "shadow data structures". + + Dynamic and Adaptive Updates of Non-Quiescent Subsystems in Commodity + Operating System Kernels (Kritis Makris, Kyung Dong Ryu 2007) presented + a datatype update technique called "shadow data structures". |