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) {