Abstract¶

Static keys allows the inclusion of seldom used features inperformance-sensitive fast-path kernel code, via a GCC feature and a codepatching technique. A quick example:

DEFINE_STATIC_KEY_FALSE(key);...if (static_branch_unlikely(&key))        do unlikely codeelse        do likely code...static_branch_enable(&key);...static_branch_disable(&key);...

Thestatic_branch_unlikely() branch will be generated into the code with as littleimpact to the likely code path as possible.

Motivation¶

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

Solution¶

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

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

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

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

if (static_branch_unlikely(&key))        printk("I am the true branch\n");

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

This lowlevel patching mechanism is called ‘jump label patching’, and it givesthe basis for the static keys facility.

Static key label API, usage and examples¶

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

DEFINE_STATIC_KEY_TRUE(key);

or:

DEFINE_STATIC_KEY_FALSE(key);

The key must be global, that is, it can’t be allocated on the stack or dynamicallyallocated at run-time.

The key is then used in code as:

if (static_branch_unlikely(&key))        do unlikely codeelse        do likely code

Or:

if (static_branch_likely(&key))        do likely codeelse        do unlikely code

Keys defined viaDEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, maybe used in eitherstatic_branch_likely() orstatic_branch_unlikely()statements.

Branch(es) can be set true via:

static_branch_enable(&key);

or false via:

static_branch_disable(&key);

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

static_branch_inc(&key);...static_branch_dec(&key);

Thus, ‘static_branch_inc()’ means ‘make the branch true’, and‘static_branch_dec()’ means ‘make the branch false’ with appropriatereference counting. For example, if the key is initialized true, astatic_branch_dec(), will switch the branch to false. And a subsequentstatic_branch_inc(), will change the branch back to true. Likewise, if thekey is initialized false, a ‘static_branch_inc()’, will change the branch totrue. And then a ‘static_branch_dec()’, will again make the branch false.

The state and the reference count can be retrieved with ‘static_key_enabled()’and ‘static_key_count()’. In general, if you use these functions, theyshould be protected with the same mutex used around the enable/disableor increment/decrement function.

Note that switching branches results in some locks being taken,particularly the CPU hotplug lock (in order to avoid races againstCPUs being brought in the kernel while the kernel is gettingpatched). Calling the static key API from within a hotplug notifier isthus a sure deadlock recipe. In order to still allow use of thefunctionality, the following functions are provided:

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

These functions arenot general purpose, and must only be used whenyou really know that you’re in the above context, and no other.

Where an array of keys is required, it can be defined as:

DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);

or:

DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);

4. Architecture level code patching interface, ‘jump labels’

There are a few functions and macros that architectures must implement in orderto take advantage of this optimization. If there is no architecture support, wesimply fall back to a traditional, load, test, and jump sequence. Also, thestructjump_entry table must be at least 4-byte aligned because thestatic_key->entry field makes use of the two least significant bits.

• selectHAVE_ARCH_JUMP_LABEL,

  see: arch/x86/Kconfig

• #defineJUMP_LABEL_NOP_SIZE,

  see: arch/x86/include/asm/jump_label.h

• __always_inlineboolarch_static_branch(structstatic_key*key,boolbranch),

  see: arch/x86/include/asm/jump_label.h

• __always_inlineboolarch_static_branch_jump(structstatic_key*key,boolbranch),

  see: arch/x86/include/asm/jump_label.h

• voidarch_jump_label_transform(structjump_entry*entry,enumjump_label_typetype),

  see: arch/x86/kernel/jump_label.c

• structjump_entry,

  see: arch/x86/include/asm/jump_label.h

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

As an example, let’s add the following branch to ‘getppid()’, such that thesystem call now looks like:

SYSCALL_DEFINE0(getppid){      int pid;+     if (static_branch_unlikely(&key))+             printk("I am the true branch\n");      rcu_read_lock();      pid = task_tgid_vnr(rcu_dereference(current->real_parent));      rcu_read_unlock();      return pid;}

The resulting instructions with jump labels generated by GCC is:

ffffffff81044290 <sys_getppid>:ffffffff81044290:       55                      push   %rbpffffffff81044291:       48 89 e5                mov    %rsp,%rbpffffffff81044294:       e9 00 00 00 00          jmpq   ffffffff81044299 <sys_getppid+0x9>ffffffff81044299:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%raxffffffff810442a0:       00 00ffffffff810442a2:       48 8b 80 80 02 00 00    mov    0x280(%rax),%raxffffffff810442a9:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%raxffffffff810442b0:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdiffffffff810442b7:       e8 f4 d9 00 00          callq  ffffffff81051cb0 <pid_vnr>ffffffff810442bc:       5d                      pop    %rbpffffffff810442bd:       48 98                   cltqffffffff810442bf:       c3                      retqffffffff810442c0:       48 c7 c7 e3 54 98 81    mov    $0xffffffff819854e3,%rdiffffffff810442c7:       31 c0                   xor    %eax,%eaxffffffff810442c9:       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   %rbpffffffff810441f7:       48 89 e5                mov    %rsp,%rbpffffffff810441fa:       85 c0                   test   %eax,%eaxffffffff810441fc:       75 27                   jne    ffffffff81044225 <sys_getppid+0x35>ffffffff810441fe:       65 48 8b 04 25 c0 b6    mov    %gs:0xb6c0,%raxffffffff81044205:       00 00ffffffff81044207:       48 8b 80 80 02 00 00    mov    0x280(%rax),%raxffffffff8104420e:       48 8b 80 b0 02 00 00    mov    0x2b0(%rax),%raxffffffff81044215:       48 8b b8 e8 02 00 00    mov    0x2e8(%rax),%rdiffffffff8104421c:       e8 2f da 00 00          callq  ffffffff81051c50 <pid_vnr>ffffffff81044221:       5d                      pop    %rbpffffffff81044222:       48 98                   cltqffffffff81044224:       c3                      retqffffffff81044225:       48 c7 c7 13 53 98 81    mov    $0xffffffff81985313,%rdiffffffff8104422c:       31 c0                   xor    %eax,%eaxffffffff8104422e:       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

Thus, the disable jump label case adds a ‘mov’, ‘test’ and ‘jne’ instructionvs. the jump label case just has a ‘no-op’ or ‘jmp 0’. (The jmp 0, is patchedto a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jumplabel case adds:

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

If we then include the padding bytes, the jump label code saves, 16 total bytesof instruction memory for this small function. In this case the non-jump labelfunction is 80 bytes long. Thus, we have saved 20% of the instructionfootprint. We can in fact improve this even further, since the 5-byte no-opreally 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 currentlyhard-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 theperformance improvement. Testing done on 3.3.0-rc2:

jump label disabled:

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% )

jump label enabled:

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, sincethis optimization is about reducing the number of branches. In addition, we’vesaved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.