prog: use dense indexes for copyout instructions

Fixes #174

3 files changed, 64 insertions, 48 deletions

diff --git a/prog/decodeexec.go b/prog/decodeexec.go
index 696de461e..e62569b42 100644
--- a/prog/decodeexec.go
+++ b/prog/decodeexec.go
@@ -71,22 +71,22 @@ func (target *Target) DeserializeExec(exec []byte) (ExecProg, error) {
 	}
 	p := ExecProg{
 		Calls:   dec.calls,
-		NumVars: dec.numInstr,
+		NumVars: dec.numVars,
 	}
 	return p, nil
 }
 
 type execDecoder struct {
-	target   *Target
-	data     []byte
-	err      error
-	numInstr uint64
-	call     ExecCall
-	calls    []ExecCall
+	target  *Target
+	data    []byte
+	err     error
+	numVars uint64
+	call    ExecCall
+	calls   []ExecCall
 }
 
 func (dec *execDecoder) parse() {
-	for ; dec.err == nil; dec.numInstr++ {
+	for dec.err == nil {
 		switch instr := dec.read(); instr {
 		case execInstrCopyin:
 			dec.commitCall()
@@ -96,7 +96,7 @@ func (dec *execDecoder) parse() {
 			})
 		case execInstrCopyout:
 			dec.call.Copyout = append(dec.call.Copyout, ExecCopyout{
-				Index: dec.numInstr,
+				Index: dec.read(),
 				Addr:  dec.read(),
 				Size:  dec.read(),
 			})
@@ -107,7 +107,7 @@ func (dec *execDecoder) parse() {
 				return
 			}
 			dec.call.Meta = dec.target.Syscalls[instr]
-			dec.call.Index = dec.numInstr
+			dec.call.Index = dec.read()
 			for i := dec.read(); i > 0; i-- {
 				switch arg := dec.readArg(); arg.(type) {
 				case ExecArgConst, ExecArgResult:
@@ -206,8 +206,17 @@ func (dec *execDecoder) setErr(err error) {
 }
 
 func (dec *execDecoder) commitCall() {
-	if dec.call.Meta != nil {
-		dec.calls = append(dec.calls, dec.call)
-		dec.call = ExecCall{}
+	if dec.call.Meta == nil {
+		return
 	}
+	if dec.call.Index != ExecNoCopyout && dec.numVars < dec.call.Index+1 {
+		dec.numVars = dec.call.Index + 1
+	}
+	for _, copyout := range dec.call.Copyout {
+		if dec.numVars < copyout.Index+1 {
+			dec.numVars = copyout.Index + 1
+		}
+	}
+	dec.calls = append(dec.calls, dec.call)
+	dec.call = ExecCall{}
 }
diff --git a/prog/encodingexec.go b/prog/encodingexec.go
index b89788378..86ec1f638 100644
--- a/prog/encodingexec.go
+++ b/prog/encodingexec.go
@@ -6,11 +6,11 @@
 
 // Exec format is an sequence of uint64's which encodes a sequence of calls.
 // The sequence is terminated by a speciall call execInstrEOF.
-// Each call is (call ID, number of arguments, arguments...).
+// Each call is (call ID, copyout index, number of arguments, arguments...).
 // Each argument is (type, size, value).
 // There are 4 types of arguments:
 //  - execArgConst: value is const value
-//  - execArgResult: value is index of a call whose result we want to reference
+//  - execArgResult: value is copyout index we want to reference
 //  - execArgData: value is a binary blob (represented as ]size/8[ uint64's)
 //  - execArgCsum: runtime checksum calculation
 // There are 2 other special calls:
@@ -48,6 +48,7 @@ const (
 
 const (
 	ExecBufferSize = 2 << 20
+	ExecNoCopyout  = ^uint64(0)
 )
 
 type Args []Arg
@@ -78,7 +79,7 @@ func (p *Prog) SerializeForExec(buffer []byte, pid int) (int, error) {
 			panic(fmt.Errorf("serializing invalid program: %v", err))
 		}
 	}
-	instrSeq := 0
+	var copyoutSeq uint64
 	w := &execContext{
 		target: p.Target,
 		buf:    buffer,
@@ -125,7 +126,6 @@ func (p *Prog) SerializeForExec(buffer []byte, pid int) (int, error) {
 						w.write(execInstrCopyin)
 						w.write(addr)
 						w.writeArg(arg1, pid)
-						instrSeq++
 					}
 				})
 			}
@@ -168,19 +168,21 @@ func (p *Prog) SerializeForExec(buffer []byte, pid int) (int, error) {
 				default:
 					panic(fmt.Sprintf("csum arg has unknown kind %v", csumMap[arg].Kind))
 				}
-				instrSeq++
 			}
 		}
 		// Generate the call itself.
 		w.write(uint64(c.Meta.ID))
+		if isUsed(c.Ret) {
+			w.args[c.Ret] = argInfo{Idx: copyoutSeq}
+			w.write(copyoutSeq)
+			copyoutSeq++
+		} else {
+			w.write(ExecNoCopyout)
+		}
 		w.write(uint64(len(c.Args)))
 		for _, arg := range c.Args {
 			w.writeArg(arg, pid)
 		}
-		if isUsed(c.Ret) {
-			w.args[c.Ret] = argInfo{Idx: instrSeq}
-		}
-		instrSeq++
 		// Generate copyout instructions that persist interesting return values.
 		foreachArg(c, func(arg, base Arg, _ *[]Arg) {
 			if !isUsed(arg) {
@@ -195,10 +197,11 @@ func (p *Prog) SerializeForExec(buffer []byte, pid int) (int, error) {
 					panic("arg base is not a pointer")
 				}
 				info := w.args[arg]
-				info.Idx = instrSeq
-				instrSeq++
+				info.Idx = copyoutSeq
+				copyoutSeq++
 				w.args[arg] = info
 				w.write(execInstrCopyout)
+				w.write(info.Idx)
 				w.write(info.Addr)
 				w.write(arg.Size())
 			default:
@@ -236,7 +239,7 @@ type execContext struct {
 
 type argInfo struct {
 	Addr uint64 // physical addr
-	Idx  int    // instruction index
+	Idx  uint64 // copyout instruction index
 }
 
 func (w *execContext) write(v uint64) {
@@ -271,9 +274,13 @@ func (w *execContext) writeArg(arg Arg, pid int) {
 			w.write(0) // bit field offset
 			w.write(0) // bit field length
 		} else {
+			info, ok := w.args[a.Res]
+			if !ok {
+				panic("no copyout index")
+			}
 			w.write(execArgResult)
 			w.write(a.Size())
-			w.write(uint64(w.args[a.Res].Idx))
+			w.write(info.Idx)
 			w.write(a.OpDiv)
 			w.write(a.OpAdd)
 		}
diff --git a/prog/encodingexec_test.go b/prog/encodingexec_test.go
index 8a0325f0a..15d58d873 100644
--- a/prog/encodingexec_test.go
+++ b/prog/encodingexec_test.go
@@ -48,23 +48,23 @@ func TestSerializeForExec(t *testing.T) {
 		{
 			"syz_test()",
 			[]uint64{
-				callID("syz_test"), 0,
+				callID("syz_test"), ExecNoCopyout, 0,
 				execInstrEOF,
 			},
 			&ExecProg{
 				Calls: []ExecCall{
 					{
 						Meta:  target.SyscallMap["syz_test"],
-						Index: 0,
+						Index: ExecNoCopyout,
 					},
 				},
-				NumVars: 1,
+				NumVars: 0,
 			},
 		},
 		{
 			"syz_test$int(0x1, 0x2, 0x3, 0x4, 0x5)",
 			[]uint64{
-				callID("syz_test$int"), 5,
+				callID("syz_test$int"), ExecNoCopyout, 5,
 				execArgConst, 8, 1, 0, 0,
 				execArgConst, 1, 2, 0, 0,
 				execArgConst, 2, 3, 0, 0,
@@ -82,7 +82,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 8, execArgConst, 1, 3, 0, 0,
 				execInstrCopyin, dataOffset + 10, execArgConst, 2, 4, 0, 0,
 				execInstrCopyin, dataOffset + 16, execArgConst, 8, 5, 0, 0,
-				callID("syz_test$align0"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$align0"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -95,7 +95,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 6, execArgConst, 1, 3, 0, 0,
 				execInstrCopyin, dataOffset + 7, execArgConst, 2, 4, 0, 0,
 				execInstrCopyin, dataOffset + 9, execArgConst, 8, 5, 0, 0,
-				callID("syz_test$align1"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$align1"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -106,7 +106,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 0, execArgConst, 1, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 1, execArgConst, 2, 0x43, 0, 0,
 				execInstrCopyin, dataOffset + 4, execArgConst, 2, 0x44, 0, 0,
-				callID("syz_test$align2"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$align2"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -117,7 +117,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 0, execArgConst, 1, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 1, execArgConst, 1, 0x43, 0, 0,
 				execInstrCopyin, dataOffset + 4, execArgConst, 1, 0x44, 0, 0,
-				callID("syz_test$align3"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$align3"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -128,7 +128,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 0, execArgConst, 1, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 1, execArgConst, 2, 0x43, 0, 0,
 				execInstrCopyin, dataOffset + 4, execArgConst, 1, 0x44, 0, 0,
-				callID("syz_test$align4"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$align4"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -142,7 +142,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 18, execArgConst, 2, 0x45, 0, 0,
 				execInstrCopyin, dataOffset + 20, execArgConst, 2, 0x46, 0, 0,
 				execInstrCopyin, dataOffset + 22, execArgConst, 1, 0x47, 0, 0,
-				callID("syz_test$align5"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$align5"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -152,7 +152,7 @@ func TestSerializeForExec(t *testing.T) {
 			[]uint64{
 				execInstrCopyin, dataOffset + 0, execArgConst, 1, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 4, execArgConst, 4, 0x43, 0, 0,
-				callID("syz_test$align6"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$align6"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -162,7 +162,7 @@ func TestSerializeForExec(t *testing.T) {
 			[]uint64{
 				execInstrCopyin, dataOffset + 0, execArgConst, 8, 1, 0, 0,
 				execInstrCopyin, dataOffset + 8, execArgConst, 1, 2, 0, 0,
-				callID("syz_test$union0"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$union0"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -172,7 +172,7 @@ func TestSerializeForExec(t *testing.T) {
 			[]uint64{
 				execInstrCopyin, dataOffset + 0, execArgConst, 4, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 8, execArgConst, 1, 0x43, 0, 0,
-				callID("syz_test$union1"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$union1"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -182,7 +182,7 @@ func TestSerializeForExec(t *testing.T) {
 			[]uint64{
 				execInstrCopyin, dataOffset + 0, execArgConst, 4, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 4, execArgConst, 1, 0x43, 0, 0,
-				callID("syz_test$union2"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$union2"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -194,7 +194,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 1, execArgConst, 2, 2, 0, 0,
 				execInstrCopyin, dataOffset + 3, execArgConst, 8, 3, 0, 0,
 				execInstrCopyin, dataOffset + 11, execArgConst, 8, 4, 0, 0,
-				callID("syz_test$array0"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$array0"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -204,7 +204,7 @@ func TestSerializeForExec(t *testing.T) {
 			[]uint64{
 				execInstrCopyin, dataOffset + 0, execArgConst, 1, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 1, execArgData, 5, 0x0504030201,
-				callID("syz_test$array1"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$array1"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -215,7 +215,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 0, execArgConst, 2, 0x42, 0, 0,
 				execInstrCopyin, dataOffset + 2, execArgData, 16, 0xbbbbbbbbaaaaaaaa, 0xddddddddcccccccc,
 				execInstrCopyin, dataOffset + 18, execArgConst, 2, 0x43, 0, 0,
-				callID("syz_test$array2"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$array2"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -227,7 +227,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 1, execArgConst, 2, 0x4200, 0, 0,
 				execInstrCopyin, dataOffset + 3, execArgConst, 4, 0x42000000, 0, 0,
 				execInstrCopyin, dataOffset + 7, execArgConst, 8, 0x4200000000000000, 0, 0,
-				callID("syz_test$end0"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$end0"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -238,7 +238,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 0, execArgConst, 2, 0x0e00, 0, 0,
 				execInstrCopyin, dataOffset + 2, execArgConst, 4, 0x42000000, 0, 0,
 				execInstrCopyin, dataOffset + 6, execArgConst, 8, 0x0100000000000000, 0, 0,
-				callID("syz_test$end1"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$end1"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -254,7 +254,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 24, execArgConst, 2, 0x42, 0, 11,
 				execInstrCopyin, dataOffset + 26, execArgConst, 2, 0x4200, 0, 11,
 				execInstrCopyin, dataOffset + 28, execArgConst, 1, 0x42, 0, 0,
-				callID("syz_test$bf0"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$bf0"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -266,7 +266,7 @@ func TestSerializeForExec(t *testing.T) {
 				execInstrCopyin, dataOffset + 0, execArgConst, 4, 0x42, 10, 10,
 				execInstrCopyin, dataOffset + 0, execArgConst, 4, 0x42, 20, 10,
 				execInstrCopyin, dataOffset + 4, execArgConst, 1, 0x42, 0, 0,
-				callID("syz_test$bf1"), 1, execArgConst, ptrSize, dataOffset, 0, 0,
+				callID("syz_test$bf1"), ExecNoCopyout, 1, execArgConst, ptrSize, dataOffset, 0, 0,
 				execInstrEOF,
 			},
 			nil,
@@ -274,7 +274,7 @@ func TestSerializeForExec(t *testing.T) {
 		{
 			"syz_test$res1(0xffff)",
 			[]uint64{
-				callID("syz_test$res1"), 1, execArgConst, 4, 0xffff, 0, 0,
+				callID("syz_test$res1"), ExecNoCopyout, 1, execArgConst, 4, 0xffff, 0, 0,
 				execInstrEOF,
 			},
 			nil,