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_MEMORY_USAGE_ESTIMATOR_H_ |
| 6 #define BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_ |
| 7 |
| 8 #include <stdint.h> |
| 9 |
| 10 #include <array> |
| 11 #include <list> |
| 12 #include <map> |
| 13 #include <memory> |
| 14 #include <set> |
| 15 #include <string> |
| 16 #include <type_traits> |
| 17 #include <unordered_map> |
| 18 #include <unordered_set> |
| 19 #include <vector> |
| 20 |
| 21 #include "base/base_export.h" |
| 22 #include "base/strings/string16.h" |
| 23 #include "base/template_util.h" |
| 24 |
| 25 // Composable memory usage estimators. |
| 26 // |
| 27 // This file defines set of EstimateMemoryUsage(object) functions that return |
| 28 // approximate memory usage of their argument. |
| 29 // |
| 30 // The ultimate goal is to make memory usage estimation for a class simply a |
| 31 // matter of aggregating EstimateMemoryUsage() results over all fields. |
| 32 // |
| 33 // That is achieved via composability: if EstimateMemoryUsage() is defined |
| 34 // for T then EstimateMemoryUsage() is also defined for any combination of |
| 35 // containers holding T (e.g. std::map<int, std::vector<T>>). |
| 36 // |
| 37 // There are two ways of defining EstimateMemoryUsage() for a type: |
| 38 // |
| 39 // 1. As a global function 'size_t EstimateMemoryUsage(T)' in |
| 40 // in base::trace_event namespace. |
| 41 // |
| 42 // 2. As 'size_t T::EstimateMemoryUsage() const' method. In this case |
| 43 // EstimateMemoryUsage(T) function in base::trace_event namespace is |
| 44 // provided automatically. |
| 45 // |
| 46 // Here is an example implementation: |
| 47 // |
| 48 // size_t foo::bar::MyClass::EstimateMemoryUsage() const { |
| 49 // return base::trace_event::EstimateMemoryUsage(name_) + |
| 50 // base::trace_event::EstimateMemoryUsage(id_) + |
| 51 // base::trace_event::EstimateMemoryUsage(items_); |
| 52 // } |
| 53 // |
| 54 // The approach is simple: first call EstimateMemoryUsage() on all members, |
| 55 // then recursively fix compilation errors that are caused by types not |
| 56 // implementing EstimateMemoryUsage(). |
| 57 |
| 58 namespace base { |
| 59 namespace trace_event { |
| 60 |
| 61 // Declarations |
| 62 |
| 63 // If T declares 'EstimateMemoryUsage() const' member function, then |
| 64 // global function EstimateMemoryUsage(T) is available, and just calls |
| 65 // the member function. |
| 66 template <class T> |
| 67 auto EstimateMemoryUsage(const T& object) |
| 68 -> decltype(object.EstimateMemoryUsage()); |
| 69 |
| 70 // String |
| 71 |
| 72 template <class C, class T, class A> |
| 73 size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string); |
| 74 |
| 75 // Arrays |
| 76 |
| 77 template <class T, size_t N> |
| 78 size_t EstimateMemoryUsage(const std::array<T, N>& array); |
| 79 |
| 80 template <class T, size_t N> |
| 81 size_t EstimateMemoryUsage(T (&array)[N]); |
| 82 |
| 83 template <class T> |
| 84 size_t EstimateMemoryUsage(const T* array, size_t array_length); |
| 85 |
| 86 // std::unique_ptr |
| 87 |
| 88 template <class T, class D> |
| 89 size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr); |
| 90 |
| 91 template <class T, class D> |
| 92 size_t EstimateMemoryUsage(const std::unique_ptr<T[], D>& array, |
| 93 size_t array_length); |
| 94 |
| 95 // Containers |
| 96 |
| 97 template <class F, class S> |
| 98 size_t EstimateMemoryUsage(const std::pair<F, S>& pair); |
| 99 |
| 100 template <class T, class A> |
| 101 size_t EstimateMemoryUsage(const std::vector<T, A>& vector); |
| 102 |
| 103 template <class T, class A> |
| 104 size_t EstimateMemoryUsage(const std::list<T, A>& list); |
| 105 |
| 106 template <class T, class C, class A> |
| 107 size_t EstimateMemoryUsage(const std::set<T, C, A>& set); |
| 108 |
| 109 template <class T, class C, class A> |
| 110 size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set); |
| 111 |
| 112 template <class K, class V, class C, class A> |
| 113 size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map); |
| 114 |
| 115 template <class K, class V, class C, class A> |
| 116 size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map); |
| 117 |
| 118 template <class T, class H, class KE, class A> |
| 119 size_t EstimateMemoryUsage(const std::unordered_set<T, H, KE, A>& set); |
| 120 |
| 121 template <class T, class H, class KE, class A> |
| 122 size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set); |
| 123 |
| 124 template <class K, class V, class H, class KE, class A> |
| 125 size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map); |
| 126 |
| 127 template <class K, class V, class H, class KE, class A> |
| 128 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map); |
| 129 |
| 130 // TODO(dskiba): |
| 131 // std::forward_list |
| 132 // std::deque |
| 133 // std::queue |
| 134 // std::stack |
| 135 // std::queue |
| 136 // std::priority_queue |
| 137 |
| 138 // Definitions |
| 139 |
| 140 namespace internal { |
| 141 |
| 142 // HasEMU<T>::value is true iff EstimateMemoryUsage(T) is available. |
| 143 // (This is the default version, which is false.) |
| 144 template <class T, class X = void> |
| 145 struct HasEMU : std::false_type {}; |
| 146 |
| 147 // This HasEMU specialization is only picked up if there exists function |
| 148 // EstimateMemoryUsage(const T&) that returns size_t. Simpler ways to |
| 149 // achieve this don't work on MSVC. |
| 150 template <class T> |
| 151 struct HasEMU< |
| 152 T, |
| 153 typename std::enable_if<std::is_same< |
| 154 size_t, |
| 155 decltype(EstimateMemoryUsage(std::declval<const T&>()))>::value>::type> |
| 156 : std::true_type {}; |
| 157 |
| 158 // EMUCaller<T> does three things: |
| 159 // 1. Defines Call() method that calls EstimateMemoryUsage(T) if it's |
| 160 // available. |
| 161 // 2. If EstimateMemoryUsage(T) is not available, but T has trivial dtor |
| 162 // (i.e. it's POD, integer, pointer, enum, etc.) then it defines Call() |
| 163 // method that returns 0. This is useful for containers, which allocate |
| 164 // memory regardless of T (also for cases like std::map<int, MyClass>). |
| 165 // 3. Finally, if EstimateMemoryUsage(T) is not available, then it triggers |
| 166 // a static_assert with a helpful message. That cuts numbers of errors |
| 167 // considerably - if you just call EstimateMemoryUsage(T) but it's not |
| 168 // available for T, then compiler will helpfully list *all* possible |
| 169 // variants of it, with an explanation for each. |
| 170 template <class T, class X = void> |
| 171 struct EMUCaller { |
| 172 // std::is_same<> below makes static_assert depend on T, in order to |
| 173 // prevent it from asserting regardless instantiation. |
| 174 static_assert(std::is_same<T, std::false_type>::value, |
| 175 "Neither global function 'size_t EstimateMemoryUsage(T)' " |
| 176 "nor member function 'size_t T::EstimateMemoryUsage() const' " |
| 177 "is defined for the type."); |
| 178 |
| 179 static size_t Call(const T&) { return 0; } |
| 180 }; |
| 181 |
| 182 template <class T> |
| 183 struct EMUCaller<T, typename std::enable_if<HasEMU<T>::value>::type> { |
| 184 static size_t Call(const T& value) { return EstimateMemoryUsage(value); } |
| 185 }; |
| 186 |
| 187 template <class T> |
| 188 struct EMUCaller< |
| 189 T, |
| 190 typename std::enable_if<!HasEMU<T>::value && |
| 191 is_trivially_destructible<T>::value>::type> { |
| 192 static size_t Call(const T& value) { return 0; } |
| 193 }; |
| 194 |
| 195 } // namespace internal |
| 196 |
| 197 // Proxy that deducts T and calls EMUCaller<T>. |
| 198 // To be used by EstimateMemoryUsage() implementations for containers. |
| 199 template <class T> |
| 200 size_t EstimateItemMemoryUsage(const T& value) { |
| 201 return internal::EMUCaller<T>::Call(value); |
| 202 } |
| 203 |
| 204 template <class I> |
| 205 size_t EstimateIterableMemoryUsage(const I& iterable) { |
| 206 size_t memory_usage = 0; |
| 207 for (const auto& item : iterable) { |
| 208 memory_usage += EstimateItemMemoryUsage(item); |
| 209 } |
| 210 return memory_usage; |
| 211 } |
| 212 |
| 213 // Global EstimateMemoryUsage(T) that just calls T::EstimateMemoryUsage(). |
| 214 template <class T> |
| 215 auto EstimateMemoryUsage(const T& object) |
| 216 -> decltype(object.EstimateMemoryUsage()) { |
| 217 static_assert( |
| 218 std::is_same<decltype(object.EstimateMemoryUsage()), size_t>::value, |
| 219 "'T::EstimateMemoryUsage() const' must return size_t."); |
| 220 return object.EstimateMemoryUsage(); |
| 221 } |
| 222 |
| 223 // String |
| 224 |
| 225 template <class C, class T, class A> |
| 226 size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string) { |
| 227 using string_type = std::basic_string<C, T, A>; |
| 228 using value_type = typename string_type::value_type; |
| 229 // C++11 doesn't leave much room for implementors - std::string can |
| 230 // use short string optimization, but that's about it. We detect SSO |
| 231 // by checking that c_str() points inside |string|. |
| 232 const uint8_t* cstr = reinterpret_cast<const uint8_t*>(string.c_str()); |
| 233 const uint8_t* inline_cstr = reinterpret_cast<const uint8_t*>(&string); |
| 234 if (cstr >= inline_cstr && cstr < inline_cstr + sizeof(string)) { |
| 235 // SSO string |
| 236 return 0; |
| 237 } |
| 238 return (string.capacity() + 1) * sizeof(value_type); |
| 239 } |
| 240 |
| 241 // Use explicit instantiations from the .cc file (reduces bloat). |
| 242 extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::string&); |
| 243 extern template BASE_EXPORT size_t EstimateMemoryUsage(const string16&); |
| 244 |
| 245 // Arrays |
| 246 |
| 247 template <class T, size_t N> |
| 248 size_t EstimateMemoryUsage(const std::array<T, N>& array) { |
| 249 return EstimateIterableMemoryUsage(array); |
| 250 } |
| 251 |
| 252 template <class T, size_t N> |
| 253 size_t EstimateMemoryUsage(T (&array)[N]) { |
| 254 return EstimateIterableMemoryUsage(array); |
| 255 } |
| 256 |
| 257 template <class T> |
| 258 size_t EstimateMemoryUsage(const T* array, size_t array_length) { |
| 259 size_t memory_usage = sizeof(T) * array_length; |
| 260 for (size_t i = 0; i != array_length; ++i) { |
| 261 memory_usage += EstimateItemMemoryUsage(array[i]); |
| 262 } |
| 263 return memory_usage; |
| 264 } |
| 265 |
| 266 // std::unique_ptr |
| 267 |
| 268 template <class T, class D> |
| 269 size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr) { |
| 270 return ptr ? (sizeof(T) + EstimateItemMemoryUsage(*ptr)) : 0; |
| 271 } |
| 272 |
| 273 template <class T, class D> |
| 274 size_t EstimateMemoryUsage(const std::unique_ptr<T[], D>& array, |
| 275 size_t array_length) { |
| 276 return EstimateMemoryUsage(array.get(), array_length); |
| 277 } |
| 278 |
| 279 // std::pair |
| 280 |
| 281 template <class F, class S> |
| 282 size_t EstimateMemoryUsage(const std::pair<F, S>& pair) { |
| 283 return EstimateItemMemoryUsage(pair.first) + |
| 284 EstimateItemMemoryUsage(pair.second); |
| 285 } |
| 286 |
| 287 // std::vector |
| 288 |
| 289 template <class T, class A> |
| 290 size_t EstimateMemoryUsage(const std::vector<T, A>& vector) { |
| 291 return sizeof(T) * vector.capacity() + EstimateIterableMemoryUsage(vector); |
| 292 } |
| 293 |
| 294 // std::list |
| 295 |
| 296 template <class T, class A> |
| 297 size_t EstimateMemoryUsage(const std::list<T, A>& list) { |
| 298 using value_type = typename std::list<T, A>::value_type; |
| 299 struct Node { |
| 300 Node* prev; |
| 301 Node* next; |
| 302 value_type value; |
| 303 }; |
| 304 return sizeof(Node) * list.size() + |
| 305 EstimateIterableMemoryUsage(list); |
| 306 } |
| 307 |
| 308 // Tree containers |
| 309 |
| 310 template <class V> |
| 311 size_t EstimateTreeMemoryUsage(size_t size) { |
| 312 // Tree containers are modeled after libc++ |
| 313 // (__tree_node from include/__tree) |
| 314 struct Node { |
| 315 Node* left; |
| 316 Node* right; |
| 317 Node* parent; |
| 318 bool is_black; |
| 319 V value; |
| 320 }; |
| 321 return sizeof(Node) * size; |
| 322 } |
| 323 |
| 324 template <class T, class C, class A> |
| 325 size_t EstimateMemoryUsage(const std::set<T, C, A>& set) { |
| 326 using value_type = typename std::set<T, C, A>::value_type; |
| 327 return EstimateTreeMemoryUsage<value_type>(set.size()) + |
| 328 EstimateIterableMemoryUsage(set); |
| 329 } |
| 330 |
| 331 template <class T, class C, class A> |
| 332 size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set) { |
| 333 using value_type = typename std::multiset<T, C, A>::value_type; |
| 334 return EstimateTreeMemoryUsage<value_type>(set.size()) + |
| 335 EstimateIterableMemoryUsage(set); |
| 336 } |
| 337 |
| 338 template <class K, class V, class C, class A> |
| 339 size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map) { |
| 340 using value_type = typename std::map<K, V, C, A>::value_type; |
| 341 return EstimateTreeMemoryUsage<value_type>(map.size()) + |
| 342 EstimateIterableMemoryUsage(map); |
| 343 } |
| 344 |
| 345 template <class K, class V, class C, class A> |
| 346 size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map) { |
| 347 using value_type = typename std::multimap<K, V, C, A>::value_type; |
| 348 return EstimateTreeMemoryUsage<value_type>(map.size()) + |
| 349 EstimateIterableMemoryUsage(map); |
| 350 } |
| 351 |
| 352 // HashMap containers |
| 353 |
| 354 namespace internal { |
| 355 |
| 356 // While hashtable containers model doesn't depend on STL implementation, one |
| 357 // detail still crept in: bucket_count. It's used in size estimation, but its |
| 358 // value after inserting N items is not predictable. |
| 359 // This function is specialized by unittests to return constant value, thus |
| 360 // excluding bucket_count from testing. |
| 361 template <class V> |
| 362 size_t HashMapBucketCountForTesting(size_t bucket_count) { |
| 363 return bucket_count; |
| 364 } |
| 365 |
| 366 } // namespace internal |
| 367 |
| 368 template <class V> |
| 369 size_t EstimateHashMapMemoryUsage(size_t bucket_count, size_t size) { |
| 370 // Hashtable containers are modeled after libc++ |
| 371 // (__hash_node from include/__hash_table) |
| 372 struct Node { |
| 373 void* next; |
| 374 size_t hash; |
| 375 V value; |
| 376 }; |
| 377 using Bucket = void*; |
| 378 bucket_count = internal::HashMapBucketCountForTesting<V>(bucket_count); |
| 379 return sizeof(Bucket) * bucket_count + sizeof(Node) * size; |
| 380 } |
| 381 |
| 382 template <class K, class H, class KE, class A> |
| 383 size_t EstimateMemoryUsage(const std::unordered_set<K, H, KE, A>& set) { |
| 384 using value_type = typename std::unordered_set<K, H, KE, A>::value_type; |
| 385 return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(), |
| 386 set.size()) + |
| 387 EstimateIterableMemoryUsage(set); |
| 388 } |
| 389 |
| 390 template <class K, class H, class KE, class A> |
| 391 size_t EstimateMemoryUsage(const std::unordered_multiset<K, H, KE, A>& set) { |
| 392 using value_type = typename std::unordered_multiset<K, H, KE, A>::value_type; |
| 393 return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(), |
| 394 set.size()) + |
| 395 EstimateIterableMemoryUsage(set); |
| 396 } |
| 397 |
| 398 template <class K, class V, class H, class KE, class A> |
| 399 size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map) { |
| 400 using value_type = typename std::unordered_map<K, V, H, KE, A>::value_type; |
| 401 return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(), |
| 402 map.size()) + |
| 403 EstimateIterableMemoryUsage(map); |
| 404 } |
| 405 |
| 406 template <class K, class V, class H, class KE, class A> |
| 407 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) { |
| 408 using value_type = |
| 409 typename std::unordered_multimap<K, V, H, KE, A>::value_type; |
| 410 return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(), |
| 411 map.size()) + |
| 412 EstimateIterableMemoryUsage(map); |
| 413 } |
| 414 |
| 415 } // namespace trace_event |
| 416 } // namespace base |
| 417 |
| 418 #endif // BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_ |
OLD | NEW |