pkg/bisect: fix bisection fails for recently introduced bugs

[a-nogikh]

Linux source tree history is convoluted: tons of merges in and out of dozens of trees. There are also cases when history branches off at an older revision, some changes are made, and then they are only merged months later.

We seem to have trouble handling the case when git bisect visits those branches of history, which, though merged into the mainline after the bug was already there, did not have the bug at the moment of their branch-off. We correctly conclude that the revision has no bug and the bisection process goes off the rails.

Example:

Bug: https://syzkaller.appspot.com/bug?extid=70b97abe3e253d1c3f8e, bisection log: https://syzkaller.appspot.com/x/bisect.txt?x=11aeb085a80000

We determine that the bug was indeed present at the faulty revision:

testing commit a901a3568fd26ca9c4a82d8bc5ed5b3ed844d451 gcc
compiler: gcc (Debian 12.2.0-14) 12.2.0, GNU ld (GNU Binutils for Debian) 2.40
kernel signature: 0e894ff22fe5ae2b96cbda77efa02a645cbe1ecd453a80d3f5637010c996c241
<..>
representative crash: general protection fault in mt_validate, types: [UNKNOWN BUG]

The bug is not present on HEAD:

testing current HEAD 0108963f14e96abcfae0c4d1186c237cfb1a7fad
testing commit 0108963f14e96abcfae0c4d1186c237cfb1a7fad gcc
compiler: gcc (Debian 12.2.0-14) 12.2.0, GNU ld (GNU Binutils for Debian) 2.40
kernel signature: 27c563f3b93301d84e10c837317d579d37b405be596cce6ff88b2833609caa5a
all runs: OK

And then all following bisection steps finish with all runs: OK, which lands us at

commit ef513aa7aa5038d2f53e9f2932af5006f37ed0b6
Author: Luca Weiss <luca@z3ntu.xyz>
Date:   Fri Apr 14 01:17:49 2023 +0200

    dt-bindings: iio: adc: qcom,spmi-vadc: Allow 1/16 for pre-scaling

Which is based on 6.1:

$ git show ef513aa7aa5038d2f53e9f2932af5006f37ed0b6^1
commit ac9a78681b921877518763ba0e89202254349d1b (tag: v6.4-rc1, tag: linux/v6.4-rc1)
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Sun May 7 13:34:35 2023 -0700

    Linux 6.4-rc1

We began to actively trigger this bug ~ month ago, when the mainline was already at v6.5.

[a-nogikh]

Some random ideas:

• When we do have a cause bisection result, the solution might be do bisect skip (or, rather, bisect good?) those revisions, from which the guilty commit is not reachable. This won't always help though -- we don't really have many successful cause bisections.
• An alternative solution is to treat the earliest hash where we detected the bug as such. But it will hurt fix bisections for older bugs -- we'd be more likely to finish at some merge commit into the mainline rather than the real bug fix.
  • Upd: that should actually be the behavior of --first-parent.
• When we test a git revision, look at the merge base between the known bad commit and the currently tested revision
  • If it's the known bad commit (that is, bad commit is definitely reachable from the tested revision), just proceed to testing.
  • If it's another commit, we need to ensure it actually contained the bug. Hopefully, if we remember the oldest retested commit, we won't need too many extra test() runs.