pkg/fuzzer: mix in exec fuzz and exec gen

The fuzzer may become too busy doing potentially very long hint jobs,
while we want it to also keep exploring other parts of the input space.

If there are only smash and hint jobs left, ignore them for 33% of
executions.

Reduce the number of smash iterations:
1) If new coverage is found, we will likely repeat the smash job with a
   similar program.
2) We mostly do the same during exec fuzz anyway.

4 files changed, 54 insertions, 29 deletions

diff --git a/pkg/fuzzer/fuzzer.go b/pkg/fuzzer/fuzzer.go
index 8ce2ebe26..4582ada44 100644
--- a/pkg/fuzzer/fuzzer.go
+++ b/pkg/fuzzer/fuzzer.go
@@ -39,9 +39,6 @@ type Fuzzer struct {
 
 	runningJobs      atomic.Int64
 	queuedCandidates atomic.Int64
-
-	outOfQueue     atomic.Bool
-	outOfQueueNext atomic.Int64
 }
 
 func NewFuzzer(ctx context.Context, cfg *Config, rnd *rand.Rand,
@@ -177,16 +174,18 @@ func (fuzzer *Fuzzer) NextInput() *Request {
 }
 
 func (fuzzer *Fuzzer) nextInput() *Request {
-	// The fuzzer may get biased to one specific part of the kernel.
-	// Periodically generate random programs to ensure that the coverage
-	// is more uniform.
-	if !fuzzer.outOfQueue.Load() ||
-		fuzzer.outOfQueueNext.Add(1)%400 > 0 {
-		nextExec := fuzzer.nextExec.tryPop()
-		if nextExec != nil {
+	nextExec := fuzzer.nextExec.tryPop()
+
+	// The fuzzer may become too interested in potentially very long hint and smash jobs.
+	// Let's leave more space for new input space exploration.
+	if nextExec != nil {
+		if nextExec.prio.greaterThan(priority{smashPrio}) || fuzzer.nextRand()%3 != 0 {
 			return nextExec.value
+		} else {
+			fuzzer.nextExec.push(nextExec)
 		}
 	}
+
 	// Either generate a new input or mutate an existing one.
 	mutateRate := 0.95
 	if !fuzzer.Config.Coverage {
@@ -206,7 +205,11 @@ func (fuzzer *Fuzzer) nextInput() *Request {
 
 func (fuzzer *Fuzzer) startJob(newJob job) {
 	fuzzer.Logf(2, "started %T", newJob)
-	newJob.saveID(-fuzzer.nextJobID.Add(1))
+	if impl, ok := newJob.(jobSaveID); ok {
+		// E.g. for big and slow hint jobs, we would prefer not to serialize them,
+		// but rather to start them all in parallel.
+		impl.saveID(-fuzzer.nextJobID.Add(1))
+	}
 	go func() {
 		fuzzer.runningJobs.Add(1)
 		newJob.run(fuzzer)
@@ -228,15 +231,14 @@ func (fuzzer *Fuzzer) AddCandidates(candidates []Candidate) {
 	}
 }
 
-func (fuzzer *Fuzzer) EnableOutOfQueue() {
-	fuzzer.outOfQueue.Store(true)
+func (fuzzer *Fuzzer) rand() *rand.Rand {
+	return rand.New(rand.NewSource(fuzzer.nextRand()))
 }
 
-func (fuzzer *Fuzzer) rand() *rand.Rand {
+func (fuzzer *Fuzzer) nextRand() int64 {
 	fuzzer.mu.Lock()
-	seed := fuzzer.rnd.Int63()
-	fuzzer.mu.Unlock()
-	return rand.New(rand.NewSource(seed))
+	defer fuzzer.mu.Unlock()
+	return fuzzer.rnd.Int63()
 }
 
 func (fuzzer *Fuzzer) pushExec(req *Request, prio priority) {
diff --git a/pkg/fuzzer/job.go b/pkg/fuzzer/job.go
index f567fc2cc..a0412126f 100644
--- a/pkg/fuzzer/job.go
+++ b/pkg/fuzzer/job.go
@@ -25,10 +25,13 @@ const (
 
 type job interface {
 	run(fuzzer *Fuzzer)
-	saveID(id int64)
 	priority() priority
 }
 
+type jobSaveID interface {
+	saveID(id int64)
+}
+
 type ProgTypes int
 
 const (
@@ -42,6 +45,8 @@ type jobPriority struct {
 	prio priority
 }
 
+var _ jobSaveID = new(jobPriority)
+
 func newJobPriority(base int64) jobPriority {
 	prio := append(make(priority, 0, 2), base)
 	return jobPriority{prio}
@@ -146,9 +151,8 @@ func (job *triageJob) run(fuzzer *Fuzzer) {
 	fuzzer.Logf(2, "added new input for %q to the corpus:\n%s", logCallName, job.p.String())
 	if job.flags&progSmashed == 0 {
 		fuzzer.startJob(&smashJob{
-			p:           job.p.Clone(),
-			call:        job.call,
-			jobPriority: newJobPriority(smashPrio),
+			p:    job.p.Clone(),
+			call: job.call,
 		})
 	}
 	input := corpus.NewInput{
@@ -274,20 +278,19 @@ func getSignalAndCover(p *prog.Prog, info *ipc.ProgInfo, call int) (signal.Signa
 type smashJob struct {
 	p    *prog.Prog
 	call int
-	jobPriority
+}
+
+func (job *smashJob) priority() priority {
+	return priority{smashPrio}
 }
 
 func (job *smashJob) run(fuzzer *Fuzzer) {
 	fuzzer.Logf(2, "smashing the program %s (call=%d):", job.p, job.call)
 	if fuzzer.Config.Comparisons && job.call >= 0 {
-		fuzzer.startJob(&hintsJob{
-			p:           job.p.Clone(),
-			call:        job.call,
-			jobPriority: newJobPriority(smashPrio),
-		})
+		fuzzer.startJob(newHintsJob(job.p.Clone(), job.call))
 	}
 
-	const iters = 100
+	const iters = 75
 	rnd := fuzzer.rand()
 	for i := 0; i < iters; i++ {
 		p := job.p.Clone()
@@ -364,7 +367,17 @@ func (job *smashJob) faultInjection(fuzzer *Fuzzer) {
 type hintsJob struct {
 	p    *prog.Prog
 	call int
-	jobPriority
+}
+
+func newHintsJob(p *prog.Prog, call int) *hintsJob {
+	return &hintsJob{
+		p:    p,
+		call: call,
+	}
+}
+
+func (job *hintsJob) priority() priority {
+	return priority{smashPrio}
 }
 
 func (job *hintsJob) run(fuzzer *Fuzzer) {
diff --git a/pkg/fuzzer/prio_queue.go b/pkg/fuzzer/prio_queue.go
index cb35cebf7..c67b6216c 100644
--- a/pkg/fuzzer/prio_queue.go
+++ b/pkg/fuzzer/prio_queue.go
@@ -19,6 +19,14 @@ func (p priority) greaterThan(other priority) bool {
 			return false
 		}
 	}
+	for i := len(p); i < len(other); i++ {
+		if other[i] < 0 {
+			return true
+		}
+		if other[i] > 0 {
+			return false
+		}
+	}
 	return false
 }
 
diff --git a/pkg/fuzzer/prio_queue_test.go b/pkg/fuzzer/prio_queue_test.go
index df8b4e9b0..3b5b87105 100644
--- a/pkg/fuzzer/prio_queue_test.go
+++ b/pkg/fuzzer/prio_queue_test.go
@@ -14,6 +14,8 @@ func TestPriority(t *testing.T) {
 	assert.True(t, priority{1, 2}.greaterThan(priority{1, 1}))
 	assert.True(t, priority{3, 2}.greaterThan(priority{2, 3}))
 	assert.True(t, priority{1, -5}.greaterThan(priority{1, -10}))
+	assert.True(t, priority{1}.greaterThan(priority{1, -1}))
+	assert.False(t, priority{1}.greaterThan(priority{1, 1}))
 }
 
 func TestPrioQueueOrder(t *testing.T) {