Data Structure Alignment-Packing of Structures

From Embedded Systems Learning Academy
Revision as of 00:01, 19 December 2016 by Proj user12 (talk | contribs)

Jump to: navigation, search

This is a technique to manually reduce the amount of memory that a C program occupies. This method is useful for applications of C programs in low memory embedded systems. This also helps in the efficient utilization of the cache.

The term packing and unpacking seems a bit misleading. As the first instinct says the packing of a structure reduces the effective memory size of it. It may not always be right. The explanation of why it may not always be right is given below.

For example: Assuming the following struct is declared.

struct structure-name
{
  char member1;
  int member2;
  float member3;

};

The total size occupied by a single variable of the above struct datatype struct structure-name effectively is 9-bytes. Now when this data structure is "Packed", the effective memory now occupied by the same structure variable after packing is 12-bytes. There is a 3-byte increase in the amount of memory the structure. This contradicts the term of packing. Ironically, this increases the memory utilization capacity of the system employing this technique.

Let us now see why and how a 9-byte structure is not efficient but a 12-byte structure efficient. The only data type that doesn't need memory alignment is char type as it is a single byte. This is essential because the processors access the variables memory locations based on their memory address and for both int and float types, the address locations starting number has to be divisible by 4. For an 8-byte long and double types, the starting address location has to be divisible by 8.

As one can imagine that in a system which could have more than one type of structs, and more than 1 variable initialized by these structs can cause a lot of fragmentation in the memory. The processor also needs to make more than one bus transaction to fetch the data from the structure.

This is where the concept of packing comes handy as all the structures are self-aligned helping the processor to fetch the values quicker. Packing adds more number of bits to the existing structure to make the divisibility of the starting address by 4 or by 8. This process is called padding. The bits are padded in such a way that the total number of bytes that the struct uses after padding is even.

The way that the operations of accessing becomes faster is related to the bank accessing time. That is if an int type member is taken into consideration since the memory addressing is sequential, the member occupies 4 bytes of sequential addresses. If this member is preceded with a char type member, then the int type member which still follows the sequential addressing occupies some memory locations in the bank after the initial allocation too. This causes the processor to make 2 bus transactions to get the data of a single member.

Packing is effective when the members of the structure are defined such that the datatypes with higher memory occupancy come first. That is char type shouldn't come first as it defeats the purpose of packing. Since all other datatypes need an even number of bytes which is usually 4 bytes, the addressing sequence of the structure thus begins with a number that is divisible by 4. Now if the struct is packed, each member of the struct occupies one bank of the memory (which is achieved by padding), thus improving the bus transaction rate for the processor.

One such example of packing in embedded systems is shown below:

typedef struct {
     union {
         uint32_t frame; 
         struct {
             uint32_t          : 16; 
             uint32_t data_len : 4;  
             uint32_t          : 10; 
             uint32_t is_rtr   : 1;  
             uint32_t is_29bit : 1;  
         } frame_fields;
     };
 
     uint32_t msg_id; 
     can_data_t data; 
 } __attribute__((__packed__)) can_msg_t;