1// Copyright 2017 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package trace
6
7import (
8	"bytes"
9	"math"
10	"os"
11	"testing"
12	"time"
13)
14
15// aeq returns true if x and y are equal up to 8 digits (1 part in 100
16// million).
17func aeq(x, y float64) bool {
18	if x < 0 && y < 0 {
19		x, y = -x, -y
20	}
21	const digits = 8
22	factor := 1 - math.Pow(10, -digits+1)
23	return x*factor <= y && y*factor <= x
24}
25
26func TestMMU(t *testing.T) {
27	t.Parallel()
28
29	// MU
30	// 1.0  *****   *****   *****
31	// 0.5      *   *   *   *
32	// 0.0      *****   *****
33	//      0   1   2   3   4   5
34	util := [][]MutatorUtil{{
35		{0e9, 1},
36		{1e9, 0},
37		{2e9, 1},
38		{3e9, 0},
39		{4e9, 1},
40		{5e9, 0},
41	}}
42	mmuCurve := NewMMUCurve(util)
43
44	for _, test := range []struct {
45		window time.Duration
46		want   float64
47		worst  []float64
48	}{
49		{0, 0, []float64{}},
50		{time.Millisecond, 0, []float64{0, 0}},
51		{time.Second, 0, []float64{0, 0}},
52		{2 * time.Second, 0.5, []float64{0.5, 0.5}},
53		{3 * time.Second, 1 / 3.0, []float64{1 / 3.0}},
54		{4 * time.Second, 0.5, []float64{0.5}},
55		{5 * time.Second, 3 / 5.0, []float64{3 / 5.0}},
56		{6 * time.Second, 3 / 5.0, []float64{3 / 5.0}},
57	} {
58		if got := mmuCurve.MMU(test.window); !aeq(test.want, got) {
59			t.Errorf("for %s window, want mu = %f, got %f", test.window, test.want, got)
60		}
61		worst := mmuCurve.Examples(test.window, 2)
62		// Which exact windows are returned is unspecified
63		// (and depends on the exact banding), so we just
64		// check that we got the right number with the right
65		// utilizations.
66		if len(worst) != len(test.worst) {
67			t.Errorf("for %s window, want worst %v, got %v", test.window, test.worst, worst)
68		} else {
69			for i := range worst {
70				if worst[i].MutatorUtil != test.worst[i] {
71					t.Errorf("for %s window, want worst %v, got %v", test.window, test.worst, worst)
72					break
73				}
74			}
75		}
76	}
77}
78
79func TestMMUTrace(t *testing.T) {
80	// Can't be t.Parallel() because it modifies the
81	// testingOneBand package variable.
82	if testing.Short() {
83		// test input too big for all.bash
84		t.Skip("skipping in -short mode")
85	}
86
87	data, err := os.ReadFile("testdata/stress_1_10_good")
88	if err != nil {
89		t.Fatalf("failed to read input file: %v", err)
90	}
91	_, events, err := parse(bytes.NewReader(data), "")
92	if err != nil {
93		t.Fatalf("failed to parse trace: %s", err)
94	}
95	mu := MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist)
96	mmuCurve := NewMMUCurve(mu)
97
98	// Test the optimized implementation against the "obviously
99	// correct" implementation.
100	for window := time.Nanosecond; window < 10*time.Second; window *= 10 {
101		want := mmuSlow(mu[0], window)
102		got := mmuCurve.MMU(window)
103		if !aeq(want, got) {
104			t.Errorf("want %f, got %f mutator utilization in window %s", want, got, window)
105		}
106	}
107
108	// Test MUD with band optimization against MUD without band
109	// optimization. We don't have a simple testing implementation
110	// of MUDs (the simplest implementation is still quite
111	// complex), but this is still a pretty good test.
112	defer func(old int) { bandsPerSeries = old }(bandsPerSeries)
113	bandsPerSeries = 1
114	mmuCurve2 := NewMMUCurve(mu)
115	quantiles := []float64{0, 1 - .999, 1 - .99}
116	for window := time.Microsecond; window < time.Second; window *= 10 {
117		mud1 := mmuCurve.MUD(window, quantiles)
118		mud2 := mmuCurve2.MUD(window, quantiles)
119		for i := range mud1 {
120			if !aeq(mud1[i], mud2[i]) {
121				t.Errorf("for quantiles %v at window %v, want %v, got %v", quantiles, window, mud2, mud1)
122				break
123			}
124		}
125	}
126}
127
128func BenchmarkMMU(b *testing.B) {
129	data, err := os.ReadFile("testdata/stress_1_10_good")
130	if err != nil {
131		b.Fatalf("failed to read input file: %v", err)
132	}
133	_, events, err := parse(bytes.NewReader(data), "")
134	if err != nil {
135		b.Fatalf("failed to parse trace: %s", err)
136	}
137	mu := MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist|UtilSweep)
138	b.ResetTimer()
139
140	for i := 0; i < b.N; i++ {
141		mmuCurve := NewMMUCurve(mu)
142		xMin, xMax := time.Microsecond, time.Second
143		logMin, logMax := math.Log(float64(xMin)), math.Log(float64(xMax))
144		const samples = 100
145		for i := 0; i < samples; i++ {
146			window := time.Duration(math.Exp(float64(i)/(samples-1)*(logMax-logMin) + logMin))
147			mmuCurve.MMU(window)
148		}
149	}
150}
151
152func mmuSlow(util []MutatorUtil, window time.Duration) (mmu float64) {
153	if max := time.Duration(util[len(util)-1].Time - util[0].Time); window > max {
154		window = max
155	}
156
157	mmu = 1.0
158
159	// muInWindow returns the mean mutator utilization between
160	// util[0].Time and end.
161	muInWindow := func(util []MutatorUtil, end int64) float64 {
162		total := 0.0
163		var prevU MutatorUtil
164		for _, u := range util {
165			if u.Time > end {
166				total += prevU.Util * float64(end-prevU.Time)
167				break
168			}
169			total += prevU.Util * float64(u.Time-prevU.Time)
170			prevU = u
171		}
172		return total / float64(end-util[0].Time)
173	}
174	update := func() {
175		for i, u := range util {
176			if u.Time+int64(window) > util[len(util)-1].Time {
177				break
178			}
179			mmu = math.Min(mmu, muInWindow(util[i:], u.Time+int64(window)))
180		}
181	}
182
183	// Consider all left-aligned windows.
184	update()
185	// Reverse the trace. Slightly subtle because each MutatorUtil
186	// is a *change*.
187	rutil := make([]MutatorUtil, len(util))
188	if util[len(util)-1].Util != 0 {
189		panic("irreversible trace")
190	}
191	for i, u := range util {
192		util1 := 0.0
193		if i != 0 {
194			util1 = util[i-1].Util
195		}
196		rutil[len(rutil)-i-1] = MutatorUtil{Time: -u.Time, Util: util1}
197	}
198	util = rutil
199	// Consider all right-aligned windows.
200	update()
201	return
202}
203