Question about malloc, alignment, ...

[Bhalchandra Thatte]

I am allocating a block of memory using malloc.
I want to use it to store a "header" structure
followed by structs in my application. How to calculate
the alignment without making any assumption
about the most restrictive type on my machine?
Thanks.

 

[Irrwahn Grausewitz]

Bertrand Mollinier Toublet

There is no need to coerce malloc into giving you the "right" alignment.
It is supposed to allocate blocks of memory suitably aligned to fit any
type.

Hmm, maybe I'm totally wrong, but reading the OP's question
again and again I suspect that he wants to calculate the
offsets of his data-structures, in which case the 'sizeof'
operator comes to mind. Too sad that no code was provided
by the OP.

 

[Richard Heathfield]

I am allocating a block of memory using malloc.
I want to use it to store a "header" structure
followed by structs in my application. How to calculate
the alignment without making any assumption
about the most restrictive type on my machine?

If you must do it this way, the least clumsy way I can think of that is
guaranteed to work is to make a union of the header and the record itself,
and allocate a bunch of those. This isn't particularly wasteful if the size
of the header and the size of the record are approximately the same. This
way, you don't need to calculate the alignment at all. Just treat
element[0] as your header, and all the other elements as records.

 

[Barry Schwarz]

I am allocating a block of memory using malloc.
I want to use it to store a "header" structure
followed by structs in my application. How to calculate
the alignment without making any assumption
about the most restrictive type on my machine?
Thanks.

The value returned by malloc is guaranteed to be suitable for any
object, including the different types of struct you describe.

Using notation _t for struct types and _ptr pointers to struct, we
start from scratch and build up. Remember to add error checking after
each call to malloc.

For just the header,
header_ptr = malloc(sizeof *header_ptr);
will allocate a sufficient quantity of properly aligned memory to hold
one header structure.

For one header and one struct1,
header_ptr = malloc(sizeof *header_ptr + sizeof *struct1_ptr);
struct1_ptr = (struct1_t*)(header_ptr+1);
will allocate enough space for one header structure and one other
structure. But we have no idea if the value assigned to struct1_ptr
is properly aligned this structure.

One possible solution is
n = (sizeof *header_ptr)/(sizeof *struct1_ptr)+1;
header_ptr = malloc(sizeof *header_ptr +
2 * (sizeof *struct1_ptr));
struct1_ptr = (struct1_t*)header_ptr+n;
Both pointers are guaranteed to be aligned properly.

For an array of k struct1,
n = (sizeof *header_ptr)/(sizeof *struct1_ptr)+1;
header_ptr = malloc(sizeof *header_ptr +
(k+1)*sizeof *struct1_ptr);
struct1_ptr = (struct1_t*)header_ptr+n;
will allocate enough space and align both pointers.

For two different types of application structures,
n1 = (sizeof *header_ptr)/(sizeof *struct1_ptr)+1;
n2 = ((n1+1)*(sizeof *struct1_ptr))/(sizeof *struct2_ptr)+1;
header_ptr = malloc(sizeof *header_ptr +
2 * (sizeof *struct1_ptr) +
2 * (sizeof *struct2_ptr));
struct1_ptr = (struct1_t*)header_ptr + n1;
struct2_ptr = (struct2_t*)header_ptr + n2;

You can extrapolate for more variety and quantity of structures .

However, this appears to be a maintenance nightmare. You would be
much better off with separate allocations instead of trying to force
one block to hold disparate types. Something like
header_ptr = malloc(sizeof *header_ptr);
struct1_ptr = malloc(k1 * sizeof *struct1_ptr);
struct2_ptr = malloc(k2 * sizeof *struct2_ptr);


<<Remove the del for email>>

 

[The Real OS/2 Guy]

I am allocating a block of memory using malloc.
I want to use it to store a "header" structure
followed by structs in my application. How to calculate
the alignment without making any assumption
about the most restrictive type on my machine?
Thanks.

sizeof() gives you always the size of a type. So use sizeof(struct
header) + sizeof(struct xyz) * number_of_struct xyz
as parameter to malloc to get enough space to store one struct header
+ the number of struct xyz elements you have to store there.

sizeof gives always the same answer for an given type. That is it
thinks you means to build an array of that type - even when you needs
only one of that. Let the compiler think about alignments, YOU have no
need to think on it.

 

[Malcolm]

itself, and allocate a bunch of those.

No. You can do it, yes, but what if you have a header followed by a
different number of structs?

/* reserve memory for an header and 100 struct x */
struct header *p = malloc(sizeof(struct header) + 100 * sizeof(struct
x));
/* calculate the base address for struct x (struct x [0]) */
struct x *px = (struct x *) (p + 1);
px[99].member1 = value; /* fill the meber named member1 of the 100.

The way you do it is this.

typedef struct
{
int foo;
int bar;
int N;
}HEADER;

typedef struct
{
char fname[32];
char sname[32];
float salary;
}RECORD;

typedef union
{
HEADER hdr;
RECORD rec;
}MYUNION;

MYUNION *records = malloc( (1 + Nrecords) * sizeof(MYUNION));

It is tempting to say

records = malloc(sizeof(HEADER) + Nrecords * sizeof(RECORD));

but there is no way of guaranteeing that the second set of structures will
be correctly aligned. You can almost guarantee it, by padding HEADER out to
the nearest size of a double, bu this isn't cast iron.

 

[Barry Schwarz]

sizeof() gives you always the size of a type. So use sizeof(struct
header) + sizeof(struct xyz) * number_of_struct xyz
as parameter to malloc to get enough space to store one struct header
+ the number of struct xyz elements you have to store there.

Not if sizeof (struct header) is not a multiple of the alignment
requirement for struct xyz.

Consider a system where int is aligned on a multiple of 4 and
struct header {char c;};
struct xyz {int i;};

sizeof (struct header) could be 1 (there is no need for any padding
after c). and sizeof (struct xyz) could be 4. struct xyz must be
aligned on a multiple of 4 to insure i is aligned.

The sum of the two sizeof values will allocate 5 bytes aligned on a
multiple of 4 which is not sufficient to hold a struct header followed
by a struct xyz.


<<Remove the del for email>>

 

[Richard Heathfield]

I am allocating a block of memory using malloc.
I want to use it to store a "header" structure
followed by structs in my application. How to calculate
the alignment without making any assumption
about the most restrictive type on my machine?

If you must do it this way, the least clumsy way I can think of that is
guaranteed to work is to make a union of the header and the record
itself, and allocate a bunch of those. This isn't particularly wasteful
if the size of the header and the size of the record are approximately
the same. This way, you don't need to calculate the alignment at all.
Just treat element[0] as your header, and all the other elements as
records.

No. You can do it, yes, but what if you have a header followed by a
different number of structs?

You haven't the faintest idea what I was actually suggesting, have you? Try
reading it again.

<snip>

 

[Richard Heathfield]

I am allocating a block of memory using malloc.
I want to use it to store a "header" structure
followed by structs in my application. How to calculate
the alignment without making any assumption
about the most restrictive type on my machine?

If you must do it this way, the least clumsy way I can think of that is
guaranteed to work is to make a union of the header and the record
itself, and allocate a bunch of those. This isn't particularly wasteful
if the size of the header and the size of the record are approximately
the same. This way, you don't need to calculate the alignment at all.
Just treat element[0] as your header, and all the other elements as
records.

This idea is interesting, since it is the simplest, and involves
no computation on my part. And the size of my header is in fact
smaller than other structs.

Since you only have one header, if it's smaller than the records themselves,
that's perfect. Wastage minimised.

Meanwhile I went to a book shop, and browsed through a book
(C interfaces or something like that by Hansen I think). He suggests

union Alignment {
int a;
long b;
float c;
double d;
void (*f)(void) fptr;

Huh? I think this is a bug. (They happen.)

void* e;
...
}
He then uses sizeof(Alignment) and sizeof(header)
to calculate the offset.

In "C Unleashed" I suggest

typedef union
{
long l; /* if C99, consider using intmax_t instead */
unsigned long lu;
double f;
long double lf;
void *vp;
void (*fp)(void);
} ALIGN;

but, as I say, if you adopt my suggestion you won't need this.

I am still not comfortable with it. What if one missed
something in the union? Is it sufficient to list all
basic types provided by the language?

No. For the alignment thing to be ***guaranteed*** to work on a general
basis, you must list every type used by the program, which includes all
user-defined types (which is why implementing a generalised leak detector
is much harder than it looks). It would be sufficient, in *your* case, to
include

struct header hdr;

and

struct record rcd;

into the alignment structure. But of course my solution doesn't require you
to include any of the other types (into your program, to solve your current
problem). A simple union of struct header and struct record is sufficient.

 

[The Real OS/2 Guy]

typedef struct
{
int foo;
int bar;
int N;
}HEADER;

typedef struct
{
char fname[32];
char sname[32];
float salary;
}RECORD;

typedef union
{
HEADER hdr;
RECORD rec;
}MYUNION;

MYUNION *records = malloc( (1 + Nrecords) * sizeof(MYUNION));

It is tempting to say

records = malloc(sizeof(HEADER) + Nrecords * sizeof(RECORD));

but there is no way of guaranteeing that the second set of structures will
be correctly aligned. You can almost guarantee it, by padding HEADER out to
the nearest size of a double, bu this isn't cast iron.

It IS guaranteed that (pointer to struct) (<pointer to struct> + n)
results always to an well aligned pointer to any struct.
typedef struct x X;
typedef struct y Y;
typedef struct z Z;

typedef struct {
int type;
char flags;
X *px;
Y *py;
Z *pz;
} HEADER;

HEADER *p = malloc(sizeof(HEADER) + sizeof(X) + sizeof(Y) * nY +
sizeof(Z))

gives enough space to hold all 3 structs (whereas one of them is an
array of structs.

sample A: work with pointer arithmetic
p->px = (X*) (p + 1); /* base to struct X */
p->py = (Y*) (px + 1); /* base to struct Y[ny] */
p->pz = (Z*) (py + nY); /* base to struct Z */

Works always. That is because you needs ponter arithmetic even when
you addresses members of an array of structs.

sample B: work with byte counts
p->px = (X*) (((char *) p) + sizeof(HEADER)); /* the same as above */
p->py = (Y*) (((char *) px) + sizeof(X));
p->pz = (Z*) (((char *) py) + sizeof(Y) * ny);

Sample A and B delivers exactly the same result. Sample A is simple
beacuse the compiler does the actions of sample B implicite.

malloced_size = ((char *) (p->pz+1)) - (char *) p;
or
malloced_size = ((char *) p->pz) + sizeof(Z) - (char *) p;

All pointer to all structs are identical. structs are always in the
right size to get the object behind it gets aligned right. When an
object is on an aligned address a pointer to it must be aligned well.

How odd the alignment requirement of a mashine ever been, malloc
returns a well aligned address. Adding to that address any size_t
returned from sizeof results in an aligned address of the type sizeof
was worked on. As any struct has the same alignment you can savely
cast a pointer to struct x to pointer to struct y. You can savely work
with pointers to char too because each struct's size is always rounded
up to have the next object on an aligned address.

In practice you can forget about alignment problems because the
compiler works on it for you.

This may not true when you uses implementation defined things, such as
#pragma align - but then you leave ANSI C and gets unportable.

 

[Christian Bau]

Meanwhile I went to a book shop, and browsed through a book
(C interfaces or something like that by Hansen I think). He suggests

union Alignment {
int a;
long b;
float c;
double d;
void (*f)(void) fptr;
void* e;
...
}
He then uses sizeof(Alignment) and sizeof(header)
to calculate the offset.
I am still not comfortable with it. What if one missed
something in the union?

He missed pointer to short, int, long, long long and pointer to struct;
he missed long long as well. All the pointers that I mentioned could in
principle have different size and alignment requirements than void*.

Is it sufficient to list all
basic types provided by the language?

On one very common architecture where sizeof (double) == 8, it would be
quite reasonable that structs with two consecutive double members have
alignment requirement of 16. And I cannot see anything in the C Standard
that would prevent this from happening.

 

[The Real OS/2 Guy]

"The Real OS/2 Guy" <[email protected]> wrote:

[Actually, /I/ wrote the first bit...]

RJH>> > If you must do it this way, the least clumsy way
RJH>> > I can think of that is guaranteed to work is to
RJH>> > make a union of the header and the record itself,
RJH>> > and allocate a bunch of those.

TROS2G>> No. You can do it, yes, but what if you have a
TROS2G>> header followed by a different number of structs?

<snip>

(Over to Malcolm for a bit...)

The way you do it is this.

typedef struct
{
int foo;
int bar;
int N;
}HEADER;

typedef struct
{
char fname[32];
char sname[32];
float salary;
}RECORD;

typedef union
{
HEADER hdr;
RECORD rec;
}MYUNION;

MYUNION *records = malloc( (1 + Nrecords) * sizeof(MYUNION));

Thank you, Malcolm. It appears that *you* actually took the time to read
what I'd written, for which I am grateful. Reading is a dying art, is it
not?

Now your union has the size of the biggest struct. When the big struct
is 4 K, your header 20 bytes and the smallest struct is 16 bytes then
you needs more than 400 KB instead 20 + 16 * 100 = 1620 bytes when you
needs header + smallest struct [100].

The idea is really bad.

Understund how pointer arithmetic works and your memory usage is
thifty. Always let the compiler think about alignment - it is its work
to do so. sizeof is designed to deliver the size of a struct always so
that adding it to a byte pointer the resulting address will be aligned
right for each other object when the base pointer is aligned for.
Adding a counter to a pointer inreses the pointer of sizeof type *
conter bytes implicity.

Pointers to structs are addresses aligned to be pointer of struct (any
struct).

See my other artikle for more details.

 

[The Real OS/2 Guy]

Not if sizeof (struct header) is not a multiple of the alignment
requirement for struct xyz.

Consider a system where int is aligned on a multiple of 4 and
struct header {char c;};
struct xyz {int i;};

sizeof (struct header) could be 1 (there is no need for any padding
after c). and sizeof (struct xyz) could be 4. struct xyz must be
aligned on a multiple of 4 to insure i is aligned.

No sizeof(struct header) would be 4 when the alignment requirement of
a struct is a multiple of 4. Don't work with implementation defined
extensions (e.g. #pragma align) in that case. ANCI C requires that
each member of an array is on an aligned address. struct header[100]
must be 400 bytes in size to have 100 structs of that type aligned
right.

sizeof(char) is always 1. sizeof(struct) is always (sizeof member
rounded up to alignment for any type) + (sizeof next member rounded up
to alignment for any type) + ......

So the single char in the struct has a number of padding bytes to get
the struct the right size to come to the next aligned address. Check
it with any ANSI C compiler you can get in your hands - or simply read
the standard carefully.

The sum of the two sizeof values will allocate 5 bytes aligned on a
multiple of 4 which is not sufficient to hold a struct header followed
by a struct xyz.

Wrong. a char is not a stuct, even as a struct may contain (only) a
char, so the size of struct and char differs.

Use sizeof to get the size of a struct. add the number of of structs
to a pointer, cast the pointer to another struct type - and you're
guaranteed that this new pointer is well aligned to point to an
aligned stuct of that type. The size of an struct doesn't matter. It
is portable, it is ANSI C.

The size of an struct can differ from implementation to implementation
because each implementation has its own alignment requirements and the
size of a struct is based on the align requirements of each of its
members (including the last one). A struct is calculated:

size in bytes of 1. menber + padding bytes to get an address able to
hold an aligned object of any type
+ size in bytes ...
+ ...

So the size of a struct ends up so that a pointer to an aligned object
increased with the size of a struct results in a pointer to an aligned
object of any type.

Define a char! define thereafter another char - the compiler will
create both on different addresses - and each address will differ in
sizeof(char) + required bytes to get the next address aligned to hold
each other other object. It is always the job of the compiler to
define objects on aligned addresses.

When you plays around with implementation defined things (such as
#pragma align) then you leaves ANSI C and you gets unportable. In ANSI
C you can always count on the compiler that pointer arithmetic works
right, so whenever you have to build a pointer you gets a well aligned
pointer when you works on a well aligned pointer.

Increasing a pointer with a number of elements of that type results
always in an well aligned pointer of that type. All structs have equal
alignment requirements to get the next struct.

 

[The Real OS/2 Guy]

This idea is interesting, since it is the simplest, and involves

union Alignment {
int a;
long b;
float c;
double d;
void (*f)(void) fptr;
void* e;
...
}
He then uses sizeof(Alignment) and sizeof(header)
to calculate the offset.

No need for such thing. sizeof delivers allways the needed size to get
the next aligned address if adding to an aligned pointer.

- all structs have the same align requirement.
- adding the number of structs to a pointer of that struct type gives
always the address of the next aligned struct
- casting a pointer to struct to another struct type changes nothing
except the type of the struct.
whenever the pointer is aligned to point to an aligned struct of one
type
it can be casted to another struct type without loosing the
alignment.
- for malloc you have to add the sizeo of each struct, because you
needs a
number of bytes big enough to hold the structs
- for simple pointer arithmetic you can simple add the number of
structs
to the base address of the parent struct to get the address of the
next struct.
whenever the address points to an aligned struct the resulting
address
does the same.
- you can cast a pointer to one struct to another struct. This tells
the
compiler only that the type and order of the members of that struct
are other than the one of the old struct. Whenever the address
points
an aligned struct it will do so thereafter too.

Simply forget about alignment. It is the job of the compiler to think
on it.
Based on this you can get different results from sizeof on different
implementations!
So when you have to serialise your memory you have to handle each
struct member separately when you have to work with different
implementation on them. But then you may have the problem of byte
order too.

 

[Christian Bau]

Consider a system where int is aligned on a multiple of 4 and
struct header {char c;};
struct xyz {int i;};

sizeof (struct header) could be 1 (there is no need for any padding
after c). and sizeof (struct xyz) could be 4. struct xyz must be
aligned on a multiple of 4 to insure i is aligned.

No sizeof(struct header) would be 4 when the alignment requirement of
a struct is a multiple of 4. Don't work with implementation defined
extensions (e.g. #pragma align) in that case. ANCI C requires that
each member of an array is on an aligned address. struct header[100]
must be 400 bytes in size to have 100 structs of that type aligned
right.

There is no reason whatsoever why "struct header" should have a size
greater than one. It may on the compiler that you are using, in general
there is no reason for that assumption. It is absolutely possible that
struct header has an alignment requirement of 1, a size of 1, and an
array of 100 struct header has a size of 100, and everything works fine.

 

[pete]

I am allocating a block of memory using malloc.
I want to use it to store a "header" structure
followed by structs in my application. How to calculate
the alignment without making any assumption
about the most restrictive type on my machine?

The memory returned by malloc is suitably aligned for
the most restrictive type on your machine.
Why not use that information ?

 

[Jarno A Wuolijoki]

What can a cpu do with a struct that has two double members,
when the the alignment requirements are for the size of the structure,
that a cpu can't can't do
when the structure alignment requirements are for the size of a member ?

perform operations for both members with a single instruction:

foo.a+=bar->a; foo.b+=bar->b; /* addpd xmm0, [eax]. requires bar->a to be
16 byte aligned. */

 

[Jack Klein]

"The Real OS/2 Guy" <[email protected]> wrote:

[Actually, /I/ wrote the first bit...]

RJH>> > If you must do it this way, the least clumsy way
RJH>> > I can think of that is guaranteed to work is to
RJH>> > make a union of the header and the record itself,
RJH>> > and allocate a bunch of those.

TROS2G>> No. You can do it, yes, but what if you have a
TROS2G>> header followed by a different number of structs?

<snip>

(Over to Malcolm for a bit...)

The way you do it is this.

typedef struct
{
int foo;
int bar;
int N;
}HEADER;

typedef struct
{
char fname[32];
char sname[32];
float salary;
}RECORD;

typedef union
{
HEADER hdr;
RECORD rec;
}MYUNION;

MYUNION *records = malloc( (1 + Nrecords) * sizeof(MYUNION));

Thank you, Malcolm. It appears that *you* actually took the time to read
what I'd written, for which I am grateful. Reading is a dying art, is it
not?

Now your union has the size of the biggest struct. When the big struct
is 4 K, your header 20 bytes and the smallest struct is 16 bytes then
you needs more than 400 KB instead 20 + 16 * 100 = 1620 bytes when you
needs header + smallest struct [100].

The idea is really bad.

Maybe, maybe not.

Understund how pointer arithmetic works and your memory usage is
thifty. Always let the compiler think about alignment - it is its work
to do so. sizeof is designed to deliver the size of a struct always so
that adding it to a byte pointer the resulting address will be aligned
right for each other object when the base pointer is aligned for.
Adding a counter to a pointer inreses the pointer of sizeof type *
conter bytes implicity.

Pointers to structs are addresses aligned to be pointer of struct (any
struct).

Can you provide a reference from the C standard to support your
statement above? Frankly I know that you can't. It is completely
long. All pointers to structures have the same size and bitwise
representation. That is NOT the same as saying that all structures
have the same memory alignment.

Consider:

================
#include <stdlib.h>

struct one { char ch; };
struct two { long l; };

char *fred = malloc(sizeof(one) + sizeof(two));

struct two *ptr2 = fred + sizeof(one);

long x = ptr2->l;
================

Code equivalent to the above will generate an alignment fault on some
architectures.

See my other artikle for more details.

See ANSI/ISO/IEC 9899:1999 for accurate information.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Chris Torek]

It IS guaranteed that (pointer to struct) (<pointer to struct> + n)
results always to an well aligned pointer to any struct.

This claim is unsupportable.

typedef struct x X;
typedef struct y Y;
typedef struct z Z;

typedef struct {
int type;
char flags;
X *px;
Y *py;
Z *pz;
} HEADER;

HEADER *p = malloc(sizeof(HEADER) + sizeof(X) + sizeof(Y) * nY +
sizeof(Z))

gives enough space to hold all 3 structs (whereas one of them is an
array of structs.

Example where it fails on (e.g.) SPARC (V6 through V9 inclusive):

struct x { char elem; };
struct y { int elem; };
struct z { double elem; };

Here sizeof(X) is 1, and sizeof(HEADER) is either 20 (32-bit mode)
or 32 (64-bit mode). Y and Z have sizes 4 and 8 respectively, and
require 4 and either 4 or 8 (depending on compiler and flags) byte
alignments, so we get:

#define H 20 /* or 32 */
p = malloc(H + 1 + 4 * nY + 8)

(which is definitely an odd number, because of the "+1" in the middle,
not that this matters too much). Then:

sample A: work with pointer arithmetic
p->px = (X*) (p + 1); /* base to struct X */

(assuming p!=NULL of course) this is OK, but:

p->py = (Y*) (px + 1); /* base to struct Y[ny] */

if p is something like 0x4041a800, (p+1) is (unsigned long)p + H
(where H is either 20, hex 0x14, or 32, hex 0x20). (Recall that
I have specified SPARC V6-through-V9; pre-V9 all pointers are 32
bits, and in V9 one usually runs in 32-bit mode, with an "ILP32"
model, or in 64-bit mode, with an "I32LP64" model, so that pointers
fit in "long"s in either case.)

In 32-bit mode, then, p+1 produces address 0x4041a814, which is
valid for "X *px", but (px+1) produces address 0x4041a815, which
is *not* valid for "Y *py". In particular, "int"s must be aligned
on four-byte boundaries.

It *is* possible to make this kind of allocation work, using any
of various tricks shown elsethread, but simply summing the sizes
of the elements and then using element-wise pointer arithmetic will
not do it. The problem will not show up on architectures that make
no strong alignment constraints, of course, and this includes the
usual x86 configurations.

 

[Richard Heathfield]

Now your union has the size of the biggest struct.

Correct. This is why I pointed out that efficiency might be an issue if the
structs were wildly different in size.

When the big struct
is 4 K, your header 20 bytes and the smallest struct is 16 bytes then
you needs more than 400 KB instead 20 + 16 * 100 = 1620 bytes when you
needs header + smallest struct [100].

But, as it turns out, the OP's header is slightly smaller than his struct,
so there is almost no waste of space, and the solution is much simpler than
any other so far proposed.

The idea is really bad.

Your assertion is noted. I disagree entirely with it. The idea of following
the advice slavishly is bad (for example, consider a very large header and
a comparatively small record), but in certain circumstances, including
those of the OP, it is a sensible strategy.

Understund how pointer arithmetic works and your memory usage is
thifty.

Parse error.

Always let the compiler think about alignment - it is its work
to do so.

It's the programmer's job to understand his program.

<snip>