Commit | Line | Data |
---|---|---|
5e4e3844 PM |
1 | ========= |
2 | Livepatch | |
3 | ========= | |
4 | ||
5 | This document outlines basic information about kernel livepatching. | |
6 | ||
7 | Table of Contents: | |
8 | ||
9 | 1. Motivation | |
10 | 2. Kprobes, Ftrace, Livepatching | |
11 | 3. Consistency model | |
12 | 4. Livepatch module | |
13 | 4.1. New functions | |
14 | 4.2. Metadata | |
5e4e3844 | 15 | 5. 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 |
21 | 6. Sysfs |
22 | 7. Limitations | |
23 | ||
24 | ||
25 | 1. Motivation | |
26 | ============= | |
27 | ||
28 | There are many situations where users are reluctant to reboot a system. It may | |
29 | be because their system is performing complex scientific computations or under | |
30 | heavy load during peak usage. In addition to keeping systems up and running, | |
31 | users want to also have a stable and secure system. Livepatching gives users | |
32 | both by allowing for function calls to be redirected; thus, fixing critical | |
33 | functions without a system reboot. | |
34 | ||
35 | ||
36 | 2. Kprobes, Ftrace, Livepatching | |
37 | ================================ | |
38 | ||
39 | There are multiple mechanisms in the Linux kernel that are directly related | |
40 | to redirection of code execution; namely: kernel probes, function tracing, | |
41 | and 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 | ||
54 | All three approaches need to modify the existing code at runtime. Therefore | |
55 | they need to be aware of each other and not step over each other's toes. | |
56 | Most of these problems are solved by using the dynamic ftrace framework as | |
57 | a base. A Kprobe is registered as a ftrace handler when the function entry | |
58 | is probed, see CONFIG_KPROBES_ON_FTRACE. Also an alternative function from | |
59 | a live patch is called with the help of a custom ftrace handler. But there are | |
60 | some limitations, see below. | |
61 | ||
62 | ||
63 | 3. Consistency model | |
64 | ==================== | |
65 | ||
66 | Functions are there for a reason. They take some input parameters, get or | |
67 | release locks, read, process, and even write some data in a defined way, | |
68 | have return values. In other words, each function has a defined semantic. | |
69 | ||
70 | Many fixes do not change the semantic of the modified functions. For | |
71 | example, they add a NULL pointer or a boundary check, fix a race by adding | |
72 | a missing memory barrier, or add some locking around a critical section. | |
73 | Most of these changes are self contained and the function presents itself | |
74 | the same way to the rest of the system. In this case, the functions might | |
d0807da7 | 75 | be updated independently one by one. |
5e4e3844 PM |
76 | |
77 | But there are more complex fixes. For example, a patch might change | |
78 | ordering of locking in multiple functions at the same time. Or a patch | |
79 | might exchange meaning of some temporary structures and update | |
80 | all the relevant functions. In this case, the affected unit | |
81 | (thread, whole kernel) need to start using all new versions of | |
82 | the functions at the same time. Also the switch must happen only | |
83 | when it is safe to do so, e.g. when the affected locks are released | |
84 | or no data are stored in the modified structures at the moment. | |
85 | ||
86 | The theory about how to apply functions a safe way is rather complex. | |
87 | The aim is to define a so-called consistency model. It attempts to define | |
88 | conditions when the new implementation could be used so that the system | |
d83a7cb3 JP |
89 | stays consistent. |
90 | ||
91 | Livepatch has a consistency model which is a hybrid of kGraft and | |
92 | kpatch: it uses kGraft's per-task consistency and syscall barrier | |
93 | switching combined with kpatch's stack trace switching. There are also | |
94 | a number of fallback options which make it quite flexible. | |
95 | ||
96 | Patches are applied on a per-task basis, when the task is deemed safe to | |
97 | switch over. When a patch is enabled, livepatch enters into a | |
98 | transition state where tasks are converging to the patched state. | |
99 | Usually this transition state can complete in a few seconds. The same | |
100 | sequence occurs when a patch is disabled, except the tasks converge from | |
101 | the patched state to the unpatched state. | |
102 | ||
103 | An interrupt handler inherits the patched state of the task it | |
104 | interrupts. The same is true for forked tasks: the child inherits the | |
105 | patched state of the parent. | |
106 | ||
107 | Livepatch uses several complementary approaches to determine when it's | |
108 | safe to patch tasks: | |
109 | ||
110 | 1. 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 | ||
117 | 2. 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 | |
128 | 3. 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 |
134 | Architectures which don't have HAVE_RELIABLE_STACKTRACE solely rely on |
135 | the second approach. It's highly likely that some tasks may still be | |
136 | running with an old version of the function, until that function | |
137 | returns. In this case you would have to signal the tasks. This | |
138 | especially applies to kthreads. They may not be woken up and would need | |
139 | to be forced. See below for more information. | |
d83a7cb3 | 140 | |
d0807da7 MB |
141 | Unless we can come up with another way to patch kthreads, architectures |
142 | without HAVE_RELIABLE_STACKTRACE are not considered fully supported by | |
143 | the kernel livepatching. | |
d83a7cb3 JP |
144 | |
145 | The /sys/kernel/livepatch/<patch>/transition file shows whether a patch | |
146 | is in transition. Only a single patch (the topmost patch on the stack) | |
147 | can be in transition at a given time. A patch can remain in transition | |
148 | indefinitely, if any of the tasks are stuck in the initial patch state. | |
149 | ||
150 | A transition can be reversed and effectively canceled by writing the | |
151 | opposite value to the /sys/kernel/livepatch/<patch>/enabled file while | |
152 | the transition is in progress. Then all the tasks will attempt to | |
153 | converge back to the original patch state. | |
154 | ||
155 | There's also a /proc/<pid>/patch_state file which can be used to | |
156 | determine which tasks are blocking completion of a patching operation. | |
157 | If a patch is in transition, this file shows 0 to indicate the task is | |
158 | unpatched and 1 to indicate it's patched. Otherwise, if no patch is in | |
159 | transition, it shows -1. Any tasks which are blocking the transition | |
160 | can be signaled with SIGSTOP and SIGCONT to force them to change their | |
43347d56 MB |
161 | patched state. This may be harmful to the system though. |
162 | /sys/kernel/livepatch/<patch>/signal attribute provides a better alternative. | |
163 | Writing 1 to the attribute sends a fake signal to all remaining blocking | |
164 | tasks. No proper signal is actually delivered (there is no data in signal | |
165 | pending structures). Tasks are interrupted or woken up, and forced to change | |
166 | their patched state. | |
d83a7cb3 | 167 | |
c99a2be7 MB |
168 | Administrator can also affect a transition through |
169 | /sys/kernel/livepatch/<patch>/force attribute. Writing 1 there clears | |
170 | TIF_PATCH_PENDING flag of all tasks and thus forces the tasks to the patched | |
171 | state. Important note! The force attribute is intended for cases when the | |
172 | transition gets stuck for a long time because of a blocking task. Administrator | |
173 | is expected to collect all necessary data (namely stack traces of such blocking | |
174 | tasks) and request a clearance from a patch distributor to force the transition. | |
175 | Unauthorized usage may cause harm to the system. It depends on the nature of the | |
176 | patch, which functions are (un)patched, and which functions the blocking tasks | |
177 | are sleeping in (/proc/<pid>/stack may help here). Removal (rmmod) of patch | |
178 | modules is permanently disabled when the force feature is used. It cannot be | |
179 | guaranteed there is no task sleeping in such module. It implies unbounded | |
180 | reference count if a patch module is disabled and enabled in a loop. | |
181 | ||
d0807da7 MB |
182 | Moreover, the usage of force may also affect future applications of live |
183 | patches and cause even more harm to the system. Administrator should first | |
184 | consider to simply cancel a transition (see above). If force is used, reboot | |
185 | should be planned and no more live patches applied. | |
186 | ||
d83a7cb3 JP |
187 | 3.1 Adding consistency model support to new architectures |
188 | --------------------------------------------------------- | |
189 | ||
190 | For adding consistency model support to new architectures, there are a | |
191 | few options: | |
192 | ||
193 | 1) 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 | ||
197 | 2) 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 | |
225 | 4. Livepatch module | |
226 | =================== | |
227 | ||
228 | Livepatches are distributed using kernel modules, see | |
229 | samples/livepatch/livepatch-sample.c. | |
230 | ||
231 | The module includes a new implementation of functions that we want | |
232 | to replace. In addition, it defines some structures describing the | |
233 | relation between the original and the new implementation. Then there | |
234 | is code that makes the kernel start using the new code when the livepatch | |
235 | module is loaded. Also there is code that cleans up before the | |
236 | livepatch module is removed. All this is explained in more details in | |
237 | the next sections. | |
238 | ||
239 | ||
240 | 4.1. New functions | |
241 | ------------------ | |
242 | ||
243 | New versions of functions are typically just copied from the original | |
244 | sources. A good practice is to add a prefix to the names so that they | |
245 | can be distinguished from the original ones, e.g. in a backtrace. Also | |
246 | they can be declared as static because they are not called directly | |
247 | and do not need the global visibility. | |
248 | ||
249 | The patch contains only functions that are really modified. But they | |
250 | might want to access functions or data from the original source file | |
251 | that may only be locally accessible. This can be solved by a special | |
252 | relocation section in the generated livepatch module, see | |
253 | Documentation/livepatch/module-elf-format.txt for more details. | |
254 | ||
255 | ||
256 | 4.2. Metadata | |
d83a7cb3 | 257 | ------------- |
5e4e3844 PM |
258 | |
259 | The patch is described by several structures that split the information | |
260 | into 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 |
301 | 5. Livepatch life-cycle |
302 | ======================= | |
303 | ||
e1452b60 JB |
304 | Livepatching can be described by five basic operations: |
305 | loading, enabling, replacing, disabling, removing. | |
306 | ||
307 | Where the replacing and the disabling operations are mutually | |
308 | exclusive. They have the same result for the given patch but | |
309 | not for the system. | |
5e4e3844 | 310 | |
5e4e3844 | 311 | |
958ef1e3 PM |
312 | 5.1. Loading |
313 | ------------ | |
5e4e3844 | 314 | |
958ef1e3 PM |
315 | The only reasonable way is to enable the patch when the livepatch kernel |
316 | module is being loaded. For this, klp_enable_patch() has to be called | |
317 | in the module_init() callback. There are two main reasons: | |
5e4e3844 | 318 | |
958ef1e3 | 319 | First, only the module has an easy access to the related struct klp_patch. |
5e4e3844 | 320 | |
958ef1e3 PM |
321 | Second, the error code might be used to refuse loading the module when |
322 | the patch cannot get enabled. | |
5e4e3844 PM |
323 | |
324 | ||
325 | 5.2. Enabling | |
326 | ------------- | |
327 | ||
958ef1e3 PM |
328 | The livepatch gets enabled by calling klp_enable_patch() from |
329 | the module_init() callback. The system will start using the new | |
330 | implementation of the patched functions at this stage. | |
5e4e3844 | 331 | |
958ef1e3 PM |
332 | First, the addresses of the patched functions are found according to their |
333 | names. The special relocations, mentioned in the section "New functions", | |
334 | are applied. The relevant entries are created under | |
335 | /sys/kernel/livepatch/<name>. The patch is rejected when any above | |
336 | operation fails. | |
d83a7cb3 | 337 | |
958ef1e3 PM |
338 | Second, livepatch enters into a transition state where tasks are converging |
339 | to the patched state. If an original function is patched for the first | |
340 | time, a function specific struct klp_ops is created and an universal | |
341 | ftrace handler is registered[*]. This stage is indicated by a value of '1' | |
342 | in /sys/kernel/livepatch/<name>/transition. For more information about | |
343 | this process, see the "Consistency model" section. | |
5e4e3844 | 344 | |
958ef1e3 PM |
345 | Finally, once all tasks have been patched, the 'transition' value changes |
346 | to '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 PM |
353 | |
354 | ||
e1452b60 JB |
355 | 5.3. Replacing |
356 | -------------- | |
357 | ||
358 | All enabled patches might get replaced by a cumulative patch that | |
359 | has the .replace flag set. | |
360 | ||
361 | Once the new patch is enabled and the 'transition' finishes then | |
362 | all the functions (struct klp_func) associated with the replaced | |
363 | patches are removed from the corresponding struct klp_ops. Also | |
364 | the ftrace handler is unregistered and the struct klp_ops is | |
365 | freed when the related function is not modified by the new patch | |
366 | and func_stack list becomes empty. | |
367 | ||
c4e6874f PM |
368 | See Documentation/livepatch/cumulative-patches.txt for more details. |
369 | ||
e1452b60 JB |
370 | |
371 | 5.4. Disabling | |
5e4e3844 PM |
372 | -------------- |
373 | ||
958ef1e3 PM |
374 | Enabled patches might get disabled by writing '0' to |
375 | /sys/kernel/livepatch/<name>/enabled. | |
5e4e3844 | 376 | |
958ef1e3 PM |
377 | First, livepatch enters into a transition state where tasks are converging |
378 | to the unpatched state. The system starts using either the code from | |
379 | the previously enabled patch or even the original one. This stage is | |
380 | indicated by a value of '1' in /sys/kernel/livepatch/<name>/transition. | |
381 | For more information about this process, see the "Consistency model" | |
382 | section. | |
d83a7cb3 | 383 | |
958ef1e3 PM |
384 | Second, once all tasks have been unpatched, the 'transition' value changes |
385 | to '0'. All the functions (struct klp_func) associated with the to-be-disabled | |
5e4e3844 PM |
386 | patch are removed from the corresponding struct klp_ops. The ftrace handler |
387 | is unregistered and the struct klp_ops is freed when the func_stack list | |
388 | becomes empty. | |
389 | ||
958ef1e3 | 390 | Third, the sysfs interface is destroyed. |
5e4e3844 | 391 | |
958ef1e3 PM |
392 | Note that patches must be disabled in exactly the reverse order in which |
393 | they were enabled. It makes the problem and the implementation much easier. | |
5e4e3844 | 394 | |
5e4e3844 | 395 | |
e1452b60 | 396 | 5.5. Removing |
958ef1e3 | 397 | ------------- |
5e4e3844 | 398 | |
958ef1e3 PM |
399 | Module removal is only safe when there are no users of functions provided |
400 | by the module. This is the reason why the force feature permanently | |
401 | disables the removal. Only when the system is successfully transitioned | |
402 | to a new patch state (patched/unpatched) without being forced it is | |
403 | guaranteed that no task sleeps or runs in the old code. | |
5e4e3844 PM |
404 | |
405 | ||
406 | 6. Sysfs | |
407 | ======== | |
408 | ||
409 | Information about the registered patches can be found under | |
410 | /sys/kernel/livepatch. The patches could be enabled and disabled | |
411 | by writing there. | |
412 | ||
c99a2be7 MB |
413 | /sys/kernel/livepatch/<patch>/signal and /sys/kernel/livepatch/<patch>/force |
414 | attributes allow administrator to affect a patching operation. | |
43347d56 | 415 | |
5e4e3844 PM |
416 | See Documentation/ABI/testing/sysfs-kernel-livepatch for more details. |
417 | ||
418 | ||
419 | 7. Limitations | |
420 | ============== | |
421 | ||
422 | The current Livepatch implementation has several limitations: | |
423 | ||
5e4e3844 PM |
424 | + Only functions that can be traced could be patched. |
425 | ||
426 | Livepatch is based on the dynamic ftrace. In particular, functions | |
427 | implementing ftrace or the livepatch ftrace handler could not be | |
428 | patched. Otherwise, the code would end up in an infinite loop. A | |
429 | potential mistake is prevented by marking the problematic functions | |
430 | by "notrace". | |
431 | ||
432 | ||
5e4e3844 PM |
433 | |
434 | + Livepatch works reliably only when the dynamic ftrace is located at | |
435 | the very beginning of the function. | |
436 | ||
437 | The function need to be redirected before the stack or the function | |
438 | parameters are modified in any way. For example, livepatch requires | |
439 | using -fentry gcc compiler option on x86_64. | |
440 | ||
441 | One exception is the PPC port. It uses relative addressing and TOC. | |
442 | Each function has to handle TOC and save LR before it could call | |
443 | the ftrace handler. This operation has to be reverted on return. | |
444 | Fortunately, the generic ftrace code has the same problem and all | |
8da9704c | 445 | this is handled on the ftrace level. |
5e4e3844 PM |
446 | |
447 | ||
448 | + Kretprobes using the ftrace framework conflict with the patched | |
449 | functions. | |
450 | ||
451 | Both kretprobes and livepatches use a ftrace handler that modifies | |
452 | the return address. The first user wins. Either the probe or the patch | |
453 | is rejected when the handler is already in use by the other. | |
454 | ||
455 | ||
456 | + Kprobes in the original function are ignored when the code is | |
457 | redirected to the new implementation. | |
458 | ||
459 | There is a work in progress to add warnings about this situation. |