From: Patrick Steinhardt <ps@pks.im>
To: Taylor Blau <me@ttaylorr.com>
Cc: git@vger.kernel.org, Elijah Newren <newren@gmail.com>,
Jeff King <peff@peff.net>, Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH v3 02/13] pack-revindex: prepare for incremental MIDX bitmaps
Date: Fri, 28 Feb 2025 11:01:12 +0100 [thread overview]
Message-ID: <Z8GJaFPMQtslEEt3@pks.im> (raw)
In-Reply-To: <b902513f43697e94976c1baf5598222fe2e3b847.1732054032.git.me@ttaylorr.com>
On Tue, Nov 19, 2024 at 05:07:22PM -0500, Taylor Blau wrote:
> diff --git a/pack-bitmap.c b/pack-bitmap.c
> index 4fa9dfc771a..bba9c6a905a 100644
> --- a/pack-bitmap.c
> +++ b/pack-bitmap.c
> @@ -170,6 +170,15 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
> return read_bitmap(index->map, index->map_size, &index->map_pos);
> }
>
> +static uint32_t bitmap_non_extended_bits(struct bitmap_index *index)
> +{
> + if (index->midx) {
> + struct multi_pack_index *m = index->midx;
> + return m->num_objects + m->num_objects_in_base;
> + }
> + return index->pack->num_objects;
> +}
>
> static uint32_t bitmap_num_objects(struct bitmap_index *index)
> {
> if (index->midx)
Okay, despite counting our own objects, we also need to account for any
objects that the MIDX layer that we depend on may refer to. I assume
that this is basically recursive, and that the base itself would also
account for its next layer, if any.
What is interesting to see after this commit is what callsites remain
for `bitmap_num_objects()`. Most of them are converted, but some still
exist:
- `load_bitmap_header()`, where we use it to determine the size of the
hash cache. Makes sense.
- `pseudo_merge_bitmap_for_commit()`, where we use it to compute the
merged bitmap of a specific commit. This one feels weird to me, I
would have expected to use `bitmap_non_extended_bits()` here.
- `filter_bitmap_blob_limit()`, where we seem to filter through the
bitmap of the current layer. I _think_ it makes sense to retain.
- `create_bitmap_mapping()`, which feels like it should be converted?
It would be nice to document in the commit message why those functions
don't need to be converted to help guide the reader a bit.
> diff --git a/pack-revindex.c b/pack-revindex.c
> index 22d3c234648..ce3f7ae2149 100644
> --- a/pack-revindex.c
> +++ b/pack-revindex.c
> @@ -383,8 +383,12 @@ int load_midx_revindex(struct multi_pack_index *m)
> trace2_data_string("load_midx_revindex", the_repository,
> "source", "rev");
>
> - get_midx_filename_ext(&revindex_name, m->object_dir,
> - get_midx_checksum(m), MIDX_EXT_REV);
> + if (m->has_chain)
> + get_split_midx_filename_ext(&revindex_name, m->object_dir,
> + get_midx_checksum(m), MIDX_EXT_REV);
> + else
> + get_midx_filename_ext(&revindex_name, m->object_dir,
> + get_midx_checksum(m), MIDX_EXT_REV);
>
> ret = load_revindex_from_disk(revindex_name.buf,
> m->num_objects,
Here we teach the reverse index to read indices from MIDX chains.
> @@ -471,11 +475,15 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)
>
> uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos)
> {
> + while (m && pos < m->num_objects_in_base)
> + m = m->base_midx;
> + if (!m)
> + BUG("NULL multi-pack-index for object position: %"PRIu32, pos);
> if (!m->revindex_data)
> BUG("pack_pos_to_midx: reverse index not yet loaded");
> - if (m->num_objects <= pos)
> + if (m->num_objects + m->num_objects_in_base <= pos)
> BUG("pack_pos_to_midx: out-of-bounds object at %"PRIu32, pos);
> - return get_be32(m->revindex_data + pos);
> + return get_be32(m->revindex_data + pos - m->num_objects_in_base);
> }
>
> struct midx_pack_key {
Here we teach the reverse index logic to walk the MIDX layers so that we
find the one that is supposed to contain a given position.
> @@ -491,7 +499,8 @@ static int midx_pack_order_cmp(const void *va, const void *vb)
> const struct midx_pack_key *key = va;
> struct multi_pack_index *midx = key->midx;
>
> - uint32_t versus = pack_pos_to_midx(midx, (uint32_t*)vb - (const uint32_t *)midx->revindex_data);
> + size_t pos = (uint32_t*)vb - (const uint32_t *)midx->revindex_data;
Micronit: missing space between `uint32_t` and `*`.
> + uint32_t versus = pack_pos_to_midx(midx, pos + midx->num_objects_in_base);
> uint32_t versus_pack = nth_midxed_pack_int_id(midx, versus);
> off_t versus_offset;
>
Okay, the calculation to calculate the position is basically the same,
but we now also offset the position by the number of objects in
preceding layers. Makes sense.
Patrick
next prev parent reply other threads:[~2025-02-28 10:01 UTC|newest]
Thread overview: 136+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-08-15 21:01 [PATCH 00/13] midx: incremental multi-pack indexes, part two Taylor Blau
2024-08-15 21:01 ` [PATCH 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2024-08-15 21:01 ` [PATCH 02/13] pack-revindex: prepare for " Taylor Blau
2024-08-15 21:01 ` [PATCH 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2024-08-15 21:01 ` [PATCH 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2024-08-15 21:01 ` [PATCH 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2024-08-15 21:01 ` [PATCH 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2024-08-15 21:01 ` [PATCH 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2024-08-15 21:01 ` [PATCH 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2024-08-15 21:01 ` [PATCH 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2024-08-15 21:01 ` [PATCH 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2024-08-15 21:01 ` [PATCH 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2024-08-15 21:01 ` [PATCH 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2024-08-15 21:01 ` [PATCH 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2024-08-15 22:28 ` [PATCH v2 00/13] midx: incremental multi-pack indexes, part two Taylor Blau
2024-08-15 22:28 ` [PATCH v2 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2024-08-15 22:28 ` [PATCH v2 02/13] pack-revindex: prepare for " Taylor Blau
2024-08-15 22:28 ` [PATCH v2 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2024-08-15 22:29 ` [PATCH v2 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2024-08-15 22:29 ` [PATCH v2 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2024-08-15 22:29 ` [PATCH v2 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2024-08-15 22:29 ` [PATCH v2 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2024-08-15 22:29 ` [PATCH v2 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2024-08-15 22:29 ` [PATCH v2 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2024-08-15 22:29 ` [PATCH v2 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2024-08-15 22:29 ` [PATCH v2 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2024-08-15 22:29 ` [PATCH v2 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2024-08-15 22:29 ` [PATCH v2 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2024-08-28 17:55 ` [PATCH] fixup! " Junio C Hamano
2024-08-28 18:33 ` Jeff King
2024-08-29 18:57 ` Taylor Blau
2024-08-29 19:27 ` Jeff King
2024-11-19 20:56 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 00/13] midx: incremental multi-pack indexes, part two Taylor Blau
2024-11-19 22:07 ` [PATCH v3 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-02-28 23:26 ` Taylor Blau
2025-03-03 10:54 ` Patrick Steinhardt
2024-11-19 22:07 ` [PATCH v3 02/13] pack-revindex: prepare for " Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt [this message]
2025-02-28 23:39 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-02-28 23:49 ` Taylor Blau
2025-03-03 10:55 ` Patrick Steinhardt
2024-11-19 22:07 ` [PATCH v3 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-03-01 0:12 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2024-11-19 22:07 ` [PATCH v3 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-03-01 0:16 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-03-01 0:19 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2024-11-19 22:07 ` [PATCH v3 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2024-11-19 22:07 ` [PATCH v3 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-03-01 0:22 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-03-01 0:26 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-03-01 0:28 ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2025-02-28 10:01 ` Patrick Steinhardt
2025-03-01 0:31 ` Taylor Blau
2024-11-20 8:49 ` [PATCH v3 00/13] midx: incremental multi-pack indexes, part two Junio C Hamano
2025-03-14 20:18 ` [PATCH v4 " Taylor Blau
2025-03-14 20:18 ` [PATCH v4 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2025-03-18 1:16 ` Jeff King
2025-03-18 23:11 ` Taylor Blau
2025-03-18 2:42 ` Elijah Newren
2025-03-18 23:19 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 02/13] pack-revindex: prepare for " Taylor Blau
2025-03-18 1:27 ` Jeff King
2025-03-19 0:02 ` Taylor Blau
2025-03-19 0:07 ` Taylor Blau
2025-03-26 18:08 ` Jeff King
2025-03-18 2:43 ` Elijah Newren
2025-03-19 0:03 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2025-03-18 4:13 ` Elijah Newren
2025-03-19 0:08 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2025-03-18 1:38 ` Jeff King
2025-03-19 0:13 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2025-03-14 20:18 ` [PATCH v4 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2025-03-18 4:13 ` Elijah Newren
2025-03-19 0:17 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2025-03-18 5:31 ` Elijah Newren
2025-03-19 0:30 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2025-03-18 1:41 ` Jeff King
2025-03-19 0:30 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2025-03-14 20:18 ` [PATCH v4 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2025-03-18 1:44 ` Jeff King
2025-03-19 0:33 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2025-03-18 2:01 ` Jeff King
2025-03-19 0:38 ` Taylor Blau
2025-03-18 6:43 ` Elijah Newren
2025-03-19 0:39 ` Taylor Blau
2025-03-14 20:18 ` [PATCH v4 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2025-03-18 2:05 ` Jeff King
2025-03-19 23:02 ` Taylor Blau
2025-03-14 20:19 ` [PATCH v4 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2025-03-18 2:16 ` Jeff King
2025-03-20 0:14 ` Taylor Blau
2025-03-18 17:13 ` Elijah Newren
2025-03-20 0:16 ` Taylor Blau
2025-03-18 2:21 ` [PATCH v4 00/13] midx: incremental multi-pack indexes, part two Jeff King
2025-03-20 0:18 ` Taylor Blau
2025-03-20 17:56 ` [PATCH v5 00/14] " Taylor Blau
2025-03-20 17:56 ` [PATCH v5 01/14] Documentation: remove a "future work" item from the MIDX docs Taylor Blau
2025-03-20 17:56 ` [PATCH v5 02/14] Documentation: describe incremental MIDX bitmaps Taylor Blau
2025-03-20 17:56 ` [PATCH v5 03/14] pack-revindex: prepare for " Taylor Blau
2025-03-20 17:56 ` [PATCH v5 04/14] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2025-03-20 17:56 ` [PATCH v5 05/14] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2025-03-20 17:56 ` [PATCH v5 06/14] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2025-03-20 17:56 ` [PATCH v5 07/14] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2025-03-20 17:56 ` [PATCH v5 08/14] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2025-03-20 17:56 ` Taylor Blau
2025-03-20 17:58 ` Taylor Blau
2025-03-20 17:56 ` [PATCH v5 09/14] pack-bitmap.c: compute disk-usage with " Taylor Blau
2025-03-20 17:56 ` [PATCH v5 10/14] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2025-03-20 17:56 ` [PATCH v5 11/14] ewah: implement `struct ewah_or_iterator` Taylor Blau
2025-03-20 17:57 ` [PATCH v5 12/14] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2025-03-20 17:57 ` [PATCH v5 13/14] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2025-03-20 17:57 ` [PATCH v5 14/14] midx: implement writing incremental MIDX bitmaps Taylor Blau
2025-03-20 20:00 ` [PATCH v5 00/14] midx: incremental multi-pack indexes, part two Elijah Newren
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=Z8GJaFPMQtslEEt3@pks.im \
--to=ps@pks.im \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=me@ttaylorr.com \
--cc=newren@gmail.com \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
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;
as well as URLs for NNTP newsgroup(s).