From cfc46d9d0bea72865ba75e0e4063a1a558262df8 Mon Sep 17 00:00:00 2001 From: Andrey Konovalov Date: Tue, 11 Jul 2017 16:49:08 +0200 Subject: prog: split Arg into smaller structs Right now Arg is a huge struct (160 bytes), which has many different fields used for different arg kinds. Since most of the args we see in a typical corpus are ArgConst, this results in a significant memory overuse. This change: - makes Arg an interface instead of a struct - adds a SomethingArg struct for each arg kind we have - converts all *Arg pointers into just Arg, since interface variable by itself contains a pointer to the actual data - removes ArgPageSize, now ConstArg is used instead - consolidates correspondence between arg kinds and types, see comments before each SomethingArg struct definition - now LenType args that denote the length of VmaType args are serialized as "0x1000" instead of "(0x1000)"; to preserve backwards compatibility syzkaller is able to parse the old format for now - multiple small changes all over to make the above work After this change syzkaller uses twice less memory after deserializing a typical corpus. --- prog/mutation.go | 223 ++++++++++++++++++++++++++++++++----------------------- 1 file changed, 130 insertions(+), 93 deletions(-) (limited to 'prog/mutation.go') diff --git a/prog/mutation.go b/prog/mutation.go index cbf1f53d5..d6a9380ae 100644 --- a/prog/mutation.go +++ b/prog/mutation.go @@ -68,90 +68,84 @@ func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Pro arg, base := args[idx], bases[idx] var baseSize uintptr if base != nil { - if base.Kind != ArgPointer || base.Res == nil { + b, ok := base.(*PointerArg) + if !ok || b.Res == nil { panic("bad base arg") } - baseSize = base.Res.Size() + baseSize = b.Res.Size() } - switch a := arg.Type.(type) { + switch t := arg.Type().(type) { case *sys.IntType, *sys.FlagsType: + a := arg.(*ConstArg) if r.bin() { - arg1, calls1 := r.generateArg(s, arg.Type) + arg1, calls1 := r.generateArg(s, arg.Type()) p.replaceArg(c, arg, arg1, calls1) } else { switch { case r.nOutOf(1, 3): - arg.Val += uintptr(r.Intn(4)) + 1 + a.Val += uintptr(r.Intn(4)) + 1 case r.nOutOf(1, 2): - arg.Val -= uintptr(r.Intn(4)) + 1 + a.Val -= uintptr(r.Intn(4)) + 1 default: - arg.Val ^= 1 << uintptr(r.Intn(64)) + a.Val ^= 1 << uintptr(r.Intn(64)) } } case *sys.ResourceType, *sys.VmaType, *sys.ProcType: - arg1, calls1 := r.generateArg(s, arg.Type) + arg1, calls1 := r.generateArg(s, arg.Type()) p.replaceArg(c, arg, arg1, calls1) case *sys.BufferType: - switch a.Kind { + a := arg.(*DataArg) + switch t.Kind { case sys.BufferBlobRand, sys.BufferBlobRange: var data []byte - switch arg.Kind { - case ArgData: - data = append([]byte{}, arg.Data...) - case ArgConst: - // 0 is OK for optional args. - if arg.Val != 0 { - panic(fmt.Sprintf("BufferType has non-zero const value: %v", arg.Val)) - } - default: - panic(fmt.Sprintf("bad arg kind for BufferType: %v", arg.Kind)) - } + data = append([]byte{}, a.Data...) minLen := int(0) maxLen := math.MaxInt32 - if a.Kind == sys.BufferBlobRange { - minLen = int(a.RangeBegin) - maxLen = int(a.RangeEnd) + if t.Kind == sys.BufferBlobRange { + minLen = int(t.RangeBegin) + maxLen = int(t.RangeEnd) } - arg.Data = mutateData(r, data, minLen, maxLen) + a.Data = mutateData(r, data, minLen, maxLen) case sys.BufferString: if r.bin() { minLen := int(0) maxLen := math.MaxInt32 - if a.Length != 0 { - minLen = int(a.Length) - maxLen = int(a.Length) + if t.Length != 0 { + minLen = int(t.Length) + maxLen = int(t.Length) } - arg.Data = mutateData(r, append([]byte{}, arg.Data...), minLen, maxLen) + a.Data = mutateData(r, append([]byte{}, a.Data...), minLen, maxLen) } else { - arg.Data = r.randString(s, a.Values, a.Dir()) + a.Data = r.randString(s, t.Values, t.Dir()) } case sys.BufferFilename: - arg.Data = []byte(r.filename(s)) + a.Data = []byte(r.filename(s)) case sys.BufferText: - arg.Data = r.mutateText(a.Text, arg.Data) + a.Data = r.mutateText(t.Text, a.Data) default: panic("unknown buffer kind") } case *sys.ArrayType: + a := arg.(*GroupArg) count := uintptr(0) - switch a.Kind { + switch t.Kind { case sys.ArrayRandLen: - for count == uintptr(len(arg.Inner)) { + for count == uintptr(len(a.Inner)) { count = r.randArrayLen() } case sys.ArrayRangeLen: - if a.RangeBegin == a.RangeEnd { + if t.RangeBegin == t.RangeEnd { panic("trying to mutate fixed length array") } - for count == uintptr(len(arg.Inner)) { - count = r.randRange(int(a.RangeBegin), int(a.RangeEnd)) + for count == uintptr(len(a.Inner)) { + count = r.randRange(int(t.RangeBegin), int(t.RangeEnd)) } } - if count > uintptr(len(arg.Inner)) { + if count > uintptr(len(a.Inner)) { var calls []*Call - for count > uintptr(len(arg.Inner)) { - arg1, calls1 := r.generateArg(s, a.Type) - arg.Inner = append(arg.Inner, arg1) + for count > uintptr(len(a.Inner)) { + arg1, calls1 := r.generateArg(s, t.Type) + a.Inner = append(a.Inner, arg1) for _, c1 := range calls1 { calls = append(calls, c1) s.analyze(c1) @@ -162,43 +156,48 @@ func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Pro } sanitizeCall(c) p.insertBefore(c, calls) - } else if count < uintptr(len(arg.Inner)) { - for _, arg := range arg.Inner[count:] { + } else if count < uintptr(len(a.Inner)) { + for _, arg := range a.Inner[count:] { p.removeArg(c, arg) } - arg.Inner = arg.Inner[:count] + a.Inner = a.Inner[:count] } // TODO: swap elements of the array case *sys.PtrType: + a, ok := arg.(*PointerArg) + if !ok { + break + } // TODO: we don't know size for out args size := uintptr(1) - if arg.Res != nil { - size = arg.Res.Size() + if a.Res != nil { + size = a.Res.Size() } - arg1, calls1 := r.addr(s, a, size, arg.Res) + arg1, calls1 := r.addr(s, t, size, a.Res) p.replaceArg(c, arg, arg1, calls1) case *sys.StructType: - ctor := isSpecialStruct(a) + ctor := isSpecialStruct(t) if ctor == nil { panic("bad arg returned by mutationArgs: StructType") } arg1, calls1 := ctor(r, s) - for i, f := range arg1.Inner { - p.replaceArg(c, arg.Inner[i], f, calls1) + for i, f := range arg1.(*GroupArg).Inner { + p.replaceArg(c, arg.(*GroupArg).Inner[i], f, calls1) calls1 = nil } case *sys.UnionType: - optType := a.Options[r.Intn(len(a.Options))] + a := arg.(*UnionArg) + optType := t.Options[r.Intn(len(t.Options))] maxIters := 1000 - for i := 0; optType.FieldName() == arg.OptionType.FieldName(); i++ { - optType = a.Options[r.Intn(len(a.Options))] + for i := 0; optType.FieldName() == a.OptionType.FieldName(); i++ { + optType = t.Options[r.Intn(len(t.Options))] if i >= maxIters { - panic(fmt.Sprintf("couldn't generate a different union option after %v iterations, type: %+v", maxIters, a)) + panic(fmt.Sprintf("couldn't generate a different union option after %v iterations, type: %+v", maxIters, t)) } } - p.removeArg(c, arg.Option) + p.removeArg(c, a.Option) opt, calls := r.generateArg(s, optType) - arg1 := unionArg(a, opt, optType) + arg1 := unionArg(t, opt, optType) p.replaceArg(c, arg, arg1, calls) case *sys.LenType: panic("bad arg returned by mutationArgs: LenType") @@ -207,19 +206,23 @@ func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Pro case *sys.ConstType: panic("bad arg returned by mutationArgs: ConstType") default: - panic(fmt.Sprintf("bad arg returned by mutationArgs: %#v, type=%#v", *arg, arg.Type)) + panic(fmt.Sprintf("bad arg returned by mutationArgs: %#v, type=%#v", arg, arg.Type())) } // Update base pointer if size has increased. - if base != nil && baseSize < base.Res.Size() { - arg1, calls1 := r.addr(s, base.Type, base.Res.Size(), base.Res) - for _, c1 := range calls1 { - sanitizeCall(c1) + if base != nil { + b := base.(*PointerArg) + if baseSize < b.Res.Size() { + arg1, calls1 := r.addr(s, b.Type(), b.Res.Size(), b.Res) + for _, c1 := range calls1 { + sanitizeCall(c1) + } + p.insertBefore(c, calls1) + a1 := arg1.(*PointerArg) + b.PageIndex = a1.PageIndex + b.PageOffset = a1.PageOffset + b.PagesNum = a1.PagesNum } - p.insertBefore(c, calls1) - arg.AddrPage = arg1.AddrPage - arg.AddrOffset = arg1.AddrOffset - arg.AddrPagesNum = arg1.AddrPagesNum } // Update all len fields. @@ -313,33 +316,41 @@ func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool, crash bool) var triedPaths map[string]bool - var rec func(p *Prog, call *Call, arg *Arg, path string) bool - rec = func(p *Prog, call *Call, arg *Arg, path string) bool { - path += fmt.Sprintf("-%v", arg.Type.FieldName()) - switch typ := arg.Type.(type) { + var rec func(p *Prog, call *Call, arg Arg, path string) bool + rec = func(p *Prog, call *Call, arg Arg, path string) bool { + path += fmt.Sprintf("-%v", arg.Type().FieldName()) + switch typ := arg.Type().(type) { case *sys.StructType: - for _, innerArg := range arg.Inner { + a := arg.(*GroupArg) + for _, innerArg := range a.Inner { if rec(p, call, innerArg, path) { return true } } case *sys.UnionType: - if rec(p, call, arg.Option, path) { + a := arg.(*UnionArg) + if rec(p, call, a.Option, path) { return true } case *sys.PtrType: // TODO: try to remove optional ptrs - if arg.Res != nil { - return rec(p, call, arg.Res, path) + a, ok := arg.(*PointerArg) + if !ok { + // Can also be *ConstArg. + return false + } + if a.Res != nil { + return rec(p, call, a.Res, path) } case *sys.ArrayType: - for i, innerArg := range arg.Inner { + a := arg.(*GroupArg) + for i, innerArg := range a.Inner { innerPath := fmt.Sprintf("%v-%v", path, i) if !triedPaths[innerPath] && !crash { - if (typ.Kind == sys.ArrayRangeLen && len(arg.Inner) > int(typ.RangeBegin)) || + if (typ.Kind == sys.ArrayRangeLen && len(a.Inner) > int(typ.RangeBegin)) || (typ.Kind == sys.ArrayRandLen) { - copy(arg.Inner[i:], arg.Inner[i+1:]) - arg.Inner = arg.Inner[:len(arg.Inner)-1] + copy(a.Inner[i:], a.Inner[i+1:]) + a.Inner = a.Inner[:len(a.Inner)-1] p.removeArg(call, innerArg) assignSizesCall(call) @@ -356,7 +367,7 @@ func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool, crash bool) return true } } - case *sys.IntType, *sys.FlagsType, *sys.ResourceType, *sys.ProcType: + case *sys.IntType, *sys.FlagsType, *sys.ProcType: // TODO: try to reset bits in ints // TODO: try to set separate flags if crash { @@ -366,16 +377,39 @@ func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool, crash bool) return false } triedPaths[path] = true - if arg.Val == typ.Default() { + a := arg.(*ConstArg) + if a.Val == typ.Default() { + return false + } + v0 := a.Val + a.Val = typ.Default() + if pred(p, callIndex0) { + p0 = p + return true + } else { + a.Val = v0 + } + case *sys.ResourceType: + if crash { + return false + } + if triedPaths[path] { + return false + } + triedPaths[path] = true + a := arg.(*ResultArg) + if a.Res == nil { return false } - v0 := arg.Val - arg.Val = typ.Default() + r0 := a.Res + a.Res = nil + a.Val = typ.Default() if pred(p, callIndex0) { p0 = p return true } else { - arg.Val = v0 + a.Res = r0 + a.Val = 0 } case *sys.BufferType: // TODO: try to set individual bytes to 0 @@ -386,15 +420,16 @@ func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool, crash bool) if typ.Kind != sys.BufferBlobRand && typ.Kind != sys.BufferBlobRange { return false } + a := arg.(*DataArg) minLen := int(typ.RangeBegin) - for step := len(arg.Data) - minLen; len(arg.Data) > minLen && step > 0; { - if len(arg.Data)-step >= minLen { - arg.Data = arg.Data[:len(arg.Data)-step] + for step := len(a.Data) - minLen; len(a.Data) > minLen && step > 0; { + if len(a.Data)-step >= minLen { + a.Data = a.Data[:len(a.Data)-step] assignSizesCall(call) if pred(p, callIndex0) { continue } - arg.Data = arg.Data[:len(arg.Data)+step] + a.Data = a.Data[:len(a.Data)+step] assignSizesCall(call) } step /= 2 @@ -440,18 +475,20 @@ func (p *Prog) TrimAfter(idx int) { } for i := len(p.Calls) - 1; i > idx; i-- { c := p.Calls[i] - foreachArg(c, func(arg, _ *Arg, _ *[]*Arg) { - if arg.Kind == ArgResult { - delete(arg.Res.Uses, arg) + foreachArg(c, func(arg, _ Arg, _ *[]Arg) { + if a, ok := arg.(*ResultArg); ok && a.Res != nil { + if used, ok := a.Res.(ArgUsed); ok { + delete(*used.Used(), arg) + } } }) } p.Calls = p.Calls[:idx+1] } -func mutationArgs(c *Call) (args, bases []*Arg) { - foreachArg(c, func(arg, base *Arg, _ *[]*Arg) { - switch typ := arg.Type.(type) { +func mutationArgs(c *Call) (args, bases []Arg) { + foreachArg(c, func(arg, base Arg, _ *[]Arg) { + switch typ := arg.Type().(type) { case *sys.StructType: if isSpecialStruct(typ) == nil { // For structs only individual fields are updated. @@ -477,11 +514,11 @@ func mutationArgs(c *Call) (args, bases []*Arg) { return // string const } } - if arg.Type.Dir() == sys.DirOut { + if arg.Type().Dir() == sys.DirOut { return } if base != nil { - if _, ok := base.Type.(*sys.StructType); ok && isSpecialStruct(base.Type) != nil { + if _, ok := base.Type().(*sys.StructType); ok && isSpecialStruct(base.Type()) != nil { // These special structs are mutated as a whole. return } -- cgit mrf-deployment