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
|