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