The Stack

In this article I want to describe how the stack works and how it is structured.

Background information

The stack is a LIFO (Last In First Out) data structure used to store information about functions of a running program.

The information store in the stack follow some specifications, for x86-64 architecture the System V ABI (Application Binary Interface) is a set of specification that define libraries, function, executable, how these elements interact with each other and much more.

System V ABI

For x86-64 architecture the System V ABI defines (among other things):

  • The stack grows towards low memory locations.

  • The registers RDI, RSI, RDX, RCX, R8, R9 (in this order) are used to pass parameters to a function (this different than in 8086 architecture). If a function requires more parameters they will be pushed into the stack.

  • The stack alignment is 16 bytes

Conceptually, on x86-64 architecture the stack looks like this:

Let’s now run an example program and check what is actually stored in the stack.

The example program

The program that we are going to execute is:

    // file: example64.c
    int function(int a, int b)
    {   
        int c;
        c = a * b;
        return c;
    }    

    int main(int argc, char* argv[])
    {   
        int d;
        d = function(7,15);
        return d;
    }

I am going to compile the code as :

    $ gcc -mpreferred-stack-boundary=4  -fno-stack-protector -o example64 example64.c

When decompiled the main function looks like:

    Dump of assembler code for function main:
       0x0000000000000613 <+0>:    push   rbp
       0x0000000000000614 <+1>:    mov    rbp,rsp
       0x0000000000000617 <+4>:    sub    rsp,0x20
       0x000000000000061b <+8>:    mov    DWORD PTR [rbp-0x14],edi
       0x000000000000061e <+11>:   mov    QWORD PTR [rbp-0x20],rsi
       0x0000000000000622 <+15>:   mov    esi,0xf
       0x0000000000000627 <+20>:   mov    edi,0x7
       0x000000000000062c <+25>:   call   0x5fa <multiplication>
       0x0000000000000631 <+30>:   mov    DWORD PTR [rbp-0x4],eax
       0x0000000000000634 <+33>:   mov    eax,DWORD PTR [rbp-0x4]
       0x0000000000000637 <+36>:   leave  
       0x0000000000000638 <+37>:   ret 
    End of assembler dump.

In line 5 and 6 we can see that the parameters passed to the main function are store in two memory locations [rbp-0x14] and [rbp-0x20]. In fact, in Background Information you can see that the first two parameters are passed in register rdi and rsi.

In line 7 and 8 we can see that the function parameter 15 and 7 are being positioned in the rdi and rsi registers before the call of the multiplication function (they are stored in esi and edi that are the lowest 32 bit parts of the 64 bit registers rdi and rsi ).

Set a breakpoint in line 8, .i.e., just before the call to the multiplication function. When the program hit the breakpoint the stack will look like this:

    gef➤  dereference $rsp 5
    0x00007fffffffdd20│+0x0000: 0x00007fffffffde28  →  0x00007fffffffe1af  →  "/home/pippo/example64"	 ← $rsp
    0x00007fffffffdd28│+0x0008: 0x00000001555544f0
    0x00007fffffffdd30│+0x0010: 0x00007fffffffde20  →  0x0000000000000001
    0x00007fffffffdd38│+0x0018: 0x0000000000000000
    0x00007fffffffdd40│+0x0020: 0x0000555555554640  →  <__libc_csu_init+0> push r15	 ← $rbp

In line 2, it is shown the result of the instruction DWORD PTR [rbp-0x20],rsi (in line 6 of the disassembled main). The memory value is the second parameter of the function main, in fact it was stored in register edi, i.e., the register that contains the second parameter of function call. The memory location rbp-0x20 points to the byte with value 0x28 (i.e., the right most byte of the value 0x00007fffffffde28). Remember that we are in a little-endian architecture so the address with value 0x00007fffffffde28 will store its lowest byte in the highest position in memory. We also need to remember also that the stack grows towards lower memory locations.

In line 3, there is the result of the instruction DWORD PTR [rbp-0x14],edi (in line 6 of the disassembled main). In the stack is copied only 4 bytes, i.e., edi (DWORD).

In line 5, this is the space used to store the local variable d as shown in line 11 of the C code. As you can see, it is declared as int, i.e., it occupy 4 bytes.

If we sum up the 4 bytes used to store the argc + the 8 bytes of the argv[] + the 4 bytes of the d variable the total is only 16 bytes. Why the program is allocating 32 bytes sub rsp,0x20 (in line 4 of the disassembled main)?. Although, argc is passed in the register edi that is 4 bytes, the stack reservation is for the full register i.e., 8 bytes. Furthermore, the program has been compiled with the option -mpreferred-stack-boundary=4 that align the stack to multiple of 2^4 bytes i.e., 16 bytes. Therefore, the only option was to allocate the nearest multiple of 16 bytes i.e., 32 bytes (or 0x20 bytes).

GDB tip. In GDB, it’s easy to get confused regarding the position of each byte because they are usually display in groups of 8 bytes. To have a visual graphical representation of the memory location, you can follow this sign:

Here, the address on the left, points to the right most byte on the right, that is also the lowest memory address on the line. Following the arrow to reach the top of the stack, that means going toward low memory addresses.

Continue the example. Let’s now see what does the multiplication function looks like when disassembled:

    gef➤  disassemble multiplication
    Dump of assembler code for function multiplication:
      0x00000000000005fa <+0>:	push   rbp
      0x00000000000005fb <+1>:	mov    rbp,rsp
      0x00000000000005fe <+4>:	mov    DWORD PTR [rbp-0x14],edi
      0x0000000000000601 <+7>:	mov    DWORD PTR [rbp-0x18],esi
      0x0000000000000604 <+10>:	mov    eax,DWORD PTR [rbp-0x14]
      0x0000000000000607 <+13>:	imul   eax,DWORD PTR [rbp-0x18]
      0x000000000000060b <+17>:	mov    DWORD PTR [rbp-0x4],eax
      0x000000000000060e <+20>:	mov    eax,DWORD PTR [rbp-0x4]
      0x0000000000000611 <+23>:	pop    rbp
      0x0000000000000612 <+24>:	ret    
    End of assembler dump.

In this function we can see that there is no space reservation in the stack as in line 4 of the main disassembled function. We can see parameters copied above rsp in line 5 and 6. In this particular case, since these parameters are used just after it, there is no harm in coping them above rsp.

Set a breakpoint in line 12. Once we hit the breakpoint, we can see that stack as follow:

    gef➤  dereference $rsp
    0x00007fffffffdd18│+0x0000: 0x0000555555554631  →  <main+30> mov DWORD PTR [rbp-0x4], eax	 ← $rsp
    0x00007fffffffdd20│+0x0008: 0x00007fffffffde28  →  0x00007fffffffe1af  →  "/home/pippo/example64"
    0x00007fffffffdd28│+0x0010: 0x00000001555544f0
    0x00007fffffffdd30│+0x0018: 0x00007fffffffde20  →  0x0000000000000001
    0x00007fffffffdd38│+0x0020: 0x0000000000000000
    0x00007fffffffdd40│+0x0028: 0x0000555555554640  →  <__libc_csu_init+0> push r15	 ← $rbp

In line 2, we can see that rsp is pointing toward the memory location of the instruction that needs to be executed when the program finished the execution of the multiplication function. (Here, the rbp point already to the previous memory frame and it is ready to resume the execution of the main.)

This is the end of this stack walkthrough. I hope it was helpful, additional resources follows.



Additional resources

More to read about System V ABI: