From: Junio C Hamano <hidden> Date: 2016-06-15 22:44:43
"Ben Lynn" [off-list ref] writes:
I had thought about this. I hacked some code up where the index looks
at the current system time when updating a cache entry to determine if
the hash is racy. Is doing one time(NULL) call per file reasonable?
I'm guessing it must be cheaper that a stat call.
Hmm, sorry, could you elaborate how you would plan to use the return value
from time(2) per file?
The "index file timestamp" trick assumes that once we start reading from
and writing to the filesystem (in order to hash the current contents,
check if there is any modification), nobody else touches the paths we are
interested in (e.g., after "read-tree -m -u" checks out the new contents,
grabs the stat information from the newly deposited file and stuffs that
in the index, you do not go in and edit it further until our process
returns the control to you). We also assume that the files (both work
tree and the index) live in the same filesystem and the file timestamp,
which could be skewed compared to the system clock if the filesystem is
over the network, are consistent among them and monotonicly increasing.
You have to have some assumption --- if you allow anybody to touch
anything behind your back, or if you allow timestamps of some
files come from different time sources than the one for some other
files, I do not think any lstat(2) based change detection scheme
would work.
We do our writeout first and then the index is updated after all our
writeout is done, so by definition (more precisely, "by that assumption"),
anything older than the timestamp of the index file are up to date, if
their filesystem timestamp match the timestamp recorded in the index, and
anything that is the same or newer than the index timestamp is suspect.
And that is the reason the current code gets by only with a single
timestamp. I'd have to go back and study your breakage scenario a bit
better (I'm still at work today).
I had thought about this. I hacked some code up where the index looks
at the current system time when updating a cache entry to determine if
the hash is racy. Is doing one time(NULL) call per file reasonable?
I'm guessing it must be cheaper that a stat call.
Hmm, sorry, could you elaborate how you would plan to use the return value
from time(2) per file?
My bad, I was extremely unclear. I meant I had thought about not
bothering to look at the index file timestamp (I'm not sure why, but I
instinctively trust the system clock more!). I'm making the same
assumptions, i.e. files are not touched while they're being indexed. I
suppose with the way I'm doing things, you can touch a file right up
to the point where the index wants to stat that particular file and
maybe look at its contents, but not afterwards. (And this is pretty
useless, because how are you going to know which file the index is up
to?)
I maintain a flag per file, and after computing its SHA1, I compare
the mtime with the current system time. If it matches, then that means
the hash can't be trusted (because of the race condition) and I set
the flag. This way, I avoid examining the index timestamp.
I call time(NULL) for each file out of laziness. I could cache the
value somewhere the first time, but that means I'd have to pass around
an extra argument to a whole bunch of functions, because of the way
I've written my code. But I don't think it's much of a drawback,
because I stat() each file anyway.
Actually, what Linus describes would be desirable in some sense. If
the index mtime timestamp were always later than the time you
performed the indexing (and accurate) because it always took a long
time, assuming no one messes with files while you're indexing, there
would be no race condition to worry about.
-Ben
I call time(NULL) for each file out of laziness. I could cache the
value somewhere the first time, but that means I'd have to pass around
an extra argument to a whole bunch of functions, because of the way
I've written my code. But I don't think it's much of a drawback,
because I stat() each file anyway.
No, that would be horrible. There is no guarantee that time() has
anything to do with the stat timestamps anyway.
The right way to do things would be to just do a stat() on the index file
as it is created, and then save the mtime of that stat into the file. That
way, you have the mtime of the index file not for the *last* write, but
for the *first* one.
Linus
The right way to do things would be to just do a stat() on the index file
as it is created, and then save the mtime of that stat into the file. That
way, you have the mtime of the index file not for the *last* write, but
for the *first* one.
Sorry, but if we're assuming no one is touching the files while we're
updating the index (including writing it to disk), why does it matter
whether we use the time of first or last write? In fact, if a index
write takes a long time, using the last write time as the mtime would
be beneficial for the race condition stuff.
-Ben
Sorry, but if we're assuming no one is touching the files while we're
updating the index (including writing it to disk), why does it matter
whether we use the time of first or last write? In fact, if a index
write takes a long time, using the last write time as the mtime would
be beneficial for the race condition stuff.
Oh, if you assume nobody is touching the files as the index is created,
none of this matters.
So if *that* was your only race worry, then git should already be
perfectly fine.
The issue with the timestamp of the index only happens if somebody ends up
modifying the files that are being indexed _as_ they are indexed. Quite
frankly, git will notice that too in just about all possible cases, but if
the size stays the same and the modification time ends up still being
smaller than the final index mtime (because writing the index took so
long!), then you might miss some modifications that would otherwise be
noticed.
Linus
Ah, I hadn't seen that. Yes, it is better to use the first write as
the timestamp. Would this catch everything? If the filesystem clock is
monotonically increasing and consistent then with this setup, you can
touch files even as they are being indexed? (Disregarding nonsense
like changing sizes by 2^32.)
Just realized I should have paid more attention to Junio's first reply
to me. My eye had skipped over the paragraph about clock skew, and
this caused some confusion. Sorry about all my extra emails!
-Ben
On Tue, Jun 10, 2008 at 7:12 PM, Linus Torvalds
[off-list ref] wrote:
On Tue, 10 Jun 2008, Ben Lynn wrote:
quoted
Sorry, but if we're assuming no one is touching the files while we're
updating the index (including writing it to disk), why does it matter
whether we use the time of first or last write? In fact, if a index
write takes a long time, using the last write time as the mtime would
be beneficial for the race condition stuff.
Oh, if you assume nobody is touching the files as the index is created,
none of this matters.
So if *that* was your only race worry, then git should already be
perfectly fine.
The issue with the timestamp of the index only happens if somebody ends up
modifying the files that are being indexed _as_ they are indexed. Quite
frankly, git will notice that too in just about all possible cases, but if
the size stays the same and the modification time ends up still being
smaller than the final index mtime (because writing the index took so
long!), then you might miss some modifications that would otherwise be
noticed.
Linus
Ah, I hadn't seen that. Yes, it is better to use the first write as
the timestamp. Would this catch everything? If the filesystem clock is
monotonically increasing and consistent then with this setup, you can
touch files even as they are being indexed? (Disregarding nonsense
like changing sizes by 2^32.)
Yes, I think that at that point it would protect against arbitrary
modifications even concurrently to index file creation.
That said, I don't think you even need a new index file format. We could
just do a stat() on starting the index file creation, and then do a
futimes() system call at the end to re-set the mtime to the beginning
before we rename it back over the old index file.
Linus
Am I going crazy? All of a sudden I think I can get away without a
size zero hack. How about this smudging routine:
if (!ce_match_stat_basic(ce, &st)) {
recompute_sha1_and_update_index(); // no other checks required
}
That should be sufficient. I think what happened was the following.
Once upon a time, the race fix was "if (stats_match) cached_size = 0",
which is nice because you don't have to examine file contents. Later,
because of the
$ echo xyzzy >frotz ; git-update-index --add frotz ; : >frotz
$ sleep 3
$ echo filfre >nitfol ; git-update-index --add nitfol
issue, the ce_modified_check_fs was added.
But then if we're going to be examining file contents anyway, we may
as well drop the whole size zero trick and simply update the hash. The
bug I brought up also goes away.
-Ben
P.S: I could go through the history to see, but I bet there was a
stage after the race condition was discovered but before it was
realized that
$ git update-index 'foo'
: modify 'foo' in-place without changing its size
: wait for enough time
$ git update-index 'bar'
was a problem.
On Tue, Jun 10, 2008 at 7:39 PM, Linus Torvalds
[off-list ref] wrote:
On Tue, 10 Jun 2008, Ben Lynn wrote:
quoted
Ah, I hadn't seen that. Yes, it is better to use the first write as
the timestamp. Would this catch everything? If the filesystem clock is
monotonically increasing and consistent then with this setup, you can
touch files even as they are being indexed? (Disregarding nonsense
like changing sizes by 2^32.)
Yes, I think that at that point it would protect against arbitrary
modifications even concurrently to index file creation.
That said, I don't think you even need a new index file format. We could
just do a stat() on starting the index file creation, and then do a
futimes() system call at the end to re-set the mtime to the beginning
before we rename it back over the old index file.
Linus
And I'm sure you've also realized we could use the old race fix with
SIZE_MAX instead of zero, i.e:
if (!ce_match_stat_basic(ce, &st)) {
ce->ce_size = ~0;
}
return; // don't bother with ce_modified_check_fs
This is dissatisfying in that we're abusing the size variable. I'd
much prefer adding a flag per entry. And now there are other file
sizes, albeit ridiculously large ones, that will trick git. But it is
much faster than examining file contents. Luckily the decision of
which fix to use is not up to me.
-Ben
On Wed, Jun 11, 2008 at 5:58 AM, Ben Lynn [off-list ref] wrote:
Am I going crazy? All of a sudden I think I can get away without a
size zero hack. How about this smudging routine:
if (!ce_match_stat_basic(ce, &st)) {
recompute_sha1_and_update_index(); // no other checks required
}
That should be sufficient. I think what happened was the following.
Once upon a time, the race fix was "if (stats_match) cached_size = 0",
which is nice because you don't have to examine file contents. Later,
because of the
$ echo xyzzy >frotz ; git-update-index --add frotz ; : >frotz
$ sleep 3
$ echo filfre >nitfol ; git-update-index --add nitfol
issue, the ce_modified_check_fs was added.
But then if we're going to be examining file contents anyway, we may
as well drop the whole size zero trick and simply update the hash. The
bug I brought up also goes away.
-Ben
P.S: I could go through the history to see, but I bet there was a
stage after the race condition was discovered but before it was
realized that
$ git update-index 'foo'
: modify 'foo' in-place without changing its size
: wait for enough time
$ git update-index 'bar'
was a problem.
On Tue, Jun 10, 2008 at 7:39 PM, Linus Torvalds
[off-list ref] wrote:
quoted
On Tue, 10 Jun 2008, Ben Lynn wrote:
quoted
Ah, I hadn't seen that. Yes, it is better to use the first write as
the timestamp. Would this catch everything? If the filesystem clock is
monotonically increasing and consistent then with this setup, you can
touch files even as they are being indexed? (Disregarding nonsense
like changing sizes by 2^32.)
Yes, I think that at that point it would protect against arbitrary
modifications even concurrently to index file creation.
That said, I don't think you even need a new index file format. We could
just do a stat() on starting the index file creation, and then do a
futimes() system call at the end to re-set the mtime to the beginning
before we rename it back over the old index file.
Linus
Am I going crazy? All of a sudden I think I can get away without a
size zero hack. How about this smudging routine:
if (!ce_match_stat_basic(ce, &st)) {
recompute_sha1_and_update_index(); // no other checks required
}
No.
You can't recompute the sha1. That SHA1 is what the user asked us to
remember - whether smudged or not. So you mustn't change it, until the
user does a "git add" or "git update-index" (or anything that implicitly
does the same).
You can change the _stat_ information, since that is only used for
matching the tree (positively or negatively), but the SHA1 itself is not
just a cache, it's the "pending state" in the index.
So smudging must change some piece of data that is only about the stat
cache - the st_size, the mtime, anything like that.
Linus
I'm not sure why you think my patch that just did the zero-sized blob
thing was slow? It's a 20-byte memcmp(). It takes no time at all.
I don't think the memcmp is slow. I think the ce_modified_check_fs in:
smudge() {
...
if (ce_match_stat_basic(ce, &st))
return;
if (ce_modified_check_fs(ce, &st))
ce->ce_size = 0;
}
is potentially slow, and I'm saying you could replace it with
smudge() {
...
if (ce_match_stat_basic(ce, &st))
return;
ce->ce_size = ~0;
}
to avoid the ce_modified_check_fs call. But it is an unclean solution,
which is why I champion having an extra flag per file.
Also, I think we could set ce->ce_size to ~0 when we first realize
timestamp = mtime, and we'd no longer have to do index-wide smudging
on writes.
Thanks for the explanation by the way. I get why you can't modify the
SHA1. It is indeed what we asked git to record, right or wrong. I got
confused because I misread the code and thought ce_modified_check_fs()
would write the new SHA1 to disk.
-Ben
I don't think the memcmp is slow. I think the ce_modified_check_fs in:
smudge() {
...
if (ce_match_stat_basic(ce, &st))
return;
if (ce_modified_check_fs(ce, &st))
ce->ce_size = 0;
}
is potentially slow, and I'm saying you could replace it with
smudge() {
...
if (ce_match_stat_basic(ce, &st))
return;
ce->ce_size = ~0;
}
to avoid the ce_modified_check_fs call. But it is an unclean solution,
which is why I champion having an extra flag per file.
Well, you have to think about what you want to optimize here.
The thing we want to optimize is not the writing of the index file, but
the subsequent _use_ of it!
As such, the last thing we actually want to do is to smudge the index file
entry. If it actually has a possibility of being not smudged, we're much
better off saying "hey, now the index file is newer, and the file it
refers to is all good!"
That way, we won't have to do the ce_modified_check_fs() call later - we
do it just once, and the file is up-to-date.
So we don't want to smudge it, but if the stat information says it migth
match even though it doesn't, we have to. But if the stat information says
it matches, and the data actually _does_ match, then we shouldn't smudge
it, we should be happy - and all subsequent users of the index will then
know that they don't even need to look at the file contents.
Linus
So we don't want to smudge it, but if the stat information says it migth
match even though it doesn't, we have to. But if the stat information says
it matches, and the data actually _does_ match, then we shouldn't smudge
it, we should be happy - and all subsequent users of the index will then
know that they don't even need to look at the file contents.
I understand. In that case, what about an unsmudging routine so we can
have the best of both worlds? We unconditionally smudge the file as
soon as timestamp = mtime is detected. We never do index-wide smudging
on writes, but rather, on index read of particular file we do this:
if (stats_differ()) {
if (hash_matches()) {
// Aha! An unconditionally smudged file that we might be able to unsmudge,
// so future reads can avoid this check.
if (mtime < timestamp) {
fix_stats(); // Involves writing to index.
}
// D'oh! This file could still be racy, leave it smudged.
} else {
// The stats were right, the hash does differ.
...
}
}
We minimize the amount of ce_check_modified_fs() calls for any given
sequence of index operations. Instead of doing index-wide checks on
every write, we only check when we have no choice, i.e. the first time
a particular file is being looked up in the index. We fix its stats if
possible so future reads can avoid the painful check. The only
drawback is that I'm not sure how acceptable it is to write to the
index on a read operation. Is this a big deal? (If it were a separate
flag, I'm sure no one would mind!)
-Ben
The only drawback is that I'm not sure how acceptable it is to write to
the index on a read operation. Is this a big deal?
Historically, we *never* did it. In fact, it was a big deal. These days we
do it opportunistically for "git diff" if we can, but making sure that it
all still works for a read-only access (think gitweb etc - the reader is
*not* necessarily the owner of the archive at all!)
So I really prefer not to. But you can take it up with Junio if you think
it can be a big deal.
Linus
So I really prefer not to. But you can take it up with Junio if you think
it can be a big deal.
I began writing a patch but I abandoned it. I don't have much
experience with the code base and I'd almost certainly miss a bunch of
corner cases. Your patch seems to be the easiest way to go. I'm not
motivated to push pre-emptive smudging, even if it might be more
efficient. After all, how often does this race condition come up?
But I have a per-file flagged version of the index for personal use,
and it's good to know that it's a valid strategy.
Historically, we *never* did it. In fact, it was a big deal. These days we
do it opportunistically for "git diff" if we can, but making sure that it
all still works for a read-only access (think gitweb etc - the reader is
*not* necessarily the owner of the archive at all!)
I hadn't thought about this case. This is intriguing: why does gitweb
need access to the index? I thought the index was only to make
operations fast for users intending to make changes to the repo. Why
can't servers run stripped-down versions of git that don't bother with
an index?
-Ben