Debian Codegraph @

pkg/util/flowcontrol/fairqueuing/queueset/fifo_list_test.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 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 }