Re: [Patch] bitmap_allocator.

[Dhruv Matani <dhruvbird at gmx dot net>]

On Thu, 2004-10-14 at 04:23, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >Ok. Let me explain what I am trying to do: 
> >I have a pointer to some type T which is not the one parameterizing the
> >allocator.
> >
> A *very down to earth* proposal: can't you simply stop referring internally
> to unsigned int (T is unsigned int currently, right?) which is only 16 
> bits both

Yes, partly correct. T is at times unsigned int, and at times
_Alloc_block<some_size>. Now, _Alloc_block is guaranteed to be 8-byte
aligned, while the number of bit-maps is always a multiple of 32. The
number of bytes in an unsigned int = 4, so always, _Alloc_block will
start at an 8-byte aligned address if we can somehow prove that the
first(last) bitmap starts at an 8-byte aligned address. This is quite
simple to see IMHO.

typedef unsigned int bitmap_type

Now, size of memory returned by operator new is = num_bitmaps *
sizeof(bitmap_type) + 2*sizeof(unsigned int)/*for book-keeping*/ +
num_bitmaps * 32 /*number of bits in 1 bitmap*/ *
sizeof(_Alloc_block<sizeof(value_type)>.

So, as you can see, the initial book-keeping data is 2 unsigned ints,
which stores the size of the returned block, and the references that the
user program has to that block. By references I mean how many blocks
from the current blocks are being used. When the count falls to 0, the
block is deallocated.

So, with the alignment patch, what I did was that those 2 unsigned ints
at the start we made aligned to 8-bytes, which guaranteed that the
bitmap would start at an 8-byte aligned address.

Now, IMO, the problem might be starting at the place when I start
accessing bit-maps! That's because half of them will have only 4-byte
alignment! If this in fact is the problem, then how does the compiler
arrays of unsigned ints for 64-bit machines? We can then adopt the same
strategy!



> on 32-bit and 64-bit machines? Can't you just use a wider type? Long would
> do much better, I'm sure, since it's 8 bytes on 64-bit machines, and, 
> possibly,
> if the user wants to configure for the best alignment, you could just 
> consider
> pairs of those objects as your basic internal units.

Yes, currently I use the __builting_ctz instruction, which is working
for 32-bit types. Now, I need to change that to __builtin_ctzl. But is
it guaranteed that it will work for 8-byte types, and also will
sizeof(long) == 8-bytes on 32-bit and 64-bit machines?

> 
> Also, remember that if you allocate bookkeeping data in the memory returned
> by ::operator new, that data must also be aligned according to its type 
> and then,
> in general, you need padding between that data and your usable memory: f.i.,
> if you store a single int in an header, you need, for best alignement, 4 
> bytes
> (or 12 bytes) of padding in the middle.

Should I assume that 8-byte alignment is sufficient?

> 
> Paolo.
-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs