How stack works in function call

The Stack in Computer Science

The stack is an important concept in computer science. If you are planning to learn reverse engineering, malware analyzing, exploitation, etc., this concept is a must to learn. After learning about the stack, we can delve into the world of stack buffer overflows. So let's see why we use this stack concept.

In C and many high-level programming languages, we use functions. A function takes some data, processes it, and returns something. How is this possible? We use the stack to give function arguments. In this document, we are going to learn all the required theories about stack architecture.

Some Terminologies About the Stack

The stack always begins from high memory and grows into low memory. There is a special pointer register called "ESP" that deals with the stack. This register always points to the top of the stack. ESP stands for "Extended Stack Pointer," indicating that ESP keeps track of the stack.

Every function has its own stack frame. This is where a function keeps its local variables. When we talk about the stack and stack frames, EBP is another important register. EBP is used to identify the base of a stack frame. So what we call a function's stack frame is the memory area surrounded by EBP and ESP. As ESP points to the top of the stack, when the stack grows, ESP gets reduced because the stack is always growing into lower memory addresses. Similarly, when the stack shrinks, ESP increases.

PUSH and POP with the Stack

Here we are going to talk about two basic operations we frequently do with the stack: PUSH and POP. The instruction PUSH means that we are pushing something onto the top of the stack. If we push something onto the stack frame, the stack should grow more. As you know, the stack grows into lower memory addresses, so ESP (or RSP) will reduce.

Think about pushing an integer onto the stack. An integer is four bytes long, so ESP will reduce by 4 bytes. Let's understand this situation with an image.

Stack Layout Before PUSH

[Image of stack layout before push]

Let's use the PUSH instruction and push the value of eax (Assume that the value of the eax at the moment is 0x5).

push eax

You can see the space allocated for the integer in a blue box.

Pushed a Value to the Stack

[Image of pushed value to the stack]

Now we are going to see the POP instruction. What this instruction does is remove whatever is found at the top of the stack and place it in another register. So after this process, the length of the stack should be reduced, and ESP will go higher.

Think about removing the value at the top of the stack and placing it in EBP. We can just use the command:

pop ebp

So, we can summarize all of the above content into the following:

• The stack starts from high memory and grows into low memory.
• The stack pointer is always pointing to the top of the stack (This can be esp or rsp).
• If we push something (using the PUSH instruction), the stack grows more into lower addresses, so esp will be reduced.
• We can pop off the stack and copy whatever is found on top of the stack into a register. After that, the stack length will be reduced, and esp will go higher.

Example:

[push ebp]: esp --> esp-4 : value of ebp pushed onto the stack.
[pop ebp]: esp --> esp+4 : remove value of the top stack and copy it to ebp.

Function Prologue

The prologue is the process that builds a stack frame for a function. The compiler is responsible for the function prologue. It creates a set of instructions to allocate space in the stack and put some data on it.

You know that every function has its own stack frame. I'm going to write a small C program to demonstrate the function prologue.

int sub_function(a, b){
    int x;
    x = a + b;
    return x;
}

int main(){
    sub_function(4, 5);
    return 0;
}

Here I used a function called sub_function and called it from the main function. The main function is also just a function, so it has a stack frame that holds some data like argc, argv, etc. sub_function() receives two arguments, a and b. It has a local variable called x. At the beginning, x holds nothing. In sub_function(), a and b will be added, and the result will be saved in the local variable x. Finally, sub_function() returns the value of x as the return value. Just a simple program.

Now we can draw a layout of our stack as follows:

[Image of main function stack frame]

For now, we don't examine what is inside the main function's stack frame. Let's see how the function-prologue builds the sub_function's stack frame.

The first thing that happens in the prologue is pushing arguments to sub_function() in the stack. In the main function, we gave 4 and 5 as arguments, so we are going to put them on top of the stack. At the assembly level, we use the PUSH instruction to do this. In the above image, you can see the stack layout after we put arguments on the stack.

Now esp is not the same as before. It has been reduced by eight bytes. Why 8 bytes? Because a single integer is four bytes long. 0x5 and 0x4 are the hexadecimal representations of five and four.

Pushed Function Arguments onto the Stack

[Image of pushed function arguments onto the stack]

You may notice a special thing: when we push these arguments, the second argument (value 5) is pushed before the first argument (value 4). I'll explain why we do that in the next tutorial. Let's see what happens next.

We are calling sub_function() in the middle of the main function. So in the main function, there are some other things to do after completing sub_function(). The structure of CPU instructions is something like the following:

CPU Instructions in Multiple Functions

[Image of CPU instructions in multiple functions]

In the above three sections, there is a list of CPU instructions, and the EIP register is pointing to the instruction that should be executed next. So the CPU looks at EIP and decides what to execute.

When we switch to sub_function() from main, we set EIP to the first instruction of sub_function(). What happens when the CPU completes the execution of sub_function()? There are some other instructions in the main after sub_function(). So how do we set the EIP to the next instruction in main? The solution to this problem is saving the address of that instruction in the stack. Take a look at our C program. The instruction after sub_function(4, 5) is return 0. So we save the address of return 0 in the stack. We call it the return address, which holds the location to jump after completing sub_function().

Stack Layout After Pushing EIP

[Image of pushed-old-eip-value-on-the-stack]

Now we are going to see the next steps. You know that we identify a function's stack frame with EBP and ESP. EBP is the beginning point of the stack frame, while ESP indicates the top of the stack frame. So the main() function is using EBP to identify its stack frame. But sub_function() also needs EBP to mark its stack frame. So what we do here is save the current value of EBP in the stack. When we finish sub_function() and switch to main(), we get this saved EBP value from the stack and save it again in the EBP register. So main() function can use it again with no errors.

Stack Layout After Pushing EBP

[Image of stack-tutorial-pushed-old-ebp-value]

You have to understand that both EIP and EBP are 4 bytes in size. So compared to the initial ESP value, it has now been reduced by 16 bytes (two arguments, return address, and EBP value). At this moment, the current value of ESP is the same as the current value of EBP, and we can initialize our stack frame from there.

Remember, this is the structure of the sub_function() stack frame.

Initialized sub_function() Stack Frame

[Image of initialized sub function stack frame]

Now in our C program, we need a local variable called x in sub_function(). We are going to allocate space for this local variable in the stack. Let's use the next two instructions:

mov ebp, esp

sub esp, 4

mov ebp, esp means "let's take the current value of ESP and store it in EBP". This is what identifies the beginning of the stack frame. After that, we need a variable of type integer (four bytes) for x. Therefore, we reduce ESP by four bytes. So ESP goes lower and shows the current top of the stack.

Allocated Space for the Local Variable

[Image of stack after allocating space for local variable]

That is how a function stack frame is created. Understanding this will help you a lot when we move on to reverse engineering. In the next part of the tutorial, we will learn how the compiler generates assembly code to implement this concept.

Happy Coding!