Call Stack in C

One of the fundamental properties of the C language is the ability to define and invoke functions. Functions allow dividing a program into smaller and more manageable parts, making the code more readable and maintainable.

A function can, in turn, invoke other functions, thus creating call chains. To implement this mechanism, each process in memory has a Call Stack. In this lesson we will see how the Call Stack works and how it is used to manage function calls in a program written in C language.

Functions that invoke other functions

We have seen, in previous lessons, that a function written in C language can, in turn, invoke another function. The latter can, in turn, invoke another function and so on.

To better understand, let's take a practical example. Suppose we want to create a program that calculates the area of a circle. We can create this program by breaking it down into three functions:

• main: main function of the program, which takes care of asking the user for the radius of the circle and printing the calculated area on screen;
• calculate_circle_area: function that calculates the area of the circle, given the measure of the radius;
• square: function that calculates the square of a number.

The program could be written this way:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>

// Function prototypes
double calculate_circle_area(double radius);
double square(double n);

int main() {
    double radius, area;

    printf("Enter the circle radius: ");
    scanf("%lf", &radius);

    area = calculate_circle_area(radius);

    printf("The area of the circle with radius %.2f is %.2f\n", radius, area);

    return 0;
}

double calculate_circle_area(double radius) {
    double result = 3.14159 * square(radius);
    return result;
}

double square(double n) {
    double result = n * n;
    return result;
}

In this example, the main function invokes the calculate_circle_area function, which in turn invokes the square function. We have, in practice, a chain of function calls.

Let's try to see, in practice, what happens when the program is executed:

1. The main function is invoked by the operating system.
2. The main function invokes the calculate_circle_area function at line 13;
3. The calculate_circle_area function invokes the square function at line 21;
4. The square function calculates the square of the radius and returns the result to the calculate_circle_area function;
5. The calculate_circle_area function resumes its execution at the point where it was interrupted, multiplies the result obtained from the square function by the value of π and returns the result to the main function;
6. The main function resumes its execution at the point where it was interrupted, assigns the result obtained from the calculate_circle_area function to the area variable and prints the result on screen.

Observing carefully the sequence of steps just described we notice that, somehow, the program, whenever it invokes a function, must remember the point where it is within the calling function.

For example, at point 2, when the main function invokes the calculate_circle_area function, the program must remember that, once the execution of the calculate_circle_area function is finished, it must resume execution from line 14 of the main function. If it did not store this information, the program would not know how to proceed at point 6.

Similarly, the program must, somehow, store the information at point 3, in order to be able to resume execution of the calculate_circle_area function at point 5.

How does our program store this information?

To answer this question let's review the diagram we introduced in the lesson on programs and processes. In that lesson we said that a process in memory is assigned four memory areas or rather memory segments.

So far we have seen two: the Text segment which contains the program instructions, and the Data segment which contains global variables.

The third memory segment is the Stack Segment or Call Stack. This memory segment is used precisely to store the information needed to resume execution of a calling function, once execution of a called function is finished.

In this lesson we will deal precisely with this memory segment, the Stack Segment as it is fundamental to understand how function calls work in C language.

But before we can understand how it works, we must clarify a fundamental concept: what is a Stack?.

What is a Stack?

A Stack, in Italian Pila, is a fundamental data structure in Computer Science. A Stack is a dynamic data structure that allows storing and retrieving data in a particular way.

It is the basis of many more complex algorithms and, in particular, is used to manage function calls in a program. The C language uses under the hood a Stack to manage function calls.

To understand how it works we must consider a vertical shelf where we can only stack objects. In other words, we can only insert or remove objects from the top of the shelf.

This shelf is initially empty:

On this shelf only two operations are possible:

• Push: inserts a new object on top of the shelf;
• Pop: removes the object from the top of the shelf.

When an object is inserted on top of the shelf, it is said that a Push has been performed. When the object is removed from the top of the shelf, it is said that a Pop has been performed.

Suppose we want to insert three objects in a Stack, in order A, B and C.

First we perform a Push of object A:

Then we perform a Push of object B:

As you can see, object B is positioned right above object A. In other words it stacks above object A. Hence the name Stack or Pila.

Finally we perform a Push of object C:

Now we have a stack of three objects. Among these, object C is on top. Just like when you have a stack of books or a stack of plates, the object at the top is the last one inserted.

At this point, if we perform a Pop, that is we remove an element from the Stack, the element that will be extracted will not be the first one we inserted, namely A, but the one at the top which in this case is C.

If we think about it, even when we take a book from a stack of books, we cannot remove an element in the middle or at the bottom... Otherwise the stack risks falling. We can only remove starting from the element at the top.

If we perform another Pop, element B will be extracted.

If, at this point we perform the Push of a new element, for example D, we get:

And if we perform a Pop, element D which is the last inserted will be extracted.

To summarize, a Stack is a data structure that allows storing and retrieving data in a LIFO (Last In First Out) way, that is The last to enter is the first to exit.

Call Stack

Now that we know what, in general, a Stack is, we can analyze how the Call Stack works in C language.

The Call Stack is a dynamic memory area that is used to store the information needed to manage function calls.

Let's review the example above of the program that calculates the area of a circle:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>

// Function prototypes
double calculate_circle_area(double radius);
double square(double n);

int main() {
    double radius, area;

    printf("Enter the circle radius: ");
    scanf("%lf", &radius);

    area = calculate_circle_area(radius);

    printf("The area of the circle with radius %.2f is %.2f\n", radius, area);

    return 0;
}

double calculate_circle_area(double radius) {
    double result = 3.14159 * square(radius);
    return result;
}

double square(double n) {
    double result = n * n;
    return result;
}

When the program is executed, the operating system creates a process in memory and assigns an initially empty Stack memory segment to the process itself.

The process starts its execution starting from the beginning of the main function and, at a certain point, reaches line 13 where it invokes the calculate_circle_area function.

To be able to invoke the calculate_circle_area function, the process must store the information needed to resume execution starting from line 14. Actually, to be precise, the process should resume execution starting from the assignment of the area variable at line 13, but let's skip this detail.

To store this information, the process performs a Push on the Call Stack. In particular, the process stores the address of the instruction following the function call, that is the address of line 14. Therefore, the Call Stack will contain the address of line 14:

Having done this, the process jumps to the beginning of the calculate_circle_area function and starts executing the function itself.

When the calculate_circle_area function reaches the function call to the square function, the process must store the address of the instruction following the function call, that is the address of line 21. Therefore it will perform a second Push on the Call Stack:

The process then jumps to the square function. This function has no function calls inside it. Therefore it performs its calculations and reaches the return instruction at line 27.

When the process reaches this line it must return control to the calling function, that is calculate_circle_area. To do this, the process performs a Pop from the Call Stack. In particular, the process extracts the address stored in the Call Stack and jumps to that address, that is to line 21:

Having done this, the calculate_circle_area function resumes its execution from line 21 and calculates the result. When it reaches the return instruction at line 17, the process must return control to the calling function, that is main.

To do this, the process performs a second Pop from the Call Stack. In particular, the process extracts the address stored in the Call Stack and jumps to that address, that is to line 14:

Finally, the main function resumes its execution from line 14 and assigns the result obtained from the calculate_circle_area function to the area variable.

Finally, when the main function reaches the return instruction at line 18, the process ends its execution and releases the occupied memory.

As can be observed, the peculiar characteristics of a Stack are fundamental for managing function calls in a program. Thanks to it, even if it is not directly manipulated by a developer, it is possible to nest function calls inside other function calls transparently.

This last point is fundamental and can be summarized in two concepts:

1. Each Process in Memory has a stack that manages function calls;
2. Developers do not directly access it. Its management is transparent and automatic. However, it is fundamental to understand how it works to write efficient and correct programs.

Stack Frame

We have seen that the Call Stack is used to save, at each function call, the address of the instruction following the function call. But not only.

In reality, the Call Stack is very powerful and versatile. It allows storing many other useful information to manage function calls.

In particular, it is used to:

• Store the parameters passed to the called function;
• Store the local variables of the called function.

Therefore, every time a function is invoked, the process saves on the stack a series of information that collectively take the name of Stack Frame or, in Italian, Activation Record.

To understand what a Stack Frame looks like, let's review the example of the circle area.

Initially, the call stack is empty. When the process, from the main function invokes the calculate_circle_area function, the process must first save on the stack the address of line 14:

But not only. It must also save on the stack the value of the radius parameter passed to the calculate_circle_area function. In this case, the value of radius is 5. Therefore, the Stack Frame will also contain the value 5:

Having done this, the process jumps to the beginning of the calculate_circle_area function and starts executing the function itself.

However, the calculate_circle_area function uses inside it a local variable, that is the result variable. This variable has a lifetime equal to the execution duration of the calculate_circle_area function. In other words, it exists only for the entire time that the calculate_circle_area function is running.

Therefore, the process uses the Stack Frame also to reserve the space needed to store the result variable:

Having done this, for convenience the process also saves the so-called Base Pointer or Frame Pointer. This pointer points to the return address stored in the Stack Frame. In practice, the Base Pointer points to the beginning of the Stack Frame. The purpose of the Base Pointer is to allow immediate access to the return address when the called function ends its execution:

Having done these operations, the calculate_circle_area function can begin its execution.

Therefore, in general, a Stack Frame is composed of:

Similarly, when the calculate_circle_area function invokes the square function, the process will create a second Stack Frame for the square function:

When the square function ends its execution, the process, using the Base Pointer, immediately retrieves the return address and can delete or clean the Stack Frame of the square function:

And so on, for each function call. Therefore also when exiting the calculate_circle_area function, the process can delete or clean the Stack Frame of the calculate_circle_area function:

From this we can derive an important consequence:

Local variables, therefore, reside on the Call Stack unlike global variables which reside in the Data Segment.

In Summary

In this lesson we have seen how the Call Stack works in C language.

In particular we have studied that:

• The Call Stack is a dynamic memory area that is used to store the information needed to manage function calls;
• It is used to store the addresses of the instructions from which to resume execution once the execution of a function ends;
• Each function call creates a Stack Frame that contains the information needed to manage the function call, in particular the return address, the parameters passed to the function and the local variables of the function;
• The local variables of a function are stored in the Stack Frame of the function itself and are removed from memory when the function ends its execution.

Furthermore, we have seen that the Call Stack is a fundamental data structure for managing function calls in a program. Even if it is not directly manipulated by a developer, it is fundamental to understand how it works to write efficient and correct programs.