ブートローダからカーネルまで

これまでの私の ブログ投稿 を読まれた方はご存じかと思いますが、しばらく前から低水準言語を使うようになりました。Linux用x86_64アセンブリ言語プログラミングについても書いています。また、同時にLinuxのソースコードにも触れるようになりました。下層がどのように機能しているのか、コンピュータでプログラムがどのように実行されるのか、どのようにメモリに配置されるのか、カーネルがどのように処理や記憶をするのか、下層でネットワークスタックがどのように動くのかなどなど、多くのことを理解しようと意欲が湧いています。これをきっかけに、 x86_64 版Linuxカーネルについてシリーズを書いてみようと思いました。

私はプロのカーネルプログラマではないことと、仕事でもカーネルのコードを書いていないことをご了承ください。個人的な趣味です。私は下層で何が起きているのかとても興味があり、単に好きなのです。読んでいて私が勘違いしている点、ご質問やご意見がありましたら、ツイッター（ 0xAX ）や メール でお知らせいただくか、もしくはGithubで Issue を作成してください。助かります。全ての投稿は linux-insides からアクセスできますので、ぜひ読んでみて下さい。また、私の英文が間違っていたり内容に問題があったりした場合は、お気軽にご連絡ください。

これは正式なドキュメントではありません。あくまでも学習のためや知識共有のためのものですのでご注意ください。

必要な知識

• Cコードの理解
• アセンブリコード(AT&T記法)の理解

ツールについて学び始めている人のために、本稿やそれ以降の投稿の中で説明を入れるようにします。簡単な前置きはここまでにして、本題のカーネルと下層のものに入りましょう。

本稿で紹介するコードはLinuxカーネル3.18のものです。変更が生じた場合は、その都度更新します。

魔法の電源ボタン。次に何が起きるのか。

本連載はLinuxカーネルについてのシリーズなのですが、カーネルコードからは始めません(少なくともこの段落では)。ノートパソコンやデスクトップは魔法の電源ボタンを押すと起動します。マザーボードが 電源回路 に信号を送り、コンピュータに適量の電力が供給されます。マザーボードが 電気を流して大丈夫という信号 を受けると、CPUが起動します。CPUによってレジスタに残されたデータはリセットされ、所定の値が設定されます。

80386 や後継のCPUでは、コンピュータがリセットされると次の所定のデータがCPUレジスタに定義されています。

IP  0xfff0 
CS selector     0xf000 
CS base         0xffff0000

リアルモード でプロセッサは動作を始めます。少し戻ってこの動作モードのセグメント方式を理解しましょう。リアルモードは、 8086 を始め、最新のIntel64ビットCPUまでのx86互換のプロセッサに導入されています。8086プロセッサには20ビットアドレスバスがあります。つまり、0-2^20バイト(1メガバイト)のアドレス空間を利用できます。しかし16ビットのレジスタしかなく、16ビットのレジスタが使用できるアドレスは最大で2^16 , または0xffff(64KB)までです。 セグメント方式 は、アドレス空間すべてを利用するために用いられる方法です。全てのメモリは65535バイトまたは64キロバイトの固定長の小さなセグメントに分けられます。16ビットレジスタでは、64キロバイト以上のメモリ位置にアクセスできないので、別の方法でアクセスします。アドレスは、前半のセグメントアドレス部分とオフセットアドレスの2つの部分で構成しています。メモリ内の物理アドレスを割り出すには、セグメントアドレスに16をかけ、オフセットアドレス部分を足します。

PhysicalAddress = Segment * 16 + Offset

例えば、 CS:IP が 0x2000:0x0010 の場合、物理アドレスは次のようになります。

>>> hex((0x2000 << 4) + 0x0010)
'0x20010'

しかし、セグメント部分とオフセット部分を両方最大にした場合、つまり 0xffff:0xffff の場合は次のようになります。

>>> hex((0xffff << 4) + 0xffff)
'0x10ffef'

つまり、最初の1メガバイトよりも65519バイトオーバーしていることになります。リアルモードでアクセスできるのは最大で1メガバイトのため、 A20ライン が無効になっていると 0x10ffef は 0x00ffef になります。

リアルモードとメモリアドレスが分かったところで、リセット後のレジスタの値について説明しましょう。

CS レジスタは、見えるセグメントセレクタと隠れたベースアドレスの2つの部分で構成されています。 CS ベースと IP の値は既知なので、論理アドレスは次にようになります。

0xffff0000:0xfff0

ベースアドレスをEIPレジスタの値に足して、アドレスバスの最初の部分が生成されます。

>>> 0xffff0000 + 0xfff0
'0xfffffff0'

その結果、 0xfffffff0 ができ、4GB-16byteになります。このポイントを リセットベクタ と呼びます。このメモリ配置には、リセット後にCPUが最初に実行するプログラムが置かれています。これには、 JMP命令 が含まれ、通常はBIOSのエントリポイントを指しています。例えば、 coreboot のソースコードを見ると、次のように書かれています。

    .section ".reset"
    .code16
 .globl
 reset_vector reset_vector:
    .byte  0xe9
    .int   _start - ( . + 2 )
    ...

JMP命令の オペコード である0xe9と、その宛先アドレスである _start - ( . + 2) があります。また、 reset セクションが16バイトで 0xfffffff0 から始まることが分かります。

SECTIONS { 
    _ROMTOP = 0xfffffff0;
    . = _ROMTOP; 
    .reset . : { 
        *(.reset) 
        . = 15 ; 
        BYTE(0x00);
    } 
} 

ここでBIOSが実行されます。ハードウェアの初期化とチェックを行い、ブートできるデバイスを探します。ブート順位はBIOS設定に保存されており、カーネルがどのデバイスを使用して起動するのかを操作します。ハードドライブから起動しようとする場合、BIOSはブートセクタを探そうとします。ハードディスクがMBRのパーティションレイアウトによってパーティション分割されている場合、ブートセクタは最初のセクター（512バイト）の最初の446バイトに置かれています。最初のセクターの最後2バイトは 0x55 と 0xaa で、BIOSにこのデバイスが起動可能であることを知らせます。例えば次のようになります。

; 
; Note: this example is written in Intel Assembly syntax 
; 
[BITS 16] 
[ORG  0x7c00]

boot: 
    mov al, '!' 
    mov ah, 0x0e 
    mov bh, 0x00 
    mov bl, 0x07 

    int 0x10 
    jmp $  

times 510-($-$$) db 0  

db 0x55 
db 0xaa

これを実行します。

nasm -f bin boot.nasm && qemu-system-x86\_64 boot 

上のコードが QEMU にディスクイメージとして作成した boot バイナリコードを使用するよう命令します。上のアセンブリコードによって生成されるバイナリコードはブートセクタの要件（はじめが 0x7c00 に設定され、マジックシーケンスで終点を指定）を満たしているので、QEMUはそのバイナリコードをディスクイメージのMBRセクタとして扱います。

次のとおりです。

この例では、16ビットリアルモードでコードが実行され、メモリの0x7c00から始まります。実行が始まると、 0x10 が呼び出され、 ! マークが出力されます。残りの510バイトを0で埋め、2つのマジックバイト 0xaa と 0x55 で終わります。

上のバイナリダンプは objdump で見ることができます。

nasm -f bin boot.nasm 
objdump -D -b binary -mi386 -Maddr16,data16,intel boot 

実際のブートセクタの場合、この続きは多くの0や感嘆府ではなく、起動処理とパーティションテーブルになります。これ以降はBIOSではなくブートローダが操作します。

注 ：上でも書いたようにCPUはリアルモードで動作します。リアルモードでは、メモリ内の物理アドレスを次のように計算します。

PhysicalAddress = Segment * 16 + Offset 

前述したように、16ビットの汎用レジスタしかなく、16ビットレジスタの最大値は 0xffff のため、最大値を取ると次のようになります。

>>> hex((0xffff * 16) + 0xffff) '0x10ffef'

0x10ffef は、 1MB + 64KB - 16b と同じになります。しかし、 8086 プロセッサは、リアルモードが搭載された初めてのプロセッサであり、A20ラインが有効です。また、 2^20 = 1048576 は1MBなので、実際に使用可能なメモリは1メガバイトとなっています。

一般的なリアルモードでのメモリマップは次のとおりです。

0x00000000 - 0x000003FF - Real Mode Interrupt Vector Table 
0x00000400 - 0x000004FF - BIOS Data Area 
0x00000500 - 0x00007BFF - Unused 
0x00007C00 - 0x00007DFF - Our Bootloader 
0x00007E00 - 0x0009FFFF - Unused 
0x000A0000 - 0x000BFFFF - Video RAM (VRAM) Memory 
0x000B0000 - 0x000B7777 - Monochrome Video Memory 
0x000B8000 - 0x000BFFFF - Color Video Memory 
0x000C0000 - 0x000C7FFF - Video ROM BIOS 
0x000C8000 - 0x000EFFFF - BIOS Shadow Area 
0x000F0000 - 0x000FFFFF - System BIOS 

本稿の最初の部分でも書きましたが、CPUが実行する最初の処理は 0xFFFFFFF0 アドレスに配置されています。これは、 0xFFFFF (1メガバイト)よりはるかに大きい領域です。CPUはどのようにしてこのリアルモードでアクセスするのでしょうか。これは coreboot ドキュメントに記載されています。

0xFFFE_0000 - 0xFFFF_FFFF: 128 kilobyte ROM mapped into address space 

実行時、BIOSはRAMではなくROMに置かれています。

ブートローダ

GRUB 2 や syslinux のような、Linux
を起動させることができるブートローダは数多くあります。Linuxカーネルは、Linuxサポートを実行するためのブートローダに必要な条件を指定する ブートプロトコル を持っています。ここではGRUB 2について取り上げます。

BIOSはブートデバイスを選んで、ブートセクタコードに対する制御を伝達し、 boot.img から実行を開始します。このコードは、利用可能な空間が限られているため非常に単純であり、GRUB 2のコアイメージの位置へジャンプするためのポインタを含んでいます。コアイメージは diskboot.img で始まりますが、これは通常、最初のパーティションの前の、使用されていないスペースにある最初のセクタの直後に格納されます。上記のコードは残りのコアイメージをメモリにロードしますが、それにはGRUB 2のカーネルとファイルシステムを取り扱うためのドライバを含んでいます。残りのコアイメージをロードした後に、 grub_main を実行します。

grub_main は、コンソールの初期化、モジュールのためのベースアドレスの取得、ルートデバイスの設定、GRUB設定ファイルの搭載/パース、モジュールのロードなどを行います。実行の最後には、 grub_main がGRUBを通常モードへ移動させます。（ grub-core/normal/main.c からの） grub_normal_execute が最後の準備を完了させ、オペレーティングシステムを選択するためのメニューを表示します。GRUBメニューを選択する際に、 grub_menu_execute_entry が起動し、GRUB boot コマンドを実行して、選択したオペレーティングシステムが作動します。

カーネルのブートプロトコルを見て分かるように、ブートローダはカーネルのセットアップヘッダを読み込み、いくつかのフィールドを満たさなければいけません。そしてそれは、カーネルの設定コードのオフセット 0x01f1 から始まります。カーネルヘッダ arch/x86/boot/header.S は次のようにスタートします。

    .globl hdr 
hdr: 
    setup_sects: .byte 0 
    root_flags:  .word ROOT_RDONLY 
    syssize:     .long 0 
    ram_size:    .word 0 
    vid_mode:    .word SVGA_MODE 
    root_dev:    .word 0 
    boot_flag:   .word 0xAA55

ブートローダは、これと、（ この 例のようなLinuxブートプロトコルの write でマークされている）残りのヘッダを、コマンドラインや計算から導き出される値で満たす必要があります。カーネルのセットアップヘッダの全てのフィールドの記述や説明についてはここれは触れません。後で、カーネルが使用する時に説明します。 ブートプロトコル で全てのフィールドの記述を見つけることができます。

カーネルのブートプロトコルを見て分かるように、メモリマップはカーネルをロードした後、次のようになるでしょう。

         | Protected-mode kernel    | 
100000   +------------------------+ 
        | I/O memory hole   | 
0A0000   +------------------------+  
        | Reserved for BIOS     | Leave as much as possible unused  
        ~                        ~  
        | Command line  | (Can also be below the X+10000 mark) 
X+10000  +------------------------+  
        | Stack/heap    | For use by the kernel real-mode code. 
X+08000  +------------------------+  
        | Kernel setup  | The kernel real-mode code.  
        | Kernel boot sector    | The kernel legacy boot sector. 
      X   +------------------------+   
        | Boot loader   | <- Boot sector entry point 0x7C00 
001000   +------------------------+  
        | Reserved for MBR/BIOS | 
000800   +------------------------+  
        | Typically used by MBR | 

000600   +------------------------+ 
        | BIOS use only     | 
000000   +------------------------+ 

そこでブートローダがカーネルに対する制御を転送したときに、以下で開始されます。

0x1000 + X + sizeof(KernelBootSector) + 1

X がカーネルのブートセクタが搭載されている位置を示します。この場合は、 X が 0x10000 で、メモリダンプに見て取れます。

ブートロードはLinuxカーネルをメモリへロードし、ヘッダのフィールドを満たし、そこへジャンプします。今は、カーネルの設定コードへ直接移動することができます。

カーネルセットアップを開始する。

ついにカーネルまでたどり着きました。しかし、このままでは、カーネルは起動しません。まず、カーネルとメモリ管理、プロセス管理などの設定が必要になります。カーネルのセットアップの実行は _start で arch/x86/boot/header.S から開始します。いくつか命令が前にあって、ひと目見ると、少し違和感を覚えるかもしれません。

ひと昔前は、Linuxカーネルは自前のブートローダを持っていました。ですが、今は実行すると次のようになります。

qemu-system-x86\_64 vmlinuz-3.18-generic

次のような結果が見られるはずです。

実際は（画像の上にある） MZ から header.S が開始され、 PE ヘッダに続いて、エラーメッセージが表示されます。

#ifdef CONFIG_EFI_STUB 
# "MZ", MS-DOS header 
.byte 0x4d 
.byte 0x5a 
#endif 
... 
... 
... 
pe_header: 
    .ascii "PE" 
    .word 0

これには UEFI モードでOSを起動することが必要です。今すぐにこれが稼働するかどうかを確かめることはしませんが、次の章の中の1つで見ていきましょう。

実際のカーネルセットアップのエントリポイントはこちらです。

// header.S line 292 
.globl _start 
_start:

ブートローダ（grub2など）はこのポイント（ MZ からオフセット 0x200 ）を知っています。 header.S がエラーメッセージが表示される .bstext セクションから始まっているにも関わらず、このエントリポイントへ直接ジャンプします。

// 
// arch/x86/boot/setup.ld 
// 
. = 0;                    // current position 
.bstext : { *(.bstext) }  // put .bstext section to position 0 
.bsdata : { *(.bsdata) }

カーネルセットアップのエントリポイントはこちらです。

    .globl _start 
_start: 
    .byte 0xeb 
    .byte start_of_setup-1f 
1: 
    // 
    // rest of the header 
    //

ここでは start_of_setup-1f のポイントに対する jmp 命令オペコード 0xeb が見て取れます。 Nf 表記が意味するところは、 2f が次のローカル 2: ラベルを表しているということです。この場合、ジャンプした直後に行くのがラベル 1 です。そこには残りのセットアップ ヘッダ も含まれます。セットアップヘッダのすぐ後に、 start_of_setup ラベルで開始される .entrytext を見られます。

実際にはこれが（もちろんジャンプ命令を除いて）最初に実行するコードです。カーネルセットアップがブートローダから制御された後に、最初の jmp 命令がカーネルのリアルモードの開始からオフセット 0x200. （最初は512バイト）に格納されます。これは次のLinuxのカーネルブートプロトコルとgrub2のソースコードを見て分かります。

  state.gs = state.fs = state.es = state.ds = state.ss = segment; 
  state.cs = segment + 0x20;

カーネルセットアップが始まった後、セグメントレジスタが以下の値を持つことを意味します。

  gs = fs = es = ds = ss = 0x1000 
  cs = 0x1020

この場合は、カーネルが 0x10000 に置かれます。

start_of_setup にジャンプした後は、以下の作業が必要になります。

• セグメントレジスタの値が同じか確かめる。
• 必要に応じて、正しいスタックをセットアップする。
• bss をセットアップする。
• main.c のCコードにジャンプする。

それでは実装を見てみましょう。

セグメントレジスタのアライメント

まず、セグメントレジスタの ds と es が同じアドレスを指すようにし、 cli 命令を実行して割り込みに応答しないようにします。

    movw    %ds, %ax
    movw    %ax, %es
    cli

前述したとおり、GRUB 2はカーネルの設定コードをアドレス 0x10000 に、 cs を 0x1020 にロードします。なぜなら、実行はファイルの冒頭からではなく、以下のコードから開始されるからです。

_start:
    .byte 0xeb
    .byte start_of_setup-1f 

jump は 4d 5a から512バイト離れたオフセットにあります。また、他の全てのセグメントレジスタと同じように、 cs を 0x1020 から 0x10000 までアラインする必要があります。それが終わったらスタックを設定します。

    pushw   %ds
    pushw   $6f
    lretw

ds の値をスタックにプッシュし、続けてラベル 6 のアドレスもスタックにプッシュすると、 lretw 命令が実行されます。 lretw を呼び出すと、ラベル 6 のアドレスが IP（instruction pointer） レジスタの中にロードされ、 ds の値を備えた cs もロードされます。それが完了すると、 ds と cs は同じ値を持つようになります。

スタックの設定

実際、ほぼ全ての設定コードが、リアルモードでC言語の開発環境を作る準備となります。次の ステップ では ss レジスタの値をチェックし、もし ss が間違っている場合は正しいスタックを設定します。

    movw    %ss, %dx
    cmpw    %ax, %dx
    movw    %sp, %dx
    je  2f

これは、異なる3つのシナリオを導くことが可能です。

• ss が有効値0x10000を持つ（ cs を除く全てのセグメントレジスタと同様）
• ss は無効で、 CAN_USE_HEAP フラッグが設定されている（下記参照）
• ss は無効で、 CAN_USE_HEAP フラッグが設定されていない（下記参照）

それでは、これら3つのシナリオを全て見てみましょう。

1. ss は正しいアドレス（0x10000）を持つ。この場合は、ラベル 2 へと進みます。

2:  andw    $~3, %dx
    jnz 3f
    movw    $0xfffc, %dx
3:  movw    %ax, %ss
    movzwl %dx, %esp
    sti

ここで、 dx （ブートローダによって与えられる sp を含みます）が4バイトにアラインされ、ゼロになっているかどうか確認できます。ゼロの場合は 0xfffc （最大セグメントサイズの64KBより前で4バイトにアラインされたアドレス）を dx 内に置きます。ゼロでない場合は、引き続きブートローダに与えられた sp （私の例では0xf7f4）を使います。正しいセグメントアドレス 0x10000 を格納している ss に ax の値を置いた後で、正しい sp の値を設定します。これで正しいスタックが設定できました。

2. 2つ目のシナリオでは（ ss != ds ）となります。まず、 _end (設定コードの最後のアドレス)の値を dx に置き、 loadflags のヘッダフィールドを testb 命令を使ってチェックし、ヒープ領域を使えるかどうかを確認します。 loadflags は、以下のように定義されるビットマスクヘッダです。

#define LOADED_HIGH     (1<<0)
#define QUIET_FLAG      (1<<5)
#define KEEP_SEGMENTS   (1<<6)
#define CAN_USE_HEAP    (1<<7)

また、ブートプロトコルを読むと、以下のように書かれています。

Field name: loadflags

  This field is a bitmask.

  Bit 7 (write): CAN_USE_HEAP
    Set this bit to 1 to indicate that the value entered in the
    heap_end_ptr is valid.  If this field is clear, some setup code
    functionality will be disabled.

(訳: heap_end_ptrに入力された値が有効であることを示すために、このビットを1にしてください。もしこのフィールドがからの場合、いくつかのセットアップコードの機能は無効になります。)

CAN_USE_HEAP のビットが設定された場合は、 _end を指す dx に heap_end_ptr を置き、そこに STACK_SIZE （最小スタックのサイズは512バイト）を加えます。これ以降、 dx がキャリーでない場合（キャリーでなければ、dx = _end + 512となる）、これの前のケースと同じようにラベル 2 にジャンプし、正しいスタックを作ります。

3. CAN_USE_HEAP が設定されていない場合は、 _end から _end + STACK_SIZE まで、最小スタックを使うだけです。

BSSの設定

メインのCコードにジャンプする前に、あと2つステップが残っています。それは BSS 領域の設定と”マジック”シグネチャの確認です。それでは、まずシグネチャの確認から始めましょう。

cmpl    $0x5a5aaa55, setup_sig
jne setup_bad

これは単純に、 setup_sig をマジックナンバー 0x5a5aaa55 と比べているだけです。この2つが等しくなければ、Fatal errorが表示されます。

マジックナンバーと等しくなれば、正しいセグメントレジスタとスタックを設定できたことが分かり、あとはBSSセクションさえ設定すればCコードにジャンプすることができます。

BSSセクションは、静的にアロケートされた初期化されていないデータを保存するために使われます。Linuxでは以下のコードを使い、このメモリ領域が必ず最初は空になるように設定します。

    movw    $__bss_start, %di
    movw    $_end+3, %cx
    xorl    %eax, %eax
    subw    %di, %cx
    shrw    $2, %cx
    rep; stosl

最初に __bss_start のアドレスが di に移動し、次に _end + 3 （+3は4バイトにアラインされている）のアドレスが cx に移動します。 eax レジスタは消去され（ xor 命令を使います）、BSSセクションのサイズ（ cx-di ）が計算されて cx の中に置かれます。それから、 cx は4（=語長）で除算され、 stosl 命令を繰り返し di が指すアドレスに eax の値（ゼロ）を格納して、 di は自動的に4ずつ増加します（これは cx がゼロになるまで続きます）。このコードの実際の効果は、 __bss_start to _end から始まり、メモリ内にある全ての語を介してゼロが書き出されるということです。

mainへジャンプする

これで準備完了です。スタックもBSSもそろったので、C言語の関数 main() にジャンプできます。

    calll main

main() 関数は arch/x86/boot/main.c. にあります。この働きについては、パート2で説明しましょう。

まとめ

これでLinux kernel internalsについて書いた本稿のパート1が終わります。ご質問やご意見がありましたら、ツイッター（ 0xAX ）や メール でお知らせいただくか、もしくはGithubで Issue を作成してください。本稿のパート2では、Linuxカーネルの設定で実行する最初のCコード、 memset 、 memcpy 、 earlyprintk の実装といったメモリルーチンの実装、そし初期のコンソールの初期化など、他にも多くを説明していく予定です。

リンク

• Intel 80386 programmer’s reference manual 1986
• Minimal Boot Loader for Intel® Architecture
• 8086
• 80386
• Reset vector
• Real mode
• Linux kernel boot protocol
• CoreBoot developer manual
• Ralf Brown’s Interrupt List
• Power supply
• Power good signal