src/allocators.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2013 The Bitcoin developers
   3 // Distributed under the MIT/X11 software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #ifndef BITCOIN_ALLOCATORS_H
   7 #define BITCOIN_ALLOCATORS_H
   8
   9 #include <map>
  10 #include <string>
  11 #include <string.h>
  12 #include <vector>
  13
  14 #include <boost/thread/mutex.hpp>
  15 #include <boost/thread/once.hpp>
  16
  17 #include <openssl/crypto.h> // for OPENSSL_cleanse()
  18
  19 /**
  20  * Thread-safe class to keep track of locked (ie, non-swappable) memory pages.
  21  *
  22  * Memory locks do not stack, that is, pages which have been locked several times by calls to mlock()
  23  * will be unlocked by a single call to munlock(). This can result in keying material ending up in swap when
  24  * those functions are used naively. This class simulates stacking memory locks by keeping a counter per page.
  25  *
  26  * @note By using a map from each page base address to lock count, this class is optimized for
  27  * small objects that span up to a few pages, mostly smaller than a page. To support large allocations,
  28  * something like an interval tree would be the preferred data structure.
  29  */
  30 template <class Locker>
  31 class LockedPageManagerBase
  32 {
  33 public:
  34     LockedPageManagerBase(size_t page_size) : page_size(page_size)
  35     {
  36         // Determine bitmask for extracting page from address
  37         assert(!(page_size & (page_size - 1))); // size must be power of two
  38         page_mask = ~(page_size - 1);
  39     }
  40
  41     ~LockedPageManagerBase()
  42     {
  43         assert(this->GetLockedPageCount() == 0);
  44     }
  45
  46
  47     // For all pages in affected range, increase lock count
  48     void LockRange(void* p, size_t size)
  49     {
  50         boost::mutex::scoped_lock lock(mutex);
  51         if (!size)
  52             return;
  53         const size_t base_addr = reinterpret_cast<size_t>(p);
  54         const size_t start_page = base_addr & page_mask;
  55         const size_t end_page = (base_addr + size - 1) & page_mask;
  56         for (size_t page = start_page; page <= end_page; page += page_size) {
  57             Histogram::iterator it = histogram.find(page);
  58             if (it == histogram.end()) // Newly locked page
  59             {
  60                 locker.Lock(reinterpret_cast<void*>(page), page_size);
  61                 histogram.insert(std::make_pair(page, 1));
  62             } else // Page was already locked; increase counter
  63             {
  64                 it->second += 1;
  65             }
  66         }
  67     }
  68
  69     // For all pages in affected range, decrease lock count
  70     void UnlockRange(void* p, size_t size)
  71     {
  72         boost::mutex::scoped_lock lock(mutex);
  73         if (!size)
  74             return;
  75         const size_t base_addr = reinterpret_cast<size_t>(p);
  76         const size_t start_page = base_addr & page_mask;
  77         const size_t end_page = (base_addr + size - 1) & page_mask;
  78         for (size_t page = start_page; page <= end_page; page += page_size) {
  79             Histogram::iterator it = histogram.find(page);
  80             assert(it != histogram.end()); // Cannot unlock an area that was not locked
  81             // Decrease counter for page, when it is zero, the page will be unlocked
  82             it->second -= 1;
  83             if (it->second == 0) // Nothing on the page anymore that keeps it locked
  84             {
  85                 // Unlock page and remove the count from histogram
  86                 locker.Unlock(reinterpret_cast<void*>(page), page_size);
  87                 histogram.erase(it);
  88             }
  89         }
  90     }
  91
  92     // Get number of locked pages for diagnostics
  93     int GetLockedPageCount()
  94     {
  95         boost::mutex::scoped_lock lock(mutex);
  96         return histogram.size();
  97     }
  98
  99 private:
 100     Locker locker;
 101     boost::mutex mutex;
 102     size_t page_size, page_mask;
 103     // map of page base address to lock count
 104     typedef std::map<size_t, int> Histogram;
 105     Histogram histogram;
 106 };
 107
 108
 109 /**
 110  * OS-dependent memory page locking/unlocking.
 111  * Defined as policy class to make stubbing for test possible.
 112  */
 113 class MemoryPageLocker
 114 {
 115 public:
 116     /** Lock memory pages.
 117      * addr and len must be a multiple of the system page size
 118      */
 119     bool Lock(const void* addr, size_t len);
 120     /** Unlock memory pages.
 121      * addr and len must be a multiple of the system page size
 122      */
 123     bool Unlock(const void* addr, size_t len);
 124 };
 125
 126 /**
 127  * Singleton class to keep track of locked (ie, non-swappable) memory pages, for use in
 128  * std::allocator templates.
 129  *
 130  * Some implementations of the STL allocate memory in some constructors (i.e., see
 131  * MSVC's vector<T> implementation where it allocates 1 byte of memory in the allocator.)
 132  * Due to the unpredictable order of static initializers, we have to make sure the
 133  * LockedPageManager instance exists before any other STL-based objects that use
 134  * secure_allocator are created. So instead of having LockedPageManager also be
 135  * static-initialized, it is created on demand.
 136  */
 137 class LockedPageManager : public LockedPageManagerBase<MemoryPageLocker>
 138 {
 139 public:
 140     static LockedPageManager& Instance()
 141     {
 142         boost::call_once(LockedPageManager::CreateInstance, LockedPageManager::init_flag);
 143         return *LockedPageManager::_instance;
 144     }
 145
 146 private:
 147     LockedPageManager();
 148
 149     static void CreateInstance()
 150     {
 151         // Using a local static instance guarantees that the object is initialized
 152         // when it's first needed and also deinitialized after all objects that use
 153         // it are done with it.  I can think of one unlikely scenario where we may
 154         // have a static deinitialization order/problem, but the check in
 155         // LockedPageManagerBase's destructor helps us detect if that ever happens.
 156         static LockedPageManager instance;
 157         LockedPageManager::_instance = &instance;
 158     }
 159
 160     static LockedPageManager* _instance;
 161     static boost::once_flag init_flag;
 162 };
 163
 164 //
 165 // Functions for directly locking/unlocking memory objects.
 166 // Intended for non-dynamically allocated structures.
 167 //
 168 template <typename T>
 169 void LockObject(const T& t)
 170 {
 171     LockedPageManager::Instance().LockRange((void*)(&t), sizeof(T));
 172 }
 173
 174 template <typename T>
 175 void UnlockObject(const T& t)
 176 {
 177     OPENSSL_cleanse((void*)(&t), sizeof(T));
 178     LockedPageManager::Instance().UnlockRange((void*)(&t), sizeof(T));
 179 }
 180
 181 //
 182 // Allocator that locks its contents from being paged
 183 // out of memory and clears its contents before deletion.
 184 //
 185 template <typename T>
 186 struct secure_allocator : public std::allocator<T> {
 187     // MSVC8 default copy constructor is broken
 188     typedef std::allocator<T> base;
 189     typedef typename base::size_type size_type;
 190     typedef typename base::difference_type difference_type;
 191     typedef typename base::pointer pointer;
 192     typedef typename base::const_pointer const_pointer;
 193     typedef typename base::reference reference;
 194     typedef typename base::const_reference const_reference;
 195     typedef typename base::value_type value_type;
 196     secure_allocator() throw() {}
 197     secure_allocator(const secure_allocator& a) throw() : base(a) {}
 198     template <typename U>
 199     secure_allocator(const secure_allocator<U>& a) throw() : base(a)
 200     {
 201     }
 202     ~secure_allocator() throw() {}
 203     template <typename _Other>
 204     struct rebind {
 205         typedef secure_allocator<_Other> other;
 206     };
 207
 208     T* allocate(std::size_t n, const void* hint = 0)
 209     {
 210         T* p;
 211         p = std::allocator<T>::allocate(n, hint);
 212         if (p != NULL)
 213             LockedPageManager::Instance().LockRange(p, sizeof(T) * n);
 214         return p;
 215     }
 216
 217     void deallocate(T* p, std::size_t n)
 218     {
 219         if (p != NULL) {
 220             OPENSSL_cleanse(p, sizeof(T) * n);
 221             LockedPageManager::Instance().UnlockRange(p, sizeof(T) * n);
 222         }
 223         std::allocator<T>::deallocate(p, n);
 224     }
 225 };
 226
 227
 228 //
 229 // Allocator that clears its contents before deletion.
 230 //
 231 template <typename T>
 232 struct zero_after_free_allocator : public std::allocator<T> {
 233     // MSVC8 default copy constructor is broken
 234     typedef std::allocator<T> base;
 235     typedef typename base::size_type size_type;
 236     typedef typename base::difference_type difference_type;
 237     typedef typename base::pointer pointer;
 238     typedef typename base::const_pointer const_pointer;
 239     typedef typename base::reference reference;
 240     typedef typename base::const_reference const_reference;
 241     typedef typename base::value_type value_type;
 242     zero_after_free_allocator() throw() {}
 243     zero_after_free_allocator(const zero_after_free_allocator& a) throw() : base(a) {}
 244     template <typename U>
 245     zero_after_free_allocator(const zero_after_free_allocator<U>& a) throw() : base(a)
 246     {
 247     }
 248     ~zero_after_free_allocator() throw() {}
 249     template <typename _Other>
 250     struct rebind {
 251         typedef zero_after_free_allocator<_Other> other;
 252     };
 253
 254     void deallocate(T* p, std::size_t n)
 255     {
 256         if (p != NULL)
 257             OPENSSL_cleanse(p, sizeof(T) * n);
 258         std::allocator<T>::deallocate(p, n);
 259     }
 260 };
 261
 262 // This is exactly like std::string, but with a custom allocator.
 263 typedef std::basic_string<char, std::char_traits<char>, secure_allocator<char> > SecureString;
 264
 265 // Byte-vector that clears its contents before deletion.
 266 typedef std::vector<char, zero_after_free_allocator<char> > CSerializeData;
 267
 268 #endif // BITCOIN_ALLOCATORS_H