camera2: Add camera client eviction enforcement.
- This updates the CameraService to implement client
eviction behavior based on process priority.
Bug: 19186859
Change-Id: I646939b1cdf1a2237c4e5044164d55a2542cf36e
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