7#include <botan/internal/mem_pool.h>
8#include <botan/mem_ops.h>
11#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
12 #include <botan/internal/os_utils.h>
91size_t choose_bucket(
size_t n)
93 const size_t MINIMUM_ALLOCATION = 16;
94 const size_t MAXIMUM_ALLOCATION = 256;
96 if(n < MINIMUM_ALLOCATION || n > MAXIMUM_ALLOCATION)
101 const size_t buckets[] = {
102 16, 24, 32, 48, 64, 80, 96, 112, 128, 160, 192, 256, 0,
105 for(
size_t i = 0; buckets[i]; ++i)
116inline bool ptr_in_pool(
const void* pool_ptr,
size_t poolsize,
117 const void* buf_ptr,
size_t bufsize)
119 const uintptr_t pool =
reinterpret_cast<uintptr_t
>(pool_ptr);
120 const uintptr_t buf =
reinterpret_cast<uintptr_t
>(buf_ptr);
121 return (buf >= pool) && (buf + bufsize <= pool + poolsize);
126size_t find_set_bit(
T b)
128 size_t s = 8*
sizeof(
T) / 2;
134 const T mask = (
static_cast<T>(1) << s) - 1;
149 BitMap(
size_t bits) : m_len(bits)
151 m_bits.resize((bits + BITMASK_BITS - 1) / BITMASK_BITS);
152 m_main_mask =
static_cast<bitmask_type
>(~0);
153 m_last_mask = m_main_mask;
155 if(bits % BITMASK_BITS != 0)
156 m_last_mask = (
static_cast<bitmask_type
>(1) << (bits % BITMASK_BITS)) - 1;
159 bool find_free(
size_t* bit);
161 void free(
size_t bit)
164 const size_t w = bit / BITMASK_BITS;
166 const bitmask_type mask =
static_cast<bitmask_type
>(1) << (bit % BITMASK_BITS);
167 m_bits[w] = m_bits[w] & (~mask);
172 for(
size_t i = 0; i != m_bits.size(); ++i)
184#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
185 typedef uint8_t bitmask_type;
186 enum { BITMASK_BITS = 8 };
188 typedef word bitmask_type;
189 enum { BITMASK_BITS = BOTAN_MP_WORD_BITS };
193 bitmask_type m_main_mask;
194 bitmask_type m_last_mask;
195 std::vector<bitmask_type> m_bits;
198bool BitMap::find_free(
size_t* bit)
200 for(
size_t i = 0; i != m_bits.size(); ++i)
202 const bitmask_type mask = (i == m_bits.size() - 1) ? m_last_mask : m_main_mask;
203 if((m_bits[i] & mask) != mask)
205 size_t free_bit = find_set_bit(~m_bits[i]);
206 const bitmask_type bmask =
static_cast<bitmask_type
>(1) << (free_bit % BITMASK_BITS);
209 *bit = BITMASK_BITS*i + free_bit;
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),
226 m_bitmap(mem_size / item_size),
240 if(!m_bitmap.find_free(&offset))
247 BOTAN_ASSERT(offset * m_item_size < m_page_size,
"Offset is in range");
248 return m_range + m_item_size*offset;
253 if(!in_this_bucket(p))
260 std::memset(p, 0, m_item_size);
262 const size_t offset = (
reinterpret_cast<uintptr_t
>(p) -
reinterpret_cast<uintptr_t
>(m_range)) / m_item_size;
264 m_bitmap.free(offset);
270 bool in_this_bucket(
void* p)
const
272 return ptr_in_pool(m_range, m_page_size, p, m_item_size);
277 return m_bitmap.empty();
294 m_page_size(page_size)
296 m_min_page_ptr = ~static_cast<uintptr_t>(0);
299 for(
size_t i = 0; i != pages.size(); ++i)
301 const uintptr_t p =
reinterpret_cast<uintptr_t
>(pages[i]);
303 m_min_page_ptr = std::min(p, m_min_page_ptr);
304 m_max_page_ptr = std::max(p, m_max_page_ptr);
307#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
310 m_free_pages.push_back(
static_cast<uint8_t*
>(pages[i]));
317 m_max_page_ptr += page_size;
322#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
323 for(
size_t i = 0; i != m_free_pages.size(); ++i)
335 const size_t n_bucket = choose_bucket(n);
341 std::deque<Bucket>& buckets = m_buckets_for[n_bucket];
349 for(
auto& bucket : buckets)
351 if(uint8_t* p = bucket.alloc())
358 if(m_free_pages.size() > 0)
360 uint8_t* ptr = m_free_pages[0];
361 m_free_pages.pop_front();
362#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
365 buckets.push_front(Bucket(ptr, m_page_size, n_bucket));
366 void* p = buckets[0].alloc();
379 const uintptr_t p_val =
reinterpret_cast<uintptr_t
>(p);
380 if(p_val < m_min_page_ptr || p_val > m_max_page_ptr)
383 const size_t n_bucket = choose_bucket(len);
391 std::deque<Bucket>& buckets = m_buckets_for[n_bucket];
393 for(
size_t i = 0; i != buckets.size(); ++i)
395 Bucket& bucket = buckets[i];
400#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
403 m_free_pages.push_back(bucket.ptr());
405 if(i != buckets.size() - 1)
406 std::swap(buckets.back(), buckets[i]);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ASSERT(expr, assertion_made)
Memory_Pool(const std::vector< void * > &pages, size_t page_size)
bool deallocate(void *p, size_t size) noexcept
void * allocate(size_t size)
int(* final)(unsigned char *, CTX *)
void page_allow_access(void *page)
void page_prohibit_access(void *page)
void clear_bytes(void *ptr, size_t bytes)