memusage.h
1 // Copyright (c) 2015-2022 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 #include <support/allocators/pool.h> 11 12 #include <cassert> 13 #include <cstdlib> 14 #include <list> 15 #include <map> 16 #include <memory> 17 #include <set> 18 #include <vector> 19 #include <unordered_map> 20 #include <unordered_set> 21 22 23 namespace memusage 24 { 25 26 /** Compute the total memory used by allocating alloc bytes. */ 27 static size_t MallocUsage(size_t alloc); 28 29 /** Dynamic memory usage for built-in types is zero. */ 30 static inline size_t DynamicUsage(const int8_t& v) { return 0; } 31 static inline size_t DynamicUsage(const uint8_t& v) { return 0; } 32 static inline size_t DynamicUsage(const int16_t& v) { return 0; } 33 static inline size_t DynamicUsage(const uint16_t& v) { return 0; } 34 static inline size_t DynamicUsage(const int32_t& v) { return 0; } 35 static inline size_t DynamicUsage(const uint32_t& v) { return 0; } 36 static inline size_t DynamicUsage(const int64_t& v) { return 0; } 37 static inline size_t DynamicUsage(const uint64_t& v) { return 0; } 38 static inline size_t DynamicUsage(const float& v) { return 0; } 39 static inline size_t DynamicUsage(const double& v) { return 0; } 40 template<typename X> static inline size_t DynamicUsage(X * const &v) { return 0; } 41 template<typename X> static inline size_t DynamicUsage(const X * const &v) { return 0; } 42 43 /** Compute the memory used for dynamically allocated but owned data structures. 44 * For generic data types, this is *not* recursive. DynamicUsage(vector<vector<int> >) 45 * will compute the memory used for the vector<int>'s, but not for the ints inside. 46 * This is for efficiency reasons, as these functions are intended to be fast. If 47 * application data structures require more accurate inner accounting, they should 48 * iterate themselves, or use more efficient caching + updating on modification. 49 */ 50 51 static inline size_t MallocUsage(size_t alloc) 52 { 53 // Measured on libc6 2.19 on Linux. 54 if (alloc == 0) { 55 return 0; 56 } else if (sizeof(void*) == 8) { 57 return ((alloc + 31) >> 4) << 4; 58 } else if (sizeof(void*) == 4) { 59 return ((alloc + 15) >> 3) << 3; 60 } else { 61 assert(0); 62 } 63 } 64 65 // STL data structures 66 67 template<typename X> 68 struct stl_tree_node 69 { 70 private: 71 int color; 72 void* parent; 73 void* left; 74 void* right; 75 X x; 76 }; 77 78 struct stl_shared_counter 79 { 80 /* Various platforms use different sized counters here. 81 * Conservatively assume that they won't be larger than size_t. */ 82 void* class_type; 83 size_t use_count; 84 size_t weak_count; 85 }; 86 87 template<typename X> 88 static inline size_t DynamicUsage(const std::vector<X>& v) 89 { 90 return MallocUsage(v.capacity() * sizeof(X)); 91 } 92 93 template<unsigned int N, typename X, typename S, typename D> 94 static inline size_t DynamicUsage(const prevector<N, X, S, D>& v) 95 { 96 return MallocUsage(v.allocated_memory()); 97 } 98 99 template<typename X, typename Y> 100 static inline size_t DynamicUsage(const std::set<X, Y>& s) 101 { 102 return MallocUsage(sizeof(stl_tree_node<X>)) * s.size(); 103 } 104 105 template<typename X, typename Y> 106 static inline size_t IncrementalDynamicUsage(const std::set<X, Y>& s) 107 { 108 return MallocUsage(sizeof(stl_tree_node<X>)); 109 } 110 111 template<typename X, typename Y, typename Z> 112 static inline size_t DynamicUsage(const std::map<X, Y, Z>& m) 113 { 114 return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)) * m.size(); 115 } 116 117 template<typename X, typename Y, typename Z> 118 static inline size_t IncrementalDynamicUsage(const std::map<X, Y, Z>& m) 119 { 120 return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)); 121 } 122 123 // indirectmap has underlying map with pointer as key 124 125 template<typename X, typename Y> 126 static inline size_t DynamicUsage(const indirectmap<X, Y>& m) 127 { 128 return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >)) * m.size(); 129 } 130 131 template<typename X, typename Y> 132 static inline size_t IncrementalDynamicUsage(const indirectmap<X, Y>& m) 133 { 134 return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >)); 135 } 136 137 template<typename X> 138 static inline size_t DynamicUsage(const std::unique_ptr<X>& p) 139 { 140 return p ? MallocUsage(sizeof(X)) : 0; 141 } 142 143 template<typename X> 144 static inline size_t DynamicUsage(const std::shared_ptr<X>& p) 145 { 146 // A shared_ptr can either use a single continuous memory block for both 147 // the counter and the storage (when using std::make_shared), or separate. 148 // We can't observe the difference, however, so assume the worst. 149 return p ? MallocUsage(sizeof(X)) + MallocUsage(sizeof(stl_shared_counter)) : 0; 150 } 151 152 template<typename X> 153 struct list_node 154 { 155 private: 156 void* ptr_next; 157 void* ptr_prev; 158 X x; 159 }; 160 161 template<typename X> 162 static inline size_t DynamicUsage(const std::list<X>& l) 163 { 164 return MallocUsage(sizeof(list_node<X>)) * l.size(); 165 } 166 167 template<typename X> 168 struct unordered_node : private X 169 { 170 private: 171 void* ptr; 172 }; 173 174 template<typename X, typename Y> 175 static inline size_t DynamicUsage(const std::unordered_set<X, Y>& s) 176 { 177 return MallocUsage(sizeof(unordered_node<X>)) * s.size() + MallocUsage(sizeof(void*) * s.bucket_count()); 178 } 179 180 template<typename X, typename Y, typename Z> 181 static inline size_t DynamicUsage(const std::unordered_map<X, Y, Z>& m) 182 { 183 return MallocUsage(sizeof(unordered_node<std::pair<const X, Y> >)) * m.size() + MallocUsage(sizeof(void*) * m.bucket_count()); 184 } 185 186 template <class Key, class T, class Hash, class Pred, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> 187 static inline size_t DynamicUsage(const std::unordered_map<Key, 188 T, 189 Hash, 190 Pred, 191 PoolAllocator<std::pair<const Key, T>, 192 MAX_BLOCK_SIZE_BYTES, 193 ALIGN_BYTES>>& m) 194 { 195 auto* pool_resource = m.get_allocator().resource(); 196 197 // The allocated chunks are stored in a std::list. Size per node should 198 // therefore be 3 pointers: next, previous, and a pointer to the chunk. 199 size_t estimated_list_node_size = MallocUsage(sizeof(void*) * 3); 200 size_t usage_resource = estimated_list_node_size * pool_resource->NumAllocatedChunks(); 201 size_t usage_chunks = MallocUsage(pool_resource->ChunkSizeBytes()) * pool_resource->NumAllocatedChunks(); 202 return usage_resource + usage_chunks + MallocUsage(sizeof(void*) * m.bucket_count()); 203 } 204 205 } // namespace memusage 206 207 #endif // BITCOIN_MEMUSAGE_H