{"thread":{"id":"37389","subject":"[BUG] resolved deltas","startedAt":"2014-08-21T11:35:43Z","lastAt":"2014-09-02T17:19:37Z","messageCount":30,"participants":["Petr Stodulka","Martin von Gagern","René Scharfe","Jeff King","Shawn Pearce","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"248050","messageId":"53F5D98F.4040700@redhat.com","threadId":"37389","inReplyTo":null,"subject":"[BUG] resolved deltas","fromName":"Petr Stodulka","fromEmail":"pstodulk@redhat.com","sentAt":"2014-08-21T11:35:43Z","receivedAt":"2014-08-21T11:35:43Z","isPatch":false,"sender":{"key":"pstodulk@redhat.com","avatar":"https://avatars.githubusercontent.com/u/1656374?v=4"},"body":"Hi guys,\nI wanted post you patch here for this bug, but I can't find primary \nsource of this problem [0], because I don't understand some ideas in the \ncode. So what I investigate:\n\nBug is reprodusible since git version 1.8.3.1 (may earlier 1.8.xx, but I \ndon't test it) to actual upstream version.\nThis problem \"doesn't exists\" in version 1.7.xx - or more precisely is \nnot reproducible. \"May\" this is reproducible\nsince commit \"7218a215\" - in this commit was added assert in file \n\"builtin/index-pack.c\" (actual line is 918), but I didn't test this.\n\nThis assert tests if object's (child) real type == OBJ_REF_DELTA. This \nwill failure for object with real_type == OBJ_TREE (set as parent's \ntype) and type == OBJ_REF_DELTA. Here some prints of important variables \nbefore failure assert() (from older version but I think that values are \nstill actual in this case):\n------------------------------\n(gdb) p base->ref_first\n$9 = 3223\n\n(gdb) p deltas[3223]\n$10 = {\n base = {\n sha1 = \"\\274\\070k\\343K\\324x\\037q\\273h\\327*n\\n\\356\\061$ \\036\",\n offset = 2267795834784135356\n },\n obj_no = 11152\n}\n\n(gdb) p *child\n$11 = {\n idx = {\n sha1 = \"J\\242i\\251\\261\\273\\305\\067\\236%CE\\022\\257\\252\\342[;\\tD\",\n crc32 = 2811659028,\n offset = 10392153\n },\n size = 30,\n hdr_size = 22,\n type = OBJ_REF_DELTA,\n real_type = OBJ_TREE,\n delta_depth = 0,\n base_object_no = 5458\n}\n\n(gdb) p objects[5458]\n$13 = {\n idx = {\n sha1 = \"\\274\\070k\\343K\\324x\\037q\\273h\\327*n\\n\\356\\061$ \\036\",\n crc32 = 3724458534,\n offset = 6879168\n },\n size = 236,\n hdr_size = 2,\n type = OBJ_TREE,\n real_type = OBJ_TREE,\n delta_depth = 0,\n base_object_no = 0\n}\n---------------------------------------\n\n\"base_object_no\" is static 5458. \"base->ref_first\" child's object are \ndynamic. If you want stop process in same position my recommendation for \ngdb (if you use gdb) when you will be in file index-pack.c:\nbr 1093\ncont\nset variable nr_threads = 1\nbr 1111\ncond 2 i == 6300\ncont\nbr 916\ncont\n-----------\ncompilated without any optimisation, line numbers modified for commit \n\"6c4ab27f2378ce67940b4496365043119d7ffff2\"\nCondition i == 6300 ---> last iteration before failure has dynamic rank \nin range 6304 to 6309 in the most cases (that's weird for me, when count \nof downloaded objects is statically 12806, may wrong search of children?)\n-----------------------------------\n\nHere I am lost. I don't know really what I can do next here, because I \ndon't understand some ideas in code. e.g. searching of child - functions \nfind_delta(), find_delta_children(). Calculation on line 618:\n----\n int next = (first+last) / 2;\n----\nI still don't understand. I didn't find description of this searching \nalgorithm in tech. documentation but I didn't read all yet. However I \nthink that source of problems could be somewhere in these two functions. \nWhen child is found, its real_type is set to parent's type in function \nresolve_delta() on the line 865 and then lasts wait for failure. I don't \nthink that problem is in repository itself [1], but it is possible.\n\nAny next ideas/hints or explanation of these functions? I began study \nsource code and mechanisms of the git this week, so don't beat me yet \nplease :-)\n\nRegards,\nPetr\n\n[0] https://bugzilla.redhat.com/show_bug.cgi?id=1099919\n[1] git clone https://code.google.com/p/mapsforge/ mapsforge.git\n"},{"id":"248071","messageId":"53F639A3.80805@redhat.com","threadId":"37389","inReplyTo":"53F5D98F.4040700@redhat.com","subject":"Re: [BUG] resolved deltas","fromName":"Petr Stodulka","fromEmail":"pstodulk@redhat.com","sentAt":"2014-08-21T18:25:39Z","receivedAt":"2014-08-21T18:25:39Z","isPatch":false,"sender":{"key":"pstodulk@redhat.com","avatar":"https://avatars.githubusercontent.com/u/1656374?v=4"},"body":"\n> \n> Bug is reprodusible since git version 1.8.3.1 (may earlier 1.8.xx, but \n> I don't test it) to actual upstream version.\n> This problem \"doesn't exists\" in version 1.7.xx - or more precisely is \n> not reproducible. \"May\" this is reproducible\n> since commit \"7218a215\" - in this commit was added assert in file \n> \"builtin/index-pack.c\" (actual line is 918), but I didn't test this.\nOk so this is reproducible since this commit because of assert().\n\n> Here I am lost. I don't know really what I can do next here, because I \n> don't understand some ideas in code. e.g. searching of child - \n> functions find_delta(), find_delta_children(). Calculation on line 618:\n> ----\n> int next = (first+last) / 2;\n> ----\n> I still don't understand. I didn't find description of this searching \n> algorithm in tech. documentation but I didn't read all yet. However I \n> think that source of problems could be somewhere in these two \n> functions. When child is found, its real_type is set to parent's type \n> in function resolve_delta() on the line 865 and then lasts wait for \n> failure. I don't think that problem is in repository itself [1], but \n> it is possible.\nI read history of commits and my idea seems to be incorrect. It seems \nmore like some error in repository itself. But I'd rather get opinion \nfrom someone who knows this code and ideas better.\n\nRegards,\nPetr\n\n> [0] https://bugzilla.redhat.com/show_bug.cgi?id=1099919\n> [1] git clone https://code.google.com/p/mapsforge/ mapsforge.git\n"},{"id":"248139","messageId":"53F79CE3.60803@gmx.net","threadId":"37389","inReplyTo":"53F5D98F.4040700@redhat.com","subject":"Re: [BUG] resolved deltas","fromName":"Martin von Gagern","fromEmail":"martin.vgagern@gmx.net","sentAt":"2014-08-22T19:41:23Z","receivedAt":"2014-08-22T19:41:23Z","isPatch":false,"sender":{"key":"martin.vgagern@gmx.net","avatar":"https://avatars.githubusercontent.com/u/190759?v=4"},"body":"On 21.08.2014 13:35, Petr Stodulka wrote:\n> Hi guys,\n> I wanted post you patch here for this bug, but I can't find primary\n> source of this problem [0], because I don't understand some ideas in the\n> code.\n>\n> […]\n> \n> Any next ideas/hints or explanation of these functions? I began study\n> source code and mechanisms of the git this week, so don't beat me yet\n> please :-)\n> \n> Regards,\n> Petr\n> \n> [0] https://bugzilla.redhat.com/show_bug.cgi?id=1099919\n\nSome pointers to related reports and investigations:\n\nhttps://groups.google.com/forum/#!topic/mapsforge-dev/IF6mgmwvZmY\nhttps://groups.google.com/forum/#!topic/mapsforge-dev/f2KvFALlkvo\nhttps://code.google.com/p/support/issues/detail?id=31571\nhttps://groups.google.com/forum/#!topic/mapsforge-dev/nomzr5dkkqc\nhttp://thread.gmane.org/gmane.comp.version-control.git/254626\n\nThe last is my own bug report to this mailing list here, which\nunfortunately received no reaction yet. In that report, I can confirm\nthat the commit introducing the assertion is the same commit which\ncauses things to fail:\nhttps://github.com/git/git/commit/7218a215efc7ae46f7ca8d82442f354e\n\nIn this https://code.google.com/p/mapsforge/ repository, resolve_delta\ngets called twice for some delta. The first time, type and real_type are\nidentical, but by the second pass in find_unresolved_deltas the real\ntype will have chaned to OBJ_TREE. This caused the old code to simply\nscip the object, but the new code aborts instead.\n\nSo far my understanding. I'm not sure whether this kind of duplicate\nresolution is something normal or indicates some breakage in the\nrepository in question. But aborting seems a bad solution in either case.\n\nGreetings,\n Martin von Gagern\n"},{"id":"248183","messageId":"53F868F8.9080000@web.de","threadId":"37389","inReplyTo":"53F79CE3.60803@gmx.net","subject":"Re: [BUG] resolved deltas","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-08-23T10:12:08Z","receivedAt":"2014-08-23T10:12:08Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 22.08.2014 um 21:41 schrieb Martin von Gagern:\n> On 21.08.2014 13:35, Petr Stodulka wrote:\n>> Hi guys,\n>> I wanted post you patch here for this bug, but I can't find primary\n>> source of this problem [0], because I don't understand some ideas in the\n>> code.\n>>\n>> […]\n>>\n>> Any next ideas/hints or explanation of these functions? I began study\n>> source code and mechanisms of the git this week, so don't beat me yet\n>> please :-)\n>>\n>> Regards,\n>> Petr\n>>\n>> [0] https://bugzilla.redhat.com/show_bug.cgi?id=1099919\n> \n> Some pointers to related reports and investigations:\n> \n> https://groups.google.com/forum/#!topic/mapsforge-dev/IF6mgmwvZmY\n> https://groups.google.com/forum/#!topic/mapsforge-dev/f2KvFALlkvo\n> https://code.google.com/p/support/issues/detail?id=31571\n> https://groups.google.com/forum/#!topic/mapsforge-dev/nomzr5dkkqc\n> http://thread.gmane.org/gmane.comp.version-control.git/254626\n> \n> The last is my own bug report to this mailing list here, which\n> unfortunately received no reaction yet. In that report, I can confirm\n> that the commit introducing the assertion is the same commit which\n> causes things to fail:\n> https://github.com/git/git/commit/7218a215efc7ae46f7ca8d82442f354e\n> \n> In this https://code.google.com/p/mapsforge/ repository, resolve_delta\n> gets called twice for some delta. The first time, type and real_type are\n> identical, but by the second pass in find_unresolved_deltas the real\n> type will have chaned to OBJ_TREE. This caused the old code to simply\n> scip the object, but the new code aborts instead.\n> \n> So far my understanding. I'm not sure whether this kind of duplicate\n> resolution is something normal or indicates some breakage in the\n> repository in question. But aborting seems a bad solution in either case.\n\nGit 1.7.6 clones the repo without reporting an error or warning, but a\ncheck shows that a tree object is missing:\n\n $ git clone https://code.google.com/p/mapsforge/\n Cloning into mapsforge...\n remote: Counting objects: 12879, done.\n Receiving objects: 100% (12879/12879), 10.19 MiB | 2.48 MiB/s, done.\n Resolving deltas: 100% (4349/4349), done.\n $ cd mapsforge/\n $ git fsck\n broken link from tree eb95fb0268c43f512e2ce512e6625072acafbdb5\n to tree a0155d8d5bb58afb9a5d20459be023899c9a1cef\n missing tree a0155d8d5bb58afb9a5d20459be023899c9a1cef\n dangling tree b6f32087526f43205bf8b5e6539936da787ecb1a\n\nGit 2.1.0 hits an assertion:\n\n $ git clone https://code.google.com/p/mapsforge/\n Cloning into 'mapsforge'...\n remote: Counting objects: 12879, done.\n Receiving objects: 100% (12879/12879), 10.19 MiB | 2.53 MiB/s, done.\n git: builtin/index-pack.c:918: find_unresolved_deltas_1: Assertion `child->real_type == OBJ_REF_DELTA' failed.\n error: index-pack died of signal 6\n fatal: index-pack failed\n\nThe patch below, which makes index-pack ignore objects with unexpected\nreal_type as before, changes the shown error message, but clone still\nfails:\n\n $ git clone https://code.google.com/p/mapsforge/\n Cloning into 'mapsforge'...\n remote: Counting objects: 12879, done.\n Receiving objects: 100% (12879/12879), 10.19 MiB | 2.43 MiB/s, done.\n Resolving deltas: 100% (4348/4348), done.\n fatal: did not receive expected object a0155d8d5bb58afb9a5d20459be023899c9a1cef\n fatal: index-pack failed\n\nTurning that fatal error into a warning get us a bit further:\n\n $ git clone https://code.google.com/p/mapsforge/\n Cloning into 'mapsforge'...\n remote: Counting objects: 12879, done.\n Receiving objects: 100% (12879/12879), 10.19 MiB | 2.38 MiB/s, done.\n Resolving deltas: 100% (4350/4350), done.\n warning: did not receive expected object a0155d8d5bb58afb9a5d20459be023899c9a1cef\n fatal: The same object bc386be34bd4781f71bb68d72a6e0aee3124201e appears twice in the pack\n fatal: index-pack failed\n\nDisabling strict checking (WRITE_IDX_STRICT) as well lets clone\nsucceed, but a check shows that a tree is missing, as wiht git 1.7.6:\n\n $ git clone https://code.google.com/p/mapsforge/\n Cloning into 'mapsforge'...\n remote: Counting objects: 12879, done.\n Receiving objects: 100% (12879/12879), 10.19 MiB | 2.37 MiB/s, done.\n Resolving deltas: 100% (4349/4349), done.\n warning: did not receive expected object a0155d8d5bb58afb9a5d20459be023899c9a1cef\n Checking connectivity... done.\n $ cd mapsforge/\n $ git fsck\n Checking object directories: 100% (256/256), done.\n Checking objects: 100% (12879/12879), done.\n broken link from tree eb95fb0268c43f512e2ce512e6625072acafbdb5\n to tree a0155d8d5bb58afb9a5d20459be023899c9a1cef\n missing tree a0155d8d5bb58afb9a5d20459be023899c9a1cef\n\nCloning the repo with Egit works fine, but git fsck shows the same\nresults as above.\n\nhttps://github.com/applantation/mapsforge has that missing tree\nobject, by the way.\n\nOK, what now? It's better to show an error message instead of\nfailing an assertion if a repo is found to be corrupt because the\nissue is caused by external input. I don't know if the patch\nbelow may have any bad side effects, though, so no sign-off at\nthis time.\n\nAllowing git to clone a broken repo sounds useful, up to point.\nIn this particular case older versions had no problem doing that,\nso it seems worth supporting.\n\nAnd how did the tree object went missing in the first place?\n\nRené\n---\n builtin/index-pack.c | 33 +++++++++++++++++++--------------\n 1 file changed, 19 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 5568a5b..f7dc5b0 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -913,28 +913,33 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \n \tif (base->ref_first <= base->ref_last) {\n \t\tstruct object_entry *child = objects + deltas[base->ref_first].obj_no;\n-\t\tstruct base_data *result = alloc_base_data();\n \n-\t\tassert(child->real_type == OBJ_REF_DELTA);\n-\t\tresolve_delta(child, base, result);\n-\t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n-\t\t\tfree_base_data(base);\n+\t\tif (child->real_type == OBJ_REF_DELTA) {\n+\t\t\tstruct base_data *result = alloc_base_data();\n \n-\t\tbase->ref_first++;\n-\t\treturn result;\n+\t\t\tresolve_delta(child, base, result);\n+\t\t\tif (base->ref_first == base->ref_last &&\n+\t\t\t base->ofs_last == -1)\n+\t\t\t\tfree_base_data(base);\n+\n+\t\t\tbase->ref_first++;\n+\t\t\treturn result;\n+\t\t}\n \t}\n \n \tif (base->ofs_first <= base->ofs_last) {\n \t\tstruct object_entry *child = objects + deltas[base->ofs_first].obj_no;\n-\t\tstruct base_data *result = alloc_base_data();\n \n-\t\tassert(child->real_type == OBJ_OFS_DELTA);\n-\t\tresolve_delta(child, base, result);\n-\t\tif (base->ofs_first == base->ofs_last)\n-\t\t\tfree_base_data(base);\n+\t\tif (child->real_type == OBJ_OFS_DELTA) {\n+\t\t\tstruct base_data *result = alloc_base_data();\n \n-\t\tbase->ofs_first++;\n-\t\treturn result;\n+\t\t\tresolve_delta(child, base, result);\n+\t\t\tif (base->ofs_first == base->ofs_last)\n+\t\t\t\tfree_base_data(base);\n+\n+\t\t\tbase->ofs_first++;\n+\t\t\treturn result;\n+\t\t}\n \t}\n \n \tunlink_base_data(base);\n-- \n2.1.0\n"},{"id":"248184","messageId":"20140823105640.GA6881@peff.net","threadId":"37389","inReplyTo":"53F868F8.9080000@web.de","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-23T10:56:40Z","receivedAt":"2014-08-23T10:56:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[+cc spearce, as I think this is a bug in code.google.com's sending\n side, and he can probably get the attention of the right folks]\n\nOn Sat, Aug 23, 2014 at 12:12:08PM +0200, René Scharfe wrote:\n\n> Git 1.7.6 clones the repo without reporting an error or warning, but a\n> check shows that a tree object is missing:\n\nThanks for digging on this. I happened to be looking at it at the exact\nsame time, so now I can stop. :)\n\n> The patch below, which makes index-pack ignore objects with unexpected\n> real_type as before, changes the shown error message, but clone still\n> fails:\n> \n> $ git clone https://code.google.com/p/mapsforge/\n> Cloning into 'mapsforge'...\n> remote: Counting objects: 12879, done.\n> Receiving objects: 100% (12879/12879), 10.19 MiB | 2.43 MiB/s, done.\n> Resolving deltas: 100% (4348/4348), done.\n> fatal: did not receive expected object a0155d8d5bb58afb9a5d20459be023899c9a1cef\n> fatal: index-pack failed\n\nThis makes sense. Early versions of index-pack didn't know how to check\nfor missing objects, but now it does. However, we only trigger that code\nif we are using --strict, or if we are cloning (in which case we pass\nthe --check-self-contained-and-connected option).\n\nIf you are doing a regular fetch, we rely on check_everything_connected\nafter the pack is received. So (with your patch):\n\n $ git init\n $ git fetch https://code.google.com/p/mapsforge/\n remote: Counting objects: 12298, done.\n Receiving objects: 100% (12298/12298), 9.24 MiB | 959.00 KiB/s, done.\n Resolving deltas: 100% (4107/4107), done.\n error: Could not read a0155d8d5bb58afb9a5d20459be023899c9a1cef\n fatal: bad tree object a0155d8d5bb58afb9a5d20459be023899c9a1cef\n error: https://code.google.com/p/mapsforge/ did not send all necessary objects\n\nThat all makes sense.\n\n> Turning that fatal error into a warning get us a bit further:\n> \n> $ git clone https://code.google.com/p/mapsforge/\n> Cloning into 'mapsforge'...\n> remote: Counting objects: 12879, done.\n> Receiving objects: 100% (12879/12879), 10.19 MiB | 2.38 MiB/s, done.\n> Resolving deltas: 100% (4350/4350), done.\n> warning: did not receive expected object a0155d8d5bb58afb9a5d20459be023899c9a1cef\n> fatal: The same object bc386be34bd4781f71bb68d72a6e0aee3124201e appears twice in the pack\n> fatal: index-pack failed\n> \n> Disabling strict checking (WRITE_IDX_STRICT) as well lets clone\n> succeed, but a check shows that a tree is missing, as wiht git 1.7.6:\n\nInteresting that one object is duplicated and another object is missing.\nThe pack doesn't contain the sha1s of the objects; we compute them on\nthe fly in index-pack. So it's likely that the real problem is that one\nentry in the pack either has the wrong delta data, or mentions the wrong\nbase object. And does it in such a way that we generate the another\nobject that does exist (so the packfile data isn't garbled or corrupted;\nit's a bug on the sending side that uses the wrong data).\n\n> https://github.com/applantation/mapsforge has that missing tree\n> object, by the way.\n\nUnsurprisingly, it's a tree object quite similar to the duplicated one.\n\n> OK, what now? It's better to show an error message instead of\n> failing an assertion if a repo is found to be corrupt because the\n> issue is caused by external input. I don't know if the patch\n> below may have any bad side effects, though, so no sign-off at\n> this time.\n\nDefinitely. Your patch looks like an improvement. The objects in the\ndelta list must have had their real_types set to REF_DELTA and OFS_DELTA\nat some point (since that is how they got on the list). And there is no\nway for the type field to change from a delta type to anything else\n_except_ by us resolving the delta. So I think the condition triggering\nthat assert cannot mean anything except that we have a duplicate object\n(and it is not actually the delta object that is duplicated, but rather\nits base, as seeing it again is what causes us to try to resolve twice).\n\nSo we know at this point that we have a duplicate object, and we could\nwarn or say something. But I think we probably would not want to. If\n--strict is in effect, then we will notice and complain later. And if it\nis not, then we should allow it without comment (in this case the repo\nis broken, but it would not _have_ to be).\n\nSo I think your patch is doing the right thing.\n\n> Allowing git to clone a broken repo sounds useful, up to point.\n> In this particular case older versions had no problem doing that,\n> so it seems worth supporting.\n\nI think with your patch we are fine. Without --strict (which is implied\non a clone), you can still \"git init\" and \"git fetch\" the broken pack\n(fetch will complain, but it leaves the pack in place).\n\nWe may want to adjust the fact that --check-self-contained-and-connected\nimplies strict (it builds on the fsck bits of index-pack, but it does\nnot have to imply a full fsck, nor strict index writing).\n\n> And how did the tree object went missing in the first place?\n\nMy guess is a bug on the sending side. We have seen duplicate pack\nobjects before, but never (AFAIK) combined with a missing object. This\nreally seems like the sender just sent the wrong data for one object.\n\nIIRC, code.google.com is backed by their custom Dulwich implementation\nwhich runs on BigTable. We'll see if Shawn can get this to the right\npeople as a bug report. :)\n\n-Peff\n"},{"id":"248185","messageId":"20140823110459.GA13087@peff.net","threadId":"37389","inReplyTo":"20140823105640.GA6881@peff.net","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-23T11:04:59Z","receivedAt":"2014-08-23T11:04:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 23, 2014 at 06:56:40AM -0400, Jeff King wrote:\n\n> So I think your patch is doing the right thing.\n\nBy the way, if you want to add a test to your patch, there is\ninfrastructure in t5308 to create packs with duplicate objects. If I\nunderstand the problem correctly, you could trigger this by having a\ndelta object whose base is duplicated, even without the missing object.\n\n-Peff\n"},{"id":"248187","messageId":"20140823111804.GA17335@peff.net","threadId":"37389","inReplyTo":"20140823110459.GA13087@peff.net","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-23T11:18:04Z","receivedAt":"2014-08-23T11:18:04Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 23, 2014 at 07:04:59AM -0400, Jeff King wrote:\n\n> On Sat, Aug 23, 2014 at 06:56:40AM -0400, Jeff King wrote:\n> \n> > So I think your patch is doing the right thing.\n> \n> By the way, if you want to add a test to your patch, there is\n> infrastructure in t5308 to create packs with duplicate objects. If I\n> understand the problem correctly, you could trigger this by having a\n> delta object whose base is duplicated, even without the missing object.\n\nThis actually turned out to be really easy. The test below fails without\nyour patch and passes with it. Please feel free to squash it in.\n\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 9c5a876..50f7a69 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -77,4 +77,19 @@ test_expect_success 'index-pack can reject packs with duplicates' '\n \ttest_expect_code 1 git cat-file -e $LO_SHA1\n '\n \n+test_expect_success 'duplicated delta base does not trigger assert' '\n+\tclear_packs &&\n+\t{\n+\t\tA=01d7713666f4de822776c7622c10f1b07de280dc &&\n+\t\tB=e68fe8129b546b101aee9510c5328e7f21ca1d18 &&\n+\t\tpack_header 3 &&\n+\t\tpack_obj $A $B &&\n+\t\tpack_obj $B &&\n+\t\tpack_obj $B\n+\t} >dups.pack &&\n+\tpack_trailer dups.pack &&\n+\tgit index-pack --stdin On Sat, Aug 23, 2014 at 07:04:59AM -0400, Jeff King wrote:\n> \n>> On Sat, Aug 23, 2014 at 06:56:40AM -0400, Jeff King wrote:\n>>\n>>> So I think your patch is doing the right thing.\n>>\n>> By the way, if you want to add a test to your patch, there is\n>> infrastructure in t5308 to create packs with duplicate objects. If I\n>> understand the problem correctly, you could trigger this by having a\n>> delta object whose base is duplicated, even without the missing object.\n> \n> This actually turned out to be really easy. The test below fails without\n> your patch and passes with it. Please feel free to squash it in.\n> \n> diff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\n> index 9c5a876..50f7a69 100755\n> --- a/t/t5308-pack-detect-duplicates.sh\n> +++ b/t/t5308-pack-detect-duplicates.sh\n> @@ -77,4 +77,19 @@ test_expect_success 'index-pack can reject packs with duplicates' '\n> \ttest_expect_code 1 git cat-file -e $LO_SHA1\n> '\n> \n> +test_expect_success 'duplicated delta base does not trigger assert' '\n> +\tclear_packs &&\n> +\t{\n> +\t\tA=01d7713666f4de822776c7622c10f1b07de280dc &&\n> +\t\tB=e68fe8129b546b101aee9510c5328e7f21ca1d18 &&\n> +\t\tpack_header 3 &&\n> +\t\tpack_obj $A $B &&\n> +\t\tpack_obj $B &&\n> +\t\tpack_obj $B\n> +\t} >dups.pack &&\n> +\tpack_trailer dups.pack &&\n> +\tgit index-pack --stdin +\ttest_must_fail git index-pack --stdin --strict +'\n> +\n> test_done\n\nThanks, that looks good. But while preparing the patch I noticed that\nthe added test sometimes fails. Helgrind pointed outet a race\ncondition. It is not caused by the patch to turn the asserts into\nregular ifs, however -- here's a Helgrind report for the original code\nwith the new test:\n\n==34949== Helgrind, a thread error detector\n==34949== Copyright (C) 2007-2013, and GNU GPL'd, by OpenWorks LLP et al.\n==34949== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info\n==34949== Command: /home/lsr/src/git/t/../bin-wrappers/git index-pack --stdin\n==34949==\n==34949== Helgrind, a thread error detector\n==34949== Copyright (C) 2007-2013, and GNU GPL'd, by OpenWorks LLP et al.\n==34949== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info\n==34949== Command: /home/lsr/src/git/git index-pack --stdin\n==34949==\n==34949== ---Thread-Announcement------------------------------------------\n==34949==\n==34949== Thread #3 was created\n==34949== at 0x594DF7E: clone (clone.S:74)\n==34949== by 0x544A2B9: do_clone.constprop.3 (createthread.c:75)\n==34949== by 0x544B762: pthread_create@@GLIBC_2.2.5 (createthread.c:245)\n==34949== by 0x4C2D55D: pthread_create_WRK (hg_intercepts.c:269)\n==34949== by 0x43ABB8: cmd_index_pack (index-pack.c:1097)\n==34949== by 0x405B6A: handle_builtin (git.c:351)\n==34949== by 0x404CE8: main (git.c:575)\n==34949==\n==34949== ---Thread-Announcement------------------------------------------\n==34949==\n==34949== Thread #2 was created\n==34949== at 0x594DF7E: clone (clone.S:74)\n==34949== by 0x544A2B9: do_clone.constprop.3 (createthread.c:75)\n==34949== by 0x544B762: pthread_create@@GLIBC_2.2.5 (createthread.c:245)\n==34949== by 0x4C2D55D: pthread_create_WRK (hg_intercepts.c:269)\n==34949== by 0x43ABB8: cmd_index_pack (index-pack.c:1097)\n==34949== by 0x405B6A: handle_builtin (git.c:351)\n==34949== by 0x404CE8: main (git.c:575)\n==34949==\n==34949== ----------------------------------------------------------------\n==34949==\n==34949== Possible data race during read of size 4 at 0x5E15910 by thread #3\n==34949== Locks held: none\n==34949== at 0x439327: find_unresolved_deltas (index-pack.c:918)\n==34949== by 0x439666: threaded_second_pass (index-pack.c:1002)\n==34949== by 0x4C2D6F6: mythread_wrapper (hg_intercepts.c:233)\n==34949== by 0x544B0A3: start_thread (pthread_create.c:309)\n==34949==\n==34949== This conflicts with a previous write of size 4 by thread #2\n==34949== Locks held: none\n==34949== at 0x4390E2: resolve_delta (index-pack.c:865)\n==34949== by 0x439340: find_unresolved_deltas (index-pack.c:919)\n==34949== by 0x439666: threaded_second_pass (index-pack.c:1002)\n==34949== by 0x4C2D6F6: mythread_wrapper (hg_intercepts.c:233)\n==34949== by 0x544B0A3: start_thread (pthread_create.c:309)\n==34949==\n==34949== Address 0x5E15910 is 48 bytes inside a block of size 256 alloc'd\n==34949== at 0x4C2A7D0: calloc (vg_replace_malloc.c:618)\n==34949== by 0x50CA83: xcalloc (wrapper.c:119)\n==34949== by 0x439AF6: cmd_index_pack (index-pack.c:1643)\n==34949== by 0x405B6A: handle_builtin (git.c:351)\n==34949== by 0x404CE8: main (git.c:575)\n==34949==\ngit: builtin/index-pack.c:918: find_unresolved_deltas_1: Assertion `child->real_type == OBJ_REF_DELTA' failed.\n==34949==\n==34949== For counts of detected and suppressed errors, rerun with: -v\n==34949== Use --history-level=approx or =none to gain increased speed, at\n==34949== the cost of reduced accuracy of conflicting-access information\n==34949== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 15 from 12)\nKilled\n\nIt only happens in one of ten cases or so. The write at index-pack.c\nline 865 is in resolve_delta() and sets real_type of a delta object to\nthe real_type of its base. It seems that threads can end up with work\nitems that end up requiring to touch another thread's part of the pie\nif there are duplicates.\n\nRené\n"},{"id":"248240","messageId":"CAJo=hJvF6dZdN9Y0CGuLFX__UQuRgYtM0xP7Ly2yCofxC1Yg2g@mail.gmail.com","threadId":"37389","inReplyTo":"20140823105640.GA6881@peff.net","subject":"Re: [BUG] resolved deltas","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-08-25T17:19:53Z","receivedAt":"2014-08-25T17:19:53Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Aug 23, 2014 at 3:56 AM, Jeff King wrote:\n> [+cc spearce, as I think this is a bug in code.google.com's sending\n> side, and he can probably get the attention of the right folks]\n...\n> My guess is a bug on the sending side. We have seen duplicate pack\n> objects before, but never (AFAIK) combined with a missing object. This\n> really seems like the sender just sent the wrong data for one object.\n>\n> IIRC, code.google.com is backed by their custom Dulwich implementation\n> which runs on BigTable. We'll see if Shawn can get this to the right\n> people as a bug report. :)\n\nThanks. This is a bug in the code.google.com implementation that is\nrunning on Bigtable. I forwarded the report to the team that manages\nthat service so they can investigate further.\n"},{"id":"248525","messageId":"20140828220821.GA31545@peff.net","threadId":"37389","inReplyTo":"53FB66D1.709@web.de","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-28T22:08:21Z","receivedAt":"2014-08-28T22:08:21Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 25, 2014 at 06:39:45PM +0200, René Scharfe wrote:\n\n> Thanks, that looks good. But while preparing the patch I noticed that\n> the added test sometimes fails. Helgrind pointed outet a race\n> condition. It is not caused by the patch to turn the asserts into\n> regular ifs, however -- here's a Helgrind report for the original code\n> with the new test:\n\nInteresting. I couldn't convince Helgrind to catch such a case, but it\nmakes sense. We split the delta-resolving work by dividing up the base\nobjects. We then find any deltas that need that base object (which is\nread-only). If there's only one instances of the base, then we'll be the\nonly thread working on those delta. But if there are two such bases,\nthey're going to look at the same deltas.\n\nSo we need some kind of mutual exclusion so that only one thread\nproceeds with resolving the delta. The \"real_type\" check sort-of\nfunctions in that way (except of course it is not actually thread safe).\nSo one obvious option is just a coarse-grained global lock to modify or\ncheck real_type fields. That would probably perform badly (lots of\nuseless lock contention on unrelated objects), but at least it would\nwork.\n\nIf we accept pushing a lock into _each_ object_entry, then we would get\na lot less lock contention (i.e., none at all in the common case of no\nduplicates). The cost is storing one lock per object, though. Not great,\nbut probably OK.\n\nIs there some way we can make real_type itself more atomic? I.e., use it\nas the mutex with the rule that we do not \"claim\" the object_entry as\nours to work on until we atomically set delta_obj->real_type. I think\ndoing a compare-and-swap looking for OBJ_REF_DELTA and replacing it with\nbase->real_type would be enough there (and substitute OBJ_OFS_DELTA for\nthe second conditional, of course).\n\nHowever, I'm not sure we can portably rely on having a compare-and-swap\nprimitive (or that we want to go through the hassle of conditionally\nusing it).\n\n-Peff\n"},{"id":"248526","messageId":"20140828221518.GA18799@peff.net","threadId":"37389","inReplyTo":"20140828220821.GA31545@peff.net","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-28T22:15:19Z","receivedAt":"2014-08-28T22:15:19Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 28, 2014 at 06:08:21PM -0400, Jeff King wrote:\n\n> So we need some kind of mutual exclusion so that only one thread\n> proceeds with resolving the delta. The \"real_type\" check sort-of\n> functions in that way (except of course it is not actually thread safe).\n\nHere's a patch which implements that. Since I couldn't replicate the\noriginal problem with helgrind, I am just guessing at whether it\nproperly fixes it (well, it is more than just a guess; I used my brain\nto analyze it, but that is far from foolproof).\n\nIt uses a single lock. I did a best-of-five timing of \"git index-pack\n--verify\" on the kernel repo, both before and after. The results ended\nup quite similar (both about 57s), though the run-to-run numbers are all\nover the place (up to about 65s in the worst case). So maybe it is not\nso bad.\n\nAs I implemented, I realized that even with the mutex, I really was just\nimplementing compare_and_swap (and I wrote it that way to make it more\nobvious). So if we wanted to, it would be trivial to replace the\n\"claim_delta\" function with a true compare-and-swap instruction if the\ncompiler and processor support it.\n\n---\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex f7dc5b0..ed9e253 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -112,6 +112,10 @@ static pthread_mutex_t deepest_delta_mutex;\n #define deepest_delta_lock()\tlock_mutex(&deepest_delta_mutex)\n #define deepest_delta_unlock()\tunlock_mutex(&deepest_delta_mutex)\n \n+static pthread_mutex_t object_entry_mutex;\n+#define object_entry_lock()\tlock_mutex(&object_entry_mutex)\n+#define object_entry_unlock()\tunlock_mutex(&object_entry_mutex)\n+\n static pthread_key_t key;\n \n static inline void lock_mutex(pthread_mutex_t *mutex)\n@@ -135,6 +139,7 @@ static void init_thread(void)\n \tinit_recursive_mutex(&read_mutex);\n \tpthread_mutex_init(&counter_mutex, NULL);\n \tpthread_mutex_init(&work_mutex, NULL);\n+\tpthread_mutex_init(&object_entry_mutex, NULL);\n \tif (show_stat)\n \t\tpthread_mutex_init(&deepest_delta_mutex, NULL);\n \tpthread_key_create(&key, NULL);\n@@ -157,6 +162,7 @@ static void cleanup_thread(void)\n \tpthread_mutex_destroy(&read_mutex);\n \tpthread_mutex_destroy(&counter_mutex);\n \tpthread_mutex_destroy(&work_mutex);\n+\tpthread_mutex_destroy(&object_entry_mutex);\n \tif (show_stat)\n \t\tpthread_mutex_destroy(&deepest_delta_mutex);\n \tfor (i = 0; i < nr_threads; i++)\n@@ -862,7 +868,6 @@ static void resolve_delta(struct object_entry *delta_obj,\n {\n \tvoid *base_data, *delta_data;\n \n-\tdelta_obj->real_type = base->obj->real_type;\n \tif (show_stat) {\n \t\tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n \t\tdeepest_delta_lock();\n@@ -888,6 +893,21 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tcounter_unlock();\n }\n \n+static int claim_delta(struct object_entry *delta_obj,\n+\t\t enum object_type delta_type,\n+\t\t enum object_type base_type)\n+{\n+\tenum object_type old_type;\n+\n+\tobject_entry_lock();\n+\told_type = delta_obj->real_type;\n+\tif (old_type == delta_type)\n+\t\tdelta_obj->real_type = base_type;\n+\tobject_entry_unlock();\n+\n+\treturn old_type == delta_type;\n+}\n+\n static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t\t\t\t struct base_data *prev_base)\n {\n@@ -914,7 +934,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \tif (base->ref_first <= base->ref_last) {\n \t\tstruct object_entry *child = objects + deltas[base->ref_first].obj_no;\n \n-\t\tif (child->real_type == OBJ_REF_DELTA) {\n+\t\tif (claim_delta(child, OBJ_REF_DELTA, base->obj->real_type)) {\n \t\t\tstruct base_data *result = alloc_base_data();\n \n \t\t\tresolve_delta(child, base, result);\n@@ -930,7 +950,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \tif (base->ofs_first <= base->ofs_last) {\n \t\tstruct object_entry *child = objects + deltas[base->ofs_first].obj_no;\n \n-\t\tif (child->real_type == OBJ_OFS_DELTA) {\n+\t\tif (claim_delta(child, OBJ_OFS_DELTA, base->obj->real_type)) {\n \t\t\tstruct base_data *result = alloc_base_data();\n \n \t\t\tresolve_delta(child, base, result);\n"},{"id":"248527","messageId":"20140828222227.GA30879@peff.net","threadId":"37389","inReplyTo":"20140828220821.GA31545@peff.net","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-28T22:22:27Z","receivedAt":"2014-08-28T22:22:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 28, 2014 at 06:08:21PM -0400, Jeff King wrote:\n\n> Interesting. I couldn't convince Helgrind to catch such a case...\n\nUgh. It helps if you actually helgrind the git binary, and not the\nshell-script from bin-wrappers. I can easily replicate the problem now.\nThe patch I just posted seems to fix it (at least it has been running in\na loop for over a minute with no failures, whereas before it took only a\nfew seconds to provoke a failure).\n\n-Peff\n"},{"id":"248530","messageId":"20140828230411.GA20484@peff.net","threadId":"37389","inReplyTo":"20140828221518.GA18799@peff.net","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-28T23:04:11Z","receivedAt":"2014-08-28T23:04:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 28, 2014 at 06:15:18PM -0400, Jeff King wrote:\n\n> As I implemented, I realized that even with the mutex, I really was just\n> implementing compare_and_swap (and I wrote it that way to make it more\n> obvious). So if we wanted to, it would be trivial to replace the\n> \"claim_delta\" function with a true compare-and-swap instruction if the\n> compiler and processor support it.\n\nThat's something like this on top:\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex ed9e253..1782a46 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -897,6 +897,10 @@ static int claim_delta(struct object_entry *delta_obj,\n \t\t enum object_type delta_type,\n \t\t enum object_type base_type)\n {\n+#ifdef __GCC_HAVE_SYNC_COMPARE_AND_SWAP_4\n+\treturn __sync_bool_compare_and_swap(&delta_obj->real_type, delta_type,\n+\t\t\t\t\t base_type);\n+#else\n \tenum object_type old_type;\n \n \tobject_entry_lock();\n@@ -906,6 +910,7 @@ static int claim_delta(struct object_entry *delta_obj,\n \tobject_entry_unlock();\n \n \treturn old_type == delta_type;\n+#endif\n }\n \n static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n\n\nThough I guess gcc's __sync stuff is old, and the new C11 thing is\nstdatomic.h. I guess we could support either if we can find the right\npreprocessor macros (I am not even sure if the above is correct; the \"4\"\nis for the size of the data type, but this is an enum, so we don't even\nknow what the right size is...).\n\nHowever, the above doesn't seem to be any faster for me, so it may not\nbe worth the hassle.\n\n-Peff\n"},{"id":"248531","messageId":"xmqq1ts08ax2.fsf@gitster.dls.corp.google.com","threadId":"37389","inReplyTo":"20140828222227.GA30879@peff.net","subject":"Re: [BUG] resolved deltas","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-08-28T23:14:01Z","receivedAt":"2014-08-28T23:14:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Thu, Aug 28, 2014 at 06:08:21PM -0400, Jeff King wrote:\n>\n>> Interesting. I couldn't convince Helgrind to catch such a case...\n>\n> Ugh. It helps if you actually helgrind the git binary, and not the\n> shell-script from bin-wrappers. I can easily replicate the problem now.\n> The patch I just posted seems to fix it (at least it has been running in\n> a loop for over a minute with no failures, whereas before it took only a\n> few seconds to provoke a failure).\n\nThanks for digging. I'll pick it up and may comment on it in\ntomorrow's cycle (it is a bit too late for today's cycle,\nunfortunately).\n"},{"id":"248587","messageId":"20140829205538.GD29456@peff.net","threadId":"37389","inReplyTo":"xmqq1ts08ax2.fsf@gitster.dls.corp.google.com","subject":"Re: [BUG] resolved deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-29T20:55:38Z","receivedAt":"2014-08-29T20:55:38Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 28, 2014 at 04:14:01PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > On Thu, Aug 28, 2014 at 06:08:21PM -0400, Jeff King wrote:\n> >\n> >> Interesting. I couldn't convince Helgrind to catch such a case...\n> >\n> > Ugh. It helps if you actually helgrind the git binary, and not the\n> > shell-script from bin-wrappers. I can easily replicate the problem now.\n> > The patch I just posted seems to fix it (at least it has been running in\n> > a loop for over a minute with no failures, whereas before it took only a\n> > few seconds to provoke a failure).\n> \n> Thanks for digging. I'll pick it up and may comment on it in\n> tomorrow's cycle (it is a bit too late for today's cycle,\n> unfortunately).\n\nHere's a proposed series.\n\n [1/2]: index-pack: fix race condition with duplicate bases\n [2/2]: index-pack: handle duplicate base objects gracefully\n\nThere are two big changes from what has been posted already:\n\n 1. While writing up the commit message, I realized that this can't\n ever happen for OFS_DELTA (neither the race condition, nor the\n duplicate resolution) because offsets by definition point to a\n unique entry in our object_entry array. So even if we have multiple\n copies of the base object in the pack, there's only one possible\n base for an OFS_DELTA.\n\n 2. René's original patch just does nothing for a delta which has\n already been resolved, and continues through the function to try\n any OFS_DELTA objects. If there isn't one, we return NULL to say\n \"nothing left to resolve\". But that's not quite true. There may\n have been other REF_DELTA against the same base, but we never\n incremented our counter to find it.\n\n Instead, we need to actually increment our counter and loop again\n to see if there's another REF_DELTA to handle.\n\n-Peff\n"},{"id":"248590","messageId":"20140829205746.GA7060@peff.net","threadId":"37389","inReplyTo":"20140829205538.GD29456@peff.net","subject":"[PATCH 1/2] index-pack: fix race condition with duplicate bases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-29T20:57:47Z","receivedAt":"2014-08-29T20:57:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are resolving deltas in an indexed pack, we do it by\nfirst selecting a potential base (either one stored in full\nin the pack, or one created by resolving another delta), and\nthen resolving any deltas that use that base. When we\nresolve a particular delta, we flip its \"real_type\" field\nfrom OBJ_{REF,OFS}_DELTA to whatever the real type is.\n\nWe assume that traversing the objects this way will visit\neach delta only once. This is correct for most packs; we\nvisit the delta only when we process its base, and each\nobject (and thus each base) appears only once. However, if a\nbase object appears multiple times in the pack, we will try\nto resolve any deltas based on it once for each instance.\n\nWe can detect this case by noting that a delta we are about\nto resolve has already had its real_type field flipped, and\nwe already do so with an assert(). However, if multiple\nthreads are in use, we may race with another thread on\ncomparing and flipping the field. We need to synchronize the\naccess.\n\nThe right mechanism for doing this is a compare-and-swap (we\natomically \"claim\" the delta for our own and find out\nwhether our claim was successful). We can implement this\nin C by using a pthread mutex to protect the operation. This\nis not the fastest way of doing a compare-and-swap; many\nprocessors provide instructions for this, and gcc and other\ncompilers provide builtins to access them. However, some\nexperiments showed that lock contention does not cause a\nsignificant slowdown here. Adding c-a-s support for many\ncompilers would increase the maintenance burden (and we\nwould still end up including the pthread version as a\nfallback).\n\nNote that we only need to touch the OBJ_REF_DELTA codepath\nhere. An OBJ_OFS_DELTA object points to its base using an\noffset, and therefore has only one base, even if another\ncopy of that base object appears in the pack (we do still\ntouch it briefly because the setting of real_type is\nfactored out of resolve_data).\n\nSigned-off-by: Jeff King \n---\n builtin/index-pack.c | 33 +++++++++++++++++++++++++++++++--\n 1 file changed, 31 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 5568a5b..eebf1a8 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -112,6 +112,10 @@ static pthread_mutex_t deepest_delta_mutex;\n #define deepest_delta_lock()\tlock_mutex(&deepest_delta_mutex)\n #define deepest_delta_unlock()\tunlock_mutex(&deepest_delta_mutex)\n \n+static pthread_mutex_t type_cas_mutex;\n+#define type_cas_lock()\t\tlock_mutex(&type_cas_mutex)\n+#define type_cas_unlock()\tunlock_mutex(&type_cas_mutex)\n+\n static pthread_key_t key;\n \n static inline void lock_mutex(pthread_mutex_t *mutex)\n@@ -135,6 +139,7 @@ static void init_thread(void)\n \tinit_recursive_mutex(&read_mutex);\n \tpthread_mutex_init(&counter_mutex, NULL);\n \tpthread_mutex_init(&work_mutex, NULL);\n+\tpthread_mutex_init(&type_cas_mutex, NULL);\n \tif (show_stat)\n \t\tpthread_mutex_init(&deepest_delta_mutex, NULL);\n \tpthread_key_create(&key, NULL);\n@@ -157,6 +162,7 @@ static void cleanup_thread(void)\n \tpthread_mutex_destroy(&read_mutex);\n \tpthread_mutex_destroy(&counter_mutex);\n \tpthread_mutex_destroy(&work_mutex);\n+\tpthread_mutex_destroy(&type_cas_mutex);\n \tif (show_stat)\n \t\tpthread_mutex_destroy(&deepest_delta_mutex);\n \tfor (i = 0; i < nr_threads; i++)\n@@ -862,7 +868,6 @@ static void resolve_delta(struct object_entry *delta_obj,\n {\n \tvoid *base_data, *delta_data;\n \n-\tdelta_obj->real_type = base->obj->real_type;\n \tif (show_stat) {\n \t\tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n \t\tdeepest_delta_lock();\n@@ -888,6 +893,26 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tcounter_unlock();\n }\n \n+/*\n+ * Standard boolean compare-and-swap: atomically check whether \"*type\" is\n+ * \"want\"; if so, swap in \"set\" and return true. Otherwise, leave it untouched\n+ * and return false.\n+ */\n+static int compare_and_swap_type(enum object_type *type,\n+\t\t\t\t enum object_type want,\n+\t\t\t\t enum object_type set)\n+{\n+\tenum object_type old;\n+\n+\ttype_cas_lock();\n+\told = *type;\n+\tif (old == want)\n+\t\t*type = set;\n+\ttype_cas_unlock();\n+\n+\treturn old == want;\n+}\n+\n static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t\t\t\t struct base_data *prev_base)\n {\n@@ -915,7 +940,10 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\tstruct object_entry *child = objects + deltas[base->ref_first].obj_no;\n \t\tstruct base_data *result = alloc_base_data();\n \n-\t\tassert(child->real_type == OBJ_REF_DELTA);\n+\t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n+\t\t\t\t\t base->obj->real_type))\n+\t\t\tdie(\"BUG: child->real_type != OBJ_REF_DELTA\");\n+\n \t\tresolve_delta(child, base, result);\n \t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n \t\t\tfree_base_data(base);\n@@ -929,6 +957,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\tstruct base_data *result = alloc_base_data();\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n+\t\tchild->real_type = base->obj->real_type;\n \t\tresolve_delta(child, base, result);\n \t\tif (base->ofs_first == base->ofs_last)\n \t\t\tfree_base_data(base);\n-- \n2.1.0.346.ga0367b9\n"},{"id":"248591","messageId":"20140829205809.GB7060@peff.net","threadId":"37389","inReplyTo":"20140829205538.GD29456@peff.net","subject":"[PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-29T20:58:10Z","receivedAt":"2014-08-29T20:58:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If a pack contains duplicates of an object, and if that\nobject has any deltas pointing at it with REF_DELTA, we will\ntry to resolve the deltas twice. While unusual, this is not\nstrictly an error, but we currently die() with an unhelpful\nmessage. We should instead silently ignore the delta and\nmove on. The first resolution already filled in any data we\nneeded (like the sha1).\n\nThe duplicate base object is not our concern during the\nresolution phase, and the .idx-writing phase will decide\nwhether to complain or allow it (based on whether --strict\nis set).\n\nBased-on-work-by: René Scharfe \nSigned-off-by: Jeff King \n---\n builtin/index-pack.c | 18 ++++++++++--------\n t/t5308-pack-detect-duplicates.sh | 15 +++++++++++++++\n 2 files changed, 25 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex eebf1a8..acc30a9 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -936,20 +936,22 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\tlink_base_data(prev_base, base);\n \t}\n \n-\tif (base->ref_first <= base->ref_last) {\n+\twhile (base->ref_first <= base->ref_last) {\n \t\tstruct object_entry *child = objects + deltas[base->ref_first].obj_no;\n-\t\tstruct base_data *result = alloc_base_data();\n+\t\tstruct base_data *result = NULL;\n \n-\t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n-\t\t\t\t\t base->obj->real_type))\n-\t\t\tdie(\"BUG: child->real_type != OBJ_REF_DELTA\");\n+\t\tif (compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n+\t\t\t\t\t base->obj->real_type)) {\n+\t\t\tresult = alloc_base_data();\n+\t\t\tresolve_delta(child, base, result);\n+\t\t}\n \n-\t\tresolve_delta(child, base, result);\n \t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n \t\t\tfree_base_data(base);\n-\n \t\tbase->ref_first++;\n-\t\treturn result;\n+\n+\t\tif (result)\n+\t\t\treturn result;\n \t}\n \n \tif (base->ofs_first <= base->ofs_last) {\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 9c5a876..50f7a69 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -77,4 +77,19 @@ test_expect_success 'index-pack can reject packs with duplicates' '\n \ttest_expect_code 1 git cat-file -e $LO_SHA1\n '\n \n+test_expect_success 'duplicated delta base does not trigger assert' '\n+\tclear_packs &&\n+\t{\n+\t\tA=01d7713666f4de822776c7622c10f1b07de280dc &&\n+\t\tB=e68fe8129b546b101aee9510c5328e7f21ca1d18 &&\n+\t\tpack_header 3 &&\n+\t\tpack_obj $A $B &&\n+\t\tpack_obj $B &&\n+\t\tpack_obj $B\n+\t} >dups.pack &&\n+\tpack_trailer dups.pack &&\n+\tgit index-pack --stdin writes:\n\n> If a pack contains duplicates of an object, and if that\n> object has any deltas pointing at it with REF_DELTA, we will\n> try to resolve the deltas twice. While unusual, this is not\n> strictly an error, but we currently die() with an unhelpful\n> message.\n\nHmm, I vaguely recall Shawn declaring this as an error in the pack\nstream, though.\n\n> The duplicate base object is not our concern during the\n> resolution phase, and the .idx-writing phase will decide\n> whether to complain or allow it (based on whether --strict\n> is set).\n\nOK. We still diagnose and just be more lenient without loosening\nthe correctness of the result, so that would be not just OK but a\nvery welcome change.\n\nWill queue. Thanks.\n"},{"id":"248595","messageId":"20140829220818.GA24834@peff.net","threadId":"37389","inReplyTo":"xmqqegvz3qpp.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-29T22:08:19Z","receivedAt":"2014-08-29T22:08:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 29, 2014 at 02:56:18PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > If a pack contains duplicates of an object, and if that\n> > object has any deltas pointing at it with REF_DELTA, we will\n> > try to resolve the deltas twice. While unusual, this is not\n> > strictly an error, but we currently die() with an unhelpful\n> > message.\n> \n> Hmm, I vaguely recall Shawn declaring this as an error in the pack\n> stream, though.\n\nI agree it is probably a bug on the sending side, but I think last time\nthis came up we decided to try to be liberal in what we accept. c.f.\nhttp://thread.gmane.org/gmane.comp.version-control.git/232305/focus=232310\n\n-Peff\n"},{"id":"248603","messageId":"CAJo=hJs3mM7=LcOop-WD=bipA=Wx-7MDh6ObQwFUE38tjurvcw@mail.gmail.com","threadId":"37389","inReplyTo":"20140829220818.GA24834@peff.net","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-08-30T02:59:32Z","receivedAt":"2014-08-30T02:59:32Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Aug 29, 2014 at 3:08 PM, Jeff King wrote:\n> On Fri, Aug 29, 2014 at 02:56:18PM -0700, Junio C Hamano wrote:\n>\n>> Jeff King writes:\n>>\n>> > If a pack contains duplicates of an object, and if that\n>> > object has any deltas pointing at it with REF_DELTA, we will\n>> > try to resolve the deltas twice. While unusual, this is not\n>> > strictly an error, but we currently die() with an unhelpful\n>> > message.\n>>\n>> Hmm, I vaguely recall Shawn declaring this as an error in the pack\n>> stream, though.\n>\n> I agree it is probably a bug on the sending side, but I think last time\n> this came up we decided to try to be liberal in what we accept. c.f.\n> http://thread.gmane.org/gmane.comp.version-control.git/232305/focus=232310\n\nIIRC they aren't valid pack files to contain duplicates.\n\nOnce upon a time JGit had a bug and android.googlesource.com returned\nduplicate objects in a Linux kernel repository. This caused at least\nsome versions of git-core to fail very badly in binary search at\nobject lookup time or something. We had a lot of users angry with us.\n:)\n\nI know Nico said its OK last year, but its really not. I don't think\nimplementations are capable of handling it.\n"},{"id":"248647","messageId":"20140830131649.GA26833@peff.net","threadId":"37389","inReplyTo":"CAJo=hJs3mM7=LcOop-WD=bipA=Wx-7MDh6ObQwFUE38tjurvcw@mail.gmail.com","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-30T13:16:49Z","receivedAt":"2014-08-30T13:16:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 29, 2014 at 07:59:32PM -0700, Shawn Pearce wrote:\n\n> > I agree it is probably a bug on the sending side, but I think last time\n> > this came up we decided to try to be liberal in what we accept. c.f.\n> > http://thread.gmane.org/gmane.comp.version-control.git/232305/focus=232310\n> \n> IIRC they aren't valid pack files to contain duplicates.\n> \n> Once upon a time JGit had a bug and android.googlesource.com returned\n> duplicate objects in a Linux kernel repository. This caused at least\n> some versions of git-core to fail very badly in binary search at\n> object lookup time or something. We had a lot of users angry with us.\n> :)\n> \n> I know Nico said its OK last year, but its really not. I don't think\n> implementations are capable of handling it.\n\nWe do detect and complain if --strict is given. Should we make it the\ndefault instead? I think it is still worthwhile to have a mode that can\nhandle these packs. It may be the only reasonable way to recover the\ndata from such a broken pack (and that broken pack may be the only copy\nof the data you have, if you are stuck getting it out of a broken\nimplementation on a remote server).\n\n-Peff\n"},{"id":"248648","messageId":"20140830132311.GA14709@peff.net","threadId":"37389","inReplyTo":"20140829205538.GD29456@peff.net","subject":"[PATCH 3/2] t5309: mark delta-cycle failover tests as passing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-30T13:23:12Z","receivedAt":"2014-08-30T13:23:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"t5309 checks that we detect and fail when there is a cycle\nof deltas (i.e., A is a delta on B, which is a delta on A).\nIt also checks the cases where we have such a cycle, but we\nhave an extra copy of the object either in the same pack or\nin another one. These cases are recoverable, because we can\nuse the alternate copy to reconstruct the delta object.\n\nHowever, it did not work in practice (and the tests were\nmarked as expect_failure) because it led to us trying to\nresolve some deltas multiple times, something we assert()\nshould not happen. E.g., we'd see the full base A, use it to\nresolve delta B on top of A, then use that to resolve the\ndelta A on top of B, and then finally try resolving B on top\nof A again.\n\nSince the previous commit, we handle duplicate bases more\ngracefully, and the tests pass. While we're here, let's also\nmake the tests a little more robust:\n\n 1. For the case of finding the extra base in the same\n pack, we do not need to use --fix-thin; it should (and\n does) work without it.\n\n 2. Confirm that the resulting pack has a duplicate object.\n In the case of using --fix-thin to pull the object from\n another pack, the duplicate is added to the pack by us\n (this is a good thing, as otherwise future readers\n would encounter the cycle again).\n\nSigned-off-by: Jeff King \n---\nAn obvious follow-on to the other two patches.\n\nThe implications of this make me slightly nervous, though. In the\n--fix-thin case, the resulting pack will have 3 objects:\n\n - A as a delta on B\n - B as a delta on A\n - a full copy of either A (or B) provided by --fix-thin\n\nWe create a .idx that has duplicate entries for A. If a reader is trying\nto reconstruct B and they find the full copy of A, they're fine. If they\nfind the delta copy, what happens?\n\nIdeally the reader would say \"hey, I can't reconstruct A here, let me\ntry to find another copy\". But I am not sure if that happens, or if we\nare even capable of finding another copy of A (certainly we can find one\nin another pack, but I do not think we are smart enough to find a\nduplicate in the same pack).\n\nBy definition, we have a copy in another pack here (that is where the\n--fix-thin base came from), but there is nothing to guarantee that the\nother pack lives on.\n\n t/t5309-pack-delta-cycles.sh | 10 ++++++----\n 1 file changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 3e7861b..5309095 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -56,13 +56,14 @@ test_expect_success 'index-pack detects REF_DELTA cycles' '\n \ttest_must_fail git index-pack --fix-thin --stdin recoverable.pack &&\n \tpack_trailer recoverable.pack &&\n-\tgit index-pack --fix-thin --stdin On Fri, Aug 29, 2014 at 07:59:32PM -0700, Shawn Pearce wrote:\n>\n>>> I agree it is probably a bug on the sending side, but I think last time\n>>> this came up we decided to try to be liberal in what we accept. c.f.\n>>> http://thread.gmane.org/gmane.comp.version-control.git/232305/focus=232310\n>>\n>> IIRC they aren't valid pack files to contain duplicates.\n>>\n>> Once upon a time JGit had a bug and android.googlesource.com returned\n>> duplicate objects in a Linux kernel repository. This caused at least\n>> some versions of git-core to fail very badly in binary search at\n>> object lookup time or something. We had a lot of users angry with us.\n>> :)\n>>\n>> I know Nico said its OK last year, but its really not. I don't think\n>> implementations are capable of handling it.\n>\n> We do detect and complain if --strict is given. Should we make it the\n> default instead? I think it is still worthwhile to have a mode that can\n> handle these packs. It may be the only reasonable way to recover the\n> data from such a broken pack (and that broken pack may be the only copy\n> of the data you have, if you are stuck getting it out of a broken\n> implementation on a remote server).\n\nSounds reasonable; being able to extract code from broken repos -- \nespecially in this real-world case -- is beneficial.\n\nMy only nit with patch 2: Petr Stodulka and Martin \nvon Gagern should be mentioned as bug reporters.\n\nRené\n"},{"id":"248670","messageId":"CAJo=hJu-DCMv=jepMJvcmR9EOedkynCyL0kD_hB+UGWxbErDfA@mail.gmail.com","threadId":"37389","inReplyTo":"20140830131649.GA26833@peff.net","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-08-31T01:10:33Z","receivedAt":"2014-08-31T01:10:33Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Aug 30, 2014 at 6:16 AM, Jeff King wrote:\n> On Fri, Aug 29, 2014 at 07:59:32PM -0700, Shawn Pearce wrote:\n>\n>> > I agree it is probably a bug on the sending side, but I think last time\n>> > this came up we decided to try to be liberal in what we accept. c.f.\n>> > http://thread.gmane.org/gmane.comp.version-control.git/232305/focus=232310\n>>\n>> IIRC they aren't valid pack files to contain duplicates.\n>>\n>> Once upon a time JGit had a bug and android.googlesource.com returned\n>> duplicate objects in a Linux kernel repository. This caused at least\n>> some versions of git-core to fail very badly in binary search at\n>> object lookup time or something. We had a lot of users angry with us.\n>> :)\n>>\n>> I know Nico said its OK last year, but its really not. I don't think\n>> implementations are capable of handling it.\n>\n> We do detect and complain if --strict is given. Should we make it the\n> default instead? I think it is still worthwhile to have a mode that can\n> handle these packs. It may be the only reasonable way to recover the\n> data from such a broken pack (and that broken pack may be the only copy\n> of the data you have, if you are stuck getting it out of a broken\n> implementation on a remote server).\n\nEh, OK, that does make a lot of sense.\n\nUnfortunately accepting it by default encourages broken\nimplementations to stay broken and ship packs with duplicate objects,\nwhich they shouldn't do since there are readers out there that cannot\nhandle it.\n\nIn my opinion we should make --strict default, but its an excellent\npoint made that users should have an escape hatch to disable this\ncheck, attempt accepting a broken pack and try fixing it locally with\nrepack.\n"},{"id":"248682","messageId":"20140831151550.GA16499@peff.net","threadId":"37389","inReplyTo":"20140830132311.GA14709@peff.net","subject":"Re: [PATCH 3/2] t5309: mark delta-cycle failover tests as passing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-31T15:15:50Z","receivedAt":"2014-08-31T15:15:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 30, 2014 at 09:23:11AM -0400, Jeff King wrote:\n\n> The implications of this make me slightly nervous, though. In the\n> --fix-thin case, the resulting pack will have 3 objects:\n> \n> - A as a delta on B\n> - B as a delta on A\n> - a full copy of either A (or B) provided by --fix-thin\n> \n> We create a .idx that has duplicate entries for A. If a reader is trying\n> to reconstruct B and they find the full copy of A, they're fine. If they\n> find the delta copy, what happens?\n> \n> Ideally the reader would say \"hey, I can't reconstruct A here, let me\n> try to find another copy\". But I am not sure if that happens, or if we\n> are even capable of finding another copy of A (certainly we can find one\n> in another pack, but I do not think we are smart enough to find a\n> duplicate in the same pack).\n\nThe main reason this was \"makes me nervous\" before is that I did not\nfully understand _why_ it worked with the current code. That bugged me,\nso I dug further. And the answer is that it does not, but just happens\nto work for some small cases.\n\nTry this on top:\n\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 5309095..4086983 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -58,9 +58,19 @@ test_expect_success 'index-pack detects REF_DELTA cycles' '\n \n test_expect_success 'failover to an object in another pack' '\n \tclear_packs &&\n+\t{\n+\t\tpack_header 100 &&\n+\t\tfor i in $(test_seq 50); do\n+\t\t\tpack_obj $A $B &&\n+\t\t\tpack_obj $B $A || break\n+\t\tdone\n+\t} >megacycle.pack &&\n+\tpack_trailer megacycle.pack &&\n \tgit index-pack --stdin &2 indexed pack successfully... &&\n+\tgit fsck &&\n+\techo >&2 actually re-read pack successfully\n '\n \n test_expect_success 'failover to a duplicate object in the same pack' '\n\n\nIt has the same cycle problem, but we are just adding a larger number of\ninstances to the pack. Which means that any given sha1-lookup in the\nindex is more likely to hit a delta rather than the base object.\n\nWe successfully index the pack, but our fsck goes into an infinite loop.\nYikes.\n\nI haven't really looked into it, but I suspect we would need some kind\nof cycle detection on the delta resolution (and possibly to teach the\nsha1-lookup to recognize duplicate objects in the pack and treat them\nindividually). Frankly, I don't think it is worth the effort or\ncomplexity. We should probably just declare delta cycles insane and\nreject them outright.\n\nWe used to do that because the only way to correctly resolve them was by\nintroducing a duplicate base object, and we did not allow that. Patch 2\nfrom my series loosened this, which makes index-pack work, but not\nnecessarily the rest of git. And since index-pack is the gatekeeper on\nreceiving objects from remotes, it needs to be the _most_ picky. So my\nseries is definitely a regression as-is.\n\nWe can solve this in one of three ways:\n\n 1. Teach the rest of git to handle recoverable delta cycles. This is\n probably crazy and not worth the effort (and it just lets crap\n through that will hurt other git implementations, too).\n\n 2. Continue to let through duplicate objects in index-pack, but\n specifically detect and reject delta cycles. This is more work (I'm\n not sure yet how easy it would be to detect cycles), but it would\n mean we can treat duplicates (a much less nasty problem) and cycles\n differently.\n\n 3. Go back to outlawing duplicate bases. This is very easy. Just drop\n my patch 2. :)\n\nI am inclined to go with the third option. There has already been a\nsuggestion from Shawn that we disallow duplicates entirely, and I was\ntempted to go that direction even without this finding. But to me this\nmakes it a no-brainer; the question has gone from \"how strict do we want\nto be\" to \"do we want to protect the rest of the code against useless\nand potentially harmful violations of their assumptions\".\n\nIf we do go with (3), that opens up two new questions:\n\n a. Should we disallow _all_ duplicates, or just those that are bases?\n This is actually easy to code; the assert() in find_unresolved_deltas\n catches the bases, and the .idx writer catches any other ones.\n\n b. How optional do we want to make this? Right now (without this\n series) the delta-base duplicates always die, and regular\n duplicates are prevented only under --strict.\n\n If we treat them the same, it should probably be die-by-default.\n Should there be an optional mode to let this stuff through (i.e., a\n \"I know this might cause problems with the rest of git, but I am\n desperate to get the data out of this pack\" mode?)\n\n If we treat them differently, there is not much harm in an option\n to loosen regular duplicates, as I think the rest of git handles\n it. For bases, in theory you might be able to recover some data.\n But you may also run into this infinite loop. It is very much \"at\n your own risk\".\n\n I wonder if index-pack is really the right place for such a \"please\n help me get the data out of this broken pack\" operation in the\n first place. If it is a broken pack, we are probably much better\n off to explode it into loose objects than try to index a broken\n pack. That's way less efficient, but this should be a last-resort.\n\nI think my preference is to outlaw all duplicates unconditionally in\nindex-pack. Catch the duplicate base in find_unresolved_deltas as we do\nnow, but improve the error message. Confirm that unpack-objects can\nhandle these cases. Optionally attach advice to the duplicate errors\ndirecting people to use \"unpack-objects\" and/or set\ntransfer.unpackLimit higher.\n\n-Peff\n"},{"id":"248683","messageId":"20140831151753.GA17449@peff.net","threadId":"37389","inReplyTo":"5401F53B.6070707@web.de","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-31T15:17:53Z","receivedAt":"2014-08-31T15:17:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 30, 2014 at 06:00:59PM +0200, René Scharfe wrote:\n\n> My only nit with patch 2: Petr Stodulka and Martin von\n> Gagern should be mentioned as bug reporters.\n\nYeah, I agree with that. And actually, you should get a Reported-by:\non the first patch. :)\n\nHowever, I think there are some grave implications of this series; see\nthe message I just posted elsewhere in the thread. I think we will end\nup dropping patch 2, but keep patch 1.\n\n-Peff\n"},{"id":"248684","messageId":"20140831152437.GB17449@peff.net","threadId":"37389","inReplyTo":"CAJo=hJu-DCMv=jepMJvcmR9EOedkynCyL0kD_hB+UGWxbErDfA@mail.gmail.com","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-31T15:24:38Z","receivedAt":"2014-08-31T15:24:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 30, 2014 at 06:10:33PM -0700, Shawn Pearce wrote:\n\n> > We do detect and complain if --strict is given. Should we make it the\n> > default instead? I think it is still worthwhile to have a mode that can\n> > handle these packs. It may be the only reasonable way to recover the\n> > data from such a broken pack (and that broken pack may be the only copy\n> > of the data you have, if you are stuck getting it out of a broken\n> > implementation on a remote server).\n> \n> Eh, OK, that does make a lot of sense.\n> \n> Unfortunately accepting it by default encourages broken\n> implementations to stay broken and ship packs with duplicate objects,\n> which they shouldn't do since there are readers out there that cannot\n> handle it.\n\nI was pretty much convinced by this line of reasoning after you reading\nyour message. But after discovering some horrible side effects that I\njust posted elsewhere, I think it's a no-brainer.\n\n> In my opinion we should make --strict default, but its an excellent\n> point made that users should have an escape hatch to disable this\n> check, attempt accepting a broken pack and try fixing it locally with\n> repack.\n\nI am not sure if you meant it this way, but --strict controls a lot more\nthan just duplicate objects. It also runs fsck checks against the\nincoming objects. Turning all of that on is a much bigger change than I\nthink we've been talking about.\n\nBut it's one I think we should consider. We've had --strict on at GitHub\nfor a few years, and it has caught many problems. Frequently we get\npush-back from users saying \"but nowhere else I pushed this to\ncomplains\". My opinion is that it is not that we are wrong for being\npicky, but that other servers are not being picky enough.\n\nIt's also a bit of a hassle, though. E.g., a lot of projects have broken\nident lines deep in their history (from old versions of git, or other\nbroken implementations) and it is often way too late to fix them. We\nusually try to get people to rewrite the history if it's not a problem,\nbut otherwise will lift the restrictions temporarily to let them push up\nold history.\n\nBroken ident lines are annoying, but not _too_ fundamentally bad.\nDuplicate tree entries are a lot worse. Fsck even distinguishes between\n\"error\" and \"warning\", but \"index-pack --strict\" treats both as a reason\nto reject the object. We could perhaps loosen that, and make sure our\nerror/warning categories are reasonable.\n\n-Peff\n"},{"id":"248688","messageId":"54034DAF.7030203@web.de","threadId":"37389","inReplyTo":"20140831151753.GA17449@peff.net","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-08-31T16:30:39Z","receivedAt":"2014-08-31T16:30:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 31.08.2014 um 17:17 schrieb Jeff King:\n> On Sat, Aug 30, 2014 at 06:00:59PM +0200, René Scharfe wrote:\n>\n>> My only nit with patch 2: Petr Stodulka and Martin von\n>> Gagern should be mentioned as bug reporters.\n>\n> Yeah, I agree with that. And actually, you should get a Reported-by:\n> on the first patch. :)\n>\n> However, I think there are some grave implications of this series; see\n> the message I just posted elsewhere in the thread. I think we will end\n> up dropping patch 2, but keep patch 1.\n\nOK, but it would still be a good idea to replace the assert()s with \ndie()s and error messages that tell users that the repo is broken, not git.\n\nRené\n"},{"id":"248695","messageId":"xmqq38cc47tp.fsf@gitster.dls.corp.google.com","threadId":"37389","inReplyTo":"20140831152437.GB17449@peff.net","subject":"Re: [PATCH 2/2] index-pack: handle duplicate base objects gracefully","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-08-31T22:23:30Z","receivedAt":"2014-08-31T22:23:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Broken ident lines are annoying, but not _too_ fundamentally bad.\n> Duplicate tree entries are a lot worse. Fsck even distinguishes between\n> \"error\" and \"warning\", but \"index-pack --strict\" treats both as a reason\n> to reject the object. We could perhaps loosen that, and make sure our\n> error/warning categories are reasonable.\n\nA pack stream that records the same object twice is not a breakage\nthat is buried deep in the history and cannot be corrected without a\nwholesale history rewrite, unlike commit objects with broken ident\nlines or tree objects with 0-filled file type designators.\n\nAs such, I think it is a reasonable thing to do the following:\n\n - \"git repack\" should be taught to dedup, as a way to recover from\n such a breakage, if not done already.\n\n - \"git fsck\" should complain, suggesting users to repack to\n recover. It may even want to exit with non-zero status.\n\n - \"git receive-pack\" and \"git fetch-pack\" should warn, loudly,\n without failing. They should ideally not keep such a corrupt\n pack stream on disk at all, de-duping the objects while\n streaming, but if that is not practical, at least they should\n give an easy way for the user to cause de-duping immediately (I\n do not mind if that is \"we detected that the other side fed us a\n pack stream that is broken. We automatically correct the\n breakage for you by repacking. Be patient while we do so\").\n\n - If the other side of \"receive-pack/fetch-pack\" implements the\n agent capability, upon detecting such a breakage, it may not be a\n bad idea to offer the user to send an e-mail reporting the\n version of the software to a wall-of-shame e-mail address ;-).\n\nI agree that a tree that records the same path twice should be\noutright rejected. There is no sane recovery path.\n"},{"id":"248717","messageId":"xmqqoauy2b4m.fsf@gitster.dls.corp.google.com","threadId":"37389","inReplyTo":"20140831151550.GA16499@peff.net","subject":"Re: [PATCH 3/2] t5309: mark delta-cycle failover tests as passing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-09-02T17:19:37Z","receivedAt":"2014-09-02T17:19:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> We used to do that because the only way to correctly resolve them was by\n> introducing a duplicate base object, and we did not allow that. Patch 2\n> from my series loosened this, which makes index-pack work, but not\n> necessarily the rest of git. And since index-pack is the gatekeeper on\n> receiving objects from remotes, it needs to be the _most_ picky. So my\n> series is definitely a regression as-is.\n\nYeah, at first, allowing the delta resolution so that we can\nresurrect data from such a corrupt pack looked a no-brainer\nimprovement, but I think that is probably a right conclusion.\nThanks for digging this one through.\n\n> I wonder if index-pack is really the right place for such a \"please\n> help me get the data out of this broken pack\" operation in the\n> first place. If it is a broken pack, we are probably much better\n> off to explode it into loose objects than try to index a broken\n> pack. That's way less efficient, but this should be a last-resort.\n\nMost objects in such a broken pack do not have to get unpacked, no?\nI wonder if we can excise duplicate objects from the pack stream,\nwhich would involve adjusting the delta offset for any ofs-delta\nrepresentations that appear after the part we cut out of the stream\nto remove such cruft.\n"}]}