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// This file does serialization of programs for executor binary. 5// The format aims at simple parsing: binary and irreversible. 6 7// Exec format is an sequence of uint64's which encodes a sequence of calls. 8// The sequence is terminated by a speciall call execInstrEOF. 9// Each call is (call ID, copyout index, number of arguments, arguments...). 10// Each argument is (type, size, value). 11// There are 4 types of arguments: 12// - execArgConst: value is const value 13// - execArgResult: value is copyout index we want to reference 14// - execArgData: value is a binary blob (represented as ]size/8[ uint64's) 15// - execArgCsum: runtime checksum calculation 16// There are 2 other special calls: 17// - execInstrCopyin: copies its second argument into address specified by first argument 18// - execInstrCopyout: reads value at address specified by first argument (result can be referenced by execArgResult) 19 20package prog 21 22import ( 23 "fmt" 24 "sort" 25) 26 27const ( 28 execInstrEOF = ^uint64(iota) 29 execInstrCopyin 30 execInstrCopyout 31) 32 33const ( 34 execArgConst = uint64(iota) 35 execArgResult 36 execArgData 37 execArgCsum 38) 39 40const ( 41 ExecArgCsumInet = uint64(iota) 42) 43 44const ( 45 ExecArgCsumChunkData = uint64(iota) 46 ExecArgCsumChunkConst 47) 48 49const ( 50 ExecBufferSize = 2 << 20 51 ExecNoCopyout = ^uint64(0) 52) 53 54// SerializeForExec serializes program p for execution by process pid into the provided buffer. 55// Returns number of bytes written to the buffer. 56// If the provided buffer is too small for the program an error is returned. 57func (p *Prog) SerializeForExec(buffer []byte) (int, error) { 58 p.debugValidate() 59 w := &execContext{ 60 target: p.Target, 61 buf: buffer, 62 eof: false, 63 args: make(map[Arg]argInfo), 64 } 65 for _, c := range p.Calls { 66 w.csumMap, w.csumUses = calcChecksumsCall(c) 67 w.serializeCall(c) 68 } 69 w.write(execInstrEOF) 70 if w.eof { 71 return 0, fmt.Errorf("provided buffer is too small") 72 } 73 return len(buffer) - len(w.buf), nil 74} 75 76func (w *execContext) serializeCall(c *Call) { 77 // Calculate arg offsets within structs. 78 // Generate copyin instructions that fill in data into pointer arguments. 79 w.writeCopyin(c) 80 // Generate checksum calculation instructions starting from the last one, 81 // since checksum values can depend on values of the latter ones 82 w.writeChecksums() 83 // Generate the call itself. 84 w.write(uint64(c.Meta.ID)) 85 if c.Ret != nil && len(c.Ret.uses) != 0 { 86 if _, ok := w.args[c.Ret]; ok { 87 panic("argInfo is already created for return value") 88 } 89 w.args[c.Ret] = argInfo{Idx: w.copyoutSeq, Ret: true} 90 w.write(w.copyoutSeq) 91 w.copyoutSeq++ 92 } else { 93 w.write(ExecNoCopyout) 94 } 95 w.write(uint64(len(c.Args))) 96 for _, arg := range c.Args { 97 w.writeArg(arg) 98 } 99 // Generate copyout instructions that persist interesting return values. 100 w.writeCopyout(c) 101} 102 103func (target *Target) PhysicalAddr(arg *PointerArg) uint64 { 104 if arg.IsNull() { 105 return 0 106 } 107 return target.DataOffset + arg.Address 108} 109 110type execContext struct { 111 target *Target 112 buf []byte 113 eof bool 114 args map[Arg]argInfo 115 copyoutSeq uint64 116 // Per-call state cached here to not pass it through all functions. 117 csumMap map[Arg]CsumInfo 118 csumUses map[Arg]struct{} 119} 120 121type argInfo struct { 122 Addr uint64 // physical addr 123 Idx uint64 // copyout instruction index 124 Ret bool 125} 126 127func (w *execContext) writeCopyin(c *Call) { 128 ForeachArg(c, func(arg Arg, ctx *ArgCtx) { 129 if ctx.Base == nil { 130 return 131 } 132 addr := w.target.PhysicalAddr(ctx.Base) + ctx.Offset 133 if w.willBeUsed(arg) { 134 w.args[arg] = argInfo{Addr: addr} 135 } 136 switch arg.(type) { 137 case *GroupArg, *UnionArg: 138 return 139 } 140 typ := arg.Type() 141 if typ.Dir() == DirOut || IsPad(typ) || arg.Size() == 0 { 142 return 143 } 144 w.write(execInstrCopyin) 145 w.write(addr) 146 w.writeArg(arg) 147 }) 148} 149 150func (w *execContext) willBeUsed(arg Arg) bool { 151 if res, ok := arg.(*ResultArg); ok && len(res.uses) != 0 { 152 return true 153 } 154 _, ok1 := w.csumMap[arg] 155 _, ok2 := w.csumUses[arg] 156 return ok1 || ok2 157} 158 159func (w *execContext) writeChecksums() { 160 if len(w.csumMap) == 0 { 161 return 162 } 163 csumArgs := make([]Arg, 0, len(w.csumMap)) 164 for arg := range w.csumMap { 165 csumArgs = append(csumArgs, arg) 166 } 167 sort.Slice(csumArgs, func(i, j int) bool { 168 return w.args[csumArgs[i]].Addr < w.args[csumArgs[j]].Addr 169 }) 170 for i := len(csumArgs) - 1; i >= 0; i-- { 171 arg := csumArgs[i] 172 info := w.csumMap[arg] 173 if _, ok := arg.Type().(*CsumType); !ok { 174 panic("csum arg is not csum type") 175 } 176 w.write(execInstrCopyin) 177 w.write(w.args[arg].Addr) 178 w.write(execArgCsum) 179 w.write(arg.Size()) 180 switch info.Kind { 181 case CsumInet: 182 w.write(ExecArgCsumInet) 183 w.write(uint64(len(info.Chunks))) 184 for _, chunk := range info.Chunks { 185 switch chunk.Kind { 186 case CsumChunkArg: 187 w.write(ExecArgCsumChunkData) 188 w.write(w.args[chunk.Arg].Addr) 189 w.write(chunk.Arg.Size()) 190 case CsumChunkConst: 191 w.write(ExecArgCsumChunkConst) 192 w.write(chunk.Value) 193 w.write(chunk.Size) 194 default: 195 panic(fmt.Sprintf("csum chunk has unknown kind %v", chunk.Kind)) 196 } 197 } 198 default: 199 panic(fmt.Sprintf("csum arg has unknown kind %v", info.Kind)) 200 } 201 } 202} 203 204func (w *execContext) writeCopyout(c *Call) { 205 ForeachArg(c, func(arg Arg, _ *ArgCtx) { 206 if res, ok := arg.(*ResultArg); ok && len(res.uses) != 0 { 207 // Create a separate copyout instruction that has own Idx. 208 info := w.args[arg] 209 if info.Ret { 210 return // Idx is already assigned above. 211 } 212 info.Idx = w.copyoutSeq 213 w.copyoutSeq++ 214 w.args[arg] = info 215 w.write(execInstrCopyout) 216 w.write(info.Idx) 217 w.write(info.Addr) 218 w.write(arg.Size()) 219 } 220 }) 221} 222 223func (w *execContext) write(v uint64) { 224 if len(w.buf) < 8 { 225 w.eof = true 226 return 227 } 228 w.buf[0] = byte(v >> 0) 229 w.buf[1] = byte(v >> 8) 230 w.buf[2] = byte(v >> 16) 231 w.buf[3] = byte(v >> 24) 232 w.buf[4] = byte(v >> 32) 233 w.buf[5] = byte(v >> 40) 234 w.buf[6] = byte(v >> 48) 235 w.buf[7] = byte(v >> 56) 236 w.buf = w.buf[8:] 237} 238 239func (w *execContext) writeArg(arg Arg) { 240 switch a := arg.(type) { 241 case *ConstArg: 242 val, pidStride := a.Value() 243 typ := a.Type() 244 w.writeConstArg(a.Size(), val, typ.BitfieldOffset(), typ.BitfieldLength(), pidStride, typ.Format()) 245 case *ResultArg: 246 if a.Res == nil { 247 w.writeConstArg(a.Size(), a.Val, 0, 0, 0, a.Type().Format()) 248 } else { 249 info, ok := w.args[a.Res] 250 if !ok { 251 panic("no copyout index") 252 } 253 w.write(execArgResult) 254 meta := a.Size() | uint64(a.Type().Format())<<8 255 w.write(meta) 256 w.write(info.Idx) 257 w.write(a.OpDiv) 258 w.write(a.OpAdd) 259 w.write(a.Type().(*ResourceType).Default()) 260 } 261 case *PointerArg: 262 w.writeConstArg(a.Size(), w.target.PhysicalAddr(a), 0, 0, 0, FormatNative) 263 case *DataArg: 264 data := a.Data() 265 w.write(execArgData) 266 w.write(uint64(len(data))) 267 padded := len(data) 268 if pad := 8 - len(data)%8; pad != 8 { 269 padded += pad 270 } 271 if len(w.buf) < padded { 272 w.eof = true 273 } else { 274 copy(w.buf, data) 275 w.buf = w.buf[padded:] 276 } 277 case *UnionArg: 278 w.writeArg(a.Option) 279 default: 280 panic("unknown arg type") 281 } 282} 283 284func (w *execContext) writeConstArg(size, val, bfOffset, bfLength, pidStride uint64, bf BinaryFormat) { 285 w.write(execArgConst) 286 meta := size | uint64(bf)<<8 | bfOffset<<16 | bfLength<<24 | pidStride<<32 287 w.write(meta) 288 w.write(val) 289} 290