PCIデバイスが存在するか確認する

PCIデバイスがあるかどうか確認する。一応それっぽいデバイスが表示はされる。

io_inXとio_outX,Printfが既に定義されているものとする。 io_inとio_outはそれぞれのビット数のin,out命令。

enum PCI_CONFIGURATION_REGISTER
{
	VenderID = 0x00, //bit0-15
	DeviceID = 0x00, //bit16-32
	CommandRegister = 0x04, //bit0-15
	StatusRegister = 0x04, //bit16-32
	RevisionRegister = 0x08, //bit0-7
	ClassCode = 0x08, //bit8-31
	CacheLineSize = 0x0C, //bit0-7
	MasterLatencyTimer = 0x0C, //bit8-15
	HeaderType = 0x0C, //bit16-32
	BISTRegister = 0x0C, //bit24-31
};

#define CONFIGURATION_ADDRESS 0x0CF8
#define CONFIGURATION_DATA 0x0CFC
#define CONFIGURATION_DATA1 0x0CFD
#define CONFIGURATION_DATA2 0x0CFE
#define CONFIGURATION_DATA3 0x0CFF

struct PCIConfigHeader{
	uint16 venderID;
	uint16 deviceID;
	uint16 command;
	uint16 status;
	uint8 revision;
	uint8 classCode[3]; //3byte
	uint8 chacheLineSize;
	uint8 latency;
	uint8 header;
	uint8 builtInSelftest;
	uint32 baseAddrReg0;
	uint32 baseAddrReg1;
	uint32 baseAddrReg2;
	uint32 baseAddrReg3;
	uint32 baseAddrReg4;
	uint32 baseAddrReg5;
	uint32 cardBusCISPointer;
	uint16 subSystemVenderID;
	uint16 subSystemID;
	uint32 expansionRomAddr;
	uint32 Reserved0;
	uint32 Reserved1;
	uint8 irqLine;
	uint8 interruptPin;
	uint8 minGrant;
	uint8 maxLatency;
};

//bus=バス番号 dev=デバイス番号,reg=レジスタ番号(bit0-7) func = 機能番号
int WriteConfigAddr(int bus, int dev, int reg, int func)
{
	int data;
	data = 0x80000000 |
		((bus << 16) & 0xFF0000) |
		((dev << 11) & 0xF800) |
		((func << 8) & 0x700) |
		(((reg/4) << 2) & 0xFC);
	io_out32(CONFIGURATION_ADDRESS, data);
	return 0;
}

int ReadConfig32(int bus, int dev, int reg, int func)
{
	WriteConfigAddr(bus, dev, reg, func);
	return io_in32(CONFIGURATION_DATA);
}

int CheckBus(int bus)
{
  int dev;
  for(dev=0; dev<32; dev++)
  {
    int vender,devid;
    int tmp = ReadConfig32(bus, dev, VenderID, 0);
    vender = tmp&0xFFFF;
    devid = (tmp>>16)&0xFFFF;
    if(vender == 0xFFFF) //デバイスは存在しない
			continue;
    Printf("PCI bus %d, dev %d Exist. Vender=%x, DevID=%x\n", bus, dev,vender,devid);
  }
  return 0;
}

int CheckPCI()
{
 for(int i = 0; i < 0x0100; i++)
 {
   CheckBus(i);
 }
 return 0;
}

qemuでCheckPCIを呼び出したら以下のように表示された。

PCI bus 0, dev 0 Exist. Vender=8086, DevID=1237
PCI bus 0, dev 1 Exist. Vender=8086, DevID=7000
PCI bus 0, dev 2 Exist. Vender=1013, DevID=B8
PCI bus 0, dev 3 Exist. Vender=10EC, DevID=8029
PCI bus 0, dev 4 Exist. Vender=1AF4, DevID=1002

Nachosを学ぶ

概要

Nachos(Not Another Completely Heuristic Operating System)はカリフォルニア大学バークレー校で開発された教育用のオペレーティングシステム。

C++で記述されていて、MIPSやx86上のlinuxやSolarisなどで動く・・・んだと思う。

Nachos自体はユーザーレベルで動作し、Nachosのユーザープログラムは MIPSシミュレーターで動作する。

MIPSシミュレーターはディレクトリmachine以下でMachineクラスとして実装されている。userprog/exception.ccあたりも利用しているので machineディレクトリ以外も気をつけなければならないところがあるかも。

クラス一覧

ヘッダファイルからなんとなく読み取ったこと。

• filesysディレクトリ
  • DirectoryEntry (ディレクトリエントリ。ディレクトリ中のファイルを表現する。ファイル名とヘッダのディスク中の位置を保持する(sector))
  • Directory (UNIX-likeのディレクトリ)
  • FileHeader (ファイルヘッダ(UNIXでいうならi-node)ファイル本体がディスク中のどこにあるかといった情報を持つ)
  • FileSystem (2つのうちどちらか。STUBはUNIX関数をラップしたもので,realはディスクの処理をシミュレートする)
  • OpenFile (FileSystemに合わせて2つある。個々のファイルのread,write,closeなどを扱う)
  • SynchDisk (スレッドからのリクエストに対してディスク操作し、割り込みをかけて通知するようにみせる)
• machineディレクトリ
  • Console (コンソールデバイス)
  • Disk (ディスクIOデバイス。セクタ番号でアドレッシング。UNIXファイルをディスクに見立てる)
  • PendingInterrupt (将来発生するのでスケジューリングされる割り込み)
  • Interrupt (ハードウェア割り込みをシミュレートする)
  • Instruction (MIPSプログラムを読み込んだ個々の命令。opCodeはMIPSのopcodeフィールドとは異なる)
  • Machine (シミュレーター)
  • PacketHeader (ネットワークパケットのヘッダ)
  • Network (ネットワークデバイス。固定長のパケットを転送できる。)
  • Statistics (statistics=統計。Nachosの振舞についての統計情報。時間、ディスクIOなど。)
  • Timer (ハードウェアタイマー)
  • TranslationEntry (変換テーブルのエントリ。ページテーブルかTLB(Translation Lookaside Buffer)。どちらも仮想->物理アドレス変換)
• networkディレクトリ
  • MailHeader (Mailのヘッダ)
  • Mail (Mailメッセージ)
  • MailBox (メールボックス)
  • PostOffice (メールボックスへのメッセージの送信と受信を扱う)
• threadsディレクトリ
  • ListElement (単方向リスト。ソートされたリストを利用する場合のためのkeyとvoid* itemを持つ)
  • List (単方向リスト。ListElementを管理する。firstとlastへのポインタを保持)
  • Scheduler (スケジューラ/ディスパッチャ。現在動作しているスレッドと動作可能なスレッドを保持する)
  • Semaphore (セマフォ。Pメソッド(down)とVメソッド(up)がある。)
  • Lock (ロック。BUSYかFREE状態をとる。Acquire(手に入れる),Releaseメソッドがある。必要なら要素を付け足してね、と書いてある。)
  • Condition (condition variable。値を持たない。Wait,Signal,Broadcastメソッドがある。Mesa-styleってなんだろう。)
  • SynchList (synchronized list.Removeするとき空なら要素が追加される間で待つ。同時にアクセスできるのは1スレッドだけ)
  • Thread ("thread control block"を定義。stack(bottom),stackTop,status,machineState(レジスタの状態)などをメンバとして持つ)
• userprogディレクトリ
  • AddrSpace (ユーザプログラムの実行に関する情報を持つが、いまはthreadがCPU状態等を保存してる?)
  • BitMap (ビット列。セット、クリア、テストができる)

Machineクラスメモ

Machineで利用されるOP_xxxという定数は、MIPSのオペコードそのものではなく、変換テーブルを使って変換した後の定数値。

システムコールは例外を発生させることで処理されるが、Halt以外の処理は実装されていない。

Machine::OneInstruction内でMIPS用バイナリコードの読み込み、Machineで利用する内部構造(Instructionクラス)への変換(Decodeメソッド)を行ったのち、命令ごとに処理を行うが、OP_SYSCALLであった場合はMachine::RaiseExceptionが呼び出され、そこから exception.ccのExceptionHandlerが呼び出される。

threadsディレクトリを読む

Nachosのエントリポイントはthreads/main.ccのmain関数。 OSとしての処理の中心はthreadsディレクトリ内のファイルで実装されているようなので、このあたりから見ていく。

mainではInitialize関数でグローバルなデータ構造の初期化(currentThread = new Thread("main")なども)する。コマンドラインオプションに応じたテストの類も行う。

return(0)とあるが、その前のcurrentThread->Finish()時に他のスレッドが無ければ最終的に Cleanup関数を呼び出してその中のExit(0)で終了する。

Threadクラス

int* stackTopとint machineState[MachineStateSize]メンバは場所を変えるなと書かれている。

あと、スタックの容量にも気をつける。

Threadクラスのpublicメソッド

コンストラクタはデバッグ用の名前を引数にとり、nameに設定する。statusをJUST_CREATEDにする以外は、NULLに設定する。

デストラクタはスレッドの解放を行うが、this == currentThreadの場合はスタックの解放が行えないため不正である。スタックの解放にはDeallocBoundedArray関数を用いる。

Forkメソッドは引数にとった関数をスレッドで走らせる。 callerとcalleeが同時に動作実行される事を許す。 StackAllocateメソッドの呼び出しスタックの確保と初期設定を行った後で scheduler->ReadyToRun(this)でスケジューラーに登録する。

Yieldメソッドは他に実行可能なスレッドがあれば、CPUを放棄させる。その場合はscheduler->ReadyToRunメソッドで実行可能プロセスのリストにCPUを放棄したスレッドを追加する。

Sleepメソッドはスレッドを眠らせ、CPUを放棄させる。 Yieldと異なり、スレッドはブロック状態になるので実行可能リストには追加されない。他に実行可能スレッドが無い場合はInterrupt::Idleメソッドを呼び出し続ける。

Finishメソッドはスレッドの実行を終了する。 ThreadRootから処理終了時に呼ばれる。まだ実行中なので、即座にスタックの解放等を行うわけではなく、 threadToBeDestroyedにスレッドをセットしSleepする。実際にスレッドが解放されるのは次回のscheduler->Run()中である。

CheckOverflowメソッドはスタックがオーバーフローしているか確認する。 int* stackの値がStackAllocateメソッドでセットしたSTACK_FENCEPOSTか確認することでオーバーフローが起きたかどうかをチェックする。

setStatusメソッドはスレッドの状態を設定する。

getNameメソッドはデバッグ用のスレッドの名前(コンストラクタで設定)を返す。

Printメソッドはスレッドの名前を表示する。

SaveUserStateメソッドはユーザプログラムを動作させているmachineのレジスタを保存する。 userRegisters[i] = machine->ReadRegister(i)

RestoreUserStateメソッドはユーザプログラムを動作させているmachineのレジスタを復元する。 machine->WriteRegister(i, userRegisters[i])

Threadクラスメンバ変数

変数名	説明
AddrSpace* space	ユーザーコード
int* stackTop	スタックポインタ(スタックトップ)
int machineState[MachineStateSize]	stackTop以外のレジスタ
int* stack	スタックの底.mainスレッド(Initializeで作られるスレッドか)はNULL。
ThreadStatus status	スレッドの状態。ready,running,blocked,just_created
char* name	デバッグ用の名前
int userRegisters[NumTotalRegs]	user-level CPU register state(カーネルコード実行中とユーザコード実行中は別に保存するため)

Threadクラスprivateメソッド

StackAllocateメソッドはForkメソッド内部で使われ、スタックの確保と初期設定を行う。スタックはAllocBoundedArray関数によって確保される。 AllocBoundedArrayはスタックの前後に1ページサイズ(getpagesizeの返り値)ずつ余分に領域を確保する。 i386ではstackTop = stack + StackSize - 4とされているが、-4は大事をとってるだけらしい。スタックにはSWITCH()でThreadRootを呼び出すための値を積んでいる。 machineStateに呼び出す関数やその引数などを設定する。

ThreadRootはアセンブラルーチン。 StartupPc,InitialPc,WhenDonePcレジスタの指す関数を順に実行する。WhenDonePCでthread->Finish()が呼び出されるはずなので、そのあとに処理は続かない。 i386ではInitialPCはESI,InitialArgはEDX,WhenDonePCはEDI,StartupPCはECXである。 ThreadRootが呼び出された時点でこれらのレジスタにはStackAllocateで設定した値がセットされている。おそらくSWITCHでスレッド先頭のmachineStateから読み込まれるのだろう。

例えばmachineState[InitialPC]はESI(%thread)というイメージ。switch.hでの定義の-1はint* stackTopの分(4バイト)の差だろう。

thread先頭からESI=24, EDX=16, EDI=28, ECX=12.

Schedulerクラス

スケジューラー。スレッドの切り替えはswitch.sのSWITCH手続きで行う。

Schedulerクラスpublicメソッド

コンストラクタはreadyListを初期化する。

デストラクタはreadyListを解放する。

ReadyToRunメソッドはスレッドを実行可能状態にし、実行可能スレッドのリストに追加する。 thread->setStatusでREADYをセットし、readyList->Append(thread)で最後尾にスレッドを追加する(エンキュー)。

FindNextToRunメソッドは次に実行すべきスレッドを返す。実行可能なスレッドが無ければNULLを返す。 readyList->Remove()の返り値を返している(デキュー)。

Runメソッドは引数に指定したスレッドを操作させる。切り替わる前のスレッドの状態はRunメソッドが呼び出される前にBLOCKEDかREADYになっているものとみなす。 currentThreadが変更されるのはこのメソッドの内部である。また、threadToBeDestroyedがセットされていればスレッドの切り替え後にそのスレッドを解放する。

PrintメソッドはreadyListの内容を表示する。

Schedulerクラスの変数

名前	説明
List* readyList	実行中で無いが実行可能なスレッドを保持するリスト。キューとして扱う。

SWITCH手続き

void SWITCH(Thread* oldThread, Thread* newThread)となっている。コンテキストスイッチを行うアセンブラルーチンで、CPUに依存する。

どうもswitch.sのうち必要な分だけ抜き出されてswtch.sになってる・・・っぽい。 ThreadRoot手続きもswtch.s(switch.s)にある。

EAXに引数の値(スレッドへのポインタ)をセットして使うので、EAX自体の値は_eax_saveという領域に一時保存して保存、復元する。リターンアドレスを4(%esp)にセットするのはなぜだろう。0(%esp)がSWITCHからのリターンアドレスだと思うのだが。

Semaphoreクラス

Semaphoreクラスpublicメソッド

コンストラクタはセマフォの値の初期値を引数にとる。キューの初期化をする。

デストラクタはキューを解放する。

Pメソッドはdown操作である。 value==0ならばスレッドをスリープする。 valueを1減少させる。

Vメソッドはup操作である。セマフォを待っているスレッドがあれば1つ起こす。 valueを1増加させる。

Semaphoreクラス変数

変数名	説明
List* queue	P(down)でスリープしているスレッドを保持するキュー
char* name	デバッグ用の名前
int value	セマフォの値。常に0以上

Lockクラス

実装が不完全

Conditionクラス

実装が不完全。

メモ：Multiboot Specification

前に調べたことをメモしておく。

Multiboot Specification準拠のブートローダ(つまりはGRUB)からカーネルを起動したときの状態について。

• EAXレジスタ マジックナンバー0x2BADB002
• EBXレジスタ Multibootの情報を持つ構造体へのポインタ
• A20GATE 有効 (メモリアドレス1M以上へのアクセス有効)
• CR0レジスタ ビット31(PG) クリア (ページング無効)
• CR0レジスタ ビット0(PE) セット (32ビットモード)
• EFLAGSレジスタ ビット17(VM) クリア (プロテクトモード)
• EFLAGSレジスタ ビット9(IF)　クリア (割り込み無効)
• ESPレジスタ 未設定
• GDTR ブートストラップローダが作成したセグメント
• IDTR 未設定
• カーネルが読み込まれるのは0x100000番地

アセンブラで書いたカーネルの先頭が0x100000となるようにリンカスクリプトを書く。たぶんこんなの。

ENTRY(_start)
SECTIONS
{
  . = 0x100000;
  .text :{
       *(.start);
       *(.text);
  }
  .data :{
    *(.data);
  }
  .bss :{
    *(.bss);
  }
  end = .;
}

C++のスタートアップ(C++でカーネルコードを書きたい)

以前適当に解決しようとした問題を調べた。といってもwiki.osdev.orgのC++の項目を読んだだけ。英語の読解力がろくに無いので間違えて理解したかもしれない。

ようは、OSというパトロンがいなくなったC++さんが路頭に迷わないための手引き。

以下自分の理解をまとめる。osdev.orgにはサンプルコードまで載っていて素敵です。

デフォルトのスタートアップコードを利用しない

デフォルトでは、G++はmainが呼び出される前に実行されるコードや、mainがreturnした後に呼ばれるコードをリンクしようとする。

なので、無効にするために-nostartfilesオプションをつける。

new/delete

必要な処理を無効にしてしまった以上は、自前で実装しなければならない。とりあえず、global/staticなオブジェクトのコンストラクタ、デストラクタを呼び出すコードを追加すればよい。

コンストラクタ、デストラクタではnew/delete(new[]/delete[]も)が必要なので、これらも実装しなければならないが、その際にメモリマネジメントの機能が必要になる。特定のアドレスにオブジェクトを作るplacement newというテクニックもあるらしい。

mainの前後

GCC(G++)はctors、dtorsというセクションにそれぞれ、 global/staticオブジェクトのコンストラクタ、デストラクタを登録する。

C++のコードにジャンプする前後にこれらのセクションの内容を処理する。セクションの境界を知るためにリンカスクリプトを書く。

__cxa_atexitは、__cxa_finalizeで呼ばれる,オブジェクトや共有リソースを破棄する時のハンドルを登録する。

C++のカーネルコードが終了したら__cxa_finalize(0)を呼ぶべき。 dctorの処理と__cxa_finalize(0)の呼び出しは両方するべきなのだろうか。まぁ、終了時の事はあまり気にしなくても動くので良いか。

__dso_handleはさようならするオブジェクトがDynamic Shared Objectかどうか判別する？

純粋仮想関数(pure virtual function)

純粋仮想関数がオーバライドされていないのに呼びだされる(?)ときのための関数を用意する。

どこかの.cpp内に、__cxa_pure_virtualという関数を作る。なお、__cxa_pure_virtualにはextern "C"でC言語のリンケージを指定する。

Local static variables

GCCはローカルなスタティック変数のコンストラクタの前後に、複数スレッドから同時に呼び出されないように保護するコードを挿入するらしい。

いままで気にした事が無いシンボル名が出てきたので、他のどこかのオプションで無効になってるのではなかろうか。標準ライブラリを無効にするところだろうか。

標準ライブラリ

無効にするために-nostdlibオプションをつける。

実行時型情報

無効にするために-fno-tffiオプションをつける。

例外

無効にするために-fno-exceptionsオプションをつける。

C++で書いたコードをGRUBから起動したい

GRUBから起動するコードをCで書いていたが、ろくに触ったことのないC++に書き換えてみることにした。

OSの力が借りられない(と思う)ので、コンパイルが通らなかったり、リンクできなかったりと大変だったので、とりあえずの解決へいたった道筋をメモしておく。

一応動くようになった、というレベルでしかないので、間違ったことをしているかもしれないし、勝手に思い込んでるだけという可能性も高い。

環境はVM上のUbuntu8.04。 GCC4.2.4(G++)でオブジェクトファイルにコンパイル -> ldでリンクという流れ。

• staticメンバへの参照を解決できない
  • staticメンバはクラス定義の外部に実態を作らないといけない
• eh_frameというセクションから何かの関数への参照を解決できない
  • eh_frameは例外処理関係のコードが入ってるらしい。
  • コンパイルオプションに-fno-exceptionsをつけると例外処理を無効にできる
• 関数static_initialization_and_destructionからcxa_atexitとdso_handleに対する参照が解決できない
  • static_init(ry はnew以外で静的に用意したオブジェクトの初期化と後処理のための関数?
  • cxa_atexitで終了時に動作するデストラクタを登録している?
    • ダミーのcxa_atexitをリンクさせて無理やり解決
  • dso_handleはよくわからない。Dynamic Shared Object関係?
    • libgcc.aからarコマンドでdso_handle.oを抜き出してリンク。とりあえず動く。
• new演算子への参照が(ry
  • new演算子関数というものを定義すれば良いらしい
  • new演算子関数はオブジェクトのためのメモリ確保を行う
  • オブジェクトのサイズを引数として呼ばれ、確保したメモリのアドレスを返す
  • new演算子関数が返したアドレスをthisとしてコンストラクタが呼ばれる


• アセンブラの関数への参照が(ry
  • extern "C" としなければいけないらしい

割と問題が山積みな気もするけど、一応動くとこまで持っていけるということで手打ちにする。

FDイメージにGRUBを入れる

フロッピーディスクのイメージを作ってGRUBで起動し Multiboot Specificationとやらのパワーでプログラムを実行するためのメモ．

GNUのマニュアルや多数のブログ記事を参考にした．皆様に感謝．

$ dd if=/dev/zero of=./test bs=512 count=2880
2880+0 records in
2880+0 records out
1474560 bytes (1.5 MB) copied, 0.109047 s, 13.5 MB/s

ddコマンドで512バイトx2880(セクタ数18xヘッド数2xシリンダ数80)= 1.44MBのファイルを生成する．bs=1k count=1440の方が解りやすいかも．

$ mkfs.vfat test
mkfs.vfat 2.11 (12 Mar 2005)

適当なファイルシステムでフォーマット．mkfs.vfatはオプションを付けないとFAT16になるそうだ．

$ sudo mount test tmp -o loop

カレントディレクトリにtmpというディレクトリがあることを前提とする． mountは-oに続けてオプションを指定できる．

loopオプションはループデバイス(ループバックデバイス)の機能を用いて通常のファイルをブロック型デバイスとして扱うためのオプション． -o loop=/dev/loop0等と指定するが，省略されると使われてないループデバイスを探して利用してくれるそうだ．

$ cd tmp
$ sudo mkdir boot
$ cd boot
$ sudo mkdir grub
$ sudo cp /boot/grub/stage1 /boot/grub/stage2 /boot/grub/menu.lst ./
$ menu.lstを適当に編集

マウントしたイメージに/boot/grub/というディレクトリを作り，そこに grubのstage1(1次ローダ),stage2(2次ローダ),menu.lst(grub 起動時の設定？)をコピーする．このままだとmenu.lstが現在のブート時の設定になってるので適当にいじる．いじらなくてもコマンド入力すれば動かせはする．

$ grub
/* grubのコマンド */
> device (fd0) test /* デバイスの指定 */
> root (fd0)
> setup (fd0)       /* stage1を書きこむ */
> quit

grubがインストールされる．たったこれだけでいいそうな．

あとはMultiboot Specificationに対応したバイナリをディスクイメージの中に入れて(/hoge.bin等)ブートし，grubのコマンドとしてkernel /hoge.bin と打てば実行される．

今日の結論：grubすげぇ．