Loading...
Note: File does not exist in v6.13.7.
1 Static Keys
2 -----------
3
4DEPRECATED 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);
18DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
19DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
20static_branch_likely()
21static_branch_unlikely()
22
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
29 DEFINE_STATIC_KEY_FALSE(key);
30
31 ...
32
33 if (static_branch_unlikely(&key))
34 do unlikely code
35 else
36 do likely code
37
38 ...
39 static_branch_enable(&key);
40 ...
41 static_branch_disable(&key);
42 ...
43
44The static_branch_unlikely() branch will be generated into the code with as little
45impact 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
76 if (static_branch_unlikely(&key))
77 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
95 DEFINE_STATIC_KEY_TRUE(key);
96
97or:
98
99 DEFINE_STATIC_KEY_FALSE(key);
100
101
102The key must be global, that is, it can't be allocated on the stack or dynamically
103allocated at run-time.
104
105The key is then used in code as:
106
107 if (static_branch_unlikely(&key))
108 do unlikely code
109 else
110 do likely code
111
112Or:
113
114 if (static_branch_likely(&key))
115 do likely code
116 else
117 do unlikely code
118
119Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
120be used in either static_branch_likely() or static_branch_unlikely()
121statemnts.
122
123Branch(es) can be set true via:
124
125static_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);
134 ...
135 static_branch_dec(&key);
136
137Thus, 'static_branch_inc()' means 'make the branch true', and
138'static_branch_dec()' means 'make the branch false' with appropriate
139reference counting. For example, if the key is initialized true, a
140static_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.
144
145Where 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);
152
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
158simply fall back to a traditional, load, test, and jump sequence.
159
160* select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig
161
162* #define JUMP_LABEL_NOP_SIZE, see: arch/x86/include/asm/jump_label.h
163
164* __always_inline bool arch_static_branch(struct static_key *key, bool branch), see:
165 arch/x86/include/asm/jump_label.h
166
167* __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch),
168 see: arch/x86/include/asm/jump_label.h
169
170* void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type),
171 see: arch/x86/kernel/jump_label.c
172
173* __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type),
174 see: arch/x86/kernel/jump_label.c
175
176
177* struct jump_entry, see: arch/x86/include/asm/jump_label.h
178
179
1805) Static keys / jump label analysis, results (x86_64):
181
182
183As an example, let's add the following branch to 'getppid()', such that the
184system call now looks like:
185
186SYSCALL_DEFINE0(getppid)
187{
188 int pid;
189
190+ if (static_branch_unlikely(&key))
191+ printk("I am the true branch\n");
192
193 rcu_read_lock();
194 pid = task_tgid_vnr(rcu_dereference(current->real_parent));
195 rcu_read_unlock();
196
197 return pid;
198}
199
200The resulting instructions with jump labels generated by GCC is:
201
202ffffffff81044290 <sys_getppid>:
203ffffffff81044290: 55 push %rbp
204ffffffff81044291: 48 89 e5 mov %rsp,%rbp
205ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9>
206ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
207ffffffff810442a0: 00 00
208ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
209ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
210ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
211ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr>
212ffffffff810442bc: 5d pop %rbp
213ffffffff810442bd: 48 98 cltq
214ffffffff810442bf: c3 retq
215ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi
216ffffffff810442c7: 31 c0 xor %eax,%eax
217ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk>
218ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9>
219
220Without the jump label optimization it looks like:
221
222ffffffff810441f0 <sys_getppid>:
223ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key>
224ffffffff810441f6: 55 push %rbp
225ffffffff810441f7: 48 89 e5 mov %rsp,%rbp
226ffffffff810441fa: 85 c0 test %eax,%eax
227ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35>
228ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
229ffffffff81044205: 00 00
230ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
231ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
232ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
233ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr>
234ffffffff81044221: 5d pop %rbp
235ffffffff81044222: 48 98 cltq
236ffffffff81044224: c3 retq
237ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi
238ffffffff8104422c: 31 c0 xor %eax,%eax
239ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk>
240ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe>
241ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1)
242ffffffff8104423c: 00 00 00 00
243
244Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
245vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
246to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
247label case adds:
248
2496 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
250
251If we then include the padding bytes, the jump label code saves, 16 total bytes
252of instruction memory for this small function. In this case the non-jump label
253function is 80 bytes long. Thus, we have saved 20% of the instruction
254footprint. We can in fact improve this even further, since the 5-byte no-op
255really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
256However, we have not yet implemented optimal no-op sizes (they are currently
257hard-coded).
258
259Since there are a number of static key API uses in the scheduler paths,
260'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
261performance improvement. Testing done on 3.3.0-rc2:
262
263jump label disabled:
264
265 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
266
267 855.700314 task-clock # 0.534 CPUs utilized ( +- 0.11% )
268 200,003 context-switches # 0.234 M/sec ( +- 0.00% )
269 0 CPU-migrations # 0.000 M/sec ( +- 39.58% )
270 487 page-faults # 0.001 M/sec ( +- 0.02% )
271 1,474,374,262 cycles # 1.723 GHz ( +- 0.17% )
272 <not supported> stalled-cycles-frontend
273 <not supported> stalled-cycles-backend
274 1,178,049,567 instructions # 0.80 insns per cycle ( +- 0.06% )
275 208,368,926 branches # 243.507 M/sec ( +- 0.06% )
276 5,569,188 branch-misses # 2.67% of all branches ( +- 0.54% )
277
278 1.601607384 seconds time elapsed ( +- 0.07% )
279
280jump label enabled:
281
282 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
283
284 841.043185 task-clock # 0.533 CPUs utilized ( +- 0.12% )
285 200,004 context-switches # 0.238 M/sec ( +- 0.00% )
286 0 CPU-migrations # 0.000 M/sec ( +- 40.87% )
287 487 page-faults # 0.001 M/sec ( +- 0.05% )
288 1,432,559,428 cycles # 1.703 GHz ( +- 0.18% )
289 <not supported> stalled-cycles-frontend
290 <not supported> stalled-cycles-backend
291 1,175,363,994 instructions # 0.82 insns per cycle ( +- 0.04% )
292 206,859,359 branches # 245.956 M/sec ( +- 0.04% )
293 4,884,119 branch-misses # 2.36% of all branches ( +- 0.85% )
294
295 1.579384366 seconds time elapsed
296
297The percentage of saved branches is .7%, and we've saved 12% on
298'branch-misses'. This is where we would expect to get the most savings, since
299this optimization is about reducing the number of branches. In addition, we've
300saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.