Alignment problems

[jacob navia]

I am trying to test the containers library in different environments

One of those is SUN sparc, that crashes when a double is accessed
in an address not multiple of 8. I got an access to an old one:

: ~/ccl ; uname -a
SunOS 5.9 Generic_118558-25 sun4u sparc SUNW,Sun-Fire-V210

Now, I have a list container with elements that
have this structure:

typedef struct _ListElement {
struct _ListElement *Next;
char Data[MINIMUM_ARRAY_INDEX]; // Generic storage...
} ListElement;


If I store double data in the "Data" member the machine will
crash since apparently it is a 32 bit SPARC, and the start of Data
is NOT aligned to an eight byte boundary.

One solution (albeit very ugly) is:

typedef struct _ListElement {
struct _ListElement *Next;
double alignment1;
char Data[MINIMUM_ARRAY_INDEX]; // Generic storage...
} ListElement;

This works. The compiler will correctly align "Data" and I
can safely store doubles into it. But this solutions is VERY
expensive since for EACH element I am spending 8 bytes
in alignment...

Is there another solution?

The "Data" member MUST be the last since it is a variable length
structure.


Thanks in advance for any pointers.

jacob

P.S. If anyone knows that system, gcc warns me

warning: implicit declaration of function 'snprintf'

I do include stdio.h...

What else should I include for getting snprintf?
Note that the link works, the function exists.
My compile options are:

gcc -std=c99 -I. -g -DUNIX -c sequential.c

 

[Ian Collins]

I am trying to test the containers library in different environments

One of those is SUN sparc, that crashes when a double is accessed
in an address not multiple of 8. I got an access to an old one:

: ~/ccl ; uname -a
SunOS 5.9 Generic_118558-25 sun4u sparc SUNW,Sun-Fire-V210

Now, I have a list container with elements that
have this structure:

typedef struct _ListElement {
struct _ListElement *Next;
char Data[MINIMUM_ARRAY_INDEX]; // Generic storage...
} ListElement;


If I store double data in the "Data" member the machine will
crash since apparently it is a 32 bit SPARC, and the start of Data
is NOT aligned to an eight byte boundary.

One solution (albeit very ugly) is:

typedef struct _ListElement {
struct _ListElement *Next;
double alignment1;
char Data[MINIMUM_ARRAY_INDEX]; // Generic storage...
} ListElement;

This works. The compiler will correctly align "Data" and I
can safely store doubles into it. But this solutions is VERY
expensive since for EACH element I am spending 8 bytes
in alignment...

Some waste is unavoidable, the alignment has to be correct on Sparc.

How about a union of (long) double and char[sizeof(long double]?

P.S. If anyone knows that system, gcc warns me

warning: implicit declaration of function 'snprintf'

I do include stdio.h...

What else should I include for getting snprintf?

I think there was a problem with the header on that old OS version.

 

[Alan Curry]

I am trying to test the containers library in different environments

One of those is SUN sparc, that crashes when a double is accessed
in an address not multiple of 8. I got an access to an old one:

: ~/ccl ; uname -a
SunOS 5.9 Generic_118558-25 sun4u sparc SUNW,Sun-Fire-V210

Now, I have a list container with elements that
have this structure:

typedef struct _ListElement {
struct _ListElement *Next;
char Data[MINIMUM_ARRAY_INDEX]; // Generic storage...
} ListElement;


If I store double data in the "Data" member the machine will
crash since apparently it is a 32 bit SPARC, and the start of Data
is NOT aligned to an eight byte boundary.

It'll crash if you do the store by casting a pointer. It won't if you do it
with a memcpy, which is what you should do when you're treating a char array
as "generic storage".

It seems to me it'd be easier if the list implementation didn't know anything
about the type of the list elements except their size. Then you'd be forced
to use memcpy for all transactions.

 

[jacob navia]

Thanks to everybody tht answered. I think I will go the way
Gordon Burditt proposed.


jacob

 

[BartC]

If I store double data in the "Data" member the machine will
crash since apparently it is a 32 bit SPARC, and the start of Data
is NOT aligned to an eight byte boundary.

One solution (albeit very ugly) is:

typedef struct _ListElement {
struct _ListElement *Next;
double alignment1;
char Data[MINIMUM_ARRAY_INDEX]; // Generic storage...
} ListElement;

Why not just insert a 4-byte 'alignment1' element, but conditionally. So
that it is only used for a machine known to be a 32-bit SPARC. This will
need to be done manually somewhere, unless the compiler for that machine
already has an identifying macro.

This would cost 4 bytes on SPARC and 0 elsewhere. Inserting an 8-byte field
unconditionally would cost 12 bytes on SPARC, and at least 8 bytes
elsewhere.

Unions might work, but usually mean rewriting all the code (because the name
of the union has to be specified on each access, for most compilers).

Alternatively, don't compilers have a 'pack' directive for exactly this
purpose? Again this would be conditional. Ideally a way of controlling
alignment on a field-by-field basis is needed.

 

[Alan Curry]

Thanks to everybody tht answered. I think I will go the way
Gordon Burditt proposed.

There's another answer that we forgot:

Put the array at the beginning of the struct. Then if the struct is malloced,
the array inherits its "aligned for anything" property.

 

[jacob navia]

Le 01/12/11 21:38, Alan Curry a écrit :

There's another answer that we forgot:

Put the array at the beginning of the struct. Then if the struct is malloced,
the array inherits its "aligned for anything" property.

I can't do that since I do not know how big the array will be.
The user calls me with

iList.Create(sizeof(double));

to create a list of doubles.

This is a variable length structure, allocated with

malloc(sizeof(ListElement)+list->ElementSize);

The data start immediately after the pointer.

Now, there are two solutions to this:

1) Use a specific version of lists for integers, doubles, etc.
2) Align the data at run time to a miltiple of 8 or 16:

We would have

iList.CreateAligned(sizeof(double),8);

This special version of Create would align to 8 or whatever bytes
its data.

Or I could modify the Create function to align data in a machine
specific way in each machine.


The problem is further complicated by the fact that under SPARC
modern versions you do NOT need to align anything since the OS
catches the unaligned trap, and loads the double with 2 instructions.

Now the problem is that modern versions of gcc (and that machine has
4.2 installed) follow the recommendations of Oracle (ex Sun) and
emit ldd instead of a sequence of two ld instructions expecting
the OS to trap that. But since that machine has an OS from May
2002 (imagine that, almost ten years old) that apparently does NOT
catch that unaligned instruction.

Anyway, this is a general problem since the power PC has probably
similar problems.

 

[Ian Collins]

Le 01/12/11 21:38, Alan Curry a écrit :
I can't do that since I do not know how big the array will be.
The user calls me with

iList.Create(sizeof(double));

to create a list of doubles.

This is a variable length structure, allocated with

malloc(sizeof(ListElement)+list->ElementSize);

The data start immediately after the pointer.

In that case, wouldn't it have been better to declare char Data[]?

But then again, you can't use a flexible array in a nested union.

The problem is further complicated by the fact that under SPARC
modern versions you do NOT need to align anything since the OS
catches the unaligned trap, and loads the double with 2 instructions.

That's an expensive option, or at least it used to be on older
processors. The Sun compilers support misaligned access (through the
-xmemalign option), but transferring to trap handler is a significant
overhead.

Now the problem is that modern versions of gcc (and that machine has
4.2 installed) follow the recommendations of Oracle (ex Sun) and
emit ldd instead of a sequence of two ld instructions expecting
the OS to trap that. But since that machine has an OS from May
2002 (imagine that, almost ten years old) that apparently does NOT
catch that unaligned instruction.

Anyway, this is a general problem since the power PC has probably
similar problems.

The joys of portable code!

 

[Keith Thompson]

Alternatively, don't compilers have a 'pack' directive for exactly this
purpose? Again this would be conditional. Ideally a way of controlling
alignment on a field-by-field basis is needed.

Yes, some compilers have a pack directive, but it doesn't always work.

For example, on SPARC, attempting to access a misaligned object causes
the program to crash. Here's a program that uses gcc's
__attribute__((packed)) extension:

#include <stdio.h>
int main(void) {
struct unpacked {
char c;
double d;
};

struct packed {
char c;
double d;
} __attribute__((packed));

struct unpacked u[2] = { { 'u', 1.2 }, { 'U', 3.4 } };
struct packed p[2] = { { 'p', 5.6 }, { 'P', 7.8 } };
double *up0 = &u[0].d;
double *up1 = &u[1].d;
double *pp0 = &p[0].d;
double *pp1 = &p[1].d;

printf("*up0 = %g\n", *up0);
printf("*up1 = %g\n", *up1);
printf("*pp0 = %g\n", *pp0);
printf("*pp1 = %g\n", *pp1);

return 0;
}

And here's the output I got:

*up0 = 1.2
*up1 = 3.4
Bus error

If you refer to the misaligned member directly, so the compiler
knows that it's misaligned, it can access it correctly. If you've
saved a pointer to the misaligned member, there's no way for the
compiler to know that it's misaligned.

 

[ImpalerCore]

I can't do that since I do not know how big the array will be.
The user calls me with

iList.Create(sizeof(double));

to create a list of doubles.

This is a variable length structure, allocated with

        malloc(sizeof(ListElement)+list->ElementSize);

The data start immediately after the pointer.

Now, there are two solutions to this:

1) Use a specific version of lists for integers, doubles, etc.
2) Align the data at run time to a miltiple of 8 or 16:

3) Use void* pointers and live with double malloc calls.

The downside to this solution is that populating a list element now
takes two calls to malloc, one for the ListElement, the other for the
actual data.

The upside is that in addition to being free of alignment issues,
keeping the allocation separate from the list node is that one can
have a 'master' list of data, and create views of that data without
reallocating the original data. When you pack the data in with list
node, any filtered view of that data requires a copy of the actual
data. This may not be a big problem for doubles, but when you're in
my scenario where each element is a 128 byte blob where a single
flight runs on the order of 10+ million elements, the overhead for
creating views becomes a big headache. This kind of usage in my
problem domain has lead me to prefer a separate allocation for data.

If malloc becomes a bottleneck, one could resort to parameterizing the
list allocator with a function pointer and reference an allocator that
optimizes for equal sized blocks. You could use a 'chunk_malloc' for
the constant sized ListElement, and any constant sized list object
(like double, but not variable length strings using char*). I've not
had time to attempt it yet, so I don't know what kind of gains could
be made.

If you prefer to pack the data in with the list node, and you had
access to a ALIGN_MAX constant, which Chris Thomasson has proposed
before using union and offsetof, one could pack the allocation and do
something like 'malloc(maxalignof(ListElement)+list->ElementSize)'
where maxalignof would round 'sizeof (ListElement)' to the next
greatest multiple of ALIGN_MAX, and assign your pointers to aligned
addresses in the memory blob that way. The 'maxalignof' would
probably have to be a function evaluated at runtime, rather than an
operator like 'sizeof'.

Best regards,
John D.

 

[James]

I am trying to test the containers library in different environments

One of those is SUN sparc, that crashes when a double is accessed
in an address not multiple of 8. I got an access to an old one:

: ~/ccl ; uname -a
SunOS 5.9 Generic_118558-25 sun4u sparc SUNW,Sun-Fire-V210

Now, I have a list container with elements that
have this structure:

typedef struct _ListElement {
struct _ListElement *Next;
char Data[MINIMUM_ARRAY_INDEX]; // Generic storage...
} ListElement;


If I store double data in the "Data" member the machine will
crash since apparently it is a 32 bit SPARC, and the start of Data
is NOT aligned to an eight byte boundary.

[...]

You could examine this region allocator code, perhaps is might of some
interest:

http://groups.google.com/group/comp.lang.misc/msg/f44b54d0539825b1

 

[Jorgen Grahn]

On 12/ 2/11 09:50 AM, jacob navia wrote: ....

That's an expensive option, or at least it used to be on older
processors. The Sun compilers support misaligned access (through the
-xmemalign option), but transferring to trap handler is a significant
overhead.

*sigh*

Are people still playing that stupid game? If it's an overhead of
100x or 1000x like I've seen on some ARM systems, it's much better to
crash. In one project I'm in, we're kind of sorry we abandoned the
Sparc architecture -- because it reveals problems like this one.

/Jorgen

 

[Ian Collins]

*sigh*

Are people still playing that stupid game? If it's an overhead of
100x or 1000x like I've seen on some ARM systems, it's much better to
crash. In one project I'm in, we're kind of sorry we abandoned the
Sparc architecture -- because it reveals problems like this one.

The last time I played that "stupid game" I had little choice. The code
I was testing was developed for an embedded 68K target, where alignment
wasn't an issue.

That compiler option really is a quick and nasty hack to help porting
poor code to Sparc.

 

[Brain]

Dude, you are boring me to death.

 

[Keith Thompson]

Dude, you are boring me to death.

Dude, stop changing your name; I'm tired of updating my killfile every
time you morph.

 

[Phil Carmody]

Dude, stop changing your name; I'm tired of updating my killfile every
time you morph.

Who do you think he is? His volume's previously been low enough that
I've relied on repeated use of 'n' rather than 'L a s p <ret>', but
apparently his volume's increasing. Rather tempted to just stick
spameranza.aioe.org in the filters, and get rid of everyone unaware
of its reputation. (My sci.crypt filters have that enabled already,
for example; I don't believe I'm missing anything.)

Phil

 

[Keith Thompson]

Who do you think he is?

[...]

I had already killfiled Brian <[email protected]>; I'm assuming
(perhaps incorrectly) that "Brain" <[email protected]> is the
same person.

 

[lovecreatesbeauty]

Keith Thompson (The_Other_Keith) (e-mail address removed)  <http://www.ghoti.net/~kst>
    Will write code for food.

Hi Keith, did you quit nokia?

 

[Keith Thompson]

Hi Keith, did you quit nokia?

<OT>They quit me.</OT>

 

[Phil Carmody]

<OT>They quit me.</OT>

Ah, but they've only done that once to you - they've now done it
three times to me! (Sold me to Marconi in 2000, outsourced me to
Tieto-Enator in 2003, and finally of course Feb 11.)

Then again, it works both ways. I've quit this current Nokia gig
twice (and even left the country) but apparenty I'm still working
there.

I can't work out who's the Matti Nykanen, and who's the Mervi
Tapola.

Phil