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