Re: [PATCH v5 00/14] midx: incremental multi-pack indexes, part two
From: Elijah Newren <hidden>
Date: 2025-03-20 20:00:29
On Thu, Mar 20, 2025 at 10:56 AM Taylor Blau [off-list ref] wrote:
This is another new round of my series to implement bitmap support for incremental multi-pack indexes (MIDXs). It is still based on 683c54c999 (Git 2.49, 2025-03-14). == Changes since last time This round addresses thorough review from Elijah and Peff. The series substantively is unchanged, but there are lots of little quality-of-life and commit message readability improvements throughout. As usual, there is a range-diff below for convenience.
[...]
Range-diff against v4:
-: ---------- > 1: 6af65fdaac Documentation: remove a "future work" item from the MIDX docs
1: f565f2fff1 ! 2: 0897359506 Documentation: describe incremental MIDX bitmaps
@@ Documentation/technical/multi-pack-index.adoc: objects_nr($H2) + objects_nr($H1)
+`o1` and `o2` are compared as follows:
+
+1. If `o1` appears in an earlier layer of the MIDX chain than `o2`, then
-+ `o1` is considered less than `o2`.
++ `o1` sorts ahead of `o2`.
+
+2. Otherwise, if `o1` and `o2` appear in the same MIDX layer, and that
+ MIDX layer has no base, then if one of `pack(o1)` and `pack(o2)` is
-+ preferred and the other is not, then the preferred one sorts first. If
-+ there is a base layer (i.e. the MIDX layer is not the first layer in
-+ the chain), then if `pack(o1)` appears earlier in that MIDX layer's
-+ pack order, than `o1` is less than `o2`. Likewise if `pack(o2)`
-+ appears earlier, than the opposite is true.
++ preferred and the other is not, then the preferred one sorts ahead of
++ the non-preferred one. If there is a base layer (i.e. the MIDX layer
++ is not the first layer in the chain), then if `pack(o1)` appears
++ earlier in that MIDX layer's pack order, then `o1` sorts ahead of
++ `o2`. Likewise if `pack(o2)` appears earlier, then the opposite is
++ true.
+
+3. Otherwise, `o1` and `o2` appear in the same pack, and thus in the
+ same MIDX layer. Sort `o1` and `o2` by their offset within their
@@ Documentation/technical/multi-pack-index.adoc: objects_nr($H2) + objects_nr($H1)
+The structure of a `*.bitmap` file belonging to an incremental MIDX
+chain is identical to that of a non-incremental MIDX bitmap, or a
+classic single-pack bitmap. Since objects are added to the end of the
-+incremental MIDX's pseudo-pack order (see: above), it is possible to
++incremental MIDX's pseudo-pack order (see above), it is possible to
+extend a bitmap when appending to the end of a MIDX chain.
+
+(Note: it is possible likewise to compress a contiguous sequence of MIDX
-+incremental layers, and their `*.bitmap`(s) into a single layer and
++incremental layers, and their `*.bitmap` files into a single layer and
+`*.bitmap`, but this is not yet implemented.)
+
+The object positions used are global within the pseudo-pack order, so
2: f2a232e556 ! 3: 5eac0d1485 pack-revindex: prepare for incremental MIDX bitmaps
@@ Commit message
incremental or not.
- pack_pos_to_midx() and midx_to_pack_pos() now both take in a global
- object position in the MIDX pseudo-pack order, and finds the
+ object position in the MIDX pseudo-pack order, and find the
earliest containing MIDX (similar to midx.c::midx_for_object().
- midx_pack_order_cmp() adjusts its call to pack_pos_to_midx() by the
@@ pack-bitmap.c: static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *ind
return read_bitmap(index->map, index->map_size, &index->map_pos);
}
-+static uint32_t bitmap_non_extended_bits(struct bitmap_index *index)
++static uint32_t bitmap_num_objects_total(struct bitmap_index *index)
+{
+ if (index->midx) {
+ struct multi_pack_index *m = index->midx;
@@ pack-bitmap.c: static inline int bitmap_position_extended(struct bitmap_index *b
if (pos < kh_end(positions)) {
int bitmap_pos = kh_value(positions, pos);
- return bitmap_pos + bitmap_num_objects(bitmap_git);
-+ return bitmap_pos + bitmap_non_extended_bits(bitmap_git);
++ return bitmap_pos + bitmap_num_objects_total(bitmap_git);
}
return -1;
@@ pack-bitmap.c: static int ext_index_add_object(struct bitmap_index *bitmap_git,
}
- return bitmap_pos + bitmap_num_objects(bitmap_git);
-+ return bitmap_pos + bitmap_non_extended_bits(bitmap_git);
++ return bitmap_pos + bitmap_num_objects_total(bitmap_git);
}
struct bitmap_show_data {
@@ pack-bitmap.c: static void show_extended_objects(struct bitmap_index *bitmap_git
- if (!bitmap_get(objects, st_add(bitmap_num_objects(bitmap_git), i)))
+ if (!bitmap_get(objects,
-+ st_add(bitmap_non_extended_bits(bitmap_git), i)))
++ st_add(bitmap_num_objects_total(bitmap_git),
++ i)))
continue;
obj = eindex->objects[i];
@@ pack-bitmap.c: static void filter_bitmap_exclude_type(struct bitmap_index *bitma
*/
for (i = 0; i < eindex->count; i++) {
- size_t pos = st_add(i, bitmap_num_objects(bitmap_git));
-+ size_t pos = st_add(i, bitmap_non_extended_bits(bitmap_git));
++ size_t pos = st_add(i, bitmap_num_objects_total(bitmap_git));
if (eindex->objects[i]->type == type &&
bitmap_get(to_filter, pos) &&
!bitmap_get(tips, pos))
@@ pack-bitmap.c: static unsigned long get_size_by_pos(struct bitmap_index *bitmap_
oi.sizep = &size;
- if (pos < bitmap_num_objects(bitmap_git)) {
-+ if (pos < bitmap_non_extended_bits(bitmap_git)) {
++ if (pos < bitmap_num_objects_total(bitmap_git)) {
struct packed_git *pack;
off_t ofs;
@@ pack-bitmap.c: static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
+ die(_("unable to get size of %s"), oid_to_hex(&oid));
}
} else {
++ size_t eindex_pos = pos - bitmap_num_objects_total(bitmap_git);
struct eindex *eindex = &bitmap_git->ext_index;
- struct object *obj = eindex->objects[pos - bitmap_num_objects(bitmap_git)];
-+ struct object *obj = eindex->objects[pos - bitmap_non_extended_bits(bitmap_git)];
++ struct object *obj = eindex->objects[eindex_pos];
if (oid_object_info_extended(bitmap_repo(bitmap_git), &obj->oid,
&oi, 0) < 0)
die(_("unable to get size of %s"), oid_to_hex(&obj->oid));
@@ pack-bitmap.c: static void filter_packed_objects_from_bitmap(struct bitmap_index
size_t i, pos;
- objects_nr = bitmap_num_objects(bitmap_git);
-+ objects_nr = bitmap_non_extended_bits(bitmap_git);
++ objects_nr = bitmap_num_objects_total(bitmap_git);
pos = objects_nr / BITS_IN_EWORD;
if (pos > result->word_alloc)
@@ pack-bitmap.c: static uint32_t count_object_type(struct bitmap_index *bitmap_git
if (eindex->objects[i]->type == type &&
bitmap_get(objects,
- st_add(bitmap_num_objects(bitmap_git), i)))
-+ st_add(bitmap_non_extended_bits(bitmap_git), i)))
++ st_add(bitmap_num_objects_total(bitmap_git), i)))
count++;
}
@@ pack-bitmap.c: uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
"extension");
- num_objects = bitmap_num_objects(bitmap_git);
-+ num_objects = bitmap_non_extended_bits(bitmap_git);
++ num_objects = bitmap_num_objects_total(bitmap_git);
CALLOC_ARRAY(reposition, num_objects);
for (i = 0; i < num_objects; ++i) {
@@ pack-bitmap.c: static off_t get_disk_usage_for_extended(struct bitmap_index *bit
if (!bitmap_get(result,
- st_add(bitmap_num_objects(bitmap_git), i)))
-+ st_add(bitmap_non_extended_bits(bitmap_git), i)))
++ st_add(bitmap_num_objects_total(bitmap_git),
++ i)))
continue;
if (oid_object_info_extended(bitmap_repo(bitmap_git), &obj->oid,
3: aca0318fb1 ! 4: 922ea2f607 pack-bitmap.c: open and store incremental bitmap layers
@@ Commit message
with the previous MIDX layer.
The changes in this commit are mostly boilerplate to open the correct
- bitmap(s), add them to the chain bitmap layers along the "base" pointer,
- ensures that the correct packs and their reverse indexes are loaded
- across MIDX layers, etc.
+ bitmap(s), add them to the chain of bitmap layers along the "base"
+ pointer, ensure that the correct packs and their reverse indexes are
+ loaded across MIDX layers, etc.
While we're at it, keep track of a base_nr field to indicate how many
bitmap layers (including the current bitmap) exist. This will be used in
4: 832fd0e8dc = 5: 8fedd96614 pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs
5: c7c9f89956 = 6: dccc1b2d2e pack-bitmap.c: teach `show_objects_for_type()` about incremental MIDXs
6: 14d3d80c3d ! 7: e31bddd240 pack-bitmap.c: support bitmap pack-reuse with incremental MIDXs
@@ Commit message
Likewise, in reuse_partial_packfile_from_bitmap(), when reusing only a
single pack from a MIDX, use the oldest layer's preferred pack as it is
- likely to contain the most amount of reusable sections.
+ likely to contain the largest number of reusable sections.
Signed-off-by: Taylor Blau [off-list ref]
7: b45a9ccbc2 ! 8: d9dfcb5a1b pack-bitmap.c: teach `rev-list --test-bitmap` about incremental MIDXs
@@ pack-bitmap.c: static void test_show_commit(struct commit *commit, void *data)
+ tdata->tags = ewah_to_bitmap(bitmap_git->tags);
+
+ if (bitmap_git->base) {
-+ CALLOC_ARRAY(tdata->base_tdata, 1);
++ tdata->base_tdata = xmalloc(sizeof(struct bitmap_test_data));
+ bitmap_test_data_prepare(tdata->base_tdata, bitmap_git->base);
+ }
+}
8: c1eefeae99 = 9: b1bd60d25d pack-bitmap.c: compute disk-usage with incremental MIDXs
9: 11c4b7b949 = 10: 7477a8ac03 pack-bitmap.c: apply pseudo-merge commits with incremental MIDXs
10: cb08ad6a62 ! 11: 0fbef17acc ewah: implement `struct ewah_or_iterator`
@@ ewah/ewah_bitmap.c: void ewah_iterator_init(struct ewah_iterator *it, struct ewa
+ return ret;
+}
+
-+void ewah_or_iterator_free(struct ewah_or_iterator *it)
++void ewah_or_iterator_release(struct ewah_or_iterator *it)
+{
+ free(it->its);
+}
@@ ewah/ewok.h: void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitma
+
+int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it);
+
-+void ewah_or_iterator_free(struct ewah_or_iterator *it);
++void ewah_or_iterator_release(struct ewah_or_iterator *it);
+
void ewah_xor(
struct ewah_bitmap *ewah_i,
11: a29f4ee60d ! 12: 439e743fd5 pack-bitmap.c: keep track of each layer's type bitmaps
@@ pack-bitmap.c: struct bitmap_index {
+ * commits_all[n-2] is the commits field of this bitmap's
+ * 'base', and so on.
+ *
-+ * When either associated either with a non-incremental MIDX, or
-+ * a single packfile, these arrays each contain a single
-+ * element.
++ * When associated either with a non-incremental MIDX or a
++ * single packfile, these arrays each contain a single element.
+ */
+ struct ewah_bitmap **commits_all;
+ struct ewah_bitmap **trees_all;
12: a1cf65bedc ! 13: dcb45e349e pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators
@@ pack-bitmap.c: static void show_objects_for_type(
}
}
+
-+ ewah_or_iterator_free(&it);
++ ewah_or_iterator_release(&it);
}
static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
@@ pack-bitmap.c: static void filter_bitmap_exclude_type(struct bitmap_index *bitma
bitmap_unset(to_filter, pos);
}
-+ ewah_or_iterator_free(&it);
++ ewah_or_iterator_release(&it);
bitmap_free(tips);
}
@@ pack-bitmap.c: static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_
bitmap_unset(to_filter, pos);
}
-+ ewah_or_iterator_free(&it);
++ ewah_or_iterator_release(&it);
bitmap_free(tips);
}
@@ pack-bitmap.c: static uint32_t count_object_type(struct bitmap_index *bitmap_git
count++;
}
-+ ewah_or_iterator_free(&it);
++ ewah_or_iterator_release(&it);
+
return count;
}
@@ pack-bitmap.c: static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_
}
}
-+ ewah_or_iterator_free(&it);
++ ewah_or_iterator_release(&it);
+
return total;
}
13: d0d564685b ! 14: 13568cfa3b midx: implement writing incremental MIDX bitmaps
@@ builtin/pack-objects.c: static void write_pack_file(void)
bitmap_writer_build_type_index(&bitmap_writer,
written_list);
- ## ewah/ewah_bitmap.c ##
-@@ ewah/ewah_bitmap.c: int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it)
- return ret;
- }
-
--void ewah_or_iterator_free(struct ewah_or_iterator *it)
-+void ewah_or_iterator_release(struct ewah_or_iterator *it)
- {
- free(it->its);
- }
-
- ## ewah/ewok.h ##
-@@ ewah/ewok.h: void ewah_or_iterator_init(struct ewah_or_iterator *it,
-
- int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it);
-
--void ewah_or_iterator_free(struct ewah_or_iterator *it);
-+void ewah_or_iterator_release(struct ewah_or_iterator *it);
-
- void ewah_xor(
- struct ewah_bitmap *ewah_i,
-
## midx-write.c ##
@@ midx-write.c: static uint32_t *midx_pack_order(struct write_midx_context *ctx)
return pack_order;
@@ pack-bitmap-write.c: void bitmap_writer_finish(struct bitmap_writer *writer,
write_selected_commits_v1(writer, f, offsets);
- ## pack-bitmap.c ##
-@@ pack-bitmap.c: static void show_objects_for_type(
- }
- }
-
-- ewah_or_iterator_free(&it);
-+ ewah_or_iterator_release(&it);
- }
-
- static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
-@@ pack-bitmap.c: static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
- bitmap_unset(to_filter, pos);
- }
-
-- ewah_or_iterator_free(&it);
-+ ewah_or_iterator_release(&it);
- bitmap_free(tips);
- }
-
-@@ pack-bitmap.c: static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
- bitmap_unset(to_filter, pos);
- }
-
-- ewah_or_iterator_free(&it);
-+ ewah_or_iterator_release(&it);
- bitmap_free(tips);
- }
-
-@@ pack-bitmap.c: static uint32_t count_object_type(struct bitmap_index *bitmap_git,
- count++;
- }
-
-- ewah_or_iterator_free(&it);
-+ ewah_or_iterator_release(&it);
-
- return count;
- }
-@@ pack-bitmap.c: static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git,
- }
- }
-
-- ewah_or_iterator_free(&it);
-+ ewah_or_iterator_release(&it);
-
- return total;
- }
-
## pack-bitmap.h ##
@@ pack-bitmap.h: struct bitmap_writer {
@@ t/t5334-incremental-multi-pack-index.sh: test_expect_success 'convert incrementa
+'
+
+test_expect_success 'midx verify with multiple layers' '
++ test_path_is_file "$midx_chain" &&
++ test_line_count = 2 "$midx_chain" &&
++
+ git multi-pack-index verify
+'
+
base-commit: 683c54c999c301c2cd6f715c411407c413b1d84e
--
2.49.0.14.g88b49c1b34Reading the range-diff plus the new first patch, all my feedback has been addressed with this round.