UNIX 6th code reading - unix/alloc.c

unix 勉強

はじめに

unix/alloc.cを見ていきます。

alloc.cではブロックデバイス中のinode領域やデータ領域の割り当て・解放を行っています。

ブロックデバイスのinode領域の割り当て＆解放

各ブロックデバイスに対応したsuperblock(filsys構造体(5561行目))がコア中に存在しており、その中のs_inode[ ](要素数100はハードコーディング。param.hなどで編集できる値ではない), s_ninodeでブロックデバイス中の未使用inode numberを管理しています。

s_inode[ ]にはブロックデバイス中の未使用inode numberが格納されています。(inode構造体が格納されているわけではない)

s_ninodeはs_inode[ ]中の未使用inode numberの数を表します。

s_inode[ ]は未使用inode numberのstackでs_ninodeはそのstackのstack pointerと考えると理解しやすいでしょう。


ialloc( )

ialloc( )(7067行目)はブロックデバイス中のinode領域の割り当て関数です。

s_ninodeが指すs_inode[ ]の要素(ブロックデバイス中で未使用のinode number)を取得し、そのinode numberを使ってinode[ ]からエントリを取得します。

s_inode[ ]が空になるとブロックデバイスのinode領域の先頭(ブロックNo.2)から探索し、未使用inode numberをs_inode[ ]に格納します。

疑問：毎回先頭から探索すると、先頭ブロックの領域ばかりが使われて、後方のブロックがあまり使われないのでは……？

ialloc( )の全体像はこんな感じです。

s_inode[ ]が空になったときに初めてブロックデバイスとやり取りをします。プロセスからブロックデバイスのinode領域の割り当て要求が来たときに、毎回ブロックデバイスにアクセスをする必要がない分性能が上がります。

ifree( )

ifree( )(7134行目)はinode領域の解放です。

解放されたinode numberがs_inode[ ]に格納されます。s_inode[ ]が満杯だったとき、そのinode numberは捨てられます。捨てられたinode numberは、ialloc( )のブロックデバイスからs_inode[ ]に格納する時に拾われます。


ブロックデバイスのデータ領域の割り当て＆解放

superblockのs_free[ ](要素数100はハードコーディング。param.hなどで編集できる値ではない), s_nfreeでブロックデバイス中の未使用データ領域のblock numberを管理しています。

s_free[ ]はstackでs_nfreeがstack pointerと見ることが出来ます。

大きなレベルではinode割り当てと同じロジックと見ることができます。細かい部分で異なるので、それらを中心に解説します。

alloc( )

alloc( )(6956行目)は、ブロックデバイス中の未使用データ領域を割り当てる関数です。

s_nfreeが指すs_free[ ]の要素(未使用block number)を取得し、getblk( )を呼んでブロックポインタを返します。

s_free[ ]が空になったらブロックデバイスから未使用データ領域のblock numberを取得し、s_free[ ]に格納します。

この格納処理がinodeの割り当てと大きく異なります。ブロックデバイス中で(基本的に？)99個の未使用block number listでまとめられていて、そのリストの先頭にはlistの要素数(基本的には100のはず)と次のblock number listを管理しているblock numberが収められています。

  • block number list
    • 0 : listの要素数(基本的に100のはず)
    • 1 : 次のリストを管理しているblock number
    • 2 - 100 : 未使用block number(基本的に99個のはず)


ブロックデバイスのデータ領域の中でも、データを格納している領域と、block numberのリストを管理している領域の二つがあるようです。

絵で描くとこんな感じです。

疑問：誰がblock number listの初期設定を行う？フォーマットを行うコマンドが存在するとか？

free( )

free( )(7000行目)はデータ領域の解放を行う関数です。

解放されたblock numberをs_free[ ]に格納します。

s_free[ ]が満杯だったときは、s_free[ ]の内容をブロックデバイスに書き戻します。現在のs_nfree(基本的には100のはず)を先頭にし、その後ろにs_free[ ]の要素(100個)が連なるリストを、今解放しようとしているブロックに書き込みます。そしてs_nfreeを0にし、s_free[ 0 ]に解放しようとしているブロックのblock numberを書き込みます。

これにより、alloc( )のところで描いた絵のようなリストが出来上がります。

root devの設定

iinit( )(6922行目)は起動時にmain( )から呼ばれます。(1615行目)

ブロックデバイスからsuperblockを読み出して、mount[ ]配列の先頭に格納します。

superblockはブロックデバイスのblock number 1に格納されているので、それを読み出します。中身をworkspaceにコピーしたら、読み出しに使用したブロックポインタは解放します。workspaceはgetblk(NODEV)により作成します。

mount[ ]配列の先頭のmount構造体のm_bufpがそのworkspaceを指すようにし、m_dev(デバイス種)にはrootdevをセットします。そして(workspaceの)superblockのロック関係を全て解除し、リードオンリーフラグもリセットします。

superblockのs_time[ ]をカーネル内で時刻を管理するtime[ ]にコピーします。

疑問：システムの電源を切っている時も、root deviceは時を刻み続け、s_time[ ]に反映される？。そうでないならば、システムの電源をオン／オフするたびに時計が狂っていくような。

絵で描くとこんな感じです。


その他の関数

getfs( )(7167行目)は引数devに対応したsuperblockをmount[ ]から探し出し、それを返します。

update( )(7201行目)は、ブロックデバイスにまだ反映されていない以下のデータをフラッシュします。

  • superblock(mount[ ])
  • inode(inode[ ])
  • block(block pointer)


update( )はsync( )から呼ばれ、sync( )は30秒毎に呼び出されます。

badblock( )(7040行目)は、block numberがブロックデバイス中のinode領域かデータ領域を指しているかをチェックする

コードメモ

ialloc( )
  • 7072 : getfs( )を使って引数devに対応したfilsys(superblock)を取得する
  • 7073-7074 : filsysのロックが開くまで寝る
  • 7076 : filsysが持つinodeフリーリストに未割当てinode numberがまだ残っていたら
    • 7077 : フリーリストの(スタックの)先頭にあるinode numberを取得
    • 7078-7080 : 取得したinode numberを用い、iget( )を使ってinode[ ]のエントリへのポインタを得る。失敗したらNULLをreturn
    • 7081 : 取得したinodeポインタのi_mode==0ならば(inodeを解放するときにi_modeを0にしている。i_modeが0でないというのは、そのinodeを使用している、もしくは、inodeの解放がうまくいっていないということ)
      • 7082-7083 : inodeポインタのi_modeからi_addrまでを0クリア
      • 7084 : filsysのs_modを1にして、filsysの更新フラグを立てる
      • 7085 : inodeポインタをreturn
    • 7091 : i_modeが0以外だったら、取得したinodeを解放して、loopに戻ってもう一度inodeの取得を試みる
  • 7094 : フリーリストに未割当inode numberが残っていなければ、filsysのロックを取得
  • 7096 : ブロックデバイスのinode領域(#2〜)のブロックを辿る
    • 7099 : ブロック中の1inodeずつたどり
      • 7100 : inoをインクリメント
      • 7101-7102 : i_modeが0でないなら使用中のinode numberなのでcontinue
      • 7103-7106 : コア中のinode[ ]に該当するエントリがあればcontに飛ぶ(実質continueと同じだと思う)。通常、i_modeが0ならばinode[ ]中にも存在しないと思うのだが……どうやらブロックデバイス中でもコア中でもそのinodeが未割当であるのを確認して、初めて未割当てinodeだとみなしている様子
      • 7107 : フリーリストにinode numberを格納
      • 7108-7109 : フリーリストが満杯になったらbreakでループを抜ける
    • 7112 : 7097行目で取得した、inode領域読み出し用のブロックポインタを解放
    • 7113-7114 : フリーリストが満杯になったらbreakでループを抜け、inode number格納処理を終了する
  • 7116 : filsysのロックを解放する
  • 7117 : filsysのロックが開くのを待っているプロセスを起こす
  • 7118 : フリーリストに未割当てinode numberを格納できたらloopに戻って、inode割当て処理に戻る
  • 7119-7122 : フリーリストに未割当てinode numberが格納できなかったら、それはブロックデバイスのinode領域が全て使用中であることを表すのでエラー処理
ifree( )
  • 7138 : getfs( )を使って、引数で渡されたdevに対応したfilsysを取得する
  • 7139-7140 : filsysにロックがかかっていたらreturn(フリーリストにinode numberが戻されないが、そのinode numberはialloc( )のフリーリストへの拡充処理のタイミングで回収されるので、問題はない)
  • 7141-7142 : フリーリストが満杯なら何もせずreturn(フリーリストにinode numberが戻されないが、以下同上)
  • 7143 : inode numberをフリーリストに戻す
  • 7144 : filsysのs_modを1にして、filsysの更新フラグを立てる
alloc( )
  • 6961 : getfs( )を使って、引数で渡されたdevに対応したfilsysを取得する
  • 6962-6963 : filsysにロックがかかっていたら、開くまで寝る
  • 6964 : 適切なblock numberが取得できるまでループ。badblock( )は、取得したblock numberがブロックデバイス中のinode領域でもデータ領域でもないところを指していたら1が返ってくる。この状態はどういうときに起こりうる？Lions本では不正なファイルデバイスがマウントされている場合と書いてあるが
    • 6965-6966 : フリーリストが空ならばnospaceへ飛ぶ
    • 6967-6969 : フリーリストからblock numberを取得。取得したblock numberが0ならばnospaceへ飛ぶ。(0は何を意味する？)
  • 6971 : 妥当なblock numberを取得できたが、フリーリストが空になった場合。フリーリストの拡充処理を行う
    • 6972 : filsysをロック
    • 6973 : 取得したblock numberはフリーリストの先頭のblock number。これは、次のフリーリストが格納されているblock numberを指すので、bread( )で読み出す
    • 6975 : 読み出したブロックの先頭には、フリーリストに格納されているblock numberが格納されているので、s_nfreeに格納する
    • 6976 : bcopy( )を使ってフリーリストをs_freeに一括コピー
    • 6977 : ブロックポインタ(バッファポインタ)を解放
    • 6978 : filsysのロックを解放
    • 6979 : filsysのロックが空くのを待っているプロセスを起こす
  • 6981 : 取得したblock numberを用い、getblk( )を呼んでブロックポインタ(バッファポインタ)を取得する
  • 6982 : 取得したバッファを0クリア
  • 6983 : filsysの更新フラグを立てる
  • 6984 : バッファポインタをreturn
  • 6986-6990 : フリーリストに空きがなければエラー処理
free( )
  • 7004 : getfs( )を使って、引数で渡されたdevに対応したfilsysを取得する
  • 7005 : filsysの更新フラグを立てる
  • 7006-7007 : filsysのロックが開くまで寝る
  • 7008-7009 : 引数で渡されたblock numberがinode領域でもデータ領域でもなければreturn
  • 7010-7013 : s_nfreeが0以下ならばn_free=1, s_free[0]=0をセット
  • 7014 : フリーリストが満杯ならば。フリーリストをブロックデバイスに書き出し、フリーリストをリセットする
    • 7015 : filsysをロックする
    • 7016 : 引数で渡されたblock numberのバッファを取得する
    • 7018 : バッファの先頭にn_freeを格納する
    • 7019 : フリーリストをバッファに丸ごとコピー
    • 7020 : n_freeを0に(フリーリストを空に)
    • 7021 : フリーリストを格納したバッファをブロックデバイスに書き込む
    • 7022 : filsysのロックを解放する
    • 7023 : filsysのロックが開くのを待っているプロセスを起こす
  • 7025 : フリーリストにblock numberを戻す(7014-の処理をしていた場合、フリーリストの先頭にblock number)
  • 7026 : filsysの更新フラグを立てる
iinit( )
  • 6926 : デバイスのオープン処理。RKの場合は何もしない
  • 6927 : ブロック#1のsuperblockを読み出す
  • 6928 : work用バッファを取得
  • 6929-6930 : エラーがあればpanic( )
  • 6931 : superblockの内容をwork用バッファにコピー
  • 6932 : superblock読み出しにしようしたバッファを解放
  • 6933-6934 : mount[ 0 ](rootdev用)のm_bufpからwork用バッファを指すようにし、m_devにはrootdevをセット
  • 6935-6938 : superblock(filsys)のロック関係とリードオンリーをクリア
  • 6939-6940 : カーネルで保持している、時刻を表現するtime[ ]にsuperblockのs_time[ ]を格納する
badblock( )
  • 7047-7051 : 引数で与えられたblock numberがブロックデバイス中のinode領域かデータ領域を指していれば0を返す。そうでなければ1を返す
getfs( )
  • 7172 : mount[ ]を探索。引数で与えられたdevに該当するものを探す
    • 7173 : m_bufpがNULLでなくm_devが引数のdevと等しければ
      • 7174 : これでfilsys(superblock)情報にアクセスできる
      • 7175-7181 : s_nfree, n_ninodeが100を超えていたら不正なので0に戻す
      • 7182 : superblock(filsys)へのポインタを返す
  • 7184 : devに該当するmount[ ]のエントリがなかったのでpanic( )。マウントが正しく行われていないことを表す？
update( )
  • 7207-7208 : 同期用のupdlockにロックがかかっていたらreturn. 何もしない
  • 7209 : updlockにロックをかける
  • 7210 : mount[ ]を探索
    • 7211-7215 : 更新フラグが立っていなかったり、ロックがかかっていたり、リードオンリーならばそのエントリには何もしない。ロックがかかっていた場合、フラッシュされないが問題はないのか？
    • 7216 : superblockであるblock#1のバッファポインタを取得
    • 7217 : 更新フラグをリセット
    • 7218-7219 : superblockのs_timeを更新
    • 7220 : superblockの内容をバッファにコピー
    • 7221 : バッファをブロックデバイスに書き込む
  • 7223 : inode[ ]を探索。inodeにロックがかかっていなければ、ロックをかけてからiupdate( )を呼び出しinodeのフラッシュ。その後解放。ロックがかかっていた場合、フラッシュされないが問題はないのか？
  • 7229 : updlockの解放
  • 7230 : bflush( )を呼んで、ブロックバッファのフラッシュ。引数がNODEVなので、全てのデバイスのブロックバッファがフラッシュされる

終わりに

ブロックデバイスの領域割り当ての解説を行いました。次回はカーネル内でのinode割り当てや解放を解説する予定です。