Understanding function stack in C

The C function calling convention

For functions, compilers have some convention used for calling them. A convention is a way of doing things that is standardized, but not a document standard. A calling convention describes things such as:

• The order in which parameters are allocated.
• Where parameters are placed (stack or registers).
• Which registers may be used by the function.
• Whether the caller or the callee is responsible for cleaning up the stack on return.

Functions with different calling conventions are incompaticle to each other. There are often subtle differences as to how various compiler vendors or even different versions of the compiler implement these conventions. Thus, it is often difficult to interface code which is compiled by different compilers.

For GNU GCC, __attribute__ keyword is used to state the calling convention as:

while in Borland and Microsoft the convention is specified as:

cdecl calling convention

Arguments are pushed in the stack in reverse order (right to left). Caller (calling function) cleans up the stack. This is de-facto standard for calling conventions on Linux GCC.

The fact that caller cleans up the argument from the stack allows for variable argument lists, eg. printf(). Function values are returned in the EAX register (except for floating point values, which are returned in the x87 register ST(0). EAX, ECX and EDX registers are available for use in the function.

Example in assembly:

/*example of cdecl */
pushl $arg2;
pushl $arg1;
call function;
addl $8, %esp;     /* Stack cleaned by the caller. */

stdcall calling convention

Arguments are pushed in the stack in reverse order (right to left). Callee (function being called) cleans up the stack. This is standard calling convention for Microsoft WIN32 API or Open Watcom C++. Function values are returned in the EAX register. EAX, ECX and EDX registers are available for use in the function.

Example in assembly:

/*example of stdcall */</span>
pushl $arg2;
pushl $arg1;
call function;
 /* No stack cleanup, it will be done by the callee. */

fastcall calling convention

fastcall conventions have not been standardized, and depending on the compiler vendor have been implemented differently. Typically fastcall calling conventions pass one or more arguments in registers speeds up the execution by reducing the number of memory accesses required for the call. If stack is used then it is cleaned by the callee.

C procedure calls and returns

We will narrow down our discussion to stack only. IA-32 utilizes stacks to support procedure calls. When using the flat memory model (in the case of Windows), the stack can be located anywhere in the linear address space for the program. A stack can be up to 4 GBytes long, the maximum size of a segment. Items are placed on the stack using the PUSH instruction and removed from the stack using the POP instruction. On the IA-32 architecture stacks grow downwards from a higher memory address to lower memory address i.e. a push instruction will cause the %esp pointer to decrease, while a pop instruction will cause the %esp pointer to increase. Thus, new data that is pushed will be located at lower memory address than the earlier data items pushed.

A Stack frame is the block of information stored on the stack to effect a procedure call and return. The topmost stack frame is delimited by two registers %ebp serving as frame/base pointer and %esp serving as stack pointer. Each function call creates a new stack framed which is “stacked down” onto the previous stack(s) where each stack frame keeps track of the sequence of function calls and where to return to once the function has completed execution.

C Function stores it’s return value in one or more registers. It is summarized as follows:

GCC expects functions to preserve the following callee-save registers: %ebx, %edi, %esi, %ebp, %ds, %es, and %ss.

Passing Function parameters on the Stack

Before calling a function the required input parameters for the function are pushed on the stack in reverse order. When the call instruction is executed, it places the return address from the calling procedure onto the top of the stack and then jumps to the called procedure. At this point the stack pointer points to the top of the stack, where the return address is located. All of the input parametrs are located “underneath” the return address of the stack. If we pop the values off the stack to retrieve the input parameters the return address might be lost, this causes a problem. One might suggest the use of indirect addressing to access the parameters, but there is a problem with this technique also. While in function, it is possible that part of the function process will include pushing data on the stack. If this happens, it would change the location of the ESP stack pointer and throw off the indirect addressing values for accessing the parameters in the stack.

To avoid this problem, it is common practice to copy the ESP register value to the EBP register when entering the function. This ensures that there is a register that always contains the correct pointer to the top of the stack when the function is called. Any data pushed onto the stack during the function would not affect the EBP register value. To avoid corrupting the original EBP register if it is used in the main program, before the ESP register value is copied, the EBP register value is also placed on the stack.

The input parameters can be accessed using indexed memory location. The first input parameter is localted at indexed memory location 8(%ebp), second at 12(%ebp) and so on. These values can be used throughout the function without worrying about what other values are pushed or popped of the stack.

Function Prologue and Epilogue

At the beginning and end of any procedure the stack frame must be set up and restored as follows:

function:
pushl %ebp
movl %esp, %ebp
.....
....
movl %ebp, %esp
popl %ebp
ret

The first two instructions at the top of the function code save the original value of EBP to the top of the stack, and then copy the current ESP stack pointer (now pointing to the original value of EBP in the stack) to the EBP register.

After the function processing completes, the last two instructions in the function retrieve the original value in the ESP register that was stored in the EBP register, and restore the original EBP register value.

Resetting the ESP register value ensures that any data placed on the stack within the function but not cleaned off will be discarded when execution returns to the main program (otherwise, the RET instruction could return to the wrong memory location). The ret instruction pops the return address in the %eip register and continues execution by jumping to %eip register.

The ENTER and LEAVE instructions are specifically designed for setting up function prologues (the ENTER instruction) and epilogues (the LEAVE instruction). These can be used instead of creating the prologues by hand.

The instructions correspond to

Defining local data variables

Once the EBP register is set to point to the top of the stack, any additional data used in the function can be placed on the stack after that point without affecting how the input values are accessed.

At the start of the function code another line is added to reserve a set amount of stack space for local variables by subtracting the value from the ESP register.

Now, if the data items are pushed on the stack they will be placed beneath the local variables.

Now that the local variables are defined on the stack, they can easily be referenced using the EBP register. Assuming 4-byte data values, the first local variable would be accessed by referencing –4(%ebp), while the second local variable would be accessed by referencing –8(%ebp). when the procedure finishes execution the esp register is set back to it’s original value, the local variables will be lost and will not be directly accessible using either %esp or %ebp register from the calling procedure (thus the name “local variables“).
Now the stack looks like this:

Figure 1: Function Stack

Cleaning out the stack

Before the function is called, the calling program places all of the required input values onto the stack. When the function returns, those values are still on the stack (since the function accessed them without popping them off of the stack). If the main program uses the stack for other things, most likely it will want to remove the old input values from the stack to get the stack back to where it was before the function call.

While you can use the POP instruction to do this, you can also just move the ESP stack pointer back to the original location before the function call. Adding back the size of the data elements pushed onto the stack using the ADD instruction does this.
For example:

pushl %eax;
pushl %edx;
call function;
addl $8, %esp;  /* Stack cleaned by the caller. */

Watching the stack in action

Figure 2: Conceptual Stack Layout

We will try to understand the concepts using a very simple C program. We have seen that the conceptually stack should be as:
We will watch how the data values are placed on the stack area while the program is running by using the debugger.

int add (int a, int b){
        int c;
        c=a+b;
        return c;
}
int main(){
        add(10, 20);
        return 0;
}

This is a very simple C Program which defines a function and calls it from the main function. We will use “-ggdb” flag which tells the compiler to include the debugging information in the generated binary executable file. We will also use “-mpreferred-stack-boundary=num” flag which alligs the stack to 2^num bytes boundary. Default stack alignment is 16 bytes (after GCC 2.96) whereas we have to align the stack at 4 bytes boundary to keep things simple.
We will compile this program as (program stored as func.c) :
gcc -ggdb -mpreferred-stack-boundary=2 -o func func.c

We will start debugging the executable as:
gdb ./func
We will set two breakpoints at the starting of both functions to analyze the stack as following:

Figure 3: Program listing and setting breakpoints

If we run the program then the execution will stop at the first breakpoint encountered and that is inside the main function. If we disassemble the main function we can see the actual instructions being executed :

Figure 4: Dump of assembler code for main

Currently the EIP register is at line 4 (we can see a “=>” at the left hand side of the assembler code). First we can see the function prologue, which is followed by creating space on the stack to pass the input parameter to function being called and then storing the actual arguments in the stack. Interestingly enough the GCC compiler prefers to push the arguments onto the stack using the mov instruction rather than a push. It also addresses the stack pointer directly using the ESP register, instead of using the push and pop instructions. Then we can see the function epilogue.
Few things to note here: first of all until now the main function has created space to pass the input parameters to the function (note “sub $0×8, %esp” instruction) but the parameters are not yet being stored on the stack so they will be containing some junk values, secondly the return address pushed on the stack after the call instruction should be 0x080483c5 which is the next instruction to be executed after the call instruction.
If we take look at the stack at this moment it will look something like this :

Figure 5: Stack Memory

We can see that current stack pointer is at 0xbfffff400, and the space has been made for input parameters.

We continue our program and reach the next breakpoint which is inside the called “add” function. Disassembling the function gives us the following output:

Figure 6: Dump of assembler code for add function

Now we can see that after the usual function prologue, the space is made for local variable “int c” which is 4 bytes in length, then the input paramerets are accessed using indirect addressing from base pointer: the first parameter at 0xc(%ebp) and the second one at 0×8(%ebp) since they are pushed in reverse order. Then the assembler uses “lea” instruction for add operation. This is an optimization which intel strogly recommends since LEA (Load Effective Address) instruction is faster then the ADD instruction. The “lea (%edx, %eax, 1), %eax” instruction evaluates to :

which gives same output as corresponding add instruction would have given. Then the next instruction moves the output to the local variable c, which is accessed using indirect addressing from base pointer. The last instruction before the function epilogue is storing the return value from the local variable “c” to the eax register.

If we look at the stack at this point it’s like:

Figure 7: Stack Memory

Currently %esp points at memory location 0xbffff3f4, this is the space allocated for local variable, after that we have saved old ebp, followed by return address then the two input parameters and then we have stack setup for main function. Current base pointer should point at 0xbfffff3f8, we can confirm this as:

Figure 7: Stack Memory

We can draw the whole stack diagram as:

Figure 9: Stack Layout for our program

This confirms to our conceptual stack layout in Figure 2.

I hope this article was helpful