From 49e6369fe732c0f81e5b03b36e345afbf3c79a15 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Wed, 24 Jul 2024 12:08:49 +0200 Subject: pkg/stat: rename package name to singular form Go package names should generally be singular form: https://go.dev/blog/package-names https://rakyll.org/style-packages https://groups.google.com/g/golang-nuts/c/buBwLar1gNw --- pkg/corpus/corpus.go | 20 +- pkg/flatrpc/conn.go | 10 +- pkg/fuzzer/cover.go | 6 +- pkg/fuzzer/fuzzer.go | 4 +- pkg/fuzzer/queue/queue.go | 4 +- pkg/fuzzer/stats.go | 104 ++++----- pkg/rpcserver/rpcserver.go | 40 ++-- pkg/rpcserver/runner.go | 14 +- pkg/stat/avg.go | 32 +++ pkg/stat/sample/pvalue.go | 20 ++ pkg/stat/sample/sample.go | 73 ++++++ pkg/stat/sample/sample_test.go | 66 ++++++ pkg/stat/set.go | 488 ++++++++++++++++++++++++++++++++++++++++ pkg/stat/set_test.go | 219 ++++++++++++++++++ pkg/stat/syzbotstats/bug.go | 32 +++ pkg/stats/avg.go | 32 --- pkg/stats/sample/pvalue.go | 20 -- pkg/stats/sample/sample.go | 73 ------ pkg/stats/sample/sample_test.go | 66 ------ pkg/stats/set.go | 488 ---------------------------------------- pkg/stats/set_test.go | 219 ------------------ pkg/stats/syzbotstats/bug.go | 32 --- 22 files changed, 1031 insertions(+), 1031 deletions(-) create mode 100644 pkg/stat/avg.go create mode 100644 pkg/stat/sample/pvalue.go create mode 100644 pkg/stat/sample/sample.go create mode 100644 pkg/stat/sample/sample_test.go create mode 100644 pkg/stat/set.go create mode 100644 pkg/stat/set_test.go create mode 100644 pkg/stat/syzbotstats/bug.go delete mode 100644 pkg/stats/avg.go delete mode 100644 pkg/stats/sample/pvalue.go delete mode 100644 pkg/stats/sample/sample.go delete mode 100644 pkg/stats/sample/sample_test.go delete mode 100644 pkg/stats/set.go delete mode 100644 pkg/stats/set_test.go delete mode 100644 pkg/stats/syzbotstats/bug.go (limited to 'pkg') diff --git a/pkg/corpus/corpus.go b/pkg/corpus/corpus.go index af5754273..8b70b0cfd 100644 --- a/pkg/corpus/corpus.go +++ b/pkg/corpus/corpus.go @@ -10,7 +10,7 @@ import ( "github.com/google/syzkaller/pkg/cover" "github.com/google/syzkaller/pkg/hash" "github.com/google/syzkaller/pkg/signal" - "github.com/google/syzkaller/pkg/stats" + "github.com/google/syzkaller/pkg/stat" "github.com/google/syzkaller/prog" ) @@ -24,9 +24,9 @@ type Corpus struct { cover cover.Cover // total coverage of all items updates chan<- NewItemEvent *ProgramsList - StatProgs *stats.Val - StatSignal *stats.Val - StatCover *stats.Val + StatProgs *stat.Val + StatSignal *stat.Val + StatCover *stat.Val } func NewCorpus(ctx context.Context) *Corpus { @@ -40,12 +40,12 @@ func NewMonitoredCorpus(ctx context.Context, updates chan<- NewItemEvent) *Corpu updates: updates, ProgramsList: &ProgramsList{}, } - corpus.StatProgs = stats.New("corpus", "Number of test programs in the corpus", stats.Console, - stats.Link("/corpus"), stats.Graph("corpus"), stats.LenOf(&corpus.progs, &corpus.mu)) - corpus.StatSignal = stats.New("signal", "Fuzzing signal in the corpus", - stats.LenOf(&corpus.signal, &corpus.mu)) - corpus.StatCover = stats.New("coverage", "Source coverage in the corpus", stats.Console, - stats.Link("/cover"), stats.Prometheus("syz_corpus_cover"), stats.LenOf(&corpus.cover, &corpus.mu)) + corpus.StatProgs = stat.New("corpus", "Number of test programs in the corpus", stat.Console, + stat.Link("/corpus"), stat.Graph("corpus"), stat.LenOf(&corpus.progs, &corpus.mu)) + corpus.StatSignal = stat.New("signal", "Fuzzing signal in the corpus", + stat.LenOf(&corpus.signal, &corpus.mu)) + corpus.StatCover = stat.New("coverage", "Source coverage in the corpus", stat.Console, + stat.Link("/cover"), stat.Prometheus("syz_corpus_cover"), stat.LenOf(&corpus.cover, &corpus.mu)) return corpus } diff --git a/pkg/flatrpc/conn.go b/pkg/flatrpc/conn.go index 0658522a0..c5e1cb1a4 100644 --- a/pkg/flatrpc/conn.go +++ b/pkg/flatrpc/conn.go @@ -15,14 +15,14 @@ import ( "github.com/google/flatbuffers/go" "github.com/google/syzkaller/pkg/log" - "github.com/google/syzkaller/pkg/stats" + "github.com/google/syzkaller/pkg/stat" ) var ( - statSent = stats.New("rpc sent", "Outbound RPC traffic", - stats.Graph("traffic"), stats.Rate{}, stats.FormatMB) - statRecv = stats.New("rpc recv", "Inbound RPC traffic", - stats.Graph("traffic"), stats.Rate{}, stats.FormatMB) + statSent = stat.New("rpc sent", "Outbound RPC traffic", + stat.Graph("traffic"), stat.Rate{}, stat.FormatMB) + statRecv = stat.New("rpc recv", "Inbound RPC traffic", + stat.Graph("traffic"), stat.Rate{}, stat.FormatMB) ) type Serv struct { diff --git a/pkg/fuzzer/cover.go b/pkg/fuzzer/cover.go index 876d2f4dc..442b4707a 100644 --- a/pkg/fuzzer/cover.go +++ b/pkg/fuzzer/cover.go @@ -7,7 +7,7 @@ import ( "sync" "github.com/google/syzkaller/pkg/signal" - "github.com/google/syzkaller/pkg/stats" + "github.com/google/syzkaller/pkg/stat" ) // Cover keeps track of the signal known to the fuzzer. @@ -19,8 +19,8 @@ type Cover struct { func newCover() *Cover { cover := new(Cover) - stats.New("max signal", "Maximum fuzzing signal (including flakes)", - stats.Graph("signal"), stats.LenOf(&cover.maxSignal, &cover.mu)) + stat.New("max signal", "Maximum fuzzing signal (including flakes)", + stat.Graph("signal"), stat.LenOf(&cover.maxSignal, &cover.mu)) return cover } diff --git a/pkg/fuzzer/fuzzer.go b/pkg/fuzzer/fuzzer.go index 7ac8cba3e..0b7af3c98 100644 --- a/pkg/fuzzer/fuzzer.go +++ b/pkg/fuzzer/fuzzer.go @@ -15,7 +15,7 @@ import ( "github.com/google/syzkaller/pkg/flatrpc" "github.com/google/syzkaller/pkg/fuzzer/queue" "github.com/google/syzkaller/pkg/signal" - "github.com/google/syzkaller/pkg/stats" + "github.com/google/syzkaller/pkg/stat" "github.com/google/syzkaller/prog" ) @@ -240,7 +240,7 @@ func (fuzzer *Fuzzer) genFuzz() *queue.Request { return req } -func (fuzzer *Fuzzer) startJob(stat *stats.Val, newJob job) { +func (fuzzer *Fuzzer) startJob(stat *stat.Val, newJob job) { fuzzer.Logf(2, "started %T", newJob) go func() { stat.Add(1) diff --git a/pkg/fuzzer/queue/queue.go b/pkg/fuzzer/queue/queue.go index 051f7205e..aadbaade8 100644 --- a/pkg/fuzzer/queue/queue.go +++ b/pkg/fuzzer/queue/queue.go @@ -14,7 +14,7 @@ import ( "github.com/google/syzkaller/pkg/flatrpc" "github.com/google/syzkaller/pkg/hash" "github.com/google/syzkaller/pkg/signal" - "github.com/google/syzkaller/pkg/stats" + "github.com/google/syzkaller/pkg/stat" "github.com/google/syzkaller/prog" ) @@ -33,7 +33,7 @@ type Request struct { ReturnOutput bool // This stat will be incremented on request completion. - Stat *stats.Val + Stat *stat.Val // Options needed by runtest. BinaryFile string // If set, it's executed instead of Prog. diff --git a/pkg/fuzzer/stats.go b/pkg/fuzzer/stats.go index 11f98f2a6..073afab29 100644 --- a/pkg/fuzzer/stats.go +++ b/pkg/fuzzer/stats.go @@ -3,63 +3,63 @@ package fuzzer -import "github.com/google/syzkaller/pkg/stats" +import "github.com/google/syzkaller/pkg/stat" type Stats struct { - statCandidates *stats.Val - statNewInputs *stats.Val - statJobs *stats.Val - statJobsTriage *stats.Val - statJobsTriageCandidate *stats.Val - statJobsSmash *stats.Val - statJobsFaultInjection *stats.Val - statJobsHints *stats.Val - statExecTime *stats.Val - statExecGenerate *stats.Val - statExecFuzz *stats.Val - statExecCandidate *stats.Val - statExecTriage *stats.Val - statExecMinimize *stats.Val - statExecSmash *stats.Val - statExecFaultInject *stats.Val - statExecHint *stats.Val - statExecSeed *stats.Val - statExecCollide *stats.Val + statCandidates *stat.Val + statNewInputs *stat.Val + statJobs *stat.Val + statJobsTriage *stat.Val + statJobsTriageCandidate *stat.Val + statJobsSmash *stat.Val + statJobsFaultInjection *stat.Val + statJobsHints *stat.Val + statExecTime *stat.Val + statExecGenerate *stat.Val + statExecFuzz *stat.Val + statExecCandidate *stat.Val + statExecTriage *stat.Val + statExecMinimize *stat.Val + statExecSmash *stat.Val + statExecFaultInject *stat.Val + statExecHint *stat.Val + statExecSeed *stat.Val + statExecCollide *stat.Val } func newStats() Stats { return Stats{ - statCandidates: stats.New("candidates", "Number of candidate programs in triage queue", - stats.Console, stats.Graph("corpus")), - statNewInputs: stats.New("new inputs", "Potential untriaged corpus candidates", - stats.Graph("corpus")), - statJobs: stats.New("fuzzer jobs", "Total running fuzzer jobs", stats.NoGraph), - statJobsTriage: stats.New("triage jobs", "Running triage jobs", stats.StackedGraph("jobs")), - statJobsTriageCandidate: stats.New("candidate triage jobs", "Running candidate triage jobs", - stats.StackedGraph("jobs")), - statJobsSmash: stats.New("smash jobs", "Running smash jobs", stats.StackedGraph("jobs")), - statJobsFaultInjection: stats.New("fault jobs", "Running fault injection jobs", stats.StackedGraph("jobs")), - statJobsHints: stats.New("hints jobs", "Running hints jobs", stats.StackedGraph("jobs")), - statExecTime: stats.New("prog exec time", "Test program execution time (ms)", stats.Distribution{}), - statExecGenerate: stats.New("exec gen", "Executions of generated programs", stats.Rate{}, - stats.StackedGraph("exec")), - statExecFuzz: stats.New("exec fuzz", "Executions of mutated programs", - stats.Rate{}, stats.StackedGraph("exec")), - statExecCandidate: stats.New("exec candidate", "Executions of candidate programs", - stats.Rate{}, stats.StackedGraph("exec")), - statExecTriage: stats.New("exec triage", "Executions of corpus triage programs", - stats.Rate{}, stats.StackedGraph("exec")), - statExecMinimize: stats.New("exec minimize", "Executions of programs during minimization", - stats.Rate{}, stats.StackedGraph("exec")), - statExecSmash: stats.New("exec smash", "Executions of smashed programs", - stats.Rate{}, stats.StackedGraph("exec")), - statExecFaultInject: stats.New("exec inject", "Executions of fault injection", - stats.Rate{}, stats.StackedGraph("exec")), - statExecHint: stats.New("exec hints", "Executions of programs generated using hints", - stats.Rate{}, stats.StackedGraph("exec")), - statExecSeed: stats.New("exec seeds", "Executions of programs for hints extraction", - stats.Rate{}, stats.StackedGraph("exec")), - statExecCollide: stats.New("exec collide", "Executions of programs in collide mode", - stats.Rate{}, stats.StackedGraph("exec")), + statCandidates: stat.New("candidates", "Number of candidate programs in triage queue", + stat.Console, stat.Graph("corpus")), + statNewInputs: stat.New("new inputs", "Potential untriaged corpus candidates", + stat.Graph("corpus")), + statJobs: stat.New("fuzzer jobs", "Total running fuzzer jobs", stat.NoGraph), + statJobsTriage: stat.New("triage jobs", "Running triage jobs", stat.StackedGraph("jobs")), + statJobsTriageCandidate: stat.New("candidate triage jobs", "Running candidate triage jobs", + stat.StackedGraph("jobs")), + statJobsSmash: stat.New("smash jobs", "Running smash jobs", stat.StackedGraph("jobs")), + statJobsFaultInjection: stat.New("fault jobs", "Running fault injection jobs", stat.StackedGraph("jobs")), + statJobsHints: stat.New("hints jobs", "Running hints jobs", stat.StackedGraph("jobs")), + statExecTime: stat.New("prog exec time", "Test program execution time (ms)", stat.Distribution{}), + statExecGenerate: stat.New("exec gen", "Executions of generated programs", stat.Rate{}, + stat.StackedGraph("exec")), + statExecFuzz: stat.New("exec fuzz", "Executions of mutated programs", + stat.Rate{}, stat.StackedGraph("exec")), + statExecCandidate: stat.New("exec candidate", "Executions of candidate programs", + stat.Rate{}, stat.StackedGraph("exec")), + statExecTriage: stat.New("exec triage", "Executions of corpus triage programs", + stat.Rate{}, stat.StackedGraph("exec")), + statExecMinimize: stat.New("exec minimize", "Executions of programs during minimization", + stat.Rate{}, stat.StackedGraph("exec")), + statExecSmash: stat.New("exec smash", "Executions of smashed programs", + stat.Rate{}, stat.StackedGraph("exec")), + statExecFaultInject: stat.New("exec inject", "Executions of fault injection", + stat.Rate{}, stat.StackedGraph("exec")), + statExecHint: stat.New("exec hints", "Executions of programs generated using hints", + stat.Rate{}, stat.StackedGraph("exec")), + statExecSeed: stat.New("exec seeds", "Executions of programs for hints extraction", + stat.Rate{}, stat.StackedGraph("exec")), + statExecCollide: stat.New("exec collide", "Executions of programs in collide mode", + stat.Rate{}, stat.StackedGraph("exec")), } } diff --git a/pkg/rpcserver/rpcserver.go b/pkg/rpcserver/rpcserver.go index 0b7d566bb..b371785d4 100644 --- a/pkg/rpcserver/rpcserver.go +++ b/pkg/rpcserver/rpcserver.go @@ -23,7 +23,7 @@ import ( "github.com/google/syzkaller/pkg/log" "github.com/google/syzkaller/pkg/mgrconfig" "github.com/google/syzkaller/pkg/signal" - "github.com/google/syzkaller/pkg/stats" + "github.com/google/syzkaller/pkg/stat" "github.com/google/syzkaller/pkg/vminfo" "github.com/google/syzkaller/prog" "github.com/google/syzkaller/sys/targets" @@ -58,8 +58,8 @@ type Manager interface { type Server struct { Port int - StatExecs *stats.Val - StatNumFuzzing *stats.Val + StatExecs *stat.Val + StatNumFuzzing *stat.Val cfg *Config mgr Manager @@ -81,7 +81,7 @@ type Server struct { runners map[string]*Runner execSource queue.Source triagedCorpus atomic.Bool - statVMRestarts *stats.Val + statVMRestarts *stat.Val *runnerStats } @@ -144,24 +144,24 @@ func newImpl(ctx context.Context, cfg *Config, mgr Manager) (*Server, error) { baseSource: baseSource, execSource: queue.Retry(baseSource), - StatExecs: stats.New("exec total", "Total test program executions", - stats.Console, stats.Rate{}, stats.Prometheus("syz_exec_total")), - StatNumFuzzing: stats.New("fuzzing VMs", "Number of VMs that are currently fuzzing", - stats.Console, stats.Link("/vms")), - statVMRestarts: stats.New("vm restarts", "Total number of VM starts", - stats.Rate{}, stats.NoGraph), + StatExecs: stat.New("exec total", "Total test program executions", + stat.Console, stat.Rate{}, stat.Prometheus("syz_exec_total")), + StatNumFuzzing: stat.New("fuzzing VMs", "Number of VMs that are currently fuzzing", + stat.Console, stat.Link("/vms")), + statVMRestarts: stat.New("vm restarts", "Total number of VM starts", + stat.Rate{}, stat.NoGraph), runnerStats: &runnerStats{ - statExecRetries: stats.New("exec retries", + statExecRetries: stat.New("exec retries", "Number of times a test program was restarted because the first run failed", - stats.Rate{}, stats.Graph("executor")), - statExecutorRestarts: stats.New("executor restarts", - "Number of times executor process was restarted", stats.Rate{}, stats.Graph("executor")), - statExecBufferTooSmall: stats.New("buffer too small", - "Program serialization overflowed exec buffer", stats.NoGraph), - statNoExecRequests: stats.New("no exec requests", - "Number of times fuzzer was stalled with no exec requests", stats.Rate{}), - statNoExecDuration: stats.New("no exec duration", - "Total duration fuzzer was stalled with no exec requests (ns/sec)", stats.Rate{}), + stat.Rate{}, stat.Graph("executor")), + statExecutorRestarts: stat.New("executor restarts", + "Number of times executor process was restarted", stat.Rate{}, stat.Graph("executor")), + statExecBufferTooSmall: stat.New("buffer too small", + "Program serialization overflowed exec buffer", stat.NoGraph), + statNoExecRequests: stat.New("no exec requests", + "Number of times fuzzer was stalled with no exec requests", stat.Rate{}), + statNoExecDuration: stat.New("no exec duration", + "Total duration fuzzer was stalled with no exec requests (ns/sec)", stat.Rate{}), }, } serv.runnerStats.statExecs = serv.StatExecs diff --git a/pkg/rpcserver/runner.go b/pkg/rpcserver/runner.go index 21b270421..a0b519d20 100644 --- a/pkg/rpcserver/runner.go +++ b/pkg/rpcserver/runner.go @@ -18,7 +18,7 @@ import ( "github.com/google/syzkaller/pkg/fuzzer/queue" "github.com/google/syzkaller/pkg/log" "github.com/google/syzkaller/pkg/osutil" - "github.com/google/syzkaller/pkg/stats" + "github.com/google/syzkaller/pkg/stat" "github.com/google/syzkaller/prog" "github.com/google/syzkaller/sys/targets" "github.com/google/syzkaller/vm/dispatcher" @@ -54,12 +54,12 @@ type Runner struct { } type runnerStats struct { - statExecs *stats.Val - statExecRetries *stats.Val - statExecutorRestarts *stats.Val - statExecBufferTooSmall *stats.Val - statNoExecRequests *stats.Val - statNoExecDuration *stats.Val + statExecs *stat.Val + statExecRetries *stat.Val + statExecutorRestarts *stat.Val + statExecBufferTooSmall *stat.Val + statNoExecRequests *stat.Val + statNoExecDuration *stat.Val } type handshakeConfig struct { diff --git a/pkg/stat/avg.go b/pkg/stat/avg.go new file mode 100644 index 000000000..fcfc9f5d5 --- /dev/null +++ b/pkg/stat/avg.go @@ -0,0 +1,32 @@ +// Copyright 2024 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +package stat + +import ( + "sync" + "time" +) + +type AverageParameter interface { + time.Duration +} + +type AverageValue[T AverageParameter] struct { + mu sync.Mutex + total int64 + avg T +} + +func (av *AverageValue[T]) Value() T { + av.mu.Lock() + defer av.mu.Unlock() + return av.avg +} + +func (av *AverageValue[T]) Save(val T) { + av.mu.Lock() + defer av.mu.Unlock() + av.total++ + av.avg += (val - av.avg) / T(av.total) +} diff --git a/pkg/stat/sample/pvalue.go b/pkg/stat/sample/pvalue.go new file mode 100644 index 000000000..acfff4bc4 --- /dev/null +++ b/pkg/stat/sample/pvalue.go @@ -0,0 +1,20 @@ +// Copyright 2021 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +package sample + +// TODO: I didn't find the substitution as of Feb 2023. Let's keep it as is while it works. +import "golang.org/x/perf/benchstat" // nolint:all + +// Mann-Whitney U test. +func UTest(old, new *Sample) (pval float64, err error) { + // Unfortunately we cannot just invoke MannWhitneyUTest from x/perf/benchstat/internal/stats, + // so we first wrap the data in Metrics. + mOld := benchstat.Metrics{ + RValues: old.Xs, + } + mNew := benchstat.Metrics{ + RValues: new.Xs, + } + return benchstat.UTest(&mOld, &mNew) +} diff --git a/pkg/stat/sample/sample.go b/pkg/stat/sample/sample.go new file mode 100644 index 000000000..740f9aefe --- /dev/null +++ b/pkg/stat/sample/sample.go @@ -0,0 +1,73 @@ +// Copyright 2021 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +// Package sample provides various statistical operations and algorithms. +package sample + +import ( + "math" + "sort" +) + +// Sample represents a single sample - set of data points collected during an experiment. +type Sample struct { + Xs []float64 + Sorted bool +} + +func (s *Sample) Percentile(p float64) float64 { + s.Sort() + // The code below is taken from golang.org/x/perf/internal/stats + // Unfortunately, that package is internal and we cannot just import and use it. + N := float64(len(s.Xs)) + n := 1/3.0 + p*(N+1/3.0) // R8 + kf, frac := math.Modf(n) + k := int(kf) + if k <= 0 { + return s.Xs[0] + } else if k >= len(s.Xs) { + return s.Xs[len(s.Xs)-1] + } + return s.Xs[k-1] + frac*(s.Xs[k]-s.Xs[k-1]) +} + +func (s *Sample) Median() float64 { + return s.Percentile(0.5) +} + +// Remove outliers by the Tukey's fences method. +func (s *Sample) RemoveOutliers() *Sample { + if len(s.Xs) < 4 { + // If the data set is too small, we cannot reliably detect outliers anyway. + return s.Copy() + } + s.Sort() + Q1 := s.Percentile(0.25) + Q3 := s.Percentile(0.75) + minValue := Q1 - 1.5*(Q3-Q1) + maxValue := Q3 + 1.5*(Q3-Q1) + xs := []float64{} + for _, value := range s.Xs { + if value >= minValue && value <= maxValue { + xs = append(xs, value) + } + } + return &Sample{ + Xs: xs, + Sorted: s.Sorted, + } +} + +func (s *Sample) Copy() *Sample { + return &Sample{ + Xs: append([]float64{}, s.Xs...), + Sorted: s.Sorted, + } +} + +func (s *Sample) Sort() { + if !s.Sorted { + sort.Slice(s.Xs, func(i, j int) bool { return s.Xs[i] < s.Xs[j] }) + s.Sorted = true + } +} diff --git a/pkg/stat/sample/sample_test.go b/pkg/stat/sample/sample_test.go new file mode 100644 index 000000000..ac7845ccf --- /dev/null +++ b/pkg/stat/sample/sample_test.go @@ -0,0 +1,66 @@ +// Copyright 2021 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +package sample + +import ( + "reflect" + "testing" +) + +func TestMedian(t *testing.T) { + tests := []struct { + input []float64 + minMedian float64 + maxMedian float64 + }{ + { + input: []float64{1, 2, 3}, + minMedian: 1.99, // we cannot do exact floating point equality comparison + maxMedian: 2.01, + }, + { + input: []float64{0, 1, 2, 3}, + minMedian: 1.0, + maxMedian: 2.0, + }, + } + for _, test := range tests { + sample := Sample{Xs: test.input} + median := sample.Median() + if median < test.minMedian || median > test.maxMedian { + t.Errorf("sample %v, median got %v, median expected [%v;%v]", + test.input, median, test.minMedian, test.maxMedian) + } + } +} + +func TestRemoveOutliers(t *testing.T) { + // Some tests just to check the overall sanity of the method. + tests := []struct { + input []float64 + output []float64 + }{ + { + input: []float64{-20, 1, 2, 3, 4, 5}, + output: []float64{1, 2, 3, 4, 5}, + }, + { + input: []float64{1, 2, 3, 4, 25}, + output: []float64{1, 2, 3, 4}, + }, + { + input: []float64{-10, -5, 0, 5, 10, 15}, + output: []float64{-10, -5, 0, 5, 10, 15}, + }, + } + for _, test := range tests { + sample := Sample{Xs: test.input} + result := sample.RemoveOutliers() + result.Sort() + if !reflect.DeepEqual(result.Xs, test.output) { + t.Errorf("input: %v, expected no outliers: %v, got: %v", + test.input, test.output, result.Xs) + } + } +} diff --git a/pkg/stat/set.go b/pkg/stat/set.go new file mode 100644 index 000000000..690d0406a --- /dev/null +++ b/pkg/stat/set.go @@ -0,0 +1,488 @@ +// Copyright 2024 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +package stat + +import ( + "bytes" + "fmt" + "reflect" + "sort" + "strconv" + "sync" + "sync/atomic" + "time" + + "github.com/VividCortex/gohistogram" + "github.com/google/syzkaller/pkg/html/pages" + "github.com/prometheus/client_golang/prometheus" +) + +// This file provides prometheus/streamz style metrics (Val type) for instrumenting code for monitoring. +// It also provides a registry for such metrics (set type) and a global default registry. +// +// Simple uses of metrics: +// +// statFoo := stat.New("metric name", "metric description") +// statFoo.Add(1) +// +// stat.New("metric name", "metric description", LenOf(mySlice, rwMutex)) +// +// Metric visualization code uses Collect/RenderHTML functions to obtain values of all registered metrics. + +type UI struct { + Name string + Desc string + Link string + Level Level + Value string + V int +} + +func New(name, desc string, opts ...any) *Val { + return global.New(name, desc, opts...) +} + +func Collect(level Level) []UI { + return global.Collect(level) +} + +func RenderHTML() ([]byte, error) { + return global.RenderHTML() +} + +var global = newSet(256, true) + +type set struct { + mu sync.Mutex + vals map[string]*Val + graphs map[string]*graph + totalTicks int + historySize int + historyTicks int + historyPos int + historyScale int +} + +type graph struct { + level Level + stacked bool + lines map[string]*line +} + +type line struct { + desc string + rate bool + data []float64 + hist []*gohistogram.NumericHistogram +} + +const ( + tickPeriod = time.Second + histogramBuckets = 255 +) + +func newSet(histSize int, tick bool) *set { + s := &set{ + vals: make(map[string]*Val), + historySize: histSize, + historyScale: 1, + graphs: make(map[string]*graph), + } + if tick { + go func() { + for range time.NewTicker(tickPeriod).C { + s.tick() + } + }() + } + return s +} + +func (s *set) Collect(level Level) []UI { + s.mu.Lock() + defer s.mu.Unlock() + period := time.Duration(s.totalTicks) * tickPeriod + if period == 0 { + period = tickPeriod + } + var res []UI + for _, v := range s.vals { + if v.level < level { + continue + } + val := v.Val() + res = append(res, UI{ + Name: v.name, + Desc: v.desc, + Link: v.link, + Level: v.level, + Value: v.fmt(val, period), + V: val, + }) + } + sort.Slice(res, func(i, j int) bool { + if res[i].Level != res[j].Level { + return res[i].Level > res[j].Level + } + return res[i].Name < res[j].Name + }) + return res +} + +// Additional options for Val metrics. + +// Level controls if the metric should be printed to console in periodic heartbeat logs, +// or showed on the simple web interface, or showed in the expert interface only. +type Level int + +const ( + All Level = iota + Simple + Console +) + +// Link adds a hyperlink to metric name. +type Link string + +// Prometheus exports the metric to Prometheus under the given name. +type Prometheus string + +// Rate says to collect/visualize metric rate per unit of time rather then total value. +type Rate struct{} + +// Distribution says to collect/visualize histogram of individual sample distributions. +type Distribution struct{} + +// Graph allows to combine multiple related metrics on a single graph. +type Graph string + +// StackedGraph is like Graph, but shows metrics on a stacked graph. +type StackedGraph string + +// NoGraph says to not visualize the metric as a graph. +const NoGraph Graph = "" + +// LenOf reads the metric value from the given slice/map/chan. +func LenOf(containerPtr any, mu *sync.RWMutex) func() int { + v := reflect.ValueOf(containerPtr) + _ = v.Elem().Len() // panics if container is not slice/map/chan + return func() int { + mu.RLock() + defer mu.RUnlock() + return v.Elem().Len() + } +} + +func FormatMB(v int, period time.Duration) string { + const KB, MB = 1 << 10, 1 << 20 + return fmt.Sprintf("%v MB (%v kb/sec)", (v+MB/2)/MB, (v+KB/2)/KB/int(period/time.Second)) +} + +// Addittionally a custom 'func() int' can be passed to read the metric value from the function. +// and 'func(int, time.Duration) string' can be passed for custom formatting of the metric value. + +func (s *set) New(name, desc string, opts ...any) *Val { + v := &Val{ + name: name, + desc: desc, + graph: name, + fmt: func(v int, period time.Duration) string { return strconv.Itoa(v) }, + } + stacked := false + for _, o := range opts { + switch opt := o.(type) { + case Level: + v.level = opt + case Link: + v.link = string(opt) + case Graph: + v.graph = string(opt) + case StackedGraph: + v.graph = string(opt) + stacked = true + case Rate: + v.rate = true + v.fmt = formatRate + case Distribution: + v.hist = true + case func() int: + v.ext = opt + case func(int, time.Duration) string: + v.fmt = opt + case Prometheus: + // Prometheus Instrumentation https://prometheus.io/docs/guides/go-application. + prometheus.Register(prometheus.NewGaugeFunc(prometheus.GaugeOpts{ + Name: string(opt), + Help: desc, + }, + func() float64 { return float64(v.Val()) }, + )) + default: + panic(fmt.Sprintf("unknown stats option %#v", o)) + } + } + s.mu.Lock() + defer s.mu.Unlock() + s.vals[name] = v + if v.graph != "" { + if s.graphs[v.graph] == nil { + s.graphs[v.graph] = &graph{ + lines: make(map[string]*line), + } + } + if s.graphs[v.graph].level < v.level { + s.graphs[v.graph].level = v.level + } + s.graphs[v.graph].stacked = stacked + } + return v +} + +type Val struct { + name string + desc string + link string + graph string + level Level + val atomic.Uint64 + ext func() int + fmt func(int, time.Duration) string + rate bool + hist bool + prev int + histMu sync.Mutex + histVal *gohistogram.NumericHistogram +} + +func (v *Val) Add(val int) { + if v.ext != nil { + panic(fmt.Sprintf("stat %v is in external mode", v.name)) + } + if v.hist { + v.histMu.Lock() + if v.histVal == nil { + v.histVal = gohistogram.NewHistogram(histogramBuckets) + } + v.histVal.Add(float64(val)) + v.histMu.Unlock() + return + } + v.val.Add(uint64(val)) +} + +func (v *Val) Val() int { + if v.ext != nil { + return v.ext() + } + if v.hist { + v.histMu.Lock() + defer v.histMu.Unlock() + if v.histVal == nil { + return 0 + } + return int(v.histVal.Mean()) + } + return int(v.val.Load()) +} + +func formatRate(v int, period time.Duration) string { + secs := int(period.Seconds()) + if x := v / secs; x >= 10 { + return fmt.Sprintf("%v (%v/sec)", v, x) + } + if x := v * 60 / secs; x >= 10 { + return fmt.Sprintf("%v (%v/min)", v, x) + } + x := v * 60 * 60 / secs + return fmt.Sprintf("%v (%v/hour)", v, x) +} + +func (s *set) tick() { + s.mu.Lock() + defer s.mu.Unlock() + + if s.historyPos == s.historySize { + s.compress() + } + + s.totalTicks++ + s.historyTicks++ + for _, v := range s.vals { + if v.graph == "" { + continue + } + graph := s.graphs[v.graph] + ln := graph.lines[v.name] + if ln == nil { + ln = &line{ + desc: v.desc, + rate: v.rate, + } + if v.hist { + ln.hist = make([]*gohistogram.NumericHistogram, s.historySize) + } else { + ln.data = make([]float64, s.historySize) + } + graph.lines[v.name] = ln + } + if v.hist { + if s.historyTicks == s.historyScale { + v.histMu.Lock() + ln.hist[s.historyPos] = v.histVal + v.histVal = nil + v.histMu.Unlock() + } + } else { + val := v.Val() + pv := &ln.data[s.historyPos] + if v.rate { + *pv += float64(val-v.prev) / float64(s.historyScale) + v.prev = val + } else { + if *pv < float64(val) { + *pv = float64(val) + } + } + } + } + if s.historyTicks != s.historyScale { + return + } + s.historyTicks = 0 + s.historyPos++ +} + +func (s *set) compress() { + half := s.historySize / 2 + s.historyPos = half + s.historyScale *= 2 + for _, graph := range s.graphs { + for _, line := range graph.lines { + for i := 0; i < half; i++ { + if line.hist != nil { + h1, h2 := line.hist[2*i], line.hist[2*i+1] + line.hist[2*i], line.hist[2*i+1] = nil, nil + line.hist[i] = h1 + if h1 == nil { + line.hist[i] = h2 + } + } else { + v1, v2 := line.data[2*i], line.data[2*i+1] + line.data[2*i], line.data[2*i+1] = 0, 0 + if line.rate { + line.data[i] = (v1 + v2) / 2 + } else { + line.data[i] = v1 + if v2 > v1 { + line.data[i] = v2 + } + } + } + } + } + } +} + +func (s *set) RenderHTML() ([]byte, error) { + s.mu.Lock() + defer s.mu.Unlock() + type Point struct { + X int + Y []float64 + } + type Graph struct { + ID int + Title string + Stacked bool + Level Level + Lines []string + Points []Point + } + var graphs []Graph + tick := s.historyScale * int(tickPeriod.Seconds()) + for title, graph := range s.graphs { + if len(graph.lines) == 0 { + continue + } + g := Graph{ + ID: len(graphs), + Title: title, + Stacked: graph.stacked, + Level: graph.level, + Points: make([]Point, s.historyPos), + } + for i := 0; i < s.historyPos; i++ { + g.Points[i].X = i * tick + } + for name, ln := range graph.lines { + if ln.hist == nil { + g.Lines = append(g.Lines, name+": "+ln.desc) + for i := 0; i < s.historyPos; i++ { + g.Points[i].Y = append(g.Points[i].Y, ln.data[i]) + } + } else { + for _, percent := range []int{10, 50, 90} { + g.Lines = append(g.Lines, fmt.Sprintf("%v%%", percent)) + for i := 0; i < s.historyPos; i++ { + v := 0.0 + if ln.hist[i] != nil { + v = ln.hist[i].Quantile(float64(percent) / 100) + } + g.Points[i].Y = append(g.Points[i].Y, v) + } + } + } + } + graphs = append(graphs, g) + } + sort.Slice(graphs, func(i, j int) bool { + if graphs[i].Level != graphs[j].Level { + return graphs[i].Level > graphs[j].Level + } + return graphs[i].Title < graphs[j].Title + }) + buf := new(bytes.Buffer) + err := htmlTemplate.Execute(buf, graphs) + return buf.Bytes(), err +} + +var htmlTemplate = pages.Create(` + + + + syzkaller stats + + {{HEAD}} + + +{{range $g := .}} +
+ +{{end}} + + +`) diff --git a/pkg/stat/set_test.go b/pkg/stat/set_test.go new file mode 100644 index 000000000..4313db1ef --- /dev/null +++ b/pkg/stat/set_test.go @@ -0,0 +1,219 @@ +// Copyright 2024 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +package stat + +import ( + "fmt" + "math/rand" + "sync/atomic" + "testing" + "time" + + "github.com/stretchr/testify/assert" +) + +func TestSet(t *testing.T) { + a := assert.New(t) + set := newSet(4, false) + a.Empty(set.Collect(All)) + _, err := set.RenderHTML() + a.NoError(err) + + v0 := set.New("v0", "desc0") + a.Equal(v0.Val(), 0) + v0.Add(1) + a.Equal(v0.Val(), 1) + v0.Add(1) + a.Equal(v0.Val(), 2) + + vv1 := 0 + v1 := set.New("v1", "desc1", Simple, func() int { return vv1 }) + a.Equal(v1.Val(), 0) + vv1 = 11 + a.Equal(v1.Val(), 11) + a.Panics(func() { v1.Add(1) }) + + v2 := set.New("v2", "desc2", Console, func(v int, period time.Duration) string { + return fmt.Sprintf("v2 %v %v", v, period) + }) + v2.Add(100) + + v3 := set.New("v3", "desc3", Link("/v3"), NoGraph, Distribution{}) + a.Equal(v3.Val(), 0) + v3.Add(10) + a.Equal(v3.Val(), 10) + v3.Add(20) + a.Equal(v3.Val(), 15) + v3.Add(20) + a.Equal(v3.Val(), 16) + v3.Add(30) + a.Equal(v3.Val(), 20) + v3.Add(30) + a.Equal(v3.Val(), 22) + v3.Add(30) + v3.Add(30) + a.Equal(v3.Val(), 24) + + v4 := set.New("v4", "desc4", Rate{}, Graph("graph")) + v4.Add(10) + a.Equal(v4.Val(), 10) + v4.Add(10) + a.Equal(v4.Val(), 20) + + a.Panics(func() { set.New("v0", "desc0", float64(1)) }) + + ui := set.Collect(All) + a.Equal(len(ui), 5) + a.Equal(ui[0], UI{"v2", "desc2", "", Console, "v2 100 1s", 100}) + a.Equal(ui[1], UI{"v1", "desc1", "", Simple, "11", 11}) + a.Equal(ui[2], UI{"v0", "desc0", "", All, "2", 2}) + a.Equal(ui[3], UI{"v3", "desc3", "/v3", All, "24", 24}) + a.Equal(ui[4], UI{"v4", "desc4", "", All, "20 (20/sec)", 20}) + + ui1 := set.Collect(Simple) + a.Equal(len(ui1), 2) + a.Equal(ui1[0].Name, "v2") + a.Equal(ui1[1].Name, "v1") + + ui2 := set.Collect(Console) + a.Equal(len(ui2), 1) + a.Equal(ui2[0].Name, "v2") + + _, err = set.RenderHTML() + a.NoError(err) +} + +func TestSetRateFormat(t *testing.T) { + a := assert.New(t) + set := newSet(4, false) + v := set.New("v", "desc", Rate{}) + a.Equal(set.Collect(All)[0].Value, "0 (0/hour)") + v.Add(1) + a.Equal(set.Collect(All)[0].Value, "1 (60/min)") + v.Add(99) + a.Equal(set.Collect(All)[0].Value, "100 (100/sec)") +} + +func TestSetHistoryCounter(t *testing.T) { + a := assert.New(t) + set := newSet(4, false) + v := set.New("v0", "desc0") + set.tick() + hist := func() []float64 { return set.graphs["v0"].lines["v0"].data[:set.historyPos] } + step := func(n int) []float64 { + v.Add(n) + set.tick() + return hist() + } + a.Equal(hist(), []float64{0}) + v.Add(1) + v.Add(1) + a.Equal(hist(), []float64{0}) + set.tick() + a.Equal(hist(), []float64{0, 2}) + v.Add(3) + a.Equal(hist(), []float64{0, 2}) + set.tick() + a.Equal(hist(), []float64{0, 2, 5}) + a.Equal(step(-1), []float64{0, 2, 5, 4}) + // Compacted, each new history value will require 2 steps. + a.Equal(step(7), []float64{2, 5}) + a.Equal(step(-10), []float64{2, 5, 11}) + a.Equal(step(2), []float64{2, 5, 11}) + a.Equal(step(1), []float64{2, 5, 11, 4}) + // 4 steps for each new value. + a.Equal(step(1), []float64{5, 11}) + a.Equal(step(1), []float64{5, 11}) + a.Equal(step(1), []float64{5, 11}) + a.Equal(step(1), []float64{5, 11, 8}) +} + +func TestSetHistoryRate(t *testing.T) { + a := assert.New(t) + set := newSet(4, false) + v := set.New("v0", "desc0", Rate{}) + step := func(n int) []float64 { + v.Add(n) + set.tick() + return set.graphs["v0"].lines["v0"].data[:set.historyPos] + } + a.Equal(step(3), []float64{3}) + a.Equal(step(1), []float64{3, 1}) + a.Equal(step(2), []float64{3, 1, 2}) + a.Equal(step(5), []float64{3, 1, 2, 5}) + a.Equal(step(1), []float64{2, 3.5}) + a.Equal(step(2), []float64{2, 3.5, 1.5}) + a.Equal(step(2), []float64{2, 3.5, 1.5}) + a.Equal(step(4), []float64{2, 3.5, 1.5, 3}) + a.Equal(step(1), []float64{2.75, 2.25}) + a.Equal(step(2), []float64{2.75, 2.25}) + a.Equal(step(3), []float64{2.75, 2.25}) + a.Equal(step(4), []float64{2.75, 2.25, 2.5}) +} + +func TestSetHistoryDistribution(t *testing.T) { + a := assert.New(t) + set := newSet(4, false) + v := set.New("v0", "desc0", Distribution{}) + step := func(n int) [3][]float64 { + v.Add(n) + set.tick() + var history [3][]float64 + for p, percent := range []int{10, 50, 90} { + history[p] = make([]float64, set.historyPos) + for i := 0; i < set.historyPos; i++ { + hist := set.graphs["v0"].lines["v0"].hist[i] + if hist != nil { + history[p][i] = hist.Quantile(float64(percent) / 100) + } + } + } + return history + } + a.Equal(step(3), [3][]float64{{3}, {3}, {3}}) + a.Equal(step(6), [3][]float64{{3, 6}, {3, 6}, {3, 6}}) + a.Equal(step(1), [3][]float64{{3, 6, 1}, {3, 6, 1}, {3, 6, 1}}) + a.Equal(step(2), [3][]float64{{3, 6, 1, 2}, {3, 6, 1, 2}, {3, 6, 1, 2}}) + a.Equal(step(1), [3][]float64{{3, 1}, {3, 1}, {3, 1}}) + a.Equal(step(10), [3][]float64{{3, 1, 1}, {3, 1, 1}, {3, 1, 10}}) +} + +func TestSetStress(t *testing.T) { + set := newSet(4, false) + var stop atomic.Bool + var seq atomic.Uint64 + start := func(f func()) { + go func() { + for !stop.Load() { + f() + } + }() + } + for p := 0; p < 2; p++ { + for _, opt := range []any{Link(""), NoGraph, Rate{}, Distribution{}} { + opt := opt + go func() { + v := set.New(fmt.Sprintf("v%v", seq.Add(1)), "desc", opt) + for p1 := 0; p1 < 2; p1++ { + start(func() { v.Val() }) + start(func() { v.Add(rand.Intn(10000)) }) + } + }() + } + go func() { + var vv atomic.Uint64 + v := set.New(fmt.Sprintf("v%v", seq.Add(1)), "desc", + func() int { return int(vv.Load()) }) + for p1 := 0; p1 < 2; p1++ { + start(func() { v.Val() }) + start(func() { vv.Store(uint64(rand.Intn(10000))) }) + } + }() + start(func() { set.Collect(All) }) + start(func() { set.RenderHTML() }) + start(func() { set.tick() }) + } + time.Sleep(time.Second) + stop.Store(true) +} diff --git a/pkg/stat/syzbotstats/bug.go b/pkg/stat/syzbotstats/bug.go new file mode 100644 index 000000000..c11274583 --- /dev/null +++ b/pkg/stat/syzbotstats/bug.go @@ -0,0 +1,32 @@ +// Copyright 2023 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +package syzbotstats + +import "time" + +type BugStatSummary struct { + Title string + IDs []string // IDs used by syzbot for this bug. + FirstTime time.Time // When the bug was first hit. + ReleasedTime time.Time // When the bug was published. + ReproTime time.Time // When we found the reproducer. + CauseBisectTime time.Time // When we found cause bisection. + ResolvedTime time.Time // When the bug was resolved. + Status BugStatus + Subsystems []string + Strace bool // Whether we managed to reproduce under strace. + HitsPerDay float64 // Average number of bug hits per day. + FixHashes []string // Hashes of fix commits. + HappenedOn []string // Managers on which the crash happened. +} + +type BugStatus string + +const ( + BugFixed BugStatus = "fixed" + BugInvalidated BugStatus = "invalidated" + BugAutoInvalidated BugStatus = "auto-invalidated" + BugDup BugStatus = "dup" + BugPending BugStatus = "pending" +) diff --git a/pkg/stats/avg.go b/pkg/stats/avg.go deleted file mode 100644 index 430ff335b..000000000 --- a/pkg/stats/avg.go +++ /dev/null @@ -1,32 +0,0 @@ -// Copyright 2024 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package stats - -import ( - "sync" - "time" -) - -type AverageParameter interface { - time.Duration -} - -type AverageValue[T AverageParameter] struct { - mu sync.Mutex - total int64 - avg T -} - -func (av *AverageValue[T]) Value() T { - av.mu.Lock() - defer av.mu.Unlock() - return av.avg -} - -func (av *AverageValue[T]) Save(val T) { - av.mu.Lock() - defer av.mu.Unlock() - av.total++ - av.avg += (val - av.avg) / T(av.total) -} diff --git a/pkg/stats/sample/pvalue.go b/pkg/stats/sample/pvalue.go deleted file mode 100644 index acfff4bc4..000000000 --- a/pkg/stats/sample/pvalue.go +++ /dev/null @@ -1,20 +0,0 @@ -// Copyright 2021 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package sample - -// TODO: I didn't find the substitution as of Feb 2023. Let's keep it as is while it works. -import "golang.org/x/perf/benchstat" // nolint:all - -// Mann-Whitney U test. -func UTest(old, new *Sample) (pval float64, err error) { - // Unfortunately we cannot just invoke MannWhitneyUTest from x/perf/benchstat/internal/stats, - // so we first wrap the data in Metrics. - mOld := benchstat.Metrics{ - RValues: old.Xs, - } - mNew := benchstat.Metrics{ - RValues: new.Xs, - } - return benchstat.UTest(&mOld, &mNew) -} diff --git a/pkg/stats/sample/sample.go b/pkg/stats/sample/sample.go deleted file mode 100644 index 740f9aefe..000000000 --- a/pkg/stats/sample/sample.go +++ /dev/null @@ -1,73 +0,0 @@ -// Copyright 2021 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -// Package sample provides various statistical operations and algorithms. -package sample - -import ( - "math" - "sort" -) - -// Sample represents a single sample - set of data points collected during an experiment. -type Sample struct { - Xs []float64 - Sorted bool -} - -func (s *Sample) Percentile(p float64) float64 { - s.Sort() - // The code below is taken from golang.org/x/perf/internal/stats - // Unfortunately, that package is internal and we cannot just import and use it. - N := float64(len(s.Xs)) - n := 1/3.0 + p*(N+1/3.0) // R8 - kf, frac := math.Modf(n) - k := int(kf) - if k <= 0 { - return s.Xs[0] - } else if k >= len(s.Xs) { - return s.Xs[len(s.Xs)-1] - } - return s.Xs[k-1] + frac*(s.Xs[k]-s.Xs[k-1]) -} - -func (s *Sample) Median() float64 { - return s.Percentile(0.5) -} - -// Remove outliers by the Tukey's fences method. -func (s *Sample) RemoveOutliers() *Sample { - if len(s.Xs) < 4 { - // If the data set is too small, we cannot reliably detect outliers anyway. - return s.Copy() - } - s.Sort() - Q1 := s.Percentile(0.25) - Q3 := s.Percentile(0.75) - minValue := Q1 - 1.5*(Q3-Q1) - maxValue := Q3 + 1.5*(Q3-Q1) - xs := []float64{} - for _, value := range s.Xs { - if value >= minValue && value <= maxValue { - xs = append(xs, value) - } - } - return &Sample{ - Xs: xs, - Sorted: s.Sorted, - } -} - -func (s *Sample) Copy() *Sample { - return &Sample{ - Xs: append([]float64{}, s.Xs...), - Sorted: s.Sorted, - } -} - -func (s *Sample) Sort() { - if !s.Sorted { - sort.Slice(s.Xs, func(i, j int) bool { return s.Xs[i] < s.Xs[j] }) - s.Sorted = true - } -} diff --git a/pkg/stats/sample/sample_test.go b/pkg/stats/sample/sample_test.go deleted file mode 100644 index ac7845ccf..000000000 --- a/pkg/stats/sample/sample_test.go +++ /dev/null @@ -1,66 +0,0 @@ -// Copyright 2021 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package sample - -import ( - "reflect" - "testing" -) - -func TestMedian(t *testing.T) { - tests := []struct { - input []float64 - minMedian float64 - maxMedian float64 - }{ - { - input: []float64{1, 2, 3}, - minMedian: 1.99, // we cannot do exact floating point equality comparison - maxMedian: 2.01, - }, - { - input: []float64{0, 1, 2, 3}, - minMedian: 1.0, - maxMedian: 2.0, - }, - } - for _, test := range tests { - sample := Sample{Xs: test.input} - median := sample.Median() - if median < test.minMedian || median > test.maxMedian { - t.Errorf("sample %v, median got %v, median expected [%v;%v]", - test.input, median, test.minMedian, test.maxMedian) - } - } -} - -func TestRemoveOutliers(t *testing.T) { - // Some tests just to check the overall sanity of the method. - tests := []struct { - input []float64 - output []float64 - }{ - { - input: []float64{-20, 1, 2, 3, 4, 5}, - output: []float64{1, 2, 3, 4, 5}, - }, - { - input: []float64{1, 2, 3, 4, 25}, - output: []float64{1, 2, 3, 4}, - }, - { - input: []float64{-10, -5, 0, 5, 10, 15}, - output: []float64{-10, -5, 0, 5, 10, 15}, - }, - } - for _, test := range tests { - sample := Sample{Xs: test.input} - result := sample.RemoveOutliers() - result.Sort() - if !reflect.DeepEqual(result.Xs, test.output) { - t.Errorf("input: %v, expected no outliers: %v, got: %v", - test.input, test.output, result.Xs) - } - } -} diff --git a/pkg/stats/set.go b/pkg/stats/set.go deleted file mode 100644 index 7e4804280..000000000 --- a/pkg/stats/set.go +++ /dev/null @@ -1,488 +0,0 @@ -// Copyright 2024 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package stats - -import ( - "bytes" - "fmt" - "reflect" - "sort" - "strconv" - "sync" - "sync/atomic" - "time" - - "github.com/VividCortex/gohistogram" - "github.com/google/syzkaller/pkg/html/pages" - "github.com/prometheus/client_golang/prometheus" -) - -// This file provides prometheus/streamz style metrics (Val type) for instrumenting code for monitoring. -// It also provides a registry for such metrics (set type) and a global default registry. -// -// Simple uses of metrics: -// -// statFoo := stats.New("metric name", "metric description") -// statFoo.Add(1) -// -// stats.New("metric name", "metric description", LenOf(mySlice, rwMutex)) -// -// Metric visualization code uses Collect/RenderHTML functions to obtain values of all registered metrics. - -type UI struct { - Name string - Desc string - Link string - Level Level - Value string - V int -} - -func New(name, desc string, opts ...any) *Val { - return global.New(name, desc, opts...) -} - -func Collect(level Level) []UI { - return global.Collect(level) -} - -func RenderHTML() ([]byte, error) { - return global.RenderHTML() -} - -var global = newSet(256, true) - -type set struct { - mu sync.Mutex - vals map[string]*Val - graphs map[string]*graph - totalTicks int - historySize int - historyTicks int - historyPos int - historyScale int -} - -type graph struct { - level Level - stacked bool - lines map[string]*line -} - -type line struct { - desc string - rate bool - data []float64 - hist []*gohistogram.NumericHistogram -} - -const ( - tickPeriod = time.Second - histogramBuckets = 255 -) - -func newSet(histSize int, tick bool) *set { - s := &set{ - vals: make(map[string]*Val), - historySize: histSize, - historyScale: 1, - graphs: make(map[string]*graph), - } - if tick { - go func() { - for range time.NewTicker(tickPeriod).C { - s.tick() - } - }() - } - return s -} - -func (s *set) Collect(level Level) []UI { - s.mu.Lock() - defer s.mu.Unlock() - period := time.Duration(s.totalTicks) * tickPeriod - if period == 0 { - period = tickPeriod - } - var res []UI - for _, v := range s.vals { - if v.level < level { - continue - } - val := v.Val() - res = append(res, UI{ - Name: v.name, - Desc: v.desc, - Link: v.link, - Level: v.level, - Value: v.fmt(val, period), - V: val, - }) - } - sort.Slice(res, func(i, j int) bool { - if res[i].Level != res[j].Level { - return res[i].Level > res[j].Level - } - return res[i].Name < res[j].Name - }) - return res -} - -// Additional options for Val metrics. - -// Level controls if the metric should be printed to console in periodic heartbeat logs, -// or showed on the simple web interface, or showed in the expert interface only. -type Level int - -const ( - All Level = iota - Simple - Console -) - -// Link adds a hyperlink to metric name. -type Link string - -// Prometheus exports the metric to Prometheus under the given name. -type Prometheus string - -// Rate says to collect/visualize metric rate per unit of time rather then total value. -type Rate struct{} - -// Distribution says to collect/visualize histogram of individual sample distributions. -type Distribution struct{} - -// Graph allows to combine multiple related metrics on a single graph. -type Graph string - -// StackedGraph is like Graph, but shows metrics on a stacked graph. -type StackedGraph string - -// NoGraph says to not visualize the metric as a graph. -const NoGraph Graph = "" - -// LenOf reads the metric value from the given slice/map/chan. -func LenOf(containerPtr any, mu *sync.RWMutex) func() int { - v := reflect.ValueOf(containerPtr) - _ = v.Elem().Len() // panics if container is not slice/map/chan - return func() int { - mu.RLock() - defer mu.RUnlock() - return v.Elem().Len() - } -} - -func FormatMB(v int, period time.Duration) string { - const KB, MB = 1 << 10, 1 << 20 - return fmt.Sprintf("%v MB (%v kb/sec)", (v+MB/2)/MB, (v+KB/2)/KB/int(period/time.Second)) -} - -// Addittionally a custom 'func() int' can be passed to read the metric value from the function. -// and 'func(int, time.Duration) string' can be passed for custom formatting of the metric value. - -func (s *set) New(name, desc string, opts ...any) *Val { - v := &Val{ - name: name, - desc: desc, - graph: name, - fmt: func(v int, period time.Duration) string { return strconv.Itoa(v) }, - } - stacked := false - for _, o := range opts { - switch opt := o.(type) { - case Level: - v.level = opt - case Link: - v.link = string(opt) - case Graph: - v.graph = string(opt) - case StackedGraph: - v.graph = string(opt) - stacked = true - case Rate: - v.rate = true - v.fmt = formatRate - case Distribution: - v.hist = true - case func() int: - v.ext = opt - case func(int, time.Duration) string: - v.fmt = opt - case Prometheus: - // Prometheus Instrumentation https://prometheus.io/docs/guides/go-application. - prometheus.Register(prometheus.NewGaugeFunc(prometheus.GaugeOpts{ - Name: string(opt), - Help: desc, - }, - func() float64 { return float64(v.Val()) }, - )) - default: - panic(fmt.Sprintf("unknown stats option %#v", o)) - } - } - s.mu.Lock() - defer s.mu.Unlock() - s.vals[name] = v - if v.graph != "" { - if s.graphs[v.graph] == nil { - s.graphs[v.graph] = &graph{ - lines: make(map[string]*line), - } - } - if s.graphs[v.graph].level < v.level { - s.graphs[v.graph].level = v.level - } - s.graphs[v.graph].stacked = stacked - } - return v -} - -type Val struct { - name string - desc string - link string - graph string - level Level - val atomic.Uint64 - ext func() int - fmt func(int, time.Duration) string - rate bool - hist bool - prev int - histMu sync.Mutex - histVal *gohistogram.NumericHistogram -} - -func (v *Val) Add(val int) { - if v.ext != nil { - panic(fmt.Sprintf("stat %v is in external mode", v.name)) - } - if v.hist { - v.histMu.Lock() - if v.histVal == nil { - v.histVal = gohistogram.NewHistogram(histogramBuckets) - } - v.histVal.Add(float64(val)) - v.histMu.Unlock() - return - } - v.val.Add(uint64(val)) -} - -func (v *Val) Val() int { - if v.ext != nil { - return v.ext() - } - if v.hist { - v.histMu.Lock() - defer v.histMu.Unlock() - if v.histVal == nil { - return 0 - } - return int(v.histVal.Mean()) - } - return int(v.val.Load()) -} - -func formatRate(v int, period time.Duration) string { - secs := int(period.Seconds()) - if x := v / secs; x >= 10 { - return fmt.Sprintf("%v (%v/sec)", v, x) - } - if x := v * 60 / secs; x >= 10 { - return fmt.Sprintf("%v (%v/min)", v, x) - } - x := v * 60 * 60 / secs - return fmt.Sprintf("%v (%v/hour)", v, x) -} - -func (s *set) tick() { - s.mu.Lock() - defer s.mu.Unlock() - - if s.historyPos == s.historySize { - s.compress() - } - - s.totalTicks++ - s.historyTicks++ - for _, v := range s.vals { - if v.graph == "" { - continue - } - graph := s.graphs[v.graph] - ln := graph.lines[v.name] - if ln == nil { - ln = &line{ - desc: v.desc, - rate: v.rate, - } - if v.hist { - ln.hist = make([]*gohistogram.NumericHistogram, s.historySize) - } else { - ln.data = make([]float64, s.historySize) - } - graph.lines[v.name] = ln - } - if v.hist { - if s.historyTicks == s.historyScale { - v.histMu.Lock() - ln.hist[s.historyPos] = v.histVal - v.histVal = nil - v.histMu.Unlock() - } - } else { - val := v.Val() - pv := &ln.data[s.historyPos] - if v.rate { - *pv += float64(val-v.prev) / float64(s.historyScale) - v.prev = val - } else { - if *pv < float64(val) { - *pv = float64(val) - } - } - } - } - if s.historyTicks != s.historyScale { - return - } - s.historyTicks = 0 - s.historyPos++ -} - -func (s *set) compress() { - half := s.historySize / 2 - s.historyPos = half - s.historyScale *= 2 - for _, graph := range s.graphs { - for _, line := range graph.lines { - for i := 0; i < half; i++ { - if line.hist != nil { - h1, h2 := line.hist[2*i], line.hist[2*i+1] - line.hist[2*i], line.hist[2*i+1] = nil, nil - line.hist[i] = h1 - if h1 == nil { - line.hist[i] = h2 - } - } else { - v1, v2 := line.data[2*i], line.data[2*i+1] - line.data[2*i], line.data[2*i+1] = 0, 0 - if line.rate { - line.data[i] = (v1 + v2) / 2 - } else { - line.data[i] = v1 - if v2 > v1 { - line.data[i] = v2 - } - } - } - } - } - } -} - -func (s *set) RenderHTML() ([]byte, error) { - s.mu.Lock() - defer s.mu.Unlock() - type Point struct { - X int - Y []float64 - } - type Graph struct { - ID int - Title string - Stacked bool - Level Level - Lines []string - Points []Point - } - var graphs []Graph - tick := s.historyScale * int(tickPeriod.Seconds()) - for title, graph := range s.graphs { - if len(graph.lines) == 0 { - continue - } - g := Graph{ - ID: len(graphs), - Title: title, - Stacked: graph.stacked, - Level: graph.level, - Points: make([]Point, s.historyPos), - } - for i := 0; i < s.historyPos; i++ { - g.Points[i].X = i * tick - } - for name, ln := range graph.lines { - if ln.hist == nil { - g.Lines = append(g.Lines, name+": "+ln.desc) - for i := 0; i < s.historyPos; i++ { - g.Points[i].Y = append(g.Points[i].Y, ln.data[i]) - } - } else { - for _, percent := range []int{10, 50, 90} { - g.Lines = append(g.Lines, fmt.Sprintf("%v%%", percent)) - for i := 0; i < s.historyPos; i++ { - v := 0.0 - if ln.hist[i] != nil { - v = ln.hist[i].Quantile(float64(percent) / 100) - } - g.Points[i].Y = append(g.Points[i].Y, v) - } - } - } - } - graphs = append(graphs, g) - } - sort.Slice(graphs, func(i, j int) bool { - if graphs[i].Level != graphs[j].Level { - return graphs[i].Level > graphs[j].Level - } - return graphs[i].Title < graphs[j].Title - }) - buf := new(bytes.Buffer) - err := htmlTemplate.Execute(buf, graphs) - return buf.Bytes(), err -} - -var htmlTemplate = pages.Create(` - - - - syzkaller stats - - {{HEAD}} - - -{{range $g := .}} -
- -{{end}} - - -`) diff --git a/pkg/stats/set_test.go b/pkg/stats/set_test.go deleted file mode 100644 index 862882fc2..000000000 --- a/pkg/stats/set_test.go +++ /dev/null @@ -1,219 +0,0 @@ -// Copyright 2024 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package stats - -import ( - "fmt" - "math/rand" - "sync/atomic" - "testing" - "time" - - "github.com/stretchr/testify/assert" -) - -func TestSet(t *testing.T) { - a := assert.New(t) - set := newSet(4, false) - a.Empty(set.Collect(All)) - _, err := set.RenderHTML() - a.NoError(err) - - v0 := set.New("v0", "desc0") - a.Equal(v0.Val(), 0) - v0.Add(1) - a.Equal(v0.Val(), 1) - v0.Add(1) - a.Equal(v0.Val(), 2) - - vv1 := 0 - v1 := set.New("v1", "desc1", Simple, func() int { return vv1 }) - a.Equal(v1.Val(), 0) - vv1 = 11 - a.Equal(v1.Val(), 11) - a.Panics(func() { v1.Add(1) }) - - v2 := set.New("v2", "desc2", Console, func(v int, period time.Duration) string { - return fmt.Sprintf("v2 %v %v", v, period) - }) - v2.Add(100) - - v3 := set.New("v3", "desc3", Link("/v3"), NoGraph, Distribution{}) - a.Equal(v3.Val(), 0) - v3.Add(10) - a.Equal(v3.Val(), 10) - v3.Add(20) - a.Equal(v3.Val(), 15) - v3.Add(20) - a.Equal(v3.Val(), 16) - v3.Add(30) - a.Equal(v3.Val(), 20) - v3.Add(30) - a.Equal(v3.Val(), 22) - v3.Add(30) - v3.Add(30) - a.Equal(v3.Val(), 24) - - v4 := set.New("v4", "desc4", Rate{}, Graph("graph")) - v4.Add(10) - a.Equal(v4.Val(), 10) - v4.Add(10) - a.Equal(v4.Val(), 20) - - a.Panics(func() { set.New("v0", "desc0", float64(1)) }) - - ui := set.Collect(All) - a.Equal(len(ui), 5) - a.Equal(ui[0], UI{"v2", "desc2", "", Console, "v2 100 1s", 100}) - a.Equal(ui[1], UI{"v1", "desc1", "", Simple, "11", 11}) - a.Equal(ui[2], UI{"v0", "desc0", "", All, "2", 2}) - a.Equal(ui[3], UI{"v3", "desc3", "/v3", All, "24", 24}) - a.Equal(ui[4], UI{"v4", "desc4", "", All, "20 (20/sec)", 20}) - - ui1 := set.Collect(Simple) - a.Equal(len(ui1), 2) - a.Equal(ui1[0].Name, "v2") - a.Equal(ui1[1].Name, "v1") - - ui2 := set.Collect(Console) - a.Equal(len(ui2), 1) - a.Equal(ui2[0].Name, "v2") - - _, err = set.RenderHTML() - a.NoError(err) -} - -func TestSetRateFormat(t *testing.T) { - a := assert.New(t) - set := newSet(4, false) - v := set.New("v", "desc", Rate{}) - a.Equal(set.Collect(All)[0].Value, "0 (0/hour)") - v.Add(1) - a.Equal(set.Collect(All)[0].Value, "1 (60/min)") - v.Add(99) - a.Equal(set.Collect(All)[0].Value, "100 (100/sec)") -} - -func TestSetHistoryCounter(t *testing.T) { - a := assert.New(t) - set := newSet(4, false) - v := set.New("v0", "desc0") - set.tick() - hist := func() []float64 { return set.graphs["v0"].lines["v0"].data[:set.historyPos] } - step := func(n int) []float64 { - v.Add(n) - set.tick() - return hist() - } - a.Equal(hist(), []float64{0}) - v.Add(1) - v.Add(1) - a.Equal(hist(), []float64{0}) - set.tick() - a.Equal(hist(), []float64{0, 2}) - v.Add(3) - a.Equal(hist(), []float64{0, 2}) - set.tick() - a.Equal(hist(), []float64{0, 2, 5}) - a.Equal(step(-1), []float64{0, 2, 5, 4}) - // Compacted, each new history value will require 2 steps. - a.Equal(step(7), []float64{2, 5}) - a.Equal(step(-10), []float64{2, 5, 11}) - a.Equal(step(2), []float64{2, 5, 11}) - a.Equal(step(1), []float64{2, 5, 11, 4}) - // 4 steps for each new value. - a.Equal(step(1), []float64{5, 11}) - a.Equal(step(1), []float64{5, 11}) - a.Equal(step(1), []float64{5, 11}) - a.Equal(step(1), []float64{5, 11, 8}) -} - -func TestSetHistoryRate(t *testing.T) { - a := assert.New(t) - set := newSet(4, false) - v := set.New("v0", "desc0", Rate{}) - step := func(n int) []float64 { - v.Add(n) - set.tick() - return set.graphs["v0"].lines["v0"].data[:set.historyPos] - } - a.Equal(step(3), []float64{3}) - a.Equal(step(1), []float64{3, 1}) - a.Equal(step(2), []float64{3, 1, 2}) - a.Equal(step(5), []float64{3, 1, 2, 5}) - a.Equal(step(1), []float64{2, 3.5}) - a.Equal(step(2), []float64{2, 3.5, 1.5}) - a.Equal(step(2), []float64{2, 3.5, 1.5}) - a.Equal(step(4), []float64{2, 3.5, 1.5, 3}) - a.Equal(step(1), []float64{2.75, 2.25}) - a.Equal(step(2), []float64{2.75, 2.25}) - a.Equal(step(3), []float64{2.75, 2.25}) - a.Equal(step(4), []float64{2.75, 2.25, 2.5}) -} - -func TestSetHistoryDistribution(t *testing.T) { - a := assert.New(t) - set := newSet(4, false) - v := set.New("v0", "desc0", Distribution{}) - step := func(n int) [3][]float64 { - v.Add(n) - set.tick() - var history [3][]float64 - for p, percent := range []int{10, 50, 90} { - history[p] = make([]float64, set.historyPos) - for i := 0; i < set.historyPos; i++ { - hist := set.graphs["v0"].lines["v0"].hist[i] - if hist != nil { - history[p][i] = hist.Quantile(float64(percent) / 100) - } - } - } - return history - } - a.Equal(step(3), [3][]float64{{3}, {3}, {3}}) - a.Equal(step(6), [3][]float64{{3, 6}, {3, 6}, {3, 6}}) - a.Equal(step(1), [3][]float64{{3, 6, 1}, {3, 6, 1}, {3, 6, 1}}) - a.Equal(step(2), [3][]float64{{3, 6, 1, 2}, {3, 6, 1, 2}, {3, 6, 1, 2}}) - a.Equal(step(1), [3][]float64{{3, 1}, {3, 1}, {3, 1}}) - a.Equal(step(10), [3][]float64{{3, 1, 1}, {3, 1, 1}, {3, 1, 10}}) -} - -func TestSetStress(t *testing.T) { - set := newSet(4, false) - var stop atomic.Bool - var seq atomic.Uint64 - start := func(f func()) { - go func() { - for !stop.Load() { - f() - } - }() - } - for p := 0; p < 2; p++ { - for _, opt := range []any{Link(""), NoGraph, Rate{}, Distribution{}} { - opt := opt - go func() { - v := set.New(fmt.Sprintf("v%v", seq.Add(1)), "desc", opt) - for p1 := 0; p1 < 2; p1++ { - start(func() { v.Val() }) - start(func() { v.Add(rand.Intn(10000)) }) - } - }() - } - go func() { - var vv atomic.Uint64 - v := set.New(fmt.Sprintf("v%v", seq.Add(1)), "desc", - func() int { return int(vv.Load()) }) - for p1 := 0; p1 < 2; p1++ { - start(func() { v.Val() }) - start(func() { vv.Store(uint64(rand.Intn(10000))) }) - } - }() - start(func() { set.Collect(All) }) - start(func() { set.RenderHTML() }) - start(func() { set.tick() }) - } - time.Sleep(time.Second) - stop.Store(true) -} diff --git a/pkg/stats/syzbotstats/bug.go b/pkg/stats/syzbotstats/bug.go deleted file mode 100644 index c11274583..000000000 --- a/pkg/stats/syzbotstats/bug.go +++ /dev/null @@ -1,32 +0,0 @@ -// Copyright 2023 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package syzbotstats - -import "time" - -type BugStatSummary struct { - Title string - IDs []string // IDs used by syzbot for this bug. - FirstTime time.Time // When the bug was first hit. - ReleasedTime time.Time // When the bug was published. - ReproTime time.Time // When we found the reproducer. - CauseBisectTime time.Time // When we found cause bisection. - ResolvedTime time.Time // When the bug was resolved. - Status BugStatus - Subsystems []string - Strace bool // Whether we managed to reproduce under strace. - HitsPerDay float64 // Average number of bug hits per day. - FixHashes []string // Hashes of fix commits. - HappenedOn []string // Managers on which the crash happened. -} - -type BugStatus string - -const ( - BugFixed BugStatus = "fixed" - BugInvalidated BugStatus = "invalidated" - BugAutoInvalidated BugStatus = "auto-invalidated" - BugDup BugStatus = "dup" - BugPending BugStatus = "pending" -) -- cgit mrf-deployment