{"thread":{"id":"34695","subject":"duplicate objects in packfile","startedAt":"2013-08-14T18:17:18Z","lastAt":"2013-08-24T00:02:45Z","messageCount":37,"participants":["Jeff King","Junio C Hamano","Nicolas Pitre","Duy Nguyen","Johannes Sixt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"225221","messageId":"20130814181718.GA7911@sigill.intra.peff.net","threadId":"34695","inReplyTo":null,"subject":"duplicate objects in packfile","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-14T18:17:18Z","receivedAt":"2013-08-14T18:17:18Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I'm tracking down a rather odd problem in a packfile I found on GitHub.\nThis particular packfile contains the same object at various offsets\nwithin the file. In fact there are several packfiles that exhibit this\nbehavior, all in the same repository, and in each one there are several\nduplicated objects (some of which are present 3 or even 4 times).\n\nindex-pack is happy to index these packfiles, and just creates multiple\nentries for the object. The usual binary search in find_pack_entry_one\nwill find one of them (though of course which depends on the exact\nlayout of the index). But curiously, the experimental sha1_entry_pos\nlookup does not. It hits an assert() that can only be triggered in the\nface of duplicate objects. For example:\n\n $ git cat-file -t 4ea4acbcb0930ac42acc87a0d203864dec1a9697\n commit\n\n $ GIT_USE_LOOKUP=1 git cat-file -t 4ea4acbcb0930ac42acc87a0d203864dec1a9697\n git: sha1-lookup.c:222: sha1_entry_pos: Assertion `lov < hiv' failed.\n Aborted\n\nIt's easy enough to fix with a repack, but I am curious:\n\n 1. Is sha1_entry_pos wrong to barf on duplicate items in the index? If\n so, do we want to fix it, or simply retire GIT_USE_LOOKUP?\n\n Related, should we consider duplicate items in a packfile to be a\n bogus packfile (and consequently notice and complain during\n indexing)? I don't think it _hurts_ anything (aside from the assert\n above), though it is of course wasteful.\n\n I didn't go into detail on how the assertion above is triggered,\n but I can break it down line by line if anybody cares; the short of\n it is that it can only be caused by an unsorted index or a\n duplicate entry.\n\n 2. How can duplicate entries get into a packfile?\n\n Git itself should not generate duplicate entries (pack-objects is\n careful to remove duplicates). Since these packs almost certainly\n were pushed by a client, I wondered if \"index-pack --fix-thin\"\n might accidentally add multiple copies of an object when it is the\n preferred base for multiple objects, but it specifically avoids\n doing so.\n\n The packs in question were received by us in 2010. Did we ever have\n bugs in this area? I don't recall any, nor could I find any in the\n history.\n\n That makes me suspect the user may have been using an alternate git\n implementation. libgit2 did not know how to pack in 2010, and Grit\n still doesn't. JGit did, and I don't know offhand about Dulwich.\n Does anyone know of bugs in those implementations that might have\n caused this?\n\nThe packs in question are public, so I can share them if anybody is\ncurious to look (but the whole repository is on the order of 700M).\n\nGiven the dates on the packs and how rare this is, I'm pretty much\nwilling to chalk it up to a random bug (in git or otherwise) that does\nnot any longer exist. But I was curious if anybody else knew anything,\nand we may want to fix sha1_entry_pos to behave more like the regular\nbinary search.\n\n-Peff\n"},{"id":"225223","messageId":"7v4nast9bv.fsf@alter.siamese.dyndns.org","threadId":"34695","inReplyTo":"20130814181718.GA7911@sigill.intra.peff.net","subject":"Re: duplicate objects in packfile","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-14T18:29:24Z","receivedAt":"2013-08-14T18:29:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> lookup does not. It hits an assert() that can only be triggered in the\n> face of duplicate objects. For example:\n>\n> $ git cat-file -t 4ea4acbcb0930ac42acc87a0d203864dec1a9697\n> commit\n>\n> $ GIT_USE_LOOKUP=1 git cat-file -t 4ea4acbcb0930ac42acc87a0d203864dec1a9697\n> git: sha1-lookup.c:222: sha1_entry_pos: Assertion `lov < hiv' failed.\n> Aborted\n\nOlder versions of JGit used to put duplicate objects in a pack, and\nIIRC Shawn declared that a bug in the packer and fixed it, so from\nthat point of view, I think rejecting is probably the right thing,\neven though I think warning and continuing is also acceptable and\nindeed may be better.\n"},{"id":"225224","messageId":"7vvc38ruah.fsf@alter.siamese.dyndns.org","threadId":"34695","inReplyTo":"7v4nast9bv.fsf@alter.siamese.dyndns.org","subject":"Re: duplicate objects in packfile","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-14T18:39:34Z","receivedAt":"2013-08-14T18:39:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Jeff King writes:\n>\n>> lookup does not. It hits an assert() that can only be triggered in the\n>> face of duplicate objects. For example:\n>>\n>> $ git cat-file -t 4ea4acbcb0930ac42acc87a0d203864dec1a9697\n>> commit\n>>\n>> $ GIT_USE_LOOKUP=1 git cat-file -t 4ea4acbcb0930ac42acc87a0d203864dec1a9697\n>> git: sha1-lookup.c:222: sha1_entry_pos: Assertion `lov < hiv' failed.\n>> Aborted\n>\n> Older versions of JGit used to put duplicate objects in a pack, and\n> IIRC Shawn declared that a bug in the packer and fixed it, so from\n> that point of view, I think rejecting is probably the right thing,\n> even though I think warning and continuing is also acceptable and\n> indeed may be better.\n\nAlso repacking may have a funny corner case. I do not recall the\ndetails as the above was a long time ago, but when I was tracking it\ndown, a delta was made against one copy of the base object, and\nreferred to it using delta-offset, while there was another copy of\nthe base object which was found by the bisection search, and from\nthere on, the inconsistencies between these two (they represent the\nsame payload, but they are at different offsets in the same pack and\nwith different in-pack sizes) led to some funky behaviour.\n"},{"id":"225225","messageId":"alpine.LFD.2.03.1308141425110.14472@syhkavp.arg","threadId":"34695","inReplyTo":"20130814181718.GA7911@sigill.intra.peff.net","subject":"Re: duplicate objects in packfile","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-14T18:50:01Z","receivedAt":"2013-08-14T18:50:01Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 14 Aug 2013, Jeff King wrote:\n\n> 1. Is sha1_entry_pos wrong to barf on duplicate items in the index? If\n> so, do we want to fix it, or simply retire GIT_USE_LOOKUP?\n\nI'd think that sha1_entry_pos should be more lenient here, especially if \nthis doesn't compromize the overall git behavior.\n\n> Related, should we consider duplicate items in a packfile to be a\n> bogus packfile (and consequently notice and complain during\n> indexing)? I don't think it _hurts_ anything (aside from the assert\n> above), though it is of course wasteful.\n\nThis should indeed be considered a bogus pack file. But we have a lot \nof code to be able to cope with bogus/corrupted pack files already. \nHandling this case as well would not hurt.\n\nMore importantly we should make sure the code we have doesn't generate \nsuch packs.\n\n> 2. How can duplicate entries get into a packfile?\n> \n> Git itself should not generate duplicate entries (pack-objects is\n> careful to remove duplicates). Since these packs almost certainly\n> were pushed by a client, I wondered if \"index-pack --fix-thin\"\n> might accidentally add multiple copies of an object when it is the\n> preferred base for multiple objects, but it specifically avoids\n> doing so.\n\nIt is probably simpler than that. An alternative pack-objects \nimplementation could stream multiple copies of an object upon a push, \nand index-pack on the receiving end would simply store what's been \nreceived to disk as is without a fuss.\n\n> Given the dates on the packs and how rare this is, I'm pretty much\n> willing to chalk it up to a random bug (in git or otherwise) that does\n> not any longer exist.\n\nPossibly. Given this is not compromizing the validity of the pack, and \na simple repack \"fixes\" it, I would not worry too much about it.\n\n\nNicolas\n"},{"id":"225226","messageId":"alpine.LFD.2.03.1308141451200.14472@syhkavp.arg","threadId":"34695","inReplyTo":"7vvc38ruah.fsf@alter.siamese.dyndns.org","subject":"Re: duplicate objects in packfile","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-14T18:54:49Z","receivedAt":"2013-08-14T18:54:49Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 14 Aug 2013, Junio C Hamano wrote:\n\n> Also repacking may have a funny corner case. I do not recall the\n> details as the above was a long time ago, but when I was tracking it\n> down, a delta was made against one copy of the base object, and\n> referred to it using delta-offset, while there was another copy of\n> the base object which was found by the bisection search, and from\n> there on, the inconsistencies between these two (they represent the\n> same payload, but they are at different offsets in the same pack and\n> with different in-pack sizes) led to some funky behaviour.\n\nCrap.\n\nBetter try to cope with this (with a test case, etc.) rather than \nrejecting them now I'd say. Strictly speaking, they're still valid pack \nfiles.\n\n\nNicolas\n"},{"id":"225346","messageId":"20130816150138.GA4823@sigill.intra.peff.net","threadId":"34695","inReplyTo":"7vvc38ruah.fsf@alter.siamese.dyndns.org","subject":"Re: duplicate objects in packfile","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-16T15:01:38Z","receivedAt":"2013-08-16T15:01:38Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 14, 2013 at 11:39:34AM -0700, Junio C Hamano wrote:\n\n> > Older versions of JGit used to put duplicate objects in a pack, and\n> > IIRC Shawn declared that a bug in the packer and fixed it, so from\n> > that point of view, I think rejecting is probably the right thing,\n> > even though I think warning and continuing is also acceptable and\n> > indeed may be better.\n> \n> Also repacking may have a funny corner case. I do not recall the\n> details as the above was a long time ago, but when I was tracking it\n> down, a delta was made against one copy of the base object, and\n> referred to it using delta-offset, while there was another copy of\n> the base object which was found by the bisection search, and from\n> there on, the inconsistencies between these two (they represent the\n> same payload, but they are at different offsets in the same pack and\n> with different in-pack sizes) led to some funky behaviour.\n\nThanks for the pointer. I found this commit:\n\n https://eclipse.googlesource.com/jgit/jgit/+/2fbf296fda205446eac11a13abd4fcdb182f28d9\n\nwhich is presumably what you're thinking of.\n\nI did not run into the problem described in my case, but presumably I\ndid not have a delta cycle between the multiple versions. In theory we\nshould find the same copy of the object each time we search, but there\nare enough code paths to access the objects that I would not be\nsurprised if such funkiness is still triggerable, including infinite\nloops.\n\nThat makes me inclined to teach index-pack to reject duplicate objects\nin a single pack in order to prevent denial-of-service attacks. We can\npotentially make them work in all code paths, but given that nobody\nshould be doing this legitimately, rejecting the duplicates outright\nkeeps our attack surface small, and nobody but attackers or users of\nbroken implementations should care.\n\n-Peff\n"},{"id":"225642","messageId":"20130821204955.GA28025@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130816150138.GA4823@sigill.intra.peff.net","subject":"[RFC/PATCH 0/4] duplicate objects in packfiles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-21T20:49:55Z","receivedAt":"2013-08-21T20:49:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 16, 2013 at 11:01:38AM -0400, Jeff King wrote:\n\n> That makes me inclined to teach index-pack to reject duplicate objects\n> in a single pack in order to prevent denial-of-service attacks. We can\n> potentially make them work in all code paths, but given that nobody\n> should be doing this legitimately, rejecting the duplicates outright\n> keeps our attack surface small, and nobody but attackers or users of\n> broken implementations should care.\n\nHere's a patch series in that direction:\n\n [1/4]: sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP\n\nThis reproduces and fixes the sha1-lookup bug. We should do this no\nmatter what else we do.\n\n [2/4]: index-pack: optionally reject packs with duplicate objects\n\nThis adds a pack.indexDuplicates option so that sites receiving\npackfiles from random folks on the internet can protect themselves from\nthe potential denial-of-service mentioned above. The default remains to\nallow it.\n\n [3/4]: reject duplicates when indexing a packfile we created\n\nThis is a safety check for packs we generate. Optional, but I think it's\nprobably a good idea (and doesn't cost very much).\n\n [4/4]: index-pack: optionally skip duplicate packfile entries\n\nI really wanted to have a \"fix\" mode where we could take in packs with\nduplicate entries and just use them as-is. It's not correct to throw\naway the duplicates (they may be bases in a delta cycle), but we could\nmaybe get by with simply not referencing them in the pack index.\nUnfortunately, the pack reader does not like the index we generate; see\nthe patch for details and possible solutions (all of which are ugly).\nAnd it only helps in a delta cycle when delta base offsets are used.\n\nI had hoped to have a 5/4 flipping the default to \"skip\", since it would\npotentially fix the infinite loop problem and wouldn't have a downside.\nBut since it doesn't work (and cannot fix the REF_DELTA case), it seems\nlike a bad idea.\n\nWhich leaves the open question: should the default for index-pack flip\nto reject duplicates rather than allow? It seems like it would be worth\nit to identify buggy packfiles before they move between repos. And in an\nemergency, we have the config flag to be more permissive in case\nsomebody really needs to move the data via git.\n\nThoughts?\n\n-Peff\n"},{"id":"225643","messageId":"20130821205118.GA28165@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130821204955.GA28025@sigill.intra.peff.net","subject":"[PATCH 1/4] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-21T20:51:18Z","receivedAt":"2013-08-21T20:51:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The sha1_entry_pos function tries to be smart about\nselecting the middle of a range for its binary search by\nlooking at the value differences between the \"lo\" and \"hi\"\nconstraints. However, it is unable to cope with entries with\nduplicate keys in the sorted list.\n\nWe may hit a point in the search where both our \"lo\" and\n\"hi\" point to the same key. In this case, the range of\nvalues between our endpoints is 0, and trying to scale the\ndifference between our key and the endpoints over that range\nis undefined (i.e., divide by zero). The current code\ncatches this with an \"assert(lov < hiv)\".\n\nMoreover, after seeing that the first 20 byte of the key are\nthe same, we will try to establish a value from the 21st\nbyte. Which is nonsensical.\n\nInstead, we can detect the case that we are in a run of\nduplicates, and simply do a final comparison against any one\nof them (since they are all the same, it does not matter\nwhich). If the keys match, we have found our entry (or one\nof them, anyway). If not, then we know that we do not need\nto look further, as we must be in a run of the duplicate\nkey.\n\nFurthermore, we know that one of our endpoints must be\nthe edge of the run of duplicates. For example, given this\nsequence:\n\n idx 0 1 2 3 4 5\n key A C C C C D\n\nIf we are searching for \"B\", we might hit the duplicate run\nat lo=1, hi=3 (e.g., by first mi=3, then mi=0). But we can\nnever have lo > 1, because B < C. That is, if our key is\nless than the run, we know that \"lo\" is the edge, but we can\nsay nothing of \"hi\". Similarly, if our key is greater than\nthe run, we know that \"hi\" is the edge, but we can say\nnothing of \"lo\". But that is enough for us to return not\nonly \"not found\", but show the position at which we would\ninsert the new item.\n\nSigned-off-by: Jeff King \n---\n sha1-lookup.c | 23 ++++++++++\n t/t5308-pack-detect-duplicates.sh | 97 +++++++++++++++++++++++++++++++++++++++\n 2 files changed, 120 insertions(+)\n create mode 100755 t/t5308-pack-detect-duplicates.sh\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex c4dc55d..614cbb6 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -204,7 +204,30 @@ int sha1_entry_pos(const void *table,\n \t\t\t * byte 0 thru (ofs-1) are the same between\n \t\t\t * lo and hi; ofs is the first byte that is\n \t\t\t * different.\n+\t\t\t *\n+\t\t\t * If ofs==20, then no bytes are different,\n+\t\t\t * meaning we have entries with duplicate\n+\t\t\t * keys. We know that we are in a solid run\n+\t\t\t * of this entry (because the entries are\n+\t\t\t * sorted, and our lo and hi are the same,\n+\t\t\t * there can be nothing but this single key\n+\t\t\t * in between). So we can stop the search.\n+\t\t\t * Either one of these entries is it (and\n+\t\t\t * we do not care which), or we do not have\n+\t\t\t * it.\n \t\t\t */\n+\t\t\tif (ofs == 20) {\n+\t\t\t\tmi = lo;\n+\t\t\t\tmi_key = base + elem_size * mi + key_offset;\n+\t\t\t\tcmp = memcmp(mi_key, key, 20);\n+\t\t\t\tif (!cmp)\n+\t\t\t\t\treturn mi;\n+\t\t\t\tif (cmp < 0)\n+\t\t\t\t\treturn -1 - hi;\n+\t\t\t\telse\n+\t\t\t\t\treturn -1 - lo;\n+\t\t\t}\n+\n \t\t\thiv = hi_key[ofs_0];\n \t\t\tif (ofs_0 < 19)\n \t\t\t\thiv = (hiv << 8) | hi_key[ofs_0+1];\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nnew file mode 100755\nindex 0000000..4800379\n--- /dev/null\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -0,0 +1,97 @@\n+#!/bin/sh\n+\n+test_description='handling of duplicate objects in incoming packfiles'\n+. ./test-lib.sh\n+\n+# git will never intentionally create packfiles with\n+# duplicate objects, so we have to construct them by hand.\n+#\n+# $1 is the number of times to duplicate each object (must be\n+# less than 127 for simplicify of implementation).\n+create_pack() {\n+\t{\n+\t\t# header magic\n+\t\tprintf 'PACK' &&\n+\t\t# version 2\n+\t\tprintf '\\0\\0\\0\\2' &&\n+\t\t# num of objects\n+\t\tprintf '\\0\\0\\0\\'\"$(printf \"%o\" $(($1*2)))\" &&\n+\n+\t\tfor i in $(test_seq 1 \"$1\"); do\n+\t\t\t# blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391\n+\t\t\tprintf '\\060\\170\\234\\003\\0\\0\\0\\0\\1' &&\n+\t\t\t# blob e68fe8129b546b101aee9510c5328e7f21ca1d18\n+\t\t\tprintf '\\062\\170\\234\\143\\267\\3\\0\\0\\116\\0\\106'\n+\t\tdone\n+\t} >tmp.pack &&\n+\t# we store and cat the pack because we also have to output\n+\t# the sha1 pack trailer\n+\tcat tmp.pack &&\n+\ttest-sha1 no-dups.pack &&\n+\tgit index-pack --stdin dups.pack &&\n+\tgit index-pack --stdin input <<-EOF &&\n+\t$LO_SHA1\n+\t$HI_SHA1\n+\t$MISSING_SHA1\n+\tEOF\n+\tcat >expect <<-EOF\n+\t$LO_SHA1 blob 2\n+\t$HI_SHA1 blob 0\n+\t$MISSING_SHA1 missing\n+\tEOF\n+'\n+\n+test_expect_success 'lookup in duplicated pack (binary search)' '\n+\tgit cat-file --batch-check actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'lookup in duplicated pack (GIT_USE_LOOKUP)' '\n+\t(\n+\t\tGIT_USE_LOOKUP=1 &&\n+\t\texport GIT_USE_LOOKUP &&\n+\t\tgit cat-file --batch-check actual\n+\t) &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n1.8.4.rc2.28.g6bb5f3f\n"},{"id":"225644","messageId":"20130821205220.GB28165@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130821204955.GA28025@sigill.intra.peff.net","subject":"[PATCH 2/4] index-pack: optionally reject packs with duplicate objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-21T20:52:20Z","receivedAt":"2013-08-21T20:52:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Git should never generate packs with duplicate objects.\nHowever, we may see such packs due to bugs in Git or other\nimplementations (e.g., JGit had such a bug a few years ago).\n\nIn theory, such packs should not be a problem for us (we\nwill simply find one of the instances of the object when\nlooking in the pack). However, the JGit bug report mentioned\npossible infinite loops during repacking due to cycles in\nthe delta chain. Though this problem hasn't specifically\nbeen reproduced on modern git, there is no reason not to be\ncareful with incoming packs, given that only buggy\nimplementations should be producing such packs, anyway.\n\nThis patch introduces the pack.indexDuplicates option to\nallow or reject such packs from index-pack. The default\nremains to allow it.\n\nSigned-off-by: Jeff King \n---\n builtin/index-pack.c | 10 ++++++++++\n pack-write.c | 23 +++++++++++++++++++++++\n pack.h | 5 +++++\n t/t5308-pack-detect-duplicates.sh | 8 ++++++++\n 4 files changed, 46 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 9c1cfac..83fd3bb 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1369,6 +1369,16 @@ static int git_index_pack_config(const char *k, const char *v, void *cb)\n #endif\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.indexduplicates\")) {\n+\t\tint boolval = git_config_maybe_bool(k, v);\n+\t\tif (boolval > 0 || !strcmp(v, \"ignore\"))\n+\t\t\topts->duplicates = WRITE_IDX_DUPLICATES_IGNORE;\n+\t\telse if (boolval == 0 || !strcmp(v, \"reject\"))\n+\t\t\topts->duplicates = WRITE_IDX_DUPLICATES_REJECT;\n+\t\telse\n+\t\t\tdie(\"unknown value for pack.indexduplicates: %s\", v);\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v, cb);\n }\n \ndiff --git a/pack-write.c b/pack-write.c\nindex ca9e63b..542b081 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -37,6 +37,19 @@ static int need_large_offset(off_t offset, const struct pack_idx_option *opts)\n \t\t\t sizeof(ofsval), cmp_uint32);\n }\n \n+static void *find_duplicate(void *vbase, size_t n, size_t size,\n+\t\t\t int (*cmp)(const void *, const void *))\n+{\n+\tunsigned char *base = vbase;\n+\twhile (n > 1) {\n+\t\tif (!cmp(base, base + size))\n+\t\t\treturn base;\n+\t\tbase += size;\n+\t\tn--;\n+\t}\n+\treturn NULL;\n+}\n+\n /*\n * On entry *sha1 contains the pack content SHA1 hash, on exit it is\n * the SHA1 hash of sorted object names. The objects array passed in\n@@ -68,6 +81,16 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \telse\n \t\tsorted_by_sha = list = last = NULL;\n \n+\tif (opts->duplicates == WRITE_IDX_DUPLICATES_REJECT) {\n+\t\tstruct pack_idx_entry **dup;\n+\n+\t\tdup = find_duplicate(sorted_by_sha, nr_objects,\n+\t\t\t\t sizeof(*sorted_by_sha), sha1_compare);\n+\t\tif (dup)\n+\t\t\tdie(\"pack has duplicate entries for %s\",\n+\t\t\t sha1_to_hex((*dup)->sha1));\n+\t}\n+\n \tif (opts->flags & WRITE_IDX_VERIFY) {\n \t\tassert(index_name);\n \t\tf = sha1fd_check(index_name);\ndiff --git a/pack.h b/pack.h\nindex aa6ee7d..cd4b536 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -44,6 +44,11 @@ struct pack_idx_option {\n \tuint32_t version;\n \tuint32_t off32_limit;\n \n+\tenum {\n+\t\tWRITE_IDX_DUPLICATES_IGNORE = 0,\n+\t\tWRITE_IDX_DUPLICATES_REJECT\n+\t} duplicates;\n+\n \t/*\n \t * List of offsets that would fit within off32_limit but\n \t * need to be written out as 64-bit entity for byte-for-byte\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 4800379..0f2d928 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -94,4 +94,12 @@ test_expect_success 'lookup in duplicated pack (GIT_USE_LOOKUP)' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'index-pack can reject packs with duplicates' '\n+\tclear_packs &&\n+\tcreate_pack 2 >dups.pack &&\n+\ttest_must_fail \\\n+\t\tgit -c pack.indexDuplicates=0 index-pack --stdin \n---\nThis turns on rejection for everywhere _except_ a separately-run\nindex-pack. If we decide to turn it on there, too, it would make sense\nto scrap this patch and just put it in reset_pack_idx_opts().\n\n builtin/pack-objects.c | 1 +\n bulk-checkin.c | 1 +\n fast-import.c | 1 +\n 3 files changed, 3 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f069462..8da2a66 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2511,6 +2511,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tread_replace_refs = 0;\n \n \treset_pack_idx_option(&pack_idx_opts);\n+\tpack_idx_opts.duplicates = WRITE_IDX_DUPLICATES_REJECT;\n \tgit_config(git_pack_config, NULL);\n \tif (!pack_compression_seen && core_compression_seen)\n \t\tpack_compression_level = core_compression_level;\ndiff --git a/bulk-checkin.c b/bulk-checkin.c\nindex 6b0b6d4..bad191f 100644\n--- a/bulk-checkin.c\n+++ b/bulk-checkin.c\n@@ -174,6 +174,7 @@ static void prepare_to_stream(struct bulk_checkin_state *state,\n \n \tstate->f = create_tmp_packfile(&state->pack_tmp_name);\n \treset_pack_idx_option(&state->pack_idx_opts);\n+\tstate->pack_idx_opts.duplicates = WRITE_IDX_DUPLICATES_REJECT;\n \n \t/* Pretend we are going to write only one object */\n \tstate->offset = write_pack_header(state->f, 1);\ndiff --git a/fast-import.c b/fast-import.c\nindex 23f625f..b7beab0 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -3360,6 +3360,7 @@ int main(int argc, char **argv)\n \n \tsetup_git_directory();\n \treset_pack_idx_option(&pack_idx_opts);\n+\tpack_idx_opts.duplicates = WRITE_IDX_DUPLICATES_REJECT;\n \tgit_config(git_pack_config, NULL);\n \tif (!pack_compression_seen && core_compression_seen)\n \t\tpack_compression_level = core_compression_level;\n-- \n1.8.4.rc2.28.g6bb5f3f\n"},{"id":"225646","messageId":"20130821205555.GD28165@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130821204955.GA28025@sigill.intra.peff.net","subject":"[DO NOT APPLY PATCH 4/4] index-pack: optionally skip duplicate packfile entries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-21T20:55:55Z","receivedAt":"2013-08-21T20:55:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are building the pack index, we can notice that\nthere are duplicate objects, pick one \"winner\" instance, and\nmention the object only once in the index (mapped to the\nwinner's offset).\n\nThis has the effect that the duplicate packfile entries are\nnever found by lookup. The data still exists in the\npackfile, though, and can be used as a delta base if delta\nbase offsets are used. If delta refs are used, then it is\npossible that some deltas may be broken.\n\nUnfortunately, this scheme does not quite work, as the pack\nreader checks that the index and packfile claim the same\nnumber of objects, and will refuse to open such a packfile.\n\nWe have a few options:\n\n 1. Loosen the check in the reader. This drops a\n potentially useful sanity check on the data, and it\n won't work for any other implementations (including\n older versions of git).\n\n 2. Loosen the check only if a special flag is found in the\n index indicating that we removed duplicates. This means\n that we only lose the safety check in the rare case\n that duplicates are found. But there is actually no\n place in the index to put such a flag, and in addition\n no other implementation would understand our flag.\n\n 3. Instead of reducing the numnber of objects in the\n index, include \"dummy\" entries using the null sha1 or a\n similar sentinel value (and pointing to some invalid\n offset). This should work, but is awfully hacky (and\n will probably create havoc as we will now claim to have\n the null sha1, but will throw errors if you actually\n look at it).\n\nSigned-off-by: Jeff King \n---\nI think this line of \"fixing\" should probably be scrapped. Truly fixing\nit and covering the REF_DELTA case would involve magic in the actual\nobject lookups (we would have to detect cycles and find the \"other\"\nobject that is the real base). And it's probably just not worth the\neffort.\n\n builtin/index-pack.c | 2 ++\n pack-write.c | 30 ++++++++++++++++++++++++++++++\n pack.h | 3 ++-\n t/t5308-pack-detect-duplicates.sh | 8 ++++++++\n 4 files changed, 42 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 83fd3bb..1dadd56 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1375,6 +1375,8 @@ static int git_index_pack_config(const char *k, const char *v, void *cb)\n \t\t\topts->duplicates = WRITE_IDX_DUPLICATES_IGNORE;\n \t\telse if (boolval == 0 || !strcmp(v, \"reject\"))\n \t\t\topts->duplicates = WRITE_IDX_DUPLICATES_REJECT;\n+\t\telse if (!strcmp(v, \"skip\"))\n+\t\t\topts->duplicates = WRITE_IDX_DUPLICATES_SKIP;\n \t\telse\n \t\t\tdie(\"unknown value for pack.indexduplicates: %s\", v);\n \t\treturn 0;\ndiff --git a/pack-write.c b/pack-write.c\nindex 542b081..657da2a 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -50,6 +50,27 @@ static void *find_duplicate(void *vbase, size_t n, size_t size,\n \treturn NULL;\n }\n \n+static size_t remove_duplicates(void *base, size_t n, size_t size,\n+\t\t\t\tint (*cmp)(const void *, const void *))\n+{\n+\tunsigned char *from = base, *to = base;\n+\n+\tfrom += size;\n+\tto += size;\n+\tn--;\n+\n+\twhile (n > 0) {\n+\t\tif (cmp(from, from - size)) {\n+\t\t\tif (to != from)\n+\t\t\t\tmemcpy(to, from, size);\n+\t\t\tto += size;\n+\t\t}\n+\t\tfrom += size;\n+\t\tn--;\n+\t}\n+\treturn (to - (unsigned char *)base) / size;\n+}\n+\n /*\n * On entry *sha1 contains the pack content SHA1 hash, on exit it is\n * the SHA1 hash of sorted object names. The objects array passed in\n@@ -89,6 +110,15 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t\tif (dup)\n \t\t\tdie(\"pack has duplicate entries for %s\",\n \t\t\t sha1_to_hex((*dup)->sha1));\n+\t} else if (opts->duplicates == WRITE_IDX_DUPLICATES_SKIP) {\n+\t\tint nr_unique = remove_duplicates(sorted_by_sha,\n+\t\t\t\t\t\t nr_objects,\n+\t\t\t\t\t\t sizeof(*sorted_by_sha),\n+\t\t\t\t\t\t sha1_compare);\n+\t\tif (nr_unique != nr_objects) {\n+\t\t\tnr_objects = nr_unique;\n+\t\t\tlast = sorted_by_sha + nr_objects;\n+\t\t}\n \t}\n \n \tif (opts->flags & WRITE_IDX_VERIFY) {\ndiff --git a/pack.h b/pack.h\nindex cd4b536..3017ea4 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -46,7 +46,8 @@ struct pack_idx_option {\n \n \tenum {\n \t\tWRITE_IDX_DUPLICATES_IGNORE = 0,\n-\t\tWRITE_IDX_DUPLICATES_REJECT\n+\t\tWRITE_IDX_DUPLICATES_REJECT,\n+\t\tWRITE_IDX_DUPLICATES_SKIP\n \t} duplicates;\n \n \t/*\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 0f2d928..963d7b9 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -102,4 +102,12 @@ 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 'index-pack can fix packs with duplicates' '\n+\tclear_packs &&\n+\tcreate_pack 2 >dups.pack &&\n+\tgit -c pack.indexDuplicates=skip index-pack --stdin actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n1.8.4.rc2.28.g6bb5f3f\n"},{"id":"225655","messageId":"xmqq38q2u1si.fsf@gitster.dls.corp.google.com","threadId":"34695","inReplyTo":"20130821204955.GA28025@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 0/4] duplicate objects in packfiles","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-21T22:17:17Z","receivedAt":"2013-08-21T22:17:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Which leaves the open question: should the default for index-pack flip\n> to reject duplicates rather than allow?\n\nI'd say so.\n\nIn am emergency, people with broken packfiles can feed them to\nunpack-objects ;-)\n\nMore seriously, an alternative emergency mode may be an option to\nunpack-objects that does not unpack objects but streams to a new\npack or something to resurret the objects that are salvageable from\na corrupt packfile.\n"},{"id":"225660","messageId":"xmqqob8qskbc.fsf@gitster.dls.corp.google.com","threadId":"34695","inReplyTo":"20130821205555.GD28165@sigill.intra.peff.net","subject":"Re: [DO NOT APPLY PATCH 4/4] index-pack: optionally skip duplicate packfile entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-21T23:20:07Z","receivedAt":"2013-08-21T23:20:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> When we are building the pack index, we can notice that\n> there are duplicate objects, pick one \"winner\" instance, and\n> mention the object only once in the index (mapped to the\n> winner's offset).\n>\n> This has the effect that the duplicate packfile entries are\n> never found by lookup. The data still exists in the\n> packfile, though, and can be used as a delta base if delta\n> base offsets are used. If delta refs are used, then it is\n> possible that some deltas may be broken.\n\nI do not understand the last bit. If two copies of an object exist\nbut you have only one slot for the object in the index, and another\nobject names it as its base with ref-delta, then reconstituting it\nshould work just fine---whichever representation of the base object\nis recorded in the .idx, that first needs to be reconstituted before\nthe delta is applied to it, and both copies should yield identical\ncontents for the delta base object, no?\n\nIn any case, ejecting one from the pack .idx would not help in the\npresense of either broken or malicious packer that reuses delta too\naggressively. Suppose you have objects A and B and somehow manage\nto create a cycle of deltas, A names B as its delta base and B names\nA as its delta base. The packer may notice its mistake and then add\nanother copy of A as a base object. The pack contains two copies of\nA (one is delta based on B, the other is full) and B (delta against\nA).\n\nIf B refers to the copy of A that is delta against B using ofs-delta,\nfixing the .idx file will have no effect. read_packed_sha1(B) will\nread the delta data of B, finds the offset to start reading the data\nfor A which was excised from the .idx and unless that codepath is\nupdated to consult revindex (i.e. you mark one copy of A in the .pack\nas bad, and when B refers to that bad copy of A via ofs-delta, you\ncheck the offset against revindex to get the object name of A and go\nto the good copy of A), you will never finish reading B because\nreading the bad copy of A will lead you to first reconstitute B.\n\n> I think this line of \"fixing\" should probably be scrapped.\n\nI tend to agree.\n"},{"id":"225667","messageId":"20130822004710.GA563@sigill.intra.peff.net","threadId":"34695","inReplyTo":"xmqqob8qskbc.fsf@gitster.dls.corp.google.com","subject":"Re: [DO NOT APPLY PATCH 4/4] index-pack: optionally skip duplicate packfile entries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-22T00:47:10Z","receivedAt":"2013-08-22T00:47:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 21, 2013 at 04:20:07PM -0700, Junio C Hamano wrote:\n\n> I do not understand the last bit. If two copies of an object exist\n> but you have only one slot for the object in the index, and another\n> object names it as its base with ref-delta, then reconstituting it\n> should work just fine---whichever representation of the base object\n> is recorded in the .idx, that first needs to be reconstituted before\n> the delta is applied to it, and both copies should yield identical\n> contents for the delta base object, no?\n> \n> In any case, ejecting one from the pack .idx would not help in the\n> presense of either broken or malicious packer that reuses delta too\n> aggressively. Suppose you have objects A and B and somehow manage\n> to create a cycle of deltas, A names B as its delta base and B names\n> A as its delta base. The packer may notice its mistake and then add\n> another copy of A as a base object. The pack contains two copies of\n> A (one is delta based on B, the other is full) and B (delta against\n> A).\n\nYes, that is the potentially problematic scenario...\n\n> If B refers to the copy of A that is delta against B using ofs-delta,\n> fixing the .idx file will have no effect. read_packed_sha1(B) will\n> read the delta data of B, finds the offset to start reading the data\n> for A which was excised from the .idx and unless that codepath is\n> updated to consult revindex (i.e. you mark one copy of A in the .pack\n> as bad, and when B refers to that bad copy of A via ofs-delta, you\n> check the offset against revindex to get the object name of A and go\n> to the good copy of A), you will never finish reading B because\n> reading the bad copy of A will lead you to first reconstitute B.\n\nYes. There are two levels of brokenness here.\n\nOne is that the pack has a delta base offset for B that leads to the\n\"wrong\" A, creating a cycle. This is an utterly broken pack and cannot\nbe fixed automatically (you do not even know the name of the cycled A\nbecause you cannot constitute it to find its name and realize that it\nhas a duplicate!). But we should notice this during index-pack, because\nwe cannot reconstruct the object.\n\nAnother situation is that your delta base points to the \"right\" A. You\ncan reconstruct either A or B, because although there is a duplicate,\nthere are no cycles in the delta chain (i.e., the chain does not care\nabout object name, only offset, and offsets point only one way).\n\nSo we do not have a problem at all with reconstructing the object data.\nWe do have two ways we might access A from the same pack. For regular\nobject lookup, that is probably not a big deal. For operations like\nrepacking that look more closely at the on-disk representation, I do not\nknow. We may mark A as \"has a delta\" or \"does not have a delta\" at one\npoint in the code, but then later find the other copy of A which does\nnot match. I did not trace through all of pack-objects to find whether\nthat is possible, or what bugs it might cause. But indexing only one\ncopy as the \"master\" means that we will always get a consistent view of\nthe object (from that particular pack, at least).\n\nNow consider REF_DELTA. We lookup the base object by name, so we may get\na different answer depending on how it is indexed. E.g., index-pack\nkeeps an internal hash table, whereas later callers will use the .idx\nfile. When looking at the .idx file, we may use a regular binary search,\nor sha1_entry_pos. The exact order of the search may even change from\ngit version to git version.\n\nSo you may have a situation where index-pack finds the \"right\" A and\nproperly reconstructs the file while creating the .idx, and thinks all\nis well. But later lookups may find the \"wrong\" A, and fail. In other\nwords, we cannot trust that data that makes it through index-pack is not\ncorrupted (and it is index-pack's output that lets receive-pack commit\nto the client that we have their objects, so we want to be reasonably\nsure we have uncorrupted copies at that point).\n\nChoosing a single \"master\" A to go in the .idx means we will get a\nconsistent view of A once the .idx is generated. But it may not be the\nright one, and it may not be the one we used to check that we can\nresolve A and B in the first place.\n\nThe right fix for that situation is to keep both entries in the .idx,\ndetect delta cycles, then look up extra copies of A, but being aware\nthat you already found one copy in the .idx and that sha1_entry_pos (or\nthe vanilla binary search) should return any other copies, if they\nexist. I do not think we detect delta cycles at all (though I didn't\ncheck), but certainly we do not have a way to tell sha1_entry_pos any\ndifferent information so that it will find the \"other\" A.\n\nSo I think it is a recoverable state, but it is a non-trivial bit of\ncode for something that should never happen. Rejecting on push/fetch via\nindex-pack is simple and easy, and we can deal with the fallout if and\nwhen it ever actually happens.\n\n> > I think this line of \"fixing\" should probably be scrapped.\n> \n> I tend to agree.\n\nOK. Let's drop the \"skip\" patch, then. I'll re-roll with a patch to flip\nthe default to \"reject\".\n\n-Peff\n"},{"id":"225677","messageId":"CACsJy8DkUeS3s+X=gKX4ZAi82g_D_9t=bBVs8NNY2EeqM9W-rQ@mail.gmail.com","threadId":"34695","inReplyTo":"20130821205220.GB28165@sigill.intra.peff.net","subject":"Re: [PATCH 2/4] index-pack: optionally reject packs with duplicate objects","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-22T13:45:19Z","receivedAt":"2013-08-22T13:45:19Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Aug 22, 2013 at 3:52 AM, Jeff King wrote:\n> @@ -68,6 +81,16 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n> else\n> sorted_by_sha = list = last = NULL;\n>\n> + if (opts->duplicates == WRITE_IDX_DUPLICATES_REJECT) {\n> + struct pack_idx_entry **dup;\n> +\n> + dup = find_duplicate(sorted_by_sha, nr_objects,\n> + sizeof(*sorted_by_sha), sha1_compare);\n> + if (dup)\n> + die(\"pack has duplicate entries for %s\",\n> + sha1_to_hex((*dup)->sha1));\n> + }\n> +\n> if (opts->flags & WRITE_IDX_VERIFY) {\n> assert(index_name);\n> f = sha1fd_check(index_name);\n\nwrite_idx_file() is called after index-pack processes all delta\nobjects. Could resolve_deltas() go cyclic with certain duplicate\nobject setup?\n-- \nDuy\n"},{"id":"225678","messageId":"20130822144305.GA21219@sigill.intra.peff.net","threadId":"34695","inReplyTo":"CACsJy8DkUeS3s+X=gKX4ZAi82g_D_9t=bBVs8NNY2EeqM9W-rQ@mail.gmail.com","subject":"Re: [PATCH 2/4] index-pack: optionally reject packs with duplicate objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-22T14:43:05Z","receivedAt":"2013-08-22T14:43:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 22, 2013 at 08:45:19PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Thu, Aug 22, 2013 at 3:52 AM, Jeff King wrote:\n> > @@ -68,6 +81,16 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n> > else\n> > sorted_by_sha = list = last = NULL;\n> >\n> > + if (opts->duplicates == WRITE_IDX_DUPLICATES_REJECT) {\n> > + struct pack_idx_entry **dup;\n> > +\n> > + dup = find_duplicate(sorted_by_sha, nr_objects,\n> > + sizeof(*sorted_by_sha), sha1_compare);\n> > + if (dup)\n> > + die(\"pack has duplicate entries for %s\",\n> > + sha1_to_hex((*dup)->sha1));\n> > + }\n> > +\n> > if (opts->flags & WRITE_IDX_VERIFY) {\n> > assert(index_name);\n> > f = sha1fd_check(index_name);\n> \n> write_idx_file() is called after index-pack processes all delta\n> objects. Could resolve_deltas() go cyclic with certain duplicate\n> object setup?\n\nGood question. I'm not sure. I'll check it out.\n\n-Peff\n"},{"id":"225696","messageId":"20130822231215.GA16978@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130822144305.GA21219@sigill.intra.peff.net","subject":"[PATCHv2 0/6] duplicate objects and delta cycles, oh my!","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-22T23:12:15Z","receivedAt":"2013-08-22T23:12:15Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 22, 2013 at 10:43:05AM -0400, Jeff King wrote:\n\n> > write_idx_file() is called after index-pack processes all delta\n> > objects. Could resolve_deltas() go cyclic with certain duplicate\n> > object setup?\n> \n> Good question. I'm not sure. I'll check it out.\n\nI think the answer is \"no\", based on both reasoning and testing (both of\nwhich are included in patches 3-4 of the series below).\n\nSo here's my re-roll of the series.\n\n [1/6]: test-sha1: add a binary output mode\n\n New in this iteration; the previous version piped test-sha1 into\n perl to create the pack trailer, but with this simple change we can\n drop the perl dependency.\n\n [2/6]: sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP\n\n Same code as before. I've factored the pack-creation bits from the\n tests into lib-pack.sh, so they can be reused elsewhere when we want\n to create bogus packs (and patches 3-4 reuse them here).\n\n [3/6]: add tests for indexing packs with delta cycles\n [4/6]: test index-pack on packs with recoverable delta cycles\n\n New tests covering delta cycles.\n\n [5/6]: index-pack: optionally reject packs with duplicate objects\n\n Similar to before, but I converted the config flag to a simple\n boolean (since we scrapped the \"fix\" of the tri-state \"allow,\n reject, fix\").\n\n [6/6]: default pack.indexDuplicates to false\n\n This flips the safety check on by default everywhere (before, it was\n left off for index-pack).\n\n-Peff\n"},{"id":"225698","messageId":"20130822231241.GA17060@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130822231215.GA16978@sigill.intra.peff.net","subject":"[PATCH 1/6] test-sha1: add a binary output mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-22T23:12:42Z","receivedAt":"2013-08-22T23:12:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The test-sha1 helper program will run our internal sha1\nroutines over its input and output the 40-byte hex sha1.\nSometimes, however, it is useful to have the binary 20-byte\nsha1 (and it's a pain to convert back in the shell). Let's\nadd a \"-b\" option to output the binary version.\n\nSigned-off-by: Jeff King \n---\n test-sha1.c | 15 ++++++++++++---\n 1 file changed, 12 insertions(+), 3 deletions(-)\n\ndiff --git a/test-sha1.c b/test-sha1.c\nindex 80daba9..e57eae1 100644\n--- a/test-sha1.c\n+++ b/test-sha1.c\n@@ -5,10 +5,15 @@ int main(int ac, char **av)\n \tgit_SHA_CTX ctx;\n \tunsigned char sha1[20];\n \tunsigned bufsz = 8192;\n+\tint binary = 0;\n \tchar *buffer;\n \n-\tif (ac == 2)\n-\t\tbufsz = strtoul(av[1], NULL, 10) * 1024 * 1024;\n+\tif (ac == 2) {\n+\t\tif (!strcmp(av[1], \"-b\"))\n+\t\t\tbinary = 1;\n+\t\telse\n+\t\t\tbufsz = strtoul(av[1], NULL, 10) * 1024 * 1024;\n+\t}\n \n \tif (!bufsz)\n \t\tbufsz = 8192;\n@@ -42,6 +47,10 @@ int main(int ac, char **av)\n \t\tgit_SHA1_Update(&ctx, buffer, this_sz);\n \t}\n \tgit_SHA1_Final(sha1, &ctx);\n-\tputs(sha1_to_hex(sha1));\n+\n+\tif (binary)\n+\t\tfwrite(sha1, 1, 20, stdout);\n+\telse\n+\t\tputs(sha1_to_hex(sha1));\n \texit(0);\n }\n-- \n1.8.4.rc2.28.g6bb5f3f\n"},{"id":"225699","messageId":"20130822231404.GB17060@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130822231215.GA16978@sigill.intra.peff.net","subject":"[PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-22T23:14:04Z","receivedAt":"2013-08-22T23:14:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The sha1_entry_pos function tries to be smart about\nselecting the middle of a range for its binary search by\nlooking at the value differences between the \"lo\" and \"hi\"\nconstraints. However, it is unable to cope with entries with\nduplicate keys in the sorted list.\n\nWe may hit a point in the search where both our \"lo\" and\n\"hi\" point to the same key. In this case, the range of\nvalues between our endpoints is 0, and trying to scale the\ndifference between our key and the endpoints over that range\nis undefined (i.e., divide by zero). The current code\ncatches this with an \"assert(lov < hiv)\".\n\nMoreover, after seeing that the first 20 byte of the key are\nthe same, we will try to establish a value from the 21st\nbyte. Which is nonsensical.\n\nInstead, we can detect the case that we are in a run of\nduplicates, and simply do a final comparison against any one\nof them (since they are all the same, it does not matter\nwhich). If the keys match, we have found our entry (or one\nof them, anyway). If not, then we know that we do not need\nto look further, as we must be in a run of the duplicate\nkey.\n\nFurthermore, we know that one of our endpoints must be\nthe edge of the run of duplicates. For example, given this\nsequence:\n\n idx 0 1 2 3 4 5\n key A C C C C D\n\nIf we are searching for \"B\", we might hit the duplicate run\nat lo=1, hi=3 (e.g., by first mi=3, then mi=0). But we can\nnever have lo > 1, because B < C. That is, if our key is\nless than the run, we know that \"lo\" is the edge, but we can\nsay nothing of \"hi\". Similarly, if our key is greater than\nthe run, we know that \"hi\" is the edge, but we can say\nnothing of \"lo\". But that is enough for us to return not\nonly \"not found\", but show the position at which we would\ninsert the new item.\n\nSigned-off-by: Jeff King \n---\n sha1-lookup.c | 23 ++++++++++++\n t/lib-pack.sh | 78 +++++++++++++++++++++++++++++++++++++++\n t/t5308-pack-detect-duplicates.sh | 73 ++++++++++++++++++++++++++++++++++++\n 3 files changed, 174 insertions(+)\n create mode 100644 t/lib-pack.sh\n create mode 100755 t/t5308-pack-detect-duplicates.sh\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex c4dc55d..614cbb6 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -204,7 +204,30 @@ int sha1_entry_pos(const void *table,\n \t\t\t * byte 0 thru (ofs-1) are the same between\n \t\t\t * lo and hi; ofs is the first byte that is\n \t\t\t * different.\n+\t\t\t *\n+\t\t\t * If ofs==20, then no bytes are different,\n+\t\t\t * meaning we have entries with duplicate\n+\t\t\t * keys. We know that we are in a solid run\n+\t\t\t * of this entry (because the entries are\n+\t\t\t * sorted, and our lo and hi are the same,\n+\t\t\t * there can be nothing but this single key\n+\t\t\t * in between). So we can stop the search.\n+\t\t\t * Either one of these entries is it (and\n+\t\t\t * we do not care which), or we do not have\n+\t\t\t * it.\n \t\t\t */\n+\t\t\tif (ofs == 20) {\n+\t\t\t\tmi = lo;\n+\t\t\t\tmi_key = base + elem_size * mi + key_offset;\n+\t\t\t\tcmp = memcmp(mi_key, key, 20);\n+\t\t\t\tif (!cmp)\n+\t\t\t\t\treturn mi;\n+\t\t\t\tif (cmp < 0)\n+\t\t\t\t\treturn -1 - hi;\n+\t\t\t\telse\n+\t\t\t\t\treturn -1 - lo;\n+\t\t\t}\n+\n \t\t\thiv = hi_key[ofs_0];\n \t\t\tif (ofs_0 < 19)\n \t\t\t\thiv = (hiv << 8) | hi_key[ofs_0+1];\ndiff --git a/t/lib-pack.sh b/t/lib-pack.sh\nnew file mode 100644\nindex 0000000..61c5d19\n--- /dev/null\n+++ b/t/lib-pack.sh\n@@ -0,0 +1,78 @@\n+#!/bin/sh\n+#\n+# Support routines for hand-crafting weird or malicious packs.\n+#\n+# You can make a complete pack like:\n+#\n+# pack_header 2 >foo.pack &&\n+# pack_obj e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 >>foo.pack &&\n+# pack_obj e68fe8129b546b101aee9510c5328e7f21ca1d18 >>foo.pack &&\n+# pack_trailer foo.pack\n+\n+# Print the big-endian 4-byte octal representation of $1\n+uint32_octal() {\n+\tn=$1\n+\tprintf '\\%o' $(($n / 16777216)); n=$((n % 16777216))\n+\tprintf '\\%o' $(($n / 65536)); n=$((n % 65536))\n+\tprintf '\\%o' $(($n / 256)); n=$((n % 256))\n+\tprintf '\\%o' $(($n ));\n+}\n+\n+# Print the big-endian 4-byte binary representation of $1\n+uint32_binary() {\n+\tprintf \"$(uint32_octal \"$1\")\"\n+}\n+\n+# Print a pack header, version 2, for a pack with $1 objects\n+pack_header() {\n+\tprintf 'PACK' &&\n+\tprintf '\\0\\0\\0\\2' &&\n+\tuint32_binary \"$1\"\n+}\n+\n+# Print the pack data for object $1, as a delta against object $2 (or as a full\n+# object if $2 is missing or empty). The output is suitable for including\n+# directly in the packfile, and represents the entirety of the object entry.\n+# Doing this on the fly (especially picking your deltas) is quite tricky, so we\n+# have hardcoded some well-known objects. See the case statements below for the\n+# complete list.\n+pack_obj() {\n+\tcase \"$1\" in\n+\t# empty blob\n+\te69de29bb2d1d6434b8b29ae775ad8c2e48c5391)\n+\t\tcase \"$2\" in\n+\t\t'')\n+\t\t\tprintf '\\060\\170\\234\\003\\0\\0\\0\\0\\1'\n+\t\t\treturn\n+\t\t\t;;\n+\t\tesac\n+\t\t;;\n+\n+\t# blob containing \"\\7\\76\"\n+\te68fe8129b546b101aee9510c5328e7f21ca1d18)\n+\t\tcase \"$2\" in\n+\t\t'')\n+\t\t\tprintf '\\062\\170\\234\\143\\267\\3\\0\\0\\116\\0\\106'\n+\t\t\treturn\n+\t\t\t;;\n+\t\tesac\n+\t\t;;\n+\tesac\n+\n+\techo >&2 \"BUG: don't know how to print $1${2:+ (from $2)}\"\n+\treturn 1\n+}\n+\n+# Compute and append pack trailer to \"$1\"\n+pack_trailer() {\n+\ttest-sha1 -b <\"$1\" >trailer.tmp &&\n+\tcat trailer.tmp >>\"$1\" &&\n+\trm -f trailer.tmp\n+}\n+\n+# Remove any existing packs to make sure that\n+# whatever we index next will be the pack that we\n+# actually use.\n+clear_packs() {\n+\trm -f .git/objects/pack/*\n+}\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nnew file mode 100755\nindex 0000000..719d48f\n--- /dev/null\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -0,0 +1,73 @@\n+#!/bin/sh\n+\n+test_description='handling of duplicate objects in incoming packfiles'\n+. ./test-lib.sh\n+. ../lib-pack.sh\n+\n+# The sha1s we have in our pack. It's important that these have the same\n+# starting byte, so that they end up in the same fanout section of the index.\n+# That lets us make sure we are exercising the binary search with both sets.\n+LO_SHA1=e68fe8129b546b101aee9510c5328e7f21ca1d18\n+HI_SHA1=e69de29bb2d1d6434b8b29ae775ad8c2e48c5391\n+\n+# And here's a \"missing sha1\" which will produce failed lookups. It must also\n+# be in the same fanout section, and should be between the two (so that during\n+# our binary search, we are sure to end up looking at one or the other of the\n+# duplicate runs).\n+MISSING_SHA1='e69d000000000000000000000000000000000000'\n+\n+# git will never intentionally create packfiles with\n+# duplicate objects, so we have to construct them by hand.\n+#\n+# $1 is the name of the packfile to create\n+#\n+# $2 is the number of times to duplicate each object\n+create_pack() {\n+\tpack_header \"$((2 * $2))\" >\"$1\" &&\n+\tfor i in $(test_seq 1 \"$2\"); do\n+\t\tpack_obj $LO_SHA1 &&\n+\t\tpack_obj $HI_SHA1\n+\tdone >>\"$1\" &&\n+\tpack_trailer \"$1\"\n+}\n+\n+# double-check that create_pack actually works\n+test_expect_success 'pack with no duplicates' '\n+\tcreate_pack no-dups.pack 1 &&\n+\tgit index-pack --stdin input <<-EOF &&\n+\t$LO_SHA1\n+\t$HI_SHA1\n+\t$MISSING_SHA1\n+\tEOF\n+\tcat >expect <<-EOF\n+\t$LO_SHA1 blob 2\n+\t$HI_SHA1 blob 0\n+\t$MISSING_SHA1 missing\n+\tEOF\n+'\n+\n+test_expect_success 'lookup in duplicated pack (binary search)' '\n+\tgit cat-file --batch-check actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'lookup in duplicated pack (GIT_USE_LOOKUP)' '\n+\t(\n+\t\tGIT_USE_LOOKUP=1 &&\n+\t\texport GIT_USE_LOOKUP &&\n+\t\tgit cat-file --batch-check actual\n+\t) &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n1.8.4.rc2.28.g6bb5f3f\n"},{"id":"225700","messageId":"20130822231440.GC17060@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130822231215.GA16978@sigill.intra.peff.net","subject":"[PATCH 3/6] add tests for indexing packs with delta cycles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-22T23:14:40Z","receivedAt":"2013-08-22T23:14:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If we receive a broken or malicious pack from a remote, we\nwill feed it to index-pack. As index-pack processes the\nobjects as a stream, reconstructing and hashing each object\nto get its name, it is not very susceptible to doing the\nwrong with bad data (it simply notices that the data is\nbogus and aborts).\n\nHowever, one question raised on the list is whether it could\nbe susceptible to problems during the delta-resolution\nphase. In particular, can a cycle in the packfile deltas\ncause us to go into an infinite loop or cause any other\nproblem?\n\nThe answer is no.\n\nWe cannot have a cycle of delta-base offsets, because they\ngo only in one direction (the OFS_DELTA object mentions its\nbase by an offset towards the beginning of the file, and we\nexplicitly reject negative offsets).\n\nWe can have a cycle of REF_DELTA objects, which refer to\nbase objects by sha1 name. However, index-pack does not know\nthese sha1 names ahead of time; it has to reconstruct the\nobjects to get their names, and it cannot do so if there is\na delta cycle (in other words, it does not even realize\nthere is a cycle, but only that there are items that cannot\nbe resolved).\n\nEven though we can reason out that index-pack should handle\nthis fine, let's add a few tests to make sure it behaves\ncorrectly.\n\nSigned-off-by: Jeff King \n---\n t/lib-pack.sh | 22 +++++++++++++++++\n t/t5309-pack-delta-cycles.sh | 59 ++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 81 insertions(+)\n create mode 100755 t/t5309-pack-delta-cycles.sh\n\ndiff --git a/t/lib-pack.sh b/t/lib-pack.sh\nindex 61c5d19..e028c40 100644\n--- a/t/lib-pack.sh\n+++ b/t/lib-pack.sh\n@@ -55,6 +55,28 @@ pack_obj() {\n \t\t\tprintf '\\062\\170\\234\\143\\267\\3\\0\\0\\116\\0\\106'\n \t\t\treturn\n \t\t\t;;\n+\t\t01d7713666f4de822776c7622c10f1b07de280dc)\n+\t\t\tprintf '\\165\\1\\327\\161\\66\\146\\364\\336\\202\\47\\166' &&\n+\t\t\tprintf '\\307\\142\\54\\20\\361\\260\\175\\342\\200\\334\\170' &&\n+\t\t\tprintf '\\234\\143\\142\\142\\142\\267\\003\\0\\0\\151\\0\\114'\n+\t\t\treturn\n+\t\t\t;;\n+\t\tesac\n+\t\t;;\n+\n+\t# blob containing \"\\7\\0\"\n+\t01d7713666f4de822776c7622c10f1b07de280dc)\n+\t\tcase \"$2\" in\n+\t\t'')\n+\t\t\tprintf '\\062\\170\\234\\143\\147\\0\\0\\0\\20\\0\\10'\n+\t\t\treturn\n+\t\t\t;;\n+\t\te68fe8129b546b101aee9510c5328e7f21ca1d18)\n+\t\t\tprintf '\\165\\346\\217\\350\\22\\233\\124\\153\\20\\32\\356' &&\n+\t\t\tprintf '\\225\\20\\305\\62\\216\\177\\41\\312\\35\\30\\170\\234' &&\n+\t\t\tprintf '\\143\\142\\142\\142\\147\\0\\0\\0\\53\\0\\16'\n+\t\t\treturn\n+\t\t\t;;\n \t\tesac\n \t\t;;\n \tesac\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nnew file mode 100755\nindex 0000000..9b3f2c3\n--- /dev/null\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -0,0 +1,59 @@\n+#!/bin/sh\n+\n+test_description='test index-pack handling of delta cycles in packfiles'\n+. ./test-lib.sh\n+. ../lib-pack.sh\n+\n+# Two similar-ish objects that we have computed deltas between.\n+A=01d7713666f4de822776c7622c10f1b07de280dc\n+B=e68fe8129b546b101aee9510c5328e7f21ca1d18\n+\n+# double-check our hand-constucted packs\n+test_expect_success 'index-pack works with a single delta (A->B)' '\n+\tclear_packs &&\n+\t{\n+\t\tpack_header 2 &&\n+\t\tpack_obj $A $B &&\n+\t\tpack_obj $B\n+\t} >ab.pack &&\n+\tpack_trailer ab.pack &&\n+\tgit index-pack --stdin A)' '\n+\tclear_packs &&\n+\t{\n+\t\tpack_header 2 &&\n+\t\tpack_obj $A &&\n+\t\tpack_obj $B $A\n+\t} >ba.pack &&\n+\tpack_trailer ba.pack &&\n+\tgit index-pack --stdin missing.pack &&\n+\tpack_trailer missing.pack &&\n+\ttest_must_fail git index-pack --fix-thin --stdin cycle.pack &&\n+\tpack_trailer cycle.pack &&\n+\ttest_must_fail git index-pack --fix-thin --stdin \n---\n t/t5309-pack-delta-cycles.sh | 18 ++++++++++++++++++\n 1 file changed, 18 insertions(+)\n\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 9b3f2c3..38e1809 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -56,4 +56,22 @@ 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 \n---\n builtin/index-pack.c | 4 ++++\n pack-write.c | 24 ++++++++++++++++++++++++\n pack.h | 2 ++\n t/t5308-pack-detect-duplicates.sh | 8 ++++++++\n 4 files changed, 38 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 9c1cfac..c27556f 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1369,6 +1369,10 @@ static int git_index_pack_config(const char *k, const char *v, void *cb)\n #endif\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.indexduplicates\")) {\n+\t\topts->allow_duplicates = git_config_bool(k, v);\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v, cb);\n }\n \ndiff --git a/pack-write.c b/pack-write.c\nindex ca9e63b..da946a7 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -7,6 +7,7 @@ void reset_pack_idx_option(struct pack_idx_option *opts)\n \tmemset(opts, 0, sizeof(*opts));\n \topts->version = 2;\n \topts->off32_limit = 0x7fffffff;\n+\topts->allow_duplicates = 1;\n }\n \n static int sha1_compare(const void *_a, const void *_b)\n@@ -37,6 +38,19 @@ static int need_large_offset(off_t offset, const struct pack_idx_option *opts)\n \t\t\t sizeof(ofsval), cmp_uint32);\n }\n \n+static void *find_duplicate(void *vbase, size_t n, size_t size,\n+\t\t\t int (*cmp)(const void *, const void *))\n+{\n+\tunsigned char *base = vbase;\n+\twhile (n > 1) {\n+\t\tif (!cmp(base, base + size))\n+\t\t\treturn base;\n+\t\tbase += size;\n+\t\tn--;\n+\t}\n+\treturn NULL;\n+}\n+\n /*\n * On entry *sha1 contains the pack content SHA1 hash, on exit it is\n * the SHA1 hash of sorted object names. The objects array passed in\n@@ -68,6 +82,16 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \telse\n \t\tsorted_by_sha = list = last = NULL;\n \n+\tif (!opts->allow_duplicates) {\n+\t\tstruct pack_idx_entry **dup;\n+\n+\t\tdup = find_duplicate(sorted_by_sha, nr_objects,\n+\t\t\t\t sizeof(*sorted_by_sha), sha1_compare);\n+\t\tif (dup)\n+\t\t\tdie(\"pack has duplicate entries for %s\",\n+\t\t\t sha1_to_hex((*dup)->sha1));\n+\t}\n+\n \tif (opts->flags & WRITE_IDX_VERIFY) {\n \t\tassert(index_name);\n \t\tf = sha1fd_check(index_name);\ndiff --git a/pack.h b/pack.h\nindex aa6ee7d..45217b6 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -44,6 +44,8 @@ struct pack_idx_option {\n \tuint32_t version;\n \tuint32_t off32_limit;\n \n+\tint allow_duplicates;\n+\n \t/*\n \t * List of offsets that would fit within off32_limit but\n \t * need to be written out as 64-bit entity for byte-for-byte\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 719d48f..cb9b44e 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -70,4 +70,12 @@ test_expect_success 'lookup in duplicated pack (GIT_USE_LOOKUP)' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'index-pack can reject packs with duplicates' '\n+\tclear_packs &&\n+\tcreate_pack dups.pack 2 &&\n+\ttest_must_fail \\\n+\t\tgit -c pack.indexDuplicates=0 index-pack --stdin \n---\n pack-write.c | 1 -\n t/t5308-pack-detect-duplicates.sh | 9 ++++-----\n 2 files changed, 4 insertions(+), 6 deletions(-)\n\ndiff --git a/pack-write.c b/pack-write.c\nindex da946a7..1e3c459 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -7,7 +7,6 @@ void reset_pack_idx_option(struct pack_idx_option *opts)\n \tmemset(opts, 0, sizeof(*opts));\n \topts->version = 2;\n \topts->off32_limit = 0x7fffffff;\n-\topts->allow_duplicates = 1;\n }\n \n static int sha1_compare(const void *_a, const void *_b)\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex cb9b44e..e982095 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -37,10 +37,10 @@ test_expect_success 'index-pack will allow duplicate objects by default' '\n \tgit index-pack --stdin On Thu, Aug 22, 2013 at 10:43:05AM -0400, Jeff King wrote:\n> \n> > > write_idx_file() is called after index-pack processes all delta\n> > > objects. Could resolve_deltas() go cyclic with certain duplicate\n> > > object setup?\n> > \n> > Good question. I'm not sure. I'll check it out.\n> \n> I think the answer is \"no\", based on both reasoning and testing (both of\n> which are included in patches 3-4 of the series below).\n> \n> So here's my re-roll of the series.\n\nThis looks all good to me.\n\n\nAcked-by: Nicolas Pitre \n\n\nNicolas\n"},{"id":"225722","messageId":"xmqqob8opdey.fsf@gitster.dls.corp.google.com","threadId":"34695","inReplyTo":"20130822231404.GB17060@sigill.intra.peff.net","subject":"Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-23T16:41:57Z","receivedAt":"2013-08-23T16:41:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Furthermore, we know that one of our endpoints must be\n> the edge of the run of duplicates. For example, given this\n> sequence:\n>\n> idx 0 1 2 3 4 5\n> key A C C C C D\n>\n> If we are searching for \"B\", we might hit the duplicate run\n> at lo=1, hi=3 (e.g., by first mi=3, then mi=0). But we can\n> never have lo > 1, because B < C. That is, if our key is\n> less than the run, we know that \"lo\" is the edge, but we can\n> say nothing of \"hi\". Similarly, if our key is greater than\n> the run, we know that \"hi\" is the edge, but we can say\n> nothing of \"lo\". But that is enough for us to return not\n> only \"not found\", but show the position at which we would\n> insert the new item.\n\nThis is somewhat tricky and may deserve an in-code comment.\n\n> diff --git a/sha1-lookup.c b/sha1-lookup.c\n> index c4dc55d..614cbb6 100644\n> --- a/sha1-lookup.c\n> +++ b/sha1-lookup.c\n> @@ -204,7 +204,30 @@ int sha1_entry_pos(const void *table,\n> \t\t\t * byte 0 thru (ofs-1) are the same between\n> \t\t\t * lo and hi; ofs is the first byte that is\n> \t\t\t * different.\n> +\t\t\t *\n> +\t\t\t * If ofs==20, then no bytes are different,\n> +\t\t\t * meaning we have entries with duplicate\n> +\t\t\t * keys. We know that we are in a solid run\n> +\t\t\t * of this entry (because the entries are\n> +\t\t\t * sorted, and our lo and hi are the same,\n> +\t\t\t * there can be nothing but this single key\n> +\t\t\t * in between). So we can stop the search.\n> +\t\t\t * Either one of these entries is it (and\n> +\t\t\t * we do not care which), or we do not have\n> +\t\t\t * it.\n> \t\t\t */\n> +\t\t\tif (ofs == 20) {\n> +\t\t\t\tmi = lo;\n> +\t\t\t\tmi_key = base + elem_size * mi + key_offset;\n> +\t\t\t\tcmp = memcmp(mi_key, key, 20);\n\nIt think we already know that mi_key[0:ofs_0] and key[0:ofs_0] are\nthe same at this point and we do not have to compare full 20 bytes\nagain, but this is done only once and a better readablity of the\nabove trumps micro-optimization possibility, I think.\n\n> +\t\t\t\tif (!cmp)\n> +\t\t\t\t\treturn mi;\n> +\t\t\t\tif (cmp < 0)\n> +\t\t\t\t\treturn -1 - hi;\n> +\t\t\t\telse\n> +\t\t\t\t\treturn -1 - lo;\n> +\t\t\t}\n> +\n> \t\t\thiv = hi_key[ofs_0];\n> \t\t\tif (ofs_0 < 19)\n> \t\t\t\thiv = (hiv << 8) | hi_key[ofs_0+1];\n> diff --git a/t/lib-pack.sh b/t/lib-pack.sh\n> new file mode 100644\n> index 0000000..61c5d19\n> --- /dev/null\n> +++ b/t/lib-pack.sh\n> @@ -0,0 +1,78 @@\n> +#!/bin/sh\n> +#\n> +# Support routines for hand-crafting weird or malicious packs.\n> +#\n> +# You can make a complete pack like:\n> +#\n> +# pack_header 2 >foo.pack &&\n> +# pack_obj e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 >>foo.pack &&\n> +# pack_obj e68fe8129b546b101aee9510c5328e7f21ca1d18 >>foo.pack &&\n> +# pack_trailer foo.pack\n> +\n> +# Print the big-endian 4-byte octal representation of $1\n> +uint32_octal() {\n\nmicronit (style):\n\n\tuint32_octal () {\n\n> +\tn=$1\n> +\tprintf '\\%o' $(($n / 16777216)); n=$((n % 16777216))\n> +\tprintf '\\%o' $(($n / 65536)); n=$((n % 65536))\n> +\tprintf '\\%o' $(($n / 256)); n=$((n % 256))\n> +\tprintf '\\%o' $(($n ));\n> +}\n> +\n> +# Print the big-endian 4-byte binary representation of $1\n> +uint32_binary() {\n> +\tprintf \"$(uint32_octal \"$1\")\"\n> +}\n> +\n> +# Print a pack header, version 2, for a pack with $1 objects\n> +pack_header() {\n> +\tprintf 'PACK' &&\n> +\tprintf '\\0\\0\\0\\2' &&\n> +\tuint32_binary \"$1\"\n> +}\n> +\n> +# Print the pack data for object $1, as a delta against object $2 (or as a full\n> +# object if $2 is missing or empty). The output is suitable for including\n> +# directly in the packfile, and represents the entirety of the object entry.\n> +# Doing this on the fly (especially picking your deltas) is quite tricky, so we\n> +# have hardcoded some well-known objects. See the case statements below for the\n> +# complete list.\n\nCute ;-) I like the idea of having this function with a right API in\nplace, and cheating by limiting its implementation to what is\nnecessary.\n\nThanks.\n"},{"id":"225730","messageId":"20130823182409.GA30130@sigill.intra.peff.net","threadId":"34695","inReplyTo":"xmqqob8opdey.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-23T18:24:10Z","receivedAt":"2013-08-23T18:24:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 23, 2013 at 09:41:57AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Furthermore, we know that one of our endpoints must be\n> > the edge of the run of duplicates. For example, given this\n> > sequence:\n> >\n> > idx 0 1 2 3 4 5\n> > key A C C C C D\n> >\n> > If we are searching for \"B\", we might hit the duplicate run\n> > at lo=1, hi=3 (e.g., by first mi=3, then mi=0). But we can\n> > never have lo > 1, because B < C. That is, if our key is\n> > less than the run, we know that \"lo\" is the edge, but we can\n> > say nothing of \"hi\". Similarly, if our key is greater than\n> > the run, we know that \"hi\" is the edge, but we can say\n> > nothing of \"lo\". But that is enough for us to return not\n> > only \"not found\", but show the position at which we would\n> > insert the new item.\n> \n> This is somewhat tricky and may deserve an in-code comment.\n\nDo you want me to re-roll, pushing it down into the comment, or do you\nwant to mark it up yourself? I think there might be some value in the\nlatter as your re-writing of it as a comment may cross-check that my\nlogic is sound.\n\n> > +\t\t\tif (ofs == 20) {\n> > +\t\t\t\tmi = lo;\n> > +\t\t\t\tmi_key = base + elem_size * mi + key_offset;\n> > +\t\t\t\tcmp = memcmp(mi_key, key, 20);\n> \n> It think we already know that mi_key[0:ofs_0] and key[0:ofs_0] are\n> the same at this point and we do not have to compare full 20 bytes\n> again, but this is done only once and a better readablity of the\n> above trumps micro-optimization possibility, I think.\n\nYes, I had the same idea, and came to the same conclusion. Though if\nanybody did want to try it, note that we have just overwritten the old\nofs_0, so you would want to bump the new code up above that line).\n\n> > +uint32_octal() {\n> \n> micronit (style):\n> \n> \tuint32_octal () {\n\nHmph. I always forget which one we prefer, and we seem to have equal\nnumbers of both already. Again, want a re-roll or to mark it up\nyourself?\n\n> > +# Print the pack data for object $1, as a delta against object $2 (or as a full\n> > +# object if $2 is missing or empty). The output is suitable for including\n> > +# directly in the packfile, and represents the entirety of the object entry.\n> > +# Doing this on the fly (especially picking your deltas) is quite tricky, so we\n> > +# have hardcoded some well-known objects. See the case statements below for the\n> > +# complete list.\n> \n> Cute ;-) I like the idea of having this function with a right API in\n> place, and cheating by limiting its implementation to what is\n> necessary.\n\nJust for reference, the procedure I used to generate the \"base\" data is\nreasonably straight forward:\n\n sha1=$(printf %s \"$content\" | git hash-object -w --stdin)\n echo $sha1 | git pack-objects --stdout >tmp.pack\n tail -c +13 tmp.pack >no-header.pack\n head -c -20 no-header.pack >no-trailer.pack\n od -b no-trailer.pack | grep ' ' | cut -d' ' -f2- | tr ' ' '\\\\'\n\nSince we want binary, we can skip the \"od\" call at the end (I needed it\nto convert to something readable to hand \"printf\"). But \"head -c\" is not\nportable, nor is head with a negative count.\n\nTo find items in the same fanout, I just used for-loops to calculate the\nsha1s of all 2-byte blobs. And that is why we have the odd magic \"\\7\\76\"\nblob.\n\nMaking the deltas was considerably less elegant, since we cannot provoke\npack-objects to pick arbitrary deltas (and it will not even try to delta\ntiny objects, anyway, which would bloat our samples). I ended up with\nthe horrible patch below. We _could_ clean it up (error-checking? Who\nneeds it?) and make it a debug-and-testing-only option for pack-objects,\nbut I just didn't think the grossness was worth it. Still, it's probably\nworth documenting here on the list in case somebody else ever needs to\nadd new samples to lib-pack.sh.\n\n---\n builtin/pack-objects.c | 30 ++++++++++++++++++++++++++++++\n 1 file changed, 30 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 8da2a66..e8937f5 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2442,6 +2442,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tconst char *rp_av[6];\n \tint rp_ac = 0;\n \tint rev_list_unpacked = 0, rev_list_all = 0, rev_list_reflog = 0;\n+\tint magic = 0;\n \tstruct option pack_objects_options[] = {\n \t\tOPT_SET_INT('q', \"quiet\", &progress,\n \t\t\t N_(\"do not show progress meter\"), 0),\n@@ -2505,6 +2506,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\t N_(\"pack compression level\")),\n \t\tOPT_SET_INT(0, \"keep-true-parents\", &grafts_replace_parents,\n \t\t\t N_(\"do not hide commits by grafts\"), 0),\n+\t\tOPT_BOOL(0, \"magic\", &magic, \"make deltas\"),\n \t\tOPT_END(),\n \t};\n \n@@ -2520,6 +2522,34 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \targc = parse_options(argc, argv, prefix, pack_objects_options,\n \t\t\t pack_usage, 0);\n \n+\tif (magic) {\n+\t\tunsigned char sha1[20];\n+\t\tstruct delta_index *index;\n+\t\tvoid *src, *trg, *delta;\n+\t\tenum object_type src_type, trg_type;\n+\t\tunsigned long src_size, trg_size, delta_size, z_delta_size;\n+\t\tunsigned char header[10];\n+\t\tunsigned long header_len;\n+\n+\t\tget_sha1(argv[0], sha1);\n+\t\ttrg = read_sha1_file(sha1, &trg_type, &trg_size);\n+\n+\t\tget_sha1(argv[1], sha1);\n+\t\tsrc = read_sha1_file(sha1, &src_type, &src_size);\n+\n+\t\tindex = create_delta_index(src, src_size);\n+\t\tdelta = create_delta(index, trg, trg_size, &delta_size, 8192);\n+\n+\t\tz_delta_size = do_compress(&delta, delta_size);\n+\t\theader_len = encode_in_pack_object_header(OBJ_REF_DELTA, delta_size,\n+\t\t\t\t\t\t\t header);\n+\t\tfwrite(header, 1, header_len, stdout);\n+\t\tfwrite(sha1, 1, 20, stdout);\n+\t\tfwrite(delta, 1, z_delta_size, stdout);\n+\t\treturn 0;\n+\t}\n+\n+\n \tif (argc) {\n \t\tbase_name = argv[0];\n \t\targc--;\n"},{"id":"225733","messageId":"alpine.LFD.2.03.1308231451030.14472@syhkavp.arg","threadId":"34695","inReplyTo":"20130823182409.GA30130@sigill.intra.peff.net","subject":"Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-23T18:54:19Z","receivedAt":"2013-08-23T18:54:19Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 23 Aug 2013, Jeff King wrote:\n\n> Making the deltas was considerably less elegant, since we cannot provoke\n> pack-objects to pick arbitrary deltas (and it will not even try to delta\n> tiny objects, anyway, which would bloat our samples). I ended up with\n> the horrible patch below. We _could_ clean it up (error-checking? Who\n> needs it?) and make it a debug-and-testing-only option for pack-objects,\n> but I just didn't think the grossness was worth it. Still, it's probably\n> worth documenting here on the list in case somebody else ever needs to\n> add new samples to lib-pack.sh.\n\nMaybe using test-delta (from test-delta.c) would have helped here?\n\nIn any case, if something needs to be permanently added into the code to \nhelp in the creation of test objects, I think test-delta.c is a far \nbetter place than pack-objects.c.\n\n\nNicolas\n"},{"id":"225734","messageId":"20130823185618.GD30130@sigill.intra.peff.net","threadId":"34695","inReplyTo":"alpine.LFD.2.03.1308231451030.14472@syhkavp.arg","subject":"Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-23T18:56:18Z","receivedAt":"2013-08-23T18:56:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 23, 2013 at 02:54:19PM -0400, Nicolas Pitre wrote:\n\n> On Fri, 23 Aug 2013, Jeff King wrote:\n> \n> > Making the deltas was considerably less elegant, since we cannot provoke\n> > pack-objects to pick arbitrary deltas (and it will not even try to delta\n> > tiny objects, anyway, which would bloat our samples). I ended up with\n> > the horrible patch below. We _could_ clean it up (error-checking? Who\n> > needs it?) and make it a debug-and-testing-only option for pack-objects,\n> > but I just didn't think the grossness was worth it. Still, it's probably\n> > worth documenting here on the list in case somebody else ever needs to\n> > add new samples to lib-pack.sh.\n> \n> Maybe using test-delta (from test-delta.c) would have helped here?\n> \n> In any case, if something needs to be permanently added into the code to \n> help in the creation of test objects, I think test-delta.c is a far \n> better place than pack-objects.c.\n\n*forehead palm*\n\nI didn't even know we had test-delta. Yes, that is obviously a way\nbetter place (I initially looked at pack-objects because it has the\nhelpers to do compression and the type/size header properly).\n\n-Peff\n"},{"id":"225738","messageId":"5217BAF3.2000702@kdbg.org","threadId":"34695","inReplyTo":"20130822231404.GB17060@sigill.intra.peff.net","subject":"Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2013-08-23T19:41:39Z","receivedAt":"2013-08-23T19:41:39Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 23.08.2013 01:14, schrieb Jeff King:\n> +++ b/t/t5308-pack-detect-duplicates.sh\n> @@ -0,0 +1,73 @@\n> +#!/bin/sh\n> +\n> +test_description='handling of duplicate objects in incoming packfiles'\n> +. ./test-lib.sh\n> +. ../lib-pack.sh\n\nThis should be\n\n. \"$TEST_DIRECTORY\"/lib-pack.sh\n\nto support running tests with --root (also in patch 3/6).\n\n-- Hannes\n"},{"id":"225750","messageId":"20130823233752.GA19125@sigill.intra.peff.net","threadId":"34695","inReplyTo":"5217BAF3.2000702@kdbg.org","subject":"Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-23T23:37:53Z","receivedAt":"2013-08-23T23:37:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 23, 2013 at 09:41:39PM +0200, Johannes Sixt wrote:\n\n> Am 23.08.2013 01:14, schrieb Jeff King:\n> >+++ b/t/t5308-pack-detect-duplicates.sh\n> >@@ -0,0 +1,73 @@\n> >+#!/bin/sh\n> >+\n> >+test_description='handling of duplicate objects in incoming packfiles'\n> >+. ./test-lib.sh\n> >+. ../lib-pack.sh\n> \n> This should be\n> \n> . \"$TEST_DIRECTORY\"/lib-pack.sh\n> \n> to support running tests with --root (also in patch 3/6).\n\nDoh, you would think that I would remember that, as the one who\nintroduced \"--root\" in the first place.\n\nWill fix. Thanks for noticing.\n\n-Peff\n"},{"id":"225752","messageId":"20130824000111.GA20255@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130823182409.GA30130@sigill.intra.peff.net","subject":"[PATCHv3 0/6] duplicate objects and delta cycles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-24T00:01:11Z","receivedAt":"2013-08-24T00:01:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 23, 2013 at 02:24:10PM -0400, Jeff King wrote:\n\n> > This is somewhat tricky and may deserve an in-code comment.\n> \n> Do you want me to re-roll[...]\n\nSince there were a few things to fix, I went ahead and re-rolled. Here's\nv3, which changes:\n\n 1. Move \"edge of run\" logic description into the in-code comment\n rather than the commit message.\n\n 2. Include space between shell function names and parentheses.\n\n 3. Use $TEST_DIRECTORY to find lib-pack so that \"--root\" works.\n\nI added in Nicolas's acks, too, as this version makes no changes of\nsubstance from the previous ack'd version. Interdiff is below.\n\n sha1-lookup.c | 24 ++++++++++++++++++++++++\n t/lib-pack.sh | 12 ++++++------\n t/t5308-pack-detect-duplicates.sh | 4 ++--\n t/t5309-pack-delta-cycles.sh | 2 +-\n 4 files changed, 33 insertions(+), 9 deletions(-)\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex 614cbb6..2dd8515 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -215,6 +215,30 @@ int sha1_entry_pos(const void *table,\n \t\t\t * Either one of these entries is it (and\n \t\t\t * we do not care which), or we do not have\n \t\t\t * it.\n+\t\t\t *\n+\t\t\t * Furthermore, we know that one of our\n+\t\t\t * endpoints must be the edge of the run of\n+\t\t\t * duplicates. For example, given this\n+\t\t\t * sequence:\n+\t\t\t *\n+\t\t\t * idx 0 1 2 3 4 5\n+\t\t\t * key A C C C C D\n+\t\t\t *\n+\t\t\t * If we are searching for \"B\", we might\n+\t\t\t * hit the duplicate run at lo=1, hi=3\n+\t\t\t * (e.g., by first mi=3, then mi=0). But we\n+\t\t\t * can never have lo > 1, because B < C.\n+\t\t\t * That is, if our key is less than the\n+\t\t\t * run, we know that \"lo\" is the edge, but\n+\t\t\t * we can say nothing of \"hi\". Similarly,\n+\t\t\t * if our key is greater than the run, we\n+\t\t\t * know that \"hi\" is the edge, but we can\n+\t\t\t * say nothing of \"lo\".\n+\t\t\t *\n+\t\t\t * Therefore if we do not find it, we also\n+\t\t\t * know where it would go if it did exist:\n+\t\t\t * just on the far side of the edge that we\n+\t\t\t * know about.\n \t\t\t */\n \t\t\tif (ofs == 20) {\n \t\t\t\tmi = lo;\ndiff --git a/t/lib-pack.sh b/t/lib-pack.sh\nindex e028c40..7e8685b 100644\n--- a/t/lib-pack.sh\n+++ b/t/lib-pack.sh\n@@ -10,7 +10,7 @@\n # pack_trailer foo.pack\n \n # Print the big-endian 4-byte octal representation of $1\n-uint32_octal() {\n+uint32_octal () {\n \tn=$1\n \tprintf '\\%o' $(($n / 16777216)); n=$((n % 16777216))\n \tprintf '\\%o' $(($n / 65536)); n=$((n % 65536))\n@@ -19,12 +19,12 @@ uint32_binary() {\n }\n \n # Print the big-endian 4-byte binary representation of $1\n-uint32_binary() {\n+uint32_binary () {\n \tprintf \"$(uint32_octal \"$1\")\"\n }\n \n # Print a pack header, version 2, for a pack with $1 objects\n-pack_header() {\n+pack_header () {\n \tprintf 'PACK' &&\n \tprintf '\\0\\0\\0\\2' &&\n \tuint32_binary \"$1\"\n@@ -36,7 +36,7 @@ pack_header() {\n # Doing this on the fly (especially picking your deltas) is quite tricky, so we\n # have hardcoded some well-known objects. See the case statements below for the\n # complete list.\n-pack_obj() {\n+pack_obj () {\n \tcase \"$1\" in\n \t# empty blob\n \te69de29bb2d1d6434b8b29ae775ad8c2e48c5391)\n@@ -86,7 +86,7 @@ pack_obj() {\n }\n \n # Compute and append pack trailer to \"$1\"\n-pack_trailer() {\n+pack_trailer () {\n \ttest-sha1 -b <\"$1\" >trailer.tmp &&\n \tcat trailer.tmp >>\"$1\" &&\n \trm -f trailer.tmp\n@@ -95,6 +95,6 @@ pack_trailer() {\n # Remove any existing packs to make sure that\n # whatever we index next will be the pack that we\n # actually use.\n-clear_packs() {\n+clear_packs () {\n \trm -f .git/objects/pack/*\n }\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex e982095..e0ba5e1 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -2,7 +2,7 @@ test_description='handling of duplicate objects in incoming packfiles'\n \n test_description='handling of duplicate objects in incoming packfiles'\n . ./test-lib.sh\n-. ../lib-pack.sh\n+. \"$TEST_DIRECTORY\"/lib-pack.sh\n \n # The sha1s we have in our pack. It's important that these have the same\n # starting byte, so that they end up in the same fanout section of the index.\n@@ -22,7 +22,7 @@ MISSING_SHA1='e69d000000000000000000000000000000000000'\n # $1 is the name of the packfile to create\n #\n # $2 is the number of times to duplicate each object\n-create_pack() {\n+create_pack () {\n \tpack_header \"$((2 * $2))\" >\"$1\" &&\n \tfor i in $(test_seq 1 \"$2\"); do\n \t\tpack_obj $LO_SHA1 &&\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 38e1809..3e7861b 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -2,7 +2,7 @@ test_description='test index-pack handling of delta cycles in packfiles'\n \n test_description='test index-pack handling of delta cycles in packfiles'\n . ./test-lib.sh\n-. ../lib-pack.sh\n+. \"$TEST_DIRECTORY\"/lib-pack.sh\n \n # Two similar-ish objects that we have computed deltas between.\n A=01d7713666f4de822776c7622c10f1b07de280dc\n"},{"id":"225753","messageId":"20130824000157.GA25833@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130824000111.GA20255@sigill.intra.peff.net","subject":"[PATCH 1/6] test-sha1: add a binary output mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-24T00:01:57Z","receivedAt":"2013-08-24T00:01:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The test-sha1 helper program will run our internal sha1\nroutines over its input and output the 40-byte hex sha1.\nSometimes, however, it is useful to have the binary 20-byte\nsha1 (and it's a pain to convert back in the shell). Let's\nadd a \"-b\" option to output the binary version.\n\nSigned-off-by: Jeff King \nAcked-by: Nicolas Pitre \n---\n test-sha1.c | 15 ++++++++++++---\n 1 file changed, 12 insertions(+), 3 deletions(-)\n\ndiff --git a/test-sha1.c b/test-sha1.c\nindex 80daba9..e57eae1 100644\n--- a/test-sha1.c\n+++ b/test-sha1.c\n@@ -5,10 +5,15 @@ int main(int ac, char **av)\n \tgit_SHA_CTX ctx;\n \tunsigned char sha1[20];\n \tunsigned bufsz = 8192;\n+\tint binary = 0;\n \tchar *buffer;\n \n-\tif (ac == 2)\n-\t\tbufsz = strtoul(av[1], NULL, 10) * 1024 * 1024;\n+\tif (ac == 2) {\n+\t\tif (!strcmp(av[1], \"-b\"))\n+\t\t\tbinary = 1;\n+\t\telse\n+\t\t\tbufsz = strtoul(av[1], NULL, 10) * 1024 * 1024;\n+\t}\n \n \tif (!bufsz)\n \t\tbufsz = 8192;\n@@ -42,6 +47,10 @@ int main(int ac, char **av)\n \t\tgit_SHA1_Update(&ctx, buffer, this_sz);\n \t}\n \tgit_SHA1_Final(sha1, &ctx);\n-\tputs(sha1_to_hex(sha1));\n+\n+\tif (binary)\n+\t\tfwrite(sha1, 1, 20, stdout);\n+\telse\n+\t\tputs(sha1_to_hex(sha1));\n \texit(0);\n }\n-- \n1.8.4.rc2.28.g6bb5f3f\n"},{"id":"225754","messageId":"20130824000225.GB25833@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130824000111.GA20255@sigill.intra.peff.net","subject":"[PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-24T00:02:25Z","receivedAt":"2013-08-24T00:02:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The sha1_entry_pos function tries to be smart about\nselecting the middle of a range for its binary search by\nlooking at the value differences between the \"lo\" and \"hi\"\nconstraints. However, it is unable to cope with entries with\nduplicate keys in the sorted list.\n\nWe may hit a point in the search where both our \"lo\" and\n\"hi\" point to the same key. In this case, the range of\nvalues between our endpoints is 0, and trying to scale the\ndifference between our key and the endpoints over that range\nis undefined (i.e., divide by zero). The current code\ncatches this with an \"assert(lov < hiv)\".\n\nMoreover, after seeing that the first 20 byte of the key are\nthe same, we will try to establish a value from the 21st\nbyte. Which is nonsensical.\n\nInstead, we can detect the case that we are in a run of\nduplicates, and simply do a final comparison against any one\nof them (since they are all the same, it does not matter\nwhich). If the keys match, we have found our entry (or one\nof them, anyway). If not, then we know that we do not need\nto look further, as we must be in a run of the duplicate\nkey.\n\nSigned-off-by: Jeff King \nAcked-by: Nicolas Pitre \n---\n sha1-lookup.c | 47 +++++++++++++++++++++++\n t/lib-pack.sh | 78 +++++++++++++++++++++++++++++++++++++++\n t/t5308-pack-detect-duplicates.sh | 73 ++++++++++++++++++++++++++++++++++++\n 3 files changed, 198 insertions(+)\n create mode 100644 t/lib-pack.sh\n create mode 100755 t/t5308-pack-detect-duplicates.sh\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex c4dc55d..2dd8515 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -204,7 +204,54 @@ int sha1_entry_pos(const void *table,\n \t\t\t * byte 0 thru (ofs-1) are the same between\n \t\t\t * lo and hi; ofs is the first byte that is\n \t\t\t * different.\n+\t\t\t *\n+\t\t\t * If ofs==20, then no bytes are different,\n+\t\t\t * meaning we have entries with duplicate\n+\t\t\t * keys. We know that we are in a solid run\n+\t\t\t * of this entry (because the entries are\n+\t\t\t * sorted, and our lo and hi are the same,\n+\t\t\t * there can be nothing but this single key\n+\t\t\t * in between). So we can stop the search.\n+\t\t\t * Either one of these entries is it (and\n+\t\t\t * we do not care which), or we do not have\n+\t\t\t * it.\n+\t\t\t *\n+\t\t\t * Furthermore, we know that one of our\n+\t\t\t * endpoints must be the edge of the run of\n+\t\t\t * duplicates. For example, given this\n+\t\t\t * sequence:\n+\t\t\t *\n+\t\t\t * idx 0 1 2 3 4 5\n+\t\t\t * key A C C C C D\n+\t\t\t *\n+\t\t\t * If we are searching for \"B\", we might\n+\t\t\t * hit the duplicate run at lo=1, hi=3\n+\t\t\t * (e.g., by first mi=3, then mi=0). But we\n+\t\t\t * can never have lo > 1, because B < C.\n+\t\t\t * That is, if our key is less than the\n+\t\t\t * run, we know that \"lo\" is the edge, but\n+\t\t\t * we can say nothing of \"hi\". Similarly,\n+\t\t\t * if our key is greater than the run, we\n+\t\t\t * know that \"hi\" is the edge, but we can\n+\t\t\t * say nothing of \"lo\".\n+\t\t\t *\n+\t\t\t * Therefore if we do not find it, we also\n+\t\t\t * know where it would go if it did exist:\n+\t\t\t * just on the far side of the edge that we\n+\t\t\t * know about.\n \t\t\t */\n+\t\t\tif (ofs == 20) {\n+\t\t\t\tmi = lo;\n+\t\t\t\tmi_key = base + elem_size * mi + key_offset;\n+\t\t\t\tcmp = memcmp(mi_key, key, 20);\n+\t\t\t\tif (!cmp)\n+\t\t\t\t\treturn mi;\n+\t\t\t\tif (cmp < 0)\n+\t\t\t\t\treturn -1 - hi;\n+\t\t\t\telse\n+\t\t\t\t\treturn -1 - lo;\n+\t\t\t}\n+\n \t\t\thiv = hi_key[ofs_0];\n \t\t\tif (ofs_0 < 19)\n \t\t\t\thiv = (hiv << 8) | hi_key[ofs_0+1];\ndiff --git a/t/lib-pack.sh b/t/lib-pack.sh\nnew file mode 100644\nindex 0000000..fecd5a0\n--- /dev/null\n+++ b/t/lib-pack.sh\n@@ -0,0 +1,78 @@\n+#!/bin/sh\n+#\n+# Support routines for hand-crafting weird or malicious packs.\n+#\n+# You can make a complete pack like:\n+#\n+# pack_header 2 >foo.pack &&\n+# pack_obj e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 >>foo.pack &&\n+# pack_obj e68fe8129b546b101aee9510c5328e7f21ca1d18 >>foo.pack &&\n+# pack_trailer foo.pack\n+\n+# Print the big-endian 4-byte octal representation of $1\n+uint32_octal () {\n+\tn=$1\n+\tprintf '\\%o' $(($n / 16777216)); n=$((n % 16777216))\n+\tprintf '\\%o' $(($n / 65536)); n=$((n % 65536))\n+\tprintf '\\%o' $(($n / 256)); n=$((n % 256))\n+\tprintf '\\%o' $(($n ));\n+}\n+\n+# Print the big-endian 4-byte binary representation of $1\n+uint32_binary () {\n+\tprintf \"$(uint32_octal \"$1\")\"\n+}\n+\n+# Print a pack header, version 2, for a pack with $1 objects\n+pack_header () {\n+\tprintf 'PACK' &&\n+\tprintf '\\0\\0\\0\\2' &&\n+\tuint32_binary \"$1\"\n+}\n+\n+# Print the pack data for object $1, as a delta against object $2 (or as a full\n+# object if $2 is missing or empty). The output is suitable for including\n+# directly in the packfile, and represents the entirety of the object entry.\n+# Doing this on the fly (especially picking your deltas) is quite tricky, so we\n+# have hardcoded some well-known objects. See the case statements below for the\n+# complete list.\n+pack_obj () {\n+\tcase \"$1\" in\n+\t# empty blob\n+\te69de29bb2d1d6434b8b29ae775ad8c2e48c5391)\n+\t\tcase \"$2\" in\n+\t\t'')\n+\t\t\tprintf '\\060\\170\\234\\003\\0\\0\\0\\0\\1'\n+\t\t\treturn\n+\t\t\t;;\n+\t\tesac\n+\t\t;;\n+\n+\t# blob containing \"\\7\\76\"\n+\te68fe8129b546b101aee9510c5328e7f21ca1d18)\n+\t\tcase \"$2\" in\n+\t\t'')\n+\t\t\tprintf '\\062\\170\\234\\143\\267\\3\\0\\0\\116\\0\\106'\n+\t\t\treturn\n+\t\t\t;;\n+\t\tesac\n+\t\t;;\n+\tesac\n+\n+\techo >&2 \"BUG: don't know how to print $1${2:+ (from $2)}\"\n+\treturn 1\n+}\n+\n+# Compute and append pack trailer to \"$1\"\n+pack_trailer () {\n+\ttest-sha1 -b <\"$1\" >trailer.tmp &&\n+\tcat trailer.tmp >>\"$1\" &&\n+\trm -f trailer.tmp\n+}\n+\n+# Remove any existing packs to make sure that\n+# whatever we index next will be the pack that we\n+# actually use.\n+clear_packs () {\n+\trm -f .git/objects/pack/*\n+}\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nnew file mode 100755\nindex 0000000..04fe242\n--- /dev/null\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -0,0 +1,73 @@\n+#!/bin/sh\n+\n+test_description='handling of duplicate objects in incoming packfiles'\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-pack.sh\n+\n+# The sha1s we have in our pack. It's important that these have the same\n+# starting byte, so that they end up in the same fanout section of the index.\n+# That lets us make sure we are exercising the binary search with both sets.\n+LO_SHA1=e68fe8129b546b101aee9510c5328e7f21ca1d18\n+HI_SHA1=e69de29bb2d1d6434b8b29ae775ad8c2e48c5391\n+\n+# And here's a \"missing sha1\" which will produce failed lookups. It must also\n+# be in the same fanout section, and should be between the two (so that during\n+# our binary search, we are sure to end up looking at one or the other of the\n+# duplicate runs).\n+MISSING_SHA1='e69d000000000000000000000000000000000000'\n+\n+# git will never intentionally create packfiles with\n+# duplicate objects, so we have to construct them by hand.\n+#\n+# $1 is the name of the packfile to create\n+#\n+# $2 is the number of times to duplicate each object\n+create_pack () {\n+\tpack_header \"$((2 * $2))\" >\"$1\" &&\n+\tfor i in $(test_seq 1 \"$2\"); do\n+\t\tpack_obj $LO_SHA1 &&\n+\t\tpack_obj $HI_SHA1\n+\tdone >>\"$1\" &&\n+\tpack_trailer \"$1\"\n+}\n+\n+# double-check that create_pack actually works\n+test_expect_success 'pack with no duplicates' '\n+\tcreate_pack no-dups.pack 1 &&\n+\tgit index-pack --stdin input <<-EOF &&\n+\t$LO_SHA1\n+\t$HI_SHA1\n+\t$MISSING_SHA1\n+\tEOF\n+\tcat >expect <<-EOF\n+\t$LO_SHA1 blob 2\n+\t$HI_SHA1 blob 0\n+\t$MISSING_SHA1 missing\n+\tEOF\n+'\n+\n+test_expect_success 'lookup in duplicated pack (binary search)' '\n+\tgit cat-file --batch-check actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'lookup in duplicated pack (GIT_USE_LOOKUP)' '\n+\t(\n+\t\tGIT_USE_LOOKUP=1 &&\n+\t\texport GIT_USE_LOOKUP &&\n+\t\tgit cat-file --batch-check actual\n+\t) &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n1.8.4.rc2.28.g6bb5f3f\n"},{"id":"225755","messageId":"20130824000231.GC25833@sigill.intra.peff.net","threadId":"34695","inReplyTo":"20130824000111.GA20255@sigill.intra.peff.net","subject":"[PATCH 3/6] add tests for indexing packs with delta cycles","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-24T00:02:31Z","receivedAt":"2013-08-24T00:02:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If we receive a broken or malicious pack from a remote, we\nwill feed it to index-pack. As index-pack processes the\nobjects as a stream, reconstructing and hashing each object\nto get its name, it is not very susceptible to doing the\nwrong with bad data (it simply notices that the data is\nbogus and aborts).\n\nHowever, one question raised on the list is whether it could\nbe susceptible to problems during the delta-resolution\nphase. In particular, can a cycle in the packfile deltas\ncause us to go into an infinite loop or cause any other\nproblem?\n\nThe answer is no.\n\nWe cannot have a cycle of delta-base offsets, because they\ngo only in one direction (the OFS_DELTA object mentions its\nbase by an offset towards the beginning of the file, and we\nexplicitly reject negative offsets).\n\nWe can have a cycle of REF_DELTA objects, which refer to\nbase objects by sha1 name. However, index-pack does not know\nthese sha1 names ahead of time; it has to reconstruct the\nobjects to get their names, and it cannot do so if there is\na delta cycle (in other words, it does not even realize\nthere is a cycle, but only that there are items that cannot\nbe resolved).\n\nEven though we can reason out that index-pack should handle\nthis fine, let's add a few tests to make sure it behaves\ncorrectly.\n\nSigned-off-by: Jeff King \nAcked-by: Nicolas Pitre \n---\n t/lib-pack.sh | 22 +++++++++++++++++\n t/t5309-pack-delta-cycles.sh | 59 ++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 81 insertions(+)\n create mode 100755 t/t5309-pack-delta-cycles.sh\n\ndiff --git a/t/lib-pack.sh b/t/lib-pack.sh\nindex fecd5a0..7e8685b 100644\n--- a/t/lib-pack.sh\n+++ b/t/lib-pack.sh\n@@ -55,6 +55,28 @@ pack_obj () {\n \t\t\tprintf '\\062\\170\\234\\143\\267\\3\\0\\0\\116\\0\\106'\n \t\t\treturn\n \t\t\t;;\n+\t\t01d7713666f4de822776c7622c10f1b07de280dc)\n+\t\t\tprintf '\\165\\1\\327\\161\\66\\146\\364\\336\\202\\47\\166' &&\n+\t\t\tprintf '\\307\\142\\54\\20\\361\\260\\175\\342\\200\\334\\170' &&\n+\t\t\tprintf '\\234\\143\\142\\142\\142\\267\\003\\0\\0\\151\\0\\114'\n+\t\t\treturn\n+\t\t\t;;\n+\t\tesac\n+\t\t;;\n+\n+\t# blob containing \"\\7\\0\"\n+\t01d7713666f4de822776c7622c10f1b07de280dc)\n+\t\tcase \"$2\" in\n+\t\t'')\n+\t\t\tprintf '\\062\\170\\234\\143\\147\\0\\0\\0\\20\\0\\10'\n+\t\t\treturn\n+\t\t\t;;\n+\t\te68fe8129b546b101aee9510c5328e7f21ca1d18)\n+\t\t\tprintf '\\165\\346\\217\\350\\22\\233\\124\\153\\20\\32\\356' &&\n+\t\t\tprintf '\\225\\20\\305\\62\\216\\177\\41\\312\\35\\30\\170\\234' &&\n+\t\t\tprintf '\\143\\142\\142\\142\\147\\0\\0\\0\\53\\0\\16'\n+\t\t\treturn\n+\t\t\t;;\n \t\tesac\n \t\t;;\n \tesac\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nnew file mode 100755\nindex 0000000..1640bf7\n--- /dev/null\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -0,0 +1,59 @@\n+#!/bin/sh\n+\n+test_description='test index-pack handling of delta cycles in packfiles'\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-pack.sh\n+\n+# Two similar-ish objects that we have computed deltas between.\n+A=01d7713666f4de822776c7622c10f1b07de280dc\n+B=e68fe8129b546b101aee9510c5328e7f21ca1d18\n+\n+# double-check our hand-constucted packs\n+test_expect_success 'index-pack works with a single delta (A->B)' '\n+\tclear_packs &&\n+\t{\n+\t\tpack_header 2 &&\n+\t\tpack_obj $A $B &&\n+\t\tpack_obj $B\n+\t} >ab.pack &&\n+\tpack_trailer ab.pack &&\n+\tgit index-pack --stdin A)' '\n+\tclear_packs &&\n+\t{\n+\t\tpack_header 2 &&\n+\t\tpack_obj $A &&\n+\t\tpack_obj $B $A\n+\t} >ba.pack &&\n+\tpack_trailer ba.pack &&\n+\tgit index-pack --stdin missing.pack &&\n+\tpack_trailer missing.pack &&\n+\ttest_must_fail git index-pack --fix-thin --stdin cycle.pack &&\n+\tpack_trailer cycle.pack &&\n+\ttest_must_fail git index-pack --fix-thin --stdin \nAcked-by: Nicolas Pitre \n---\n t/t5309-pack-delta-cycles.sh | 18 ++++++++++++++++++\n 1 file changed, 18 insertions(+)\n\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 1640bf7..3e7861b 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -56,4 +56,22 @@ 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 \nAcked-by: Nicolas Pitre \n---\n builtin/index-pack.c | 4 ++++\n pack-write.c | 24 ++++++++++++++++++++++++\n pack.h | 2 ++\n t/t5308-pack-detect-duplicates.sh | 8 ++++++++\n 4 files changed, 38 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 79dfe47..72e19a0 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1364,6 +1364,10 @@ static int git_index_pack_config(const char *k, const char *v, void *cb)\n #endif\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.indexduplicates\")) {\n+\t\topts->allow_duplicates = git_config_bool(k, v);\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v, cb);\n }\n \ndiff --git a/pack-write.c b/pack-write.c\nindex ca9e63b..da946a7 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -7,6 +7,7 @@ void reset_pack_idx_option(struct pack_idx_option *opts)\n \tmemset(opts, 0, sizeof(*opts));\n \topts->version = 2;\n \topts->off32_limit = 0x7fffffff;\n+\topts->allow_duplicates = 1;\n }\n \n static int sha1_compare(const void *_a, const void *_b)\n@@ -37,6 +38,19 @@ static int need_large_offset(off_t offset, const struct pack_idx_option *opts)\n \t\t\t sizeof(ofsval), cmp_uint32);\n }\n \n+static void *find_duplicate(void *vbase, size_t n, size_t size,\n+\t\t\t int (*cmp)(const void *, const void *))\n+{\n+\tunsigned char *base = vbase;\n+\twhile (n > 1) {\n+\t\tif (!cmp(base, base + size))\n+\t\t\treturn base;\n+\t\tbase += size;\n+\t\tn--;\n+\t}\n+\treturn NULL;\n+}\n+\n /*\n * On entry *sha1 contains the pack content SHA1 hash, on exit it is\n * the SHA1 hash of sorted object names. The objects array passed in\n@@ -68,6 +82,16 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \telse\n \t\tsorted_by_sha = list = last = NULL;\n \n+\tif (!opts->allow_duplicates) {\n+\t\tstruct pack_idx_entry **dup;\n+\n+\t\tdup = find_duplicate(sorted_by_sha, nr_objects,\n+\t\t\t\t sizeof(*sorted_by_sha), sha1_compare);\n+\t\tif (dup)\n+\t\t\tdie(\"pack has duplicate entries for %s\",\n+\t\t\t sha1_to_hex((*dup)->sha1));\n+\t}\n+\n \tif (opts->flags & WRITE_IDX_VERIFY) {\n \t\tassert(index_name);\n \t\tf = sha1fd_check(index_name);\ndiff --git a/pack.h b/pack.h\nindex aa6ee7d..45217b6 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -44,6 +44,8 @@ struct pack_idx_option {\n \tuint32_t version;\n \tuint32_t off32_limit;\n \n+\tint allow_duplicates;\n+\n \t/*\n \t * List of offsets that would fit within off32_limit but\n \t * need to be written out as 64-bit entity for byte-for-byte\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 04fe242..97ce2e0 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -70,4 +70,12 @@ test_expect_success 'lookup in duplicated pack (GIT_USE_LOOKUP)' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'index-pack can reject packs with duplicates' '\n+\tclear_packs &&\n+\tcreate_pack dups.pack 2 &&\n+\ttest_must_fail \\\n+\t\tgit -c pack.indexDuplicates=0 index-pack --stdin \nAcked-by: Nicolas Pitre \n---\n pack-write.c | 1 -\n t/t5308-pack-detect-duplicates.sh | 9 ++++-----\n 2 files changed, 4 insertions(+), 6 deletions(-)\n\ndiff --git a/pack-write.c b/pack-write.c\nindex da946a7..1e3c459 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -7,7 +7,6 @@ void reset_pack_idx_option(struct pack_idx_option *opts)\n \tmemset(opts, 0, sizeof(*opts));\n \topts->version = 2;\n \topts->off32_limit = 0x7fffffff;\n-\topts->allow_duplicates = 1;\n }\n \n static int sha1_compare(const void *_a, const void *_b)\ndiff --git a/t/t5308-pack-detect-duplicates.sh b/t/t5308-pack-detect-duplicates.sh\nindex 97ce2e0..e0ba5e1 100755\n--- a/t/t5308-pack-detect-duplicates.sh\n+++ b/t/t5308-pack-detect-duplicates.sh\n@@ -37,10 +37,10 @@ test_expect_success 'index-pack will allow duplicate objects by default' '\n \tgit index-pack --stdin