From: Jeff King Date: Tue, 18 Nov 2025 08:59:49 GMT Subject: Re: [PATCH 2/9] pack-bitmap: handle name-hash lookups in incremental bitmaps Message-ID: <20251118085949.GD4164207@coredump.intra.peff.net> In-Reply-To: On Wed, Nov 12, 2025 at 09:55:03PM -0500, Taylor Blau wrote: > 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. > > +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. > > + 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. > > + 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