panda's tech note

Advent Calendar 2018: advos

Day 2: ブートローダ（MBR）

今日からブートローダを作ります。

BIOSとUEFI

x86/x86-64のブートシーケンスは，コンピュータの起動とともにマザーボードに搭載されたROMなどから実行される Basic Input Output System (BIOS) または Unified Extensible Firmware Interface (UEFI) が二次記憶の特定の場所に記録されたプログラムを読み込み実行する。このプログラムからさらにOSをメモリに読み込み実行するため，ブートローダ や Initial Program Loader (IPL) と呼ばれる。

BIOSとUEFIはどちらも二次記憶などの周辺機器にアクセスするためのファームウェアを実装しており，ブートローダからそれらにアクセスするためのAPIを提供している。UEFIはBIOSの置き換えとして提案されたこともあり，より高度な機能を提供している。一方，BIOSはその名の通り，非常に基本的なI/O関係の機能だけを提供している。また，BIOSは16ビットモード（リアルモード）で起動する一方，UEFIは32ビットモード（プロテクテッドモード）で起動する。

BIOSのAPIは，後述するように割り込み（INT命令）により呼び出す。一方，UEFIは関数呼び出しとして定義されており，BIOSの割り込みベースのAPIと比較して高速に呼び出すことができる。UEFIの方が高機能でより多くの機能を実装しており，機能上はメリットしかないが，自分でブートローダを実装するにあたって，PEフォーマット（実行ファイルの形式）やFATファイルシステムなど，必要な知識やツールが増えるため，今回はまずBIOSを前提にブートローダを作成していくことにします。

余裕があれば，UEFIやネットワークブート（PXEブート）も後日扱うかもしれません。たぶんそんな余裕はないです。

BIOSからMaster Boot Record (MBR)の起動

BIOSは設定で指定したブートドライブからプログラムを読み込みます。ブートドライブがフロッピーディスク，HDD/SSD，USBフラッシュメモリなどの場合は，先頭1セクタ（512バイト）を読み込み，最後の2バイトがブートドライブであることを表すシグネチャ（0x55 0xaa）であることを確認し，ブートドライブであれば，ディスクの先頭1セクタ（512バイト）をメインメモリの0x7c00から0x7fffに読み込み，0x7c00からプログラムを実行していきます。この先頭の1セクタはMaster Boot Record（MBR）と呼ばれます。HDD/SSDやUSBフラッシュメモリの場合は，この先頭1セクタの後半にプログラム以外にもパーティションテーブルが配置されます。なお，CD/DVDはISO9660というフォーマットでMBR形式とは異なるので今回は扱いません。

パーティションテーブルを考慮するとMBRには多くても446バイトのプログラムしか配置できないため，BIOSから起動する場合は，ブートローダを別の領域に置き，MBRにはブートローダをメモリに読み込む最小限のプログラムを配置します。このMBRは，容量が限られていて16ビットモード（リアルモード）で書かないといけないので，アセンブリで書きます。個人的には64ビットモード（ロングモード）になってから高級言語（Cが高級かはここでは議論しない）を使うのが良いと思っています。

コンパイルとリンカ

MBRのプログラムは後述する通りsrc/boot/mbr.Sに書いています。これをコンパイルしてMBRに書き込むバイナリにするために以下のようなMakefileを書きました。

mbr: mbr.o
        $(LD) -N -T mbr.ld -o $@ $^

mbr.oはmbr.Sからコンパイルされたオブジェクトファイルです。今回はLinux上でコンパイルするのでELF形式のオブジェクトファイルを生成します。このMakefileはオブジェクトファイルをリンカ（ld）でmbrという単一のバイナリにします。mbr.ldはリンカオプションをまとめたもので以下の通りです。

OUTPUT_FORMAT("binary","binary","binary");
OUTPUT_ARCH(i386:x86-64);
ENTRY(start)

SECTIONS
{
  . = 0x7c00;
  .text : { *(.text) }
  .data : { *(.data) }
}

OUTPUT_FORMAT()はOUTPUT_FORMAT(デフォルト, ビッグエンディアン, リトルエンディアン)の出力を定義します。MBR，ブートローダではELFやPEなどのポータブルフォーマットではなくバイナリを吐くようにするため，binaryを指定します。OUTPUT_ARCH()は，出力のCPUアーキテクチャとしてi386:x86-64を指定します。ENTRY()ではプログラムのエントリポイント（0x7c00にあたる部分）を指定します。後述するmbr.Sのエントリポイントのラベルはstartなので，startを指定します。

SECTIONSでは，セクションの配置を指定します。MBRはメモリの0x7c00に配置されるので，. = 0x7c00で0x7c00から.textセクション，.dataセクションを配置し，オブジェクトファイルのリロケーションアドレスを確定させます。

上述のMakefileで生成したmbrはセクタの最後のブートシグネチャ（0x55 0xaa）がないだけでなく，サイズが小さすぎるため，QEMUの仮想ディスクとして起動できません。なので，以下のsrc/Makefileでブートシグネチャを追加し，1474560バイト（1.44MB）のディスクイメージにしています。

all:
        make -C boot mbr
        cp boot/mbr advos.img
        printf '\125\252' | dd of=advos.img bs=1 seek=510 conv=notrunc
        printf '\000' | dd of=advos.img bs=1 seek=1474559 conv=notrunc

MBRのプログラム

簡単なMBRのプログラムとして，BIOSの機能を使ってメッセージを表示するプログラムをGNUアセンブリで書きました。src/boot/mbr.Sに沿って説明をしようと思います。

まず最初の

#define VGA_TEXT_COLOR_80x25    0x03

はC言語の#defineと同じで，定数を定義します。

次に，

    .globl	start

は，ラベルstartを外部ファイルから参照可能にします。今回は上述したリンカからこのラベルを参照するので，.globl指定しています。

    .text
    .code16

で，テキストセクション（プログラム部）を開始し，リアルモード用の16ビットコードのアセンブリであることを明示します。

    cld		/* Clear direction flag (inc di/si for str ops) */

はストリング命令のdi/siの方向を減算方向にするフラグ（direction flag）をクリアします。BIOSからの起動時はフラグが未定なので，この命令を実行しておきます。

    cli

では，Interrupt Flagをクリアし，割り込みを無効にします。この後スタックをセットするため，ここで割り込みが発生するとスタックが壊れてしまう可能性があるためです。

    /* Setup the stack (below $start = 0x7c00) */
    xorw	%ax,%ax
    movw	%ax,%ss
    movw	$start,%sp

スタックをスタックセグメント0，スタックポインタをstartラベルの場所，即ち0x7c00に設定します。つまり，MBRのプログラムが0x7c00から上のメモリ領域に配置され，スタックはその下に延びていくようにします。メモリの中にはBIOSやシステムで使用している領域がありますが，0x7c00からしばらく下は空いているのでここをスタックに使います。具体的な使用可能メモリ領域は明日以降説明することになると思います。

    /* Reset data segment registers */
    movw	%ax,%ds
    movw	%ax,%es

このあとメッセージ表示でセグメントレジスタを使うのでデータセグメントを0に設定しておきます。

    sti

スタックのセットアップが終わったので，割り込みを有効にします。文字列の画面表示などはBIOSの機能を割り込み命令越しで使うので，割り込みは有効にする必要があります。

    /* Save drive information */
    movb	%dl,drive

BIOSからの起動時に，ブートドライブのBIOS内部でのドライブ番号（管理ID）が%dlレジスタに入っているので，これを.dataセクションのdriveラベルの場所に保存しておきます。今日はドライブにアクセスしませんが，この情報は明日以降，ブートローダを読み込むのに使います。

    /* Set the video mode to 16-bit color text mode */
    movb	$VGA_TEXT_COLOR_80x25,%al
    movb	$0x00,%ah
    int	$0x10

画面モードをVGAカラーテキストの80列25行モードにします。ディスプレイ関係のBIOSサービスは Video BIOS services として割り込み番号10番への割り込み（int $0x10）で提供されています。このページの後半にリストをまとめます。詳細はEmbedded BIOSTM 4.1などを参照するとどのようなサービス定義が定義されているかわかります。

    /* Display welcome message */
    movw	$msg_welcome,%ax
    movw	%ax,%si
    call	putstr

このコードでmsg_welcomeラベルで定義されたNULL-terminateされた文字列をディスプレイに表示します。putstrは後述しますがC言語のputs(%ds:%si)のようなものだと思ってください。msg_welcomeは以下のように定義しています。.ascizはNULL-terminate文字列を定義するディレクティブです。

msg_welcome:
    .asciz	"Welcome to advos\r\n\n"

    /* Test error message */
    movb	$0xab,%ah
    call	disk_error

こちらは後日ディスク読み込みなどを実装するにあたって，エラーメッセージをエラーコードとともに表示するルーチンのテストです。%ahにエラーコードを入れてdisk_errorを呼びます。disk_errorの中身は後述します。

halt:
    hlt
    jmp	halt

こちらは，HLT命令を無限に実行するループです。HLT命令は割り込みが来るまでCPUを停止させます。CLI命令で割り込みを禁止した後HLTすることもできますが，CPUや仮想マシンによっては，割り込み禁止状態でHLTすることを異常と判断することがあるため，ここではInterrupt FlagをセットしたままHLTを呼んでいます。

putstr: 文字列の表示

文字列の表示は以下のルーチンで定義しています。

/*
 * Display a null-terminated string
 * Parameters:
 *   %ds:(%si): Pointer to the string
 * Unpreserved registers: %ax
 */
putstr:
putstr.load:
    lodsb			/* Load %ds:(%si) to %al, then incl %si */
    testb	%al,%al
    jnz	putstr.putc
    xorw	%ax,%ax
    ret
putstr.putc:
    call	putc
    jmp	putstr
putc:
    pushw	%bx
    movw	$0x7,%bx
    movb	$0xe,%ah
    int	$0x10
    popw	%bx
    ret

%ds:(%si)から1文字ずつ読んで，INT 10h, AH=0Ehでテレタイプモードで書き込みます。 後述の通り，INT 10h, AH=0Ehの入力パラメータは%alに文字，%blに文字カラー（$0x7は白色），%bhにビデオページ番号（ここでは0）を取ります。アセンブリではCalling Conventionは自分で決められますが，ここでは%bxは呼び出し元で使う可能性を考えてPreserved registersとして，このルーチン内で書き換わらないようにputc内でスタックに退避しています。%alがNULL文字（ゼロ）になるとjnz putstr.putcが呼ばれなくなり，putstrルーチンから返ります（ret）。

disk_error: エラーメッセージの表示

エラーメッセージとエラーコードの表示は以下のルーチンで定義しています。

/*
 * Display the read error message (%ah = error codee)
 * Parameters:
 *   %ds:(%si): Pointer to the string
 * Unpreserved registers: %es, %ax, %di
 */
disk_error:
    pushw	%bx
    movb	%ah,%al
    movw	$error_code,%di
    xorw	%bx,%bx
    movw	%bx,%es
    call	hex8
    movw	$msg_error,%si
    call	putstr
    popw	%bx
    ret

前半は%ahのエラーコードをhex8によりerror_codeラベルのASCIIコード二文字（2バイト）に変換しています。後半はmsg_errorを表示しているだけです。msg_errorラベルの文字列定義は.ascii "Disk error: 0x"でNULL-terminateしていないため，putstrでerror_codeのNULL-terminateされた文字列の最後まで表示します。

エラーコードのASCIIコード変換

以下のコードがエラーコード（1バイト）をASCII二文字に変換するルーチンです。少し複雑なので，ここで詳解します。

/*
 * Convert %al to hex characters, and save the result to %es:(%di)
 * Parameters:
 *   %es:(%di): Pointer to the buffer to store the result (2 bytes)
 *   %al: Byte to be converted to hex characters
 * Unpreserved registers: %al, %di
 */
hex8:
    pushw	%ax
    shrb	$4,%al		/* Get the most significant 4 bits in %al */
    call	hex8.allsb
    popw	%ax
hex8.allsb:
    andb	$0xf,%al	/* Get the least significant 4 bits in %al */
    cmpb	$0xa,%al	/* CF=1 if %al < 10 */
    sbbb	$0x69,%al	/* %al <= %al - (0x69 + CF) */
    das			/* Adjust BCD */
    orb	$0x20,%al	/* To lower case */
    stosb			/* Save chars to %es:(%di) and inc %di */
    ret

以下は4ビットのバイナリデータをASCIIコードに変換するコードです。OSのブートローダなどでは一般的に用いられているアルゴリズムですが，少し特殊なのでここで詳しく説明します。

    andb	$0xf,%al	/* Get the least significant 4 bits in %al */
    cmpb	$0xa,%al	/* CF=1 if %al < 10 */
    sbbb	$0x69,%al	/* %al <= %al - (0x69 + CF) */
    das	           		/* Adjust BCD */

まず，このコードを理解するために，以下のASCIIコード表（16進数）を参照します。

30  0    31  1    32  2    33  3    34  4    35  5    36  6    37  7
38  8    39  9    3a  :    3b  ;    3c  <    3d  =    3e  >    3f  ?
40  @    41  A    42  B    43  C    44  D    45  E    46  F    47  G
48  H    49  I    4a  J    4b  K    4c  L    4d  M    4e  N    4f  O
50  P    51  Q    52  R    53  S    54  T    55  U    56  V    57  W
58  X    59  Y    5a  Z    5b  [    5c  \    5d  ]    5e  ^    5f  _
60  `    61  a    62  b    63  c    64  d    65  e    66  f    67  g

ここで0-9が30h-39h，Ah-Fhが41h-46hにマッピングされていることに注目します。ASCIIコードをc，4ビットの数値をxとすると，

c = x + 30h (if x <= 9)
c = x + 31h + 10h - Ah (if x > 9)

と表現できます。ここで注目するのは，x > 9のとき，x' = x + 10h - Ahとすることでx = Ah-Fh = 10-15はx' = 10h-15hとなります。このx'はxのBinary Coded Decimal (BCD)になっています。BCDは，10進数の各桁を16進数の4ビットずつに格納したものです。例えば，10進数の35は16進数の35hとして表します。x86のCPUにはBBCDの計算を行う命令が用意されており，上のコードではこれを応用しています。

BCD表現数をサフィックス_bcdで表すと，

c_bcd = x_bcd + 31_bcd - 1 (if x <= 9)
c_bcd = x_bcd + 31_bcd (if x > 9)

となります。x <= 9のときの-1の項をcmp $0xa,x命令のCF（x<10のときに1）で表すと，

c_bcd = x_bcd - 69_bcd - CF

と変形できます。これはアセンブリで

cmpb    $0xa,x
sbbb    $0x69,x_bcd
das

となります。SBB命令は第二引数から第一引数を引いて，CFがセットされている場合はさらに1を引く命令です。DAS命令は16進数での引き算結果を調整し，BCDにする命令です。ここでsbbb $0x69,x_bcdのx_bcdについて，CPU内の実装は下位4ビット目からボロー（桁の繰り下がり）があった場合に，AFフラグがセットされます。DAS命令はこのフラグと下位4ビットの値を参照して16進数での引き算の結果を調整します（AFがセットされている場合は上位4ビットからの繰り下がりがあるため下位4ビット部をさらに6を引く）。そのため，sbbb $0x69,x_bcdは，下位4ビットの引き算が9のため，x>9のときも下位4ビットがBCDと矛盾しないためsbbb $0x69,xと等価になります。よって，xを%alレジスタとすると以下のコードになります。

    cmpb    $0xa,%al
    sbbb    $0x69,%al
    das

Appendix: BIOSサービスの呼び出し

INT 10h: Video BIOS services

ここでは，INT 10hのサービス一覧をまとめます。

AH Description
00h Set video mode
01h Set cursor size
02h Set cursor position
03h Read cursor position
04h Read light pen position
05h Select video page
06h Scroll up window
07h Scroll down window
08h Read char/attr from screen
09h Write char/attr to screen
0Ah Write character to screen
0Bh Set color palette
0Ch Write pixel
0Dh Read pixel
0Eh Write teletype mode
0Fh Return video status
INT 10h, AH=00h: Set video mode

上記のコードで使用している画面モードの設定（INT 10h, AH=00h）について解説します。

  • 入力パラメータ
    • AL: 画面モード（Video Mode）
      • 00h: Text mode, 16 colors, 40x25, 320x200
      • 01h: Text mode, 16 colors, 40x25, 320x200
      • 02h: Text mode, 16 colors, 80x25, 640x200
      • 03h: Text mode, 16 colors, 80x25, 640x200
      • などがあります。Ref. VGADOC
  • 返り値パラメータ
    • AL: 設定後の画面モード
INT 10h, AH=0Eh: Write teletype mode

上記のコードで使用しているテレタイプモードでの書き込み（INT 10h, AH=0Eh）について解説します。

  • 入力パラメータ
    • AL: 書き込む文字
    • BL: 文字カラー
    • BH: ビデオページ番号
  • 返り値パラメータ
    • なし

まとめと明日の予定

今日はBIOSの機能を使って簡単な文字列の表示プログラムを書きました。明日はMBRからブートローダの読み込みをしていきたいと思います。