| 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 queueset |
| 18 |
|
| 19 |
import ( |
| 20 |
"math/rand" |
| 21 |
"reflect" |
| 22 |
"testing" |
| 23 |
"time" |
| 24 |
|
| 25 |
"github.com/google/go-cmp/cmp" |
| 26 |
fcrequest "k8s.io/apiserver/pkg/util/flowcontrol/request" |
| 27 |
) |
| 28 |
|
| 29 |
func TestFIFOWithEnqueueDequeueSingleRequest(t *testing.T) { |
| 30 |
req := &request{} |
| 31 |
|
| 32 |
list := newRequestFIFO() |
| 33 |
list.Enqueue(req) |
| 34 |
|
| 35 |
reqGot, ok := list.Dequeue() |
| 36 |
if !ok { |
| 37 |
t.Errorf("Expected true, but got: %t", ok) |
| 38 |
} |
| 39 |
if req != reqGot { |
| 40 |
t.Errorf("Expected dequued request: (%p), but got: (%p)", req, reqGot) |
| 41 |
} |
| 42 |
if list.Length() != 0 { |
| 43 |
t.Errorf("Expected length: %d, but got: %d)", 0, list.Length()) |
| 44 |
} |
| 45 |
} |
| 46 |
|
| 47 |
func TestFIFOWithEnqueueDequeueMultipleRequests(t *testing.T) { |
| 48 |
arrival := []*request{{}, {}, {}, {}, {}, {}} |
| 49 |
|
| 50 |
list := newRequestFIFO() |
| 51 |
for i := range arrival { |
| 52 |
list.Enqueue(arrival[i]) |
| 53 |
} |
| 54 |
|
| 55 |
dequeued := make([]*request, 0) |
| 56 |
for list.Length() > 0 { |
| 57 |
req, _ := list.Dequeue() |
| 58 |
dequeued = append(dequeued, req) |
| 59 |
} |
| 60 |
|
| 61 |
verifyOrder(t, arrival, dequeued) |
| 62 |
} |
| 63 |
|
| 64 |
func TestFIFOWithEnqueueDequeueSomeRequestsRemainInQueue(t *testing.T) { |
| 65 |
list := newRequestFIFO() |
| 66 |
|
| 67 |
arrival := []*request{{}, {}, {}, {}, {}, {}} |
| 68 |
half := len(arrival) / 2 |
| 69 |
for i := range arrival { |
| 70 |
list.Enqueue(arrival[i]) |
| 71 |
} |
| 72 |
|
| 73 |
dequeued := make([]*request, 0) |
| 74 |
for i := 0; i < half; i++ { |
| 75 |
req, _ := list.Dequeue() |
| 76 |
dequeued = append(dequeued, req) |
| 77 |
} |
| 78 |
|
| 79 |
verifyOrder(t, arrival[:half], dequeued) |
| 80 |
} |
| 81 |
|
| 82 |
func TestFIFOWithRemoveMultipleRequestsInArrivalOrder(t *testing.T) { |
| 83 |
list := newRequestFIFO() |
| 84 |
|
| 85 |
arrival := []*request{{}, {}, {}, {}, {}, {}} |
| 86 |
removeFn := make([]removeFromFIFOFunc, 0) |
| 87 |
for i := range arrival { |
| 88 |
removeFn = append(removeFn, list.Enqueue(arrival[i])) |
| 89 |
} |
| 90 |
|
| 91 |
expected := append([]*request{}, arrival...) |
| 92 |
for idx, f := range removeFn { |
| 93 |
if a := f(); a != arrival[idx] { |
| 94 |
t.Errorf("Removal %d returned %v instead of expected pointer", idx, a) |
| 95 |
} |
| 96 |
if a := f(); a != nil { |
| 97 |
t.Errorf("Redundant removal %d returned %v instead of expected nil", idx, a) |
| 98 |
} |
| 99 |
expected = expected[1:] |
| 100 |
actual := walkAll(list) |
| 101 |
verifyOrder(t, expected, actual) |
| 102 |
} |
| 103 |
|
| 104 |
if list.Length() != 0 { |
| 105 |
t.Errorf("Expected length: %d, but got: %d)", 0, list.Length()) |
| 106 |
} |
| 107 |
} |
| 108 |
|
| 109 |
func TestFIFORemoveFromFIFOFunc(t *testing.T) { |
| 110 |
list := newRequestFIFO() |
| 111 |
reqWant := &request{} |
| 112 |
removeFn := list.Enqueue(reqWant) |
| 113 |
|
| 114 |
reqGot := removeFn() |
| 115 |
if reqWant != reqGot { |
| 116 |
t.Errorf("Expected request identity: %p, but got: %p)", reqWant, reqGot) |
| 117 |
} |
| 118 |
|
| 119 |
if got := removeFn(); got != nil { |
| 120 |
t.Errorf("Expected a nil request, but got: %v)", got) |
| 121 |
} |
| 122 |
} |
| 123 |
|
| 124 |
func TestFIFOWithRemoveMultipleRequestsInRandomOrder(t *testing.T) { |
| 125 |
list := newRequestFIFO() |
| 126 |
|
| 127 |
arrival := []*request{{}, {}, {}, {}, {}, {}} |
| 128 |
removeFn := make([]removeFromFIFOFunc, 0) |
| 129 |
for i := range arrival { |
| 130 |
removeFn = append(removeFn, list.Enqueue(arrival[i])) |
| 131 |
} |
| 132 |
|
| 133 |
expected := append([]*request{}, arrival...) |
| 134 |
r := rand.New(rand.NewSource(time.Now().UnixNano())) |
| 135 |
for range arrival { |
| 136 |
idx := r.Intn(len(expected)) |
| 137 |
t.Logf("Removing random index %d", idx) |
| 138 |
if e, a := expected[idx], removeFn[idx](); e != a { |
| 139 |
t.Errorf("Removal of %d returned %v instead of expected pointer %v", idx, a, e) |
| 140 |
} |
| 141 |
if e, a := (*request)(nil), removeFn[idx](); e != a { |
| 142 |
t.Errorf("Redundant removal of %d returned %v instead of expected nil pointer", idx, a) |
| 143 |
} |
| 144 |
expected = append(expected[:idx], expected[idx+1:]...) |
| 145 |
actual := walkAll(list) |
| 146 |
verifyOrder(t, expected, actual) |
| 147 |
removeFn = append(removeFn[:idx], removeFn[idx+1:]...) |
| 148 |
} |
| 149 |
if list.Length() != 0 { |
| 150 |
t.Errorf("Expected length: %d, but got: %d)", 0, list.Length()) |
| 151 |
} |
| 152 |
} |
| 153 |
|
| 154 |
func TestFIFOWithRemoveIsIdempotent(t *testing.T) { |
| 155 |
list := newRequestFIFO() |
| 156 |
|
| 157 |
arrival := []*request{{}, {}, {}, {}} |
| 158 |
removeFn := make([]removeFromFIFOFunc, 0) |
| 159 |
for i := range arrival { |
| 160 |
removeFn = append(removeFn, list.Enqueue(arrival[i])) |
| 161 |
} |
| 162 |
|
| 163 |
// pick one request to be removed at random |
| 164 |
r := rand.New(rand.NewSource(time.Now().UnixNano())) |
| 165 |
randomIndex := r.Intn(len(removeFn)) |
| 166 |
t.Logf("Random remove index: %d", randomIndex) |
| 167 |
|
| 168 |
// remove the request from the fifo twice, we expect it to be idempotent |
| 169 |
removeFn[randomIndex]() |
| 170 |
removeFn[randomIndex]() |
| 171 |
|
| 172 |
lengthExpected := len(arrival) - 1 |
| 173 |
if lengthExpected != list.Length() { |
| 174 |
t.Errorf("Expected length: %d, but got: %d)", lengthExpected, list.Length()) |
| 175 |
} |
| 176 |
|
| 177 |
orderExpected := append(arrival[0:randomIndex], arrival[randomIndex+1:]...) |
| 178 |
remainingRequests := walkAll(list) |
| 179 |
verifyOrder(t, orderExpected, remainingRequests) |
| 180 |
} |
| 181 |
|
| 182 |
func TestFIFOQueueWorkEstimate(t *testing.T) { |
| 183 |
qs := &queueSet{estimatedServiceDuration: time.Second} |
| 184 |
list := newRequestFIFO() |
| 185 |
|
| 186 |
update := func(we *queueSum, req *request, multiplier int) { |
| 187 |
we.InitialSeatsSum += multiplier * req.InitialSeats() |
| 188 |
we.MaxSeatsSum += multiplier * req.MaxSeats() |
| 189 |
we.TotalWorkSum += fcrequest.SeatSeconds(multiplier) * req.totalWork() |
| 190 |
} |
| 191 |
|
| 192 |
assert := func(t *testing.T, want, got *queueSum) { |
| 193 |
if !reflect.DeepEqual(want, got) { |
| 194 |
t.Errorf("Expected queue work estimate to match, diff: %s", cmp.Diff(want, got)) |
| 195 |
} |
| 196 |
} |
| 197 |
|
| 198 |
newRequest := func(initialSeats, finalSeats uint64, additionalLatency time.Duration) *request { |
| 199 |
return &request{workEstimate: qs.completeWorkEstimate(&fcrequest.WorkEstimate{ |
| 200 |
InitialSeats: initialSeats, |
| 201 |
FinalSeats: finalSeats, |
| 202 |
AdditionalLatency: additionalLatency, |
| 203 |
})} |
| 204 |
} |
| 205 |
arrival := []*request{ |
| 206 |
newRequest(1, 3, time.Second), |
| 207 |
newRequest(2, 2, 2*time.Second), |
| 208 |
newRequest(3, 1, 3*time.Second), |
| 209 |
} |
| 210 |
removeFn := make([]removeFromFIFOFunc, 0) |
| 211 |
|
| 212 |
queueSumExpected := queueSum{} |
| 213 |
for i := range arrival { |
| 214 |
req := arrival[i] |
| 215 |
removeFn = append(removeFn, list.Enqueue(req)) |
| 216 |
update(&queueSumExpected, req, 1) |
| 217 |
|
| 218 |
workEstimateGot := list.QueueSum() |
| 219 |
assert(t, &queueSumExpected, &workEstimateGot) |
| 220 |
} |
| 221 |
|
| 222 |
// NOTE: the test expects the request and the remove func to be at the same index |
| 223 |
for i := range removeFn { |
| 224 |
req := arrival[i] |
| 225 |
removeFn[i]() |
| 226 |
|
| 227 |
update(&queueSumExpected, req, -1) |
| 228 |
|
| 229 |
workEstimateGot := list.QueueSum() |
| 230 |
assert(t, &queueSumExpected, &workEstimateGot) |
| 231 |
|
| 232 |
// check idempotency |
| 233 |
removeFn[i]() |
| 234 |
|
| 235 |
workEstimateGot = list.QueueSum() |
| 236 |
assert(t, &queueSumExpected, &workEstimateGot) |
| 237 |
} |
| 238 |
|
| 239 |
// Check second type of idempotency: Dequeue + removeFn. |
| 240 |
for i := range arrival { |
| 241 |
req := arrival[i] |
| 242 |
removeFn[i] = list.Enqueue(req) |
| 243 |
|
| 244 |
update(&queueSumExpected, req, 1) |
| 245 |
} |
| 246 |
|
| 247 |
for i := range arrival { |
| 248 |
// we expect Dequeue to pop the oldest request that should |
| 249 |
// have the lowest index as well. |
| 250 |
req := arrival[i] |
| 251 |
|
| 252 |
if _, ok := list.Dequeue(); !ok { |
| 253 |
t.Errorf("Unexpected failed dequeue: %d", i) |
| 254 |
} |
| 255 |
|
| 256 |
update(&queueSumExpected, req, -1) |
| 257 |
|
| 258 |
queueSumGot := list.QueueSum() |
| 259 |
assert(t, &queueSumExpected, &queueSumGot) |
| 260 |
|
| 261 |
removeFn[i]() |
| 262 |
|
| 263 |
queueSumGot = list.QueueSum() |
| 264 |
assert(t, &queueSumExpected, &queueSumGot) |
| 265 |
} |
| 266 |
} |
| 267 |
|
| 268 |
func TestFIFOWithWalk(t *testing.T) { |
| 269 |
list := newRequestFIFO() |
| 270 |
|
| 271 |
arrival := []*request{{}, {}, {}, {}, {}, {}} |
| 272 |
for i := range arrival { |
| 273 |
list.Enqueue(arrival[i]) |
| 274 |
} |
| 275 |
|
| 276 |
visited := walkAll(list) |
| 277 |
|
| 278 |
verifyOrder(t, arrival, visited) |
| 279 |
} |
| 280 |
|
| 281 |
func verifyOrder(t *testing.T, expected, actual []*request) { |
| 282 |
if len(expected) != len(actual) { |
| 283 |
t.Fatalf("Expected slice length: %d, but got: %d", len(expected), len(actual)) |
| 284 |
} |
| 285 |
for i := range expected { |
| 286 |
if expected[i] != actual[i] { |
| 287 |
t.Errorf("Dequeue order mismatch, expected request: (%p), but got: (%p)", expected[i], actual[i]) |
| 288 |
} |
| 289 |
} |
| 290 |
} |
| 291 |
|
| 292 |
func walkAll(l fifo) []*request { |
| 293 |
visited := make([]*request, 0) |
| 294 |
l.Walk(func(req *request) bool { |
| 295 |
visited = append(visited, req) |
| 296 |
return true |
| 297 |
}) |
| 298 |
|
| 299 |
return visited |
| 300 |
} |