{"thread":{"id":"34804","subject":"[PATCH] has_sha1_file: re-check pack directory before giving up","startedAt":"2013-08-30T01:10:53Z","lastAt":"2013-08-30T19:14:13Z","messageCount":6,"participants":["Jeff King","Eric Sunshine","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"226286","messageId":"20130830011052.GA21895@sigill.intra.peff.net","threadId":"34804","inReplyTo":null,"subject":"[PATCH] has_sha1_file: re-check pack directory before giving up","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-30T01:10:53Z","receivedAt":"2013-08-30T01:10:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we read a sha1 file, we first look for a packed\nversion, then a loose version, and then re-check the pack\ndirectory again before concluding that we cannot find it.\nThis lets us handle a process that is writing to the\nrepository simultaneously (e.g., receive-pack writing a new\npack followed by a ref update, or git-repack packing\nexisting loose objects into a new pack).\n\nHowever, we do not do the same trick with has_sha1_file; we\nonly check the packed objects once, followed by loose\nobjects. This means that we might incorrectly report that we\ndo not have an object, even though we could find it if we\nsimply re-checked the pack directory.\n\nBy itself, this is usually not a big deal. The other process\nis running simultaneously, so we may run has_sha1_file\nbefore it writes, anyway. It is a race whether we see the\nobject or not.  However, we may also see other things\nthe writing process has done (like updating refs); and in\nthat case, we must be able to also see the new objects.\n\nFor example, imagine we are doing a for_each_ref iteration,\nand somebody simultaneously pushes. Receive-pack may write\nthe pack and update a ref after we have examined the\nobjects/pack directory, but before the iteration gets to the\nupdated ref. When we do finally see the updated ref,\nfor_each_ref will call has_sha1_file to check whether the\nref is broken. If has_sha1_file returns the wrong answer, we\nerroneously will think that the ref is broken.\n\nIn the case of git-fsck, which uses the\nDO_FOR_EACH_INCLUDE_BROKEN flag, this will cause us to\nerroneously complain that the ref points to an invalid\nobject. But for git-repack, which does not use that flag, we\nwill skip the ref completely! So not only will we fail to\nprocess the new objects that the ref points to (which is\nacceptabale, since the processes are running simultaneously,\nand we might well do our whole repack before the other\nprocess updates the ref), but we will not see the ref at\nall. Its old objects may be omitted from the pack (and even\nlost, if --unpack-unreachable is used with an expiration\ntime).\n\nThere's no test included here, because the success case is\ntwo processes running simultaneously forever. But you can\nreplicate the issue with:\n\n  # base.sh\n  # run this in one terminal; it creates and pushes\n  # repeatedly to a repository\n  git init parent &&\n  (cd parent &&\n\n    # create a base commit that will trigger us looking at\n    # the objects/pack directory before we hit the updated ref\n    echo content >file &&\n    git add file &&\n    git commit -m base &&\n\n    # set the unpack limit abnormally low, which\n    # lets us simulate full-size pushes using tiny ones\n    git config receive.unpackLimit 1\n  ) &&\n  git clone parent child &&\n  cd child &&\n  n=0 &&\n  while true; do\n    echo $n >file && git add file && git commit -m $n &&\n    git push origin HEAD:refs/remotes/child/master &&\n    n=$(($n + 1))\n  done\n\n  # fsck.sh\n  # now run this simultaneously in another terminal; it\n  # repeatedly fscks, looking for us to consider the\n  # newly-pushed ref broken.\n  cd parent &&\n  while true; do\n    broken=`git fsck 2>&1 | grep remotes/child`\n    if test -n \"$broken\"; then\n      echo $broken\n      exit 1\n    fi\n  done\n\nWithout this patch, the fsck loop fails within a few seconds\n(and almost instantly if the test repository actually has a\nlarge number of refs). With it, the two can run\nindefinitely.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI observed this being triggered in practice on a repository with a large\nnumber of refs. Clients complained of refs being reported as bogus by\nthe server and being omitted (because of upload-pack missing the ref in\nthe advertisement), and git-fsck would randomly report breakages (that\nwould then go away if run again). I didn't observe any object loss as I\ntheorized above, but I'm pretty sure it's possible (ironically, _not_\nthe new objects, because they will be newer than the prune time, but the\nold objects they are based on).\n\nNote that this works against the optimization in b495697 (fetch-pack:\navoid repeatedly re-scanning pack directory, 2013-01-26), which uses\nhas_sha1_file specifically to avoid the re-scan. But it is much more\nimportant to be correct here, so I'd like to start with this fix. For\nthe use case in b495697, we can have a \"quick but occasionally wrong\"\nversion.\n\n sha1_file.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 8e27db1..06784fb 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2925,7 +2925,10 @@ int has_sha1_file(const unsigned char *sha1)\n \n \tif (find_pack_entry(sha1, &e))\n \t\treturn 1;\n-\treturn has_loose_object(sha1);\n+\tif (has_loose_object(sha1))\n+\t\treturn 1;\n+\treprepare_packed_git();\n+\treturn find_pack_entry(sha1, &e);\n }\n \n static void check_tree(const void *buf, size_t size)\n-- \n1.8.4.2.g87d4a77\n"},{"id":"226287","messageId":"CAPig+cQnD3bUA5qdvMGCLuC3f0-+EcSbHrnqxBqEhaYRX3wDxQ@mail.gmail.com","threadId":"34804","inReplyTo":"20130830011052.GA21895@sigill.intra.peff.net","subject":"Re: [PATCH] has_sha1_file: re-check pack directory before giving up","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-08-30T01:40:32Z","receivedAt":"2013-08-30T01:40:32Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Thu, Aug 29, 2013 at 9:10 PM, Jeff King <peff@peff.net> wrote:\n> When we read a sha1 file, we first look for a packed\n> version, then a loose version, and then re-check the pack\n> directory again before concluding that we cannot find it.\n> This lets us handle a process that is writing to the\n> repository simultaneously (e.g., receive-pack writing a new\n> pack followed by a ref update, or git-repack packing\n> existing loose objects into a new pack).\n>\n> However, we do not do the same trick with has_sha1_file; we\n> only check the packed objects once, followed by loose\n> objects. This means that we might incorrectly report that we\n> do not have an object, even though we could find it if we\n> simply re-checked the pack directory.\n>\n> By itself, this is usually not a big deal. The other process\n> is running simultaneously, so we may run has_sha1_file\n> before it writes, anyway. It is a race whether we see the\n> object or not.  However, we may also see other things\n> the writing process has done (like updating refs); and in\n> that case, we must be able to also see the new objects.\n>\n> For example, imagine we are doing a for_each_ref iteration,\n> and somebody simultaneously pushes. Receive-pack may write\n> the pack and update a ref after we have examined the\n> objects/pack directory, but before the iteration gets to the\n> updated ref. When we do finally see the updated ref,\n> for_each_ref will call has_sha1_file to check whether the\n> ref is broken. If has_sha1_file returns the wrong answer, we\n> erroneously will think that the ref is broken.\n>\n> In the case of git-fsck, which uses the\n> DO_FOR_EACH_INCLUDE_BROKEN flag, this will cause us to\n> erroneously complain that the ref points to an invalid\n> object. But for git-repack, which does not use that flag, we\n> will skip the ref completely! So not only will we fail to\n> process the new objects that the ref points to (which is\n> acceptabale, since the processes are running simultaneously,\n\ns/acceptabale/acceptable/\n\n> and we might well do our whole repack before the other\n> process updates the ref), but we will not see the ref at\n> all. Its old objects may be omitted from the pack (and even\n> lost, if --unpack-unreachable is used with an expiration\n> time).\n>\n> There's no test included here, because the success case is\n> two processes running simultaneously forever. But you can\n> replicate the issue with:\n>\n>   # base.sh\n>   # run this in one terminal; it creates and pushes\n>   # repeatedly to a repository\n>   git init parent &&\n>   (cd parent &&\n>\n>     # create a base commit that will trigger us looking at\n>     # the objects/pack directory before we hit the updated ref\n>     echo content >file &&\n>     git add file &&\n>     git commit -m base &&\n>\n>     # set the unpack limit abnormally low, which\n>     # lets us simulate full-size pushes using tiny ones\n>     git config receive.unpackLimit 1\n>   ) &&\n>   git clone parent child &&\n>   cd child &&\n>   n=0 &&\n>   while true; do\n>     echo $n >file && git add file && git commit -m $n &&\n>     git push origin HEAD:refs/remotes/child/master &&\n>     n=$(($n + 1))\n>   done\n>\n>   # fsck.sh\n>   # now run this simultaneously in another terminal; it\n>   # repeatedly fscks, looking for us to consider the\n>   # newly-pushed ref broken.\n>   cd parent &&\n>   while true; do\n>     broken=`git fsck 2>&1 | grep remotes/child`\n>     if test -n \"$broken\"; then\n>       echo $broken\n>       exit 1\n>     fi\n>   done\n>\n> Without this patch, the fsck loop fails within a few seconds\n> (and almost instantly if the test repository actually has a\n> large number of refs). With it, the two can run\n> indefinitely.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n"},{"id":"226289","messageId":"xmqqioyn24ne.fsf@gitster.dls.corp.google.com","threadId":"34804","inReplyTo":"20130830011052.GA21895@sigill.intra.peff.net","subject":"Re: [PATCH] has_sha1_file: re-check pack directory before giving up","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-30T04:17:57Z","receivedAt":"2013-08-30T04:17:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> When we read a sha1 file, we first look for a packed\n> version, then a loose version, and then re-check the pack\n> directory again before concluding that we cannot find it.\n> This lets us handle a process that is writing to the\n> repository simultaneously (e.g., receive-pack writing a new\n> pack followed by a ref update, or git-repack packing\n> existing loose objects into a new pack).\n>\n> However, we do not do the same trick with has_sha1_file; we\n> only check the packed objects once, followed by loose\n> objects. This means that we might incorrectly report that we\n> do not have an object, even though we could find it if we\n> simply re-checked the pack directory.\n\nHmm, would the same reasoning apply to sha1_object_info(), or do\nexisting critical code happen not to have a problematic calling\nsequence like you noticed for repack?\n"},{"id":"226290","messageId":"20130830042533.GA23608@sigill.intra.peff.net","threadId":"34804","inReplyTo":"xmqqioyn24ne.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] has_sha1_file: re-check pack directory before giving up","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-30T04:25:34Z","receivedAt":"2013-08-30T04:25:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 29, 2013 at 09:17:57PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > When we read a sha1 file, we first look for a packed\n> > version, then a loose version, and then re-check the pack\n> > directory again before concluding that we cannot find it.\n> > This lets us handle a process that is writing to the\n> > repository simultaneously (e.g., receive-pack writing a new\n> > pack followed by a ref update, or git-repack packing\n> > existing loose objects into a new pack).\n> >\n> > However, we do not do the same trick with has_sha1_file; we\n> > only check the packed objects once, followed by loose\n> > objects. This means that we might incorrectly report that we\n> > do not have an object, even though we could find it if we\n> > simply re-checked the pack directory.\n> \n> Hmm, would the same reasoning apply to sha1_object_info(), or do\n> existing critical code happen not to have a problematic calling\n> sequence like you noticed for repack?\n\nI think the same reasoning would apply; however, we seem to already do\nthe pack-loose-pack lookup there:\n\nint sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi)\n{\n[...]\n        if (!find_pack_entry(sha1, &e)) {\n                /* Most likely it's a loose object. */\n                if (!sha1_loose_object_info(sha1, oi)) {\n                        oi->whence = OI_LOOSE;\n                        return 0;\n                }\n\n                /* Not a loose object; someone else may have just packed it. */\n                reprepare_packed_git();\n                if (!find_pack_entry(sha1, &e))\n                        return -1;\n        }\n\n-Peff\n"},{"id":"226291","messageId":"20130830042801.GA23780@sigill.intra.peff.net","threadId":"34804","inReplyTo":"20130830011052.GA21895@sigill.intra.peff.net","subject":"Re: [PATCH] has_sha1_file: re-check pack directory before giving up","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-30T04:28:01Z","receivedAt":"2013-08-30T04:28:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 29, 2013 at 09:10:52PM -0400, Jeff King wrote:\n\n> In the case of git-fsck, which uses the\n> DO_FOR_EACH_INCLUDE_BROKEN flag, this will cause us to\n> erroneously complain that the ref points to an invalid\n> object. But for git-repack, which does not use that flag, we\n> will skip the ref completely!\n\nHmm. This is slightly inaccurate. fsck does not use INCLUDE_BROKEN, and\nthat is why it recognizes (and prints the warning) the \"broken\" ref.\npack-objects would also print a warning, but would dutifully ignore the\nbroken ref during the repack.\n\nSo it is actually something like for-each-ref, which _does_ use\nINCLUDE_BROKEN, that behaves differently. And it tends to work, because\nit ends up calling read_sha1_file to find out about the file rather than\nchecking has_sha1_file.\n\n-Peff\n"},{"id":"226363","messageId":"20130830191412.GA15584@sigill.intra.peff.net","threadId":"34804","inReplyTo":"20130830042801.GA23780@sigill.intra.peff.net","subject":"[PATCHv2] has_sha1_file: re-check pack directory before giving up","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-30T19:14:13Z","receivedAt":"2013-08-30T19:14:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 30, 2013 at 12:28:01AM -0400, Jeff King wrote:\n\n> On Thu, Aug 29, 2013 at 09:10:52PM -0400, Jeff King wrote:\n> \n> > In the case of git-fsck, which uses the\n> > DO_FOR_EACH_INCLUDE_BROKEN flag, this will cause us to\n> > erroneously complain that the ref points to an invalid\n> > object. But for git-repack, which does not use that flag, we\n> > will skip the ref completely!\n> \n> Hmm. This is slightly inaccurate. fsck does not use INCLUDE_BROKEN, and\n> that is why it recognizes (and prints the warning) the \"broken\" ref.\n> pack-objects would also print a warning, but would dutifully ignore the\n> broken ref during the repack.\n> \n> So it is actually something like for-each-ref, which _does_ use\n> INCLUDE_BROKEN, that behaves differently. And it tends to work, because\n> it ends up calling read_sha1_file to find out about the file rather than\n> checking has_sha1_file.\n\nHere's a re-roll with a commit message that clarifies the role of\nDO_FOR_EACH_INCLUDE_BROKEN. The code is the same, and the diff between\nthe commit messages is below.\n\n\t@@ -34,18 +34,17 @@\n\t     ref is broken. If has_sha1_file returns the wrong answer, we\n\t     erroneously will think that the ref is broken.\n\t     \n\t-    In the case of git-fsck, which uses the\n\t-    DO_FOR_EACH_INCLUDE_BROKEN flag, this will cause us to\n\t-    erroneously complain that the ref points to an invalid\n\t-    object. But for git-repack, which does not use that flag, we\n\t-    will skip the ref completely! So not only will we fail to\n\t-    process the new objects that the ref points to (which is\n\t-    acceptabale, since the processes are running simultaneously,\n\t-    and we might well do our whole repack before the other\n\t-    process updates the ref), but we will not see the ref at\n\t-    all. Its old objects may be omitted from the pack (and even\n\t-    lost, if --unpack-unreachable is used with an expiration\n\t-    time).\n\t+    For a normal iteration without DO_FOR_EACH_INCLUDE_BROKEN,\n\t+    this means that the caller does not see the ref at all\n\t+    (neither the old nor the new value).  So not only will we\n\t+    fail to see the new value of the ref (which is acceptable,\n\t+    since we are running simultaneously with the writer, and we\n\t+    might well read the ref before the writer commits its\n\t+    write), but we will not see the old value either. For\n\t+    programs that act on reachability like pack-objects or\n\t+    prune, this can cause data loss, as we may see the objects\n\t+    referenced by the original ref value as dangling (and either\n\t+    omit them from the pack, or delete them via prune).\n\t     \n\t     There's no test included here, because the success case is\n\t     two processes running simultaneously forever. But you can\n\t@@ -79,7 +78,11 @@\n\t       # fsck.sh\n\t       # now run this simultaneously in another terminal; it\n\t       # repeatedly fscks, looking for us to consider the\n\t-      # newly-pushed ref broken.\n\t+      # newly-pushed ref broken. We cannot use for-each-ref\n\t+      # here, as it uses DO_FOR_EACH_INCLUDE_BROKEN, which\n\t+      # skips the has_sha1_file check (and if it wants\n\t+      # more information on the object, it will actually read\n\t+      # the object, which does the proper two-step lookup)\n\t       cd parent &&\n\t       while true; do\n\t         broken=`git fsck 2>&1 | grep remotes/child`\n\n-- >8 --\nSubject: has_sha1_file: re-check pack directory before giving up\n\nWhen we read a sha1 file, we first look for a packed\nversion, then a loose version, and then re-check the pack\ndirectory again before concluding that we cannot find it.\nThis lets us handle a process that is writing to the\nrepository simultaneously (e.g., receive-pack writing a new\npack followed by a ref update, or git-repack packing\nexisting loose objects into a new pack).\n\nHowever, we do not do the same trick with has_sha1_file; we\nonly check the packed objects once, followed by loose\nobjects. This means that we might incorrectly report that we\ndo not have an object, even though we could find it if we\nsimply re-checked the pack directory.\n\nBy itself, this is usually not a big deal. The other process\nis running simultaneously, so we may run has_sha1_file\nbefore it writes, anyway. It is a race whether we see the\nobject or not.  However, we may also see other things\nthe writing process has done (like updating refs); and in\nthat case, we must be able to also see the new objects.\n\nFor example, imagine we are doing a for_each_ref iteration,\nand somebody simultaneously pushes. Receive-pack may write\nthe pack and update a ref after we have examined the\nobjects/pack directory, but before the iteration gets to the\nupdated ref. When we do finally see the updated ref,\nfor_each_ref will call has_sha1_file to check whether the\nref is broken. If has_sha1_file returns the wrong answer, we\nerroneously will think that the ref is broken.\n\nFor a normal iteration without DO_FOR_EACH_INCLUDE_BROKEN,\nthis means that the caller does not see the ref at all\n(neither the old nor the new value).  So not only will we\nfail to see the new value of the ref (which is acceptable,\nsince we are running simultaneously with the writer, and we\nmight well read the ref before the writer commits its\nwrite), but we will not see the old value either. For\nprograms that act on reachability like pack-objects or\nprune, this can cause data loss, as we may see the objects\nreferenced by the original ref value as dangling (and either\nomit them from the pack, or delete them via prune).\n\nThere's no test included here, because the success case is\ntwo processes running simultaneously forever. But you can\nreplicate the issue with:\n\n  # base.sh\n  # run this in one terminal; it creates and pushes\n  # repeatedly to a repository\n  git init parent &&\n  (cd parent &&\n\n    # create a base commit that will trigger us looking at\n    # the objects/pack directory before we hit the updated ref\n    echo content >file &&\n    git add file &&\n    git commit -m base &&\n\n    # set the unpack limit abnormally low, which\n    # lets us simulate full-size pushes using tiny ones\n    git config receive.unpackLimit 1\n  ) &&\n  git clone parent child &&\n  cd child &&\n  n=0 &&\n  while true; do\n    echo $n >file && git add file && git commit -m $n &&\n    git push origin HEAD:refs/remotes/child/master &&\n    n=$(($n + 1))\n  done\n\n  # fsck.sh\n  # now run this simultaneously in another terminal; it\n  # repeatedly fscks, looking for us to consider the\n  # newly-pushed ref broken. We cannot use for-each-ref\n  # here, as it uses DO_FOR_EACH_INCLUDE_BROKEN, which\n  # skips the has_sha1_file check (and if it wants\n  # more information on the object, it will actually read\n  # the object, which does the proper two-step lookup)\n  cd parent &&\n  while true; do\n    broken=`git fsck 2>&1 | grep remotes/child`\n    if test -n \"$broken\"; then\n      echo $broken\n      exit 1\n    fi\n  done\n\nWithout this patch, the fsck loop fails within a few seconds\n(and almost instantly if the test repository actually has a\nlarge number of refs). With it, the two can run\nindefinitely.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1_file.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex e1b2290..02ebb80 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2640,7 +2640,10 @@ int has_sha1_file(const unsigned char *sha1)\n \n \tif (find_pack_entry(sha1, &e))\n \t\treturn 1;\n-\treturn has_loose_object(sha1);\n+\tif (has_loose_object(sha1))\n+\t\treturn 1;\n+\treprepare_packed_git();\n+\treturn find_pack_entry(sha1, &e);\n }\n \n static void check_tree(const void *buf, size_t size)\n-- \n1.8.4.2.g87d4a77\n"}]}