Data Structure Alignment and Padding

You must have heard that the fundamental data types must be aligned to a specific byte boundary. Most of you must have seen your programs being killed due to alignment exception generated by the processor. For any C programmer it is very important to understand the reasons behind the alignment restrictions.
In this article we will see why the compiler align certain data types to a certain boundary.

Why alignment restrictions ?
Typically a 32 bit processor reads or writes from the memory in chunks of 4 bytes (32 bits). The reads and writes can be performed at addresses that are divisible by 4.
Even if you want to read a single byte, 4 bytes are read from the memory and then the processor hardware circuitry will copy the requested byte to the specific position in the register.
For example, on m68K processor, a multiplexer sits in between an internal register and the external bus. The multiplexer selects the specified byte and routes it to the appropriate byte position in the register.

Lets try to see why processor restricts the data to be aligned to a specific byte boundary. Suppose the processor needs to read an integer (4 bytes in size).

Case 1: Integer is stored at address that is 4 byte aligned (say 0x100)

As the processor can read/write only at addresses that are divisible by 4, all four bytes can be read in a single bus cycle. Note that the address 0x100 is divisible by 4.

Address	Byte 0	Byte 1	Byte 2	Byte 3
0x100	X0	X1	X2	X3

Case 2: Integer is stored at an unaligned address (say 0x101)

This read cannot be performed in a single 32 bit bus cycle. The processor will have to issue two different reads at addresses 0x100 and 0x104.

Thus, it takes twice the time to read a misaligned data.

Address	Byte 0	Byte 1	Byte 2	Byte 3
0x100		X0	X1	X2
0x104	X3

It is important to note that

·    Some processors allow unaligned access but at a performance penalty as we saw above. Total time to read a misaligned data is more/double as compared to the aligned data Intel processor allow reading/writing data which is unaligned but at the cost of reduced performance.

·    Some processors generate an alignment exception on accessing a misaligned data. Then it is up to the exception handler either to report an error (kill the user process) or perform two read cycles to read the misaligned data (user process will run normally in this case but at reduced performance).

C compiler allocates addresses such that the data types are properly aligned. This helps in speeding up the read/write operation without causing any exception.
Typically on a 32 bit processor (like 32 bit x86, m68k, PowerPC, ARM etc)

·         A char (one byte) will be 1-byte aligned.

·         A short (two bytes) will be 2-byte aligned.

·         An int (four bytes) will be 4-byte aligned.

·         Any pointer (four bytes) will be 4-byte aligned  (e.g.: char *, int *)

Structure alignment and padding

Compiler add pad bytes in the user defined structures so that the various fields of a structure are properly aligned.

There are certain rules that can be kept in mind to understand padding in a structure.

1) No padding before the first element

The first element of a struct must come first, and must be preceded by no padding. This allows a struct pointer to be converted to a pointer to the struct's first element and vice versa, which is a useful property.

2) Pad bytes at the end of structure

It is obvious to add bytes in between the elements of a structure to keep the elements aligned. But why the compiler will put pad bytes at the end of a structure ?

This is because if an array of structure is declared, start of each structure should be properly aligned.

For an array of structure,  struct A array[10],

ð  array[1] should be equivalent to *(array + 1).

ð  difference between array + 1 and array + 0, should exactly equal to the size of struct A

To satisfy above constraints, compiler may have to put padding bytes at the end of structure. The rule is that the last member inside a structure should be padded with the number of bytes to make the structure aligned to the size of largest member of structure.

Lets see few examples for structure alignment and padding

struct exampleStruct {

   char data1;

   short data2;

   int data 3;

   char data 4;

};

On a typical 32 bit processor (say m68k or PowerPC), the compiler will insert padding in between various members so that they are properly aligned.

struct exampleStruct {

   char data1;

   char padding[1];    // pad of 1 byte to keep short to be 2

                       // byte aligned

   short data2;

   int data3;          // already aligned to 4 byte boundary,

                       // so no padding before this

   char data4;

   char padding[3];    // padding at the end of structure so

                       // that if an array of such structures is

                       // declared, the start of each structure

                       // in the array is properly aligned.

                       // Padding should be done such that

                       // start of structure address is aligned

                       // to the size of largest data member of

                       // structure. In this case, the size of

                       // largest data type (int data3) is 4.

                       // So, 3 pad bytes are added to the end.

};

How to arrange members so as to minimize padding?

By changing the ordering of members in a structure, it is possible to minimize the amount of padding. If members are sorted by ascending or descending aligment requirements, minimal amount of padding is required.

So, if you have a structure with multiple integer, short and char members, then keep all integer members at the beginning, keep all short members after interger members and all chars at the end.

How to prevent compiler from putting pad bytes in between or at the end of structure?

Compiler provides #pragma directives to specify the alignment of members inside a structure.

#pragma pack(push)          // save original alignment on stack

#pragma pack(1)             // set alignment to 1 byte boundary

struct packedStruct {

   char data1;

   int data2;               // no padding is inserted,

                            // as alignment specified is 1 byte.

   char data3;

};

#pragma pack(pop)           // restore original alignment

Here, we tell the compiler that each element should be aligned to 1 byte boundary. So, no padding is inserted in between elements. The size of this structure aftre compilation will be 6 bytes.

Thats all for today.
Have Fun !!!