1// Copyright 2023 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
5// Minimum mutator utilization (MMU) graphing.
6
7// TODO:
8//
9// In worst window list, show break-down of GC utilization sources
10// (STW, assist, etc). Probably requires a different MutatorUtil
11// representation.
12//
13// When a window size is selected, show a second plot of the mutator
14// utilization distribution for that window size.
15//
16// Render plot progressively so rough outline is visible quickly even
17// for very complex MUTs. Start by computing just a few window sizes
18// and then add more window sizes.
19//
20// Consider using sampling to compute an approximate MUT. This would
21// work by sampling the mutator utilization at randomly selected
22// points in time in the trace to build an empirical distribution. We
23// could potentially put confidence intervals on these estimates and
24// render this progressively as we refine the distributions.
25
26package traceviewer
27
28import (
29	"encoding/json"
30	"fmt"
31	"internal/trace"
32	"log"
33	"math"
34	"net/http"
35	"strconv"
36	"strings"
37	"sync"
38	"time"
39)
40
41type MutatorUtilFunc func(trace.UtilFlags) ([][]trace.MutatorUtil, error)
42
43func MMUHandlerFunc(ranges []Range, f MutatorUtilFunc) http.HandlerFunc {
44	mmu := &mmu{
45		cache:  make(map[trace.UtilFlags]*mmuCacheEntry),
46		f:      f,
47		ranges: ranges,
48	}
49	return func(w http.ResponseWriter, r *http.Request) {
50		switch r.FormValue("mode") {
51		case "plot":
52			mmu.HandlePlot(w, r)
53			return
54		case "details":
55			mmu.HandleDetails(w, r)
56			return
57		}
58		http.ServeContent(w, r, "", time.Time{}, strings.NewReader(templMMU))
59	}
60}
61
62var utilFlagNames = map[string]trace.UtilFlags{
63	"perProc":    trace.UtilPerProc,
64	"stw":        trace.UtilSTW,
65	"background": trace.UtilBackground,
66	"assist":     trace.UtilAssist,
67	"sweep":      trace.UtilSweep,
68}
69
70func requestUtilFlags(r *http.Request) trace.UtilFlags {
71	var flags trace.UtilFlags
72	for _, flagStr := range strings.Split(r.FormValue("flags"), "|") {
73		flags |= utilFlagNames[flagStr]
74	}
75	return flags
76}
77
78type mmuCacheEntry struct {
79	init     sync.Once
80	util     [][]trace.MutatorUtil
81	mmuCurve *trace.MMUCurve
82	err      error
83}
84
85type mmu struct {
86	mu     sync.Mutex
87	cache  map[trace.UtilFlags]*mmuCacheEntry
88	f      MutatorUtilFunc
89	ranges []Range
90}
91
92func (m *mmu) get(flags trace.UtilFlags) ([][]trace.MutatorUtil, *trace.MMUCurve, error) {
93	m.mu.Lock()
94	entry := m.cache[flags]
95	if entry == nil {
96		entry = new(mmuCacheEntry)
97		m.cache[flags] = entry
98	}
99	m.mu.Unlock()
100
101	entry.init.Do(func() {
102		util, err := m.f(flags)
103		if err != nil {
104			entry.err = err
105		} else {
106			entry.util = util
107			entry.mmuCurve = trace.NewMMUCurve(util)
108		}
109	})
110	return entry.util, entry.mmuCurve, entry.err
111}
112
113// HandlePlot serves the JSON data for the MMU plot.
114func (m *mmu) HandlePlot(w http.ResponseWriter, r *http.Request) {
115	mu, mmuCurve, err := m.get(requestUtilFlags(r))
116	if err != nil {
117		http.Error(w, fmt.Sprintf("failed to produce MMU data: %v", err), http.StatusInternalServerError)
118		return
119	}
120
121	var quantiles []float64
122	for _, flagStr := range strings.Split(r.FormValue("flags"), "|") {
123		if flagStr == "mut" {
124			quantiles = []float64{0, 1 - .999, 1 - .99, 1 - .95}
125			break
126		}
127	}
128
129	// Find a nice starting point for the plot.
130	xMin := time.Second
131	for xMin > 1 {
132		if mmu := mmuCurve.MMU(xMin); mmu < 0.0001 {
133			break
134		}
135		xMin /= 1000
136	}
137	// Cover six orders of magnitude.
138	xMax := xMin * 1e6
139	// But no more than the length of the trace.
140	minEvent, maxEvent := mu[0][0].Time, mu[0][len(mu[0])-1].Time
141	for _, mu1 := range mu[1:] {
142		if mu1[0].Time < minEvent {
143			minEvent = mu1[0].Time
144		}
145		if mu1[len(mu1)-1].Time > maxEvent {
146			maxEvent = mu1[len(mu1)-1].Time
147		}
148	}
149	if maxMax := time.Duration(maxEvent - minEvent); xMax > maxMax {
150		xMax = maxMax
151	}
152	// Compute MMU curve.
153	logMin, logMax := math.Log(float64(xMin)), math.Log(float64(xMax))
154	const samples = 100
155	plot := make([][]float64, samples)
156	for i := 0; i < samples; i++ {
157		window := time.Duration(math.Exp(float64(i)/(samples-1)*(logMax-logMin) + logMin))
158		if quantiles == nil {
159			plot[i] = make([]float64, 2)
160			plot[i][1] = mmuCurve.MMU(window)
161		} else {
162			plot[i] = make([]float64, 1+len(quantiles))
163			copy(plot[i][1:], mmuCurve.MUD(window, quantiles))
164		}
165		plot[i][0] = float64(window)
166	}
167
168	// Create JSON response.
169	err = json.NewEncoder(w).Encode(map[string]any{"xMin": int64(xMin), "xMax": int64(xMax), "quantiles": quantiles, "curve": plot})
170	if err != nil {
171		log.Printf("failed to serialize response: %v", err)
172		return
173	}
174}
175
176var templMMU = `<!doctype html>
177<html>
178  <head>
179    <meta charset="utf-8">
180    <script type="text/javascript" src="https://www.gstatic.com/charts/loader.js"></script>
181    <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/3.2.1/jquery.min.js"></script>
182    <script type="text/javascript">
183      google.charts.load('current', {'packages':['corechart']});
184      var chartsReady = false;
185      google.charts.setOnLoadCallback(function() { chartsReady = true; refreshChart(); });
186
187      var chart;
188      var curve;
189
190      function niceDuration(ns) {
191          if (ns < 1e3) { return ns + 'ns'; }
192          else if (ns < 1e6) { return ns / 1e3 + 'µs'; }
193          else if (ns < 1e9) { return ns / 1e6 + 'ms'; }
194          else { return ns / 1e9 + 's'; }
195      }
196
197      function niceQuantile(q) {
198        return 'p' + q*100;
199      }
200
201      function mmuFlags() {
202        var flags = "";
203        $("#options input").each(function(i, elt) {
204          if (elt.checked)
205            flags += "|" + elt.id;
206        });
207        return flags.substr(1);
208      }
209
210      function refreshChart() {
211        if (!chartsReady) return;
212        var container = $('#mmu_chart');
213        container.css('opacity', '.5');
214        refreshChart.count++;
215        var seq = refreshChart.count;
216        $.getJSON('?mode=plot&flags=' + mmuFlags())
217         .fail(function(xhr, status, error) {
218           alert('failed to load plot: ' + status);
219         })
220         .done(function(result) {
221           if (refreshChart.count === seq)
222             drawChart(result);
223         });
224      }
225      refreshChart.count = 0;
226
227      function drawChart(plotData) {
228        curve = plotData.curve;
229        var data = new google.visualization.DataTable();
230        data.addColumn('number', 'Window duration');
231        data.addColumn('number', 'Minimum mutator utilization');
232        if (plotData.quantiles) {
233          for (var i = 1; i < plotData.quantiles.length; i++) {
234            data.addColumn('number', niceQuantile(1 - plotData.quantiles[i]) + ' MU');
235          }
236        }
237        data.addRows(curve);
238        for (var i = 0; i < curve.length; i++) {
239          data.setFormattedValue(i, 0, niceDuration(curve[i][0]));
240        }
241
242        var options = {
243          chart: {
244            title: 'Minimum mutator utilization',
245          },
246          hAxis: {
247            title: 'Window duration',
248            scaleType: 'log',
249            ticks: [],
250          },
251          vAxis: {
252            title: 'Minimum mutator utilization',
253            minValue: 0.0,
254            maxValue: 1.0,
255          },
256          legend: { position: 'none' },
257          focusTarget: 'category',
258          width: 900,
259          height: 500,
260          chartArea: { width: '80%', height: '80%' },
261        };
262        for (var v = plotData.xMin; v <= plotData.xMax; v *= 10) {
263          options.hAxis.ticks.push({v:v, f:niceDuration(v)});
264        }
265        if (plotData.quantiles) {
266          options.vAxis.title = 'Mutator utilization';
267          options.legend.position = 'in';
268        }
269
270        var container = $('#mmu_chart');
271        container.empty();
272        container.css('opacity', '');
273        chart = new google.visualization.LineChart(container[0]);
274        chart = new google.visualization.LineChart(document.getElementById('mmu_chart'));
275        chart.draw(data, options);
276
277        google.visualization.events.addListener(chart, 'select', selectHandler);
278        $('#details').empty();
279      }
280
281      function selectHandler() {
282        var items = chart.getSelection();
283        if (items.length === 0) {
284          return;
285        }
286        var details = $('#details');
287        details.empty();
288        var windowNS = curve[items[0].row][0];
289        var url = '?mode=details&window=' + windowNS + '&flags=' + mmuFlags();
290        $.getJSON(url)
291         .fail(function(xhr, status, error) {
292            details.text(status + ': ' + url + ' could not be loaded');
293         })
294         .done(function(worst) {
295            details.text('Lowest mutator utilization in ' + niceDuration(windowNS) + ' windows:');
296            for (var i = 0; i < worst.length; i++) {
297              details.append($('<br>'));
298              var text = worst[i].MutatorUtil.toFixed(3) + ' at time ' + niceDuration(worst[i].Time);
299              details.append($('<a/>').text(text).attr('href', worst[i].URL));
300            }
301         });
302      }
303
304      $.when($.ready).then(function() {
305        $("#options input").click(refreshChart);
306      });
307    </script>
308    <style>
309      .help {
310        display: inline-block;
311        position: relative;
312        width: 1em;
313        height: 1em;
314        border-radius: 50%;
315        color: #fff;
316        background: #555;
317        text-align: center;
318        cursor: help;
319      }
320      .help > span {
321        display: none;
322      }
323      .help:hover > span {
324        display: block;
325        position: absolute;
326        left: 1.1em;
327        top: 1.1em;
328        background: #555;
329        text-align: left;
330        width: 20em;
331        padding: 0.5em;
332        border-radius: 0.5em;
333        z-index: 5;
334      }
335    </style>
336  </head>
337  <body>
338    <div style="position: relative">
339      <div id="mmu_chart" style="width: 900px; height: 500px; display: inline-block; vertical-align: top">Loading plot...</div>
340      <div id="options" style="display: inline-block; vertical-align: top">
341        <p>
342          <b>View</b><br>
343          <input type="radio" name="view" id="system" checked><label for="system">System</label>
344          <span class="help">?<span>Consider whole system utilization. For example, if one of four procs is available to the mutator, mutator utilization will be 0.25. This is the standard definition of an MMU.</span></span><br>
345          <input type="radio" name="view" id="perProc"><label for="perProc">Per-goroutine</label>
346          <span class="help">?<span>Consider per-goroutine utilization. When even one goroutine is interrupted by GC, mutator utilization is 0.</span></span><br>
347        </p>
348        <p>
349          <b>Include</b><br>
350          <input type="checkbox" id="stw" checked><label for="stw">STW</label>
351          <span class="help">?<span>Stop-the-world stops all goroutines simultaneously.</span></span><br>
352          <input type="checkbox" id="background" checked><label for="background">Background workers</label>
353          <span class="help">?<span>Background workers are GC-specific goroutines. 25% of the CPU is dedicated to background workers during GC.</span></span><br>
354          <input type="checkbox" id="assist" checked><label for="assist">Mark assist</label>
355          <span class="help">?<span>Mark assists are performed by allocation to prevent the mutator from outpacing GC.</span></span><br>
356          <input type="checkbox" id="sweep"><label for="sweep">Sweep</label>
357          <span class="help">?<span>Sweep reclaims unused memory between GCs. (Enabling this may be very slow.).</span></span><br>
358        </p>
359        <p>
360          <b>Display</b><br>
361          <input type="checkbox" id="mut"><label for="mut">Show percentiles</label>
362          <span class="help">?<span>Display percentile mutator utilization in addition to minimum. E.g., p99 MU drops the worst 1% of windows.</span></span><br>
363        </p>
364      </div>
365    </div>
366    <div id="details">Select a point for details.</div>
367  </body>
368</html>
369`
370
371// HandleDetails serves details of an MMU graph at a particular window.
372func (m *mmu) HandleDetails(w http.ResponseWriter, r *http.Request) {
373	_, mmuCurve, err := m.get(requestUtilFlags(r))
374	if err != nil {
375		http.Error(w, fmt.Sprintf("failed to produce MMU data: %v", err), http.StatusInternalServerError)
376		return
377	}
378
379	windowStr := r.FormValue("window")
380	window, err := strconv.ParseUint(windowStr, 10, 64)
381	if err != nil {
382		http.Error(w, fmt.Sprintf("failed to parse window parameter %q: %v", windowStr, err), http.StatusBadRequest)
383		return
384	}
385	worst := mmuCurve.Examples(time.Duration(window), 10)
386
387	// Construct a link for each window.
388	var links []linkedUtilWindow
389	for _, ui := range worst {
390		links = append(links, m.newLinkedUtilWindow(ui, time.Duration(window)))
391	}
392
393	err = json.NewEncoder(w).Encode(links)
394	if err != nil {
395		log.Printf("failed to serialize trace: %v", err)
396		return
397	}
398}
399
400type linkedUtilWindow struct {
401	trace.UtilWindow
402	URL string
403}
404
405func (m *mmu) newLinkedUtilWindow(ui trace.UtilWindow, window time.Duration) linkedUtilWindow {
406	// Find the range containing this window.
407	var r Range
408	for _, r = range m.ranges {
409		if r.EndTime > ui.Time {
410			break
411		}
412	}
413	return linkedUtilWindow{ui, fmt.Sprintf("%s#%v:%v", r.URL(ViewProc), float64(ui.Time)/1e6, float64(ui.Time+int64(window))/1e6)}
414}
415