]>
Commit | Line | Data |
---|---|---|
2de9b711 | 1 | Use of index and Racy Git problem |
520cd3ec JH |
2 | ================================= |
3 | ||
4 | Background | |
5 | ---------- | |
6 | ||
2de9b711 | 7 | The index is one of the most important data structures in Git. |
520cd3ec JH |
8 | It represents a virtual working tree state by recording list of |
9 | paths and their object names and serves as a staging area to | |
10 | write out the next tree object to be committed. The state is | |
11 | "virtual" in the sense that it does not necessarily have to, and | |
12 | often does not, match the files in the working tree. | |
13 | ||
2de9b711 | 14 | There are cases Git needs to examine the differences between the |
520cd3ec JH |
15 | virtual working tree state in the index and the files in the |
16 | working tree. The most obvious case is when the user asks `git | |
17 | diff` (or its low level implementation, `git diff-files`) or | |
2de9b711 | 18 | `git-ls-files --modified`. In addition, Git internally checks |
e1bb1d31 | 19 | if the files in the working tree are different from what are |
520cd3ec JH |
20 | recorded in the index to avoid stomping on local changes in them |
21 | during patch application, switching branches, and merging. | |
22 | ||
23 | In order to speed up this comparison between the files in the | |
24 | working tree and the index entries, the index entries record the | |
25 | information obtained from the filesystem via `lstat(2)` system | |
26 | call when they were last updated. When checking if they differ, | |
2de9b711 | 27 | Git first runs `lstat(2)` on the files and compares the result |
520cd3ec | 28 | with this information (this is what was originally done by the |
e1bb1d31 | 29 | `ce_match_stat()` function, but the current code does it in |
520cd3ec | 30 | `ce_match_stat_basic()` function). If some of these "cached |
2de9b711 | 31 | stat information" fields do not match, Git can tell that the |
520cd3ec JH |
32 | files are modified without even looking at their contents. |
33 | ||
34 | Note: not all members in `struct stat` obtained via `lstat(2)` | |
35 | are used for this comparison. For example, `st_atime` obviously | |
2de9b711 | 36 | is not useful. Currently, Git compares the file type (regular |
520cd3ec JH |
37 | files vs symbolic links) and executable bits (only for regular |
38 | files) from `st_mode` member, `st_mtime` and `st_ctime` | |
39 | timestamps, `st_uid`, `st_gid`, `st_ino`, and `st_size` members. | |
40 | With a `USE_STDEV` compile-time option, `st_dev` is also | |
41 | compared, but this is not enabled by default because this member | |
42 | is not stable on network filesystems. With `USE_NSEC` | |
43 | compile-time option, `st_mtim.tv_nsec` and `st_ctim.tv_nsec` | |
b1ffafa9 | 44 | members are also compared. On Linux, this is not enabled by default |
989c530e JN |
45 | because in-core timestamps can have finer granularity than |
46 | on-disk timestamps, resulting in meaningless changes when an | |
47 | inode is evicted from the inode cache. See commit 8ce13b0 | |
48 | of git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git | |
17b83d71 | 49 | ([PATCH] Sync in core time granularity with filesystems, |
b1ffafa9 KB |
50 | 2005-01-04). This patch is included in kernel 2.6.11 and newer, but |
51 | only fixes the issue for file systems with exactly 1 ns or 1 s | |
52 | resolution. Other file systems are still broken in current Linux | |
53 | kernels (e.g. CEPH, CIFS, NTFS, UDF), see | |
14b7664d | 54 | https://lore.kernel.org/lkml/5577240D.7020309@gmail.com/ |
520cd3ec | 55 | |
2de9b711 | 56 | Racy Git |
520cd3ec JH |
57 | -------- |
58 | ||
59 | There is one slight problem with the optimization based on the | |
60 | cached stat information. Consider this sequence: | |
61 | ||
e1bb1d31 | 62 | : modify 'foo' |
520cd3ec | 63 | $ git update-index 'foo' |
e1bb1d31 | 64 | : modify 'foo' again, in-place, without changing its size |
520cd3ec JH |
65 | |
66 | The first `update-index` computes the object name of the | |
67 | contents of file `foo` and updates the index entry for `foo` | |
68 | along with the `struct stat` information. If the modification | |
69 | that follows it happens very fast so that the file's `st_mtime` | |
70 | timestamp does not change, after this sequence, the cached stat | |
71 | information the index entry records still exactly match what you | |
e1bb1d31 JH |
72 | would see in the filesystem, even though the file `foo` is now |
73 | different. | |
2de9b711 | 74 | This way, Git can incorrectly think files in the working tree |
520cd3ec | 75 | are unmodified even though they actually are. This is called |
2de9b711 | 76 | the "racy Git" problem (discovered by Pasky), and the entries |
520cd3ec JH |
77 | that appear clean when they may not be because of this problem |
78 | are called "racily clean". | |
79 | ||
2de9b711 | 80 | To avoid this problem, Git does two things: |
520cd3ec JH |
81 | |
82 | . When the cached stat information says the file has not been | |
83 | modified, and the `st_mtime` is the same as (or newer than) | |
84 | the timestamp of the index file itself (which is the time `git | |
85 | update-index foo` finished running in the above example), it | |
86 | also compares the contents with the object registered in the | |
87 | index entry to make sure they match. | |
88 | ||
89 | . When the index file is updated that contains racily clean | |
90 | entries, cached `st_size` information is truncated to zero | |
91 | before writing a new version of the index file. | |
92 | ||
93 | Because the index file itself is written after collecting all | |
94 | the stat information from updated paths, `st_mtime` timestamp of | |
95 | it is usually the same as or newer than any of the paths the | |
96 | index contains. And no matter how quick the modification that | |
97 | follows `git update-index foo` finishes, the resulting | |
e1bb1d31 | 98 | `st_mtime` timestamp on `foo` cannot get a value earlier |
520cd3ec JH |
99 | than the index file. Therefore, index entries that can be |
100 | racily clean are limited to the ones that have the same | |
101 | timestamp as the index file itself. | |
102 | ||
103 | The callers that want to check if an index entry matches the | |
104 | corresponding file in the working tree continue to call | |
105 | `ce_match_stat()`, but with this change, `ce_match_stat()` uses | |
106 | `ce_modified_check_fs()` to see if racily clean ones are | |
107 | actually clean after comparing the cached stat information using | |
108 | `ce_match_stat_basic()`. | |
109 | ||
110 | The problem the latter solves is this sequence: | |
111 | ||
112 | $ git update-index 'foo' | |
113 | : modify 'foo' in-place without changing its size | |
114 | : wait for enough time | |
115 | $ git update-index 'bar' | |
116 | ||
117 | Without the latter, the timestamp of the index file gets a newer | |
118 | value, and falsely clean entry `foo` would not be caught by the | |
119 | timestamp comparison check done with the former logic anymore. | |
120 | The latter makes sure that the cached stat information for `foo` | |
121 | would never match with the file in the working tree, so later | |
e1bb1d31 | 122 | checks by `ce_match_stat_basic()` would report that the index entry |
2de9b711 | 123 | does not match the file and Git does not have to fall back on more |
520cd3ec JH |
124 | expensive `ce_modified_check_fs()`. |
125 | ||
126 | ||
127 | Runtime penalty | |
128 | --------------- | |
129 | ||
130 | The runtime penalty of falling back to `ce_modified_check_fs()` | |
131 | from `ce_match_stat()` can be very expensive when there are many | |
132 | racily clean entries. An obvious way to artificially create | |
133 | this situation is to give the same timestamp to all the files in | |
134 | the working tree in a large project, run `git update-index` on | |
135 | them, and give the same timestamp to the index file: | |
136 | ||
137 | $ date >.datestamp | |
138 | $ git ls-files | xargs touch -r .datestamp | |
139 | $ git ls-files | git update-index --stdin | |
140 | $ touch -r .datestamp .git/index | |
141 | ||
283efb01 TK |
142 | This will make all index entries racily clean. The linux project, for |
143 | example, there are over 20,000 files in the working tree. On my | |
144 | Athlon 64 X2 3800+, after the above: | |
520cd3ec JH |
145 | |
146 | $ /usr/bin/time git diff-files | |
147 | 1.68user 0.54system 0:02.22elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k | |
148 | 0inputs+0outputs (0major+67111minor)pagefaults 0swaps | |
149 | $ git update-index MAINTAINERS | |
150 | $ /usr/bin/time git diff-files | |
151 | 0.02user 0.12system 0:00.14elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k | |
152 | 0inputs+0outputs (0major+935minor)pagefaults 0swaps | |
153 | ||
154 | Running `git update-index` in the middle checked the racily | |
155 | clean entries, and left the cached `st_mtime` for all the paths | |
156 | intact because they were actually clean (so this step took about | |
157 | the same amount of time as the first `git diff-files`). After | |
158 | that, they are not racily clean anymore but are truly clean, so | |
159 | the second invocation of `git diff-files` fully took advantage | |
160 | of the cached stat information. | |
161 | ||
162 | ||
163 | Avoiding runtime penalty | |
164 | ------------------------ | |
165 | ||
2de9b711 | 166 | In order to avoid the above runtime penalty, post 1.4.2 Git used |
e1bb1d31 JH |
167 | to have a code that made sure the index file |
168 | got timestamp newer than the youngest files in the index when | |
520cd3ec JH |
169 | there are many young files with the same timestamp as the |
170 | resulting index file would otherwise would have by waiting | |
171 | before finishing writing the index file out. | |
172 | ||
e1bb1d31 JH |
173 | I suspected that in practice the situation where many paths in the |
174 | index are all racily clean was quite rare. The only code paths | |
175 | that can record recent timestamp for large number of paths are: | |
520cd3ec JH |
176 | |
177 | . Initial `git add .` of a large project. | |
178 | ||
179 | . `git checkout` of a large project from an empty index into an | |
180 | unpopulated working tree. | |
181 | ||
182 | Note: switching branches with `git checkout` keeps the cached | |
183 | stat information of existing working tree files that are the | |
184 | same between the current branch and the new branch, which are | |
185 | all older than the resulting index file, and they will not | |
186 | become racily clean. Only the files that are actually checked | |
187 | out can become racily clean. | |
188 | ||
189 | In a large project where raciness avoidance cost really matters, | |
190 | however, the initial computation of all object names in the | |
191 | index takes more than one second, and the index file is written | |
192 | out after all that happens. Therefore the timestamp of the | |
a5d86f74 | 193 | index file will be more than one seconds later than the |
520cd3ec JH |
194 | youngest file in the working tree. This means that in these |
195 | cases there actually will not be any racily clean entry in | |
196 | the resulting index. | |
197 | ||
e1bb1d31 JH |
198 | Based on this discussion, the current code does not use the |
199 | "workaround" to avoid the runtime penalty that does not exist in | |
200 | practice anymore. This was done with commit 0fc82cff on Aug 15, | |
201 | 2006. |