{"thread":{"id":"63337","subject":"[PATCH 0/3] Fix REF_DELTA chain bug in 'git index-pack'","startedAt":"2025-04-23T17:40:07Z","lastAt":"2025-05-07T13:47:48Z","messageCount":29,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Derrick Stolee","Patrick Steinhardt","Johannes Schindelin","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"516617","messageId":"pull.1906.git.1745430004.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":null,"subject":"[PATCH 0/3] Fix REF_DELTA chain bug in 'git index-pack'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-23T17:40:01Z","receivedAt":"2025-04-23T17:40:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"When fetching content from a remote, 'git index-pack' processes the packfile\ncontent, storing a packfile appropriate for on-disk storage and a pack-index\nhelping to perform random-access into that packfile. To help with\ncompression, the packfile sent over the wire can use REF_DELTAs in addition\nto OFS_DELTAs to refer to objects that are already known to exist in the\nclient's repository. REF_DELTAs can also refer to objects within the\npackfile, though this is not typically done.\n\nBecause this inter-pack REF_DELTA is not a typical data shape, a latent bug\nhas been waiting that causes 'git index-pack' to die() even on legitimate\npackfile content that it could resolve.\n\nThis series resolves this problem while also creating a test helper for\nconstructing packfiles with specific objects represented in specific types\nof deltas and in a given order. This should make it easier to create test\ncases like this in the future instead of updating t/lib-pack.sh through\nother means.\n\nThanks, -Stolee\n\nDerrick Stolee (3):\n test-tool: add pack-deltas helper\n t5309: create failing test for 'git index-pack'\n index-pack: allow revisiting REF_DELTA chains\n\n Makefile | 1 +\n builtin/index-pack.c | 58 ++++++++-------\n t/helper/meson.build | 1 +\n t/helper/test-pack-deltas.c | 140 +++++++++++++++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/t5309-pack-delta-cycles.sh | 36 ++++++++-\n 7 files changed, 210 insertions(+), 28 deletions(-)\n create mode 100644 t/helper/test-pack-deltas.c\n\n\nbase-commit: 4bbb303af69990ccd05fe3a2eb58a1ce036f8220\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1906%2Fderrickstolee%2Findex-pack-ref-deltas-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1906/derrickstolee/index-pack-ref-deltas-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1906\n-- \ngitgitgadget\n"},{"id":"516618","messageId":"5d4beb202d6ed842de72928462a10a4f5faa2718.1745430004.git.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":"pull.1906.git.1745430004.gitgitgadget@gmail.com","subject":"[PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-23T17:40:02Z","receivedAt":"2025-04-23T17:40:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen trying to demonstrate certain behavior in tests, it can be helpful\nto create packfiles that have specific delta structures. 'git\npack-objects' uses various algorithms to select deltas based on their\ncompression rates, but that does not always demonstrate all possible\npackfile shapes. This becomes especially important when wanting to test\n'git index-pack' and its ability to parse certain pack shapes.\n\nWe have prior art in t/lib-pack.sh, where certain delta structures are\nproduced by manually writing certain opaque pack contents. However,\nproducing these script updates is cumbersome and difficult to do as a\ncontributor.\n\nInstead, create a new test-tool, 'test-tool pack-deltas', that reads a\nlist of instructions for which objects to include in a packfile and how\nthose objects should be written in delta form.\n\nAt the moment, this only supports REF_DELTAs as those are the kinds of\ndeltas needed to exercise a bug in 'git index-pack'.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n t/helper/meson.build | 1 +\n t/helper/test-pack-deltas.c | 140 ++++++++++++++++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n 5 files changed, 144 insertions(+)\n create mode 100644 t/helper/test-pack-deltas.c\n\ndiff --git a/Makefile b/Makefile\nindex 13f9062a056..c4d21ccd3d1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -821,6 +821,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o\n TEST_BUILTINS_OBJS += test-mktemp.o\n TEST_BUILTINS_OBJS += test-name-hash.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\n+TEST_BUILTINS_OBJS += test-pack-deltas.o\n TEST_BUILTINS_OBJS += test-pack-mtimes.o\n TEST_BUILTINS_OBJS += test-parse-options.o\n TEST_BUILTINS_OBJS += test-parse-pathspec-file.o\ndiff --git a/t/helper/meson.build b/t/helper/meson.build\nindex d2cabaa2bcf..d4e8b26df8d 100644\n--- a/t/helper/meson.build\n+++ b/t/helper/meson.build\n@@ -36,6 +36,7 @@ test_tool_sources = [\n 'test-mktemp.c',\n 'test-name-hash.c',\n 'test-online-cpus.c',\n+ 'test-pack-deltas.c',\n 'test-pack-mtimes.c',\n 'test-parse-options.c',\n 'test-parse-pathspec-file.c',\ndiff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\nnew file mode 100644\nindex 00000000000..db7d1c3cd1f\n--- /dev/null\n+++ b/t/helper/test-pack-deltas.c\n@@ -0,0 +1,140 @@\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n+#include \"test-tool.h\"\n+#include \"git-compat-util.h\"\n+#include \"delta.h\"\n+#include \"git-zlib.h\"\n+#include \"hash.h\"\n+#include \"hex.h\"\n+#include \"pack.h\"\n+#include \"pack-objects.h\"\n+#include \"setup.h\"\n+#include \"strbuf.h\"\n+#include \"string-list.h\"\n+\n+static const char usage_str[] = \"test-tool pack-deltas \";\n+\n+static unsigned long do_compress(void **pptr, unsigned long size)\n+{\n+\tgit_zstream stream;\n+\tvoid *in, *out;\n+\tunsigned long maxsize;\n+\n+\tgit_deflate_init(&stream, 1);\n+\tmaxsize = git_deflate_bound(&stream, size);\n+\n+\tin = *pptr;\n+\tout = xmalloc(maxsize);\n+\t*pptr = out;\n+\n+\tstream.next_in = in;\n+\tstream.avail_in = size;\n+\tstream.next_out = out;\n+\tstream.avail_out = maxsize;\n+\twhile (git_deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t; /* nothing */\n+\tgit_deflate_end(&stream);\n+\n+\tfree(in);\n+\treturn stream.total_out;\n+}\n+\n+static void write_ref_delta(struct hashfile *f,\n+\t\t\t struct object_id *oid,\n+\t\t\t struct object_id *base)\n+{\n+\tunsigned char header[MAX_PACK_OBJECT_HEADER];\n+\tunsigned long size, base_size, delta_size, compressed_size, hdrlen;\n+\tenum object_type type;\n+\tvoid *base_buf, *delta_buf;\n+\tvoid *buf = repo_read_object_file(the_repository,\n+\t\t\t\t\t oid, &type,\n+\t\t\t\t\t &size);\n+\n+\tif (!buf)\n+\t\tdie(\"unable to read %s\", oid_to_hex(oid));\n+\n+\tbase_buf = repo_read_object_file(the_repository,\n+\t\t\t\t\t base, &type,\n+\t\t\t\t\t &base_size);\n+\n+\tif (!base_buf)\n+\t\tdie(\"unable to read %s\", oid_to_hex(base));\n+\n+\tdelta_buf = diff_delta(base_buf, base_size,\n+\t\t\t buf, size, &delta_size, 0);\n+\n+\tcompressed_size = do_compress(&delta_buf, delta_size);\n+\n+\thdrlen = encode_in_pack_object_header(header, sizeof(header),\n+\t\t\t\t\t OBJ_REF_DELTA, delta_size);\n+\thashwrite(f, header, hdrlen);\n+\thashwrite(f, base->hash, the_repository->hash_algo->rawsz);\n+\thashwrite(f, delta_buf, compressed_size);\n+\n+\tfree(buf);\n+\tfree(base_buf);\n+\tfree(delta_buf);\n+}\n+\n+int cmd__pack_deltas(int argc, const char **argv)\n+{\n+\tint N;\n+\tstruct hashfile *f;\n+\tstruct strbuf line = STRBUF_INIT;\n+\n+\tif (argc != 2) {\n+\t\tusage(usage_str);\n+\t\treturn -1;\n+\t}\n+\n+\tN = atoi(argv[1]);\n+\n+\tsetup_git_directory();\n+\n+\tf = hashfd(the_repository->hash_algo, 1, \"\");\n+\twrite_pack_header(f, N);\n+\n+\t/* Read each line from stdin into 'line' */\n+\twhile (strbuf_getline_lf(&line, stdin) != EOF) {\n+\t\tconst char *type_str, *content_oid_str, *base_oid_str = NULL;\n+\t\tstruct object_id content_oid, base_oid;\n+\t\tstruct string_list items = STRING_LIST_INIT_NODUP;\n+\t\t/*\n+\t\t * Tokenize into two or three parts:\n+\t\t * 1. REF_DELTA, OFS_DELTA, or FULL.\n+\t\t * 2. The object ID for the content object.\n+\t\t * 3. The object ID for the base object (optional).\n+\t\t */\n+\t\tif (string_list_split_in_place(&items, line.buf, \" \", 3) < 0)\n+\t\t\tdie(\"invalid input format: %s\", line.buf);\n+\n+\t\tif (items.nr < 2)\n+\t\t\tdie(\"invalid input format: %s\", line.buf);\n+\n+\t\ttype_str = items.items[0].string;\n+\t\tcontent_oid_str = items.items[1].string;\n+\n+\t\tif (get_oid_hex(content_oid_str, &content_oid))\n+\t\t\tdie(\"invalid object: %s\", content_oid_str);\n+\t\tif (items.nr >= 3) {\n+\t\t\tbase_oid_str = items.items[2].string;\n+\t\t\tif (get_oid_hex(base_oid_str, &base_oid))\n+\t\t\t\tdie(\"invalid object: %s\", base_oid_str);\n+\t\t}\n+\n+\t\tif (!strcmp(type_str, \"REF_DELTA\"))\n+\t\t\twrite_ref_delta(f, &content_oid, &base_oid);\n+\t\telse if (!strcmp(type_str, \"OFS_DELTA\"))\n+\t\t\tdie(\"OFS_DELTA not implemented\");\n+\t\telse if (!strcmp(type_str, \"FULL\"))\n+\t\t\tdie(\"FULL not implemented\");\n+\t\telse\n+\t\t\tdie(\"unknown pack type: %s\", type_str);\n+\t}\n+\n+\tfinalize_hashfile(f, NULL, FSYNC_COMPONENT_PACK,\n+\t\t\t CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);\n+\tstrbuf_release(&line);\n+\treturn 0;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex 50dc4dac4ed..74812ed86d3 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -46,6 +46,7 @@ static struct test_cmd cmds[] = {\n \t{ \"mktemp\", cmd__mktemp },\n \t{ \"name-hash\", cmd__name_hash },\n \t{ \"online-cpus\", cmd__online_cpus },\n+\t{ \"pack-deltas\", cmd__pack_deltas },\n \t{ \"pack-mtimes\", cmd__pack_mtimes },\n \t{ \"parse-options\", cmd__parse_options },\n \t{ \"parse-options-flags\", cmd__parse_options_flags },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex 6d62a5b53d9..2571a3ccfe8 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -39,6 +39,7 @@ int cmd__mergesort(int argc, const char **argv);\n int cmd__mktemp(int argc, const char **argv);\n int cmd__name_hash(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\n+int cmd__pack_deltas(int argc, const char **argv);\n int cmd__pack_mtimes(int argc, const char **argv);\n int cmd__parse_options(int argc, const char **argv);\n int cmd__parse_options_flags(int argc, const char **argv);\n-- \ngitgitgadget\n\n"},{"id":"516619","messageId":"a9430447641ff3b3f519abc0960b6741fd7df700.1745430004.git.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":"pull.1906.git.1745430004.gitgitgadget@gmail.com","subject":"[PATCH 2/3] t5309: create failing test for 'git index-pack'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-23T17:40:03Z","receivedAt":"2025-04-23T17:40:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis new test demonstrates some behavior where a valid packfile is being\nrejected by the Git client due to the order in which it is resolving\nREF_DELTAs.\n\nThe thin packfile has a REF_DELTA chain A->B->C where C is not included\nin the packfile. However, the client repository contains both C and B\nalready. Thus, 'git index-pack' is able to resolve A before resolving B.\n\nWhen resolving B, it then attempts to resolve any other REF_DELTAs that\nare pointing to B as a base. This \"revisits\" A and complains as if there\nis a cycle, but it did not actually detect a cycle.\n\nA fix will arrive in the next change.\n\nSigned-off-by: Derrick Stolee \n---\n t/t5309-pack-delta-cycles.sh | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 60fc710bacb..9029f8a0dda 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -75,4 +75,30 @@ test_expect_success 'failover to a duplicate object in the same pack' '\n \ttest_must_fail git index-pack --fix-thin --stdin B->C with B on disk' '\n+\tgit init server &&\n+\t(\n+\t\tcd server &&\n+\t\ttest_commit_bulk 4\n+\t) &&\n+\n+\tA=$(git -C server rev-parse HEAD^{tree}) &&\n+\tB=$(git -C server rev-parse HEAD~1^{tree}) &&\n+\tC=$(git -C server rev-parse HEAD~2^{tree}) &&\n+\tgit -C server reset --hard HEAD~1 &&\n+\n+\tcat >in <<-EOF &&\n+\tREF_DELTA $A $B\n+\tREF_DELTA $B $C\n+\tEOF\n+\n+\ttest-tool -C server pack-deltas 2 thin.pack &&\n+\n+\tgit clone \"file://$(pwd)/server\" client &&\n+\t(\n+\t\tcd client &&\n+\t\tgit index-pack --fix-thin --stdin <../thin.pack\n+\t)\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"516620","messageId":"27d36402fe9c8262c459d606bf4aace1919aa2ae.1745430004.git.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":"pull.1906.git.1745430004.gitgitgadget@gmail.com","subject":"[PATCH 3/3] index-pack: allow revisiting REF_DELTA chains","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-23T17:40:04Z","receivedAt":"2025-04-23T17:40:10Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAs detailed in the previous changes to t5309-pack-delta-cycles.sh, the\nlogic within 'git index-pack' to analyze an incoming thin packfile with\nREF_DELTAs is suspect. The algorithm is overly cautious around delta\ncycles, and that leads in fact to failing even when there is no cycle.\n\nThis change adjusts the algorithm to no longer fail in these cases. In\nfact, these cycle cases will no longer fail but more importantly the\nvalid cases will no longer fail, either. The resulting packfile from the\n--fix-thin operation will not have cycles either since REF_DELTAs are\nforbidden from the on-disk format and OFS_DELTAs are impossible to write\nas a cycle.\n\nThe crux of the matter is how the algorithm works when the REF_DELTAs\npoint to base objects that exist in the local repository. When reading\nthe thin packfile, the object IDs for the delta objects are unknown so\nwe do not have the delta chain structure automatically. Instead, we need\nto start somewhere by selecting a delta whose base is inside our current\nobject database.\n\nConsider the case where the packfile has two REF_DELTA objects, A and B,\nand the delta chain looks like \"A depends on B\" and \"B depends on C\" for\nsome third object C, where C is already in the current repository. The\nalgorithm _should_ start with all objects that depend on C, finding B,\nand then moving on to all objects depending on B, finding A.\n\nHowever, if the repository also already has object B, then the delta\nchain can be analyzed in a different order. The deltas with base B can\nbe analyzed first, finding A, and then the deltas with base C are\nanalyzed, finding B. The algorithm currently continues to look for\nobjects that depend on B, finding A again. This fails due to A's\n'real_type' member already being overwritten from OBJ_REF_DELTA to the\ncorrect object type.\n\nThis scenario is possible in a typical 'git fetch' where the client does\nnot advertise B as a 'have' but requests A as a 'want' (and C is noticed\nas a common object based on other 'have's). The reason this isn't\ntypically seen is that most Git servers use OFS_DELTAs to represent\ndeltas within a packfile. However, if a server uses only REF_DELTAs,\nthen this kind of issue can occur. There is nothing in the explicit\npackfile format that states this use of inter-pack REF_DELTA is\nincorrect, only that REF_DELTAs should not be used in the on-disk\nrepresentation to avoid cycles.\n\nThis die() was introduced in ab791dd138 (index-pack: fix race condition\nwith duplicate bases, 2014-08-29). Several refactors have adjusted the\nerror message and the surrounding logic, but this issue has existed for\na longer time as that was only a conversion from an assert().\n\nThe tests in t5309 originated in 3b910d0c5e (add tests for indexing\npacks with delta cycles, 2013-08-23) and b2ef3d9ebb (test index-pack on\npacks with recoverable delta cycles, 2013-08-23). These changes make\nnote that the current behavior of handling \"resolvable\" cycles is mostly\na documentation-only test, not that this behavior is the best way for\nGit to handle the situation.\n\nThe fix here is somewhat complicated due to the amount of state being\nadjusted by the loop within threaded_second_pass(). Instead of trying to\nresume the start of the loop while adjusting the necessary context, I\nchose to scan the REF_DELTAs depending on the current 'parent' and skip\nany that have already been processed. This necessarily leaves us in a\nstate where 'child' and 'child_obj' could be left as NULL and that must\nbe handled later. There is also some careful handling around skipping\nREF_DELTAs when there are also OFS_DELTAs depending on that parent.\nThere may be value in extending 'test-tool pack-deltas' to allow writing\nOFS_DELTAs in order to exercise this logic across the delta types.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/index-pack.c | 58 ++++++++++++++++++++----------------\n t/t5309-pack-delta-cycles.sh | 12 ++++++--\n 2 files changed, 41 insertions(+), 29 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex de127c0ff13..dbe79701fb8 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1109,8 +1109,8 @@ static void *threaded_second_pass(void *data)\n \t\tset_thread_data(data);\n \tfor (;;) {\n \t\tstruct base_data *parent = NULL;\n-\t\tstruct object_entry *child_obj;\n-\t\tstruct base_data *child;\n+\t\tstruct object_entry *child_obj = NULL;\n+\t\tstruct base_data *child = NULL;\n \n \t\tcounter_lock();\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n@@ -1137,15 +1137,18 @@ static void *threaded_second_pass(void *data)\n \t\t\tparent = list_first_entry(&work_head, struct base_data,\n \t\t\t\t\t\t list);\n \n-\t\t\tif (parent->ref_first <= parent->ref_last) {\n+\t\t\twhile (parent->ref_first <= parent->ref_last) {\n \t\t\t\tint offset = ref_deltas[parent->ref_first++].obj_no;\n \t\t\t\tchild_obj = objects + offset;\n-\t\t\t\tif (child_obj->real_type != OBJ_REF_DELTA)\n-\t\t\t\t\tdie(\"REF_DELTA at offset %\"PRIuMAX\" already resolved (duplicate base %s?)\",\n-\t\t\t\t\t (uintmax_t) child_obj->idx.offset,\n-\t\t\t\t\t oid_to_hex(&parent->obj->idx.oid));\n+\t\t\t\tif (child_obj->real_type != OBJ_REF_DELTA) {\n+\t\t\t\t\tchild_obj = NULL;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n \t\t\t\tchild_obj->real_type = parent->obj->real_type;\n-\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n+\t\t\tif (!child_obj && parent->ofs_first <= parent->ofs_last) {\n \t\t\t\tchild_obj = objects +\n \t\t\t\t\tofs_deltas[parent->ofs_first++].obj_no;\n \t\t\t\tassert(child_obj->real_type == OBJ_OFS_DELTA);\n@@ -1178,29 +1181,32 @@ static void *threaded_second_pass(void *data)\n \t\t}\n \t\twork_unlock();\n \n-\t\tif (parent) {\n-\t\t\tchild = resolve_delta(child_obj, parent);\n-\t\t\tif (!child->children_remaining)\n-\t\t\t\tFREE_AND_NULL(child->data);\n-\t\t} else {\n-\t\t\tchild = make_base(child_obj, NULL);\n-\t\t\tif (child->children_remaining) {\n-\t\t\t\t/*\n-\t\t\t\t * Since this child has its own delta children,\n-\t\t\t\t * we will need this data in the future.\n-\t\t\t\t * Inflate now so that future iterations will\n-\t\t\t\t * have access to this object's data while\n-\t\t\t\t * outside the work mutex.\n-\t\t\t\t */\n-\t\t\t\tchild->data = get_data_from_pack(child_obj);\n-\t\t\t\tchild->size = child_obj->size;\n+\t\tif (child_obj) {\n+\t\t\tif (parent) {\n+\t\t\t\tchild = resolve_delta(child_obj, parent);\n+\t\t\t\tif (!child->children_remaining)\n+\t\t\t\t\tFREE_AND_NULL(child->data);\n+\t\t\t} else{\n+\t\t\t\tchild = make_base(child_obj, NULL);\n+\t\t\t\tif (child->children_remaining) {\n+\t\t\t\t\t/*\n+\t\t\t\t\t * Since this child has its own delta children,\n+\t\t\t\t\t * we will need this data in the future.\n+\t\t\t\t\t * Inflate now so that future iterations will\n+\t\t\t\t\t * have access to this object's data while\n+\t\t\t\t\t * outside the work mutex.\n+\t\t\t\t\t */\n+\t\t\t\t\tchild->data = get_data_from_pack(child_obj);\n+\t\t\t\t\tchild->size = child_obj->size;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \n \t\twork_lock();\n \t\tif (parent)\n \t\t\tparent->retain_data--;\n-\t\tif (child->data) {\n+\n+\t\tif (child && child->data) {\n \t\t\t/*\n \t\t\t * This child has its own children, so add it to\n \t\t\t * work_head.\n@@ -1209,7 +1215,7 @@ static void *threaded_second_pass(void *data)\n \t\t\tbase_cache_used += child->size;\n \t\t\tprune_base_data(NULL);\n \t\t\tfree_base_data(child);\n-\t\t} else {\n+\t\t} else if (child) {\n \t\t\t/*\n \t\t\t * This child does not have its own children. It may be\n \t\t\t * the last descendant of its ancestors; free those\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 9029f8a0dda..fc3594aaae9 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -60,7 +60,10 @@ test_expect_success 'index-pack detects REF_DELTA cycles' '\n test_expect_success 'failover to an object in another pack' '\n \tclear_packs &&\n \tgit index-pack --stdin recoverable.pack &&\n \tpack_trailer recoverable.pack &&\n-\ttest_must_fail git index-pack --fix-thin --stdin B->C with B on disk' '\n+test_expect_success 'index-pack works with thin pack A->B->C with B on disk' '\n \tgit init server &&\n \t(\n \t\tcd server &&\n-- \ngitgitgadget\n"},{"id":"516631","messageId":"xmqqmsc6y911.fsf@gitster.g","threadId":"63337","inReplyTo":"5d4beb202d6ed842de72928462a10a4f5faa2718.1745430004.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-23T19:26:02Z","receivedAt":"2025-04-23T19:26:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n>\n> When trying to demonstrate certain behavior in tests, it can be helpful\n> to create packfiles that have specific delta structures. 'git\n> pack-objects' uses various algorithms to select deltas based on their\n> compression rates, but that does not always demonstrate all possible\n> packfile shapes. This becomes especially important when wanting to test\n> 'git index-pack' and its ability to parse certain pack shapes.\n>\n> We have prior art in t/lib-pack.sh, where certain delta structures are\n> produced by manually writing certain opaque pack contents. However,\n> producing these script updates is cumbersome and difficult to do as a\n> contributor.\n>\n> Instead, create a new test-tool, 'test-tool pack-deltas', that reads a\n> list of instructions for which objects to include in a packfile and how\n> those objects should be written in delta form.\n>\n> At the moment, this only supports REF_DELTAs as those are the kinds of\n> deltas needed to exercise a bug in 'git index-pack'.\n\nWonderful writing. I agree with the destination where this effort\nwants to go, including the decision that starting with ref-delta\nonly is a good enough first step.\n\nAs to the implementation, I was a tiny little bit bummed to see\nthat, even though it does share the code with the real pack-objects\ncode paths to compute delta data by calling diff_delta(), and to\nwrite per-object header by calling encode_in_pack_object_header(),\nit has its own compression loop that does not even do an error\nchecking after calling into zlib deflate machinery.\n\nPerhaps that is unavoidable due to the code structure of the\nproduction code.\n\n> +static const char usage_str[] = \"test-tool pack-deltas \";\n> ...\n> +int cmd__pack_deltas(int argc, const char **argv)\n> +{\n> +\tint N;\n> +\tstruct hashfile *f;\n> +\tstruct strbuf line = STRBUF_INIT;\n> +\n> +\tif (argc != 2) {\n> +\t\tusage(usage_str);\n> +\t\treturn -1;\n> +\t}\n> +\n> +\tN = atoi(argv[1]);\n\nIt somewhat looks strange to see an uppercase N used as a variable\nname. Together with the usage string, how about renaming \"N\" and\n\"n\" after \"number of objects\", e.g.\n\n\ttest-tool pack-deltas \n\tint num_objects;\n\nor something?\n\nOther than that, looking very good.\n\n"},{"id":"516632","messageId":"460cd77b-2b49-4159-bac5-0fd4fb655f84@gmail.com","threadId":"63337","inReplyTo":"xmqqmsc6y911.fsf@gitster.g","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-04-23T19:32:09Z","receivedAt":"2025-04-23T19:32:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/23/2025 3:26 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> From: Derrick Stolee \n>>\n>> When trying to demonstrate certain behavior in tests, it can be helpful\n>> to create packfiles that have specific delta structures. 'git\n>> pack-objects' uses various algorithms to select deltas based on their\n>> compression rates, but that does not always demonstrate all possible\n>> packfile shapes. This becomes especially important when wanting to test\n>> 'git index-pack' and its ability to parse certain pack shapes.\n>>\n>> We have prior art in t/lib-pack.sh, where certain delta structures are\n>> produced by manually writing certain opaque pack contents. However,\n>> producing these script updates is cumbersome and difficult to do as a\n>> contributor.\n>>\n>> Instead, create a new test-tool, 'test-tool pack-deltas', that reads a\n>> list of instructions for which objects to include in a packfile and how\n>> those objects should be written in delta form.\n>>\n>> At the moment, this only supports REF_DELTAs as those are the kinds of\n>> deltas needed to exercise a bug in 'git index-pack'.\n> \n> Wonderful writing. I agree with the destination where this effort\n> wants to go, including the decision that starting with ref-delta\n> only is a good enough first step.\n> \n> As to the implementation, I was a tiny little bit bummed to see\n> that, even though it does share the code with the real pack-objects\n> code paths to compute delta data by calling diff_delta(), and to\n> write per-object header by calling encode_in_pack_object_header(),\n> it has its own compression loop that does not even do an error\n> checking after calling into zlib deflate machinery.\n\nI could strengthen these options to help folks more quickly understand\npotential failures as being part of the pack write instead of them\nfailing during the later pack read.\n\n> Perhaps that is unavoidable due to the code structure of the\n> production code.\n\nI briefly considered extracting some code out of builtin/pack-objects.c\nbut it relies heavily on globals and context that I won't have in this\nhelper. I'm open to suggestions for how I can safely share more code,\nbut my initial attempt required too much refactoring to be worth it.\n\nI am grateful for the amount of code from pack-write.c that I _was_\nable to reuse.\n\n>> +static const char usage_str[] = \"test-tool pack-deltas \";\n>> ...\n>> +int cmd__pack_deltas(int argc, const char **argv)\n>> +{\n>> +\tint N;\n>> +\tstruct hashfile *f;\n>> +\tstruct strbuf line = STRBUF_INIT;\n>> +\n>> +\tif (argc != 2) {\n>> +\t\tusage(usage_str);\n>> +\t\treturn -1;\n>> +\t}\n>> +\n>> +\tN = atoi(argv[1]);\n> \n> It somewhat looks strange to see an uppercase N used as a variable\n> name. Together with the usage string, how about renaming \"N\" and\n> \"n\" after \"number of objects\", e.g.\n> \n> \ttest-tool pack-deltas \n> \tint num_objects;\n> \n> or something?\n\nI definitely should have used a better name here. Thanks.\n\n-Stolee\n\n"},{"id":"516633","messageId":"xmqqfrhyy8ia.fsf@gitster.g","threadId":"63337","inReplyTo":"a9430447641ff3b3f519abc0960b6741fd7df700.1745430004.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/3] t5309: create failing test for 'git index-pack'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-23T19:37:17Z","receivedAt":"2025-04-23T19:37:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n>\n> This new test demonstrates some behavior where a valid packfile is being\n> rejected by the Git client due to the order in which it is resolving\n> REF_DELTAs.\n>\n> The thin packfile has a REF_DELTA chain A->B->C where C is not included\n> in the packfile. However, the client repository contains both C and B\n> already. Thus, 'git index-pack' is able to resolve A before resolving B.\n\nIn order to reconstitute A, B is needed (which recipient has), and\nin order to reconstitute B, C is needed (which recipient also has).\n\nThe index-pack sees delta based on B to recreate A; it should be\nable to reconstitute A using B that already exists.\n\nOK.\n\n> When resolving B, it then attempts to resolve any other REF_DELTAs that\n> are pointing to B as a base. This \"revisits\" A and complains as if there\n> is a cycle, but it did not actually detect a cycle.\n\nThat's interesting.\n\n> +test_expect_failure 'index-pack works with thin pack A->B->C with B on disk' '\n> +\tgit init server &&\n> +\t(\n> +\t\tcd server &&\n> +\t\ttest_commit_bulk 4\n> +\t) &&\n> +\n> +\tA=$(git -C server rev-parse HEAD^{tree}) &&\n> +\tB=$(git -C server rev-parse HEAD~1^{tree}) &&\n> +\tC=$(git -C server rev-parse HEAD~2^{tree}) &&\n> +\tgit -C server reset --hard HEAD~1 &&\n> +\n> +\tcat >in <<-EOF &&\n> +\tREF_DELTA $A $B\n> +\tREF_DELTA $B $C\n> +\tEOF\n> +\n> +\ttest-tool -C server pack-deltas 2 thin.pack &&\n\nThis is minor, but I somehow find it easier to follow without the\ntemporary file, i.e.\n\n\ttest-tool -C server pack-deltas 2 >thin.pack <<-EOF &&\n\tREF_DELTA $A $B\n\tREF_DELTA $B $C\n\tEOF\n\n> +\tgit clone \"file://$(pwd)/server\" client &&\n\nThis truly loses A from the resulting \"client\" repository, but the\nhistory still can reach B and C.\n\n> +\t(\n> +\t\tcd client &&\n> +\t\tgit index-pack --fix-thin --stdin <../thin.pack\n> +\t)\n> +'\n\nMakes sense.\n"},{"id":"516685","messageId":"xmqq34dxuz21.fsf@gitster.g","threadId":"63337","inReplyTo":"5d4beb202d6ed842de72928462a10a4f5faa2718.1745430004.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-24T19:41:58Z","receivedAt":"2025-04-24T19:42:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I needed this to make\n\n$ SANITIZE=leak GIT_TEST_PASSING_SANITIZE_LEAK=true make\n$ cd t && sh t5309-pack-delta-cycles.sh\n\npass.\n--- >8 ------ >8 ------ >8 ---\nSubject: [PATCH] fixup! test-tool: add pack-deltas helper\n\n t/helper/test-pack-deltas.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\nindex db7d1c3cd1..c8e837ea06 100644\n--- a/t/helper/test-pack-deltas.c\n+++ b/t/helper/test-pack-deltas.c\n@@ -122,6 +122,7 @@ int cmd__pack_deltas(int argc, const char **argv)\n \t\t\tif (get_oid_hex(base_oid_str, &base_oid))\n \t\t\t\tdie(\"invalid object: %s\", base_oid_str);\n \t\t}\n+\t\tstring_list_clear(&items, 0);\n \n \t\tif (!strcmp(type_str, \"REF_DELTA\"))\n \t\t\twrite_ref_delta(f, &content_oid, &base_oid);\n-- \n2.49.0-555-g43235db9c8\n\n"},{"id":"516686","messageId":"9999f7f2-759a-4721-a4d0-6d3bdeb17b25@gmail.com","threadId":"63337","inReplyTo":"xmqq34dxuz21.fsf@gitster.g","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-04-24T20:06:58Z","receivedAt":"2025-04-24T20:07:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/24/2025 3:41 PM, Junio C Hamano wrote:\n> I needed this to make\n> \n> $ SANITIZE=leak GIT_TEST_PASSING_SANITIZE_LEAK=true make\n> $ cd t && sh t5309-pack-delta-cycles.sh\n> \n> pass.\n> --- >8 ------ >8 ------ >8 ---\n> Subject: [PATCH] fixup! test-tool: add pack-deltas helper\n> \n> t/helper/test-pack-deltas.c | 1 +\n> 1 file changed, 1 insertion(+)\n> \n> diff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\n> index db7d1c3cd1..c8e837ea06 100644\n> --- a/t/helper/test-pack-deltas.c\n> +++ b/t/helper/test-pack-deltas.c\n> @@ -122,6 +122,7 @@ int cmd__pack_deltas(int argc, const char **argv)\n> \t\t\tif (get_oid_hex(base_oid_str, &base_oid))\n> \t\t\t\tdie(\"invalid object: %s\", base_oid_str);\n> \t\t}\n> +\t\tstring_list_clear(&items, 0);\n\nThanks. I'll make sure to apply it. My GGG PR validation was broken\ntop-to-bottom due to other environmental issues so I had not seen\nthis failure myself.\n\nThanks,\n-Stolee\n\n"},{"id":"516689","messageId":"xmqqy0vpth1i.fsf@gitster.g","threadId":"63337","inReplyTo":"9999f7f2-759a-4721-a4d0-6d3bdeb17b25@gmail.com","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-24T20:56:25Z","receivedAt":"2025-04-24T20:56:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 4/24/2025 3:41 PM, Junio C Hamano wrote:\n>> I needed this to make\n>> \n>> $ SANITIZE=leak GIT_TEST_PASSING_SANITIZE_LEAK=true make\n>> $ cd t && sh t5309-pack-delta-cycles.sh\n>> \n>> pass.\n>> --- >8 ------ >8 ------ >8 ---\n>> Subject: [PATCH] fixup! test-tool: add pack-deltas helper\n>> \n>> t/helper/test-pack-deltas.c | 1 +\n>> 1 file changed, 1 insertion(+)\n>> \n>> diff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\n>> index db7d1c3cd1..c8e837ea06 100644\n>> --- a/t/helper/test-pack-deltas.c\n>> +++ b/t/helper/test-pack-deltas.c\n>> @@ -122,6 +122,7 @@ int cmd__pack_deltas(int argc, const char **argv)\n>> \t\t\tif (get_oid_hex(base_oid_str, &base_oid))\n>> \t\t\t\tdie(\"invalid object: %s\", base_oid_str);\n>> \t\t}\n>> +\t\tstring_list_clear(&items, 0);\n>\n> Thanks. I'll make sure to apply it. My GGG PR validation was broken\n> top-to-bottom due to other environmental issues so I had not seen\n> this failure myself.\n\nI squashed this in so unless there are other things you need to\nchange, this alone does not make it necessary to reroll the series.\n\nThanks.\n"},{"id":"516692","messageId":"xmqqjz79texy.fsf@gitster.g","threadId":"63337","inReplyTo":"27d36402fe9c8262c459d606bf4aace1919aa2ae.1745430004.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/3] index-pack: allow revisiting REF_DELTA chains","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-24T21:41:45Z","receivedAt":"2025-04-24T21:41:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n>\n> As detailed in the previous changes to t5309-pack-delta-cycles.sh, the\n> logic within 'git index-pack' to analyze an incoming thin packfile with\n> REF_DELTAs is suspect. The algorithm is overly cautious around delta\n> cycles, and that leads in fact to failing even when there is no cycle.\n>\n> This change adjusts the algorithm to no longer fail in these cases. In\n> fact, these cycle cases will no longer fail but more importantly the\n> valid cases will no longer fail, either. The resulting packfile from the\n> --fix-thin operation will not have cycles either since REF_DELTAs are\n> forbidden from the on-disk format and OFS_DELTAs are impossible to write\n> as a cycle.\n\nLoosening cycle avoidance indeed is worrysome. How do we guarantee\n\"since REF_DELTAs are forbidden from the on-disk format\" (it is\nobvious with OFS_DELTA only you cannot form a cycle)? By code\ninspection and in-code comment for the code path of \"--fix-thin\"?\n\nI think the most interesting question would be how, with the\nloosening of the cycle check in this patch, we would still protect\nagainst a malicious on-the-wire packdata that has a cycle in it\nalready, where deltas cannot be resolved.\n"},{"id":"516713","messageId":"d7313975-24a7-48eb-9626-66a3e53d4234@gmail.com","threadId":"63337","inReplyTo":"xmqqjz79texy.fsf@gitster.g","subject":"Re: [PATCH 3/3] index-pack: allow revisiting REF_DELTA chains","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-04-25T03:49:35Z","receivedAt":"2025-04-25T03:49:37Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/24/2025 5:41 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> From: Derrick Stolee \n>>\n>> As detailed in the previous changes to t5309-pack-delta-cycles.sh, the\n>> logic within 'git index-pack' to analyze an incoming thin packfile with\n>> REF_DELTAs is suspect. The algorithm is overly cautious around delta\n>> cycles, and that leads in fact to failing even when there is no cycle.\n>>\n>> This change adjusts the algorithm to no longer fail in these cases. In\n>> fact, these cycle cases will no longer fail but more importantly the\n>> valid cases will no longer fail, either. The resulting packfile from the\n>> --fix-thin operation will not have cycles either since REF_DELTAs are\n>> forbidden from the on-disk format and OFS_DELTAs are impossible to write\n>> as a cycle.\n> \n> Loosening cycle avoidance indeed is worrysome. How do we guarantee\n> \"since REF_DELTAs are forbidden from the on-disk format\" (it is\n> obvious with OFS_DELTA only you cannot form a cycle)? By code\n> inspection and in-code comment for the code path of \"--fix-thin\"?\n> \n> I think the most interesting question would be how, with the\n> loosening of the cycle check in this patch, we would still protect\n> against a malicious on-the-wire packdata that has a cycle in it\n> already, where deltas cannot be resolved.\n\nThe good news is two-fold:\n\n1. We have a test in t5309 (index-pack detects REF_DELTA cycles) that\n checks this case and did not change behavior with this patch.\n\n2. If we don't already have any of the objects that exist in the cycle,\n then we can't _start_ expanding the objects to their full contents\n as we don't have their bases. So what is left is a list of REF_DELTAs\n that have not been processed but also a list of base object IDs that\n we can't load. We'll fail without writing those objects to disk.\n\nDoes that satisfy your concerns in this space?\n\nThanks,\n-Stolee\n\n"},{"id":"516715","messageId":"aAsQwSfr-YvS2Mvh@pks.im","threadId":"63337","inReplyTo":"5d4beb202d6ed842de72928462a10a4f5faa2718.1745430004.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-04-25T04:34:09Z","receivedAt":"2025-04-25T04:34:18Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Apr 23, 2025 at 05:40:02PM +0000, Derrick Stolee via GitGitGadget wrote:\n> diff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\n> new file mode 100644\n> index 00000000000..db7d1c3cd1f\n> --- /dev/null\n> +++ b/t/helper/test-pack-deltas.c\n> @@ -0,0 +1,140 @@\n[snip]\n> +int cmd__pack_deltas(int argc, const char **argv)\n> +{\n> +\tint N;\n> +\tstruct hashfile *f;\n> +\tstruct strbuf line = STRBUF_INIT;\n> +\n> +\tif (argc != 2) {\n> +\t\tusage(usage_str);\n> +\t\treturn -1;\n> +\t}\n> +\n> +\tN = atoi(argv[1]);\n\nIs there a reason why we don't use `parse_options()` here? It might make\nthis tool easier to use and extend going forward, and we wouldn't have\nto care about invalid arguments. Right now, we silently accept a\nnon-integer argument and do the wrong thing.\n\nPatrick\n"},{"id":"516776","messageId":"090ef16f-42a7-8de6-a79e-5a1958e2c103@gmx.de","threadId":"63337","inReplyTo":"aAsQwSfr-YvS2Mvh@pks.im","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2025-04-25T09:34:01Z","receivedAt":"2025-04-25T09:34:10Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Patrick,\n\nOn Fri, 25 Apr 2025, Patrick Steinhardt wrote:\n\n> On Wed, Apr 23, 2025 at 05:40:02PM +0000, Derrick Stolee via GitGitGadget wrote:\n> > diff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\n> > new file mode 100644\n> > index 00000000000..db7d1c3cd1f\n> > --- /dev/null\n> > +++ b/t/helper/test-pack-deltas.c\n> > @@ -0,0 +1,140 @@\n> [snip]\n> > +int cmd__pack_deltas(int argc, const char **argv)\n> > +{\n> > +\tint N;\n> > +\tstruct hashfile *f;\n> > +\tstruct strbuf line = STRBUF_INIT;\n> > +\n> > +\tif (argc != 2) {\n> > +\t\tusage(usage_str);\n> > +\t\treturn -1;\n> > +\t}\n> > +\n> > +\tN = atoi(argv[1]);\n> \n> Is there a reason why we don't use `parse_options()` here? It might make\n> this tool easier to use and extend going forward, and we wouldn't have\n> to care about invalid arguments. Right now, we silently accept a\n> non-integer argument and do the wrong thing.\n\nI think that `parse_options()` would be overkill here because:\n\n- This is a _mandatory_ argument, not an optional one.\n\n- The required data type is `uint32_t`, and `parse_options()` has no\n support for that.\n\nBut you do have a good point in that we may want to validate the data type\n(even if technically, this is not a user-facing program, it's a test\nhelper that is used under tight control by Git's own test suite).\n\nConsequently, I would suggest this fixup instead:\n\n-- snipsnap --\nSubject: [PATCH] fixup! test-tool: add pack-deltas helper\n\nLet's make the command-line parsing a bit more stringent. We _could_\nuse `parse_options()`, but that would be overkill for a single,\nnon-optional argument. Besides, it would not bring any benefit, as the\nparsed value needs to fit in the `uint32_t` type, and `parse_options()`\nhas no provision to ensure that.\n\nSigned-off-by: Johannes Schindelin \n---\n t/helper/test-pack-deltas.c | 10 ++++++----\n 1 file changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\nindex 4af69bdc05d3..f95d8ee16768 100644\n--- a/t/helper/test-pack-deltas.c\n+++ b/t/helper/test-pack-deltas.c\n@@ -8,11 +8,12 @@\n #include \"hex.h\"\n #include \"pack.h\"\n #include \"pack-objects.h\"\n+#include \"parse.h\"\n #include \"setup.h\"\n #include \"strbuf.h\"\n #include \"string-list.h\"\n \n-static const char usage_str[] = \"test-tool pack-deltas \";\n+static const char usage_str[] = \"test-tool pack-deltas \";\n \n static unsigned long do_compress(void **pptr, unsigned long size)\n {\n@@ -79,7 +80,7 @@ static void write_ref_delta(struct hashfile *f,\n \n int cmd__pack_deltas(int argc, const char **argv)\n {\n-\tint N;\n+\tunsigned long n;\n \tstruct hashfile *f;\n \tstruct strbuf line = STRBUF_INIT;\n \n@@ -88,12 +89,13 @@ int cmd__pack_deltas(int argc, const char **argv)\n \t\treturn -1;\n \t}\n \n-\tN = atoi(argv[1]);\n+\tif (!git_parse_ulong(argv[1], &n) || n != (uint32_t)n)\n+\t\tdie(\"invalid number of objects: %s\", argv[1]);\n \n \tsetup_git_directory();\n \n \tf = hashfd(1, \"\");\n-\twrite_pack_header(f, N);\n+\twrite_pack_header(f, n);\n \n \t/* Read each line from stdin into 'line' */\n \twhile (strbuf_getline_lf(&line, stdin) != EOF) {\n-- \n2.49.0.windows.1\n\n"},{"id":"516777","messageId":"aAtZuU6Qqfag6OHj@pks.im","threadId":"63337","inReplyTo":"090ef16f-42a7-8de6-a79e-5a1958e2c103@gmx.de","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-04-25T09:45:29Z","receivedAt":"2025-04-25T09:45:36Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Apr 25, 2025 at 11:34:01AM +0200, Johannes Schindelin wrote:\n> Hi Patrick,\n> \n> On Fri, 25 Apr 2025, Patrick Steinhardt wrote:\n> \n> > On Wed, Apr 23, 2025 at 05:40:02PM +0000, Derrick Stolee via GitGitGadget wrote:\n> > > diff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\n> > > new file mode 100644\n> > > index 00000000000..db7d1c3cd1f\n> > > --- /dev/null\n> > > +++ b/t/helper/test-pack-deltas.c\n> > > @@ -0,0 +1,140 @@\n> > [snip]\n> > > +int cmd__pack_deltas(int argc, const char **argv)\n> > > +{\n> > > +\tint N;\n> > > +\tstruct hashfile *f;\n> > > +\tstruct strbuf line = STRBUF_INIT;\n> > > +\n> > > +\tif (argc != 2) {\n> > > +\t\tusage(usage_str);\n> > > +\t\treturn -1;\n> > > +\t}\n> > > +\n> > > +\tN = atoi(argv[1]);\n> > \n> > Is there a reason why we don't use `parse_options()` here? It might make\n> > this tool easier to use and extend going forward, and we wouldn't have\n> > to care about invalid arguments. Right now, we silently accept a\n> > non-integer argument and do the wrong thing.\n> \n> I think that `parse_options()` would be overkill here because:\n> \n> - This is a _mandatory_ argument, not an optional one.\n> \n> - The required data type is `uint32_t`, and `parse_options()` has no\n> support for that.\n\nSupport for that has been merged just this week via 2bc5414c411 (Merge\nbranch 'ps/parse-options-integers', 2025-04-24).\n\n> But you do have a good point in that we may want to validate the data type\n> (even if technically, this is not a user-facing program, it's a test\n> helper that is used under tight control by Git's own test suite).\n> \n> Consequently, I would suggest this fixup instead:\n\nBut in any case, I'd be equally fine with your suggestion.\n\nPatrick\n"},{"id":"516780","messageId":"118698a1-33f8-36b5-c7c6-ed44b9e30d5d@gmx.de","threadId":"63337","inReplyTo":"aAtZuU6Qqfag6OHj@pks.im","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2025-04-25T09:51:52Z","receivedAt":"2025-04-25T09:52:04Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Patrick,\n\nOn Fri, 25 Apr 2025, Patrick Steinhardt wrote:\n\n> On Fri, Apr 25, 2025 at 11:34:01AM +0200, Johannes Schindelin wrote:\n> > \n> > On Fri, 25 Apr 2025, Patrick Steinhardt wrote:\n> > \n> > > On Wed, Apr 23, 2025 at 05:40:02PM +0000, Derrick Stolee via GitGitGadget wrote:\n> > > > diff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\n> > > > new file mode 100644\n> > > > index 00000000000..db7d1c3cd1f\n> > > > --- /dev/null\n> > > > +++ b/t/helper/test-pack-deltas.c\n> > > > @@ -0,0 +1,140 @@\n> > > [snip]\n> > > > +int cmd__pack_deltas(int argc, const char **argv)\n> > > > +{\n> > > > +\tint N;\n> > > > +\tstruct hashfile *f;\n> > > > +\tstruct strbuf line = STRBUF_INIT;\n> > > > +\n> > > > +\tif (argc != 2) {\n> > > > +\t\tusage(usage_str);\n> > > > +\t\treturn -1;\n> > > > +\t}\n> > > > +\n> > > > +\tN = atoi(argv[1]);\n> > > \n> > > Is there a reason why we don't use `parse_options()` here? It might make\n> > > this tool easier to use and extend going forward, and we wouldn't have\n> > > to care about invalid arguments. Right now, we silently accept a\n> > > non-integer argument and do the wrong thing.\n> > \n> > I think that `parse_options()` would be overkill here because:\n> > \n> > - This is a _mandatory_ argument, not an optional one.\n> > \n> > - The required data type is `uint32_t`, and `parse_options()` has no\n> > support for that.\n> \n> Support for that has been merged just this week via 2bc5414c411 (Merge\n> branch 'ps/parse-options-integers', 2025-04-24).\n\nThat's too new for me to be useful, as I have to work on top of v2.49.0\n(see https://github.com/microsoft/git/pull/745).\n\n> > But you do have a good point in that we may want to validate the data type\n> > (even if technically, this is not a user-facing program, it's a test\n> > helper that is used under tight control by Git's own test suite).\n> > \n> > Consequently, I would suggest this fixup instead:\n> \n> But in any case, I'd be equally fine with your suggestion.\n\nThanks!\nJohannes\n"},{"id":"516815","messageId":"xmqqbjskurz5.fsf@gitster.g","threadId":"63337","inReplyTo":"aAtZuU6Qqfag6OHj@pks.im","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-25T16:27:10Z","receivedAt":"2025-04-25T16:27:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n>> > Is there a reason why we don't use `parse_options()` here? It might make\n>> > this tool easier to use and extend going forward, and we wouldn't have\n>> > to care about invalid arguments. Right now, we silently accept a\n>> > non-integer argument and do the wrong thing.\n>> \n>> I think that `parse_options()` would be overkill here because:\n>> \n>> - This is a _mandatory_ argument, not an optional one.\n>> \n>> - The required data type is `uint32_t`, and `parse_options()` has no\n>> support for that.\n>\n> Support for that has been merged just this week via 2bc5414c411 (Merge\n> branch 'ps/parse-options-integers', 2025-04-24).\n>\n>> But you do have a good point in that we may want to validate the data type\n>> (even if technically, this is not a user-facing program, it's a test\n>> helper that is used under tight control by Git's own test suite).\n>> \n>> Consequently, I would suggest this fixup instead:\n>\n> But in any case, I'd be equally fine with your suggestion.\n\nYeah, I think we clearly showed our \"it's just test helper, whose\ncallers are supposed to know what they are doing\" attitude, but with\nproper helpers, it is not too much additional effort to do the right\nthing.\n\nThanks, both.\n"},{"id":"516892","messageId":"275808ae-7126-4a24-b5f3-283ea8023f5f@gmail.com","threadId":"63337","inReplyTo":"xmqqbjskurz5.fsf@gitster.g","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-04-28T15:22:13Z","receivedAt":"2025-04-28T15:22:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/25/2025 12:27 PM, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n> \n>>>> Is there a reason why we don't use `parse_options()` here? It might make\n>>>> this tool easier to use and extend going forward, and we wouldn't have\n>>>> to care about invalid arguments. Right now, we silently accept a\n>>>> non-integer argument and do the wrong thing.\n>>>\n>>> I think that `parse_options()` would be overkill here because:\n>>>\n>>> - This is a _mandatory_ argument, not an optional one.\n>>>\n>>> - The required data type is `uint32_t`, and `parse_options()` has no\n>>> support for that.\n>>\n>> Support for that has been merged just this week via 2bc5414c411 (Merge\n>> branch 'ps/parse-options-integers', 2025-04-24).\n\nThe thing that confused me even with those changes is that this is a\n_positional_ argument and we don't have a way to say \"parse the 1st\npositional argument into an integer\".\n\n>>> But you do have a good point in that we may want to validate the data type\n>>> (even if technically, this is not a user-facing program, it's a test\n>>> helper that is used under tight control by Git's own test suite).\n>>>\n>>> Consequently, I would suggest this fixup instead:\n>>\n>> But in any case, I'd be equally fine with your suggestion.\n> \n> Yeah, I think we clearly showed our \"it's just test helper, whose\n> callers are supposed to know what they are doing\" attitude, but with\n> proper helpers, it is not too much additional effort to do the right\n> thing.\n\nBut with this philosophy in mind I can change the CLI to be of the form\n\"--num-objects \" to use the parse-options feature. This should make\nthings more extensible in the future.\n\nThanks,\n-Stolee\n\n"},{"id":"516897","messageId":"xmqqmsc0dyyf.fsf@gitster.g","threadId":"63337","inReplyTo":"275808ae-7126-4a24-b5f3-283ea8023f5f@gmail.com","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-28T16:37:28Z","receivedAt":"2025-04-28T16:37:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> Yeah, I think we clearly showed our \"it's just test helper, whose\n>> callers are supposed to know what they are doing\" attitude, but with\n>> proper helpers, it is not too much additional effort to do the right\n>> thing.\n>\n> But with this philosophy in mind I can change the CLI to be of the form\n> \"--num-objects \" to use the parse-options feature. This should make\n> things more extensible in the future.\n\nTrue. If we are aiming to deliver this to end-user's hands in some\nfuture, I agree that we want to make it extensible, make it dtrt\nwithout being told, and make it harder to give wrong input. If we\nare going in that direction [*], I suspect this should not be a\nseparate and independent input---rather, shouldn't the tool already\n_know_ what objects it placed in the resulting output stream, and\nshould be able to _count_ that number by itself? One thing it lets\nus do to have this as a separate number is to create an invalid pack\nstream where the header gives a wrong number, and as a test tool,\nthat may trump the convenience of not having to give the number\nexplicitly.\n\nAnother thing we may want to add to the tool is to give it a mode\nthat either (1) refuses to place the same object in a single pack\nstream more than once, or (2) warn when it happens. The latter\nwould be useful to create an invalid pack stream for testing.\n\nThanks.\n\n\n[Footnote]\n\n* ... which I would welcome as the project manager, even though\n personally I find that 'it is just test helper' attitude\n attractive. Not everybody in this project is experienced enough\n to understand the 'it is just test helper, let's not spend too\n much effort on it' attitude and elements in the code there should\n not be blindly copied and pasted to production part of the system.\n"},{"id":"516905","messageId":"6df25bf2-6df1-4c3a-9061-e3297dec38ab@gmail.com","threadId":"63337","inReplyTo":"xmqqmsc0dyyf.fsf@gitster.g","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-04-28T18:59:22Z","receivedAt":"2025-04-28T18:59:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/28/2025 12:37 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n> \n>>> Yeah, I think we clearly showed our \"it's just test helper, whose\n>>> callers are supposed to know what they are doing\" attitude, but with\n>>> proper helpers, it is not too much additional effort to do the right\n>>> thing.\n>>\n>> But with this philosophy in mind I can change the CLI to be of the form\n>> \"--num-objects \" to use the parse-options feature. This should make\n>> things more extensible in the future.\n> \n> True. If we are aiming to deliver this to end-user's hands in some\n> future, I agree that we want to make it extensible, make it dtrt\n> without being told, and make it harder to give wrong input. \n\nI'm not focused on usability, but instead on faster development cycles\nif more advanced options are required in the future. I'll happily take\nsome extra time now to help those who come after.\n\n> If we\n> are going in that direction [*], I suspect this should not be a\n> separate and independent input---rather, shouldn't the tool already\n> _know_ what objects it placed in the resulting output stream, and\n> should be able to _count_ that number by itself? \n\nThis makes sense as a feature, except that we need to write the number\nof objects present in a packfile in its header. If we wanted to avoid\nthe argument, then we'd need to load the data into a list before\nstarting to write the packfile. By taking the count in advance, the\nimplementation is simpler.\n\n> One thing it lets\n> us do to have this as a separate number is to create an invalid pack\n> stream where the header gives a wrong number, and as a test tool,\n> that may trump the convenience of not having to give the number\n> explicitly.\nBut also, this allows generating bad packfiles which is a bonus.\nA very good point. \n> Another thing we may want to add to the tool is to give it a mode\n> that either (1) refuses to place the same object in a single pack\n> stream more than once, or (2) warn when it happens. The latter\n> would be useful to create an invalid pack stream for testing.\n\nNoted for potential future expansion.\n\nThanks,\n-Stolee\n\n"},{"id":"516912","messageId":"pull.1906.v2.git.1745871885.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":"pull.1906.git.1745430004.gitgitgadget@gmail.com","subject":"[PATCH v2 0/3] Fix REF_DELTA chain bug in 'git index-pack'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-28T20:24:42Z","receivedAt":"2025-04-28T20:24:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"When fetching content from a remote, 'git index-pack' processes the packfile\ncontent, storing a packfile appropriate for on-disk storage and a pack-index\nhelping to perform random-access into that packfile. To help with\ncompression, the packfile sent over the wire can use REF_DELTAs in addition\nto OFS_DELTAs to refer to objects that are already known to exist in the\nclient's repository. REF_DELTAs can also refer to objects within the\npackfile, though this is not typically done.\n\nBecause this inter-pack REF_DELTA is not a typical data shape, a latent bug\nhas been waiting that causes 'git index-pack' to die() even on legitimate\npackfile content that it could resolve.\n\nThis series resolves this problem while also creating a test helper for\nconstructing packfiles with specific objects represented in specific types\nof deltas and in a given order. This should make it easier to create test\ncases like this in the future instead of updating t/lib-pack.sh through\nother means.\n\n\nUpdates in V2\n=============\n\n * Fixed a memory leak in the test helper.\n * The test helper has a better CLI that makes use of the parse-options\n library.\n * The test script skips the in file and instead feeds the input directly to\n the test helper.\n\nThanks, -Stolee\n\nDerrick Stolee (3):\n test-tool: add pack-deltas helper\n t5309: create failing test for 'git index-pack'\n index-pack: allow revisiting REF_DELTA chains\n\n Makefile | 1 +\n builtin/index-pack.c | 58 ++++++++------\n t/helper/meson.build | 1 +\n t/helper/test-pack-deltas.c | 148 +++++++++++++++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/t5309-pack-delta-cycles.sh | 34 +++++++-\n 7 files changed, 216 insertions(+), 28 deletions(-)\n create mode 100644 t/helper/test-pack-deltas.c\n\n\nbase-commit: 4bbb303af69990ccd05fe3a2eb58a1ce036f8220\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1906%2Fderrickstolee%2Findex-pack-ref-deltas-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1906/derrickstolee/index-pack-ref-deltas-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1906\n\nRange-diff vs v1:\n\n 1: 5d4beb202d6 ! 1: 41aac8e782f test-tool: add pack-deltas helper\n @@ t/helper/test-pack-deltas.c (new)\n +#include \"hex.h\"\n +#include \"pack.h\"\n +#include \"pack-objects.h\"\n ++#include \"parse-options.h\"\n +#include \"setup.h\"\n +#include \"strbuf.h\"\n +#include \"string-list.h\"\n +\n -+static const char usage_str[] = \"test-tool pack-deltas \";\n ++static const char *usage_str[] = {\n ++\t\"test-tool pack-deltas --num-objects \",\n ++\tNULL\n ++};\n +\n +static unsigned long do_compress(void **pptr, unsigned long size)\n +{\n @@ t/helper/test-pack-deltas.c (new)\n +\n +int cmd__pack_deltas(int argc, const char **argv)\n +{\n -+\tint N;\n ++\tint num_objects = -1;\n +\tstruct hashfile *f;\n +\tstruct strbuf line = STRBUF_INIT;\n ++\tstruct option options[] = {\n ++\t\tOPT_INTEGER('n', \"num-objects\", &num_objects, N_(\"the number of objects to write\")),\n ++\t\tOPT_END()\n ++\t};\n +\n -+\tif (argc != 2) {\n -+\t\tusage(usage_str);\n -+\t\treturn -1;\n -+\t}\n ++\targc = parse_options(argc, argv, NULL,\n ++\t\t\t options, usage_str, 0);\n +\n -+\tN = atoi(argv[1]);\n ++\tif (argc || num_objects < 0)\n ++\t\tusage_with_options(usage_str, options);\n +\n +\tsetup_git_directory();\n +\n +\tf = hashfd(the_repository->hash_algo, 1, \"\");\n -+\twrite_pack_header(f, N);\n ++\twrite_pack_header(f, num_objects);\n +\n +\t/* Read each line from stdin into 'line' */\n +\twhile (strbuf_getline_lf(&line, stdin) != EOF) {\n @@ t/helper/test-pack-deltas.c (new)\n +\t\t\tif (get_oid_hex(base_oid_str, &base_oid))\n +\t\t\t\tdie(\"invalid object: %s\", base_oid_str);\n +\t\t}\n ++\t\tstring_list_clear(&items, 0);\n +\n +\t\tif (!strcmp(type_str, \"REF_DELTA\"))\n +\t\t\twrite_ref_delta(f, &content_oid, &base_oid);\n 2: a9430447641 ! 2: 53a990e69ea t5309: create failing test for 'git index-pack'\n @@ t/t5309-pack-delta-cycles.sh: test_expect_success 'failover to a duplicate objec\n +\tC=$(git -C server rev-parse HEAD~2^{tree}) &&\n +\tgit -C server reset --hard HEAD~1 &&\n +\n -+\tcat >in <<-EOF &&\n ++\ttest-tool -C server pack-deltas --num-objects=2 >thin.pack <<-EOF &&\n +\tREF_DELTA $A $B\n +\tREF_DELTA $B $C\n +\tEOF\n +\n -+\ttest-tool -C server pack-deltas 2 thin.pack &&\n -+\n +\tgit clone \"file://$(pwd)/server\" client &&\n +\t(\n +\t\tcd client &&\n 3: 27d36402fe9 = 3: 1358039b2f3 index-pack: allow revisiting REF_DELTA chains\n\n-- \ngitgitgadget\n"},{"id":"516913","messageId":"41aac8e782fdd9e2a19c6fadd27807782fc36203.1745871885.git.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":"pull.1906.v2.git.1745871885.gitgitgadget@gmail.com","subject":"[PATCH v2 1/3] test-tool: add pack-deltas helper","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-28T20:24:43Z","receivedAt":"2025-04-28T20:24:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen trying to demonstrate certain behavior in tests, it can be helpful\nto create packfiles that have specific delta structures. 'git\npack-objects' uses various algorithms to select deltas based on their\ncompression rates, but that does not always demonstrate all possible\npackfile shapes. This becomes especially important when wanting to test\n'git index-pack' and its ability to parse certain pack shapes.\n\nWe have prior art in t/lib-pack.sh, where certain delta structures are\nproduced by manually writing certain opaque pack contents. However,\nproducing these script updates is cumbersome and difficult to do as a\ncontributor.\n\nInstead, create a new test-tool, 'test-tool pack-deltas', that reads a\nlist of instructions for which objects to include in a packfile and how\nthose objects should be written in delta form.\n\nAt the moment, this only supports REF_DELTAs as those are the kinds of\ndeltas needed to exercise a bug in 'git index-pack'.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n t/helper/meson.build | 1 +\n t/helper/test-pack-deltas.c | 148 ++++++++++++++++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n 5 files changed, 152 insertions(+)\n create mode 100644 t/helper/test-pack-deltas.c\n\ndiff --git a/Makefile b/Makefile\nindex 13f9062a056..c4d21ccd3d1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -821,6 +821,7 @@ TEST_BUILTINS_OBJS += test-mergesort.o\n TEST_BUILTINS_OBJS += test-mktemp.o\n TEST_BUILTINS_OBJS += test-name-hash.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\n+TEST_BUILTINS_OBJS += test-pack-deltas.o\n TEST_BUILTINS_OBJS += test-pack-mtimes.o\n TEST_BUILTINS_OBJS += test-parse-options.o\n TEST_BUILTINS_OBJS += test-parse-pathspec-file.o\ndiff --git a/t/helper/meson.build b/t/helper/meson.build\nindex d2cabaa2bcf..d4e8b26df8d 100644\n--- a/t/helper/meson.build\n+++ b/t/helper/meson.build\n@@ -36,6 +36,7 @@ test_tool_sources = [\n 'test-mktemp.c',\n 'test-name-hash.c',\n 'test-online-cpus.c',\n+ 'test-pack-deltas.c',\n 'test-pack-mtimes.c',\n 'test-parse-options.c',\n 'test-parse-pathspec-file.c',\ndiff --git a/t/helper/test-pack-deltas.c b/t/helper/test-pack-deltas.c\nnew file mode 100644\nindex 00000000000..4caa024b1eb\n--- /dev/null\n+++ b/t/helper/test-pack-deltas.c\n@@ -0,0 +1,148 @@\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n+#include \"test-tool.h\"\n+#include \"git-compat-util.h\"\n+#include \"delta.h\"\n+#include \"git-zlib.h\"\n+#include \"hash.h\"\n+#include \"hex.h\"\n+#include \"pack.h\"\n+#include \"pack-objects.h\"\n+#include \"parse-options.h\"\n+#include \"setup.h\"\n+#include \"strbuf.h\"\n+#include \"string-list.h\"\n+\n+static const char *usage_str[] = {\n+\t\"test-tool pack-deltas --num-objects \",\n+\tNULL\n+};\n+\n+static unsigned long do_compress(void **pptr, unsigned long size)\n+{\n+\tgit_zstream stream;\n+\tvoid *in, *out;\n+\tunsigned long maxsize;\n+\n+\tgit_deflate_init(&stream, 1);\n+\tmaxsize = git_deflate_bound(&stream, size);\n+\n+\tin = *pptr;\n+\tout = xmalloc(maxsize);\n+\t*pptr = out;\n+\n+\tstream.next_in = in;\n+\tstream.avail_in = size;\n+\tstream.next_out = out;\n+\tstream.avail_out = maxsize;\n+\twhile (git_deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t; /* nothing */\n+\tgit_deflate_end(&stream);\n+\n+\tfree(in);\n+\treturn stream.total_out;\n+}\n+\n+static void write_ref_delta(struct hashfile *f,\n+\t\t\t struct object_id *oid,\n+\t\t\t struct object_id *base)\n+{\n+\tunsigned char header[MAX_PACK_OBJECT_HEADER];\n+\tunsigned long size, base_size, delta_size, compressed_size, hdrlen;\n+\tenum object_type type;\n+\tvoid *base_buf, *delta_buf;\n+\tvoid *buf = repo_read_object_file(the_repository,\n+\t\t\t\t\t oid, &type,\n+\t\t\t\t\t &size);\n+\n+\tif (!buf)\n+\t\tdie(\"unable to read %s\", oid_to_hex(oid));\n+\n+\tbase_buf = repo_read_object_file(the_repository,\n+\t\t\t\t\t base, &type,\n+\t\t\t\t\t &base_size);\n+\n+\tif (!base_buf)\n+\t\tdie(\"unable to read %s\", oid_to_hex(base));\n+\n+\tdelta_buf = diff_delta(base_buf, base_size,\n+\t\t\t buf, size, &delta_size, 0);\n+\n+\tcompressed_size = do_compress(&delta_buf, delta_size);\n+\n+\thdrlen = encode_in_pack_object_header(header, sizeof(header),\n+\t\t\t\t\t OBJ_REF_DELTA, delta_size);\n+\thashwrite(f, header, hdrlen);\n+\thashwrite(f, base->hash, the_repository->hash_algo->rawsz);\n+\thashwrite(f, delta_buf, compressed_size);\n+\n+\tfree(buf);\n+\tfree(base_buf);\n+\tfree(delta_buf);\n+}\n+\n+int cmd__pack_deltas(int argc, const char **argv)\n+{\n+\tint num_objects = -1;\n+\tstruct hashfile *f;\n+\tstruct strbuf line = STRBUF_INIT;\n+\tstruct option options[] = {\n+\t\tOPT_INTEGER('n', \"num-objects\", &num_objects, N_(\"the number of objects to write\")),\n+\t\tOPT_END()\n+\t};\n+\n+\targc = parse_options(argc, argv, NULL,\n+\t\t\t options, usage_str, 0);\n+\n+\tif (argc || num_objects < 0)\n+\t\tusage_with_options(usage_str, options);\n+\n+\tsetup_git_directory();\n+\n+\tf = hashfd(the_repository->hash_algo, 1, \"\");\n+\twrite_pack_header(f, num_objects);\n+\n+\t/* Read each line from stdin into 'line' */\n+\twhile (strbuf_getline_lf(&line, stdin) != EOF) {\n+\t\tconst char *type_str, *content_oid_str, *base_oid_str = NULL;\n+\t\tstruct object_id content_oid, base_oid;\n+\t\tstruct string_list items = STRING_LIST_INIT_NODUP;\n+\t\t/*\n+\t\t * Tokenize into two or three parts:\n+\t\t * 1. REF_DELTA, OFS_DELTA, or FULL.\n+\t\t * 2. The object ID for the content object.\n+\t\t * 3. The object ID for the base object (optional).\n+\t\t */\n+\t\tif (string_list_split_in_place(&items, line.buf, \" \", 3) < 0)\n+\t\t\tdie(\"invalid input format: %s\", line.buf);\n+\n+\t\tif (items.nr < 2)\n+\t\t\tdie(\"invalid input format: %s\", line.buf);\n+\n+\t\ttype_str = items.items[0].string;\n+\t\tcontent_oid_str = items.items[1].string;\n+\n+\t\tif (get_oid_hex(content_oid_str, &content_oid))\n+\t\t\tdie(\"invalid object: %s\", content_oid_str);\n+\t\tif (items.nr >= 3) {\n+\t\t\tbase_oid_str = items.items[2].string;\n+\t\t\tif (get_oid_hex(base_oid_str, &base_oid))\n+\t\t\t\tdie(\"invalid object: %s\", base_oid_str);\n+\t\t}\n+\t\tstring_list_clear(&items, 0);\n+\n+\t\tif (!strcmp(type_str, \"REF_DELTA\"))\n+\t\t\twrite_ref_delta(f, &content_oid, &base_oid);\n+\t\telse if (!strcmp(type_str, \"OFS_DELTA\"))\n+\t\t\tdie(\"OFS_DELTA not implemented\");\n+\t\telse if (!strcmp(type_str, \"FULL\"))\n+\t\t\tdie(\"FULL not implemented\");\n+\t\telse\n+\t\t\tdie(\"unknown pack type: %s\", type_str);\n+\t}\n+\n+\tfinalize_hashfile(f, NULL, FSYNC_COMPONENT_PACK,\n+\t\t\t CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);\n+\tstrbuf_release(&line);\n+\treturn 0;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex 50dc4dac4ed..74812ed86d3 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -46,6 +46,7 @@ static struct test_cmd cmds[] = {\n \t{ \"mktemp\", cmd__mktemp },\n \t{ \"name-hash\", cmd__name_hash },\n \t{ \"online-cpus\", cmd__online_cpus },\n+\t{ \"pack-deltas\", cmd__pack_deltas },\n \t{ \"pack-mtimes\", cmd__pack_mtimes },\n \t{ \"parse-options\", cmd__parse_options },\n \t{ \"parse-options-flags\", cmd__parse_options_flags },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex 6d62a5b53d9..2571a3ccfe8 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -39,6 +39,7 @@ int cmd__mergesort(int argc, const char **argv);\n int cmd__mktemp(int argc, const char **argv);\n int cmd__name_hash(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\n+int cmd__pack_deltas(int argc, const char **argv);\n int cmd__pack_mtimes(int argc, const char **argv);\n int cmd__parse_options(int argc, const char **argv);\n int cmd__parse_options_flags(int argc, const char **argv);\n-- \ngitgitgadget\n\n"},{"id":"516914","messageId":"53a990e69eaf9564e6bb7a38f9205a17283321de.1745871885.git.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":"pull.1906.v2.git.1745871885.gitgitgadget@gmail.com","subject":"[PATCH v2 2/3] t5309: create failing test for 'git index-pack'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-28T20:24:44Z","receivedAt":"2025-04-28T20:24:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis new test demonstrates some behavior where a valid packfile is being\nrejected by the Git client due to the order in which it is resolving\nREF_DELTAs.\n\nThe thin packfile has a REF_DELTA chain A->B->C where C is not included\nin the packfile. However, the client repository contains both C and B\nalready. Thus, 'git index-pack' is able to resolve A before resolving B.\n\nWhen resolving B, it then attempts to resolve any other REF_DELTAs that\nare pointing to B as a base. This \"revisits\" A and complains as if there\nis a cycle, but it did not actually detect a cycle.\n\nA fix will arrive in the next change.\n\nSigned-off-by: Derrick Stolee \n---\n t/t5309-pack-delta-cycles.sh | 24 ++++++++++++++++++++++++\n 1 file changed, 24 insertions(+)\n\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 60fc710bacb..6a936763302 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -75,4 +75,28 @@ test_expect_success 'failover to a duplicate object in the same pack' '\n \ttest_must_fail git index-pack --fix-thin --stdin B->C with B on disk' '\n+\tgit init server &&\n+\t(\n+\t\tcd server &&\n+\t\ttest_commit_bulk 4\n+\t) &&\n+\n+\tA=$(git -C server rev-parse HEAD^{tree}) &&\n+\tB=$(git -C server rev-parse HEAD~1^{tree}) &&\n+\tC=$(git -C server rev-parse HEAD~2^{tree}) &&\n+\tgit -C server reset --hard HEAD~1 &&\n+\n+\ttest-tool -C server pack-deltas --num-objects=2 >thin.pack <<-EOF &&\n+\tREF_DELTA $A $B\n+\tREF_DELTA $B $C\n+\tEOF\n+\n+\tgit clone \"file://$(pwd)/server\" client &&\n+\t(\n+\t\tcd client &&\n+\t\tgit index-pack --fix-thin --stdin <../thin.pack\n+\t)\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"516915","messageId":"1358039b2f3bf893fffc63c1065f1d6862b74957.1745871885.git.gitgitgadget@gmail.com","threadId":"63337","inReplyTo":"pull.1906.v2.git.1745871885.gitgitgadget@gmail.com","subject":"[PATCH v2 3/3] index-pack: allow revisiting REF_DELTA chains","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-04-28T20:24:45Z","receivedAt":"2025-04-28T20:24:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAs detailed in the previous changes to t5309-pack-delta-cycles.sh, the\nlogic within 'git index-pack' to analyze an incoming thin packfile with\nREF_DELTAs is suspect. The algorithm is overly cautious around delta\ncycles, and that leads in fact to failing even when there is no cycle.\n\nThis change adjusts the algorithm to no longer fail in these cases. In\nfact, these cycle cases will no longer fail but more importantly the\nvalid cases will no longer fail, either. The resulting packfile from the\n--fix-thin operation will not have cycles either since REF_DELTAs are\nforbidden from the on-disk format and OFS_DELTAs are impossible to write\nas a cycle.\n\nThe crux of the matter is how the algorithm works when the REF_DELTAs\npoint to base objects that exist in the local repository. When reading\nthe thin packfile, the object IDs for the delta objects are unknown so\nwe do not have the delta chain structure automatically. Instead, we need\nto start somewhere by selecting a delta whose base is inside our current\nobject database.\n\nConsider the case where the packfile has two REF_DELTA objects, A and B,\nand the delta chain looks like \"A depends on B\" and \"B depends on C\" for\nsome third object C, where C is already in the current repository. The\nalgorithm _should_ start with all objects that depend on C, finding B,\nand then moving on to all objects depending on B, finding A.\n\nHowever, if the repository also already has object B, then the delta\nchain can be analyzed in a different order. The deltas with base B can\nbe analyzed first, finding A, and then the deltas with base C are\nanalyzed, finding B. The algorithm currently continues to look for\nobjects that depend on B, finding A again. This fails due to A's\n'real_type' member already being overwritten from OBJ_REF_DELTA to the\ncorrect object type.\n\nThis scenario is possible in a typical 'git fetch' where the client does\nnot advertise B as a 'have' but requests A as a 'want' (and C is noticed\nas a common object based on other 'have's). The reason this isn't\ntypically seen is that most Git servers use OFS_DELTAs to represent\ndeltas within a packfile. However, if a server uses only REF_DELTAs,\nthen this kind of issue can occur. There is nothing in the explicit\npackfile format that states this use of inter-pack REF_DELTA is\nincorrect, only that REF_DELTAs should not be used in the on-disk\nrepresentation to avoid cycles.\n\nThis die() was introduced in ab791dd138 (index-pack: fix race condition\nwith duplicate bases, 2014-08-29). Several refactors have adjusted the\nerror message and the surrounding logic, but this issue has existed for\na longer time as that was only a conversion from an assert().\n\nThe tests in t5309 originated in 3b910d0c5e (add tests for indexing\npacks with delta cycles, 2013-08-23) and b2ef3d9ebb (test index-pack on\npacks with recoverable delta cycles, 2013-08-23). These changes make\nnote that the current behavior of handling \"resolvable\" cycles is mostly\na documentation-only test, not that this behavior is the best way for\nGit to handle the situation.\n\nThe fix here is somewhat complicated due to the amount of state being\nadjusted by the loop within threaded_second_pass(). Instead of trying to\nresume the start of the loop while adjusting the necessary context, I\nchose to scan the REF_DELTAs depending on the current 'parent' and skip\nany that have already been processed. This necessarily leaves us in a\nstate where 'child' and 'child_obj' could be left as NULL and that must\nbe handled later. There is also some careful handling around skipping\nREF_DELTAs when there are also OFS_DELTAs depending on that parent.\nThere may be value in extending 'test-tool pack-deltas' to allow writing\nOFS_DELTAs in order to exercise this logic across the delta types.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/index-pack.c | 58 ++++++++++++++++++++----------------\n t/t5309-pack-delta-cycles.sh | 12 ++++++--\n 2 files changed, 41 insertions(+), 29 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex de127c0ff13..dbe79701fb8 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1109,8 +1109,8 @@ static void *threaded_second_pass(void *data)\n \t\tset_thread_data(data);\n \tfor (;;) {\n \t\tstruct base_data *parent = NULL;\n-\t\tstruct object_entry *child_obj;\n-\t\tstruct base_data *child;\n+\t\tstruct object_entry *child_obj = NULL;\n+\t\tstruct base_data *child = NULL;\n \n \t\tcounter_lock();\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n@@ -1137,15 +1137,18 @@ static void *threaded_second_pass(void *data)\n \t\t\tparent = list_first_entry(&work_head, struct base_data,\n \t\t\t\t\t\t list);\n \n-\t\t\tif (parent->ref_first <= parent->ref_last) {\n+\t\t\twhile (parent->ref_first <= parent->ref_last) {\n \t\t\t\tint offset = ref_deltas[parent->ref_first++].obj_no;\n \t\t\t\tchild_obj = objects + offset;\n-\t\t\t\tif (child_obj->real_type != OBJ_REF_DELTA)\n-\t\t\t\t\tdie(\"REF_DELTA at offset %\"PRIuMAX\" already resolved (duplicate base %s?)\",\n-\t\t\t\t\t (uintmax_t) child_obj->idx.offset,\n-\t\t\t\t\t oid_to_hex(&parent->obj->idx.oid));\n+\t\t\t\tif (child_obj->real_type != OBJ_REF_DELTA) {\n+\t\t\t\t\tchild_obj = NULL;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n \t\t\t\tchild_obj->real_type = parent->obj->real_type;\n-\t\t\t} else {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n+\t\t\tif (!child_obj && parent->ofs_first <= parent->ofs_last) {\n \t\t\t\tchild_obj = objects +\n \t\t\t\t\tofs_deltas[parent->ofs_first++].obj_no;\n \t\t\t\tassert(child_obj->real_type == OBJ_OFS_DELTA);\n@@ -1178,29 +1181,32 @@ static void *threaded_second_pass(void *data)\n \t\t}\n \t\twork_unlock();\n \n-\t\tif (parent) {\n-\t\t\tchild = resolve_delta(child_obj, parent);\n-\t\t\tif (!child->children_remaining)\n-\t\t\t\tFREE_AND_NULL(child->data);\n-\t\t} else {\n-\t\t\tchild = make_base(child_obj, NULL);\n-\t\t\tif (child->children_remaining) {\n-\t\t\t\t/*\n-\t\t\t\t * Since this child has its own delta children,\n-\t\t\t\t * we will need this data in the future.\n-\t\t\t\t * Inflate now so that future iterations will\n-\t\t\t\t * have access to this object's data while\n-\t\t\t\t * outside the work mutex.\n-\t\t\t\t */\n-\t\t\t\tchild->data = get_data_from_pack(child_obj);\n-\t\t\t\tchild->size = child_obj->size;\n+\t\tif (child_obj) {\n+\t\t\tif (parent) {\n+\t\t\t\tchild = resolve_delta(child_obj, parent);\n+\t\t\t\tif (!child->children_remaining)\n+\t\t\t\t\tFREE_AND_NULL(child->data);\n+\t\t\t} else{\n+\t\t\t\tchild = make_base(child_obj, NULL);\n+\t\t\t\tif (child->children_remaining) {\n+\t\t\t\t\t/*\n+\t\t\t\t\t * Since this child has its own delta children,\n+\t\t\t\t\t * we will need this data in the future.\n+\t\t\t\t\t * Inflate now so that future iterations will\n+\t\t\t\t\t * have access to this object's data while\n+\t\t\t\t\t * outside the work mutex.\n+\t\t\t\t\t */\n+\t\t\t\t\tchild->data = get_data_from_pack(child_obj);\n+\t\t\t\t\tchild->size = child_obj->size;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \n \t\twork_lock();\n \t\tif (parent)\n \t\t\tparent->retain_data--;\n-\t\tif (child->data) {\n+\n+\t\tif (child && child->data) {\n \t\t\t/*\n \t\t\t * This child has its own children, so add it to\n \t\t\t * work_head.\n@@ -1209,7 +1215,7 @@ static void *threaded_second_pass(void *data)\n \t\t\tbase_cache_used += child->size;\n \t\t\tprune_base_data(NULL);\n \t\t\tfree_base_data(child);\n-\t\t} else {\n+\t\t} else if (child) {\n \t\t\t/*\n \t\t\t * This child does not have its own children. It may be\n \t\t\t * the last descendant of its ancestors; free those\ndiff --git a/t/t5309-pack-delta-cycles.sh b/t/t5309-pack-delta-cycles.sh\nindex 6a936763302..6b03675d91b 100755\n--- a/t/t5309-pack-delta-cycles.sh\n+++ b/t/t5309-pack-delta-cycles.sh\n@@ -60,7 +60,10 @@ test_expect_success 'index-pack detects REF_DELTA cycles' '\n test_expect_success 'failover to an object in another pack' '\n \tclear_packs &&\n \tgit index-pack --stdin recoverable.pack &&\n \tpack_trailer recoverable.pack &&\n-\ttest_must_fail git index-pack --fix-thin --stdin B->C with B on disk' '\n+test_expect_success 'index-pack works with thin pack A->B->C with B on disk' '\n \tgit init server &&\n \t(\n \t\tcd server &&\n-- \ngitgitgadget\n"},{"id":"516916","messageId":"xmqqwmb4ausy.fsf@gitster.g","threadId":"63337","inReplyTo":"6df25bf2-6df1-4c3a-9061-e3297dec38ab@gmail.com","subject":"Re: [PATCH 1/3] test-tool: add pack-deltas helper","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-28T20:35:25Z","receivedAt":"2025-04-28T20:35:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> This makes sense as a feature, except that we need to write the number\n> of objects present in a packfile in its header. If we wanted to avoid\n> the argument, then we'd need to load the data into a list before\n> starting to write the packfile. By taking the count in advance, the\n> implementation is simpler.\n\nPerhaps, but in the production code we already seek back and update\nthe header after writing a packfile with fixup_pack_header_footer(),\nso which shoulnd't be too much work conceptually. You earlier said\nsomething about faster development cycles; not having to figure out\nhow to seek back and fix the header does help faster development of\nthis helper ;-).\n\n>> One thing it lets\n>> us do to have this as a separate number is to create an invalid pack\n>> stream where the header gives a wrong number, and as a test tool,\n>> that may trump the convenience of not having to give the number\n>> explicitly.\n> But also, this allows generating bad packfiles which is a bonus.\n> A very good point. \n\nIf this were an end-user facing program, we would most likely let it\ncount but let the count be overridden by the command line argument.\n\nBut until then, as I said, I am fine to just declare that it is just\na test helper ;-)\n\nThanks.\n"},{"id":"516924","messageId":"xmqqecxbap0l.fsf@gitster.g","threadId":"63337","inReplyTo":"pull.1906.v2.git.1745871885.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/3] Fix REF_DELTA chain bug in 'git index-pack'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-28T22:40:26Z","receivedAt":"2025-04-28T22:40:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> Updates in V2\n> =============\n>\n> * Fixed a memory leak in the test helper.\n> * The test helper has a better CLI that makes use of the parse-options\n> library.\n> * The test script skips the in file and instead feeds the input directly to\n> the test helper.\n\nEverything in the changes relative to the previous iteration looked\nquite sane. Will replace. Thanks.\n"},{"id":"516928","messageId":"aBBkq_WQGHziC9is@pks.im","threadId":"63337","inReplyTo":"xmqqecxbap0l.fsf@gitster.g","subject":"Re: [PATCH v2 0/3] Fix REF_DELTA chain bug in 'git index-pack'","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-04-29T05:33:31Z","receivedAt":"2025-04-29T05:33:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Apr 28, 2025 at 03:40:26PM -0700, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n> > Updates in V2\n> > =============\n> >\n> > * Fixed a memory leak in the test helper.\n> > * The test helper has a better CLI that makes use of the parse-options\n> > library.\n> > * The test script skips the in file and instead feeds the input directly to\n> > the test helper.\n> \n> Everything in the changes relative to the previous iteration looked\n> quite sane. Will replace. Thanks.\n\nSeconded, the range-diff looks as expected and addresses my comments.\nThanks!\n\nPatrick\n"},{"id":"517431","messageId":"aBrAlc8k8uxzrIV9@nand.local","threadId":"63337","inReplyTo":"1358039b2f3bf893fffc63c1065f1d6862b74957.1745871885.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/3] index-pack: allow revisiting REF_DELTA chains","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-05-07T02:08:21Z","receivedAt":"2025-05-07T02:08:23Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Apr 28, 2025 at 08:24:45PM +0000, Derrick Stolee via GitGitGadget wrote:\n> The crux of the matter is how the algorithm works when the REF_DELTAs\n> point to base objects that exist in the local repository.\n\nHmm. I'm having trouble squaring this with these next two paragraphs:\n\n> Consider the case where the packfile has two REF_DELTA objects, A and B,\n> and the delta chain looks like \"A depends on B\" and \"B depends on C\" for\n> some third object C, where C is already in the current repository. The\n> algorithm _should_ start with all objects that depend on C, finding B,\n> and then moving on to all objects depending on B, finding A.\n>\n> However, if the repository also already has object B, then the delta\n> chain can be analyzed in a different order. The deltas with base B can\n> be analyzed first, finding A, and then the deltas with base C are\n> analyzed, finding B. The algorithm currently continues to look for\n> objects that depend on B, finding A again. This fails due to A's\n> 'real_type' member already being overwritten from OBJ_REF_DELTA to the\n> correct object type.\n\nISTM that this A->B->C chain is a problem because (in the above example)\nthe server sent B as a REF_DELTA base for A but also had its own\npre-existing copy of B.\n\nBut the first quoted sentence suggests that the issue is with REF_DELTAs\nthat point to base objects that exist in the local repository. Does\n\"point to\" mean that the REF_DELTA's base is the local object, or that\nthe local object itself was sent as a REF_DELTA against some other base?\n\nI haven't fully wrapped my head around the implications of this all yet,\nbut I think that it's the former, though admittedly even typing this I\nam not quite sure of myself. I *think* that doing this is OK if the only\npath from base objects to their corresponding deltas is unique, and/or\nthere were no such paths at all.\n\nI'm trying to think through the implications of this against my\nseries[1] from a while ago that converts OFS_DELTAs that weren't usable\nas part of verbatim pack-reuse into REF_DELTAs. There are two cases\nthere that I was considering:\n\n - For some (delta, base) pair in a pack, there was an additional copy\n of 'base' in some other pack, and the MIDX chose the copy from that\n pack. That forms what I'm calling a \"cross-pack\" delta. This isn't\n currently reusable as an OFS_DELTA for a variety of reasons, but is\n OK as a REF_DELTA provided we know that the client either already\n has the base object or we are sending it as part of the pack anyway.\n\n - The other case is that we the client wants the delta-half of a\n delta/base-pair, but not the base object. In this case, we can't\n currently reuse the OFS_DELTA verbatim, but could if we converted it\n to a REF_DELTA based on the knowledge that the client already has\n the base object.\n\nThe latter is doable based on the information in the wants/haves bitmap.\nThe process there looks like: determine that the client doesn't want the\nbase object, realize that its bit is set in the 'haves' bitmap, and then\nconvert the delta object from a OFS_DELTA to a REF_DELTA.\n\nBut I think that all breaks for older clients that don't meet the unique\npaths condition above. Does that sound right to you?\n\nI think the cross-pack case is fine, provided we know ahead of time that\nthe client doesn't have the (converted-to-REF_DELTA) delta object in its\nlocal copy.\n\nUnfortunately, I think this means that [1] is a bit of a dead-end for\nserves that have older clients (running a version that does not include\nthis patch). At least, I think that's true if we can construct a\nsituation where the server sends a REF_DELTA that it thinks the client\ndoesn't have but actually does. I'm not immediately sure what such a\nsituation would look like beyond cases like: \"the client verbatim asked\nfor an object it already has, but isn't reachable from the set of\nprovided 'haves'\".\n\nThanks,\nTaylor\n\n[1]: https://lore.kernel.org/git/cover.1728505840.git.me@ttaylorr.com/\n"},{"id":"517492","messageId":"43b5bf20-89b8-4eca-a952-0bcc28a23d19@gmail.com","threadId":"63337","inReplyTo":"aBrAlc8k8uxzrIV9@nand.local","subject":"Re: [PATCH v2 3/3] index-pack: allow revisiting REF_DELTA chains","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-05-07T13:47:46Z","receivedAt":"2025-05-07T13:47:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/6/2025 10:08 PM, Taylor Blau wrote:\n> On Mon, Apr 28, 2025 at 08:24:45PM +0000, Derrick Stolee via GitGitGadget wrote:\n>> The crux of the matter is how the algorithm works when the REF_DELTAs\n>> point to base objects that exist in the local repository.\n> \n> Hmm. I'm having trouble squaring this with these next two paragraphs:\n> \n>> Consider the case where the packfile has two REF_DELTA objects, A and B,\n>> and the delta chain looks like \"A depends on B\" and \"B depends on C\" for\n>> some third object C, where C is already in the current repository. The\n>> algorithm _should_ start with all objects that depend on C, finding B,\n>> and then moving on to all objects depending on B, finding A.\n>>\n>> However, if the repository also already has object B, then the delta\n>> chain can be analyzed in a different order. The deltas with base B can\n>> be analyzed first, finding A, and then the deltas with base C are\n>> analyzed, finding B. The algorithm currently continues to look for\n>> objects that depend on B, finding A again. This fails due to A's\n>> 'real_type' member already being overwritten from OBJ_REF_DELTA to the\n>> correct object type.\n> \n> ISTM that this A->B->C chain is a problem because (in the above example)\n> the server sent B as a REF_DELTA base for A but also had its own\n> pre-existing copy of B.\n> \n> But the first quoted sentence suggests that the issue is with REF_DELTAs\n> that point to base objects that exist in the local repository. Does\n> \"point to\" mean that the REF_DELTA's base is the local object, or that\n> the local object itself was sent as a REF_DELTA against some other base?\n\nThe issue is that based on the negotiation, the server knows the client\nwants A and has C but doesn't think the client has B despite the client\nhaving B.\n\nIf the server sends these two objects as a delta chain A->B->C using\nREF_DELTAs (and not the typical OFS_DELTA from A to B) then the client\nmay inflate A first and B second (and then try to inflate A again).\n\n> I haven't fully wrapped my head around the implications of this all yet,\n> but I think that it's the former, though admittedly even typing this I\n> am not quite sure of myself. I *think* that doing this is OK if the only\n> path from base objects to their corresponding deltas is unique, and/or\n> there were no such paths at all.\n> \n> I'm trying to think through the implications of this against my\n> series[1] from a while ago that converts OFS_DELTAs that weren't usable\n> as part of verbatim pack-reuse into REF_DELTAs. There are two cases\n> there that I was considering:\n> \n> - For some (delta, base) pair in a pack, there was an additional copy\n> of 'base' in some other pack, and the MIDX chose the copy from that\n> pack. That forms what I'm calling a \"cross-pack\" delta. This isn't\n> currently reusable as an OFS_DELTA for a variety of reasons, but is\n> OK as a REF_DELTA provided we know that the client either already\n> has the base object or we are sending it as part of the pack anyway.\n\nThese are the kinds of deltas that could hit this problem.\n\n> - The other case is that we the client wants the delta-half of a\n> delta/base-pair, but not the base object. In this case, we can't\n> currently reuse the OFS_DELTA verbatim, but could if we converted it\n> to a REF_DELTA based on the knowledge that the client already has\n> the base object.\n\nIf we know the client has the base object, then not including the base in\nthe pack and referencing it as a REF_DELTA will always be OK.\n\n> The latter is doable based on the information in the wants/haves bitmap.\n> The process there looks like: determine that the client doesn't want the\n> base object, realize that its bit is set in the 'haves' bitmap, and then\n> convert the delta object from a OFS_DELTA to a REF_DELTA.\n> \n> But I think that all breaks for older clients that don't meet the unique\n> paths condition above. Does that sound right to you?\n> \n> I think the cross-pack case is fine, provided we know ahead of time that\n> the client doesn't have the (converted-to-REF_DELTA) delta object in its\n> local copy.\n> \n> Unfortunately, I think this means that [1] is a bit of a dead-end for\n> serves that have older clients (running a version that does not include\n> this patch). At least, I think that's true if we can construct a\n> situation where the server sends a REF_DELTA that it thinks the client\n> doesn't have but actually does. I'm not immediately sure what such a\n> situation would look like beyond cases like: \"the client verbatim asked\n> for an object it already has, but isn't reachable from the set of\n> provided 'haves'\".\n\nI agree that [1] is going to present more opportunities for this bug to\nbe hit by older clients, though I will admit that the frequency of the\nproblem seems to have odd frequencies. It relies upon the fact that the\nfetch negotiation fails to identify \"B\" as a common object. This sort of\nthing can happen more frequently when using the commit boundary between\nthe haves and wants (instead of walking from all haves like a bitmap walk\nwould do). If the client fails to advertise all of its haves, then that\ncould also lead to this problem even if the server is walking all objects\nreachable from the haves.\n\nThe other thing that you'll have going for you is that cross-pack deltas\nshould be rare. The case that helped me discover this issue was where the\nserver did not send any OFS_DELTAs at all but used REF_DELTAs for all\ndelta relationships. (This is required if the client doesn't advertise\nthe \"ofs-delta\" capability, but we'd need to go _way_ back for a client\nto not include that capability.)\n\nThanks,\n-Stolee\n\n"}]}