Alignment problems

[jacob navia]

One of the critics to the container library was that I did not align in
the sample implementation the values given to it as the element size. In
some machines, accessing double data in an unaligned fashion could
provoke a segmentation fault.

My answer was that any actual implementation could take care
specifically of any alignment problems but in retrospect that is making
things too easy for me. So I have added the following macros to align
data when requesting an element size:

#define roundupTo(x,n) (((x)+((n)-1))&(~((n)-1)))
#define roundup(x) roundupTo(x,sizeof(void *))

The first macro supposes that sizeof(void *) is a power of two. Besides
the DeathStar 9000 has anyone ever heared from a machine where
sizeof(void *) is NOT a power of two?

The second macro supposes that all alignment problems disappear if we
align to sizeof void *. Has anyone here an example where that is not true?

Thanks in advance.

Jacob

 

[Ian Collins]

One of the critics to the container library was that I did not align in
the sample implementation the values given to it as the element size. In
some machines, accessing double data in an unaligned fashion could
provoke a segmentation fault.

My answer was that any actual implementation could take care
specifically of any alignment problems but in retrospect that is making
things too easy for me. So I have added the following macros to align
data when requesting an element size:

#define roundupTo(x,n) (((x)+((n)-1))&(~((n)-1)))
#define roundup(x) roundupTo(x,sizeof(void *))

Why don't you use inline functions?

The first macro supposes that sizeof(void *) is a power of two. Besides
the DeathStar 9000 has anyone ever heared from a machine where
sizeof(void *) is NOT a power of two?

The second macro supposes that all alignment problems disappear if we
align to sizeof void *. Has anyone here an example where that is not true?

double and long double may be an issue, especially on a 32 bit machine.

How about:

const size_t shift = (sizeof(long double)/sizeof(void*)-1);

size_t roundup( size_t x )
{
return roundupTo( x, sizeof(void*)<<shift );
}

 

[jacob navia]

Ian Collins a écrit :

Why don't you use inline functions?

Because microsoft refuses to accept "inline" in their compilers and the
library must be compatible with microsoft windows.

double and long double may be an issue, especially on a 32 bit machine.

How about:

const size_t shift = (sizeof(long double)/sizeof(void*)-1);

In a 32 bit machine sizeof(long double) can be 12 (lcc-win for instance)
and sizeof (void *) is 4. 12/4 --> 3, minus one is 2. Shift is two.

size_t roundup( size_t x )
{
return roundupTo( x, sizeof(void*)<<shift );
}

That sizeof(void *) * 2 is 8. We would round up to 8 when only 4 is
necessary... at least in the x86 architecture.

 

[Ian Collins]

Ian Collins a écrit :


Because microsoft refuses to accept "inline" in their compilers and the
library must be compatible with microsoft windows.
Blimey.


In a 32 bit machine sizeof(long double) can be 12 (lcc-win for instance)
and sizeof (void *) is 4. 12/4 --> 3, minus one is 2. Shift is two.

So the alignment will be 16, which should be safe for any long double.

That sizeof(void *) * 2 is 8. We would round up to 8 when only 4 is
necessary... at least in the x86 architecture.

* 4, rounding to 16. I was being conservative!

 

[Keith Thompson]

The second macro supposes that all alignment problems disappear if we
align to sizeof void *. Has anyone here an example where that is not true?

I've used several systems where long double, or even double, has
stricter alignment requirements than void* (e.g., void* requires
4-byte alignment and long double requires 8-byte aligbment).

Actually I'm not certain that the stricter alignment is *required* in
all cases; I have a test program that infers alignment requirements
from how struct members are allocated, but compilers can impose
stricter alignment than is necessary.

Function pointers are probably also worth checking. I seem to
recall that on the AS/400 function pointers are much larger than
data pointers, but I don't know about alignment requirements.

If you take the maximum required alignment of any of:
long long
intmax_t
double
long double
void*
void(*)(void)
you're very likely to be ok. (I wouldn't skip anything from this
list; for example, if long double is implemented in software,
it might be less strictly aligned than double.)

 

[Seebs]

The second macro supposes that all alignment problems disappear if we
align to sizeof void *. Has anyone here an example where that is not true?

Tons, double is often larger than void *.

-s

 

[Ian Collins]

Tons, double is often larger than void *.

Double the size...

 

[jacob navia]

Ian Collins a écrit :

Double the size...

That woiuld be a C++ answer, not a C answer Ian. Suppose you want to
store shorts in your container (size 2). You would end up rounding
to 16 for each short, i.e. an overhead of 800%, multiplying by
8 the storage requirements.

Impossible.

 

[jacob navia]

Seebs a écrit :

Tons, double is often larger than void *.

-s

Yes, but that doesn't matter since

(1) You store doubles. Size is 8, and roundup requirements are 4, say,
and in that case no alignment will be performed at all and everything
will work "out of the box" since 8 is a multiple of 4.

(2) You store the doubles in a structure. In that case the compiler will
have done the alignment for you.

 

[Ian Collins]

Ian Collins a écrit :

That woiuld be a C++ answer, not a C answer Ian.

It was intended as a pun...

 

[Ian Collins]

It was intended as a pun...

The C++ answer would be "use a template".

The code snippet I posted calculates the power of 2 >= sizeof(long
double) and is basically what I use for malloc.

If you are always storing your data in memory returned by malloc, it
will obviously be correctly aligned. If you are using an offset into an
allocated block, the same alignment is appropriate. Storing a single
value in a container is an edge case.

 

[Stephen Sprunk]

One of the critics to the container library was that I did not align in
the sample implementation the values given to it as the element size. In
some machines, accessing double data in an unaligned fashion could
provoke a segmentation fault.

My answer was that any actual implementation could take care
specifically of any alignment problems but in retrospect that is making
things too easy for me. So I have added the following macros to align
data when requesting an element size:

#define roundupTo(x,n) (((x)+((n)-1))&(~((n)-1)))
#define roundup(x) roundupTo(x,sizeof(void *))

The first macro supposes that sizeof(void *) is a power of two. Besides
the DeathStar 9000 has anyone ever heared from a machine where
sizeof(void *) is NOT a power of two?

There are embedded processors with 24- and 48-bit pointers, but I'm not
sure what CHAR_BIT is on those platforms. It's conceivable that an
x86/x64 compiler might have a 48-bit/96-bit void*, but I've never seen
one in the wild.

The second macro supposes that all alignment problems disappear if we
align to sizeof void *. Has anyone here an example where that is not true?

There are real-world systems where one or more of double, long double,
and long long require stricter alignment than void*.

I did some thinking, and came up with a few non-portable ideas that
reminded me of how offsetof() must work internally*, so I tried this and
it seems to work fine:

#define alignmentof(T) offsetof(struct {char foo;T bar;}, bar)

For some reason, I had expected that wouldn't be conforming since I've
never seen code remotely like it before, but GCC accepts it with -ansi
-pedantic, so I'm assuming it's portable.

S

(* Most interestingly, this:
#define alignmentof(T) (int)&((T*)0)[1]
Unfortunately, that overstates the alignment requirements of any types
for which the correct alignmentof(T) < sizeof(T).)

 

[Seebs]

(1) You store doubles. Size is 8, and roundup requirements are 4, say,
and in that case no alignment will be performed at all and everything
will work "out of the box" since 8 is a multiple of 4.

On at least some targets, the alignment requirement for double is 8, and
sizeof (void *) is 4, so rounding to 4s doesn't guarantee you suitable
alignment for double.

-s

 

[Alexander Klauer]

That's a fascinating little hack. I can't see anything technically wrong
with it, either. Anyone?

(And because the struct is anonymous, it doesn't even pollute user
namespace.)

It doesn't work with function pointer types. For example,

alignmentof(void (*)(void))

expands to

offsetof(struct {char foo; void (*)(void) bar;}, bar)

which is a syntax error. For function pointers, one would need another
macro, maybe something along the lines of

#define alignmentoffp(T, ...) offsetof(struct {char foo; \
T (*bar)(__VA_ARGS__);}, bar)

with the first macro parameter the return type and subsequent macro
parameters the function parameters.

 

[Ben Bacarisse]

It doesn't work with function pointer types. For example,

Nor pointers to arrays for the same reason. Array types in general are
also a problem but maybe one never wants to know their alignment by
automatic means.

alignmentof(void (*)(void))

expands to

offsetof(struct {char foo; void (*)(void) bar;}, bar)

which is a syntax error. For function pointers, one would need another
macro, maybe something along the lines of

#define alignmentoffp(T, ...) offsetof(struct {char foo; \
T (*bar)(__VA_ARGS__);}, bar)

Alternatively, just require that the argument be a declaration of a
specified member:

#define alignmentof(D, member) offsetof(struct {char foo;D;}, member)

alignmentof(void (*fp)(void), fp)
alignmentof(int array[8], array)

Not ideal, but it works.

[I tried a typedef in the original macro:

alignmentof(typedef void (*FP)(void); FP)

but typedefs are not permitted inside structs.]

 

[Alexander Klauer]

Nor pointers to arrays for the same reason. Array types in general are

Indeed. I didn't think of arrays.

also a problem but maybe one never wants to know their alignment by
automatic means. [...]

#define alignmentoffp(T, ...) offsetof(struct {char foo; \
T (*bar)(__VA_ARGS__);}, bar)

Alternatively, just require that the argument be a declaration of a
specified member:

#define alignmentof(D, member) offsetof(struct {char foo;D;}, member)

alignmentof(void (*fp)(void), fp)
alignmentof(int array[8], array)

Not ideal, but it works.

It seems like the best solution so far, especially when very complex
declarations are involved (think array of pointer to function or some
such).

BTW, I noticed a discrepancy between paragraphs 7 and 8 of N1256, 6.3.2.3.
If you convert a pointer to an object type to a pointer to a different
object type and back again, the behaviour is undefined if an alignment
requirement is violated along the way. No such undefined behaviour occurs
when doing the same with pointers to function. While this is insufficient
to construe that all pointers to function have the same alignment
requirement (which would obsolete the need for an alignmentof macro for
pointer to function types), it makes me wonder why the standard treats
these two pointer categories differently in this respect.

 

[Keith Thompson]

BTW, I noticed a discrepancy between paragraphs 7 and 8 of N1256, 6.3.2.3.
If you convert a pointer to an object type to a pointer to a different
object type and back again, the behaviour is undefined if an alignment
requirement is violated along the way. No such undefined behaviour occurs
when doing the same with pointers to function. While this is insufficient
to construe that all pointers to function have the same alignment
requirement (which would obsolete the need for an alignmentof macro for
pointer to function types), it makes me wonder why the standard treats
these two pointer categories differently in this respect.

In this context, "correctly aligned" refers to the alignment of
the object to which the pointer points, not the alignment of the
pointer object itself. Functions aren't objects, so they don't have
an alignment. (Well, they might, but there's no way to generate
a misaligned pointer-to-function, so it's not a language-visible
issue.)

Conversions operate on values, so the alignment of an object whose
value is being converted is irrelevant to pointer conversions.
(If a pointer object is misaligned, you get undefined behavior when
you access it.)

You still need to worry about the alignment of pointer *objects*,
including pointer-to-function objects.

 

[Keith Thompson]

It doesn't work with function pointer types. For example,

alignmentof(void (*)(void))

expands to

offsetof(struct {char foo; void (*)(void) bar;}, bar)

which is a syntax error. For function pointers, one would need another
macro, maybe something along the lines of

#define alignmentoffp(T, ...) offsetof(struct {char foo; \
T (*bar)(__VA_ARGS__);}, bar)

with the first macro parameter the return type and subsequent macro
parameters the function parameters.

Or you can declare a typedef for the function pointer type and pass the
name of the typedef to the macro.

Here's a snippet from a program I use to test the characteristics of
C implementations:

#define ALIGNOF(type) ((int)(offsetof(struct {char c; type t;}, t)))
....
typedef void(*simple_func_ptr)(void);
....
#define SHOW_RAW_TYPE(type) \
do { \
int size = sizeof(type) * CHAR_BIT; \
int align = ALIGNOF(type) * CHAR_BIT; \
printf("%-20s %3d bits align %3d\n", \
#type, \
size, \
align); \
} while(0)
....
SHOW_RAW_TYPE(simple_func_ptr);

 

[ImpalerCore]

One of the critics to the container library was that I did not align in
the sample implementation the values given to it as the element size. In
some machines, accessing double data in an unaligned fashion could
provoke a segmentation fault.

My answer was that any actual implementation could take care
specifically of any alignment problems but in retrospect that is making
things too easy for me. So I have added the following macros to align
data when requesting an element size:

#define roundupTo(x,n) (((x)+((n)-1))&(~((n)-1)))
#define roundup(x) roundupTo(x,sizeof(void *))

The first macro supposes that sizeof(void *) is a power of two. Besides
the DeathStar 9000 has anyone ever heared from a machine where
sizeof(void *) is NOT a power of two?

The second macro supposes that all alignment problems disappear if we
align to sizeof void *. Has anyone here an example where that is not true?

Thanks in advance.

Jacob

What's the performance differences between mashing the container
struct and the data together versus using a separate pointer? The
obvious benefit of using a separate pointer is that you avoid all this
alignment nonsense all-together. While I sort of understand that
mashing the structures together can provide better performance (better
cache locality, any others?), the total savings of complicating your
design to tweak out a potentially nominal performance gain may not be
worth it.

Then again, there are likely specific scenarios where it is worth it,
but I'm not familiar with them enough for it to be a factor to want to
deal with the alignment issues. Are there any references or articles
that contrast the performance of these two pointer paradigms? Have
you had measurably better performance using your method? Is the risk
of seg-faulting on some unknown compiler with some unknown alignment
issue with a data type worth the performance gains? I don't know,
that's why I'm asking.

Best regards,
John D.

 

[Lauri Alanko]

#define alignmentof(D, member) offsetof(struct {char foo;D;}, member)

Very nice, but even this cannot be used to get the alignment of a
struct with a flexible array member, as such a struct cannot be a
member of another struct. Anyone have suggestions how to deal with
those?

Also, is there some magic (for a custom memory allocator) to find out
what would be the greatest alignment that any object can require?


Lauri Alanko
(e-mail address removed)