pkg/bisect: support bisections on other trees

The current code only supports fix/cause bisections when the known bad
commit is reachable from Kernel.Repo/Kernel.Branch.

Add a CrossTree parameter to pkg/bisect. If it's set to true and we're
doing a fix bisection, the bisection algorithm first operates with the
original commit message (i.e. checks that it indeed crashes the kernel
and performs config minimization), but the actual bisection starts from
the merge base of Commit and Branch.

We could have calculated the merge base outside of pkg/bisect and just
started the algorithm from that merge base, but there's a problem:
there's no guarantee that the kernel will build/boot with a syzbot
config at the merge base. So we take the commit known to work well and
then assume that the bug is also present on the merge base commit. If it
were not present, we wouldn't have found a fix commit from Branch
anyway.

2 files changed, 65 insertions, 13 deletions

diff --git a/pkg/bisect/bisect.go b/pkg/bisect/bisect.go
index 1a20a5cab..71cab039f 100644
--- a/pkg/bisect/bisect.go
+++ b/pkg/bisect/bisect.go
@@ -33,6 +33,10 @@ type Config struct {
 	Manager         *mgrconfig.Config
 	BuildSemaphore  *instance.Semaphore
 	TestSemaphore   *instance.Semaphore
+	// CrossTree specifies whether a cross tree bisection is to take place, i.e.
+	// Kernel.Commit is not reachable from Kernel.Branch.
+	// In this case, bisection starts from their merge base.
+	CrossTree bool
 }
 
 type KernelConfig struct {
@@ -317,6 +321,10 @@ func (env *env) bisect() (*Result, error) {
 
 func (env *env) identifyRewrittenCommit() (string, error) {
 	cfg := env.cfg
+	if cfg.Kernel.Commit != "" && cfg.CrossTree {
+		// If the failing commit is on another tree, just take it as is.
+		return cfg.Kernel.Commit, nil
+	}
 	_, err := env.repo.CheckoutBranch(cfg.Kernel.Repo, cfg.Kernel.Branch)
 	if err != nil {
 		return cfg.Kernel.Commit, err
@@ -417,6 +425,21 @@ func (env *env) commitRange() (*vcs.Commit, *vcs.Commit, []*testResult, *Result,
 }
 
 func (env *env) commitRangeForFix() (*vcs.Commit, *vcs.Commit, []*testResult, error) {
+	startCommit := env.commit
+	if env.cfg.CrossTree {
+		env.log("determining the merge base between %v and %v",
+			env.commit.Hash, env.head.Hash)
+		bases, err := env.repo.MergeBases(env.commit.Hash, env.head.Hash)
+		if err != nil {
+			return nil, nil, nil, err
+		}
+		if len(bases) != 1 {
+			env.log("expected 1 merge base, got %d", len(bases))
+			return nil, nil, nil, fmt.Errorf("expected 1 merge base, got %d", len(bases))
+		}
+		env.log("%s/%s is a merge base", bases[0].Hash, bases[0].Title)
+		startCommit = bases[0]
+	}
 	env.log("testing current HEAD %v", env.head.Hash)
 	if _, err := env.repo.SwitchCommit(env.head.Hash); err != nil {
 		return nil, nil, nil, err
@@ -428,7 +451,7 @@ func (env *env) commitRangeForFix() (*vcs.Commit, *vcs.Commit, []*testResult, er
 	if res.verdict != vcs.BisectGood {
 		return env.head, nil, []*testResult{res}, nil
 	}
-	return env.head, env.commit, []*testResult{res}, nil
+	return env.head, startCommit, []*testResult{res}, nil
 }
 
 func (env *env) commitRangeForCause() (*vcs.Commit, *vcs.Commit, []*testResult, error) {
diff --git a/pkg/bisect/bisect_test.go b/pkg/bisect/bisect_test.go
index 4dbed9e34..53426c86e 100644
--- a/pkg/bisect/bisect_test.go
+++ b/pkg/bisect/bisect_test.go
@@ -131,6 +131,12 @@ func createTestRepo(t *testing.T) string {
 			}
 		}
 	}
+	// Emulate another tree, that's needed for cross-tree tests.
+	repo.Git("checkout", "v8.0")
+	repo.Git("checkout", "-b", "v8-branch")
+	repo.CommitFileChange("850", "v8-branch")
+	repo.CommitChange("851")
+	repo.CommitChange("852")
 	return baseDir
 }
 
@@ -139,11 +145,19 @@ func testBisection(t *testing.T, baseDir string, test BisectionTest) {
 	if err != nil {
 		t.Fatal(err)
 	}
-	r.SwitchCommit("master")
+	if test.startCommitBranch != "" {
+		r.SwitchCommit(test.startCommitBranch)
+	} else {
+		r.SwitchCommit("master")
+	}
 	sc, err := r.GetCommitByTitle(fmt.Sprint(test.startCommit))
 	if err != nil {
 		t.Fatal(err)
 	}
+	if sc == nil {
+		t.Fatalf("start commit %v is not found", test.startCommit)
+	}
+	r.SwitchCommit("master")
 	cfg := &Config{
 		Fix:   test.fix,
 		Trace: &debugtracer.TestTracer{T: t},
@@ -163,6 +177,7 @@ func testBisection(t *testing.T, baseDir string, test BisectionTest) {
 			Config:         []byte("original config"),
 			BaselineConfig: []byte(test.baselineConfig),
 		},
+		CrossTree: test.crossTree,
 	}
 	inst := &testEnv{
 		t:    t,
@@ -188,10 +203,12 @@ func testBisection(t *testing.T, baseDir string, test BisectionTest) {
 
 	res, err := runImpl(cfg, r, inst)
 	checkBisectionError(test, res, err)
-	// Should be mitigated via GetCommitByTitle during bisection.
-	cfg.Kernel.Commit = fmt.Sprintf("fake-hash-for-%v-%v", cfg.Kernel.Commit, cfg.Kernel.CommitTitle)
-	res, err = runImpl(cfg, r, inst)
-	checkBisectionError(test, res, err)
+	if !test.crossTree {
+		// Should be mitigated via GetCommitByTitle during bisection.
+		cfg.Kernel.Commit = fmt.Sprintf("fake-hash-for-%v-%v", cfg.Kernel.Commit, cfg.Kernel.CommitTitle)
+		res, err = runImpl(cfg, r, inst)
+		checkBisectionError(test, res, err)
+	}
 }
 
 func checkBisectionResult(t *testing.T, test BisectionTest, res *Result) {
@@ -224,13 +241,15 @@ func checkBisectionResult(t *testing.T, test BisectionTest, res *Result) {
 
 type BisectionTest struct {
 	// input environment
-	name          string
-	fix           bool
-	startCommit   int
-	brokenStart   int
-	brokenEnd     int
-	infraErrStart int
-	infraErrEnd   int
+	name string
+	fix  bool
+	// By default it's set to "master".
+	startCommitBranch string
+	startCommit       int
+	brokenStart       int
+	brokenEnd         int
+	infraErrStart     int
+	infraErrEnd       int
 	// Range of commits that result in the same kernel binary signature.
 	sameBinaryStart int
 	sameBinaryEnd   int
@@ -252,6 +271,7 @@ type BisectionTest struct {
 	culprit         int
 	baselineConfig  string
 	resultingConfig string
+	crossTree       bool
 }
 
 var bisectionTests = []BisectionTest{
@@ -535,6 +555,15 @@ var bisectionTests = []BisectionTest{
 		infraErrEnd:   800,
 		culprit:       602,
 	},
+	{
+		name:              "fix-cross-tree",
+		fix:               true,
+		startCommit:       851,
+		startCommitBranch: "v8-branch",
+		commitLen:         1,
+		crossTree:         true,
+		culprit:           903,
+	},
 }
 
 func TestBisectionResults(t *testing.T) {