1// Copyright 2020 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package runtime 6 7import ( 8 "internal/runtime/atomic" 9 "runtime/internal/sys" 10 "unsafe" 11) 12 13const ( 14 // For the time histogram type, we use an HDR histogram. 15 // Values are placed in buckets based solely on the most 16 // significant set bit. Thus, buckets are power-of-2 sized. 17 // Values are then placed into sub-buckets based on the value of 18 // the next timeHistSubBucketBits most significant bits. Thus, 19 // sub-buckets are linear within a bucket. 20 // 21 // Therefore, the number of sub-buckets (timeHistNumSubBuckets) 22 // defines the error. This error may be computed as 23 // 1/timeHistNumSubBuckets*100%. For example, for 16 sub-buckets 24 // per bucket the error is approximately 6%. 25 // 26 // The number of buckets (timeHistNumBuckets), on the 27 // other hand, defines the range. To avoid producing a large number 28 // of buckets that are close together, especially for small numbers 29 // (e.g. 1, 2, 3, 4, 5 ns) that aren't very useful, timeHistNumBuckets 30 // is defined in terms of the least significant bit (timeHistMinBucketBits) 31 // that needs to be set before we start bucketing and the most 32 // significant bit (timeHistMaxBucketBits) that we bucket before we just 33 // dump it into a catch-all bucket. 34 // 35 // As an example, consider the configuration: 36 // 37 // timeHistMinBucketBits = 9 38 // timeHistMaxBucketBits = 48 39 // timeHistSubBucketBits = 2 40 // 41 // Then: 42 // 43 // 011000001 44 // ^-- 45 // │ ^ 46 // │ └---- Next 2 bits -> sub-bucket 3 47 // └------- Bit 9 unset -> bucket 0 48 // 49 // 110000001 50 // ^-- 51 // │ ^ 52 // │ └---- Next 2 bits -> sub-bucket 2 53 // └------- Bit 9 set -> bucket 1 54 // 55 // 1000000010 56 // ^-- ^ 57 // │ ^ └-- Lower bits ignored 58 // │ └---- Next 2 bits -> sub-bucket 0 59 // └------- Bit 10 set -> bucket 2 60 // 61 // Following this pattern, bucket 38 will have the bit 46 set. We don't 62 // have any buckets for higher values, so we spill the rest into an overflow 63 // bucket containing values of 2^47-1 nanoseconds or approx. 1 day or more. 64 // This range is more than enough to handle durations produced by the runtime. 65 timeHistMinBucketBits = 9 66 timeHistMaxBucketBits = 48 // Note that this is exclusive; 1 higher than the actual range. 67 timeHistSubBucketBits = 2 68 timeHistNumSubBuckets = 1 << timeHistSubBucketBits 69 timeHistNumBuckets = timeHistMaxBucketBits - timeHistMinBucketBits + 1 70 // Two extra buckets, one for underflow, one for overflow. 71 timeHistTotalBuckets = timeHistNumBuckets*timeHistNumSubBuckets + 2 72) 73 74// timeHistogram represents a distribution of durations in 75// nanoseconds. 76// 77// The accuracy and range of the histogram is defined by the 78// timeHistSubBucketBits and timeHistNumBuckets constants. 79// 80// It is an HDR histogram with exponentially-distributed 81// buckets and linearly distributed sub-buckets. 82// 83// The histogram is safe for concurrent reads and writes. 84type timeHistogram struct { 85 counts [timeHistNumBuckets * timeHistNumSubBuckets]atomic.Uint64 86 87 // underflow counts all the times we got a negative duration 88 // sample. Because of how time works on some platforms, it's 89 // possible to measure negative durations. We could ignore them, 90 // but we record them anyway because it's better to have some 91 // signal that it's happening than just missing samples. 92 underflow atomic.Uint64 93 94 // overflow counts all the times we got a duration that exceeded 95 // the range counts represents. 96 overflow atomic.Uint64 97} 98 99// record adds the given duration to the distribution. 100// 101// Disallow preemptions and stack growths because this function 102// may run in sensitive locations. 103// 104//go:nosplit 105func (h *timeHistogram) record(duration int64) { 106 // If the duration is negative, capture that in underflow. 107 if duration < 0 { 108 h.underflow.Add(1) 109 return 110 } 111 // bucketBit is the target bit for the bucket which is usually the 112 // highest 1 bit, but if we're less than the minimum, is the highest 113 // 1 bit of the minimum (which will be zero in the duration). 114 // 115 // bucket is the bucket index, which is the bucketBit minus the 116 // highest bit of the minimum, plus one to leave room for the catch-all 117 // bucket for samples lower than the minimum. 118 var bucketBit, bucket uint 119 if l := sys.Len64(uint64(duration)); l < timeHistMinBucketBits { 120 bucketBit = timeHistMinBucketBits 121 bucket = 0 // bucketBit - timeHistMinBucketBits 122 } else { 123 bucketBit = uint(l) 124 bucket = bucketBit - timeHistMinBucketBits + 1 125 } 126 // If the bucket we computed is greater than the number of buckets, 127 // count that in overflow. 128 if bucket >= timeHistNumBuckets { 129 h.overflow.Add(1) 130 return 131 } 132 // The sub-bucket index is just next timeHistSubBucketBits after the bucketBit. 133 subBucket := uint(duration>>(bucketBit-1-timeHistSubBucketBits)) % timeHistNumSubBuckets 134 h.counts[bucket*timeHistNumSubBuckets+subBucket].Add(1) 135} 136 137// write dumps the histogram to the passed metricValue as a float64 histogram. 138func (h *timeHistogram) write(out *metricValue) { 139 hist := out.float64HistOrInit(timeHistBuckets) 140 // The bottom-most bucket, containing negative values, is tracked 141 // separately as underflow, so fill that in manually and then iterate 142 // over the rest. 143 hist.counts[0] = h.underflow.Load() 144 for i := range h.counts { 145 hist.counts[i+1] = h.counts[i].Load() 146 } 147 hist.counts[len(hist.counts)-1] = h.overflow.Load() 148} 149 150const ( 151 fInf = 0x7FF0000000000000 152 fNegInf = 0xFFF0000000000000 153) 154 155func float64Inf() float64 { 156 inf := uint64(fInf) 157 return *(*float64)(unsafe.Pointer(&inf)) 158} 159 160func float64NegInf() float64 { 161 inf := uint64(fNegInf) 162 return *(*float64)(unsafe.Pointer(&inf)) 163} 164 165// timeHistogramMetricsBuckets generates a slice of boundaries for 166// the timeHistogram. These boundaries are represented in seconds, 167// not nanoseconds like the timeHistogram represents durations. 168func timeHistogramMetricsBuckets() []float64 { 169 b := make([]float64, timeHistTotalBuckets+1) 170 // Underflow bucket. 171 b[0] = float64NegInf() 172 173 for j := 0; j < timeHistNumSubBuckets; j++ { 174 // No bucket bit for the first few buckets. Just sub-bucket bits after the 175 // min bucket bit. 176 bucketNanos := uint64(j) << (timeHistMinBucketBits - 1 - timeHistSubBucketBits) 177 // Convert nanoseconds to seconds via a division. 178 // These values will all be exactly representable by a float64. 179 b[j+1] = float64(bucketNanos) / 1e9 180 } 181 // Generate the rest of the buckets. It's easier to reason 182 // about if we cut out the 0'th bucket. 183 for i := timeHistMinBucketBits; i < timeHistMaxBucketBits; i++ { 184 for j := 0; j < timeHistNumSubBuckets; j++ { 185 // Set the bucket bit. 186 bucketNanos := uint64(1) << (i - 1) 187 // Set the sub-bucket bits. 188 bucketNanos |= uint64(j) << (i - 1 - timeHistSubBucketBits) 189 // The index for this bucket is going to be the (i+1)'th bucket 190 // (note that we're starting from zero, but handled the first bucket 191 // earlier, so we need to compensate), and the j'th sub bucket. 192 // Add 1 because we left space for -Inf. 193 bucketIndex := (i-timeHistMinBucketBits+1)*timeHistNumSubBuckets + j + 1 194 // Convert nanoseconds to seconds via a division. 195 // These values will all be exactly representable by a float64. 196 b[bucketIndex] = float64(bucketNanos) / 1e9 197 } 198 } 199 // Overflow bucket. 200 b[len(b)-2] = float64(uint64(1)<<(timeHistMaxBucketBits-1)) / 1e9 201 b[len(b)-1] = float64Inf() 202 return b 203} 204