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. Also, the
 159 struct jump_entry table must be at least 4-byte aligned because the
 160 static_key->entry field makes use of the two least significant bits.
 161
 162 * select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig
 163
 164 * #define JUMP_LABEL_NOP_SIZE, see: arch/x86/include/asm/jump_label.h
 165
 166 * __always_inline bool arch_static_branch(struct static_key *key, bool branch), see:
 167                                         arch/x86/include/asm/jump_label.h
 168
 169 * __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch),
 170                                         see: arch/x86/include/asm/jump_label.h
 171
 172 * void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type),
 173                                         see: arch/x86/kernel/jump_label.c
 174
 175 * __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type),
 176                                         see: arch/x86/kernel/jump_label.c
 177
 178
 179 * struct jump_entry, see: arch/x86/include/asm/jump_label.h
 180
 181
 182 5) Static keys / jump label analysis, results (x86_64):
 183
 184
 185 As an example, let's add the following branch to 'getppid()', such that the
 186 system call now looks like:
 187
 188 SYSCALL_DEFINE0(getppid)
 189 {
 190         int pid;
 191
 192 +       if (static_branch_unlikely(&key))
 193 +               printk("I am the true branch\n");
 194
 195         rcu_read_lock();
 196         pid = task_tgid_vnr(rcu_dereference(current->real_parent));
 197         rcu_read_unlock();
 198
 199         return pid;
 200 }
 201
 202 The resulting instructions with jump labels generated by GCC is:
 203
 204 ffffffff81044290 <sys_getppid>:
 205 ffffffff81044290:       55                      push   %rbp
 206 ffffffff81044291:       48 89 e5                mov    %rsp,%rbp
 207 ffffffff81044294:       e9 00 00 00 00          jmpq   ffffffff81044299 <sys_getppid+0x9>
 208 ffffffff81044299:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
 209 ffffffff810442a0:       00 00
 210 ffffffff810442a2:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
 211 ffffffff810442a9:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
 212 ffffffff810442b0:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
 213 ffffffff810442b7:       e8 f4 d9 00 00          callq  ffffffff81051cb0 <pid_vnr>
 214 ffffffff810442bc:       5d                      pop    %rbp
 215 ffffffff810442bd:       48 98                   cltq
 216 ffffffff810442bf:       c3                      retq
 217 ffffffff810442c0:       48 c7 c7 e3 54 98 81    mov    $0xffffffff819854e3,%rdi
 218 ffffffff810442c7:       31 c0                   xor    %eax,%eax
 219 ffffffff810442c9:       e8 71 13 6d 00          callq  ffffffff8171563f <printk>
 220 ffffffff810442ce:       eb c9                   jmp    ffffffff81044299 <sys_getppid+0x9>
 221
 222 Without the jump label optimization it looks like:
 223
 224 ffffffff810441f0 <sys_getppid>:
 225 ffffffff810441f0:       8b 05 8a 52 d8 00       mov    0xd8528a(%rip),%eax        # ffffffff81dc9480 <key>
 226 ffffffff810441f6:       55                      push   %rbp
 227 ffffffff810441f7:       48 89 e5                mov    %rsp,%rbp
 228 ffffffff810441fa:       85 c0                   test   %eax,%eax
 229 ffffffff810441fc:       75 27                   jne    ffffffff81044225 <sys_getppid+0x35>
 230 ffffffff810441fe:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
 231 ffffffff81044205:       00 00
 232 ffffffff81044207:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
 233 ffffffff8104420e:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
 234 ffffffff81044215:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
 235 ffffffff8104421c:       e8 2f da 00 00          callq  ffffffff81051c50 <pid_vnr>
 236 ffffffff81044221:       5d                      pop    %rbp
 237 ffffffff81044222:       48 98                   cltq
 238 ffffffff81044224:       c3                      retq
 239 ffffffff81044225:       48 c7 c7 13 53 98 81    mov    $0xffffffff81985313,%rdi
 240 ffffffff8104422c:       31 c0                   xor    %eax,%eax
 241 ffffffff8104422e:       e8 60 0f 6d 00          callq  ffffffff81715193 <printk>
 242 ffffffff81044233:       eb c9                   jmp    ffffffff810441fe <sys_getppid+0xe>
 243 ffffffff81044235:       66 66 2e 0f 1f 84 00    data32 nopw %cs:0x0(%rax,%rax,1)
 244 ffffffff8104423c:       00 00 00 00
 245
 246 Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
 247 vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
 248 to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
 249 label case adds:
 250
 251 6 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
 252
 253 If we then include the padding bytes, the jump label code saves, 16 total bytes
 254 of instruction memory for this small function. In this case the non-jump label
 255 function is 80 bytes long. Thus, we have saved 20% of the instruction
 256 footprint. We can in fact improve this even further, since the 5-byte no-op
 257 really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
 258 However, we have not yet implemented optimal no-op sizes (they are currently
 259 hard-coded).
 260
 261 Since there are a number of static key API uses in the scheduler paths,
 262 'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
 263 performance improvement. Testing done on 3.3.0-rc2:
 264
 265 jump label disabled:
 266
 267  Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
 268
 269         855.700314 task-clock                #    0.534 CPUs utilized            ( +-  0.11% )
 270            200,003 context-switches          #    0.234 M/sec                    ( +-  0.00% )
 271                  0 CPU-migrations            #    0.000 M/sec                    ( +- 39.58% )
 272                487 page-faults               #    0.001 M/sec                    ( +-  0.02% )
 273      1,474,374,262 cycles                    #    1.723 GHz                      ( +-  0.17% )
 274    <not supported> stalled-cycles-frontend
 275    <not supported> stalled-cycles-backend
 276      1,178,049,567 instructions              #    0.80  insns per cycle          ( +-  0.06% )
 277        208,368,926 branches                  #  243.507 M/sec                    ( +-  0.06% )
 278          5,569,188 branch-misses             #    2.67% of all branches          ( +-  0.54% )
 279
 280        1.601607384 seconds time elapsed                                          ( +-  0.07% )
 281
 282 jump label enabled:
 283
 284  Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
 285
 286         841.043185 task-clock                #    0.533 CPUs utilized            ( +-  0.12% )
 287            200,004 context-switches          #    0.238 M/sec                    ( +-  0.00% )
 288                  0 CPU-migrations            #    0.000 M/sec                    ( +- 40.87% )
 289                487 page-faults               #    0.001 M/sec                    ( +-  0.05% )
 290      1,432,559,428 cycles                    #    1.703 GHz                      ( +-  0.18% )
 291    <not supported> stalled-cycles-frontend
 292    <not supported> stalled-cycles-backend
 293      1,175,363,994 instructions              #    0.82  insns per cycle          ( +-  0.04% )
 294        206,859,359 branches                  #  245.956 M/sec                    ( +-  0.04% )
 295          4,884,119 branch-misses             #    2.36% of all branches          ( +-  0.85% )
 296
 297        1.579384366 seconds time elapsed
 298
 299 The percentage of saved branches is .7%, and we've saved 12% on
 300 'branch-misses'. This is where we would expect to get the most savings, since
 301 this optimization is about reducing the number of branches. In addition, we've
 302 saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.