linux/Documentation/static-keys.txt
<<
>>
Prefs
   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);
  18DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
  19DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
  20static_branch_likely()
  21static_branch_unlikely()
  22
  230) Abstract
  24
  25Static keys allows the inclusion of seldom used features in
  26performance-sensitive fast-path kernel code, via a GCC feature and a code
  27patching 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
  44The static_branch_unlikely() branch will be generated into the code with as little
  45impact to the likely code path as possible.
  46
  47
  481) Motivation
  49
  50
  51Currently, tracepoints are implemented using a conditional branch. The
  52conditional check requires checking a global variable for each tracepoint.
  53Although the overhead of this check is small, it increases when the memory
  54cache comes under pressure (memory cache lines for these global variables may
  55be shared with other memory accesses). As we increase the number of tracepoints
  56in the kernel this overhead may become more of an issue. In addition,
  57tracepoints are often dormant (disabled) and provide no direct kernel
  58functionality. Thus, it is highly desirable to reduce their impact as much as
  59possible. Although tracepoints are the original motivation for this work, other
  60kernel code paths should be able to make use of the static keys facility.
  61
  62
  632) Solution
  64
  65
  66gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:
  67
  68http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html
  69
  70Using the 'asm goto', we can create branches that are either taken or not taken
  71by default, without the need to check memory. Then, at run-time, we can patch
  72the branch site to change the branch direction.
  73
  74For 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
  79Thus, by default the 'printk' will not be emitted. And the code generated will
  80consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
  81straight-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
  83out-of-line true branch. Thus, changing branch direction is expensive but
  84branch selection is basically 'free'. That is the basic tradeoff of this
  85optimization.
  86
  87This lowlevel patching mechanism is called 'jump label patching', and it gives
  88the basis for the static keys facility.
  89
  903) Static key label API, usage and examples:
  91
  92
  93In order to make use of this optimization you must first define a key:
  94
  95        DEFINE_STATIC_KEY_TRUE(key);
  96
  97or:
  98
  99        DEFINE_STATIC_KEY_FALSE(key);
 100
 101
 102The key must be global, that is, it can't be allocated on the stack or dynamically
 103allocated at run-time.
 104
 105The 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
 112Or:
 113
 114        if (static_branch_likely(&key))
 115                do likely code
 116        else
 117                do unlikely code
 118
 119Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
 120be used in either static_branch_likely() or static_branch_unlikely()
 121statemnts.
 122
 123Branch(es) can be set true via:
 124
 125static_branch_enable(&key);
 126
 127or false via:
 128
 129static_branch_disable(&key);
 130
 131The branch(es) can then be switched via reference counts:
 132
 133        static_branch_inc(&key);
 134        ...
 135        static_branch_dec(&key);
 136
 137Thus, 'static_branch_inc()' means 'make the branch true', and
 138'static_branch_dec()' means 'make the branch false' with appropriate
 139reference counting. For example, if the key is initialized true, a
 140static_branch_dec(), will switch the branch to false. And a subsequent
 141static_branch_inc(), will change the branch back to true. Likewise, if the
 142key is initialized false, a 'static_branch_inc()', will change the branch to
 143true. And then a 'static_branch_dec()', will again make the branch false.
 144
 145Where an array of keys is required, it can be defined as:
 146
 147        DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
 148
 149or:
 150
 151        DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
 152
 1534) Architecture level code patching interface, 'jump labels'
 154
 155
 156There are a few functions and macros that architectures must implement in order
 157to take advantage of this optimization. If there is no architecture support, we
 158simply 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
 1805) Static keys / jump label analysis, results (x86_64):
 181
 182
 183As an example, let's add the following branch to 'getppid()', such that the
 184system call now looks like:
 185
 186SYSCALL_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
 200The resulting instructions with jump labels generated by GCC is:
 201
 202ffffffff81044290 <sys_getppid>:
 203ffffffff81044290:       55                      push   %rbp
 204ffffffff81044291:       48 89 e5                mov    %rsp,%rbp
 205ffffffff81044294:       e9 00 00 00 00          jmpq   ffffffff81044299 <sys_getppid+0x9>
 206ffffffff81044299:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
 207ffffffff810442a0:       00 00
 208ffffffff810442a2:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
 209ffffffff810442a9:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
 210ffffffff810442b0:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
 211ffffffff810442b7:       e8 f4 d9 00 00          callq  ffffffff81051cb0 <pid_vnr>
 212ffffffff810442bc:       5d                      pop    %rbp
 213ffffffff810442bd:       48 98                   cltq
 214ffffffff810442bf:       c3                      retq
 215ffffffff810442c0:       48 c7 c7 e3 54 98 81    mov    $0xffffffff819854e3,%rdi
 216ffffffff810442c7:       31 c0                   xor    %eax,%eax
 217ffffffff810442c9:       e8 71 13 6d 00          callq  ffffffff8171563f <printk>
 218ffffffff810442ce:       eb c9                   jmp    ffffffff81044299 <sys_getppid+0x9>
 219
 220Without the jump label optimization it looks like:
 221
 222ffffffff810441f0 <sys_getppid>:
 223ffffffff810441f0:       8b 05 8a 52 d8 00       mov    0xd8528a(%rip),%eax        # ffffffff81dc9480 <key>
 224ffffffff810441f6:       55                      push   %rbp
 225ffffffff810441f7:       48 89 e5                mov    %rsp,%rbp
 226ffffffff810441fa:       85 c0                   test   %eax,%eax
 227ffffffff810441fc:       75 27                   jne    ffffffff81044225 <sys_getppid+0x35>
 228ffffffff810441fe:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
 229ffffffff81044205:       00 00
 230ffffffff81044207:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
 231ffffffff8104420e:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
 232ffffffff81044215:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
 233ffffffff8104421c:       e8 2f da 00 00          callq  ffffffff81051c50 <pid_vnr>
 234ffffffff81044221:       5d                      pop    %rbp
 235ffffffff81044222:       48 98                   cltq
 236ffffffff81044224:       c3                      retq
 237ffffffff81044225:       48 c7 c7 13 53 98 81    mov    $0xffffffff81985313,%rdi
 238ffffffff8104422c:       31 c0                   xor    %eax,%eax
 239ffffffff8104422e:       e8 60 0f 6d 00          callq  ffffffff81715193 <printk>
 240ffffffff81044233:       eb c9                   jmp    ffffffff810441fe <sys_getppid+0xe>
 241ffffffff81044235:       66 66 2e 0f 1f 84 00    data32 nopw %cs:0x0(%rax,%rax,1)
 242ffffffff8104423c:       00 00 00 00
 243
 244Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
 245vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
 246to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
 247label case adds:
 248
 2496 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
 250
 251If we then include the padding bytes, the jump label code saves, 16 total bytes
 252of instruction memory for this small function. In this case the non-jump label
 253function is 80 bytes long. Thus, we have saved 20% of the instruction
 254footprint. We can in fact improve this even further, since the 5-byte no-op
 255really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
 256However, we have not yet implemented optimal no-op sizes (they are currently
 257hard-coded).
 258
 259Since 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
 261performance improvement. Testing done on 3.3.0-rc2:
 262
 263jump 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
 280jump 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
 297The 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
 299this optimization is about reducing the number of branches. In addition, we've
 300saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.
 301