From: "brian m. carlson" <sandals@crustytoothpaste•net>
To: Patrick Steinhardt <ps@pks•im>
Cc: git@vger•kernel.org, Junio C Hamano <gitster@pobox•com>,
Ezekiel Newren <ezekielnewren@gmail•com>
Subject: Re: [PATCH 12/14] rust: add a new binary loose object map format
Date: Wed, 29 Oct 2025 01:37:49 +0000 [thread overview]
Message-ID: <aQFv7cJUYaSUipF-@fruit.crustytoothpaste.net> (raw)
In-Reply-To: <aQCKaK6kTfwoj28O@pks.im>
[-- Attachment #1: Type: text/plain, Size: 11147 bytes --]
On 2025-10-28 at 09:18:32, Patrick Steinhardt wrote:
> 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?
Sure. I will admit I'm terrible at naming things. What do you think it
should be called.
> s/enabling//
Will fix in v2.
> 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?
Sure, I can do that.
> 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.
It is the main hash. I'll update that for v2.
> > +`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?
I've actually put this into `git gc`, which will come in in a future
series, so I'll update this for v2.
> 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.
Exactly. We were discussing BLAKE3 at the contributor summit as a
potential option.
The careful reader will note that this format looks suspiciously like
pack index v3, which is intentional.
> > + * 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?
I'd imagined we could do something like fanout entries for tree
structures to help parse large trees better (since trees cannot be
binary searched). That's something I wanted to add to multi-pack index
as a set of chunks.
They are read until the end of the header section.
> 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?
Exactly. This is what we do with pack index v3 as well. As a practical
matter, every chunk of NUL padding contains 0 to 3 bytes: just enough to
align the data for 4-byte access.
> > +- 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?
No, it doesn't. The full object names are always in the order of the
first format. The shortened names for second and subsequent formats
point into an offset table that finds the offset in the first format.
Therefore, to look up an OID in the second format knowing its OID in the
first format, you use the first format's prefixes to find its offset,
verify its OID in the full object names, and then look up that offset in
the list of full object names in the second format.
To go the other way, you find the prefix in the second format, find its
corresponding offset in the mapping table, verify the full object ID in
the second format, and then look up that offset in the full object names
in the first 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.
The answer is that it very much resembles pack index v3, except that
instead of having pack order, we just always use the sorted order of the
first object format (since we don't have a pack). That also makes the
data deterministic so that we always write identical files for identical
objects.
> 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.
Yeah, and then the file gets very large. We mmap these into memory and
never free them during the life of the program (except when compacting
them and deleting the unused ones), so we want to be quite conservative
with our memory.
> 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.
We have that with the shortened object IDs and we do a binary search
over those. This is more cache-friendly and all we need to do is verify
that the full object ID matches our value (as opposed to a different
object stored elsewhere with an identical shortened prefix).
> 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.
This is very similar to what we have now, except that it has mapping
offsets for each algorithm instead of the second and subsequent
algorithms and it re-orders the location of the full object IDs.
I also intentionally wanted to produce completely deterministic output,
since in `git verify-pack` we verify that the output is byte-for-byte
identical and I wanted to have the ability to do that here as well. (It
isn't implemented yet, but that's a goal.) In order to do that, we need
to write every part of the data in a fixed order, so we'd have to define
the main table as being sorted by the first algorithm.
> With some slight adjustments one could also adapt this format to become
> streamable:
I don't think these formats are as streamable as you might like. In
order to create the tables, we need to sort the data for each algorithm
to find the short name length, which requires knowing all of the data up
front in order.
I, too, thought that might be a nice idea, but when I implemented pack
index v3, I realized that effectively all of the data has to be computed
up front. Once you do that, computing the offsets isn't hard because
it's just some addition and multiplication.
I personally like a header with offsets better than a trailer since it
makes parsing easier. We can peek at the first 64 bytes of the file to
see if it meets our needs or has data we're interested in.
--
brian m. carlson (they/them)
Toronto, Ontario, CA
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 262 bytes --]
next prev parent reply other threads:[~2025-10-29 1:37 UTC|newest]
Thread overview: 118+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-10-27 0:43 [PATCH 00/14] SHA-1/SHA-256 interoperability, part 2 brian m. carlson
2025-10-27 0:43 ` [PATCH 01/14] repository: require Rust support for interoperability brian m. carlson
2025-10-28 9:16 ` Patrick Steinhardt
2025-10-27 0:43 ` [PATCH 02/14] conversion: don't crash when no destination algo brian m. carlson
2025-10-27 0:43 ` [PATCH 03/14] hash: use uint32_t for object_id algorithm brian m. carlson
2025-10-28 9:16 ` Patrick Steinhardt
2025-10-28 18:28 ` Ezekiel Newren
2025-10-28 19:33 ` Junio C Hamano
2025-10-28 19:58 ` Ezekiel Newren
2025-10-28 20:20 ` Junio C Hamano
2025-10-30 0:23 ` brian m. carlson
2025-10-30 1:58 ` Collin Funk
2025-11-03 1:30 ` brian m. carlson
2025-10-29 0:33 ` brian m. carlson
2025-10-29 9:07 ` Patrick Steinhardt
2025-10-27 0:43 ` [PATCH 04/14] rust: add a ObjectID struct brian m. carlson
2025-10-28 9:17 ` Patrick Steinhardt
2025-10-28 19:07 ` Ezekiel Newren
2025-10-29 0:42 ` brian m. carlson
2025-10-28 19:40 ` Junio C Hamano
2025-10-29 0:47 ` brian m. carlson
2025-10-29 0:36 ` brian m. carlson
2025-10-29 9:08 ` Patrick Steinhardt
2025-10-30 0:32 ` brian m. carlson
2025-10-27 0:43 ` [PATCH 05/14] rust: add a hash algorithm abstraction brian m. carlson
2025-10-28 9:18 ` Patrick Steinhardt
2025-10-28 17:09 ` Ezekiel Newren
2025-10-28 20:00 ` Junio C Hamano
2025-10-28 20:03 ` Ezekiel Newren
2025-10-29 13:27 ` Junio C Hamano
2025-10-29 14:32 ` Junio C Hamano
2025-10-27 0:43 ` [PATCH 06/14] hash: add a function to look up hash algo structs brian m. carlson
2025-10-28 9:18 ` Patrick Steinhardt
2025-10-28 20:12 ` Junio C Hamano
2025-11-04 1:48 ` brian m. carlson
2025-11-04 10:24 ` Junio C Hamano
2025-10-27 0:43 ` [PATCH 07/14] csum-file: define hashwrite's count as a uint32_t brian m. carlson
2025-10-28 17:22 ` Ezekiel Newren
2025-10-27 0:43 ` [PATCH 08/14] write-or-die: add an fsync component for the loose object map brian m. carlson
2025-10-27 0:43 ` [PATCH 09/14] hash: expose hash context functions to Rust brian m. carlson
2025-10-29 16:32 ` Junio C Hamano
2025-10-30 21:42 ` brian m. carlson
2025-10-30 21:52 ` Junio C Hamano
2025-10-27 0:44 ` [PATCH 10/14] rust: add a build.rs script for tests brian m. carlson
2025-10-28 9:18 ` Patrick Steinhardt
2025-10-28 17:42 ` Ezekiel Newren
2025-10-29 16:43 ` Junio C Hamano
2025-10-29 22:10 ` Ezekiel Newren
2025-10-29 23:12 ` Junio C Hamano
2025-10-30 6:26 ` Patrick Steinhardt
2025-10-30 13:54 ` Junio C Hamano
2025-10-31 22:43 ` Ezekiel Newren
2025-11-01 11:18 ` Junio C Hamano
2025-10-27 0:44 ` [PATCH 11/14] rust: add functionality to hash an object brian m. carlson
2025-10-28 9:18 ` Patrick Steinhardt
2025-10-29 0:53 ` brian m. carlson
2025-10-29 9:07 ` Patrick Steinhardt
2025-10-28 18:05 ` Ezekiel Newren
2025-10-29 1:05 ` brian m. carlson
2025-10-29 16:02 ` Ben Knoble
2025-10-27 0:44 ` [PATCH 12/14] rust: add a new binary loose object map format brian m. carlson
2025-10-28 9:18 ` Patrick Steinhardt
2025-10-29 1:37 ` brian m. carlson [this message]
2025-10-29 9:07 ` Patrick Steinhardt
2025-10-29 17:03 ` Junio C Hamano
2025-10-29 18:21 ` Junio C Hamano
2025-10-27 0:44 ` [PATCH 13/14] rust: add a small wrapper around the hashfile code brian m. carlson
2025-10-28 18:19 ` Ezekiel Newren
2025-10-29 1:39 ` brian m. carlson
2025-10-27 0:44 ` [PATCH 14/14] object-file-convert: always make sure object ID algo is valid brian m. carlson
2025-10-29 20:07 ` [PATCH 00/14] SHA-1/SHA-256 interoperability, part 2 Junio C Hamano
2025-10-29 20:15 ` Junio C Hamano
2025-11-11 0:12 ` Ezekiel Newren
2025-11-14 17:25 ` Junio C Hamano
2025-11-14 21:11 ` Junio C Hamano
2025-11-17 6:56 ` Junio C Hamano
2025-11-17 22:09 ` brian m. carlson
2025-11-18 0:13 ` Junio C Hamano
2025-11-19 23:04 ` brian m. carlson
2025-11-19 23:24 ` Junio C Hamano
2025-11-19 23:37 ` Ezekiel Newren
2025-11-20 19:52 ` Ezekiel Newren
2025-11-20 23:02 ` brian m. carlson
2025-11-20 23:11 ` Ezekiel Newren
2025-11-20 23:14 ` Junio C Hamano
2025-11-17 22:16 ` [PATCH v2 00/15] " brian m. carlson
2025-11-17 22:16 ` [PATCH v2 01/15] repository: require Rust support for interoperability brian m. carlson
2025-11-17 22:16 ` [PATCH v2 02/15] conversion: don't crash when no destination algo brian m. carlson
2025-11-17 22:16 ` [PATCH v2 03/15] hash: use uint32_t for object_id algorithm brian m. carlson
2025-11-17 22:16 ` [PATCH v2 04/15] rust: add a ObjectID struct brian m. carlson
2025-11-17 22:16 ` [PATCH v2 05/15] rust: add a hash algorithm abstraction brian m. carlson
2025-11-17 22:16 ` [PATCH v2 06/15] hash: add a function to look up hash algo structs brian m. carlson
2025-11-17 22:16 ` [PATCH v2 07/15] rust: add additional helpers for ObjectID brian m. carlson
2025-11-17 22:16 ` [PATCH v2 08/15] csum-file: define hashwrite's count as a uint32_t brian m. carlson
2025-11-17 22:16 ` [PATCH v2 09/15] write-or-die: add an fsync component for the object map brian m. carlson
2025-11-17 22:16 ` [PATCH v2 10/15] hash: expose hash context functions to Rust brian m. carlson
2025-11-17 22:16 ` [PATCH v2 11/15] rust: add a build.rs script for tests brian m. carlson
2025-11-17 22:16 ` [PATCH v2 12/15] rust: add functionality to hash an object brian m. carlson
2025-11-17 22:16 ` [PATCH v2 13/15] rust: add a new binary object map format brian m. carlson
2025-11-17 22:16 ` [PATCH v2 14/15] rust: add a small wrapper around the hashfile code brian m. carlson
2025-11-17 22:16 ` [PATCH v2 15/15] object-file-convert: always make sure object ID algo is valid brian m. carlson
2026-02-07 20:04 ` [PATCH v3 00/16] SHA-1/SHA-256 interoperability, part 2 brian m. carlson
2026-02-07 20:04 ` [PATCH v3 01/16] repository: require Rust support for interoperability brian m. carlson
2026-02-07 20:04 ` [PATCH v3 02/16] conversion: don't crash when no destination algo brian m. carlson
2026-02-07 20:04 ` [PATCH v3 03/16] hash: use uint32_t for object_id algorithm brian m. carlson
2026-02-07 20:04 ` [PATCH v3 04/16] rust: add a ObjectID struct brian m. carlson
2026-02-07 20:04 ` [PATCH v3 05/16] rust: add a hash algorithm abstraction brian m. carlson
2026-02-07 20:04 ` [PATCH v3 06/16] hash: add a function to look up hash algo structs brian m. carlson
2026-02-07 20:04 ` [PATCH v3 07/16] rust: add additional helpers for ObjectID brian m. carlson
2026-02-07 20:04 ` [PATCH v3 08/16] csum-file: define hashwrite's count as a uint32_t brian m. carlson
2026-02-07 20:04 ` [PATCH v3 09/16] write-or-die: add an fsync component for the object map brian m. carlson
2026-02-07 20:04 ` [PATCH v3 10/16] hash: expose hash context functions to Rust brian m. carlson
2026-02-07 20:04 ` [PATCH v3 11/16] rust: fix linking binaries with cargo brian m. carlson
2026-02-07 20:04 ` [PATCH v3 12/16] rust: add a build.rs script for tests brian m. carlson
2026-02-07 20:04 ` [PATCH v3 13/16] rust: add functionality to hash an object brian m. carlson
2026-02-07 20:04 ` [PATCH v3 14/16] rust: add a new binary object map format brian m. carlson
2026-02-07 20:04 ` [PATCH v3 15/16] rust: add a small wrapper around the hashfile code brian m. carlson
2026-02-07 20:04 ` [PATCH v3 16/16] object-file-convert: always make sure object ID algo is valid brian m. carlson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=aQFv7cJUYaSUipF-@fruit.crustytoothpaste.net \
--to=sandals@crustytoothpaste$(echo .)net \
--cc=ezekielnewren@gmail$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=ps@pks$(echo .)im \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox