Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 1 | Static Keys |
| 2 | ----------- |
| 3 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 4 | DEPRECATED API: |
| 5 | |
| 6 | The use of 'struct static_key' directly, is now DEPRECATED. In addition |
| 7 | static_key_{true,false}() is also DEPRECATED. IE DO NOT use the following: |
| 8 | |
| 9 | struct static_key false = STATIC_KEY_INIT_FALSE; |
| 10 | struct static_key true = STATIC_KEY_INIT_TRUE; |
| 11 | static_key_true() |
| 12 | static_key_false() |
| 13 | |
| 14 | The updated API replacements are: |
| 15 | |
| 16 | DEFINE_STATIC_KEY_TRUE(key); |
| 17 | DEFINE_STATIC_KEY_FALSE(key); |
Catalin Marinas | ef0da55 | 2016-09-05 18:25:47 +0100 | [diff] [blame] | 18 | DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count); |
| 19 | DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count); |
Jonathan Corbet | 1975dbc | 2015-09-14 17:11:05 -0600 | [diff] [blame] | 20 | static_branch_likely() |
| 21 | static_branch_unlikely() |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 22 | |
| 23 | 0) Abstract |
| 24 | |
| 25 | Static keys allows the inclusion of seldom used features in |
| 26 | performance-sensitive fast-path kernel code, via a GCC feature and a code |
| 27 | patching technique. A quick example: |
| 28 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 29 | DEFINE_STATIC_KEY_FALSE(key); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 30 | |
| 31 | ... |
| 32 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 33 | if (static_branch_unlikely(&key)) |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 34 | do unlikely code |
| 35 | else |
| 36 | do likely code |
| 37 | |
| 38 | ... |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 39 | static_branch_enable(&key); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 40 | ... |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 41 | static_branch_disable(&key); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 42 | ... |
| 43 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 44 | The static_branch_unlikely() branch will be generated into the code with as little |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 45 | impact to the likely code path as possible. |
| 46 | |
| 47 | |
| 48 | 1) Motivation |
| 49 | |
| 50 | |
| 51 | Currently, tracepoints are implemented using a conditional branch. The |
| 52 | conditional check requires checking a global variable for each tracepoint. |
| 53 | Although the overhead of this check is small, it increases when the memory |
| 54 | cache comes under pressure (memory cache lines for these global variables may |
| 55 | be shared with other memory accesses). As we increase the number of tracepoints |
| 56 | in the kernel this overhead may become more of an issue. In addition, |
| 57 | tracepoints are often dormant (disabled) and provide no direct kernel |
| 58 | functionality. Thus, it is highly desirable to reduce their impact as much as |
| 59 | possible. Although tracepoints are the original motivation for this work, other |
| 60 | kernel code paths should be able to make use of the static keys facility. |
| 61 | |
| 62 | |
| 63 | 2) Solution |
| 64 | |
| 65 | |
| 66 | gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label: |
| 67 | |
| 68 | http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html |
| 69 | |
| 70 | Using the 'asm goto', we can create branches that are either taken or not taken |
| 71 | by default, without the need to check memory. Then, at run-time, we can patch |
| 72 | the branch site to change the branch direction. |
| 73 | |
| 74 | For example, if we have a simple branch that is disabled by default: |
| 75 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 76 | if (static_branch_unlikely(&key)) |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 77 | printk("I am the true branch\n"); |
| 78 | |
| 79 | Thus, by default the 'printk' will not be emitted. And the code generated will |
| 80 | consist of a single atomic 'no-op' instruction (5 bytes on x86), in the |
| 81 | straight-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 |
| 83 | out-of-line true branch. Thus, changing branch direction is expensive but |
| 84 | branch selection is basically 'free'. That is the basic tradeoff of this |
| 85 | optimization. |
| 86 | |
| 87 | This lowlevel patching mechanism is called 'jump label patching', and it gives |
| 88 | the basis for the static keys facility. |
| 89 | |
| 90 | 3) Static key label API, usage and examples: |
| 91 | |
| 92 | |
| 93 | In order to make use of this optimization you must first define a key: |
| 94 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 95 | DEFINE_STATIC_KEY_TRUE(key); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 96 | |
| 97 | or: |
| 98 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 99 | DEFINE_STATIC_KEY_FALSE(key); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 100 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 101 | |
| 102 | The key must be global, that is, it can't be allocated on the stack or dynamically |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 103 | allocated at run-time. |
| 104 | |
| 105 | The key is then used in code as: |
| 106 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 107 | if (static_branch_unlikely(&key)) |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 108 | do unlikely code |
| 109 | else |
| 110 | do likely code |
| 111 | |
| 112 | Or: |
| 113 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 114 | if (static_branch_likely(&key)) |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 115 | do likely code |
| 116 | else |
| 117 | do unlikely code |
| 118 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 119 | Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may |
| 120 | be used in either static_branch_likely() or static_branch_unlikely() |
| 121 | statemnts. |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 122 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 123 | Branch(es) can be set true via: |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 124 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 125 | static_branch_enable(&key); |
| 126 | |
| 127 | or false via: |
| 128 | |
| 129 | static_branch_disable(&key); |
| 130 | |
| 131 | The branch(es) can then be switched via reference counts: |
| 132 | |
| 133 | static_branch_inc(&key); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 134 | ... |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 135 | static_branch_dec(&key); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 136 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 137 | Thus, 'static_branch_inc()' means 'make the branch true', and |
| 138 | 'static_branch_dec()' means 'make the branch false' with appropriate |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 139 | reference counting. For example, if the key is initialized true, a |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 140 | static_branch_dec(), will switch the branch to false. And a subsequent |
| 141 | static_branch_inc(), will change the branch back to true. Likewise, if the |
| 142 | key is initialized false, a 'static_branch_inc()', will change the branch to |
| 143 | true. And then a 'static_branch_dec()', will again make the branch false. |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 144 | |
Catalin Marinas | ef0da55 | 2016-09-05 18:25:47 +0100 | [diff] [blame] | 145 | Where an array of keys is required, it can be defined as: |
| 146 | |
| 147 | DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count); |
| 148 | |
| 149 | or: |
| 150 | |
| 151 | DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count); |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 152 | |
| 153 | 4) Architecture level code patching interface, 'jump labels' |
| 154 | |
| 155 | |
| 156 | There are a few functions and macros that architectures must implement in order |
| 157 | to take advantage of this optimization. If there is no architecture support, we |
| 158 | simply 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 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 164 | * __always_inline bool arch_static_branch(struct static_key *key, bool branch), see: |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 165 | arch/x86/include/asm/jump_label.h |
| 166 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 167 | * __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch), |
| 168 | see: arch/x86/include/asm/jump_label.h |
| 169 | |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 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 | |
| 180 | 5) Static keys / jump label analysis, results (x86_64): |
| 181 | |
| 182 | |
| 183 | As an example, let's add the following branch to 'getppid()', such that the |
| 184 | system call now looks like: |
| 185 | |
| 186 | SYSCALL_DEFINE0(getppid) |
| 187 | { |
| 188 | int pid; |
| 189 | |
Jason Baron | 412758c | 2015-07-30 03:59:48 +0000 | [diff] [blame] | 190 | + if (static_branch_unlikely(&key)) |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 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 | |
| 200 | The resulting instructions with jump labels generated by GCC is: |
| 201 | |
| 202 | ffffffff81044290 <sys_getppid>: |
| 203 | ffffffff81044290: 55 push %rbp |
| 204 | ffffffff81044291: 48 89 e5 mov %rsp,%rbp |
| 205 | ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9> |
| 206 | ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax |
| 207 | ffffffff810442a0: 00 00 |
| 208 | ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax |
| 209 | ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax |
| 210 | ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi |
| 211 | ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr> |
| 212 | ffffffff810442bc: 5d pop %rbp |
| 213 | ffffffff810442bd: 48 98 cltq |
| 214 | ffffffff810442bf: c3 retq |
| 215 | ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi |
| 216 | ffffffff810442c7: 31 c0 xor %eax,%eax |
| 217 | ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk> |
| 218 | ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9> |
| 219 | |
| 220 | Without the jump label optimization it looks like: |
| 221 | |
| 222 | ffffffff810441f0 <sys_getppid>: |
| 223 | ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key> |
| 224 | ffffffff810441f6: 55 push %rbp |
| 225 | ffffffff810441f7: 48 89 e5 mov %rsp,%rbp |
| 226 | ffffffff810441fa: 85 c0 test %eax,%eax |
| 227 | ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35> |
| 228 | ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax |
| 229 | ffffffff81044205: 00 00 |
| 230 | ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax |
| 231 | ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax |
| 232 | ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi |
| 233 | ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr> |
| 234 | ffffffff81044221: 5d pop %rbp |
| 235 | ffffffff81044222: 48 98 cltq |
| 236 | ffffffff81044224: c3 retq |
| 237 | ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi |
| 238 | ffffffff8104422c: 31 c0 xor %eax,%eax |
| 239 | ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk> |
| 240 | ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe> |
| 241 | ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1) |
| 242 | ffffffff8104423c: 00 00 00 00 |
| 243 | |
| 244 | Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction |
| 245 | vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched |
| 246 | to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump |
| 247 | label case adds: |
| 248 | |
| 249 | 6 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes. |
| 250 | |
| 251 | If we then include the padding bytes, the jump label code saves, 16 total bytes |
Masanari Iida | c94bed8e | 2012-04-10 00:22:13 +0900 | [diff] [blame] | 252 | of instruction memory for this small function. In this case the non-jump label |
Xishi Qiu | c79a8d8 | 2013-11-06 13:18:21 -0800 | [diff] [blame] | 253 | function is 80 bytes long. Thus, we have saved 20% of the instruction |
Jason Baron | 1cfa60d | 2012-02-21 15:03:30 -0500 | [diff] [blame] | 254 | footprint. We can in fact improve this even further, since the 5-byte no-op |
| 255 | really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp. |
| 256 | However, we have not yet implemented optimal no-op sizes (they are currently |
| 257 | hard-coded). |
| 258 | |
| 259 | Since 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 |
| 261 | performance improvement. Testing done on 3.3.0-rc2: |
| 262 | |
| 263 | jump 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 | |
| 280 | jump 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 | |
| 297 | The 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 |
| 299 | this optimization is about reducing the number of branches. In addition, we've |
| 300 | saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time. |