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