[BUG] v2.16.0-rc0 seg faults when git bisect skip

[BUG] v2.16.0-rc0 seg faults when git bisect skip

[Yasushi SHOJI]

Hi,

git version 2.16.0.rc0 seg faults on my machine when I

git bisect skip

Here is a back trace:

$ /opt/mygit/bin/git --version
git version 2.16.0.rc0

$ /opt/mygit/bin/git bisect skip
Segmentation fault (core dumped)

$ gdb /opt/mygit/bin/git core
GNU gdb (Debian 7.12-6+b1) 7.12.0.20161007-git
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from /opt/mygit/bin/git...done.
[New LWP 5211]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Core was generated by `git bisect--helper --next-all'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
232 free_commit_list(p->next);
(gdb) bt
#0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
#1  0x000055a73107fc0f in do_find_bisection (list=0x0, nr=0,
weights=0x55a731b6ffd0, find_all=1) at bisect.c:361
#2  0x000055a73107fcf4 in find_bisection (commit_list=0x7ffe8750d4d0,
reaches=0x7ffe8750d4c4, all=0x7ffe8750d4c0, find_all=1) at
bisect.c:400
#3  0x000055a73108128d in bisect_next_all (prefix=0x0, no_checkout=0)
at bisect.c:969
#4  0x000055a730fd5238 in cmd_bisect__helper (argc=0,
argv=0x7ffe8750e230, prefix=0x0) at builtin/bisect--helper.c:140
#5  0x000055a730fcbc76 in run_builtin (p=0x55a73145c778
<commands+120>, argc=2, argv=0x7ffe8750e230) at git.c:346
#6  0x000055a730fcbf40 in handle_builtin (argc=2, argv=0x7ffe8750e230)
at git.c:554
#7  0x000055a730fcc0e8 in run_argv (argcp=0x7ffe8750e0ec,
argv=0x7ffe8750e0e0) at git.c:606
#8  0x000055a730fcc29b in cmd_main (argc=2, argv=0x7ffe8750e230) at git.c:683
#9  0x000055a731068d9e in main (argc=3, argv=0x7ffe8750e228) at common-main.c:43
(gdb) p p
$1 = (struct commit_list *) 0x0

As you can see, the code dereferences to the 'next' while 'p' is NULL.

I'm sure I did 'git bisect good' after git _found_ bad commit.  Then I
typed 'git bisect skip' on the commit 726804874 of guile repository.
If that matters at all.

I haven't touched guile repo to preserve the current state.

Let me know if you need any other info.
-- 
          yashi

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Ævar Arnfjörð Bjarmason]

On Wed, Jan 03 2018, Yasushi SHOJI jotted:

> Hi,
>
> git version 2.16.0.rc0 seg faults on my machine when I
> [...]
> Program terminated with signal SIGSEGV, Segmentation fault.
> #0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
> 232 free_commit_list(p->next);
> (gdb) bt
> #0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
> #1  0x000055a73107fc0f in do_find_bisection (list=0x0, nr=0,
> weights=0x55a731b6ffd0, find_all=1) at bisect.c:361
> #2  0x000055a73107fcf4 in find_bisection (commit_list=0x7ffe8750d4d0,
> reaches=0x7ffe8750d4c4, all=0x7ffe8750d4c0, find_all=1) at
> bisect.c:400
> #3  0x000055a73108128d in bisect_next_all (prefix=0x0, no_checkout=0)
> at bisect.c:969
> #4  0x000055a730fd5238 in cmd_bisect__helper (argc=0,
> argv=0x7ffe8750e230, prefix=0x0) at builtin/bisect--helper.c:140
> #5  0x000055a730fcbc76 in run_builtin (p=0x55a73145c778
> <commands+120>, argc=2, argv=0x7ffe8750e230) at git.c:346
> #6  0x000055a730fcbf40 in handle_builtin (argc=2, argv=0x7ffe8750e230)
> at git.c:554
> #7  0x000055a730fcc0e8 in run_argv (argcp=0x7ffe8750e0ec,
> argv=0x7ffe8750e0e0) at git.c:606
> #8  0x000055a730fcc29b in cmd_main (argc=2, argv=0x7ffe8750e230) at git.c:683
> #9  0x000055a731068d9e in main (argc=3, argv=0x7ffe8750e228) at common-main.c:43
> (gdb) p p
> $1 = (struct commit_list *) 0x0
>
> As you can see, the code dereferences to the 'next' while 'p' is NULL.
>
> I'm sure I did 'git bisect good' after git _found_ bad commit.  Then I
> typed 'git bisect skip' on the commit 726804874 of guile repository.
> If that matters at all.
>
> I haven't touched guile repo to preserve the current state.

I can't reproduce this myself, but looking at the backtrace it seems
pretty obvious that 7c117184d7 ("bisect: fix off-by-one error in
`best_bisection_sorted()`", 2017-11-05) is the culprit.

That changed more careful code added by Christian in 50e62a8e70
("rev-list: implement --bisect-all", 2007-10-22) to free a pointer which
as you can see can be NULL.

If you can test a patch to see if it works this should fix it:

diff --git a/bisect.c b/bisect.c
index 0fca17c02b..2f3008b078 100644
--- a/bisect.c
+++ b/bisect.c
@@ -229,8 +229,10 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
                if (i < cnt - 1)
                        p = p->next;
        }
-       free_commit_list(p->next);
-       p->next = NULL;
+       if (p) {
+               free_commit_list(p->next);
+               p->next = NULL;
+       }
        strbuf_release(&buf);
        free(array);
        return list;

But given the commit message by Martin maybe there's some deeper bug here.

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Martin Ågren]

On 3 January 2018 at 15:21, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
> On Wed, Jan 03 2018, Yasushi SHOJI jotted:
>
>> Hi,
>>
>> git version 2.16.0.rc0 seg faults on my machine when I
>> [...]
>> Program terminated with signal SIGSEGV, Segmentation fault.
>> #0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
>> 232 free_commit_list(p->next);
>> (gdb) bt
>> #0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
>> #1  0x000055a73107fc0f in do_find_bisection (list=0x0, nr=0,
>> weights=0x55a731b6ffd0, find_all=1) at bisect.c:361
>> #2  0x000055a73107fcf4 in find_bisection (commit_list=0x7ffe8750d4d0,
>> reaches=0x7ffe8750d4c4, all=0x7ffe8750d4c0, find_all=1) at
>> bisect.c:400
>> #3  0x000055a73108128d in bisect_next_all (prefix=0x0, no_checkout=0)
>> at bisect.c:969
>> #4  0x000055a730fd5238 in cmd_bisect__helper (argc=0,
>> argv=0x7ffe8750e230, prefix=0x0) at builtin/bisect--helper.c:140
>> #5  0x000055a730fcbc76 in run_builtin (p=0x55a73145c778
>> <commands+120>, argc=2, argv=0x7ffe8750e230) at git.c:346
>> #6  0x000055a730fcbf40 in handle_builtin (argc=2, argv=0x7ffe8750e230)
>> at git.c:554
>> #7  0x000055a730fcc0e8 in run_argv (argcp=0x7ffe8750e0ec,
>> argv=0x7ffe8750e0e0) at git.c:606
>> #8  0x000055a730fcc29b in cmd_main (argc=2, argv=0x7ffe8750e230) at git.c:683
>> #9  0x000055a731068d9e in main (argc=3, argv=0x7ffe8750e228) at common-main.c:43
>> (gdb) p p
>> $1 = (struct commit_list *) 0x0
>>
>> As you can see, the code dereferences to the 'next' while 'p' is NULL.
>>
>> I'm sure I did 'git bisect good' after git _found_ bad commit.  Then I
>> typed 'git bisect skip' on the commit 726804874 of guile repository.
>> If that matters at all.
>>
>> I haven't touched guile repo to preserve the current state.
>
> I can't reproduce this myself, but looking at the backtrace it seems
> pretty obvious that 7c117184d7 ("bisect: fix off-by-one error in
> `best_bisection_sorted()`", 2017-11-05) is the culprit.
>
> That changed more careful code added by Christian in 50e62a8e70
> ("rev-list: implement --bisect-all", 2007-10-22) to free a pointer which
> as you can see can be NULL.
>
> If you can test a patch to see if it works this should fix it:
>
> diff --git a/bisect.c b/bisect.c
> index 0fca17c02b..2f3008b078 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -229,8 +229,10 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
>                 if (i < cnt - 1)
>                         p = p->next;
>         }
> -       free_commit_list(p->next);
> -       p->next = NULL;
> +       if (p) {
> +               free_commit_list(p->next);
> +               p->next = NULL;
> +       }
>         strbuf_release(&buf);
>         free(array);
>         return list;
>
> But given the commit message by Martin maybe there's some deeper bug here.

I haven't tried to reproduce, or tested the patch, but from the looks of
it, your analysis and fix are both spot on. The special case that yashi
has hit is that `list` is NULL. The old code handled that very well, the
code after my patch ... not so well. The loop-sort-loop pattern reduces
to a no-op, both before and after my patch. But what I failed to realize
was that `list` could be NULL.

This could be fixed by an early return if `list` is NULL, but that would
also need some memory-handling. So I think your patch is just as good or
better, since it can be seen as restoring what was lost in 7c117184d7.

Thanks both, and sorry for this.
Martin

[PATCH] bisect: fix a regression causing a segfault

[Ævar Arnfjörð Bjarmason]

In 7c117184d7 ("bisect: fix off-by-one error in
`best_bisection_sorted()`", 2017-11-05) the more careful logic dealing
with freeing p->next in 50e62a8e70 ("rev-list: implement
--bisect-all", 2007-10-22) was removed.

Restore the more careful check to avoid segfaulting. Ideally this
would come with a test case, but we don't have steps to reproduce
this, only a backtrace from gdb pointing to this being the issue.

Reported-by: Yasushi SHOJI <yasushi.shoji@gmail.com>
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 bisect.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/bisect.c b/bisect.c
index 0fca17c02b..2f3008b078 100644
--- a/bisect.c
+++ b/bisect.c
@@ -229,8 +229,10 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		if (i < cnt - 1)
 			p = p->next;
 	}
-	free_commit_list(p->next);
-	p->next = NULL;
+	if (p) {
+		free_commit_list(p->next);
+		p->next = NULL;
+	}
 	strbuf_release(&buf);
 	free(array);
 	return list;
-- 
2.15.1.424.g9478a66081

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Yasushi SHOJI]

Hi,

On Thu, Jan 4, 2018 at 3:26 AM, Martin Ågren <martin.agren@gmail.com> wrote:
> On 3 January 2018 at 15:21, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>>
>> On Wed, Jan 03 2018, Yasushi SHOJI jotted:
>>
>>> Hi,
>>>
>>> git version 2.16.0.rc0 seg faults on my machine when I
>>> [...]
>>> Program terminated with signal SIGSEGV, Segmentation fault.
>>> #0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
>>> 232 free_commit_list(p->next);
>>> (gdb) bt
>>> #0  0x000055a73107f900 in best_bisection_sorted (list=0x0, nr=0) at bisect.c:232
>>> #1  0x000055a73107fc0f in do_find_bisection (list=0x0, nr=0,
>>> weights=0x55a731b6ffd0, find_all=1) at bisect.c:361
>>> #2  0x000055a73107fcf4 in find_bisection (commit_list=0x7ffe8750d4d0,
>>> reaches=0x7ffe8750d4c4, all=0x7ffe8750d4c0, find_all=1) at
>>> bisect.c:400
>>> #3  0x000055a73108128d in bisect_next_all (prefix=0x0, no_checkout=0)
>>> at bisect.c:969
>>> #4  0x000055a730fd5238 in cmd_bisect__helper (argc=0,
>>> argv=0x7ffe8750e230, prefix=0x0) at builtin/bisect--helper.c:140
>>> #5  0x000055a730fcbc76 in run_builtin (p=0x55a73145c778
>>> <commands+120>, argc=2, argv=0x7ffe8750e230) at git.c:346
>>> #6  0x000055a730fcbf40 in handle_builtin (argc=2, argv=0x7ffe8750e230)
>>> at git.c:554
>>> #7  0x000055a730fcc0e8 in run_argv (argcp=0x7ffe8750e0ec,
>>> argv=0x7ffe8750e0e0) at git.c:606
>>> #8  0x000055a730fcc29b in cmd_main (argc=2, argv=0x7ffe8750e230) at git.c:683
>>> #9  0x000055a731068d9e in main (argc=3, argv=0x7ffe8750e228) at common-main.c:43
>>> (gdb) p p
>>> $1 = (struct commit_list *) 0x0
>>>
>>> As you can see, the code dereferences to the 'next' while 'p' is NULL.
>>>
>>> I'm sure I did 'git bisect good' after git _found_ bad commit.  Then I
>>> typed 'git bisect skip' on the commit 726804874 of guile repository.
>>> If that matters at all.
>>>
>>> I haven't touched guile repo to preserve the current state.
>>
>> I can't reproduce this myself, but looking at the backtrace it seems
>> pretty obvious that 7c117184d7 ("bisect: fix off-by-one error in
>> `best_bisection_sorted()`", 2017-11-05) is the culprit.
>>
>> That changed more careful code added by Christian in 50e62a8e70
>> ("rev-list: implement --bisect-all", 2007-10-22) to free a pointer which
>> as you can see can be NULL.
>>
>> If you can test a patch to see if it works this should fix it:
>>
>> diff --git a/bisect.c b/bisect.c
>> index 0fca17c02b..2f3008b078 100644
>> --- a/bisect.c
>> +++ b/bisect.c
>> @@ -229,8 +229,10 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
>>                 if (i < cnt - 1)
>>                         p = p->next;
>>         }
>> -       free_commit_list(p->next);
>> -       p->next = NULL;
>> +       if (p) {
>> +               free_commit_list(p->next);
>> +               p->next = NULL;
>> +       }
>>         strbuf_release(&buf);
>>         free(array);
>>         return list;
>>
>> But given the commit message by Martin maybe there's some deeper bug here.
>
> I haven't tried to reproduce, or tested the patch, but from the looks of
> it, your analysis and fix are both spot on. The special case that yashi
> has hit is that `list` is NULL. The old code handled that very well, the
> code after my patch ... not so well. The loop-sort-loop pattern reduces
> to a no-op, both before and after my patch. But what I failed to realize
> was that `list` could be NULL.

The patch (actually, I've tested the one in pu, 2e9fdc795cb27) avoids
the seg fault for sure, but the question is:

When does the list allowed to contain NULLs?

Since nobody noticed it since 7c117184d7, it must be a rare case, right?

Would you guys elaborate a bit?  I don't have any insight how
best_bisection_sorted() should work and what the list should contain.
So that I can make a test case.

Thanks,
-- 
               yashi

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Yasushi SHOJI]

Hi,

On Fri, Jan 5, 2018 at 11:45 AM, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:
> So that I can make a test case.

OK, here is the step to reproduce on git.git

$ git bisect start
$ git bisect bad v2.16.0-rc0
$ git bisect good 0433d533f13671f4313c31e34707f0f5281a18e0
$ git bisect good
$ git bisect bad
$ git bisect bad
$ git bisect skip #=> works with error
$ git bisect good #=> Segmentation fault
$ git bisect skip #=> Segmentation fault

The following is with full outputs, just in case you need it.

$ git describe
v2.16.0-rc0

$ git bisect start
$ git bisect bad v2.16.0-rc0

$ git bisect good 0433d533f13671f4313c31e34707f0f5281a18e0
Bisecting: 4 revisions left to test after this (roughly 2 steps)
[c87b653c46c4455561642b14efc8920a0b3e44b9] builtin/describe.c: rename
`oid` to avoid variable shadowing

$ git bisect good
Bisecting: 2 revisions left to test after this (roughly 1 step)
[4dbc59a4cce418ff8428a9d2ecd67c34ca50db56] builtin/describe.c: factor
out describe_commit

$ git bisect bad
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[cdaed0cf023a47cae327671fae11c10d88100ee7] builtin/describe.c: print
debug statements earlier

$ git bisect bad
cdaed0cf023a47cae327671fae11c10d88100ee7 is the first bad commit
commit cdaed0cf023a47cae327671fae11c10d88100ee7
Author: Stefan Beller <sbeller@google.com>
Date:   Wed Nov 15 18:00:37 2017 -0800

    builtin/describe.c: print debug statements earlier

    When debugging, print the received argument at the start of the
    function instead of in the middle. This ensures that the received
    argument is printed in all code paths, and also allows a subsequent
    refactoring to not need to move the "arg" parameter.

    Signed-off-by: Stefan Beller <sbeller@google.com>
    Signed-off-by: Junio C Hamano <gitster@pobox.com>

:040000 040000 beb1f2c4d9ee7584e54e0489c7e85e348cbf9fc7
b9882eea0772e3025690d3513cea5a940567668e M builtin

$ git bisect skip
There are only 'skip'ped commits left to test.
The first bad commit could be any of:
cdaed0cf023a47cae327671fae11c10d88100ee7
We cannot bisect more!

$ git bisect good
Segmentation fault

$ git bisect skip
Segmentation fault
-- 
               yashi

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Martin Ågren]

> On Fri, Jan 5, 2018 at 11:45 AM, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:
>> When does the list allowed to contain NULLs?

Short answer: there are no commits left to test.

The list is built in the for-loop in `find_bisection()`. So the
technical answer is: if all commits in the initial list `commit_list`
are UNINTERESTING (including if `commit_list` is empty to begin with).

It's also helpful to study where we should end up from there. We should
take the `if (!revs.commits)` branch in `bisect_next_all()`. That is, we
should print either "There are only 'skip'ped commits left to test. The
first bad commit could be any of:" or "<commit> was both good and bad".

>> Since nobody noticed it since 7c117184d7, it must be a rare case, right?

Right, you marked a commit both good and bad. That's probably not very
common. But it obviously happens. :-)

On 5 January 2018 at 06:28, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:
> OK, here is the step to reproduce on git.git

Thank you for providing a script for reproducing this. It helped me come
up with the attached patch. The patch is based on ma/bisect-leakfix,
which includes Ævar's patch.

I think this patch could be useful, either as a final "let's test
something previously non-tested; this would have caught the segfault",
or simply squashed into Ævar's patch as a "let's add a test that would
have caught this, and which also tests a previously non-tested code
path."

Thanks for digging and finding a reproduction recipe.

Martin

-- >8 --
Subject: [PATCH] bisect: add test for marking commit both good and bad

Since 670f5fe34f ([PATCH] Fix bisection terminating condition,
2005-08-30), we have noticed and complained when a commit was marked
both good and bad. But we had no tests for this behavior.

Test the behavior when we mark a commit first bad, then good, but also
when we are already in the bad state, where `git bisect skip` should
notice it.

This test would have caught the segfault which was recently fixed in
2e9fdc795c (bisect: fix a regression causing a segfault, 2018-01-03).

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 t/t6030-bisect-porcelain.sh | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index 8c2c6eaef8..190f0ce0ab 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -894,4 +894,13 @@ test_expect_success 'bisect start takes options and revs in any order' '
 	test_cmp expected actual
 '
 
+test_expect_success 'marking commit both good and bad gets reported' '
+	git bisect reset &&
+	git bisect start HEAD &&
+	test_must_fail git bisect good HEAD >out &&
+	test_i18ngrep "both good and bad" out &&
+	test_must_fail git bisect skip >out &&
+	test_i18ngrep "both good and bad" out
+'
+
 test_done
-- 
2.16.0.rc1

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Yasushi SHOJI]

Hi Martin,

Thank you for your comment.
I haven't have time to read the code carefully so bare with me.

On Sat, Jan 6, 2018 at 5:21 PM, Martin Ågren <martin.agren@gmail.com> wrote:
>> On Fri, Jan 5, 2018 at 11:45 AM, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:
>>> When does the list allowed to contain NULLs?
>
> Short answer: there are no commits left to test.
>
> The list is built in the for-loop in `find_bisection()`. So the
> technical answer is: if all commits in the initial list `commit_list`
> are UNINTERESTING (including if `commit_list` is empty to begin with).
>
> It's also helpful to study where we should end up from there. We should
> take the `if (!revs.commits)` branch in `bisect_next_all()`. That is, we
> should print either "There are only 'skip'ped commits left to test. The
> first bad commit could be any of:" or "<commit> was both good and bad".

best_bisection_sorted() seems to do

 - get the commit list along with the number of elements in the list
 - walk the list one by one to check whether a element have TREESAME or not
 - if TREESAME, skip
 - if not, add it to array
 - sort the array by distance
 - put elements back to the list

so, if you find TREESAME, you get less elements than given, right?
Also, if you sort, the last commit, which has NULL in the ->next,
might get in the middle of the array??

# BTW, is it really fast to use QSORT even if you have to convert to
# an array from list?

>>> Since nobody noticed it since 7c117184d7, it must be a rare case, right?
>
> Right, you marked a commit both good and bad. That's probably not very
> common. But it obviously happens. :-)
>
> On 5 January 2018 at 06:28, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:
>> OK, here is the step to reproduce on git.git
>
> Thank you for providing a script for reproducing this. It helped me come
> up with the attached patch. The patch is based on ma/bisect-leakfix,
> which includes Ævar's patch.
>
> I think this patch could be useful, either as a final "let's test
> something previously non-tested; this would have caught the segfault",
> or simply squashed into Ævar's patch as a "let's add a test that would
> have caught this, and which also tests a previously non-tested code
> path."

Do we really need that?  What is a practical use of a commit having
both good and bad?

Regards,
-- 
            yashi

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Martin Ågren]

On 6 January 2018 at 15:27, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:
> best_bisection_sorted() seems to do
>
>  - get the commit list along with the number of elements in the list
>  - walk the list one by one to check whether a element have TREESAME or not
>  - if TREESAME, skip
>  - if not, add it to array
>  - sort the array by distance
>  - put elements back to the list
>
> so, if you find TREESAME, you get less elements than given, right?

All of this matches my understanding.

> Also, if you sort, the last commit, which has NULL in the ->next,
> might get in the middle of the array??

This is a bit tricky. The elements of the linked list are not sorted.
Instead, the items of the linked list are copied into an array and
sorted. The result is then put into a linked list.

Or actually, into the *same* list. That's an optimization to avoid
deallocating all objects in the list, then allocate (roughly) the same
number of objects again. It means all the `next`-pointers are already
set up, and we just need to set the final one to NULL. (It will already
be NULL if and only if the new list has the same length as the old,
i.e., if we didn't skip any TREESAME-commit.)

> # BTW, is it really fast to use QSORT even if you have to convert to
> # an array from list?

You'll find some QSORT/qsort-stuff in git-compat-util.h. We may or may
not end up doing an actual "quick sort". That would depend on, e.g., how
the C-library implements `qsort()`. Also, I'd guess that even if we have
room for an improvement, those cases (small `cnt`!) are already fast
enough that no-one really cares. That is, maybe we could measure a
speed-up, but would anyone really *notice* it?

>> Thank you for providing a script for reproducing this. It helped me come
>> up with the attached patch. The patch is based on ma/bisect-leakfix,
>> which includes Ævar's patch.
>>
>> I think this patch could be useful, either as a final "let's test
>> something previously non-tested; this would have caught the segfault",
>> or simply squashed into Ævar's patch as a "let's add a test that would
>> have caught this, and which also tests a previously non-tested code
>> path."
>
> Do we really need that?  What is a practical use of a commit having
> both good and bad?

There is not much practical use for *having* it. But there might be some
use in *detecting* it. Linus wrote in 670f5fe34f: "Also, add a safety
net: if somebody marks as good something that includes the known-bad
point, we now notice and complain, instead of writing an empty revision
to the new bisection branch."

So there might be some value in verifying that the safety-net works and
tells the user something useful (as opposed to Git segfaulting ;-) ).

Regards,
Martin

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Christian Couder]

Hi Yasushi,

On Sat, Jan 6, 2018 at 3:27 PM, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:

> best_bisection_sorted() seems to do
>
>  - get the commit list along with the number of elements in the list
>  - walk the list one by one to check whether a element have TREESAME or not
>  - if TREESAME, skip
>  - if not, add it to array
>  - sort the array by distance
>  - put elements back to the list

Yes.

> so, if you find TREESAME, you get less elements than given, right?

Yes.

> Also, if you sort, the last commit, which has NULL in the ->next,
> might get in the middle of the array??

Well, first the array is just necessary to sort the items pointed to
by the list. It is freed at the end of the function. We are mostly
interested in getting a sorted list from this function, not a sorted
array.

Also the array contains only items (commits) and distances, not list
elements, so the elements in the array don't have a ->next pointer.

About items in the list, when we put them back into the list we only
change p->item, so p->next still points to the next one. Only for the
last one we set p->next to NULL (if p is not NULL). So we don't
actually sort the list elements, we sort the items pointed to by the
list.

> # BTW, is it really fast to use QSORT even if you have to convert to
> # an array from list?

It is easier and probably faster to just use qsort, which we get from
#include <stdlib.h>, as it is hopefully optimized, rather than
reimplementing our own list sorting.

>>>> Since nobody noticed it since 7c117184d7, it must be a rare case, right?
>>
>> Right, you marked a commit both good and bad. That's probably not very
>> common. But it obviously happens. :-)

Yeah, mistakes unfortunately happens :-)

>> Thank you for providing a script for reproducing this. It helped me come
>> up with the attached patch. The patch is based on ma/bisect-leakfix,
>> which includes Ævar's patch.
>>
>> I think this patch could be useful, either as a final "let's test
>> something previously non-tested; this would have caught the segfault",
>> or simply squashed into Ævar's patch as a "let's add a test that would
>> have caught this, and which also tests a previously non-tested code
>> path."
>
> Do we really need that?  What is a practical use of a commit having
> both good and bad?

It is not practical, but it is a user mistake that happens.

Thanks for your reports and test cases,
Christian.

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Yasushi SHOJI]

[-- Attachment #1: Type: text/plain, Size: 356 bytes --]

Hi all,

Thank you guys for insightful help.  I just read the code and now I understand
what you guys are saying.  Yeah, I can say the fix is "spot on".

But, to be honest, it's hard to see why you need "if (p)" at  the first glance.
So, how about this fix, instead?

I also found a bug in show_list().  I'm attaching a patch as well.
-- 
           yashi

[-- Attachment #2: 0001-bisect-debug-convert-struct-object-to-object_id.patch --]
[-- Type: text/x-patch, Size: 1498 bytes --]

From d149a1348e94ea0246a10181751ce3bf9ba48198 Mon Sep 17 00:00:00 2001
From: Yasushi SHOJI <yashi@atmark-techno.com>
Date: Mon, 8 Jan 2018 22:31:10 +0900
Subject: [PATCH 1/2] bisect: debug: convert struct object to object_id

The commit f2fd0760f62e79609fef7bfd7ecebb002e8e4ced converted struct
object to object_id but a debug function show_list(), which is
ifdef'ed to noop, in bisect.c wasn't.

So fix it.
---
 bisect.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/bisect.c b/bisect.c
index 0fca17c02..fb3e44903 100644
--- a/bisect.c
+++ b/bisect.c
@@ -132,7 +132,7 @@ static void show_list(const char *debug, int counted, int nr,
 		unsigned flags = commit->object.flags;
 		enum object_type type;
 		unsigned long size;
-		char *buf = read_sha1_file(commit->object.sha1, &type, &size);
+		char *buf = read_sha1_file(commit->object.oid.hash, &type, &size);
 		const char *subject_start;
 		int subject_len;
 
@@ -144,10 +144,10 @@ static void show_list(const char *debug, int counted, int nr,
 			fprintf(stderr, "%3d", weight(p));
 		else
 			fprintf(stderr, "---");
-		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
+		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.oid.hash));
 		for (pp = commit->parents; pp; pp = pp->next)
 			fprintf(stderr, " %.*s", 8,
-				sha1_to_hex(pp->item->object.sha1));
+				sha1_to_hex(pp->item->object.oid.hash));
 
 		subject_len = find_commit_subject(buf, &subject_start);
 		if (subject_len)
-- 
2.15.1


[-- Attachment #3: 0002-bisect-handle-empty-list-in-best_bisection_sorted.patch --]
[-- Type: text/x-patch, Size: 2314 bytes --]

From 2ec8823de3bd0ca8253ddbd07f58b66afcfabe96 Mon Sep 17 00:00:00 2001
From: Yasushi SHOJI <yashi@atmark-techno.com>
Date: Mon, 8 Jan 2018 22:35:12 +0900
Subject: [PATCH 2/2] bisect: handle empty list in best_bisection_sorted()

In 7c117184d7 ("bisect: fix off-by-one error in
`best_bisection_sorted()`", 2017-11-05) the more careful logic dealing
with freeing p->next in 50e62a8e70 ("rev-list: implement
--bisect-all", 2007-10-22) was removed.

This function, and also all other functions below find_bisection() to
be complete, will be called with an empty commit list if all commits
are _uninteresting_.  So the functions must be prepared for it.

This commit, instead of restoring the check, moves the clean-up code
into the loop.  To do that this commit changes the non-last-case
branch in the loop to a last-case branch, and clean-up unused trailing
elements there.

We could, on the other hand, do a big "if list" condition at the very
beginning.  But, that doesn't sound right for the current code base.
No other functions does that but all blocks in the functions are
tolerant to an empty list.

By the way, as you can tell from the non-last-case branch we had in
the loop, this fix shouldn't cause a pipeline stall on every iteration
on modern processors with a branch predictor.

Signed-off-by: Yasushi ShOJI <yasushi.shoji@gmail.com>
---
 bisect.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

diff --git a/bisect.c b/bisect.c
index fb3e44903..cec4a537f 100644
--- a/bisect.c
+++ b/bisect.c
@@ -218,7 +218,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		cnt++;
 	}
 	QSORT(array, cnt, compare_commit_dist);
-	for (p = list, i = 0; i < cnt; i++) {
+	for (p = list, i = 0; i < cnt; i++, p = p->next) {
 		struct object *obj = &(array[i].commit->object);
 
 		strbuf_reset(&buf);
@@ -226,11 +226,13 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		add_name_decoration(DECORATION_NONE, buf.buf, obj);
 
 		p->item = array[i].commit;
-		if (i < cnt - 1)
-			p = p->next;
+
+		if (i == cnt) {
+			/* clean-up unused elements if any */
+			free_commit_list(p->next);
+			p->next = NULL;
+		}
 	}
-	free_commit_list(p->next);
-	p->next = NULL;
 	strbuf_release(&buf);
 	free(array);
 	return list;
-- 
2.15.1

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Christian Couder]

Hi,

On Mon, Jan 8, 2018 at 3:45 PM, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:
> Hi all,
>
> Thank you guys for insightful help.  I just read the code and now I understand
> what you guys are saying.  Yeah, I can say the fix is "spot on".
>
> But, to be honest, it's hard to see why you need "if (p)" at  the first glance.
> So, how about this fix, instead?

+    for (p = list, i = 0; i < cnt; i++, p = p->next) {

Here "i" can reach "cnt - 1" at most, so ...

+        if (i == cnt) {
+            /* clean-up unused elements if any */
+            free_commit_list(p->next);
+            p->next = NULL;
+        }

... "i == cnt" is always false above. I think it should be "i == cnt - 1".

And with your code one can wonder why the cleanup is part of the loop.

> I also found a bug in show_list().  I'm attaching a patch as well.

Could you send it inline as explained in Documentation/SubmittingPatches?

Thanks,
Christian.

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Yasushi SHOJI]

Hi,

On Tue, Jan 9, 2018 at 12:09 AM, Christian Couder
<christian.couder@gmail.com> wrote:
> ... "i == cnt" is always false above. I think it should be "i == cnt - 1".

uga.  Thanks.  That's stupid of me.

> And with your code one can wonder why the cleanup is part of the loop.

OK.  I have nothing to offer, then.  Thank you for taking care of this!

>> I also found a bug in show_list().  I'm attaching a patch as well.
>
> Could you send it inline as explained in Documentation/SubmittingPatches?

Done that.

Thanks,
-- 
          yashi

Re: [BUG] v2.16.0-rc0 seg faults when git bisect skip

[Junio C Hamano]

Yasushi SHOJI <yasushi.shoji@gmail.com> writes:

> The patch (actually, I've tested the one in pu, 2e9fdc795cb27) avoids
> the seg fault for sure, but the question is:
>
> When does the list allowed to contain NULLs?

A very legitimate question.  With the proposed log message alone, it
is even tempting to declare that the change may merely be sweeping
the issue under the rug.  A bit better explanation is needed, at
least.