});前回「仮想ファイルシステムのありがたみを知ろう」では、仮想ファイルシステムがあるおかげで、“多種類のファイルシステムが共通インターフェイスを通して共存できる”ということを説明しました。仮想ファイルシステムには、さまざまなデータ構造があります。今回はその中から、ファイル名を管理する「dentry」というデータ構造について解説していきます。dentryとは?dentryには、主に以下のような3つの役割があります。ファイル名の管理ディレクトリ階層構造の管理キャッシュ管理これらの役割を担うために、dentryのデータ構造には表1に示すメンバが用意されています。前回説明しましたが、ここでも「list_head」構造体が出てきています。dentry構造体もリストだらけです。それでは、これらメンバの役割について少しつずつひもといていきましょう。ファイル名の管理はじめに、dentryのファイル名の管理を理解するために、以下のコマンドを実行してみましょう。......(4)file_A、file_Bのinode番号はともに10番file_Aとfile_Bには、同じ「inode番号」が付いています。ハードリンクを実行すると、1つのファイルに複数の名前を付けることができます(注1)。この状態を図示すると、以下のようになります(図1)。※注1:似たものとして“シンボリックリンク”がありますが、こちらは間接的にファイル名とファイルを結び付けるものです。dentryの「d_name」には、ファイル名(file_A、file_B)が入っていることが分かります。同じinode(注2)を共有するdentry同士は「d_alias」で結び付いており、その先にあるinodeの「i_dentry」というメンバからdentryへと戻っていく構造になっています。各dentryからは、「d_inode」というメンバで直接inodeをポイントすることで、inodeを直接参照できるようにしています。※注2:inodeについては、次回詳しく説明します。ディレクトリ階層構造dentryは、ディレクトリ階層構造も管理できます。以下、「testDir」配下に2つのファイル(article_1、article_2)が存在している状態のdentryのディレクトリ階層管理を見てみましょう(図2)。ディレクトリ階層構造まず、testDirという名前を持つdentryが頂上におり、その「d_subdirs」というメンバから、子ファイルであるarticle_2、article_1へとたどることができます。この際、子ファイル同士は「d_child」というメンバでアクセスすることになります。子ファイルのdentryの「d_parent」というメンバには親ディレクトリのdentryがポイントされており、直接親ディレクトリへアクセスできるようになっています。キャッシュ管理dentryには、“キャッシュ”という重要な役割があります。dentryがキャッシュ管理されているおかげで、非常に高速にファイルのアクセスが可能となります。Android仮想マシン上でファイルアクセスの高速化度合いを測ってみました。android-x86-1.6-r2.iso」からISOイメージをダウンロードしました。テスト内容Androidの全ファイルのリストアップを2回行い、1回目と2回目のファイルアクセス性能を測定しました。具体的な実行コマンドは以下のとおりです。dentryキャッシュ効果の確認方法dentryのキャッシュ数は、「/proc/slabinfo」のdentryの行をチェックします。具体的な実行コマンドは以下のとおりです。驚くべきことに、実行時間は200倍以上も向上しました。この要因がキャッシュ効果であることは、コマンド実行前のdentryキャッシュ数を見れば分かります。ご覧のとおり、dentry数は13倍以上も増加していますよね。キャッシュがあることで、CPUのアクセスはメモリ(dentry)だけで済み、時間のかかるUSBメモリへのアクセスはスキップされるのです。これこそがキャッシュ効果の威力です!dentryのキャッシュ管理ですが、図3のようにハッシュ管理されています。dentryのハッシュリストまず、図3のdentryの右下にある紫色の「name」と「hash」は、「qstr」構造体の実体です。ここにファイルの名前とハッシュ値が入ります。このハッシュ値は、ファイルの名前から計算で求められるもので、32ビットの変数です。ファイル名検索の処理の論理だけを考えるのであれば、“dentryごと”にハッシュ値は必要ありません。検索したいファイルの名前とdentryのファイルの名前を比較すればよいだけです。これだと大量にファイルが存在する場合、この文字列比較処理が性能ネックになり得ます。文字列比較のロジックは、1文字ずつチェックを掛けて、最大でファイル名長分だけチェックが入ります。ファイル総数が10万個で、平均ファイル名長が10文字である場合、最大で100万回(=10万×10回)のチェックが入ることになります。ファイル名の一致性のチェックがハッシュ値だけで済むのであれば、1dentry当たりのチェックは1回だけで終わるというわけです。すべてのdentryは、ハッシュテーブル内のどこかのエントリに登録されています。対象となるエントリは、dentryのd_parentのアドレス値とファイル名で求めたハッシュ値(図3中のHash)で求められます。対象となるエントリは、ハッシュテーブルの先頭からハッシュ値番目のエントリが使用されます。SNSfacebooktwitterITmediaはアイティメディア株式会社の登録商標です。