1// Copyright 2018 syzkaller project authors. All rights reserved. 2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. 3 4package bisect 5 6import ( 7 "fmt" 8 "io" 9 "path/filepath" 10 "time" 11 12 "github.com/google/syzkaller/pkg/build" 13 "github.com/google/syzkaller/pkg/instance" 14 "github.com/google/syzkaller/pkg/mgrconfig" 15 "github.com/google/syzkaller/pkg/osutil" 16 "github.com/google/syzkaller/pkg/vcs" 17) 18 19type Config struct { 20 Trace io.Writer 21 Fix bool 22 BinDir string 23 DebugDir string 24 Kernel KernelConfig 25 Syzkaller SyzkallerConfig 26 Repro ReproConfig 27 Manager mgrconfig.Config 28} 29 30type KernelConfig struct { 31 Repo string 32 Branch string 33 Commit string 34 Cmdline string 35 Sysctl string 36 Config []byte 37 Userspace string 38} 39 40type SyzkallerConfig struct { 41 Repo string 42 Commit string 43 Descriptions string 44} 45 46type ReproConfig struct { 47 Opts []byte 48 Syz []byte 49 C []byte 50} 51 52type env struct { 53 cfg *Config 54 repo vcs.Repo 55 head *vcs.Commit 56 inst *instance.Env 57 numTests int 58 buildTime time.Duration 59 testTime time.Duration 60} 61 62type buildEnv struct { 63 compiler string 64} 65 66func Run(cfg *Config) (*vcs.Commit, error) { 67 repo, err := vcs.NewRepo(cfg.Manager.TargetOS, cfg.Manager.Type, cfg.Manager.KernelSrc) 68 if err != nil { 69 return nil, err 70 } 71 env := &env{ 72 cfg: cfg, 73 repo: repo, 74 } 75 if cfg.Fix { 76 env.log("searching for fixing commit since %v", cfg.Kernel.Commit) 77 } else { 78 env.log("searching for guilty commit starting from %v", cfg.Kernel.Commit) 79 } 80 start := time.Now() 81 res, err := env.bisect() 82 env.log("revisions tested: %v, total time: %v (build: %v, test: %v)", 83 env.numTests, time.Since(start), env.buildTime, env.testTime) 84 if err != nil { 85 env.log("error: %v", err) 86 return nil, err 87 } 88 if res == nil { 89 env.log("the crash is still unfixed") 90 return nil, nil 91 } 92 what := "bad" 93 if cfg.Fix { 94 what = "good" 95 } 96 env.log("first %v commit: %v %v", what, res.Hash, res.Title) 97 env.log("cc: %q", res.CC) 98 return res, nil 99} 100 101func (env *env) bisect() (*vcs.Commit, error) { 102 cfg := env.cfg 103 var err error 104 if env.inst, err = instance.NewEnv(&cfg.Manager); err != nil { 105 return nil, err 106 } 107 if env.head, err = env.repo.Poll(cfg.Kernel.Repo, cfg.Kernel.Branch); err != nil { 108 return nil, err 109 } 110 if err := build.Clean(cfg.Manager.TargetOS, cfg.Manager.TargetVMArch, 111 cfg.Manager.Type, cfg.Manager.KernelSrc); err != nil { 112 return nil, fmt.Errorf("kernel clean failed: %v", err) 113 } 114 env.log("building syzkaller on %v", cfg.Syzkaller.Commit) 115 if err := env.inst.BuildSyzkaller(cfg.Syzkaller.Repo, cfg.Syzkaller.Commit); err != nil { 116 return nil, err 117 } 118 if _, err := env.repo.SwitchCommit(cfg.Kernel.Commit); err != nil { 119 return nil, err 120 } 121 if res, err := env.test(); err != nil { 122 return nil, err 123 } else if res != vcs.BisectBad { 124 return nil, fmt.Errorf("the crash wasn't reproduced on the original commit") 125 } 126 res, bad, good, err := env.commitRange() 127 if err != nil { 128 return nil, err 129 } 130 if res != nil { 131 return res, nil // happens on the oldest release 132 } 133 if good == "" { 134 return nil, nil // still not fixed 135 } 136 return env.repo.Bisect(bad, good, cfg.Trace, func() (vcs.BisectResult, error) { 137 res, err := env.test() 138 if cfg.Fix { 139 if res == vcs.BisectBad { 140 res = vcs.BisectGood 141 } else if res == vcs.BisectGood { 142 res = vcs.BisectBad 143 } 144 } 145 return res, err 146 }) 147} 148 149func (env *env) commitRange() (*vcs.Commit, string, string, error) { 150 if env.cfg.Fix { 151 return env.commitRangeForFix() 152 } 153 return env.commitRangeForBug() 154} 155 156func (env *env) commitRangeForFix() (*vcs.Commit, string, string, error) { 157 env.log("testing current HEAD %v", env.head.Hash) 158 if _, err := env.repo.SwitchCommit(env.head.Hash); err != nil { 159 return nil, "", "", err 160 } 161 res, err := env.test() 162 if err != nil { 163 return nil, "", "", err 164 } 165 if res != vcs.BisectGood { 166 return nil, "", "", nil 167 } 168 return nil, env.head.Hash, env.cfg.Kernel.Commit, nil 169} 170 171func (env *env) commitRangeForBug() (*vcs.Commit, string, string, error) { 172 cfg := env.cfg 173 tags, err := env.repo.PreviousReleaseTags(cfg.Kernel.Commit) 174 if err != nil { 175 return nil, "", "", err 176 } 177 for i, tag := range tags { 178 if tag == "v3.8" { 179 // v3.8 does not work with modern perl, and as we go further in history 180 // make stops to work, then binutils, glibc, etc. So we stop at v3.8. 181 // Up to that point we only need an ancient gcc. 182 tags = tags[:i] 183 break 184 } 185 } 186 if len(tags) == 0 { 187 return nil, "", "", fmt.Errorf("no release tags before this commit") 188 } 189 lastBad := cfg.Kernel.Commit 190 for i, tag := range tags { 191 env.log("testing release %v", tag) 192 commit, err := env.repo.SwitchCommit(tag) 193 if err != nil { 194 return nil, "", "", err 195 } 196 res, err := env.test() 197 if err != nil { 198 return nil, "", "", err 199 } 200 if res == vcs.BisectGood { 201 return nil, lastBad, tag, nil 202 } 203 if res == vcs.BisectBad { 204 lastBad = tag 205 } 206 if i == len(tags)-1 { 207 return commit, "", "", nil 208 } 209 } 210 panic("unreachable") 211} 212 213func (env *env) test() (vcs.BisectResult, error) { 214 cfg := env.cfg 215 env.numTests++ 216 current, err := env.repo.HeadCommit() 217 if err != nil { 218 return 0, err 219 } 220 be, err := env.buildEnvForCommit(current.Hash) 221 if err != nil { 222 return 0, err 223 } 224 compilerID, err := build.CompilerIdentity(be.compiler) 225 if err != nil { 226 return 0, err 227 } 228 env.log("testing commit %v with %v", current.Hash, compilerID) 229 buildStart := time.Now() 230 if err := build.Clean(cfg.Manager.TargetOS, cfg.Manager.TargetVMArch, 231 cfg.Manager.Type, cfg.Manager.KernelSrc); err != nil { 232 return 0, fmt.Errorf("kernel clean failed: %v", err) 233 } 234 err = env.inst.BuildKernel(be.compiler, cfg.Kernel.Userspace, 235 cfg.Kernel.Cmdline, cfg.Kernel.Sysctl, cfg.Kernel.Config) 236 env.buildTime += time.Since(buildStart) 237 if err != nil { 238 if verr, ok := err.(*osutil.VerboseError); ok { 239 env.log("%v", verr.Title) 240 env.saveDebugFile(current.Hash, 0, verr.Output) 241 } else { 242 env.log("%v", err) 243 } 244 return vcs.BisectSkip, nil 245 } 246 testStart := time.Now() 247 results, err := env.inst.Test(8, cfg.Repro.Syz, cfg.Repro.Opts, cfg.Repro.C) 248 env.testTime += time.Since(testStart) 249 if err != nil { 250 env.log("failed: %v", err) 251 return vcs.BisectSkip, nil 252 } 253 bad, good := env.processResults(current, results) 254 res := vcs.BisectSkip 255 if bad != 0 { 256 res = vcs.BisectBad 257 } else if good != 0 { 258 res = vcs.BisectGood 259 } 260 return res, nil 261} 262 263func (env *env) processResults(current *vcs.Commit, results []error) (bad, good int) { 264 var verdicts []string 265 for i, res := range results { 266 if res == nil { 267 good++ 268 verdicts = append(verdicts, "OK") 269 continue 270 } 271 switch err := res.(type) { 272 case *instance.TestError: 273 if err.Boot { 274 verdicts = append(verdicts, fmt.Sprintf("boot failed: %v", err)) 275 } else { 276 verdicts = append(verdicts, fmt.Sprintf("basic kernel testing failed: %v", err)) 277 } 278 output := err.Output 279 if err.Report != nil { 280 output = err.Report.Output 281 } 282 env.saveDebugFile(current.Hash, i, output) 283 case *instance.CrashError: 284 bad++ 285 verdicts = append(verdicts, fmt.Sprintf("crashed: %v", err)) 286 output := err.Report.Report 287 if len(output) == 0 { 288 output = err.Report.Output 289 } 290 env.saveDebugFile(current.Hash, i, output) 291 default: 292 verdicts = append(verdicts, fmt.Sprintf("failed: %v", err)) 293 } 294 } 295 unique := make(map[string]bool) 296 for _, verdict := range verdicts { 297 unique[verdict] = true 298 } 299 if len(unique) == 1 { 300 env.log("all runs: %v", verdicts[0]) 301 } else { 302 for i, verdict := range verdicts { 303 env.log("run #%v: %v", i, verdict) 304 } 305 } 306 return 307} 308 309// Note: linux-specific. 310func (env *env) buildEnvForCommit(commit string) (*buildEnv, error) { 311 cfg := env.cfg 312 tags, err := env.repo.PreviousReleaseTags(commit) 313 if err != nil { 314 return nil, err 315 } 316 be := &buildEnv{ 317 compiler: filepath.Join(cfg.BinDir, "gcc-"+linuxCompilerVersion(tags), "bin", "gcc"), 318 } 319 return be, nil 320} 321 322func linuxCompilerVersion(tags []string) string { 323 for _, tag := range tags { 324 switch tag { 325 case "v4.12": 326 return "8.1.0" 327 case "v4.11": 328 return "7.3.0" 329 case "v3.19": 330 return "5.5.0" 331 } 332 } 333 return "4.9.4" 334} 335 336func (env *env) saveDebugFile(hash string, idx int, data []byte) { 337 if env.cfg.DebugDir == "" || len(data) == 0 { 338 return 339 } 340 osutil.WriteFile(filepath.Join(env.cfg.DebugDir, fmt.Sprintf("%v.%v", hash, idx)), data) 341} 342 343func (env *env) log(msg string, args ...interface{}) { 344 fmt.Fprintf(env.cfg.Trace, msg+"\n", args...) 345} 346