OS学習メモ13 (MINIX本4.3-4.3.2章)
本自体は既に一回読んだんですが、復習を兼ねてこの記事を書くためにわざわざ”The MINIX book Operating system implementation”を図書館から借りてきました。持ち歩くのが重いったらないです(笑)。
洋書で読んでるので、もしかしたら英語の解釈違いによる致命的な間違いがある可能性もあるので…違和感感じたら各自改めて調べてください…。
4.3仮想記憶
昔は、利用可能なメモリよりも大きいプログラムを実行しなければならないときにプログラムをオーバレイという小さい断片に分けて実行させる方法を取っていた。オーバレイのスワップイン/アウトはシステムが行うにしても、オーバレイへの分割はプログラマの仕事で、これがまた結構面倒くさいからこれもコンピュータにやらせようってことになって仮想記憶が登場する。
仮想記憶の基本的な考え方は、プログラム、データ、スタックなどを合わせたサイズが物理メモリ量を超えることにある。つまりOSは、その時点でプログラムが使ってる部分だけメモリに残しておいて残りはディスクに置けばいいのである。
4.3.1 ページング
例えば MOV $t0 1000 というアセンブラ命令があったとすると、CPUはメモリアドレス1000の内容をt0にコピーする。この時プログラムが指定するアドレスは仮想アドレスで、これはMMU（Memory Management Unit）によって物理アドレスに変換される。仮想アドレス空間はページという単位に分割され、物理メモリ内における対応する単位はページフレームと呼ばれる（ページとページフレームは同じサイズであることが多い）
明らかに、ページ数>ページフレーム数であるから全てのページを物理メモリにマップすることは不可能なので(だから仮想メモリがあるわけなんだし)、実際のハードウェアでは、物理メモリ上にページが存在するか否かを示すpresent/absent bit(在/不在ビット)が各エントリにある。もしプログラムがマップされていないページを使おうとすると、CPUはOSに対して割り込みを引き起こす（この割り込みはページフォルトと呼ばれている）。これが発生すると、OSはあまり使用されていないページフレームを選び、その内容をディスクに書き込んで、空いたところに該当ページを読み込んで、変換テーブルを書き換えて、割り込みを起こした命令を再度実行する。
4.3.2 ページテーブル
仮想アドレスは「ページ番号を表す部分」と「オフセットを表す部分」に分割される。例えば16bitのアドレスの場合、上位4bitをページ番号に割り当てて(この時2^4=16個のページを持てる)、下位12bitは指定されたページ内のオフセット(0-4095)にしたりする。ページテーブルの目的は”ページ→ページフレーム”の変換であるが...2つの大きな問題がある。「1.ページテーブルが極端に大きくなること」と「2.変換が高速に行われなくてはいけないこと」である。
１、32ビットの仮想アドレス幅を持っているとすると、ページサイズが4KBとして約100万ページ(2^32/4KB)あることになる。これがもし64ビットなら4.5*10^15に…考えたくない。
２、メモリが参照される度に”仮想→物理”の変換がなされるという点に問題がある。典型的な命令は命令ワードとメモリオペランドを持っているので、一命令あたり1か2回,場合によってはそれ以上のページテーブル参照が必要になる。
大きなエントリを持って高速なページ変換を実現するというのは、コンピュータ設計の大きな制約条件になる。超高性能を要求されるマシンには深刻な問題だし、ローエンドなものに関してもコスト/性能比が非常に大事という意味では見逃すことが出来ない項目。
そこで、現実のコンピュータで使われているハードウェアの解決法の例↓
多階層ページテーブル
巨大なページテーブルを常にメモリ上に持たなければいけないという問題を抱えているので、多くのコンピュータではこの多階層ページテーブルを採用している。
(名前からある程度想像できると思うが)この方式では、アドレス32bitをいくつかのまとまりに分けてページテーブルを階層構造にすることで不要な部分をメモリに配置しないようにしている。具体的には、32を10/10/12の3つのまとまりに分け、最初の10bitはページテーブルのインデックス※として利用（第一層）,次の10bitは4MBのページテーブル(第二層)に、残る12bitをオフセットとして利用する。
※ちなみに第一層の1024個のエントリのうち、エントリ0はプログラムテキストのページテーブルを指しており、エントリ1023はスタックのページテーブルを指している。
これなら、100万ページのアドレス空間であるにも関わらず必要なのは4つの小さなページテーブルだけで済む（第一層のテーブル、それに対応する第二層のテーブル、それに加えて第二層エントリ0,1023)
これはあくまで2階層ページテーブルシステムであり、3階層,4階層…と拡張可能である。階層を追加すればその分柔軟にはなるが複雑になる
ページテーブルエントリの構成
エントリのサイズはコンピュータによって異なるが32ビットが通常サイズになっていて、ページフレーム番号,在/不在ビット,保護ビット,更新ビット,参照ビット,キャッシュ禁止を指示するビットの内容を含んでいる
・（最初の2つは説明を省略）
・protection bits(保護ビット)は、どんなアクセスが許されるかを示していて、単純な形であれば1ビットで”読み書き可能/読み出しのみ”を表している。
・modified (更新ビット)はページの使用履歴を示している（次に出てくる参照ビットも）。ページが読み込まれたらハードウェアが自動的に更新ビットをセットし、OSがこのページフレームを再利用する時に使われる。つまり、もしもページが更新されていたらそのページはディスクに書き戻さなければならないし、そうでなければディスク内のコピーとページが同一なので直ちに破棄できる。このビットはページの状態を表しているのでdirty bitと呼ばれることもある。
・referenced bit(参照ビット)は、そのページに参照した時にセットされ、ページフォルト発生時の追放ページを選ぶ根拠になる。
・最後のビットはページにキャッシュ禁止の指示をしている。これはデバイスレジスタ上にマップされたページに対して重要な意味を持っている。OSがI/Oをポーリングで待っている時（I/Oからのワードを読み続けている時）、CPU上のキャッシュが溢れたからといって古いキャッシュ内容のコピーを書き戻してはいけないので、このビットを使ってキャッシュをオフと指定する（...なので分離したI/O空間を持つメモリマップドI/Oを使っていないマシンではこのビットは不要）
ちょっと疲れたので半端ですが今日はここまで。
次回は4.3.3 TLB（Translation Lookaaside Buffers）の説明から。
余談:
先日研究室が決まりました。AI関係なのでこういったOSの知識って殆ど使わないんですけど、なんか個人的に好きなのでこの分野は趣味として続けようと思ってます。今のモチベーションとして、MINIX(バージョンは最新の3ではなく1)のソースを読んでみたいなって思っています。理論だけじゃなくて、実際にどう実装されているのかまで追ってみたいです。Linuxとかと違って教育用のOSなので1万行くらいですし、学生じゃないとそんなことしてる時間無さそうなので...春休みにでも。
OS学習メモ12 (MINIX本4.1-4.2章)
メモリ管理の章です。
4.3（仮想記憶）は少し長いので区切りの良いところまで。
メモリ管理システムは２つに分類できる。一つはプロセスの実行中にその内容をメモリとディスク間で移動するページング方式で、もう片方の方式ではそれを行わない（後者の方が単純なのでそちらから見ていく）
4.1.1 スワップ,ページングを必要としない単一プログラミング
最も単純なメモリ管理方式は、プログラムとOSがメモリを共有して同時に一つのプログラムしか実行しない方式である。これには３つの方法があって、「RAMの一番下にOSを配置する」、「メモリ先頭のROMにOSをを配置する」、「メモリの先頭のROMにはデバイスドライバを入れて、システムの残り部分をRAMの下の方に配置する」のいずれかである。ユーザがコマンドを叩けば、OSは要求されたプロセスを主メモリに読んで、実行する。プロセスが完了したらOSは次のコマンド入力を待つ。次のコマンドが入力されたら、対応プログラムを前に使用したものに上書きして読み込むという流れになる。
4.1.2 固定パーディションによるマルチプログラミング
実は4.1.1の仕組みは今日ではほとんど使われていない。現在のほとんどのシステムでは複数のプロセスを同時実行できる。これを実現する最も簡単な方法は単純にメモリを分割するという方法で、ジョブが到着するとそのジョブが入る最も小さなパーティションの待ち行列にジョブを入れるということを行う。しかしこの方式では待ち行列の作り方によって、ジョブ中に使われない領域ができたり、大きなパーティションに小さなジョブを入れてメモリを無駄にしてしまうといった問題が発生する。これを解決する手段として、「小さなパーティションを持っておく」とか「実行待ちのジョブに実行件を与えてk回以上スキップされない規則にする」というのがある。
4.1.3再配置と記憶保護
マルチプログラミングの実現において解決すべきなのが再配置と記憶保護の問題。
あるプログラムをリンクする時、リンカはそのプログラムがどのアドレスから開始するかを知る必要がある。（例えば最初の命令が、リンカによって生成された、バイナリファイル内の絶対アドレス100番にあるサブルーチンコールだとすると、もしもそのプログラムがアドレス200K番地にロードされた場合200K+100番地にサブルーチンコールをする必要がある。もちろん、300K番地にロードされた場合は300K+100番地である。）これが再配置の問題である。
この解決方法の一つは、メモリにプログラムをロードした時点で命令を書き換える方法、つまりプログラムが200K番地のところにロードされたなら各アドレス部に200Kを加算するという方法である。だが、ローディング中の再配置は記憶保護の問題を解決できない。悪意のあるプログラムが常に新しい命令列を作って実行するかもしれない。このため、再配置と記憶保護の別の方法として、ベースレジスタと境界レジスタの２つの特殊なハードウェアレジスタを用いることがある。あるプロセスがスケジュールされると、ベースレジスタにはパーティションの先頭アドレス、境界レジスタにはパーティションの長さが入り、メモリアドレス生成の度に自動的にベースレジスタの内容がアクセス前に加算されるようになる。アドレスは現在のパーティション外のメモリにアクセスしないように境界レジスタによって保護されていて、これらは改竄されることもない。
4.2 スワッピング
スワッピングとは、プロセス全体を主記憶にロードして暫く実行させた後で、ディスクに吐き出してプロセスを停止するというのを繰り返す方法で、ここまでの固定パーティションの方式とは違ってパーティションの数や位置やサイズが動的に変化する。この分、柔軟性は高まったといえるけれども、メモリを割り当てたり開放するための管理の複雑さは増している。スワッピングを繰り返すとメモリの中に小さな空き領域が出来るので、プロセスを移動することによってそれらを一箇所にまとめることが出来る（これはメモリコンパクションと呼ばれる）。そして肝心のスワッピングだが、プロセスにどのくらいのメモリ量を割り当てるかは重要な問題である。
動的にメモリを割り当てる歳に、OSははそれを管理する必要がある。使用状況の管理には一般に２つの方法ービットマップによる管理とリストによる管理ーがある。
4.2.1 ビットマップによるメモリ管理
あらかじめ”単位”を決めてメモリを分割し（数ワードとか数KBとか）、その単位ごとに「空き」ならば0,「使用中」ならば1をつけて管理する方法。当然ながらこの”単位”を小さくすればするほどビットマップは大きくなる。この方法はメモリサイズと割り当てる単位によって決まるので、一定サイズのメモリを使って全メモリの管理を可能とする簡単な方法であるが、与えられたビットパターンをビットマップ上から探すのは一般的に処理が遅くなるという問題点がある。
4.2.2 リンクリストによるメモリ管理
パーティションをリスト構造にして連結して管理する方法。それぞれのリンクには「空き/使用中」「各パーティションの先頭アドレス」「各パーティションの長さ」「次のパーティションの情報」が入っている。以下はリストを管理するためのアルゴリズムである。
ファーストフィットは該当プロセスのメモリ容量を最初に満たす空きリストを見つけるまで探すもの。ネクストフィットはファーストフィットと同じように空きを探すが、見つかった位置を記憶しておいて、次にコールされるとそのリストの場所から求める空きリストを探す（ファーストフィットと違って最初からは探さない）。ベストフィットは、全リストを調べて空き容量が最小になるエントリを求める。ワーストフィットは、プロセスに割り当てた後で空きと成る部分で最大になるような選択法。クイックフィットは、比較的よく要求されるサイズごとに別々の空きリストを作って管理する。
4.3は今読んでいます。
OS学習メモ11(30日OS自作入門11日)
やっていきましょう。
スタートはここから。
11日目から pic.twitter.com/md94FLc9sU
— Yamahiro (@ymhr_s) 2018年6月8日
ご覧の有様です。
右端に行ったら変な動きをしているので、画面外に出てしまった時には値を補正するようにします。このくらいであれば本を読まなくても自分で直せました。 そんなに大きな変更も加えてないのでプログラムは省略します。
次に「shtctlの指定を省略する」ということをやります。難しいことは特になくて（前回作ったsheet_updown関数を見てもらえればわかるんですけど）下敷きを上げ下げするために毎回ctlを指定しているのが面倒くさいからそれを改良しようというだけのことです。
(久しぶりなので前回作ったsheet_updown関数を簡単におさらいしておくと、この関数はまず引数として「SHTCTL型の*ctl」「SHEET型の*sht (高さを変更したい下敷きの情報)」「int型のheight(変更後の下敷きの高さ)」の３つを受け取ります。受け取ったheightによって、ctlの情報をどんどん書き換えて行くことで下敷きの高さ関係を変更していくというのが、このsheet_updown関数でした。)
SHEET構造体の中にSHTCTL型の構造体を追加して、sheet_updownやらshtctl_unitやら関係するところを書き換えていくだけです。詳しい説明は省略しますね。
struct SHEET { unsigned char *buf; int bxsize, bysize, vx0, vy0, col_inv, height, flags; struct SHTCTL *ctl; };
void sheet_updown(struct SHEET *sht, int height) { struct SHTCTL *ctl = sht->ctl; int h, old = sht->height; /*略*/ for (h = old; h > height; h--) { ctl->sheets[h]=ctl->sheets[h - 1]; //こんな感じで使ってます ctl->sheets[h]->height = h; } ctl->sheets[height] = sht; /*略*/ }
引数の数が3つ→2つになったり、プログラムがちょびっとコンパクトになりました。
さてここからが本当の11日目という所でしょう。ウィンドウを出していきます。…とは言っても、すでに土台は出来上がっているのでそれらを駆使するだけです。プログラムはコピペさせてください。
init_palette(); shtctl = shtctl_init(memman, binfo->vram, binfo->scrnx, binfo->scrny); sht_back = sheet_alloc(shtctl); sht_mouse = sheet_alloc(shtctl); sht_win = sheet_alloc(shtctl); buf_back = (unsigned char *) memman_alloc_4k(memman, binfo->scrnx * binfo->scrny); buf_win = (unsigned char *) memman_alloc_4k(memman, 160 * 68); sheet_setbuf(sht_back, buf_back, binfo->scrnx, binfo->scrny, -1); sheet_setbuf(sht_mouse, buf_mouse, 16, 16, 99); sheet_setbuf(sht_win, buf_win, 160, 68, -1); init_screen8(buf_back, binfo->scrnx, binfo->scrny); init_mouse_cursor8(buf_mouse, 99); make_window8(buf_win, 160, 68, "window"); putfonts8_asc(buf_win, 160, 24, 28, COL8_000000, "Welcome to"); putfonts8_asc(buf_win, 160, 24, 44, COL8_000000, " Haribote-OS!"); sheet_slide(sht_back, 0, 0); mx = (binfo->scrnx - 16) ; my = (binfo->scrny - 28 - 16) / 2; sheet_slide(sht_mouse, mx, my); sheet_slide(sht_win, 80, 72); sheet_updown(sht_back, 0); sheet_updown(sht_mouse, 1); sheet_updown(sht_win, 2); sprintf(s, "(%3d, %3d)", mx, my); putfonts8_asc(buf_back, binfo->scrnx, 0, 0, COL8_FFFFFF, s); sprintf(s, "memory %dMB free : %dKB", memtotal / (1024 * 1024), memman_total(memman) / 1024); putfonts8_asc(buf_back, binfo->scrnx, 0, 32, COL8_FFFFFF, s); sheet_refresh(sht_back, 0, 0, binfo->scrnx, 48);
特に理由は無いんですけど、なんとなくsheet_updown関数が好きです。
実行結果↓
ここまで順調にやってこれました。次はカウンタを作ります。その名の通り0から数を数えていうというもので、ループの中でsheet_refreshとカウントを行います。文字が出力できるのだから、当然こういうこともできるよなぁという感じですね。
unsigned int memtotal, count = 0; for (;;) { count+=20000; sprintf(s, "%010d", count); boxfill8(buf_win, 160, COL8_C6C6C6, 40, 28, 119, 43); putfonts8_asc(buf_win, 160, 40, 28, COL8_000000, s); sheet_refresh(sht_win, 40, 28, 120, 44); }
で、動かしてみると
チラチラチラチラしてる。 pic.twitter.com/JgzGlkeSUq
— Yamahiro (@ymhr_s) 2018年6月8日
書き換える必要のない背景の下敷きまで書き換えてるからこういったことが起きてしまってます。というわけで、必要な部分だけ書き換えるように書き換えたものがこれです。高さを指定してます。
void sheet_refreshsub(struct SHTCTL *ctl, int vx0, int vy0, int vx1, int vy1, int h0) { /*略*/ for (h = h0; h <= ctl->top; h++) { /*略*/ } return; }
動画は載せませんが、さっきみたいにカウントする度にちらちらする現象は直りました。が、これでもまだ不十分で、カウントのところにマウスをもっていくとマウスがちらちらしてしまいます。マウスまで一緒に描いて消してを繰り返しているのが原因なので、これを直すためにはウィンドウを描画する際にマウスカーソル部分を避けて描き込むしかありません。
一応自分でも解決方法を数分考えてみたのですが、どうにも思いつかないので本に沿ってやっていくことに。今回は”map”を使う方法です。言葉でうまく説明できませんが下の図が全てです。
例えば図中で一番下の下敷きをリフレッシュするなら、右側で”１”になっているところだけを書き変えればいい（２の所まで書き直す必要はない）というわけです。これを使ってマウスカーソルの所を避けて画面をリフレッシュしようというわけですね。
...と、いうのが仕組みの話で….ここまではわかったのですが…、正直、実装の所はコードを読んで考えても良くわかりませんでした。この本、後になって読み返したらすっと分かるとかよくあるのでちょっとこの辺り一旦スキップしようと思います。というわけで半端ですがここまで。
CTFに初参加した（SECCON Beginners CTF）
5月26日から27日にかけてSECCON Beginners CTFに一人で参加しました。これまで何度か常設のものを解いてみたことはありましたが、こうして大会っぽい大会に参加するのは初めてでした。
warm up5つしか解けず残念な結果に終わってしまいました。
この記事を書いている5月27日22時45分現在、まだ他の人が書いたwrite upには全く目を通していないのですが、僕もCTFの大会に出た以上はwrite upを書いたりしてアウトプットとかしないと成長しないと思うので、（正直今回に関しては恥ずかしくて書きたくないんですけど）今後出場したものに関してはなるべく書いていこうと思います。
************************
[Warmup] Veni, vidi, vici 51 (Crypto)
3つのテキストファイルが渡される。
１つ目は見た感じがもうシーザー暗号っぽいので、ROT13したら"The first part of the flag is: ctf4b{n0more"が出てきた。
２つ目もシーザー暗号っぽかったためROT13したけど違ったので、ROT1から試してみたらROT8のところでフラグ”The second part of the flag is: _cLass!cal_c”が出た。
3つ目は”{ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥”で、macbookひっくり返して読んだ。
それでつなげるとFLAGに。
[Warmup] Simple Auth51 (Reversing)
実行ファイルが渡さて認証に使われているパスワードを使えとのことだった。いつ入れたかも分からない使い方も分からないディスアセンブラに突っ込んでみて、深く考えないで眺めてたらそれっぽいのがあったので、とりあえずASCIIコードだと思って文字列にしたらあっさりFLAG出てしまった。なんかごめんなさい
[Warmup] Greeting 51(Web)
”admin”にならないとフラグが表示されないwebサイト。名前を変更するフォームはあるが、”admin”と入力すると”偽管理者”に勝手に名前変更されてしまう仕様になっている。コードを見たらhtmlspecialchars関数でサニタイジングされているのでSQLインジェクションでも無さそう（なぜかそこは知ってた）。
...よく見てみたらCookieを使っていたので、名前のところにadminと入力してページを再読み込みしてみたところFLAGが出てた。
[Warmup] plain mail 51 (Misc)
ダウンロードしたpcapファイルをwiresharkで見てみたはいいものの、全然勉強したことなかったのでわからなかった。調べながら解いた。
TCPストリームを追跡して見たら、"I will send secret information .First, I will send encrypted file. Second, I wll send you the password"というのがあった。別のTCPストリームを追跡してみたら内容が見事にそれっぽかったので、raw(無加工)形式で保存してみたらちゃんと暗号化されたzipファイルが添付されていた。”_you_are_pro_”なんていう皮肉パスワードもメールに書いてあったので、それで中身をみたらテキストファイルにFLAGがいた。なんか「他人のメール盗み見てる感」が気持ちよくてこれがCTFなのかって興奮した自分がいた（気がする）
[Warmup] Welcome 51 (Misc)
公式IRCチャンネルみたら堂々と書いてあった
************************
恐れ恥ずかしながらこんな感じです...
やっぱり解けないからwriteupを見て勉強しよう...。初CTFは悔しい結果に終わってしまったようだ。
— Yamahiro (@_YMHR_U) May 26, 2018
とりあえず本当に悔しかったので、ちゃんと勉強して強くなろうと思いました。
OS学習メモ10(30日OS自作入門10日目)
（通信制限のためか画像アップロードできないので後ほど修正加えます）
※修正しました(5/24 8:40)
さて10日目,ようやく3分の1ですね。やっていきしょう。
最初の方でちょっとメモリ管理の続きでmallocっぽいのを作ったり、切り上げ切り捨てのやり方の話とかの話もあるのですが、ちょっとその辺りはスキップしまして早速8日目の続きからいきたいのですが、8日目の記事書いたのだいぶ前なので、ちょっと振り返るところから。
8日目の所でマウスカーソルが動くようになったのですが、その処理を「カーソルの上に色を上塗りして見えなくする→再びカーソル描画」とやっていたために、マウスを動かす度に画面を破壊してしたところで終わりましたね。
さて今回はこれを解決するために重ね合わせをやっていこうという所です。
イメージとしてはまさにお絵かきする時とかに使う”レイヤー”ですね。
ここでは”透明な下敷きにかいた絵”を重ねると表現されています。
というわけで、まずはその下敷きとやらを定義します。
struct SHEET{ unsigned char *bar; int bxsize,bysize,vx0,vy0,col_inv,height,flags; }
（そういえば、今回は構造体があたまの中でごちゃごちゃしたのでいつにも増して図が多いです。自分の備忘録のつもりですが、誰かの理解の助けになったりすれば嬉しいです）
構造体SHEETのイメージはこんな感じ。
これで一枚分の情報が出来ましたね。
では次に、複数枚の下敷きを管理するための”下敷き管理用構造体”を作ります。
struct SHTCTL{ unsigned char *vram; int xsize,ysize,top; struct SHEET *sheets[256]; struct SHEET sheets0[256]; }
sheets0で一枚一枚に下敷きの情報を保持しておきます。この時、どの下敷きが上にあってどれが下かとかは関係なくバラバラに格納されているので、それを下層から順に並べて番地だけを並べた構造体配列がsheetsです。イメージを見たほうが早い気がします。
これで管理の準備が整いました。この下敷き管理構造体を記憶するためのメモリを確保してぱぱっと値を設定。flagはそのシートが未使用であるか否かを示していて、はじめは全て0にしておいて使うときには1にします。
struct SHTCTL *shtctl_init(struct MEMMAN *memman, unsigned char *vram, int xsize, int ysize) { struct SHTCTL *ctl; int i; ctl = (struct SHTCTL *) memman_alloc_4k(memman, sizeof (struct SHTCTL)); if (ctl == 0) {goto err;} ctl->vram = vram; ctl->xsize = xsize; ctl->ysize = ysize; ctl->top = -1; for (i = 0; i < MAX_SHEETS; i++) {ctl->sheets0[i].flags = 0; } err: return ctl; }
次に未使用の下敷きを持ってくる関数。
気になるのは高さを-1にしている所だと思いますが、これは後から設定するからここでは気にしなくても大丈夫です。
struct SHEET *sheet_alloc(struct SHTCTL *ctl) { struct SHEET *sht; int i; for (i = 0; i < MAX_SHEETS; i++) { if (ctl->sheets0[i].flags == 0) { sht = &ctl->sheets0[i]; sht->flags = SHEET_USE; sht->height = -1; return sht; } } return 0; }
次に下敷きの高さを設定する関数です。
void sheet_updown(struct SHTCTL *ctl, struct SHEET *sht, int height){ int h, old = sht->height; if (height > ctl->top + 1) {height = ctl->top + 1;} if (height < -1) {height = -1;} sht->height = height; if (old > height) { if (height >= 0) { for (h = old; h > height; h--) { ctl->sheets[h] = ctl->sheets[h - 1]; ctl->sheets[h]->height = h; } ctl->sheets[height] = sht; } else { if (ctl->top > old) { for (h = old; h < ctl->top; h++) { ctl->sheets[h] = ctl->sheets[h + 1]; ctl->sheets[h]->height = h; } } ctl->top--; } sheet_refresh(ctl); } else if (old < height) { if (old >= 0) { for (h = old; h < height; h++) { ctl->sheets[h] = ctl->sheets[h + 1]; ctl->sheets[h]->height = h; } ctl->sheets[height] = sht; } else { for (h = ctl->top; h >= height; h--) { ctl->sheets[h + 1] = ctl->sheets[h]; ctl->sheets[h + 1]->height = h + 1; } ctl->sheets[height] = sht; ctl->top++; } sheet_refresh(ctl); } return; }
プログラムはちょっと長いですが、こでまでのプログラムをなんとか読めるだけの力がついていればこれも読みこなせるはずです。最初の頃はつらいなぁとおもうわけですが、それでもめげずに頑張っていると、どんどん読む能力が上達してきます。
ということなので丁寧に読んでいきましょう。
このsheet_updown関数では、ある下敷きの高さを、引数で渡しているhightの位置に設定します。
int h, old = sht->height;
もともとどこのレイヤにいたのかをoldに。
if (height > ctl->top + 1) {height = ctl->top + 1;} if (height < -1) {height = -1;} sht->height = height;
一番上のレイヤがctl（管理用構造体）のtopなので、hightをtopよりも上に指定する必要はないし、同様に低すぎる値にする必要もありません。最下層を０ではなく−１にしていますが、これは下敷きを非表示にする時のためです（地下1階みたいなイメージ?）
if (old > height) { if (height >= 0) { for (h = old; h > height; h--) { ctl->sheets[h] = ctl->sheets[h - 1]; ctl->sheets[h]->height = h; } ctl->sheets[height] = sht; } else { if (ctl->top > old) { for (h = old; h < ctl->top; h++) { ctl->sheets[h] = ctl->sheets[h + 1]; ctl->sheets[h]->height = h; } } ctl->top--; } sheet_refresh(ctl); }
細かく分けてみていきます。
if (old > height) {
old>hightはつまり、下敷きの”レイヤを下げる”場合です。
if (height >= 0) { for (h = old; h > height; h--) { ctl->sheets[h] = ctl->sheets[h - 1]; ctl->sheets[h]->height = h; } ctl->sheets[height] = sht; }
ここは、コードと図を一緒に見てください。
(ここでは青を一番下に持っていく例で考えます)
一回のループで↓をやります。
最終的にはこうなります。
下敷きを非表示にした場合はtopを1減らすのを忘れないようにしましょう。
並び順がちゃんと整理されたので、これに基づき再描画する処理が後に続きます。
ここまでわかれば残りの部分は”レイヤーを上げる処理”で、ほとんどやっていることは同じなのでスラスラと読めるはずです。
で、保留した再描画の処理がこちら
void sheet_refresh(struct SHTCTL *ctl){ int h, bx, by, vx, vy; unsigned char *buf, c, *vram = ctl->vram; struct SHEET *sht; for (h = 0; h <= ctl->top; h++) { sht = ctl->sheets[h]; buf = sht->buf; for (by = 0; by < sht->bysize; by++) { vy = sht->vy0 + by; for (bx = 0; bx < sht->bxsize; bx++) { vx = sht->vx0 + bx; c = buf[by * sht->bxsize + bx]; if (c != sht->col_inv) { vram[vy * ctl->xsize + vx] = c; } } } } return; }
下敷きを下層から描いていきます。
OS自作入門の初めの方で作ったboxfill関数とやってることは同じです。
あとは、下敷きをずらしたり,使い終わった下敷きを解放したり,といった関数をちょこっと追加してやると動きます。
10日目 pic.twitter.com/6Rq1DCUAKL
— Yamahiro (@ymhr_s) 2018年5月22日
（平井堅「トドカナイカラ」いい曲です）
だいぶGUIっぽく、OSっぽくなってきましたね！
画像、くどかったかも...
OS学習メモ9(30日OS自作入門9日目)
（完成直前の記事が誤操作で一度全部消えたので沈みムード）
１週間ぶりのOS本の進捗です。ここ１週間は中間試験の勉強やseccampの選択課題の勉強であまりこちらに手を回せていませんでしたが、意欲は全く下がっていません。張り切ってやっていきましょうー。
前回は「ようやく動いたマウスカーソル君がせっかく作った画面をどんどん破壊してしまう」という状態で終了したので、今回はそれを直していく...のかなと思いきやちょっと休憩。メモリ管理のお話です。
さてメモリ管理とは言っても、そもそもメモリがどのくらいの容量なのかが分からなければ管理もへったくれもないので、まずはそこから調べていきます。どうやら起動時にBIOSがチェックしてくれているらしいのですが、それを見るのはややこしいこといっぱいあって大変なのでBIOSを使わないでメモリチェックしていきます。
...って本には書いてあったんですが、そう言われちゃうとBIOSを使ってメモリチェックしてみたくなり、自分にはまだ早いかなー出来ないだろうなぁ..ーとは思いつつ、
http://oswiki.osask.jp/?(AT)BIOS
http://softwaretechnique.jp/OS_Development/Tips/Bios_Services/video_services.html
あたりを見ながら一応自分でも色々試してみました。3時間くらいは粘ったんですが案の定うまく行かなくて「やっぱり一旦本に沿って終わらせよう...」と改めて思うのでした...（悔しい）
— Yamahiro (@_YMHR_U) 2018年5月13日
まぁそんなわけで今回も本に沿って進めていきました。
32MB。
更に進めて...
空き容量も表示できましたよ
（正直書くのがちょっと面倒くさくなっちゃっているんですが...笑）説明これだけというのはさすがに雑なので、簡単に何をやったのかだけ書いて今日は終わろうと思います。
まずはコードをコピぺして置いておきます
void memman_init(struct MEMMAN *man){ man->frees = 0; /* 空き情報の個数 */ man->maxfrees = 0; /* 状況観察用：freesの最大値 */ man->lostsize = 0; /* 解放に失敗した合計サイズ */ man->losts = 0; /* 解放に失敗した回数 */ return; } /*確保*/ unsigned int memman_alloc(struct MEMMAN *man, unsigned int size){ unsigned int i, a; for (i = 0; i < man->frees; i++) { if (man->free[i].size >= size) { /* 十分な広さの空きを発見した時 */ a = man->free[i].addr; man->free[i].addr += size; man->free[i].size -= size; if (man->free[i].size == 0) { man->frees--; for (; i < man->frees; i++) { man->free[i] = man->free[i + 1]; } } return a; } } return 0; /* 空きが無かった場合 */ } /* 解放 */ int memman_free(struct MEMMAN *man, unsigned int addr, unsigned int size){ int i, j; for (i = 0; i < man->frees; i++) { if (man->free[i].addr > addr) { break; } } /* free[i - 1].addr < addr < free[i].addr */ if (i > 0) { if (man->free[i - 1].addr + man->free[i - 1].size == addr) { man->free[i - 1].size += size; if (i < man->frees) { if (addr + size == man->free[i].addr) { man->free[i - 1].size += man->free[i].size; man->frees--; for (; i < man->frees; i++) { man->free[i] = man->free[i + 1]; } } } return 0; } } if (i < man->frees) { if (addr + size == man->free[i].addr) { man->free[i].addr = addr; man->free[i].size += size; return 0; } } if (man->frees < MEMMAN_FREES) { for (j = man->frees; j > i; j--) { man->free[j] = man->free[j - 1]; } man->frees++; if (man->maxfrees < man->frees) { man->maxfrees = man->frees; } man->free[i].addr = addr; man->free[i].size = size; return 0; } man->losts++; man->lostsize += size; return -1; }
メモリ管理用に作った構造体MEMMANには「frees,maxfrees,lostsize,losts,free」の５つが入っていて、その中のfree[ ]は「空いているメモリの番地と大きさの情報が(○○から--だけ空いていると言った感じに)入っている構造体FREEINFO」の配列です。
メモリが必要になったら、MEMMANの中のfree[ ]から（free[i].sizeを見て）必要な大きさを確保できるところを探し、見つかったらその部分を確保。その部分は空き情報リストから削除します。反対に解放する時は、空き情報を追加して隣の空き地とひとまとめに出来ないかを調べ可能であればまとめるといった作業をしています。
後半は結構本の説明を借りちゃってますが..まぁ９日目はこんなところで。MINIX本の方のメモリ管理の章は手を付けていなかったと思うので、なるべく早めに読んでみようと思います。
おやすみなさい〜
OS学習メモ8(30日OS自作入門8日目)
８日目、今度こそマウスを動かす。
ここまでやってきてマウスからのデータを受け取れるようになったので、あとはそれを解読し、それにあわせてカーソルを動かせばよいだけ。ここからは本に沿ってやっていく。
i = fifo8_get(&mousefifo); io_sti(); if (mdec->phase == 0) { if (i== 0xfa) { mdec->phase = 1; } return 0; } if (mdec->phase == 1) { mdec->buf[0] = i; mdec->phase = 2; return 0; } if (mdec->phase == 2) { mdec->buf[1] = i; mdec->phase = 3; return 0; } if (mdec->phase == 3) { mdec->buf[2] = i; mouse->phase=1 sprintf(s, "%02X %02X %02X", mouse_dbuf[0], mouse_dbuf[1], mouse_dbuf[2]); boxfill8(binfo->vram, binfo->scrnx, COL8_008484, 32, 16, 32 + 8 * 8 - 1, 31); putfonts8_asc(binfo->vram, binfo->scrnx, 32, 16, COL8_FFFFFF, s); }
マウスからデータが３バイト送られてくるので３バイトたまった時点で画面に表示。
途中経過
こんな感じで解読はできた。
あとは表示部分を変えていく。
i = fifo8_get(&mousefifo); io_sti(); if (mouse_decode(&mdec, i) != 0) { //マウスを消す boxfill8(binfo->vram, binfo->scrnx, COL8_00FF00, mx, my, mx + 15, my + 15); mx += mdec.x; my += mdec.y; if (mx < 0) {mx = 0;} if (my < 0) {my = 0;} if (mx > binfo->scrnx - 16) {mx = binfo->scrnx - 16;} if (my > binfo->scrny - 16) {my = binfo->scrny - 16;} putblock8_8(binfo->vram, binfo->scrnx, 16, 16, mx, my, mcursor, 16); //マウスを描く }
カーソルがあった位置に背景色を書き込んでマウスカーソルを消して再度カーソルを描くという内容（↓の画像ではなんとなく色を変えてみたのでお絵描きみたいになっている）
見て分かる通り、下側の部分もboxfill関数で作ったただの四角形なので、カーソルを持っていくと上書きされてしまう。この問題は10日目から直していく。
簡単だけどこの辺で。
