YATOS - Yet Another Teachable Operating System

[1] 本プログラムについて
  本プログラムは, 大学の学部学生程度の知識(3-4年次を想定）の範囲で, 
オペレーティングシステムの基本的な考え方を学ぶための教材とすることを想
定して実装した簡単なオペレーティングシステムカーネルです。

名称は, Yet Another Teachable Operating System(以下YATOSと略す）です。
  スイス連邦工科大学チューリッヒ校の教育用マイクロカーネルである
Topsy( http://www.tik.ee.ethz.ch/~topsy/ )の開発が停止していること,
近年のFreeBSD, Linux, Minixが実用指向を目指しており, OSの設計や実装
を学ぶには, プログラムコードとして処理ロジックが見通しにくく, 教育に
向かないことから新規のOSカーネルを実装し直しています。

OSの実装・運用上エラー処理や互換性の担保は重要なのですが, 本筋の
ロジックが見えにくくなるため, YATOSでは, 各種デバイスへのワークアラウ
ンドや従来のUNIX OSの仕様や設計との互換性よりも, OSカーネルの動作を
より簡易に示すことを重視した設計を行っています。

スイス連邦工科大学チューリッヒ校のTopsyを参考に機能設計を行っています。
また, OSの構成設計・実装については, 以下のOSの考え方を参考にしています。

- カーネギーメロン大学 Mach-3/ユタ大学 Mach-4
- Microsoft Windows NT 3.1-3.51
- BeOS/NewOS(haiku)
- Xinu/Embedded Xinu
- Minix V1.1
- L4
- Mungi
- QNX
- OS-9
- Sanos
- xv6
- BTRON仕様
- uITRON仕様

X86-64機でのCPU初期化処理/SLABについては, 「０から作るソフトウェア開発」
( http://softwaretechnique.jp/index.html )の実装を参考にしています。

[2] 機能概要

YATOSは, 近年のOSが持つ基本機能と設計・実装の説明を行えるよう以下の機
能を実装しています。

1. マルチスレッド
多重プログラミング環境での実行スレッド間での同期（mutexによる相互排他や
ランデブ同期）の考え方を説明することを想定し, ユーザプロセスやカーネル
空間内に複数の軽量プロセス（スレッド）を生成する機能を搭載しています。

また、プリエンプションの説明を想定し, 優先度付きスレッドのスケジューリ
ングには, FCFS(First Come First Served - 到着順方式)優先度スケジューリ
ングを採用しています。 

また、タイムシェアリングシステムの考え方の基礎を説明することを
想定し, 優先度を付けない(優先度0)スレッドについては, 単純な
ラウンドロビンスケジューリングを行うようにしています。

2. プリエンプティブカーネル

近年のOSではメディア処理などに必要な高応答性を確保する観点から, OSカー
ネル内部のサービスを実行中であっても, 外部デバイスからの要求に応じて, 
より優先度の高いスレッドに処理を移行します（カーネルレベルプリエンプ
ション）。

YATOSでは, OSカーネルがカーネル動作中でのCPUの横取り可否を判断し, 
カーネル動作中でのCPUの横取り制御を行います。

3. ページ管理機構
ページの外部断片化や内部断片化に関する説明および一般的に普及している対
策を説明することを想定し, buddy アルゴリズムによる物理メモリページ管理
とSlabメモリアロケータ(*2)を搭載しています。

4. マルチプロセス
マルチプロセスモデルの説明とその原理を説明することを想定し, ユーザプ
ロセス空間には, MMUの仮想<->物理アドレス変換機構を利用した多重仮想化
を行い, 互いに独立したアドレス空間を割り当てています。

5. シングルアドレス空間（SAS）によるカーネルメモリレイアウト
プロセス<->カーネル間での安全なデータの受け渡し方式(copy in/out), 
プロセス間でのデータ通信をより高速に実現する方式を説明
することを想定し, シングルアドレス空間によるカーネルメモリレイアウトを
採用しています。

カーネルの仮想メモリ領域とユーザプロセスのメモリ領域を同一のアド
レス空間上に配置する仮想メモリレイアウト(Single Address Space)を
採用しています。

YATOSでは, 全ての物理メモリをカーネル空間から直接アクセスできるように
アドレス空間を構成しています。

全ての物理メモリをカーネル空間から直接アクセスできるようにすることで, 
より高速なプロセス間通信を実現できます。これは, 以下の理由によるもので
す。

- カーネル内の中間バッファを介してコピーする際に必要な
  ユーザプロセス<->バッファ間でのデータコピー時間を削減

- アドレス空間切り替えによるTLBエントリのフラッシュ・
  再ロード時間を削減

また, ユーザプロセス間でのデータ通信時にカーネル内の中間バッファ
領域を用意することなくユーザメモリの内容を直接参照・コピーすることが
でき, メモリ消費を抑えることができます。

6. メッセージパッシング
YATOSでは, スレッド間での固定長メッセージ通信機構を搭載しています。
これは, 以下の考え方を説明するための機能です。

- 多重プログラミング環境でのランデブ同期

- OSサービスをユーザスレッド<->カーネルスレッド間通信により実現し, 
  OSカーネルの肥大化防止と保守性の担保を実現する設計手法
 （マイクロカーネルアーキテクチャ）

YATOSでは, 一部の例外を除いて, ユーザプロセスからカーネルサービスの呼出しは, 
ユーザスレッドからカーネル内スレッドへのメッセージ通信によって実現して
います。

7. 非同期イベント
スレッド間での非同期イベント(タスク例外処理）の説明のために, OSカーネ
ルからユーザランドのサブルーチンを呼び出す機構を搭載しています。
ユーザランドでUNIX signal相当の機能を実現するための基盤機能です。

なお, 非同期イベントは, OSカーネル内でキューイングされ, イベント
発生回数分ユーザランドに通知されます。

8. システムコール
YATOSでは, OSカーネルが以下の9つのシステムコールを処理します。

  1) register_common_event_handler
     ユーザ空間中の共通イベントハンドラのアドレスをカーネルに登録する

  2) return_from_event_handler
     ユーザ空間のイベントハンドラからカーネルに復帰し, イベントハンド
     ラ中で書き換えたコンテキストの内容を復元する

  3) thr_yield
     自スレッドのCPUを他のスレッドに受け渡す

  4) thr_exit
     自スレッドを終了する

  5) thr_getid
     自スレッドのIDを取得する

  6) thr_wait
     終了した他のスレッドのスレッドIDと終了コードを取得する

  7) lpc_send
     他のスレッドにメッセージを送信する

  8) lpc_recv
     他のスレッドからメッセージを受信する

  9) lpc_send_and_reply
     他のスレッドにメッセージを送信し, 送信先からの返信を待ち受ける

9. ユーザAPIライブラリ
   ユーザプログラムからOSカーネルやカーネル内システムサービスを利用す
   るためのAPIライブラリを搭載しています。

   トップディレクトリから

   cc -I include -nostdlib -T user/user.lds lib/crt0.o \
   ユーザプログラムのオブジェクトファイル(.o) -o 実行ファイル名 \
   -Llib -lyatos

   を実行することでユーザプログラムを編纂(リンク)します。

   1) lib/libyatos.a
      カーネル層のサービスやOSが提供する基本機能を利用する低レベル
      ライブラリです. 以下の機能を提供します。
   
      - ユーザスレッドの生成(yatos_proc_create_thread)
      - 自スレッドの終了(yatos_thread_exit)
      - 自スレッドのスレッドIDの取得(yatos_thread_getid)
      - 子スレッドの終了待ち合わせ(yatos_thread_wait)
      - 自スレッドのCPUを解放し他のスレッドに明け渡す
        (yatos_thread_yield)
      - 他のスレッドのCPU使用量を獲得する(yatos_proc_get_thread_resource)
      - 自スレッドが提供するシステムサービスの登録
        (yatos_register_service)
      - 自スレッドが提供するシステムサービスの登録破棄
        (yatos_unregister_service)
      - サービス名からメッセージ送信先を探査する
        (yatos_lookup_service)
      - 他のスレッドからメッセージを受信する
        (yatos_lpc_recv)
      - 他のスレッドにメッセージを送信する
        (yatos_lpc_send)
      - 他のスレッドにメッセージを送信し, 返信を待ち合わせる
        (yatos_lpc_send_and_reply)
      - 他のスレッドに非同期イベントを送出する(yatos_proc_send_event)
      - 非同期イベントハンドラを登録する
        (yatos_register_user_event_handler)
      - 自スレッドのイベントマスクを取得する(yatos_get_event_mask)
      - 自スレッドのイベントマスクを設定する(yatos_set_event_mask)
        * イベントマスク操作
          - イベントマスクをクリアする(ev_mask_clr)
          - イベントマスク中の特定のイベントが設定されていることを確認する
	    (ev_mask_test)
          - イベントマスクが空であることを確認する(ev_mask_empty)
          - イベントマスク中の所定のイベント位置をマスクする
            (ev_mask_set)
          - イベントマスク中の所定のイベント位置をクリアする
            (ev_mask_unset)
          - イベントマスクの排他的論理和を取得する
            (ev_mask_xor)
          - イベントマスクの論理積を取得する
            (ev_mask_and)
          - マスク不能イベントを除いて, イベントを全マスクしたイベントマスクを取得する
            (ev_mask_fill)
      - 送信先スレッドの所属するプロセス中のイベント受信可能なスレッドにイベントを配送する
        (yatos_proc_send_proc_event)
      - 送信先スレッドの所属するプロセス中の全スレッドにイベントを配送する
        (yatos_proc_bcast_proc_event)
      - 自プロセスのヒープ領域を伸縮する
        (yatos_vm_sbrk)
      - デバッグ用コンソール(シリアル）に書式指定文字列を出力する
        (yatos_printf)
      - 書式指定文字列をメモリ中に書き込む
        (yatos_snprintf)

   2) lib/crt0.o
      ユーザランド用のスタートアップルーチンです。

(*1) カーネルが現在実行中のスレッドからCPUの実行権を奪い取り他のより優
先度の高いスレッドにCPUを強制的に割り当て直すこと。

(*2) The Slab Allocator: An Object-Caching Kernel Memoryの論文を参考に
    実装
    https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/
    bonwick.ps

[3] YATOSにおけるマイクロカーネルアーキテクチャに対する考え方

     近年普及しているOSカーネルの多くは, マイクロカーネルアーキテクチャ
   を採用しています(Microsoft Windows NT/MacOS-Xなど)。

     YATOSでも, 近年のOSの考え方を示す観点からマイクロカーネルアーキテ
   クチャを採用しています。 

   　一般的なマイクロカーネルの設計方針と異なり, YATOSでは
   マイクロカーネル機能の最小化（カーネル以外で実装可能な場合は, 
   ユーザランドに機能を持っていく考え方, 一般には, IPC, VM, Threadのみを特権空間の
   カーネル含める）を重視しない設計を採用しています。

     YATOSではユーザランドで持つ方がカーネル層で機能を実装するより, 
   処理ロジックが複雑化するような場合は,カーネル層に機能実装しており,
   純粋なマイクロカーネルよりカーネル内に搭載されるサービスが比較的
   多くなっています（将来的に設計の見直しを図るかもしれませんが）。

[4] コンパイル環境

以下の開発環境でのコンパイルを確認しています。

Cコンパイラ・・・gcc-4.8.3, LLVM clang-3.4.2
アセンブラ・・・ GNU assembler 2.23.52.0.1
リンカ ・・・ GNU ld 2.23.52.0.1

[5] 実行環境

現在のところ, 実行環境としてQEmu(http://wiki.qemu.org/Main_Page)の
X86-64システムシミュレータでの動作を確認しています。

QEmu・・・QEMU emulator version 2.0.0

[6] コンパイル手順

本OSの提供機能の基本動作確認を行うには以下の手順を踏みます。

1) カーネルの構築時コンフィグレーションを設定

トップディレクトリから
   make menuconfig
を実行することで, メニューが出てきます.

  設定項目には, カーネル構築時のコンパイルオプションやメッセージ出力先のシ
リアルポートの選択がありますが, 通常設定を変更する必要はありませんので,
Exitを選択して<ENTER>を押します。

2) カーネルのコンパイル

トップディレクトリから
   make
を実行します。

コンパイルが完了するとトップディレクトリにkernel.elfというカーネルの実
行イメージとuser/ディレクトリにuser1.elfというユーザランドのデモプログ
ラムができます。

3) 実行

トップディレクトリから
make run-nox
を実行するとOSカーネルが起動し, ユーザプログラム（機能確認用デモ）
が動作します。なお、キーボードからCtrl-A, x のキーシーケンスを入力することで
QEmuを終了させることができます。

実行例
---
Initialize...
boot-map-kernel : [0x0000000000000000, 0x00000000bfffffff] to 0xffff800000000000
map-kernel : [0x0000000000000000, 0x000000013fffffff] to 0xffff800000000000
High APIC I/O region : [0x00000000fe000000, 0x0000000100000000] to 0xfffffffffc000000
OS kernel
page-pool: 984001/1048318 free pages(3843 MiB free)
[256]: 0: argv[0]: user1.elf
[256]: 1: argv[1]: arg1
[256]: 2: argv[2]: arg2
[256]: 0: environ[0]: TERM=yatos
[256]: 1: data_bss: 0, data 8000
[256]: 100: data_bss: 1356, data a6ac
[256]: floating test
[256]: sbrk(0) old-heap=0x0000000000407000
[256]: sbrk(10) old-heap=0x0000000000407000
[256]: sbrk(4M) old-heap=0x0000000000408000
[256]: sbrk(-2M) old-heap=0x0000000000808000
[256]: sbrk(0) old-heap=0x0000000000608000
[256]: heap access test: 0x0000000000607000 - 0x0000000000608000
[256]: set event full mask.
[256]: mask[0], 0xfffffdff
[256]: mask[1], 0xffffffff
[256]: create-thread start:0x0000000000400146 stack:0x0000000000607ff8
[257]: new_thread(arg=0x0000000000001234)
[256]: create-thread rc=0 id=257
[256]: 0 th Hello World
[256]: 1 th Hello World
[256]: 2 th Hello World
[256]: 3 th Hello World
[256]: 4 th Hello World
[256]: 5 th Hello World
[256]: 6 th Hello World
[256]: 7 th Hello World
[256]: 8 th Hello World
[256]: 9 th Hello World
[257]: unset event mask EV_SIG_USR1.
[256]: wait for child thread's preparation.
[257]: mask[0], 0xbffffdff
[257]: mask[1], 0xffffffff
[256]: unset event mask EV_SIG_USR2.
[257]: consume user cpu resources, please wait
[256]: mask[0], 0x7ffffdff
[256]: mask[1], 0xffffffff
[256]: send event (id, data)=(30, 0x00000000deaddead)
[257]: user_handler(30, 0x0000000000607c90, 0x0000000000607c90), data=0x00000000deaddead and return
[256]: send event rc = 0
[257]: wait parent thread's event test completion.
[256]: send proc event (id, data)=(31, 0x00000000deadbeef)
[256]: user_handler(31, 0x00003ffffffffaf9, 0x00003ffffffffaf9), data=0x00000000deadbeef and return
[256]: send event rc = 0
[256]: send proc broad cast event (id, data)=(30, 0x000000000000dead)
[257]: user_handler(30, 0x0000000000607c70, 0x0000000000607c70), data=0x000000000000dead and return
[256]: wait any thread
[257]: return 0
[256]: wait-thread rc=0 id=257 code=0
[256]: unset event mask of EV_SIG_USR1.
[256]: user_handler(30, 0x00003ffffffffb09, 0x00003ffffffffb09), data=0x000000000000dead and return
[256]: mask[0], 0x3ffffdff
[256]: mask[1], 0xffffffff
[256]: consume user cpu resources, please wait
[256]: get resource usage of this thread and children.
[256]: result (rc, sys, user, child-sys, child-user)=(0, 5, 58, 1, 293)
[256]: process stack demand paging test.
[256]: process stack demand paging test OK
[256]: return 0
---

[6] 開発環境構築手順について

ツールチェイン構築用のシェルスクリプトを tools/toolchain/cross.sh に配置しています。

x86-64 Linux環境で, cross.sh と同じディレクトリに 

  tools/newlib/yatos-newlib-2_4_0.patch
  tools/gdb/gdb-7.10-qemu-x86-64.patch

を配置し,

/bin/sh ./cross.sh

を実行すると, 
${HOME}/cross/yatos/構築日
(*) 構築日はYYYY-MM-DD形式

配下にx86_64-elf-のツールチェインを構築・インストールします。
${HOME}/cross/yatos/currentという名前で, 上記ディレクトリにシンボリックリンクを
作成しますので, 

${HOME}/cross/yatos/current/bin

にパスを通しておくことで直近にビルドしたツールチェインを利用することができます。

cp lib/libyatos.a  ${HOME}/cross/yatos/current/rfs/usr/lib

を実行し, 低レベルライブラリをライブラリディレクトリにコピーしておくことで,
以下のようにクロスコンパイラを使用したアプリケーション構築を行えます。

x86_64-elf-gcc  -o 実行形式ファイル名 Cソースファイル名  -lc -lm -lyatos

例:
x86_64-elf-gcc  -o hello.elf hello.c -lc -lm -lyatos

作成した実行形式は, .elfの拡張子を付けて, user/ ディレクトリに配置します。

hal/x86-64/grub/iso/grub.cfg
を編集し, 作成したプログラムをGRUB2のモジュールとして指定することで, make run実行時に
読み込まれるようになります(実行形式は, make run時に生成されるisoファイルの/boot配下に
配置されます)。

GRUB2のモジュールの指定は, 以下の書式で行います:

module2 /boot/実行形式ファイル名 コマンド名 引数1 引数2 ...

例: /boot/user1.elfをコマンド名``user1.elf'' 引数 arg1 arg2 を付けて起動する場合

menuentry "kernel" {
    multiboot2 /boot/kernel.elf
    module2    /boot/user1.elf user1.elf arg1 arg2
}