From 7eca15bf0a08747c3f79445ca59ed86eb1ced4fd Mon Sep 17 00:00:00 2001
From: Dmitry Vyukov <dvyukov@google.com>
Date: Tue, 17 Nov 2020 16:39:02 +0100
Subject: pkg/kconfig: add minimization test with dependent configs

Test for case described in:
https://groups.google.com/g/syzkaller/c/c1J1kzzW7Ew/m/CeyEJm04AQAJ

It seems to work as is (mostly).
Fix parsing of the very last kconfig config (currently it's dropped).
s/menuend/endmenu/ in error message.
Sort dependencies so that we can express the test.
But none of this should have affected actual config minimization.
---
 pkg/kconfig/kconfig.go       |  5 +++--
 pkg/kconfig/minimize.go      | 15 ++++++++++-----
 pkg/kconfig/minimize_test.go | 28 ++++++++++++++++++++++++++++
 3 files changed, 41 insertions(+), 7 deletions(-)

(limited to 'pkg')

diff --git a/pkg/kconfig/kconfig.go b/pkg/kconfig/kconfig.go
index 40e19b9af..273495390 100644
--- a/pkg/kconfig/kconfig.go
+++ b/pkg/kconfig/kconfig.go
@@ -166,6 +166,7 @@ func (kp *kconfigParser) parseFile() {
 			_ = kp.ConsumeLine()
 		}
 	}
+	kp.endCurrent()
 }
 
 func (kp *kconfigParser) parseLine() {
@@ -347,7 +348,7 @@ func (kp *kconfigParser) pushCurrent(m *Menu) {
 func (kp *kconfigParser) popCurrent() {
 	kp.endCurrent()
 	if len(kp.stack) < 2 {
-		kp.failf("unbalanced menuend")
+		kp.failf("unbalanced endmenu")
 		return
 	}
 	last := kp.stack[len(kp.stack)-1]
@@ -375,7 +376,7 @@ func (kp *kconfigParser) endCurrent() {
 		return
 	}
 	if len(kp.stack) == 0 {
-		kp.failf("unbalanced menuend")
+		kp.failf("unbalanced endmenu")
 		return
 	}
 	top := kp.stack[len(kp.stack)-1]
diff --git a/pkg/kconfig/minimize.go b/pkg/kconfig/minimize.go
index 7acf2b349..bbcb95414 100644
--- a/pkg/kconfig/minimize.go
+++ b/pkg/kconfig/minimize.go
@@ -28,7 +28,7 @@ func (kconf *KConfig) Minimize(base, full *ConfigFile, pred func(*ConfigFile) (b
 	}
 	// Since base does not crash, full config is our best bet for now.
 	current := full.clone()
-	var suspects map[string]bool
+	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.
@@ -48,11 +48,11 @@ top:
 			trace.log("trying half: %v", part)
 			closure := kconf.addDependencies(base, full, part)
 			candidate := base.clone()
-			// 1. Always move all non-tristate configs from full to base as we don't minimize them.
+			// 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 {
+			for _, cfg := range closure {
 				candidate.Set(cfg, Yes)
 			}
 			res, err := pred(candidate)
@@ -90,7 +90,7 @@ func (kconf *KConfig) missingConfigs(base, full *ConfigFile) (tristate []string,
 	return
 }
 
-func (kconf *KConfig) addDependencies(base, full *ConfigFile, configs []string) map[string]bool {
+func (kconf *KConfig) addDependencies(base, full *ConfigFile, configs []string) []string {
 	closure := make(map[string]bool)
 	for _, cfg := range configs {
 		closure[cfg] = true
@@ -102,7 +102,12 @@ func (kconf *KConfig) addDependencies(base, full *ConfigFile, configs []string)
 			}
 		}
 	}
-	return closure
+	var sorted []string
+	for cfg := range closure {
+		sorted = append(sorted, cfg)
+	}
+	sort.Strings(sorted)
+	return sorted
 }
 
 type traceLogger struct{ io.Writer }
diff --git a/pkg/kconfig/minimize_test.go b/pkg/kconfig/minimize_test.go
index 24738ebeb..28dca33bd 100644
--- a/pkg/kconfig/minimize_test.go
+++ b/pkg/kconfig/minimize_test.go
@@ -21,6 +21,18 @@ config C
 config D
 config I
 config S
+
+menuconfig HAMRADIO
+	depends on NET && !S390
+	bool "Amateur Radio support"
+
+config AX25
+	tristate "Amateur Radio AX.25 Level 2 protocol"
+	depends on HAMRADIO
+
+config ROSE
+	tristate "Amateur Radio X.25 PLP (Rose)"
+	depends on AX25
 `
 		baseConfig = `
 CONFIG_A=y
@@ -33,6 +45,9 @@ CONFIG_C=y
 CONFIG_D=y
 CONFIG_I=42
 CONFIG_S="foo"
+CONFIG_HAMRADIO=y
+CONFIG_AX25=y
+CONFIG_ROSE=y
 `
 	)
 	type Test struct {
@@ -61,6 +76,19 @@ CONFIG_A=y
 CONFIG_I=42
 CONFIG_S="foo"
 CONFIG_C=y
+`,
+		},
+		{
+			pred: func(cf *ConfigFile) (bool, error) {
+				return cf.Value("HAMRADIO") == Yes && cf.Value("AX25") == Yes && cf.Value("ROSE") == Yes, nil
+			},
+			result: `
+CONFIG_A=y
+CONFIG_I=42
+CONFIG_S="foo"
+CONFIG_AX25=y
+CONFIG_HAMRADIO=y
+CONFIG_ROSE=y
 `,
 		},
 	}
-- 
cgit mrf-deployment