Debian Codegraph @

sdk/metric/internal/aggregate/atomic.go

raw
1 // Copyright The OpenTelemetry Authors
2 // SPDX-License-Identifier: Apache-2.0
3
4 package aggregate // import "go.opentelemetry.io/otel/sdk/metric/internal/aggregate"
5
6 import (
7 "math"
8 "runtime"
9 "sync"
10 "sync/atomic"
11
12 "go.opentelemetry.io/otel/attribute"
13 )
14
15 // atomicCounter is an efficient way of adding to a number which is either an
16 // int64 or float64. It is designed to be efficient when adding whole
17 // numbers, regardless of whether N is an int64 or float64.
18 //
19 // Inspired by the Prometheus counter implementation:
20 // https://github.com/prometheus/client_golang/blob/14ccb93091c00f86b85af7753100aa372d63602b/prometheus/counter.go#L108
21 type atomicCounter[N int64 | float64] struct {
22 // nFloatBits contains only the non-integer portion of the counter.
23 nFloatBits atomic.Uint64
24 // nInt contains only the integer portion of the counter.
25 nInt atomic.Int64
26 }
27
28 // load returns the current value. The caller must ensure all calls to add have
29 // returned prior to calling load.
30 func (n *atomicCounter[N]) load() N {
31 fval := math.Float64frombits(n.nFloatBits.Load())
32 ival := n.nInt.Load()
33 return N(fval + float64(ival))
34 }
35
36 func (n *atomicCounter[N]) add(value N) {
37 ival := int64(value)
38 // This case is where the value is an int, or if it is a whole-numbered float.
39 if float64(ival) == float64(value) {
40 n.nInt.Add(ival)
41 return
42 }
43
44 // Value must be a float below.
45 for {
46 oldBits := n.nFloatBits.Load()
47 newBits := math.Float64bits(math.Float64frombits(oldBits) + float64(value))
48 if n.nFloatBits.CompareAndSwap(oldBits, newBits) {
49 return
50 }
51 }
52 }
53
54 // reset resets the internal state, and is not safe to call concurrently.
55 func (n *atomicCounter[N]) reset() {
56 n.nFloatBits.Store(0)
57 n.nInt.Store(0)
58 }
59
60 // atomicN is a generic atomic number value.
61 type atomicN[N int64 | float64] struct {
62 val atomic.Uint64
63 }
64
65 func (a *atomicN[N]) Load() (value N) {
66 v := a.val.Load()
67 switch any(value).(type) {
68 case int64:
69 value = N(v)
70 case float64:
71 value = N(math.Float64frombits(v))
72 default:
73 panic("unsupported type")
74 }
75 return value
76 }
77
78 func (a *atomicN[N]) Store(v N) {
79 var val uint64
80 switch any(v).(type) {
81 case int64:
82 val = uint64(v)
83 case float64:
84 val = math.Float64bits(float64(v))
85 default:
86 panic("unsupported type")
87 }
88 a.val.Store(val)
89 }
90
91 func (a *atomicN[N]) CompareAndSwap(oldN, newN N) bool {
92 var o, n uint64
93 switch any(oldN).(type) {
94 case int64:
95 o, n = uint64(oldN), uint64(newN)
96 case float64:
97 o, n = math.Float64bits(float64(oldN)), math.Float64bits(float64(newN))
98 default:
99 panic("unsupported type")
100 }
101 return a.val.CompareAndSwap(o, n)
102 }
103
104 type atomicMinMax[N int64 | float64] struct {
105 minimum, maximum atomicN[N]
106 set atomic.Bool
107 mu sync.Mutex
108 }
109
110 // init returns true if the value was used to initialize min and max.
111 func (s *atomicMinMax[N]) init(val N) bool {
112 s.mu.Lock()
113 defer s.mu.Unlock()
114 if !s.set.Load() {
115 defer s.set.Store(true)
116 s.minimum.Store(val)
117 s.maximum.Store(val)
118 return true
119 }
120 return false
121 }
122
123 func (s *atomicMinMax[N]) Update(val N) {
124 if !s.set.Load() && s.init(val) {
125 return
126 }
127
128 old := s.minimum.Load()
129 for val < old {
130 if s.minimum.CompareAndSwap(old, val) {
131 return
132 }
133 old = s.minimum.Load()
134 }
135
136 old = s.maximum.Load()
137 for old < val {
138 if s.maximum.CompareAndSwap(old, val) {
139 return
140 }
141 old = s.maximum.Load()
142 }
143 }
144
145 // hotColdWaitGroup is a synchronization primitive which enables lockless
146 // writes for concurrent writers and enables a reader to acquire exclusive
147 // access to a snapshot of state including only completed operations.
148 // Conceptually, it can be thought of as a "hot" wait group,
149 // and a "cold" wait group, with the ability for the reader to atomically swap
150 // the hot and cold wait groups, and wait for the now-cold wait group to
151 // complete.
152 //
153 // Inspired by the prometheus/client_golang histogram implementation:
154 // https://github.com/prometheus/client_golang/blob/a974e0d45e0aa54c65492559114894314d8a2447/prometheus/histogram.go#L725
155 //
156 // Usage:
157 //
158 // var hcwg hotColdWaitGroup
159 // var data [2]any
160 //
161 // func write() {
162 // hotIdx := hcwg.start()
163 // defer hcwg.done(hotIdx)
164 // // modify data without locking
165 // data[hotIdx].update()
166 // }
167 //
168 // func read() {
169 // coldIdx := hcwg.swapHotAndWait()
170 // // read data now that all writes to the cold data have completed.
171 // data[coldIdx].read()
172 // }
173 type hotColdWaitGroup struct {
174 // startedCountAndHotIdx contains a 63-bit counter in the lower bits,
175 // and a 1 bit hot index to denote which of the two data-points new
176 // measurements to write to. These are contained together so that read()
177 // can atomically swap the hot bit, reset the started writes to zero, and
178 // read the number writes that were started prior to the hot bit being
179 // swapped.
180 startedCountAndHotIdx atomic.Uint64
181 // endedCounts is the number of writes that have completed to each
182 // dataPoint.
183 endedCounts [2]atomic.Uint64
184 }
185
186 // start returns the hot index that the writer should write to. The returned
187 // hot index is 0 or 1. The caller must call done(hot index) after it finishes
188 // its operation. start() is safe to call concurrently with other methods.
189 func (l *hotColdWaitGroup) start() uint64 {
190 // We increment h.startedCountAndHotIdx so that the counter in the lower
191 // 63 bits gets incremented. At the same time, we get the new value
192 // back, which we can use to return the currently-hot index.
193 return l.startedCountAndHotIdx.Add(1) >> 63
194 }
195
196 // done signals to the reader that an operation has fully completed.
197 // done is safe to call concurrently.
198 func (l *hotColdWaitGroup) done(hotIdx uint64) {
199 l.endedCounts[hotIdx].Add(1)
200 }
201
202 // swapHotAndWait swaps the hot bit, waits for all start() calls to be done(),
203 // and then returns the now-cold index for the reader to read from. The
204 // returned index is 0 or 1. swapHotAndWait must not be called concurrently.
205 func (l *hotColdWaitGroup) swapHotAndWait() uint64 {
206 n := l.startedCountAndHotIdx.Load()
207 coldIdx := (^n) >> 63
208 // Swap the hot and cold index while resetting the started measurements
209 // count to zero.
210 n = l.startedCountAndHotIdx.Swap((coldIdx << 63))
211 hotIdx := n >> 63
212 startedCount := n & ((1 << 63) - 1)
213 // Wait for all measurements to the previously-hot map to finish.
214 for startedCount != l.endedCounts[hotIdx].Load() {
215 runtime.Gosched() // Let measurements complete.
216 }
217 // reset the number of ended operations
218 l.endedCounts[hotIdx].Store(0)
219 return hotIdx
220 }
221
222 // limitedSyncMap is a sync.Map which enforces the aggregation limit on
223 // attribute sets and provides a Len() function.
224 type limitedSyncMap struct {
225 sync.Map
226 aggLimit int
227 len int
228 lenMux sync.Mutex
229 }
230
231 func (m *limitedSyncMap) LoadOrStoreAttr(fltrAttr attribute.Set, newValue func(attribute.Set) any) any {
232 actual, loaded := m.Load(fltrAttr.Equivalent())
233 if loaded {
234 return actual
235 }
236 // If the overflow set exists, assume we have already overflowed and don't
237 // bother with the slow path below.
238 actual, loaded = m.Load(overflowSet.Equivalent())
239 if loaded {
240 return actual
241 }
242 // Slow path: add a new attribute set.
243 m.lenMux.Lock()
244 defer m.lenMux.Unlock()
245
246 // re-fetch now that we hold the lock to ensure we don't use the overflow
247 // set unless we are sure the attribute set isn't being written
248 // concurrently.
249 actual, loaded = m.Load(fltrAttr.Equivalent())
250 if loaded {
251 return actual
252 }
253
254 if m.aggLimit > 0 && m.len >= m.aggLimit-1 {
255 fltrAttr = overflowSet
256 }
257 actual, loaded = m.LoadOrStore(fltrAttr.Equivalent(), newValue(fltrAttr))
258 if !loaded {
259 m.len++
260 }
261 return actual
262 }
263
264 func (m *limitedSyncMap) Clear() {
265 m.lenMux.Lock()
266 defer m.lenMux.Unlock()
267 m.len = 0
268 m.Map.Clear()
269 }
270
271 func (m *limitedSyncMap) Len() int {
272 m.lenMux.Lock()
273 defer m.lenMux.Unlock()
274 return m.len
275 }