OLD | NEW |
(Empty) | |
| 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_ESTIMATE_MEMORY_USAGE_H_ |
| 6 #define BASE_TRACE_EVENT_ESTIMATE_MEMORY_USAGE_H_ |
| 7 |
| 8 #include <array> |
| 9 #include <list> |
| 10 #include <map> |
| 11 #include <memory> |
| 12 #include <set> |
| 13 #include <string> |
| 14 #include <type_traits> |
| 15 #include <unordered_map> |
| 16 #include <unordered_set> |
| 17 #include <vector> |
| 18 |
| 19 #include "base/template_util.h" |
| 20 |
| 21 // Composable memory usage estimators. |
| 22 // |
| 23 // This file defines set of EstimateMemoryUsage(object) functions that return |
| 24 // approximate memory usage of their argument. |
| 25 // |
| 26 // The ultimate goal is to make memory usage estimation for a class simply a |
| 27 // matter of aggregating EstimateMemoryUsage() results over all fields. |
| 28 // |
| 29 // That is achieved via composability: if EstimateMemoryUsage() is defined |
| 30 // for T then EstimateMemoryUsage() is also defined for any combination of |
| 31 // containers holding T (e.g. std::map<int, std::vector<T>>). |
| 32 // |
| 33 // There are two ways of defining EstimateMemoryUsage() for a type: |
| 34 // |
| 35 // 1. As a global function 'size_t EstimateMemoryUsage(T)' in type's namespace |
| 36 // (or as a last resort, in base::trace_event namespace). |
| 37 // |
| 38 // 2. As 'size_t T::EstimateMemoryUsage() const' method. In this case global |
| 39 // EstimateMemoryUsage(T) function in base::trace_event namespace is |
| 40 // provided automatically. |
| 41 // |
| 42 // Here is an example implementation: |
| 43 // |
| 44 // size_t foo::bar::MyClass::EstimateMemoryUsage() const { |
| 45 // using base::trace_event::EstimateMemoryUsage; |
| 46 // return EstimateMemoryUsage(name_) + |
| 47 // EstimateMemoryUsage(id_) + |
| 48 // EstimateMemoryUsage(items_); |
| 49 // } |
| 50 // |
| 51 // Two things to note: |
| 52 // |
| 53 // 1. It starts with 'using' declaration. This makes everything defined in |
| 54 // this file (i.e. all EstimateMemoryUsage variants) available for compiler |
| 55 // to choose from. |
| 56 // |
| 57 // 2. It just calls EstimateMemoryUsage() on all (suitable) members. |
| 58 // The pattern is simple: first call EstimateMemoryUsage() on all members, |
| 59 // then fix compilation errors that are caused by types not implementing |
| 60 // 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> |
| 93 size_t EstimateMemoryUsage(const std::unique_ptr<T>& ptr); |
| 94 |
| 95 template <class T> |
| 96 size_t EstimateMemoryUsage(const std::unique_ptr<T[]>& array, |
| 97 size_t array_length); |
| 98 |
| 99 // Containers |
| 100 |
| 101 template <class F, class S> |
| 102 size_t EstimateMemoryUsage(const std::pair<F, S>& pair); |
| 103 |
| 104 template <class T, class A> |
| 105 size_t EstimateMemoryUsage(const std::vector<T, A>& vector); |
| 106 |
| 107 template <class T, class A> |
| 108 size_t EstimateMemoryUsage(const std::list<T, A>& list); |
| 109 |
| 110 template <class T, class C, class A> |
| 111 size_t EstimateMemoryUsage(const std::set<T, C, A>& set); |
| 112 |
| 113 template <class T, class C, class A> |
| 114 size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set); |
| 115 |
| 116 template <class K, class V, class C, class A> |
| 117 size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map); |
| 118 |
| 119 template <class K, class V, class C, class A> |
| 120 size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map); |
| 121 |
| 122 template <class T, class H, class KE, class A> |
| 123 size_t EstimateMemoryUsage(const std::unordered_set<T, H, KE, A>& set); |
| 124 |
| 125 template <class T, class H, class KE, class A> |
| 126 size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set); |
| 127 |
| 128 template <class K, class V, class H, class KE, class A> |
| 129 size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map); |
| 130 |
| 131 template <class K, class V, class H, class KE, class A> |
| 132 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map); |
| 133 |
| 134 // TODO(dskiba): |
| 135 // std::forward_list |
| 136 // std::deque |
| 137 // std::queue |
| 138 // std::stack |
| 139 // std::queue |
| 140 // std::priority_queue |
| 141 |
| 142 // Definitions |
| 143 |
| 144 namespace internal { |
| 145 |
| 146 // HasEMU<T>::value is true iff EstimateMemoryUsage(T) is available. |
| 147 // (This is the default version, which is false.) |
| 148 template <class T, class X = void> |
| 149 struct HasEMU : std::false_type {}; |
| 150 |
| 151 // This HasEMU specialization is only picked up if there exists function |
| 152 // EstimateMemoryUsage(const T&) that returns size_t. Simpler ways to |
| 153 // achieve this don't work on MSVC. |
| 154 template <class T> |
| 155 struct HasEMU< |
| 156 T, |
| 157 typename std::enable_if<std::is_same< |
| 158 size_t, |
| 159 decltype(EstimateMemoryUsage(std::declval<const T&>()))>::value>::type> |
| 160 : std::true_type {}; |
| 161 |
| 162 // EMUCaller<T> does three things: |
| 163 // 1. Defines Call() method that calls EstimateMemoryUsage(T) if it's |
| 164 // available. |
| 165 // 2. If EstimateMemoryUsage(T) is not available, but T has trivial dtor |
| 166 // (i.e. it's POD, integer, pointer, enum, etc.) then it defines Call() |
| 167 // method that returns 0. This is useful for containers, which allocate |
| 168 // memory regardless of T (also for cases like std::map<int, MyClass>). |
| 169 // 3. Finally, if EstimateMemoryUsage(T) is not available, then it triggers |
| 170 // a static_assert with a helpful message. That cuts numbers of errors |
| 171 // considerably - if you just call EstimateMemoryUsage(T) but it's not |
| 172 // available for T, then compiler will helpfully list *all* possible |
| 173 // variants of it, with an explanation for each. |
| 174 template <class T, class X = void> |
| 175 struct EMUCaller { |
| 176 // std::is_same<> below is only to make static_assert depend on T |
| 177 // to force compilers to include type of T in the error message. |
| 178 static_assert(std::is_same<T, X>::value, |
| 179 "Neither global function 'size_t EstimateMemoryUsage(T)' " |
| 180 "nor member function 'size_t T::EstimateMemoryUsage() const' " |
| 181 "is defined for the type."); |
| 182 |
| 183 static size_t Call(const T&) { return 0; } |
| 184 }; |
| 185 |
| 186 template <class T> |
| 187 struct EMUCaller<T, typename std::enable_if<HasEMU<T>::value>::type> { |
| 188 static size_t Call(const T& value) { return EstimateMemoryUsage(value); } |
| 189 }; |
| 190 |
| 191 template <class T> |
| 192 struct EMUCaller< |
| 193 T, |
| 194 typename std::enable_if<!HasEMU<T>::value && |
| 195 is_trivially_destructible<T>::value>::type> { |
| 196 static size_t Call(const T& value) { return 0; } |
| 197 }; |
| 198 |
| 199 } // namespace internal |
| 200 |
| 201 // Proxy that deducts T and calls EMUCaller<T>. |
| 202 // To be used by EstimateMemoryUsage() implementations for containers. |
| 203 template <class T> |
| 204 size_t EstimateItemMemoryUsage(const T& value) { |
| 205 return internal::EMUCaller<T>::Call(value); |
| 206 } |
| 207 |
| 208 template <class I> |
| 209 size_t EstimateIterableMemoryUsage(const I& iterable) { |
| 210 size_t memory_usage = 0; |
| 211 for (const auto& item : iterable) { |
| 212 memory_usage += EstimateItemMemoryUsage(item); |
| 213 } |
| 214 return memory_usage; |
| 215 } |
| 216 |
| 217 // Global EstimateMemoryUsage(T) that just calls T::EstimateMemoryUsage(). |
| 218 template <class T> |
| 219 auto EstimateMemoryUsage(const T& object) |
| 220 -> decltype(object.EstimateMemoryUsage()) { |
| 221 static_assert( |
| 222 std::is_same<decltype(object.EstimateMemoryUsage()), size_t>::value, |
| 223 "'T::EstimateMemoryUsage() const' must return size_t."); |
| 224 return object.EstimateMemoryUsage(); |
| 225 } |
| 226 |
| 227 // String |
| 228 |
| 229 template <class C, class T, class A> |
| 230 size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string) { |
| 231 using string_type = std::basic_string<C, T, A>; |
| 232 using value_type = typename string_type::value_type; |
| 233 #if defined(__GLIBCXX__) && _GLIBCXX_USE_CXX11_ABI == 0 |
| 234 // libstdc++ with COW std::string - each string allocates a header |
| 235 // (see std::basic_string::_Rep). We don't take into account number |
| 236 // of references, but we do handle 'empty string' case. |
| 237 struct Header { |
| 238 typename string_type::size_type length; |
| 239 typename string_type::size_type capacity; |
| 240 int refcount; |
| 241 }; |
| 242 // There is one shared empty string, which we estimate to 0. |
| 243 static const value_type* empty_cstr = nullptr; |
| 244 if (!empty_cstr) { |
| 245 empty_cstr = string_type().c_str(); |
| 246 } |
| 247 return (string.c_str() == empty_cstr) |
| 248 ? 0 |
| 249 : sizeof(Header) + (string.capacity() + 1) * sizeof(value_type); |
| 250 #else |
| 251 // C++11 doesn't leave much room for implementors - std::string can |
| 252 // use short string optimization, but that's about it. We detect SSO |
| 253 // by checking that c_str() points inside |string|. |
| 254 const char* cstr = reinterpret_cast<const char*>(string.c_str()); |
| 255 const char* inline_cstr = reinterpret_cast<const char*>(&string); |
| 256 if (cstr >= inline_cstr && cstr < inline_cstr + sizeof(string)) { |
| 257 // SSO string |
| 258 return 0; |
| 259 } |
| 260 return (string.capacity() + 1) * sizeof(value_type); |
| 261 #endif |
| 262 } |
| 263 |
| 264 // Arrays |
| 265 |
| 266 template <class T, size_t N> |
| 267 size_t EstimateMemoryUsage(const std::array<T, N>& array) { |
| 268 return EstimateIterableMemoryUsage(array); |
| 269 } |
| 270 |
| 271 template <class T, size_t N> |
| 272 size_t EstimateMemoryUsage(T (&array)[N]) { |
| 273 return EstimateIterableMemoryUsage(array); |
| 274 } |
| 275 |
| 276 template <class T> |
| 277 size_t EstimateMemoryUsage(const T* array, size_t array_length) { |
| 278 size_t memory_usage = sizeof(T) * array_length; |
| 279 for (size_t i = 0; i != array_length; ++i) { |
| 280 memory_usage += EstimateItemMemoryUsage(array[i]); |
| 281 } |
| 282 return memory_usage; |
| 283 } |
| 284 |
| 285 // std::unique_ptr |
| 286 |
| 287 template <class T> |
| 288 size_t EstimateMemoryUsage(const std::unique_ptr<T>& ptr) { |
| 289 return ptr ? (sizeof(T) + EstimateItemMemoryUsage(*ptr)) : 0; |
| 290 } |
| 291 |
| 292 template <class T> |
| 293 size_t EstimateMemoryUsage(const std::unique_ptr<T[]>& array, |
| 294 size_t array_length) { |
| 295 return EstimateMemoryUsage(array.get(), array_length); |
| 296 } |
| 297 |
| 298 // std::pair |
| 299 |
| 300 template <class F, class S> |
| 301 size_t EstimateMemoryUsage(const std::pair<F, S>& pair) { |
| 302 return EstimateItemMemoryUsage(pair.first) + |
| 303 EstimateItemMemoryUsage(pair.second); |
| 304 } |
| 305 |
| 306 // std::vector |
| 307 |
| 308 template <class T, class A> |
| 309 size_t EstimateMemoryUsage(const std::vector<T, A>& vector) { |
| 310 return sizeof(T) * vector.capacity() + EstimateIterableMemoryUsage(vector); |
| 311 } |
| 312 |
| 313 // std::list |
| 314 |
| 315 template <class T, class A> |
| 316 size_t EstimateMemoryUsage(const std::list<T, A>& list) { |
| 317 using value_type = typename std::list<T, A>::value_type; |
| 318 struct Node { |
| 319 Node* prev; |
| 320 Node* next; |
| 321 value_type value; |
| 322 }; |
| 323 return sizeof(Node) * list.size() + |
| 324 #if defined(_MSC_VER) |
| 325 // MSVC: std::list allocates root node from the heap |
| 326 sizeof(Node) + |
| 327 #endif |
| 328 EstimateIterableMemoryUsage(list); |
| 329 } |
| 330 |
| 331 // Tree containers |
| 332 |
| 333 template <class V> |
| 334 size_t EstimateTreeMemoryUsage(size_t size) { |
| 335 #if defined(_MSC_VER) |
| 336 // MSVC: _Tree_node from include/xtree |
| 337 struct Node { |
| 338 Node* left; |
| 339 Node* parent; |
| 340 Node* right; |
| 341 char color; |
| 342 char isnil; |
| 343 V value; |
| 344 }; |
| 345 // _Tree (from include/xtree) allocates root node from the heap |
| 346 return sizeof(Node) * (size + 1); |
| 347 #elif defined(__GLIBCXX__) |
| 348 // libstdc++: _Rb_tree_node from include/bits/stl_tree.h |
| 349 struct Node { |
| 350 bool color; |
| 351 Node* parent; |
| 352 Node* left; |
| 353 Node* right; |
| 354 V value; |
| 355 }; |
| 356 return sizeof(Node) * size; |
| 357 #else |
| 358 // libc++: __tree_node from include/__tree |
| 359 struct Node { |
| 360 Node* left; |
| 361 Node* right; |
| 362 Node* parent; |
| 363 bool is_black; |
| 364 V value; |
| 365 }; |
| 366 return sizeof(Node) * size; |
| 367 #endif |
| 368 } |
| 369 |
| 370 template <class T, class C, class A> |
| 371 size_t EstimateMemoryUsage(const std::set<T, C, A>& set) { |
| 372 using value_type = typename std::set<T, C, A>::value_type; |
| 373 return EstimateTreeMemoryUsage<value_type>(set.size()) + |
| 374 EstimateIterableMemoryUsage(set); |
| 375 } |
| 376 |
| 377 template <class T, class C, class A> |
| 378 size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set) { |
| 379 using value_type = typename std::multiset<T, C, A>::value_type; |
| 380 return EstimateTreeMemoryUsage<value_type>(set.size()) + |
| 381 EstimateIterableMemoryUsage(set); |
| 382 } |
| 383 |
| 384 template <class K, class V, class C, class A> |
| 385 size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map) { |
| 386 using value_type = typename std::map<K, V, C, A>::value_type; |
| 387 return EstimateTreeMemoryUsage<value_type>(map.size()) + |
| 388 EstimateIterableMemoryUsage(map); |
| 389 } |
| 390 |
| 391 template <class K, class V, class C, class A> |
| 392 size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map) { |
| 393 using value_type = typename std::multimap<K, V, C, A>::value_type; |
| 394 return EstimateTreeMemoryUsage<value_type>(map.size()) + |
| 395 EstimateIterableMemoryUsage(map); |
| 396 } |
| 397 |
| 398 // HashMap containers |
| 399 |
| 400 template <class V> |
| 401 size_t EstimateHashMapMemoryUsage(size_t bucket_count, size_t size) { |
| 402 #if defined(_MSC_VER) |
| 403 // MSVC: _Hash (from include/xhash) uses std::list to store values |
| 404 struct Node { |
| 405 Node* prev; |
| 406 Node* next; |
| 407 V value; |
| 408 }; |
| 409 using Bucket = void*; |
| 410 // _Hash::_Init() allocates twice as many buckets |
| 411 // std::list allocates root node from the heap |
| 412 return sizeof(Bucket) * (2 * bucket_count) + sizeof(Node) * (size + 1); |
| 413 #elif defined(__GLIBCXX__) |
| 414 // libstdc++: _Hash_node<T, false> from include/bits/hashtable_policy.h |
| 415 struct Node { |
| 416 V value; |
| 417 Node* next; |
| 418 }; |
| 419 using Bucket = Node*; |
| 420 // _Hashtable::_M_allocate_buckets() from include/bits/hashtable.h |
| 421 // allocates one extra bucket. |
| 422 return sizeof(Bucket) * (bucket_count + 1) + sizeof(Node) * size; |
| 423 #else |
| 424 // libc++: __hash_node from include/__hash_table |
| 425 struct Node { |
| 426 void* next; |
| 427 size_t hash; |
| 428 V value; |
| 429 }; |
| 430 using Bucket = void*; |
| 431 return sizeof(Bucket) * bucket_count + sizeof(Node) * size; |
| 432 #endif |
| 433 } |
| 434 |
| 435 template <class K, class H, class KE, class A> |
| 436 size_t EstimateMemoryUsage(const std::unordered_set<K, H, KE, A>& set) { |
| 437 using value_type = typename std::unordered_set<K, H, KE, A>::value_type; |
| 438 return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(), |
| 439 set.size()) + |
| 440 EstimateIterableMemoryUsage(set); |
| 441 } |
| 442 |
| 443 template <class K, class H, class KE, class A> |
| 444 size_t EstimateMemoryUsage(const std::unordered_multiset<K, H, KE, A>& set) { |
| 445 using value_type = typename std::unordered_multiset<K, H, KE, A>::value_type; |
| 446 return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(), |
| 447 set.size()) + |
| 448 EstimateIterableMemoryUsage(set); |
| 449 } |
| 450 |
| 451 template <class K, class V, class H, class KE, class A> |
| 452 size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map) { |
| 453 using value_type = typename std::unordered_map<K, V, H, KE, A>::value_type; |
| 454 return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(), |
| 455 map.size()) + |
| 456 EstimateIterableMemoryUsage(map); |
| 457 } |
| 458 |
| 459 template <class K, class V, class H, class KE, class A> |
| 460 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) { |
| 461 using value_type = |
| 462 typename std::unordered_multimap<K, V, H, KE, A>::value_type; |
| 463 return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(), |
| 464 map.size()) + |
| 465 EstimateIterableMemoryUsage(map); |
| 466 } |
| 467 |
| 468 } // namespace trace_event |
| 469 } // namespace base |
| 470 |
| 471 #endif // BASE_TRACE_EVENT_ESTIMATE_MEMORY_USAGE_H_ |
OLD | NEW |