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