threads / patch / 27939

patch, 7 partswas: long fast-import errors out "failed to apply delta"

Subject: [PATCH/WIP 0/7] was: long fast-import errors out "failed to apply delta"

## tl;dr

13 messages between Jul 28, 2011 and Jul 28, 2011. Diffs are folded; open one to read it.

replies: 12people: 2as markdown or json

Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · lore

A very short summary. It was found [1] that fast-import sometimes can produce broken packfiles (sha1 mismatch) or even wrong packfiles (data differs from what was expected). This happens mostly on not so tiny svn-to-git or even cvs-to-svn-to-git imports with all these copying across the tree (simulating tags/branches as a directories in git, for example). But I won't be surprised if this can happen without these operations too.

Technically, fast-import has in-memory tree representation where it stores sha1's of some previous tree states (to make delta on them), but when it comes to producing the delta, old sha1's tree content is fetched from the in-memory node and it's children (not via sha1->object lookup). And these can turn out to be unrelated to each other as some operations changes the children's states.

The most wanted bit for these patches is small testcases. Keeping in mind all the in-memory tree state and fast-import logic is hard for me, so I wasn't able to create small tests (the best is [2] - 15M archive + custom git builds + fix the Makefile in [2] + a few minutes to reproduce). Another good todo is to always avoid base sha1's mismatch (not just to avoid corruption if it is detected). I think I can do this, but I won't be sure in the code unless there is a bunch of good tests, this series is quite big already.

[1] http://thread.gmane.org/gmane.comp.version-control.git/176753 [2] http://thread.gmane.org/gmane.comp.version-control.git/176753/focus=177901

Dmitry Ivankov (7):
  fast-import: extract object preparation function
  fast-import: be saner with temporary trees
  fast-import: fix a data corruption in parse_ls
  fast-import: fix data corruption in store_tree
  fast-import: extract tree_content reading function
  fast-import: workaround data corruption
  fast-import: fix data corruption in load_tree
 fast-import.c |  169 +++++++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 135 insertions(+), 34 deletions(-)
-- 
1.7.3.4
Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · re: Dmitry Ivankov · lore

[PATCH/WIP 1/7] fast-import: extract object preparation function

We're constructing raw objects and compute their sha1's in fast-import just before saving them.

Extract header and sha1 computations so that we can get sha1 without actually saving the object.

Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>
---
 fast-import.c |   32 +++++++++++++++++++++++++-------
 1 files changed, 25 insertions(+), 7 deletions(-)
Show changes to fast-import.c +25 −7
diff --git a/fast-import.c b/fast-import.c
index 9e8d186..05cc55e 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1005,6 +1005,30 @@ static void cycle_packfile(void)
 	start_packfile();
 }
 
+static void prepare_object_hash(
+	enum object_type type,
+	struct strbuf *dat,
+	unsigned char *hdr_out,
+	unsigned long *hdrlen_out,
+	unsigned char *sha1_out
+)
+{
+	unsigned char hdr_[96];
+	unsigned char *hdr = hdr_out ? hdr_out : hdr_;
+	unsigned long hdrlen;
+	git_SHA_CTX c;
+
+	hdrlen = sprintf((char *)hdr,"%s %lu", typename(type),
+		(unsigned long)dat->len) + 1;
+	git_SHA1_Init(&c);
+	git_SHA1_Update(&c, hdr, hdrlen);
+	git_SHA1_Update(&c, dat->buf, dat->len);
+	git_SHA1_Final(sha1_out, &c);
+
+	if (hdrlen_out)
+		*hdrlen_out = hdrlen;
+}
+
 static int store_object(
 	enum object_type type,
 	struct strbuf *dat,
@@ -1017,15 +1041,9 @@ static int store_object(
 	unsigned char hdr[96];
 	unsigned char sha1[20];
 	unsigned long hdrlen, deltalen;
-	git_SHA_CTX c;
 	git_zstream s;
 
-	hdrlen = sprintf((char *)hdr,"%s %lu", typename(type),
-		(unsigned long)dat->len) + 1;
-	git_SHA1_Init(&c);
-	git_SHA1_Update(&c, hdr, hdrlen);
-	git_SHA1_Update(&c, dat->buf, dat->len);
-	git_SHA1_Final(sha1, &c);
+	prepare_object_hash(type, dat, hdr, &hdrlen, sha1);
 	if (sha1out)
 		hashcpy(sha1out, sha1);
 

-- 
1.7.3.4
Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · re: Dmitry Ivankov · lore

[PATCH/WIP 2/7] fast-import: be saner with temporary trees

new_tree_entry() doesn't zero or otherwise initialize the returned entry, neither does release_tree_entry(). So it is quite possible to get previously released data in a new entry.

parse_ls doesn't set entry->versions[0] fields, but it does call store_tree(entry) which looks for this base sha1 and tries to do delta compression with that random object.

Reset entry->versions[0] fields to make things more predictable and to avoid surprises here.

Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>
---
 fast-import.c |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)
Show changes to fast-import.c +3 −0
diff --git a/fast-import.c b/fast-import.c
index 05cc55e..da9cb62 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -2968,6 +2968,9 @@ static void parse_ls(struct branch *b)
 	} else {
 		struct object_entry *e = parse_treeish_dataref(&p);
 		root = new_tree_entry();
+		hashclr(root->versions[0].sha1);
+		root->versions[0].mode = 0;
+		root->versions[1].mode = S_IFDIR;
 		hashcpy(root->versions[1].sha1, e->idx.sha1);
 		load_tree(root);
 		if (*p++ != ' ')

-- 
1.7.3.4
Jonathan Nieder· Jul 28, 2011, 07:27 UTC · re: Dmitry Ivankov · lore

Re: [PATCH/WIP 2/7] fast-import: be saner with temporary trees

Dmitry Ivankov wrote:
> new_tree_entry() doesn't zero or otherwise initialize the returned
> entry, neither does release_tree_entry(). So it is quite possible
> to get previously released data in a new entry.

Thanks. Background for the confused: new_tree_entry / release_tree_entry manage a stack of tree_entry structs to use as temporaries. Initializing them is the responsibility of the caller, both after allocation with xmalloc() when existing temporaries are exhausted and after used entries are pushed with release_tree_entry().

Show 8 quoted lines
> parse_ls doesn't set entry->versions[0] fields, but it does call
> store_tree(entry) which looks for this base sha1 and tries to do
> delta compression with that random object.
>
> Reset entry->versions[0] fields to make things more predictable
> and to avoid surprises here.
>
> Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>

Good idea --- "root" is invalid at this point. Looks like a mistake introduced by my tweaks to v1.7.5-rc0~3^2~33 (fast-import: add 'ls' command, 2010-12-02).

But isn't store_tree() only called on "leaf" which is completely zero-initialized?

So I don't see why this change would have any effect. For what it's worth, even so, except for the commit message,

Acked-by: Jonathan Nieder <jrnieder@gmail.com>
Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · re: Dmitry Ivankov · lore

[PATCH/WIP 3/7] fast-import: fix a data corruption in parse_ls

store_tree sets versions[0] = versions[1] unconditionally. This is fine if it is run from the very root. But if it's run for a intermediate node in parse_ls, node's parent versions[0] can become invalid as it references it's children versions[0].

Move dropping old version to a function and don't drop old version in parse_ls. Also this split will allow to perform a few more fixes for store_tree itself.

Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>
---
 fast-import.c |   42 ++++++++++++++++++++++++++----------------
 1 files changed, 26 insertions(+), 16 deletions(-)
Show changes to fast-import.c +26 −16
diff --git a/fast-import.c b/fast-import.c
index da9cb62..d5915b8 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1439,12 +1439,36 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)
 	}
 }
 
-static void store_tree(struct tree_entry *root)
+static void drop_old(struct tree_entry *root)
 {
 	struct tree_content *t = root->tree;
 	unsigned int i, j, del;
+
+	hashcpy(root->versions[0].sha1, root->versions[1].sha1);
+	root->versions[0].mode = root->versions[1].mode;
+
+	if (!t)
+		return;
+
+	for (i = 0, j = 0, del = 0; i < t->entry_count; i++) {
+		struct tree_entry *e = t->entries[i];
+		if (e->versions[1].mode) {
+			drop_old(e);
+			t->entries[j++] = e;
+		} else {
+			release_tree_entry(e);
+			del++;
+		}
+	}
+	t->entry_count -= del;
+}
+
+static void store_tree(struct tree_entry *root)
+{
+	struct tree_content *t = root->tree;
 	struct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };
 	struct object_entry *le;
+	unsigned int i;
 
 	if (!is_null_sha1(root->versions[1].sha1))
 		return;
@@ -1464,20 +1488,7 @@ static void store_tree(struct tree_entry *root)
 
 	mktree(t, 1, &new_tree);
 	store_object(OBJ_TREE, &new_tree, &lo, root->versions[1].sha1, 0);
-
 	t->delta_depth = lo.depth;
-	for (i = 0, j = 0, del = 0; i < t->entry_count; i++) {
-		struct tree_entry *e = t->entries[i];
-		if (e->versions[1].mode) {
-			e->versions[0].mode = e->versions[1].mode;
-			hashcpy(e->versions[0].sha1, e->versions[1].sha1);
-			t->entries[j++] = e;
-		} else {
-			release_tree_entry(e);
-			del++;
-		}
-	}
-	t->entry_count -= del;
 }
 
 static void tree_content_replace(
@@ -2640,8 +2651,7 @@ static void parse_new_commit(void)
 
 	/* build the tree and the commit */
 	store_tree(&b->branch_tree);
-	hashcpy(b->branch_tree.versions[0].sha1,
-		b->branch_tree.versions[1].sha1);
+	drop_old(&b->branch_tree);
 
 	strbuf_reset(&new_data);
 	strbuf_addf(&new_data, "tree %s\n",

-- 
1.7.3.4
Jonathan Nieder· Jul 28, 2011, 07:34 UTC · re: Dmitry Ivankov · lore

Re: [PATCH/WIP 3/7] fast-import: fix a data corruption in parse_ls

Dmitry Ivankov wrote:
> store_tree sets versions[0] = versions[1] unconditionally. This is fine
> if it is run from the very root.
True.
> But if it's run for a intermediate
> node in parse_ls, node's parent versions[0] can become invalid as it
> references it's children versions[0].

A puzzle: when would parse_ls() call store_tree() on a subdirectory? The store_tree() call is preceded by

	tree_content_get(root, p, &leaf);

which makes a deep copy of "root" in leaf (which seems to be leaked --- oops).

Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · re: Dmitry Ivankov · lore

[PATCH/WIP 4/7] fast-import: fix data corruption in store_tree

store_tree didn't check for S_ISDIR(versions[1].mode), but it did check for tree != NULL.

It's possible that tree == NULL && S_ISDIR(versions[1].mode) in which case we need to load_tree and then to store_tree, and not to drop that entry. Calling load_tree requires S_ISDIR check to be present, that's why it is added..

Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>
---
 fast-import.c |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)
Show changes to fast-import.c +5 −2
diff --git a/fast-import.c b/fast-import.c
index d5915b8..d917ea6 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1474,8 +1474,11 @@ static void store_tree(struct tree_entry *root)
 		return;
 
 	for (i = 0; i < t->entry_count; i++) {
-		if (t->entries[i]->tree)
-			store_tree(t->entries[i]);
+		if (!S_ISDIR(t->entries[i]->versions[1].mode))
+			continue;
+		if (!t->entries[i]->tree)
+			load_tree(t->entries[i]);
+		store_tree(t->entries[i]);
 	}
 
 	le = find_object(root->versions[0].sha1);

-- 
1.7.3.4
Jonathan Nieder· Jul 28, 2011, 07:42 UTC · re: Dmitry Ivankov · lore

Re: [PATCH/WIP 4/7] fast-import: fix data corruption in store_tree

Dmitry Ivankov wrote:
Show 13 quoted lines
> --- a/fast-import.c
> +++ b/fast-import.c
> @@ -1474,8 +1474,11 @@ static void store_tree(struct tree_entry *root)
>  		return;
>  
>  	for (i = 0; i < t->entry_count; i++) {
> -		if (t->entries[i]->tree)
> -			store_tree(t->entries[i]);
> +		if (!S_ISDIR(t->entries[i]->versions[1].mode))
> +			continue;
> +		if (!t->entries[i]->tree)
> +			load_tree(t->entries[i]);
> +		store_tree(t->entries[i]);

How can this load_tree call work if t->entries[i]->versions[1].sha1 is not already in the object database?

Dmitry Ivankov· Jul 28, 2011, 08:11 UTC · re: Jonathan Nieder · lore

Re: [PATCH/WIP 4/7] fast-import: fix data corruption in store_tree

On Thu, Jul 28, 2011 at 1:42 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
Show 18 quoted lines
> Dmitry Ivankov wrote:
>
>> --- a/fast-import.c
>> +++ b/fast-import.c
>> @@ -1474,8 +1474,11 @@ static void store_tree(struct tree_entry *root)
>>               return;
>>
>>       for (i = 0; i < t->entry_count; i++) {
>> -             if (t->entries[i]->tree)
>> -                     store_tree(t->entries[i]);
>> +             if (!S_ISDIR(t->entries[i]->versions[1].mode))
>> +                     continue;
>> +             if (!t->entries[i]->tree)
>> +                     load_tree(t->entries[i]);
>> +             store_tree(t->entries[i]);
>
> How can this load_tree call work if t->entries[i]->versions[1].sha1
> is not already in the object database?

Well, it can be in the database and at the same time t->entries[i]->tree == NULL. In my testcase the commit is like

ls :10386 trunk M 040000 e1b2ea9d3634cb7914044425ffae91945c41ac6a branches/cygnus D branches/cygnus/gcc/assert.h D branches/cygnus/gcc/collect2.c D branches/cygnus/gcc/cccp.c D branches/cygnus/gcc/c-parse.gperf ... only D branches/cygnus/gcc/..... lines progress done #here we call it, so it's when we store whole tree, some subdirectory of branches/cygnus

the load_tree really gets called (with whole series applied to fast-import) and the load works (sha1 = 2e90a035614854f626bb35eeac517f41ac84da27) Though I don't yet see if not loading it breaks anything in my test (with the whole series).

Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · re: Dmitry Ivankov · lore

[PATCH/WIP 5/7] fast-import: extract tree_content reading function

It will be useful to fetch tree contents by a sha1. First, we can check our in-memory tree against it. Second, we may need to read both old and new tree contents and merge them in load_tree.

Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>
---
 fast-import.c |   19 +++++++++++--------
 1 files changed, 11 insertions(+), 8 deletions(-)
Show changes to fast-import.c +11 −8
diff --git a/fast-import.c b/fast-import.c
index d917ea6..9f0d2fe 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1344,19 +1344,14 @@ static const char *get_mode(const char *str, uint16_t *modep)
 	return str;
 }
 
-static void load_tree(struct tree_entry *root)
+static void load_tree_content(struct tree_content **root, unsigned char *sha1)
 {
-	unsigned char *sha1 = root->versions[1].sha1;
 	struct object_entry *myoe;
-	struct tree_content *t;
+	struct tree_content *t = *root;
 	unsigned long size;
 	char *buf;
 	const char *c;
 
-	root->tree = t = new_tree_content(8);
-	if (is_null_sha1(sha1))
-		return;
-
 	myoe = find_object(sha1);
 	if (myoe && myoe->pack_id != MAX_PACK_ID) {
 		if (myoe->type != OBJ_TREE)
@@ -1377,7 +1372,7 @@ static void load_tree(struct tree_entry *root)
 		struct tree_entry *e = new_tree_entry();
 
 		if (t->entry_count == t->entry_capacity)
-			root->tree = t = grow_tree_content(t, t->entry_count);
+			*root = t = grow_tree_content(t, t->entry_count);
 		t->entries[t->entry_count++] = e;
 
 		e->tree = NULL;
@@ -1394,6 +1389,14 @@ static void load_tree(struct tree_entry *root)
 	free(buf);
 }
 
+static void load_tree(struct tree_entry *root)
+{
+	root->tree = t = new_tree_content(8);
+	if (is_null_sha1(sha1))
+		return;
+       load_tree_content(&root->tree, root->versions[1].sha1);
+}
+
 static int tecmp0 (const void *_a, const void *_b)
 {
 	struct tree_entry *a = *((struct tree_entry**)_a);

-- 
1.7.3.4
Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · re: Dmitry Ivankov · lore

[PATCH/WIP 6/7] fast-import: workaround data corruption

fast-import keeps track of some delta-base for tree objects. When it is time to compute the delta, base object is constructed from in-memory tree representation using children's delta bases sha1. But these can be unrelated due to several bugs, and it leads to object with wrong sha1 being delta-written to the packfile.

We have the base sha1 and what we think it's data is. Verify sha1 and if it doesn't match, report it to stderr and don't use delta for this tree.

We could also die() here when bugs are fixed. Or we can see if the data we've got is from our pack file and so still try to use it as a base.

Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>
---
 fast-import.c |   14 +++++++++++++-
 1 files changed, 13 insertions(+), 1 deletions(-)
Show changes to fast-import.c +13 −1
diff --git a/fast-import.c b/fast-import.c
index 9f0d2fe..14a2a63 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1469,7 +1469,8 @@ static void drop_old(struct tree_entry *root)
 static void store_tree(struct tree_entry *root)
 {
 	struct tree_content *t = root->tree;
-	struct last_object lo = { STRBUF_INIT, 0, 0, /* no_swap */ 1 };
+	struct strbuf empty = STRBUF_INIT;
+	struct last_object lo = { empty, 0, 0, /* no_swap */ 1 };
 	struct object_entry *le;
 	unsigned int i;
 
@@ -1486,10 +1487,21 @@ static void store_tree(struct tree_entry *root)
 
 	le = find_object(root->versions[0].sha1);
 	if (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {
+		unsigned char sh[20];
 		mktree(t, 0, &old_tree);
 		lo.data = old_tree;
 		lo.offset = le->idx.offset;
 		lo.depth = t->delta_depth;
+
+		prepare_object_hash(OBJ_TREE, &old_tree, NULL, NULL, sh);
+		if (hashcmp(sh, root->versions[0].sha1)) {
+			fprintf(stderr, "internal sha1 delta base mismatch,"
+					" won't use delta for that tree\n");
+			lo.data = empty;
+			lo.offset = 0;
+			lo.depth = 0;
+		}
+
 	}
 
 	mktree(t, 1, &new_tree);

-- 
1.7.3.4
Jonathan Nieder· Jul 28, 2011, 06:31 UTC · re: Dmitry Ivankov · lore

Re: [PATCH/WIP 6/7] fast-import: workaround data corruption

Hi!
Dmitry Ivankov wrote:
Show 5 quoted lines
> fast-import keeps track of some delta-base for tree objects. When it is
> time to compute the delta, base object is constructed from in-memory
> tree representation using children's delta bases sha1. But these can be
> unrelated due to several bugs, and it leads to object with wrong sha1
> being delta-written to the packfile.

This seems like as good a starting point as any. Small language nitpicks:

 - "some delta-base" is somewhat vague
 - missing article (probably "the") before "base object" and
   "children's"
 - does "children's delta bases sha1" mean "the pre-computed object
   names and modes in versions[0].{sha1,mode} for each tree entry" or
   something else?
 - when you say "unrelated": unrelated to what?
> We have the base sha1 and what we think it's data is. Verify sha1 and if
> it doesn't match, report it to stderr and don't use delta for this tree.

At any rate, if I understand correctly, the idea is that when store_tree() is being called, root->versions[0].sha1 does not match the tree object implied by root->tree->entries[*]->{name,versions[0].{mode,sha1}}. This patch adds a quick check to notice when that happens.

Makes a lot of sense, especially as a demonstration of the problem. store_object() returns early in many cases so this probably does make the bug easier to find (good).

I wonder if it would make more sense to perform this sanity check in store_object() so blobs could benefit, too. How much does the check slow fast-import down (if at all)?

> We could also die() here when bugs are fixed.

If the check is fast, sure, why not? :) The only reason I can think of is that computing a SHA-1 is an O(size of object) cost which it would be nice to avoid if profiling shows it is noticeable.

> Or we can see if the data
> we've got is from our pack file and so still try to use it as a base.

Can you elaborate? When would versions[0].sha1 not match the data but the data still be in the pack file?

> --- a/fast-import.c
> +++ b/fast-import.c
[...]
Show 5 quoted lines
> @@ -1486,10 +1487,21 @@ static void store_tree(struct tree_entry *root)
>  
>  	le = find_object(root->versions[0].sha1);
>  	if (S_ISDIR(root->versions[0].mode) && le && le->pack_id == pack_id) {
> +		unsigned char sh[20];
What does "sh" stand for?
Show 10 quoted lines
>  		mktree(t, 0, &old_tree);
>  		lo.data = old_tree;
>  		lo.offset = le->idx.offset;
>  		lo.depth = t->delta_depth;
> +
> +		prepare_object_hash(OBJ_TREE, &old_tree, NULL, NULL, sh);
> +		if (hashcmp(sh, root->versions[0].sha1)) {
> +			fprintf(stderr, "internal sha1 delta base mismatch,"
> +					" won't use delta for that tree\n");
> +			lo.data = empty;
To avoid a memory leak and introducing an unnecessary variable:
			strbuf_reset(&lo.data);
Thanks, that was interesting.
Dmitry Ivankov· Jul 28, 2011, 04:46 UTC · re: Dmitry Ivankov · lore

[PATCH/WIP 7/7] fast-import: fix data corruption in load_tree

load_tree could be used to load a tree having different base and current sha1. For example it can happens after a parent tree was set by sha1 (it's tree becomes NULL, versions[0].sha1 remain and versions[1].sha1 change). But it doesn't look at versions[0].sha1 and just loads a new version resetting the base one to the new one. This corrupts parent tree delta.

Try to detect that case. Load both base and new trees and merge them together so that mktree is able to produce both base and new trees correctly.

There still may be a delta data corruption. For example tree_content_set with subtree != NULL can produce subtree entries bases and subtree's new parent base mismatch. tree_content_set is used in file_modify_cr - copy and move trees by names. And another place is notes writing thing that does some trees magic too.

Signed-off-by: Dmitry Ivankov <divanorama@gmail.com>
---
 fast-import.c |   68 ++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 60 insertions(+), 8 deletions(-)
Show changes to fast-import.c +60 −8
diff --git a/fast-import.c b/fast-import.c
index 14a2a63..feccd14 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1389,14 +1389,6 @@ static void load_tree_content(struct tree_content **root, unsigned char *sha1)
 	free(buf);
 }
 
-static void load_tree(struct tree_entry *root)
-{
-	root->tree = t = new_tree_content(8);
-	if (is_null_sha1(sha1))
-		return;
-       load_tree_content(&root->tree, root->versions[1].sha1);
-}
-
 static int tecmp0 (const void *_a, const void *_b)
 {
 	struct tree_entry *a = *((struct tree_entry**)_a);
@@ -1442,6 +1434,66 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)
 	}
 }
 
+static void load_tree(struct tree_entry *root)
+{
+	struct tree_content *oldt;
+	size_t n, i, j;
+
+	root->tree = new_tree_content(8);
+	if (is_null_sha1(root->versions[1].sha1)) {
+		if (!S_ISDIR(root->versions[0].mode) || is_null_sha1(root->versions[0].sha1) || !hashcmp(root->versions[0].sha1, root->versions[1].sha1))
+			return;
+		// looks like it is currently unreachable, but let it be for a while
+		load_tree_content(&root->tree, root->versions[0].sha1);
+		for (i = 0; i < root->tree->entry_count; ++i) {
+			root->tree->entries[i]->versions[1].mode = 0;
+			hashclr(root->tree->entries[i]->versions[1].sha1);
+		}
+		return;
+	}
+
+	load_tree_content(&root->tree, root->versions[1].sha1);
+	if (!S_ISDIR(root->versions[0].mode) || is_null_sha1(root->versions[0].sha1) || !hashcmp(root->versions[0].sha1, root->versions[1].sha1))
+ 		return;
+
+	oldt = new_tree_content(8);
+	load_tree_content(&oldt, root->versions[0].sha1);
+
+	qsort(root->tree->entries, root->tree->entry_count, sizeof(root->tree->entries[0]), tecmp1);
+	qsort(oldt->entries, oldt->entry_count, sizeof(oldt->entries[0]), tecmp1);
+
+	n = root->tree->entry_count;
+	i = 0;
+	j = 0;
+	while (i < n || j < oldt->entry_count) {
+		int cmp = i == n ? 1 : j == oldt->entry_count ? -1 : tecmp1(root->tree->entries + i, oldt->entries + j);
+		if (cmp > 0) {
+			if (root->tree->entry_count == root->tree->entry_capacity)
+				root->tree = grow_tree_content(root->tree, root->tree->entry_count);
+			oldt->entries[j]->versions[1].mode = 0;
+			hashclr(oldt->entries[j]->versions[1].sha1);
+			root->tree->entries[root->tree->entry_count++] = oldt->entries[j];
+			oldt->entries[j] = NULL;
+			++j;
+		} else if (cmp < 0) {
+			root->tree->entries[i]->versions[0].mode = 0;
+			hashclr(root->tree->entries[i]->versions[0].sha1);
+			++i;
+		} else {
+			root->tree->entries[i]->versions[0].mode = oldt->entries[j]->versions[1].mode;
+			hashcpy(root->tree->entries[i]->versions[0].sha1, oldt->entries[j]->versions[1].sha1);
+			++i;
+			++j;
+		}
+	}
+	for (j = 0; j < oldt->entry_count; ++j)
+		if (oldt->entries[j]) {
+			release_tree_entry(oldt->entries[j]);
+			oldt->entries[j] = NULL;
+		}
+	release_tree_content(oldt);
+}
+
 static void drop_old(struct tree_entry *root)
 {
 	struct tree_content *t = root->tree;

-- 
1.7.3.4

← back to recent threads