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