About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / static-keys.txt




Custom Search

Based on kernel version 4.9. Page generated on 2016-12-21 14:37 EST.

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.
Hide Line Numbers
About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog
Information is copyright its respective author. All material is available from the Linux Kernel Source distributed under a GPL License. This page is provided as a free service by mjmwired.net.