monotone

monotone Mtn Source Tree

Root/botan/mem_pool.cpp

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

Archive Download this file

Branches

Tags

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