Debian Codegraph @

pkg/util/flowcontrol/fairqueuing/testing/eventclock/fake.go

raw
1 /*
2 Copyright 2021 The Kubernetes Authors.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 package eventclock
18
19 import (
20 "container/heap"
21 "fmt"
22 "math/rand"
23 "runtime"
24 "strconv"
25 "strings"
26 "sync"
27 "time"
28
29 baseclocktest "k8s.io/utils/clock/testing"
30
31 "k8s.io/apiserver/pkg/util/flowcontrol/counter"
32 "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing/eventclock"
33 "k8s.io/klog/v2"
34 )
35
36 // waitGroupCounter is a wait group used for a GoRoutineCounter. This private
37 // type is used to disallow direct waitGroup access
38 type waitGroupCounter struct {
39 wg sync.WaitGroup
40 }
41
42 // compile time assertion that waitGroupCounter meets requirements
43 // of GoRoutineCounter
44 var _ counter.GoRoutineCounter = (*waitGroupCounter)(nil)
45
46 func (wgc *waitGroupCounter) Add(delta int) {
47 klogV := klog.V(7)
48 if klogV.Enabled() {
49 var pcs [10]uintptr
50 nCallers := runtime.Callers(2, pcs[:])
51 frames := runtime.CallersFrames(pcs[:nCallers])
52 callers := make(stackExcerpt, 0, 10)
53 more := frames != nil
54 boundary := 1
55 for i := 0; more && len(callers) < cap(callers); i++ {
56 var frame runtime.Frame
57 frame, more = frames.Next()
58 fileParts := strings.Split(frame.File, "/")
59 isMine := strings.HasSuffix(frame.File, "/fairqueuing/testing/eventclock/fake.go")
60 if isMine {
61 boundary = 2
62 }
63 callers = append(callers, stackFrame{file: fileParts[len(fileParts)-1], line: frame.Line})
64 if i >= boundary && !isMine {
65 break
66 }
67 }
68 klogV.InfoS("Add", "counter", fmt.Sprintf("%p", wgc), "delta", delta, "callers", callers)
69 }
70 wgc.wg.Add(delta)
71 }
72
73 type stackExcerpt []stackFrame
74
75 type stackFrame struct {
76 file string
77 line int
78 }
79
80 var _ fmt.Stringer = stackExcerpt(nil)
81
82 func (se stackExcerpt) String() string {
83 var sb strings.Builder
84 sb.WriteString("[")
85 for i, sf := range se {
86 if i > 0 {
87 sb.WriteString(", ")
88 }
89 sb.WriteString(sf.file)
90 sb.WriteString(":")
91 sb.WriteString(strconv.FormatInt(int64(sf.line), 10))
92 }
93 sb.WriteString("]")
94 return sb.String()
95 }
96
97 func (wgc *waitGroupCounter) Wait() {
98 wgc.wg.Wait()
99 }
100
101 // Fake is one whose time does not pass implicitly but
102 // rather is explicitly set by invocations of its SetTime method.
103 // Each Fake has an associated GoRoutineCounter that is
104 // used to track associated activity.
105 // For the EventAfterDuration and EventAfterTime methods,
106 // the clock itself counts the start and stop of the EventFunc
107 // and the client is responsible for counting any suspend and
108 // resume internal to the EventFunc.
109 // The Sleep method must only be invoked from a goroutine that is
110 // counted in that GoRoutineCounter.
111 type Fake struct {
112 baseclocktest.FakePassiveClock
113
114 // waiters is a heap of waiting work, sorted by time
115 waiters eventWaiterHeap
116 waitersLock sync.RWMutex
117
118 // clientWG may be nil and if not supplies constraints on time
119 // passing in Run. The Run method will not pick a new time until
120 // this is nil or its counter is zero.
121 clientWG *waitGroupCounter
122
123 // fuzz is the amount of noise to add to scheduling. An event
124 // requested to run at time T will run at some time chosen
125 // uniformly at random from the interval [T, T+fuzz]; the upper
126 // bound is exclusive iff fuzz is non-zero.
127 fuzz time.Duration
128
129 // rand is the random number generator to use in fuzzing
130 rand *rand.Rand
131 }
132
133 var _ eventclock.Interface = &Fake{}
134
135 type eventWaiterHeap []eventWaiter
136
137 var _ heap.Interface = (*eventWaiterHeap)(nil)
138
139 type eventWaiter struct {
140 targetTime time.Time
141 f eventclock.EventFunc
142 }
143
144 // NewFake constructs a new fake event clock. The given `r *rand.Rand` must
145 // henceforth not be used for any other purpose. If `r` is nil then a
146 // fresh one will be constructed, seeded with the current real time.
147 // The clientWG can be `nil` and if not is used to let Run know about
148 // additional work that has to complete before time can advance.
149 func NewFake(t time.Time, fuzz time.Duration, r *rand.Rand) (*Fake, counter.GoRoutineCounter) {
150 grc := &waitGroupCounter{}
151
152 if r == nil {
153 r = rand.New(rand.NewSource(time.Now().UnixNano()))
154 r.Uint64()
155 r.Uint64()
156 r.Uint64()
157 }
158 return &Fake{
159 FakePassiveClock: *baseclocktest.NewFakePassiveClock(t),
160 clientWG: grc,
161 fuzz: fuzz,
162 rand: r,
163 }, grc
164 }
165
166 // GetNextTime returns the next time at which there is work scheduled,
167 // and a bool indicating whether there is any such time
168 func (fec *Fake) GetNextTime() (time.Time, bool) {
169 fec.waitersLock.RLock()
170 defer fec.waitersLock.RUnlock()
171 if len(fec.waiters) > 0 {
172 return fec.waiters[0].targetTime, true
173 }
174 return time.Time{}, false
175 }
176
177 // Run runs all the events scheduled, and all the events they
178 // schedule, and so on, until there are none scheduled or the limit is not
179 // nil and the next time would exceed the limit. The associated
180 // GoRoutineCounter gates the advancing of time. That is,
181 // time is not advanced until all the associated work is finished.
182 func (fec *Fake) Run(limit *time.Time) {
183 for {
184 fec.clientWG.Wait()
185 t, ok := fec.GetNextTime()
186 if !ok || limit != nil && t.After(*limit) {
187 break
188 }
189 fec.SetTime(t)
190 }
191 }
192
193 // SetTime sets the time and runs to completion all events that should
194 // be started by the given time --- including any further events they
195 // schedule
196 func (fec *Fake) SetTime(t time.Time) {
197 fec.FakePassiveClock.SetTime(t)
198 for {
199 foundSome := false
200 func() {
201 fec.waitersLock.Lock()
202 defer fec.waitersLock.Unlock()
203 // This loop is because events run at a given time may schedule more
204 // events to run at that or an earlier time.
205 // Events should not advance the clock. But just in case they do...
206 now := fec.Now()
207 for len(fec.waiters) > 0 && !now.Before(fec.waiters[0].targetTime) {
208 ew := heap.Pop(&fec.waiters).(eventWaiter)
209 fec.clientWG.Add(1)
210 go func(f eventclock.EventFunc, now time.Time) {
211 f(now)
212 fec.clientWG.Add(-1)
213 }(ew.f, now)
214 foundSome = true
215 }
216 }()
217 if !foundSome {
218 break
219 }
220 fec.clientWG.Wait()
221 }
222 }
223
224 // Sleep returns after the given duration has passed.
225 // Sleep must only be invoked in a goroutine that is counted
226 // in the Fake's associated GoRoutineCounter.
227 // Unlike the base FakeClock's Sleep, this method does not itself advance the clock
228 // but rather leaves that up to other actors (e.g., Run).
229 func (fec *Fake) Sleep(duration time.Duration) {
230 doneCh := make(chan struct{})
231 fec.EventAfterDuration(func(time.Time) {
232 fec.clientWG.Add(1)
233 close(doneCh)
234 }, duration)
235 fec.clientWG.Add(-1)
236 <-doneCh
237 }
238
239 // EventAfterDuration schedules the given function to be invoked once
240 // the given duration has passed.
241 func (fec *Fake) EventAfterDuration(f eventclock.EventFunc, d time.Duration) {
242 fec.waitersLock.Lock()
243 defer fec.waitersLock.Unlock()
244 now := fec.Now()
245 fd := time.Duration(float32(fec.fuzz) * fec.rand.Float32())
246 heap.Push(&fec.waiters, eventWaiter{targetTime: now.Add(d + fd), f: f})
247 }
248
249 // EventAfterTime schedules the given function to be invoked once
250 // the given time has arrived.
251 func (fec *Fake) EventAfterTime(f eventclock.EventFunc, t time.Time) {
252 fec.waitersLock.Lock()
253 defer fec.waitersLock.Unlock()
254 fd := time.Duration(float32(fec.fuzz) * fec.rand.Float32())
255 heap.Push(&fec.waiters, eventWaiter{targetTime: t.Add(fd), f: f})
256 }
257
258 func (ewh eventWaiterHeap) Len() int { return len(ewh) }
259
260 func (ewh eventWaiterHeap) Less(i, j int) bool { return ewh[i].targetTime.Before(ewh[j].targetTime) }
261
262 func (ewh eventWaiterHeap) Swap(i, j int) { ewh[i], ewh[j] = ewh[j], ewh[i] }
263
264 func (ewh *eventWaiterHeap) Push(x interface{}) {
265 *ewh = append(*ewh, x.(eventWaiter))
266 }
267
268 func (ewh *eventWaiterHeap) Pop() interface{} {
269 old := *ewh
270 n := len(old)
271 x := old[n-1]
272 *ewh = old[:n-1]
273 return x
274 }