Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Custom memory allocator - alignment

Reply
Thread Tools

Custom memory allocator - alignment

 
 
Romeo Colacitti
Guest
Posts: n/a
 
      03-04-2005
I have a need to make a custom quasi-memory allocator, and I remembered
a simple ons in K&R2. Looking at the code for it now, I think I notice
a "fault" in the design, and I was wondering if people would back me up
on this.

The design basically uses a pool of memory, allocated as a character
array. Pointers into the array are retured by the allocated function.
Isn't this very dangerous, as a char has very lenient memory alignment
requirements, which would allow the compiler to allocate the array
starting at a location that might not be a multiple of an address
required for other type. Also, pointers in the middle of the arrat
(after the first allocation) will certainly be unaligned for some
types.

My fix, is to use an array of ints (as they match the natural size for
my syste), and then use a pointer into this array of ints. When
returning the pointer value, I could cast it to (void *).

Isn't this much safer than the char array versoin?

Can someone correct me on this, or verify my line of thoughts? thx

 
Reply With Quote
 
 
 
 
Chris Torek
Guest
Posts: n/a
 
      03-04-2005
In article <(E-Mail Removed). com>
Romeo Colacitti <(E-Mail Removed)> wrote:
>I have a need to make a custom quasi-memory allocator, and I remembered
>a simple ons in K&R2. Looking at the code for it now, I think I notice
>a "fault" in the design, and I was wondering if people would back me up
>on this.
>
>The design basically uses a pool of memory, allocated as a character
>array. Pointers into the array are retured by the allocated function.
>Isn't this very dangerous, as a char has very lenient memory alignment
>requirements ...


It is indeed unsuitable as a general-purpose allocator. (As a
char-array allocator it works fine, of course.)

>My fix, is to use an array of ints (as they match the natural size for
>my syste), and then use a pointer into this array of ints. When
>returning the pointer value, I could cast it to (void *).
>
>Isn't this much safer than the char array versoin?


Well, how much is "much"? Safe*r*, yes, but perhaps not so much.
In particular it will not fix the problem on machines with 4-byte
"int"s and 8-byte alignment requirements, such as SPARC and MIPS
processors.

ANSI/ISO C, for whatever reasons, does not give one the tools
required to write malloc() in pure ANSI/ISO C. I find this somewhat
unfortunate, but for those who want to press on regardless, it
usually suffices to have the two macros we put into <machine/param.h>
on 4.xBSD systems: ALIGN(p) takes an arbitrary pointer-or-"intptr_t"
value p, and returns an aligned variant of it (as an intptr_t),
which has possibly been increased by some number of bytes ("char"s);
and ALIGNBYTES is the maximum such increase.

In other words, on a BSD system, you can write a malloc() clone
using ALIGNBYTES (to know how many extra bytes to allocate for
rounding) and ALIGN() (to align pointers). You can also use these
for other sneaky allocation tricks involving malloc() itself.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
 
Reply With Quote
 
 
 
 
Romeo Colacitti
Guest
Posts: n/a
 
      03-04-2005
Chris Torek wrote:
> In article <(E-Mail Removed). com>
> Romeo Colacitti <(E-Mail Removed)> wrote:
> >
> >The design basically uses a pool of memory, allocated as a character
> >array. Pointers into the array are retured by the allocated

function.
> >Isn't this very dangerous, as a char has very lenient memory

alignment
> >requirements ...

>
> It is indeed unsuitable as a general-purpose allocator. (As a
> char-array allocator it works fine, of course.)
>


Thank you for clearing that up. The lack of a warning in K&R got me
confused.

>
> >My fix, is to use an array of ints (as they match the natural size

for
> >my syste), and then use a pointer into this array of ints. When
> >returning the pointer value, I could cast it to (void *).
> >
> >Isn't this much safer than the char array versoin?

>
> Well, how much is "much"? Safe*r*, yes, but perhaps not so much.
> In particular it will not fix the problem on machines with 4-byte
> "int"s and 8-byte alignment requirements, such as SPARC and MIPS
> processors.
>


Oh. I would have thought that most implementations (like mine) would
make sizeof "int" equal to the alignment requirement.

>
> ANSI/ISO C, for whatever reasons, does not give one the tools
> required to write malloc() in pure ANSI/ISO C.


Is malloc usually coded in assembly?

> I find this somewhat
> unfortunate, but for those who want to press on regardless, it
> usually suffices to have the two macros we put into <machine/param.h>
> on 4.xBSD systems: ALIGN(p) takes an arbitrary pointer-or-"intptr_t"
> value p, and returns an aligned variant of it (as an intptr_t),
> which has possibly been increased by some number of bytes ("char"s);
> and ALIGNBYTES is the maximum such increase.
>


When it returns the aligned variant, does it copy over the contents of
the object too?

>
> In other words, on a BSD system, you can write a malloc() clone
> using ALIGNBYTES (to know how many extra bytes to allocate for
> rounding) and ALIGN() (to align pointers). You can also use these
> for other sneaky allocation tricks involving malloc() itself.


Well beyond my comprehension, but thank you for clearing up my massive
confusion. I will use an array of ints in my case.

 
Reply With Quote
 
RoSsIaCrIiLoIA
Guest
Posts: n/a
 
      03-04-2005
On 3 Mar 2005 22:26:25 -0800, "Romeo Colacitti" <(E-Mail Removed)>
wrote:
>Chris Torek wrote:
>> In article <(E-Mail Removed). com>
>> Romeo Colacitti <(E-Mail Removed)> wrote:
>> >
>> >The design basically uses a pool of memory, allocated as a character
>> >array. Pointers into the array are retured by the allocated

>function.
>> >Isn't this very dangerous, as a char has very lenient memory

>alignment
>> >requirements ...

>>
>> It is indeed unsuitable as a general-purpose allocator. (As a
>> char-array allocator it works fine, of course.)
>>

>
>Thank you for clearing that up. The lack of a warning in K&R got me
>confused.


have you read K&R2 malloc implementation?
no and NO, K&R2 malloc returns arrays of units aligned to 8 bytes in
my x86>=386 Pc and borland C compiler this seems good; sizeof(long)=4;
but this not fits the other restriction sizeof(long double)=10. it
seems I remember that if an array of long double 10bytes are aligned
to 8bytes => x86 cpu can perform operations but 2x more slow: is it
true?

How about change *here in my pc&cpu* "Align long" with
"Align long double"?
(so there is not problems with long double arrays)
Thank you very much
 
Reply With Quote
 
Chris Torek
Guest
Posts: n/a
 
      03-07-2005
[snippage throughout]

>Chris Torek wrote:
>> Well, how much is "much"? Safe*r*, yes, but perhaps not so much.
>> In particular it will not fix the problem on machines with 4-byte
>> "int"s and 8-byte alignment requirements, such as SPARC and MIPS
>> processors.


In article <(E-Mail Removed). com>
Romeo Colacitti <(E-Mail Removed)> wrote:
>Oh. I would have thought that most implementations (like mine) would
>make sizeof "int" equal to the alignment requirement.


Well, when "maximum alignment" is 128 bytes, do you really want
128-byte "int"s? Even if maximum alignment is a mere 8 or 16 bytes,
as is the case on many modern CPUs, are you sure you want to commit
to having at-least-8-byte "int"s (so that INT_MAX is 9223372036854775807)
on modern 64-bit CPUs? If so, what will you use for a four-byte
type, if "char" is to be one 8-bit byte and "short" is to be two?

>> ANSI/ISO C, for whatever reasons, does not give one the tools
>> required to write malloc() in pure ANSI/ISO C.


>Is malloc usually coded in assembly?


I would imagine not. But one need not resort to assembly code,
when non-portable C will suffice. The problem then lies in the
fact that the code is non-portable, so that moving it from machine
A to machine B causes it to break.

>> ... for those who want to press on regardless, it
>> usually suffices to have the two macros we put into <machine/param.h>
>> on 4.xBSD systems: ALIGN(p) takes an arbitrary pointer-or-"intptr_t"
>> value p, and returns an aligned variant of it (as an intptr_t),
>> which has possibly been increased by some number of bytes ("char"s);
>> and ALIGNBYTES is the maximum such increase.


>When it returns the aligned variant, does it copy over the contents of
>the object too?


I fear you misunderstand: the ALIGN macro does no copying whatsoever.
In fact, three actual implementations, for three different machines,
are:

/* Intel, before SSE */
#define ALIGNBYTES 3
#define ALIGN(p) (((intptr_t)(p) + 3) & ~3)

and:

/* SPARC and MIPS */
#define ALIGNBYTES 7
#define ALIGN(p) (((intptr_t)(p) + 7) & ~7)

and:

/* Intel, when using SSE */
#define ALIGNBYTES 15
#define ALIGN(p) (((intptr_t)(p) + 15) & ~15)

It makes little sense to apply ALIGN() to a pointer after storing
value(s) into the memory to which it points, because the whole
point of applying the ALIGN() macro is to come up with a "well-aligned"
pointer, so that *(type)ptr = value works regardless of the given
pointer-type (char *, int *, double *, long double *, float (**)[5],
short *(**)(int), whatever).

Note that the definition on a Data General Eclipse might perhaps
be:

#define ALIGNBYTES 3
#define ALIGN(p) (((intptr_t)(p) + 1) & ~1)

(depending on the rules for conversion of arbitrary pointers to
type "intptr_t" -- this assumes the conversion produces a word
pointer in all cases), so it is not necessarily the case that
the "number of bytes" (chars) needed is the same as the constant
added-and-masked-out. (If the conversion from pointer-to-integer
and back does not account for byte pointers vs word pointers,
these macros will not suffice, at least not without additional
rules not present in the BSD implementations.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[Slightly OT] Memory management and custom allocator FtM C Programming 64 01-07-2012 01:20 PM
Re: standard memory allocator alignment issue... Spiros Bousbouras C Programming 9 05-13-2008 08:29 PM
allocator alignment issues... Chris Thomasson C++ 1 08-22-2007 03:05 AM
Custom allocator sample code for vector Alex Vinokur C++ 16 08-16-2004 11:25 AM
Idea for custom thread-safe STL allocator? Brian Genisio C++ 12 01-15-2004 03:41 PM



Advertisments