From f0ba6809a8b86c889e26579ef4a7a2cba244e12f Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Thu, 15 Oct 2020 10:59:59 +0200 Subject: pkg/kconfig: add Kconfig parsing Update #2171 --- pkg/kconfig/fuzz.go | 5 + pkg/kconfig/kconfig.go | 407 ++++++++++++++++++++++++++++++++++++++++++++ pkg/kconfig/kconfig_test.go | 41 +++++ 3 files changed, 453 insertions(+) create mode 100644 pkg/kconfig/kconfig.go create mode 100644 pkg/kconfig/kconfig_test.go diff --git a/pkg/kconfig/fuzz.go b/pkg/kconfig/fuzz.go index 49f43efcb..4de9e91c8 100644 --- a/pkg/kconfig/fuzz.go +++ b/pkg/kconfig/fuzz.go @@ -3,6 +3,11 @@ package kconfig +func FuzzParseKConfig(data []byte) int { + ParseData(data, "kconfig") + return 0 +} + func FuzzParseExpr(data []byte) int { p := newParser(data, "expr") if !p.nextLine() { diff --git a/pkg/kconfig/kconfig.go b/pkg/kconfig/kconfig.go new file mode 100644 index 000000000..05c8d521f --- /dev/null +++ b/pkg/kconfig/kconfig.go @@ -0,0 +1,407 @@ +// Copyright 2020 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 kconfig implements parsing of the Linux kernel Kconfig and .config files +// and provides some algorithms to work with these files. For Kconfig reference see: +// https://www.kernel.org/doc/html/latest/kbuild/kconfig-language.html +package kconfig + +import ( + "fmt" + "io/ioutil" + "path/filepath" + "strings" + "sync" +) + +// KConfig represents a parsed Kconfig file (including includes). +type KConfig struct { + Root *Menu // mainmenu + Configs map[string]*Menu // only config/menuconfig entries +} + +// Menu represents a single hierarchical menu or config. +type Menu struct { + Kind MenuKind // config/menu/choice/etc + Type ConfigType // tristate/bool/string/etc + Name string // name without CONFIG_ + Elems []*Menu // sub-elements for menus + Parent *Menu // parent menu, non-nil for everythign except for mainmenu + + kconf *KConfig // back-link to the owning KConfig + prompts []prompt + defaults []defaultVal + dependsOn expr + visibleIf expr + deps map[string]bool + depsOnce sync.Once +} + +type prompt struct { + text string + cond expr +} + +type defaultVal struct { + val expr + cond expr +} + +type ( + MenuKind int + ConfigType int +) + +const ( + _ MenuKind = iota + MenuConfig + MenuGroup + MenuChoice + MenuComment +) +const ( + _ ConfigType = iota + TypeBool + TypeTristate + TypeString + TypeInt + TypeHex +) + +// DependsOn returns all transitive configs this config depends on. +func (m *Menu) DependsOn() map[string]bool { + m.depsOnce.Do(func() { + m.deps = make(map[string]bool) + if m.dependsOn != nil { + m.dependsOn.collectDeps(m.deps) + } + if m.visibleIf != nil { + m.visibleIf.collectDeps(m.deps) + } + var indirect []string + for cfg := range m.deps { + dep := m.kconf.Configs[cfg] + if dep == nil { + delete(m.deps, cfg) + continue + } + for cfg1 := range dep.DependsOn() { + indirect = append(indirect, cfg1) + } + } + for _, cfg := range indirect { + m.deps[cfg] = true + } + }) + return m.deps +} + +func (m *Menu) Prompt() string { + // TODO: check prompt conditions, some prompts may be not visible. + // If all prompts are not visible, then then menu if effectively disabled (at least for user). + for _, p := range m.prompts { + return p.text + } + return "" +} + +type kconfigParser struct { + *parser + includes []*parser + stack []*Menu + cur *Menu + baseDir string + helpIdent int +} + +func Parse(file string) (*KConfig, error) { + data, err := ioutil.ReadFile(file) + if err != nil { + return nil, fmt.Errorf("failed to open Kconfig file %v: %v", file, err) + } + return ParseData(data, file) +} + +func ParseData(data []byte, file string) (*KConfig, error) { + kp := &kconfigParser{ + parser: newParser(data, file), + baseDir: filepath.Dir(file), + } + kp.parseFile() + if kp.err != nil { + return nil, kp.err + } + if len(kp.stack) == 0 { + return nil, fmt.Errorf("no mainmenu in config") + } + root := kp.stack[0] + kconf := &KConfig{ + Root: root, + Configs: make(map[string]*Menu), + } + kconf.walk(root, nil, nil) + return kconf, nil +} + +func (kconf *KConfig) walk(m *Menu, dependsOn, visibleIf expr) { + m.kconf = kconf + m.dependsOn = exprAnd(dependsOn, m.dependsOn) + m.visibleIf = exprAnd(visibleIf, m.visibleIf) + if m.Kind == MenuConfig { + kconf.Configs[m.Name] = m + } + for _, elem := range m.Elems { + kconf.walk(elem, m.dependsOn, m.visibleIf) + } +} + +func (kp *kconfigParser) parseFile() { + for kp.nextLine() { + kp.parseLine() + if kp.TryConsume("#") { + _ = kp.ConsumeLine() + } + } +} + +func (kp *kconfigParser) parseLine() { + if kp.eol() { + return + } + if kp.helpIdent != 0 { + if kp.identLevel() >= kp.helpIdent { + _ = kp.ConsumeLine() + return + } + kp.helpIdent = 0 + } + if kp.TryConsume("#") { + _ = kp.ConsumeLine() + return + } + if kp.TryConsume("$") { + _ = kp.Shell() + return + } + ident := kp.Ident() + if kp.TryConsume("=") || kp.TryConsume(":=") { + // Macro definition, see: + // https://www.kernel.org/doc/html/latest/kbuild/kconfig-macro-language.html + // We don't use this for anything now. + kp.ConsumeLine() + return + } + kp.parseMenu(ident) +} + +func (kp *kconfigParser) parseMenu(cmd string) { + switch cmd { + case "source": + kp.includeSource(kp.QuotedString()) + case "mainmenu": + kp.pushCurrent(&Menu{ + Kind: MenuConfig, + prompts: []prompt{{text: kp.QuotedString()}}, + }) + case "comment": + kp.newCurrent(&Menu{ + Kind: MenuComment, + prompts: []prompt{{text: kp.QuotedString()}}, + }) + case "menu": + kp.pushCurrent(&Menu{ + Kind: MenuGroup, + prompts: []prompt{{text: kp.QuotedString()}}, + }) + case "if": + kp.pushCurrent(&Menu{ + Kind: MenuGroup, + visibleIf: kp.parseExpr(), + }) + case "choice": + kp.pushCurrent(&Menu{ + Kind: MenuChoice, + }) + case "endmenu", "endif", "endchoice": + kp.popCurrent() + case "config", "menuconfig": + kp.newCurrent(&Menu{ + Kind: MenuConfig, + Name: kp.Ident(), + }) + default: + kp.parseConfigType(cmd) + } +} + +func (kp *kconfigParser) parseConfigType(typ string) { + cur := kp.current() + switch typ { + case "tristate": + cur.Type = TypeTristate + kp.tryParsePrompt() + case "def_tristate": + cur.Type = TypeTristate + kp.parseDefaultValue() + case "bool": + cur.Type = TypeBool + kp.tryParsePrompt() + case "def_bool": + cur.Type = TypeBool + kp.parseDefaultValue() + case "int": + cur.Type = TypeInt + kp.tryParsePrompt() + case "def_int": + cur.Type = TypeInt + kp.parseDefaultValue() + case "hex": + cur.Type = TypeHex + kp.tryParsePrompt() + case "def_hex": + cur.Type = TypeHex + kp.parseDefaultValue() + case "string": + cur.Type = TypeString + kp.tryParsePrompt() + case "def_string": + cur.Type = TypeString + kp.parseDefaultValue() + default: + kp.parseProperty(typ) + } +} + +func (kp *kconfigParser) parseProperty(prop string) { + cur := kp.current() + switch prop { + case "prompt": + kp.tryParsePrompt() + case "depends": + kp.MustConsume("on") + cur.dependsOn = exprAnd(cur.dependsOn, kp.parseExpr()) + case "visible": + kp.MustConsume("if") + cur.visibleIf = exprAnd(cur.visibleIf, kp.parseExpr()) + case "select", "imply": + _ = kp.Ident() + if kp.TryConsume("if") { + _ = kp.parseExpr() + } + case "option": + _ = kp.Ident() + case "optional": + case "default": + kp.parseDefaultValue() + case "range": + _, _ = kp.parseExpr(), kp.parseExpr() // from, to + if kp.TryConsume("if") { + _ = kp.parseExpr() + } + case "help", "---help---": + // Help rules are tricky: end of help is identified by smaller indentation level + // as would be rendered on a terminal with 8-column tabs setup, minus empty lines. + for kp.nextLine() { + if kp.eol() { + continue + } + kp.helpIdent = kp.identLevel() + kp.ConsumeLine() + break + } + default: + kp.failf("unknown line") + } +} + +func (kp *kconfigParser) includeSource(file string) { + kp.newCurrent(nil) + file = kp.expandString(file) + file = filepath.Join(kp.baseDir, file) + data, err := ioutil.ReadFile(file) + if err != nil { + kp.failf("%v", err) + return + } + kp.includes = append(kp.includes, kp.parser) + kp.parser = newParser(data, file) + kp.parseFile() + err = kp.err + kp.parser = kp.includes[len(kp.includes)-1] + kp.includes = kp.includes[:len(kp.includes)-1] + if kp.err == nil { + kp.err = err + } +} + +func (kp *kconfigParser) pushCurrent(m *Menu) { + kp.endCurrent() + kp.cur = m + kp.stack = append(kp.stack, m) +} + +func (kp *kconfigParser) popCurrent() { + kp.endCurrent() + if len(kp.stack) < 2 { + kp.failf("unbalanced menuend") + return + } + last := kp.stack[len(kp.stack)-1] + kp.stack = kp.stack[:len(kp.stack)-1] + top := kp.stack[len(kp.stack)-1] + last.Parent = top + top.Elems = append(top.Elems, last) +} + +func (kp *kconfigParser) newCurrent(m *Menu) { + kp.endCurrent() + kp.cur = m +} + +func (kp *kconfigParser) current() *Menu { + if kp.cur == nil { + kp.failf("config property outside of config") + return &Menu{} + } + return kp.cur +} + +func (kp *kconfigParser) endCurrent() { + if kp.cur == nil { + return + } + if len(kp.stack) == 0 { + kp.failf("unbalanced menuend") + return + } + top := kp.stack[len(kp.stack)-1] + if top != kp.cur { + kp.cur.Parent = top + top.Elems = append(top.Elems, kp.cur) + } + kp.cur = nil +} + +func (kp *kconfigParser) tryParsePrompt() { + if str, ok := kp.TryQuotedString(); ok { + prompt := prompt{ + text: str, + } + if kp.TryConsume("if") { + prompt.cond = kp.parseExpr() + } + kp.current().prompts = append(kp.current().prompts, prompt) + } +} + +func (kp *kconfigParser) parseDefaultValue() { + def := defaultVal{val: kp.parseExpr()} + if kp.TryConsume("if") { + def.cond = kp.parseExpr() + } + kp.current().defaults = append(kp.current().defaults, def) +} + +func (kp *kconfigParser) expandString(str string) string { + return strings.ReplaceAll(str, "$(SRCARCH)", "x86") +} diff --git a/pkg/kconfig/kconfig_test.go b/pkg/kconfig/kconfig_test.go new file mode 100644 index 000000000..e3bdd8668 --- /dev/null +++ b/pkg/kconfig/kconfig_test.go @@ -0,0 +1,41 @@ +// Copyright 2020 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 kconfig + +import ( + "fmt" + "testing" +) + +func TestParseKConfig(t *testing.T) { + type Test struct { + in string + } + tests := []Test{ + { + in: ` +mainmenu "test" +config FOO + default "$(shell,$(srctree)/scripts/gcc-plugin.sh "$(preferred-plugin-hostcc)" "$(HOSTCXX)" "$(CC)")" if CC_IS_GCC +`, + }, + } + for i, test := range tests { + t.Run(fmt.Sprint(i), func(t *testing.T) { + kconf, err := ParseData([]byte(test.in), "Kconfig") + if err != nil { + t.Fatal(err) + } + _ = kconf + }) + } +} + +func TestFuzzParseKConfig(t *testing.T) { + for _, data := range []string{ + ``, + } { + FuzzParseKConfig([]byte(data)[:len(data):len(data)]) + } +} -- cgit mrf-deployment