Re: [PATCH 1/6] Documentation/technical: describe bitmap lookup table extension

From: Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>
Date: Jun 21, 2022, 08:23 UTC
Message-ID: <20220621082308.21376-1-chakrabortyabhradeep79@gmail.com>
In-Reply-To: <b21af0bc-3234-3aa2-e4a0-82874e9a670e@github.com>

Derrick Stole <derrickstolee@github.com> wrote:

Show 5 quoted lines

> It might be worth mentioning in your commit message what happens when an
> older version of Git (or JGit) notices this flag. Does it refuse to
> operate on the .bitmap file? Does it give a warning or die? It would be
> nice if this extension could be ignored (it seems like adding the extra
> data at the end does not stop the bitmap data from being understood).

No, it doesn't refuse to operate on the .bitmap file. It just ignores the extension. Will update the commit message.

> Perhaps it would be better to say "the last N * (HASH_LEN + 8) + 4 bytes
> preceding the trailing hash" or something? This gives us a concrete way
> to compute the start of the table, while also being clear that the table
> is included in the trailing hash.

Hmm, well said. Will update it.

> Could you expand that these objects are commit OIDs, one for each bitmap
> in the file. Are they sorted in lexicographical order for binary search,
> or are we expecting to read the entire table into a hashtable in-memory?

Yeah, of course! They are sorted in lexicographical order for binary search.

> Interesting to give the xor chains directions here. You say "position"
> here for the second commit: do you mean within the list of object names
> as opposed to the offset? That would make the most sense so we can trace
> the full list of XORs we need to make all at once.

I think I blundered here. I forgot that the xor-offset is relative to the current bitmap. The current proposed code takes it as ABSOLUTE value and tries to find the commit on that position (in the list of commit ids). So, there are two faults in my code - (1) As the xor-offset have an upper limit (which is 10 probably; not sure), any of the first 10 commits is always selected. (2) As xor-offsets are relative to the current bitmap, it depends On the order of the bitmaps. These bitmaps are ordered by the date of their corresponding commit and commit ids in the lookup table are ordered lexicographically. So, we can't use that xor-offset to find the xor'd commit position.

Will fix it.

> Are .bitmap files already constrained to 4GB, so these 32-bit offsets
> make sense? Using 64-bit offsets would be a small cost here, I think,
> without needing to do any fancy "overflow" tables that could introduce
> a variable-length extension.

I think you're right. I should use 64-bit types here.

> I'm guessing this is at the end of the extension because a future flag
> could modify the length of the extension, so we need the flags to be
> in a predictable location. Could we make that clear somewhere?

Flags are at the end of this extension.

Thanks :)