blob: ce579b310f0f2f782d24f0d9a0346bb47a4c3352 [file] [log] [blame]
/*
* 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 ? "" : "~") << &timestring.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