{"thread":{"id":"13880","subject":"git bugs","startedAt":"2008-06-10T08:41:34Z","lastAt":"2008-06-14T06:25:13Z","messageCount":35,"participants":["Ben Lynn","Daniel Barkalow","Linus Torvalds","Junio C Hamano","Stephen R. van den Berg","Shawn O. Pearce","Johannes Schindelin","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"79326","messageId":"832adb090806100141n69c086a2v2f59fe94b2f4ead3@mail.gmail.com","threadId":"13880","inReplyTo":null,"subject":"git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-10T08:41:34Z","receivedAt":"2008-06-10T08:41:34Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"I've come across a couple of bugs. Most users will probably never\nencounter them, but I think they ought to be fixed. Apologies if\nthey're well-known issues. I haven't read much of this list.\n\n1. The import/export language poorly handles distinct initial commits\non the same branch, because given two commits with same branch name,\nit assumes the latter is the descendant of the former (if there are no\n\"from\" commands).\n\nNormally this is what you want. But if your project, like git, ever\nmerges distinct initial commits, then all but the first will\nunexpectedly gain parents, corrupting all their descendants' hashes.\nFor example:\n\n$ git clone git://git.kernel.org/pub/scm/git/git.git\n$ git checkout -b test 60ea0fdd7de001405fcc7591beb18a66a1f0dd09\n$ git fast-export test > /tmp/x\n$ cd /some/empty/dir\n$ git init\n$ git fast-import < /tmp/x\n$ git checkout test\n\nImporting a pristine export, we discover Linus did not in fact make\nthe first commit to the git project:\n\n$ git log d154ebcc23bfcec2ed44e365af9e5c14c6e22015\n\nAs a workaround, I have a custom importer that knows that\ngit-fast-export omits the \"from\" command in initial commits. But there\nshould be a command to specify that the current commit is an initial\ncommit, allowing reliable export of projects such as git.\n\n2. Kudos to everyone who figured out the nasty race condition and its\ncomplex solution as described in Documentation/technical/racy-git.txt\nand the comments of read-cache.c. It took me a while to get my head\naround it.\n\nUnfortunately, the solution isn't perfect. Try this:\n\n$ echo xyzzy > file\n$ git update-index --add file   # don't zero size since contents match\n$ echo frotz > file             # all stats still match, contents don't\n$ echo nitfol > other  # can be done much earlier\n$ git update-index --add other  # now the cached size is zeroed\n$ : > file                      # zero the file size muahahaha\n$ # Type fast! The above must take place within the same second! ;-)\n$ sleep 2\n$ echo filfre > other\n$ git update-index --add other  # stats of \"file\" match, hash is wrong\n\nEssentially, we trigger two index writes that avoid operations on\n\"file\": one immediately after \"file\" is first committed and identified\nas racily clean, and the second some time later, after we have\nsneakily zeroed the file behind git's back (after previously editing\nits contents in place). We defeat the safeguards and end up with a bad\nhash in the index that appears valid.\n\nThe\"other\" file merely causes index writes without reading the \"file\"\nentry. It is also racily clean in the above, but this is irrelevant.\n\nIt's unlikely this sequence of operations would occur in real usage,\nbut I'd sleep better if this index corruption bug were eliminated. One\npractical but unsatisfactory easy \"fix\" is to mark racily clean\nentries with SIZE_MAX instead of 0. Who uses git to track to files of\nthis size?\n\nA better solution would be to introduce a new per-entry flag. Let's\ncall it \"dodgy\". Then during a cache entry update, we set \"dodgy\" if\nthe mtime is bigger or equal to the index timestamp. And during cache\nentry reads, we check \"dodgy\": if clear, then we trust the hatch,\notherwise we don't trust the hash and recompute it, again setting\n\"dodgy\" if necessary (i.e. if the mtime matches the index timestamp\nagain).\n\nAlthough this solution does require adding a flag per index entry, we\nno longer have to scan through the index on every index write to\nperform the size zero hack.\n\n-Ben\n"},{"id":"79365","messageId":"alpine.LNX.1.00.0806101236120.19665@iabervon.org","threadId":"13880","inReplyTo":"832adb090806100141n69c086a2v2f59fe94b2f4ead3@mail.gmail.com","subject":"Re: git bugs","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2008-06-10T16:58:34Z","receivedAt":"2008-06-10T16:58:34Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Tue, 10 Jun 2008, Ben Lynn wrote:\n\n> 2. Kudos to everyone who figured out the nasty race condition and its\n> complex solution as described in Documentation/technical/racy-git.txt\n> and the comments of read-cache.c. It took me a while to get my head\n> around it.\n> \n> Unfortunately, the solution isn't perfect. Try this:\n> \n> $ echo xyzzy > file\n> $ git update-index --add file   # don't zero size since contents match\n> $ echo frotz > file             # all stats still match, contents don't\n> $ echo nitfol > other  # can be done much earlier\n> $ git update-index --add other  # now the cached size is zeroed\n> $ : > file                      # zero the file size muahahaha\n> $ # Type fast! The above must take place within the same second! ;-)\n> $ sleep 2\n> $ echo filfre > other\n> $ git update-index --add other  # stats of \"file\" match, hash is wrong\n> \n> Essentially, we trigger two index writes that avoid operations on\n> \"file\": one immediately after \"file\" is first committed and identified\n> as racily clean, and the second some time later, after we have\n> sneakily zeroed the file behind git's back (after previously editing\n> its contents in place). We defeat the safeguards and end up with a bad\n> hash in the index that appears valid.\n> \n> The\"other\" file merely causes index writes without reading the \"file\"\n> entry. It is also racily clean in the above, but this is irrelevant.\n> \n> It's unlikely this sequence of operations would occur in real usage,\n> but I'd sleep better if this index corruption bug were eliminated. One\n> practical but unsatisfactory easy \"fix\" is to mark racily clean\n> entries with SIZE_MAX instead of 0.\n\nWe could distinguish a \"racily clean\" entry from a 0-length file entry \nbased on the hash. That is, say that a file isn't clean even though the \nsize matches, if the size is 0 and the entry's hash isn't the same as the \nfile's hash, which is e69de29bb2d1d6434b8b29ae775ad8c2e48c5391. Nice thing \nabout 0-length files is that you can compute their hashes without reading \nthem.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"79371","messageId":"alpine.LFD.1.10.0806101028040.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806100141n69c086a2v2f59fe94b2f4ead3@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-10T17:44:43Z","receivedAt":"2008-06-10T17:44:43Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 10 Jun 2008, Ben Lynn wrote:\n> \n> Unfortunately, the solution isn't perfect. Try this:\n\nHeh.\n\nThat's just because our \"smudge_racily_clean_entry()\" uses 0 as the magic \nsmudging size.\n\nYou can fix this multiple ways. One would be to pick another size that is \nsimply less likely (eg ~0 instead), which leaves the theoretical race, and \njust makes it practically impossible to hit (not that I think it's very \npractical to hit already).\n\nThe other approach is to know that an empty blob always has a very \nspecific SHA1. Here's an trial patch.\n\n\t\tLinus\n\n---\n read-cache.c |   16 ++++++++++++++++\n 1 files changed, 16 insertions(+), 0 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 8e5fbb6..f83de8c 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -138,6 +138,16 @@ static int ce_modified_check_fs(struct cache_entry *ce, struct stat *st)\n \treturn 0;\n }\n \n+static int is_empty_blob_sha1(const unsigned char *sha1)\n+{\n+\tstatic const unsigned char empty_blob_sha1[20] = {\n+\t\t0xe6,0x9d,0xe2,0x9b,0xb2,0xd1,0xd6,0x43,0x4b,0x8b,\n+\t\t0x29,0xae,0x77,0x5a,0xd8,0xc2,0xe4,0x8c,0x53,0x91\n+\t};\n+\n+\treturn !hashcmp(sha1, empty_blob_sha1);\n+}\n+\n static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)\n {\n \tunsigned int changed = 0;\n@@ -193,6 +203,12 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)\n \tif (ce->ce_size != (unsigned int) st->st_size)\n \t\tchanged |= DATA_CHANGED;\n \n+\t/* Racily smudged entry? */\n+\tif (!ce->ce_size) {\n+\t\tif (!is_empty_blob_sha1(ce->sha1))\n+\t\t\tchanged |= DATA_CHANGED;\n+\t}\n+\n \treturn changed;\n }\n \n"},{"id":"79375","messageId":"832adb090806101145w55729676ya7bcfb41b0413f59@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806101028040.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-10T18:45:23Z","receivedAt":"2008-06-10T18:45:23Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"I hadn't thought of exploiting the fact that the SHA1 of an empty file\nis fixed. Nice! I believe I can prove there are no races now.\nIncidentally, this is how I first found the bug: I was trying to prove\nwhat git did worked.\n\nI still prefer a per-entry flag solution (I suspect it's faster, and\nthe proof is easier), but that's too much work.\n\n-Ben\n\nOn Tue, Jun 10, 2008 at 10:44 AM, Linus Torvalds\n<torvalds@linux-foundation.org> wrote:\n>\n>\n> On Tue, 10 Jun 2008, Ben Lynn wrote:\n>>\n>> Unfortunately, the solution isn't perfect. Try this:\n>\n> Heh.\n>\n> That's just because our \"smudge_racily_clean_entry()\" uses 0 as the magic\n> smudging size.\n>\n> You can fix this multiple ways. One would be to pick another size that is\n> simply less likely (eg ~0 instead), which leaves the theoretical race, and\n> just makes it practically impossible to hit (not that I think it's very\n> practical to hit already).\n>\n> The other approach is to know that an empty blob always has a very\n> specific SHA1. Here's an trial patch.\n>\n>                Linus\n>\n> ---\n>  read-cache.c |   16 ++++++++++++++++\n>  1 files changed, 16 insertions(+), 0 deletions(-)\n>\n> diff --git a/read-cache.c b/read-cache.c\n> index 8e5fbb6..f83de8c 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -138,6 +138,16 @@ static int ce_modified_check_fs(struct cache_entry *ce, struct stat *st)\n>        return 0;\n>  }\n>\n> +static int is_empty_blob_sha1(const unsigned char *sha1)\n> +{\n> +       static const unsigned char empty_blob_sha1[20] = {\n> +               0xe6,0x9d,0xe2,0x9b,0xb2,0xd1,0xd6,0x43,0x4b,0x8b,\n> +               0x29,0xae,0x77,0x5a,0xd8,0xc2,0xe4,0x8c,0x53,0x91\n> +       };\n> +\n> +       return !hashcmp(sha1, empty_blob_sha1);\n> +}\n> +\n>  static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)\n>  {\n>        unsigned int changed = 0;\n> @@ -193,6 +203,12 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)\n>        if (ce->ce_size != (unsigned int) st->st_size)\n>                changed |= DATA_CHANGED;\n>\n> +       /* Racily smudged entry? */\n> +       if (!ce->ce_size) {\n> +               if (!is_empty_blob_sha1(ce->sha1))\n> +                       changed |= DATA_CHANGED;\n> +       }\n> +\n>        return changed;\n>  }\n>\n>\n"},{"id":"79383","messageId":"alpine.LFD.1.10.0806101249580.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806101145w55729676ya7bcfb41b0413f59@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-10T20:06:22Z","receivedAt":"2008-06-10T20:06:22Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 10 Jun 2008, Ben Lynn wrote:\n>\n> Nice! I believe I can prove there are no races now.\n\nIt's worth pointing out that even in the absense of races, you can \nobviously screw things up if you really work at it, and *want* to. We \ncannot guarantee that we see all file changes from the stat() information, \nand we don't even save the whole stat info (ie we only save the low 32 \nbits).\n\nThe ctime check is there to help make it harder for people to play games \nby setting the mtime back in time after having changed things, but we may \nat some point be forced to remove it because it triggers with things like \nbeagle that use inode attributes to save indexing information (and thus \nchange ctime).\n\nAnd different systems have different approaches to what happens when a \nfile gets modified through a writable mmap(). Exactly what is the mtime \ngoing to be? \n\nSo I think git does a really good job at matching the stat() information, \nand the suggested patch makes it even stricter, but I think we should not \neven try to make it handle \"malicious\" changes. I bet you can work at \nmaking it miss some update if you really *really* try.\n\nAnd I think there is one known race: the index mtime itself is not \nrace-free. Remember: it may take more than a second to write the index \nfile! So I can imagine that if you can set it up so that you change the \nfile as the index is written out, and the index write is delayed \nsufficiently, the racy timestamp logic can fail just because the timestamp \non the index file ends up being later.\n\nThis is more easily shown by doing a 'touch' on the index file afterwards, \nof course.\n\nAnd yes, we should have written the timestamp to the file itself, instead \nof reading it from the filesystem.\n\n\t\t\tLinus\n"},{"id":"79402","messageId":"832adb090806101609q17a21948nb5814c3b22bd832d@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806101249580.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-10T23:09:23Z","receivedAt":"2008-06-10T23:09:23Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":">> Nice! I believe I can prove there are no races now.\n>\n> It's worth pointing out that even in the absense of races, you can\n> obviously screw things up if you really work at it, and *want* to. We\n> cannot guarantee that we see all file changes from the stat() information,\n> and we don't even save the whole stat info (ie we only save the low 32\n> bits).\n\nI agree completely. My proof only holds in an abstract setting. It\nassumes things such as a strictly nondecreasing system clock is and\nthat ctime and mtime work in an ideal sense.\n\n> And different systems have different approaches to what happens when a\n> file gets modified through a writable mmap(). Exactly what is the mtime\n> going to be?\n\nGood point. I confess I've only learned about mmap very recently, from\nbrowsing the git code. All this time, I've been using streams, file\ndescriptors, etc. mmap is so much better!\n\nWhat's Linux do in this case? For indexing purposes, so long as the\nmtime is updated after the last write before git gets to it, things\nshould be fine.\n\n> So I think git does a really good job at matching the stat() information,\n> and the suggested patch makes it even stricter, but I think we should not\n> even try to make it handle \"malicious\" changes. I bet you can work at\n> making it miss some update if you really *really* try.\n\nDefinitely. e.g. rig the mtime by 2^32 seconds, or add 2^32 bytes to a\nfile within a second.\n\n> And I think there is one known race: the index mtime itself is not\n> race-free. Remember: it may take more than a second to write the index\n> file! So I can imagine that if you can set it up so that you change the\n> file as the index is written out, and the index write is delayed\n> sufficiently, the racy timestamp logic can fail just because the timestamp\n> on the index file ends up being later.\n\nI had thought about this. I hacked some code up where the index looks\nat the current system time when updating a cache entry to determine if\nthe hash is racy. Is doing one time(NULL) call per file reasonable?\nI'm guessing it must be cheaper that a stat call.\n\n> This is more easily shown by doing a 'touch' on the index file afterwards,\n> of course.\n\nAgreed. Another assumption of my proof is that the index is\ntrustworthy. If you tamper with it, all bets are off. You can't stop\ndetermined users from hurting themselves.\n\n> And yes, we should have written the timestamp to the file itself, instead\n> of reading it from the filesystem.\n\nInteresting. I had hacked a version of the index that did this (before\nchanging it to use a different solution).\n\nIn general, is the format of the index file set in stone? Is that why\nit's better to use the size zero trick for the race condition rather\nthan introduce a new flag for example? Or are these wrinkles too small\nto justify a potentially painful upgrade?\n\n-Ben\n"},{"id":"79403","messageId":"7v1w34dfn3.fsf@gitster.siamese.dyndns.org","threadId":"13880","inReplyTo":"832adb090806101609q17a21948nb5814c3b22bd832d@mail.gmail.com","subject":"Re: git bugs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-06-10T23:38:56Z","receivedAt":"2008-06-10T23:38:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Ben Lynn\" <benlynn@gmail.com> writes:\n\n> I had thought about this. I hacked some code up where the index looks\n> at the current system time when updating a cache entry to determine if\n> the hash is racy. Is doing one time(NULL) call per file reasonable?\n> I'm guessing it must be cheaper that a stat call.\n\nHmm, sorry, could you elaborate how you would plan to use the return value\nfrom time(2) per file?\n\nThe \"index file timestamp\" trick assumes that once we start reading from\nand writing to the filesystem (in order to hash the current contents,\ncheck if there is any modification), nobody else touches the paths we are\ninterested in (e.g., after \"read-tree -m -u\" checks out the new contents,\ngrabs the stat information from the newly deposited file and stuffs that\nin the index, you do not go in and edit it further until our process\nreturns the control to you).  We also assume that the files (both work\ntree and the index) live in the same filesystem and the file timestamp,\nwhich could be skewed compared to the system clock if the filesystem is\nover the network, are consistent among them and monotonicly increasing.\n\n        You have to have some assumption --- if you allow anybody to touch\n        anything behind your back, or if you allow timestamps of some\n        files come from different time sources than the one for some other\n        files, I do not think any lstat(2) based change detection scheme\n        would work.\n\nWe do our writeout first and then the index is updated after all our\nwriteout is done, so by definition (more precisely, \"by that assumption\"),\nanything older than the timestamp of the index file are up to date, if\ntheir filesystem timestamp match the timestamp recorded in the index, and\nanything that is the same or newer than the index timestamp is suspect.\n\nAnd that is the reason the current code gets by only with a single\ntimestamp.  I'd have to go back and study your breakage scenario a bit\nbetter (I'm still at work today).\n"},{"id":"79404","messageId":"832adb090806101702l79aba80cvba1eaab029e9ecd5@mail.gmail.com","threadId":"13880","inReplyTo":"7v1w34dfn3.fsf@gitster.siamese.dyndns.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T00:02:31Z","receivedAt":"2008-06-11T00:02:31Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":">> I had thought about this. I hacked some code up where the index looks\n>> at the current system time when updating a cache entry to determine if\n>> the hash is racy. Is doing one time(NULL) call per file reasonable?\n>> I'm guessing it must be cheaper that a stat call.\n>\n> Hmm, sorry, could you elaborate how you would plan to use the return value\n> from time(2) per file?\n\nMy bad, I was extremely unclear. I meant I had thought about not\nbothering to look at the index file timestamp (I'm not sure why, but I\ninstinctively trust the system clock more!). I'm making the same\nassumptions, i.e. files are not touched while they're being indexed. I\nsuppose with the way I'm doing things, you can touch a file right up\nto the point where the index wants to stat that particular file and\nmaybe look at its contents, but not afterwards. (And this is pretty\nuseless, because how are you going to know which file the index is up\nto?)\n\nI maintain a flag per file, and after computing its SHA1, I compare\nthe mtime with the current system time. If it matches, then that means\nthe hash can't be trusted (because of the race condition) and I set\nthe flag. This way, I avoid examining the index timestamp.\n\nI call time(NULL) for each file out of laziness. I could cache the\nvalue somewhere the first time, but that means I'd have to pass around\nan extra argument to a whole bunch of functions, because of the way\nI've written my code. But I don't think it's much of a drawback,\nbecause I stat() each file anyway.\n\nActually, what Linus describes would be desirable in some sense. If\nthe index mtime timestamp were always later than the time you\nperformed the indexing (and accurate) because it always took a long\ntime, assuming no one messes with files while you're indexing, there\nwould be no race condition to worry about.\n\n-Ben\n"},{"id":"79405","messageId":"7vwskwbz63.fsf@gitster.siamese.dyndns.org","threadId":"13880","inReplyTo":"832adb090806101702l79aba80cvba1eaab029e9ecd5@mail.gmail.com","subject":"Re: git bugs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-06-11T00:20:04Z","receivedAt":"2008-06-11T00:20:04Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Ben Lynn\" <benlynn@gmail.com> writes:\n\n> ... I'm making the same\n> assumptions, i.e. files are not touched while they're being indexed.\n\nActually you are making another assumption that is somewhat worrysome.\n\nThe filesystem clock and time(2) clock can be skewed and comparing a\ntimestamp you obtain from lstat(2) and time(2) might not give you any\nmeaningful information.  That is why I made this codepath without using\ntime(2) when I did the racy-git work.\n"},{"id":"79406","messageId":"832adb090806101724k6199694ftbbc6ed151489a6e3@mail.gmail.com","threadId":"13880","inReplyTo":"7vwskwbz63.fsf@gitster.siamese.dyndns.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T00:24:46Z","receivedAt":"2008-06-11T00:24:46Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"That is problematic. How do I figure out what the filesystem thinks is\nthe current time? I could touch some file and read its mtime, but I\nwant a shortcut.\n\nAre there any guarantees of any kind? e.g. is the filesystem current\ntime at least never ahead of the system time?\n\n-Ben\n\nOn Tue, Jun 10, 2008 at 5:20 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> \"Ben Lynn\" <benlynn@gmail.com> writes:\n>\n>> ... I'm making the same\n>> assumptions, i.e. files are not touched while they're being indexed.\n>\n> Actually you are making another assumption that is somewhat worrysome.\n>\n> The filesystem clock and time(2) clock can be skewed and comparing a\n> timestamp you obtain from lstat(2) and time(2) might not give you any\n> meaningful information.  That is why I made this codepath without using\n> time(2) when I did the racy-git work.\n>\n>\n"},{"id":"79409","messageId":"832adb090806101753m19e76512k6cc3f93aecc2599c@mail.gmail.com","threadId":"13880","inReplyTo":"832adb090806101724k6199694ftbbc6ed151489a6e3@mail.gmail.com","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T00:53:40Z","receivedAt":"2008-06-11T00:53:40Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"Also, without using the time(2) call, how would we write the timestamp\nof the index to the file as Linus suggests? I'm guessing we'd write\nit, then read its mtime, and the write it again (just the part storing\nthe timestamp), but that seems inelegant. In addition, the second\nwrite may happen in the next second and you'll get an mtime different\nto that in the file, though that shouldn't matter.\n\n-Ben\n\nOn Tue, Jun 10, 2008 at 5:24 PM, Ben Lynn <benlynn@gmail.com> wrote:\n> That is problematic. How do I figure out what the filesystem thinks is\n> the current time? I could touch some file and read its mtime, but I\n> want a shortcut.\n>\n> Are there any guarantees of any kind? e.g. is the filesystem current\n> time at least never ahead of the system time?\n>\n> -Ben\n>\n> On Tue, Jun 10, 2008 at 5:20 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>> \"Ben Lynn\" <benlynn@gmail.com> writes:\n>>\n>>> ... I'm making the same\n>>> assumptions, i.e. files are not touched while they're being indexed.\n>>\n>> Actually you are making another assumption that is somewhat worrysome.\n>>\n>> The filesystem clock and time(2) clock can be skewed and comparing a\n>> timestamp you obtain from lstat(2) and time(2) might not give you any\n>> meaningful information.  That is why I made this codepath without using\n>> time(2) when I did the racy-git work.\n>>\n>>\n>\n"},{"id":"79413","messageId":"alpine.LFD.1.10.0806101834460.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806101702l79aba80cvba1eaab029e9ecd5@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-11T01:36:18Z","receivedAt":"2008-06-11T01:36:18Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 10 Jun 2008, Ben Lynn wrote:\n> \n> I call time(NULL) for each file out of laziness. I could cache the\n> value somewhere the first time, but that means I'd have to pass around\n> an extra argument to a whole bunch of functions, because of the way\n> I've written my code. But I don't think it's much of a drawback,\n> because I stat() each file anyway.\n\nNo, that would be horrible. There is no guarantee that time() has \nanything to do with the stat timestamps anyway. \n\nThe right way to do things would be to just do a stat() on the index file \nas it is created, and then save the mtime of that stat into the file. That \nway, you have the mtime of the index file not for the *last* write, but \nfor the *first* one.\n\n\t\tLinus\n"},{"id":"79420","messageId":"832adb090806101904k5eba3bd6p277c955b1782afbe@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806101834460.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T02:04:33Z","receivedAt":"2008-06-11T02:04:33Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"> The right way to do things would be to just do a stat() on the index file\n> as it is created, and then save the mtime of that stat into the file. That\n> way, you have the mtime of the index file not for the *last* write, but\n> for the *first* one.\n\nSorry, but if we're assuming no one is touching the files while we're\nupdating the index (including writing it to disk), why does it matter\nwhether we use the time of first or last write? In fact, if a index\nwrite takes a long time, using the last write time as the mtime would\nbe beneficial for the race condition stuff.\n\n-Ben\n"},{"id":"79423","messageId":"alpine.LFD.1.10.0806101909430.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806101904k5eba3bd6p277c955b1782afbe@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-11T02:12:28Z","receivedAt":"2008-06-11T02:12:28Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 10 Jun 2008, Ben Lynn wrote:\n> \n> Sorry, but if we're assuming no one is touching the files while we're\n> updating the index (including writing it to disk), why does it matter\n> whether we use the time of first or last write? In fact, if a index\n> write takes a long time, using the last write time as the mtime would\n> be beneficial for the race condition stuff.\n\nOh, if you assume nobody is touching the files as the index is created, \nnone of this matters. \n\nSo if *that* was your only race worry, then git should already be \nperfectly fine.\n\nThe issue with the timestamp of the index only happens if somebody ends up \nmodifying the files that are being indexed _as_ they are indexed. Quite \nfrankly, git will notice that too in just about all possible cases, but if \nthe size stays the same and the modification time ends up still being \nsmaller than the final index mtime (because writing the index took so \nlong!), then you might miss some modifications that would otherwise be \nnoticed.\n\n\t\tLinus\n"},{"id":"79424","messageId":"832adb090806101931y754fa6b7nfcb58a9c34f0c582@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806101909430.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T02:31:25Z","receivedAt":"2008-06-11T02:31:25Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"Ah, I hadn't seen that. Yes, it is better to use the first write as\nthe timestamp. Would this catch everything? If the filesystem clock is\nmonotonically increasing and consistent then with this setup, you can\ntouch files even as they are being indexed? (Disregarding nonsense\nlike changing sizes by 2^32.)\n\nJust realized I should have paid more attention to Junio's first reply\nto me. My eye had skipped over the paragraph about clock skew, and\nthis caused some confusion. Sorry about all my extra emails!\n\n-Ben\n\nOn Tue, Jun 10, 2008 at 7:12 PM, Linus Torvalds\n<torvalds@linux-foundation.org> wrote:\n>\n>\n> On Tue, 10 Jun 2008, Ben Lynn wrote:\n>>\n>> Sorry, but if we're assuming no one is touching the files while we're\n>> updating the index (including writing it to disk), why does it matter\n>> whether we use the time of first or last write? In fact, if a index\n>> write takes a long time, using the last write time as the mtime would\n>> be beneficial for the race condition stuff.\n>\n> Oh, if you assume nobody is touching the files as the index is created,\n> none of this matters.\n>\n> So if *that* was your only race worry, then git should already be\n> perfectly fine.\n>\n> The issue with the timestamp of the index only happens if somebody ends up\n> modifying the files that are being indexed _as_ they are indexed. Quite\n> frankly, git will notice that too in just about all possible cases, but if\n> the size stays the same and the modification time ends up still being\n> smaller than the final index mtime (because writing the index took so\n> long!), then you might miss some modifications that would otherwise be\n> noticed.\n>\n>                Linus\n>\n"},{"id":"79425","messageId":"alpine.LFD.1.10.0806101935130.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806101931y754fa6b7nfcb58a9c34f0c582@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-11T02:39:16Z","receivedAt":"2008-06-11T02:39:16Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 10 Jun 2008, Ben Lynn wrote:\n>\n> Ah, I hadn't seen that. Yes, it is better to use the first write as\n> the timestamp. Would this catch everything? If the filesystem clock is\n> monotonically increasing and consistent then with this setup, you can\n> touch files even as they are being indexed? (Disregarding nonsense\n> like changing sizes by 2^32.)\n\nYes, I think that at that point it would protect against arbitrary \nmodifications even concurrently to index file creation.\n\nThat said, I don't think you even need a new index file format. We could \njust do a stat() on starting the index file creation, and then do a \nfutimes() system call at the end to re-set the mtime to the beginning \nbefore we rename it back over the old index file.\n\n\t\tLinus\n"},{"id":"79431","messageId":"832adb090806102258v3fd63605p8c45513690b78fe8@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806101935130.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T05:58:15Z","receivedAt":"2008-06-11T05:58:15Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"Am I going crazy? All of a sudden I think I can get away without a\nsize zero hack. How about this smudging routine:\n\nif (!ce_match_stat_basic(ce, &st)) {\n  recompute_sha1_and_update_index();  // no other checks required\n}\n\nThat should be sufficient. I think what happened was the following.\nOnce upon a time, the race fix was \"if (stats_match) cached_size = 0\",\nwhich is nice because you don't have to examine file contents. Later,\nbecause of the\n\n $ echo xyzzy >frotz ; git-update-index --add frotz ; : >frotz\n $ sleep 3\n $ echo filfre >nitfol ; git-update-index --add nitfol\n\nissue, the ce_modified_check_fs was added.\n\nBut then if we're going to be examining file contents anyway, we may\nas well drop the whole size zero trick and simply update the hash. The\nbug I brought up also goes away.\n\n-Ben\n\nP.S: I could go through the history to see, but I bet there was a\nstage after the race condition was discovered but before it was\nrealized that\n  $ git update-index 'foo'\n  : modify 'foo' in-place without changing its size\n  : wait for enough time\n  $ git update-index 'bar'\nwas a problem.\n\nOn Tue, Jun 10, 2008 at 7:39 PM, Linus Torvalds\n<torvalds@linux-foundation.org> wrote:\n>\n>\n> On Tue, 10 Jun 2008, Ben Lynn wrote:\n>>\n>> Ah, I hadn't seen that. Yes, it is better to use the first write as\n>> the timestamp. Would this catch everything? If the filesystem clock is\n>> monotonically increasing and consistent then with this setup, you can\n>> touch files even as they are being indexed? (Disregarding nonsense\n>> like changing sizes by 2^32.)\n>\n> Yes, I think that at that point it would protect against arbitrary\n> modifications even concurrently to index file creation.\n>\n> That said, I don't think you even need a new index file format. We could\n> just do a stat() on starting the index file creation, and then do a\n> futimes() system call at the end to re-set the mtime to the beginning\n> before we rename it back over the old index file.\n>\n>                Linus\n>\n"},{"id":"79434","messageId":"832adb090806102318k5727bb06p6c3211a6aebbfbe9@mail.gmail.com","threadId":"13880","inReplyTo":"832adb090806102258v3fd63605p8c45513690b78fe8@mail.gmail.com","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T06:18:49Z","receivedAt":"2008-06-11T06:18:49Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"And I'm sure you've also realized we could use the old race fix with\nSIZE_MAX instead of zero, i.e:\n\n if (!ce_match_stat_basic(ce, &st)) {\n   ce->ce_size = ~0;\n }\n return; // don't bother with ce_modified_check_fs\n\nThis is dissatisfying in that we're abusing the size variable. I'd\nmuch prefer adding a flag per entry. And now there are other file\nsizes, albeit ridiculously large ones, that will trick git. But it is\nmuch faster than examining file contents. Luckily the decision of\nwhich fix to use is not up to me.\n\n-Ben\n\nOn Wed, Jun 11, 2008 at 5:58 AM, Ben Lynn <benlynn@gmail.com> wrote:\n> Am I going crazy? All of a sudden I think I can get away without a\n> size zero hack. How about this smudging routine:\n>\n> if (!ce_match_stat_basic(ce, &st)) {\n>  recompute_sha1_and_update_index();  // no other checks required\n> }\n>\n> That should be sufficient. I think what happened was the following.\n> Once upon a time, the race fix was \"if (stats_match) cached_size = 0\",\n> which is nice because you don't have to examine file contents. Later,\n> because of the\n>\n>  $ echo xyzzy >frotz ; git-update-index --add frotz ; : >frotz\n>  $ sleep 3\n>  $ echo filfre >nitfol ; git-update-index --add nitfol\n>\n> issue, the ce_modified_check_fs was added.\n>\n> But then if we're going to be examining file contents anyway, we may\n> as well drop the whole size zero trick and simply update the hash. The\n> bug I brought up also goes away.\n>\n> -Ben\n>\n> P.S: I could go through the history to see, but I bet there was a\n> stage after the race condition was discovered but before it was\n> realized that\n>  $ git update-index 'foo'\n>  : modify 'foo' in-place without changing its size\n>  : wait for enough time\n>  $ git update-index 'bar'\n> was a problem.\n>\n> On Tue, Jun 10, 2008 at 7:39 PM, Linus Torvalds\n> <torvalds@linux-foundation.org> wrote:\n>>\n>>\n>> On Tue, 10 Jun 2008, Ben Lynn wrote:\n>>>\n>>> Ah, I hadn't seen that. Yes, it is better to use the first write as\n>>> the timestamp. Would this catch everything? If the filesystem clock is\n>>> monotonically increasing and consistent then with this setup, you can\n>>> touch files even as they are being indexed? (Disregarding nonsense\n>>> like changing sizes by 2^32.)\n>>\n>> Yes, I think that at that point it would protect against arbitrary\n>> modifications even concurrently to index file creation.\n>>\n>> That said, I don't think you even need a new index file format. We could\n>> just do a stat() on starting the index file creation, and then do a\n>> futimes() system call at the end to re-set the mtime to the beginning\n>> before we rename it back over the old index file.\n>>\n>>                Linus\n>>\n>\n"},{"id":"79446","messageId":"20080611124634.GA26729@cuci.nl","threadId":"13880","inReplyTo":"832adb090806101724k6199694ftbbc6ed151489a6e3@mail.gmail.com","subject":"Re: git bugs","fromName":"Stephen R. van den Berg","fromEmail":"srb@cuci.nl","sentAt":"2008-06-11T12:46:34Z","receivedAt":"2008-06-11T12:46:34Z","isPatch":false,"sender":{"key":"srb@cuci.nl","avatar":"https://gravatar.com/avatar/f75389059e827634d38e9df2a9b6ecbd50028b5a454442efa1c7205b7ff29c6a?d=mp&s=160"},"body":"Ben Lynn wrote:\n>That is problematic. How do I figure out what the filesystem thinks is\n>the current time? I could touch some file and read its mtime, but I\n>want a shortcut.\n\nThat basically is as short as it gets, except perhaps statting a freshly\nmodified file (not necessarily by oneself).\n\n>Are there any guarantees of any kind? e.g. is the filesystem current\n>time at least never ahead of the system time?\n\nPractically no guarantees, just that it is rather likely for the time at\nthe fileserver to progress at about the same pace as yours.\n-- \nSincerely,\n           Stephen R. van den Berg.\n\nDifferentiation is an integral part of calculus.\n"},{"id":"79453","messageId":"alpine.LFD.1.10.0806110749230.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806102258v3fd63605p8c45513690b78fe8@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-11T14:52:05Z","receivedAt":"2008-06-11T14:52:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 10 Jun 2008, Ben Lynn wrote:\n>\n> Am I going crazy? All of a sudden I think I can get away without a\n> size zero hack. How about this smudging routine:\n> \n> if (!ce_match_stat_basic(ce, &st)) {\n>   recompute_sha1_and_update_index();  // no other checks required\n> }\n\nNo.\n\nYou can't recompute the sha1. That SHA1 is what the user asked us to \nremember - whether smudged or not. So you mustn't change it, until the \nuser does a \"git add\" or \"git update-index\" (or anything that implicitly \ndoes the same).\n\nYou can change the _stat_ information, since that is only used for \nmatching the tree (positively or negatively), but the SHA1 itself is not \njust a cache, it's the \"pending state\" in the index.\n\nSo smudging must change some piece of data that is only about the stat \ncache - the st_size, the mtime, anything like that.\n\n\t\t\tLinus\n"},{"id":"79454","messageId":"alpine.LFD.1.10.0806110752550.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806102318k5727bb06p6c3211a6aebbfbe9@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-11T14:54:23Z","receivedAt":"2008-06-11T14:54:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 11 Jun 2008, Ben Lynn wrote:\n>\n> But it is much faster than examining file contents.\n\nI'm not sure why you think my patch that just did the zero-sized blob \nthing was slow? It's a 20-byte memcmp(). It takes no time at all. \n\n\t\tLinus\n"},{"id":"79468","messageId":"832adb090806111052p32a750c2n5f2d43e0ed1b910d@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806110752550.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T17:52:32Z","receivedAt":"2008-06-11T17:52:32Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"> I'm not sure why you think my patch that just did the zero-sized blob\n> thing was slow? It's a 20-byte memcmp(). It takes no time at all.\n\nI don't think the memcmp is slow. I think the ce_modified_check_fs in:\n\nsmudge() {\n   ...\n  if (ce_match_stat_basic(ce, &st))\n                return;\n  if (ce_modified_check_fs(ce, &st))\n                ce->ce_size = 0;\n}\n\nis potentially slow, and I'm saying you could replace it with\n\nsmudge() {\n   ...\n  if (ce_match_stat_basic(ce, &st))\n                return;\n  ce->ce_size = ~0;\n}\n\nto avoid the ce_modified_check_fs call. But it is an unclean solution,\nwhich is why I champion having an extra flag per file.\n\nAlso, I think we could set ce->ce_size to ~0 when we first realize\ntimestamp = mtime, and we'd no longer have to do index-wide smudging\non writes.\n\nThanks for the explanation by the way. I get why you can't modify the\nSHA1. It is indeed what we asked git to record, right or wrong. I got\nconfused because I misread the code and thought ce_modified_check_fs()\nwould write the new SHA1 to disk.\n\n-Ben\n"},{"id":"79471","messageId":"alpine.LFD.1.10.0806111105150.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806111052p32a750c2n5f2d43e0ed1b910d@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-11T18:10:34Z","receivedAt":"2008-06-11T18:10:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 11 Jun 2008, Ben Lynn wrote:\n> \n> I don't think the memcmp is slow. I think the ce_modified_check_fs in:\n> \n> smudge() {\n>    ...\n>   if (ce_match_stat_basic(ce, &st))\n>                 return;\n>   if (ce_modified_check_fs(ce, &st))\n>                 ce->ce_size = 0;\n> }\n> \n> is potentially slow, and I'm saying you could replace it with\n> \n> smudge() {\n>    ...\n>   if (ce_match_stat_basic(ce, &st))\n>                 return;\n>   ce->ce_size = ~0;\n> }\n> \n> to avoid the ce_modified_check_fs call. But it is an unclean solution,\n> which is why I champion having an extra flag per file.\n\nWell, you have to think about what you want to optimize here.\n\nThe thing we want to optimize is not the writing of the index file, but \nthe subsequent _use_ of it!\n\nAs such, the last thing we actually want to do is to smudge the index file \nentry. If it actually has a possibility of being not smudged, we're much \nbetter off saying \"hey, now the index file is newer, and the file it \nrefers to is all good!\"\n\nThat way, we won't have to do the ce_modified_check_fs() call later - we \ndo it just once, and the file is up-to-date.\n\nSo we don't want to smudge it, but if the stat information says it migth \nmatch even though it doesn't, we have to. But if the stat information says \nit matches, and the data actually _does_ match, then we shouldn't smudge \nit, we should be happy - and all subsequent users of the index will then \nknow that they don't even need to look at the file contents.\n\n\t\t\tLinus\n"},{"id":"79479","messageId":"832adb090806111148u5e13e9c5g7afc5b013e6f1223@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806111105150.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T18:48:10Z","receivedAt":"2008-06-11T18:48:10Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"> So we don't want to smudge it, but if the stat information says it migth\n> match even though it doesn't, we have to. But if the stat information says\n> it matches, and the data actually _does_ match, then we shouldn't smudge\n> it, we should be happy - and all subsequent users of the index will then\n> know that they don't even need to look at the file contents.\n\nI understand. In that case, what about an unsmudging routine so we can\nhave the best of both worlds? We unconditionally smudge the file as\nsoon as timestamp = mtime is detected. We never do index-wide smudging\non writes, but rather, on index read of particular file we do this:\n\n  if (stats_differ()) {\n    if (hash_matches()) {\n      // Aha! An unconditionally smudged file that we might be able to unsmudge,\n      // so future reads can avoid this check.\n      if (mtime < timestamp) {\n        fix_stats();  // Involves writing to index.\n      }\n      // D'oh! This file could still be racy, leave it smudged.\n    } else {\n      // The stats were right, the hash does differ.\n      ...\n    }\n  }\n\nWe minimize the amount of ce_check_modified_fs() calls for any given\nsequence of index operations. Instead of doing index-wide checks on\nevery write, we only check when we have no choice, i.e. the first time\na particular file is being looked up in the index. We fix its stats if\npossible so future reads can avoid the painful check. The only\ndrawback is that I'm not sure how acceptable it is to write to the\nindex on a read operation. Is this a big deal? (If it were a separate\nflag, I'm sure no one would mind!)\n\n-Ben\n"},{"id":"79480","messageId":"alpine.LFD.1.10.0806111151260.3101@woody.linux-foundation.org","threadId":"13880","inReplyTo":"832adb090806111148u5e13e9c5g7afc5b013e6f1223@mail.gmail.com","subject":"Re: git bugs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-06-11T18:53:27Z","receivedAt":"2008-06-11T18:53:27Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 11 Jun 2008, Ben Lynn wrote:\n>\n> The only drawback is that I'm not sure how acceptable it is to write to \n> the index on a read operation. Is this a big deal?\n\nHistorically, we *never* did it. In fact, it was a big deal. These days we \ndo it opportunistically for \"git diff\" if we can, but making sure that it \nall still works for a read-only access (think gitweb etc - the reader is \n*not* necessarily the owner of the archive at all!)\n\nSo I really prefer not to. But you can take it up with Junio if you think \nit can be a big deal.\n\n\t\tLinus\n"},{"id":"79502","messageId":"832adb090806111357y749a4e03qbddd37b0c077b1c4@mail.gmail.com","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806111151260.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-11T20:57:50Z","receivedAt":"2008-06-11T20:57:50Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"> So I really prefer not to. But you can take it up with Junio if you think\n> it can be a big deal.\n\nI began writing a patch but I abandoned it. I don't have much\nexperience with the code base and I'd almost certainly miss a bunch of\ncorner cases. Your patch seems to be the easiest way to go. I'm not\nmotivated to push pre-emptive smudging, even if it might be more\nefficient. After all, how often does this race condition come up?\n\nBut I have a per-file flagged version of the index for personal use,\nand it's good to know that it's a valid strategy.\n\n> Historically, we *never* did it. In fact, it was a big deal. These days we\n> do it opportunistically for \"git diff\" if we can, but making sure that it\n> all still works for a read-only access (think gitweb etc - the reader is\n> *not* necessarily the owner of the archive at all!)\n\nI hadn't thought about this case. This is intriguing: why does gitweb\nneed access to the index? I thought the index was only to make\noperations fast for users intending to make changes to the repo. Why\ncan't servers run stripped-down versions of git that don't bother with\nan index?\n\n-Ben\n"},{"id":"79513","messageId":"7viqwfbpzs.fsf@gitster.siamese.dyndns.org","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806111151260.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-06-11T21:50:31Z","receivedAt":"2008-06-11T21:50:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Wed, 11 Jun 2008, Ben Lynn wrote:\n>>\n>> The only drawback is that I'm not sure how acceptable it is to write to \n>> the index on a read operation. Is this a big deal?\n>\n> Historically, we *never* did it. In fact, it was a big deal. These days we \n> do it opportunistically for \"git diff\" if we can, but making sure that it \n> all still works for a read-only access (think gitweb etc - the reader is \n\nThanks for giving a good summary (I've been away), and I agree with your\nanalysis of the situation.  I do not see much need to _fix_ anything\naround this area, except your \"smudging is not zero timestamp\" update.\n"},{"id":"79534","messageId":"20080612031723.GJ11793@spearce.org","threadId":"13880","inReplyTo":"832adb090806100141n69c086a2v2f59fe94b2f4ead3@mail.gmail.com","subject":"Re: git bugs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-06-12T03:17:23Z","receivedAt":"2008-06-12T03:17:23Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ben Lynn <benlynn@gmail.com> wrote:\n> 1. The import/export language poorly handles distinct initial commits\n> on the same branch, because given two commits with same branch name,\n> it assumes the latter is the descendant of the former (if there are no\n> \"from\" commands).\n> \n> Normally this is what you want. But if your project, like git, ever\n> merges distinct initial commits, then all but the first will\n> unexpectedly gain parents, corrupting all their descendants' hashes.\n...\n> As a workaround, I have a custom importer that knows that\n> git-fast-export omits the \"from\" command in initial commits. But there\n> should be a command to specify that the current commit is an initial\n> commit, allowing reliable export of projects such as git.\n\nfast-export is wrong, and is using the language wrong.  fast-import\nis correct.  Because I said so.  :-)\n\nNo, seriously, fast-import came along first and can describe what\nyou are referring to as the many initial root commits in git.git.\nThe issue is fast-export is not generating commands to say as much.\n\nIts quite easily fixable.\n\nWhen we output a commit in handle_commit() we just need to reset\nthe branch if we have no parents.  That simple.  This is totally\nuntested, but I think it fixes it.\n\n\ndiff --git a/builtin-fast-export.c b/builtin-fast-export.c\nindex 1dfc01e..d0a462f 100644\n--- a/builtin-fast-export.c\n+++ b/builtin-fast-export.c\n@@ -188,6 +188,8 @@ static void handle_commit(struct commit *commit, struct rev_info *rev)\n \tmark_object(&commit->object);\n \tif (!is_encoding_utf8(encoding))\n \t\treencoded = reencode_string(message, \"UTF-8\", encoding);\n+\tif (!commit->parents)\n+\t\tprintf(\"reset %s\\n\", (const char*)commit->util);\n \tprintf(\"commit %s\\nmark :%d\\n%.*s\\n%.*s\\ndata %u\\n%s\",\n \t       (const char *)commit->util, last_idnum,\n \t       (int)(author_end - author), author,\n\n-- \nShawn.\n"},{"id":"79564","messageId":"832adb090806112346r12c34d2bibf822f8422b349c5@mail.gmail.com","threadId":"13880","inReplyTo":"20080612031723.GJ11793@spearce.org","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-12T06:46:23Z","receivedAt":"2008-06-12T06:46:23Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"Thanks! I just tested it on the example I quoted before, and it works.\nI misunderstood the reset command. I thought it took you to some\nprevious commit. But now I see it takes you back to before the initial\ncommit if you don't use the \"from\" command.\n\n-Ben\n\nOn Wed, Jun 11, 2008 at 8:17 PM, Shawn O. Pearce <spearce@spearce.org> wrote:\n> Ben Lynn <benlynn@gmail.com> wrote:\n>> 1. The import/export language poorly handles distinct initial commits\n>> on the same branch, because given two commits with same branch name,\n>> it assumes the latter is the descendant of the former (if there are no\n>> \"from\" commands).\n>>\n>> Normally this is what you want. But if your project, like git, ever\n>> merges distinct initial commits, then all but the first will\n>> unexpectedly gain parents, corrupting all their descendants' hashes.\n> ...\n>> As a workaround, I have a custom importer that knows that\n>> git-fast-export omits the \"from\" command in initial commits. But there\n>> should be a command to specify that the current commit is an initial\n>> commit, allowing reliable export of projects such as git.\n>\n> fast-export is wrong, and is using the language wrong.  fast-import\n> is correct.  Because I said so.  :-)\n>\n> No, seriously, fast-import came along first and can describe what\n> you are referring to as the many initial root commits in git.git.\n> The issue is fast-export is not generating commands to say as much.\n>\n> Its quite easily fixable.\n>\n> When we output a commit in handle_commit() we just need to reset\n> the branch if we have no parents.  That simple.  This is totally\n> untested, but I think it fixes it.\n>\n>\n> diff --git a/builtin-fast-export.c b/builtin-fast-export.c\n> index 1dfc01e..d0a462f 100644\n> --- a/builtin-fast-export.c\n> +++ b/builtin-fast-export.c\n> @@ -188,6 +188,8 @@ static void handle_commit(struct commit *commit, struct rev_info *rev)\n>        mark_object(&commit->object);\n>        if (!is_encoding_utf8(encoding))\n>                reencoded = reencode_string(message, \"UTF-8\", encoding);\n> +       if (!commit->parents)\n> +               printf(\"reset %s\\n\", (const char*)commit->util);\n>        printf(\"commit %s\\nmark :%d\\n%.*s\\n%.*s\\ndata %u\\n%s\",\n>               (const char *)commit->util, last_idnum,\n>               (int)(author_end - author), author,\n>\n> --\n> Shawn.\n>\n"},{"id":"79565","messageId":"832adb090806112351t44a4495fsa72c0c98e9eab3fd@mail.gmail.com","threadId":"13880","inReplyTo":"20080611124634.GA26729@cuci.nl","subject":"Re: git bugs","fromName":"Ben Lynn","fromEmail":"benlynn@gmail.com","sentAt":"2008-06-12T06:51:17Z","receivedAt":"2008-06-12T06:51:17Z","isPatch":false,"sender":{"key":"benlynn@gmail.com","avatar":"https://gravatar.com/avatar/3183782929c56156a56b88cfae4d728a8dc9137385fe17cf4bbee1faabf9be49?d=mp&s=160"},"body":"Thanks everyone who replied. You know, I was a bit apprehensive about\nposting originally, because I had heard the git ML was inflammable.\nBut all these responses have been prompt, well-thought-out and\ninformative.\n\nI plan to take all these suggestions and have a go at hacking a\nrace-free index which updates successfully despite concurrent file\noperations.\n\nThanks again,\n-Ben\n\nOn Wed, Jun 11, 2008 at 5:46 AM, Stephen R. van den Berg <srb@cuci.nl> wrote:\n> Ben Lynn wrote:\n>>That is problematic. How do I figure out what the filesystem thinks is\n>>the current time? I could touch some file and read its mtime, but I\n>>want a shortcut.\n>\n> That basically is as short as it gets, except perhaps statting a freshly\n> modified file (not necessarily by oneself).\n>\n>>Are there any guarantees of any kind? e.g. is the filesystem current\n>>time at least never ahead of the system time?\n>\n> Practically no guarantees, just that it is rather likely for the time at\n> the fileserver to progress at about the same pace as yours.\n> --\n> Sincerely,\n>           Stephen R. van den Berg.\n>\n> Differentiation is an integral part of calculus.\n>\n"},{"id":"79569","messageId":"alpine.DEB.1.00.0806120811440.1783@racer","threadId":"13880","inReplyTo":"20080612031723.GJ11793@spearce.org","subject":"Re: git bugs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-06-12T07:12:29Z","receivedAt":"2008-06-12T07:12:29Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 11 Jun 2008, Shawn O. Pearce wrote:\n\n> diff --git a/builtin-fast-export.c b/builtin-fast-export.c\n> index 1dfc01e..d0a462f 100644\n> --- a/builtin-fast-export.c\n> +++ b/builtin-fast-export.c\n> @@ -188,6 +188,8 @@ static void handle_commit(struct commit *commit, struct rev_info *rev)\n>  \tmark_object(&commit->object);\n>  \tif (!is_encoding_utf8(encoding))\n>  \t\treencoded = reencode_string(message, \"UTF-8\", encoding);\n> +\tif (!commit->parents)\n> +\t\tprintf(\"reset %s\\n\", (const char*)commit->util);\n>  \tprintf(\"commit %s\\nmark :%d\\n%.*s\\n%.*s\\ndata %u\\n%s\",\n>  \t       (const char *)commit->util, last_idnum,\n>  \t       (int)(author_end - author), author,\n\nDeemed-obviously-correct-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n\nCiao,\nDscho\n"},{"id":"79621","messageId":"7v4p7y1kqu.fsf@gitster.siamese.dyndns.org","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806101028040.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-06-12T20:06:17Z","receivedAt":"2008-06-12T20:06:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> The other approach is to know that an empty blob always has a very \n> specific SHA1. Here's an trial patch.\n\n>  read-cache.c |   16 ++++++++++++++++\n>  1 files changed, 16 insertions(+), 0 deletions(-)\n>\n> diff --git a/read-cache.c b/read-cache.c\n> index 8e5fbb6..f83de8c 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> ...\n> @@ -193,6 +203,12 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)\n>  \tif (ce->ce_size != (unsigned int) st->st_size)\n>  \t\tchanged |= DATA_CHANGED;\n>  \n> +\t/* Racily smudged entry? */\n> +\tif (!ce->ce_size) {\n> +\t\tif (!is_empty_blob_sha1(ce->sha1))\n> +\t\t\tchanged |= DATA_CHANGED;\n> +\t}\n> +\n>  \treturn changed;\n>  }\n\nThanks.  This would be a good fix to the issue.\n\nThe only theoretical worry I can think of is if there is an insane\nconvert_to_worktree() filter that turns a non-empty blob into an empty\nwork tree file.\n\nAn \"In blobs, always store everything as UTF16 with BOM\" filter, when\nbadly implemented, might turn an empty work tree file into a blob with BOM\nand nothing else in it, but we can safely declare that such use case is\nsimply insane and broken ;-).\n"},{"id":"79702","messageId":"20080613101024.GA8221@sigill.intra.peff.net","threadId":"13880","inReplyTo":"alpine.LFD.1.10.0806101028040.3101@woody.linux-foundation.org","subject":"Re: git bugs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-06-13T10:10:24Z","receivedAt":"2008-06-13T10:10:24Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 10, 2008 at 10:44:43AM -0700, Linus Torvalds wrote:\n\n> You can fix this multiple ways. One would be to pick another size that is \n> simply less likely (eg ~0 instead), which leaves the theoretical race, and \n> just makes it practically impossible to hit (not that I think it's very \n> practical to hit already).\n\nHmm. I may have just hit it in the test suite.\n\nTry this:\n\n  cd git/t\n  for i in `seq 1 1000`; do\n    ./t4126-apply-empty.sh -v -i || break\n  done\n  echo made it to $i\n\nMost of the time it works, but somewhere in that thousand (generally\nwithin a few hundred), I end up with a failed test. The failure looks\nlike:\n\n   * expecting success:\n           git reset --hard &&\n           >empty &&\n           rm -f missing &&\n           git apply --index patch0 &&\n           test_cmp expect empty &&\n           git diff --exit-code\n\n   HEAD is now at e3f79fd initial\n   error: empty: does not match index\n   * FAIL 3: apply --index empty\n\n> The other approach is to know that an empty blob always has a very \n> specific SHA1. Here's an trial patch.\n\nHowever, I can still trigger the failure with your patch, so I wonder if\nit is some other race entirely...\n\n-Peff\n"},{"id":"79792","messageId":"7vbq25j5ke.fsf@gitster.siamese.dyndns.org","threadId":"13880","inReplyTo":"20080613101024.GA8221@sigill.intra.peff.net","subject":"Re: git bugs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-06-13T23:09:05Z","receivedAt":"2008-06-13T23:09:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Jun 10, 2008 at 10:44:43AM -0700, Linus Torvalds wrote:\n>\n>> You can fix this multiple ways. One would be to pick another size that is \n>> simply less likely (eg ~0 instead), which leaves the theoretical race, and \n>> just makes it practically impossible to hit (not that I think it's very \n>> practical to hit already).\n>\n> Hmm. I may have just hit it in the test suite.\n>\n> Try this:\n>\n>   cd git/t\n>   for i in `seq 1 1000`; do\n>     ./t4126-apply-empty.sh -v -i || break\n>   done\n>   echo made it to $i\n>\n> Most of the time it works, but somewhere in that thousand (generally\n> within a few hundred), I end up with a failed test.\n> ...\n> However, I can still trigger the failure with your patch, so I wonder if\n> it is some other race entirely...\n\nThis is not a race but the test itself is simply buggy.\n\nWhen telling apply to affect index and work tree at the same time (that is\nwhat --index means), the caller must make sure that the diff-files won't\nreport stale stat information.\n\nIf \"git reset --hard\" and \">empty\" crossed the second boundary, the reset\nmight have written out an empty \"empty\" with timestamp T and then the\nindependent \">empty\" would have given a new timestamp T+1.\n\nI think \"reset --hard\" without \">empty\" is enough as the head commit\nrecords an empty blob there.\n\n---\n\n t/t4126-apply-empty.sh |    4 ----\n 1 files changed, 0 insertions(+), 4 deletions(-)\n\ndiff --git a/t/t4126-apply-empty.sh b/t/t4126-apply-empty.sh\nindex 0cfd47c..ceb6a79 100755\n--- a/t/t4126-apply-empty.sh\n+++ b/t/t4126-apply-empty.sh\n@@ -26,7 +26,6 @@ test_expect_success setup '\n \n test_expect_success 'apply empty' '\n \tgit reset --hard &&\n-\t>empty &&\n \trm -f missing &&\n \tgit apply patch0 &&\n \ttest_cmp expect empty\n@@ -34,7 +33,6 @@ test_expect_success 'apply empty' '\n \n test_expect_success 'apply --index empty' '\n \tgit reset --hard &&\n-\t>empty &&\n \trm -f missing &&\n \tgit apply --index patch0 &&\n \ttest_cmp expect empty &&\n@@ -43,7 +41,6 @@ test_expect_success 'apply --index empty' '\n \n test_expect_success 'apply create' '\n \tgit reset --hard &&\n-\t>empty &&\n \trm -f missing &&\n \tgit apply patch1 &&\n \ttest_cmp expect missing\n@@ -51,7 +48,6 @@ test_expect_success 'apply create' '\n \n test_expect_success 'apply --index create' '\n \tgit reset --hard &&\n-\t>empty &&\n \trm -f missing &&\n \tgit apply --index patch1 &&\n \ttest_cmp expect missing &&\n"},{"id":"79804","messageId":"20080614062513.GA24508@sigill.intra.peff.net","threadId":"13880","inReplyTo":"7vbq25j5ke.fsf@gitster.siamese.dyndns.org","subject":"Re: git bugs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-06-14T06:25:13Z","receivedAt":"2008-06-14T06:25:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 13, 2008 at 04:09:05PM -0700, Junio C Hamano wrote:\n\n> When telling apply to affect index and work tree at the same time (that is\n> what --index means), the caller must make sure that the diff-files won't\n> report stale stat information.\n\nAh, I had assumed that git-apply would notice the stale stat information\nand fall back to checking the content, which should be accurate.\n\n> I think \"reset --hard\" without \">empty\" is enough as the head commit\n> records an empty blob there.\n\nYes, it is redundant. With your patch I was not able to reproduce the\nproblem over a few thousand trials.\n\n-Peff\n"}]}