{"thread":{"id":"62610","subject":"[PATCH 0/5] PATH WALK III: Add 'git backfill' command","startedAt":"2024-12-06T20:07:21Z","lastAt":"2025-02-05T17:07:30Z","messageCount":39,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Patrick Steinhardt","Derrick Stolee","Jean-Noël AVILA"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"508803","messageId":"pull.1820.git.1733515638.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":null,"subject":"[PATCH 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-06T20:07:13Z","receivedAt":"2024-12-06T20:07:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This is based on v3 of ds/path-walk-1 [1] and an earlier version was part of\nmy initial path-walk RFC [2].\n\n[1]\nhttps://lore.kernel.org/git/pull.1818.v3.git.1733514358.gitgitgadget@gmail.com/\n\n[2]\nhttps://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/\n\nThis series adds a new 'git backfill' command that uses the path-walk API to\ndownload missing blobs in a blobless partial clone. Users can specify\ninteraction with the sparse-checkout using '--[no-]sparse' but the\n'--sparse' option is implied by the existence of a sparse-checkout.\n\nThe reason to use the path-walk API is to make sure that the missing objects\nare grouped by a common path, giving a reasonable process for batching\nrequests and expecting the server to compress the resulting packfile nicely\ntogether.\n\nI first prototyped this feature in June 2024 as an exploration and created\nthe path-walk algorithm for this purpose. It was only my intuition that led\nme to believe that batching by path would lead to better packfiles. This has\nbeen proven out as a very important feature due to recent investigations to\ncompressing full repositories by doing a better job of grouping objects by\npath. See the --name-hash-version series [3] or the 'git pack-objects\n--path-walk' series [4] (currently on hold as it conflicts with the\n--name-hash-version series).\n\n[3]\nhttps://lore.kernel.org/git/pull.1823.v2.git.1733181682.gitgitgadget@gmail.com/\n\n[4]\nhttps://lore.kernel.org/git/pull.1813.v2.git.1729431810.gitgitgadget@gmail.com/\n\nThis idea can be further demonstrated by the evidence in testing this\nfeature: by downloading objects in small batch sizes, the client can force\nthe server to repack things more efficiently than a full repack.\n\nThe example repository I have used in multiple places is the\nmicrosoft/fluentui repo [5] as it has many CHANGELOG.md files that cause\nname hash collisions that make the full repack inefficient.\n\n[5] https://github.com/microsoft/fluentui\n\nIf we create a blobless clone of the fluentui repo, then this downloads 105\nMB across two packfiles (the commits and trees pack, followed by the blobs\nneeded for an initial checkout). Running 'git backfill --batch-size=' for\ndifferent sizes leads to some interesting results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 105 MB | |\n| 5K | 53 | 348 MB | 2m 26s |\n| 10K | 28 | 365 MB | 2m 22s |\n| 15K | 19 | 407 MB | 2m 21s |\n| 20K | 15 | 393 MB | 2m 28s |\n| 25K | 13 | 417 MB | 2m 06s |\n| 50K | 8 | 509 MB | 1m 34s |\n| 100K | 5 | 535 MB | 1m 56s |\n| 250K | 4 | 698 MB | 1m 33s |\n| 500K | 3 | 696 MB | 1m 42s |\n\n\nThe smaller batches cause the server to realize that the existing deltas\ncannot be reused and it finds better deltas. This takes some extra time for\nthe small batches, but halves the size of the repo. Even in the 500K batch\nsize, we get less data than the 738 MB of a full clone.\n\nImplementing the --sparse feature is best done by augmenting the path-walk\nAPI to be aware of a pattern list. This works for both cone and non-cone\nmode sparse-checkouts.\n\nThere are future directions we could take this command, especially to run\nthe command with a user-specified pathspec. The tricky case for that\nadditional feature is trying to make the path-walk more efficient by\nskipping tree paths that would not lead to a match of the pathspec. It would\nlikely need optimization in a small subset of pathspec features (such as\nprefix matches) to work as efficiently as possible. I did prototype a\nversion that puts the pathspec match in the callback function within\nbuiltin/backfill.c, but I found that uninspiring and unnecessary for now.\n\nThanks, -Stolee\n\nDerrick Stolee (5):\n backfill: add builtin boilerplate\n backfill: basic functionality and tests\n backfill: add --batch-size= option\n backfill: add --sparse option\n backfill: assume --sparse when sparse-checkout is enabled\n\n .gitignore | 1 +\n Documentation/git-backfill.txt | 60 ++++++++\n Documentation/technical/api-path-walk.txt | 11 +-\n Makefile | 1 +\n builtin.h | 1 +\n builtin/backfill.c | 147 ++++++++++++++++++\n command-list.txt | 1 +\n dir.c | 10 +-\n dir.h | 3 +\n git.c | 1 +\n path-walk.c | 18 +++\n path-walk.h | 11 ++\n t/helper/test-path-walk.c | 22 ++-\n t/t5620-backfill.sh | 178 ++++++++++++++++++++++\n t/t6601-path-walk.sh | 32 ++++\n 15 files changed, 488 insertions(+), 9 deletions(-)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 builtin/backfill.c\n create mode 100755 t/t5620-backfill.sh\n\n\nbase-commit: e716672c041473dd2bf257b7532b86696fef32a0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1820%2Fderrickstolee%2Fbackfill-upstream-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1820/derrickstolee/backfill-upstream-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1820\n-- \ngitgitgadget\n"},{"id":"508804","messageId":"0300aa1b8c37dcd0d529cc24588ae77960fdfbff.1733515638.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.git.1733515638.gitgitgadget@gmail.com","subject":"[PATCH 1/5] backfill: add builtin boilerplate","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-06T20:07:14Z","receivedAt":"2024-12-06T20:07:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of implementing 'git backfill', populate the necessary files\nwith the boilerplate of a new builtin.\n\nSigned-off-by: Derrick Stolee \n---\n .gitignore | 1 +\n Documentation/git-backfill.txt | 23 +++++++++++++++++++++++\n Makefile | 1 +\n builtin.h | 1 +\n builtin/backfill.c | 29 +++++++++++++++++++++++++++++\n command-list.txt | 1 +\n git.c | 1 +\n 7 files changed, 57 insertions(+)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 builtin/backfill.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 6687bd6db4c..0f9e7de2ec3 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -20,6 +20,7 @@\n /git-apply\n /git-archimport\n /git-archive\n+/git-backfill\n /git-bisect\n /git-blame\n /git-branch\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nnew file mode 100644\nindex 00000000000..640144187d3\n--- /dev/null\n+++ b/Documentation/git-backfill.txt\n@@ -0,0 +1,23 @@\n+git-backfill(1)\n+===============\n+\n+NAME\n+----\n+git-backfill - Download missing objects in a partial clone\n+\n+\n+SYNOPSIS\n+--------\n+[verse]\n+'git backfill' []\n+\n+DESCRIPTION\n+-----------\n+\n+SEE ALSO\n+--------\n+linkgit:git-clone[1].\n+\n+GIT\n+---\n+Part of the linkgit:git[1] suite\ndiff --git a/Makefile b/Makefile\nindex 50413d96492..e18e0f4e447 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1203,6 +1203,7 @@ BUILTIN_OBJS += builtin/am.o\n BUILTIN_OBJS += builtin/annotate.o\n BUILTIN_OBJS += builtin/apply.o\n BUILTIN_OBJS += builtin/archive.o\n+BUILTIN_OBJS += builtin/backfill.o\n BUILTIN_OBJS += builtin/bisect.o\n BUILTIN_OBJS += builtin/blame.o\n BUILTIN_OBJS += builtin/branch.o\ndiff --git a/builtin.h b/builtin.h\nindex f7b166b3348..89928ccf92f 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -120,6 +120,7 @@ int cmd_am(int argc, const char **argv, const char *prefix, struct repository *r\n int cmd_annotate(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_apply(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_archive(int argc, const char **argv, const char *prefix, struct repository *repo);\n+int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_bisect(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_blame(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_branch(int argc, const char **argv, const char *prefix, struct repository *repo);\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nnew file mode 100644\nindex 00000000000..38e6aaeaa03\n--- /dev/null\n+++ b/builtin/backfill.c\n@@ -0,0 +1,29 @@\n+#include \"builtin.h\"\n+#include \"config.h\"\n+#include \"parse-options.h\"\n+#include \"repository.h\"\n+#include \"object.h\"\n+\n+static const char * const builtin_backfill_usage[] = {\n+\tN_(\"git backfill []\"),\n+\tNULL\n+};\n+\n+int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n+{\n+\tstruct option options[] = {\n+\t\tOPT_END(),\n+\t};\n+\n+\tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n+\t\tusage_with_options(builtin_backfill_usage, options);\n+\n+\targc = parse_options(argc, argv, prefix, options, builtin_backfill_usage,\n+\t\t\t 0);\n+\n+\trepo_config(repo, git_default_config, NULL);\n+\n+\tdie(_(\"not implemented\"));\n+\n+\treturn 0;\n+}\ndiff --git a/command-list.txt b/command-list.txt\nindex e0bb87b3b5c..c537114b468 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -60,6 +60,7 @@ git-annotate ancillaryinterrogators\n git-apply plumbingmanipulators complete\n git-archimport foreignscminterface\n git-archive mainporcelain\n+git-backfill mainporcelain history\n git-bisect mainporcelain info\n git-blame ancillaryinterrogators complete\n git-branch mainporcelain history\ndiff --git a/git.c b/git.c\nindex 2fbea24ec92..00d9b3ec8a9 100644\n--- a/git.c\n+++ b/git.c\n@@ -509,6 +509,7 @@ static struct cmd_struct commands[] = {\n \t{ \"annotate\", cmd_annotate, RUN_SETUP },\n \t{ \"apply\", cmd_apply, RUN_SETUP_GENTLY },\n \t{ \"archive\", cmd_archive, RUN_SETUP_GENTLY },\n+\t{ \"backfill\", cmd_backfill, RUN_SETUP },\n \t{ \"bisect\", cmd_bisect, RUN_SETUP },\n \t{ \"blame\", cmd_blame, RUN_SETUP },\n \t{ \"branch\", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG },\n-- \ngitgitgadget\n\n"},{"id":"508805","messageId":"5728dd2702195b7ba3a208859f114e40ba2b6bbd.1733515638.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.git.1733515638.gitgitgadget@gmail.com","subject":"[PATCH 2/5] backfill: basic functionality and tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-06T20:07:15Z","receivedAt":"2024-12-06T20:07:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe default behavior of 'git backfill' is to fetch all missing blobs that\nare reachable from HEAD. Document and test this behavior.\n\nThe implementation is a very simple use of the path-walk API, initializing\nthe revision walk at HEAD to start the path-walk from all commits reachable\nfrom HEAD. Ignore the object arrays that correspond to tree entries,\nassuming that they are all present already.\n\nThe path-walk API provides lists of objects in batches according to a\ncommon path, but that list could be very small. We want to balance the\nnumber of requests to the server with the ability to have the process\ninterrupted with minimal repeated work to catch up in the next run.\nBased on some experiments (detailed in the next change) a minimum batch\nsize of 50,000 is selected for the default.\n\nThis batch size is a _minimum_. As the path-walk API emits lists of blob\nIDs, they are collected into a list of objects for a request to the\nserver. When that list is at least the minimum batch size, then the\nrequest is sent to the server for the new objects. However, the list of\nblob IDs from the path-walk API could be much longer than the batch\nsize. At this moment, it is unclear if there is a benefit to split the\nlist when there are too many objects at the same path.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 24 +++++\n Documentation/technical/api-path-walk.txt | 3 +-\n builtin/backfill.c | 104 +++++++++++++++++++++-\n t/t5620-backfill.sh | 94 +++++++++++++++++++\n 4 files changed, 221 insertions(+), 4 deletions(-)\n create mode 100755 t/t5620-backfill.sh\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 640144187d3..0e10f066fef 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -14,6 +14,30 @@ SYNOPSIS\n DESCRIPTION\n -----------\n \n+Blobless partial clones are created using `git clone --filter=blob:none`\n+and then configure the local repository such that the Git client avoids\n+downloading blob objects unless they are required for a local operation.\n+This initially means that the clone and later fetches download reachable\n+commits and trees but no blobs. Later operations that change the `HEAD`\n+pointer, such as `git checkout` or `git merge`, may need to download\n+missing blobs in order to complete their operation.\n+\n+In the worst cases, commands that compute blob diffs, such as `git blame`,\n+become very slow as they download the missing blobs in single-blob\n+requests to satisfy the missing object as the Git command needs it. This\n+leads to multiple download requests and no ability for the Git server to\n+provide delta compression across those objects.\n+\n+The `git backfill` command provides a way for the user to request that\n+Git downloads the missing blobs (with optional filters) such that the\n+missing blobs representing historical versions of files can be downloaded\n+in batches. The `backfill` command attempts to optimize the request by\n+grouping blobs that appear at the same path, hopefully leading to good\n+delta compression in the packfile sent by the server.\n+\n+By default, `git backfill` downloads all blobs reachable from the `HEAD`\n+commit. This set can be restricted or expanded using various options.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 7075d0d5ab5..1fba0ce04cb 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -60,4 +60,5 @@ Examples\n --------\n \n See example usages in:\n-\t`t/helper/test-path-walk.c`\n+\t`t/helper/test-path-walk.c`,\n+\t`builtin/backfill.c`\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 38e6aaeaa03..e5f2000d5e0 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -1,16 +1,116 @@\n #include \"builtin.h\"\n+#include \"git-compat-util.h\"\n #include \"config.h\"\n #include \"parse-options.h\"\n #include \"repository.h\"\n+#include \"commit.h\"\n+#include \"hex.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n #include \"object.h\"\n+#include \"object-store-ll.h\"\n+#include \"oid-array.h\"\n+#include \"oidset.h\"\n+#include \"promisor-remote.h\"\n+#include \"strmap.h\"\n+#include \"string-list.h\"\n+#include \"revision.h\"\n+#include \"trace2.h\"\n+#include \"progress.h\"\n+#include \"packfile.h\"\n+#include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n \tN_(\"git backfill []\"),\n \tNULL\n };\n \n+struct backfill_context {\n+\tstruct repository *repo;\n+\tstruct oid_array current_batch;\n+\tsize_t batch_size;\n+};\n+\n+static void clear_backfill_context(struct backfill_context *ctx)\n+{\n+\toid_array_clear(&ctx->current_batch);\n+}\n+\n+static void download_batch(struct backfill_context *ctx)\n+{\n+\tpromisor_remote_get_direct(ctx->repo,\n+\t\t\t\t ctx->current_batch.oid,\n+\t\t\t\t ctx->current_batch.nr);\n+\toid_array_clear(&ctx->current_batch);\n+\n+\t/*\n+\t * We likely have a new packfile. Add it to the packed list to\n+\t * avoid possible duplicate downloads of the same objects.\n+\t */\n+\treprepare_packed_git(ctx->repo);\n+}\n+\n+static int fill_missing_blobs(const char *path UNUSED,\n+\t\t\t struct oid_array *list,\n+\t\t\t enum object_type type,\n+\t\t\t void *data)\n+{\n+\tstruct backfill_context *ctx = data;\n+\n+\tif (type != OBJ_BLOB)\n+\t\treturn 0;\n+\n+\tfor (size_t i = 0; i < list->nr; i++) {\n+\t\toff_t size = 0;\n+\t\tstruct object_info info = OBJECT_INFO_INIT;\n+\t\tinfo.disk_sizep = &size;\n+\t\tif (oid_object_info_extended(ctx->repo,\n+\t\t\t\t\t &list->oid[i],\n+\t\t\t\t\t &info,\n+\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH) ||\n+\t\t !size)\n+\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n+\t}\n+\n+\tif (ctx->current_batch.nr >= ctx->batch_size)\n+\t\tdownload_batch(ctx);\n+\n+\treturn 0;\n+}\n+\n+static int do_backfill(struct backfill_context *ctx)\n+{\n+\tstruct rev_info revs;\n+\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n+\tint ret;\n+\n+\trepo_init_revisions(ctx->repo, &revs, \"\");\n+\thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n+\n+\tinfo.blobs = 1;\n+\tinfo.tags = info.commits = info.trees = 0;\n+\n+\tinfo.revs = &revs;\n+\tinfo.path_fn = fill_missing_blobs;\n+\tinfo.path_fn_data = ctx;\n+\n+\tret = walk_objects_by_path(&info);\n+\n+\t/* Download the objects that did not fill a batch. */\n+\tif (!ret)\n+\t\tdownload_batch(ctx);\n+\n+\tclear_backfill_context(ctx);\n+\treturn ret;\n+}\n+\n int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n {\n+\tstruct backfill_context ctx = {\n+\t\t.repo = repo,\n+\t\t.current_batch = OID_ARRAY_INIT,\n+\t\t.batch_size = 50000,\n+\t};\n \tstruct option options[] = {\n \t\tOPT_END(),\n \t};\n@@ -23,7 +123,5 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \n \trepo_config(repo, git_default_config, NULL);\n \n-\tdie(_(\"not implemented\"));\n-\n-\treturn 0;\n+\treturn do_backfill(&ctx);\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nnew file mode 100755\nindex 00000000000..64326362d80\n--- /dev/null\n+++ b/t/t5620-backfill.sh\n@@ -0,0 +1,94 @@\n+#!/bin/sh\n+\n+test_description='git backfill on partial clones'\n+\n+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main\n+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME\n+\n+. ./test-lib.sh\n+\n+# We create objects in the 'src' repo.\n+test_expect_success 'setup repo for object creation' '\n+\techo \"{print \\$1}\" >print_1.awk &&\n+\techo \"{print \\$2}\" >print_2.awk &&\n+\n+\tgit init src &&\n+\n+\tmkdir -p src/a/b/c &&\n+\tmkdir -p src/d/e &&\n+\n+\tfor i in 1 2\n+\tdo\n+\t\tfor n in 1 2 3 4\n+\t\tdo\n+\t\t\techo \"Version $i of file $n\" > src/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/$n\" > src/a/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/$n\" > src/a/b/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/c/$n\" > src/a/b/c/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/$n\" > src/d/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/e/$n\" > src/d/e/file.$n.txt &&\n+\t\t\tgit -C src add . &&\n+\t\t\tgit -C src commit -m \"Iteration $n\" || return 1\n+\t\tdone\n+\tdone\n+'\n+\n+# Clone 'src' into 'srv.bare' so we have a bare repo to be our origin\n+# server for the partial clone.\n+test_expect_success 'setup bare clone for server' '\n+\tgit clone --bare \"file://$(pwd)/src\" srv.bare &&\n+\tgit -C srv.bare config --local uploadpack.allowfilter 1 &&\n+\tgit -C srv.bare config --local uploadpack.allowanysha1inwant 1\n+'\n+\n+# do basic partial clone from \"srv.bare\"\n+test_expect_success 'do partial clone 1, backfill gets all objects' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill1 &&\n+\n+\t# Backfill with no options gets everything reachable from HEAD.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-file-trace\" git \\\n+\t\t-C backfill1 backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n+. \"$TEST_DIRECTORY\"/lib-httpd.sh\n+start_httpd\n+\n+test_expect_success 'create a partial clone over HTTP' '\n+\tSERVER=\"$HTTPD_DOCUMENT_ROOT_PATH/server\" &&\n+\trm -rf \"$SERVER\" repo &&\n+\tgit clone --bare \"file://$(pwd)/src\" \"$SERVER\" &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowfilter 1 &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowanysha1inwant 1 &&\n+\n+\tgit clone --no-checkout --filter=blob:none \\\n+\t\t\"$HTTPD_URL/smart/server\" backfill-http\n+'\n+\n+test_expect_success 'backfilling over HTTP succeeds' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-http-trace\" git \\\n+\t\t-C backfill-http backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 rev-list-out &&\n+\tawk \"{print \\$1;}\" oids &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/walk-trace\" git -C backfill-http \\\n+\t\tcat-file --batch-check batch-out &&\n+\t! grep missing batch-out\n+'\n+\n+# DO NOT add non-httpd-specific tests here, because the last part of this\n+# test script is only executed when httpd is available and enabled.\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"508806","messageId":"3cfd23073a036ea426569769b3e31290076257a6.1733515638.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.git.1733515638.gitgitgadget@gmail.com","subject":"[PATCH 3/5] backfill: add --batch-size= option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-06T20:07:16Z","receivedAt":"2024-12-06T20:07:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nUsers may want to specify a minimum batch size for their needs. This is only\na minimum: the path-walk API provides a list of OIDs that correspond to the\nsame path, and thus it is optimal to allow delta compression across those\nobjects in a single server request.\n\nWe could consider limiting the request to have a maximum batch size in the\nfuture. For now, we let the path-walk API batches determine the\nboundaries.\n\nTo get a feeling for the value of specifying the --batch-size parameter,\nI tested a number of open source repositories available on GitHub. The\nprocedure was generally:\n\n 1. git clone --filter=blob:none \n 2. git backfill\n\nChecking the number of packfiles and the size of the .git/objects/pack\ndirectory helps to identify the effects of different batch sizes.\n\nFor the Git repository, we get these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|-------|\n| (Initial clone) | 2 | 119 MB | |\n| 25K | 8 | 290 MB | 24s |\n| 50K | 5 | 290 MB | 24s |\n| 100K | 4 | 290 MB | 29s |\n\nOther than the packfile counts decreasing as we need fewer batches, the\nsize and time required is not changing much for this small example.\n\nFor the nodejs/node repository, we see these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 330 MB | |\n| 25K | 19 | 1,222 MB | 1m 22s |\n| 50K | 11 | 1,221 MB | 1m 24s |\n| 100K | 7 | 1,223 MB | 1m 40s |\n| 250K | 4 | 1,224 MB | 2m 23s |\n| 500K | 3 | 1,216 MB | 4m 38s |\n\nHere, we don't have much difference in the size of the repo, though the\n500K batch size results in a few MB gained. That comes at a cost of a\nmuch longer time. This extra time is due to server-side delta\ncompression happening as the on-disk deltas don't appear to be reusable\nall the time. But for smaller batch sizes, the server is able to find\nreasonable deltas partly because we are asking for objects that appear\nin the same region of the directory tree and include all versions of a\nfile at a specific path.\n\nTo contrast this example, I tested the microsoft/fluentui repo, which\nhas been known to have inefficient packing due to name hash collisions.\nThese results are found before GitHub had the opportunity to repack the\nserver with more advanced name hash versions:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 105 MB | |\n| 5K | 53 | 348 MB | 2m 26s |\n| 10K | 28 | 365 MB | 2m 22s |\n| 15K | 19 | 407 MB | 2m 21s |\n| 20K | 15 | 393 MB | 2m 28s |\n| 25K | 13 | 417 MB | 2m 06s |\n| 50K | 8 | 509 MB | 1m 34s |\n| 100K | 5 | 535 MB | 1m 56s |\n| 250K | 4 | 698 MB | 1m 33s |\n| 500K | 3 | 696 MB | 1m 42s |\n\nHere, a larger variety of batch sizes were chosen because of the great\nvariation in results. By asking the server to download small batches\ncorresponding to fewer paths at a time, the server is able to provide\nbetter compression for these batches than it would for a regular clone.\nA typical full clone for this repository would require 738 MB.\n\nThis example justifies the choice to batch requests by path name,\nleading to improved communication with a server that is not optimally\npacked.\n\nFinally, the same experiment for the Linux repository had these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|---------|\n| (Initial clone) | 2 | 2,153 MB | |\n| 25K | 63 | 6,380 MB | 14m 08s |\n| 50K | 58 | 6,126 MB | 15m 11s |\n| 100K | 30 | 6,135 MB | 18m 11s |\n| 250K | 14 | 6,146 MB | 18m 22s |\n| 500K | 8 | 6,143 MB | 33m 29s |\n\nEven in this example, where the default name hash algorithm leads to\ndecent compression of the Linux kernel repository, there is value for\nselecting a smaller batch size, to a limit. The 25K batch size has the\nfastest time, but uses 250 MB more than the 50K batch size. The 500K\nbatch size took much more time due to server compression time and thus\nwe should avoid large batch sizes like this.\n\nBased on these experiments, a batch size of 50,000 was chosen as the\ndefault value.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 10 +++++++++-\n builtin/backfill.c | 4 +++-\n t/t5620-backfill.sh | 18 ++++++++++++++++++\n 3 files changed, 30 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 0e10f066fef..9b0bae04e9d 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [verse]\n-'git backfill' []\n+'git backfill' [--batch-size=]\n \n DESCRIPTION\n -----------\n@@ -38,6 +38,14 @@ delta compression in the packfile sent by the server.\n By default, `git backfill` downloads all blobs reachable from the `HEAD`\n commit. This set can be restricted or expanded using various options.\n \n+OPTIONS\n+-------\n+\n+--batch-size=::\n+\tSpecify a minimum size for a batch of missing objects to request\n+\tfrom the server. This size may be exceeded by the last set of\n+\tblobs seen at a given path. Default batch size is 16,000.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex e5f2000d5e0..127333daef8 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -21,7 +21,7 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill []\"),\n+\tN_(\"git backfill [--batch-size=]\"),\n \tNULL\n };\n \n@@ -112,6 +112,8 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \t\t.batch_size = 50000,\n \t};\n \tstruct option options[] = {\n+\t\tOPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n+\t\t\t N_(\"Minimun number of objects to request at a time\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 64326362d80..32e2bb1c132 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -59,6 +59,24 @@ test_expect_success 'do partial clone 1, backfill gets all objects' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'do partial clone 2, backfill batch size' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill2 &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/batch-trace\" git \\\n+\t\t-C backfill2 backfill --batch-size=20 &&\n+\n+\t# Batches were used\n+\ttest_trace2_data promisor fetch_count 20 matches &&\n+\ttest_line_count = 2 matches &&\n+\ttest_trace2_data promisor fetch_count 8 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \n-- \ngitgitgadget\n\n"},{"id":"508808","messageId":"19a8efebbad7f414e3ef3fdca612dc1fcb835f25.1733515638.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.git.1733515638.gitgitgadget@gmail.com","subject":"[PATCH 4/5] backfill: add --sparse option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-06T20:07:17Z","receivedAt":"2024-12-06T20:07:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nOne way to significantly reduce the cost of a Git clone and later fetches is\nto use a blobless partial clone and combine that with a sparse-checkout that\nreduces the paths that need to be populated in the working directory. Not\nonly does this reduce the cost of clones and fetches, the sparse-checkout\nreduces the number of objects needed to download from a promisor remote.\n\nHowever, history investigations can be expensie as computing blob diffs will\ntrigger promisor remote requests for one object at a time. This can be\navoided by downloading the blobs needed for the given sparse-checkout using\n'git backfill' and its new '--sparse' mode, at a time that the user is\nwilling to pay that extra cost.\n\nNote that this is distinctly different from the '--filter=sparse:'\noption, as this assumes that the partial clone has all reachable trees and\nwe are using client-side logic to avoid downloading blobs outside of the\nsparse-checkout cone. This avoids the server-side cost of walking trees\nwhile also achieving a similar goal. It also downloads in batches based on\nsimilar path names, presenting a resumable download if things are\ninterrupted.\n\nThis augments the path-walk API to have a possibly-NULL 'pl' member that may\npoint to a 'struct pattern_list'. This could be more general than the\nsparse-checkout definition at HEAD, but 'git backfill --sparse' is currently\nthe only consumer.\n\nBe sure to test this in both cone mode and not cone mode. Cone mode has the\nbenefit that the path-walk can skip certain paths once they would expand\nbeyond the sparse-checkout.\n\nTo test this, we can create a blobless sparse clone, expand the\nsparse-checkout slightly, and then run 'git backfill --sparse' to see\nhow much data is downloaded. The general steps are\n\n 1. git clone --filter=blob:none --sparse \n 2. git sparse-checkout set ... \n 3. git backfill --sparse\n\nFor the Git repository with the 'builtin' directory in the\nsparse-checkout, we get these results for various batch sizes:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|-------|\n| (Initial clone) | 3 | 110 MB | |\n| 10K | 12 | 192 MB | 17.2s |\n| 15K | 9 | 192 MB | 15.5s |\n| 20K | 8 | 192 MB | 15.5s |\n| 25K | 7 | 192 MB | 14.7s |\n\nThis case matters less because a full clone of the Git repository from\nGitHub is currently at 277 MB.\n\nUsing a copy of the Linux repository with the 'kernel/' directory in the\nsparse-checkout, we get these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|------|\n| (Initial clone) | 2 | 1,876 MB | |\n| 10K | 11 | 2,187 MB | 46s |\n| 25K | 7 | 2,188 MB | 43s |\n| 50K | 5 | 2,194 MB | 44s |\n| 100K | 4 | 2,194 MB | 48s |\n\nThis case is more meaningful because a full clone of the Linux\nrepository is currently over 6 GB, so this is a valuable way to download\na fraction of the repository and no longer need network access for all\nreachable objects within the sparse-checkout.\n\nChoosing a batch size will depend on a lot of factors, including the\nuser's network speed or reliability, the repository's file structure,\nand how many versions there are of the file within the sparse-checkout\nscope. There will not be a one-size-fits-all solution.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 6 ++-\n Documentation/technical/api-path-walk.txt | 8 ++++\n builtin/backfill.c | 13 +++++-\n dir.c | 10 ++---\n dir.h | 3 ++\n path-walk.c | 18 ++++++++\n path-walk.h | 11 +++++\n t/helper/test-path-walk.c | 22 ++++++++-\n t/t5620-backfill.sh | 55 +++++++++++++++++++++++\n t/t6601-path-walk.sh | 32 +++++++++++++\n 10 files changed, 168 insertions(+), 10 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 9b0bae04e9d..ecf2ac428ce 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [verse]\n-'git backfill' [--batch-size=]\n+'git backfill' [--batch-size=] [--[no-]sparse]\n \n DESCRIPTION\n -----------\n@@ -46,6 +46,10 @@ OPTIONS\n \tfrom the server. This size may be exceeded by the last set of\n \tblobs seen at a given path. Default batch size is 16,000.\n \n+--[no-]sparse::\n+\tOnly download objects if they appear at a path that matches the\n+\tcurrent sparse-checkout.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 1fba0ce04cb..3e089211fb4 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -56,6 +56,14 @@ better off using the revision walk API instead.\n \tthe revision walk so that the walk emits commits marked with the\n \t`UNINTERESTING` flag.\n \n+`pl`::\n+\tThis pattern list pointer allows focusing the path-walk search to\n+\ta set of patterns, only emitting paths that match the given\n+\tpatterns. See linkgit:gitignore[5] or\n+\tlinkgit:git-sparse-checkout[1] for details about pattern lists.\n+\tWhen the pattern list uses cone-mode patterns, then the path-walk\n+\tAPI can prune the set of paths it walks to improve performance.\n+\n Examples\n --------\n \ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 127333daef8..cdee87e38af 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"repository.h\"\n #include \"commit.h\"\n+#include \"dir.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -21,7 +22,7 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill [--batch-size=]\"),\n+\tN_(\"git backfill [--batch-size=] [--[no-]sparse]\"),\n \tNULL\n };\n \n@@ -29,6 +30,7 @@ struct backfill_context {\n \tstruct repository *repo;\n \tstruct oid_array current_batch;\n \tsize_t batch_size;\n+\tint sparse;\n };\n \n static void clear_backfill_context(struct backfill_context *ctx)\n@@ -84,6 +86,12 @@ static int do_backfill(struct backfill_context *ctx)\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tint ret;\n \n+\tif (ctx->sparse) {\n+\t\tCALLOC_ARRAY(info.pl, 1);\n+\t\tif (get_sparse_checkout_patterns(info.pl))\n+\t\t\treturn error(_(\"problem loading sparse-checkout\"));\n+\t}\n+\n \trepo_init_revisions(ctx->repo, &revs, \"\");\n \thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n \n@@ -110,10 +118,13 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \t\t.repo = repo,\n \t\t.current_batch = OID_ARRAY_INIT,\n \t\t.batch_size = 50000,\n+\t\t.sparse = 0,\n \t};\n \tstruct option options[] = {\n \t\tOPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n \t\t\t N_(\"Minimun number of objects to request at a time\")),\n+\t\tOPT_BOOL(0, \"sparse\", &ctx.sparse,\n+\t\t\t N_(\"Restrict the missing objects to the current sparse-checkout\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/dir.c b/dir.c\nindex c43b5e30813..32af7ee294d 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -1088,10 +1088,6 @@ static void invalidate_directory(struct untracked_cache *uc,\n \t\tdir->dirs[i]->recurse = 0;\n }\n \n-static int add_patterns_from_buffer(char *buf, size_t size,\n-\t\t\t\t const char *base, int baselen,\n-\t\t\t\t struct pattern_list *pl);\n-\n /* Flags for add_patterns() */\n #define PATTERN_NOFOLLOW (1<<0)\n \n@@ -1181,9 +1177,9 @@ static int add_patterns(const char *fname, const char *base, int baselen,\n \treturn 0;\n }\n \n-static int add_patterns_from_buffer(char *buf, size_t size,\n-\t\t\t\t const char *base, int baselen,\n-\t\t\t\t struct pattern_list *pl)\n+int add_patterns_from_buffer(char *buf, size_t size,\n+\t\t\t const char *base, int baselen,\n+\t\t\t struct pattern_list *pl)\n {\n \tchar *orig = buf;\n \tint i, lineno = 1;\ndiff --git a/dir.h b/dir.h\nindex a3a2f00f5d9..6cfef5df660 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -467,6 +467,9 @@ void add_patterns_from_file(struct dir_struct *, const char *fname);\n int add_patterns_from_blob_to_list(struct object_id *oid,\n \t\t\t\t const char *base, int baselen,\n \t\t\t\t struct pattern_list *pl);\n+int add_patterns_from_buffer(char *buf, size_t size,\n+\t\t\t const char *base, int baselen,\n+\t\t\t struct pattern_list *pl);\n void parse_path_pattern(const char **string, int *patternlen, unsigned *flags, int *nowildcardlen);\n void add_pattern(const char *string, const char *base,\n \t\t int baselen, struct pattern_list *pl, int srcpos);\ndiff --git a/path-walk.c b/path-walk.c\nindex b31924df52e..47809f8c315 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -12,6 +12,7 @@\n #include \"object.h\"\n #include \"oid-array.h\"\n #include \"prio-queue.h\"\n+#include \"repository.h\"\n #include \"revision.h\"\n #include \"string-list.h\"\n #include \"strmap.h\"\n@@ -166,6 +167,23 @@ static int add_children(struct path_walk_context *ctx,\n \t\tif (type == OBJ_TREE)\n \t\t\tstrbuf_addch(&path, '/');\n \n+\t\tif (ctx->info->pl) {\n+\t\t\tint dtype;\n+\t\t\tenum pattern_match_result match;\n+\t\t\tmatch = path_matches_pattern_list(path.buf, path.len,\n+\t\t\t\t\t\t\t path.buf + base_len, &dtype,\n+\t\t\t\t\t\t\t ctx->info->pl,\n+\t\t\t\t\t\t\t ctx->repo->index);\n+\n+\t\t\tif (ctx->info->pl->use_cone_patterns &&\n+\t\t\t match == NOT_MATCHED)\n+\t\t\t\tcontinue;\n+\t\t\telse if (!ctx->info->pl->use_cone_patterns &&\n+\t\t\t\t type == OBJ_BLOB &&\n+\t\t\t\t match != MATCHED)\n+\t\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) {\n \t\t\tCALLOC_ARRAY(list, 1);\n \t\t\tlist->type = type;\ndiff --git a/path-walk.h b/path-walk.h\nindex de0db007dc9..0961f67bc9d 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -6,6 +6,7 @@\n \n struct rev_info;\n struct oid_array;\n+struct pattern_list;\n \n /**\n * The type of a function pointer for the method that is called on a list of\n@@ -47,6 +48,16 @@ struct path_walk_info {\n \t * walk the children of such trees.\n \t */\n \tint prune_all_uninteresting;\n+\n+\t/**\n+\t * Specify a sparse-checkout definition to match our paths to. Do not\n+\t * walk outside of this sparse definition. If the patterns are in\n+\t * cone mode, then the search may prune directories that are outside\n+\t * of the cone. If not in cone mode, then all tree paths will be\n+\t * explored but the path_fn will only be called when the path matches\n+\t * the sparse-checkout patterns.\n+\t */\n+\tstruct pattern_list *pl;\n };\n \n #define PATH_WALK_INFO_INIT { \\\ndiff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\nindex 7f2d409c5bc..61e845e5ec2 100644\n--- a/t/helper/test-path-walk.c\n+++ b/t/helper/test-path-walk.c\n@@ -1,6 +1,7 @@\n #define USE_THE_REPOSITORY_VARIABLE\n \n #include \"test-tool.h\"\n+#include \"dir.h\"\n #include \"environment.h\"\n #include \"hex.h\"\n #include \"object-name.h\"\n@@ -9,6 +10,7 @@\n #include \"revision.h\"\n #include \"setup.h\"\n #include \"parse-options.h\"\n+#include \"strbuf.h\"\n #include \"path-walk.h\"\n #include \"oid-array.h\"\n \n@@ -65,7 +67,7 @@ static int emit_block(const char *path, struct oid_array *oids,\n \n int cmd__path_walk(int argc, const char **argv)\n {\n-\tint res;\n+\tint res, stdin_pl = 0;\n \tstruct rev_info revs = REV_INFO_INIT;\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tstruct path_walk_test_data data = { 0 };\n@@ -80,6 +82,8 @@ int cmd__path_walk(int argc, const char **argv)\n \t\t\t N_(\"toggle inclusion of tree objects\")),\n \t\tOPT_BOOL(0, \"prune\", &info.prune_all_uninteresting,\n \t\t\t N_(\"toggle pruning of uninteresting paths\")),\n+\t\tOPT_BOOL(0, \"stdin-pl\", &stdin_pl,\n+\t\t\t N_(\"read a pattern list over stdin\")),\n \t\tOPT_END(),\n \t};\n \n@@ -99,6 +103,17 @@ int cmd__path_walk(int argc, const char **argv)\n \tinfo.path_fn = emit_block;\n \tinfo.path_fn_data = &data;\n \n+\tif (stdin_pl) {\n+\t\tstruct strbuf in = STRBUF_INIT;\n+\t\tCALLOC_ARRAY(info.pl, 1);\n+\n+\t\tinfo.pl->use_cone_patterns = 1;\n+\n+\t\tstrbuf_fread(&in, 2048, stdin);\n+\t\tadd_patterns_from_buffer(in.buf, in.len, \"\", 0, info.pl);\n+\t\tstrbuf_release(&in);\n+\t}\n+\n \tres = walk_objects_by_path(&info);\n \n \tprintf(\"commits:%\" PRIuMAX \"\\n\"\n@@ -107,6 +122,11 @@ int cmd__path_walk(int argc, const char **argv)\n \t \"tags:%\" PRIuMAX \"\\n\",\n \t data.commit_nr, data.tree_nr, data.blob_nr, data.tag_nr);\n \n+\tif (info.pl) {\n+\t\tclear_pattern_list(info.pl);\n+\t\tfree(info.pl);\n+\t}\n+\n \trelease_revisions(&revs);\n \treturn res;\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 32e2bb1c132..c2acd1339bd 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -77,6 +77,61 @@ test_expect_success 'do partial clone 2, backfill batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse' '\n+\tgit clone --sparse --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill3 &&\n+\n+\t# Initial checkout includes four files at root.\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 44 missing &&\n+\n+\t# Initial sparse-checkout is just the files at root, so we get the\n+\t# older versions of the four files at tip.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace1\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 4 missing &&\n+\ttest_line_count = 40 missing &&\n+\n+\t# Expand the sparse-checkout to include 'd' recursively. This\n+\t# engages the algorithm to skip the trees for 'a'. Note that\n+\t# the \"sparse-checkout set\" command downloads the objects at tip\n+\t# to satisfy the current checkout.\n+\tgit -C backfill3 sparse-checkout set d &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace2\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 8 missing &&\n+\ttest_line_count = 24 missing\n+'\n+\n+test_expect_success 'backfill --sparse without cone mode' '\n+\tgit clone --no-checkout --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill4 &&\n+\n+\t# No blobs yet\n+\tgit -C backfill4 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 48 missing &&\n+\n+\t# Define sparse-checkout by filename regardless of parent directory.\n+\t# This downloads 6 blobs to satisfy the checkout.\n+\tgit -C backfill4 sparse-checkout set --no-cone \"**/file.1.txt\" &&\n+\tgit -C backfill4 checkout main &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/no-cone-trace1\" git \\\n+\t\t-C backfill4 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 6 missing &&\n+\ttest_line_count = 36 missing\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \ndiff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh\nindex 7d765ffe907..538e2ed297f 100755\n--- a/t/t6601-path-walk.sh\n+++ b/t/t6601-path-walk.sh\n@@ -176,6 +176,38 @@ test_expect_success 'branches and indexed objects mix well' '\n \ttest_cmp_sorted expect out\n '\n \n+test_expect_success 'base & topic, sparse' '\n+\tcat >patterns <<-EOF &&\n+\t/*\n+\t!/*/\n+\t/left/\n+\tEOF\n+\n+\ttest-tool path-walk --stdin-pl -- base topic out &&\n+\n+\tcat >expect <<-EOF &&\n+\t0:commit::$(git rev-parse topic)\n+\t0:commit::$(git rev-parse base)\n+\t0:commit::$(git rev-parse base~1)\n+\t0:commit::$(git rev-parse base~2)\n+\t1:tree::$(git rev-parse topic^{tree})\n+\t1:tree::$(git rev-parse base^{tree})\n+\t1:tree::$(git rev-parse base~1^{tree})\n+\t1:tree::$(git rev-parse base~2^{tree})\n+\t2:blob:a:$(git rev-parse base~2:a)\n+\t3:tree:left/:$(git rev-parse base:left)\n+\t3:tree:left/:$(git rev-parse base~2:left)\n+\t4:blob:left/b:$(git rev-parse base~2:left/b)\n+\t4:blob:left/b:$(git rev-parse base:left/b)\n+\tblobs:3\n+\tcommits:4\n+\ttags:0\n+\ttrees:6\n+\tEOF\n+\n+\ttest_cmp_sorted expect out\n+'\n+\n test_expect_success 'topic only' '\n \ttest-tool path-walk -- topic >out &&\n \n-- \ngitgitgadget\n\n"},{"id":"508807","messageId":"35a7e4ec4d376ae57bf181b74f26ff67e1b1ac69.1733515638.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.git.1733515638.gitgitgadget@gmail.com","subject":"[PATCH 5/5] backfill: assume --sparse when sparse-checkout is enabled","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-06T20:07:18Z","receivedAt":"2024-12-06T20:07:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change introduced the '--[no-]sparse' option for the 'git\nbackfill' command, but did not assume it as enabled by default. However,\nthis is likely the behavior that users will most often want to happen.\nWithout this default, users with a small sparse-checkout may be confused\nwhen 'git backfill' downloads every version of every object in the full\nhistory.\n\nHowever, this is left as a separate change so this decision can be reviewed\nindependently of the value of the '--[no-]sparse' option.\n\nAdd a test of adding the '--sparse' option to a repo without sparse-checkout\nto make it clear that supplying it without a sparse-checkout is an error.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 3 ++-\n builtin/backfill.c | 7 +++++++\n t/t5620-backfill.sh | 13 ++++++++++++-\n 3 files changed, 21 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex ecf2ac428ce..066ec6b161a 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -48,7 +48,8 @@ OPTIONS\n \n --[no-]sparse::\n \tOnly download objects if they appear at a path that matches the\n-\tcurrent sparse-checkout.\n+\tcurrent sparse-checkout. If the sparse-checkout feature is enabled,\n+\tthen `--sparse` is assumed and can be disabled with `--no-sparse`.\n \n SEE ALSO\n --------\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex cdee87e38af..225764f17e8 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -1,3 +1,6 @@\n+/* We need this macro to access core_apply_sparse_checkout */\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n #include \"builtin.h\"\n #include \"git-compat-util.h\"\n #include \"config.h\"\n@@ -5,6 +8,7 @@\n #include \"repository.h\"\n #include \"commit.h\"\n #include \"dir.h\"\n+#include \"environment.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -136,5 +140,8 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \n \trepo_config(repo, git_default_config, NULL);\n \n+\tif (ctx.sparse < 0)\n+\t\tctx.sparse = core_apply_sparse_checkout;\n+\n \treturn do_backfill(&ctx);\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex c2acd1339bd..eecf03d5199 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -77,6 +77,12 @@ test_expect_success 'do partial clone 2, backfill batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse without sparse-checkout fails' '\n+\tgit init not-sparse &&\n+\ttest_must_fail git -C not-sparse backfill --sparse 2>err &&\n+\tgrep \"problem loading sparse-checkout\" err\n+'\n+\n test_expect_success 'backfill --sparse' '\n \tgit clone --sparse --filter=blob:none\t\t\\\n \t\t--single-branch --branch=main \t\t\\\n@@ -105,7 +111,12 @@ test_expect_success 'backfill --sparse' '\n \ttest_trace2_data promisor fetch_count 8 missing &&\n-\ttest_line_count = 24 missing\n+\ttest_line_count = 24 missing &&\n+\n+\t# Disabling the --sparse option (on by default) will download everything\n+\tgit -C backfill3 backfill --no-sparse &&\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 0 missing\n '\n \n test_expect_success 'backfill --sparse without cone mode' '\n-- \ngitgitgadget\n"},{"id":"508835","messageId":"xmqqy10qqwco.fsf@gitster.g","threadId":"62610","inReplyTo":"pull.1820.git.1733515638.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-12-08T10:53:43Z","receivedAt":"2024-12-08T10:53:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"It seems that the result of calling init_revisions() from backfill\nis leaked?\n\nhttps://github.com/git/git/actions/runs/12218430154/job/34083929479 \n\nI did not dig further but the below is from my local leaksanitizer\nrun.\n\nThanks.\n\n=================================================================\n==git==182342==ERROR: LeakSanitizer: detected memory leaks\n\nDirect leak of 576 byte(s) in 1 object(s) allocated from:\n #0 0x55d4b0e42915 in __interceptor_realloc (git+0x84915) (BuildId: c861e65ec43b0a3ef46b9555a81d6ddfc2358e8e)\n #1 0x55d4b119ce6d in xrealloc wrapper.c:140:8\n #2 0x55d4b11204d4 in add_rev_cmdline revision.c:1563:2\n #3 0x55d4b11187a1 in handle_revision_arg_1 revision.c:2263:2\n #4 0x55d4b1118398 in handle_revision_arg revision.c:2275:12\n #5 0x55d4b0e5233b in do_backfill builtin/backfill.c:100:2\n #6 0x55d4b0e52253 in cmd_backfill builtin/backfill.c:146:9\n #7 0x55d4b0e46b80 in run_builtin git.c:480:11\n #8 0x55d4b0e45502 in handle_builtin git.c:741:9\n #9 0x55d4b0e4649c in run_argv git.c:808:4\n #10 0x55d4b0e45274 in cmd_main git.c:948:19\n #11 0x55d4b0f6da8a in main common-main.c:9:11\n #12 0x7ff25f97ac89 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16\n #13 0x7ff25f97ad44 in __libc_start_main csu/../csu/libc-start.c:360:3\n #14 0x55d4b0e171e0 in _start (git+0x591e0) (BuildId: c861e65ec43b0a3ef46b9555a81d6ddfc2358e8e)\n\nDEDUP_TOKEN: __interceptor_realloc--xrealloc--add_rev_cmdline--handle_revision_arg_1--handle_revision_arg--do_backfill--cmd_backfill--run_builtin--handle_builtin--run_argv--cmd_main--main--__libc_start_call_main--__libc_start_main--_start\nIndirect leak of 5 byte(s) in 1 object(s) allocated from:\n #0 0x55d4b0e424b6 in __interceptor_malloc (git+0x844b6) (BuildId: c861e65ec43b0a3ef46b9555a81d6ddfc2358e8e)\n #1 0x7ff25f9f34f9 in strdup string/strdup.c:42:15\n #2 0x55d4b119cb14 in xstrdup wrapper.c:43:14\n #3 0x55d4b1120506 in add_rev_cmdline revision.c:1565:23\n #4 0x55d4b11187a1 in handle_revision_arg_1 revision.c:2263:2\n #5 0x55d4b1118398 in handle_revision_arg revision.c:2275:12\n #6 0x55d4b0e5233b in do_backfill builtin/backfill.c:100:2\n #7 0x55d4b0e52253 in cmd_backfill builtin/backfill.c:146:9\n #8 0x55d4b0e46b80 in run_builtin git.c:480:11\n #9 0x55d4b0e45502 in handle_builtin git.c:741:9\n #10 0x55d4b0e4649c in run_argv git.c:808:4\n #11 0x55d4b0e45274 in cmd_main git.c:948:19\n #12 0x55d4b0f6da8a in main common-main.c:9:11\n #13 0x7ff25f97ac89 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16\n #14 0x7ff25f97ad44 in __libc_start_main csu/../csu/libc-start.c:360:3\n #15 0x55d4b0e171e0 in _start (git+0x591e0) (BuildId: c861e65ec43b0a3ef46b9555a81d6ddfc2358e8e)\n\nDEDUP_TOKEN: __interceptor_malloc--strdup--xstrdup--add_rev_cmdline--handle_revision_arg_1--handle_revision_arg--do_backfill--cmd_backfill--run_builtin--handle_builtin--run_argv--cmd_main--main--__libc_start_call_main--__libc_start_main--_start\nSUMMARY: LeakSanitizer: 581 byte(s) leaked in 2 allocation(s).\nOur logs revealed a memory leak...\n++ rmdir /home/gitster/w/git.git/t/test-results/t5620-backfill.leak\n++ :\n++ exit 134\n++ eval_ret=134\n"},{"id":"508840","messageId":"xmqqjzc9r8xs.fsf@gitster.g","threadId":"62610","inReplyTo":"xmqqy10qqwco.fsf@gitster.g","subject":"Re: [PATCH 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-12-09T00:34:07Z","receivedAt":"2024-12-09T00:34:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> It seems that the result of calling init_revisions() from backfill\n> is leaked?\n>\n> https://github.com/git/git/actions/runs/12218430154/job/34083929479 \n>\n> I did not dig further but the below is from my local leaksanitizer\n> run.\n\nThe attached patch seems to plug the leaks observed by your backfill\ntests. If you agree with the implementation of the change, you are\nwelcome to squash it in. I may be missing a better mechanism in the\npath-walk API that I could use to plug the leaks, in which case, of\ncourse a fix using such a better mechanism is very much welcomed.\n\nA few things I noticed about path-walk API during my poking are:\n\n - struct path_walk_info has PATH_WALK_INFO_INIT() macro, but not a\n matching path_walk_info_init() helper function to help initialize\n any heap-allocated instances. In general, anything that requires\n _INIT() macro by definition wants to be initialized with more\n than nul-initialized (otherwise, it would be fine to leave it\n uninitialized in the BSS, clear with = {0} initialization on the\n stack), so lack of matching path_walk_info_init() raises an\n eyebrow.\n\n - struct path_walk_info seems to lack a destructor. In general,\n anything complex enough to require initializer should have one.\n\n - lack of destructor for path_walk_info requires users to release\n resources held by \"struct pattern_list\" instance at pwi.pl; if we\n had a destructor, we wouldn't have 2 of the three leaks we had to\n fix here.\n\nThanks.\n\n\ndiff --git c/builtin/backfill.c w/builtin/backfill.c\nindex 225764f17e..1cf2df9303 100644\n--- c/builtin/backfill.c\n+++ w/builtin/backfill.c\n@@ -92,8 +92,11 @@ static int do_backfill(struct backfill_context *ctx)\n \n \tif (ctx->sparse) {\n \t\tCALLOC_ARRAY(info.pl, 1);\n-\t\tif (get_sparse_checkout_patterns(info.pl))\n+\t\tif (get_sparse_checkout_patterns(info.pl)) {\n+\t\t\tclear_pattern_list(info.pl);\n+\t\t\tfree(info.pl);\n \t\t\treturn error(_(\"problem loading sparse-checkout\"));\n+\t\t}\n \t}\n \n \trepo_init_revisions(ctx->repo, &revs, \"\");\n@@ -113,6 +116,11 @@ static int do_backfill(struct backfill_context *ctx)\n \t\tdownload_batch(ctx);\n \n \tclear_backfill_context(ctx);\n+\trelease_revisions(&revs);\n+\tif (info.pl) {\n+\t\tclear_pattern_list(info.pl);\n+\t\tfree(info.pl);\n+\t}\n \treturn ret;\n }\n \n\n"},{"id":"509141","messageId":"Z1_eTHk6IEJ0BEEg@pks.im","threadId":"62610","inReplyTo":"3cfd23073a036ea426569769b3e31290076257a6.1733515638.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/5] backfill: add --batch-size= option","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-12-16T08:01:16Z","receivedAt":"2024-12-16T08:01:37Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 06, 2024 at 08:07:16PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> Users may want to specify a minimum batch size for their needs. This is only\n> a minimum: the path-walk API provides a list of OIDs that correspond to the\n> same path, and thus it is optimal to allow delta compression across those\n> objects in a single server request.\n\nOkay, here you explicitly say that this is a minimum batch size, so this\nis by design and with a proper reason. Good.\n\n> We could consider limiting the request to have a maximum batch size in the\n> future. For now, we let the path-walk API batches determine the\n> boundaries.\n\nShould we maybe rename `--batch-size` to `--min-batch-size` so that it\ndoes not become awkward if we ever want to have a maximum batch size, as\nwell? Also helps to set expectations with the user.\n\n[snip]\n> Based on these experiments, a batch size of 50,000 was chosen as the\n> default value.\n\nThanks for all the data, this is really helpful!\n\n> diff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\n> index 0e10f066fef..9b0bae04e9d 100644\n> --- a/Documentation/git-backfill.txt\n> +++ b/Documentation/git-backfill.txt\n> @@ -38,6 +38,14 @@ delta compression in the packfile sent by the server.\n> By default, `git backfill` downloads all blobs reachable from the `HEAD`\n> commit. This set can be restricted or expanded using various options.\n> \n> +OPTIONS\n> +-------\n> +\n> +--batch-size=::\n> +\tSpecify a minimum size for a batch of missing objects to request\n> +\tfrom the server. This size may be exceeded by the last set of\n> +\tblobs seen at a given path. Default batch size is 16,000.\n\nThis is stale: s/16,000/50,000/\n\n> diff --git a/builtin/backfill.c b/builtin/backfill.c\n> index e5f2000d5e0..127333daef8 100644\n> --- a/builtin/backfill.c\n> +++ b/builtin/backfill.c\n> @@ -112,6 +112,8 @@ int cmd_backfill(int argc, const char **argv, const char *prefix,\n> struct reposit\n> .batch_size = 50000,\n> };\n> struct option options[] = {\n> + OPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n> + N_(\"Minimun number of objects to request at a time\")),\n\ns/Minimun/Minimum\n\nPatrick\n"},{"id":"509142","messageId":"Z1_eUSGN3B13uGmM@pks.im","threadId":"62610","inReplyTo":"5728dd2702195b7ba3a208859f114e40ba2b6bbd.1733515638.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/5] backfill: basic functionality and tests","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-12-16T08:01:21Z","receivedAt":"2024-12-16T08:01:41Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 06, 2024 at 08:07:15PM +0000, Derrick Stolee via GitGitGadget wrote:\n> diff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\n> index 640144187d3..0e10f066fef 100644\n> --- a/Documentation/git-backfill.txt\n> +++ b/Documentation/git-backfill.txt\n> @@ -14,6 +14,30 @@ SYNOPSIS\n> DESCRIPTION\n> -----------\n> \n> +Blobless partial clones are created using `git clone --filter=blob:none`\n> +and then configure the local repository such that the Git client avoids\n> +downloading blob objects unless they are required for a local operation.\n> +This initially means that the clone and later fetches download reachable\n> +commits and trees but no blobs. Later operations that change the `HEAD`\n> +pointer, such as `git checkout` or `git merge`, may need to download\n> +missing blobs in order to complete their operation.\n\nOkay.\n\n> +In the worst cases, commands that compute blob diffs, such as `git blame`,\n> +become very slow as they download the missing blobs in single-blob\n> +requests to satisfy the missing object as the Git command needs it. This\n> +leads to multiple download requests and no ability for the Git server to\n> +provide delta compression across those objects.\n> +\n> +The `git backfill` command provides a way for the user to request that\n> +Git downloads the missing blobs (with optional filters) such that the\n> +missing blobs representing historical versions of files can be downloaded\n> +in batches. The `backfill` command attempts to optimize the request by\n> +grouping blobs that appear at the same path, hopefully leading to good\n> +delta compression in the packfile sent by the server.\n\nHm. So we're asking the user to fix a usability issue of git-blame(1),\ndon't we? Ideally, git-blame(1) itself should know to transparently\nbatch the blobs it requires to compute its output, shouldn't it? That\nusecase alone doesn't yet convince me that git-backfill(1) is a good\nidea as I'd think we should rather fix the underlying issue.\n\nSo are there other usecases for git-backfill(1)? I can imagine that it\nmight be helpful in the context of scripts that know they'll operate on\na bunch of blobs.\n\n> diff --git a/builtin/backfill.c b/builtin/backfill.c\n> index 38e6aaeaa03..e5f2000d5e0 100644\n> --- a/builtin/backfill.c\n> +++ b/builtin/backfill.c\n> @@ -1,16 +1,116 @@\n> #include \"builtin.h\"\n> +#include \"git-compat-util.h\"\n> #include \"config.h\"\n> #include \"parse-options.h\"\n> #include \"repository.h\"\n> +#include \"commit.h\"\n> +#include \"hex.h\"\n> +#include \"tree.h\"\n> +#include \"tree-walk.h\"\n> #include \"object.h\"\n> +#include \"object-store-ll.h\"\n> +#include \"oid-array.h\"\n> +#include \"oidset.h\"\n> +#include \"promisor-remote.h\"\n> +#include \"strmap.h\"\n> +#include \"string-list.h\"\n> +#include \"revision.h\"\n> +#include \"trace2.h\"\n> +#include \"progress.h\"\n> +#include \"packfile.h\"\n> +#include \"path-walk.h\"\n> \n> static const char * const builtin_backfill_usage[] = {\n> \tN_(\"git backfill []\"),\n> \tNULL\n> };\n> \n> +struct backfill_context {\n> +\tstruct repository *repo;\n> +\tstruct oid_array current_batch;\n> +\tsize_t batch_size;\n> +};\n> +\n> +static void clear_backfill_context(struct backfill_context *ctx)\n> +{\n> +\toid_array_clear(&ctx->current_batch);\n> +}\n\nNit: our style guide says that this should rather be\n`backfill_context_clear()`.\n\n> +static void download_batch(struct backfill_context *ctx)\n> +{\n> +\tpromisor_remote_get_direct(ctx->repo,\n> +\t\t\t\t ctx->current_batch.oid,\n> +\t\t\t\t ctx->current_batch.nr);\n> +\toid_array_clear(&ctx->current_batch);\n> +\n> +\t/*\n> +\t * We likely have a new packfile. Add it to the packed list to\n> +\t * avoid possible duplicate downloads of the same objects.\n> +\t */\n> +\treprepare_packed_git(ctx->repo);\n> +}\n> +\n> +static int fill_missing_blobs(const char *path UNUSED,\n> +\t\t\t struct oid_array *list,\n> +\t\t\t enum object_type type,\n> +\t\t\t void *data)\n> +{\n> +\tstruct backfill_context *ctx = data;\n> +\n> +\tif (type != OBJ_BLOB)\n> +\t\treturn 0;\n> +\n> +\tfor (size_t i = 0; i < list->nr; i++) {\n> +\t\toff_t size = 0;\n> +\t\tstruct object_info info = OBJECT_INFO_INIT;\n> +\t\tinfo.disk_sizep = &size;\n> +\t\tif (oid_object_info_extended(ctx->repo,\n> +\t\t\t\t\t &list->oid[i],\n> +\t\t\t\t\t &info,\n> +\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH) ||\n> +\t\t !size)\n> +\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n> +\t}\n> +\n> +\tif (ctx->current_batch.nr >= ctx->batch_size)\n> +\t\tdownload_batch(ctx);\n\nOkay, so the batch size is just \"best effort\". If we walk a tree that\nmakes us exceed the batch size then we wouldn't issue a fetch during the\ntree walk. Is there any specific reason for this behaviour?\n\nIn any case, as long as this is properly documented I think this should\nbe fine in general.\n\n> +\treturn 0;\n> +}\n> +\n> +static int do_backfill(struct backfill_context *ctx)\n> +{\n> +\tstruct rev_info revs;\n> +\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n> +\tint ret;\n> +\n> +\trepo_init_revisions(ctx->repo, &revs, \"\");\n> +\thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n> +\n> +\tinfo.blobs = 1;\n> +\tinfo.tags = info.commits = info.trees = 0;\n> +\n> +\tinfo.revs = &revs;\n> +\tinfo.path_fn = fill_missing_blobs;\n> +\tinfo.path_fn_data = ctx;\n> +\n> +\tret = walk_objects_by_path(&info);\n> +\n> +\t/* Download the objects that did not fill a batch. */\n> +\tif (!ret)\n> +\t\tdownload_batch(ctx);\n> +\n> +\tclear_backfill_context(ctx);\n\nAre we leaking `revs` and `info`?\n\n> +\treturn ret;\n> +}\n> +\n> int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n> {\n> +\tstruct backfill_context ctx = {\n> +\t\t.repo = repo,\n> +\t\t.current_batch = OID_ARRAY_INIT,\n> +\t\t.batch_size = 50000,\n> +\t};\n> \tstruct option options[] = {\n> \t\tOPT_END(),\n> \t};\n> @@ -23,7 +123,5 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n> \n> \trepo_config(repo, git_default_config, NULL);\n> \n> -\tdie(_(\"not implemented\"));\n> -\n> -\treturn 0;\n> +\treturn do_backfill(&ctx);\n> }\n\nThe current iteration only backfills blobs as far as I can see. Do we\nmaybe want to keep the door open for future changes in git-backfill(1)\nby implementing this via a \"blob\" subcommand?\n\nPatrick\n"},{"id":"509143","messageId":"Z1_eVZTDPp9g1FhQ@pks.im","threadId":"62610","inReplyTo":"19a8efebbad7f414e3ef3fdca612dc1fcb835f25.1733515638.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 4/5] backfill: add --sparse option","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-12-16T08:01:25Z","receivedAt":"2024-12-16T08:01:44Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 06, 2024 at 08:07:17PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> One way to significantly reduce the cost of a Git clone and later fetches is\n> to use a blobless partial clone and combine that with a sparse-checkout that\n> reduces the paths that need to be populated in the working directory. Not\n> only does this reduce the cost of clones and fetches, the sparse-checkout\n> reduces the number of objects needed to download from a promisor remote.\n> \n> However, history investigations can be expensie as computing blob diffs will\n\ns/expensie/expensive\n\nPatrick\n"},{"id":"509298","messageId":"79e8b04c-f8e4-4a8d-b55d-74f39d5978b6@gmail.com","threadId":"62610","inReplyTo":"Z1_eUSGN3B13uGmM@pks.im","subject":"Re: [PATCH 2/5] backfill: basic functionality and tests","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-12-18T15:03:13Z","receivedAt":"2024-12-18T15:03:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/16/24 3:01 AM, Patrick Steinhardt wrote:\n > On Fri, Dec 06, 2024 at 08:07:15PM +0000, Derrick Stolee via GitGitGadget wrote:\n\n >> +The `git backfill` command provides a way for the user to request that\n >> +Git downloads the missing blobs (with optional filters) such that the\n >> +missing blobs representing historical versions of files can be downloaded\n >> +in batches. The `backfill` command attempts to optimize the request by\n >> +grouping blobs that appear at the same path, hopefully leading to good\n >> +delta compression in the packfile sent by the server.\n >\n > Hm. So we're asking the user to fix a usability issue of git-blame(1),\n > don't we? Ideally, git-blame(1) itself should know to transparently\n > batch the blobs it requires to compute its output, shouldn't it? That\n > usecase alone doesn't yet convince me that git-backfill(1) is a good\n > idea as I'd think we should rather fix the underlying issue.\n\nI've looked into making this change for 'git blame' and it is a\nnontrivial change. I'm not sure on the timeline that we could expect\n'git blame' to be improved.\n\nBut you're right that this is not enough justification on its own. It's\nan example of a kind of command that has these problems, including 'git\nlog [-p|-L]'.\n\n > So are there other usecases for git-backfill(1)? I can imagine that it\n > might be helpful in the context of scripts that know they'll operate on\n > a bunch of blobs.\n\nOne major motivation is that it can essentially provide a way to do\nresumable clones: get the commits and trees in one go with a blobless\nclone, then download the blobs in batches. If something interrupts the\n'git backfill' command, then restarting it will only repeat the most\nrecent batch.\n\nFinally, in a later patch we can see that the --sparse option allows a\nuser to operate as if they have a full clone but where they only include\nblob data within their sparse-checkout, providing reduced disk space and\nnetwork time to get to that state.\n\n >> +\tif (ctx->current_batch.nr >= ctx->batch_size)\n >> +\t\tdownload_batch(ctx);\n >\n > Okay, so the batch size is just \"best effort\". If we walk a tree that\n > makes us exceed the batch size then we wouldn't issue a fetch during the\n > tree walk. Is there any specific reason for this behaviour?\n >\n > In any case, as long as this is properly documented I think this should\n > be fine in general.\n\nThe main reason is that we expect the server to return a packfile that\nhas many delta relationships within the objects at a given path. If we\nsplit the batch in the middle of a path batch, then we are artificially\nintroducing breaks in the delta chains that could be wasteful.\n\nHowever, this batching pattern could be problematic if there are a\nmillion versions of a single file and the batch is too large to download\nefficiently. This \"absolute max batch size\" is currently left as a\nfuture extension.\n\n >> +\tclear_backfill_context(ctx);\n >\n > Are we leaking `revs` and `info`?\n\nAt the moment. Will fix.\n\n >> +\treturn ret;\n >> +}\n >> +\n >> int cmd_backfill(int argc, const char **argv, const char *prefix, struct \nrepository *repo)\n >> {\n >> +\tstruct backfill_context ctx = {\n >> +\t\t.repo = repo,\n >> +\t\t.current_batch = OID_ARRAY_INIT,\n >> +\t\t.batch_size = 50000,\n >> +\t};\n >> \tstruct option options[] = {\n >> \t\tOPT_END(),\n >> \t};\n >> @@ -23,7 +123,5 @@ int cmd_backfill(int argc, const char **argv, const char \n*prefix, struct reposit\n >>\n >> \trepo_config(repo, git_default_config, NULL);\n >>\n >> -\tdie(_(\"not implemented\"));\n >> -\n >> -\treturn 0;\n >> +\treturn do_backfill(&ctx);\n >> }\n >\n > The current iteration only backfills blobs as far as I can see. Do we\n > maybe want to keep the door open for future changes in git-backfill(1)\n > by implementing this via a \"blob\" subcommand?\n\nI think that one tricky part is to ask \"what could be missing?\". With\nGit's partial clone, it seems that we could have treeless or depth-\nbased tree restrictions. Technically, there could also be clones that\nrestrict to a set of sparse-checkout patterns, but I'm not aware of any\nserver that will respect those kinds of clones. At the moment, the tree\nwalk would fault in any missing trees as they are seen, but this is\nextremely inefficient.\n\nI think that the path-walk API could be adjusted to be more careful to\ncheck for the existence of an object before automatically loading it.\nThat would allow for batched downloads of missing trees, though a\nsecond scan would be required to get the next layer of objects.\n\nI'm not sure a subcommand is the right way to solve for this potential\nfuture, but instead later we could adjust the logic to be better for\nthese treeless or tree-restricted clones.\n\nThanks,\n-Stolee\n"},{"id":"509299","messageId":"d8e64f60-79c2-4c3d-9dc4-5e9842943de3@gmail.com","threadId":"62610","inReplyTo":"Z1_eTHk6IEJ0BEEg@pks.im","subject":"Re: [PATCH 3/5] backfill: add --batch-size= option","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-12-18T15:09:38Z","receivedAt":"2024-12-18T15:09:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/16/24 3:01 AM, Patrick Steinhardt wrote:\n > On Fri, Dec 06, 2024 at 08:07:16PM +0000, Derrick Stolee via GitGitGadget wrote:\n >> From: Derrick Stolee \n >>\n >> Users may want to specify a minimum batch size for their needs. This is only\n >> a minimum: the path-walk API provides a list of OIDs that correspond to the\n >> same path, and thus it is optimal to allow delta compression across those\n >> objects in a single server request.\n >\n > Okay, here you explicitly say that this is a minimum batch size, so this\n > is by design and with a proper reason. Good.\n >\n >> We could consider limiting the request to have a maximum batch size in the\n >> future. For now, we let the path-walk API batches determine the\n >> boundaries.\n >\n > Should we maybe rename `--batch-size` to `--min-batch-size` so that it\n > does not become awkward if we ever want to have a maximum batch size, as\n > well? Also helps to set expectations with the user.\n\nGood idea. Will do.\n\n >> diff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\n >> index 0e10f066fef..9b0bae04e9d 100644\n >> --- a/Documentation/git-backfill.txt\n >> +++ b/Documentation/git-backfill.txt\n >> @@ -38,6 +38,14 @@ delta compression in the packfile sent by the server.\n >> By default, `git backfill` downloads all blobs reachable from the `HEAD`\n >> commit. This set can be restricted or expanded using various options.\n >>\n >> +OPTIONS\n >> +-------\n >> +\n >> +--batch-size=::\n >> +\tSpecify a minimum size for a batch of missing objects to request\n >> +\tfrom the server. This size may be exceeded by the last set of\n >> +\tblobs seen at a given path. Default batch size is 16,000.\n >\n > This is stale: s/16,000/50,000/\n\nThanks!\n\n >> diff --git a/builtin/backfill.c b/builtin/backfill.c\n >> index e5f2000d5e0..127333daef8 100644\n >> --- a/builtin/backfill.c\n >> +++ b/builtin/backfill.c\n >> @@ -112,6 +112,8 @@ int cmd_backfill(int argc, const char **argv, const char \n*prefix,\n >> struct reposit\n >> .batch_size = 50000,\n >> };\n >> struct option options[] = {\n >> + OPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n >> + N_(\"Minimun number of objects to request at a \ntime\")),\n >\n > s/Minimun/Minimum\n\nThanks for the careful eye for detail.\n\n-Stolee\n"},{"id":"509418","messageId":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.git.1733515638.gitgitgadget@gmail.com","subject":"[PATCH v2 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-20T16:29:48Z","receivedAt":"2024-12-20T16:29:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This is based on v4 of ds/path-walk-1 [1] and an earlier version was part of\nmy initial path-walk RFC [2].\n\n[1]\nhttps://lore.kernel.org/git/pull.1818.v3.git.1733514358.gitgitgadget@gmail.com/\n\n[2]\nhttps://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/\n\nThis series adds a new 'git backfill' command that uses the path-walk API to\ndownload missing blobs in a blobless partial clone. Users can specify\ninteraction with the sparse-checkout using '--[no-]sparse' but the\n'--sparse' option is implied by the existence of a sparse-checkout.\n\nThe reason to use the path-walk API is to make sure that the missing objects\nare grouped by a common path, giving a reasonable process for batching\nrequests and expecting the server to compress the resulting packfile nicely\ntogether.\n\nI first prototyped this feature in June 2024 as an exploration and created\nthe path-walk algorithm for this purpose. It was only my intuition that led\nme to believe that batching by path would lead to better packfiles. This has\nbeen proven out as a very important feature due to recent investigations to\ncompressing full repositories by doing a better job of grouping objects by\npath. See the --name-hash-version series [3] or the 'git pack-objects\n--path-walk' series [4] (currently on hold as it conflicts with the\n--name-hash-version series).\n\n[3]\nhttps://lore.kernel.org/git/pull.1823.v2.git.1733181682.gitgitgadget@gmail.com/\n\n[4]\nhttps://lore.kernel.org/git/pull.1813.v2.git.1729431810.gitgitgadget@gmail.com/\n\nThis idea can be further demonstrated by the evidence in testing this\nfeature: by downloading objects in small batch sizes, the client can force\nthe server to repack things more efficiently than a full repack.\n\nThe example repository I have used in multiple places is the\nmicrosoft/fluentui repo [5] as it has many CHANGELOG.md files that cause\nname hash collisions that make the full repack inefficient.\n\n[5] https://github.com/microsoft/fluentui\n\nIf we create a blobless clone of the fluentui repo, then this downloads 105\nMB across two packfiles (the commits and trees pack, followed by the blobs\nneeded for an initial checkout). Running 'git backfill --batch-size=' for\ndifferent sizes leads to some interesting results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 105 MB | |\n| 5K | 53 | 348 MB | 2m 26s |\n| 10K | 28 | 365 MB | 2m 22s |\n| 15K | 19 | 407 MB | 2m 21s |\n| 20K | 15 | 393 MB | 2m 28s |\n| 25K | 13 | 417 MB | 2m 06s |\n| 50K | 8 | 509 MB | 1m 34s |\n| 100K | 5 | 535 MB | 1m 56s |\n| 250K | 4 | 698 MB | 1m 33s |\n| 500K | 3 | 696 MB | 1m 42s |\n\n\nThe smaller batches cause the server to realize that the existing deltas\ncannot be reused and it finds better deltas. This takes some extra time for\nthe small batches, but halves the size of the repo. Even in the 500K batch\nsize, we get less data than the 738 MB of a full clone.\n\nImplementing the --sparse feature is best done by augmenting the path-walk\nAPI to be aware of a pattern list. This works for both cone and non-cone\nmode sparse-checkouts.\n\nThere are future directions we could take this command, especially to run\nthe command with a user-specified pathspec. The tricky case for that\nadditional feature is trying to make the path-walk more efficient by\nskipping tree paths that would not lead to a match of the pathspec. It would\nlikely need optimization in a small subset of pathspec features (such as\nprefix matches) to work as efficiently as possible. I did prototype a\nversion that puts the pathspec match in the callback function within\nbuiltin/backfill.c, but I found that uninspiring and unnecessary for now.\n\n\nUpdates in v2\n=============\n\nThanks for the review on v1.\n\n * Memory leaks should be plugged now due to the introduction of a\n destructor in v4 of the path-walk API and its extension here to clear the\n pattern list.\n\n * Documentation is expanded to demonstrate that 'git backfill' can also\n approximate incremental/resumable clones of repositories.\n\n * Method renames to better match style.\n\n * --batch-size is renamed to --min-batch-size for clarity and future\n extensibility.\n\nThanks, -Stolee\n\nDerrick Stolee (5):\n backfill: add builtin boilerplate\n backfill: basic functionality and tests\n backfill: add --min-batch-size= option\n backfill: add --sparse option\n backfill: assume --sparse when sparse-checkout is enabled\n\n .gitignore | 1 +\n Documentation/git-backfill.txt | 68 +++++++++\n Documentation/technical/api-path-walk.txt | 11 +-\n Makefile | 1 +\n builtin.h | 1 +\n builtin/backfill.c | 151 ++++++++++++++++++\n command-list.txt | 1 +\n dir.c | 10 +-\n dir.h | 3 +\n git.c | 1 +\n path-walk.c | 28 +++-\n path-walk.h | 11 ++\n t/helper/test-path-walk.c | 22 ++-\n t/t5620-backfill.sh | 178 ++++++++++++++++++++++\n t/t6601-path-walk.sh | 32 ++++\n 15 files changed, 505 insertions(+), 14 deletions(-)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 builtin/backfill.c\n create mode 100755 t/t5620-backfill.sh\n\n\nbase-commit: ef543429ed9cb92e209900e7c7fc4f8e0698a306\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1820%2Fderrickstolee%2Fbackfill-upstream-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1820/derrickstolee/backfill-upstream-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1820\n\nRange-diff vs v1:\n\n 1: 0300aa1b8c3 = 1: ac86510417a backfill: add builtin boilerplate\n 2: 5728dd27021 ! 2: e4e88794cae backfill: basic functionality and tests\n @@ Documentation/git-backfill.txt: SYNOPSIS\n +grouping blobs that appear at the same path, hopefully leading to good\n +delta compression in the packfile sent by the server.\n +\n ++In this way, `git backfill` provides a mechanism to break a large clone\n ++into smaller chunks. Starting with a blobless partial clone with `git\n ++clone --filter=blob:none` and then running `git backfill` in the local\n ++repository provides a way to download all reachable objects in several\n ++smaller network calls than downloading the entire repository at clone\n ++time.\n ++\n +By default, `git backfill` downloads all blobs reachable from the `HEAD`\n +commit. This set can be restricted or expanded using various options.\n +\n @@ builtin/backfill.c\n +\tsize_t batch_size;\n +};\n +\n -+static void clear_backfill_context(struct backfill_context *ctx)\n ++static void backfill_context_clear(struct backfill_context *ctx)\n +{\n +\toid_array_clear(&ctx->current_batch);\n +}\n @@ builtin/backfill.c\n +\tif (!ret)\n +\t\tdownload_batch(ctx);\n +\n -+\tclear_backfill_context(ctx);\n ++\tbackfill_context_clear(ctx);\n ++\tpath_walk_info_clear(&info);\n ++\trelease_revisions(&revs);\n +\treturn ret;\n +}\n +\n 3: 3cfd23073a0 ! 3: 3fa32822dab backfill: add --batch-size= option\n @@ Metadata\n Author: Derrick Stolee \n \n ## Commit message ##\n - backfill: add --batch-size= option\n + backfill: add --min-batch-size= option\n \n Users may want to specify a minimum batch size for their needs. This is only\n a minimum: the path-walk API provides a list of OIDs that correspond to the\n @@ Documentation/git-backfill.txt: git-backfill - Download missing objects in a par\n \n DESCRIPTION\n -----------\n -@@ Documentation/git-backfill.txt: delta compression in the packfile sent by the server.\n +@@ Documentation/git-backfill.txt: time.\n By default, `git backfill` downloads all blobs reachable from the `HEAD`\n commit. This set can be restricted or expanded using various options.\n \n +OPTIONS\n +-------\n +\n -+--batch-size=::\n ++--min-batch-size=::\n +\tSpecify a minimum size for a batch of missing objects to request\n +\tfrom the server. This size may be exceeded by the last set of\n -+\tblobs seen at a given path. Default batch size is 16,000.\n ++\tblobs seen at a given path. The default minimum batch size is\n ++\t50,000.\n +\n SEE ALSO\n --------\n @@ builtin/backfill.c\n \tNULL\n };\n \n + struct backfill_context {\n + \tstruct repository *repo;\n + \tstruct oid_array current_batch;\n +-\tsize_t batch_size;\n ++\tsize_t min_batch_size;\n + };\n + \n + static void backfill_context_clear(struct backfill_context *ctx)\n +@@ builtin/backfill.c: static int fill_missing_blobs(const char *path UNUSED,\n + \t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n + \t}\n + \n +-\tif (ctx->current_batch.nr >= ctx->batch_size)\n ++\tif (ctx->current_batch.nr >= ctx->min_batch_size)\n + \t\tdownload_batch(ctx);\n + \n + \treturn 0;\n @@ builtin/backfill.c: int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n - \t\t.batch_size = 50000,\n + \tstruct backfill_context ctx = {\n + \t\t.repo = repo,\n + \t\t.current_batch = OID_ARRAY_INIT,\n +-\t\t.batch_size = 50000,\n ++\t\t.min_batch_size = 50000,\n \t};\n \tstruct option options[] = {\n -+\t\tOPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n -+\t\t\t N_(\"Minimun number of objects to request at a time\")),\n ++\t\tOPT_INTEGER(0, \"min-batch-size\", &ctx.min_batch_size,\n ++\t\t\t N_(\"Minimum number of objects to request at a time\")),\n \t\tOPT_END(),\n \t};\n \n @@ t/t5620-backfill.sh: test_expect_success 'do partial clone 1, backfill gets all\n \ttest_line_count = 0 revs2\n '\n \n -+test_expect_success 'do partial clone 2, backfill batch size' '\n ++test_expect_success 'do partial clone 2, backfill min batch size' '\n +\tgit clone --no-checkout --filter=blob:none\t\\\n +\t\t--single-branch --branch=main \t\t\\\n +\t\t\"file://$(pwd)/srv.bare\" backfill2 &&\n +\n +\tGIT_TRACE2_EVENT=\"$(pwd)/batch-trace\" git \\\n -+\t\t-C backfill2 backfill --batch-size=20 &&\n ++\t\t-C backfill2 backfill --min-batch-size=20 &&\n +\n +\t# Batches were used\n +\ttest_trace2_data promisor fetch_count 20 matches &&\n 4: 19a8efebbad ! 4: 2723143afb3 backfill: add --sparse option\n @@ Commit message\n only does this reduce the cost of clones and fetches, the sparse-checkout\n reduces the number of objects needed to download from a promisor remote.\n \n - However, history investigations can be expensie as computing blob diffs will\n - trigger promisor remote requests for one object at a time. This can be\n + However, history investigations can be expensive as computing blob diffs\n + will trigger promisor remote requests for one object at a time. This can be\n avoided by downloading the blobs needed for the given sparse-checkout using\n 'git backfill' and its new '--sparse' mode, at a time that the user is\n willing to pay that extra cost.\n @@ Documentation/git-backfill.txt: git-backfill - Download missing objects in a par\n DESCRIPTION\n -----------\n @@ Documentation/git-backfill.txt: OPTIONS\n - \tfrom the server. This size may be exceeded by the last set of\n - \tblobs seen at a given path. Default batch size is 16,000.\n + \tblobs seen at a given path. The default minimum batch size is\n + \t50,000.\n \n +--[no-]sparse::\n +\tOnly download objects if they appear at a path that matches the\n @@ builtin/backfill.c\n @@ builtin/backfill.c: struct backfill_context {\n \tstruct repository *repo;\n \tstruct oid_array current_batch;\n - \tsize_t batch_size;\n + \tsize_t min_batch_size;\n +\tint sparse;\n };\n \n - static void clear_backfill_context(struct backfill_context *ctx)\n + static void backfill_context_clear(struct backfill_context *ctx)\n @@ builtin/backfill.c: static int do_backfill(struct backfill_context *ctx)\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tint ret;\n \n +\tif (ctx->sparse) {\n +\t\tCALLOC_ARRAY(info.pl, 1);\n -+\t\tif (get_sparse_checkout_patterns(info.pl))\n ++\t\tif (get_sparse_checkout_patterns(info.pl)) {\n ++\t\t\tpath_walk_info_clear(&info);\n +\t\t\treturn error(_(\"problem loading sparse-checkout\"));\n ++\t\t}\n +\t}\n +\n \trepo_init_revisions(ctx->repo, &revs, \"\");\n @@ builtin/backfill.c: static int do_backfill(struct backfill_context *ctx)\n @@ builtin/backfill.c: int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \t\t.repo = repo,\n \t\t.current_batch = OID_ARRAY_INIT,\n - \t\t.batch_size = 50000,\n + \t\t.min_batch_size = 50000,\n +\t\t.sparse = 0,\n \t};\n \tstruct option options[] = {\n - \t\tOPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n - \t\t\t N_(\"Minimun number of objects to request at a time\")),\n + \t\tOPT_INTEGER(0, \"min-batch-size\", &ctx.min_batch_size,\n + \t\t\t N_(\"Minimum number of objects to request at a time\")),\n +\t\tOPT_BOOL(0, \"sparse\", &ctx.sparse,\n +\t\t\t N_(\"Restrict the missing objects to the current sparse-checkout\")),\n \t\tOPT_END(),\n @@ path-walk.c\n #include \"revision.h\"\n #include \"string-list.h\"\n #include \"strmap.h\"\n -@@ path-walk.c: static int add_children(struct path_walk_context *ctx,\n +@@ path-walk.c: static int add_tree_entries(struct path_walk_context *ctx,\n \t\tif (type == OBJ_TREE)\n \t\t\tstrbuf_addch(&path, '/');\n \n @@ path-walk.c: static int add_children(struct path_walk_context *ctx,\n \t\tif (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) {\n \t\t\tCALLOC_ARRAY(list, 1);\n \t\t\tlist->type = type;\n +@@ path-walk.c: void path_walk_info_init(struct path_walk_info *info)\n + \tmemcpy(info, &empty, sizeof(empty));\n + }\n + \n +-void path_walk_info_clear(struct path_walk_info *info UNUSED)\n ++void path_walk_info_clear(struct path_walk_info *info)\n + {\n +-\t/*\n +-\t * This destructor is empty for now, as info->revs\n +-\t * is not owned by 'struct path_walk_info'.\n +-\t */\n ++\tif (info->pl) {\n ++\t\tclear_pattern_list(info->pl);\n ++\t\tfree(info->pl);\n ++\t}\n + }\n \n ## path-walk.h ##\n @@\n @@ t/helper/test-path-walk.c: int cmd__path_walk(int argc, const char **argv)\n }\n \n ## t/t5620-backfill.sh ##\n -@@ t/t5620-backfill.sh: test_expect_success 'do partial clone 2, backfill batch size' '\n +@@ t/t5620-backfill.sh: test_expect_success 'do partial clone 2, backfill min batch size' '\n \ttest_line_count = 0 revs2\n '\n \n 5: 35a7e4ec4d3 ! 5: 1f765409eaf backfill: assume --sparse when sparse-checkout is enabled\n @@ builtin/backfill.c: int cmd_backfill(int argc, const char **argv, const char *pr\n }\n \n ## t/t5620-backfill.sh ##\n -@@ t/t5620-backfill.sh: test_expect_success 'do partial clone 2, backfill batch size' '\n +@@ t/t5620-backfill.sh: test_expect_success 'do partial clone 2, backfill min batch size' '\n \ttest_line_count = 0 revs2\n '\n \n\n-- \ngitgitgadget\n"},{"id":"509419","messageId":"ac86510417a0b1713f5fa34acab547f01b716fd2.1734712193.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","subject":"[PATCH v2 1/5] backfill: add builtin boilerplate","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-20T16:29:49Z","receivedAt":"2024-12-20T16:29:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of implementing 'git backfill', populate the necessary files\nwith the boilerplate of a new builtin.\n\nSigned-off-by: Derrick Stolee \n---\n .gitignore | 1 +\n Documentation/git-backfill.txt | 23 +++++++++++++++++++++++\n Makefile | 1 +\n builtin.h | 1 +\n builtin/backfill.c | 29 +++++++++++++++++++++++++++++\n command-list.txt | 1 +\n git.c | 1 +\n 7 files changed, 57 insertions(+)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 builtin/backfill.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 6687bd6db4c..0f9e7de2ec3 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -20,6 +20,7 @@\n /git-apply\n /git-archimport\n /git-archive\n+/git-backfill\n /git-bisect\n /git-blame\n /git-branch\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nnew file mode 100644\nindex 00000000000..640144187d3\n--- /dev/null\n+++ b/Documentation/git-backfill.txt\n@@ -0,0 +1,23 @@\n+git-backfill(1)\n+===============\n+\n+NAME\n+----\n+git-backfill - Download missing objects in a partial clone\n+\n+\n+SYNOPSIS\n+--------\n+[verse]\n+'git backfill' []\n+\n+DESCRIPTION\n+-----------\n+\n+SEE ALSO\n+--------\n+linkgit:git-clone[1].\n+\n+GIT\n+---\n+Part of the linkgit:git[1] suite\ndiff --git a/Makefile b/Makefile\nindex 50413d96492..e18e0f4e447 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1203,6 +1203,7 @@ BUILTIN_OBJS += builtin/am.o\n BUILTIN_OBJS += builtin/annotate.o\n BUILTIN_OBJS += builtin/apply.o\n BUILTIN_OBJS += builtin/archive.o\n+BUILTIN_OBJS += builtin/backfill.o\n BUILTIN_OBJS += builtin/bisect.o\n BUILTIN_OBJS += builtin/blame.o\n BUILTIN_OBJS += builtin/branch.o\ndiff --git a/builtin.h b/builtin.h\nindex f7b166b3348..89928ccf92f 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -120,6 +120,7 @@ int cmd_am(int argc, const char **argv, const char *prefix, struct repository *r\n int cmd_annotate(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_apply(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_archive(int argc, const char **argv, const char *prefix, struct repository *repo);\n+int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_bisect(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_blame(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_branch(int argc, const char **argv, const char *prefix, struct repository *repo);\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nnew file mode 100644\nindex 00000000000..38e6aaeaa03\n--- /dev/null\n+++ b/builtin/backfill.c\n@@ -0,0 +1,29 @@\n+#include \"builtin.h\"\n+#include \"config.h\"\n+#include \"parse-options.h\"\n+#include \"repository.h\"\n+#include \"object.h\"\n+\n+static const char * const builtin_backfill_usage[] = {\n+\tN_(\"git backfill []\"),\n+\tNULL\n+};\n+\n+int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n+{\n+\tstruct option options[] = {\n+\t\tOPT_END(),\n+\t};\n+\n+\tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n+\t\tusage_with_options(builtin_backfill_usage, options);\n+\n+\targc = parse_options(argc, argv, prefix, options, builtin_backfill_usage,\n+\t\t\t 0);\n+\n+\trepo_config(repo, git_default_config, NULL);\n+\n+\tdie(_(\"not implemented\"));\n+\n+\treturn 0;\n+}\ndiff --git a/command-list.txt b/command-list.txt\nindex e0bb87b3b5c..c537114b468 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -60,6 +60,7 @@ git-annotate ancillaryinterrogators\n git-apply plumbingmanipulators complete\n git-archimport foreignscminterface\n git-archive mainporcelain\n+git-backfill mainporcelain history\n git-bisect mainporcelain info\n git-blame ancillaryinterrogators complete\n git-branch mainporcelain history\ndiff --git a/git.c b/git.c\nindex 2fbea24ec92..00d9b3ec8a9 100644\n--- a/git.c\n+++ b/git.c\n@@ -509,6 +509,7 @@ static struct cmd_struct commands[] = {\n \t{ \"annotate\", cmd_annotate, RUN_SETUP },\n \t{ \"apply\", cmd_apply, RUN_SETUP_GENTLY },\n \t{ \"archive\", cmd_archive, RUN_SETUP_GENTLY },\n+\t{ \"backfill\", cmd_backfill, RUN_SETUP },\n \t{ \"bisect\", cmd_bisect, RUN_SETUP },\n \t{ \"blame\", cmd_blame, RUN_SETUP },\n \t{ \"branch\", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG },\n-- \ngitgitgadget\n\n"},{"id":"509421","messageId":"e4e88794cae7edc568dd054b1376caac7fd30076.1734712193.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","subject":"[PATCH v2 2/5] backfill: basic functionality and tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-20T16:29:50Z","receivedAt":"2024-12-20T16:29:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe default behavior of 'git backfill' is to fetch all missing blobs that\nare reachable from HEAD. Document and test this behavior.\n\nThe implementation is a very simple use of the path-walk API, initializing\nthe revision walk at HEAD to start the path-walk from all commits reachable\nfrom HEAD. Ignore the object arrays that correspond to tree entries,\nassuming that they are all present already.\n\nThe path-walk API provides lists of objects in batches according to a\ncommon path, but that list could be very small. We want to balance the\nnumber of requests to the server with the ability to have the process\ninterrupted with minimal repeated work to catch up in the next run.\nBased on some experiments (detailed in the next change) a minimum batch\nsize of 50,000 is selected for the default.\n\nThis batch size is a _minimum_. As the path-walk API emits lists of blob\nIDs, they are collected into a list of objects for a request to the\nserver. When that list is at least the minimum batch size, then the\nrequest is sent to the server for the new objects. However, the list of\nblob IDs from the path-walk API could be much longer than the batch\nsize. At this moment, it is unclear if there is a benefit to split the\nlist when there are too many objects at the same path.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 31 +++++++\n Documentation/technical/api-path-walk.txt | 3 +-\n builtin/backfill.c | 106 +++++++++++++++++++++-\n t/t5620-backfill.sh | 94 +++++++++++++++++++\n 4 files changed, 230 insertions(+), 4 deletions(-)\n create mode 100755 t/t5620-backfill.sh\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 640144187d3..ece887831f6 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -14,6 +14,37 @@ SYNOPSIS\n DESCRIPTION\n -----------\n \n+Blobless partial clones are created using `git clone --filter=blob:none`\n+and then configure the local repository such that the Git client avoids\n+downloading blob objects unless they are required for a local operation.\n+This initially means that the clone and later fetches download reachable\n+commits and trees but no blobs. Later operations that change the `HEAD`\n+pointer, such as `git checkout` or `git merge`, may need to download\n+missing blobs in order to complete their operation.\n+\n+In the worst cases, commands that compute blob diffs, such as `git blame`,\n+become very slow as they download the missing blobs in single-blob\n+requests to satisfy the missing object as the Git command needs it. This\n+leads to multiple download requests and no ability for the Git server to\n+provide delta compression across those objects.\n+\n+The `git backfill` command provides a way for the user to request that\n+Git downloads the missing blobs (with optional filters) such that the\n+missing blobs representing historical versions of files can be downloaded\n+in batches. The `backfill` command attempts to optimize the request by\n+grouping blobs that appear at the same path, hopefully leading to good\n+delta compression in the packfile sent by the server.\n+\n+In this way, `git backfill` provides a mechanism to break a large clone\n+into smaller chunks. Starting with a blobless partial clone with `git\n+clone --filter=blob:none` and then running `git backfill` in the local\n+repository provides a way to download all reachable objects in several\n+smaller network calls than downloading the entire repository at clone\n+time.\n+\n+By default, `git backfill` downloads all blobs reachable from the `HEAD`\n+commit. This set can be restricted or expanded using various options.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 7075d0d5ab5..1fba0ce04cb 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -60,4 +60,5 @@ Examples\n --------\n \n See example usages in:\n-\t`t/helper/test-path-walk.c`\n+\t`t/helper/test-path-walk.c`,\n+\t`builtin/backfill.c`\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 38e6aaeaa03..177fd4286c7 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -1,16 +1,118 @@\n #include \"builtin.h\"\n+#include \"git-compat-util.h\"\n #include \"config.h\"\n #include \"parse-options.h\"\n #include \"repository.h\"\n+#include \"commit.h\"\n+#include \"hex.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n #include \"object.h\"\n+#include \"object-store-ll.h\"\n+#include \"oid-array.h\"\n+#include \"oidset.h\"\n+#include \"promisor-remote.h\"\n+#include \"strmap.h\"\n+#include \"string-list.h\"\n+#include \"revision.h\"\n+#include \"trace2.h\"\n+#include \"progress.h\"\n+#include \"packfile.h\"\n+#include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n \tN_(\"git backfill []\"),\n \tNULL\n };\n \n+struct backfill_context {\n+\tstruct repository *repo;\n+\tstruct oid_array current_batch;\n+\tsize_t batch_size;\n+};\n+\n+static void backfill_context_clear(struct backfill_context *ctx)\n+{\n+\toid_array_clear(&ctx->current_batch);\n+}\n+\n+static void download_batch(struct backfill_context *ctx)\n+{\n+\tpromisor_remote_get_direct(ctx->repo,\n+\t\t\t\t ctx->current_batch.oid,\n+\t\t\t\t ctx->current_batch.nr);\n+\toid_array_clear(&ctx->current_batch);\n+\n+\t/*\n+\t * We likely have a new packfile. Add it to the packed list to\n+\t * avoid possible duplicate downloads of the same objects.\n+\t */\n+\treprepare_packed_git(ctx->repo);\n+}\n+\n+static int fill_missing_blobs(const char *path UNUSED,\n+\t\t\t struct oid_array *list,\n+\t\t\t enum object_type type,\n+\t\t\t void *data)\n+{\n+\tstruct backfill_context *ctx = data;\n+\n+\tif (type != OBJ_BLOB)\n+\t\treturn 0;\n+\n+\tfor (size_t i = 0; i < list->nr; i++) {\n+\t\toff_t size = 0;\n+\t\tstruct object_info info = OBJECT_INFO_INIT;\n+\t\tinfo.disk_sizep = &size;\n+\t\tif (oid_object_info_extended(ctx->repo,\n+\t\t\t\t\t &list->oid[i],\n+\t\t\t\t\t &info,\n+\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH) ||\n+\t\t !size)\n+\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n+\t}\n+\n+\tif (ctx->current_batch.nr >= ctx->batch_size)\n+\t\tdownload_batch(ctx);\n+\n+\treturn 0;\n+}\n+\n+static int do_backfill(struct backfill_context *ctx)\n+{\n+\tstruct rev_info revs;\n+\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n+\tint ret;\n+\n+\trepo_init_revisions(ctx->repo, &revs, \"\");\n+\thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n+\n+\tinfo.blobs = 1;\n+\tinfo.tags = info.commits = info.trees = 0;\n+\n+\tinfo.revs = &revs;\n+\tinfo.path_fn = fill_missing_blobs;\n+\tinfo.path_fn_data = ctx;\n+\n+\tret = walk_objects_by_path(&info);\n+\n+\t/* Download the objects that did not fill a batch. */\n+\tif (!ret)\n+\t\tdownload_batch(ctx);\n+\n+\tbackfill_context_clear(ctx);\n+\tpath_walk_info_clear(&info);\n+\trelease_revisions(&revs);\n+\treturn ret;\n+}\n+\n int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n {\n+\tstruct backfill_context ctx = {\n+\t\t.repo = repo,\n+\t\t.current_batch = OID_ARRAY_INIT,\n+\t\t.batch_size = 50000,\n+\t};\n \tstruct option options[] = {\n \t\tOPT_END(),\n \t};\n@@ -23,7 +125,5 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \n \trepo_config(repo, git_default_config, NULL);\n \n-\tdie(_(\"not implemented\"));\n-\n-\treturn 0;\n+\treturn do_backfill(&ctx);\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nnew file mode 100755\nindex 00000000000..64326362d80\n--- /dev/null\n+++ b/t/t5620-backfill.sh\n@@ -0,0 +1,94 @@\n+#!/bin/sh\n+\n+test_description='git backfill on partial clones'\n+\n+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main\n+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME\n+\n+. ./test-lib.sh\n+\n+# We create objects in the 'src' repo.\n+test_expect_success 'setup repo for object creation' '\n+\techo \"{print \\$1}\" >print_1.awk &&\n+\techo \"{print \\$2}\" >print_2.awk &&\n+\n+\tgit init src &&\n+\n+\tmkdir -p src/a/b/c &&\n+\tmkdir -p src/d/e &&\n+\n+\tfor i in 1 2\n+\tdo\n+\t\tfor n in 1 2 3 4\n+\t\tdo\n+\t\t\techo \"Version $i of file $n\" > src/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/$n\" > src/a/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/$n\" > src/a/b/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/c/$n\" > src/a/b/c/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/$n\" > src/d/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/e/$n\" > src/d/e/file.$n.txt &&\n+\t\t\tgit -C src add . &&\n+\t\t\tgit -C src commit -m \"Iteration $n\" || return 1\n+\t\tdone\n+\tdone\n+'\n+\n+# Clone 'src' into 'srv.bare' so we have a bare repo to be our origin\n+# server for the partial clone.\n+test_expect_success 'setup bare clone for server' '\n+\tgit clone --bare \"file://$(pwd)/src\" srv.bare &&\n+\tgit -C srv.bare config --local uploadpack.allowfilter 1 &&\n+\tgit -C srv.bare config --local uploadpack.allowanysha1inwant 1\n+'\n+\n+# do basic partial clone from \"srv.bare\"\n+test_expect_success 'do partial clone 1, backfill gets all objects' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill1 &&\n+\n+\t# Backfill with no options gets everything reachable from HEAD.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-file-trace\" git \\\n+\t\t-C backfill1 backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n+. \"$TEST_DIRECTORY\"/lib-httpd.sh\n+start_httpd\n+\n+test_expect_success 'create a partial clone over HTTP' '\n+\tSERVER=\"$HTTPD_DOCUMENT_ROOT_PATH/server\" &&\n+\trm -rf \"$SERVER\" repo &&\n+\tgit clone --bare \"file://$(pwd)/src\" \"$SERVER\" &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowfilter 1 &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowanysha1inwant 1 &&\n+\n+\tgit clone --no-checkout --filter=blob:none \\\n+\t\t\"$HTTPD_URL/smart/server\" backfill-http\n+'\n+\n+test_expect_success 'backfilling over HTTP succeeds' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-http-trace\" git \\\n+\t\t-C backfill-http backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 rev-list-out &&\n+\tawk \"{print \\$1;}\" oids &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/walk-trace\" git -C backfill-http \\\n+\t\tcat-file --batch-check batch-out &&\n+\t! grep missing batch-out\n+'\n+\n+# DO NOT add non-httpd-specific tests here, because the last part of this\n+# test script is only executed when httpd is available and enabled.\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"509420","messageId":"3fa32822dabb64266a0625c50530ae2ae0797de6.1734712193.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","subject":"[PATCH v2 3/5] backfill: add --min-batch-size= option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-20T16:29:51Z","receivedAt":"2024-12-20T16:30:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nUsers may want to specify a minimum batch size for their needs. This is only\na minimum: the path-walk API provides a list of OIDs that correspond to the\nsame path, and thus it is optimal to allow delta compression across those\nobjects in a single server request.\n\nWe could consider limiting the request to have a maximum batch size in the\nfuture. For now, we let the path-walk API batches determine the\nboundaries.\n\nTo get a feeling for the value of specifying the --batch-size parameter,\nI tested a number of open source repositories available on GitHub. The\nprocedure was generally:\n\n 1. git clone --filter=blob:none \n 2. git backfill\n\nChecking the number of packfiles and the size of the .git/objects/pack\ndirectory helps to identify the effects of different batch sizes.\n\nFor the Git repository, we get these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|-------|\n| (Initial clone) | 2 | 119 MB | |\n| 25K | 8 | 290 MB | 24s |\n| 50K | 5 | 290 MB | 24s |\n| 100K | 4 | 290 MB | 29s |\n\nOther than the packfile counts decreasing as we need fewer batches, the\nsize and time required is not changing much for this small example.\n\nFor the nodejs/node repository, we see these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 330 MB | |\n| 25K | 19 | 1,222 MB | 1m 22s |\n| 50K | 11 | 1,221 MB | 1m 24s |\n| 100K | 7 | 1,223 MB | 1m 40s |\n| 250K | 4 | 1,224 MB | 2m 23s |\n| 500K | 3 | 1,216 MB | 4m 38s |\n\nHere, we don't have much difference in the size of the repo, though the\n500K batch size results in a few MB gained. That comes at a cost of a\nmuch longer time. This extra time is due to server-side delta\ncompression happening as the on-disk deltas don't appear to be reusable\nall the time. But for smaller batch sizes, the server is able to find\nreasonable deltas partly because we are asking for objects that appear\nin the same region of the directory tree and include all versions of a\nfile at a specific path.\n\nTo contrast this example, I tested the microsoft/fluentui repo, which\nhas been known to have inefficient packing due to name hash collisions.\nThese results are found before GitHub had the opportunity to repack the\nserver with more advanced name hash versions:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 105 MB | |\n| 5K | 53 | 348 MB | 2m 26s |\n| 10K | 28 | 365 MB | 2m 22s |\n| 15K | 19 | 407 MB | 2m 21s |\n| 20K | 15 | 393 MB | 2m 28s |\n| 25K | 13 | 417 MB | 2m 06s |\n| 50K | 8 | 509 MB | 1m 34s |\n| 100K | 5 | 535 MB | 1m 56s |\n| 250K | 4 | 698 MB | 1m 33s |\n| 500K | 3 | 696 MB | 1m 42s |\n\nHere, a larger variety of batch sizes were chosen because of the great\nvariation in results. By asking the server to download small batches\ncorresponding to fewer paths at a time, the server is able to provide\nbetter compression for these batches than it would for a regular clone.\nA typical full clone for this repository would require 738 MB.\n\nThis example justifies the choice to batch requests by path name,\nleading to improved communication with a server that is not optimally\npacked.\n\nFinally, the same experiment for the Linux repository had these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|---------|\n| (Initial clone) | 2 | 2,153 MB | |\n| 25K | 63 | 6,380 MB | 14m 08s |\n| 50K | 58 | 6,126 MB | 15m 11s |\n| 100K | 30 | 6,135 MB | 18m 11s |\n| 250K | 14 | 6,146 MB | 18m 22s |\n| 500K | 8 | 6,143 MB | 33m 29s |\n\nEven in this example, where the default name hash algorithm leads to\ndecent compression of the Linux kernel repository, there is value for\nselecting a smaller batch size, to a limit. The 25K batch size has the\nfastest time, but uses 250 MB more than the 50K batch size. The 500K\nbatch size took much more time due to server compression time and thus\nwe should avoid large batch sizes like this.\n\nBased on these experiments, a batch size of 50,000 was chosen as the\ndefault value.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 11 ++++++++++-\n builtin/backfill.c | 10 ++++++----\n t/t5620-backfill.sh | 18 ++++++++++++++++++\n 3 files changed, 34 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex ece887831f6..e392517869c 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [verse]\n-'git backfill' []\n+'git backfill' [--batch-size=]\n \n DESCRIPTION\n -----------\n@@ -45,6 +45,15 @@ time.\n By default, `git backfill` downloads all blobs reachable from the `HEAD`\n commit. This set can be restricted or expanded using various options.\n \n+OPTIONS\n+-------\n+\n+--min-batch-size=::\n+\tSpecify a minimum size for a batch of missing objects to request\n+\tfrom the server. This size may be exceeded by the last set of\n+\tblobs seen at a given path. The default minimum batch size is\n+\t50,000.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 177fd4286c7..ddccececc36 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -21,14 +21,14 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill []\"),\n+\tN_(\"git backfill [--batch-size=]\"),\n \tNULL\n };\n \n struct backfill_context {\n \tstruct repository *repo;\n \tstruct oid_array current_batch;\n-\tsize_t batch_size;\n+\tsize_t min_batch_size;\n };\n \n static void backfill_context_clear(struct backfill_context *ctx)\n@@ -72,7 +72,7 @@ static int fill_missing_blobs(const char *path UNUSED,\n \t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n \t}\n \n-\tif (ctx->current_batch.nr >= ctx->batch_size)\n+\tif (ctx->current_batch.nr >= ctx->min_batch_size)\n \t\tdownload_batch(ctx);\n \n \treturn 0;\n@@ -111,9 +111,11 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \tstruct backfill_context ctx = {\n \t\t.repo = repo,\n \t\t.current_batch = OID_ARRAY_INIT,\n-\t\t.batch_size = 50000,\n+\t\t.min_batch_size = 50000,\n \t};\n \tstruct option options[] = {\n+\t\tOPT_INTEGER(0, \"min-batch-size\", &ctx.min_batch_size,\n+\t\t\t N_(\"Minimum number of objects to request at a time\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 64326362d80..36107a51c54 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -59,6 +59,24 @@ test_expect_success 'do partial clone 1, backfill gets all objects' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'do partial clone 2, backfill min batch size' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill2 &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/batch-trace\" git \\\n+\t\t-C backfill2 backfill --min-batch-size=20 &&\n+\n+\t# Batches were used\n+\ttest_trace2_data promisor fetch_count 20 matches &&\n+\ttest_line_count = 2 matches &&\n+\ttest_trace2_data promisor fetch_count 8 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \n-- \ngitgitgadget\n\n"},{"id":"509422","messageId":"2723143afb397507cbc794375525c37497046dc2.1734712193.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","subject":"[PATCH v2 4/5] backfill: add --sparse option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-20T16:29:52Z","receivedAt":"2024-12-20T16:30:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nOne way to significantly reduce the cost of a Git clone and later fetches is\nto use a blobless partial clone and combine that with a sparse-checkout that\nreduces the paths that need to be populated in the working directory. Not\nonly does this reduce the cost of clones and fetches, the sparse-checkout\nreduces the number of objects needed to download from a promisor remote.\n\nHowever, history investigations can be expensive as computing blob diffs\nwill trigger promisor remote requests for one object at a time. This can be\navoided by downloading the blobs needed for the given sparse-checkout using\n'git backfill' and its new '--sparse' mode, at a time that the user is\nwilling to pay that extra cost.\n\nNote that this is distinctly different from the '--filter=sparse:'\noption, as this assumes that the partial clone has all reachable trees and\nwe are using client-side logic to avoid downloading blobs outside of the\nsparse-checkout cone. This avoids the server-side cost of walking trees\nwhile also achieving a similar goal. It also downloads in batches based on\nsimilar path names, presenting a resumable download if things are\ninterrupted.\n\nThis augments the path-walk API to have a possibly-NULL 'pl' member that may\npoint to a 'struct pattern_list'. This could be more general than the\nsparse-checkout definition at HEAD, but 'git backfill --sparse' is currently\nthe only consumer.\n\nBe sure to test this in both cone mode and not cone mode. Cone mode has the\nbenefit that the path-walk can skip certain paths once they would expand\nbeyond the sparse-checkout.\n\nTo test this, we can create a blobless sparse clone, expand the\nsparse-checkout slightly, and then run 'git backfill --sparse' to see\nhow much data is downloaded. The general steps are\n\n 1. git clone --filter=blob:none --sparse \n 2. git sparse-checkout set ... \n 3. git backfill --sparse\n\nFor the Git repository with the 'builtin' directory in the\nsparse-checkout, we get these results for various batch sizes:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|-------|\n| (Initial clone) | 3 | 110 MB | |\n| 10K | 12 | 192 MB | 17.2s |\n| 15K | 9 | 192 MB | 15.5s |\n| 20K | 8 | 192 MB | 15.5s |\n| 25K | 7 | 192 MB | 14.7s |\n\nThis case matters less because a full clone of the Git repository from\nGitHub is currently at 277 MB.\n\nUsing a copy of the Linux repository with the 'kernel/' directory in the\nsparse-checkout, we get these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|------|\n| (Initial clone) | 2 | 1,876 MB | |\n| 10K | 11 | 2,187 MB | 46s |\n| 25K | 7 | 2,188 MB | 43s |\n| 50K | 5 | 2,194 MB | 44s |\n| 100K | 4 | 2,194 MB | 48s |\n\nThis case is more meaningful because a full clone of the Linux\nrepository is currently over 6 GB, so this is a valuable way to download\na fraction of the repository and no longer need network access for all\nreachable objects within the sparse-checkout.\n\nChoosing a batch size will depend on a lot of factors, including the\nuser's network speed or reliability, the repository's file structure,\nand how many versions there are of the file within the sparse-checkout\nscope. There will not be a one-size-fits-all solution.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 6 ++-\n Documentation/technical/api-path-walk.txt | 8 ++++\n builtin/backfill.c | 15 ++++++-\n dir.c | 10 ++---\n dir.h | 3 ++\n path-walk.c | 28 +++++++++---\n path-walk.h | 11 +++++\n t/helper/test-path-walk.c | 22 ++++++++-\n t/t5620-backfill.sh | 55 +++++++++++++++++++++++\n t/t6601-path-walk.sh | 32 +++++++++++++\n 10 files changed, 175 insertions(+), 15 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex e392517869c..4710e2c12e3 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [verse]\n-'git backfill' [--batch-size=]\n+'git backfill' [--batch-size=] [--[no-]sparse]\n \n DESCRIPTION\n -----------\n@@ -54,6 +54,10 @@ OPTIONS\n \tblobs seen at a given path. The default minimum batch size is\n \t50,000.\n \n+--[no-]sparse::\n+\tOnly download objects if they appear at a path that matches the\n+\tcurrent sparse-checkout.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 1fba0ce04cb..3e089211fb4 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -56,6 +56,14 @@ better off using the revision walk API instead.\n \tthe revision walk so that the walk emits commits marked with the\n \t`UNINTERESTING` flag.\n \n+`pl`::\n+\tThis pattern list pointer allows focusing the path-walk search to\n+\ta set of patterns, only emitting paths that match the given\n+\tpatterns. See linkgit:gitignore[5] or\n+\tlinkgit:git-sparse-checkout[1] for details about pattern lists.\n+\tWhen the pattern list uses cone-mode patterns, then the path-walk\n+\tAPI can prune the set of paths it walks to improve performance.\n+\n Examples\n --------\n \ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex ddccececc36..b9f1cc98501 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"repository.h\"\n #include \"commit.h\"\n+#include \"dir.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -21,7 +22,7 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill [--batch-size=]\"),\n+\tN_(\"git backfill [--batch-size=] [--[no-]sparse]\"),\n \tNULL\n };\n \n@@ -29,6 +30,7 @@ struct backfill_context {\n \tstruct repository *repo;\n \tstruct oid_array current_batch;\n \tsize_t min_batch_size;\n+\tint sparse;\n };\n \n static void backfill_context_clear(struct backfill_context *ctx)\n@@ -84,6 +86,14 @@ static int do_backfill(struct backfill_context *ctx)\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tint ret;\n \n+\tif (ctx->sparse) {\n+\t\tCALLOC_ARRAY(info.pl, 1);\n+\t\tif (get_sparse_checkout_patterns(info.pl)) {\n+\t\t\tpath_walk_info_clear(&info);\n+\t\t\treturn error(_(\"problem loading sparse-checkout\"));\n+\t\t}\n+\t}\n+\n \trepo_init_revisions(ctx->repo, &revs, \"\");\n \thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n \n@@ -112,10 +122,13 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \t\t.repo = repo,\n \t\t.current_batch = OID_ARRAY_INIT,\n \t\t.min_batch_size = 50000,\n+\t\t.sparse = 0,\n \t};\n \tstruct option options[] = {\n \t\tOPT_INTEGER(0, \"min-batch-size\", &ctx.min_batch_size,\n \t\t\t N_(\"Minimum number of objects to request at a time\")),\n+\t\tOPT_BOOL(0, \"sparse\", &ctx.sparse,\n+\t\t\t N_(\"Restrict the missing objects to the current sparse-checkout\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/dir.c b/dir.c\nindex c43b5e30813..32af7ee294d 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -1088,10 +1088,6 @@ static void invalidate_directory(struct untracked_cache *uc,\n \t\tdir->dirs[i]->recurse = 0;\n }\n \n-static int add_patterns_from_buffer(char *buf, size_t size,\n-\t\t\t\t const char *base, int baselen,\n-\t\t\t\t struct pattern_list *pl);\n-\n /* Flags for add_patterns() */\n #define PATTERN_NOFOLLOW (1<<0)\n \n@@ -1181,9 +1177,9 @@ static int add_patterns(const char *fname, const char *base, int baselen,\n \treturn 0;\n }\n \n-static int add_patterns_from_buffer(char *buf, size_t size,\n-\t\t\t\t const char *base, int baselen,\n-\t\t\t\t struct pattern_list *pl)\n+int add_patterns_from_buffer(char *buf, size_t size,\n+\t\t\t const char *base, int baselen,\n+\t\t\t struct pattern_list *pl)\n {\n \tchar *orig = buf;\n \tint i, lineno = 1;\ndiff --git a/dir.h b/dir.h\nindex a3a2f00f5d9..6cfef5df660 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -467,6 +467,9 @@ void add_patterns_from_file(struct dir_struct *, const char *fname);\n int add_patterns_from_blob_to_list(struct object_id *oid,\n \t\t\t\t const char *base, int baselen,\n \t\t\t\t struct pattern_list *pl);\n+int add_patterns_from_buffer(char *buf, size_t size,\n+\t\t\t const char *base, int baselen,\n+\t\t\t struct pattern_list *pl);\n void parse_path_pattern(const char **string, int *patternlen, unsigned *flags, int *nowildcardlen);\n void add_pattern(const char *string, const char *base,\n \t\t int baselen, struct pattern_list *pl, int srcpos);\ndiff --git a/path-walk.c b/path-walk.c\nindex 136ec08fb0e..c7456a9c1c0 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -12,6 +12,7 @@\n #include \"object.h\"\n #include \"oid-array.h\"\n #include \"prio-queue.h\"\n+#include \"repository.h\"\n #include \"revision.h\"\n #include \"string-list.h\"\n #include \"strmap.h\"\n@@ -173,6 +174,23 @@ static int add_tree_entries(struct path_walk_context *ctx,\n \t\tif (type == OBJ_TREE)\n \t\t\tstrbuf_addch(&path, '/');\n \n+\t\tif (ctx->info->pl) {\n+\t\t\tint dtype;\n+\t\t\tenum pattern_match_result match;\n+\t\t\tmatch = path_matches_pattern_list(path.buf, path.len,\n+\t\t\t\t\t\t\t path.buf + base_len, &dtype,\n+\t\t\t\t\t\t\t ctx->info->pl,\n+\t\t\t\t\t\t\t ctx->repo->index);\n+\n+\t\t\tif (ctx->info->pl->use_cone_patterns &&\n+\t\t\t match == NOT_MATCHED)\n+\t\t\t\tcontinue;\n+\t\t\telse if (!ctx->info->pl->use_cone_patterns &&\n+\t\t\t\t type == OBJ_BLOB &&\n+\t\t\t\t match != MATCHED)\n+\t\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) {\n \t\t\tCALLOC_ARRAY(list, 1);\n \t\t\tlist->type = type;\n@@ -583,10 +601,10 @@ void path_walk_info_init(struct path_walk_info *info)\n \tmemcpy(info, &empty, sizeof(empty));\n }\n \n-void path_walk_info_clear(struct path_walk_info *info UNUSED)\n+void path_walk_info_clear(struct path_walk_info *info)\n {\n-\t/*\n-\t * This destructor is empty for now, as info->revs\n-\t * is not owned by 'struct path_walk_info'.\n-\t */\n+\tif (info->pl) {\n+\t\tclear_pattern_list(info->pl);\n+\t\tfree(info->pl);\n+\t}\n }\ndiff --git a/path-walk.h b/path-walk.h\nindex 414d6db23c2..473ee9d361c 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -6,6 +6,7 @@\n \n struct rev_info;\n struct oid_array;\n+struct pattern_list;\n \n /**\n * The type of a function pointer for the method that is called on a list of\n@@ -48,6 +49,16 @@ struct path_walk_info {\n \t * walk the children of such trees.\n \t */\n \tint prune_all_uninteresting;\n+\n+\t/**\n+\t * Specify a sparse-checkout definition to match our paths to. Do not\n+\t * walk outside of this sparse definition. If the patterns are in\n+\t * cone mode, then the search may prune directories that are outside\n+\t * of the cone. If not in cone mode, then all tree paths will be\n+\t * explored but the path_fn will only be called when the path matches\n+\t * the sparse-checkout patterns.\n+\t */\n+\tstruct pattern_list *pl;\n };\n \n #define PATH_WALK_INFO_INIT { \\\ndiff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\nindex 7f2d409c5bc..61e845e5ec2 100644\n--- a/t/helper/test-path-walk.c\n+++ b/t/helper/test-path-walk.c\n@@ -1,6 +1,7 @@\n #define USE_THE_REPOSITORY_VARIABLE\n \n #include \"test-tool.h\"\n+#include \"dir.h\"\n #include \"environment.h\"\n #include \"hex.h\"\n #include \"object-name.h\"\n@@ -9,6 +10,7 @@\n #include \"revision.h\"\n #include \"setup.h\"\n #include \"parse-options.h\"\n+#include \"strbuf.h\"\n #include \"path-walk.h\"\n #include \"oid-array.h\"\n \n@@ -65,7 +67,7 @@ static int emit_block(const char *path, struct oid_array *oids,\n \n int cmd__path_walk(int argc, const char **argv)\n {\n-\tint res;\n+\tint res, stdin_pl = 0;\n \tstruct rev_info revs = REV_INFO_INIT;\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tstruct path_walk_test_data data = { 0 };\n@@ -80,6 +82,8 @@ int cmd__path_walk(int argc, const char **argv)\n \t\t\t N_(\"toggle inclusion of tree objects\")),\n \t\tOPT_BOOL(0, \"prune\", &info.prune_all_uninteresting,\n \t\t\t N_(\"toggle pruning of uninteresting paths\")),\n+\t\tOPT_BOOL(0, \"stdin-pl\", &stdin_pl,\n+\t\t\t N_(\"read a pattern list over stdin\")),\n \t\tOPT_END(),\n \t};\n \n@@ -99,6 +103,17 @@ int cmd__path_walk(int argc, const char **argv)\n \tinfo.path_fn = emit_block;\n \tinfo.path_fn_data = &data;\n \n+\tif (stdin_pl) {\n+\t\tstruct strbuf in = STRBUF_INIT;\n+\t\tCALLOC_ARRAY(info.pl, 1);\n+\n+\t\tinfo.pl->use_cone_patterns = 1;\n+\n+\t\tstrbuf_fread(&in, 2048, stdin);\n+\t\tadd_patterns_from_buffer(in.buf, in.len, \"\", 0, info.pl);\n+\t\tstrbuf_release(&in);\n+\t}\n+\n \tres = walk_objects_by_path(&info);\n \n \tprintf(\"commits:%\" PRIuMAX \"\\n\"\n@@ -107,6 +122,11 @@ int cmd__path_walk(int argc, const char **argv)\n \t \"tags:%\" PRIuMAX \"\\n\",\n \t data.commit_nr, data.tree_nr, data.blob_nr, data.tag_nr);\n \n+\tif (info.pl) {\n+\t\tclear_pattern_list(info.pl);\n+\t\tfree(info.pl);\n+\t}\n+\n \trelease_revisions(&revs);\n \treturn res;\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 36107a51c54..f87a471c221 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -77,6 +77,61 @@ test_expect_success 'do partial clone 2, backfill min batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse' '\n+\tgit clone --sparse --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill3 &&\n+\n+\t# Initial checkout includes four files at root.\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 44 missing &&\n+\n+\t# Initial sparse-checkout is just the files at root, so we get the\n+\t# older versions of the four files at tip.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace1\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 4 missing &&\n+\ttest_line_count = 40 missing &&\n+\n+\t# Expand the sparse-checkout to include 'd' recursively. This\n+\t# engages the algorithm to skip the trees for 'a'. Note that\n+\t# the \"sparse-checkout set\" command downloads the objects at tip\n+\t# to satisfy the current checkout.\n+\tgit -C backfill3 sparse-checkout set d &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace2\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 8 missing &&\n+\ttest_line_count = 24 missing\n+'\n+\n+test_expect_success 'backfill --sparse without cone mode' '\n+\tgit clone --no-checkout --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill4 &&\n+\n+\t# No blobs yet\n+\tgit -C backfill4 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 48 missing &&\n+\n+\t# Define sparse-checkout by filename regardless of parent directory.\n+\t# This downloads 6 blobs to satisfy the checkout.\n+\tgit -C backfill4 sparse-checkout set --no-cone \"**/file.1.txt\" &&\n+\tgit -C backfill4 checkout main &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/no-cone-trace1\" git \\\n+\t\t-C backfill4 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 6 missing &&\n+\ttest_line_count = 36 missing\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \ndiff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh\nindex 5f04acb8a2f..c89b0f1e19d 100755\n--- a/t/t6601-path-walk.sh\n+++ b/t/t6601-path-walk.sh\n@@ -176,6 +176,38 @@ test_expect_success 'branches and indexed objects mix well' '\n \ttest_cmp_sorted expect out\n '\n \n+test_expect_success 'base & topic, sparse' '\n+\tcat >patterns <<-EOF &&\n+\t/*\n+\t!/*/\n+\t/left/\n+\tEOF\n+\n+\ttest-tool path-walk --stdin-pl -- base topic out &&\n+\n+\tcat >expect <<-EOF &&\n+\t0:commit::$(git rev-parse topic)\n+\t0:commit::$(git rev-parse base)\n+\t0:commit::$(git rev-parse base~1)\n+\t0:commit::$(git rev-parse base~2)\n+\t1:tree::$(git rev-parse topic^{tree})\n+\t1:tree::$(git rev-parse base^{tree})\n+\t1:tree::$(git rev-parse base~1^{tree})\n+\t1:tree::$(git rev-parse base~2^{tree})\n+\t2:blob:a:$(git rev-parse base~2:a)\n+\t3:tree:left/:$(git rev-parse base:left)\n+\t3:tree:left/:$(git rev-parse base~2:left)\n+\t4:blob:left/b:$(git rev-parse base~2:left/b)\n+\t4:blob:left/b:$(git rev-parse base:left/b)\n+\tblobs:3\n+\tcommits:4\n+\ttags:0\n+\ttrees:6\n+\tEOF\n+\n+\ttest_cmp_sorted expect out\n+'\n+\n test_expect_success 'topic only' '\n \ttest-tool path-walk -- topic >out &&\n \n-- \ngitgitgadget\n\n"},{"id":"509423","messageId":"1f765409eaf0576de52948ed0a0eb8a5b3493977.1734712194.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","subject":"[PATCH v2 5/5] backfill: assume --sparse when sparse-checkout is enabled","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-12-20T16:29:53Z","receivedAt":"2024-12-20T16:30:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change introduced the '--[no-]sparse' option for the 'git\nbackfill' command, but did not assume it as enabled by default. However,\nthis is likely the behavior that users will most often want to happen.\nWithout this default, users with a small sparse-checkout may be confused\nwhen 'git backfill' downloads every version of every object in the full\nhistory.\n\nHowever, this is left as a separate change so this decision can be reviewed\nindependently of the value of the '--[no-]sparse' option.\n\nAdd a test of adding the '--sparse' option to a repo without sparse-checkout\nto make it clear that supplying it without a sparse-checkout is an error.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 3 ++-\n builtin/backfill.c | 7 +++++++\n t/t5620-backfill.sh | 13 ++++++++++++-\n 3 files changed, 21 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 4710e2c12e3..9eecc6210c0 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -56,7 +56,8 @@ OPTIONS\n \n --[no-]sparse::\n \tOnly download objects if they appear at a path that matches the\n-\tcurrent sparse-checkout.\n+\tcurrent sparse-checkout. If the sparse-checkout feature is enabled,\n+\tthen `--sparse` is assumed and can be disabled with `--no-sparse`.\n \n SEE ALSO\n --------\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex b9f1cc98501..d7c300dbe67 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -1,3 +1,6 @@\n+/* We need this macro to access core_apply_sparse_checkout */\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n #include \"builtin.h\"\n #include \"git-compat-util.h\"\n #include \"config.h\"\n@@ -5,6 +8,7 @@\n #include \"repository.h\"\n #include \"commit.h\"\n #include \"dir.h\"\n+#include \"environment.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -140,5 +144,8 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \n \trepo_config(repo, git_default_config, NULL);\n \n+\tif (ctx.sparse < 0)\n+\t\tctx.sparse = core_apply_sparse_checkout;\n+\n \treturn do_backfill(&ctx);\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex f87a471c221..3fafcf99b58 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -77,6 +77,12 @@ test_expect_success 'do partial clone 2, backfill min batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse without sparse-checkout fails' '\n+\tgit init not-sparse &&\n+\ttest_must_fail git -C not-sparse backfill --sparse 2>err &&\n+\tgrep \"problem loading sparse-checkout\" err\n+'\n+\n test_expect_success 'backfill --sparse' '\n \tgit clone --sparse --filter=blob:none\t\t\\\n \t\t--single-branch --branch=main \t\t\\\n@@ -105,7 +111,12 @@ test_expect_success 'backfill --sparse' '\n \ttest_trace2_data promisor fetch_count 8 missing &&\n-\ttest_line_count = 24 missing\n+\ttest_line_count = 24 missing &&\n+\n+\t# Disabling the --sparse option (on by default) will download everything\n+\tgit -C backfill3 backfill --no-sparse &&\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 0 missing\n '\n \n test_expect_success 'backfill --sparse without cone mode' '\n-- \ngitgitgadget\n"},{"id":"510654","messageId":"Z4jY2Bj-e8i9Zuig@pks.im","threadId":"62610","inReplyTo":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-01-16T10:00:56Z","receivedAt":"2025-01-16T10:01:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 20, 2024 at 04:29:48PM +0000, Derrick Stolee via GitGitGadget wrote:\n> This is based on v4 of ds/path-walk-1 [1] and an earlier version was part of\n> my initial path-walk RFC [2].\n\nI've got a couple more nits, but other than that I think that this\nseries looks quite nice.\n\nI was wondering whether we might want to mark the new command as\nexperimental at first to allow us to iterate, but the last set of\ncommands where we have done so are still experimental many years after\nthey have been introduced. So... probably not a good idea.\n\nPatrick\n"},{"id":"510655","messageId":"Z4jY3EQbC42scEIF@pks.im","threadId":"62610","inReplyTo":"e4e88794cae7edc568dd054b1376caac7fd30076.1734712193.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/5] backfill: basic functionality and tests","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-01-16T10:01:00Z","receivedAt":"2025-01-16T10:01:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 20, 2024 at 04:29:50PM +0000, Derrick Stolee via GitGitGadget wrote:\n> diff --git a/builtin/backfill.c b/builtin/backfill.c\n> index 38e6aaeaa03..177fd4286c7 100644\n> --- a/builtin/backfill.c\n> +++ b/builtin/backfill.c\n[snip]\n> +static int fill_missing_blobs(const char *path UNUSED,\n> +\t\t\t struct oid_array *list,\n> +\t\t\t enum object_type type,\n> +\t\t\t void *data)\n> +{\n> +\tstruct backfill_context *ctx = data;\n> +\n> +\tif (type != OBJ_BLOB)\n> +\t\treturn 0;\n> +\n> +\tfor (size_t i = 0; i < list->nr; i++) {\n> +\t\toff_t size = 0;\n> +\t\tstruct object_info info = OBJECT_INFO_INIT;\n> +\t\tinfo.disk_sizep = &size;\n> +\t\tif (oid_object_info_extended(ctx->repo,\n> +\t\t\t\t\t &list->oid[i],\n> +\t\t\t\t\t &info,\n> +\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH) ||\n> +\t\t !size)\n\nSo this is the object existence test? Is there a reason why we don't use\n`repo_has_object_file()`, or its `_with_flags()` variant if we need to\npass `OBJECT_INFO_FOR_PREFETCH`?\n\n> +\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n> +\t}\n> +\n> +\tif (ctx->current_batch.nr >= ctx->batch_size)\n> +\t\tdownload_batch(ctx);\n> +\n> +\treturn 0;\n> +}\n> +\n> +static int do_backfill(struct backfill_context *ctx)\n> +{\n> +\tstruct rev_info revs;\n> +\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n> +\tint ret;\n> +\n> +\trepo_init_revisions(ctx->repo, &revs, \"\");\n> +\thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n> +\n> +\tinfo.blobs = 1;\n> +\tinfo.tags = info.commits = info.trees = 0;\n\nNit: this should be unnecessary as PATH_WALK_INFO_INIT already\ninitialized those fields for us, right?\n\n> +\tinfo.revs = &revs;\n> +\tinfo.path_fn = fill_missing_blobs;\n> +\tinfo.path_fn_data = ctx;\n> +\n> +\tret = walk_objects_by_path(&info);\n> +\n> +\t/* Download the objects that did not fill a batch. */\n> +\tif (!ret)\n> +\t\tdownload_batch(ctx);\n> +\n> +\tbackfill_context_clear(ctx);\n\nNit: I think it's a bit funny that we're cleaning up the context over\nhere rather than in the caller.\n\nPatrick\n"},{"id":"510656","messageId":"Z4jY34vmK1yj0Mzi@pks.im","threadId":"62610","inReplyTo":"3fa32822dabb64266a0625c50530ae2ae0797de6.1734712193.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/5] backfill: add --min-batch-size= option","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-01-16T10:01:03Z","receivedAt":"2025-01-16T10:01:08Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 20, 2024 at 04:29:51PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> Users may want to specify a minimum batch size for their needs. This is only\n> a minimum: the path-walk API provides a list of OIDs that correspond to the\n> same path, and thus it is optimal to allow delta compression across those\n> objects in a single server request.\n> \n> We could consider limiting the request to have a maximum batch size in the\n> future. For now, we let the path-walk API batches determine the\n> boundaries.\n> \n> To get a feeling for the value of specifying the --batch-size parameter,\n\nThis should say `--min-batch-size`.\n\n> diff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\n> index ece887831f6..e392517869c 100644\n> --- a/Documentation/git-backfill.txt\n> +++ b/Documentation/git-backfill.txt\n> @@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n> SYNOPSIS\n> --------\n> [verse]\n> -'git backfill' []\n> +'git backfill' [--batch-size=]\n> \n> DESCRIPTION\n> -----------\n\nHere, as well.\n\n> diff --git a/builtin/backfill.c b/builtin/backfill.c\n> index 177fd4286c7..ddccececc36 100644\n> --- a/builtin/backfill.c\n> +++ b/builtin/backfill.c\n> @@ -21,14 +21,14 @@\n> #include \"path-walk.h\"\n> \n> static const char * const builtin_backfill_usage[] = {\n> -\tN_(\"git backfill []\"),\n> +\tN_(\"git backfill [--batch-size=]\"),\n\nAnd here.\n\n> @@ -111,9 +111,11 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n> \tstruct backfill_context ctx = {\n> \t\t.repo = repo,\n> \t\t.current_batch = OID_ARRAY_INIT,\n> -\t\t.batch_size = 50000,\n> +\t\t.min_batch_size = 50000,\n> \t};\n\nNit: it would be nice to adjust the name of this variable in the\npreceding commit already so that it doesn't have to change again over\nhere.\n\nPatrick\n"},{"id":"510657","messageId":"Z4jY4rELRYvS2gOk@pks.im","threadId":"62610","inReplyTo":"2723143afb397507cbc794375525c37497046dc2.1734712193.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 4/5] backfill: add --sparse option","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-01-16T10:01:06Z","receivedAt":"2025-01-16T10:01:12Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 20, 2024 at 04:29:52PM +0000, Derrick Stolee via GitGitGadget wrote:\n> diff --git a/path-walk.c b/path-walk.c\n> index 136ec08fb0e..c7456a9c1c0 100644\n> --- a/path-walk.c\n> +++ b/path-walk.c\n> @@ -12,6 +12,7 @@\n> #include \"object.h\"\n> #include \"oid-array.h\"\n> #include \"prio-queue.h\"\n> +#include \"repository.h\"\n> #include \"revision.h\"\n> #include \"string-list.h\"\n> #include \"strmap.h\"\n> @@ -173,6 +174,23 @@ static int add_tree_entries(struct path_walk_context *ctx,\n> \t\tif (type == OBJ_TREE)\n> \t\t\tstrbuf_addch(&path, '/');\n> \n> +\t\tif (ctx->info->pl) {\n> +\t\t\tint dtype;\n> +\t\t\tenum pattern_match_result match;\n> +\t\t\tmatch = path_matches_pattern_list(path.buf, path.len,\n> +\t\t\t\t\t\t\t path.buf + base_len, &dtype,\n> +\t\t\t\t\t\t\t ctx->info->pl,\n> +\t\t\t\t\t\t\t ctx->repo->index);\n> +\n> +\t\t\tif (ctx->info->pl->use_cone_patterns &&\n> +\t\t\t match == NOT_MATCHED)\n> +\t\t\t\tcontinue;\n> +\t\t\telse if (!ctx->info->pl->use_cone_patterns &&\n> +\t\t\t\t type == OBJ_BLOB &&\n> +\t\t\t\t match != MATCHED)\n\nFor my own understanding: is there as pecific reason why one of the\nbranches uses `== NOT_MATCHED` whereas the other one uses `!= MATCHED`?\n\n> diff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\n> index 7f2d409c5bc..61e845e5ec2 100644\n> --- a/t/helper/test-path-walk.c\n> +++ b/t/helper/test-path-walk.c\n> @@ -65,7 +67,7 @@ static int emit_block(const char *path, struct oid_array *oids,\n> \n> int cmd__path_walk(int argc, const char **argv)\n> {\n> -\tint res;\n> +\tint res, stdin_pl = 0;\n> \tstruct rev_info revs = REV_INFO_INIT;\n> \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n> \tstruct path_walk_test_data data = { 0 };\n> @@ -80,6 +82,8 @@ int cmd__path_walk(int argc, const char **argv)\n> \t\t\t N_(\"toggle inclusion of tree objects\")),\n> \t\tOPT_BOOL(0, \"prune\", &info.prune_all_uninteresting,\n> \t\t\t N_(\"toggle pruning of uninteresting paths\")),\n> +\t\tOPT_BOOL(0, \"stdin-pl\", &stdin_pl,\n> +\t\t\t N_(\"read a pattern list over stdin\")),\n> \t\tOPT_END(),\n> \t};\n> \n\nI was about to suggest giving this a more descriptive name, as it might\nbe confusing for anybody not intimately familiar with the code. But then\nI noticed that this is part of the test helper, only, so it doesn't\nmatter as much. So feel free to ignore.\n\nPatrick\n"},{"id":"510670","messageId":"Z4jbW7UtaC7hQU1Z@pks.im","threadId":"62610","inReplyTo":"0300aa1b8c37dcd0d529cc24588ae77960fdfbff.1733515638.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/5] backfill: add builtin boilerplate","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-01-16T10:11:39Z","receivedAt":"2025-01-16T10:11:44Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 06, 2024 at 08:07:14PM +0000, Derrick Stolee via GitGitGadget wrote:\n> diff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\n> new file mode 100644\n> index 00000000000..640144187d3\n> --- /dev/null\n> +++ b/Documentation/git-backfill.txt\n> @@ -0,0 +1,23 @@\n> +git-backfill(1)\n> +===============\n> +\n> +NAME\n> +----\n> +git-backfill - Download missing objects in a partial clone\n> +\n> +\n> +SYNOPSIS\n> +--------\n> +[verse]\n> +'git backfill' []\n\nAh, one thing I forgot about: this could use the new `[synopsis]` style,\nwhich removes some need for formatting directives.\n\nPatrick\n"},{"id":"510723","messageId":"xmqqfrlisl23.fsf@gitster.g","threadId":"62610","inReplyTo":"Z4jbW7UtaC7hQU1Z@pks.im","subject":"Re: [PATCH 1/5] backfill: add builtin boilerplate","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-01-16T17:52:36Z","receivedAt":"2025-01-16T17:52:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> On Fri, Dec 06, 2024 at 08:07:14PM +0000, Derrick Stolee via GitGitGadget wrote:\n>> diff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\n>> new file mode 100644\n>> index 00000000000..640144187d3\n>> --- /dev/null\n>> +++ b/Documentation/git-backfill.txt\n>> @@ -0,0 +1,23 @@\n>> +git-backfill(1)\n>> +===============\n>> +\n>> +NAME\n>> +----\n>> +git-backfill - Download missing objects in a partial clone\n>> +\n>> +\n>> +SYNOPSIS\n>> +--------\n>> +[verse]\n>> +'git backfill' []\n>\n> Ah, one thing I forgot about: this could use the new `[synopsis]` style,\n> which removes some need for formatting directives.\n\nYeah, I thought it was more or less simultaneous development and it\nwas OK to convert after the dust settles, but it seems to predate\nthe series by 3 months.\n\n$ git show -s --format=reference 029eff9e34f 375852e20\n029eff9e34 (doc: update the guidelines to reflect the current formatting rules, 2024-09-24)\n375852e20f (backfill: add builtin boilerplate, 2024-12-20)\n\nds/backfill:Documentation/CodingGuidelines does tell us '[synopsis]'\nis available, even ;-)\n\nThanks for noticing.\n"},{"id":"510851","messageId":"xmqqsephhxs0.fsf@gitster.g","threadId":"62610","inReplyTo":"Z4jY2Bj-e8i9Zuig@pks.im","subject":"Re: [PATCH v2 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-01-17T22:37:51Z","receivedAt":"2025-01-17T22:37:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> I was wondering whether we might want to mark the new command as\n> experimental at first to allow us to iterate, but the last set of\n> commands where we have done so are still experimental many years after\n> they have been introduced. So... probably not a good idea.\n\nI am not sure if I agree. Anybody who wants any of these commands\nthat are marked as experimental to be declared stable can propose\nto do so with a reasonable timeline attached.\n"},{"id":"510911","messageId":"2972493.e9J7NaK4W3@cayenne","threadId":"62610","inReplyTo":"3cfd23073a036ea426569769b3e31290076257a6.1733515638.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/5] backfill: add --batch-size= option","fromName":"Jean-Noël AVILA","fromEmail":"jn.avila@free.fr","sentAt":"2025-01-19T17:57:46Z","receivedAt":"2025-01-19T17:58:09Z","isPatch":true,"sender":{"key":"jn.avila@free.fr","avatar":"https://avatars.githubusercontent.com/u/156172?v=4"},"body":"On Friday, 6 December 2024 21:07:16 UTC+1 Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n\n> @@ -38,6 +38,14 @@ delta compression in the packfile sent by the server.\n> By default, `git backfill` downloads all blobs reachable from the `HEAD`\n> commit. This set can be restricted or expanded using various options.\n> \n> +OPTIONS\n> +-------\n> +\n> +--batch-size=::\n\nPlease format automatically using backticks: `--batch-size=`::\n\n> +\tSpecify a minimum size for a batch of missing objects to request\n> +\tfrom the server. This size may be exceeded by the last set of\n> +\tblobs seen at a given path. Default batch size is 16,000.\n> +\n> SEE ALSO\n> --------\n> linkgit:git-clone[1].\n\n\n\n\n"},{"id":"511736","messageId":"65e1bd7b-f388-424f-96dc-2df9b50540d2@gmail.com","threadId":"62610","inReplyTo":"xmqqfrlisl23.fsf@gitster.g","subject":"Re: [PATCH 1/5] backfill: add builtin boilerplate","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-02-03T14:38:40Z","receivedAt":"2025-02-03T14:38:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/16/25 12:52 PM, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n> \n>> On Fri, Dec 06, 2024 at 08:07:14PM +0000, Derrick Stolee via GitGitGadget wrote:\n>>> diff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\n>>> new file mode 100644\n>>> index 00000000000..640144187d3\n>>> --- /dev/null\n>>> +++ b/Documentation/git-backfill.txt\n>>> @@ -0,0 +1,23 @@\n>>> +git-backfill(1)\n>>> +===============\n>>> +\n>>> +NAME\n>>> +----\n>>> +git-backfill - Download missing objects in a partial clone\n>>> +\n>>> +\n>>> +SYNOPSIS\n>>> +--------\n>>> +[verse]\n>>> +'git backfill' []\n>>\n>> Ah, one thing I forgot about: this could use the new `[synopsis]` style,\n>> which removes some need for formatting directives.\n> \n> Yeah, I thought it was more or less simultaneous development and it\n> was OK to convert after the dust settles, but it seems to predate\n> the series by 3 months.\n> \n> $ git show -s --format=reference 029eff9e34f 375852e20\n> 029eff9e34 (doc: update the guidelines to reflect the current formatting rules, 2024-09-24)\n> 375852e20f (backfill: add builtin boilerplate, 2024-12-20)\n> \n> ds/backfill:Documentation/CodingGuidelines does tell us '[synopsis]'\n> is available, even ;-)\n\nThanks. I was not aware of this new style. Will be fixed in the next version.\n\nThanks,\n-Stolee\n\n"},{"id":"511737","messageId":"718583a4-31e6-45d4-9807-c5a07050b28f@gmail.com","threadId":"62610","inReplyTo":"Z4jY3EQbC42scEIF@pks.im","subject":"Re: [PATCH v2 2/5] backfill: basic functionality and tests","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-02-03T14:44:49Z","receivedAt":"2025-02-03T14:44:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/16/25 5:01 AM, Patrick Steinhardt wrote:\n> On Fri, Dec 20, 2024 at 04:29:50PM +0000, Derrick Stolee via GitGitGadget wrote:\n>> diff --git a/builtin/backfill.c b/builtin/backfill.c\n>> index 38e6aaeaa03..177fd4286c7 100644\n>> --- a/builtin/backfill.c\n>> +++ b/builtin/backfill.c\n> [snip]\n>> +static int fill_missing_blobs(const char *path UNUSED,\n>> +\t\t\t struct oid_array *list,\n>> +\t\t\t enum object_type type,\n>> +\t\t\t void *data)\n>> +{\n>> +\tstruct backfill_context *ctx = data;\n>> +\n>> +\tif (type != OBJ_BLOB)\n>> +\t\treturn 0;\n>> +\n>> +\tfor (size_t i = 0; i < list->nr; i++) {\n>> +\t\toff_t size = 0;\n>> +\t\tstruct object_info info = OBJECT_INFO_INIT;\n>> +\t\tinfo.disk_sizep = &size;\n>> +\t\tif (oid_object_info_extended(ctx->repo,\n>> +\t\t\t\t\t &list->oid[i],\n>> +\t\t\t\t\t &info,\n>> +\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH) ||\n>> +\t\t !size)\n> \n> So this is the object existence test? Is there a reason why we don't use\n> `repo_has_object_file()`, or its `_with_flags()` variant if we need to\n> pass `OBJECT_INFO_FOR_PREFETCH`?\n\nYou make a good point, but I also notice that repo_has_object_file() has\nthe following comment:\n\n * These functions can be removed once all callers have migrated to\n * has_object() and/or oid_object_info_extended().\n\nso I'll use has_object().\n\n>> +\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n>> +\t}\n>> +\n>> +\tif (ctx->current_batch.nr >= ctx->batch_size)\n>> +\t\tdownload_batch(ctx);\n>> +\n>> +\treturn 0;\n>> +}\n>> +\n>> +static int do_backfill(struct backfill_context *ctx)\n>> +{\n>> +\tstruct rev_info revs;\n>> +\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n>> +\tint ret;\n>> +\n>> +\trepo_init_revisions(ctx->repo, &revs, \"\");\n>> +\thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n>> +\n>> +\tinfo.blobs = 1;\n>> +\tinfo.tags = info.commits = info.trees = 0;\n> \n> Nit: this should be unnecessary as PATH_WALK_INFO_INIT already\n> initialized those fields for us, right?\n\nThe info.blobs is redundant, but is helpful for context. The\nother line is necessary as PATH_WALK_INFO_INIT is defined as:\n\n#define PATH_WALK_INFO_INIT { \\\n\t.blobs = 1,\t\t\\\n\t.trees = 1,\t\t\\\n\t.commits = 1,\t\t\\\n\t.tags = 1,\t\t\\\n}\n\n>> +\tinfo.revs = &revs;\n>> +\tinfo.path_fn = fill_missing_blobs;\n>> +\tinfo.path_fn_data = ctx;\n>> +\n>> +\tret = walk_objects_by_path(&info);\n>> +\n>> +\t/* Download the objects that did not fill a batch. */\n>> +\tif (!ret)\n>> +\t\tdownload_batch(ctx);\n>> +\n>> +\tbackfill_context_clear(ctx);\n> \n> Nit: I think it's a bit funny that we're cleaning up the context over\n> here rather than in the caller.\nCleaning up in the caller makes the \"return do_backfill(&ctx);\" line\nslightly more complicated, but you are right that we shouldn't be\ncleaning up something that the method \"doesn't own\".\n\nThanks,\n-Stolee\n\n"},{"id":"511740","messageId":"34379f16-9da6-440b-8656-5d580056c36b@gmail.com","threadId":"62610","inReplyTo":"Z4jY4rELRYvS2gOk@pks.im","subject":"Re: [PATCH v2 4/5] backfill: add --sparse option","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-02-03T15:11:28Z","receivedAt":"2025-02-03T15:11:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/16/25 5:01 AM, Patrick Steinhardt wrote:\n> On Fri, Dec 20, 2024 at 04:29:52PM +0000, Derrick Stolee via GitGitGadget wrote:\n\n>> +\t\tif (ctx->info->pl) {\n>> +\t\t\tint dtype;\n>> +\t\t\tenum pattern_match_result match;\n>> +\t\t\tmatch = path_matches_pattern_list(path.buf, path.len,\n>> +\t\t\t\t\t\t\t path.buf + base_len, &dtype,\n>> +\t\t\t\t\t\t\t ctx->info->pl,\n>> +\t\t\t\t\t\t\t ctx->repo->index);\n>> +\n>> +\t\t\tif (ctx->info->pl->use_cone_patterns &&\n>> +\t\t\t match == NOT_MATCHED)\n>> +\t\t\t\tcontinue;\n>> +\t\t\telse if (!ctx->info->pl->use_cone_patterns &&\n>> +\t\t\t\t type == OBJ_BLOB &&\n>> +\t\t\t\t match != MATCHED)\n> \n> For my own understanding: is there as pecific reason why one of the\n> branches uses `== NOT_MATCHED` whereas the other one uses `!= MATCHED`?\n\nWith cone mode sparse-checkout, 'match' could equal MATCHED,\nMATCHED_RECURSIVE, or UNDECIDED, which we want to be considered all the\nsame case: continue along this path.\n\nWhen not in cone mode, we can't decide to filter by trees (hence the\nOBJ_BLOB restriction) and then the result can be MATCHED, NOT_MATCHED,\nand UNDECIDED. This rule matches the following realization:\n\n * MATCHED if there is a positive pattern that matches the path.\n * NOT_MATCHED if there is a negative pattern that matches the path.\n * UNDECIDED if no pattern matches the path.\n\nThis is subtle, but switching this to \"match == NOT_MATCHED\" will\nresult in the test failing (and the test is right).\n\nI will make note of this in my commit message in the next version, as\nwell as adding a test that has nested positive and negative patterns.\n\nThanks,\n-Stolee\n\n"},{"id":"511750","messageId":"pull.1820.v3.git.1738602667.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v2.git.1734712193.gitgitgadget@gmail.com","subject":"[PATCH v3 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-02-03T17:11:02Z","receivedAt":"2025-02-03T17:11:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This is based on 'master' now that ds/path-walk [1] is merged. An earlier\nversion was part of my initial path-walk RFC [2].\n\n[1]\nhttps://lore.kernel.org/git/pull.1818.v3.git.1733514358.gitgitgadget@gmail.com/\n\n[2]\nhttps://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/\n\nThis series adds a new 'git backfill' command that uses the path-walk API to\ndownload missing blobs in a blobless partial clone. Users can specify\ninteraction with the sparse-checkout using '--[no-]sparse' but the\n'--sparse' option is implied by the existence of a sparse-checkout.\n\nThe reason to use the path-walk API is to make sure that the missing objects\nare grouped by a common path, giving a reasonable process for batching\nrequests and expecting the server to compress the resulting packfile nicely\ntogether.\n\nI first prototyped this feature in June 2024 as an exploration and created\nthe path-walk algorithm for this purpose. It was only my intuition that led\nme to believe that batching by path would lead to better packfiles. This has\nbeen proven out as a very important feature due to recent investigations to\ncompressing full repositories by doing a better job of grouping objects by\npath. See the --name-hash-version series [3] or the 'git pack-objects\n--path-walk' series [4] (currently on hold as it conflicts with the\n--name-hash-version series).\n\n[3]\nhttps://lore.kernel.org/git/pull.1823.v2.git.1733181682.gitgitgadget@gmail.com/\n\n[4]\nhttps://lore.kernel.org/git/pull.1813.v2.git.1729431810.gitgitgadget@gmail.com/\n\nThis idea can be further demonstrated by the evidence in testing this\nfeature: by downloading objects in small batch sizes, the client can force\nthe server to repack things more efficiently than a full repack.\n\nThe example repository I have used in multiple places is the\nmicrosoft/fluentui repo [5] as it has many CHANGELOG.md files that cause\nname hash collisions that make the full repack inefficient.\n\n[5] https://github.com/microsoft/fluentui\n\nIf we create a blobless clone of the fluentui repo, then this downloads 105\nMB across two packfiles (the commits and trees pack, followed by the blobs\nneeded for an initial checkout). Running 'git backfill --batch-size=' for\ndifferent sizes leads to some interesting results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 105 MB | |\n| 5K | 53 | 348 MB | 2m 26s |\n| 10K | 28 | 365 MB | 2m 22s |\n| 15K | 19 | 407 MB | 2m 21s |\n| 20K | 15 | 393 MB | 2m 28s |\n| 25K | 13 | 417 MB | 2m 06s |\n| 50K | 8 | 509 MB | 1m 34s |\n| 100K | 5 | 535 MB | 1m 56s |\n| 250K | 4 | 698 MB | 1m 33s |\n| 500K | 3 | 696 MB | 1m 42s |\n\n\nThe smaller batches cause the server to realize that the existing deltas\ncannot be reused and it finds better deltas. This takes some extra time for\nthe small batches, but halves the size of the repo. Even in the 500K batch\nsize, we get less data than the 738 MB of a full clone.\n\nImplementing the --sparse feature is best done by augmenting the path-walk\nAPI to be aware of a pattern list. This works for both cone and non-cone\nmode sparse-checkouts.\n\nThere are future directions we could take this command, especially to run\nthe command with a user-specified pathspec. The tricky case for that\nadditional feature is trying to make the path-walk more efficient by\nskipping tree paths that would not lead to a match of the pathspec. It would\nlikely need optimization in a small subset of pathspec features (such as\nprefix matches) to work as efficiently as possible. I did prototype a\nversion that puts the pathspec match in the callback function within\nbuiltin/backfill.c, but I found that uninspiring and unnecessary for now.\n\n\nUpdates in v2\n=============\n\nThanks for the review on v1.\n\n * Memory leaks should be plugged now due to the introduction of a\n destructor in v4 of the path-walk API and its extension here to clear the\n pattern list.\n\n * Documentation is expanded to demonstrate that 'git backfill' can also\n approximate incremental/resumable clones of repositories.\n\n * Method renames to better match style.\n\n * --batch-size is renamed to --min-batch-size for clarity and future\n extensibility.\n\n\nUpdates in v3\n=============\n\n * Rebased onto 'master' now that the path-walk API is merged.\n\n * New builtin boilerplate is updated with new standards, including:\n\n * Doc formatting uses [synopsis] formatting.\n * Add builtin/backfill.c to meson.build.\n * Add Documentation/git-backfill.txt to Documentation/meson.build.\n * Add t/t5620-backfill.sh to t/meson.build.\n * Update handling of -h due to f66d1423f5 (builtin: send usage() help text\n to standard output, 2025-01-16).\n\n * Doc formatting is updated to use back-ticks on options and mark the\n builtin as experimental.\n\n * The batch_size member of 'struct backfill_context' is now named\n 'min_batch_size' in all patches.\n\n * Some mentions of '--batch-size' are updated to '--min-batch-size'.\n\n * An additional test is included for non-cone-mode sparse-checkout patterns\n to further check the return values of path_matches_pattern_list() within\n the path-walk API with sparse mode.\n\n * A use of oid_object_info_extended() is replaced with has_object().\n\n * The backfill_context_clear() method is called by the proper owner of the\n struct.\n\nThanks, -Stolee\n\nDerrick Stolee (5):\n backfill: add builtin boilerplate\n backfill: basic functionality and tests\n backfill: add --min-batch-size= option\n backfill: add --sparse option\n backfill: assume --sparse when sparse-checkout is enabled\n\n .gitignore | 1 +\n Documentation/git-backfill.txt | 71 ++++++++\n Documentation/meson.build | 1 +\n Documentation/technical/api-path-walk.txt | 11 +-\n Makefile | 1 +\n builtin.h | 1 +\n builtin/backfill.c | 146 +++++++++++++++\n command-list.txt | 1 +\n dir.c | 10 +-\n dir.h | 3 +\n git.c | 1 +\n meson.build | 1 +\n path-walk.c | 28 ++-\n path-walk.h | 11 ++\n t/helper/test-path-walk.c | 22 ++-\n t/meson.build | 1 +\n t/t5620-backfill.sh | 211 ++++++++++++++++++++++\n t/t6601-path-walk.sh | 32 ++++\n 18 files changed, 539 insertions(+), 14 deletions(-)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 builtin/backfill.c\n create mode 100755 t/t5620-backfill.sh\n\n\nbase-commit: 58b5801aa94ad5031978f8e42c1be1230b3d352f\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1820%2Fderrickstolee%2Fbackfill-upstream-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1820/derrickstolee/backfill-upstream-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/1820\n\nRange-diff vs v2:\n\n 1: ac86510417a ! 1: 1612ad92455 backfill: add builtin boilerplate\n @@ Commit message\n backfill: add builtin boilerplate\n \n In anticipation of implementing 'git backfill', populate the necessary files\n - with the boilerplate of a new builtin.\n + with the boilerplate of a new builtin. Mark the builtin as experimental at\n + this time, allowing breaking changes in the near future, if necessary.\n \n Signed-off-by: Derrick Stolee \n \n @@ Documentation/git-backfill.txt (new)\n +\n +SYNOPSIS\n +--------\n -+[verse]\n -+'git backfill' []\n ++[synopsis]\n ++git backfill []\n +\n +DESCRIPTION\n +-----------\n +\n ++THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR MAY CHANGE IN THE FUTURE.\n ++\n +SEE ALSO\n +--------\n +linkgit:git-clone[1].\n @@ Documentation/git-backfill.txt (new)\n +---\n +Part of the linkgit:git[1] suite\n \n + ## Documentation/meson.build ##\n +@@ Documentation/meson.build: manpages = {\n + 'git-apply.txt' : 1,\n + 'git-archimport.txt' : 1,\n + 'git-archive.txt' : 1,\n ++ 'git-backfill.txt' : 1,\n + 'git-bisect.txt' : 1,\n + 'git-blame.txt' : 1,\n + 'git-branch.txt' : 1,\n +\n ## Makefile ##\n @@ Makefile: BUILTIN_OBJS += builtin/am.o\n BUILTIN_OBJS += builtin/annotate.o\n @@ builtin/backfill.c (new)\n +\t\tOPT_END(),\n +\t};\n +\n -+\tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n -+\t\tusage_with_options(builtin_backfill_usage, options);\n ++\tshow_usage_if_asked(argc, argv, builtin_backfill_usage[0]);\n +\n +\targc = parse_options(argc, argv, prefix, options, builtin_backfill_usage,\n +\t\t\t 0);\n @@ git.c: static struct cmd_struct commands[] = {\n \t{ \"bisect\", cmd_bisect, RUN_SETUP },\n \t{ \"blame\", cmd_blame, RUN_SETUP },\n \t{ \"branch\", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG },\n +\n + ## meson.build ##\n +@@ meson.build: builtin_sources = [\n + 'builtin/annotate.c',\n + 'builtin/apply.c',\n + 'builtin/archive.c',\n ++ 'builtin/backfill.c',\n + 'builtin/bisect.c',\n + 'builtin/blame.c',\n + 'builtin/branch.c',\n 2: e4e88794cae ! 2: d0cb9cb9af5 backfill: basic functionality and tests\n @@ Commit message\n Signed-off-by: Derrick Stolee \n \n ## Documentation/git-backfill.txt ##\n -@@ Documentation/git-backfill.txt: SYNOPSIS\n +@@ Documentation/git-backfill.txt: git backfill []\n DESCRIPTION\n -----------\n \n @@ Documentation/git-backfill.txt: SYNOPSIS\n +By default, `git backfill` downloads all blobs reachable from the `HEAD`\n +commit. This set can be restricted or expanded using various options.\n +\n + THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR MAY CHANGE IN THE FUTURE.\n + \n SEE ALSO\n - --------\n - linkgit:git-clone[1].\n \n ## Documentation/technical/api-path-walk.txt ##\n @@ Documentation/technical/api-path-walk.txt: Examples\n @@ builtin/backfill.c\n +struct backfill_context {\n +\tstruct repository *repo;\n +\tstruct oid_array current_batch;\n -+\tsize_t batch_size;\n ++\tsize_t min_batch_size;\n +};\n +\n +static void backfill_context_clear(struct backfill_context *ctx)\n @@ builtin/backfill.c\n +\t\treturn 0;\n +\n +\tfor (size_t i = 0; i < list->nr; i++) {\n -+\t\toff_t size = 0;\n -+\t\tstruct object_info info = OBJECT_INFO_INIT;\n -+\t\tinfo.disk_sizep = &size;\n -+\t\tif (oid_object_info_extended(ctx->repo,\n -+\t\t\t\t\t &list->oid[i],\n -+\t\t\t\t\t &info,\n -+\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH) ||\n -+\t\t !size)\n ++\t\tif (!has_object(ctx->repo, &list->oid[i],\n ++\t\t\t\tOBJECT_INFO_FOR_PREFETCH))\n +\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n +\t}\n +\n -+\tif (ctx->current_batch.nr >= ctx->batch_size)\n ++\tif (ctx->current_batch.nr >= ctx->min_batch_size)\n +\t\tdownload_batch(ctx);\n +\n +\treturn 0;\n @@ builtin/backfill.c\n +\tif (!ret)\n +\t\tdownload_batch(ctx);\n +\n -+\tbackfill_context_clear(ctx);\n +\tpath_walk_info_clear(&info);\n +\trelease_revisions(&revs);\n +\treturn ret;\n @@ builtin/backfill.c\n +\n int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n {\n ++\tint result;\n +\tstruct backfill_context ctx = {\n +\t\t.repo = repo,\n +\t\t.current_batch = OID_ARRAY_INIT,\n -+\t\t.batch_size = 50000,\n ++\t\t.min_batch_size = 50000,\n +\t};\n \tstruct option options[] = {\n \t\tOPT_END(),\n @@ builtin/backfill.c: int cmd_backfill(int argc, const char **argv, const char *pr\n -\tdie(_(\"not implemented\"));\n -\n -\treturn 0;\n -+\treturn do_backfill(&ctx);\n ++\tresult = do_backfill(&ctx);\n ++\tbackfill_context_clear(&ctx);\n ++\treturn result;\n }\n \n + ## t/meson.build ##\n +@@ t/meson.build: integration_tests = [\n + 't5617-clone-submodules-remote.sh',\n + 't5618-alternate-refs.sh',\n + 't5619-clone-local-ambiguous-transport.sh',\n ++ 't5620-backfill.sh',\n + 't5700-protocol-v1.sh',\n + 't5701-git-serve.sh',\n + 't5702-protocol-v2.sh',\n +\n ## t/t5620-backfill.sh (new) ##\n @@\n +#!/bin/sh\n 3: 3fa32822dab ! 3: b35c2f06b59 backfill: add --min-batch-size= option\n @@ Commit message\n future. For now, we let the path-walk API batches determine the\n boundaries.\n \n - To get a feeling for the value of specifying the --batch-size parameter,\n + To get a feeling for the value of specifying the --min-batch-size parameter,\n I tested a number of open source repositories available on GitHub. The\n procedure was generally:\n \n @@ Documentation/git-backfill.txt\n @@ Documentation/git-backfill.txt: git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n - [verse]\n --'git backfill' []\n -+'git backfill' [--batch-size=]\n + [synopsis]\n +-git backfill []\n ++git backfill [--min-batch-size=]\n \n DESCRIPTION\n -----------\n -@@ Documentation/git-backfill.txt: time.\n - By default, `git backfill` downloads all blobs reachable from the `HEAD`\n - commit. This set can be restricted or expanded using various options.\n +@@ Documentation/git-backfill.txt: commit. This set can be restricted or expanded using various options.\n \n + THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR MAY CHANGE IN THE FUTURE.\n + \n ++\n +OPTIONS\n +-------\n +\n -+--min-batch-size=::\n ++`--min-batch-size=`::\n +\tSpecify a minimum size for a batch of missing objects to request\n +\tfrom the server. This size may be exceeded by the last set of\n +\tblobs seen at a given path. The default minimum batch size is\n @@ builtin/backfill.c\n \n static const char * const builtin_backfill_usage[] = {\n -\tN_(\"git backfill []\"),\n -+\tN_(\"git backfill [--batch-size=]\"),\n ++\tN_(\"git backfill [--min-batch-size=]\"),\n \tNULL\n };\n \n - struct backfill_context {\n - \tstruct repository *repo;\n - \tstruct oid_array current_batch;\n --\tsize_t batch_size;\n -+\tsize_t min_batch_size;\n - };\n - \n - static void backfill_context_clear(struct backfill_context *ctx)\n -@@ builtin/backfill.c: static int fill_missing_blobs(const char *path UNUSED,\n - \t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n - \t}\n - \n --\tif (ctx->current_batch.nr >= ctx->batch_size)\n -+\tif (ctx->current_batch.nr >= ctx->min_batch_size)\n - \t\tdownload_batch(ctx);\n - \n - \treturn 0;\n @@ builtin/backfill.c: int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n - \tstruct backfill_context ctx = {\n - \t\t.repo = repo,\n - \t\t.current_batch = OID_ARRAY_INIT,\n --\t\t.batch_size = 50000,\n -+\t\t.min_batch_size = 50000,\n + \t\t.min_batch_size = 50000,\n \t};\n \tstruct option options[] = {\n +\t\tOPT_INTEGER(0, \"min-batch-size\", &ctx.min_batch_size,\n 4: 2723143afb3 ! 4: f1c5a5c5fde backfill: add --sparse option\n @@ Commit message\n \n Be sure to test this in both cone mode and not cone mode. Cone mode has the\n benefit that the path-walk can skip certain paths once they would expand\n - beyond the sparse-checkout.\n + beyond the sparse-checkout. Non-cone mode can describe the included files\n + using both positive and negative patterns, which changes the possible return\n + values of path_matches_pattern_list(). Test both kinds of matches for\n + increased coverage.\n \n To test this, we can create a blobless sparse clone, expand the\n sparse-checkout slightly, and then run 'git backfill --sparse' to see\n @@ Documentation/git-backfill.txt\n @@ Documentation/git-backfill.txt: git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n - [verse]\n --'git backfill' [--batch-size=]\n -+'git backfill' [--batch-size=] [--[no-]sparse]\n + [synopsis]\n +-git backfill [--min-batch-size=]\n ++git backfill [--min-batch-size=] [--[no-]sparse]\n \n DESCRIPTION\n -----------\n @@ Documentation/git-backfill.txt: OPTIONS\n \tblobs seen at a given path. The default minimum batch size is\n \t50,000.\n \n -+--[no-]sparse::\n ++`--[no-]sparse`::\n +\tOnly download objects if they appear at a path that matches the\n +\tcurrent sparse-checkout.\n +\n @@ builtin/backfill.c\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n --\tN_(\"git backfill [--batch-size=]\"),\n -+\tN_(\"git backfill [--batch-size=] [--[no-]sparse]\"),\n +-\tN_(\"git backfill [--min-batch-size=]\"),\n ++\tN_(\"git backfill [--min-batch-size=] [--[no-]sparse]\"),\n \tNULL\n };\n \n @@ t/t5620-backfill.sh: test_expect_success 'do partial clone 2, backfill min batch\n +\ttest_line_count = 24 missing\n +'\n +\n -+test_expect_success 'backfill --sparse without cone mode' '\n ++test_expect_success 'backfill --sparse without cone mode (positive)' '\n +\tgit clone --no-checkout --filter=blob:none\t\t\\\n +\t\t--single-branch --branch=main \t\t\\\n +\t\t\"file://$(pwd)/srv.bare\" backfill4 &&\n @@ t/t5620-backfill.sh: test_expect_success 'do partial clone 2, backfill min batch\n +\tgit -C backfill4 sparse-checkout set --no-cone \"**/file.1.txt\" &&\n +\tgit -C backfill4 checkout main &&\n +\n ++\t# Track new blob count\n ++\tgit -C backfill4 rev-list --quiet --objects --missing=print HEAD >missing &&\n ++\ttest_line_count = 42 missing &&\n ++\n +\tGIT_TRACE2_EVENT=\"$(pwd)/no-cone-trace1\" git \\\n +\t\t-C backfill4 backfill --sparse &&\n +\ttest_trace2_data promisor fetch_count 6 missing &&\n +\ttest_line_count = 36 missing\n +'\n ++\n ++test_expect_success 'backfill --sparse without cone mode (negative)' '\n ++\tgit clone --no-checkout --filter=blob:none\t\t\\\n ++\t\t--single-branch --branch=main \t\t\\\n ++\t\t\"file://$(pwd)/srv.bare\" backfill5 &&\n ++\n ++\t# No blobs yet\n ++\tgit -C backfill5 rev-list --quiet --objects --missing=print HEAD >missing &&\n ++\ttest_line_count = 48 missing &&\n ++\n ++\t# Define sparse-checkout by filename regardless of parent directory.\n ++\t# This downloads 18 blobs to satisfy the checkout\n ++\tgit -C backfill5 sparse-checkout set --no-cone \"**/file*\" \"!**/file.1.txt\" &&\n ++\tgit -C backfill5 checkout main &&\n ++\n ++\t# Track new blob count\n ++\tgit -C backfill5 rev-list --quiet --objects --missing=print HEAD >missing &&\n ++\ttest_line_count = 30 missing &&\n ++\n ++\tGIT_TRACE2_EVENT=\"$(pwd)/no-cone-trace2\" git \\\n ++\t\t-C backfill5 backfill --sparse &&\n ++\ttest_trace2_data promisor fetch_count 18 missing &&\n ++\ttest_line_count = 12 missing\n ++'\n +\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n 5: 1f765409eaf ! 5: f22cf8b3485 backfill: assume --sparse when sparse-checkout is enabled\n @@ Commit message\n ## Documentation/git-backfill.txt ##\n @@ Documentation/git-backfill.txt: OPTIONS\n \n - --[no-]sparse::\n + `--[no-]sparse`::\n \tOnly download objects if they appear at a path that matches the\n -\tcurrent sparse-checkout.\n +\tcurrent sparse-checkout. If the sparse-checkout feature is enabled,\n @@ builtin/backfill.c: int cmd_backfill(int argc, const char **argv, const char *pr\n +\tif (ctx.sparse < 0)\n +\t\tctx.sparse = core_apply_sparse_checkout;\n +\n - \treturn do_backfill(&ctx);\n - }\n + \tresult = do_backfill(&ctx);\n + \tbackfill_context_clear(&ctx);\n + \treturn result;\n \n ## t/t5620-backfill.sh ##\n @@ t/t5620-backfill.sh: test_expect_success 'do partial clone 2, backfill min batch size' '\n @@ t/t5620-backfill.sh: test_expect_success 'backfill --sparse' '\n +\ttest_line_count = 0 missing\n '\n \n - test_expect_success 'backfill --sparse without cone mode' '\n + test_expect_success 'backfill --sparse without cone mode (positive)' '\n\n-- \ngitgitgadget\n"},{"id":"511751","messageId":"1612ad924556974e41587b441ccf886d74963048.1738602667.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v3.git.1738602667.gitgitgadget@gmail.com","subject":"[PATCH v3 1/5] backfill: add builtin boilerplate","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-02-03T17:11:03Z","receivedAt":"2025-02-03T17:11:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of implementing 'git backfill', populate the necessary files\nwith the boilerplate of a new builtin. Mark the builtin as experimental at\nthis time, allowing breaking changes in the near future, if necessary.\n\nSigned-off-by: Derrick Stolee \n---\n .gitignore | 1 +\n Documentation/git-backfill.txt | 25 +++++++++++++++++++++++++\n Documentation/meson.build | 1 +\n Makefile | 1 +\n builtin.h | 1 +\n builtin/backfill.c | 28 ++++++++++++++++++++++++++++\n command-list.txt | 1 +\n git.c | 1 +\n meson.build | 1 +\n 9 files changed, 60 insertions(+)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 builtin/backfill.c\n\ndiff --git a/.gitignore b/.gitignore\nindex e82aa19df03..95cd94c5044 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -19,6 +19,7 @@\n /git-apply\n /git-archimport\n /git-archive\n+/git-backfill\n /git-bisect\n /git-blame\n /git-branch\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nnew file mode 100644\nindex 00000000000..ab384dad6e4\n--- /dev/null\n+++ b/Documentation/git-backfill.txt\n@@ -0,0 +1,25 @@\n+git-backfill(1)\n+===============\n+\n+NAME\n+----\n+git-backfill - Download missing objects in a partial clone\n+\n+\n+SYNOPSIS\n+--------\n+[synopsis]\n+git backfill []\n+\n+DESCRIPTION\n+-----------\n+\n+THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR MAY CHANGE IN THE FUTURE.\n+\n+SEE ALSO\n+--------\n+linkgit:git-clone[1].\n+\n+GIT\n+---\n+Part of the linkgit:git[1] suite\ndiff --git a/Documentation/meson.build b/Documentation/meson.build\nindex 2a26fa8a5fe..5e9e3e19c5c 100644\n--- a/Documentation/meson.build\n+++ b/Documentation/meson.build\n@@ -6,6 +6,7 @@ manpages = {\n 'git-apply.txt' : 1,\n 'git-archimport.txt' : 1,\n 'git-archive.txt' : 1,\n+ 'git-backfill.txt' : 1,\n 'git-bisect.txt' : 1,\n 'git-blame.txt' : 1,\n 'git-branch.txt' : 1,\ndiff --git a/Makefile b/Makefile\nindex 2f6e2d52955..efa199d390c 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1203,6 +1203,7 @@ BUILTIN_OBJS += builtin/am.o\n BUILTIN_OBJS += builtin/annotate.o\n BUILTIN_OBJS += builtin/apply.o\n BUILTIN_OBJS += builtin/archive.o\n+BUILTIN_OBJS += builtin/backfill.o\n BUILTIN_OBJS += builtin/bisect.o\n BUILTIN_OBJS += builtin/blame.o\n BUILTIN_OBJS += builtin/branch.o\ndiff --git a/builtin.h b/builtin.h\nindex f7b166b3348..89928ccf92f 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -120,6 +120,7 @@ int cmd_am(int argc, const char **argv, const char *prefix, struct repository *r\n int cmd_annotate(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_apply(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_archive(int argc, const char **argv, const char *prefix, struct repository *repo);\n+int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_bisect(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_blame(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_branch(int argc, const char **argv, const char *prefix, struct repository *repo);\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nnew file mode 100644\nindex 00000000000..58d0866c0fc\n--- /dev/null\n+++ b/builtin/backfill.c\n@@ -0,0 +1,28 @@\n+#include \"builtin.h\"\n+#include \"config.h\"\n+#include \"parse-options.h\"\n+#include \"repository.h\"\n+#include \"object.h\"\n+\n+static const char * const builtin_backfill_usage[] = {\n+\tN_(\"git backfill []\"),\n+\tNULL\n+};\n+\n+int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n+{\n+\tstruct option options[] = {\n+\t\tOPT_END(),\n+\t};\n+\n+\tshow_usage_if_asked(argc, argv, builtin_backfill_usage[0]);\n+\n+\targc = parse_options(argc, argv, prefix, options, builtin_backfill_usage,\n+\t\t\t 0);\n+\n+\trepo_config(repo, git_default_config, NULL);\n+\n+\tdie(_(\"not implemented\"));\n+\n+\treturn 0;\n+}\ndiff --git a/command-list.txt b/command-list.txt\nindex e0bb87b3b5c..c537114b468 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -60,6 +60,7 @@ git-annotate ancillaryinterrogators\n git-apply plumbingmanipulators complete\n git-archimport foreignscminterface\n git-archive mainporcelain\n+git-backfill mainporcelain history\n git-bisect mainporcelain info\n git-blame ancillaryinterrogators complete\n git-branch mainporcelain history\ndiff --git a/git.c b/git.c\nindex a94dab37702..a9b45fcef79 100644\n--- a/git.c\n+++ b/git.c\n@@ -506,6 +506,7 @@ static struct cmd_struct commands[] = {\n \t{ \"annotate\", cmd_annotate, RUN_SETUP },\n \t{ \"apply\", cmd_apply, RUN_SETUP_GENTLY },\n \t{ \"archive\", cmd_archive, RUN_SETUP_GENTLY },\n+\t{ \"backfill\", cmd_backfill, RUN_SETUP },\n \t{ \"bisect\", cmd_bisect, RUN_SETUP },\n \t{ \"blame\", cmd_blame, RUN_SETUP },\n \t{ \"branch\", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG },\ndiff --git a/meson.build b/meson.build\nindex 548eac62b28..527c015acfa 100644\n--- a/meson.build\n+++ b/meson.build\n@@ -487,6 +487,7 @@ builtin_sources = [\n 'builtin/annotate.c',\n 'builtin/apply.c',\n 'builtin/archive.c',\n+ 'builtin/backfill.c',\n 'builtin/bisect.c',\n 'builtin/blame.c',\n 'builtin/branch.c',\n-- \ngitgitgadget\n\n"},{"id":"511752","messageId":"d0cb9cb9af5efd5337f7af4de782660c7552fa69.1738602667.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v3.git.1738602667.gitgitgadget@gmail.com","subject":"[PATCH v3 2/5] backfill: basic functionality and tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-02-03T17:11:04Z","receivedAt":"2025-02-03T17:11:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe default behavior of 'git backfill' is to fetch all missing blobs that\nare reachable from HEAD. Document and test this behavior.\n\nThe implementation is a very simple use of the path-walk API, initializing\nthe revision walk at HEAD to start the path-walk from all commits reachable\nfrom HEAD. Ignore the object arrays that correspond to tree entries,\nassuming that they are all present already.\n\nThe path-walk API provides lists of objects in batches according to a\ncommon path, but that list could be very small. We want to balance the\nnumber of requests to the server with the ability to have the process\ninterrupted with minimal repeated work to catch up in the next run.\nBased on some experiments (detailed in the next change) a minimum batch\nsize of 50,000 is selected for the default.\n\nThis batch size is a _minimum_. As the path-walk API emits lists of blob\nIDs, they are collected into a list of objects for a request to the\nserver. When that list is at least the minimum batch size, then the\nrequest is sent to the server for the new objects. However, the list of\nblob IDs from the path-walk API could be much longer than the batch\nsize. At this moment, it is unclear if there is a benefit to split the\nlist when there are too many objects at the same path.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 31 +++++++\n Documentation/technical/api-path-walk.txt | 3 +-\n builtin/backfill.c | 102 +++++++++++++++++++++-\n t/meson.build | 1 +\n t/t5620-backfill.sh | 94 ++++++++++++++++++++\n 5 files changed, 227 insertions(+), 4 deletions(-)\n create mode 100755 t/t5620-backfill.sh\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex ab384dad6e4..56cbb9ffd82 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -14,6 +14,37 @@ git backfill []\n DESCRIPTION\n -----------\n \n+Blobless partial clones are created using `git clone --filter=blob:none`\n+and then configure the local repository such that the Git client avoids\n+downloading blob objects unless they are required for a local operation.\n+This initially means that the clone and later fetches download reachable\n+commits and trees but no blobs. Later operations that change the `HEAD`\n+pointer, such as `git checkout` or `git merge`, may need to download\n+missing blobs in order to complete their operation.\n+\n+In the worst cases, commands that compute blob diffs, such as `git blame`,\n+become very slow as they download the missing blobs in single-blob\n+requests to satisfy the missing object as the Git command needs it. This\n+leads to multiple download requests and no ability for the Git server to\n+provide delta compression across those objects.\n+\n+The `git backfill` command provides a way for the user to request that\n+Git downloads the missing blobs (with optional filters) such that the\n+missing blobs representing historical versions of files can be downloaded\n+in batches. The `backfill` command attempts to optimize the request by\n+grouping blobs that appear at the same path, hopefully leading to good\n+delta compression in the packfile sent by the server.\n+\n+In this way, `git backfill` provides a mechanism to break a large clone\n+into smaller chunks. Starting with a blobless partial clone with `git\n+clone --filter=blob:none` and then running `git backfill` in the local\n+repository provides a way to download all reachable objects in several\n+smaller network calls than downloading the entire repository at clone\n+time.\n+\n+By default, `git backfill` downloads all blobs reachable from the `HEAD`\n+commit. This set can be restricted or expanded using various options.\n+\n THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR MAY CHANGE IN THE FUTURE.\n \n SEE ALSO\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 7075d0d5ab5..1fba0ce04cb 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -60,4 +60,5 @@ Examples\n --------\n \n See example usages in:\n-\t`t/helper/test-path-walk.c`\n+\t`t/helper/test-path-walk.c`,\n+\t`builtin/backfill.c`\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 58d0866c0fc..0eca175a7fe 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -1,16 +1,112 @@\n #include \"builtin.h\"\n+#include \"git-compat-util.h\"\n #include \"config.h\"\n #include \"parse-options.h\"\n #include \"repository.h\"\n+#include \"commit.h\"\n+#include \"hex.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n #include \"object.h\"\n+#include \"object-store-ll.h\"\n+#include \"oid-array.h\"\n+#include \"oidset.h\"\n+#include \"promisor-remote.h\"\n+#include \"strmap.h\"\n+#include \"string-list.h\"\n+#include \"revision.h\"\n+#include \"trace2.h\"\n+#include \"progress.h\"\n+#include \"packfile.h\"\n+#include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n \tN_(\"git backfill []\"),\n \tNULL\n };\n \n+struct backfill_context {\n+\tstruct repository *repo;\n+\tstruct oid_array current_batch;\n+\tsize_t min_batch_size;\n+};\n+\n+static void backfill_context_clear(struct backfill_context *ctx)\n+{\n+\toid_array_clear(&ctx->current_batch);\n+}\n+\n+static void download_batch(struct backfill_context *ctx)\n+{\n+\tpromisor_remote_get_direct(ctx->repo,\n+\t\t\t\t ctx->current_batch.oid,\n+\t\t\t\t ctx->current_batch.nr);\n+\toid_array_clear(&ctx->current_batch);\n+\n+\t/*\n+\t * We likely have a new packfile. Add it to the packed list to\n+\t * avoid possible duplicate downloads of the same objects.\n+\t */\n+\treprepare_packed_git(ctx->repo);\n+}\n+\n+static int fill_missing_blobs(const char *path UNUSED,\n+\t\t\t struct oid_array *list,\n+\t\t\t enum object_type type,\n+\t\t\t void *data)\n+{\n+\tstruct backfill_context *ctx = data;\n+\n+\tif (type != OBJ_BLOB)\n+\t\treturn 0;\n+\n+\tfor (size_t i = 0; i < list->nr; i++) {\n+\t\tif (!has_object(ctx->repo, &list->oid[i],\n+\t\t\t\tOBJECT_INFO_FOR_PREFETCH))\n+\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n+\t}\n+\n+\tif (ctx->current_batch.nr >= ctx->min_batch_size)\n+\t\tdownload_batch(ctx);\n+\n+\treturn 0;\n+}\n+\n+static int do_backfill(struct backfill_context *ctx)\n+{\n+\tstruct rev_info revs;\n+\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n+\tint ret;\n+\n+\trepo_init_revisions(ctx->repo, &revs, \"\");\n+\thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n+\n+\tinfo.blobs = 1;\n+\tinfo.tags = info.commits = info.trees = 0;\n+\n+\tinfo.revs = &revs;\n+\tinfo.path_fn = fill_missing_blobs;\n+\tinfo.path_fn_data = ctx;\n+\n+\tret = walk_objects_by_path(&info);\n+\n+\t/* Download the objects that did not fill a batch. */\n+\tif (!ret)\n+\t\tdownload_batch(ctx);\n+\n+\tpath_walk_info_clear(&info);\n+\trelease_revisions(&revs);\n+\treturn ret;\n+}\n+\n int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo)\n {\n+\tint result;\n+\tstruct backfill_context ctx = {\n+\t\t.repo = repo,\n+\t\t.current_batch = OID_ARRAY_INIT,\n+\t\t.min_batch_size = 50000,\n+\t};\n \tstruct option options[] = {\n \t\tOPT_END(),\n \t};\n@@ -22,7 +118,7 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \n \trepo_config(repo, git_default_config, NULL);\n \n-\tdie(_(\"not implemented\"));\n-\n-\treturn 0;\n+\tresult = do_backfill(&ctx);\n+\tbackfill_context_clear(&ctx);\n+\treturn result;\n }\ndiff --git a/t/meson.build b/t/meson.build\nindex 35f25ca4a1d..af53e8ee583 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -721,6 +721,7 @@ integration_tests = [\n 't5617-clone-submodules-remote.sh',\n 't5618-alternate-refs.sh',\n 't5619-clone-local-ambiguous-transport.sh',\n+ 't5620-backfill.sh',\n 't5700-protocol-v1.sh',\n 't5701-git-serve.sh',\n 't5702-protocol-v2.sh',\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nnew file mode 100755\nindex 00000000000..64326362d80\n--- /dev/null\n+++ b/t/t5620-backfill.sh\n@@ -0,0 +1,94 @@\n+#!/bin/sh\n+\n+test_description='git backfill on partial clones'\n+\n+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main\n+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME\n+\n+. ./test-lib.sh\n+\n+# We create objects in the 'src' repo.\n+test_expect_success 'setup repo for object creation' '\n+\techo \"{print \\$1}\" >print_1.awk &&\n+\techo \"{print \\$2}\" >print_2.awk &&\n+\n+\tgit init src &&\n+\n+\tmkdir -p src/a/b/c &&\n+\tmkdir -p src/d/e &&\n+\n+\tfor i in 1 2\n+\tdo\n+\t\tfor n in 1 2 3 4\n+\t\tdo\n+\t\t\techo \"Version $i of file $n\" > src/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/$n\" > src/a/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/$n\" > src/a/b/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/c/$n\" > src/a/b/c/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/$n\" > src/d/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/e/$n\" > src/d/e/file.$n.txt &&\n+\t\t\tgit -C src add . &&\n+\t\t\tgit -C src commit -m \"Iteration $n\" || return 1\n+\t\tdone\n+\tdone\n+'\n+\n+# Clone 'src' into 'srv.bare' so we have a bare repo to be our origin\n+# server for the partial clone.\n+test_expect_success 'setup bare clone for server' '\n+\tgit clone --bare \"file://$(pwd)/src\" srv.bare &&\n+\tgit -C srv.bare config --local uploadpack.allowfilter 1 &&\n+\tgit -C srv.bare config --local uploadpack.allowanysha1inwant 1\n+'\n+\n+# do basic partial clone from \"srv.bare\"\n+test_expect_success 'do partial clone 1, backfill gets all objects' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill1 &&\n+\n+\t# Backfill with no options gets everything reachable from HEAD.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-file-trace\" git \\\n+\t\t-C backfill1 backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n+. \"$TEST_DIRECTORY\"/lib-httpd.sh\n+start_httpd\n+\n+test_expect_success 'create a partial clone over HTTP' '\n+\tSERVER=\"$HTTPD_DOCUMENT_ROOT_PATH/server\" &&\n+\trm -rf \"$SERVER\" repo &&\n+\tgit clone --bare \"file://$(pwd)/src\" \"$SERVER\" &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowfilter 1 &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowanysha1inwant 1 &&\n+\n+\tgit clone --no-checkout --filter=blob:none \\\n+\t\t\"$HTTPD_URL/smart/server\" backfill-http\n+'\n+\n+test_expect_success 'backfilling over HTTP succeeds' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-http-trace\" git \\\n+\t\t-C backfill-http backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 rev-list-out &&\n+\tawk \"{print \\$1;}\" oids &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/walk-trace\" git -C backfill-http \\\n+\t\tcat-file --batch-check batch-out &&\n+\t! grep missing batch-out\n+'\n+\n+# DO NOT add non-httpd-specific tests here, because the last part of this\n+# test script is only executed when httpd is available and enabled.\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"511753","messageId":"b35c2f06b5952ff34ea52766652a3bd3c698f681.1738602667.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v3.git.1738602667.gitgitgadget@gmail.com","subject":"[PATCH v3 3/5] backfill: add --min-batch-size= option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-02-03T17:11:05Z","receivedAt":"2025-02-03T17:11:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nUsers may want to specify a minimum batch size for their needs. This is only\na minimum: the path-walk API provides a list of OIDs that correspond to the\nsame path, and thus it is optimal to allow delta compression across those\nobjects in a single server request.\n\nWe could consider limiting the request to have a maximum batch size in the\nfuture. For now, we let the path-walk API batches determine the\nboundaries.\n\nTo get a feeling for the value of specifying the --min-batch-size parameter,\nI tested a number of open source repositories available on GitHub. The\nprocedure was generally:\n\n 1. git clone --filter=blob:none \n 2. git backfill\n\nChecking the number of packfiles and the size of the .git/objects/pack\ndirectory helps to identify the effects of different batch sizes.\n\nFor the Git repository, we get these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|-------|\n| (Initial clone) | 2 | 119 MB | |\n| 25K | 8 | 290 MB | 24s |\n| 50K | 5 | 290 MB | 24s |\n| 100K | 4 | 290 MB | 29s |\n\nOther than the packfile counts decreasing as we need fewer batches, the\nsize and time required is not changing much for this small example.\n\nFor the nodejs/node repository, we see these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 330 MB | |\n| 25K | 19 | 1,222 MB | 1m 22s |\n| 50K | 11 | 1,221 MB | 1m 24s |\n| 100K | 7 | 1,223 MB | 1m 40s |\n| 250K | 4 | 1,224 MB | 2m 23s |\n| 500K | 3 | 1,216 MB | 4m 38s |\n\nHere, we don't have much difference in the size of the repo, though the\n500K batch size results in a few MB gained. That comes at a cost of a\nmuch longer time. This extra time is due to server-side delta\ncompression happening as the on-disk deltas don't appear to be reusable\nall the time. But for smaller batch sizes, the server is able to find\nreasonable deltas partly because we are asking for objects that appear\nin the same region of the directory tree and include all versions of a\nfile at a specific path.\n\nTo contrast this example, I tested the microsoft/fluentui repo, which\nhas been known to have inefficient packing due to name hash collisions.\nThese results are found before GitHub had the opportunity to repack the\nserver with more advanced name hash versions:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|--------|\n| (Initial clone) | 2 | 105 MB | |\n| 5K | 53 | 348 MB | 2m 26s |\n| 10K | 28 | 365 MB | 2m 22s |\n| 15K | 19 | 407 MB | 2m 21s |\n| 20K | 15 | 393 MB | 2m 28s |\n| 25K | 13 | 417 MB | 2m 06s |\n| 50K | 8 | 509 MB | 1m 34s |\n| 100K | 5 | 535 MB | 1m 56s |\n| 250K | 4 | 698 MB | 1m 33s |\n| 500K | 3 | 696 MB | 1m 42s |\n\nHere, a larger variety of batch sizes were chosen because of the great\nvariation in results. By asking the server to download small batches\ncorresponding to fewer paths at a time, the server is able to provide\nbetter compression for these batches than it would for a regular clone.\nA typical full clone for this repository would require 738 MB.\n\nThis example justifies the choice to batch requests by path name,\nleading to improved communication with a server that is not optimally\npacked.\n\nFinally, the same experiment for the Linux repository had these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|---------|\n| (Initial clone) | 2 | 2,153 MB | |\n| 25K | 63 | 6,380 MB | 14m 08s |\n| 50K | 58 | 6,126 MB | 15m 11s |\n| 100K | 30 | 6,135 MB | 18m 11s |\n| 250K | 14 | 6,146 MB | 18m 22s |\n| 500K | 8 | 6,143 MB | 33m 29s |\n\nEven in this example, where the default name hash algorithm leads to\ndecent compression of the Linux kernel repository, there is value for\nselecting a smaller batch size, to a limit. The 25K batch size has the\nfastest time, but uses 250 MB more than the 50K batch size. The 500K\nbatch size took much more time due to server compression time and thus\nwe should avoid large batch sizes like this.\n\nBased on these experiments, a batch size of 50,000 was chosen as the\ndefault value.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 12 +++++++++++-\n builtin/backfill.c | 4 +++-\n t/t5620-backfill.sh | 18 ++++++++++++++++++\n 3 files changed, 32 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 56cbb9ffd82..136a1f1d294 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [synopsis]\n-git backfill []\n+git backfill [--min-batch-size=]\n \n DESCRIPTION\n -----------\n@@ -47,6 +47,16 @@ commit. This set can be restricted or expanded using various options.\n \n THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR MAY CHANGE IN THE FUTURE.\n \n+\n+OPTIONS\n+-------\n+\n+`--min-batch-size=`::\n+\tSpecify a minimum size for a batch of missing objects to request\n+\tfrom the server. This size may be exceeded by the last set of\n+\tblobs seen at a given path. The default minimum batch size is\n+\t50,000.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 0eca175a7fe..cfebee6e17b 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -21,7 +21,7 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill []\"),\n+\tN_(\"git backfill [--min-batch-size=]\"),\n \tNULL\n };\n \n@@ -108,6 +108,8 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \t\t.min_batch_size = 50000,\n \t};\n \tstruct option options[] = {\n+\t\tOPT_INTEGER(0, \"min-batch-size\", &ctx.min_batch_size,\n+\t\t\t N_(\"Minimum number of objects to request at a time\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 64326362d80..36107a51c54 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -59,6 +59,24 @@ test_expect_success 'do partial clone 1, backfill gets all objects' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'do partial clone 2, backfill min batch size' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill2 &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/batch-trace\" git \\\n+\t\t-C backfill2 backfill --min-batch-size=20 &&\n+\n+\t# Batches were used\n+\ttest_trace2_data promisor fetch_count 20 matches &&\n+\ttest_line_count = 2 matches &&\n+\ttest_trace2_data promisor fetch_count 8 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \n-- \ngitgitgadget\n\n"},{"id":"511755","messageId":"f1c5a5c5fde41c307b61c9ffb8edb68b3c8786e9.1738602667.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v3.git.1738602667.gitgitgadget@gmail.com","subject":"[PATCH v3 4/5] backfill: add --sparse option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-02-03T17:11:06Z","receivedAt":"2025-02-03T17:11:15Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nOne way to significantly reduce the cost of a Git clone and later fetches is\nto use a blobless partial clone and combine that with a sparse-checkout that\nreduces the paths that need to be populated in the working directory. Not\nonly does this reduce the cost of clones and fetches, the sparse-checkout\nreduces the number of objects needed to download from a promisor remote.\n\nHowever, history investigations can be expensive as computing blob diffs\nwill trigger promisor remote requests for one object at a time. This can be\navoided by downloading the blobs needed for the given sparse-checkout using\n'git backfill' and its new '--sparse' mode, at a time that the user is\nwilling to pay that extra cost.\n\nNote that this is distinctly different from the '--filter=sparse:'\noption, as this assumes that the partial clone has all reachable trees and\nwe are using client-side logic to avoid downloading blobs outside of the\nsparse-checkout cone. This avoids the server-side cost of walking trees\nwhile also achieving a similar goal. It also downloads in batches based on\nsimilar path names, presenting a resumable download if things are\ninterrupted.\n\nThis augments the path-walk API to have a possibly-NULL 'pl' member that may\npoint to a 'struct pattern_list'. This could be more general than the\nsparse-checkout definition at HEAD, but 'git backfill --sparse' is currently\nthe only consumer.\n\nBe sure to test this in both cone mode and not cone mode. Cone mode has the\nbenefit that the path-walk can skip certain paths once they would expand\nbeyond the sparse-checkout. Non-cone mode can describe the included files\nusing both positive and negative patterns, which changes the possible return\nvalues of path_matches_pattern_list(). Test both kinds of matches for\nincreased coverage.\n\nTo test this, we can create a blobless sparse clone, expand the\nsparse-checkout slightly, and then run 'git backfill --sparse' to see\nhow much data is downloaded. The general steps are\n\n 1. git clone --filter=blob:none --sparse \n 2. git sparse-checkout set ... \n 3. git backfill --sparse\n\nFor the Git repository with the 'builtin' directory in the\nsparse-checkout, we get these results for various batch sizes:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|-------|\n| (Initial clone) | 3 | 110 MB | |\n| 10K | 12 | 192 MB | 17.2s |\n| 15K | 9 | 192 MB | 15.5s |\n| 20K | 8 | 192 MB | 15.5s |\n| 25K | 7 | 192 MB | 14.7s |\n\nThis case matters less because a full clone of the Git repository from\nGitHub is currently at 277 MB.\n\nUsing a copy of the Linux repository with the 'kernel/' directory in the\nsparse-checkout, we get these results:\n\n| Batch Size | Pack Count | Pack Size | Time |\n|-----------------|------------|-----------|------|\n| (Initial clone) | 2 | 1,876 MB | |\n| 10K | 11 | 2,187 MB | 46s |\n| 25K | 7 | 2,188 MB | 43s |\n| 50K | 5 | 2,194 MB | 44s |\n| 100K | 4 | 2,194 MB | 48s |\n\nThis case is more meaningful because a full clone of the Linux\nrepository is currently over 6 GB, so this is a valuable way to download\na fraction of the repository and no longer need network access for all\nreachable objects within the sparse-checkout.\n\nChoosing a batch size will depend on a lot of factors, including the\nuser's network speed or reliability, the repository's file structure,\nand how many versions there are of the file within the sparse-checkout\nscope. There will not be a one-size-fits-all solution.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 6 +-\n Documentation/technical/api-path-walk.txt | 8 +++\n builtin/backfill.c | 15 +++-\n dir.c | 10 +--\n dir.h | 3 +\n path-walk.c | 28 ++++++--\n path-walk.h | 11 +++\n t/helper/test-path-walk.c | 22 +++++-\n t/t5620-backfill.sh | 88 +++++++++++++++++++++++\n t/t6601-path-walk.sh | 32 +++++++++\n 10 files changed, 208 insertions(+), 15 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 136a1f1d294..a28678983e3 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [synopsis]\n-git backfill [--min-batch-size=]\n+git backfill [--min-batch-size=] [--[no-]sparse]\n \n DESCRIPTION\n -----------\n@@ -57,6 +57,10 @@ OPTIONS\n \tblobs seen at a given path. The default minimum batch size is\n \t50,000.\n \n+`--[no-]sparse`::\n+\tOnly download objects if they appear at a path that matches the\n+\tcurrent sparse-checkout.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 1fba0ce04cb..3e089211fb4 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -56,6 +56,14 @@ better off using the revision walk API instead.\n \tthe revision walk so that the walk emits commits marked with the\n \t`UNINTERESTING` flag.\n \n+`pl`::\n+\tThis pattern list pointer allows focusing the path-walk search to\n+\ta set of patterns, only emitting paths that match the given\n+\tpatterns. See linkgit:gitignore[5] or\n+\tlinkgit:git-sparse-checkout[1] for details about pattern lists.\n+\tWhen the pattern list uses cone-mode patterns, then the path-walk\n+\tAPI can prune the set of paths it walks to improve performance.\n+\n Examples\n --------\n \ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex cfebee6e17b..d7b997fd6f7 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"repository.h\"\n #include \"commit.h\"\n+#include \"dir.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -21,7 +22,7 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill [--min-batch-size=]\"),\n+\tN_(\"git backfill [--min-batch-size=] [--[no-]sparse]\"),\n \tNULL\n };\n \n@@ -29,6 +30,7 @@ struct backfill_context {\n \tstruct repository *repo;\n \tstruct oid_array current_batch;\n \tsize_t min_batch_size;\n+\tint sparse;\n };\n \n static void backfill_context_clear(struct backfill_context *ctx)\n@@ -78,6 +80,14 @@ static int do_backfill(struct backfill_context *ctx)\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tint ret;\n \n+\tif (ctx->sparse) {\n+\t\tCALLOC_ARRAY(info.pl, 1);\n+\t\tif (get_sparse_checkout_patterns(info.pl)) {\n+\t\t\tpath_walk_info_clear(&info);\n+\t\t\treturn error(_(\"problem loading sparse-checkout\"));\n+\t\t}\n+\t}\n+\n \trepo_init_revisions(ctx->repo, &revs, \"\");\n \thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n \n@@ -106,10 +116,13 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \t\t.repo = repo,\n \t\t.current_batch = OID_ARRAY_INIT,\n \t\t.min_batch_size = 50000,\n+\t\t.sparse = 0,\n \t};\n \tstruct option options[] = {\n \t\tOPT_INTEGER(0, \"min-batch-size\", &ctx.min_batch_size,\n \t\t\t N_(\"Minimum number of objects to request at a time\")),\n+\t\tOPT_BOOL(0, \"sparse\", &ctx.sparse,\n+\t\t\t N_(\"Restrict the missing objects to the current sparse-checkout\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/dir.c b/dir.c\nindex 5b2181e5899..16ccfe7e4e8 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -1093,10 +1093,6 @@ static void invalidate_directory(struct untracked_cache *uc,\n \t\tdir->dirs[i]->recurse = 0;\n }\n \n-static int add_patterns_from_buffer(char *buf, size_t size,\n-\t\t\t\t const char *base, int baselen,\n-\t\t\t\t struct pattern_list *pl);\n-\n /* Flags for add_patterns() */\n #define PATTERN_NOFOLLOW (1<<0)\n \n@@ -1186,9 +1182,9 @@ static int add_patterns(const char *fname, const char *base, int baselen,\n \treturn 0;\n }\n \n-static int add_patterns_from_buffer(char *buf, size_t size,\n-\t\t\t\t const char *base, int baselen,\n-\t\t\t\t struct pattern_list *pl)\n+int add_patterns_from_buffer(char *buf, size_t size,\n+\t\t\t const char *base, int baselen,\n+\t\t\t struct pattern_list *pl)\n {\n \tchar *orig = buf;\n \tint i, lineno = 1;\ndiff --git a/dir.h b/dir.h\nindex a3a2f00f5d9..6cfef5df660 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -467,6 +467,9 @@ void add_patterns_from_file(struct dir_struct *, const char *fname);\n int add_patterns_from_blob_to_list(struct object_id *oid,\n \t\t\t\t const char *base, int baselen,\n \t\t\t\t struct pattern_list *pl);\n+int add_patterns_from_buffer(char *buf, size_t size,\n+\t\t\t const char *base, int baselen,\n+\t\t\t struct pattern_list *pl);\n void parse_path_pattern(const char **string, int *patternlen, unsigned *flags, int *nowildcardlen);\n void add_pattern(const char *string, const char *base,\n \t\t int baselen, struct pattern_list *pl, int srcpos);\ndiff --git a/path-walk.c b/path-walk.c\nindex 9715a5550ef..341bdd2ba4e 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -12,6 +12,7 @@\n #include \"object.h\"\n #include \"oid-array.h\"\n #include \"prio-queue.h\"\n+#include \"repository.h\"\n #include \"revision.h\"\n #include \"string-list.h\"\n #include \"strmap.h\"\n@@ -172,6 +173,23 @@ static int add_tree_entries(struct path_walk_context *ctx,\n \t\tif (type == OBJ_TREE)\n \t\t\tstrbuf_addch(&path, '/');\n \n+\t\tif (ctx->info->pl) {\n+\t\t\tint dtype;\n+\t\t\tenum pattern_match_result match;\n+\t\t\tmatch = path_matches_pattern_list(path.buf, path.len,\n+\t\t\t\t\t\t\t path.buf + base_len, &dtype,\n+\t\t\t\t\t\t\t ctx->info->pl,\n+\t\t\t\t\t\t\t ctx->repo->index);\n+\n+\t\t\tif (ctx->info->pl->use_cone_patterns &&\n+\t\t\t match == NOT_MATCHED)\n+\t\t\t\tcontinue;\n+\t\t\telse if (!ctx->info->pl->use_cone_patterns &&\n+\t\t\t\t type == OBJ_BLOB &&\n+\t\t\t\t match != MATCHED)\n+\t\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) {\n \t\t\tCALLOC_ARRAY(list, 1);\n \t\t\tlist->type = type;\n@@ -582,10 +600,10 @@ void path_walk_info_init(struct path_walk_info *info)\n \tmemcpy(info, &empty, sizeof(empty));\n }\n \n-void path_walk_info_clear(struct path_walk_info *info UNUSED)\n+void path_walk_info_clear(struct path_walk_info *info)\n {\n-\t/*\n-\t * This destructor is empty for now, as info->revs\n-\t * is not owned by 'struct path_walk_info'.\n-\t */\n+\tif (info->pl) {\n+\t\tclear_pattern_list(info->pl);\n+\t\tfree(info->pl);\n+\t}\n }\ndiff --git a/path-walk.h b/path-walk.h\nindex 414d6db23c2..473ee9d361c 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -6,6 +6,7 @@\n \n struct rev_info;\n struct oid_array;\n+struct pattern_list;\n \n /**\n * The type of a function pointer for the method that is called on a list of\n@@ -48,6 +49,16 @@ struct path_walk_info {\n \t * walk the children of such trees.\n \t */\n \tint prune_all_uninteresting;\n+\n+\t/**\n+\t * Specify a sparse-checkout definition to match our paths to. Do not\n+\t * walk outside of this sparse definition. If the patterns are in\n+\t * cone mode, then the search may prune directories that are outside\n+\t * of the cone. If not in cone mode, then all tree paths will be\n+\t * explored but the path_fn will only be called when the path matches\n+\t * the sparse-checkout patterns.\n+\t */\n+\tstruct pattern_list *pl;\n };\n \n #define PATH_WALK_INFO_INIT { \\\ndiff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\nindex 7f2d409c5bc..61e845e5ec2 100644\n--- a/t/helper/test-path-walk.c\n+++ b/t/helper/test-path-walk.c\n@@ -1,6 +1,7 @@\n #define USE_THE_REPOSITORY_VARIABLE\n \n #include \"test-tool.h\"\n+#include \"dir.h\"\n #include \"environment.h\"\n #include \"hex.h\"\n #include \"object-name.h\"\n@@ -9,6 +10,7 @@\n #include \"revision.h\"\n #include \"setup.h\"\n #include \"parse-options.h\"\n+#include \"strbuf.h\"\n #include \"path-walk.h\"\n #include \"oid-array.h\"\n \n@@ -65,7 +67,7 @@ static int emit_block(const char *path, struct oid_array *oids,\n \n int cmd__path_walk(int argc, const char **argv)\n {\n-\tint res;\n+\tint res, stdin_pl = 0;\n \tstruct rev_info revs = REV_INFO_INIT;\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tstruct path_walk_test_data data = { 0 };\n@@ -80,6 +82,8 @@ int cmd__path_walk(int argc, const char **argv)\n \t\t\t N_(\"toggle inclusion of tree objects\")),\n \t\tOPT_BOOL(0, \"prune\", &info.prune_all_uninteresting,\n \t\t\t N_(\"toggle pruning of uninteresting paths\")),\n+\t\tOPT_BOOL(0, \"stdin-pl\", &stdin_pl,\n+\t\t\t N_(\"read a pattern list over stdin\")),\n \t\tOPT_END(),\n \t};\n \n@@ -99,6 +103,17 @@ int cmd__path_walk(int argc, const char **argv)\n \tinfo.path_fn = emit_block;\n \tinfo.path_fn_data = &data;\n \n+\tif (stdin_pl) {\n+\t\tstruct strbuf in = STRBUF_INIT;\n+\t\tCALLOC_ARRAY(info.pl, 1);\n+\n+\t\tinfo.pl->use_cone_patterns = 1;\n+\n+\t\tstrbuf_fread(&in, 2048, stdin);\n+\t\tadd_patterns_from_buffer(in.buf, in.len, \"\", 0, info.pl);\n+\t\tstrbuf_release(&in);\n+\t}\n+\n \tres = walk_objects_by_path(&info);\n \n \tprintf(\"commits:%\" PRIuMAX \"\\n\"\n@@ -107,6 +122,11 @@ int cmd__path_walk(int argc, const char **argv)\n \t \"tags:%\" PRIuMAX \"\\n\",\n \t data.commit_nr, data.tree_nr, data.blob_nr, data.tag_nr);\n \n+\tif (info.pl) {\n+\t\tclear_pattern_list(info.pl);\n+\t\tfree(info.pl);\n+\t}\n+\n \trelease_revisions(&revs);\n \treturn res;\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 36107a51c54..6b72e9d0e31 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -77,6 +77,94 @@ test_expect_success 'do partial clone 2, backfill min batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse' '\n+\tgit clone --sparse --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill3 &&\n+\n+\t# Initial checkout includes four files at root.\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 44 missing &&\n+\n+\t# Initial sparse-checkout is just the files at root, so we get the\n+\t# older versions of the four files at tip.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace1\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 4 missing &&\n+\ttest_line_count = 40 missing &&\n+\n+\t# Expand the sparse-checkout to include 'd' recursively. This\n+\t# engages the algorithm to skip the trees for 'a'. Note that\n+\t# the \"sparse-checkout set\" command downloads the objects at tip\n+\t# to satisfy the current checkout.\n+\tgit -C backfill3 sparse-checkout set d &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace2\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 8 missing &&\n+\ttest_line_count = 24 missing\n+'\n+\n+test_expect_success 'backfill --sparse without cone mode (positive)' '\n+\tgit clone --no-checkout --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill4 &&\n+\n+\t# No blobs yet\n+\tgit -C backfill4 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 48 missing &&\n+\n+\t# Define sparse-checkout by filename regardless of parent directory.\n+\t# This downloads 6 blobs to satisfy the checkout.\n+\tgit -C backfill4 sparse-checkout set --no-cone \"**/file.1.txt\" &&\n+\tgit -C backfill4 checkout main &&\n+\n+\t# Track new blob count\n+\tgit -C backfill4 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 42 missing &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/no-cone-trace1\" git \\\n+\t\t-C backfill4 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 6 missing &&\n+\ttest_line_count = 36 missing\n+'\n+\n+test_expect_success 'backfill --sparse without cone mode (negative)' '\n+\tgit clone --no-checkout --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill5 &&\n+\n+\t# No blobs yet\n+\tgit -C backfill5 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 48 missing &&\n+\n+\t# Define sparse-checkout by filename regardless of parent directory.\n+\t# This downloads 18 blobs to satisfy the checkout\n+\tgit -C backfill5 sparse-checkout set --no-cone \"**/file*\" \"!**/file.1.txt\" &&\n+\tgit -C backfill5 checkout main &&\n+\n+\t# Track new blob count\n+\tgit -C backfill5 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 30 missing &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/no-cone-trace2\" git \\\n+\t\t-C backfill5 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 18 missing &&\n+\ttest_line_count = 12 missing\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \ndiff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh\nindex 5f04acb8a2f..c89b0f1e19d 100755\n--- a/t/t6601-path-walk.sh\n+++ b/t/t6601-path-walk.sh\n@@ -176,6 +176,38 @@ test_expect_success 'branches and indexed objects mix well' '\n \ttest_cmp_sorted expect out\n '\n \n+test_expect_success 'base & topic, sparse' '\n+\tcat >patterns <<-EOF &&\n+\t/*\n+\t!/*/\n+\t/left/\n+\tEOF\n+\n+\ttest-tool path-walk --stdin-pl -- base topic out &&\n+\n+\tcat >expect <<-EOF &&\n+\t0:commit::$(git rev-parse topic)\n+\t0:commit::$(git rev-parse base)\n+\t0:commit::$(git rev-parse base~1)\n+\t0:commit::$(git rev-parse base~2)\n+\t1:tree::$(git rev-parse topic^{tree})\n+\t1:tree::$(git rev-parse base^{tree})\n+\t1:tree::$(git rev-parse base~1^{tree})\n+\t1:tree::$(git rev-parse base~2^{tree})\n+\t2:blob:a:$(git rev-parse base~2:a)\n+\t3:tree:left/:$(git rev-parse base:left)\n+\t3:tree:left/:$(git rev-parse base~2:left)\n+\t4:blob:left/b:$(git rev-parse base~2:left/b)\n+\t4:blob:left/b:$(git rev-parse base:left/b)\n+\tblobs:3\n+\tcommits:4\n+\ttags:0\n+\ttrees:6\n+\tEOF\n+\n+\ttest_cmp_sorted expect out\n+'\n+\n test_expect_success 'topic only' '\n \ttest-tool path-walk -- topic >out &&\n \n-- \ngitgitgadget\n\n"},{"id":"511754","messageId":"f22cf8b34851a3ba4cd6ab1d31f0835579143c40.1738602667.git.gitgitgadget@gmail.com","threadId":"62610","inReplyTo":"pull.1820.v3.git.1738602667.gitgitgadget@gmail.com","subject":"[PATCH v3 5/5] backfill: assume --sparse when sparse-checkout is enabled","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-02-03T17:11:07Z","receivedAt":"2025-02-03T17:11:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change introduced the '--[no-]sparse' option for the 'git\nbackfill' command, but did not assume it as enabled by default. However,\nthis is likely the behavior that users will most often want to happen.\nWithout this default, users with a small sparse-checkout may be confused\nwhen 'git backfill' downloads every version of every object in the full\nhistory.\n\nHowever, this is left as a separate change so this decision can be reviewed\nindependently of the value of the '--[no-]sparse' option.\n\nAdd a test of adding the '--sparse' option to a repo without sparse-checkout\nto make it clear that supplying it without a sparse-checkout is an error.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 3 ++-\n builtin/backfill.c | 7 +++++++\n t/t5620-backfill.sh | 13 ++++++++++++-\n 3 files changed, 21 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex a28678983e3..95623051f78 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -59,7 +59,8 @@ OPTIONS\n \n `--[no-]sparse`::\n \tOnly download objects if they appear at a path that matches the\n-\tcurrent sparse-checkout.\n+\tcurrent sparse-checkout. If the sparse-checkout feature is enabled,\n+\tthen `--sparse` is assumed and can be disabled with `--no-sparse`.\n \n SEE ALSO\n --------\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex d7b997fd6f7..d7ee84692f3 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -1,3 +1,6 @@\n+/* We need this macro to access core_apply_sparse_checkout */\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n #include \"builtin.h\"\n #include \"git-compat-util.h\"\n #include \"config.h\"\n@@ -5,6 +8,7 @@\n #include \"repository.h\"\n #include \"commit.h\"\n #include \"dir.h\"\n+#include \"environment.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -133,6 +137,9 @@ int cmd_backfill(int argc, const char **argv, const char *prefix, struct reposit\n \n \trepo_config(repo, git_default_config, NULL);\n \n+\tif (ctx.sparse < 0)\n+\t\tctx.sparse = core_apply_sparse_checkout;\n+\n \tresult = do_backfill(&ctx);\n \tbackfill_context_clear(&ctx);\n \treturn result;\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 6b72e9d0e31..58c81556e72 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -77,6 +77,12 @@ test_expect_success 'do partial clone 2, backfill min batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse without sparse-checkout fails' '\n+\tgit init not-sparse &&\n+\ttest_must_fail git -C not-sparse backfill --sparse 2>err &&\n+\tgrep \"problem loading sparse-checkout\" err\n+'\n+\n test_expect_success 'backfill --sparse' '\n \tgit clone --sparse --filter=blob:none\t\t\\\n \t\t--single-branch --branch=main \t\t\\\n@@ -105,7 +111,12 @@ test_expect_success 'backfill --sparse' '\n \ttest_trace2_data promisor fetch_count 8 missing &&\n-\ttest_line_count = 24 missing\n+\ttest_line_count = 24 missing &&\n+\n+\t# Disabling the --sparse option (on by default) will download everything\n+\tgit -C backfill3 backfill --no-sparse &&\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 0 missing\n '\n \n test_expect_success 'backfill --sparse without cone mode (positive)' '\n-- \ngitgitgadget\n"},{"id":"511769","messageId":"xmqqwme6y32z.fsf@gitster.g","threadId":"62610","inReplyTo":"pull.1820.v3.git.1738602667.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-04T00:18:44Z","receivedAt":"2025-02-04T00:18:47Z","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 v3\n> =============\n>\n> * Rebased onto 'master' now that the path-walk API is merged.\n\nI was going to object to this rebase, as the same path-walk was\ncontained already while building the base of the series for the\nprevious rounds. IOW, \"now that the path-walk API is merged\" is not\na good excuse to rebase onto 'master'.\n\nBut then I forgot that there are other topics, like 'meson based\nbuild' and 'synopsis formatting', that were in flight at the same\ntime that have been merged to 'master'. They are good reasons why\nwe may want to rebase the updated version to 'master'.\n\nIOW ...\n\n> * New builtin boilerplate is updated with new standards, including:\n>\n> * Doc formatting uses [synopsis] formatting.\n> * Add builtin/backfill.c to meson.build.\n> * Add Documentation/git-backfill.txt to Documentation/meson.build.\n> * Add t/t5620-backfill.sh to t/meson.build.\n> * Update handling of -h due to f66d1423f5 (builtin: send usage() help text\n> to standard output, 2025-01-16).\n\n... these are all good reasons, even if path-walk were still cooking\nin 'next' (in which case, we'd prepare a custom base by merging path-walk\ninto 'master' and then apply these patches).\n\n> * Doc formatting is updated to use back-ticks on options and mark the\n> builtin as experimental.\n>\n> * The batch_size member of 'struct backfill_context' is now named\n> 'min_batch_size' in all patches.\n>\n> * Some mentions of '--batch-size' are updated to '--min-batch-size'.\n>\n> * An additional test is included for non-cone-mode sparse-checkout patterns\n> to further check the return values of path_matches_pattern_list() within\n> the path-walk API with sparse mode.\n>\n> * A use of oid_object_info_extended() is replaced with has_object().\n>\n> * The backfill_context_clear() method is called by the proper owner of the\n> struct.\n>\n> Thanks, -Stolee\n\nEverything looked great from a quick look. I'll have a more\ndetailed look later, but this round looks quite promising.\n\nThanks.\n"},{"id":"511856","messageId":"Z6MQK6anxpMhlL9i@pks.im","threadId":"62610","inReplyTo":"xmqqwme6y32z.fsf@gitster.g","subject":"Re: [PATCH v3 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-02-05T07:15:55Z","receivedAt":"2025-02-05T07:16:01Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Feb 03, 2025 at 04:18:44PM -0800, Junio C Hamano wrote:\n> Everything looked great from a quick look. I'll have a more\n> detailed look later, but this round looks quite promising.\n\nI didn't do another deep dive, but mostly had a look at my last comments\nand the range-diff. As far as I can see my comments have been addressed,\nso this version looks good to me.\n\nThanks!\n\nPatrick\n"},{"id":"511888","messageId":"xmqqpljwpbg0.fsf@gitster.g","threadId":"62610","inReplyTo":"Z6MQK6anxpMhlL9i@pks.im","subject":"Re: [PATCH v3 0/5] PATH WALK III: Add 'git backfill' command","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-05T17:07:27Z","receivedAt":"2025-02-05T17:07:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> On Mon, Feb 03, 2025 at 04:18:44PM -0800, Junio C Hamano wrote:\n>> Everything looked great from a quick look. I'll have a more\n>> detailed look later, but this round looks quite promising.\n>\n> I didn't do another deep dive, but mostly had a look at my last comments\n> and the range-diff. As far as I can see my comments have been addressed,\n> so this version looks good to me.\n\nThanks.\n"}]}