chromium/base/trace_event/memory_usage_estimator.h

// Copyright 2016 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
#pragma allow_unsafe_buffers
#endif

#ifndef BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
#define BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_

#include <stdint.h>

#include <array>
#include <concepts>
#include <deque>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "base/base_export.h"
#include "base/containers/circular_deque.h"
#include "base/containers/flat_map.h"
#include "base/containers/flat_set.h"
#include "base/containers/heap_array.h"
#include "base/containers/linked_list.h"
#include "base/containers/lru_cache.h"
#include "base/containers/queue.h"
#include "base/containers/span.h"
#include "base/memory/raw_ptr.h"
#include "base/stl_util.h"
#include "base/types/always_false.h"

// Composable memory usage estimators.
//
// This file defines set of EstimateMemoryUsage(object) functions that return
// approximate dynamically allocated memory usage of their argument.
//
// The ultimate goal is to make memory usage estimation for a class simply a
// matter of aggregating EstimateMemoryUsage() results over all fields.
//
// That is achieved via composability: if EstimateMemoryUsage() is defined
// for T then EstimateMemoryUsage() is also defined for any combination of
// containers holding T (e.g. std::map<int, std::vector<T>>).
//
// There are two ways of defining EstimateMemoryUsage() for a type:
//
// 1. As a global function 'size_t EstimateMemoryUsage(T)' in
//    in base::trace_event namespace.
//
// 2. As 'size_t T::EstimateMemoryUsage() const' method. In this case
//    EstimateMemoryUsage(T) function in base::trace_event namespace is
//    provided automatically.
//
// Here is an example implementation:
//
// class MyClass {
//   ...
//   ...
//   size_t EstimateMemoryUsage() const {
//     return base::trace_event::EstimateMemoryUsage(set_) +
//            base::trace_event::EstimateMemoryUsage(name_) +
//            base::trace_event::EstimateMemoryUsage(foo_);
//   }
//   ...
//  private:
//   ...
//   std::set<int> set_;
//   std::string name_;
//   Foo foo_;
//   int id_;
//   bool success_;
// }
//
// The approach is simple: first call EstimateMemoryUsage() on all members,
// then recursively fix compilation errors that are caused by types not
// implementing EstimateMemoryUsage().
//
// Note that in the above example, the memory estimates for `id_` and `success_` are
// intentionally omitted. This is because these members do not allocate any _dynamic_ memory.
// If, for example, `MyClass` is declared as a heap-allocated `unique_ptr` member in some parent
// class, then `EstimateMemoryUsage` on the `unique_ptr` will automatically take into account
// `sizeof(MyClass)`.

namespace base {
namespace trace_event {

// Declarations

// If T declares 'EstimateMemoryUsage() const' member function, then
// global function EstimateMemoryUsage(T) is available, and just calls
// the member function.
template <class T>
auto EstimateMemoryUsage(const T& object)
    -> decltype(object …);

// String

template <class C, class T, class A>
size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string);

// Arrays

template <class T, size_t N>
size_t EstimateMemoryUsage(const std::array<T, N>& array);

template <class T, size_t N>
size_t EstimateMemoryUsage(T (&array)[N]);

template <class T>
size_t EstimateMemoryUsage(const base::HeapArray<T>& array);

template <class T>
size_t EstimateMemoryUsage(base::span<T> array);

// std::unique_ptr

template <class T, class D>
size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr);

// std::shared_ptr

template <class T>
size_t EstimateMemoryUsage(const std::shared_ptr<T>& ptr);

// Containers

template <class F, class S>
size_t EstimateMemoryUsage(const std::pair<F, S>& pair);

template <class T, class A>
size_t EstimateMemoryUsage(const std::vector<T, A>& vector);

template <class T, class A>
size_t EstimateMemoryUsage(const std::list<T, A>& list);

template <class T>
size_t EstimateMemoryUsage(const base::LinkedList<T>& list);

template <class T, class C, class A>
size_t EstimateMemoryUsage(const std::set<T, C, A>& set);

template <class T, class C, class A>
size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set);

template <class K, class V, class C, class A>
size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map);

template <class K, class V, class C, class A>
size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map);

template <class T, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_set<T, H, KE, A>& set);

template <class T, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set);

template <class K, class V, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map);

template <class K, class V, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map);

template <class T, class A>
size_t EstimateMemoryUsage(const std::deque<T, A>& deque);

template <class T, class C>
size_t EstimateMemoryUsage(const std::queue<T, C>& queue);

template <class T, class C>
size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue);

template <class T, class C>
size_t EstimateMemoryUsage(const std::stack<T, C>& stack);

template <class T>
size_t EstimateMemoryUsage(const base::circular_deque<T>& deque);

template <class T, class C>
size_t EstimateMemoryUsage(const base::flat_set<T, C>& set);

template <class K, class V, class C>
size_t EstimateMemoryUsage(const base::flat_map<K, V, C>& map);

template <class K, class V, class C>
size_t EstimateMemoryUsage(const base::LRUCache<K, V, C>& lru);

template <class K, class V, class C>
size_t EstimateMemoryUsage(const base::HashingLRUCache<K, V, C>& lru);

template <class V, class C>
size_t EstimateMemoryUsage(const base::LRUCacheSet<V, C>& lru);

template <class V, class C>
size_t EstimateMemoryUsage(const base::HashingLRUCacheSet<V, C>& lru);

// TODO(dskiba):
//   std::forward_list

// Definitions

namespace internal {

// HasEMU<T> is true iff EstimateMemoryUsage(const T&) is available.
HasEMU;

IteratorValueType;

IsIteratorOfInstantiatedContainer;

IsIteratorOfContainer;

// std::array has an extra required template argument.
array_test_helper;

// TODO(dyaroshev): deal with maps iterators if there is a need.
// It requires to parse pairs into keys and values.
// TODO(dyaroshev): deal with unordered containers: they do not have reverse
// iterators.
IsIteratorOfStandardContainer;

IsKnownNonAllocatingType;

}  // namespace internal

// Estimates T's memory usage as follows:
// 1. Calls `EstimateMemoryUsage(T)` if it is available.
// 2. If `EstimateMemoryUsage(T)` is not available, but T has trivial dtor
//    (i.e. it's POD, integer, pointer, enum, etc.) then it returns 0. This is
//    useful for containers, which allocate memory regardless of T (also for
//    cases like std::map<int, MyClass>).
// 3. Otherwise, it triggers a `static_assert` with a helpful message.
//
// To be used by `EstimateMemoryUsage()` implementations for containers.
template <class T>
size_t EstimateItemMemoryUsage(const T& value) { … }

template <class I>
size_t EstimateIterableMemoryUsage(const I& iterable) { … }

// Global EstimateMemoryUsage(T) that just calls T::EstimateMemoryUsage().
template <class T>
auto EstimateMemoryUsage(const T& object)
    -> decltype(object.EstimateMemoryUsage()) { … }

// String

template <class C, class T, class A>
size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string) { … }

// Use explicit instantiations from the .cc file (reduces bloat).
extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::string&);
extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::u16string&);

// Arrays

template <class T, size_t N>
size_t EstimateMemoryUsage(const std::array<T, N>& array) { … }

template <class T, size_t N>
size_t EstimateMemoryUsage(T (&array)[N]) { … }

template <class T>
size_t EstimateMemoryUsage(const base::HeapArray<T>& array) { … }

template <class T>
size_t EstimateMemoryUsage(base::span<T> array) { … }

// std::unique_ptr

template <class T, class D>
size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr) { … }

// std::shared_ptr

template <class T>
size_t EstimateMemoryUsage(const std::shared_ptr<T>& ptr) { … }

// std::pair

template <class F, class S>
size_t EstimateMemoryUsage(const std::pair<F, S>& pair) { … }

// std::vector

template <class T, class A>
size_t EstimateMemoryUsage(const std::vector<T, A>& vector) { … }

// std::list

template <class T, class A>
size_t EstimateMemoryUsage(const std::list<T, A>& list) { … }

template <class T>
size_t EstimateMemoryUsage(const base::LinkedList<T>& list) { … }

// Tree containers

template <class V>
size_t EstimateTreeMemoryUsage(size_t size) { … }

template <class T, class C, class A>
size_t EstimateMemoryUsage(const std::set<T, C, A>& set) { … }

template <class T, class C, class A>
size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set) { … }

template <class K, class V, class C, class A>
size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map) { … }

template <class K, class V, class C, class A>
size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map) { … }

// HashMap containers

namespace internal {

// While hashtable containers model doesn't depend on STL implementation, one
// detail still crept in: bucket_count. It's used in size estimation, but its
// value after inserting N items is not predictable.
// This function is specialized by unittests to return constant value, thus
// excluding bucket_count from testing.
template <class V>
size_t HashMapBucketCountForTesting(size_t bucket_count) { … }

template <class LruCacheType>
size_t DoEstimateMemoryUsageForLruCache(const LruCacheType& lru_cache) { … }

}  // namespace internal

template <class V>
size_t EstimateHashMapMemoryUsage(size_t bucket_count, size_t size) { … }

template <class K, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_set<K, H, KE, A>& set) { … }

template <class K, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_multiset<K, H, KE, A>& set) { … }

template <class K, class V, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map) { … }

template <class K, class V, class H, class KE, class A>
size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) { … }

// std::deque

template <class T, class A>
size_t EstimateMemoryUsage(const std::deque<T, A>& deque) { … }

// Container adapters

template <class T, class C>
size_t EstimateMemoryUsage(const std::queue<T, C>& queue) { … }

template <class T, class C>
size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue) { … }

template <class T, class C>
size_t EstimateMemoryUsage(const std::stack<T, C>& stack) { … }

// base::circular_deque

template <class T>
size_t EstimateMemoryUsage(const base::circular_deque<T>& deque) { … }

// Flat containers

template <class T, class C>
size_t EstimateMemoryUsage(const base::flat_set<T, C>& set) { … }

template <class K, class V, class C>
size_t EstimateMemoryUsage(const base::flat_map<K, V, C>& map) { … }

template <class K, class V, class C>
size_t EstimateMemoryUsage(const LRUCache<K, V, C>& lru_cache) { … }

template <class K, class V, class C>
size_t EstimateMemoryUsage(const HashingLRUCache<K, V, C>& lru_cache) { … }

template <class V, class C>
size_t EstimateMemoryUsage(const LRUCacheSet<V, C>& lru_cache) { … }

template <class V, class C>
size_t EstimateMemoryUsage(const HashingLRUCacheSet<V, C>& lru_cache) { … }

}  // namespace trace_event
}  // namespace base

#endif  // BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_