summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--pack-bitmap-write.c72
-rwxr-xr-xt/t5310-pack-bitmaps.sh85
2 files changed, 148 insertions, 9 deletions
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 7e218d0..0af9319 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -180,8 +180,10 @@ static void compute_xor_offsets(void)
struct bb_commit {
struct commit_list *reverse_edges;
+ struct bitmap *commit_mask;
struct bitmap *bitmap;
- unsigned selected:1;
+ unsigned selected:1,
+ maximal:1;
unsigned idx; /* within selected array */
};
@@ -198,7 +200,7 @@ static void bitmap_builder_init(struct bitmap_builder *bb,
{
struct rev_info revs;
struct commit *commit;
- unsigned int i;
+ unsigned int i, num_maximal;
memset(bb, 0, sizeof(*bb));
init_bb_data(&bb->data);
@@ -210,27 +212,85 @@ static void bitmap_builder_init(struct bitmap_builder *bb,
for (i = 0; i < writer->selected_nr; i++) {
struct commit *c = writer->selected[i].commit;
struct bb_commit *ent = bb_data_at(&bb->data, c);
+
ent->selected = 1;
+ ent->maximal = 1;
ent->idx = i;
+
+ ent->commit_mask = bitmap_new();
+ bitmap_set(ent->commit_mask, i);
+
add_pending_object(&revs, &c->object, "");
}
+ num_maximal = writer->selected_nr;
if (prepare_revision_walk(&revs))
die("revision walk setup failed");
while ((commit = get_revision(&revs))) {
struct commit_list *p;
+ struct bb_commit *c_ent;
parse_commit_or_die(commit);
- ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
- bb->commits[bb->commits_nr++] = commit;
+ c_ent = bb_data_at(&bb->data, commit);
+
+ if (c_ent->maximal) {
+ if (!c_ent->selected) {
+ bitmap_set(c_ent->commit_mask, num_maximal);
+ num_maximal++;
+ }
+
+ ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
+ bb->commits[bb->commits_nr++] = commit;
+ }
for (p = commit->parents; p; p = p->next) {
- struct bb_commit *ent = bb_data_at(&bb->data, p->item);
- commit_list_insert(commit, &ent->reverse_edges);
+ struct bb_commit *p_ent = bb_data_at(&bb->data, p->item);
+ int c_not_p, p_not_c;
+
+ if (!p_ent->commit_mask) {
+ p_ent->commit_mask = bitmap_new();
+ c_not_p = 1;
+ p_not_c = 0;
+ } else {
+ c_not_p = bitmap_is_subset(c_ent->commit_mask, p_ent->commit_mask);
+ p_not_c = bitmap_is_subset(p_ent->commit_mask, c_ent->commit_mask);
+ }
+
+ if (!c_not_p)
+ continue;
+
+ bitmap_or(p_ent->commit_mask, c_ent->commit_mask);
+
+ if (p_not_c)
+ p_ent->maximal = 1;
+ else {
+ p_ent->maximal = 0;
+ free_commit_list(p_ent->reverse_edges);
+ p_ent->reverse_edges = NULL;
+ }
+
+ if (c_ent->maximal) {
+ commit_list_insert(commit, &p_ent->reverse_edges);
+ } else {
+ struct commit_list *cc = c_ent->reverse_edges;
+
+ for (; cc; cc = cc->next) {
+ if (!commit_list_contains(cc->item, p_ent->reverse_edges))
+ commit_list_insert(cc->item, &p_ent->reverse_edges);
+ }
+ }
}
+
+ bitmap_free(c_ent->commit_mask);
+ c_ent->commit_mask = NULL;
}
+
+ trace2_data_intmax("pack-bitmap-write", the_repository,
+ "num_selected_commits", writer->selected_nr);
+ trace2_data_intmax("pack-bitmap-write", the_repository,
+ "num_maximal_commits", num_maximal);
}
static void bitmap_builder_clear(struct bitmap_builder *bb)
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index 1dd9723..7ba796b 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -20,12 +20,88 @@ has_any () {
grep -Ff "$1" "$2"
}
+# To ensure the logic for "maximal commits" is exercised, make
+# the repository a bit more complicated.
+#
+# other master
+# * *
+# (99 commits) (99 commits)
+# * *
+# |\ /|
+# | * octo-other octo-master * |
+# |/|\_________ ____________/|\|
+# | \ \/ __________/ |
+# | | ________/\ / |
+# * |/ * merge-right *
+# | _|__________/ \____________ |
+# |/ | \|
+# (l1) * * merge-left * (r1)
+# | / \________________________ |
+# |/ \|
+# (l2) * * (r2)
+# \___________________________ |
+# \|
+# * (base)
+#
+# The important part for the maximal commit algorithm is how
+# the bitmasks are extended. Assuming starting bit positions
+# for master (bit 0) and other (bit 1), and some flexibility
+# in the order that merge bases are visited, the bitmasks at
+# the end should be:
+#
+# master: 1 (maximal, selected)
+# other: 01 (maximal, selected)
+# octo-master: 1
+# octo-other: 01
+# merge-right: 111 (maximal)
+# (l1): 111
+# (r1): 111
+# merge-left: 1101 (maximal)
+# (l2): 11111 (maximal)
+# (r2): 111101 (maximal)
+# (base): 1111111 (maximal)
+
test_expect_success 'setup repo with moderate-sized history' '
- test_commit_bulk --id=file 100 &&
+ test_commit_bulk --id=file 10 &&
git branch -M second &&
git checkout -b other HEAD~5 &&
test_commit_bulk --id=side 10 &&
+
+ # add complicated history setup, including merges and
+ # ambiguous merge-bases
+
+ git checkout -b merge-left other~2 &&
+ git merge second~2 -m "merge-left" &&
+
+ git checkout -b merge-right second~1 &&
+ git merge other~1 -m "merge-right" &&
+
+ git checkout -b octo-second second &&
+ git merge merge-left merge-right -m "octopus-second" &&
+
+ git checkout -b octo-other other &&
+ git merge merge-left merge-right -m "octopus-other" &&
+
+ git checkout other &&
+ git merge octo-other -m "pull octopus" &&
+
+ git checkout second &&
+ git merge octo-second -m "pull octopus" &&
+
+ # Remove these branches so they are not selected
+ # as bitmap tips
+ git branch -D merge-left &&
+ git branch -D merge-right &&
+ git branch -D octo-other &&
+ git branch -D octo-second &&
+
+ # add padding to make these merges less interesting
+ # and avoid having them selected for bitmaps
+ test_commit_bulk --id=file 100 &&
+ git checkout other &&
+ test_commit_bulk --id=side 100 &&
git checkout second &&
+
bitmaptip=$(git rev-parse second) &&
blob=$(echo tagged-blob | git hash-object -w --stdin) &&
git tag tagged-blob $blob &&
@@ -33,9 +109,12 @@ test_expect_success 'setup repo with moderate-sized history' '
'
test_expect_success 'full repack creates bitmaps' '
- git repack -ad &&
+ GIT_TRACE2_EVENT_NESTING=4 GIT_TRACE2_EVENT="$(pwd)/trace" \
+ git repack -ad &&
ls .git/objects/pack/ | grep bitmap >output &&
- test_line_count = 1 output
+ test_line_count = 1 output &&
+ grep "\"key\":\"num_selected_commits\",\"value\":\"106\"" trace &&
+ grep "\"key\":\"num_maximal_commits\",\"value\":\"111\"" trace
'
test_expect_success 'rev-list --test-bitmap verifies bitmaps' '