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 //go:nosplit 88 func (h *timeHistogram) record(duration int64) { 89 if duration < 0 { 90 atomic.Xadd64(&h.underflow, 1) 91 return 92 } 93 // The index of the exponential bucket is just the index 94 // of the highest set bit adjusted for how many bits we 95 // use for the subbucket. Note that it's timeHistSubBucketsBits-1 96 // because we use the 0th bucket to hold values < timeHistNumSubBuckets. 97 var superBucket, subBucket uint 98 if duration >= timeHistNumSubBuckets { 99 // At this point, we know the duration value will always be 100 // at least timeHistSubBucketsBits long. 101 superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits 102 if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) { 103 // The bucket index we got is larger than what we support, so 104 // include this count in the highest bucket, which extends to 105 // infinity. 106 superBucket = timeHistNumSuperBuckets - 1 107 subBucket = timeHistNumSubBuckets - 1 108 } else { 109 // The linear subbucket index is just the timeHistSubBucketsBits 110 // bits after the top bit. To extract that value, shift down 111 // the duration such that we leave the top bit and the next bits 112 // intact, then extract the index. 113 subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets) 114 } 115 } else { 116 subBucket = uint(duration) 117 } 118 atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1) 119 } 120 121 const ( 122 fInf = 0x7FF0000000000000 123 fNegInf = 0xFFF0000000000000 124 ) 125 126 func float64Inf() float64 { 127 inf := uint64(fInf) 128 return *(*float64)(unsafe.Pointer(&inf)) 129 } 130 131 func float64NegInf() float64 { 132 inf := uint64(fNegInf) 133 return *(*float64)(unsafe.Pointer(&inf)) 134 } 135 136 // timeHistogramMetricsBuckets generates a slice of boundaries for 137 // the timeHistogram. These boundaries are represented in seconds, 138 // not nanoseconds like the timeHistogram represents durations. 139 func timeHistogramMetricsBuckets() []float64 { 140 b := make([]float64, timeHistTotalBuckets+1) 141 b[0] = float64NegInf() 142 // Super-bucket 0 has no bits above timeHistSubBucketBits 143 // set, so just iterate over each bucket and assign the 144 // incrementing bucket. 145 for i := 0; i < timeHistNumSubBuckets; i++ { 146 bucketNanos := uint64(i) 147 b[i+1] = float64(bucketNanos) / 1e9 148 } 149 // Generate the rest of the super-buckets. It's easier to reason 150 // about if we cut out the 0'th bucket, so subtract one since 151 // we just handled that bucket. 152 for i := 0; i < timeHistNumSuperBuckets-1; i++ { 153 for j := 0; j < timeHistNumSubBuckets; j++ { 154 // Set the super-bucket bit. 155 bucketNanos := uint64(1) << (i + timeHistSubBucketBits) 156 // Set the sub-bucket bits. 157 bucketNanos |= uint64(j) << i 158 // The index for this bucket is going to be the (i+1)'th super bucket 159 // (note that we're starting from zero, but handled the first super-bucket 160 // earlier, so we need to compensate), and the j'th sub bucket. 161 // Add 1 because we left space for -Inf. 162 bucketIndex := (i+1)*timeHistNumSubBuckets + j + 1 163 // Convert nanoseconds to seconds via a division. 164 // These values will all be exactly representable by a float64. 165 b[bucketIndex] = float64(bucketNanos) / 1e9 166 } 167 } 168 b[len(b)-1] = float64Inf() 169 return b 170 } 171