{"thread":{"id":"33309","subject":"[PATCH v3 3/3] sha1_file: remove recursion in unpack_entry","startedAt":"2013-03-27T20:03:39Z","lastAt":"2013-03-27T20:29:23Z","messageCount":5,"participants":["Thomas Rast","Junio C Hamano"],"isPatch":true,"patchVersion":3,"patchTotal":3},"messages":[{"id":"212443","messageId":"cover.1364414442.git.trast@inf.ethz.ch","threadId":"33309","inReplyTo":"87620faky3.fsf@linux-k42r.v.cablecom.net","subject":"[PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-27T20:03:39Z","receivedAt":"2013-03-27T20:03:39Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Thomas Rast <trast@inf.ethz.ch>\n\nAlmost the same as last time.  Changed: the rename suggested by Junio\n\n> The only little concern I may have is this cmp_* function tells us\n> \"I found it!\" by returning true, which is counter-intuitive to the\n> readers of the caller (not the callee).\n> \n> I think it makes sense to compare delta-base-cache entries only for\n> equality, so eq-delta-base-cache-entry might be a better name for\n> it, perhaps?\n\nand a small reword to patch 3's commit message to make it clearer at\nwhich stage we unpack the deltas.\n\n\nThomas Rast (3):\n  sha1_file: remove recursion in packed_object_info\n  Refactor parts of in_delta_base_cache/cache_or_unpack_entry\n  sha1_file: remove recursion in unpack_entry\n\n sha1_file.c | 411 +++++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 266 insertions(+), 145 deletions(-)\n\n-- \n1.8.2.344.g1440b22\n"},{"id":"212444","messageId":"a825fb3134bbb78d3c7a2de8fbab1314d7f219a8.1364414442.git.trast@inf.ethz.ch","threadId":"33309","inReplyTo":"cover.1364414442.git.trast@inf.ethz.ch","subject":"[PATCH v3 1/3] sha1_file: remove recursion in packed_object_info","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-27T20:03:40Z","receivedAt":"2013-03-27T20:03:40Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"packed_object_info() and packed_delta_info() were mutually recursive.\nThe former would handle ordinary types and defer deltas to the latter;\nthe latter would use the former to resolve the delta base.\n\nThis arrangement, however, leads to trouble with threaded index-pack\nand long delta chains on platforms where thread stacks are small, as\nhappened on OS X (512kB thread stacks by default) with the chromium\nrepo.\n\nThe task of the two functions is not all that hard to describe without\nany recursion, however.  It proceeds in three steps:\n\n- determine the representation type and size, based on the outermost\n  object (delta or not)\n\n- follow through the delta chain, if any\n\n- determine the object type from what is found at the end of the delta\n  chain\n\nThe only complication stems from the error recovery.  If parsing fails\nat any step, we want to mark that object (within the pack) as bad and\ntry getting the corresponding SHA1 from elsewhere.  If that also\nfails, we want to repeat this process back up the delta chain until we\nfind a reasonable solution or conclude that there is no way to\nreconstruct the object.  (This is conveniently checked by t5303.)\n\nTo achieve that within the pack, we keep track of the entire delta\nchain in a stack.  When things go sour, we process that stack from the\ntop, marking entries as bad and attempting to re-resolve by sha1.  To\navoid excessive malloc(), the stack starts out with a small\nstack-allocated array.  The choice of 64 is based on the default of\npack.depth, which is 50, in the hope that it covers \"most\" delta\nchains without any need for malloc().\n\nIt's much harder to make the actual re-resolving by sha1 nonrecursive,\nso we skip that.  If you can't afford *that* recursion, your\ncorruption problems are more serious than your stack size problems.\n\nReported-by: Stefan Zager <szager@google.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n sha1_file.c | 135 +++++++++++++++++++++++++++++++++++++-----------------------\n 1 file changed, 84 insertions(+), 51 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 16967d3..2c8b549 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1639,50 +1639,6 @@ static off_t get_delta_base(struct packed_git *p,\n \treturn base_offset;\n }\n \n-/* forward declaration for a mutually recursive function */\n-static int packed_object_info(struct packed_git *p, off_t offset,\n-\t\t\t      unsigned long *sizep, int *rtype);\n-\n-static int packed_delta_info(struct packed_git *p,\n-\t\t\t     struct pack_window **w_curs,\n-\t\t\t     off_t curpos,\n-\t\t\t     enum object_type type,\n-\t\t\t     off_t obj_offset,\n-\t\t\t     unsigned long *sizep)\n-{\n-\toff_t base_offset;\n-\n-\tbase_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);\n-\tif (!base_offset)\n-\t\treturn OBJ_BAD;\n-\ttype = packed_object_info(p, base_offset, NULL, NULL);\n-\tif (type <= OBJ_NONE) {\n-\t\tstruct revindex_entry *revidx;\n-\t\tconst unsigned char *base_sha1;\n-\t\trevidx = find_pack_revindex(p, base_offset);\n-\t\tif (!revidx)\n-\t\t\treturn OBJ_BAD;\n-\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n-\t\tmark_bad_packed_object(p, base_sha1);\n-\t\ttype = sha1_object_info(base_sha1, NULL);\n-\t\tif (type <= OBJ_NONE)\n-\t\t\treturn OBJ_BAD;\n-\t}\n-\n-\t/* We choose to only get the type of the base object and\n-\t * ignore potentially corrupt pack file that expects the delta\n-\t * based on a base with a wrong size.  This saves tons of\n-\t * inflate() calls.\n-\t */\n-\tif (sizep) {\n-\t\t*sizep = get_size_from_delta(p, w_curs, curpos);\n-\t\tif (*sizep == 0)\n-\t\t\ttype = OBJ_BAD;\n-\t}\n-\n-\treturn type;\n-}\n-\n int unpack_object_header(struct packed_git *p,\n \t\t\t struct pack_window **w_curs,\n \t\t\t off_t *curpos,\n@@ -1709,6 +1665,25 @@ int unpack_object_header(struct packed_git *p,\n \treturn type;\n }\n \n+static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)\n+{\n+\tint type;\n+\tstruct revindex_entry *revidx;\n+\tconst unsigned char *sha1;\n+\trevidx = find_pack_revindex(p, obj_offset);\n+\tif (!revidx)\n+\t\treturn OBJ_BAD;\n+\tsha1 = nth_packed_object_sha1(p, revidx->nr);\n+\tmark_bad_packed_object(p, sha1);\n+\ttype = sha1_object_info(sha1, NULL);\n+\tif (type <= OBJ_NONE)\n+\t\treturn OBJ_BAD;\n+\treturn type;\n+}\n+\n+\n+#define POI_STACK_PREALLOC 64\n+\n static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \t\t\t      unsigned long *sizep, int *rtype)\n {\n@@ -1716,31 +1691,89 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \tunsigned long size;\n \toff_t curpos = obj_offset;\n \tenum object_type type;\n+\toff_t small_poi_stack[POI_STACK_PREALLOC];\n+\toff_t *poi_stack = small_poi_stack;\n+\tint poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;\n \n \ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\n \tif (rtype)\n \t\t*rtype = type; /* representation type */\n \n+\tif (sizep) {\n+\t\tif (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n+\t\t\toff_t tmp_pos = curpos;\n+\t\t\toff_t base_offset = get_delta_base(p, &w_curs, &tmp_pos,\n+\t\t\t\t\t\t\t   type, obj_offset);\n+\t\t\tif (!base_offset) {\n+\t\t\t\ttype = OBJ_BAD;\n+\t\t\t\tgoto out;\n+\t\t\t}\n+\t\t\t*sizep = get_size_from_delta(p, &w_curs, tmp_pos);\n+\t\t\tif (*sizep == 0) {\n+\t\t\t\ttype = OBJ_BAD;\n+\t\t\t\tgoto out;\n+\t\t\t}\n+\t\t} else {\n+\t\t\t*sizep = size;\n+\t\t}\n+\t}\n+\n+\twhile (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n+\t\toff_t base_offset;\n+\t\t/* Push the object we're going to leave behind */\n+\t\tif (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {\n+\t\t\tpoi_stack_alloc = alloc_nr(poi_stack_nr);\n+\t\t\tpoi_stack = xmalloc(sizeof(off_t)*poi_stack_alloc);\n+\t\t\tmemcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);\n+\t\t} else {\n+\t\t\tALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);\n+\t\t}\n+\t\tpoi_stack[poi_stack_nr++] = obj_offset;\n+\t\t/* If parsing the base offset fails, just unwind */\n+\t\tbase_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);\n+\t\tif (!base_offset)\n+\t\t\tgoto unwind;\n+\t\tcurpos = obj_offset = base_offset;\n+\t\ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\t\tif (type <= OBJ_NONE) {\n+\t\t\t/* If getting the base itself fails, we first\n+\t\t\t * retry the base, otherwise unwind */\n+\t\t\ttype = retry_bad_packed_offset(p, base_offset);\n+\t\t\tif (type > OBJ_NONE)\n+\t\t\t\tgoto out;\n+\t\t\tgoto unwind;\n+\t\t}\n+\t}\n+\n \tswitch (type) {\n-\tcase OBJ_OFS_DELTA:\n-\tcase OBJ_REF_DELTA:\n-\t\ttype = packed_delta_info(p, &w_curs, curpos,\n-\t\t\t\t\t type, obj_offset, sizep);\n-\t\tbreak;\n+\tcase OBJ_BAD:\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tif (sizep)\n-\t\t\t*sizep = size;\n \t\tbreak;\n \tdefault:\n \t\terror(\"unknown object type %i at offset %\"PRIuMAX\" in %s\",\n \t\t      type, (uintmax_t)obj_offset, p->pack_name);\n \t\ttype = OBJ_BAD;\n \t}\n+\n+out:\n+\tif (poi_stack != small_poi_stack)\n+\t\tfree(poi_stack);\n \tunuse_pack(&w_curs);\n \treturn type;\n+\n+unwind:\n+\twhile (poi_stack_nr) {\n+\t\tobj_offset = poi_stack[--poi_stack_nr];\n+\t\ttype = retry_bad_packed_offset(p, obj_offset);\n+\t\tif (type > OBJ_NONE)\n+\t\t\tgoto out;\n+\t}\n+\ttype = OBJ_BAD;\n+\tgoto out;\n }\n \n static void *unpack_compressed_entry(struct packed_git *p,\n-- \n1.8.2.344.g1440b22\n"},{"id":"212446","messageId":"272cfb933d5ab748fa8c1b3ebb769ecf90f3bbfb.1364414442.git.trast@inf.ethz.ch","threadId":"33309","inReplyTo":"cover.1364414442.git.trast@inf.ethz.ch","subject":"[PATCH v3 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-27T20:03:41Z","receivedAt":"2013-03-27T20:03:41Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"The delta base cache lookup and test were shared.  Refactor them;\nwe'll need both parts again.  Also, we'll use the clearing routine\nlater.\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n sha1_file.c | 45 ++++++++++++++++++++++++++++++++-------------\n 1 file changed, 32 insertions(+), 13 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 2c8b549..da41f51 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1835,32 +1835,51 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)\n \treturn hash % MAX_DELTA_CACHE;\n }\n \n-static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n+static struct delta_base_cache_entry *\n+get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)\n {\n \tunsigned long hash = pack_entry_hash(p, base_offset);\n-\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n+\treturn delta_base_cache + hash;\n+}\n+\n+static int eq_delta_base_cache_entry(struct delta_base_cache_entry *ent,\n+\t\t\t\t     struct packed_git *p, off_t base_offset)\n+{\n \treturn (ent->data && ent->p == p && ent->base_offset == base_offset);\n }\n \n+static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n+{\n+\tstruct delta_base_cache_entry *ent;\n+\tent = get_delta_base_cache_entry(p, base_offset);\n+\treturn eq_delta_base_cache_entry(ent, p, base_offset);\n+}\n+\n+static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n+{\n+\tent->data = NULL;\n+\tent->lru.next->prev = ent->lru.prev;\n+\tent->lru.prev->next = ent->lru.next;\n+\tdelta_base_cached -= ent->size;\n+}\n+\n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \tunsigned long *base_size, enum object_type *type, int keep_cache)\n {\n+\tstruct delta_base_cache_entry *ent;\n \tvoid *ret;\n-\tunsigned long hash = pack_entry_hash(p, base_offset);\n-\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n \n-\tret = ent->data;\n-\tif (!ret || ent->p != p || ent->base_offset != base_offset)\n+\tent = get_delta_base_cache_entry(p, base_offset);\n+\n+\tif (!eq_delta_base_cache_entry(ent, p, base_offset))\n \t\treturn unpack_entry(p, base_offset, type, base_size);\n \n-\tif (!keep_cache) {\n-\t\tent->data = NULL;\n-\t\tent->lru.next->prev = ent->lru.prev;\n-\t\tent->lru.prev->next = ent->lru.next;\n-\t\tdelta_base_cached -= ent->size;\n-\t} else {\n+\tret = ent->data;\n+\n+\tif (!keep_cache)\n+\t\tclear_delta_base_cache_entry(ent);\n+\telse\n \t\tret = xmemdupz(ent->data, ent->size);\n-\t}\n \t*type = ent->type;\n \t*base_size = ent->size;\n \treturn ret;\n-- \n1.8.2.344.g1440b22\n"},{"id":"212442","messageId":"1b5875495c959ba96848fcf9d3067e25e3c1e75b.1364414442.git.trast@inf.ethz.ch","threadId":"33309","inReplyTo":"cover.1364414442.git.trast@inf.ethz.ch","subject":"[PATCH v3 3/3] sha1_file: remove recursion in unpack_entry","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-27T20:03:42Z","receivedAt":"2013-03-27T20:03:42Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Similar to the recursion in packed_object_info(), this leads to\nproblems on stack-space-constrained systems in the presence of long\ndelta chains.\n\nWe proceed in three phases:\n\n1. Dig through the delta chain, saving each delta object's offsets and\n   size on an ad-hoc stack.\n\n2. Unpack the base object at the bottom.\n\n3. Unpack and apply the deltas from the stack.\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 150 insertions(+), 81 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex da41f51..f9191aa 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1943,68 +1943,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n static void *read_object(const unsigned char *sha1, enum object_type *type,\n \t\t\t unsigned long *size);\n \n-static void *unpack_delta_entry(struct packed_git *p,\n-\t\t\t\tstruct pack_window **w_curs,\n-\t\t\t\toff_t curpos,\n-\t\t\t\tunsigned long delta_size,\n-\t\t\t\toff_t obj_offset,\n-\t\t\t\tenum object_type *type,\n-\t\t\t\tunsigned long *sizep)\n-{\n-\tvoid *delta_data, *result, *base;\n-\tunsigned long base_size;\n-\toff_t base_offset;\n-\n-\tbase_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);\n-\tif (!base_offset) {\n-\t\terror(\"failed to validate delta base reference \"\n-\t\t      \"at offset %\"PRIuMAX\" from %s\",\n-\t\t      (uintmax_t)curpos, p->pack_name);\n-\t\treturn NULL;\n-\t}\n-\tunuse_pack(w_curs);\n-\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);\n-\tif (!base) {\n-\t\t/*\n-\t\t * We're probably in deep shit, but let's try to fetch\n-\t\t * the required base anyway from another pack or loose.\n-\t\t * This is costly but should happen only in the presence\n-\t\t * of a corrupted pack, and is better than failing outright.\n-\t\t */\n-\t\tstruct revindex_entry *revidx;\n-\t\tconst unsigned char *base_sha1;\n-\t\trevidx = find_pack_revindex(p, base_offset);\n-\t\tif (!revidx)\n-\t\t\treturn NULL;\n-\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n-\t\terror(\"failed to read delta base object %s\"\n-\t\t      \" at offset %\"PRIuMAX\" from %s\",\n-\t\t      sha1_to_hex(base_sha1), (uintmax_t)base_offset,\n-\t\t      p->pack_name);\n-\t\tmark_bad_packed_object(p, base_sha1);\n-\t\tbase = read_object(base_sha1, type, &base_size);\n-\t\tif (!base)\n-\t\t\treturn NULL;\n-\t}\n-\n-\tdelta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);\n-\tif (!delta_data) {\n-\t\terror(\"failed to unpack compressed delta \"\n-\t\t      \"at offset %\"PRIuMAX\" from %s\",\n-\t\t      (uintmax_t)curpos, p->pack_name);\n-\t\tfree(base);\n-\t\treturn NULL;\n-\t}\n-\tresult = patch_delta(base, base_size,\n-\t\t\t     delta_data, delta_size,\n-\t\t\t     sizep);\n-\tif (!result)\n-\t\tdie(\"failed to apply delta\");\n-\tfree(delta_data);\n-\tadd_delta_base_cache(p, base_offset, base, base_size, *type);\n-\treturn result;\n-}\n-\n static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n {\n \tstatic FILE *log_file;\n@@ -2025,48 +1963,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n \n int do_check_packed_object_crc;\n \n+#define UNPACK_ENTRY_STACK_PREALLOC 64\n+struct unpack_entry_stack_ent {\n+\toff_t obj_offset;\n+\toff_t curpos;\n+\tunsigned long size;\n+};\n+\n void *unpack_entry(struct packed_git *p, off_t obj_offset,\n-\t\t   enum object_type *type, unsigned long *sizep)\n+\t\t   enum object_type *final_type, unsigned long *final_size)\n {\n \tstruct pack_window *w_curs = NULL;\n \toff_t curpos = obj_offset;\n-\tvoid *data;\n+\tvoid *data = NULL;\n+\tunsigned long size;\n+\tenum object_type type;\n+\tstruct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];\n+\tstruct unpack_entry_stack_ent *delta_stack = small_delta_stack;\n+\tint delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;\n+\tint base_from_cache = 0;\n \n \tif (log_pack_access)\n \t\twrite_pack_access_log(p, obj_offset);\n \n-\tif (do_check_packed_object_crc && p->index_version > 1) {\n-\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n-\t\tunsigned long len = revidx[1].offset - obj_offset;\n-\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n-\t\t\tconst unsigned char *sha1 =\n-\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n-\t\t\terror(\"bad packed object CRC for %s\",\n-\t\t\t      sha1_to_hex(sha1));\n-\t\t\tmark_bad_packed_object(p, sha1);\n-\t\t\tunuse_pack(&w_curs);\n-\t\t\treturn NULL;\n+\t/* PHASE 1: drill down to the innermost base object */\n+\tfor (;;) {\n+\t\toff_t base_offset;\n+\t\tint i;\n+\t\tstruct delta_base_cache_entry *ent;\n+\n+\t\tif (do_check_packed_object_crc && p->index_version > 1) {\n+\t\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n+\t\t\tunsigned long len = revidx[1].offset - obj_offset;\n+\t\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n+\t\t\t\tconst unsigned char *sha1 =\n+\t\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n+\t\t\t\terror(\"bad packed object CRC for %s\",\n+\t\t\t\t      sha1_to_hex(sha1));\n+\t\t\t\tmark_bad_packed_object(p, sha1);\n+\t\t\t\tunuse_pack(&w_curs);\n+\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\n+\t\tent = get_delta_base_cache_entry(p, curpos);\n+\t\tif (eq_delta_base_cache_entry(ent, p, curpos)) {\n+\t\t\ttype = ent->type;\n+\t\t\tdata = ent->data;\n+\t\t\tsize = ent->size;\n+\t\t\tclear_delta_base_cache_entry(ent);\n+\t\t\tbase_from_cache = 1;\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\t\tif (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)\n+\t\t\tbreak;\n+\n+\t\tbase_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);\n+\t\tif (!base_offset) {\n+\t\t\terror(\"failed to validate delta base reference \"\n+\t\t\t      \"at offset %\"PRIuMAX\" from %s\",\n+\t\t\t      (uintmax_t)curpos, p->pack_name);\n+\t\t\t/* bail to phase 2, in hopes of recovery */\n+\t\t\tdata = NULL;\n+\t\t\tbreak;\n \t\t}\n+\n+\t\t/* push object, proceed to base */\n+\t\tif (delta_stack_nr >= delta_stack_alloc\n+\t\t    && delta_stack == small_delta_stack) {\n+\t\t\tdelta_stack_alloc = alloc_nr(delta_stack_nr);\n+\t\t\tdelta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);\n+\t\t\tmemcpy(delta_stack, small_delta_stack,\n+\t\t\t       sizeof(*delta_stack)*delta_stack_nr);\n+\t\t} else {\n+\t\t\tALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);\n+\t\t}\n+\t\ti = delta_stack_nr++;\n+\t\tdelta_stack[i].obj_offset = obj_offset;\n+\t\tdelta_stack[i].curpos = curpos;\n+\t\tdelta_stack[i].size = size;\n+\n+\t\tcurpos = obj_offset = base_offset;\n \t}\n \n-\t*type = unpack_object_header(p, &w_curs, &curpos, sizep);\n-\tswitch (*type) {\n+\t/* PHASE 2: handle the base */\n+\tswitch (type) {\n \tcase OBJ_OFS_DELTA:\n \tcase OBJ_REF_DELTA:\n-\t\tdata = unpack_delta_entry(p, &w_curs, curpos, *sizep,\n-\t\t\t\t\t  obj_offset, type, sizep);\n+\t\tif (data)\n+\t\t\tdie(\"BUG in unpack_entry: left loop at a valid delta\");\n \t\tbreak;\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, *sizep);\n+\t\tif (!base_from_cache)\n+\t\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, size);\n \t\tbreak;\n \tdefault:\n \t\tdata = NULL;\n \t\terror(\"unknown object type %i at offset %\"PRIuMAX\" in %s\",\n-\t\t      *type, (uintmax_t)obj_offset, p->pack_name);\n+\t\t      type, (uintmax_t)obj_offset, p->pack_name);\n \t}\n+\n+\t/* PHASE 3: apply deltas in order */\n+\n+\t/* invariants:\n+\t *   'data' holds the base data, or NULL if there was corruption\n+\t */\n+\twhile (delta_stack_nr) {\n+\t\tvoid *delta_data;\n+\t\tvoid *base = data;\n+\t\tunsigned long delta_size, base_size = size;\n+\t\tint i;\n+\n+\t\tdata = NULL;\n+\n+\t\tif (base)\n+\t\t\tadd_delta_base_cache(p, obj_offset, base, base_size, type);\n+\n+\t\tif (!base) {\n+\t\t\t/*\n+\t\t\t * We're probably in deep shit, but let's try to fetch\n+\t\t\t * the required base anyway from another pack or loose.\n+\t\t\t * This is costly but should happen only in the presence\n+\t\t\t * of a corrupted pack, and is better than failing outright.\n+\t\t\t */\n+\t\t\tstruct revindex_entry *revidx;\n+\t\t\tconst unsigned char *base_sha1;\n+\t\t\trevidx = find_pack_revindex(p, obj_offset);\n+\t\t\tif (revidx) {\n+\t\t\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n+\t\t\t\terror(\"failed to read delta base object %s\"\n+\t\t\t\t      \" at offset %\"PRIuMAX\" from %s\",\n+\t\t\t\t      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,\n+\t\t\t\t      p->pack_name);\n+\t\t\t\tmark_bad_packed_object(p, base_sha1);\n+\t\t\t\tbase = read_object(base_sha1, &type, &base_size);\n+\t\t\t}\n+\t\t}\n+\n+\t\ti = --delta_stack_nr;\n+\t\tobj_offset = delta_stack[i].obj_offset;\n+\t\tcurpos = delta_stack[i].curpos;\n+\t\tdelta_size = delta_stack[i].size;\n+\n+\t\tif (!base)\n+\t\t\tcontinue;\n+\n+\t\tdelta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);\n+\n+\t\tif (!delta_data) {\n+\t\t\terror(\"failed to unpack compressed delta \"\n+\t\t\t      \"at offset %\"PRIuMAX\" from %s\",\n+\t\t\t      (uintmax_t)curpos, p->pack_name);\n+\t\t\tfree(base);\n+\t\t\tdata = NULL;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tdata = patch_delta(base, base_size,\n+\t\t\t\t   delta_data, delta_size,\n+\t\t\t\t   &size);\n+\t\tif (!data)\n+\t\t\tdie(\"failed to apply delta\");\n+\n+\t\tfree (delta_data);\n+\t}\n+\n+\t*final_type = type;\n+\t*final_size = size;\n+\n \tunuse_pack(&w_curs);\n \treturn data;\n }\n-- \n1.8.2.344.g1440b22\n"},{"id":"212451","messageId":"7vli98lh7g.fsf@alter.siamese.dyndns.org","threadId":"33309","inReplyTo":"1b5875495c959ba96848fcf9d3067e25e3c1e75b.1364414442.git.trast@inf.ethz.ch","subject":"Re: [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-27T20:29:23Z","receivedAt":"2013-03-27T20:29:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\n\n> Similar to the recursion in packed_object_info(), this leads to\n> problems on stack-space-constrained systems in the presence of long\n> delta chains.\n>\n> We proceed in three phases:\n>\n> 1. Dig through the delta chain, saving each delta object's offsets and\n>    size on an ad-hoc stack.\n>\n> 2. Unpack the base object at the bottom.\n>\n> 3. Unpack and apply the deltas from the stack.\n>\n> Signed-off-by: Thomas Rast <trast@student.ethz.ch>\n> ---\n\nSounds sensible.\n\nDo we keep the packfiles open that hold the deltas involved in the\nchain so that they won't be removed by a concurrent repack?  I do\nnot think this rewrite changes anything with respect to that access\npattern, though.\n\nWill replace and merge to 'next'.  Thanks.\n\n>  sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------\n>  1 file changed, 150 insertions(+), 81 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index da41f51..f9191aa 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -1943,68 +1943,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n>  static void *read_object(const unsigned char *sha1, enum object_type *type,\n>  \t\t\t unsigned long *size);\n>  \n> -static void *unpack_delta_entry(struct packed_git *p,\n> -\t\t\t\tstruct pack_window **w_curs,\n> -\t\t\t\toff_t curpos,\n> -\t\t\t\tunsigned long delta_size,\n> -\t\t\t\toff_t obj_offset,\n> -\t\t\t\tenum object_type *type,\n> -\t\t\t\tunsigned long *sizep)\n> -{\n> -\tvoid *delta_data, *result, *base;\n> -\tunsigned long base_size;\n> -\toff_t base_offset;\n> -\n> -\tbase_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);\n> -\tif (!base_offset) {\n> -\t\terror(\"failed to validate delta base reference \"\n> -\t\t      \"at offset %\"PRIuMAX\" from %s\",\n> -\t\t      (uintmax_t)curpos, p->pack_name);\n> -\t\treturn NULL;\n> -\t}\n> -\tunuse_pack(w_curs);\n> -\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);\n> -\tif (!base) {\n> -\t\t/*\n> -\t\t * We're probably in deep shit, but let's try to fetch\n> -\t\t * the required base anyway from another pack or loose.\n> -\t\t * This is costly but should happen only in the presence\n> -\t\t * of a corrupted pack, and is better than failing outright.\n> -\t\t */\n> -\t\tstruct revindex_entry *revidx;\n> -\t\tconst unsigned char *base_sha1;\n> -\t\trevidx = find_pack_revindex(p, base_offset);\n> -\t\tif (!revidx)\n> -\t\t\treturn NULL;\n> -\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n> -\t\terror(\"failed to read delta base object %s\"\n> -\t\t      \" at offset %\"PRIuMAX\" from %s\",\n> -\t\t      sha1_to_hex(base_sha1), (uintmax_t)base_offset,\n> -\t\t      p->pack_name);\n> -\t\tmark_bad_packed_object(p, base_sha1);\n> -\t\tbase = read_object(base_sha1, type, &base_size);\n> -\t\tif (!base)\n> -\t\t\treturn NULL;\n> -\t}\n> -\n> -\tdelta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);\n> -\tif (!delta_data) {\n> -\t\terror(\"failed to unpack compressed delta \"\n> -\t\t      \"at offset %\"PRIuMAX\" from %s\",\n> -\t\t      (uintmax_t)curpos, p->pack_name);\n> -\t\tfree(base);\n> -\t\treturn NULL;\n> -\t}\n> -\tresult = patch_delta(base, base_size,\n> -\t\t\t     delta_data, delta_size,\n> -\t\t\t     sizep);\n> -\tif (!result)\n> -\t\tdie(\"failed to apply delta\");\n> -\tfree(delta_data);\n> -\tadd_delta_base_cache(p, base_offset, base, base_size, *type);\n> -\treturn result;\n> -}\n> -\n>  static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n>  {\n>  \tstatic FILE *log_file;\n> @@ -2025,48 +1963,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n>  \n>  int do_check_packed_object_crc;\n>  \n> +#define UNPACK_ENTRY_STACK_PREALLOC 64\n> +struct unpack_entry_stack_ent {\n> +\toff_t obj_offset;\n> +\toff_t curpos;\n> +\tunsigned long size;\n> +};\n> +\n>  void *unpack_entry(struct packed_git *p, off_t obj_offset,\n> -\t\t   enum object_type *type, unsigned long *sizep)\n> +\t\t   enum object_type *final_type, unsigned long *final_size)\n>  {\n>  \tstruct pack_window *w_curs = NULL;\n>  \toff_t curpos = obj_offset;\n> -\tvoid *data;\n> +\tvoid *data = NULL;\n> +\tunsigned long size;\n> +\tenum object_type type;\n> +\tstruct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];\n> +\tstruct unpack_entry_stack_ent *delta_stack = small_delta_stack;\n> +\tint delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;\n> +\tint base_from_cache = 0;\n>  \n>  \tif (log_pack_access)\n>  \t\twrite_pack_access_log(p, obj_offset);\n>  \n> -\tif (do_check_packed_object_crc && p->index_version > 1) {\n> -\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n> -\t\tunsigned long len = revidx[1].offset - obj_offset;\n> -\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n> -\t\t\tconst unsigned char *sha1 =\n> -\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n> -\t\t\terror(\"bad packed object CRC for %s\",\n> -\t\t\t      sha1_to_hex(sha1));\n> -\t\t\tmark_bad_packed_object(p, sha1);\n> -\t\t\tunuse_pack(&w_curs);\n> -\t\t\treturn NULL;\n> +\t/* PHASE 1: drill down to the innermost base object */\n> +\tfor (;;) {\n> +\t\toff_t base_offset;\n> +\t\tint i;\n> +\t\tstruct delta_base_cache_entry *ent;\n> +\n> +\t\tif (do_check_packed_object_crc && p->index_version > 1) {\n> +\t\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n> +\t\t\tunsigned long len = revidx[1].offset - obj_offset;\n> +\t\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n> +\t\t\t\tconst unsigned char *sha1 =\n> +\t\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n> +\t\t\t\terror(\"bad packed object CRC for %s\",\n> +\t\t\t\t      sha1_to_hex(sha1));\n> +\t\t\t\tmark_bad_packed_object(p, sha1);\n> +\t\t\t\tunuse_pack(&w_curs);\n> +\t\t\t\treturn NULL;\n> +\t\t\t}\n> +\t\t}\n> +\n> +\t\tent = get_delta_base_cache_entry(p, curpos);\n> +\t\tif (eq_delta_base_cache_entry(ent, p, curpos)) {\n> +\t\t\ttype = ent->type;\n> +\t\t\tdata = ent->data;\n> +\t\t\tsize = ent->size;\n> +\t\t\tclear_delta_base_cache_entry(ent);\n> +\t\t\tbase_from_cache = 1;\n> +\t\t\tbreak;\n> +\t\t}\n> +\n> +\t\ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n> +\t\tif (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)\n> +\t\t\tbreak;\n> +\n> +\t\tbase_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);\n> +\t\tif (!base_offset) {\n> +\t\t\terror(\"failed to validate delta base reference \"\n> +\t\t\t      \"at offset %\"PRIuMAX\" from %s\",\n> +\t\t\t      (uintmax_t)curpos, p->pack_name);\n> +\t\t\t/* bail to phase 2, in hopes of recovery */\n> +\t\t\tdata = NULL;\n> +\t\t\tbreak;\n>  \t\t}\n> +\n> +\t\t/* push object, proceed to base */\n> +\t\tif (delta_stack_nr >= delta_stack_alloc\n> +\t\t    && delta_stack == small_delta_stack) {\n> +\t\t\tdelta_stack_alloc = alloc_nr(delta_stack_nr);\n> +\t\t\tdelta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);\n> +\t\t\tmemcpy(delta_stack, small_delta_stack,\n> +\t\t\t       sizeof(*delta_stack)*delta_stack_nr);\n> +\t\t} else {\n> +\t\t\tALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);\n> +\t\t}\n> +\t\ti = delta_stack_nr++;\n> +\t\tdelta_stack[i].obj_offset = obj_offset;\n> +\t\tdelta_stack[i].curpos = curpos;\n> +\t\tdelta_stack[i].size = size;\n> +\n> +\t\tcurpos = obj_offset = base_offset;\n>  \t}\n>  \n> -\t*type = unpack_object_header(p, &w_curs, &curpos, sizep);\n> -\tswitch (*type) {\n> +\t/* PHASE 2: handle the base */\n> +\tswitch (type) {\n>  \tcase OBJ_OFS_DELTA:\n>  \tcase OBJ_REF_DELTA:\n> -\t\tdata = unpack_delta_entry(p, &w_curs, curpos, *sizep,\n> -\t\t\t\t\t  obj_offset, type, sizep);\n> +\t\tif (data)\n> +\t\t\tdie(\"BUG in unpack_entry: left loop at a valid delta\");\n>  \t\tbreak;\n>  \tcase OBJ_COMMIT:\n>  \tcase OBJ_TREE:\n>  \tcase OBJ_BLOB:\n>  \tcase OBJ_TAG:\n> -\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, *sizep);\n> +\t\tif (!base_from_cache)\n> +\t\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, size);\n>  \t\tbreak;\n>  \tdefault:\n>  \t\tdata = NULL;\n>  \t\terror(\"unknown object type %i at offset %\"PRIuMAX\" in %s\",\n> -\t\t      *type, (uintmax_t)obj_offset, p->pack_name);\n> +\t\t      type, (uintmax_t)obj_offset, p->pack_name);\n>  \t}\n> +\n> +\t/* PHASE 3: apply deltas in order */\n> +\n> +\t/* invariants:\n> +\t *   'data' holds the base data, or NULL if there was corruption\n> +\t */\n> +\twhile (delta_stack_nr) {\n> +\t\tvoid *delta_data;\n> +\t\tvoid *base = data;\n> +\t\tunsigned long delta_size, base_size = size;\n> +\t\tint i;\n> +\n> +\t\tdata = NULL;\n> +\n> +\t\tif (base)\n> +\t\t\tadd_delta_base_cache(p, obj_offset, base, base_size, type);\n> +\n> +\t\tif (!base) {\n> +\t\t\t/*\n> +\t\t\t * We're probably in deep shit, but let's try to fetch\n> +\t\t\t * the required base anyway from another pack or loose.\n> +\t\t\t * This is costly but should happen only in the presence\n> +\t\t\t * of a corrupted pack, and is better than failing outright.\n> +\t\t\t */\n> +\t\t\tstruct revindex_entry *revidx;\n> +\t\t\tconst unsigned char *base_sha1;\n> +\t\t\trevidx = find_pack_revindex(p, obj_offset);\n> +\t\t\tif (revidx) {\n> +\t\t\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n> +\t\t\t\terror(\"failed to read delta base object %s\"\n> +\t\t\t\t      \" at offset %\"PRIuMAX\" from %s\",\n> +\t\t\t\t      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,\n> +\t\t\t\t      p->pack_name);\n> +\t\t\t\tmark_bad_packed_object(p, base_sha1);\n> +\t\t\t\tbase = read_object(base_sha1, &type, &base_size);\n> +\t\t\t}\n> +\t\t}\n> +\n> +\t\ti = --delta_stack_nr;\n> +\t\tobj_offset = delta_stack[i].obj_offset;\n> +\t\tcurpos = delta_stack[i].curpos;\n> +\t\tdelta_size = delta_stack[i].size;\n> +\n> +\t\tif (!base)\n> +\t\t\tcontinue;\n> +\n> +\t\tdelta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);\n> +\n> +\t\tif (!delta_data) {\n> +\t\t\terror(\"failed to unpack compressed delta \"\n> +\t\t\t      \"at offset %\"PRIuMAX\" from %s\",\n> +\t\t\t      (uintmax_t)curpos, p->pack_name);\n> +\t\t\tfree(base);\n> +\t\t\tdata = NULL;\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tdata = patch_delta(base, base_size,\n> +\t\t\t\t   delta_data, delta_size,\n> +\t\t\t\t   &size);\n> +\t\tif (!data)\n> +\t\t\tdie(\"failed to apply delta\");\n> +\n> +\t\tfree (delta_data);\n> +\t}\n> +\n> +\t*final_type = type;\n> +\t*final_size = size;\n> +\n>  \tunuse_pack(&w_curs);\n>  \treturn data;\n>  }\n"}]}