Re: [PATCH 12/14] rust: add a new binary loose object map format

[Patrick Steinhardt <ps@pks.im>]

On Mon, Oct 27, 2025 at 12:44:02AM +0000, brian m. carlson wrote:
> Our current loose object format has a few problems.  First, it is not
> efficient: the list of object IDs is not sorted and even if it were,
> there would not be an efficient way to look up objects in both
> algorithms.
> 
> Second, we need to store mappings for things which are not technically
> loose objects but are not packed objects, either, and so cannot be
> stored in a pack index.  These kinds of things include shallows, their
> parents, and their trees, as well as submodules. Yet we also need to
> implement a sensible way to store the kind of object so that we can
> prune unneeded entries.  For instance, if the user has updated the
> shallows, we can remove the old values.

Doesn't this indicate that calling this "loose object map" is kind of a
misnomer? If we want to be able to store arbitrary objects regardless of
the way those are stored (or not stored) in the ODB then I think it's
overall quite confusing to have "loose" in the name.

This isn't something we can fix for the old loose object map. But
shouldn't we fix this now for the new format you're about to introduce?

> For these reasons, introduce a new binary loose object map format.  The
> careful reader will notice that it resembles very closely the pack index
> v3 format.  Add an in-memory loose object map as well, and allow
> enabling writing to a batched map, which can then be written later as
> one of the binary loose object maps.  Include several tests for round
> tripping and data lookup across algorithms.

s/enabling//

> diff --git a/Documentation/gitformat-loose.adoc b/Documentation/gitformat-loose.adoc
> index 947993663e..4850c91669 100644
> --- a/Documentation/gitformat-loose.adoc
> +++ b/Documentation/gitformat-loose.adoc
> @@ -48,6 +50,108 @@ stored under
>  Similarly, a blob containing the contents `abc` would have the uncompressed
>  data of `blob 3\0abc`.
>  
> +== Loose object mapping
> +
> +When the `compatObjectFormat` option is used, Git needs to store a mapping
> +between the repository's main algorithm and the compatibility algorithm. There
> +are two formats for this: the legacy mapping and the modern mapping.
> +
> +=== Legacy mapping
> +
> +The compatibility mapping is stored in a file called
> +`$GIT_DIR/objects/loose-object-idx`.  The format of this file looks like this:
> +
> +  # loose-object-idx
> +  (main-name SP compat-name LF)*
> +
> +`main-name` refers to hexadecimal object ID of the object in the main
> +repository format and `compat-name` refers to the same thing, but for the
> +compatibility format.
> +
> +This format is read if it exists but is not written.
> +
> +Note that carriage returns are not permitted in this file, regardless of the
> +host system or configuration.

As far as I understood, this legacy mapping wasn't really used anywhere
as it is basically nonfunctional in the first place. Can we get away
with dropping it altogether?

> +=== Modern mapping
> +
> +The modern mapping consists of a set of files under `$GIT_DIR/objects/loose`
> +ending in `.map`.  The portion of the filename before the extension is that of
> +the hash checksum in hex format.

Given that we're talking about multiple different hashes: which hash
function is used for this checksum? I assume it's the main hash, but it
might be sensible to document this.

> +`git pack-objects` will repack existing entries into one file, removing any
> +unnecessary objects, such as obsolete shallow entries or loose objects that
> +have been packed.

Curious that this is put into git-pack-objects(1), as it doesn't quite
feel related to the task. Sure, it generates packfiles, but it doesn't
really handle the logic to manage loose objects/packfiles in the repo.
This feels closer to what git-repack(1) is doing, so would that be a
better place to put it?

> +==== Mapping file format
> +
> +- A header appears at the beginning and consists of the following:
> +	* A 4-byte mapping signature: `LMAP`
> +	* 4-byte version number: 1
> +	* 4-byte length of the header section.
> +	* 4-byte number of objects declared in this map file.
> +	* 4-byte number of object formats declared in this map file.
> +  * For each object format:
> +    ** 4-byte format identifier (e.g., `sha1` for SHA-1)
> +    ** 4-byte length in bytes of shortened object names. This is the
> +      shortest possible length needed to make names in the shortened
> +      object name table unambiguous.
> +    ** 8-byte integer, recording where tables relating to this format
> +      are stored in this index file, as an offset from the beginning.

As far as I understand this allows us to even store multiple
compatibility hashes if we were ever to grow a third hash. We would
still be able to binary-search through the file as we can compute the
size of every record with this header.

> +  * 8-byte offset to the trailer from the beginning of this file.
> +	* Zero or more additional key/value pairs (4-byte key, 4-byte value), which
> +		may optionally declare one or more chunks.  No chunks are currently
> +		defined. Readers must ignore unrecognized keys.

How does the reader identify these key/value pairs and know how many of
those there are? Also, do you already have an idea what those should be
used for?

> +- Zero or more NUL bytes.  These are used to improve the alignment of the
> +	4-byte quantities below.

How does one figure out how many NUL bytes there's going to be? I guess
the reader doesn't need to know as it simply uses the length of the
header section to seek to the tables?

> +- Tables for the first object format:
> +	* A sorted table of shortened object names.  These are prefixes of the names
> +		of all objects in this file, packed together without offset values to
> +		reduce the cache footprint of the binary search for a specific object name.

Okay. The length of the shortened object names is encoded in the header,
so all of the objects have the same length.

Does the reader have a way to disambiguate the shortened object names?
They may be unambiguous at the point in time where the mapping is
written, but when they are being shortened it becomes plausible that the
object names becomes ambiguous at a later point in time. 

> +  * A sorted table of full object names.

Ah, I see! We have a second table further down that encodes full object
names, so yes, we can fully disambiguate.

> +	* A table of 4-byte metadata values.
> +	* Zero or more chunks.  A chunk starts with a four-byte chunk identifier and
> +		a four-byte parameter (which, if unneeded, is all zeros) and an eight-byte
> +		size (not including the identifier, parameter, or size), plus the chunk
> +		data.
> +- Zero or more NUL bytes.
> +- Tables for subsequent object formats:
> +	* A sorted table of shortened object names.  These are prefixes of the names
> +		of all objects in this file, packed together without offset values to
> +		reduce the cache footprint of the binary search for a specific object name.
> +  * A table of full object names in the order specified by the first object format.

Interesting, why are these sorted by the first object format again?
Doesn't that mean that I have to do a linear search now to locate the
entry for the second object format?

    Disclaimer: the following paragraphs go into how I would have
    designed this. This is _not_ meant as a "you have to do it this
    way", but as a discussion starter to figure out why you have picked
    the proposed format and for me to get a better understanding of it.

Stepping back a bit, my expectation is that we'd have one lookup table
per object format so that we can map into all directions: SHA1 -> SHA256
and in reverse. If we had more than two hash functions we'd also need to
have a table for e.g. Blake3 -> SHA1 and Blake3 -> SHA256 and reverse.

One way to do this is to have three tables, one for each object format.
The object formats would be ordered lexicographically by their own
object ID, so that one can perform a binary search for an object ID in
every format.

Each row could then either contain all compatibility hashes directly,
but this would explode quite fast in storage space. An optimization
would thus be to have one table per object format that contains the
shortened object ID plus an offset where the actual record can be found.
You know where to find the tables from the header, and you know the
exact size of each entry, so you can trivially perform a binary search
for the abbreviated object ID in that index.

Once you've found that index you take the stored offset to look up the
record in the "main" table. This main table contains the full object IDs
for all object hashes. So something like the following simplified
format:

        +---------------------------------+
        | header                          |
        | Format version                  |
        | Number of object IDs            |
        | SHA1: abbrev, offset            |
        | SHA256: abbrev, offset          |
        | Blake3: abbrev, offset          |
        | Main: offset                    |
        +---------------------------------+
        | table for SHA1                  |
        | 11111 -> 1                      |
        | 22222 -> 2                      |
        +---------------------------------+
        | table for SHA256                |
        | aaaaa -> 2                      |
        | bbbbb -> 1                      |
        +---------------------------------+
        | table for Blake3                |
        | 88888 -> 2                      |
        | 99999 -> 1                      |
        +---------------------------------+
        | main table                      |
        | 11111111 -> bbbbbbbb -> 9999999 |
        | 22222222 -> aaaaaaaa -> 8888888 |
        +---------------------------------+
        | trailer                         |
        | trailer hash                    |
        +---------------------------------+

Overall you only have to store the full object ID for each hash exactly
once, and the mappings also only have to be stored once. But you can
look up an ID by each of its formats via its indices.

With some slight adjustments one could also adapt this format to become
streamable:

  - The header only contains the format information as well as which
    hash functions are contained.

  - The header is followed by the main table. The order of these objects
    is basically the streaming order, we don't care about it. We also
    don't have to abbreviate any hashes here. Like this we can stream
    the mappings to disk one by one, and we only need to remember the
    specific offsets where each mapping was stored.

  - Once all mappings have been streamed we can then write the lookup
    tables. We remember the starting index for each lookup table.

  - The footer contains the number of records stored in the table as
    well as the individual abbreviated object ID lengths per hash. From
    that number it becomes trivial to compute the offsets of every
    single lookup table. The offset of the main table is static.

        +---------------------------------+
        | header                          |
        | Format version                  |
        | SHA1                            |
        | SHA256                          |
        | Blake3                          |
        +---------------------------------+
        | main table                      |
        | 11111111 -> bbbbbbbb -> 9999999 |
        | 22222222 -> aaaaaaaa -> 8888888 |
        +---------------------------------+
        | table for SHA1                  |
        | 11111 -> 1                      |
        | 22222 -> 2                      |
        +---------------------------------+
        | table for SHA256                |
        | aaaaa -> 2                      |
        | bbbbb -> 1                      |
        +---------------------------------+
        | table for Blake3                |
        | 88888 -> 2                      |
        | 99999 -> 1                      |
        +---------------------------------+
        | trailer                         |
        | number of objects               |
        | SHA1 abbrev                     |
        | SHA256 abbrev                   |
        | Blake3 abbrev                   |
        | hash                            |
        +---------------------------------+

Anyway, this is how I would have designed this format, and I think your
format works differently. As I said, my intent here is not to say that
you should take my format, but I mostly intend it as a discussion
starter to figure out why you have chosen the proposed design so that I
can get a better understanding for it.

Thanks!

Patrick