Re: [PATCH] pack-bitmap: handle objects at bitmap position zero

On Mon, Jul 27, 2026 at 01:13:31PM -0400, David Lin wrote:

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.

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.

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< ---
diff --git a/pack-bitmap.c b/pack-bitmap.c
index d8dc4ae8d1..4e86aa15dd 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c

@@ -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 ---

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.

OK, this is obviously good.

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