camera2: Add camera client eviction enforcement.

- This updates the CameraService to implement client
  eviction behavior based on process priority.

Bug: 19186859

Change-Id: I646939b1cdf1a2237c4e5044164d55a2542cf36e

4 files changed, 1089 insertions, 0 deletions

diff --git a/services/camera/libcameraservice/utils/AutoConditionLock.cpp b/services/camera/libcameraservice/utils/AutoConditionLock.cpp
new file mode 100644
index 0000000..c8ee965
--- /dev/null
+++ b/services/camera/libcameraservice/utils/AutoConditionLock.cpp
@@ -0,0 +1,90 @@
+/*
+ * 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.
+ */
+
+#include "AutoConditionLock.h"
+
+namespace android {
+
+WaitableMutexWrapper::WaitableMutexWrapper(Mutex* mutex) : mMutex{mutex}, mState{false} {}
+
+WaitableMutexWrapper::~WaitableMutexWrapper() {}
+
+// Locks manager-owned mutex
+AutoConditionLock::AutoConditionLock(const std::shared_ptr<WaitableMutexWrapper>& manager) :
+        mManager{manager}, mAutoLock{manager->mMutex} {}
+
+// Unlocks manager-owned mutex
+AutoConditionLock::~AutoConditionLock() {
+    // Unset the condition and wake everyone up before releasing lock
+    mManager->mState = false;
+    mManager->mCondition.broadcast();
+}
+
+std::unique_ptr<AutoConditionLock> AutoConditionLock::waitAndAcquire(
+        const std::shared_ptr<WaitableMutexWrapper>& manager, nsecs_t waitTime) {
+
+    if (manager == nullptr || manager->mMutex == nullptr) {
+        // Bad input, return null
+        return std::unique_ptr<AutoConditionLock>{nullptr};
+    }
+
+    // Acquire scoped lock
+    std::unique_ptr<AutoConditionLock> scopedLock(new AutoConditionLock(manager));
+
+    // Figure out what time in the future we should hit the timeout
+    nsecs_t failTime = systemTime(SYSTEM_TIME_MONOTONIC) + waitTime;
+
+    // Wait until we timeout, or success
+    while(manager->mState) {
+        status_t ret = manager->mCondition.waitRelative(*(manager->mMutex), waitTime);
+        if (ret != NO_ERROR) {
+            // Timed out or whatever, return null
+            return std::unique_ptr<AutoConditionLock>{nullptr};
+        }
+        waitTime = failTime - systemTime(SYSTEM_TIME_MONOTONIC);
+    }
+
+    // Set the condition and return
+    manager->mState = true;
+    return scopedLock;
+}
+
+std::unique_ptr<AutoConditionLock> AutoConditionLock::waitAndAcquire(
+        const std::shared_ptr<WaitableMutexWrapper>& manager) {
+
+    if (manager == nullptr || manager->mMutex == nullptr) {
+        // Bad input, return null
+        return std::unique_ptr<AutoConditionLock>{nullptr};
+    }
+
+    // Acquire scoped lock
+    std::unique_ptr<AutoConditionLock> scopedLock(new AutoConditionLock(manager));
+
+    // Wait until we timeout, or success
+    while(manager->mState) {
+        status_t ret = manager->mCondition.wait(*(manager->mMutex));
+        if (ret != NO_ERROR) {
+            // Timed out or whatever, return null
+            return std::unique_ptr<AutoConditionLock>{nullptr};
+        }
+    }
+
+    // Set the condition and return
+    manager->mState = true;
+    return scopedLock;
+}
+
+}; // namespace android
diff --git a/services/camera/libcameraservice/utils/AutoConditionLock.h b/services/camera/libcameraservice/utils/AutoConditionLock.h
new file mode 100644
index 0000000..9a3eafc
--- /dev/null
+++ b/services/camera/libcameraservice/utils/AutoConditionLock.h
@@ -0,0 +1,99 @@
+/*
+ * 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_SCOPED_CONDITION_H
+#define ANDROID_SERVICE_UTILS_SCOPED_CONDITION_H
+
+#include <utils/Timers.h>
+#include <utils/Condition.h>
+#include <utils/Errors.h>
+#include <utils/Mutex.h>
+
+#include <memory>
+
+namespace android {
+
+/**
+ * WaitableMutexWrapper can be used with AutoConditionLock to construct scoped locks for the
+ * wrapped Mutex with timeouts for lock acquisition.
+ */
+class WaitableMutexWrapper {
+    friend class AutoConditionLock;
+public:
+    /**
+     * Construct the ConditionManger with the given Mutex.
+     */
+    WaitableMutexWrapper(Mutex* mutex);
+
+    virtual ~WaitableMutexWrapper();
+private:
+    Mutex* mMutex;
+    bool mState;
+    Condition mCondition;
+};
+
+/**
+ * AutoConditionLock is a scoped lock similar to Mutex::Autolock, but allows timeouts to be
+ * specified for lock acquisition.
+ *
+ * AutoConditionLock is used with a WaitableMutexWrapper to lock/unlock the WaitableMutexWrapper's
+ * wrapped Mutex, and wait/set/signal the WaitableMutexWrapper's wrapped condition. To use this,
+ * call AutoConditionLock::waitAndAcquire to get an instance.  This will:
+ *      - Lock the given WaitableMutexWrapper's mutex.
+ *      - Wait for the WaitableMutexWrapper's condition to become false, or timeout.
+ *      - Set the WaitableMutexWrapper's condition to true.
+ *
+ * When the AutoConditionLock goes out of scope and is destroyed, this will:
+ *      - Set the WaitableMutexWrapper's condition to false.
+ *      - Signal threads waiting on this condition to wakeup.
+ *      - Release WaitableMutexWrapper's mutex.
+ */
+class AutoConditionLock final {
+public:
+    AutoConditionLock() = delete;
+    AutoConditionLock(const AutoConditionLock& other) = delete;
+    AutoConditionLock & operator=(const AutoConditionLock&) = delete;
+
+    ~AutoConditionLock();
+
+    /**
+     * Make a new AutoConditionLock from a given WaitableMutexWrapper, waiting up to waitTime
+     * nanoseconds to acquire the WaitableMutexWrapper's wrapped lock.
+     *
+     * Return an empty unique_ptr if this fails, or a timeout occurs.
+     */
+    static std::unique_ptr<AutoConditionLock> waitAndAcquire(
+            const std::shared_ptr<WaitableMutexWrapper>& manager, nsecs_t waitTime);
+
+    /**
+     * Make a new AutoConditionLock from a given WaitableMutexWrapper, waiting indefinitely to
+     * acquire the WaitableMutexWrapper's wrapped lock.
+     *
+     * Return an empty unique_ptr if this fails.
+     */
+    static std::unique_ptr<AutoConditionLock> waitAndAcquire(
+            const std::shared_ptr<WaitableMutexWrapper>& manager);
+private:
+    AutoConditionLock(const std::shared_ptr<WaitableMutexWrapper>& manager);
+
+    std::shared_ptr<WaitableMutexWrapper> mManager;
+    Mutex::Autolock mAutoLock;
+};
+
+}; // namespace android
+
+#endif // ANDROID_SERVICE_UTILS_SCOPED_CONDITION_H
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
diff --git a/services/camera/libcameraservice/utils/RingBuffer.h b/services/camera/libcameraservice/utils/RingBuffer.h
new file mode 100644
index 0000000..df7c00e
--- /dev/null
+++ b/services/camera/libcameraservice/utils/RingBuffer.h
@@ -0,0 +1,361 @@
+/*
+ * 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_RING_BUFFER_H
+#define ANDROID_SERVICE_UTILS_RING_BUFFER_H
+
+#include <utils/Log.h>
+#include <cutils/compiler.h>
+
+#include <iterator>
+#include <utility>
+#include <vector>
+
+namespace android {
+
+/**
+ * A RingBuffer class that maintains an array of objects that can grow up to a certain size.
+ * Elements added to the RingBuffer are inserted in the logical front of the buffer, and
+ * invalidate all current iterators for that RingBuffer object.
+ */
+template <class T>
+class RingBuffer final {
+public:
+
+    /**
+     * Construct a RingBuffer that can grow up to the given length.
+     */
+    RingBuffer(size_t length);
+
+    /**
+     * Forward iterator to this class.  Implements an std:forward_iterator.
+     */
+    class iterator : public std::iterator<std::forward_iterator_tag, T> {
+    public:
+        iterator(T* ptr, size_t size, size_t pos, size_t ctr);
+
+        iterator& operator++();
+
+        iterator operator++(int);
+
+        bool operator==(const iterator& rhs);
+
+        bool operator!=(const iterator& rhs);
+
+        T& operator*();
+
+        T* operator->();
+
+    private:
+        T* mPtr;
+        size_t mSize;
+        size_t mPos;
+        size_t mCtr;
+    };
+
+    /**
+     * Constant forward iterator to this class.  Implements an std:forward_iterator.
+     */
+    class const_iterator : public std::iterator<std::forward_iterator_tag, T> {
+    public:
+        const_iterator(const T* ptr, size_t size, size_t pos, size_t ctr);
+
+        const_iterator& operator++();
+
+        const_iterator operator++(int);
+
+        bool operator==(const const_iterator& rhs);
+
+        bool operator!=(const const_iterator& rhs);
+
+        const T& operator*();
+
+        const T* operator->();
+
+    private:
+        const T* mPtr;
+        size_t mSize;
+        size_t mPos;
+        size_t mCtr;
+    };
+
+    /**
+     * Adds item to the front of this RingBuffer.  If the RingBuffer is at its maximum length,
+     * this will result in the last element being replaced (this is done using the element's
+     * assignment operator).
+     *
+     * All current iterators are invalidated.
+     */
+    void add(const T& item);
+
+    /**
+     * Moves item to the front of this RingBuffer.  Following a call to this, item should no
+     * longer be used.  If the RingBuffer is at its maximum length, this will result in the
+     * last element being replaced (this is done using the element's assignment operator).
+     *
+     * All current iterators are invalidated.
+     */
+    void add(T&& item);
+
+    /**
+     * Construct item in-place in the front of this RingBuffer using the given arguments.  If
+     * the RingBuffer is at its maximum length, this will result in the last element being
+     * replaced (this is done using the element's assignment operator).
+     *
+     * All current iterators are invalidated.
+     */
+    template <class... Args>
+    void emplace(Args&&... args);
+
+    /**
+     * Get an iterator to the front of this RingBuffer.
+     */
+    iterator begin();
+
+    /**
+     * Get an iterator to the end of this RingBuffer.
+     */
+    iterator end();
+
+    /**
+     * Get a const_iterator to the front of this RingBuffer.
+     */
+    const_iterator begin() const;
+
+    /**
+     * Get a const_iterator to the end of this RingBuffer.
+     */
+    const_iterator end() const;
+
+    /**
+     * Return a reference to the element at a given index.  If the index is out of range for
+     * this ringbuffer, [0, size), the behavior for this is undefined.
+     */
+    T& operator[](size_t index);
+
+    /**
+     * Return a const reference to the element at a given index.  If the index is out of range
+     * for this ringbuffer, [0, size), the behavior for this is undefined.
+     */
+    const T& operator[](size_t index) const;
+
+    /**
+     * Return the current size of this RingBuffer.
+     */
+    size_t size() const;
+
+    /**
+     * Remove all elements from this RingBuffer and set the size to 0.
+     */
+    void clear();
+
+private:
+    size_t mFrontIdx;
+    size_t mMaxBufferSize;
+    std::vector<T> mBuffer;
+}; // class RingBuffer
+
+
+template <class T>
+RingBuffer<T>::RingBuffer(size_t length) : mFrontIdx{0}, mMaxBufferSize{length} {}
+
+template <class T>
+RingBuffer<T>::iterator::iterator(T* ptr, size_t size, size_t pos, size_t ctr) :
+        mPtr{ptr}, mSize{size}, mPos{pos}, mCtr{ctr} {}
+
+template <class T>
+typename RingBuffer<T>::iterator& RingBuffer<T>::iterator::operator++() {
+    ++mCtr;
+
+    if (CC_UNLIKELY(mCtr == mSize)) {
+        mPos = mSize;
+        return *this;
+    }
+
+    mPos = ((CC_UNLIKELY(mPos == 0)) ? mSize - 1 : mPos - 1);
+    return *this;
+}
+
+template <class T>
+typename RingBuffer<T>::iterator RingBuffer<T>::iterator::operator++(int) {
+    iterator tmp{mPtr, mSize, mPos, mCtr};
+    ++(*this);
+    return tmp;
+}
+
+template <class T>
+bool RingBuffer<T>::iterator::operator==(const iterator& rhs) {
+    return (mPtr + mPos) == (rhs.mPtr + rhs.mPos);
+}
+
+template <class T>
+bool RingBuffer<T>::iterator::operator!=(const iterator& rhs) {
+    return (mPtr + mPos) != (rhs.mPtr + rhs.mPos);
+}
+
+template <class T>
+T& RingBuffer<T>::iterator::operator*() {
+    return *(mPtr + mPos);
+}
+
+template <class T>
+T* RingBuffer<T>::iterator::operator->() {
+    return mPtr + mPos;
+}
+
+template <class T>
+RingBuffer<T>::const_iterator::const_iterator(const T* ptr, size_t size, size_t pos, size_t ctr) :
+        mPtr{ptr}, mSize{size}, mPos{pos}, mCtr{ctr} {}
+
+template <class T>
+typename RingBuffer<T>::const_iterator& RingBuffer<T>::const_iterator::operator++() {
+    ++mCtr;
+
+    if (CC_UNLIKELY(mCtr == mSize)) {
+        mPos = mSize;
+        return *this;
+    }
+
+    mPos = ((CC_UNLIKELY(mPos == 0)) ? mSize - 1 : mPos - 1);
+    return *this;
+}
+
+template <class T>
+typename RingBuffer<T>::const_iterator RingBuffer<T>::const_iterator::operator++(int) {
+    const_iterator tmp{mPtr, mSize, mPos, mCtr};
+    ++(*this);
+    return tmp;
+}
+
+template <class T>
+bool RingBuffer<T>::const_iterator::operator==(const const_iterator& rhs) {
+    return (mPtr + mPos) == (rhs.mPtr + rhs.mPos);
+}
+
+template <class T>
+bool RingBuffer<T>::const_iterator::operator!=(const const_iterator& rhs) {
+    return (mPtr + mPos) != (rhs.mPtr + rhs.mPos);
+}
+
+template <class T>
+const T& RingBuffer<T>::const_iterator::operator*() {
+    return *(mPtr + mPos);
+}
+
+template <class T>
+const T* RingBuffer<T>::const_iterator::operator->() {
+    return mPtr + mPos;
+}
+
+template <class T>
+void RingBuffer<T>::add(const T& item) {
+    if (mBuffer.size() < mMaxBufferSize) {
+        mBuffer.push_back(item);
+        mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
+        return;
+    }
+
+    mBuffer[mFrontIdx] = item;
+    mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
+}
+
+template <class T>
+void RingBuffer<T>::add(T&& item) {
+    if (mBuffer.size() != mMaxBufferSize) {
+        mBuffer.push_back(std::forward<T>(item));
+        mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
+        return;
+    }
+
+    // Only works for types with move assignment operator
+    mBuffer[mFrontIdx] = std::forward<T>(item);
+    mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
+}
+
+template <class T>
+template <class... Args>
+void RingBuffer<T>::emplace(Args&&... args) {
+    if (mBuffer.size() != mMaxBufferSize) {
+        mBuffer.emplace_back(std::forward<Args>(args)...);
+        mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
+        return;
+    }
+
+    // Only works for types with move assignment operator
+    mBuffer[mFrontIdx] = T(std::forward<Args>(args)...);
+    mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
+}
+
+template <class T>
+typename RingBuffer<T>::iterator RingBuffer<T>::begin() {
+    size_t tmp = (mBuffer.size() == 0) ? 0 : mBuffer.size() - 1;
+    return iterator(mBuffer.data(), mBuffer.size(), (mFrontIdx == 0) ? tmp : mFrontIdx - 1, 0);
+}
+
+template <class T>
+typename RingBuffer<T>::iterator RingBuffer<T>::end() {
+    size_t s = mBuffer.size();
+    return iterator(mBuffer.data(), s, s, s);
+}
+
+template <class T>
+typename RingBuffer<T>::const_iterator RingBuffer<T>::begin() const {
+    size_t tmp = (mBuffer.size() == 0) ? 0 : mBuffer.size() - 1;
+    return const_iterator(mBuffer.data(), mBuffer.size(),
+            (mFrontIdx == 0) ? tmp : mFrontIdx - 1, 0);
+}
+
+template <class T>
+typename RingBuffer<T>::const_iterator RingBuffer<T>::end() const {
+    size_t s = mBuffer.size();
+    return const_iterator(mBuffer.data(), s, s, s);
+}
+
+template <class T>
+T& RingBuffer<T>::operator[](size_t index) {
+    LOG_ALWAYS_FATAL_IF(index >= mBuffer.size(), "Index %zu out of bounds, size is %zu.",
+            index, mBuffer.size());
+    size_t pos = (index >= mFrontIdx) ?
+            mBuffer.size() - 1 - (index - mFrontIdx) : mFrontIdx - 1 - index;
+    return mBuffer[pos];
+}
+
+template <class T>
+const T& RingBuffer<T>::operator[](size_t index) const {
+    LOG_ALWAYS_FATAL_IF(index >= mBuffer.size(), "Index %zu out of bounds, size is %zu.",
+            index, mBuffer.size());
+    size_t pos = (index >= mFrontIdx) ?
+            mBuffer.size() - 1 - (index - mFrontIdx) : mFrontIdx - 1 - index;
+    return mBuffer[pos];
+}
+
+template <class T>
+size_t RingBuffer<T>::size() const {
+    return mBuffer.size();
+}
+
+template <class T>
+void RingBuffer<T>::clear() {
+    mBuffer.clear();
+    mFrontIdx = 0;
+}
+
+}; // namespace android
+
+#endif // ANDROID_SERVICE_UTILS_RING_BUFFER_H
+
+