prog: fix determinism in choice table

Floats bite.
We interated over uses map non-deterministically,
which would be fine overall except that it may
break floats due to rounding.

2 files changed, 39 insertions, 3 deletions

diff --git a/prog/prio.go b/prog/prio.go
index 3a3f31b63..e5966aa65 100644
--- a/prog/prio.go
+++ b/prog/prio.go
@@ -43,9 +43,21 @@ func (target *Target) calcStaticPriorities() [][]float32 {
 	for i := range prios {
 		prios[i] = make([]float32, len(target.Syscalls))
 	}
-	for _, calls := range uses {
-		for c0, w0 := range calls {
-			for c1, w1 := range calls {
+	var keys []string
+	for key := range uses {
+		keys = append(keys, key)
+	}
+	sort.Strings(keys)
+	for _, key := range keys {
+		var calls []int
+		for call := range uses[key] {
+			calls = append(calls, call)
+		}
+		sort.Ints(calls)
+		for _, c0 := range calls {
+			w0 := uses[key][c0]
+			for _, c1 := range calls {
+				w1 := uses[key][c1]
 				if c0 == c1 {
 					// Self-priority is assigned below.
 					continue
diff --git a/prog/prio_test.go b/prog/prio_test.go
index 4497233b4..dede67e5f 100644
--- a/prog/prio_test.go
+++ b/prog/prio_test.go
@@ -7,6 +7,8 @@ import (
 	"math/rand"
 	"reflect"
 	"testing"
+
+	"github.com/google/go-cmp/cmp"
 )
 
 func TestNormalizePrio(t *testing.T) {
@@ -67,3 +69,25 @@ func TestStaticPriorities(t *testing.T) {
 		}
 	}
 }
+
+func TestPrioDeterminism(t *testing.T) {
+	target, rs, iters := initTest(t)
+	ct := target.DefaultChoiceTable()
+	var corpus []*Prog
+	for i := 0; i < 100; i++ {
+		corpus = append(corpus, target.Generate(rs, 10, ct))
+	}
+	ct0 := target.BuildChoiceTable(corpus, nil)
+	ct1 := target.BuildChoiceTable(corpus, nil)
+	if diff := cmp.Diff(ct0.runs, ct1.runs); diff != "" {
+		t.Fatal(diff)
+	}
+	for i := 0; i < iters; i++ {
+		seed := rs.Int63()
+		call0 := ct0.choose(rand.New(rand.NewSource(seed)), -1)
+		call1 := ct1.choose(rand.New(rand.NewSource(seed)), -1)
+		if call0 != call1 {
+			t.Fatalf("seed=%v iter=%v call=%v/%v", seed, i, call0, call1)
+		}
+	}
+}