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 #include "common/metric_id_manager.h"
19
20 #include <gmock/gmock.h>
21 #include <gtest/gtest.h>
22
23 #include <thread>
24
25 // TODO(b/369381361) Enfore -Wmissing-prototypes
26 #pragma GCC diagnostic ignored "-Wmissing-prototypes"
27
28 namespace testing {
29
30 using bluetooth::common::MetricIdManager;
31
kthAddress(uint32_t k)32 bluetooth::hci::Address kthAddress(uint32_t k) {
33 uint8_t array[6] = {0, 0, 0, 0, 0, 0};
34 for (int i = 5; i >= 2; i--) {
35 array[i] = k % 256;
36 k = k / 256;
37 }
38 bluetooth::hci::Address addr(array);
39 return addr;
40 }
41
generateAddresses(const uint32_t num)42 std::unordered_map<bluetooth::hci::Address, int> generateAddresses(const uint32_t num) {
43 // generate first num of mac address -> id pairs
44 // input may is always valid 256^6 = 2^48 > 2^32
45 std::unordered_map<bluetooth::hci::Address, int> device_map;
46 for (size_t key = 0; key < num; key++) {
47 device_map[kthAddress(key)] = key + MetricIdManager::kMinId;
48 }
49 return device_map;
50 }
51
TEST(BluetoothMetricIdManagerTest,MetricIdManagerInitCloseTest)52 TEST(BluetoothMetricIdManagerTest, MetricIdManagerInitCloseTest) {
53 auto& manager = MetricIdManager::GetInstance();
54 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
55 MetricIdManager::Callback callback = [](const bluetooth::hci::Address&, const int) {
56 return true;
57 };
58 ASSERT_TRUE(manager.Init(paired_device_map, callback, callback));
59 ASSERT_FALSE(manager.Init(paired_device_map, callback, callback));
60 ASSERT_TRUE(manager.Close());
61 }
62
TEST(BluetoothMetricIdManagerTest,MetricIdManagerNotCloseTest)63 TEST(BluetoothMetricIdManagerTest, MetricIdManagerNotCloseTest) {
64 auto& manager = MetricIdManager::GetInstance();
65 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
66 MetricIdManager::Callback callback = [](const bluetooth::hci::Address&, const int) {
67 return true;
68 };
69 ASSERT_TRUE(manager.Init(paired_device_map, callback, callback));
70
71 // should fail because it isn't closed
72 ASSERT_FALSE(manager.Init(paired_device_map, callback, callback));
73 ASSERT_TRUE(manager.Close());
74 }
75
TEST(BluetoothMetricIdManagerTest,MetricIdManagerScanDeviceFromEmptyTest)76 TEST(BluetoothMetricIdManagerTest, MetricIdManagerScanDeviceFromEmptyTest) {
77 auto& manager = MetricIdManager::GetInstance();
78 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
79 MetricIdManager::Callback callback = [](const bluetooth::hci::Address&, const int) {
80 return true;
81 };
82 // test empty map, next id should be kMinId
83 ASSERT_TRUE(manager.Init(paired_device_map, callback, callback));
84 ASSERT_EQ(manager.AllocateId(kthAddress(0)), MetricIdManager::kMinId);
85 ASSERT_EQ(manager.AllocateId(kthAddress(1)), MetricIdManager::kMinId + 1);
86 ASSERT_EQ(manager.AllocateId(kthAddress(0)), MetricIdManager::kMinId);
87 ASSERT_EQ(manager.AllocateId(kthAddress(2)), MetricIdManager::kMinId + 2);
88 ASSERT_TRUE(manager.Close());
89 }
90
TEST(BluetoothMetricIdManagerTest,MetricIdManagerScanDeviceFromFilledTest)91 TEST(BluetoothMetricIdManagerTest, MetricIdManagerScanDeviceFromFilledTest) {
92 auto& manager = MetricIdManager::GetInstance();
93 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
94 MetricIdManager::Callback callback = [](const bluetooth::hci::Address&, const int) {
95 return true;
96 };
97 int id =
98 static_cast<int>(MetricIdManager::kMaxNumPairedDevicesInMemory) + MetricIdManager::kMinId;
99 // next id should be MetricIdManager::kMaxNumPairedDevicesInMemory
100 paired_device_map = generateAddresses(MetricIdManager::kMaxNumPairedDevicesInMemory);
101 ASSERT_TRUE(manager.Init(paired_device_map, callback, callback));
102 // try new values not in the map, should get new id.
103 ASSERT_EQ(manager.AllocateId(kthAddress(INT_MAX)), id);
104 ASSERT_EQ(manager.AllocateId(kthAddress(INT_MAX - 1)), id + 1);
105 ASSERT_EQ(manager.AllocateId(kthAddress(INT_MAX)), id);
106 ASSERT_EQ(manager.AllocateId(kthAddress(INT_MAX - 2)), id + 2);
107 ASSERT_TRUE(manager.Close());
108 }
109
TEST(BluetoothMetricIdManagerTest,MetricIdManagerAllocateExistingTest)110 TEST(BluetoothMetricIdManagerTest, MetricIdManagerAllocateExistingTest) {
111 auto& manager = MetricIdManager::GetInstance();
112 std::unordered_map<bluetooth::hci::Address, int> paired_device_map =
113 generateAddresses(MetricIdManager::kMaxNumPairedDevicesInMemory);
114
115 MetricIdManager::Callback callback = [](const bluetooth::hci::Address&, const int) {
116 return true;
117 };
118 int id = MetricIdManager::kMinId;
119 // next id should be MetricIdManager::kMaxNumPairedDevicesInMemory
120 ASSERT_TRUE(manager.Init(paired_device_map, callback, callback));
121
122 // try values already in the map, should get new id.
123 ASSERT_EQ(manager.AllocateId(bluetooth::hci::Address({0, 0, 0, 0, 0, 0})), id);
124 ASSERT_EQ(manager.AllocateId(bluetooth::hci::Address({0, 0, 0, 0, 0, 1})), id + 1);
125 ASSERT_EQ(manager.AllocateId(bluetooth::hci::Address({0, 0, 0, 0, 0, 0})), id);
126 ASSERT_EQ(manager.AllocateId(bluetooth::hci::Address({0, 0, 0, 0, 0, 2})), id + 2);
127 ASSERT_TRUE(manager.Close());
128 }
129
TEST(BluetoothMetricIdManagerTest,MetricIdManagerMainTest1)130 TEST(BluetoothMetricIdManagerTest, MetricIdManagerMainTest1) {
131 auto& manager = MetricIdManager::GetInstance();
132 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
133 int placeholder = 22;
134 int* pointer = &placeholder;
135 MetricIdManager::Callback save_callback = [pointer](const bluetooth::hci::Address&, const int) {
136 *pointer = *pointer * 2;
137 return true;
138 };
139 MetricIdManager::Callback forget_callback = [pointer](const bluetooth::hci::Address&, const int) {
140 *pointer = *pointer / 2;
141 return true;
142 };
143
144 ASSERT_TRUE(manager.Init(paired_device_map, save_callback, forget_callback));
145 ASSERT_EQ(manager.AllocateId(bluetooth::hci::Address({0, 0, 0, 0, 0, 0})),
146 MetricIdManager::kMinId);
147 // save it and make sure the callback is called
148 ASSERT_TRUE(manager.SaveDevice(bluetooth::hci::Address({0, 0, 0, 0, 0, 0})));
149 ASSERT_EQ(placeholder, 44);
150
151 // should fail, since id of device is not allocated
152 ASSERT_FALSE(manager.SaveDevice(bluetooth::hci::Address({0, 0, 0, 0, 0, 1})));
153 ASSERT_EQ(placeholder, 44);
154
155 // save it and make sure the callback is called
156 ASSERT_EQ(manager.AllocateId(bluetooth::hci::Address({0, 0, 0, 0, 0, 2})),
157 MetricIdManager::kMinId + 1);
158 ASSERT_EQ(manager.AllocateId(bluetooth::hci::Address({0, 0, 0, 0, 0, 3})),
159 MetricIdManager::kMinId + 2);
160 ASSERT_TRUE(manager.SaveDevice(bluetooth::hci::Address({0, 0, 0, 0, 0, 2})));
161 ASSERT_EQ(placeholder, 88);
162 ASSERT_TRUE(manager.SaveDevice(bluetooth::hci::Address({0, 0, 0, 0, 0, 3})));
163 ASSERT_EQ(placeholder, 176);
164
165 // should be true but callback won't be called, since id had been saved
166 ASSERT_TRUE(manager.SaveDevice(bluetooth::hci::Address({0, 0, 0, 0, 0, 0})));
167 ASSERT_EQ(placeholder, 176);
168
169 // forget
170 manager.ForgetDevice(bluetooth::hci::Address({0, 0, 0, 0, 0, 1}));
171 ASSERT_EQ(placeholder, 176);
172 manager.ForgetDevice(bluetooth::hci::Address({0, 0, 0, 0, 0, 2}));
173 ASSERT_EQ(placeholder, 88);
174
175 ASSERT_TRUE(manager.Close());
176 }
177
TEST(BluetoothMetricIdManagerTest,MetricIdManagerFullPairedMap)178 TEST(BluetoothMetricIdManagerTest, MetricIdManagerFullPairedMap) {
179 auto& manager = MetricIdManager::GetInstance();
180 // preset a full map
181 std::unordered_map<bluetooth::hci::Address, int> paired_device_map =
182 generateAddresses(MetricIdManager::kMaxNumPairedDevicesInMemory);
183 int placeholder = 243;
184 int* pointer = &placeholder;
185 MetricIdManager::Callback save_callback = [pointer](const bluetooth::hci::Address&, const int) {
186 *pointer = *pointer * 2;
187 return true;
188 };
189 MetricIdManager::Callback forget_callback = [pointer](const bluetooth::hci::Address&, const int) {
190 *pointer = *pointer / 3;
191 return true;
192 };
193
194 ASSERT_TRUE(manager.Init(paired_device_map, save_callback, forget_callback));
195
196 // check if all preset ids are there.
197 // comments based on kMaxNumPairedDevicesInMemory = 200. It can change.
198 int key = 0;
199 for (key = 0; key < static_cast<int>(MetricIdManager::kMaxNumPairedDevicesInMemory); key++) {
200 ASSERT_EQ(manager.AllocateId(kthAddress(key)), key + MetricIdManager::kMinId);
201 }
202 // paired: 0, 1, 2 ... 199,
203 // scanned:
204
205 int id =
206 static_cast<int>(MetricIdManager::kMaxNumPairedDevicesInMemory + MetricIdManager::kMinId);
207 // next id should be MetricIdManager::kMaxNumPairedDevicesInMemory +
208 // MetricIdManager::kMinId
209
210 ASSERT_EQ(manager.AllocateId(kthAddress(key)), id++);
211 // paired: 0, 1, 2 ... 199,
212 // scanned: 200
213
214 // save it and make sure the callback is called
215 ASSERT_TRUE(manager.SaveDevice(kthAddress(key)));
216 // one key is evicted, another key is saved so *2/3
217 ASSERT_EQ(placeholder, 162);
218
219 // paired: 1, 2 ... 199, 200,
220 // scanned:
221
222 ASSERT_EQ(manager.AllocateId(kthAddress(0)), id++);
223 // paired: 1, 2 ... 199, 200
224 // scanned: 0
225
226 // key == 200
227 // should fail, since id of device is not allocated
228 ASSERT_FALSE(manager.SaveDevice(kthAddress(key + 1)));
229 ASSERT_EQ(placeholder, 162);
230 // paired: 1, 2 ... 199, 200,
231 // scanned: 0
232
233 ASSERT_EQ(manager.AllocateId(kthAddress(key + 1)), id++);
234 ASSERT_TRUE(manager.SaveDevice(kthAddress(key + 1)));
235 // one key is evicted, another key is saved so *2/3,
236 ASSERT_EQ(placeholder, 108);
237 // paired: 2 ... 199, 200, 201
238 // scanned: 0
239
240 ASSERT_EQ(manager.AllocateId(kthAddress(1)), id++);
241 // paired: 2 ... 199, 200, 201,
242 // scanned: 0, 1
243
244 // save it and make sure the callback is called
245 ASSERT_EQ(manager.AllocateId(kthAddress(key + 2)), id++);
246 ASSERT_EQ(manager.AllocateId(kthAddress(key + 3)), id++);
247 // paired: 2 ... 199, 200, 201,
248 // scanned: 0, 1, 202, 203
249
250 placeholder = 9;
251 ASSERT_TRUE(manager.SaveDevice(kthAddress(key + 2)));
252 // one key is evicted, another key is saved so *2/3,
253 ASSERT_EQ(placeholder, 6);
254 ASSERT_TRUE(manager.SaveDevice(kthAddress(key + 3)));
255 // one key is evicted, another key is saved so *2/3,
256 ASSERT_EQ(placeholder, 4);
257 // paired: 4 ... 199, 200, 201, 202, 203
258 // scanned: 0, 1
259
260 // should be true but callback won't be called, since id had been saved
261 ASSERT_TRUE(manager.SaveDevice(kthAddress(key + 2)));
262 ASSERT_EQ(placeholder, 4);
263
264 placeholder = 27;
265 // forget
266 manager.ForgetDevice(kthAddress(key + 200));
267 ASSERT_EQ(placeholder, 27); // should fail, no such a key
268 manager.ForgetDevice(kthAddress(key + 2));
269 ASSERT_EQ(placeholder, 9);
270 // paired: 4 ... 199, 200, 201, 203
271 // scanned: 0, 1
272
273 // save it and make sure the callback is called
274 ASSERT_EQ(manager.AllocateId(kthAddress(key + 2)), id++);
275 ASSERT_EQ(manager.AllocateId(kthAddress(key + 4)), id++);
276 ASSERT_EQ(manager.AllocateId(kthAddress(key + 5)), id++);
277 // paired: 4 ... 199, 200, 201, 203
278 // scanned: 0, 1, 202, 204, 205
279
280 ASSERT_TRUE(manager.SaveDevice(kthAddress(key + 2)));
281 ASSERT_EQ(placeholder, 18); // no key is evicted, a key is saved so *2,
282
283 // should be true but callback won't be called, since id had been saved
284 ASSERT_TRUE(manager.SaveDevice(kthAddress(key + 3)));
285 ASSERT_EQ(placeholder, 18); // no such a key in scanned
286 ASSERT_TRUE(manager.SaveDevice(kthAddress(key + 4)));
287 // one key is evicted, another key is saved so *2/3
288 ASSERT_EQ(placeholder, 12);
289 // paired: 5 6 ... 199, 200, 201, 203, 202, 204
290 // scanned: 0, 1, 205
291
292 // verify paired:
293 for (key = 5; key <= 199; key++) {
294 placeholder = 3;
295 manager.ForgetDevice(kthAddress(key));
296 ASSERT_EQ(placeholder, 1);
297 }
298 for (size_t k = MetricIdManager::kMaxNumPairedDevicesInMemory;
299 k <= MetricIdManager::kMaxNumPairedDevicesInMemory + 4; k++) {
300 placeholder = 3;
301 manager.ForgetDevice(kthAddress(k));
302 ASSERT_EQ(placeholder, 1);
303 }
304
305 // verify scanned
306 placeholder = 4;
307 ASSERT_TRUE(manager.SaveDevice(kthAddress(0)));
308 ASSERT_TRUE(manager.SaveDevice(kthAddress(1)));
309 ASSERT_TRUE(manager.SaveDevice(kthAddress(MetricIdManager::kMaxNumPairedDevicesInMemory + 5)));
310 ASSERT_EQ(placeholder, 32);
311
312 ASSERT_TRUE(manager.Close());
313 }
314
TEST(BluetoothMetricIdManagerTest,MetricIdManagerFullScannedMap)315 TEST(BluetoothMetricIdManagerTest, MetricIdManagerFullScannedMap) {
316 auto& manager = MetricIdManager::GetInstance();
317 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
318 int placeholder = 22;
319 int* pointer = &placeholder;
320 MetricIdManager::Callback save_callback = [pointer](const bluetooth::hci::Address&, const int) {
321 *pointer = *pointer * 2;
322 return true;
323 };
324 MetricIdManager::Callback forget_callback = [pointer](const bluetooth::hci::Address&, const int) {
325 *pointer = *pointer / 2;
326 return true;
327 };
328
329 ASSERT_TRUE(manager.Init(paired_device_map, save_callback, forget_callback));
330
331 // allocate kMaxNumUnpairedDevicesInMemory ids
332 // comments based on kMaxNumUnpairedDevicesInMemory = 200
333 for (int key = 0; key < static_cast<int>(MetricIdManager::kMaxNumUnpairedDevicesInMemory);
334 key++) {
335 ASSERT_EQ(manager.AllocateId(kthAddress(key)), key + MetricIdManager::kMinId);
336 }
337 // scanned: 0, 1, 2 ... 199,
338 // paired:
339
340 int id = MetricIdManager::kMaxNumUnpairedDevicesInMemory + MetricIdManager::kMinId;
341 bluetooth::hci::Address addr = kthAddress(MetricIdManager::kMaxNumUnpairedDevicesInMemory);
342 ASSERT_EQ(manager.AllocateId(addr), id);
343 // scanned: 1, 2 ... 199, 200
344
345 // save it and make sure the callback is called
346 ASSERT_TRUE(manager.SaveDevice(addr));
347 ASSERT_EQ(manager.AllocateId(addr), id);
348 ASSERT_EQ(placeholder, 44);
349 // paired: 200,
350 // scanned: 1, 2 ... 199,
351 id++;
352
353 addr = kthAddress(MetricIdManager::kMaxNumUnpairedDevicesInMemory + 1);
354 ASSERT_EQ(manager.AllocateId(addr), id++);
355 // paired: 200,
356 // scanned: 1, 2 ... 199, 201
357
358 // try to allocate for device 0, 1, 2, 3, 4....199
359 // we should have a new id every time,
360 // since the scanned map is full at this point
361 for (int key = 0; key < static_cast<int>(MetricIdManager::kMaxNumUnpairedDevicesInMemory);
362 key++) {
363 ASSERT_EQ(manager.AllocateId(kthAddress(key)), id++);
364 }
365 ASSERT_TRUE(manager.Close());
366 }
367
TEST(BluetoothMetricIdManagerTest,MetricIdManagerMultiThreadPressureTest)368 TEST(BluetoothMetricIdManagerTest, MetricIdManagerMultiThreadPressureTest) {
369 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
370 auto& manager = MetricIdManager::GetInstance();
371 int placeholder = 22;
372 int* pointer = &placeholder;
373 MetricIdManager::Callback save_callback = [pointer](const bluetooth::hci::Address&, const int) {
374 *pointer = *pointer + 1;
375 return true;
376 };
377 MetricIdManager::Callback forget_callback = [pointer](const bluetooth::hci::Address&, const int) {
378 *pointer = *pointer - 1;
379 return true;
380 };
381 ASSERT_TRUE(manager.Init(paired_device_map, save_callback, forget_callback));
382
383 // make sure no deadlock
384 std::vector<std::thread> workers;
385 for (int key = 0; key < static_cast<int>(MetricIdManager::kMaxNumUnpairedDevicesInMemory);
386 key++) {
387 workers.push_back(std::thread([key]() {
388 auto& manager = MetricIdManager::GetInstance();
389 bluetooth::hci::Address fake_mac_address = kthAddress(key);
390 manager.AllocateId(fake_mac_address);
391 ASSERT_TRUE(manager.SaveDevice(fake_mac_address));
392 manager.ForgetDevice(fake_mac_address);
393 }));
394 }
395 for (auto& worker : workers) {
396 worker.join();
397 }
398 ASSERT_TRUE(manager.IsEmpty());
399 ASSERT_TRUE(manager.Close());
400 }
401
TEST(BluetoothMetricIdManagerTest,MetricIdManagerWrapAroundTest1)402 TEST(BluetoothMetricIdManagerTest, MetricIdManagerWrapAroundTest1) {
403 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
404 auto& manager = MetricIdManager::GetInstance();
405 MetricIdManager::Callback callback = [](const bluetooth::hci::Address&, const int) {
406 return true;
407 };
408
409 // make a sparse paired_device_map
410 int min_id = MetricIdManager::kMinId;
411 paired_device_map[kthAddress(min_id)] = min_id;
412 paired_device_map[kthAddress(min_id + 1)] = min_id + 1;
413 paired_device_map[kthAddress(min_id + 3)] = min_id + 3;
414 paired_device_map[kthAddress(min_id + 4)] = min_id + 4;
415
416 int max_id = MetricIdManager::kMaxId;
417 paired_device_map[kthAddress(max_id - 3)] = max_id - 3;
418 paired_device_map[kthAddress(max_id - 4)] = max_id - 4;
419
420 ASSERT_TRUE(manager.Init(paired_device_map, callback, callback));
421
422 // next id should be max_id - 2, max_id - 1, max_id, min_id + 2, min_id + 5
423 ASSERT_EQ(manager.AllocateId(kthAddress(max_id - 2)), max_id - 2);
424 ASSERT_EQ(manager.AllocateId(kthAddress(max_id - 1)), max_id - 1);
425 ASSERT_EQ(manager.AllocateId(kthAddress(max_id)), max_id);
426 ASSERT_EQ(manager.AllocateId(kthAddress(min_id + 2)), min_id + 2);
427 ASSERT_EQ(manager.AllocateId(kthAddress(min_id + 5)), min_id + 5);
428
429 ASSERT_TRUE(manager.Close());
430 }
431
TEST(BluetoothMetricIdManagerTest,MetricIdManagerWrapAroundTest2)432 TEST(BluetoothMetricIdManagerTest, MetricIdManagerWrapAroundTest2) {
433 std::unordered_map<bluetooth::hci::Address, int> paired_device_map;
434 auto& manager = MetricIdManager::GetInstance();
435 MetricIdManager::Callback callback = [](const bluetooth::hci::Address&, const int) {
436 return true;
437 };
438
439 // make a sparse paired_device_map
440 int min_id = MetricIdManager::kMinId;
441 int max_id = MetricIdManager::kMaxId;
442 paired_device_map[kthAddress(max_id)] = max_id;
443
444 ASSERT_TRUE(manager.Init(paired_device_map, callback, callback));
445
446 // next id should be min_id, min_id + 1
447 ASSERT_EQ(manager.AllocateId(kthAddress(min_id)), min_id);
448 ASSERT_EQ(manager.AllocateId(kthAddress(min_id + 1)), min_id + 1);
449
450 ASSERT_TRUE(manager.Close());
451 }
452
453 } // namespace testing
454