pack-bitmap: remove checks before bitmap_free

From: Lidong Yan <[email protected]>

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.

---
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(-)

index ac6d62b980c..8727f316de9 100644
@@ -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

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.

    `cascade_pseudo_merges()`.

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

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).

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

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.

-: ----------- > 2: 56b24d681cb t5333: test memory leak when use pseudo-merge in boundary traversal

gitgitgadget

From: Lidong Yan <[email protected]>

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.

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

index ac6d62b980c5..8727f316de92 100644
@@ -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

From: Lidong Yan <[email protected]>

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.

---
 t/t5333-pseudo-merge-bitmaps.sh | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

index 56674db562f9..5e263fce50a7 100755
@@ -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

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 &&

Thanks, I should run this before submit.

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.

From: Lidong Yan <[email protected]>

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.

---
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 <[email protected]>

## 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.

+ ## 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(-)

index ac6d62b980c..8727f316de9 100644
@@ -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);
 	}
 
 	/*

index 56674db562f..454f8c7a817 100755
@@ -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

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?

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

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.

From: Lidong Yan <[email protected]>

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.

---
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(-)

index ac6d62b980c..8727f316de9 100644
@@ -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);
 	}
 
 	/*

index 56674db562f..e665001a410 100755
@@ -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

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.

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.

index e665001a41..491ef404ea 100755
@@ -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
 	)
 '

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

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

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

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

Got it.

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.

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

Thanks,
Lidong

From: Lidong Yan <[email protected]>

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.

---
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 <[email protected]>
      
     @@ 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(-)

index ac6d62b980c..8727f316de9 100644
@@ -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);
 	}
 
 	/*

index 56674db562f..ba5ae6a00c9 100755
@@ -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

"Once cascade_pseudo_merges_1() succeeds", perhaps?

"contains" -> "that contains"?

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.

From: Lidong Yan <[email protected]>

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.

---
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(-)

index ac6d62b980c..8727f316de9 100644
@@ -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);
 	}
 
 	/*

index 56674db562f..ba5ae6a00c9 100755
@@ -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

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.
”

From: Lidong Yan <[email protected]>

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.

---
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(-)

index ac6d62b980c..8727f316de9 100644
@@ -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);
 	}
 
 	/*

index 56674db562f..ba5ae6a00c9 100755
@@ -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