{"thread":{"id":"66074","subject":"[PATCH] pack-bitmap: handle objects at bitmap position zero","startedAt":"2026-07-27T17:15:07Z","lastAt":"2026-07-28T23:31:53Z","messageCount":6,"participants":["David Lin","Taylor Blau","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"549097","messageId":"20260727171331.21088-1-davidlin@stripe.com","threadId":"66074","inReplyTo":null,"subject":"[PATCH] pack-bitmap: handle objects at bitmap position zero","fromName":"David Lin","fromEmail":"davidzylin@gmail.com","sentAt":"2026-07-27T17:13:31Z","receivedAt":"2026-07-27T17:15:07Z","isPatch":true,"body":"`bitmap_position()` only returns a negative value when an object is not present in the bitmap index.\n\nIn `find_objects()`, we have added a check in 11d45a6e6a to avoid processing a root whose reachability is already represented by the base bitmap, but accidentally uses `pos > 0`. Consequently, it never performs the membership test for an object at position zero.\n\nIf that object has an individual reachability bitmap, we unnecessarily load and OR that bitmap into the base again. Otherwise, we add the object to the not-mapped list, only for the subsequent pass to recognize that it is already present. The latter pass correctly treats all non-negative positions as valid, so this does not change the resulting object set, but an off-by-one edge case.\n\nTreat position zero as valid by changing the condition to `pos >= 0`.\n\nThe existing pseudo-merge traversal test exercises this case. Its position-zero commit is presented through multiple roots. Before this change, each occurrence is counted as a bitmap hit; afterwards, only the first occurrence loads the bitmap. Assert the resulting hit count to cover the boundary condition.\n\nThanks in advance for the review!\n\nSigned-off-by: David Lin \n---\n pack-bitmap.c | 2 +-\n t/t5333-pseudo-merge-bitmaps.sh | 4 ++++\n 2 files changed, 5 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex d8dc4ae8d1..e85bd69ba4 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1569,7 +1569,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \n \t\tif (base) {\n \t\t\tint pos = bitmap_position(bitmap_git, &object->oid);\n-\t\t\tif (pos > 0 && bitmap_get(base, pos)) {\n+\t\t\tif (pos >= 0 && bitmap_get(base, pos)) {\n \t\t\t\tobject->flags |= SEEN;\n \t\t\t\tcontinue;\n \t\t\t}\ndiff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh\nindex 305d677108..2a6c0e2318 100755\n--- a/t/t5333-pseudo-merge-bitmaps.sh\n+++ b/t/t5333-pseudo-merge-bitmaps.sh\n@@ -85,6 +85,10 @@ test_expect_success 'bitmap traversal with pseudo-merges' '\n \n \ttest_pseudo_merges_satisfied 8 In `find_objects()`, we have added a check in 11d45a6e6a to avoid\n> processing a root whose reachability is already represented by the\n> base bitmap, but accidentally uses `pos > 0`. Consequently, it never\n> performs the membership test for an object at position zero.\n\nMakes sense. The commit message here and below looks reasonable, but\nplease wrap it at a maximum of 72 characters per line.\n\n> If that object has an individual reachability bitmap, we unnecessarily\n> load and OR that bitmap into the base again. Otherwise, we add the\n> object to the not-mapped list, only for the subsequent pass to\n> recognize that it is already present. The latter pass correctly treats\n> all non-negative positions as valid, so this does not change the\n> resulting object set, but an off-by-one edge case.\n\nAt this point, \"load\" is a fairly cheap operation. We have already\nloaded the bits off of disk in a previous step. If the bitmap was\nstored as an XOR against a neighbor, we have already XOR'd it against\nthat neighbor and stored the result.\n\nMore importantly, you're right that this does not change the result we\nget from the bitmap machinery. `find_objects()` works as follows:\n\n 1. We first start with a \"roots_bitmap\" (which is non-zero *only* in\n the positions specified by the given \"roots\", and *not* their\n reachability closure).\n\n 2. We then apply pseudo-merges to that bitmap of roots, OR-ing that\n into the \"base\" bitmap if we were able to apply a non-zero amount of\n pseudo-merge bitamps.\n\n 3. We then loop over all supplied \"roots\". If we have a \"base\" bitmap,\n we try and mark the given root as SEEN if its corresponding bit\n position is set. If it isn't, then we try and call the function\n `add_commit_to_bitmap()`, which ORs in a stored bitmap to \"base\".\n\n 4. Finally, if that fails, mark the object as `not_mapped`.\n\nSo in the case there are pseudo-merge bitmaps, and if one of our\nsupplied \"roots\" is stored at bit position zero, then we will only fall\nthrough to the `add_commit_to_bitmap()` case (incrementing the \"hit\"\ncount further than necessary), but othewrise marking the object as SEEN\nand continuing. This also sets \"existing_bitmaps\", which involves one\nextra pseudo-merge cascade.\n\nIn the case where there aren't any pseudo-merge bitmaps, the reasoning\nis similar, except that we must have (a) at least one \"root\" which has a\nstored bitmap, and (b) that we see the root at bit position zero *after*\none or more stored bitmaps. Note that (a) and (b) can refer to the same\nroot here, so something like:\n\n $ git rev-list --objects --use-bitmap-index HEAD HEAD\n\nshould do the trick.\n\n> Treat position zero as valid by changing the condition to `pos >= 0`.\n\nI briefly wondered whether other callers of `bitmap_position()` would\nhave similar issues. There are a total of twelve `bitmap_position()`\ncallers, and all of them except the one in this patch handle the return\nvalue correctly.\n\nAs an aside, we could consider doing something like changing the return\nvalue of `bitmap_position()` to indicate non-zero on failure, and zero\non success, and fills the result through a uint32_t pointer. I roughed\nthis out locally, but the patch is mostly noisy and not really worth\nsending.\n\nThe important part of the change is the following:\n\n--- 8< ---\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex d8dc4ae8d1..4e86aa15dd 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1064,7 +1064,8 @@ struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,\n }\n\n static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,\n-\t\t\t\t\t const struct object_id *oid)\n+\t\t\t\t\t const struct object_id *oid,\n+\t\t\t\t\t uint32_t *bitmap_pos)\n {\n \tkh_oid_pos_t *positions = bitmap_git->ext_index.positions;\n \tkhiter_t pos = kh_get_oid_pos(positions, *oid);\n@@ -1078,39 +1079,44 @@ static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,\n }\n\n static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,\n-\t\t\t\t\t const struct object_id *oid)\n+\t\t\t\t\t const struct object_id *oid,\n+\t\t\t\t\t uint32_t *bitmap_pos)\n {\n-\tuint32_t pos;\n \toff_t offset = find_pack_entry_one(oid, bitmap_git->pack);\n+\n \tif (!offset)\n \t\treturn -1;\n\n-\tif (offset_to_pack_pos(bitmap_git->pack, offset, &pos) < 0)\n-\t\treturn -1;\n-\treturn pos;\n+\treturn offset_to_pack_pos(bitmap_git->pack, offset, bitmap_pos);\n }\n\n static int bitmap_position_midx(struct bitmap_index *bitmap_git,\n-\t\t\t\tconst struct object_id *oid)\n+\t\t\t\tconst struct object_id *oid,\n+\t\t\t\tuint32_t *bitmap_pos)\n {\n-\tuint32_t want, got;\n+\tuint32_t want;\n+\n \tif (!bsearch_midx(oid, bitmap_git->midx, &want))\n \t\treturn -1;\n\n-\tif (midx_to_pack_pos(bitmap_git->midx, want, &got) < 0)\n-\t\treturn -1;\n-\treturn got;\n+\treturn midx_to_pack_pos(bitmap_git->midx, want, bitmap_pos);\n }\n\n static int bitmap_position(struct bitmap_index *bitmap_git,\n-\t\t\t const struct object_id *oid)\n+\t\t\t const struct object_id *oid,\n+\t\t\t uint32_t *bitmap_pos)\n {\n-\tint pos;\n+\tint ret;\n+\n \tif (bitmap_is_midx(bitmap_git))\n-\t\tpos = bitmap_position_midx(bitmap_git, oid);\n+\t\tret = bitmap_position_midx(bitmap_git, oid, bitmap_pos);\n \telse\n-\t\tpos = bitmap_position_packfile(bitmap_git, oid);\n-\treturn (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);\n+\t\tret = bitmap_position_packfile(bitmap_git, oid, bitmap_pos);\n+\n+\tif (!ret)\n+\t\treturn 0;\n+\n+\treturn bitmap_position_extended(bitmap_git, oid, bitmap_pos);\n }\n\n static int ext_index_add_object(struct bitmap_index *bitmap_git,\n--- >8 ---\n\n> The existing pseudo-merge traversal test exercises this case. Its\n> position-zero commit is presented through multiple roots. Before this\n> change, each occurrence is counted as a bitmap hit; afterwards, only\n> the first occurrence loads the bitmap. Assert the resulting hit count\n> to cover the boundary condition.\n\nExactly.\n\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index d8dc4ae8d1..e85bd69ba4 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -1569,7 +1569,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n>\n> \t\tif (base) {\n> \t\t\tint pos = bitmap_position(bitmap_git, &object->oid);\n> -\t\t\tif (pos > 0 && bitmap_get(base, pos)) {\n> +\t\t\tif (pos >= 0 && bitmap_get(base, pos)) {\n\nOK, this is obviously good.\n\n> diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh\n> index 305d677108..2a6c0e2318 100755\n> --- a/t/t5333-pseudo-merge-bitmaps.sh\n> +++ b/t/t5333-pseudo-merge-bitmaps.sh\n> @@ -85,6 +85,10 @@ test_expect_success 'bitmap traversal with pseudo-merges' '\n>\n> \ttest_pseudo_merges_satisfied 8 \ttest_pseudo_merges_cascades 1 +\n> +\t# Position zero is named by HEAD, its branch, and its tag, but its\n> +\t# bitmap should only be loaded once.\n> +\ttest_trace2_data bitmap bitmap/hits 1 \ttest_cmp expect actual\n> '\n\nThis is good, though it is a little bit fragile in the sense that we\nrely on the pack ordering to place HEAD as the first object in the pack.\nI'm comfortable with it given the comment, which effectively documents\nthat fragility.\n\nHowever, I think it's worth covering the non-pseudo-merge case as I\ndescribed above, too.\n\nThanks,\nTaylor\n"},{"id":"549127","messageId":"20260728134047.33801-1-davidlin@stripe.com","threadId":"66074","inReplyTo":"ame6B7pHSvXekdPZ@com-79390","subject":"Re: [PATCH] pack-bitmap: handle objects at bitmap position zero","fromName":"David Lin","fromEmail":"davidzylin@gmail.com","sentAt":"2026-07-28T13:40:47Z","receivedAt":"2026-07-28T13:40:55Z","isPatch":true,"body":"On Mon, Jul 27, 2026 at 03:05:27PM -0500, Taylor Blau wrote:\n> Makes sense. The commit message here and below looks reasonable, but\n> please wrap it at a maximum of 72 characters per line.\n\nDone in v2, apologize for the formatting.\n\n> At this point, \"load\" is a fairly cheap operation. We have already\n> loaded the bits off of disk in a previous step. If the bitmap was\n> stored as an XOR against a neighbor, we have already XOR'd it against\n> that neighbor and stored the result.\n\nAgree, I reworded the commit message/comment to consolidate the wording, so\nthat a duplicate disk read is not always implied.\n\n> However, I think it's worth covering the non-pseudo-merge case as I\n> described above, too.\n\nGood call, and thank you for the expanded explanation above, added in v2 using\na duplicate `HEAD` traversal, as suggested.\n\nThanks again for the detailed review. I will send v2 shortly.\n\nBest,\nDavid\n\n"},{"id":"549129","messageId":"20260728135248.61304-1-davidlin@stripe.com","threadId":"66074","inReplyTo":"20260727171331.21088-1-davidlin@stripe.com","subject":"[PATCH v2] pack-bitmap: handle objects at bitmap position zero","fromName":"David Lin","fromEmail":"davidzylin@gmail.com","sentAt":"2026-07-28T13:52:48Z","receivedAt":"2026-07-28T13:54:33Z","isPatch":true,"body":"`bitmap_position()` only returns a negative value when an object is not\npresent in the bitmap index.\n\nIn `find_objects()`, we have added a check (11d45a6e6a) to avoid\nprocessing a root whose reachability is already represented by the base\nbitmap, but accidentally uses `pos > 0`. Consequently, it never performs\nthe membership test for an object at position zero.\n\nIf that object has an individual reachability bitmap, we unnecessarily\nOR that bitmap into the base again. Otherwise, we add the object to the\nnot-mapped list, only for the subsequent pass to recognize that it is\nalready present. The latter pass correctly treats all non-negative\npositions as valid, so this does not change the resulting object set,\nbut an off-by-one edge case.\n\nTreat position zero as valid by changing the condition to `pos >= 0`.\n\nThe existing pseudo-merge traversal test exercises this case. Its\nposition-zero commit is presented through multiple roots. Before this\nchange, each occurrence is counted as a bitmap hit; afterwards, only\nthe first occurrence is counted. Assert the resulting hit count to\ncover the boundary condition.\n\nAlso cover the non-pseudo-merge case by passing `HEAD` twice. The first\noccurrence initializes the base from its stored bitmap, and the second\nmust recognize that position zero is already present.\n\nHelped-by: Taylor Blau \nSigned-off-by: David Lin \n---\nChanges since v1:\n- Clarify the bitmap disk load wordings.\n- Add coverage for the non-pseudo-merge case.\n\n pack-bitmap.c | 2 +-\n t/t5333-pseudo-merge-bitmaps.sh | 14 +++++++++++++-\n 2 files changed, 14 insertions(+), 2 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex d8dc4ae8d1..e85bd69ba4 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1569,7 +1569,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \n \t\tif (base) {\n \t\t\tint pos = bitmap_position(bitmap_git, &object->oid);\n-\t\t\tif (pos > 0 && bitmap_get(base, pos)) {\n+\t\t\tif (pos >= 0 && bitmap_get(base, pos)) {\n \t\t\t\tobject->flags |= SEEN;\n \t\t\t\tcontinue;\n \t\t\t}\ndiff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh\nindex 305d677108..5b2a17f90a 100755\n--- a/t/t5333-pseudo-merge-bitmaps.sh\n+++ b/t/t5333-pseudo-merge-bitmaps.sh\n@@ -50,7 +50,15 @@ test_expect_success 'bitmap traversal without pseudo-merges' '\n \ttest_pseudo_merges_cascades 0 merges &&\n \ttest_must_be_empty merges &&\n-\ttest_cmp expect actual\n+\ttest_cmp expect actual &&\n+\n+\t: >trace2.txt &&\n+\tGIT_TRACE2_EVENT=$PWD/trace2.txt \\\n+\t\tgit rev-list --objects --use-bitmap-index HEAD HEAD >/dev/null &&\n+\n+\t# The first HEAD initializes base from its position-zero bitmap. The\n+\t# duplicate root should not count as another bitmap hit.\n+\ttest_trace2_data bitmap bitmap/hits 1 writes:\n\n> `bitmap_position()` only returns a negative value when an object is not\n> present in the bitmap index.\n> ...\n> Also cover the non-pseudo-merge case by passing `HEAD` twice. The first\n> occurrence initializes the base from its stored bitmap, and the second\n> must recognize that position zero is already present.\n>\n> Helped-by: Taylor Blau \n> Signed-off-by: David Lin \n> ---\n> Changes since v1:\n> - Clarify the bitmap disk load wordings.\n> - Add coverage for the non-pseudo-merge case.\n\nThanks, both of you. Will queue.\n"},{"id":"549180","messageId":"amk75SuhyHBbx-E8@com-79390","threadId":"66074","inReplyTo":"xmqq5x1yd968.fsf@gitster.g","subject":"Re: [PATCH v2] pack-bitmap: handle objects at bitmap position zero","fromName":"Taylor Blau","fromEmail":"ttaylorr@openai.com","sentAt":"2026-07-28T23:31:49Z","receivedAt":"2026-07-28T23:31:53Z","isPatch":true,"body":"On Tue, Jul 28, 2026 at 03:46:39PM -0700, Junio C Hamano wrote:\n> David Lin writes:\n>\n> > `bitmap_position()` only returns a negative value when an object is not\n> > present in the bitmap index.\n> > ...\n> > Also cover the non-pseudo-merge case by passing `HEAD` twice. The first\n> > occurrence initializes the base from its stored bitmap, and the second\n> > must recognize that position zero is already present.\n> >\n> > Helped-by: Taylor Blau \n> > Signed-off-by: David Lin \n> > ---\n> > Changes since v1:\n> > - Clarify the bitmap disk load wordings.\n> > - Add coverage for the non-pseudo-merge case.\n>\n> Thanks, both of you. Will queue.\n\nThis version looks good to me.\n\nThanks,\nTaylor\n"}]}