Git 2.19 Segmentation fault 11 on macOS

Git 2.19 Segmentation fault 11 on macOS

[ryenus]

I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
only got a Segmentation fault: 11

    $ git version; git range-diff origin/master  HEAD@{2} HEAD
    git version 2.19.0
    Segmentation fault: 11

Both origin/master and my local branch each got two new commits of their own,
please correct me if this is not the expected way to use git range-diff.

FYI, I've created a sample repo here:
https://github.com/ryenus/range-diff-segfault/

Re: Git 2.19 Segmentation fault 11 on macOS

[Derrick Stolee]

On 9/11/2018 11:25 AM, ryenus wrote:
> I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
> only got a Segmentation fault: 11
>
>      $ git version; git range-diff origin/master  HEAD@{2} HEAD
>      git version 2.19.0
>      Segmentation fault: 11
>
> Both origin/master and my local branch each got two new commits of their own,
> please correct me if this is not the expected way to use git range-diff.
>
> FYI, I've created a sample repo here:
> https://github.com/ryenus/range-diff-segfault/

Hi Ryenus,

Thanks for the report!

I ran something similar using Git for Windows 2.19.0-rc2. I had to run 
`git commit --amend --no-edit` on the tip commit to make my local master 
disagree with origin/master. I then ran the following:

$ git range-diff origin/master HEAD~1 HEAD
-:  ------- > 1:  5009c62 aaa

With this, the command succeeded for me. There is another way to get a 
similar result, could you try it?

$ git range-diff origin/master~1..origin/master HEAD~1..HEAD
1:  f14d571 = 1:  5009c62 aaa

Otherwise, we can now get started trying to repro this on a Mac. Thanks!

-Stolee

Re: Git 2.19 Segmentation fault 11 on macOS

[Derrick Stolee]

On 9/11/2018 11:38 AM, Derrick Stolee wrote:
> On 9/11/2018 11:25 AM, ryenus wrote:
>> I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
>> only got a Segmentation fault: 11
>>
>>      $ git version; git range-diff origin/master  HEAD@{2} HEAD
>>      git version 2.19.0
>>      Segmentation fault: 11
>>
>> Both origin/master and my local branch each got two new commits of 
>> their own,
>> please correct me if this is not the expected way to use git range-diff.
>>
>> FYI, I've created a sample repo here:
>> https://github.com/ryenus/range-diff-segfault/
>
> Hi Ryenus,
>
> Thanks for the report!
>
> I ran something similar using Git for Windows 2.19.0-rc2. I had to run 
> `git commit --amend --no-edit` on the tip commit to make my local 
> master disagree with origin/master. I then ran the following:
>
> $ git range-diff origin/master HEAD~1 HEAD
> -:  ------- > 1:  5009c62 aaa
>
> With this, the command succeeded for me. There is another way to get a 
> similar result, could you try it?
>
> $ git range-diff origin/master~1..origin/master HEAD~1..HEAD
> 1:  f14d571 = 1:  5009c62 aaa
>
> Otherwise, we can now get started trying to repro this on a Mac. Thanks!

The patch below includes a test that fails on Mac OSX with a segfault.

GitGitGadget PR: https://github.com/gitgitgadget/git/pull/36
Failed Build: 
https://git-for-windows.visualstudio.com/git/_build/results?buildId=18616&view=logs

-->8--

 From 3ee470d09d54b9ad7ab950f17051d625db0c8654 Mon Sep 17 00:00:00 2001
From: Derrick Stolee <dstolee@microsoft.com>
Date: Tue, 11 Sep 2018 11:42:03 -0400
Subject: [PATCH] range-diff: attempt to create test that fails on OSX

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
  t/t3206-range-diff.sh | 5 +++++
  1 file changed, 5 insertions(+)

diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
index 2237c7f4af..02744b07a8 100755
--- a/t/t3206-range-diff.sh
+++ b/t/t3206-range-diff.sh
@@ -142,4 +142,9 @@ test_expect_success 'changed message' '
         test_cmp expected actual
  '

+test_expect_success 'amend and check' '
+       git commit --amend -m "new message" &&
+       git range-diff changed-message HEAD@{2} HEAD
+'
+
  test_done
--
2.19.0.rc2.windows.1

Re: Git 2.19 Segmentation fault 11 on macOS

[Derrick Stolee]

On 9/11/2018 12:04 PM, Derrick Stolee wrote:
> On 9/11/2018 11:38 AM, Derrick Stolee wrote:
>> On 9/11/2018 11:25 AM, ryenus wrote:
>>> I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
>>> only got a Segmentation fault: 11
>>>
>>>      $ git version; git range-diff origin/master  HEAD@{2} HEAD
>>>      git version 2.19.0
>>>      Segmentation fault: 11
>>>
>>> Both origin/master and my local branch each got two new commits of 
>>> their own,
>>> please correct me if this is not the expected way to use git 
>>> range-diff.
>>>
>>> FYI, I've created a sample repo here:
>>> https://github.com/ryenus/range-diff-segfault/
>>
>> Hi Ryenus,
>>
>> Thanks for the report!
>>
>> I ran something similar using Git for Windows 2.19.0-rc2. I had to 
>> run `git commit --amend --no-edit` on the tip commit to make my local 
>> master disagree with origin/master. I then ran the following:
>>
>> $ git range-diff origin/master HEAD~1 HEAD
>> -:  ------- > 1:  5009c62 aaa
>>
>> With this, the command succeeded for me. There is another way to get 
>> a similar result, could you try it?
>>
>> $ git range-diff origin/master~1..origin/master HEAD~1..HEAD
>> 1:  f14d571 = 1:  5009c62 aaa
>>
>> Otherwise, we can now get started trying to repro this on a Mac. Thanks!
>
> The patch below includes a test that fails on Mac OSX with a segfault.
>
> GitGitGadget PR: https://github.com/gitgitgadget/git/pull/36
> Failed Build: 
> https://git-for-windows.visualstudio.com/git/_build/results?buildId=18616&view=logs
>
> -->8--
>
> From 3ee470d09d54b9ad7ab950f17051d625db0c8654 Mon Sep 17 00:00:00 2001
> From: Derrick Stolee <dstolee@microsoft.com>
> Date: Tue, 11 Sep 2018 11:42:03 -0400
> Subject: [PATCH] range-diff: attempt to create test that fails on OSX
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  t/t3206-range-diff.sh | 5 +++++
>  1 file changed, 5 insertions(+)
>
> diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> index 2237c7f4af..02744b07a8 100755
> --- a/t/t3206-range-diff.sh
> +++ b/t/t3206-range-diff.sh
> @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
>         test_cmp expected actual
>  '
>
> +test_expect_success 'amend and check' '
> +       git commit --amend -m "new message" &&
> +       git range-diff changed-message HEAD@{2} HEAD
> +'
> +
>  test_done
> -- 
> 2.19.0.rc2.windows.1


Sorry, nevermind. The test failed for a different reason:

2018-09-11T16:02:20.2680990Z ++ git range-diff changed-message 
'HEAD@{2}' HEAD
2018-09-11T16:02:20.2779250Z fatal: Log for 'HEAD' only has 2 entries.
2018-09-11T16:02:20.2802520Z error: could not parse log for 
'changed-message..HEAD@{2}'
2018-09-11T16:02:20.2817470Z error: last command exited with $?=255
2018-09-11T16:02:20.2832300Z not ok 12 - amend and check

Ryenus, it would help if you could create and push the following 
branches based on your local repro:

     git branch base HEAD@{2}

     git branch topic HEAD

     git push origin base topic

Also, does the following command fail, after creating the branches?

     git range-diff origin/master base topic


Thanks,

-Stolee

Re: Git 2.19 Segmentation fault 11 on macOS

[Thomas Gummerer]

On 09/11, Derrick Stolee wrote:
> On 9/11/2018 12:04 PM, Derrick Stolee wrote:
> > On 9/11/2018 11:38 AM, Derrick Stolee wrote:
> > The patch below includes a test that fails on Mac OSX with a segfault.
> > 
> > GitGitGadget PR: https://github.com/gitgitgadget/git/pull/36
> > Failed Build: https://git-for-windows.visualstudio.com/git/_build/results?buildId=18616&view=logs
> > 
> > -->8--
> > 
> > From 3ee470d09d54b9ad7ab950f17051d625db0c8654 Mon Sep 17 00:00:00 2001
> > From: Derrick Stolee <dstolee@microsoft.com>
> > Date: Tue, 11 Sep 2018 11:42:03 -0400
> > Subject: [PATCH] range-diff: attempt to create test that fails on OSX
> > 
> > Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> > ---
> >  t/t3206-range-diff.sh | 5 +++++
> >  1 file changed, 5 insertions(+)
> > 
> > diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> > index 2237c7f4af..02744b07a8 100755
> > --- a/t/t3206-range-diff.sh
> > +++ b/t/t3206-range-diff.sh
> > @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
> >         test_cmp expected actual
> >  '
> > 
> > +test_expect_success 'amend and check' '
> > +       git commit --amend -m "new message" &&
> > +       git range-diff changed-message HEAD@{2} HEAD
> > +'
> > +
> >  test_done
> > -- 
> > 2.19.0.rc2.windows.1
> 
> 
> Sorry, nevermind. The test failed for a different reason:

I think you're on the right track here.  I can not test this on Mac
OS, but on Linux, the following fails when running the test under
valgrind:

    diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
    index 2237c7f4af..a8b0ef8c1d 100755
    --- a/t/t3206-range-diff.sh
    +++ b/t/t3206-range-diff.sh
    @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
            test_cmp expected actual
     '
     
    +test_expect_success 'amend and check' '
    +       git commit --amend -m "new message" &&
    +       git range-diff master HEAD@{1} HEAD
    +'
    +
     test_done

valgrind gives me the following:

==18232== Invalid read of size 4
==18232==    at 0x34D7B5: compute_assignment (linear-assignment.c:54)
==18232==    by 0x2A4253: get_correspondences (range-diff.c:245)
==18232==    by 0x2A4BFB: show_range_diff (range-diff.c:427)
==18232==    by 0x19D453: cmd_range_diff (range-diff.c:108)
==18232==    by 0x122698: run_builtin (git.c:418)
==18232==    by 0x1229D8: handle_builtin (git.c:637)
==18232==    by 0x122BCC: run_argv (git.c:689)
==18232==    by 0x122D90: cmd_main (git.c:766)
==18232==    by 0x1D55A3: main (common-main.c:45)
==18232==  Address 0x4f4d844 is 0 bytes after a block of size 4 alloc'd
==18232==    at 0x483777F: malloc (vg_replace_malloc.c:299)
==18232==    by 0x3381B0: do_xmalloc (wrapper.c:60)
==18232==    by 0x338283: xmalloc (wrapper.c:87)
==18232==    by 0x2A3F8C: get_correspondences (range-diff.c:207)
==18232==    by 0x2A4BFB: show_range_diff (range-diff.c:427)
==18232==    by 0x19D453: cmd_range_diff (range-diff.c:108)
==18232==    by 0x122698: run_builtin (git.c:418)
==18232==    by 0x1229D8: handle_builtin (git.c:637)
==18232==    by 0x122BCC: run_argv (git.c:689)
==18232==    by 0x122D90: cmd_main (git.c:766)
==18232==    by 0x1D55A3: main (common-main.c:45)
==18232== 

I'm looking into why that fails.  Also adding Dscho to Cc here as the
author of this code.

Re: Git 2.19 Segmentation fault 11 on macOS

[Thomas Gummerer]

On 09/11, Thomas Gummerer wrote:
> I think you're on the right track here.  I can not test this on Mac
> OS, but on Linux, the following fails when running the test under
> valgrind:
> 
>     diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
>     index 2237c7f4af..a8b0ef8c1d 100755
>     --- a/t/t3206-range-diff.sh
>     +++ b/t/t3206-range-diff.sh
>     @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
>             test_cmp expected actual
>      '
>      
>     +test_expect_success 'amend and check' '
>     +       git commit --amend -m "new message" &&
>     +       git range-diff master HEAD@{1} HEAD
>     +'
>     +
>      test_done
> 
> valgrind gives me the following:
> 
> ==18232== Invalid read of size 4
> ==18232==    at 0x34D7B5: compute_assignment (linear-assignment.c:54)
> ==18232==    by 0x2A4253: get_correspondences (range-diff.c:245)
> ==18232==    by 0x2A4BFB: show_range_diff (range-diff.c:427)
> ==18232==    by 0x19D453: cmd_range_diff (range-diff.c:108)
> ==18232==    by 0x122698: run_builtin (git.c:418)
> ==18232==    by 0x1229D8: handle_builtin (git.c:637)
> ==18232==    by 0x122BCC: run_argv (git.c:689)
> ==18232==    by 0x122D90: cmd_main (git.c:766)
> ==18232==    by 0x1D55A3: main (common-main.c:45)
> ==18232==  Address 0x4f4d844 is 0 bytes after a block of size 4 alloc'd
> ==18232==    at 0x483777F: malloc (vg_replace_malloc.c:299)
> ==18232==    by 0x3381B0: do_xmalloc (wrapper.c:60)
> ==18232==    by 0x338283: xmalloc (wrapper.c:87)
> ==18232==    by 0x2A3F8C: get_correspondences (range-diff.c:207)
> ==18232==    by 0x2A4BFB: show_range_diff (range-diff.c:427)
> ==18232==    by 0x19D453: cmd_range_diff (range-diff.c:108)
> ==18232==    by 0x122698: run_builtin (git.c:418)
> ==18232==    by 0x1229D8: handle_builtin (git.c:637)
> ==18232==    by 0x122BCC: run_argv (git.c:689)
> ==18232==    by 0x122D90: cmd_main (git.c:766)
> ==18232==    by 0x1D55A3: main (common-main.c:45)
> ==18232== 
> 
> I'm looking into why that fails.  Also adding Dscho to Cc here as the
> author of this code.

The diff below seems to fix it.  Not submitting this as a proper
patch, as I don't quite understand what the original code tried to do
here.  However this does pass all tests we currently have and fixes
the out of bounds memory read that's caught by valgrind (and that I
imagine could cause the segfault on Mac OS).

This matches how the initial minimum for the reduction transfer is
calculated in [1].

I'll try to convince myself of the right solution, but should someone
more familiar with the linear-assignment algorithm have an idea, feel
free to take this over :)

[1]: https://github.com/src-d/lapjv/blob/master/lap.h#L276

--- >8 ---

diff --git a/linear-assignment.c b/linear-assignment.c
index 9b3e56e283..ab0aa5fd41 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -51,7 +51,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
 		else if (j1 < -1)
 			row2column[i] = -2 - j1;
 		else {
-			int min = COST(!j1, i) - v[!j1];
+			int min = INT_MAX;
 			for (j = 1; j < column_count; j++)
 				if (j != j1 && min > COST(j, i) - v[j])
 					min = COST(j, i) - v[j];
diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
index 2237c7f4af..a8b0ef8c1d 100755
--- a/t/t3206-range-diff.sh
+++ b/t/t3206-range-diff.sh
@@ -142,4 +142,9 @@ test_expect_success 'changed message' '
 	test_cmp expected actual
 '
 
+test_expect_success 'amend and check' '
+	git commit --amend -m "new message" &&
+	git range-diff master HEAD@{1} HEAD
+'
+
 test_done

--- >8 ---

[PATCH] linear-assignment: fix potential out of bounds memory access (was: Re: Git 2.19 Segmentation fault 11 on macOS)

[Thomas Gummerer]

On 09/11, Thomas Gummerer wrote:
> On 09/11, Thomas Gummerer wrote:
> > I think you're on the right track here.  I can not test this on Mac
> > OS, but on Linux, the following fails when running the test under
> > valgrind:
> > 
> >     diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> >     index 2237c7f4af..a8b0ef8c1d 100755
> >     --- a/t/t3206-range-diff.sh
> >     +++ b/t/t3206-range-diff.sh
> >     @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
> >             test_cmp expected actual
> >      '
> >      
> >     +test_expect_success 'amend and check' '
> >     +       git commit --amend -m "new message" &&
> >     +       git range-diff master HEAD@{1} HEAD
> >     +'
> >     +
> >      test_done
> > 
> > valgrind gives me the following:
> > 
> > ==18232== Invalid read of size 4
> > ==18232==    at 0x34D7B5: compute_assignment (linear-assignment.c:54)
> > ==18232==    by 0x2A4253: get_correspondences (range-diff.c:245)
> > ==18232==    by 0x2A4BFB: show_range_diff (range-diff.c:427)
> > ==18232==    by 0x19D453: cmd_range_diff (range-diff.c:108)
> > ==18232==    by 0x122698: run_builtin (git.c:418)
> > ==18232==    by 0x1229D8: handle_builtin (git.c:637)
> > ==18232==    by 0x122BCC: run_argv (git.c:689)
> > ==18232==    by 0x122D90: cmd_main (git.c:766)
> > ==18232==    by 0x1D55A3: main (common-main.c:45)
> > ==18232==  Address 0x4f4d844 is 0 bytes after a block of size 4 alloc'd
> > ==18232==    at 0x483777F: malloc (vg_replace_malloc.c:299)
> > ==18232==    by 0x3381B0: do_xmalloc (wrapper.c:60)
> > ==18232==    by 0x338283: xmalloc (wrapper.c:87)
> > ==18232==    by 0x2A3F8C: get_correspondences (range-diff.c:207)
> > ==18232==    by 0x2A4BFB: show_range_diff (range-diff.c:427)
> > ==18232==    by 0x19D453: cmd_range_diff (range-diff.c:108)
> > ==18232==    by 0x122698: run_builtin (git.c:418)
> > ==18232==    by 0x1229D8: handle_builtin (git.c:637)
> > ==18232==    by 0x122BCC: run_argv (git.c:689)
> > ==18232==    by 0x122D90: cmd_main (git.c:766)
> > ==18232==    by 0x1D55A3: main (common-main.c:45)
> > ==18232== 
> > 
> > I'm looking into why that fails.  Also adding Dscho to Cc here as the
> > author of this code.
> 
> The diff below seems to fix it.  Not submitting this as a proper
> patch [...]

I found the time to actually have a look at the paper, so here's a
proper patch:

I'm still not entirely sure what the initial code tried to do here,
but I think staying as close as possible to the original is probably
our best option here, also for future readers of this code.

--- >8 ---

Subject: [PATCH] linear-assignment: fix potential out of bounds memory access

Currently the 'compute_assignment()' function can may read memory out
of bounds, even if used correctly.  Namely this happens when we only
have one column.  In that case we try to calculate the initial
minimum cost using '!j1' as column in the reduction transfer code.
That in turn causes us to try and get the cost from column 1 in the
cost matrix, which does not exist, and thus results in an out of
bounds memory read.

Instead of trying to intialize the minimum cost from another column,
just set it to INT_MAX.  This also matches what the example code in the
original paper for the algorithm [1] does (it initializes the value to
inf, for which INT_MAX is the closest match in C).

Note that the test only fails under valgrind on Linux, but the same
command has been reported to segfault on Mac OS.

Also start from 0 in the loop, which matches what the example code in
the original paper does as well.  Starting from 1 means we'd ignore
the first column during the reduction transfer phase.  Note that in
the original paper the loop does start from 1, but the implementation
is in Pascal, where arrays are 1 indexed.

[1]: Jonker, R., & Volgenant, A. (1987). A shortest augmenting path
     algorithm for dense and sparse linear assignment
     problems. Computing, 38(4), 325–340.

Reported-by: ryenus <ryenus@gmail.com>
Helped-by: Derrick Stolee <stolee@gmail.com>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
---
 linear-assignment.c   | 4 ++--
 t/t3206-range-diff.sh | 5 +++++
 2 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index 9b3e56e283..7700b80eeb 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -51,8 +51,8 @@ void compute_assignment(int column_count, int row_count, int *cost,
 		else if (j1 < -1)
 			row2column[i] = -2 - j1;
 		else {
-			int min = COST(!j1, i) - v[!j1];
-			for (j = 1; j < column_count; j++)
+			int min = INT_MAX;
+			for (j = 0; j < column_count; j++)
 				if (j != j1 && min > COST(j, i) - v[j])
 					min = COST(j, i) - v[j];
 			v[j1] -= min;
diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
index 2237c7f4af..fb4c13a84a 100755
--- a/t/t3206-range-diff.sh
+++ b/t/t3206-range-diff.sh
@@ -142,4 +142,9 @@ test_expect_success 'changed message' '
 	test_cmp expected actual
 '
 
+test_expect_success 'no commits on one side' '
+	git commit --amend -m "new message" &&
+	git range-diff master HEAD@{1} HEAD
+'
+
 test_done
-- 
2.19.0.397.gdd90340f6a

Re: [PATCH] linear-assignment: fix potential out of bounds memory access

[Junio C Hamano]

Thomas Gummerer <t.gummerer@gmail.com> writes:

>> > I'm looking into why that fails.  Also adding Dscho to Cc here as the
>> > author of this code.
>> 
>> The diff below seems to fix it.  Not submitting this as a proper
>> patch [...]
>
> I found the time to actually have a look at the paper, so here's a
> proper patch:
>
> I'm still not entirely sure what the initial code tried to do here,

It looks to me an attempt to optimize (instead of starting from a
value that is too big to be minimum, pick the first value and start
from there, and all the "found even smaller one, so let's replace"
later would work the same way) that went wrong (just that the "first
one" was written incorrectly), but it is not absolutely necessary to
find out why the code was written in a particular way that happened
to be buggy.

> but I think staying as close as possible to the original is probably
> our best option here, also for future readers of this code.

Thanks for digging.

> --- >8 ---
>
> Subject: [PATCH] linear-assignment: fix potential out of bounds memory access
>
> Currently the 'compute_assignment()' function can may read memory out
> of bounds, even if used correctly.  Namely this happens when we only
> have one column.  In that case we try to calculate the initial
> minimum cost using '!j1' as column in the reduction transfer code.
> That in turn causes us to try and get the cost from column 1 in the
> cost matrix, which does not exist, and thus results in an out of
> bounds memory read.

This nicely explains what goes wrong.

> Instead of trying to intialize the minimum cost from another column,
> just set it to INT_MAX.  This also matches what the example code in the
> original paper for the algorithm [1] does (it initializes the value to
> inf, for which INT_MAX is the closest match in C).

Yeah, if we really want to avoid INT_MAX we could use another "have
we found any value yet?" boolean variable, but the caller in
get_correspondences() does not even worry about integer overflows
when stuffing diffsize to the cost[] array, and the other possible
value that can go to cost[] array is COST_MAX that is mere 65k, so
it would be OK to use INT_MAX as sentinel here, I guess.

> Note that the test only fails under valgrind on Linux, but the same
> command has been reported to segfault on Mac OS.
>
> Also start from 0 in the loop, which matches what the example code in
> the original paper does as well.  Starting from 1 means we'd ignore
> the first column during the reduction transfer phase.  Note that in
> the original paper the loop does start from 1, but the implementation
> is in Pascal, where arrays are 1 indexed.
>
> [1]: Jonker, R., & Volgenant, A. (1987). A shortest augmenting path
>      algorithm for dense and sparse linear assignment
>      problems. Computing, 38(4), 325–340.
>
> Reported-by: ryenus <ryenus@gmail.com>
> Helped-by: Derrick Stolee <stolee@gmail.com>
> Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
> ---
>  linear-assignment.c   | 4 ++--
>  t/t3206-range-diff.sh | 5 +++++
>  2 files changed, 7 insertions(+), 2 deletions(-)
>
> diff --git a/linear-assignment.c b/linear-assignment.c
> index 9b3e56e283..7700b80eeb 100644
> --- a/linear-assignment.c
> +++ b/linear-assignment.c
> @@ -51,8 +51,8 @@ void compute_assignment(int column_count, int row_count, int *cost,
>  		else if (j1 < -1)
>  			row2column[i] = -2 - j1;
>  		else {
> -			int min = COST(!j1, i) - v[!j1];
> -			for (j = 1; j < column_count; j++)
> +			int min = INT_MAX;
> +			for (j = 0; j < column_count; j++)
>  				if (j != j1 && min > COST(j, i) - v[j])
>  					min = COST(j, i) - v[j];
>  			v[j1] -= min;
> diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> index 2237c7f4af..fb4c13a84a 100755
> --- a/t/t3206-range-diff.sh
> +++ b/t/t3206-range-diff.sh
> @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
>  	test_cmp expected actual
>  '
>  
> +test_expect_success 'no commits on one side' '
> +	git commit --amend -m "new message" &&
> +	git range-diff master HEAD@{1} HEAD
> +'
> +
>  test_done

Re: [PATCH] linear-assignment: fix potential out of bounds memory access

[Thomas Gummerer]

On 09/12, Junio C Hamano wrote:
> Thomas Gummerer <t.gummerer@gmail.com> writes:

> > --- >8 ---
> >
> > Subject: [PATCH] linear-assignment: fix potential out of bounds memory access
> >
> > Currently the 'compute_assignment()' function can may read memory out
> > of bounds, even if used correctly.  Namely this happens when we only
> > have one column.  In that case we try to calculate the initial
> > minimum cost using '!j1' as column in the reduction transfer code.
> > That in turn causes us to try and get the cost from column 1 in the
> > cost matrix, which does not exist, and thus results in an out of
> > bounds memory read.
> 
> This nicely explains what goes wrong.
> 
> > Instead of trying to intialize the minimum cost from another column,
> > just set it to INT_MAX.  This also matches what the example code in the
> > original paper for the algorithm [1] does (it initializes the value to
> > inf, for which INT_MAX is the closest match in C).
> 
> Yeah, if we really want to avoid INT_MAX we could use another "have
> we found any value yet?" boolean variable, but the caller in
> get_correspondences() does not even worry about integer overflows
> when stuffing diffsize to the cost[] array, and the other possible
> value that can go to cost[] array is COST_MAX that is mere 65k, so
> it would be OK to use INT_MAX as sentinel here, I guess.

Right, I'm not sure it would be worth introducing another boolean
variable here.  In the normal case we'll always enter the if condition
inside the loop, and set a reasonable 'min' value.

That does not happen if we only have one column, and the 'min' will
remain 'INT_MAX'.  Now in that case it doesn't matter much, as having
only one column means there's no possibility to assign anything, so
the actual values shouldn't matter (at least that's my understanding
of the algorithm so far).

Another improvement we may be able to make here is to not even try to
compute the assignment if there's only one column for that reason, but
I'm out of time today and the rest of my week looks a bit busy, so I
probably won't get to do anything before the beginning of next week.

> > Note that the test only fails under valgrind on Linux, but the same
> > command has been reported to segfault on Mac OS.
> >
> > Also start from 0 in the loop, which matches what the example code in
> > the original paper does as well.  Starting from 1 means we'd ignore
> > the first column during the reduction transfer phase.  Note that in
> > the original paper the loop does start from 1, but the implementation
> > is in Pascal, where arrays are 1 indexed.
> >
> > [1]: Jonker, R., & Volgenant, A. (1987). A shortest augmenting path
> >      algorithm for dense and sparse linear assignment
> >      problems. Computing, 38(4), 325–340.
> >
> > Reported-by: ryenus <ryenus@gmail.com>
> > Helped-by: Derrick Stolee <stolee@gmail.com>
> > Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
> > ---
> >  linear-assignment.c   | 4 ++--
> >  t/t3206-range-diff.sh | 5 +++++
> >  2 files changed, 7 insertions(+), 2 deletions(-)
> >
> > diff --git a/linear-assignment.c b/linear-assignment.c
> > index 9b3e56e283..7700b80eeb 100644
> > --- a/linear-assignment.c
> > +++ b/linear-assignment.c
> > @@ -51,8 +51,8 @@ void compute_assignment(int column_count, int row_count, int *cost,
> >  		else if (j1 < -1)
> >  			row2column[i] = -2 - j1;
> >  		else {
> > -			int min = COST(!j1, i) - v[!j1];
> > -			for (j = 1; j < column_count; j++)
> > +			int min = INT_MAX;
> > +			for (j = 0; j < column_count; j++)
> >  				if (j != j1 && min > COST(j, i) - v[j])
> >  					min = COST(j, i) - v[j];
> >  			v[j1] -= min;
> > diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> > index 2237c7f4af..fb4c13a84a 100755
> > --- a/t/t3206-range-diff.sh
> > +++ b/t/t3206-range-diff.sh
> > @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
> >  	test_cmp expected actual
> >  '
> >  
> > +test_expect_success 'no commits on one side' '
> > +	git commit --amend -m "new message" &&
> > +	git range-diff master HEAD@{1} HEAD
> > +'
> > +
> >  test_done

Re: [PATCH] linear-assignment: fix potential out of bounds memory access (was: Re: Git 2.19 Segmentation fault 11 on macOS)

[Johannes Schindelin]

Hi Thomas,

[quickly, as I will go back to a proper vacation after this]

On Wed, 12 Sep 2018, Thomas Gummerer wrote:

> diff --git a/linear-assignment.c b/linear-assignment.c
> index 9b3e56e283..7700b80eeb 100644
> --- a/linear-assignment.c
> +++ b/linear-assignment.c
> @@ -51,8 +51,8 @@ void compute_assignment(int column_count, int row_count, int *cost,
>  		else if (j1 < -1)
>  			row2column[i] = -2 - j1;
>  		else {
> -			int min = COST(!j1, i) - v[!j1];
> -			for (j = 1; j < column_count; j++)
> +			int min = INT_MAX;

I am worried about this, as I tried very hard to avoid integer overruns.

Wouldn't it be possible to replace the `else {` by an appropriate `else if
(...) { ... } else {`? E.g. `else if (column_count < 2)` or some such?

Ciao,
Dscho

> +			for (j = 0; j < column_count; j++)
>  				if (j != j1 && min > COST(j, i) - v[j])
>  					min = COST(j, i) - v[j];
>  			v[j1] -= min;
> diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> index 2237c7f4af..fb4c13a84a 100755
> --- a/t/t3206-range-diff.sh
> +++ b/t/t3206-range-diff.sh
> @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
>  	test_cmp expected actual
>  '
>  
> +test_expect_success 'no commits on one side' '
> +	git commit --amend -m "new message" &&
> +	git range-diff master HEAD@{1} HEAD
> +'
> +
>  test_done
> -- 
> 2.19.0.397.gdd90340f6a
> 
> 

Re: [PATCH] linear-assignment: fix potential out of bounds memory access (was: Re: Git 2.19 Segmentation fault 11 on macOS)

[Thomas Gummerer]

On 09/12, Johannes Schindelin wrote:
> Hi Thomas,
> 
> [quickly, as I will go back to a proper vacation after this]

Sorry about interrupting your vacation, enjoy wherever you are! :)

> On Wed, 12 Sep 2018, Thomas Gummerer wrote:
> 
> > diff --git a/linear-assignment.c b/linear-assignment.c
> > index 9b3e56e283..7700b80eeb 100644
> > --- a/linear-assignment.c
> > +++ b/linear-assignment.c
> > @@ -51,8 +51,8 @@ void compute_assignment(int column_count, int row_count, int *cost,
> >  		else if (j1 < -1)
> >  			row2column[i] = -2 - j1;
> >  		else {
> > -			int min = COST(!j1, i) - v[!j1];
> > -			for (j = 1; j < column_count; j++)
> > +			int min = INT_MAX;
> 
> I am worried about this, as I tried very hard to avoid integer overruns.

Ah fair enough, now I think I understand where the calculation of the
initial value of min comes from, thanks!

> Wouldn't it be possible to replace the `else {` by an appropriate `else if
> (...) { ... } else {`? E.g. `else if (column_count < 2)` or some such?

Yes, I think that would be possible.  However if we're already special
casing "column_count < 2", I think we might as well just exit early
before running through the whole algorithm in that case.  If there's
only one column, there are no commits that can be assigned to
eachother, as there is only the one.

We could also just not run call 'compute_assignment' in the first
place if column_count == 1, however I'd rather make the function safer
to call, just in case we find it useful for something else in the
future.

Will send an updated patch in a bit.

> Ciao,
> Dscho
> 
> > +			for (j = 0; j < column_count; j++)
> >  				if (j != j1 && min > COST(j, i) - v[j])
> >  					min = COST(j, i) - v[j];
> >  			v[j1] -= min;
> > diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> > index 2237c7f4af..fb4c13a84a 100755
> > --- a/t/t3206-range-diff.sh
> > +++ b/t/t3206-range-diff.sh
> > @@ -142,4 +142,9 @@ test_expect_success 'changed message' '
> >  	test_cmp expected actual
> >  '
> >  
> > +test_expect_success 'no commits on one side' '
> > +	git commit --amend -m "new message" &&
> > +	git range-diff master HEAD@{1} HEAD
> > +'
> > +
> >  test_done
> > -- 
> > 2.19.0.397.gdd90340f6a
> > 
> > 

Re: [PATCH] linear-assignment: fix potential out of bounds memory access (was: Re: Git 2.19 Segmentation fault 11 on macOS)

[Eric Sunshine]

On Wed, Sep 12, 2018 at 3:01 PM Thomas Gummerer <t.gummerer@gmail.com> wrote:
> Subject: [PATCH] linear-assignment: fix potential out of bounds memory access
>
> Currently the 'compute_assignment()' function can may read memory out

"can may"?

> of bounds, even if used correctly.  Namely this happens when we only
> have one column.  In that case we try to calculate the initial
> minimum cost using '!j1' as column in the reduction transfer code.
> That in turn causes us to try and get the cost from column 1 in the
> cost matrix, which does not exist, and thus results in an out of
> bounds memory read.

[PATCH v2] linear-assignment: fix potential out of bounds memory access

[Thomas Gummerer]

Currently the 'compute_assignment()' function may read memory out
of bounds, even if used correctly.  Namely this happens when we only
have one column.  In that case we try to calculate the initial
minimum cost using '!j1' as column in the reduction transfer code.
That in turn causes us to try and get the cost from column 1 in the
cost matrix, which does not exist, and thus results in an out of
bounds memory read.

In the original paper [1], the example code initializes that minimum
cost to "infinite".  We could emulate something similar by setting the
minimum cost to INT_MAX, which would result in the same minimum cost
as the current algorithm, as we'd always go into the if condition at
least once, except when we only have one column, and column_count thus
equals 1.

If column_count does equal 1, the condition in the loop would always
be false, and we'd end up with a minimum of INT_MAX, which may lead to
integer overflows later in the algorithm.

For a column count of 1, we however do not even really need to go
through the whole algorithm.  A column count of 1 means that there's
no possible assignments, and we can just zero out the column2row and
row2column arrays, and return early from the function, while keeping
the reduction transfer part of the function the same as it is
currently.

Another solution would be to just not call the 'compute_assignment()'
function from the range diff code in this case, however it's better to
make the compute_assignment function more robust, so future callers
don't run into this potential problem.

Note that the test only fails under valgrind on Linux, but the same
command has been reported to segfault on Mac OS.

[1]: Jonker, R., & Volgenant, A. (1987). A shortest augmenting path
     algorithm for dense and sparse linear assignment
     problems. Computing, 38(4), 325–340.

Reported-by: ryenus <ryenus@gmail.com>
Helped-by: Derrick Stolee <stolee@gmail.com>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
---
 linear-assignment.c   | 6 ++++++
 t/t3206-range-diff.sh | 5 +++++
 2 files changed, 11 insertions(+)

diff --git a/linear-assignment.c b/linear-assignment.c
index 9b3e56e283..ecffc09be6 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -19,6 +19,12 @@ void compute_assignment(int column_count, int row_count, int *cost,
 	int *free_row, free_count = 0, saved_free_count, *pred, *col;
 	int i, j, phase;
 
+	if (column_count < 2) {
+		memset(column2row, 0, sizeof(int) * column_count);
+		memset(row2column, 0, sizeof(int) * row_count);
+		return;
+	}
+
 	memset(column2row, -1, sizeof(int) * column_count);
 	memset(row2column, -1, sizeof(int) * row_count);
 	ALLOC_ARRAY(v, column_count);
diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
index 2237c7f4af..fb4c13a84a 100755
--- a/t/t3206-range-diff.sh
+++ b/t/t3206-range-diff.sh
@@ -142,4 +142,9 @@ test_expect_success 'changed message' '
 	test_cmp expected actual
 '
 
+test_expect_success 'no commits on one side' '
+	git commit --amend -m "new message" &&
+	git range-diff master HEAD@{1} HEAD
+'
+
 test_done
-- 
2.19.0.397.gdd90340f6a

Re: [PATCH v2] linear-assignment: fix potential out of bounds memory access

[Jonathan Nieder]

Thomas Gummerer wrote:

> Currently the 'compute_assignment()' function may read memory out
> of bounds, even if used correctly.  Namely this happens when we only
> have one column.
[...]
> Reported-by: ryenus <ryenus@gmail.com>
> Helped-by: Derrick Stolee <stolee@gmail.com>
> Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
> ---
>  linear-assignment.c   | 6 ++++++
>  t/t3206-range-diff.sh | 5 +++++
>  2 files changed, 11 insertions(+)

Here's a bit of a non-review, but hopefully it pokes others into
doing a proper review.

I haven't carefully examined the checks you're adding here.  Your
goals seem to be right.  I've been running with this patch since last
Thursday, with no problems yet.  Thanks for writing it.

Sincerely,
Jonathan

Re: Git 2.19 Segmentation fault 11 on macOS

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> On 9/11/2018 12:04 PM, Derrick Stolee wrote:
>
>> The patch below includes a test that fails on Mac OSX with a segfault.
> ...
> Sorry, nevermind. The test failed for a different reason:

Even if it is for a different reason, segfaulting is not acceptable,
but it seems it is failing quite normally.

Shucks.  It sounded too easy to get a reproduction like so X-<.

> 2018-09-11T16:02:20.2680990Z ++ git range-diff changed-message
> 'HEAD@{2}' HEAD
> 2018-09-11T16:02:20.2779250Z fatal: Log for 'HEAD' only has 2 entries.
> 2018-09-11T16:02:20.2802520Z error: could not parse log for
> 'changed-message..HEAD@{2}'
> 2018-09-11T16:02:20.2817470Z error: last command exited with $?=255
> 2018-09-11T16:02:20.2832300Z not ok 12 - amend and check
>
> Ryenus, it would help if you could create and push the following
> branches based on your local repro:
>
>     git branch base HEAD@{2}
>
>     git branch topic HEAD
>
>     git push origin base topic
>
> Also, does the following command fail, after creating the branches?
>
>     git range-diff origin/master base topic

Yup, that is a very sensible way to get a reliable reproduction.

Thanks for helping.

Re: Git 2.19 Segmentation fault 11 on macOS

[Elijah Newren]

On Tue, Sep 11, 2018 at 8:27 AM ryenus <ryenus@gmail.com> wrote:
>
> I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
> only got a Segmentation fault: 11
>
>     $ git version; git range-diff origin/master  HEAD@{2} HEAD
>     git version 2.19.0
>     Segmentation fault: 11
>
> Both origin/master and my local branch each got two new commits of their own,
> please correct me if this is not the expected way to use git range-diff.
>
> FYI, I've created a sample repo here:
> https://github.com/ryenus/range-diff-segfault/

Thanks for the report and coming up with a sample repo.  However,
reflogs don't transfer with clones, and your origin/master may well
point somewhere different than ours.  Could you run
   git rev-parse origin/master HEAD@{2} HEAD
in the range-diff-segfault repo where you can reproduce so we know
what commits to pass to trigger the bug?

Re: Git 2.19 Segmentation fault 11 on macOS

[Thomas Gummerer]

Hi,

thanks for your bug report!

On 09/11, ryenus wrote:
> I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
> only got a Segmentation fault: 11
> 
>     $ git version; git range-diff origin/master  HEAD@{2} HEAD

Unfortunately the HEAD@{2} syntax needs your reflog, which is not
available when just cloning the repository (the reflog is only local
and not pushed to the remote repository).  Would it be possible to
create a short script to create the repository where you're
experiencing the behaviour, or replacing 'origin/master', 'HEAD@{2}'
and 'HEAD' with the actual commit ids?

I tried with various values, but unfortunately failed to reproduce
this so far (although admittedly I tried it on linux, not Mac OS).

>     git version 2.19.0
>     Segmentation fault: 11
> 
> Both origin/master and my local branch each got two new commits of their own,
> please correct me if this is not the expected way to use git range-diff.
> 
> FYI, I've created a sample repo here:
> https://github.com/ryenus/range-diff-segfault/

Re: Git 2.19 Segmentation fault 11 on macOS

[ryenus]

On Tue, 11 Sep 2018 at 23:49, Thomas Gummerer <t.gummerer@gmail.com> wrote:
>
> Hi,
>
> thanks for your bug report!
>
> On 09/11, ryenus wrote:
> > I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
> > only got a Segmentation fault: 11
> >
> >     $ git version; git range-diff origin/master  HEAD@{2} HEAD
>
> Unfortunately the HEAD@{2} syntax needs your reflog, which is not
> available when just cloning the repository (the reflog is only local
> and not pushed to the remote repository).  Would it be possible to
> create a short script to create the repository where you're
> experiencing the behaviour, or replacing 'origin/master', 'HEAD@{2}'
> and 'HEAD' with the actual commit ids?

so `HEAD~2` should be used instead of `HEAD@{2}`, right?
I just tried the following and got same error:

    $ git range-diff master patch~2 patch
    Segmentation fault: 11

>
> I tried with various values, but unfortunately failed to reproduce
> this so far (although admittedly I tried it on linux, not Mac OS).
>
> >     git version 2.19.0
> >     Segmentation fault: 11
> >
> > Both origin/master and my local branch each got two new commits of their own,
> > please correct me if this is not the expected way to use git range-diff.
> >
> > FYI, I've created a sample repo here:
> > https://github.com/ryenus/range-diff-segfault/

Re: Git 2.19 Segmentation fault 11 on macOS

[Elijah Newren]

On Tue, Sep 11, 2018 at 9:07 AM ryenus <ryenus@gmail.com> wrote:
> On Tue, 11 Sep 2018 at 23:49, Thomas Gummerer <t.gummerer@gmail.com> wrote:
> >
> > Hi,
> >
> > thanks for your bug report!
> >
> > On 09/11, ryenus wrote:
> > > I just updated to 2.19 via Homebrew, git range-diff seems cool, but I
> > > only got a Segmentation fault: 11
> > >
> > >     $ git version; git range-diff origin/master  HEAD@{2} HEAD
> >
> > Unfortunately the HEAD@{2} syntax needs your reflog, which is not
> > available when just cloning the repository (the reflog is only local
> > and not pushed to the remote repository).  Would it be possible to
> > create a short script to create the repository where you're
> > experiencing the behaviour, or replacing 'origin/master', 'HEAD@{2}'
> > and 'HEAD' with the actual commit ids?
>
> so `HEAD~2` should be used instead of `HEAD@{2}`, right?
> I just tried the following and got same error:
>
>     $ git range-diff master patch~2 patch
>     Segmentation fault: 11

After cloning the repo and running
$ git range-diff master origin/patch~2 origin/patch

I cannot reproduce on either Linux or Mac OS X.  On Mac OS X, I tried
both with a locally built git-2.19 from sources, as well as an
homebrew-installed version of git-2.19.0.

For reference here's what I get running git rev-parse on those arguments:
$ git rev-parse master origin/patch~2 origin/patch
f14d571887c1b98fd22c60bc21c11700456162fa
5c7e07ebfbc7de5304deab6a04b476e6fa082d0e
ad8a185de38bfe546dd64fe37ae566de260d73c2

Is there any chance I'm misunderstanding or the repo doesn't have the
commits you were actually using to reproduce the bug?