memtest64 開発メモ

memtest86 という有名なメモリチェッカがあるんですが、これ 64bit に対応していません。

PAE には対応しているので、64GB までのメモリチェックは出来るんですが、お陰で結構複雑なコードになってるし、メモリアクセスは 32bit なので遅い... ということで、64bit 移植に挑戦してみようと思いました。

ところがブートローダーってまともに書いたことが無いので、さっぱりわかりません。ある程度まとまってきたので、自分用に調査メモを残します。

全般的な情報

Intel® 64 and IA-32 Architectures Software Developer Manuals
リファレンスといえば Intel です。 AMD64 なんですが、ドキュメントは Intel のほうが親切な気がするので、こっちを読んでます。迷ったらこれ、です。

Linux i386 Boot Code HOWTO
i386 向けですが、Linux のブートコードの解説です。
memtest86 もブートローダーは Linux のを借りているので、勉強になります。

Linux のブートローダー
memtest86 のブートローダーの元です。
バージョンが変わってるのでかなり変わってますが、参考になります。

GRUB
GNU のブートローダーです。
ライセンスは GPLv3 なので、Linux 関係のコードと混ぜられませんが、勉強にはなります。

Entering Long Mode Directly
Long mode に入るには protected mode を経由しないとだめなんですが、手順を一部省略する方法が書かれています。
どれぐらい安全なのかはわかりませんが...

メモリ情報

メモリ情報は、OS が起動している状態だと OS がよしなにやってくれますが、起動した状態だとどの物理アドレスが使えるのかもわかりません。

Detecting Memory (x86)
メモリ情報は BIOS の E820 というコールを使うのがよさそうです。
2002年以降の BIOS だと使えるようなので、x64 対応の CPU が載ってるマシンだとほぼ問題ないでしょう。

x86-64 Page table structure
Wikipedia のページテーブル関係の記述です。プログラマ向けじゃないので情報量は少ないですが、あらすじはわかります。

Memory Map (x86)
典型的なメモリマップが載ってます。E820 で情報取るまでは決め打ちでメモリを使うしかないので、参考にします。

その他メモ

• E820 は long mode からは呼べないので、それまでにマップを取得する必要がある。
• startup_32 と startup_64 というエントリが結構キーポイントっぽい。

Ackermann function

アッカーマン関数という関数があります。
バカ正直に計算しようとするとすぐ計算量が膨大になり、計算できなくなるたぐいの関数です。

これをアセンブリでバカ正直に計算させるコードを書いてみました。階乗を計算させるコードのおまけ付きです。

実際に実行させたところ、ack(3, 12) あたりになるとスタックがあふれました。
スタックサイズを調整すればもうちょっといけると思います。

使用した高速化のテクニック

• 末尾再帰を CALL から JMP に置き換え
• TEST+JE でmacro fusion できる命令形式にした
• INC / DEC を ADD / SUB に置き換えて、フラグレジスタの依存関係を解消
• MOV RDX, 1 を MOV EDX, 1 にして命令長を短縮

    .code

ack PROC public

    ; RCX = m, RDX = n
    TEST    RCX, RCX
    JE      m_zero

    TEST    RDX, RDX
    JE      n_zero

    PUSH    RCX
    SUB     RDX, 1
    CALL    ack
    POP     RCX
    SUB     RCX, 1
    MOV     RDX, RAX
    JMP     ack

n_zero:
    MOV     EDX, 1
    SUB     RCX, 1
    JMP     ack

m_zero:
    MOV     RAX, RDX
    ADD     RAX, 1
    RET

    ack ENDP

factorial PROC public
    
    MOV     EAX, 1
    CMP     RCX, 1
    JLE     f_ret

f_loop:
    IMUL    RAX, RCX
    SUB     RCX, 1
    CMP     RCX, 1
    JNLE    f_loop

f_ret:

    RET

    factorial ENDP

    END

一応 C で書いた以下のコードよりは、3割ぐらい速いようです(Visual C++ 2010 で /O2 としてコンパイル)。階乗は微妙に速いだけでほとんど変わりませんでした。CPU は Penryn ベースの Core2 Duo です。

int64_t factorial_c(int64_t n)
{
    int64_t r = 1;
    while(n > 1) r *= n--;
    return r;
}

int64_t ack_c(int64_t m, int64_t n)
{
    return m == 0 ? n + 1 : n == 0 ? ack_c(m - 1, 1) : ack_c(m - 1, ack_c(m, n - 1));
}