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); 18static_branch_likely() 19static_branch_unlikely() 20 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 27 DEFINE_STATIC_KEY_FALSE(key); 28 29 ... 30 31 if (static_branch_unlikely(&key)) 32 do unlikely code 33 else 34 do likely code 35 36 ... 37 static_branch_enable(&key); 38 ... 39 static_branch_disable(&key); 40 ... 41 42The static_branch_unlikely() branch will be generated into the code with as little 43impact 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 74 if (static_branch_unlikely(&key)) 75 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 93 DEFINE_STATIC_KEY_TRUE(key); 94 95or: 96 97 DEFINE_STATIC_KEY_FALSE(key); 98 99 100The key must be global, that is, it can't be allocated on the stack or dynamically 101allocated at run-time. 102 103The key is then used in code as: 104 105 if (static_branch_unlikely(&key)) 106 do unlikely code 107 else 108 do likely code 109 110Or: 111 112 if (static_branch_likely(&key)) 113 do likely code 114 else 115 do unlikely code 116 117Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may 118be used in either static_branch_likely() or static_branch_unlikely() 119statemnts. 120 121Branch(es) can be set true via: 122 123static_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); 132 ... 133 static_branch_dec(&key); 134 135Thus, 'static_branch_inc()' means 'make the branch true', and 136'static_branch_dec()' means 'make the branch false' with appropriate 137reference counting. For example, if the key is initialized true, a 138static_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. 142 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 155* __always_inline bool arch_static_branch(struct static_key *key, bool branch), see: 156 arch/x86/include/asm/jump_label.h 157 158* __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch), 159 see: arch/x86/include/asm/jump_label.h 160 161* 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 181+ if (static_branch_unlikely(&key)) 182+ 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 243of instruction memory for this small function. In this case the non-jump label 244function is 80 bytes long. Thus, we have saved 20% of the instruction 245footprint. 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. 292