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