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 62 namespace base { 63 namespace 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. 70 template <class T> 71 auto EstimateMemoryUsage(const T& object) 72 -> decltype(object.EstimateMemoryUsage()); 73 74 // String 75 76 template <class C, class T, class A> 77 size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string); 78 79 // Arrays 80 81 template <class T, size_t N> 82 size_t EstimateMemoryUsage(const std::array<T, N>& array); 83 84 template <class T, size_t N> 85 size_t EstimateMemoryUsage(T (&array)[N]); 86 87 template <class T> 88 size_t EstimateMemoryUsage(const T* array, size_t array_length); 89 90 // std::unique_ptr 91 92 template <class T, class D> 93 size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr); 94 95 template <class T, class D> 96 size_t EstimateMemoryUsage(const std::unique_ptr<T[], D>& array, 97 size_t array_length); 98 99 // std::shared_ptr 100 101 template <class T> 102 size_t EstimateMemoryUsage(const std::shared_ptr<T>& ptr); 103 104 // Containers 105 106 template <class F, class S> 107 size_t EstimateMemoryUsage(const std::pair<F, S>& pair); 108 109 template <class T, class A> 110 size_t EstimateMemoryUsage(const std::vector<T, A>& vector); 111 112 template <class T, class A> 113 size_t EstimateMemoryUsage(const std::list<T, A>& list); 114 115 template <class T> 116 size_t EstimateMemoryUsage(const base::LinkedList<T>& list); 117 118 template <class T, class C, class A> 119 size_t EstimateMemoryUsage(const std::set<T, C, A>& set); 120 121 template <class T, class C, class A> 122 size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set); 123 124 template <class K, class V, class C, class A> 125 size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map); 126 127 template <class K, class V, class C, class A> 128 size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map); 129 130 template <class T, class H, class KE, class A> 131 size_t EstimateMemoryUsage(const std::unordered_set<T, H, KE, A>& set); 132 133 template <class T, class H, class KE, class A> 134 size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set); 135 136 template <class K, class V, class H, class KE, class A> 137 size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map); 138 139 template <class K, class V, class H, class KE, class A> 140 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map); 141 142 template <class T, class A> 143 size_t EstimateMemoryUsage(const std::deque<T, A>& deque); 144 145 template <class T, class C> 146 size_t EstimateMemoryUsage(const std::queue<T, C>& queue); 147 148 template <class T, class C> 149 size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue); 150 151 template <class T, class C> 152 size_t EstimateMemoryUsage(const std::stack<T, C>& stack); 153 154 // TODO(dskiba): 155 // std::forward_list 156 157 // Definitions 158 159 namespace internal { 160 161 // HasEMU<T>::value is true iff EstimateMemoryUsage(T) is available. 162 // (This is the default version, which is false.) 163 template <class T, class X = void> 164 struct 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. 169 template <class T> 170 struct 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. 189 template <class T, class X = void> 190 struct 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 201 template <class T> 202 struct EMUCaller<T, typename std::enable_if<HasEMU<T>::value>::type> { 203 static size_t Call(const T& value) { return EstimateMemoryUsage(value); } 204 }; 205 206 template <class T> 207 struct 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. 216 template <class A> 217 const 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. 228 template <class T> 229 size_t EstimateItemMemoryUsage(const T& value) { 230 return internal::EMUCaller<T>::Call(value); 231 } 232 233 template <class I> 234 size_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(). 243 template <class T> 244 auto 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 254 template <class C, class T, class A> 255 size_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). 271 extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::string&); 272 extern template BASE_EXPORT size_t EstimateMemoryUsage(const string16&); 273 274 // Arrays 275 276 template <class T, size_t N> 277 size_t EstimateMemoryUsage(const std::array<T, N>& array) { 278 return EstimateIterableMemoryUsage(array); 279 } 280 281 template <class T, size_t N> 282 size_t EstimateMemoryUsage(T (&array)[N]) { 283 return EstimateIterableMemoryUsage(array); 284 } 285 286 template <class T> 287 size_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 297 template <class T, class D> 298 size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr) { 299 return ptr ? (sizeof(T) + EstimateItemMemoryUsage(*ptr)) : 0; 300 } 301 302 template <class T, class D> 303 size_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 310 template <class T> 311 size_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 332 template <class F, class S> 333 size_t EstimateMemoryUsage(const std::pair<F, S>& pair) { 334 return EstimateItemMemoryUsage(pair.first) + 335 EstimateItemMemoryUsage(pair.second); 336 } 337 338 // std::vector 339 340 template <class T, class A> 341 size_t EstimateMemoryUsage(const std::vector<T, A>& vector) { 342 return sizeof(T) * vector.capacity() + EstimateIterableMemoryUsage(vector); 343 } 344 345 // std::list 346 347 template <class T, class A> 348 size_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 359 template <class T> 360 size_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 373 template <class V> 374 size_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 387 template <class T, class C, class A> 388 size_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 394 template <class T, class C, class A> 395 size_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 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 408 template <class K, class V, class C, class A> 409 size_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 417 namespace 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. 424 template <class V> 425 size_t HashMapBucketCountForTesting(size_t bucket_count) { 426 return bucket_count; 427 } 428 429 } // namespace internal 430 431 template <class V> 432 size_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 445 template <class K, class H, class KE, class A> 446 size_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 453 template <class K, class H, class KE, class A> 454 size_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 461 template <class K, class V, class H, class KE, class A> 462 size_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 469 template <class K, class V, class H, class KE, class A> 470 size_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 480 template <class T, class A> 481 size_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 531 template <class T, class C> 532 size_t EstimateMemoryUsage(const std::queue<T, C>& queue) { 533 return EstimateMemoryUsage(internal::GetUnderlyingContainer(queue)); 534 } 535 536 template <class T, class C> 537 size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue) { 538 return EstimateMemoryUsage(internal::GetUnderlyingContainer(queue)); 539 } 540 541 template <class T, class C> 542 size_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