_Alignof Limitations

[Shao Miller]

Suppose we've the unfortunate:

typedef struct { char c; int x; } * foo_t;

Now suppose we wish to produce an object with the referenced type of the
'foo_t' pointer type, and we wish that object to have automatic storage:

foo_t foo;
_Alignas (_Alignof (*foo)) unsigned char substrate[sizeof *foo];

foo = (void *) substrate;

Oh but wait, you can't do that with '_Alignof'.

unsigned char pool[sizeof *foo * 2];

Somewhere in 'pool', there is a byte that is suitably aligned for an
object of the referenced type, and is followed by sufficient storage, if
we... Just... Knew... Where... :(

/* Loved */
foo = malloc(sizeof *foo);
free(foo);

/* D'oh. Doesn't work this way */
foo = aligned_alloc(_Alignof (*foo), sizeof *foo);

Is there an easy or a clever way to figure out the alignment of the
referenced type?

--
- Shao Miller
--
"Thank you for the kind words; those are the kind of words I like to hear.

Cheerily," -- Richard Harter

[Russell Shaw]

On 18/03/13 13:33, Shao Miller wrote:
> Suppose we've the unfortunate:
>
> typedef struct { char c; int x; } * foo_t;
>
> Now suppose we wish to produce an object with the referenced type of the 'foo_t'
> pointer type, and we wish that object to have automatic storage:
>
> foo_t foo;
> _Alignas (_Alignof (*foo)) unsigned char substrate[sizeof *foo];
>
> foo = (void *) substrate;
>
> Oh but wait, you can't do that with '_Alignof'.
>
> unsigned char pool[sizeof *foo * 2];
>
> Somewhere in 'pool', there is a byte that is suitably aligned for an object of
> the referenced type, and is followed by sufficient storage, if we... Just...
> Knew... Where... :(
>
> /* Loved */
> foo = malloc(sizeof *foo);
> free(foo);
>
> /* D'oh. Doesn't work this way */
> foo = aligned_alloc(_Alignof (*foo), sizeof *foo);
>
> Is there an easy or a clever way to figure out the alignment of the referenced
> type?

What are you trying to do with the alignment of the referenced type?

The stack struct will already get the alignment of "int" or coarser.

The malloc struct will already get the coarsest alignment of "double".

[Shao Miller]

Declare an object suitable for the referenced type: Suitable size &
alignment, and not breaking any effective type rules.

> The stack struct will already get the alignment of "int" or coarser.
>

That would be handy. Where can I find out more about that?

> The malloc struct will already get the coarsest alignment of "double".

I am under the impression that 'malloc' returns storage that is suitably
aligned for any type, and that 'double' isn't relevant. Which resource
has more detail about this situation?

Thanks. :)

[Keith Thompson]

Shao Miller <sha0....@gmail.com> writes:
> On 3/18/2013 07:03, Russell Shaw wrote:

[...]

>> The malloc struct will already get the coarsest alignment of "double".
>
> I am under the impression that 'malloc' returns storage that is suitably
> aligned for any type, and that 'double' isn't relevant. Which resource
> has more detail about this situation?

N1570 7.20.3:

The pointer returned if the allocation succeeds is suitably
aligned so that it may be assigned to a pointer to any type
of object and then used to access such an object or an array
of such objects in the space allocated (until the space is
explicitly deallocated).

On many, but by no means all, implementations "double" happens to
have the strictest alignment. I've worked on systems where the
alignment of "long double" is the same, less strict, and more strict
than the alignment of "double".

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Russell Shaw]

I don't quite understand.

Just declaring:

struct { char c; int x; } mystruct;

declares a stack object with suitable size & alignment.

>> The stack struct will already get the alignment of "int" or coarser.
>>
>
> That would be handy. Where can I find out more about that?
>
>> The malloc struct will already get the coarsest alignment of "double".
>
> I am under the impression that 'malloc' returns storage that is suitably aligned
> for any type, and that 'double' isn't relevant. Which resource has more detail
> about this situation?

The C Programming Language (2nd Edition) by Brian W. Kernighan, and Dennis M.
Ritchie has a malloc allocator that explains the alignment.

[Shao Miller]

How do you know that there are the same number of padding bytes between
these two members as in the original pointer type's referenced type?
How do you know the alignment requirement is the same?

>>> The stack struct will already get the alignment of "int" or coarser.
>>>
>>
>> That would be handy. Where can I find out more about that?
>>
>>> The malloc struct will already get the coarsest alignment of "double".
>>
>> I am under the impression that 'malloc' returns storage that is
>> suitably aligned
>> for any type, and that 'double' isn't relevant. Which resource has
>> more detail
>> about this situation?
>
> The C Programming Language (2nd Edition) by Brian W. Kernighan, and
> Dennis M. Ritchie has a malloc allocator that explains the alignment.

Do they mention that 'double' always has the strictest alignment
requirement for all implementations?

Thanks for the information.

[Keith Thompson]

Shao Miller <sha0....@gmail.com> writes:
> On 3/18/2013 21:51, Russell Shaw wrote:

[...]

>> The C Programming Language (2nd Edition) by Brian W. Kernighan, and
>> Dennis M. Ritchie has a malloc allocator that explains the alignment.
>
> Do they mention that 'double' always has the strictest alignment
> requirement for all implementations?

It doesn't, so I seriously doubt it.

[Shao Miller]

On 3/19/2013 00:56, Keith Thompson wrote:
> Shao Miller <sha0....@gmail.com> writes:
>> On 3/18/2013 21:51, Russell Shaw wrote:
> [...]
>>> The C Programming Language (2nd Edition) by Brian W. Kernighan, and
>>> Dennis M. Ritchie has a malloc allocator that explains the alignment.
>>
>> Do they mention that 'double' always has the strictest alignment
>> requirement for all implementations?
>
> It doesn't, so I seriously doubt it.
>

Yeah, from your other post and from what I've read in the Standard, I
didn't think so. But that would've been interesting, if they had.

In C11, I believe 'malloc' returns storage whose alignment satisfies
'_Alignof(max_align_t)'. I guess that's the only way to be safe for the
original problem of the referenced type, but potentially wasteful.

[Russell Shaw]

On 19/03/13 15:30, Shao Miller wrote:
> On 3/18/2013 21:51, Russell Shaw wrote:
>> On 19/03/13 02:24, Shao Miller wrote:
>>> On 3/18/2013 07:03, Russell Shaw wrote:
>>>> On 18/03/13 13:33, Shao Miller wrote:

...

>>> Declare an object suitable for the referenced type: Suitable size &
>>> alignment,
>>> and not breaking any effective type rules.
>>
>> I don't quite understand.
>>
>> Just declaring:
>>
>> struct { char c; int x; } mystruct;
>>
>> declares a stack object with suitable size & alignment.
>>
>
> How do you know that there are the same number of padding bytes between these
> two members as in the original pointer type's referenced type? How do you know
> the alignment requirement is the same?

The compiler sets the alignment of the struct to match it's worst case member,
"int".

Because "char c" comes first it'll be aligned as if it were an "int", so there
will be padding between "c" and "x". All object instances of this struct will
get aligned and padded the same way by the compiler.

[James Kuyper]

On 03/19/2013 05:33 AM, Russell Shaw wrote:
> On 19/03/13 15:30, Shao Miller wrote:
>> On 3/18/2013 21:51, Russell Shaw wrote:

...

>>> I don't quite understand.
>>>
>>> Just declaring:
>>>
>>> struct { char c; int x; } mystruct;
>>>
>>> declares a stack object with suitable size & alignment.
>>>
>>
>> How do you know that there are the same number of padding bytes between these
>> two members as in the original pointer type's referenced type? How do you know
>> the alignment requirement is the same?
>
> The compiler sets the alignment of the struct to match it's worst case member,
> "int".

Not necessarily - the alignment could be stricter. Some systems impose a
minimum alignment for struct types, which could be greater than that for
'int'.

> Because "char c" comes first it'll be aligned as if it were an "int", so there

> will be padding between "c" and "x". ...

Except in those rare cases where sizeof(int)==1.

> ... All object instances of this struct will

> get aligned and padded the same way by the compiler.

There's neither a struct tag nor a typedef name attached to that struct
type; the only way another object could have the same type as mystruct
is by being defined in the same declaration as mystruct. Anywhere else,
a declaration of a different identifier with exactly the same struct
definition would have a different type, and could therefore, in
principle, have different alignment characteristics.

That's extremely unlikely to be the case. First of all, there's no
obvious reason for ever inserting more than the absolute minimum amount
of padding needed to achieve the required alignment. Secondly, identical
struct definitions used in different translation units must be
compatible; it's only when they occur within the same translation unit
that they're incompatible. The easiest way to achieve this is to
implement then identically even when in the same translation unit.
However, in principle, a fully conforming implementation could check
whether a given unnamed struct type is ever used in a way that could
require it to be compatible with a struct type declared in some other
translation unit. If not, it could randomly choose the amount of
padding, constrained only by the requirement that the mystruct and
mystruct.x must both be aligned correctly for 'int'.

If you want to guarantee that two structs not declared in the same
declaration have the same layout, you should name the struct type, with
either a struct tag or a typedef, so you can explicitly declare them to
have the same type. That's what the tag is there for.
--
James Kuyper

[Marc]

Shao Miller wrote:

> I am under the impression that 'malloc' returns storage that is suitably
> aligned for any type,

Except the over-aligned ones. But that's irrelevant to this conversation,
you don't seem to be using any of those, so forget my remark.

[Wojtek Lerch]

On 19-Mar-13 7:37 AM, James Kuyper wrote:
> First of all, there's no
> obvious reason for ever inserting more than the absolute minimum amount
> of padding needed to achieve the required alignment.

What constitutes the "required alignment" is, to a degree, up to the
compiler, and is not necessary the same as the absolute minimum of
padding. It can be a matter of a tradeoff between space and speed --
aligning everything for maximum speed will often add a substantial
amount of padding, whereas tighter packing may require extra opcodes or
maybe just more processor cycles. Conceivably, a compiler could choose
its "official" alignment requirements to be somewhere in the middle.
For instance, a compiler could align 64-bit integers on a 32-bit
boundary if the processor accesses them 32 bits at a time most of the
time, even if aligning them on a 64-bit boundary might make some
operations a little faster. Other compilers for the same hardware could
choose differently.

[Dag-Erling Smørgrav]

Wojtek Lerch <wojt...@yahoo.ca> writes:
> Conceivably, a compiler could choose its "official" alignment

> requirements to be somewhere in the middle. [...] Other compilers

> for the same hardware could choose differently.

In practice, any compiler that does not conform to the target platform's
ABI (which specifies alignment, padding, calling conventions etc.) is
doomed to either sink into obscurity or rise to infamy.

DES
--
Dag-Erling Smørgrav - d...@des.no

[Keith Thompson]

Russell Shaw <rjshawN_o@s_pam.netspace.net.au> writes:
> On 19/03/13 15:30, Shao Miller wrote:
>> On 3/18/2013 21:51, Russell Shaw wrote:
>>> On 19/03/13 02:24, Shao Miller wrote:
>>>> On 3/18/2013 07:03, Russell Shaw wrote:
>>>>> On 18/03/13 13:33, Shao Miller wrote:
>
> ...
>
>>>> Declare an object suitable for the referenced type: Suitable size &
>>>> alignment,
>>>> and not breaking any effective type rules.
>>>
>>> I don't quite understand.
>>>
>>> Just declaring:
>>>
>>> struct { char c; int x; } mystruct;
>>>
>>> declares a stack object with suitable size & alignment.
>>>
>>
>> How do you know that there are the same number of padding bytes between these
>> two members as in the original pointer type's referenced type? How do you know
>> the alignment requirement is the same?
>
> The compiler sets the alignment of the struct to match it's worst case member,
> "int".

To match *at least* its worst case member. And we know that that's the
int in this case only because char has to have 1-byte alignment.

> Because "char c" comes first it'll be aligned as if it were an "int",

Or the compiler could choose to align the structure even more strictly
than an int. For example, if int is 4 bytes it could put c at offset 0
and x at offset 4 making the whole structure 8 bytes. The compiler
might choose to impose 8-byte alignment on the structure, so it can
easily be manipulated as a single 8-byte object.

> so there
> will be padding between "c" and "x".

Not necessarily. int might have have 1-byte alignment, either because
sizeof (int) == 1 (which requires CHAR_BIT >= 16), or because the
hardware doesn't require any stricter alignment for int. Perhaps
"misaligned" words can be accessed as efficiently as aligned words, or
perhaps the compiler is optimizing for memory usage rather than speed.

> All object instances of this struct will
> get aligned and padded the same way by the compiler.

Given the declaration above, there is only one instance of the struct
type. Instances of identical struct types will *probably* have the
same representation, but that's not required in all cases.

[Hans-Bernhard Bröker]

On 19.03.2013 16:02, Dag-Erling Smørgrav wrote:
> In practice, any compiler that does not conform to the target platform's
> ABI (which specifies alignment, padding, calling conventions etc.)

That's assuming there _is_ such a thing as an ABI for the target
platform in question. Small-ish embedded systems usually don't have any.

[Philip Lantz]

James wrote the statement you quoted in the context of whether a
compiler might use a different amount of internal padding in two structs
whose members are the same. He wasn't in any way questioning the
compiler's complete authority to use whatever alignment it chooses. Your
response doesn't say anything about why a compiler might vary its
alignment choices for the same member types, so it really has nothing to
do with what James was writing about.

[Wojtek Lerch]

Well I was trying to make some points that I still think are related,
but maybe I wasn't making them clearly enough. Let me try again:

* The only "absolute minimum" is zero padding. No matter what the
hardware requirements are, it's never impossible for a compiler to work
around them. If course, often this may require massive overhead;
avoiding this overhead counts as an obvious reason to insert more than
the real absolute minimum (zero) of padding in my book.

* I strongly suspect that James meant something else when he wrote
"absolute minimum"; but given the above I'd argue that no other
"minimum" deserves to be called "absolute".

* The amount of padding generally affects data size and code speed and
may affect code size. If a structure type is declared with a scope
small enough to allow the compiler to fully analyze its usage,
conceivably the compiler might make a different decision about the
relative importance of size versus speed for that structure, compared to
similar structure types declared elsewhere in the program. For
instance, when one struct type declares a huge array that is not used
much, and another struct with an identical specifier is used to declare
just one local object whose members are referenced a lot in an inner
loop of a function, the compiler may tightly pack the first one to save
memory but insert padding into the second one to save time.

[James Kuyper]

I was not talking about the minimum over all possible implementations,
but rather the minimum over all permitted amounts of padding of that
struct for a particular implementation of C. For any given
implementation of C, _Alignof(int) has a single specific value. If that
value is > 1, then the minimum permitted amount of padding will be >0,
and all other permitted amounts of padding will differ from that one by
integer multiples of _Alignof(int).

> * I strongly suspect that James meant something else when he wrote
> "absolute minimum"; but given the above I'd argue that no other
> "minimum" deserves to be called "absolute".

The minimum over all possible implementations, while arguably more
"absolute" than the minimum I was talking about, is too trivial to be of
any interest.

[Wojtek Lerch]

On 20-Mar-13 11:51 AM, James Kuyper wrote:
> On 03/20/2013 11:06 AM, Wojtek Lerch wrote:
>>>> James Kuyper wrote:
>>>>> First of all, there's no
>>>>> obvious reason for ever inserting more than the absolute minimum amount
>>>>> of padding needed to achieve the required alignment.

...

>> Let me try again:
>>
>> * The only "absolute minimum" is zero padding. No matter what the
>> hardware requirements are, it's never impossible for a compiler to work
>> around them. If course, often this may require massive overhead;
>> avoiding this overhead counts as an obvious reason to insert more than
>> the real absolute minimum (zero) of padding in my book.
>
> I was not talking about the minimum over all possible implementations,
> but rather the minimum over all permitted amounts of padding of that
> struct for a particular implementation of C. For any given
> implementation of C, _Alignof(int) has a single specific value. If that
> value is > 1, then the minimum permitted amount of padding will be >0,
> and all other permitted amounts of padding will differ from that one by
> integer multiples of _Alignof(int).

OK, but my point is that it's up to the implementation. It's a minimum
that the implementation chooses to impose on itself, and as we agree
different implementations can choose differently. If an implementation
chooses to allow tight packing with little padding, it may still decide
to align variables for speed.

As an example, the x86 has a switch that lets the (system) programmer
decide whether unaligned accesses should be allowed or cause a trap. If
they're allowed, they're much slower than aligned accesses but don't
require any special treatment from the compiler. If a compiler knows
that this switch is always enabled on the platform that it's generating
code for, I don't think it would be outrageously unreasonable for it to
return 1 for _Alignof(int) and allow people to manufacture pointers to
unaligned ints, but still align all declared ints for fastest possible
access. (Or maybe just most ints, and make exceptions to avoid
structures with a high padding-to-data ratio.) Would that qualify as
inserting more padding than your "absolute minimum"?

>> * I strongly suspect that James meant something else when he wrote
>> "absolute minimum"; but given the above I'd argue that no other
>> "minimum" deserves to be called "absolute".
>
> The minimum over all possible implementations, while arguably more
> "absolute" than the minimum I was talking about, is too trivial to be of
> any interest.

No disagreement there, except about whether "less absolute" still
qualifies as "absolute". :)

[James Kuyper]

On 03/20/2013 01:06 PM, Wojtek Lerch wrote:
> On 20-Mar-13 11:51 AM, James Kuyper wrote:

...

>> I was not talking about the minimum over all possible implementations,
>> but rather the minimum over all permitted amounts of padding of that
>> struct for a particular implementation of C. For any given
>> implementation of C, _Alignof(int) has a single specific value. If that
>> value is > 1, then the minimum permitted amount of padding will be >0,
>> and all other permitted amounts of padding will differ from that one by
>> integer multiples of _Alignof(int).
>
> OK, but my point is that it's up to the implementation. It's a minimum
> that the implementation chooses to impose on itself,

Your wording could be interpreted as implying more freedom than the
implementation actually has. For this particular struct, minimum_padding
== _Alignof(int)-1. The implementation is free to choose _Alignof(int)
to be any positive integer power of 2 (before C2011, the alignment
requirement could have been any arbitrary positive integer). The
implementation is free to choose minimum_padding to be one less than any
positive integer power of 2. But those choices are not independent,
they're directly linked. actual_padding = minimum_padding +
k*_Alignof(int), where k is an non-negative integer, and the
implementation is free to choose which one. If you did not intend to
imply that implementors have more freedom of choice than that, then
we're in agreement.

[Wojtek Lerch]

On 20-Mar-13 1:42 PM, James Kuyper wrote:
> On 03/20/2013 01:06 PM, Wojtek Lerch wrote:

> ...

> Your wording could be interpreted as implying more freedom than the
> implementation actually has. For this particular struct, minimum_padding
> == _Alignof(int)-1. The implementation is free to choose _Alignof(int)
> to be any positive integer power of 2 (before C2011, the alignment
> requirement could have been any arbitrary positive integer). The
> implementation is free to choose minimum_padding to be one less than any
> positive integer power of 2. But those choices are not independent,
> they're directly linked. actual_padding = minimum_padding +
> k*_Alignof(int), where k is an non-negative integer, and the
> implementation is free to choose which one. If you did not intend to
> imply that implementors have more freedom of choice than that, then
> we're in agreement.

I did not and we are; all I was disagreeing with is your previous claim
that there's never an obvious reason for k to be nonzero:

"First of all, there's no obvious reason for ever inserting more than
the absolute minimum amount of padding needed to achieve the required
alignment."

Of course, it's now obvious to me that the possible reason that seems
obvious to me may not necessarily be so obvious to anybody else, so
maybe that's not really a disagreement either. :)

[James Kuyper]

On 03/20/2013 03:27 PM, Wojtek Lerch wrote:
> On 20-Mar-13 1:42 PM, James Kuyper wrote:
>> On 03/20/2013 01:06 PM, Wojtek Lerch wrote:
>> ...
>> Your wording could be interpreted as implying more freedom than the
>> implementation actually has. For this particular struct, minimum_padding
>> == _Alignof(int)-1. The implementation is free to choose _Alignof(int)
>> to be any positive integer power of 2 (before C2011, the alignment
>> requirement could have been any arbitrary positive integer). The
>> implementation is free to choose minimum_padding to be one less than any
>> positive integer power of 2. But those choices are not independent,
>> they're directly linked. actual_padding = minimum_padding +
>> k*_Alignof(int), where k is an non-negative integer, and the
>> implementation is free to choose which one. If you did not intend to
>> imply that implementors have more freedom of choice than that, then
>> we're in agreement.
>
> I did not and we are; all I was disagreeing with is your previous claim
> that there's never an obvious reason for k to be nonzero:

OK - I misread your message - re-reading it, I see now that you were in
fact talking about that. It's my fault - not a problem with your
wording. I'll concede that there can be reasons for choosing non-zero
values of k; though I'd consider them to be less than perfectly obvious.
I should have worded that part of my message that a little less
emphatically, though I'm not sure what the best way to say it would be.

[Wojtek Lerch]

On 20-Mar-13 4:04 PM, James Kuyper wrote:
> I'll concede that there can be reasons for choosing non-zero
> values of k; though I'd consider them to be less than perfectly obvious.
> I should have worded that part of my message that a little less
> emphatically, though I'm not sure what the best way to say it would be.

"Less than perfectly obvious" sounds good to me. :)