無限遠まで突撃中

ネット日記書きの徒然。

酒に酔った

プレモル500ml缶で酔うお手軽ボディは大変よいものでございます、突撃隊です。

疲れからか酒をコンビニで買ってぐいっといっていい気分になったからこんな記事を書いているわけでございます。

将来

どうするんでしょう。 OSいじって就職できるとあんまり思えないし、なんかWebのやつやんなきゃいけないかなあ。

できれば低レイヤ就職したいんですがどうしたもんですかね。

学業

GPAは破滅しているのでどうするか。

院進は今の所したいなあと思っているのですが、推薦はもらえなさそうなので、普通に大学院入試を受ける必要がありそうです。

そもそも親氏は許してくれますかね? 二浪もしているので留年したら割と行かせてもらえなそう。

自由研究

自作OSは最近調子よくて、なんかバリバリ実装しています。

コードレビューしてもらいながら開発しているとたいへん効率がよく、効率がいいです。 fork()とか実装しちゃってるもんね。

ファイルシステム実装までは行きたいですね。

まとめ

以上がお気持ちです。

自作OSのmallocを大きなバイト数でアライメントできるようにしたい

こんにちは、突撃隊です。

コロナで皆さん大変ですが、自分は作業がはかどっています。 なんとも皮肉なもんです。

自作OSのmallocで大きなアライメントを取りたい

タイトルのとおりです。 4KBとか1MBとかのアライメントを取りたいねという話です。

自分の自作OS「minOSv2」では動的メモリ確保にK&R mallocを実装しています。

github.com

mallocの基本構造は らじうむ覚書さんの K&R Malloc解説 を読むと良いです。

以下の文章ではK&R mallocの基本概念はわかっているとします。

mallocのヘッダサイズと16バイトアライメント

minOSv2のmallocヘッダは以下のように定義されています。

minOSv2/mm.h at feature-ext2 · Totsugekitai/minOSv2 · GitHub

struct malloc_header {
    struct malloc_header *next;
    uint64_t size; // This param's unit is sizeof(struct malloc_header).
};

ポインタ型と uint64_t 型の構造体なので、構造体のサイズは16バイトです。

K&R mallocはヘッダのサイズを1単位として扱うので、つまりmallocの単位としては16バイトずつの確保になります。

リンカスクリプトでヒープ領域をアライメントしてあげると、mallocで確保された領域は自動的に16バイトアライメントされていることになります。

16バイトより大きなアライメントを取るには

リンカスクリプトで調整してあげることによって16バイトアライメントが自動的になされることがわかりました。

しかし16バイトより大きいアライメントを取りたいときがあります。

そう、 ハードウェアの操作 をするときです。

AHCIの操作

この前までAHCIデバイスドライバを書くために奮闘していました。

totsugekitai.hatenablog.com

totsugekitai.hatenablog.com

AHCIデバイスドライバを書く際には128Bアライメントや4KBアライメントでメモリを確保する必要があります。

mallocくんは16バイトアライメントは守ってくれますが、それより大きなアライメントは対応していませんので、なんとかしてやる必要があります。

大きなアライメントに対応したメモリ確保をする関数を作る

まず、アライメントを調整するために何バイトmallocする必要があるでしょうか。

size バイトを al バイトでアライメントするときを考えると、 size + al バイト確保してやり、この確保したメモリ上で開始アドレスをいじってやればアライメントを守ったメモリが確保できそうです。

つまりこうすれば解決ですね。

void *not_aligned_allocate = malloc(size + al);
void *aligned_allocate = align(not_aligned_allocate, al);

void *align(void *addr, int align)
{
    uint64_t addr_num = (uint64_t)addr;
    return (void *)(addr_num + (align - (addr_num % align)));
}

freeができない

しかしこのままでは問題があります、freeができないのです。

というのもK&R Mallocのfreeは、引数で受け取ったアドレスの一個手前にmallocヘッダがあると仮定した処理をしています。

今私たちはmallocしたときに返ってきたアドレスを何バイトか後ろにずらして使っていますので、こうすることはできないのです。

free(aligned_allocate);

何バイトずらしたか情報をもたせたい

何らかの手を考える必要があります。

私たちが知りたいのは何バイトずらしたかという情報です。 この情報さえあれば、大きくアライメントされていても元に戻すことができます。

ここで考えてみると、mallocは16バイトごとにメモリを確保し、そして16バイトより大きくアライメントされているときには、 最低でも16バイトは元の確保したメモリの先頭アドレスからずらしているはずです(ここでは2の累乗バイトアライメントを考えています)。

ということはアライメントした後のアドレスからアドレスが小さい方向に16バイトは何にも使われないことになります。

そういうわけでここに情報を書き込んじゃいましょう。

こちらがソースコードになります。

void *kmalloc_alignas(int size, int align_size)
{
    void *tmp = kmalloc(size + align_size);
    if (is_aligned(tmp, align_size)) {
        return tmp;
    } else {
        void *true_ptr = align(tmp, align_size);
        uint64_t diff = (uint64_t)true_ptr - (uint64_t)tmp;
        putsn_serial("malloc align diff: ", diff);
        ((uint64_t *)true_ptr)[-1] = diff;
        strcpy(&((char *)true_ptr)[-16], "ALIGNED");
        return true_ptr;
    }
}

void kfree_aligned(void *ptr, int align_size)
{
    if ((unsigned long)align_size <= sizeof(struct malloc_header)) {
        kfree(ptr);
    } else {
        if (strcmp(&((char *)ptr)[-16], "ALIGNED") == 0) {
            uint64_t diff = ((uint64_t *)ptr)[-1];
            void *true_ptr = (void *)((char *)ptr - diff);
            putsn_serial("kfree addr diff: ", diff);
            putsp_serial("kfree true free address point: ", true_ptr);
            kfree(true_ptr);
        } else {
            kfree(ptr);
        }
    }
}

kmalloc_alignasとkfree_alignedという関数を作りました。

まずkmalloc_alignasでは、kmallocで確保したメモリ領域のアライメントがあっているかチェックし、あっていたらそのままリターンします。 あっていなかったら、アライメントした後のアドレスの前8バイトにアライメントのために移動させた差の値を書き込みます。

またアライメントした後のアドレスの前16バイトから前9バイトにかけて "ALIGNED" という識別子を置きました。

kfree_alignedでは、まずアライメントサイズを確認し、16バイト以下だったらずらされていないので普通にfreeします。

16バイトより大きい場合、アライメントのためにずらされているかどうかを "ALIGNED" の識別子があるはずの部分を見て判断します。 識別子があったらずらされていると判断し、アライメントのためにどれだけずらされたかを差の値があるはずの部分を読んで計算し直し、mallocヘッダが読み込まれるようにアドレスを調整してからfreeします。

いかがでしたか?

アライメントはたいへんですね、そういえばアライメントの話だとこんな記事もあります。

uchan.hateblo.jp

いや〜アライメントはたいへんですね、気をつけましょう。

AHCI奮闘記 - Read/Write編

AHCIの読み出し書き込みに成功した

こんにちは、突撃隊です。 AHCIを用いたSATAディスクへの読み書き(QEMU上ですが)が無事成功したので、メモを残しておこうかと思います。

実機確認はまだできていませんので話半分にお願いします。 実機確認できました!

以下の記事 totsugekitai.hatenablog.com

で解説されている初期化を行ったものとして以降は解説していきます。

また、一挙一足説明していると時間が足りないので、そこらへん足りない部分は自分のリポジトリを見て下さい。

github.com

仕様書の該当部分を読む

AHCIの仕様書の 5.5 System Software Rules に記述されているので、それのとおりやればできます。

でも落とし穴が多いので解説します。

まずはポートのセッティング

ポートの設定をまずはします。 ここは仕様書の 5.5 には載っておらず、実装の上で必要になったので追加していることをお伝えします。

以下のような処理を行います。

static inline void start_cmd(HBA_PORT *port)
{
    puts_serial("start_cmd start\n");
    port->cmd &= 0xfffffffe;    // PxCMD.ST = 0
    // wait until CR is cleared
    while (port->cmd & 0x8000) { asm volatile("hlt"); }

    // set FRE and ST
    port->cmd |= 0x10;
    port->cmd |= 0x01;
    puts_serial("start_cmd end\n");
}

最初に PxCMD.ST をクリアします。 するとAHCIの状態が遷移して PxCMD.CR が0にクリアされるので、それを待ちます。

それが終わったら、また PxCMD.ST を上げ直しますが、 PxCMD.FRE を上げてから PxCMD.ST を上げます。 順番が大事です。

コマンドをつくる

次にコマンドと呼ばれるものを作ります。 コマンドをAHCIコントローラに送ることによって、AHCIコントローラに命令を送ることができます。

それでは手順を記します。 ATAPIコマンドの部分の記述は省略します。

  1. ポートの空いているスロットを見つける
    • 空いているスロットは、 PxCIPxSACT の両方がクリアされているビットに対応するスロット
    • 空いているスロットのことを以下では pFreeSlot とする
  2. メモリ上にcommand FISを構築する
    • 開始アドレスは PxCLB[CH(pFreeSlot)]:CFIS
    • command typeも指定する
  3. PxCLB[CH(pFreeSlot)] にcommand headerを構築する。条件は以下の通り
    • PRDTL はPRD tableの数を格納する
    • CFL はCFIS領域のサイズを指定する
    • A ビットはクリアする(ATAPIコマンド識別ビット)
    • W ビットはwrite処理ならセット、read処理ならクリアする
    • P ビットはオプショナル(今回はやめておく)
  4. PxCI.CI(pFreeSlot) のビットを立てて、コマンドがアクティブであることをAHCI側に通知する

以上の処理を以下のコードのようにまとめました。 build_command が本体です。

static int find_free_cmdslot(HBA_PORT *port)
{
    uint32_t slots = (port->ci | port->sact);
    for (int i = 0; i < 32; i++) {
        if ((slots & 1) == 0) {
            return i;
        }
        slots >>= 1;
    }
    puts_serial("Cannot find free command list entry\n");
    return -1;
}

#define CMD_TBL_BASE 0x10010000
static inline void build_cmd_table(CMD_PARAMS *params, uint64_t *table_addr)
{
    memset((void *)table_addr, 0, 0x80 + 16 * 65536); // zero clear
    HBA_CMD_TBL *table = (HBA_CMD_TBL *)table_addr;

    // build CFIS
    if (params->fis_type == 0x27) { // if Register H2D
        FIS_REG_H2D *h2dfis = (FIS_REG_H2D *)table_addr;
        h2dfis->fis_type = 0x27;    // H2D FIS type magic number
        h2dfis->c = 1;              // This is command
        // command type is referenced in ATA command set
        h2dfis->command = params->cmd_type;
        // device
        //h2dfis->device = 0xe0;
        h2dfis->device = 1 << 6;
        // LBA
        h2dfis->lba0 = (uint8_t)(((uint64_t)(params->lba) >>  0) & 0xff);
        h2dfis->lba1 = (uint8_t)(((uint64_t)(params->lba) >>  8) & 0xff);
        h2dfis->lba2 = (uint8_t)(((uint64_t)(params->lba) >> 16) & 0xff);
        h2dfis->lba3 = (uint8_t)(((uint64_t)(params->lba) >> 24) & 0xff);
        h2dfis->lba4 = (uint8_t)(((uint64_t)(params->lba) >> 32) & 0xff);
        h2dfis->lba5 = (uint8_t)(((uint64_t)(params->lba) >> 40) & 0xff);
        // block count
        h2dfis->countl = (uint8_t)((params->count >> 0) & 0xff);
        h2dfis->counth = (uint8_t)((params->count >> 8) & 0xff);
    } else {
        puts_serial("fis type error\n");
        return;
    }

    // build PRD Table
    // 8 KB (16 sectors) per PRD Table
    // 1 sectors = 512 KB
    uint16_t count = params->count;
    int prdtl = (int)((params->count - 1) >> 4) + 1;
    uint8_t *buf = (uint8_t *)params->dba;
    int i;
    for (i = 0; i < prdtl - 1; i++) {
        table->prdt_entry[i].dba  = (uint32_t)buf;
        table->prdt_entry[i].dbau = 0;
        table->prdt_entry[i].dbc = 8 * 1024 - 1;
        table->prdt_entry[i].i = 1; // notify interrupt
        buf += 8 * 1024; // 8K bytes
        count -= 16; // 16 sectors
    }

    // Last entry
    table->prdt_entry[i].dba = (uint32_t)buf;
    table->prdt_entry[i].dbc = (count << 9) - 1;
    table->prdt_entry[i].i = 1;
}

static inline void build_cmdheader(HBA_PORT *port, int slot, CMD_PARAMS *params)
{
    HBA_CMD_HEADER *cmd_list = ((HBA_CMD_HEADER *)port->clb + slot);
    memset((void *)cmd_list, 0, 0x400);
    cmd_list->ctba = (uint32_t)CMD_TBL_BASE;
    cmd_list->ctbau = 0;
    cmd_list->prdtl = (uint16_t)(((params->count - 1) >> 4) + 1);
    cmd_list->cfl = params->cfis_len;
    cmd_list->w = params->w;
}

static inline void notify_cmd_is_active(HBA_PORT *port, int slot)
{
    port->ci |= 1 << slot;
}

static inline void build_command(HBA_PORT *port, CMD_PARAMS *params)
{
    int slot = find_free_cmdslot(port);
    // step 1:
    // build a command FIS in system memory at location PxCLB[CH(pFreeSlot)]:CFIS with the command type.
    build_cmd_table(params, (uint64_t *)CMD_TBL_BASE);
    // step 2:
    // build a command header at PxCLB[CH(pFreeSlot)].
    build_cmdheader(port, slot, params);
    // step 3:
    // set PxCI.CI(pFreeSlot) to indicate to the HBA that a command is active.
    notify_cmd_is_active(port, slot);

    puts_serial("build command is over\n");
}

1つの関数で1つのステップを処理しています。

コマンドテーブルの開始アドレスは面倒だったので決め打ちにしました。 ここは malloc などで確保してやったほうがお行儀が良さそうです。 後々直したいと思います。

コマンド特有のパラメータ(例えば W ビットが立っているかどうか)は CMD_PARAMS 型にまとめました。

さて

これでAHCIがよろしくやってくれて、コマンドが実行されます

最後は後処理を忘れずに

最後の終了処理を忘れると痛い目を見るので、しっかり後片付けをしましょう。 では手順を説明します。

  1. IS.IPS を監視して、割り込みが来たことを確認
  2. 対応するポートの PxIS レジスタを確認し、正常な割り込みが来ているか確認
  3. 正常だったら PxIS をクリアする
  4. IS.IPS をクリアする
  5. AHCI側が PxCI をクリアするのを待つ

以上の処理をこんなふうに書いてみました。

static inline void wait_interrupt(HBA_PORT *port)
{
    puts_serial("while waiting interrupt\n");
    while (port->is == 0) {
        asm volatile("hlt");
    }
    puts_serial("interrupt comes\n");
}

static inline void clear_pxis(HBA_PORT *port)
{
    port->is |= port->is;
    puts_serial("while clear PxIS\n");
    while (port->is) {
        asm volatile("hlt");
    }
    puts_serial("clearing PxIS is over\n");
}

static inline void clear_ghc_is(int portno)
{
    HBA_MEM_REG *ghc = (HBA_MEM_REG *)abar;
    ghc->is |= 1 << portno;
    puts_serial("while clear IS.IPS\n");
    while (ghc->is) {
        asm volatile("hlt");
    }
    puts_serial("clearing IS.IPS is finished\n");
}

static inline void wait_pxci_clear(HBA_PORT *port)
{
    puts_serial("wait PxCI\n");
    while (port->ci) {
        asm volatile("hlt");
    }
    puts_serial("wait PxCI end\n");
}

いくつか注意点を述べます。

PxIS をクリアする方法は、 立っているビットに対して1を書き込んでAHCI側がクリアするのを待つ ことです。 これは仕様書にも載っています。 0クリアするために1を書き込むというのは感覚的にむむっ?と来ましたが、まあそういうもんだと思って従います。 IS.IPS のクリア方法も同様ですので承知しておいて下さい。

また、AHCI側が PxCI をクリアするまで待つというのも意外な落とし穴ポイントです。 クリアする前に次のコマンドをアクティブにしてしまうとエラーがおきてしまいますので注意です。

以上をまとめてRead/Write処理を書く

ということでまとめです。 以下のようなコードになりますた。

int ahci_read_test(HBA_PORT *port, int portno, uint64_t start, uint16_t count, uint16_t *buf)
{
    start_cmd(port);
    CMD_PARAMS params;
    params.fis_type = 0x27;
    params.cmd_type = READ_DMA_EXT;
    params.cfis_len = 5;
    params.lba = (uint64_t *)start;
    params.count = count;
    params.dba = (uint64_t *)buf;
    params.w = 0;
    build_command(port, &params);
    wait_interrupt(port);
    clear_pxis(port);
    clear_ghc_is(portno);
    wait_pxci_clear(port);
    return 1;
}

int ahci_write_test(HBA_PORT *port, int portno, uint64_t start, uint16_t count, uint16_t *buf)
{
    start_cmd(port);
    CMD_PARAMS params;
    params.fis_type = 0x27;
    params.cmd_type = WRITE_DMA_EXT;
    params.cfis_len = 5;
    params.lba = (uint64_t *)start;
    params.count = count;
    params.dba = (uint64_t *)buf;
    params.w = 1;
    build_command(port, &params);
    wait_interrupt(port);
    clear_pxis(port);
    clear_ghc_is(portno);
    wait_pxci_clear(port);
    return 1;
}

ahci_read_test では、 portno 番のポートで作業します。 SATAstart 番地から count セクタ分を読み出して、メモリ上の buf 番地へコピーします。

ahci_write_test では、メモリ上の buf 番地からデータを読み出して、SATAstart 番地から count セクタ分だけ書き込みます。

これで読み書きができると思います。 自分はできました。

AHCI奮闘記 - 初期化編

こんにちは、突撃隊です。 最近いじっているAHCIというデバイスについて、な、な、なんと 初期化 が無事終了したので知見を共有したいと思います。

AHCIとはなんぞや

Advanced Host Controller Interface(AHCI)とは、SATAのデバイスコントローラです。 SATAをいい感じに触るためのインターフェースを提供してくれます。

初期化の手順について

しっかり初期化をしないとほとんど使い物にならないかもしれません。 ちゃんと仕様書を読んでしっかり初期化をしましょう。

仕様書の該当箇所

AHCI Specification ver 1.3 では、 10.1.2 System Software Specific Initialization にソフトウェアプログラマがやるべき初期化が書かれています。

初期化手順をまとめた

自分なりにやるべき処理をまとめました。

初期化処理メモ(上から順番)

  • 最初にリセットをしたほうがいいかもしれない
    • リセットはGHC.AE = 1にした後、GHC.HR = 1にしてしばらく待つ
  • PIレジスタを見て実装されているポートを探す
    • 以下の処理はすべて実装されているポートにのみ対して行う
  • ソフトウェア側でPxCMD.STを0にセットしハードウェアがPxCMD.CRを0にするのを待つ
  • 最低500msくらいは待つ
  • (PxCMD.FREが1だった場合、これを0にしてハードウェアがPxCMD.FRを0にするのを待つ(最低500ms))
  • CAP.NCSを読んで対応スロットを探す
  • 各対応スロットにおいて、PxCLBとPxFBのぶんのメモリを確保して0で埋める
  • PxFBのメモリ領域を確保した後、PxCMD.FREを1にする
  • 各対応スロットに対して、PxSERRをクリアする。ビットに'1s'を書き込んでクリアする
  • PxISをクリアした後、IS.IPSをクリアする(順番が重要)
  • PxIEレジスタをenableにする。またGHC.IEも1にセットする

(必要なら追加の初期化をする、その際の注意)

  • バイスが動いている間は、PxCMD.STは1にセットしようとしない
    • 具体的には、PxTFD.STS.BSY=0,PxTFD.STS.DRQ=0,PxSSTS.DET=3hのときである
  • PxTFDレジスタをenableにするために、PxSERR.DIAG.Xは0にクリアされてなければならない

自分の自作OSではどうなっているか

QEMU上で動かしています。

初期化直後は以下のようなフラグの状態です。 多分正常だと思います。

status of Generic Host Control
cap: 0x00000000c0141f05
ghc: 0x0000000080000002
is: 0x0000000000000000
pi: 0x000000000000003f
vs: 0x0000000000010000
ccc_ctl: 0x0000000000000000
ccc_pts: 0x0000000000000000
em_loc: 0x0000000000000000
em_ctl: 0x0000000000000000
cap2: 0x0000000000000000
bohc: 0x0000000000000000

status of HBA Port 0
clb: 0x0000000010000000
clbu: 0x0000000000000000
fb: 0x0000000010008000
fbu: 0x0000000000000000
is: 0x0000000000000000
ie: 0x00000000fdc000ff
cmd: 0x0000000000004016
tfd: 0x0000000000000130
sig: 0x0000000000000101
ssts: 0x0000000000000113
sctl: 0x0000000000000000
serr: 0x0000000000000000
sact: 0x0000000000000000
ci: 0x0000000000000000
sntf: 0x0000000000000000
fbs: 0x0000000000000000

なぐり書きなので

また随時更新します。

Windows updateかけたらrEFIndからArch Linuxが起動できなくなったのをなんとか直した

発端

自分のPCはrEFIndを使ってWindows 10とArch Linuxデュアルブートしているのですが、Windows updateをかけたらEFI領域を見事にぶっ壊されました。 なんやかんやで解決したので今後のためにも自分が行った解決方法を記しておきます。

症状

Windows updateをかけたあとrEFIndから vmlinuz-linux を起動しようとすると

Invalid loader file!
Error: Not Found while loading vmlinuz-linux

* Hit any key to continue *

こんな感じのエラーが。

解決方法

vmlinuz-linux がなんか知らんがおかしいらしく、起動しないので、Arch Linuxのインストールメディアを用いる。 あのArchLinuxInstallBattleに使うやつです。

おなじみコマンド。 sd{X1} とかは自分の環境にあったやつに置き換えてください。

# mount /dev/sd{X1} /mnt
# mount /dev/sd{X2} /mnt/boot
# arch-chroot /mnt

これでとりあえずLinuxに入る。

そして ip コマンドとか iw コマンドとか使ってネットにつないでください。 Free-Wifiがおすすめです( wpa_supplicantCLIむずすぎない?)。

そしたら vmlinuz-linux を更新します。

# pacman -S linux

これで vmlinuz-linux はOK。

これでいいかと思ったらrEFInd君が探してくる vmlinuz から起動しようとしたら、

mount: /new_root: wrong fs type, bad option, bad superblock, on /dev/sda2, missing codepage or helper program, or other error

今度はbtrfs君が死んでいます(いや知らんが…)。

rEFIndの設定を見直して手動でブートディスクを指定します。

/boot/EFI/refind/refind.conf をこんな感じに。

menuentry Arch {
    icon     /EFI/refind/icons/os_arch.png
    volume   "Arch"
    loader   /vmlinuz-linux
    initrd   /initramfs-linux.img
    options  "root=/dev/sd{X1} ro"
    submenuentry "Boot using fallback initramfs" {
        initrd /initramfs-linux-fallback.img
    }
    submenuentry "Boot to terminal" {
        add_options "systemd.unit=multi-user.target"
    }
    #disabled
}

loaderinitrdvmlinuz-linux があるファイルシステムのルートディレクトリからの相対パスにするらしい。 これ豆知識ね。 あと /refind_linux.conf があるとそっちの設定が読み込まれちゃうので refind_linux.conf.old とか適当にリネームしとく。

これでrEFIndの画面からArch Linuxのアイコンのやつを選択して起動!

起動したわw

まとめ

(大事なレポートや論文の提出間近にWindows updateは)してはいけない(戒め)。

大きく振り返って

この記事は coins Advent Calendar 2019 23日目の記事です。 22日目はわかめさんの 天久保周りの飯屋 でした。

早いものでもう2019年が終わろうとしています。 みなさんは有意義な一年にできたでしょうか? 自分は今年は色々やった年だったので振り返りを書こうかと思います。

1 - 3月

前半はなんかあんまり良く覚えていません。 色々なことに手を出して撃沈していたような気がします。

春休みに入ると暇になったので自作OSを始めました。

30日でできる! OS自作入門

30日でできる! OS自作入門

この本をやるぞと決めて、一日一章こつこつやりました。

実は購入自体は2018年にしていたのですが、何回かやり始めては挫折するを繰り返していたので、そろそろやりきりたいと思って気合を入れてやりました。 これが4回目の挑戦でした。

途中まで理解したことをブログにまとめていたのですが、大変だったのでやめました。

無事春休み中にやり切ることができました。

その後は64bit環境での自作OSをはじめました。

4 - 5月

セキュリティキャンプ2019全国大会 の募集が始まりました。 自作OSコースがあったので応募してみました。

応募用紙です。

github.com

調子に乗って サイボウズラボユース にも自作OSを作るというテーマで応募しました。

6 - 7月

なんとセキュリティキャンプとラボユースのどちらも選考を通過していました。 セキュリティキャンプ当日に向けて自作OSをガリガリ書く日々が始まりました。 ほぼ毎日3~4時間位はOSの資料を読んだり、コードをウンウンうなりながら書いていたと思います。

8月

セキュリティキャンプに行きました。 詳細な様子は以下です。

totsugekitai.hatenablog.com

大変楽しかったです。

またラボユース合宿にも行きました。温泉宿で3日間の合宿でした。 合宿中はPICの設定で時間を浪費したのが痛かったです。 温泉は大変気持ちよかったです。

9月

まだ夏休みが続いていましたが、体調が優れず、ほとんど活動ができませんでした。 夏休み前半に少し飛ばしすぎたのかもしれません。。。

10 - 12月

体調が戻ったので活動を再開しました。 自作OSの方もマルチタスクやメモリアロケータなどができ、だんだん形になってきていい感じでした。

まとめ

振り返ってみると、この一年は自作OSのことしかやってないですね。 とくに飲み会とか恋愛とか、大学生らしいことをほとんどやってないのですが、なんか楽しかったのでOKです。 (ま、自作OSはまとまった時間がないと難しいので、それが大学生らしいことということで)

来年度は

何やろうかなと悩んでいますが、候補は以下の2つ。

  • 自作コンテナ(DockerとかLXDとか、そういうやつ)
  • BitVisorを用いたベアメタルプログラミング向けデバッグ環境の作成

自作コンテナはDockerのしくみが知りたくなったからです。 しくみが知りたくなったら自作するのがいいかなと思います。

BitVisorの方は、BitVisor Summitという勉強会にお邪魔したときに、品川先生が誰かやってくれと言っていたのでやりたいなと思いました。 (ベアメタル下のデバッグ環境は自作OSをするときにも役立ちますしね!)

あとは本をもうちょっと読みたいですね。

自作OSでマルチタスクやった

この記事は coins Advent Calendar 2019 3日目の記事です。

この記事は WORDIAN Advent Calendar 2019 3日目の記事です。。

この記事は OS-CPU Advent Calendar 2019 3日目の記事です。。。

師走の挨拶

どうもこんにちは、突撃隊です。

64bit自作OS「minOS」をちまちま作っとるのですが、11月でついにマルチタスクを実装できたので解説します。

github.com

設計

スレッドかプロセスか

OSのタスク単位としてとりあえずスレッドを実装することにしました。 プロセスはメモリ空間を分離しなくてはいけないので、その分コーディングが大変だからです。 スレッドならスタックを用意してあげるだけなので簡単簡単。

thread 構造体

スレッドごとの構造体はこんな感じにしてみました。

struct thread_func {
    void (*func)(int, char**);
    int argc;
    char **argv;
};

enum thread_state {
    RUNNABLE,
    SLEEP,
    DEAD
};

struct thread {
    uint64_t *stack;
    uint64_t rsp;
    // uint64_t rip;
    struct thread_func func_info;
    enum thread_state state;
    int index;
};

struct thread ですが、上から順に

  1. スレッドのスタック領域の開始アドレス
  2. スレッドごとのスタックポインタ
  3. スレッドで実行する関数の情報
  4. スレッドの状態
  5. スレッドキューに登録した際のインデックス

です。

順番に解説していきます。

スレッドのスタック

自作の malloc 関数を用いてスタック領域を確保します。 大きさは 0x1000 = 4kB としています。

malloc 関数のソースコードはこちら。

https://github.com/Totsugekitai/minOS/blob/develop/kernel/mm/memory.c

スレッドごとのスタックポインタ

汎用レジスタはスタックに push しますが、スタックポインタは構造体に持たせるほうがやりやすそうです。

スレッドで実行する関数の情報

関数ポインタとその引数を受け取ります。

スレッドの状態

RUNNABLE SLEEP DEAD の3種類を用意しておきました。

スレッドキューに登録した際のインデックス

minOSではスレッドのキューはただの配列です。 スレッドの削除時に配列に登録したときのインデックスが必要になるのでパラメータとして持たせてあります。

どのタイミングでスレッド切り替えをするか

タイマ割り込みのタイミングでスレッド切り替えをすることにしました。 タイマ割り込みの何回かに一回にスケジューラを呼び出してタスクを切り替えます。

coinsLT#110で話したときの資料が詳しいです。

docs.google.com

実装

今回のキモはスレッドのスタックの初期化処理とスレッドを切り替える瞬間の処理です。

スタックの初期化処理

/** スレッドの生成
 * thread構造体の初期化とスタックの初期化を行う
 */
struct thread thread_gen(void (*func)(int, char**), int argc, char **argv)
{
    struct thread thread;

    thread.stack = (uint64_t *)minmalloc(STACK_LENGTH);
    thread.rsp = (uint64_t)(thread.stack + STACK_LENGTH);
    thread.rip = (uint64_t)thread_exec;
    thread.func_info.func = func;
    thread.func_info.argc = argc;
    thread.func_info.argv = argv;

    put_str_num_serial("thread stack bottom: ", (uint64_t)thread.stack + STACK_LENGTH);
    put_str_num_serial("thread rsp: ", thread.rsp);

    return thread;
}

void thread_stack_init(struct thread *thread)
{
    thread->rsp = init_stack(thread->rsp, thread->rip, thread);
    put_str_num_serial("thread stack bottom: ", (uint64_t)thread->stack + STACK_LENGTH);
    put_str_num_serial("thread rsp: ", thread->rsp);
}

void thread_exec(struct thread *thread)
{
    thread->func_info.func(thread->func_info.argc, thread->func_info.argv);
    thread_end(thread->index);
    minfree(thread->stack);
    thread_scheduler();
}

thread_gen 関数でスレッドの生成を行います。 thread 構造体に各種情報を登録していきます。

thread_stack_init でスレッドのスタックの初期化を行います。この時スタックポインタの値も調整されます。

init_stack 関数の実装はレジスタをいじるのでアセンブラで書きます。

.global     init_stack
.align      16
init_stack:           # uint64_t init_stack(uint64_t stack_bottom, uint64_t rip, struct thread *thread);
    cli
    mov     rcx,rsp   # save rsp at rcx
    mov     rsp,rdi   # move rip to rsp
# push general registers to stack
    push    rsi       # push rip(second argument) to stack bottom
                      # because function switch_context requires return rip
    push    0         # rbp
    push    0         # r11
    push    0         # r10
    push    0         # r9
    push    0         # r8
    push    rdx       # rdi
    push    0         # rsi
    push    0         # rcx
    push    0         # rdx
    push    0         # rax
    mov     rax,rsp   # set current rsp to return value
    mov     rsp,rcx   # load rsp from rcx
    sti
    ret

まず現在の rsprcx に保存し、今のスタックに戻ってこれるようにします。 次に init_stack 関数の第1引数で受け取ったスレッドのスタックポインタをロードして、スレッドのスタックの初期化作業を始めます。 コード中のコメントと push している数値が初期化のデフォルト値に対応しています。

rdi だけ rdx つまり init_stack に渡された第3引数をセットしていますが、これは thread_exec に渡す引数を設定しています。

少しややこしいので説明すると、まずスレッドで実行する関数を thread_exec で包みます。 そして thread_exec をスレッドで実行する関数として登録します(thread_gen をよく見ると関数の設定で thread_exec を登録している)。 というのも、 thread_exec でスレッドの関数が終わった際の終了処理とスケジューラ呼び出しを行うからです。 thread_exec には thread 構造体へのポインタが必要なので、レジスタの初期化を行うときに rdi つまり第一引数に thread 構造体へのポインタを設定してやることで引数を渡します。 thread_exec の末尾3行はスレッドの状態を変更し、mallocした領域を開放し、スケジューラを呼び出します。

thread_genthread_stack_init はこんな感じで使います。

    // スレッドを生成
    struct thread thread0 = thread_gen(console, 0, 0);
    struct thread thread1 = thread_gen(task_a, 0, 0);
    struct thread thread2 = thread_gen(task_b, 0, 0);
    struct thread thread3 = thread_gen(task_c, 0, 0);

    // initialize stack
    thread_stack_init(&thread0);
    thread_stack_init(&thread1);
    thread_stack_init(&thread2);
    thread_stack_init(&thread3);

スレッドを切り替える処理

まずタイマの割り込みハンドラでスケジューラを呼び出す処理を見ましょう。

/**
 * タイマ割り込みハンドラ
 * クロック値を進めて、スケジューラを呼び出す
*/
__attribute__((interrupt))
void timer_handler(struct InterruptFrame *frame)
{
    // クロック値を進める
    milli_clock++;
    // EOIをPICに送る
    io_outb(PIC0_OCW2, PIC_EOI);
    io_outb(PIC1_OCW2, PIC_EOI);

    /** 周期が来たらスケジューラを呼び出す
     * 各種パラメータはint_handler.hで設定
     */
    if (milli_clock > previous_interrupt + timer_period && milli_clock > 100) {
        previous_interrupt = milli_clock;
        put_str_num_serial("timer_handler old rip: ", frame->rip);
        puts_serial("\n");
        thread_scheduler();
    }
}

if の条件式でスケジューラを呼び出す条件を設定しています。 間隔をグローバル変数 timer_period で指定しています。 一定時間が経ったら thread_scheduler を呼び出すようになっています。

次に thread_scheduler を見てみましょう。

void thread_scheduler(void)
{
    // update current_thread_index
    int old_thread_index = current_thread_index;
    int i = 1;
    while (current_thread_index == old_thread_index) {
        if (threads[(current_thread_index + i) % THREAD_NUM]->state == RUNNABLE) {
            current_thread_index = (current_thread_index + i) % THREAD_NUM;
        }
        i++;
    }

    put_str_num_serial("next thread index: ", (uint64_t)current_thread_index);
    put_str_num_serial("next start rsp: ", threads[current_thread_index]->rsp);
    put_str_num_serial("next start func address: ", (uint64_t)(threads[current_thread_index]->func_info.func));
    puts_serial("\n");
    puts_serial("dispatch start\n\n");

    switch_context(&threads[old_thread_index]->rsp, threads[current_thread_index]->rsp);
}

前半部でスレッドキューから次に実行するスレッドを選択しています。

後半部で重要な処理は switch_context です。見てみましょう。

switch_context:   # void switch_context(uint64_t *current_rsp, uint64_t next_rsp);
# push current task's general registers to stack
    push    rbp
    push    r11
    push    r10
    push    r9
    push    r8
    push    rdi
    push    rsi
    push    rdx
    push    rcx
    push    rax
# switch rsp
    mov     [rdi],rsp
    mov     rsp,rsi
# pop next task's general registers from stack
    pop     rax
    pop     rcx
    pop     rdx
    pop     rsi
    pop     rdi
    pop     r8
    pop     r9
    pop     r10
    pop     r11
    pop     rbp
# return to next task
    ret

レジスタをいじるためアセンブラでしか書けません。

まず現在実行しているスレッドのレジスタの値を保存するために、現在のスレッドのスタックに現在のスレッドのレジスタを保存しています。

次にスタックポインタ rsp の処理です。 現在のスタックポインタを現在のスレッドの構造体に保存し、次に実行するスレッドのスタックポインタを読み出します。

するとここでスタックが切り替わるため、次に実行するスレッドのスタックから次に実行するスレッドのレジスタを読み出すことができます。 ですので次に実行するスレッドのレジスタをスタックから読み出します。

最後に retrip を読み出し、次のスレッドにジャンプします。

最後の ret でどこにジャンプするのか?

これは少しややこしいですので説明します。 switch_context が呼ばれた瞬間のスタックが属するスレッドをAt、次に実行するスレッドをBtとします。

まず switch_context 中で rsp が切り替わったときにスタックがBtのものに切り替わります。 レジスタをpopしていって最後に ret を発行すると、 スタックはBtのもので ripthread_scheduler 関数の switch_context から抜けた所に飛びます。

thread_scheduler 関数はこれ以上の処理はないため、 スタックはBtのもので rip はタイマ割り込みハンドラの timer_handlerthread_scheduler から抜けた所に飛びます。

timer_handler はこれ以上の処理はないため、 スタックはBtのもので rip は割り込み前に実行していた所がロードされます。 スタックがBtのもの なので、ロードされる rip はスタックBtに積まれた関数中のアドレスであり、スタックBtに積まれる関数というのはスレッドBtに登録されている関数です。

実装は以上

たぶんこれで動くと思います。

まとめ

タスクスイッチの実装はスタックにレジスタを積まなくてはならず、かなりややこしい部分です。 実装は大変苦労しましたが、喜びもひとしおでしたね。