Line data    Source code

       1             : // Copyright (c) 2015-2020 The Bitcoin Core developers
       2             : // Distributed under the MIT software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #ifndef BITCOIN_MEMUSAGE_H
       6             : #define BITCOIN_MEMUSAGE_H
       7             : 
       8             : #include <indirectmap.h>
       9             : #include <prevector.h>
      10             : 
      11             : #include <stdlib.h>
      12             : 
      13             : #include <cassert>
      14             : #include <map>
      15             : #include <memory>
      16             : #include <set>
      17             : #include <vector>
      18             : #include <unordered_map>
      19             : #include <unordered_set>
      20             : 
      21             : 
      22             : namespace memusage
      23             : {
      24             : 
      25             : /** Compute the total memory used by allocating alloc bytes. */
      26             : static size_t MallocUsage(size_t alloc);
      27             : 
      28             : /** Dynamic memory usage for built-in types is zero. */
      29             : static inline size_t DynamicUsage(const int8_t& v) { return 0; }
      30             : static inline size_t DynamicUsage(const uint8_t& v) { return 0; }
      31             : static inline size_t DynamicUsage(const int16_t& v) { return 0; }
      32             : static inline size_t DynamicUsage(const uint16_t& v) { return 0; }
      33             : static inline size_t DynamicUsage(const int32_t& v) { return 0; }
      34             : static inline size_t DynamicUsage(const uint32_t& v) { return 0; }
      35             : static inline size_t DynamicUsage(const int64_t& v) { return 0; }
      36             : static inline size_t DynamicUsage(const uint64_t& v) { return 0; }
      37             : static inline size_t DynamicUsage(const float& v) { return 0; }
      38             : static inline size_t DynamicUsage(const double& v) { return 0; }
      39             : template<typename X> static inline size_t DynamicUsage(X * const &v) { return 0; }
      40             : template<typename X> static inline size_t DynamicUsage(const X * const &v) { return 0; }
      41             : 
      42             : /** Compute the memory used for dynamically allocated but owned data structures.
      43             :  *  For generic data types, this is *not* recursive. DynamicUsage(vector<vector<int> >)
      44             :  *  will compute the memory used for the vector<int>'s, but not for the ints inside.
      45             :  *  This is for efficiency reasons, as these functions are intended to be fast. If
      46             :  *  application data structures require more accurate inner accounting, they should
      47             :  *  iterate themselves, or use more efficient caching + updating on modification.
      48             :  */
      49             : 
      50    39461176 : static inline size_t MallocUsage(size_t alloc)
      51             : {
      52             :     // Measured on libc6 2.19 on Linux.
      53    39461176 :     if (alloc == 0) {
      54    25934825 :         return 0;
      55             :     } else if (sizeof(void*) == 8) {
      56    13526351 :         return ((alloc + 31) >> 4) << 4;
      57             :     } else if (sizeof(void*) == 4) {
      58             :         return ((alloc + 15) >> 3) << 3;
      59             :     } else {
      60             :         assert(0);
      61             :     }
      62    39461176 : }
      63             : 
      64             : // STL data structures
      65             : 
      66             : template<typename X>
      67             : struct stl_tree_node
      68             : {
      69             : private:
      70             :     int color;
      71             :     void* parent;
      72             :     void* left;
      73             :     void* right;
      74             :     X x;
      75             : };
      76             : 
      77             : struct stl_shared_counter
      78             : {
      79             :     /* Various platforms use different sized counters here.
      80             :      * Conservatively assume that they won't be larger than size_t. */
      81             :     void* class_type;
      82             :     size_t use_count;
      83             :     size_t weak_count;
      84             : };
      85             : 
      86             : template<typename X>
      87      679586 : static inline size_t DynamicUsage(const std::vector<X>& v)
      88             : {
      89      679586 :     return MallocUsage(v.capacity() * sizeof(X));
      90             : }
      91             : 
      92             : template<unsigned int N, typename X, typename S, typename D>
      93    26806225 : static inline size_t DynamicUsage(const prevector<N, X, S, D>& v)
      94             : {
      95    26806225 :     return MallocUsage(v.allocated_memory());
      96             : }
      97             : 
      98             : template<typename X, typename Y>
      99    10331164 : static inline size_t DynamicUsage(const std::set<X, Y>& s)
     100             : {
     101    10331164 :     return MallocUsage(sizeof(stl_tree_node<X>)) * s.size();
     102             : }
     103             : 
     104             : template<typename X, typename Y>
     105      161236 : static inline size_t IncrementalDynamicUsage(const std::set<X, Y>& s)
     106             : {
     107      161236 :     return MallocUsage(sizeof(stl_tree_node<X>));
     108             : }
     109             : 
     110             : template<typename X, typename Y, typename Z>
     111      194583 : static inline size_t DynamicUsage(const std::map<X, Y, Z>& m)
     112             : {
     113      194583 :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)) * m.size();
     114             : }
     115             : 
     116             : template<typename X, typename Y, typename Z>
     117             : static inline size_t IncrementalDynamicUsage(const std::map<X, Y, Z>& m)
     118             : {
     119             :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >));
     120             : }
     121             : 
     122             : // indirectmap has underlying map with pointer as key
     123             : 
     124             : template<typename X, typename Y>
     125      194583 : static inline size_t DynamicUsage(const indirectmap<X, Y>& m)
     126             : {
     127      194583 :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >)) * m.size();
     128             : }
     129             : 
     130             : template<typename X, typename Y>
     131             : static inline size_t IncrementalDynamicUsage(const indirectmap<X, Y>& m)
     132             : {
     133             :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >));
     134             : }
     135             : 
     136             : template<typename X>
     137             : static inline size_t DynamicUsage(const std::unique_ptr<X>& p)
     138             : {
     139             :     return p ? MallocUsage(sizeof(X)) : 0;
     140             : }
     141             : 
     142             : template<typename X>
     143       69329 : static inline size_t DynamicUsage(const std::shared_ptr<X>& p)
     144             : {
     145             :     // A shared_ptr can either use a single continuous memory block for both
     146             :     // the counter and the storage (when using std::make_shared), or separate.
     147             :     // We can't observe the difference, however, so assume the worst.
     148       69329 :     return p ? MallocUsage(sizeof(X)) + MallocUsage(sizeof(stl_shared_counter)) : 0;
     149             : }
     150             : 
     151             : template<typename X>
     152             : struct unordered_node : private X
     153             : {
     154             : private:
     155             :     void* ptr;
     156             : };
     157             : 
     158             : template<typename X, typename Y>
     159             : static inline size_t DynamicUsage(const std::unordered_set<X, Y>& s)
     160             : {
     161             :     return MallocUsage(sizeof(unordered_node<X>)) * s.size() + MallocUsage(sizeof(void*) * s.bucket_count());
     162             : }
     163             : 
     164             : template<typename X, typename Y, typename Z>
     165      377108 : static inline size_t DynamicUsage(const std::unordered_map<X, Y, Z>& m)
     166             : {
     167      377108 :     return MallocUsage(sizeof(unordered_node<std::pair<const X, Y> >)) * m.size() + MallocUsage(sizeof(void*) * m.bucket_count());
     168             : }
     169             : 
     170             : }
     171             : 
     172             : #endif // BITCOIN_MEMUSAGE_H