monotone

monotone Mtn Source Tree

Root/botan/mem_pool.cpp

1/*************************************************
2* Pooling Allocator Source File *
3* (C) 1999-2006 The Botan Project *
4*************************************************/
5
6#include <botan/mem_pool.h>
7#include <botan/libstate.h>
8#include <botan/config.h>
9#include <botan/bit_ops.h>
10#include <botan/util.h>
11#include <algorithm>
12
13namespace Botan {
14
15namespace {
16
17/*************************************************
18* Decide how much memory to allocate at once *
19*************************************************/
20u32bit choose_pref_size(u32bit provided)
21 {
22 if(provided)
23 return provided;
24
25 u32bit result = global_config().option_as_u32bit("base/memory_chunk");
26 if(result)
27 return result;
28
29 return 16*1024;
30 }
31
32}
33
34/*************************************************
35* Memory_Block Constructor *
36*************************************************/
37Pooling_Allocator::Memory_Block::Memory_Block(void* buf, u32bit map_size,
38 u32bit block_size)
39 {
40 buffer = static_cast<byte*>(buf);
41 bitmap = 0;
42 this->block_size = block_size;
43
44 buffer_end = buffer + (block_size * BITMAP_SIZE);
45
46 clear_mem(buffer, block_size * BITMAP_SIZE);
47
48 if(map_size != BITMAP_SIZE)
49 throw Invalid_Argument("Memory_Block: Bad bitmap size");
50 }
51
52/*************************************************
53* Compare a Memory_Block with a void pointer *
54*************************************************/
55inline bool Pooling_Allocator::Memory_Block::operator<(const void* other) const
56 {
57 if(buffer <= other && other < buffer_end)
58 return false;
59 return (buffer < other);
60 }
61
62/*************************************************
63* See if ptr is contained by this block *
64*************************************************/
65bool Pooling_Allocator::Memory_Block::contains(void* ptr,
66 u32bit length) const throw()
67 {
68 return ((buffer <= ptr) &&
69 (buffer_end >= (byte*)ptr + length * block_size));
70 }
71
72/*************************************************
73* Allocate some memory, if possible *
74*************************************************/
75byte* Pooling_Allocator::Memory_Block::alloc(u32bit n) throw()
76 {
77 if(n == 0 || n > BITMAP_SIZE)
78 return 0;
79
80 if(n == BITMAP_SIZE)
81 {
82 if(bitmap)
83 return 0;
84 else
85 {
86 bitmap = ~bitmap;
87 return buffer;
88 }
89 }
90
91 bitmap_type mask = ((bitmap_type)1 << n) - 1;
92 u32bit offset = 0;
93
94 while(bitmap & mask)
95 {
96 mask <<= 1;
97 ++offset;
98
99 if((bitmap & mask) == 0)
100 break;
101 if(mask >> 63)
102 break;
103 }
104
105 if(bitmap & mask)
106 return 0;
107
108 bitmap |= mask;
109 return buffer + offset * block_size;
110 }
111
112/*************************************************
113* Mark this memory as free, if we own it *
114*************************************************/
115void Pooling_Allocator::Memory_Block::free(void* ptr, u32bit blocks) throw()
116 {
117 clear_mem((byte*)ptr, blocks * block_size);
118
119 const u32bit offset = ((byte*)ptr - buffer) / block_size;
120
121 if(offset == 0 && blocks == BITMAP_SIZE)
122 bitmap = ~bitmap;
123 else
124 {
125 for(u32bit j = 0; j != blocks; ++j)
126 bitmap &= ~((bitmap_type)1 << (j+offset));
127 }
128 }
129
130/*************************************************
131* Pooling_Allocator Constructor *
132*************************************************/
133Pooling_Allocator::Pooling_Allocator(u32bit p_size, bool) :
134 PREF_SIZE(choose_pref_size(p_size)), BLOCK_SIZE(64)
135 {
136 mutex = global_state().get_mutex();
137 last_used = blocks.begin();
138 }
139
140/*************************************************
141* Pooling_Allocator Destructor *
142*************************************************/
143Pooling_Allocator::~Pooling_Allocator()
144 {
145 delete mutex;
146 if(blocks.size())
147 throw Invalid_State("Pooling_Allocator: Never released memory");
148 }
149
150/*************************************************
151* Free all remaining memory *
152*************************************************/
153void Pooling_Allocator::destroy()
154 {
155 Mutex_Holder lock(mutex);
156
157 blocks.clear();
158
159 for(u32bit j = 0; j != allocated.size(); ++j)
160 dealloc_block(allocated[j].first, allocated[j].second);
161 allocated.clear();
162 }
163
164/*************************************************
165* Allocation *
166*************************************************/
167void* Pooling_Allocator::allocate(u32bit n)
168 {
169 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
170
171 Mutex_Holder lock(mutex);
172
173 if(n <= BITMAP_SIZE * BLOCK_SIZE)
174 {
175 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
176
177 byte* mem = allocate_blocks(block_no);
178 if(mem)
179 return mem;
180
181 get_more_core(PREF_SIZE);
182
183 mem = allocate_blocks(block_no);
184 if(mem)
185 return mem;
186
187 throw Memory_Exhaustion();
188 }
189
190 void* new_buf = alloc_block(n);
191 if(new_buf)
192 return new_buf;
193
194 throw Memory_Exhaustion();
195 }
196
197/*************************************************
198* Deallocation *
199*************************************************/
200void Pooling_Allocator::deallocate(void* ptr, u32bit n)
201 {
202 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
203
204 if(ptr == 0 && n == 0)
205 return;
206
207 Mutex_Holder lock(mutex);
208
209 if(n > BITMAP_SIZE * BLOCK_SIZE)
210 dealloc_block(ptr, n);
211 else
212 {
213 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
214
215 std::vector<Memory_Block>::iterator i =
216 std::lower_bound(blocks.begin(), blocks.end(), ptr, diff_less<Memory_Block,void*>());
217
218 if(i != blocks.end() && i->contains((byte*)ptr, block_no))
219 i->free(ptr, block_no);
220 else
221 throw Invalid_State("Pointer released to the wrong allocator");
222 }
223 }
224
225/*************************************************
226* Try to get some memory from an existing block *
227*************************************************/
228byte* Pooling_Allocator::allocate_blocks(u32bit n)
229 {
230 if(blocks.empty())
231 return 0;
232
233 std::vector<Memory_Block>::iterator i = last_used;
234
235 do
236 {
237 byte* mem = i->alloc(n);
238 if(mem)
239 {
240 last_used = i;
241 return mem;
242 }
243
244 ++i;
245 if(i == blocks.end())
246 i = blocks.begin();
247 }
248 while(i != last_used);
249
250 return 0;
251 }
252
253/*************************************************
254* Allocate more memory for the pool *
255*************************************************/
256void Pooling_Allocator::get_more_core(u32bit in_bytes)
257 {
258 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
259
260 const u32bit TOTAL_BLOCK_SIZE = BLOCK_SIZE * BITMAP_SIZE;
261
262 const u32bit in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE;
263 const u32bit to_allocate = in_blocks * TOTAL_BLOCK_SIZE;
264
265 void* ptr = alloc_block(to_allocate);
266 if(ptr == 0)
267 throw Memory_Exhaustion();
268
269 allocated.push_back(std::make_pair(ptr, to_allocate));
270
271 for(u32bit j = 0; j != in_blocks; ++j)
272 {
273 byte* byte_ptr = static_cast<byte*>(ptr);
274
275 blocks.push_back(
276 Memory_Block(byte_ptr + j * TOTAL_BLOCK_SIZE, BITMAP_SIZE, BLOCK_SIZE)
277 );
278 }
279
280 std::sort(blocks.begin(), blocks.end());
281 last_used = std::lower_bound(blocks.begin(), blocks.end(), ptr, diff_less<Memory_Block,void*>());
282 }
283
284}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status