{"thread":{"id":"27767","subject":"long fast-import errors out \"failed to apply delta\"","startedAt":"2011-07-07T10:47:31Z","lastAt":"2011-07-28T11:24:06Z","messageCount":10,"participants":["Dmitry Ivankov","Jonathan Nieder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"170969","messageId":"CA+gfSn8jjptyv10iVimmfXpf6QHrR_3UpkRdd+Dv1M=KgORtGQ@mail.gmail.com","threadId":"27767","inReplyTo":null,"subject":"long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-07T10:47:31Z","receivedAt":"2011-07-07T10:47:31Z","isPatch":false,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"Hi,\n\nI'm getting a strange error from git-fast-import.\nTested on v1.7.5 and v1.7.6 on two machines (gentoo amd64 8gb ram,\n3-core amd cpu; gentoo x86 2gb ram, 1-core intel mobile cpu).\nThe crash is stable - same message, instruction and deepest function\n(patch_delta) parameters contents.\n\n$ git fast-import --quiet < big_dump\nfatal: failed to apply delta\nfast-import: dumping crash report to fast_import_crash_7700\n\nWhere big_dump is produced by svn-fe, 3.3Gb, 43404 sequential commits\n(in fact 43403, 43404th causes a crash in the middle) to a single\nbranch with a \"mark\" and \"progress\" commands for each commit.\nCrash report doesn't give much hints:\nThe last commands are\ncommit refs/heads/master\nmark :43404\ncommitter ...\ndata 53\n[a few \"ls ...\" & \"M 100644 ...\", one \"M 100755 ...\"]\n  ls :43402 incubator/directory/seda/trunk/impl/src/java/org/apache/seda/processor/RequestProcessorMonitorAdapter.java\n* M 100644 64d6fb598ba6b6a3f8418e62ea9bceb0cefe4481\nincubator/directory/seda/trunk/api/src/java/org/apache/seda/protocol/RequestProcessorMonitorAdapter.java\n\nThe failure is in sha1_file.c:unpack_delta_entry on unpacking\nsomething like depth=7 tree on the path to that file.\n\nAnd the failure comes from:\nvoid *patch_delta(const void *src_buf, unsigned long src_size,\n                  const void *delta_buf, unsigned long delta_size,\n                  unsigned long *dst_size)\n...\n        size = get_delta_hdr_size(&data, top);\n        if (size != src_size)\n                return NULL;\n\nWhere size is arount 590(don't remember, can gdb again if needed or it\ncan be extracted from the dumped delta_data), and src_size is 396. One\ncan inspect the parameters with a program at the bottom of this email.\n\nI tried to add a \"checkpoint\" command before the failing commit - no effect.\nAnd then I split the dump, imported commits that don't fail, with\n--export-marks, run fast-import --import-marks on the remaining commit\ndump and it didn't fail.\n\nThis looks strange to me.\nShouldn't checkpoint dump everything on the disk and have the same\neffect as splitting the stream?\nIt doesn't look like an interrupted read of object because src_size is\nalways the same.\n\nOn a split run there is no delta resolution that visually looks like\nthe problematic one, the one that suits most has different base_size,\ndelta_size, delta_data is completely different and src_datas have some\ncommon prefix of 14 bytes.\n\nAny advices on debugging this?\nI'll try valgrind for now.\n\n---\ntest-apply-delta.c:\n#include \"git-compat-util.h\"\n#include \"delta.h\"\n\nstatic const size_t base_size = 396;\nstatic const unsigned char base_data[397] =\n\"\\x31\\x30\\x30\\x36\\x34\\x34\\x20\\x48\\x61\\x6E\\x64\\x6C\\x65\\x72\\x54\\x79\\x70\\x65\\x45\\x6E\\x75\\x6D\\x2E\\x6A\\x61\\x76\\x61\\x0\\x9D\\xF4\\x1\\x98\\xF4\\x69\\x73\\x58\\x5\\xCD\\xC9\\x5E\\x19\\x8E\\xD0\\x9E\\x52\\x3D\\xA3\\x4A\\x31\\x30\\x30\\x37\\x35\\x35\\x20\\x49\\x6E\\x65\\x74\\x53\\x65\\x72\\x76\\x69\\x63\\x65\\x45\\x6E\\x74\\x72\\x79\\x2E\\x6A\\x61\\x76\\x61\\x0\\x2\\xA1\\x5\\x42\\x84\\xC5\\xD0\\x36\\xFB\\x20\\x4F\\x26\\x59\\x73\\x8F\\x8F\\x49\\x62\\x19\\x33\\x31\\x30\\x30\\x36\\x34\\x34\\x20\\x49\\x6E\\x65\\x74\\x53\\x65\\x72\\x76\\x69\\x63\\x65\\x50\\x72\\x6F\\x76\\x69\\x64\\x65\\x72\\x2E\\x6A\\x61\\x76\\x61\\x0\\xAC\\x24\\xC6\\x28\\x6\\x4\\xD5\\xC5\\x4F\\xF7\\xE0\\xBC\\x97\\x51\\xF4\\x55\\xE5\\x76\\x17\\x22\\x31\\x30\\x30\\x37\\x35\\x35\\x20\\x49\\x6E\\x65\\x74\\x53\\x65\\x72\\x76\\x69\\x63\\x65\\x73\\x44\\x61\\x74\\x61\\x62\\x61\\x73\\x65\\x2E\\x6A\\x61\\x76\\x61\\x0\\x6B\\x49\\x6F\\x2E\\x48\\xDC\\xF7\\xB7\\xD4\\x7D\\x2C\\xFE\\x97\\xC8\\xB\\xF1\\x39\\x8B\\x49\\xFA\\x\n 31\\x30\\x30\\x36\\x34\\x34\\x20\\x4D\\x61\\x6E\\x79\\x52\\x65\\x70\\x6C\\x79\\x48\\x61\\x6E\\x64\\x6C\\x65\\x72\\x2E\\x6A\\x61\\x76\\x61\\x0\\x50\\xA0\\x5B\\x3A\\x3\\xDF\\x8B\\x8C\\x6E\\xE4\\x79\\x3E\\xCA\\xF6\\x90\\x48\\xDB\\xF3\\xE9\\x1B\\x31\\x30\\x30\\x36\\x34\\x34\\x20\\x4E\\x6F\\x52\\x65\\x70\\x6C\\x79\\x48\\x61\\x6E\\x64\\x6C\\x65\\x72\\x2E\\x6A\\x61\\x76\\x61\\x0\\x2F\\x90\\x8D\\xC3\\x6D\\x8F\\x6F\\x49\\xCC\\x38\\xF\\x51\\x4C\\x9F\\xD8\\x2F\\x58\\x7D\\x54\\x41\\x31\\x30\\x30\\x36\\x34\\x34\\x20\\x52\\x65\\x71\\x75\\x65\\x73\\x74\\x48\\x61\\x6E\\x64\\x6C\\x65\\x72\\x2E\\x6A\\x61\\x76\\x61\\x0\\x13\\x66\\x67\\x26\\x2B\\x4F\\x84\\xBF\\x97\\xC0\\x4E\\x5F\\xEB\\x90\\x97\\xC0\\xF8\\x72\\x10\\x75\\x31\\x30\\x30\\x36\\x34\\x34\\x20\\x53\\x69\\x6E\\x67\\x6C\\x65\\x52\\x65\\x70\\x6C\\x79\\x48\\x61\\x6E\\x64\\x6C\\x65\\x72\\x2E\\x6A\\x61\\x76\\x61\\x0\\xD7\\x91\\xF0\\x9C\\x25\\xAE\\x1E\\x4F\\xD8\\x2\\x47\\x31\\x37\\x96\\x70\\x7E\\x5\\xCF\\x49\\x0\";\nstatic const size_t delta_size = 333;\nstatic const unsigned char delta_data[334] =\n\"\\xCF\\x4\\xCF\\x4\\x90\\x1C\\x14\\xC5\\x4F\\x12\\xA1\\x4\\xB1\\x2D\\xD6\\xFE\\xE9\\x44\\x66\\x9A\\xC\\x99\\x47\\x74\\xD7\\x6C\\xC7\\x91\\x30\\x1D\\x14\\xAF\\x4B\\x19\\xC8\\xA3\\x8B\\xCC\\x5C\\x3E\\x3C\\xDA\\xF6\\xC4\\x1C\\x78\\xF6\\x86\\xB3\\x74\\x56\\x91\\x61\\x20\\x14\\x97\\xE8\\x87\\xB8\\xE6\\x5A\\x45\\xB5\\x33\\x60\\xB4\\xBA\\x87\\x7F\\xD7\\x3B\\x80\\xA2\\x61\\x4B\\x91\\x95\\x21\\x14\\x5\\xF3\\xED\\xFD\\xED\\x9A\\x85\\xC2\\x12\\x23\\x76\\xCF\\xCC\\xF\\x41\\x39\\xAA\\xEB\\x8D\\xC1\\x91\\xCA\\x1D\\x14\\x18\\x9F\\xB7\\x73\\xF0\\x34\\x90\\xE4\\x50\\xA2\\xA\\x16\\x53\\x24\\x33\\xD\\x94\\x79\\xE6\\xDE\\x91\\xFB\\x1B\\x14\\x9B\\xC8\\x11\\x8\\x8F\\xA9\\x7A\\x3E\\xF7\\x16\\xE\\xDC\\x38\\x89\\xC2\\x4D\\x93\\x78\\x16\\xCE\\x93\\x2A\\x1\\x1B\\x14\\x83\\x13\\x6C\\xDD\\x24\\x42\\x7B\\x36\\x7\\x77\\x7D\\x60\\x28\\x4D\\xD1\\x80\\xDC\\xC9\\x27\\x94\\x93\\x59\\x1\\x1D\\x14\\x1A\\x9\\x4E\\x5E\\xEF\\x7\\x35\\x63\\xCD\\x71\\xE9\\x70\\xBD\\xF6\\xC0\\x27\\xEE\\x51\\x2C\\x29\\x93\\x8A\\x1\\x24\\x7F\\x49\\x6\n D\\x4B\\x33\\x55\\x49\\x95\\xC0\\x3D\\x38\\xDF\\xA3\\xF4\\x6D\\xBB\\x67\\x98\\xB\\xB9\\xC1\\x31\\x30\\x30\\x36\\x34\\x34\\x20\\x53\\x69\\x6E\\x67\\x6C\\x65\\x52\\x65\\x70\\x6C\\x79\\x48\\x61\\x6E\\x64\\x6C\\x65\\x72\\x2E\\x6A\\x61\\x76\\x61\\x0\\x95\\x72\\x6A\\xDA\\x7B\\x82\\xFF\\xFC\\xD3\\xD\\x61\\x63\\xFF\\x7A\\x46\\x34\\x8F\\x4\\xFC\\x13\\x31\\x30\\x30\\x37\\x35\\x35\\x20\\x54\\x72\\x61\\x6E\\x73\\x70\\x6F\\x72\\x74\\x54\\x79\\x70\\x65\\x45\\x6E\\x75\\x6D\\x2E\\x6A\\x61\\x76\\x61\\x0\\x11\\x6E\\x4C\\xF4\\xCB\\x97\\xCF\\x30\\x1B\\x93\\xB3\\xA7\\x92\\x4F\\xE9\\xB3\\x46\\xAF\\xE3\\x2\\x31\\x30\\x30\\x36\\x34\\x34\\x93\\x2D\\x2\\x22\";\n\nstatic long unsigned result_size;\nstatic long unsigned *result_size_p = &result_size;\nstatic void *result = NULL;\n\nint main() {\n\tresult = patch_delta(base_data, base_size, delta_data, delta_size,\nresult_size_p);\n\treturn result == NULL ? 1 : 0;\n}\n"},{"id":"170975","messageId":"CA+gfSn_zdMJ-J_5unUjUtqGzoRyy_Hy9Bo0MNh9Qt+zzGL8Q_A@mail.gmail.com","threadId":"27767","inReplyTo":"CA+gfSn8jjptyv10iVimmfXpf6QHrR_3UpkRdd+Dv1M=KgORtGQ@mail.gmail.com","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-07T12:24:07Z","receivedAt":"2011-07-07T12:24:07Z","isPatch":false,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"Small update: valgrind didn't detect anything.\n"},{"id":"171900","messageId":"CA+gfSn8C-nB2hSSRTqSu1N1Z-b8ctRsVmUGAjLXTW0du_W3EQw@mail.gmail.com","threadId":"27767","inReplyTo":"CA+gfSn8jjptyv10iVimmfXpf6QHrR_3UpkRdd+Dv1M=KgORtGQ@mail.gmail.com","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-23T20:34:20Z","receivedAt":"2011-07-23T20:34:20Z","isPatch":false,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"+people contributed to the related parts of fast-import.c\n\nHi!\n\nI did more tests and investigations. (one can safely jump over next 2\nparagraphs)\nThere is a problem in fast-import, triggered on long svn-fe produced\nimports (10k..80k commits depending on the svn repo history, in my\ntests at least). fast-imports sometimes writes off a tree object with\nwrong sha1. It goes silent unless it tries to read these objects for\nlater revisions (via ls command) and \"crashes\", or unless fsck is run\nto find sha1 mismatches.\n\nThis seems to be a old bug. Due to the content of my fast-import\nstreams, I need cat-blob and ls commands (once the import stream is\nsniffed these can be ignored) and more importantly 334fba656b50c9..\n\"Teach fast-import to import subtrees named by tree id\" 30 Jun 2010\nfor  \"M 040000 <tree id> pathname\" commands. The earliest git version\nI've tested so far is v1.6.0.6-7-g3d1d81e Jan 2009 + dummy cat-blob\nand ls + 334fba656b50c9..\n\nSo, how do I currently reproduce it.\nImport gcc svn repository with svn-fe up to r15507 - fine. (1.9G\nfast-import stream, 3min to import, 1min to fsck)\nImport up to r15508 - fine, but fsck finds a sha1 mismatch in a tree object.\nStrip r15508 to a three commands:\n\n..commit header..\nls :14842 branches/gcc3/gcc/config\nM 040000 fbc83f80e9516c831918dff149058cba38a2e5f1 tags/egcs_ss_970917/gcc/config\nls :15459 trunk/gcc/config/alpha\nM 040000 9ffe84c346eec93b523d95ce642b54d54d23109c\ntags/egcs_ss_970917/gcc/config/alpha\nls \"tags/egcs_ss_970917/gcc/config/alpha\"\nD tags/egcs_ss_970917/gcc/config/alpha/vms-tramp.asm\n\nSo here we set a directory with one old tree, then set it's child with\nanother old tree, and then delete a file in the child. The broken tree\nis the resulting tree for that child. sha1 written to the pack matches\nthe intent (the second M + D) while the content is wrong (matches the\nfirst M/subdir + D) - the second M command is partially lost.\n\nIf a checkpoint command is added before the last commit there is no\nsha1 mismatch. I haven't yet found a small fast-import stream with\nthis bug, but it is a definetely a logic bug somewhere in fast-import.\nI randomly changed pool sizes (didn't touch packfile settings yet),\nrun valgrind, slightly modified the stream many times, tested a bunch\nof different git versions on two machines - the bug is stable.\n\nAny ideas? How is it possible at all that the tree's sha1 and content\ndiverge, and moreover this is unnoticed by fast-import and a broken\npackfile is produced?\n\nOn Thu, Jul 7, 2011 at 4:47 PM, Dmitry Ivankov <divanorama@gmail.com> wrote:\n> Hi,\n>\n> I'm getting a strange error from git-fast-import.\n> Tested on v1.7.5 and v1.7.6 on two machines (gentoo amd64 8gb ram,\n> 3-core amd cpu; gentoo x86 2gb ram, 1-core intel mobile cpu).\n> The crash is stable - same message, instruction and deepest function\n> (patch_delta) parameters contents.\n>\n> $ git fast-import --quiet < big_dump\n> fatal: failed to apply delta\n> fast-import: dumping crash report to fast_import_crash_7700\n[skipped the details]\n"},{"id":"172054","messageId":"CA+gfSn8m=_vd91Xe5EnFXUvZnuJf-yUE6H7FU+ak8S8a+NtCjA@mail.gmail.com","threadId":"27767","inReplyTo":"CA+gfSn8C-nB2hSSRTqSu1N1Z-b8ctRsVmUGAjLXTW0du_W3EQw@mail.gmail.com","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-26T11:46:54Z","receivedAt":"2011-07-26T11:46:54Z","isPatch":false,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"Hi,\n\nI've found where the bug comes from, but not yet understand the delta\nlogic in fast-import.c enough to fix it properly or to create a small testcase.\nThe problem is with delta coding a tree change, e->versions[0].sha1 and\ne->tree->..->versions[0].sha1 diverge, the former corresponds to an older\nstate. When doing delta coding  we call mktree(t, 0, oldtree) that reads from\nour in-memory e->tree structure, get the correct delta with the produced, the\ndata sha1 is also correct, but e->versions[0].sha1 is written to the packfile\nas a delta base and it is wrong. When this object is unpacked by git delta\nis applied to wrong base and hence the sha1 mismatch.\n\n1) Do we need to delta code trees?\n2) Was it supposed to work, or only blob deltas were meant to work?\n3) Is this breakage specific to tags/v1.7.3-rc0~75^2 \"Teach\nfast-import to import subtrees named by tree id\" 30 Jun 2010 (allowing\nM 040000 <tree id> pathname)?\n\nThe simple fix is not to delta-code tree in store_tree():\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 9e8d186..129f1c7 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1425,8 +1425,6 @@ static void store_tree(struct tree_entry *root)\n {\n        struct tree_content *t = root->tree;\n        unsigned int i, j, del;\n-       struct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };\n-       struct object_entry *le;\n\n        if (!is_null_sha1(root->versions[1].sha1))\n                return;\n@@ -1436,18 +1434,10 @@ static void store_tree(struct tree_entry *root)\n                        store_tree(t->entries[i]);\n        }\n\n-       le = find_object(root->versions[0].sha1);\n-       if (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {\n-               mktree(t, 0, &old_tree);\n-               lo.data = old_tree;\n-               lo.offset = le->idx.offset;\n-               lo.depth = t->delta_depth;\n-       }\n-\n        mktree(t, 1, &new_tree);\n-       store_object(OBJ_TREE, &new_tree, &lo, root->versions[1].sha1, 0);\n+       store_object(OBJ_TREE, &new_tree, NULL, root->versions[1].sha1, 0);\n\n-       t->delta_depth = lo.depth;\n+       t->delta_depth = 0;\n        for (i = 0, j = 0, del = 0; i < t->entry_count; i++) {\n                struct tree_entry *e = t->entries[i];\n                if (e->versions[1].mode) {\n\nThe harder fix is to try to keep e->versions[0].sha1 for trees correct.\nThat looks like that it should match mktree(v=0), and it uses\nversions[0].sha1 of child entries. Once a version[0].sha1 changes all\nparents should clear their versions[0].sha1 (is it right?). And also in\nload_tree(), child entries versions[0].sha1 should be set (its it right?)\nfrom parent base object. No patch for this case.\n\nAssuming that trees delta coding breaks only when we do\nM 040000 sha1 some/path\nand only that tree's data gets invalid, we can do this patch:\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 9e8d186..85c711c 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1514,6 +1514,9 @@ static int tree_content_set(\n                                if (e->tree)\n                                        release_tree_content_recursive(e->tree);\n                                e->tree = subtree;\n+                               if (S_ISDIR(mode)) {\n+                                       hashclr(e->versions[0].sha1);\n+                               }\n                                hashclr(root->versions[1].sha1);\n                                return 1;\n                        }\n\nBoth patches seem to fix the bug, at least on one large testcase I'm testing it.\nBut first of all a small test is needed, it looks very likely that\nthere exists one.\nAnd then, of course, a proper fix is needed.\n\nI'll leave a short description of the setup for a reference.\n\n> So, how do I currently reproduce it.\n> Import gcc svn repository with svn-fe up to r15507 - fine. (1.9G\n> fast-import stream, 3min to import, 1min to fsck)\n> Import up to r15508 - fine, but fsck finds a sha1 mismatch in a tree object.\n> Strip r15508 to a three commands:\n>\n> ..commit header..\n> ls :14842 branches/gcc3/gcc/config\n> M 040000 fbc83f80e9516c831918dff149058cba38a2e5f1 tags/egcs_ss_970917/gcc/config\n> ls :15459 trunk/gcc/config/alpha\n> M 040000 9ffe84c346eec93b523d95ce642b54d54d23109c\n> tags/egcs_ss_970917/gcc/config/alpha\n> ls \"tags/egcs_ss_970917/gcc/config/alpha\"\n> D tags/egcs_ss_970917/gcc/config/alpha/vms-tramp.asm\n>\n> So here we set a directory with one old tree, then set it's child with\n> another old tree, and then delete a file in the child. The broken tree\n> is the resulting tree for that child. sha1 written to the pack matches\n> the intent (the second M + D) while the content is wrong (matches the\n> first M/subdir + D) - the second M command is partially lost.\n"},{"id":"172086","messageId":"20110726165858.GA2334@elie.dc0b.debconf.org","threadId":"27767","inReplyTo":"CA+gfSn8m=_vd91Xe5EnFXUvZnuJf-yUE6H7FU+ak8S8a+NtCjA@mail.gmail.com","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-26T16:58:58Z","receivedAt":"2011-07-26T16:58:58Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi Dmitry,\n\nDmitry Ivankov wrote:\n\n> 3) Is this breakage specific to tags/v1.7.3-rc0~75^2 \"Teach\n> fast-import to import subtrees named by tree id\" 30 Jun 2010 (allowing\n> M 040000 <tree id> pathname)?\n\nProbably. :)\n\n> The harder fix is to try to keep e->versions[0].sha1 for trees correct.\n\nContext for those who don't remember all the details:\n\nWhen first introduced, \"struct tree_entry\" was very simple: a mode, a\nfilename, and:\n\n - for regular objects and symlinks, a blob object name representing\n   its content;\n\n - for subdirectories, a pointer to \"struct tree_content\" listing its\n   contents, along with an _optional_ cached tree object name.\n\nWhen modifying a tree entry, fast-import would walk through the path\nto it and invalidate the cached tree names at each step.  Shawn wrote:\n\n\tCurrently trees and commits aren't being deltafied when written to\n\tthe pack and branch reloading from the current pack doesn't work,\n\tso at most 5 branches can be worked with at any one time.\n\nbut the advantage was that it was very simple.  Later, delta\ncompression arrived:\n\n\tcommit 4cabf858\n\tAuthor: Shawn O. Pearce <spearce@spearce.org>\n\tDate:   Mon Aug 28 12:22:50 2006 -0400\n\n\t    Implemented tree delta compression in fast-import.\n\n\t    We now store for every tree entry two modes and two sha1 values;\n\t    the base (aka \"version 0\") and the current/new (aka \"version 1\").\n\t    When we generate a tree object we also regenerate the prior version\n\t    object and use that as our base object for a delta.  This strategy\n\t    saves a significant amount of memory as we can continue to use the\n\t    atom pool for file/directory names and only increases each tree\n\t    entry by an additional 24 bytes of memory.\n\nIn other words, this commit introduced a \"prior\" mode and tree or blob\nname to give the pack-writing machinery a hint about what to delta\nagainst.\n\nWith that in mind, it seems very weird that the version 0 tree would\never be changed and need to have its object name invalidated.  Perhaps\nwe are releasing some memory too early and it is getting clobbered?\nUnless I am missing something, the patch\n\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -1514,6 +1514,9 @@ static int tree_content_set(\n>                                 if (e->tree)\n>                                         release_tree_content_recursive(e->tree);\n>                                 e->tree = subtree;\n> +                               if (S_ISDIR(mode)) {\n> +                                       hashclr(e->versions[0].sha1);\n> +                               }\n>                                 hashclr(root->versions[1].sha1);\n>                                 return 1;\n\njust disables deltas for trees that have been modified by a \"M 040000\"\ncommand, so it feels more like a workaround than a fundamental fix.\n\nCould you save the svn-fe output (e.g., by introducing \"tee\" in the\nmiddle of the \"svn-fe | fast-import\" pipeline) and put it up\nsomewhere online?  This would also be a good starting point for coming\nup with a reduced testcase.\n\nHope that helps,\nJonathan\n"},{"id":"172087","messageId":"CA+gfSn-ZhqXfTELg_LfMJhMW7L7GVBoRTwZO_+QYntLrh+rk0Q@mail.gmail.com","threadId":"27767","inReplyTo":"20110726165858.GA2334@elie.dc0b.debconf.org","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-26T18:22:26Z","receivedAt":"2011-07-26T18:22:26Z","isPatch":false,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"Hi,\n\nOn Tue, Jul 26, 2011 at 10:58 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n> Hi Dmitry,\n>\n> Dmitry Ivankov wrote:\n>\n>> 3) Is this breakage specific to tags/v1.7.3-rc0~75^2 \"Teach\n>> fast-import to import subtrees named by tree id\" 30 Jun 2010 (allowing\n>> M 040000 <tree id> pathname)?\n>\n> Probably. :)\n>\n>> The harder fix is to try to keep e->versions[0].sha1 for trees correct.\n>\n> Context for those who don't remember all the details:\n>\n> When first introduced, \"struct tree_entry\" was very simple: a mode, a\n> filename, and:\n>\n>  - for regular objects and symlinks, a blob object name representing\n>   its content;\n>\n>  - for subdirectories, a pointer to \"struct tree_content\" listing its\n>   contents, along with an _optional_ cached tree object name.\n>\n> When modifying a tree entry, fast-import would walk through the path\n> to it and invalidate the cached tree names at each step.  Shawn wrote:\n>\n>        Currently trees and commits aren't being deltafied when written to\n>        the pack and branch reloading from the current pack doesn't work,\n>        so at most 5 branches can be worked with at any one time.\n>\n> but the advantage was that it was very simple.  Later, delta\n> compression arrived:\n>\n>        commit 4cabf858\n>        Author: Shawn O. Pearce <spearce@spearce.org>\n>        Date:   Mon Aug 28 12:22:50 2006 -0400\n>\n>            Implemented tree delta compression in fast-import.\n>\n>            We now store for every tree entry two modes and two sha1 values;\n>            the base (aka \"version 0\") and the current/new (aka \"version 1\").\n>            When we generate a tree object we also regenerate the prior version\n>            object and use that as our base object for a delta.  This strategy\n>            saves a significant amount of memory as we can continue to use the\n>            atom pool for file/directory names and only increases each tree\n>            entry by an additional 24 bytes of memory.\n>\n> In other words, this commit introduced a \"prior\" mode and tree or blob\n> name to give the pack-writing machinery a hint about what to delta\n> against.\n>\n> With that in mind, it seems very weird that the version 0 tree would\n> ever be changed and need to have its object name invalidated.\n\nWell, if we'd read the actual prior contents via sha1-lookup, no\ninvalidation would be needed,\nwe can create delta with any base after all.\nBut we use mktree(v=0) to collect versions[0].sha1 of entries with\n(mode != 0) as a content.\nI think I almost got it now. When we tree_content_set by sha1 (we use\nsubtree = NULL) and\nthat tree had some versions[0].sha1, we reset it's ->tree to NULL\nloosing the old sha1's of\nthe entries. Later we traverse there and load_tree that NULL, setting\nthe entries with\nversions[0].sha1 = versions[1].sha1 = sha1's of new/current tree entries.\n\nSo looks like load_tree should restore versions[0].sha1's IF the prior\nobject was a tree.\nI've tried this approach with merging two trees, but my rough patch is\nbloated and crashes.\n\nA bit slower one is to do sha1 lookups for the delta base trees.\n\n>  Perhaps\n> we are releasing some memory too early and it is getting clobbered?\n> Unless I am missing something, the patch\n>\n>> --- a/fast-import.c\n>> +++ b/fast-import.c\n>> @@ -1514,6 +1514,9 @@ static int tree_content_set(\n>>                                 if (e->tree)\n>>                                         release_tree_content_recursive(e->tree);\n>>                                 e->tree = subtree;\n>> +                               if (S_ISDIR(mode)) {\n>> +                                       hashclr(e->versions[0].sha1);\n>> +                               }\n>>                                 hashclr(root->versions[1].sha1);\n>>                                 return 1;\n>\n> just disables deltas for trees that have been modified by a \"M 040000\"\n> command, so it feels more like a workaround than a fundamental fix.\nRight, I can't even say I understand in full what does it change.\n\n> Could you save the svn-fe output (e.g., by introducing \"tee\" in the\n> middle of the \"svn-fe | fast-import\" pipeline) and put it up\n> somewhere online?  This would also be a good starting point for coming\n> up with a reduced testcase.\nIt's 1.9G uncompressed, 0.7G lzo-compressed. Will setup a ftp or\ntorrent seed a bit later.\n\n>\n> Hope that helps,\n> Jonathan\n>\n"},{"id":"172091","messageId":"20110726185504.GA2398@elie.dc0b.debconf.org","threadId":"27767","inReplyTo":"CA+gfSn-ZhqXfTELg_LfMJhMW7L7GVBoRTwZO_+QYntLrh+rk0Q@mail.gmail.com","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-26T18:55:04Z","receivedAt":"2011-07-26T18:55:04Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dmitry Ivankov wrote:\n> On Tue, Jul 26, 2011 at 10:58 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n\n>> Could you save the svn-fe output (e.g., by introducing \"tee\" in the\n>> middle of the \"svn-fe | fast-import\" pipeline) and put it up\n>> somewhere online?  This would also be a good starting point for coming\n>> up with a reduced testcase.\n>\n> It's 1.9G uncompressed, 0.7G lzo-compressed. Will setup a ftp or\n> torrent seed a bit later.\n\nAh, never mind then. :)  Do you have a script to reproduce it?\n"},{"id":"172095","messageId":"CA+gfSn8-+X9vrCYamN9Rg-PnGAQ3u5jH+S7LYxoZopMyEF9VPg@mail.gmail.com","threadId":"27767","inReplyTo":"20110726185504.GA2398@elie.dc0b.debconf.org","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-26T21:09:41Z","receivedAt":"2011-07-26T21:09:41Z","isPatch":false,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"On Wed, Jul 27, 2011 at 12:55 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n> Dmitry Ivankov wrote:\n>> On Tue, Jul 26, 2011 at 10:58 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n>\n>>> Could you save the svn-fe output (e.g., by introducing \"tee\" in the\n>>> middle of the \"svn-fe | fast-import\" pipeline) and put it up\n>>> somewhere online?  This would also be a good starting point for coming\n>>> up with a reduced testcase.\n>>\n>> It's 1.9G uncompressed, 0.7G lzo-compressed. Will setup a ftp or\n>> torrent seed a bit later.\n>\n> Ah, never mind then. :)  Do you have a script to reproduce it?\nI've uploaded the compressed svnadmin dump to dropbox - it's just 15M.\nSo here is a Makefile to reproduce the bug.\nIt needs svn-fe using deltas and fast-import knowing cat-blob-fd, cat-blob, ls.\nBut once gcc.fi_stream is built, any more or less recent fast-import\ncan be used.\n\nbug: gcc.fi_stream gcc.fi_stream_more\n        rm -rf tmp && \\\n        git init --bare tmp && \\\n        cat gcc.fi_stream gcc.fi_stream_more | \\\n        GIT_DIR=tmp git fast-import 2>&1 >/dev/null && \\\n        GIT_DIR=tmp git fsck\ngcc.svndump.tar.bz2:\n        wget http://dl.dropbox.com/u/36429197/gcc.svndump.tar.bz2\ngcc.svndump: gcc.svndump.tar.bz2\n        tar xjpf $<\n        #command -v svnrdump && \\\n        #svnrdump dump -r0:15507 svn://gcc.gnu.org/svn/gcc >gcc.svndump\n        #|| rm -f gcc.svndump\ngcc.fi_stream: gcc.svndump\n        command -v svn-fe && \\\n        rm -f backflow && \\\n        mkfifo backflow && \\\n        rm -rf tmp && \\\n        git init --bare tmp && \\\n        cat gcc.svndump | svn-fe 3<backflow | tee gcc.fi_stream | \\\n        GIT_DIR=tmp git fast-import --cat-blob-fd=3 3>backflow 2>&1 >/dev/null \\\n        || rm -f gcc.fi_stream\ngcc.fi_stream_more:\n        echo \"commit refs/heads/master\" >$@\n        echo \"mark :15508\" >>$@\n        echo \"committer nobody\n<nobody@69586fb2-bf4f-e74e-8260-21e4b08243f9> 874511505 +0000\" >>$@\n        echo \"data 71\" >>$@\n        echo \"This commit was manufactured by cvs2svn to create tag\" >>$@\n        echo \"'egcs_ss_970917'.\" >>$@\n        echo \"#ls :14842 branches/gcc3/gcc/config\" >>$@\n        echo \"M 040000 fbc83f80e9516c831918dff149058cba38a2e5f1\ntags/egcs_ss_970917/gcc/config\" >>$@\n        echo \"#ls :15459 trunk/gcc/config/alpha\" >>$@\n        echo \"M 040000 9ffe84c346eec93b523d95ce642b54d54d23109c\ntags/egcs_ss_970917/gcc/config/alpha\" >>$@\n        echo \"#ls \\\"tags/egcs_ss_970917/gcc/config/alpha\\\"\" >>$@\n        echo \"M 100644 inline\ntags/egcs_ss_970917/gcc/config/alpha/vms-tramp.asm_\" >>$@\n        echo \"data <<EOF\" >>$@\n        echo \"123\" >>$@\n        echo \"EOF\" >>$@\n        echo \"progress Imported commit 15508\" >>$@\n.PHONY: bug\n"},{"id":"172246","messageId":"20110728095634.GA6991@elie","threadId":"27767","inReplyTo":"CA+gfSn8m=_vd91Xe5EnFXUvZnuJf-yUE6H7FU+ak8S8a+NtCjA@mail.gmail.com","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-28T09:56:34Z","receivedAt":"2011-07-28T09:56:34Z","isPatch":false,"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> @@ -1514,6 +1514,9 @@ static int tree_content_set(\n>                                 if (e->tree)\n>                                         release_tree_content_recursive(e->tree);\n>                                 e->tree = subtree;\n> +                               if (S_ISDIR(mode)) {\n> +                                       hashclr(e->versions[0].sha1);\n> +                               }\n>                                 hashclr(root->versions[1].sha1);\n>                                 return 1;\n>                         }\n\nBased on your later explanations, it looks like this hit the nail on\nthe head.  The idea is that normally e->tree includes entries for both\ne->versions[0] and e->versions[1] and that in the \"M 040000 ...\" case,\nthis codepath at least currently doesn't have enough information to\ndecide on a good delta base.\n\nJust doing a \"hashclr(e->versions[0].sha1)\" will change the preimage\ntree object for the parent directory, causing invalid deltas _there_.\nSo that's not quite right.\n\nPossible fixes:\n\n a. invalidate preimage tree names all the way up the hierarchy.\n    This is what I misread the code as doing at first.  It would\n    be a cop-out; I think we can do better.\n\n b. merge the preimage and postimage trees in e->tree, and use\n    the existing preimage tree as delta basis.  This would produce\n    an unnecessarily large delta, but it should work.\n\n c. add a bit to \"struct tree_content\" (or abuse delta_depth) to\n    say \"my parent entry's versions[0].sha1 has nothing to do with\n    me; please do not write me out as a delta against it\"\n\n d. invalidate preimage tree object names up the hierarchy, and allow\n    tree_content_set callers to pass a \"const struct tree_entry_ms *\"\n    argument indicating a preimage tree object name for the new\n    subtree.\n\n e. instead of replacing a tree entry, delete it and add it again as a\n    new tree entry.  Make sure internal APIs can deal with multiple\n    tree entries with the same name.\n\nI find (c) tempting.  Like this, vaguely.  What do you think?\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\n fast-import.c |   35 ++++++++++++++++++++++++++++++-----\n 1 files changed, 30 insertions(+), 5 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 9e8d1868..2880af7b 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@@ -1415,8 +1420,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@@ -1426,7 +1432,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@@ -1436,7 +1442,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@@ -1470,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@@ -1514,6 +1522,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@@ -2928,7 +2953,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}\n-- \n1.7.6\n"},{"id":"172256","messageId":"CA+gfSn_dzuW-z-S8y2n2jnzwdm477GN5oXdnAoUb81-fQyC-_A@mail.gmail.com","threadId":"27767","inReplyTo":"20110728095634.GA6991@elie","subject":"Re: long fast-import errors out \"failed to apply delta\"","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-07-28T11:24:06Z","receivedAt":"2011-07-28T11:24:06Z","isPatch":false,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"On Thu, Jul 28, 2011 at 3:56 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n> Dmitry Ivankov wrote:\n>\n>> --- a/fast-import.c\n>> +++ b/fast-import.c\n>> @@ -1514,6 +1514,9 @@ static int tree_content_set(\n>>                                 if (e->tree)\n>>                                         release_tree_content_recursive(e->tree);\n>>                                 e->tree = subtree;\n>> +                               if (S_ISDIR(mode)) {\n>> +                                       hashclr(e->versions[0].sha1);\n>> +                               }\n>>                                 hashclr(root->versions[1].sha1);\n>>                                 return 1;\n>>                         }\n>\n> Based on your later explanations, it looks like this hit the nail on\n> the head.  The idea is that normally e->tree includes entries for both\n> e->versions[0] and e->versions[1] and that in the \"M 040000 ...\" case,\n> this codepath at least currently doesn't have enough information to\n> decide on a good delta base.\n>\n> Just doing a \"hashclr(e->versions[0].sha1)\" will change the preimage\n> tree object for the parent directory, causing invalid deltas _there_.\n> So that's not quite right.\n>\n> Possible fixes:\n>\n>  a. invalidate preimage tree names all the way up the hierarchy.\n>    This is what I misread the code as doing at first.  It would\n>    be a cop-out; I think we can do better.\n>\n>  b. merge the preimage and postimage trees in e->tree, and use\n>    the existing preimage tree as delta basis.  This would produce\n>    an unnecessarily large delta, but it should work.\nThat's what I was trying to do in  [7/7] fast-import: fix data\ncorruption in load_tree.\nBut [7/7] covers only subtree == NULL case.\nDelta size shouldn't be too large for the top level tree, if of course\npreimage and postimage are similar. Another bad thing is that changes\ngo deep down the tree (while in a. they go up the tree).\n\n>  c. add a bit to \"struct tree_content\" (or abuse delta_depth) to\n>    say \"my parent entry's versions[0].sha1 has nothing to do with\n>    me; please do not write me out as a delta against it\"\n>\n>  d. invalidate preimage tree object names up the hierarchy, and allow\n>    tree_content_set callers to pass a \"const struct tree_entry_ms *\"\n>    argument indicating a preimage tree object name for the new\n>    subtree.\nnot much better than a.\n\n>  e. instead of replacing a tree entry, delete it and add it again as a\n>    new tree entry.  Make sure internal APIs can deal with multiple\n>    tree entries with the same name.\nThere is a risk that trees will grow twice in ram :)\n\n> I find (c) tempting.\nThe best thing about it is that it's local. And it looks like it\ndisables deltas for the minimum number of objects among a-d, and e.\nisn't too much better.\n\n>  Like this, vaguely.  What do you think?\nTested it on my dump - no fsck complaints.\n\n[skipped part of the patch]\n> @@ -1470,6 +1477,7 @@ static void tree_content_replace(\n>  {\n>        if (!S_ISDIR(mode))\n>                die(\"Root cannot be a non-directory\");\n> +       hashclr(root->versions[0].sha1);\n>        hashcpy(root->versions[1].sha1, sha1);\n>        if (root->tree)\n>                release_tree_content_recursive(root->tree);\nShould it be root->versions[0].mode |= NO_DELTA instead?\nI see that it's only called for the tree root, but still. This way\nversions[0].sha1\nwill be changed only in store tree to discard the preimage and in\nload_tree or other\nentry creation place (in the end of tree_content_set).\n\nWill give it more testing, thanks for a small patch for this problem :)\n"}]}