Custom memory allocator - alignment

[Romeo Colacitti]

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

 

[Chris Torek]

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.

 

[Romeo Colacitti]

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.

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.

 

[RoSsIaCrIiLoIA]

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

 

[Chris Torek]

[snippage throughout]

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?

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.

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.)