Background
インデックスは、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/ を参照してください。
Racy Git
キャッシュされた統計情報に基づく最適化には、わずかな問題が1つあります。 以下のシーケンスについて考えてみましょう:
: 'foo' を編集
$ git update-index 'foo'
: 再び 'foo' を編集。サイズを変更せずに 'foo' の内容を編集します
最初の update-index `は、ファイル `foo
の内容のオブジェクト名を計算し、 struct stat
情報とともに foo
のインデックスエントリを更新します。 その後の変更が非常に高速に行われ、ファイルの st_mtime
タイムスタンプが変更されない場合、このシーケンスの後、インデックスエントリが記録するキャッシュされた統計情報は、ファイル foo
は今では異なっいても、ファイルシステムに表示される情報と完全に一致します。 このように、Gitは、実際には変更されていても、作業ツリー内のファイルが変更されていないと誤って考える可能性があります。 これは「racy Git」問題(Paskyによって発見されました)と呼ばれ、この問題が原因ではない可能性があるときにクリーンに見えるエントリは「racily clean」と呼ばれます。
この問題を回避するために、Gitは2つのことを行います:
-
キャッシュされた統計情報によりファイルが変更されていないと言うには、
st_mtime
がインデックスファイル自体のタイムスタンプと同じ(またはそれより新しい)場合(これは、上記の例ではgit update-index foo
の実行を終了した時間です)では、コンテンツをインデックスエントリに登録されているオブジェクトと比較して、それらが一致することを確認します。 -
非常にクリーンなエントリを含むインデックスファイルが更新されると、キャッシュされた
st_size
情報は、新しいバージョンのインデックスファイルを書き込む前にゼロに切り捨てられます。
インデックスファイル自体は、更新されたパスからすべての統計情報を収集した後に書き込まれるため、その 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 かどうかを判断するようになりました。
後者が解決する問題は、以下のシーケンスです:
$ git update-index 'foo'
: サイズを変更せずに `foo` をその場で変更
: 十分な時間待つ
$ git update-index 'bar'
後者がないと、インデックスファイルのタイムスタンプは新しい値を取得し、誤ってクリーンなエントリ foo
は、前者のロジックで実行されたタイムスタンプ比較チェックによってキャッチされなくなります。 後者は、 foo
のキャッシュされた統計情報が作業ツリー内のファイルと決して一致しないことを保証するため、後で ce_match_stat_basic()
をチェックすると、インデックスエントリがファイルと一致しないことが報告され、Gitはより高価な ce_modified_check_fs()
にフォールバックする必要がありません。
Runtime penalty
ce_match_stat()
から ce_modified_check_fs()
にフォールバックすることによる実行時のペナルティは、非常にクリーンなエントリが多数ある場合、非常に高くつく可能性があります。 この状況を人為的に作成する明白な方法は、大規模プロジェクトの作業ツリー内のすべてのファイルに同じタイムスタンプを付け、それらに対して git update-index
を実行し、インデックスファイルに同じタイムスタンプを付けることです。
$ date >.datestamp
$ git ls-files | xargs touch -r .datestamp
$ git ls-files | git update-index --stdin
$ touch -r .datestamp .git/index
これにより、すべてのインデックスエントリが迅速にクリーンになります。 たとえば、Linuxプロジェクトでは、作業ツリーに20,000を超えるファイルがあります。 私のAthlon64X2 3800+で、上記の後に以下を実行します:
$ /usr/bin/time git diff-files
1.68user 0.54system 0:02.22elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+67111minor)pagefaults 0swaps
$ git update-index MAINTAINERS
$ /usr/bin/time git diff-files
0.02user 0.12system 0:00.14elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+935minor)pagefaults 0swaps
途中で git update-index
を実行すると、racily cleanなエントリがチェックされ、実際にはクリーンであるため、すべてのパスのキャッシュされた st_mtime
がそのまま残りました(したがって、このステップには最初の git diff-files
とほぼ同じ時間がかかりました)。 その後、それらはもはやracily cleanではありませんが、本当にクリーンであるため、git diff-files
の2回目の呼び出しはキャッシュされた統計情報を完全に利用しました。
Avoiding runtime penalty
上記の実行時のペナルティを回避するために、1.4.2以降のGitには、結果のインデックスファイルと同じタイムスタンプを持つ若いファイルが多数ある場合に、インデックスファイルがインデックス内の最も若いファイルよりも新しいタイムスタンプを取得することを確認するコードがありました。 それ以外の場合は、インデックスファイルの書き込みが完了する前に待機する必要があります。
実際には、インデックス内の多くのパスがすべて非常にクリーンであるという状況は非常にまれであると私は思いました。 多数のパスの最近のタイムスタンプを記録できる唯一のコードパスは以下のとおりです:
-
大規模プロジェクトの最初の
git add .
。 -
大規模プロジェクトを、空のインデックスから未入力の作業ツリーへ
git checkout
注意: git checkout
を使用してブランチを切り替えると、現在のブランチと新しいブランチの間で同じである既存の作業ツリーファイルのキャッシュされた統計情報が保持されます。これらはすべて、結果のインデックスファイルよりも古く、racily cleanになることはありません。 実際にチェックアウトされたファイルだけが、racily cleanになることができます。
ただし、racy回避コスト(raciness avoidance cost)が非常に重要な大規模なプロジェクトでは、インデックス内のすべてのオブジェクト名の初期計算に1秒以上かかり、その後インデックスファイルが書き出されます。 したがって、インデックスファイルのタイムスタンプは、作業ツリーの最も若いファイルより1秒以上遅くなります。 これは、これらの場合、結果のインデックスに実際には racily clean なエントリがないことを意味します。
この議論に基づいて、現在のコードは、実際にはもう存在しない実行時のペナルティを回避するために「回避策」を使用していません。 これは、2006年8月15日にcommit0fc82cffで実行されました。