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