memusage.h raw
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
221