0001 ===========
0002 Static Keys
0003 ===========
0004
0005 .. warning::
0006
0007 DEPRECATED API:
0008
0009 The use of 'struct static_key' directly, is now DEPRECATED. In addition
0010 static_key_{true,false}() is also DEPRECATED. IE DO NOT use the following::
0011
0012 struct static_key false = STATIC_KEY_INIT_FALSE;
0013 struct static_key true = STATIC_KEY_INIT_TRUE;
0014 static_key_true()
0015 static_key_false()
0016
0017 The updated API replacements are::
0018
0019 DEFINE_STATIC_KEY_TRUE(key);
0020 DEFINE_STATIC_KEY_FALSE(key);
0021 DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
0022 DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
0023 static_branch_likely()
0024 static_branch_unlikely()
0025
0026 Abstract
0027 ========
0028
0029 Static keys allows the inclusion of seldom used features in
0030 performance-sensitive fast-path kernel code, via a GCC feature and a code
0031 patching technique. A quick example::
0032
0033 DEFINE_STATIC_KEY_FALSE(key);
0034
0035 ...
0036
0037 if (static_branch_unlikely(&key))
0038 do unlikely code
0039 else
0040 do likely code
0041
0042 ...
0043 static_branch_enable(&key);
0044 ...
0045 static_branch_disable(&key);
0046 ...
0047
0048 The static_branch_unlikely() branch will be generated into the code with as little
0049 impact to the likely code path as possible.
0050
0051
0052 Motivation
0053 ==========
0054
0055
0056 Currently, tracepoints are implemented using a conditional branch. The
0057 conditional check requires checking a global variable for each tracepoint.
0058 Although the overhead of this check is small, it increases when the memory
0059 cache comes under pressure (memory cache lines for these global variables may
0060 be shared with other memory accesses). As we increase the number of tracepoints
0061 in the kernel this overhead may become more of an issue. In addition,
0062 tracepoints are often dormant (disabled) and provide no direct kernel
0063 functionality. Thus, it is highly desirable to reduce their impact as much as
0064 possible. Although tracepoints are the original motivation for this work, other
0065 kernel code paths should be able to make use of the static keys facility.
0066
0067
0068 Solution
0069 ========
0070
0071
0072 gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:
0073
0074 https://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html
0075
0076 Using the 'asm goto', we can create branches that are either taken or not taken
0077 by default, without the need to check memory. Then, at run-time, we can patch
0078 the branch site to change the branch direction.
0079
0080 For example, if we have a simple branch that is disabled by default::
0081
0082 if (static_branch_unlikely(&key))
0083 printk("I am the true branch\n");
0084
0085 Thus, by default the 'printk' will not be emitted. And the code generated will
0086 consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
0087 straight-line code path. When the branch is 'flipped', we will patch the
0088 'no-op' in the straight-line codepath with a 'jump' instruction to the
0089 out-of-line true branch. Thus, changing branch direction is expensive but
0090 branch selection is basically 'free'. That is the basic tradeoff of this
0091 optimization.
0092
0093 This lowlevel patching mechanism is called 'jump label patching', and it gives
0094 the basis for the static keys facility.
0095
0096 Static key label API, usage and examples
0097 ========================================
0098
0099
0100 In order to make use of this optimization you must first define a key::
0101
0102 DEFINE_STATIC_KEY_TRUE(key);
0103
0104 or::
0105
0106 DEFINE_STATIC_KEY_FALSE(key);
0107
0108
0109 The key must be global, that is, it can't be allocated on the stack or dynamically
0110 allocated at run-time.
0111
0112 The key is then used in code as::
0113
0114 if (static_branch_unlikely(&key))
0115 do unlikely code
0116 else
0117 do likely code
0118
0119 Or::
0120
0121 if (static_branch_likely(&key))
0122 do likely code
0123 else
0124 do unlikely code
0125
0126 Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
0127 be used in either static_branch_likely() or static_branch_unlikely()
0128 statements.
0129
0130 Branch(es) can be set true via::
0131
0132 static_branch_enable(&key);
0133
0134 or false via::
0135
0136 static_branch_disable(&key);
0137
0138 The branch(es) can then be switched via reference counts::
0139
0140 static_branch_inc(&key);
0141 ...
0142 static_branch_dec(&key);
0143
0144 Thus, 'static_branch_inc()' means 'make the branch true', and
0145 'static_branch_dec()' means 'make the branch false' with appropriate
0146 reference counting. For example, if the key is initialized true, a
0147 static_branch_dec(), will switch the branch to false. And a subsequent
0148 static_branch_inc(), will change the branch back to true. Likewise, if the
0149 key is initialized false, a 'static_branch_inc()', will change the branch to
0150 true. And then a 'static_branch_dec()', will again make the branch false.
0151
0152 The state and the reference count can be retrieved with 'static_key_enabled()'
0153 and 'static_key_count()'. In general, if you use these functions, they
0154 should be protected with the same mutex used around the enable/disable
0155 or increment/decrement function.
0156
0157 Note that switching branches results in some locks being taken,
0158 particularly the CPU hotplug lock (in order to avoid races against
0159 CPUs being brought in the kernel while the kernel is getting
0160 patched). Calling the static key API from within a hotplug notifier is
0161 thus a sure deadlock recipe. In order to still allow use of the
0162 functionality, the following functions are provided:
0163
0164 static_key_enable_cpuslocked()
0165 static_key_disable_cpuslocked()
0166 static_branch_enable_cpuslocked()
0167 static_branch_disable_cpuslocked()
0168
0169 These functions are *not* general purpose, and must only be used when
0170 you really know that you're in the above context, and no other.
0171
0172 Where an array of keys is required, it can be defined as::
0173
0174 DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
0175
0176 or::
0177
0178 DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
0179
0180 4) Architecture level code patching interface, 'jump labels'
0181
0182
0183 There are a few functions and macros that architectures must implement in order
0184 to take advantage of this optimization. If there is no architecture support, we
0185 simply fall back to a traditional, load, test, and jump sequence. Also, the
0186 struct jump_entry table must be at least 4-byte aligned because the
0187 static_key->entry field makes use of the two least significant bits.
0188
0189 * ``select HAVE_ARCH_JUMP_LABEL``,
0190 see: arch/x86/Kconfig
0191
0192 * ``#define JUMP_LABEL_NOP_SIZE``,
0193 see: arch/x86/include/asm/jump_label.h
0194
0195 * ``__always_inline bool arch_static_branch(struct static_key *key, bool branch)``,
0196 see: arch/x86/include/asm/jump_label.h
0197
0198 * ``__always_inline bool arch_static_branch_jump(struct static_key *key, bool branch)``,
0199 see: arch/x86/include/asm/jump_label.h
0200
0201 * ``void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type)``,
0202 see: arch/x86/kernel/jump_label.c
0203
0204 * ``struct jump_entry``,
0205 see: arch/x86/include/asm/jump_label.h
0206
0207
0208 5) Static keys / jump label analysis, results (x86_64):
0209
0210
0211 As an example, let's add the following branch to 'getppid()', such that the
0212 system call now looks like::
0213
0214 SYSCALL_DEFINE0(getppid)
0215 {
0216 int pid;
0217
0218 + if (static_branch_unlikely(&key))
0219 + printk("I am the true branch\n");
0220
0221 rcu_read_lock();
0222 pid = task_tgid_vnr(rcu_dereference(current->real_parent));
0223 rcu_read_unlock();
0224
0225 return pid;
0226 }
0227
0228 The resulting instructions with jump labels generated by GCC is::
0229
0230 ffffffff81044290 <sys_getppid>:
0231 ffffffff81044290: 55 push %rbp
0232 ffffffff81044291: 48 89 e5 mov %rsp,%rbp
0233 ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9>
0234 ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
0235 ffffffff810442a0: 00 00
0236 ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
0237 ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
0238 ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
0239 ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr>
0240 ffffffff810442bc: 5d pop %rbp
0241 ffffffff810442bd: 48 98 cltq
0242 ffffffff810442bf: c3 retq
0243 ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi
0244 ffffffff810442c7: 31 c0 xor %eax,%eax
0245 ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk>
0246 ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9>
0247
0248 Without the jump label optimization it looks like::
0249
0250 ffffffff810441f0 <sys_getppid>:
0251 ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key>
0252 ffffffff810441f6: 55 push %rbp
0253 ffffffff810441f7: 48 89 e5 mov %rsp,%rbp
0254 ffffffff810441fa: 85 c0 test %eax,%eax
0255 ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35>
0256 ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
0257 ffffffff81044205: 00 00
0258 ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
0259 ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
0260 ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
0261 ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr>
0262 ffffffff81044221: 5d pop %rbp
0263 ffffffff81044222: 48 98 cltq
0264 ffffffff81044224: c3 retq
0265 ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi
0266 ffffffff8104422c: 31 c0 xor %eax,%eax
0267 ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk>
0268 ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe>
0269 ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1)
0270 ffffffff8104423c: 00 00 00 00
0271
0272 Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
0273 vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
0274 to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
0275 label case adds::
0276
0277 6 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
0278
0279 If we then include the padding bytes, the jump label code saves, 16 total bytes
0280 of instruction memory for this small function. In this case the non-jump label
0281 function is 80 bytes long. Thus, we have saved 20% of the instruction
0282 footprint. We can in fact improve this even further, since the 5-byte no-op
0283 really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
0284 However, we have not yet implemented optimal no-op sizes (they are currently
0285 hard-coded).
0286
0287 Since there are a number of static key API uses in the scheduler paths,
0288 'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
0289 performance improvement. Testing done on 3.3.0-rc2:
0290
0291 jump label disabled::
0292
0293 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
0294
0295 855.700314 task-clock # 0.534 CPUs utilized ( +- 0.11% )
0296 200,003 context-switches # 0.234 M/sec ( +- 0.00% )
0297 0 CPU-migrations # 0.000 M/sec ( +- 39.58% )
0298 487 page-faults # 0.001 M/sec ( +- 0.02% )
0299 1,474,374,262 cycles # 1.723 GHz ( +- 0.17% )
0300 <not supported> stalled-cycles-frontend
0301 <not supported> stalled-cycles-backend
0302 1,178,049,567 instructions # 0.80 insns per cycle ( +- 0.06% )
0303 208,368,926 branches # 243.507 M/sec ( +- 0.06% )
0304 5,569,188 branch-misses # 2.67% of all branches ( +- 0.54% )
0305
0306 1.601607384 seconds time elapsed ( +- 0.07% )
0307
0308 jump label enabled::
0309
0310 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
0311
0312 841.043185 task-clock # 0.533 CPUs utilized ( +- 0.12% )
0313 200,004 context-switches # 0.238 M/sec ( +- 0.00% )
0314 0 CPU-migrations # 0.000 M/sec ( +- 40.87% )
0315 487 page-faults # 0.001 M/sec ( +- 0.05% )
0316 1,432,559,428 cycles # 1.703 GHz ( +- 0.18% )
0317 <not supported> stalled-cycles-frontend
0318 <not supported> stalled-cycles-backend
0319 1,175,363,994 instructions # 0.82 insns per cycle ( +- 0.04% )
0320 206,859,359 branches # 245.956 M/sec ( +- 0.04% )
0321 4,884,119 branch-misses # 2.36% of all branches ( +- 0.85% )
0322
0323 1.579384366 seconds time elapsed
0324
0325 The percentage of saved branches is .7%, and we've saved 12% on
0326 'branch-misses'. This is where we would expect to get the most savings, since
0327 this optimization is about reducing the number of branches. In addition, we've
0328 saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.
