{"thread":{"id":"28075","subject":"[PATCH 0/3] fix data corruption in fast-import","startedAt":"2011-08-12T10:32:47Z","lastAt":"2011-08-20T18:28:34Z","messageCount":14,"participants":["Dmitry Ivankov","Jonathan Nieder","Andreas Schwab"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"173394","messageId":"1313145170-24471-1-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":null,"subject":"[PATCH 0/3] fix data corruption in fast-import","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-12T10:32:47Z","receivedAt":"2011-08-12T10:32:47Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"Finally the bug reported first in [1] is solved and has a small testcase.\nPreliminary attempts can be found in [2] for curious.\nAnd the actual \"3/3: fix\" comes from [3].\n\nBrief introduction. While testing huge imports produced by svn-fe I've found\na \"failed to unpack delta\" error in fast-import, which is actually caused by\n\"sha1 mismatch\" error in a packfile, and this one is caused by a bug of producing\nwrong deltas for tree objects in fast-import. \n\nLooks like that only 'M 040000 sha1_or_mark path' commands could trigger it. \nThey were introduced in tags/v1.7.3-rc0~75^2\n(30 Jun 2010  334fba65.. Teach fast-import to import subtrees named by tree id)\nThis series should resolve the bug for any copy/rename/set/delete trees scenario\nanyway.\n\nI've tested it on a gcc svn repository import - went fine, trees match the gcc\ngit mirror on github. One more test is ~700k commits from kde repository - fine\ntoo.\n\n1/3 just extracts a sha1 calculation function for 2/3\n2/3 adds a die() for \"corrupted\" delta data and a testcase that triggers it\n3/3 is the fix\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/176753\n[2] http://thread.gmane.org/gmane.comp.version-control.git/178007\n[3] http://thread.gmane.org/gmane.comp.version-control.git/176753/focus=178053\n\nDmitry Ivankov (3):\n  fast-import: extract object preparation function\n  fast-import: add a check for tree delta base sha1\n  fast-import: prevent producing bad delta\n\n fast-import.c          |   85 +++++++++++++++++++++++++++++++++++++++---------\n t/t9300-fast-import.sh |   38 +++++++++++++++++++++\n 2 files changed, 107 insertions(+), 16 deletions(-)\n\n-- \n1.7.3.4\n"},{"id":"173395","messageId":"1313145170-24471-2-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":"1313145170-24471-1-git-send-email-divanorama@gmail.com","subject":"[PATCH 1/3] fast-import: extract object preparation function","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-12T10:32:48Z","receivedAt":"2011-08-12T10:32:48Z","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 7cc2262..d0f8580 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1006,6 +1006,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@@ -1018,15 +1042,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":"173396","messageId":"1313145170-24471-3-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":"1313145170-24471-1-git-send-email-divanorama@gmail.com","subject":"[PATCH 2/3] fast-import: add a check for tree delta base sha1","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-12T10:32:49Z","receivedAt":"2011-08-12T10:32:49Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"fast-import is able to write imported tree objects in delta format.\nIt holds a tree structure in memory where each tree entry may have\na delta base sha1 assigned. When delta base data is needed it is\nreconstructed from this in-memory structure. Though sometimes the\ndelta base data doesn't match the delta base sha1 so wrong or even\ncorrupt pack is produced.\n\nTo create a small easily reproducible test, add an excessive check\nfor delta base sha1. It's not likely that computing sha1 for each\ntree delta base costs us much.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c          |   20 +++++++++++++++-----\n t/t9300-fast-import.sh |   38 ++++++++++++++++++++++++++++++++++++++\n 2 files changed, 53 insertions(+), 5 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex d0f8580..8196d1b 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1455,12 +1455,22 @@ static void store_tree(struct tree_entry *root)\n \t\t\tstore_tree(t->entries[i]);\n \t}\n \n-\tle = find_object(root->versions[0].sha1);\n-\tif (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n+\tif (!is_null_sha1(root->versions[0].sha1)\n+\t\t\t\t\t&& S_ISDIR(root->versions[0].mode)) {\n+\t\tunsigned char old_tree_sha1[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+\t\tprepare_object_hash(OBJ_TREE, &old_tree,\n+\t\t\t\t\t\tNULL, NULL, old_tree_sha1);\n+\n+\t\tif (hashcmp(old_tree_sha1, root->versions[0].sha1))\n+\t\t\tdie(\"internal tree delta base sha1 mismatch\");\n+\n+\t\tle = find_object(root->versions[0].sha1);\n+\t\tif (le && le->pack_id == pack_id) {\n+\t\t\tlo.data = old_tree;\n+\t\t\tlo.offset = le->idx.offset;\n+\t\t\tlo.depth = t->delta_depth;\n+\t\t}\n \t}\n \n \tmktree(t, 1, &new_tree);\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex f256475..c70e489 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -734,6 +734,44 @@ test_expect_success \\\n \t git diff-tree --abbrev --raw L^ L >output &&\n \t test_cmp expect output'\n \n+cat >input <<INPUT_END\n+blob\n+mark :1\n+data <<EOF\n+the data\n+EOF\n+\n+commit refs/heads/L2\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+data <<COMMIT\n+init L2\n+COMMIT\n+\n+M 644 :1 a/b/c\n+M 644 :1 a/b/d\n+M 644 :1 a/e/f\n+INPUT_END\n+\n+cat >input2 <<INPUT_END\n+commit refs/heads/L2\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+data <<COMMIT\n+update L2\n+COMMIT\n+from refs/heads/L2^0\n+M 040000 @A g\n+M 040000 @E g/b\n+M 040000 @E g/b/h\n+INPUT_END\n+\n+test_expect_failure \\\n+    'L: verify internal tree delta base' \\\n+\t'git fast-import <input &&\n+\tA=$(git ls-tree L2 a | tr \" \" \"\\t\" | cut -f 3) &&\n+\tE=$(git ls-tree L2 a/e | tr \" \" \"\\t\" | cut -f 3) &&\n+\tcat input2 | sed -e \"s/@A/$A/\" -e \"s/@E/$E/\" >input &&\n+\tgit fast-import <input'\n+\n ###\n ### series M\n ###\n-- \n1.7.3.4\n"},{"id":"173397","messageId":"1313145170-24471-4-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":"1313145170-24471-1-git-send-email-divanorama@gmail.com","subject":"[PATCH 3/3] fast-import: prevent producing bad delta","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-12T10:32:50Z","receivedAt":"2011-08-12T10:32:50Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"To produce deltas for tree objects fast-import tracks two versions\nof tree's entries - base and current one. Base version stands both\nfor a delta base of this tree, and for a entry inside a delta base\nof a parent tree. So care should be taken to keep it in sync.\n\ntree_content_set cuts away a whole subtree and replaces it with a\nnew one (or NULL for lazy load of a tree with known sha1). It\nkeeps a base sha1 for this subtree (needed for parent tree). And\nhere is the problem, 'subtree' tree root doesn't have the implied\nbase version entries.\n\nAdjusting the subtree to include them would mean a deep rewrite of\nsubtree. Invalidating the subtree base version would mean recursive\ninvalidation of parents' base versions. So just mark this tree as\ndo-not-delta me. Abuse setuid bit for this purpose.\n\ntree_content_replace is the same as tree_content_set except that is\nis used to replace the root, so just clearing base sha1 here (instead\nof setting the bit) is fine.\n\n[di: log message]\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c          |   33 +++++++++++++++++++++++++++++----\n t/t9300-fast-import.sh |    2 +-\n 2 files changed, 30 insertions(+), 5 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 8196d1b..d9049af 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -170,6 +170,11 @@ Format of STDIN stream:\n #define DEPTH_BITS 13\n #define MAX_DEPTH ((1<<DEPTH_BITS)-1)\n \n+/*\n+ * We abuse the setuid bit on directories to mean \"do not delta\".\n+ */\n+#define NO_DELTA S_ISUID\n+\n struct object_entry {\n \tstruct pack_idx_entry idx;\n \tstruct object_entry *next;\n@@ -1434,8 +1439,9 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)\n \t\tstruct tree_entry *e = t->entries[i];\n \t\tif (!e->versions[v].mode)\n \t\t\tcontinue;\n-\t\tstrbuf_addf(b, \"%o %s%c\", (unsigned int)e->versions[v].mode,\n-\t\t\t\t\te->name->str_dat, '\\0');\n+\t\tstrbuf_addf(b, \"%o %s%c\",\n+\t\t\t(unsigned int)(e->versions[v].mode & ~NO_DELTA),\n+\t\t\te->name->str_dat, '\\0');\n \t\tstrbuf_add(b, e->versions[v].sha1, 20);\n \t}\n }\n@@ -1445,7 +1451,7 @@ static void store_tree(struct tree_entry *root)\n \tstruct tree_content *t = root->tree;\n \tunsigned int i, j, del;\n \tstruct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };\n-\tstruct object_entry *le;\n+\tstruct object_entry *le = NULL;\n \n \tif (!is_null_sha1(root->versions[1].sha1))\n \t\treturn;\n@@ -1456,6 +1462,7 @@ static void store_tree(struct tree_entry *root)\n \t}\n \n \tif (!is_null_sha1(root->versions[0].sha1)\n+\t\t\t\t\t&& !(root->versions[0].mode & NO_DELTA)\n \t\t\t\t\t&& S_ISDIR(root->versions[0].mode)) {\n \t\tunsigned char old_tree_sha1[20];\n \t\tmktree(t, 0, &old_tree);\n@@ -1499,6 +1506,7 @@ static void tree_content_replace(\n {\n \tif (!S_ISDIR(mode))\n \t\tdie(\"Root cannot be a non-directory\");\n+\thashclr(root->versions[0].sha1);\n \thashcpy(root->versions[1].sha1, sha1);\n \tif (root->tree)\n \t\trelease_tree_content_recursive(root->tree);\n@@ -1543,6 +1551,23 @@ static int tree_content_set(\n \t\t\t\tif (e->tree)\n \t\t\t\t\trelease_tree_content_recursive(e->tree);\n \t\t\t\te->tree = subtree;\n+\n+\t\t\t\t/*\n+\t\t\t\t * We need to leave e->versions[0].sha1 alone\n+\t\t\t\t * to avoid modifying the preimage tree used\n+\t\t\t\t * when writing out the parent directory.\n+\t\t\t\t * But after replacing the subdir with a\n+\t\t\t\t * completely different one, it's not a good\n+\t\t\t\t * delta base any more, and besides, we've\n+\t\t\t\t * thrown away the tree entries needed to\n+\t\t\t\t * make a delta against it.\n+\t\t\t\t *\n+\t\t\t\t * So let's just explicitly disable deltas\n+\t\t\t\t * for the subtree.\n+\t\t\t\t */\n+\t\t\t\tif (S_ISDIR(e->versions[0].mode))\n+\t\t\t\t\te->versions[0].mode |= NO_DELTA;\n+\n \t\t\t\thashclr(root->versions[1].sha1);\n \t\t\t\treturn 1;\n \t\t\t}\n@@ -2957,7 +2982,7 @@ static void print_ls(int mode, const unsigned char *sha1, const char *path)\n \t\t/* mode SP type SP object_name TAB path LF */\n \t\tstrbuf_reset(&line);\n \t\tstrbuf_addf(&line, \"%06o %s %s\\t\",\n-\t\t\t\tmode, type, sha1_to_hex(sha1));\n+\t\t\t\tmode & ~NO_DELTA, type, sha1_to_hex(sha1));\n \t\tquote_c_style(path, &line, NULL, 0);\n \t\tstrbuf_addch(&line, '\\n');\n \t}\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex c70e489..50b22f0 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -764,7 +764,7 @@ M 040000 @E g/b\n M 040000 @E g/b/h\n INPUT_END\n \n-test_expect_failure \\\n+test_expect_success \\\n     'L: verify internal tree delta base' \\\n \t'git fast-import <input &&\n \tA=$(git ls-tree L2 a | tr \" \" \"\\t\" | cut -f 3) &&\n-- \n1.7.3.4\n"},{"id":"173466","messageId":"20110813210221.GA16194@elie.gateway.2wire.net","threadId":"28075","inReplyTo":"1313145170-24471-3-git-send-email-divanorama@gmail.com","subject":"Re: [PATCH 2/3] fast-import: add a check for tree delta base sha1","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-08-13T21:02:21Z","receivedAt":"2011-08-13T21:02:21Z","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 is able to write imported tree objects in delta format.\n> It holds a tree structure in memory where each tree entry may have\n> a delta base sha1 assigned. When delta base data is needed it is\n> reconstructed from this in-memory structure. Though sometimes the\n> delta base data doesn't match the delta base sha1 so wrong or even\n> corrupt pack is produced.\n\nI'm having trouble parsing this; not sure why.  Some guesses:\n\n - dropping the word \"imported\" could help, since it is the\n   content of trees that comes from the user, not the tree objects\n\n - it's not clear to me what the second sentence is saying.  Do you\n   mean that git looks at the versions[0].sha1 fields of item in\n   t->entries to construct an in-memory tree object to delta against,\n   instead of finding the object named by versions[0].sha1, inflating\n   it, and using it directly?\n\n - the third sentence seems to be describing a problem, but I'm not\n   sure what the relationship is to this patch: will this patch fix\n   that problem, or does it just add a test illustrating it?\n\n> To create a small easily reproducible test, add an excessive check\n> for delta base sha1. It's not likely that computing sha1 for each\n> tree delta base costs us much.\n\nSince the first word in fast-import is \"fast\", I would be much\nhappier with some measurements with a typical import (i.e., one that\ndoesn't use --cat-blob-fd) than the statement \"It's not likely\". :)\n\nIf this tweak will continue to be useful after the fix, perhaps it\ncould be made optional.  I haven't thought carefully about this,\nthough.\n\nOn to the patch.\n\n[...]\n> +++ b/fast-import.c\n> @@ -1455,12 +1455,22 @@ static void store_tree(struct tree_entry *root)\n>  \t\t\tstore_tree(t->entries[i]);\n>  \t}\n>  \n> +\tif (!is_null_sha1(root->versions[0].sha1)\n> +\t\t\t\t\t&& S_ISDIR(root->versions[0].mode)) {\n> +\t\tunsigned char old_tree_sha1[20];\n> +\t\tmktree(t, 0, &old_tree);\n> +\t\tprepare_object_hash(OBJ_TREE, &old_tree,\n> +\t\t\t\t\t\tNULL, NULL, old_tree_sha1);\n> +\n> +\t\tif (hashcmp(old_tree_sha1, root->versions[0].sha1))\n> +\t\t\tdie(\"internal tree delta base sha1 mismatch\");\n\nThis is the heart of the patch; it involves several changes.\n\n 1. construct the base object tree whether the base object is in the\n    current pack or not\n\n 2. calculate its hash and compare to ->versions[0].sha1 as a sanity\n    check.\n\nFor large trees, I fear it could be an important slowdown.\n\n> +\n> -\t\tle = find_object(root->versions[0].sha1);\n> -\t\tif (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n> -\t\t\tmktree(t, 0, &old_tree);\n> +\t\tle = find_object(root->versions[0].sha1);\n> +\t\tif (le && le->pack_id == pack_id) {\n>  \t\t\tlo.data = old_tree;\n>  \t\t\tlo.offset = le->idx.offset;\n>  \t\t\tlo.depth = t->delta_depth;\n>  \t\t}\n> +\t}\n[...]\n> --- a/t/t9300-fast-import.sh\n> +++ b/t/t9300-fast-import.sh\n> @@ -734,6 +734,44 @@ test_expect_success \\\n[...]\n> +cat >input2 <<INPUT_END\n> +commit refs/heads/L2\n> +committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n> +data <<COMMIT\n> +update L2\n> +COMMIT\n> +from refs/heads/L2^0\n> +M 040000 @A g\n> +M 040000 @E g/b\n> +M 040000 @E g/b/h\n> +INPUT_END\n> +\n> +test_expect_failure \\\n> +    'L: verify internal tree delta base' \\\n> +\t'git fast-import <input &&\n> +\tA=$(git ls-tree L2 a | tr \" \" \"\\t\" | cut -f 3) &&\n> +\tE=$(git ls-tree L2 a/e | tr \" \" \"\\t\" | cut -f 3) &&\n> +\tcat input2 | sed -e \"s/@A/$A/\" -e \"s/@E/$E/\" >input &&\n> +\tgit fast-import <input'\n\nThe description (\"L: verify internal tree delta base\" here) should\ndescribe something we want to work --- a facility or a statement ---\nand should leave out words like \"verify\" unless it is a test of\nverification facilities.\n\nIn this example, I guess it is testing something like \"delta base is\nnot corrupted when replacing one directory by another\"?  (That's a\nrandom, wild guess and not meant as an example to be used verbatim.)\n\nI suppose I would be happier if we can find a way to reproduce this\nwithout modifying the behavior in such an invasive way.  Which should\nbe easier while thinking about the fix, so I'll move on to that.\n"},{"id":"173508","messageId":"1313346744-30340-1-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":"1313145170-24471-1-git-send-email-divanorama@gmail.com","subject":"[PATCH v2 0/2] fix data corruption in fast-import","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-14T18:32:22Z","receivedAt":"2011-08-14T18:32:22Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"It turns out the bug is older than \"M 040000..\" command.\nManaged to reproduce with just \"C ..\" command from tags/v1.5.3-rc2~6^2\nb6f3481b.. Teach fast-import to recursively copy files/directories (Jul 15 2007)\n\nAnd even better, there is no need to add a explicit check for sha1 mismatch (we\nmay still want to have this, but it can go separately).\n\nBasically the test does:\nFill two distinct directories old/a, old/b\nCommit them \n(necessary to make trees have sha1 computed and thus become potential delta bases)\nC old new\nC old/a new/b\nM ... new/b/new_file\n\nnew/b is stored as a delta against old/a, but with delta base pointing to old/b.\nAnd so ls-tree new/b fails, fsck fails both with \"failed to apply delta\".\n\nDmitry Ivankov (2):\n  fast-import: add a test for tree delta base corruption\n  fast-import: prevent producing bad delta\n\n fast-import.c          |   35 ++++++++++++++++++++++++++++++-----\n t/t9300-fast-import.sh |   41 +++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 71 insertions(+), 5 deletions(-)\n\n-- \n1.7.3.4\n"},{"id":"173509","messageId":"1313346744-30340-2-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":"1313145170-24471-1-git-send-email-divanorama@gmail.com","subject":"[PATCH v2 1/2] fast-import: add a test for tree delta base corruption","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-14T18:32:23Z","receivedAt":"2011-08-14T18:32:23Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"fast-import is able to write imported tree objects in delta format.\nIt holds a tree structure in memory where each tree entry may have\na delta base sha1 assigned. When delta base data is needed it is\nreconstructed from this in-memory structure. Though sometimes the\ndelta base data doesn't match the delta base sha1 so wrong or even\ncorrupt pack is produced.\n\nAdd a small test that produces a corrupt pack. It uses just tree\ncopy and file modification commands aside from the very basic commit\nand blob commands.\n\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n t/t9300-fast-import.sh |   41 +++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 41 insertions(+), 0 deletions(-)\n\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex f256475..e2b94b5 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -734,6 +734,47 @@ test_expect_success \\\n \t git diff-tree --abbrev --raw L^ L >output &&\n \t test_cmp expect output'\n \n+cat >input <<INPUT_END\n+blob\n+mark :1\n+data <<EOF\n+the data\n+EOF\n+\n+commit refs/heads/L2\n+committer C O Mitter <committer@example.com> 1112912473 -0700\n+data <<COMMIT\n+init L2\n+COMMIT\n+M 644 :1 a/b/c\n+M 644 :1 a/b/d\n+M 644 :1 a/e/f\n+\n+commit refs/heads/L2\n+committer C O Mitter <committer@example.com> 1112912473 -0700\n+data <<COMMIT\n+update L2\n+COMMIT\n+C a g\n+C a/e g/b\n+M 644 :1 g/b/h\n+INPUT_END\n+\n+cat <<EOF >expect\n+g/b/f\n+g/b/h\n+EOF\n+\n+test_expect_failure \\\n+    'L: nested tree copy does not corrupt deltas' \\\n+\t'git fast-import <input &&\n+\tgit ls-tree L2 g/b/ >tmp &&\n+\tcat tmp | cut -f 2 >actual &&\n+\ttest_cmp expect actual &&\n+\tgit fsck `git rev-parse L2`'\n+\n+git update-ref -d refs/heads/L2\n+\n ###\n ### series M\n ###\n-- \n1.7.3.4\n"},{"id":"173510","messageId":"1313346744-30340-3-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":"1313145170-24471-1-git-send-email-divanorama@gmail.com","subject":"[PATCH v2 2/2] fast-import: prevent producing bad delta","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-14T18:32:24Z","receivedAt":"2011-08-14T18:32:24Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"To produce deltas for tree objects fast-import tracks two versions\nof tree's entries - base and current one. Base version stands both\nfor a delta base of this tree, and for a entry inside a delta base\nof a parent tree. So care should be taken to keep it in sync.\n\ntree_content_set cuts away a whole subtree and replaces it with a\nnew one (or NULL for lazy load of a tree with known sha1). It\nkeeps a base sha1 for this subtree (needed for parent tree). And\nhere is the problem, 'subtree' tree root doesn't have the implied\nbase version entries.\n\nAdjusting the subtree to include them would mean a deep rewrite of\nsubtree. Invalidating the subtree base version would mean recursive\ninvalidation of parents' base versions. So just mark this tree as\ndo-not-delta me. Abuse setuid bit for this purpose.\n\ntree_content_replace is the same as tree_content_set except that is\nis used to replace the root, so just clearing base sha1 here (instead\nof setting the bit) is fine.\n\n[di: log message]\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c          |   35 ++++++++++++++++++++++++++++++-----\n t/t9300-fast-import.sh |    2 +-\n 2 files changed, 31 insertions(+), 6 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 7cc2262..0be7629 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -170,6 +170,11 @@ Format of STDIN stream:\n #define DEPTH_BITS 13\n #define MAX_DEPTH ((1<<DEPTH_BITS)-1)\n \n+/*\n+ * We abuse the setuid bit on directories to mean \"do not delta\".\n+ */\n+#define NO_DELTA S_ISUID\n+\n struct object_entry {\n \tstruct pack_idx_entry idx;\n \tstruct object_entry *next;\n@@ -1416,8 +1421,9 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)\n \t\tstruct tree_entry *e = t->entries[i];\n \t\tif (!e->versions[v].mode)\n \t\t\tcontinue;\n-\t\tstrbuf_addf(b, \"%o %s%c\", (unsigned int)e->versions[v].mode,\n-\t\t\t\t\te->name->str_dat, '\\0');\n+\t\tstrbuf_addf(b, \"%o %s%c\",\n+\t\t\t(unsigned int)(e->versions[v].mode & ~NO_DELTA),\n+\t\t\te->name->str_dat, '\\0');\n \t\tstrbuf_add(b, e->versions[v].sha1, 20);\n \t}\n }\n@@ -1427,7 +1433,7 @@ static void store_tree(struct tree_entry *root)\n \tstruct tree_content *t = root->tree;\n \tunsigned int i, j, del;\n \tstruct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };\n-\tstruct object_entry *le;\n+\tstruct object_entry *le = NULL;\n \n \tif (!is_null_sha1(root->versions[1].sha1))\n \t\treturn;\n@@ -1437,7 +1443,8 @@ static void store_tree(struct tree_entry *root)\n \t\t\tstore_tree(t->entries[i]);\n \t}\n \n-\tle = find_object(root->versions[0].sha1);\n+\tif (!(root->versions[0].mode & NO_DELTA))\n+\t\tle = find_object(root->versions[0].sha1);\n \tif (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n \t\tmktree(t, 0, &old_tree);\n \t\tlo.data = old_tree;\n@@ -1471,6 +1478,7 @@ static void tree_content_replace(\n {\n \tif (!S_ISDIR(mode))\n \t\tdie(\"Root cannot be a non-directory\");\n+\thashclr(root->versions[0].sha1);\n \thashcpy(root->versions[1].sha1, sha1);\n \tif (root->tree)\n \t\trelease_tree_content_recursive(root->tree);\n@@ -1515,6 +1523,23 @@ static int tree_content_set(\n \t\t\t\tif (e->tree)\n \t\t\t\t\trelease_tree_content_recursive(e->tree);\n \t\t\t\te->tree = subtree;\n+\n+\t\t\t\t/*\n+\t\t\t\t * We need to leave e->versions[0].sha1 alone\n+\t\t\t\t * to avoid modifying the preimage tree used\n+\t\t\t\t * when writing out the parent directory.\n+\t\t\t\t * But after replacing the subdir with a\n+\t\t\t\t * completely different one, it's not a good\n+\t\t\t\t * delta base any more, and besides, we've\n+\t\t\t\t * thrown away the tree entries needed to\n+\t\t\t\t * make a delta against it.\n+\t\t\t\t *\n+\t\t\t\t * So let's just explicitly disable deltas\n+\t\t\t\t * for the subtree.\n+\t\t\t\t */\n+\t\t\t\tif (S_ISDIR(e->versions[0].mode))\n+\t\t\t\t\te->versions[0].mode |= NO_DELTA;\n+\n \t\t\t\thashclr(root->versions[1].sha1);\n \t\t\t\treturn 1;\n \t\t\t}\n@@ -2929,7 +2954,7 @@ static void print_ls(int mode, const unsigned char *sha1, const char *path)\n \t\t/* mode SP type SP object_name TAB path LF */\n \t\tstrbuf_reset(&line);\n \t\tstrbuf_addf(&line, \"%06o %s %s\\t\",\n-\t\t\t\tmode, type, sha1_to_hex(sha1));\n+\t\t\t\tmode & ~NO_DELTA, type, sha1_to_hex(sha1));\n \t\tquote_c_style(path, &line, NULL, 0);\n \t\tstrbuf_addch(&line, '\\n');\n \t}\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex e2b94b5..106e3f3 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -765,7 +765,7 @@ g/b/f\n g/b/h\n EOF\n \n-test_expect_failure \\\n+test_expect_success \\\n     'L: nested tree copy does not corrupt deltas' \\\n \t'git fast-import <input &&\n \tgit ls-tree L2 g/b/ >tmp &&\n-- \n1.7.3.4\n"},{"id":"173905","messageId":"20110820010901.GA2512@elie.sbx02827.chicail.wayport.net","threadId":"28075","inReplyTo":"1313346744-30340-3-git-send-email-divanorama@gmail.com","subject":"[PATCH v3] fast-import: do not write bad delta for replaced subtrees","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-08-20T01:09:02Z","receivedAt":"2011-08-20T01:09:02Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dmitry Ivankov wrote:\n\n> To produce deltas for tree objects fast-import tracks two versions\n> of tree's entries - base and current one. Base version stands both\n> for a delta base of this tree, and for a entry inside a delta base\n> of a parent tree. So care should be taken to keep it in sync.\n\nThanks again for this.  Abusing (S_ISDIR | S_ISUID) still leaves a bad\ntaste in my mouth, but after your description I'm convinced that\nbehavior-wise it's the right thing to do.\n\nI'm thinking of queueing the following to svn-fe-maint.  If there's\nsomething wrong with it, I'd be happy to hear that now; otherwise,\nwe can put fixes on top.  In other words, \"please speak now or forever\nhold your peace\".  Changes since v2:\n\n - clarify description\n\n - some tiny style nitpicks in the code and test\n\n - made a pass through checking uses of \"mode\" to make sure we are\n   scrubbing out the S_ISUID bit before passing it to code that is not\n   aware of that bit.\n\n   The result is a few assert() calls to document those cases that\n   required a second's thought and some extra scrubbing in tecmp0()\n   when passing the mode to base_name_compare.  Although the latter is\n   not needed and base_name_compare() only pays attention to the\n   S_IFDIR bit, it seems best to stick to the expected interface and\n   pass a real mode.\n\n - take care of a missed case where NO_DELTA was not being set:\n\n\tcreate branch \"basis\":\n\n\t\tM 100644 inline dir/hello.c\n\t\tdata <<EOF\n\t\thello\n\t\tEOF\n\t\tC dir/hello.c unrelated\n\n\ton branch \"master\":\n\n\t\tfrom refs/heads/basis\n\t\tD dir\n\n\tcorrupt the subtree\n\n\t\tC unrelated dir/nothello.c\n\nThe patch has way too few tests.  Oh, well.\n\nBugs?  Improvements?\n\n-- >8 --\nSubject: fast-import: do not write bad delta for replaced subtrees\n\nTo produce deltas for tree objects, fast-import tracks two versions of\neach tree entry - a base and the current version. The base version on\na tree stands both for a delta base of this tree, and for a entry\ninside the delta base of the parent tree. So care needs to be taken to\nkeep them consistent.\n\nUnfortunately this all gets forgotten when replacing one subtree by\nanother using tree_content_set.  When writing an entry representing\nthe new subtree, it keeps the old base sha1, since it is needed by the\nparent tree.  But the new tree doesn't have the implied base version\nentries, and when it is time to write it to pack, git writes an\ninvalid delta that is declared to have one base (the old tree name)\nbut actually has another one (the new tree for an \"M\" command, or the\ntree's old base for an \"R\" or \"C\" command).\n\nHow to fix it?  Modifying the new subtree's entries to match the\ndeclared base would be expensive, since it requires reading the tree\ncorresponding to the declared base from the object db and recursively\nrewriting children's base versions to match.  Invalidating the parent\ntrees' bases would involve recursively walking up the tree and\ndisables deltas for each tree it touches, meaning a larger pack.\nLet's just mark the new tree as do-not-delta-me instead.  We abuse the\nsetuid bit in the base \"mode\" field for this purpose.\n\ntree_content_replace is in a similar predicament to tree_content_set,\nexcept that because it is only used to replace the root, just\ninvalidating the base sha1 there (instead of setting the no-delta bit)\nis fine.\n\nInitial hack by Jonathan, test and description by Dmitry.\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\n fast-import.c          |   55 ++++++++++++++++++++++++++++++++++++++++++-----\n t/t9300-fast-import.sh |   40 ++++++++++++++++++++++++++++++++++\n 2 files changed, 89 insertions(+), 6 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 65d65bf8..95919b63 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -170,6 +170,11 @@ Format of STDIN stream:\n #define DEPTH_BITS 13\n #define MAX_DEPTH ((1<<DEPTH_BITS)-1)\n \n+/*\n+ * We abuse the setuid bit on directories to mean \"do not delta\".\n+ */\n+#define NO_DELTA S_ISUID\n+\n struct object_entry {\n \tstruct pack_idx_entry idx;\n \tstruct object_entry *next;\n@@ -1380,9 +1385,12 @@ static int tecmp0 (const void *_a, const void *_b)\n {\n \tstruct tree_entry *a = *((struct tree_entry**)_a);\n \tstruct tree_entry *b = *((struct tree_entry**)_b);\n+\n \treturn base_name_compare(\n-\t\ta->name->str_dat, a->name->str_len, a->versions[0].mode,\n-\t\tb->name->str_dat, b->name->str_len, b->versions[0].mode);\n+\t\ta->name->str_dat, a->name->str_len,\n+\t\t\t\t\ta->versions[0].mode & ~NO_DELTA,\n+\t\tb->name->str_dat, b->name->str_len,\n+\t\t\t\t\tb->versions[0].mode & ~NO_DELTA);\n }\n \n static int tecmp1 (const void *_a, const void *_b)\n@@ -1405,6 +1413,14 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)\n \t\tqsort(t->entries,t->entry_count,sizeof(t->entries[0]),tecmp1);\n \n \tfor (i = 0; i < t->entry_count; i++) {\n+\t\t/*\n+\t\t * A hypothetical mode == (0 | NO_DELTA) would mean\n+\t\t * \"this version does not exist, and please don't\n+\t\t * make deltas against it when writing a tree object\n+\t\t * based on it\".  That is spelled as \"mode == 0\".\n+\t\t */\n+\t\tassert(t->entries[i]->versions[v].mode != NO_DELTA);\n+\n \t\tif (t->entries[i]->versions[v].mode)\n \t\t\tmaxlen += t->entries[i]->name->str_len + 34;\n \t}\n@@ -1415,8 +1431,9 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)\n \t\tstruct tree_entry *e = t->entries[i];\n \t\tif (!e->versions[v].mode)\n \t\t\tcontinue;\n-\t\tstrbuf_addf(b, \"%o %s%c\", (unsigned int)e->versions[v].mode,\n-\t\t\t\t\te->name->str_dat, '\\0');\n+\t\tstrbuf_addf(b, \"%o %s%c\",\n+\t\t\t(unsigned int)(e->versions[v].mode & ~NO_DELTA),\n+\t\t\te->name->str_dat, '\\0');\n \t\tstrbuf_add(b, e->versions[v].sha1, 20);\n \t}\n }\n@@ -1436,7 +1453,10 @@ static void store_tree(struct tree_entry *root)\n \t\t\tstore_tree(t->entries[i]);\n \t}\n \n-\tle = find_object(root->versions[0].sha1);\n+\tif (root->versions[0].mode & NO_DELTA)\n+\t\tle = NULL;\n+\telse\n+\t\tle = find_object(root->versions[0].sha1);\n \tif (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n \t\tmktree(t, 0, &old_tree);\n \t\tlo.data = old_tree;\n@@ -1470,6 +1490,7 @@ static void tree_content_replace(\n {\n \tif (!S_ISDIR(mode))\n \t\tdie(\"Root cannot be a non-directory\");\n+\thashclr(root->versions[0].sha1);\n \thashcpy(root->versions[1].sha1, sha1);\n \tif (root->tree)\n \t\trelease_tree_content_recursive(root->tree);\n@@ -1514,11 +1535,30 @@ static int tree_content_set(\n \t\t\t\tif (e->tree)\n \t\t\t\t\trelease_tree_content_recursive(e->tree);\n \t\t\t\te->tree = subtree;\n+\n+\t\t\t\t/*\n+\t\t\t\t * We need to leave e->versions[0].sha1 alone\n+\t\t\t\t * to avoid modifying the preimage tree used\n+\t\t\t\t * when writing out the parent directory.\n+\t\t\t\t * But after replacing the subdir with a\n+\t\t\t\t * completely different one, e->versions[0]\n+\t\t\t\t * is not a good delta base any more, and\n+\t\t\t\t * besides, we've thrown away the tree\n+\t\t\t\t * entries needed to make a delta against it.\n+\t\t\t\t *\n+\t\t\t\t * Let's just disable deltas when the time\n+\t\t\t\t * comes to write this subtree to pack.\n+\t\t\t\t */\n+\t\t\t\tif (S_ISDIR(e->versions[0].mode))\n+\t\t\t\t\te->versions[0].mode |= NO_DELTA;\n+\n \t\t\t\thashclr(root->versions[1].sha1);\n \t\t\t\treturn 1;\n \t\t\t}\n \t\t\tif (!S_ISDIR(e->versions[1].mode)) {\n \t\t\t\te->tree = new_tree_content(8);\n+\t\t\t\tif (S_ISDIR(e->versions[0].mode))\n+\t\t\t\t\te->versions[0].mode |= NO_DELTA;\n \t\t\t\te->versions[1].mode = S_IFDIR;\n \t\t\t}\n \t\t\tif (!e->tree)\n@@ -2918,6 +2958,9 @@ static void print_ls(int mode, const unsigned char *sha1, const char *path)\n \t\tS_ISDIR(mode) ? tree_type :\n \t\tblob_type;\n \n+\t/* NO_DELTA is only used with tree objects. */\n+\tassert(mode != NO_DELTA);\n+\n \tif (!mode) {\n \t\t/* missing SP path LF */\n \t\tstrbuf_reset(&line);\n@@ -2928,7 +2971,7 @@ static void print_ls(int mode, const unsigned char *sha1, const char *path)\n \t\t/* mode SP type SP object_name TAB path LF */\n \t\tstrbuf_reset(&line);\n \t\tstrbuf_addf(&line, \"%06o %s %s\\t\",\n-\t\t\t\tmode, type, sha1_to_hex(sha1));\n+\t\t\t\tmode & ~NO_DELTA, type, sha1_to_hex(sha1));\n \t\tquote_c_style(path, &line, NULL, 0);\n \t\tstrbuf_addch(&line, '\\n');\n \t}\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex 6b1ba6c8..180d357b 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -734,6 +734,46 @@ test_expect_success \\\n \t git diff-tree --abbrev --raw L^ L >output &&\n \t test_cmp expect output'\n \n+cat >input <<INPUT_END\n+blob\n+mark :1\n+data <<EOF\n+the data\n+EOF\n+\n+commit refs/heads/L2\n+committer C O Mitter <committer@example.com> 1112912473 -0700\n+data <<COMMIT\n+init L2\n+COMMIT\n+M 644 :1 a/b/c\n+M 644 :1 a/b/d\n+M 644 :1 a/e/f\n+\n+commit refs/heads/L2\n+committer C O Mitter <committer@example.com> 1112912473 -0700\n+data <<COMMIT\n+update L2\n+COMMIT\n+C a g\n+C a/e g/b\n+M 644 :1 g/b/h\n+INPUT_END\n+\n+cat <<EOF >expect\n+g/b/f\n+g/b/h\n+EOF\n+\n+test_expect_success \\\n+    'L: modifying a copied tree does not produce a corrupt pack' \\\n+\t'test_when_finished \"git update-ref -d refs/heads/L2\" &&\n+\tgit fast-import <input &&\n+\tgit ls-tree L2 g/b/ >tmp &&\n+\tcut -f 2 <tmp >actual &&\n+\ttest_cmp expect actual &&\n+\tgit fsck L2'\n+\n ###\n ### series M\n ###\n-- \n1.7.6\n"},{"id":"173912","messageId":"m262lspi0h.fsf@linux-m68k.org","threadId":"28075","inReplyTo":"20110820010901.GA2512@elie.sbx02827.chicail.wayport.net","subject":"Re: [PATCH v3] fast-import: do not write bad delta for replaced subtrees","fromName":"Andreas Schwab","fromEmail":"schwab@linux-m68k.org","sentAt":"2011-08-20T09:08:30Z","receivedAt":"2011-08-20T09:08:30Z","isPatch":true,"sender":{"key":"schwab@linux-m68k.org","avatar":"https://avatars.githubusercontent.com/u/2175493?v=4"},"body":"Jonathan Nieder <jrnieder@gmail.com> writes:\n\n> Thanks again for this.  Abusing (S_ISDIR | S_ISUID) still leaves a bad\n> taste in my mouth, but after your description I'm convinced that\n> behavior-wise it's the right thing to do.\n\n$ git grep S_ISUID\ncompat/mingw.h:#define S_ISUID 0\n\nAndreas.\n\n-- \nAndreas Schwab, schwab@linux-m68k.org\nGPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5\n\"And now for something completely different.\"\n"},{"id":"173918","messageId":"20110820154356.GB15864@elie.gateway.2wire.net","threadId":"28075","inReplyTo":"m262lspi0h.fsf@linux-m68k.org","subject":"Re: [PATCH v3] fast-import: do not write bad delta for replaced subtrees","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-08-20T15:43:56Z","receivedAt":"2011-08-20T15:43:56Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Andreas Schwab wrote:\n\n> $ git grep S_ISUID\n> compat/mingw.h:#define S_ISUID 0\n\nGood catch, thanks.  Fix below --- despite appearances, this \"mode\"\nfield is about tree objects in the repository and there is no need to\nmatch the current platform's file status conventions.\n\nAnother worrisome detail is that the patch changes the semantics of\ntree_entry.versions[0].mode (by introducing the NO_DELTA bit) without\nchanging its name.  It would be safer to rename it to te_mode or\nsomething.\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\ndiff --git i/fast-import.c w/fast-import.c\nindex 95919b63..45e2128a 100644\n--- i/fast-import.c\n+++ w/fast-import.c\n@@ -173,7 +173,7 @@ Format of STDIN stream:\n /*\n  * We abuse the setuid bit on directories to mean \"do not delta\".\n  */\n-#define NO_DELTA S_ISUID\n+#define NO_DELTA 04000\n \n struct object_entry {\n \tstruct pack_idx_entry idx;\n-- \n"},{"id":"173921","messageId":"1313860946-1596-1-git-send-email-divanorama@gmail.com","threadId":"28075","inReplyTo":"20110820154356.GB15864@elie.gateway.2wire.net","subject":"[PATCH v4] fast-import: do not write bad delta for replaced subtrees","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-20T17:22:26Z","receivedAt":"2011-08-20T17:22:26Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"How about adding a new bit field \"no_delta\" instead? The patch is\nsmaller this way. Also could 04000 theoretically be S_IFDIR on some\nplatform?\n\nChanges:\n- switch to a separate no_delta bit in tree_entry, don't assume that it\n  is used only for trees. Could be useful for blobs too once their delta\n  base logic changes (now it's just delta against blob that was stored\n  just before the current one)\n- when setting no_delta = 1 don't check for S_ISDIR(versions[0].mode),\n  this is a redundant check and logic duplication. Who knows, maybe some\n  day we'll want to delta a tree against blob. :)\n- removed the asserts on mode, as now \"mode\" meaning isn't changed\n- removed the duplicated signed-of-by :)\n\n-- >8 --\nSubject: fast-import: do not write bad delta for replaced subtrees\n\nTo produce deltas for tree objects, fast-import tracks two versions of\neach tree entry - a base and the current version. The base version on\na tree stands both for a delta base of this tree, and for a entry\ninside the delta base of the parent tree. So care needs to be taken to\nkeep them consistent.\n\nUnfortunately this all gets forgotten when replacing one subtree by\nanother using tree_content_set.  When writing an entry representing\nthe new subtree, it keeps the old base sha1, since it is needed by the\nparent tree.  But the new tree doesn't have the implied base version\nentries, and when it is time to write it to pack, git writes an\ninvalid delta that is declared to have one base (the old tree name)\nbut actually has another one (the new tree for an \"M\" command, or the\ntree's old base for an \"R\" or \"C\" command).\n\nHow to fix it?  Modifying the new subtree's entries to match the\ndeclared base would be expensive, since it requires reading the tree\ncorresponding to the declared base from the object db and recursively\nrewriting children's base versions to match.  Invalidating the parent\ntrees' bases would involve recursively walking up the tree and\ndisables deltas for each tree it touches, meaning a larger pack.\nLet's just mark the new tree as do-not-delta-me instead. Add a new bit\nfor tree_entry named no_delta. It is set to 1 when subtree is replaced\nand reset back to 0 when we set a new legal delta base, that is when\ne->versions[0] is changed.\n\ntree_content_replace is in a similar predicament to tree_content_set,\nexcept that because it is only used to replace the root, just\ninvalidating the base sha1 there (instead of setting the no-delta bit)\nis fine.\n\nInitial hack by Jonathan, test and description by Dmitry.\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\nSigned-off-by: Dmitry Ivankov <divanorama@gmail.com>\n---\n fast-import.c          |   27 ++++++++++++++++++++++++++-\n t/t9300-fast-import.sh |   40 ++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 66 insertions(+), 1 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 7cc2262..3bae498 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -221,6 +221,7 @@ struct tree_entry {\n \t\tuint16_t mode;\n \t\tunsigned char sha1[20];\n \t} versions[2];\n+\tunsigned no_delta : 1;\n };\n \n struct tree_content {\n@@ -1368,6 +1369,7 @@ static void load_tree(struct tree_entry *root)\n \t\tif (!c)\n \t\t\tdie(\"Corrupt mode in %s\", sha1_to_hex(sha1));\n \t\te->versions[0].mode = e->versions[1].mode;\n+\t\te->no_delta = 0;\n \t\te->name = to_atom(c, strlen(c));\n \t\tc += e->name->str_len + 1;\n \t\thashcpy(e->versions[0].sha1, (unsigned char *)c);\n@@ -1437,7 +1439,10 @@ static void store_tree(struct tree_entry *root)\n \t\t\tstore_tree(t->entries[i]);\n \t}\n \n-\tle = find_object(root->versions[0].sha1);\n+\tif (root->no_delta)\n+\t\tle = NULL;\n+\telse\n+\t\tle = find_object(root->versions[0].sha1);\n \tif (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n \t\tmktree(t, 0, &old_tree);\n \t\tlo.data = old_tree;\n@@ -1453,6 +1458,7 @@ static void store_tree(struct tree_entry *root)\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\te->no_delta = 0;\n \t\t\thashcpy(e->versions[0].sha1, e->versions[1].sha1);\n \t\t\tt->entries[j++] = e;\n \t\t} else {\n@@ -1471,6 +1477,7 @@ static void tree_content_replace(\n {\n \tif (!S_ISDIR(mode))\n \t\tdie(\"Root cannot be a non-directory\");\n+\thashclr(root->versions[0].sha1);\n \thashcpy(root->versions[1].sha1, sha1);\n \tif (root->tree)\n \t\trelease_tree_content_recursive(root->tree);\n@@ -1515,11 +1522,28 @@ static int tree_content_set(\n \t\t\t\tif (e->tree)\n \t\t\t\t\trelease_tree_content_recursive(e->tree);\n \t\t\t\te->tree = subtree;\n+\n+\t\t\t\t/*\n+\t\t\t\t * We need to leave e->versions[0].sha1 alone\n+\t\t\t\t * to avoid modifying the preimage tree used\n+\t\t\t\t * when writing out the parent directory.\n+\t\t\t\t * But after replacing the subdir with a\n+\t\t\t\t * completely different one, e->versions[0]\n+\t\t\t\t * is not a good delta base any more, and\n+\t\t\t\t * besides, we've thrown away the tree\n+\t\t\t\t * entries needed to make a delta against it.\n+\t\t\t\t *\n+\t\t\t\t * Let's just disable deltas when the time\n+\t\t\t\t * comes to write this subtree to pack.\n+\t\t\t\t */\n+\t\t\t\te->no_delta = 1;\n+\n \t\t\t\thashclr(root->versions[1].sha1);\n \t\t\t\treturn 1;\n \t\t\t}\n \t\t\tif (!S_ISDIR(e->versions[1].mode)) {\n \t\t\t\te->tree = new_tree_content(8);\n+\t\t\t\te->no_delta = 1;\n \t\t\t\te->versions[1].mode = S_IFDIR;\n \t\t\t}\n \t\t\tif (!e->tree)\n@@ -1537,6 +1561,7 @@ static int tree_content_set(\n \te = new_tree_entry();\n \te->name = to_atom(p, n);\n \te->versions[0].mode = 0;\n+\te->no_delta = 0;\n \thashclr(e->versions[0].sha1);\n \tt->entries[t->entry_count++] = e;\n \tif (slash1) {\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex f256475..04fa70d 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -734,6 +734,46 @@ test_expect_success \\\n \t git diff-tree --abbrev --raw L^ L >output &&\n \t test_cmp expect output'\n \n+cat >input <<INPUT_END\n+blob\n+mark :1\n+data <<EOF\n+the data\n+EOF\n+\n+commit refs/heads/L2\n+committer C O Mitter <committer@example.com> 1112912473 -0700\n+data <<COMMIT\n+init L2\n+COMMIT\n+M 644 :1 a/b/c\n+M 644 :1 a/b/d\n+M 644 :1 a/e/f\n+\n+commit refs/heads/L2\n+committer C O Mitter <committer@example.com> 1112912473 -0700\n+data <<COMMIT\n+update L2\n+COMMIT\n+C a g\n+C a/e g/b\n+M 644 :1 g/b/h\n+INPUT_END\n+\n+cat <<EOF >expect\n+g/b/f\n+g/b/h\n+EOF\n+\n+test_expect_success \\\n+    'L: modifying a copied tree does not produce a corrupt pack' \\\n+\t'test_when_finished \"git update-ref -d refs/heads/L2\" &&\n+\tgit fast-import <input &&\n+\tgit ls-tree L2 g/b/ >tmp &&\n+\tcut -f 2 <tmp >actual &&\n+\ttest_cmp expect actual &&\n+\tgit fsck L2'\n+\n ###\n ### series M\n ###\n-- \n1.7.3.4\n"},{"id":"173922","messageId":"20110820174812.GD15864@elie.gateway.2wire.net","threadId":"28075","inReplyTo":"1313860946-1596-1-git-send-email-divanorama@gmail.com","subject":"Re: [PATCH v4] fast-import: do not write bad delta for replaced subtrees","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-08-20T17:48:12Z","receivedAt":"2011-08-20T17:48:12Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dmitry Ivankov wrote:\n\n> How about adding a new bit field \"no_delta\" instead?\n\nCurrently the layout of \"struct tree_entry_ms\" is:\n\n\tuint16_t mode;\t\t\ttwo bytes\n\tunsigned char sha1[20]\t\t20 bytes\n\nwhich adds up to 22 bytes.  Here is \"struct tree_entry\":\n\n\tstruct tree_entry *tree;\t\tone machine word\n\tstruct atom_str *name;\t\t\tone machine word\n\tstruct tree_entry_ms versions[2];\t44 bytes\n\nAlthough it only looks like it adds one byte per tree entry, in\npractice I suspect your patch adds four.  Is that worth it?  (The\nanswer might be yes.  I'm not sure.)\n\n> The patch is\n> smaller this way. Also could 04000 theoretically be S_IFDIR on some\n> platform?\n\nNo, these modes are part of the format of objects as written on disk\nand over the wire, so when we meet a platform with S_IFDIR != 040000,\nthere will have to be bigger changes (to distinguish between the\nplatform's idea of file status and git's idea of modes).\n\n> - switch to a separate no_delta bit in tree_entry\n\nIf it doesn't cost too much, this is a good idea.\n\n> - when setting no_delta = 1 don't check for S_ISDIR(versions[0].mode),\n>   this is a redundant check and logic duplication. Who knows, maybe some\n>   day we'll want to delta a tree against blob. :)\n\nWhy?  When versions[0] is not a tree, the hack is not needed, since\nversions[0].mode and versions[0].sha1 accurately describe the delta\nbase and are not inconsistent with anything.\n\nThanks, that was helpful.\n"},{"id":"173925","messageId":"CA+gfSn_G0Q8=NsLr_Qku+oHwgkzBXajHpebLVT2SG4YDUUZD-g@mail.gmail.com","threadId":"28075","inReplyTo":"20110820174812.GD15864@elie.gateway.2wire.net","subject":"Re: [PATCH v4] fast-import: do not write bad delta for replaced subtrees","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-20T18:28:34Z","receivedAt":"2011-08-20T18:28:34Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"On Sat, Aug 20, 2011 at 11:48 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n> Dmitry Ivankov wrote:\n>\n>> How about adding a new bit field \"no_delta\" instead?\n>\n> Currently the layout of \"struct tree_entry_ms\" is:\n>\n>        uint16_t mode;                  two bytes\n>        unsigned char sha1[20]          20 bytes\n>\n> which adds up to 22 bytes.  Here is \"struct tree_entry\":\n>\n>        struct tree_entry *tree;                one machine word\n>        struct atom_str *name;                  one machine word\n>        struct tree_entry_ms versions[2];       44 bytes\n>\n> Although it only looks like it adds one byte per tree entry, in\n> practice I suspect your patch adds four.  Is that worth it?  (The\n> answer might be yes.  I'm not sure.)\nHm, we can make mode 1 byte in fast-import (only 8 values are used).\nBut not in this patch of course.\n\n>\n>> The patch is\n>> smaller this way. Also could 04000 theoretically be S_IFDIR on some\n>> platform?\n>\n> No, these modes are part of the format of objects as written on disk\n> and over the wire, so when we meet a platform with S_IFDIR != 040000,\n> there will have to be bigger changes (to distinguish between the\n> platform's idea of file status and git's idea of modes).\n>\n>> - switch to a separate no_delta bit in tree_entry\n>\n> If it doesn't cost too much, this is a good idea.\n>\n>> - when setting no_delta = 1 don't check for S_ISDIR(versions[0].mode),\n>>   this is a redundant check and logic duplication. Who knows, maybe some\n>>   day we'll want to delta a tree against blob. :)\n>\n> Why?  When versions[0] is not a tree, the hack is not needed, since\n> versions[0].mode and versions[0].sha1 accurately describe the delta\n> base and are not inconsistent with anything.\nOh, right you are. The new check and one in store_tree look the same\nbut the purpose differs.\n\n>\n> Thanks, that was helpful.\n>\n"}]}