{"thread":{"id":"7688","subject":"[PATCH 3/9] pack-objects: rework check_delta_limit usage","startedAt":"2007-04-16T16:14:51Z","lastAt":"2007-04-16T16:14:51Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":9},"messages":[{"id":"39543","messageId":"S1030820AbXDPQOz/20070416161455Z+63@vger.kernel.org","threadId":"7688","inReplyTo":null,"subject":"[PATCH 3/9] pack-objects: rework check_delta_limit usage","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-16T16:14:51Z","receivedAt":"2007-04-16T16:14:51Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Objects that have delta \"children\" from pack data reuse must consider the\ndepth of their deepest child when they try to deltify themselves for those\nchildren not to become too deep.\n\nHowever, in the context of a \"thin\" pack, the delta children depth was\nskipped entirely on the presumption that the pack was always going to be\nexploded on the receiving end, hence the delta length wasn't an issue.\n\nNow that we keep received packs as is and reuse pack data when repacking,\nthose packs do contain delta chains that are longer than expected. Worse,\nthose delta chain may even grow longer when the pack is further repacked\ninto another thin pack for a subsequent transmission.\n\nSo this patch restores strict delta length even for thin packs, and it\nmoves check_delta_limit() usage directly in the delta loop where it is\nneeded.  This way the delta_limit can be removed from struct object_entry\nas well.  Oh and the initial value was wrong too.\n\nThe  progress_interval() function was moved to a more logical location in\nthe process.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |   76 ++++++++++++++++++++---------------------------\n 1 files changed, 32 insertions(+), 44 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 869ca1a..d44b8f4 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -27,7 +27,6 @@ struct object_entry {\n \t\t\t\t * nonzero if already written.\n \t\t\t\t */\n \tunsigned int depth;\t/* delta depth */\n-\tunsigned int delta_limit;\t/* base adjustment for in-pack delta */\n \tunsigned int hash;\t/* name hint hash */\n \tenum object_type type;\n \tenum object_type in_pack_type;\t/* could be delta */\n@@ -1172,19 +1171,6 @@ static void check_object(struct object_entry *entry)\n \t\t    sha1_to_hex(entry->sha1));\n }\n \n-static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n-{\n-\tstruct object_entry *child = me->delta_child;\n-\tunsigned int m = n;\n-\twhile (child) {\n-\t\tunsigned int c = check_delta_limit(child, n + 1);\n-\t\tif (m < c)\n-\t\t\tm = c;\n-\t\tchild = child->delta_sibling;\n-\t}\n-\treturn m;\n-}\n-\n static void get_object_details(void)\n {\n \tuint32_t i;\n@@ -1193,23 +1179,6 @@ static void get_object_details(void)\n \tprepare_pack_ix();\n \tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n \t\tcheck_object(entry);\n-\n-\tif (nr_objects == nr_result) {\n-\t\t/*\n-\t\t * Depth of objects that depend on the entry -- this\n-\t\t * is subtracted from depth-max to break too deep\n-\t\t * delta chain because of delta data reusing.\n-\t\t * However, we loosen this restriction when we know we\n-\t\t * are creating a thin pack -- it will have to be\n-\t\t * expanded on the other end anyway, so do not\n-\t\t * artificially cut the delta chain and let it go as\n-\t\t * deep as it wants.\n-\t\t */\n-\t\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n-\t\t\tif (!entry->delta && entry->delta_child)\n-\t\t\t\tentry->delta_limit =\n-\t\t\t\t\tcheck_delta_limit(entry, 1);\n-\t}\n }\n \n typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);\n@@ -1322,16 +1291,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t    trg_entry->in_pack_type != OBJ_OFS_DELTA)\n \t\treturn 0;\n \n-\t/*\n-\t * If the current object is at pack edge, take the depth the\n-\t * objects that depend on the current object into account --\n-\t * otherwise they would become too deep.\n-\t */\n-\tif (trg_entry->delta_child) {\n-\t\tif (max_depth <= trg_entry->delta_limit)\n-\t\t\treturn 0;\n-\t\tmax_depth -= trg_entry->delta_limit;\n-\t}\n+\t/* Let's not bust the allowed depth. */\n \tif (src_entry->depth >= max_depth)\n \t\treturn 0;\n \n@@ -1378,9 +1338,17 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \treturn 1;\n }\n \n-static void progress_interval(int signum)\n+static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n {\n-\tprogress_update = 1;\n+\tstruct object_entry *child = me->delta_child;\n+\tunsigned int m = n;\n+\twhile (child) {\n+\t\tunsigned int c = check_delta_limit(child, n + 1);\n+\t\tif (m < c)\n+\t\t\tm = c;\n+\t\tchild = child->delta_sibling;\n+\t}\n+\treturn m;\n }\n \n static void find_deltas(struct object_entry **list, int window, int depth)\n@@ -1389,6 +1357,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n \tunsigned last_percent = 999;\n+\tint max_depth;\n \n \tif (!nr_objects)\n \t\treturn;\n@@ -1429,6 +1398,18 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\tn->data = NULL;\n \t\tn->entry = entry;\n \n+\t\t/*\n+\t\t * If the current object is at pack edge, take the depth the\n+\t\t * objects that depend on the current object into account\n+\t\t * otherwise they would become too deep.\n+\t\t */\n+\t\tmax_depth = depth;\n+\t\tif (entry->delta_child) {\n+\t\t\tmax_depth -= check_delta_limit(entry, 0);\n+\t\t\tif (max_depth <= 0)\n+\t\t\t\tgoto next;\n+\t\t}\n+\n \t\tj = window;\n \t\twhile (--j > 0) {\n \t\t\tuint32_t other_idx = idx + j;\n@@ -1438,9 +1419,10 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\t\tm = array + other_idx;\n \t\t\tif (!m->entry)\n \t\t\t\tbreak;\n-\t\t\tif (try_delta(n, m, depth) < 0)\n+\t\t\tif (try_delta(n, m, max_depth) < 0)\n \t\t\t\tbreak;\n \t\t}\n+\n \t\t/* if we made n a delta, and if n is already at max\n \t\t * depth, leaving it in the window is pointless.  we\n \t\t * should evict it first.\n@@ -1448,6 +1430,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\tif (entry->delta && depth <= entry->depth)\n \t\t\tcontinue;\n \n+\t\tnext:\n \t\tidx++;\n \t\tif (idx >= window)\n \t\t\tidx = 0;\n@@ -1525,6 +1508,11 @@ static int reuse_cached_pack(unsigned char *sha1)\n \treturn 1;\n }\n \n+static void progress_interval(int signum)\n+{\n+\tprogress_update = 1;\n+}\n+\n static void setup_progress_signal(void)\n {\n \tstruct sigaction sa;\n-- \n1.5.1.1.781.g65e8\n"}]}