Static Keys -1- (Core API)

<kernel v5.0>

Static Keys -1- (Core API)

Static keys는 GCC 기능과 커널 코드 교체 기술로 조건을 빠르게 수행할 수 있는 fast-path 솔루션으로 branch miss 확률을 약간 줄여준다. Static Keys는 조건문의 수행이 매우 빈번하여 고성능을 추구할 때 사용되며, 조건의 변경 시에는 커널과 모듈의 코드가 변경되며, 모든 코어의 TLB 캐시를 flush 해야 하는 등 매우 큰 코스트가 발생하므로 변경이 빈번하지 않는 경우에만 사용해야 한다.

 

New Interface 소개

최근 커널 4.3-rc1에서 새로운 interface API가 제공된다.

 

Deprecated Method

다음과 같은 사용 방법들은 일정 기간 새로운 method와 같이 사용되고 이 후 어느 순간 사용되지 않을 계획이다.

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

기존 사용 예)

        struct static_key key = STATIC_KEY_INIT_FALSE;

        ...

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

 

New Method

  • DEFINE_STATIC_KEY_TRUE(key);
  • DEFINE_STATIC_KEY_FALSE(key);
  • static_branch_likely()
  • static_branch_unlikely()

개선된 사용 예)

	DEFINE_STATIC_KEY_FALSE(key);

	...

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

 


Static Key – Old API

Static Key 선언

STATIC_KEY_INIT

include/linux/jump_label.h

#define STATIC_KEY_INIT STATIC_KEY_INIT_FALSE

 

#define STATIC_KEY_INIT_TRUE ((struct static_key) \
                { .enabled = ATOMIC_INIT(1) })
#define STATIC_KEY_INIT_FALSE ((struct static_key) \
                { .enabled = ATOMIC_INIT(0) })

 

Static Key 브랜치

static_key_false()

include/linux/jump_label.h

static __always_inline bool static_key_false(struct static_key *key)
{
        return arch_static_branch(key);
}

 

static_key_true()

include/linux/jump_label.h

static __always_inline bool static_key_true(struct static_key *key)
{
        return !static_key_false(key);
}

 


Static Key – New API

Static Key 선언

DEFINE_STATIC_KEY_TRUE() & DEFINE_STATIC_KEY_FALSE()

include/linux/jump_label.h

#define DEFINE_STATIC_KEY_TRUE(name)    \
        struct static_key_true name = STATIC_KEY_TRUE_INIT
#define DEFINE_STATIC_KEY_FALSE(name)   \
        struct static_key_false name = STATIC_KEY_FALSE_INIT

주어진 이름(@name)으로 true static key 또는 false static key의 구조체를 초기화한다.

 

include/linux/jump_label.h

#define STATIC_KEY_TRUE_INIT  (struct static_key_true) { .key = STATIC_KEY_INIT_TRUE,  }
#define STATIC_KEY_FALSE_INIT (struct static_key_false){ .key = STATIC_KEY_INIT_FALSE, }

true static key와 false static key의 구조체를 초기화한다.

 

include/linux/jump_label.h

#define STATIC_KEY_INIT_TRUE                                    \
        { .enabled = { 1 },                                     \
          { .entries = (void *)JUMP_TYPE_TRUE } }
#define STATIC_KEY_INIT_FALSE                                   \
        { .enabled = { 0 },                                     \
          { .entries = (void *)JUMP_TYPE_FALSE } }

entries의 lsb 1비트를 사용하여 true 또는 false로 초기 설정을 한다.

  • 컴파일타임에 static 키를 true 또는 false로 설정할 때 enabled와 entries가 둘 다 1 또는 0으로 설정된다.
  • entries는 컴파일 타임에 결정된 후 변경되지 않는다.
  • enabled는 런타임에 변경된다.

 

include/linux/jump_label.h

struct static_key_true {
        struct static_key key;
};

struct static_key_false {
        struct static_key key;
};

static_key_true 도는 static_key_false 구조체는 static_key 구조체 하나를 포함한다.

 

Static Key 브랜치

likely와 unlikely는 컴파일러가 생성하는 코드의 위치가 달라진다.

  • static_branch_likely() 함수의 경우
    • 조건을 만족하는 코드들이 해당 문장에 같이 놓이게 컴파일된다.
  • static_branch_unlikely() 함수의 경우
    • 조건을 만족하는 코드들이 해당 문장에서 먼 위치에 놓이게 컴파일된다.

 

static_branch_likely()

include/linux/jump_label.h

/*
 * Combine the right initial value (type) with the right branch order
 * to generate the desired result.
 *
 *
 * type\branch| likely (1)            | unlikely (0)
 * -----------+-----------------------+------------------
 *            |                       |
 *  true (1)  |    ...                |    ...
 *            |    NOP                |    JMP L
 *            |    <br-stmts>         | 1: ...
 *            | L: ...                |
 *            |                       |
 *            |                       | L: <br-stmts>
 *            |                       |    jmp 1b
 *            |                       |
 * -----------+-----------------------+------------------
 *            |                       |
 *  false (0) |    ...                |    ...
 *            |    JMP L              |    NOP
 *            |    <br-stmts>         | 1: ...
 *            | L: ...                |
 *            |                       |
 *            |                       | L: <br-stmts>
 *            |                       |    jmp 1b
 *            |                       |
 * -----------+-----------------------+------------------
 *
 * The initial value is encoded in the LSB of static_key::entries,
 * type: 0 = false, 1 = true.
 *
 * The branch type is encoded in the LSB of jump_entry::key,
 * branch: 0 = unlikely, 1 = likely.
 *
 * This gives the following logic table:
 *
 *      enabled type    branch    instuction
 * -----------------------------+-----------
 *      0       0       0       | NOP
 *      0       0       1       | JMP
 *      0       1       0       | NOP
 *      0       1       1       | JMP
 *
 *      1       0       0       | JMP
 *      1       0       1       | NOP
 *      1       1       0       | JMP
 *      1       1       1       | NOP
 *
 * Which gives the following functions:
 *
 *   dynamic: instruction = enabled ^ branch
 *   static:  instruction = type ^ branch
 *
 * See jump_label_type() / jump_label_init_type().
 */
#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();                              \
        likely(branch);                                                         \
})

likely문 처럼 조건에 걸릴 확률이 높은 경우에는 조건에 걸려 동작하는 명령(nop 또는 jmp)이 코드 근접 범위에 있다.

 

static_branch_unlikely()

include/linux/jump_label.h

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

unlikely문 처럼 조건에 걸릴 확률이 낮은 경우에는 조건에 걸려 동작하는 명령이 멀리 떨어져 있다.

 

다음 그림은 static key 사용 시 likely와 unlikely 조건에 따라 코드 배치와 jump 엔트리의 기록 타입(nop/jmp)을 보여준다.

 

다음 그림은 static key 사용에 따른 likely와 unlikely 조건에 따라 코드 배치와 jump 엔트리의 기록 타입(nop/jmp)과 런타임에 변경된 코드의 변화를 보여준다.

 


Jump 라벨 사용

arch_static_branch() – ARM32

arch/arm/include/asm/jump_label.h

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

        return false;
l_yes:
        return true;
}

nop 명령이 디폴트로 동작하는 Jump 라벨이다.

  • 함수 호출 부분에 nop 코드를 배치하고 __jump_table 섹션에 3개의 word를 push한다. push되는 항목은 jump_entry 구조체 동일하다.

 

arch_static_branch_jump() – ARM32

arch/arm/include/asm/jump_label.h

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

jmp 명령이 디폴트로 동작하는 Jump 라벨이다.

 

아래 그림 역시 신규 static key API에 의해 등록되는 과정을 보여준다.

 

arch_static_branch() – ARM64

arch/arm64/include/asm/jump_label.h

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

        return false;
l_yes:
        return true;
}

nop 명령이 디폴트로 동작하는 Jump 라벨이다.

  • 두 개의 4바이트 long 값은 code와 target에 해당하는 주소에서 현재 주소(.)를 뺀 상대 위치를 저장한다.
  • 마지막으로 8바이트 quad 값은 key에 해당하는 주소에서 현재 주소(.)를 뺀 상대 위치를 저장한다.

 

arch_static_branch_jump() – ARM64

arch/arm64/include/asm/jump_label.h

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

        return false;
l_yes:
        return true;
}

jmp 명령이 디폴트로 동작하는 Jump 라벨이다.

 

static_key_enabled()

include/linux/jump_label.h

#define static_key_enabled(x)                                                   \
({                                                                              \
        if (!__builtin_types_compatible_p(typeof(*x), struct static_key) &&     \
            !__builtin_types_compatible_p(typeof(*x), struct static_key_true) &&\
            !__builtin_types_compatible_p(typeof(*x), struct static_key_false)) \
                ____wrong_branch_error();                                       \
        static_key_count((struct static_key *)x) > 0;                           \
})

static 키가 enable 상태인지 여부를 반환한다.

  • 카운트 값이 1 이상인 경우 true(1)를 반환한다.

 

static_key_count()

include/linux/jump_label.h

static inline int static_key_count(struct static_key *key)
{
        return atomic_read(&key->enabled);
}

static 키 카운트 값을 반환한다.

 


런타임중 Key 조건 변경 API

1) 일반 API

static_branch_enable() & static_branch_disable()

include/linux/jump_label.h

/*
 * Normal usage; boolean enable/disable.
 */
#define static_branch_enable(x)                 static_key_enable(&(x)->key)
#define static_branch_disable(x)                static_key_disable(&(x)->key)

static 키를 enable(1) 하거나 disable(0) 한다. 그리고 변경된 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

 

static_key_enable()

kernel/jump_label.c

void static_key_enable(struct static_key *key)
{
        cpus_read_lock();
        static_key_enable_cpuslocked(key);
        cpus_read_unlock();
}
EXPORT_SYMBOL_GPL(static_key_enable);

static 키를 enable(변경) 하고 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

 

static_key_enable_cpuslocked()

kernel/jump_label.c

void static_key_enable_cpuslocked(struct static_key *key)
{
        STATIC_KEY_CHECK_USE(key);
        lockdep_assert_cpus_held();

        if (atomic_read(&key->enabled) > 0) {
                WARN_ON_ONCE(atomic_read(&key->enabled) != 1);
                return;
        }

        jump_label_lock();
        if (atomic_read(&key->enabled) == 0) {
                atomic_set(&key->enabled, -1);
                jump_label_update(key);
                /*
                 * See static_key_slow_inc().
                 */
                atomic_set_release(&key->enabled, 1);
        }
        jump_label_unlock();
}
EXPORT_SYMBOL_GPL(static_key_enable_cpuslocked);
  • 코드 라인 6~9에서 다른 cpu에서 이미 enable 요청하여 이미 enable 된 상태인 경우에는 함수를 그냥 빠져나간다.
  • 코드 라인 11~20에서 lock을 획득한채로 다시 한 번 enable 여부를 확인해본다. 여전히 다른 cpu와 경쟁하지 않는 상태인 경우 jump 라벨을 업데이트 하기 전에 enabled를 먼저 -1로 상태를 바꾼 상태에서 jump 라벨을 변경한다. 모두 완료되면 1로 변경을 한다.

 

static_key_disable()

kernel/jump_label.c

void static_key_disable(struct static_key *key)
{
        cpus_read_lock();
        static_key_disable_cpuslocked(key);
        cpus_read_unlock();
}
EXPORT_SYMBOL_GPL(static_key_disable);

static 키를 disable(0) 하고 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

 

static_key_disable_cpuslocked()

kernel/jump_label.c

void static_key_disable_cpuslocked(struct static_key *key)
{
        STATIC_KEY_CHECK_USE(key);
        lockdep_assert_cpus_held();

        if (atomic_read(&key->enabled) != 1) {
                WARN_ON_ONCE(atomic_read(&key->enabled) != 0);
                return;
        }

        jump_label_lock();
        if (atomic_cmpxchg(&key->enabled, 1, 0))
                jump_label_update(key);
        jump_label_unlock();
}
EXPORT_SYMBOL_GPL(static_key_disable_cpuslocked);
  • 코드 라인 6~9에서 다른 cpu에서 이미 disable 요청하여 이미 disable된 상태인 경우에는 함수를 그냥 빠져나간다.
  • 코드 라인 11~14에서 lock을 획득한채로 disable 상태로 바꾼다. 다른 cpu와 경쟁 상태가 아닌 경우 jump 라벨을 변경한다.

 

2) Advanced API

static_branch_inc() & static_branch_dec()

include/linux/jump_label.h

/*
 * Advanced usage; refcount, branch is enabled when: count != 0
 */
#define static_branch_inc(x)            static_key_slow_inc(&(x)->key)
#define static_branch_dec(x)            static_key_slow_dec(&(x)->key)

static 키 카운터를 증가시키거나 감소시킨다. 증가 시켜 처음 1이 된 경우 또는 감소 시켜 다시 0이 된 경우 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

 

static_key_slow_inc()

kernel/jump_label.c

void static_key_slow_inc(struct static_key *key)
{
        cpus_read_lock();
        static_key_slow_inc_cpuslocked(key);
        cpus_read_unlock();
}
EXPORT_SYMBOL_GPL(static_key_slow_inc);

static 키 카운터를 증가시킨다. 처음 1이 된 경우 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

 

static_key_slow_inc_cpuslocked()

kernel/jump_label.c

void static_key_slow_inc_cpuslocked(struct static_key *key)
{
        int v, v1;

        STATIC_KEY_CHECK_USE(key);
        lockdep_assert_cpus_held();

        /*
         * Careful if we get concurrent static_key_slow_inc() calls;
         * later calls must wait for the first one to _finish_ the
         * jump_label_update() process.  At the same time, however,
         * the jump_label_update() call below wants to see
         * static_key_enabled(&key) for jumps to be updated properly.
         *
         * So give a special meaning to negative key->enabled: it sends
         * static_key_slow_inc() down the slow path, and it is non-zero
         * so it counts as "enabled" in jump_label_update().  Note that
         * atomic_inc_unless_negative() checks >= 0, so roll our own.
         */
        for (v = atomic_read(&key->enabled); v > 0; v = v1) {
                v1 = atomic_cmpxchg(&key->enabled, v, v + 1);
                if (likely(v1 == v))
                        return;
        }

        jump_label_lock();
        if (atomic_read(&key->enabled) == 0) {
                atomic_set(&key->enabled, -1);
                jump_label_update(key);
                /*
                 * Ensure that if the above cmpxchg loop observes our positive
                 * value, it must also observe all the text changes.
                 */
                atomic_set_release(&key->enabled, 1);
        } else {
                atomic_inc(&key->enabled);
        }
        jump_label_unlock();
}

static 키를 카운터를 증가시킨다. 처음 1이 된 경우 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

  • 코드 라인 20~24에서 카운터를 읽어 1 보다 큰 경우이므로, 처음 증가시킨 경우가 아닌 두 번 이상의 증가를 요청한 경우이다. 이 때 카운터를 atomic하게 증가시킨 후 경쟁 상황이 아니었으면 정상적으로 함수를 빠져나간다.
  • 코드 라인 26~34에서 락을 잡은 후 카운터를 0에서 처음 증가 시킨 경우에는 jump 라벨을 업데이트 하기 전에 먼저 -1로 상태를 바꾼 상태에서 jump 라벨을 변경한다. 모두 완료되면 1로 변경을 한다.
  • 코드 라인 35~37에서 다른 cpu에서 먼저 1로 증가시킨 경우이다. 이러한 경우 카운터만 증가시킨다.

 

static_key_slow_dec()

kernel/jump_label.c

void static_key_slow_dec(struct static_key *key)
{
        STATIC_KEY_CHECK_USE(key);
        __static_key_slow_dec(key, 0, NULL);
}
EXPORT_SYMBOL_GPL(static_key_slow_dec);

static 키를 카운터를 감소시킨다. 카운터가 0이 된 경우 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

 

__static_key_slow_dec()

kernel/jump_label.c

static void __static_key_slow_dec(struct static_key *key,
                                  unsigned long rate_limit,
                                  struct delayed_work *work)
{
        cpus_read_lock();
        __static_key_slow_dec_cpuslocked(key, rate_limit, work);
        cpus_read_unlock();
}

static 키를 카운터를 감소시킨다. 카운터가 0이 된 경우 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

  • rate_limit가 주어진 경우 rate_limit 만큼 딜레이 요청된 워크를 수행한다.

 

__static_key_slow_dec_cpuslocked()

kernel/jump_label.c

static void __static_key_slow_dec_cpuslocked(struct static_key *key,
                                           unsigned long rate_limit,
                                           struct delayed_work *work)
{
        lockdep_assert_cpus_held();

        /*
         * The negative count check is valid even when a negative
         * key->enabled is in use by static_key_slow_inc(); a
         * __static_key_slow_dec() before the first static_key_slow_inc()
         * returns is unbalanced, because all other static_key_slow_inc()
         * instances block while the update is in progress.
         */
        if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex)) {
                WARN(atomic_read(&key->enabled) < 0,
                     "jump label: negative count!\n");
                return;
        }

        if (rate_limit) {
                atomic_inc(&key->enabled);
                schedule_delayed_work(work, rate_limit);
        } else {
                jump_label_update(key);
        }
        jump_label_unlock();
}

static 키를 카운터를 감소시킨다. 카운터가 0이 된 경우 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

  • 코드 라인 14~18에서 카운터가 0 보다 작은 값이 되는 경우 경고 메시지를 출력하고 함수를 빠져나간다.
  • 코드 라인 20~22에서 jump_label_rate_limit() API를 사용하여 요청된 경우 rate_limit만큼 지연시켜 워크류를 동작시킨 후 jump 라벨들을 업데이트 한다.
    • x86 kvm 내에서 사용하고 있다.
  • 코드 라인 23~25에서 해당 static 키를 사용하는 모든 jump 라벨들을 업데이트한다.

 


Jump Label 수정

jump_label_update()

kernel/jump_label.c

static void jump_label_update(struct static_key *key)
{
        struct jump_entry *stop = __stop___jump_table;
        struct jump_entry *entry;
#ifdef CONFIG_MODULES
        struct module *mod;

        if (static_key_linked(key)) {
                __jump_label_mod_update(key);
                return;
        }

        preempt_disable();
        mod = __module_address((unsigned long)key);
        if (mod)
                stop = mod->jump_entries + mod->num_jump_entries;
        preempt_enable();
#endif
        entry = static_key_entries(key);
        /* if there are no users, entry can be NULL */
        if (entry)
                __jump_label_update(key, entry, stop,
                                    system_state < SYSTEM_RUNNING);
}

static 키를 변경한 경우 static 키가 존재하는 모듈 또는 커널의 초기화되지 않은 jump 엔트리들을 업데이트한다. 부트 업 중에 요청된 경우 초기화 여부와 관계없이 업데이트한다.

  • 코드 라인 8~11에서 static 키가 로드된 모듈용인 경우 초기화되지 않은 jump 엔트리들을 업데이트한다. 모듈이 처음 로딩되는 중이면 초기화 여부와 관계없이 업데이트한다.
  • 코드 라인 13~17에서 static 키가 커널과 함께 로드된 모듈 영역에 있는 경우 업데이트 범위에 그 모듈의 끝 엔트리로를 포함시킨다.
  • 코드 라인 19~23에서 static 키 엔트리가 발견된 경우 초기화되지 않은 jump 엔트리들을 업데이트한다. 부트 업 중에 요청된 경우 초기화 여부와 관계없이 업데이트한다.

 

__jump_label_mod_update()

kernel/jump_label.c

static void __jump_label_mod_update(struct static_key *key)
{
        struct static_key_mod *mod;

        for (mod = static_key_mod(key); mod; mod = mod->next) {
                struct jump_entry *stop;
                struct module *m;

                /*
                 * NULL if the static_key is defined in a module
                 * that does not use it
                 */
                if (!mod->entries)
                        continue;

                m = mod->mod;
                if (!m)
                        stop = __stop___jump_table;
                else
                        stop = m->jump_entries + m->num_jump_entries;
                __jump_label_update(key, mod->entries, stop,
                                    m && m->state == MODULE_STATE_COMING);
        }
}

요청한 static 키를 사용하는 모듈들을 순회하며 jump 엔트리들을 업데이트한다.

  • 코드 라인 5~14에서 요청한 static 키를 사용하는 모듈들을 순회하며 entries가 null인 경우 사용하지 않는 경우이므로 skip 한다.
  • 코드 라인 16~22에서 모듈이 지정되지 않은 경우 모든 jump 라벨을 대상으로하고, 모듈이 지정된 경우 해당 모듈의 점프 엔트리들까지를 대상으로 초기화되지 않은 jump 라벨 엔트리들을 업데이트한다. 만일 모듈이 로드되는 중에 요청된 경우 초기화 여부 관계 없이 업데이트한다.

 

__jump_label_update()

kernel/jump_label.c

static void __jump_label_update(struct static_key *key,
                                struct jump_entry *entry,
                                struct jump_entry *stop,
                                bool init)
{
        for (; (entry < stop) && (jump_entry_key(entry) == key); entry++) {
                /*
                 * An entry->code of 0 indicates an entry which has been
                 * disabled because it was in an init text area.
                 */
                if (init || !jump_entry_is_init(entry)) {
                        if (kernel_text_address(jump_entry_code(entry)))
                                arch_jump_label_transform(entry, jump_label_type(entry));
                        else
                                WARN_ONCE(1, "can't patch jump_label at %pS",
                                          (void *)jump_entry_code(entry));
                }
        }
}

@entry ~ @stop 까지의 jump 엔트리들을 대상으로  아직 기록되지 않았거나, 인자로 요청한 @init이 true인 경우 jump 엔트리들을 수정하여 기록한다.

 

1) Jump 라벨 수정 for ARM32

arch_jump_label_transform() – ARM32

void arch_jump_label_transform(struct jump_entry *entry,
                               enum jump_label_type type)
{
        __arch_jump_label_transform(entry, type, false);
}

요청 타입(nop, branch)에 따라 변경할 한 개의 워드 코드를 patch 한다.

 

arch_jump_label_transform_static() – ARM32

arch/arm/kernel/jump_label.c

void arch_jump_label_transform_static(struct jump_entry *entry,
                                      enum jump_label_type type)
{
        __arch_jump_label_transform(entry, type, true);
}

요청 타입(nop, branch)에 따라 변경할 한 개의 워드 코드를 early patch 한다.

 

__arch_jump_label_transform()

arch/arm/kernel/jump_label.c

static void __arch_jump_label_transform(struct jump_entry *entry,
                                        enum jump_label_type type,
                                        bool is_static)
{
        void *addr = (void *)entry->code;
        unsigned int insn;

        if (type == JUMP_LABEL_JMP)
                insn = arm_gen_branch(entry->code, entry->target);
        else
                insn = arm_gen_nop();

        if (is_static)
                __patch_text_early(addr, insn);
        else
                patch_text(addr, insn);
}

요청 타입에 따라 변경할 한 개의 워드 코드를 patch 하는데 다음의 2 가지 옵션이 있다.

  • is_static을 true로 호출하는 경우 처음 변경된 경우 이므로 곧장 패치하고, false로 호출된 경우는 이미 운영 중인 코드이므로, 모든 cpu의 스케쥴러를 정지시킨 후 커널 영역을 fixmap 매핑 영역에 잠시 매핑한 후 patch 한다

 

  • 코드 라인 8~11에서 타입이 enable이면 branch 코드를 만들고, disable 이면 nop 코드를 만든다.
  • 코드 라인 13~16에서 early 요청이 있는 경우 early patch 코드를 수행하고, 그렇지 않은 경우 patch 코드를 수행한다.

 

arm_gen_branch()

arch/arm/include/asm/insn.h

static inline unsigned long
arm_gen_branch(unsigned long pc, unsigned long addr)
{
        return __arm_gen_branch(pc, addr, false);
}

ARM 또는 THUMB 브랜치 코드를 만들어온다.

 

__arm_gen_branch()

arch/arm/kernel/insn.c

unsigned long
__arm_gen_branch(unsigned long pc, unsigned long addr, bool link)
{
        if (IS_ENABLED(CONFIG_THUMB2_KERNEL))
                return __arm_gen_branch_thumb2(pc, addr, link);
        else
                return __arm_gen_branch_arm(pc, addr, link);
}

ARM 또는 THUMB 브랜치 코드를 만들어온다.

 

__arm_gen_branch_arm()

arch/arm/kernel/insn.c

static unsigned long
__arm_gen_branch_arm(unsigned long pc, unsigned long addr, bool link)
{
        unsigned long opcode = 0xea000000;
        long offset;

        if (link)
                opcode |= 1 << 24;

        offset = (long)addr - (long)(pc + 8);
        if (unlikely(offset < -33554432 || offset > 33554428)) {
                WARN_ON_ONCE(1);
                return 0;
        }

        offset = (offset >> 2) & 0x00ffffff;

        return opcode | offset;
}

ARM용 branch 코드를 만들어 word로 리턴한다.

 

arm_gen_nop()

arch/arm/include/asm/insn.h

static inline unsigned long
arm_gen_nop(void)
{
#ifdef CONFIG_THUMB2_KERNEL
        return 0xf3af8000; /* nop.w */
#else   
        return 0xe1a00000; /* mov r0, r0 */
#endif
}

ARM용 nop 코드로 mov r0, r0에 해당하는 word를 리턴한다.

 

__patch_text_early()

arch/arm/include/asm/patch.h

static inline void __patch_text_early(void *addr, unsigned int insn)
{
        __patch_text_real(addr, insn, false);
}

주어진 주소에 명령을 즉각 패치한다.

  • 커널 초기화 시에는 이 early 함수를 호출하여 사용한다.

patch_text()

arch/arm/kernel/patch.c

void __kprobes patch_text(void *addr, unsigned int insn)
{
        struct patch patch = {
                .addr = addr,
                .insn = insn,
        };

        stop_machine(patch_text_stop_machine, &patch, NULL);
}

cpu의 스케쥴링을 모두 정지 시킨 후 주어진 주소에 명령을 패치한다.

  • 커널이 운영중일 경우에는 커널 코드가 read만 허용하므로 fixmap 영역 중 한 페이지를 사용하여 잠시 매핑하여 수정하게 한다.
  • 참고로 커널 초기화 시에는 이 함수를 사용하지 않고 __patch_text_early() 함수를 사용한다.

 

patch_text_stop_machine()

arch/arm/kernel/patch.c

static int __kprobes patch_text_stop_machine(void *data)
{
        struct patch *patch = data;

        __patch_text(patch->addr, patch->insn);

        return 0;
}

주어진 주소 위치에 명령을 기록(패치)한다.

 

__patch_text()

arch/arm/include/asm/patch.h

static inline void __patch_text(void *addr, unsigned int insn)
{
        __patch_text_real(addr, insn, true);
}

주소에 주소 위치에 명령을 기록(패치)하고 리매핑한다.

__patch_text_real()

arch/arm/kernel/patch.c

void __kprobes __patch_text_real(void *addr, unsigned int insn, bool remap)
{
        bool thumb2 = IS_ENABLED(CONFIG_THUMB2_KERNEL);
        unsigned int uintaddr = (uintptr_t) addr;
        bool twopage = false;
        unsigned long flags;
        void *waddr = addr;
        int size;

        if (remap)
                waddr = patch_map(addr, FIX_TEXT_POKE0, &flags);
        else
                __acquire(&patch_lock);

        if (thumb2 && __opcode_is_thumb16(insn)) {
                *(u16 *)waddr = __opcode_to_mem_thumb16(insn);
                size = sizeof(u16);
        } else if (thumb2 && (uintaddr & 2)) {
                u16 first = __opcode_thumb32_first(insn);
                u16 second = __opcode_thumb32_second(insn);
                u16 *addrh0 = waddr;
                u16 *addrh1 = waddr + 2;

                twopage = (uintaddr & ~PAGE_MASK) == PAGE_SIZE - 2;
                if (twopage && remap)
                        addrh1 = patch_map(addr + 2, FIX_TEXT_POKE1, NULL);

                *addrh0 = __opcode_to_mem_thumb16(first);
                *addrh1 = __opcode_to_mem_thumb16(second);

                if (twopage && addrh1 != addr + 2) {
                        flush_kernel_vmap_range(addrh1, 2);
                        patch_unmap(FIX_TEXT_POKE1, NULL);
                }

                size = sizeof(u32);
        } else {
                if (thumb2)
                        insn = __opcode_to_mem_thumb32(insn);
                else
                        insn = __opcode_to_mem_arm(insn);

                *(u32 *)waddr = insn;
                size = sizeof(u32);
        }

        if (waddr != addr) {
                flush_kernel_vmap_range(waddr, twopage ? size / 2 : size);
                patch_unmap(FIX_TEXT_POKE0, &flags);
        } else
                __release(&patch_lock);

        flush_icache_range((uintptr_t)(addr),
                           (uintptr_t)(addr) + size);
}

ARM 코드에 대해 리매핑을 하지 않고 패치하는 경우는 간단하게 4바이트만 변경하고 해당 4바이트 주소의 i-cache를 flush한다. 리매핑이 필요한 경우에는 fix-map을 사용하여 매핑 후 명령 부분의 4바이트를 변경하고 cpu 아키텍처에 따라 해당 4바이트 영역의 d-cache에 대해 flush하고 fix-map을 언매핑한 후 같은 영역에 대해 i-cache를 flush한다.

 

patch_map()

arch/arm/kernel/patch.c

static void __kprobes *patch_map(void *addr, int fixmap, unsigned long *flags)
        __acquires(&patch_lock)
{
        unsigned int uintaddr = (uintptr_t) addr;
        bool module = !core_kernel_text(uintaddr);
        struct page *page;

        if (module && IS_ENABLED(CONFIG_STRICT_MODULE_RWX))
                page = vmalloc_to_page(addr);
        else if (!module && IS_ENABLED(CONFIG_STRICT_KERNEL_RWX))
                page = virt_to_page(addr);
        else
                return addr;

        if (flags)
                spin_lock_irqsave(&patch_lock, *flags);
        else
                __acquire(&patch_lock);

        set_fixmap(fixmap, page_to_phys(page));

        return (void *) (__fix_to_virt(fixmap) + (uintaddr & ~PAGE_MASK));
}

Fixmap을 사용하여 해당 페이지를 매핑한다.

 

flush_kernel_vmap_range()

arch/arm/include/asm/cacheflush.h

static inline void flush_kernel_vmap_range(void *addr, int size)
{
        if ((cache_is_vivt() || cache_is_vipt_aliasing()))
          __cpuc_flush_dcache_area(addr, (size_t)size);
}

캐시가 vivt 또는 vipt aliasing인 경우 d-cache의 해당 영역을 flush 한다.

 

patch_unmap()

arch/arm/kernel/patch.c

static void __kprobes patch_unmap(int fixmap, unsigned long *flags)
        __releases(&patch_lock)
{
        clear_fixmap(fixmap);

        if (flags)
                spin_unlock_irqrestore(&patch_lock, *flags);
        else
                __release(&patch_lock);
}

매핑된 Fixmap 인덱스를 해지한다.

 

2) Jump 라벨 수정 for ARM64

arch_jump_label_transform() – ARM64

arch/arm64/kernel/jump_label.c

void arch_jump_label_transform(struct jump_entry *entry,
                               enum jump_label_type type)
{
        void *addr = (void *)jump_entry_code(entry);
        u32 insn;

        if (type == JUMP_LABEL_JMP) {
                insn = aarch64_insn_gen_branch_imm(jump_entry_code(entry),
                                                   jump_entry_target(entry),
                                                   AARCH64_INSN_BRANCH_NOLINK);
        } else {
                insn = aarch64_insn_gen_nop();
        }

        aarch64_insn_patch_text_nosync(addr, insn);
}

jump 엔트리의 타입에 따라 jmp 명령 또는 mop 명령을 기록한다.

  • branch 명령 코드를 만드는 aarch64_insn_gen_branch_imm() 함수와  nop  명령 코드를 만드는 aarch64_insn_gen_nop() 함수는 분석을 생략한다.

 

aarch64_insn_patch_text_nosync() – ARM64

arch/arm64/kernel/insn.c

int __kprobes aarch64_insn_patch_text_nosync(void *addr, u32 insn)
{
        u32 *tp = addr;
        int ret;

        /* A64 instructions must be word aligned */
        if ((uintptr_t)tp & 0x3)
                return -EINVAL;

        ret = aarch64_insn_write(tp, insn);
        if (ret == 0)
                __flush_icache_range((uintptr_t)tp,
                                     (uintptr_t)tp + AARCH64_INSN_SIZE);

        return ret;
}

물리 주소 @addr에 인스트럭션 @insn을 기록한 후 해당 주소의 명령 캐시를 flush 한다.

 

aarch64_insn_write()

int __kprobes aarch64_insn_write(void *addr, u32 insn)
{
        return __aarch64_insn_write(addr, cpu_to_le32(insn));
}

물리 주소 @addr에 인스트럭션 @insn을 기록한다.

 

__aarch64_insn_write()
static int __kprobes __aarch64_insn_write(void *addr, __le32 insn)
{
        void *waddr = addr;
        unsigned long flags = 0;
        int ret;

        raw_spin_lock_irqsave(&patch_lock, flags);
        waddr = patch_map(addr, FIX_TEXT_POKE0);

        ret = probe_kernel_write(waddr, &insn, AARCH64_INSN_SIZE);

        patch_unmap(FIX_TEXT_POKE0);
        raw_spin_unlock_irqrestore(&patch_lock, flags);

        return ret;
}

물리 주소 @addr에 인스트럭션 @insn을 기록한다.

  • 기록 전/후로 인터럽트의 접근을 금지하고 fixmap의 TEXT_POKE0 슬롯을 사용하여 매핑/해제한다.

 

patch_map() – ARM64

arch/arm64/kernel/insn.c

static void __kprobes *patch_map(void *addr, int fixmap)
{
        unsigned long uintaddr = (uintptr_t) addr;
        bool module = !core_kernel_text(uintaddr);
        struct page *page;

        if (module && IS_ENABLED(CONFIG_STRICT_MODULE_RWX))
                page = vmalloc_to_page(addr);
        else if (!module)
                page = phys_to_page(__pa_symbol(addr));
        else
                return addr;

        BUG_ON(!page);
        return (void *)set_fixmap_offset(fixmap, page_to_phys(page) +
                        (uintaddr & ~PAGE_MASK));
}

@fixmap 슬롯에 물리 주소 @addr을 매핑한다.

 

patch_unmap() – ARM64

arch/arm64/kernel/insn.c

static void __kprobes patch_unmap(int fixmap)
{
        clear_fixmap(fixmap);
}

@fixmap 슬롯에 매핑된 페이지를 매핑 해제한다.

 

probe_kernel_write()

mm/maccess.c

/**
 * probe_kernel_write(): safely attempt to write to a location
 * @dst: address to write to
 * @src: pointer to the data that shall be written
 * @size: size of the data chunk
 *
 * Safely write to address @dst from the buffer at @src.  If a kernel fault
 * happens, handle that and return -EFAULT.
 */
long __weak probe_kernel_write(void *dst, const void *src, size_t size)
    __attribute__((alias("__probe_kernel_write")));
long __probe_kernel_write(void *dst, const void *src, size_t size)
{
        long ret;
        mm_segment_t old_fs = get_fs();

        set_fs(KERNEL_DS);
        pagefault_disable();
        ret = __copy_to_user_inatomic((__force void __user *)dst, src, size);
        pagefault_enable();
        set_fs(old_fs);

        return ret ? -EFAULT : 0;
}
EXPORT_SYMBOL_GPL(probe_kernel_write);

 


구조체

static_key 구조체

include/linux/jump_label.h

struct static_key {
        atomic_t enabled;
/*
 * Note:
 *   To make anonymous unions work with old compilers, the static
 *   initialization of them requires brackets. This creates a dependency
 *   on the order of the struct with the initializers. If any fields
 *   are added, STATIC_KEY_INIT_TRUE and STATIC_KEY_INIT_FALSE may need
 *   to be modified.
 *
 * bit 0 => 1 if key is initially true
 *          0 if initially false
 * bit 1 => 1 if points to struct static_key_mod
 *          0 if points to struct jump_entry
 */
        union {
                unsigned long type;
                struct jump_entry *entries;
                struct static_key_mod *next;
        };
};

멤버들 중 enable를 제외한 나머지 3개의 멤버를 union 타입으로 묶어 사이즈를 줄였다.

  •  enabled
    • 런타임에 변경되는 값이지만, 초기 컴파일 타임에는 아래 entries의 bit1가 의미하는 jump 타입과 동일하게 사용된다.
    • static_key_slow_inc() 및 static_key_slow_dec() 함수에 의해 카운터 값이 런타임 중에 바뀐다.
    • 참고로 jump label 타입은 컴파일 타임과 런타임에서 다음과 같이 결정된다.
      • 컴파일 타임
        • type ^ branch
      • 런 타임
        • !!enabled ^ branch
  • type
    • lsb 2비트를 사용하여 타입을 결정한다.
      • JUMP_TYPE_FALSE(0)
      • JUMP_TYPE_TRUE(1)
      • JUMP_TYPE_LINKED(2)
  • *entries
    • key로 sort 된 첫 번째 jump 엔트리를 가리킨다.
    • jump 엔트리 포인터가 담기는데 하위 2비트에 static 키의 default 값이 설정되어 있다.
      • JUMP_TYPE_FALSE(0)과 JUMP_TYPE_TRUE(1)을 사용한다.
  • *next
    • static_key_mod 포인터가 담기는데 하위 2비트에 JUMP_TYPE_LINKED(2)가 추가되어 사용된다.

 

jump_entry 구조체 – ARM32

include/linux/jump_label.h

struct jump_entry {
        jump_label_t code;
        jump_label_t target;
        jump_label_t key;
};

아래 3개의 멤버들은 모두 주소를 담고 있는데, ARM32에서는 각각에 해당하는 절대 주소를 담고, ARM64에서는 각각에 해당하는 주소 – jump 라벨 엔트리가 저장되는 위치에 해당하는 주소를 뺀 상대 주소가 담긴다.

  •  code
    • static_branch_likely() 등의 static branch를 사용한 코드 주소
    • ARM64의 경우 32비트만을 사용하여 static_branch_*() 코드가 위치한 주소에서 이에 해당하여 저장될 jump 엔트리의 code 멤버의 주소를 뺀 상대주소가 담긴다.
  • target
    • 브랜치할 곳의 주소
    • ARM64의 경우 32비트만을 사용하여 브랜치 할 주소에서 저장될 jump 엔트리의 target 멤버의 주소를 뺀 상대주소가 담긴다.
  • key
    • static key 구조체를 가리키는 주소와 2 개의 플래그가 포함된다.
      • bit0에는 jump 엔트리의 branch 상태를 나타낸다. 1=jmp, 0=nop
      • bit1에는 코드가 init 섹션에 위치하였는지 여부를 나타낸다. 1=init 섹션에 위치, 0=그외 섹션 위치
        • init 섹션에 있는 코드들은 부트업 후에 모두 삭제되므로 런타임 시에는 이 위치의 jump 엔트리들을 수정할 필요 없다.
    • ARM64의 경우 64비트를 사용하여 선언된 static 키 주소에서 저장될 jump 엔트리의 key 멤버의 주소를 뺀 상대주소가 담긴다.

 

typedef u32 jump_label_t;

 

jump_entry 구조체 – ARM64

#ifdef CONFIG_HAVE_ARCH_JUMP_LABEL_RELATIVE
struct jump_entry {
        s32 code;
        s32 target;
        long key;       // key may be far away from the core kernel under KASLR
};

ARM64의 경우 사이즈를 줄이기 위해 CONFIG_HAVE_ARCH_JUMP_LABEL_RELATIVE 커널 옵션을 사용한다. 이 때에는 code와 target은 static 키를 기준으로 상대 주소를 사용한 4바이트를 사용하고, key 값만  8 바이트를 사용한다.

 

static_key_mod 구조체

kernel/jump_label.c

struct static_key_mod {
        struct static_key_mod *next;
        struct jump_entry *entries;
        struct module *mod;
};

모듈에서 커널이 선언한 글로벌 static 키를 사용할 때 사용된다. (참고로 모듈에서 선언된 로컬 static 키와는 관련 없다)

  • *next
    • 다음 글로벌 static key를 사용하는 모듈과 연결된다.
  • *entries
    • 모듈에서 사용하는 첫 jump 엔트리를 가리킨다.
    • 리스트의 마지막은 글로벌에서 사용하는 첫 jump 엔트리를 가리킨다.
  • *mod
    • 모듈을 가리킨다.

 

jump_label_type

include/linux/jump_label.h

enum jump_label_type { 
        JUMP_LABEL_NOP = 0,
        JUMP_LABEL_JMP,
};
  • JUMP_LABEL_NOP
    • NOP 코드로 jump_label 코드를 변경한다.
  • JUMP_LABEL_JMP
    • JMP 코드로 jump_label 코드를 변경한다.

 

참고

 

 

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다