diff options
Diffstat (limited to 'services/camera/libcameraservice/utils/ClientManager.h')
| -rw-r--r-- | services/camera/libcameraservice/utils/ClientManager.h | 539 |
1 files changed, 539 insertions, 0 deletions
diff --git a/services/camera/libcameraservice/utils/ClientManager.h b/services/camera/libcameraservice/utils/ClientManager.h new file mode 100644 index 0000000..ad5486d --- /dev/null +++ b/services/camera/libcameraservice/utils/ClientManager.h @@ -0,0 +1,539 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * 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. + */ + +#ifndef ANDROID_SERVICE_UTILS_EVICTION_POLICY_MANAGER_H +#define ANDROID_SERVICE_UTILS_EVICTION_POLICY_MANAGER_H + +#include <utils/Mutex.h> + +#include <algorithm> +#include <utility> +#include <vector> +#include <set> +#include <map> +#include <memory> + +namespace android { +namespace resource_policy { + +// -------------------------------------------------------------------------------- + +/** + * The ClientDescriptor class is a container for a given key/value pair identifying a shared + * resource, and the corresponding cost, priority, owner ID, and conflicting keys list used + * in determining eviction behavior. + * + * Aside from the priority, these values are immutable once the ClientDescriptor has been + * constructed. + */ +template<class KEY, class VALUE> +class ClientDescriptor final { +public: + ClientDescriptor(const KEY& key, const VALUE& value, int32_t cost, + const std::set<KEY>& conflictingKeys, int32_t priority, int32_t ownerId); + ClientDescriptor(KEY&& key, VALUE&& value, int32_t cost, std::set<KEY>&& conflictingKeys, + int32_t priority, int32_t ownerId); + + ~ClientDescriptor(); + + /** + * Return the key for this descriptor. + */ + const KEY& getKey() const; + + /** + * Return the value for this descriptor. + */ + const VALUE& getValue() const; + + /** + * Return the cost for this descriptor. + */ + int32_t getCost() const; + + /** + * Return the priority for this descriptor. + */ + int32_t getPriority() const; + + /** + * Return the owner ID for this descriptor. + */ + int32_t getOwnerId() const; + + /** + * Return true if the given key is in this descriptor's conflicting keys list. + */ + bool isConflicting(const KEY& key) const; + + /** + * Return the set of all conflicting keys for this descriptor. + */ + std::set<KEY> getConflicting() const; + + /** + * Set the proirity for this descriptor. + */ + void setPriority(int32_t priority); + + // This class is ordered by key + template<class K, class V> + friend bool operator < (const ClientDescriptor<K, V>& a, const ClientDescriptor<K, V>& b); + +private: + KEY mKey; + VALUE mValue; + int32_t mCost; + std::set<KEY> mConflicting; + int32_t mPriority; + int32_t mOwnerId; +}; // class ClientDescriptor + +template<class K, class V> +bool operator < (const ClientDescriptor<K, V>& a, const ClientDescriptor<K, V>& b) { + return a.mKey < b.mKey; +} + +template<class KEY, class VALUE> +ClientDescriptor<KEY, VALUE>::ClientDescriptor(const KEY& key, const VALUE& value, int32_t cost, + const std::set<KEY>& conflictingKeys, int32_t priority, int32_t ownerId) : mKey{key}, + mValue{value}, mCost{cost}, mConflicting{conflictingKeys}, mPriority{priority}, + mOwnerId{ownerId} {} + +template<class KEY, class VALUE> +ClientDescriptor<KEY, VALUE>::ClientDescriptor(KEY&& key, VALUE&& value, int32_t cost, + std::set<KEY>&& conflictingKeys, int32_t priority, int32_t ownerId) : + mKey{std::forward<KEY>(key)}, mValue{std::forward<VALUE>(value)}, mCost{cost}, + mConflicting{std::forward<std::set<KEY>>(conflictingKeys)}, mPriority{priority}, + mOwnerId{ownerId} {} + +template<class KEY, class VALUE> +ClientDescriptor<KEY, VALUE>::~ClientDescriptor() {} + +template<class KEY, class VALUE> +const KEY& ClientDescriptor<KEY, VALUE>::getKey() const { + return mKey; +} + +template<class KEY, class VALUE> +const VALUE& ClientDescriptor<KEY, VALUE>::getValue() const { + return mValue; +} + +template<class KEY, class VALUE> +int32_t ClientDescriptor<KEY, VALUE>::getCost() const { + return mCost; +} + +template<class KEY, class VALUE> +int32_t ClientDescriptor<KEY, VALUE>::getPriority() const { + return mPriority; +} + +template<class KEY, class VALUE> +int32_t ClientDescriptor<KEY, VALUE>::getOwnerId() const { + return mOwnerId; +} + +template<class KEY, class VALUE> +bool ClientDescriptor<KEY, VALUE>::isConflicting(const KEY& key) const { + if (key == mKey) return true; + for (const auto& x : mConflicting) { + if (key == x) return true; + } + return false; +} + +template<class KEY, class VALUE> +std::set<KEY> ClientDescriptor<KEY, VALUE>::getConflicting() const { + return mConflicting; +} + +template<class KEY, class VALUE> +void ClientDescriptor<KEY, VALUE>::setPriority(int32_t priority) { + mPriority = priority; +} + +// -------------------------------------------------------------------------------- + +/** + * The ClientManager class wraps an LRU-ordered list of active clients and implements eviction + * behavior for handling shared resource access. + * + * When adding a new descriptor, eviction behavior is as follows: + * - Keys are unique, adding a descriptor with the same key as an existing descriptor will + * result in the lower-priority of the two being removed. Priority ties result in the + * LRU descriptor being evicted (this means the incoming descriptor be added in this case). + * - Any descriptors with keys that are in the incoming descriptor's 'conflicting keys' list + * will be removed if they have an equal or lower priority than the incoming descriptor; + * if any have a higher priority, the incoming descriptor is removed instead. + * - If the sum of all descriptors' costs, including the incoming descriptor's, is more than + * the max cost allowed for this ClientManager, descriptors with non-zero cost, equal or lower + * priority, and a different owner will be evicted in LRU order until either the cost is less + * than the max cost, or all descriptors meeting this criteria have been evicted and the + * incoming descriptor has the highest priority. Otherwise, the incoming descriptor is + * removed instead. + */ +template<class KEY, class VALUE> +class ClientManager { +public: + // The default maximum "cost" allowed before evicting + static constexpr int32_t DEFAULT_MAX_COST = 100; + + ClientManager(); + ClientManager(int32_t totalCost); + + /** + * Add a given ClientDescriptor to the managed list. ClientDescriptors for clients that + * are evicted by this action are returned in a vector. + * + * This may return the ClientDescriptor passed in if it would be evicted. + */ + std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> addAndEvict( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client); + + /** + * Given a map containing owner (pid) -> priority mappings, update the priority of each + * ClientDescriptor with an owner in this mapping. + */ + void updatePriorities(const std::map<int32_t,int32_t>& ownerPriorityList); + + /** + * Remove all ClientDescriptors. + */ + void removeAll(); + + /** + * Remove and return the ClientDescriptor with a given key. + */ + std::shared_ptr<ClientDescriptor<KEY, VALUE>> remove(const KEY& key); + + /** + * Remove the given ClientDescriptor. + */ + void remove(const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& value); + + /** + * Return a vector of the ClientDescriptors that would be evicted by adding the given + * ClientDescriptor. + * + * This may return the ClientDescriptor passed in if it would be evicted. + */ + std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> wouldEvict( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const; + + /** + * Return a vector of active ClientDescriptors that prevent this client from being added. + */ + std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> getIncompatibleClients( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const; + + /** + * Return a vector containing all currently active ClientDescriptors. + */ + std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> getAll() const; + + /** + * Return a vector containing all keys of currently active ClientDescriptors. + */ + std::vector<KEY> getAllKeys() const; + + /** + * Return a vector of the owner tags of all currently active ClientDescriptors (duplicates + * will be removed). + */ + std::vector<int32_t> getAllOwners() const; + + /** + * Return the ClientDescriptor corresponding to the given key, or an empty shared pointer + * if none exists. + */ + std::shared_ptr<ClientDescriptor<KEY, VALUE>> get(const KEY& key) const; + +protected: + ~ClientManager(); + +private: + + /** + * Return a vector of the ClientDescriptors that would be evicted by adding the given + * ClientDescriptor. If returnIncompatibleClients is set to true, instead, return the + * vector of ClientDescriptors that are higher priority than the incoming client and + * either conflict with this client, or contribute to the resource cost if that would + * prevent the incoming client from being added. + * + * This may return the ClientDescriptor passed in. + */ + std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> wouldEvictLocked( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client, + bool returnIncompatibleClients = false) const; + + int64_t getCurrentCostLocked() const; + + mutable Mutex mLock; + int32_t mMaxCost; + // LRU ordered, most recent at end + std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> mClients; +}; // class ClientManager + +template<class KEY, class VALUE> +ClientManager<KEY, VALUE>::ClientManager() : + ClientManager(DEFAULT_MAX_COST) {} + +template<class KEY, class VALUE> +ClientManager<KEY, VALUE>::ClientManager(int32_t totalCost) : mMaxCost(totalCost) {} + +template<class KEY, class VALUE> +ClientManager<KEY, VALUE>::~ClientManager() {} + +template<class KEY, class VALUE> +std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> ClientManager<KEY, VALUE>::wouldEvict( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const { + Mutex::Autolock lock(mLock); + return wouldEvictLocked(client); +} + +template<class KEY, class VALUE> +std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> +ClientManager<KEY, VALUE>::getIncompatibleClients( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const { + Mutex::Autolock lock(mLock); + return wouldEvictLocked(client, /*returnIncompatibleClients*/true); +} + +template<class KEY, class VALUE> +std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> +ClientManager<KEY, VALUE>::wouldEvictLocked( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client, + bool returnIncompatibleClients) const { + + std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> evictList; + + // Disallow null clients, return input + if (client == nullptr) { + evictList.push_back(client); + return evictList; + } + + const KEY& key = client->getKey(); + int32_t cost = client->getCost(); + int32_t priority = client->getPriority(); + int32_t owner = client->getOwnerId(); + + int64_t totalCost = getCurrentCostLocked() + cost; + + // Determine the MRU of the owners tied for having the highest priority + int32_t highestPriorityOwner = owner; + int32_t highestPriority = priority; + for (const auto& i : mClients) { + int32_t curPriority = i->getPriority(); + if (curPriority >= highestPriority) { + highestPriority = curPriority; + highestPriorityOwner = i->getOwnerId(); + } + } + + if (highestPriority == priority) { + // Switch back owner if the incoming client has the highest priority, as it is MRU + highestPriorityOwner = owner; + } + + // Build eviction list of clients to remove + for (const auto& i : mClients) { + const KEY& curKey = i->getKey(); + int32_t curCost = i->getCost(); + int32_t curPriority = i->getPriority(); + int32_t curOwner = i->getOwnerId(); + + bool conflicting = (curKey == key || i->isConflicting(key) || + client->isConflicting(curKey)); + + if (!returnIncompatibleClients) { + // Find evicted clients + + if (conflicting && curPriority > priority) { + // Pre-existing conflicting client with higher priority exists + evictList.clear(); + evictList.push_back(client); + return evictList; + } else if (conflicting || ((totalCost > mMaxCost && curCost > 0) && + (curPriority <= priority) && + !(highestPriorityOwner == owner && owner == curOwner))) { + // Add a pre-existing client to the eviction list if: + // - We are adding a client with higher priority that conflicts with this one. + // - The total cost including the incoming client's is more than the allowable + // maximum, and the client has a non-zero cost, lower priority, and a different + // owner than the incoming client when the incoming client has the + // highest priority. + evictList.push_back(i); + totalCost -= curCost; + } + } else { + // Find clients preventing the incoming client from being added + + if (curPriority > priority && (conflicting || (totalCost > mMaxCost && curCost > 0))) { + // Pre-existing conflicting client with higher priority exists + evictList.push_back(i); + } + } + } + + // Immediately return the incompatible clients if we are calculating these instead + if (returnIncompatibleClients) { + return evictList; + } + + // If the total cost is too high, return the input unless the input has the highest priority + if (totalCost > mMaxCost && highestPriorityOwner != owner) { + evictList.clear(); + evictList.push_back(client); + return evictList; + } + + return evictList; + +} + +template<class KEY, class VALUE> +std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> ClientManager<KEY, VALUE>::addAndEvict( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) { + Mutex::Autolock lock(mLock); + auto evicted = wouldEvictLocked(client); + auto it = evicted.begin(); + if (it != evicted.end() && *it == client) { + return evicted; + } + + auto iter = evicted.cbegin(); + + // Remove evicted clients from list + mClients.erase(std::remove_if(mClients.begin(), mClients.end(), + [&iter] (std::shared_ptr<ClientDescriptor<KEY, VALUE>>& curClientPtr) { + if (curClientPtr->getKey() == (*iter)->getKey()) { + iter++; + return true; + } + return false; + }), mClients.end()); + + mClients.push_back(client); + + return evicted; +} + +template<class KEY, class VALUE> +std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> +ClientManager<KEY, VALUE>::getAll() const { + Mutex::Autolock lock(mLock); + return mClients; +} + +template<class KEY, class VALUE> +std::vector<KEY> ClientManager<KEY, VALUE>::getAllKeys() const { + Mutex::Autolock lock(mLock); + std::vector<KEY> keys(mClients.size()); + for (const auto& i : mClients) { + keys.push_back(i->getKey()); + } + return keys; +} + +template<class KEY, class VALUE> +std::vector<int32_t> ClientManager<KEY, VALUE>::getAllOwners() const { + Mutex::Autolock lock(mLock); + std::set<int32_t> owners; + for (const auto& i : mClients) { + owners.emplace(i->getOwnerId()); + } + return std::vector<int32_t>(owners.begin(), owners.end()); +} + +template<class KEY, class VALUE> +void ClientManager<KEY, VALUE>::updatePriorities( + const std::map<int32_t,int32_t>& ownerPriorityList) { + Mutex::Autolock lock(mLock); + for (auto& i : mClients) { + auto j = ownerPriorityList.find(i->getOwnerId()); + if (j != ownerPriorityList.end()) { + i->setPriority(j->second); + } + } +} + +template<class KEY, class VALUE> +std::shared_ptr<ClientDescriptor<KEY, VALUE>> ClientManager<KEY, VALUE>::get( + const KEY& key) const { + Mutex::Autolock lock(mLock); + for (const auto& i : mClients) { + if (i->getKey() == key) return i; + } + return std::shared_ptr<ClientDescriptor<KEY, VALUE>>(nullptr); +} + +template<class KEY, class VALUE> +void ClientManager<KEY, VALUE>::removeAll() { + Mutex::Autolock lock(mLock); + mClients.clear(); +} + +template<class KEY, class VALUE> +std::shared_ptr<ClientDescriptor<KEY, VALUE>> ClientManager<KEY, VALUE>::remove(const KEY& key) { + Mutex::Autolock lock(mLock); + + std::shared_ptr<ClientDescriptor<KEY, VALUE>> ret; + + // Remove evicted clients from list + mClients.erase(std::remove_if(mClients.begin(), mClients.end(), + [&key, &ret] (std::shared_ptr<ClientDescriptor<KEY, VALUE>>& curClientPtr) { + if (curClientPtr->getKey() == key) { + ret = curClientPtr; + return true; + } + return false; + }), mClients.end()); + + return ret; +} + +template<class KEY, class VALUE> +void ClientManager<KEY, VALUE>::remove( + const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& value) { + Mutex::Autolock lock(mLock); + // Remove evicted clients from list + mClients.erase(std::remove_if(mClients.begin(), mClients.end(), + [&value] (std::shared_ptr<ClientDescriptor<KEY, VALUE>>& curClientPtr) { + if (curClientPtr == value) { + return true; + } + return false; + }), mClients.end()); +} + +template<class KEY, class VALUE> +int64_t ClientManager<KEY, VALUE>::getCurrentCostLocked() const { + int64_t totalCost = 0; + for (const auto& x : mClients) { + totalCost += x->getCost(); + } + return totalCost; +} + +// -------------------------------------------------------------------------------- + +}; // namespace resource_policy +}; // namespace android + +#endif // ANDROID_SERVICE_UTILS_EVICTION_POLICY_MANAGER_H |