all: replace collide mode by `async` call property

Replace the currently existing straightforward approach to race triggering
(that was almost entirely implemented inside syz-executor) with a more
flexible one.

The `async` call property instructs syz-executor not to block until the
call has completed execution and proceed immediately to the next call.
The decision on what calls to mark with `async` is made by syz-fuzzer.

Ultimately this should let us implement more intelligent race provoking
strategies as well as make more fine-grained reproducers.

1 files changed, 57 insertions, 0 deletions

diff --git a/prog/collide.go b/prog/collide.go
new file mode 100644
index 000000000..cd059c60f
--- /dev/null
+++ b/prog/collide.go
@@ -0,0 +1,57 @@
+// Copyright 2021 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+// Contains prog transformations that intend to trigger more races.
+
+package prog
+
+import "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
+// would force the executor to fail and thus stall the fuzzing process.
+// As an educated guess, let's use no more than 24 async calls to let executor handle everything.
+const maxAsyncPerProg = 24
+
+// Ensures that if an async call produces a resource, then
+// it is distanced from a call consuming the resource at least
+// by one non-async call.
+// This does not give 100% guarantee that the async call finishes
+// by that time, but hopefully this is enough for most cases.
+func AssignRandomAsync(origProg *Prog, rand *rand.Rand) *Prog {
+	var unassigned map[*ResultArg]bool
+	leftAsync := maxAsyncPerProg
+	prog := origProg.Clone()
+	for i := len(prog.Calls) - 1; i >= 0 && leftAsync > 0; i-- {
+		call := prog.Calls[i]
+		producesUnassigned := false
+		consumes := make(map[*ResultArg]bool)
+		ForeachArg(call, func(arg Arg, ctx *ArgCtx) {
+			res, ok := arg.(*ResultArg)
+			if !ok {
+				return
+			}
+			if res.Dir() != DirIn && unassigned[res] {
+				// If this call is made async, at least one of the resources
+				// will be empty when it's needed.
+				producesUnassigned = true
+			}
+			if res.Dir() != DirOut {
+				consumes[res.Res] = true
+			}
+		})
+		// Make async with a 66% chance (but never the last call).
+		if !producesUnassigned && i+1 != len(prog.Calls) && rand.Intn(3) != 0 {
+			call.Props.Async = true
+			for res := range consumes {
+				unassigned[res] = true
+			}
+			leftAsync--
+		} else {
+			call.Props.Async = false
+			unassigned = consumes
+		}
+	}
+
+	return prog
+}