git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 3/3] sha1_file: remove recursion in unpack_entry

From
Thomas Rast <trast@student.ethz.ch>
Date
Mar 25, 2013, 18:07 UTC
Message-ID
<f65b321e148bd51fe369872c5679742e638f8fe5.1364234154.git.trast@student.ethz.ch>
In-Reply-To
<cover.1364234154.git.trast@student.ethz.ch>

Similar to the recursion in packed_object_info(), this leads to problems on stack-space-constrained systems in the presence of long delta chains.

We proceed in three phases:
1. Dig through the delta chain, saving each delta object's offsets and
   size on an ad-hoc stack.
2. Unpack the base object at the bottom.
3. Apply the deltas from the stack.
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 150 insertions(+), 81 deletions(-)
diff --git a/sha1_file.c b/sha1_file.c
index bd054d1..1b685b9 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1864,68 +1864,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
 static void *read_object(const unsigned char *sha1, enum object_type *type,
 			 unsigned long *size);
 
-static void *unpack_delta_entry(struct packed_git *p,
-				struct pack_window **w_curs,
-				off_t curpos,
-				unsigned long delta_size,
-				off_t obj_offset,
-				enum object_type *type,
-				unsigned long *sizep)
-{
-	void *delta_data, *result, *base;
-	unsigned long base_size;
-	off_t base_offset;
-
-	base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
-	if (!base_offset) {
-		error("failed to validate delta base reference "
-		      "at offset %"PRIuMAX" from %s",
-		      (uintmax_t)curpos, p->pack_name);
-		return NULL;
-	}
-	unuse_pack(w_curs);
-	base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
-	if (!base) {
-		/*
-		 * We're probably in deep shit, but let's try to fetch
-		 * the required base anyway from another pack or loose.
-		 * This is costly but should happen only in the presence
-		 * of a corrupted pack, and is better than failing outright.
-		 */
-		struct revindex_entry *revidx;
-		const unsigned char *base_sha1;
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
-			return NULL;
-		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
-		error("failed to read delta base object %s"
-		      " at offset %"PRIuMAX" from %s",
-		      sha1_to_hex(base_sha1), (uintmax_t)base_offset,
-		      p->pack_name);
-		mark_bad_packed_object(p, base_sha1);
-		base = read_object(base_sha1, type, &base_size);
-		if (!base)
-			return NULL;
-	}
-
-	delta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);
-	if (!delta_data) {
-		error("failed to unpack compressed delta "
-		      "at offset %"PRIuMAX" from %s",
-		      (uintmax_t)curpos, p->pack_name);
-		free(base);
-		return NULL;
-	}
-	result = patch_delta(base, base_size,
-			     delta_data, delta_size,
-			     sizep);
-	if (!result)
-		die("failed to apply delta");
-	free(delta_data);
-	add_delta_base_cache(p, base_offset, base, base_size, *type);
-	return result;
-}
-
 static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
 {
 	static FILE *log_file;
@@ -1946,48 +1884,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
 
 int do_check_packed_object_crc;
 
+#define UNPACK_ENTRY_STACK_PREALLOC 64
+struct unpack_entry_stack_ent {
+	off_t obj_offset;
+	off_t curpos;
+	unsigned long size;
+};
+
 void *unpack_entry(struct packed_git *p, off_t obj_offset,
-		   enum object_type *type, unsigned long *sizep)
+		   enum object_type *final_type, unsigned long *final_size)
 {
 	struct pack_window *w_curs = NULL;
 	off_t curpos = obj_offset;
-	void *data;
+	void *data = NULL;
+	unsigned long size;
+	enum object_type type;
+	struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
+	struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
+	int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
+	int base_from_cache = 0;
 
 	if (log_pack_access)
 		write_pack_access_log(p, obj_offset);
 
-	if (do_check_packed_object_crc && p->index_version > 1) {
-		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
-		unsigned long len = revidx[1].offset - obj_offset;
-		if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
-			const unsigned char *sha1 =
-				nth_packed_object_sha1(p, revidx->nr);
-			error("bad packed object CRC for %s",
-			      sha1_to_hex(sha1));
-			mark_bad_packed_object(p, sha1);
-			unuse_pack(&w_curs);
-			return NULL;
+	/* PHASE 1: drill down to the innermost base object */
+	for (;;) {
+		off_t base_offset;
+		int i;
+		struct delta_base_cache_entry *ent;
+
+		if (do_check_packed_object_crc && p->index_version > 1) {
+			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
+			unsigned long len = revidx[1].offset - obj_offset;
+			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
+				const unsigned char *sha1 =
+					nth_packed_object_sha1(p, revidx->nr);
+				error("bad packed object CRC for %s",
+				      sha1_to_hex(sha1));
+				mark_bad_packed_object(p, sha1);
+				unuse_pack(&w_curs);
+				return NULL;
+			}
+		}
+
+		ent = get_delta_base_cache_entry(p, curpos);
+		if (cmp_delta_base_cache_entry(ent, p, curpos)) {
+			type = ent->type;
+			data = ent->data;
+			size = ent->size;
+			clear_delta_base_cache_entry(ent);
+			base_from_cache = 1;
+			break;
+		}
+
+		type = unpack_object_header(p, &w_curs, &curpos, &size);
+		if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
+			break;
+
+		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
+		if (!base_offset) {
+			error("failed to validate delta base reference "
+			      "at offset %"PRIuMAX" from %s",
+			      (uintmax_t)curpos, p->pack_name);
+			/* bail to phase 2, in hopes of recovery */
+			data = NULL;
+			break;
 		}
+
+		/* push object, proceed to base */
+		if (delta_stack_nr >= delta_stack_alloc
+		    && delta_stack == small_delta_stack) {
+			delta_stack_alloc = alloc_nr(delta_stack_nr);
+			delta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);
+			memcpy(delta_stack, small_delta_stack,
+			       sizeof(*delta_stack)*delta_stack_nr);
+		} else {
+			ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
+		}
+		i = delta_stack_nr++;
+		delta_stack[i].obj_offset = obj_offset;
+		delta_stack[i].curpos = curpos;
+		delta_stack[i].size = size;
+
+		curpos = obj_offset = base_offset;
 	}
 
-	*type = unpack_object_header(p, &w_curs, &curpos, sizep);
-	switch (*type) {
+	/* PHASE 2: handle the base */
+	switch (type) {
 	case OBJ_OFS_DELTA:
 	case OBJ_REF_DELTA:
-		data = unpack_delta_entry(p, &w_curs, curpos, *sizep,
-					  obj_offset, type, sizep);
+		if (data)
+			die("BUG in unpack_entry: left loop at a valid delta");
 		break;
 	case OBJ_COMMIT:
 	case OBJ_TREE:
 	case OBJ_BLOB:
 	case OBJ_TAG:
-		data = unpack_compressed_entry(p, &w_curs, curpos, *sizep);
+		if (!base_from_cache)
+			data = unpack_compressed_entry(p, &w_curs, curpos, size);
 		break;
 	default:
 		data = NULL;
 		error("unknown object type %i at offset %"PRIuMAX" in %s",
-		      *type, (uintmax_t)obj_offset, p->pack_name);
+		      type, (uintmax_t)obj_offset, p->pack_name);
 	}
+
+	/* PHASE 3: apply deltas in order */
+
+	/* invariants:
+	 *   'data' holds the base data, or NULL if there was corruption
+	 */
+	while (delta_stack_nr) {
+		void *delta_data;
+		void *base = data;
+		unsigned long delta_size, base_size = size;
+		int i;
+
+		data = NULL;
+
+		if (base)
+			add_delta_base_cache(p, obj_offset, base, base_size, type);
+
+		if (!base) {
+			/*
+			 * We're probably in deep shit, but let's try to fetch
+			 * the required base anyway from another pack or loose.
+			 * This is costly but should happen only in the presence
+			 * of a corrupted pack, and is better than failing outright.
+			 */
+			struct revindex_entry *revidx;
+			const unsigned char *base_sha1;
+			revidx = find_pack_revindex(p, obj_offset);
+			if (revidx) {
+				base_sha1 = nth_packed_object_sha1(p, revidx->nr);
+				error("failed to read delta base object %s"
+				      " at offset %"PRIuMAX" from %s",
+				      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,
+				      p->pack_name);
+				mark_bad_packed_object(p, base_sha1);
+				base = read_object(base_sha1, &type, &base_size);
+			}
+		}
+
+		i = --delta_stack_nr;
+		obj_offset = delta_stack[i].obj_offset;
+		curpos = delta_stack[i].curpos;
+		delta_size = delta_stack[i].size;
+
+		if (!base)
+			continue;
+
+		delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
+
+		if (!delta_data) {
+			error("failed to unpack compressed delta "
+			      "at offset %"PRIuMAX" from %s",
+			      (uintmax_t)curpos, p->pack_name);
+			free(base);
+			data = NULL;
+			continue;
+		}
+
+		data = patch_delta(base, base_size,
+				   delta_data, delta_size,
+				   &size);
+		if (!data)
+			die("failed to apply delta");
+
+		free (delta_data);
+	}
+
+	*final_type = type;
+	*final_size = size;
+
 	unuse_pack(&w_curs);
 	return data;
 }

-- 
1.8.2.266.g8176668
Previous: thomasNext: Junio C Hamano
Message 42 of 46 in “regression in multi-threaded git-pack-index”
  1. Stefan ZagerMar 15, 2013
  2. Jeff KingMar 16, 2013
  3. Duy NguyenMar 16, 2013
  4. Thomas RastMar 19, 2013
  5. Jeff KingMar 19, 2013
  6. Jeff KingMar 19, 2013
  7. Jeff KingMar 19, 2013
  8. Jeff KingMar 19, 2013
  9. Thomas RastMar 19, 2013
  10. Jeff KingMar 19, 2013
  11. Thomas RastMar 19, 2013
  12. Jeff KingMar 19, 2013
  13. index-pack: always zero-initialize object_entry listJeff King, Mar 19, 2013
  14. Thomas RastMar 19, 2013
  15. Jeff KingMar 19, 2013
  16. Jeff KingMar 19, 2013
  17. index-pack: always zero-initialize object_entry listJeff King, Mar 19, 2013
  18. Thomas RastMar 19, 2013
  19. Junio C HamanoMar 19, 2013
  20. Eric SunshineMar 20, 2013
  21. Jeff KingMar 20, 2013
  22. Eric SunshineMar 20, 2013
  23. Duy NguyenMar 19, 2013
  24. index-pack: protect deepest_delta in multithread codeNguyễn Thái Ngọc Duy, Mar 19, 2013
  25. Jeff KingMar 19, 2013
  26. Thomas RastMar 19, 2013
  27. Duy NguyenMar 19, 2013
  28. index-pack: guard nr_resolved_deltas reads by lockThomas Rast, Mar 19, 2013
  29. Junio C HamanoMar 19, 2013
  30. Thomas RastMar 19, 2013
  31. Thomas RastMar 19, 2013
  32. Thomas RastMar 19, 2013
  33. Junio C HamanoMar 19, 2013
  34. sha1_file: remove recursion in packed_object_infoThomas Rast, Mar 19, 2013
  35. Junio C HamanoMar 20, 2013
  36. thomasMar 25, 2013
  37. 0/3 Recursion-free unpack_entry and packed_object_infoThomas Rast, Mar 25, 2013
  38. 1/3 sha1_file: remove recursion in packed_object_infoThomas Rast, Mar 25, 2013
  39. 2/3 Refactor parts of in_delta_base_cache/cache_or_unpack_entryThomas Rast, Mar 25, 2013
  40. Junio C HamanoMar 25, 2013
  41. thomasMar 26, 2013
  42. 3/3 sha1_file: remove recursion in unpack_entryThomas Rast, Mar 25, 2013
  43. Junio C HamanoMar 25, 2013
  44. Nicolas PitreMar 26, 2013
  45. Junio C HamanoMar 25, 2013
  46. Duy NguyenMar 20, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.