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