Skip to contentSkip to conversation

pack-bitmap: handle objects at bitmap position zero

PATCH Superseded David Lin 3 participants 6 messages Jul 27 – Jul 28

lore
Share & tools
lore

David Lin

author
#0 lore raw

PATCH 1/1 pack-bitmap: handle objects at bitmap position zero

bitmap_position() only returns a negative value when an object is not present in the bitmap index.

In find_objects(), we have added a check in 11d45a6e6a to avoid processing a root whose reachability is already represented by the base bitmap, but accidentally uses pos > 0. Consequently, it never performs the membership test for an object at position zero.

If that object has an individual reachability bitmap, we unnecessarily load and OR that bitmap into the base again. Otherwise, we add the object to the not-mapped list, only for the subsequent pass to recognize that it is already present. The latter pass correctly treats all non-negative positions as valid, so this does not change the resulting object set, but an off-by-one edge case.

Treat position zero as valid by changing the condition to pos >= 0.

The existing pseudo-merge traversal test exercises this case. Its position-zero commit is presented through multiple roots. Before this change, each occurrence is counted as a bitmap hit; afterwards, only the first occurrence loads the bitmap. Assert the resulting hit count to cover the boundary condition.

Thanks in advance for the review!

---
 pack-bitmap.c                   | 2 +-
 t/t5333-pseudo-merge-bitmaps.sh | 4 ++++
 2 files changed, 5 insertions(+), 1 deletion(-)
pack-bitmap.c +1 -1
index d8dc4ae8d1..e85bd69ba4 100644
@@ -1569,7 +1569,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
 
 		if (base) {
 			int pos = bitmap_position(bitmap_git, &object->oid);
-			if (pos > 0 && bitmap_get(base, pos)) {
+			if (pos >= 0 && bitmap_get(base, pos)) {
 				object->flags |= SEEN;
 				continue;
 			}
t/t5333-pseudo-merge-bitmaps.sh +4 -0
index 305d677108..2a6c0e2318 100755
@@ -85,6 +85,10 @@ test_expect_success 'bitmap traversal with pseudo-merges' '
 
 	test_pseudo_merges_satisfied 8 <trace2.txt &&
 	test_pseudo_merges_cascades 1 <trace2.txt &&
+
+	# Position zero is named by HEAD, its branch, and its tag, but its
+	# bitmap should only be loaded once.
+	test_trace2_data bitmap bitmap/hits 1 <trace2.txt &&
 	test_cmp expect actual
 '
 

base-commit: 9a0c4701dcd5725c4184599322b52933ff5005ca

Signature · 1 line
2.54.0
#1 lore raw
Quoted 4 lines · David Lin

In find_objects(), we have added a check in 11d45a6e6a to avoid processing a root whose reachability is already represented by the base bitmap, but accidentally uses pos > 0. Consequently, it never performs the membership test for an object at position zero.

Makes sense. The commit message here and below looks reasonable, but please wrap it at a maximum of 72 characters per line.

Quoted 6 lines

If that object has an individual reachability bitmap, we unnecessarily load and OR that bitmap into the base again. Otherwise, we add the object to the not-mapped list, only for the subsequent pass to recognize that it is already present. The latter pass correctly treats all non-negative positions as valid, so this does not change the resulting object set, but an off-by-one edge case.

At this point, "load" is a fairly cheap operation. We have already loaded the bits off of disk in a previous step. If the bitmap was stored as an XOR against a neighbor, we have already XOR'd it against that neighbor and stored the result.

More importantly, you're right that this does not change the result we get from the bitmap machinery. find_objects() works as follows:

1. We first start with a "roots_bitmap" (which is non-zero *only* in the positions specified by the given "roots", and *not* their reachability closure).

2. We then apply pseudo-merges to that bitmap of roots, OR-ing that into the "base" bitmap if we were able to apply a non-zero amount of pseudo-merge bitamps.

3. We then loop over all supplied "roots". If we have a "base" bitmap, we try and mark the given root as SEEN if its corresponding bit position is set. If it isn't, then we try and call the function add_commit_to_bitmap(), which ORs in a stored bitmap to "base".

4. Finally, if that fails, mark the object as not_mapped.

So in the case there are pseudo-merge bitmaps, and if one of our supplied "roots" is stored at bit position zero, then we will only fall through to the add_commit_to_bitmap() case (incrementing the "hit" count further than necessary), but othewrise marking the object as SEEN and continuing. This also sets "existing_bitmaps", which involves one extra pseudo-merge cascade.

In the case where there aren't any pseudo-merge bitmaps, the reasoning is similar, except that we must have (a) at least one "root" which has a stored bitmap, and (b) that we see the root at bit position zero *after* one or more stored bitmaps. Note that (a) and (b) can refer to the same root here, so something like:

    $ git rev-list --objects --use-bitmap-index HEAD HEAD

should do the trick.

Quoted 1 line

Treat position zero as valid by changing the condition to pos >= 0.

I briefly wondered whether other callers of bitmap_position() would have similar issues. There are a total of twelve bitmap_position() callers, and all of them except the one in this patch handle the return value correctly.

As an aside, we could consider doing something like changing the return value of bitmap_position() to indicate non-zero on failure, and zero on success, and fills the result through a uint32_t pointer. I roughed this out locally, but the patch is mostly noisy and not really worth sending.

The important part of the change is the following:

--- 8< ---

pack-bitmap.c +22 -16
index d8dc4ae8d1..4e86aa15dd 100644
@@ -1064,7 +1064,8 @@ struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
 }
 
 static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
-					   const struct object_id *oid)
+					   const struct object_id *oid,
+					   uint32_t *bitmap_pos)
 {
 	kh_oid_pos_t *positions = bitmap_git->ext_index.positions;
 	khiter_t pos = kh_get_oid_pos(positions, *oid);
@@ -1078,39 +1079,44 @@ static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
 }
 
 static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
-					   const struct object_id *oid)
+					   const struct object_id *oid,
+					   uint32_t *bitmap_pos)
 {
-	uint32_t pos;
 	off_t offset = find_pack_entry_one(oid, bitmap_git->pack);
+
 	if (!offset)
 		return -1;
 
-	if (offset_to_pack_pos(bitmap_git->pack, offset, &pos) < 0)
-		return -1;
-	return pos;
+	return offset_to_pack_pos(bitmap_git->pack, offset, bitmap_pos);
 }
 
 static int bitmap_position_midx(struct bitmap_index *bitmap_git,
-				const struct object_id *oid)
+				const struct object_id *oid,
+				uint32_t *bitmap_pos)
 {
-	uint32_t want, got;
+	uint32_t want;
+
 	if (!bsearch_midx(oid, bitmap_git->midx, &want))
 		return -1;
 
-	if (midx_to_pack_pos(bitmap_git->midx, want, &got) < 0)
-		return -1;
-	return got;
+	return midx_to_pack_pos(bitmap_git->midx, want, bitmap_pos);
 }
 
 static int bitmap_position(struct bitmap_index *bitmap_git,
-			   const struct object_id *oid)
+			   const struct object_id *oid,
+			   uint32_t *bitmap_pos)
 {
-	int pos;
+	int ret;
+
 	if (bitmap_is_midx(bitmap_git))
-		pos = bitmap_position_midx(bitmap_git, oid);
+		ret = bitmap_position_midx(bitmap_git, oid, bitmap_pos);
 	else
-		pos = bitmap_position_packfile(bitmap_git, oid);
-	return (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);
+		ret = bitmap_position_packfile(bitmap_git, oid, bitmap_pos);
+
+	if (!ret)
+		return 0;
+
+	return bitmap_position_extended(bitmap_git, oid, bitmap_pos);
 }
 
 static int ext_index_add_object(struct bitmap_index *bitmap_git,

--- >8 ---

Quoted 5 lines

The existing pseudo-merge traversal test exercises this case. Its position-zero commit is presented through multiple roots. Before this change, each occurrence is counted as a bitmap hit; afterwards, only the first occurrence loads the bitmap. Assert the resulting hit count to cover the boundary condition.

Exactly.

pack-bitmap.c static struct bitmap *find_objects(struct bitmap_index *bitmap_git, · line 1572

Quoted 10 lines
pack-bitmap.c +1 -1
index d8dc4ae8d1..e85bd69ba4 100644
@@ -1569,7 +1569,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
 
 		if (base) {
 			int pos = bitmap_position(bitmap_git, &object->oid);
-			if (pos > 0 && bitmap_get(base, pos)) {
+			if (pos >= 0 && bitmap_get(base, pos)) {

OK, this is obviously good.

Quoted 5 lines
t/t5333-pseudo-merge-bitmaps.sh +0 -0
index 305d677108..2a6c0e2318 100755

t/t5333-pseudo-merge-bitmaps.sh test_expect_success 'bitmap traversal with pseudo-merges' ' · line 93

Quoted 9 lines
t/t5333-pseudo-merge-bitmaps.sh +4 -0
@@ -85,6 +85,10 @@ test_expect_success 'bitmap traversal with pseudo-merges' '
 
 	test_pseudo_merges_satisfied 8 <trace2.txt &&
 	test_pseudo_merges_cascades 1 <trace2.txt &&
+
+	# Position zero is named by HEAD, its branch, and its tag, but its
+	# bitmap should only be loaded once.
+	test_trace2_data bitmap bitmap/hits 1 <trace2.txt &&
 	test_cmp expect actual
 '

This is good, though it is a little bit fragile in the sense that we rely on the pack ordering to place HEAD as the first object in the pack. I'm comfortable with it given the comment, which effectively documents that fragility.

However, I think it's worth covering the non-pseudo-merge case as I described above, too.

Thanks,
Taylor

author
#2 lore raw
Quoted 2 lines · Taylor Blau

Makes sense. The commit message here and below looks reasonable, but please wrap it at a maximum of 72 characters per line.

Done in v2, apologize for the formatting.

Quoted 4 lines

At this point, "load" is a fairly cheap operation. We have already loaded the bits off of disk in a previous step. If the bitmap was stored as an XOR against a neighbor, we have already XOR'd it against that neighbor and stored the result.

Agree, I reworded the commit message/comment to consolidate the wording, so that a duplicate disk read is not always implied.

Quoted 2 lines

However, I think it's worth covering the non-pseudo-merge case as I described above, too.

Good call, and thank you for the expanded explanation above, added in v2 using a duplicate HEAD traversal, as suggested.

Thanks again for the detailed review. I will send v2 shortly.

Best,
David

author
#3 lore raw

PATCH v2 1/1 pack-bitmap: handle objects at bitmap position zero

In reply to David Lin

bitmap_position() only returns a negative value when an object is not present in the bitmap index.

In find_objects(), we have added a check (11d45a6e6a) to avoid processing a root whose reachability is already represented by the base bitmap, but accidentally uses pos > 0. Consequently, it never performs the membership test for an object at position zero.

If that object has an individual reachability bitmap, we unnecessarily OR that bitmap into the base again. Otherwise, we add the object to the not-mapped list, only for the subsequent pass to recognize that it is already present. The latter pass correctly treats all non-negative positions as valid, so this does not change the resulting object set, but an off-by-one edge case.

Treat position zero as valid by changing the condition to pos >= 0.

The existing pseudo-merge traversal test exercises this case. Its position-zero commit is presented through multiple roots. Before this change, each occurrence is counted as a bitmap hit; afterwards, only the first occurrence is counted. Assert the resulting hit count to cover the boundary condition.

Also cover the non-pseudo-merge case by passing HEAD twice. The first occurrence initializes the base from its stored bitmap, and the second must recognize that position zero is already present.

---
Changes since v1:
- Clarify the bitmap disk load wordings.
- Add coverage for the non-pseudo-merge case.

 pack-bitmap.c                   |  2 +-
 t/t5333-pseudo-merge-bitmaps.sh | 14 +++++++++++++-
 2 files changed, 14 insertions(+), 2 deletions(-)
pack-bitmap.c +1 -1
index d8dc4ae8d1..e85bd69ba4 100644
@@ -1569,7 +1569,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
 
 		if (base) {
 			int pos = bitmap_position(bitmap_git, &object->oid);
-			if (pos > 0 && bitmap_get(base, pos)) {
+			if (pos >= 0 && bitmap_get(base, pos)) {
 				object->flags |= SEEN;
 				continue;
 			}
t/t5333-pseudo-merge-bitmaps.sh +13 -1
index 305d677108..5b2a17f90a 100755
@@ -50,7 +50,15 @@ test_expect_success 'bitmap traversal without pseudo-merges' '
 	test_pseudo_merges_cascades 0 <trace2.txt &&
 	test_pseudo_merges >merges &&
 	test_must_be_empty merges &&
-	test_cmp expect actual
+	test_cmp expect actual &&
+
+	: >trace2.txt &&
+	GIT_TRACE2_EVENT=$PWD/trace2.txt \
+		git rev-list --objects --use-bitmap-index HEAD HEAD >/dev/null &&
+
+	# The first HEAD initializes base from its position-zero bitmap. The
+	# duplicate root should not count as another bitmap hit.
+	test_trace2_data bitmap bitmap/hits 1 <trace2.txt
 '
 
 test_expect_success 'pseudo-merges accurately represent their objects' '
@@ -85,6 +93,10 @@ test_expect_success 'bitmap traversal with pseudo-merges' '
 
 	test_pseudo_merges_satisfied 8 <trace2.txt &&
 	test_pseudo_merges_cascades 1 <trace2.txt &&
+
+	# Position zero is named by HEAD, its branch, and its tag, but it
+	# should count as only one bitmap hit.
+	test_trace2_data bitmap bitmap/hits 1 <trace2.txt &&
 	test_cmp expect actual
 '
 

base-commit: 9a0c4701dcd5725c4184599322b52933ff5005ca

Signature · 1 line
2.54.0
#4 lore raw
Quoted 7 lines · David Lin

bitmap_position() only returns a negative value when an object is not present in the bitmap index.
...
Also cover the non-pseudo-merge case by passing HEAD twice. The first occurrence initializes the base from its stored bitmap, and the second must recognize that position zero is already present.

Quoted 6 lines

---
Changes since v1:
- Clarify the bitmap disk load wordings.
- Add coverage for the non-pseudo-merge case.

Thanks, both of you. Will queue.

#5 lore raw
Quoted 9 lines · Junio C Hamano
Quoted 7 lines · David Lin

bitmap_position() only returns a negative value when an object is not present in the bitmap index.
...
Also cover the non-pseudo-merge case by passing HEAD twice. The first occurrence initializes the base from its stored bitmap, and the second must recognize that position zero is already present.

Quoted 8 lines
Quoted 6 lines

---
Changes since v1:
- Clarify the bitmap disk load wordings.
- Add coverage for the non-pseudo-merge case.

Thanks, both of you. Will queue.

This version looks good to me.

Thanks,
Taylor