all: add the `DoubleExecCollide` strategy

Add a strategy that resembles the previous collide mode, but detaches not
every other call, rather all calls during the second execution (or at least
as much as possible). Follow the strategy for 33% of all collide
executions.

It was shown during the experiments that this strategy has a positive
effect on the number of discovered crashes and bugs.

4 files changed, 119 insertions, 10 deletions

diff --git a/prog/clone.go b/prog/clone.go
index d1e23409b..9fa660e67 100644
--- a/prog/clone.go
+++ b/prog/clone.go
@@ -8,12 +8,18 @@ import (
 )
 
 func (p *Prog) Clone() *Prog {
+	newargs := make(map[*ResultArg]*ResultArg)
 	p1 := &Prog{
 		Target: p.Target,
-		Calls:  make([]*Call, len(p.Calls)),
+		Calls:  cloneCalls(p.Calls, newargs),
 	}
-	newargs := make(map[*ResultArg]*ResultArg)
-	for ci, c := range p.Calls {
+	p1.debugValidate()
+	return p1
+}
+
+func cloneCalls(origCalls []*Call, newargs map[*ResultArg]*ResultArg) []*Call {
+	calls := make([]*Call, len(origCalls))
+	for ci, c := range origCalls {
 		c1 := new(Call)
 		c1.Meta = c.Meta
 		if c.Ret != nil {
@@ -24,10 +30,9 @@ func (p *Prog) Clone() *Prog {
 			c1.Args[ai] = clone(arg, newargs)
 		}
 		c1.Props = c.Props
-		p1.Calls[ci] = c1
+		calls[ci] = c1
 	}
-	p1.debugValidate()
-	return p1
+	return calls
 }
 
 func clone(arg Arg, newargs map[*ResultArg]*ResultArg) Arg {
@@ -67,15 +72,20 @@ func clone(arg Arg, newargs map[*ResultArg]*ResultArg) Arg {
 		*a1 = *a
 		arg1 = a1
 		if a1.Res != nil {
-			r := newargs[a1.Res]
-			a1.Res = r
+			r := a1.Res
+			if newargs != nil {
+				r = newargs[a1.Res]
+				a1.Res = r
+			}
 			if r.uses == nil {
 				r.uses = make(map[*ResultArg]bool)
 			}
 			r.uses[a1] = true
 		}
 		a1.uses = nil // filled when we clone the referent
-		newargs[a] = a1
+		if newargs != nil {
+			newargs[a] = a1
+		}
 	default:
 		panic(fmt.Sprintf("bad arg kind: %#v", arg))
 	}
diff --git a/prog/collide.go b/prog/collide.go
index 77065147f..fea8cc146 100644
--- a/prog/collide.go
+++ b/prog/collide.go
@@ -5,7 +5,10 @@
 
 package prog
 
-import "math/rand"
+import (
+	"fmt"
+	"math/rand"
+)
 
 // The executor has no more than 32 threads that are used both for async calls and for calls
 // that timed out. If we just ignore that limit, we could end up generating programs that
@@ -71,3 +74,26 @@ func AssignRandomRerun(prog *Prog, rand *rand.Rand) {
 		i++
 	}
 }
+
+// We append prog to itself, but let the second part only reference resource from the first one.
+// Then we execute all the duplicated calls simultaneously.
+// This somehow resembles the way the previous collide mode was implemented - a program was executed
+// normally and then one more time again, while keeping resource values from the first execution and
+// not waiting until every other call finishes.
+func DoubleExecCollide(origProg *Prog, rand *rand.Rand) (*Prog, error) {
+	if len(origProg.Calls)*2 > MaxCalls {
+		return nil, fmt.Errorf("the prog is too big for the DoubleExecCollide transformation")
+	}
+	prog := origProg.Clone()
+	dupCalls := cloneCalls(prog.Calls, nil)
+	leftAsync := maxAsyncPerProg
+	for _, c := range dupCalls {
+		if leftAsync == 0 {
+			break
+		}
+		c.Props.Async = true
+		leftAsync--
+	}
+	prog.Calls = append(prog.Calls, dupCalls...)
+	return prog, nil
+}
diff --git a/prog/collide_test.go b/prog/collide_test.go
index 614b677ef..269b541ff 100644
--- a/prog/collide_test.go
+++ b/prog/collide_test.go
@@ -82,3 +82,69 @@ r4 = dup(r3)
 		t.Fatalf("not a single async was assigned")
 	}
 }
+
+func TestDoubleExecCollide(t *testing.T) {
+	tests := []struct {
+		os         string
+		arch       string
+		orig       string
+		duplicated string
+		shouldFail bool
+	}{
+		{
+			"linux", "amd64",
+			`r0 = openat(0xffffffffffffff9c, &AUTO='./file1\x00', 0x42, 0x1ff)
+r1 = dup(r0)
+r2 = dup(r1)
+r3 = dup(r2)
+r4 = dup(r2)
+r5 = dup(r3)
+`,
+			`r0 = openat(0xffffffffffffff9c, &(0x7f0000000040)='./file1\x00', 0x42, 0x1ff)
+r1 = dup(r0)
+r2 = dup(r1)
+r3 = dup(r2)
+dup(r2)
+dup(r3)
+openat(0xffffffffffffff9c, &(0x7f0000000040)='./file1\x00', 0x42, 0x1ff)
+dup(r0)
+dup(r1)
+dup(r2)
+dup(r2)
+dup(r3)
+`,
+			false,
+		},
+	}
+	_, rs, iters := initTest(t)
+	r := rand.New(rs)
+	for _, test := range tests {
+		target, err := GetTarget(test.os, test.arch)
+		if err != nil {
+			t.Fatal(err)
+		}
+		p, err := target.Deserialize([]byte(test.orig), Strict)
+		if err != nil {
+			t.Fatal(err)
+		}
+		for i := 0; i < iters; i++ {
+			collided, err := DoubleExecCollide(p, r)
+			if test.shouldFail && err == nil {
+				t.Fatalf("expected to fail, but it hasn't")
+			} else if !test.shouldFail && err != nil {
+				t.Fatalf("unexpected error: %s", err)
+			}
+			if test.duplicated != "" {
+				woProps := collided.Clone()
+				for _, c := range woProps.Calls {
+					c.Props = CallProps{}
+				}
+				serialized := string(woProps.Serialize())
+				if serialized != test.duplicated {
+					t.Fatalf("expected:%s\ngot:%s\n", test.duplicated, serialized)
+				}
+			}
+			// TODO: also test the `async` assignment.
+		}
+	}
+}
diff --git a/syz-fuzzer/proc.go b/syz-fuzzer/proc.go
index 55d718f88..96d10a7ec 100644
--- a/syz-fuzzer/proc.go
+++ b/syz-fuzzer/proc.go
@@ -288,6 +288,13 @@ func (proc *Proc) executeAndCollide(execOpts *ipc.ExecOpts, p *prog.Prog, flags
 }
 
 func (proc *Proc) randomCollide(origP *prog.Prog) *prog.Prog {
+	// Old-styl collide with a 33% probability.
+	if proc.rnd.Intn(3) == 0 {
+		p, err := prog.DoubleExecCollide(origP, proc.rnd)
+		if err == nil {
+			return p
+		}
+	}
 	p := prog.AssignRandomAsync(origP, proc.rnd)
 	if proc.rnd.Intn(2) != 0 {
 		prog.AssignRandomRerun(p, proc.rnd)