Re: [BUG] fast-import producing very deep tree deltas
"Shawn O. Pearce" <spearce@spearce.org> wrote:
Show 14 quoted lines
> Brian Downing <bdowning@lavos.net> wrote:
> > I've happened upon a case where fast-import produces deep tree deltas.
> > How deep? Really deep. 6035 entries deep to be precise for this case:
> >
> > depths: count 135970 total 120567366 min 0 max 6035 mean 886.72 median 3 std_dev 1653.48
> >
> > 27b8a20bdf39fecd917e8401d3499013e49449d0 tree 32 99609547 6035 0000000000000000000000000000000000000000
> >
> > This was with git-fast-import from 'next' as of a couple days ago,
> > run with the default options (no --depth passed in).
> >
> > Needless to say the pack that resulted was just about useless. Trying to
> > repack it resulted in the "counting objects" phase running at about five
> > objects per second.
Brian, does this fix it?
--8>--
From ff39dd457564b9198344e0cc785afa8cac05b486 Mon Sep 17 00:00:00 2001
From: Shawn O. Pearce <spearce@spearce.org>
Date: Tue, 13 Nov 2007 04:26:24 -0500
Subject: [PATCH] Don't allow fast-import tree delta chains to exceed maximum depth
To: Junio C Hamano <gitster@pobox.com>
Cc: git@vger.kernel.org
Brian Downing noticed fast-import can produce tree depths of up to 6,035 objects and even deeper. Long delta chains can create very small packfiles but cause problems during repacking as git needs to unpack each tree to count the reachable blobs.
What's happening here is the active branch cache isn't big enough. We're swapping out the branch and thus recycling the tree information (struct tree_content) back into the free pool. When we later reload the tree we set the delta_depth to 0 but we kept the tree we just reloaded as a delta base.
So if the tree we reloaded was already at the maximum depth we wouldn't know it and make the new tree a delta. Multiply the number of times the branch cache has to swap out the tree times max_depth (10) and you get the maximum delta depth of a tree created by fast-import. In Brian's case above the active branch cache had to swap the branch out 603/604 times during this import to produce a tree with a delta depth of 6035.
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
fast-import.c | 16 ++++++++++++----
1 files changed, 12 insertions(+), 4 deletions(-)
diff --git a/fast-import.c b/fast-import.c
index f93d7d6..215f1e7 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -153,13 +153,16 @@ Format of STDIN stream:
#define PACK_ID_BITS 16
#define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
+#define DEPTH_BITS 13
+#define MAX_DEPTH ((1<<DEPTH_BITS)-1)
struct object_entry
{
struct object_entry *next;
uint32_t offset;
- unsigned type : TYPE_BITS;
- unsigned pack_id : PACK_ID_BITS;
+ uint32_t type : TYPE_BITS,
+ pack_id : PACK_ID_BITS,
+ depth : DEPTH_BITS;
unsigned char sha1[20];
};
@@ -1084,6 +1087,7 @@ static int store_object(
delta_count_by_type[type]++;
last->depth++;
+ e->depth = last->depth;
hdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);
write_or_die(pack_data->pack_fd, hdr, hdrlen);
@@ -1097,6 +1101,7 @@ static int store_object(
} else {
if (last)
last->depth = 0;
+ e->depth = 0;
hdrlen = encode_header(type, dat->len, hdr);
write_or_die(pack_data->pack_fd, hdr, hdrlen);
pack_size += hdrlen;
@@ -1160,7 +1165,7 @@ static void load_tree(struct tree_entry *root)
if (myoe && myoe->pack_id != MAX_PACK_ID) {
if (myoe->type != OBJ_TREE)
die("Not a tree: %s", sha1_to_hex(sha1));
- t->delta_depth = 0;
+ t->delta_depth = myoe->depth;
buf = gfi_unpack_entry(myoe, &size);
} else {
enum object_type type;
@@ -2289,8 +2294,11 @@ int main(int argc, const char **argv)
}
else if (!prefixcmp(a, "--max-pack-size="))
max_packsize = strtoumax(a + 16, NULL, 0) * 1024 * 1024;
- else if (!prefixcmp(a, "--depth="))
+ else if (!prefixcmp(a, "--depth=")) {
max_depth = strtoul(a + 8, NULL, 0);
+ if (max_depth > MAX_DEPTH)
+ die("--depth cannot exceed %u", MAX_DEPTH);
+ }
else if (!prefixcmp(a, "--active-branches="))
max_active_branches = strtoul(a + 18, NULL, 0);
else if (!prefixcmp(a, "--import-marks="))
--
1.5.3.5.1661.gcbf0
--
Shawn.
Brian Downing
