Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/Documentation/static-keys.txt

  1                         Static Keys
  2                         -----------
  3 
  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);
 18 DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
 19 DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
 20 static_branch_likely()
 21 static_branch_unlikely()
 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 
 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 
 44 The static_branch_unlikely() branch will be generated into the code with as little
 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 
 76         if (static_branch_unlikely(&key))
 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 
 95         DEFINE_STATIC_KEY_TRUE(key);
 96 
 97 or:
 98 
 99         DEFINE_STATIC_KEY_FALSE(key);
100 
101 
102 The key must be global, that is, it can't be allocated on the stack or dynamically
103 allocated at run-time.
104 
105 The 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 
112 Or:
113 
114         if (static_branch_likely(&key))
115                 do likely code
116         else
117                 do unlikely code
118 
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.
122 
123 Branch(es) can be set true via:
124 
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);
134         ...
135         static_branch_dec(&key);
136 
137 Thus, 'static_branch_inc()' means 'make the branch true', and
138 'static_branch_dec()' means 'make the branch false' with appropriate
139 reference counting. For example, if the key is initialized true, a
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.
144 
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);
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 
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 
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 
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 
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
252 of instruction memory for this small function. In this case the non-jump label
253 function is 80 bytes long. Thus, we have saved 20% of the instruction
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.

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us