blob: ef419fd0897f037539b14d69e1f71e37136e3186 [file] [log] [blame]
Jason Baron1cfa60d2012-02-21 15:03:30 -05001 Static Keys
2 -----------
3
Jason Baron412758c2015-07-30 03:59:48 +00004DEPRECATED API:
5
6The use of 'struct static_key' directly, is now DEPRECATED. In addition
7static_key_{true,false}() is also DEPRECATED. IE DO NOT use the following:
8
9struct static_key false = STATIC_KEY_INIT_FALSE;
10struct static_key true = STATIC_KEY_INIT_TRUE;
11static_key_true()
12static_key_false()
13
14The updated API replacements are:
15
16DEFINE_STATIC_KEY_TRUE(key);
17DEFINE_STATIC_KEY_FALSE(key);
Catalin Marinasef0da552016-09-05 18:25:47 +010018DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
19DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
Jonathan Corbet1975dbc2015-09-14 17:11:05 -060020static_branch_likely()
21static_branch_unlikely()
Jason Baron1cfa60d2012-02-21 15:03:30 -050022
230) Abstract
24
25Static keys allows the inclusion of seldom used features in
26performance-sensitive fast-path kernel code, via a GCC feature and a code
27patching technique. A quick example:
28
Jason Baron412758c2015-07-30 03:59:48 +000029 DEFINE_STATIC_KEY_FALSE(key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050030
31 ...
32
Jason Baron412758c2015-07-30 03:59:48 +000033 if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -050034 do unlikely code
35 else
36 do likely code
37
38 ...
Jason Baron412758c2015-07-30 03:59:48 +000039 static_branch_enable(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050040 ...
Jason Baron412758c2015-07-30 03:59:48 +000041 static_branch_disable(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050042 ...
43
Jason Baron412758c2015-07-30 03:59:48 +000044The static_branch_unlikely() branch will be generated into the code with as little
Jason Baron1cfa60d2012-02-21 15:03:30 -050045impact to the likely code path as possible.
46
47
481) Motivation
49
50
51Currently, tracepoints are implemented using a conditional branch. The
52conditional check requires checking a global variable for each tracepoint.
53Although the overhead of this check is small, it increases when the memory
54cache comes under pressure (memory cache lines for these global variables may
55be shared with other memory accesses). As we increase the number of tracepoints
56in the kernel this overhead may become more of an issue. In addition,
57tracepoints are often dormant (disabled) and provide no direct kernel
58functionality. Thus, it is highly desirable to reduce their impact as much as
59possible. Although tracepoints are the original motivation for this work, other
60kernel code paths should be able to make use of the static keys facility.
61
62
632) Solution
64
65
66gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:
67
68http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html
69
70Using the 'asm goto', we can create branches that are either taken or not taken
71by default, without the need to check memory. Then, at run-time, we can patch
72the branch site to change the branch direction.
73
74For example, if we have a simple branch that is disabled by default:
75
Jason Baron412758c2015-07-30 03:59:48 +000076 if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -050077 printk("I am the true branch\n");
78
79Thus, by default the 'printk' will not be emitted. And the code generated will
80consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
81straight-line code path. When the branch is 'flipped', we will patch the
82'no-op' in the straight-line codepath with a 'jump' instruction to the
83out-of-line true branch. Thus, changing branch direction is expensive but
84branch selection is basically 'free'. That is the basic tradeoff of this
85optimization.
86
87This lowlevel patching mechanism is called 'jump label patching', and it gives
88the basis for the static keys facility.
89
903) Static key label API, usage and examples:
91
92
93In order to make use of this optimization you must first define a key:
94
Jason Baron412758c2015-07-30 03:59:48 +000095 DEFINE_STATIC_KEY_TRUE(key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050096
97or:
98
Jason Baron412758c2015-07-30 03:59:48 +000099 DEFINE_STATIC_KEY_FALSE(key);
Jason Baron1cfa60d2012-02-21 15:03:30 -0500100
Jason Baron412758c2015-07-30 03:59:48 +0000101
102The key must be global, that is, it can't be allocated on the stack or dynamically
Jason Baron1cfa60d2012-02-21 15:03:30 -0500103allocated at run-time.
104
105The key is then used in code as:
106
Jason Baron412758c2015-07-30 03:59:48 +0000107 if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -0500108 do unlikely code
109 else
110 do likely code
111
112Or:
113
Jason Baron412758c2015-07-30 03:59:48 +0000114 if (static_branch_likely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -0500115 do likely code
116 else
117 do unlikely code
118
Jason Baron412758c2015-07-30 03:59:48 +0000119Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
120be used in either static_branch_likely() or static_branch_unlikely()
Stan Drozd9bb0e9c2017-04-21 13:16:03 +0200121statements.
Jason Baron1cfa60d2012-02-21 15:03:30 -0500122
Jason Baron412758c2015-07-30 03:59:48 +0000123Branch(es) can be set true via:
Jason Baron1cfa60d2012-02-21 15:03:30 -0500124
Jason Baron412758c2015-07-30 03:59:48 +0000125static_branch_enable(&key);
126
127or false via:
128
129static_branch_disable(&key);
130
131The branch(es) can then be switched via reference counts:
132
133 static_branch_inc(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -0500134 ...
Jason Baron412758c2015-07-30 03:59:48 +0000135 static_branch_dec(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -0500136
Jason Baron412758c2015-07-30 03:59:48 +0000137Thus, 'static_branch_inc()' means 'make the branch true', and
138'static_branch_dec()' means 'make the branch false' with appropriate
Jason Baron1cfa60d2012-02-21 15:03:30 -0500139reference counting. For example, if the key is initialized true, a
Jason Baron412758c2015-07-30 03:59:48 +0000140static_branch_dec(), will switch the branch to false. And a subsequent
141static_branch_inc(), will change the branch back to true. Likewise, if the
142key is initialized false, a 'static_branch_inc()', will change the branch to
143true. And then a 'static_branch_dec()', will again make the branch false.
Jason Baron1cfa60d2012-02-21 15:03:30 -0500144
Catalin Marinasef0da552016-09-05 18:25:47 +0100145Where an array of keys is required, it can be defined as:
146
147 DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
148
149or:
150
151 DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
Jason Baron1cfa60d2012-02-21 15:03:30 -0500152
1534) Architecture level code patching interface, 'jump labels'
154
155
156There are a few functions and macros that architectures must implement in order
157to take advantage of this optimization. If there is no architecture support, we
Jason Baron3821fd32017-02-03 15:42:24 -0500158simply fall back to a traditional, load, test, and jump sequence. Also, the
159struct jump_entry table must be at least 4-byte aligned because the
160static_key->entry field makes use of the two least significant bits.
Jason Baron1cfa60d2012-02-21 15:03:30 -0500161
162* select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig
163
164* #define JUMP_LABEL_NOP_SIZE, see: arch/x86/include/asm/jump_label.h
165
Jason Baron412758c2015-07-30 03:59:48 +0000166* __always_inline bool arch_static_branch(struct static_key *key, bool branch), see:
Jason Baron1cfa60d2012-02-21 15:03:30 -0500167 arch/x86/include/asm/jump_label.h
168
Jason Baron412758c2015-07-30 03:59:48 +0000169* __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch),
170 see: arch/x86/include/asm/jump_label.h
171
Jason Baron1cfa60d2012-02-21 15:03:30 -0500172* void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type),
173 see: arch/x86/kernel/jump_label.c
174
175* __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type),
176 see: arch/x86/kernel/jump_label.c
177
178
179* struct jump_entry, see: arch/x86/include/asm/jump_label.h
180
181
1825) Static keys / jump label analysis, results (x86_64):
183
184
185As an example, let's add the following branch to 'getppid()', such that the
186system call now looks like:
187
188SYSCALL_DEFINE0(getppid)
189{
190 int pid;
191
Jason Baron412758c2015-07-30 03:59:48 +0000192+ if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -0500193+ printk("I am the true branch\n");
194
195 rcu_read_lock();
196 pid = task_tgid_vnr(rcu_dereference(current->real_parent));
197 rcu_read_unlock();
198
199 return pid;
200}
201
202The resulting instructions with jump labels generated by GCC is:
203
204ffffffff81044290 <sys_getppid>:
205ffffffff81044290: 55 push %rbp
206ffffffff81044291: 48 89 e5 mov %rsp,%rbp
207ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9>
208ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
209ffffffff810442a0: 00 00
210ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
211ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
212ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
213ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr>
214ffffffff810442bc: 5d pop %rbp
215ffffffff810442bd: 48 98 cltq
216ffffffff810442bf: c3 retq
217ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi
218ffffffff810442c7: 31 c0 xor %eax,%eax
219ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk>
220ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9>
221
222Without the jump label optimization it looks like:
223
224ffffffff810441f0 <sys_getppid>:
225ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key>
226ffffffff810441f6: 55 push %rbp
227ffffffff810441f7: 48 89 e5 mov %rsp,%rbp
228ffffffff810441fa: 85 c0 test %eax,%eax
229ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35>
230ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
231ffffffff81044205: 00 00
232ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
233ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
234ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
235ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr>
236ffffffff81044221: 5d pop %rbp
237ffffffff81044222: 48 98 cltq
238ffffffff81044224: c3 retq
239ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi
240ffffffff8104422c: 31 c0 xor %eax,%eax
241ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk>
242ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe>
243ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1)
244ffffffff8104423c: 00 00 00 00
245
246Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
247vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
248to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
249label case adds:
250
2516 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
252
253If we then include the padding bytes, the jump label code saves, 16 total bytes
Masanari Iidac94bed8e2012-04-10 00:22:13 +0900254of instruction memory for this small function. In this case the non-jump label
Xishi Qiuc79a8d82013-11-06 13:18:21 -0800255function is 80 bytes long. Thus, we have saved 20% of the instruction
Jason Baron1cfa60d2012-02-21 15:03:30 -0500256footprint. We can in fact improve this even further, since the 5-byte no-op
257really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
258However, we have not yet implemented optimal no-op sizes (they are currently
259hard-coded).
260
261Since there are a number of static key API uses in the scheduler paths,
262'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
263performance improvement. Testing done on 3.3.0-rc2:
264
265jump label disabled:
266
267 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
268
269 855.700314 task-clock # 0.534 CPUs utilized ( +- 0.11% )
270 200,003 context-switches # 0.234 M/sec ( +- 0.00% )
271 0 CPU-migrations # 0.000 M/sec ( +- 39.58% )
272 487 page-faults # 0.001 M/sec ( +- 0.02% )
273 1,474,374,262 cycles # 1.723 GHz ( +- 0.17% )
274 <not supported> stalled-cycles-frontend
275 <not supported> stalled-cycles-backend
276 1,178,049,567 instructions # 0.80 insns per cycle ( +- 0.06% )
277 208,368,926 branches # 243.507 M/sec ( +- 0.06% )
278 5,569,188 branch-misses # 2.67% of all branches ( +- 0.54% )
279
280 1.601607384 seconds time elapsed ( +- 0.07% )
281
282jump label enabled:
283
284 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
285
286 841.043185 task-clock # 0.533 CPUs utilized ( +- 0.12% )
287 200,004 context-switches # 0.238 M/sec ( +- 0.00% )
288 0 CPU-migrations # 0.000 M/sec ( +- 40.87% )
289 487 page-faults # 0.001 M/sec ( +- 0.05% )
290 1,432,559,428 cycles # 1.703 GHz ( +- 0.18% )
291 <not supported> stalled-cycles-frontend
292 <not supported> stalled-cycles-backend
293 1,175,363,994 instructions # 0.82 insns per cycle ( +- 0.04% )
294 206,859,359 branches # 245.956 M/sec ( +- 0.04% )
295 4,884,119 branch-misses # 2.36% of all branches ( +- 0.85% )
296
297 1.579384366 seconds time elapsed
298
299The percentage of saved branches is .7%, and we've saved 12% on
300'branch-misses'. This is where we would expect to get the most savings, since
301this optimization is about reducing the number of branches. In addition, we've
302saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.