Alignment (K&R question)

Discussion in 'C Programming' started by sandeep, Apr 23, 2010.

  1. sandeep

    sandeep Guest

    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 ~
     
    sandeep, Apr 23, 2010
    #1
    1. Advertising

  2. sandeep

    Seebs Guest

    On 2010-04-23, sandeep <> wrote:
    >< 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
    --
    Copyright 2010, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, Apr 23, 2010
    #2
    1. Advertising

  3. sandeep

    sandeep Guest

    Seebs writes:
    > On 2010-04-23, sandeep <> wrote:
    >>< 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


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

    Regards ~
     
    sandeep, Apr 23, 2010
    #3
  4. sandeep <> writes:
    > 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.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Apr 23, 2010
    #4
  5. sandeep

    sandeep Guest

    Keith Thompson writes:
    > sandeep <> writes:
    >> 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.


    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 ~
     
    sandeep, Apr 23, 2010
    #5
  6. sandeep

    Eric Sosman Guest

    On 4/23/2010 4:31 PM, sandeep wrote:
    > [...]
    > 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.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Apr 23, 2010
    #6
  7. sandeep

    Seebs Guest

    On 2010-04-23, sandeep <> wrote:
    > 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
    --
    Copyright 2010, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, Apr 23, 2010
    #7
  8. sandeep <> writes:
    > Keith Thompson writes:
    >> sandeep <> writes:
    >>> 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.

    >
    > 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?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Apr 23, 2010
    #8
  9. sandeep

    bartc Guest

    "sandeep" <> wrote in message
    news:hqt032$jod$...

    > 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.

    --
    Bartc
     
    bartc, Apr 23, 2010
    #9
  10. sandeep

    Eric Sosman Guest

    On 4/23/2010 5:58 PM, Seebs wrote:
    > On 2010-04-23, sandeep<> wrote:
    >> 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.


    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.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Apr 23, 2010
    #10
  11. Seebs <> writes:
    > On 2010-04-23, sandeep <> wrote:
    >> 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.


    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]

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Apr 23, 2010
    #11
  12. Seebs <> writes:

    > On 2010-04-23, sandeep <> wrote:
    >> 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.


    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>
    --
    Ben.
     
    Ben Bacarisse, Apr 24, 2010
    #12
  13. sandeep

    Seebs Guest

    On 2010-04-23, Ben Bacarisse <> wrote:
    > 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
    --
    Copyright 2010, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, Apr 24, 2010
    #13
  14. sandeep

    Richard Bos Guest

    sandeep <> wrote:

    > 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
     
    Richard Bos, Apr 27, 2010
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wayne Wengert

    Alignment Question

    Wayne Wengert, Nov 28, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    605
    Wayne Wengert
    Nov 28, 2005
  2. John Curley

    [Newbie to Swing]: Alignment question

    John Curley, Aug 8, 2004, in forum: Java
    Replies:
    10
    Views:
    779
    Larry Barowski
    Aug 21, 2004
  3. Jeremy Williams

    Alignment question

    Jeremy Williams, Jul 18, 2003, in forum: HTML
    Replies:
    5
    Views:
    409
    Jeremy Williams
    Jul 20, 2003
  4. Pete
    Replies:
    6
    Views:
    1,107
    Inger Helene Falch-Jacobsen
    Mar 5, 2004
  5. Becky Lash
    Replies:
    8
    Views:
    416
    Lauri Raittila
    Nov 23, 2004
Loading...

Share This Page