pkg/bisect: switch to kconfig.Minimize

Use the new kconfig.Minimize for config minization
instead of the config-bisect.pl script.
This is mostly just deleting code.

Also update tests:
 - minimization is now supposed to test the baseline config
   (update "testos" stub accordingly)
 - minimization is not supposed to return a config that does not build
   (a reasonable config minimization procedure can't arrive to such config),
   remove test that tests this

Update #2171

3 files changed, 21 insertions, 276 deletions

diff --git a/pkg/vcs/linux.go b/pkg/vcs/linux.go
index fc57532cb..b3c22e0d6 100644
--- a/pkg/vcs/linux.go
+++ b/pkg/vcs/linux.go
@@ -4,13 +4,10 @@
 package vcs
 
 import (
-	"bufio"
 	"bytes"
 	"fmt"
 	"io"
-	"io/ioutil"
 	"net/mail"
-	"os"
 	"path/filepath"
 	"regexp"
 	"sort"
@@ -304,166 +301,31 @@ func (ctx *linux) Minimize(original, baseline []byte, trace io.Writer,
 		fmt.Fprintf(trace, "# configuration already minimized\n")
 		return original, nil
 	}
-	bisectDir, err := ioutil.TempDir("", "syz-config-bisect")
+	kconf, err := kconfig.Parse(filepath.Join(ctx.git.dir, "Kconfig"))
 	if err != nil {
-		return nil, fmt.Errorf("failed to create temp dir for config bisect: %v", err)
+		return nil, fmt.Errorf("failed to parse Kconfig: %v", err)
 	}
-	defer os.RemoveAll(bisectDir)
-	kernelConfig := filepath.Join(bisectDir, "kernel.config")
-	kernelBaselineConfig := filepath.Join(bisectDir, "kernel.baseline_config")
-	if err := ctx.prepareConfigBisectEnv(kernelConfig, kernelBaselineConfig, original, baseline); err != nil {
-		return nil, err
-	}
-
-	fmt.Fprintf(trace, "# start config bisection\n")
-	configBisect := filepath.Join(ctx.git.dir, "tools", "testing", "ktest", "config-bisect.pl")
-	output, err := osutil.RunCmd(time.Hour, "", configBisect,
-		"-l", ctx.git.dir, "-r", "-b", ctx.git.dir, kernelBaselineConfig, kernelConfig)
+	originalConfig, err := kconfig.ParseConfigData(original, "original")
 	if err != nil {
-		return nil, fmt.Errorf("config bisect failed: %v", err)
-	}
-	fmt.Fprintf(trace, "# config-bisect.pl -r:\n%s", output)
-	for {
-		config, err := ioutil.ReadFile(filepath.Join(ctx.git.dir, ".config"))
-		if err != nil {
-			return nil, fmt.Errorf("failed to read .config: %v", err)
-		}
-
-		testRes, err := pred(config)
-		if err != nil {
-			return nil, err
-		}
-		if testRes == BisectSkip {
-			return nil, fmt.Errorf("unable to test, stopping config bisection")
-		}
-		verdict := "good"
-		if testRes == BisectBad {
-			verdict = "bad"
-		}
-
-		output1, err := osutil.RunCmd(time.Hour, "", configBisect,
-			"-l", ctx.git.dir, "-b", ctx.git.dir, kernelBaselineConfig, kernelConfig, verdict)
-		fmt.Fprintf(trace, "# config-bisect.pl %v:\n%s", verdict, output1)
-		output = append(output, output1...)
-		if err != nil {
-			if verr, ok := err.(*osutil.VerboseError); ok && verr.ExitCode == 2 {
-				break
-			}
-			return nil, fmt.Errorf("config bisect failed: %v", err)
-		}
-	}
-	fmt.Fprintf(trace, "# config_bisect.pl finished\n")
-	configOptions := ctx.parseConfigBisectLog(trace, output)
-	if len(configOptions) == 0 {
-		return nil, fmt.Errorf("no config changes in the config bisect log:\n%s", output)
-	}
-
-	// Parse minimalistic configuration to generate the crash.
-	minimizedConfig, err := ctx.generateMinConfig(configOptions, bisectDir, kernelBaselineConfig)
-	if err != nil {
-		return nil, fmt.Errorf("generating minimized config failed: %v", err)
-	}
-	return minimizedConfig, nil
-}
-
-func (ctx *linux) prepareConfigBisectEnv(kernelConfig, kernelBaselineConfig string, original, baseline []byte) error {
-	current, err := ctx.HeadCommit()
-	if err != nil {
-		return err
+		return nil, err
 	}
-
-	// Call EnvForCommit if some options needs to be adjusted.
-	bisectEnv, err := ctx.EnvForCommit("", current.Hash, original)
+	baselineConfig, err := kconfig.ParseConfigData(baseline, "baseline")
 	if err != nil {
-		return fmt.Errorf("failed create commit environment: %v", err)
+		return nil, err
 	}
-	if err := osutil.WriteFile(kernelConfig, bisectEnv.KernelConfig); err != nil {
-		return fmt.Errorf("failed to write config file: %v", err)
+	linuxAlterConfigs(originalConfig, nil)
+	linuxAlterConfigs(baselineConfig, nil)
+	kconfPred := func(candidate *kconfig.ConfigFile) (bool, error) {
+		res, err := pred(serialize(candidate))
+		return res == BisectBad, err
 	}
-
-	// Call EnvForCommit again if some options needs to be adjusted in baseline.
-	bisectEnv, err = ctx.EnvForCommit("", current.Hash, baseline)
+	minConfig, err := kconf.Minimize(baselineConfig, originalConfig, kconfPred, trace)
 	if err != nil {
-		return fmt.Errorf("failed create commit environment: %v", err)
-	}
-	if err := osutil.WriteFile(kernelBaselineConfig, bisectEnv.KernelConfig); err != nil {
-		return fmt.Errorf("failed to write minimum config file: %v", err)
-	}
-	return nil
-}
-
-//       Takes in config_bisect.pl output:
-//       Hmm, can't make any more changes without making good == bad?
-//       Difference between good (+) and bad (-)
-//        +DRIVER1=n
-//        +DRIVER2=n
-//        -DRIVER3=n
-//        -DRIVER4=n
-//        DRIVER5 n -> y
-//        DRIVER6 y -> n
-//       See good and bad configs for details:
-//       good: /mnt/work/linux/good_config.tmp
-//       bad:  /mnt/work/linux/bad_config.tmp
-func (ctx *linux) parseConfigBisectLog(trace io.Writer, bisectLog []byte) []string {
-	var configOptions []string
-	start := false
-	for s := bufio.NewScanner(bytes.NewReader(bisectLog)); s.Scan(); {
-		line := s.Text()
-		if strings.Contains(line, "See good and bad configs for details:") {
-			break
-		}
-		if !start {
-			if strings.Contains(line, "Difference between good (+) and bad (-)") {
-				start = true
-			}
-			continue
-		}
-		if strings.HasPrefix(line, "+") {
-			// This is option only in good config. Drop it as it's dependent
-			// on some option which is disabled in bad config.
-			continue
-		}
-		option, selection := "", ""
-		if strings.HasPrefix(line, "-") {
-			// -CONFIG_DRIVER_1=n
-			// Remove preceding -1 and split to option and selection
-			fields := strings.Split(strings.TrimPrefix(line, "-"), "=")
-			option = fields[0]
-			selection = fields[len(fields)-1]
-		} else {
-			// DRIVER_OPTION1 n -> y
-			fields := strings.Split(strings.TrimPrefix(line, " "), " ")
-			option = fields[0]
-			selection = fields[len(fields)-1]
-		}
-
-		configOptioon := "CONFIG_" + option + "=" + selection
-		if selection == "n" {
-			configOptioon = "# CONFIG_" + option + " is not set"
-		}
-		configOptions = append(configOptions, configOptioon)
+		return nil, err
 	}
-
-	fmt.Fprintf(trace, "# found config option changes %v\n", configOptions)
-	return configOptions
+	return serialize(minConfig), nil
 }
 
-func (ctx *linux) generateMinConfig(configOptions []string, outdir, baseline string) ([]byte, error) {
-	kernelAdditionsConfig := filepath.Join(outdir, "kernel.additions_config")
-	if err := osutil.WriteFile(kernelAdditionsConfig, []byte(strings.Join(configOptions, "\n"))); err != nil {
-		return nil, fmt.Errorf("failed to write config additions file: %v", err)
-	}
-
-	_, err := osutil.RunCmd(time.Hour, "", filepath.Join(ctx.git.dir, "scripts", "kconfig", "merge_config.sh"),
-		"-m", "-O", outdir, baseline, kernelAdditionsConfig)
-	if err != nil {
-		return nil, fmt.Errorf("config merge failed: %v", err)
-	}
-
-	minConfig, err := ioutil.ReadFile(filepath.Join(outdir, ".config"))
-	if err != nil {
-		return nil, fmt.Errorf("failed to read merged configuration: %v", err)
-	}
-	minConfig = append([]byte(fmt.Sprintf("%v, rev: %v\n", configBisectTag, prog.GitRevision)), minConfig...)
-	return minConfig, nil
+func serialize(cf *kconfig.ConfigFile) []byte {
+	return []byte(fmt.Sprintf("%v, rev: %v\n%s", configBisectTag, prog.GitRevision, cf.Serialize()))
 }
diff --git a/pkg/vcs/linux_test.go b/pkg/vcs/linux_test.go
deleted file mode 100644
index c2bfd17e0..000000000
--- a/pkg/vcs/linux_test.go
+++ /dev/null
@@ -1,120 +0,0 @@
-// Copyright 2019 syzkaller project authors. All rights reserved.
-// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
-
-package vcs
-
-import (
-	"bytes"
-	"fmt"
-	"io/ioutil"
-	"os"
-	"runtime"
-	"strings"
-	"testing"
-
-	"github.com/google/syzkaller/pkg/osutil"
-)
-
-type MinimizationTest struct {
-	config         string
-	baselineConfig string
-	// Output contains expected config option.
-	expectedConfig string
-	// Minimization is expected to pass or fail.
-	passing bool
-}
-
-func TestConfigMinimizer(t *testing.T) {
-	if runtime.GOOS != "linux" {
-		// The test config-bisect.pl uses bash-isms and can't run on OS that don't have bash.
-		t.Skipf("skipping on non-linux")
-	}
-	t.Parallel()
-	tests := []MinimizationTest{
-		{
-			config:         "CONFIG_ORIGINAL=y",
-			baselineConfig: "CONFIG_FAILING=y",
-			expectedConfig: "CONFIG_ORIGINAL=y",
-			passing:        false,
-		},
-		{
-			config:         "CONFIG_ORIGINAL=y",
-			baselineConfig: "CONFIG_REPRODUCES_CRASH=y",
-			expectedConfig: "CONFIG_REPRODUCES_CRASH=y",
-			passing:        true,
-		},
-		{
-			config:         configBisectTag,
-			baselineConfig: "CONFIG_NOT_REPRODUCE_CRASH=y",
-			expectedConfig: configBisectTag,
-			passing:        true,
-		},
-	}
-
-	baseDir := createTestLinuxRepo(t)
-	repo, err := NewRepo("linux", "64", baseDir)
-	if err != nil {
-		t.Fatalf("Unable to create repository")
-	}
-	pred := func(test []byte) (BisectResult, error) {
-		if strings.Contains(string(test), "CONFIG_REPRODUCES_CRASH=y") {
-			return BisectBad, nil
-		}
-		return BisectGood, nil
-	}
-
-	minimizer, ok := repo.(ConfigMinimizer)
-	if !ok {
-		t.Fatalf("Config minimization is not implemented")
-	}
-	for i, test := range tests {
-		t.Run(fmt.Sprint(i), func(t *testing.T) {
-			trace := new(bytes.Buffer)
-			outConfig, err := minimizer.Minimize([]byte(test.config),
-				[]byte(test.baselineConfig), trace, pred)
-			t.Log(trace.String())
-			if test.passing && err != nil {
-				t.Fatalf("failed to run Minimize: %v", err)
-			} else if test.passing && !strings.Contains(string(outConfig),
-				test.expectedConfig) {
-				t.Fatalf("output is not expected %v vs. %v", string(outConfig),
-					test.expectedConfig)
-			}
-		})
-	}
-}
-
-func createTestLinuxRepo(t *testing.T) string {
-	baseDir, err := ioutil.TempDir("", "syz-config-bisect-test")
-	if err != nil {
-		t.Fatal(err)
-	}
-	repo := CreateTestRepo(t, baseDir, "")
-	if !repo.SupportsBisection() {
-		t.Skip("bisection is unsupported by git (probably too old version)")
-	}
-	repo.CommitChange("commit")
-	repo.SetTag("v4.1")
-	err = os.MkdirAll(baseDir+"/tools/testing/ktest", 0755)
-	if err != nil {
-		t.Fatal(err)
-	}
-	err = os.MkdirAll(baseDir+"/scripts/kconfig", 0755)
-	if err != nil {
-		t.Fatal(err)
-	}
-
-	// Copy stubbed scripts used by config bisect.
-	err = osutil.CopyFile("testdata/linux/config-bisect.pl",
-		baseDir+"/tools/testing/ktest/config-bisect.pl")
-	if err != nil {
-		t.Fatal(err)
-	}
-	err = osutil.CopyFile("testdata/linux/merge_config.sh",
-		baseDir+"/scripts/kconfig/merge_config.sh")
-	if err != nil {
-		t.Fatal(err)
-	}
-
-	return baseDir
-}
diff --git a/pkg/vcs/testos.go b/pkg/vcs/testos.go
index c2957d3a2..ccabcf5f2 100644
--- a/pkg/vcs/testos.go
+++ b/pkg/vcs/testos.go
@@ -30,6 +30,11 @@ func (ctx *testos) EnvForCommit(binDir, commit string, kernelConfig []byte) (*Bi
 
 func (ctx *testos) Minimize(original, baseline []byte, trace io.Writer,
 	pred func(test []byte) (BisectResult, error)) ([]byte, error) {
+	if res, err := pred(baseline); err != nil {
+		return nil, err
+	} else if res == BisectBad {
+		return baseline, nil
+	}
 	switch string(baseline) {
 	case "minimize-fails":
 		return nil, fmt.Errorf("minimization failure")
@@ -37,8 +42,6 @@ func (ctx *testos) Minimize(original, baseline []byte, trace io.Writer,
 		config := []byte("new-minimized-config")
 		pred(config)
 		return config, nil
-	case "baseline-broken-build":
-		return []byte("broken-build"), nil
 	default:
 		return original, nil
 	}