[Botan-devel] Re: botan-devel Digest, Vol 30, Issue 6
Erik Loman
erik at surfright.nl
Wed Jun 20 04:55:08 EDT 2007
Isn't this the same problem you've fixed for me a while ago?
On Wed, Dec 20, 2006 at 04:01:59PM -0500, Jack Lloyd wrote:
>
> I've attached new versions of mem_pool.*; all that should be needed is
> to copy them into include/ and src/ and rerun the configure script.
> Downside is, it seems the easiest way to avoid the problem is to use a
> linear search instead of lower_bound when searching through the blocks
> during deallocation. On the validation suite (which is very allocation
> heavy) that only slows things down by around 5%, so it shouldn't cause
> any major problems.
>
> -Jack
>
See attachments.
Regards,
Erik
-----Original Message-----
From: botan-devel-bounces at randombit.net
[mailto:botan-devel-bounces at randombit.net] On Behalf Of Jack Lloyd
Sent: dinsdag 19 juni 2007 19:54
To: Botan development list
Subject: Re: [Botan-devel] Re: botan-devel Digest, Vol 30, Issue 6
OK, thanks. I'll try to fire up VMware tonight and take a further look
into this. -Jack
On Tue, Jun 19, 2007 at 01:48:21PM -0400, John Proffer wrote:
> Didn't work - i applied your patch and recompiled with nmake, and got
> the following errors:
>
> C:\Program Files\Microsoft Visual Studio 8\VC\INCLUDE\xutility(267) :
> error C2679: binary '<' : no operator found which takes a right-hand
> operand of
> type 'Botan::Pooling_Allocator::Memory_Block' (or there is no acceptable
> conversion)
>
> could be 'built-in C++ operator<(void *, void
> *)'
>
> while trying to match the argument list '(void *const ,
> Botan::Pooling_Allocator::Memory_Block)'
>
> C:\Program Files\Microsoft Visual Studio
> 8\VC\INCLUDE\algorithm(2268) : see reference to function template
> instantiation 'bool std::_Debug_lt<
> Botan::Pooling_Allocator::Memory_Block,_Ty>(_Ty1 &,const _Ty2 &,const
> wchar_t *,unsigned int)' being
> compiled
>
> with
>
>
> [
>
> _Ty=void
> *,
>
>
> _Ty1=Botan::Pooling_Allocator::Memory_Block,
>
> _Ty2=void
> *
>
>
> ]
>
> C:\Program Files\Microsoft Visual Studio
> 8\VC\INCLUDE\algorithm(2280) : see reference to function template
> instantiation '_FwdIt std::_Lower_b
> ound<std::_Vector_iterator<_Ty,_Alloc>,void,__w64
> int>(_FwdIt,_FwdIt,void &,_Diff *)' being
> compiled
>
> with
>
>
> [
>
>
>
_FwdIt=std::_Vector_iterator<Botan::Pooling_Allocator::Memory_Block,std::all
ocator<Botan::Pooling_Allocator::Memory_Block>>,
>
>
> _Ty=Botan::Pooling_Allocator::Memory_Block,
>
>
> _Alloc=std::allocator<Botan::Pooling_Allocator::Memory_Block>,
>
> _Diff=__w64
> int
>
>
> ]
>
> src\mem_pool.cpp(263) : see reference to function template
> instantiation '_FwdIt
> std::lower_bound<std::_Vector_iterator<_Ty,_Alloc>,void*>(_Fw
> dIt,_FwdIt,void &)' being
> compiled
>
>
> with
>
>
> [
>
>
>
_FwdIt=std::_Vector_iterator<Botan::Pooling_Allocator::Memory_Block,std::all
ocator<Botan::Pooling_Allocator::Memory_Block>>,
>
>
> _Ty=Botan::Pooling_Allocator::Memory_Block,
>
>
> _Alloc=std::allocator<Botan::Pooling_Allocator::Memory_Block>
>
>
> ]
>
> NMAKE : fatal error U1077: '"C:\Program Files\Microsoft Visual Studio
> 8\VC\BIN\cl.EXE"' : return code
> '0x2'
> Stop.
>
>
>
> begin:vcard
> fn:Johnathan Proffer
> n:Proffer;Johnathan
> org:Visual Language Interpreting;Information Technology
> adr;dom:STE B1;;1330 New Hampshire Ave. NW;Washington;DC;20036
> email;internet:jproffer at vli-dc.com
> tel;work:202.464.6800
> tel;fax:202.464.6810
> note;quoted-printable:AIM: jprofferVLI=0D=0A=
> VP: proffer.vli-dc.com
> x-mozilla-html:TRUE
> url:https://www.aboutvli.com
> version:2.1
> end:vcard
>
> _______________________________________________
> botan-devel mailing list
> botan-devel at randombit.net
> http://www.randombit.net/mailman/listinfo/botan-devel
_______________________________________________
botan-devel mailing list
botan-devel at randombit.net
http://www.randombit.net/mailman/listinfo/botan-devel
-------------- next part --------------
/*************************************************
* Pooling Allocator Header File *
* (C) 1999-2006 The Botan Project *
*************************************************/
#ifndef BOTAN_POOLING_ALLOCATOR_H__
#define BOTAN_POOLING_ALLOCATOR_H__
#include <botan/allocate.h>
#include <botan/exceptn.h>
#include <botan/mutex.h>
#include <utility>
#include <vector>
namespace Botan {
/*************************************************
* Pooling Allocator *
*************************************************/
class Pooling_Allocator : public Allocator
{
public:
void* allocate(u32bit);
void deallocate(void*, u32bit);
void destroy();
Pooling_Allocator(u32bit, bool);
~Pooling_Allocator();
private:
void get_more_core(u32bit);
byte* allocate_blocks(u32bit);
virtual void* alloc_block(u32bit) = 0;
virtual void dealloc_block(void*, u32bit) = 0;
class Memory_Block
{
public:
Memory_Block(void*);
static u32bit bitmap_size() { return BITMAP_SIZE; }
static u32bit block_size() { return BLOCK_SIZE; }
bool contains(void*, u32bit) const throw();
byte* alloc(u32bit) throw();
void free(void*, u32bit) throw();
bool operator<(const void*) const;
bool operator<(const Memory_Block& other) const
{ return (buffer < other.buffer); }
private:
typedef u64bit bitmap_type;
static const u32bit BITMAP_SIZE = 8 * sizeof(bitmap_type);
static const u32bit BLOCK_SIZE = 64;
bitmap_type bitmap;
byte* buffer, *buffer_end;
};
const u32bit PREF_SIZE;
std::vector<Memory_Block> blocks;
std::vector<Memory_Block>::iterator last_used;
std::vector<std::pair<void*, u32bit> > allocated;
Mutex* mutex;
};
}
#endif
-------------- next part --------------
/*************************************************
* Pooling Allocator Source File *
* (C) 1999-2006 The Botan Project *
*************************************************/
#include <botan/mem_pool.h>
#include <botan/libstate.h>
#include <botan/config.h>
#include <botan/bit_ops.h>
#include <botan/util.h>
#include <algorithm>
namespace Botan {
namespace {
/*************************************************
* Decide how much memory to allocate at once *
*************************************************/
u32bit choose_pref_size(u32bit provided)
{
if(provided)
return provided;
u32bit result = global_config().option_as_u32bit("base/memory_chunk");
if(result)
return result;
return 16*1024;
}
}
/*************************************************
* Memory_Block Constructor *
*************************************************/
Pooling_Allocator::Memory_Block::Memory_Block(void* buf)
{
buffer = static_cast<byte*>(buf);
bitmap = 0;
buffer_end = buffer + (BLOCK_SIZE * BITMAP_SIZE);
}
/*************************************************
* Compare a Memory_Block with a void pointer *
*************************************************/
inline bool Pooling_Allocator::Memory_Block::operator<(const void* other) const
{
if(buffer <= other && other < buffer_end)
return false;
return (buffer < other);
}
/*************************************************
* 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))
{
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");
}
/*************************************************
* 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();
const u32bit BLOCK_SIZE = Memory_Block::block_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();
const u32bit BLOCK_SIZE = Memory_Block::block_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;
#if _DEBUG
std::vector<Memory_Block>::iterator i = blocks.begin();
while(i != blocks.end())
{
if(i->contains(ptr, block_no))
break;
++i;
}
#else
std::vector<Memory_Block>::iterator i =
std::lower_bound(blocks.begin(), blocks.end(), ptr);
#endif
if(i == blocks.end() || !i->contains(ptr, block_no))
throw Invalid_State("Pointer released to the wrong allocator");
i->free(ptr, block_no);
}
}
/*************************************************
* Try to get some memory from an existing block *
*************************************************/
byte* Pooling_Allocator::allocate_blocks(u32bit n)
{
if(blocks.empty())
return 0;
std::vector<Memory_Block>::iterator i = last_used;
do
{
byte* mem = i->alloc(n);
if(mem)
{
last_used = i;
return mem;
}
++i;
if(i == blocks.end())
i = blocks.begin();
}
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 BLOCK_SIZE = Memory_Block::block_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<byte*>(ptr);
blocks.push_back(Memory_Block(byte_ptr + j * TOTAL_BLOCK_SIZE));
}
std::sort(blocks.begin(), blocks.end());
last_used = std::lower_bound(blocks.begin(), blocks.end(),
Memory_Block(ptr));
}
}
More information about the botan-devel
mailing list