istio

1
// Copyright 2017 Istio Authors
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
package cache
16

17
import (
18
	"runtime"
19
	"strconv"
20
	"sync"
21
	"testing"
22
	"time"
23
)
24

25
type cacheOp int
26

27
const (
28
	Get = iota
29
	Set
30
	Remove
31
	RemoveAll
32
)
33

34
func testCacheBasic(c Cache, t *testing.T) {
35
	cases := []struct {
36
		op     cacheOp
37
		key    string
38
		value  string
39
		result bool
40
		stats  Stats
41
	}{
42
		// try to get when the entry isn't present
43
		{Get, "X", "", false, Stats{Misses: 1}},
44

45
		// add an entry and make sure we can get it
46
		{Set, "X", "12", false, Stats{Misses: 1, Writes: 1}},
47
		{Get, "X", "12", true, Stats{Misses: 1, Writes: 1, Hits: 1}},
48
		{Get, "X", "12", true, Stats{Misses: 1, Writes: 1, Hits: 2}},
49

50
		// check interference between get/set
51
		{Get, "Y", "", false, Stats{Misses: 2, Writes: 1, Hits: 2}},
52
		{Set, "X", "23", false, Stats{Misses: 2, Writes: 2, Hits: 2}},
53
		{Get, "X", "23", true, Stats{Misses: 2, Writes: 2, Hits: 3}},
54
		{Set, "Y", "34", false, Stats{Misses: 2, Writes: 3, Hits: 3}},
55
		{Get, "X", "23", true, Stats{Misses: 2, Writes: 3, Hits: 4}},
56
		{Get, "Y", "34", true, Stats{Misses: 2, Writes: 3, Hits: 5}},
57

58
		// ensure removing X works and doesn't affect Y
59
		{Remove, "X", "", false, Stats{Misses: 2, Writes: 3, Hits: 5}},
60
		{Get, "X", "", false, Stats{Misses: 3, Writes: 3, Hits: 5}},
61
		{Get, "Y", "34", true, Stats{Misses: 3, Writes: 3, Hits: 6}},
62

63
		// make sure everything recovers from remove and then get/set
64
		{Remove, "X", "", false, Stats{Misses: 3, Writes: 3, Hits: 6}},
65
		{Remove, "Y", "", false, Stats{Misses: 3, Writes: 3, Hits: 6}},
66
		{Get, "Y", "", false, Stats{Misses: 4, Writes: 3, Hits: 6}},
67
		{Set, "X", "45", false, Stats{Misses: 4, Writes: 4, Hits: 6}},
68
		{Get, "X", "45", true, Stats{Misses: 4, Writes: 4, Hits: 7}},
69
		{Get, "Y", "", false, Stats{Misses: 5, Writes: 4, Hits: 7}},
70

71
		// remove a missing entry, should be a nop
72
		{Remove, "Z", "", false, Stats{Misses: 5, Writes: 4, Hits: 7}},
73

74
		// remove everything
75
		{Set, "A", "45", false, Stats{Misses: 5, Writes: 5, Hits: 7}},
76
		{Set, "B", "45", false, Stats{Misses: 5, Writes: 6, Hits: 7}},
77
		{RemoveAll, "", "", false, Stats{Misses: 5, Writes: 6, Hits: 7}},
78
		{Get, "A", "45", false, Stats{Misses: 6, Writes: 6, Hits: 7}},
79
		{Get, "B", "45", false, Stats{Misses: 7, Writes: 6, Hits: 7}},
80
	}
81

82
	for i, tc := range cases {
83
		t.Run(strconv.Itoa(i), func(t *testing.T) {
84
			switch tc.op {
85
			case Get:
86
				value, result := c.Get(tc.key)
87

88
				if result != tc.result {
89
					t.Errorf("Got result %v, expected %v", result, tc.result)
90
				}
91

92
				if result {
93
					str := value.(string)
94

95
					if str != tc.value {
96
						t.Errorf("Got value %v, expected %v", str, tc.value)
97
					}
98
				} else if value != nil {
99
					t.Errorf("Got value %v, expected nil", value)
100
				}
101

102
			case Set:
103
				c.Set(tc.key, tc.value)
104

105
			case Remove:
106
				c.Remove(tc.key)
107

108
			case RemoveAll:
109
				c.RemoveAll()
110
			}
111

112
			s := c.Stats()
113

114
			// removals are inconsistently tracked between implementations, so we ignore these here
115
			s.Removals = 0
116

117
			if s != tc.stats {
118
				t.Errorf("Got stats of %v, expected %v", s, tc.stats)
119
			}
120
		})
121
	}
122
}
123

124
func testCacheConcurrent(c Cache, t *testing.T) {
125
	wg := new(sync.WaitGroup)
126
	workers := runtime.NumCPU()
127
	wg.Add(workers)
128

129
	const numIters = 10000
130
	for i := 0; i < workers; i++ {
131
		workerNum := i
132
		go func() {
133
			for j := 0; j < numIters; j++ {
134

135
				key := "X" + strconv.Itoa(workerNum) + "." + strconv.Itoa(workerNum)
136
				c.Set(key, j)
137
				v, ok := c.Get(key)
138
				if !ok {
139
					t.Errorf("Got false for key %s, expecting true", key)
140
				} else if v.(int) != j {
141
					t.Errorf("Got %d for key %s, expecting %d", v, key, j)
142
				}
143
				c.Remove(key)
144
			}
145
			wg.Done()
146
		}()
147
	}
148
	wg.Wait()
149

150
	stats := c.Stats()
151
	if stats.Misses != 0 {
152
		t.Errorf("Got %d misses, expecting %d", stats.Misses, 0)
153
	}
154

155
	if stats.Hits != uint64(workers*numIters) {
156
		t.Errorf("Got %d hits, expecting %d", stats.Hits, workers*numIters)
157
	}
158

159
	if stats.Writes != uint64(workers*numIters) {
160
		t.Errorf("Got %d writes, expecting %d", stats.Writes, workers*numIters*2)
161
	}
162
}
163

164
// WARNING: This test expects the cache to have been created with no automatic eviction.
165
func testCacheExpiration(c ExpiringCache, evictExpired func(time.Time), t *testing.T) {
166
	now := time.Now()
167

168
	c.SetWithExpiration("EARLY", "123", 10*time.Millisecond)
169
	c.SetWithExpiration("LATER", "123", 20*time.Millisecond+123*time.Nanosecond)
170

171
	evictExpired(now)
172
	s := c.Stats()
173

174
	_, ok := c.Get("EARLY")
175
	if !ok {
176
		t.Errorf("Got no value, expected EARLY to be present")
177
	}
178

179
	_, ok = c.Get("LATER")
180
	if !ok {
181
		t.Errorf("Got no value, expected LATER to be present")
182
	}
183

184
	if s.Evictions != 0 {
185
		t.Errorf("Got %d evictions, expecting 0", s.Evictions)
186
	}
187

188
	evictExpired(now.Add(15 * time.Millisecond))
189
	s = c.Stats()
190

191
	_, ok = c.Get("EARLY")
192
	if ok {
193
		t.Errorf("Got value, expected EARLY to have been evicted")
194
	}
195

196
	_, ok = c.Get("LATER")
197
	if !ok {
198
		t.Errorf("Got no value, expected LATER to still be present")
199
	}
200

201
	if s.Evictions != 1 {
202
		t.Errorf("Got %d evictions, expecting 1", s.Evictions)
203
	}
204

205
	evictExpired(now.Add(25 * time.Millisecond))
206
	s = c.Stats()
207

208
	_, ok = c.Get("EARLY")
209
	if ok {
210
		t.Errorf("Got value, expected EARLY to have been evicted")
211
	}
212

213
	_, ok = c.Get("LATER")
214
	if ok {
215
		t.Errorf("Got value, expected LATER to have been evicted")
216
	}
217

218
	if s.Evictions != 2 {
219
		t.Errorf("Got %d evictions, expecting 2", s.Evictions)
220
	}
221
}
222

223
func testCacheEvictExpired(c ExpiringCache, t *testing.T) {
224
	c.SetWithExpiration("A", "A", 1*time.Millisecond)
225

226
	_, ok := c.Get("A")
227
	if !ok {
228
		t.Error("Got no entry, expecting it to be there")
229
	}
230

231
	time.Sleep(10 * time.Millisecond)
232
	c.EvictExpired()
233

234
	_, ok = c.Get("A")
235
	if ok {
236
		t.Error("Got an entry, expecting it to have been evicted")
237
	}
238
}
239

240
func testCacheEvicter(c ExpiringCache) {
241
	c.SetWithExpiration("A", "A", 1*time.Millisecond)
242

243
	// loop until eviction happens. If eviction doesn't happen, this loop will get stuck forever which is fine
244
	for {
245
		time.Sleep(10 * time.Millisecond)
246

247
		_, ok := c.Get("A")
248
		if !ok {
249
			// item disappeared, we're done
250
			return
251
		}
252
	}
253
}
254

255
func testCacheFinalizer(gate *sync.WaitGroup) {
256
	runtime.GC() //nolint: revive
257
	gate.Wait()
258
}
259

260
func benchmarkCacheGet(c Cache, b *testing.B) {
261
	c.Set("foo", "bar")
262

263
	b.ResetTimer()
264
	for i := 0; i < b.N; i++ {
265
		c.Get("foo")
266
	}
267
}
268

269
func benchmarkCacheGetConcurrent(c Cache, b *testing.B) {
270
	c.Set("foo1", "bar")
271
	c.Set("foo2", "bar")
272
	c.Set("foo3", "bar")
273
	c.Set("foo4", "bar")
274
	c.Set("foo5", "bar")
275
	c.Set("foo6", "bar")
276
	c.Set("foo7", "bar")
277

278
	wg := new(sync.WaitGroup)
279
	workers := runtime.NumCPU()
280
	each := b.N / workers
281
	wg.Add(workers)
282

283
	b.ResetTimer()
284
	for i := 0; i < workers; i++ {
285
		go func() {
286
			for j := 0; j < each; j++ {
287
				c.Get("foo1")
288
				c.Get("foo2")
289
				c.Get("foo3")
290
				c.Get("foo5")
291
				c.Get("foo6")
292
				c.Get("foo7")
293
				c.Get("foo8") // doesn't exist
294
			}
295
			wg.Done()
296
		}()
297
	}
298
	wg.Wait()
299
}
300

301
func benchmarkCacheSet(c Cache, b *testing.B) {
302
	b.ResetTimer()
303
	for i := 0; i < b.N; i++ {
304
		c.Set("foo", "bar")
305
	}
306
}
307

308
func benchmarkCacheSetConcurrent(c Cache, b *testing.B) {
309
	wg := new(sync.WaitGroup)
310
	workers := runtime.NumCPU()
311
	each := b.N / workers
312
	wg.Add(workers)
313

314
	b.ResetTimer()
315
	for i := 0; i < workers; i++ {
316
		go func() {
317
			for j := 0; j < each; j++ {
318
				c.Set("foo1", "bar")
319
				c.Set("foo2", "bar")
320
				c.Set("foo3", "bar")
321
				c.Set("foo4", "bar")
322
				c.Set("foo5", "bar")
323
				c.Set("foo6", "bar")
324
				c.Set("foo7", "bar")
325
			}
326
			wg.Done()
327
		}()
328
	}
329
	wg.Wait()
330
}
331

332
func benchmarkCacheGetSetConcurrent(c Cache, b *testing.B) {
333
	c.Set("foo1", "bar")
334
	c.Set("foo2", "bar")
335
	c.Set("foo3", "bar")
336
	c.Set("foo4", "bar")
337
	c.Set("foo5", "bar")
338
	c.Set("foo6", "bar")
339
	c.Set("foo7", "bar")
340

341
	wg := new(sync.WaitGroup)
342
	workers := runtime.NumCPU()
343
	each := b.N / workers
344
	wg.Add(workers)
345

346
	b.ResetTimer()
347
	for i := 0; i < workers; i++ {
348
		go func() {
349
			for j := 0; j < each; j++ {
350
				c.Get("foo1")
351
				c.Get("foo2")
352
				c.Get("foo3")
353
				c.Get("foo5")
354
				c.Get("foo6")
355
				c.Get("foo7")
356
				c.Get("foo8") // doesn't exist
357

358
				c.Set("foo1", "bar")
359
			}
360
			wg.Done()
361
		}()
362
	}
363
	wg.Wait()
364
}
365

366
func benchmarkCacheSetRemove(c Cache, b *testing.B) {
367
	b.ResetTimer()
368
	for i := 0; i < b.N; i++ {
369
		name := "foo" + strconv.Itoa(i)
370
		c.Set(name, "bar")
371
		c.Remove(name)
372
	}
373
}
374