Alignment problems

Discussion in 'C Programming' started by jacob navia, Jul 8, 2010.

  1. jacob navia

    jacob navia Guest

    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
     
    jacob navia, Jul 8, 2010
    #1
    1. Advertising

  2. jacob navia

    Ian Collins Guest

    On 07/ 8/10 08:59 PM, jacob navia wrote:
    > 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 );
    }

    --
    Ian Collins
     
    Ian Collins, Jul 8, 2010
    #2
    1. Advertising

  3. jacob navia

    jacob navia Guest

    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.
     
    jacob navia, Jul 8, 2010
    #3
  4. jacob navia

    Ian Collins Guest

    On 07/ 8/10 09:52 PM, jacob navia wrote:
    > 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.


    Blimey.

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


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

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


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

    --
    Ian Collins
     
    Ian Collins, Jul 8, 2010
    #4
  5. jacob navia <> writes:
    [...]
    > 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.)

    --
    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, Jul 8, 2010
    #5
  6. jacob navia

    Seebs Guest

    On 2010-07-08, jacob navia <> wrote:
    > 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
    --
    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, Jul 9, 2010
    #6
  7. jacob navia

    Ian Collins Guest

    On 07/ 9/10 01:36 PM, Seebs wrote:
    > On 2010-07-08, jacob navia<> wrote:
    >> 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 *.


    Double the size...

    --
    Ian Collins
     
    Ian Collins, Jul 9, 2010
    #7
  8. jacob navia

    jacob navia Guest

    Ian Collins a écrit :
    > On 07/ 9/10 01:36 PM, Seebs wrote:
    >> On 2010-07-08, jacob navia<> wrote:
    >>> 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 *.

    >
    > 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, Jul 9, 2010
    #8
  9. jacob navia

    jacob navia Guest

    Seebs a écrit :
    > On 2010-07-08, jacob navia <> wrote:
    >> 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


    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.
     
    jacob navia, Jul 9, 2010
    #9
  10. jacob navia

    Ian Collins Guest

    On 07/ 9/10 05:03 PM, jacob navia wrote:
    > Ian Collins a écrit :
    >> On 07/ 9/10 01:36 PM, Seebs wrote:
    >>> On 2010-07-08, jacob navia<> wrote:
    >>>> 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 *.

    >>
    >> Double the size...

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


    It was intended as a pun...

    --
    Ian Collins
     
    Ian Collins, Jul 9, 2010
    #10
  11. jacob navia

    Ian Collins Guest

    On 07/ 9/10 05:24 PM, Ian Collins wrote:
    > On 07/ 9/10 05:03 PM, jacob navia wrote:
    >> Ian Collins a écrit :
    >>> On 07/ 9/10 01:36 PM, Seebs wrote:
    >>>> On 2010-07-08, jacob navia<> wrote:
    >>>>> 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 *.
    >>>
    >>> Double the size...

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

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

    --
    Ian Collins
     
    Ian Collins, Jul 9, 2010
    #11
  12. On 08 Jul 2010 03:59, jacob navia wrote:
    > 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).)

    --
    Stephen Sprunk "God does not play dice." --Albert Einstein
    CCIE #3723 "God is an inveterate gambler, and He throws the
    K5SSS dice at every possible opportunity." --Stephen Hawking
     
    Stephen Sprunk, Jul 9, 2010
    #12
  13. jacob navia

    Seebs Guest

    On 2010-07-09, jacob navia <> wrote:
    > (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
    --
    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, Jul 9, 2010
    #13
  14. Richard Heathfield wrote:
    > Stephen Sprunk wrote:
    >> #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.

    >
    > 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.
     
    Alexander Klauer, Jul 9, 2010
    #14
  15. Alexander Klauer <-mannheim.de> writes:

    > Richard Heathfield wrote:
    >> Stephen Sprunk wrote:
    >>> #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.

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


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

    --
    Ben.
     
    Ben Bacarisse, Jul 9, 2010
    #15
  16. Ben Bacarisse wrote:
    > Alexander Klauer <-mannheim.de> writes:
    >> Richard Heathfield wrote:
    >>> Stephen Sprunk wrote:
    >>>> #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.
    >>>
    >>> 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,

    >
    > 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.
     
    Alexander Klauer, Jul 9, 2010
    #16
  17. Alexander Klauer <-mannheim.de> writes:
    [...]
    > 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 (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, Jul 9, 2010
    #17
  18. Alexander Klauer <-mannheim.de> writes:
    > Richard Heathfield wrote:
    >> Stephen Sprunk wrote:
    >>> #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.

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


    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);

    --
    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, Jul 9, 2010
    #18
  19. jacob navia

    ImpalerCore Guest

    On Jul 8, 4:59 am, jacob navia <> wrote:
    > 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.
     
    ImpalerCore, Jul 10, 2010
    #19
  20. jacob navia

    Lauri Alanko Guest

    In article <>,
    Ben Bacarisse <> wrote:
    > #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
     
    Lauri Alanko, Jul 12, 2010
    #20
    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. =?Utf-8?B?bWFudQ==?=

    Regd---Justify option in Alignment.

    =?Utf-8?B?bWFudQ==?=, Sep 23, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    456
    =?Utf-8?B?bWFudQ==?=
    Sep 23, 2005
  2. ALuPin

    Phase alignment

    ALuPin, May 17, 2004, in forum: VHDL
    Replies:
    0
    Views:
    593
    ALuPin
    May 17, 2004
  3. Sunil Menon

    Re: Help required for alignment problem

    Sunil Menon, Jun 26, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    822
    Sunil Menon
    Jun 26, 2003
  4. Kevin G.

    ASP to Excel Image Alignment Problems

    Kevin G., Oct 1, 2008, in forum: ASP General
    Replies:
    2
    Views:
    187
    Daniel Crichton
    Oct 2, 2008
  5. jacob navia

    Alignment problems

    jacob navia, Dec 1, 2011, in forum: C Programming
    Replies:
    20
    Views:
    797
    David Thompson
    Jan 19, 2012
Loading...

Share This Page