{"thread":{"id":"10861","subject":"[PATCH] Don't allow fast-import tree delta chains to exceed maximum depth","startedAt":"2007-11-14T04:48:42Z","lastAt":"2007-11-14T05:54:34Z","messageCount":4,"participants":["Shawn O. Pearce","Brian Downing","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"59811","messageId":"20071114044842.GA6876@spearce.org","threadId":"10861","inReplyTo":null,"subject":"[PATCH] Don't allow fast-import tree delta chains to exceed maximum depth","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-11-14T04:48:42Z","receivedAt":"2007-11-14T04:48:42Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Brian Downing noticed fast-import can produce tree depths of up\nto 6,035 objects and even deeper.  Long delta chains can create\nvery small packfiles but cause problems during repacking as git\nneeds to unpack each tree to count the reachable blobs.\n\nWhat's happening here is the active branch cache isn't big enough.\nWe're swapping out the branch and thus recycling the tree information\n(struct tree_content) back into the free pool.  When we later reload\nthe tree we set the delta_depth to 0 but we kept the tree we just\nreloaded as a delta base.\n\nSo if the tree we reloaded was already at the maximum depth we\nwouldn't know it and make the new tree a delta.  Multiply the\nnumber of times the branch cache has to swap out the tree times\nmax_depth (10) and you get the maximum delta depth of a tree created\nby fast-import.  In Brian's case above the active branch cache had\nto swap the branch out 603/604 times during this import to produce\na tree with a delta depth of 6035.\n\nAcked-by: Brian Downing <bdowning@lavos.net>\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n\n Junio, this patch is against maint.  It will apply cleanly to maint\n but is also crafted to ensure it should apply to next with git-am -3.\n Its a real bug that's lasted a long time in fast-import.  I think\n it is maint material.\n\n My fast-import tree is quite behind yours so I would appreciate\n it if you could apply this to your own tree instead of trying to\n fetch things from me.  Thanks.\n\n fast-import.c |   17 ++++++++++++-----\n 1 files changed, 12 insertions(+), 5 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex c07e3d8..7544949 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -154,13 +154,16 @@ Format of STDIN stream:\n \n #define PACK_ID_BITS 16\n #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)\n+#define DEPTH_BITS 13\n+#define MAX_DEPTH ((1<<DEPTH_BITS)-1)\n \n struct object_entry\n {\n \tstruct object_entry *next;\n \tuint32_t offset;\n-\tunsigned type : TYPE_BITS;\n-\tunsigned pack_id : PACK_ID_BITS;\n+\tuint32_t type : TYPE_BITS,\n+\t\tpack_id : PACK_ID_BITS,\n+\t\tdepth : DEPTH_BITS;\n \tunsigned char sha1[20];\n };\n \n@@ -1105,7 +1108,7 @@ static int store_object(\n \t\tunsigned pos = sizeof(hdr) - 1;\n \n \t\tdelta_count_by_type[type]++;\n-\t\tlast->depth++;\n+\t\te->depth = ++last->depth++;\n \n \t\thdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);\n \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n@@ -1117,6 +1120,7 @@ static int store_object(\n \t\twrite_or_die(pack_data->pack_fd, hdr + pos, sizeof(hdr) - pos);\n \t\tpack_size += sizeof(hdr) - pos;\n \t} else {\n+\t\te->depth = 0;\n \t\tif (last)\n \t\t\tlast->depth = 0;\n \t\thdrlen = encode_header(type, datlen, hdr);\n@@ -1181,7 +1185,7 @@ static void load_tree(struct tree_entry *root)\n \tif (myoe && myoe->pack_id != MAX_PACK_ID) {\n \t\tif (myoe->type != OBJ_TREE)\n \t\t\tdie(\"Not a tree: %s\", sha1_to_hex(sha1));\n-\t\tt->delta_depth = 0;\n+\t\tt->delta_depth = myoe->depth;\n \t\tbuf = gfi_unpack_entry(myoe, &size);\n \t} else {\n \t\tenum object_type type;\n@@ -2347,8 +2351,11 @@ int main(int argc, const char **argv)\n \t\t}\n \t\telse if (!prefixcmp(a, \"--max-pack-size=\"))\n \t\t\tmax_packsize = strtoumax(a + 16, NULL, 0) * 1024 * 1024;\n-\t\telse if (!prefixcmp(a, \"--depth=\"))\n+\t\telse if (!prefixcmp(a, \"--depth=\")) {\n \t\t\tmax_depth = strtoul(a + 8, NULL, 0);\n+\t\t\tif (max_depth > MAX_DEPTH)\n+\t\t\t\tdie(\"--depth cannot exceed %u\", MAX_DEPTH);\n+\t\t}\n \t\telse if (!prefixcmp(a, \"--active-branches=\"))\n \t\t\tmax_active_branches = strtoul(a + 18, NULL, 0);\n \t\telse if (!prefixcmp(a, \"--import-marks=\"))\n-- \n1.5.3.5.1728.g34b3e\n"},{"id":"59812","messageId":"20071114054524.GV6212@lavos.net","threadId":"10861","inReplyTo":"20071114044842.GA6876@spearce.org","subject":"Re: [PATCH] Don't allow fast-import tree delta chains to exceed maximum depth","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-11-14T05:45:24Z","receivedAt":"2007-11-14T05:45:24Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Tue, Nov 13, 2007 at 11:48:42PM -0500, Shawn O. Pearce wrote:\n> @@ -1105,7 +1108,7 @@ static int store_object(\n>  \t\tunsigned pos = sizeof(hdr) - 1;\n>  \n>  \t\tdelta_count_by_type[type]++;\n> -\t\tlast->depth++;\n> +\t\te->depth = ++last->depth++;\n>  \n>  \t\thdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);\n>  \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n\nI'm not sure, but I think that's too many ++'s.\n\nThe earlier patch had:\n\n@@ -1084,6 +1087,7 @@ static int store_object(\n\n                delta_count_by_type[type]++;\n                last->depth++;\n+               e->depth = last->depth;\n\n                hdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);\n                write_or_die(pack_data->pack_fd, hdr, hdrlen);\n\nWhich of course would be the equivalent of:\n\n> +\t\te->depth = ++last->depth;\n\nMaybe there's some cleverness here I'm missing, though.\n\n-bcd\n"},{"id":"59813","messageId":"7vhcjpnzvq.fsf@gitster.siamese.dyndns.org","threadId":"10861","inReplyTo":"20071114044842.GA6876@spearce.org","subject":"Re: [PATCH] Don't allow fast-import tree delta chains to exceed maximum depth","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-14T05:46:01Z","receivedAt":"2007-11-14T05:46:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n>  Junio, this patch is against maint.  It will apply cleanly to maint\n>  but is also crafted to ensure it should apply to next with git-am -3.\n>  Its a real bug that's lasted a long time in fast-import.  I think\n>  it is maint material.\n\nThanks.\n\n> diff --git a/fast-import.c b/fast-import.c\n> index c07e3d8..7544949 100644\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -154,13 +154,16 @@ Format of STDIN stream:\n>  \n>  #define PACK_ID_BITS 16\n>  #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)\n> +#define DEPTH_BITS 13\n> +#define MAX_DEPTH ((1<<DEPTH_BITS)-1)\n>  \n>  struct object_entry\n>  {\n>  \tstruct object_entry *next;\n>  \tuint32_t offset;\n> -\tunsigned type : TYPE_BITS;\n> -\tunsigned pack_id : PACK_ID_BITS;\n> +\tuint32_t type : TYPE_BITS,\n> +\t\tpack_id : PACK_ID_BITS,\n> +\t\tdepth : DEPTH_BITS;\n>  \tunsigned char sha1[20];\n>  };\n\nuint32_t with bit-width specifiers look somewhat funny here...\n\n>  \n> @@ -1105,7 +1108,7 @@ static int store_object(\n>  \t\tunsigned pos = sizeof(hdr) - 1;\n>  \n>  \t\tdelta_count_by_type[type]++;\n> -\t\tlast->depth++;\n> +\t\te->depth = ++last->depth++;\n\n\"lvalue required as increment operand\"?\n\nWouldn't it be easier to read like this?\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 7544949..d32c412 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -161,7 +161,7 @@ struct object_entry\n {\n \tstruct object_entry *next;\n \tuint32_t offset;\n-\tuint32_t type : TYPE_BITS,\n+\tunsigned type : TYPE_BITS,\n \t\tpack_id : PACK_ID_BITS,\n \t\tdepth : DEPTH_BITS;\n \tunsigned char sha1[20];\n@@ -1108,7 +1108,7 @@ static int store_object(\n \t\tunsigned pos = sizeof(hdr) - 1;\n \n \t\tdelta_count_by_type[type]++;\n-\t\te->depth = ++last->depth++;\n+\t\te->depth = last->depth + 1;\n \n \t\thdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);\n \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n@@ -1121,8 +1121,6 @@ static int store_object(\n \t\tpack_size += sizeof(hdr) - pos;\n \t} else {\n \t\te->depth = 0;\n-\t\tif (last)\n-\t\t\tlast->depth = 0;\n \t\thdrlen = encode_header(type, datlen, hdr);\n \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n \t\tpack_size += hdrlen;\n@@ -1138,6 +1136,7 @@ static int store_object(\n \t\t\tfree(last->data);\n \t\tlast->data = dat;\n \t\tlast->offset = e->offset;\n+\t\tlast->depth = e->depth;\n \t\tlast->len = datlen;\n \t}\n \treturn 0;\n"},{"id":"59815","messageId":"20071114055434.GG14735@spearce.org","threadId":"10861","inReplyTo":"7vhcjpnzvq.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Don't allow fast-import tree delta chains to exceed maximum depth","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-11-14T05:54:34Z","receivedAt":"2007-11-14T05:54:34Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <gitster@pobox.com> wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> > +\tuint32_t type : TYPE_BITS,\n> > +\t\tpack_id : PACK_ID_BITS,\n> > +\t\tdepth : DEPTH_BITS;\n> \n> uint32_t with bit-width specifiers look somewhat funny here...\n\nSure.  But the prior item is also uint32_t and before that a pointer\nso it aligns out nice.  And we're using exactly 32 bits in this field.\nSo it just sort of made sense to me to declare it was a uint32_t.\n \n> > @@ -1105,7 +1108,7 @@ static int store_object(\n> >  \t\tunsigned pos = sizeof(hdr) - 1;\n> >  \n> >  \t\tdelta_count_by_type[type]++;\n> > -\t\tlast->depth++;\n> > +\t\te->depth = ++last->depth++;\n> \n> \"lvalue required as increment operand\"?\n> \n> Wouldn't it be easier to read like this?\n\nYes.  Good call.  :-)\n \n> diff --git a/fast-import.c b/fast-import.c\n> index 7544949..d32c412 100644\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -161,7 +161,7 @@ struct object_entry\n>  {\n>  \tstruct object_entry *next;\n>  \tuint32_t offset;\n> -\tuint32_t type : TYPE_BITS,\n> +\tunsigned type : TYPE_BITS,\n>  \t\tpack_id : PACK_ID_BITS,\n>  \t\tdepth : DEPTH_BITS;\n>  \tunsigned char sha1[20];\n> @@ -1108,7 +1108,7 @@ static int store_object(\n>  \t\tunsigned pos = sizeof(hdr) - 1;\n>  \n>  \t\tdelta_count_by_type[type]++;\n> -\t\te->depth = ++last->depth++;\n> +\t\te->depth = last->depth + 1;\n>  \n>  \t\thdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);\n>  \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n> @@ -1121,8 +1121,6 @@ static int store_object(\n>  \t\tpack_size += sizeof(hdr) - pos;\n>  \t} else {\n>  \t\te->depth = 0;\n> -\t\tif (last)\n> -\t\t\tlast->depth = 0;\n>  \t\thdrlen = encode_header(type, datlen, hdr);\n>  \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n>  \t\tpack_size += hdrlen;\n> @@ -1138,6 +1136,7 @@ static int store_object(\n>  \t\t\tfree(last->data);\n>  \t\tlast->data = dat;\n>  \t\tlast->offset = e->offset;\n> +\t\tlast->depth = e->depth;\n>  \t\tlast->len = datlen;\n>  \t}\n>  \treturn 0;\n\n-- \nShawn.\n"}]}