1 ===========
2 Static Keys
3 ===========
4
5 .. warning::
6
7 DEPRECATED API:
8
9 The use of 'struct static_key' directly, is now DEPRECATED. In addition
10 static_key_{true,false}() is also DEPRECATED. IE DO NOT use the following::
11
12 struct static_key false = STATIC_KEY_INIT_FALSE;
13 struct static_key true = STATIC_KEY_INIT_TRUE;
14 static_key_true()
15 static_key_false()
16
17 The updated API replacements are::
18
19 DEFINE_STATIC_KEY_TRUE(key);
20 DEFINE_STATIC_KEY_FALSE(key);
21 DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
22 DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
23 static_branch_likely()
24 static_branch_unlikely()
25
26 Abstract
27 ========
28
29 Static keys allows the inclusion of seldom used features in
30 performance-sensitive fast-path kernel code, via a GCC feature and a code
31 patching technique. A quick example::
32
33 DEFINE_STATIC_KEY_FALSE(key);
34
35 ...
36
37 if (static_branch_unlikely(&key))
38 do unlikely code
39 else
40 do likely code
41
42 ...
43 static_branch_enable(&key);
44 ...
45 static_branch_disable(&key);
46 ...
47
48 The static_branch_unlikely() branch will be generated into the code with as little
49 impact to the likely code path as possible.
50
51
52 Motivation
53 ==========
54
55
56 Currently, tracepoints are implemented using a conditional branch. The
57 conditional check requires checking a global variable for each tracepoint.
58 Although the overhead of this check is small, it increases when the memory
59 cache comes under pressure (memory cache lines for these global variables may
60 be shared with other memory accesses). As we increase the number of tracepoints
61 in the kernel this overhead may become more of an issue. In addition,
62 tracepoints are often dormant (disabled) and provide no direct kernel
63 functionality. Thus, it is highly desirable to reduce their impact as much as
64 possible. Although tracepoints are the original motivation for this work, other
65 kernel code paths should be able to make use of the static keys facility.
66
67
68 Solution
69 ========
70
71
72 gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:
73
74 https://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html
75
76 Using the 'asm goto', we can create branches that are either taken or not taken
77 by default, without the need to check memory. Then, at run-time, we can patch
78 the branch site to change the branch direction.
79
80 For example, if we have a simple branch that is disabled by default::
81
82 if (static_branch_unlikely(&key))
83 printk("I am the true branch\n");
84
85 Thus, by default the 'printk' will not be emitted. And the code generated will
86 consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
87 straight-line code path. When the branch is 'flipped', we will patch the
88 'no-op' in the straight-line codepath with a 'jump' instruction to the
89 out-of-line true branch. Thus, changing branch direction is expensive but
90 branch selection is basically 'free'. That is the basic tradeoff of this
91 optimization.
92
93 This lowlevel patching mechanism is called 'jump label patching', and it gives
94 the basis for the static keys facility.
95
96 Static key label API, usage and examples
97 ========================================
98
99
100 In order to make use of this optimization you must first define a key::
101
102 DEFINE_STATIC_KEY_TRUE(key);
103
104 or::
105
106 DEFINE_STATIC_KEY_FALSE(key);
107
108
109 The key must be global, that is, it can't be allocated on the stack or dynamically
110 allocated at run-time.
111
112 The key is then used in code as::
113
114 if (static_branch_unlikely(&key))
115 do unlikely code
116 else
117 do likely code
118
119 Or::
120
121 if (static_branch_likely(&key))
122 do likely code
123 else
124 do unlikely code
125
126 Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
127 be used in either static_branch_likely() or static_branch_unlikely()
128 statements.
129
130 Branch(es) can be set true via::
131
132 static_branch_enable(&key);
133
134 or false via::
135
136 static_branch_disable(&key);
137
138 The branch(es) can then be switched via reference counts::
139
140 static_branch_inc(&key);
141 ...
142 static_branch_dec(&key);
143
144 Thus, 'static_branch_inc()' means 'make the branch true', and
145 'static_branch_dec()' means 'make the branch false' with appropriate
146 reference counting. For example, if the key is initialized true, a
147 static_branch_dec(), will switch the branch to false. And a subsequent
148 static_branch_inc(), will change the branch back to true. Likewise, if the
149 key is initialized false, a 'static_branch_inc()', will change the branch to
150 true. And then a 'static_branch_dec()', will again make the branch false.
151
152 The state and the reference count can be retrieved with 'static_key_enabled()'
153 and 'static_key_count()'. In general, if you use these functions, they
154 should be protected with the same mutex used around the enable/disable
155 or increment/decrement function.
156
157 Note that switching branches results in some locks being taken,
158 particularly the CPU hotplug lock (in order to avoid races against
159 CPUs being brought in the kernel while the kernel is getting
160 patched). Calling the static key API from within a hotplug notifier is
161 thus a sure deadlock recipe. In order to still allow use of the
162 functionality, the following functions are provided:
163
164 static_key_enable_cpuslocked()
165 static_key_disable_cpuslocked()
166 static_branch_enable_cpuslocked()
167 static_branch_disable_cpuslocked()
168
169 These functions are *not* general purpose, and must only be used when
170 you really know that you're in the above context, and no other.
171
172 Where an array of keys is required, it can be defined as::
173
174 DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
175
176 or::
177
178 DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
179
180 4) Architecture level code patching interface, 'jump labels'
181
182
183 There are a few functions and macros that architectures must implement in order
184 to take advantage of this optimization. If there is no architecture support, we
185 simply fall back to a traditional, load, test, and jump sequence. Also, the
186 struct jump_entry table must be at least 4-byte aligned because the
187 static_key->entry field makes use of the two least significant bits.
188
189 * ``select HAVE_ARCH_JUMP_LABEL``,
190 see: arch/x86/Kconfig
191
192 * ``#define JUMP_LABEL_NOP_SIZE``,
193 see: arch/x86/include/asm/jump_label.h
194
195 * ``__always_inline bool arch_static_branch(struct static_key *key, bool branch)``,
196 see: arch/x86/include/asm/jump_label.h
197
198 * ``__always_inline bool arch_static_branch_jump(struct static_key *key, bool branch)``,
199 see: arch/x86/include/asm/jump_label.h
200
201 * ``void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type)``,
202 see: arch/x86/kernel/jump_label.c
203
204 * ``struct jump_entry``,
205 see: arch/x86/include/asm/jump_label.h
206
207
208 5) Static keys / jump label analysis, results (x86_64):
209
210
211 As an example, let's add the following branch to 'getppid()', such that the
212 system call now looks like::
213
214 SYSCALL_DEFINE0(getppid)
215 {
216 int pid;
217
218 + if (static_branch_unlikely(&key))
219 + printk("I am the true branch\n");
220
221 rcu_read_lock();
222 pid = task_tgid_vnr(rcu_dereference(current->real_parent));
223 rcu_read_unlock();
224
225 return pid;
226 }
227
228 The resulting instructions with jump labels generated by GCC is::
229
230 ffffffff81044290 <sys_getppid>:
231 ffffffff81044290: 55 push %rbp
232 ffffffff81044291: 48 89 e5 mov %rsp,%rbp
233 ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9>
234 ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
235 ffffffff810442a0: 00 00
236 ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
237 ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
238 ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
239 ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr>
240 ffffffff810442bc: 5d pop %rbp
241 ffffffff810442bd: 48 98 cltq
242 ffffffff810442bf: c3 retq
243 ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi
244 ffffffff810442c7: 31 c0 xor %eax,%eax
245 ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk>
246 ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9>
247
248 Without the jump label optimization it looks like::
249
250 ffffffff810441f0 <sys_getppid>:
251 ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key>
252 ffffffff810441f6: 55 push %rbp
253 ffffffff810441f7: 48 89 e5 mov %rsp,%rbp
254 ffffffff810441fa: 85 c0 test %eax,%eax
255 ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35>
256 ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
257 ffffffff81044205: 00 00
258 ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
259 ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
260 ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
261 ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr>
262 ffffffff81044221: 5d pop %rbp
263 ffffffff81044222: 48 98 cltq
264 ffffffff81044224: c3 retq
265 ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi
266 ffffffff8104422c: 31 c0 xor %eax,%eax
267 ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk>
268 ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe>
269 ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1)
270 ffffffff8104423c: 00 00 00 00
271
272 Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
273 vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
274 to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
275 label case adds::
276
277 6 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
278
279 If we then include the padding bytes, the jump label code saves, 16 total bytes
280 of instruction memory for this small function. In this case the non-jump label
281 function is 80 bytes long. Thus, we have saved 20% of the instruction
282 footprint. We can in fact improve this even further, since the 5-byte no-op
283 really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
284 However, we have not yet implemented optimal no-op sizes (they are currently
285 hard-coded).
286
287 Since there are a number of static key API uses in the scheduler paths,
288 'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
289 performance improvement. Testing done on 3.3.0-rc2:
290
291 jump label disabled::
292
293 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
294
295 855.700314 task-clock # 0.534 CPUs utilized ( +- 0.11% )
296 200,003 context-switches # 0.234 M/sec ( +- 0.00% )
297 0 CPU-migrations # 0.000 M/sec ( +- 39.58% )
298 487 page-faults # 0.001 M/sec ( +- 0.02% )
299 1,474,374,262 cycles # 1.723 GHz ( +- 0.17% )
300 <not supported> stalled-cycles-frontend
301 <not supported> stalled-cycles-backend
302 1,178,049,567 instructions # 0.80 insns per cycle ( +- 0.06% )
303 208,368,926 branches # 243.507 M/sec ( +- 0.06% )
304 5,569,188 branch-misses # 2.67% of all branches ( +- 0.54% )
305
306 1.601607384 seconds time elapsed ( +- 0.07% )
307
308 jump label enabled::
309
310 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
311
312 841.043185 task-clock # 0.533 CPUs utilized ( +- 0.12% )
313 200,004 context-switches # 0.238 M/sec ( +- 0.00% )
314 0 CPU-migrations # 0.000 M/sec ( +- 40.87% )
315 487 page-faults # 0.001 M/sec ( +- 0.05% )
316 1,432,559,428 cycles # 1.703 GHz ( +- 0.18% )
317 <not supported> stalled-cycles-frontend
318 <not supported> stalled-cycles-backend
319 1,175,363,994 instructions # 0.82 insns per cycle ( +- 0.04% )
320 206,859,359 branches # 245.956 M/sec ( +- 0.04% )
321 4,884,119 branch-misses # 2.36% of all branches ( +- 0.85% )
322
323 1.579384366 seconds time elapsed
324
325 The percentage of saved branches is .7%, and we've saved 12% on
326 'branch-misses'. This is where we would expect to get the most savings, since
327 this optimization is about reducing the number of branches. In addition, we've
328 saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.