Fix REF_DELTA chain bug in 'git index-pack'

When fetching content from a remote, 'git index-pack' processes the packfile content, storing a packfile appropriate for on-disk storage and a pack-index helping to perform random-access into that packfile. To help with compression, the packfile sent over the wire can use REF_DELTAs in addition to OFS_DELTAs to refer to objects that are already known to exist in the client's repository. REF_DELTAs can also refer to objects within the packfile, though this is not typically done.

Because this inter-pack REF_DELTA is not a typical data shape, a latent bug has been waiting that causes 'git index-pack' to die() even on legitimate packfile content that it could resolve.

This series resolves this problem while also creating a test helper for constructing packfiles with specific objects represented in specific types of deltas and in a given order. This should make it easier to create test cases like this in the future instead of updating t/lib-pack.sh through other means.

Thanks, -Stolee

Derrick Stolee (3):
test-tool: add pack-deltas helper
t5309: create failing test for 'git index-pack'
index-pack: allow revisiting REF_DELTA chains

 Makefile                     |   1 +
 builtin/index-pack.c         |  58 ++++++++-------
 t/helper/meson.build         |   1 +
 t/helper/test-pack-deltas.c  | 140 +++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c         |   1 +
 t/helper/test-tool.h         |   1 +
 t/t5309-pack-delta-cycles.sh |  36 ++++++++-
 7 files changed, 210 insertions(+), 28 deletions(-)
 create mode 100644 t/helper/test-pack-deltas.c

base-commit: 4bbb303af69990ccd05fe3a2eb58a1ce036f8220
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1906%2Fderrickstolee%2Findex-pack-ref-deltas-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1906/derrickstolee/index-pack-ref-deltas-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1906

gitgitgadget

From: Derrick Stolee <[email protected]>

When trying to demonstrate certain behavior in tests, it can be helpful to create packfiles that have specific delta structures. 'git pack-objects' uses various algorithms to select deltas based on their compression rates, but that does not always demonstrate all possible packfile shapes. This becomes especially important when wanting to test 'git index-pack' and its ability to parse certain pack shapes.

We have prior art in t/lib-pack.sh, where certain delta structures are produced by manually writing certain opaque pack contents. However, producing these script updates is cumbersome and difficult to do as a contributor.

Instead, create a new test-tool, 'test-tool pack-deltas', that reads a list of instructions for which objects to include in a packfile and how those objects should be written in delta form.

At the moment, this only supports REF_DELTAs as those are the kinds of deltas needed to exercise a bug in 'git index-pack'.

---
 Makefile                    |   1 +
 t/helper/meson.build        |   1 +
 t/helper/test-pack-deltas.c | 140 ++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c        |   1 +
 t/helper/test-tool.h        |   1 +
 5 files changed, 144 insertions(+)
 create mode 100644 t/helper/test-pack-deltas.c

index 13f9062a056..c4d21ccd3d1 100644
@@ -821,6 +821,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
 TEST_BUILTINS_OBJS += test-name-hash.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
+TEST_BUILTINS_OBJS += test-pack-deltas.o
 TEST_BUILTINS_OBJS += test-pack-mtimes.o
 TEST_BUILTINS_OBJS += test-parse-options.o
 TEST_BUILTINS_OBJS += test-parse-pathspec-file.o

index d2cabaa2bcf..d4e8b26df8d 100644
@@ -36,6 +36,7 @@ test_tool_sources = [
   'test-mktemp.c',
   'test-name-hash.c',
   'test-online-cpus.c',
+  'test-pack-deltas.c',
   'test-pack-mtimes.c',
   'test-parse-options.c',
   'test-parse-pathspec-file.c',

index 50dc4dac4ed..74812ed86d3 100644
@@ -46,6 +46,7 @@ static struct test_cmd cmds[] = {
 	{ "mktemp", cmd__mktemp },
 	{ "name-hash", cmd__name_hash },
 	{ "online-cpus", cmd__online_cpus },
+	{ "pack-deltas", cmd__pack_deltas },
 	{ "pack-mtimes", cmd__pack_mtimes },
 	{ "parse-options", cmd__parse_options },
 	{ "parse-options-flags", cmd__parse_options_flags },

index 6d62a5b53d9..2571a3ccfe8 100644
@@ -39,6 +39,7 @@ int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
 int cmd__name_hash(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
+int cmd__pack_deltas(int argc, const char **argv);
 int cmd__pack_mtimes(int argc, const char **argv);
 int cmd__parse_options(int argc, const char **argv);
 int cmd__parse_options_flags(int argc, const char **argv);

gitgitgadget

Wonderful writing. I agree with the destination where this effort wants to go, including the decision that starting with ref-delta only is a good enough first step.

As to the implementation, I was a tiny little bit bummed to see that, even though it does share the code with the real pack-objects code paths to compute delta data by calling diff_delta(), and to write per-object header by calling encode_in_pack_object_header(), it has its own compression loop that does not even do an error checking after calling into zlib deflate machinery.

Perhaps that is unavoidable due to the code structure of the production code.

	test-tool pack-deltas <num-objects>
	int num_objects;

I could strengthen these options to help folks more quickly understand potential failures as being part of the pack write instead of them failing during the later pack read.

I briefly considered extracting some code out of builtin/pack-objects.c but it relies heavily on globals and context that I won't have in this helper. I'm open to suggestions for how I can safely share more code, but my initial attempt required too much refactoring to be worth it.

I am grateful for the amount of code from pack-write.c that I _was_ able to reuse.

I definitely should have used a better name here. Thanks.

-Stolee

I needed this to make

$ SANITIZE=leak GIT_TEST_PASSING_SANITIZE_LEAK=true make
$ cd t && sh t5309-pack-delta-cycles.sh

pass.
--- >8 ------ >8 ------ >8 ---
Subject: [PATCH] fixup! test-tool: add pack-deltas helper

 t/helper/test-pack-deltas.c | 1 +
 1 file changed, 1 insertion(+)

index db7d1c3cd1..c8e837ea06 100644
@@ -122,6 +122,7 @@ int cmd__pack_deltas(int argc, const char **argv)
 			if (get_oid_hex(base_oid_str, &base_oid))
 				die("invalid object: %s", base_oid_str);
 		}
+		string_list_clear(&items, 0);
 
 		if (!strcmp(type_str, "REF_DELTA"))
 			write_ref_delta(f, &content_oid, &base_oid);

2.49.0-555-g43235db9c8

I squashed this in so unless there are other things you need to change, this alone does not make it necessary to reroll the series.

Thanks.

[snip]

Hi Patrick,

I think that parse_options() would be overkill here because:

- This is a _mandatory_ argument, not an optional one.

- The required data type is uint32_t, and parse_options() has no support for that.

But you do have a good point in that we may want to validate the data type (even if technically, this is not a user-facing program, it's a test helper that is used under tight control by Git's own test suite).

Consequently, I would suggest this fixup instead:

-- snipsnap --
Subject: [PATCH] fixup! test-tool: add pack-deltas helper

Let's make the command-line parsing a bit more stringent. We _could_ use parse_options(), but that would be overkill for a single, non-optional argument. Besides, it would not bring any benefit, as the parsed value needs to fit in the uint32_t type, and parse_options() has no provision to ensure that.

---
 t/helper/test-pack-deltas.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

index 4af69bdc05d3..f95d8ee16768 100644
@@ -8,11 +8,12 @@
 #include "hex.h"
 #include "pack.h"
 #include "pack-objects.h"
+#include "parse.h"
 #include "setup.h"
 #include "strbuf.h"
 #include "string-list.h"
 
-static const char usage_str[] = "test-tool pack-deltas <n>";
+static const char usage_str[] = "test-tool pack-deltas <nr_entries>";
 
 static unsigned long do_compress(void **pptr, unsigned long size)
 {

@@ -79,7 +80,7 @@ static void write_ref_delta(struct hashfile *f,
 
 int cmd__pack_deltas(int argc, const char **argv)
 {
-	int N;
+	unsigned long n;
 	struct hashfile *f;
 	struct strbuf line = STRBUF_INIT;
 

@@ -88,12 +89,13 @@ int cmd__pack_deltas(int argc, const char **argv)
 		return -1;
 	}
 
-	N = atoi(argv[1]);
+	if (!git_parse_ulong(argv[1], &n) || n != (uint32_t)n)
+		die("invalid number of objects: %s", argv[1]);
 
 	setup_git_directory();
 
 	f = hashfd(1, "<stdout>");
-	write_pack_header(f, N);
+	write_pack_header(f, n);
 
 	/* Read each line from stdin into 'line' */
 	while (strbuf_getline_lf(&line, stdin) != EOF) {

2.49.0.windows.1

Support for that has been merged just this week via 2bc5414c411 (Merge branch 'ps/parse-options-integers', 2025-04-24).

But in any case, I'd be equally fine with your suggestion.

Patrick

Hi Patrick,

That's too new for me to be useful, as I have to work on top of v2.49.0 (see https://github.com/microsoft/git/pull/745).

Thanks!
Johannes

Yeah, I think we clearly showed our "it's just test helper, whose callers are supposed to know what they are doing" attitude, but with proper helpers, it is not too much additional effort to do the right thing.

Thanks, both.

The thing that confused me even with those changes is that this is a _positional_ argument and we don't have a way to say "parse the 1st positional argument into an integer".

But with this philosophy in mind I can change the CLI to be of the form "--num-objects <n>" to use the parse-options feature. This should make things more extensible in the future.

Thanks,
-Stolee

True. If we are aiming to deliver this to end-user's hands in some future, I agree that we want to make it extensible, make it dtrt without being told, and make it harder to give wrong input. If we are going in that direction [*], I suspect this should not be a separate and independent input---rather, shouldn't the tool already _know_ what objects it placed in the resulting output stream, and should be able to _count_ that number by itself? One thing it lets us do to have this as a separate number is to create an invalid pack stream where the header gives a wrong number, and as a test tool, that may trump the convenience of not having to give the number explicitly.

Another thing we may want to add to the tool is to give it a mode that either (1) refuses to place the same object in a single pack stream more than once, or (2) warn when it happens. The latter would be useful to create an invalid pack stream for testing.

Thanks.

[Footnote]

* ... which I would welcome as the project manager, even though personally I find that 'it is just test helper' attitude attractive. Not everybody in this project is experienced enough to understand the 'it is just test helper, let's not spend too much effort on it' attitude and elements in the code there should not be blindly copied and pasted to production part of the system.

I'm not focused on usability, but instead on faster development cycles if more advanced options are required in the future. I'll happily take some extra time now to help those who come after.

This makes sense as a feature, except that we need to write the number of objects present in a packfile in its header. If we wanted to avoid the argument, then we'd need to load the data into a list before starting to write the packfile. By taking the count in advance, the implementation is simpler.

But also, this allows generating bad packfiles which is a bonus. A very good point.

Noted for potential future expansion.

Thanks,
-Stolee

Perhaps, but in the production code we already seek back and update the header after writing a packfile with fixup_pack_header_footer(), so which shoulnd't be too much work conceptually. You earlier said something about faster development cycles; not having to figure out how to seek back and fix the header does help faster development of this helper ;-).

If this were an end-user facing program, we would most likely let it count but let the count be overridden by the command line argument.

But until then, as I said, I am fine to just declare that it is just a test helper ;-)

Thanks.

From: Derrick Stolee <[email protected]>

This new test demonstrates some behavior where a valid packfile is being rejected by the Git client due to the order in which it is resolving REF_DELTAs.

The thin packfile has a REF_DELTA chain A->B->C where C is not included in the packfile. However, the client repository contains both C and B already. Thus, 'git index-pack' is able to resolve A before resolving B.

When resolving B, it then attempts to resolve any other REF_DELTAs that are pointing to B as a base. This "revisits" A and complains as if there is a cycle, but it did not actually detect a cycle.

A fix will arrive in the next change.

---
 t/t5309-pack-delta-cycles.sh | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

index 60fc710bacb..9029f8a0dda 100755
@@ -75,4 +75,30 @@ test_expect_success 'failover to a duplicate object in the same pack' '
 	test_must_fail git index-pack --fix-thin --stdin <recoverable.pack
 '
 
+test_expect_failure 'index-pack works with thin pack A->B->C with B on disk' '
+	git init server &&
+	(
+		cd server &&
+		test_commit_bulk 4
+	) &&
+
+	A=$(git -C server rev-parse HEAD^{tree}) &&
+	B=$(git -C server rev-parse HEAD~1^{tree}) &&
+	C=$(git -C server rev-parse HEAD~2^{tree}) &&
+	git -C server reset --hard HEAD~1 &&
+
+	cat >in <<-EOF &&
+	REF_DELTA $A $B
+	REF_DELTA $B $C
+	EOF
+
+	test-tool -C server pack-deltas 2 <in >thin.pack &&
+
+	git clone "file://$(pwd)/server" client &&
+	(
+		cd client &&
+		git index-pack --fix-thin --stdin <../thin.pack
+	)
+'
+
 test_done

gitgitgadget

In order to reconstitute A, B is needed (which recipient has), and in order to reconstitute B, C is needed (which recipient also has).

The index-pack sees delta based on B to recreate A; it should be able to reconstitute A using B that already exists.

OK.

That's interesting.

From: Derrick Stolee <[email protected]>

As detailed in the previous changes to t5309-pack-delta-cycles.sh, the logic within 'git index-pack' to analyze an incoming thin packfile with REF_DELTAs is suspect. The algorithm is overly cautious around delta cycles, and that leads in fact to failing even when there is no cycle.

This change adjusts the algorithm to no longer fail in these cases. In fact, these cycle cases will no longer fail but more importantly the valid cases will no longer fail, either. The resulting packfile from the --fix-thin operation will not have cycles either since REF_DELTAs are forbidden from the on-disk format and OFS_DELTAs are impossible to write as a cycle.

The crux of the matter is how the algorithm works when the REF_DELTAs point to base objects that exist in the local repository. When reading the thin packfile, the object IDs for the delta objects are unknown so we do not have the delta chain structure automatically. Instead, we need to start somewhere by selecting a delta whose base is inside our current object database.

Consider the case where the packfile has two REF_DELTA objects, A and B, and the delta chain looks like "A depends on B" and "B depends on C" for some third object C, where C is already in the current repository. The algorithm _should_ start with all objects that depend on C, finding B, and then moving on to all objects depending on B, finding A.

However, if the repository also already has object B, then the delta chain can be analyzed in a different order. The deltas with base B can be analyzed first, finding A, and then the deltas with base C are analyzed, finding B. The algorithm currently continues to look for objects that depend on B, finding A again. This fails due to A's 'real_type' member already being overwritten from OBJ_REF_DELTA to the correct object type.

This scenario is possible in a typical 'git fetch' where the client does not advertise B as a 'have' but requests A as a 'want' (and C is noticed as a common object based on other 'have's). The reason this isn't typically seen is that most Git servers use OFS_DELTAs to represent deltas within a packfile. However, if a server uses only REF_DELTAs, then this kind of issue can occur. There is nothing in the explicit packfile format that states this use of inter-pack REF_DELTA is incorrect, only that REF_DELTAs should not be used in the on-disk representation to avoid cycles.

This die() was introduced in ab791dd138 (index-pack: fix race condition with duplicate bases, 2014-08-29). Several refactors have adjusted the error message and the surrounding logic, but this issue has existed for a longer time as that was only a conversion from an assert().

The tests in t5309 originated in 3b910d0c5e (add tests for indexing packs with delta cycles, 2013-08-23) and b2ef3d9ebb (test index-pack on packs with recoverable delta cycles, 2013-08-23). These changes make note that the current behavior of handling "resolvable" cycles is mostly a documentation-only test, not that this behavior is the best way for Git to handle the situation.

The fix here is somewhat complicated due to the amount of state being adjusted by the loop within threaded_second_pass(). Instead of trying to resume the start of the loop while adjusting the necessary context, I chose to scan the REF_DELTAs depending on the current 'parent' and skip any that have already been processed. This necessarily leaves us in a state where 'child' and 'child_obj' could be left as NULL and that must be handled later. There is also some careful handling around skipping REF_DELTAs when there are also OFS_DELTAs depending on that parent. There may be value in extending 'test-tool pack-deltas' to allow writing OFS_DELTAs in order to exercise this logic across the delta types.

---
 builtin/index-pack.c         | 58 ++++++++++++++++++++----------------
 t/t5309-pack-delta-cycles.sh | 12 ++++++--
 2 files changed, 41 insertions(+), 29 deletions(-)

index de127c0ff13..dbe79701fb8 100644
@@ -1109,8 +1109,8 @@ static void *threaded_second_pass(void *data)
 		set_thread_data(data);
 	for (;;) {
 		struct base_data *parent = NULL;
-		struct object_entry *child_obj;
-		struct base_data *child;
+		struct object_entry *child_obj = NULL;
+		struct base_data *child = NULL;
 
 		counter_lock();
 		display_progress(progress, nr_resolved_deltas);

@@ -1137,15 +1137,18 @@ static void *threaded_second_pass(void *data)
 			parent = list_first_entry(&work_head, struct base_data,
 						  list);
 
-			if (parent->ref_first <= parent->ref_last) {
+			while (parent->ref_first <= parent->ref_last) {
 				int offset = ref_deltas[parent->ref_first++].obj_no;
 				child_obj = objects + offset;
-				if (child_obj->real_type != OBJ_REF_DELTA)
-					die("REF_DELTA at offset %"PRIuMAX" already resolved (duplicate base %s?)",
-					    (uintmax_t) child_obj->idx.offset,
-					    oid_to_hex(&parent->obj->idx.oid));
+				if (child_obj->real_type != OBJ_REF_DELTA) {
+					child_obj = NULL;
+					continue;
+				}
 				child_obj->real_type = parent->obj->real_type;
-			} else {
+				break;
+			}
+
+			if (!child_obj && parent->ofs_first <= parent->ofs_last) {
 				child_obj = objects +
 					ofs_deltas[parent->ofs_first++].obj_no;
 				assert(child_obj->real_type == OBJ_OFS_DELTA);

@@ -1178,29 +1181,32 @@ static void *threaded_second_pass(void *data)
 		}
 		work_unlock();
 
-		if (parent) {
-			child = resolve_delta(child_obj, parent);
-			if (!child->children_remaining)
-				FREE_AND_NULL(child->data);
-		} else {
-			child = make_base(child_obj, NULL);
-			if (child->children_remaining) {
-				/*
-				 * Since this child has its own delta children,
-				 * we will need this data in the future.
-				 * Inflate now so that future iterations will
-				 * have access to this object's data while
-				 * outside the work mutex.
-				 */
-				child->data = get_data_from_pack(child_obj);
-				child->size = child_obj->size;
+		if (child_obj) {
+			if (parent) {
+				child = resolve_delta(child_obj, parent);
+				if (!child->children_remaining)
+					FREE_AND_NULL(child->data);
+			} else{
+				child = make_base(child_obj, NULL);
+				if (child->children_remaining) {
+					/*
+					 * Since this child has its own delta children,
+					 * we will need this data in the future.
+					 * Inflate now so that future iterations will
+					 * have access to this object's data while
+					 * outside the work mutex.
+					 */
+					child->data = get_data_from_pack(child_obj);
+					child->size = child_obj->size;
+				}
 			}
 		}
 
 		work_lock();
 		if (parent)
 			parent->retain_data--;
-		if (child->data) {
+
+		if (child && child->data) {
 			/*
 			 * This child has its own children, so add it to
 			 * work_head.

@@ -1209,7 +1215,7 @@ static void *threaded_second_pass(void *data)
 			base_cache_used += child->size;
 			prune_base_data(NULL);
 			free_base_data(child);
-		} else {
+		} else if (child) {
 			/*
 			 * This child does not have its own children. It may be
 			 * the last descendant of its ancestors; free those

index 9029f8a0dda..fc3594aaae9 100755
@@ -60,7 +60,10 @@ test_expect_success 'index-pack detects REF_DELTA cycles' '
 test_expect_success 'failover to an object in another pack' '
 	clear_packs &&
 	git index-pack --stdin <ab.pack &&
-	test_must_fail git index-pack --stdin --fix-thin <cycle.pack
+
+	# This cycle does not fail since the existence of A & B in
+	# the repo allows us to resolve the cycle.
+	git index-pack --stdin --fix-thin <cycle.pack
 '
 
 test_expect_success 'failover to a duplicate object in the same pack' '

@@ -72,10 +75,13 @@ test_expect_success 'failover to a duplicate object in the same pack' '
 		pack_obj $A
 	} >recoverable.pack &&
 	pack_trailer recoverable.pack &&
-	test_must_fail git index-pack --fix-thin --stdin <recoverable.pack
+
+	# This cycle does not fail since the existence of a full copy
+	# of A in the pack allows us to resolve the cycle.
+	git index-pack --fix-thin --stdin <recoverable.pack
 '
 
-test_expect_failure 'index-pack works with thin pack A->B->C with B on disk' '
+test_expect_success 'index-pack works with thin pack A->B->C with B on disk' '
 	git init server &&
 	(
 		cd server &&

gitgitgadget

Loosening cycle avoidance indeed is worrysome. How do we guarantee "since REF_DELTAs are forbidden from the on-disk format" (it is obvious with OFS_DELTA only you cannot form a cycle)? By code inspection and in-code comment for the code path of "--fix-thin"?

I think the most interesting question would be how, with the loosening of the cycle check in this patch, we would still protect against a malicious on-the-wire packdata that has a cycle in it already, where deltas cannot be resolved.

The good news is two-fold:

1. We have a test in t5309 (index-pack detects REF_DELTA cycles) that checks this case and did not change behavior with this patch.

2. If we don't already have any of the objects that exist in the cycle, then we can't _start_ expanding the objects to their full contents as we don't have their bases. So what is left is a list of REF_DELTAs that have not been processed but also a list of base object IDs that we can't load. We'll fail without writing those objects to disk.

Does that satisfy your concerns in this space?

Thanks,
-Stolee

When fetching content from a remote, 'git index-pack' processes the packfile content, storing a packfile appropriate for on-disk storage and a pack-index helping to perform random-access into that packfile. To help with compression, the packfile sent over the wire can use REF_DELTAs in addition to OFS_DELTAs to refer to objects that are already known to exist in the client's repository. REF_DELTAs can also refer to objects within the packfile, though this is not typically done.

Because this inter-pack REF_DELTA is not a typical data shape, a latent bug has been waiting that causes 'git index-pack' to die() even on legitimate packfile content that it could resolve.

This series resolves this problem while also creating a test helper for constructing packfiles with specific objects represented in specific types of deltas and in a given order. This should make it easier to create test cases like this in the future instead of updating t/lib-pack.sh through other means.

Updates in V2
=============

* Fixed a memory leak in the test helper.
* The test helper has a better CLI that makes use of the parse-options library.
* The test script skips the in file and instead feeds the input directly to the test helper.

Thanks, -Stolee

Derrick Stolee (3):
test-tool: add pack-deltas helper
t5309: create failing test for 'git index-pack'
index-pack: allow revisiting REF_DELTA chains

 Makefile                     |   1 +
 builtin/index-pack.c         |  58 ++++++++------
 t/helper/meson.build         |   1 +
 t/helper/test-pack-deltas.c  | 148 +++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c         |   1 +
 t/helper/test-tool.h         |   1 +
 t/t5309-pack-delta-cycles.sh |  34 +++++++-
 7 files changed, 216 insertions(+), 28 deletions(-)
 create mode 100644 t/helper/test-pack-deltas.c

base-commit: 4bbb303af69990ccd05fe3a2eb58a1ce036f8220
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1906%2Fderrickstolee%2Findex-pack-ref-deltas-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1906/derrickstolee/index-pack-ref-deltas-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1906

Range-diff vs v1:

1: 5d4beb202d6 ! 1: 41aac8e782f test-tool: add pack-deltas helper

     @@ t/helper/test-pack-deltas.c (new)
      +#include "hex.h"
      +#include "pack.h"
      +#include "pack-objects.h"
     ++#include "parse-options.h"
      +#include "setup.h"
      +#include "strbuf.h"
      +#include "string-list.h"
      +
     -+static const char usage_str[] = "test-tool pack-deltas <n>";
     ++static const char *usage_str[] = {
     ++	"test-tool pack-deltas --num-objects <num-objects>",
     ++	NULL
     ++};
      +
      +static unsigned long do_compress(void **pptr, unsigned long size)
      +{
     @@ t/helper/test-pack-deltas.c (new)
      +
      +int cmd__pack_deltas(int argc, const char **argv)
      +{
     -+	int N;
     ++	int num_objects = -1;
      +	struct hashfile *f;
      +	struct strbuf line = STRBUF_INIT;
     ++	struct option options[] = {
     ++		OPT_INTEGER('n', "num-objects", &num_objects, N_("the number of objects to write")),
     ++		OPT_END()
     ++	};
      +
     -+	if (argc != 2) {
     -+		usage(usage_str);
     -+		return -1;
     -+	}
     ++	argc = parse_options(argc, argv, NULL,
     ++			     options, usage_str, 0);
      +
     -+	N = atoi(argv[1]);
     ++	if (argc || num_objects < 0)
     ++		usage_with_options(usage_str, options);
      +
      +	setup_git_directory();
      +
      +	f = hashfd(the_repository->hash_algo, 1, "<stdout>");
     -+	write_pack_header(f, N);
     ++	write_pack_header(f, num_objects);
      +
      +	/* Read each line from stdin into 'line' */
      +	while (strbuf_getline_lf(&line, stdin) != EOF) {
     @@ t/helper/test-pack-deltas.c (new)
      +			if (get_oid_hex(base_oid_str, &base_oid))
      +				die("invalid object: %s", base_oid_str);
      +		}
     ++		string_list_clear(&items, 0);
      +
      +		if (!strcmp(type_str, "REF_DELTA"))
      +			write_ref_delta(f, &content_oid, &base_oid);
 2:  a9430447641 ! 2:  53a990e69ea t5309: create failing test for 'git index-pack'
     @@ t/t5309-pack-delta-cycles.sh: test_expect_success 'failover to a duplicate objec
      +	C=$(git -C server rev-parse HEAD~2^{tree}) &&
      +	git -C server reset --hard HEAD~1 &&
      +
     -+	cat >in <<-EOF &&
     ++	test-tool -C server pack-deltas --num-objects=2 >thin.pack <<-EOF &&
      +	REF_DELTA $A $B
      +	REF_DELTA $B $C
      +	EOF
      +
     -+	test-tool -C server pack-deltas 2 <in >thin.pack &&
     -+
      +	git clone "file://$(pwd)/server" client &&
      +	(
      +		cd client &&

3: 27d36402fe9 = 3: 1358039b2f3 index-pack: allow revisiting REF_DELTA chains

gitgitgadget

From: Derrick Stolee <[email protected]>

When trying to demonstrate certain behavior in tests, it can be helpful to create packfiles that have specific delta structures. 'git pack-objects' uses various algorithms to select deltas based on their compression rates, but that does not always demonstrate all possible packfile shapes. This becomes especially important when wanting to test 'git index-pack' and its ability to parse certain pack shapes.

We have prior art in t/lib-pack.sh, where certain delta structures are produced by manually writing certain opaque pack contents. However, producing these script updates is cumbersome and difficult to do as a contributor.

Instead, create a new test-tool, 'test-tool pack-deltas', that reads a list of instructions for which objects to include in a packfile and how those objects should be written in delta form.

At the moment, this only supports REF_DELTAs as those are the kinds of deltas needed to exercise a bug in 'git index-pack'.

---
 Makefile                    |   1 +
 t/helper/meson.build        |   1 +
 t/helper/test-pack-deltas.c | 148 ++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c        |   1 +
 t/helper/test-tool.h        |   1 +
 5 files changed, 152 insertions(+)
 create mode 100644 t/helper/test-pack-deltas.c

index 13f9062a056..c4d21ccd3d1 100644
@@ -821,6 +821,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
 TEST_BUILTINS_OBJS += test-name-hash.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
+TEST_BUILTINS_OBJS += test-pack-deltas.o
 TEST_BUILTINS_OBJS += test-pack-mtimes.o
 TEST_BUILTINS_OBJS += test-parse-options.o
 TEST_BUILTINS_OBJS += test-parse-pathspec-file.o

index d2cabaa2bcf..d4e8b26df8d 100644
@@ -36,6 +36,7 @@ test_tool_sources = [
   'test-mktemp.c',
   'test-name-hash.c',
   'test-online-cpus.c',
+  'test-pack-deltas.c',
   'test-pack-mtimes.c',
   'test-parse-options.c',
   'test-parse-pathspec-file.c',

index 50dc4dac4ed..74812ed86d3 100644
@@ -46,6 +46,7 @@ static struct test_cmd cmds[] = {
 	{ "mktemp", cmd__mktemp },
 	{ "name-hash", cmd__name_hash },
 	{ "online-cpus", cmd__online_cpus },
+	{ "pack-deltas", cmd__pack_deltas },
 	{ "pack-mtimes", cmd__pack_mtimes },
 	{ "parse-options", cmd__parse_options },
 	{ "parse-options-flags", cmd__parse_options_flags },

index 6d62a5b53d9..2571a3ccfe8 100644
@@ -39,6 +39,7 @@ int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
 int cmd__name_hash(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
+int cmd__pack_deltas(int argc, const char **argv);
 int cmd__pack_mtimes(int argc, const char **argv);
 int cmd__parse_options(int argc, const char **argv);
 int cmd__parse_options_flags(int argc, const char **argv);

gitgitgadget

From: Derrick Stolee <[email protected]>

This new test demonstrates some behavior where a valid packfile is being rejected by the Git client due to the order in which it is resolving REF_DELTAs.

The thin packfile has a REF_DELTA chain A->B->C where C is not included in the packfile. However, the client repository contains both C and B already. Thus, 'git index-pack' is able to resolve A before resolving B.

When resolving B, it then attempts to resolve any other REF_DELTAs that are pointing to B as a base. This "revisits" A and complains as if there is a cycle, but it did not actually detect a cycle.

A fix will arrive in the next change.

---
 t/t5309-pack-delta-cycles.sh | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

index 60fc710bacb..6a936763302 100755
@@ -75,4 +75,28 @@ test_expect_success 'failover to a duplicate object in the same pack' '
 	test_must_fail git index-pack --fix-thin --stdin <recoverable.pack
 '
 
+test_expect_failure 'index-pack works with thin pack A->B->C with B on disk' '
+	git init server &&
+	(
+		cd server &&
+		test_commit_bulk 4
+	) &&
+
+	A=$(git -C server rev-parse HEAD^{tree}) &&
+	B=$(git -C server rev-parse HEAD~1^{tree}) &&
+	C=$(git -C server rev-parse HEAD~2^{tree}) &&
+	git -C server reset --hard HEAD~1 &&
+
+	test-tool -C server pack-deltas --num-objects=2 >thin.pack <<-EOF &&
+	REF_DELTA $A $B
+	REF_DELTA $B $C
+	EOF
+
+	git clone "file://$(pwd)/server" client &&
+	(
+		cd client &&
+		git index-pack --fix-thin --stdin <../thin.pack
+	)
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

As detailed in the previous changes to t5309-pack-delta-cycles.sh, the logic within 'git index-pack' to analyze an incoming thin packfile with REF_DELTAs is suspect. The algorithm is overly cautious around delta cycles, and that leads in fact to failing even when there is no cycle.

This change adjusts the algorithm to no longer fail in these cases. In fact, these cycle cases will no longer fail but more importantly the valid cases will no longer fail, either. The resulting packfile from the --fix-thin operation will not have cycles either since REF_DELTAs are forbidden from the on-disk format and OFS_DELTAs are impossible to write as a cycle.

The crux of the matter is how the algorithm works when the REF_DELTAs point to base objects that exist in the local repository. When reading the thin packfile, the object IDs for the delta objects are unknown so we do not have the delta chain structure automatically. Instead, we need to start somewhere by selecting a delta whose base is inside our current object database.

Consider the case where the packfile has two REF_DELTA objects, A and B, and the delta chain looks like "A depends on B" and "B depends on C" for some third object C, where C is already in the current repository. The algorithm _should_ start with all objects that depend on C, finding B, and then moving on to all objects depending on B, finding A.

However, if the repository also already has object B, then the delta chain can be analyzed in a different order. The deltas with base B can be analyzed first, finding A, and then the deltas with base C are analyzed, finding B. The algorithm currently continues to look for objects that depend on B, finding A again. This fails due to A's 'real_type' member already being overwritten from OBJ_REF_DELTA to the correct object type.

This scenario is possible in a typical 'git fetch' where the client does not advertise B as a 'have' but requests A as a 'want' (and C is noticed as a common object based on other 'have's). The reason this isn't typically seen is that most Git servers use OFS_DELTAs to represent deltas within a packfile. However, if a server uses only REF_DELTAs, then this kind of issue can occur. There is nothing in the explicit packfile format that states this use of inter-pack REF_DELTA is incorrect, only that REF_DELTAs should not be used in the on-disk representation to avoid cycles.

This die() was introduced in ab791dd138 (index-pack: fix race condition with duplicate bases, 2014-08-29). Several refactors have adjusted the error message and the surrounding logic, but this issue has existed for a longer time as that was only a conversion from an assert().

The tests in t5309 originated in 3b910d0c5e (add tests for indexing packs with delta cycles, 2013-08-23) and b2ef3d9ebb (test index-pack on packs with recoverable delta cycles, 2013-08-23). These changes make note that the current behavior of handling "resolvable" cycles is mostly a documentation-only test, not that this behavior is the best way for Git to handle the situation.

The fix here is somewhat complicated due to the amount of state being adjusted by the loop within threaded_second_pass(). Instead of trying to resume the start of the loop while adjusting the necessary context, I chose to scan the REF_DELTAs depending on the current 'parent' and skip any that have already been processed. This necessarily leaves us in a state where 'child' and 'child_obj' could be left as NULL and that must be handled later. There is also some careful handling around skipping REF_DELTAs when there are also OFS_DELTAs depending on that parent. There may be value in extending 'test-tool pack-deltas' to allow writing OFS_DELTAs in order to exercise this logic across the delta types.

---
 builtin/index-pack.c         | 58 ++++++++++++++++++++----------------
 t/t5309-pack-delta-cycles.sh | 12 ++++++--
 2 files changed, 41 insertions(+), 29 deletions(-)

index de127c0ff13..dbe79701fb8 100644
@@ -1109,8 +1109,8 @@ static void *threaded_second_pass(void *data)
 		set_thread_data(data);
 	for (;;) {
 		struct base_data *parent = NULL;
-		struct object_entry *child_obj;
-		struct base_data *child;
+		struct object_entry *child_obj = NULL;
+		struct base_data *child = NULL;
 
 		counter_lock();
 		display_progress(progress, nr_resolved_deltas);

@@ -1137,15 +1137,18 @@ static void *threaded_second_pass(void *data)
 			parent = list_first_entry(&work_head, struct base_data,
 						  list);
 
-			if (parent->ref_first <= parent->ref_last) {
+			while (parent->ref_first <= parent->ref_last) {
 				int offset = ref_deltas[parent->ref_first++].obj_no;
 				child_obj = objects + offset;
-				if (child_obj->real_type != OBJ_REF_DELTA)
-					die("REF_DELTA at offset %"PRIuMAX" already resolved (duplicate base %s?)",
-					    (uintmax_t) child_obj->idx.offset,
-					    oid_to_hex(&parent->obj->idx.oid));
+				if (child_obj->real_type != OBJ_REF_DELTA) {
+					child_obj = NULL;
+					continue;
+				}
 				child_obj->real_type = parent->obj->real_type;
-			} else {
+				break;
+			}
+
+			if (!child_obj && parent->ofs_first <= parent->ofs_last) {
 				child_obj = objects +
 					ofs_deltas[parent->ofs_first++].obj_no;
 				assert(child_obj->real_type == OBJ_OFS_DELTA);

@@ -1178,29 +1181,32 @@ static void *threaded_second_pass(void *data)
 		}
 		work_unlock();
 
-		if (parent) {
-			child = resolve_delta(child_obj, parent);
-			if (!child->children_remaining)
-				FREE_AND_NULL(child->data);
-		} else {
-			child = make_base(child_obj, NULL);
-			if (child->children_remaining) {
-				/*
-				 * Since this child has its own delta children,
-				 * we will need this data in the future.
-				 * Inflate now so that future iterations will
-				 * have access to this object's data while
-				 * outside the work mutex.
-				 */
-				child->data = get_data_from_pack(child_obj);
-				child->size = child_obj->size;
+		if (child_obj) {
+			if (parent) {
+				child = resolve_delta(child_obj, parent);
+				if (!child->children_remaining)
+					FREE_AND_NULL(child->data);
+			} else{
+				child = make_base(child_obj, NULL);
+				if (child->children_remaining) {
+					/*
+					 * Since this child has its own delta children,
+					 * we will need this data in the future.
+					 * Inflate now so that future iterations will
+					 * have access to this object's data while
+					 * outside the work mutex.
+					 */
+					child->data = get_data_from_pack(child_obj);
+					child->size = child_obj->size;
+				}
 			}
 		}
 
 		work_lock();
 		if (parent)
 			parent->retain_data--;
-		if (child->data) {
+
+		if (child && child->data) {
 			/*
 			 * This child has its own children, so add it to
 			 * work_head.

@@ -1209,7 +1215,7 @@ static void *threaded_second_pass(void *data)
 			base_cache_used += child->size;
 			prune_base_data(NULL);
 			free_base_data(child);
-		} else {
+		} else if (child) {
 			/*
 			 * This child does not have its own children. It may be
 			 * the last descendant of its ancestors; free those

index 6a936763302..6b03675d91b 100755
@@ -60,7 +60,10 @@ test_expect_success 'index-pack detects REF_DELTA cycles' '
 test_expect_success 'failover to an object in another pack' '
 	clear_packs &&
 	git index-pack --stdin <ab.pack &&
-	test_must_fail git index-pack --stdin --fix-thin <cycle.pack
+
+	# This cycle does not fail since the existence of A & B in
+	# the repo allows us to resolve the cycle.
+	git index-pack --stdin --fix-thin <cycle.pack
 '
 
 test_expect_success 'failover to a duplicate object in the same pack' '

@@ -72,10 +75,13 @@ test_expect_success 'failover to a duplicate object in the same pack' '
 		pack_obj $A
 	} >recoverable.pack &&
 	pack_trailer recoverable.pack &&
-	test_must_fail git index-pack --fix-thin --stdin <recoverable.pack
+
+	# This cycle does not fail since the existence of a full copy
+	# of A in the pack allows us to resolve the cycle.
+	git index-pack --fix-thin --stdin <recoverable.pack
 '
 
-test_expect_failure 'index-pack works with thin pack A->B->C with B on disk' '
+test_expect_success 'index-pack works with thin pack A->B->C with B on disk' '
 	git init server &&
 	(
 		cd server &&

gitgitgadget

Hmm. I'm having trouble squaring this with these next two paragraphs:

ISTM that this A->B->C chain is a problem because (in the above example) the server sent B as a REF_DELTA base for A but also had its own pre-existing copy of B.

But the first quoted sentence suggests that the issue is with REF_DELTAs that point to base objects that exist in the local repository. Does "point to" mean that the REF_DELTA's base is the local object, or that the local object itself was sent as a REF_DELTA against some other base?

I haven't fully wrapped my head around the implications of this all yet, but I think that it's the former, though admittedly even typing this I am not quite sure of myself. I *think* that doing this is OK if the only path from base objects to their corresponding deltas is unique, and/or there were no such paths at all.

I'm trying to think through the implications of this against my series[1] from a while ago that converts OFS_DELTAs that weren't usable as part of verbatim pack-reuse into REF_DELTAs. There are two cases there that I was considering:

- For some (delta, base) pair in a pack, there was an additional copy of 'base' in some other pack, and the MIDX chose the copy from that pack. That forms what I'm calling a "cross-pack" delta. This isn't currently reusable as an OFS_DELTA for a variety of reasons, but is OK as a REF_DELTA provided we know that the client either already has the base object or we are sending it as part of the pack anyway.

- The other case is that we the client wants the delta-half of a delta/base-pair, but not the base object. In this case, we can't currently reuse the OFS_DELTA verbatim, but could if we converted it to a REF_DELTA based on the knowledge that the client already has the base object.

The latter is doable based on the information in the wants/haves bitmap. The process there looks like: determine that the client doesn't want the base object, realize that its bit is set in the 'haves' bitmap, and then convert the delta object from a OFS_DELTA to a REF_DELTA.

But I think that all breaks for older clients that don't meet the unique paths condition above. Does that sound right to you?

I think the cross-pack case is fine, provided we know ahead of time that the client doesn't have the (converted-to-REF_DELTA) delta object in its local copy.

Unfortunately, I think this means that [1] is a bit of a dead-end for serves that have older clients (running a version that does not include this patch). At least, I think that's true if we can construct a situation where the server sends a REF_DELTA that it thinks the client doesn't have but actually does. I'm not immediately sure what such a situation would look like beyond cases like: "the client verbatim asked for an object it already has, but isn't reachable from the set of provided 'haves'".

Thanks,
Taylor

[1]: https://lore.kernel.org/git/[email protected]/

The issue is that based on the negotiation, the server knows the client wants A and has C but doesn't think the client has B despite the client having B.

If the server sends these two objects as a delta chain A->B->C using REF_DELTAs (and not the typical OFS_DELTA from A to B) then the client may inflate A first and B second (and then try to inflate A again).

These are the kinds of deltas that could hit this problem.

If we know the client has the base object, then not including the base in the pack and referencing it as a REF_DELTA will always be OK.

I agree that [1] is going to present more opportunities for this bug to be hit by older clients, though I will admit that the frequency of the problem seems to have odd frequencies. It relies upon the fact that the fetch negotiation fails to identify "B" as a common object. This sort of thing can happen more frequently when using the commit boundary between the haves and wants (instead of walking from all haves like a bitmap walk would do). If the client fails to advertise all of its haves, then that could also lead to this problem even if the server is walking all objects reachable from the haves.

The other thing that you'll have going for you is that cross-pack deltas should be rare. The case that helped me discover this issue was where the server did not send any OFS_DELTAs at all but used REF_DELTAs for all delta relationships. (This is required if the client doesn't advertise the "ofs-delta" capability, but we'd need to go _way_ back for a client to not include that capability.)

Thanks,
-Stolee

Everything in the changes relative to the previous iteration looked quite sane. Will replace. Thanks.

Seconded, the range-diff looks as expected and addresses my comments. Thanks!

Patrick