Re: [PATCH 2/9] pack-bitmap: handle name-hash lookups in incremental bitmaps

From: Jeff King <peff@peff.net>
Date: Nov 18, 2025, 08:59 UTC
Message-ID: <20251118085949.GD4164207@coredump.intra.peff.net>
In-Reply-To: <aRVIh9R8Pnuk+yS0@nand.local>

On Wed, Nov 12, 2025 at 09:55:03PM -0500, Taylor Blau wrote:

Show 14 quoted lines

> On Wed, Nov 12, 2025 at 03:01:51AM -0500, Jeff King wrote:
> > As always with the midx and bitmap code, I am left unsure of which
> > ordering it is correct to use (pseudo-pack order, or lexical oid order,
> > or how each splits across incremental files). I _think_ this is right
> > because it's matching the ordering that is already used for a single
> > midx. But clearly this area is under-tested, since even when we did not
> > go off the end of the array we were probably passing back junk
> > name-hashes (either from the .bitmap file's trailing checksum, or
> > zero-padding at the end of the mapped page).
> 
> Yeah, this is the right order. "index_pos" is a good hint that this is
> in lexical order. bitmap_writer_finish() has some oid_pos() lookups that
> use index directly without sorting, so bitmap_writer_finish() expects
> this array in lexical order.

OK, that matches my analysis. I guess I was just a little surprised that the name hash is in lexical index order, and not pack order. But it definitely is according to the documentation and the implementation. I guess in the end it doesn't really matter that much either way, as you tend to reverse the pack/bit position into a lexical index position anyway to get the oid. So there is no situation where you don't have both anyway.

> Commit c528e17966 (pack-bitmap: write multi-pack bitmaps, 2021-08-31)
> has a comment in (what is now) midx-write.c explaining this assumption
> in bitmap_writer_finish(), but it should probably be documented
> explicitly in pack-bitmap.h.

Maybe, but I think I may just have been overly paranoid that I got it wrong.

Show 18 quoted lines

> > +static uint32_t bitmap_name_hash(struct bitmap_index *index, uint32_t pos)
> > +{
> > +	if (bitmap_is_midx(index)) {
> > +		while (index && pos < index->midx->num_objects_in_base)
> > +			index = index->base;
> 
> Looks good. It's too bad that we have to reimplement something very
> similar to midx_for_object(), but I agree with what you wrote in the
> patch message and this faithfully captures that. It might be worth doing
> something like:
> 
>     while (index && pos < index->midx->num_objects_in_base) {
>         ASSERT(bitmap_is_midx(index));
>         index = index->base;
>     }
> 
> , which should never trigger, but is a good sanity check. Definitely not
> worth re-rolling IMHO.

Yeah, I wondered the same thing while writing it. It would be a pretty horrid bug to have mixed entries in the linked list. But that is also what assertions are there for. ;) I added it for v2.

Show 9 quoted lines

> > +		if (!index)
> > +			BUG("NULL base bitmap for object position: %"PRIu32, pos);
> > +
> > +		pos -= index->midx->num_objects_in_base;
> > +		if (pos >= index->midx->num_objects)
> > +			BUG("out-of-bounds midx bitmap object at %"PRIu32, pos);
> 
> midx_for_object() spells this portion slightly differently, but what you
> have here is still good.

Yes, there it's a die(). But elsewhere, like in pack_pos_to_midx() and its reverse, the same situation is a BUG(). It's not clear to me we get a bit or index position that is out of bounds here (is it truly a bug or programming error, or might we get it from a corrupt on-disk file). So I think it's mostly academic, at least until somebody can generate a real corrupted case.

Show 9 quoted lines

> > +	if (!index->hashes)
> > +		return 0;
> > +
> > +	return get_be32(index->hashes + pos);
> 
> We *could* double check that that offset is within bounds of
> index->map_size, and I think that is ultimately worth doing at some
> point. But I think that stopping where you did makes sense, since it
> does the minimal thing to fix this bug.

I don't think we need to. When we open the bitmap, we check that its hash-cache size matches our expectation based on the number of objects covered by the bitmap (using bitmap_num_objects(), so either from the pack's count or the midx slice's count).

-Peff