10.8 – Memory – Stack segment (call Stack)

by subbu on December 6, 2013

Stack:

Before discoursing stack segment, let us see what is stack?
If we consider a stack of plates in a cafeteria, we can perform limited operations on the stack of plates like adding a new plate at the top, removing a plate from the top and looking the color of a plate at a position from the top etc.
Here adding a new plate on the top of plates stack is called push operation, removing a plate from the top of the stack is called pop operation.

Limitation with the stack is that, it works on LIFO principle that is last added plate is first removed (Last In First Out).

Stack of plates

In computer programming a stack is used to hold similar elements like an array but, in an array elements can be added and removed from any where. Where as in stack new element can be added only at the top and removed only from the top that is works on LIFO (Last in fist out) principle.

Top pointer:

Adding a new element at the top of the stack is called push and removing an element from the top of the stack is called pop.
Top pointer is a variable which always holds the index of top element.

Computer stack

Stack segment (call stack):

Stack segment or call stack is located in the higher part of memory and opposite to the heap segment. The stack grows towards the lower part of memory that is towards heap. In other hand heap grows towards higher part of memory that is towards stack. If both heap and stack meets at a point then there would be no free memory and the state is called stack overflow.

Stack and heap segments
Local variables of functions, parameters and addresses of calling functions are pushed on the stack segment. Stack grows as the number of functions called is increased.
Here the top pointer of the stack segment is a stack pointer in the CPU register, which keeps the track of where the top of stack currently is.

What happens when a function is called?

All the local variables and parameters are local to function. Now, we will see what happens when a function is called? Here is a sequence of steps that takes when a function is called

  1. The address of the instruction next to the function call is pushed onto the stack. This is how the CPU remembers where to go after the completion of function execution.
  2. Space is selected on the stack for the function’s return type. It is just a placeholder for now.
  3. The CPU jumps to the function’s definition.
  4. Now, the current top of the stack is held in a special pointer called the stack frame. Everything added to the stack after this point is considered local to the function.
  5. All function arguments are placed on the stack.
  6. The instructions inside the function are executed.
  7. Local variables are pushed onto the stack as they are defined.

What happens when a function is terminated?

The following things happen when a function is terminated

  1. The function’s return value is copied into the placeholder that was put on the stack for the purpose.
  2. Everything after the stack frame pointer is popped off. This destroys all local variables and arguments.
  3. The return value is popped off the stack and is assigned as the value of the function. If the value of the function isn’t assigned to anything, no assignment takes place, and the value is lost.
  4. The address of the next instruction to execute is popped off the stack, and the CPU resumes execution from that instruction.

Now we will see an example to understand the process.

#include<stdio.h>
int sum(int,int);
int main()
{
 int x,y,s;
 x=30,y=67;
 s=sum(x,y);
 printf("Sum of two numbers %d",s);
 return 0;
}
int sum(int a,int b)
{
 int c;
 c=a+b;
 return c;
}

Output:
Sum of two numbers 97

Calling the function:

1) Operating system calls the main() because entry point to any C program is main(). As the control enters into the main(), local variables belongs to main() are pushed onto the stack.

Stack segment - pushing local variebles

2) Address of the next statement to the function call that is the address of printf(“Sum of two numbers is %d”,s); is pushed onto the stack. It helps to go back after the completion of function execution.

Stack segment - pushing address

3) Place holder of returned type is created to store returned value

Stack segment - pushing return type

4) The CPU jumps to the function’s definition. Now, the current top of the stack is held in a special pointer called the stack frame. Everything added to the stack after this point is considered local to the function sum(). All function arguments are placed on the stack.

Stack frame

5) The instructions inside the function begin executing and local variables are pushed onto the stack as they are defined.

Stack segment - pushing parameters

Returning from function:

6) After the completion of function execution sum(), returning value is stored in the place holder that was placed on the stack for the purpose

Stack segment returning value

7) Everything after the stack frame pointer is popped off. This destroys all local variables and arguments.

Stack segment - pop the parameters

8) The return value is popped off the stack and is assigned as the value of the function. If the value of the function isn’t assigned to anything, no assignment takes place, and the value is lost.

Assigning the function - Stack segment

9)The address of the next instruction to execute is popped off the stack, and the CPU resumes execution from that instruction.

pop the address

10) Once the execution of main() is completed, pop() all the local variables of  main() from the stack and control returns to Operating system.

Completing the function execution

At this point it is enough to know that functions are effectively pushed on the stack when they are called and popped off when they return gives you the fundamentals needed to understand recursion, as well as some other concepts that are useful when debugging.

Previous post:

Next post: