{"thread":{"id":"15940","subject":"[PATCH 1/2] index-pack: rationalize delta resolution code","startedAt":"2008-10-17T19:57:57Z","lastAt":"2008-10-17T19:57:58Z","messageCount":2,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"93310","messageId":"1224273478-18384-1-git-send-email-nico@cam.org","threadId":"15940","inReplyTo":null,"subject":"[PATCH 1/2] index-pack: rationalize delta resolution code","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-10-17T19:57:57Z","receivedAt":"2008-10-17T19:57:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Instead of having strange loops for walking unresolved deltas with the\nsame base duplicated in many places, let's rework the code so this is\ndone in a single place instead.  This simplifies callers quite a bit too.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n index-pack.c |  123 +++++++++++++++++++++++++++------------------------------\n 1 files changed, 58 insertions(+), 65 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex d3a4d31..82843e7 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -244,7 +244,8 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n \n \tc->base = base;\n \tc->child = NULL;\n-\tbase_cache_used += c->size;\n+\tif (c->data)\n+\t\tbase_cache_used += c->size;\n \tprune_base_data(c);\n }\n \n@@ -494,8 +495,10 @@ static void *get_base_data(struct base_data *c)\n \t\t\tfree(raw);\n \t\t\tif (!c->data)\n \t\t\t\tbad_object(obj->idx.offset, \"failed to apply delta\");\n-\t\t} else\n+\t\t} else {\n \t\t\tc->data = get_data_from_pack(obj);\n+\t\t\tc->size = obj->size;\n+\t\t}\n \n \t\tbase_cache_used += c->size;\n \t\tprune_base_data(c);\n@@ -504,49 +507,73 @@ static void *get_base_data(struct base_data *c)\n }\n \n static void resolve_delta(struct object_entry *delta_obj,\n-\t\t\t  struct base_data *base_obj, enum object_type type)\n+\t\t\t  struct base_data *base, struct base_data *result)\n {\n \tvoid *delta_data;\n \tunsigned long delta_size;\n-\tunion delta_base delta_base;\n-\tint j, first, last;\n-\tstruct base_data result;\n \n-\tdelta_obj->real_type = type;\n+\tdelta_obj->real_type = base->obj->type;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tdelta_size = delta_obj->size;\n-\tresult.data = patch_delta(get_base_data(base_obj), base_obj->size,\n-\t\t\t     delta_data, delta_size,\n-\t\t\t     &result.size);\n+\tresult->obj = delta_obj;\n+\tresult->data = patch_delta(get_base_data(base), base->obj->size,\n+\t\t\t\t   delta_data, delta_size, &result->size);\n \tfree(delta_data);\n-\tif (!result.data)\n+\tif (!result->data)\n \t\tbad_object(delta_obj->idx.offset, \"failed to apply delta\");\n-\tsha1_object(result.data, result.size, type, delta_obj->idx.sha1);\n+\tsha1_object(result->data, result->size, delta_obj->real_type,\n+\t\t    delta_obj->idx.sha1);\n \tnr_resolved_deltas++;\n+}\n+\n+static void find_unresolved_deltas(struct base_data *base,\n+\t\t\t\t   struct base_data *prev_base)\n+{\n+\tint i, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;\n+\n+\t/*\n+\t * This is a recursive function. Those brackets should help reducing\n+\t * stack usage by limiting the scope of the delta_base union.\n+\t */\n+\t{\n+\t\tunion delta_base base_spec;\n+\n+\t\thashcpy(base_spec.sha1, base->obj->idx.sha1);\n+\t\tref = !find_delta_children(&base_spec, &ref_first, &ref_last);\n+\n+\t\tmemset(&base_spec, 0, sizeof(base_spec));\n+\t\tbase_spec.offset = base->obj->idx.offset;\n+\t\tofs = !find_delta_children(&base_spec, &ofs_first, &ofs_last);\n+\t}\n+\n+\tif (!ref && !ofs)\n+\t\treturn;\n \n-\tresult.obj = delta_obj;\n-\tlink_base_data(base_obj, &result);\n+\tlink_base_data(prev_base, base);\n \n-\thashcpy(delta_base.sha1, delta_obj->idx.sha1);\n-\tif (!find_delta_children(&delta_base, &first, &last)) {\n-\t\tfor (j = first; j <= last; j++) {\n-\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n-\t\t\tif (child->real_type == OBJ_REF_DELTA)\n-\t\t\t\tresolve_delta(child, &result, type);\n+\tif (ref) {\n+\t\tfor (i = ref_first; i <= ref_last; i++) {\n+\t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n+\t\t\tif (child->real_type == OBJ_REF_DELTA) {\n+\t\t\t\tstruct base_data result;\n+\t\t\t\tresolve_delta(child, base, &result);\n+\t\t\t\tfind_unresolved_deltas(&result, base);\n+\t\t\t}\n \t\t}\n \t}\n \n-\tmemset(&delta_base, 0, sizeof(delta_base));\n-\tdelta_base.offset = delta_obj->idx.offset;\n-\tif (!find_delta_children(&delta_base, &first, &last)) {\n-\t\tfor (j = first; j <= last; j++) {\n-\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n-\t\t\tif (child->real_type == OBJ_OFS_DELTA)\n-\t\t\t\tresolve_delta(child, &result, type);\n+\tif (ofs) {\n+\t\tfor (i = ofs_first; i <= ofs_last; i++) {\n+\t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n+\t\t\tif (child->real_type == OBJ_OFS_DELTA) {\n+\t\t\t\tstruct base_data result;\n+\t\t\t\tresolve_delta(child, base, &result);\n+\t\t\t\tfind_unresolved_deltas(&result, base);\n+\t\t\t}\n \t\t}\n \t}\n \n-\tunlink_base_data(&result);\n+\tunlink_base_data(base);\n }\n \n static int compare_delta_entry(const void *a, const void *b)\n@@ -622,37 +649,13 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\tprogress = start_progress(\"Resolving deltas\", nr_deltas);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tunion delta_base base;\n-\t\tint j, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;\n \t\tstruct base_data base_obj;\n \n \t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA)\n \t\t\tcontinue;\n-\t\thashcpy(base.sha1, obj->idx.sha1);\n-\t\tref = !find_delta_children(&base, &ref_first, &ref_last);\n-\t\tmemset(&base, 0, sizeof(base));\n-\t\tbase.offset = obj->idx.offset;\n-\t\tofs = !find_delta_children(&base, &ofs_first, &ofs_last);\n-\t\tif (!ref && !ofs)\n-\t\t\tcontinue;\n-\t\tbase_obj.data = get_data_from_pack(obj);\n-\t\tbase_obj.size = obj->size;\n \t\tbase_obj.obj = obj;\n-\t\tlink_base_data(NULL, &base_obj);\n-\n-\t\tif (ref)\n-\t\t\tfor (j = ref_first; j <= ref_last; j++) {\n-\t\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n-\t\t\t\tif (child->real_type == OBJ_REF_DELTA)\n-\t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n-\t\t\t}\n-\t\tif (ofs)\n-\t\t\tfor (j = ofs_first; j <= ofs_last; j++) {\n-\t\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n-\t\t\t\tif (child->real_type == OBJ_OFS_DELTA)\n-\t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n-\t\t\t}\n-\t\tunlink_base_data(&base_obj);\n+\t\tbase_obj.data = NULL;\n+\t\tfind_unresolved_deltas(&base_obj, NULL);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n }\n@@ -745,7 +748,6 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \tfor (i = 0; i < n; i++) {\n \t\tstruct delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n-\t\tint j, first, last;\n \t\tstruct base_data base_obj;\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n@@ -759,16 +761,7 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n \t\tbase_obj.obj = append_obj_to_pack(f, d->base.sha1,\n \t\t\t\t\tbase_obj.data, base_obj.size, type);\n-\t\tlink_base_data(NULL, &base_obj);\n-\n-\t\tfind_delta_children(&d->base, &first, &last);\n-\t\tfor (j = first; j <= last; j++) {\n-\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n-\t\t\tif (child->real_type == OBJ_REF_DELTA)\n-\t\t\t\tresolve_delta(child, &base_obj, type);\n-\t\t}\n-\n-\t\tunlink_base_data(&base_obj);\n+\t\tfind_unresolved_deltas(&base_obj, NULL);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n1.6.0.2.711.gf1ba4\n"},{"id":"93311","messageId":"1224273478-18384-2-git-send-email-nico@cam.org","threadId":"15940","inReplyTo":"1224273478-18384-1-git-send-email-nico@cam.org","subject":"[PATCH 2/2] index-pack: smarter memory usage during delta resolution","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-10-17T19:57:58Z","receivedAt":"2008-10-17T19:57:58Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"There is no need to keep the base object data around after its last delta\nhas been resolved.  This also means that long delta chains with only one\ndelta per base won't grow the cache size unnecessarily as the base will\nbe freed before recursing down.\n\nTo make it easy, find_delta_children() is modified so the first and last\nindices are initialized in all cases.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n index-pack.c |   73 +++++++++++++++++++++++++++++++---------------------------\n 1 files changed, 39 insertions(+), 34 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex 82843e7..9def641 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -221,17 +221,23 @@ static void bad_object(unsigned long offset, const char *format, ...)\n \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n }\n \n+static void free_base_data(struct base_data *c)\n+{\n+\tif (c->data) {\n+\t\tfree(c->data);\n+\t\tc->data = NULL;\n+\t\tbase_cache_used -= c->size;\n+\t}\n+}\n+\n static void prune_base_data(struct base_data *retain)\n {\n \tstruct base_data *b = base_cache;\n \tfor (b = base_cache;\n \t     base_cache_used > delta_base_cache_limit && b;\n \t     b = b->child) {\n-\t\tif (b->data && b != retain) {\n-\t\t\tfree(b->data);\n-\t\t\tb->data = NULL;\n-\t\t\tbase_cache_used -= b->size;\n-\t\t}\n+\t\tif (b->data && b != retain)\n+\t\t\tfree_base_data(b);\n \t}\n }\n \n@@ -256,10 +262,7 @@ static void unlink_base_data(struct base_data *c)\n \t\tbase->child = NULL;\n \telse\n \t\tbase_cache = NULL;\n-\tif (c->data) {\n-\t\tfree(c->data);\n-\t\tbase_cache_used -= c->size;\n-\t}\n+\tfree_base_data(c);\n }\n \n static void *unpack_entry_data(unsigned long offset, unsigned long size)\n@@ -409,22 +412,24 @@ static int find_delta(const union delta_base *base)\n         return -first-1;\n }\n \n-static int find_delta_children(const union delta_base *base,\n-\t\t\t       int *first_index, int *last_index)\n+static void find_delta_children(const union delta_base *base,\n+\t\t\t\tint *first_index, int *last_index)\n {\n \tint first = find_delta(base);\n \tint last = first;\n \tint end = nr_deltas - 1;\n \n-\tif (first < 0)\n-\t\treturn -1;\n+\tif (first < 0) {\n+\t\t*first_index = 0;\n+\t\t*last_index = -1;\n+\t\treturn;\n+\t}\n \twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))\n \t\t--first;\n \twhile (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))\n \t\t++last;\n \t*first_index = first;\n \t*last_index = last;\n-\treturn 0;\n }\n \n static void sha1_object(const void *data, unsigned long size,\n@@ -529,7 +534,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n static void find_unresolved_deltas(struct base_data *base,\n \t\t\t\t   struct base_data *prev_base)\n {\n-\tint i, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;\n+\tint i, ref_first, ref_last, ofs_first, ofs_last;\n \n \t/*\n \t * This is a recursive function. Those brackets should help reducing\n@@ -539,37 +544,37 @@ static void find_unresolved_deltas(struct base_data *base,\n \t\tunion delta_base base_spec;\n \n \t\thashcpy(base_spec.sha1, base->obj->idx.sha1);\n-\t\tref = !find_delta_children(&base_spec, &ref_first, &ref_last);\n+\t\tfind_delta_children(&base_spec, &ref_first, &ref_last);\n \n \t\tmemset(&base_spec, 0, sizeof(base_spec));\n \t\tbase_spec.offset = base->obj->idx.offset;\n-\t\tofs = !find_delta_children(&base_spec, &ofs_first, &ofs_last);\n+\t\tfind_delta_children(&base_spec, &ofs_first, &ofs_last);\n \t}\n \n-\tif (!ref && !ofs)\n+\tif (ref_last == -1 && ofs_last == -1)\n \t\treturn;\n \n \tlink_base_data(prev_base, base);\n \n-\tif (ref) {\n-\t\tfor (i = ref_first; i <= ref_last; i++) {\n-\t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n-\t\t\tif (child->real_type == OBJ_REF_DELTA) {\n-\t\t\t\tstruct base_data result;\n-\t\t\t\tresolve_delta(child, base, &result);\n-\t\t\t\tfind_unresolved_deltas(&result, base);\n-\t\t\t}\n+\tfor (i = ref_first; i <= ref_last; i++) {\n+\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n+\t\tif (child->real_type == OBJ_REF_DELTA) {\n+\t\t\tstruct base_data result;\n+\t\t\tresolve_delta(child, base, &result);\n+\t\t\tif (i == ref_last && ofs_last == -1)\n+\t\t\t\tfree_base_data(base);\n+\t\t\tfind_unresolved_deltas(&result, base);\n \t\t}\n \t}\n \n-\tif (ofs) {\n-\t\tfor (i = ofs_first; i <= ofs_last; i++) {\n-\t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n-\t\t\tif (child->real_type == OBJ_OFS_DELTA) {\n-\t\t\t\tstruct base_data result;\n-\t\t\t\tresolve_delta(child, base, &result);\n-\t\t\t\tfind_unresolved_deltas(&result, base);\n-\t\t\t}\n+\tfor (i = ofs_first; i <= ofs_last; i++) {\n+\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n+\t\tif (child->real_type == OBJ_OFS_DELTA) {\n+\t\t\tstruct base_data result;\n+\t\t\tresolve_delta(child, base, &result);\n+\t\t\tif (i == ofs_last)\n+\t\t\t\tfree_base_data(base);\n+\t\t\tfind_unresolved_deltas(&result, base);\n \t\t}\n \t}\n \n-- \n1.6.0.2.711.gf1ba4\n"}]}