BYB

低レイヤ好き学生エンジニアによる備忘録

MikanOSにユーザースレッド風機能を実装

概要

初めに

このブログは以前書いたものを、2022 自作 OS Advent Calendar用に書き換えて再公開したものです。
当初は備忘録的な意味で書き殴っていたものであるため、非常に長くまとまりのない文章になってしまってすみません。
また勘違いをしていて間違った内容を書いているところがあるかもしれないので、気付いた方はご指摘をいただけると嬉しいです。

このブログの内容について

前回のブログでMikanOSにspinlockを実装したつもりであったが、勉強していくうちに、MikanOSはシングルスレッドなのでCPUで割り込み防止をするだけで排他制御が可能であることが分かった。
そしてMikanOSにはアプリケーションを並列処理で実行するための仕組みが備わっていないことも知った。
今回はそれを実現するためのユーザースレッドを実装した。
なお前回のブログに書いていた通り、自力で調べて実装までするのは難しいと感じたため、サイボウズ・ラボユースに応募してそこで取り組ませてもらうことにした。
labs.cybozu.co.jp
サイボウズ・ラボユースは、世界に通用する日本の若手エンジニアの発掘と育成を目指すことを目的に、学生の若手クリエイターに研究開発の機会を提供する場としてサイボウズ・ラボさんが開いてくだっさっている。
ここに採択されると、サイボウズ・ラボの方にメンターとしてついてもらって自分のしたい研究・開発に取り組むことができ、奨励金もいただくことができるという嘘みたいな本当の制度である。

訂正

記事内ではユーザスレッドを実装したという風に書いていますが、下にも書いているようにユーザースレッドというのは、システムコールを用いてユーザ側でスケジューリングを行うものである。
今回はスケジュール自体をカーネル側に任せているので、ユーザースレッド風機能という言い方がよいだろうか。



ユーザースレッドについて

スレッドとは

そもそもスレッドとはどういったものだろうか。
スレッドとプロセスの違いなども含めて説明しておきたいと思う。
簡単に述べると、

  • プロセス:プロセスID,メモリ空間,コンテキストなどを独自に持つ実行単位
  • スレッド:プロセスに紐づいている、メモリ空間をプロセスと共有するひとまとまりの命令処理

といった具合だろうか。
(おまけ)低レイヤの話 ~Linuxとの比較~｜Goでの並行処理を徹底解剖！
なおこのブログにも書いてある通り、Linuxカーネル内部ではプロセスとスレッドはtask_struct構造体という共通のデータ構造で扱われている。

ユーザースレッド

ユーザースレッドとは、ユーザー空間上で生成されるスレッドのことである。
スケジューリングはライブラリ内のスレッドスケジューラが行う。

今回実現したユーザースレッドの機能と仕様

今回は、POSIXスレッドにおけるpthread_createとpthread_joinにあたる機能を実装した。
create関数は引数として、新スレッドに対応するapp_thread_t構造体へのポインタと新スレッドのエントリポイント関数のアドレス、その関数に渡す引数をとる。
pthread_createと違い、属性の指定はできない。
apps/app_thread.cpp

int app_thread_create(app_thread_t* t, void* f, int64_t data){
    auto [ret, err] =SyscallThreadCreate((void *)f,data);
    t->task_id=ret;
    return 0;
}


join関数は引数として待ち合わせたいスレッドに対応するapp_thread_t構造体へのポインタを引数として取る。
pthread_join関数ではpthread_t構造体そのものを引数として取るが、createと違う形にすることに特に意味はないと思ったので、join関数もポインタを引数にすることとした。
処理の中身は、指定したスレッドが終わっているかを無限ループで監視し続け、終わっていたらループを抜けるというものである。

int app_thread_join(app_thread_t *thread){
    int64_t task_id=thread->task_id;
    while(1){
        auto [ret, err]=SyscallTaskExist(task_id);
        if(ret==0){
            break;
        }
    }
    return 0;
}


スレッドのエントリポイント関数は、引数として64bitの値をとる。

実装に必要な前提知識

実装に必要な計算機科学やMikanOSについての前提知識をまとめる。

MikanOSにおけるマルチタスクの実現

MIkanOSを含む多くのOSにおいて、マルチタスクの実現はコンテキストを切り替えることによって行う。
スタックポインタや命令ポインタなどの値をそっくりすげ替えることで、CPUからすると命令を逐次実行しているだけにも関わらず、全く違う処理に飛ぶことができるのだ。
ただし、タスクを切り替える前の処理にもう一度戻ってこれるように、前のタスクにおけるスタックポインタや命令ポインタなどの値を保存しておく必要がある。
このようなデータや変数のまとまりのことをコンテキストと呼ぶ。
MikanOSのコンテキスト構造体を以下に示す。
コンテキストを切り替える際に値の保存と復帰が必要なレジスタを全て含んでいる。

struct TaskContext {
  uint64_t cr3, rip, rflags, reserved1; // offset 0x00
  uint64_t cs, ss, fs, gs; // offset 0x20
  uint64_t rax, rbx, rcx, rdx, rdi, rsi, rsp, rbp; // offset 0x40
  uint64_t r8, r9, r10, r11, r12, r13, r14, r15; // offset 0x80
  std::array<uint8_t, 512> fxsave_area; // offset 0xc0
} __attribute__((packed));

タスクの自動切り替えは、タイマーによって一定時間が来たら割り込みを行うような処理をして、その割り込みのハンドラでSwichTask関数を呼ぶことで実現している。

メモリ空間

MikanOSを始めとするx86-64の64bitモードで動くOSは、メモリ管理をページングによって行う必要がある。
ページングとは仮想記憶（仮想メモリ）の方式の一つで、メモリ領域をページと呼ばれる一定の大きさの領域に分割し、物理的なアドレス（番地）とは別に仮想的なアドレスを割り当てて管理する方式である。
ページング方式 - Wikipedia

x86_64におけるページング構造は、次のような階層を持っている。
この構造通りにメモリ上に階層ページング構造(ページテーブル等)を構築すれば、MMUがそれを辿ることで仮想メモリ-物理メモリ間の変換を行うことができる。

出典:
https://qiita.com/mopp/items/82bef23d0470de21b5d3


特権レベル3で動くアプリの呼び出しと復帰 (CallApp)

特権レベル3で動かすアプリの処理へ移行するためには、以下のことが必要である。

  • 予めDPL(descriptor_privilege_level)=3を持つコードセグメントとデータセグメントを構築し、GDT(Grobal Descriptor Table)に登録しておく。
  • アプリを呼び出す前に、アプリ用のスタック領域や引数受け渡し用の領域をアプリ用のアドレス空間に構築しておく。

アプリ用のページテーブルへのポインタをcr3レジスタに入れた上で、userビット1の領域をSetupPageMaps関数で確保することで、アプリ用のアドレス空間にアプリが使えるメモリ領域を作ることができる。


移行時の処理としては、

  1. OS用のスタック領域に、現在の各種レジスタの値を保存する。
  2. アプリ呼び出しの際に、セグメントレジスタであるCS・SSがそれぞれ先程登録したコードセグメント・データセグメントを指すようにする。
  3. rspを書き換えてスタックをアプリ用のものに変える。
  4. ripの値をアプリのエントリポイント関数のアドレスに書き換える。

上記の処理を行うことで、そのタスクにおいて権限レベル3でアプリが動き出す。
なお上記の内2-4のレジスタ書き換え処理は、スタックに適切な順番で値を積んだ後に、far returnを呼び出すことで実現している。
(権限が低いコードセグメントへのfar returnの場合、rip・csだけでなく、ss・rspもスタックから取り出される。)
この処理を行うのがCallApp関数である。

kernel/asmfunc.asm

global CallApp
CallApp:  ; int CallApp(int argc, char** argv, uint16_t ss,
          ;             uint64_t rip, uint64_t rsp, uint64_t* os_stack_ptr);
    push rbx
    push rbp
    push r12
    push r13
    push r14
    push r15
    mov [r9], rsp ; OS 用のスタックポインタを保存

    push rdx  ; SS
    push r8   ; RSP
    add rdx, 8
    push rdx  ; CS
    push rcx  ; RIP
    o64 retf
    ; アプリケーションが終了してもここには来ない


アプリを終了して特権レベル3から0に戻す処理には、システムコールを利用する。
通常のシステムコールは処理が終わるとsysret命令で呼び出し元の処理に戻る。
しかしアプリ終了システムコールは、処理の最後でスタックをアプリ用のものに切り替えたのち、ret命令を呼ぶ。
そうすることで、CallApp関数を呼んだOS側の処理に戻る。
CallApp関数がここへのreturnを呼ぶことはないので、CallApp関数呼び出し時のcall命令でスタックに積まれたripの値を、アプリ終了システムコールが利用するという形である。
(CallApp関数の最後のfar returnが呼ばれるときは、スタック(やその他レジスタ)がアプリ用のものになっていて、スタックに積まれた取り出すべきripの値はアプリのエントリポイントである。)


アプリケーションから画面への出力

アプリ上のprintf()関数等からターミナルへの出力を行うためには、write()システムコールが必要である。
sourceware.org Git - newlib-cygwin.git/tree
(このようなドキュメントを見ていくことで、標準関数に必要な関数とその形式を調べることができる。)
MikanOSにおけるwrite()はapps/newlib_support.cppの中に実装されており、その実体はPutStringシステムコールを呼び出すことである。
PutStringシステムコールでは、指定されたファイルディスクリプタの番号に従って、適切な場所に文字列を送り込むことである。
(MikanOSにて実装されているのは、ターミナルへの出力およびコマンドのパイプライン上への出力である)


設計と実装

設計の背景と概要

プロセス

MikanOS上でタスクと呼ばれているものは、メモリ空間を別に持つためLinuxにおけるプロセスのようなものである。
ただしMikanOSではLinuxと違って、タスクをツリー構造ではなくリストとして管理しており、タスク同士の親子関係という概念も存在しない。
しかしスレッドを実装する上でどのプロセスのメモリ空間と紐づくスレッドかという情報をタスクに置いておく必要があるため、リスト構造となっているのとは別に親子関係を示すポインタを保持しておく。

スケジューリング

なお本来ユーザースレッドのスケジューリングはアプリ側のライブラリ内のスレッドスケジューラが行うものだが、今回はユーザースレッドも他のプロセスと同様にOSがスケジューリングを行うようにした。

メモリ空間

またMikanOSにおけるtaskはLinuxのプロセスのように、データやメモリ空間をそれぞれ独立して持つ。
一方ユーザースレッドは、親タスクや他のスレッドとメモリ空間を共有している必要がある。
ページング方式のメモリ管理において、メモリ空間を共有するということは、ページマップ(ページング構造)を共有するということである。
そのためスレッドは、親タスクが持つページング構造をそのまま利用するような実装にした。

入出力

またCLIアプリケーションから呼び出すスレッドということで、スレッドが呼び出し元タスクと同じターミナルと紐づく必要がある。
ファイルディスクリプタを共有することで、その要件を満たした。

追加したデータ構造

task、terminal、layer(画面に出力する平面の画像データ。複数重ね合わせることで、windowの重なりやマウスポインタなどを表現。)を繋ぐデータ構造を変更した。

元々の実装

  • terminal-task
  • layer-task
  • (もちろんlayer-terminalも)


がそれぞれ1対1対応だった。
キーボードからの入力があった際に、アクティブな(一番上に来ていて入力を受け付けている)レイヤーと対応しているタスクに、入力された文字列を送信する仕組みをとっていた。

新しい実装

1つのターミナルに複数のタスクが紐づくようになり、layerとtaskが1対1対応ではなくなった。
そこで、

class Terminal {
  //省略
  uint64_t input_task_id=0; 
  //省略
};

このような変数を付け加えて、ターミナルの中のどのタスク(スレッド)から入力があったかを記録するようにした。
また、

  • terminal-layer

間は1対1対応である。

そこで、

  • layer->terminal ->task(input_task_idを持つもの)

というふうに辿ることで、入力を適切なタスクに送り届けるようにした。


システムコールの準備

ユーザースレッドは、アプリケーションからシステムコール呼び出しで作成される。
今回はスレッドを作成するシステムコールに加え、指定したタスクIDをもつタスクが存在するか調べるもの、アプリケーションが動くタスクにて使用しているCR3レジスタの値を返すもの、CPUの割り込み禁止/許可によって排他制御を実現するシステムコールを加えた。

apps/syscall.h

struct SyscallResult SyscallThreadCreate(void *f,uint64_t data);
struct SyscallResult SyscallCR3toApp();
struct SyscallResult SyscallTaskExist(uint64_t task_id);
struct SyscallResult SyscallIntrLock();
struct SyscallResult SyscallIntrUnlock();

スレッド生成処理の流れ

スレッド生成システムコールが呼び出されると、まずはthread_create関数が呼び出される。
そこから呼び出される関数ごとに、処理の流れを説明してゆく。

thread_create
  • まずは空のタスクを生成して、タスク構造体に親子関係を記述する。
  • その後、生成したタスクのコンテキスト構造体に各種設定をしてゆく。
  • スレッドでは呼び出し元タスクとメモリ空間を共有するため、現在のcr3レジスタの値を取得して、それをそのまま新たなスレッドのコンテキスト構造体のcr3の値に設定する。

(システムコールによって処理がカーネル側に奪われた際も、cr3レジスタの値は変化しないようになっている。)

  • ripにはexec_thread_funcのアドレスをセットし、引数を示すrdi、rsi、rdxに引数の値をセットする。

そして最後にこのスレッドをWakeupさせれば、ここまでで作成したタスクにCPU時間が割り振られるようになる。
このタスクが初めて実行される時、ripにセットしたexec_thread_func関数のアドレスから実行が始まる。
kernel/thread.cpp

uint64_t thread_create(ThreadFunc* f,int64_t data){
    __asm__("cli");
    Task* current=&(task_manager->CurrentTask());
    Task* new_task=&(task_manager->NewTask());
    __asm__("sti");
    new_task->is_thread=true;
    new_task->parent_id=current->ID();
    current->children_id.push_back(new_task->ID());
    //ここでいろいろコピー
    const size_t stack_size = new_task->kDefaultKernelStackBytesOfThread / sizeof(new_task->stack_[0]);
    new_task->stack_.resize(stack_size);
    uint64_t stack_end = reinterpret_cast<uint64_t>(&new_task->stack_[stack_size]);

    memset(&(new_task->context_), 0, sizeof(new_task->context_));
    new_task->context_.cr3 = GetCR3();
    //printk("thread_create : cr3=%lx\n",new_task->context_.cr3);
    new_task->context_.rflags = 0x202;
    new_task->context_.cs = kKernelCS;
    new_task->context_.ss = kKernelSS;
    new_task->context_.rsp = (stack_end & ~0xflu) - 8;

    void (*etfunc)(ThreadFunc* ,u_int64_t,int64_t)=exec_thread_func;
    new_task->context_.rip = reinterpret_cast<uint64_t>(etfunc);
    new_task->context_.rdi = reinterpret_cast<uint64_t>(f); 
    new_task->context_.rsi = new_task->ID();
    new_task->context_.rdx = data;

    task_manager->Wakeup(new_task);

    return new_task->ID();
}
exec_thread_func
  • まずstack_frame用のメモリ領域に、スレッド用のスタック領域を確保する。

具体的にはスタック領域として使用したいアドレスの範囲をSetupPageMaps関数渡すと、この関数がページング構造を設定してくれるので、その領域にアクセスすることが可能となる。

これによって、親タスクと同じターミナルからの入出力が可能となる。

  • デマンドページングによって使用可能なアドレスの範囲も親タスクと共有する。
  • 最後に、CallAppforThreadを呼ぶ。

CallAppforThreadは、引数の数以外は CallApp関数と同じである。
戻ってきたら、その自分自身のタスクをスリープさせておく。

kernel/thread.cpp

void exec_thread_func(ThreadFunc* f,uint64_t task_id,int64_t data){
    Task* child=task_manager->GetTaskFromID(task_id);
    Task* parent=task_manager->GetTaskFromID(child->parent_id);
    const int stack_size = 16 * 4096;
    num_of_thread++;
    LinearAddress4Level stack_frame_addr{0xffff'ffff'ffff'f000 - (stack_size)*(num_of_thread+1)};
    // #@@range_end(increase_appstack)
    if (auto err = SetupPageMaps(stack_frame_addr, stack_size / 4096)) {
        printk("thread exec func : stack page map err\n");
        while(1) __asm__("hlt");
        return ;
    }
    for (int i = 0; i < parent->files_.size(); ++i) {
        child->Files().push_back(parent->files_[i]);
    }
    child->SetDPagingBegin(parent->DPagingBegin());
    child->SetDPagingEnd(parent->DPagingEnd());
    int ret = CallAppforThread(data, 3 << 3 | 3, reinterpret_cast<uint64_t>(f),
                    stack_frame_addr.value + stack_size - 8,
                    &(child->OSStackPointer()));

    while(1){
        __asm__("cli"); 
        task_manager->Sleep(task_id);  
    }    
    return;
}
後処理

スレッドを呼び出したアプリケーションの終了時に、sleepしているはずの子スレッドを終了させるような実装にしている。
もしjoin忘れ等で親タスク終了時に子スレッドが走っていた際は、子スレッドをsleepさせるような実装にした。


難しかった点

今回の改造には様々な前提知識が必要なので、それを体系的に学ぶまでは難しいというより歯が立たない状態だった。
逆に、ラボユースのメンターの方とのミーティングの中でそれらの知識を手に入れて以降は、スムーズに設計と実装をすることができた。
QEMUが落ちてしまうバグ(おそらくトリプルフォールト？)に見舞われてデバッグに苦労した時期も一度あったが、printデバッグとGDBによるデバッグを組み合わせることで、原因を特定することができた。
(スレッド終了の待ち合わせができておらず、アプリ終了時に解放したメモリ領域にスレッドからアクセスしようとしていたのが原因だった。)
以下はMikanOSでのgdbデバッグのやり方をまとめたスライドである。
ゼロからのOS自作入門 輪読会 第7回 - Google スライド


マルチスレッドを用いたサンプルアプリケーション

実装したユーザースレッドの動作確認のために、3つのアプリケーションを作成した。
いずれも意図通り動作した。

テスト出力アプリ

2つのスレッドから異なるメッセージをターミナルに出力する。


2つのスレッドからの出力が、毎回違う順番で表示される様子

mikanos_thread1/uthread1.cpp at u_thread · yushoyamaguchi/mikanos_thread1 · GitHub

入出力アプリ

入力スレッドはキーボードからの入力があると、その数字をグローバル変数に設定する。
出力スレッドはグローバル変数の値を無限ループで表示し続ける。
このアプリで確認したいことは、

  • 同ターミナルへの入出力を違うスレッドで行うことができること
  • スレッド間でグローバル変数を共有できること

である。

mikanos_thread1/uthread2.cpp at u_thread · yushoyamaguchi/mikanos_thread1 · GitHub


ソートアプリ

int型配列を前後半2つに分けて、2つのスレッドでそれぞれマージソートした後、さらにマージする。
これもスレッド間で同じ配列を扱うテストである。

https://github.com/yushoyamaguchi/mikanos_thread3/blob/u_thread/apps/uthread1/uthread3.cpp


ソースコード

github.com
元のソースコードとの差分を見たい方は以下
github.com

謝辞

この実装は自分ひとりの力では絶対にできませんでした。
ラボユースでメンターをしてくださっている川合さんと様々なアドバイスをくださった内田さんという、ビッグなお二人の知恵をお借りしてで実現することができました。
ありがとうございました。