1/*
2Copyright (C) 1999-2007 The Botan Project. All rights reserved.
3
4Redistribution and use in source and binary forms, for any use, with or without
5modification, is permitted provided that the following conditions are met:
6
71. Redistributions of source code must retain the above copyright notice, this
8list of conditions, and the following disclaimer.
9
102. Redistributions in binary form must reproduce the above copyright notice,
11this list of conditions, and the following disclaimer in the documentation
12and/or other materials provided with the distribution.
13
14THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED
15WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED.
17
18IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT,
19INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
20BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
22LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
23OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
24ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*/
26// LICENSEHEADER_END
27namespace QCA { // WRAPNS_LINE
28/*************************************************
29 * Pooling Allocator Source File *
30 * (C) 1999-2007 The Botan Project *
31 *************************************************/
32
33} // WRAPNS_LINE
34#include <botan/mem_pool.h>
35namespace QCA { // WRAPNS_LINE
36} // WRAPNS_LINE
37#include <botan/libstate.h>
38namespace QCA { // WRAPNS_LINE
39#ifdef BOTAN_TOOLS_ONLY
40} // WRAPNS_LINE
41#include <botan/mem_ops.h>
42namespace QCA { // WRAPNS_LINE
43#else
44} // WRAPNS_LINE
45#include <botan/config.h>
46namespace QCA { // WRAPNS_LINE
47} // WRAPNS_LINE
48#include <botan/bit_ops.h>
49namespace QCA { // WRAPNS_LINE
50#endif
51} // WRAPNS_LINE
52#include <botan/util.h>
53namespace QCA { // WRAPNS_LINE
54} // WRAPNS_LINE
55#include <algorithm>
56namespace QCA { // WRAPNS_LINE
57
58namespace Botan {
59
60namespace {
61
62/*************************************************
63 * Decide how much memory to allocate at once *
64 *************************************************/
65u32bit choose_pref_size(u32bit provided)
66{
67 if (provided)
68 return provided;
69
70#ifdef BOTAN_TOOLS_ONLY
71 u32bit result = (u32bit)global_state().prealloc_size;
72#else
73 u32bit result = global_config().option_as_u32bit("base/memory_chunk");
74#endif
75 if (result)
76 return result;
77
78 return 16 * 1024;
79}
80
81}
82
83/*************************************************
84 * Memory_Block Constructor *
85 *************************************************/
86Pooling_Allocator::Memory_Block::Memory_Block(void *buf)
87{
88 buffer = static_cast<byte *>(buf);
89 bitmap = 0;
90 buffer_end = buffer + (BLOCK_SIZE * BITMAP_SIZE);
91}
92
93/*************************************************
94 * See if ptr is contained by this block *
95 *************************************************/
96bool Pooling_Allocator::Memory_Block::contains(void *ptr, u32bit length) const throw()
97{
98 return ((buffer <= ptr) && (buffer_end >= (byte *)ptr + length * BLOCK_SIZE));
99}
100
101/*************************************************
102 * Allocate some memory, if possible *
103 *************************************************/
104byte *Pooling_Allocator::Memory_Block::alloc(u32bit n) throw()
105{
106 if (n == 0 || n > BITMAP_SIZE)
107 return nullptr;
108
109 if (n == BITMAP_SIZE) {
110 if (bitmap)
111 return nullptr;
112 else {
113 bitmap = ~bitmap;
114 return buffer;
115 }
116 }
117
118 bitmap_type mask = ((bitmap_type)1 << n) - 1;
119 u32bit offset = 0;
120
121 while (bitmap & mask) {
122 mask <<= 1;
123 ++offset;
124
125 if ((bitmap & mask) == 0)
126 break;
127 if (mask >> 63)
128 break;
129 }
130
131 if (bitmap & mask)
132 return nullptr;
133
134 bitmap |= mask;
135 return buffer + offset * BLOCK_SIZE;
136}
137
138/*************************************************
139 * Mark this memory as free, if we own it *
140 *************************************************/
141void Pooling_Allocator::Memory_Block::free(void *ptr, u32bit blocks) throw()
142{
143 clear_mem(ptr: (byte *)ptr, n: blocks * BLOCK_SIZE);
144
145 const u32bit offset = ((byte *)ptr - buffer) / BLOCK_SIZE;
146
147 if (offset == 0 && blocks == BITMAP_SIZE)
148 bitmap = ~bitmap;
149 else {
150 for (u32bit j = 0; j != blocks; ++j)
151 bitmap &= ~((bitmap_type)1 << (j + offset));
152 }
153}
154
155/*************************************************
156 * Pooling_Allocator Constructor *
157 *************************************************/
158Pooling_Allocator::Pooling_Allocator(u32bit p_size, bool)
159 : PREF_SIZE(choose_pref_size(provided: p_size))
160{
161 mutex = global_state().get_mutex();
162 last_used = blocks.begin();
163}
164
165/*************************************************
166 * Pooling_Allocator Destructor *
167 *************************************************/
168Pooling_Allocator::~Pooling_Allocator() QCA_NOEXCEPT(false)
169{
170 delete mutex;
171 if (blocks.size())
172 throw Invalid_State("Pooling_Allocator: Never released memory");
173}
174
175/*************************************************
176 * Free all remaining memory *
177 *************************************************/
178void Pooling_Allocator::destroy()
179{
180 Mutex_Holder lock(mutex);
181
182 blocks.clear();
183
184 for (const std::pair<void *, u32bit> &p : allocated)
185 dealloc_block(p.first, p.second);
186 allocated.clear();
187}
188
189/*************************************************
190 * Allocation *
191 *************************************************/
192void *Pooling_Allocator::allocate(u32bit n)
193{
194 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
195 const u32bit BLOCK_SIZE = Memory_Block::block_size();
196
197 Mutex_Holder lock(mutex);
198
199 if (n <= BITMAP_SIZE * BLOCK_SIZE) {
200 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
201
202 byte *mem = allocate_blocks(block_no);
203 if (mem)
204 return mem;
205
206 get_more_core(PREF_SIZE);
207
208 mem = allocate_blocks(block_no);
209 if (mem)
210 return mem;
211
212 throw Memory_Exhaustion();
213 }
214
215 void *new_buf = alloc_block(n);
216 if (new_buf)
217 return new_buf;
218
219 throw Memory_Exhaustion();
220}
221
222/*************************************************
223 * Deallocation *
224 *************************************************/
225void Pooling_Allocator::deallocate(void *ptr, u32bit n)
226{
227 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
228 const u32bit BLOCK_SIZE = Memory_Block::block_size();
229
230 if (ptr == nullptr || n == 0)
231 return;
232
233 Mutex_Holder lock(mutex);
234
235 if (n > BITMAP_SIZE * BLOCK_SIZE)
236 dealloc_block(ptr, n);
237 else {
238 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
239
240 std::vector<Memory_Block>::iterator i = std::lower_bound(first: blocks.begin(), last: blocks.end(), val: Memory_Block(ptr));
241
242 if (i == blocks.end() || !i->contains(ptr, length: block_no))
243 throw Invalid_State("Pointer released to the wrong allocator");
244
245 i->free(ptr, blocks: block_no);
246 }
247}
248
249/*************************************************
250 * Try to get some memory from an existing block *
251 *************************************************/
252byte *Pooling_Allocator::allocate_blocks(u32bit n)
253{
254 if (blocks.empty())
255 return nullptr;
256
257 std::vector<Memory_Block>::iterator i = last_used;
258
259 do {
260 byte *mem = i->alloc(n);
261 if (mem) {
262 last_used = i;
263 return mem;
264 }
265
266 ++i;
267 if (i == blocks.end())
268 i = blocks.begin();
269 } while (i != last_used);
270
271 return nullptr;
272}
273
274/*************************************************
275 * Allocate more memory for the pool *
276 *************************************************/
277void Pooling_Allocator::get_more_core(u32bit in_bytes)
278{
279 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
280 const u32bit BLOCK_SIZE = Memory_Block::block_size();
281
282 const u32bit TOTAL_BLOCK_SIZE = BLOCK_SIZE * BITMAP_SIZE;
283
284 const u32bit in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE;
285 const u32bit to_allocate = in_blocks * TOTAL_BLOCK_SIZE;
286
287 void *ptr = alloc_block(to_allocate);
288 if (ptr == nullptr)
289 throw Memory_Exhaustion();
290
291 allocated.emplace_back(args&: ptr, args: to_allocate);
292
293 for (u32bit j = 0; j != in_blocks; ++j) {
294 byte *byte_ptr = static_cast<byte *>(ptr);
295 blocks.emplace_back(args: byte_ptr + j * TOTAL_BLOCK_SIZE);
296 }
297
298 std::sort(first: blocks.begin(), last: blocks.end());
299 last_used = std::lower_bound(first: blocks.begin(), last: blocks.end(), val: Memory_Block(ptr));
300}
301
302const u32bit Pooling_Allocator::Memory_Block::BITMAP_SIZE = 8 * sizeof(Pooling_Allocator::Memory_Block::bitmap_type);
303const u32bit Pooling_Allocator::Memory_Block::BLOCK_SIZE = 64;
304
305}
306} // WRAPNS_LINE
307

source code of qca/src/botantools/botan/mem_pool.cpp