Function Call Stack in C

Learn via video course
FREE
View all courses
C++ Course: Learn the Essentials
C++ Course: Learn the Essentials
by Prateek Narang
1000
5
Start Learning
C++ Course: Learn the Essentials
C++ Course: Learn the Essentials
by Prateek Narang
1000
5
Start Learning
Topics Covered

Overview

Function call stack in C is a dynamic data structure where elements are stored at contiguous memory locations. Function call stack is maintained for every function call where it contains its own local variables and parameters of the callee function.

In fact, the function call stack also stores the return address of the function itself. Function call stack in c is widely used in many applications like recursion and calling functions.

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. what are stacks
  • 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 are stacks 2

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.

call stack in c

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)]

Items on StackBase AddressDescription
Callee Saved Registers EBX, ESI,EDIAddress is saved
Temporary storagevariables get temp. storage
Local var #1EBP - 8 0xFF8local variable
Local var #0EBP - 4 0xFFClocal variable
Caller’s EBPEBP + 0 0x1000EBP of main function is saved
Caller’s return addressEBP + 4 0x1004return address of main function
Parameter #0EBP + 8 0x1008parameter field
Parameter #1EBP + 12 0x100Cparameter field
Caller’s saved EAX, ECX, EDXAddress is saved
  • 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:

Items on StackBase AddressDescription
Temporary storage allocationint j gets temp. storage
int jlocal variable of fun2
Save EPB of fun1, EBP = 0x2000fun1's EBP
Save return address of fun1fun1's return address
Pushing arguments for fun2calling fun2 from fun1
Temporary storage allocationint a,b gets temp. storage
int bEPB - 8local variable of fun1
int aEBP - 4local variable of fun1
EBP of main function (fun 1)EBP + 0main function's EBP is saved
Address for returning to main functionEBP + 4main function return address
int xEBP + 8parameter of fun1
int yEBP + 12parameter of fun1

Conclusion

  • Stack is a data structure which follows Last-In-First-Out (LIFO) mechanism.
  • Function call stack in c is a dynamic data structure which is maintained for every function call.
  • Function Call Stack allocates a minimum of four bytes of memory for every x86 register.
  • For x86 register stack grows downwards starting from the highest address in memory.
  • Objective of the function call stack in c is to organize the function calls in RAM.