Personal tools
You are here: Home ブログ 学習経過 ファイルシステム(その6)
« December 2010 »
Su Mo Tu We Th Fr Sa
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
Recent entries
sysfs tips 02 ohyama 2010-09-09
sysfs tips ohyama 2010-09-02
Haskell で周波数スペクトルを得る ohyama 2010-07-29
Haskell で線形識別関数の学習を行う ohyama 2010-07-19
Haskell で逆行列を求める ohyama 2010-07-16
Recent comments
Re:vim に lisp 機能をつける t.mimori 2010-12-16
Re:Haskell で周波数スペクトルを得る H.OHYAMA 2010-08-01
Re:lkml でお勉強 (その1-1) Hiroyasu OHYAMA 2009-08-21
Re:lkml でお勉強 (その1-1) kosaki 2009-08-20
Re:vim に lisp 機能をつける ohyama 2008-05-08
Categories
学習経過
GNU/Linux
 
Document Actions

ファイルシステム(その6)

    前回は、ファイル(inode)がどこに作成されるのかに焦点を当て、ファイルの作成処理の実装について見てきた。
    ファイルオープン処理はまだまだ奥が深く、前回話した部分は、一連の処理の一部分に過ぎないのだが、霧散した目的で実装を調べても、得られた内容は冗長で、再度思い起こせる"理解"と過去に得た理解から、別の視点で得られる理解("発見")が少ない事が経験上わかっているので、それについては、別の目的でこれを調べる近い未来の自分に任せる事にする(つまるところ、自分が"調べる"動機は目的ありきという事になる)。

    今回は、書き込むデータがファイル上のどこに配置されるのかという事について調べてみる。
    なので、write システムコールのサービスルーチン sys_write() から処理を追ってみる。
    前回同様、話の見通しを良くする為、自分が使っているカーネルバージョン(2.6.20)における sys_write() から呼び出される関数郡を以下に示す。尚、記載されている関数は、対象行の ">" が一つ少ない直上の関数から呼ばれる。又、"()"は自分用のメモである。

sys_write
> vfs_write
>> do_sync_write (f_op->write メソッド)
>>> generic_file_aio_write
>>>> __generic_file_aio_write_nolock
>>>>> generic_file_direct_write (O_DIRECT フラグが設定されたファイルに対する書き込み)
>>>>> generic_file_buffered_write (書き込みの遅延を行う)
>>>>>> ext2_prepare_write  (a_ops->prepare_write メソッド)
>>>>>>> block_prepare_write
>>>>>>>> __block_prpare_write
>>>>>>>>> ext2_get_block (get_block コールバック関数)
>>>>>>>>>> ext2_get_branch
>>>>>>>>>> ext2_find_goal
>>>>>>>>>>> ext2_find_near
>>>>>>>>>> ext2_alloc_branch
>>>>>>>>>>> ext2_alloc_block
>>>>>>>>>>>> ext2_new_block

    sys_write() 関数から呼び出される fget_light() 関数で、引数で渡したファイルディスクリプタ fd から、ファイルオブジェクトを取得する。そして、file_pos_read() 関数から、引数で渡したファイルオブジェクトの f_pos メンバを取得し、ファイルオフセットを取得し、vfs_write() を呼び出す。
    vfs_write() では、書き込む範囲のチェックと、権限のチェックを行った後、ファイルオブジェクトの f_op メンバが参照するファイル操作関数郡の write メソッドを呼び出す。
    ところで、open_namei() から呼ばれる __path_lookup_intent_open() 関数が、get_empty_filp() 関数を呼び出し、空のファイルオブジェクトを生成するという話は、前回したが。f_op の初期化はいつどのように行われるのだろうか。

    ファイルを新たに open した時、作成されたファイルオブジェクトの操作メソッド郡 f_op は、VFS inode の i_fop で初期化される(__dentry_open() 関数)。
    ファイル作成時において、親ディレクトリの inode を引数にして vfs_create() 関数を呼び出し、親ディレクトリの inode 操作関数の create メソッドを実行し、先に作成したファイルの dentry に対応する inode を生成、初期する。
    ファイルシステムのルート(マウントポイント)では、マウント時に作成されたマウントポイントの inode が特別な振舞(マウントポイントとは違う i_pos メンバを持つ事)をし、以降のファイルに対しては、親の d エントリオブジェクトが参照する inode から情報を引っ張ってくる。
    これにより、linux の低レイヤファイルシステム設計者は、inode の操作関数及び、inode オブジェクトの file_operations 型の i_pos メンバを定義すれば、ファイルの生成、読み込み、書き込み処理について、VFS がそれらを呼び出し、ファイルシステム依存の処理を行ってくれる(ちょうど、キャラクタデバイスのデバイスファイル操作関数を定義し、cdev_add() 関数でそれらを登録するように)。実に秀逸なシステムである。

    さて、ファイルオブジェクトの f_op メンバは、fs/ext2/file.c で定義されている、ext2_file_operations で初期される。そして、vfs_write() で実行した write メソッドは、do_sync_write() 関数を呼び出す。
    do_sync_write() 関数では、iovec 型オブジェクトと kiocb 型オブジェクトを生成し、f_op->aio_write() メソッドを呼び出す。
    両オブジェクトが存在する必然性はよくわからないが、これまでの情報を引き継ぐ。iovec オブジェクトは、ユーザーバッファ(ユーザーから渡されたバッファ領域)のアドレスと長さを初期化設定。kiocb オブジェクトは、init_sync_kiocb() 関数を呼び出し、ki_filp メンバに引数で渡したファイルオブジェクト、ki_obj.tsk メンバにカレントプロセスを初期化設定している。
    aio_write() メソッドは、ext2 ファイルシステムでは generic_file_aio_write() 関数を呼び出す。

    generic_file_aio_write() 関数は、ファイルオブジェクトから、アドレス空間オブジェクト、inode を取得し、__generic_file_aio_write_nolock() 関数を呼び出す。ここでは、時刻の更新などの処理をおこなっている。
    ここでのミソは、O_DIRECT フラグ付きでオープンされているファイルに対する処理とそうでない場合の処理の実行である。O_DIRECT フラグについては、オンラインマニュアルを参照されたし。
    今回知りたいのは、バッファヘッドを生成した際に、実ブロック番号をどのように決定するかについてなので、generic_file_direct_write() 関数の実装の調査については、先送りする。
    さて、通常ファイルに対する書き込みが行われると、ページキャッシュに対してデータ書き込みを行い、ディスクに対する書き込みは遅延される事は以前に述べた(と思う)。ここで呼ばれる generic_file_buffered_write() 関数は、現在のファイルオフセットから、ページサイズだけファイルオフセットを右シフトして得られる、ファイルオフセットが存在するページキャッシュ番号、ページキャッシュ内でのファイル位置、そして、ページキャッシュ内オフセットからページキャッシュの終端までの長さを取得し、__grab_cache_page() 関数を呼び出し、キャッシュページを取得する(指定したキャッシュページ番号に対応するキャッシュページが存在しない時、page_cache_alloc() 関数を呼び出し、新たにキャッシュページを呼び出し、キャッシュに挿入する)。
    そして、__grab_cache_page() によって得られたページを引数に、アドレス空間オブジェクトの操作関数郡 a_ops の prepare_write() メソッドを呼び出す。a_ops メンバは、ファイル作成時に呼び出された ext2_create() 関数で、&ext2_aops で初期化されている(cf. ファイルシステム(その5))。
    a_ops->prepare_write() メソッドは、ext2_prepare_wirte() 関数を実行する。ここでは、ページキャッシュのブロックバッファ取得失敗時に呼び出される低レイヤファイルシステム依存のコールバック関数 ext2_get_block のアドレスを引数に指定し、block_prepare_write() メソッドを呼び出す。
    block_prepare_write() 関数は、__block_prepare_write() 関数のラッパールーチンであり、ここではまず、キャッシュページがブロックバッファを持っていない時、create_empty_buffers() 関数を呼び出し、バッファヘッドを生成、b_blocknr = -1、b_state フラグに 0 を初期化設定し、キャッシュページに登録し、__block_prepare_wirte() 関数に処理を戻す。
    そして、キャッシュページのバッファがディスクデータをマッピングしていない場合、ext2_prepare_write() で設定したコールバック関数 get_block() 関数を実行し、ext2_get_block() 関数を呼び出す。

 ext2_get_block() 関数から呼ばれる、ext2_block_to_path() 関数で、対象のファイルオフセットが存在するキャッシュ内におけるブロック番号から、inode のデータテーブルの階層がわかる。次に、ext2_block_to_path() で設定した offsets 変数を引数に ext2_get_branch() 関数を呼び出し、offsets 変数に格納された論理ブロック番号(page の index メンバで指定されたファイル内オフセットを含むブロック番号)に対応する実ブロック番号(論理ブロック番号に対応するディスク上のブロック番号)を inode データテーブルから取得する。
    ここまでが前回説明した処理であるが。これに失敗した時、つまり、要求した論理ブロック番号に対応する実ブロック番号が未割り当ての場合、ext2_find_goal() 関数を呼び出し、実ブロックの取得を行う。
    ext2_inode_info 型の i_next_alloc_block メンバは、対象のファイルにおいて、最近割り当てた論理ブロック番号を表す(変数名の命名ミスらしい)。又、i_next_alloc_goal メンバは、i_next_alloc_block メンバと対になるデータ。対象ファイルにおいて、最近割り当てた実ブロック番号を表す。
    ext2_find_goal() 関数において、最後に割り当てた論理ブロック番号が現在の論理ブロック番号と隣接している場合、対象ファイルのディスク inode の i_next_alloc_block メンバと i_next_alloc_goal メンバをそれぞれインクリメントし、i_next_alloc_goal メンバの値を割り当てる実ブロックの候補に設定する。これに失敗する時、つまり、i_next_alloc_goal が設定されていない (はじめて実ブロックを割り当てる) 場合、ext2_find_near() 関数を呼び出し、謎な方程式によって、実ブロック候補を決定する。
    この段階で決定されたブロック番号の候補(goal)は、ext2_alloc_branch() から呼ばれる ext2_alloc_block() 関数に渡され、先行割り当てされたブロック番号かどうかのチェックが行われる。ext2 ファイルシステムはブロックの先行割り当てを行っている。つまり、ディスクからデータブロックを取得する際、最大で8個(デフォルトでは、スーパーブロックの s_prealloc_blocks で指定される値であるが、対象ブロックグループの空きブロックの状況により変化する)までの連続したデータブロックを確保し、空きデータブロックを確保する。i_prealloc_cout メンバには、先行割り当てを行ったデータブロックのうち、未使用のデータブロックの数が格納されており、i_prealloc_block メンバには、先行割り当てを行ったデータブロックのうち、未使用のデータブロック番号番号が格納されている。ext2_find_goal() によって、goal にディスク inode の i_next_alloc_goal メンバが設定された場合、これに該当する。
    これに失敗した時(以前に取得したデータブロックに連続したブロックの取得に失敗した時)、先行割り当ての情報をクリアし、新たにディスクから先行割り当てを行う為に、ext2_new_block() 関数を呼び出す。
    ext2_new_block() 関数では、現在の goal の値(ext2_find_near() で決めた適当な値)が属するブロックグループに空きブロックが存在する場合、対象ブロックグループのビットマップを取得し、grab_block() 関数を呼び出して、ブロックグループ内における空きブロック検索を行う。
    その前に、(偶然に) goal のブロックグループオフセット(以下、group_goal)が指すブロック番号が空きブロックかもしれないので、ext2_test_bit() を呼び出し、現在の group_goal の値が空いているかを確認。空いていない場合、ブロックグループ内の適当な位置から、ビットマップを走査し、空きブロックを見付ける。これに失敗すると、ブロックグループの先頭からビットマップを走査する。
    grab_block() を呼び出す前に実行した、ext2_new_block() の group_reserve_block() 関数の判定によって対象ブロックグループに空きブロックが存在するする事を確認したので、grab_block() を呼び出した時点で、空きブロックの取得に失敗することはない(SMP システムによる例外もあるが)。
    group_reserve_block() 関数の判定に失敗した時(つまり、同一ファイルにおいて、以前に利用したブロックグループに空きブロックが存在しない時)、全てのブロックグループに対して、先の処理(group_reserve_block() によって空きブロックが存在するブロックグループを検出し、grab_block() によってブロックグループ内の空きブロック番号を走査する処理)を繰り返し、空きブロックを見付ける。

    以上が、ブロックグループ取得の ext2 ファイルシステムの処理である。ミソとなる部分は、ext2_find_near() による goal の設定と、ブロックの先行割り当てと、grab_block() におけるブロック走査アルゴリズムなのだろう。

Category(s)
学習経過
The URL to Trackback this entry is:
http://dev.ariel-networks.com/Members/ohyama/30d530a130a430eb30b730b930c630e0-305d306e6/tbping
Add comment

You can add a comment by filling out the form below. Plain text formatting.

(Required)
(Required)
(Required)
(Required)
(Required)
This helps us prevent automated spamming.
Captcha Image


Copyright(C) 2001 - 2006 Ariel Networks, Inc. All rights reserved.