UNIX 6th code reading - buffer pool

unix 勉強

はじめに

前回のエントリでキャラクタデバイスハンドラの実装を確認しました。

今回はその中で使用されていたbuffer pool, putc( ), getc( )の詳細を確認していきます。

Lions本で言うと23章の内容です。

buffer pool

buffer poolの実態は、7908行目、8140行目に書かれている以下のFIFOリスト(キュー)です。

struct clist
{
    int c_cc;
    int c_cf;
    int c_cl;
};

struct cblock {
    struct cblock *c_next;
    char info[6];
};
struct cblock cfree[NCLIST];
struct cblock *cfreelist;

cblockのinfo[6]が文字(1byte data)を格納する場所であり、cblock1つあたり6文字保持できます。c_nextは別のcblockを指しています。

clistがFIFOリストのヘッダとなっています。clistはデバイスごとに定義されており(例えばLPの場合はlp11構造体(の先頭3つのint))、デバイスごとにFIFOリストを持っていると言えます。clistはデータの文字数を管理し、さらにFIFOリストの先頭と後尾を指すポインタを持っています。

cblockの配列がcfree[ ]として定義されていて、そのうち使用されていないものは、cfreelist(これもcblock構造体)をヘッダとしたフリーリストに保管されています。各デバイスのFIFOリストは、必要になったらフリーリストからcblockを取得し、必要なくなったらフリーリストに返します。1つのcfree[ ]を全デバイスで共有しています。

絵で描くとこんな感じです。この例では'hogefugahomumado'という16文字がFIFOリストに保持されている場合を想定しています。

getc( )はFIFOリストの先頭から1文字取り出します。

下図は、上図から先頭の'h'を取り出したケースを表してます。

putc( )はFIFOリストの最後尾に1文字(1byteのデータ)を追加します。

下図は、上図から後尾に'k'を追加したケースを表しています。フリーリストからcblockを取り出しています。


cinit( )

cinit( )(8234行目)はbuffer poolの初期化を行います。起動時にmain( )から1度だけ呼び出されます。

cinit( )はcfree[ ]のエントリをフリーリストに全て追加します。

また、システム中のキャラクタデバイスを数え、その数を保存しておきます。

getc( )

getc( )(930行目)はFIFOリストから先頭の1文字を取り出します。1文字取り出した結果、空になったcblockがあれば、それををフリーリストに返します。

アセンブリコードで書かれています。

putc( )

putc( )(967行目)はFIFOリストの後尾に1文字追加します。最後尾のcblockのinfo[ ]が満杯だったら、フリーリストからcblockを取ってきてFIFOに追加します。

アセンブリコードで書かれています。

コードメモ

cinit( )
  • 8239-8243 : cfree[ ]をcfreelistがヘッダのフリーリストに追加していく。cfreeを逆から辿るフリーリストが形成される。cfree[ ]のエントリのcblockは8bytesのデータなので、8の倍数になるようにfor分の初回のアドレスを調整している(なぜこれが必要？pragmaとかそういう話？)
  • 8244-8247 : cdevswに登録されているopenハンドラの数を数えることでキャラクタデバイス(ドライバ)の個数を数える。その個数をnchrdevに保存しておく
getc( )
  • arguments
    • clist(FIFOリストのヘッダ)のポインタ
  • 931 : 引数をr1にコピー
  • 932 : PS(Processor Status word)をスタックに退避
  • 933 : r2をスタックに退避
  • 934-935 : プロセッサ優先度を5に変更
  • 936 : FIFOの先頭ポインタをr2にコピー
  • 937 : 先頭ポインタがNULLかどうか(FIFOリストが空か)チェック。NULLならば961行へ
  • 938 : 先頭ポインタが指す1文字をr0にコピー。先頭ポインタを1文字分ずらす
  • 939 : 拡張された負符号を取り除く
  • 940 : clistの先頭ポインタを更新
  • 941 : clistの文字カウンタをデクリメント
  • 942 : 文字カウンタが0でなければ947行へ
  • 943-944 : 文字カウンタが0、つまりFIFOリストは空。clistの先頭ポインタと後尾ポインタを0クリア(NULL)
  • 945 : 952行目へ
  • 947 : FIFOリストが空でないならば。先頭ポインタの下位3bit(つまり8で割った余り)をr2に格納
  • 948 : 8で割った余りが0でないならば956行目へ
  • 949 : 8で割った余りが0ならば。先頭ポインタは次のcblockの文字列を指しているので、cblockのc_nextの値を先頭ポインタに格納
  • 950 : info[0]はcblock中の2word目なのでポインタを調整
  • 952-953 : 空になったcblockをフリーリストに返すために、r2が空になったcblock(の先頭)を指すように調整
  • 954-955 : フリーリストの先頭に、空になったcblockを追加
  • 957-958 : 退避しておいたr2とPSを復帰
  • 959 : return. 938行目でセットしたr0の値が呼び出し元への返り値となる
  • 961-965 : FIFOが空だった場合の処理。後尾ポインタを(念のため？)クリアし、返り値となるr0には-1をセットし、退避しておいたr2とSPを復帰させてからreturn
putc( )
  • arguments
    • 1文字(1byte data)
    • clist(FIFOリストのヘッダ)のポインタ
  • 968-969 : 引数の1文字をr0に、clistのポインタをr1にコピー
  • 970-972 : PS, r2, r3をスタックへ退避
  • 973-974 : プロセッサ優先度を5に
  • 975 : clistの後尾ポインタをr2へコピー
  • 976 : 後尾ポインタがNULLでなかったら(FIFOリストが空でなかったら)984行目へ
  • 977 : FIFOリストが空であった場合の処理。フリーリストの先頭cblockのポインタをr2へ
  • 978 : フリーリストが空だったら1001行目へ
  • 979 : フリーリストから先頭cblockを取り除く
  • 980 : 取り除いたcblockのc_nextが指す先をNULLに
  • 981 : FIFOリストにcblockを追加
  • 982 : 993行目へ
  • 984 : 先頭ポインタを8で割った余りをr2に格納
  • 985 : 8で割った余りが0でなかったら(先頭ポインタがcblockの境を指していたら)992行目へ
  • 986-987 : 8で割った余りが0ならば、フリーリストからcblockを取ってくる。フリーリストが空ならば1001行目へ
  • 988 : フリーリストから先頭のcblockを取り除く
  • 989 : FIFOの最後尾に、フリーリストから取ってきたcblockを追加
  • 990-991 : 最後尾のcblock(フリーリストから取ってきたもの)のc_nextをNULLに
  • 993 : 引数で渡された1byte dataをFIFOリスト最後尾に追加
  • 994 : clistの後尾ポインタを更新
  • 995 : clistの文字数カウンタをインクリメント
  • 996-999 : r0をクリアし(つまり正常終了の場合は呼び出し元に0が返る)、退避していたSP, r2, r3を復帰させる
  • 1000 : return
  • 1002-1006 : r0にpc(失敗時は呼び出し元に0でない値を返す。なぜPCの値？？)をセットし、退避していたSP, r2, r3を復帰し、return

終わりに

buffer poolの内容がわかったので、キャラクタデバイスの「1文字処理する」という特性がより理解できたと思います。

次回は対話型端末について見ていく予定です。