File indexing completed on 2024-05-12 04:45:14
0001 /* 0002 Copyright (C) 1999-2007 The Botan Project. All rights reserved. 0003 0004 Redistribution and use in source and binary forms, for any use, with or without 0005 modification, is permitted provided that the following conditions are met: 0006 0007 1. Redistributions of source code must retain the above copyright notice, this 0008 list of conditions, and the following disclaimer. 0009 0010 2. Redistributions in binary form must reproduce the above copyright notice, 0011 this list of conditions, and the following disclaimer in the documentation 0012 and/or other materials provided with the distribution. 0013 0014 THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED 0015 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 0016 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED. 0017 0018 IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT, 0019 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 0020 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 0021 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 0022 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 0023 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 0024 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 0025 */ 0026 // LICENSEHEADER_END 0027 namespace QCA { // WRAPNS_LINE 0028 /************************************************* 0029 * Pooling Allocator Source File * 0030 * (C) 1999-2007 The Botan Project * 0031 *************************************************/ 0032 0033 } // WRAPNS_LINE 0034 #include <botan/mem_pool.h> 0035 namespace QCA { // WRAPNS_LINE 0036 } // WRAPNS_LINE 0037 #include <botan/libstate.h> 0038 namespace QCA { // WRAPNS_LINE 0039 #ifdef BOTAN_TOOLS_ONLY 0040 } // WRAPNS_LINE 0041 #include <botan/mem_ops.h> 0042 namespace QCA { // WRAPNS_LINE 0043 #else 0044 } // WRAPNS_LINE 0045 #include <botan/config.h> 0046 namespace QCA { // WRAPNS_LINE 0047 } // WRAPNS_LINE 0048 #include <botan/bit_ops.h> 0049 namespace QCA { // WRAPNS_LINE 0050 #endif 0051 } // WRAPNS_LINE 0052 #include <botan/util.h> 0053 namespace QCA { // WRAPNS_LINE 0054 } // WRAPNS_LINE 0055 #include <algorithm> 0056 namespace QCA { // WRAPNS_LINE 0057 0058 namespace Botan { 0059 0060 namespace { 0061 0062 /************************************************* 0063 * Decide how much memory to allocate at once * 0064 *************************************************/ 0065 u32bit choose_pref_size(u32bit provided) 0066 { 0067 if (provided) 0068 return provided; 0069 0070 #ifdef BOTAN_TOOLS_ONLY 0071 u32bit result = (u32bit)global_state().prealloc_size; 0072 #else 0073 u32bit result = global_config().option_as_u32bit("base/memory_chunk"); 0074 #endif 0075 if (result) 0076 return result; 0077 0078 return 16 * 1024; 0079 } 0080 0081 } 0082 0083 /************************************************* 0084 * Memory_Block Constructor * 0085 *************************************************/ 0086 Pooling_Allocator::Memory_Block::Memory_Block(void *buf) 0087 { 0088 buffer = static_cast<byte *>(buf); 0089 bitmap = 0; 0090 buffer_end = buffer + (BLOCK_SIZE * BITMAP_SIZE); 0091 } 0092 0093 /************************************************* 0094 * See if ptr is contained by this block * 0095 *************************************************/ 0096 bool Pooling_Allocator::Memory_Block::contains(void *ptr, u32bit length) const throw() 0097 { 0098 return ((buffer <= ptr) && (buffer_end >= (byte *)ptr + length * BLOCK_SIZE)); 0099 } 0100 0101 /************************************************* 0102 * Allocate some memory, if possible * 0103 *************************************************/ 0104 byte *Pooling_Allocator::Memory_Block::alloc(u32bit n) throw() 0105 { 0106 if (n == 0 || n > BITMAP_SIZE) 0107 return nullptr; 0108 0109 if (n == BITMAP_SIZE) { 0110 if (bitmap) 0111 return nullptr; 0112 else { 0113 bitmap = ~bitmap; 0114 return buffer; 0115 } 0116 } 0117 0118 bitmap_type mask = ((bitmap_type)1 << n) - 1; 0119 u32bit offset = 0; 0120 0121 while (bitmap & mask) { 0122 mask <<= 1; 0123 ++offset; 0124 0125 if ((bitmap & mask) == 0) 0126 break; 0127 if (mask >> 63) 0128 break; 0129 } 0130 0131 if (bitmap & mask) 0132 return nullptr; 0133 0134 bitmap |= mask; 0135 return buffer + offset * BLOCK_SIZE; 0136 } 0137 0138 /************************************************* 0139 * Mark this memory as free, if we own it * 0140 *************************************************/ 0141 void Pooling_Allocator::Memory_Block::free(void *ptr, u32bit blocks) throw() 0142 { 0143 clear_mem((byte *)ptr, blocks * BLOCK_SIZE); 0144 0145 const u32bit offset = ((byte *)ptr - buffer) / BLOCK_SIZE; 0146 0147 if (offset == 0 && blocks == BITMAP_SIZE) 0148 bitmap = ~bitmap; 0149 else { 0150 for (u32bit j = 0; j != blocks; ++j) 0151 bitmap &= ~((bitmap_type)1 << (j + offset)); 0152 } 0153 } 0154 0155 /************************************************* 0156 * Pooling_Allocator Constructor * 0157 *************************************************/ 0158 Pooling_Allocator::Pooling_Allocator(u32bit p_size, bool) 0159 : PREF_SIZE(choose_pref_size(p_size)) 0160 { 0161 mutex = global_state().get_mutex(); 0162 last_used = blocks.begin(); 0163 } 0164 0165 /************************************************* 0166 * Pooling_Allocator Destructor * 0167 *************************************************/ 0168 Pooling_Allocator::~Pooling_Allocator() QCA_NOEXCEPT(false) 0169 { 0170 delete mutex; 0171 if (blocks.size()) 0172 throw Invalid_State("Pooling_Allocator: Never released memory"); 0173 } 0174 0175 /************************************************* 0176 * Free all remaining memory * 0177 *************************************************/ 0178 void Pooling_Allocator::destroy() 0179 { 0180 Mutex_Holder lock(mutex); 0181 0182 blocks.clear(); 0183 0184 for (const std::pair<void *, u32bit> &p : allocated) 0185 dealloc_block(p.first, p.second); 0186 allocated.clear(); 0187 } 0188 0189 /************************************************* 0190 * Allocation * 0191 *************************************************/ 0192 void *Pooling_Allocator::allocate(u32bit n) 0193 { 0194 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size(); 0195 const u32bit BLOCK_SIZE = Memory_Block::block_size(); 0196 0197 Mutex_Holder lock(mutex); 0198 0199 if (n <= BITMAP_SIZE * BLOCK_SIZE) { 0200 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE; 0201 0202 byte *mem = allocate_blocks(block_no); 0203 if (mem) 0204 return mem; 0205 0206 get_more_core(PREF_SIZE); 0207 0208 mem = allocate_blocks(block_no); 0209 if (mem) 0210 return mem; 0211 0212 throw Memory_Exhaustion(); 0213 } 0214 0215 void *new_buf = alloc_block(n); 0216 if (new_buf) 0217 return new_buf; 0218 0219 throw Memory_Exhaustion(); 0220 } 0221 0222 /************************************************* 0223 * Deallocation * 0224 *************************************************/ 0225 void Pooling_Allocator::deallocate(void *ptr, u32bit n) 0226 { 0227 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size(); 0228 const u32bit BLOCK_SIZE = Memory_Block::block_size(); 0229 0230 if (ptr == nullptr || n == 0) 0231 return; 0232 0233 Mutex_Holder lock(mutex); 0234 0235 if (n > BITMAP_SIZE * BLOCK_SIZE) 0236 dealloc_block(ptr, n); 0237 else { 0238 const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE; 0239 0240 std::vector<Memory_Block>::iterator i = std::lower_bound(blocks.begin(), blocks.end(), Memory_Block(ptr)); 0241 0242 if (i == blocks.end() || !i->contains(ptr, block_no)) 0243 throw Invalid_State("Pointer released to the wrong allocator"); 0244 0245 i->free(ptr, block_no); 0246 } 0247 } 0248 0249 /************************************************* 0250 * Try to get some memory from an existing block * 0251 *************************************************/ 0252 byte *Pooling_Allocator::allocate_blocks(u32bit n) 0253 { 0254 if (blocks.empty()) 0255 return nullptr; 0256 0257 std::vector<Memory_Block>::iterator i = last_used; 0258 0259 do { 0260 byte *mem = i->alloc(n); 0261 if (mem) { 0262 last_used = i; 0263 return mem; 0264 } 0265 0266 ++i; 0267 if (i == blocks.end()) 0268 i = blocks.begin(); 0269 } while (i != last_used); 0270 0271 return nullptr; 0272 } 0273 0274 /************************************************* 0275 * Allocate more memory for the pool * 0276 *************************************************/ 0277 void Pooling_Allocator::get_more_core(u32bit in_bytes) 0278 { 0279 const u32bit BITMAP_SIZE = Memory_Block::bitmap_size(); 0280 const u32bit BLOCK_SIZE = Memory_Block::block_size(); 0281 0282 const u32bit TOTAL_BLOCK_SIZE = BLOCK_SIZE * BITMAP_SIZE; 0283 0284 const u32bit in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE; 0285 const u32bit to_allocate = in_blocks * TOTAL_BLOCK_SIZE; 0286 0287 void *ptr = alloc_block(to_allocate); 0288 if (ptr == nullptr) 0289 throw Memory_Exhaustion(); 0290 0291 allocated.emplace_back(ptr, to_allocate); 0292 0293 for (u32bit j = 0; j != in_blocks; ++j) { 0294 byte *byte_ptr = static_cast<byte *>(ptr); 0295 blocks.emplace_back(byte_ptr + j * TOTAL_BLOCK_SIZE); 0296 } 0297 0298 std::sort(blocks.begin(), blocks.end()); 0299 last_used = std::lower_bound(blocks.begin(), blocks.end(), Memory_Block(ptr)); 0300 } 0301 0302 const u32bit Pooling_Allocator::Memory_Block::BITMAP_SIZE = 8 * sizeof(Pooling_Allocator::Memory_Block::bitmap_type); 0303 const u32bit Pooling_Allocator::Memory_Block::BLOCK_SIZE = 64; 0304 0305 } 0306 } // WRAPNS_LINE