Background

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

There are cases where Git needs to examine the differences between the virtual working tree state in the index and the files in the working tree. The most obvious case is when the user asks git diff (or its low level implementation, git diff-files) or git-ls-files --modified. In addition, Git internally checks if the files in the working tree are different from what are recorded in the index to avoid stomping on local changes in them during patch application, switching branches, and merging.

作業ツリー内のファイルとインデックスエントリ間のこの比較を高速化するために、インデックスエントリは、最後に更新されたときに 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つのことを行います:

  1. キャッシュされた統計情報によりファイルが変更されていないと言うには、 st_mtime がインデックスファイル自体のタイムスタンプと同じ(またはそれより新しい)場合(これは、上記の例では git update-index foo の実行を終了した時間です)では、コンテンツをインデックスエントリに登録されているオブジェクトと比較して、それらが一致することを確認します。

  2. 非常にクリーンなエントリを含むインデックスファイルが更新されると、キャッシュされた 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

In order to avoid the above runtime penalty, post 1.4.2 Git used to have a code that made sure the index file got a timestamp newer than the youngest files in the index when there were many young files with the same timestamp as the resulting index file otherwise would have by waiting before finishing writing the index file out.

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

  1. 大規模プロジェクトの最初の git add . 。

  2. 大規模プロジェクトを、空のインデックスから未入力の作業ツリーへ git checkout

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

In a large project where raciness avoidance cost really matters, however, the initial computation of all object names in the index takes more than one second, and the index file is written out after all that happens. Therefore the timestamp of the index file will be more than one second later than the youngest file in the working tree. This means that in these cases there actually will not be any racily clean entry in the resulting index.

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