この記事はカーネル／VM Advent Calendarの15日目の記事です。
Sorry, this article is written in Japanese
さて、Minixと言えば教育用のOSとして有名だと思うのですが（教科書「オペレーティングシステム 設計と実装」とかで）、現在も開発は続いており、SCMにgitを使って行われています。リポジトリもmasterブランチの他にジャーナリングファイルシステムを開発しているブランチなんかもありました。今回は今のMinixがオペレーティングシステム第3版からどの程度変わったかを見てみたいと思います。といっても自分が把握できた部分だけなので見逃し等はすみません＞＜
＊コードは2011/12/8時点のマスターブランチから取得したものを見ています
まずはkernelディレクトリから見てみましょう。ここは名前の通りカーネルのコードがあるディレクトリデスが、ご存知の方も多いと思いますがMinixはマイクロカーネルなのでデバイスドライバやファイルシステム等のコードは入っていません。
それでカーネルで大幅に変わった部分というと
- メモリ管理としてx86のセグメント方式からページングを使うようになった
本のバージョンだと#ifdefでcpuが16bit、32bitによって処理を分けている箇所があり8086でも動くような仕組みになってました（動作確認はしてません）が今はなくなってます
- SMPに対応
- バイナリの形式としてELFにも対応しているっぽい
#if defined(__ELF__)がkernel/main.cのなかにいます
それではちょっとコードを見てみたいと思います。まずはkernel/arch/i386/memory.cから。このファイルはページングの処理をしています。色々と関数はありますが名前からarch_enable_paging()がページングの初期化するんだろーなと判断できますね。
PUBLIC int arch_enable_paging(struct proc * caller, const message * m_ptr)
arch_enable_paging()はこのような流れで呼ばれます。
do_vmctl() at kernel/system/do_vmctl.c |-> arch_enable_paging() at kernel/arch/i386/memory.c
ところでMinixの場合、システムコールはsys_XXXな名前になってます。そしてそれの処理はdo_XXXな感じです。
# define SYS_VMCTL (KERNEL_CALL + 43) /* sys_vmctl() */
割り込みベクタへの登録は以下のような処理です。mapはマクロです。
map(SYS_VMCTL, do_vmctl); /* various VM process settings */
sys_vmctl()はシステムコールなのでカーネルがソフトウェア割り込みとして受け取り、メッセージングでvmサーバ（servers/vm/main.c）と通信しつつページングの処理が行われるようです。ページングに関する処理はarch_enable_paging()が最初の間口になっていますが、実際の処理は他の関数で行います。cr3レジスタの切り替えはkernel/arch/i386/klib.Sにある__switch_address_space()、ページングを有効にするのはkernel/arch/i386/memory.cにあるvm_enable_paging()が行います。
__switch_address_space()はシンプルなアセンブラコードです。処理の内容としてはproc構造体メンバ変数の値を必要に応じてcr3にロードするのと、eaxレジスタの指すアドレスに%edxの値が設定されるってところですね。
/*===========================================================================*/ /* __switch_address_space */ /*===========================================================================*/ /* PUBLIC void __switch_address_space(struct proc *p, struct ** ptproc) * * sets the %cr3 register to the supplied value if it is not already set to the * same value in which case it would only result in an extra TLB flush which is * not desirable */ ENTRY(__switch_address_space) /* read the process pointer */ mov 4(%esp), %edx /* enable process' segment descriptors */ lldt P_LDT_SEL(%edx) /* get the new cr3 value */ movl P_CR3(%edx), %eax /* test if the new cr3 != NULL */ cmpl $0, %eax je 0f /* * test if the cr3 is loaded with the current value to avoid unnecessary * TLB flushes */ mov %cr3, %ecx cmp %ecx, %eax je 0f mov %eax, %cr3 /* get ptproc */ mov 8(%esp), %eax mov %edx, (%eax) 0: ret
P_LDT_SEL、P_CR3は普段見慣れないと思いますが、これはマクロでproc構造体の先頭からnバイト目の値を取得しています。これで構造体のメンバーにアクセスするという形です。
cのコードからは以下のように呼ばれます。
__switch_address_space(proc, get_cpulocal_var_ptr(ptproc))
現バージョンではSMPに対応しているのでarch_enable_paging()の1番目の引数のプロセス構造体の他に対象のcpuを渡してあげます。
もう一つ重要なvm_enable_paging()はこのような短い関数です。使用している変数名とか関数名を見れば説明不要な気もしますw
PRIVATE void vm_enable_paging(void) { u32_t cr0, cr4; int pgeok; psok = _cpufeature(_CPUF_I386_PSE); pgeok = _cpufeature(_CPUF_I386_PGE); cr0= read_cr0(); cr4= read_cr4(); /* First clear PG and PGE flag, as PGE must be enabled after PG. */ write_cr0(cr0 & ~I386_CR0_PG); write_cr4(cr4 & ~(I386_CR4_PGE | I386_CR4_PSE)); cr0= read_cr0(); cr4= read_cr4(); /* Our first page table contains 4MB entries. */ if(psok) cr4 |= I386_CR4_PSE; write_cr4(cr4); /* First enable paging, then enable global page flag. */ cr0 |= I386_CR0_PG; write_cr0(cr0 ); cr0 |= I386_CR0_WP; write_cr0(cr0); /* May we enable these features? */ if(pgeok) cr4 |= I386_CR4_PGE; write_cr4(cr4); }
単にページングを有効にするだけならcr3にページディレクトリの先頭アドレスをセットするのとcr0のPGビットをONにするだけでOKですが、MinixではPSEとPGEもサポートしてますね。
ページングはこれくらいにして次はSMPを見てみましょう。SMPに関する処理はkernel/main.cのmain()の一番最後にbsp_finish_booting()を呼び出すことで実施します。ちなみにbspとはBootstrap Processorの略で1個目のCPUになります。CPUが複数あった場合にどれがbspになるかはハードウェア次第です。2個目以降はAP（Application Processor）と呼びます。x86系のcpuでSMPに興味のある人はIntelが提供しているMultiProcessor Specificationを読むことをお勧めします。APを見つけて初期化していくというのは基本的にMultiProcessor Specificationの通りにやるだけなので割愛しますね(m´・ω・｀)m ゴメン… もしくは、この辺を見てみてください。
Minixの場合、cpuに関する情報は以下のcpu_info構造体の配列で持っています。CONFIG_MAX_CPUSは現状1で設定されているようです。まだ複数に対応するのはデフォルトになってないんですね。
EXTERN struct cpu_info cpu_info[CONFIG_MAX_CPUS];
さて、SMPに対応というところで変わった部分としてプロセスのランキューも変わったようです。この辺りのデータはkernel/cpulocals.hに定義されています。マクロとかあって面倒なんですが、1CPUにつきランキューが1個という対応になっているように見えます。現在の最新リリースであるMinix 3.1.8だとランキュー自体は1個です。下の関数は次に実行するプロセスを決定する処理を行ってますが、このなかのrdy_headを求める箇所がそのcpuのランキューを取得している箇所ですね。
/*===========================================================================* * pick_proc * *===========================================================================*/ PRIVATE struct proc * pick_proc(void) { /* Decide who to run now. A new process is selected an returned. * When a billable process is selected, record it in 'bill_ptr', so that the * clock task can tell who to bill for system time. * * This function always uses the run queues of the local cpu! */ register struct proc *rp; /* process to run */ struct proc **rdy_head; int q; /* iterate over queues */ /* Check each of the scheduling queues for ready processes. The number of * queues is defined in proc.h, and priorities are set in the task table. * If there are no processes ready to run, return NULL. */ rdy_head = get_cpulocal_var(run_q_head); for (q=0; q < NR_SCHED_QUEUES; q++) { if(!(rp = rdy_head[q])) { TRACE(VF_PICKPROC, printf("cpu %d queue %d empty\n", cpuid, q);); continue; } assert(proc_is_runnable(rp)); if (priv(rp)->s_flags & BILLABLE) get_cpulocal_var(bill_ptr) = rp; /* bill for system time */ return rp; } return NULL; }
ここで、get_cpulocal_var()はどんな感じの処理かというとマクロでget_cpu_var()を呼び出してます。この時にnameはrun_q_headになりますがcpuidは？というと、
#define get_cpulocal_var(name) get_cpu_var(cpuid, name)
kernel/kernel.hで以下のように定義がされてます。
#ifndef CONFIG_SMP /* We only support 1 cpu now */ #define CONFIG_MAX_CPUS 1 #define cpuid 0 /* this is always true on an uniprocessor */ #define cpu_is_bsp(x) 1 #else #include "smp.h" #endif
CONFIG_SMPが定義されている場合は当然smp.hを読みますね。これは最終的にkernel/arch/i386/include/arch_smp.hの以下のマクロになります。
/* returns the current cpu id */ #define cpuid (((u32_t *)(((u32_t)get_stack_frame() + (K_STACK_SIZE - 1)) \ & ~(K_STACK_SIZE - 1)))[-1])
get_stack_frame()は名前通りの動きするだろ常識(ryってなりますよね。実際↓のようになってます。
#ifndef __GNUC__ /* call a function to read the stack fram pointer (%ebp) */ _PROTOTYPE(reg_t read_ebp, (void)); #define get_stack_frame(__X) ((reg_t)read_ebp()) #else /* read %ebp directly */ #define get_stack_frame(__X) ((reg_t)__builtin_frame_address(0)) #endif
そして、これは何を最終的に見ているのか？というと、多分proc構造体のp_cpuかなと。理由としてはLinuxのcurrent_thread_info()っぽい感じでproc構造体を取得するんだろうという勝手な想像と、プロセス毎にどのcpuの上で動いているのか分かるはずだろうという適当な理由です。ちゃんとソースを追っていません＞＜
struct proc { struct stackframe_s p_reg; /* process' registers saved in stack frame */ struct fpu_state_s p_fpu_state; /* process' fpu_regs saved lazily */ struct segframe p_seg; /* segment descriptors */ proc_nr_t p_nr; /* number of this process (for fast access) */ struct priv *p_priv; /* system privileges structure */ u32_t p_rts_flags; /* process is runnable only if zero */ u32_t p_misc_flags; /* flags that do not suspend the process */ char p_priority; /* current process priority */ u64_t p_cpu_time_left; /* time left to use the cpu */ unsigned p_quantum_size_ms; /* assigned time quantum in ms FIXME remove this */ struct proc *p_scheduler; /* who should get out of quantum msg */ unsigned p_cpu; /* what CPU is the process running on */
そしてget_cpu_var()に戻るとこれもマクロでCPULOCAL_STRUCT構造体の配列からメンバ変数のname(今はrun_q_head)にアクセスします。
#define get_cpu_var(cpu, name) CPULOCAL_STRUCT[cpu].name
CPULOCAL_STRUCTはkernel/cpulocals.hで定義されています。そのなかでrun_q_headはこんな風にマクロを使って定義されてます。
/* CPU private run queues */ DECLARE_CPULOCAL(struct proc *, run_q_head[NR_SCHED_QUEUES]); /* ptrs to ready list headers */
ちなみにDECLARE_CPULOCALはこれです。
#define DECLARE_CPULOCAL(type, name) type name
そんなこんなで、カレントのcpuが分かるとそれがCPULOCAL_STRUCT構造体の配列のインデックスになり、どこからランキューを取得すれば良いかが分かるという流れですね( ´ー｀)フゥー．．．
それではカーネルはこれくらいにして次はサーバを見てみましょうか。こっちは色々と増えてますが個人的に名前から興味があるのはvfs、vm、sched辺りです.
[masami@rune:~/tmp/minix]$ ls servers . .. apfs avfs devman ds ext2 hgfs inet init ipc is iso9660fs lwip Makefile Makefile.inc mfs pfs pm procfs rs sched vfs vm
オペレーティングシステム第3版のときと比べ、以下のような変化があります
- vfsサーバの追加
- vmサーバの追加
ページングのように新機能の他にいくつかの処理がPMサーバから移動してきている
- schedサーバの追加
vmはカーネルでみたようにページングが使われるようになったのでこれに関するサーバです。vfsはその名の通りですね。今時のカーネルとしてはサポートされてて当然な機能と言えますがオペレーティングシステム第3版の時点ではサポートされていませんでした。プロセスのスケジューリングは前からあったけどschedサーバとして分離されたようですね。ということでschedサーバを見てみます。Minixのサーバは通常のプロセスとしてmain()で始まりwhileで無限ループしながらメッセージが届くのを待ち、メッセージの種類に応じて何かしらの処理を行います。この部分を見てみるとSCHEDULING_INHERIT、SCHEDULING_START、SCHEDULING_STOP、SCHEDULING_SET_NICE、SCHEDULING_NO_QUANTUMがこのサーバで行う処理のようです。これらの処理の実態はservers/sched/schedule.cにあります。
switch(call_nr) { case SCHEDULING_INHERIT: case SCHEDULING_START: result = do_start_scheduling(&m_in); break; case SCHEDULING_STOP: result = do_stop_scheduling(&m_in); break; case SCHEDULING_SET_NICE: result = do_nice(&m_in); break; case SCHEDULING_NO_QUANTUM: /* This message was sent from the kernel, don't reply */ if (IPC_STATUS_FLAGS_TEST(ipc_status, IPC_FLG_MSG_FROM_KERNEL)) { if ((rv = do_noquantum(&m_in)) != (OK)) { printf("SCHED: Warning, do_noquantum " "failed with %d\n", rv); } continue; /* Don't reply */ } else { printf("SCHED: process %d faked " "SCHEDULING_NO_QUANTUM message!\n", who_e); result = EPERM; } break; default: result = no_sys(who_e, call_nr); }
まずdo_start_scheduling()ですが、これはプロセスに対してcpu時間を割り当ててその後sys_schedctl()、 sys_schedule()と呼んでいく流れです。do_nice()、do_noquantum()はプロセスの優先度を変更した後にsys_schedule()を呼び出します。do_stop_scheduling()はプロセスのschedproc構造体のflags変数を0に設定して、もうスケジューリング不要だよって印を設定しているようですね。do_start_scheduling()から呼ばれるsys_sched()はkernel/system/do_schedule.cにあるdo_schedule()が実際の処理ですが、この中では大したことはしていなくてreturnの戻り値になるsched_proc()がメインです。このsched_procではプロセスの状態に応じてRTS_SET、RTS_UNSETを使ってプロセスをランキューへ登録したり外したりします。
/* Set flag and dequeue if the process was runnable. */ #define RTS_SET(rp, f) \ do { \ const int rts = (rp)->p_rts_flags; \ (rp)->p_rts_flags |= (f); \ if(rts_f_is_runnable(rts) && !proc_is_runnable(rp)) { \ dequeue(rp); \ } \ } while(0) /* Clear flag and enqueue if the process was not runnable but is now. */ #define RTS_UNSET(rp, f) \ do { \ int rts; \ rts = (rp)->p_rts_flags; \ (rp)->p_rts_flags &= ~(f); \ if(!rts_f_is_runnable(rts) && proc_is_runnable(rp)) { \ enqueue(rp); \ } \ } while(0)
上記マクロ内のenqueue()、dequeue()はkernel/proc.cにいます。これら本のバージョンでも存在し、処理の概要は同じですが実装は多少変わってます。
もう一つのシステムコールsys_schedctl()はkernel/system/do_schedctl.cにいます。
/*===========================================================================* * do_schedctl * *===========================================================================*/ PUBLIC int do_schedctl(struct proc * caller, message * m_ptr) { struct proc *p; unsigned flags; int priority, quantum, cpu; int proc_nr; int r; /* check parameter validity */ flags = (unsigned) m_ptr->SCHEDCTL_FLAGS; if (flags & ~SCHEDCTL_FLAG_KERNEL) { printf("do_schedctl: flags 0x%x invalid, caller=%d\n", flags, caller - proc); return EINVAL; } if (!isokendpt(m_ptr->SCHEDCTL_ENDPOINT, &proc_nr)) return EINVAL; p = proc_addr(proc_nr); if ((flags & SCHEDCTL_FLAG_KERNEL) == SCHEDCTL_FLAG_KERNEL) { /* the kernel becomes the scheduler and starts * scheduling the process. */ priority = (int) m_ptr->SCHEDCTL_PRIORITY; quantum = (int) m_ptr->SCHEDCTL_QUANTUM; cpu = (int) m_ptr->SCHEDCTL_CPU; /* Try to schedule the process. */ if((r = sched_proc(p, priority, quantum, cpu) != OK)) return r; p->p_scheduler = NULL; } else { /* the caller becomes the scheduler */ p->p_scheduler = caller; } return(OK); }
ここで気になるのは最後のif-else文にあるコメントですね。カーネルがスケジューラになる場合と、このシステムコールを呼んだプロセスがスケジューラになるってことですよね？ プロセスの構造体にあるp_schedulerのコメントを見るとcpu時間を使い切った時にカーネルが処理するのか、それともschedサーバが処理するかってことでしょうかね。
struct proc *p_scheduler; /* who should get out of quantum msg */
kernel/proc.cにあるproc_no_time()がそれっぽいですね。ただし、p_scheduleが設定されていたとしてもプリエンティブ可能で無い場合はカーネル側でcpu時間を割り当てています。schedサーバが処理を行う場合はnotify_scheduler()が呼ばれます。
PUBLIC void proc_no_time(struct proc * p) { if (!proc_kernel_scheduler(p) && priv(p)->s_flags & PREEMPTIBLE) { /* this dequeues the process */ notify_scheduler(p); } else { /* * non-preemptible processes only need their quantum to * be renewed. In fact, they by pass scheduling */ p->p_cpu_time_left = ms_2_cpu_time(p->p_quantum_size_ms); #if DEBUG_RACE RTS_SET(p, RTS_PREEMPTED); RTS_UNSET(p, RTS_PREEMPTED); #endif } }
notify_scheduler()はp->p_scheduler->p_endpointに設定されているプロセスに対してメッセージを送ります。この場合、宛先はschedサーバですよね。
if ((err = mini_send(p, p->p_scheduler->p_endpoint, &m_no_quantum, FROM_KERNEL))) { panic("WARNING: Scheduling: mini_send returned %d\n", err); }
そうすると、schedサーバのメインループにあるswitch文でSCHEDULING_NO_QUANTUMに当たってcpu時間の割り当てが行われると。
それでは次にvmサーバを見てみましょう。vmディレクトリ以下にはファイルもそこそこあるのですがファイル名からmmap、fork、exit、ページフォルトなどの処理を行って入るのが見て取れます。これも先ほどのschedサーバと同様にmain()のループでメッセージを処理している部分を見てみます。
if (msg.m_type == VM_PAGEFAULT) { if (!IPC_STATUS_FLAGS_TEST(rcv_sts, IPC_FLG_MSG_FROM_KERNEL)) { printf("VM: process %d faked VM_PAGEFAULT " "message!\n", msg.m_source); } do_pagefaults(&msg); /* * do not reply to this call, the caller is unblocked by * a sys_vmctl() call in do_pagefaults if success. VM panics * otherwise */ continue; } else if(c < 0 || !vm_calls[c].vmc_func) { /* out of range or missing callnr */ } else { if (vm_acl_ok(who_e, c) != OK) { printf("VM: unauthorized %s by %d\n", vm_calls[c].vmc_name, who_e); } else { SANITYCHECK(SCL_FUNCTIONS); result = vm_calls[c].vmc_func(&msg); SANITYCHECK(SCL_FUNCTIONS); } }
ページフォルトの場合はdo_pagefaults()を呼んでいるのが分かります。それ以外の場合はelseのブロックに入り、vm_calls[c].vmc_func(&msg);という形で関数の呼び出しが行われます。vm_callsはmain.cのsef_cb_init_fresh()で設定されています。forkの場合はservers/vm/fork.cのdo_fork()が呼ばれてそこからさらにsys_fork()によってカーネルのdo_fork()が呼ばれるようになっています。ちなみにソースはGNU GLOBALで索引付けして読んでますが関数呼び出しと違ってメッセージのやりとりは追いかけ辛いですね＞＜
話をdo_fork()に戻しまして、これはpmサーバのdo_fork()、カーネルのsys_fork()、do_fork()、vmサーバのdo_fork()、vfsサーバのpm_fork()あたりが関連して動いているようですが追いかけるのが面倒くさくなってあきらめましたorz
まとめ
さらっと見てきましたがオペレーティングシステム第3版から結構変わりましたね。というか、本のバージョンだと今時普通な機能が入っていなかったという面もあると思いますが。でも教育用のOSという側面から機能をシンプルに抑えてるという部分も本から読み取れたりしますし、それはそれで良いかなと。むしろ足りない機能を追加するハックがしやすいと思えば良いのですヽ(*´∀｀)ノ キャッホーイ!! 最新のコードでもマルチプロセッサ対応の向上とか64bit対応とか色々やることは多そうですし興味のある人は手を出してみてはどうですか？
