Alignment (K&R question)

[sandeep]

Hello Friends ~

In K&R (Kernighan and Richie) section 8.7 we find this

< malloc is aligned properly for the objects that will be stored in it.
Although machines varyfor each machine there is a most restrictive type:
if the most restrictive type can be stored at a
particular address, all other types may be also. >

But is this true according to the C standard?

I will describe a machine. On this machine an object can have any size
and an object of size n bytes must be aligned on a multiple of n (e.g.
chars have any alignment, int32_t must be aligned on a multiple of 4
bytes, etc. ... but also a struct of size 5000 bytes must be aligned on a
multiple of 5000 bytes).

Because malloc must return an address that is good for any alignment, it
can only ever return the address zero. So that's what malloc does - it
either returns address zero or a NUL pointer for all calls.

Isn't what I have described conforming to the standard?

Regards ~

 

[Seebs]

< malloc is aligned properly for the objects that will be stored in it.
Although machines varyfor each machine there is a most restrictive type:
if the most restrictive type can be stored at a
particular address, all other types may be also. >

But is this true according to the C standard?

Yes.

Or at least, it is required that there exists an alignment suitable
for any kind of object.

I will describe a machine. On this machine an object can have any size
and an object of size n bytes must be aligned on a multiple of n (e.g.
chars have any alignment, int32_t must be aligned on a multiple of 4
bytes, etc. ... but also a struct of size 5000 bytes must be aligned on a
multiple of 5000 bytes).

But that's not what really happens -- what really happens is that the
struct must be aligned on a boundary suitable to its most-restrictive
member. Same for arrays.

Isn't what I have described conforming to the standard?

In practice, no. I am not totally sure whether it's specified formally,
but it's certainly in practice the case that alignment requirements come
only from the non-aggregate types.

-s

 

[sandeep]

Yes.

Or at least, it is required that there exists an alignment suitable for
any kind of object.


But that's not what really happens -- what really happens is that the
struct must be aligned on a boundary suitable to its most-restrictive
member. Same for arrays.


In practice, no. I am not totally sure whether it's specified formally,
but it's certainly in practice the case that alignment requirements come
only from the non-aggregate types.

-s

Yes this is what happens in practise... but does the C standard force it?
I don't believe so.....

Regards ~

 

[Keith Thompson]

In K&R (Kernighan and Richie) section 8.7 we find this

< malloc is aligned properly for the objects that will be stored in it.
Although machines varyfor each machine there is a most restrictive type:
if the most restrictive type can be stored at a
particular address, all other types may be also. >

But is this true according to the C standard?
Yes.

I will describe a machine. On this machine an object can have any size
and an object of size n bytes must be aligned on a multiple of n (e.g.
chars have any alignment, int32_t must be aligned on a multiple of 4
bytes, etc. ... but also a struct of size 5000 bytes must be aligned on a
multiple of 5000 bytes).

Because malloc must return an address that is good for any alignment, it
can only ever return the address zero. So that's what malloc does - it
either returns address zero or a NUL pointer for all calls.

Isn't what I have described conforming to the standard?

More concretely, in your hypothetical implementation a struct
of 5000 bytes requires 5000-byte alignment, and a struct of 5001
bytes requires a 5001-byte alignment. The smallest alignment that
satisfies both is 25005000 bytes. Throw in a few other sizes, and
you very quickly reach the point where only address 0 can satisfy
all possible alignment requirements.

That's exactly why such alignment requirements don't exist in real
life, and the C standard doesn't expend any effort to meet them.

In practice, there's always some alignment that's good enough for all
possible objects. It might be, say, 8 or 16 bytes. In some special
cases, there might be some advantage to, say, 1024-byte alignment,
but that's usually not a requirement (you might get faster code if
something is 1024-byte aligned, but making it 8-byte aligned still
works with a slight performance penalty).

There are all sorts of requirements that a machine can impose
that make it difficult or impossible to provide a conforming C
implementation. In practice, the C standard's requirements are
designed to cover a very wide variety of possible machines, and
machines are designed with the C standard's requirements in mind,
at least indirectly.

 

[sandeep]

More concretely, in your hypothetical implementation a struct of 5000
bytes requires 5000-byte alignment, and a struct of 5001 bytes requires
a 5001-byte alignment. The smallest alignment that satisfies both is
25005000 bytes. Throw in a few other sizes, and you very quickly reach
the point where only address 0 can satisfy all possible alignment
requirements.

That's exactly why such alignment requirements don't exist in real life,
and the C standard doesn't expend any effort to meet them.

Hello Kieth ~

You have completely misread my question! I already said that on my
imagined machine, the only non-NUL pointer that malloc ever returns is
the zero address!

Regards ~

 

[Eric Sosman]

[...]
I will describe a machine. On this machine an object can have any size
and an object of size n bytes must be aligned on a multiple of n (e.g.
chars have any alignment, int32_t must be aligned on a multiple of 4
bytes, etc. ... but also a struct of size 5000 bytes must be aligned on a
multiple of 5000 bytes).

On your machine, what is the sizeof

union {
char II[2];
char III[3];
char V[5];
char VI[7];
char XI[11];
char XII[13];
...
char XCVII[97];
} alignMe;

? I make it about 2e27 gigabytes. (Keep in mind that sizeof
includes any padding that's inserted for alignment's sake.)

If this is a conforming implementation (which I sort of
doubt), it has extremely low QoI.

 

[Seebs]

Yes this is what happens in practise... but does the C standard force it?
I don't believe so.....

Ah-hah!

6.2.5

(paragraph 27)
"All pointers to structure types shall have the same representation
and alignment requirements as each other. All pointers to union
types shall have the same representation and alignment requirements
as each other."

So the alignment requirements of two different structure types can't be
different, so the hypothetical implementation where a larger struct has
a stricter alignment requirement is prohibited.

For clarification, we have 6.3.2.3's footnote 57:

In general, the concept ''correctly aligned''
is transitive: if a pointer to type A is correctly aligned
for a pointer to type B, which in turn is correctly aligned
for a pointer to type C, then a pointer to type A is
correctly aligned for a pointer to type C.

We now have the following information:

1. A pointer to a structure, suitably converted, is a valid pointer to
its first member.
2. That conversion does not change the address, so the first object in
the structure is at the same location as the structure, and thus, the
structure must be suitably aligned for its first member.
3. All structure pointers must have the same alignment requirements -- as
in, there must exist some alignment adequate to point to any structure.
4. Any object may be the first member of a structure.

Conclusion: There must exist some alignment which is aligned for all
possible objects, as you could declare a pair of structures with each of
two object types as their first member, and since the structures must have
compatible alignment, and must be suitably aligned for their first members,
the objects must then also have suitable alignment.

We can also get further:
1. There is no padding in arrays.
2. Every object in an array is suitably aligned.
Therefore:
3. No object has alignment requirements stricter than its size.
Therefore:
4. A structure's alignment requirement cannot be stricter than the size
of the largest non-aggregate type.

Now, if you want, you could make a system with CHAR_BIT=8 and int40000_t,
which is a 5000-byte integer, but then your problem is solved; the maximum
alignment requirement is 5000 bytes. You have to be able to declare a
structure starting with an array[2] of int40000_t, and any other object has
to have compatible alignment.

-s

 

[Keith Thompson]

Hello Kieth ~

It's "Keith", not "Kieth". (Don't worry about it too much;
unintentional misspellings of my name don't offend me.)

You have completely misread my question! I already said that on my
imagined machine, the only non-NUL pointer that malloc ever returns is
the zero address!

How did I misread it? I understand what you said, and I agreed
with it.

On your imagined machine (assuming the zero address and the null
pointer are not the same), there could probably be a conforming C
implementation, but it wouldn't be very useful. There could be at
most one malloc-allocated object at a time in a given program.

My point was that the C standard doesn't and shouldn't make any
particular effort to support such machines, because in practice
they don't exist.

What did I miss?

 

[bartc]

I will describe a machine. On this machine an object can have any size
and an object of size n bytes must be aligned on a multiple of n (e.g.
chars have any alignment, int32_t must be aligned on a multiple of 4
bytes, etc. ... but also a struct of size 5000 bytes must be aligned on a
multiple of 5000 bytes).

How many of these machines are you planning to sell?

Because malloc must return an address that is good for any alignment, it
can only ever return the address zero. So that's what malloc does - it
either returns address zero or a NUL pointer for all calls.

Isn't what I have described conforming to the standard?

There is only one way to interpret the standard in a meaningful way: that is
for any pointer to a struct to be a properly aligned pointer it's first
element, and to stay properly aligned when stepped to each of the remaining
elements.

To achieve this, only the size of the largest element need be taken into
account. (When elements are arrays, then the pointer to the first element is
considered; and when an element is itself a struct, the process is
repeated.)

This means only the size of primitive types need be considered by malloc,
and it will likely use the size of the largest primitive to determine a
standard alignment to use.

Your hypothetical hardware doesn't ring true: even if it is capable of
primitive types of variable and unlimited size, a C implementation only
requires a few small primitives; the 5000-struct will consist of collections
of these.

If your design has integers of, say 40000-bits, then even here, C can only
really cope with a small number of these. But then your design might be
almost as impractical as a machine with a single wordsize of 32Gbits, and a
memory of 4GB: it can only ever store one integer.

 

[Eric Sosman]

Ah-hah!

6.2.5

(paragraph 27)
"All pointers to structure types shall have the same representation
and alignment requirements as each other. All pointers to union
types shall have the same representation and alignment requirements
as each other."

So the alignment requirements of two different structure types can't be
different, so the hypothetical implementation where a larger struct has
a stricter alignment requirement is prohibited.

You've misread, I think. All struct *pointers* have the same
alignment requirement, not all the structs they point at -- and
similarly for unions. (All struct pointers smell the same, and
all union pointers smell the same, but struct pointers and union
pointers can smell different.)

For clarification, we have 6.3.2.3's footnote 57:

In general, the concept ''correctly aligned''
is transitive: if a pointer to type A is correctly aligned
for a pointer to type B, which in turn is correctly aligned
for a pointer to type C, then a pointer to type A is
correctly aligned for a pointer to type C.

We now have the following information:

1. A pointer to a structure, suitably converted, is a valid pointer to
its first member.
2. That conversion does not change the address, so the first object in
the structure is at the same location as the structure, and thus, the
structure must be suitably aligned for its first member.
3. All structure pointers must have the same alignment requirements -- as
in, there must exist some alignment adequate to point to any structure.
4. Any object may be the first member of a structure.

Conclusion: There must exist some alignment which is aligned for all
possible objects, as you could declare a pair of structures with each of
two object types as their first member, and since the structures must have
compatible alignment, and must be suitably aligned for their first members,
the objects must then also have suitable alignment.

Again, the "same alignment" language you've quoted applies
to the pointer objects themselves, not to their targets.

We can also get further:
1. There is no padding in arrays.
2. Every object in an array is suitably aligned.
Therefore:
3. No object has alignment requirements stricter than its size.

We can do better still: The alignment requirement for any
type T is an exact divisor of sizeof(T).

Therefore:
4. A structure's alignment requirement cannot be stricter than the size
of the largest non-aggregate type.

Doesn't follow. `struct one { char c; }' might require four-
byte alignment, for example, without violating any of 1,2,3.

 

[Keith Thompson]

Ah-hah!

6.2.5

(paragraph 27)
"All pointers to structure types shall have the same representation
and alignment requirements as each other. All pointers to union
types shall have the same representation and alignment requirements
as each other."

So the alignment requirements of two different structure types can't be
different, so the hypothetical implementation where a larger struct has
a stricter alignment requirement is prohibited.

No, that refers to the alignment *of the pointer* (i.e., of an
object of pointer type), not the alignment of the structure.

Typically all pointer-to-struct types have a size of, say, 4 or 8 bytes
and require 4-byte or 8-byte alignment. The point of 6.2.5p27 is to
forbid an implementation, where for example, sizeof(struct tiny*) == 8
and sizeof(struct huge*) == 4.

I would expect
struct { char c; }
and
struct { long double x; }
to have different alignment requirements in most implementations.

[snip]

 

[Ben Bacarisse]

Ah-hah!

6.2.5

(paragraph 27)
"All pointers to structure types shall have the same representation
and alignment requirements as each other. All pointers to union
types shall have the same representation and alignment requirements
as each other."

So the alignment requirements of two different structure types can't be
different, so the hypothetical implementation where a larger struct has
a stricter alignment requirement is prohibited.

I don't think that is what that paragraph is about. I read it as
describing the representation and alignment for objects of type pointer
to struct, rather than describing the representation of the pointer and
the alignment of the structures to which they point. It's certainly
ambiguous, in part because of the footnote you quote below, but the
context is all about the requirements on various derived types (pointers
in this case) not about the types from which they are derived.

If it meant what you say, why would anyone bother to use the trick of a
union with a whole bunch of types in it to try to get a maximally
aligned address? As you go on to argue, if all structs must have the
same alignment requirement then this must be the strictest possible
requirement so a simple struct { char c; } would be enough.

For clarification, we have 6.3.2.3's footnote 57:

In general, the concept ''correctly aligned''
is transitive: if a pointer to type A is correctly aligned
for a pointer to type B, which in turn is correctly aligned
for a pointer to type C, then a pointer to type A is
correctly aligned for a pointer to type C.

This seems to be simply using the same phrase to mean something else. I
think the situation could be clarified by using "address" here and
leaving the wording about pointers alone. Because an address is a
value, its "alignment" refers unambiguously to thing it is an address
of. A pointer can be both a value and an object with an alignment all
of its own.

<snip>

 

[Seebs]

I don't think that is what that paragraph is about. I read it as
describing the representation and alignment for objects of type pointer
to struct, rather than describing the representation of the pointer and
the alignment of the structures to which they point.

You're quite right. I was clearly confused.

This seems to be simply using the same phrase to mean something else. I
think the situation could be clarified by using "address" here and
leaving the wording about pointers alone. Because an address is a
value, its "alignment" refers unambiguously to thing it is an address
of. A pointer can be both a value and an object with an alignment all
of its own.

Right.

So on thinking about it, I think sandeep's probably right in theory --
you could make an implementation where many types had extremely odd
alignment requirements. And this would cripple malloc(). That would
suck, and no one would buy it.

-s

 

[Richard Bos]

In K&R (Kernighan and Richie) section 8.7 we find this

< malloc is aligned properly for the objects that will be stored in it.
Although machines varyfor each machine there is a most restrictive type:
if the most restrictive type can be stored at a
particular address, all other types may be also. >

But is this true according to the C standard?

In practice, yes, although it is not put like that.

I will describe a machine. On this machine an object can have any size
and an object of size n bytes must be aligned on a multiple of n (e.g.
chars have any alignment, int32_t must be aligned on a multiple of 4
bytes, etc. ... but also a struct of size 5000 bytes must be aligned on a
multiple of 5000 bytes).

Because malloc must return an address that is good for any alignment, it
can only ever return the address zero. So that's what malloc does - it
either returns address zero or a NUL pointer for all calls.

That's theoretically possible, but also very bad QoI, and not necessary.

For each program, you know the types that are used in it. Therefore, for
each program, you know the LCM of the alignment requirements of the
types used. Therefore, for each program, you can set a hidden parameter
in the *alloc() package to that combined alignment.
This has to work, even on your theoretical machine, because although in
principle you have an infinite supply of alignment requirements, in
practice each program only uses a limited number of these. malloc() does
not have to work correctly with all programs at the same time - only
with the one it's currently being called by.

Richard