{"thread":{"id":"26391","subject":"Q on \"index-pack: smarter memory usage during delta resolution, 2008-10-17\"","startedAt":"2011-02-02T18:11:26Z","lastAt":"2011-02-03T05:22:56Z","messageCount":2,"participants":["Junio C Hamano","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"160280","messageId":"7vfws6xq5t.fsf@alter.siamese.dyndns.org","threadId":"26391","inReplyTo":null,"subject":"Q on \"index-pack: smarter memory usage during delta resolution, 2008-10-17\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-02-02T18:11:26Z","receivedAt":"2011-02-02T18:11:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In find_unresolved_deltas(), there are two loops that walk the range of deltas[]\narray that potentially share the same base object.  One loop for ref-delta\nlooks like this:\n\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\nI was wondering what happens when the entry at ref_last was a false match\n(i.e. the \"union delta_base\" happened to have the same 20-byte pattern but\nwas of a wrong kind).\n\nThe other loop for ofs-delta has the same \"if (i == ofs_last)\" condition.\n\nAdmittedly this is rather hard to trigger (you have to find an object\nas a ofs-delta base object, and then come up with another object whose\nobject name is the same as the offset of the first base object followed\nby bunch of '\\0' and use it as a ref-delta base), and even if it did, it\nwill only retain the memory for slightly longer time in the function.\n\nIs a patch along the following line worth doing, I wonder.\n\n-- >8 --\nSubject: index-pack: group the delta-base array entries also by type\n\nEntries in the delta_base array are only grouped by the bytepattern in\nthe delta_base union, some of which have 20-byte object name of the base\nobject (i.e. base for REF_DELTA objects), while others have sizeof(off_t)\nbytes followed by enough NULs to fill 20-byte.  The loops to iterate\nthrough a range inside this array still needs to inspect the type of the\ndelta, and skip over false hits.\n\nGroup the entries also by type to eliminate the potential of false hits.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/index-pack.c |   61 ++++++++++++++++++++++++++++++++-----------------\n 1 files changed, 40 insertions(+), 21 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 8dc5c0b..1b5d83a 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -391,7 +391,18 @@ static void *get_data_from_pack(struct object_entry *obj)\n \treturn data;\n }\n \n-static int find_delta(const union delta_base *base)\n+static int compare_delta_bases(const union delta_base *base1,\n+\t\t\t       const union delta_base *base2,\n+\t\t\t       enum object_type type1,\n+\t\t\t       enum object_type type2)\n+{\n+\tint cmp = type1 - type2;\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn memcmp(base1, base2, UNION_BASE_SZ);\n+}\n+\n+static int find_delta(const union delta_base *base, enum object_type type)\n {\n \tint first = 0, last = nr_deltas;\n \n@@ -400,7 +411,8 @@ static int find_delta(const union delta_base *base)\n                 struct delta_entry *delta = &deltas[next];\n                 int cmp;\n \n-                cmp = memcmp(base, &delta->base, UNION_BASE_SZ);\n+\t\tcmp = compare_delta_bases(base, &delta->base,\n+\t\t\t\t\t  type, objects[delta->obj_no].type);\n                 if (!cmp)\n                         return next;\n                 if (cmp < 0) {\n@@ -413,9 +425,10 @@ static int find_delta(const union delta_base *base)\n }\n \n static void find_delta_children(const union delta_base *base,\n-\t\t\t\tint *first_index, int *last_index)\n+\t\t\t\tint *first_index, int *last_index,\n+\t\t\t\tenum object_type type)\n {\n-\tint first = find_delta(base);\n+\tint first = find_delta(base, type);\n \tint last = first;\n \tint end = nr_deltas - 1;\n \n@@ -543,11 +556,13 @@ 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\tfind_delta_children(&base_spec, &ref_first, &ref_last);\n+\t\tfind_delta_children(&base_spec,\n+\t\t\t\t    &ref_first, &ref_last, OBJ_REF_DELTA);\n \n \t\tmemset(&base_spec, 0, sizeof(base_spec));\n \t\tbase_spec.offset = base->obj->idx.offset;\n-\t\tfind_delta_children(&base_spec, &ofs_first, &ofs_last);\n+\t\tfind_delta_children(&base_spec,\n+\t\t\t\t    &ofs_first, &ofs_last, OBJ_OFS_DELTA);\n \t}\n \n \tif (ref_last == -1 && ofs_last == -1) {\n@@ -559,24 +574,24 @@ static void find_unresolved_deltas(struct base_data *base,\n \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\tstruct base_data result;\n+\n+\t\tassert(child->real_type == OBJ_REF_DELTA);\n+\t\tresolve_delta(child, base, &result);\n+\t\tif (i == ref_last && ofs_last == -1)\n+\t\t\tfree_base_data(base);\n+\t\tfind_unresolved_deltas(&result, base);\n \t}\n \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\tstruct base_data result;\n+\n+\t\tassert(child->real_type == OBJ_OFS_DELTA);\n+\t\tresolve_delta(child, base, &result);\n+\t\tif (i == ofs_last)\n+\t\t\tfree_base_data(base);\n+\t\tfind_unresolved_deltas(&result, base);\n \t}\n \n \tunlink_base_data(base);\n@@ -586,7 +601,11 @@ static int compare_delta_entry(const void *a, const void *b)\n {\n \tconst struct delta_entry *delta_a = a;\n \tconst struct delta_entry *delta_b = b;\n-\treturn memcmp(&delta_a->base, &delta_b->base, UNION_BASE_SZ);\n+\n+\t/* group by type (ref vs ofs) and then by value (sha-1 or offset) */\n+\treturn compare_delta_bases(&delta_a->base, &delta_b->base,\n+\t\t\t\t   objects[delta_a->obj_no].type,\n+\t\t\t\t   objects[delta_b->obj_no].type);\n }\n \n /* Parse all objects and return the pack content SHA1 hash */\n"},{"id":"160307","messageId":"alpine.LFD.2.00.1102022330330.12104@xanadu.home","threadId":"26391","inReplyTo":"7vfws6xq5t.fsf@alter.siamese.dyndns.org","subject":"Re: Q on \"index-pack: smarter memory usage during delta resolution, 2008-10-17\"","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2011-02-03T05:22:56Z","receivedAt":"2011-02-03T05:22:56Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 2 Feb 2011, Junio C Hamano wrote:\n\n> In find_unresolved_deltas(), there are two loops that walk the range of deltas[]\n> array that potentially share the same base object.  One loop for ref-delta\n> looks like this:\n> \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> I was wondering what happens when the entry at ref_last was a false match\n> (i.e. the \"union delta_base\" happened to have the same 20-byte pattern but\n> was of a wrong kind).\n\nI've never seen that in practice.  You'd need at least one object with a \nSHA1 made of 12 trailing zero bytes out of 20 to start with. I'm \nchallenging you to find such an object.  ;-)  But let's pretend this may \nhappen in theory, and that's why the test is there.\n\n> The other loop for ofs-delta has the same \"if (i == ofs_last)\" condition.\n\nNo, it is not exactly the same.  The first loop walk the deltas list in \nthe range of deltas requiring the current object for base by SHA1 \nreference.  Once it is done resolving all those deltas it may free this \nbase object's memory, but _only_ if it is _not_ also required by the \nsecond loop.  That is expressed by ofs_last == -1 meaning that the ofs \nrange is empty.\n\nThe second loop does the same, but in the range of deltas requiring this \nbase by offset reference.  Once it is over with it then it may free the \nbase right away.\n\nOf course, in practice only one of those 2 loops will actually be \nentered, as only one between the SHA1 ref range or the offset ref range \nwill possibly be non empty.\n\n> Admittedly this is rather hard to trigger (you have to find an object\n> as a ofs-delta base object, and then come up with another object whose\n> object name is the same as the offset of the first base object followed\n> by bunch of '\\0' and use it as a ref-delta base), and even if it did, it\n> will only retain the memory for slightly longer time in the function.\n\nRight.  If you ever manage to create such a condition you're probably up \nfor cracking SHA1 entirely.  But for all purposes this is probably never \ngoing to happen.\n\n> Is a patch along the following line worth doing, I wonder.\n> \n> -- >8 --\n> Subject: index-pack: group the delta-base array entries also by type\n> \n> Entries in the delta_base array are only grouped by the bytepattern in\n> the delta_base union, some of which have 20-byte object name of the base\n> object (i.e. base for REF_DELTA objects), while others have sizeof(off_t)\n> bytes followed by enough NULs to fill 20-byte.  The loops to iterate\n> through a range inside this array still needs to inspect the type of the\n> delta, and skip over false hits.\n> \n> Group the entries also by type to eliminate the potential of false hits.\n> \n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n\nIf the goal here is to eliminate the cost of the inner test on the \nobject type in the loop then I don't think you actually gain anything.  \nThe same test is moved elsewhere instead (the assertion notwitstanding), \nbut in a more costly form as the sort will test that condition more \noften than a linear walk, plus the extra argument passing in a couple \nplaces.\n\nIf instead the goal was to ensure that no delta gets wrongly unresolved \nfor whatever reason then this is already covered once at the end with:\n\n                if (nr_deltas != nr_resolved_deltas)\n                        die(\"pack has %d unresolved deltas\",\n                            nr_deltas - nr_resolved_deltas);\n\nSo no, I don't think this patch brings any advantages.\n\n> ---\n>  builtin/index-pack.c |   61 ++++++++++++++++++++++++++++++++-----------------\n>  1 files changed, 40 insertions(+), 21 deletions(-)\n> \n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index 8dc5c0b..1b5d83a 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -391,7 +391,18 @@ static void *get_data_from_pack(struct object_entry *obj)\n>  \treturn data;\n>  }\n>  \n> -static int find_delta(const union delta_base *base)\n> +static int compare_delta_bases(const union delta_base *base1,\n> +\t\t\t       const union delta_base *base2,\n> +\t\t\t       enum object_type type1,\n> +\t\t\t       enum object_type type2)\n> +{\n> +\tint cmp = type1 - type2;\n> +\tif (cmp)\n> +\t\treturn cmp;\n> +\treturn memcmp(base1, base2, UNION_BASE_SZ);\n> +}\n> +\n> +static int find_delta(const union delta_base *base, enum object_type type)\n>  {\n>  \tint first = 0, last = nr_deltas;\n>  \n> @@ -400,7 +411,8 @@ static int find_delta(const union delta_base *base)\n>                  struct delta_entry *delta = &deltas[next];\n>                  int cmp;\n>  \n> -                cmp = memcmp(base, &delta->base, UNION_BASE_SZ);\n> +\t\tcmp = compare_delta_bases(base, &delta->base,\n> +\t\t\t\t\t  type, objects[delta->obj_no].type);\n>                  if (!cmp)\n>                          return next;\n>                  if (cmp < 0) {\n> @@ -413,9 +425,10 @@ static int find_delta(const union delta_base *base)\n>  }\n>  \n>  static void find_delta_children(const union delta_base *base,\n> -\t\t\t\tint *first_index, int *last_index)\n> +\t\t\t\tint *first_index, int *last_index,\n> +\t\t\t\tenum object_type type)\n>  {\n> -\tint first = find_delta(base);\n> +\tint first = find_delta(base, type);\n>  \tint last = first;\n>  \tint end = nr_deltas - 1;\n>  \n> @@ -543,11 +556,13 @@ 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\tfind_delta_children(&base_spec, &ref_first, &ref_last);\n> +\t\tfind_delta_children(&base_spec,\n> +\t\t\t\t    &ref_first, &ref_last, OBJ_REF_DELTA);\n>  \n>  \t\tmemset(&base_spec, 0, sizeof(base_spec));\n>  \t\tbase_spec.offset = base->obj->idx.offset;\n> -\t\tfind_delta_children(&base_spec, &ofs_first, &ofs_last);\n> +\t\tfind_delta_children(&base_spec,\n> +\t\t\t\t    &ofs_first, &ofs_last, OBJ_OFS_DELTA);\n>  \t}\n>  \n>  \tif (ref_last == -1 && ofs_last == -1) {\n> @@ -559,24 +574,24 @@ static void find_unresolved_deltas(struct base_data *base,\n>  \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\tstruct base_data result;\n> +\n> +\t\tassert(child->real_type == OBJ_REF_DELTA);\n> +\t\tresolve_delta(child, base, &result);\n> +\t\tif (i == ref_last && ofs_last == -1)\n> +\t\t\tfree_base_data(base);\n> +\t\tfind_unresolved_deltas(&result, base);\n>  \t}\n>  \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\tstruct base_data result;\n> +\n> +\t\tassert(child->real_type == OBJ_OFS_DELTA);\n> +\t\tresolve_delta(child, base, &result);\n> +\t\tif (i == ofs_last)\n> +\t\t\tfree_base_data(base);\n> +\t\tfind_unresolved_deltas(&result, base);\n>  \t}\n>  \n>  \tunlink_base_data(base);\n> @@ -586,7 +601,11 @@ static int compare_delta_entry(const void *a, const void *b)\n>  {\n>  \tconst struct delta_entry *delta_a = a;\n>  \tconst struct delta_entry *delta_b = b;\n> -\treturn memcmp(&delta_a->base, &delta_b->base, UNION_BASE_SZ);\n> +\n> +\t/* group by type (ref vs ofs) and then by value (sha-1 or offset) */\n> +\treturn compare_delta_bases(&delta_a->base, &delta_b->base,\n> +\t\t\t\t   objects[delta_a->obj_no].type,\n> +\t\t\t\t   objects[delta_b->obj_no].type);\n>  }\n>  \n>  /* Parse all objects and return the pack content SHA1 hash */\n> \n"}]}