long fast-import errors out "failed to apply delta"

long fast-import errors out "failed to apply delta"

[Dmitry Ivankov]

Hi,

I'm getting a strange error from git-fast-import.
Tested on v1.7.5 and v1.7.6 on two machines (gentoo amd64 8gb ram,
3-core amd cpu; gentoo x86 2gb ram, 1-core intel mobile cpu).
The crash is stable - same message, instruction and deepest function
(patch_delta) parameters contents.

$ git fast-import --quiet < big_dump
fatal: failed to apply delta
fast-import: dumping crash report to fast_import_crash_7700

Where big_dump is produced by svn-fe, 3.3Gb, 43404 sequential commits
(in fact 43403, 43404th causes a crash in the middle) to a single
branch with a "mark" and "progress" commands for each commit.
Crash report doesn't give much hints:
The last commands are
commit refs/heads/master
mark :43404
committer ...
data 53
[a few "ls ..." & "M 100644 ...", one "M 100755 ..."]
  ls :43402 incubator/directory/seda/trunk/impl/src/java/org/apache/seda/processor/RequestProcessorMonitorAdapter.java
* M 100644 64d6fb598ba6b6a3f8418e62ea9bceb0cefe4481
incubator/directory/seda/trunk/api/src/java/org/apache/seda/protocol/RequestProcessorMonitorAdapter.java

The failure is in sha1_file.c:unpack_delta_entry on unpacking
something like depth=7 tree on the path to that file.

And the failure comes from:
void *patch_delta(const void *src_buf, unsigned long src_size,
                  const void *delta_buf, unsigned long delta_size,
                  unsigned long *dst_size)
...
        size = get_delta_hdr_size(&data, top);
        if (size != src_size)
                return NULL;

Where size is arount 590(don't remember, can gdb again if needed or it
can be extracted from the dumped delta_data), and src_size is 396. One
can inspect the parameters with a program at the bottom of this email.

I tried to add a "checkpoint" command before the failing commit - no effect.
And then I split the dump, imported commits that don't fail, with
--export-marks, run fast-import --import-marks on the remaining commit
dump and it didn't fail.

This looks strange to me.
Shouldn't checkpoint dump everything on the disk and have the same
effect as splitting the stream?
It doesn't look like an interrupted read of object because src_size is
always the same.

On a split run there is no delta resolution that visually looks like
the problematic one, the one that suits most has different base_size,
delta_size, delta_data is completely different and src_datas have some
common prefix of 14 bytes.

Any advices on debugging this?
I'll try valgrind for now.

---
test-apply-delta.c:
#include "git-compat-util.h"
#include "delta.h"

static const size_t base_size = 396;
static const unsigned char base_data[397] =
"\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
 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";
static const size_t delta_size = 333;
static const unsigned char delta_data[334] =
"\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
 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";

static long unsigned result_size;
static long unsigned *result_size_p = &result_size;
static void *result = NULL;

int main() {
	result = patch_delta(base_data, base_size, delta_data, delta_size,
result_size_p);
	return result == NULL ? 1 : 0;
}

Re: long fast-import errors out "failed to apply delta"

[Dmitry Ivankov]

Small update: valgrind didn't detect anything.

Re: long fast-import errors out "failed to apply delta"

[Dmitry Ivankov]

+people contributed to the related parts of fast-import.c

Hi!

I did more tests and investigations. (one can safely jump over next 2
paragraphs)
There is a problem in fast-import, triggered on long svn-fe produced
imports (10k..80k commits depending on the svn repo history, in my
tests at least). fast-imports sometimes writes off a tree object with
wrong sha1. It goes silent unless it tries to read these objects for
later revisions (via ls command) and "crashes", or unless fsck is run
to find sha1 mismatches.

This seems to be a old bug. Due to the content of my fast-import
streams, I need cat-blob and ls commands (once the import stream is
sniffed these can be ignored) and more importantly 334fba656b50c9..
"Teach fast-import to import subtrees named by tree id" 30 Jun 2010
for  "M 040000 <tree id> pathname" commands. The earliest git version
I've tested so far is v1.6.0.6-7-g3d1d81e Jan 2009 + dummy cat-blob
and ls + 334fba656b50c9..

So, how do I currently reproduce it.
Import gcc svn repository with svn-fe up to r15507 - fine. (1.9G
fast-import stream, 3min to import, 1min to fsck)
Import up to r15508 - fine, but fsck finds a sha1 mismatch in a tree object.
Strip r15508 to a three commands:

..commit header..
ls :14842 branches/gcc3/gcc/config
M 040000 fbc83f80e9516c831918dff149058cba38a2e5f1 tags/egcs_ss_970917/gcc/config
ls :15459 trunk/gcc/config/alpha
M 040000 9ffe84c346eec93b523d95ce642b54d54d23109c
tags/egcs_ss_970917/gcc/config/alpha
ls "tags/egcs_ss_970917/gcc/config/alpha"
D tags/egcs_ss_970917/gcc/config/alpha/vms-tramp.asm

So here we set a directory with one old tree, then set it's child with
another old tree, and then delete a file in the child. The broken tree
is the resulting tree for that child. sha1 written to the pack matches
the intent (the second M + D) while the content is wrong (matches the
first M/subdir + D) - the second M command is partially lost.

If a checkpoint command is added before the last commit there is no
sha1 mismatch. I haven't yet found a small fast-import stream with
this bug, but it is a definetely a logic bug somewhere in fast-import.
I randomly changed pool sizes (didn't touch packfile settings yet),
run valgrind, slightly modified the stream many times, tested a bunch
of different git versions on two machines - the bug is stable.

Any ideas? How is it possible at all that the tree's sha1 and content
diverge, and moreover this is unnoticed by fast-import and a broken
packfile is produced?

On Thu, Jul 7, 2011 at 4:47 PM, Dmitry Ivankov <divanorama@gmail.com> wrote:
> Hi,
>
> I'm getting a strange error from git-fast-import.
> Tested on v1.7.5 and v1.7.6 on two machines (gentoo amd64 8gb ram,
> 3-core amd cpu; gentoo x86 2gb ram, 1-core intel mobile cpu).
> The crash is stable - same message, instruction and deepest function
> (patch_delta) parameters contents.
>
> $ git fast-import --quiet < big_dump
> fatal: failed to apply delta
> fast-import: dumping crash report to fast_import_crash_7700
[skipped the details]

Re: long fast-import errors out "failed to apply delta"

[Dmitry Ivankov]

Hi,

I've found where the bug comes from, but not yet understand the delta
logic in fast-import.c enough to fix it properly or to create a small testcase.
The problem is with delta coding a tree change, e->versions[0].sha1 and
e->tree->..->versions[0].sha1 diverge, the former corresponds to an older
state. When doing delta coding  we call mktree(t, 0, oldtree) that reads from
our in-memory e->tree structure, get the correct delta with the produced, the
data sha1 is also correct, but e->versions[0].sha1 is written to the packfile
as a delta base and it is wrong. When this object is unpacked by git delta
is applied to wrong base and hence the sha1 mismatch.

1) Do we need to delta code trees?
2) Was it supposed to work, or only blob deltas were meant to work?
3) Is this breakage specific to tags/v1.7.3-rc0~75^2 "Teach
fast-import to import subtrees named by tree id" 30 Jun 2010 (allowing
M 040000 <tree id> pathname)?

The simple fix is not to delta-code tree in store_tree():

diff --git a/fast-import.c b/fast-import.c
index 9e8d186..129f1c7 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1425,8 +1425,6 @@ static void store_tree(struct tree_entry *root)
 {
        struct tree_content *t = root->tree;
        unsigned int i, j, del;
-       struct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };
-       struct object_entry *le;

        if (!is_null_sha1(root->versions[1].sha1))
                return;
@@ -1436,18 +1434,10 @@ static void store_tree(struct tree_entry *root)
                        store_tree(t->entries[i]);
        }

-       le = find_object(root->versions[0].sha1);
-       if (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {
-               mktree(t, 0, &old_tree);
-               lo.data = old_tree;
-               lo.offset = le->idx.offset;
-               lo.depth = t->delta_depth;
-       }
-
        mktree(t, 1, &new_tree);
-       store_object(OBJ_TREE, &new_tree, &lo, root->versions[1].sha1, 0);
+       store_object(OBJ_TREE, &new_tree, NULL, root->versions[1].sha1, 0);

-       t->delta_depth = lo.depth;
+       t->delta_depth = 0;
        for (i = 0, j = 0, del = 0; i < t->entry_count; i++) {
                struct tree_entry *e = t->entries[i];
                if (e->versions[1].mode) {

The harder fix is to try to keep e->versions[0].sha1 for trees correct.
That looks like that it should match mktree(v=0), and it uses
versions[0].sha1 of child entries. Once a version[0].sha1 changes all
parents should clear their versions[0].sha1 (is it right?). And also in
load_tree(), child entries versions[0].sha1 should be set (its it right?)
from parent base object. No patch for this case.

Assuming that trees delta coding breaks only when we do
M 040000 sha1 some/path
and only that tree's data gets invalid, we can do this patch:

diff --git a/fast-import.c b/fast-import.c
index 9e8d186..85c711c 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1514,6 +1514,9 @@ static int tree_content_set(
                                if (e->tree)
                                        release_tree_content_recursive(e->tree);
                                e->tree = subtree;
+                               if (S_ISDIR(mode)) {
+                                       hashclr(e->versions[0].sha1);
+                               }
                                hashclr(root->versions[1].sha1);
                                return 1;
                        }

Both patches seem to fix the bug, at least on one large testcase I'm testing it.
But first of all a small test is needed, it looks very likely that
there exists one.
And then, of course, a proper fix is needed.

I'll leave a short description of the setup for a reference.

> So, how do I currently reproduce it.
> Import gcc svn repository with svn-fe up to r15507 - fine. (1.9G
> fast-import stream, 3min to import, 1min to fsck)
> Import up to r15508 - fine, but fsck finds a sha1 mismatch in a tree object.
> Strip r15508 to a three commands:
>
> ..commit header..
> ls :14842 branches/gcc3/gcc/config
> M 040000 fbc83f80e9516c831918dff149058cba38a2e5f1 tags/egcs_ss_970917/gcc/config
> ls :15459 trunk/gcc/config/alpha
> M 040000 9ffe84c346eec93b523d95ce642b54d54d23109c
> tags/egcs_ss_970917/gcc/config/alpha
> ls "tags/egcs_ss_970917/gcc/config/alpha"
> D tags/egcs_ss_970917/gcc/config/alpha/vms-tramp.asm
>
> So here we set a directory with one old tree, then set it's child with
> another old tree, and then delete a file in the child. The broken tree
> is the resulting tree for that child. sha1 written to the pack matches
> the intent (the second M + D) while the content is wrong (matches the
> first M/subdir + D) - the second M command is partially lost.

Re: long fast-import errors out "failed to apply delta"

[Jonathan Nieder]

Hi Dmitry,

Dmitry Ivankov wrote:

> 3) Is this breakage specific to tags/v1.7.3-rc0~75^2 "Teach
> fast-import to import subtrees named by tree id" 30 Jun 2010 (allowing
> M 040000 <tree id> pathname)?

Probably. :)

> The harder fix is to try to keep e->versions[0].sha1 for trees correct.

Context for those who don't remember all the details:

When first introduced, "struct tree_entry" was very simple: a mode, a
filename, and:

 - for regular objects and symlinks, a blob object name representing
   its content;

 - for subdirectories, a pointer to "struct tree_content" listing its
   contents, along with an _optional_ cached tree object name.

When modifying a tree entry, fast-import would walk through the path
to it and invalidate the cached tree names at each step.  Shawn wrote:

	Currently trees and commits aren't being deltafied when written to
	the pack and branch reloading from the current pack doesn't work,
	so at most 5 branches can be worked with at any one time.

but the advantage was that it was very simple.  Later, delta
compression arrived:

	commit 4cabf858
	Author: Shawn O. Pearce <spearce@spearce.org>
	Date:   Mon Aug 28 12:22:50 2006 -0400

	    Implemented tree delta compression in fast-import.

	    We now store for every tree entry two modes and two sha1 values;
	    the base (aka "version 0") and the current/new (aka "version 1").
	    When we generate a tree object we also regenerate the prior version
	    object and use that as our base object for a delta.  This strategy
	    saves a significant amount of memory as we can continue to use the
	    atom pool for file/directory names and only increases each tree
	    entry by an additional 24 bytes of memory.

In other words, this commit introduced a "prior" mode and tree or blob
name to give the pack-writing machinery a hint about what to delta
against.

With that in mind, it seems very weird that the version 0 tree would
ever be changed and need to have its object name invalidated.  Perhaps
we are releasing some memory too early and it is getting clobbered?
Unless I am missing something, the patch

> --- a/fast-import.c
> +++ b/fast-import.c
> @@ -1514,6 +1514,9 @@ static int tree_content_set(
>                                 if (e->tree)
>                                         release_tree_content_recursive(e->tree);
>                                 e->tree = subtree;
> +                               if (S_ISDIR(mode)) {
> +                                       hashclr(e->versions[0].sha1);
> +                               }
>                                 hashclr(root->versions[1].sha1);
>                                 return 1;

just disables deltas for trees that have been modified by a "M 040000"
command, so it feels more like a workaround than a fundamental fix.

Could you save the svn-fe output (e.g., by introducing "tee" in the
middle of the "svn-fe | fast-import" pipeline) and put it up
somewhere online?  This would also be a good starting point for coming
up with a reduced testcase.

Hope that helps,
Jonathan

Re: long fast-import errors out "failed to apply delta"

[Dmitry Ivankov]

Hi,

On Tue, Jul 26, 2011 at 10:58 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Hi Dmitry,
>
> Dmitry Ivankov wrote:
>
>> 3) Is this breakage specific to tags/v1.7.3-rc0~75^2 "Teach
>> fast-import to import subtrees named by tree id" 30 Jun 2010 (allowing
>> M 040000 <tree id> pathname)?
>
> Probably. :)
>
>> The harder fix is to try to keep e->versions[0].sha1 for trees correct.
>
> Context for those who don't remember all the details:
>
> When first introduced, "struct tree_entry" was very simple: a mode, a
> filename, and:
>
>  - for regular objects and symlinks, a blob object name representing
>   its content;
>
>  - for subdirectories, a pointer to "struct tree_content" listing its
>   contents, along with an _optional_ cached tree object name.
>
> When modifying a tree entry, fast-import would walk through the path
> to it and invalidate the cached tree names at each step.  Shawn wrote:
>
>        Currently trees and commits aren't being deltafied when written to
>        the pack and branch reloading from the current pack doesn't work,
>        so at most 5 branches can be worked with at any one time.
>
> but the advantage was that it was very simple.  Later, delta
> compression arrived:
>
>        commit 4cabf858
>        Author: Shawn O. Pearce <spearce@spearce.org>
>        Date:   Mon Aug 28 12:22:50 2006 -0400
>
>            Implemented tree delta compression in fast-import.
>
>            We now store for every tree entry two modes and two sha1 values;
>            the base (aka "version 0") and the current/new (aka "version 1").
>            When we generate a tree object we also regenerate the prior version
>            object and use that as our base object for a delta.  This strategy
>            saves a significant amount of memory as we can continue to use the
>            atom pool for file/directory names and only increases each tree
>            entry by an additional 24 bytes of memory.
>
> In other words, this commit introduced a "prior" mode and tree or blob
> name to give the pack-writing machinery a hint about what to delta
> against.
>
> With that in mind, it seems very weird that the version 0 tree would
> ever be changed and need to have its object name invalidated.

Well, if we'd read the actual prior contents via sha1-lookup, no
invalidation would be needed,
we can create delta with any base after all.
But we use mktree(v=0) to collect versions[0].sha1 of entries with
(mode != 0) as a content.
I think I almost got it now. When we tree_content_set by sha1 (we use
subtree = NULL) and
that tree had some versions[0].sha1, we reset it's ->tree to NULL
loosing the old sha1's of
the entries. Later we traverse there and load_tree that NULL, setting
the entries with
versions[0].sha1 = versions[1].sha1 = sha1's of new/current tree entries.

So looks like load_tree should restore versions[0].sha1's IF the prior
object was a tree.
I've tried this approach with merging two trees, but my rough patch is
bloated and crashes.

A bit slower one is to do sha1 lookups for the delta base trees.

>  Perhaps
> we are releasing some memory too early and it is getting clobbered?
> Unless I am missing something, the patch
>
>> --- a/fast-import.c
>> +++ b/fast-import.c
>> @@ -1514,6 +1514,9 @@ static int tree_content_set(
>>                                 if (e->tree)
>>                                         release_tree_content_recursive(e->tree);
>>                                 e->tree = subtree;
>> +                               if (S_ISDIR(mode)) {
>> +                                       hashclr(e->versions[0].sha1);
>> +                               }
>>                                 hashclr(root->versions[1].sha1);
>>                                 return 1;
>
> just disables deltas for trees that have been modified by a "M 040000"
> command, so it feels more like a workaround than a fundamental fix.
Right, I can't even say I understand in full what does it change.

> Could you save the svn-fe output (e.g., by introducing "tee" in the
> middle of the "svn-fe | fast-import" pipeline) and put it up
> somewhere online?  This would also be a good starting point for coming
> up with a reduced testcase.
It's 1.9G uncompressed, 0.7G lzo-compressed. Will setup a ftp or
torrent seed a bit later.

>
> Hope that helps,
> Jonathan
>

Re: long fast-import errors out "failed to apply delta"

[Jonathan Nieder]

Dmitry Ivankov wrote:
> On Tue, Jul 26, 2011 at 10:58 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:

>> Could you save the svn-fe output (e.g., by introducing "tee" in the
>> middle of the "svn-fe | fast-import" pipeline) and put it up
>> somewhere online?  This would also be a good starting point for coming
>> up with a reduced testcase.
>
> It's 1.9G uncompressed, 0.7G lzo-compressed. Will setup a ftp or
> torrent seed a bit later.

Ah, never mind then. :)  Do you have a script to reproduce it?

Re: long fast-import errors out "failed to apply delta"

[Dmitry Ivankov]

On Wed, Jul 27, 2011 at 12:55 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Dmitry Ivankov wrote:
>> On Tue, Jul 26, 2011 at 10:58 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
>
>>> Could you save the svn-fe output (e.g., by introducing "tee" in the
>>> middle of the "svn-fe | fast-import" pipeline) and put it up
>>> somewhere online?  This would also be a good starting point for coming
>>> up with a reduced testcase.
>>
>> It's 1.9G uncompressed, 0.7G lzo-compressed. Will setup a ftp or
>> torrent seed a bit later.
>
> Ah, never mind then. :)  Do you have a script to reproduce it?
I've uploaded the compressed svnadmin dump to dropbox - it's just 15M.
So here is a Makefile to reproduce the bug.
It needs svn-fe using deltas and fast-import knowing cat-blob-fd, cat-blob, ls.
But once gcc.fi_stream is built, any more or less recent fast-import
can be used.

bug: gcc.fi_stream gcc.fi_stream_more
        rm -rf tmp && \
        git init --bare tmp && \
        cat gcc.fi_stream gcc.fi_stream_more | \
        GIT_DIR=tmp git fast-import 2>&1 >/dev/null && \
        GIT_DIR=tmp git fsck
gcc.svndump.tar.bz2:
        wget http://dl.dropbox.com/u/36429197/gcc.svndump.tar.bz2
gcc.svndump: gcc.svndump.tar.bz2
        tar xjpf $<
        #command -v svnrdump && \
        #svnrdump dump -r0:15507 svn://gcc.gnu.org/svn/gcc >gcc.svndump
        #|| rm -f gcc.svndump
gcc.fi_stream: gcc.svndump
        command -v svn-fe && \
        rm -f backflow && \
        mkfifo backflow && \
        rm -rf tmp && \
        git init --bare tmp && \
        cat gcc.svndump | svn-fe 3<backflow | tee gcc.fi_stream | \
        GIT_DIR=tmp git fast-import --cat-blob-fd=3 3>backflow 2>&1 >/dev/null \
        || rm -f gcc.fi_stream
gcc.fi_stream_more:
        echo "commit refs/heads/master" >$@
        echo "mark :15508" >>$@
        echo "committer nobody
<nobody@69586fb2-bf4f-e74e-8260-21e4b08243f9> 874511505 +0000" >>$@
        echo "data 71" >>$@
        echo "This commit was manufactured by cvs2svn to create tag" >>$@
        echo "'egcs_ss_970917'." >>$@
        echo "#ls :14842 branches/gcc3/gcc/config" >>$@
        echo "M 040000 fbc83f80e9516c831918dff149058cba38a2e5f1
tags/egcs_ss_970917/gcc/config" >>$@
        echo "#ls :15459 trunk/gcc/config/alpha" >>$@
        echo "M 040000 9ffe84c346eec93b523d95ce642b54d54d23109c
tags/egcs_ss_970917/gcc/config/alpha" >>$@
        echo "#ls \"tags/egcs_ss_970917/gcc/config/alpha\"" >>$@
        echo "M 100644 inline
tags/egcs_ss_970917/gcc/config/alpha/vms-tramp.asm_" >>$@
        echo "data <<EOF" >>$@
        echo "123" >>$@
        echo "EOF" >>$@
        echo "progress Imported commit 15508" >>$@
.PHONY: bug

Re: long fast-import errors out "failed to apply delta"

[Jonathan Nieder]

Dmitry Ivankov wrote:

> --- a/fast-import.c
> +++ b/fast-import.c
> @@ -1514,6 +1514,9 @@ static int tree_content_set(
>                                 if (e->tree)
>                                         release_tree_content_recursive(e->tree);
>                                 e->tree = subtree;
> +                               if (S_ISDIR(mode)) {
> +                                       hashclr(e->versions[0].sha1);
> +                               }
>                                 hashclr(root->versions[1].sha1);
>                                 return 1;
>                         }

Based on your later explanations, it looks like this hit the nail on
the head.  The idea is that normally e->tree includes entries for both
e->versions[0] and e->versions[1] and that in the "M 040000 ..." case,
this codepath at least currently doesn't have enough information to
decide on a good delta base.

Just doing a "hashclr(e->versions[0].sha1)" will change the preimage
tree object for the parent directory, causing invalid deltas _there_.
So that's not quite right.

Possible fixes:

 a. invalidate preimage tree names all the way up the hierarchy.
    This is what I misread the code as doing at first.  It would
    be a cop-out; I think we can do better.

 b. merge the preimage and postimage trees in e->tree, and use
    the existing preimage tree as delta basis.  This would produce
    an unnecessarily large delta, but it should work.

 c. add a bit to "struct tree_content" (or abuse delta_depth) to
    say "my parent entry's versions[0].sha1 has nothing to do with
    me; please do not write me out as a delta against it"

 d. invalidate preimage tree object names up the hierarchy, and allow
    tree_content_set callers to pass a "const struct tree_entry_ms *"
    argument indicating a preimage tree object name for the new
    subtree.

 e. instead of replacing a tree entry, delete it and add it again as a
    new tree entry.  Make sure internal APIs can deal with multiple
    tree entries with the same name.

I find (c) tempting.  Like this, vaguely.  What do you think?

Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 fast-import.c |   35 ++++++++++++++++++++++++++++++-----
 1 files changed, 30 insertions(+), 5 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 9e8d1868..2880af7b 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -170,6 +170,11 @@ Format of STDIN stream:
 #define DEPTH_BITS 13
 #define MAX_DEPTH ((1<<DEPTH_BITS)-1)
 
+/*
+ * We abuse the setuid bit on directories to mean "do not delta".
+ */
+#define NO_DELTA S_ISUID
+
 struct object_entry {
 	struct pack_idx_entry idx;
 	struct object_entry *next;
@@ -1415,8 +1420,9 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)
 		struct tree_entry *e = t->entries[i];
 		if (!e->versions[v].mode)
 			continue;
-		strbuf_addf(b, "%o %s%c", (unsigned int)e->versions[v].mode,
-					e->name->str_dat, '\0');
+		strbuf_addf(b, "%o %s%c",
+			(unsigned int)(e->versions[v].mode & ~NO_DELTA),
+			e->name->str_dat, '\0');
 		strbuf_add(b, e->versions[v].sha1, 20);
 	}
 }
@@ -1426,7 +1432,7 @@ static void store_tree(struct tree_entry *root)
 	struct tree_content *t = root->tree;
 	unsigned int i, j, del;
 	struct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };
-	struct object_entry *le;
+	struct object_entry *le = NULL;
 
 	if (!is_null_sha1(root->versions[1].sha1))
 		return;
@@ -1436,7 +1442,8 @@ static void store_tree(struct tree_entry *root)
 			store_tree(t->entries[i]);
 	}
 
-	le = find_object(root->versions[0].sha1);
+	if (!(root->versions[0].mode & NO_DELTA))
+		le = find_object(root->versions[0].sha1);
 	if (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {
 		mktree(t, 0, &old_tree);
 		lo.data = old_tree;
@@ -1470,6 +1477,7 @@ static void tree_content_replace(
 {
 	if (!S_ISDIR(mode))
 		die("Root cannot be a non-directory");
+	hashclr(root->versions[0].sha1);
 	hashcpy(root->versions[1].sha1, sha1);
 	if (root->tree)
 		release_tree_content_recursive(root->tree);
@@ -1514,6 +1522,23 @@ static int tree_content_set(
 				if (e->tree)
 					release_tree_content_recursive(e->tree);
 				e->tree = subtree;
+
+				/*
+				 * We need to leave e->versions[0].sha1 alone
+				 * to avoid modifying the preimage tree used
+				 * when writing out the parent directory.
+				 * But after replacing the subdir with a
+				 * completely different one, it's not a good
+				 * delta base any more, and besides, we've
+				 * thrown away the tree entries needed to
+				 * make a delta against it.
+				 *
+				 * So let's just explicitly disable deltas
+				 * for the subtree.
+				 */
+				if (S_ISDIR(e->versions[0].mode))
+					e->versions[0].mode |= NO_DELTA;
+
 				hashclr(root->versions[1].sha1);
 				return 1;
 			}
@@ -2928,7 +2953,7 @@ static void print_ls(int mode, const unsigned char *sha1, const char *path)
 		/* mode SP type SP object_name TAB path LF */
 		strbuf_reset(&line);
 		strbuf_addf(&line, "%06o %s %s\t",
-				mode, type, sha1_to_hex(sha1));
+				mode & ~NO_DELTA, type, sha1_to_hex(sha1));
 		quote_c_style(path, &line, NULL, 0);
 		strbuf_addch(&line, '\n');
 	}
-- 
1.7.6

Re: long fast-import errors out "failed to apply delta"

[Dmitry Ivankov]

On Thu, Jul 28, 2011 at 3:56 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Dmitry Ivankov wrote:
>
>> --- a/fast-import.c
>> +++ b/fast-import.c
>> @@ -1514,6 +1514,9 @@ static int tree_content_set(
>>                                 if (e->tree)
>>                                         release_tree_content_recursive(e->tree);
>>                                 e->tree = subtree;
>> +                               if (S_ISDIR(mode)) {
>> +                                       hashclr(e->versions[0].sha1);
>> +                               }
>>                                 hashclr(root->versions[1].sha1);
>>                                 return 1;
>>                         }
>
> Based on your later explanations, it looks like this hit the nail on
> the head.  The idea is that normally e->tree includes entries for both
> e->versions[0] and e->versions[1] and that in the "M 040000 ..." case,
> this codepath at least currently doesn't have enough information to
> decide on a good delta base.
>
> Just doing a "hashclr(e->versions[0].sha1)" will change the preimage
> tree object for the parent directory, causing invalid deltas _there_.
> So that's not quite right.
>
> Possible fixes:
>
>  a. invalidate preimage tree names all the way up the hierarchy.
>    This is what I misread the code as doing at first.  It would
>    be a cop-out; I think we can do better.
>
>  b. merge the preimage and postimage trees in e->tree, and use
>    the existing preimage tree as delta basis.  This would produce
>    an unnecessarily large delta, but it should work.
That's what I was trying to do in  [7/7] fast-import: fix data
corruption in load_tree.
But [7/7] covers only subtree == NULL case.
Delta size shouldn't be too large for the top level tree, if of course
preimage and postimage are similar. Another bad thing is that changes
go deep down the tree (while in a. they go up the tree).

>  c. add a bit to "struct tree_content" (or abuse delta_depth) to
>    say "my parent entry's versions[0].sha1 has nothing to do with
>    me; please do not write me out as a delta against it"
>
>  d. invalidate preimage tree object names up the hierarchy, and allow
>    tree_content_set callers to pass a "const struct tree_entry_ms *"
>    argument indicating a preimage tree object name for the new
>    subtree.
not much better than a.

>  e. instead of replacing a tree entry, delete it and add it again as a
>    new tree entry.  Make sure internal APIs can deal with multiple
>    tree entries with the same name.
There is a risk that trees will grow twice in ram :)

> I find (c) tempting.
The best thing about it is that it's local. And it looks like it
disables deltas for the minimum number of objects among a-d, and e.
isn't too much better.

>  Like this, vaguely.  What do you think?
Tested it on my dump - no fsck complaints.

[skipped part of the patch]
> @@ -1470,6 +1477,7 @@ static void tree_content_replace(
>  {
>        if (!S_ISDIR(mode))
>                die("Root cannot be a non-directory");
> +       hashclr(root->versions[0].sha1);
>        hashcpy(root->versions[1].sha1, sha1);
>        if (root->tree)
>                release_tree_content_recursive(root->tree);
Should it be root->versions[0].mode |= NO_DELTA instead?
I see that it's only called for the tree root, but still. This way
versions[0].sha1
will be changed only in store tree to discard the preimage and in
load_tree or other
entry creation place (in the end of tree_content_set).

Will give it more testing, thanks for a small patch for this problem :)