{"thread":{"id":"61956","subject":"[PATCH 0/8] pseudo-merge: avoid empty and non-closed pseudo-merge commits","startedAt":"2024-08-15T17:30:59Z","lastAt":"2024-08-29T19:37:00Z","messageCount":20,"participants":["Taylor Blau","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"501022","messageId":"cover.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":null,"subject":"[PATCH 0/8] pseudo-merge: avoid empty and non-closed pseudo-merge commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:30:56Z","receivedAt":"2024-08-15T17:30:59Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"This series fixes a couple of small issues with pseudo-merge groups,\nwhere it is possible to (a) select pseudo-merges that are not closed\nover reachability with respect to the bitmap's pack or MIDX, and (b)\ngenerate empty pseudo-merge commits.\n\nThe series is structured as follows:\n\n  - The first four commits refactor the pack-bitmap machinery to make\n    the bitmap_writer's packing_data structure available earlier at\n    selection time, and then remove redundant arguments from the rest of\n    the API as a result of that change.\n\n  - The fifth commit makes it so we select pseudo-merges even in small\n    repositories, making it easier to write tests in the remainder of\n    the series.\n\n  - The next two commits demonstrate and fix a case where we would\n    generate empty pseudo-merge commits (see (b) above).\n\n  - The final commit ensures that we do not generate pseudo-merge groups\n    which reach objects not contained in the bitmap's pack or MIDX (see\n    (a) above).\n\nThe bug described in (a) was noticed by Peff, and the remaining seven\ncommits are preparatory, and/or fixing other small issues I noticed\nalong the way while investigating the original impetus for this series.\n\nThanks in advance for your review!\n\nTaylor Blau (8):\n  pack-bitmap: initialize `bitmap_writer_init()` with packing_data\n  pack-bitmap: drop redundant args from\n    `bitmap_writer_build_type_index()`\n  pack-bitmap: drop redundant args from `bitmap_writer_build()`\n  pack-bitmap: drop redundant args from `bitmap_writer_finish()`\n  pack-bitmap-write.c: select pseudo-merges even for small bitmaps\n  t/t5333-pseudo-merge-bitmaps.sh: demonstrate empty pseudo-merge groups\n  pseudo-merge.c: do not generate empty pseudo-merge commits\n  pseudo-merge.c: ensure pseudo-merge groups are closed\n\n builtin/pack-objects.c          |  8 ++---\n midx-write.c                    | 10 +++---\n pack-bitmap-write.c             | 37 +++++++++++-----------\n pack-bitmap.h                   | 11 +++----\n pseudo-merge.c                  | 13 +++++---\n t/t5333-pseudo-merge-bitmaps.sh | 56 +++++++++++++++++++++++++++++++++\n 6 files changed, 96 insertions(+), 39 deletions(-)\n\n\nbase-commit: 406f326d271e0bacecdb00425422c5fa3f314930\n-- \n2.46.0.54.gc9a64b1d2a\n"},{"id":"501023","messageId":"9d322fc5399c453913d08f35eee907b5c909ad6b.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 1/8] pack-bitmap: initialize `bitmap_writer_init()` with packing_data","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:00Z","receivedAt":"2024-08-15T17:31:02Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In order to determine its object order, the pack-bitmap machinery keeps\na 'struct packing_data' corresponding to the pack or pseudo-pack (when\nwriting a MIDX bitmap) being written.\n\nThe to_pack field is provided to the bitmap machinery by callers of\nbitmap_writer_build() and assigned to the bitmap_writer struct at that\npoint.\n\nBut a subsequent commit will want to have access to that data earlier on\nduring commit selection. Prepare for that by adding a 'to_pack' argument\nto 'bitmap_writer_init()', and initializing the field during that\nfunction.\n\nSubsequent commits will clean up other functions which take\nnow-redundant arguments (like nr_objects, which is equivalent to\npdata->objects_nr, or pdata itself).\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/pack-objects.c | 2 +-\n midx-write.c           | 2 +-\n pack-bitmap-write.c    | 4 +++-\n pack-bitmap.h          | 3 ++-\n 4 files changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f395488971..0ad533c045 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1342,7 +1342,7 @@ static void write_pack_file(void)\n \n \t\t\tif (write_bitmap_index) {\n \t\t\t\tbitmap_writer_init(&bitmap_writer,\n-\t\t\t\t\t\t   the_repository);\n+\t\t\t\t\t\t   the_repository, &to_pack);\n \t\t\t\tbitmap_writer_set_checksum(&bitmap_writer, hash);\n \t\t\t\tbitmap_writer_build_type_index(&bitmap_writer,\n \t\t\t\t\t&to_pack, written_list, nr_written);\ndiff --git a/midx-write.c b/midx-write.c\nindex a77ee73c68..62f507eb72 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -825,7 +825,7 @@ static int write_midx_bitmap(const char *midx_name,\n \tfor (i = 0; i < pdata->nr_objects; i++)\n \t\tindex[i] = &pdata->objects[i].idx;\n \n-\tbitmap_writer_init(&writer, the_repository);\n+\tbitmap_writer_init(&writer, the_repository, pdata);\n \tbitmap_writer_show_progress(&writer, flags & MIDX_PROGRESS);\n \tbitmap_writer_build_type_index(&writer, pdata, index,\n \t\t\t\t       pdata->nr_objects);\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex bf96c80898..4a7d2d1370 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -41,13 +41,15 @@ static inline int bitmap_writer_nr_selected_commits(struct bitmap_writer *writer\n \treturn writer->selected_nr - writer->pseudo_merges_nr;\n }\n \n-void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r)\n+void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r,\n+\t\t\tstruct packing_data *pdata)\n {\n \tmemset(writer, 0, sizeof(struct bitmap_writer));\n \tif (writer->bitmaps)\n \t\tBUG(\"bitmap writer already initialized\");\n \twriter->bitmaps = kh_init_oid_map();\n \twriter->pseudo_merge_commits = kh_init_oid_map();\n+\twriter->to_pack = pdata;\n \n \tstring_list_init_dup(&writer->pseudo_merge_groups);\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 1171e6d989..ab20d6a0b6 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -123,7 +123,8 @@ struct bitmap_writer {\n \tunsigned char pack_checksum[GIT_MAX_RAWSZ];\n };\n \n-void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r);\n+void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r,\n+\t\t\tstruct packing_data *pdata);\n void bitmap_writer_show_progress(struct bitmap_writer *writer, int show);\n void bitmap_writer_set_checksum(struct bitmap_writer *writer,\n \t\t\t\tconst unsigned char *sha1);\n-- \n2.46.0.54.gc9a64b1d2a\n\n"},{"id":"501024","messageId":"238ca46998e936fb5d57467aeec5d9a0b187341e.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 2/8] pack-bitmap: drop redundant args from `bitmap_writer_build_type_index()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:03Z","receivedAt":"2024-08-15T17:31:05Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The previous commit ensures that the bitmap_writer's \"to_pack\" field is\ninitialized early on, so the \"to_pack\" and \"index_nr\" arguments to\n`bitmap_writer_build_type_index()` are redundant.\n\nDrop them and adjust the callers accordingly.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/pack-objects.c |  2 +-\n midx-write.c           |  3 +--\n pack-bitmap-write.c    | 12 +++++-------\n pack-bitmap.h          |  4 +---\n 4 files changed, 8 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0ad533c045..c08a62718d 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1345,7 +1345,7 @@ static void write_pack_file(void)\n \t\t\t\t\t\t   the_repository, &to_pack);\n \t\t\t\tbitmap_writer_set_checksum(&bitmap_writer, hash);\n \t\t\t\tbitmap_writer_build_type_index(&bitmap_writer,\n-\t\t\t\t\t&to_pack, written_list, nr_written);\n+\t\t\t\t\t\t\t       written_list);\n \t\t\t}\n \n \t\t\tif (cruft)\ndiff --git a/midx-write.c b/midx-write.c\nindex 62f507eb72..b3015af07f 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -827,8 +827,7 @@ static int write_midx_bitmap(const char *midx_name,\n \n \tbitmap_writer_init(&writer, the_repository, pdata);\n \tbitmap_writer_show_progress(&writer, flags & MIDX_PROGRESS);\n-\tbitmap_writer_build_type_index(&writer, pdata, index,\n-\t\t\t\t       pdata->nr_objects);\n+\tbitmap_writer_build_type_index(&writer, index);\n \n \t/*\n \t * bitmap_writer_finish expects objects in lex order, but pack_order\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 4a7d2d1370..34cdf5f150 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -101,9 +101,7 @@ void bitmap_writer_show_progress(struct bitmap_writer *writer, int show)\n  * Build the initial type index for the packfile or multi-pack-index\n  */\n void bitmap_writer_build_type_index(struct bitmap_writer *writer,\n-\t\t\t\t    struct packing_data *to_pack,\n-\t\t\t\t    struct pack_idx_entry **index,\n-\t\t\t\t    uint32_t index_nr)\n+\t\t\t\t    struct pack_idx_entry **index)\n {\n \tuint32_t i;\n \n@@ -111,13 +109,13 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer,\n \twriter->trees = ewah_new();\n \twriter->blobs = ewah_new();\n \twriter->tags = ewah_new();\n-\tALLOC_ARRAY(to_pack->in_pack_pos, to_pack->nr_objects);\n+\tALLOC_ARRAY(writer->to_pack->in_pack_pos, writer->to_pack->nr_objects);\n \n-\tfor (i = 0; i < index_nr; ++i) {\n+\tfor (i = 0; i < writer->to_pack->nr_objects; ++i) {\n \t\tstruct object_entry *entry = (struct object_entry *)index[i];\n \t\tenum object_type real_type;\n \n-\t\toe_set_in_pack_pos(to_pack, entry, i);\n+\t\toe_set_in_pack_pos(writer->to_pack, entry, i);\n \n \t\tswitch (oe_type(entry)) {\n \t\tcase OBJ_COMMIT:\n@@ -128,7 +126,7 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer,\n \t\t\tbreak;\n \n \t\tdefault:\n-\t\t\treal_type = oid_object_info(to_pack->repo,\n+\t\t\treal_type = oid_object_info(writer->to_pack->repo,\n \t\t\t\t\t\t    &entry->idx.oid, NULL);\n \t\t\tbreak;\n \t\t}\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex ab20d6a0b6..d2529abadc 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -129,9 +129,7 @@ void bitmap_writer_show_progress(struct bitmap_writer *writer, int show);\n void bitmap_writer_set_checksum(struct bitmap_writer *writer,\n \t\t\t\tconst unsigned char *sha1);\n void bitmap_writer_build_type_index(struct bitmap_writer *writer,\n-\t\t\t\t    struct packing_data *to_pack,\n-\t\t\t\t    struct pack_idx_entry **index,\n-\t\t\t\t    uint32_t index_nr);\n+\t\t\t\t    struct pack_idx_entry **index);\n int bitmap_writer_has_bitmapped_object_id(struct bitmap_writer *writer,\n \t\t\t\t\t  const struct object_id *oid);\n void bitmap_writer_push_commit(struct bitmap_writer *writer,\n-- \n2.46.0.54.gc9a64b1d2a\n\n"},{"id":"501025","messageId":"5e198489fa807c551c36b391c8e8ca8efb0c52b9.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 3/8] pack-bitmap: drop redundant args from `bitmap_writer_build()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:06Z","receivedAt":"2024-08-15T17:31:08Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In a similar fashion as the previous commit, drop a redundant argument\nfrom the `bitmap_writer_build()` function.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/pack-objects.c | 2 +-\n midx-write.c           | 2 +-\n pack-bitmap-write.c    | 9 +++------\n pack-bitmap.h          | 3 +--\n 4 files changed, 6 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c08a62718d..97090433a1 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1367,7 +1367,7 @@ static void write_pack_file(void)\n \t\t\t\tbitmap_writer_select_commits(&bitmap_writer,\n \t\t\t\t\t\t\t     indexed_commits,\n \t\t\t\t\t\t\t     indexed_commits_nr);\n-\t\t\t\tif (bitmap_writer_build(&bitmap_writer, &to_pack) < 0)\n+\t\t\t\tif (bitmap_writer_build(&bitmap_writer) < 0)\n \t\t\t\t\tdie(_(\"failed to write bitmap index\"));\n \t\t\t\tbitmap_writer_finish(&bitmap_writer,\n \t\t\t\t\t\t     written_list, nr_written,\ndiff --git a/midx-write.c b/midx-write.c\nindex b3015af07f..1ccdf0df30 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -846,7 +846,7 @@ static int write_midx_bitmap(const char *midx_name,\n \t\tindex[pack_order[i]] = &pdata->objects[i].idx;\n \n \tbitmap_writer_select_commits(&writer, commits, commits_nr);\n-\tret = bitmap_writer_build(&writer, pdata);\n+\tret = bitmap_writer_build(&writer);\n \tif (ret < 0)\n \t\tgoto cleanup;\n \ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 34cdf5f150..8d7437955d 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -569,8 +569,7 @@ static void store_selected(struct bitmap_writer *writer,\n \tkh_value(writer->bitmaps, hash_pos) = stored;\n }\n \n-int bitmap_writer_build(struct bitmap_writer *writer,\n-\t\t\tstruct packing_data *to_pack)\n+int bitmap_writer_build(struct bitmap_writer *writer)\n {\n \tstruct bitmap_builder bb;\n \tsize_t i;\n@@ -581,17 +580,15 @@ int bitmap_writer_build(struct bitmap_writer *writer,\n \tuint32_t *mapping;\n \tint closed = 1; /* until proven otherwise */\n \n-\twriter->to_pack = to_pack;\n-\n \tif (writer->show_progress)\n \t\twriter->progress = start_progress(\"Building bitmaps\",\n \t\t\t\t\t\t  writer->selected_nr);\n \ttrace2_region_enter(\"pack-bitmap-write\", \"building_bitmaps_total\",\n \t\t\t    the_repository);\n \n-\told_bitmap = prepare_bitmap_git(to_pack->repo);\n+\told_bitmap = prepare_bitmap_git(writer->to_pack->repo);\n \tif (old_bitmap)\n-\t\tmapping = create_bitmap_mapping(old_bitmap, to_pack);\n+\t\tmapping = create_bitmap_mapping(old_bitmap, writer->to_pack);\n \telse\n \t\tmapping = NULL;\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex d2529abadc..0c5b83e954 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -146,8 +146,7 @@ struct ewah_bitmap *pseudo_merge_bitmap_for_commit(struct bitmap_index *bitmap_g\n void bitmap_writer_select_commits(struct bitmap_writer *writer,\n \t\t\t\t  struct commit **indexed_commits,\n \t\t\t\t  unsigned int indexed_commits_nr);\n-int bitmap_writer_build(struct bitmap_writer *writer,\n-\t\t\tstruct packing_data *to_pack);\n+int bitmap_writer_build(struct bitmap_writer *writer);\n void bitmap_writer_finish(struct bitmap_writer *writer,\n \t\t\t  struct pack_idx_entry **index,\n \t\t\t  uint32_t index_nr,\n-- \n2.46.0.54.gc9a64b1d2a\n\n"},{"id":"501026","messageId":"819a0765f380e69d2ae53304214d77dcdbb7b91c.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 4/8] pack-bitmap: drop redundant args from `bitmap_writer_finish()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:08Z","receivedAt":"2024-08-15T17:31:11Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In a similar fashion as the previous commit, drop a redundant argument\nfrom the `bitmap_writer_finish()` function.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n builtin/pack-objects.c | 2 +-\n midx-write.c           | 3 +--\n pack-bitmap-write.c    | 8 ++++----\n pack-bitmap.h          | 1 -\n 4 files changed, 6 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 97090433a1..e23c4950ed 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1370,7 +1370,7 @@ static void write_pack_file(void)\n \t\t\t\tif (bitmap_writer_build(&bitmap_writer) < 0)\n \t\t\t\t\tdie(_(\"failed to write bitmap index\"));\n \t\t\t\tbitmap_writer_finish(&bitmap_writer,\n-\t\t\t\t\t\t     written_list, nr_written,\n+\t\t\t\t\t\t     written_list,\n \t\t\t\t\t\t     tmpname.buf, write_bitmap_options);\n \t\t\t\tbitmap_writer_free(&bitmap_writer);\n \t\t\t\twrite_bitmap_index = 0;\ndiff --git a/midx-write.c b/midx-write.c\nindex 1ccdf0df30..d2d13447af 100644\n--- a/midx-write.c\n+++ b/midx-write.c\n@@ -851,8 +851,7 @@ static int write_midx_bitmap(const char *midx_name,\n \t\tgoto cleanup;\n \n \tbitmap_writer_set_checksum(&writer, midx_hash);\n-\tbitmap_writer_finish(&writer, index, pdata->nr_objects, bitmap_name,\n-\t\t\t     options);\n+\tbitmap_writer_finish(&writer, index, bitmap_name, options);\n \n cleanup:\n \tfree(index);\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 8d7437955d..346fb29513 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -998,7 +998,6 @@ void bitmap_writer_set_checksum(struct bitmap_writer *writer,\n \n void bitmap_writer_finish(struct bitmap_writer *writer,\n \t\t\t  struct pack_idx_entry **index,\n-\t\t\t  uint32_t index_nr,\n \t\t\t  const char *filename,\n \t\t\t  uint16_t options)\n {\n@@ -1031,12 +1030,13 @@ void bitmap_writer_finish(struct bitmap_writer *writer,\n \tdump_bitmap(f, writer->tags);\n \n \tif (options & BITMAP_OPT_LOOKUP_TABLE)\n-\t\tCALLOC_ARRAY(offsets, index_nr);\n+\t\tCALLOC_ARRAY(offsets, writer->to_pack->nr_objects);\n \n \tfor (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {\n \t\tstruct bitmapped_commit *stored = &writer->selected[i];\n \t\tint commit_pos = oid_pos(&stored->commit->object.oid, index,\n-\t\t\t\t\t index_nr, oid_access);\n+\t\t\t\t\t writer->to_pack->nr_objects,\n+\t\t\t\t\t oid_access);\n \n \t\tif (commit_pos < 0)\n \t\t\tBUG(_(\"trying to write commit not in index\"));\n@@ -1052,7 +1052,7 @@ void bitmap_writer_finish(struct bitmap_writer *writer,\n \t\twrite_lookup_table(writer, f, offsets);\n \n \tif (options & BITMAP_OPT_HASH_CACHE)\n-\t\twrite_hash_cache(f, index, index_nr);\n+\t\twrite_hash_cache(f, index, writer->to_pack->nr_objects);\n \n \tfinalize_hashfile(f, NULL, FSYNC_COMPONENT_PACK_METADATA,\n \t\t\t  CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 0c5b83e954..ff0fd815b8 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -149,7 +149,6 @@ void bitmap_writer_select_commits(struct bitmap_writer *writer,\n int bitmap_writer_build(struct bitmap_writer *writer);\n void bitmap_writer_finish(struct bitmap_writer *writer,\n \t\t\t  struct pack_idx_entry **index,\n-\t\t\t  uint32_t index_nr,\n \t\t\t  const char *filename,\n \t\t\t  uint16_t options);\n void bitmap_writer_free(struct bitmap_writer *writer);\n-- \n2.46.0.54.gc9a64b1d2a\n\n"},{"id":"501027","messageId":"0fea7803d86ca17451af408e1bf93c32690edc44.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 5/8] pack-bitmap-write.c: select pseudo-merges even for small bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:12Z","receivedAt":"2024-08-15T17:31:14Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Ordinarily, the pack-bitmap machinery will select some subset of\nreachable commits to receive bitmaps. But when there are fewer than 100\ncommits indexed in the first place, they will all receive bitmaps as a\nspecial case.\n\nWhen this happens, pseudo-merges are not generated, making it impossible\nto test pseudo-merge corner cases with fewer than 100 commits.\n\nSelect pseudo-merges even for bitmaps with fewer than 100 commits to\nmake such testing easier. In practice, this should not make a difference\nto non-testing bitmaps, as they are unlikely to be used when a\nrepository has so few commits to begin with.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n pack-bitmap-write.c | 4 ++++\n 1 file changed, 4 insertions(+)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 346fb29513..923f793cec 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -694,6 +694,10 @@ void bitmap_writer_select_commits(struct bitmap_writer *writer,\n \tif (indexed_commits_nr < 100) {\n \t\tfor (i = 0; i < indexed_commits_nr; ++i)\n \t\t\tbitmap_writer_push_commit(writer, indexed_commits[i], 0);\n+\n+\t\tselect_pseudo_merges(writer, indexed_commits,\n+\t\t\t\t     indexed_commits_nr);\n+\n \t\treturn;\n \t}\n \n-- \n2.46.0.54.gc9a64b1d2a\n\n"},{"id":"501028","messageId":"228553e412fc3020a6f24eea601c47a08d70a2bf.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 6/8] t/t5333-pseudo-merge-bitmaps.sh: demonstrate empty pseudo-merge groups","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:14Z","receivedAt":"2024-08-15T17:31:17Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Demonstrate that it is possible to generate empty pseudo-merge commits\nin certain cases.\n\nIn the below instance, we generate one non-empty pseudo-merge\n(containing commit \"base\"), and one empty pseudo-merge group\n(corresponding to the unstable commits within that group).\n\n(In my testing, the pseudo-merge machinery seems to handle empty groups\njust fine, but generating them is pointless as they carry no\ninformation.)\n\nThis commit (introducing a deliberate \"test_expect_failure\") is split\nout from the actual fix (which will appear in the following commit) to\ndemonstrate that the failure is correctly induced.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n t/t5333-pseudo-merge-bitmaps.sh | 20 ++++++++++++++++++++\n 1 file changed, 20 insertions(+)\n\ndiff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh\nindex f052f395a7..0288691340 100755\n--- a/t/t5333-pseudo-merge-bitmaps.sh\n+++ b/t/t5333-pseudo-merge-bitmaps.sh\n@@ -390,4 +390,24 @@ test_expect_success 'pseudo-merge reuse' '\n \t)\n '\n \n+test_expect_failure 'empty pseudo-merge group' '\n+\tgit init pseudo-merge-empty-group &&\n+\t(\n+\t\tcd pseudo-merge-empty-group &&\n+\n+\t\t# Ensure that a pseudo-merge group with no unstable\n+\t\t# commits does not generate an empty pseudo-merge\n+\t\t# bitmap.\n+\t\tgit config bitmapPseudoMerge.empty.pattern refs/ &&\n+\n+\t\ttest_commit base &&\n+\t\tgit repack -adb &&\n+\n+\t\ttest-tool bitmap dump-pseudo-merges >merges &&\n+\t\ttest_line_count = 1 merges &&\n+\n+\t\ttest 0 -eq \"$(grep -c commits=0 <merges)\"\n+\t)\n+'\n+\n test_done\n-- \n2.46.0.54.gc9a64b1d2a\n\n"},{"id":"501029","messageId":"c7e0ee0712034f654f018361f52c09b1043a8441.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 7/8] pseudo-merge.c: do not generate empty pseudo-merge commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:17Z","receivedAt":"2024-08-15T17:31:20Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The previous commit demonstrated it is possible to generate empty\npseudo-merge commits, which is not useful as such pseudo-merges carry no\ninformation.\n\nEnsure that we only generate non-empty groups by not pushing a new\ncommit onto the bitmap_writer when that commit has no parents.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n pseudo-merge.c                  | 11 +++++++----\n t/t5333-pseudo-merge-bitmaps.sh |  2 +-\n 2 files changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/pseudo-merge.c b/pseudo-merge.c\nindex f0fde13c47..6422be979c 100644\n--- a/pseudo-merge.c\n+++ b/pseudo-merge.c\n@@ -357,8 +357,10 @@ static void select_pseudo_merges_1(struct bitmap_writer *writer,\n \t\t\tp = commit_list_append(c, p);\n \t\t} while (j % group->stable_size);\n \n-\t\tbitmap_writer_push_commit(writer, merge, 1);\n-\t\twriter->pseudo_merges_nr++;\n+\t\tif (merge->parents) {\n+\t\t\tbitmap_writer_push_commit(writer, merge, 1);\n+\t\t\twriter->pseudo_merges_nr++;\n+\t\t}\n \t}\n \n \t/* make up to group->max_merges pseudo merges for unstable commits */\n@@ -398,8 +400,9 @@ static void select_pseudo_merges_1(struct bitmap_writer *writer,\n \t\t\tp = commit_list_append(c, p);\n \t\t}\n \n-\t\tbitmap_writer_push_commit(writer, merge, 1);\n-\t\twriter->pseudo_merges_nr++;\n+\t\tif (merge->parents) {\n+\t\t\tbitmap_writer_push_commit(writer, merge, 1);\n+\t\t\twriter->pseudo_merges_nr++; }\n \t\tif (end >= matches->unstable_nr)\n \t\t\tbreak;\n \t}\ndiff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh\nindex 0288691340..aa1a7d26f1 100755\n--- a/t/t5333-pseudo-merge-bitmaps.sh\n+++ b/t/t5333-pseudo-merge-bitmaps.sh\n@@ -390,7 +390,7 @@ test_expect_success 'pseudo-merge reuse' '\n \t)\n '\n \n-test_expect_failure 'empty pseudo-merge group' '\n+test_expect_success 'empty pseudo-merge group' '\n \tgit init pseudo-merge-empty-group &&\n \t(\n \t\tcd pseudo-merge-empty-group &&\n-- \n2.46.0.54.gc9a64b1d2a\n\n"},{"id":"501030","messageId":"c9a64b1d2a9d6b3fe1f5fb0a7303e043114fcd8f.1723743050.git.me@ttaylorr.com","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"[PATCH 8/8] pseudo-merge.c: ensure pseudo-merge groups are closed","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-15T17:31:20Z","receivedAt":"2024-08-15T17:31:23Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When generating pseudo-merge bitmaps, it's possible that concurrent\nreference updates may reveal some pseudo-merge candidates which reach\nobjects that are not contained in the bitmap's pack or pseudo-pack\norder (in the case of MIDX bitmaps).\n\nThe latter case is relatively easy to demonstrate: if we generate a MIDX\nbitmap with only half of the repository packed, then the unpacked\ncontents are not part of the MIDX's object order.\n\nIf we happen to select one or more commit(s) from the unpacked portion\nof the repository for inclusion in a pseudo-merge, we'll get the\nfollowing message when trying to generate its bitmap:\n\n    $ git multi-pack-index write --bitmap\n    [...]\n    Selecting pseudo-merge commits: 100% (1/1), done.\n    warning: Failed to write bitmap index. Packfile doesn't have full closure (object ... is missing)\n    Building bitmaps:  50% (1/2), done.\n    error: could not write multi-pack bitmap\n\n, and the attempted bitmap write will fail, leaving the repository\nwithout a current bitmap.\n\nRectify this by ensuring that the commits which are pseudo-merge\ncandidates can only be so if they appear somewhere in the packing order.\n\nThis is sufficient, since we know that the original packing order is\nclosed under reachability, so if a commit appears in that list as a\npotential pseudo-merge candidate, we know that everything reachable from\nit also appears in the list (and thus the candidate is a good one).\n\nNoticed-by: Jeff King <peff@peff.net>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n pseudo-merge.c                  |  2 ++\n t/t5333-pseudo-merge-bitmaps.sh | 36 +++++++++++++++++++++++++++++++++\n 2 files changed, 38 insertions(+)\n\ndiff --git a/pseudo-merge.c b/pseudo-merge.c\nindex 6422be979c..7ec9d4c51c 100644\n--- a/pseudo-merge.c\n+++ b/pseudo-merge.c\n@@ -217,6 +217,8 @@ static int find_pseudo_merge_group_for_ref(const char *refname,\n \tc = lookup_commit(the_repository, oid);\n \tif (!c)\n \t\treturn 0;\n+\tif (!packlist_find(writer->to_pack, oid))\n+\t\treturn 0;\n \n \thas_bitmap = bitmap_writer_has_bitmapped_object_id(writer, oid);\n \ndiff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh\nindex aa1a7d26f1..1dd6284756 100755\n--- a/t/t5333-pseudo-merge-bitmaps.sh\n+++ b/t/t5333-pseudo-merge-bitmaps.sh\n@@ -410,4 +410,40 @@ test_expect_success 'empty pseudo-merge group' '\n \t)\n '\n \n+test_expect_success 'pseudo-merge closure' '\n+\tgit init pseudo-merge-closure &&\n+\t(\n+\t\tcd pseudo-merge-closure &&\n+\n+\t\ttest_commit A &&\n+\t\tgit repack -d &&\n+\n+\t\ttest_commit B &&\n+\n+\t\t# Note that the contents of A is packed, but B is not. A\n+\t\t# (and the objects reachable from it) are thus visible\n+\t\t# to the MIDX, but the same is not true for B and its\n+\t\t# objects.\n+\t\t#\n+\t\t# Ensure that we do not attempt to create a pseudo-merge\n+\t\t# for B, depsite it matching the below pseudo-merge\n+\t\t# group pattern, as doing so would result in a failure\n+\t\t# to write a non-closed bitmap.\n+\t\tgit config bitmapPseudoMerge.test.pattern refs/ &&\n+\t\tgit config bitmapPseudoMerge.test.threshold now &&\n+\n+\t\tgit multi-pack-index write --bitmap &&\n+\n+\t\ttest-tool bitmap dump-pseudo-merges >pseudo-merges &&\n+\t\ttest_line_count = 1 pseudo-merges &&\n+\n+\t\tgit rev-parse A >expect &&\n+\n+\t\ttest-tool bitmap list-commits >actual &&\n+\t\ttest_cmp expect actual &&\n+\t\ttest-tool bitmap dump-pseudo-merge-commits 0 >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n test_done\n-- \n2.46.0.54.gc9a64b1d2a\n"},{"id":"501216","messageId":"20240817103155.GA551779@coredump.intra.peff.net","threadId":"61956","inReplyTo":"9d322fc5399c453913d08f35eee907b5c909ad6b.1723743050.git.me@ttaylorr.com","subject":"Re: [PATCH 1/8] pack-bitmap: initialize `bitmap_writer_init()` with packing_data","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-08-17T10:31:55Z","receivedAt":"2024-08-17T10:31:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 15, 2024 at 01:31:00PM -0400, Taylor Blau wrote:\n\n> In order to determine its object order, the pack-bitmap machinery keeps\n> a 'struct packing_data' corresponding to the pack or pseudo-pack (when\n> writing a MIDX bitmap) being written.\n> \n> The to_pack field is provided to the bitmap machinery by callers of\n> bitmap_writer_build() and assigned to the bitmap_writer struct at that\n> point.\n> \n> But a subsequent commit will want to have access to that data earlier on\n> during commit selection. Prepare for that by adding a 'to_pack' argument\n> to 'bitmap_writer_init()', and initializing the field during that\n> function.\n> \n> Subsequent commits will clean up other functions which take\n> now-redundant arguments (like nr_objects, which is equivalent to\n> pdata->objects_nr, or pdata itself).\n\nThis (and the next few follow-on commits) seem like a good change to me.\nIt simplifies many of the function calls, and I think it expresses the\ndomain logic in the API: there is a single set of objects being mapped\nto bits, and many parts of the process will rely on it.\n\nEven the midx code, which is not generating a pack, uses a \"fake\"\npacking_data as the way to express that (because inherently the bit\nordering is all coming from the pack-index nature). If we likewise ever\nwrote code to generate bitmaps from an existing pack, it would probably\nuse packing_data, too. :)\n\n-Peff\n"},{"id":"501217","messageId":"20240817103401.GB551779@coredump.intra.peff.net","threadId":"61956","inReplyTo":"0fea7803d86ca17451af408e1bf93c32690edc44.1723743050.git.me@ttaylorr.com","subject":"Re: [PATCH 5/8] pack-bitmap-write.c: select pseudo-merges even for small bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-08-17T10:34:01Z","receivedAt":"2024-08-17T10:34:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 15, 2024 at 01:31:12PM -0400, Taylor Blau wrote:\n\n> Ordinarily, the pack-bitmap machinery will select some subset of\n> reachable commits to receive bitmaps. But when there are fewer than 100\n> commits indexed in the first place, they will all receive bitmaps as a\n> special case.\n> \n> When this happens, pseudo-merges are not generated, making it impossible\n> to test pseudo-merge corner cases with fewer than 100 commits.\n> \n> Select pseudo-merges even for bitmaps with fewer than 100 commits to\n> make such testing easier. In practice, this should not make a difference\n> to non-testing bitmaps, as they are unlikely to be used when a\n> repository has so few commits to begin with.\n\nI think you could argue that if there are fewer than 100 commits in the\nhistory that pseudo-merge bitmaps are overkill, so it does not matter\nmuch either way. But I think being consistent with our behavior (i.e.,\ngenerating them if asked) is important for testing and debugging.\n\n> diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\n> index 346fb29513..923f793cec 100644\n> --- a/pack-bitmap-write.c\n> +++ b/pack-bitmap-write.c\n> @@ -694,6 +694,10 @@ void bitmap_writer_select_commits(struct bitmap_writer *writer,\n>  \tif (indexed_commits_nr < 100) {\n>  \t\tfor (i = 0; i < indexed_commits_nr; ++i)\n>  \t\t\tbitmap_writer_push_commit(writer, indexed_commits[i], 0);\n> +\n> +\t\tselect_pseudo_merges(writer, indexed_commits,\n> +\t\t\t\t     indexed_commits_nr);\n> +\n\nI of course just posted a series which drops the latter two arguments\nfrom this function. It's a semantic conflict, not a textual one, so\nwe'll have to fix it up when the two are merged (but the compiler will\neasily notice to remind us).\n\n-Peff\n"},{"id":"501218","messageId":"20240817103822.GC551779@coredump.intra.peff.net","threadId":"61956","inReplyTo":"c7e0ee0712034f654f018361f52c09b1043a8441.1723743050.git.me@ttaylorr.com","subject":"Re: [PATCH 7/8] pseudo-merge.c: do not generate empty pseudo-merge commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-08-17T10:38:22Z","receivedAt":"2024-08-17T10:38:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 15, 2024 at 01:31:17PM -0400, Taylor Blau wrote:\n\n> The previous commit demonstrated it is possible to generate empty\n> pseudo-merge commits, which is not useful as such pseudo-merges carry no\n> information.\n> \n> Ensure that we only generate non-empty groups by not pushing a new\n> commit onto the bitmap_writer when that commit has no parents.\n\nMakes sense, and the patch seems pretty straight-forward.\n\nIt's a little tempting to suggest that we keep some way of writing\nthese, so that we can exercise the reading side in the tests (we\n_shouldn't_ see these if we're not writing them, but as an on-disk\nformat, we may see examples from other sources). But it is probably not\nworth the complexity. If we really want to test them, we can probably\ngenerate a single example by hand (and we can probably even wait on that\nuntil we see something in the wild that makes it worth doing).\n\n-Peff\n"},{"id":"501219","messageId":"20240817104341.GD551779@coredump.intra.peff.net","threadId":"61956","inReplyTo":"c9a64b1d2a9d6b3fe1f5fb0a7303e043114fcd8f.1723743050.git.me@ttaylorr.com","subject":"Re: [PATCH 8/8] pseudo-merge.c: ensure pseudo-merge groups are closed","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-08-17T10:43:41Z","receivedAt":"2024-08-17T10:43:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 15, 2024 at 01:31:20PM -0400, Taylor Blau wrote:\n\n> Rectify this by ensuring that the commits which are pseudo-merge\n> candidates can only be so if they appear somewhere in the packing order.\n> \n> This is sufficient, since we know that the original packing order is\n> closed under reachability, so if a commit appears in that list as a\n> potential pseudo-merge candidate, we know that everything reachable from\n> it also appears in the list (and thus the candidate is a good one).\n\nRight, good explanation.\n\n> diff --git a/pseudo-merge.c b/pseudo-merge.c\n> index 6422be979c..7ec9d4c51c 100644\n> --- a/pseudo-merge.c\n> +++ b/pseudo-merge.c\n> @@ -217,6 +217,8 @@ static int find_pseudo_merge_group_for_ref(const char *refname,\n>  \tc = lookup_commit(the_repository, oid);\n>  \tif (!c)\n>  \t\treturn 0;\n> +\tif (!packlist_find(writer->to_pack, oid))\n> +\t\treturn 0;\n>  \n>  \thas_bitmap = bitmap_writer_has_bitmapped_object_id(writer, oid);\n>  \n\nAnd the patch looks good. I wondered about checking the packlist before\ncalling lookup_commit(), but the latter is really not very expensive (it\nis not reading the object, but just creating a struct).\n\n> +test_expect_success 'pseudo-merge closure' '\n> +\tgit init pseudo-merge-closure &&\n> +\t(\n> +\t\tcd pseudo-merge-closure &&\n> +\n> +\t\ttest_commit A &&\n> +\t\tgit repack -d &&\n> +\n> +\t\ttest_commit B &&\n> +\n> +\t\t# Note that the contents of A is packed, but B is not. A\n> +\t\t# (and the objects reachable from it) are thus visible\n> +\t\t# to the MIDX, but the same is not true for B and its\n> +\t\t# objects.\n> +\t\t#\n> +\t\t# Ensure that we do not attempt to create a pseudo-merge\n> +\t\t# for B, depsite it matching the below pseudo-merge\n> +\t\t# group pattern, as doing so would result in a failure\n> +\t\t# to write a non-closed bitmap.\n> +\t\tgit config bitmapPseudoMerge.test.pattern refs/ &&\n> +\t\tgit config bitmapPseudoMerge.test.threshold now &&\n> +\n> +\t\tgit multi-pack-index write --bitmap &&\n\nOK, clever. In the real world, I think this would happen racily, because\nyou'd usually suck up all of the loose objects into a pack to feed into\nthe midx. And the problem is new objects (whether packed or not) that\nare referenced after that step.\n\nBut here we just skip that step and generate the midx directly, which\nlets us do it deterministically.\n\n-Peff\n"},{"id":"501220","messageId":"20240817104412.GE551779@coredump.intra.peff.net","threadId":"61956","inReplyTo":"cover.1723743050.git.me@ttaylorr.com","subject":"Re: [PATCH 0/8] pseudo-merge: avoid empty and non-closed pseudo-merge commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-08-17T10:44:12Z","receivedAt":"2024-08-17T10:44:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 15, 2024 at 01:30:56PM -0400, Taylor Blau wrote:\n\n> This series fixes a couple of small issues with pseudo-merge groups,\n> where it is possible to (a) select pseudo-merges that are not closed\n> over reachability with respect to the bitmap's pack or MIDX, and (b)\n> generate empty pseudo-merge commits.\n\nThanks, the whole series looks good to me (I left some comments, but it\nis all just walking through my thought process).\n\n-Peff\n"},{"id":"501227","messageId":"xmqq8qwvhzja.fsf@gitster.g","threadId":"61956","inReplyTo":"20240817103401.GB551779@coredump.intra.peff.net","subject":"Re: [PATCH 5/8] pack-bitmap-write.c: select pseudo-merges even for small bitmaps","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-08-17T16:42:01Z","receivedAt":"2024-08-17T16:42:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>> Select pseudo-merges even for bitmaps with fewer than 100 commits to\n>> make such testing easier. In practice, this should not make a difference\n>> to non-testing bitmaps, as they are unlikely to be used when a\n>> repository has so few commits to begin with.\n>\n> I think you could argue that if there are fewer than 100 commits in the\n> history that pseudo-merge bitmaps are overkill, so it does not matter\n> much either way. But I think being consistent with our behavior (i.e.,\n> generating them if asked) is important for testing and debugging.\n\nOK.  I had an opposite reaction to this change, i.e. \"eh, are we\nlifting the safety that protected the users from asking for a\nsuboptimal way to pack, only to make it easier to write this test?\",\nbut I do buy \"the user tells us to do the suboptimal thing, we do\nthat thing.\"\n"},{"id":"501855","messageId":"ZtDFRYQRLQoe+CHS@nand.local","threadId":"61956","inReplyTo":"20240817103155.GA551779@coredump.intra.peff.net","subject":"Re: [PATCH 1/8] pack-bitmap: initialize `bitmap_writer_init()` with packing_data","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-29T19:00:21Z","receivedAt":"2024-08-29T19:00:23Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Aug 17, 2024 at 06:31:55AM -0400, Jeff King wrote:\n> On Thu, Aug 15, 2024 at 01:31:00PM -0400, Taylor Blau wrote:\n>\n> > In order to determine its object order, the pack-bitmap machinery keeps\n> > a 'struct packing_data' corresponding to the pack or pseudo-pack (when\n> > writing a MIDX bitmap) being written.\n> >\n> > The to_pack field is provided to the bitmap machinery by callers of\n> > bitmap_writer_build() and assigned to the bitmap_writer struct at that\n> > point.\n> >\n> > But a subsequent commit will want to have access to that data earlier on\n> > during commit selection. Prepare for that by adding a 'to_pack' argument\n> > to 'bitmap_writer_init()', and initializing the field during that\n> > function.\n> >\n> > Subsequent commits will clean up other functions which take\n> > now-redundant arguments (like nr_objects, which is equivalent to\n> > pdata->objects_nr, or pdata itself).\n>\n> This (and the next few follow-on commits) seem like a good change to me.\n> It simplifies many of the function calls, and I think it expresses the\n> domain logic in the API: there is a single set of objects being mapped\n> to bits, and many parts of the process will rely on it.\n\nThanks. Yeah, it was a little surprising to me that it wasn't already\nthis way, especially having worked in this area for so long. I suspect\nit grew this way organically over time (though haven't actually gone\nspelunking through the history to confirm).\n\n> Even the midx code, which is not generating a pack, uses a \"fake\"\n> packing_data as the way to express that (because inherently the bit\n> ordering is all coming from the pack-index nature). If we likewise ever\n> wrote code to generate bitmaps from an existing pack, it would probably\n> use packing_data, too. :)\n\nI agree for the most part, though there is a lot of weight in\npacking_data that would be nice to not have to carry around. I know\nwithin GitHub's infrastructure we sometimes OOM kill invocations of \"git\nmulti-pack-index write --bitmap\" because of the memory overhead (a lot\nof which is dominated by the actual traversal and bitmap generation, but\na lot that comes from just the per-object overhead).\n\nI've thought about alternative structures that might be a little more\nmemory efficient, but it's never gotten to the top of my list.\n\nThanks,\nTaylor\n"},{"id":"501856","messageId":"ZtDFkO4gFz7hC0Iw@nand.local","threadId":"61956","inReplyTo":"20240817103401.GB551779@coredump.intra.peff.net","subject":"Re: [PATCH 5/8] pack-bitmap-write.c: select pseudo-merges even for small bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-29T19:01:36Z","receivedAt":"2024-08-29T19:01:39Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Aug 17, 2024 at 06:34:01AM -0400, Jeff King wrote:\n> On Thu, Aug 15, 2024 at 01:31:12PM -0400, Taylor Blau wrote:\n>\n> > Ordinarily, the pack-bitmap machinery will select some subset of\n> > reachable commits to receive bitmaps. But when there are fewer than 100\n> > commits indexed in the first place, they will all receive bitmaps as a\n> > special case.\n> >\n> > When this happens, pseudo-merges are not generated, making it impossible\n> > to test pseudo-merge corner cases with fewer than 100 commits.\n> >\n> > Select pseudo-merges even for bitmaps with fewer than 100 commits to\n> > make such testing easier. In practice, this should not make a difference\n> > to non-testing bitmaps, as they are unlikely to be used when a\n> > repository has so few commits to begin with.\n>\n> I think you could argue that if there are fewer than 100 commits in the\n> history that pseudo-merge bitmaps are overkill, so it does not matter\n> much either way. But I think being consistent with our behavior (i.e.,\n> generating them if asked) is important for testing and debugging.\n\nOh, I think that argument is very fair and makes a lot of sense. The\npoint of this patch wasn't that having pseudo-merge bitmaps for\nrepositories that small (and which already have complete bitmap\ncoverage!) is helpful for performance.\n\nRather, it was to make it easier to test the pseudo-merge code path in\nsmall repositories without having to waste CPU cycles to generate 98\nextra commits when 2 would do, etc.\n\nThanks,\nTaylor\n"},{"id":"501857","messageId":"ZtDGB4otIjnAhiJ2@nand.local","threadId":"61956","inReplyTo":"20240817103822.GC551779@coredump.intra.peff.net","subject":"Re: [PATCH 7/8] pseudo-merge.c: do not generate empty pseudo-merge commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-29T19:03:35Z","receivedAt":"2024-08-29T19:03:38Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Aug 17, 2024 at 06:38:22AM -0400, Jeff King wrote:\n> [...] If we really want to test them, we can probably generate a\n> single example by hand (and we can probably even wait on that until we\n> see something in the wild that makes it worth doing).\n\nYeah, I had a similar thought as you. I considered adding a test fixture\nthat has a .bitmap with a pseudo-merge bitmap containing zero parents,\nbut figured that it was probably overkill since this feature is still\nconsidered experimental.\n\nThanks,\nTaylor\n"},{"id":"501858","messageId":"ZtDGImCRmC0N/cen@nand.local","threadId":"61956","inReplyTo":"20240817104412.GE551779@coredump.intra.peff.net","subject":"Re: [PATCH 0/8] pseudo-merge: avoid empty and non-closed pseudo-merge commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-08-29T19:04:02Z","receivedAt":"2024-08-29T19:04:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Aug 17, 2024 at 06:44:12AM -0400, Jeff King wrote:\n> On Thu, Aug 15, 2024 at 01:30:56PM -0400, Taylor Blau wrote:\n>\n> > This series fixes a couple of small issues with pseudo-merge groups,\n> > where it is possible to (a) select pseudo-merges that are not closed\n> > over reachability with respect to the bitmap's pack or MIDX, and (b)\n> > generate empty pseudo-merge commits.\n>\n> Thanks, the whole series looks good to me (I left some comments, but it\n> is all just walking through my thought process).\n\nThanks (as always) for a thoughtful review!\n\nThanks,\nTaylor\n"},{"id":"501860","messageId":"20240829193659.GB423429@coredump.intra.peff.net","threadId":"61956","inReplyTo":"ZtDFRYQRLQoe+CHS@nand.local","subject":"Re: [PATCH 1/8] pack-bitmap: initialize `bitmap_writer_init()` with packing_data","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-08-29T19:36:59Z","receivedAt":"2024-08-29T19:37:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 29, 2024 at 03:00:21PM -0400, Taylor Blau wrote:\n\n> > Even the midx code, which is not generating a pack, uses a \"fake\"\n> > packing_data as the way to express that (because inherently the bit\n> > ordering is all coming from the pack-index nature). If we likewise ever\n> > wrote code to generate bitmaps from an existing pack, it would probably\n> > use packing_data, too. :)\n> \n> I agree for the most part, though there is a lot of weight in\n> packing_data that would be nice to not have to carry around. I know\n> within GitHub's infrastructure we sometimes OOM kill invocations of \"git\n> multi-pack-index write --bitmap\" because of the memory overhead (a lot\n> of which is dominated by the actual traversal and bitmap generation, but\n> a lot that comes from just the per-object overhead).\n> \n> I've thought about alternative structures that might be a little more\n> memory efficient, but it's never gotten to the top of my list.\n\nTrue. What the index and bitmap steps really want is not an array of\nobject_entry, but an array of pack_idx_entry (which is the first\ncomponent of an object_entry).\n\nI wonder how feasible it would be to simply hold two arrays with\ncorresponding entries at each index. Many places only care about one or\nthe other. But for places that do care about both, especially ones that\nreceive a pointer to an individual object_entry, they'd need to receive\npointers to both.\n\nI briefly looked at the compile errors that come from making such a\nchange. Many of them look trivial, but I think some of them get weird\n(the ext_bases array is also holding object_entry structs). So maybe\nworth pursuing in the long run, but not something to knock out this\nafternoon.\n\n-Peff\n"}]}