git/pack-bitmap.h, branch v2.48.2

pack-bitmap: tag bitmapped packs with their corresponding MIDX

2024-08-27T21:50:26Z

The next commit will need to use the bitmap's MIDX (if one exists) to translate bit positions into pack-relative positions in the source pack. Ordinarily, we'd use the "midx" field of the bitmap_index struct. But since that struct is defined within pack-bitmap.c, and our caller is in a separate compilation unit, we do not have access to the MIDX field. Instead, add a "from_midx" field to the bitmapped_pack structure so that we can use that piece of data from outside of pack-bitmap.c. The caller that uses this new piece of information will be added in the following commit. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pack-bitmap: drop redundant args from `bitmap_writer_finish()`

2024-08-15T18:23:15Z

In a similar fashion as the previous commit, drop a redundant argument from the `bitmap_writer_finish()` function. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pack-bitmap: drop redundant args from `bitmap_writer_build()`

2024-08-15T18:22:27Z

In a similar fashion as the previous commit, drop a redundant argument from the `bitmap_writer_build()` function. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pack-bitmap: drop redundant args from `bitmap_writer_build_type_index()`

2024-08-15T18:20:24Z

The previous commit ensures that the bitmap_writer's "to_pack" field is initialized early on, so the "to_pack" and "index_nr" arguments to `bitmap_writer_build_type_index()` are redundant. Drop them and adjust the callers accordingly. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pack-bitmap: initialize `bitmap_writer_init()` with packing_data

2024-08-15T18:18:04Z

In order to determine its object order, the pack-bitmap machinery keeps a 'struct packing_data' corresponding to the pack or pseudo-pack (when writing a MIDX bitmap) being written. The to_pack field is provided to the bitmap machinery by callers of bitmap_writer_build() and assigned to the bitmap_writer struct at that point. But a subsequent commit will want to have access to that data earlier on during commit selection. Prepare for that by adding a 'to_pack' argument to 'bitmap_writer_init()', and initializing the field during that function. Subsequent commits will clean up other functions which take now-redundant arguments (like nr_objects, which is equivalent to pdata->objects_nr, or pdata itself). Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pseudo-merge: implement support for finding existing merges

2024-05-24T18:40:44Z

This patch implements support for reusing existing pseudo-merge commits when writing bitmaps when there is an existing pseudo-merge bitmap which has exactly the same set of parents as one that we are about to write. Note that unstable pseudo-merges are likely to change between consecutive repacks, and so are generally poor candidates for reuse. However, stable pseudo-merges (see the configuration option 'bitmapPseudoMerge..stableThreshold') are by definition unlikely to change between runs (as they represent long-running branches). Because there is no index from a *set* of pseudo-merge parents to a matching pseudo-merge bitmap, we have to construct the bitmap corresponding to the set of parents for each pending pseudo-merge commit and see if a matching bitmap exists. This is technically quadratic in the number of pseudo-merges, but is OK in practice for a couple of reasons: - non-matching pseudo-merge bitmaps are rejected quickly as soon as they differ in a single bit - already-matched pseudo-merge bitmaps are discarded from subsequent rounds of search - the number of pseudo-merges is generally small, even for large repositories In order to do this, implement (a) a function that finds a matching pseudo-merge given some uncompressed bitset describing its parents, (b) a function that computes the bitset of parents for a given pseudo-merge commit, and (c) call that function before computing the set of reachable objects for some pending pseudo-merge. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pack-bitmap: implement test helpers for pseudo-merge

2024-05-24T18:40:43Z

Implement three new sub-commands for the "bitmap" test-helper: - t/helper test-tool bitmap dump-pseudo-merges - t/helper test-tool bitmap dump-pseudo-merge-commits - t/helper test-tool bitmap dump-pseudo-merge-objects These three helpers dump the list of pseudo merges, the "parents" of the nth pseudo-merges, and the set of objects reachable from those parents, respectively. These helpers will be useful in subsequent patches when we add test coverage for pseudo-merge bitmaps. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pack-bitmap: extract `read_bitmap()` function

2024-05-24T18:40:42Z

The pack-bitmap machinery uses the `read_bitmap_1()` function to read a bitmap from within the mmap'd region corresponding to the .bitmap file. As as side-effect of calling this function, `read_bitmap_1()` increments the `index->map_pos` variable to reflect the number of bytes read. Extract the core of this routine to a separate function (that operates over a `const unsigned char *`, a `size_t` and a `size_t *` pointer) instead of a `struct bitmap_index *` pointer. This function (called `read_bitmap()`) is part of the pack-bitmap.h API so that it can be used within the upcoming portion of the implementation in pseduo-merge.ch. Rewrite the existing function, `read_bitmap_1()`, in terms of its more generic counterpart. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pack-bitmap-write.c: write pseudo-merge table

2024-05-24T18:40:42Z

Now that the pack-bitmap writer machinery understands how to select and store pseudo-merge commits, teach it how to write the new optional pseudo-merge .bitmap extension. No readers yet exist for this new extension to the .bitmap format. The following commits will take any preparatory step(s) necessary before then implementing the routines necessary to read this new table. In the meantime, the new `write_pseudo_merges()` function implements writing this new format as described by a previous commit in Documentation/technical/bitmap-format.txt. Writing this table is fairly straightforward and consists of a few sub-components: - a pair of bitmaps for each pseudo-merge (one for the pseudo-merge "parents", and another for the objects reachable from those parents) - for each commit, the offset of either (a) the pseudo-merge it belongs to, or (b) an extended lookup table if it belongs to >1 pseudo-merge groups - if there are any commits belonging to >1 pseudo-merge group, the extended lookup tables (which each consist of the number of pseudo-merge groups a commit appears in, and then that many 4-byte unsigned ) Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

pseudo-merge: implement support for selecting pseudo-merge commits

2024-05-24T18:40:42Z

Teach the new pseudo-merge machinery how to select non-bitmapped commits for inclusion in different pseudo-merge group(s) based on a handful of criteria. Note that the selected pseudo-merge commits aren't actually used or written anywhere yet. This will be done in the following commit. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano