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
62inline bool Pooling_Allocator::Memory_Block::operator>(const void* other) const
63 {
64 if(buffer <= other && other < buffer_end)
65 return false;
66 return (buffer > other);
67 }
68
69/*************************************************
70* See if ptr is contained by this block *
71*************************************************/
72bool Pooling_Allocator::Memory_Block::contains(void* ptr,
73 u32bit length) const throw()
74 {
75 return ((buffer <= ptr) &&
76 (buffer_end >= (byte*)ptr + length * block_size));
77 }
78
79/*************************************************
80* Allocate some memory, if possible *
81*************************************************/
82byte* Pooling_Allocator::Memory_Block::alloc(u32bit n) throw()
83 {
84 if(n == 0 || n > BITMAP_SIZE)
85 return 0;
86
87 if(n == BITMAP_SIZE)
88 {
89 if(bitmap)
90 return 0;
91 else
92 {
93 bitmap = ~bitmap;
94 return buffer;
95 }
96 }
97
98 bitmap_type mask = ((bitmap_type)1 << n) - 1;
99 u32bit offset = 0;
100
101 while(bitmap & mask)
102 {
103 mask <<= 1;
104 ++offset;
105
106 if((bitmap & mask) == 0)
107 break;
108 if(mask >> 63)
109 break;
110 }
111
112 if(bitmap & mask)
113 return 0;
114
115 bitmap |= mask;
116 return buffer + offset * block_size;
117 }
118
119/*************************************************
120* Mark this memory as free, if we own it *
121*************************************************/
122void Pooling_Allocator::Memory_Block::free(void* ptr, u32bit blocks) throw()
123 {
124 clear_mem((byte*)ptr, blocks * block_size);
125
126 const u32bit offset = ((byte*)ptr - buffer) / block_size;
127
128 if(offset == 0 && blocks == BITMAP_SIZE)
129 bitmap = ~bitmap;
130 else
131 {
132 for(u32bit j = 0; j != blocks; ++j)
133 bitmap &= ~((bitmap_type)1 << (j+offset));
134 }
135 }
136
137/*************************************************
138* Pooling_Allocator Constructor *
139*************************************************/
140Pooling_Allocator::Pooling_Allocator(u32bit p_size, bool) :
141 PREF_SIZE(choose_pref_size(p_size)), BLOCK_SIZE(64)
142 {
143 mutex = global_state().get_mutex();
144 last_used = blocks.begin();
145 }
146
147/*************************************************
148* Pooling_Allocator Destructor *
149*************************************************/
150Pooling_Allocator::~Pooling_Allocator()
151 {
152 delete mutex;
153 if(blocks.size())
154 throw Invalid_State("Pooling_Allocator: Never released memory");
155 }
156
157/*************************************************
158* Free all remaining memory *
159*************************************************/
160void Pooling_Allocator::destroy()
161 {
162 Mutex_Holder lock(mutex);
163
164 blocks.clear();
165
166 for(u32bit j = 0; j != allocated.size(); ++j)
167 dealloc_block(allocated[j].first, allocated[j].second);
168 allocated.clear();
169 }
170
171/*************************************************
172* Allocation *
173*************************************************/
174void* Pooling_Allocator::allocate(u32bit n)
175 {
176 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
177
178 Mutex_Holder lock(mutex);
179
180 if(n <= BITMAP_SIZE * BLOCK_SIZE)
181 {
182 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
183
184 byte* mem = allocate_blocks(block_no);
185 if(mem)
186 return mem;
187
188 get_more_core(PREF_SIZE);
189
190 mem = allocate_blocks(block_no);
191 if(mem)
192 return mem;
193
194 throw Memory_Exhaustion();
195 }
196
197 void* new_buf = alloc_block(n);
198 if(new_buf)
199 return new_buf;
200
201 throw Memory_Exhaustion();
202 }
203
204/*************************************************
205* Deallocation *
206*************************************************/
207void Pooling_Allocator::deallocate(void* ptr, u32bit n)
208 {
209 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
210
211 if(ptr == 0 && n == 0)
212 return;
213
214 Mutex_Holder lock(mutex);
215
216 if(n > BITMAP_SIZE * BLOCK_SIZE)
217 dealloc_block(ptr, n);
218 else
219 {
220 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
221
222 std::vector<Memory_Block>::iterator i =
223 std::lower_bound(blocks.begin(), blocks.end(), ptr, diff_less<Memory_Block,void*>());
224
225 if(i != blocks.end() && i->contains((byte*)ptr, block_no))
226 i->free(ptr, block_no);
227 else
228 throw Invalid_State("Pointer released to the wrong allocator");
229 }
230 }
231
232/*************************************************
233* Try to get some memory from an existing block *
234*************************************************/
235byte* Pooling_Allocator::allocate_blocks(u32bit n)
236 {
237 if(blocks.empty())
238 return 0;
239
240 std::vector<Memory_Block>::iterator i = last_used;
241
242 do
243 {
244 byte* mem = i->alloc(n);
245 if(mem)
246 {
247 last_used = i;
248 return mem;
249 }
250
251 ++i;
252 if(i == blocks.end())
253 i = blocks.begin();
254 }
255 while(i != last_used);
256
257 return 0;
258 }
259
260/*************************************************
261* Allocate more memory for the pool *
262*************************************************/
263void Pooling_Allocator::get_more_core(u32bit in_bytes)
264 {
265 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
266
267 const u32bit TOTAL_BLOCK_SIZE = BLOCK_SIZE * BITMAP_SIZE;
268
269 const u32bit in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE;
270 const u32bit to_allocate = in_blocks * TOTAL_BLOCK_SIZE;
271
272 void* ptr = alloc_block(to_allocate);
273 if(ptr == 0)
274 throw Memory_Exhaustion();
275
276 allocated.push_back(std::make_pair(ptr, to_allocate));
277
278 for(u32bit j = 0; j != in_blocks; ++j)
279 {
280 byte* byte_ptr = static_cast<byte*>(ptr);
281
282 blocks.push_back(
283 Memory_Block(byte_ptr + j * TOTAL_BLOCK_SIZE, BITMAP_SIZE, BLOCK_SIZE)
284 );
285 }
286
287 std::sort(blocks.begin(), blocks.end());
288 last_used = std::lower_bound(blocks.begin(), blocks.end(), ptr, diff_less<Memory_Block,void*>());
289 }
290
291}

Archive Download this file

Branches

Tags

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