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

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.

On Wed, Jan 03 2018, Yasushi SHOJI jotted:

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:

On 3 January 2018 at 15:21, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

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

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(-)

Hi,

On Thu, Jan 4, 2018 at 3:26 AM, Martin Ågren <martin.agren@gmail.com> wrote:

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,

Hi,

On Fri, Jan 5, 2018 at 11:45 AM, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:

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

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".

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:

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(+)

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:

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?

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

Regards,

On 6 January 2018 at 15:27, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:

All of this matches my understanding.

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.)

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?

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

Hi Yasushi,

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

Yes.

Yes.

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.

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.

Yeah, mistakes unfortunately happens :-)

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

Thanks for your reports and test cases, Christian.

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.

Hi,

On Mon, Jan 8, 2018 at 3:45 PM, Yasushi SHOJI <yasushi.shoji@gmail.com> wrote:

+    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.

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

Thanks, Christian.

Hi,

On Tue, Jan 9, 2018 at 12:09 AM, Christian Couder <christian.couder@gmail.com> wrote:

uga.  Thanks.  That's stupid of me.

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

Done that.

Thanks,

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

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.