1 /******************************************************************************
2 *
3 * Copyright 2020 Google, Inc.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at:
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 ******************************************************************************/
18
19 #include <base/logging.h>
20 #include <gmock/gmock.h>
21 #include <gtest/gtest.h>
22 #include <chrono>
23 #include <limits>
24
25 #include "common/lru.h"
26
27 namespace testing {
28
29 using bluetooth::common::LegacyLruCache;
30
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheMainTest1)31 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheMainTest1) {
32 int* value = new int(0);
33 LegacyLruCache<int, int> cache(3, "testing"); // capacity = 3;
34 cache.Put(1, 10);
35 EXPECT_EQ(cache.Size(), 1);
36 EXPECT_FALSE(cache.Put(2, 20));
37 EXPECT_FALSE(cache.Put(3, 30));
38 EXPECT_EQ(cache.Size(), 3);
39
40 // 1, 2, 3 should be in cache
41 EXPECT_TRUE(cache.Get(1, value));
42 EXPECT_EQ(*value, 10);
43 EXPECT_TRUE(cache.Get(2, value));
44 EXPECT_EQ(*value, 20);
45 EXPECT_TRUE(cache.Get(3, value));
46 EXPECT_EQ(*value, 30);
47 EXPECT_EQ(cache.Size(), 3);
48
49 EXPECT_THAT(cache.Put(4, 40), Optional(Pair(1, 10)));
50 // 2, 3, 4 should be in cache, 1 is evicted
51 EXPECT_FALSE(cache.Get(1, value));
52 EXPECT_TRUE(cache.Get(4, value));
53 EXPECT_EQ(*value, 40);
54 EXPECT_TRUE(cache.Get(2, value));
55 EXPECT_EQ(*value, 20);
56 EXPECT_TRUE(cache.Get(3, value));
57 EXPECT_EQ(*value, 30);
58
59 EXPECT_THAT(cache.Put(5, 50), Optional(Pair(4, 40)));
60 EXPECT_EQ(cache.Size(), 3);
61 // 2, 3, 5 should be in cache, 4 is evicted
62
63 EXPECT_TRUE(cache.Remove(3));
64 EXPECT_FALSE(cache.Put(6, 60));
65 // 2, 5, 6 should be in cache
66
67 EXPECT_FALSE(cache.Get(3, value));
68 EXPECT_FALSE(cache.Get(4, value));
69 EXPECT_TRUE(cache.Get(2, value));
70 EXPECT_EQ(*value, 20);
71 EXPECT_TRUE(cache.Get(5, value));
72 EXPECT_EQ(*value, 50);
73 EXPECT_TRUE(cache.Get(6, value));
74 EXPECT_EQ(*value, 60);
75 }
76
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheMainTest2)77 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheMainTest2) {
78 int* value = new int(0);
79 LegacyLruCache<int, int> cache(2, "testing"); // size = 2;
80 EXPECT_FALSE(cache.Put(1, 10));
81 EXPECT_FALSE(cache.Put(2, 20));
82 EXPECT_THAT(cache.Put(3, 30), Optional(Pair(1, 10)));
83 EXPECT_FALSE(cache.Put(2, 200));
84 EXPECT_EQ(cache.Size(), 2);
85 // 3, 2 should be in cache
86
87 EXPECT_FALSE(cache.HasKey(1));
88 EXPECT_TRUE(cache.Get(2, value));
89 EXPECT_EQ(*value, 200);
90 EXPECT_TRUE(cache.Get(3, value));
91 EXPECT_EQ(*value, 30);
92
93 EXPECT_THAT(cache.Put(4, 40), Optional(Pair(2, 200)));
94 // 3, 4 should be in cache
95
96 EXPECT_FALSE(cache.HasKey(2));
97 EXPECT_TRUE(cache.Get(3, value));
98 EXPECT_EQ(*value, 30);
99 EXPECT_TRUE(cache.Get(4, value));
100 EXPECT_EQ(*value, 40);
101
102 EXPECT_TRUE(cache.Remove(4));
103 EXPECT_EQ(cache.Size(), 1);
104 cache.Put(2, 2000);
105 // 3, 2 should be in cache
106
107 EXPECT_FALSE(cache.HasKey(4));
108 EXPECT_TRUE(cache.Get(3, value));
109 EXPECT_EQ(*value, 30);
110 EXPECT_TRUE(cache.Get(2, value));
111 EXPECT_EQ(*value, 2000);
112
113 EXPECT_TRUE(cache.Remove(2));
114 EXPECT_TRUE(cache.Remove(3));
115 cache.Put(5, 50);
116 cache.Put(1, 100);
117 cache.Put(1, 1000);
118 EXPECT_EQ(cache.Size(), 2);
119 // 1, 5 should be in cache
120
121 EXPECT_FALSE(cache.HasKey(2));
122 EXPECT_FALSE(cache.HasKey(3));
123 EXPECT_TRUE(cache.Get(1, value));
124 EXPECT_EQ(*value, 1000);
125 EXPECT_TRUE(cache.Get(5, value));
126 EXPECT_EQ(*value, 50);
127 }
128
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheFindTest)129 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheFindTest) {
130 LegacyLruCache<int, int> cache(10, "testing");
131 cache.Put(1, 10);
132 cache.Put(2, 20);
133 int value = 0;
134 EXPECT_TRUE(cache.Get(1, &value));
135 EXPECT_EQ(value, 10);
136 auto value_ptr = cache.Find(1);
137 EXPECT_NE(value_ptr, nullptr);
138 *value_ptr = 20;
139 EXPECT_TRUE(cache.Get(1, &value));
140 EXPECT_EQ(value, 20);
141 cache.Put(1, 40);
142 EXPECT_EQ(*value_ptr, 40);
143 EXPECT_EQ(cache.Find(10), nullptr);
144 }
145
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheGetTest)146 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheGetTest) {
147 LegacyLruCache<int, int> cache(10, "testing");
148 cache.Put(1, 10);
149 cache.Put(2, 20);
150 int value = 0;
151 EXPECT_TRUE(cache.Get(1, &value));
152 EXPECT_EQ(value, 10);
153 EXPECT_TRUE(cache.HasKey(1));
154 EXPECT_TRUE(cache.HasKey(2));
155 EXPECT_FALSE(cache.HasKey(3));
156 EXPECT_FALSE(cache.Get(3, &value));
157 EXPECT_EQ(value, 10);
158 }
159
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheRemoveTest)160 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheRemoveTest) {
161 LegacyLruCache<int, int> cache(10, "testing");
162 for (int key = 0; key <= 30; key++) {
163 cache.Put(key, key * 100);
164 }
165 for (int key = 0; key <= 20; key++) {
166 EXPECT_FALSE(cache.HasKey(key));
167 }
168 for (int key = 21; key <= 30; key++) {
169 EXPECT_TRUE(cache.HasKey(key));
170 }
171 for (int key = 21; key <= 30; key++) {
172 EXPECT_TRUE(cache.Remove(key));
173 }
174 for (int key = 21; key <= 30; key++) {
175 EXPECT_FALSE(cache.HasKey(key));
176 }
177 }
178
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheClearTest)179 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheClearTest) {
180 LegacyLruCache<int, int> cache(10, "testing");
181 for (int key = 0; key < 10; key++) {
182 cache.Put(key, key * 100);
183 }
184 for (int key = 0; key < 10; key++) {
185 EXPECT_TRUE(cache.HasKey(key));
186 }
187 cache.Clear();
188 for (int key = 0; key < 10; key++) {
189 EXPECT_FALSE(cache.HasKey(key));
190 }
191
192 for (int key = 0; key < 10; key++) {
193 cache.Put(key, key * 1000);
194 }
195 for (int key = 0; key < 10; key++) {
196 EXPECT_TRUE(cache.HasKey(key));
197 }
198 }
199
TEST(BluetoothLegacyLruCacheTest,LegacyLruCachePressureTest)200 TEST(BluetoothLegacyLruCacheTest, LegacyLruCachePressureTest) {
201 auto started = std::chrono::high_resolution_clock::now();
202 int max_size = 0xFFFFF; // 2^20 = 1M
203 LegacyLruCache<int, int> cache(static_cast<size_t>(max_size), "testing");
204
205 // fill the cache
206 for (int key = 0; key < max_size; key++) {
207 cache.Put(key, key);
208 }
209
210 // make sure the cache is full
211 for (int key = 0; key < max_size; key++) {
212 EXPECT_TRUE(cache.HasKey(key));
213 }
214
215 // refresh the entire cache
216 for (int key = 0; key < max_size; key++) {
217 int new_key = key + max_size;
218 cache.Put(new_key, new_key);
219 EXPECT_FALSE(cache.HasKey(key));
220 EXPECT_TRUE(cache.HasKey(new_key));
221 }
222
223 // clear the entire cache
224 int* value = new int(0);
225 for (int key = max_size; key < 2 * max_size; key++) {
226 EXPECT_TRUE(cache.Get(key, value));
227 EXPECT_EQ(*value, key);
228 EXPECT_TRUE(cache.Remove(key));
229 }
230 EXPECT_EQ(cache.Size(), 0);
231
232 // test execution time
233 auto done = std::chrono::high_resolution_clock::now();
234 int execution_time =
235 std::chrono::duration_cast<std::chrono::milliseconds>(done - started)
236 .count();
237 // always around 750ms on flame. 1400 ms on crosshatch, 6800 ms on presubmit
238 // Shouldn't be more than 10000ms
239 EXPECT_LT(execution_time, 10000);
240 }
241
TEST(BluetoothLegacyLruCacheTest,BluetoothLruMultiThreadPressureTest)242 TEST(BluetoothLegacyLruCacheTest, BluetoothLruMultiThreadPressureTest) {
243 LegacyLruCache<int, int> cache(100, "testing");
244 auto pointer = &cache;
245 // make sure no deadlock
246 std::vector<std::thread> workers;
247 for (int key = 0; key < 100; key++) {
248 workers.push_back(std::thread([key, pointer]() {
249 pointer->Put(key, key);
250 EXPECT_TRUE(pointer->HasKey(key));
251 EXPECT_TRUE(pointer->Remove(key));
252 }));
253 }
254 for (auto& worker : workers) {
255 worker.join();
256 }
257 EXPECT_EQ(cache.Size(), 0);
258 }
259
260 } // namespace testing
261