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