Debian Codegraph @

pkg/storage/cacher/watch_cache_interval_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 cacher
18
19 import (
20 "errors"
21 "fmt"
22 "reflect"
23 "sync"
24 "testing"
25
26 v1 "k8s.io/api/core/v1"
27 "k8s.io/apimachinery/pkg/fields"
28 "k8s.io/apimachinery/pkg/labels"
29 "k8s.io/apimachinery/pkg/runtime"
30 "k8s.io/apimachinery/pkg/watch"
31 "k8s.io/client-go/tools/cache"
32 )
33
34 func intervalFromEvents(events []*watchCacheEvent) *watchCacheInterval {
35 startIndex, endIndex, locker := 0, len(events), &sync.Mutex{}
36 indexer := func(i int) *watchCacheEvent {
37 if len(events) == 0 {
38 return nil
39 }
40 return events[i]
41 }
42 indexValidator := func(_ int) bool { return true }
43
44 return newCacheInterval(startIndex, endIndex, indexer, indexValidator, 0, locker)
45 }
46
47 func bufferFromEvents(events []*watchCacheEvent) *watchCacheIntervalBuffer {
48 wcib := &watchCacheIntervalBuffer{
49 buffer: make([]*watchCacheEvent, bufferSize),
50 startIndex: 0,
51 endIndex: len(events),
52 }
53 copy(wcib.buffer, events)
54
55 return wcib
56 }
57
58 func generateEvents(start, end int) []*watchCacheEvent {
59 n := end - start
60 events := make([]*watchCacheEvent, n)
61 for i := 0; i < n; i++ {
62 events[i] = &watchCacheEvent{
63 Type: watch.Added,
64 Object: makeTestPod(fmt.Sprintf("pod%d", start+i), uint64(start+i)),
65 }
66 }
67 return events
68 }
69
70 func verifyEvent(ok bool, event, expectedEvent *watchCacheEvent) error {
71 if !ok {
72 return fmt.Errorf("expected event: %#v, got no event", expectedEvent)
73 }
74
75 if event == nil {
76 return fmt.Errorf("unexpected nil event, expected: %#v", expectedEvent)
77 }
78
79 if !reflect.DeepEqual(event, expectedEvent) {
80 return fmt.Errorf("expected %v, got %v", *event, *expectedEvent)
81 }
82
83 return nil
84 }
85
86 func verifyNoEvent(ok bool, event *watchCacheEvent) error {
87 if ok {
88 return errors.New("unexpected bool value indicating buffer is not empty")
89 }
90 if event != nil {
91 return fmt.Errorf("unexpected event received, expected: nil, got %v", *event)
92 }
93
94 return nil
95 }
96
97 func TestIntervalBufferIsFull(t *testing.T) {
98 cases := []struct {
99 endIndex int
100 expected bool
101 }{
102 {endIndex: bufferSize - 1, expected: false},
103 {endIndex: bufferSize, expected: true},
104 {endIndex: bufferSize + 1, expected: true},
105 }
106
107 for _, c := range cases {
108 wcib := &watchCacheIntervalBuffer{endIndex: c.endIndex}
109 actual := wcib.isFull()
110 if actual != c.expected {
111 t.Errorf("expected %v, got %v", c.expected, actual)
112 }
113 }
114 }
115
116 func TestIntervalBufferIsEmpty(t *testing.T) {
117 cases := []struct {
118 startIndex int
119 endIndex int
120 expected bool
121 }{
122 {startIndex: 0, endIndex: 10, expected: false},
123 {startIndex: 5, endIndex: 20, expected: false},
124 {startIndex: 50, endIndex: 50, expected: true},
125 }
126
127 for _, c := range cases {
128 wcib := &watchCacheIntervalBuffer{
129 startIndex: c.startIndex,
130 endIndex: c.endIndex,
131 }
132 actual := wcib.isEmpty()
133 if actual != c.expected {
134 t.Errorf("expected %v, got %v", c.expected, actual)
135 }
136 }
137 }
138
139 func TestIntervalBufferNext(t *testing.T) {
140 cases := []struct {
141 name string
142 events []*watchCacheEvent
143 }{
144 {
145 name: "buffer has elements",
146 events: []*watchCacheEvent{
147 {Type: watch.Added, Object: makeTestPod("pod1", 1)},
148 {Type: watch.Added, Object: makeTestPod("pod2", 2)},
149 {Type: watch.Modified, Object: makeTestPod("pod3", 3)},
150 },
151 },
152 {
153 name: "buffer is empty",
154 events: []*watchCacheEvent{},
155 },
156 }
157
158 for _, c := range cases {
159 t.Run(c.name, func(t *testing.T) {
160 wcib := bufferFromEvents(c.events)
161 for i := 0; i < len(c.events); i++ {
162 event, ok := wcib.next()
163 if err := verifyEvent(ok, event, c.events[i]); err != nil {
164 t.Error(err)
165 }
166 }
167 event, ok := wcib.next()
168 if err := verifyNoEvent(ok, event); err != nil {
169 t.Error(err)
170 }
171 })
172 }
173 }
174
175 func TestFillBuffer(t *testing.T) {
176 cases := []struct {
177 name string
178 numEventsToFill int
179 }{
180 {
181 name: "no events to put in buffer",
182 numEventsToFill: 0,
183 },
184 {
185 name: "less than bufferSize events to put in buffer",
186 numEventsToFill: 5,
187 },
188 {
189 name: "equal to bufferSize events to put in buffer",
190 numEventsToFill: bufferSize,
191 },
192 {
193 name: "greater than bufferSize events to put in buffer",
194 numEventsToFill: bufferSize + 5,
195 },
196 }
197
198 for _, c := range cases {
199 t.Run(c.name, func(t *testing.T) {
200 events := generateEvents(0, c.numEventsToFill)
201 wci := intervalFromEvents(events)
202
203 for i := 0; i < len(events); i++ {
204 if i%bufferSize == 0 {
205 wci.fillBuffer()
206 }
207 event, ok := wci.buffer.next()
208 if err := verifyEvent(ok, event, events[i]); err != nil {
209 t.Error(err)
210 }
211 // If we have already received bufferSize number of events,
212 // buffer should be empty and we should receive no event.
213 if i%bufferSize == bufferSize-1 {
214 event, ok := wci.buffer.next()
215 if err := verifyNoEvent(ok, event); err != nil {
216 t.Error(err)
217 }
218 }
219 }
220 // buffer should be empty and return no event.
221 event, ok := wci.buffer.next()
222 if err := verifyNoEvent(ok, event); err != nil {
223 t.Error(err)
224 }
225 // Buffer should be empty now, an additional fillBuffer()
226 // should make no difference.
227 wci.fillBuffer()
228 event, ok = wci.buffer.next()
229 if err := verifyNoEvent(ok, event); err != nil {
230 t.Error(err)
231 }
232 })
233 }
234 }
235
236 func TestCacheIntervalNextFromWatchCache(t *testing.T) {
237 // Have the capacity such that it facilitates
238 // filling the interval buffer more than once
239 // completely and then some more - 10 here is
240 // arbitrary.
241 const capacity = 2*bufferSize + 10
242
243 cases := []struct {
244 name string
245 // The total number of events that the watch
246 // cache will be populated with to start with.
247 eventsAddedToWatchcache int
248 intervalStartIndex int
249 }{
250 {
251 name: "watchCache empty, eventsAddedToWatchcache = 0",
252 eventsAddedToWatchcache: 0,
253 intervalStartIndex: 0,
254 },
255 {
256 name: "watchCache partially propagated, eventsAddedToWatchcache < capacity",
257 eventsAddedToWatchcache: bufferSize,
258 intervalStartIndex: 0,
259 },
260 {
261 name: "watchCache partially propagated, eventsAddedToWatchcache < capacity, intervalStartIndex at some offset",
262 eventsAddedToWatchcache: bufferSize,
263 intervalStartIndex: 5,
264 },
265 {
266 name: "watchCache fully propagated, eventsAddedToWatchcache = capacity",
267 eventsAddedToWatchcache: capacity,
268 intervalStartIndex: 0,
269 },
270 {
271 name: "watchCache fully propagated, eventsAddedToWatchcache = capacity, intervalStartIndex at some offset",
272 eventsAddedToWatchcache: capacity,
273 intervalStartIndex: 5,
274 },
275 {
276 name: "watchCache over propagated, eventsAddedToWatchcache > capacity",
277 eventsAddedToWatchcache: capacity + bufferSize,
278 intervalStartIndex: 0,
279 },
280 {
281 name: "watchCache over propagated, eventsAddedToWatchcache > capacity, intervalStartIndex at some offset",
282 eventsAddedToWatchcache: capacity + bufferSize,
283 intervalStartIndex: 5,
284 },
285 }
286
287 for _, c := range cases {
288 t.Run(c.name, func(t *testing.T) {
289 wc := newTestWatchCache(capacity, DefaultEventFreshDuration, &cache.Indexers{})
290 defer wc.Stop()
291 for i := 0; i < c.eventsAddedToWatchcache; i++ {
292 wc.Add(makeTestPod(fmt.Sprintf("pod%d", i), uint64(i)))
293 }
294 indexerFunc := func(i int) *watchCacheEvent {
295 return wc.cache[i%wc.capacity]
296 }
297
298 wci := newCacheInterval(
299 c.intervalStartIndex,
300 wc.endIndex,
301 indexerFunc,
302 wc.isIndexValidLocked,
303 wc.resourceVersion,
304 &wc.RWMutex,
305 )
306
307 numExpectedEvents := wc.endIndex - c.intervalStartIndex
308 for i := 0; i < numExpectedEvents; i++ {
309 // Simulate and test interval invalidation iff
310 // the watchCache itself is not empty.
311 if c.eventsAddedToWatchcache > 0 {
312 // The points at which we want to artificially
313 // invalidate the interval and test its behaviour
314 // should be multiples of bufferSize. This is because
315 // invalidation only needs to be checked when we are
316 // copying over events from the underlying watch cache,
317 // i.e. freshly filling in the interval buffer.
318 if i%bufferSize == 0 && i != c.eventsAddedToWatchcache {
319 originalCacheStartIndex := wc.startIndex
320 wc.startIndex = wci.startIndex + 1
321 event, err := wci.Next()
322 if err == nil {
323 t.Errorf("expected non-nil error")
324 }
325 if event != nil {
326 t.Errorf("expected nil event, got %v", *event)
327 }
328 // Restore startIndex.
329 wc.startIndex = originalCacheStartIndex
330 }
331 }
332
333 // Check if the state of the interval buffer is as expected.
334 // The interval buffer can be empty either when received is
335 // either a multiple of bufferSize (after one complete fill)
336 // or when received is equal to the number of expected events.
337 // The latter happens when partial filling occurs and no more
338 // events are left post the partial fill.
339 if wci.buffer.isEmpty() != (i%bufferSize == 0 || i == numExpectedEvents) {
340 t.Error("expected empty interval buffer")
341 return
342 }
343
344 event, err := wci.Next()
345 if err != nil {
346 t.Errorf("unexpected error: %v", err)
347 return
348 }
349
350 expectedIndex := (c.intervalStartIndex + i) % wc.capacity
351 expectedEvent := wc.cache[expectedIndex]
352 if err := verifyEvent(true, event, expectedEvent); err != nil {
353 t.Error(err)
354 }
355 }
356 event, err := wci.Next()
357 ok := err != nil
358 if err := verifyNoEvent(ok, event); err != nil {
359 t.Error(err)
360 }
361 })
362 }
363 }
364
365 func TestCacheIntervalNextFromStore(t *testing.T) {
366 getAttrsFunc := func(obj runtime.Object) (labels.Set, fields.Set, error) {
367 pod, ok := obj.(*v1.Pod)
368 if !ok {
369 return nil, nil, fmt.Errorf("not a pod")
370 }
371 return labels.Set(pod.Labels), fields.Set{"spec.nodeName": pod.Spec.NodeName}, nil
372 }
373 const numEvents = 50
374 store := cache.NewIndexer(storeElementKey, storeElementIndexers(nil))
375 events := make(map[string]*watchCacheEvent)
376 var rv uint64 = 1 // arbitrary number; rv till which the watch cache has progressed.
377
378 for i := 0; i < numEvents; i++ {
379 elem := makeTestStoreElement(makeTestPod(fmt.Sprintf("pod%d", i), uint64(i)))
380 objLabels, objFields, err := getAttrsFunc(elem.Object)
381 if err != nil {
382 t.Fatal(err)
383 }
384 events[elem.Key] = &watchCacheEvent{
385 Type: watch.Added,
386 Object: elem.Object,
387 ObjLabels: objLabels,
388 ObjFields: objFields,
389 Key: elem.Key,
390 ResourceVersion: rv,
391 }
392 store.Add(elem)
393 }
394
395 wci, err := newCacheIntervalFromStore(rv, store, "", false)
396 if err != nil {
397 t.Fatal(err)
398 }
399
400 for i := 0; i < numEvents; i++ {
401 // The interval buffer can never be empty unless
402 // all elements obtained through List() have been
403 // returned.
404 if wci.buffer.isEmpty() && i != numEvents {
405 t.Fatal("expected non-empty interval buffer")
406 }
407 event, err := wci.Next()
408 if err != nil {
409 t.Fatalf("unexpected error: %v", err)
410 }
411 if event == nil {
412 t.Error("unexpected nil event")
413 break
414 }
415 expectedEvent, ok := events[event.Key]
416 if !ok {
417 t.Fatalf("event with key %s not found", event.Key)
418 }
419 if !reflect.DeepEqual(event, expectedEvent) {
420 t.Errorf("expected: %v, got %v", *events[event.Key], *event)
421 }
422 }
423
424 // The interval's buffer should now be empty.
425 if !wci.buffer.isEmpty() {
426 t.Error("expected cache interval's buffer to be empty")
427 }
428 }