ELFをロードするブートローダを書く

ELFにコンパイルしたカーネルを動かしたい！願わくばどこにロードしても動いてほしい！

ELFフォーマットもUEFIもEDKもわからんわからん良いながらがんばったのでメモ書き程度に。

今回は共有ライブラリとしてコンパイルしたELFを動かすので、ELFの話とかも共有ライブラリの話に偏ります。

コード書く時に参照した記事・コード：[ELF入門](http://sugawarayusuke.hatenablog.com/entry/2017/04/09/213133)、[mikanos](https://github.com/uchan-nos/mikanos)

# 本題の前に、題材をつくろう。

今回ロードするカーネルはこちら

``` c
#include <stdint.h>

int a = 0xaa;
uint64_t i;

uint8_t f() {
    return a;
}

int _start(uint8_t *frame_buffer, uint64_t size) {
    for (i = 0; i < size; i ++) {
        frame_buffer[i] = f();
    }

    while (1) {
        __asm__ volatile ("hlt");
    }
}
```

やってることはブートローダからブレームバッファをもらって全部に0xaaを書き込むだけです。色は白と黒以外から適当に選びました。

ポイントは「グローバル変数を使用している」、「関数を使用している」です。

で、コンパイルは

```
gcc -o kernel.elf kernel.c -fPIC --shared -nostdlib
```

共有ライブラリとしてコンパイルします。PICなのはどこに入れても動くようにですが、共有ライブラリにした理由はまた後にわかります。(再配置がgotだけで簡単だから)

# まずはELFの話から

ELFとは実行バイナリのフォーマットのことで、動くプログラム(.textセクション)以外にデバッグシンボルやら再配置情報やらデータやらが詰まっています。あとで再配置の情報というのが大事になってきますがまあ。

ELFには大きく「ファイル(ELF)ヘッダ」、「プログラムヘッダテーブル」、「セクションヘッダテーブル」が重要な要素としてあります。


まずファイルヘッダはファイルの先頭にあって自分の情報が詰まっています。まあ内容は実際のコードを見ればわかります。

``` c:elf.h
typedef struct
{
  unsigned char	e_ident[EI_NIDENT];	/* Magic number and other info */
  Elf64_Half	e_type;			/* Object file type */
  Elf64_Half	e_machine;		/* Architecture */
  Elf64_Word	e_version;		/* Object file version */
  Elf64_Addr	e_entry;		/* Entry point virtual address */
  Elf64_Off	e_phoff;		/* Program header table file offset */
  Elf64_Off	e_shoff;		/* Section header table file offset */
  Elf64_Word	e_flags;		/* Processor-specific flags */
  Elf64_Half	e_ehsize;		/* ELF header size in bytes */
  Elf64_Half	e_phentsize;		/* Program header table entry size */
  Elf64_Half	e_phnum;		/* Program header table entry count */
  Elf64_Half	e_shentsize;		/* Section header table entry size */
  Elf64_Half	e_shnum;		/* Section header table entry count */
  Elf64_Half	e_shstrndx;		/* Section header string table index */
} Elf64_Ehdr;
```

ここにおいてwordは32、halfは16bitです。

ここで重要なのは`e_phoff`と`e_shoff`です。これがプログラムヘッダテーブルのファイルの先頭からのオフセットとセクションヘッダテーブルのファイルの先頭からのオフセットになります。

つまり

``` c
    Elf64_Ehdr *elf_header = (Elf64_Ehdr*)ファイルを読んだ先頭のアドレス;
    Elf64_Shdr *section_header_table = (Elf64_Shdr*)((UINT64)先頭 + elf_header->e_shoff);
    Elf64_Phdr *program_header_table = (Elf64_Phdr*)((UINT64)先頭 + elf_header->e_phoff);
```

となります。

型とかフィールドの命名が若干不思議な気がするかも知れませんが慣れてください。

ちなみに実際のファイルヘッダは`readelf -h`で見ることができます。

```
$ readelf -h kernel.elf
ELF ヘッダ:
  マジック:  7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  クラス:                            ELF64
  データ:                            2 の補数、リトルエンディアン
  バージョン:                        1 (current)
  OS/ABI:                            UNIX - System V
  ABI バージョン:                    0
  型:                                DYN (共有オブジェクトファイル)
  マシン:                            Advanced Micro Devices X86-64
  バージョン:                        0x1
  エントリポイントアドレス:          0x102f
  プログラムの開始ヘッダ:            64 (バイト)
  セクションヘッダ始点:              13232 (バイト)
  フラグ:                            0x0
  このヘッダのサイズ:                64 (バイト)
  プログラムヘッダサイズ:            56 (バイト)
  プログラムヘッダ数:                9
  セクションヘッダ:                  64 (バイト)
  セクションヘッダサイズ:            20
  セクションヘッダ文字列表索引:      19
```

で、セクションヘッダの定義が

``` c
typedef struct
{
  Elf64_Word	sh_name;		/* Section name (string tbl index) */
  Elf64_Word	sh_type;		/* Section type */
  Elf64_Xword	sh_flags;		/* Section flags */
  Elf64_Addr	sh_addr;		/* Section virtual addr at execution */
  Elf64_Off	sh_offset;		/* Section file offset */
  Elf64_Xword	sh_size;		/* Section size in bytes */
  Elf64_Word	sh_link;		/* Link to another section */
  Elf64_Word	sh_info;		/* Additional section information */
  Elf64_Xword	sh_addralign;		/* Section alignment */
  Elf64_Xword	sh_entsize;		/* Entry size if section holds table */
} Elf64_Shdr;
```

プログラムヘッダの定義が

``` c
typedef struct
{
  Elf64_Word	p_type;			/* Segment type */
  Elf64_Word	p_flags;		/* Segment flags */
  Elf64_Off	p_offset;		/* Segment file offset */
  Elf64_Addr	p_vaddr;		/* Segment virtual address */
  Elf64_Addr	p_paddr;		/* Segment physical address */
  Elf64_Xword	p_filesz;		/* Segment size in file */
  Elf64_Xword	p_memsz;		/* Segment size in memory */
  Elf64_Xword	p_align;		/* Segment alignment */
} Elf64_Phdr;
```

`readelf`は、セクションが`-S`、プログラムが`-l`で見れます。

```
$  readelf -S kernel.elf
There are 20 section headers, starting at offset 0x33b0:

セクションヘッダ:
  [番] 名前              タイプ           アドレス          オフセット
       サイズ            EntSize          フラグ Link  情報  整列
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .note.gnu.build-i NOTE             0000000000000238  00000238
       0000000000000024  0000000000000000   A       0     0     4
  [ 2] .gnu.hash         GNU_HASH         0000000000000260  00000260
       0000000000000034  0000000000000000   A       3     0     8
  [ 3] .dynsym           DYNSYM           0000000000000298  00000298
       0000000000000078  0000000000000018   A       4     1     8
  [ 4] .dynstr           STRTAB           0000000000000310  00000310
       000000000000000e  0000000000000000   A       0     0     1
  [ 5] .rela.dyn         RELA             0000000000000320  00000320
       0000000000000030  0000000000000018   A       3     0     8
  [ 6] .rela.plt         RELA             0000000000000350  00000350
       0000000000000018  0000000000000018  AI       3    13     8
  [ 7] .plt              PROGBITS         0000000000001000  00001000
       0000000000000020  0000000000000010  AX       0     0     16
  [ 8] .text             PROGBITS         0000000000001020  00001020
       0000000000000079  0000000000000000  AX       0     0     1
  [ 9] .eh_frame_hdr     PROGBITS         0000000000002000  00002000
       0000000000000024  0000000000000000   A       0     0     4
  [10] .eh_frame         PROGBITS         0000000000002028  00002028
       000000000000007c  0000000000000000   A       0     0     8
  [11] .dynamic          DYNAMIC          0000000000003ed0  00002ed0
       0000000000000120  0000000000000010  WA       4     0     8
  [12] .got              PROGBITS         0000000000003ff0  00002ff0
       0000000000000010  0000000000000008  WA       0     0     8
  [13] .got.plt          PROGBITS         0000000000004000  00003000
       0000000000000020  0000000000000008  WA       0     0     8
  [14] .data             PROGBITS         0000000000004020  00003020
       0000000000000004  0000000000000000  WA       0     0     4
  [15] .bss              NOBITS           0000000000004028  00003024
       0000000000000008  0000000000000000  WA       0     0     8
  [16] .comment          PROGBITS         0000000000000000  00003024
       000000000000002c  0000000000000001  MS       0     0     1
  [17] .symtab           SYMTAB           0000000000000000  00003050
       0000000000000270  0000000000000018          18    22     8
  [18] .strtab           STRTAB           0000000000000000  000032c0
       0000000000000047  0000000000000000           0     0     1
  [19] .shstrtab         STRTAB           0000000000000000  00003307
       00000000000000a5  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)
```

```
$  readelf -l kernel.elf

Elf ファイルタイプは DYN (共有オブジェクトファイル) です
Entry point 0x102f
There are 9 program headers, starting at offset 64

プログラムヘッダ:
  タイプ        オフセット          仮想Addr           物理Addr
            ファイルサイズ        メモリサイズ         フラグ 整列
  LOAD           0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000368 0x0000000000000368  R      0x1000
  LOAD           0x0000000000001000 0x0000000000001000 0x0000000000001000
                 0x0000000000000099 0x0000000000000099  R E    0x1000
  LOAD           0x0000000000002000 0x0000000000002000 0x0000000000002000
                 0x00000000000000a4 0x00000000000000a4  R      0x1000
  LOAD           0x0000000000002ed0 0x0000000000003ed0 0x0000000000003ed0
                 0x0000000000000154 0x0000000000000160  RW     0x1000
  DYNAMIC        0x0000000000002ed0 0x0000000000003ed0 0x0000000000003ed0
                 0x0000000000000120 0x0000000000000120  RW     0x8
  NOTE           0x0000000000000238 0x0000000000000238 0x0000000000000238
                 0x0000000000000024 0x0000000000000024  R      0x4
  GNU_EH_FRAME   0x0000000000002000 0x0000000000002000 0x0000000000002000
                 0x0000000000000024 0x0000000000000024  R      0x4
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RW     0x10
  GNU_RELRO      0x0000000000002ed0 0x0000000000003ed0 0x0000000000003ed0
                 0x0000000000000130 0x0000000000000130  R      0x1

 セグメントマッピングへのセクション:
  セグメントセクション...
   00     .note.gnu.build-id .gnu.hash .dynsym .dynstr .rela.dyn .rela.plt 
   01     .plt .text 
   02     .eh_frame_hdr .eh_frame 
   03     .dynamic .got .got.plt .data .bss 
   04     .dynamic 
   05     .note.gnu.build-id 
   06     .eh_frame_hdr 
   07     
   08     .dynamic .got
```

セクションヘッダはセクションを見るのに、プログラムヘッダは実際にメモリに読み込むときにファイルとメモリ配置の異差の解決に使うことになります。


# 実装的な話に入ってくよ

ELFは、

OS「はいいらっしゃい(ファイルを開く)エントリーポイントﾄﾞｰｰｰｰｰﾝ(call)！！！！！！！！！動け動け動け動け動け動け動け動け動いた？動いた？動いた？動いた？動いた？うごいた？動いた？動いた？動いた？動いた？動いた？返れ返れ返れ返れ返れ返れ返れ返れ返れ返れ返れ(exit)

とはいきません。ファイルそのままでは動かず、メモリにいい感じに配置する必要があります。例えば、ファイルの容量を減らすために初めから0とわかっている領域があれば、「ここからここまでは0」という情報を載せて実際の0は除きます。これがプログラムヘッダのファイルサイズとメモリサイズに当たります。

つまり

OS「はいいらっしゃい(ファイルを開く)**お席へどうぞ(メモリに配置)**エントリーポイントﾄﾞｰｰｰｰｰﾝ(call)！！！！！！！！！動け動け動け動け動け動け動け動け動いた？動いた？動いた？動いた？動いた？うごいた？動いた？動いた？動いた？動いた？動いた？返れ返れ返れ返れ返れ返れ返れ返れ返れ返れ返れ(exit)

の1ステップが必要です。

というわけでまずは席へ案内しましょう。

CでEDKを使って書きますがまあ普通に読めると思うので、普通の環境で書き直してもいいと思います。mallocとかローカル変数でメモリとっても実行はできないので注意(mmapを使いましょう)

席へ案内する前に席を確保する前に適切な席の大きさを知りたいです。

``` c
    UINT64 last_offset;
    last_offset = 0;
    for (UINTN i = 0; i < elf_header->e_phnum; i ++) {
        Elf64_Phdr program_header = program_header_table[i];

        if (program_header.p_type != PT_LOAD) {
            continue;
        }

        last_offset = MAX(last_offset, program_header.p_vaddr + program_header.p_memsz);
    }
```

まず、プログラムヘッダを巡回します。ファイルヘッダの`e_phnum`にプログラムヘッダの数があるので利用します。

そして、タイプがPT_LOADじゃなかったらスキップします。詳細はよくわかりませんがLOADじゃないところはロードしなくてもうごくので・・・

で、必要なメモリの大きさを調べます。p_vaddrは仮想アドレスですが、これは共有ライブラリであってロードする場所とかは特にないので、いい感じに0から始まってくれています。なので、これがオフセットになってくれます(動いてるからヨシ！状態)。で、これにその領域の大きさを足した値の最大値をとって、0から最大値までが必要な席の大きさとします。


次に席を確保します。これにはboot serviceのAllocatePoolを使うだけです。(普通の環境でmallocするとメモリに実行権限がつかないので注意)

``` c
    VOID *buffer;
    gBS->AllocatePool(EfiLoaderData, last_offset, &buffer);
```

(本来は返り値のステータスを見るべきですが。)
(EfiLoaderDataは多分(ブート)ローダ用のデータ、みたいな意味かな。知らんけど)


で、やっと席に案内します。

``` c
    for (UINTN i = 0; i < elf_header->e_phnum; i ++) {
        Elf64_Phdr program_header = program_header_table[i];
        if (program_header.p_type != PT_LOAD) {
            continue;
        }

        CopyMem(buffer + program_header.p_vaddr, file_buffer + program_header.p_offset, program_header.p_filesz);
        SetMem(buffer + program_header.p_vaddr + program_header.p_filesz,program_header.p_memsz - program_header.p_filesz,  0);
    }
```

やってることはさっきと同じでプログラムヘッダを巡回、LOAD以外弾く。
そしてファイルからコピーする領域はコピーして、ファイルに無い領域は0をセットします。(CopyMemの引数の順番がmemcpyとは違うので注意)
(file_bufferはファイルのバッファーです。さっき先頭って書いたやつ。)



# 再配置する

セクションヘッダの出番です。

PICといっても、すべての要素になんの調整もなくアクセスできるわけでもなく、というか本来共有ライブラリはそれ単体でなんとかするものではないので、他のプログラムから要素にアクセスできる仕組みがよういされています。これがGOT(Grobal Offset Table)です。

共有ライブラリはそれぞれGOTを持っていて、GOTに実態のアドレスを置いておいて、外から(自分からも)GOTにアクセスして、そこにあるアドレスにアクセスします。
(関数アクセスはこれに＋でPLT(Program Linkage Table)も通ります。)

つまりGOTに再配置情報を書き込めばいいわけですが、これがまとまっているセクションが.relaです。

とりあえず`readelf`で見てみましょう。`-r`です。

```
$  readelf -r kernel.elf

再配置セクション '.rela.dyn' at offset 0x320 contains 2 entries:
  オフセット      情報           型             シンボル値    シンボル名 + 加数
000000003ff0  000200000006 R_X86_64_GLOB_DAT 0000000000004028 i + 0
000000003ff8  000400000006 R_X86_64_GLOB_DAT 0000000000004020 a + 0

再配置セクション '.rela.plt' at offset 0x350 contains 1 entry:
  オフセット      情報           型             シンボル値    シンボル名 + 加数
000000004018  000100000007 R_X86_64_JUMP_SLO 0000000000001020 f + 0
```

このオフセットのところにシンボル値と言うやつを書き込めば万事解決です。
このシンボル値、Relaセクションだけ見ても書いてなくて、Relaからシンボルテーブルのインデックスを出してシンボルをみないといけません。


さて、まずは特定のセクションを取り出します。取り出すのは`.rela.dyn, .rela.plt, .dynsym, .dynstr`です。

ただその前に、セクション名を知るのにも1ステップあって、セクションの名前テーブルがあります。


セクションの名前テーブル(絶妙にダサい)(正式な日本語約がわからない)のセクションヘッダのインデックスがファイルヘッダの`e_shstrndx`に入っています。
これで得たセクションヘッダの`sh_offset`がファイルの先頭からセクションの名前テーブルへのオフセットになります。

```c
CHAR8* section_name_table = (CHAR8*)(file_buffer + section_header_table[elf_header->e_shstrndx].sh_offset);
```

どう使うかと言うと、セクションヘッダの`sh_name`がこのsection name tableでのインデックスになります。
これを使って、`.rela.dyn, .rela.plt, .dynsym, .dynstr`を取り出します。

``` c
    Elf64_Shdr rela_dyn_section, rela_plt_section, dynsym_section, dynstr_section;

    for (UINTN i = 0; i < elf_header->e_shnum; i ++) {
        Elf64_Shdr section_header = section_header_table[i];

        CHAR8* sec_name = section_name_table + section_header.sh_name;

        if (strcmp_8(sec_name, ".rela.dyn") == 0) {
            rela_dyn_section = section_header;
        } else if (strcmp_8(sec_name, ".rela.plt") == 0) {
            rela_plt_section = section_header;
        } else if (strcmp_8(sec_name, ".dynsym") == 0) {
            dynsym_section = section_header;
        } else if (strcmp_8(sec_name, ".dynstr") == 0) {
            dynstr_section = section_header;
        }
    }
```

`strcmp_8`は適当に実装したstrcmpです(_8ってつけたのはUEFIはUTF16だから)
これで特定のセクションヘッダを取り出すことができました。


あとはrelaを回って置き換えるだけです。

ところで、dynsymセクションにはシンボル情報のテーブルがあります。シンボルとはグローバル変数とか関数とかのことです。
.rela.dynも.rela.pltも再配置情報のテーブルです。セクションは大体テーブルです。そんな気がしてきた

ちなみにそれぞれ`Elf64_Sym`、`Elf64_Rela`って型です。`/usr/include/elf.h`にあるので見てみてください・・・

``` c
    Elf64_Sym *sym_table = (Elf64_Sym*)(file_buffer + dynsym_section.sh_offset);
    Elf64_Rela *rela_dyn = (Elf64_Rela*)(file_buffer + rela_dyn_section.sh_offset);
    Elf64_Rela *rela_plt = (Elf64_Rela*)(file_buffer + rela_plt_section.sh_offset);
```

``` c
    for (UINTN i = 0; i < rela_dyn_section.sh_size / sizeof(Elf64_Rela); i ++) {
        Elf64_Sym s = sym_table[ELF64_R_SYM(rela_dyn[i].r_info)];
        Elf64_Rela r = rela_dyn[i];

        void *to = buffer + r.r_offset;
        *(uint64_t*)to = (uint64_t)(buffer + s.st_value);
    }
```

`sh_size`にセクションの大きさが入っているので要素の大きさで割って数を出します。

で、シンボルテーブルのインデックスの出し方が曲者なのですが、`r_info`にはシンボルのインデックスとタイプが混ざっています。のでインデックスだけ取り出して使用します。

で、relaの`r_offset`の位置にシンボルの`st_value`の位置を書き込めばOKです。


これをrela.pltにもやります

``` c
    for (UINTN i = 0; i < rela_plt_section.sh_size / sizeof(Elf64_Rela); i ++) {
        Elf64_Sym s = sym_table[ELF64_R_SYM(rela_plt[i].r_info)];
        Elf64_Rela r = rela_plt[i];

        void *to = buffer + r.r_offset;
        *(uint64_t*)to = (uint64_t)(buffer + s.st_value);
    }
```


そして最後、エントリーポイントを探します。
今回は`"_start"`とします。

さっきのと同じように今度はdynsymを回ってシンボル名が`"_start"`なシンボルを探して位置を取り出します。

ところでここでやっと登場するのがdynstrセクションです。これはdynsymのシンボル名のテーブルになります。

``` c
    UINT64 entry_offset = 0;
    for (UINTN i = 0; i < dynsym_section.sh_size / sizeof(Elf64_Sym); i ++) {
        Elf64_Sym s = sym_table[i];

        if (ELF64_ST_TYPE(s.st_info) == STT_FUNC) {
            CHAR8 *sym_name = ((CHAR8*)(file_buffer + dynstr_section.sh_offset)) + s.st_name;
            if (strcmp_8(sym_name, entry_point_symbol) == 0) {
                entry_offset = s.st_value;
            }
        }
    }
```

`entry_point_symbol`に`"_start"`が入っています。

ここでもさっきと同じように、Symのタイプもマクロを使って取り出します。エントリーポイントは当然FUNCなはずなのでFUNC以外はスルーします。

これでやっと起動準備が整いました。

``` c
void *entry_point = buffer + entrty_offset;
```



[全容はGitHubを見てください・・(力尽きた)]([https://github.com/Lan-t/MyOsLoader/blob/master/Applications/Loader/LoadElf.c)