I'm a little confused and I'm trying to understand structure padding and how variables are actually laid out in memory on a 32-bit machine ARM. This is a generic question just to help me understand basic.

Suppose I have this program:

#include <stdio.h>

struct test {
    
    char x;
    int y;
    
};

int main()

{
    struct test s;
    char a = 'z';
    
    s.x = 'b';
    s.y = 10;
    
    return 0;
}

Let's assume RAM addresses look something like this:

0x00
0x01
0x02
0x03
0x04
0x05
0x06
0x07
0x08
...

variable a occupies 1 byte, while struct test s occupies 8 bytes in total: 1 byte for s.x, 3 bytes of padding, and 4 bytes for s.y. What I'm trying to understand is how the compiler places these variables in RAM. Where would a be located, and where would s.x and s.y typically be placed in memory?

I know the exact layout is implementation-defined. I'm just trying to understand the general idea of how compilers lay out local variables and structure variable in memory and how alignment affects that process.

 

How variables get placed in memory depends to a large extent on the range of load and store operations available on a particular platform and what costs are associated with accesses to units that are not on 32-bit word boundaries.

The most common strategy I have seen in practice is to align the current item on the appropriate boundary.

• 32bit words go on word boundaries which are at addresses with zeros in the least significant two bits.
• 16-bit halfwords go on halfword boundaries which are at addresses with a zero in the least significant bit.
• 8-bit bytes can go at any address.

When switching from bytes or halfwords back to words, the words must be word aligned and any bytes or halfwords leftover are skipped and ignored. I don't remember any systems that ever attempted to use the leftover bytes between allocation units of different sizes.

 

It depends on the memory architecture of the processor.
If it takes the same effort to access 8-bit data vs 32-bit data, then the compiler might choose to store 8-bit and 16-bit data as 32-bit data. Thus all data would be on 32-bit boundaries.

 

My first attempt was to understand this in a general sense. after reading both of your replies, I felt you were looking for more specific information before explaining it.

So I've updated my original post and assumed an ARM processor. If it helps to go even more specific, let's assume a Cortex-M0. You can also assume any compiler you're most comfortable with if that makes the explanation easier.

What I'm really trying to understand is the memory layout shown in my example. Given the memory table I drew, how would the compiler place these variables in RAM?

My current understanding is that memory itself is not divided into 4-byte address blocks. Each address still represents 1 byte, but the compiler aligns certain data types (like int) on 4-byte boundaries. I'm trying to understand how that affects the placement of a, s.x, the padding bytes, and s.y in memory.

 

@Embededd

Compilers do a huge amount of work and determining addresses of variables is not trivial. One of the things a compiler does is create a "symbol table" that's a data structure that is created as the compiler executes.

The symbol table contains metadata associated with each declared variable. The first step here is to insert entries for each symbol as its encountered during the processing of the code.

The symbol table contains entries that describe:

1. The name
2. The data type
3. The storage type (static, stack)
4. Struct members (if any)
5. Size, alignment, offset

The details in step 5. are often unknown and are determined some time after the symbol entry has been initially added to the symbol table.

The "offset" here is a value derived from the offset of the preceding symbol, so it increases and depends on the offset and size of that preceding symbol.

So we determine size, alignment and offset of the first symbol then we do the same for the next and so on, for every symbol.

The offset too is either an offset into the static section or an offset from the start of the stack frame if its a stack based declaration.

Now for structures of course, there is more work to do, the symbol itself becomes a tree and each node of the tree is a symbol, and the process of determining offset is just a more general form of what I described above.

The concept of padding does not always need to be made explicit in the symbol table either, it just needs to be known when we compute the offset, it doesn't necessarily need to be recorded in the symbol table but can be.

Having said all that, understand that the code that's generated often includes a dynamically generated expression, called and "offset expression" and that is executed in order to get the actual offset at runtime for whatever variables are being referenced.

So in your example you have s.y = 10 and so the generated code will calculate some expression (a mathematical function) that uses the symbol table metadata for s and y.

The offset expression often is a constant value though because the offset does not change at runtime, so in the generated code you see just that calculated offset but if we have structs or arrays and combinations of these, the offset expression is in the generated code because it must be executed at runtime based on array subscripts.

Basically we want to calculate the address to write to, for every assignment and so the offset calculation does that.

Finally the symbol table is used as the basis for supporting debuggers and it appears in the final generated output file.

If you really want more insight then you must dive into some books, there is just too much work being done to deeply explain it in a post here.

 

You can find the memory address assigned to a variable by looking at the .map file of the project.

 

Local variables that are not marked static are stored on the stack. The actual address is not determined until execution time and can vary from one invocation of the function to the next.

Variables that are marked static or declared outside of any function are assigned fixed memory locations by the linker, not the compiler in the typical implenentation.

Whether the variable is an atomic type, struct or array has no bearing in it. Padding is a completely separate question.

 

When I search about structure padding on Google, almost every explanation starts talking about memory alignment, 4-byte boundaries, addresses divisible by 4, and 32-bit processors. I can read the definitions of each of these terms individually, but I still can't connect them together into one complete picture.

That's why I'm asking this question. I want to understand how all of these concepts relate to each other, so I can connect every piece instead of just memorizing the individual definitions.

 

When I search about structure padding on Google, almost every explanation starts talking about memory alignment

If you want some variable or struct member to be aligned in some way then the compiler might need to use padding to accomplish that, so that's why these come up together in searches.

4-byte boundaries, addresses divisible by 4, and 32-bit processors. I can read the definitions of each of these terms individually, but I still can't connect them together into one complete picture.

That's why I'm asking this question. I want to understand how all of these concepts relate to each other, so I can connect every piece instead of just memorizing the individual definitions.

Every struct member (including members that are themselves structs) has an alignment, whether one cares about it or not, it is always present, every thing that has an address by definition has an alignment, alignment is 1, 2, 4, 8, 16, 32, 64, 128 etc and every address has one of these alignments - the number refers to bytes.

Alignments are inclusive, so every 8 byte aligned address is also 4 and 2 byte aligned but the opposite is not true, not every 4-byte aligned address is 8-byte aligned.

Every type has a default alignment, it's part of the type. So to make sure that each struct member has the right alignment the compiler might need to insert (unseen) pad bytes.

Is this the thing that's bothering you? alignment specifically?

 

When I search about structure padding on Google, almost every explanation starts talking about memory alignment, 4-byte boundaries, addresses divisible by 4, and 32-bit processors. I can read the definitions of each of these terms individually, but I still can't connect them together into one complete picture.

That's why I'm asking this question. I want to understand how all of these concepts relate to each other, so I can connect every piece instead of just memorizing the individual definitions.

Disclaimer up front: The compiler is generally free to do things however the compiler designer chooses to do it, provided they adhere to the constraints imposed by the programming language standard and the CPU. Most languages don't have much to say about how things are placed in memory, and most CPU architectures impose few, if any, constraints and the once they do are very low level. So the compiler designer has pretty free reign.

In many/most processors, the processor can only access memory at boundaries that match the register size of the processor. This could be a fundamental constraint because the necessary lower bits of the address may not be stored in the instruction, thus the code has to be written in such a way that those lower bits are intrinsically zero. Other processors can access unaligned data such that, say, a 32-bit processor loads four bytes of data into a register data starting at the specified address regardless of whether that address is aligned in any way. However, it is pretty common that processors that allow unaligned access require more time to do so than they do to access properly aligned data (my quick search indicates that this includes later ARM and Cortex processors), so the compiler will likely choose to use aligned data layouts even when it's not absolutely required by the processor.

So, what might that layout look like for a structure such as the one you offered:

struct test {
    
    char x;
    int y;
    
};

In general, structures will be padded to make the entire structure an integer multiple of the preferred alignment size for the processor. Doing so facilitates things like making arrays of structures. How this is done is completely up to the compiler. It is not allowed to place padding at the front, since the address of the struct is required to also be the address of the first element. It also can't re-arrange the order to structure members since they are required to remain in their declared order. It can add padding between members and/or add padding at the end, but how it does that is up to it.

Let's assume that your machine is a 32-bit machine that requires data to be 32-bit word-aligned. Let's further assume that int type data is 32-bit (that is NOT required by the language standard, only that it be at least 16-bit).

So let's look at your example code:

#include <stdio.h>

struct test {

char x;
int y;

};

int main()

{
struct test s;
char a = 'z';

s.x = 'b';
s.y = 10;

return 0;
}

The compiler maintains a symbol table during translation (i.e., while it's actually compiling the code) that maintains the information about each variable and type declaration and definition. This symbol table generally is not included in the final code, it's only there for the compiler to use while it is doing it's job. The details of what is in the symbol table and how it is organized is completely up to compiler designer, so what I'm about to describe is a conceptual description only.

The table will store the offsets of each member of a structure relative to the start of the structure, as well as the overall size of the structure:

struct test: 8, (char x 0, int y 4)

This is my way of saying that the overall structure is 8 bytes and that x is a char located 0 bytes after the start and y is an int located 4 bytes after the start.

Local variables (more properly known as automatic variables, since they are automatically allocated and deallocated at run time as functions are called and returned from) are generally stored on the stack (which is how the automatic allocation and deallocation comes about). When a function is executing, there is a special register that stores the address of its stack frame (the portion of memory that is for its use at this time). For local variables within a function, the addresses that the compiler associates with the variable is an offset that gets added (or subtracted, depending on what direction the stack grows) to the base pointer. For simplicity, let's assume that the stack grows upward (even though most go the other way).

The compiler knows (since it's the one that dictates it) how the stack frames are structured. There are likely some things that are contained at the beginning of the stack frame, such as the return address or some arguments that were passed to the function, and hence the local variables will likely not be stored right at the start of the frame. For our example, let's assume there are 16 bytes at the start of the frame used for these things While the compiler can't reorder the members within a struct, it is completely free to reorder local variables however it chooses, but let's assume that it assigns them in the order they are declared. So, in the instructions it produces, the address of struct 's' will be 16 (0x0010). Since the sizeof(s) is 8, the char 'a' will be at address 24 (0x0018). The address of 's.x' will be 16+0, (0x0010) since it is stored at the beginning of the struct, while the address of s.y will be 16+4 (0x0014).

Let's now assume that, at the time main() is invoked, the base pointer is set to 0x1308.

We know have all that we need to resolve the addresses of the variables:

&(s.x) = 0x1318
&(s.y) = 0x131C
&(a) = 0x1320

Assuming I didn't mess up the math in my head, which is often not a good assumption.

 

In many/most processors, the processor can only access memory at boundaries that match the register size of the processor.

Yes, this is exactly the part I'm struggling to understand. data register size is 4 bytes long

For example, suppose the memory looks like this:

0x00      a      z
0x01
0x02
0x03
0x04
0x05
0x06
0x07
0x08
...

Let's say my first variable, a, is stored at address 0x00.

Now I'm confused about where s.x would be placed. Could it be stored immediately at 0x01, or would the compiler place it at 0x04 because of alignment?

This is where I get confused about boundaries. What exactly does a 4-byte boundary mean? Where does a boundary start and where does it end?

Is it always based on addresses like 0x00, 0x04, 0x08, 0x0C, and so on? Or does it depend on where the previous variable was placed?

For example, if a is stored at address 0x00, can the next variable start at 0x01, 0x05, or 0x07, ?

 

Yes, this is exactly the part I'm struggling to understand. data register size is 4 bytes long

For example, suppose the memory looks like this:

0x00      a      z
0x01
0x02
0x03
0x04
0x05
0x06
0x07
0x08
...

Let's say my first variable, a, is stored at address 0x00.

Now I'm confused about where s.x would be placed. Could it be stored immediately at 0x01, or would the compiler place it at 0x04 because of alignment?

This is where I get confused about boundaries. What exactly does a 4-byte boundary mean? Where does a boundary start and where does it end?

Is it always based on addresses like 0x00, 0x04, 0x08, 0x0C, and so on? Or does it depend on where the previous variable was placed?

For example, if a is stored at address 0x00, can the next variable start at 0x01, 0x05, or 0x07, ?

If the system is byte-addressable, this really only means that each byte of memory has it's own address (as opposed to each 16-bit or each 32-bit block of memory). That's largely all it means.

This is separate from the data alignment requirements, which often require that N-byte variables must have a base address that is on an N-byte boundary and that N must be an integer power of two.

All "boundary" means is that the address is evenly divisible by N.

So variables that are 4 bytes in size have to start at addresses that are divisible by 4.

It really can't depend on what happens elsewhere, that would create all sorts of problems that would be virtually impossible to deal with.

So if 'a' is stored at 0x00 and is a 1-byte variable, another 1-byte variable could be placed at 0x01. But if a 2-byte variable has to be aligned on a 2-byte boundary, the next available location would be 0x02. However, the compiler might know, because it knows what processor (family, if nothing else) it is targeting, that memory access is the fastest for items on 4-byte boundaries, so it might choose to place that 2-byte variable on a 4-byte boundary and park it at 0x04. Keep in mind that this is a perfectly acceptable action because a 4-byte boundary IS also a 2-byte boundary.

Alignment requirements can arise from a few places. The first and most rigorous is the CPU architecture itself. There's not much anyone can do about that except choose a different CPU. Next is the the ABI (Application Binary Interface) in use, which is a specification on many things, including calling conventions, register usage, and data alignment, that is designed to let separately-compiled pieces of code interact successfully. A compiler implements the ABI. Then there might be requirements imposed by the language. The operating system doesn't play much of a role beyond insuring that things like requested virtual memory blocks are adequately aligned per the CPU and ABI specifications.

 

All "boundary" means is that the address is evenly divisible by N.

So variables that are 4 bytes in size have to start at addresses that are divisible by 4.

I think I'm starting to understand the idea, so let me know if my understanding is correct.

If I have:

char a;
char b;
char c;

then all of them only require 1-byte alignment, so they can simply be placed one after another:

0x00   a
0x01   b
0x02   c

Now consider:

struct test {

    char x;
    int y;

};

struct test s;
char a = 'z';

Since struct test contains an int, the structure itself requires 4-byte alignment. So if a is placed at 0x00, the compiler cannot start s at 0x01. Instead, it places s at the next address that is divisible by 4:

0x00   a
0x01
0x02
0x03
0x04   s.x
0x05   padding
0x06   padding
0x07   padding
0x08   s.y
0x09
0x0A
0x0B

On the other hand, if the structure is:

struct test {
char x;
char y;
};

then the structure only requires 1-byte alignment, so it can immediately follow a:

0x00 a = 'z'
0x01 s.x = 'b'
0x02 s.y = 10

So my understanding is that the compiler doesn't simply place every variable at the next address. Instead, it looks at the alignment requirement of the next object. If the next object only needs 1-byte alignment, it can start at the very next address. If it needs 4-byte alignment, the compiler moves to the next address divisible by 4 before placing it.

 

Now want to understand why it prefers the aligned layout over the unaligned one.

suppose the compiler doesn't align the data:

0x00 a = 'z'
0x01 s.x = 'b'
0x02 s.y (byte 0)
0x03 s.y (byte 1)
0x04 s.y (byte 2)
0x05 s.y (byte 3)

Now with an aligned layout:

0x00 a = 'z'
0x01
0x02
0x03
0x04 s.x = 'b'
0x05 padding
0x06 padding
0x07 padding
0x08 s.y (byte 0)
0x09 s.y (byte 1)
0x0A s.y (byte 2)
0x0B s.y (byte 3)

On the other hand, if the structure contains only two char members:

0x00   a = 'z'
0x01   s.x = 'b'
0x02   s.y = 'j'

What is the actual advantage of alignment? we say a 32-bit processor can read 4 bytes at a time, what difference does it make whether s.y starts at 0x02 or 0x08? What extra work does the processor have to do in the unaligned case, and why is the aligned case more efficient?

 

On many processors, an unaligned access is an error that results in a trap, so it is an error for the compiler to generate one.

In many others, an unaligned access requires two memory accesses to get all the bytes it needs, so it takes longer.

 

I think I'm starting to understand the idea, so let me know if my understanding is correct.

If I have:

char a;
char b;
char c;

then all of them only require 1-byte alignment, so they can simply be placed one after another:

0x00   a
0x01   b
0x02   c

Now consider:

struct test {

    char x;
    int y;

};

struct test s;
char a = 'z';

Since struct test contains an int, the structure itself requires 4-byte alignment. So if a is placed at 0x00, the compiler cannot start s at 0x01. Instead, it places s at the next address that is divisible by 4:

0x00   a
0x01
0x02
0x03
0x04   s.x
0x05   padding
0x06   padding
0x07   padding
0x08   s.y
0x09
0x0A
0x0B

On the other hand, if the structure is:

struct test {
char x;
char y;
};

then the structure only requires 1-byte alignment, so it can immediately follow a:

0x00 a = 'z'
0x01 s.x = 'b'
0x02 s.y = 10

So my understanding is that the compiler doesn't simply place every variable at the next address. Instead, it looks at the alignment requirement of the next object. If the next object only needs 1-byte alignment, it can start at the very next address. If it needs 4-byte alignment, the compiler moves to the next address divisible by 4 before placing it.

Declaring a struct does not allocate any memory. It merely tells the compiler that, should you ever actually make a variable that is one of these, this is what it looks like. Your program only has one struct, namely 's'.

The alignment for a struct is independent of the alignment for the items within it. As far as the compiler is concerned, references to structures are to a block block of a certain size.

 

What is the actual advantage of alignment? we say a 32-bit processor can read 4 bytes at a time, what difference does it make whether s.y starts at 0x02 or 0x08? What extra work does the processor have to do in the unaligned case, and why is the aligned case more efficient?

That answer lies in asking HOW can a processor read 4 bytes at a time.

Now, actual modern computer systems are extremely complex, with all of the caches and DRM and multicore processors that share caches and a bunch of other things. To keep things simply, consider a 32-bit processor that is connected directly to RAM with a 32-bit data bus. If you were responsible for making the RAM design and your priority was speed of access and memory capacity, as well as keeping as inexpensive to manufacture as possible, how would you do it? You know you need to deliver 32 bits of data with every request, starting at the memory address placed on the address lines. What if you said that you would serve that data aligned on 32-bit boundaries? That means that you don't even need the last two bits of the address, since they will always be zero. Not only does that make your circuitry simpler, since you don't need to decode them, but it makes the motherboard circuitry simpler, which allows components to be placed closer together, which allows them to be clocked a bit faster. It also means that the CPU doesn't have to output those signals and drive those lines, which reduces the pin count on the CPU and reduces power consumption. Inside your RAM, it also means that each one of your 32 data pins only has to connect to every 32nd RAM cell, as opposed to every 8th one. That simplifies the circuitry considerably, which makes the RAM chips smaller, faster, and cheaper at the cost of a loss of flexibility.

The cost of that loss of flexibility manifests itself in two ways. If the processor and compiler allow unaligned data, then to read a 4-byte value from an address that is not on a 4-byte boundary requires two reads and some additional operations. For instance, let's say that you want to read x, which consists of the bytes [x3,x2,x1,x0], from address 0x05 in Register D. In RAM, it is stored as follows,

----------------
0x00
0x01
0x02
0x03
----------------
0x04
0x05 x0
0x06 x1
0x07 x2
----------------
0x08 x3
0x09
0x0A
0x0B
----------------

You first have to read the data that is in one of the two 4-byte words into D, then shift them to their final location (or have the additional circuitry to do the shift as part of the store), then you have to do a second memory access to get the rest of the data from the other 4-byte word, shift it, and the logically OR it with what you read in previously. But, if it were aligned on a 4-byte boundary, you could just read it in directly in a single read and store it right into the register.

The other cost is that, to keep the speed up, you have to accept memory that is effectively lost to your program as variables are padded to meet alignment requirements.

 

consider a 32-bit processor that is connected directly to RAM with a 32-bit data bus.

So, as I understand it, we have program memory, where the program instructions are stored, a PC (Program Counter) that points to the next instruction to execute, and RAM, where the actual data is stored.

For example, if a 4-byte value is stored starting at 0x04:

0x04 x0
0x05 x1
0x06 x2
0x07 x3

If the CPU needs to read this value, it starts from address 0x04 and reads the 4 bytes. So I understand why this is considered aligned.

But I'm confused about the unaligned case. Suppose the 4-byte value starts at 0x05:

0x04
0x05 x0
0x06 x1
0x07 x2

0x08 x3
0x09
0x0A
0x0B

If the CPU is asked to read 4 bytes starting from 0x05, wouldn't it simply read:

0x05, 0x06, 0x07, 0x08

in the same way?

My understanding is that RAM is not physically divided into fixed 4-byte blocks. Each address represents a byte, so the CPU can request data starting from any address.

So in both cases the CPU is reading 4 bytes:

Aligned:
0x04 → 0x05 → 0x06 → 0x07

Unaligned:
0x05 → 0x06 → 0x07 → 0x08

If that's the case, I don't understand why the second case would require more time or two memory accesses.

 

You are making the assumption that RAM is byte addressable. This might not be the case.
If RAM is accessed as 4 bytes at a time, you don't need the least two address bits to access a 32-bit word.

 

So, as I understand it, we have program memory, where the program instructions are stored, a PC (Program Counter) that points to the next instruction to execute, and RAM, where the actual data is stored.

For example, if a 4-byte value is stored starting at 0x04:

0x04 x0
0x05 x1
0x06 x2
0x07 x3

If the CPU needs to read this value, it starts from address 0x04 and reads the 4 bytes. So I understand why this is considered aligned.

It doesn't START at 0x04, read a byte, the move on to 0x05 and read a byte, and so on.

It gives the address 0x04 to the memory (which we are assuming is RAM and that there is no cache involved, but the issues are the same) and the memory gives it all four bytes all at once.

In reality, the CPU probably doesn't give the memory the full address 0x04, it gives it the address 0x01 because the memory has no use for the lowest two bits. It provides data in four-byte blocks and any four-byte block it provides starts on a 4-byte boundary.

But I'm confused about the unaligned case. Suppose the 4-byte value starts at 0x05:

0x04
0x05 x0
0x06 x1
0x07 x2

0x08 x3
0x09
0x0A
0x0B

If the CPU is asked to read 4 bytes starting from 0x05, wouldn't it simply read:

0x05, 0x06, 0x07, 0x08

in the same way?

I explained that in the prior post. To get four bytes starting at 0x05, you would need to get four-bytes at address 0x00, pull out the data at 0x05, then get the four bytes at 0x04 and pull out the bytes at 0x06, 0x07, and 0x08. Then shift them appropriately and combine them.

You could certainly do this, but doesn't it make sense that it would take more time?

You could also make CPUs and RAMs that allow unaligned access, and those certainly exist. They generally cost more and are slower, because of the added complexity. So why do it if you don't need to be able to use unaligned data?

My understanding is that RAM is not physically divided into fixed 4-byte blocks. Each address represents a byte, so the CPU can request data starting from any address.

So in both cases the CPU is reading 4 bytes:

Aligned:
0x04 → 0x05 → 0x06 → 0x07

Unaligned:
0x05 → 0x06 → 0x07 → 0x08

If that's the case, I don't understand why the second case would require more time or two memory accesses.

Maybe, maybe not. What if that 4 bytes cross a cache-line boundary? Also, modern processes have ways of insuring atomic operations of some instructions, meaning that they cannot be divided in such a way that other operations can see any intermediate result. If a memory access crosses a cache-line boundary, that becomes a lot harder to guarantee and the added complexity will likely slow down performing even operations that don't cross the boundary. So, again, why add the complexity and accept the performance hit unless there is a compelling reason?

Then there is the ABI that compiler's generate code in compliance with. This is to ensure that the code generated by other compilers, compiling other languages, using other libraries of pre-compiled functions, can interact. That's only possible if they all agree on how memory is laid out, Keep in mind that just because I write a program today that is going to run on today's latest PC, that doesn't mean that it isn't going to get linked to functions from libraries that are decades old. The ABI needs to be stable and backwards compatible.