malloc memory corruption on merge-tree with leading newline

malloc memory corruption on merge-tree with leading newline

[Stefan Frühwirth]

Hi,

in one specific circumstance, git-merge-tree exits with a segfault 
caused by "*** Error in `git': malloc(): memory corruption (fast)":

There has to be at least one commit first (as far as I can tell it 
doesn't matter what content). Then create a tree containing a file with 
a leading newline character (\n) followed by some random string, and 
another tree with a file containing a string without leading newline. 
Now merge trees: Segmentation fault.

There is a test case[1] kindly provided by chrisrossi, which he crafted 
after I discovered the problem[2] in the context of Pylons/acidfs.

Best,
Stefan

[1] https://gist.github.com/chrisrossi/f09c8bed70b364f9f12e
[2] https://github.com/Pylons/acidfs/issues/3

For in-line reference, here's the test case:

git init bug
cd bug
echo b > a
git add a
git commit -m "first commit"
echo > b
echo -n a >> b
git add b
git commit -m "second commit, first branch"
git checkout HEAD~1
git checkout -b other
echo -n a > b
git add b
git commit -m "second commit, second branch"
git merge-tree HEAD~1 master other
cd ..
rm -rf bug

Re: malloc memory corruption on merge-tree with leading newline

[Stefan Frühwirth]

Addendum: Problem occurs with version 2.7.1 as well as version 1.9.1.

On 15/02/16 22:39, Stefan Frühwirth wrote:

> in one specific circumstance, git-merge-tree exits with a segfault
> caused by "*** Error in `git': malloc(): memory corruption (fast)":

Stefan

[PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Jeff King]

On Mon, Feb 15, 2016 at 10:39:39PM +0100, Stefan Frühwirth wrote:

> in one specific circumstance, git-merge-tree exits with a segfault caused by
> "*** Error in `git': malloc(): memory corruption (fast)":
> 
> There has to be at least one commit first (as far as I can tell it doesn't
> matter what content). Then create a tree containing a file with a leading
> newline character (\n) followed by some random string, and another tree with
> a file containing a string without leading newline. Now merge trees:
> Segmentation fault.
> 
> There is a test case[1] kindly provided by chrisrossi, which he crafted
> after I discovered the problem[2] in the context of Pylons/acidfs.

Wow, I had to look up what "git merge-tree" even is. It looks like a
proof-of-concept added by 492e075 (Handling large files with GIT,
2006-02-14) that has somehow hung around forever.

I find some of the merging code there questionable, and I wonder if
people are actually using it.  And yet there is this report, and it has
received one or two fixes over the years. So maybe people are.

Anyway, here is an immediate fix for the memory corruption. I'm pretty
sure the _result_ is still buggy in this case, as explained below. I
suspect this weird add/add case should just be a full conflict (like it
is for the normal merge code), and we should just be using ll_merge()
directly. But I have to admit I have very little desire to think hard on
this crufty code. My first preference would be to remove it, but I don't
want to hurt people who might actually be using it. But they can do
their own hard-thinking.

-- >8 --
Subject: merge_blobs: use strbuf instead of manually-sized mmfile_t

The ancient merge_blobs function (which is used nowhere
except in the equally ancient git-merge-tree, which does
not itself seem to be called by any modern git code), tries
to create a plausible base object for an add/add conflict by
finding the common parts of the "ours" and "theirs" blobs.
It does so by calling xdiff with XDIFF_EMIT_COMMON, and
stores the result in a buffer that is as big as the smaller
of "ours" and "theirs".

In theory, this is right; we cannot have more common content
than is in the smaller of the two blobs. But in practice,
xdiff may give us more: if neither file ends in a newline,
we get the "\nNo newline at end of file" marker.

This is somewhat of a bug in itself (the "no newline" string
becomes part of the blob output!), but much worse is that we
may overflow our output buffer with this string (if the
common content was otherwise close to the size of the
smaller blob).

The minimal fix for the memory corruption is to size the
buffer appropriately. We could do so by manually adding in
an extra 29 bytes for the "no newline" string to our buffer
size. But that's somewhat fragile. Instead, let's replace
the fixed-size output buffer with a strbuf which can grow as
necessary.

Reported-by: Stefan Frühwirth <stefan.fruehwirth@uni-graz.at>
Signed-off-by: Jeff King <peff@peff.net>
---
 merge-blobs.c | 23 ++++++++++++-----------
 1 file changed, 12 insertions(+), 11 deletions(-)

diff --git a/merge-blobs.c b/merge-blobs.c
index ddca601..acfd110 100644
--- a/merge-blobs.c
+++ b/merge-blobs.c
@@ -51,19 +51,16 @@ static void *three_way_filemerge(const char *path, mmfile_t *base, mmfile_t *our
 static int common_outf(void *priv_, mmbuffer_t *mb, int nbuf)
 {
 	int i;
-	mmfile_t *dst = priv_;
+	struct strbuf *dst = priv_;
 
-	for (i = 0; i < nbuf; i++) {
-		memcpy(dst->ptr + dst->size, mb[i].ptr, mb[i].size);
-		dst->size += mb[i].size;
-	}
+	for (i = 0; i < nbuf; i++)
+		strbuf_add(dst, mb[i].ptr, mb[i].size);
 	return 0;
 }
 
 static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)
 {
-	unsigned long size = f1->size < f2->size ? f1->size : f2->size;
-	void *ptr = xmalloc(size);
+	struct strbuf out = STRBUF_INIT;
 	xpparam_t xpp;
 	xdemitconf_t xecfg;
 	xdemitcb_t ecb;
@@ -75,11 +72,15 @@ static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)
 	xecfg.flags = XDL_EMIT_COMMON;
 	ecb.outf = common_outf;
 
-	res->ptr = ptr;
-	res->size = 0;
+	ecb.priv = &out;
+	if (xdi_diff(f1, f2, &xpp, &xecfg, &ecb) < 0) {
+		strbuf_release(&out);
+		return -1;
+	}
 
-	ecb.priv = res;
-	return xdi_diff(f1, f2, &xpp, &xecfg, &ecb);
+	res->size = out.len; /* avoid long/size_t pointer mismatch below */
+	res->ptr = strbuf_detach(&out, NULL);
+	return 0;
 }
 
 void *merge_blobs(const char *path, struct blob *base, struct blob *our, struct blob *their, unsigned long *size)
-- 
2.7.1.574.gccd43a9

Re: [PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Eric Sunshine]

On Mon, Feb 15, 2016 at 08:12:58PM -0500, Jeff King wrote:
> On Mon, Feb 15, 2016 at 10:39:39PM +0100, Stefan Frühwirth wrote:
> > in one specific circumstance, git-merge-tree exits with a segfault caused by
> > "*** Error in `git': malloc(): memory corruption (fast)":
> > 
> > There is a test case[1] kindly provided by chrisrossi, which he crafted
> > after I discovered the problem[2] in the context of Pylons/acidfs.
> 
> -- >8 --
> Subject: merge_blobs: use strbuf instead of manually-sized mmfile_t
> 
> [...]
> It does so by calling xdiff with XDIFF_EMIT_COMMON, and
> stores the result in a buffer that is as big as the smaller
> of "ours" and "theirs".
> 
> In theory, this is right; we cannot have more common content
> than is in the smaller of the two blobs. But in practice,
> xdiff may give us more: if neither file ends in a newline,
> we get the "\nNo newline at end of file" marker.
> [...]
> 
> Reported-by: Stefan Frühwirth <stefan.fruehwirth@uni-graz.at>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> diff --git a/merge-blobs.c b/merge-blobs.c
> @@ -51,19 +51,16 @@ static void *three_way_filemerge(const char *path, mmfile_t *base, mmfile_t *our
>  static int common_outf(void *priv_, mmbuffer_t *mb, int nbuf)
>  {
>  	int i;
> -	mmfile_t *dst = priv_;
> +	struct strbuf *dst = priv_;
>  
> -	for (i = 0; i < nbuf; i++) {
> -		memcpy(dst->ptr + dst->size, mb[i].ptr, mb[i].size);
> -		dst->size += mb[i].size;
> -	}
> +	for (i = 0; i < nbuf; i++)
> +		strbuf_add(dst, mb[i].ptr, mb[i].size);
>  	return 0;
>  }
>  
>  static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)
>  {
> -	unsigned long size = f1->size < f2->size ? f1->size : f2->size;
> -	void *ptr = xmalloc(size);
> +	struct strbuf out = STRBUF_INIT;
>  	xpparam_t xpp;
>  	xdemitconf_t xecfg;
>  	xdemitcb_t ecb;
> @@ -75,11 +72,15 @@ static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)
>  	xecfg.flags = XDL_EMIT_COMMON;
>  	ecb.outf = common_outf;
>  
> -	res->ptr = ptr;
> -	res->size = 0;
> +	ecb.priv = &out;
> +	if (xdi_diff(f1, f2, &xpp, &xecfg, &ecb) < 0) {
> +		strbuf_release(&out);
> +		return -1;
> +	}
>  
> -	ecb.priv = res;
> -	return xdi_diff(f1, f2, &xpp, &xecfg, &ecb);
> +	res->size = out.len; /* avoid long/size_t pointer mismatch below */

It took a minute or two for me to realize that "mismatch below" was
talking about the second argument to strbuf_detach(). I tried
rewriting the comment to mention the second argument explicitly, but
couldn't come up with one sufficiently succinct. Oh well.

> +	res->ptr = strbuf_detach(&out, NULL);
> +	return 0;
>  }

My reviewed-by may not be worth much since this code is new to me
too, but this patch looks "obviously correct" to me, so:

    Reviewed-by: Eric Sunshine <sunshine@sunshineco.com>

Perhaps squash in the following test which I adapted from the
reproduction recipe provided by Chris Rossi[1]?

[1] https://gist.github.com/chrisrossi/f09c8bed70b364f9f12e


--- 8< ---
diff --git a/t/t4300-merge-tree.sh b/t/t4300-merge-tree.sh
index 9015e47..1f2aa74 100755
--- a/t/t4300-merge-tree.sh
+++ b/t/t4300-merge-tree.sh
@@ -352,4 +352,22 @@ test_expect_success 'turn tree to file' '
 	test_cmp expect actual
 '
 
+test_expect_success "don't underallocate result buffer" '
+	test_when_finished "git checkout master" &&
+	git checkout --orphan some &&
+	git rm -rf . &&
+	printf "b\n" >a &&
+	git add a &&
+	git commit -m "first commit" &&
+	printf "\na" >b &&
+	git add b &&
+	git commit -m "second commit, first branch" &&
+	git checkout @^ &&
+	git checkout -b other &&
+	printf "a" >b &&
+	git add b &&
+	git commit -m "second commit, second branch" &&
+	git merge-tree @^ some other
+'
+
 test_done
--- 8< ---

Re: [PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Jeff King]

On Tue, Feb 16, 2016 at 12:09:15AM -0500, Eric Sunshine wrote:

> > -	ecb.priv = res;
> > -	return xdi_diff(f1, f2, &xpp, &xecfg, &ecb);
> > +	res->size = out.len; /* avoid long/size_t pointer mismatch below */
> 
> It took a minute or two for me to realize that "mismatch below" was
> talking about the second argument to strbuf_detach(). I tried
> rewriting the comment to mention the second argument explicitly, but
> couldn't come up with one sufficiently succinct. Oh well.

Maybe "avoid long/size_t mismatch in strbuf_detach" would be better.

> > +	res->ptr = strbuf_detach(&out, NULL);
> > +	return 0;
> >  }
> 
> My reviewed-by may not be worth much since this code is new to me
> too, but this patch looks "obviously correct" to me, so:
> 
>     Reviewed-by: Eric Sunshine <sunshine@sunshineco.com>
> 
> Perhaps squash in the following test which I adapted from the
> reproduction recipe provided by Chris Rossi[1]?
> 
> [1] https://gist.github.com/chrisrossi/f09c8bed70b364f9f12e

Yeah, maybe. There were two reasons I avoided adding a test.

One, I secretly hoped that by dragging my feet we could get consensus on
just ripping out merge-tree entirely. ;)

Two, I'm not sure what the test output _should_ be. I think this case is
buggy. So we can check that we don't corrupt the heap, which is nice,
but I don't like adding a test that doesn't test_cmp the expected output
(and see my earlier comments re: thinking hard).

But if we are going to keep it, maybe some exercise of the code is
better than none.

-Peff

Re: [PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Stefan Frühwirth]

Thank you for working on this! Let me just address two things from an 
outsider's perspective:

On 2016-02-16 at 06:50, Jeff King wrote:
> Yeah, maybe. There were two reasons I avoided adding a test.
>
> One, I secretly hoped that by dragging my feet we could get consensus on
> just ripping out merge-tree entirely. ;)

Since I cannot comment on the code quality or maturity of merge-tree, 
but would appreciate if this tool worked as expected, let me quote 
Chris' comment[1] on why he uses merge-tree instead of just "git merge", 
hoping that it has an impact upon your decision whether to keep the code 
or "ripping it out":

"One might ask, why not use the porcelain 'git merge' command? One
reason is, in the context of the two phase commit protocol, we'd rather
do pretty much everything we possibly can in the voting stage, leaving
ourselves with nothing to do in the finish phase except updating the
head to the commit we just created, and possibly updating the working
directory--operations that are guaranteed to work. Since 'git merge'
will update the head, we'd prefer to do it during the final phase of the
commit, but we can't guarantee it will work. There is not a convenient
way to do a merge dry run during the voting phase. Although I can
conceive of ways to do the merge during the voting phase and roll back
to the previous head if we need to, that feels a little riskier. Doing
the merge ourselves, here, also frees us from having to work with a
working directory, required by the porcelain 'git merge' command. This
means we can use bare repositories and/or have transactions that use
a head other than the repositories 'current' head."

> Two, I'm not sure what the test output _should_ be. I think this case is
> buggy. So we can check that we don't corrupt the heap, which is nice,

What do you mean exactly by "this case is buggy"? Doesn't make sense to me.

Stefan

[1] https://github.com/Pylons/acidfs/blob/master/acidfs/__init__.py

Re: [PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Jeff King]

On Tue, Feb 16, 2016 at 01:14:09PM +0100, Stefan Frühwirth wrote:

> On 2016-02-16 at 06:50, Jeff King wrote:
> >Yeah, maybe. There were two reasons I avoided adding a test.
> >
> >One, I secretly hoped that by dragging my feet we could get consensus on
> >just ripping out merge-tree entirely. ;)
> 
> Since I cannot comment on the code quality or maturity of merge-tree, but
> would appreciate if this tool worked as expected, let me quote Chris'
> comment[1] on why he uses merge-tree instead of just "git merge", hoping
> that it has an impact upon your decision whether to keep the code or
> "ripping it out":
> 
> "One might ask, why not use the porcelain 'git merge' command? One
> reason is, in the context of the two phase commit protocol, we'd rather
> do pretty much everything we possibly can in the voting stage, leaving
> ourselves with nothing to do in the finish phase except updating the
> head to the commit we just created, and possibly updating the working
> directory--operations that are guaranteed to work. Since 'git merge'
> will update the head, we'd prefer to do it during the final phase of the
> commit, but we can't guarantee it will work. There is not a convenient
> way to do a merge dry run during the voting phase. Although I can
> conceive of ways to do the merge during the voting phase and roll back
> to the previous head if we need to, that feels a little riskier. Doing
> the merge ourselves, here, also frees us from having to work with a
> working directory, required by the porcelain 'git merge' command. This
> means we can use bare repositories and/or have transactions that use
> a head other than the repositories 'current' head."

Yeah, I agree there isn't a great solution in git here. Using "git
merge" is definitely wrong if you don't want to touch HEAD or have a
working directory.  If you _just_ care about doing the tree-level merge
without content-level merging inside blobs, you can do it in the index
like:

  export GIT_INDEX_FILE=temp.index
  base=$(git merge-base $ours $theirs)
  git read-tree -i -m --aggressive $base $ours $theirs

If you want to do content-level resolving on top of that, you can do it
with:

  git merge-index git-merge-one-file -a

though it will need a temp directory to write out conflicts and
resolved content.

That was what powered GitHub's "merge" button for many years, though we
recently switched to using libgit2's merge (mostly because the
merge-one-file bit can be slow; we didn't care about seeing the
conflicts, and as a shell script it runs O(# of merged files)
processes).

I don't think merge-tree is at all the wrong tool, in the sense that it
is being used as designed. But it is using merge code that is different
from literally the rest of git. That means you're going to run into
weird bugs (like this one), and places where it does not behave the
same.  This add/add case, for instance, is usually a conflict in a
normal git merge (try your test case with "git merge"), but merge-tree
tries to do a partial content merge with a base that never actually
existed[1].

So I worry that merge-tree's existence is a disservice to people like
Chris, because there is no disclaimer that it is effectively
unmaintained.

> >Two, I'm not sure what the test output _should_ be. I think this case is
> >buggy. So we can check that we don't corrupt the heap, which is nice,
> 
> What do you mean exactly by "this case is buggy"? Doesn't make sense to me.

Actually, I'm not sure now.  Look at the output of git-merge-tree on
your test case, once my patch is applied[2]:

  $ git merge-tree HEAD~1 master other
  added in both
    our    100644 9fe188c32cdde9723a119c69548e3768882827d1 b
    their  100644 2e65efe2a145dda7ee51d1741299f848e5bf752e b
  @@ -1,2 +1,5 @@
  +<<<<<<< .our
   
  +=======
  +>>>>>>> .their
   a
  \ No newline at end of file

We blindly stick the "No newline at end of file" marker into the base
file content (which is what caused the overflow in the first place). So
our three-way merge is proceeding from a bogus state that has that extra
marker in it.  I _thought_ that was what I was seeing in the output
above.

But I think in practice it magically works, because it looks like both
sides remove that (so the correct merge resolution is to drop it, as
well). And the output above is because it shows the file content as a
diff against the "ours" version (you can tell from the hunk header that
the "No newline" marker is not part of the diff content).

So merge-blobs.c:generate_common_file() is definitely buggy, but I think
the bug gets unintentionally canceled out by the follow-on three-way
merge. Which is...good, I guess?

-Peff

[1] So one obvious alternative to my patch (besides killing off
    merge-tree entirely) would be to rip out the weird add/add handling.
    That would bring merge-tree in line with the rest of git, and would
    eliminate the buffer-overflowing code entirely.

[2] You can trigger it without my patch, too, but you need input files
    which differ by more than 29 bytes.

Re: [PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Yeah, maybe. There were two reasons I avoided adding a test.
>
> One, I secretly hoped that by dragging my feet we could get consensus on
> just ripping out merge-tree entirely. ;)
>
> Two, I'm not sure what the test output _should_ be. I think this case is
> buggy. So we can check that we don't corrupt the heap, which is nice,
> but I don't like adding a test that doesn't test_cmp the expected output
> (and see my earlier comments re: thinking hard).

Three, I know the existence of the program is not more than "we
could do something like this" illustration by Linus, and its output
is in no way _designed_ to be so.  We know today that it does not do
add/add conflict correctly thanks to this thread, but if we are
going to keep this program, we'd need to start from really designing
what its behaviour _should_ be, before casting the desirable
behaviour into stone with tests.

> But if we are going to keep it, maybe some exercise of the code is
> better than none.

So, "exercise" is better than none in the sense that it would
validate that "the command does something without barfing", but I
think there is a downside to casting its current behaviour as the
expected output in stone, if we are going to keep it.

Re: [PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Stefan Frühwirth]

On 2016-02-16 at 21:35 Jeff King wrote:

> Yeah, I agree there isn't a great solution in git here. Using "git
> merge" is definitely wrong if you don't want to touch HEAD or have a
> working directory.  If you _just_ care about doing the tree-level merge
> without content-level merging inside blobs, you can do it in the index
> like:
>
>    export GIT_INDEX_FILE=temp.index
>    base=$(git merge-base $ours $theirs)
>    git read-tree -i -m --aggressive $base $ours $theirs
>
> If you want to do content-level resolving on top of that, you can do it
> with:
>
>    git merge-index git-merge-one-file -a
>
> though it will need a temp directory to write out conflicts and
> resolved content.

That's an interesting alternative, I'll give it a try!

> I don't think merge-tree is at all the wrong tool, in the sense that it
> is being used as designed. But it is using merge code that is different
> from literally the rest of git. That means you're going to run into
> weird bugs (like this one), and places where it does not behave the
> same.  This add/add case, for instance, is usually a conflict in a
> normal git merge (try your test case with "git merge"), but merge-tree
> tries to do a partial content merge with a base that never actually
> existed[1].

Thank you for clarifying, I understand.

> So I worry that merge-tree's existence is a disservice to people like
> Chris, because there is no disclaimer that it is effectively
> unmaintained.

I agree, I don't want to advocate continuing development under these 
conditions.

> So merge-blobs.c:generate_common_file() is definitely buggy, but I think
> the bug gets unintentionally canceled out by the follow-on three-way
> merge. Which is...good, I guess?

Well I don't know how to handle all this with respect to my original 
problem, but that's completely off topic. Anyway: Thanks!

Stefan

Re: [PATCH] merge_blobs: use strbuf instead of manually-sized mmfile_t

[Stefan Frühwirth]

On 2016-02-16 at 22:27 Junio C Hamano wrote:

> Three, I know the existence of the program is not more than "we
> could do something like this" illustration by Linus, and its output
> is in no way _designed_ to be so.  We know today that it does not do

Well, then it is just really sad that the manpage doesn't say so. This 
should be corrected immediately in order to prevent someone to build 
more (e.g.) libraries on top of it.

Stefan