Line data    Source code

       1             : // Copyright (c) 2015 The Bitcoin 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 PIVX_MEMUSAGE_H
       6             : #define PIVX_MEMUSAGE_H
       7             : 
       8             : #include "indirectmap.h"
       9             : #include "prevector.h"
      10             : 
      11             : #include <stdlib.h>
      12             : 
      13             : #include <map>
      14             : #include <memory>
      15             : #include <set>
      16             : #include <vector>
      17             : #include <unordered_map>
      18             : #include <unordered_set>
      19             : 
      20             : namespace memusage
      21             : {
      22             : 
      23             : /** Compute the total memory used by allocating alloc bytes. */
      24             : static size_t MallocUsage(size_t alloc);
      25             : 
      26             : /** Dynamic memory usage for built-in types is zero. */
      27             : static inline size_t DynamicUsage(const int8_t& v) { return 0; }
      28             : static inline size_t DynamicUsage(const uint8_t& v) { return 0; }
      29             : static inline size_t DynamicUsage(const int16_t& v) { return 0; }
      30             : static inline size_t DynamicUsage(const uint16_t& v) { return 0; }
      31             : static inline size_t DynamicUsage(const int32_t& v) { return 0; }
      32             : static inline size_t DynamicUsage(const uint32_t& v) { return 0; }
      33             : static inline size_t DynamicUsage(const int64_t& v) { return 0; }
      34             : static inline size_t DynamicUsage(const uint64_t& v) { return 0; }
      35             : static inline size_t DynamicUsage(const float& v) { return 0; }
      36             : static inline size_t DynamicUsage(const double& v) { return 0; }
      37             : template<typename X> static inline size_t DynamicUsage(X * const &v) { return 0; }
      38             : template<typename X> static inline size_t DynamicUsage(const X * const &v) { return 0; }
      39             : template<typename X, typename Y> static inline size_t DynamicUsage(std::pair<X, Y> &p) { return 0; }
      40             : 
      41             : /** Compute the memory used for dynamically allocated but owned data structures.
      42             :  *  For generic data types, this is *not* recursive. DynamicUsage(vector<vector<int> >)
      43             :  *  will compute the memory used for the vector<int>'s, but not for the ints inside.
      44             :  *  This is for efficiency reasons, as these functions are intended to be fast. If
      45             :  *  application data structures require more accurate inner accounting, they should
      46             :  *  use RecursiveDynamicUsage, iterate themselves, or use more efficient caching +
      47             :  *  updating on modification.
      48             :  */
      49             : template<typename X> static size_t DynamicUsage(const std::vector<X>& v);
      50             : template<typename X> static size_t DynamicUsage(const std::set<X>& s);
      51             : template<typename X, typename Y> static size_t DynamicUsage(const std::map<X, Y>& m);
      52             : template<typename X> static size_t DynamicUsage(const X& x);
      53             : 
      54             : template<typename X> static size_t RecursiveDynamicUsage(const std::vector<X>& v);
      55             : template<typename X> static size_t RecursiveDynamicUsage(const std::set<X>& v);
      56             : template<typename X, typename Y> static size_t RecursiveDynamicUsage(const std::map<X, Y>& v);
      57             : template<typename X, typename Y> static size_t RecursiveDynamicUsage(const std::pair<X, Y>& v);
      58             : template<typename X> static size_t RecursiveDynamicUsage(const X& v);
      59             : 
      60     6583321 : static inline size_t MallocUsage(size_t alloc)
      61             : {
      62             :     // Measured on libc6 2.19 on Linux.
      63     6583321 :     if (alloc == 0) {
      64             :         return 0;
      65     7503472 :     } else if (sizeof(void*) == 8) {
      66     3007073 :         return ((alloc + 31) >> 4) << 4;
      67             :     } else if (sizeof(void*) == 4) {
      68             :         return ((alloc + 15) >> 3) << 3;
      69             :     } else {
      70             :         assert(0);
      71             :     }
      72             : }
      73             : 
      74             : // STL data structures
      75             : 
      76             : template<typename X>
      77             : struct stl_tree_node
      78             : {
      79             : private:
      80             :     int color;
      81             :     void* parent;
      82             :     void* left;
      83             :     void* right;
      84             :     X x;
      85             : };
      86             : 
      87             : struct stl_shared_counter
      88             : {
      89             :     /* Various platforms use different sized counters here.
      90             :      * Conservatively assume that they won't be larger than size_t. */
      91             :     void* class_type;
      92             :     size_t use_count;
      93             :     size_t weak_count;
      94             : };
      95             : 
      96             : template<typename X>
      97      620232 : static inline size_t DynamicUsage(const std::vector<X>& v)
      98             : {
      99      620232 :     return MallocUsage(v.capacity() * sizeof(X));
     100             : }
     101             : 
     102             : template<typename X>
     103      620232 : static inline size_t RecursiveDynamicUsage(const std::vector<X>& v)
     104             : {
     105      620232 :     size_t usage = DynamicUsage(v);
     106     2060745 :     for (const X& x : v) {
     107     1440512 :         usage += RecursiveDynamicUsage(x);
     108             :     }
     109      620232 :     return usage;
     110             : }
     111             : 
     112             : template<unsigned int N, typename X, typename S, typename D>
     113    23782620 : static inline size_t DynamicUsage(const prevector<N, X, S, D>& v)
     114             : {
     115      894026 :     return MallocUsage(v.allocated_memory());
     116             : }
     117             : 
     118             : template<typename X, typename Y>
     119     3451482 : static inline size_t DynamicUsage(const std::set<X, Y>& s)
     120             : {
     121     3264586 :     return MallocUsage(sizeof(stl_tree_node<X>)) * s.size();
     122             : }
     123             : 
     124             : template<typename X>
     125             : static inline size_t RecursiveDynamicUsage(const std::set<X>& v)
     126             : {
     127             :     size_t usage = DynamicUsage(v);
     128             :     for (const X& x : v) {
     129             :         usage += RecursiveDynamicUsage(x);
     130             :     }
     131             :     return usage;
     132             : }
     133             : 
     134             : template<typename X, typename Y>
     135      124560 : static inline size_t IncrementalDynamicUsage(const std::set<X, Y>& s)
     136             : {
     137      124560 :     return MallocUsage(sizeof(stl_tree_node<X>));
     138             : }
     139             : 
     140             : template<typename X, typename Y, typename Z>
     141      562486 : static inline size_t DynamicUsage(const std::map<X, Y, Z>& m)
     142             : {
     143      562486 :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)) * m.size();
     144             : }
     145             : 
     146             : template<typename X, typename Y>
     147      562486 : static inline size_t DynamicUsage(const std::map<X, Y>& m)
     148             : {
     149      562486 :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)) * m.size();
     150             : }
     151             : 
     152             : template<typename X, typename Y>
     153             : static inline size_t RecursiveDynamicUsage(const std::map<X, Y>& v)
     154             : {
     155             :     size_t usage = DynamicUsage(v);
     156             :     for (typename std::map<X, Y>::const_iterator it = v.begin(); it != v.end(); it++) {
     157             :         usage += RecursiveDynamicUsage(*it);
     158             :     }
     159             :     return usage;
     160             : }
     161             : 
     162             : template<typename X, typename Y, typename Z>
     163             : static inline size_t IncrementalDynamicUsage(const std::map<X, Y, Z>& m)
     164             : {
     165             :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >));
     166             : }
     167             : 
     168             : template<typename X, typename Y>
     169             : static inline size_t RecursiveDynamicUsage(const std::pair<X, Y>& v)
     170             : {
     171             :     return RecursiveDynamicUsage(v.first) + RecursiveDynamicUsage(v.second);
     172             : }
     173             : 
     174             : template<typename X>
     175             : static inline size_t DynamicUsage(const std::unique_ptr<X>& p)
     176             : {
     177             :     return p ? MallocUsage(sizeof(X)) : 0;
     178             : }
     179             : 
     180             : template<typename X>
     181      118575 : static inline size_t DynamicUsage(const std::shared_ptr<X>& p)
     182             : {
     183             :     // A shared_ptr can either use a single continuous memory block for both
     184             :     // the counter and the storage (when using std::make_shared), or separate.
     185             :     // We can't observe the difference, however, so assume the worst.
     186      118575 :     return p ? MallocUsage(sizeof(X)) + MallocUsage(sizeof(stl_shared_counter)) : 0;
     187             : }
     188             : 
     189             : // indirectmap has underlying map with pointer as key
     190             : 
     191             : template<typename X, typename Y>
     192      562486 : static inline size_t DynamicUsage(const indirectmap<X, Y>& m)
     193             : {
     194      562486 :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >)) * m.size();
     195             : }
     196             : 
     197             : template<typename X, typename Y>
     198             : static inline size_t IncrementalDynamicUsage(const indirectmap<X, Y>& m)
     199             : {
     200             :     return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >));
     201             : }
     202             : 
     203             : // Boost data structures
     204             : 
     205             : template<typename X>
     206             : struct unordered_node : private X
     207             : {
     208             : private:
     209             :     void* ptr;
     210             : };
     211             : 
     212             : template<typename X, typename Y>
     213             : static inline size_t DynamicUsage(const std::unordered_set<X, Y>& s)
     214             : {
     215             :     return MallocUsage(sizeof(unordered_node<X>)) * s.size() + MallocUsage(sizeof(void*) * s.bucket_count());
     216             : }
     217             : 
     218             : template<typename X, typename Y, typename Z>
     219      613572 : static inline size_t DynamicUsage(const std::unordered_map<X, Y, Z>& m)
     220             : {
     221      920644 :     return MallocUsage(sizeof(unordered_node<std::pair<const X, Y> >)) * m.size() + MallocUsage(sizeof(void*) * m.bucket_count());
     222             : }
     223             : 
     224             : // Dispatch to class method as fallback
     225             : 
     226             : template<typename X>
     227    10421106 : static inline size_t DynamicUsage(const X& x)
     228             : {
     229    23292040 :     return x.DynamicMemoryUsage();
     230             : }
     231             : 
     232             : template<typename X>
     233     1559091 : static inline size_t RecursiveDynamicUsage(const X& x)
     234             : {
     235     1559091 :     return DynamicUsage(x);
     236             : }
     237             : 
     238             : template<typename X>
     239      118575 : static inline size_t RecursiveDynamicUsage(const std::shared_ptr<X>& p)
     240             : {
     241      118575 :     return p ? memusage::DynamicUsage(p) + RecursiveDynamicUsage(*p) : 0;
     242             : }
     243             : 
     244             : }
     245             : 
     246             : #endif // PIVX_MEMUSAGE_H