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