Static key와 jump label

폐기된 API와 대체 API

`struct static_key`를 직접 사용하는 방식과 `static_key_true()`·`static_key_false()`는 폐기되었다. `STATIC_KEY_INIT_FALSE`나 `STATIC_KEY_INIT_TRUE`로 구조체 변수를 직접 초기화하는 code도 사용하면 안 된다.

대신 `DEFINE_STATIC_KEY_TRUE()`와 `DEFINE_STATIC_KEY_FALSE()`로 key를 선언하고, 배열에는 `DEFINE_STATIC_KEY_ARRAY_TRUE()` 또는 `DEFINE_STATIC_KEY_ARRAY_FALSE()`를 사용한다. branch site에서는 `static_branch_likely()`와 `static_branch_unlikely()`를 사용한다.

===========
Static Keys
===========

.. warning::

   DEPRECATED API:

   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::

	struct static_key false = STATIC_KEY_INIT_FALSE;
	struct static_key true = STATIC_KEY_INIT_TRUE;
	static_key_true()
	static_key_false()

   The updated API replacements are::

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

fast path에 드문 기능 넣기

static key는 GCC 기능과 runtime code patching을 결합해 성능에 민감한 kernel fast path에 거의 사용되지 않는 기능을 낮은 비용으로 포함하게 한다.

예제는 `DEFINE_STATIC_KEY_FALSE(key)`로 기본 false key를 만들고 `static_branch_unlikely(&key)`로 드문 경로를 고른다. `static_branch_enable(&key)`이 true branch를 활성화하고 `static_branch_disable(&key)`이 다시 비활성화한다.

`static_branch_unlikely()` site는 흔한 likely code path에 주는 영향을 가능한 한 작게 만들도록 생성된다.

Abstract
========

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

	DEFINE_STATIC_KEY_FALSE(key);

	...

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

	...
	static_branch_enable(&key);
	...
	static_branch_disable(&key);
	...

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

tracepoint 조건 검사 비용

기존 tracepoint는 conditional branch로 구현되어 각 tracepoint마다 global variable을 확인해야 한다. 이 검사 자체의 overhead는 작지만 global variable이 들어 있는 cache line이 다른 memory access와 공유되고 cache pressure가 커지면 비용이 증가한다.

kernel의 tracepoint 수가 늘수록 이 비용은 더 문제가 될 수 있다. tracepoint는 대부분 disabled 상태이고 직접적인 kernel 기능을 제공하지 않는 경우가 많으므로 dormant 상태의 영향을 최대한 줄이는 것이 중요하다.

tracepoint가 이 작업의 최초 동기였지만 static key facility는 다른 kernel code path에서도 사용할 수 있다.

Motivation
==========


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.

asm goto와 jump label patching

GCC 4.5는 assembly에서 C label로 분기할 수 있는 `asm goto` statement를 추가했다. 이를 사용하면 memory를 읽지 않고도 기본적으로 taken 또는 not-taken인 branch를 만들고, runtime에 branch site를 patch해 방향을 바꿀 수 있다.

기본 disabled인 `static_branch_unlikely()` 예에서는 true branch의 `printk()`가 실행되지 않는다. x86의 straight-line path에는 단일 5-byte atomic no-op이 놓인다.

branch를 flip하면 straight-line의 no-op을 out-of-line true branch로 가는 jump instruction으로 patch한다. branch 방향을 바꾸는 작업은 비싸지만 이후의 branch 선택은 사실상 무료라는 것이 이 최적화의 핵심 tradeoff다.

이 low-level patching mechanism을 jump label patching이라고 하며 static key 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 taken
by default, without the need to check memory. Then, at run-time, we can patch
the 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 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.

Key 정의와 branch site 사용

최적화를 사용하려면 `DEFINE_STATIC_KEY_TRUE(key)` 또는 `DEFINE_STATIC_KEY_FALSE(key)`로 key를 먼저 정의한다. key는 global이어야 하므로 stack에 두거나 runtime에 동적으로 할당할 수 없다.

code에서는 `static_branch_unlikely(&key)` 또는 `static_branch_likely(&key)` 조건으로 likely와 unlikely 경로를 나눈다. `DEFINE_STATIC_KEY_TRUE()`와 `DEFINE_STATIC_KEY_FALSE()` 중 어느 것으로 정의했든 두 branch helper 중 어느 것과도 함께 사용할 수 있다.

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 dynamically
allocated at run-time.

The key is then used in code as::

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

Or::

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

Keys defined via DEFINE_STATIC_KEY_TRUE(), or DEFINE_STATIC_KEY_FALSE, may
be used in either static_branch_likely() or static_branch_unlikely()
statements.

상태 전환, reference count와 CPU hotplug

`static_branch_enable(&key)`은 branch를 true로, `static_branch_disable(&key)`은 false로 설정한다. reference-count 방식은 `static_branch_inc()`와 `static_branch_dec()`를 사용한다.

`static_branch_inc()`는 적절한 reference count를 증가시키며 branch를 true로 만들고, `static_branch_dec()`는 감소시키며 false로 만든다. true로 초기화한 key는 `dec()`로 false가 되고 다음 `inc()`로 true가 된다. false 초기 key는 `inc()`로 true, 이후 `dec()`로 다시 false가 된다.

현재 상태와 reference count는 `static_key_enabled()`와 `static_key_count()`로 얻는다. 일반적으로 이 조회는 enable/disable 또는 inc/dec를 보호하는 것과 같은 mutex로 보호해야 한다.

branch 전환은 kernel patch 중 CPU가 새로 들어오는 race를 피하기 위해 CPU hotplug lock을 비롯한 lock을 잡는다. 따라서 hotplug notifier 안에서 일반 static key API를 호출하면 deadlock이 확실하다.

그 특수 context를 위해 `_cpuslocked` 변형인 `static_key_enable_cpuslocked()`, `static_key_disable_cpuslocked()`, `static_branch_enable_cpuslocked()`, `static_branch_disable_cpuslocked()`가 제공된다. 이는 범용 API가 아니며 정확히 해당 context임을 아는 경우에만 사용해야 한다.

key 배열은 `DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count)` 또는 `DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count)`로 정의한다.

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 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.

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.

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 while 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
functionality, 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.

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

Architecture jump-label 구현 인터페이스

architecture가 jump-label 최적화를 사용하려면 몇 가지 함수와 macro를 구현해야 한다. 지원이 없으면 전통적인 load, test, jump sequence로 fallback한다.

`static_key->entry` field가 두 least-significant bit를 사용하므로 `struct jump_entry` table은 최소 4-byte alignment를 가져야 한다.

필요한 interface는 `HAVE_ARCH_JUMP_LABEL` 선택, `JUMP_LABEL_NOP_SIZE`, `arch_static_branch()`, `arch_static_branch_jump()`, `arch_jump_label_transform()`, `struct jump_entry`다. 원문은 x86 Kconfig, `arch/x86/include/asm/jump_label.h`, `arch/x86/kernel/jump_label.c`를 구현 예로 든다.

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
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.

* ``select HAVE_ARCH_JUMP_LABEL``,
    see: arch/x86/Kconfig

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

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

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

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

* ``struct jump_entry``,
    see: arch/x86/include/asm/jump_label.h

x86_64 getppid instruction 분석

분석 예는 `getppid()` system call에 `static_branch_unlikely(&key)` 조건과 `printk()` true branch를 추가한다. GCC가 jump label을 생성한 instruction sequence와 최적화가 없는 sequence를 비교한다.

jump-label version의 기본 disabled path에는 `jmpq`의 5-byte 자리만 있고 boot 때 5-byte atomic no-op으로 patch된다. true branch의 `printk()`는 out-of-line에 놓이며 활성화 시 jump가 그쪽으로 향한다.

최적화가 없으면 fast path가 global key를 읽는 `mov`, 값을 검사하는 `test`, true branch로 가는 `jne`를 매번 실행한다. disabled case에서 이 세 instruction은 6+2+2=10 byte이고 jump-label 자리 5 byte와 비교하면 5 byte가 추가된다.

padding까지 포함하면 이 작은 함수에서 jump-label code가 instruction memory 16 byte를 절약한다. 비최적화 함수가 80 byte이므로 instruction footprint가 20% 줄어든다.

분기 거리가 2-byte jump로 닿는다면 5-byte no-op 대신 2-byte no-op을 써서 더 줄일 수 있지만, 문서 시점에는 optimal no-op size가 구현되지 않고 크기가 hard-coded되어 있다.

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


As an example, let's add the following branch to 'getppid()', such that the
system 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   %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

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
label 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 bytes
of instruction memory for this small function. In this case the non-jump label
function is 80 bytes long. Thus, we have saved 20% of the instruction
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).

Scheduler pipe-test 실측 결과

scheduler path에 static key API 사용이 많으므로 `pipe-test`, 즉 `perf bench sched pipe`로 성능 향상을 확인할 수 있다. 원문 결과는 Linux 3.3.0-rc2에서 50회 실행한 성능 counter다.

jump label disabled 결과는 task-clock 855.700314, cycles 1,474,374,262, instructions 1,178,049,567, branches 208,368,926, branch-misses 5,569,188, elapsed 1.601607384초다.

jump label enabled 결과는 task-clock 841.043185, cycles 1,432,559,428, instructions 1,175,363,994, branches 206,859,359, branch-misses 4,884,119, elapsed 1.579384366초다. 두 경우 모두 약 200,000번의 context switch, 0 CPU migration, 487 page fault를 기록했다.

문서가 계산한 개선은 branch 0.7%, branch-miss 12%, instruction 0.2%, cycle 2.8%, elapsed time 1.4% 감소다. branch 수를 줄이는 최적화이므로 가장 큰 절약이 branch-miss에서 나타나는 것이 예상과 맞는다.

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:

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, 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.