| /* |
| * Copyright (C) 2019 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. |
| */ |
| |
| #pragma once |
| |
| #include <any> |
| #include <map> |
| #include <mutex> |
| #include <sstream> |
| #include <string> |
| #include <variant> |
| #include <vector> |
| |
| #include <android-base/thread_annotations.h> |
| #include <media/MediaMetricsItem.h> |
| #include <utils/Timers.h> |
| |
| namespace android::mediametrics { |
| |
| // define a way of printing the monostate |
| inline std::ostream & operator<< (std::ostream& s, |
| std::monostate const& v __unused) { |
| s << "none_item"; |
| return s; |
| } |
| |
| // define a way of printing a std::pair. |
| template <typename T, typename U> |
| std::ostream & operator<< (std::ostream& s, |
| const std::pair<T, U>& v) { |
| s << "{ " << v.first << ", " << v.second << " }"; |
| return s; |
| } |
| |
| // define a way of printing a variant |
| // see https://en.cppreference.com/w/cpp/utility/variant/visit |
| template <typename T0, typename ... Ts> |
| std::ostream & operator<< (std::ostream& s, |
| std::variant<T0, Ts...> const& v) { |
| std::visit([&s](auto && arg){ s << std::forward<decltype(arg)>(arg); }, v); |
| return s; |
| } |
| |
| /** |
| * The TimeMachine is used to record timing changes of MediaAnalyticItem |
| * properties. |
| * |
| * Any URL that ends with '#' (AMEDIAMETRICS_PROP_SUFFIX_CHAR_DUPLICATES_ALLOWED) |
| * will have a time sequence that keeps duplicates. |
| * |
| * The TimeMachine is NOT thread safe. |
| */ |
| class TimeMachine final { // made final as we have copy constructor instead of dup() override. |
| public: |
| using Elem = Item::Prop::Elem; // use the Item property element. |
| using PropertyHistory = std::multimap<int64_t /* time */, Elem>; |
| |
| private: |
| |
| // KeyHistory contains no lock. |
| // Access is through the TimeMachine, and a hash-striped lock is used |
| // before calling into KeyHistory. |
| class KeyHistory { |
| public: |
| template <typename T> |
| KeyHistory(T key, uid_t allowUid, int64_t time) |
| : mKey(key) |
| , mAllowUid(allowUid) |
| , mCreationTime(time) |
| , mLastModificationTime(time) |
| { |
| (void)mCreationTime; // suppress unused warning. |
| |
| // allowUid allows an untrusted client with a matching uid to set properties |
| // in this key. |
| // If allowUid == (uid_t)-1, no untrusted client may set properties in the key. |
| if (allowUid != (uid_t)-1) { |
| // Set ALLOWUID property here; does not change after key creation. |
| putValue(AMEDIAMETRICS_PROP_ALLOWUID, (int32_t)allowUid, time); |
| } |
| } |
| |
| KeyHistory(const KeyHistory &other) = default; |
| |
| // Return NO_ERROR only if the passed in uidCheck is -1 or matches |
| // the internal mAllowUid. |
| // An external submit will always have a valid uidCheck parameter. |
| // An internal get request within mediametrics will have a uidCheck == -1 which |
| // we allow to proceed. |
| status_t checkPermission(uid_t uidCheck) const { |
| return uidCheck != (uid_t)-1 && uidCheck != mAllowUid ? PERMISSION_DENIED : NO_ERROR; |
| } |
| |
| template <typename T> |
| status_t getValue(const std::string &property, T* value, int64_t time = 0) const |
| REQUIRES(mPseudoKeyHistoryLock) { |
| if (time == 0) time = systemTime(SYSTEM_TIME_REALTIME); |
| const auto tsptr = mPropertyMap.find(property); |
| if (tsptr == mPropertyMap.end()) return BAD_VALUE; |
| const auto& timeSequence = tsptr->second; |
| auto eptr = timeSequence.upper_bound(time); |
| if (eptr == timeSequence.begin()) return BAD_VALUE; |
| --eptr; |
| if (eptr == timeSequence.end()) return BAD_VALUE; |
| const T* vptr = std::get_if<T>(&eptr->second); |
| if (vptr == nullptr) return BAD_VALUE; |
| *value = *vptr; |
| return NO_ERROR; |
| } |
| |
| template <typename T> |
| status_t getValue(const std::string &property, T defaultValue, int64_t time = 0) const |
| REQUIRES(mPseudoKeyHistoryLock){ |
| T value; |
| return getValue(property, &value, time) != NO_ERROR ? defaultValue : value; |
| } |
| |
| void putProp( |
| const std::string &name, const mediametrics::Item::Prop &prop, int64_t time = 0) |
| REQUIRES(mPseudoKeyHistoryLock) { |
| //alternatively: prop.visit([&](auto value) { putValue(name, value, time); }); |
| putValue(name, prop.get(), time); |
| } |
| |
| template <typename T> |
| void putValue(const std::string &property, T&& e, int64_t time = 0) |
| REQUIRES(mPseudoKeyHistoryLock) { |
| if (time == 0) time = systemTime(SYSTEM_TIME_REALTIME); |
| mLastModificationTime = time; |
| if (mPropertyMap.size() >= kKeyMaxProperties && |
| !mPropertyMap.count(property)) { |
| ALOGV("%s: too many properties, rejecting %s", __func__, property.c_str()); |
| return; |
| } |
| auto& timeSequence = mPropertyMap[property]; |
| Elem el{std::forward<T>(e)}; |
| if (timeSequence.empty() // no elements |
| || property.back() == AMEDIAMETRICS_PROP_SUFFIX_CHAR_DUPLICATES_ALLOWED |
| || timeSequence.rbegin()->second != el) { // value changed |
| timeSequence.emplace_hint(timeSequence.end(), time, std::move(el)); |
| |
| if (timeSequence.size() > kTimeSequenceMaxElements) { |
| ALOGV("%s: restricting maximum elements (discarding oldest) for %s", |
| __func__, property.c_str()); |
| timeSequence.erase(timeSequence.begin()); |
| } |
| } |
| } |
| |
| std::pair<std::string, int32_t> dump(int32_t lines, int64_t time) const |
| REQUIRES(mPseudoKeyHistoryLock) { |
| std::stringstream ss; |
| int32_t ll = lines; |
| for (auto& tsPair : mPropertyMap) { |
| if (ll <= 0) break; |
| std::string s = dump(mKey, tsPair, time); |
| if (s.size() > 0) { |
| --ll; |
| ss << s; |
| } |
| } |
| return { ss.str(), lines - ll }; |
| } |
| |
| int64_t getLastModificationTime() const REQUIRES(mPseudoKeyHistoryLock) { |
| return mLastModificationTime; |
| } |
| |
| private: |
| static std::string dump( |
| const std::string &key, |
| const std::pair<std::string /* prop */, PropertyHistory>& tsPair, |
| int64_t time) { |
| const auto timeSequence = tsPair.second; |
| auto eptr = timeSequence.lower_bound(time); |
| if (eptr == timeSequence.end()) { |
| return {}; // don't dump anything. tsPair.first + "={};\n"; |
| } |
| std::stringstream ss; |
| ss << key << "." << tsPair.first << "={"; |
| |
| time_string_t last_timestring{}; // last timestring used. |
| while (true) { |
| const time_string_t timestring = mediametrics::timeStringFromNs(eptr->first); |
| // find common prefix offset. |
| const size_t offset = commonTimePrefixPosition(timestring.time, |
| last_timestring.time); |
| last_timestring = timestring; |
| ss << "(" << (offset == 0 ? "" : "~") << ×tring.time[offset] |
| << ") " << eptr->second; |
| if (++eptr == timeSequence.end()) { |
| break; |
| } |
| ss << ", "; |
| } |
| ss << "};\n"; |
| return ss.str(); |
| } |
| |
| const std::string mKey; |
| const uid_t mAllowUid; |
| const int64_t mCreationTime; |
| |
| int64_t mLastModificationTime; |
| std::map<std::string /* property */, PropertyHistory> mPropertyMap; |
| }; |
| |
| using History = std::map<std::string /* key */, std::shared_ptr<KeyHistory>>; |
| |
| static inline constexpr size_t kTimeSequenceMaxElements = 50; |
| static inline constexpr size_t kKeyMaxProperties = 50; |
| static inline constexpr size_t kKeyLowWaterMark = 400; |
| static inline constexpr size_t kKeyHighWaterMark = 500; |
| |
| // Estimated max data space usage is 3KB * kKeyHighWaterMark. |
| |
| public: |
| |
| TimeMachine() = default; |
| TimeMachine(size_t keyLowWaterMark, size_t keyHighWaterMark) |
| : mKeyLowWaterMark(keyLowWaterMark) |
| , mKeyHighWaterMark(keyHighWaterMark) { |
| LOG_ALWAYS_FATAL_IF(keyHighWaterMark <= keyLowWaterMark, |
| "%s: required that keyHighWaterMark:%zu > keyLowWaterMark:%zu", |
| __func__, keyHighWaterMark, keyLowWaterMark); |
| } |
| |
| // The TimeMachine copy constructor/assignment uses a deep copy, |
| // though the snapshot is not instantaneous nor isochronous. |
| // |
| // If there are concurrent operations ongoing in the other TimeMachine |
| // then there may be some history more recent than others (a time shear). |
| // This is expected to be a benign addition in history as small number of |
| // future elements are incorporated. |
| TimeMachine(const TimeMachine& other) { |
| *this = other; |
| } |
| TimeMachine& operator=(const TimeMachine& other) { |
| std::lock_guard lock(mLock); |
| mHistory.clear(); |
| |
| { |
| std::lock_guard lock2(other.mLock); |
| mHistory = other.mHistory; |
| mGarbageCollectionCount = other.mGarbageCollectionCount.load(); |
| } |
| |
| // Now that we safely have our own shared pointers, let's dup them |
| // to ensure they are decoupled. We do this by acquiring the other lock. |
| for (const auto &[lkey, lhist] : mHistory) { |
| std::lock_guard lock2(other.getLockForKey(lkey)); |
| mHistory[lkey] = std::make_shared<KeyHistory>(*lhist); |
| } |
| return *this; |
| } |
| |
| /** |
| * Put all the properties from an item into the Time Machine log. |
| */ |
| status_t put(const std::shared_ptr<const mediametrics::Item>& item, bool isTrusted = false) { |
| const int64_t time = item->getTimestamp(); |
| const std::string &key = item->getKey(); |
| |
| ALOGV("%s(%zu, %zu): key: %s isTrusted:%d size:%zu", |
| __func__, mKeyLowWaterMark, mKeyHighWaterMark, |
| key.c_str(), (int)isTrusted, item->count()); |
| std::shared_ptr<KeyHistory> keyHistory; |
| { |
| std::vector<std::any> garbage; |
| std::lock_guard lock(mLock); |
| |
| auto it = mHistory.find(key); |
| if (it == mHistory.end()) { |
| if (!isTrusted) return PERMISSION_DENIED; |
| |
| (void)gc(garbage); |
| |
| // We set the allowUid for client access on key creation. |
| int32_t allowUid = -1; |
| (void)item->get(AMEDIAMETRICS_PROP_ALLOWUID, &allowUid); |
| // no keylock needed here as we are sole owner |
| // until placed on mHistory. |
| keyHistory = std::make_shared<KeyHistory>( |
| key, allowUid, time); |
| mHistory[key] = keyHistory; |
| } else { |
| keyHistory = it->second; |
| } |
| } |
| |
| // deferred contains remote properties (for other keys) to do later. |
| std::vector<const mediametrics::Item::Prop *> deferred; |
| { |
| // handle local properties |
| std::lock_guard lock(getLockForKey(key)); |
| if (!isTrusted) { |
| status_t status = keyHistory->checkPermission(item->getUid()); |
| if (status != NO_ERROR) return status; |
| } |
| |
| for (const auto &prop : *item) { |
| const std::string &name = prop.getName(); |
| if (name.size() == 0 || name[0] == '_') continue; |
| |
| // Cross key settings are with [key]property |
| if (name[0] == '[') { |
| if (!isTrusted) continue; |
| deferred.push_back(&prop); |
| } else { |
| keyHistory->putProp(name, prop, time); |
| } |
| } |
| } |
| |
| // handle remote properties, if any |
| for (const auto propptr : deferred) { |
| const auto &prop = *propptr; |
| const std::string &name = prop.getName(); |
| size_t end = name.find_first_of(']'); // TODO: handle nested [] or escape? |
| if (end == 0) continue; |
| std::string remoteKey = name.substr(1, end - 1); |
| std::string remoteName = name.substr(end + 1); |
| if (remoteKey.size() == 0 || remoteName.size() == 0) continue; |
| std::shared_ptr<KeyHistory> remoteKeyHistory; |
| { |
| std::lock_guard lock(mLock); |
| auto it = mHistory.find(remoteKey); |
| if (it == mHistory.end()) continue; |
| remoteKeyHistory = it->second; |
| } |
| std::lock_guard lock(getLockForKey(remoteKey)); |
| remoteKeyHistory->putProp(remoteName, prop, time); |
| } |
| return NO_ERROR; |
| } |
| |
| template <typename T> |
| status_t get(const std::string &key, const std::string &property, |
| T* value, int32_t uidCheck = -1, int64_t time = 0) const { |
| std::shared_ptr<KeyHistory> keyHistory; |
| { |
| std::lock_guard lock(mLock); |
| const auto it = mHistory.find(key); |
| if (it == mHistory.end()) return BAD_VALUE; |
| keyHistory = it->second; |
| } |
| std::lock_guard lock(getLockForKey(key)); |
| return keyHistory->checkPermission(uidCheck) |
| ?: keyHistory->getValue(property, value, time); |
| } |
| |
| /** |
| * Individual property put. |
| * |
| * Put takes in a time (if none is provided then SYSTEM_TIME_REALTIME is used). |
| */ |
| template <typename T> |
| status_t put(const std::string &url, T &&e, int64_t time = 0) { |
| std::string key; |
| std::string prop; |
| std::shared_ptr<KeyHistory> keyHistory = |
| getKeyHistoryFromUrl(url, &key, &prop); |
| if (keyHistory == nullptr) return BAD_VALUE; |
| if (time == 0) time = systemTime(SYSTEM_TIME_REALTIME); |
| std::lock_guard lock(getLockForKey(key)); |
| keyHistory->putValue(prop, std::forward<T>(e), time); |
| return NO_ERROR; |
| } |
| |
| /** |
| * Individual property get |
| */ |
| template <typename T> |
| status_t get(const std::string &url, T* value, int32_t uidCheck, int64_t time = 0) const { |
| std::string key; |
| std::string prop; |
| std::shared_ptr<KeyHistory> keyHistory = |
| getKeyHistoryFromUrl(url, &key, &prop); |
| if (keyHistory == nullptr) return BAD_VALUE; |
| |
| std::lock_guard lock(getLockForKey(key)); |
| return keyHistory->checkPermission(uidCheck) |
| ?: keyHistory->getValue(prop, value, time); |
| } |
| |
| /** |
| * Individual property get with default |
| */ |
| template <typename T> |
| T get(const std::string &url, const T &defaultValue, int32_t uidCheck, |
| int64_t time = 0) const { |
| T value; |
| return get(url, &value, uidCheck, time) == NO_ERROR |
| ? value : defaultValue; |
| } |
| |
| /** |
| * Returns number of keys in the Time Machine. |
| */ |
| size_t size() const { |
| std::lock_guard lock(mLock); |
| return mHistory.size(); |
| } |
| |
| /** |
| * Clears all properties from the Time Machine. |
| */ |
| void clear() { |
| std::lock_guard lock(mLock); |
| mHistory.clear(); |
| mGarbageCollectionCount = 0; |
| } |
| |
| /** |
| * Returns a pair consisting of the TimeMachine state as a string |
| * and the number of lines in the string. |
| * |
| * The number of lines in the returned pair is used as an optimization |
| * for subsequent line limiting. |
| * |
| * \param lines the maximum number of lines in the string returned. |
| * \param key selects only that key. |
| * \param sinceNs the nanoseconds since Unix epoch to start dump (0 shows all) |
| * \param prefix the desired key prefix to match (nullptr shows all) |
| */ |
| std::pair<std::string, int32_t> dump( |
| int32_t lines = INT32_MAX, int64_t sinceNs = 0, const char *prefix = nullptr) const { |
| std::lock_guard lock(mLock); |
| std::stringstream ss; |
| int32_t ll = lines; |
| |
| for (auto it = prefix != nullptr ? mHistory.lower_bound(prefix) : mHistory.begin(); |
| it != mHistory.end(); |
| ++it) { |
| if (ll <= 0) break; |
| if (prefix != nullptr && !startsWith(it->first, prefix)) break; |
| std::lock_guard lock2(getLockForKey(it->first)); |
| auto [s, l] = it->second->dump(ll, sinceNs); |
| ss << s; |
| ll -= l; |
| } |
| return { ss.str(), lines - ll }; |
| } |
| |
| size_t getGarbageCollectionCount() const { |
| return mGarbageCollectionCount; |
| } |
| |
| private: |
| |
| // Obtains the lock for a KeyHistory. |
| std::mutex &getLockForKey(const std::string &key) const |
| RETURN_CAPABILITY(mPseudoKeyHistoryLock) { |
| return mKeyLocks[std::hash<std::string>{}(key) % std::size(mKeyLocks)]; |
| } |
| |
| // Finds a KeyHistory from a URL. Returns nullptr if not found. |
| std::shared_ptr<KeyHistory> getKeyHistoryFromUrl( |
| const std::string& url, std::string* key, std::string *prop) const { |
| std::lock_guard lock(mLock); |
| |
| auto it = mHistory.upper_bound(url); |
| if (it == mHistory.begin()) { |
| return nullptr; |
| } |
| --it; // go to the actual key, if it exists. |
| |
| const std::string& itKey = it->first; |
| if (strncmp(itKey.c_str(), url.c_str(), itKey.size())) { |
| return nullptr; |
| } |
| if (key) *key = itKey; |
| if (prop) *prop = url.substr(itKey.size() + 1); |
| return it->second; |
| } |
| |
| /** |
| * Garbage collects if the TimeMachine size exceeds the high water mark. |
| * |
| * This GC operation limits the number of keys stored (not the size of properties |
| * stored in each key). |
| * |
| * \param garbage a type-erased vector of elements to be destroyed |
| * outside of lock. Move large items to be destroyed here. |
| * |
| * \return true if garbage collection was done. |
| */ |
| bool gc(std::vector<std::any>& garbage) REQUIRES(mLock) { |
| // TODO: something better than this for garbage collection. |
| if (mHistory.size() < mKeyHighWaterMark) return false; |
| |
| // erase everything explicitly expired. |
| std::multimap<int64_t, std::string> accessList; |
| // use a stale vector with precise type to avoid type erasure overhead in garbage |
| std::vector<std::shared_ptr<KeyHistory>> stale; |
| |
| for (auto it = mHistory.begin(); it != mHistory.end();) { |
| const std::string& key = it->first; |
| std::shared_ptr<KeyHistory> &keyHist = it->second; |
| |
| std::lock_guard lock(getLockForKey(it->first)); |
| int64_t expireTime = keyHist->getValue("_expire", -1 /* default */); |
| if (expireTime != -1) { |
| stale.emplace_back(std::move(it->second)); |
| it = mHistory.erase(it); |
| } else { |
| accessList.emplace(keyHist->getLastModificationTime(), key); |
| ++it; |
| } |
| } |
| |
| if (mHistory.size() > mKeyLowWaterMark) { |
| const size_t toDelete = mHistory.size() - mKeyLowWaterMark; |
| auto it = accessList.begin(); |
| for (size_t i = 0; i < toDelete; ++i) { |
| auto it2 = mHistory.find(it->second); |
| stale.emplace_back(std::move(it2->second)); |
| mHistory.erase(it2); |
| ++it; |
| } |
| } |
| garbage.emplace_back(std::move(accessList)); |
| garbage.emplace_back(std::move(stale)); |
| |
| ALOGD("%s(%zu, %zu): key size:%zu", |
| __func__, mKeyLowWaterMark, mKeyHighWaterMark, |
| mHistory.size()); |
| |
| ++mGarbageCollectionCount; |
| return true; |
| } |
| |
| const size_t mKeyLowWaterMark = kKeyLowWaterMark; |
| const size_t mKeyHighWaterMark = kKeyHighWaterMark; |
| |
| std::atomic<size_t> mGarbageCollectionCount{}; |
| |
| /** |
| * Locking Strategy |
| * |
| * Each key in the History has a KeyHistory. To get a shared pointer to |
| * the KeyHistory requires a lookup of mHistory under mLock. Once the shared |
| * pointer to KeyHistory is obtained, the mLock for mHistory can be released. |
| * |
| * Once the shared pointer to the key's KeyHistory is obtained, the KeyHistory |
| * can be locked for read and modification through the method getLockForKey(). |
| * |
| * Instead of having a mutex per KeyHistory, we use a hash striped lock |
| * which assigns a mutex based on the hash of the key string. |
| * |
| * Once the last shared pointer reference to KeyHistory is released, it is |
| * destroyed. This is done through the garbage collection method. |
| * |
| * This two level locking allows multiple threads to access the TimeMachine |
| * in parallel. |
| */ |
| |
| mutable std::mutex mLock; // Lock for mHistory |
| History mHistory GUARDED_BY(mLock); |
| |
| // KEY_LOCKS is the number of mutexes for keys. |
| // It need not be a power of 2, but faster that way. |
| static inline constexpr size_t KEY_LOCKS = 256; |
| mutable std::mutex mKeyLocks[KEY_LOCKS]; // Hash-striped lock for KeyHistory based on key. |
| |
| // Used for thread-safety analysis, we create a fake mutex object to represent |
| // the hash stripe lock mechanism, which is then tracked by the compiler. |
| class CAPABILITY("mutex") PseudoLock {}; |
| static inline PseudoLock mPseudoKeyHistoryLock; |
| }; |
| |
| } // namespace android::mediametrics |