1// Copyright 2017 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 prog 5 6import ( 7 "fmt" 8 "math/rand" 9 "sort" 10 "sync" 11) 12 13// Target describes target OS/arch pair. 14type Target struct { 15 OS string 16 Arch string 17 Revision string // unique hash representing revision of the descriptions 18 PtrSize uint64 19 PageSize uint64 20 NumPages uint64 21 DataOffset uint64 22 23 Syscalls []*Syscall 24 Resources []*ResourceDesc 25 Structs []*KeyedStruct 26 Consts []ConstValue 27 28 // MakeMmap creates call that maps [addr, addr+size) memory range. 29 MakeMmap func(addr, size uint64) *Call 30 31 // SanitizeCall neutralizes harmful calls. 32 SanitizeCall func(c *Call) 33 34 // SpecialTypes allows target to do custom generation/mutation for some struct's and union's. 35 // Map key is struct/union name for which custom generation/mutation is required. 36 // Map value is custom generation/mutation function that will be called 37 // for the corresponding type. g is helper object that allows generate random numbers, 38 // allocate memory, etc. typ is the struct/union type. old is the old value of the struct/union 39 // for mutation, or nil for generation. The function returns a new value of the struct/union, 40 // and optionally any calls that need to be inserted before the arg reference. 41 SpecialTypes map[string]func(g *Gen, typ Type, old Arg) (Arg, []*Call) 42 43 // Special strings that can matter for the target. 44 // Used as fallback when string type does not have own dictionary. 45 StringDictionary []string 46 47 // Filled by prog package: 48 init sync.Once 49 initArch func(target *Target) 50 SyscallMap map[string]*Syscall 51 ConstMap map[string]uint64 52 resourceMap map[string]*ResourceDesc 53 // Maps resource name to a list of calls that can create the resource. 54 resourceCtors map[string][]*Syscall 55 any anyTypes 56} 57 58var targets = make(map[string]*Target) 59 60func RegisterTarget(target *Target, initArch func(target *Target)) { 61 key := target.OS + "/" + target.Arch 62 if targets[key] != nil { 63 panic(fmt.Sprintf("duplicate target %v", key)) 64 } 65 target.initArch = initArch 66 targets[key] = target 67} 68 69func GetTarget(OS, arch string) (*Target, error) { 70 key := OS + "/" + arch 71 target := targets[key] 72 if target == nil { 73 var supported []string 74 for _, t := range targets { 75 supported = append(supported, fmt.Sprintf("%v/%v", t.OS, t.Arch)) 76 } 77 sort.Strings(supported) 78 return nil, fmt.Errorf("unknown target: %v (supported: %v)", key, supported) 79 } 80 target.init.Do(target.lazyInit) 81 return target, nil 82} 83 84func AllTargets() []*Target { 85 var res []*Target 86 for _, target := range targets { 87 target.init.Do(target.lazyInit) 88 res = append(res, target) 89 } 90 sort.Slice(res, func(i, j int) bool { 91 if res[i].OS != res[j].OS { 92 return res[i].OS < res[j].OS 93 } 94 return res[i].Arch < res[j].Arch 95 }) 96 return res 97} 98 99func (target *Target) lazyInit() { 100 target.SanitizeCall = func(c *Call) {} 101 target.initTarget() 102 target.initArch(target) 103 target.ConstMap = nil // currently used only by initArch 104} 105 106func (target *Target) initTarget() { 107 target.ConstMap = make(map[string]uint64) 108 for _, c := range target.Consts { 109 target.ConstMap[c.Name] = c.Value 110 } 111 112 target.resourceMap = make(map[string]*ResourceDesc) 113 for _, res := range target.Resources { 114 target.resourceMap[res.Name] = res 115 } 116 117 keyedStructs := make(map[StructKey]*StructDesc) 118 for _, desc := range target.Structs { 119 keyedStructs[desc.Key] = desc.Desc 120 } 121 target.Structs = nil 122 123 target.SyscallMap = make(map[string]*Syscall) 124 for i, c := range target.Syscalls { 125 c.ID = i 126 target.SyscallMap[c.Name] = c 127 ForeachType(c, func(t0 Type) { 128 switch t := t0.(type) { 129 case *ResourceType: 130 t.Desc = target.resourceMap[t.TypeName] 131 if t.Desc == nil { 132 panic("no resource desc") 133 } 134 case *StructType: 135 t.StructDesc = keyedStructs[t.Key] 136 if t.StructDesc == nil { 137 panic("no struct desc") 138 } 139 case *UnionType: 140 t.StructDesc = keyedStructs[t.Key] 141 if t.StructDesc == nil { 142 panic("no union desc") 143 } 144 } 145 }) 146 } 147 148 target.resourceCtors = make(map[string][]*Syscall) 149 for _, res := range target.Resources { 150 target.resourceCtors[res.Name] = target.calcResourceCtors(res.Kind, false) 151 } 152 initAnyTypes(target) 153} 154 155type Gen struct { 156 r *randGen 157 s *state 158} 159 160func (g *Gen) Target() *Target { 161 return g.r.target 162} 163 164func (g *Gen) Rand() *rand.Rand { 165 return g.r.Rand 166} 167 168func (g *Gen) NOutOf(n, outOf int) bool { 169 return g.r.nOutOf(n, outOf) 170} 171 172func (g *Gen) Alloc(ptrType Type, data Arg) (Arg, []*Call) { 173 return g.r.allocAddr(g.s, ptrType, data.Size(), data), nil 174} 175 176func (g *Gen) GenerateArg(typ Type, pcalls *[]*Call) Arg { 177 return g.generateArg(typ, pcalls, false) 178} 179 180func (g *Gen) GenerateSpecialArg(typ Type, pcalls *[]*Call) Arg { 181 return g.generateArg(typ, pcalls, true) 182} 183 184func (g *Gen) generateArg(typ Type, pcalls *[]*Call, ignoreSpecial bool) Arg { 185 arg, calls := g.r.generateArgImpl(g.s, typ, ignoreSpecial) 186 *pcalls = append(*pcalls, calls...) 187 g.r.target.assignSizesArray([]Arg{arg}) 188 return arg 189} 190 191func (g *Gen) MutateArg(arg0 Arg) (calls []*Call) { 192 updateSizes := true 193 for stop := false; !stop; stop = g.r.oneOf(3) { 194 ma := &mutationArgs{target: g.r.target, ignoreSpecial: true} 195 ForeachSubArg(arg0, ma.collectArg) 196 if len(ma.args) == 0 { 197 // TODO(dvyukov): probably need to return this condition 198 // and updateSizes to caller so that Mutate can act accordingly. 199 return 200 } 201 idx := g.r.Intn(len(ma.args)) 202 arg, ctx := ma.args[idx], ma.ctxes[idx] 203 newCalls, ok := g.r.target.mutateArg(g.r, g.s, arg, ctx, &updateSizes) 204 if !ok { 205 continue 206 } 207 calls = append(calls, newCalls...) 208 } 209 return calls 210} 211