{"thread":{"id":"38644","subject":"[BUG] diffcore-rename with duplicate tree entries can segfault","startedAt":"2015-02-24T21:43:11Z","lastAt":"2015-02-27T21:48:11Z","messageCount":12,"participants":["Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"256596","messageId":"20150224214311.GA8622@peff.net","threadId":"38644","inReplyTo":null,"subject":"[BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-24T21:43:11Z","receivedAt":"2015-02-24T21:43:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I ran across a real-world case where git segfaults on some trees that\nhave duplicate entries. Those trees are obviously broken, and I'm fine\nwith us producing whatever output we like on them. But probably we\nshouldn't segfault.\n\nBasically what happens is that the rename_dst array maps paths to\ndiff_filepairs. When we process the results of the rename, if we have\nduplicates we may hit that same pathname multiple times, and pull out\nthe same diff_filepair. So we end up with a diff_queue that has the same\nfilepair mentioned multiple times. When it comes time to flush and free\nthat queue, we do a double (or triple) free of the filepair and its\ncontents, which corrupts the heap.\n\nI managed to reduce it to a simplified test case:\n\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nnew file mode 100755\nindex 0000000..9e03490\n--- /dev/null\n+++ b/t/t4058-diff-duplicates.sh\n@@ -0,0 +1,85 @@\n+#!/bin/sh\n+\n+test_description='test tree diff when trees have duplicate entries'\n+. ./test-lib.sh\n+\n+# make_tree_entry <mode> <mode> <sha1>\n+#\n+# We have to rely on perl here because not all printfs understand\n+# hex escapes (only octal), and xxd is not portable.\n+make_tree_entry () {\n+\tprintf '%s %s\\0' \"$1\" \"$2\" &&\n+\tperl -e 'print chr(hex($_)) for ($ARGV[0] =~ /../g)' \"$3\"\n+}\n+\n+# Like git-mktree, but without all of the pesky sanity checking.\n+# Arguments come in groups of three, each group specifying a single\n+# tree entry (see make_tree_entry above).\n+make_tree () {\n+\twhile test $# -gt 2; do\n+\t\tmake_tree_entry \"$1\" \"$2\" \"$3\"\n+\t\tshift; shift; shift\n+\tdone |\n+\tgit hash-object -w -t tree --stdin\n+}\n+\n+# this is kind of a convoluted setup, but matches\n+# a real-world case. Each tree contains four entries\n+# for the given path, one with one sha1, and three with\n+# the other. The first tree has them split across\n+# two subtrees (which are themselves duplicate entries in\n+# the root tree), and the second has them all in a single subtree.\n+test_expect_success 'create trees with duplicate entries' '\n+\tblob_one=$(echo one | git hash-object -w --stdin) &&\n+\tblob_two=$(echo two | git hash-object -w --stdin) &&\n+\tinner_one_a=$(make_tree \\\n+\t\t100644 inner $blob_one\n+\t) &&\n+\tinner_one_b=$(make_tree \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two\n+\t) &&\n+\touter_one=$(make_tree \\\n+\t\t040000 outer $inner_one_a \\\n+\t\t040000 outer $inner_one_b\n+\t) &&\n+\tinner_two=$(make_tree \\\n+\t\t100644 inner $blob_one \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two\n+\t) &&\n+\touter_two=$(make_tree \\\n+\t\t040000 outer $inner_two\n+\t) &&\n+\tgit tag one $outer_one &&\n+\tgit tag two $outer_two\n+'\n+\n+test_expect_success 'diff-tree between trees' '\n+\t{\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\"\n+\t} >expect &&\n+\tgit diff-tree -r --no-abbrev one two >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'diff-tree with renames' '\n+\t{\n+\t\tprintf \":100644 100644 $blob_two $blob_two M\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\"\n+\t} >expect &&\n+\tgit diff-tree -M -r --no-abbrev one two >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n\nThe diff-tree outputs are up for debate. Possibly we should not even be\nchecking the output at all, and just making sure we don't segfault. The\nfirst one is produced with stock git, and kind-of makes sense (we don't\nlink up the obviously matching paths in the tree diff because they come\nfrom two different subtrees). Of course with \"-p\" it cannot be applied,\nbut it is at least somewhat informative to the user.\n\nThe second one is what is produced by the patch below. It also kind of\nmakes sense (we link up one pair, but the others are left out of the\nrename detection). Though I would have expected the `M` in the first\nline to be an `R100`.\n\nMy idea for a fix was to make sure we didn't pull the same entry out of\nlocate_rename_dst multiple times:\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 4e132f1..7030502 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -12,6 +12,7 @@\n static struct diff_rename_dst {\n \tstruct diff_filespec *two;\n \tstruct diff_filepair *pair;\n+\tint used;\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n \n@@ -27,7 +28,7 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n \t\tint cmp = strcmp(two->path, dst->two->path);\n \t\tif (!cmp)\n-\t\t\treturn dst;\n+\t\t\treturn dst->used ? NULL : dst;\n \t\tif (cmp < 0) {\n \t\t\tlast = next;\n \t\t\tcontinue;\n@@ -46,6 +47,7 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \trename_dst[first].two = alloc_filespec(two->path);\n \tfill_filespec(rename_dst[first].two, two->sha1, two->sha1_valid, two->mode);\n \trename_dst[first].pair = NULL;\n+\trename_dst[first].used = 0;\n \treturn &(rename_dst[first]);\n }\n \n@@ -587,6 +589,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tif (dst && dst->pair) {\n \t\t\t\tdiff_q(&outq, dst->pair);\n \t\t\t\tpair_to_free = p;\n+\t\t\t\tdst->used = 1;\n \t\t\t}\n \t\t\telse\n \t\t\t\t/* no matching rename/copy source, so\n\n\nThat does fix this problem, and it doesn't break any other tests. But\nfrankly, I don't know what I'm doing and this feels like a giant hack.\nThe \"M\" output above is confusing to me, and I have no faith that there\nisn't another way this problem can come up (e.g., with duplicate\nsources).\n\nGiven that this is tangentially related to the \"-B -M\" stuff you've been\nlooking at (and it's your code in the first place :) ), I thought you\nmight have some insight.\n\n-Peff\n"},{"id":"256604","messageId":"xmqqh9uborrx.fsf@gitster.dls.corp.google.com","threadId":"38644","inReplyTo":"20150224214311.GA8622@peff.net","subject":"Re: [BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-24T22:42:42Z","receivedAt":"2015-02-24T22:42:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> I ran across a real-world case where git segfaults on some trees that\n> have duplicate entries. Those trees are obviously broken, and I'm fine\n> with us producing whatever output we like on them. But probably we\n> shouldn't segfault.\n\nThanks.\n\n> ...\n> That does fix this problem, and it doesn't break any other tests. But\n> frankly, I don't know what I'm doing and this feels like a giant hack.\n>\n> Given that this is tangentially related to the \"-B -M\" stuff you've been\n> looking at (and it's your code in the first place :) ), I thought you\n> might have some insight.\n\nIndeed.\n\nHonestly, I'd rather see us diagnose duplicate filepairs as an error\nand drop them on the floor upon entry to the diffcore_std(), even\nbefore we go into the rename codepath.\n"},{"id":"256605","messageId":"20150224224918.GA24749@peff.net","threadId":"38644","inReplyTo":"xmqqh9uborrx.fsf@gitster.dls.corp.google.com","subject":"Re: [BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-24T22:49:18Z","receivedAt":"2015-02-24T22:49:18Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 24, 2015 at 02:42:42PM -0800, Junio C Hamano wrote:\n\n> > That does fix this problem, and it doesn't break any other tests. But\n> > frankly, I don't know what I'm doing and this feels like a giant hack.\n> >\n> > Given that this is tangentially related to the \"-B -M\" stuff you've been\n> > looking at (and it's your code in the first place :) ), I thought you\n> > might have some insight.\n> \n> Indeed.\n> \n> Honestly, I'd rather see us diagnose duplicate filepairs as an error\n> and drop them on the floor upon entry to the diffcore_std(), even\n> before we go into the rename codepath.\n\nYeah, I had a similar thought. Just saying \"your diff is broken, we\ncan't do rename detection\" is totally reasonable to me.\n\nMy main concern with that approach is that we would waste time finding\nthe duplicate paths, for something that comes up only rarely. At the\ntime of locate_rename_dst, we've already created a mapping, and it's\nvery easy to detect the duplicates. But before that, we have only the\nlinear list of queued items.\n\nIn theory they're sorted and we could do an O(n) pass to find\nduplicates. But I'm not sure if the sorting holds in the face of other\nbreakages (like unsorted trees; they also shouldn't happen, but the\nwhole point here is to gracefully handle things that shouldn't).\n\nI dunno. Maybe we could do an O(n) pass to check sort order and\nuniqueness. If either fails (which should be rare), then we sort and\nre-check uniqueness.\n\nI'm assuming there _is_ a sane sort order. We have two halves of a\nfilepair, but I think before any of the rename or break detection kicks\nin, each pair should either:\n\n  1. Have a name in pair->one, and an invalid filespec in pair->two\n     (i.e., a deletion).\n\n  2. The opposite (name in pair->two, /dev/null in pair->one). An\n     addition.\n\n  3. The same name in pair->one and pair->two.\n\n-Peff\n"},{"id":"256606","messageId":"xmqqd24yq517.fsf@gitster.dls.corp.google.com","threadId":"38644","inReplyTo":"20150224224918.GA24749@peff.net","subject":"Re: [BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-24T23:11:00Z","receivedAt":"2015-02-24T23:11:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> I'm assuming there _is_ a sane sort order. We have two halves of a\n> filepair, but I think before any of the rename or break detection kicks\n> in, each pair should either:\n>\n>   1. Have a name in pair->one, and an invalid filespec in pair->two\n>      (i.e., a deletion).\n>\n>   2. The opposite (name in pair->two, /dev/null in pair->one). An\n>      addition.\n>\n>   3. The same name in pair->one and pair->two.\n\nI think creation and deletion are expressed with mode=0 and not with\n/dev/null.\n"},{"id":"256608","messageId":"20150224234737.GA8370@peff.net","threadId":"38644","inReplyTo":"xmqqd24yq517.fsf@gitster.dls.corp.google.com","subject":"Re: [BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-24T23:47:37Z","receivedAt":"2015-02-24T23:47:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 24, 2015 at 03:11:00PM -0800, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > I'm assuming there _is_ a sane sort order. We have two halves of a\n> > filepair, but I think before any of the rename or break detection kicks\n> > in, each pair should either:\n> >\n> >   1. Have a name in pair->one, and an invalid filespec in pair->two\n> >      (i.e., a deletion).\n> >\n> >   2. The opposite (name in pair->two, /dev/null in pair->one). An\n> >      addition.\n> >\n> >   3. The same name in pair->one and pair->two.\n> \n> I think creation and deletion are expressed with mode=0 and not with\n> /dev/null.\n\nYeah, or better spelled DIFF_FILE_VALID().\n\nSo here's a first stab at doing this. There are a couple of issues:\n\n  1. It makes the check part of diffcore_std. My thinking was that we\n     can actually correct some problems (like sort order) for all cases,\n     and the duplicate check may want to disable more than renames\n     (e.g., it could turn off any fancy features like break detection).\n\n     It is possible to run diffcore_rename by itself, which would miss\n     this protection. We don't seem to do that anywhere, though (even\n     for try_to_follow_renames, we set up a new diff_options struct and\n     just call diffcore_std).\n\n  2. It disables rename detection by tweaking the diff_options struct.\n     This is OK for a single diff, but I suspect is wrong for \"git log\",\n     as we use the same diff_options for each (so one bogus diff would\n     turn off renames for the rest of the commits). We can probably get\n     around this by returning a \"bogus, don't do renames\" flag from\n     diffcore_sanity and respecting it in diffcore_std.\n\n  3. The sort order check is wrong. :-/ It needs to take into account\n     git's magic \"if it's a tree, pretend it has '/' after it\" rule.\n     That's not too hard for a single tree (fsck.c:verify_ordered does\n     it). But for filepairs, I'm not sure what to do. Most cases\n     have a single mode/name pair. But what about a D/F typechange? If\n     \"foo\" becomes \"foo/\", which do I use to sort?\n\n     I have a feeling the order in which we queue the pairs may even\n     depend on the direction of the typechange. Or maybe it always\n     matches the p->one version. I'll have to think on it.\n\nI'm out of time to work on this tonight, but I'll try to get back to it\ntomorrow. Any wisdom is appreciated.\n\n---\ndiff --git a/Makefile b/Makefile\nindex 44f1dd1..838a21c 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -690,6 +690,7 @@ LIB_OBJS += diffcore-delta.o\n LIB_OBJS += diffcore-order.o\n LIB_OBJS += diffcore-pickaxe.o\n LIB_OBJS += diffcore-rename.o\n+LIB_OBJS += diffcore-sanity.o\n LIB_OBJS += diff-delta.o\n LIB_OBJS += diff-lib.o\n LIB_OBJS += diff-no-index.o\ndiff --git a/diff.c b/diff.c\nindex d1bd534..5f7c43a 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4768,6 +4768,7 @@ void diffcore_std(struct diff_options *options)\n \t/* NOTE please keep the following in sync with diff_tree_combined() */\n \tif (options->skip_stat_unmatch)\n \t\tdiffcore_skip_stat_unmatch(options);\n+\tdiffcore_sanity(options);\n \tif (!options->found_follow) {\n \t\t/* See try_to_follow_renames() in tree-diff.c */\n \t\tif (options->break_opt != -1)\ndiff --git a/diffcore-sanity.c b/diffcore-sanity.c\nnew file mode 100644\nindex 0000000..ab770c9\n--- /dev/null\n+++ b/diffcore-sanity.c\n@@ -0,0 +1,84 @@\n+#include \"cache.h\"\n+#include \"diff.h\"\n+#include \"diffcore.h\"\n+\n+enum sanity_check {\n+\tSANITY_OK,\n+\tSANITY_UNSORTED,\n+\tSANITY_DUPLICATES\n+};\n+\n+static const char *filepair_name(const struct diff_filepair *p)\n+{\n+\t/*\n+\t * There's no point in checking that one or the other is valid;\n+\t * that invariant is set by earlier code, not by the trees\n+\t * themselves.\n+\t */\n+\tif (!DIFF_FILE_VALID(p->one))\n+\t\treturn p->two->path;\n+\tif (!DIFF_FILE_VALID(p->two))\n+\t\treturn p->one->path;\n+\t/*\n+\t * one->path should be the same as two->path here;\n+\t * we could check, but again, this invariant comes\n+\t * from our diff code, not the tree\n+\t */\n+\treturn p->one->path;\n+}\n+\n+static enum sanity_check check_sanity(struct diff_queue_struct *q)\n+{\n+\tint i;\n+\tfor (i = 1; i < q->nr; i++) {\n+\t\tint cmp = strcmp(filepair_name(q->queue[i - 1]),\n+\t\t\t\t filepair_name(q->queue[i]));\n+\t\tif (cmp == 0)\n+\t\t\treturn SANITY_DUPLICATES;\n+\t\tif (cmp > 0)\n+\t\t\treturn SANITY_UNSORTED;\n+\t}\n+\treturn SANITY_OK;\n+}\n+\n+int cmp_filepair(const void *va, const void *vb)\n+{\n+\tconst struct diff_filepair * const *a = va, * const *b = vb;\n+\treturn strcmp(filepair_name(*a), filepair_name(*b));\n+}\n+\n+static void sort_diff_queue(struct diff_queue_struct *q)\n+{\n+\tqsort(q->queue, q->nr, sizeof(*q->queue), cmp_filepair);\n+}\n+\n+void diffcore_sanity(struct diff_options *options)\n+{\n+\tenum sanity_check check = check_sanity(&diff_queued_diff);\n+\n+\tif (check == SANITY_OK)\n+\t\treturn;\n+\n+\t/*\n+\t * We can fix sorting, but once fixed, we have to check\n+\t * again to make sure we don't have duplicates, since\n+\t * that relies on sort order.\n+\t */\n+\tif (check == SANITY_UNSORTED) {\n+\t\twarning(\"diff entries are not sorted; your trees may be broken\");\n+\t\tsort_diff_queue(&diff_queued_diff);\n+\t\tcheck = check_sanity(&diff_queued_diff);\n+\t\tif (check == SANITY_OK)\n+\t\t\treturn;\n+\t}\n+\n+\t/*\n+\t * If we get here, we have duplicates. The rename code isn't ready\n+\t * to handle this, so we have to turn it off.\n+\t */\n+\tif (options->detect_rename) {\n+\t\twarning(\"duplicate tree entries found; disabling rename detection\");\n+\t\toptions->detect_rename = 0;\n+\t}\n+\t/* XXX break detection, too? */\n+}\ndiff --git a/diffcore.h b/diffcore.h\nindex 33ea2de..fa359ce 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -107,6 +107,7 @@ extern struct diff_filepair *diff_queue(struct diff_queue_struct *,\n \t\t\t\t\tstruct diff_filespec *);\n extern void diff_q(struct diff_queue_struct *, struct diff_filepair *);\n \n+extern void diffcore_sanity(struct diff_options *);\n extern void diffcore_break(int);\n extern void diffcore_rename(struct diff_options *);\n extern void diffcore_merge_broken(void);\n"},{"id":"256613","messageId":"xmqq8ufmpouz.fsf@gitster.dls.corp.google.com","threadId":"38644","inReplyTo":"20150224234737.GA8370@peff.net","subject":"Re: [BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-25T05:00:20Z","receivedAt":"2015-02-25T05:00:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>   3. The sort order check is wrong. :-/ It needs to take into account\n>      git's magic \"if it's a tree, pretend it has '/' after it\" rule.\n>      That's not too hard for a single tree (fsck.c:verify_ordered does\n>      it). But for filepairs, I'm not sure what to do. Most cases\n>      have a single mode/name pair. But what about a D/F typechange? If\n>      \"foo\" becomes \"foo/\", which do I use to sort?\n\nI think diff-index populates the diff queue in a wrong order and\nthen calls diffcore_fix_diff_index() to fix it up.\n\nI am a bit worried about the effect this stricter input check might\nhave to \"diff --no-index\" codepath, though.\n"},{"id":"256662","messageId":"20150225214032.GA32295@peff.net","threadId":"38644","inReplyTo":"xmqq8ufmpouz.fsf@gitster.dls.corp.google.com","subject":"Re: [BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-25T21:40:32Z","receivedAt":"2015-02-25T21:40:32Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 24, 2015 at 09:00:20PM -0800, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> >   3. The sort order check is wrong. :-/ It needs to take into account\n> >      git's magic \"if it's a tree, pretend it has '/' after it\" rule.\n> >      That's not too hard for a single tree (fsck.c:verify_ordered does\n> >      it). But for filepairs, I'm not sure what to do. Most cases\n> >      have a single mode/name pair. But what about a D/F typechange? If\n> >      \"foo\" becomes \"foo/\", which do I use to sort?\n> \n> I think diff-index populates the diff queue in a wrong order and\n> then calls diffcore_fix_diff_index() to fix it up.\n> \n> I am a bit worried about the effect this stricter input check might\n> have to \"diff --no-index\" codepath, though.\n\nInteresting, I didn't even know about diffcore_fix_diff_index.\n\nLet's forget about sorting for a moment. Unsorted trees will produce odd\nresults, certainly, but the order of your diff is perhaps the least of\nthe problems. The only reason we care about it here is to do a cheap\nuniq() operation.\n\nBut we can also do that with a hash table, or an auxiliary sorted array.\nAnd sure enough, that's exactly what the rename_dst array is. When we\nare inserting into it, we can easily detect duplicates there, and just\nabort the rename operation. Like:\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 4e132f1..e26dd62 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -27,7 +27,7 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n \t\tint cmp = strcmp(two->path, dst->two->path);\n \t\tif (!cmp)\n-\t\t\treturn dst;\n+\t\t\treturn insert_ok ? NULL : dst;\n \t\tif (cmp < 0) {\n \t\t\tlast = next;\n \t\t\tcontinue;\n@@ -450,8 +450,10 @@ void diffcore_rename(struct diff_options *options)\n \t\t\telse if (!DIFF_OPT_TST(options, RENAME_EMPTY) &&\n \t\t\t\t is_empty_blob_sha1(p->two->sha1))\n \t\t\t\tcontinue;\n-\t\t\telse\n-\t\t\t\tlocate_rename_dst(p->two, 1);\n+\t\t\telse {\n+\t\t\t\tif (!locate_rename_dst(p->two, 1))\n+\t\t\t\t\tgoto cleanup;\n+\t\t\t}\n \t\t}\n \t\telse if (!DIFF_OPT_TST(options, RENAME_EMPTY) &&\n \t\t\t is_empty_blob_sha1(p->one->sha1))\n\nwhich I think is a pretty simple and sane fix. I do notice that\nrename_dst and rename_src are essentially hash tables. They predate\nhashmap.c by quite a bit, but it might be worth moving them. It would\nsimplify the code, and I suspect perform better (they progressively\ninsert into a sorted list; in the worst case that means O(n^2)\nmemmove's, though if the input is sorted we get best-case behavior).\n\nSo to go forward, I'm happy to prepare a patch, but I'd like to know:\n\n  1. Does something like the above look reasonable to you (I'd probably\n     refactor it to avoid the bizarre return value semantics from\n     locate_rename_dst, though)?\n\n  2. If so, do you want something minimal like what's above, or do you\n     mind if I build it on top of a hashmap conversion? I suspect the\n     logic may also end up more clear with the hashmap (since inserting\n     versus lookup will be more distinct in the callers).\n\n-Peff\n"},{"id":"256663","messageId":"xmqq1tldoe35.fsf@gitster.dls.corp.google.com","threadId":"38644","inReplyTo":"20150225214032.GA32295@peff.net","subject":"Re: [BUG] diffcore-rename with duplicate tree entries can segfault","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-25T21:50:38Z","receivedAt":"2015-02-25T21:50:38Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> But we can also do that with a hash table, or an auxiliary sorted array.\n> And sure enough, that's exactly what the rename_dst array is.\n> ...\n> which I think is a pretty simple and sane fix.\n\nYeah, good observation.\n\n> So to go forward, I'm happy to prepare a patch, but I'd like to know:\n>\n>   1. Does something like the above look reasonable to you (I'd probably\n>      refactor it to avoid the bizarre return value semantics from\n>      locate_rename_dst, though)?\n>\n>   2. If so, do you want something minimal like what's above, or do you\n>      mind if I build it on top of a hashmap conversion? I suspect the\n>      logic may also end up more clear with the hashmap (since inserting\n>      versus lookup will be more distinct in the callers).\n\nNo, I don't mind.  The diff-b-m topic seems to need a lot deeper\nrethink than I originally anticipated anyway, and it can wait for a\nclean-up to use hashmap to stabilize.\n\nThanks.\n"},{"id":"256732","messageId":"20150227013847.GA2983@peff.net","threadId":"38644","inReplyTo":"xmqq1tldoe35.fsf@gitster.dls.corp.google.com","subject":"[PATCH 0/2] diffcore-rename with duplicate tree entries can segfault","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-27T01:38:47Z","receivedAt":"2015-02-27T01:38:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Feb 25, 2015 at 01:50:38PM -0800, Junio C Hamano wrote:\n\n> > So to go forward, I'm happy to prepare a patch, but I'd like to know:\n> >\n> >   1. Does something like the above look reasonable to you (I'd probably\n> >      refactor it to avoid the bizarre return value semantics from\n> >      locate_rename_dst, though)?\n> >\n> >   2. If so, do you want something minimal like what's above, or do you\n> >      mind if I build it on top of a hashmap conversion? I suspect the\n> >      logic may also end up more clear with the hashmap (since inserting\n> >      versus lookup will be more distinct in the callers).\n> \n> No, I don't mind.  The diff-b-m topic seems to need a lot deeper\n> rethink than I originally anticipated anyway, and it can wait for a\n> clean-up to use hashmap to stabilize.\n\nI tried switching to a hashmap, but the diff_score code actually wants\nto index into the array using an int. In a hashmap, we'd use a pointer\ninstead, but that increases the size of \"struct diff_score\", which is\nsomething that we have to allocate a lot of (src * dst, I think).\n\nSo I punted on that and just cleaned up the locate_rename_dst interface\na bit.  Here's the result.\n\n  [1/2]: diffcore-rename: split locate_rename_dst into two functions\n  [2/2]: diffcore-rename: avoid processing duplicate destinations\n\n-Peff\n"},{"id":"256733","messageId":"20150227013948.GA3210@peff.net","threadId":"38644","inReplyTo":"20150227013847.GA2983@peff.net","subject":"[PATCH 1/2] diffcore-rename: split locate_rename_dst into two functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-27T01:39:48Z","receivedAt":"2015-02-27T01:39:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This function manages the mapping of destination pathnames\nto filepairs, and it handles both insertion and lookup. This\nmakes the return value a bit confusing, as we return a newly\ncreated entry (even though no caller cares), and have no\nroom to indicate to the caller that an entry already\nexisted.\n\nInstead, let's break this up into two distinct functions,\nboth backed by a common binary search. The binary search\nwill use our normal \"return the index if we found something,\nor negative index minus one to show where it would have\ngone\" semantics.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n diffcore-rename.c | 38 ++++++++++++++++++++++++++------------\n 1 file changed, 26 insertions(+), 12 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 4e132f1..4250cc0 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -15,8 +15,7 @@ static struct diff_rename_dst {\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n \n-static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n-\t\t\t\t\t\t int insert_ok)\n+static int find_rename_dst(struct diff_filespec *two)\n {\n \tint first, last;\n \n@@ -27,16 +26,33 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n \t\tint cmp = strcmp(two->path, dst->two->path);\n \t\tif (!cmp)\n-\t\t\treturn dst;\n+\t\t\treturn next;\n \t\tif (cmp < 0) {\n \t\t\tlast = next;\n \t\t\tcontinue;\n \t\t}\n \t\tfirst = next+1;\n \t}\n-\t/* not found */\n-\tif (!insert_ok)\n-\t\treturn NULL;\n+\treturn -first - 1;\n+}\n+\n+static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)\n+{\n+\tint ofs = find_rename_dst(two);\n+\treturn ofs < 0 ? NULL : &rename_dst[ofs];\n+}\n+\n+/*\n+ * Returns 0 on success, -1 if we found a duplicate.\n+ */\n+static int add_rename_dst(struct diff_filespec *two)\n+{\n+\tint first = find_rename_dst(two);\n+\n+\tif (first >= 0)\n+\t\treturn -1;\n+\tfirst = -first - 1;\n+\n \t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n \trename_dst_nr++;\n@@ -46,7 +62,7 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \trename_dst[first].two = alloc_filespec(two->path);\n \tfill_filespec(rename_dst[first].two, two->sha1, two->sha1_valid, two->mode);\n \trename_dst[first].pair = NULL;\n-\treturn &(rename_dst[first]);\n+\treturn 0;\n }\n \n /* Table of rename/copy src files */\n@@ -451,7 +467,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t is_empty_blob_sha1(p->two->sha1))\n \t\t\t\tcontinue;\n \t\t\telse\n-\t\t\t\tlocate_rename_dst(p->two, 1);\n+\t\t\t\tadd_rename_dst(p->two);\n \t\t}\n \t\telse if (!DIFF_OPT_TST(options, RENAME_EMPTY) &&\n \t\t\t is_empty_blob_sha1(p->one->sha1))\n@@ -582,8 +598,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t * We would output this create record if it has\n \t\t\t * not been turned into a rename/copy already.\n \t\t\t */\n-\t\t\tstruct diff_rename_dst *dst =\n-\t\t\t\tlocate_rename_dst(p->two, 0);\n+\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two);\n \t\t\tif (dst && dst->pair) {\n \t\t\t\tdiff_q(&outq, dst->pair);\n \t\t\t\tpair_to_free = p;\n@@ -613,8 +628,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t */\n \t\t\tif (DIFF_PAIR_BROKEN(p)) {\n \t\t\t\t/* broken delete */\n-\t\t\t\tstruct diff_rename_dst *dst =\n-\t\t\t\t\tlocate_rename_dst(p->one, 0);\n+\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->one);\n \t\t\t\tif (dst && dst->pair)\n \t\t\t\t\t/* counterpart is now rename/copy */\n \t\t\t\t\tpair_to_free = p;\n-- \n2.3.0.449.g1690e78\n"},{"id":"256734","messageId":"20150227014227.GB3210@peff.net","threadId":"38644","inReplyTo":"20150227013847.GA2983@peff.net","subject":"[PATCH 2/2] diffcore-rename: avoid processing duplicate destinations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-27T01:42:27Z","receivedAt":"2015-02-27T01:42:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The rename code cannot handle an input where we have\nduplicate destinations (i.e., more than one diff_filepair in\nthe queue with the same string in its pair->two->path). We\nend up allocating only one slot in the rename_dst mapping.\nIf we fill in the diff_filepair for that slot, when we\nre-queue the results, we may queue that filepair multiple\ntimes. When the diff is finally flushed, the filepair is\nprocessed and free()d multiple times, leading to heap\ncorruption.\n\nThis situation should only happen when a tree diff sees\nduplicates in one of the trees (see the added test for a\ndetailed example). Rather than handle it, the sanest thing\nis just to turn off rename detection altogether for the\ndiff.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nLike I mentioned before, I'm OK with not checking the actual diff output\nin the test. It's not like it was planned, and is just what diff_tree()\nhappens to produce. It does make sense, though. We descend into the\nfirst \"outer/\" of the \"a/\" side along with the sole \"outer/\" of the\n\"b/\" side. We see that the entries from \"b/\" are all added. Then we come\nback out, and see that \"a/\" has another \"outer/\", but that \"b/\" does\nnot. So all of those entries look like they were deleted.\n\n diffcore-rename.c          |  8 +++--\n t/t4058-diff-duplicates.sh | 79 ++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 85 insertions(+), 2 deletions(-)\n create mode 100755 t/t4058-diff-duplicates.sh\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 4250cc0..af1fe08 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -466,8 +466,12 @@ void diffcore_rename(struct diff_options *options)\n \t\t\telse if (!DIFF_OPT_TST(options, RENAME_EMPTY) &&\n \t\t\t\t is_empty_blob_sha1(p->two->sha1))\n \t\t\t\tcontinue;\n-\t\t\telse\n-\t\t\t\tadd_rename_dst(p->two);\n+\t\t\telse if (add_rename_dst(p->two) < 0) {\n+\t\t\t\twarning(\"skipping rename detection, detected\"\n+\t\t\t\t\t\" duplicate destination '%s'\",\n+\t\t\t\t\tp->two->path);\n+\t\t\t\tgoto cleanup;\n+\t\t\t}\n \t\t}\n \t\telse if (!DIFF_OPT_TST(options, RENAME_EMPTY) &&\n \t\t\t is_empty_blob_sha1(p->one->sha1))\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nnew file mode 100755\nindex 0000000..0a23242\n--- /dev/null\n+++ b/t/t4058-diff-duplicates.sh\n@@ -0,0 +1,79 @@\n+#!/bin/sh\n+\n+test_description='test tree diff when trees have duplicate entries'\n+. ./test-lib.sh\n+\n+# make_tree_entry <mode> <mode> <sha1>\n+#\n+# We have to rely on perl here because not all printfs understand\n+# hex escapes (only octal), and xxd is not portable.\n+make_tree_entry () {\n+\tprintf '%s %s\\0' \"$1\" \"$2\" &&\n+\tperl -e 'print chr(hex($_)) for ($ARGV[0] =~ /../g)' \"$3\"\n+}\n+\n+# Like git-mktree, but without all of the pesky sanity checking.\n+# Arguments come in groups of three, each group specifying a single\n+# tree entry (see make_tree_entry above).\n+make_tree () {\n+\twhile test $# -gt 2; do\n+\t\tmake_tree_entry \"$1\" \"$2\" \"$3\"\n+\t\tshift; shift; shift\n+\tdone |\n+\tgit hash-object -w -t tree --stdin\n+}\n+\n+# this is kind of a convoluted setup, but matches\n+# a real-world case. Each tree contains four entries\n+# for the given path, one with one sha1, and three with\n+# the other. The first tree has them split across\n+# two subtrees (which are themselves duplicate entries in\n+# the root tree), and the second has them all in a single subtree.\n+test_expect_success 'create trees with duplicate entries' '\n+\tblob_one=$(echo one | git hash-object -w --stdin) &&\n+\tblob_two=$(echo two | git hash-object -w --stdin) &&\n+\tinner_one_a=$(make_tree \\\n+\t\t100644 inner $blob_one\n+\t) &&\n+\tinner_one_b=$(make_tree \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two\n+\t) &&\n+\touter_one=$(make_tree \\\n+\t\t040000 outer $inner_one_a \\\n+\t\t040000 outer $inner_one_b\n+\t) &&\n+\tinner_two=$(make_tree \\\n+\t\t100644 inner $blob_one \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two \\\n+\t\t100644 inner $blob_two\n+\t) &&\n+\touter_two=$(make_tree \\\n+\t\t040000 outer $inner_two\n+\t) &&\n+\tgit tag one $outer_one &&\n+\tgit tag two $outer_two\n+'\n+\n+test_expect_success 'diff-tree between trees' '\n+\t{\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $_z40 $blob_two A\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $_z40 D\\touter/inner\\n\"\n+\t} >expect &&\n+\tgit diff-tree -r --no-abbrev one two >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'diff-tree with renames' '\n+\t# same expectation as above, since we disable rename detection\n+\tgit diff-tree -M -r --no-abbrev one two >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n2.3.0.449.g1690e78\n"},{"id":"256755","messageId":"xmqqr3tbhvqc.fsf@gitster.dls.corp.google.com","threadId":"38644","inReplyTo":"20150227014227.GB3210@peff.net","subject":"Re: [PATCH 2/2] diffcore-rename: avoid processing duplicate destinations","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-27T21:48:11Z","receivedAt":"2015-02-27T21:48:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Like I mentioned before, I'm OK with not checking the actual diff output\n> in the test. It's not like it was planned, and is just what diff_tree()\n> happens to produce.  It does make sense, though....\n\nWhen the topic is on processing broken input, I do not think \"It\ndoes make sense, though.\" is a primary point, unless the result\nexpected by these tests is the only possibly sane outcome\n(otherwise, another equally-sensible output will be rejected as a\ntest failure).  So I agree that there is a possibility that we might\nregret having the diff output tested here in the future when\nsomebody further works in the area.\n\nBut let's not worry too much about it for now.\n\nThanks; the solution seems reasonable.\n"}]}