blob: 477927becacba69ee4bdea2203dd796979d14449 [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);
Jonathan Corbet1975dbc2015-09-14 17:11:05 -060018static_branch_likely()
19static_branch_unlikely()
Jason Baron1cfa60d2012-02-21 15:03:30 -050020
210) Abstract
22
23Static keys allows the inclusion of seldom used features in
24performance-sensitive fast-path kernel code, via a GCC feature and a code
25patching technique. A quick example:
26
Jason Baron412758c2015-07-30 03:59:48 +000027 DEFINE_STATIC_KEY_FALSE(key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050028
29 ...
30
Jason Baron412758c2015-07-30 03:59:48 +000031 if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -050032 do unlikely code
33 else
34 do likely code
35
36 ...
Jason Baron412758c2015-07-30 03:59:48 +000037 static_branch_enable(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050038 ...
Jason Baron412758c2015-07-30 03:59:48 +000039 static_branch_disable(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050040 ...
41
Jason Baron412758c2015-07-30 03:59:48 +000042The static_branch_unlikely() branch will be generated into the code with as little
Jason Baron1cfa60d2012-02-21 15:03:30 -050043impact to the likely code path as possible.
44
45
461) Motivation
47
48
49Currently, tracepoints are implemented using a conditional branch. The
50conditional check requires checking a global variable for each tracepoint.
51Although the overhead of this check is small, it increases when the memory
52cache comes under pressure (memory cache lines for these global variables may
53be shared with other memory accesses). As we increase the number of tracepoints
54in the kernel this overhead may become more of an issue. In addition,
55tracepoints are often dormant (disabled) and provide no direct kernel
56functionality. Thus, it is highly desirable to reduce their impact as much as
57possible. Although tracepoints are the original motivation for this work, other
58kernel code paths should be able to make use of the static keys facility.
59
60
612) Solution
62
63
64gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:
65
66http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html
67
68Using the 'asm goto', we can create branches that are either taken or not taken
69by default, without the need to check memory. Then, at run-time, we can patch
70the branch site to change the branch direction.
71
72For example, if we have a simple branch that is disabled by default:
73
Jason Baron412758c2015-07-30 03:59:48 +000074 if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -050075 printk("I am the true branch\n");
76
77Thus, by default the 'printk' will not be emitted. And the code generated will
78consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
79straight-line code path. When the branch is 'flipped', we will patch the
80'no-op' in the straight-line codepath with a 'jump' instruction to the
81out-of-line true branch. Thus, changing branch direction is expensive but
82branch selection is basically 'free'. That is the basic tradeoff of this
83optimization.
84
85This lowlevel patching mechanism is called 'jump label patching', and it gives
86the basis for the static keys facility.
87
883) Static key label API, usage and examples:
89
90
91In order to make use of this optimization you must first define a key:
92
Jason Baron412758c2015-07-30 03:59:48 +000093 DEFINE_STATIC_KEY_TRUE(key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050094
95or:
96
Jason Baron412758c2015-07-30 03:59:48 +000097 DEFINE_STATIC_KEY_FALSE(key);
Jason Baron1cfa60d2012-02-21 15:03:30 -050098
Jason Baron412758c2015-07-30 03:59:48 +000099
100The key must be global, that is, it can't be allocated on the stack or dynamically
Jason Baron1cfa60d2012-02-21 15:03:30 -0500101allocated at run-time.
102
103The key is then used in code as:
104
Jason Baron412758c2015-07-30 03:59:48 +0000105 if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -0500106 do unlikely code
107 else
108 do likely code
109
110Or:
111
Jason Baron412758c2015-07-30 03:59:48 +0000112 if (static_branch_likely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -0500113 do likely code
114 else
115 do unlikely code
116
Jason Baron412758c2015-07-30 03:59:48 +0000117Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
118be used in either static_branch_likely() or static_branch_unlikely()
119statemnts.
Jason Baron1cfa60d2012-02-21 15:03:30 -0500120
Jason Baron412758c2015-07-30 03:59:48 +0000121Branch(es) can be set true via:
Jason Baron1cfa60d2012-02-21 15:03:30 -0500122
Jason Baron412758c2015-07-30 03:59:48 +0000123static_branch_enable(&key);
124
125or false via:
126
127static_branch_disable(&key);
128
129The branch(es) can then be switched via reference counts:
130
131 static_branch_inc(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -0500132 ...
Jason Baron412758c2015-07-30 03:59:48 +0000133 static_branch_dec(&key);
Jason Baron1cfa60d2012-02-21 15:03:30 -0500134
Jason Baron412758c2015-07-30 03:59:48 +0000135Thus, 'static_branch_inc()' means 'make the branch true', and
136'static_branch_dec()' means 'make the branch false' with appropriate
Jason Baron1cfa60d2012-02-21 15:03:30 -0500137reference counting. For example, if the key is initialized true, a
Jason Baron412758c2015-07-30 03:59:48 +0000138static_branch_dec(), will switch the branch to false. And a subsequent
139static_branch_inc(), will change the branch back to true. Likewise, if the
140key is initialized false, a 'static_branch_inc()', will change the branch to
141true. And then a 'static_branch_dec()', will again make the branch false.
Jason Baron1cfa60d2012-02-21 15:03:30 -0500142
143
1444) Architecture level code patching interface, 'jump labels'
145
146
147There are a few functions and macros that architectures must implement in order
148to take advantage of this optimization. If there is no architecture support, we
149simply fall back to a traditional, load, test, and jump sequence.
150
151* select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig
152
153* #define JUMP_LABEL_NOP_SIZE, see: arch/x86/include/asm/jump_label.h
154
Jason Baron412758c2015-07-30 03:59:48 +0000155* __always_inline bool arch_static_branch(struct static_key *key, bool branch), see:
Jason Baron1cfa60d2012-02-21 15:03:30 -0500156 arch/x86/include/asm/jump_label.h
157
Jason Baron412758c2015-07-30 03:59:48 +0000158* __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch),
159 see: arch/x86/include/asm/jump_label.h
160
Jason Baron1cfa60d2012-02-21 15:03:30 -0500161* void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type),
162 see: arch/x86/kernel/jump_label.c
163
164* __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type),
165 see: arch/x86/kernel/jump_label.c
166
167
168* struct jump_entry, see: arch/x86/include/asm/jump_label.h
169
170
1715) Static keys / jump label analysis, results (x86_64):
172
173
174As an example, let's add the following branch to 'getppid()', such that the
175system call now looks like:
176
177SYSCALL_DEFINE0(getppid)
178{
179 int pid;
180
Jason Baron412758c2015-07-30 03:59:48 +0000181+ if (static_branch_unlikely(&key))
Jason Baron1cfa60d2012-02-21 15:03:30 -0500182+ printk("I am the true branch\n");
183
184 rcu_read_lock();
185 pid = task_tgid_vnr(rcu_dereference(current->real_parent));
186 rcu_read_unlock();
187
188 return pid;
189}
190
191The resulting instructions with jump labels generated by GCC is:
192
193ffffffff81044290 <sys_getppid>:
194ffffffff81044290: 55 push %rbp
195ffffffff81044291: 48 89 e5 mov %rsp,%rbp
196ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9>
197ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
198ffffffff810442a0: 00 00
199ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
200ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
201ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
202ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr>
203ffffffff810442bc: 5d pop %rbp
204ffffffff810442bd: 48 98 cltq
205ffffffff810442bf: c3 retq
206ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi
207ffffffff810442c7: 31 c0 xor %eax,%eax
208ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk>
209ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9>
210
211Without the jump label optimization it looks like:
212
213ffffffff810441f0 <sys_getppid>:
214ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key>
215ffffffff810441f6: 55 push %rbp
216ffffffff810441f7: 48 89 e5 mov %rsp,%rbp
217ffffffff810441fa: 85 c0 test %eax,%eax
218ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35>
219ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
220ffffffff81044205: 00 00
221ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
222ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
223ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
224ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr>
225ffffffff81044221: 5d pop %rbp
226ffffffff81044222: 48 98 cltq
227ffffffff81044224: c3 retq
228ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi
229ffffffff8104422c: 31 c0 xor %eax,%eax
230ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk>
231ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe>
232ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1)
233ffffffff8104423c: 00 00 00 00
234
235Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
236vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
237to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
238label case adds:
239
2406 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
241
242If we then include the padding bytes, the jump label code saves, 16 total bytes
Masanari Iidac94bed8e2012-04-10 00:22:13 +0900243of instruction memory for this small function. In this case the non-jump label
Xishi Qiuc79a8d82013-11-06 13:18:21 -0800244function is 80 bytes long. Thus, we have saved 20% of the instruction
Jason Baron1cfa60d2012-02-21 15:03:30 -0500245footprint. We can in fact improve this even further, since the 5-byte no-op
246really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
247However, we have not yet implemented optimal no-op sizes (they are currently
248hard-coded).
249
250Since there are a number of static key API uses in the scheduler paths,
251'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
252performance improvement. Testing done on 3.3.0-rc2:
253
254jump label disabled:
255
256 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
257
258 855.700314 task-clock # 0.534 CPUs utilized ( +- 0.11% )
259 200,003 context-switches # 0.234 M/sec ( +- 0.00% )
260 0 CPU-migrations # 0.000 M/sec ( +- 39.58% )
261 487 page-faults # 0.001 M/sec ( +- 0.02% )
262 1,474,374,262 cycles # 1.723 GHz ( +- 0.17% )
263 <not supported> stalled-cycles-frontend
264 <not supported> stalled-cycles-backend
265 1,178,049,567 instructions # 0.80 insns per cycle ( +- 0.06% )
266 208,368,926 branches # 243.507 M/sec ( +- 0.06% )
267 5,569,188 branch-misses # 2.67% of all branches ( +- 0.54% )
268
269 1.601607384 seconds time elapsed ( +- 0.07% )
270
271jump label enabled:
272
273 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
274
275 841.043185 task-clock # 0.533 CPUs utilized ( +- 0.12% )
276 200,004 context-switches # 0.238 M/sec ( +- 0.00% )
277 0 CPU-migrations # 0.000 M/sec ( +- 40.87% )
278 487 page-faults # 0.001 M/sec ( +- 0.05% )
279 1,432,559,428 cycles # 1.703 GHz ( +- 0.18% )
280 <not supported> stalled-cycles-frontend
281 <not supported> stalled-cycles-backend
282 1,175,363,994 instructions # 0.82 insns per cycle ( +- 0.04% )
283 206,859,359 branches # 245.956 M/sec ( +- 0.04% )
284 4,884,119 branch-misses # 2.36% of all branches ( +- 0.85% )
285
286 1.579384366 seconds time elapsed
287
288The percentage of saved branches is .7%, and we've saved 12% on
289'branch-misses'. This is where we would expect to get the most savings, since
290this optimization is about reducing the number of branches. In addition, we've
291saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.