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 <gmock/gmock.h>
20 #include <gtest/gtest.h>
21 #include <chrono>
22 #include <limits>
23
24 #include "common/lru.h"
25
26 namespace testing {
27
28 using bluetooth::common::LegacyLruCache;
29
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheMainTest1)30 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheMainTest1) {
31 int* value = new int(0);
32 LegacyLruCache<int, int> cache(3, "testing"); // capacity = 3;
33 cache.Put(1, 10);
34 EXPECT_EQ(cache.Size(), 1);
35 EXPECT_FALSE(cache.Put(2, 20));
36 EXPECT_FALSE(cache.Put(3, 30));
37 EXPECT_EQ(cache.Size(), 3);
38
39 // 1, 2, 3 should be in cache
40 EXPECT_TRUE(cache.Get(1, value));
41 EXPECT_EQ(*value, 10);
42 EXPECT_TRUE(cache.Get(2, value));
43 EXPECT_EQ(*value, 20);
44 EXPECT_TRUE(cache.Get(3, value));
45 EXPECT_EQ(*value, 30);
46 EXPECT_EQ(cache.Size(), 3);
47
48 EXPECT_THAT(cache.Put(4, 40), Optional(Pair(1, 10)));
49 // 2, 3, 4 should be in cache, 1 is evicted
50 EXPECT_FALSE(cache.Get(1, value));
51 EXPECT_TRUE(cache.Get(4, value));
52 EXPECT_EQ(*value, 40);
53 EXPECT_TRUE(cache.Get(2, value));
54 EXPECT_EQ(*value, 20);
55 EXPECT_TRUE(cache.Get(3, value));
56 EXPECT_EQ(*value, 30);
57
58 EXPECT_THAT(cache.Put(5, 50), Optional(Pair(4, 40)));
59 EXPECT_EQ(cache.Size(), 3);
60 // 2, 3, 5 should be in cache, 4 is evicted
61
62 EXPECT_TRUE(cache.Remove(3));
63 EXPECT_FALSE(cache.Put(6, 60));
64 // 2, 5, 6 should be in cache
65
66 EXPECT_FALSE(cache.Get(3, value));
67 EXPECT_FALSE(cache.Get(4, value));
68 EXPECT_TRUE(cache.Get(2, value));
69 EXPECT_EQ(*value, 20);
70 EXPECT_TRUE(cache.Get(5, value));
71 EXPECT_EQ(*value, 50);
72 EXPECT_TRUE(cache.Get(6, value));
73 EXPECT_EQ(*value, 60);
74 }
75
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheMainTest2)76 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheMainTest2) {
77 int* value = new int(0);
78 LegacyLruCache<int, int> cache(2, "testing"); // size = 2;
79 EXPECT_FALSE(cache.Put(1, 10));
80 EXPECT_FALSE(cache.Put(2, 20));
81 EXPECT_THAT(cache.Put(3, 30), Optional(Pair(1, 10)));
82 EXPECT_FALSE(cache.Put(2, 200));
83 EXPECT_EQ(cache.Size(), 2);
84 // 3, 2 should be in cache
85
86 EXPECT_FALSE(cache.HasKey(1));
87 EXPECT_TRUE(cache.Get(2, value));
88 EXPECT_EQ(*value, 200);
89 EXPECT_TRUE(cache.Get(3, value));
90 EXPECT_EQ(*value, 30);
91
92 EXPECT_THAT(cache.Put(4, 40), Optional(Pair(2, 200)));
93 // 3, 4 should be in cache
94
95 EXPECT_FALSE(cache.HasKey(2));
96 EXPECT_TRUE(cache.Get(3, value));
97 EXPECT_EQ(*value, 30);
98 EXPECT_TRUE(cache.Get(4, value));
99 EXPECT_EQ(*value, 40);
100
101 EXPECT_TRUE(cache.Remove(4));
102 EXPECT_EQ(cache.Size(), 1);
103 cache.Put(2, 2000);
104 // 3, 2 should be in cache
105
106 EXPECT_FALSE(cache.HasKey(4));
107 EXPECT_TRUE(cache.Get(3, value));
108 EXPECT_EQ(*value, 30);
109 EXPECT_TRUE(cache.Get(2, value));
110 EXPECT_EQ(*value, 2000);
111
112 EXPECT_TRUE(cache.Remove(2));
113 EXPECT_TRUE(cache.Remove(3));
114 cache.Put(5, 50);
115 cache.Put(1, 100);
116 cache.Put(1, 1000);
117 EXPECT_EQ(cache.Size(), 2);
118 // 1, 5 should be in cache
119
120 EXPECT_FALSE(cache.HasKey(2));
121 EXPECT_FALSE(cache.HasKey(3));
122 EXPECT_TRUE(cache.Get(1, value));
123 EXPECT_EQ(*value, 1000);
124 EXPECT_TRUE(cache.Get(5, value));
125 EXPECT_EQ(*value, 50);
126 }
127
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheFindTest)128 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheFindTest) {
129 LegacyLruCache<int, int> cache(10, "testing");
130 cache.Put(1, 10);
131 cache.Put(2, 20);
132 int value = 0;
133 EXPECT_TRUE(cache.Get(1, &value));
134 EXPECT_EQ(value, 10);
135 auto value_ptr = cache.Find(1);
136 EXPECT_NE(value_ptr, nullptr);
137 *value_ptr = 20;
138 EXPECT_TRUE(cache.Get(1, &value));
139 EXPECT_EQ(value, 20);
140 cache.Put(1, 40);
141 EXPECT_EQ(*value_ptr, 40);
142 EXPECT_EQ(cache.Find(10), nullptr);
143 }
144
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheGetTest)145 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheGetTest) {
146 LegacyLruCache<int, int> cache(10, "testing");
147 cache.Put(1, 10);
148 cache.Put(2, 20);
149 int value = 0;
150 EXPECT_TRUE(cache.Get(1, &value));
151 EXPECT_EQ(value, 10);
152 EXPECT_TRUE(cache.HasKey(1));
153 EXPECT_TRUE(cache.HasKey(2));
154 EXPECT_FALSE(cache.HasKey(3));
155 EXPECT_FALSE(cache.Get(3, &value));
156 EXPECT_EQ(value, 10);
157 }
158
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheRemoveTest)159 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheRemoveTest) {
160 LegacyLruCache<int, int> cache(10, "testing");
161 for (int key = 0; key <= 30; key++) {
162 cache.Put(key, key * 100);
163 }
164 for (int key = 0; key <= 20; key++) {
165 EXPECT_FALSE(cache.HasKey(key));
166 }
167 for (int key = 21; key <= 30; key++) {
168 EXPECT_TRUE(cache.HasKey(key));
169 }
170 for (int key = 21; key <= 30; key++) {
171 EXPECT_TRUE(cache.Remove(key));
172 }
173 for (int key = 21; key <= 30; key++) {
174 EXPECT_FALSE(cache.HasKey(key));
175 }
176 }
177
TEST(BluetoothLegacyLruCacheTest,LegacyLruCacheClearTest)178 TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheClearTest) {
179 LegacyLruCache<int, int> cache(10, "testing");
180 for (int key = 0; key < 10; key++) {
181 cache.Put(key, key * 100);
182 }
183 for (int key = 0; key < 10; key++) {
184 EXPECT_TRUE(cache.HasKey(key));
185 }
186 cache.Clear();
187 for (int key = 0; key < 10; key++) {
188 EXPECT_FALSE(cache.HasKey(key));
189 }
190
191 for (int key = 0; key < 10; key++) {
192 cache.Put(key, key * 1000);
193 }
194 for (int key = 0; key < 10; key++) {
195 EXPECT_TRUE(cache.HasKey(key));
196 }
197 }
198
TEST(BluetoothLegacyLruCacheTest,LegacyLruCachePressureTest)199 TEST(BluetoothLegacyLruCacheTest, LegacyLruCachePressureTest) {
200 int max_size = 0xFFFFF; // 2^20 = 1M
201 LegacyLruCache<int, int> cache(static_cast<size_t>(max_size), "testing");
202
203 // fill the cache
204 for (int key = 0; key < max_size; key++) {
205 cache.Put(key, key);
206 }
207
208 // make sure the cache is full
209 for (int key = 0; key < max_size; key++) {
210 EXPECT_TRUE(cache.HasKey(key));
211 }
212
213 // refresh the entire cache
214 for (int key = 0; key < max_size; key++) {
215 int new_key = key + max_size;
216 cache.Put(new_key, new_key);
217 EXPECT_FALSE(cache.HasKey(key));
218 EXPECT_TRUE(cache.HasKey(new_key));
219 }
220
221 // clear the entire cache
222 int* value = new int(0);
223 for (int key = max_size; key < 2 * max_size; key++) {
224 EXPECT_TRUE(cache.Get(key, value));
225 EXPECT_EQ(*value, key);
226 EXPECT_TRUE(cache.Remove(key));
227 }
228 EXPECT_EQ(cache.Size(), 0);
229 }
230
TEST(BluetoothLegacyLruCacheTest,BluetoothLruMultiThreadPressureTest)231 TEST(BluetoothLegacyLruCacheTest, BluetoothLruMultiThreadPressureTest) {
232 LegacyLruCache<int, int> cache(100, "testing");
233 auto pointer = &cache;
234 // make sure no deadlock
235 std::vector<std::thread> workers;
236 for (int key = 0; key < 100; key++) {
237 workers.push_back(std::thread([key, pointer]() {
238 pointer->Put(key, key);
239 EXPECT_TRUE(pointer->HasKey(key));
240 EXPECT_TRUE(pointer->Remove(key));
241 }));
242 }
243 for (auto& worker : workers) {
244 worker.join();
245 }
246 EXPECT_EQ(cache.Size(), 0);
247 }
248
249 } // namespace testing
250