JD(情報系大学生)雑記

JD-情報系大学生-

OverTheWire のbanditをやる(途中)

OverTheWire: Bandit

途中までだけど、とりあえず詰まってしまったのでできてるところまで...
周辺知識を理解するところまでが最終的な目標ですが、まずは解ききることを優先します。どうしてもわからない所はwrite upを見るつもりですがなるべく自分で...

 

※ちょっと放棄気味(18/12/29/14:34)

 

Level0→1

ユーザ名bandit0,ホスト名bandit.labs.overthewire.orgsshするだけ。パスワードは書いてある通りbandit0に。

 

Level1→2

ホームディレクトリのreadmecat等で読むだけ

boJ9jbbUNNfktd78OOpsqOltutMc3MY1

 

Level2→3

-っていうファイル名なので、"cat -" とかやるとオプションと勘違いされちゃう。絶対パスで指定する。

$ cat /home/bandit1/-

CV1DtqXWVFXTvM2F0k09SHz0YwRINYA9

 

Level3→4

ファイル名にスペースが入ってるのでバックスラッシュ\でエスケープさせる

$cat spaces\ in\ this\ filename

UmHadQclWmgdLOKQ3YNgjWxGoRMb5luK

 

Level4→5

$ls -a すると、隠しファイル”.hidden”があったからcatで読む。

pIwrPrtPN36QITSp3EQaw936yaFoFgAB

 

Level5→6

”-file00”から”-file09”の9つのファイルがあってhuman-readableなものを探せってことだった。

$ file /home/bandit4/inhere/-file0*

って打ってみたら-file07だけASCII textだったのでcatで読んだ。

koReBOKuIDDepwhWk7jZC0RTdopnAYKh

 

Level6→7

inhereディレクトリのなかに更にmaybeinhere01からmaybeinhere19まであって、更にその中にもいくつかファイルがある。人間が読める,1033バイト,実行不可っていう条件があるのでfindコマンドで探すことにした。

$ find /home/bandit5/inhere/ -size 1033c

って打ったら、/home/bandit5/inhere/maybehere07/.file2だけが条件に当てはまった(他の条件は使わなかった)のでこれをcatした。

DXjZPULLxYr17uwoI01bNLQbtFemEgo7

 

Level7→8

level6と同じ感じだけれど今度は検索すべき範囲がサーバ全体っていうことに加えて条件も変わった。所有者はbandit7、所有グループはbandit6,サイズが33バイト。findのオプションについて調べていたら-lsが使えそうだったので

$ find / -size 33c -ls|grep bandit7

ってやったらだいぶ絞り込めた。

適当にcatして、/var/lib/dpkg/info/bandit7.passwordというところにあった。

HKBPTKQnIay4Fw76bEy8PVxKEDQRKTzs

 

Level8→9

”英単語 + flagっぽい文字列”っていうのがひたすら並んでた。

これはgrepするだけででいい。

cvX2JJa4CFALtqS87jk27qwqGhBM9plV

 

Level9→10

ひたすら並んでる中で、重複していない行のものがフラグだよってこと。“cat 重複”とかGoogleで調べてるうちにuniqコマンドがあったことを思い出した。

$ sort data.txt |uniq -u

UsvVyFSfZZWbi6wgC7dAFyFuR6jQQUhR

 

Level10→11

catすると一見文字化けして読めないように見えるけれど、いくつかの’=‘文字で始まるhuman-readableな文字列があるらしい。そういうことならstringsコマンドで良さそう。

$ strings data.txt とやって該当するものが見つかった

truKLdjsbJ5g7yyJ2X2R0o3a5HQJFuLk

 

Level11→12

Base64で暗号化されてるので、

$ base64 data.txt -d

でデコードするだけだった。(この程度なら反射的に解けちゃうんだけども、そもそも暗号周り全然知らないから勉強しなきゃなぁ

IFukwKGsFW8MOq3IRFqrxE1hxTNEbUPR

 

Level12→13

ROT13。戻してくれるページを調べて、そこに投げておしまい。

5Te8Y4drgCRfCx8ugdwuEX8KFC6k2EUu

 

Level13→14

去年一回解いたはずの問題なんだけど、改めて見たらそもそもhexdump(16進ダンプ)ってなんだっけって感じになって色々調べた。どうやらバイナリとか色んなデータをそのまま16進数の形式で表示するらしい。xxdコマンドの-rオプションを使えば復元出来るみたいなので、/tmp下にディレクトリを作って

$ xxd -r data.txt > /tmp/myname_yamahiro/test

とやってみて、次にこいつをfileコマンドで調べてみた。

/tmp/myname_yamahiro/test: gzip compressed data, was…(略)ということで、どうやらgzipで圧縮されているらしい。gzip -d testってやったらunknown suffix -- ignored って出てきて、どうやら拡張子を.gzにしないとダメみたいだったのでmv test test.gz でファイル名を変更してからgzip -d test.gzってやったらちゃんと展開できた。

ここで出てきたtestっていうファイル(さっきのtestとは別物)をfileコマンドで調べるとbzip2だったから、拡張子.bz2を付けて更に展開。

こんな感じで出てきたものを何度も展開していくとbata5.binというやつが出てくる…と思ったらこいつもtarだった時はイラッとしたけど、本当に最後まで展開したら8ZjyCRiBWFYkneahHwxCv3wb2a1ORpYLというflagが出てきた…疲れたなぁ。

 

Level14→15

次のlevelに進むために必要なパスワード(flag)が別のユーザしか読めないファイルに書いてある。パスワードはわからないけどssh鍵はあるということなので、sshの-iオプション使い、ssh -i sshkey.private bandit14@localhost で入って、さっきのファイルをcat。4wcYUJFw0k0XLShlDzztnTBHiqxU3b3e

 

Level15→16

ネットワークは今までロクに勉強してこなかったから、サーバに文字列投げるだけだけど分からなかった。仕方ないのでとりあえずnc(というコマンドがネットワークのスイスアーミーナイフってことだけは授業で習って知っていたので)調べた。…まぁncの一番基本的な使い方なので秒で出てきた。

nc localhost 30000 ってやって、前問で得たflagを投げてみたらcorrect!って言ってflagを得られた。BfMYroe26WYalil77FoDi9qh59eK5xNr

 

Level16→17

SSL暗号化通信してlocalhostの30001番ポートに前問のパスワードを投げる問題。openSSL調べて、ヒットしたサンプルをコピーしてごちゃごちゃやってたら出来たんだけど、そもそもopensslの引数のとり方とかなんかもう色々よくわからないから後で調べてまとめる(なので余裕があれば追記予定)

$ echo "BfMYroe26WYalil77FoDi9qh59eK5xNr"|openssl s_client -connect localhost:30001 -ign_eof

とやったらcorrect!と帰ってきてcluFn7wTiGryunymYOu4RcffSxQluehd

 

Level17→18(途中)

再びパスワード提出系の問題。ポート番号31000-32000のどこかがlistenになっているとのこと。

$ nmap -sT -p 31000-32000 localhost

とやってみると、ポート番号31518と31790の2つが開いていた。

echo "cluFn7wTiGryunymYOu4RcffSxQluehd"|openssl s_client -connect localhost:31518 -ign_eof

echo "cluFn7wTiGryunymYOu4RcffSxQluehd"|openssl s_client -connect localhost:31790 -ign_eof

どちらも試したら後者の方でcorrect!って帰ってきた。しかし今回得られたはflagではなくてRSA秘密鍵だった。これ使ってssh -iでログインするんだと思ったけれどホームディレクトリにはファイル作れないっぽいので、/tmp下に適当にファイル作ってコピペした。これでログインを試みたら、”他のユーザも見れるようになってるパーミッション”ではダメだよって起こられたから600に設定して再度試したけれどこれもダメ。今度のエラーは.ssh/known_hostsに書き込めないよってことみたい(そもそもls -aしても無い)。ここで手詰まり中。

2018年の某の応募課題を今更ながら...

一部書き換えてますが、2018年のseccampに応募したときに書いたやつです(→落ちました)。これ書いた時点で予備知識が完全にゼロだったので、”常識”を堂々と書いちゃってると思いますし、間違ってること書いてるかもしれないです(...とにかく手を動かせって言われてたので気にせず提出したんですけど笑)。

アップするかどうか迷いましたけど”とりあえず2018年も終わるしなんとなく上げておくかぁ”くらいの気持ちです。間違いがあってもそれを今の僕じゃぁ確かめられないので(勉強不足)、とにかく勉強しなきゃいけないなぁ...

----(以下本文)----

大学のSoralis演習室を使いました。

いきなりですが、”prtconf -D”を実行した時の結果が以下になります。

$prtconf -D 

 

System Configuration:  Oracle Corporation  i86pc

Memory size: 65404 Megabytes

System Peripherals (Software Nodes):

 

i86pc

    scsi_vhci, instance #0

        disk, instance #3

        disk, instance #1

        disk, instance #2

        disk, instance #0

    pci, instance #0

        pci8086,0 (pciex8086,6f00) (driver not attached)

        pci8086,6f02 (pciex8086,6f02) (driver not attached)

        pci8086,6f04 (pciex8086,6f04) (driver not attached)

        pci8086,6f08 (pciex8086,6f08), instance #2

            pci1000,9361 (pciex1000,5d), instance #0

                iport, instance #1

        pci8086,6f0a (pciex8086,6f0a), instance #3

            pci108e,4852 (pciex8086,1528), instance #0

            pci108e,4852 (pciex8086,1528), instance #1

        pci8086,0 (pciex8086,6f20) (driver not attached)

        pci8086,0 (pciex8086,6f21) (driver not attached)

        pci8086,0 (pciex8086,6f22) (driver not attached)

        pci8086,0 (pciex8086,6f23) (driver not attached)

        pci8086,0 (pciex8086,6f24) (driver not attached)

        pci8086,0 (pciex8086,6f25) (driver not attached)

        pci8086,0 (pciex8086,6f26) (driver not attached)

        pci8086,0 (pciex8086,6f27) (driver not attached)

        pci8086,6f28 (pciex8086,6f28) (driver not attached)

        pci8086,6f29 (pciex8086,6f29) (driver not attached)

        pci8086,6f2a (pciex8086,6f2a) (driver not attached)

        pci8086,0 (pciex8086,6f2c) (driver not attached)

        pci108e,4852 (pciex8086,8d7c) (driver not attached)

        pci108e,4852 (pciex8086,8d3a) (driver not attached)

        pci108e,4852 (pciex8086,8d3b) (driver not attached)

        pci108e,4852 (pciex8086,8d2d), instance #0

            hub, instance #0

        pci8086,8d10 (pciex8086,8d10) (driver not attached)

        pci8086,8d1e (pciex8086,8d1e), instance #5

            display (pciex102b,522), instance #0

        pci108e,4852 (pciex8086,8d26), instance #1

            hub, instance #1

                hub, instance #2

                    device, instance #3

                        keyboard, instance #8

                        input, instance #9

                        mouse, instance #10

                        mouse, instance #11

                communications, instance #0

        isa (pciex8086,8d44), instance #0

            asy, instance #0

            pit_beep, instance #0

        pci108e,4852 (pciex8086,8d02), instance #0

            cdrom, instance #4

        pci108e,4852 (pciex8086,8d22) (driver not attached)

    ioapics (driver not attached)

        ioapic, instance #0 (driver not attached)

        ioapic, instance #1 (driver not attached)

    pci, instance #1

        pci8086,6f80 (pciex8086,6f80) (driver not attached)

        pci8086,6f32 (pciex8086,6f32) (driver not attached)

        pci8086,6f83 (pciex8086,6f83) (driver not attached)

        pci8086,6f90 (pciex8086,6f90) (driver not attached)

        pci8086,6f33 (pciex8086,6f33) (driver not attached)

        pci8086,6f93 (pciex8086,6f93) (driver not attached)

        pci8086,6f81 (pciex8086,6f81) (driver not attached)

        pci8086,6f36 (pciex8086,6f36) (driver not attached)

        pci8086,6f37 (pciex8086,6f37) (driver not attached)

        pci8086,6f76 (pciex8086,6f76) (driver not attached)

        pci8086,6fe0 (pciex8086,6fe0) (driver not attached)

        pci8086,6fe1 (pciex8086,6fe1) (driver not attached)

        pci8086,6fe2 (pciex8086,6fe2) (driver not attached)

        pci8086,6fe3 (pciex8086,6fe3) (driver not attached)

        pci8086,6fe4 (pciex8086,6fe4) (driver not attached)

        pci8086,6fe5 (pciex8086,6fe5) (driver not attached)

        pci8086,6fe6 (pciex8086,6fe6) (driver not attached)

        pci8086,6fe7 (pciex8086,6fe7) (driver not attached)

        pci8086,6ff8 (pciex8086,6ff8) (driver not attached)

        pci8086,6ff9 (pciex8086,6ff9) (driver not attached)

        pci8086,6fe0 (pciex8086,6ffc) (driver not attached)

        pci8086,6fe0 (pciex8086,6ffd) (driver not attached)

        pci8086,6fe0 (pciex8086,6ffe) (driver not attached)

        pci8086,6f1d (pciex8086,6f1d) (driver not attached)

        pci8086,6f34 (pciex8086,6f34) (driver not attached)

        pci8086,6f1e (pciex8086,6f1e) (driver not attached)

        pci8086,6f7d (pciex8086,6f7d) (driver not attached)

        pci8086,6f1f (pciex8086,6f1f) (driver not attached)

        pci8086,6fa0 (pciex8086,6fa0) (driver not attached)

        pci8086,6f30 (pciex8086,6f30) (driver not attached)

        pci8086,6fa8 (pciex8086,6fa8) (driver not attached)

        pci8086,6f71 (pciex8086,6f71) (driver not attached)

        pci8086,6faa (pciex8086,6faa) (driver not attached)

        pci8086,6fab (pciex8086,6fab) (driver not attached)

        pci8086,6fac (pciex8086,6fac) (driver not attached)

        pci8086,6fad (pciex8086,6fad) (driver not attached)

        pci8086,6fae (pciex8086,6fae) (driver not attached)

        pci8086,6faf (pciex8086,6faf) (driver not attached)

        pci8086,6fb0 (pciex8086,6fb0) (driver not attached)

        pci8086,6fb1 (pciex8086,6fb1) (driver not attached)

        pci8086,6fb2 (pciex8086,6fb2) (driver not attached)

        pci8086,6fb3 (pciex8086,6fb3) (driver not attached)

        pci8086,6fbc (pciex8086,6fbc) (driver not attached)

        pci8086,6fbd (pciex8086,6fbd) (driver not attached)

        pci8086,6fbe (pciex8086,6fbe) (driver not attached)

        pci8086,6fbf (pciex8086,6fbf) (driver not attached)

        pci8086,6fb4 (pciex8086,6fb4) (driver not attached)

        pci8086,6fb5 (pciex8086,6fb5) (driver not attached)

        pci8086,6fb6 (pciex8086,6fb6) (driver not attached)

        pci8086,6fb7 (pciex8086,6fb7) (driver not attached)

        pci8086,6f68 (pciex8086,6f68) (driver not attached)

        pci8086,6f6e (pciex8086,6f6e) (driver not attached)

        pci8086,6f6f (pciex8086,6f6f) (driver not attached)

        pci8086,6fd0 (pciex8086,6fd0) (driver not attached)

        pci8086,6fb8 (pciex8086,6fb8) (driver not attached)

        pci8086,6fb9 (pciex8086,6fb9) (driver not attached)

        pci8086,6fba (pciex8086,6fba) (driver not attached)

        pci8086,6fbb (pciex8086,6fbb) (driver not attached)

        pci8086,6f98 (pciex8086,6f98) (driver not attached)

        pci8086,6f99 (pciex8086,6f99) (driver not attached)

        pci8086,6f9a (pciex8086,6f9a) (driver not attached)

        pci8086,6fc0 (pciex8086,6fc0) (driver not attached)

        pci8086,6f9c (pciex8086,6f9c) (driver not attached)

        pci8086,6f88 (pciex8086,6f88) (driver not attached)

        pci8086,6f8a (pciex8086,6f8a) (driver not attached)

    pci, instance #2

        pci8086,6f02 (pciex8086,6f02), instance #6

            pci108e,4852 (pciex8086,1528), instance #2

            pci108e,4852 (pciex8086,1528), instance #3

        pci8086,6f08 (pciex8086,6f08) (driver not attached)

        pci8086,0 (pciex8086,6f20) (driver not attached)

        pci8086,0 (pciex8086,6f21) (driver not attached)

        pci8086,0 (pciex8086,6f22) (driver not attached)

        pci8086,0 (pciex8086,6f23) (driver not attached)

        pci8086,0 (pciex8086,6f24) (driver not attached)

        pci8086,0 (pciex8086,6f25) (driver not attached)

        pci8086,0 (pciex8086,6f26) (driver not attached)

        pci8086,0 (pciex8086,6f27) (driver not attached)

        pci8086,6f28 (pciex8086,6f28) (driver not attached)

        pci8086,6f29 (pciex8086,6f29) (driver not attached)

        pci8086,6f2a (pciex8086,6f2a) (driver not attached)

        pci8086,0 (pciex8086,6f2c) (driver not attached)

    fw, instance #0

        sb, instance #1

            socket, instance #2

                cpu, instance #0

                cpu, instance #1

                cpu, instance #2

                cpu, instance #3

                cpu, instance #4

                cpu, instance #5

                cpu, instance #6

                cpu, instance #7

                cpu, instance #8

                cpu, instance #9

                cpu, instance #10

                cpu, instance #11

            socket, instance #3

                cpu, instance #12

                cpu, instance #13

                cpu, instance #14

                cpu, instance #15

                cpu, instance #16

                cpu, instance #17

                cpu, instance #18

                cpu, instance #19

                cpu, instance #20

                cpu, instance #21

                cpu, instance #22

                cpu, instance #23

    used-resources (driver not attached)

    fcoe, instance #0

    iscsi, instance #0

    agpgart, instance #0

    options, instance #0

    pseudo, instance #0

    vga_arbiter, instance #0

    xsvc, instance #0

    intel-iommu, instance #0

    intel-iommu, instance #1

partconfはシステム構成を出力するコマンドで、-Dオプションを指定すると、周辺機器ごとにそれを管理するために使用されているデバイスドライバの名前を表示してくれます。インデントで階層構造を表現してます(最初はこれをどうやって読むのかも分かりませんでした)

つまり以下の部分は、

pci, instance #0

        pci8086,0 (pciex8086,6f00) (driver not attached)

        pci8086,6f02 (pciex8086,6f02) (driver not attached)

        pci8086,6f04 (pciex8086,6f04) (driver not attached)

        pci8086,6f08 (pciex8086,6f08), instance #2

            pci1000,9361 (pciex1000,5d), instance #0

                iport, instance #1

        pci8086,6f0a (pciex8086,6f0a), instance #3

            pci108e,4852 (pciex8086,1528), instance #0

下図ようになってます

f:id:unyamahiro:20180525002207p:plain

(ちなみにここで、実行結果の方で「driver not attached 」となっている部分がありますが、これはデバイスが繋がっていない(あるいは使用中ではない)ために、デバイスインスタンスに現在接続されているドライバがないことを意味していて、ドライバは、デバイスがアクセスされると自動的にロードされデバイスが使用されなくなると自動的にアンロードされます)

 

ここで、pci8086とpci1000などが何を意味しているのかが気になりました。「pciex8086は恐らくpci expressのことだろう」という感じで多少の類推はできるのですが、考えてもそれ以上のことが分からなかったので調べました。

The PCI ID Repositoryを見たら、どうやらこれらはデバイス名であるらしいことがわかりました。例えば”pciex8086,6f02”だと(https://pci-ids.ucw.cz/read/PC/8086/6f04PCI Express Root Port 2と書いてあって、詳細はともかく、「何をするためのものか」くらいは調べればなんとなく分かる状態になりました。

それがわかった上で、以下の部分を見てみます。

  pci, instance #2

        pci8086,6f02 (pciex8086,6f02), instance #6

            pci108e,4852 (pciex8086,1528), instance #2

            pci108e,4852 (pciex8086,1528), instance #3

まずいちばん上の”pci instance #2”と書いてあるところがおそらくホスト-PCIブリッジで、ここには今pciex8086,6f02が繋がれています。この記事によると、PCI Expressのシステムを構成する要素の一つにはルートコンプレックスというものが存在し、そこには1つ以上のPCIeポートがあるということなので、恐らくpci8086 6f02がそのルートコンプレックスなのだろうと分かります。そして、その下層に2つ繋がっているpci108e,4852 (pciex8086,1528)を調べてみると、デバイス名がEthernet Server Adapter X540ということで、ネットワークに関する何かなのだということが分かりました。 

 

他にも聞き覚えのないデバイスをいくつか調べてみました。

scsi_vhci

パソコンと周辺機器をつなぐ規格で主にハードディスクなどのドライブを接続するために使われるが、最近では同じ用途にUSBやIEEE1394を使用するのが一般的で、SCSIはあまり使われなくなった

ioapics

I/Oデバイスから受け取った割り込みを、CPUへ通知する

fcoe    

イーサネットを通じてファイバチャネルのフレーム転送を行うためのもの。Storage Area Networkという、(名前通りに)ストレージをネットワークを経由して利用する仕組みを構築するために使われる

iscsi

FCoeEと同じく、SANを利用する仕組みを実現するために使われる。上述したSCSIのデータをTCP/IPで利用できるようにするもの。

 

--(本文終わり)--

※他にも色々書きましたが、残っているのがこれだけでした。

なんか今になって読むと、もっと色々手動かせばできることあったんじゃない?って思います(まぁこれだけでもかなり時間かかった思い出あるのですが笑)

来年も応募するつもりなので...精進しなくてはいけませんね...。

OS学習メモ13 (MINIX本4.3-4.3.2章)

本自体は既に一回読んだんですが、復習を兼ねてこの記事を書くためにわざわざ”The MINIX book Operating system implementation”を図書館から借りてきました。持ち歩くのが重いったらないです()

このブログの更新を半年サボりましたけど、これから少しずつ更新していこうかなって思ってます(授業があるのでしばらくは休日だけ)半年前どんな感じで書いてたか覚えてませんけど、僕がこの手のものを書く時は基本的に「まず一通り読む→(自分の言葉を8割と本の言葉を2割使って)再構成」って感じでやってます。洋書で読んでるのでもしかしたら英語の間違いによる致命的な間違いがある可能性もあるので違和感感じたら各自改めて調べてください

 

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.変換が高速に行われなくてはいけないこと」である。

1、32ビットの仮想アドレス幅を持っているとすると、ページサイズが4KBとして約100万ページ(2^32/4KB)あることになる。これがもし64ビットなら4.5*10^15に…考えたくない。

2、メモリが参照される度に”仮想→物理”の変換がなされるという点に問題がある。典型的な命令は命令ワードとメモリオペランドを持っているので、一命令あたり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(仮想記憶)は少し長いので区切りの良いところまで。

メモリ管理システムは2つに分類できる。一つはプロセスの実行中にその内容をメモリとディスク間で移動するページング方式で、もう片方の方式ではそれを行わない(後者の方が単純なのでそちらから見ていく)

 

4.1.1 スワップ,ページングを必要としない単一プログラミング

最も単純なメモリ管理方式は、プログラムとOSがメモリを共有して同時に一つのプログラムしか実行しない方式である。これには3つの方法があって、「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を加算するという方法である。だが、ローディング中の再配置は記憶保護の問題を解決できない。悪意のあるプログラムが常に新しい命令列を作って実行するかもしれない。このため、再配置と記憶保護の別の方法として、ベースレジスタと境界レジスタの2つの特殊なハードウェアレジスタを用いることがある。あるプロセスがスケジュールされると、ベースレジスタにはパーティションの先頭アドレス、境界レジスタにはパーティションの長さが入り、メモリアドレス生成の度に自動的にベースレジスタの内容がアクセス前に加算されるようになる。アドレスは現在のパーティション外のメモリにアクセスしないように境界レジスタによって保護されていて、これらは改竄されることもない。

 

4.2 スワッピング

スワッピングとは、プロセス全体を主記憶にロードして暫く実行させた後で、ディスクに吐き出してプロセスを停止するというのを繰り返す方法で、ここまでの固定パーティションの方式とは違ってパーティションの数や位置やサイズが動的に変化する。この分、柔軟性は高まったといえるけれども、メモリを割り当てたり開放するための管理の複雑さは増している。スワッピングを繰り返すとメモリの中に小さな空き領域が出来るので、プロセスを移動することによってそれらを一箇所にまとめることが出来る(これはメモリコンパクションと呼ばれる)。そして肝心のスワッピングだが、プロセスにどのくらいのメモリ量を割り当てるかは重要な問題である。

 

動的にメモリを割り当てる歳に、OSははそれを管理する必要がある。使用状況の管理には一般に2つの方法ービットマップによる管理とリストによる管理ーがある。

 

4.2.1 ビットマップによるメモリ管理

あらかじめ”単位”を決めてメモリを分割し(数ワードとか数KBとか)、その単位ごとに「空き」ならば0,「使用中」ならば1をつけて管理する方法。当然ながらこの”単位”を小さくすればするほどビットマップは大きくなる。この方法はメモリサイズと割り当てる単位によって決まるので、一定サイズのメモリを使って全メモリの管理を可能とする簡単な方法であるが、与えられたビットパターンをビットマップ上から探すのは一般的に処理が遅くなるという問題点がある。

 

4.2.2  リンクリストによるメモリ管理

パーティションをリスト構造にして連結して管理する方法。それぞれのリンクには「空き/使用中」「各パーティションの先頭アドレス」「各パーティションの長さ」「次のパーティションの情報」が入っている。以下はリストを管理するためのアルゴリズムである。

 

ファーストフィットは該当プロセスのメモリ容量を最初に満たす空きリストを見つけるまで探すもの。ネクストフィットはファーストフィットと同じように空きを探すが、見つかった位置を記憶しておいて、次にコールされるとそのリストの場所から求める空きリストを探す(ファーストフィットと違って最初からは探さない)。ベストフィットは、全リストを調べて空き容量が最小になるエントリを求める。ワーストフィットは、プロセスに割り当てた後で空きと成る部分で最大になるような選択法。クイックフィットは、比較的よく要求されるサイズごとに別々の空きリストを作って管理する。

 

4.3は今読んでいます。

OS学習メモ11(30日OS自作入門11日)

やっていきましょう。
スタートはここから。

ご覧の有様です。
右端に行ったら変な動きをしているので、画面外に出てしまった時には値を補正するようにします。このくらいであれば本を読まなくても自分で直せました。 そんなに大きな変更も加えてないのでプログラムは省略します。


次に「shtctlの指定を省略する」ということをやります。難しいことは特になくて(前回作ったsheet_updown関数を見てもらえればわかるんですけど)下敷きを上げ下げするために毎回ctlを指定しているのが面倒くさいからそれを改良しようというだけのことです。

(久しぶりなので前回作ったsheet_updown関数を簡単におさらいしておくと、この関数はまず引数として「SHTCTL型の*ctl」「SHEET型の*sht (高さを変更したい下敷きの情報)」「int型のheight(変更後の下敷きの高さ)」の3つを受け取ります。受け取った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関数が好きです。

実行結果↓
f:id:unyamahiro:20180609092325p:plain


ここまで順調にやってこれました。次はカウンタを作ります。その名の通り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);
}

で、動かしてみると

書き換える必要のない背景の下敷きまで書き換えてるからこういったことが起きてしまってます。というわけで、必要な部分だけ書き換えるように書き換えたものがこれです。高さを指定してます。

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”を使う方法です。言葉でうまく説明できませんが下の図が全てです。

f:id:unyamahiro:20180609091933p:plain

例えば図中で一番下の下敷きをリフレッシュするなら、右側で”1”になっているところだけを書き変えればいい(2の所まで書き直す必要はない)というわけです。これを使ってマウスカーソルの所を避けて画面をリフレッシュしようというわけですね。




...と、いうのが仕組みの話で….ここまではわかったのですが…、正直、実装の所はコードを読んで考えても良くわかりませんでした。この本、後になって読み返したらすっと分かるとかよくあるのでちょっとこの辺り一旦スキップしようと思います。というわけで半端ですがここまで。

「半年前くらいにOS本やった」といっても、この辺りからで内容がほとんど頭に残っていないという感じなので初見とあんまり変わりません。そしてよくわからない所がちらっと出てきました。頑張らないといけませんね。

CTFに初参加した(SECCON Beginners CTF)

5月26日から27日にかけてSECCON Beginners CTFに一人で参加しました。これまで何度か常設のものを解いてみたことはありましたが、こうして大会っぽい大会に参加するのは初めてでした。

warm up5つしか解けず残念な結果に終わってしまいました。

f:id:unyamahiro:20180527231234p:plain

この記事を書いている5月27日22時45分現在、まだ他の人が書いたwrite upには全く目を通していないのですが、僕もCTFの大会に出た以上はwrite upを書いたりしてアウトプットとかしないと成長しないと思うので、(正直今回に関しては恥ずかしくて書きたくないんですけど)今後出場したものに関してはなるべく書いていこうと思います。

************************

[Warmup] Veni, vidi, vici 51 (Crypto)

3つのテキストファイルが渡される。
1つ目は見た感じがもうシーザー暗号っぽいので、ROT13したら"The first part of the flag is: ctf4b{n0more"が出てきた。
2つ目もシーザー暗号っぽかったため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出てしまった。なんかごめんなさい

f:id:unyamahiro:20180527224912p:plain

[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チャンネルみたら堂々と書いてあった

 

************************

恐れ恥ずかしながらこんな感じです...

OS学習メモ10(30日OS自作入門10日目)

通信制限のためか画像アップロードできないので後ほど修正加えます)
※修正しました(5/24 8:40)

さて10日目,ようやく3分の1ですね。先日これまでの記事をさっと見直してみたのですが、人に読ませることを想定してない自己満足の記事っぽいなって思ったので、ちゃんとまとめっぽく書くことを意識しようと思います…(笑)

ではやっていきしょう。
最初の方でちょっとメモリ管理の続きでmallocっぽいのを作ったり、切り上げ切り捨てのやり方の話とかの話もあるのですが、ちょっとその辺りはスキップしまして早速8日目の続きからいきたいのですが、8日目の記事書いたのだいぶ前なので、ちょっと振り返るところから。

8日目の所でマウスカーソルが動くようになったのですが、その処理を「カーソルの上に色を上塗りして見えなくする→再びカーソル描画」とやっていたために、マウスを動かす度に画面を破壊してしたところで終わりましたね。

f:id:unyamahiro:20180505121905p:plain

さて今回はこれを解決するために重ね合わせをやっていこうという所です。
イメージとしてはまさにお絵かきする時とかに使う”レイヤー”ですね。
ここでは”透明な下敷きにかいた絵”を重ねると表現されています。

というわけで、まずはその下敷きとやらを定義します。

struct SHEET{
	unsigned char *bar;
	int bxsize,bysize,vx0,vy0,col_inv,height,flags;
}

(そういえば、今回は構造体があたまの中でごちゃごちゃしたのでいつにも増して図が多いです。自分の備忘録のつもりですが、誰かの理解の助けになったりすれば嬉しいです)

構造体SHEETのイメージはこんな感じ。
f:id:unyamahiro:20180524083259p:plain
これで一枚分の情報が出来ましたね。
では次に、複数枚の下敷きを管理するための”下敷き管理用構造体”を作ります。

struct SHTCTL{
	unsigned char *vram;
	int xsize,ysize,top;
	struct SHEET *sheets[256];
	struct SHEET sheets0[256];
}

f:id:unyamahiro:20180524083127p:plain

sheets0で一枚一枚に下敷きの情報を保持しておきます。この時、どの下敷きが上にあってどれが下かとかは関係なくバラバラに格納されているので、それを下層から順に並べて番地だけを並べた構造体配列がsheetsです。イメージを見たほうが早い気がします。
f:id:unyamahiro:20180524083653p:plain


これで管理の準備が整いました。この下敷き管理構造体を記憶するためのメモリを確保してぱぱっと値を設定。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よりも上に指定する必要はないし、同様に低すぎる値にする必要もありません。最下層を0ではなく−1にしていますが、これは下敷きを非表示にする時のためです(地下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;
}

ここは、コードと図を一緒に見てください。
f:id:unyamahiro:20180524083846p:plain
(ここでは青を一番下に持っていく例で考えます)
一回のループで↓をやります。
f:id:unyamahiro:20180524083926p:plain
最終的にはこうなります。
f:id:unyamahiro:20180524084010p:plain
下敷きを非表示にした場合は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関数とやってることは同じです。

あとは、下敷きをずらしたり,使い終わった下敷きを解放したり,といった関数をちょこっと追加してやると動きます。

(本ではここから更に重ね合わせの処理の無駄を取り除いたりして高速化をするのですが…今日はちょっと大学の課題が山積みになっているので、まとめをここまでにして最後に動画で報告だけします(汗)。時間がある時に書きますね。)


平井堅「トドカナイカラ」いい曲です)

だいぶGUIっぽく、OSっぽくなってきましたね!
画像、くどかったかも...