{"thread":{"id":"27939","subject":"[PATCH/WIP 0/7] was: long fast-import errors out \"failed to apply delta\"","startedAt":"2011-07-28T04:46:03Z","lastAt":"2011-07-28T08:11:47Z","messageCount":13,"participants":["Dmitry Ivankov","Jonathan Nieder"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"172200","messageId":"1311828370-30477-1-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":null,"subject":"[PATCH/WIP 0/7] was: long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:03Z","receivedAt":"2011-07-28T04:46:03Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"A very short summary. It was found [1] that fast-import sometimes can produce\nbroken packfiles (sha1 mismatch) or even wrong packfiles (data differs\nfrom what was expected). This happens mostly on not so tiny svn-to-git or\neven cvs-to-svn-to-git imports with all these copying across the tree\n(simulating tags/branches as a directories in git, for example). But I won't\nbe surprised if this can happen without these operations too.\n\nTechnically, fast-import has in-memory tree representation where it stores\nsha1's of some previous tree states (to make delta on them), but when it comes\nto producing the delta, old sha1's tree content is fetched from the in-memory\nnode and it's children (not via sha1->object lookup). And these can turn out\nto be unrelated to each other as some operations changes the children's states.\n\nThe most wanted bit for these patches is small testcases. Keeping in mind all\nthe in-memory tree state and fast-import logic is hard for me, so I wasn't able\nto create small tests (the best is [2] - 15M archive + custom git builds + fix the\nMakefile in [2] + a few minutes to reproduce).\nAnother good todo is to always avoid base sha1's mismatch (not just to avoid \ncorruption if it is detected). I think I can do this, but I won't be sure in \nthe code unless there is a bunch of good tests, this series is quite big already.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/176753\n[2] http://thread.gmane.org/gmane.comp.version-control.git/176753/focus=177901\n\nDmitry Ivankov (7):\n  fast-import: extract object preparation function\n  fast-import: be saner with temporary trees\n  fast-import: fix a data corruption in parse_ls\n  fast-import: fix data corruption in store_tree\n  fast-import: extract tree_content reading function\n  fast-import: workaround data corruption\n  fast-import: fix data corruption in load_tree\n\n fast-import.c |  169 +++++++++++++++++++++++++++++++++++++++++++++------------\n 1 files changed, 135 insertions(+), 34 deletions(-)\n\n-- \n1.7.3.4\n"},{"id":"172201","messageId":"1311828370-30477-2-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":"1311828370-30477-1-git-send-email-divanorama@gmail.com","subject":"[PATCH/WIP 1/7] fast-import: extract object preparation function","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:04Z","receivedAt":"2011-07-28T04:46:04Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"We're constructing raw objects and compute their sha1's in fast-import\njust before saving them.\n\nExtract header and sha1 computations so that we can get sha1 without\nactually saving the object.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c |   32 +++++++++++++++++++++++++-------\n 1 files changed, 25 insertions(+), 7 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 9e8d186..05cc55e 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1005,6 +1005,30 @@ static void cycle_packfile(void)\n \tstart_packfile();\n }\n \n+static void prepare_object_hash(\n+\tenum object_type type,\n+\tstruct strbuf *dat,\n+\tunsigned char *hdr_out,\n+\tunsigned long *hdrlen_out,\n+\tunsigned char *sha1_out\n+)\n+{\n+\tunsigned char hdr_[96];\n+\tunsigned char *hdr = hdr_out ? hdr_out : hdr_;\n+\tunsigned long hdrlen;\n+\tgit_SHA_CTX c;\n+\n+\thdrlen = sprintf((char *)hdr,\"%s %lu\", typename(type),\n+\t\t(unsigned long)dat->len) + 1;\n+\tgit_SHA1_Init(&c);\n+\tgit_SHA1_Update(&c, hdr, hdrlen);\n+\tgit_SHA1_Update(&c, dat->buf, dat->len);\n+\tgit_SHA1_Final(sha1_out, &c);\n+\n+\tif (hdrlen_out)\n+\t\t*hdrlen_out = hdrlen;\n+}\n+\n static int store_object(\n \tenum object_type type,\n \tstruct strbuf *dat,\n@@ -1017,15 +1041,9 @@ static int store_object(\n \tunsigned char hdr[96];\n \tunsigned char sha1[20];\n \tunsigned long hdrlen, deltalen;\n-\tgit_SHA_CTX c;\n \tgit_zstream s;\n \n-\thdrlen = sprintf((char *)hdr,\"%s %lu\", typename(type),\n-\t\t(unsigned long)dat->len) + 1;\n-\tgit_SHA1_Init(&c);\n-\tgit_SHA1_Update(&c, hdr, hdrlen);\n-\tgit_SHA1_Update(&c, dat->buf, dat->len);\n-\tgit_SHA1_Final(sha1, &c);\n+\tprepare_object_hash(type, dat, hdr, &hdrlen, sha1);\n \tif (sha1out)\n \t\thashcpy(sha1out, sha1);\n \n-- \n1.7.3.4\n"},{"id":"172202","messageId":"1311828370-30477-3-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":"1311828370-30477-1-git-send-email-divanorama@gmail.com","subject":"[PATCH/WIP 2/7] fast-import: be saner with temporary trees","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:05Z","receivedAt":"2011-07-28T04:46:05Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"new_tree_entry() doesn't zero or otherwise initialize the returned\nentry, neither does release_tree_entry(). So it is quite possible\nto get previously released data in a new entry.\n\nparse_ls doesn't set entry->versions[0] fields, but it does call\nstore_tree(entry) which looks for this base sha1 and tries to do\ndelta compression with that random object.\n\nReset entry->versions[0] fields to make things more predictable\nand to avoid surprises here.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c |    3 +++\n 1 files changed, 3 insertions(+), 0 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 05cc55e..da9cb62 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2968,6 +2968,9 @@ static void parse_ls(struct branch *b)\n \t} else {\n \t\tstruct object_entry *e = parse_treeish_dataref(&p);\n \t\troot = new_tree_entry();\n+\t\thashclr(root->versions[0].sha1);\n+\t\troot->versions[0].mode = 0;\n+\t\troot->versions[1].mode = S_IFDIR;\n \t\thashcpy(root->versions[1].sha1, e->idx.sha1);\n \t\tload_tree(root);\n \t\tif (*p++ != ' ')\n-- \n1.7.3.4\n"},{"id":"172203","messageId":"1311828370-30477-4-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":"1311828370-30477-1-git-send-email-divanorama@gmail.com","subject":"[PATCH/WIP 3/7] fast-import: fix a data corruption in parse_ls","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:06Z","receivedAt":"2011-07-28T04:46:06Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"store_tree sets versions[0] = versions[1] unconditionally. This is fine\nif it is run from the very root. But if it's run for a intermediate\nnode in parse_ls, node's parent versions[0] can become invalid as it\nreferences it's children versions[0].\n\nMove dropping old version to a function and don't drop old version in\nparse_ls. Also this split will allow to perform a few more fixes for\nstore_tree itself.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c |   42 ++++++++++++++++++++++++++----------------\n 1 files changed, 26 insertions(+), 16 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex da9cb62..d5915b8 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1439,12 +1439,36 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)\n \t}\n }\n \n-static void store_tree(struct tree_entry *root)\n+static void drop_old(struct tree_entry *root)\n {\n \tstruct tree_content *t = root->tree;\n \tunsigned int i, j, del;\n+\n+\thashcpy(root->versions[0].sha1, root->versions[1].sha1);\n+\troot->versions[0].mode = root->versions[1].mode;\n+\n+\tif (!t)\n+\t\treturn;\n+\n+\tfor (i = 0, j = 0, del = 0; i < t->entry_count; i++) {\n+\t\tstruct tree_entry *e = t->entries[i];\n+\t\tif (e->versions[1].mode) {\n+\t\t\tdrop_old(e);\n+\t\t\tt->entries[j++] = e;\n+\t\t} else {\n+\t\t\trelease_tree_entry(e);\n+\t\t\tdel++;\n+\t\t}\n+\t}\n+\tt->entry_count -= del;\n+}\n+\n+static void store_tree(struct tree_entry *root)\n+{\n+\tstruct tree_content *t = root->tree;\n \tstruct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };\n \tstruct object_entry *le;\n+\tunsigned int i;\n \n \tif (!is_null_sha1(root->versions[1].sha1))\n \t\treturn;\n@@ -1464,20 +1488,7 @@ static void store_tree(struct tree_entry *root)\n \n \tmktree(t, 1, &new_tree);\n \tstore_object(OBJ_TREE, &new_tree, &lo, root->versions[1].sha1, 0);\n-\n \tt->delta_depth = lo.depth;\n-\tfor (i = 0, j = 0, del = 0; i < t->entry_count; i++) {\n-\t\tstruct tree_entry *e = t->entries[i];\n-\t\tif (e->versions[1].mode) {\n-\t\t\te->versions[0].mode = e->versions[1].mode;\n-\t\t\thashcpy(e->versions[0].sha1, e->versions[1].sha1);\n-\t\t\tt->entries[j++] = e;\n-\t\t} else {\n-\t\t\trelease_tree_entry(e);\n-\t\t\tdel++;\n-\t\t}\n-\t}\n-\tt->entry_count -= del;\n }\n \n static void tree_content_replace(\n@@ -2640,8 +2651,7 @@ static void parse_new_commit(void)\n \n \t/* build the tree and the commit */\n \tstore_tree(&b->branch_tree);\n-\thashcpy(b->branch_tree.versions[0].sha1,\n-\t\tb->branch_tree.versions[1].sha1);\n+\tdrop_old(&b->branch_tree);\n \n \tstrbuf_reset(&new_data);\n \tstrbuf_addf(&new_data, \"tree %s\\n\",\n-- \n1.7.3.4\n"},{"id":"172207","messageId":"1311828370-30477-5-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":"1311828370-30477-1-git-send-email-divanorama@gmail.com","subject":"[PATCH/WIP 4/7] fast-import: fix data corruption in store_tree","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:07Z","receivedAt":"2011-07-28T04:46:07Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"store_tree didn't check for S_ISDIR(versions[1].mode), but it did check\nfor tree != NULL.\n\nIt's possible that tree == NULL && S_ISDIR(versions[1].mode) in which\ncase we need to load_tree and then to store_tree, and not to drop that\nentry. Calling load_tree requires S_ISDIR check to be present, that's\nwhy it is added..\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c |    7 +++++--\n 1 files changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex d5915b8..d917ea6 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1474,8 +1474,11 @@ static void store_tree(struct tree_entry *root)\n \t\treturn;\n \n \tfor (i = 0; i < t->entry_count; i++) {\n-\t\tif (t->entries[i]->tree)\n-\t\t\tstore_tree(t->entries[i]);\n+\t\tif (!S_ISDIR(t->entries[i]->versions[1].mode))\n+\t\t\tcontinue;\n+\t\tif (!t->entries[i]->tree)\n+\t\t\tload_tree(t->entries[i]);\n+\t\tstore_tree(t->entries[i]);\n \t}\n \n \tle = find_object(root->versions[0].sha1);\n-- \n1.7.3.4\n"},{"id":"172204","messageId":"1311828370-30477-6-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":"1311828370-30477-1-git-send-email-divanorama@gmail.com","subject":"[PATCH/WIP 5/7] fast-import: extract tree_content reading function","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:08Z","receivedAt":"2011-07-28T04:46:08Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"It will be useful to fetch tree contents by a sha1. First, we can check\nour in-memory tree against it. Second, we may need to read both old and\nnew tree contents and merge them in load_tree.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c |   19 +++++++++++--------\n 1 files changed, 11 insertions(+), 8 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex d917ea6..9f0d2fe 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1344,19 +1344,14 @@ static const char *get_mode(const char *str, uint16_t *modep)\n \treturn str;\n }\n \n-static void load_tree(struct tree_entry *root)\n+static void load_tree_content(struct tree_content **root, unsigned char *sha1)\n {\n-\tunsigned char *sha1 = root->versions[1].sha1;\n \tstruct object_entry *myoe;\n-\tstruct tree_content *t;\n+\tstruct tree_content *t = *root;\n \tunsigned long size;\n \tchar *buf;\n \tconst char *c;\n \n-\troot->tree = t = new_tree_content(8);\n-\tif (is_null_sha1(sha1))\n-\t\treturn;\n-\n \tmyoe = find_object(sha1);\n \tif (myoe && myoe->pack_id != MAX_PACK_ID) {\n \t\tif (myoe->type != OBJ_TREE)\n@@ -1377,7 +1372,7 @@ static void load_tree(struct tree_entry *root)\n \t\tstruct tree_entry *e = new_tree_entry();\n \n \t\tif (t->entry_count == t->entry_capacity)\n-\t\t\troot->tree = t = grow_tree_content(t, t->entry_count);\n+\t\t\t*root = t = grow_tree_content(t, t->entry_count);\n \t\tt->entries[t->entry_count++] = e;\n \n \t\te->tree = NULL;\n@@ -1394,6 +1389,14 @@ static void load_tree(struct tree_entry *root)\n \tfree(buf);\n }\n \n+static void load_tree(struct tree_entry *root)\n+{\n+\troot->tree = t = new_tree_content(8);\n+\tif (is_null_sha1(sha1))\n+\t\treturn;\n+       load_tree_content(&root->tree, root->versions[1].sha1);\n+}\n+\n static int tecmp0 (const void *_a, const void *_b)\n {\n \tstruct tree_entry *a = *((struct tree_entry**)_a);\n-- \n1.7.3.4\n"},{"id":"172205","messageId":"1311828370-30477-7-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":"1311828370-30477-1-git-send-email-divanorama@gmail.com","subject":"[PATCH/WIP 6/7] fast-import: workaround data corruption","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:09Z","receivedAt":"2011-07-28T04:46:09Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"fast-import keeps track of some delta-base for tree objects. When it is\ntime to compute the delta, base object is constructed from in-memory\ntree representation using children's delta bases sha1. But these can be\nunrelated due to several bugs, and it leads to object with wrong sha1\nbeing delta-written to the packfile.\n\nWe have the base sha1 and what we think it's data is. Verify sha1 and if\nit doesn't match, report it to stderr and don't use delta for this tree.\n\nWe could also die() here when bugs are fixed. Or we can see if the data\nwe've got is from our pack file and so still try to use it as a base.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c |   14 +++++++++++++-\n 1 files changed, 13 insertions(+), 1 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 9f0d2fe..14a2a63 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1469,7 +1469,8 @@ static void drop_old(struct tree_entry *root)\n static void store_tree(struct tree_entry *root)\n {\n \tstruct tree_content *t = root->tree;\n-\tstruct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };\n+\tstruct strbuf empty = STRBUF_INIT;\n+\tstruct last_object lo = { empty, 0, 0, /* no_swap */ 1 };\n \tstruct object_entry *le;\n \tunsigned int i;\n \n@@ -1486,10 +1487,21 @@ static void store_tree(struct tree_entry *root)\n \n \tle = find_object(root->versions[0].sha1);\n \tif (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n+\t\tunsigned char sh[20];\n \t\tmktree(t, 0, &old_tree);\n \t\tlo.data = old_tree;\n \t\tlo.offset = le->idx.offset;\n \t\tlo.depth = t->delta_depth;\n+\n+\t\tprepare_object_hash(OBJ_TREE, &old_tree, NULL, NULL, sh);\n+\t\tif (hashcmp(sh, root->versions[0].sha1)) {\n+\t\t\tfprintf(stderr, \"internal sha1 delta base mismatch,\"\n+\t\t\t\t\t\" won't use delta for that tree\\n\");\n+\t\t\tlo.data = empty;\n+\t\t\tlo.offset = 0;\n+\t\t\tlo.depth = 0;\n+\t\t}\n+\n \t}\n \n \tmktree(t, 1, &new_tree);\n-- \n1.7.3.4\n"},{"id":"172206","messageId":"1311828370-30477-8-git-send-email-divanorama@gmail.com","threadId":"27939","inReplyTo":"1311828370-30477-1-git-send-email-divanorama@gmail.com","subject":"[PATCH/WIP 7/7] fast-import: fix data corruption in load_tree","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T04:46:10Z","receivedAt":"2011-07-28T04:46:10Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"load_tree could be used to load a tree having different base and\ncurrent sha1. For example it can happens after a parent tree was\nset by sha1 (it's tree becomes NULL, versions[0].sha1 remain and\nversions[1].sha1 change). But it doesn't look at versions[0].sha1\nand just loads a new version resetting the base one to the new one.\nThis corrupts parent tree delta.\n\nTry to detect that case. Load both base and new trees and merge them\ntogether so that mktree is able to produce both base and new trees\ncorrectly.\n\nThere still may be a delta data corruption. For example tree_content_set\nwith subtree != NULL can produce subtree entries bases and subtree's new\nparent base mismatch. tree_content_set is used in file_modify_cr - copy\nand move trees by names. And another place is notes writing thing that\ndoes some trees magic too.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c |   68 ++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 files changed, 60 insertions(+), 8 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 14a2a63..feccd14 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1389,14 +1389,6 @@ static void load_tree_content(struct tree_content **root, unsigned char *sha1)\n \tfree(buf);\n }\n \n-static void load_tree(struct tree_entry *root)\n-{\n-\troot->tree = t = new_tree_content(8);\n-\tif (is_null_sha1(sha1))\n-\t\treturn;\n-       load_tree_content(&root->tree, root->versions[1].sha1);\n-}\n-\n static int tecmp0 (const void *_a, const void *_b)\n {\n \tstruct tree_entry *a = *((struct tree_entry**)_a);\n@@ -1442,6 +1434,66 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)\n \t}\n }\n \n+static void load_tree(struct tree_entry *root)\n+{\n+\tstruct tree_content *oldt;\n+\tsize_t n, i, j;\n+\n+\troot->tree = new_tree_content(8);\n+\tif (is_null_sha1(root->versions[1].sha1)) {\n+\t\tif (!S_ISDIR(root->versions[0].mode) || is_null_sha1(root->versions[0].sha1) || !hashcmp(root->versions[0].sha1, root->versions[1].sha1))\n+\t\t\treturn;\n+\t\t// looks like it is currently unreachable, but let it be for a while\n+\t\tload_tree_content(&root->tree, root->versions[0].sha1);\n+\t\tfor (i = 0; i < root->tree->entry_count; ++i) {\n+\t\t\troot->tree->entries[i]->versions[1].mode = 0;\n+\t\t\thashclr(root->tree->entries[i]->versions[1].sha1);\n+\t\t}\n+\t\treturn;\n+\t}\n+\n+\tload_tree_content(&root->tree, root->versions[1].sha1);\n+\tif (!S_ISDIR(root->versions[0].mode) || is_null_sha1(root->versions[0].sha1) || !hashcmp(root->versions[0].sha1, root->versions[1].sha1))\n+ \t\treturn;\n+\n+\toldt = new_tree_content(8);\n+\tload_tree_content(&oldt, root->versions[0].sha1);\n+\n+\tqsort(root->tree->entries, root->tree->entry_count, sizeof(root->tree->entries[0]), tecmp1);\n+\tqsort(oldt->entries, oldt->entry_count, sizeof(oldt->entries[0]), tecmp1);\n+\n+\tn = root->tree->entry_count;\n+\ti = 0;\n+\tj = 0;\n+\twhile (i < n || j < oldt->entry_count) {\n+\t\tint cmp = i == n ? 1 : j == oldt->entry_count ? -1 : tecmp1(root->tree->entries + i, oldt->entries + j);\n+\t\tif (cmp > 0) {\n+\t\t\tif (root->tree->entry_count == root->tree->entry_capacity)\n+\t\t\t\troot->tree = grow_tree_content(root->tree, root->tree->entry_count);\n+\t\t\toldt->entries[j]->versions[1].mode = 0;\n+\t\t\thashclr(oldt->entries[j]->versions[1].sha1);\n+\t\t\troot->tree->entries[root->tree->entry_count++] = oldt->entries[j];\n+\t\t\toldt->entries[j] = NULL;\n+\t\t\t++j;\n+\t\t} else if (cmp < 0) {\n+\t\t\troot->tree->entries[i]->versions[0].mode = 0;\n+\t\t\thashclr(root->tree->entries[i]->versions[0].sha1);\n+\t\t\t++i;\n+\t\t} else {\n+\t\t\troot->tree->entries[i]->versions[0].mode = oldt->entries[j]->versions[1].mode;\n+\t\t\thashcpy(root->tree->entries[i]->versions[0].sha1, oldt->entries[j]->versions[1].sha1);\n+\t\t\t++i;\n+\t\t\t++j;\n+\t\t}\n+\t}\n+\tfor (j = 0; j < oldt->entry_count; ++j)\n+\t\tif (oldt->entries[j]) {\n+\t\t\trelease_tree_entry(oldt->entries[j]);\n+\t\t\toldt->entries[j] = NULL;\n+\t\t}\n+\trelease_tree_content(oldt);\n+}\n+\n static void drop_old(struct tree_entry *root)\n {\n \tstruct tree_content *t = root->tree;\n-- \n1.7.3.4\n"},{"id":"172235","messageId":"20110728063134.GA4179@elie","threadId":"27939","inReplyTo":"1311828370-30477-7-git-send-email-divanorama@gmail.com","subject":"Re: [PATCH/WIP 6/7] fast-import: workaround data corruption","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-28T06:31:34Z","receivedAt":"2011-07-28T06:31:34Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi!\n\nDmitry Ivankov wrote:\n\n> fast-import keeps track of some delta-base for tree objects. When it is\n> time to compute the delta, base object is constructed from in-memory\n> tree representation using children's delta bases sha1. But these can be\n> unrelated due to several bugs, and it leads to object with wrong sha1\n> being delta-written to the packfile.\n\nThis seems like as good a starting point as any.  Small language\nnitpicks:\n\n - \"some delta-base\" is somewhat vague\n\n - missing article (probably \"the\") before \"base object\" and\n   \"children's\"\n\n - does \"children's delta bases sha1\" mean \"the pre-computed object\n   names and modes in versions[0].{sha1,mode} for each tree entry\" or\n   something else?\n\n - when you say \"unrelated\": unrelated to what?\n\n> We have the base sha1 and what we think it's data is. Verify sha1 and if\n> it doesn't match, report it to stderr and don't use delta for this tree.\n\nAt any rate, if I understand correctly, the idea is that when store_tree()\nis being called, root->versions[0].sha1 does not match the tree object\nimplied by root->tree->entries[*]->{name,versions[0].{mode,sha1}}.  This\npatch adds a quick check to notice when that happens.\n\nMakes a lot of sense, especially as a demonstration of the problem.\nstore_object() returns early in many cases so this probably does make\nthe bug easier to find (good).\n\nI wonder if it would make more sense to perform this sanity check in\nstore_object() so blobs could benefit, too.  How much does the check slow\nfast-import down (if at all)?\n\n> We could also die() here when bugs are fixed.\n\nIf the check is fast, sure, why not? :)  The only reason I can think\nof is that computing a SHA-1 is an O(size of object) cost which it\nwould be nice to avoid if profiling shows it is noticeable.\n\n> Or we can see if the data\n> we've got is from our pack file and so still try to use it as a base.\n\nCan you elaborate?  When would versions[0].sha1 not match the data\nbut the data still be in the pack file?\n\n> --- a/fast-import.c\n> +++ b/fast-import.c\n[...]\n> @@ -1486,10 +1487,21 @@ static void store_tree(struct tree_entry *root)\n>  \n>  \tle = find_object(root->versions[0].sha1);\n>  \tif (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n> +\t\tunsigned char sh[20];\n\nWhat does \"sh\" stand for?\n\n>  \t\tmktree(t, 0, &old_tree);\n>  \t\tlo.data = old_tree;\n>  \t\tlo.offset = le->idx.offset;\n>  \t\tlo.depth = t->delta_depth;\n> +\n> +\t\tprepare_object_hash(OBJ_TREE, &old_tree, NULL, NULL, sh);\n> +\t\tif (hashcmp(sh, root->versions[0].sha1)) {\n> +\t\t\tfprintf(stderr, \"internal sha1 delta base mismatch,\"\n> +\t\t\t\t\t\" won't use delta for that tree\\n\");\n> +\t\t\tlo.data = empty;\n\nTo avoid a memory leak and introducing an unnecessary variable:\n\n\t\t\tstrbuf_reset(&lo.data);\n\nThanks, that was interesting.\n"},{"id":"172236","messageId":"20110728072748.GB4179@elie","threadId":"27939","inReplyTo":"1311828370-30477-3-git-send-email-divanorama@gmail.com","subject":"Re: [PATCH/WIP 2/7] fast-import: be saner with temporary trees","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-28T07:27:48Z","receivedAt":"2011-07-28T07:27:48Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dmitry Ivankov wrote:\n\n> new_tree_entry() doesn't zero or otherwise initialize the returned\n> entry, neither does release_tree_entry(). So it is quite possible\n> to get previously released data in a new entry.\n\nThanks.  Background for the confused: new_tree_entry /\nrelease_tree_entry manage a stack of tree_entry structs to use as\ntemporaries.  Initializing them is the responsibility of the caller,\nboth after allocation with xmalloc() when existing temporaries are\nexhausted and after used entries are pushed with release_tree_entry().\n\n> parse_ls doesn't set entry->versions[0] fields, but it does call\n> store_tree(entry) which looks for this base sha1 and tries to do\n> delta compression with that random object.\n>\n> Reset entry->versions[0] fields to make things more predictable\n> and to avoid surprises here.\n>\n> Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>\n\nGood idea --- \"root\" is invalid at this point.  Looks like a mistake\nintroduced by my tweaks to v1.7.5-rc0~3^2~33 (fast-import: add 'ls'\ncommand, 2010-12-02).\n\nBut isn't store_tree() only called on \"leaf\" which is completely\nzero-initialized?\n\nSo I don't see why this change would have any effect.  For what it's\nworth, even so, except for the commit message,\n\nAcked-by: Jonathan Nieder <jrnieder@gmail.com>\n"},{"id":"172237","messageId":"20110728073434.GC4179@elie","threadId":"27939","inReplyTo":"1311828370-30477-4-git-send-email-divanorama@gmail.com","subject":"Re: [PATCH/WIP 3/7] fast-import: fix a data corruption in parse_ls","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-28T07:34:34Z","receivedAt":"2011-07-28T07:34:34Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dmitry Ivankov wrote:\n\n> store_tree sets versions[0] = versions[1] unconditionally. This is fine\n> if it is run from the very root.\n\nTrue.\n\n> But if it's run for a intermediate\n> node in parse_ls, node's parent versions[0] can become invalid as it\n> references it's children versions[0].\n\nA puzzle: when would parse_ls() call store_tree() on a subdirectory?\nThe store_tree() call is preceded by\n\n\ttree_content_get(root, p, &leaf);\n\nwhich makes a deep copy of \"root\" in leaf (which seems to be leaked\n--- oops).\n"},{"id":"172239","messageId":"20110728074239.GA5980@elie","threadId":"27939","inReplyTo":"1311828370-30477-5-git-send-email-divanorama@gmail.com","subject":"Re: [PATCH/WIP 4/7] fast-import: fix data corruption in store_tree","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-28T07:42:39Z","receivedAt":"2011-07-28T07:42:39Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dmitry Ivankov wrote:\n\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -1474,8 +1474,11 @@ static void store_tree(struct tree_entry *root)\n>  \t\treturn;\n>  \n>  \tfor (i = 0; i < t->entry_count; i++) {\n> -\t\tif (t->entries[i]->tree)\n> -\t\t\tstore_tree(t->entries[i]);\n> +\t\tif (!S_ISDIR(t->entries[i]->versions[1].mode))\n> +\t\t\tcontinue;\n> +\t\tif (!t->entries[i]->tree)\n> +\t\t\tload_tree(t->entries[i]);\n> +\t\tstore_tree(t->entries[i]);\n\nHow can this load_tree call work if t->entries[i]->versions[1].sha1\nis not already in the object database?\n"},{"id":"172240","messageId":"CA+gfSn-62W8TPjaKkSZCbWmxaeNnk_KSWJ-1=x106hGk5cEw=w@mail.gmail.com","threadId":"27939","inReplyTo":"20110728074239.GA5980@elie","subject":"Re: [PATCH/WIP 4/7] fast-import: fix data corruption in store_tree","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T08:11:47Z","receivedAt":"2011-07-28T08:11:47Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"On Thu, Jul 28, 2011 at 1:42 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n> Dmitry Ivankov wrote:\n>\n>> --- a/fast-import.c\n>> +++ b/fast-import.c\n>> @@ -1474,8 +1474,11 @@ static void store_tree(struct tree_entry *root)\n>>               return;\n>>\n>>       for (i = 0; i < t->entry_count; i++) {\n>> -             if (t->entries[i]->tree)\n>> -                     store_tree(t->entries[i]);\n>> +             if (!S_ISDIR(t->entries[i]->versions[1].mode))\n>> +                     continue;\n>> +             if (!t->entries[i]->tree)\n>> +                     load_tree(t->entries[i]);\n>> +             store_tree(t->entries[i]);\n>\n> How can this load_tree call work if t->entries[i]->versions[1].sha1\n> is not already in the object database?\nWell, it can be in the database and at the same time\nt->entries[i]->tree == NULL.\nIn my testcase the commit is like\n\nls :10386 trunk\nM 040000 e1b2ea9d3634cb7914044425ffae91945c41ac6a branches/cygnus\nD branches/cygnus/gcc/assert.h\nD branches/cygnus/gcc/collect2.c\nD branches/cygnus/gcc/cccp.c\nD branches/cygnus/gcc/c-parse.gperf\n...\nonly D branches/cygnus/gcc/..... lines\nprogress done #here we call it, so it's when we store whole tree, some\nsubdirectory of branches/cygnus\n\nthe load_tree really gets called (with whole series applied to\nfast-import) and the load works (sha1 =\n2e90a035614854f626bb35eeac517f41ac84da27)\nThough I don't yet see if not loading it breaks anything in my test\n(with the whole series).\n"}]}