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 5 package runtime 6 7 import ( 8 "runtime/internal/atomic" 9 "runtime/internal/sys" 10 "unsafe" 11 ) 12 13 const ( 14 // For the time histogram type, we use an HDR histogram. 15 // Values are placed in super-buckets based solely on the most 16 // significant set bit. Thus, super-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 super-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 super-bucket the error is approximately 6%. 25 // 26 // The number of super-buckets (timeHistNumSuperBuckets), on the 27 // other hand, defines the range. To reserve room for sub-buckets, 28 // bit timeHistSubBucketBits is the first bit considered for 29 // super-buckets, so super-bucket indices are adjusted accordingly. 30 // 31 // As an example, consider 45 super-buckets with 16 sub-buckets. 32 // 33 // 00110 34 // ^---- 35 // │ ^ 36 // │ └---- Lowest 4 bits -> sub-bucket 6 37 // └------- Bit 4 unset -> super-bucket 0 38 // 39 // 10110 40 // ^---- 41 // │ ^ 42 // │ └---- Next 4 bits -> sub-bucket 6 43 // └------- Bit 4 set -> super-bucket 1 44 // 100010 45 // ^----^ 46 // │ ^ └-- Lower bits ignored 47 // │ └---- Next 4 bits -> sub-bucket 1 48 // └------- Bit 5 set -> super-bucket 2 49 // 50 // Following this pattern, super-bucket 44 will have the bit 47 set. We don't 51 // have any buckets for higher values, so the highest sub-bucket will 52 // contain values of 2^48-1 nanoseconds or approx. 3 days. This range is 53 // more than enough to handle durations produced by the runtime. 54 timeHistSubBucketBits = 4 55 timeHistNumSubBuckets = 1 << timeHistSubBucketBits 56 timeHistNumSuperBuckets = 45 57 timeHistTotalBuckets = timeHistNumSuperBuckets*timeHistNumSubBuckets + 1 58 ) 59 60 // timeHistogram represents a distribution of durations in 61 // nanoseconds. 62 // 63 // The accuracy and range of the histogram is defined by the 64 // timeHistSubBucketBits and timeHistNumSuperBuckets constants. 65 // 66 // It is an HDR histogram with exponentially-distributed 67 // buckets and linearly distributed sub-buckets. 68 // 69 // Counts in the histogram are updated atomically, so it is safe 70 // for concurrent use. It is also safe to read all the values 71 // atomically. 72 type timeHistogram struct { 73 counts [timeHistNumSuperBuckets * timeHistNumSubBuckets]uint64 74 75 // underflow counts all the times we got a negative duration 76 // sample. Because of how time works on some platforms, it's 77 // possible to measure negative durations. We could ignore them, 78 // but we record them anyway because it's better to have some 79 // signal that it's happening than just missing samples. 80 underflow uint64 81 } 82 83 // record adds the given duration to the distribution. 84 // 85 // Disallow preemptions and stack growths because this function 86 // may run in sensitive locations. 87 // 88 //go:nosplit 89 func (h *timeHistogram) record(duration int64) { 90 if duration < 0 { 91 atomic.Xadd64(&h.underflow, 1) 92 return 93 } 94 // The index of the exponential bucket is just the index 95 // of the highest set bit adjusted for how many bits we 96 // use for the subbucket. Note that it's timeHistSubBucketsBits-1 97 // because we use the 0th bucket to hold values < timeHistNumSubBuckets. 98 var superBucket, subBucket uint 99 if duration >= timeHistNumSubBuckets { 100 // At this point, we know the duration value will always be 101 // at least timeHistSubBucketsBits long. 102 superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits 103 if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) { 104 // The bucket index we got is larger than what we support, so 105 // include this count in the highest bucket, which extends to 106 // infinity. 107 superBucket = timeHistNumSuperBuckets - 1 108 subBucket = timeHistNumSubBuckets - 1 109 } else { 110 // The linear subbucket index is just the timeHistSubBucketsBits 111 // bits after the top bit. To extract that value, shift down 112 // the duration such that we leave the top bit and the next bits 113 // intact, then extract the index. 114 subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets) 115 } 116 } else { 117 subBucket = uint(duration) 118 } 119 atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1) 120 } 121 122 const ( 123 fInf = 0x7FF0000000000000 124 fNegInf = 0xFFF0000000000000 125 ) 126 127 func float64Inf() float64 { 128 inf := uint64(fInf) 129 return *(*float64)(unsafe.Pointer(&inf)) 130 } 131 132 func float64NegInf() float64 { 133 inf := uint64(fNegInf) 134 return *(*float64)(unsafe.Pointer(&inf)) 135 } 136 137 // timeHistogramMetricsBuckets generates a slice of boundaries for 138 // the timeHistogram. These boundaries are represented in seconds, 139 // not nanoseconds like the timeHistogram represents durations. 140 func timeHistogramMetricsBuckets() []float64 { 141 b := make([]float64, timeHistTotalBuckets+1) 142 b[0] = float64NegInf() 143 // Super-bucket 0 has no bits above timeHistSubBucketBits 144 // set, so just iterate over each bucket and assign the 145 // incrementing bucket. 146 for i := 0; i < timeHistNumSubBuckets; i++ { 147 bucketNanos := uint64(i) 148 b[i+1] = float64(bucketNanos) / 1e9 149 } 150 // Generate the rest of the super-buckets. It's easier to reason 151 // about if we cut out the 0'th bucket, so subtract one since 152 // we just handled that bucket. 153 for i := 0; i < timeHistNumSuperBuckets-1; i++ { 154 for j := 0; j < timeHistNumSubBuckets; j++ { 155 // Set the super-bucket bit. 156 bucketNanos := uint64(1) << (i + timeHistSubBucketBits) 157 // Set the sub-bucket bits. 158 bucketNanos |= uint64(j) << i 159 // The index for this bucket is going to be the (i+1)'th super bucket 160 // (note that we're starting from zero, but handled the first super-bucket 161 // earlier, so we need to compensate), and the j'th sub bucket. 162 // Add 1 because we left space for -Inf. 163 bucketIndex := (i+1)*timeHistNumSubBuckets + j + 1 164 // Convert nanoseconds to seconds via a division. 165 // These values will all be exactly representable by a float64. 166 b[bucketIndex] = float64(bucketNanos) / 1e9 167 } 168 } 169 b[len(b)-1] = float64Inf() 170 return b 171 } 172