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