bobuhiro11's diary

ABC CD問題を埋めた

18 Jan 2019
[atcoder]

Atcoder Beginner Contest #1 ~ #115 の CD 問題をすべて解いた。 C問題は7割くらい、D問題は半分くらい自分の力で解くことができた。 特殊なアルゴリズムを使うことはあまりなく、ちゃんと考察できれば、解けるんじゃないかなと思う。 役立ちそうなことを残しておく。

  • Example の最初の1~2個は手で解いてみる。特に、幾何の問題は実際に書いてみる。
  • 複数のパラメータを総当たりするときはどちらか一方のパラメータを固定して考える。
  • あらかじめソートや累積和を計算しておく。

その他、Youtube の解説動画が充実していて、かなり助けになった。

x86エミュレータ開発記録 (5)

04 Jan 2019
[x86]

あけましておめでとうございます。 x86のエミュレータの開発を続けてきましたが、半年が経過し開発速度もゆっくりになってきたので、 一旦このタイミングでコードを公開することにします。 https://github.com/nmi/tiny_x86_emu に置いているので、 興味があれば見てみてください。

x86エミュレータ開発記録 (4)

19 Sep 2018
[x86]

先月、Go 1.11がリリースされ、WebAssemblyが実験的にサポートされるようになった。 開発中のエミュレータもGoで書かれているということで、せっかくなので、 WebAssemblyに移植した。 単純にGoをWebAssemblyにコンパイルすると標準出力としてブラウザのコンソールが使われるが、 divタグの中に出力したかったので、syscall/jsパッケージでDOMを操作した。 その他の部分は特に変更の必要がなかった。 https://bobuhiro11.net/tiny_x86_emu/に公開している。 まだ開発途中という状態で、ユーザプロセス実行に関する開発が滞っているので、そろそろ手をつけていきたい。 tiny_x86_emu_wasm_screenshot

x86エミュレータ開発記録 (3)

19 Aug 2018
[x86]

mpmain()、scheduler()、swtch()とプロセス切り替えできるまで、 エミュレータの開発が進んだ。 xv6のコードproc.cの334行目sti命令をずっと発行していて、どうやらループに入っているようなので、 ここでスケジューリング、コンテキストスイッチ周りをまとめたい。 切り替え先のプロセスは、切り替えられた直後forkret()、iinit()関数内にて、IOを行っている。 ここで、スリープ状態に入り、割り込みを待っているようだ。

proc構造体

xv6では各プロセスはproc構造体で管理される。 contextには、コンテキストスイッチのためのレジスタを格納する。 CSなどセグメントレジスタは、プロセス間で共通なので、保存する必要がない。 EAX、ECS、EDXなどは関数呼び出し時に自動的にスタックに保存されるため、contextに含めない。 最初のユーザプロセスは、userinit関数とallocproc関数で作成する。 proc構造体のコメントには、最初のユーザプロセスのデータをメモしておく。 トラップフレームは、ハードウェアとtrapasm.Sによりスタック上に積まれるもので、 trap関数へと引き渡される。 forkret関数のreturn先は、trapretに設定する。

struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // このプロセスのカーネルスタックの底
  enum procstate state;        // プロセスの状態：EMBRYO
  int pid;                     // PID：1
  struct proc *parent;         // 親プロセス：NULL
  struct trapframe *tf;        // トラップフレーム
  struct context *context;     // このプロセスのコンテキスト
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // カレントディレクトリ：/
  char name[16];               // プロセス名：initcode
};

struct context {
  uint edi;
  uint esi;
  uint ebx;
  uint ebp;
  uint eip; // forkret
};

struct trapframe {
  // registers as pushed by pusha
  uint edi, esi, ebp, oesp, ebx, edx, ecx, eax;

  // rest of trap frame
  ushort gs, padding1, fs, padding2, es, padding3, ds, padding4;
  uint trapno;

  // below here defined by x86 hardware
  uint err;
  uint eip;
  ushort cs;
  ushort padding5;
  uint eflags;

  // below here only when crossing rings, such as from user to kernel
  uint esp;
  ushort ss;
  ushort padding6;
};

struct {
  struct spinlock lock;
  struct proc proc[NPROC];
} ptable;

カーネルスタック

proc->kstackの中身を図示しておく。 swtchでは、espをproc->contextとして、edi、esi、ebx、ebpをpopする。 そして、最後にret命令で、eipを復元する。

(lower address)
 ------------------- 
|                   | <= proc->kstack
|                   |
 ------------------- 
 ------------------- 
| edi               | <= proc->context
| esi               |
| ebx               |
| ebp               |
| eip = forkret     |
 ------------------- 
 ------------------- 
|                   | <= trapret（関数ポインタ）
 ------------------- 
 ------------------- 
|                   | <= proc->tf
 ------------------- 
                      <= proc->kstack + KSTACKSIZE(4096)
(upper address)
 

参考

はじめて読む486の読書メモ

04 Aug 2018
[x86]

初めて読む486を読んだので、気になってことをメモしておく。 エミュレータを作っているので、参考になる。 全体を通して、図が分かりやすいので、図を見るだけでも勉強になる。

セグメント

  • EIPから命令を読み出すときにはCSレジスタの指すセグメントが使われ、命令実行時のメモリアクセスにはDSレジスタの指すセグメントが使われる。また、PUSH、POP、CALL、RETなどスタックに関する操作には、SSレジスタの指すセグメントが使われる。スタックは下位アドレス方向に伸びるため、スタックセグメントのリミットは例外的に下限を指定する。
  • すべてのメモリアクセスのたびにセグメントディスクリプタを参照するのは、無駄が多いので、CPU内にセグメントディスクリプタ自体のキャッシュ（セグメントディスクリプタキャッシュ）を持つ。
  • プロテクトモードでは、CSレジスタが16ビットセグメントを指していれば、オペランドサイズとアドレスサイズは16ビットになる。同様に、32ビットセグメントでは、それらのサイズは32bitになる。
  • セグメントごとにDPL（Descriptor Privilege Level）で特権レベルを指定する。現在実行中のセグメントのDPLによって、CPL（Current Privilege Level）が決まる。CPLはCSレジスタの下位2bit、DPLはセグメントディスクリプタで設定される。ジャンプ先セグメントのDPLがCPLより高い場合には、直接ジャンプすることはできず、コールゲートを経由する必要がある。

ディスクリプタ

  • GDTには、セグメントディスクリプタのほかに、TSS、コールゲート、タスクゲート、トラップゲート、割り込みゲートなど複数のシステムオブジェクトが格納される。
  • 各種ゲートディスクリプタにもDPLを設定しておき、ゲートを呼び出すときに、CPLとDPLを比較する。CPLがゲートのDPL以上であれば、ゲートの先のセグメントのDPLによらず、そのセグメントにジャンプできる。
  • LDTを使うときは、GDT内にLDTを指すディスクリプタを作成して、そのセレクタ値をLDTRに設定する。

割り込み

  • 割り込み番号は0x00~0xFFまで全256種類。
  • 割り込みディスクリプタテーブル（IDT）には、ゲートディスクリプタを並べておく。割り込み番号がIDT内オフセットとなる。ゲートの種類は、割り込みゲート、トラップゲート、タスクゲートの3種類。
  • ふつうRET命令は単純にCS,EIPをPOPするだけだが、POPしたCSのDPLがCPLよりも低ければ、続けてSSとESPもPOPする。
  • 低特権レベルからコールゲートを介してOSの関数を呼び出したとき、引数は低特権レベルのスタックにしか存在しないため、OSから簡単に扱えない。対策として、コールゲートのコピーカウントというパラメタに、引数のバイト数/4を設定しておき、自動的に引数をOS側のスタックにコピーさせる。戻るときは、オペランド付きRET命令を使い、OSのスタックをインクリメントさせる。

I/O

  • IOポートはディスクリプタがないので、DPLを持たないが、代わりにIOポート専用の特権レベルIOPRL(I/O Privilege Level)がある。IOPRLは、EFLAGSレジスタで設定される。また、TSS内のIO許可マップで制御することもできる。

その他

  • クロックダブラーと呼ばれるクロック周波数を2倍にする技術があった。486DX2やODP（Over Drive Processor）で使われていた。
  • OSが利用するシステムレジスタはGDTR、IDTR、LDTR、TR、CR0~CR3。
  • DR0~DR7を操作することでブレークポイントを仕掛けて、デバッグできる。
  • アドレスバスとデータバスは32ビット、IOアドレスバスは16ビット。
  • オペランドサイズとアドレスサイズはそれぞれ32ビットあるいは16ビットで解釈される。どちらもプレフィックス（0x66あるいは0x67）をつけることでサイズを変更できる。
  • 現在のタスクが使っているTSSのセレクト値は、TR（Task Register）に保持する。
  • 同特権レベルでのCALL命令であれば、CSとEIPをPUSHして、ジャンプするだけ。異なる特権レベルへ移るためのコールゲートへのCALL命令であれば、スタックを切り替えてから、SS、ESP、CS、EIPをPUSHする。