static-keys.txt 13 KB
Newer Older
1 2 3
===========
Static Keys
===========
4

5
.. warning::
6

7
   DEPRECATED API:
8

9 10
   The use of 'struct static_key' directly, is now DEPRECATED. In addition
   static_key_{true,false}() is also DEPRECATED. IE DO NOT use the following::
11

12 13 14 15
	struct static_key false = STATIC_KEY_INIT_FALSE;
	struct static_key true = STATIC_KEY_INIT_TRUE;
	static_key_true()
	static_key_false()
16

17
   The updated API replacements are::
18

19 20 21 22 23 24 25 26 27
	DEFINE_STATIC_KEY_TRUE(key);
	DEFINE_STATIC_KEY_FALSE(key);
	DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
	DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
	static_branch_likely()
	static_branch_unlikely()

Abstract
========
28 29 30

Static keys allows the inclusion of seldom used features in
performance-sensitive fast-path kernel code, via a GCC feature and a code
31
patching technique. A quick example::
32

33
	DEFINE_STATIC_KEY_FALSE(key);
34 35 36

	...

37
        if (static_branch_unlikely(&key))
38 39 40 41 42
                do unlikely code
        else
                do likely code

	...
43
	static_branch_enable(&key);
44
	...
45
	static_branch_disable(&key);
46 47
	...

48
The static_branch_unlikely() branch will be generated into the code with as little
49 50 51
impact to the likely code path as possible.


52 53
Motivation
==========
54 55 56 57 58 59 60 61 62 63 64 65 66 67


Currently, tracepoints are implemented using a conditional branch. The
conditional check requires checking a global variable for each tracepoint.
Although the overhead of this check is small, it increases when the memory
cache comes under pressure (memory cache lines for these global variables may
be shared with other memory accesses). As we increase the number of tracepoints
in the kernel this overhead may become more of an issue. In addition,
tracepoints are often dormant (disabled) and provide no direct kernel
functionality. Thus, it is highly desirable to reduce their impact as much as
possible. Although tracepoints are the original motivation for this work, other
kernel code paths should be able to make use of the static keys facility.


68 69
Solution
========
70 71 72 73 74 75 76 77 78 79


gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:

http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html

Using the 'asm goto', we can create branches that are either taken or not taken
by default, without the need to check memory. Then, at run-time, we can patch
the branch site to change the branch direction.

80
For example, if we have a simple branch that is disabled by default::
81

82
	if (static_branch_unlikely(&key))
83 84 85 86 87 88 89 90 91 92 93 94 95
		printk("I am the true branch\n");

Thus, by default the 'printk' will not be emitted. And the code generated will
consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
straight-line code path. When the branch is 'flipped', we will patch the
'no-op' in the straight-line codepath with a 'jump' instruction to the
out-of-line true branch. Thus, changing branch direction is expensive but
branch selection is basically 'free'. That is the basic tradeoff of this
optimization.

This lowlevel patching mechanism is called 'jump label patching', and it gives
the basis for the static keys facility.

96 97
Static key label API, usage and examples
========================================
98 99


100
In order to make use of this optimization you must first define a key::
101

102
	DEFINE_STATIC_KEY_TRUE(key);
103

104
or::
105

106 107
	DEFINE_STATIC_KEY_FALSE(key);

108

109
The key must be global, that is, it can't be allocated on the stack or dynamically
110 111
allocated at run-time.

112
The key is then used in code as::
113

114
        if (static_branch_unlikely(&key))
115 116 117 118
                do unlikely code
        else
                do likely code

119
Or::
120

121
        if (static_branch_likely(&key))
122 123 124 125
                do likely code
        else
                do unlikely code

126 127
Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
be used in either static_branch_likely() or static_branch_unlikely()
Stan Drozd's avatar
Stan Drozd committed
128
statements.
129

130
Branch(es) can be set true via::
131

132
	static_branch_enable(&key);
133

134
or false via::
135

136
	static_branch_disable(&key);
137

138
The branch(es) can then be switched via reference counts::
139

140 141 142
	static_branch_inc(&key);
	...
	static_branch_dec(&key);
143

144 145 146 147 148 149 150
Thus, 'static_branch_inc()' means 'make the branch true', and
'static_branch_dec()' means 'make the branch false' with appropriate
reference counting. For example, if the key is initialized true, a
static_branch_dec(), will switch the branch to false. And a subsequent
static_branch_inc(), will change the branch back to true. Likewise, if the
key is initialized false, a 'static_branch_inc()', will change the branch to
true. And then a 'static_branch_dec()', will again make the branch false.
151

152 153 154 155 156
The state and the reference count can be retrieved with 'static_key_enabled()'
and 'static_key_count()'.  In general, if you use these functions, they
should be protected with the same mutex used around the enable/disable
or increment/decrement function.

157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
Note that switching branches results in some locks being taken,
particularly the CPU hotplug lock (in order to avoid races against
CPUs being brought in the kernel whilst the kernel is getting
patched). Calling the static key API from within a hotplug notifier is
thus a sure deadlock recipe. In order to still allow use of the
functionnality, the following functions are provided:

	static_key_enable_cpuslocked()
	static_key_disable_cpuslocked()
	static_branch_enable_cpuslocked()
	static_branch_disable_cpuslocked()

These functions are *not* general purpose, and must only be used when
you really know that you're in the above context, and no other.

172
Where an array of keys is required, it can be defined as::
173 174 175

	DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);

176
or::
177 178

	DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
179 180 181 182 183 184

4) Architecture level code patching interface, 'jump labels'


There are a few functions and macros that architectures must implement in order
to take advantage of this optimization. If there is no architecture support, we
185 186 187
simply fall back to a traditional, load, test, and jump sequence. Also, the
struct jump_entry table must be at least 4-byte aligned because the
static_key->entry field makes use of the two least significant bits.
188

189 190
* ``select HAVE_ARCH_JUMP_LABEL``,
    see: arch/x86/Kconfig
191

192 193
* ``#define JUMP_LABEL_NOP_SIZE``,
    see: arch/x86/include/asm/jump_label.h
194

195 196
* ``__always_inline bool arch_static_branch(struct static_key *key, bool branch)``,
    see: arch/x86/include/asm/jump_label.h
197

198 199
* ``__always_inline bool arch_static_branch_jump(struct static_key *key, bool branch)``,
    see: arch/x86/include/asm/jump_label.h
200

201 202
* ``void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type)``,
    see: arch/x86/kernel/jump_label.c
203

204 205
* ``__init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type)``,
    see: arch/x86/kernel/jump_label.c
206

207 208
* ``struct jump_entry``,
    see: arch/x86/include/asm/jump_label.h
209 210 211 212 213 214


5) Static keys / jump label analysis, results (x86_64):


As an example, let's add the following branch to 'getppid()', such that the
215
system call now looks like::
216

217 218
  SYSCALL_DEFINE0(getppid)
  {
219 220
        int pid;

221 222
  +     if (static_branch_unlikely(&key))
  +             printk("I am the true branch\n");
223 224 225 226 227 228

        rcu_read_lock();
        pid = task_tgid_vnr(rcu_dereference(current->real_parent));
        rcu_read_unlock();

        return pid;
229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273
  }

The resulting instructions with jump labels generated by GCC is::

  ffffffff81044290 <sys_getppid>:
  ffffffff81044290:       55                      push   %rbp
  ffffffff81044291:       48 89 e5                mov    %rsp,%rbp
  ffffffff81044294:       e9 00 00 00 00          jmpq   ffffffff81044299 <sys_getppid+0x9>
  ffffffff81044299:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
  ffffffff810442a0:       00 00
  ffffffff810442a2:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
  ffffffff810442a9:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
  ffffffff810442b0:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
  ffffffff810442b7:       e8 f4 d9 00 00          callq  ffffffff81051cb0 <pid_vnr>
  ffffffff810442bc:       5d                      pop    %rbp
  ffffffff810442bd:       48 98                   cltq
  ffffffff810442bf:       c3                      retq
  ffffffff810442c0:       48 c7 c7 e3 54 98 81    mov    $0xffffffff819854e3,%rdi
  ffffffff810442c7:       31 c0                   xor    %eax,%eax
  ffffffff810442c9:       e8 71 13 6d 00          callq  ffffffff8171563f <printk>
  ffffffff810442ce:       eb c9                   jmp    ffffffff81044299 <sys_getppid+0x9>

Without the jump label optimization it looks like::

  ffffffff810441f0 <sys_getppid>:
  ffffffff810441f0:       8b 05 8a 52 d8 00       mov    0xd8528a(%rip),%eax        # ffffffff81dc9480 <key>
  ffffffff810441f6:       55                      push   %rbp
  ffffffff810441f7:       48 89 e5                mov    %rsp,%rbp
  ffffffff810441fa:       85 c0                   test   %eax,%eax
  ffffffff810441fc:       75 27                   jne    ffffffff81044225 <sys_getppid+0x35>
  ffffffff810441fe:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
  ffffffff81044205:       00 00
  ffffffff81044207:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
  ffffffff8104420e:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
  ffffffff81044215:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
  ffffffff8104421c:       e8 2f da 00 00          callq  ffffffff81051c50 <pid_vnr>
  ffffffff81044221:       5d                      pop    %rbp
  ffffffff81044222:       48 98                   cltq
  ffffffff81044224:       c3                      retq
  ffffffff81044225:       48 c7 c7 13 53 98 81    mov    $0xffffffff81985313,%rdi
  ffffffff8104422c:       31 c0                   xor    %eax,%eax
  ffffffff8104422e:       e8 60 0f 6d 00          callq  ffffffff81715193 <printk>
  ffffffff81044233:       eb c9                   jmp    ffffffff810441fe <sys_getppid+0xe>
  ffffffff81044235:       66 66 2e 0f 1f 84 00    data32 nopw %cs:0x0(%rax,%rax,1)
  ffffffff8104423c:       00 00 00 00
274 275 276 277

Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
278
label case adds::
279

280
  6 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
281 282

If we then include the padding bytes, the jump label code saves, 16 total bytes
283
of instruction memory for this small function. In this case the non-jump label
284
function is 80 bytes long. Thus, we have saved 20% of the instruction
285 286 287 288 289 290 291 292 293
footprint. We can in fact improve this even further, since the 5-byte no-op
really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
However, we have not yet implemented optimal no-op sizes (they are currently
hard-coded).

Since there are a number of static key API uses in the scheduler paths,
'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
performance improvement. Testing done on 3.3.0-rc2:

294
jump label disabled::
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310

 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):

        855.700314 task-clock                #    0.534 CPUs utilized            ( +-  0.11% )
           200,003 context-switches          #    0.234 M/sec                    ( +-  0.00% )
                 0 CPU-migrations            #    0.000 M/sec                    ( +- 39.58% )
               487 page-faults               #    0.001 M/sec                    ( +-  0.02% )
     1,474,374,262 cycles                    #    1.723 GHz                      ( +-  0.17% )
   <not supported> stalled-cycles-frontend
   <not supported> stalled-cycles-backend
     1,178,049,567 instructions              #    0.80  insns per cycle          ( +-  0.06% )
       208,368,926 branches                  #  243.507 M/sec                    ( +-  0.06% )
         5,569,188 branch-misses             #    2.67% of all branches          ( +-  0.54% )

       1.601607384 seconds time elapsed                                          ( +-  0.07% )

311
jump label enabled::
312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331

 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):

        841.043185 task-clock                #    0.533 CPUs utilized            ( +-  0.12% )
           200,004 context-switches          #    0.238 M/sec                    ( +-  0.00% )
                 0 CPU-migrations            #    0.000 M/sec                    ( +- 40.87% )
               487 page-faults               #    0.001 M/sec                    ( +-  0.05% )
     1,432,559,428 cycles                    #    1.703 GHz                      ( +-  0.18% )
   <not supported> stalled-cycles-frontend
   <not supported> stalled-cycles-backend
     1,175,363,994 instructions              #    0.82  insns per cycle          ( +-  0.04% )
       206,859,359 branches                  #  245.956 M/sec                    ( +-  0.04% )
         4,884,119 branch-misses             #    2.36% of all branches          ( +-  0.85% )

       1.579384366 seconds time elapsed

The percentage of saved branches is .7%, and we've saved 12% on
'branch-misses'. This is where we would expect to get the most savings, since
this optimization is about reducing the number of branches. In addition, we've
saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.