pkg/bisect: try to reidentify commit rebased after crash

When bisecting a breaking commit, syzkaller starts the bisection from
the commit recorded in the last crash for the given bug. Previously the
bisection was aborted should the commit no longer exist in the repo.

Now we try to reidentify the breaking commit. For git pretty much the
best we can do is to search a commit reachable from HEAD with the same
title. Other VCS systems might have something better.

Syzkaller will still first validate that the start commit is indeed
broken in the way it expects. This prevents syzkaller from getting
confused should we accidentally pick a completely unrelated commit.

2 files changed, 102 insertions, 44 deletions

diff --git a/pkg/bisect/bisect.go b/pkg/bisect/bisect.go
index 1813abaa5..939101a6e 100644
--- a/pkg/bisect/bisect.go
+++ b/pkg/bisect/bisect.go
@@ -32,12 +32,13 @@ type Config struct {
 }
 
 type KernelConfig struct {
-	Repo    string
-	Branch  string
-	Commit  string
-	Cmdline string
-	Sysctl  string
-	Config  []byte
+	Repo        string
+	Branch      string
+	Commit      string
+	CommitTitle string
+	Cmdline     string
+	Sysctl      string
+	Config      []byte
 	// Baseline configuration is used in commit bisection. If the crash doesn't reproduce
 	// with baseline configuratopm config bisection is run. When triggering configuration
 	// option is found provided baseline configuration is modified according the bisection
@@ -148,6 +149,7 @@ func runImpl(cfg *Config, repo vcs.Repo, inst instance.Env) (*Result, error) {
 	if err != nil {
 		return nil, err
 	}
+	defer env.repo.SwitchCommit(head.Hash)
 	env.head = head
 	hostname, err := os.Hostname()
 	if err != nil {
@@ -216,11 +218,17 @@ func (env *env) bisect() (*Result, error) {
 	if _, err := env.inst.BuildSyzkaller(cfg.Syzkaller.Repo, cfg.Syzkaller.Commit); err != nil {
 		return nil, err
 	}
-	com, err := env.repo.CheckoutCommit(cfg.Kernel.Repo, cfg.Kernel.Commit)
+
+	cfg.Kernel.Commit, err = env.identifyRewrittenCommit()
+	if err != nil {
+		return nil, err
+	}
+	com, err := env.repo.SwitchCommit(cfg.Kernel.Commit)
 	if err != nil {
 		return nil, err
 	}
 
+	env.log("ensuring issue is reproducible on original commit %v\n", cfg.Kernel.Commit)
 	env.commit = com
 	env.kernelConfig = cfg.Kernel.Config
 	testRes, err := env.test()
@@ -302,6 +310,42 @@ func (env *env) bisect() (*Result, error) {
 	return res, nil
 }
 
+func (env *env) identifyRewrittenCommit() (string, error) {
+	cfg := env.cfg
+	_, err := env.repo.CheckoutBranch(cfg.Kernel.Repo, cfg.Kernel.Branch)
+	if err != nil {
+		return cfg.Kernel.Commit, err
+	}
+	contained, err := env.repo.Contains(cfg.Kernel.Commit)
+	if err != nil || contained {
+		return cfg.Kernel.Commit, err
+	}
+
+	// We record the tested kernel commit when syzkaller triggers a crash. These commits can become
+	// unreachable after the crash was found, when the history of the tested kernel branch was
+	// rewritten. The commit might have been completely deleted from the branch or just changed in
+	// some way. Some branches like linux-next are often and heavily rewritten (aka rebased).
+	// This can also happen when changing the branch you fuzz in an existing syz-manager config.
+	// This makes sense when a downstream kernel fork rebased on top of a new upstream version and
+	// you don't want syzkaller to report all your old bugs again.
+	if cfg.Kernel.CommitTitle == "" {
+		// This can happen during a manual bisection, when only a hash is given.
+		return cfg.Kernel.Commit, fmt.Errorf(
+			"commit %v not reachable in branch '%v' and no commit title available",
+			cfg.Kernel.Commit, cfg.Kernel.Branch)
+	}
+	commit, err := env.repo.GetCommitByTitle(cfg.Kernel.CommitTitle)
+	if err != nil {
+		return cfg.Kernel.Commit, err
+	}
+	if commit == nil {
+		return cfg.Kernel.Commit, fmt.Errorf(
+			"commit %v not reachable in branch '%v'", cfg.Kernel.Commit, cfg.Kernel.Branch)
+	}
+	env.log("rewritten commit %v reidentified by title '%v'\n", commit.Hash, cfg.Kernel.CommitTitle)
+	return commit.Hash, nil
+}
+
 func (env *env) minimizeConfig() (*testResult, error) {
 	// Find minimal configuration based on baseline to reproduce the crash.
 	testResults := make(map[hash.Sig]*testResult)
diff --git a/pkg/bisect/bisect_test.go b/pkg/bisect/bisect_test.go
index 1cd0dc261..7930e545c 100644
--- a/pkg/bisect/bisect_test.go
+++ b/pkg/bisect/bisect_test.go
@@ -108,7 +108,7 @@ func createTestRepo(t *testing.T) string {
 	return baseDir
 }
 
-func runBisection(t *testing.T, baseDir string, test BisectionTest) (*Result, error) {
+func testBisection(t *testing.T, baseDir string, test BisectionTest) {
 	r, err := vcs.NewRepo(targets.TestOS, targets.TestArch64, baseDir, vcs.OptPrecious)
 	if err != nil {
 		t.Fatal(err)
@@ -131,7 +131,9 @@ func runBisection(t *testing.T, baseDir string, test BisectionTest) (*Result, er
 		},
 		Kernel: KernelConfig{
 			Repo:           baseDir,
+			Branch:         "master",
 			Commit:         sc.Hash,
+			CommitTitle:    sc.Title,
 			Config:         []byte("original config"),
 			BaselineConfig: []byte(test.baselineConfig),
 		},
@@ -141,8 +143,54 @@ func runBisection(t *testing.T, baseDir string, test BisectionTest) (*Result, er
 		r:    r,
 		test: test,
 	}
+
+	checkBisectionError := func(test BisectionTest, res *Result, err error) {
+		if test.expectErr != (err != nil) {
+			t.Fatalf("expected error %v, got %v", test.expectErr, err)
+		}
+		if err != nil {
+			if res != nil {
+				t.Fatalf("got both result and error: '%v' %+v", err, *res)
+			}
+		} else {
+			checkBisectionResult(t, test, res)
+		}
+	}
+
 	res, err := runImpl(cfg, r, inst)
-	return res, err
+	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)
+}
+
+func checkBisectionResult(t *testing.T, test BisectionTest, res *Result) {
+	if len(res.Commits) != test.commitLen {
+		t.Fatalf("expected %d commits got %d commits", test.commitLen, len(res.Commits))
+	}
+	expectedTitle := fmt.Sprint(test.culprit)
+	if len(res.Commits) == 1 && expectedTitle != res.Commits[0].Title {
+		t.Fatalf("expected commit '%v' got '%v'", expectedTitle, res.Commits[0].Title)
+	}
+	if test.expectRep != (res.Report != nil) {
+		t.Fatalf("got rep: %v, want: %v", res.Report, test.expectRep)
+	}
+	if res.NoopChange != test.noopChange {
+		t.Fatalf("got noop change: %v, want: %v", res.NoopChange, test.noopChange)
+	}
+	if res.IsRelease != test.isRelease {
+		t.Fatalf("got release change: %v, want: %v", res.IsRelease, test.isRelease)
+	}
+	if test.oldestLatest != 0 && fmt.Sprint(test.oldestLatest) != res.Commit.Title ||
+		test.oldestLatest == 0 && res.Commit != nil {
+		t.Fatalf("expected latest/oldest: %v got '%v'",
+			test.oldestLatest, res.Commit.Title)
+	}
+	if test.resultingConfig != "" && test.resultingConfig != string(res.Config) {
+		t.Fatalf("expected resulting config: %q got %q",
+			test.resultingConfig, res.Config)
+	}
 }
 
 type BisectionTest struct {
@@ -441,41 +489,7 @@ func TestBisectionResults(t *testing.T) {
 				defer func() {
 					repoCache <- repoDir
 				}()
-				res, err := runBisection(t, repoDir, test)
-				if test.expectErr != (err != nil) {
-					t.Fatalf("returned error: %v", err)
-				}
-				if err != nil {
-					if res != nil {
-						t.Fatalf("got both result and error: '%v' %+v", err, *res)
-					}
-					return
-				}
-				if len(res.Commits) != test.commitLen {
-					t.Fatalf("expected %d commits got %d commits", test.commitLen, len(res.Commits))
-				}
-				expectedTitle := fmt.Sprint(test.culprit)
-				if len(res.Commits) == 1 && expectedTitle != res.Commits[0].Title {
-					t.Fatalf("expected commit '%v' got '%v'", expectedTitle, res.Commits[0].Title)
-				}
-				if test.expectRep != (res.Report != nil) {
-					t.Fatalf("got rep: %v, want: %v", res.Report, test.expectRep)
-				}
-				if res.NoopChange != test.noopChange {
-					t.Fatalf("got noop change: %v, want: %v", res.NoopChange, test.noopChange)
-				}
-				if res.IsRelease != test.isRelease {
-					t.Fatalf("got release change: %v, want: %v", res.IsRelease, test.isRelease)
-				}
-				if test.oldestLatest != 0 && fmt.Sprint(test.oldestLatest) != res.Commit.Title ||
-					test.oldestLatest == 0 && res.Commit != nil {
-					t.Fatalf("expected latest/oldest: %v got '%v'",
-						test.oldestLatest, res.Commit.Title)
-				}
-				if test.resultingConfig != "" && test.resultingConfig != string(res.Config) {
-					t.Fatalf("expected resulting config: %q got %q",
-						test.resultingConfig, res.Config)
-				}
+				testBisection(t, repoDir, test)
 			})
 		}
 	})