1// Copyright 2017, OpenCensus Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package trace
16
17import (
18	"time"
19)
20
21// samplePeriod is the minimum time between accepting spans in a single bucket.
22const samplePeriod = time.Second
23
24// defaultLatencies contains the default latency bucket bounds.
25// TODO: consider defaults, make configurable
26var defaultLatencies = [...]time.Duration{
27	10 * time.Microsecond,
28	100 * time.Microsecond,
29	time.Millisecond,
30	10 * time.Millisecond,
31	100 * time.Millisecond,
32	time.Second,
33	10 * time.Second,
34	time.Minute,
35}
36
37// bucket is a container for a set of spans for a particular error code or latency range.
38type bucket struct {
39	nextTime  time.Time   // next time we can accept a span
40	buffer    []*SpanData // circular buffer of spans
41	nextIndex int         // location next SpanData should be placed in buffer
42	overflow  bool        // whether the circular buffer has wrapped around
43}
44
45func makeBucket(bufferSize int) bucket {
46	return bucket{
47		buffer: make([]*SpanData, bufferSize),
48	}
49}
50
51// add adds a span to the bucket, if nextTime has been reached.
52func (b *bucket) add(s *SpanData) {
53	if s.EndTime.Before(b.nextTime) {
54		return
55	}
56	if len(b.buffer) == 0 {
57		return
58	}
59	b.nextTime = s.EndTime.Add(samplePeriod)
60	b.buffer[b.nextIndex] = s
61	b.nextIndex++
62	if b.nextIndex == len(b.buffer) {
63		b.nextIndex = 0
64		b.overflow = true
65	}
66}
67
68// size returns the number of spans in the bucket.
69func (b *bucket) size() int {
70	if b.overflow {
71		return len(b.buffer)
72	}
73	return b.nextIndex
74}
75
76// span returns the ith span in the bucket.
77func (b *bucket) span(i int) *SpanData {
78	if !b.overflow {
79		return b.buffer[i]
80	}
81	if i < len(b.buffer)-b.nextIndex {
82		return b.buffer[b.nextIndex+i]
83	}
84	return b.buffer[b.nextIndex+i-len(b.buffer)]
85}
86
87// resize changes the size of the bucket to n, keeping up to n existing spans.
88func (b *bucket) resize(n int) {
89	cur := b.size()
90	newBuffer := make([]*SpanData, n)
91	if cur < n {
92		for i := 0; i < cur; i++ {
93			newBuffer[i] = b.span(i)
94		}
95		b.buffer = newBuffer
96		b.nextIndex = cur
97		b.overflow = false
98		return
99	}
100	for i := 0; i < n; i++ {
101		newBuffer[i] = b.span(i + cur - n)
102	}
103	b.buffer = newBuffer
104	b.nextIndex = 0
105	b.overflow = true
106}
107
108// latencyBucket returns the appropriate bucket number for a given latency.
109func latencyBucket(latency time.Duration) int {
110	i := 0
111	for i < len(defaultLatencies) && latency >= defaultLatencies[i] {
112		i++
113	}
114	return i
115}
116
117// latencyBucketBounds returns the lower and upper bounds for a latency bucket
118// number.
119//
120// The lower bound is inclusive, the upper bound is exclusive (except for the
121// last bucket.)
122func latencyBucketBounds(index int) (lower time.Duration, upper time.Duration) {
123	if index == 0 {
124		return 0, defaultLatencies[index]
125	}
126	if index == len(defaultLatencies) {
127		return defaultLatencies[index-1], 1<<63 - 1
128	}
129	return defaultLatencies[index-1], defaultLatencies[index]
130}
131