5079590438

Committed 25 May 2023 12:28PM UTC coverage: 92.228% (+0.5%) from 91.723%

Build # 5079590438

Build Type

Pull #3502

github

Pull Request Pull Request #3502: Apply clang-format to the codebase

Run Details

75589 of 81959 relevant lines covered (92.23%)

12139530.51 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.17

/src/lib/utils/mem_pool/mem_pool.cpp

/*
* (C) 2018,2019 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/mem_pool.h>

#include <botan/mem_ops.h>
#include <algorithm>

#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
   #include <botan/internal/os_utils.h>
#endif

namespace Botan {

/*
* Memory pool theory of operation
*
* This allocator is not useful for general purpose but works well within the
* context of allocating cryptographic keys. It makes several assumptions which
* don't work for implementing malloc but simplify and speed up the implementation:
*
* - There is some set of pages, which cannot be expanded later. These are pages
*   which were allocated, mlocked and passed to the Memory_Pool constructor.
*
* - The allocator is allowed to return null anytime it feels like not servicing
*   a request, in which case the request will be sent to calloc instead. In
*   particular, requests which are too small or too large are rejected.
*
* - Most allocations are powers of 2, the remainder are usually a multiple of 8
*
* - Free requests include the size of the allocation, so there is no need to
*   track this within the pool.
*
* - Alignment is important to the caller. For this allocator, any allocation of
*   size N is aligned evenly at N bytes.
*
* Initially each page is in the free page list. Each page is used for just one
* size of allocation, with requests bucketed into a small number of common
* sizes. If the allocation would be too big or too small it is rejected by the pool.
*
* The free list is maintained by a bitmap, one per page/Bucket. Since each
* Bucket only maintains objects of a single size, each bit set or clear
* indicates the status of one object.
*
* An allocation walks the list of buckets and asks each in turn if there is
* space. If a Bucket does not have any space, it sets a boolean flag m_is_full
* so that it does not need to rescan when asked again. The flag is cleared on
* first free from that bucket. If no bucket has space, but there are some free
* pages left, a free page is claimed as a new Bucket for that size. In this case
* it is pushed to the front of the list so it is first in line to service new
* requests.
*
* A deallocation also walks the list of buckets for the size and asks each
* Bucket in turn if it recognizes the pointer. When a Bucket becomes empty as a
* result of a deallocation, it is recycled back into the free pool. When this
* happens, the Buckets page goes to the end of the free list. All pages on the
* free list are marked in the MMU as noaccess, so anything touching them will
* immediately crash. They are only marked R/W once placed into a new bucket.
* Making the free list FIFO maximizes the time between the last free of a bucket
* and that page being writable again, maximizing chances of crashing after a
* use-after-free.
*
* Future work
* -------------
*
* The allocator is protected by a global lock. It would be good to break this
* up, since almost all of the work can actually be done in parallel especially
* when allocating objects of different sizes (which can't possibly share a
* bucket).
*
* It may be worthwhile to optimize deallocation by storing the Buckets in order
* (by pointer value) which would allow binary search to find the owning bucket.
*
* A useful addition would be to randomize the allocations. Memory_Pool would be
* changed to receive also a RandomNumberGenerator& object (presumably the system
* RNG, or maybe a ChaCha_RNG seeded with system RNG). Then the bucket to use and
* the offset within the bucket would be chosen randomly, instead of using first fit.
*
* Right now we don't make any provision for threading, so if two threads both
* allocate 32 byte values one after the other, the two allocations will likely
* share a cache line. Ensuring that distinct threads will (tend to) use distinct
* buckets would reduce this.
*
* Supporting a realloc-style API may be useful.
*/

namespace {

size_t choose_bucket(size_t n) {
   const size_t MINIMUM_ALLOCATION = 16;
   const size_t MAXIMUM_ALLOCATION = 256;

   if(n < MINIMUM_ALLOCATION || n > MAXIMUM_ALLOCATION)
      return 0;

   // Need to tune these

   const size_t buckets[] = {
      16,
      24,
      32,
      48,
      64,
      80,
      96,
      112,
      128,
      160,
      192,
      256,
      0,
   };

   for(size_t i = 0; buckets[i]; ++i) {
      if(n <= buckets[i]) {
         return buckets[i];
      }
   }

   return 0;
}

inline bool ptr_in_pool(const void* pool_ptr, size_t poolsize, const void* buf_ptr, size_t bufsize) {
   const uintptr_t pool = reinterpret_cast<uintptr_t>(pool_ptr);
   const uintptr_t buf = reinterpret_cast<uintptr_t>(buf_ptr);
   return (buf >= pool) && (buf + bufsize <= pool + poolsize);
}

// return index of first set bit
template <typename T>
size_t find_set_bit(T b) {
   size_t s = 8 * sizeof(T) / 2;
   size_t bit = 0;

   // In this context we don't need to be const-time
   while(s > 0) {
      const T mask = (static_cast<T>(1) << s) - 1;
      if((b & mask) == 0) {
         bit += s;
         b >>= s;
      }
      s /= 2;
   }

   return bit;
}

class BitMap final {
   public:
      explicit BitMap(size_t bits) : m_len(bits) {
         m_bits.resize((bits + BITMASK_BITS - 1) / BITMASK_BITS);
         // MSVC warns if the cast isn't there, clang-tidy warns that the cast is pointless
         m_main_mask = static_cast<bitmask_type>(~0);  // NOLINT(bugprone-misplaced-widening-cast)
         m_last_mask = m_main_mask;

         if(bits % BITMASK_BITS != 0)
            m_last_mask = (static_cast<bitmask_type>(1) << (bits % BITMASK_BITS)) - 1;
      }

      bool find_free(size_t* bit);

      void free(size_t bit) {
         BOTAN_ASSERT_NOMSG(bit <= m_len);
         const size_t w = bit / BITMASK_BITS;
         BOTAN_ASSERT_NOMSG(w < m_bits.size());
         const bitmask_type mask = static_cast<bitmask_type>(1) << (bit % BITMASK_BITS);
         m_bits[w] = m_bits[w] & (~mask);
      }

      bool empty() const {
         for(auto bitset : m_bits) {
            if(bitset != 0) {
               return false;
            }
         }

         return true;
      }

   private:
#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
      using bitmask_type = uint8_t;

      enum { BITMASK_BITS = 8 };
#else
      using bitmask_type = word;

      enum { BITMASK_BITS = BOTAN_MP_WORD_BITS };
#endif

      size_t m_len;
      bitmask_type m_main_mask;
      bitmask_type m_last_mask;
      std::vector<bitmask_type> m_bits;
};

bool BitMap::find_free(size_t* bit) {
   for(size_t i = 0; i != m_bits.size(); ++i) {
      const bitmask_type mask = (i == m_bits.size() - 1) ? m_last_mask : m_main_mask;
      if((m_bits[i] & mask) != mask) {
         const size_t free_bit = find_set_bit(~m_bits[i]);
         const bitmask_type bmask = static_cast<bitmask_type>(1) << (free_bit % BITMASK_BITS);
         BOTAN_ASSERT_NOMSG((m_bits[i] & bmask) == 0);
         m_bits[i] |= bmask;
         *bit = BITMASK_BITS * i + free_bit;
         return true;
      }
   }

   return false;
}

}

class Bucket final {
   public:
      Bucket(uint8_t* mem, size_t mem_size, size_t item_size) :
            m_item_size(item_size),
            m_page_size(mem_size),
            m_range(mem),
            m_bitmap(mem_size / item_size),
            m_is_full(false) {}

      uint8_t* alloc() {
         if(m_is_full) {
            // I know I am full
            return nullptr;
         }

         size_t offset;
         if(!m_bitmap.find_free(&offset)) {
            // I just found out I am full
            m_is_full = true;
            return nullptr;
         }

         BOTAN_ASSERT(offset * m_item_size < m_page_size, "Offset is in range");
         return m_range + m_item_size * offset;
      }

      bool free(void* p) {
         if(!in_this_bucket(p))
            return false;

         /*
         Zero also any trailing bytes, which should not have been written to,
         but maybe the user was bad and wrote past the end.
         */
         std::memset(p, 0, m_item_size);

         const size_t offset = (reinterpret_cast<uintptr_t>(p) - reinterpret_cast<uintptr_t>(m_range)) / m_item_size;

         m_bitmap.free(offset);
         m_is_full = false;

         return true;
      }

      bool in_this_bucket(void* p) const { return ptr_in_pool(m_range, m_page_size, p, m_item_size); }

      bool empty() const { return m_bitmap.empty(); }

      uint8_t* ptr() const { return m_range; }

   private:
      size_t m_item_size;
      size_t m_page_size;
      uint8_t* m_range;
      BitMap m_bitmap;
      bool m_is_full;
};

Memory_Pool::Memory_Pool(const std::vector<void*>& pages, size_t page_size) : m_page_size(page_size) {
   m_min_page_ptr = ~static_cast<uintptr_t>(0);
   m_max_page_ptr = 0;

   for(auto page : pages) {
      const uintptr_t p = reinterpret_cast<uintptr_t>(page);

      m_min_page_ptr = std::min(p, m_min_page_ptr);
      m_max_page_ptr = std::max(p, m_max_page_ptr);

      clear_bytes(page, m_page_size);
#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
      OS::page_prohibit_access(page);
#endif
      m_free_pages.push_back(static_cast<uint8_t*>(page));
   }

   /*
   Right now this points to the start of the last page, adjust it to instead
   point to the first byte of the following page
   */
   m_max_page_ptr += page_size;
}

Memory_Pool::~Memory_Pool()  // NOLINT(*-use-equals-default)
{
#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
   for(size_t i = 0; i != m_free_pages.size(); ++i) {
      OS::page_allow_access(m_free_pages[i]);
   }
#endif
}

void* Memory_Pool::allocate(size_t n) {
   if(n > m_page_size)
      return nullptr;

   const size_t n_bucket = choose_bucket(n);

   if(n_bucket > 0) {
      lock_guard_type<mutex_type> lock(m_mutex);

      std::deque<Bucket>& buckets = m_buckets_for[n_bucket];

      /*
      It would be optimal to pick the bucket with the most usage,
      since a bucket with say 1 item allocated out of it has a high
      chance of becoming later freed and then the whole page can be
      recycled.
      */
      for(auto& bucket : buckets) {
         if(uint8_t* p = bucket.alloc())
            return p;

         // If the bucket is full, maybe move it to the end of the list?
         // Otoh bucket search should be very fast
      }

      if(!m_free_pages.empty()) {
         uint8_t* ptr = m_free_pages[0];
         m_free_pages.pop_front();
#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
         OS::page_allow_access(ptr);
#endif
         buckets.push_front(Bucket(ptr, m_page_size, n_bucket));
         void* p = buckets[0].alloc();
         BOTAN_ASSERT_NOMSG(p != nullptr);
         return p;
      }
   }

   // out of room
   return nullptr;
}

bool Memory_Pool::deallocate(void* p, size_t len) noexcept {
   // Do a fast range check first, before taking the lock
   const uintptr_t p_val = reinterpret_cast<uintptr_t>(p);
   if(p_val < m_min_page_ptr || p_val > m_max_page_ptr)
      return false;

   const size_t n_bucket = choose_bucket(len);

   if(n_bucket != 0) {
      try {
         lock_guard_type<mutex_type> lock(m_mutex);

         std::deque<Bucket>& buckets = m_buckets_for[n_bucket];

         for(size_t i = 0; i != buckets.size(); ++i) {
            Bucket& bucket = buckets[i];
            if(bucket.free(p)) {
               if(bucket.empty()) {
#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
                  OS::page_prohibit_access(bucket.ptr());
#endif
                  m_free_pages.push_back(bucket.ptr());

                  if(i != buckets.size() - 1)
                     std::swap(buckets.back(), buckets[i]);
                  buckets.pop_back();
               }
               return true;
            }
         }
      } catch(...) {
         /*
         * The only exception throws that can occur in the above code are from
         * either the STL or BOTAN_ASSERT failures. In either case, such an
         * error indicates a logic error or data corruption in the memory
         * allocator such that it is no longer safe to continue executing.
         *
         * Since this function is noexcept, simply letting the exception escape
         * is sufficient for terminate to be called. However in this scenario
         * it is implementation defined if any stack unwinding is performed.
         * Since stack unwinding could cause further memory deallocations this
         * could result in further corruption in this allocator state. To prevent
         * this, call terminate directly.
         */
         std::terminate();
      }
   }

   return false;
}

}

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
16	namespace 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
90	namespace {
91
92	size_t choose_bucket(size_t n) {	223,955,244✔
93	const size_t MINIMUM_ALLOCATION = 16;	223,955,244✔
94	const size_t MAXIMUM_ALLOCATION = 256;	223,955,244✔
95
96	if(n < MINIMUM_ALLOCATION \|\| n > MAXIMUM_ALLOCATION)	223,955,244✔
97	return 0;
98
99	// Need to tune these
100
101	const size_t buckets[] = {	205,957,179✔
102	16,
103	24,
104	32,
105	48,
106	64,
107	80,
108	96,
109	112,
110	128,
111	160,
112	192,
113	256,
114	0,
115	};
116
117	for(size_t i = 0; buckets[i]; ++i) {	1,175,055,177✔
118	if(n <= buckets[i]) {	1,175,055,177✔
119	return buckets[i];	205,957,179✔
120	}
121	}
122
123	return 0;
124	}
125
126	inline bool ptr_in_pool(const void* pool_ptr, size_t poolsize, const void* buf_ptr, size_t bufsize) {	103,214,299✔
127	const uintptr_t pool = reinterpret_cast<uintptr_t>(pool_ptr);	103,214,299✔
128	const uintptr_t buf = reinterpret_cast<uintptr_t>(buf_ptr);	103,214,299✔
129	return (buf >= pool) && (buf + bufsize <= pool + poolsize);	91,733,086✔
130	}
131
132	// return index of first set bit
133	template <typename T>
134	size_t find_set_bit(T b) {	77,435,236✔
135	size_t s = 8 * sizeof(T) / 2;
136	size_t bit = 0;
137
138	// In this context we don't need to be const-time
139	while(s > 0) {	542,046,652✔
140	const T mask = (static_cast<T>(1) << s) - 1;	464,611,416✔
141	if((b & mask) == 0) {	464,611,416✔
142	bit += s;	148,369,523✔
143	b >>= s;	148,369,523✔
144	}
145	s /= 2;	464,611,416✔
146	}
147
148	return bit;
149	}
150
151	class BitMap final {	36,334,781✔
152	public:
153	explicit BitMap(size_t bits) : m_len(bits) {	7,212,691✔
154	m_bits.resize((bits + BITMASK_BITS - 1) / BITMASK_BITS);	7,212,691✔
155	// MSVC warns if the cast isn't there, clang-tidy warns that the cast is pointless
156	m_main_mask = static_cast<bitmask_type>(~0); // NOLINT(bugprone-misplaced-widening-cast)	7,212,691✔
157	m_last_mask = m_main_mask;	7,212,691✔
158
159	if(bits % BITMASK_BITS != 0)	7,212,691✔
160	m_last_mask = (static_cast<bitmask_type>(1) << (bits % BITMASK_BITS)) - 1;	4,126,557✔
161	}	7,212,691✔
162
163	bool find_free(size_t* bit);
164
165	void free(size_t bit) {	77,432,285✔
166	BOTAN_ASSERT_NOMSG(bit <= m_len);	77,432,285✔
167	const size_t w = bit / BITMASK_BITS;	77,432,285✔
168	BOTAN_ASSERT_NOMSG(w < m_bits.size());	77,432,285✔
169	const bitmask_type mask = static_cast<bitmask_type>(1) << (bit % BITMASK_BITS);	77,432,285✔
170	m_bits[w] = m_bits[w] & (~mask);	77,432,285✔
171	}	77,432,285✔
172
173	bool empty() const {	77,432,285✔
174	for(auto bitset : m_bits) {	91,132,525✔
175	if(bitset != 0) {	83,921,872✔
176	return false;
177	}
178	}
179
180	return true;
181	}
182
183	private:
184	#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
185	using bitmask_type = uint8_t;
186
187	enum { BITMASK_BITS = 8 };
188	#else
189	using bitmask_type = word;
190
191	enum { BITMASK_BITS = BOTAN_MP_WORD_BITS };
192	#endif
193
194	size_t m_len;
195	bitmask_type m_main_mask;
196	bitmask_type m_last_mask;
197	std::vector<bitmask_type> m_bits;
198	};
199
200	bool BitMap::find_free(size_t* bit) {	79,564,228✔
201	for(size_t i = 0; i != m_bits.size(); ++i) {	82,183,362✔
202	const bitmask_type mask = (i == m_bits.size() - 1) ? m_last_mask : m_main_mask;	80,054,370✔
203	if((m_bits[i] & mask) != mask) {	80,054,370✔
204	const size_t free_bit = find_set_bit(~m_bits[i]);	77,435,236✔
205	const bitmask_type bmask = static_cast<bitmask_type>(1) << (free_bit % BITMASK_BITS);	77,435,236✔
206	BOTAN_ASSERT_NOMSG((m_bits[i] & bmask) == 0);	77,435,236✔
207	m_bits[i] \|= bmask;	77,435,236✔
208	bit = BITMASK_BITS i + free_bit;	77,435,236✔
209	return true;	77,435,236✔
210	}
211	}
212
213	return false;
214	}
215
216	}
217
218	class Bucket final {	19,327,394✔
219	public:
220	Bucket(uint8_t* mem, size_t mem_size, size_t item_size) :	7,212,691✔
221	m_item_size(item_size),	7,212,691✔
222	m_page_size(mem_size),	7,212,691✔
223	m_range(mem),	7,212,691✔
224	m_bitmap(mem_size / item_size),	7,212,691✔
225	m_is_full(false) {}	7,212,691✔
226
227	uint8_t* alloc() {	211,061,337✔
228	if(m_is_full) {	211,061,337✔
229	// I know I am full
230	return nullptr;
231	}
232
233	size_t offset;	79,564,228✔
234	if(!m_bitmap.find_free(&offset)) {	79,564,228✔
235	// I just found out I am full
236	m_is_full = true;	2,128,992✔
237	return nullptr;	2,128,992✔
238	}
239
240	BOTAN_ASSERT(offset * m_item_size < m_page_size, "Offset is in range");	77,435,236✔
241	return m_range + m_item_size * offset;	77,435,236✔
242	}
243
244	bool free(void* p) {	103,214,299✔
245	if(!in_this_bucket(p))	283,860,883✔
246	return false;
247
248	/*
249	Zero also any trailing bytes, which should not have been written to,
250	but maybe the user was bad and wrote past the end.
251	*/
252	std::memset(p, 0, m_item_size);	77,432,285✔
253
254	const size_t offset = (reinterpret_cast<uintptr_t>(p) - reinterpret_cast<uintptr_t>(m_range)) / m_item_size;	77,432,285✔
255
256	m_bitmap.free(offset);	77,432,285✔
257	m_is_full = false;	77,432,285✔
258
259	return true;	77,432,285✔
260	}
261
262	bool in_this_bucket(void* p) const { return ptr_in_pool(m_range, m_page_size, p, m_item_size); }	180,646,584✔
263
264	bool empty() const { return m_bitmap.empty(); }	154,864,570✔
265
266	uint8_t* ptr() const { return m_range; }	7,210,653✔
267
268	private:
269	size_t m_item_size;
270	size_t m_page_size;
271	uint8_t* m_range;
272	BitMap m_bitmap;
273	bool m_is_full;
274	};
275
276	Memory_Pool::Memory_Pool(const std::vector<void*>& pages, size_t page_size) : m_page_size(page_size) {	9,583✔
277	m_min_page_ptr = ~static_cast<uintptr_t>(0);	9,583✔
278	m_max_page_ptr = 0;	9,583✔
279
280	for(auto page : pages) {	150,911✔
281	const uintptr_t p = reinterpret_cast<uintptr_t>(page);	141,328✔
282
283	m_min_page_ptr = std::min(p, m_min_page_ptr);	141,328✔
284	m_max_page_ptr = std::max(p, m_max_page_ptr);	141,328✔
285
286	clear_bytes(page, m_page_size);	141,328✔
287	#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
288	OS::page_prohibit_access(page);
289	#endif
290	m_free_pages.push_back(static_cast<uint8_t*>(page));	141,328✔
291	}
292
293	/*
294	Right now this points to the start of the last page, adjust it to instead
295	point to the first byte of the following page
296	*/
297	m_max_page_ptr += page_size;	9,583✔
298	}	9,583✔
299
300	Memory_Pool::~Memory_Pool() // NOLINT(*-use-equals-default)	9,583✔
301	{
302	#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
303	for(size_t i = 0; i != m_free_pages.size(); ++i) {
304	OS::page_allow_access(m_free_pages[i]);
305	}
306	#endif
307	}	9,583✔
308
309	void* Memory_Pool::allocate(size_t n) {	146,557,057✔
310	if(n > m_page_size)	146,557,057✔
311	return nullptr;
312
313	const size_t n_bucket = choose_bucket(n);	146,522,959✔
314
315	if(n_bucket > 0) {	146,522,959✔
316	lock_guard_type<mutex_type> lock(m_mutex);	128,524,894✔
317
318	std::deque<Bucket>& buckets = m_buckets_for[n_bucket];	128,524,894✔
319
320	/*
321	It would be optimal to pick the bucket with the most usage,
322	since a bucket with say 1 item allocated out of it has a high
323	chance of becoming later freed and then the whole page can be
324	recycled.
325	*/
326	for(auto& bucket : buckets) {	395,777,096✔
327	if(uint8_t* p = bucket.alloc())	203,848,646✔
328	return p;	70,222,545✔
329
330	// If the bucket is full, maybe move it to the end of the list?
331	// Otoh bucket search should be very fast
332	}
333
334	if(!m_free_pages.empty()) {	58,302,349✔
335	uint8_t* ptr = m_free_pages[0];	7,212,691✔
336	m_free_pages.pop_front();	7,212,691✔
337	#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
338	OS::page_allow_access(ptr);
339	#endif
340	buckets.push_front(Bucket(ptr, m_page_size, n_bucket));	7,212,691✔
341	void* p = buckets[0].alloc();	7,212,691✔
342	BOTAN_ASSERT_NOMSG(p != nullptr);	7,212,691✔
343	return p;
344	}
345	}	128,524,894✔
346
347	// out of room
348	return nullptr;
349	}
350
351	bool Memory_Pool::deallocate(void* p, size_t len) noexcept {	146,506,852✔
352	// Do a fast range check first, before taking the lock
353	const uintptr_t p_val = reinterpret_cast<uintptr_t>(p);	146,506,852✔
354	if(p_val < m_min_page_ptr \|\| p_val > m_max_page_ptr)	146,506,852✔
355	return false;
356
357	const size_t n_bucket = choose_bucket(len);	77,432,285✔
358
359	if(n_bucket != 0) {	77,432,285✔
360	try {	77,432,285✔
361	lock_guard_type<mutex_type> lock(m_mutex);	77,432,285✔
362
363	std::deque<Bucket>& buckets = m_buckets_for[n_bucket];	77,432,285✔
364
365	for(size_t i = 0; i != buckets.size(); ++i) {	103,214,299✔
366	Bucket& bucket = buckets[i];	103,214,299✔
367	if(bucket.free(p)) {	103,214,299✔
368	if(bucket.empty()) {	154,864,570✔
369	#if defined(BOTAN_MEM_POOL_USE_MMU_PROTECTIONS)
370	OS::page_prohibit_access(bucket.ptr());
371	#endif
372	m_free_pages.push_back(bucket.ptr());	7,210,653✔
373
374	if(i != buckets.size() - 1)	7,210,653✔
375	std::swap(buckets.back(), buckets[i]);	105,774✔
376	buckets.pop_back();	7,210,653✔
377	}
378	return true;	77,432,285✔
379	}
380	}
381	} catch(...) {	77,432,285✔
382	/*
383	* The only exception throws that can occur in the above code are from
384	* either the STL or BOTAN_ASSERT failures. In either case, such an
385	* error indicates a logic error or data corruption in the memory
386	* allocator such that it is no longer safe to continue executing.
387	*
388	* Since this function is noexcept, simply letting the exception escape
389	* is sufficient for terminate to be called. However in this scenario
390	* it is implementation defined if any stack unwinding is performed.
391	* Since stack unwinding could cause further memory deallocations this
392	* could result in further corruption in this allocator state. To prevent
393	* this, call terminate directly.
394	*/
395	std::terminate();	×
396	}
397	}
398
399	return false;
400	}
401
402	}

randombit / botan / 5079590438

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous