🎃
"Hello World!" on HinaOS
概要
最近「自作OSで学ぶマイクロカーネルの設計と実装」という本を読んだ。仕組みをより深く知るためにコードを読むことにした。HinaOSで「Hello World!」が出力されるまでの過程を追ってみる。
コードは以下にある。
実行
Code Reading
- まずはshellサーバーの処理を追う。
servers/shell/main.c
void main(void) {
char cmdline[1024];
// startコマンドで起動したタスクが終了したら知らせてもらうようにしておく。
struct message m;
m.type = WATCH_TASKS_MSG;
ASSERT_OK(ipc_call(VM_SERVER, &m));
char *autorun = AUTORUN;
if (autorun[0] != '\0') {
strcpy_safe(cmdline, sizeof(cmdline), autorun);
INFO("running autorun script: %s", cmdline);
eval(cmdline);
}
// 他のサーバが起動しているとシェルのプロンプトがログの中に紛れて分かりづらいので、
// ここでちょっと待つ。
sys_time(100);
ipc_recv(IPC_ANY, &m);
ASSERT(m.type == NOTIFY_TIMER_MSG);
printf("\nWelcome to HinaOS!\n\n");
while (true) {
printf("\x1b[1mshell> \x1b[0m");
printf_flush();
error_t err = read_line(cmdline, sizeof(cmdline));
if (err == OK) {
eval(cmdline);
}
}
}
- ipc_call(VM_SERVER, &m);の処理を追う。dst, srcをどちらもVM_SERVERにして、sys_ipcを呼んでいる。フラグにはIPC_CALLが指定されている。
libs/user/ipc.c
error_t ipc_call(task_t dst, struct message *m) {
error_t err = sys_ipc(dst, dst, m, IPC_CALL);
if (err != OK) {
return err;
}
// エラーメッセージが返ってくれば、そのエラーを返す。
if (IS_ERROR(m->type)) {
return m->type;
}
return OK;
- sys_ipcはarch_syscallを呼び出しているだけ。arch_syscallはシステムコールラッパー。
libs/user/syscall.c
error_t sys_ipc(task_t dst, task_t src, struct message *m, unsigned flags) {
return arch_syscall(dst, src, (uintptr_t) m, flags, 0, SYS_IPC);
}
libs/user/riscv32/arch_syscall.h
static inline uint32_t arch_syscall(uint32_t r0, uint32_t r1, uint32_t r2,
uint32_t r3, uint32_t r4, uint32_t r5) {
register int32_t a0 __asm__("a0") = r0; // a0レジスタの内容
register int32_t a1 __asm__("a1") = r1; // a1レジスタの内容
register int32_t a2 __asm__("a2") = r2; // a2レジスタの内容
register int32_t a3 __asm__("a3") = r3; // a3レジスタの内容
register int32_t a4 __asm__("a4") = r4; // a4レジスタの内容
register int32_t a5 __asm__("a5") = r5; // a5レジスタの内容
register int32_t result __asm__("a0"); // 戻り値 (a0レジスタに戻ってくる)
// ecall命令を実行し、カーネルのシステムコールハンドラ (riscv32_trap_handler) に処理を移す。
// 返り値がa0レジスタ (result変数) に戻ってくる。
__asm__ __volatile__("ecall"
: "=r"(result)
: "r"(a0), "r"(a1), "r"(a2), "r"(a3), "r"(a4), "r"(a5)
: "memory");
return result;
}
- ハンドラはkernel/riscv32/handler.sで定義されている。コンテキストを退避した上でriscv32_handler_trapを呼び出している。これはkernel/riscv32/tarp.cで定義されている。
- ecallを読んでいるのでscauseは8(SCAUSE_ENV_CALL)になる。そのため、以下の処理が実行される。ロックをとってhandle_syscall_trapを呼び出している。
kernel/riscv32/trap.c
case SCAUSE_ENV_CALL:
mp_lock();
handle_syscall_trap(frame);
mp_unlock();
break;
- handle_syscall_trapではhandle_syscallを呼び出して戻り値を取得している。
- handle_syscallはフラグがSYS_IPCの場合はsys_ipcを呼び出す。名前が同じなのが紛らわしいが、これはさっきのsys_ipcとは別物。
kernel/syscall.c
case SYS_IPC:
ret = sys_ipc(a0, a1, (__user struct message *) a2, a3);
break;
- IPC_CALLはlibs/common.h/message.hで以下のように定義されている。
- src, dstは共にVM_SERVERだった。以下ではtask_findを呼び出してタスクidがVM_SERVERとなるタスクを探している。最終的にipcを呼び出している。
#define IPC_CALL (IPC_SEND | IPC_RECV)
kernel/syscall.c
static error_t sys_ipc(task_t dst, task_t src, __user struct message *m,
unsigned flags) {
// 許可されていないフラグが指定されていないかチェック
if ((flags & ~(IPC_SEND | IPC_RECV | IPC_NOBLOCK)) != 0) {
return ERR_INVALID_ARG;
}
// 有効なタスクIDかチェック
if (src < 0 || src > NUM_TASKS_MAX) {
return ERR_INVALID_ARG;
}
// 送信処理が含まれているのであれば、送信先タスクを取得
struct task *dst_task = NULL;
if (flags & IPC_SEND) {
dst_task = task_find(dst);
if (!dst_task) {
return ERR_INVALID_TASK;
}
}
return ipc(dst_task, src, m, flags);
}
- task_findはシンプルな実装になっている。tasksはグローバル変数。
kernel/task.c
struct task *task_find(task_t tid) {
if (tid < 0 || tid >= NUM_TASKS_MAX) {
return NULL;
}
struct task *task = &tasks[tid - 1];
if (task->state == TASK_UNUSED) {
return NULL;
}
return task;
}
- ipc関数はflagに応じて関数を呼び出している。IPC_CALLはIPC_SENDとIPC_RECVのorだったので、send_messaageと、recv_messageが呼び出される。
kernel/ipc.c
error_t ipc(struct task *dst, task_t src, __user struct message *m,
unsigned flags) {
// 送信操作
if (flags & IPC_SEND) {
error_t err = send_message(dst, m, flags);
if (err != OK) {
return err;
}
}
// 受信操作
if (flags & IPC_RECV) {
error_t err = recv_message(src, m, flags);
if (err != OK) {
return err;
}
}
return OK;
}
- まずsend_messageの処理を追う。長いのでコードは省略。kernel/ipc.cに定義されている。
- 最初に現在実行中のタスクがdstに指定されていないか調べているけど、currentはshellサーバーになるので問題ない。
- メッセージをユーザー空間からコピーして、送信先がメッセージを待っているか確認している。vmはフラグにIPC_ANYを指定してipc_recvを呼んでいるので、以下が実行される。
kernel/ipc.c
memcpy(&dst->m, &copied_m, sizeof(struct message));
dst->m.src = (flags & IPC_KERNEL) ? FROM_KERNEL : current->tid;
task_resume(dst);
return OK;
- dst->mにメッセージをコピーしている。dst->m.srcはcurrent->tidになるので、shellサーバのtidになる。
- task_resumeの中でlist_push_backを呼び出してランキューに追加している。タスク切り替えは行っていない。
- タスク切り替えはタイマー割り込みで行っている。handler_timer_interruptがkernel/interrupt.cで定義されている。各タスクのタイマーを更新した後に現在実行中のタスクの実行時間を更新して0になったらtask_switchを呼び出して切り替えている。
- 次にrecv_messageの処理を追う。長いのでコードは省略。kernel/ipc.cに定義されている。
- srcはVM_SERVERだったので、以下が実行される。
- currentはshellサーバ。wait_forにVM_SERVERを代入して現在のタスクの状態をブロック状態に(TASK_BLOCKED)にしたのち、task_switchでタスクを切り替えている。task_switchのコードを読むと分かるのだが、現在実行中のタスクはランキューの中になく、タスクを切り替える際に状態がTASK_RUNNABLEの場合にのみランキューに戻す処理がある。そのため、これ以降(vmサーバによって起こされるまで)shellサーバーが実行されることはない。
- vmサーバーに起こされると、メッセージをcurrent->mにコピーして戻る。
kernel/ipc.c
// メッセージを受信するまで待つ
current->wait_for = src;
task_block(current);
task_switch();
// メッセージを受け取った
current->wait_for = IPC_DENY;
memcpy(&copied_m, ¤t->m, sizeof(struct message));
- 次にvmサーバーの処理を追う。shellサーバから送られてくるメッセージの種類はWATCH_TASK_MSGだったので、以下が実行される。
- shellサーバを見つけて、watch_taskフラグを立てたのち、ipc_replyで応答している。
servers/vm/main.c
case WATCH_TASKS_MSG: {
struct task *task = task_find(m.src);
ASSERT(task);
task->watch_tasks = true;
m.type = WATCH_TASKS_REPLY_MSG;
ipc_reply(m.src, &m);
break;
- ipc_replyはipc_send_noblockを呼び出すだけ。
libs/user/ipc.c
void ipc_reply(task_t dst, struct message *m) {
error_t err = ipc_send_noblock(dst, m);
OOPS_OK(err);
}
- ipc_send_noblockはIPC_SENDとIPC_NOBLOCkフラグを付けてsys_ipcを呼び出す。上で見た処理の後に、ipcが呼び出される。
libs/user/ipc.c
error_t ipc_send_noblock(task_t dst, struct message *m) {
return sys_ipc(dst, 0, m, IPC_SEND | IPC_NOBLOCK);
}
- IPC_SENDフラグが立っているのでsend_messageが呼ばれる。shellサーバーはrecv_messageを呼び出してTASK_BLOCKEDになっていたので、readyがtrueになり、以下が実行される。task_resumeにより、shellサーバーが再びランキューに追加される。
kernel/ipc.c
memcpy(&dst->m, &copied_m, sizeof(struct message));
dst->m.src = (flags & IPC_KERNEL) ? FROM_KERNEL : current->tid;
task_resume(dst);
return OK;
- shellサーバーの続きを追っていく。コードを再掲する。
servers/
char *autorun = AUTORUN;
if (autorun[0] != '\0') {
strcpy_safe(cmdline, sizeof(cmdline), autorun);
INFO("running autorun script: %s", cmdline);
eval(cmdline);
}
// 他のサーバが起動しているとシェルのプロンプトがログの中に紛れて分かりづらいので、
// ここでちょっと待つ。
sys_time(100);
ipc_recv(IPC_ANY, &m);
ASSERT(m.type == NOTIFY_TIMER_MSG);
printf("\nWelcome to HinaOS!\n\n");
while (true) {
printf("\x1b[1mshell> \x1b[0m");
printf_flush();
error_t err = read_line(cmdline, sizeof(cmdline));
if (err == OK) {
eval(cmdline);
}
}
}
- autorunの処理は良く分からない。スタートアップみたいな感じかな。
- その後sys_timeを呼び出して、一定時間待っている。タイマー割り込みのハンドラ内にタイムアウトしたタスクに対して通知を送る処理がある。
kernel/interrupt.c
void handle_timer_interrupt(unsigned ticks) {
// 起動してからの経過時間を更新
uptime_ticks += ticks;
if (CPUVAR->id == 0) {
// 各タスクのタイマーを更新する
LIST_FOR_EACH (task, &active_tasks, struct task, next) {
if (task->timeout > 0) {
task->timeout -= MIN(task->timeout, ticks);
if (!task->timeout) {
// タイムアウトしたのでタスクに通知する
notify(task, NOTIFY_TIMER);
}
}
}
}
// 実行中タスクの残り実行可能時間を更新し、ゼロになったらタスク切り替えを行う
struct task *current = CURRENT_TASK;
DEBUG_ASSERT(current->quantum >= 0 || current == IDLE_TASK);
current->quantum -= MIN(ticks, current->quantum);
if (!current->quantum) {
task_switch();
}
}
- その後無限ループでコマンドの読み取りと実行を行っている。"start hello"が入力されたとして読み進める。
- 入力の評価はeval関数で行っている。evalは引数と引数の数をstruct argsに入れてrun_commandを実行している。
- run_commadの実装は面白い。args->arg[0]とcmd->nameを比較して、一致した場合はcmd->run(args)を実行している。
servers/shell/command.c
void run_command(struct args *args) {
if (args->argc == 0) {
return;
}
struct command *cmd = commands;
while (cmd->name != NULL) {
if (!strcmp(cmd->name, args->argv[0])) {
cmd->run(args);
return;
}
cmd++;
}
WARN("unknown command: %s", args->argv[0]);
}
commandsは以下のように定義されている。あらかじめ関数と名前を定義することで、長いif-else, switch-caseを避けている。見やすい。
servers/shell/command.c
static struct command commands[] = {
{.name = "help", .run = do_help, .help = "Show this help"},
{.name = "echo", .run = do_echo, .help = "Print arguments"},
{.name = "http", .run = do_http, .help = "Fetch a URL"},
{.name = "cat", .run = do_cat, .help = "Show file contents"},
{.name = "write", .run = do_write, .help = "Write text to a file"},
{.name = "ls", .run = do_listdir, .help = "List files in a directory"},
{.name = "mkdir", .run = do_mkdir, .help = "Create a directory"},
{.name = "delete", .run = do_delete, .help = "Delete a file or directory"},
{.name = "start", .run = do_start, .help = "Launch a task from bootfs"},
{.name = "sleep", .run = do_sleep, .help = "Pause for a while"},
{.name = "ping", .run = do_ping, .help = "Send a ping to pong server"},
{.name = "uptime", .run = do_uptime, .help = "Show seconds since boot"},
{.name = "shutdown", .run = do_shutdown, .help = "Shut down the system"},
{.name = NULL},
};
- "start hello"を入力した場合はdo_start(args)が実行される。
- do_startの中ではvmに対してSPAWN_TASK_MSGというタイプのメッセージを送信している。m.spawn_task.nameは"hello"になる。
servers/shell/commands.c
static void do_start(struct args *args) {
if (args->argc != 2) {
WARN("Usage: start <NAME>");
return;
}
// タスクを起動する
struct message m;
m.type = SPAWN_TASK_MSG;
strcpy_safe(m.spawn_task.name, sizeof(m.spawn_task.name), args->argv[1]);
error_t err = ipc_call(VM_SERVER, &m);
if (IS_ERROR(err)) {
WARN("failed to spawn %s: %s", args->argv[0], err2str(err));
}
[snip]
- SPAWN_TASK_MSGメッセージの処理を追う。
servers/vm/main.c
case SPAWN_TASK_MSG: {
char name[sizeof(m.spawn_task.name)];
strcpy_safe(name, sizeof(name), m.spawn_task.name);
struct bootfs_file *file = bootfs_open(name);
if (!file) {
ipc_reply_err(m.src, ERR_NOT_FOUND);
break;
}
task_t task_or_err = task_spawn(file);
if (IS_ERROR(task_or_err)) {
ipc_reply_err(m.src, task_or_err);
break;
}
m.type = SPAWN_TASK_REPLY_MSG;
m.spawn_task_reply.task = task_or_err;
ipc_reply(m.src, &m);
break;
}
- bootfs_openを呼び出して指定された名前のファイルを検索している。ここでは"hello"になる。
- ファイルが見つかった場合はtask_spawnでタスクを生成して、tidをメッセージに入れて呼び出し元に戻している。
- task_spawnはservers/vm/task.cで定義されている。elfファイルからタスクを生成している。sys_task_createでシステムコールを呼び出している。同名の関数がkernel/syscall.cにある。ページャータスクはvmサーバーになる。これでhelloサーバーが生成され、ランキューに追加される。
kernel/syscall.c
static task_t sys_task_create(__user const char *name, uaddr_t ip,
task_t pager) {
// タスク名を取得
char namebuf[TASK_NAME_LEN];
error_t err = strcpy_from_user(namebuf, sizeof(namebuf), name);
if (err != OK) {
return err;
}
// ページャータスクを取得
struct task *pager_task = task_find(pager);
if (!pager_task) {
return ERR_INVALID_ARG;
}
// 通常のユーザータスクを作成する場合
return task_create(namebuf, ip, pager_task);
}
- helloサーバーはprintfで"Hello World!"を表示しているだけ。
servers/hello/main.c
#include <libs/common/print.h>
void main(void) {
INFO("Hello World!");
}
- shellサーバーの続きを追う。起動したhelloサーバの終了を待っている。
servers/shell/commands.c
// タスクが終了するまで待つ
task_t new_task = m.spawn_task_reply.task;
while (true) {
struct message m;
ASSERT_OK(ipc_recv(IPC_ANY, &m));
if (m.type == TASK_DESTROYED_MSG && m.task_destroyed.task == new_task) {
break;
}
}
}
- helloサーバの終了の通知はtask_exit関数で行われている。これが呼び出されるとページャータスク(vmサーバー)にEXCEPTION_MSGが飛び、task_destroyが呼ばれる。これでやっと"start hello"が終了する。
kernel/task.c
__noreturn void task_exit(int exception) {
struct task *pager = CURRENT_TASK->pager;
ASSERT(pager != NULL);
TRACE("exiting a task \"%s\" (tid=%d)", CURRENT_TASK->name,
CURRENT_TASK->tid);
// ページャータスクに終了理由を通知する。ページャータスクがtask_destroyシステムコールを
// 呼び出すことで、このタスクが実際に削除される。
struct message m;
m.type = EXCEPTION_MSG;
m.exception.task = CURRENT_TASK->tid;
m.exception.reason = exception;
error_t err = ipc(CURRENT_TASK->pager, IPC_DENY,
(__user struct message *) &m, IPC_SEND | IPC_KERNEL);
if (err != OK) {
WARN("%s: failed to send an exit message to '%s': %s",
CURRENT_TASK->name, pager->name, err2str(err));
}
// 他のタスクを実行する。もうこのタスクに戻ってくることはない。
task_block(CURRENT_TASK);
task_switch();
UNREACHABLE();
}
- 問題はtask_exitがどこから呼ばれるか。怪しいのはhelloサーバーがret命令で戻る先。ということで、タスク生成時の処理を追う。task_createが呼ばれていたのでまずこれを見る。
- task_create→init_task_struct→arch_task_initの順に呼び出される。arch_task_initを見ると以下のような処理がある。
kernel/riscv32/task.c
} else {
// riscv32_user_entry_trampoline関数でポップされる値
*--sp = ip; // タスクの実行開始アドレス
entry = (uint32_t) riscv32_user_entry_trampoline;
}
- riscv32_user_entry_trampolineからタスクのエントリポイントに飛ぶっぽいので、この関数を見る。
kernel/riscv32/switch.S
.align 4
.global riscv32_user_entry_trampoline
riscv32_user_entry_trampoline:
// スタックから引数を取り出して、riscv32_user_entry関数にジャンプする
lw a0, 0 * 4(sp) // ip
j riscv32_user_entry
- riscv32_user_entryを呼び出している。これはkernel/riscv32/task.cで定義されている。(長いので省略)ここではレジスタをクリアしてタスクのエントリポイントに飛んでいる。
- この関数の最後にtask_exitがあるのかと思ったが、以下のコメントの通り、この関数に戻ってくることはないらしい。
kernel/riscv32/task.c
// この関数には決して戻ってこない。ユーザータスクからカーネルモードに戻るときは常に
// riscv32_trap_handler が入り口となる。
UNREACHABLE();
- 呼び出し元を特定するために、ソースコードを以下のように編集した。
libs/user/syscall.c
// task_destroyシステムコール: タスクの削除
error_t sys_task_destroy(task_t task) {
OOPS("sys_task_destroy");
return arch_syscall(task, 0, 0, 0, 0, SYS_TASK_DESTROY);
}
// task_exitシステムコール: 実行中タスクの終了
__noreturn void sys_task_exit(void) {
OOPS("sys_task_exit");
arch_syscall(0, 0, 0, 0, 0, SYS_TASK_EXIT);
UNREACHABLE();
}
- この状態でmake runして、"start hello"を入力すると以下のようになった。
- アドレスが分かったので以下のコマンドでelfファイルをディスアセンブリして場所を特定する。
$ llvm-objdump -d -M intel ./build/servers/hello.elf.debug
- すると以下の箇所がヒットする。start関数からmain関数が呼ばれた後、sys_task_exitが呼ばれていることが確認できる。つまりhelloサーバーのエントリポイントはmain関数ではなく、start関数。これはlibs/user/riscv32/start.Sで定義されている。
240055c0 <start>:
240055c0: 01 44 li s0, 0
240055c2 <.Lpcrel_hi0>:
240055c2: 17 b1 48 00 auipc sp, 1163
240055c6: 13 01 e1 b4 addi sp, sp, -1202
240055ca: ef e0 2f ee jal 0x24003cac <hinaos_init>
240055ce: ef a0 3f a3 jal 0x24000000 <main>
240055d2: ef d0 df 95 jal 0x24002f2e <sys_task_exit>
240055d6: 00 00 unimp
.align 4
.global start
start:
mv fp, zero // フレームポインタをゼロに初期化することで、スタックトレースがここで
// 停止するようにする
la sp, __stack // スタックポインタをスタックの最上位に設定する
jal hinaos_init // userライブラリの初期化
jal main // ユーザープログラムのエントリーポイント (main関数)
jal sys_task_exit // main関数から戻ってきたらタスクを終了する
分かったこと
- microkernelでは"Hello World!"の表示だけでも結構複雑な処理になる。
- kernelには基本的にメッセージパッシング用のAPIだけがあり、タスクの生成、削除といったモノリシックカーネルでは普通kernel内に実装される処理をvmサーバー(ユーザーランド)が行っている。
考察
- メッセージパッシング時にはtidを指定していたが、「どのサーバーがどのtidを持つか」を知っている必要があるのが欠点だと思った。今回みたいに少数のサーバーしか動かさないならこれでも問題ないけど、数が増えるときつくなりそう。名前とtidを紐づける、「名前解決サーバー」があると便利かも。
- タスク切り替えは単純なラウンドロビンで実装されていたけど、「スケジューリングサーバー」を作ればいろいろなスケジューリングアルゴリズムを切り替えられて面白そうだと思った。
- 同期的メッセージパッシングが採用されていて、メッセージがstruct taskのメンバ(要素数1)になっていた。今回のような単純な処理だと大丈夫だけど、ネットワーク周りの処理とか、たくさんのメッセージをやり取りしそうなので、この実装だと辛そうだなと思った。(後で実装読む)メッセージをキューにして、非同期でやり取りできるようにしたいと思った。
Discussion