text:
// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package xsrftoken

import (
	"encoding/base64"
	"testing"
	"time"
)

const (
	key      = "quay"
	userID   = "12345678"
	actionID = "POST /form"
)

var (
	now              = time.Now()
	oneMinuteFromNow = now.Add(1 * time.Minute)
)

func TestValidToken(t *testing.T) {
	tok := generateTokenAtTime(key, userID, actionID, now)
	if !validTokenAtTime(tok, key, userID, actionID, oneMinuteFromNow) {
		t.Error("One second later: Expected token to be valid")
	}
	if !validTokenAtTime(tok, key, userID, actionID, now.Add(Timeout-1*time.Nanosecond)) {
		t.Error("Just before timeout: Expected token to be valid")
	}
	if !validTokenAtTime(tok, key, userID, actionID, now.Add(-1*time.Minute+1*time.Millisecond)) {
		t.Error("One minute in the past: Expected token to be valid")
	}
}

// TestSeparatorReplacement tests that separators are being correctly substituted
func TestSeparatorReplacement(t *testing.T) {
	tok := generateTokenAtTime("foo:bar", "baz", "wah", now)
	tok2 := generateTokenAtTime("foo", "bar:baz", "wah", now)
	if tok == tok2 {
		t.Errorf("Expected generated tokens to be different")
	}
}

func TestInvalidToken(t *testing.T) {
	invalidTokenTests := []struct {
		name, key, userID, actionID string
		t                           time.Time
	}{
		{"Bad key", "foobar", userID, actionID, oneMinuteFromNow},
		{"Bad userID", key, "foobar", actionID, oneMinuteFromNow},
		{"Bad actionID", key, userID, "foobar", oneMinuteFromNow},
		{"Expired", key, userID, actionID, now.Add(Timeout + 1*time.Millisecond)},
		{"More than 1 minute from the future", key, userID, actionID, now.Add(-1*time.Nanosecond - 1*time.Minute)},
	}

	tok := generateTokenAtTime(key, userID, actionID, now)
	for _, itt := range invalidTokenTests {
		if validTokenAtTime(tok, itt.key, itt.userID, itt.actionID, itt.t) {
			t.Errorf("%v: Expected token to be invalid", itt.name)
		}
	}
}

// TestValidateBadData primarily tests that no unexpected panics are triggered
// during parsing
func TestValidateBadData(t *testing.T) {
	badDataTests := []struct {
		name, tok string
	}{
		{"Invalid Base64", "ASDab24(@)$*=="},
		{"No delimiter", base64.URLEncoding.EncodeToString([]byte("foobar12345678"))},
		{"Invalid time", base64.URLEncoding.EncodeToString([]byte("foobar:foobar"))},
		{"Wrong length", "1234" + generateTokenAtTime(key, userID, actionID, now)},
	}

	for _, bdt := range badDataTests {
		if validTokenAtTime(bdt.tok, key, userID, actionID, oneMinuteFromNow) {
			t.Errorf("%v: Expected token to be invalid", bdt.name)
		}
	}
}


text:
// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package trace

// This file implements histogramming for RPC statistics collection.

import (
	"bytes"
	"fmt"
	"html/template"
	"log"
	"math"
	"sync"

	"golang.org/x/net/internal/timeseries"
)

const (
	bucketCount = 38
)

// histogram keeps counts of values in buckets that are spaced
// out in powers of 2: 0-1, 2-3, 4-7...
// histogram implements timeseries.Observable
type histogram struct {
	sum          int64   // running total of measurements
	sumOfSquares float64 // square of running total
	buckets      []int64 // bucketed values for histogram
	value        int     // holds a single value as an optimization
	valueCount   int64   // number of values recorded for single value
}

// AddMeasurement records a value measurement observation to the histogram.
func (h *histogram) addMeasurement(value int64) {
	// TODO: assert invariant
	h.sum += value
	h.sumOfSquares += float64(value) * float64(value)

	bucketIndex := getBucket(value)

	if h.valueCount == 0 || (h.valueCount > 0 && h.value == bucketIndex) {
		h.value = bucketIndex
		h.valueCount++
	} else {
		h.allocateBuckets()
		h.buckets[bucketIndex]++
	}
}

func (h *histogram) allocateBuckets() {
	if h.buckets == nil {
		h.buckets = make([]int64, bucketCount)
		h.buckets[h.value] = h.valueCount
		h.value = 0
		h.valueCount = -1
	}
}

func log2(i int64) int {
	n := 0
	for ; i >= 0x100; i >>= 8 {
		n += 8
	}
	for ; i > 0; i >>= 1 {
		n += 1
	}
	return n
}

func getBucket(i int64) (index int) {
	index = log2(i) - 1
	if index < 0 {
		index = 0
	}
	if index >= bucketCount {
		index = bucketCount - 1
	}
	return
}

// Total returns the number of recorded observations.
func (h *histogram) total() (total int64) {
	if h.valueCount >= 0 {
		total = h.valueCount
	}
	for _, val := range h.buckets {
		total += int64(val)
	}
	return
}

// Average returns the average value of recorded observations.
func (h *histogram) average() float64 {
	t := h.total()
	if t == 0 {
		return 0
	}
	return float64(h.sum) / float64(t)
}

// Variance returns the variance of recorded observations.
func (h *histogram) variance() float64 {
	t := float64(h.total())
	if t == 0 {
		return 0
	}
	s := float64(h.sum) / t
	return h.sumOfSquares/t - s*s
}

// StandardDeviation returns the standard deviation of recorded observations.
func (h *histogram) standardDeviation() float64 {
	return math.Sqrt(h.variance())
}

// PercentileBoundary estimates the value that the given fraction of recorded
// observations are less than.
func (h *histogram) percentileBoundary(percentile float64) int64 {
	total := h.total()

	// Corner cases (make sure result is strictly less than Total())
	if total == 0 {
		return 0
	} else if total == 1 {
		return int64(h.average())
	}

	percentOfTotal := round(float64(total) * percentile)
	var runningTotal int64

	for i := range h.buckets {
		value := h.buckets[i]
		runningTotal += value
		if runningTotal == percentOfTotal {
			// We hit an exact bucket boundary. If the next bucket has data, it is a
			// good estimate of the value. If the bucket is empty, we interpolate the
			// midpoint between the next bucket's boundary and the next non-zero
			// bucket. If the remaining buckets are all empty, then we use the
			// boundary for the next bucket as the estimate.
			j := uint8(i + 1)
			min := bucketBoundary(j)
			if runningTotal < total {
				for h.buckets[j] == 0 {
					j++
				}
			}
			max := bucketBoundary(j)
			return min + round(float64(max-min)/2)
		} else if runningTotal > percentOfTotal {
			// The value is in this bucket. Interpolate the value.
			delta := runningTotal - percentOfTotal
			percentBucket := float64(value-delta) / float64(value)
			bucketMin := bucketBoundary(uint8(i))
			nextBucketMin := bucketBoundary(uint8(i + 1))
			bucketSize := nextBucketMin - bucketMin
			return bucketMin + round(percentBucket*float64(bucketSize))
		}
	}
	return bucketBoundary(bucketCount - 1)
}

// Median returns the estimated median of the observed values.
func (h *histogram) median() int64 {
	return h.percentileBoundary(0.5)
}

// Add adds other to h.
func (h *histogram) Add(other timeseries.Observable) {
	o := other.(*histogram)
	if o.valueCount == 0 {
		// Other histogram is empty
	} else if h.valueCount >= 0 && o.valueCount > 0 && h.value == o.value {
		// Both have a single bucketed value, aggregate them
		h.valueCount += o.valueCount
	} else {
		// Two different values necessitate buckets in this histogram
		h.allocateBuckets()
		if o.valueCount >= 0 {
			h.buckets[o.value] += o.valueCount
		} else {
			for i := range h.buckets {
				h.buckets[i] += o.buckets[i]
			}
		}
	}
	h.sumOfSquares += o.sumOfSquares
	h.sum += o.sum
}

// Clear resets the histogram to an empty state, removing all observed values.
func (h *histogram) Clear() {
	h.buckets = nil
	h.value = 0
	h.valueCount = 0
	h.sum = 0
	h.sumOfSquares = 0
}

// CopyFrom copies from other, which must be a *histogram, into h.
func (h *histogram) CopyFrom(other timeseries.Observable) {
	o := other.(*histogram)
	if o.valueCount == -1 {
		h.allocateBuckets()
		copy(h.buckets, o.buckets)
	}
	h.sum = o.sum
	h.sumOfSquares = o.sumOfSquares
	h.value = o.value
	h.valueCount = o.valueCount
}

// Multiply scales the histogram by the specified ratio.
func (h *histogram) Multiply(ratio float64) {
	if h.valueCount == -1 {
		for i := range h.buckets {
			h.buckets[i] = int64(float64(h.buckets[i]) * ratio)
		}
	} else {
		h.valueCount = int64(float64(h.valueCount) * ratio)
	}
	h.sum = int64(float64(h.sum) * ratio)
	h.sumOfSquares = h.sumOfSquares * ratio
}

// New creates a new histogram.
func (h *histogram) New() timeseries.Observable {
	r := new(histogram)
	r.Clear()
	return r
}

func (h *histogram) String() string {
	return fmt.Sprintf("%d, %f, %d, %d, %v",
		h.sum, h.sumOfSquares, h.value, h.valueCount, h.buckets)
}

// round returns the closest int64 to the argument
func round(in float64) int64 {
	return int64(math.Floor(in + 0.5))
}

// bucketBoundary returns the first value in the bucket.
func bucketBoundary(bucket uint8) int64 {
	if bucket == 0 {
		return 0
	}
	return 1 << bucket
}

// bucketData holds data about a specific bucket for use in distTmpl.
type bucketData struct {
	Lower, Upper       int64
	N                  int64
	Pct, CumulativePct float64
	GraphWidth         int
}

// data holds data about a Distribution for use in distTmpl.
type data struct {
	Buckets                 []*bucketData
	Count, Median           int64
	Mean, StandardDeviation float64
}

// maxHTMLBarWidth is the maximum width of the HTML bar for visualizing buckets.
const maxHTMLBarWidth = 350.0

// newData returns data representing h for use in distTmpl.
func (h *histogram) newData() *data {
	// Force the allocation of buckets to simplify the rendering implementation
	h.allocateBuckets()
	// We scale the bars on the right so that the largest bar is
	// maxHTMLBarWidth pixels in width.
	maxBucket := int64(0)
	for _, n := range h.buckets {
		if n > maxBucket {
			maxBucket = n
		}
	}
	total := h.total()
	barsizeMult := maxHTMLBarWidth / float64(maxBucket)
	var pctMult float64
	if total == 0 {
		pctMult = 1.0
	} else {
		pctMult = 100.0 / float64(total)
	}

	buckets := make([]*bucketData, len(h.buckets))
	runningTotal := int64(0)
	for i, n := range h.buckets {
		if n == 0 {
			continue
		}
		runningTotal += n
		var upperBound int64
		if i < bucketCount-1 {
			upperBound = bucketBoundary(uint8(i + 1))
		} else {
			upperBound = math.MaxInt64
		}
		buckets[i] = &bucketData{
			Lower:         bucketBoundary(uint8(i)),
			Upper:         upperBound,
			N:             n,
			Pct:           float64(n) * pctMult,
			CumulativePct: float64(runningTotal) * pctMult,
			GraphWidth:    int(float64(n) * barsizeMult),
		}
	}
	return &data{
		Buckets:           buckets,
		Count:             total,
		Median:            h.median(),
		Mean:              h.average(),
		StandardDeviation: h.standardDeviation(),
	}
}

func (h *histogram) html() template.HTML {
	buf := new(bytes.Buffer)
	if err := distTmpl().Execute(buf, h.newData()); err != nil {
		buf.Reset()
		log.Printf("net/trace: couldn't execute template: %v", err)
	}
	return template.HTML(buf.String())
}

var distTmplCache *template.Template
var distTmplOnce sync.Once

func distTmpl() *template.Template {
	distTmplOnce.Do(func() {
		// Input: data
		distTmplCache = template.Must(template.New("distTmpl").Parse(`

    Count: {{.Count}}
    Mean: {{printf "%.0f" .Mean}}
    StdDev: {{printf "%.0f" .StandardDeviation}}
    Median: {{.Median}}

{{range $b := .Buckets}}
{{if $b}}

    [
    {{.Lower}},
    {{.Upper}})
    {{.N}}
    {{printf "%#.3f" .Pct}}%
    {{printf "%#.3f" .CumulativePct}}%

{{end}}
{{end}}

`))
	})
	return distTmplCache
}

repo_name: dan-v/dosxvpn

repo_language: Go

mime_type: text/x-shellscript


text:
// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package trace

import (
	"net/http"
	"reflect"
	"testing"
)

type s struct{}

func (s) String() string { return "lazy string" }

// TestReset checks whether all the fields are zeroed after reset.
func TestReset(t *testing.T) {
	tr := New("foo", "bar")
	tr.LazyLog(s{}, false)
	tr.LazyPrintf("%d", 1)
	tr.SetRecycler(func(_ interface{}) {})
	tr.SetTraceInfo(3, 4)
	tr.SetMaxEvents(100)
	tr.SetError()
	tr.Finish()

	tr.(*trace).reset()

	if !reflect.DeepEqual(tr, new(trace)) {
		t.Errorf("reset didn't clear all fields: %+v", tr)
	}
}

// TestResetLog checks whether all the fields are zeroed after reset.
func TestResetLog(t *testing.T) {
	el := NewEventLog("foo", "bar")
	el.Printf("message")
	el.Errorf("error")
	el.Finish()

	el.(*eventLog).reset()

	if !reflect.DeepEqual(el, new(eventLog)) {
		t.Errorf("reset didn't clear all fields: %+v", el)
	}
}

func TestAuthRequest(t *testing.T) {
	testCases := []struct {
		host string
		want bool
	}{
		{host: "192.168.23.1", want: false},
		{host: "192.168.23.1:8080", want: false},
		{host: "malformed remote addr", want: false},
		{host: "localhost", want: true},
		{host: "localhost:8080", want: true},
		{host: "127.0.0.1", want: true},
		{host: "127.0.0.1:8080", want: true},
		{host: "::1", want: true},
		{host: "[::1]:8080", want: true},
	}
	for _, tt := range testCases {
		req := &http.Request{RemoteAddr: tt.host}
		any, sensitive := AuthRequest(req)
		if any != tt.want || sensitive != tt.want {
			t.Errorf("AuthRequest(%q) = %t, %t; want %t, %t", tt.host, any, sensitive, tt.want, tt.want)
		}
	}
}

// TestParseTemplate checks that all templates used by this package are valid
// as they are parsed on first usage
func TestParseTemplate(t *testing.T) {
	if tmpl := distTmpl(); tmpl == nil {
		t.Error("invalid template returned from distTmpl()")
	}
	if tmpl := pageTmpl(); tmpl == nil {
		t.Error("invalid template returned from pageTmpl()")
	}
	if tmpl := eventsTmpl(); tmpl == nil {
		t.Error("invalid template returned from eventsTmpl()")
	}
}

func benchmarkTrace(b *testing.B, maxEvents, numEvents int) {
	numSpans := (b.N + numEvents + 1) / numEvents

	for i := 0; i < numSpans; i++ {
		tr := New("test", "test")
		tr.SetMaxEvents(maxEvents)
		for j := 0; j < numEvents; j++ {
			tr.LazyPrintf("%d", j)
		}
		tr.Finish()
	}
}

func BenchmarkTrace_Default_2(b *testing.B) {
	benchmarkTrace(b, 0, 2)
}

func BenchmarkTrace_Default_10(b *testing.B) {
	benchmarkTrace(b, 0, 10)
}

func BenchmarkTrace_Default_100(b *testing.B) {
	benchmarkTrace(b, 0, 100)
}

func BenchmarkTrace_Default_1000(b *testing.B) {
	benchmarkTrace(b, 0, 1000)
}

func BenchmarkTrace_Default_10000(b *testing.B) {
	benchmarkTrace(b, 0, 10000)
}

func BenchmarkTrace_10_2(b *testing.B) {
	benchmarkTrace(b, 10, 2)
}

func BenchmarkTrace_10_10(b *testing.B) {
	benchmarkTrace(b, 10, 10)
}

func BenchmarkTrace_10_100(b *testing.B) {
	benchmarkTrace(b, 10, 100)
}

func BenchmarkTrace_10_1000(b *testing.B) {
	benchmarkTrace(b, 10, 1000)
}

func BenchmarkTrace_10_10000(b *testing.B) {
	benchmarkTrace(b, 10, 10000)
}

func BenchmarkTrace_100_2(b *testing.B) {
	benchmarkTrace(b, 100, 2)
}

func BenchmarkTrace_100_10(b *testing.B) {
	benchmarkTrace(b, 100, 10)
}

func BenchmarkTrace_100_100(b *testing.B) {
	benchmarkTrace(b, 100, 100)
}

func BenchmarkTrace_100_1000(b *testing.B) {
	benchmarkTrace(b, 100, 1000)
}

func BenchmarkTrace_100_10000(b *testing.B) {
	benchmarkTrace(b, 100, 10000)
}

func BenchmarkTrace_1000_2(b *testing.B) {
	benchmarkTrace(b, 1000, 2)
}

func BenchmarkTrace_1000_10(b *testing.B) {
	benchmarkTrace(b, 1000, 10)
}

func BenchmarkTrace_1000_100(b *testing.B) {
	benchmarkTrace(b, 1000, 100)
}

func BenchmarkTrace_1000_1000(b *testing.B) {
	benchmarkTrace(b, 1000, 1000)
}

func BenchmarkTrace_1000_10000(b *testing.B) {
	benchmarkTrace(b, 1000, 10000)
}


text:
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// +build go1.7

package trace

import "context"

// NewContext returns a copy of the parent context
// and associates it with a Trace.
func NewContext(ctx context.Context, tr Trace) context.Context {
	return context.WithValue(ctx, contextKey, tr)
}

// FromContext returns the Trace bound to the context, if any.
func FromContext(ctx context.Context) (tr Trace, ok bool) {
	tr, ok = ctx.Value(contextKey).(Trace)
	return
}


text:
// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package trace

import (
	"bytes"
	"fmt"
	"html/template"
	"io"
	"log"
	"net/http"
	"runtime"
	"sort"
	"strconv"
	"strings"
	"sync"
	"sync/atomic"
	"text/tabwriter"
	"time"
)

const maxEventsPerLog = 100

type bucket struct {
	MaxErrAge time.Duration
	String    string
}

var buckets = []bucket{
	{0, "total"},
	{10 * time.Second, "errs<10s"},
	{1 * time.Minute, "errs<1m"},
	{10 * time.Minute, "errs<10m"},
	{1 * time.Hour, "errs<1h"},
	{10 * time.Hour, "errs<10h"},
	{24000 * time.Hour, "errors"},
}

// RenderEvents renders the HTML page typically served at /debug/events.
// It does not do any auth checking. The request may be nil.
//
// Most users will use the Events handler.
func RenderEvents(w http.ResponseWriter, req *http.Request, sensitive bool) {
	now := time.Now()
	data := &struct {
		Families []string // family names
		Buckets  []bucket
		Counts   [][]int // eventLog count per family/bucket

		// Set when a bucket has been selected.
		Family    string
		Bucket    int
		EventLogs eventLogs
		Expanded  bool
	}{
		Buckets: buckets,
	}

	data.Families = make([]string, 0, len(families))
	famMu.RLock()
	for name := range families {
		data.Families = append(data.Families, name)
	}
	famMu.RUnlock()
	sort.Strings(data.Families)

	// Count the number of eventLogs in each family for each error age.
	data.Counts = make([][]int, len(data.Families))
	for i, name := range data.Families {
		// TODO(sameer): move this loop under the family lock.
		f := getEventFamily(name)
		data.Counts[i] = make([]int, len(data.Buckets))
		for j, b := range data.Buckets {
			data.Counts[i][j] = f.Count(now, b.MaxErrAge)
		}
	}

	if req != nil {
		var ok bool
		data.Family, data.Bucket, ok = parseEventsArgs(req)
		if !ok {
			// No-op
		} else {
			data.EventLogs = getEventFamily(data.Family).Copy(now, buckets[data.Bucket].MaxErrAge)
		}
		if data.EventLogs != nil {
			defer data.EventLogs.Free()
			sort.Sort(data.EventLogs)
		}
		if exp, err := strconv.ParseBool(req.FormValue("exp")); err == nil {
			data.Expanded = exp
		}
	}

	famMu.RLock()
	defer famMu.RUnlock()
	if err := eventsTmpl().Execute(w, data); err != nil {
		log.Printf("net/trace: Failed executing template: %v", err)
	}
}

func parseEventsArgs(req *http.Request) (fam string, b int, ok bool) {
	fam, bStr := req.FormValue("fam"), req.FormValue("b")
	if fam == "" || bStr == "" {
		return "", 0, false
	}
	b, err := strconv.Atoi(bStr)
	if err != nil || b < 0 || b >= len(buckets) {
		return "", 0, false
	}
	return fam, b, true
}

// An EventLog provides a log of events associated with a specific object.
type EventLog interface {
	// Printf formats its arguments with fmt.Sprintf and adds the
	// result to the event log.
	Printf(format string, a ...interface{})

	// Errorf is like Printf, but it marks this event as an error.
	Errorf(format string, a ...interface{})

	// Finish declares that this event log is complete.
	// The event log should not be used after calling this method.
	Finish()
}

// NewEventLog returns a new EventLog with the specified family name
// and title.
func NewEventLog(family, title string) EventLog {
	el := newEventLog()
	el.ref()
	el.Family, el.Title = family, title
	el.Start = time.Now()
	el.events = make([]logEntry, 0, maxEventsPerLog)
	el.stack = make([]uintptr, 32)
	n := runtime.Callers(2, el.stack)
	el.stack = el.stack[:n]

	getEventFamily(family).add(el)
	return el
}

func (el *eventLog) Finish() {
	getEventFamily(el.Family).remove(el)
	el.unref() // matches ref in New
}

var (
	famMu    sync.RWMutex
	families = make(map[string]*eventFamily) // family name => family
)

func getEventFamily(fam string) *eventFamily {
	famMu.Lock()
	defer famMu.Unlock()
	f := families[fam]
	if f == nil {
		f = &eventFamily{}
		families[fam] = f
	}
	return f
}

type eventFamily struct {
	mu        sync.RWMutex
	eventLogs eventLogs
}

func (f *eventFamily) add(el *eventLog) {
	f.mu.Lock()
	f.eventLogs = append(f.eventLogs, el)
	f.mu.Unlock()
}

func (f *eventFamily) remove(el *eventLog) {
	f.mu.Lock()
	defer f.mu.Unlock()
	for i, el0 := range f.eventLogs {
		if el == el0 {
			copy(f.eventLogs[i:], f.eventLogs[i+1:])
			f.eventLogs = f.eventLogs[:len(f.eventLogs)-1]
			return
		}
	}
}

func (f *eventFamily) Count(now time.Time, maxErrAge time.Duration) (n int) {
	f.mu.RLock()
	defer f.mu.RUnlock()
	for _, el := range f.eventLogs {
		if el.hasRecentError(now, maxErrAge) {
			n++
		}
	}
	return
}

func (f *eventFamily) Copy(now time.Time, maxErrAge time.Duration) (els eventLogs) {
	f.mu.RLock()
	defer f.mu.RUnlock()
	els = make(eventLogs, 0, len(f.eventLogs))
	for _, el := range f.eventLogs {
		if el.hasRecentError(now, maxErrAge) {
			el.ref()
			els = append(els, el)
		}
	}
	return
}

type eventLogs []*eventLog

// Free calls unref on each element of the list.
func (els eventLogs) Free() {
	for _, el := range els {
		el.unref()
	}
}

// eventLogs may be sorted in reverse chronological order.
func (els eventLogs) Len() int           { return len(els) }
func (els eventLogs) Less(i, j int) bool { return els[i].Start.After(els[j].Start) }
func (els eventLogs) Swap(i, j int)      { els[i], els[j] = els[j], els[i] }

// A logEntry is a timestamped log entry in an event log.
type logEntry struct {
	When    time.Time
	Elapsed time.Duration // since previous event in log
	NewDay  bool          // whether this event is on a different day to the previous event
	What    string
	IsErr   bool
}

// WhenString returns a string representation of the elapsed time of the event.
// It will include the date if midnight was crossed.
func (e logEntry) WhenString() string {
	if e.NewDay {
		return e.When.Format("2006/01/02 15:04:05.000000")
	}
	return e.When.Format("15:04:05.000000")
}

// An eventLog represents an active event log.
type eventLog struct {
	// Family is the top-level grouping of event logs to which this belongs.
	Family string

	// Title is the title of this event log.
	Title string

	// Timing information.
	Start time.Time

	// Call stack where this event log was created.
	stack []uintptr

	// Append-only sequence of events.
	//
	// TODO(sameer): change this to a ring buffer to avoid the array copy
	// when we hit maxEventsPerLog.
	mu            sync.RWMutex
	events        []logEntry
	LastErrorTime time.Time
	discarded     int

	refs int32 // how many buckets this is in
}

func (el *eventLog) reset() {
	// Clear all but the mutex. Mutexes may not be copied, even when unlocked.
	el.Family = ""
	el.Title = ""
	el.Start = time.Time{}
	el.stack = nil
	el.events = nil
	el.LastErrorTime = time.Time{}
	el.discarded = 0
	el.refs = 0
}

func (el *eventLog) hasRecentError(now time.Time, maxErrAge time.Duration) bool {
	if maxErrAge == 0 {
		return true
	}
	el.mu.RLock()
	defer el.mu.RUnlock()
	return now.Sub(el.LastErrorTime) < maxErrAge
}

// delta returns the elapsed time since the last event or the log start,
// and whether it spans midnight.
// L >= el.mu
func (el *eventLog) delta(t time.Time) (time.Duration, bool) {
	if len(el.events) == 0 {
		return t.Sub(el.Start), false
	}
	prev := el.events[len(el.events)-1].When
	return t.Sub(prev), prev.Day() != t.Day()

}

func (el *eventLog) Printf(format string, a ...interface{}) {
	el.printf(false, format, a...)
}

func (el *eventLog) Errorf(format string, a ...interface{}) {
	el.printf(true, format, a...)
}

func (el *eventLog) printf(isErr bool, format string, a ...interface{}) {
	e := logEntry{When: time.Now(), IsErr: isErr, What: fmt.Sprintf(format, a...)}
	el.mu.Lock()
	e.Elapsed, e.NewDay = el.delta(e.When)
	if len(el.events) < maxEventsPerLog {
		el.events = append(el.events, e)
	} else {
		// Discard the oldest event.
		if el.discarded == 0 {
			// el.discarded starts at two to count for the event it
			// is replacing, plus the next one that we are about to
			// drop.
			el.discarded = 2
		} else {
			el.discarded++
		}
		// TODO(sameer): if this causes allocations on a critical path,
		// change eventLog.What to be a fmt.Stringer, as in trace.go.
		el.events[0].What = fmt.Sprintf("(%d events discarded)", el.discarded)
		// The timestamp of the discarded meta-event should be
		// the time of the last event it is representing.
		el.events[0].When = el.events[1].When
		copy(el.events[1:], el.events[2:])
		el.events[maxEventsPerLog-1] = e
	}
	if e.IsErr {
		el.LastErrorTime = e.When
	}
	el.mu.Unlock()
}

func (el *eventLog) ref() {
	atomic.AddInt32(&el.refs, 1)
}

func (el *eventLog) unref() {
	if atomic.AddInt32(&el.refs, -1) == 0 {
		freeEventLog(el)
	}
}

func (el *eventLog) When() string {
	return el.Start.Format("2006/01/02 15:04:05.000000")
}

func (el *eventLog) ElapsedTime() string {
	elapsed := time.Since(el.Start)
	return fmt.Sprintf("%.6f", elapsed.Seconds())
}

func (el *eventLog) Stack() string {
	buf := new(bytes.Buffer)
	tw := tabwriter.NewWriter(buf, 1, 8, 1, '\t', 0)
	printStackRecord(tw, el.stack)
	tw.Flush()
	return buf.String()
}

// printStackRecord prints the function + source line information
// for a single stack trace.
// Adapted from runtime/pprof/pprof.go.
func printStackRecord(w io.Writer, stk []uintptr) {
	for _, pc := range stk {
		f := runtime.FuncForPC(pc)
		if f == nil {
			continue
		}
		file, line := f.FileLine(pc)
		name := f.Name()
		// Hide runtime.goexit and any runtime functions at the beginning.
		if strings.HasPrefix(name, "runtime.") {
			continue
		}
		fmt.Fprintf(w, "#   %s\t%s:%d\n", name, file, line)
	}
}

func (el *eventLog) Events() []logEntry {
	el.mu.RLock()
	defer el.mu.RUnlock()
	return el.events
}

// freeEventLogs is a freelist of *eventLog
var freeEventLogs = make(chan *eventLog, 1000)

// newEventLog returns a event log ready to use.
func newEventLog() *eventLog {
	select {
	case el := <-freeEventLogs:
		return el
	default:
		return new(eventLog)
	}
}

// freeEventLog adds el to freeEventLogs if there's room.
// This is non-blocking.
func freeEventLog(el *eventLog) {
	el.reset()
	select {
	case freeEventLogs <- el:
	default:
	}
}

var eventsTmplCache *template.Template
var eventsTmplOnce sync.Once

func eventsTmpl() *template.Template {
	eventsTmplOnce.Do(func() {
		eventsTmplCache = template.Must(template.New("events").Funcs(template.FuncMap{
			"elapsed":   elapsed,
			"trimSpace": strings.TrimSpace,
		}).Parse(eventsHTML))
	})
	return eventsTmplCache
}

const eventsHTML = `

		<title>events</title>

/debug/events

	{{range $i, $fam := .Families}}

		{{$fam}}

	        {{range $j, $bucket := $.Buckets}}
	        {{$n := index $.Counts $i $j}}

	                {{if $n}}{{end}}
		        [{{$n}} {{$bucket.String}}]
			{{if $n}}{{end}}

                {{end}}

{{end}}

{{if $.EventLogs}}

Family: {{$.Family}}

{{if $.Expanded}}{{end}}
[Summary]{{if $.Expanded}}{{end}}

{{if not $.Expanded}}{{end}}
[Expanded]{{if not $.Expanded}}{{end}}

When	Elapsed

	{{range $el := $.EventLogs}}

		{{$el.When}}
		{{$el.ElapsedTime}}
		{{$el.Title}}

	{{if $.Expanded}}

{{$el.Stack|trimSpace}}

	{{range $el.Events}}

		{{.WhenString}}
		{{elapsed .Elapsed}}
		.{{if .IsErr}}E{{else}}.{{end}}. {{.What}}

	{{end}}
	{{end}}
	{{end}}

{{end}}

`


text:
// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

/*
Package trace implements tracing of requests and long-lived objects.
It exports HTTP interfaces on /debug/requests and /debug/events.

A trace.Trace provides tracing for short-lived objects, usually requests.
A request handler might be implemented like this:

	func fooHandler(w http.ResponseWriter, req *http.Request) {
		tr := trace.New("mypkg.Foo", req.URL.Path)
		defer tr.Finish()
		...
		tr.LazyPrintf("some event %q happened", str)
		...
		if err := somethingImportant(); err != nil {
			tr.LazyPrintf("somethingImportant failed: %v", err)
			tr.SetError()
		}
	}

The /debug/requests HTTP endpoint organizes the traces by family,
errors, and duration.  It also provides histogram of request duration
for each family.

A trace.EventLog provides tracing for long-lived objects, such as RPC
connections.

	// A Fetcher fetches URL paths for a single domain.
	type Fetcher struct {
		domain string
		events trace.EventLog
	}

	func NewFetcher(domain string) *Fetcher {
		return &Fetcher{
			domain,
			trace.NewEventLog("mypkg.Fetcher", domain),
		}
	}

	func (f *Fetcher) Fetch(path string) (string, error) {
		resp, err := http.Get("http://" + f.domain + "/" + path)
		if err != nil {
			f.events.Errorf("Get(%q) = %v", path, err)
			return "", err
		}
		f.events.Printf("Get(%q) = %s", path, resp.Status)
		...
	}

	func (f *Fetcher) Close() error {
		f.events.Finish()
		return nil
	}

The /debug/events HTTP endpoint organizes the event logs by family and
by time since the last error.  The expanded view displays recent log
entries and the log's call stack.
*/
package trace // import "golang.org/x/net/trace"

import (
	"bytes"
	"fmt"
	"html/template"
	"io"
	"log"
	"net"
	"net/http"
	"runtime"
	"sort"
	"strconv"
	"sync"
	"sync/atomic"
	"time"

	"golang.org/x/net/internal/timeseries"
)

// DebugUseAfterFinish controls whether to debug uses of Trace values after finishing.
// FOR DEBUGGING ONLY. This will slow down the program.
var DebugUseAfterFinish = false

// AuthRequest determines whether a specific request is permitted to load the
// /debug/requests or /debug/events pages.
//
// It returns two bools; the first indicates whether the page may be viewed at all,
// and the second indicates whether sensitive events will be shown.
//
// AuthRequest may be replaced by a program to customize its authorization requirements.
//
// The default AuthRequest function returns (true, true) if and only if the request
// comes from localhost/127.0.0.1/[::1].
var AuthRequest = func(req *http.Request) (any, sensitive bool) {
	// RemoteAddr is commonly in the form "IP" or "IP:port".
	// If it is in the form "IP:port", split off the port.
	host, _, err := net.SplitHostPort(req.RemoteAddr)
	if err != nil {
		host = req.RemoteAddr
	}
	switch host {
	case "localhost", "127.0.0.1", "::1":
		return true, true
	default:
		return false, false
	}
}

func init() {
	// TODO(jbd): Serve Traces from /debug/traces in the future?
	// There is no requirement for a request to be present to have traces.
	http.HandleFunc("/debug/requests", Traces)
	http.HandleFunc("/debug/events", Events)
}

// Traces responds with traces from the program.
// The package initialization registers it in http.DefaultServeMux
// at /debug/requests.
//
// It performs authorization by running AuthRequest.
func Traces(w http.ResponseWriter, req *http.Request) {
	any, sensitive := AuthRequest(req)
	if !any {
		http.Error(w, "not allowed", http.StatusUnauthorized)
		return
	}
	w.Header().Set("Content-Type", "text/html; charset=utf-8")
	Render(w, req, sensitive)
}

// Events responds with a page of events collected by EventLogs.
// The package initialization registers it in http.DefaultServeMux
// at /debug/events.
//
// It performs authorization by running AuthRequest.
func Events(w http.ResponseWriter, req *http.Request) {
	any, sensitive := AuthRequest(req)
	if !any {
		http.Error(w, "not allowed", http.StatusUnauthorized)
		return
	}
	w.Header().Set("Content-Type", "text/html; charset=utf-8")
	RenderEvents(w, req, sensitive)
}

// Render renders the HTML page typically served at /debug/requests.
// It does not do any auth checking. The request may be nil.
//
// Most users will use the Traces handler.
func Render(w io.Writer, req *http.Request, sensitive bool) {
	data := &struct {
		Families         []string
		ActiveTraceCount map[string]int
		CompletedTraces  map[string]*family

		// Set when a bucket has been selected.
		Traces        traceList
		Family        string
		Bucket        int
		Expanded      bool
		Traced        bool
		Active        bool
		ShowSensitive bool // whether to show sensitive events

		Histogram       template.HTML
		HistogramWindow string // e.g. "last minute", "last hour", "all time"

		// If non-zero, the set of traces is a partial set,
		// and this is the total number.
		Total int
	}{
		CompletedTraces: completedTraces,
	}

	data.ShowSensitive = sensitive
	if req != nil {
		// Allow show_sensitive=0 to force hiding of sensitive data for testing.
		// This only goes one way; you can't use show_sensitive=1 to see things.
		if req.FormValue("show_sensitive") == "0" {
			data.ShowSensitive = false
		}

		if exp, err := strconv.ParseBool(req.FormValue("exp")); err == nil {
			data.Expanded = exp
		}
		if exp, err := strconv.ParseBool(req.FormValue("rtraced")); err == nil {
			data.Traced = exp
		}
	}

	completedMu.RLock()
	data.Families = make([]string, 0, len(completedTraces))
	for fam := range completedTraces {
		data.Families = append(data.Families, fam)
	}
	completedMu.RUnlock()
	sort.Strings(data.Families)

	// We are careful here to minimize the time spent locking activeMu,
	// since that lock is required every time an RPC starts and finishes.
	data.ActiveTraceCount = make(map[string]int, len(data.Families))
	activeMu.RLock()
	for fam, s := range activeTraces {
		data.ActiveTraceCount[fam] = s.Len()
	}
	activeMu.RUnlock()

	var ok bool
	data.Family, data.Bucket, ok = parseArgs(req)
	switch {
	case !ok:
		// No-op
	case data.Bucket == -1:
		data.Active = true
		n := data.ActiveTraceCount[data.Family]
		data.Traces = getActiveTraces(data.Family)
		if len(data.Traces) < n {
			data.Total = n
		}
	case data.Bucket < bucketsPerFamily:
		if b := lookupBucket(data.Family, data.Bucket); b != nil {
			data.Traces = b.Copy(data.Traced)
		}
	default:
		if f := getFamily(data.Family, false); f != nil {
			var obs timeseries.Observable
			f.LatencyMu.RLock()
			switch o := data.Bucket - bucketsPerFamily; o {
			case 0:
				obs = f.Latency.Minute()
				data.HistogramWindow = "last minute"
			case 1:
				obs = f.Latency.Hour()
				data.HistogramWindow = "last hour"
			case 2:
				obs = f.Latency.Total()
				data.HistogramWindow = "all time"
			}
			f.LatencyMu.RUnlock()
			if obs != nil {
				data.Histogram = obs.(*histogram).html()
			}
		}
	}

	if data.Traces != nil {
		defer data.Traces.Free()
		sort.Sort(data.Traces)
	}

	completedMu.RLock()
	defer completedMu.RUnlock()
	if err := pageTmpl().ExecuteTemplate(w, "Page", data); err != nil {
		log.Printf("net/trace: Failed executing template: %v", err)
	}
}

func parseArgs(req *http.Request) (fam string, b int, ok bool) {
	if req == nil {
		return "", 0, false
	}
	fam, bStr := req.FormValue("fam"), req.FormValue("b")
	if fam == "" || bStr == "" {
		return "", 0, false
	}
	b, err := strconv.Atoi(bStr)
	if err != nil || b < -1 {
		return "", 0, false
	}

	return fam, b, true
}

func lookupBucket(fam string, b int) *traceBucket {
	f := getFamily(fam, false)
	if f == nil || b < 0 || b >= len(f.Buckets) {
		return nil
	}
	return f.Buckets[b]
}

type contextKeyT string

var contextKey = contextKeyT("golang.org/x/net/trace.Trace")

// Trace represents an active request.
type Trace interface {
	// LazyLog adds x to the event log. It will be evaluated each time the
	// /debug/requests page is rendered. Any memory referenced by x will be
	// pinned until the trace is finished and later discarded.
	LazyLog(x fmt.Stringer, sensitive bool)

	// LazyPrintf evaluates its arguments with fmt.Sprintf each time the
	// /debug/requests page is rendered. Any memory referenced by a will be
	// pinned until the trace is finished and later discarded.
	LazyPrintf(format string, a ...interface{})

	// SetError declares that this trace resulted in an error.
	SetError()

	// SetRecycler sets a recycler for the trace.
	// f will be called for each event passed to LazyLog at a time when
	// it is no longer required, whether while the trace is still active
	// and the event is discarded, or when a completed trace is discarded.
	SetRecycler(f func(interface{}))

	// SetTraceInfo sets the trace info for the trace.
	// This is currently unused.
	SetTraceInfo(traceID, spanID uint64)

	// SetMaxEvents sets the maximum number of events that will be stored
	// in the trace. This has no effect if any events have already been
	// added to the trace.
	SetMaxEvents(m int)

	// Finish declares that this trace is complete.
	// The trace should not be used after calling this method.
	Finish()
}

type lazySprintf struct {
	format string
	a      []interface{}
}

func (l *lazySprintf) String() string {
	return fmt.Sprintf(l.format, l.a...)
}

// New returns a new Trace with the specified family and title.
func New(family, title string) Trace {
	tr := newTrace()
	tr.ref()
	tr.Family, tr.Title = family, title
	tr.Start = time.Now()
	tr.maxEvents = maxEventsPerTrace
	tr.events = tr.eventsBuf[:0]

	activeMu.RLock()
	s := activeTraces[tr.Family]
	activeMu.RUnlock()
	if s == nil {
		activeMu.Lock()
		s = activeTraces[tr.Family] // check again
		if s == nil {
			s = new(traceSet)
			activeTraces[tr.Family] = s
		}
		activeMu.Unlock()
	}
	s.Add(tr)

	// Trigger allocation of the completed trace structure for this family.
	// This will cause the family to be present in the request page during
	// the first trace of this family. We don't care about the return value,
	// nor is there any need for this to run inline, so we execute it in its
	// own goroutine, but only if the family isn't allocated yet.
	completedMu.RLock()
	if _, ok := completedTraces[tr.Family]; !ok {
		go allocFamily(tr.Family)
	}
	completedMu.RUnlock()

	return tr
}

func (tr *trace) Finish() {
	elapsed := time.Now().Sub(tr.Start)
	tr.mu.Lock()
	tr.Elapsed = elapsed
	tr.mu.Unlock()

	if DebugUseAfterFinish {
		buf := make([]byte, 4<<10) // 4 KB should be enough
		n := runtime.Stack(buf, false)
		tr.finishStack = buf[:n]
	}

	activeMu.RLock()
	m := activeTraces[tr.Family]
	activeMu.RUnlock()
	m.Remove(tr)

	f := getFamily(tr.Family, true)
	tr.mu.RLock() // protects tr fields in Cond.match calls
	for _, b := range f.Buckets {
		if b.Cond.match(tr) {
			b.Add(tr)
		}
	}
	tr.mu.RUnlock()

	// Add a sample of elapsed time as microseconds to the family's timeseries
	h := new(histogram)
	h.addMeasurement(elapsed.Nanoseconds() / 1e3)
	f.LatencyMu.Lock()
	f.Latency.Add(h)
	f.LatencyMu.Unlock()

	tr.unref() // matches ref in New
}

const (
	bucketsPerFamily    = 9
	tracesPerBucket     = 10
	maxActiveTraces     = 20 // Maximum number of active traces to show.
	maxEventsPerTrace   = 10
	numHistogramBuckets = 38
)

var (
	// The active traces.
	activeMu     sync.RWMutex
	activeTraces = make(map[string]*traceSet) // family -> traces

	// Families of completed traces.
	completedMu     sync.RWMutex
	completedTraces = make(map[string]*family) // family -> traces
)

type traceSet struct {
	mu sync.RWMutex
	m  map[*trace]bool

	// We could avoid the entire map scan in FirstN by having a slice of all the traces
	// ordered by start time, and an index into that from the trace struct, with a periodic
	// repack of the slice after enough traces finish; we could also use a skip list or similar.
	// However, that would shift some of the expense from /debug/requests time to RPC time,
	// which is probably the wrong trade-off.
}

func (ts *traceSet) Len() int {
	ts.mu.RLock()
	defer ts.mu.RUnlock()
	return len(ts.m)
}

func (ts *traceSet) Add(tr *trace) {
	ts.mu.Lock()
	if ts.m == nil {
		ts.m = make(map[*trace]bool)
	}
	ts.m[tr] = true
	ts.mu.Unlock()
}

func (ts *traceSet) Remove(tr *trace) {
	ts.mu.Lock()
	delete(ts.m, tr)
	ts.mu.Unlock()
}

// FirstN returns the first n traces ordered by time.
func (ts *traceSet) FirstN(n int) traceList {
	ts.mu.RLock()
	defer ts.mu.RUnlock()

	if n > len(ts.m) {
		n = len(ts.m)
	}
	trl := make(traceList, 0, n)

	// Fast path for when no selectivity is needed.
	if n == len(ts.m) {
		for tr := range ts.m {
			tr.ref()
			trl = append(trl, tr)
		}
		sort.Sort(trl)
		return trl
	}

	// Pick the oldest n traces.
	// This is inefficient. See the comment in the traceSet struct.
	for tr := range ts.m {
		// Put the first n traces into trl in the order they occur.
		// When we have n, sort trl, and thereafter maintain its order.
		if len(trl) < n {
			tr.ref()
			trl = append(trl, tr)
			if len(trl) == n {
				// This is guaranteed to happen exactly once during this loop.
				sort.Sort(trl)
			}
			continue
		}
		if tr.Start.After(trl[n-1].Start) {
			continue
		}

		// Find where to insert this one.
		tr.ref()
		i := sort.Search(n, func(i int) bool { return trl[i].Start.After(tr.Start) })
		trl[n-1].unref()
		copy(trl[i+1:], trl[i:])
		trl[i] = tr
	}

	return trl
}

func getActiveTraces(fam string) traceList {
	activeMu.RLock()
	s := activeTraces[fam]
	activeMu.RUnlock()
	if s == nil {
		return nil
	}
	return s.FirstN(maxActiveTraces)
}

func getFamily(fam string, allocNew bool) *family {
	completedMu.RLock()
	f := completedTraces[fam]
	completedMu.RUnlock()
	if f == nil && allocNew {
		f = allocFamily(fam)
	}
	return f
}

func allocFamily(fam string) *family {
	completedMu.Lock()
	defer completedMu.Unlock()
	f := completedTraces[fam]
	if f == nil {
		f = newFamily()
		completedTraces[fam] = f
	}
	return f
}

// family represents a set of trace buckets and associated latency information.
type family struct {
	// traces may occur in multiple buckets.
	Buckets [bucketsPerFamily]*traceBucket

	// latency time series
	LatencyMu sync.RWMutex
	Latency   *timeseries.MinuteHourSeries
}

func newFamily() *family {
	return &family{
		Buckets: [bucketsPerFamily]*traceBucket{
			{Cond: minCond(0)},
			{Cond: minCond(50 * time.Millisecond)},
			{Cond: minCond(100 * time.Millisecond)},
			{Cond: minCond(200 * time.Millisecond)},
			{Cond: minCond(500 * time.Millisecond)},
			{Cond: minCond(1 * time.Second)},
			{Cond: minCond(10 * time.Second)},
			{Cond: minCond(100 * time.Second)},
			{Cond: errorCond{}},
		},
		Latency: timeseries.NewMinuteHourSeries(func() timeseries.Observable { return new(histogram) }),
	}
}

// traceBucket represents a size-capped bucket of historic traces,
// along with a condition for a trace to belong to the bucket.
type traceBucket struct {
	Cond cond

	// Ring buffer implementation of a fixed-size FIFO queue.
	mu     sync.RWMutex
	buf    [tracesPerBucket]*trace
	start  int // < tracesPerBucket
	length int // <= tracesPerBucket
}

func (b *traceBucket) Add(tr *trace) {
	b.mu.Lock()
	defer b.mu.Unlock()

	i := b.start + b.length
	if i >= tracesPerBucket {
		i -= tracesPerBucket
	}
	if b.length == tracesPerBucket {
		// "Remove" an element from the bucket.
		b.buf[i].unref()
		b.start++
		if b.start == tracesPerBucket {
			b.start = 0
		}
	}
	b.buf[i] = tr
	if b.length < tracesPerBucket {
		b.length++
	}
	tr.ref()
}

// Copy returns a copy of the traces in the bucket.
// If tracedOnly is true, only the traces with trace information will be returned.
// The logs will be ref'd before returning; the caller should call
// the Free method when it is done with them.
// TODO(dsymonds): keep track of traced requests in separate buckets.
func (b *traceBucket) Copy(tracedOnly bool) traceList {
	b.mu.RLock()
	defer b.mu.RUnlock()

	trl := make(traceList, 0, b.length)
	for i, x := 0, b.start; i < b.length; i++ {
		tr := b.buf[x]
		if !tracedOnly || tr.spanID != 0 {
			tr.ref()
			trl = append(trl, tr)
		}
		x++
		if x == b.length {
			x = 0
		}
	}
	return trl
}

func (b *traceBucket) Empty() bool {
	b.mu.RLock()
	defer b.mu.RUnlock()
	return b.length == 0
}

// cond represents a condition on a trace.
type cond interface {
	match(t *trace) bool
	String() string
}

type minCond time.Duration

func (m minCond) match(t *trace) bool { return t.Elapsed >= time.Duration(m) }
func (m minCond) String() string      { return fmt.Sprintf("≥%gs", time.Duration(m).Seconds()) }

type errorCond struct{}

func (e errorCond) match(t *trace) bool { return t.IsError }
func (e errorCond) String() string      { return "errors" }

type traceList []*trace

// Free calls unref on each element of the list.
func (trl traceList) Free() {
	for _, t := range trl {
		t.unref()
	}
}

// traceList may be sorted in reverse chronological order.
func (trl traceList) Len() int           { return len(trl) }
func (trl traceList) Less(i, j int) bool { return trl[i].Start.After(trl[j].Start) }
func (trl traceList) Swap(i, j int)      { trl[i], trl[j] = trl[j], trl[i] }

// An event is a timestamped log entry in a trace.
type event struct {
	When       time.Time
	Elapsed    time.Duration // since previous event in trace
	NewDay     bool          // whether this event is on a different day to the previous event
	Recyclable bool          // whether this event was passed via LazyLog
	Sensitive  bool          // whether this event contains sensitive information
	What       interface{}   // string or fmt.Stringer
}

// WhenString returns a string representation of the elapsed time of the event.
// It will include the date if midnight was crossed.
func (e event) WhenString() string {
	if e.NewDay {
		return e.When.Format("2006/01/02 15:04:05.000000")
	}
	return e.When.Format("15:04:05.000000")
}

// discarded represents a number of discarded events.
// It is stored as *discarded to make it easier to update in-place.
type discarded int

func (d *discarded) String() string {
	return fmt.Sprintf("(%d events discarded)", int(*d))
}

// trace represents an active or complete request,
// either sent or received by this program.
type trace struct {
	// Family is the top-level grouping of traces to which this belongs.
	Family string

	// Title is the title of this trace.
	Title string

	// Start time of the this trace.
	Start time.Time

	mu        sync.RWMutex
	events    []event // Append-only sequence of events (modulo discards).
	maxEvents int
	recycler  func(interface{})
	IsError   bool          // Whether this trace resulted in an error.
	Elapsed   time.Duration // Elapsed time for this trace, zero while active.
	traceID   uint64        // Trace information if non-zero.
	spanID    uint64

	refs int32     // how many buckets this is in
	disc discarded // scratch space to avoid allocation

	finishStack []byte // where finish was called, if DebugUseAfterFinish is set

	eventsBuf [4]event // preallocated buffer in case we only log a few events
}

func (tr *trace) reset() {
	// Clear all but the mutex. Mutexes may not be copied, even when unlocked.
	tr.Family = ""
	tr.Title = ""
	tr.Start = time.Time{}

	tr.mu.Lock()
	tr.Elapsed = 0
	tr.traceID = 0
	tr.spanID = 0
	tr.IsError = false
	tr.maxEvents = 0
	tr.events = nil
	tr.recycler = nil
	tr.mu.Unlock()

	tr.refs = 0
	tr.disc = 0
	tr.finishStack = nil
	for i := range tr.eventsBuf {
		tr.eventsBuf[i] = event{}
	}
}

// delta returns the elapsed time since the last event or the trace start,
// and whether it spans midnight.
// L >= tr.mu
func (tr *trace) delta(t time.Time) (time.Duration, bool) {
	if len(tr.events) == 0 {
		return t.Sub(tr.Start), false
	}
	prev := tr.events[len(tr.events)-1].When
	return t.Sub(prev), prev.Day() != t.Day()
}

func (tr *trace) addEvent(x interface{}, recyclable, sensitive bool) {
	if DebugUseAfterFinish && tr.finishStack != nil {
		buf := make([]byte, 4<<10) // 4 KB should be enough
		n := runtime.Stack(buf, false)
		log.Printf("net/trace: trace used after finish:\nFinished at:\n%s\nUsed at:\n%s", tr.finishStack, buf[:n])
	}

	/*
		NOTE TO DEBUGGERS

		If you are here because your program panicked in this code,
		it is almost definitely the fault of code using this package,
		and very unlikely to be the fault of this code.

		The most likely scenario is that some code elsewhere is using
		a trace.Trace after its Finish method is called.
		You can temporarily set the DebugUseAfterFinish var
		to help discover where that is; do not leave that var set,
		since it makes this package much less efficient.
	*/

	e := event{When: time.Now(), What: x, Recyclable: recyclable, Sensitive: sensitive}
	tr.mu.Lock()
	e.Elapsed, e.NewDay = tr.delta(e.When)
	if len(tr.events) < tr.maxEvents {
		tr.events = append(tr.events, e)
	} else {
		// Discard the middle events.
		di := int((tr.maxEvents - 1) / 2)
		if d, ok := tr.events[di].What.(*discarded); ok {
			(*d)++
		} else {
			// disc starts at two to count for the event it is replacing,
			// plus the next one that we are about to drop.
			tr.disc = 2
			if tr.recycler != nil && tr.events[di].Recyclable {
				go tr.recycler(tr.events[di].What)
			}
			tr.events[di].What = &tr.disc
		}
		// The timestamp of the discarded meta-event should be
		// the time of the last event it is representing.
		tr.events[di].When = tr.events[di+1].When

		if tr.recycler != nil && tr.events[di+1].Recyclable {
			go tr.recycler(tr.events[di+1].What)
		}
		copy(tr.events[di+1:], tr.events[di+2:])
		tr.events[tr.maxEvents-1] = e
	}
	tr.mu.Unlock()
}

func (tr *trace) LazyLog(x fmt.Stringer, sensitive bool) {
	tr.addEvent(x, true, sensitive)
}

func (tr *trace) LazyPrintf(format string, a ...interface{}) {
	tr.addEvent(&lazySprintf{format, a}, false, false)
}

func (tr *trace) SetError() {
	tr.mu.Lock()
	tr.IsError = true
	tr.mu.Unlock()
}

func (tr *trace) SetRecycler(f func(interface{})) {
	tr.mu.Lock()
	tr.recycler = f
	tr.mu.Unlock()
}

func (tr *trace) SetTraceInfo(traceID, spanID uint64) {
	tr.mu.Lock()
	tr.traceID, tr.spanID = traceID, spanID
	tr.mu.Unlock()
}

func (tr *trace) SetMaxEvents(m int) {
	tr.mu.Lock()
	// Always keep at least three events: first, discarded count, last.
	if len(tr.events) == 0 && m > 3 {
		tr.maxEvents = m
	}
	tr.mu.Unlock()
}

func (tr *trace) ref() {
	atomic.AddInt32(&tr.refs, 1)
}

func (tr *trace) unref() {
	if atomic.AddInt32(&tr.refs, -1) == 0 {
		tr.mu.RLock()
		if tr.recycler != nil {
			// freeTrace clears tr, so we hold tr.recycler and tr.events here.
			go func(f func(interface{}), es []event) {
				for _, e := range es {
					if e.Recyclable {
						f(e.What)
					}
				}
			}(tr.recycler, tr.events)
		}
		tr.mu.RUnlock()

		freeTrace(tr)
	}
}

func (tr *trace) When() string {
	return tr.Start.Format("2006/01/02 15:04:05.000000")
}

func (tr *trace) ElapsedTime() string {
	tr.mu.RLock()
	t := tr.Elapsed
	tr.mu.RUnlock()

	if t == 0 {
		// Active trace.
		t = time.Since(tr.Start)
	}
	return fmt.Sprintf("%.6f", t.Seconds())
}

func (tr *trace) Events() []event {
	tr.mu.RLock()
	defer tr.mu.RUnlock()
	return tr.events
}

var traceFreeList = make(chan *trace, 1000) // TODO(dsymonds): Use sync.Pool?

// newTrace returns a trace ready to use.
func newTrace() *trace {
	select {
	case tr := <-traceFreeList:
		return tr
	default:
		return new(trace)
	}
}

// freeTrace adds tr to traceFreeList if there's room.
// This is non-blocking.
func freeTrace(tr *trace) {
	if DebugUseAfterFinish {
		return // never reuse
	}
	tr.reset()
	select {
	case traceFreeList <- tr:
	default:
	}
}

func elapsed(d time.Duration) string {
	b := []byte(fmt.Sprintf("%.6f", d.Seconds()))

	// For subsecond durations, blank all zeros before decimal point,
	// and all zeros between the decimal point and the first non-zero digit.
	if d < time.Second {
		dot := bytes.IndexByte(b, '.')
		for i := 0; i < dot; i++ {
			b[i] = ' '
		}
		for i := dot + 1; i < len(b); i++ {
			if b[i] == '0' {
				b[i] = ' '
			} else {
				break
			}
		}
	}

	return string(b)
}

var pageTmplCache *template.Template
var pageTmplOnce sync.Once

func pageTmpl() *template.Template {
	pageTmplOnce.Do(func() {
		pageTmplCache = template.Must(template.New("Page").Funcs(template.FuncMap{
			"elapsed": elapsed,
			"add":     func(a, b int) int { return a + b },
		}).Parse(pageHTML))
	})
	return pageTmplCache
}

const pageHTML = `
{{template "Prolog" .}}
{{template "StatusTable" .}}
{{template "Epilog" .}}

{{define "Prolog"}}
<html>
	<head>
	<title>/debug/requests</title>
	<style type="text/css">
		body {
			font-family: sans-serif;
		}
		table#tr-status td.family {
			padding-right: 2em;
		}
		table#tr-status td.active {
			padding-right: 1em;
		}
		table#tr-status td.latency-first {
			padding-left: 1em;
		}
		table#tr-status td.empty {
			color: #aaa;
		}
		table#reqs {
			margin-top: 1em;
		}
		table#reqs tr.first {
			{{if $.Expanded}}font-weight: bold;{{end}}
		}
		table#reqs td {
			font-family: monospace;
		}
		table#reqs td.when {
			text-align: right;
			white-space: nowrap;
		}
		table#reqs td.elapsed {
			padding: 0 0.5em;
			text-align: right;
			white-space: pre;
			width: 10em;
		}
		address {
			font-size: smaller;
			margin-top: 5em;
		}
	</style>
	</head>
	<body>

<h1>/debug/requests</h1>
{{end}} {{/* end of Prolog */}}

{{define "StatusTable"}}
<table id="tr-status">
	{{range $fam := .Families}}
	<tr>
		<td class="family">{{$fam}}</td>

		{{$n := index $.ActiveTraceCount $fam}}
		<td class="active {{if not $n}}empty{{end}}">
			{{if $n}}<a href="?fam={{$fam}}&b=-1{{if $.Expanded}}&exp=1{{end}}">{{end}}
			[{{$n}} active]
			{{if $n}}</a>{{end}}
		</td>

		{{$f := index $.CompletedTraces $fam}}
		{{range $i, $b := $f.Buckets}}
		{{$empty := $b.Empty}}
		<td {{if $empty}}class="empty"{{end}}>
		{{if not $empty}}<a href="?fam={{$fam}}&b={{$i}}{{if $.Expanded}}&exp=1{{end}}">{{end}}
		[{{.Cond}}]
		{{if not $empty}}</a>{{end}}
		</td>
		{{end}}

		{{$nb := len $f.Buckets}}
		<td class="latency-first">
		<a href="?fam={{$fam}}&b={{$nb}}">[minute]</a>
		</td>
		<td>
		<a href="?fam={{$fam}}&b={{add $nb 1}}">[hour]</a>
		</td>
		<td>
		<a href="?fam={{$fam}}&b={{add $nb 2}}">[total]</a>
		</td>

	</tr>
	{{end}}
</table>
{{end}} {{/* end of StatusTable */}}

{{define "Epilog"}}
{{if $.Traces}}
<hr />
<h3>Family: {{$.Family}}</h3>

{{if or $.Expanded $.Traced}}
  <a href="?fam={{$.Family}}&b={{$.Bucket}}">[Normal/Summary]</a>
{{else}}
  [Normal/Summary]
{{end}}

{{if or (not $.Expanded) $.Traced}}
  <a href="?fam={{$.Family}}&b={{$.Bucket}}&exp=1">[Normal/Expanded]</a>
{{else}}
  [Normal/Expanded]
{{end}}

{{if not $.Active}}
	{{if or $.Expanded (not $.Traced)}}
	<a href="?fam={{$.Family}}&b={{$.Bucket}}&rtraced=1">[Traced/Summary]</a>
	{{else}}
	[Traced/Summary]
	{{end}}
	{{if or (not $.Expanded) (not $.Traced)}}
	<a href="?fam={{$.Family}}&b={{$.Bucket}}&exp=1&rtraced=1">[Traced/Expanded]</a>
        {{else}}
	[Traced/Expanded]
	{{end}}
{{end}}

{{if $.Total}}
<p><em>Showing <b>{{len $.Traces}}</b> of <b>{{$.Total}}</b> traces.</em></p>
{{end}}

<table id="reqs">
	<caption>
		{{if $.Active}}Active{{else}}Completed{{end}} Requests
	</caption>
	<tr><th>When</th><th>Elapsed (s)</th></tr>
	{{range $tr := $.Traces}}
	<tr class="first">
		<td class="when">{{$tr.When}}</td>
		<td class="elapsed">{{$tr.ElapsedTime}}</td>
		<td>{{$tr.Title}}</td>
		{{/* TODO: include traceID/spanID */}}
	</tr>
	{{if $.Expanded}}
	{{range $tr.Events}}
	<tr>
		<td class="when">{{.WhenString}}</td>
		<td class="elapsed">{{elapsed .Elapsed}}</td>
		<td>{{if or $.ShowSensitive (not .Sensitive)}}... {{.What}}{{else}}<em>[redacted]</em>{{end}}</td>
	</tr>
	{{end}}
	{{end}}
	{{end}}
</table>
{{end}} {{/* if $.Traces */}}

{{if $.Histogram}}
<h4>Latency (µs) of {{$.Family}} over {{$.HistogramWindow}}</h4>
{{$.Histogram}}
{{end}} {{/* if $.Histogram */}}

	</body>
</html>
{{end}} {{/* end of Epilog */}}
`


text:
// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package trace

import (
	"math"
	"testing"
)

type sumTest struct {
	value        int64
	sum          int64
	sumOfSquares float64
	total        int64
}

var sumTests = []sumTest{
	{100, 100, 10000, 1},
	{50, 150, 12500, 2},
	{50, 200, 15000, 3},
	{50, 250, 17500, 4},
}

type bucketingTest struct {
	in     int64
	log    int
	bucket int
}

var bucketingTests = []bucketingTest{
	{0, 0, 0},
	{1, 1, 0},
	{2, 2, 1},
	{3, 2, 1},
	{4, 3, 2},
	{1000, 10, 9},
	{1023, 10, 9},
	{1024, 11, 10},
	{1000000, 20, 19},
}

type multiplyTest struct {
	in                   int64
	ratio                float64
	expectedSum          int64
	expectedTotal        int64
	expectedSumOfSquares float64
}

var multiplyTests = []multiplyTest{
	{15, 2.5, 37, 2, 562.5},
	{128, 4.6, 758, 13, 77953.9},
}

type percentileTest struct {
	fraction float64
	expected int64
}

var percentileTests = []percentileTest{
	{0.25, 48},
	{0.5, 96},
	{0.6, 109},
	{0.75, 128},
	{0.90, 205},
	{0.95, 230},
	{0.99, 256},
}

func TestSum(t *testing.T) {
	var h histogram

	for _, test := range sumTests {
		h.addMeasurement(test.value)
		sum := h.sum
		if sum != test.sum {
			t.Errorf("h.Sum = %v WANT: %v", sum, test.sum)
		}

		sumOfSquares := h.sumOfSquares
		if sumOfSquares != test.sumOfSquares {
			t.Errorf("h.SumOfSquares = %v WANT: %v", sumOfSquares, test.sumOfSquares)
		}

		total := h.total()
		if total != test.total {
			t.Errorf("h.Total = %v WANT: %v", total, test.total)
		}
	}
}

func TestMultiply(t *testing.T) {
	var h histogram
	for i, test := range multiplyTests {
		h.addMeasurement(test.in)
		h.Multiply(test.ratio)
		if h.sum != test.expectedSum {
			t.Errorf("#%v: h.sum = %v WANT: %v", i, h.sum, test.expectedSum)
		}
		if h.total() != test.expectedTotal {
			t.Errorf("#%v: h.total = %v WANT: %v", i, h.total(), test.expectedTotal)
		}
		if h.sumOfSquares != test.expectedSumOfSquares {
			t.Errorf("#%v: h.SumOfSquares = %v WANT: %v", i, test.expectedSumOfSquares, h.sumOfSquares)
		}
	}
}

func TestBucketingFunctions(t *testing.T) {
	for _, test := range bucketingTests {
		log := log2(test.in)
		if log != test.log {
			t.Errorf("log2 = %v WANT: %v", log, test.log)
		}

		bucket := getBucket(test.in)
		if bucket != test.bucket {
			t.Errorf("getBucket = %v WANT: %v", bucket, test.bucket)
		}
	}
}

func TestAverage(t *testing.T) {
	a := new(histogram)
	average := a.average()
	if average != 0 {
		t.Errorf("Average of empty histogram was %v WANT: 0", average)
	}

	a.addMeasurement(1)
	a.addMeasurement(1)
	a.addMeasurement(3)
	const expected = float64(5) / float64(3)
	average = a.average()

	if !isApproximate(average, expected) {
		t.Errorf("Average = %g WANT: %v", average, expected)
	}
}

func TestStandardDeviation(t *testing.T) {
	a := new(histogram)
	add(a, 10, 1<<4)
	add(a, 10, 1<<5)
	add(a, 10, 1<<6)
	stdDev := a.standardDeviation()
	const expected = 19.95

	if !isApproximate(stdDev, expected) {
		t.Errorf("StandardDeviation = %v WANT: %v", stdDev, expected)
	}

	// No values
	a = new(histogram)
	stdDev = a.standardDeviation()

	if !isApproximate(stdDev, 0) {
		t.Errorf("StandardDeviation = %v WANT: 0", stdDev)
	}

	add(a, 1, 1<<4)
	if !isApproximate(stdDev, 0) {
		t.Errorf("StandardDeviation = %v WANT: 0", stdDev)
	}

	add(a, 10, 1<<4)
	if !isApproximate(stdDev, 0) {
		t.Errorf("StandardDeviation = %v WANT: 0", stdDev)
	}
}

func TestPercentileBoundary(t *testing.T) {
	a := new(histogram)
	add(a, 5, 1<<4)
	add(a, 10, 1<<6)
	add(a, 5, 1<<7)

	for _, test := range percentileTests {
		percentile := a.percentileBoundary(test.fraction)
		if percentile != test.expected {
			t.Errorf("h.PercentileBoundary (fraction=%v) = %v WANT: %v", test.fraction, percentile, test.expected)
		}
	}
}

func TestCopyFrom(t *testing.T) {
	a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
		19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}
	b := histogram{6, 36, []int64{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
		20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39}, 5, -1}

	a.CopyFrom(&b)

	if a.String() != b.String() {
		t.Errorf("a.String = %s WANT: %s", a.String(), b.String())
	}
}

func TestClear(t *testing.T) {
	a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
		19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}

	a.Clear()

	expected := "0, 0.000000, 0, 0, []"
	if a.String() != expected {
		t.Errorf("a.String = %s WANT %s", a.String(), expected)
	}
}

func TestNew(t *testing.T) {
	a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
		19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}
	b := a.New()

	expected := "0, 0.000000, 0, 0, []"
	if b.(*histogram).String() != expected {
		t.Errorf("b.(*histogram).String = %s WANT: %s", b.(*histogram).String(), expected)
	}
}

func TestAdd(t *testing.T) {
	// The tests here depend on the associativity of addMeasurement and Add.
	// Add empty observation
	a := histogram{5, 25, []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
		19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}, 4, -1}
	b := a.New()

	expected := a.String()
	a.Add(b)
	if a.String() != expected {
		t.Errorf("a.String = %s WANT: %s", a.String(), expected)
	}

	// Add same bucketed value, no new buckets
	c := new(histogram)
	d := new(histogram)
	e := new(histogram)
	c.addMeasurement(12)
	d.addMeasurement(11)
	e.addMeasurement(12)
	e.addMeasurement(11)
	c.Add(d)
	if c.String() != e.String() {
		t.Errorf("c.String = %s WANT: %s", c.String(), e.String())
	}

	// Add bucketed values
	f := new(histogram)
	g := new(histogram)
	h := new(histogram)
	f.addMeasurement(4)
	f.addMeasurement(12)
	f.addMeasurement(100)
	g.addMeasurement(18)
	g.addMeasurement(36)
	g.addMeasurement(255)
	h.addMeasurement(4)
	h.addMeasurement(12)
	h.addMeasurement(100)
	h.addMeasurement(18)
	h.addMeasurement(36)
	h.addMeasurement(255)
	f.Add(g)
	if f.String() != h.String() {
		t.Errorf("f.String = %q WANT: %q", f.String(), h.String())
	}

	// add buckets to no buckets
	i := new(histogram)
	j := new(histogram)
	k := new(histogram)
	j.addMeasurement(18)
	j.addMeasurement(36)
	j.addMeasurement(255)
	k.addMeasurement(18)
	k.addMeasurement(36)
	k.addMeasurement(255)
	i.Add(j)
	if i.String() != k.String() {
		t.Errorf("i.String = %q WANT: %q", i.String(), k.String())
	}

	// add buckets to single value (no overlap)
	l := new(histogram)
	m := new(histogram)
	n := new(histogram)
	l.addMeasurement(0)
	m.addMeasurement(18)
	m.addMeasurement(36)
	m.addMeasurement(255)
	n.addMeasurement(0)
	n.addMeasurement(18)
	n.addMeasurement(36)
	n.addMeasurement(255)
	l.Add(m)
	if l.String() != n.String() {
		t.Errorf("l.String = %q WANT: %q", l.String(), n.String())
	}

	// mixed order
	o := new(histogram)
	p := new(histogram)
	o.addMeasurement(0)
	o.addMeasurement(2)
	o.addMeasurement(0)
	p.addMeasurement(0)
	p.addMeasurement(0)
	p.addMeasurement(2)
	if o.String() != p.String() {
		t.Errorf("o.String = %q WANT: %q", o.String(), p.String())
	}
}

func add(h *histogram, times int, val int64) {
	for i := 0; i < times; i++ {
		h.addMeasurement(val)
	}
}

func isApproximate(x, y float64) bool {
	return math.Abs(x-y) < 1e-2
}


text:
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// +build !go1.7

package trace

import "golang.org/x/net/context"

// NewContext returns a copy of the parent context
// and associates it with a Trace.
func NewContext(ctx context.Context, tr Trace) context.Context {
	return context.WithValue(ctx, contextKey, tr)
}

// FromContext returns the Trace bound to the context, if any.
func FromContext(ctx context.Context) (tr Trace, ok bool) {
	tr, ok = ctx.Value(contextKey).(Trace)
	return
}


text:
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package bpf

import (
	"fmt"
	"io/ioutil"
	"reflect"
	"strconv"
	"strings"
	"testing"
)

// This is a direct translation of the program in
// testdata/all_instructions.txt.
var allInstructions = []Instruction{
	LoadConstant{Dst: RegA, Val: 42},
	LoadConstant{Dst: RegX, Val: 42},

	LoadScratch{Dst: RegA, N: 3},
	LoadScratch{Dst: RegX, N: 3},

	LoadAbsolute{Off: 42, Size: 1},
	LoadAbsolute{Off: 42, Size: 2},
	LoadAbsolute{Off: 42, Size: 4},

	LoadIndirect{Off: 42, Size: 1},
	LoadIndirect{Off: 42, Size: 2},
	LoadIndirect{Off: 42, Size: 4},

	LoadMemShift{Off: 42},

	LoadExtension{Num: ExtLen},
	LoadExtension{Num: ExtProto},
	LoadExtension{Num: ExtType},
	LoadExtension{Num: ExtRand},

	StoreScratch{Src: RegA, N: 3},
	StoreScratch{Src: RegX, N: 3},

	ALUOpConstant{Op: ALUOpAdd, Val: 42},
	ALUOpConstant{Op: ALUOpSub, Val: 42},
	ALUOpConstant{Op: ALUOpMul, Val: 42},
	ALUOpConstant{Op: ALUOpDiv, Val: 42},
	ALUOpConstant{Op: ALUOpOr, Val: 42},
	ALUOpConstant{Op: ALUOpAnd, Val: 42},
	ALUOpConstant{Op: ALUOpShiftLeft, Val: 42},
	ALUOpConstant{Op: ALUOpShiftRight, Val: 42},
	ALUOpConstant{Op: ALUOpMod, Val: 42},
	ALUOpConstant{Op: ALUOpXor, Val: 42},

	ALUOpX{Op: ALUOpAdd},
	ALUOpX{Op: ALUOpSub},
	ALUOpX{Op: ALUOpMul},
	ALUOpX{Op: ALUOpDiv},
	ALUOpX{Op: ALUOpOr},
	ALUOpX{Op: ALUOpAnd},
	ALUOpX{Op: ALUOpShiftLeft},
	ALUOpX{Op: ALUOpShiftRight},
	ALUOpX{Op: ALUOpMod},
	ALUOpX{Op: ALUOpXor},

	NegateA{},

	Jump{Skip: 10},
	JumpIf{Cond: JumpEqual, Val: 42, SkipTrue: 8, SkipFalse: 9},
	JumpIf{Cond: JumpNotEqual, Val: 42, SkipTrue: 8},
	JumpIf{Cond: JumpLessThan, Val: 42, SkipTrue: 7},
	JumpIf{Cond: JumpLessOrEqual, Val: 42, SkipTrue: 6},
	JumpIf{Cond: JumpGreaterThan, Val: 42, SkipTrue: 4, SkipFalse: 5},
	JumpIf{Cond: JumpGreaterOrEqual, Val: 42, SkipTrue: 3, SkipFalse: 4},
	JumpIf{Cond: JumpBitsSet, Val: 42, SkipTrue: 2, SkipFalse: 3},

	TAX{},
	TXA{},

	RetA{},
	RetConstant{Val: 42},
}
var allInstructionsExpected = "testdata/all_instructions.bpf"

// Check that we produce the same output as the canonical bpf_asm
// linux kernel tool.
func TestInterop(t *testing.T) {
	out, err := Assemble(allInstructions)
	if err != nil {
		t.Fatalf("assembly of allInstructions program failed: %s", err)
	}
	t.Logf("Assembled program is %d instructions long", len(out))

	bs, err := ioutil.ReadFile(allInstructionsExpected)
	if err != nil {
		t.Fatalf("reading %s: %s", allInstructionsExpected, err)
	}
	// First statement is the number of statements, last statement is
	// empty. We just ignore both and rely on slice length.
	stmts := strings.Split(string(bs), ",")
	if len(stmts)-2 != len(out) {
		t.Fatalf("test program lengths don't match: %s has %d, Go implementation has %d", allInstructionsExpected, len(stmts)-2, len(allInstructions))
	}

	for i, stmt := range stmts[1 : len(stmts)-2] {
		nums := strings.Split(stmt, " ")
		if len(nums) != 4 {
			t.Fatalf("malformed instruction %d in %s: %s", i+1, allInstructionsExpected, stmt)
		}

		actual := out[i]

		op, err := strconv.ParseUint(nums[0], 10, 16)
		if err != nil {
			t.Fatalf("malformed opcode %s in instruction %d of %s", nums[0], i+1, allInstructionsExpected)
		}
		if actual.Op != uint16(op) {
			t.Errorf("opcode mismatch on instruction %d (%#v): got 0x%02x, want 0x%02x", i+1, allInstructions[i], actual.Op, op)
		}

		jt, err := strconv.ParseUint(nums[1], 10, 8)
		if err != nil {
			t.Fatalf("malformed jt offset %s in instruction %d of %s", nums[1], i+1, allInstructionsExpected)
		}
		if actual.Jt != uint8(jt) {
			t.Errorf("jt mismatch on instruction %d (%#v): got %d, want %d", i+1, allInstructions[i], actual.Jt, jt)
		}

		jf, err := strconv.ParseUint(nums[2], 10, 8)
		if err != nil {
			t.Fatalf("malformed jf offset %s in instruction %d of %s", nums[2], i+1, allInstructionsExpected)
		}
		if actual.Jf != uint8(jf) {
			t.Errorf("jf mismatch on instruction %d (%#v): got %d, want %d", i+1, allInstructions[i], actual.Jf, jf)
		}

		k, err := strconv.ParseUint(nums[3], 10, 32)
		if err != nil {
			t.Fatalf("malformed constant %s in instruction %d of %s", nums[3], i+1, allInstructionsExpected)
		}
		if actual.K != uint32(k) {
			t.Errorf("constant mismatch on instruction %d (%#v): got %d, want %d", i+1, allInstructions[i], actual.K, k)
		}
	}
}

// Check that assembly and disassembly match each other.
func TestAsmDisasm(t *testing.T) {
	prog1, err := Assemble(allInstructions)
	if err != nil {
		t.Fatalf("assembly of allInstructions program failed: %s", err)
	}
	t.Logf("Assembled program is %d instructions long", len(prog1))

	got, allDecoded := Disassemble(prog1)
	if !allDecoded {
		t.Errorf("Disassemble(Assemble(allInstructions)) produced unrecognized instructions:")
		for i, inst := range got {
			if r, ok := inst.(RawInstruction); ok {
				t.Logf("  insn %d, %#v --> %#v", i+1, allInstructions[i], r)
			}
		}
	}

	if len(allInstructions) != len(got) {
		t.Fatalf("disassembly changed program size: %d insns before, %d insns after", len(allInstructions), len(got))
	}
	if !reflect.DeepEqual(allInstructions, got) {
		t.Errorf("program mutated by disassembly:")
		for i := range got {
			if !reflect.DeepEqual(allInstructions[i], got[i]) {
				t.Logf("  insn %d, s: %#v, p1: %#v, got: %#v", i+1, allInstructions[i], prog1[i], got[i])
			}
		}
	}
}

type InvalidInstruction struct{}

func (a InvalidInstruction) Assemble() (RawInstruction, error) {
	return RawInstruction{}, fmt.Errorf("Invalid Instruction")
}

func (a InvalidInstruction) String() string {
	return fmt.Sprintf("unknown instruction: %#v", a)
}

func TestString(t *testing.T) {
	testCases := []struct {
		instruction Instruction
		assembler   string
	}{
		{
			instruction: LoadConstant{Dst: RegA, Val: 42},
			assembler:   "ld #42",
		},
		{
			instruction: LoadConstant{Dst: RegX, Val: 42},
			assembler:   "ldx #42",
		},
		{
			instruction: LoadConstant{Dst: 0xffff, Val: 42},
			assembler:   "unknown instruction: bpf.LoadConstant{Dst:0xffff, Val:0x2a}",
		},
		{
			instruction: LoadScratch{Dst: RegA, N: 3},
			assembler:   "ld M[3]",
		},
		{
			instruction: LoadScratch{Dst: RegX, N: 3},
			assembler:   "ldx M[3]",
		},
		{
			instruction: LoadScratch{Dst: 0xffff, N: 3},
			assembler:   "unknown instruction: bpf.LoadScratch{Dst:0xffff, N:3}",
		},
		{
			instruction: LoadAbsolute{Off: 42, Size: 1},
			assembler:   "ldb [42]",
		},
		{
			instruction: LoadAbsolute{Off: 42, Size: 2},
			assembler:   "ldh [42]",
		},
		{
			instruction: LoadAbsolute{Off: 42, Size: 4},
			assembler:   "ld [42]",
		},
		{
			instruction: LoadAbsolute{Off: 42, Size: -1},
			assembler:   "unknown instruction: bpf.LoadAbsolute{Off:0x2a, Size:-1}",
		},
		{
			instruction: LoadIndirect{Off: 42, Size: 1},
			assembler:   "ldb [x + 42]",
		},
		{
			instruction: LoadIndirect{Off: 42, Size: 2},
			assembler:   "ldh [x + 42]",
		},
		{
			instruction: LoadIndirect{Off: 42, Size: 4},
			assembler:   "ld [x + 42]",
		},
		{
			instruction: LoadIndirect{Off: 42, Size: -1},
			assembler:   "unknown instruction: bpf.LoadIndirect{Off:0x2a, Size:-1}",
		},
		{
			instruction: LoadMemShift{Off: 42},
			assembler:   "ldx 4*([42]&0xf)",
		},
		{
			instruction: LoadExtension{Num: ExtLen},
			assembler:   "ld #len",
		},
		{
			instruction: LoadExtension{Num: ExtProto},
			assembler:   "ld #proto",
		},
		{
			instruction: LoadExtension{Num: ExtType},
			assembler:   "ld #type",
		},
		{
			instruction: LoadExtension{Num: ExtPayloadOffset},
			assembler:   "ld #poff",
		},
		{
			instruction: LoadExtension{Num: ExtInterfaceIndex},
			assembler:   "ld #ifidx",
		},
		{
			instruction: LoadExtension{Num: ExtNetlinkAttr},
			assembler:   "ld #nla",
		},
		{
			instruction: LoadExtension{Num: ExtNetlinkAttrNested},
			assembler:   "ld #nlan",
		},
		{
			instruction: LoadExtension{Num: ExtMark},
			assembler:   "ld #mark",
		},
		{
			instruction: LoadExtension{Num: ExtQueue},
			assembler:   "ld #queue",
		},
		{
			instruction: LoadExtension{Num: ExtLinkLayerType},
			assembler:   "ld #hatype",
		},
		{
			instruction: LoadExtension{Num: ExtRXHash},
			assembler:   "ld #rxhash",
		},
		{
			instruction: LoadExtension{Num: ExtCPUID},
			assembler:   "ld #cpu",
		},
		{
			instruction: LoadExtension{Num: ExtVLANTag},
			assembler:   "ld #vlan_tci",
		},
		{
			instruction: LoadExtension{Num: ExtVLANTagPresent},
			assembler:   "ld #vlan_avail",
		},
		{
			instruction: LoadExtension{Num: ExtVLANProto},
			assembler:   "ld #vlan_tpid",
		},
		{
			instruction: LoadExtension{Num: ExtRand},
			assembler:   "ld #rand",
		},
		{
			instruction: LoadAbsolute{Off: 0xfffff038, Size: 4},
			assembler:   "ld #rand",
		},
		{
			instruction: LoadExtension{Num: 0xfff},
			assembler:   "unknown instruction: bpf.LoadExtension{Num:4095}",
		},
		{
			instruction: StoreScratch{Src: RegA, N: 3},
			assembler:   "st M[3]",
		},
		{
			instruction: StoreScratch{Src: RegX, N: 3},
			assembler:   "stx M[3]",
		},
		{
			instruction: StoreScratch{Src: 0xffff, N: 3},
			assembler:   "unknown instruction: bpf.StoreScratch{Src:0xffff, N:3}",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpAdd, Val: 42},
			assembler:   "add #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpSub, Val: 42},
			assembler:   "sub #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpMul, Val: 42},
			assembler:   "mul #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpDiv, Val: 42},
			assembler:   "div #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpOr, Val: 42},
			assembler:   "or #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpAnd, Val: 42},
			assembler:   "and #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpShiftLeft, Val: 42},
			assembler:   "lsh #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpShiftRight, Val: 42},
			assembler:   "rsh #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpMod, Val: 42},
			assembler:   "mod #42",
		},
		{
			instruction: ALUOpConstant{Op: ALUOpXor, Val: 42},
			assembler:   "xor #42",
		},
		{
			instruction: ALUOpConstant{Op: 0xffff, Val: 42},
			assembler:   "unknown instruction: bpf.ALUOpConstant{Op:0xffff, Val:0x2a}",
		},
		{
			instruction: ALUOpX{Op: ALUOpAdd},
			assembler:   "add x",
		},
		{
			instruction: ALUOpX{Op: ALUOpSub},
			assembler:   "sub x",
		},
		{
			instruction: ALUOpX{Op: ALUOpMul},
			assembler:   "mul x",
		},
		{
			instruction: ALUOpX{Op: ALUOpDiv},
			assembler:   "div x",
		},
		{
			instruction: ALUOpX{Op: ALUOpOr},
			assembler:   "or x",
		},
		{
			instruction: ALUOpX{Op: ALUOpAnd},
			assembler:   "and x",
		},
		{
			instruction: ALUOpX{Op: ALUOpShiftLeft},
			assembler:   "lsh x",
		},
		{
			instruction: ALUOpX{Op: ALUOpShiftRight},
			assembler:   "rsh x",
		},
		{
			instruction: ALUOpX{Op: ALUOpMod},
			assembler:   "mod x",
		},
		{
			instruction: ALUOpX{Op: ALUOpXor},
			assembler:   "xor x",
		},
		{
			instruction: ALUOpX{Op: 0xffff},
			assembler:   "unknown instruction: bpf.ALUOpX{Op:0xffff}",
		},
		{
			instruction: NegateA{},
			assembler:   "neg",
		},
		{
			instruction: Jump{Skip: 10},
			assembler:   "ja 10",
		},
		{
			instruction: JumpIf{Cond: JumpEqual, Val: 42, SkipTrue: 8, SkipFalse: 9},
			assembler:   "jeq #42,8,9",
		},
		{
			instruction: JumpIf{Cond: JumpEqual, Val: 42, SkipTrue: 8},
			assembler:   "jeq #42,8",
		},
		{
			instruction: JumpIf{Cond: JumpEqual, Val: 42, SkipFalse: 8},
			assembler:   "jneq #42,8",
		},
		{
			instruction: JumpIf{Cond: JumpNotEqual, Val: 42, SkipTrue: 8},
			assembler:   "jneq #42,8",
		},
		{
			instruction: JumpIf{Cond: JumpLessThan, Val: 42, SkipTrue: 7},
			assembler:   "jlt #42,7",
		},
		{
			instruction: JumpIf{Cond: JumpLessOrEqual, Val: 42, SkipTrue: 6},
			assembler:   "jle #42,6",
		},
		{
			instruction: JumpIf{Cond: JumpGreaterThan, Val: 42, SkipTrue: 4, SkipFalse: 5},
			assembler:   "jgt #42,4,5",
		},
		{
			instruction: JumpIf{Cond: JumpGreaterThan, Val: 42, SkipTrue: 4},
			assembler:   "jgt #42,4",
		},
		{
			instruction: JumpIf{Cond: JumpGreaterOrEqual, Val: 42, SkipTrue: 3, SkipFalse: 4},
			assembler:   "jge #42,3,4",
		},
		{
			instruction: JumpIf{Cond: JumpGreaterOrEqual, Val: 42, SkipTrue: 3},
			assembler:   "jge #42,3",
		},
		{
			instruction: JumpIf{Cond: JumpBitsSet, Val: 42, SkipTrue: 2, SkipFalse: 3},
			assembler:   "jset #42,2,3",
		},
		{
			instruction: JumpIf{Cond: JumpBitsSet, Val: 42, SkipTrue: 2},
			assembler:   "jset #42,2",
		},
		{
			instruction: JumpIf{Cond: JumpBitsNotSet, Val: 42, SkipTrue: 2, SkipFalse: 3},
			assembler:   "jset #42,3,2",
		},
		{
			instruction: JumpIf{Cond: JumpBitsNotSet, Val: 42, SkipTrue: 2},
			assembler:   "jset #42,0,2",
		},
		{
			instruction: JumpIf{Cond: 0xffff, Val: 42, SkipTrue: 1, SkipFalse: 2},
			assembler:   "unknown instruction: bpf.JumpIf{Cond:0xffff, Val:0x2a, SkipTrue:0x1, SkipFalse:0x2}",
		},
		{
			instruction: TAX{},
			assembler:   "tax",
		},
		{
			instruction: TXA{},
			assembler:   "txa",
		},
		{
			instruction: RetA{},
			assembler:   "ret a",
		},
		{
			instruction: RetConstant{Val: 42},
			assembler:   "ret #42",
		},
		// Invalid instruction
		{
			instruction: InvalidInstruction{},
			assembler:   "unknown instruction: bpf.InvalidInstruction{}",
		},
	}

	for _, testCase := range testCases {
		if input, ok := testCase.instruction.(fmt.Stringer); ok {
			got := input.String()
			if got != testCase.assembler {
				t.Errorf("String did not return expected assembler notation, expected: %s, got: %s", testCase.assembler, got)
			}
		} else {
			t.Errorf("Instruction %#v is not a fmt.Stringer", testCase.instruction)
		}
	}
}


text:
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package bpf_test

import (
	"net"
	"runtime"
	"testing"
	"time"

	"golang.org/x/net/bpf"
	"golang.org/x/net/ipv4"
)

// A virtualMachine is a BPF virtual machine which can process an
// input packet against a BPF program and render a verdict.
type virtualMachine interface {
	Run(in []byte) (int, error)
}

// canUseOSVM indicates if the OS BPF VM is available on this platform.
func canUseOSVM() bool {
	// OS BPF VM can only be used on platforms where x/net/ipv4 supports
	// attaching a BPF program to a socket.
	switch runtime.GOOS {
	case "linux":
		return true
	}

	return false
}

// All BPF tests against both the Go VM and OS VM are assumed to
// be used with a UDP socket. As a result, the entire contents
// of a UDP datagram is sent through the BPF program, but only
// the body after the UDP header will ever be returned in output.

// testVM sets up a Go BPF VM, and if available, a native OS BPF VM
// for integration testing.
func testVM(t *testing.T, filter []bpf.Instruction) (virtualMachine, func(), error) {
	goVM, err := bpf.NewVM(filter)
	if err != nil {
		// Some tests expect an error, so this error must be returned
		// instead of fatally exiting the test
		return nil, nil, err
	}

	mvm := &multiVirtualMachine{
		goVM: goVM,

		t: t,
	}

	// If available, add the OS VM for tests which verify that both the Go
	// VM and OS VM have exactly the same output for the same input program
	// and packet.
	done := func() {}
	if canUseOSVM() {
		osVM, osVMDone := testOSVM(t, filter)
		done = func() { osVMDone() }
		mvm.osVM = osVM
	}

	return mvm, done, nil
}

// udpHeaderLen is the length of a UDP header.
const udpHeaderLen = 8

// A multiVirtualMachine is a virtualMachine which can call out to both the Go VM
// and the native OS VM, if the OS VM is available.
type multiVirtualMachine struct {
	goVM virtualMachine
	osVM virtualMachine

	t *testing.T
}

func (mvm *multiVirtualMachine) Run(in []byte) (int, error) {
	if len(in) < udpHeaderLen {
		mvm.t.Fatalf("input must be at least length of UDP header (%d), got: %d",
			udpHeaderLen, len(in))
	}

	// All tests have a UDP header as part of input, because the OS VM
	// packets always will. For the Go VM, this output is trimmed before
	// being sent back to tests.
	goOut, goErr := mvm.goVM.Run(in)
	if goOut >= udpHeaderLen {
		goOut -= udpHeaderLen
	}

	// If Go output is larger than the size of the packet, packet filtering
	// interop tests must trim the output bytes to the length of the packet.
	// The BPF VM should not do this on its own, as other uses of it do
	// not trim the output byte count.
	trim := len(in) - udpHeaderLen
	if goOut > trim {
		goOut = trim
	}

	// When the OS VM is not available, process using the Go VM alone
	if mvm.osVM == nil {
		return goOut, goErr
	}

	// The OS VM will apply its own UDP header, so remove the pseudo header
	// that the Go VM needs.
	osOut, err := mvm.osVM.Run(in[udpHeaderLen:])
	if err != nil {
		mvm.t.Fatalf("error while running OS VM: %v", err)
	}

	// Verify both VMs return same number of bytes
	var mismatch bool
	if goOut != osOut {
		mismatch = true
		mvm.t.Logf("output byte count does not match:\n- go: %v\n- os: %v", goOut, osOut)
	}

	if mismatch {
		mvm.t.Fatal("Go BPF and OS BPF packet outputs do not match")
	}

	return goOut, goErr
}

// An osVirtualMachine is a virtualMachine which uses the OS's BPF VM for
// processing BPF programs.
type osVirtualMachine struct {
	l net.PacketConn
	s net.Conn
}

// testOSVM creates a virtualMachine which uses the OS's BPF VM by injecting
// packets into a UDP listener with a BPF program attached to it.
func testOSVM(t *testing.T, filter []bpf.Instruction) (virtualMachine, func()) {
	l, err := net.ListenPacket("udp4", "127.0.0.1:0")
	if err != nil {
		t.Fatalf("failed to open OS VM UDP listener: %v", err)
	}

	prog, err := bpf.Assemble(filter)
	if err != nil {
		t.Fatalf("failed to compile BPF program: %v", err)
	}

	p := ipv4.NewPacketConn(l)
	if err = p.SetBPF(prog); err != nil {
		t.Fatalf("failed to attach BPF program to listener: %v", err)
	}

	s, err := net.Dial("udp4", l.LocalAddr().String())
	if err != nil {
		t.Fatalf("failed to dial connection to listener: %v", err)
	}

	done := func() {
		_ = s.Close()
		_ = l.Close()
	}

	return &osVirtualMachine{
		l: l,
		s: s,
	}, done
}

// Run sends the input bytes into the OS's BPF VM and returns its verdict.
func (vm *osVirtualMachine) Run(in []byte) (int, error) {
	go func() {
		_, _ = vm.s.Write(in)
	}()

	vm.l.SetDeadline(time.Now().Add(50 * time.Millisecond))

	var b [512]byte
	n, _, err := vm.l.ReadFrom(b[:])
	if err != nil {
		// A timeout indicates that BPF filtered out the packet, and thus,
		// no input should be returned.
		if nerr, ok := err.(net.Error); ok && nerr.Timeout() {
			return n, nil
		}

		return n, err
	}

	return n, nil
}


text:
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package bpf_test

import (
	"testing"

	"golang.org/x/net/bpf"
)

func TestVMStoreScratchInvalidScratchRegisterTooSmall(t *testing.T) {
	_, _, err := testVM(t, []bpf.Instruction{
		bpf.StoreScratch{
			Src: bpf.RegA,
			N:   -1,
		},
		bpf.RetA{},
	})
	if errStr(err) != "assembling instruction 1: invalid scratch slot -1" {
		t.Fatalf("unexpected error: %v", err)
	}
}

func TestVMStoreScratchInvalidScratchRegisterTooLarge(t *testing.T) {
	_, _, err := testVM(t, []bpf.Instruction{
		bpf.StoreScratch{
			Src: bpf.RegA,
			N:   16,
		},
		bpf.RetA{},
	})
	if errStr(err) != "assembling instruction 1: invalid scratch slot 16" {
		t.Fatalf("unexpected error: %v", err)
	}
}

func TestVMStoreScratchUnknownSourceRegister(t *testing.T) {
	_, _, err := testVM(t, []bpf.Instruction{
		bpf.StoreScratch{
			Src: 100,
			N:   0,
		},
		bpf.RetA{},
	})
	if errStr(err) != "assembling instruction 1: invalid source register 100" {
		t.Fatalf("unexpected error: %v", err)
	}
}

func TestVMLoadScratchInvalidScratchRegisterTooSmall(t *testing.T) {
	_, _, err := testVM(t, []bpf.Instruction{
		bpf.LoadScratch{
			Dst: bpf.RegX,
			N:   -1,
		},
		bpf.RetA{},
	})
	if errStr(err) != "assembling instruction 1: invalid scratch slot -1" {
		t.Fatalf("unexpected error: %v", err)
	}
}

func TestVMLoadScratchInvalidScratchRegisterTooLarge(t *testing.T) {
	_, _, err := testVM(t, []bpf.Instruction{
		bpf.LoadScratch{
			Dst: bpf.RegX,
			N:   16,
		},
		bpf.RetA{},
	})
	if errStr(err) != "assembling instruction 1: invalid scratch slot 16" {
		t.Fatalf("unexpected error: %v", err)
	}
}

func TestVMLoadScratchUnknownDestinationRegister(t *testing.T) {
	_, _, err := testVM(t, []bpf.Instruction{
		bpf.LoadScratch{
			Dst: 100,
			N:   0,
		},
		bpf.RetA{},
	})
	if errStr(err) != "assembling instruction 1: invalid target register 100" {
		t.Fatalf("unexpected error: %v", err)
	}
}

func TestVMStoreScratchLoadScratchOneValue(t *testing.T) {
	vm, done, err := testVM(t, []bpf.Instruction{
		// Load byte 255
		bpf.LoadAbsolute{
			Off:  8,
			Size: 1,
		},
		// Copy to X and store in scratch[0]
		bpf.TAX{},
		bpf.StoreScratch{
			Src: bpf.RegX,
			N:   0,
		},
		// Load byte 1
		bpf.LoadAbsolute{
			Off:  9,
			Size: 1,
		},
		// Overwrite 1 with 255 from scratch[0]
		bpf.LoadScratch{
			Dst: bpf.RegA,
			N:   0,
		},
		// Return 255
		bpf.RetA{},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}
	defer done()

	out, err := vm.Run([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
		255, 1, 2,
	})
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 3, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

func TestVMStoreScratchLoadScratchMultipleValues(t *testing.T) {
	vm, done, err := testVM(t, []bpf.Instruction{
		// Load byte 10
		bpf.LoadAbsolute{
			Off:  8,
			Size: 1,
		},
		// Store in scratch[0]
		bpf.StoreScratch{
			Src: bpf.RegA,
			N:   0,
		},
		// Load byte 20
		bpf.LoadAbsolute{
			Off:  9,
			Size: 1,
		},
		// Store in scratch[1]
		bpf.StoreScratch{
			Src: bpf.RegA,
			N:   1,
		},
		// Load byte 30
		bpf.LoadAbsolute{
			Off:  10,
			Size: 1,
		},
		// Store in scratch[2]
		bpf.StoreScratch{
			Src: bpf.RegA,
			N:   2,
		},
		// Load byte 1
		bpf.LoadAbsolute{
			Off:  11,
			Size: 1,
		},
		// Store in scratch[3]
		bpf.StoreScratch{
			Src: bpf.RegA,
			N:   3,
		},
		// Load in byte 10 to X
		bpf.LoadScratch{
			Dst: bpf.RegX,
			N:   0,
		},
		// Copy X -> A
		bpf.TXA{},
		// Verify value is 10
		bpf.JumpIf{
			Cond:     bpf.JumpEqual,
			Val:      10,
			SkipTrue: 1,
		},
		// Fail test if incorrect
		bpf.RetConstant{
			Val: 0,
		},
		// Load in byte 20 to A
		bpf.LoadScratch{
			Dst: bpf.RegA,
			N:   1,
		},
		// Verify value is 20
		bpf.JumpIf{
			Cond:     bpf.JumpEqual,
			Val:      20,
			SkipTrue: 1,
		},
		// Fail test if incorrect
		bpf.RetConstant{
			Val: 0,
		},
		// Load in byte 30 to A
		bpf.LoadScratch{
			Dst: bpf.RegA,
			N:   2,
		},
		// Verify value is 30
		bpf.JumpIf{
			Cond:     bpf.JumpEqual,
			Val:      30,
			SkipTrue: 1,
		},
		// Fail test if incorrect
		bpf.RetConstant{
			Val: 0,
		},
		// Return first two bytes on success
		bpf.RetConstant{
			Val: 10,
		},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}
	defer done()

	out, err := vm.Run([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
		10, 20, 30, 1,
	})
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 2, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}


text:
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package bpf

// A Register is a register of the BPF virtual machine.
type Register uint16

const (
	// RegA is the accumulator register. RegA is always the
	// destination register of ALU operations.
	RegA Register = iota
	// RegX is the indirection register, used by LoadIndirect
	// operations.
	RegX
)

// An ALUOp is an arithmetic or logic operation.
type ALUOp uint16

// ALU binary operation types.
const (
	ALUOpAdd ALUOp = iota << 4
	ALUOpSub
	ALUOpMul
	ALUOpDiv
	ALUOpOr
	ALUOpAnd
	ALUOpShiftLeft
	ALUOpShiftRight
	aluOpNeg // Not exported because it's the only unary ALU operation, and gets its own instruction type.
	ALUOpMod
	ALUOpXor
)

// A JumpTest is a comparison operator used in conditional jumps.
type JumpTest uint16

// Supported operators for conditional jumps.
const (
	// K == A
	JumpEqual JumpTest = iota
	// K != A
	JumpNotEqual
	// K > A
	JumpGreaterThan
	// K < A
	JumpLessThan
	// K >= A
	JumpGreaterOrEqual
	// K <= A
	JumpLessOrEqual
	// K & A != 0
	JumpBitsSet
	// K & A == 0
	JumpBitsNotSet
)

// An Extension is a function call provided by the kernel that
// performs advanced operations that are expensive or impossible
// within the BPF virtual machine.
//
// Extensions are only implemented by the Linux kernel.
//
// TODO: should we prune this list? Some of these extensions seem
// either broken or near-impossible to use correctly, whereas other
// (len, random, ifindex) are quite useful.
type Extension int

// Extension functions available in the Linux kernel.
const (
	// extOffset is the negative maximum number of instructions used
	// to load instructions by overloading the K argument.
	extOffset = -0x1000
	// ExtLen returns the length of the packet.
	ExtLen Extension = 1
	// ExtProto returns the packet's L3 protocol type.
	ExtProto Extension = 0
	// ExtType returns the packet's type (skb->pkt_type in the kernel)
	//
	// TODO: better documentation. How nice an API do we want to
	// provide for these esoteric extensions?
	ExtType Extension = 4
	// ExtPayloadOffset returns the offset of the packet payload, or
	// the first protocol header that the kernel does not know how to
	// parse.
	ExtPayloadOffset Extension = 52
	// ExtInterfaceIndex returns the index of the interface on which
	// the packet was received.
	ExtInterfaceIndex Extension = 8
	// ExtNetlinkAttr returns the netlink attribute of type X at
	// offset A.
	ExtNetlinkAttr Extension = 12
	// ExtNetlinkAttrNested returns the nested netlink attribute of
	// type X at offset A.
	ExtNetlinkAttrNested Extension = 16
	// ExtMark returns the packet's mark value.
	ExtMark Extension = 20
	// ExtQueue returns the packet's assigned hardware queue.
	ExtQueue Extension = 24
	// ExtLinkLayerType returns the packet's hardware address type
	// (e.g. Ethernet, Infiniband).
	ExtLinkLayerType Extension = 28
	// ExtRXHash returns the packets receive hash.
	//
	// TODO: figure out what this rxhash actually is.
	ExtRXHash Extension = 32
	// ExtCPUID returns the ID of the CPU processing the current
	// packet.
	ExtCPUID Extension = 36
	// ExtVLANTag returns the packet's VLAN tag.
	ExtVLANTag Extension = 44
	// ExtVLANTagPresent returns non-zero if the packet has a VLAN
	// tag.
	//
	// TODO: I think this might be a lie: it reads bit 0x1000 of the
	// VLAN header, which changed meaning in recent revisions of the
	// spec - this extension may now return meaningless information.
	ExtVLANTagPresent Extension = 48
	// ExtVLANProto returns 0x8100 if the frame has a VLAN header,
	// 0x88a8 if the frame has a "Q-in-Q" double VLAN header, or some
	// other value if no VLAN information is present.
	ExtVLANProto Extension = 60
	// ExtRand returns a uniformly random uint32.
	ExtRand Extension = 56
)

// The following gives names to various bit patterns used in opcode construction.

const (
	opMaskCls uint16 = 0x7
	// opClsLoad masks
	opMaskLoadDest  = 0x01
	opMaskLoadWidth = 0x18
	opMaskLoadMode  = 0xe0
	// opClsALU
	opMaskOperandSrc = 0x08
	opMaskOperator   = 0xf0
	// opClsJump
	opMaskJumpConst = 0x0f
	opMaskJumpCond  = 0xf0
)

const (
	// +---------------+-----------------+---+---+---+
	// | AddrMode (3b) | LoadWidth (2b)  | 0 | 0 | 0 |
	// +---------------+-----------------+---+---+---+
	opClsLoadA uint16 = iota
	// +---------------+-----------------+---+---+---+
	// | AddrMode (3b) | LoadWidth (2b)  | 0 | 0 | 1 |
	// +---------------+-----------------+---+---+---+
	opClsLoadX
	// +---+---+---+---+---+---+---+---+
	// | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
	// +---+---+---+---+---+---+---+---+
	opClsStoreA
	// +---+---+---+---+---+---+---+---+
	// | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
	// +---+---+---+---+---+---+---+---+
	opClsStoreX
	// +---------------+-----------------+---+---+---+
	// | Operator (4b) | OperandSrc (1b) | 1 | 0 | 0 |
	// +---------------+-----------------+---+---+---+
	opClsALU
	// +-----------------------------+---+---+---+---+
	// |      TestOperator (4b)      | 0 | 1 | 0 | 1 |
	// +-----------------------------+---+---+---+---+
	opClsJump
	// +---+-------------------------+---+---+---+---+
	// | 0 | 0 | 0 |   RetSrc (1b)   | 0 | 1 | 1 | 0 |
	// +---+-------------------------+---+---+---+---+
	opClsReturn
	// +---+-------------------------+---+---+---+---+
	// | 0 | 0 | 0 |  TXAorTAX (1b)  | 0 | 1 | 1 | 1 |
	// +---+-------------------------+---+---+---+---+
	opClsMisc
)

const (
	opAddrModeImmediate uint16 = iota << 5
	opAddrModeAbsolute
	opAddrModeIndirect
	opAddrModeScratch
	opAddrModePacketLen // actually an extension, not an addressing mode.
	opAddrModeMemShift
)

const (
	opLoadWidth4 uint16 = iota << 3
	opLoadWidth2
	opLoadWidth1
)

// Operator defined by ALUOp*

const (
	opALUSrcConstant uint16 = iota << 3
	opALUSrcX
)

const (
	opJumpAlways = iota << 4
	opJumpEqual
	opJumpGT
	opJumpGE
	opJumpSet
)

const (
	opRetSrcConstant uint16 = iota << 4
	opRetSrcA
)

const (
	opMiscTAX = 0x00
	opMiscTXA = 0x80
)


text:
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package bpf

import "fmt"

// Assemble converts insts into raw instructions suitable for loading
// into a BPF virtual machine.
//
// Currently, no optimization is attempted, the assembled program flow
// is exactly as provided.
func Assemble(insts []Instruction) ([]RawInstruction, error) {
	ret := make([]RawInstruction, len(insts))
	var err error
	for i, inst := range insts {
		ret[i], err = inst.Assemble()
		if err != nil {
			return nil, fmt.Errorf("assembling instruction %d: %s", i+1, err)
		}
	}
	return ret, nil
}

// Disassemble attempts to parse raw back into
// Instructions. Unrecognized RawInstructions are assumed to be an
// extension not implemented by this package, and are passed through
// unchanged to the output. The allDecoded value reports whether insts
// contains no RawInstructions.
func Disassemble(raw []RawInstruction) (insts []Instruction, allDecoded bool) {
	insts = make([]Instruction, len(raw))
	allDecoded = true
	for i, r := range raw {
		insts[i] = r.Disassemble()
		if _, ok := insts[i].(RawInstruction); ok {
			allDecoded = false
		}
	}
	return insts, allDecoded
}


text:
// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package bpf_test

import (
	"net"
	"testing"

	"golang.org/x/net/bpf"
	"golang.org/x/net/ipv4"
)

func TestVMLoadAbsoluteOffsetOutOfBounds(t *testing.T) {
	vm, done, err := testVM(t, []bpf.Instruction{
		bpf.LoadAbsolute{
			Off:  100,
			Size: 2,
		},
		bpf.RetA{},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}
	defer done()

	out, err := vm.Run([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
		0, 1, 2, 3,
	})
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 0, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

func TestVMLoadAbsoluteOffsetPlusSizeOutOfBounds(t *testing.T) {
	vm, done, err := testVM(t, []bpf.Instruction{
		bpf.LoadAbsolute{
			Off:  8,
			Size: 2,
		},
		bpf.RetA{},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}
	defer done()

	out, err := vm.Run([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
		0,
	})
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 0, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

func TestVMLoadAbsoluteBadInstructionSize(t *testing.T) {
	_, _, err := testVM(t, []bpf.Instruction{
		bpf.LoadAbsolute{
			Size: 5,
		},
		bpf.RetA{},
	})
	if errStr(err) != "assembling instruction 1: invalid load byte length 0" {
		t.Fatalf("unexpected error: %v", err)
	}
}

func TestVMLoadConstantOK(t *testing.T) {
	vm, done, err := testVM(t, []bpf.Instruction{
		bpf.LoadConstant{
			Dst: bpf.RegX,
			Val: 9,
		},
		bpf.TXA{},
		bpf.RetA{},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}
	defer done()

	out, err := vm.Run([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
		0,
	})
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 1, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

func TestVMLoadIndirectOutOfBounds(t *testing.T) {
	vm, done, err := testVM(t, []bpf.Instruction{
		bpf.LoadIndirect{
			Off:  100,
			Size: 1,
		},
		bpf.RetA{},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}
	defer done()

	out, err := vm.Run([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
		0,
	})
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 0, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

func TestVMLoadMemShiftOutOfBounds(t *testing.T) {
	vm, done, err := testVM(t, []bpf.Instruction{
		bpf.LoadMemShift{
			Off: 100,
		},
		bpf.RetA{},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}
	defer done()

	out, err := vm.Run([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
		0,
	})
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 0, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

const (
	dhcp4Port = 53
)

func TestVMLoadMemShiftLoadIndirectNoResult(t *testing.T) {
	vm, in, done := testDHCPv4(t)
	defer done()

	// Append mostly empty UDP header with incorrect DHCPv4 port
	in = append(in, []byte{
		0, 0,
		0, dhcp4Port + 1,
		0, 0,
		0, 0,
	}...)

	out, err := vm.Run(in)
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := 0, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

func TestVMLoadMemShiftLoadIndirectOK(t *testing.T) {
	vm, in, done := testDHCPv4(t)
	defer done()

	// Append mostly empty UDP header with correct DHCPv4 port
	in = append(in, []byte{
		0, 0,
		0, dhcp4Port,
		0, 0,
		0, 0,
	}...)

	out, err := vm.Run(in)
	if err != nil {
		t.Fatalf("unexpected error while running program: %v", err)
	}
	if want, got := len(in)-8, out; want != got {
		t.Fatalf("unexpected number of output bytes:\n- want: %d\n-  got: %d",
			want, got)
	}
}

func testDHCPv4(t *testing.T) (virtualMachine, []byte, func()) {
	// DHCPv4 test data courtesy of David Anderson:
	// https://github.com/google/netboot/blob/master/dhcp4/conn_linux.go#L59-L70
	vm, done, err := testVM(t, []bpf.Instruction{
		// Load IPv4 packet length
		bpf.LoadMemShift{Off: 8},
		// Get UDP dport
		bpf.LoadIndirect{Off: 8 + 2, Size: 2},
		// Correct dport?
		bpf.JumpIf{Cond: bpf.JumpEqual, Val: dhcp4Port, SkipFalse: 1},
		// Accept
		bpf.RetConstant{Val: 1500},
		// Ignore
		bpf.RetConstant{Val: 0},
	})
	if err != nil {
		t.Fatalf("failed to load BPF program: %v", err)
	}

	// Minimal requirements to make a valid IPv4 header
	h := &ipv4.Header{
		Len: ipv4.HeaderLen,
		Src: net.IPv4(192, 168, 1, 1),
		Dst: net.IPv4(192, 168, 1, 2),
	}
	hb, err := h.Marshal()
	if err != nil {
		t.Fatalf("failed to marshal IPv4 header: %v", err)
	}

	hb = append([]byte{
		0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff,
	}, hb...)

	return vm, hb, done
}