Back to home page

LXR

 
 

    


0001                         Static Keys
0002                         -----------
0003 
0004 DEPRECATED API:
0005 
0006 The use of 'struct static_key' directly, is now DEPRECATED. In addition
0007 static_key_{true,false}() is also DEPRECATED. IE DO NOT use the following:
0008 
0009 struct static_key false = STATIC_KEY_INIT_FALSE;
0010 struct static_key true = STATIC_KEY_INIT_TRUE;
0011 static_key_true()
0012 static_key_false()
0013 
0014 The updated API replacements are:
0015 
0016 DEFINE_STATIC_KEY_TRUE(key);
0017 DEFINE_STATIC_KEY_FALSE(key);
0018 DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
0019 DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
0020 static_branch_likely()
0021 static_branch_unlikely()
0022 
0023 0) Abstract
0024 
0025 Static keys allows the inclusion of seldom used features in
0026 performance-sensitive fast-path kernel code, via a GCC feature and a code
0027 patching technique. A quick example:
0028 
0029         DEFINE_STATIC_KEY_FALSE(key);
0030 
0031         ...
0032 
0033         if (static_branch_unlikely(&key))
0034                 do unlikely code
0035         else
0036                 do likely code
0037 
0038         ...
0039         static_branch_enable(&key);
0040         ...
0041         static_branch_disable(&key);
0042         ...
0043 
0044 The static_branch_unlikely() branch will be generated into the code with as little
0045 impact to the likely code path as possible.
0046 
0047 
0048 1) Motivation
0049 
0050 
0051 Currently, tracepoints are implemented using a conditional branch. The
0052 conditional check requires checking a global variable for each tracepoint.
0053 Although the overhead of this check is small, it increases when the memory
0054 cache comes under pressure (memory cache lines for these global variables may
0055 be shared with other memory accesses). As we increase the number of tracepoints
0056 in the kernel this overhead may become more of an issue. In addition,
0057 tracepoints are often dormant (disabled) and provide no direct kernel
0058 functionality. Thus, it is highly desirable to reduce their impact as much as
0059 possible. Although tracepoints are the original motivation for this work, other
0060 kernel code paths should be able to make use of the static keys facility.
0061 
0062 
0063 2) Solution
0064 
0065 
0066 gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:
0067 
0068 http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html
0069 
0070 Using the 'asm goto', we can create branches that are either taken or not taken
0071 by default, without the need to check memory. Then, at run-time, we can patch
0072 the branch site to change the branch direction.
0073 
0074 For example, if we have a simple branch that is disabled by default:
0075 
0076         if (static_branch_unlikely(&key))
0077                 printk("I am the true branch\n");
0078 
0079 Thus, by default the 'printk' will not be emitted. And the code generated will
0080 consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
0081 straight-line code path. When the branch is 'flipped', we will patch the
0082 'no-op' in the straight-line codepath with a 'jump' instruction to the
0083 out-of-line true branch. Thus, changing branch direction is expensive but
0084 branch selection is basically 'free'. That is the basic tradeoff of this
0085 optimization.
0086 
0087 This lowlevel patching mechanism is called 'jump label patching', and it gives
0088 the basis for the static keys facility.
0089 
0090 3) Static key label API, usage and examples:
0091 
0092 
0093 In order to make use of this optimization you must first define a key:
0094 
0095         DEFINE_STATIC_KEY_TRUE(key);
0096 
0097 or:
0098 
0099         DEFINE_STATIC_KEY_FALSE(key);
0100 
0101 
0102 The key must be global, that is, it can't be allocated on the stack or dynamically
0103 allocated at run-time.
0104 
0105 The key is then used in code as:
0106 
0107         if (static_branch_unlikely(&key))
0108                 do unlikely code
0109         else
0110                 do likely code
0111 
0112 Or:
0113 
0114         if (static_branch_likely(&key))
0115                 do likely code
0116         else
0117                 do unlikely code
0118 
0119 Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
0120 be used in either static_branch_likely() or static_branch_unlikely()
0121 statemnts.
0122 
0123 Branch(es) can be set true via:
0124 
0125 static_branch_enable(&key);
0126 
0127 or false via:
0128 
0129 static_branch_disable(&key);
0130 
0131 The branch(es) can then be switched via reference counts:
0132 
0133         static_branch_inc(&key);
0134         ...
0135         static_branch_dec(&key);
0136 
0137 Thus, 'static_branch_inc()' means 'make the branch true', and
0138 'static_branch_dec()' means 'make the branch false' with appropriate
0139 reference counting. For example, if the key is initialized true, a
0140 static_branch_dec(), will switch the branch to false. And a subsequent
0141 static_branch_inc(), will change the branch back to true. Likewise, if the
0142 key is initialized false, a 'static_branch_inc()', will change the branch to
0143 true. And then a 'static_branch_dec()', will again make the branch false.
0144 
0145 Where an array of keys is required, it can be defined as:
0146 
0147         DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
0148 
0149 or:
0150 
0151         DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
0152 
0153 4) Architecture level code patching interface, 'jump labels'
0154 
0155 
0156 There are a few functions and macros that architectures must implement in order
0157 to take advantage of this optimization. If there is no architecture support, we
0158 simply fall back to a traditional, load, test, and jump sequence.
0159 
0160 * select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig
0161 
0162 * #define JUMP_LABEL_NOP_SIZE, see: arch/x86/include/asm/jump_label.h
0163 
0164 * __always_inline bool arch_static_branch(struct static_key *key, bool branch), see:
0165                                         arch/x86/include/asm/jump_label.h
0166 
0167 * __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch),
0168                                         see: arch/x86/include/asm/jump_label.h
0169 
0170 * void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type),
0171                                         see: arch/x86/kernel/jump_label.c
0172 
0173 * __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type),
0174                                         see: arch/x86/kernel/jump_label.c
0175 
0176 
0177 * struct jump_entry, see: arch/x86/include/asm/jump_label.h
0178 
0179 
0180 5) Static keys / jump label analysis, results (x86_64):
0181 
0182 
0183 As an example, let's add the following branch to 'getppid()', such that the
0184 system call now looks like:
0185 
0186 SYSCALL_DEFINE0(getppid)
0187 {
0188         int pid;
0189 
0190 +       if (static_branch_unlikely(&key))
0191 +               printk("I am the true branch\n");
0192 
0193         rcu_read_lock();
0194         pid = task_tgid_vnr(rcu_dereference(current->real_parent));
0195         rcu_read_unlock();
0196 
0197         return pid;
0198 }
0199 
0200 The resulting instructions with jump labels generated by GCC is:
0201 
0202 ffffffff81044290 <sys_getppid>:
0203 ffffffff81044290:       55                      push   %rbp
0204 ffffffff81044291:       48 89 e5                mov    %rsp,%rbp
0205 ffffffff81044294:       e9 00 00 00 00          jmpq   ffffffff81044299 <sys_getppid+0x9>
0206 ffffffff81044299:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
0207 ffffffff810442a0:       00 00
0208 ffffffff810442a2:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
0209 ffffffff810442a9:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
0210 ffffffff810442b0:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
0211 ffffffff810442b7:       e8 f4 d9 00 00          callq  ffffffff81051cb0 <pid_vnr>
0212 ffffffff810442bc:       5d                      pop    %rbp
0213 ffffffff810442bd:       48 98                   cltq
0214 ffffffff810442bf:       c3                      retq
0215 ffffffff810442c0:       48 c7 c7 e3 54 98 81    mov    $0xffffffff819854e3,%rdi
0216 ffffffff810442c7:       31 c0                   xor    %eax,%eax
0217 ffffffff810442c9:       e8 71 13 6d 00          callq  ffffffff8171563f <printk>
0218 ffffffff810442ce:       eb c9                   jmp    ffffffff81044299 <sys_getppid+0x9>
0219 
0220 Without the jump label optimization it looks like:
0221 
0222 ffffffff810441f0 <sys_getppid>:
0223 ffffffff810441f0:       8b 05 8a 52 d8 00       mov    0xd8528a(%rip),%eax        # ffffffff81dc9480 <key>
0224 ffffffff810441f6:       55                      push   %rbp
0225 ffffffff810441f7:       48 89 e5                mov    %rsp,%rbp
0226 ffffffff810441fa:       85 c0                   test   %eax,%eax
0227 ffffffff810441fc:       75 27                   jne    ffffffff81044225 <sys_getppid+0x35>
0228 ffffffff810441fe:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%rax
0229 ffffffff81044205:       00 00
0230 ffffffff81044207:       48 8b 80 80 02 00 00    mov    0x280(%rax),%rax
0231 ffffffff8104420e:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%rax
0232 ffffffff81044215:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdi
0233 ffffffff8104421c:       e8 2f da 00 00          callq  ffffffff81051c50 <pid_vnr>
0234 ffffffff81044221:       5d                      pop    %rbp
0235 ffffffff81044222:       48 98                   cltq
0236 ffffffff81044224:       c3                      retq
0237 ffffffff81044225:       48 c7 c7 13 53 98 81    mov    $0xffffffff81985313,%rdi
0238 ffffffff8104422c:       31 c0                   xor    %eax,%eax
0239 ffffffff8104422e:       e8 60 0f 6d 00          callq  ffffffff81715193 <printk>
0240 ffffffff81044233:       eb c9                   jmp    ffffffff810441fe <sys_getppid+0xe>
0241 ffffffff81044235:       66 66 2e 0f 1f 84 00    data32 nopw %cs:0x0(%rax,%rax,1)
0242 ffffffff8104423c:       00 00 00 00
0243 
0244 Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
0245 vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
0246 to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
0247 label case adds:
0248 
0249 6 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
0250 
0251 If we then include the padding bytes, the jump label code saves, 16 total bytes
0252 of instruction memory for this small function. In this case the non-jump label
0253 function is 80 bytes long. Thus, we have saved 20% of the instruction
0254 footprint. We can in fact improve this even further, since the 5-byte no-op
0255 really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
0256 However, we have not yet implemented optimal no-op sizes (they are currently
0257 hard-coded).
0258 
0259 Since there are a number of static key API uses in the scheduler paths,
0260 'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
0261 performance improvement. Testing done on 3.3.0-rc2:
0262 
0263 jump label disabled:
0264 
0265  Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
0266 
0267         855.700314 task-clock                #    0.534 CPUs utilized            ( +-  0.11% )
0268            200,003 context-switches          #    0.234 M/sec                    ( +-  0.00% )
0269                  0 CPU-migrations            #    0.000 M/sec                    ( +- 39.58% )
0270                487 page-faults               #    0.001 M/sec                    ( +-  0.02% )
0271      1,474,374,262 cycles                    #    1.723 GHz                      ( +-  0.17% )
0272    <not supported> stalled-cycles-frontend
0273    <not supported> stalled-cycles-backend
0274      1,178,049,567 instructions              #    0.80  insns per cycle          ( +-  0.06% )
0275        208,368,926 branches                  #  243.507 M/sec                    ( +-  0.06% )
0276          5,569,188 branch-misses             #    2.67% of all branches          ( +-  0.54% )
0277 
0278        1.601607384 seconds time elapsed                                          ( +-  0.07% )
0279 
0280 jump label enabled:
0281 
0282  Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
0283 
0284         841.043185 task-clock                #    0.533 CPUs utilized            ( +-  0.12% )
0285            200,004 context-switches          #    0.238 M/sec                    ( +-  0.00% )
0286                  0 CPU-migrations            #    0.000 M/sec                    ( +- 40.87% )
0287                487 page-faults               #    0.001 M/sec                    ( +-  0.05% )
0288      1,432,559,428 cycles                    #    1.703 GHz                      ( +-  0.18% )
0289    <not supported> stalled-cycles-frontend
0290    <not supported> stalled-cycles-backend
0291      1,175,363,994 instructions              #    0.82  insns per cycle          ( +-  0.04% )
0292        206,859,359 branches                  #  245.956 M/sec                    ( +-  0.04% )
0293          4,884,119 branch-misses             #    2.36% of all branches          ( +-  0.85% )
0294 
0295        1.579384366 seconds time elapsed
0296 
0297 The percentage of saved branches is .7%, and we've saved 12% on
0298 'branch-misses'. This is where we would expect to get the most savings, since
0299 this optimization is about reducing the number of branches. In addition, we've
0300 saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.