Memory alignment

Introduction

The Secure Elements on top of which the Ledger Operating System and the associated applications run imply a 32-bit alignment. This article aims at explaining the C associated development constraints.

Alignment concept

The memory alignment is a concept which applies to memory and pointers:

A memory address is ‘b-bits aligned’ when it is a multiple of b/8, b/8 being a power of 2
A memory address is said to be aligned when the data referenced by said address is b bits long, and said address is b-bits aligned
A pointer is ‘aligned’ when it points on aligned memory
A pointer is ‘unaligned’ when it points on unaligned memory

Alignment constraints for basic types and structures

Implementing C source code with types and structures is not functionally impacted by the 32-bit alignment, except for potentially wasting a few bytes without even noticing.

This paragraph is important for writing memory-efficient structures, once the application is compiled and loaded onto a device.

Within any application source code, the alignment of basic types will be considered as follows, at compilation time:

char / unsigned char / int8_t / uint8_t : 8-bit aligned
short / unsigned short / int16_t / uint16_t: 16-bit aligned
int / unsigned int / int32_t / uint32_t: 32-bit aligned
any pointer: 32-bit aligned

Please note that 8-bit aligned means that there is actually no alignment constraint.

The compiler will add padding in any structure which is not aligned by design, in order to respect:

The alignment of each field associated to their respective length
The alignment of the whole structure, which must have a total length, padding included, multiple of the largest field’s length

For instance the following structure is 8 bytes long before compilation:

// Before compilation
struct Example1
{
    char    field_1;
    short   field_2;
    int     field_3;
    char    field_4;
};

However during compilation, the structure is modified to ensure the alignment, and will thus be 12 bytes long:

// After compilation
struct Example1
{
    char    field_1;
    // Padding added for field_2 to start on a 16-bit aligned address
    char    padding_1;
    short   field_2;
    // With padding_1 being added, field_3 will start on a 32-bit aligned
    // address and no padding is required here.
    int     field_3;
    char    field_4;
    // The structure is aligned to the number of bits corresponding to the
    // largest field's alignment, in this case, due to field_3, 32-bits.
    // For the structure to be 32-bit aligned, it needs 3 more bytes of padding.
    char    padding_2[3];
};

 [xxxxxxxx] -------- [xxxxxxxx   xxxxxxxx]
 [xxxxxxxx   xxxxxxxx   xxxxxxxx   xxxxxxxx]
 [xxxxxxxx] --------   --------   --------

In this example, it is possible to reorganize the structure’s fields to avoid alignment-induced padding, but sometimes padding will not be avoidable.

You can order the structure fields according to their length in decreasing order:

// Before compilation
struct Example1_reordered
{
    int     field_3;
    short   field_2;
    char    field_1;
    char    field_4;
};

// After compilation
struct Example1_reordered
{
    int     field_3;
    // No need for padding since field_2 is already on a 16-bit aligned address.
    short   field_2;
    // No need for padding for char types.
    char    field_1;
    char    field_4;
    // No need for padding since the structure is 8 bytes long and thus, its length
    // is already a multiple of its largest field's length.
};

You can also order the structure fields to make sure the minimum amount of padding bytes will be added by the compilation phase:

// Before compilation
struct Example1_reordered_other_way
{
    int     field_3;
    char    field_1;
    char    field_4;
    short   field_2;
};

// After compilation
struct Example1_reordered_other_way
{
    int     field_3;
    // No need for padding for char types.
    char    field_1;
    char    field_4;
    // No need for padding since field_2 is already on a 16-bit aligned address.
    short   field_2;
    // No need for padding since the structure is 8 bytes long and thus, its length
    // is already a multiple of its largest field's length.
};

Alignment constraints for pointers

Using pointers within C source code might be functionally impacted by the 32-bit alignment in a specific case: when the pointer points on a memory area which type differs from the pointer, and is dereferenced.

Dereferencing unaligned pointers within an application makes the application crash.

Usually, pointers are used to store the address of an element which type corresponds to the pointer one, and for simple example:

uint16_t *pointer;
uint16_t array[10];
 
// Pointer positioning is perfectly fine.
pointer = &array[3];
 
// Dereferencing this pointer is also perfectly fine, since the
// pointed memory is aligned in accordance with the pointer type.
*pointer = 0x0001;

However, if we use a pointer with a specific type to store the address of a memory area declared with another type (usually with an alignment-related size less than the pointer one), it can lead to hardware faults and the application crashing:

uint16_t *pointer;
uint8_t array[10];
 
// Case where it will work even if not advised.
 
// Pointer positioning is fine.
pointer = (uint16_t*)&array[2];
 
// Dereferencing this pointer is also fine: the pointed memory is aligned
// in accordance with the pointer type (because the offset 2 in the array variable
// is a multiple of 16 bits).
if (*pointer == 0x0001) {
    do_something();
}
 
// Case where it will make the application crash.
 
// Pointer positioning is fine, but it is unaligned.
pointer = (uint16_t*)&array[3];
 
// Dereferencing this pointer will make the application crash: the pointed memory is not aligned
// in accordance with the pointer type (because the offset 3 in the array variable
// is not a multiple of 16 bits).
if (*pointer == 0x0001) { /* This dereferencing makes the application crash. */
    do_something();
}

The same reasoning applies when pointing on structures:

// Same example as within the previous paragraph, being ordered
// makes it 8 bytes long.
struct Example1_reordered
{
    int     field_3;
    short   field_2;
    char    field_1;
    char    field_4;
};
 
Example1_reordered *pointer;
uint8_t array[32];
 
// Case where it will work even if not advised.
 
// Pointer positioning is fine.
pointer = (Example1_reordered*)&array[8];
 
// Dereferencing this pointer is also fine: the pointed memory is aligned
// in accordance with the pointer type (because the offset 8 in the array variable
// is a multiple of the structure's size after compilation).
if (pointer->field_2 == 0x0001) {
    do_something();
}
 
// Case where it will make the application crash.
 
// Pointer positioning is fine, but it is unaligned.
pointer = (Example1_reordered*)&array[3];
 
// Dereferencing this pointer will make the application crash: the pointed memory is not aligned
// in accordance with the pointer type (because the offset 3 in the array variable
// is not a multiple of the structure's size after compilation).
if (pointer->field_2 == 0x0001) { /* This dereferencing makes the application crash. */
    do_something();
}

Unaligned pointers can thus occur in cases where a pointer:

is declared as positioning on some data type (or structure),
is used to point on a memory area actually containing another type of data,
is dereferenced.

In order to produce robust to alignment constraints C source code, avoid using pointers in this way.

External links

Position-independant code Security specificities