memory_usage_estimator.h 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683
  1. // Copyright 2016 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
  5. #define BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
  6. #include <stdint.h>
  7. #include <array>
  8. #include <deque>
  9. #include <list>
  10. #include <map>
  11. #include <memory>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <string>
  16. #include <type_traits>
  17. #include <unordered_map>
  18. #include <unordered_set>
  19. #include <vector>
  20. #include "base/base_export.h"
  21. #include "base/containers/circular_deque.h"
  22. #include "base/containers/flat_map.h"
  23. #include "base/containers/flat_set.h"
  24. #include "base/containers/linked_list.h"
  25. #include "base/containers/lru_cache.h"
  26. #include "base/containers/queue.h"
  27. #include "base/memory/raw_ptr.h"
  28. #include "base/stl_util.h"
  29. #include "base/template_util.h"
  30. // Composable memory usage estimators.
  31. //
  32. // This file defines set of EstimateMemoryUsage(object) functions that return
  33. // approximate dynamically allocated memory usage of their argument.
  34. //
  35. // The ultimate goal is to make memory usage estimation for a class simply a
  36. // matter of aggregating EstimateMemoryUsage() results over all fields.
  37. //
  38. // That is achieved via composability: if EstimateMemoryUsage() is defined
  39. // for T then EstimateMemoryUsage() is also defined for any combination of
  40. // containers holding T (e.g. std::map<int, std::vector<T>>).
  41. //
  42. // There are two ways of defining EstimateMemoryUsage() for a type:
  43. //
  44. // 1. As a global function 'size_t EstimateMemoryUsage(T)' in
  45. // in base::trace_event namespace.
  46. //
  47. // 2. As 'size_t T::EstimateMemoryUsage() const' method. In this case
  48. // EstimateMemoryUsage(T) function in base::trace_event namespace is
  49. // provided automatically.
  50. //
  51. // Here is an example implementation:
  52. //
  53. // class MyClass {
  54. // ...
  55. // ...
  56. // size_t EstimateMemoryUsage() const {
  57. // return base::trace_event::EstimateMemoryUsage(set_) +
  58. // base::trace_event::EstimateMemoryUsage(name_) +
  59. // base::trace_event::EstimateMemoryUsage(foo_);
  60. // }
  61. // ...
  62. // private:
  63. // ...
  64. // std::set<int> set_;
  65. // std::string name_;
  66. // Foo foo_;
  67. // int id_;
  68. // bool success_;
  69. // }
  70. //
  71. // The approach is simple: first call EstimateMemoryUsage() on all members,
  72. // then recursively fix compilation errors that are caused by types not
  73. // implementing EstimateMemoryUsage().
  74. namespace base {
  75. namespace trace_event {
  76. // Declarations
  77. // If T declares 'EstimateMemoryUsage() const' member function, then
  78. // global function EstimateMemoryUsage(T) is available, and just calls
  79. // the member function.
  80. template <class T>
  81. auto EstimateMemoryUsage(const T& object)
  82. -> decltype(object.EstimateMemoryUsage());
  83. // String
  84. template <class C, class T, class A>
  85. size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string);
  86. // Arrays
  87. template <class T, size_t N>
  88. size_t EstimateMemoryUsage(const std::array<T, N>& array);
  89. template <class T, size_t N>
  90. size_t EstimateMemoryUsage(T (&array)[N]);
  91. template <class T>
  92. size_t EstimateMemoryUsage(const T* array, size_t array_length);
  93. // std::unique_ptr
  94. template <class T, class D>
  95. size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr);
  96. template <class T, class D>
  97. size_t EstimateMemoryUsage(const std::unique_ptr<T[], D>& array,
  98. size_t array_length);
  99. // std::shared_ptr
  100. template <class T>
  101. size_t EstimateMemoryUsage(const std::shared_ptr<T>& ptr);
  102. // Containers
  103. template <class F, class S>
  104. size_t EstimateMemoryUsage(const std::pair<F, S>& pair);
  105. template <class T, class A>
  106. size_t EstimateMemoryUsage(const std::vector<T, A>& vector);
  107. template <class T, class A>
  108. size_t EstimateMemoryUsage(const std::list<T, A>& list);
  109. template <class T>
  110. size_t EstimateMemoryUsage(const base::LinkedList<T>& list);
  111. template <class T, class C, class A>
  112. size_t EstimateMemoryUsage(const std::set<T, C, A>& set);
  113. template <class T, class C, class A>
  114. size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set);
  115. template <class K, class V, class C, class A>
  116. size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map);
  117. template <class K, class V, class C, class A>
  118. size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map);
  119. template <class T, class H, class KE, class A>
  120. size_t EstimateMemoryUsage(const std::unordered_set<T, H, KE, A>& set);
  121. template <class T, class H, class KE, class A>
  122. size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set);
  123. template <class K, class V, class H, class KE, class A>
  124. size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map);
  125. template <class K, class V, class H, class KE, class A>
  126. size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map);
  127. template <class T, class A>
  128. size_t EstimateMemoryUsage(const std::deque<T, A>& deque);
  129. template <class T, class C>
  130. size_t EstimateMemoryUsage(const std::queue<T, C>& queue);
  131. template <class T, class C>
  132. size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue);
  133. template <class T, class C>
  134. size_t EstimateMemoryUsage(const std::stack<T, C>& stack);
  135. template <class T>
  136. size_t EstimateMemoryUsage(const base::circular_deque<T>& deque);
  137. template <class T, class C>
  138. size_t EstimateMemoryUsage(const base::flat_set<T, C>& set);
  139. template <class K, class V, class C>
  140. size_t EstimateMemoryUsage(const base::flat_map<K, V, C>& map);
  141. template <class K, class V, class C>
  142. size_t EstimateMemoryUsage(const base::LRUCache<K, V, C>& lru);
  143. template <class K, class V, class C>
  144. size_t EstimateMemoryUsage(const base::HashingLRUCache<K, V, C>& lru);
  145. template <class V, class C>
  146. size_t EstimateMemoryUsage(const base::LRUCacheSet<V, C>& lru);
  147. template <class V, class C>
  148. size_t EstimateMemoryUsage(const base::HashingLRUCacheSet<V, C>& lru);
  149. // TODO(dskiba):
  150. // std::forward_list
  151. // Definitions
  152. namespace internal {
  153. // HasEMU<T>::value is true iff EstimateMemoryUsage(T) is available.
  154. // (This is the default version, which is false.)
  155. template <class T, class X = void>
  156. struct HasEMU : std::false_type {};
  157. // This HasEMU specialization is only picked up if there exists function
  158. // EstimateMemoryUsage(const T&) that returns size_t. Simpler ways to
  159. // achieve this don't work on MSVC.
  160. template <class T>
  161. struct HasEMU<
  162. T,
  163. typename std::enable_if<std::is_same<
  164. size_t,
  165. decltype(EstimateMemoryUsage(std::declval<const T&>()))>::value>::type>
  166. : std::true_type {};
  167. // EMUCaller<T> does three things:
  168. // 1. Defines Call() method that calls EstimateMemoryUsage(T) if it's
  169. // available.
  170. // 2. If EstimateMemoryUsage(T) is not available, but T has trivial dtor
  171. // (i.e. it's POD, integer, pointer, enum, etc.) then it defines Call()
  172. // method that returns 0. This is useful for containers, which allocate
  173. // memory regardless of T (also for cases like std::map<int, MyClass>).
  174. // 3. Finally, if EstimateMemoryUsage(T) is not available, then it triggers
  175. // a static_assert with a helpful message. That cuts numbers of errors
  176. // considerably - if you just call EstimateMemoryUsage(T) but it's not
  177. // available for T, then compiler will helpfully list *all* possible
  178. // variants of it, with an explanation for each.
  179. template <class T, class X = void>
  180. struct EMUCaller {
  181. // std::is_same<> below makes static_assert depend on T, in order to
  182. // prevent it from asserting regardless instantiation.
  183. static_assert(std::is_same<T, std::false_type>::value,
  184. "Neither global function 'size_t EstimateMemoryUsage(T)' "
  185. "nor member function 'size_t T::EstimateMemoryUsage() const' "
  186. "is defined for the type.");
  187. static size_t Call(const T&) { return 0; }
  188. };
  189. template <class T>
  190. struct EMUCaller<T, typename std::enable_if<HasEMU<T>::value>::type> {
  191. static size_t Call(const T& value) { return EstimateMemoryUsage(value); }
  192. };
  193. template <template <class...> class Container, class I, class = void>
  194. struct IsComplexIteratorForContainer : std::false_type {};
  195. template <template <class...> class Container, class I>
  196. struct IsComplexIteratorForContainer<
  197. Container,
  198. I,
  199. std::enable_if_t<!std::is_pointer<I>::value &&
  200. base::internal::is_iterator<I>::value>> {
  201. using value_type = typename std::iterator_traits<I>::value_type;
  202. using container_type = Container<value_type>;
  203. // We use enum instead of static constexpr bool, beause we don't have inline
  204. // variables until c++17.
  205. //
  206. // The downside is - value is not of type bool.
  207. enum : bool {
  208. value =
  209. std::is_same<typename container_type::iterator, I>::value ||
  210. std::is_same<typename container_type::const_iterator, I>::value ||
  211. std::is_same<typename container_type::reverse_iterator, I>::value ||
  212. std::is_same<typename container_type::const_reverse_iterator, I>::value,
  213. };
  214. };
  215. template <class I, template <class...> class... Containers>
  216. constexpr bool OneOfContainersComplexIterators() {
  217. // We are forced to create a temporary variable to workaround a compilation
  218. // error in msvs.
  219. const bool all_tests[] = {
  220. IsComplexIteratorForContainer<Containers, I>::value...};
  221. for (bool test : all_tests)
  222. if (test)
  223. return true;
  224. return false;
  225. }
  226. // std::array has an extra required template argument. We curry it.
  227. template <class T>
  228. using array_test_helper = std::array<T, 1>;
  229. template <class I>
  230. constexpr bool IsStandardContainerComplexIterator() {
  231. // TODO(dyaroshev): deal with maps iterators if there is a need.
  232. // It requires to parse pairs into keys and values.
  233. // TODO(dyaroshev): deal with unordered containers: they do not have reverse
  234. // iterators.
  235. return OneOfContainersComplexIterators<
  236. I, array_test_helper, std::vector, std::deque,
  237. /*std::forward_list,*/ std::list, std::set, std::multiset>();
  238. }
  239. // Work around MSVS bug. For some reason constexpr function doesn't work.
  240. // However variable template does.
  241. template <typename T>
  242. constexpr bool IsKnownNonAllocatingType_v =
  243. std::is_trivially_destructible<T>::value ||
  244. IsStandardContainerComplexIterator<T>();
  245. template <class T>
  246. struct EMUCaller<
  247. T,
  248. std::enable_if_t<!HasEMU<T>::value && IsKnownNonAllocatingType_v<T>>> {
  249. static size_t Call(const T& value) { return 0; }
  250. };
  251. } // namespace internal
  252. // Proxy that deducts T and calls EMUCaller<T>.
  253. // To be used by EstimateMemoryUsage() implementations for containers.
  254. template <class T>
  255. size_t EstimateItemMemoryUsage(const T& value) {
  256. return internal::EMUCaller<T>::Call(value);
  257. }
  258. template <class I>
  259. size_t EstimateIterableMemoryUsage(const I& iterable) {
  260. size_t memory_usage = 0;
  261. for (const auto& item : iterable) {
  262. memory_usage += EstimateItemMemoryUsage(item);
  263. }
  264. return memory_usage;
  265. }
  266. // Global EstimateMemoryUsage(T) that just calls T::EstimateMemoryUsage().
  267. template <class T>
  268. auto EstimateMemoryUsage(const T& object)
  269. -> decltype(object.EstimateMemoryUsage()) {
  270. static_assert(
  271. std::is_same<decltype(object.EstimateMemoryUsage()), size_t>::value,
  272. "'T::EstimateMemoryUsage() const' must return size_t.");
  273. return object.EstimateMemoryUsage();
  274. }
  275. // String
  276. template <class C, class T, class A>
  277. size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string) {
  278. using string_type = std::basic_string<C, T, A>;
  279. using value_type = typename string_type::value_type;
  280. // C++11 doesn't leave much room for implementors - std::string can
  281. // use short string optimization, but that's about it. We detect SSO
  282. // by checking that c_str() points inside |string|.
  283. const uint8_t* cstr = reinterpret_cast<const uint8_t*>(string.c_str());
  284. const uint8_t* inline_cstr = reinterpret_cast<const uint8_t*>(&string);
  285. if (cstr >= inline_cstr && cstr < inline_cstr + sizeof(string)) {
  286. // SSO string
  287. return 0;
  288. }
  289. return (string.capacity() + 1) * sizeof(value_type);
  290. }
  291. // Use explicit instantiations from the .cc file (reduces bloat).
  292. extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::string&);
  293. extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::u16string&);
  294. // Arrays
  295. template <class T, size_t N>
  296. size_t EstimateMemoryUsage(const std::array<T, N>& array) {
  297. return EstimateIterableMemoryUsage(array);
  298. }
  299. template <class T, size_t N>
  300. size_t EstimateMemoryUsage(T (&array)[N]) {
  301. return EstimateIterableMemoryUsage(array);
  302. }
  303. template <class T>
  304. size_t EstimateMemoryUsage(const T* array, size_t array_length) {
  305. size_t memory_usage = sizeof(T) * array_length;
  306. for (size_t i = 0; i != array_length; ++i) {
  307. memory_usage += EstimateItemMemoryUsage(array[i]);
  308. }
  309. return memory_usage;
  310. }
  311. // std::unique_ptr
  312. template <class T, class D>
  313. size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr) {
  314. return ptr ? (sizeof(T) + EstimateItemMemoryUsage(*ptr)) : 0;
  315. }
  316. template <class T, class D>
  317. size_t EstimateMemoryUsage(const std::unique_ptr<T[], D>& array,
  318. size_t array_length) {
  319. return EstimateMemoryUsage(array.get(), array_length);
  320. }
  321. // std::shared_ptr
  322. template <class T>
  323. size_t EstimateMemoryUsage(const std::shared_ptr<T>& ptr) {
  324. auto use_count = ptr.use_count();
  325. if (use_count == 0) {
  326. return 0;
  327. }
  328. // Model shared_ptr after libc++,
  329. // see __shared_ptr_pointer from include/memory
  330. struct SharedPointer {
  331. raw_ptr<void> vtbl;
  332. long shared_owners;
  333. long shared_weak_owners;
  334. raw_ptr<T> value;
  335. };
  336. // If object of size S shared N > S times we prefer to (potentially)
  337. // overestimate than to return 0.
  338. return sizeof(SharedPointer) +
  339. (EstimateItemMemoryUsage(*ptr) + (use_count - 1)) / use_count;
  340. }
  341. // std::pair
  342. template <class F, class S>
  343. size_t EstimateMemoryUsage(const std::pair<F, S>& pair) {
  344. return EstimateItemMemoryUsage(pair.first) +
  345. EstimateItemMemoryUsage(pair.second);
  346. }
  347. // std::vector
  348. template <class T, class A>
  349. size_t EstimateMemoryUsage(const std::vector<T, A>& vector) {
  350. return sizeof(T) * vector.capacity() + EstimateIterableMemoryUsage(vector);
  351. }
  352. // std::list
  353. template <class T, class A>
  354. size_t EstimateMemoryUsage(const std::list<T, A>& list) {
  355. using value_type = typename std::list<T, A>::value_type;
  356. struct Node {
  357. raw_ptr<Node> prev;
  358. raw_ptr<Node> next;
  359. value_type value;
  360. };
  361. return sizeof(Node) * list.size() +
  362. EstimateIterableMemoryUsage(list);
  363. }
  364. template <class T>
  365. size_t EstimateMemoryUsage(const base::LinkedList<T>& list) {
  366. size_t memory_usage = 0u;
  367. for (base::LinkNode<T>* node = list.head(); node != list.end();
  368. node = node->next()) {
  369. // Since we increment by calling node = node->next() we know that node
  370. // isn't nullptr.
  371. memory_usage += EstimateMemoryUsage(*node->value()) + sizeof(T);
  372. }
  373. return memory_usage;
  374. }
  375. // Tree containers
  376. template <class V>
  377. size_t EstimateTreeMemoryUsage(size_t size) {
  378. // Tree containers are modeled after libc++
  379. // (__tree_node from include/__tree)
  380. struct Node {
  381. raw_ptr<Node> left;
  382. raw_ptr<Node> right;
  383. raw_ptr<Node> parent;
  384. bool is_black;
  385. V value;
  386. };
  387. return sizeof(Node) * size;
  388. }
  389. template <class T, class C, class A>
  390. size_t EstimateMemoryUsage(const std::set<T, C, A>& set) {
  391. using value_type = typename std::set<T, C, A>::value_type;
  392. return EstimateTreeMemoryUsage<value_type>(set.size()) +
  393. EstimateIterableMemoryUsage(set);
  394. }
  395. template <class T, class C, class A>
  396. size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set) {
  397. using value_type = typename std::multiset<T, C, A>::value_type;
  398. return EstimateTreeMemoryUsage<value_type>(set.size()) +
  399. EstimateIterableMemoryUsage(set);
  400. }
  401. template <class K, class V, class C, class A>
  402. size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map) {
  403. using value_type = typename std::map<K, V, C, A>::value_type;
  404. return EstimateTreeMemoryUsage<value_type>(map.size()) +
  405. EstimateIterableMemoryUsage(map);
  406. }
  407. template <class K, class V, class C, class A>
  408. size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map) {
  409. using value_type = typename std::multimap<K, V, C, A>::value_type;
  410. return EstimateTreeMemoryUsage<value_type>(map.size()) +
  411. EstimateIterableMemoryUsage(map);
  412. }
  413. // HashMap containers
  414. namespace internal {
  415. // While hashtable containers model doesn't depend on STL implementation, one
  416. // detail still crept in: bucket_count. It's used in size estimation, but its
  417. // value after inserting N items is not predictable.
  418. // This function is specialized by unittests to return constant value, thus
  419. // excluding bucket_count from testing.
  420. template <class V>
  421. size_t HashMapBucketCountForTesting(size_t bucket_count) {
  422. return bucket_count;
  423. }
  424. template <class LruCacheType>
  425. size_t DoEstimateMemoryUsageForLruCache(const LruCacheType& lru_cache) {
  426. return EstimateMemoryUsage(lru_cache.ordering_) +
  427. EstimateMemoryUsage(lru_cache.index_);
  428. }
  429. } // namespace internal
  430. template <class V>
  431. size_t EstimateHashMapMemoryUsage(size_t bucket_count, size_t size) {
  432. // Hashtable containers are modeled after libc++
  433. // (__hash_node from include/__hash_table)
  434. struct Node {
  435. raw_ptr<void> next;
  436. size_t hash;
  437. V value;
  438. };
  439. using Bucket = void*;
  440. bucket_count = internal::HashMapBucketCountForTesting<V>(bucket_count);
  441. return sizeof(Bucket) * bucket_count + sizeof(Node) * size;
  442. }
  443. template <class K, class H, class KE, class A>
  444. size_t EstimateMemoryUsage(const std::unordered_set<K, H, KE, A>& set) {
  445. using value_type = typename std::unordered_set<K, H, KE, A>::value_type;
  446. return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(),
  447. set.size()) +
  448. EstimateIterableMemoryUsage(set);
  449. }
  450. template <class K, class H, class KE, class A>
  451. size_t EstimateMemoryUsage(const std::unordered_multiset<K, H, KE, A>& set) {
  452. using value_type = typename std::unordered_multiset<K, H, KE, A>::value_type;
  453. return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(),
  454. set.size()) +
  455. EstimateIterableMemoryUsage(set);
  456. }
  457. template <class K, class V, class H, class KE, class A>
  458. size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map) {
  459. using value_type = typename std::unordered_map<K, V, H, KE, A>::value_type;
  460. return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(),
  461. map.size()) +
  462. EstimateIterableMemoryUsage(map);
  463. }
  464. template <class K, class V, class H, class KE, class A>
  465. size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) {
  466. using value_type =
  467. typename std::unordered_multimap<K, V, H, KE, A>::value_type;
  468. return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(),
  469. map.size()) +
  470. EstimateIterableMemoryUsage(map);
  471. }
  472. // std::deque
  473. template <class T, class A>
  474. size_t EstimateMemoryUsage(const std::deque<T, A>& deque) {
  475. // Since std::deque implementations are wildly different
  476. // (see crbug.com/674287), we can't have one "good enough"
  477. // way to estimate.
  478. // kBlockSize - minimum size of a block, in bytes
  479. // kMinBlockLength - number of elements in a block
  480. // if sizeof(T) > kBlockSize
  481. #if defined(_LIBCPP_VERSION)
  482. size_t kBlockSize = 4096;
  483. size_t kMinBlockLength = 16;
  484. #elif defined(__GLIBCXX__)
  485. size_t kBlockSize = 512;
  486. size_t kMinBlockLength = 1;
  487. #elif defined(_MSC_VER)
  488. size_t kBlockSize = 16;
  489. size_t kMinBlockLength = 1;
  490. #else
  491. size_t kBlockSize = 0;
  492. size_t kMinBlockLength = 1;
  493. #endif
  494. size_t block_length =
  495. (sizeof(T) > kBlockSize) ? kMinBlockLength : kBlockSize / sizeof(T);
  496. size_t blocks = (deque.size() + block_length - 1) / block_length;
  497. #if defined(__GLIBCXX__)
  498. // libstdc++: deque always has at least one block
  499. if (!blocks)
  500. blocks = 1;
  501. #endif
  502. #if defined(_LIBCPP_VERSION)
  503. // libc++: deque keeps at most two blocks when it shrinks,
  504. // so even if the size is zero, deque might be holding up
  505. // to 4096 * 2 bytes. One way to know whether deque has
  506. // ever allocated (and hence has 1 or 2 blocks) is to check
  507. // iterator's pointer. Non-zero value means that deque has
  508. // at least one block.
  509. if (!blocks && deque.begin().operator->())
  510. blocks = 1;
  511. #endif
  512. return (blocks * block_length * sizeof(T)) +
  513. EstimateIterableMemoryUsage(deque);
  514. }
  515. // Container adapters
  516. template <class T, class C>
  517. size_t EstimateMemoryUsage(const std::queue<T, C>& queue) {
  518. return EstimateMemoryUsage(GetUnderlyingContainer(queue));
  519. }
  520. template <class T, class C>
  521. size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue) {
  522. return EstimateMemoryUsage(GetUnderlyingContainer(queue));
  523. }
  524. template <class T, class C>
  525. size_t EstimateMemoryUsage(const std::stack<T, C>& stack) {
  526. return EstimateMemoryUsage(GetUnderlyingContainer(stack));
  527. }
  528. // base::circular_deque
  529. template <class T>
  530. size_t EstimateMemoryUsage(const base::circular_deque<T>& deque) {
  531. return sizeof(T) * deque.capacity() + EstimateIterableMemoryUsage(deque);
  532. }
  533. // Flat containers
  534. template <class T, class C>
  535. size_t EstimateMemoryUsage(const base::flat_set<T, C>& set) {
  536. using value_type = typename base::flat_set<T, C>::value_type;
  537. return sizeof(value_type) * set.capacity() + EstimateIterableMemoryUsage(set);
  538. }
  539. template <class K, class V, class C>
  540. size_t EstimateMemoryUsage(const base::flat_map<K, V, C>& map) {
  541. using value_type = typename base::flat_map<K, V, C>::value_type;
  542. return sizeof(value_type) * map.capacity() + EstimateIterableMemoryUsage(map);
  543. }
  544. template <class K, class V, class C>
  545. size_t EstimateMemoryUsage(const LRUCache<K, V, C>& lru_cache) {
  546. return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
  547. }
  548. template <class K, class V, class C>
  549. size_t EstimateMemoryUsage(const HashingLRUCache<K, V, C>& lru_cache) {
  550. return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
  551. }
  552. template <class V, class C>
  553. size_t EstimateMemoryUsage(const LRUCacheSet<V, C>& lru_cache) {
  554. return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
  555. }
  556. template <class V, class C>
  557. size_t EstimateMemoryUsage(const HashingLRUCacheSet<V, C>& lru_cache) {
  558. return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
  559. }
  560. } // namespace trace_event
  561. } // namespace base
  562. #endif // BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_