Botan  1.10.9
mem_pool.cpp
Go to the documentation of this file.
1 /*
2 * Pooling Allocator
3 * (C) 1999-2008 Jack Lloyd
4 * 2005 Matthew Gregan
5 * 2005-2006 Matt Johnston
6 *
7 * Distributed under the terms of the Botan license
8 */
9 
10 #include <botan/internal/mem_pool.h>
11 #include <botan/internal/rounding.h>
12 #include <botan/mem_ops.h>
13 #include <algorithm>
14 #include <exception>
15 
16 namespace Botan {
17 
18 /*
19 * Memory_Block Constructor
20 */
21 Pooling_Allocator::Memory_Block::Memory_Block(void* buf)
22  {
23  buffer = static_cast<byte*>(buf);
24  bitmap = 0;
25  buffer_end = buffer + (BLOCK_SIZE * BITMAP_SIZE);
26  }
27 
28 /*
29 * See if ptr is contained by this block
30 */
31 bool Pooling_Allocator::Memory_Block::contains(void* ptr,
32  size_t length) const
33  {
34  return ((buffer <= ptr) &&
35  (buffer_end >= static_cast<byte*>(ptr) + length * BLOCK_SIZE));
36  }
37 
38 /*
39 * Allocate some memory, if possible
40 */
42  {
43  if(n == 0 || n > BITMAP_SIZE)
44  return 0;
45 
46  if(n == BITMAP_SIZE)
47  {
48  if(bitmap)
49  return 0;
50  else
51  {
52  bitmap = ~bitmap;
53  return buffer;
54  }
55  }
56 
57  bitmap_type mask = (static_cast<bitmap_type>(1) << n) - 1;
58  size_t offset = 0;
59 
60  while(bitmap & mask)
61  {
62  mask <<= 1;
63  ++offset;
64 
65  if((bitmap & mask) == 0)
66  break;
67  if(mask >> 63)
68  break;
69  }
70 
71  if(bitmap & mask)
72  return 0;
73 
74  bitmap |= mask;
75  return buffer + offset * BLOCK_SIZE;
76  }
77 
78 /*
79 * Mark this memory as free, if we own it
80 */
81 void Pooling_Allocator::Memory_Block::free(void* ptr, size_t blocks)
82  {
83  clear_mem(static_cast<byte*>(ptr), blocks * BLOCK_SIZE);
84 
85  const size_t offset = (static_cast<byte*>(ptr) - buffer) / BLOCK_SIZE;
86 
87  if(offset == 0 && blocks == BITMAP_SIZE)
88  bitmap = ~bitmap;
89  else
90  {
91  for(size_t j = 0; j != blocks; ++j)
92  bitmap &= ~(static_cast<bitmap_type>(1) << (j+offset));
93  }
94  }
95 
96 /*
97 * Pooling_Allocator Constructor
98 */
100  {
101  last_used = blocks.begin();
102  }
103 
104 /*
105 * Pooling_Allocator Destructor
106 */
108  {
109  delete mutex;
110  if(blocks.size())
111  throw Invalid_State("Pooling_Allocator: Never released memory");
112  }
113 
114 /*
115 * Free all remaining memory
116 */
118  {
119  Mutex_Holder lock(mutex);
120 
121  blocks.clear();
122 
123  for(size_t j = 0; j != allocated.size(); ++j)
124  dealloc_block(allocated[j].first, allocated[j].second);
125  allocated.clear();
126  }
127 
128 /*
129 * Allocation
130 */
132  {
133  const size_t BITMAP_SIZE = Memory_Block::bitmap_size();
134  const size_t BLOCK_SIZE = Memory_Block::block_size();
135 
136  Mutex_Holder lock(mutex);
137 
138  if(n <= BITMAP_SIZE * BLOCK_SIZE)
139  {
140  const size_t block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
141 
142  byte* mem = allocate_blocks(block_no);
143  if(mem)
144  return mem;
145 
146  get_more_core(BOTAN_MEM_POOL_CHUNK_SIZE);
147 
148  mem = allocate_blocks(block_no);
149  if(mem)
150  return mem;
151 
152  throw Memory_Exhaustion();
153  }
154 
155  void* new_buf = alloc_block(n);
156  if(new_buf)
157  return new_buf;
158 
159  throw Memory_Exhaustion();
160  }
161 
162 /*
163 * Deallocation
164 */
165 void Pooling_Allocator::deallocate(void* ptr, size_t n)
166  {
167  const size_t BITMAP_SIZE = Memory_Block::bitmap_size();
168  const size_t BLOCK_SIZE = Memory_Block::block_size();
169 
170  if(ptr == 0 || n == 0)
171  return;
172 
173  Mutex_Holder lock(mutex);
174 
175  if(n > BITMAP_SIZE * BLOCK_SIZE)
176  dealloc_block(ptr, n);
177  else
178  {
179  const size_t block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
180 
181  std::vector<Memory_Block>::iterator i =
182  std::lower_bound(blocks.begin(), blocks.end(), Memory_Block(ptr));
183 
184  if(i == blocks.end() || !i->contains(ptr, block_no))
185  throw Invalid_State("Pointer released to the wrong allocator");
186 
187  i->free(ptr, block_no);
188  }
189  }
190 
191 /*
192 * Try to get some memory from an existing block
193 */
194 byte* Pooling_Allocator::allocate_blocks(size_t n)
195  {
196  if(blocks.empty())
197  return 0;
198 
199  std::vector<Memory_Block>::iterator i = last_used;
200 
201  do
202  {
203  byte* mem = i->alloc(n);
204  if(mem)
205  {
206  last_used = i;
207  return mem;
208  }
209 
210  ++i;
211  if(i == blocks.end())
212  i = blocks.begin();
213  }
214  while(i != last_used);
215 
216  return 0;
217  }
218 
219 /*
220 * Allocate more memory for the pool
221 */
222 void Pooling_Allocator::get_more_core(size_t in_bytes)
223  {
224  const size_t BITMAP_SIZE = Memory_Block::bitmap_size();
225  const size_t BLOCK_SIZE = Memory_Block::block_size();
226 
227  const size_t TOTAL_BLOCK_SIZE = BLOCK_SIZE * BITMAP_SIZE;
228 
229  // upper bound on allocation is 1 MiB
230  in_bytes = std::min<size_t>(in_bytes, 1024 * 1024);
231 
232  const size_t in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE;
233  const size_t to_allocate = in_blocks * TOTAL_BLOCK_SIZE;
234 
235  void* ptr = alloc_block(to_allocate);
236  if(ptr == 0)
237  throw Memory_Exhaustion();
238 
239  allocated.push_back(std::make_pair(ptr, to_allocate));
240 
241  for(size_t j = 0; j != in_blocks; ++j)
242  {
243  byte* byte_ptr = static_cast<byte*>(ptr);
244  blocks.push_back(Memory_Block(byte_ptr + j * TOTAL_BLOCK_SIZE));
245  }
246 
247  std::sort(blocks.begin(), blocks.end());
248  last_used = std::lower_bound(blocks.begin(), blocks.end(),
249  Memory_Block(ptr));
250  }
251 
252 }
BigInt n
Definition: numthry.cpp:26
size_t block_size
Definition: ossl_md.cpp:41
void deallocate(void *, size_t)
Definition: mem_pool.cpp:165
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:32
Mutex * mutex
Definition: global_rng.cpp:164
Pooling_Allocator(Mutex *mutex)
Definition: mem_pool.cpp:99
void * allocate(size_t)
Definition: mem_pool.cpp:131
unsigned char byte
Definition: types.h:22
T round_up(T n, T align_to)
Definition: rounding.h:22
Allocator * alloc
Definition: bzip2.cpp:29