UNIX 6th code reading - バッファ
はじめに
今回は17章を読み解いていきます。
17章はバッファ操作に関する内容が書かれています。15-17章はお互いに関連しているので繋がりを意識しながら読むと理解がしやすいと思います。
バッファの概要
バッファという機構を用いてブロックデバイスを操作します。
ブロックデバイスの操作で重要なのは以下だと思います。
- 複数あるプロセスが同時に(とは言っても時分割されていますが)同デバイスの同ブロックにアクセスしたときに、データの一貫性を保つ(所謂コヒーレンシ)
- よく使われるデバイスのデータをコアにコピーしておくことで、デバイスへのアクセスを減らし全体の性能を上げる(デバイスへのアクセスはプロセッサの動作と比較すると遅い)
バッファの構成
バッファは4535行で宣言されているbuf[NBUF]という構造体の配列です。bufはバッファの状態やフラグを表し、バッファのヘッダとも言えます。実際に(ブロックデバイスの)データを保持する場所はb_addrで指すアドレスです。
そのデータを保持するバッファは4720行目で宣言されているbuffers[NBUF][514]です。binit( )でbufとbuffersの関連付けが行われます。
これらの話は以前のエントリでも触れています。
buf[NBUF]は二種類の二重リンクを形成しています。b-listとav-listです。
b-listは各ブロックデバイス毎に割り当てられているバッファを表すリンクです。b_forw, b_backを使ってリンクが形成されます。
av-listは他のデバイスにも再割り当てが可能なバッファ(freeなバッファ)を表すリンクです。b-listとav-listは独立ではありません。ただし、現在使用中のバッファはav-listには含まれません。av_forw, av_backを使ってリンクが形成されています。
絵で描くとこんな感じです。
4656行目でbdevsw[ ]が設定されています。デバイス毎に適切な手続きを指定します。bdevsw構造体は4617行目で宣言されており、bdev.d_tabが各デバイス毎のb-listのヘッダになります。
bfreelistは4567行目で宣言されており、buf構造体です。av-listのヘッダであり、かつ、NODEVのb-listでもあります。NODEVは恐らくどのデバイスにも割り当てられていないb-listであり、bufは最初binit( )でNODEV b-listに割り当てられます。(上図ではNODEV b-listは省略しています)
ブロックデバイスからデータを読み込む
ブロックデバイスからデータを読み込む(バッファを取得する)にはbread( )かgetblk( )を使います。引数でデバイスの種類とデバイス上のブロックNo.を渡すとバッファが返ってきます。
bread( )から返ってくるバッファには、実際にデバイスに保持されているデータと同じデータが含まれています。B_DONEというフラグでバッファのデータとデバイスのデータが同期が取れているかどうかが管理されており、同期が取れている場合はデバイスにはアクセスしません。キャッシュの役割を果たしています。同期が取れていない場合はデバイスへのアクセスを行い、データを取得します。
getblk( )はb-listから該当のバッファを探し出し、そのバッファを返します。デバイスとデータの同期が取れているかは気にしません。もし見つからなければav-listからバッファを取得します。そのバッファは該当b-listに再割り当てされます。bread( )内ではgdtblk( )を使ってバッファを取得しています。
breada( )というものもあり、これは非同期の読み込みも同時に開始させます。データを先読みしたいときに使うようです。
ブロックデバイスへの書き込み
バッファの書き込みはbwrite( ), bawrite( ), bdwrite( )を使います。
bwrite( )はバッファデータをデバイスへ書き込みます。デバイスへの書き込み操作を開始し、動作が完了するのを待ちます。(正確に言うとB_ASYNCというフラグが立っていなければ動作完了するのを待ちます)
bawrite( )は同様にデバイスへ書き込むのですが、デバイスの動作完了を待ちません。B_ASYNCというフラグを立ててからbwrite( )を呼び出します。
bdwrite( )は遅延書き込みを行います。言い換えると、ライトバックを行うためのバッファを扱います。すぐにはデバイスへ書き込みに行かず、遅延書き込みを行うことを示すB_DELWRIフラグを立てて、そのバッファをb-listから解放しav-listに追加します。getblk( )でav-listからあるb-listへ再割り当てを行うときに実際にデバイスに書き込みに行きます。
また、bflush( )という関数があり、遅延書き込みバッファをデバイスへまとめて書き込みます。bflush( )はupdate( )から呼び出され、update( )はpanic( ), sync( ), sumount( )から呼び出されます。不具合でpanicが起きたときでもデバイスのデータが最新になるようにしているようです。
Lions本によると、2分ごとに遅延書き込みバッファをフラッシュするユーティリティプログラムがunix上で動いているようです。
そのプログラムはたぶん/etc/updateというプログラムではないかと思います。(ただし、30秒ごとにsyncを実行しているようですが)
@oracchaさんがこのプログラムについて触れています。参考にどうぞ。
simh+pdp11+unix v6環境で(実機でも?)「終了時にsyncを実行してからログアウトしろ」と言われていますが、恐らく遅延書き込みバッファを反映させるためではないかと思います。(「syncを三回」とも言われていますが、なぜ三回？)
バッファ関連のソースコード
概要を理解できたので、次はソースコードの詳細を見ていきます。
clrbuf( )
clrbuf( )はバッファのデータ256word(512bytes)を0クリアします。
incore( )
incore( )は指定した「デバイス種類、そのデバイスのブロックNo.」を指すバッファが既に存在しているかどうかをチェックします。
存在していればそのバッファを返し、存在していなければ0を返します。
該当デバイスのb-listを線形探査し、bufのb_blkno, b_devをチェックします。
getblk( )
getblk( )は指定した「デバイス種類、そのデバイスのブロックNo.」を指すバッファを返します。
該当デバイスのb-listから線形探査し、該当バッファがないかチェックします。もしなければav-listから割り当てます。
- 4925 : extern lbolt; はなんのため？
- 4927 : デバイス種類を示すdev.d_majorが大きすぎたらpanic
- 4931-4932 : NODEV(-1)の場合。&bfreelist(NODEV b-listヘッダ)をdpに格納する。exec( )からNODEVでgetblk( )が呼ばれる
- 4934-4936 : NODEVでない場合、bdevsw[ ]から該当のデバイスのd_tab(b-list ヘッダ)を取得する。これがNULLだった場合はpanic
- 4937-4939 : b-listを線形探索して該当のバッファがあるかチェック
- 4940 : 見つかったらプロセッサ優先度を6に上げる
- 4941-4946 : そのバッファが使用中だったら(B_BUSYフラグが立っていたら)B_WANTEDフラグを立てて寝る
- 4947 : プロセッサ優先度を0に戻す
- 4948 : notavail( )を呼んでそのバッファをav-listから外してB_BUSYフラグを立てる
- 4949 : そのバッファをreturn
- 4952 : b-listから該当バッファが見つからなかったら。もしくは、NODEVのバッファを取得しようとしていたら。プロセッサ優先度を0に戻す
- 4953-4957 : av-listからバッファを取得しようとしているのだが、av-listが空だった場合。av-listの先頭ヘッダbfreelistのB_WANTEDフラグを立てて寝る
- 4959 : プロセッサ優先度を0に戻す
- 4960 : av-listの先頭バッファを取得し、notavail( )を呼んでav-listから外しB_BUSYフラグを立てる
- 4961-4965 : そのバッファにB_DELWRI(遅延書き込み)フラグが立っていたら、このタイミングでデバイスへの書き込みを行う。デバイスの動作完了はまたない
- 4966 : B_BUSYフラグを立てる。4960行目でB_BUSYフラグは既に立っていると思うのだが……。B_RELOCフラグは使われていないらしい
- 4967-4968 : 現在そのバッファが割り当てられているb-listからそのバッファを取り除く
- 4969-4972 : そのバッファを新しく該当のb-listの先頭に割り当てる
- 4973-4974 : そのバッファのb_dev, b_blknoを更新し、該当デバイスの該当ブロックを指していることを表すようにする
- 4975 : そのバッファをreturnする
notavail( )
notavail( )はav-listからバッファを取り除き、B_BUSYフラグ(使用中)を立てます
- 5006, 5011 : PS(プロセッサステータスワード)を保管、復帰させるのはなぜ？
- 5007 : プロセッサ優先度を6に上げたまま戻していないが、これでいいのか？
brelse( )
brelse( )はバッファを開放(B_BUSYフラグをリセット)し、av-listに追加します。
- 4876-4877 : このバッファを待っているプロセスがいたら、そのプロセスを起こす
- 4878-4881 : av-listの空きバッファを待っているプロセスがいたら、そのプロセスを起こす。bfreelistのB_WANTEDフラグはリセットする
- 4882-4883 : バッファにエラーフラグが立っていたらd_minorを-1にする。これはどこで使われる？エラーフラグはrkstrategy( ), rkintr( )(どちらもrkディスクデバイスドライバ)などで立てられるらしい
- 4884-4892 : B_WANTED, B_BUSY, B_ASYNCフラグをリセットし、av-listの最後尾にバッファを戻す。4885, 4892行目でPSの保管、復帰をしているのは何のため？
Lions本に書かれているデッドロックについては読書会のときにでもゆっくり追いたいと思います。
binit( )
binit( )はバッファ群(buf[])の初期化を行います。main( )(起動時に実行される関数)より呼び出されます。
- 5062-5063 : bfreelist(NODEV b-listのヘッダ、av-listのヘッダ)の初期設定。前後のリンクは全て自分を指すようにする。つまりこの時点ではNODEV b-listもav-listも空ということ
- 5064-5074 : buf[]の初期化。これが終わると全てのバッファはbfreelistのb-list(NODEV b-list), av-listに追加される
- 5066 : b_dev=-1はNODEVのバッファであることを示す
- 5067 : buffers[](バッファのデータを保持するコアのアドレス)との関連付け
- 5068-5071 : NODEV b-listの先頭に追加
- 5072 : B_BUSYフラグを立てる。次の行で実行されるbrelse( )でB_BUSYフラグはリセットされるのだが、この行は必要なのか？
- 5973 : brelse( )を呼び出し、av-listに追加する
- 5076-5083 : bdevsw[]で設定されているd_tab(各デバイスのb-listのヘッダ)の初期化を行う。b_forw, b_backは自分を指すようにする。つまりb-listは空
- 5084 : bdevswで設定されているデバイスの個数をnblkdevに保存しておく。1が設定されて欲しいのだが、8が入ってしまう(Lions本にも言及あり)。このロジックのバグというよりもbdevswを設定しているconf.cの記述ミスな気がする。ちなみにconf.cは自動生成される
bread( )
bread( )はブロックデバイスからデータを取得し、そのデータを格納したバッファを返します。既にデバイスと同期の取れたデータを持っているバッファが存在していたら、デバイスのアクセスを行わずそのバッファを返します。キャッシュの役割を果たしています。
- 4758 : getblk( )を呼んで、該当バッファを取得する
- 4759-4760 : そのバッファのB_DONEフラグが立っていたら(デバイスと同期の取れたデータを保持していたら)、そのバッファをreturnする
- 4761-4763 : データが古ければB_READフラグ(読み出し動作を表す。書き込み時はこのフラグを立てない)を立て、ワードカウントを-256(512bytesを表す)に設定し、rkstrategy( )を呼び出して読み出し動作を行う
- 4764 : iowait( )を呼び、デバイスの読み出し動作が終わるまで待つ
- 4765 : デバイスからデータを取り込んだバッファをreturnする
iowait( )
iowait( )はデバイスの動作完了を待ちます。バッファのB_DONEフラグが立つまで寝ます。4992行目でgeterror( )を呼んでいますが、エラーがなければgeterror( )内で何も処理を行いません。
breada( )
bread( )と同じようにデバイスからの読み込みを行います。それと同時に先読み動作の実行も開始させます。
- 4780 : incore( )を実行し、読もうとしているデバイスのブロックが割り当てられているバッファが存在するかチェック
- 4781 : 存在しなければgetblk( )でバッファを取得。(このバッファはav-listから取得したはず)
- 4782-4786 : そのバッファのB_DONEフラグが立っていなければデバイスの読み出し動作を実行を開始する。その完了は待たない
- 4788 : 先読みを行おうとしており、かつ、そのバッファがコア内に存在していなければ
- 4789 : getblk( )で該当バッファを取得する(このバッファはav-listから取得したはず)
- 4790-4791 : そのバッファのB_DONEフラグが立っていたらbrelse( )を呼んでバッファを開放する(なんのため？)
- 4792-4796 : B_DONEフラグが立っていなければB_READ, B_ASYNC(先読みを示す)フラグを立ててデバイスの読み出し動作を開始する。その完了は待たない
- 4798-4799 : 4781行目でバッファを取得していなければ(=既にコア内にバッファが存在していれば)、bread( )を呼んでデータの読み出しを行う
- 4800 : iowait( )を呼んで、4785行で実行したデバイス読み出し動作の完了を待つ
- 4801 : そのバッファをreturnする
bwrite( )
bwrite( )はブロックデバイスへのデータ書き込みを行います。
- 4817 : B_READ, B_DONE, B_ERROR, B_DELWRIフラグをリセットする
- 4818 : ワードカウントを-256(512bytes)にセット
- 4819 : rkstrategy( )を呼び出して書き込み動作を開始する
- 4820-4825 : B_ASYNCフラグが立っていなければ、デバイスの動作完了を待ち、その後brelse( )を呼んでバッファを解放する。B_ASYNCフラグが立っていたらデバイスの動作完了は待たない。かつ、B_DELWRIフラグが立っていなければgeterror( )を呼び、エラーチェックをする。エラーがあればu構造体にエラーがセットされる。4817行目でB_DELWRIフラグはリセットされるので、4823行目のif文は必ず成立する？(rkstrategy( )の中でセットされることはある？)
bawrite( )
bwrite( )と同様にブロックデバイスへの書き込みを行います。ただしデバイスの動作完了を待ちません。
バッファにB_ASYNCフラグをセットしてからbwrite( )を呼び出します。
bdwrite( )
bdwrite( )は遅延書き込み(ライトバック)を行います。プロセスが書き込み成否を知るのは難しいのではないかと思います。
- 4844-4845 : 書こうとしているデバイスが磁気テープでなければbawrite( )を呼び書き込みをすぐに行う。tmtab, httabって何？
- 4846-4848 : 磁気テープならばB_DELWRI, B_DONEフラグをセットしてからbrelse( )を呼び出しバッファを開放する。実際にデータを書き込むのはgetblk( )でav-listから取り除かれようとするときかbflush( )(update( )から呼ばれる)実行のとき
終わりに
バッファが理解できたので、ブロックデバイスへのアクセスの仕方が大体わかりました。
フラグの遷移の仕方がわかりづらかったので、後日状態遷移図を描いてみました。
その後は18章を読み解いていく予定です。ファイルシステムに入ります。ついにLions本も終盤に差し掛かった印象です。
