Use of index and Racy Git problem

インデックスは、Gitで最も重要なデータ構造の1つです。 これは、パスとそのオブジェクト名のリストを記録することによって仮想の作業ツリーの状態を表し、コミットされる次のツリーオブジェクトを書き出すための足場領域(staging area)として機能します。 状態は、作業ツリー内のファイルと必ずしも一致する必要はなく、多くの場合一致しないという意味で「仮想」です。

Gitは、インデックス内の仮想作業ツリーの状態と、作業ツリー内のファイルの違いを調べる必要がある場合があります。 最も明白なケースは、ユーザーが git diff(またはその低レベルの実装である git diff-files) または git-ls-files --modified で問い合わせした場合です。 さらにGitは、パッチ適用中や、ブランチの切り替え中や、マージ処理中に、作業ツリーのファイルがインデックスに記録されているものと異なるかどうかを内部的にチェックし、それらのローカルな変更を踏みにじらないようにしています。

作業ツリー内のファイルとインデックスエントリ間のこの比較を高速化するために、インデックスエントリは、最後に更新されたときに lstat(2) システムコールを介してファイルシステムから取得した情報を記録します。 それらが異なるかどうかを確認するとき、Gitは最初にファイルに対して lstat(2) 実行し、結果をこの情報と比較します(これは元々は ce_match_stat() 関数によって行われてましたが、現在のコードでは ce_match_stat_basic() 関数で行います)。 これらの「キャッシュされた統計情報」(cached stat information)フィールドのいくつかが一致しない場合、Gitは、ファイルの内容を見なくてもファイルが変更されたことを通知できます。

注意: lstat(2) 介して取得した struct stat のすべてのメンバーがこの比較に使用されるわけではありません。たとえば、 st_atime は明らかに役に立ちません。現在、Gitは、st_mode からのファイルタイプ(通常のファイルとシンボリックリンク)と実行可能ビット(通常のファイルのみ)、 st_mtime と st_ctime タイムスタンプ、 st_uid 、 st_gid 、 st_ino 、 st_size を比較します。 USE_STDEV コンパイル時オプションを使用すると、 st_dev も比較されますが、このメンバーはネットワークファイルシステム上で安定していないため、これはデフォルトでは有効になっていません。 USE_NSEC コンパイル時オプションを使用すると、st_mtim.tv_nsec と st_ctim.tv_nsec も比較されます。 Linuxでは、これはデフォルトでは有効になっていません。これは、コア内のタイムスタンプがディスク上のタイムスタンプよりも細かい粒度である可能性があり、iノードがiノードキャッシュから削除されたときに意味のない変更が発生するためです。 git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git のコミット 8ce13b0 ([PATCH] Sync in core time granularity with filesystems, 2005-01-04)を参照してください。このパッチはカーネル2.6.11以降に含まれていますが、正確に1nsまたは1sの粒度のファイルシステムの問題のみを修正します。他のファイルシステムは、現在のLinuxカーネル(たとえば CEPH, CIFS, NTFS, UDF)ではまだ壊れています。 https://lore.kernel.org/lkml/5577240D.7020309@gmail.com/ を参照してください。

キャッシュされた統計情報に基づく最適化には、わずかな問題が1つあります。 以下のシーケンスについて考えてみましょう:

最初の update-index `は、ファイル `foo の内容のオブジェクト名を計算し、 struct stat 情報とともに foo のインデックスエントリを更新します。 その後の変更が非常に高速に行われ、ファイルの st_mtime タイムスタンプが変更されない場合、このシーケンスの後、インデックスエントリが記録するキャッシュされた統計情報は、ファイル foo は今では異なっいても、ファイルシステムに表示される情報と完全に一致します。 このように、Gitは、実際には変更されていても、作業ツリー内のファイルが変更されていないと誤って考える可能性があります。 これは「racy Git」問題(Paskyによって発見されました)と呼ばれ、この問題が原因ではない可能性があるときにクリーンに見えるエントリは「racily clean」と呼ばれます。

この問題を回避するために、Gitは2つのことを行います:

インデックスファイル自体は、更新されたパスからすべての統計情報を収集した後に書き込まれるため、その st_mtime タイムスタンプは通常、インデックスに含まれるどのパスと同じか、それよりも新しいものです。 また、 git update-index foo に続く変更がどれほど速く終了しても、 foo の結果の st_mtime タイムスタンプはインデックスファイルより前の値を取得できません。 したがって、迅速にクリーンアップできるインデックスエントリは、インデックスファイル自体と同じタイムスタンプを持つエントリに制限されます。

インデックスエントリが作業ツリー内の対応するファイルと一致するかどうかを確認する呼び出し元は、引き続き ce_match_stat() を呼び出しますが、この変更により ce_match_stat() は ce_modified_check_fs() を使用して、 ce_match_stat_basic() でキャッシュされた統計情報を比較してから racily clean が実際に clean かどうかを判断するようになりました。

後者が解決する問題は、以下のシーケンスです:

後者がないと、インデックスファイルのタイムスタンプは新しい値を取得し、誤ってクリーンなエントリ foo は、前者のロジックで実行されたタイムスタンプ比較チェックによってキャッチされなくなります。 後者は、 foo のキャッシュされた統計情報が作業ツリー内のファイルと決して一致しないことを保証するため、後で ce_match_stat_basic() をチェックすると、インデックスエントリがファイルと一致しないことが報告され、Gitはより高価な ce_modified_check_fs() にフォールバックする必要がありません。

ce_match_stat() から ce_modified_check_fs() にフォールバックすることによる実行時のペナルティは、非常にクリーンなエントリが多数ある場合、非常に高くつく可能性があります。 この状況を人為的に作成する明白な方法は、大規模プロジェクトの作業ツリー内のすべてのファイルに同じタイムスタンプを付け、それらに対して git update-index を実行し、インデックスファイルに同じタイムスタンプを付けることです。

これにより、すべてのインデックスエントリが迅速にクリーンになります。 たとえば、Linuxプロジェクトでは、作業ツリーに20,000を超えるファイルがあります。 私のAthlon64X2 3800+で、上記の後に以下を実行します:

途中で git update-index を実行すると、racily cleanなエントリがチェックされ、実際にはクリーンであるため、すべてのパスのキャッシュされた st_mtime がそのまま残りました(したがって、このステップには最初の git diff-files とほぼ同じ時間がかかりました)。 その後、それらはもはやracily cleanではありませんが、本当にクリーンであるため、git diff-files の2回目の呼び出しはキャッシュされた統計情報を完全に利用しました。

上記の実行時のペナルティを回避するために、1.4.2以降のGitには、結果のインデックスファイルと同じタイムスタンプを持つ若いファイルが多数ある場合に、インデックスファイルがインデックス内の最も若いファイルよりも新しいタイムスタンプを取得することを確認するコードがありました。 それ以外の場合は、インデックスファイルの書き込みが完了する前に待機する必要があります。

実際には、インデックス内の多くのパスがすべて非常にクリーンであるという状況は非常にまれであると私は思いました。 多数のパスの最近のタイムスタンプを記録できる唯一のコードパスは以下のとおりです:

注意: git checkout を使用してブランチを切り替えると、現在のブランチと新しいブランチの間で同じである既存の作業ツリーファイルのキャッシュされた統計情報が保持されます。これらはすべて、結果のインデックスファイルよりも古く、racily cleanになることはありません。 実際にチェックアウトされたファイルだけが、racily cleanになることができます。

ただし、racy回避コスト(raciness avoidance cost)が非常に重要な大規模なプロジェクトでは、インデックス内のすべてのオブジェクト名の初期計算に1秒以上かかり、その後インデックスファイルが書き出されます。 したがって、インデックスファイルのタイムスタンプは、作業ツリーの最も若いファイルより1秒以上遅くなります。 これは、これらの場合、結果のインデックスに実際には racily clean なエントリがないことを意味します。

この議論に基づいて、現在のコードは、実際にはもう存在しない実行時のペナルティを回避するために「回避策」を使用していません。 これは、2006年8月15日にcommit0fc82cffで実行されました。