livepatch: Remove ordering (stacking) of the livepatches
[linux-2.6-block.git] / Documentation / livepatch / livepatch.txt
CommitLineData
5e4e3844
PM
1=========
2Livepatch
3=========
4
5This document outlines basic information about kernel livepatching.
6
7Table of Contents:
8
91. Motivation
102. Kprobes, Ftrace, Livepatching
113. Consistency model
124. Livepatch module
13 4.1. New functions
14 4.2. Metadata
5e4e3844 155. Livepatch life-cycle
958ef1e3 16 5.1. Loading
5e4e3844 17 5.2. Enabling
e1452b60
JB
18 5.3. Replacing
19 5.4. Disabling
20 5.5. Removing
5e4e3844
PM
216. Sysfs
227. Limitations
23
24
251. Motivation
26=============
27
28There are many situations where users are reluctant to reboot a system. It may
29be because their system is performing complex scientific computations or under
30heavy load during peak usage. In addition to keeping systems up and running,
31users want to also have a stable and secure system. Livepatching gives users
32both by allowing for function calls to be redirected; thus, fixing critical
33functions without a system reboot.
34
35
362. Kprobes, Ftrace, Livepatching
37================================
38
39There are multiple mechanisms in the Linux kernel that are directly related
40to redirection of code execution; namely: kernel probes, function tracing,
41and livepatching:
42
43 + The kernel probes are the most generic. The code can be redirected by
44 putting a breakpoint instruction instead of any instruction.
45
46 + The function tracer calls the code from a predefined location that is
47 close to the function entry point. This location is generated by the
48 compiler using the '-pg' gcc option.
49
50 + Livepatching typically needs to redirect the code at the very beginning
51 of the function entry before the function parameters or the stack
52 are in any way modified.
53
54All three approaches need to modify the existing code at runtime. Therefore
55they need to be aware of each other and not step over each other's toes.
56Most of these problems are solved by using the dynamic ftrace framework as
57a base. A Kprobe is registered as a ftrace handler when the function entry
58is probed, see CONFIG_KPROBES_ON_FTRACE. Also an alternative function from
59a live patch is called with the help of a custom ftrace handler. But there are
60some limitations, see below.
61
62
633. Consistency model
64====================
65
66Functions are there for a reason. They take some input parameters, get or
67release locks, read, process, and even write some data in a defined way,
68have return values. In other words, each function has a defined semantic.
69
70Many fixes do not change the semantic of the modified functions. For
71example, they add a NULL pointer or a boundary check, fix a race by adding
72a missing memory barrier, or add some locking around a critical section.
73Most of these changes are self contained and the function presents itself
74the same way to the rest of the system. In this case, the functions might
d0807da7 75be updated independently one by one.
5e4e3844
PM
76
77But there are more complex fixes. For example, a patch might change
78ordering of locking in multiple functions at the same time. Or a patch
79might exchange meaning of some temporary structures and update
80all the relevant functions. In this case, the affected unit
81(thread, whole kernel) need to start using all new versions of
82the functions at the same time. Also the switch must happen only
83when it is safe to do so, e.g. when the affected locks are released
84or no data are stored in the modified structures at the moment.
85
86The theory about how to apply functions a safe way is rather complex.
87The aim is to define a so-called consistency model. It attempts to define
88conditions when the new implementation could be used so that the system
d83a7cb3
JP
89stays consistent.
90
91Livepatch has a consistency model which is a hybrid of kGraft and
92kpatch: it uses kGraft's per-task consistency and syscall barrier
93switching combined with kpatch's stack trace switching. There are also
94a number of fallback options which make it quite flexible.
95
96Patches are applied on a per-task basis, when the task is deemed safe to
97switch over. When a patch is enabled, livepatch enters into a
98transition state where tasks are converging to the patched state.
99Usually this transition state can complete in a few seconds. The same
100sequence occurs when a patch is disabled, except the tasks converge from
101the patched state to the unpatched state.
102
103An interrupt handler inherits the patched state of the task it
104interrupts. The same is true for forked tasks: the child inherits the
105patched state of the parent.
106
107Livepatch uses several complementary approaches to determine when it's
108safe to patch tasks:
109
1101. The first and most effective approach is stack checking of sleeping
111 tasks. If no affected functions are on the stack of a given task,
112 the task is patched. In most cases this will patch most or all of
113 the tasks on the first try. Otherwise it'll keep trying
114 periodically. This option is only available if the architecture has
115 reliable stacks (HAVE_RELIABLE_STACKTRACE).
116
1172. The second approach, if needed, is kernel exit switching. A
118 task is switched when it returns to user space from a system call, a
119 user space IRQ, or a signal. It's useful in the following cases:
120
121 a) Patching I/O-bound user tasks which are sleeping on an affected
122 function. In this case you have to send SIGSTOP and SIGCONT to
123 force it to exit the kernel and be patched.
124 b) Patching CPU-bound user tasks. If the task is highly CPU-bound
125 then it will get patched the next time it gets interrupted by an
126 IRQ.
d83a7cb3
JP
127
1283. For idle "swapper" tasks, since they don't ever exit the kernel, they
129 instead have a klp_update_patch_state() call in the idle loop which
130 allows them to be patched before the CPU enters the idle state.
131
132 (Note there's not yet such an approach for kthreads.)
133
d0807da7
MB
134Architectures which don't have HAVE_RELIABLE_STACKTRACE solely rely on
135the second approach. It's highly likely that some tasks may still be
136running with an old version of the function, until that function
137returns. In this case you would have to signal the tasks. This
138especially applies to kthreads. They may not be woken up and would need
139to be forced. See below for more information.
d83a7cb3 140
d0807da7
MB
141Unless we can come up with another way to patch kthreads, architectures
142without HAVE_RELIABLE_STACKTRACE are not considered fully supported by
143the kernel livepatching.
d83a7cb3
JP
144
145The /sys/kernel/livepatch/<patch>/transition file shows whether a patch
d67a5372
PM
146is in transition. Only a single patch can be in transition at a given
147time. A patch can remain in transition indefinitely, if any of the tasks
148are stuck in the initial patch state.
d83a7cb3
JP
149
150A transition can be reversed and effectively canceled by writing the
151opposite value to the /sys/kernel/livepatch/<patch>/enabled file while
152the transition is in progress. Then all the tasks will attempt to
153converge back to the original patch state.
154
155There's also a /proc/<pid>/patch_state file which can be used to
156determine which tasks are blocking completion of a patching operation.
157If a patch is in transition, this file shows 0 to indicate the task is
158unpatched and 1 to indicate it's patched. Otherwise, if no patch is in
159transition, it shows -1. Any tasks which are blocking the transition
160can be signaled with SIGSTOP and SIGCONT to force them to change their
43347d56
MB
161patched state. This may be harmful to the system though.
162/sys/kernel/livepatch/<patch>/signal attribute provides a better alternative.
163Writing 1 to the attribute sends a fake signal to all remaining blocking
164tasks. No proper signal is actually delivered (there is no data in signal
165pending structures). Tasks are interrupted or woken up, and forced to change
166their patched state.
d83a7cb3 167
c99a2be7
MB
168Administrator can also affect a transition through
169/sys/kernel/livepatch/<patch>/force attribute. Writing 1 there clears
170TIF_PATCH_PENDING flag of all tasks and thus forces the tasks to the patched
171state. Important note! The force attribute is intended for cases when the
172transition gets stuck for a long time because of a blocking task. Administrator
173is expected to collect all necessary data (namely stack traces of such blocking
174tasks) and request a clearance from a patch distributor to force the transition.
175Unauthorized usage may cause harm to the system. It depends on the nature of the
176patch, which functions are (un)patched, and which functions the blocking tasks
177are sleeping in (/proc/<pid>/stack may help here). Removal (rmmod) of patch
178modules is permanently disabled when the force feature is used. It cannot be
179guaranteed there is no task sleeping in such module. It implies unbounded
180reference count if a patch module is disabled and enabled in a loop.
181
d0807da7
MB
182Moreover, the usage of force may also affect future applications of live
183patches and cause even more harm to the system. Administrator should first
184consider to simply cancel a transition (see above). If force is used, reboot
185should be planned and no more live patches applied.
186
d83a7cb3
JP
1873.1 Adding consistency model support to new architectures
188---------------------------------------------------------
189
190For adding consistency model support to new architectures, there are a
191few options:
192
1931) Add CONFIG_HAVE_RELIABLE_STACKTRACE. This means porting objtool, and
194 for non-DWARF unwinders, also making sure there's a way for the stack
195 tracing code to detect interrupts on the stack.
196
1972) Alternatively, ensure that every kthread has a call to
198 klp_update_patch_state() in a safe location. Kthreads are typically
199 in an infinite loop which does some action repeatedly. The safe
200 location to switch the kthread's patch state would be at a designated
201 point in the loop where there are no locks taken and all data
202 structures are in a well-defined state.
203
204 The location is clear when using workqueues or the kthread worker
205 API. These kthreads process independent actions in a generic loop.
206
207 It's much more complicated with kthreads which have a custom loop.
208 There the safe location must be carefully selected on a case-by-case
209 basis.
210
211 In that case, arches without HAVE_RELIABLE_STACKTRACE would still be
212 able to use the non-stack-checking parts of the consistency model:
213
214 a) patching user tasks when they cross the kernel/user space
215 boundary; and
216
217 b) patching kthreads and idle tasks at their designated patch points.
218
219 This option isn't as good as option 1 because it requires signaling
220 user tasks and waking kthreads to patch them. But it could still be
221 a good backup option for those architectures which don't have
222 reliable stack traces yet.
223
5e4e3844
PM
224
2254. Livepatch module
226===================
227
228Livepatches are distributed using kernel modules, see
229samples/livepatch/livepatch-sample.c.
230
231The module includes a new implementation of functions that we want
232to replace. In addition, it defines some structures describing the
233relation between the original and the new implementation. Then there
234is code that makes the kernel start using the new code when the livepatch
235module is loaded. Also there is code that cleans up before the
236livepatch module is removed. All this is explained in more details in
237the next sections.
238
239
2404.1. New functions
241------------------
242
243New versions of functions are typically just copied from the original
244sources. A good practice is to add a prefix to the names so that they
245can be distinguished from the original ones, e.g. in a backtrace. Also
246they can be declared as static because they are not called directly
247and do not need the global visibility.
248
249The patch contains only functions that are really modified. But they
250might want to access functions or data from the original source file
251that may only be locally accessible. This can be solved by a special
252relocation section in the generated livepatch module, see
253Documentation/livepatch/module-elf-format.txt for more details.
254
255
2564.2. Metadata
d83a7cb3 257-------------
5e4e3844
PM
258
259The patch is described by several structures that split the information
260into three levels:
261
262 + struct klp_func is defined for each patched function. It describes
263 the relation between the original and the new implementation of a
264 particular function.
265
266 The structure includes the name, as a string, of the original function.
267 The function address is found via kallsyms at runtime.
268
269 Then it includes the address of the new function. It is defined
270 directly by assigning the function pointer. Note that the new
271 function is typically defined in the same source file.
272
273 As an optional parameter, the symbol position in the kallsyms database can
274 be used to disambiguate functions of the same name. This is not the
275 absolute position in the database, but rather the order it has been found
276 only for a particular object ( vmlinux or a kernel module ). Note that
277 kallsyms allows for searching symbols according to the object name.
278
279 + struct klp_object defines an array of patched functions (struct
280 klp_func) in the same object. Where the object is either vmlinux
281 (NULL) or a module name.
282
283 The structure helps to group and handle functions for each object
284 together. Note that patched modules might be loaded later than
285 the patch itself and the relevant functions might be patched
286 only when they are available.
287
288
289 + struct klp_patch defines an array of patched objects (struct
290 klp_object).
291
292 This structure handles all patched functions consistently and eventually,
293 synchronously. The whole patch is applied only when all patched
294 symbols are found. The only exception are symbols from objects
d83a7cb3
JP
295 (kernel modules) that have not been loaded yet.
296
d83a7cb3
JP
297 For more details on how the patch is applied on a per-task basis,
298 see the "Consistency model" section.
5e4e3844
PM
299
300
5e4e3844
PM
3015. Livepatch life-cycle
302=======================
303
e1452b60
JB
304Livepatching can be described by five basic operations:
305loading, enabling, replacing, disabling, removing.
306
307Where the replacing and the disabling operations are mutually
308exclusive. They have the same result for the given patch but
309not for the system.
5e4e3844 310
5e4e3844 311
958ef1e3
PM
3125.1. Loading
313------------
5e4e3844 314
958ef1e3
PM
315The only reasonable way is to enable the patch when the livepatch kernel
316module is being loaded. For this, klp_enable_patch() has to be called
317in the module_init() callback. There are two main reasons:
5e4e3844 318
958ef1e3 319First, only the module has an easy access to the related struct klp_patch.
5e4e3844 320
958ef1e3
PM
321Second, the error code might be used to refuse loading the module when
322the patch cannot get enabled.
5e4e3844
PM
323
324
3255.2. Enabling
326-------------
327
958ef1e3
PM
328The livepatch gets enabled by calling klp_enable_patch() from
329the module_init() callback. The system will start using the new
330implementation of the patched functions at this stage.
5e4e3844 331
958ef1e3
PM
332First, the addresses of the patched functions are found according to their
333names. The special relocations, mentioned in the section "New functions",
334are applied. The relevant entries are created under
335/sys/kernel/livepatch/<name>. The patch is rejected when any above
336operation fails.
d83a7cb3 337
958ef1e3
PM
338Second, livepatch enters into a transition state where tasks are converging
339to the patched state. If an original function is patched for the first
340time, a function specific struct klp_ops is created and an universal
341ftrace handler is registered[*]. This stage is indicated by a value of '1'
342in /sys/kernel/livepatch/<name>/transition. For more information about
343this process, see the "Consistency model" section.
5e4e3844 344
958ef1e3
PM
345Finally, once all tasks have been patched, the 'transition' value changes
346to '0'.
5e4e3844 347
958ef1e3
PM
348[*] Note that functions might be patched multiple times. The ftrace handler
349 is registered only once for a given function. Further patches just add
350 an entry to the list (see field `func_stack`) of the struct klp_ops.
351 The right implementation is selected by the ftrace handler, see
352 the "Consistency model" section.
5e4e3844 353
d67a5372
PM
354 That said, it is highly recommended to use cumulative livepatches
355 because they help keeping the consistency of all changes. In this case,
356 functions might be patched two times only during the transition period.
357
5e4e3844 358
e1452b60
JB
3595.3. Replacing
360--------------
361
362All enabled patches might get replaced by a cumulative patch that
363has the .replace flag set.
364
365Once the new patch is enabled and the 'transition' finishes then
366all the functions (struct klp_func) associated with the replaced
367patches are removed from the corresponding struct klp_ops. Also
368the ftrace handler is unregistered and the struct klp_ops is
369freed when the related function is not modified by the new patch
370and func_stack list becomes empty.
371
c4e6874f
PM
372See Documentation/livepatch/cumulative-patches.txt for more details.
373
e1452b60
JB
374
3755.4. Disabling
5e4e3844
PM
376--------------
377
958ef1e3
PM
378Enabled patches might get disabled by writing '0' to
379/sys/kernel/livepatch/<name>/enabled.
5e4e3844 380
958ef1e3
PM
381First, livepatch enters into a transition state where tasks are converging
382to the unpatched state. The system starts using either the code from
383the previously enabled patch or even the original one. This stage is
384indicated by a value of '1' in /sys/kernel/livepatch/<name>/transition.
385For more information about this process, see the "Consistency model"
386section.
d83a7cb3 387
958ef1e3
PM
388Second, once all tasks have been unpatched, the 'transition' value changes
389to '0'. All the functions (struct klp_func) associated with the to-be-disabled
5e4e3844
PM
390patch are removed from the corresponding struct klp_ops. The ftrace handler
391is unregistered and the struct klp_ops is freed when the func_stack list
392becomes empty.
393
958ef1e3 394Third, the sysfs interface is destroyed.
5e4e3844 395
5e4e3844 396
e1452b60 3975.5. Removing
958ef1e3 398-------------
5e4e3844 399
958ef1e3
PM
400Module removal is only safe when there are no users of functions provided
401by the module. This is the reason why the force feature permanently
402disables the removal. Only when the system is successfully transitioned
403to a new patch state (patched/unpatched) without being forced it is
404guaranteed that no task sleeps or runs in the old code.
5e4e3844
PM
405
406
4076. Sysfs
408========
409
410Information about the registered patches can be found under
411/sys/kernel/livepatch. The patches could be enabled and disabled
412by writing there.
413
c99a2be7
MB
414/sys/kernel/livepatch/<patch>/signal and /sys/kernel/livepatch/<patch>/force
415attributes allow administrator to affect a patching operation.
43347d56 416
5e4e3844
PM
417See Documentation/ABI/testing/sysfs-kernel-livepatch for more details.
418
419
4207. Limitations
421==============
422
423The current Livepatch implementation has several limitations:
424
5e4e3844
PM
425 + Only functions that can be traced could be patched.
426
427 Livepatch is based on the dynamic ftrace. In particular, functions
428 implementing ftrace or the livepatch ftrace handler could not be
429 patched. Otherwise, the code would end up in an infinite loop. A
430 potential mistake is prevented by marking the problematic functions
431 by "notrace".
432
433
5e4e3844
PM
434
435 + Livepatch works reliably only when the dynamic ftrace is located at
436 the very beginning of the function.
437
438 The function need to be redirected before the stack or the function
439 parameters are modified in any way. For example, livepatch requires
440 using -fentry gcc compiler option on x86_64.
441
442 One exception is the PPC port. It uses relative addressing and TOC.
443 Each function has to handle TOC and save LR before it could call
444 the ftrace handler. This operation has to be reverted on return.
445 Fortunately, the generic ftrace code has the same problem and all
8da9704c 446 this is handled on the ftrace level.
5e4e3844
PM
447
448
449 + Kretprobes using the ftrace framework conflict with the patched
450 functions.
451
452 Both kretprobes and livepatches use a ftrace handler that modifies
453 the return address. The first user wins. Either the probe or the patch
454 is rejected when the handler is already in use by the other.
455
456
457 + Kprobes in the original function are ignored when the code is
458 redirected to the new implementation.
459
460 There is a work in progress to add warnings about this situation.