1 // Copyright 2015 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 4 package prog 5 6 import ( 7 "fmt" 8 ) 9 10 type Prog struct { 11 Target *Target 12 Calls []*Call 13 Comments []string 14 } 15 16 type Call struct { 17 Meta *Syscall 18 Args []Arg 19 Ret *ResultArg 20 Comment string 21 } 22 23 type Arg interface { 24 Type() Type 25 Size() uint64 26 27 validate(ctx *validCtx) error 28 serialize(ctx *serializer) 29 } 30 31 type ArgCommon struct { 32 typ Type 33 } 34 35 func (arg *ArgCommon) Type() Type { 36 return arg.typ 37 } 38 39 // Used for ConstType, IntType, FlagsType, LenType, ProcType and CsumType. 40 type ConstArg struct { 41 ArgCommon 42 Val uint64 43 } 44 45 func MakeConstArg(t Type, v uint64) *ConstArg { 46 return &ConstArg{ArgCommon: ArgCommon{typ: t}, Val: v} 47 } 48 49 func (arg *ConstArg) Size() uint64 { 50 return arg.typ.Size() 51 } 52 53 // Value returns value, pid stride and endianness. 54 func (arg *ConstArg) Value() (uint64, uint64) { 55 switch typ := (*arg).Type().(type) { 56 case *IntType: 57 return arg.Val, 0 58 case *ConstType: 59 return arg.Val, 0 60 case *FlagsType: 61 return arg.Val, 0 62 case *LenType: 63 return arg.Val, 0 64 case *ResourceType: 65 return arg.Val, 0 66 case *CsumType: 67 // Checksums are computed dynamically in executor. 68 return 0, 0 69 case *ProcType: 70 if arg.Val == procDefaultValue { 71 return 0, 0 72 } 73 return typ.ValuesStart + arg.Val, typ.ValuesPerProc 74 default: 75 panic(fmt.Sprintf("unknown ConstArg type %#v", typ)) 76 } 77 } 78 79 // Used for PtrType and VmaType. 80 type PointerArg struct { 81 ArgCommon 82 Address uint64 83 VmaSize uint64 // size of the referenced region for vma args 84 Res Arg // pointee (nil for vma) 85 } 86 87 func MakePointerArg(t Type, addr uint64, data Arg) *PointerArg { 88 if data == nil { 89 panic("nil pointer data arg") 90 } 91 return &PointerArg{ 92 ArgCommon: ArgCommon{typ: t}, 93 Address: addr, 94 Res: data, 95 } 96 } 97 98 func MakeVmaPointerArg(t Type, addr, size uint64) *PointerArg { 99 if addr%1024 != 0 { 100 panic("unaligned vma address") 101 } 102 return &PointerArg{ 103 ArgCommon: ArgCommon{typ: t}, 104 Address: addr, 105 VmaSize: size, 106 } 107 } 108 109 func MakeNullPointerArg(t Type) *PointerArg { 110 return &PointerArg{ 111 ArgCommon: ArgCommon{typ: t}, 112 } 113 } 114 115 func (arg *PointerArg) Size() uint64 { 116 return arg.typ.Size() 117 } 118 119 func (arg *PointerArg) IsNull() bool { 120 return arg.Address == 0 && arg.VmaSize == 0 && arg.Res == nil 121 } 122 123 // Used for BufferType. 124 type DataArg struct { 125 ArgCommon 126 data []byte // for in/inout args 127 size uint64 // for out Args 128 } 129 130 func MakeDataArg(t Type, data []byte) *DataArg { 131 if t.Dir() == DirOut { 132 panic("non-empty output data arg") 133 } 134 return &DataArg{ArgCommon: ArgCommon{typ: t}, data: append([]byte{}, data...)} 135 } 136 137 func MakeOutDataArg(t Type, size uint64) *DataArg { 138 if t.Dir() != DirOut { 139 panic("empty input data arg") 140 } 141 return &DataArg{ArgCommon: ArgCommon{typ: t}, size: size} 142 } 143 144 func (arg *DataArg) Size() uint64 { 145 if len(arg.data) != 0 { 146 return uint64(len(arg.data)) 147 } 148 return arg.size 149 } 150 151 func (arg *DataArg) Data() []byte { 152 if arg.Type().Dir() == DirOut { 153 panic("getting data of output data arg") 154 } 155 return arg.data 156 } 157 158 // Used for StructType and ArrayType. 159 // Logical group of args (struct or array). 160 type GroupArg struct { 161 ArgCommon 162 Inner []Arg 163 } 164 165 func MakeGroupArg(t Type, inner []Arg) *GroupArg { 166 return &GroupArg{ArgCommon: ArgCommon{typ: t}, Inner: inner} 167 } 168 169 func (arg *GroupArg) Size() uint64 { 170 typ0 := arg.Type() 171 if !typ0.Varlen() { 172 return typ0.Size() 173 } 174 switch typ := typ0.(type) { 175 case *StructType: 176 var size uint64 177 for _, fld := range arg.Inner { 178 if !fld.Type().BitfieldMiddle() { 179 size += fld.Size() 180 } 181 } 182 if typ.AlignAttr != 0 && size%typ.AlignAttr != 0 { 183 size += typ.AlignAttr - size%typ.AlignAttr 184 } 185 return size 186 case *ArrayType: 187 var size uint64 188 for _, elem := range arg.Inner { 189 size += elem.Size() 190 } 191 return size 192 default: 193 panic(fmt.Sprintf("bad group arg type %v", typ)) 194 } 195 } 196 197 func (arg *GroupArg) fixedInnerSize() bool { 198 switch typ := arg.Type().(type) { 199 case *StructType: 200 return true 201 case *ArrayType: 202 return typ.Kind == ArrayRangeLen && typ.RangeBegin == typ.RangeEnd 203 default: 204 panic(fmt.Sprintf("bad group arg type %v", typ)) 205 } 206 } 207 208 // Used for UnionType. 209 type UnionArg struct { 210 ArgCommon 211 Option Arg 212 } 213 214 func MakeUnionArg(t Type, opt Arg) *UnionArg { 215 return &UnionArg{ArgCommon: ArgCommon{typ: t}, Option: opt} 216 } 217 218 func (arg *UnionArg) Size() uint64 { 219 if !arg.Type().Varlen() { 220 return arg.Type().Size() 221 } 222 return arg.Option.Size() 223 } 224 225 // Used for ResourceType. 226 // This is the only argument that can be used as syscall return value. 227 // Either holds constant value or reference another ResultArg. 228 type ResultArg struct { 229 ArgCommon 230 Res *ResultArg // reference to arg which we use 231 OpDiv uint64 // divide result (executed before OpAdd) 232 OpAdd uint64 // add to result 233 Val uint64 // value used if Res is nil 234 uses map[*ResultArg]bool // ArgResult args that use this arg 235 } 236 237 func MakeResultArg(t Type, r *ResultArg, v uint64) *ResultArg { 238 arg := &ResultArg{ArgCommon: ArgCommon{typ: t}, Res: r, Val: v} 239 if r == nil { 240 return arg 241 } 242 if r.uses == nil { 243 r.uses = make(map[*ResultArg]bool) 244 } 245 r.uses[arg] = true 246 return arg 247 } 248 249 func MakeReturnArg(t Type) *ResultArg { 250 if t == nil { 251 return nil 252 } 253 if t.Dir() != DirOut { 254 panic("return arg is not out") 255 } 256 return &ResultArg{ArgCommon: ArgCommon{typ: t}} 257 } 258 259 func (arg *ResultArg) Size() uint64 { 260 return arg.typ.Size() 261 } 262 263 // Returns inner arg for pointer args. 264 func InnerArg(arg Arg) Arg { 265 if t, ok := arg.Type().(*PtrType); ok { 266 if a, ok := arg.(*PointerArg); ok { 267 if a.Res == nil { 268 if !t.Optional() { 269 panic(fmt.Sprintf("non-optional pointer is nil\narg: %+v\ntype: %+v", a, t)) 270 } 271 return nil 272 } 273 return InnerArg(a.Res) 274 } 275 return nil // *ConstArg. 276 } 277 return arg // Not a pointer. 278 } 279 280 func isDefault(arg Arg) bool { 281 return arg.Type().isDefaultArg(arg) 282 } 283 284 func (p *Prog) insertBefore(c *Call, calls []*Call) { 285 idx := 0 286 for ; idx < len(p.Calls); idx++ { 287 if p.Calls[idx] == c { 288 break 289 } 290 } 291 var newCalls []*Call 292 newCalls = append(newCalls, p.Calls[:idx]...) 293 newCalls = append(newCalls, calls...) 294 if idx < len(p.Calls) { 295 newCalls = append(newCalls, p.Calls[idx]) 296 newCalls = append(newCalls, p.Calls[idx+1:]...) 297 } 298 p.Calls = newCalls 299 } 300 301 // replaceArg replaces arg with arg1 in a program. 302 func replaceArg(arg, arg1 Arg) { 303 switch a := arg.(type) { 304 case *ConstArg: 305 *a = *arg1.(*ConstArg) 306 case *ResultArg: 307 replaceResultArg(a, arg1.(*ResultArg)) 308 case *PointerArg: 309 *a = *arg1.(*PointerArg) 310 case *UnionArg: 311 *a = *arg1.(*UnionArg) 312 case *DataArg: 313 *a = *arg1.(*DataArg) 314 case *GroupArg: 315 a1 := arg1.(*GroupArg) 316 if len(a.Inner) != len(a1.Inner) { 317 panic(fmt.Sprintf("replaceArg: group fields don't match: %v/%v", 318 len(a.Inner), len(a1.Inner))) 319 } 320 a.ArgCommon = a1.ArgCommon 321 for i := range a.Inner { 322 replaceArg(a.Inner[i], a1.Inner[i]) 323 } 324 default: 325 panic(fmt.Sprintf("replaceArg: bad arg kind %#v", arg)) 326 } 327 } 328 329 func replaceResultArg(arg, arg1 *ResultArg) { 330 // Remove link from `a.Res` to `arg`. 331 if arg.Res != nil { 332 delete(arg.Res.uses, arg) 333 } 334 // Copy all fields from `arg1` to `arg` except for the list of args that use `arg`. 335 uses := arg.uses 336 *arg = *arg1 337 arg.uses = uses 338 // Make the link in `arg.Res` (which is now `Res` of `arg1`) to point to `arg` instead of `arg1`. 339 if arg.Res != nil { 340 resUses := arg.Res.uses 341 delete(resUses, arg1) 342 resUses[arg] = true 343 } 344 } 345 346 // removeArg removes all references to/from arg0 from a program. 347 func removeArg(arg0 Arg) { 348 ForeachSubArg(arg0, func(arg Arg, ctx *ArgCtx) { 349 a, ok := arg.(*ResultArg) 350 if !ok { 351 return 352 } 353 if a.Res != nil { 354 uses := a.Res.uses 355 if !uses[a] { 356 panic("broken tree") 357 } 358 delete(uses, a) 359 } 360 for arg1 := range a.uses { 361 arg2 := arg1.Type().makeDefaultArg().(*ResultArg) 362 replaceResultArg(arg1, arg2) 363 } 364 }) 365 } 366 367 // removeCall removes call idx from p. 368 func (p *Prog) removeCall(idx int) { 369 c := p.Calls[idx] 370 for _, arg := range c.Args { 371 removeArg(arg) 372 } 373 if c.Ret != nil { 374 removeArg(c.Ret) 375 } 376 copy(p.Calls[idx:], p.Calls[idx+1:]) 377 p.Calls = p.Calls[:len(p.Calls)-1] 378 } 379