Algorithm for determining Alignment of elements in C/C++ structs

Question

Okay, Allow me to re-ask the question, as none of the answers got at what I was really interested in (apologies if whole-scale editing of the question like this is a faux-paus).

A few points:

• This is offline analysis with a different compiler than the one I'm testing, so SIZEOF() or similar won't work for what I'm doing.
• I know it's implementation-defined, but I happen to know the implementation that is of interest to me, which is below.

Let's make a function called pack, which takes as input an integer, called alignment, and a tuple of integers, called elements. It outputs another integer, called size.

The function works as follows:

int pack (int alignment, int[] elements)
{
  total_size = 0;

  foreach( element in elements )
  {
    while( total_size % min(alignment, element) != 0 ) { ++total_size; }
    total_size += element;
  }

  while( total_size % packing != 0 ) { ++total_size; }

  return total_size;
}

I think what I want to ask is "what is the inverse of this function?", but I'm not sure whether inversion is the correct term--I don't remember ever dealing with inversions of functions with multiple inputs, so I could just be using a term that doesn't apply.

Something like what I want (sort of) exists; here I provide pseudo code for a function we'll call determine_align. The function is a little naive, though, as it just calls pack over and over again with different inputs until it gets an answer it expects (or fails).

int determine_align(int total_size, int[] elements)
{
  for(packing = 1,2,4,...,64) // expected answers.
  {
    size_at_cur_packing = pack(packing, elements);

    if(actual_size == size_at_cur_packing)
    {
      return packing;
    }
  }

  return unknown;
}

So the question is, is there a better implementation of determine_align?

Thanks,

Answer 1

I let the compiler do the alignment for me.

In gcc,

typedef struct _foo
{
    u8 v1  __attribute__((aligned(4)));
    u16 v2 __attribute__((aligned(4)));
    u32 v3 __attribute__((aligned(8)));
    u8 v1  __attribute__((aligned(4)));
} foo;

Edit: Note that sizeof(foo) will return the correct value including any padding.

Edit2: And offsetof(foo, v2) also works. Given these two functions/macros, you can figure out everything you need to know about the layout of the struct in memory.

Answer 2

You need to pad based on the alignment of the next field and then pad the last element based on the maximum alignment you've seen in the struct. Note that the actual alignment of a field is the minimum of its natural alignment and the packing for that struct. I.e., if you have a struct packed at 4 bytes, a double will be aligned to 4 bytes, even though its natural alignment is 8.

You can make your inner loop faster with total_size+= total_size % min(packing, element.size); You can optimize it further if packing and element.size is a power of two.

Answer 3

Alignment of struct members in C/C++ is entirely implementation-defined. There are a few guarantees there, but I don't see how they would help you.

Thus, there's no generic way to do what you want. In the context of a particular implementation, you should refer to the documentation of that implementation that covers this (if it is covered).

Answer 4

When choosing how to pack members into a struct an implementation doesn't have to follow the sort of scheme that you describe in your algorithm although it is a common one. (i.e. minimum of sizeof type being aligned and preferred machine alignment size.)

You don't have to compare overall size of a struct to determine the padding that has been applied to individual struct members, though. The standard macro offsetof will give the byte offset from the start of the struct of any individual struct member.

Answer 5

If the problem is just that you want to guarantee a particular alignment, that is easy. For a particular alignment=2^n:

void* p = malloc( sizeof( _foo ) + alignment -1 );
p = (void*) ( ( (char*)(p) + alignment - 1 ) & ~alignment );

I've neglected to save to original p returned from malloc. If you intend to free this memory, you need to save that pointer somewhere.

Answer 6

I'm honestly not sure what you're trying to do, and I'm probably completely misunderstanding what you're looking for, but if you want to simply determine what the alignment requirement of a struct is, the following macro might be helpful:

#define ALIGNMENT_OF( t ) offsetof( struct { char x; t test; }, test )

To determine the alignment of your foo structure, you can do:

ALIGNMENT_OF( foo);

If this isn't what you're ultimately tring to do, it might be possible that the macro might help in whatever algorithm you do come up with.