pkg/kconfig: rewrite Minimize()

1) Use the generic bisection implementation in pkg/bisect. It adds the
   support of identifying several necessary config diffs at once.
2) For now, limit the number of minimization iterations to 6. It's a
   lengthy process and we don't want to spend too much time doing this.
3) Bisect over leaf configuration options -- that is, those no other
   config depends upon. This should make diff split during bisection
   more reliable.
4) Save all intermediate configs to the debug files folder.

5 files changed, 90 insertions, 68 deletions

diff --git a/pkg/kconfig/cause.config b/pkg/kconfig/cause.config
deleted file mode 100644
index 977642377..000000000
--- a/pkg/kconfig/cause.config
+++ /dev/null
@@ -1,3 +0,0 @@
-CONFIG_AX25=y
-CONFIG_HAMRADIO=y
-CONFIG_ROSE=y
diff --git a/pkg/kconfig/minimize.go b/pkg/kconfig/minimize.go
index cbeaba08b..a9430848a 100644
--- a/pkg/kconfig/minimize.go
+++ b/pkg/kconfig/minimize.go
@@ -4,10 +4,11 @@
 package kconfig
 
 import (
+	"fmt"
 	"sort"
 
+	"github.com/google/syzkaller/pkg/bisect/minimize"
 	"github.com/google/syzkaller/pkg/debugtracer"
-	"github.com/google/syzkaller/pkg/osutil"
 )
 
 // Minimize finds an equivalent with respect to the provided predicate, but smaller config.
@@ -15,68 +16,52 @@ import (
 // It is also assumed that base and full are not just two completely arbitrary configs, but full it produced from base
 // mostly by adding more configs. The minimization procedure thus consists of figuring out what set of configs that
 // are present in full and are not present in base affect the predicate.
+// If maxPredRuns is non-zero, minimization will stop after the specified number of runs.
 func (kconf *KConfig) Minimize(base, full *ConfigFile, pred func(*ConfigFile) (bool, error),
-	dt debugtracer.DebugTracer) (*ConfigFile, error) {
-	diff, other := kconf.missingConfigs(base, full)
-	dt.Log("kconfig minimization: base=%v full=%v diff=%v", len(base.Configs), len(full.Configs), len(diff))
-	// First, check the base config as is, it is the smallest we can possibly get.
-	if res, err := pred(base); err != nil {
-		return nil, err
-	} else if res {
-		dt.Log("base config crashes")
-		return base, nil
-	}
-	// Since base does not crash, full config is our best bet for now.
-	current := full.Clone()
-	var suspects []string
-	// Take half of the diff between base and full, apply to base and test.
-	// If this candidate config crashes, we commit it as new full and repeat the process.
-	// If it does not crash, try another half.
-	// If the crash is caused by a single config, this algorithm is guaranteed to find it.
-	// If the crash is caused by multiple configs, this algorithm will most likely find them (along with some
-	// additional unrelated configs that happened to be in the same half). However, amount of unrelated configs
-	// can be quite large if we are unlucky. Also note that we sort configs so that related configs are most
-	// likely situated together.
-	// Numerous improvements are possible for this simple algorithm.
-	// 1. We could split the config onto 4 parts and try all pairs, this should find all pairs of configs reliably.
-	// 2. We could continue trying to reduce a part even if removing the whole part fails. I.e. we try to remove
-	//    a half and it fails, we can try to remove half of the half, maybe that will succeed.
-top:
-	for len(diff) >= 2 {
-		half := len(diff) / 2
-		for _, part := range [][]string{diff[:half], diff[half:]} {
-			dt.Log("trying half: %v", part)
-			closure := kconf.addDependencies(base, full, part)
-			candidate := base.Clone()
-			// Always move all non-tristate configs from full to base as we don't minimize them.
-			for _, cfg := range other {
-				candidate.Set(cfg.Name, cfg.Value)
-			}
-			for _, cfg := range closure {
-				candidate.Set(cfg, Yes)
-			}
-			res, err := pred(candidate)
-			if err != nil {
-				return nil, err
-			}
-			if res {
-				dt.Log("half crashed")
-				diff = part
-				current = candidate
-				suspects = closure
-				continue top
-			}
+	maxSteps int, dt debugtracer.DebugTracer) (*ConfigFile, error) {
+	diff, other := kconf.missingLeafConfigs(base, full)
+	dt.Log("kconfig minimization: base=%v full=%v leaves diff=%v", len(base.Configs), len(full.Configs), len(diff))
+
+	diffToConfig := func(part []string) (*ConfigFile, []string) {
+		if len(part) == 0 {
+			// We're testing the baseline config only.
+			return base, nil
+		}
+		suspects := kconf.addDependencies(base, full, part)
+		candidate := base.Clone()
+		// Always move all non-tristate configs from full to base as we don't minimize them.
+		for _, cfg := range other {
+			candidate.Set(cfg.Name, cfg.Value)
 		}
-		dt.Log("both halves did not crash")
-		break
+		for _, cfg := range suspects {
+			candidate.Set(cfg, Yes)
+		}
+		return candidate, suspects
+	}
+	var step int
+	minimizePred := func(diffs []string) (bool, error) {
+		step++
+		config, _ := diffToConfig(diffs)
+		dt.SaveFile(fmt.Sprintf("step_%d.config", step), config.Serialize())
+		return pred(config)
 	}
+	result, err := minimize.Slice(
+		minimize.Config[string]{
+			Pred:     minimizePred,
+			MaxSteps: maxSteps,
+			Logf:     dt.Log,
+		},
+		diff,
+	)
+	if err != nil {
+		return nil, err
+	}
+	config, suspects := diffToConfig(result)
 	if suspects != nil {
-		dt.Log("resulting configs: %v", suspects)
+		dt.Log("minimized to %d configs; suspects: %v", len(result), suspects)
 		kconf.writeSuspects(dt, suspects)
-	} else {
-		dt.Log("only full config crashes")
 	}
-	return current, nil
+	return config, nil
 }
 
 func (kconf *KConfig) missingConfigs(base, full *ConfigFile) (tristate []string, other []*Config) {
@@ -91,6 +76,26 @@ func (kconf *KConfig) missingConfigs(base, full *ConfigFile) (tristate []string,
 	return
 }
 
+// missingLeafConfigs returns the set of configs no other config depends upon.
+func (kconf *KConfig) missingLeafConfigs(base, full *ConfigFile) ([]string, []*Config) {
+	diff, other := kconf.missingConfigs(base, full)
+	needed := map[string]bool{}
+	for _, config := range diff {
+		for _, needs := range kconf.addDependencies(base, full, []string{config}) {
+			if needs != config {
+				needed[needs] = true
+			}
+		}
+	}
+	var leaves []string
+	for _, key := range diff {
+		if !needed[key] {
+			leaves = append(leaves, key)
+		}
+	}
+	return leaves, other
+}
+
 func (kconf *KConfig) addDependencies(base, full *ConfigFile, configs []string) []string {
 	closure := make(map[string]bool)
 	for _, cfg := range configs {
@@ -117,9 +122,8 @@ func (kconf *KConfig) writeSuspects(dt debugtracer.DebugTracer, suspects []strin
 	cf := &ConfigFile{
 		Map: make(map[string]*Config),
 	}
-
 	for _, cfg := range suspects {
 		cf.Set(cfg, Yes)
 	}
-	osutil.WriteFile(CauseConfigFile, cf.Serialize())
+	dt.SaveFile(CauseConfigFile, cf.Serialize())
 }
diff --git a/pkg/kconfig/minimize_test.go b/pkg/kconfig/minimize_test.go
index 1e1d2b0f2..fab700dd5 100644
--- a/pkg/kconfig/minimize_test.go
+++ b/pkg/kconfig/minimize_test.go
@@ -5,10 +5,12 @@ package kconfig
 
 import (
 	"fmt"
+	"strings"
 	"testing"
 
 	"github.com/google/syzkaller/pkg/debugtracer"
 	"github.com/google/syzkaller/sys/targets"
+	"github.com/stretchr/testify/assert"
 )
 
 func TestMinimize(t *testing.T) {
@@ -91,6 +93,19 @@ CONFIG_HAMRADIO=y
 CONFIG_ROSE=y
 `,
 		},
+		{
+			// Check if it works fine with several diffs.
+			pred: func(cf *ConfigFile) (bool, error) {
+				return cf.Value("D") != No && cf.Value("C") != No, nil
+			},
+			result: `
+CONFIG_A=y
+CONFIG_I=42
+CONFIG_S="foo"
+CONFIG_C=y
+CONFIG_D=y
+`,
+		},
 	}
 	kconf, err := ParseData(targets.Get("linux", "amd64"), []byte(kconfig), "kconf")
 	if err != nil {
@@ -106,14 +121,14 @@ CONFIG_ROSE=y
 	}
 	for i, test := range tests {
 		t.Run(fmt.Sprint(i), func(t *testing.T) {
-			res, err := kconf.Minimize(base, full, test.pred, &debugtracer.TestTracer{T: t})
+			res, err := kconf.Minimize(base, full, test.pred, 0, &debugtracer.TestTracer{T: t})
 			if err != nil {
 				t.Fatal(err)
 			}
 			result := string(res.Serialize())
-			if result != test.result {
-				t.Fatalf("got:\n%v\n\nwant:\n%s", result, test.result)
-			}
+			assert.ElementsMatch(t,
+				strings.Split(result, "\n"),
+				strings.Split(test.result, "\n"))
 		})
 	}
 }
diff --git a/pkg/vcs/linux.go b/pkg/vcs/linux.go
index c6effd58a..341e488f4 100644
--- a/pkg/vcs/linux.go
+++ b/pkg/vcs/linux.go
@@ -379,7 +379,13 @@ type minimizeLinuxCtx struct {
 func (ctx *minimizeLinuxCtx) minimizeAgainst(base *kconfig.ConfigFile) error {
 	base = base.Clone()
 	ctx.transform(base)
-	minConfig, err := ctx.kconf.Minimize(base, ctx.config, ctx.pred, ctx)
+	// Don't do too many minimization runs, it will make bug bisections too long.
+	// The purpose is only to reduce the number of build/boot/test errors due to bugs
+	// in unrelated parts of the kernel.
+	// Bisection is not getting much faster with smaller configs, only more reliable,
+	// so there's a trade-off. Try to do best in 5 iterations, that's about 1.5 hours.
+	const minimizeRuns = 5
+	minConfig, err := ctx.kconf.Minimize(base, ctx.config, ctx.pred, minimizeRuns, ctx)
 	if err != nil {
 		return err
 	}
diff --git a/tools/syz-minconfig/minconfig.go b/tools/syz-minconfig/minconfig.go
index 450968cff..3a4693d08 100644
--- a/tools/syz-minconfig/minconfig.go
+++ b/tools/syz-minconfig/minconfig.go
@@ -54,7 +54,7 @@ func main() {
 	gt := &debugtracer.GenericTracer{
 		TraceWriter: os.Stdout,
 	}
-	res, err := kconf.Minimize(base, full, pred, gt)
+	res, err := kconf.Minimize(base, full, pred, 0, gt)
 	if err != nil {
 		tool.Fail(err)
 	}