Wonhyuk Yang

2021년 12월 18일8분 분량

Stack trace와 kallsyms의 구현 살펴보기

OS 개발 시 가장 힘든 부분은 역시 디버깅을 하는 것인데요. 이를 위해 앞에 글에서는 gdb+qemu와 같은 방법을 살펴봤습니다. 하지만 이 방법은 원인 분석하기엔 유용하지만, 문제가 발생한 위치를 쉽게 찾지는 못합니다. Linux에서는 문제가 발생할 경우 위와 같이 Oops나 panic을 통해 여러 정보들을 출력합니다.

위의 panic 로그는 어떤 위치에서 panic이 발생했는지와 각종 레지스터들의 상태와 call trace 같은 정보들은 제공합니다. 이런 정보들은 이용하면 맨 땅에서 디버깅할 때보다 수월하게 디버깅을 할 수 있습니다. 그렇다면 위와 같은 call trace를 출력하는 것은 어떻게 구현할까요?

이것을 구현하기 위해서는 우선 stack frame 개념에 대해 알아야 합니다. 이 주제는 다룬 글들이 많기에 간단하게 설명하도록 하겠습니다.

Stack Frame

ARM 64의 스택 프레임은 아래의 그림과 같습니다. frame pointer 레지스터는 스택에 있는 이전의 frame pointer의 주소를 저장합니다. 또한 마지막 프레임은 다음 프레임이 없으므로 0을 저장합니다. 따라서 frame pointer은 linked list와 같은 특성을 가지고 있습니다. 또한 stack의 frame pointer 앞에는 LR 레지스터의 값(리턴시 점프할 주소)도 같이 저장됩니다.

위와 같은 특성을 이용하면, stack frame을 순회하면서 frame pointer와 LR의 값들을 확인할 수 있습니다. 아래는 이 특성을 이용하여 구현한 단순한 버전의 dump_stack 함수입니다.

한 가지 독특한 점은 현재 함수의 스택 프레임을 가져오기 위해 gcc의 __builtin_frame_address를 사용한 것입니다. inline assembly를 통해 직접 fp(x29) 레지스터를 읽어올 수도 있지만, 조금 더 범용적인 __builtin_frame_address를 사용하였습니다.

따라서, x86 아키텍처에서도 위 코드는 동작합니다. 이 밖에 아키텍처는 각 ABI에 맞춰 수정해야할 수 있습니다.

해당 코드를 ARM64에서 실행하면 아래와 같은 결과를 얻을 수 있습니다. frame pointer가 0에 도달할 때까지 stack frame을 순회한 것을 확인할 수 있습니다.

하지만 주소만 보여주는 것만으로는 여전히 불편합니다. 파악하기 쉽게하기 위해서는 주소에 대응하는 함수 이름도 같이 출력을 해줘야 합니다. 어떻게 주소에 대응하는 심볼을 가지고 올 수 있을까요? 한 번 리눅스에서는 어떻게 심볼을 가져오는지 살펴보도록 하겠습니다.

KALLSYMS

커널의 심볼 정보들을 담당하는 것은 kallsym입니다. kernel exploit에 관심이 있으신 분이라면 한 번쯤 들어 보셨을 것 같습니다. /proc/kallsyms 파일을 열면 현재 커널의 여러 심볼 정보들을 살펴볼 수 있습니다. 이렇게 심볼 정보를 제공하는 kallsyms의 구현은 꽤나 재밌는 방식으로 구현되어 있습니다. 관련된 파일들은 아래와 같이 3개가 있습니다.

/kernel/kallsyms.c
/scripts/kallsyms.c
/scripts/link-vmlinux.sh

우선 전체적인 구조를 이해하기 위해서 /scripts/kallsyms.c를 먼저 살펴보도록 하겠습니다.

해당 스크립트는 주석에 사용법(usage)에 나와 있듯이 별도로 컴파일 되어 실행 가능한 파일입니다. 입력으로는 nm 유틸리티의 stdout을 사용합니다. nm은 오브젝트 파일의 심볼을 읽는 유틸리티입니다. 따라서 kallsyms는 읽어 들인 vmlinux의 심볼 정보들을 파싱합니다.

아래의 주석에 따르면, 해당 스크립트는 압축 알고리즘을 이용하여 50%의 압축률을 보인다고 합니다. 압축 알고리즘은 차차 살펴보도록 하고 우선 핵심 자료 구조부터 알아보겠습니다. 주요 자료 구조는 총 4개가 존재합니다.

sym_entry: 하나의 심볼에 대응하는 자료 구조입니다. 심볼의 주소(addr), 이름(sym[])을 저장합니다.
addr_range: 어떤 영역에 대응하는 자료 구조 입니다. 영역의 시작과 끝에 대응하는 심볼과 주소를 저정합니다.
token_profit: 2개의 문자로 이루어진 문자열의 빈도 수를 기록하는 테이블입니다. 2개의 문자가 가질 수 있는 조합 수는 0x10000(=256x256) 이므로 테이블의 길이는 0x10000 입니다.
best_table: 압축에 사용되는 매핑 테이블입니다. 각각의 char이 매핑되는 문자열을 저장합니다.(구체적인 내용은 압축 알고리즘에서 보겠습니다)

addr_range는 아래와 같이 총 3개의 영역(text, init text, percpu)을 미리 정의해두었습니다. 각 영역의 시작과 끝에 대응하는 심볼은 알지만 그 주소는 아직 모르기 때문에 아래와 같이 초기화 합니다.

이제 전체 과정을 살펴보도록 하겠습니다. 전체 과정은 총 5개의 단계로 구성되어 있고 각 단계는 main 함수에서 호출하는 함수와 대응합니다.

당장은 --absolute-percpu와 --base-relative와 같은 플래그는 고려하지 않겠습니다.

Line 3~15에서는 "--all-symbols", "--absolute-percpu", "--base-relative"와 같은 argument들을 처리합니다. 단순히 플래그를 올리는 것으로 해당 인자가 들어왔음을 알립니다. 그런 다음에는 앞서 언급한 5단계를 진행합니다. 이제 각각의 단계에 대해 알아보도록 하겠습니다.

read_map

read_map 함수는 하나의 symbol을 파싱하는 read_symbol 함수를 통해 입력을 파싱하고 파싱한 정보를 테이블에 추가합니다.

위의 구현에서 볼 수 있듯이, Line 5~6에서 EOF에 도달할 때까지 계속해서 read_symbol을 호출합니다. read_symbol에서는 표준 입출력을 통해 symobl 정보를 파싱합니다. 파싱한 데이터는 symbol_entry의 형태로 반환되고, 테이블에 추가됩니다.

입력을 파싱하는 중요 함수는 read_symbol입니다. 해당 함수는 3가지의 일을 진행합니다.

입력에서 심볼의 주소(addr), 타입(type), 심볼의 이름(name)을 받아옵니다.
받아온 정보들을 이용해 symbol_entry를 생성 및 초기화합니다.
또한 읽어온 심볼이 addr_range에 시작과 끝에 해당하는 심볼이라면, 이 심볼의 주소를 addr_range에 저장합니다.

Line 9: 표준 입출력을 통해 addr, type, name을 받아옵니다.
Line 20~21: 전역으로 생성한 percpu addr_range와 text addr_range의 시작과 끝에 해당하는 심볼인지 확인 후 맞다면 주소를 addr_range에 저장합니다.
Line 26~28: sym_entry, type, name을 저장할 수 있도록 동적 할당을 받습니다. sym_entry.sym[0]에 type을 저장하기에 문자열의 크기보다 1 더 큰 사이즈를 요청합니다.
Line 34~38: 생성한 sym_entry에 addr, len, type, name을 저장합니다. percpu_absolute는 0으로 초기화합니다.

shrink_table

shrink_table에서는 invalid symbol들을 삭제합니다. 테이블을 순회하면서 invalid한 심볼들은 free하며, valid한 symbol_entry만 남기도록 합니다.

sort_symbol

sort_symbol에서는 symbol_entry 테이블을 정렬합니다. qsort를 이용하며 compare_symbols 함수를 통해 symbol_entry를 비교합니다. 비교 함수 compare_symbols는 단계적으로 symbol_entry를 비교합니다. 비교 기준은 우선 주소를 기준으로 비교하고 동일하다면 다른 것들을 이용하여 우선 순위를 정합니다.

optimize_table

압축을 담당하는 optimize_table 함수는 아래와 같이 총 3개의 단계로 구성되어 있습니다. 각각의 단계에서는 token_profit 테이블 구성, symbol들이 사용하는 문자들을 조사, 사용되지 않은 문자를 빈번하게 사용되는 문자열(char[2])과 매핑합니다.

build_initial_tok_table은 구성한 symbol_entry 테이블을 순회하면서 learn_symbol 함수를 호출합니다. learn_symbol 함수는 symbol_entry의 sym(type+name)과 len을 인자로 받습니다. learn_symbol은 받은 문자열 symobl_entry.sym을 순회하면서, char[2]의 분포를 token_profit 테이블에 반영합니다.

insert_real_symbols_in_table은 symbol_entry 테이블을 순회하면서 sym에 사용되는 char을 기록합니다. 1번이라도 사용된 char은 best_table에 기록되고, 사용되지 않은 char은 기록되지 않습니다.

optimize_result는 best_table을 순회하면서 사용되지 않은 char을 찾고, 이 char을 빈번하게 사용된 char[2]와 매핑합니다. 빈번하게 char[2]는 앞서 구성한 token_profit에서 가장 큰 값을 가진 것에 해당합니다. 그런 다음 symbol_entry에 사용된 문자열을 매핑한 문자로 치환하는 작업을 합니다.

find_best_token은 구성한 token_profit에서 가장 높은 값을 가지는 인덱스를 리턴합니다. 여기서 인덱스는 int이지만 실제 의미는 char[2]입니다.

compress_symbols 함수는 첫 번째 인자는 압축할 char[2]이고, 두 번째 인자는 매핑 된 1byte 정수입니다. symbol_entry 테이블을 순회하면서 각 symbol_entry.sym에 압축 대상의 문자열이 존재하는지 확인합니다. 만약 그렇다면, 해당 문자열을 idx로 치환합니다. 압축한 symbol_entry.sym을 반영하기 위해 이전의 내용을 지우기 위해 forget_symbol을 사용하고 압축이 완료된 후에는 다시 learn_symbols를 호출하여, token_profit을 최신으로 업데이트합니다.

write_src

write_src에서는 assembly 파일 포맷에 맞춰 필요한 정보들을 출력합니다.

우선 Archtiecture(64bit or 32bit)에 따라 매크로(PTR, ALGN)를 정의합니다. 심볼 관련 정보들은 .rodata 섹션에 배치됩니다.

그런 다음 symbol_entry를 순회하면서 각각의 address를 출력합니다. 출력의 형식은 옵션에 따라 다르게 출력합니다. 그런 다음 symbol_entry의 갯수도 kallsyms_num_syms라는 이름으로 출력합니다.

설명의 편의를 위하여 아래의 코드는 여러 옵션들의 처리를 생략하였습니다.

그런 다음, symbol_entry의 sym을 출력합니다. symbol_entry.sym은 가변 길이이므로 검색의 용이성을 위해 marker라는 검색 인덱스를 만듭니다. marker는 256개의 symbol_entry.sym마다 오프셋을 저장합니다.

이제 마지막으로 char 마다 대응하는 문자열 또는 char을 출력하는 단계입니다. 어떤 char은 재압축이 되었을 수도 있으므로 expand_symbol을 통해 압축을 해제한 문자열을 buf에 저장합니다. 즉, 아래의 예의 경우 'a'는 "de"와 매핑 되어 있고 'd', 'e'는 "fg", "hi"와 매핑 되어 있습니다. 이러한 재압축을 재귀적으로 풀어나가 최종적으로 매핑 되는 token "fghi"를 버퍼에 담고 출력합니다.

아래의 코드에서는 앞서 언급한 대로, 0x00에서 0xFF까지 순회하면서 매핑 된 문자 또는 문자열을 출력을 합니다. 이렇게 출력된 정보들은 kallsyms_token_table이라는 곳에서 찾을 수 있습니다.

expand_symbol은 재귀적으로 호출되어 재압축을 처리합니다. 이 재귀 함수의 탈출 조건은 매핑 된 문자가 자기 자신일 때 입니다. 일종의 tree traversal 하면서 압축 해제된 token을 얻습니다.

정리하면, write_src는 다음과 같은 여러 정보들을 출력합니다.

kallsyms_address: 심볼들의 주소
kallsyms_num_syms: symbol의 갯수
kallsyms_names: symbol들의 압축된 이름
kallsyms_marker: kallsyms_names의 검색 인덱스
kallsyms_token_table: 압축된 문자(char)가 매핑 된 문자 또는 문자열

생성된 kallsyms_token_table을 살펴보면 아래와 같습니다. 가장 첫 문자(0x00)은 "output_"라는 문자열과 매핑되어 있는 것을 확인할 수 있습니다.

/scripts/link-vmlinux.sh

그렇다면 앞서 본 /script/kallsym 유틸리티가 언제 어떻게 사용되는지 살펴봐야 합니다. Linux의 빌드를 담당하는 파일은

Makefile 입니다. Makefile에서 vmlinux의 레시피는 아래와 같습니다.

vmlinux를 생성하기 위해서는 결국 script/link-vmlinux.sh이 실행됩니다.

+(call if_changed_dep,link-vmlinux)는 복잡한 커맨드로 치환되어 실행됩니다. 정확히 어떤 방식으로 이렇게 변환되는지는 잘 모르겠습니다. 잘 아시는 분은 알려주시면 감사하겠습니다.

실행되는 link-vmlinux.sh에서는 CONFIG_KALLSYMS 옵션이 활성화 되어 있다면, kallsyms 관련 일을 수행합니다. kallsyms을 구성하기 위해 사용되는 핵심 함수들은 vmlinux_link와 kallsyms입니다.

vmlinux_link: 첫 번째 인자로 받는 오브젝트 파일과 vmlinux.o를 링크하여 두 번째 인자로 받은 이름으로 출력 파일을 저장합니다.
kallsyms: 첫 번째 인자로 받은 오프젝트 파일의 심볼 정보를 추출하고 어셈블리 파일으로 저장합니다. 이때 저장하는 파일의 이름은 함수의 2번째 인자와 같습니다.

아래는 kallsyms 함수의 구현입니다. 핵심적인 부분은 Line 23~24이므로 이 부분만 살펴보도록 하겠습니다.

Line 23: ${NM}에서는 nm 유틸리티의 경로를 저장합니다. 따라서 단순히 nm -n ${1}으로 보아도 무방합니다. 해당 유틸리티의 입력으로 첫 번째 인자가 사용됩니다. 출력은 scripts/kallsys로 리다이렉션("|")되고 출력은 두 번째 인자를 이름으로 사용하여 어셈블리 파일(.S)의 형태로 저장됩니다.

Line 24: 생성한 어셈블리 파일을 컴파일하고 출력 파일은 두 번째 이름으로 저장합니다.

이제 스크립트를 살펴보며 전체적인 과정을 살펴보겠습니다.

아래에 첨부한 link-vmlinux.sh은 v5.1 버전입니다. 유의하세요!

우선 두 개의 변수가 사용됩니다. 해당 변수의 의미는 각각 다음과 같습니다.

kallsymso: /script/kallsyms을 통해 생성한 최종 오브젝트 파일 이름
kallsyms_vmlinux:: /script/kallsyms에 입력으로 넘겨준 최종 오브젝트 파일의 이름

위 두 변수의 세팅을 완료완 후, step 1와 step 2를 진행합니다. 각각의 과정 vmlinux_link와 kallsyms 두 함수로 구성되어 있습니다.

step 1: vmlinux.o를 링크하여 tmp_vmlinux1이라는 임시 오브젝트 파일을 생성합니다. 이 임시 오브젝트 파일은 kallsyms의 입력 파일로 제공되며, .tmp_kallsyms1.o라는 중간 산출물 오브젝트 파일을 생성합니다. 해당 중간 산출물 파일은 다른 심볼 정보들을 포함하고 있으나, 정작 그 자신에 대한 심볼 정보(kallsyms_token_table, ..)들을 포함하지 않습니다.
step 2: 앞서 생성한 .tmp_kallsyms1.o와 vmlinux.o를 링크하여 .tmp_vmlinux2라는 오브젝트 파일을 생성합니다. 해당 오브젝트는 이전 .tmp_vmlinux1와 다르게 kallsyms 관련 심볼들에 대한 올바른 정보를 포함하고 있습니다. 이렇게 생성한 오브젝트 파일을 /script/kallsyms의 입력으로 주어 최종적인 심볼 관련 오브젝트 파일 .tmp_kallsyms2.o를 생성합니다.

다만, 위의 과정은 한 가지 전제를 두고 있습니다. 바로 .tmp_kallsyms1.o와 .tmp_kallsyms2.o의 크기가 동일하다는 것 입니다. 만약 두 파일의 크기가 달라진다면 생성한 심볼 관련 정보들이 유효하지 않기 때문입니다. 따라서 크기가 다르다면 한 단계를 추가적으로 수행합니다. 이 내용이 step 3과 뒤에 나오는 if 문에서 처리하는 내용입니다.

최종적으로 Line 30에서 vmlinux.o와 생성한 최종 오브젝트를 링크하여 우리에게 친숙한 vmlinux 파일을 생성합니다.

kernel/kallsyms.c

이제 kallsyms의 마지막 구성 요소인 kernel/kallsyms.c를 살펴보도록 하겠습니다. 해당 파일에서는 생성한 여러 심볼 정보를 사용하는 여러 api를 제공합니다. 모든 내용을 살펴보지는 않을 것이고, 주소에 대응하는 심볼을 찾은 함수 위주로 간략하게 살펴보도록 하겠습니다.

printk의 documentation을 살펴보면 포인터에 관련된 여러 확장이 있습니다.

이러한 확장을 구현하기 위해서 내부적으로는 kallsyms에서 제공하는 함수들을 사용합니다. 사용되는 함수들은 대표적으로 다음과 같습니다.

이 함수들은 아래와 같이 공통적으로, __sprint_symbol 함수를 호출합니다 다만, 전달하는 인자가 조금씩 다를 뿐입니다. 전달하는 인자(옵션)에 따라 버퍼에 추가적인 정보 표시할 지 설정할 수 있습니다.

따라서, __sprint_symbol을 살펴보도록 하겠습니다. 이 함수는 두 가지의 파트로 구성되어 있습니다.

kallsyms_lookup_buildid를 통해 필요한 정보(ex 함수 이름 문자열 등등...)들을 가져옵니다.
가져온 정보들을 옵션에 따라 버퍼에 복사합니다.

구체적으로 kallsyms_lookup_buildid는 하나의 입력 address를 받고, 다음과 같은 정보들을 출력합니다.

주소에 대응하는 함수의 이름(문자열)
주소에 대응하는 함수의 크기
주소에 대응하는 함수에서의 오프셋
주소에 대응하는 모듈 이름
주소에 대응하는 빌드 아이디

이렇게 가져온 정보들을 옵션에 따라 입맛대로 버퍼에 복사합니다. 이제 코드를 살펴보도록 하겠습니다.

Line 12에서 주소에 대응하는 다양한 정보들을 받아옵니다.
Line 17에서 주소에 대응하는 이름을 버퍼에 복사합니다.
Line 23에서는 offset, size 정보를 버퍼에 추가합니다.

앞으로 모듈 관련 정보들을 처리하는 내용은 생략하도록 하겠습니다.

이제 주소에 대응하는 정보를 조회하는 함수 kallsyms_lookup_buildid를 살펴보도록 하겠습니다. 해당 함수를 이해하기 위해선 앞서 생성한 심볼 관련 정보의 구성을 상기할 필요가 있습니다. 만약 잘 기억이 나지 않는다면 /scripts/kallsyms.c의 write_src를 다시 보면 도움이 될 것 입니다.

우리는 kallsyms_address라는 심볼들의 주소를 저장하는 테이블을 구성하였습니다. 따라서 조사하는 주소가 몇 번째 심볼에 대응하는지 찾아야 합니다. 즉, kallsyms_address에서의 인덱스를 구해야 한다는 것입니다. 이 역할을 수행하는 함수가 get_symbol_pos 함수입니다.

다음으로, 구한 pos에 위치한 압축된 문자열을 압축 해제하는 함수가 kallsyms_expand_symbol 함수입니다. 만약 조사하는 주소가 모듈, bpf, ftrace에 속한다면 별도의 처리를 수행합니다. 전체적인 윤곽은 앞서 설명한 바와 같고 같이 코드를 살펴도록 하겠습니다.

Line 11: 입력으로 받은 주소가 커널 영역인지 확인합니다. 아니라면 별도의 처리 루틴으로 빠집니다.
Line 14: get_symbol_pos 함수를 통해 주소에 대응하는 심볼의 인덱스를 리턴합니다. 또한 해당 함수의 오프셋과 사이즈도 가져옵니다.
Line 16: 구한 인덱스를 가지고 kallsyms_name에 위치한 압축된 문자열을 구합니다. 그런 다음 문자열을 압축해제합니다.
Line 23: 압축 해제한 문자열의 주소를 반환될 변수에 저장합니다.

주소에 대응하는 인덱스를 구하는 get_symbol_pos 함수는 이진 탐색으로 구현되었습니다.

앞서 심볼들의 주소를 저장할 때 정렬을 했기 때문에 이진 탐색이 가능합니다.

다만, 몇몇 심볼들은 동일한 주소를 가지고 있기에 해당 함수의 크기와 오프셋을 구하기 위해 추가적인 루틴이 존재합니다. 따라서 해당 함수는 두 가지 파트로 구성되어 있습니다.

이진 탐색을 통해 주소에 대응하는 index를 찾는 파트
인접한 인덱스에 동일한 주소를 가지는 심볼이 있는지를 확인하는 파트

이제 구현을 살펴보도록 하겠습니다.

Line 18~24: 이진 탐색을 수행합니다. 최종 인덱스는 low에 저장됩니다. kallsyms_sym_adress 함수를 통해 인덱스에 해당하는 심볼의 주소를 가져옵니다.
Line 30~33: 해당 주소에 다른 심볼이 존재할 수 있습니다. 따라서 이전의 심볼을 검색하며 동일한 주소인지 확인합니다. 따라서 해당 주소의 첫 번째 심볼을 사용합니다. 이렇게 구한 인덱스를 통해 심볼의 주소를 symbol_start에 저장합니다.
Line 35~41: 주소에 대응하는 함수의 크기를 구하기 위해 aliasing 되지 않은 심볼을 찾습니다. 찾은 심볼의 주소를 symbol_end에 저장합니다.
Line 53~56: 구한 symbol_start, symbol_end를 통해 size와 offset를 구하고 반환합니다.

이제 이렇게 구한 인덱스를 통해 압축된 문자열의 주소를 구해야 합니다. 이때 사용되는 것이 get_symbol_offset 함수입니다. 앞서 심볼 정보를 저장할 때, kallsyms_name 두에 압축된 문자열을 저장했습니다. 압축된 문자열은 앞 부분에 문자열의 길이를 저장하고 뒤에 문자열을 저장하는 형태였습니다. 또한 256개의 문자열마다의 오프셋을 기록하는 마커라는 녀석도 있었습니다. 이러한 특성을 이용하여 아래의 함수는 구현되었습니다. 간단하므로 설명은 생략하겠습니다.

이제 살펴볼 마지막 함수인 kallsyms_expand_symbol 함수입니다. 해당 함수는 압축된 문자열을 압축 해제하는 단순한 일을 수행합니다. 압축 해제하기 위해서는 kallsyms_token_table을 이용합니다.

Line 14~22: 압축 문자열의 길이를 읽어옵니다. offset은 다음 압축 문자열의 위치로 변경합니다.
Line 25~29: 길이가 긴 심볼에 대한 특별한 처리입니다.
Line 35~51: 각각의 문자에 대해 token_table에 저장되어 있는 문자열로 치환합니다.
Line 54~58: maxlen을 넘지 않았다면 끝에 0x00을 추가합니다. 또한 offset을 반환합니다.

Conclusion

이것으로 kallsyms의 전체적인 윤곽을 다 살펴보았습니다. 물론 커널 이미지 내에 심볼 처리 과정만 보았기에 부족한 부분이 있지만 충분한 통찰을 얻을 수 있다고 생각합니다. 공부한 내용을 활용하면, User space에서의 나만의 backtrace를 구현하거나, 나만의 OS에서 고수준의 panic로그를 구현할 수 있을 것 같습니다. 또한 조금 더 공격적인 압축 알고리즘을 제안할 수도 있을 것 같습니다. 이 글에서 다룬 커널에서 구현한 kallsyms 재미있었다면, glibc에서 구현한 backtrace을 살펴보는 것도 추천합니다.