From a2c99d3270eb73ef2db5704fc54356c6b75096f8 Mon Sep 17 00:00:00 2001 From: lloyd Date: Thu, 18 May 2006 18:33:19 +0000 Subject: Initial checkin --- src/mem_pool.cpp | 302 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 302 insertions(+) create mode 100644 src/mem_pool.cpp (limited to 'src/mem_pool.cpp') diff --git a/src/mem_pool.cpp b/src/mem_pool.cpp new file mode 100644 index 000000000..b157c1e59 --- /dev/null +++ b/src/mem_pool.cpp @@ -0,0 +1,302 @@ +/************************************************* +* Pooling Allocator Source File * +* (C) 1999-2006 The Botan Project * +*************************************************/ + +#include +#include +#include +#include +#include +#include + +namespace Botan { + +namespace { + +/************************************************* +* Decide how much memory to allocate at once * +*************************************************/ +u32bit choose_pref_size(u32bit provided) + { + if(provided) + return provided; + + u32bit result = Config::get_u32bit("base/memory_chunk"); + if(result) + return result; + + return 16*1024; + } + +} + +/************************************************* +* Memory_Block Constructor * +*************************************************/ +Pooling_Allocator::Memory_Block::Memory_Block(void* buf, u32bit map_size, + u32bit block_size) + { + buffer = static_cast(buf); + bitmap = 0; + this->block_size = block_size; + + buffer_end = buffer + (block_size * BITMAP_SIZE); + + clear_mem(buffer, block_size * BITMAP_SIZE); + + if(map_size != BITMAP_SIZE) + throw Invalid_Argument("Memory_Block: Bad bitmap size"); + } + +/************************************************* +* Compare a Memory_Block with a void pointer * +*************************************************/ +bool Pooling_Allocator::Memory_Block::operator<(const void* other) const + { + if(buffer <= other && other < buffer_end) + return false; + return (buffer < other); + } + +/************************************************* +* Compare two Memory_Block objects * +*************************************************/ +bool Pooling_Allocator::Memory_Block::operator<(const Memory_Block& blk) const + { + return (buffer < blk.buffer); + } + +/************************************************* +* See if ptr is contained by this block * +*************************************************/ +bool Pooling_Allocator::Memory_Block::contains(void* ptr, + u32bit length) const throw() + { + return ((buffer <= ptr) && + (buffer_end >= (byte*)ptr + length * block_size)); + } + +/************************************************* +* Allocate some memory, if possible * +*************************************************/ +byte* Pooling_Allocator::Memory_Block::alloc(u32bit n) throw() + { + if(n == 0 || n > BITMAP_SIZE) + return 0; + + if(n == BITMAP_SIZE) + { + if(bitmap) + return 0; + else + { + bitmap = ~bitmap; + return buffer; + } + } + + bitmap_type mask = ((bitmap_type)1 << n) - 1; + u32bit offset = 0; + + while(bitmap & mask) + { + mask <<= 1; + ++offset; + + if((bitmap & mask) == 0) + break; + if(mask >> 63) + break; + } + + if(bitmap & mask) + return 0; + + bitmap |= mask; + return buffer + offset * block_size; + } + +/************************************************* +* Mark this memory as free, if we own it * +*************************************************/ +void Pooling_Allocator::Memory_Block::free(void* ptr, u32bit blocks) throw() + { + clear_mem((byte*)ptr, blocks * block_size); + + const u32bit offset = ((byte*)ptr - buffer) / block_size; + + if(offset == 0 && blocks == BITMAP_SIZE) + bitmap = ~bitmap; + else + { + for(u32bit j = 0; j != blocks; ++j) + bitmap &= ~((bitmap_type)1 << (j+offset)); + } + } + +/************************************************* +* Pooling_Allocator Constructor * +*************************************************/ +Pooling_Allocator::Pooling_Allocator(u32bit p_size, bool) : + PREF_SIZE(choose_pref_size(p_size)), BLOCK_SIZE(64) + { + mutex = global_state().get_mutex(); + last_used = blocks.begin(); + } + +/************************************************* +* Pooling_Allocator Destructor * +*************************************************/ +Pooling_Allocator::~Pooling_Allocator() + { + delete mutex; + if(blocks.size()) + throw Invalid_State("Pooling_Allocator: Never released memory"); + } + +/************************************************* +* Allocate some initial buffers * +*************************************************/ +void Pooling_Allocator::init() + { + Mutex_Holder lock(mutex); + + get_more_core(PREF_SIZE); + } + +/************************************************* +* Free all remaining memory * +*************************************************/ +void Pooling_Allocator::destroy() + { + Mutex_Holder lock(mutex); + + blocks.clear(); + + for(u32bit j = 0; j != allocated.size(); ++j) + dealloc_block(allocated[j].first, allocated[j].second); + allocated.clear(); + } + +/************************************************* +* Allocation * +*************************************************/ +void* Pooling_Allocator::allocate(u32bit n) + { + const u32bit BITMAP_SIZE = Memory_Block::bitmap_size(); + + Mutex_Holder lock(mutex); + + if(n <= BITMAP_SIZE * BLOCK_SIZE) + { + const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE; + + byte* mem = allocate_blocks(block_no); + if(mem) + return mem; + + get_more_core(PREF_SIZE); + + mem = allocate_blocks(block_no); + if(mem) + return mem; + + throw Memory_Exhaustion(); + } + + void* new_buf = alloc_block(n); + if(new_buf) + return new_buf; + + throw Memory_Exhaustion(); + } + +/************************************************* +* Deallocation * +*************************************************/ +void Pooling_Allocator::deallocate(void* ptr, u32bit n) + { + const u32bit BITMAP_SIZE = Memory_Block::bitmap_size(); + + if(ptr == 0 && n == 0) + return; + + Mutex_Holder lock(mutex); + + if(n > BITMAP_SIZE * BLOCK_SIZE) + dealloc_block(ptr, n); + else + { + const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE; + + std::vector::iterator i = + std::lower_bound(blocks.begin(), blocks.end(), ptr); + + if(i != blocks.end() && i->contains((byte*)ptr, block_no)) + i->free(ptr, block_no); + else + throw Invalid_State("Pointer released to the wrong allocator"); + } + } + +/************************************************* +* Try to get some memory from an existing block * +*************************************************/ +byte* Pooling_Allocator::allocate_blocks(u32bit n) + { + if(blocks.empty()) + return 0; + + std::vector::iterator i = last_used; + + do + { + i++; + if(i == blocks.end()) + i = blocks.begin(); + + byte* mem = i->alloc(n); + if(mem) + { + last_used = i; + return mem; + } + } + while(i != last_used); + + return 0; + } + +/************************************************* +* Allocate more memory for the pool * +*************************************************/ +void Pooling_Allocator::get_more_core(u32bit in_bytes) + { + const u32bit BITMAP_SIZE = Memory_Block::bitmap_size(); + + const u32bit TOTAL_BLOCK_SIZE = BLOCK_SIZE * BITMAP_SIZE; + + const u32bit in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE; + const u32bit to_allocate = in_blocks * TOTAL_BLOCK_SIZE; + + void* ptr = alloc_block(to_allocate); + if(ptr == 0) + throw Memory_Exhaustion(); + + allocated.push_back(std::make_pair(ptr, to_allocate)); + + for(u32bit j = 0; j != in_blocks; ++j) + { + byte* byte_ptr = static_cast(ptr); + + blocks.push_back( + Memory_Block(byte_ptr + j * TOTAL_BLOCK_SIZE, BITMAP_SIZE, BLOCK_SIZE) + ); + } + + std::sort(blocks.begin(), blocks.end()); + last_used = std::lower_bound(blocks.begin(), blocks.end(), ptr); + } + +} -- cgit v1.2.3