Branch data Line data Source code
1 : : // Copyright (c) 2016-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 : : #include <support/lockedpool.h>
6 : : #include <support/cleanse.h>
7 : :
8 : : #ifdef WIN32
9 : : #include <windows.h>
10 : : #else
11 : : #include <sys/mman.h>
12 : : #include <sys/resource.h>
13 : : #include <unistd.h>
14 : : #endif
15 : :
16 : : #include <algorithm>
17 : : #include <limits>
18 : : #include <stdexcept>
19 : : #include <utility>
20 : : #ifdef ARENA_DEBUG
21 : : #include <iomanip>
22 : : #include <iostream>
23 : : #endif
24 : :
25 : : LockedPoolManager* LockedPoolManager::_instance = nullptr;
26 : :
27 : : /*******************************************************************************/
28 : : // Utilities
29 : : //
30 : : /** Align up to power of 2 */
31 : 47004 : static inline size_t align_up(size_t x, size_t align)
32 : : {
33 : 47004 : return (x + align - 1) & ~(align - 1);
34 : : }
35 : :
36 : : /*******************************************************************************/
37 : : // Implementation: Arena
38 : :
39 : 168 : Arena::Arena(void *base_in, size_t size_in, size_t alignment_in):
40 [ + - ]: 168 : base(base_in), end(static_cast<char*>(base_in) + size_in), alignment(alignment_in)
41 : : {
42 : : // Start with one free chunk that covers the entire arena
43 [ + - ]: 168 : auto it = size_to_free_chunk.emplace(size_in, base);
44 [ + - ]: 168 : chunks_free.emplace(base, it);
45 [ + - ]: 168 : chunks_free_end.emplace(static_cast<char*>(base) + size_in, it);
46 : 168 : }
47 : :
48 : 168 : Arena::~Arena() = default;
49 : :
50 : 46676 : void* Arena::alloc(size_t size)
51 : : {
52 : : // Round to next multiple of alignment
53 : 46676 : size = align_up(size, alignment);
54 : :
55 : : // Don't handle zero-sized chunks
56 [ + + ]: 46676 : if (size == 0)
57 : : return nullptr;
58 : :
59 : : // Pick a large enough free-chunk. Returns an iterator pointing to the first element that is not less than key.
60 : : // This allocation strategy is best-fit. According to "Dynamic Storage Allocation: A Survey and Critical Review",
61 : : // Wilson et. al. 1995, https://www.scs.stanford.edu/14wi-cs140/sched/readings/wilson.pdf, best-fit and first-fit
62 : : // policies seem to work well in practice.
63 : 46674 : auto size_ptr_it = size_to_free_chunk.lower_bound(size);
64 [ + + ]: 46674 : if (size_ptr_it == size_to_free_chunk.end())
65 : : return nullptr;
66 : :
67 : : // Create the used-chunk, taking its space from the end of the free-chunk
68 : 46056 : const size_t size_remaining = size_ptr_it->first - size;
69 : 46056 : char* const free_chunk = static_cast<char*>(size_ptr_it->second);
70 : 46056 : auto allocated = chunks_used.emplace(free_chunk + size_remaining, size).first;
71 : 46056 : chunks_free_end.erase(free_chunk + size_ptr_it->first);
72 [ + + ]: 46056 : if (size_ptr_it->first == size) {
73 : : // whole chunk is used up
74 : 10460 : chunks_free.erase(size_ptr_it->second);
75 : : } else {
76 : : // still some memory left in the chunk
77 : 35596 : auto it_remaining = size_to_free_chunk.emplace(size_remaining, size_ptr_it->second);
78 : 35596 : chunks_free[size_ptr_it->second] = it_remaining;
79 : 35596 : chunks_free_end.emplace(free_chunk + size_remaining, it_remaining);
80 : : }
81 : 46056 : size_to_free_chunk.erase(size_ptr_it);
82 : :
83 : 46056 : return allocated->first;
84 : : }
85 : :
86 : 49431 : void Arena::free(void *ptr)
87 : : {
88 : : // Freeing the nullptr pointer is OK.
89 [ + + ]: 49431 : if (ptr == nullptr) {
90 : : return;
91 : : }
92 : :
93 : : // Remove chunk from used map
94 : 46058 : auto i = chunks_used.find(ptr);
95 [ + + ]: 46058 : if (i == chunks_used.end()) {
96 [ + - ]: 2 : throw std::runtime_error("Arena: invalid or double free");
97 : : }
98 : 46056 : auto freed = std::make_pair(static_cast<char*>(i->first), i->second);
99 : 46056 : chunks_used.erase(i);
100 : :
101 : : // coalesce freed with previous chunk
102 : 46056 : auto prev = chunks_free_end.find(freed.first);
103 [ + + ]: 46056 : if (prev != chunks_free_end.end()) {
104 : 31245 : freed.first -= prev->second->first;
105 : 31245 : freed.second += prev->second->first;
106 : 31245 : size_to_free_chunk.erase(prev->second);
107 : 31245 : chunks_free_end.erase(prev);
108 : : }
109 : :
110 : : // coalesce freed with chunk after freed
111 : 46056 : auto next = chunks_free.find(freed.first + freed.second);
112 [ + + ]: 46056 : if (next != chunks_free.end()) {
113 : 4351 : freed.second += next->second->first;
114 : 4351 : size_to_free_chunk.erase(next->second);
115 : 4351 : chunks_free.erase(next);
116 : : }
117 : :
118 : : // Add/set space with coalesced free chunk
119 : 46056 : auto it = size_to_free_chunk.emplace(freed.second, freed.first);
120 : 46056 : chunks_free[freed.first] = it;
121 : 46056 : chunks_free_end[freed.first + freed.second] = it;
122 : : }
123 : :
124 : 33 : Arena::Stats Arena::stats() const
125 : : {
126 : 33 : Arena::Stats r{ 0, 0, 0, chunks_used.size(), chunks_free.size() };
127 [ + + ]: 1075 : for (const auto& chunk: chunks_used)
128 : 1042 : r.used += chunk.second;
129 [ + + ]: 68 : for (const auto& chunk: chunks_free)
130 : 35 : r.free += chunk.second->first;
131 : 33 : r.total = r.used + r.free;
132 : 33 : return r;
133 : : }
134 : :
135 : : #ifdef ARENA_DEBUG
136 : : static void printchunk(void* base, size_t sz, bool used) {
137 : : std::cout <<
138 : : "0x" << std::hex << std::setw(16) << std::setfill('0') << base <<
139 : : " 0x" << std::hex << std::setw(16) << std::setfill('0') << sz <<
140 : : " 0x" << used << std::endl;
141 : : }
142 : : void Arena::walk() const
143 : : {
144 : : for (const auto& chunk: chunks_used)
145 : : printchunk(chunk.first, chunk.second, true);
146 : : std::cout << std::endl;
147 : : for (const auto& chunk: chunks_free)
148 : : printchunk(chunk.first, chunk.second->first, false);
149 : : std::cout << std::endl;
150 : : }
151 : : #endif
152 : :
153 : : /*******************************************************************************/
154 : : // Implementation: Win32LockedPageAllocator
155 : :
156 : : #ifdef WIN32
157 : : /** LockedPageAllocator specialized for Windows.
158 : : */
159 : : class Win32LockedPageAllocator: public LockedPageAllocator
160 : : {
161 : : public:
162 : : Win32LockedPageAllocator();
163 : : void* AllocateLocked(size_t len, bool *lockingSuccess) override;
164 : : void FreeLocked(void* addr, size_t len) override;
165 : : size_t GetLimit() override;
166 : : private:
167 : : size_t page_size;
168 : : };
169 : :
170 : : Win32LockedPageAllocator::Win32LockedPageAllocator()
171 : : {
172 : : // Determine system page size in bytes
173 : : SYSTEM_INFO sSysInfo;
174 : : GetSystemInfo(&sSysInfo);
175 : : page_size = sSysInfo.dwPageSize;
176 : : }
177 : : void *Win32LockedPageAllocator::AllocateLocked(size_t len, bool *lockingSuccess)
178 : : {
179 : : len = align_up(len, page_size);
180 : : void *addr = VirtualAlloc(nullptr, len, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
181 : : if (addr) {
182 : : // VirtualLock is used to attempt to keep keying material out of swap. Note
183 : : // that it does not provide this as a guarantee, but, in practice, memory
184 : : // that has been VirtualLock'd almost never gets written to the pagefile
185 : : // except in rare circumstances where memory is extremely low.
186 : : *lockingSuccess = VirtualLock(const_cast<void*>(addr), len) != 0;
187 : : }
188 : : return addr;
189 : : }
190 : : void Win32LockedPageAllocator::FreeLocked(void* addr, size_t len)
191 : : {
192 : : len = align_up(len, page_size);
193 : : memory_cleanse(addr, len);
194 : : VirtualUnlock(const_cast<void*>(addr), len);
195 : : }
196 : :
197 : : size_t Win32LockedPageAllocator::GetLimit()
198 : : {
199 : : size_t min, max;
200 : : if(GetProcessWorkingSetSize(GetCurrentProcess(), &min, &max) != 0) {
201 : : return min;
202 : : }
203 : : return std::numeric_limits<size_t>::max();
204 : : }
205 : : #endif
206 : :
207 : : /*******************************************************************************/
208 : : // Implementation: PosixLockedPageAllocator
209 : :
210 : : #ifndef WIN32
211 : : /** LockedPageAllocator specialized for OSes that don't try to be
212 : : * special snowflakes.
213 : : */
214 : : class PosixLockedPageAllocator: public LockedPageAllocator
215 : : {
216 : : public:
217 : : PosixLockedPageAllocator();
218 : : void* AllocateLocked(size_t len, bool *lockingSuccess) override;
219 : : void FreeLocked(void* addr, size_t len) override;
220 : : size_t GetLimit() override;
221 : : private:
222 : : size_t page_size;
223 : : };
224 : :
225 : 164 : PosixLockedPageAllocator::PosixLockedPageAllocator()
226 : : {
227 : : // Determine system page size in bytes
228 : : #if defined(PAGESIZE) // defined in limits.h
229 : : page_size = PAGESIZE;
230 : : #else // assume some POSIX OS
231 : 164 : page_size = sysconf(_SC_PAGESIZE);
232 : : #endif
233 : 164 : }
234 : :
235 : 164 : void *PosixLockedPageAllocator::AllocateLocked(size_t len, bool *lockingSuccess)
236 : : {
237 : 164 : void *addr;
238 : 164 : len = align_up(len, page_size);
239 : 164 : addr = mmap(nullptr, len, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
240 [ + - ]: 164 : if (addr == MAP_FAILED) {
241 : : return nullptr;
242 : : }
243 [ + - ]: 164 : if (addr) {
244 : 164 : *lockingSuccess = mlock(addr, len) == 0;
245 : : #if defined(MADV_DONTDUMP) // Linux
246 : 164 : madvise(addr, len, MADV_DONTDUMP);
247 : : #elif defined(MADV_NOCORE) // FreeBSD
248 : : madvise(addr, len, MADV_NOCORE);
249 : : #endif
250 : : }
251 : : return addr;
252 : : }
253 : 164 : void PosixLockedPageAllocator::FreeLocked(void* addr, size_t len)
254 : : {
255 : 164 : len = align_up(len, page_size);
256 : 164 : memory_cleanse(addr, len);
257 : 164 : munlock(addr, len);
258 : 164 : munmap(addr, len);
259 : 164 : }
260 : 164 : size_t PosixLockedPageAllocator::GetLimit()
261 : : {
262 : : #ifdef RLIMIT_MEMLOCK
263 : 164 : struct rlimit rlim;
264 [ + - ]: 164 : if (getrlimit(RLIMIT_MEMLOCK, &rlim) == 0) {
265 [ + - ]: 164 : if (rlim.rlim_cur != RLIM_INFINITY) {
266 : 164 : return rlim.rlim_cur;
267 : : }
268 : : }
269 : : #endif
270 : : return std::numeric_limits<size_t>::max();
271 : : }
272 : : #endif
273 : :
274 : : /*******************************************************************************/
275 : : // Implementation: LockedPool
276 : :
277 : 165 : LockedPool::LockedPool(std::unique_ptr<LockedPageAllocator> allocator_in, LockingFailed_Callback lf_cb_in)
278 : 165 : : allocator(std::move(allocator_in)), lf_cb(lf_cb_in)
279 : : {
280 : 165 : }
281 : :
282 : 165 : LockedPool::~LockedPool() = default;
283 : :
284 : 40825 : void* LockedPool::alloc(size_t size)
285 : : {
286 : 40825 : std::lock_guard<std::mutex> lock(mutex);
287 : :
288 : : // Don't handle impossible sizes
289 [ + + ]: 40825 : if (size == 0 || size > ARENA_SIZE)
290 : : return nullptr;
291 : :
292 : : // Try allocating from each current arena
293 [ + + ]: 40832 : for (auto &arena: arenas) {
294 [ + - ]: 40664 : void *addr = arena.alloc(size);
295 [ + + ]: 40664 : if (addr) {
296 : : return addr;
297 : : }
298 : : }
299 : : // If that fails, create a new one
300 [ + - + + ]: 168 : if (new_arena(ARENA_SIZE, ARENA_ALIGN)) {
301 [ + - ]: 167 : return arenas.back().alloc(size);
302 : : }
303 : : return nullptr;
304 : 40825 : }
305 : :
306 : 40823 : void LockedPool::free(void *ptr)
307 : : {
308 : 40823 : std::lock_guard<std::mutex> lock(mutex);
309 : : // TODO we can do better than this linear search by keeping a map of arena
310 : : // extents to arena, and looking up the address.
311 [ + - ]: 40829 : for (auto &arena: arenas) {
312 [ + + ]: 40829 : if (arena.addressInArena(ptr)) {
313 [ + + ]: 40823 : arena.free(ptr);
314 : 40822 : return;
315 : : }
316 : : }
317 [ # # ]: 0 : throw std::runtime_error("LockedPool: invalid address not pointing to any arena");
318 : 40822 : }
319 : :
320 : 13 : LockedPool::Stats LockedPool::stats() const
321 : : {
322 : 13 : std::lock_guard<std::mutex> lock(mutex);
323 : 13 : LockedPool::Stats r{0, 0, 0, cumulative_bytes_locked, 0, 0};
324 [ + + ]: 26 : for (const auto &arena: arenas) {
325 [ + - ]: 13 : Arena::Stats i = arena.stats();
326 : 13 : r.used += i.used;
327 : 13 : r.free += i.free;
328 : 13 : r.total += i.total;
329 : 13 : r.chunks_used += i.chunks_used;
330 : 13 : r.chunks_free += i.chunks_free;
331 : : }
332 : 13 : return r;
333 : 13 : }
334 : :
335 : 168 : bool LockedPool::new_arena(size_t size, size_t align)
336 : : {
337 : 168 : bool locked;
338 : : // If this is the first arena, handle this specially: Cap the upper size
339 : : // by the process limit. This makes sure that the first arena will at least
340 : : // be locked. An exception to this is if the process limit is 0:
341 : : // in this case no memory can be locked at all so we'll skip past this logic.
342 [ + + ]: 168 : if (arenas.empty()) {
343 : 165 : size_t limit = allocator->GetLimit();
344 [ + - ]: 165 : if (limit > 0) {
345 [ + - ]: 330 : size = std::min(size, limit);
346 : : }
347 : : }
348 : 168 : void *addr = allocator->AllocateLocked(size, &locked);
349 [ + + ]: 168 : if (!addr) {
350 : : return false;
351 : : }
352 [ + + ]: 167 : if (locked) {
353 : 165 : cumulative_bytes_locked += size;
354 [ - + ]: 2 : } else if (lf_cb) { // Call the locking-failed callback if locking failed
355 [ # # ]: 0 : if (!lf_cb()) { // If the callback returns false, free the memory and fail, otherwise consider the user warned and proceed.
356 : 0 : allocator->FreeLocked(addr, size);
357 : 0 : return false;
358 : : }
359 : : }
360 : 167 : arenas.emplace_back(allocator.get(), addr, size, align);
361 : 167 : return true;
362 : : }
363 : :
364 : 167 : LockedPool::LockedPageArena::LockedPageArena(LockedPageAllocator *allocator_in, void *base_in, size_t size_in, size_t align_in):
365 : 167 : Arena(base_in, size_in, align_in), base(base_in), size(size_in), allocator(allocator_in)
366 : : {
367 : 167 : }
368 : 167 : LockedPool::LockedPageArena::~LockedPageArena()
369 : : {
370 : 167 : allocator->FreeLocked(base, size);
371 : 167 : }
372 : :
373 : : /*******************************************************************************/
374 : : // Implementation: LockedPoolManager
375 : : //
376 : 164 : LockedPoolManager::LockedPoolManager(std::unique_ptr<LockedPageAllocator> allocator_in):
377 [ + - ]: 164 : LockedPool(std::move(allocator_in), &LockedPoolManager::LockingFailed)
378 : : {
379 : 164 : }
380 : :
381 : 0 : bool LockedPoolManager::LockingFailed()
382 : : {
383 : : // TODO: log something but how? without including util.h
384 : 0 : return true;
385 : : }
386 : :
387 : 164 : void LockedPoolManager::CreateInstance()
388 : : {
389 : : // Using a local static instance guarantees that the object is initialized
390 : : // when it's first needed and also deinitialized after all objects that use
391 : : // it are done with it. I can think of one unlikely scenario where we may
392 : : // have a static deinitialization order/problem, but the check in
393 : : // LockedPoolManagerBase's destructor helps us detect if that ever happens.
394 : : #ifdef WIN32
395 : : std::unique_ptr<LockedPageAllocator> allocator(new Win32LockedPageAllocator());
396 : : #else
397 [ + - + - ]: 164 : std::unique_ptr<LockedPageAllocator> allocator(new PosixLockedPageAllocator());
398 : : #endif
399 [ + - + - : 164 : static LockedPoolManager instance(std::move(allocator));
+ - ]
400 : 164 : LockedPoolManager::_instance = &instance;
401 : 164 : }
|
