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.

          yashi

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:

index 0fca17c02b..2f3008b078 100644
@@ -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

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.

---
 bisect.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

index 0fca17c02b..2f3008b078 100644
@@ -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

Hi,

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

Hi,

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 <[email protected]>
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.

: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

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

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

---
 t/t6030-bisect-porcelain.sh | 9 +++++++++
 1 file changed, 9 insertions(+)

index 8c2c6eaef8..190f0ce0ab 100755
@@ -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

Hi Martin,

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

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,

            yashi

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,

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.

           yashi

From d149a1348e94ea0246a10181751ce3bf9ba48198 Mon Sep 17 00:00:00 2001
From: Yasushi SHOJI <[email protected]>
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(-)

index 0fca17c02..fb3e44903 100644
@@ -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

From 2ec8823de3bd0ca8253ddbd07f58b66afcfabe96 Mon Sep 17 00:00:00 2001
From: Yasushi SHOJI <[email protected]>
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.

---
 bisect.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

index fb3e44903..cec4a537f 100644
@@ -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

Hi,

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

uga. Thanks. That's stupid of me.

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

Done that.

Thanks,

          yashi

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.