• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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