Function Call Stack in C

What are Stacks in C?

• In C, stack is a Linear Data Structure where elements are stored at contiguous memory locations.
• Stack follows the LIFO mechanism, i.e. Last in First Out. Let’s understand LIFO mechanism more clearly by an example.
  • In tower of Hanoi, all the disks are placed on a peg. It must be placed on the top of the peg to insert a new disk.
  • The top disk must be removed from the peg before removing any other disk, this is the LIFO mechanism.
• Stack follows a standard terminology for every operation.
  • Push: Inserting an element at the top of stack.
  • Pop: Removing an element from the top of the stack.
  • Peek: Returns the top element of the stack without deleting.

What is Call Stack in C?

• Call stack is a dynamic data structure maintained inside the RAM memory by the Operating System.
• Primary task of Function Call Stack in C is to manage the function calls and how they pass parameters to each other.
• A call stack is maintained for each task and for each thread. It is also called an execution stack or machine stack. More often, it is simply known as a stack.
• Now let’s look at how function calls are actually organized in a stack: Let’s assume we have two functions f1() and f2() along with main().

Activation record: When a function calls another function, an entry is pushed to the stack. This entry is called as Activation Record.

Activation record contains parameters, local variables, and return address that the called function needs to return to the calling function.

• On running the program, the main() is called, so an activation record for main() is created and added to the stack.
• Now, main() calls f1(), which creates an activation record for f1() on top of stack and f1() calls f2() by adding activation record for f2() on top of stack.
• When f2() terminates, its activation record is removed from the stack.
• After completing the execution of f1(), it returns by removing the activation record from the stack.
• At this stage, we are back to our main() which removes its activation record leading to the termination of the program.

Execution Model of C

• Considering the fact that C is a procedural programming language, C doesn’t support writing code outside of a function.
• In simple words, execution model of C means how function calls work and how the functions work.
• C uses stack data structure to implement functions and stack frames for function calls.
• C stack frame would be generated uniquely to every single processor, compilers follow the function calling conventions based on the processor.

Function Stack Frames in C

Let’s see how a stack frame is generated on an x86 processor.

• As We are considering an x86, the word length is 4 bytes, for other processors, the word length might be different.

Read the following points regarding the x86 processor:

• The stack grows downwards, it starts from a higher address and then moves to a lower address.
• Push operation is used to add items to the stack while Pop operation is used to remove items from the stack.
• If the stack pointer is at 1000, if we add an item to the stack, then the stack pointer points to 996(1000 - 4).
• At this stage, if we perform a pop operation, the stack pointer gets incremented and points to the address 1000 (data at 996 is popped from the stack).

Let's look at typical x86 stack frame as shown below: [Callee Saved Registers EBX(base register), ESI(Source Index),EDI(Destination Index)]

• EBP Indicates the origin of the current stack frame. Offsets of EPB are used to access other memory locations.
• During the execution of a program, each function maintains separate stack frames in C, each function has a stack frame at a starting address pointed by EBP.
• The table shows how the function call stack in c is organized and explains how data can be accessed from it (Later in this article, we will discuss this function stack frame with an example).

Read the following regarding registers:

• Generally, data is stored and accessed from memory, this process is a little bit slower.
• To avoid this delay, processor includes some internal memory called Registers.
• Limited registers are built on processors for processing data elements without having the need to access the data from memory.
• x86 processor uses the following registers:
  • EBX: It is a 32-bit base register used in indexed addressing.
  • ESI: It is a 32-bit source register used to store source index of string operations.
  • EDI: It is a 32-bit destination register used to store destination index of string operations.
  • EAX: It is a 32-bit accumulator which is mostly used for arithmetic operations.
  • ECX: It is a 32-bit counter register used to store the loop count.
  • EDX: It is a 32-bit data register used in I/O operations.

Function Calls in C

Here, Let’s see how stack frames are created when one function calls another function and finally returning back after completing the execution.

Let's consider we have two functions like fun1 and fun2. Here, fun1 is calling fun2.

Events done by fun1 prior to calling fun2 are:

• Registers like EAX, ECX, EDX are pushed by fun1.
• All the parameters required by fun2 are pushed by fun1.
• fun1 pushes EIP (current instruction pointer) to stack, it would be used by fun2 as the return address for fun1 (automatically done by call instruction).

Events done by fun2 before executing its body:

• fun2 pushes its current EBP to stack.
• fun2 converts its EBP to ESP, which is treated as new stack frame address for the function.
• All the local variables in fun2 would be pushed to the stack.
• If there is complex computation required for producing intermediate results, then fun2 allocates temporary storage to the call stack (optional).
• Registers like EBX, ESI, EDI are saved to stack (optional).
• fun2 starts to execute its own body.

Events done by fun2 before returning to fun1:

• Return value of EAX register is saved by fun2.
• Register values of EBX, ESI, EDI are restored by fun2 (optional as they will be restored if they are updated).
• fun2 releases the temporary storage occupied for local variables and sets back stack pointer to EBP (the above two steps are done using the ‘leave’ instruction).
• To bring back stack frame of fun1 it pops ESP contents to EBP.
• fun2 pops the return address from stack and goes to that address. So, finally fun2 is returned to fun1 (use ‘ret’ instruction).

Events done by fun1 after returning from fun2:

• fun1 does not require pushing the parameters of fun2, so it sets the ESP accordingly.
• It saves the return value from EAX register.
• Restores the register values of EAX, EBX, EXC, only if required.

C code for demonstrating stack frames

Stack frame generated for fun1 calling fun2 and fun2 returning to fun1: