Thread: alignment and structures

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    330

    alignment and structures

    I'm creating a general linked list and I want it to be as portable as I can. The idea is to have a struct BUCKET with the next and previous pointers in it and allocate the members contained in the list just "above" the BUCKET structs.

    So I have:

    Code:
    typedef struct BUCKET
    {
    	struct BUCKET *Next;
    	struct BUCKET **Prev;
    } BUCKET;
    and a list struct

    Code:
    typedef struct DATA_LIST
    {
       BUCKET *First;
    } DATA_LIST;
    and when you want to add an item to the list you have to use a function newnode.

    Code:
    void *newnode(size_t Size)
    {
    	BUCKET *node = calloc(Size + sizeof *node, 1);
    
    	return node ? node + 1 : NULL;
    }
    So when you want a linked list of X structures you do:

    Code:
    struct X { int X; long double Y; };
    
    struct X *newnode = newnode(sizeof *newnode);
    
    addtolist(list, newnode);
    where addtolist only knows about the BUCKET members.

    But the problem I have is with alignment. newnode returns a pointer just above the alignment of the BUCKET struct (BUCKET *+ 1) but what if the first member of X lands on a non aligned address?
    How to solve this with standard C?

    I hope I'm clear

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > How to solve this with standard C?
    You could use a union inside the bucket to force it to be aligned to the worst case data type, by including a member with the strictest alignment requirement within the union.
    Eg.
    Code:
    typedef struct BUCKET
    {
        union {
            struct {
                struct BUCKET *Next;
                struct BUCKET **Prev;
            } node;
            long double aligner;
        } v;
    } BUCKET;
    > return node ? node + 1 : NULL;
    I trust you're going to be similarly careful when it comes to freeing the memory as well
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Why not just have the next pointer pointing to the first address of the next node, instead of just before it?

    It might very well be standard and portable, but it "smells" very non-standard,

    Big Nose

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    Quote Originally Posted by Salem View Post
    > How to solve this with standard C?
    You could use a union inside the bucket to force it to be aligned to the worst case data type, by including a member with the strictest alignment requirement within the union.
    Eg.
    Code:
    typedef struct BUCKET
    {
        union {
            struct {
                struct BUCKET *Next;
                struct BUCKET **Prev;
            } node;
            long double aligner;
        } v;
    } BUCKET;
    Does the long double always have the most strict alignment requirements?

    And does this guarantee that when I have a struct like

    Code:
    struct X
    {
      int type;
      short x;
      short y;
    };
    and I allocate this struct + a BUCKET through the newnode function that
    &x->type, &x->x and &x->y are all aligned on the right addresses?


    Quote Originally Posted by Salem
    > return node ? node + 1 : NULL;
    I trust you're going to be similarly careful when it comes to freeing the memory as well
    yes

    Code:
    void freenode(void *sym)
    {
        if (sym != NULL)
        {
          free((BUCKET *)sym - 1);
        }
    }
    The code (without the union) works on the processor I created it for, the addresses all happen to be aligned correctly (and even if they werent it would just run slower) but I just want to make sure it will keep working on other processors because this code is going to be ported in the future and we dont know to what yet.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Does the long double always have the most strict alignment requirements?
    Probably, though I don't think it's a guarantee.
    IIRC, the standard only mentions that different data types can have different alignments, and the need to make sure the alignments are preserved, but doesn't go on to specify what they should be (if anything).

    > And does this guarantee that when I have a struct like
    It's only going to work with a BUCKET at the start, unless you also go round adding the aligning data member in all the things which have a bucket following them.

    For any given struct, the compiler only has to align it in such a way to ensure that 'array of X' is also correctly aligned.

    > but it "smells" very non-standard
    Oh that's for sure. These are all mitigating steps, not actual solutions.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The other solution is to separate the linked list and the content itself - having some sort of "data" pointer.

    I would probably add "double" as one of the components of the union, because in at least x86 [as a processor architecture], "long double" is not as strictly aligned as "double" [although neither HAS to be aligned at all for x86 to work].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    I changed it to this (snipped code guideline crap):

    Code:
    typedef struct BUCKET
    {
      union  {
        struct  {
          struct BUCKET *Next;
          struct BUCKET **Prev;
        } node;
    
        long double align;
      } u;
    } BUCKET;
    
    typedef struct DATA_LIST {
      size_t Size;
      BUCKET *First;
      DATA_COMPAREFUNC *Cmp;
    } DATA_LIST;
    
    void *newnode(size_t Size)
    {
      BUCKET *node = calloc(Size + sizeof *node, 1);
    
      return node ? node + 1 : NULL;
    }
    
    void *list_addnode(DATA_LIST *List, void *iSym) {
      BUCKET *Sym = NULL;
    
      if (iSym != NULL) {
        BUCKET **p, *tmp;
    
        Sym = (BUCKET *)iSym - 1;
    
        p = &List->First;
    
        tmp = *p;
        *p = Sym;
        Sym->u.node.Prev = p;
        Sym->u.node.Next = tmp;
    
        if (tmp != NULL) {
            tmp->u.node.Prev = &Sym->u.node.Next;
        }
    
        List->Size++;
      }
      return Sym ? Sym + 1 : NULL;
    }
    Same for deletion etc and it seems to work nicely with different kinds of structure put into the lists. This is like what you intended salem?

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > This is like what you intended salem?
    Yep, that's about the size and shape of it.

    All you need to add is
    #include <std_disclaimer.h>
    and you're good

    I might include a diagnostic function you can call right at the start of the program which specifically tests whether the approach actually works on a given architecture, rather than waiting for it to fail obscurely later on.
    Remember, some architectures support unaligned accesses with a loss of performance, so even it it appears to work, you may be losing out performance-wise.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    Quote Originally Posted by matsp View Post
    I would probably add "double" as one of the components of the union, because in at least x86 [as a processor architecture], "long double" is not as strictly aligned as "double" [although neither HAS to be aligned at all for x86 to work].
    Ok, I'll add that

    Just out of interest, what are the optimal alignment requirements for double and long double on x86?

    I work on a motorola coldfire, the manual says:

    All MCF5206e data formats can be located in memory on any byte boundary. A byte
    operand is properly aligned at any address; a word operand is misaligned at an odd
    address; and a longword is misaligned at an address that is not evenly divisible by four.
    However, because operands can reside at any byte boundary, they can be misaligned.
    Although the MCF5206e does not enforce any alignment restrictions for data operands
    (including program counter (PC) relative data addressing), some performance
    degradation occurs when additional bus cycles are required for longword or word
    operands that are misaligned.


    Then they go on about what instructions are extra performed when misaligned data moves happen.

  10. #10
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    How about function [pointers btw? shouldn't I add that too?
    rofl, where does it stop

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by KIBO View Post
    Ok, I'll add that

    Just out of interest, what are the optimal alignment requirements for double and long double on x86?

    I work on a motorola coldfire, the manual says:

    All MCF5206e data formats can be located in memory on any byte boundary. A byte
    operand is properly aligned at any address; a word operand is misaligned at an odd
    address; and a longword is misaligned at an address that is not evenly divisible by four.
    However, because operands can reside at any byte boundary, they can be misaligned.
    Although the MCF5206e does not enforce any alignment restrictions for data operands
    (including program counter (PC) relative data addressing), some performance
    degradation occurs when additional bus cycles are required for longword or word
    operands that are misaligned.


    Then they go on about what instructions are extra performed when misaligned data moves happen.
    I think the "ideal" alignment is 16 byte, but you are loosing quite a bit of "extra space" that way (48 bytes).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    As a rough rule of thumb, the worst-case alignment of a type is roughly equivalent to it's size. So a 4-byte type like int or float would be on a 4-byte boundary. Sometimes it's better, but I don't recall off hand any system where it was worse than that.
    /me waits for the exceptions to flood in

    I see your coldfire manual refers to the performance issues I mentioned

    > How about function [pointers btw? shouldn't I add that too?
    You're not actually going to be containing code inside the allocated memory (or are you?). You might, if you've got some dynamic loader deal going on.

    > rofl, where does it stop
    I think if you include in your union all of int, long, float and double that should cover you. Adding short would be for completeness only.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    Quote Originally Posted by Salem View Post
    How about function [pointers btw? shouldn't I add that too?
    You're not actually going to be containing code inside the allocated memory (or are you?). You might, if you've got some dynamic loader deal going on.
    It could happen that I or somebody else wants to put a structure in there which contains function pointer. Knowing myself this will happen for sure

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    In all architectures I'm aware of, a function pointer is the same size as a regular pointer [although technically, a "far" pointer in x86 architecture could be longer - but it assumes the same alignment as a regular pointer].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alignment tutorial needed!!
    By mynickmynick in forum C++ Programming
    Replies: 11
    Last Post: 09-12-2008, 04:41 AM
  2. dynamic memory alignment (Win32)
    By ZeroMemory in forum C Programming
    Replies: 3
    Last Post: 05-25-2008, 08:15 AM
  3. memory boundry alignment with stuctures
    By ed bitwise in forum C Programming
    Replies: 3
    Last Post: 05-08-2006, 11:33 AM
  4. Replies: 1
    Last Post: 06-17-2005, 07:31 AM
  5. Ok, I'm dumb, byte alignment for the third time
    By Shadow12345 in forum C++ Programming
    Replies: 2
    Last Post: 12-30-2002, 06:19 PM