Fix a couple small leaks in merge-ort

From: Elijah Newren <[email protected]>

detect_and_process_renames() detects renames on both sides of history and then combines these into a single diff_queue_struct. The combined diff_queue_struct needs to be able to hold the renames found on either side, and since it knows the (maximum) size it needs, it pre-emptively grows the array to the appropriate size:

	ALLOC_GROW(combined.queue,
		   renames->pairs[1].nr + renames->pairs[2].nr,
		   combined.alloc);

It then collects the items from each side:

collect_renames(opt, &combined, MERGE_SIDE1, ...) collect_renames(opt, &combined, MERGE_SIDE2, ...)

Note, though, that collect_renames() sometimes determines that some pairs are unnecessary and does not include them in the combined array. When it is done, detect_and_process_renames() frees this memory:

	if (combined.nr) {
                ...
		free(combined.queue);
        }

The problem is that sometimes even when there are pairs, none of them are necessary. Instead of checking combined.nr, we should check combined.alloc. Doing so fixes the following memory leak, as reported by valgrind:

==PID== 192 bytes in 1 blocks are definitely lost in loss record 107 of 134

==PID==    at 0xADDRESS: malloc
==PID==    by 0xADDRESS: realloc
==PID==    by 0xADDRESS: xrealloc (wrapper.c:126)
==PID==    by 0xADDRESS: detect_and_process_renames (merge-ort.c:3134)
==PID==    by 0xADDRESS: merge_ort_nonrecursive_internal (merge-ort.c:4610)
==PID==    by 0xADDRESS: merge_ort_internal (merge-ort.c:4709)
==PID==    by 0xADDRESS: merge_incore_recursive (merge-ort.c:4760)
==PID==    by 0xADDRESS: merge_ort_recursive (merge-ort-wrappers.c:57)
==PID==    by 0xADDRESS: try_merge_strategy (merge.c:753)
==PID==    by 0xADDRESS: cmd_merge (merge.c:1676)
==PID==    by 0xADDRESS: run_builtin (git.c:461)
==PID==    by 0xADDRESS: handle_builtin (git.c:713)
==PID==    by 0xADDRESS: run_argv (git.c:780)
==PID==    by 0xADDRESS: cmd_main (git.c:911)
==PID==    by 0xADDRESS: main (common-main.c:52)

Reported-by Ævar Arnfjörð Bjarmason <[email protected]>

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

merge-ort.c +0 -0

index d85b1cd99e9..4f5abc558c5 100644

Quoted 59 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

detect_and_process_renames() detects renames on both sides of history and then combines these into a single diff_queue_struct. The combined diff_queue_struct needs to be able to hold the renames found on either side, and since it knows the (maximum) size it needs, it pre-emptively grows the array to the appropriate size:

      ALLOC_GROW(combined.queue,
                 renames->pairs[1].nr + renames->pairs[2].nr,
                 combined.alloc);

It then collects the items from each side:

collect_renames(opt, &combined, MERGE_SIDE1, ...) collect_renames(opt, &combined, MERGE_SIDE2, ...)

Note, though, that collect_renames() sometimes determines that some pairs are unnecessary and does not include them in the combined array. When it is done, detect_and_process_renames() frees this memory:

      if (combined.nr) {
                ...
              free(combined.queue);
        }

The problem is that sometimes even when there are pairs, none of them are necessary. Instead of checking combined.nr, we should check combined.alloc. Doing so fixes the following memory leak, as reported by valgrind:

==PID== 192 bytes in 1 blocks are definitely lost in loss record 107 of 134

==PID==    at 0xADDRESS: malloc
==PID==    by 0xADDRESS: realloc
==PID==    by 0xADDRESS: xrealloc (wrapper.c:126)
==PID==    by 0xADDRESS: detect_and_process_renames (merge-ort.c:3134)
==PID==    by 0xADDRESS: merge_ort_nonrecursive_internal (merge-ort.c:4610)
==PID==    by 0xADDRESS: merge_ort_internal (merge-ort.c:4709)
==PID==    by 0xADDRESS: merge_incore_recursive (merge-ort.c:4760)
==PID==    by 0xADDRESS: merge_ort_recursive (merge-ort-wrappers.c:57)
==PID==    by 0xADDRESS: try_merge_strategy (merge.c:753)
==PID==    by 0xADDRESS: cmd_merge (merge.c:1676)
==PID==    by 0xADDRESS: run_builtin (git.c:461)
==PID==    by 0xADDRESS: handle_builtin (git.c:713)
==PID==    by 0xADDRESS: run_argv (git.c:780)
==PID==    by 0xADDRESS: cmd_main (git.c:911)
==PID==    by 0xADDRESS: main (common-main.c:52)

Reported-by Ævar Arnfjörð Bjarmason <[email protected]>

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

merge-ort.c +0 -0

index d85b1cd99e9..4f5abc558c5 100644

merge-ort.c simple_cleanup: · line 3181

Quoted 8 lines

merge-ort.c +1 -1

@@ -3175,7 +3175,7 @@ simple_cleanup:
              free(renames->pairs[s].queue);
              DIFF_QUEUE_CLEAR(&renames->pairs[s]);
      }
-     if (combined.nr) {
+     if (combined.alloc) {
              int i;
              for (i = 0; i < combined.nr; i++)
                      pool_diff_free_filepair(&opt->priv->pool,

This looks correct in that it'll work, but I still don't get why the pre-image or post-image is going through this indirection of checking "alloc" at all. Wouldn't this be correct & more straightforward (the memset part is optional, just did it for good measure)?:

merge-ort.c +2 -6

index 40ae4dc4e92..a01f28586a1 100644
@@ -3092,12 +3092,12 @@ static int detect_and_process_renames(struct merge_options *opt,
                                      struct tree *side1,
                                      struct tree *side2)
 {
-       struct diff_queue_struct combined;
+       struct diff_queue_struct combined = { 0 };
        struct rename_info *renames = &opt->priv->renames;
        int need_dir_renames, s, clean = 1;
        unsigned detection_run = 0;
+       int i;
 
-       memset(&combined, 0, sizeof(combined));
        if (!possible_renames(renames))
                goto cleanup;
 

@@ -3181,13 +3181,10 @@ static int detect_and_process_renames(struct merge_options *opt,
                free(renames->pairs[s].queue);
                DIFF_QUEUE_CLEAR(&renames->pairs[s]);
        }
-       if (combined.alloc) {
-               int i;
-               for (i = 0; i < combined.nr; i++)
-                       pool_diff_free_filepair(&opt->priv->pool,

From: Elijah Newren <[email protected]>

The struct strmap paths member of merge_options_internal is perhaps the most central data structure to all of merge-ort. Because all the paths involved in the merge need to be kept until the merge is complete, this "paths" data structure traditionally took responsibility for owning all the allocated paths. When the merge is over, those paths were free()d as part of free()ing this strmap.

In commit 6697ee01b5d3 (merge-ort: switch our strmaps over to using memory pools, 2021-07-30), we changed the allocations for pathnames to come from a memory pool. That meant the ownership changed slightly; there were no individual free() calls to make, instead the memory pool owned all those paths and they were free()d all at once.

Unfortunately unique_path() was written presuming the pre-memory-pool model, and allocated a path on the heap and left it in the strmap for later free()ing. Modify it to return a path allocated from the memory pool instead.

Quoted 15 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

The struct strmap paths member of merge_options_internal is perhaps the most central data structure to all of merge-ort. Because all the paths involved in the merge need to be kept until the merge is complete, this "paths" data structure traditionally took responsibility for owning all the allocated paths. When the merge is over, those paths were free()d as part of free()ing this strmap.

In commit 6697ee01b5d3 (merge-ort: switch our strmaps over to using memory pools, 2021-07-30), we changed the allocations for pathnames to come from a memory pool. That meant the ownership changed slightly; there were no individual free() calls to make, instead the memory pool owned all those paths and they were free()d all at once.

Quoted 4 lines

Unfortunately unique_path() was written presuming the pre-memory-pool model, and allocated a path on the heap and left it in the strmap for later free()ing. Modify it to return a path allocated from the memory pool instead.

This seems like a rather obvious fix to the leak, as the other side wasn't ready to have the detached strbuf handed to it, and instead is assuming everything is mempools.

The downside is a bit of heap churn here since you malloc() & use the strbuf just to ask for that size from the mempool, and then free() the strbuf (of course we had that before, we just weren't free-ing).

So this is just an aside & I have no idea if it's worth it, but FWIW you can have your cake & eat it too here memory-allocation wise and avoid the strbuf allocation entirely, and just use your mem-pool.

Like this:

merge-ort.c +14 -4

index 40ae4dc4e92..1111916d5cb 100644
@@ -731,6 +731,16 @@ static char *unique_path(struct merge_options *opt,
        int suffix = 0;
        size_t base_len;
        struct strmap *existing_paths = &opt->priv->paths;
+       /*
+        * pre-size path + ~ + branch + _%d + "\0". Hopefully 6 digits
+        * of suffix is enough for everyone?
+        */
+       const size_t max_suffix = 6;
+       const size_t expected_len = strlen(path) + 1 + strlen(branch) + 1 +
+               max_suffix + 1;
+
+       ret = mem_pool_alloc(&opt->priv->pool, expected_len);
+       strbuf_attach(&newpath, ret, 0, expected_len);
 
        strbuf_addf(&newpath, "%s~", path);
        add_flattened_path(&newpath, branch);

@@ -741,10 +751,10 @@ static char *unique_path(struct merge_options *opt,
                strbuf_addf(&newpath, "_%d", suffix++);
        }
 
-       /* Track the new path in our memory pool */
-       ret = mem_pool_alloc(&opt->priv->pool, newpath.len + 1);
-       memcpy(ret, newpath.buf, newpath.len + 1);
-       strbuf_release(&newpath);
+       if (newpath.alloc > expected_len)
+               BUG("we assumed too much thinking '%s~%s' would fit in %lu, ended up %lu ('%s')",
+                   path, branch, expected_len, newpath.alloc, newpath.buf);
+
        return ret;
 }
 

A bit nasty for sure, but if you're willing to BUG() out if we ever go above 999999 suffix tries or whatever (which would be trivial to add to the loop there) it's rather straightforward.

I.e. we know the size of the buffer ahead of time, except for that loop that'll add "_%d" to the end, and that can be made bounded.

Obviously your solution's a lot simpler, so I think this is only something you should consider if you think it matters for the performance numbers linked to from 6697ee01b5d3. I'm not familiar enough with merge-ort.c to know if it is in this case, or if this would be pointless micro-optimization on a non-hot codepath.

 merge-ort.c | 15 +++++----------
 1 file changed, 5 insertions(+), 10 deletions(-)

Quoted 2 lines · Elijah Newren via GitGitGadget

 merge-ort.c | 15 +++++----------
 1 file changed, 5 insertions(+), 10 deletions(-)

Both versions of this patch look good to me (in fact, I appreciated seeing both v1 and v2, since v1 makes it more obvious what is changing, but v2 does the whole thing in a little bit of a cleaner way).

Quoted 10 lines

merge-ort.c +1 -1

index d85b1cd99e9..3d7f9feb6f7 100644
@@ -3086,12 +3086,11 @@ static int detect_and_process_renames(struct merge_options *opt,
                                    struct tree *side1,
                                    struct tree *side2)
 {
-     struct diff_queue_struct combined;
+     struct diff_queue_struct combined = { 0 };

merge-ort.c static int detect_and_process_renames(struct merge_options *opt, · line 3091

Quoted 3 lines

merge-ort.c +1 -1

      struct rename_info *renames = &opt->priv->renames;
-     int need_dir_renames, s, clean = 1;
+     int need_dir_renames, s, i, clean = 1;

And this entire patch looks good to me, but I did wonder about why "i" is an int here. Shouldn't it be a size_t instead? Looking at diff_queue_struct's definition, both "alloc" and "nr" are signed ints, when they should almost certainly be unsigned to avoid overflow.

From: Elijah Newren <[email protected]>

detect_and_process_renames() detects renames on both sides of history and then combines these into a single diff_queue_struct. The combined diff_queue_struct needs to be able to hold the renames found on either side, and since it knows the (maximum) size it needs, it pre-emptively grows the array to the appropriate size:

	ALLOC_GROW(combined.queue,
		   renames->pairs[1].nr + renames->pairs[2].nr,
		   combined.alloc);

It then collects the items from each side:

collect_renames(opt, &combined, MERGE_SIDE1, ...) collect_renames(opt, &combined, MERGE_SIDE2, ...)

Note, though, that collect_renames() sometimes determines that some pairs are unnecessary and does not include them in the combined array. When it is done, detect_and_process_renames() frees this memory:

	if (combined.nr) {
                ...
		free(combined.queue);
        }

The problem is that sometimes even when there are pairs, none of them are necessary. Instead of checking combined.nr, just remove the if-check; free() knows to skip NULL pointers. This change fixes the following memory leak, as reported by valgrind:

==PID== 192 bytes in 1 blocks are definitely lost in loss record 107 of 134

==PID==    at 0xADDRESS: malloc
==PID==    by 0xADDRESS: realloc
==PID==    by 0xADDRESS: xrealloc (wrapper.c:126)
==PID==    by 0xADDRESS: detect_and_process_renames (merge-ort.c:3134)
==PID==    by 0xADDRESS: merge_ort_nonrecursive_internal (merge-ort.c:4610)
==PID==    by 0xADDRESS: merge_ort_internal (merge-ort.c:4709)
==PID==    by 0xADDRESS: merge_incore_recursive (merge-ort.c:4760)
==PID==    by 0xADDRESS: merge_ort_recursive (merge-ort-wrappers.c:57)
==PID==    by 0xADDRESS: try_merge_strategy (merge.c:753)
==PID==    by 0xADDRESS: cmd_merge (merge.c:1676)
==PID==    by 0xADDRESS: run_builtin (git.c:461)
==PID==    by 0xADDRESS: handle_builtin (git.c:713)
==PID==    by 0xADDRESS: run_argv (git.c:780)
==PID==    by 0xADDRESS: cmd_main (git.c:911)
==PID==    by 0xADDRESS: main (common-main.c:52)

Reported-by Ævar Arnfjörð Bjarmason <[email protected]>

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c | 15 +++++----------
 1 file changed, 5 insertions(+), 10 deletions(-)

merge-ort.c +5 -10

index d85b1cd99e9..3d7f9feb6f7 100644
@@ -3086,12 +3086,11 @@ static int detect_and_process_renames(struct merge_options *opt,
 				      struct tree *side1,
 				      struct tree *side2)
 {
-	struct diff_queue_struct combined;
+	struct diff_queue_struct combined = { 0 };
 	struct rename_info *renames = &opt->priv->renames;
-	int need_dir_renames, s, clean = 1;
+	int need_dir_renames, s, i, clean = 1;
 	unsigned detection_run = 0;
 
-	memset(&combined, 0, sizeof(combined));
 	if (!possible_renames(renames))
 		goto cleanup;
 

@@ -3175,13 +3174,9 @@ simple_cleanup:
 		free(renames->pairs[s].queue);
 		DIFF_QUEUE_CLEAR(&renames->pairs[s]);
 	}
-	if (combined.nr) {
-		int i;
-		for (i = 0; i < combined.nr; i++)
-			pool_diff_free_filepair(&opt->priv->pool,
-						combined.queue[i]);
-		free(combined.queue);
-	}
+	for (i = 0; i < combined.nr; i++)
+		pool_diff_free_filepair(&opt->priv->pool, combined.queue[i]);
+	free(combined.queue);
 
 	return clean;
 }

From: Elijah Newren <[email protected]>

detect_and_process_renames() detects renames on both sides of history and then combines these into a single diff_queue_struct. The combined diff_queue_struct needs to be able to hold the renames found on either side, and since it knows the (maximum) size it needs, it pre-emptively grows the array to the appropriate size:
[...]

merge-ort.c +2 -6

index d85b1cd99e9..3d7f9feb6f7 100644
@@ -3086,12 +3086,11 @@ static int detect_and_process_renames(struct merge_options *opt,
 				      struct tree *side1,
 				      struct tree *side2)
 {
-	struct diff_queue_struct combined;
+	struct diff_queue_struct combined = { 0 };
 	struct rename_info *renames = &opt->priv->renames;
-	int need_dir_renames, s, clean = 1;
+	int need_dir_renames, s, i, clean = 1;
 	unsigned detection_run = 0;
 
-	memset(&combined, 0, sizeof(combined));
 	if (!possible_renames(renames))
 		goto cleanup;
 

@@ -3175,13 +3174,9 @@ simple_cleanup:
 		free(renames->pairs[s].queue);
 		DIFF_QUEUE_CLEAR(&renames->pairs[s]);
 	}
-	if (combined.nr) {
-		int i;
-		for (i = 0; i < combined.nr; i++)

Off-list, Ævar reported a few small leaks in merge-ort to me that I missed previously. Here's a couple fixes.

Changes since v1:

* Simplified patch 1 a bit as per Ævar's suggestion