[PATCH] pack-bitmap: remove checks before bitmap_free

[PATCH] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects, we build a roots_bitmap and
cascade it to cb.base. However, I’m wondering why we only free
roots_bitmap when the cascade succeeds. It seems we could safely remove
this check and always free roots_bitmap afterward, which might provide
some performance benefits.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
    pack-bitmap: remove checks before bitmap_free
    
    In pack-bitmap.c:find_boundary_objects, remove cascade success check and
    always free roots_bitmap afterward to make static analysis tool works
    better.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1977%2Fbrandb97%2Fremove-check-before-bitmap-free-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1977/brandb97/remove-check-before-bitmap-free-v1
Pull-Request: https://github.com/git/git/pull/1977

 pack-bitmap.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ac6d62b980c..8727f316de9 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
 			bitmap_set(roots_bitmap, pos);
 		}
 
-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
-			bitmap_free(roots_bitmap);
+		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+		bitmap_free(roots_bitmap);
 	}
 
 	/*

base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
-- 
gitgitgadget

Re: [PATCH] pack-bitmap: remove checks before bitmap_free

[Patrick Steinhardt]

On Sun, May 25, 2025 at 05:09:43AM +0000, Lidong Yan via GitGitGadget wrote:
> From: Lidong Yan <502024330056@smail.nju.edu.cn>
> 
> In pack-bitmap.c:find_boundary_objects, we build a roots_bitmap and
> cascade it to cb.base. However, I’m wondering why we only free
> roots_bitmap when the cascade succeeds. It seems we could safely remove
> this check and always free roots_bitmap afterward, which might provide
> some performance benefits.

This commit message isn't quite a convincing one. As author of a patch
the onus falls on you to explain why the change is sensible, but even
more importantly it also falls on you to explain why it is correct.

It is of course fine to ask for help and input, but in that case you
should probably mark the patch accordingly, for example with the RFC
tag.

> diff --git a/pack-bitmap.c b/pack-bitmap.c
> index ac6d62b980c..8727f316de9 100644
> --- a/pack-bitmap.c
> +++ b/pack-bitmap.c
> @@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
>  			bitmap_set(roots_bitmap, pos);
>  		}
>  
> -		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
> -			bitmap_free(roots_bitmap);
> +		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
> +		bitmap_free(roots_bitmap);
>  	}

We know that `roots_bitmap` is always allocated via `bitmap_new()`, so
it won't ever be a `NULL` pointer and should in theory always be free'd.
Furthermore, we know that the pointer never escapes the local scope,
either.

The next question would thus be: what does `cascade_pseudo_merges_1()`
do with the bitmap? Are there situations where it does free it for us,
or where it moves ownership of that bitmap? So let's go down the call
chain:

  - `cascade_pseudo_merges_1()` passes it on to
    `cascade_pseudo_merges()`.

  - `cascade_pseudo_merges()` passes it on to `apply_pseudo_merge()`.

`apply_pseudo_merge()` itself then checks whether the pseudo-merge is a
subset of the `roots_bitmap` and, if not, ORs the pseudo-merge into it.

None of these operations move around ownership or free the bitmap, so
this looks like a true memory leak in case `cascade_pseudo_merges_1()`
returns non-zero. Which would raise another question: when exactly does
it return non-zero, and can we trigger the memory leak via a test?

Information like this should ideally be part of the commit message
itself. It helps reviewers to figure out _why_ a change is correct and,
if anybody were to dig into history, would also help them to have enough
context.

Thanks!

Patrick

Re: [PATCH] pack-bitmap: remove checks before bitmap_free

[lidongyan]

2025年5月26日 14:49，Patrick Steinhardt <ps@pks.im> 写道：
> 
> This commit message isn't quite a convincing one. As author of a patch
> the onus falls on you to explain why the change is sensible, but even
> more importantly it also falls on you to explain why it is correct.
> 
> It is of course fine to ask for help and input, but in that case you
> should probably mark the patch accordingly, for example with the RFC
> tag.

Thank you for the suggestion. Please allow me to keep the patch in its
 current form this time. 

> We know that `roots_bitmap` is always allocated via `bitmap_new()`, so
> it won't ever be a `NULL` pointer and should in theory always be free'd.
> Furthermore, we know that the pointer never escapes the local scope,
> either.
> 
> The next question would thus be: what does `cascade_pseudo_merges_1()`
> do with the bitmap? Are there situations where it does free it for us,
> or where it moves ownership of that bitmap? So let's go down the call
> chain:
> 
>  - `cascade_pseudo_merges_1()` passes it on to
>    `cascade_pseudo_merges()`.
> 
>  - `cascade_pseudo_merges()` passes it on to `apply_pseudo_merge()`.
> 
> `apply_pseudo_merge()` itself then checks whether the pseudo-merge is a
> subset of the `roots_bitmap` and, if not, ORs the pseudo-merge into it.

I would put this into commit message. I also noticed that `find_objects()` in
pack-bitmap.c has similar code but without `if (cascade_pseudo_merges_1)`.

> 
> None of these operations move around ownership or free the bitmap, so
> this looks like a true memory leak in case `cascade_pseudo_merges_1()`
> returns non-zero. Which would raise another question: when exactly does
> it return non-zero, and can we trigger the memory leak via a test?

Seems we need to make `bitmap_git->pseudo_merges->v[I]` contains some
objects which doesn’t exist in `roots`. I’ll try to figure it out in the next patch. 

Thanks
Lidong

[PATCH v2 0/2] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

In pack-bitmap.c:find_boundary_objects, remove cascade success check and
always free roots_bitmap afterward to make static analysis tool works
better.

Lidong Yan (2):
  pack-bitmap: remove checks before bitmap_free
  t5333: test memory leak when use pseudo-merge in boundary traversal

 pack-bitmap.c                   |  4 ++--
 t/t5333-pseudo-merge-bitmaps.sh | 20 ++++++++++++++++++++
 2 files changed, 22 insertions(+), 2 deletions(-)


base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1977%2Fbrandb97%2Fremove-check-before-bitmap-free-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1977/brandb97/remove-check-before-bitmap-free-v2
Pull-Request: https://github.com/git/git/pull/1977

Range-diff vs v1:

 1:  19677bcbc3d ! 1:  d7b7a0e29ec pack-bitmap: remove checks before bitmap_free
     @@ Commit message
          pack-bitmap: remove checks before bitmap_free
      
          In pack-bitmap.c:find_boundary_objects, we build a roots_bitmap and
     -    cascade it to cb.base. However, I’m wondering why we only free
     -    roots_bitmap when the cascade succeeds. It seems we could safely remove
     -    this check and always free roots_bitmap afterward, which might provide
     -    some performance benefits.
     +    cascade it to cb.base. Only when cascade failed, roots_bitmap is
     +    freed otherwise it leaks. Since cascade_pseudo_merges_1() only use
     +    roots_bitmap as a mutable reference not takes roots_bitmap's ownership
     +    we'd better remove `if(cascade_pseudo_merges_1)` and frees roots_bitmap
     +    anyway.
      
          Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
      
 -:  ----------- > 2:  56b24d681cb t5333: test memory leak when use pseudo-merge in boundary traversal

-- 
gitgitgadget

[PATCH v2 1/2] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects, we build a roots_bitmap and
cascade it to cb.base. Only when cascade failed, roots_bitmap is
freed otherwise it leaks. Since cascade_pseudo_merges_1() only use
roots_bitmap as a mutable reference not takes roots_bitmap's ownership
we'd better remove `if(cascade_pseudo_merges_1)` and frees roots_bitmap
anyway.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
 pack-bitmap.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ac6d62b980c5..8727f316de92 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
 			bitmap_set(roots_bitmap, pos);
 		}
 
-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
-			bitmap_free(roots_bitmap);
+		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+		bitmap_free(roots_bitmap);
 	}
 
 	/*
-- 
gitgitgadget

[PATCH v2 2/2] t5333: test memory leak when use pseudo-merge in boundary traversal

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
if cascade_pseudo_merges_1() fails. Otherwise, it leaks, leading to
a memory leak that currently lacks a dedicated test to detect it.

To trigger this leak, we need a pseudo-merge whose size is equal to
or smaller than roots_bitmap (which corresponds to the set of "haves"
commits in prepare_bitmap_walk()). To do this, we can create two
commits: A and B. Add A to the pseudo-merge list and perform a traversal
over the range A..B. In this scenario, the "haves" set will be {A},
and cascade_pseudo_merges_1() will succeed — thereby exposing the leak
due to the missing roots_bitmap cleanup.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
 t/t5333-pseudo-merge-bitmaps.sh | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index 56674db562f9..5e263fce50a7 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -445,4 +445,24 @@ test_expect_success 'pseudo-merge closure' '
 	)
 '
 
+test_expect_success 'use pseudo-merge in boundary traversal' '
+	git init pseudo-merge-boundary-traversal &&
+	(
+		cd pseudo-merge-boundary-traversal &&
+
+		git config bitmapPseudoMerge.test.pattern refs/ &&
+		git config bitmapPseudoMerge.test.threshold now &&
+		git config bitmapPseudoMerge.test.stableThreshold now &&
+		export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
+
+		test_commit A &&
+		git repack -adb &&
+		test_commit B &&
+
+		echo '1' >expect &&
+		git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
+		test_cmp expect actual
+	)
+'
+
 test_done
-- 
gitgitgadget

Re: [PATCH v2 2/2] t5333: test memory leak when use pseudo-merge in boundary traversal

[Junio C Hamano]

"Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:

> +		export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&

The test linter complains on this line for me, it seems.

I've ran out of time for today's integration cycle, so this topic
will not be in what I'll push out later this afternoon.

Thanks.

Re: [PATCH v2 2/2] t5333: test memory leak when use pseudo-merge in boundary traversal

[Eric Sunshine]

On Fri, May 30, 2025 at 5:42 PM Junio C Hamano <gitster@pobox.com> wrote:
> "Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:
> > +             export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
>
> The test linter complains on this line for me, it seems.

To provide a bit more context:

    % (cd t && make test-lint-shell-syntax)

tells you that `export FOO=bar` is not portable and that it should
instead be written as:

    FOO=bar &&
    export FOO &&

Re: [PATCH v2 2/2] t5333: test memory leak when use pseudo-merge in boundary traversal

[lidongyan]

2025年5月31日 05:50，Eric Sunshine <sunshine@sunshineco.com> 写道：
> 
> On Fri, May 30, 2025 at 5:42 PM Junio C Hamano <gitster@pobox.com> wrote:
>> "Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:
>>> +             export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
>> 
>> The test linter complains on this line for me, it seems.
> 
> To provide a bit more context:
> 
>    % (cd t && make test-lint-shell-syntax)

Thanks, I should run this before submit.

> 
> tells you that `export FOO=bar` is not portable and that it should
> instead be written as:
> 
>    FOO=bar &&
>    export FOO &&
> 

Re: [PATCH v2 0/2] pack-bitmap: remove checks before bitmap_free

[Junio C Hamano]

"Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:

> In pack-bitmap.c:find_boundary_objects, remove cascade success check and
> always free roots_bitmap afterward to make static analysis tool works
> better.
>
> Lidong Yan (2):
>   pack-bitmap: remove checks before bitmap_free
>   t5333: test memory leak when use pseudo-merge in boundary traversal

How would these two commits relate to each other?  If [2/2] is a
test that exposes existing breakage if [1/2] weren't there, we
usually have them in the same commit.  If they are not related, of
course, they can be applied and advanced independently.

[PATCH v3] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
use roots_bitmap as a mutable reference but not takes roots_bitmap's
ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
And this leak currently lacks a dedicated test to detect it.

To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
always calling bitmap_free(roots_bitmap);

To trigger this leak, we need a pseudo-merge whose size is equal to
or smaller than roots_bitmap (which corresponds to the set of "haves"
commits in prepare_bitmap_walk()). To do this, we can create two
commits: A and B. Add A to the pseudo-merge list and perform a traversal
over the range A..B. In this scenario, the "haves" set will be {A},
and cascade_pseudo_merges_1() will succeed, thereby exposing the leak
due to the missing roots_bitmap cleanup.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
    pack-bitmap: remove checks before bitmap_free
    
    In pack-bitmap.c:find_boundary_objects, remove cascade success check and
    always free roots_bitmap afterward to make static analysis tool works
    better.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1977%2Fbrandb97%2Fremove-check-before-bitmap-free-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1977/brandb97/remove-check-before-bitmap-free-v3
Pull-Request: https://github.com/git/git/pull/1977

Range-diff vs v2:

 1:  d7b7a0e29ec < -:  ----------- pack-bitmap: remove checks before bitmap_free
 2:  56b24d681cb ! 1:  151a7f5dc70 t5333: test memory leak when use pseudo-merge in boundary traversal
     @@ Metadata
      Author: Lidong Yan <502024330056@smail.nju.edu.cn>
      
       ## Commit message ##
     -    t5333: test memory leak when use pseudo-merge in boundary traversal
     +    pack-bitmap: remove checks before bitmap_free
      
          In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
     -    if cascade_pseudo_merges_1() fails. Otherwise, it leaks, leading to
     -    a memory leak that currently lacks a dedicated test to detect it.
     +    if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
     +    use roots_bitmap as a mutable reference but not takes roots_bitmap's
     +    ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
     +    And this leak currently lacks a dedicated test to detect it.
     +
     +    To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
     +    always calling bitmap_free(roots_bitmap);
      
          To trigger this leak, we need a pseudo-merge whose size is equal to
          or smaller than roots_bitmap (which corresponds to the set of "haves"
          commits in prepare_bitmap_walk()). To do this, we can create two
          commits: A and B. Add A to the pseudo-merge list and perform a traversal
          over the range A..B. In this scenario, the "haves" set will be {A},
     -    and cascade_pseudo_merges_1() will succeed — thereby exposing the leak
     +    and cascade_pseudo_merges_1() will succeed, thereby exposing the leak
          due to the missing roots_bitmap cleanup.
      
          Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
      
     + ## pack-bitmap.c ##
     +@@ pack-bitmap.c: static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
     + 			bitmap_set(roots_bitmap, pos);
     + 		}
     + 
     +-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
     +-			bitmap_free(roots_bitmap);
     ++		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
     ++		bitmap_free(roots_bitmap);
     + 	}
     + 
     + 	/*
     +
       ## t/t5333-pseudo-merge-bitmaps.sh ##
      @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'pseudo-merge closure' '
       	)
     @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'pseudo-merge closure' '
      +		git config bitmapPseudoMerge.test.pattern refs/ &&
      +		git config bitmapPseudoMerge.test.threshold now &&
      +		git config bitmapPseudoMerge.test.stableThreshold now &&
     -+		export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
     ++		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
      +
      +		test_commit A &&
      +		git repack -adb &&


 pack-bitmap.c                   |  4 ++--
 t/t5333-pseudo-merge-bitmaps.sh | 20 ++++++++++++++++++++
 2 files changed, 22 insertions(+), 2 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ac6d62b980c..8727f316de9 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
 			bitmap_set(roots_bitmap, pos);
 		}
 
-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
-			bitmap_free(roots_bitmap);
+		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+		bitmap_free(roots_bitmap);
 	}
 
 	/*
diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index 56674db562f..454f8c7a817 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -445,4 +445,24 @@ test_expect_success 'pseudo-merge closure' '
 	)
 '
 
+test_expect_success 'use pseudo-merge in boundary traversal' '
+	git init pseudo-merge-boundary-traversal &&
+	(
+		cd pseudo-merge-boundary-traversal &&
+
+		git config bitmapPseudoMerge.test.pattern refs/ &&
+		git config bitmapPseudoMerge.test.threshold now &&
+		git config bitmapPseudoMerge.test.stableThreshold now &&
+		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
+
+		test_commit A &&
+		git repack -adb &&
+		test_commit B &&
+
+		echo '1' >expect &&
+		git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
+		test_cmp expect actual
+	)
+'
+
 test_done

base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
-- 
gitgitgadget

Re: [PATCH v3] pack-bitmap: remove checks before bitmap_free

[Junio C Hamano]

"Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:

> +test_expect_success 'use pseudo-merge in boundary traversal' '
> +	git init pseudo-merge-boundary-traversal &&
> +	(
> +		cd pseudo-merge-boundary-traversal &&
> +
> +		git config bitmapPseudoMerge.test.pattern refs/ &&
> +		git config bitmapPseudoMerge.test.threshold now &&
> +		git config bitmapPseudoMerge.test.stableThreshold now &&


> +		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&

Either before or after that line, don't you need to 

		export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL &&

as well?

And if the test passed without exporting the variable, is it really
testing what we want to test?

> +		test_commit A &&
> +		git repack -adb &&
> +		test_commit B &&
> +
> +		echo '1' >expect &&
> +		git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
> +		test_cmp expect actual
> +	)
> +'
> +
>  test_done
>
> base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229

Re: [PATCH v3] pack-bitmap: remove checks before bitmap_free

[lidongyan]

2025年6月3日 14:12，Junio C Hamano <gitster@pobox.com> 写道：
> 
> "Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> +test_expect_success 'use pseudo-merge in boundary traversal' '
>> + git init pseudo-merge-boundary-traversal &&
>> + (
>> + cd pseudo-merge-boundary-traversal &&
>> +
>> + git config bitmapPseudoMerge.test.pattern refs/ &&
>> + git config bitmapPseudoMerge.test.threshold now &&
>> + git config bitmapPseudoMerge.test.stableThreshold now &&
> 
> 
>> + GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
> 
> Either before or after that line, don't you need to 
> 
> export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL &&
> 
> as well?
> 
> And if the test passed without exporting the variable, is it really
> testing what we want to test?
> 

Sorry about that. I should put GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL
In front of `git rev-list …` so that when traverse bitmap it enters `pack-bitmap:find_boundary_objects()`.

>> + test_commit A &&
>> + git repack -adb &&
>> + test_commit B &&
>> +
>> + echo '1' >expect &&
>> + git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
>> + test_cmp expect actual
>> + )
>> +'
>> +
>> test_done
>> 
>> base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
> 

Re: [PATCH v3] pack-bitmap: remove checks before bitmap_free

[Junio C Hamano]

lidongyan <502024330056@smail.nju.edu.cn> writes:

>> And if the test passed without exporting the variable, is it really
>> testing what we want to test?
>> 
>
> Sorry about that. I should put GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL
> In front of `git rev-list …` so that when traverse bitmap it
> enters `pack-bitmap:find_boundary_objects()`.

That would work well.  By narrowing where the environment variable is
applied, such an arrangement would also help readers.

It still is curious why this version did not fail for you, though.
If setting it without exporting it still made "rev-list" traverse
and expected result, wouldn't that mean we are not really testing
what we want to test?

>>> + test_commit A &&
>>> + git repack -adb &&
>>> + test_commit B &&
>>> +
>>> + echo '1' >expect &&
>>> + git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
>>> + test_cmp expect actual
>>> + )
>>> +'
>>> +
>>> test_done
>>> 
>>> base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
>> 

Re: [PATCH v3] pack-bitmap: remove checks before bitmap_free

[lidongyan]

2025年6月3日 23:14，Junio C Hamano <gitster@pobox.com> 写道：
> 
> It still is curious why this version did not fail for you, though.
> If setting it without exporting it still made "rev-list" traverse
> and expected result, wouldn't that mean we are not really testing
> what we want to test?
> 
>>>> + test_commit A &&
>>>> + git repack -adb &&
>>>> + test_commit B &&
>>>> +
>>>> + echo '1' >expect &&
>>>> + git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
>>>> + test_cmp expect actual
>>>> + )
>>>> +'
>>>> +
>>>> test_done
>>>> 
>>>> base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
>>> 
> 

No, this test case should only fail when ’SANITIZE_LEAK’ is set. I heard
that other developer call this type of test as prereq. So only when git is
compiled with `-fsanitize=address` and `export ASAN_OPTION=detect_leaks=1`
and without changes as

- if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
- bitmap_free(roots_bitmap);
+ cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+ bitmap_free(roots_bitmap);

This test case would fail.

Re: [PATCH v3] pack-bitmap: remove checks before bitmap_free

[Junio C Hamano]

lidongyan <502024330056@smail.nju.edu.cn> writes:

> No, this test case should only fail when ’SANITIZE_LEAK’ is set. I heard
> that other developer call this type of test as prereq. So only when git is
> compiled with `-fsanitize=address` and `export ASAN_OPTION=detect_leaks=1`
> and without changes as
>
> - if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
> - bitmap_free(roots_bitmap);
> + cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
> + bitmap_free(roots_bitmap);
>
> This test case would fail.

If the test tickles the code path that used to be broken (and
corrected by the patch), temporarily reverting only the code changes
to pack-bitmap.c and then this test (under leak sanitizer, of
course) should have failed.  And if the test passed with such an
experiment, you would have noticed that something is wrong.

But you didn't notice it and sent the patch, so I'd assume that you
saw such a test still failed.  IOW, with "export" forgotten in the
test, the original (unfixed) code still leaked, without using the
bitmap traversal, right?

Which was where my question came from.

Or perhaps you didn't do that "is my test really tickling the bug I
fixed and makes the original code without my fix fail?" test?  Which
also explains why lack of "export" was not noticed.

Re: [PATCH v3] pack-bitmap: remove checks before bitmap_free

[lidongyan]

2025年6月4日 20:32，Junio C Hamano <gitster@pobox.com> 写道：
> 
> lidongyan <502024330056@smail.nju.edu.cn> writes:
> 
>> No, this test case should only fail when ’SANITIZE_LEAK’ is set. I heard
>> that other developer call this type of test as prereq. So only when git is
>> compiled with `-fsanitize=address` and `export ASAN_OPTION=detect_leaks=1`
>> and without changes as
>> 
>> - if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
>> - bitmap_free(roots_bitmap);
>> + cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
>> + bitmap_free(roots_bitmap);
>> 
>> This test case would fail.
> 
> If the test tickles the code path that used to be broken (and
> corrected by the patch), temporarily reverting only the code changes
> to pack-bitmap.c and then this test (under leak sanitizer, of
> course) should have failed.  And if the test passed with such an
> experiment, you would have noticed that something is wrong.
> 
> But you didn't notice it and sent the patch, so I'd assume that you
> saw such a test still failed.  IOW, with "export" forgotten in the
> test, the original (unfixed) code still leaked, without using the
> bitmap traversal, right?
> 
> Which was where my question came from.
> 
> Or perhaps you didn't do that "is my test really tickling the bug I
> fixed and makes the original code without my fix fail?" test?  Which
> also explains why lack of "export" was not noticed.

The test case in v0 with “export” would fail, but test-lint in CI shouts. To make
CI happy, I delete “export” and submit immediately. So I am sure now in
v3 this test truly test what we want. But I make two mistakes that I haven’t
pass all CI test before submit. I apologize for the oversight. I'll double-check
my tests more carefully in the future to avoid similar issues.

Thanks,
Lidong

Re: [PATCH v3] pack-bitmap: remove checks before bitmap_free

[Junio C Hamano]

lidongyan <502024330056@smail.nju.edu.cn> writes:

>> Which was where my question came from.
>> 
>> Or perhaps you didn't do that "is my test really tickling the bug I
>> fixed and makes the original code without my fix fail?" test?  Which
>> also explains why lack of "export" was not noticed.
>
> The test case in v0 with “export” would fail, but test-lint in CI shouts. To make
> CI happy, I delete “export” and submit immediately. So I am sure now in
> v3 this test truly test what we want. But I make two mistakes that I haven’t
> pass all CI test before submit. I apologize for the oversight. I'll double-check
> my tests more carefully in the future to avoid similar issues.

Ah, I understood what happened.  No need to apologize.  I just
wanted to know how it was missed, so that we all can learn from
this episode to make sure that our tests do verify what we want
them to.

Thanks.

[PATCH v4] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
use roots_bitmap as a mutable reference but not takes roots_bitmap's
ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
And this leak currently lacks a dedicated test to detect it.

To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
always calling bitmap_free(roots_bitmap);

To trigger this leak, we need a pseudo-merge whose size is equal to
or smaller than roots_bitmap (which corresponds to the set of "haves"
commits in prepare_bitmap_walk()). To do this, we can create two
commits: A and B. Add A to the pseudo-merge list and perform a traversal
over the range A..B. In this scenario, the "haves" set will be {A},
and cascade_pseudo_merges_1() will succeed, thereby exposing the leak
due to the missing roots_bitmap cleanup.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
    pack-bitmap: remove checks before bitmap_free
    
    In pack-bitmap.c:find_boundary_objects, remove cascade success check and
    always free roots_bitmap afterward to make static analysis tool works
    better.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1977%2Fbrandb97%2Fremove-check-before-bitmap-free-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1977/brandb97/remove-check-before-bitmap-free-v4
Pull-Request: https://github.com/git/git/pull/1977

Range-diff vs v3:

 1:  151a7f5dc70 ! 1:  fa443065436 pack-bitmap: remove checks before bitmap_free
     @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'pseudo-merge closure' '
      +		git config bitmapPseudoMerge.test.pattern refs/ &&
      +		git config bitmapPseudoMerge.test.threshold now &&
      +		git config bitmapPseudoMerge.test.stableThreshold now &&
     -+		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 &&
      +
      +		test_commit A &&
      +		git repack -adb &&
      +		test_commit B &&
      +
      +		echo '1' >expect &&
     -+		git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
     ++		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 \
     ++			git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
      +		test_cmp expect actual
      +	)
      +'


 pack-bitmap.c                   |  4 ++--
 t/t5333-pseudo-merge-bitmaps.sh | 20 ++++++++++++++++++++
 2 files changed, 22 insertions(+), 2 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ac6d62b980c..8727f316de9 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
 			bitmap_set(roots_bitmap, pos);
 		}
 
-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
-			bitmap_free(roots_bitmap);
+		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+		bitmap_free(roots_bitmap);
 	}
 
 	/*
diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index 56674db562f..e665001a410 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -445,4 +445,24 @@ test_expect_success 'pseudo-merge closure' '
 	)
 '
 
+test_expect_success 'use pseudo-merge in boundary traversal' '
+	git init pseudo-merge-boundary-traversal &&
+	(
+		cd pseudo-merge-boundary-traversal &&
+
+		git config bitmapPseudoMerge.test.pattern refs/ &&
+		git config bitmapPseudoMerge.test.threshold now &&
+		git config bitmapPseudoMerge.test.stableThreshold now &&
+
+		test_commit A &&
+		git repack -adb &&
+		test_commit B &&
+
+		echo '1' >expect &&
+		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 \
+			git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
+		test_cmp expect actual
+	)
+'
+
 test_done

base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
-- 
gitgitgadget

Re: [PATCH v4] pack-bitmap: remove checks before bitmap_free

[Taylor Blau]

On Tue, Jun 03, 2025 at 06:20:49AM +0000, Lidong Yan via GitGitGadget wrote:
> From: Lidong Yan <502024330056@smail.nju.edu.cn>
>
> In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
> if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
> use roots_bitmap as a mutable reference but not takes roots_bitmap's
> ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
> And this leak currently lacks a dedicated test to detect it.
>
> To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
> always calling bitmap_free(roots_bitmap);

This sentence might be more clear if it were written as:

    To fix this leak, unconditionally free the roots_bitmap regardless
    of whether or not cascade_pseudo_merges_1() succeeds.

> To trigger this leak, we need a pseudo-merge whose size is equal to
> or smaller than roots_bitmap (which corresponds to the set of "haves"
> commits in prepare_bitmap_walk()). To do this, we can create two
> commits: A and B. Add A to the pseudo-merge list and perform a traversal
> over the range A..B. In this scenario, the "haves" set will be {A},
> and cascade_pseudo_merges_1() will succeed, thereby exposing the leak
> due to the missing roots_bitmap cleanup.

I don't think this is quite right. Calling cascade_pseudo_merges_1()
succeeds (and returns a non-zero value) when one or more pseudo-merges
are satisfied. A pseudo-merge is satisfied here when its parents bitmap
is a *subset* of the roots_bitmap, not when it has a smaller size.

The precise definition of one bitmap being a subset of another can be
found in ewah/bitmap.c::ewah_bitamp_is_subset(). But in general one
bitmap is a subset of the other if the set of bit positions with value
"1" from one is a subset of the same set from the other bitmap.

I think that's what you meant by "smaller", but I think it's worth
clarifying here.

> diff --git a/pack-bitmap.c b/pack-bitmap.c
> index ac6d62b980c..8727f316de9 100644
> --- a/pack-bitmap.c
> +++ b/pack-bitmap.c
> @@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
>  			bitmap_set(roots_bitmap, pos);
>  		}
>
> -		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
> -			bitmap_free(roots_bitmap);
> +		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
> +		bitmap_free(roots_bitmap);

Makes sense.

> diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
> index 56674db562f..e665001a410 100755
> --- a/t/t5333-pseudo-merge-bitmaps.sh
> +++ b/t/t5333-pseudo-merge-bitmaps.sh
> @@ -445,4 +445,24 @@ test_expect_success 'pseudo-merge closure' '
>  	)
>  '
>
> +test_expect_success 'use pseudo-merge in boundary traversal' '
> +	git init pseudo-merge-boundary-traversal &&
> +	(
> +		cd pseudo-merge-boundary-traversal &&
> +
> +		git config bitmapPseudoMerge.test.pattern refs/ &&
> +		git config bitmapPseudoMerge.test.threshold now &&

Setting the unstable threshold here should be unnecessary, since the
unstable portion of the group only includes matching commits beyond the
threshold that *don't* already have a bitmap. Since "A" is the only
commit at the time you write the bitmap below, it will always be
selected, and thus never appear in the unstable portion of a
pseudo-merge group.

> +		git config bitmapPseudoMerge.test.stableThreshold now &&

This one is technically unnecessary, but only because test_commit starts
at the $test_tick value, which is very far in the past (beyond the
default value of 1.month.ago).

> +		test_commit A &&
> +		git repack -adb &&
> +		test_commit B &&
> +
> +		echo '1' >expect &&

Please do not use single-quotes in a test script. It happens to work in
this instance, but it is easy to break.

> +		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 \
> +			git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&

This test needs to use the boundary-based bitmap traversal routines, but
I'm unclear on why you're using the GIT_TEST_-environment variable to
enable them.

Is there a reason that we can't rely on the usual repository
configuration here? I would have expected something like this (which
should apply cleanly on top of your patch):

--- 8< ---
diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index e665001a41..491ef404ea 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -453,14 +453,14 @@ test_expect_success 'use pseudo-merge in boundary traversal' '
 		git config bitmapPseudoMerge.test.pattern refs/ &&
 		git config bitmapPseudoMerge.test.threshold now &&
 		git config bitmapPseudoMerge.test.stableThreshold now &&
+		git config pack.useBitmapBoundaryTraversal true &&

 		test_commit A &&
 		git repack -adb &&
 		test_commit B &&

-		echo '1' >expect &&
-		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 \
-			git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
+		echo 1 >expect &&
+		git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
 		test_cmp expect actual
 	)
 '
--- >8 ---

> +		test_cmp expect actual

Hmm. I suppose, although it feels a little clunky to me to write
something like "echo 1 >expect". I would imagine that you'd do something
like:

    test 1 -eq $(git rev-list --count --use-bitmap-index HEAD~1..HEAD)

instead. Or if you wanted to split them off into separate lines, you
could do:

    nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
    test 1 -eq "$nr"

Thanks,
Taylor

Re: [PATCH v4] pack-bitmap: remove checks before bitmap_free

[lidongyan]

> 2025年6月4日 06:09，Taylor Blau <me@ttaylorr.com> 写道：
> 
> On Tue, Jun 03, 2025 at 06:20:49AM +0000, Lidong Yan via GitGitGadget wrote:
>> From: Lidong Yan <502024330056@smail.nju.edu.cn>
>> 
>> In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
>> if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
>> use roots_bitmap as a mutable reference but not takes roots_bitmap's
>> ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
>> And this leak currently lacks a dedicated test to detect it.
>> 
>> To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
>> always calling bitmap_free(roots_bitmap);
> 
> This sentence might be more clear if it were written as:
> 
>    To fix this leak, unconditionally free the roots_bitmap regardless
>    of whether or not cascade_pseudo_merges_1() succeeds.
> 
>> To trigger this leak, we need a pseudo-merge whose size is equal to
>> or smaller than roots_bitmap (which corresponds to the set of "haves"
>> commits in prepare_bitmap_walk()). To do this, we can create two
>> commits: A and B. Add A to the pseudo-merge list and perform a traversal
>> over the range A..B. In this scenario, the "haves" set will be {A},
>> and cascade_pseudo_merges_1() will succeed, thereby exposing the leak
>> due to the missing roots_bitmap cleanup.
> 
> I don't think this is quite right. Calling cascade_pseudo_merges_1()
> succeeds (and returns a non-zero value) when one or more pseudo-merges
> are satisfied. A pseudo-merge is satisfied here when its parents bitmap
> is a *subset* of the roots_bitmap, not when it has a smaller size.
> 
> The precise definition of one bitmap being a subset of another can be
> found in ewah/bitmap.c::ewah_bitamp_is_subset(). But in general one
> bitmap is a subset of the other if the set of bit positions with value
> "1" from one is a subset of the same set from the other bitmap.
> 
> I think that's what you meant by "smaller", but I think it's worth
> clarifying here.

Yes, I want to say subset here, I will rewrite this part of comment.

> 
>> diff --git a/pack-bitmap.c b/pack-bitmap.c
>> index ac6d62b980c..8727f316de9 100644
>> --- a/pack-bitmap.c
>> +++ b/pack-bitmap.c
>> @@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
>> bitmap_set(roots_bitmap, pos);
>> }
>> 
>> - if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
>> - bitmap_free(roots_bitmap);
>> + cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
>> + bitmap_free(roots_bitmap);
> 
> Makes sense.
> 
>> diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
>> index 56674db562f..e665001a410 100755
>> --- a/t/t5333-pseudo-merge-bitmaps.sh
>> +++ b/t/t5333-pseudo-merge-bitmaps.sh
>> @@ -445,4 +445,24 @@ test_expect_success 'pseudo-merge closure' '
>> )
>> '
>> 
>> +test_expect_success 'use pseudo-merge in boundary traversal' '
>> + git init pseudo-merge-boundary-traversal &&
>> + (
>> + cd pseudo-merge-boundary-traversal &&
>> +
>> + git config bitmapPseudoMerge.test.pattern refs/ &&
>> + git config bitmapPseudoMerge.test.threshold now &&
> 
> Setting the unstable threshold here should be unnecessary, since the
> unstable portion of the group only includes matching commits beyond the
> threshold that *don't* already have a bitmap. Since "A" is the only
> commit at the time you write the bitmap below, it will always be
> selected, and thus never appear in the unstable portion of a
> pseudo-merge group.
> 
>> + git config bitmapPseudoMerge.test.stableThreshold now &&
> 
> This one is technically unnecessary, but only because test_commit starts
> at the $test_tick value, which is very far in the past (beyond the
> default value of 1.month.ago).

May be this is the time for me to re-read pseudo-merge documents.

> 
>> + test_commit A &&
>> + git repack -adb &&
>> + test_commit B &&
>> +
>> + echo '1' >expect &&
> 
> Please do not use single-quotes in a test script. It happens to work in
> this instance, but it is easy to break.

Got it.

> 
>> + GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 \
>> + git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
> 
> This test needs to use the boundary-based bitmap traversal routines, but
> I'm unclear on why you're using the GIT_TEST_-environment variable to
> enable them.

I don’t have a special reason to choose GIT_TEST rather than `git config`.
I just find in both way this test works so I use GIT_TEST. I will switch to `git config`.

>  
> Is there a reason that we can't rely on the usual repository
> configuration here? I would have expected something like this (which
> should apply cleanly on top of your patch):
> 
> --- 8< ---
> diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
> index e665001a41..491ef404ea 100755
> --- a/t/t5333-pseudo-merge-bitmaps.sh
> +++ b/t/t5333-pseudo-merge-bitmaps.sh
> @@ -453,14 +453,14 @@ test_expect_success 'use pseudo-merge in boundary traversal' '
> git config bitmapPseudoMerge.test.pattern refs/ &&
> git config bitmapPseudoMerge.test.threshold now &&
> git config bitmapPseudoMerge.test.stableThreshold now &&
> + git config pack.useBitmapBoundaryTraversal true &&
> 
> test_commit A &&
> git repack -adb &&
> test_commit B &&
> 
> - echo '1' >expect &&
> - GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 \
> - git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
> + echo 1 >expect &&
> + git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
> test_cmp expect actual
> )
> '
> --- >8 ---
> 
>> + test_cmp expect actual
> 
> Hmm. I suppose, although it feels a little clunky to me to write
> something like "echo 1 >expect". I would imagine that you'd do something
> like:
> 
>    test 1 -eq $(git rev-list --count --use-bitmap-index HEAD~1..HEAD)
> 
> instead. Or if you wanted to split them off into separate lines, you
> could do:
> 
>    nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
>    test 1 -eq "$nr"
> 

I like the latter one, I will use it in the next series.

Thanks,
Lidong

[PATCH v5] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
use roots_bitmap as a mutable reference but not takes roots_bitmap's
ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
And this leak currently lacks a dedicated test to detect it.

To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
always calling bitmap_free(roots_bitmap);

To trigger this leak, we need roots_bitmap contains at least one pseudo
merge. So that we can use pseudo merge bitmap when we compute roots
reachable bitmap. Here we create two commits: first A then B. Add A
to the pseudo-merge and perform a traversal over the range A..B.
In this scenario, the "haves" set will be {A}, and cascade_pseudo_merges_1
will succeed, thereby exposing the leak due to the missing roots_bitmap
cleanup.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
    pack-bitmap: remove checks before bitmap_free
    
    In pack-bitmap.c:find_boundary_objects, remove cascade success check and
    always free roots_bitmap afterward to make static analysis tool works
    better.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1977%2Fbrandb97%2Fremove-check-before-bitmap-free-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1977/brandb97/remove-check-before-bitmap-free-v5
Pull-Request: https://github.com/git/git/pull/1977

Range-diff vs v4:

 1:  fa443065436 ! 1:  4bc90c83a40 pack-bitmap: remove checks before bitmap_free
     @@ Commit message
          To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
          always calling bitmap_free(roots_bitmap);
      
     -    To trigger this leak, we need a pseudo-merge whose size is equal to
     -    or smaller than roots_bitmap (which corresponds to the set of "haves"
     -    commits in prepare_bitmap_walk()). To do this, we can create two
     -    commits: A and B. Add A to the pseudo-merge list and perform a traversal
     -    over the range A..B. In this scenario, the "haves" set will be {A},
     -    and cascade_pseudo_merges_1() will succeed, thereby exposing the leak
     -    due to the missing roots_bitmap cleanup.
     +    To trigger this leak, we need roots_bitmap contains at least one pseudo
     +    merge. So that we can use pseudo merge bitmap when we compute roots
     +    reachable bitmap. Here we create two commits: first A then B. Add A
     +    to the pseudo-merge and perform a traversal over the range A..B.
     +    In this scenario, the "haves" set will be {A}, and cascade_pseudo_merges_1
     +    will succeed, thereby exposing the leak due to the missing roots_bitmap
     +    cleanup.
      
          Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
      
     @@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'pseudo-merge closure' '
      +		cd pseudo-merge-boundary-traversal &&
      +
      +		git config bitmapPseudoMerge.test.pattern refs/ &&
     -+		git config bitmapPseudoMerge.test.threshold now &&
     -+		git config bitmapPseudoMerge.test.stableThreshold now &&
     ++		git config pack.useBitmapBoundaryTraversal true &&
      +
      +		test_commit A &&
      +		git repack -adb &&
      +		test_commit B &&
      +
     -+		echo '1' >expect &&
     -+		GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 \
     -+			git rev-list --count --use-bitmap-index HEAD~1..HEAD >actual &&
     -+		test_cmp expect actual
     ++		nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
     ++		test 1 -eq "$nr"
      +	)
      +'
      +


 pack-bitmap.c                   |  4 ++--
 t/t5333-pseudo-merge-bitmaps.sh | 17 +++++++++++++++++
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ac6d62b980c..8727f316de9 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
 			bitmap_set(roots_bitmap, pos);
 		}
 
-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
-			bitmap_free(roots_bitmap);
+		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+		bitmap_free(roots_bitmap);
 	}
 
 	/*
diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index 56674db562f..ba5ae6a00c9 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -445,4 +445,21 @@ test_expect_success 'pseudo-merge closure' '
 	)
 '
 
+test_expect_success 'use pseudo-merge in boundary traversal' '
+	git init pseudo-merge-boundary-traversal &&
+	(
+		cd pseudo-merge-boundary-traversal &&
+
+		git config bitmapPseudoMerge.test.pattern refs/ &&
+		git config pack.useBitmapBoundaryTraversal true &&
+
+		test_commit A &&
+		git repack -adb &&
+		test_commit B &&
+
+		nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
+		test 1 -eq "$nr"
+	)
+'
+
 test_done

base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
-- 
gitgitgadget

Re: [PATCH v5] pack-bitmap: remove checks before bitmap_free

[Junio C Hamano]

"Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Lidong Yan <502024330056@smail.nju.edu.cn>
>
> In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
> if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
> use roots_bitmap as a mutable reference but not takes roots_bitmap's
> ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.

"Once cascade_pseudo_merges_1() succeeds", perhaps?

> And this leak currently lacks a dedicated test to detect it.
>
> To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
> always calling bitmap_free(roots_bitmap);
>
> To trigger this leak, we need roots_bitmap contains at least one pseudo
> merge.

"contains" -> "that contains"?

> diff --git a/pack-bitmap.c b/pack-bitmap.c
> index ac6d62b980c..8727f316de9 100644
> --- a/pack-bitmap.c
> +++ b/pack-bitmap.c
> @@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
>  			bitmap_set(roots_bitmap, pos);
>  		}
>  
> -		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
> -			bitmap_free(roots_bitmap);
> +		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
> +		bitmap_free(roots_bitmap);

This makes it as if the original _wanted_ to leak it when the call
failed.  Readers may wonder how we got into this state in the first
place.  Was it a simple thinko when 11d45a6e (pack-bitmap.c: use
pseudo-merges during traversal, 2024-05-23) was written, I have to
wonder.

> diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
> index 56674db562f..ba5ae6a00c9 100755
> --- a/t/t5333-pseudo-merge-bitmaps.sh
> +++ b/t/t5333-pseudo-merge-bitmaps.sh
> @@ -445,4 +445,21 @@ test_expect_success 'pseudo-merge closure' '
>  	)
>  '
>  
> +test_expect_success 'use pseudo-merge in boundary traversal' '
> +	git init pseudo-merge-boundary-traversal &&
> +	(
> +		cd pseudo-merge-boundary-traversal &&
> +
> +		git config bitmapPseudoMerge.test.pattern refs/ &&
> +		git config pack.useBitmapBoundaryTraversal true &&

Yup, this is a temporary repository for only this test, so using
"git config" there makes it the simplest and the easiest to
understand.

> +		test_commit A &&
> +		git repack -adb &&
> +		test_commit B &&
> +
> +		nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
> +		test 1 -eq "$nr"
> +	)
> +'
> +
>  test_done
>
> base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229

Re: [PATCH v5] pack-bitmap: remove checks before bitmap_free

[lidongyan]

Junio C Hamano <gitster@pobox.com> 写道：
> 
> "Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> From: Lidong Yan <502024330056@smail.nju.edu.cn>
>> 
>> In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
>> if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
>> use roots_bitmap as a mutable reference but not takes roots_bitmap's
>> ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
> 
> "Once cascade_pseudo_merges_1() succeeds", perhaps?
> 
>> And this leak currently lacks a dedicated test to detect it.
>> 
>> To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
>> always calling bitmap_free(roots_bitmap);
>> 
>> To trigger this leak, we need roots_bitmap contains at least one pseudo
>> merge.
> 
> "contains" -> "that contains"?
> 
>> diff --git a/pack-bitmap.c b/pack-bitmap.c
>> index ac6d62b980c..8727f316de9 100644
>> --- a/pack-bitmap.c
>> +++ b/pack-bitmap.c
>> @@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
>> bitmap_set(roots_bitmap, pos);
>> }
>> 
>> - if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
>> - bitmap_free(roots_bitmap);
>> + cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
>> + bitmap_free(roots_bitmap);
> 
> This makes it as if the original _wanted_ to leak it when the call
> failed.  Readers may wonder how we got into this state in the first
> place.  Was it a simple thinko when 11d45a6e (pack-bitmap.c: use
> pseudo-merges during traversal, 2024-05-23) was written, I have to
> wonder.

I think this was a simple thinko, similar to "we need to free resources if
something fails. Since cascade_pseudo_merges_1() fails, we need to free roots_bitmap”.
In commit 55e563a (pseudo-merge: fix various memory leaks, 2024-09-30),
Patrick fixed a similar leak in find_objects(). However, since t5333 doesn’t
test boundary traversal, the leak in find_boundary_objects() remains unresolved.

[PATCH v6] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
use roots_bitmap as a mutable reference but not takes roots_bitmap's
ownership. Once cascade_pseudo_merges_1() succeeds, roots_bitmap leaks.
And this leak currently lacks a dedicated test to detect it.

To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
always calling bitmap_free(roots_bitmap);

To trigger this leak, we need roots_bitmap that contains at least one
pseudo merge. So that we can use pseudo merge bitmap when we compute roots
reachable bitmap. Here we create two commits: first A then B. Add A
to the pseudo-merge and perform a traversal over the range A..B.
In this scenario, the "haves" set will be {A}, and cascade_pseudo_merges_1
will succeed, thereby exposing the leak due to the missing roots_bitmap
cleanup.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
    pack-bitmap: remove checks before bitmap_free
    
    In pack-bitmap.c:find_boundary_objects, remove cascade success check and
    always free roots_bitmap afterward to make static analysis tool works
    better.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1977%2Fbrandb97%2Fremove-check-before-bitmap-free-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1977/brandb97/remove-check-before-bitmap-free-v6
Pull-Request: https://github.com/git/git/pull/1977

Range-diff vs v5:

 1:  4bc90c83a40 ! 1:  43cdce190dc pack-bitmap: remove checks before bitmap_free
     @@ Commit message
          In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
          if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
          use roots_bitmap as a mutable reference but not takes roots_bitmap's
     -    ownership. Once cascade_pseudo_merges_1 succeed(), roots_bitmap leaks.
     +    ownership. Once cascade_pseudo_merges_1() succeeds, roots_bitmap leaks.
          And this leak currently lacks a dedicated test to detect it.
      
          To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
          always calling bitmap_free(roots_bitmap);
      
     -    To trigger this leak, we need roots_bitmap contains at least one pseudo
     -    merge. So that we can use pseudo merge bitmap when we compute roots
     +    To trigger this leak, we need roots_bitmap that contains at least one
     +    pseudo merge. So that we can use pseudo merge bitmap when we compute roots
          reachable bitmap. Here we create two commits: first A then B. Add A
          to the pseudo-merge and perform a traversal over the range A..B.
          In this scenario, the "haves" set will be {A}, and cascade_pseudo_merges_1


 pack-bitmap.c                   |  4 ++--
 t/t5333-pseudo-merge-bitmaps.sh | 17 +++++++++++++++++
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ac6d62b980c..8727f316de9 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
 			bitmap_set(roots_bitmap, pos);
 		}
 
-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
-			bitmap_free(roots_bitmap);
+		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+		bitmap_free(roots_bitmap);
 	}
 
 	/*
diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index 56674db562f..ba5ae6a00c9 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -445,4 +445,21 @@ test_expect_success 'pseudo-merge closure' '
 	)
 '
 
+test_expect_success 'use pseudo-merge in boundary traversal' '
+	git init pseudo-merge-boundary-traversal &&
+	(
+		cd pseudo-merge-boundary-traversal &&
+
+		git config bitmapPseudoMerge.test.pattern refs/ &&
+		git config pack.useBitmapBoundaryTraversal true &&
+
+		test_commit A &&
+		git repack -adb &&
+		test_commit B &&
+
+		nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
+		test 1 -eq "$nr"
+	)
+'
+
 test_done

base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
-- 
gitgitgadget

Re: [PATCH v6] pack-bitmap: remove checks before bitmap_free

[Junio C Hamano]

"Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Lidong Yan <502024330056@smail.nju.edu.cn>
>
> In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
> if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
> use roots_bitmap as a mutable reference but not takes roots_bitmap's
> ownership.

Sorry but I cannot parse the last sentence above.  I would have
expected that "Since/Because X" to be followed by comma and a
sentence that describes the consequence of X.  Also "but not takes"
-> "but does not take", probably.

Re: [PATCH v6] pack-bitmap: remove checks before bitmap_free

[lidongyan]

2025年6月6日 09:28，Junio C Hamano <gitster@pobox.com> 写道：
> 
> "Lidong Yan via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> From: Lidong Yan <502024330056@smail.nju.edu.cn>
>> 
>> In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
>> if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
>> use roots_bitmap as a mutable reference but not takes roots_bitmap's
>> ownership.
> 
> Sorry but I cannot parse the last sentence above.  I would have
> expected that "Since/Because X" to be followed by comma and a
> sentence that describes the consequence of X.  Also "but not takes"
> -> "but does not take", probably.


You are right, I should use a grammar checker (chatgpt) on my log message.
How about
“
Since cascade_pseudo_merges_1() only
use roots_bitmap as a mutable reference but not takes roots_bitmap's
ownership. Once cascade_pseudo_merges_1() succeeds, roots_bitmap leaks.
”
->
“
However, cascade_pseudo_merges_1() uses roots_bitmap as a 
mutable reference without taking ownership of it. As a result, if 
cascade_pseudo_merges_1() succeeds, roots_bitmap is leaked.
”

[PATCH v7] pack-bitmap: remove checks before bitmap_free

[Lidong Yan via GitGitGadget]

From: Lidong Yan <502024330056@smail.nju.edu.cn>

In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
if cascade_pseudo_merges_1() fails. However, cascade_pseudo_merges_1()
uses roots_bitmap as a mutable reference without taking ownership of it.
As a result, if cascade_pseudo_merges_1() succeeds, roots_bitmap is leaked.
And this leak currently lacks a dedicated test to detect it.

To fix this leak, remove if cascade_pseudo_merges_1() succeed check and
always calling bitmap_free(roots_bitmap);

To trigger this leak, we need roots_bitmap that contains at least one
pseudo merge. So that we can use pseudo merge bitmap when we compute roots
reachable bitmap. Here we create two commits: first A then B. Add A
to the pseudo-merge and perform a traversal over the range A..B.
In this scenario, the "haves" set will be {A}, and cascade_pseudo_merges_1
will succeed, thereby exposing the leak due to the missing roots_bitmap
cleanup.

Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
---
    pack-bitmap: remove checks before bitmap_free
    
    In pack-bitmap.c:find_boundary_objects, remove cascade success check and
    always free roots_bitmap afterward to make static analysis tool works
    better.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1977%2Fbrandb97%2Fremove-check-before-bitmap-free-v7
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1977/brandb97/remove-check-before-bitmap-free-v7
Pull-Request: https://github.com/git/git/pull/1977

Range-diff vs v6:

 1:  43cdce190dc ! 1:  74c41eccfb0 pack-bitmap: remove checks before bitmap_free
     @@ Commit message
          pack-bitmap: remove checks before bitmap_free
      
          In pack-bitmap.c:find_boundary_objects(), the roots_bitmap is only freed
     -    if cascade_pseudo_merges_1() fails. Since cascade_pseudo_merges_1() only
     -    use roots_bitmap as a mutable reference but not takes roots_bitmap's
     -    ownership. Once cascade_pseudo_merges_1() succeeds, roots_bitmap leaks.
     +    if cascade_pseudo_merges_1() fails. However, cascade_pseudo_merges_1()
     +    uses roots_bitmap as a mutable reference without taking ownership of it.
     +    As a result, if cascade_pseudo_merges_1() succeeds, roots_bitmap is leaked.
          And this leak currently lacks a dedicated test to detect it.
      
          To fix this leak, remove if cascade_pseudo_merges_1() succeed check and


 pack-bitmap.c                   |  4 ++--
 t/t5333-pseudo-merge-bitmaps.sh | 17 +++++++++++++++++
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index ac6d62b980c..8727f316de9 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1363,8 +1363,8 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
 			bitmap_set(roots_bitmap, pos);
 		}
 
-		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
-			bitmap_free(roots_bitmap);
+		cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap);
+		bitmap_free(roots_bitmap);
 	}
 
 	/*
diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh
index 56674db562f..ba5ae6a00c9 100755
--- a/t/t5333-pseudo-merge-bitmaps.sh
+++ b/t/t5333-pseudo-merge-bitmaps.sh
@@ -445,4 +445,21 @@ test_expect_success 'pseudo-merge closure' '
 	)
 '
 
+test_expect_success 'use pseudo-merge in boundary traversal' '
+	git init pseudo-merge-boundary-traversal &&
+	(
+		cd pseudo-merge-boundary-traversal &&
+
+		git config bitmapPseudoMerge.test.pattern refs/ &&
+		git config pack.useBitmapBoundaryTraversal true &&
+
+		test_commit A &&
+		git repack -adb &&
+		test_commit B &&
+
+		nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
+		test 1 -eq "$nr"
+	)
+'
+
 test_done

base-commit: 845c48a16a7f7b2c44d8cb137b16a4a1f0140229
-- 
gitgitgadget