From 668cb1fa42960ece96b7da8d9204e486ba6dcdf6 Mon Sep 17 00:00:00 2001 From: Aleksandr Nogikh Date: Fri, 16 Jun 2023 19:18:25 +0200 Subject: 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. --- pkg/kconfig/cause.config | 3 -- pkg/kconfig/minimize.go | 122 ++++++++++++++++++++++--------------------- pkg/kconfig/minimize_test.go | 23 ++++++-- pkg/vcs/linux.go | 8 ++- 4 files changed, 89 insertions(+), 67 deletions(-) delete mode 100644 pkg/kconfig/cause.config (limited to 'pkg') 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) { @@ -89,6 +91,19 @@ CONFIG_S="foo" CONFIG_AX25=y 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 `, }, } @@ -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 } -- cgit mrf-deployment