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