Static keys

원문은 리눅스 커널 documentation 의 static-keys 입니다. 전문번역이 아닌 개인적 이해를 바탕으로 해석한 것입니다. 원문을 충실히 다루지도 않았고, “Analysis” 부분은 직접 분석한 내용을 담았습니다. 오자나 오류는 전적으로 그로인한 결과일 것입니다. 알려주시면 기쁘게 수정/반영하겠습니다.

Abstract

Static key 는 GCC 기능과 코드 패칭 기술을 통해 성능이 중요한 fast-path 커널 코드 사이에 자주 사용되지 않는 기능을 삽입 가능하게 한다. 다음 예제를 참고하라:

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

likely 코드 경로에 최대한 영향을 미치지 않는 방향으로 static_branch_unlikely() 분기가 삽입될 것이다.

Motivation

현재 tracepoints는 조건분기로 구현되어 있고, 조건검사는 각 tracepoint 마다 전역변수를 체크하는 것으로 이루어진다. 이러한 조건검사 자체의 오버헤드는 미미하지만 전역변수에 할당된 메모리 캐시 라인이 다른 메모리 공간과 공유될 때(하나의 메모리 캐시 라인은 서로 다른 여러 메모리 공간에서 공유되므로) 메모리 캐시 사용량이 늘어날수록 그 오버헤드가 커진다. 커널 내 tracepoints 가 늘어날수록 오버헤드는 무시할 수 없는 문제가 된다. 게다가 tracepoints 는 보통 사용되지 않는대다 직접적인 커널 기능을 제공하지도 않는다. 따라서 tracepoints 조건문의 영향을 최소화하는 것이 효과적일 것이다.

static key 매커니즘은 이와 같이 tracepoints 오버헤드를 최소화하기 위해 개발되었지만 다른 커널 코드 경로에도 사용할 수 있다.

Solution

gcc 버전 4.5에서 레이블로 분기할 수 있는 asm goto 구문이 추가되었다: http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html

asm goto를 사용하면 메모리 로드없이 분기하거나 또는 분기하지 않고 순차적으로 실행되는 코드흐름을 만들 수 있다. 또한 런타임에 코드흐름을 변경할 수 있다. asm goto는 자동적으로 volatile 속성을 갖는다.

가령 기본적으로 분기하지 않는 다음과 같은 구문이 있다면:

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

printk 함수는 실행되지 않을 것이고, 분기조건문은 단지 no-op 명령어로 대체될 것이다. 이후 런타임에 분기 흐름을 타도록 변경하면 no-op 명령어는 jump 명령으로 대체되고 순차적이었던 코드흐름은 깨지게 된다. 현재 코드를 런타임에 다른 코드로 대체해야 하기 때문에 코드흐름을 변경하는 것은 상대적으로 성능상 부담이 크다. 하지만 분기조건이 결정된 이후에(코드흐름을 변경하는 경우가 아니라면) 조건검사가 없으므로 분기하는 데에 아무 비용이 들지 않는다.

static key 를 구현하는 데 사용된 이 기반 코드 패칭 매커니즘을 jump label patching이라고 부른다.

Usage

static key 라는 조건분기 최적화를 사용하기 위해서는 키(key)를 먼저 다음과 같이 정의(등록)해야 한다:

    DEFINE_STATIC_KEY_TRUE(key);

또는:

    DEFINE_STATIC_KEY_FALSE(key);

키는 런타임에 등록할 수 없고 반드시 global 변수여야 한다. 즉, 스택 또는 동적으로 할당된 메모리 공간에 위치할 수 없다.

등록한 키는 다음과 같이 사용된다:

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

또는:

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

DEFINE_STATIC_KEY_TRUE() 또는 DEFINE_STATIC_KEY_FALSE() 로 등록된 키는 static_branch_likely() 또는 static_branch_unlikely() 구문에서 사용될 수 있다.

분기 조건은 다음과 같이 참true으로 설정할 수 있다:

static_branch_enable(&key);

또는 거짓false으로 설정할 수 있다.

static_branch_disable(&key);

그리고 분기 조건은 다음과 같이 참조 카운트reference counts로 변경switched할 수 있다.

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

참조 카운트에 따라 static_branch_inc() 는 분기 조건을 참으로 만들고, static_branch_dec() 는 분기 조건을 거짓으로 만든다. 예컨데 키가 참true으로 초기화되었다면 static_branch_dec() 는 분기 조건을 거짓으로 만들 것이다. 그 뒤에 실행되는 static_branch_inc() 는 분기 조건을 참으로 만든다. 만약 키가 거짓으로 초기화되었다면 마찬가지로 static_branch_inc() 는 분기 조건을 참으로 만들 것이고 뒤따른 static_branch_dec() 는 분기 조건을 거짓으로 만들 것이다.

Analysis

키 등록부터 살펴보자:

#define DEFINE_STATIC_KEY_TRUE(name)    \
        struct static_key_true name = STATIC_KEY_TRUE_INIT

키 타입은 struct static_key_true{false} 로 한단계 추상화된다. 이는 컴파일 시점에 타입체크1를 수행해 적절한 코드2를 삽입하기 위해서다.

한단계 추상화된 랩퍼wrapper 타입 내부의 실제 타입은 다음과 같다:

struct static_key {
        atomic_t enabled;
/* Set lsb bit to 1 if branch is default true, 0 ot */
        struct jump_entry *entries;
#ifdef CONFIG_MODULES
        struct static_key_mod *next;
#endif
};

TRUE로 등록된 키는 .enabled = 1, entries = (void *)1로 초기화된다. FALSE로 등록된 키는 두 변수 모두 0으로 초기화된다.

다음으로 static_branch_likely() 를 살펴보면:

#define static_branch_likely(x)                                                 \
({                                                                              \
        bool branch;                                                            \
        if (__builtin_types_compatible_p(typeof(*x), struct static_key_true))   \
                branch = !arch_static_branch(&(x)->key, true);                  \
        else if (__builtin_types_compatible_p(typeof(*x), struct static_key_false)) \
                branch = !arch_static_branch_jump(&(x)->key, true);             \
        else                                                                    \
                branch = ____wrong_branch_error();                              \
        branch;                                                                 \
})

위 코드의 조건문은 컴파일러 최적화에 의해 컴파일 시점에 모두 제거된다. 대신 그 위치에 분기 또는 nop 코드가 생성된다. likely, unlikely과 true, false의 조합으로 생성되는 코드의 결과는 다음과 같다:

type\branchlikely (1)unlikely (0)
true (1)
 NOPJMP L
 1: …
 L: … 
  L:
  jmp 1b
   
false (0)
 JMP LNOP
 1: …
 L: … 
  L:
  jmp 1b

likely의 경우 arch_static_branch{_jump} 함수를 호출할 때 매개변수 branch에 true(1) 값을, unlikely의 경우 false(0) 값을 넘긴다. 이는 호출된 함수에서 두가지 경우를 구분하기 위한 플래그로 jump_entry 구조체의 멤버 변수 key 최하위 비트에 인코딩된다.

다음으로 arch_static_branch{_jump} 따라가보면:

static __always_inline bool arch_static_branch(struct static_key *key, bool branch)
{
        asm_volatile_goto("1:\n\t"
                 WASM(nop) "\n\t"
                 ".pushsection __jump_table,  \"aw\"\n\t"
                 ".word 1b, %l[l_yes], %c0\n\t"
                 ".popsection\n\t"
                 : :  "i" (&((char *)key)[branch]) :  : l_yes);

        return false;
l_yes:
        return true;
}

static __always_inline bool arch_static_branch_jump(struct static_key *key, bool branch)
{
        asm_volatile_goto("1:\n\t"
                 WASM(b) " %l[l_yes]\n\t"
                 ".pushsection __jump_table,  \"aw\"\n\t"
                 ".word 1b, %l[l_yes], %c0\n\t"
                 ".popsection\n\t"
                 : :  "i" (&((char *)key)[branch]) :  : l_yes);

        return false;
l_yes:
        return true;
}

인라인 어셈블리 코드상에 데이터 영역 .word 1b, %l[l_yes], %c03부분은 struct jump_entry 타입으로 __jump_table 메모리 섹션에 쌓이게 된다. 이때 어셈블리 코드상의 레이블 1의 위치address는 jump_entry->code 변수에 저장되고, l_yes C 레이블은 jump_entry->target 변수에, 그리고 &((char *)key)[branch](데이터 타입의 짝수 시작주소 또는 홀수 시작주소)는 jump_entry->key 변수에 저장된다.

branch 값이 true(likely)일 때, key 변수가 가리키는 static_key 구조체의 시작주소는 (char *)&[1]이 되고, false(unlikely)일 때는 (char *)&[0]가 된다. 즉, entry->key를 읽었을 때 최하위 비트가 1이라면 likely, 0이라면 unlikely라고 디코딩된다.

결국 static_key 구조체의 멤버 변수 entries의 최하위 비트에는 초기 타입값이 true인지 false인지가 인코딩되고, jump_entry 구조체의 멤버 변수 key의 최하위 비트에는 분기 타입이 likely인지 unlikely인지가 인코딩된다.

jump_lable 초기화시4 분기 유/무에 따라 jump_entry->code 즉, 레이블 1 위치에 분기 코드가 삽입되거나 nop 코드가 삽입된다5.

TODO

References

  1. __builtin_types_compatible_p() - 인자로 넘어간 두 변수의 타입이 호환성을 갖는다면(동일하다면) 1을 리턴하고, 그렇지 않다면(다르다면) 0을 리턴한다. 최상위 레벨의 한정사 const, volatile 속성은 무시된다. 즉, const intint는 동일 타입으로 간주한다. int[]int[5] 역시 동일 타입으로 간주한다. 아키텍처에 따라 타입의 사이즈가 동일한 intchar *는 동일 타입으로 간주하지 않는다. short *short **은 서로 다른 타입이며, 각 enum 역시 동일 타입으로 간주하지 않는다. ↩︎

  2. arch_static_branch() 또는 arch_static_branch_jump(). arch_static_branchnop을 삽입하는 반면 arch_static_branch_jump는 분기코드를 삽입한다 ↩︎

  3. %c는 컴파일러가 상수에 붙이는 일련의 정보를 추가하지 않도록 함 ↩︎

  4. jump_label_init() at start_kernel() in /init/main.c ↩︎

  5. 사실 컴파일 시점에 이미 조건문은 모두 제거된 상태이나 static_key 구조체 설정과 동적 변경을 위해 초기화가 필요 ↩︎