<kernel v5.0>
Static Keys -2- (초기화)
커널과 모듈에서 조건문의 branch miss ratio를 낮추어 성능을 향상 시키기 위한 방법으로 static key를 사용한 jump label API를 사용하는데 커널에서 이러한 jump label 코드들을 모두 찾아 초기화한다.
static key를 초기화와 관련된 루틴은 다음과 같다.
- 커널 boot-up – jump_label_init() 함수
- 모듈 로딩 시 호출될 콜백 함수 등록 – jump_label_init_module()
- 각 모듈 로딩 시 호출 – jump_label_module_notify()
커널 부트 업 시 Static Key 초기화
jump_label_init()
kernel/jump_label.c
void __init jump_label_init(void)
{
struct jump_entry *iter_start = __start___jump_table;
struct jump_entry *iter_stop = __stop___jump_table;
struct static_key *key = NULL;
struct jump_entry *iter;
/*
* Since we are initializing the static_key.enabled field with
* with the 'raw' int values (to avoid pulling in atomic.h) in
* jump_label.h, let's make sure that is safe. There are only two
* cases to check since we initialize to 0 or 1.
*/
BUILD_BUG_ON((int)ATOMIC_INIT(0) != 0);
BUILD_BUG_ON((int)ATOMIC_INIT(1) != 1);
if (static_key_initialized)
return;
cpus_read_lock();
jump_label_lock();
jump_label_sort_entries(iter_start, iter_stop);
for (iter = iter_start; iter < iter_stop; iter++) {
struct static_key *iterk;
/* rewrite NOPs */
if (jump_label_type(iter) == JUMP_LABEL_NOP)
arch_jump_label_transform_static(iter, JUMP_LABEL_NOP);
if (init_section_contains((void *)jump_entry_code(iter), 1))
jump_entry_set_init(iter);
iterk = jump_entry_key(iter);
if (iterk == key)
continue;
key = iterk;
static_key_set_entries(key, iter);
}
static_key_initialized = true;
jump_label_unlock();
cpus_read_unlock();
}
jump 라벨의 사용을 위해 초기화를 수행한다. __jump_table에 있는 모든 jump 엔트리를 읽어와서 key로 소팅하고 jump 라벨 타입이 nop인 경우 해당 커널 코드(jump label 코드)의 1 word를 nop으로 rewrite 한다. 그리고 각 static 키들은 각 static 키를 사용하는 첫 jump 엔트리를 가리키게 한다.
- 코드 라인 17~18에서 static key의 초기화는 한 번만 수행하는 것으로 제한한다.
- 코드 라인 22에서 __jump_table에 있는 jump 엔트리를 key 주소로 heap sorting을 한다.
- 코드 라인 24~29에서 __jump_table을 순회하며 jump 라벨 엔트리의 타입이 nop인 경우 static key를 사용한 jump_label API 코드 주소에 nop 명령어를 rewrite 한다.
- ARM64의 경우는 컴파일 타임에 nop 명령을 사용하여 이미 초기화된 상태라 별도로 nop 코드를 rewrite 할 필요 없다.
- 코드 라인 31~32에서 jump 엔트리의 코드가 init 섹션안에 위치한 경우라면 key의 bit1을 설정하여 jump 엔트리가 init 섹션안에 위치함을 표시한다. 부트 업이 완료되면 init 섹션안의 코드는 모두 제거된다. 추후 런타임 중에 init 섹션안에 포함된 jump 엔트리들에 대해 업데이트하지 않게 하기 위함이다.
- 코드 라인 34~36에서 jump 라벨 엔트리들이 key 주소로 sorting 되어 있으므로 동일한 static key를 사용하는 jump 라벨 엔트리인 경우 skip 한다.
- 코드 라인 38~39에서 새로운 키를 사용하는 jump 엔트리인 경우이다. 이 경우 static 키에 첫 jump 엔트리를 대입한다. 대입할 때 기존 key 타입은 유지한다.
- 코드 라인 41에서 static key가 모두 초기화 되었음을 알리는 전역 플래그 변수이다.
아래 그림은 jump_label_init() 함수를 통해 동작되는 과정을 보여준다.
Jump 라벨 엔트리들 소팅
jump_label_sort_entries()
kernel/jump_label.c
static void
jump_label_sort_entries(struct jump_entry *start, struct jump_entry *stop)
{
unsigned long size;
void *swapfn = NULL;
if (IS_ENABLED(CONFIG_HAVE_ARCH_JUMP_LABEL_RELATIVE))
swapfn = jump_label_swap;
size = (((unsigned long)stop - (unsigned long)start)
/ sizeof(struct jump_entry));
sort(start, size, sizeof(struct jump_entry), jump_label_cmp, swapfn);
}
__jump_table의 entry를 key 주소로 heap sorting 알고리즘을 수행한다.
jump_label_cmp()
kernel/jump_label.c
static int jump_label_cmp(const void *a, const void *b)
{
const struct jump_entry *jea = a;
const struct jump_entry *jeb = b;
if (jump_entry_key(jea) < jump_entry_key(jeb))
return -1;
if (jump_entry_key(jea) > jump_entry_key(jeb))
return 1;
return 0;
}
두 jump 엔트리의 키를 비교하여 A가 작으면 -1, B가 크면 1, 동일하면 0을 반환한다.
jump_label_swap()
kernel/jump_label.c
static void jump_label_swap(void *a, void *b, int size)
{
long delta = (unsigned long)a - (unsigned long)b;
struct jump_entry *jea = a;
struct jump_entry *jeb = b;
struct jump_entry tmp = *jea;
jea->code = jeb->code - delta;
jea->target = jeb->target - delta;
jea->key = jeb->key - delta;
jeb->code = tmp.code + delta;
jeb->target = tmp.target + delta;
jeb->key = tmp.key + delta;
}
두 jump 엔트리를 swap 한다. ARM64의 경우 CONFIG_HAVE_ARCH_JUMP_LABEL_RELATIVE 커널 옵션을 사용한 상태이므로 두 jump 엔트리 간의 차이 값인 delta가 두 jump 엔트리의 멤버들에 모두 적용된다.
jump_label_type()
kernel/jump_label.c
static enum jump_label_type jump_label_type(struct jump_entry *entry)
{
struct static_key *key = jump_entry_key(entry);
bool enabled = static_key_enabled(key);
bool branch = jump_entry_is_branch(entry);
/* See the comment in linux/jump_label.h */
return enabled ^ branch;
}
jump 엔트리에서 jump label 타입을 알아온다. 이 타입은 코드에 기록할 타입에 사용한다. (0=JUMP_LABEL_NOP, 1=JUMP_LABEL_JMP)
- 코드 라인 3에서 jump 엔트리가 가리키는 static 키를 알아온다.
- 코드 라인 4에서 static 키의 enable 여부를 알아온다.
- 코드 라인 5에서 jump 엔트리의 nop/branch 여부를 알아온다.
- 코드 라인 8에서 최종 코드에 적용할 nop/branch 타입을 알아온다.
아래 그림은 2가지 상태(초기 설정 상태와 enable 상태)에 따라 nop(JUMP_LABEL_DISABLE)과 branch(JUMP_LABEL_ENABLE) 동작 상태를 기존 API를 사용하여 보여준다.
- STATIC_KEY_INIT_FALSE 또는 STATIC_KEY_INIT_TRUE로 초기화된 경우는 처음에 항상 nop를 수행하고 static_key_slow_inc() 또는 static_key_slow_dec() 함수에 의해 branch code가 동작하게된다.
아래 그림은 3가지 상태(초기 설정 상태, enable 상태 및 조건 API)에 따라 nop(JUMP_LABEL_DISABLE)과 branch(JUMP_LABEL_ENABLE) 동작 상태를 신규 API를 사용하여 보여준다.
- DEFINE_STATIC_KEY_FALSE 또는 DEFINE_STATIC_KEY_TRUE로 초기화된 경우는 static_branch_unlikely() 및 static_branch_likely() 함수와 enable 상태의 조합에 따라 초기 값으로 nop/branch가 결정되고 이후 static_branch_enable() 및 static_branch_disable() API에 의해 조건이 반전된다.
jump_label_init_type()
kernel/jump_label.c
static enum jump_label_type jump_label_init_type(struct jump_entry *entry)
{
struct static_key *key = jump_entry_key(entry);
bool type = static_key_type(key);
bool branch = jump_entry_is_branch(entry);
/* See the comment in linux/jump_label.h */
return type ^ branch;
}
jump 엔트리에서 초기 jump label 타입을 알아온다. (0=JUMP_LABEL_NOP, 1=JUMP_LABEL_JMP)
- 코드 라인 3에서 jump 엔트리가 가리키는 static 키를 알아온다.
- 코드 라인 4에서 static 키의 타입(true/false)을 알아온다.
- 코드 라인 5에서 jump 엔트리의 nop/branch 여부를 알아온다.
- 코드 라인 8에서 초기 코드에 적용된 nop/branch 타입을 산출해 반환한다.
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 key가 enable 되었는지 여부를 리턴한다.
static_key_count()
include/linux/jump_label.h
static inline int static_key_count(struct static_key *key)
{
return atomic_read(&key->enabled);
}
key->enabled 값을 atomic하게 읽어온다.
모듈에서 사용된 static key를 사용한 jump label API
다음 그림은 모듈용 jump 라벨 초기화 루틴에서 notifier 블럭을 등록하는 과정을 보여준다.
초기화 함수 등록
kernel/jump_label.c
early_initcall(jump_label_init_module);
.initcall 섹션에 jump_label_init_module() 함수를 등록한다.
- 등록되는 모든 initcall 함수들은 kernel_init 스레드의 do_initcalls() 함수에서 호출된다.
early_initcall()
include/linux/init.h
/* * Early initcalls run before initializing SMP. * * Only for built-in code, not modules. */ #define early_initcall(fn) __define_initcall(fn, early)
__define_initcall()
include/linux/init.h
/* initcalls are now grouped by functionality into separate
* subsections. Ordering inside the subsections is determined
* by link order.
* For backwards compatibility, initcall() puts the call in
* the device init subsection.
*
* The `id' arg to __define_initcall() is needed so that multiple initcalls
* can point at the same handler without causing duplicate-symbol build errors.
*/
#define __define_initcall(fn, id) \
static initcall_t __initcall_##fn##id __used \
__attribute__((__section__(".initcall" #id ".init"))) = fn; \
LTO_REFERENCE_INITCALL(__initcall_##fn##id)
initcall 함수를 .initcallearly.init 섹션에 등록한다.
- 예) __initcall_jump_label_init_moduleearly = jump_label_init_module;
모듈 로드/언로드
jump_label_init_module()
kernel/jump_label.c
static __init int jump_label_init_module(void)
{
return register_module_notifier(&jump_label_module_nb);
}
jump_label_module_nb 구조체를 module notifier 블록에 등록한다.
jump_label_module_nb 구조체
kernel/jump_label.c
struct notifier_block jump_label_module_nb = {
.notifier_call = jump_label_module_notify,
.priority = 1, /* higher than tracepoints */
};
- jump_label_module_notify 함수가 등록된다.
- notifier block이 ascending으로 정렬되어 있고 priority는 1의 값이다.
모듈 로딩/언로딩 시 jump 라벨 함수 호출
다음 그림은 모듈이 로딩/언로딩될 때마다 등록된 notifier 블럭에 의해 호출되는 jump_label_module_notify() 함수를 보여준다.
jump_label_module_notify()
kernel/jump_label.c
static int
jump_label_module_notify(struct notifier_block *self, unsigned long val,
void *data)
{
struct module *mod = data;
int ret = 0;
cpus_read_lock();
jump_label_lock();
switch (val) {
case MODULE_STATE_COMING:
ret = jump_label_add_module(mod);
if (ret) {
WARN(1, "Failed to allocate memory: jump_label may not work properly.\n");
jump_label_del_module(mod);
}
break;
case MODULE_STATE_GOING:
jump_label_del_module(mod);
break;
}
jump_label_unlock();
cpus_read_unlock();
return notifier_from_errno(ret);
}
개개 모듈이 로드/언로드/초기화 되었을 때 각각 호출되며 3가지 메시지에 대해 아래의 메시지에 대해 구분하여 처리된다.
- MODULE_STATE_COMING
- 모듈이 로드 되었을 때 호출되는 이벤트로 static key에 static_key_module 객체를 할당하여 연결한다.
- load_module() 함수에서 notifier_call_chain()을 호출한다.
- MODULE_STATE_GOING
- 모듈이 언로드 되었을 때 호출되는 이벤트로 static key에 연결된 static_key_module 객체들 중 해당 모듈이 있는 객체를 찾아 삭제한다.
- delete_module() 함수에서 notifier_call_chain()을 호출한다.
모듈 로딩 시 jump 라벨 초기화
jump_label_add_module()
kernel/jump_label.c
static int jump_label_add_module(struct module *mod)
{
struct jump_entry *iter_start = mod->jump_entries;
struct jump_entry *iter_stop = iter_start + mod->num_jump_entries;
struct jump_entry *iter;
struct static_key *key = NULL;
struct static_key_mod *jlm, *jlm2;
/* if the module doesn't have jump label entries, just return */
if (iter_start == iter_stop)
return 0;
jump_label_sort_entries(iter_start, iter_stop);
for (iter = iter_start; iter < iter_stop; iter++) {
struct static_key *iterk;
if (within_module_init(jump_entry_code(iter), mod))
jump_entry_set_init(iter);
iterk = jump_entry_key(iter);
if (iterk == key)
continue;
key = iterk;
if (within_module((unsigned long)key, mod)) {
static_key_set_entries(key, iter);
continue;
}
jlm = kzalloc(sizeof(struct static_key_mod), GFP_KERNEL);
if (!jlm)
return -ENOMEM;
if (!static_key_linked(key)) {
jlm2 = kzalloc(sizeof(struct static_key_mod),
GFP_KERNEL);
if (!jlm2) {
kfree(jlm);
return -ENOMEM;
}
preempt_disable();
jlm2->mod = __module_address((unsigned long)key);
preempt_enable();
jlm2->entries = static_key_entries(key);
jlm2->next = NULL;
static_key_set_mod(key, jlm2);
static_key_set_linked(key);
}
jlm->mod = mod;
jlm->entries = iter;
jlm->next = static_key_mod(key);
static_key_set_mod(key, jlm);
static_key_set_linked(key);
/* Only update if we've changed from our initial state */
if (jump_label_type(iter) != jump_label_init_type(iter))
__jump_label_update(key, iter, iter_stop, true);
}
return 0;
}
모듈에서 사용하는 jump label 엔트리를 정렬(heap sort) 한다. 그리고 static 키가 해당 모듈에 이미 포함되어 있는 경우 key->entries가 해당 엔트리를 가리키게 하고, 그렇지 않은 경우 글로벌 static 키가 커널에 존재하므로 static_key_mod 객체를 할당하고 이를 key에 연결한다. 그런 후 타입이 enable인 경우 동일한 키를 사용하는 모든 엔트리가 가리키는 code 주소의 명령을 update 한다.
- 코드 라인 10~11에서 jump 라벨을 사용하지 않은 모듈인 경우 그냥 함수를 빠져나간다.
- 코드 라인 13에서 모듈에 존재하는 jump label 엔트리를 정렬(heap sort)한다.
- 코드 라인 15~19에서 모듈에 있는 jump label 엔트리를 순회하며 jump 라벨이 모듈의 init 섹션에서 사용된 경우 이를 식별하기 위해 key의 bit1을 설정한다.
- 코드 라인 21~23에서 이미 처리한 static 키와 연결된 jump 라벨 엔트리는 skip 한다.
- 코드 라인 25~29에서 소팅된 jump 라벨 엔트리들 중 static 키와 연결된 첫 jump 라벨 엔트리이다. 여기서 static 키가 모듈에서 정의된 경우 해당 static 키를 첫 jump 라벨 엔트리에 연결한다.
- 코드 라인 30~32에서 jump 라벨이 모듈 외부의 커널에서 정의된 static를 사용하는 경우이다. 이 모듈을 커널의 static 키에 연결하기 위해 static_key_mod 구조체를 할당받는다.
- 코드 라인 33~47에서 커널의 static 키가 한 번도 모듈과 링크를 한 적이 없으면 static_key_mod 구조체를 추가로 하나 더 만들고 이를 먼저 연결한다.
- 코드 라인 48~52에서 static_key_mod 구조체의 내용을 채운 후 커널의 글로벌 static 키가 사용하는 static_key_mod에 연결한다.
- 코드 라인 55~56에서 jump 라벨의 초기값과 jump 라벨 타입이 다른 경우에 한해 이에 해당하는 jump 라벨들이 가리키는 코드들을 모두 update 한다.
다음 그림은 module-B가 로드되어 static key를 사용한 jump 라벨들이 초기화되는 과정을 보여준다.
- static_key_mod 객체가 추가되고 추가된 모듈은 module을 가리키고 entries 멤버는 해당 모듈의 해당 static 키를 사용한 첫 jump 라벨 엔트리를 가리킨다.
- 모듈 내부의 각 static key는 해당 static 키를 사용하는 첫 jump 라벨 엔트리를 가리킨다.
모듈 언로딩 시 jump 라벨 정리
jump_label_del_module()
kernel/jump_label.c
static void jump_label_del_module(struct module *mod)
{
struct jump_entry *iter_start = mod->jump_entries;
struct jump_entry *iter_stop = iter_start + mod->num_jump_entries;
struct jump_entry *iter;
struct static_key *key = NULL;
struct static_key_mod *jlm, **prev;
for (iter = iter_start; iter < iter_stop; iter++) {
if (jump_entry_key(iter) == key)
continue;
key = jump_entry_key(iter);
if (within_module((unsigned long)key, mod))
continue;
/* No memory during module load */
if (WARN_ON(!static_key_linked(key)))
continue;
prev = &key->next;
jlm = static_key_mod(key);
while (jlm && jlm->mod != mod) {
prev = &jlm->next;
jlm = jlm->next;
}
/* No memory during module load */
if (WARN_ON(!jlm))
continue;
if (prev == &key->next)
static_key_set_mod(key, jlm->next);
else
*prev = jlm->next;
kfree(jlm);
jlm = static_key_mod(key);
/* if only one etry is left, fold it back into the static_key */
if (jlm->next == NULL) {
static_key_set_entries(key, jlm->entries);
static_key_clear_linked(key);
kfree(jlm);
}
}
}
모듈에서 사용한 외부 글로벌 static key를 찾고 여기에 연결된 static_key_mod 객체를 찾아 연결을 끊고 메모리를 해지한다.
- 코드 라인 9~11에서 모듈에 있는 key 값으로 소팅된 jump label 엔트리 수 만큼 순회하며 동일한 static 키를 사용하는 jump 라벨 엔트리는 처리하지 않기 위해 skip 한다.
- 코드 라인 13~16에서 jump 라벨 엔트리가 모듈내에 정의된 static 키를 사용하는 경우 skip 한다.
- 코드 라인 19~20에서 글로벌 static 키가 링크된 적이 없으면 경고 메시지를 출력하고 skip 한다.
- 코드 라인 22~32에서 언로드될 모듈에 연결될 static_key_mod 구조체를 순차 검색한다.
- 코드 라인 34~39에서 해당 static_key_mod 구조체의 연결을 끊고 메모리를 해제한다.
- 코드 라인 41~47에서 만일 static 키에 연결된 static_key_mod 객체가 하나만 남은 경우 마저 제거하고 할당 해제한다. 이 때 마지막 객체에 연결된 글로벌 jump 라벨 엔트리는 static 키에 다시 연결한다. 연결 시 link 플래그는 제거한다.
다음 그림은 module-B가 언로드될 때 static 키 모듈 연결 정보인 static_key_mod 객체를 소멸시키는 과정을 보여준다.
참고
- Static Keys -1- (Core API) | 문c
- Static Keys -2- (초기화) | 문c – 현재 글
- Static Keys | kernel.org
- jump label: introduce static_branch() interface | LWN.net
- locking/static_keys: Add a new static_key interface