1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
// 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"
"sort"
"github.com/google/syzkaller/pkg/bisect/minimize"
"github.com/google/syzkaller/pkg/debugtracer"
)
// Minimize finds an equivalent with respect to the provided predicate, but smaller config.
// It accepts base (small) and full (large) config. It is assumed that the predicate returns true for the full config.
// 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),
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)
}
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("minimized to %d configs; suspects: %v", len(result), suspects)
kconf.writeSuspects(dt, suspects)
}
return config, nil
}
func (kconf *KConfig) missingConfigs(base, full *ConfigFile) (tristate []string, other []*Config) {
for _, cfg := range full.Configs {
if cfg.Value == Yes && base.Value(cfg.Name) == No {
tristate = append(tristate, cfg.Name)
} else if cfg.Value != No && cfg.Value != Yes && cfg.Value != Mod {
other = append(other, cfg)
}
}
sort.Strings(tristate)
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 {
closure[cfg] = true
if m := kconf.Configs[cfg]; m != nil {
for dep := range m.DependsOn() {
if full.Value(dep) != No && base.Value(dep) == No {
closure[dep] = true
}
}
}
}
var sorted []string
for cfg := range closure {
sorted = append(sorted, cfg)
}
sort.Strings(sorted)
return sorted
}
const CauseConfigFile = "cause.config"
func (kconf *KConfig) writeSuspects(dt debugtracer.DebugTracer, suspects []string) {
cf := &ConfigFile{
Map: make(map[string]*Config),
}
for _, cfg := range suspects {
cf.Set(cfg, Yes)
}
dt.SaveFile(CauseConfigFile, cf.Serialize())
}
|
