aqcc のソースコードを読みたい: リンカ編

aqcc のリンカ部分を読もうと試みつつ苦しんでいます. その途中過程を書き残します.^[1]

開発の際、リンカ・ローダ実践開発テクニックという書籍を参考にされたようですので、そちらが手元にあると便利です. あと man elf や、 X86 psABI から x86-64-psABI-property.pdf として入手できる AMD64 のABI仕様、特にTable 4.9 のRelocation Types などは参考になるかと思います.

以下説明の際は、2018/11/10 コミット分である
2861f51735e0db9e5e7f988a2e51862dca14537a をもとにしています.

概要

このリンカは、リンカローダ本にあるような、簡易的なリンカとして作成されており、いくつか機能が限られています.

リンカの機能制限

動的リンクはできない
GNU ld で生成したELF ファイルを読込めない
生成されたファイルを objdump にてうまく参照できない
再配置作業は最低限のみ行なわれる
普通のELF ファイルとは異なり、ファイルの先端末尾のみならず、中間部にもヘッダ分散^[2]

gcc などと同様に、 ./aqcc そのものではコンパイルを行わず、その下にある cc as ld などに処理を渡し、
実際の処理は ld/main.c からはじまります.

    Vector *objs = new_vector();
    for (int i = 1; i < argc - 1; i++) vector_push_back(objs, argv[i]);

    ExeImage *exe = link_objs(objs);

    FILE *fh = fopen(argv[argc - 1], "wb");
    dump_exe_image(exe, fh);
    fclose(fh);

argv には system.o main.o などとリンク対象のファイル名が指定されるので、それから link_objs() 関数を呼び、リンクされた内容を表す ExeImage へのポインタが生成されます. この構造体も動的に確保されたものですが、malloc() は link_objs() 内部で呼び出され、最後までfree() は呼び出しません. ^[3]
そうして、 dump_exe_image() 関数を呼び出して、書き込んでやっています.

リンク処理の概要

ソースコードを読むと、数値定数が多く埋め込まれていることに気づきます.

一般に、多くのELF を扱うソフトウエアでは、 /usr/include/elf.h に、ELF フォーマットを構造体を用い表したものがあるのを利用し、それに読込ませ、読み書きが分かりやすくできるようです.
一方、aqcc においては、C言語の全ての機能が実装されているわけではありません.^[4]
直接 /usr/include/elf.h を解析するわけにいかず、現状では読み込もうとしても失敗します. そこで、直接ELF ファイルをバイナリとして扱っているようです.

まずは読込みから.
ld/link.c: L55 in new_object_data() などにて、
read_entire_binary() にてchar型の配列として読込まれたデータから、それぞれのセクションごとに切り出しています.

ただ、この部分において定数が頻出します. man elf や実際のバイナリを眺めがなら行うのがよいかと思います.

例えば ld/link.c: L60 in new_object_data() 以降のセクションヘッダを読込む部分など.

    for (int i = 1; i < obj->nshdr; i++) {
        char *entry = obj->shdr + 0x40 * i;
        char *offset = data + read_dword(entry + 24);
        int size = read_dword(entry + 32);

まず、EFI のセクションヘッダが0x40 の大きさをもつことより、セクションヘッダ開始位置を entry に代入しています.
そこから、 man elf にあるように、uint32_t の個数を数えて、offset の位置を同定します. 今回は4 * 6 = 24 となるので、24先から 32bit分を読み込んでいます. ^[5]

メモリ再配置部分を見てみます.
ld/link.c: L130 in link_objs_detail() のあたりでしょうか. 読み込んだそれぞれのELF ファイルの再配置テーブルから、再配置すべきものを抜き出し、検索し書き換えを行なっています.

そののち、再配置情報が特定なものになっている場合 (aqcc のアセンブラではこれしか出てきません) AMD64 の仕様にある R_X86_64_PC32 の再配置方式に従い、オフセットの差を検索して代入しています. しかしながら、筆者の能力ではいまいち、理解できずじまいです.
仕様読めない.

ここにある & 0xff の意味については後述します.

次に、書き込みを見てみます.
ld/link.c: L207 in dump_exe_image() などにて、 emit_byte() なり emit_dword() 関数なりで、奇妙な数値を書き込んでいます.

これらの関数は ld/object.c にて定義されるように、 set_buffer_to_emit() によって定義された Vector に、順番に値を流し込んでいます.

    // ELF magic number
    emit_dword(0x7f, 0x45, 0x4c, 0x46);
    // 64bit
    emit_byte(0x02);
    // little endian
    emit_byte(0x01);
    // original version of ELF
    emit_byte(0x01);
    // System V
    emit_byte(0x00);  // 0x03 GNU
    // padding
    emit_qword(0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00);

    // (中略)
    for (int i = 0; i < vector_size(exeimg->objs); i++) {
        ObjectData *obj = (ObjectData *)vector_get(exeimg->objs, i);
        for (int j = 0; j < obj->data_size; j++) emit_byte(obj->data[j]);
        for (int j = 0; j < obj->entire_size - obj->data_size; j++)
            emit_byte(0);
    }

例えばこの部分. man elf のELF ヘッダー、最初の部分 e_ident を表しています.

また、中略以降、body の部分では、生成した本体部分の内容をバイトごとに書き込み、このようなフォーマットで時たま見かける、中途半端なバイトを0 で埋める作業も、うまく行われています.
ld/link.c: L51 in new_object_data() にて、16 の倍数になるようにして、そこからの不足分を0 にて埋めています.

    obj->entire_size = roundup(data_size, 16);

ここからは、いくつか読解に苦労している点を順不同にならべていきます.

Vector なり Map なり

眺めていると、Vector やMap などといったデータ構造が存在しますが、これは ld/vector.c などを参照すればよいかと思いますが、鮟鱇さんにより実装されたものです.
細かな点は ld/ 以下に記されていますが、関数名などから自然と内容は把握できるかと思います.

シンボルの探索

ld/link.c にあるsearch_symbol_maybe() にて、それぞれのELF オブジェクトごとに線型探索が行なわれています.

従って、時間がとてもかかり、一般的なライブラリ ( 例えば /usr/lib/libc.a の内容など) を読込めるようにするためには、ここの計算量を下げる必要があります. ^[6]

& 0xff

例えば link.c: L297 など、至るところに & 0xff と記されています.

わざわざこのような処理が加えられたのは、aqcc に unsigned char が実装されておらず、char と記すと signed char を意味するためのようです.
^[7]

aqlibc

aqlibc というのは勝手に名付けました. 前述の通り、一般的なC言語標準ライブラリのサブセットが ld/stdlib.c にて実装されています.

malloc() 関数の実装などは、次のように、ただ広い領域を確保してやるのみです. 形式的に free() 関数は実装されていますが、一切処理が行なわれず、確保したメモリが尽きることは想定しないものとなっています. ^[8]

void *malloc(int size)
{
    static char *malloc_pointer_head = 0;
    static int malloc_remaining_size = 0;

    if (malloc_pointer_head == 0) {
        char *p = brk(0);
        int size = 0x32000000;
        char *q = brk(p + size);
        // printf("init %d\n", p);
        // printf("init %d\n", q);
        malloc_pointer_head = p;
        malloc_remaining_size = size;
    }

    // 中略: バグの検出

    char *ret = malloc_pointer_head + 4;
    malloc_pointer_head += size + 4;
    malloc_remaining_size -= size + 4;

    // 中略: デバッグ用コメント
    return ret;
}

また、現状 printf() 関数が標準エラー出力に出されず、標準出力に出されるという制限があります.

以上、aqcc リンカ部分のソースコードについて述べてきました.
aqcc の特にリンカ部分は、350行程度しかなく、付加的な機能が少ないために、リンカの概要を掴むのによいと感じさせられました. 筆者は理解できていませんが、プログラミングにある程度慣れている方なら読み易いのではと思いますし、そこまではしなくとも、実際に試したり、fork してみるなどはいかがでしょうか.

以上、カオスの坩堝 Advent Calendar 21日目の記事でした^[9].

1. 人のソースコードでPVを稼ぐ悪い戦略です.

2. それでも生成した実行ファイルが動くのは、ひとえにELF というフォーマットの柔軟さゆえでしょうか.

3. malloc() にて確保したものをあえて free() しないという考え、筆者には常識外れに感じて受け入れられずにいるが、話を簡単にできるので賢い.

4. unsigned char や (細かな) #if などが実装されていません.

5. このようなソースコードをよく混乱せずに書かれたな、という気持ちになります. すごい.

6. しかしながら、静的リンクであっても実装するのは困難だと思われます. /usr/lib/libc.so はリンカスクリプトを用いた他のファイルへの参照に過ぎず、ELF 形式ではありません.

7. 短期間で自己完結 (self-hosting)を実現するためにはやむをえない回避方法だと思います.

8. この制約も、いきなり難しいものを実装しようとせず、簡単なところから始めるという良い習慣の結果だと感じます.

9. 鮟鱇さんすごいな、と改めて感じさせられました.