From 4f6d26b16703e59e009fe5dde923b87793c5f561 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Wed, 16 Jan 2019 10:25:58 -0800 Subject: list-objects: consume sparse tree walk When creating a pack-file using 'git pack-objects --revs' we provide a list of interesting and uninteresting commits. For example, a push operation would make the local topic branch be interesting and the known remote refs as uninteresting. We want to discover the set of new objects to send to the server as a thin pack. We walk these commits until we discover a frontier of commits such that every commit walk starting at interesting commits ends in a root commit or unintersting commit. We then need to discover which non-commit objects are reachable from uninteresting commits. This commit walk is not changing during this series. The mark_edges_uninteresting() method in list-objects.c iterates on the commit list and does the following: * If the commit is UNINTERSTING, then mark its root tree and every object it can reach as UNINTERESTING. * If the commit is interesting, then mark the root tree of every UNINTERSTING parent (and all objects that tree can reach) as UNINTERSTING. At the very end, we repeat the process on every commit directly given to the revision walk from stdin. This helps ensure we properly cover shallow commits that otherwise were not included in the frontier. The logic to recursively follow trees is in the mark_tree_uninteresting() method in revision.c. The algorithm avoids duplicate work by not recursing into trees that are already marked UNINTERSTING. Add a new 'sparse' option to the mark_edges_uninteresting() method that performs this logic in a slightly different way. As we iterate over the commits, we add all of the root trees to an oidset. Then, call mark_trees_uninteresting_sparse() on that oidset. Note that we include interesting trees in this process. The current implementation of mark_trees_unintersting_sparse() will walk the same trees as the old logic, but this will be replaced in a later change. Add a '--sparse' flag in 'git pack-objects' to call this new logic. Add a new test script t/t5322-pack-objects-sparse.sh that tests this option. The tests currently demonstrate that the resulting object list is the same as the old algorithm. This includes a case where both algorithms pack an object that is not needed by a remote due to limits on the explored set of trees. When the sparse algorithm is changed in a later commit, we will add a test that demonstrates a change of behavior in some cases. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/t5322-pack-objects-sparse.sh | 113 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 113 insertions(+) create mode 100755 t/t5322-pack-objects-sparse.sh (limited to 't') diff --git a/t/t5322-pack-objects-sparse.sh b/t/t5322-pack-objects-sparse.sh new file mode 100755 index 0000000000..30aef6498a --- /dev/null +++ b/t/t5322-pack-objects-sparse.sh @@ -0,0 +1,113 @@ +#!/bin/sh + +test_description='pack-objects object selection using sparse algorithm' +. ./test-lib.sh + +test_expect_success 'setup repo' ' + test_commit initial && + for i in $(test_seq 1 3) + do + mkdir f$i && + for j in $(test_seq 1 3) + do + mkdir f$i/f$j && + echo $j >f$i/f$j/data.txt + done + done && + git add . && + git commit -m "Initialized trees" && + for i in $(test_seq 1 3) + do + git checkout -b topic$i master && + echo change-$i >f$i/f$i/data.txt && + git commit -a -m "Changed f$i/f$i/data.txt" + done && + cat >packinput.txt <<-EOF && + topic1 + ^topic2 + ^topic3 + EOF + git rev-parse \ + topic1 \ + topic1^{tree} \ + topic1:f1 \ + topic1:f1/f1 \ + topic1:f1/f1/data.txt | sort >expect_objects.txt +' + +test_expect_success 'non-sparse pack-objects' ' + git pack-objects --stdout --revs nonsparse.pack && + git index-pack -o nonsparse.idx nonsparse.pack && + git show-index nonsparse_objects.txt && + test_cmp expect_objects.txt nonsparse_objects.txt +' + +test_expect_success 'sparse pack-objects' ' + git pack-objects --stdout --revs --sparse sparse.pack && + git index-pack -o sparse.idx sparse.pack && + git show-index sparse_objects.txt && + test_cmp expect_objects.txt sparse_objects.txt +' + +test_expect_success 'duplicate a folder from f3 and commit to topic1' ' + git checkout topic1 && + echo change-3 >f3/f3/data.txt && + git commit -a -m "Changed f3/f3/data.txt" && + git rev-parse \ + topic1~1 \ + topic1~1^{tree} \ + topic1^{tree} \ + topic1 \ + topic1:f1 \ + topic1:f1/f1 \ + topic1:f1/f1/data.txt | sort >required_objects.txt +' + +test_expect_success 'non-sparse pack-objects' ' + git pack-objects --stdout --revs nonsparse.pack && + git index-pack -o nonsparse.idx nonsparse.pack && + git show-index nonsparse_objects.txt && + comm -1 -2 required_objects.txt nonsparse_objects.txt >nonsparse_required_objects.txt && + test_cmp required_objects.txt nonsparse_required_objects.txt +' + +test_expect_success 'sparse pack-objects' ' + git pack-objects --stdout --revs --sparse sparse.pack && + git index-pack -o sparse.idx sparse.pack && + git show-index sparse_objects.txt && + comm -1 -2 required_objects.txt sparse_objects.txt >sparse_required_objects.txt && + test_cmp required_objects.txt sparse_required_objects.txt +' + +test_expect_success 'duplicate a folder from f1 into f3' ' + mkdir f3/f4 && + cp -r f1/f1/* f3/f4 && + git add f3/f4 && + git commit -m "Copied f1/f1 to f3/f4" && + cat >packinput.txt <<-EOF && + topic1 + ^topic1~1 + EOF + git rev-parse \ + topic1 \ + topic1^{tree} \ + topic1:f3 | sort >required_objects.txt +' + +test_expect_success 'non-sparse pack-objects' ' + git pack-objects --stdout --revs nonsparse.pack && + git index-pack -o nonsparse.idx nonsparse.pack && + git show-index nonsparse_objects.txt && + comm -1 -2 required_objects.txt nonsparse_objects.txt >nonsparse_required_objects.txt && + test_cmp required_objects.txt nonsparse_required_objects.txt +' + +test_expect_success 'sparse pack-objects' ' + git pack-objects --stdout --revs --sparse sparse.pack && + git index-pack -o sparse.idx sparse.pack && + git show-index sparse_objects.txt && + comm -1 -2 required_objects.txt sparse_objects.txt >sparse_required_objects.txt && + test_cmp required_objects.txt sparse_required_objects.txt +' + +test_done -- cgit v1.2.3