| 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 |
} |