Botan 3.14.1
Crypto and TLS for C&
mem_pool.cpp
Go to the documentation of this file.
1/*
2* (C) 2018,2019 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/mem_pool.h>
8
9#include <botan/mem_ops.h>
10#include <botan/internal/target_info.h>
11#include <algorithm>
12#include <exception>
13#include <optional>
14
15#if defined(BOTAN_HAS_VALGRIND) || defined(BOTAN_ENABLE_DEBUG_ASSERTS)
16 /**
17 * @brief Prohibits access to unused memory pages in Botan's memory pool
18 *
19 * If BOTAN_MEM_POOL_USE_MMU_PROTECTIONS is defined, the Memory_Pool
20 * class used for mlock'ed memory will use OS calls to set page
21 * permissions so as to prohibit access to pages on the free list, then
22 * enable read/write access when the page is set to be used. This will
23 * turn (some) use after free bugs into a crash.
24 *
25 * The additional syscalls have a substantial performance impact, which
26 * is why this option is not enabled by default. It is used when built for
27 * running in valgrind or debug assertions are enabled.
28 */
29 #define BOTAN_MEM_POOL_USE_MMU_PROTECTIONS
30#endif
31
32#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS) && defined(BOTAN_HAS_OS_UTILS)
33 #include <botan/internal/os_utils.h>
34#endif
35
36namespace Botan {
37
38/*
39* Memory pool theory of operation
40*
41* This allocator is not useful for general purpose but works well within the
42* context of allocating cryptographic keys. It makes several assumptions which
43* don't work for implementing malloc but simplify and speed up the implementation:
44*
45* - There is some set of pages, which cannot be expanded later. These are pages
46* which were allocated, mlocked and passed to the Memory_Pool constructor.
47*
48* - The allocator is allowed to return null anytime it feels like not servicing
49* a request, in which case the request will be sent to calloc instead. In
50* particular, requests which are too small or too large are rejected.
51*
52* - Most allocations are powers of 2, the remainder are usually a multiple of 8
53*
54* - Free requests include the size of the allocation, so there is no need to
55* track this within the pool.
56*
57* - Alignment is important to the caller. For this allocator, any allocation of
58* size N is aligned evenly at N bytes.
59*
60* Initially each page is in the free page list. Each page is used for just one
61* size of allocation, with requests bucketed into a small number of common
62* sizes. If the allocation would be too big or too small it is rejected by the pool.
63*
64* The free list is maintained by a bitmap, one per page/Bucket. Since each
65* Bucket only maintains objects of a single size, each bit set or clear
66* indicates the status of one object.
67*
68* An allocation walks the list of buckets and asks each in turn if there is
69* space. If a Bucket does not have any space, it sets a boolean flag m_is_full
70* so that it does not need to rescan when asked again. The flag is cleared on
71* first free from that bucket. If no bucket has space, but there are some free
72* pages left, a free page is claimed as a new Bucket for that size. In this case
73* it is pushed to the front of the list so it is first in line to service new
74* requests.
75*
76* A deallocation also walks the list of buckets for the size and asks each
77* Bucket in turn if it recognizes the pointer. When a Bucket becomes empty as a
78* result of a deallocation, it is recycled back into the free pool. When this
79* happens, the Buckets page goes to the end of the free list. All pages on the
80* free list are marked in the MMU as noaccess, so anything touching them will
81* immediately crash. They are only marked R/W once placed into a new bucket.
82* Making the free list FIFO maximizes the time between the last free of a bucket
83* and that page being writable again, maximizing chances of crashing after a
84* use-after-free.
85*
86* Future work
87* -------------
88*
89* The allocator is protected by a global lock. It would be good to break this
90* up, since almost all of the work can actually be done in parallel especially
91* when allocating objects of different sizes (which can't possibly share a
92* bucket).
93*
94* It may be worthwhile to optimize deallocation by storing the Buckets in order
95* (by pointer value) which would allow binary search to find the owning bucket.
96*
97* A useful addition would be to randomize the allocations. Memory_Pool would be
98* changed to receive also a RandomNumberGenerator& object (presumably the system
99* RNG, or maybe a ChaCha_RNG seeded with system RNG). Then the bucket to use and
100* the offset within the bucket would be chosen randomly, instead of using first fit.
101*
102* Right now we don't make any provision for threading, so if two threads both
103* allocate 32 byte values one after the other, the two allocations will likely
104* share a cache line. Ensuring that distinct threads will (tend to) use distinct
105* buckets would reduce this.
106*
107* Supporting a realloc-style API may be useful.
108*/
109
110namespace {
111
112size_t choose_bucket(size_t n) {
113 constexpr size_t MINIMUM_ALLOCATION = 16;
114 constexpr size_t MAXIMUM_ALLOCATION = 256;
115
116 if(n < MINIMUM_ALLOCATION || n > MAXIMUM_ALLOCATION) {
117 return 0;
118 }
119
120 // Need to tune these
121
122 constexpr size_t buckets[] = {
123 16,
124 24,
125 32,
126 48,
127 64,
128 80,
129 96,
130 112,
131 128,
132 160,
133 192,
134 256,
135 0,
136 };
137
138 for(size_t i = 0; buckets[i] != 0; ++i) {
139 if(n <= buckets[i]) {
140 return buckets[i];
141 }
142 }
143
144 return 0;
145}
146
147inline bool ptr_in_pool(const void* pool_ptr, size_t poolsize, const void* buf_ptr, size_t bufsize) {
148 const uintptr_t pool = reinterpret_cast<uintptr_t>(pool_ptr);
149 const uintptr_t buf = reinterpret_cast<uintptr_t>(buf_ptr);
150 return (buf >= pool) && (buf + bufsize <= pool + poolsize);
151}
152
153// return index of first set bit
154template <typename T>
155size_t find_set_bit(T b) {
156 size_t s = 8 * sizeof(T) / 2;
157 size_t bit = 0;
158
159 // In this context we don't need to be const-time
160 while(s > 0) {
161 const T mask = (static_cast<T>(1) << s) - 1;
162 if((b & mask) == 0) {
163 bit += s;
164 b >>= s;
165 }
166 s /= 2;
167 }
168
169 return bit;
170}
171
172class BitMap final {
173 public:
174 explicit BitMap(size_t bits) : m_len(bits) {
175 m_bits.resize((bits + BITMASK_BITS - 1) / BITMASK_BITS);
176
177 if(bits % BITMASK_BITS != 0) {
178 m_last_mask = (static_cast<bitmask_type>(1) << (bits % BITMASK_BITS)) - 1;
179 }
180 }
181
182 std::optional<size_t> find_free();
183
184 void free(size_t bit) {
185 BOTAN_ASSERT_NOMSG(bit < m_len);
186 const size_t w = bit / BITMASK_BITS;
187 BOTAN_ASSERT_NOMSG(w < m_bits.size());
188 const bitmask_type mask = static_cast<bitmask_type>(1) << (bit % BITMASK_BITS);
189 m_bits[w] = m_bits[w] & (~mask);
190 }
191
192 bool empty() const {
193 for(const auto bitset : m_bits) {
194 if(bitset != 0) {
195 return false;
196 }
197 }
198
199 return true;
200 }
201
202 private:
203#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
204 using bitmask_type = uint8_t;
205#else
206 using bitmask_type = word;
207#endif
208
209 static const size_t BITMASK_BITS = sizeof(bitmask_type) * 8;
210
211 size_t m_len;
212 // MSVC warns if the cast isn't there, clang-tidy warns that the cast is pointless
213 bitmask_type m_main_mask = static_cast<bitmask_type>(~0); // NOLINT(bugprone-misplaced-widening-cast)
214 bitmask_type m_last_mask = static_cast<bitmask_type>(~0); // NOLINT(bugprone-misplaced-widening-cast)
215 std::vector<bitmask_type> m_bits;
216};
217
218std::optional<size_t> BitMap::find_free() {
219 for(size_t i = 0; i != m_bits.size(); ++i) {
220 const bitmask_type mask = (i == m_bits.size() - 1) ? m_last_mask : m_main_mask;
221 if((m_bits[i] & mask) != mask) {
222 const size_t free_bit = find_set_bit(~m_bits[i]);
223 const bitmask_type bmask = static_cast<bitmask_type>(1) << (free_bit % BITMASK_BITS);
224 BOTAN_ASSERT_NOMSG((m_bits[i] & bmask) == 0);
225 m_bits[i] |= bmask;
226 return BITMASK_BITS * i + free_bit;
227 }
228 }
229
230 return {};
231}
232
233} // namespace
234
235class Bucket final {
236 public:
237 Bucket(uint8_t* mem, size_t mem_size, size_t item_size) :
238 m_item_size(item_size),
239 m_page_size(mem_size),
240 m_range(mem),
241 m_bitmap(mem_size / item_size),
242 m_is_full(false) {}
243
244 uint8_t* alloc() {
245 if(m_is_full) {
246 // I know I am full
247 return nullptr;
248 }
249
250 auto offset = m_bitmap.find_free();
251 if(!offset) {
252 // I just found out I am full
253 m_is_full = true;
254 return nullptr;
255 } else {
256 BOTAN_ASSERT(*offset * m_item_size < m_page_size, "Offset is in range");
257 return m_range + m_item_size * (*offset);
258 }
259 }
260
261 bool free(void* p) {
262 if(!in_this_bucket(p)) {
263 return false;
264 }
265
266 /*
267 Zero also any trailing bytes, which should not have been written to,
268 but maybe the user was bad and wrote past the end.
269 */
270 std::memset(p, 0, m_item_size);
271
272 const size_t offset = (reinterpret_cast<uintptr_t>(p) - reinterpret_cast<uintptr_t>(m_range)) / m_item_size;
273
274 m_bitmap.free(offset);
275 m_is_full = false;
276
277 return true;
278 }
279
280 bool in_this_bucket(void* p) const { return ptr_in_pool(m_range, m_page_size, p, m_item_size); }
281
282 bool empty() const { return m_bitmap.empty(); }
283
284 uint8_t* ptr() const { return m_range; }
285
286 private:
287 size_t m_item_size;
288 size_t m_page_size;
289 uint8_t* m_range;
290 BitMap m_bitmap;
291 bool m_is_full;
292};
293
294Memory_Pool::Memory_Pool(const std::vector<void*>& pages, size_t page_size) : m_page_size(page_size) {
295 for(auto* page : pages) {
296 const uintptr_t p = reinterpret_cast<uintptr_t>(page);
297
298 m_min_page_ptr = std::min(p, m_min_page_ptr);
299 m_max_page_ptr = std::max(p, m_max_page_ptr);
300
301 clear_bytes(page, m_page_size);
302#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
304#endif
305 m_free_pages.push_back(static_cast<uint8_t*>(page));
306 }
307
308 /*
309 Right now this points to the start of the last page, adjust it to instead
310 point to the first byte of the following page
311 */
312 m_max_page_ptr += page_size;
313}
314
315Memory_Pool::~Memory_Pool() noexcept // NOLINT(*-use-equals-default)
316{
317#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
318 for(size_t i = 0; i != m_free_pages.size(); ++i) {
319 OS::page_allow_access(m_free_pages[i]);
320 }
321#endif
322}
323
324void* Memory_Pool::allocate(size_t n) {
325 if(n > m_page_size) {
326 return nullptr;
327 }
328
329 const size_t n_bucket = choose_bucket(n);
330
331 if(n_bucket > 0) {
332 const lock_guard_type<mutex_type> lock(m_mutex);
333
334 std::deque<Bucket>& buckets = m_buckets_for[n_bucket];
335
336 /*
337 It would be optimal to pick the bucket with the most usage,
338 since a bucket with say 1 item allocated out of it has a high
339 chance of becoming later freed and then the whole page can be
340 recycled.
341 */
342 for(auto& bucket : buckets) {
343 // NOLINTNEXTLINE(*-const-correctness) bug in clang-tidy
344 if(uint8_t* p = bucket.alloc()) {
345 return p;
346 }
347
348 // If the bucket is full, maybe move it to the end of the list?
349 // Otoh bucket search should be very fast
350 }
351
352 if(!m_free_pages.empty()) {
353 uint8_t* ptr = m_free_pages[0];
354 m_free_pages.pop_front();
355#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
357#endif
358 buckets.push_front(Bucket(ptr, m_page_size, n_bucket));
359 // NOLINTNEXTLINE(*-const-correctness) bug in clang-tidy
360 void* p = buckets[0].alloc();
361 BOTAN_ASSERT_NOMSG(p != nullptr);
362 return p;
363 }
364 }
365
366 // out of room
367 return nullptr;
368}
369
370bool Memory_Pool::deallocate(void* p, size_t len) noexcept {
371 // Do a fast range check first, before taking the lock
372 const uintptr_t p_val = reinterpret_cast<uintptr_t>(p);
373 if(p_val < m_min_page_ptr || p_val > m_max_page_ptr) {
374 return false;
375 }
376
377 const size_t n_bucket = choose_bucket(len);
378
379 if(n_bucket != 0) {
380 try {
381 const lock_guard_type<mutex_type> lock(m_mutex);
382
383 std::deque<Bucket>& buckets = m_buckets_for[n_bucket];
384
385 for(size_t i = 0; i != buckets.size(); ++i) {
386 Bucket& bucket = buckets[i];
387 if(bucket.free(p)) {
388 if(bucket.empty()) {
389#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
390 OS::page_prohibit_access(bucket.ptr());
391#endif
392 m_free_pages.push_back(bucket.ptr());
393
394 if(i != buckets.size() - 1) {
395 std::swap(buckets.back(), buckets[i]);
396 }
397 buckets.pop_back();
398 }
399 return true;
400 }
401 }
402 } catch(...) {
403 /*
404 * The only exception throws that can occur in the above code are from
405 * either the STL or BOTAN_ASSERT failures. In either case, such an
406 * error indicates a logic error or data corruption in the memory
407 * allocator such that it is no longer safe to continue executing.
408 *
409 * Since this function is noexcept, simply letting the exception escape
410 * is sufficient for terminate to be called. However in this scenario
411 * it is implementation defined if any stack unwinding is performed.
412 * Since stack unwinding could cause further memory deallocations this
413 * could result in further corruption in this allocator state. To prevent
414 * this, call terminate directly.
415 */
416 std::terminate();
417 }
418 }
419
420 return false;
421}
422
423} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
Memory_Pool(const std::vector< void * > &pages, size_t page_size)
Definition mem_pool.cpp:294
~Memory_Pool() noexcept
Definition mem_pool.cpp:315
bool deallocate(void *p, size_t size) noexcept
Definition mem_pool.cpp:370
void * allocate(size_t size)
Definition mem_pool.cpp:324
void page_allow_access(void *page)
Definition os_utils.cpp:649
void page_prohibit_access(void *page)
Definition os_utils.cpp:663
secure_vector< T > lock(const std::vector< T > &in)
Definition secmem.h:145
constexpr void clear_bytes(void *ptr, size_t bytes)
Definition mem_ops.h:101
lock_guard< T > lock_guard_type
Definition mutex.h:58
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131