Git 2.19 Segmentation fault 11 on macOS
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: 11Both 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/
Quoted 7 lines · 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
Quoted 5 lines
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
Quoted 23 lines · Derrick Stolee
Quoted 7 lines · 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: 11Quoted 5 lines
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-editon 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
Quoted 6 lines
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 aaaOtherwise, 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 <[email protected]>
Date: Tue, 11 Sep 2018 11:42:03 -0400
Subject: [PATCH] range-diff: attempt to create test that fails on OSX
---
t/t3206-range-diff.sh | 5 +++++
1 file changed, 5 insertions(+)
t/t3206-range-diff.sh +0 -0
@@ -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
Quoted 61 lines · Derrick Stolee
Quoted 23 lines · Derrick Stolee
Quoted 7 lines · 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: 11Quoted 5 lines
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-editon 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 aaaQuoted 6 lines
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 aaaOtherwise, 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
3ee470d09d54b9ad7ab950f17051d625db0c8654Mon Sep 17 00:00:00 2001
From: Derrick Stolee <[email protected]>
Date: Tue, 11 Sep 2018 11:42:03 -0400
Subject: [PATCH] range-diff: attempt to create test that fails on OSXSigned-off-by Derrick Stolee <[email protected]>---
t/t3206-range-diff.sh | 5 +++++1 file changed, 5 insertions(+)t/t3206-range-diff.sh +0
-0@@ -142,4 +142,9 @@ test_expect_success 'changed message' '
test_cmpexpected actual
't/t3206-range-diff.sh +5
-0+test_expect_success 'amend and check' ' + git commit --amend -m "new message" && + git range-diff changed-message HEAD@{2} HEAD +' +
Quoted 3 lines
test_done
Signature · 1 line
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 checkRyenus, 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
Quoted 27 lines · Derrick Stolee
Quoted 26 lines · Derrick Stolee
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
3ee470d09d54b9ad7ab950f17051d625db0c8654Mon Sep 17 00:00:00 2001
From: Derrick Stolee <[email protected]>
Date: Tue, 11 Sep 2018 11:42:03 -0400
Subject: [PATCH] range-diff: attempt to create test that fails on OSXSigned-off-by Derrick Stolee <[email protected]>---
t/t3206-range-diff.sh | 5 +++++1 file changed, 5 insertions(+)t/t3206-range-diff.sh +0
-0@@ -142,4 +142,9 @@ test_expect_success 'changed message' '
test_cmpexpected actual
'
Quoted 11 lines
Quoted 8 lines
t/t3206-range-diff.sh +5
-0+test_expect_success 'amend and check' ' + git commit --amend -m "new message" && + git range-diff changed-message HEAD@{2} HEAD +' +test_done
Signature · 1 line
2.19.0.rc2.windows.1Sorry, 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_donevalgrind 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.
Quoted 43 lines · Thomas Gummerer
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_donevalgrind 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)
Quoted 4 lines
==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 ---
linear-assignment.c +1 -1
@@ -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];
t/t3206-range-diff.sh +5 -0
@@ -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 1/1 linear-assignment: fix potential out of bounds memory access (was: Re: Git 2.19 Segmentation fault 11 on macOS)
Quoted 46 lines · Thomas Gummerer
Quoted 45 lines · Thomas Gummerer
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_donevalgrind 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==
Quoted 5 lines
Quoted 2 lines
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.
--- linear-assignment.c | 4 ++-- t/t3206-range-diff.sh | 5 +++++ 2 files changed, 7 insertions(+), 2 deletions(-)
linear-assignment.c +2 -2
@@ -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;
t/t3206-range-diff.sh +5 -0
@@ -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
Signature · 1 line
2.19.0.397.gdd90340f6a
Re: [PATCH] linear-assignment: fix potential out of bounds memory access
Quoted 10 lines · Thomas Gummerer
Quoted 5 lines
Quoted 2 lines
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.
Quoted 2 lines
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.
Quoted 11 lines
--- >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.
Quoted 4 lines
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 whichINT_MAXis 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.
Quoted 50 lines
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 <[email protected]>Helped-by Derrick Stolee <[email protected]>Signed-off-by Thomas Gummerer <[email protected]>--- linear-assignment.c | 4 ++-- t/t3206-range-diff.sh | 5 +++++ 2 files changed, 7 insertions(+), 2 deletions(-)linear-assignment.c +2
-2@@ -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;t/t3206-range-diff.sh +5
-0@@ -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
Quoted 21 lines · Junio C Hamano
Quoted 11 lines · Thomas Gummerer
--- >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.
Quoted 4 lines
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 whichINT_MAXis the closest match in C).
Quoted 6 lines
Yeah, if we really want to avoid
INT_MAXwe could use another "have we found any value yet?" boolean variable, but the caller inget_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 isCOST_MAXthat is mere 65k, so it would be OK to useINT_MAXas 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.
Quoted 50 lines
Quoted 50 lines
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 <[email protected]>Helped-by Derrick Stolee <[email protected]>Signed-off-by Thomas Gummerer <[email protected]>--- linear-assignment.c | 4 ++-- t/t3206-range-diff.sh | 5 +++++ 2 files changed, 7 insertions(+), 2 deletions(-)linear-assignment.c +2
-2@@ -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;t/t3206-range-diff.sh +5
-0@@ -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)
In reply to Thomas GummererHi Thomas,
[quickly, as I will go back to a proper vacation after this]
linear-assignment.c void compute_assignment(int column_count, int row_count, int *cost, · line 54
Quoted 11 lines · Thomas Gummerer
linear-assignment.c +1
-2@@ -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
Quoted 22 lines
linear-assignment.c +1
-0+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;t/t3206-range-diff.sh +5
-0@@ -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_doneSignature · 1 line
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)
Quoted 3 lines · Johannes Schindelin
Hi Thomas,
[quickly, as I will go back to a proper vacation after this]
Sorry about interrupting your vacation, enjoy wherever you are! :)
Quoted 15 lines · Thomas Gummerer
linear-assignment.c void compute_assignment(int column_count, int row_count, int *cost, · line 54
Quoted 12 lines
linear-assignment.c +1
-2@@ -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!
Quoted 2 lines
Wouldn't it be possible to replace the
else {by an appropriateelse 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.
Quoted 25 lines
Ciao,
DschoQuoted 22 lines
linear-assignment.c +1
-0+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;t/t3206-range-diff.sh +5
-0@@ -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_doneSignature · 1 line
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)
In reply to Thomas GummererQuoted 3 lines · Thomas Gummerer
Subject: [PATCH] linear-assignment: fix potential out of bounds memory access
Currently the '
compute_assignment()' function can may read memory out
"can may"?
Quoted 6 lines
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 1/1 linear-assignment: fix potential out of bounds memory access
In reply to Thomas GummererCurrently 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.
--- linear-assignment.c | 6 ++++++ t/t3206-range-diff.sh | 5 +++++ 2 files changed, 11 insertions(+)
linear-assignment.c +6 -0
@@ -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);
t/t3206-range-diff.sh +5 -0
@@ -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
Signature · 1 line
2.19.0.397.gdd90340f6a
Re: [PATCH v2] linear-assignment: fix potential out of bounds memory access
Quoted 3 lines · 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.
[...]
Quoted 7 lines
Reported-by ryenus <[email protected]>Helped-by Derrick Stolee <[email protected]>Signed-off-by Thomas Gummerer <[email protected]>--- 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
Quoted 5 lines · Derrick Stolee
Quoted 1 line · Derrick Stolee
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-<.
Quoted 13 lines
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 checkRyenus, it would help if you could create and push the following branches based on your local repro:
git branch base HEAD@{2}
Quoted 7 lines
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.
Quoted 8 lines · 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
Quoted 5 lines
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?
Hi,
thanks for your bug report!
Quoted 4 lines · 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
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).
Quoted 8 lines
git version 2.19.0
Segmentation fault: 11Both 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/
Quoted 9 lines · Thomas Gummerer
Hi,
thanks for your bug report!
Quoted 3 lines · ryenus
I just updated to 2.19 via Homebrew, git range-diff seems cool, but I only got a Segmentation fault: 11
Quoted 8 lines
Quoted 1 line
$ git version; git range-diff origin/master HEAD@{2} HEADUnfortunately 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: 11Quoted 12 lines
I tried with various values, but unfortunately failed to reproduce this so far (although admittedly I tried it on linux, not Mac OS).
Quoted 8 lines
git version 2.19.0
Segmentation fault: 11Both 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/
Quoted 19 lines · ryenus
Quoted 9 lines · Thomas Gummerer
Hi,
thanks for your bug report!
Quoted 3 lines · ryenus
I just updated to 2.19 via Homebrew, git range-diff seems cool, but I only got a Segmentation fault: 11
Quoted 8 lines
Quoted 1 line
$ git version; git range-diff origin/master HEAD@{2} HEADUnfortunately 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?
Quoted 5 lines
so
HEAD~2should be used instead ofHEAD@{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?