From b12ac65535cda6a4477738ff3e060e6e9be4c08b Mon Sep 17 00:00:00 2001 From: Chen Chen Date: Thu, 20 Feb 2020 11:29:42 -0800 Subject: [PATCH] BluetoothMetrics: Implement and test metric_id_allocator and lru Test: run atest on unittests Bug: 142563377 Change-Id: I05739258479a67d47550a6cb1db1c6f8c1ff3e98 --- common/Android.bp | 3 + common/lru.h | 178 +++++++++++++ common/lru_unittest.cc | 242 +++++++++++++++++ common/metric_id_allocator.cc | 173 ++++++++++++ common/metric_id_allocator.h | 128 +++++++++ common/metric_id_allocator_unittest.cc | 468 +++++++++++++++++++++++++++++++++ types/raw_address.h | 12 + 7 files changed, 1204 insertions(+) create mode 100644 common/lru.h create mode 100644 common/lru_unittest.cc create mode 100644 common/metric_id_allocator.cc create mode 100644 common/metric_id_allocator.h create mode 100644 common/metric_id_allocator_unittest.cc diff --git a/common/Android.bp b/common/Android.bp index 587b197db..e05528c7e 100644 --- a/common/Android.bp +++ b/common/Android.bp @@ -12,6 +12,7 @@ cc_library_static { srcs: [ "address_obfuscator.cc", "message_loop_thread.cc", + "metric_id_allocator.cc", "metrics.cc", "once_timer.cc", "repeating_timer.cc", @@ -40,8 +41,10 @@ cc_test { srcs: [ "address_obfuscator_unittest.cc", "leaky_bonded_queue_unittest.cc", + "lru_unittest.cc", "message_loop_thread_unittest.cc", "metrics_unittest.cc", + "metric_id_allocator_unittest.cc", "once_timer_unittest.cc", "repeating_timer_unittest.cc", "state_machine_unittest.cc", diff --git a/common/lru.h b/common/lru.h new file mode 100644 index 000000000..0904023ff --- /dev/null +++ b/common/lru.h @@ -0,0 +1,178 @@ +/****************************************************************************** + * + * Copyright 2020 Google, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + ******************************************************************************/ + +#pragma once + +#include +#include +#include +#include +#include +#include + +#include + +namespace bluetooth { + +namespace common { + +template +class LruCache { + public: + using Node = std::pair; + using LruEvictionCallback = std::function; + /** + * Constructor of the cache + * + * @param capacity maximum size of the cache + * @param log_tag, keyword to put at the head of log. + * @param lru_eviction_callback a call back will be called when the cache is + * full and Put() is called + */ + LruCache(const size_t& capacity, const std::string& log_tag, + LruEvictionCallback lru_eviction_callback) + : capacity_(capacity), lru_eviction_callback_(lru_eviction_callback) { + if (capacity_ == 0) { + // don't allow invalid capacity + LOG(FATAL) << log_tag << " unable to have 0 LRU Cache capacity"; + } + } + + ~LruCache() { Clear(); } + + /** + * Clear the cache + */ + void Clear() { + std::lock_guard lock(lru_mutex_); + lru_map_.clear(); + node_list_.clear(); + } + + /** + * Get the value of a key, and move the key to the head of cache, if there is + * one + * + * @param key + * @param value, output parameter of value of the key + * @return true if the cache has the key + */ + bool Get(const K& key, V* value) { + std::lock_guard lock(lru_mutex_); + auto map_iterator = lru_map_.find(key); + if (map_iterator == lru_map_.end()) { + return false; + } + auto& list_iterator = map_iterator->second; + auto node = *list_iterator; + node_list_.erase(list_iterator); + node_list_.push_front(node); + map_iterator->second = node_list_.begin(); + *value = node.second; + return true; + } + + /** + * Check if the cache has the input key, move the key to the head + * if there is one + * + * @param key + * @return true if the cache has the key + */ + bool HasKey(const K& key) { + V dummy_value; + return Get(key, &dummy_value); + } + + /** + * Put a key-value pair to the head of cache + * + * @param key + * @param value + * @return true if tail value is popped + */ + bool Put(const K& key, const V& value) { + if (HasKey(key)) { + // hasKey() calls get(), therefore already move the node to the head + std::lock_guard lock(lru_mutex_); + lru_map_[key]->second = value; + return false; + } + + bool value_popped = false; + std::lock_guard lock(lru_mutex_); + // remove tail + if (lru_map_.size() == capacity_) { + lru_map_.erase(node_list_.back().first); + node_list_.pop_back(); + lru_eviction_callback_(node_list_.back().first, node_list_.back().second); + value_popped = true; + } + // insert to dummy next; + Node add(key, value); + node_list_.push_front(add); + lru_map_[key] = node_list_.begin(); + return value_popped; + } + + /** + * Delete a key from cache + * + * @param key + * @return true if delete successfully + */ + bool Remove(const K& key) { + std::lock_guard lock(lru_mutex_); + if (lru_map_.count(key) == 0) { + return false; + } + + // remove from the list + auto& iterator = lru_map_[key]; + node_list_.erase(iterator); + + // delete key from map + lru_map_.erase(key); + + return true; + } + + /** + * Return size of the cache + * + * @return size of the cache + */ + int Size() const { + std::lock_guard lock(lru_mutex_); + return lru_map_.size(); + } + + private: + std::list node_list_; + size_t capacity_; + std::unordered_map::iterator> lru_map_; + LruEvictionCallback lru_eviction_callback_; + mutable std::mutex lru_mutex_; + + // delete copy constructor + LruCache(LruCache const&) = delete; + LruCache& operator=(LruCache const&) = delete; +}; + +} // namespace common +} // namespace bluetooth diff --git a/common/lru_unittest.cc b/common/lru_unittest.cc new file mode 100644 index 000000000..aae582750 --- /dev/null +++ b/common/lru_unittest.cc @@ -0,0 +1,242 @@ +/****************************************************************************** + * + * Copyright 2020 Google, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + ******************************************************************************/ + +#include +#include +#include +#include +#include + +#include "common/lru.h" + +namespace testing { + +using bluetooth::common::LruCache; + +TEST(BluetoothLruCacheTest, LruCacheMainTest1) { + int* value = new int(0); + int dummy = 0; + int* pointer = &dummy; + auto callback = [pointer](int a, int b) { (*pointer) = 1; }; + LruCache cache(3, "testing", callback); // capacity = 3; + cache.Put(1, 10); + EXPECT_EQ(cache.Size(), 1); + cache.Put(2, 20); + cache.Put(3, 30); + EXPECT_EQ(cache.Size(), 3); + EXPECT_EQ(dummy, 0); + + // 1, 2, 3 should be in cache + EXPECT_TRUE(cache.Get(1, value)); + EXPECT_EQ(*value, 10); + EXPECT_TRUE(cache.Get(2, value)); + EXPECT_EQ(*value, 20); + EXPECT_TRUE(cache.Get(3, value)); + EXPECT_EQ(*value, 30); + EXPECT_EQ(cache.Size(), 3); + + cache.Put(4, 40); + EXPECT_EQ(dummy, 1); + // 2, 3, 4 should be in cache, 1 should not + EXPECT_FALSE(cache.Get(1, value)); + EXPECT_TRUE(cache.Get(4, value)); + EXPECT_EQ(*value, 40); + EXPECT_TRUE(cache.Get(2, value)); + EXPECT_EQ(*value, 20); + EXPECT_TRUE(cache.Get(3, value)); + EXPECT_EQ(*value, 30); + + cache.Put(5, 50); + EXPECT_EQ(cache.Size(), 3); + // 2, 3, 5 should be in cache + + EXPECT_TRUE(cache.Remove(3)); + cache.Put(6, 60); + // 2, 5, 6 should be in cache + + EXPECT_FALSE(cache.Get(3, value)); + EXPECT_FALSE(cache.Get(4, value)); + EXPECT_TRUE(cache.Get(2, value)); + EXPECT_EQ(*value, 20); + EXPECT_TRUE(cache.Get(5, value)); + EXPECT_EQ(*value, 50); + EXPECT_TRUE(cache.Get(6, value)); + EXPECT_EQ(*value, 60); +} + +TEST(BluetoothLruCacheTest, LruCacheMainTest2) { + int* value = new int(0); + int dummy = 0; + int* pointer = &dummy; + auto callback = [pointer](int a, int b) { (*pointer)++; }; + LruCache cache(2, "testing", callback); // size = 2; + cache.Put(1, 10); + cache.Put(2, 20); + EXPECT_EQ(dummy, 0); + cache.Put(3, 30); + EXPECT_EQ(dummy, 1); + cache.Put(2, 200); + EXPECT_EQ(dummy, 1); + EXPECT_EQ(cache.Size(), 2); + // 3, 2 should be in cache + + EXPECT_FALSE(cache.HasKey(1)); + EXPECT_TRUE(cache.Get(2, value)); + EXPECT_EQ(*value, 200); + EXPECT_TRUE(cache.Get(3, value)); + EXPECT_EQ(*value, 30); + + cache.Put(4, 40); + EXPECT_EQ(dummy, 2); + // 3, 4 should be in cache + + EXPECT_FALSE(cache.HasKey(2)); + EXPECT_TRUE(cache.Get(3, value)); + EXPECT_EQ(*value, 30); + EXPECT_TRUE(cache.Get(4, value)); + EXPECT_EQ(*value, 40); + + EXPECT_TRUE(cache.Remove(4)); + EXPECT_EQ(cache.Size(), 1); + cache.Put(2, 2000); + // 3, 2 should be in cache + + EXPECT_FALSE(cache.HasKey(4)); + EXPECT_TRUE(cache.Get(3, value)); + EXPECT_EQ(*value, 30); + EXPECT_TRUE(cache.Get(2, value)); + EXPECT_EQ(*value, 2000); + + EXPECT_TRUE(cache.Remove(2)); + EXPECT_TRUE(cache.Remove(3)); + cache.Put(5, 50); + cache.Put(1, 100); + cache.Put(1, 1000); + EXPECT_EQ(cache.Size(), 2); + // 1, 5 should be in cache + + EXPECT_FALSE(cache.HasKey(2)); + EXPECT_FALSE(cache.HasKey(3)); + EXPECT_TRUE(cache.Get(1, value)); + EXPECT_EQ(*value, 1000); + EXPECT_TRUE(cache.Get(5, value)); + EXPECT_EQ(*value, 50); +} + +TEST(BluetoothLruCacheTest, LruCacheRemoveTest) { + LruCache cache(10, "testing", [](int a, int b) {}); + for (int key = 0; key <= 30; key++) { + cache.Put(key, key * 100); + } + for (int key = 0; key <= 20; key++) { + EXPECT_FALSE(cache.HasKey(key)); + } + for (int key = 21; key <= 30; key++) { + EXPECT_TRUE(cache.HasKey(key)); + } + for (int key = 21; key <= 30; key++) { + EXPECT_TRUE(cache.Remove(key)); + } + for (int key = 21; key <= 30; key++) { + EXPECT_FALSE(cache.HasKey(key)); + } +} + +TEST(BluetoothLruCacheTest, LruCacheClearTest) { + LruCache cache(10, "testing", [](int a, int b) {}); + for (int key = 0; key < 10; key++) { + cache.Put(key, key * 100); + } + for (int key = 0; key < 10; key++) { + EXPECT_TRUE(cache.HasKey(key)); + } + cache.Clear(); + for (int key = 0; key < 10; key++) { + EXPECT_FALSE(cache.HasKey(key)); + } + + for (int key = 0; key < 10; key++) { + cache.Put(key, key * 1000); + } + for (int key = 0; key < 10; key++) { + EXPECT_TRUE(cache.HasKey(key)); + } +} + +TEST(BluetoothLruCacheTest, LruCachePressureTest) { + auto started = std::chrono::high_resolution_clock::now(); + int max_size = 0xFFFFF; // 2^20 = 1M + LruCache cache(static_cast(max_size), "testing", + [](int a, int b) {}); + + // fill the cache + for (int key = 0; key < max_size; key++) { + cache.Put(key, key); + } + + // make sure the cache is full + for (int key = 0; key < max_size; key++) { + EXPECT_TRUE(cache.HasKey(key)); + } + + // refresh the entire cache + for (int key = 0; key < max_size; key++) { + int new_key = key + max_size; + cache.Put(new_key, new_key); + EXPECT_FALSE(cache.HasKey(key)); + EXPECT_TRUE(cache.HasKey(new_key)); + } + + // clear the entire cache + int* value = new int(0); + for (int key = max_size; key < 2 * max_size; key++) { + EXPECT_TRUE(cache.Get(key, value)); + EXPECT_EQ(*value, key); + EXPECT_TRUE(cache.Remove(key)); + } + EXPECT_EQ(cache.Size(), 0); + + // test execution time + auto done = std::chrono::high_resolution_clock::now(); + int execution_time = + std::chrono::duration_cast(done - started) + .count(); + // always around 750ms on flame. 1400 ms on crosshatch, 6800 ms on presubmit + // Shouldn't be more than 10000ms + EXPECT_LT(execution_time, 10000); +} + +TEST(BluetoothLruCacheTest, BluetoothLruMultiThreadPressureTest) { + LruCache cache(100, "testing", [](int a, int b) {}); + auto pointer = &cache; + // make sure no deadlock + std::vector workers; + for (int key = 0; key < 100; key++) { + workers.push_back(std::thread([key, pointer]() { + pointer->Put(key, key); + EXPECT_TRUE(pointer->HasKey(key)); + EXPECT_TRUE(pointer->Remove(key)); + })); + } + for (auto& worker : workers) { + worker.join(); + } + EXPECT_EQ(cache.Size(), 0); +} + +} // namespace testing diff --git a/common/metric_id_allocator.cc b/common/metric_id_allocator.cc new file mode 100644 index 000000000..2667fa656 --- /dev/null +++ b/common/metric_id_allocator.cc @@ -0,0 +1,173 @@ +/****************************************************************************** + * + * Copyright 2020 Google, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + ******************************************************************************/ + +#include +#include +#include +#include + +#include "metric_id_allocator.h" + +namespace bluetooth { + +namespace common { + +const std::string MetricIdAllocator::LOG_TAG = "BluetoothMetricIdAllocator"; +const size_t MetricIdAllocator::kMaxNumUnpairedDevicesInMemory = 200; +const size_t MetricIdAllocator::kMaxNumPairedDevicesInMemory = 400; +const int MetricIdAllocator::kMinId = 1; +const int MetricIdAllocator::kMaxId = 65534; // 2^16 - 2 + +// id space should always be larger than kMaxNumPairedDevicesInMemory + +// kMaxNumUnpairedDevicesInMemory +static_assert((MetricIdAllocator::kMaxNumUnpairedDevicesInMemory + + MetricIdAllocator::kMaxNumPairedDevicesInMemory) < + (MetricIdAllocator::kMaxId - MetricIdAllocator::kMinId), + "id space should always be larger than " + "kMaxNumPairedDevicesInMemory + MaxNumUnpairedDevicesInMemory"); + +MetricIdAllocator::MetricIdAllocator() + : paired_device_cache_(kMaxNumPairedDevicesInMemory, LOG_TAG, + [this](RawAddress dummy, int to_remove) { + this->id_set_.erase(to_remove); + }), + temporary_device_cache_(kMaxNumUnpairedDevicesInMemory, LOG_TAG, + [this](RawAddress dummy, int to_remove) { + this->id_set_.erase(to_remove); + }) {} + +bool MetricIdAllocator::Init( + const std::unordered_map& paired_device_map, + Callback save_id_callback, Callback forget_device_callback) { + std::lock_guard lock(id_allocator_mutex_); + if (initialized_) { + return false; + } + + // init paired_devices_map + if (paired_device_map.size() > kMaxNumPairedDevicesInMemory) { + LOG(FATAL) + << LOG_TAG + << "Paired device map is bigger than kMaxNumPairedDevicesInMemory"; + // fail loudly to let caller know + return false; + } + + next_id_ = kMinId; + for (const std::pair& p : paired_device_map) { + if (p.second < kMinId || p.second > kMaxId) { + LOG(FATAL) << LOG_TAG << "Invalid Bluetooth Metric Id in config"; + } + paired_device_cache_.Put(p.first, p.second); + id_set_.insert(p.second); + next_id_ = std::max(next_id_, p.second + 1); + } + if (next_id_ > kMaxId) { + next_id_ = kMinId; + } + + // init callbacks + save_id_callback_ = save_id_callback; + forget_device_callback_ = forget_device_callback; + + return initialized_ = true; +} + +MetricIdAllocator::~MetricIdAllocator() { Close(); } + +bool MetricIdAllocator::Close() { + std::lock_guard lock(id_allocator_mutex_); + if (!initialized_) { + return false; + } + paired_device_cache_.Clear(); + temporary_device_cache_.Clear(); + id_set_.clear(); + initialized_ = false; + return true; +} + +MetricIdAllocator& MetricIdAllocator::GetInstance() { + static MetricIdAllocator metric_id_allocator; + return metric_id_allocator; +} + +bool MetricIdAllocator::IsEmpty() const { + std::lock_guard lock(id_allocator_mutex_); + return paired_device_cache_.Size() == 0 && + temporary_device_cache_.Size() == 0; +} + +// call this function when a new device is scanned +int MetricIdAllocator::AllocateId(const RawAddress& mac_address) { + std::lock_guard lock(id_allocator_mutex_); + int id = 0; + // if already have an id, return it + if (paired_device_cache_.Get(mac_address, &id)) { + return id; + } + if (temporary_device_cache_.Get(mac_address, &id)) { + return id; + } + + // find next available id + while (id_set_.count(next_id_) > 0) { + next_id_++; + if (next_id_ > kMaxId) { + next_id_ = kMinId; + LOG(WARNING) << LOG_TAG << "Bluetooth metric id overflow."; + } + } + id = next_id_++; + id_set_.insert(id); + temporary_device_cache_.Put(mac_address, id); + + if (next_id_ > kMaxId) { + next_id_ = kMinId; + } + return id; +} + +// call this function when a device is paired +bool MetricIdAllocator::SaveDevice(const RawAddress& mac_address) { + std::lock_guard lock(id_allocator_mutex_); + int id = 0; + bool success = temporary_device_cache_.Get(mac_address, &id); + success &= temporary_device_cache_.Remove(mac_address); + if (success) { + paired_device_cache_.Put(mac_address, id); + success = save_id_callback_(mac_address, id); + } + return success; +} + +// call this function when a device is forgotten +bool MetricIdAllocator::ForgetDevice(const RawAddress& mac_address) { + std::lock_guard lock(id_allocator_mutex_); + int id = 0; + bool success = paired_device_cache_.Get(mac_address, &id); + success &= paired_device_cache_.Remove(mac_address); + if (success) { + id_set_.erase(id); + success = forget_device_callback_(mac_address, id); + } + return success; +} + +} // namespace common +} // namespace bluetooth diff --git a/common/metric_id_allocator.h b/common/metric_id_allocator.h new file mode 100644 index 000000000..f941fd038 --- /dev/null +++ b/common/metric_id_allocator.h @@ -0,0 +1,128 @@ +/****************************************************************************** + * + * Copyright 2020 Google, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + ******************************************************************************/ + +#pragma once + +#include +#include +#include +#include +#include "raw_address.h" + +#include "lru.h" + +namespace bluetooth { + +namespace common { + +class MetricIdAllocator { + public: + using Callback = std::function; + + static const size_t kMaxNumUnpairedDevicesInMemory; + static const size_t kMaxNumPairedDevicesInMemory; + + static const int kMinId; + static const int kMaxId; + + ~MetricIdAllocator(); + + /** + * Get the instance of singleton + * + * @return MetricIdAllocator& + */ + static MetricIdAllocator& GetInstance(); + + /** + * Initialize the allocator + * + * @param paired_device_map map from mac_address to id already saved + * in the disk before init + * @param save_id_callback a callback that will be called after successfully + * saving id for a paired device + * @param forget_device_callback a callback that will be called after + * successful id deletion for forgotten device, + * @return true if successfully initialized + */ + bool Init(const std::unordered_map& paired_device_map, + Callback save_id_callback, Callback forget_device_callback); + + /** + * Close the allocator. should be called when Bluetooth process is killed + * + * @return true if successfully close + */ + bool Close(); + + /** + * Check if no id saved in memory + * + * @return true if no id is saved + */ + bool IsEmpty() const; + + /** + * Allocate an id for a scanned device, or return the id if there is already + * one + * + * @param mac_address mac address of Bluetooth device + * @return the id of device + */ + int AllocateId(const RawAddress& mac_address); + + /** + * Save the id for a paired device + * + * @param mac_address mac address of Bluetooth device + * @return true if save successfully + */ + bool SaveDevice(const RawAddress& mac_address); + + /** + * Delete the id for a device to be forgotten + * + * @param mac_address mac address of Bluetooth device + * @return true if delete successfully + */ + bool ForgetDevice(const RawAddress& mac_address); + + protected: + // Singleton + MetricIdAllocator(); + + private: + static const std::string LOG_TAG; + mutable std::mutex id_allocator_mutex_; + + LruCache paired_device_cache_; + LruCache temporary_device_cache_; + std::unordered_set id_set_; + + int next_id_{kMinId}; + bool initialized_{false}; + Callback save_id_callback_; + Callback forget_device_callback_; + + // delete copy constructor for singleton + MetricIdAllocator(MetricIdAllocator const&) = delete; + MetricIdAllocator& operator=(MetricIdAllocator const&) = delete; +}; + +} // namespace common +} // namespace bluetooth diff --git a/common/metric_id_allocator_unittest.cc b/common/metric_id_allocator_unittest.cc new file mode 100644 index 000000000..416b671ef --- /dev/null +++ b/common/metric_id_allocator_unittest.cc @@ -0,0 +1,468 @@ +/****************************************************************************** + * + * Copyright 2020 Google, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + ******************************************************************************/ + +#include +#include +#include +#include + +#include "common/metric_id_allocator.h" + +namespace testing { + +using bluetooth::common::MetricIdAllocator; + +RawAddress kthAddress(uint32_t k) { + uint8_t array[6] = {0, 0, 0, 0, 0, 0}; + for (int i = 5; i >= 2; i--) { + array[i] = k % 256; + k = k / 256; + } + RawAddress addr(array); + return addr; +} + +std::unordered_map generateAddresses(const uint32_t num) { + // generate first num of mac address -> id pairs + // input may is always valid 256^6 = 2^48 > 2^32 + std::unordered_map device_map; + for (size_t key = 0; key < num; key++) { + device_map[kthAddress(key)] = key + MetricIdAllocator::kMinId; + } + return device_map; +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorInitCloseTest) { + auto& allocator = MetricIdAllocator::GetInstance(); + std::unordered_map paired_device_map; + MetricIdAllocator::Callback callback = [](const RawAddress&, const int) { + return true; + }; + EXPECT_TRUE(allocator.Init(paired_device_map, callback, callback)); + EXPECT_FALSE(allocator.Init(paired_device_map, callback, callback)); + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorNotCloseTest) { + auto& allocator = MetricIdAllocator::GetInstance(); + std::unordered_map paired_device_map; + MetricIdAllocator::Callback callback = [](const RawAddress&, const int) { + return true; + }; + EXPECT_TRUE(allocator.Init(paired_device_map, callback, callback)); + + // should fail because it isn't closed + EXPECT_FALSE(allocator.Init(paired_device_map, callback, callback)); + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorScanDeviceFromEmptyTest) { + auto& allocator = MetricIdAllocator::GetInstance(); + std::unordered_map paired_device_map; + MetricIdAllocator::Callback callback = [](const RawAddress&, const int) { + return true; + }; + // test empty map, next id should be kMinId + EXPECT_TRUE(allocator.Init(paired_device_map, callback, callback)); + EXPECT_EQ(allocator.AllocateId(kthAddress(0)), MetricIdAllocator::kMinId); + EXPECT_EQ(allocator.AllocateId(kthAddress(1)), MetricIdAllocator::kMinId + 1); + EXPECT_EQ(allocator.AllocateId(kthAddress(0)), MetricIdAllocator::kMinId); + EXPECT_EQ(allocator.AllocateId(kthAddress(2)), MetricIdAllocator::kMinId + 2); + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, + MetricIdAllocatorScanDeviceFromFilledTest) { + auto& allocator = MetricIdAllocator::GetInstance(); + std::unordered_map paired_device_map; + MetricIdAllocator::Callback callback = [](const RawAddress&, const int) { + return true; + }; + int id = static_cast(MetricIdAllocator::kMaxNumPairedDevicesInMemory) + + MetricIdAllocator::kMinId; + // next id should be MetricIdAllocator::kMaxNumPairedDevicesInMemory + paired_device_map = + generateAddresses(MetricIdAllocator::kMaxNumPairedDevicesInMemory); + EXPECT_TRUE(allocator.Init(paired_device_map, callback, callback)); + // try new values not in the map, should get new id. + EXPECT_EQ(allocator.AllocateId(kthAddress(INT_MAX)), id); + EXPECT_EQ(allocator.AllocateId(kthAddress(INT_MAX - 1)), id + 1); + EXPECT_EQ(allocator.AllocateId(kthAddress(INT_MAX)), id); + EXPECT_EQ(allocator.AllocateId(kthAddress(INT_MAX - 2)), id + 2); + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorAllocateExistingTest) { + auto& allocator = MetricIdAllocator::GetInstance(); + std::unordered_map paired_device_map = + generateAddresses(MetricIdAllocator::kMaxNumPairedDevicesInMemory); + + MetricIdAllocator::Callback callback = [](const RawAddress&, const int) { + return true; + }; + int id = MetricIdAllocator::kMinId; + // next id should be MetricIdAllocator::kMaxNumPairedDevicesInMemory + EXPECT_TRUE(allocator.Init(paired_device_map, callback, callback)); + + // try values already in the map, should get new id. + EXPECT_EQ(allocator.AllocateId(RawAddress({0, 0, 0, 0, 0, 0})), id); + EXPECT_EQ(allocator.AllocateId(RawAddress({0, 0, 0, 0, 0, 1})), id + 1); + EXPECT_EQ(allocator.AllocateId(RawAddress({0, 0, 0, 0, 0, 0})), id); + EXPECT_EQ(allocator.AllocateId(RawAddress({0, 0, 0, 0, 0, 2})), id + 2); + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorMainTest1) { + auto& allocator = MetricIdAllocator::GetInstance(); + std::unordered_map paired_device_map; + int dummy = 22; + int* pointer = &dummy; + MetricIdAllocator::Callback save_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer * 2; + return true; + }; + MetricIdAllocator::Callback forget_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer / 2; + return true; + }; + + EXPECT_TRUE( + allocator.Init(paired_device_map, save_callback, forget_callback)); + EXPECT_EQ(allocator.AllocateId(RawAddress({0, 0, 0, 0, 0, 0})), + MetricIdAllocator::kMinId); + // save it and make sure the callback is called + EXPECT_TRUE(allocator.SaveDevice(RawAddress({0, 0, 0, 0, 0, 0}))); + EXPECT_EQ(dummy, 44); + + // should fail, since id of device is not allocated + EXPECT_FALSE(allocator.SaveDevice(RawAddress({0, 0, 0, 0, 0, 1}))); + EXPECT_EQ(dummy, 44); + + // save it and make sure the callback is called + EXPECT_EQ(allocator.AllocateId(RawAddress({0, 0, 0, 0, 0, 2})), + MetricIdAllocator::kMinId + 1); + EXPECT_EQ(allocator.AllocateId(RawAddress({0, 0, 0, 0, 0, 3})), + MetricIdAllocator::kMinId + 2); + EXPECT_TRUE(allocator.SaveDevice(RawAddress({0, 0, 0, 0, 0, 2}))); + EXPECT_EQ(dummy, 88); + EXPECT_TRUE(allocator.SaveDevice(RawAddress({0, 0, 0, 0, 0, 3}))); + EXPECT_EQ(dummy, 176); + + // should fail, since id had been saved + EXPECT_FALSE(allocator.SaveDevice(RawAddress({0, 0, 0, 0, 0, 0}))); + EXPECT_EQ(dummy, 176); + + // forget + EXPECT_FALSE(allocator.ForgetDevice(RawAddress({0, 0, 0, 0, 0, 1}))); + EXPECT_EQ(dummy, 176); + EXPECT_TRUE(allocator.ForgetDevice(RawAddress({0, 0, 0, 0, 0, 2}))); + EXPECT_EQ(dummy, 88); + + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorFullPairedMap) { + auto& allocator = MetricIdAllocator::GetInstance(); + // preset a full map + std::unordered_map paired_device_map = + generateAddresses(MetricIdAllocator::kMaxNumPairedDevicesInMemory); + int dummy = 22; + int* pointer = &dummy; + MetricIdAllocator::Callback save_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer * 2; + return true; + }; + MetricIdAllocator::Callback forget_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer / 2; + return true; + }; + + EXPECT_TRUE( + allocator.Init(paired_device_map, save_callback, forget_callback)); + + // check if all preset ids are there. + // comments based on kMaxNumPairedDevicesInMemory = 200. It can change. + int key = 0; + for (key = 0; + key < static_cast(MetricIdAllocator::kMaxNumPairedDevicesInMemory); + key++) { + EXPECT_EQ(allocator.AllocateId(kthAddress(key)), + key + MetricIdAllocator::kMinId); + } + // paired: 0, 1, 2 ... 199, + // scanned: + + int id = static_cast(MetricIdAllocator::kMaxNumPairedDevicesInMemory + + MetricIdAllocator::kMinId); + // next id should be MetricIdAllocator::kMaxNumPairedDevicesInMemory + + // MetricIdAllocator::kMinId + + EXPECT_EQ(allocator.AllocateId(kthAddress(key)), id++); + // paired: 0, 1, 2 ... 199, + // scanned: 200 + + // save it and make sure the callback is called + EXPECT_TRUE(allocator.SaveDevice(kthAddress(key))); + EXPECT_EQ(dummy, 44); + // paired: 1, 2 ... 199, 200, + // scanned: + + EXPECT_EQ(allocator.AllocateId(kthAddress(0)), id++); + // paired: 1, 2 ... 199, 200 + // scanned: 0 + + // key == 200 + // should fail, since id of device is not allocated + EXPECT_FALSE(allocator.SaveDevice(kthAddress(key + 1))); + EXPECT_EQ(dummy, 44); + // paired: 1, 2 ... 199, 200, + // scanned: 0 + + EXPECT_EQ(allocator.AllocateId(kthAddress(key + 1)), id++); + EXPECT_TRUE(allocator.SaveDevice(kthAddress(key + 1))); + EXPECT_EQ(dummy, 88); + // paired: 2 ... 199, 200, 201 + // scanned: 0 + + EXPECT_EQ(allocator.AllocateId(kthAddress(1)), id++); + // paired: 2 ... 199, 200, 201, + // scanned: 0, 1 + + // save it and make sure the callback is called + EXPECT_EQ(allocator.AllocateId(kthAddress(key + 2)), id++); + EXPECT_EQ(allocator.AllocateId(kthAddress(key + 3)), id++); + // paired: 2 ... 199, 200, 201, + // scanned: 0, 1, 202, 203 + + dummy = 44; + EXPECT_TRUE(allocator.SaveDevice(kthAddress(key + 2))); + EXPECT_EQ(dummy, 88); + EXPECT_TRUE(allocator.SaveDevice(kthAddress(key + 3))); + EXPECT_EQ(dummy, 176); + // paired: 4 ... 199, 200, 201, 202, 203 + // scanned: 0, 1 + + // should fail, since id had been saved + EXPECT_FALSE(allocator.SaveDevice(kthAddress(key + 2))); + EXPECT_EQ(dummy, 176); + + // forget + EXPECT_FALSE(allocator.ForgetDevice(kthAddress(key + 200))); + EXPECT_EQ(dummy, 176); + EXPECT_TRUE(allocator.ForgetDevice(kthAddress(key + 2))); + EXPECT_EQ(dummy, 88); + // paired: 4 ... 199, 200, 201, 203 + // scanned: 0, 1 + + // save it and make sure the callback is called + EXPECT_EQ(allocator.AllocateId(kthAddress(key + 2)), id++); + EXPECT_EQ(allocator.AllocateId(kthAddress(key + 4)), id++); + EXPECT_EQ(allocator.AllocateId(kthAddress(key + 5)), id++); + // paired: 4 ... 199, 200, 201, 203 + // scanned: 0, 1, 202, 204, 205 + + EXPECT_TRUE(allocator.SaveDevice(kthAddress(key + 2))); + EXPECT_EQ(dummy, 176); + EXPECT_FALSE(allocator.SaveDevice(kthAddress(key + 3))); + EXPECT_EQ(dummy, 176); + EXPECT_TRUE(allocator.SaveDevice(kthAddress(key + 4))); + EXPECT_EQ(dummy, 352); + // paired: 6 ... 199, 200, 201, 203, 202, 204 + // scanned: 0, 1, 205 + + // verify paired: + for (key = 6; key <= 199; key++) { + dummy = 10; + EXPECT_TRUE(allocator.ForgetDevice(kthAddress(key))); + EXPECT_EQ(dummy, 5); + } + for (size_t k = MetricIdAllocator::kMaxNumPairedDevicesInMemory; + k <= MetricIdAllocator::kMaxNumPairedDevicesInMemory + 4; k++) { + dummy = 10; + EXPECT_TRUE(allocator.ForgetDevice(kthAddress(k))); + EXPECT_EQ(dummy, 5); + } + + // verify scanned + dummy = 4; + EXPECT_TRUE(allocator.SaveDevice(kthAddress(0))); + EXPECT_TRUE(allocator.SaveDevice(kthAddress(1))); + EXPECT_TRUE(allocator.SaveDevice( + kthAddress(MetricIdAllocator::kMaxNumPairedDevicesInMemory + 5))); + EXPECT_EQ(dummy, 32); + + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorFullScannedMap) { + auto& allocator = MetricIdAllocator::GetInstance(); + std::unordered_map paired_device_map; + int dummy = 22; + int* pointer = &dummy; + MetricIdAllocator::Callback save_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer * 2; + return true; + }; + MetricIdAllocator::Callback forget_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer / 2; + return true; + }; + + EXPECT_TRUE( + allocator.Init(paired_device_map, save_callback, forget_callback)); + + // allocate kMaxNumUnpairedDevicesInMemory ids + // comments based on kMaxNumUnpairedDevicesInMemory = 200 + for (int key = 0; + key < + static_cast(MetricIdAllocator::kMaxNumUnpairedDevicesInMemory); + key++) { + EXPECT_EQ(allocator.AllocateId(kthAddress(key)), + key + MetricIdAllocator::kMinId); + } + // scanned: 0, 1, 2 ... 199, + // paired: + + int id = MetricIdAllocator::kMaxNumUnpairedDevicesInMemory + + MetricIdAllocator::kMinId; + RawAddress addr = + kthAddress(MetricIdAllocator::kMaxNumUnpairedDevicesInMemory); + EXPECT_EQ(allocator.AllocateId(addr), id); + // scanned: 1, 2 ... 199, 200 + + // save it and make sure the callback is called + EXPECT_TRUE(allocator.SaveDevice(addr)); + EXPECT_EQ(allocator.AllocateId(addr), id); + EXPECT_EQ(dummy, 44); + // paired: 200, + // scanned: 1, 2 ... 199, + id++; + + addr = kthAddress(MetricIdAllocator::kMaxNumUnpairedDevicesInMemory + 1); + EXPECT_EQ(allocator.AllocateId(addr), id++); + // paired: 200, + // scanned: 1, 2 ... 199, 201 + + // try to allocate for device 0, 1, 2, 3, 4....199 + // we should have a new id every time, + // since the scanned map is full at this point + for (int key = 0; + key < + static_cast(MetricIdAllocator::kMaxNumUnpairedDevicesInMemory); + key++) { + EXPECT_EQ(allocator.AllocateId(kthAddress(key)), id++); + } + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorMultiThreadPressureTest) { + std::unordered_map paired_device_map; + auto& allocator = MetricIdAllocator::GetInstance(); + int dummy = 22; + int* pointer = &dummy; + MetricIdAllocator::Callback save_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer + 1; + return true; + }; + MetricIdAllocator::Callback forget_callback = [pointer](const RawAddress&, + const int) { + *pointer = *pointer - 1; + return true; + }; + EXPECT_TRUE( + allocator.Init(paired_device_map, save_callback, forget_callback)); + + // make sure no deadlock + std::vector workers; + for (int key = 0; + key < static_cast(MetricIdAllocator::kMaxNumPairedDevicesInMemory); + key++) { + workers.push_back(std::thread([key]() { + auto& allocator = MetricIdAllocator::GetInstance(); + RawAddress fake_mac_address = kthAddress(key); + allocator.AllocateId(fake_mac_address); + EXPECT_TRUE(allocator.SaveDevice(fake_mac_address)); + EXPECT_TRUE(allocator.ForgetDevice(fake_mac_address)); + })); + } + for (auto& worker : workers) { + worker.join(); + } + EXPECT_TRUE(allocator.IsEmpty()); + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorWrapAroundTest1) { + std::unordered_map paired_device_map; + auto& allocator = MetricIdAllocator::GetInstance(); + MetricIdAllocator::Callback callback = [](const RawAddress&, const int) { + return true; + }; + + // make a sparse paired_device_map + int min_id = MetricIdAllocator::kMinId; + paired_device_map[kthAddress(min_id)] = min_id; + paired_device_map[kthAddress(min_id + 1)] = min_id + 1; + paired_device_map[kthAddress(min_id + 3)] = min_id + 3; + paired_device_map[kthAddress(min_id + 4)] = min_id + 4; + + int max_id = MetricIdAllocator::kMaxId; + paired_device_map[kthAddress(max_id - 3)] = max_id - 3; + paired_device_map[kthAddress(max_id - 4)] = max_id - 4; + + EXPECT_TRUE(allocator.Init(paired_device_map, callback, callback)); + + // next id should be max_id - 2, max_id - 1, max_id, min_id + 2, min_id + 5 + EXPECT_EQ(allocator.AllocateId(kthAddress(max_id - 2)), max_id - 2); + EXPECT_EQ(allocator.AllocateId(kthAddress(max_id - 1)), max_id - 1); + EXPECT_EQ(allocator.AllocateId(kthAddress(max_id)), max_id); + EXPECT_EQ(allocator.AllocateId(kthAddress(min_id + 2)), min_id + 2); + EXPECT_EQ(allocator.AllocateId(kthAddress(min_id + 5)), min_id + 5); + + EXPECT_TRUE(allocator.Close()); +} + +TEST(BluetoothMetricIdAllocatorTest, MetricIdAllocatorWrapAroundTest2) { + std::unordered_map paired_device_map; + auto& allocator = MetricIdAllocator::GetInstance(); + MetricIdAllocator::Callback callback = [](const RawAddress&, const int) { + return true; + }; + + // make a sparse paired_device_map + int min_id = MetricIdAllocator::kMinId; + int max_id = MetricIdAllocator::kMaxId; + paired_device_map[kthAddress(max_id)] = max_id; + + EXPECT_TRUE(allocator.Init(paired_device_map, callback, callback)); + + // next id should be min_id, min_id + 1 + EXPECT_EQ(allocator.AllocateId(kthAddress(min_id)), min_id); + EXPECT_EQ(allocator.AllocateId(kthAddress(min_id + 1)), min_id + 1); + + EXPECT_TRUE(allocator.Close()); +} + +} // namespace testing diff --git a/types/raw_address.h b/types/raw_address.h index 49443a8c1..b0035c908 100644 --- a/types/raw_address.h +++ b/types/raw_address.h @@ -18,6 +18,7 @@ #pragma once +#include #include /** Bluetooth Address */ @@ -64,3 +65,14 @@ inline std::ostream& operator<<(std::ostream& os, const RawAddress& a) { os << a.ToString(); return os; } + +template <> +struct std::hash { + std::size_t operator()(const RawAddress& val) const { + static_assert(sizeof(uint64_t) >= RawAddress::kLength); + uint64_t int_addr = 0; + memcpy(reinterpret_cast(&int_addr), val.address, + RawAddress::kLength); + return std::hash{}(int_addr); + } +}; -- 2.11.0