Stack Frame - Example

Question

I’m developing a program to simulate a Stack, however I’m having some difficulties in understanding how it works, can I correct this example?

main(int y) {
  int j;  
  f(j+1);
}

f(int x) {
  int i;
  return i+1;
}

I made this scheme, for when the main calls the function f, is correct?

Answer 1

In the end it is the compiler who decides and just looking at the source code you cannot complete anything. If you want to write a tool that automatically deduces this, you need to parse a compiled program. GCC, for example, makes all stackframes align in multiples of 16 by default adding paddings. A safer way is to compile code for Assembly (using -S) and analyse from there.

First, I modified your code like this:

main(int y) {
  int j=0;  
  f(j+1);
}

f(int x) {
  int i=0;
  asm("#BREAK POINT"); // Insere um comentário no código assembly. Isso faz nada.
  return i+1;
}

Just to know at what exact point we want to analyze the stack. I also put a value on the variables, otherwise the program would have undefined behavior and anything would be invalid. Then compiling:

main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $32, %esp
    movl    $0, 28(%esp)
    movl    28(%esp), %eax
    addl    $1, %eax
    movl    %eax, (%esp)
    call    f
    leave
    ret
f:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $16, %esp
    movl    $0, -4(%ebp)
    #BREAK POINT
    movl    -4(%ebp), %eax
    addl    $1, %eax
    leave
    ret

Let’s look at it step by step. The stack grows from the bottom up, so let’s consider that the stack starts at esp=320. At the moment it’s empty:

+-----------------------+  <- esp=320

The first step of Assembly is to save the location from where it starts frame previous to main in stack: pushl %ebp.

+-----------------------+  <- 312 (esp)
| 4 bytes: ebp          |
+-----------------------+  <- 320

Then saves the end of the current stack on esp and subtracts 32 bytes of rsp. The and what happens to -16 has the purpose of aligning the stack in a multiple of 16. So it looks like this:

+-----------------------+  <- 272 (esp)
| 32 bytes: nada        |
|                       |
|                       |
|                       |
+-----------------------+  <- 304
| 8 bytes: alinhamento  |
|                       |
+-----------------------+  <- 312 (ebp)
| 4 bytes: antigo ebp   |
+-----------------------+  <- 320

The next instruction is movl $0, 28(%esp). She puts 0 at the address esp+28:

+-----------------------+  <- 272 (esp)
| 28 bytes: nada        |
|                       |
|                       |
| 4 bytes: j=0          |
+-----------------------+  <- 304
| 8 bytes: alinhamento  |
|                       |
+-----------------------+  <- 312 (ebp)
| 4 bytes: antigo ebp   |
+-----------------------+  <- 320

In sequence: movl 28(%esp), %eax addl $1, %eax movl %eax, (%esp) read the value of j (esp+28), sum one and puts in esp+0:

+-----------------------+  <- 272 (esp)
| 4 bytes: arg0=j+1     |
| 24 bytes: nada        |
|                       |
| 4 bytes: j=0          |
+-----------------------+  <- 304
| 8 bytes: alinhamento  |
|                       |
+-----------------------+  <- 312 (ebp)
| 4 bytes: antigo ebp   |
+-----------------------+  <- 320

Then you have the function call call f. Note that call enter the current code address so that the ret can work. The function starts by inserting the old ebp into the stack, updating a new ebp and subtracting 16 from the stack. Next 0 is placed in the stack at ebp-4 (movl $0, -4(%ebp)):

+-----------------------+  <- 248 (esp)
| 12 bytes: nada        |
| 4 bytes: i=0          |
+-----------------------+  <- 264 (ebp)
| 4 bytes: 312          |
+-----------------------+  <- 268
| 4 bytes: enredeço     |
+-----------------------+  <- 272
| 4 bytes: arg0=j+1     |
| 24 bytes: nada        |
|                       |
| 4 bytes: j=0          |
+-----------------------+  <- 304
| 8 bytes: alinhamento  |
|                       |
+-----------------------+  <- 312
| 4 bytes: antigo ebp   |
+-----------------------+  <- 320

And we get to break point. If you continue, you will see the stack crumble as the functions return.

As you can see, there’s a lot going on underneath the covers. This simple example consumed 72 bytes, of which 44 were unused. On the other hand, connect optimizations and you will see that the same code consumes 0 bytes.

A mistake of yours: The return value is not always placed in the stack. It is only when it is of a large object, such as a struct. A int is merely returned straight in the register, in eax.