prog: remove several sources of non-determinism

Non-determinism is bad:
 - it leads to flaky coverage reports
 - it makes test failures non-reproducible

Remove 4 sources of non-determinism related to maps:
 - file name generation
 - string generation
 - resource generation
 - hints generation

All a test that ensures all main operations are fully deterministic.

4 files changed, 109 insertions, 41 deletions

diff --git a/prog/hints.go b/prog/hints.go
index 63199439c..8ac3ed735 100644
--- a/prog/hints.go
+++ b/prog/hints.go
@@ -22,27 +22,26 @@ import (
 	"bytes"
 	"encoding/binary"
 	"fmt"
+	"sort"
 )
 
-type uint64Set map[uint64]bool
-
 // Example: for comparisons {(op1, op2), (op1, op3), (op1, op4), (op2, op1)}
 // this map will store the following:
 // m = {
 //		op1: {map[op2]: true, map[op3]: true, map[op4]: true},
 //		op2: {map[op1]: true}
 // }.
-type CompMap map[uint64]uint64Set
+type CompMap map[uint64]map[uint64]bool
 
 const (
 	maxDataLength = 100
 )
 
-var specialIntsSet uint64Set
+var specialIntsSet map[uint64]bool
 
 func (m CompMap) AddComp(arg1, arg2 uint64) {
 	if _, ok := m[arg1]; !ok {
-		m[arg1] = make(uint64Set)
+		m[arg1] = make(map[uint64]bool)
 	}
 	m[arg1][arg2] = true
 }
@@ -106,7 +105,9 @@ func generateHints(compMap CompMap, arg Arg, exec func()) {
 
 func checkConstArg(arg *ConstArg, compMap CompMap, exec func()) {
 	original := arg.Val
-	for replacer := range shrinkExpand(original, compMap) {
+	// Note: because shrinkExpand returns a map, order of programs is non-deterministic.
+	// This can affect test coverage reports.
+	for _, replacer := range shrinkExpand(original, compMap) {
 		arg.Val = replacer
 		exec()
 	}
@@ -124,7 +125,7 @@ func checkDataArg(arg *DataArg, compMap CompMap, exec func()) {
 		original := make([]byte, 8)
 		copy(original, data[i:])
 		val := binary.LittleEndian.Uint64(original)
-		for replacer := range shrinkExpand(val, compMap) {
+		for _, replacer := range shrinkExpand(val, compMap) {
 			binary.LittleEndian.PutUint64(bytes, replacer)
 			copy(data[i:], bytes)
 			exec()
@@ -163,7 +164,8 @@ func checkDataArg(arg *DataArg, compMap CompMap, exec func()) {
 // As with shrink we ignore cases when the other operand is wider.
 // Note that executor sign extends all the comparison operands to int64.
 // ======================================================================
-func shrinkExpand(v uint64, compMap CompMap) (replacers uint64Set) {
+func shrinkExpand(v uint64, compMap CompMap) []uint64 {
+	var replacers map[uint64]bool
 	for _, iwidth := range []int{8, 4, 2, 1, -4, -2, -1} {
 		var width int
 		var size, mutant uint64
@@ -210,17 +212,27 @@ func shrinkExpand(v uint64, compMap CompMap) (replacers uint64Set) {
 				// TODO(dvyukov): should we try replacing with arg+/-1?
 				// This could trigger some off-by-ones.
 				if replacers == nil {
-					replacers = make(uint64Set)
+					replacers = make(map[uint64]bool)
 				}
 				replacers[replacer] = true
 			}
 		}
 	}
-	return
+	if replacers == nil {
+		return nil
+	}
+	res := make([]uint64, 0, len(replacers))
+	for v := range replacers {
+		res = append(res, v)
+	}
+	sort.Slice(res, func(i, j int) bool {
+		return res[i] < res[j]
+	})
+	return res
 }
 
 func init() {
-	specialIntsSet = make(uint64Set)
+	specialIntsSet = make(map[uint64]bool)
 	for _, v := range specialInts {
 		specialIntsSet[v] = true
 	}
diff --git a/prog/hints_test.go b/prog/hints_test.go
index 7cbabd992..873a3d73a 100644
--- a/prog/hints_test.go
+++ b/prog/hints_test.go
@@ -12,11 +12,13 @@ import (
 	"testing"
 )
 
+type uint64Set map[uint64]bool
+
 type ConstArgTest struct {
 	name  string
 	in    uint64
 	comps CompMap
-	res   uint64Set
+	res   []uint64
 }
 
 type DataArgTest struct {
@@ -35,7 +37,7 @@ func TestHintsCheckConstArg(t *testing.T) {
 			"One replacer test",
 			0xdeadbeef,
 			CompMap{0xdeadbeef: uint64Set{0xcafebabe: true}},
-			uint64Set{0xcafebabe: true},
+			[]uint64{0xcafebabe},
 		},
 		// Test for cases when there's multiple comparisons (op1, op2), (op1, op3), ...
 		// Checks that for every such operand a program is generated.
@@ -43,23 +45,23 @@ func TestHintsCheckConstArg(t *testing.T) {
 			"Multiple replacers test",
 			0xabcd,
 			CompMap{0xabcd: uint64Set{0x2: true, 0x3: true}},
-			uint64Set{0x2: true, 0x3: true},
+			[]uint64{0x2, 0x3},
 		},
 		// Checks that special ints are not used.
 		{
 			"Special ints test",
 			0xabcd,
 			CompMap{0xabcd: uint64Set{0x1: true, 0x2: true}},
-			uint64Set{0x2: true},
+			[]uint64{0x2},
 		},
 	}
 	for _, test := range tests {
 		t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) {
 			t.Parallel()
-			res := uint64Set{}
+			var res []uint64
 			constArg := &ConstArg{ArgCommon{nil}, test.in}
 			checkConstArg(constArg, test.comps, func() {
-				res[constArg.Val] = true
+				res = append(res, constArg.Val)
 			})
 			if !reflect.DeepEqual(res, test.res) {
 				t.Fatalf("\ngot : %v\nwant: %v", res, test.res)
@@ -236,7 +238,7 @@ func TestHintsShrinkExpand(t *testing.T) {
 				0x34:   uint64Set{0xab: true},
 				0x1234: uint64Set{0xcdcd: true},
 			},
-			uint64Set{0x12ab: true, 0xcdcd: true},
+			[]uint64{0x12ab, 0xcdcd},
 		},
 		{
 			// Models the following code:
@@ -254,7 +256,7 @@ func TestHintsShrinkExpand(t *testing.T) {
 				0x5678:     uint64Set{0xcdcd: true},
 				0x12345678: uint64Set{0xefefefef: true},
 			},
-			uint64Set{0x123456ab: true, 0x1234cdcd: true, 0xefefefef: true},
+			[]uint64{0x123456ab, 0x1234cdcd, 0xefefefef},
 		},
 		{
 			// Models the following code:
@@ -275,11 +277,11 @@ func TestHintsShrinkExpand(t *testing.T) {
 				0x90abcdef:         uint64Set{0xefefefef: true},
 				0x1234567890abcdef: uint64Set{0x0101010101010101: true},
 			},
-			uint64Set{
-				0x1234567890abcdab: true,
-				0x1234567890abcdcd: true,
-				0x12345678efefefef: true,
-				0x0101010101010101: true,
+			[]uint64{
+				0x1234567890abcdab,
+				0x1234567890abcdcd,
+				0x12345678efefefef,
+				0x0101010101010101,
 			},
 		},
 		{
@@ -310,7 +312,7 @@ func TestHintsShrinkExpand(t *testing.T) {
 			"Shrink with a wider replacer test2",
 			0x1234,
 			CompMap{0x34: uint64Set{0xfffffffffffffffd: true}},
-			uint64Set{0x12fd: true},
+			[]uint64{0x12fd},
 		},
 		// -----------------------------------------------------------------
 		// Extend tests:
@@ -325,7 +327,7 @@ func TestHintsShrinkExpand(t *testing.T) {
 			"Extend 8 test",
 			0xff,
 			CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}},
-			uint64Set{0xfe: true},
+			[]uint64{0xfe},
 		},
 		{
 			// Models the following code:
@@ -336,7 +338,7 @@ func TestHintsShrinkExpand(t *testing.T) {
 			"Extend 16 test",
 			0xffff,
 			CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}},
-			uint64Set{0xfffe: true},
+			[]uint64{0xfffe},
 		},
 		{
 			// Models the following code:
@@ -347,7 +349,7 @@ func TestHintsShrinkExpand(t *testing.T) {
 			"Extend 32 test",
 			0xffffffff,
 			CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}},
-			uint64Set{0xfffffffe: true},
+			[]uint64{0xfffffffe},
 		},
 		{
 			// Models the following code:
@@ -426,6 +428,7 @@ func extractValues(c *Call) map[uint64]bool {
 			}
 		}
 	})
+	delete(vals, 0) // replacing 0 can yield too many condidates
 	return vals
 }
 
diff --git a/prog/rand.go b/prog/rand.go
index c3b7c2352..c1ac76776 100644
--- a/prog/rand.go
+++ b/prog/rand.go
@@ -9,6 +9,7 @@ import (
 	"math"
 	"math/rand"
 	"path/filepath"
+	"sort"
 	"strings"
 
 	"github.com/google/syzkaller/pkg/ifuzz"
@@ -188,11 +189,7 @@ func (r *randGen) filenameImpl(s *state) string {
 		// Generate a new name.
 		dir := "."
 		if r.oneOf(2) && len(s.files) != 0 {
-			files := make([]string, 0, len(s.files))
-			for f := range s.files {
-				files = append(files, f)
-			}
-			dir = files[r.Intn(len(files))]
+			dir = r.randFromMap(s.files)
 			if len(dir) > 0 && dir[len(dir)-1] == 0 {
 				dir = dir[:len(dir)-1]
 			}
@@ -207,10 +204,15 @@ func (r *randGen) filenameImpl(s *state) string {
 			}
 		}
 	}
-	files := make([]string, 0, len(s.files))
-	for f := range s.files {
+	return r.randFromMap(s.files)
+}
+
+func (r *randGen) randFromMap(m map[string]bool) string {
+	files := make([]string, 0, len(m))
+	for f := range m {
 		files = append(files, f)
 	}
+	sort.Strings(files)
 	return files[r.Intn(len(files))]
 }
 
@@ -221,11 +223,7 @@ func (r *randGen) randString(s *state, t *BufferType) []byte {
 	if len(s.strings) != 0 && r.bin() {
 		// Return an existing string.
 		// TODO(dvyukov): make s.strings indexed by string SubKind.
-		strings := make([]string, 0, len(s.strings))
-		for s := range s.strings {
-			strings = append(strings, s)
-		}
-		return []byte(strings[r.Intn(len(strings))])
+		return []byte(r.randFromMap(s.strings))
 	}
 	punct := []byte{'!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '+', '\\',
 		'/', ':', '.', ',', '-', '\'', '[', ']', '{', '}'}
@@ -275,6 +273,7 @@ func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls []
 				all = append(all, kind1)
 			}
 		}
+		sort.Strings(all)
 		kind = all[r.Intn(len(all))]
 	}
 	// Find calls that produce the necessary resources.
@@ -585,8 +584,16 @@ func (a *ResourceType) generate(r *randGen, s *state) (arg Arg, calls []*Call) {
 	switch {
 	case r.nOutOf(1000, 1011):
 		// Get an existing resource.
+		alltypes := make([][]*ResultArg, 0, len(s.resources))
+		for _, res1 := range s.resources {
+			alltypes = append(alltypes, res1)
+		}
+		sort.Slice(alltypes, func(i, j int) bool {
+			return alltypes[i][0].Type().Name() < alltypes[j][0].Type().Name()
+		})
 		var allres []*ResultArg
-		for name1, res1 := range s.resources {
+		for _, res1 := range alltypes {
+			name1 := res1[0].Type().Name()
 			if r.target.isCompatibleResource(a.Desc.Name, name1) ||
 				r.oneOf(20) && r.target.isCompatibleResource(a.Desc.Kind[0], name1) {
 				allres = append(allres, res1...)
diff --git a/prog/rand_test.go b/prog/rand_test.go
index 1771a0052..d96d96260 100644
--- a/prog/rand_test.go
+++ b/prog/rand_test.go
@@ -24,3 +24,49 @@ func TestNotEscaping(t *testing.T) {
 		}
 	}
 }
+
+func TestDeterminism(t *testing.T) {
+	target, rs, iters := initTest(t)
+	iters /= 10 // takes too long
+	for i := 0; i < iters; i++ {
+		seed := rs.Int63()
+		rs1 := rand.NewSource(seed)
+		p1 := generateProg(t, target, rs1)
+		rs2 := rand.NewSource(seed)
+		p2 := generateProg(t, target, rs2)
+		ps1 := string(p1.Serialize())
+		ps2 := string(p2.Serialize())
+		r1 := rs1.Int63()
+		r2 := rs2.Int63()
+		if r1 != r2 || ps1 != ps2 {
+			t.Errorf("seed=%v\nprog 1 (%v):\n%v\nprog 2 (%v):\n%v", seed, r1, ps1, r2, ps2)
+		}
+	}
+}
+
+func generateProg(t *testing.T, target *Target, rs rand.Source) *Prog {
+	p := target.Generate(rs, 5, nil)
+	p.Mutate(rs, 10, nil, nil)
+	for i, c := range p.Calls {
+		comps := make(CompMap)
+		for v := range extractValues(c) {
+			comps.AddComp(v, v+1)
+			comps.AddComp(v, v+10)
+		}
+		p.MutateWithHints(i, comps, func(p1 *Prog) {
+			p = p1.Clone()
+		})
+	}
+	for _, crash := range []bool{false, true} {
+		p, _ = Minimize(p, -1, crash, func(*Prog, int) bool {
+			return rs.Int63()%10 == 0
+		})
+	}
+	data := p.Serialize()
+	var err error
+	p, err = target.Deserialize(data, NonStrict)
+	if err != nil {
+		t.Fatal(err)
+	}
+	return p
+}