Kallsymsの仕組み

Linuxにはkallsymsという仕組みがあります。
これはカーネル空間に存在するシンボル名とアドレスのテーブルを、実行時に参照できるようにするものです。

本稿ではソースコードを引用しながらkallsymsの用途と、いかにこれを実現しているのか、仕組みを解説します。

kallsymsとは

kallsymsはシンボル名とアドレスのテーブルです。一般的なLinux PCではsudo cat /proc/kallsymsで表示できます(一般ユーザ権限ではアドレスがすべて00000000になります)。

$ sudo cat /proc/kallsyms | head -10
0000000000000000 A fixed_percpu_data
0000000000000000 A __per_cpu_start
0000000000001000 A cpu_debug_store
0000000000002000 A irq_stack_backing_store
0000000000006000 A cpu_tss_rw
0000000000009000 A gdt_page
000000000000a000 A exception_stacks
0000000000014000 A entry_stack_storage
0000000000015000 A espfix_waddr
0000000000015008 A espfix_stack

kallsymsの用途の例 : カーネルパニック発生時のバックトレース表示

Linuxのカーネル空間で回復不能なエラーが発生した際カーネルパニックと呼ばれる状態になり、以下のようにエラー発生時のバックトレースを表示します。

[    0.478468] Call trace:
[    0.478485]  dump_backtrace+0x0/0x1e8
[    0.478530]  show_stack+0x18/0x68
[    0.478549]  dump_stack+0xcc/0x124
[    0.478564]  panic+0xd0/0x3a8
[    0.478581]  mount_block_root+0x298/0x350
[    0.478597]  mount_root+0x78/0x8c
[    0.478614]  prepare_namespace+0x13c/0x180
[    0.478629]  kernel_init_freeable+0x214/0x250
[    0.478644]  kernel_init+0x14/0x110
[    0.478658]  ret_from_fork+0x10/0x34

呼び出し元のアドレスは、例えばarm64実装の場合はスタックフレームを遡って計算します(arch/arm64/kernel/stacktrace.c)。こうして得た呼び出し元のアドレスとkallsymsの情報を突き合わせてシンボル名による表示を実現しています。

バックトレース表示のもっとも高級なAPIはdump_stackです。例えばarm64実装で異常な同期例外によりカーネルパニックに至るケースでは、inv_entryマクロで定義されるハンドラからbad_modeに行き、以下のコールスタックでdump_stackします。

(v5.10におけるarm64実装で異常な動機例外からカーネルパニックに至るコールスタック)

dump_backtraceではスタックフレームをたどって戻り先アドレス(lr)をトレースし、1行ごとにdump_backtrace_entryを実行しています。dump_backtrace_entryを見てみましょう。

// https://github.com/torvalds/linux/blob/v5.10/arch/arm64/kernel/stacktrace.c#L135

static void dump_backtrace_entry(unsigned long where, const char *loglvl)
{
    printk("%s %pS\n", loglvl, (void *)where);
}

whereが戻り先アドレスです。Linuxカーネルではsprintf等でフォーマット%pSを使用すると、カーネル空間のアドレス(unsigned long)をシンボル名+オフセットに成形してくれます。この仕組みはkallsymsによって実現されています。とても便利です。

printkにおける%pSの変換

printk("%pS")は以下のコールスタックでkernel/kallsyms.csprint_symbolにいきます。ここでkallsymsの仕組みによりアドレスがシンボル名の文字列に変換されます。コールスタックがすべてアーキテクチャ非依存であることに注目してください。これはすごいことです。

kallsyms自体はアドレスとシンボル名のテーブルにすぎず、ここまでくればアドレスでテーブルを引くだけなので、簡単です(高速化・省メモリの工夫が行われており、これは一読に値しますが)。

kallsymsのデータ構造

カーネルをCONFIG_KALLSYMS=yでビルドすると.tmp_vmlinux.kallsyms1.Sといったファイルが生成され、.rodataに以下のようなデータが入ります。

        .section .rodata, "a"
.globl kallsyms_offsets
        ALGN
kallsyms_offsets:
        .long   0
        .long   0
        .long   0x800
        .long   0x800
        .long   0x800
        .long   0x800
        .long   0x800
        .long   0xa68
...

.globl kallsyms_relative_base
        ALGN
kallsyms_relative_base:
        PTR     _text + 0

.globl kallsyms_num_syms
        ALGN
kallsyms_num_syms:
        .long   13745

.globl kallsyms_names
        ALGN
kallsyms_names:
        .byte 0x04, 0xff, 0x68, 0x65, 0xd0
        .byte 0x04, 0x54, 0xb6, 0xc9, 0x74
        .byte 0x04, 0x54, 0xb5, 0xc9, 0x74
        .byte 0x07, 0xd7, 0x8a, 0xfd, 0xc3, 0xe7, 0x72, 0x71
        .byte 0x0a, 0xd7, 0xb8, 0xd5, 0xf3, 0xda, 0x74, 0xc9, 0xff, 0xd5, 0x64
        .byte 0x0b, 0xd7, 0xb8, 0xd5, 0xf3, 0xda, 0x74, 0xc9, 0xff, 0xc1, 0xf9, 0x74
        .byte 0x10, 0x54, 0x5f, 0xfd, 0xc3, 0xe7, 0x72, 0x71, 0xd5, 0xf3, 0xda, 0x74, 0xc9, 0xff, 0xc1, 0xf9, 0x74
        .byte 0x0a, 0xd7, 0xd5, 0xf3, 0xda, 0x74, 0xc9, 0xff, 0xc1, 0xf9, 0x74
...

.globl kallsyms_markers
        ALGN
kallsyms_markers:
        .long   0
        .long   3070
        .long   6121
        .long   8976
...

.globl kallsyms_token_table
        ALGN
kallsyms_token_table:
        .asciz  "_h"
        .asciz  "dr"
        .asciz  "_cpu"
        .asciz  "T__arm64_sys_"
        .asciz  "Tp"
...

.globl kallsyms_token_index
        ALGN
kallsyms_token_index:
        .short  0
        .short  3
        .short  6
        .short  11
...

見て分かるように簡単な辞書式の圧縮が施されていますが、基本的にはuint32_t addr[N]とnull separatedな文字列のテーブルです。 圧縮アルゴリズム(scripts/kallsyms.c)や検索の方法(kernel/kallsyms.c)については各論になってしまうのでここでは説明しません。 データ構造を詳しく調べるには検索するほうの実装kernel/kallsyms.cを見ることをお勧めします。

vmlinuxに自身のシンボルテーブルを含める方法

実行可能なELFファイルのDRAMにロードされるセクション(Aフラグがついているセクション)に自身のシンボルテーブルを入れることは、通常できません。
デバッグする際にデバッガが行番号やシンボル名などを表示できますが、これはELFファイルのデバッグ情報のセクションをデバッガが読み込むからであって、デバッグセクションはDRAM上にロードされるわけではないし、実行中のプログラムから(OSの助けなしに)扱うことは通常できません。しかしLinuxはやっています。どのように実現しているのでしょう。

Linuxカーネルは最後にvmlinuxをビルドしますが、このビルドフェーズが4段階に分かれています。
手元のカーネルビルド環境で以下のコマンドを実行してみてください(CONFIG_KALLSYMS=yとして)。

$ rm vmlinux
$ make vmlinux
  CALL    scripts/checksyscalls.sh
  CALL    scripts/atomic/check-atomics.sh
  CHK     include/generated/compile.h
  GEN     .version
  CHK     include/generated/compile.h
  UPD     include/generated/compile.h
  CC      init/version.o
  AR      init/built-in.a
  LD      vmlinux.o                    <-- 1st link
  MODPOST vmlinux.symvers
  MODINFO modules.builtin.modinfo
  GEN     modules.builtin
  LD      .tmp_vmlinux.kallsyms1       <-- 2nd link
  KSYMS   .tmp_vmlinux.kallsyms1.S
  AS      .tmp_vmlinux.kallsyms1.S
  LD      .tmp_vmlinux.kallsyms2       <-- 3rd link
  KSYMS   .tmp_vmlinux.kallsyms2.S
  AS      .tmp_vmlinux.kallsyms2.S
  LD      vmlinux                      <-- final link
  SORTTAB vmlinux
  SYSMAP  System.map

vmlinuxのリンクはscripts/link-vmlinux.shで行われており、以下の処理があります。

  1. kallsymsのテーブルを除く全部入りバイナリvmlinux.oを生成
  2. 中身が空のkallsymsテーブルを含む.tmp_vmlinux.kallsyms1を生成 (最終的に作りたいvmlinuxに入っているべき全シンボルが含まれ、kallsymsテーブルのサイズが確定する)
  3. ダミーのkallsymsテーブルを含む.tmp_vmlinux.kallsyms2を生成 (各シンボルのアドレスはこのステップで決定されるので、ここに入っているkallsymsテーブルは内容が間違っている)
  4. 正しいkallsymsテーブルを含むvmlinuxを生成 (kallsymsテーブルの中身以外すべて.tmp_vmlinux.kallsyms2と同一)

kallsymsテーブルの生成はscripts/kallsyms.cで行われます。前節で示したようなアセンブラです。

kallsyms風の仕組みを作ってみよう

kallsymsの仕組みが大雑把に理解できたので、簡易的に作ってみましょう。

自身の戻り先アドレスを関数名+オフセットの形式でprintfする関数print_return_addressを作成します。

#include <stdio.h>

struct sym {
        unsigned long addr;
        const char *name;
};

struct sym symbols[] = {
#include "symbols.h"
        {0, NULL}
};

int getsym(unsigned long addr, const char **name, unsigned long *off) {
        struct sym *i;
        struct sym *sym = NULL;

        *name = NULL;

        for (i = symbols; i->name; i++) {
                if (addr < i->addr)
                        continue;

                if (sym == NULL || i->addr > sym->addr)
                        sym = i;
        }

        if (sym) {
                *name = sym->name;
                *off = addr - sym->addr;
                return 1;
        } else {
                return 0;
        }
}

void print_return_address() {
        unsigned long retaddr;
        const char *symname;
        unsigned long off;

        retaddr = (unsigned long)__builtin_extract_return_addr(__builtin_return_address(0));

        printf("return address: %016lx", retaddr);
        if (getsym(retaddr, &symname, &off)) {
                printf("  %s+0x%lx", symname, off);
        }
        printf("\n");
}

int main() {
        print_return_address();
        return 0;
}

ビルド・実行します。

$ echo > symbols.h
$ gcc -no-pie test.c && ./a.out
return address: 00000000004012cc
$ nm -a a.out | grep ' T ' | sort | awk '{printf("{0x%s,\"%s\"},\n", $1, $3)}' > symbols.h
$ gcc -no-pie test.c
$ nm -a a.out | grep ' T ' | sort | awk '{printf("{0x%s,\"%s\"},\n", $1, $3)}' > symbols.h
$ gcc -no-pie test.c
$ ./a.out
return address: 00000000004012cc  main+0x12

symbols.hの生成と再リンクは2回行う必要があります。1回でも偶然うまくいくかもしれませんが、1回目のsymbols.hの生成時点ではsymbols[]のサイズが確定していないため、もう一度実行することが必要です。

また、最近の普通のLinux PCではデフォルトでPIE,PICが有効になっており、ELFファイル上で確認できるアドレスと実行時に実際に配置されるアドレスが異なるため、-no-pieとして絶対アドレスのELFが生成されるようにしています。arm-none-eabi-gccなどベアメタル環境のツールチェーンでは通常は不要です。

さて、print_return_addressは戻り先アドレスがmain+0x12であると申告していますが、正しいか確認しましょう。

$ objdump -d a.out | grep -A 7 '<main>:'
00000000004012ba <main>:
  4012ba:       f3 0f 1e fa             endbr64
  4012be:       55                      push   %rbp
  4012bf:       48 89 e5                mov    %rsp,%rbp
  4012c2:       b8 00 00 00 00          mov    $0x0,%eax
  4012c7:       e8 5b ff ff ff          callq  401227 <print_return_address>
  4012cc:       b8 00 00 00 00          mov    $0x0,%eax
  4012d1:       5d                      pop    %rbp

main+0x120x00000000004012ba + 0x12 = 0x4012ccです。期待通りcallqの次の命令movを指していますね。

まとめ

  • Linuxカーネルは自分自身のシンボルテーブルをAフラグつきのセクションに配置して実行時に参照する機能kallsymsを持っています
  • カーネルパニック発生時のバックトレース表示機能など、Linuxカーネルの強力なデバッグ関連機能はおおいにkallsymsに頼っています
  • kallsymsはvmlinuxのビルドを複数段階に分け、テーブルサイズを決めたあとテーブルの内容を決めることで実現されています (この仕組みはレイアウトが決定的なリンカーの仕様に依存しています)
  • 単純かつポータブルで、簡単に実現できる割に(ベアメタルでは)高級な機能で、開発環境にこれを導入できれば強力なデバッグ機能となるでしょう