Branch data Line data Source code
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 : 36177559 : static inline size_t MallocUsage(size_t alloc)
52 : : {
53 : : // Measured on libc6 2.19 on Linux.
54 [ + + ]: 2236345 : if (alloc == 0) {
[ + - + - ]
[ + - + -
+ - ]
55 : : return 0;
56 : 34995844 : } else if (sizeof(void*) == 8) {
57 : 34995844 : 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 [ + + + + : 2008033 : static inline size_t DynamicUsage(const std::vector<X>& v)
+ + + + ]
[ + + + + ]
89 : : {
90 [ + + + + : 2392245 : return MallocUsage(v.capacity() * sizeof(X));
+ + + + ]
[ + + + + ]
91 : : }
92 : :
93 : : template<unsigned int N, typename X, typename S, typename D>
94 [ + + + + : 34888151 : static inline size_t DynamicUsage(const prevector<N, X, S, D>& v)
+ + + + +
+ + + + +
+ + + + +
+ + + -
- ]
[ + + + + ]
[ - + # # ]
[ - + + +
- + ]
95 : : {
96 [ + - + + : 67127975 : return MallocUsage(v.allocated_memory());
+ - + - +
- + - + +
+ - + - +
+ + - + -
+ - + - +
+ - - ][ +
- + - +
+ ][ - - #
# # # ][ +
- + - - -
- - ]
97 : : }
98 : :
99 : : template<typename X, typename Y>
100 : 6856115 : static inline size_t DynamicUsage(const std::set<X, Y>& s)
101 : : {
102 : 6856115 : 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 : 439069 : static inline size_t DynamicUsage(const std::map<X, Y, Z>& m)
113 : : {
114 [ + + ]: 439069 : 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 : 439069 : static inline size_t DynamicUsage(const indirectmap<X, Y>& m)
127 : : {
128 [ + + ]: 439069 : 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 : 83294 : 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 : 16209 : static inline size_t DynamicUsage(const std::list<X>& l)
163 : : {
164 : 16209 : 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 : 16213 : static inline size_t DynamicUsage(const std::unordered_map<X, Y, Z>& m)
182 : : {
183 [ + - ][ + - : 16217 : 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 [ + - ]: 956736 : 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 : 956736 : 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 [ + - ]: 956736 : size_t estimated_list_node_size = MallocUsage(sizeof(void*) * 3);
200 [ + - ]: 956736 : size_t usage_resource = estimated_list_node_size * pool_resource->NumAllocatedChunks();
201 [ + - + - ]: 1913472 : size_t usage_chunks = MallocUsage(pool_resource->ChunkSizeBytes()) * pool_resource->NumAllocatedChunks();
202 [ + - ]: 956736 : return usage_resource + usage_chunks + MallocUsage(sizeof(void*) * m.bucket_count());
203 : : }
204 : :
205 : : } // namespace memusage
206 : :
207 : : #endif // BITCOIN_MEMUSAGE_H
|
