Stack and Heap

Understanding memory management in C

Photo by Sharon McCutcheon on Unsplash

If you are conversant with the C programming language then you’ve probably heard of memory allocation, memory stack and/or heap. If not, don’t worry I got you, I will be using C to explain how exactly the stack and heap work. Some programmers dub C “a language for dinosaurs”. Don’t judge me, I like C. I explicitly chose C because C does not handle dynamic memory for you.

Before reading this article, all you need to know are the fundamentals for whichever programming language you understand. The underlying concept is more important than the language itself.

To understand how the stack and heap work, let’s have a brief look into the steps of converting our C source code into machine-readable code. I won’t go deeply into the specifics as the aim of the article is to demonstrate how the stack and heap work. For you to run C on your machine, you have to compile it first. Take for instance this simple code that adds up two integers and prints it on your screen:

#include <stdio.h>

int main(void)
{
  int a;
  int b;
  int sum;

  a = 524;
  b = 500;

  sum = a + b;
  printf("My sum: %d\n", sum);

  return 0;
}

When you compile this code using GCC (gcc -o sum sum.c), several things happen under the hood. First, the preprocessor handles directives like #include which brings in the stdio.h header file into your file. The compiler then converts your source code to assembly language specific to your target processor. The assembler transforms this assembly code into machine code (object code). Finally, the linker combines object files with library code to create the final executable. You can examine each stage with specific GCC flags: -E for preprocessing output, -S for assembly output, and -c for object code. Compilation also includes optimizations that can affect memory usage and performance, with levels from -O0 (no optimization) to -O3 (aggressive optimization).

The compiler determines how variables will be allocated in memory, assigns memory locations, and generates the instructions that will manipulate both the stack and heap.

When a C program runs, it receives memory divided into segments. The code segment contains executable instructions. The data segment stores global and static variables. The stack manages function calls and local variables. The heap is used for dynamic memory allocation.
The memory layout also includes other regions like the BSS segment for uninitialized globals and the read-only data segment for string literals and constants. Understanding this organization is important for effective memory management.

The Stack

In our example, variables a, b, and sum are all stack variables. This means that they’re automatically allocated when main() is called and deallocated when it exits.

The stack is a segment that operates on a Last-In, First-Out (LIFO) principle, similar to a stack of books. The first book on a stack of books is usually the last one on the stack and the first one out.

Memory Layout:
+----------------+
|     Stack      |
|  int sum (1024)| <- Top of stack
|  int b (500)   |
|  int a (524)   |
+----------------+
|     Heap       |
|     (Empty)    |
+----------------+
|      ...       |

Let's see what happens step by step:

• When main() starts, space is allocated for a, b, and sum (all integers, typically 4 bytes each)
• Values are assigned: a = 524, b = 500
• The sum is calculated: sum = a + b (1024)
• The value is printed
• When main() finishes, all these variables are automatically removed

When functions call other functions, new stack frames are created on top of existing ones, forming a stack of frames.

Before main() starts:        After main() starts:         After main() ends:
+------------------+         +------------------+         +------------------+
|                  |         |     sum: ???     |         |                  |
|                  |         |     b: ???       |         |                  |
|                  |         |     a: ???       |         |                  |
+------------------+         +------------------+         +------------------+
    Empty Stack                Stack has variables           Empty Again

As execution proceeds:

Assigning values:            After calculation:
+------------------+         +------------------+
|     sum: ???     |         |     sum: 1024    |
|     b: 500       |         |     b: 500       |
|     a: 524       |         |     a: 524       |
+------------------+         +------------------+

The stack is incredibly fast because:

• Memory allocation is just moving a pointer (like moving your hand to the next book position)
• No complex management is needed since the CPU has special instructions for stack operations
• Memory is automatically reclaimed when functions complete

However, the stack has limitations:

• Fixed size (like having a specific table space enough for a set of books)
• All space needs to be known at compile time
• Variables can’t outlive their function

If you try to use too much stack memory, you get a "stack overflow" error. For example:

void infinite_recursion() {
    int big_array[10000];  /* Large stack allocation */
    infinite_recursion();  /* Recursion without exit condition */
}

This code causes a stack overflow error.

The classical factorial (n!) recursion problem is a beautiful demonstration of the stack’s working principle.

Get Nile Okomo’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Here’s the factorial function:

int factorial(int n) {
    /* Base case */
    if (n == 0 || n == 1) {
        return 1;
    }
    /* Recursive case */
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int result = factorial(4);
    printf("Factorial of 4 is: %d\n", result);
    return 0;
}

When we call factorial(4), here's what happens on the stack:

1. Main calls factorial(4):
   The stack creates a frame for factorial(4) with the local variable n = 4. The function sees that n is not 0 or 1, so it needs to calculate 4 * factorial(3).
2. factorial(4) calls factorial(3):
   Before factorial(4) can complete, it needs the result of factorial(3). So a new stack frame is created on top with n = 3. This function needs to calculate 3 * factorial(2).
3. factorial(3) calls factorial(2):
   Again, a new stack frame with n = 2 is created. This function needs 2 * factorial(1).
4. factorial(2) calls factorial(1):
   A new stack frame with n = 1 is created.
5. factorial(1) reaches base case:
   Since n = 1 is a base case, this function immediately returns 1 without further recursion.
6. Return to factorial(2):
   The value 1 is returned to factorial(2), which calculates 2 * 1 = 2 and returns 2.
7. Return to factorial(3):
   The value 2 is returned to factorial(3), which calculates 3 * 2 = 6 and returns 6.
8. Return to factorial(4):
   The value 6 is returned to factorial(4), which calculates 4 * 6 = 24 and returns 24.
9. Return to main:
   The value 24 is returned to main() and stored in result.

Visually, the stack grows and shrinks like this:

Step 1:                Step 2:                Step 3:
+------------------+   +------------------+   +------------------+
| main()           |   | factorial(3)     |   | factorial(2)     |
|                  |   | n = 3            |   | n = 2            |
+------------------+   +------------------+   +------------------+
| factorial(4)     |   | factorial(4)     |   | factorial(3)     |
| n = 4            |   | n = 4            |   | n = 3            |
+------------------+   +------------------+   +------------------+
                       | main()           |   | factorial(4)     |
                       |                  |   | n = 4            |
                       +------------------+   +------------------+
                                              | main()           |
                                              |                  |
                                              +------------------+

Step 4:                Step 5:                Step 6 (unwinding):
+------------------+   +------------------+   +------------------+
| factorial(1)     |   | factorial(1)     |   | factorial(2)     |
| n = 1            |   | n = 1            |   | n = 2            |
| (returns 1)      |   | (returns 1)      |   | (returns 2)      |
+------------------+   +------------------+   +------------------+
| factorial(2)     |                          | factorial(3)     |
| n = 2            |                          | n = 3            |
+------------------+                          +------------------+
| factorial(3)     |                          | factorial(4)     |
| n = 3            |                          | n = 4            |
+------------------+                          +------------------+
| factorial(4)     |                          | main()           |
| n = 4            |                          |                  |
+------------------+                          +------------------+
| main()           |
|                  |
+------------------+

This demonstrates key stack properties:

• Each function call gets its own isolated space for local variables
• The stack grows with each recursive call and shrinks as functions return
• The execution always continues from the top stack frame
• Each frame maintains its own context (value of n)
• The most recently called function is always the first to complete

What do you think would happen If we tried calculating factorial(5000)?

The heap

Unlike the stack, the heap allows for dynamic memory allocation at runtime. The heap is a region of memory that isn’t automatically managed and requires explicit code to allocate and free.

Here’s our example modified to use heap memory:

#include <stdio.h>
#include <stdlib.h>  /* Required for malloc/free */

int main(void)
{
  int *a;
  int *b;
  int *sum;

  a = (int*)malloc(sizeof(int));
  b = (int*)malloc(sizeof(int));
  sum = (int*)malloc(sizeof(int));

  if (a == NULL || b == NULL || sum == NULL) {
    printf("Memory allocation failed\n");
    return 1;
  }

  *a = 524;
  *b = 500;

  *sum = *a + *b;
  printf("My sum: %d\n", *sum);

  free(a);
  free(b);
  free(sum);

  return 0;
}

We use malloc() to request for memory from the heap. Heap memory is managed using functions like malloc(), calloc(), realloc(), and free().

Memory Layout:
+----------------+
|     Stack      |
| int *sum (0x3) | <- Pointers on stack
| int *b (0x2)   |    pointing to data
| int *a (0x1)   |    on the heap
+----------------+
|     Heap       |
| 0x3: int (1024)|
| 0x2: int (500) |
| 0x1: int (524) |
+----------------+
|      ...       |

The heap may be nice since you have the feeling of control. Moreover, it can come in handy when you don’t know the size of the data you’re dealing with beforehand. For instance, Let’s imagine building a contact management program that stores information about people. Since we don’t know in advance how many contacts the user will add, the heap is perfect for this scenario.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Define a structure for contact information */
typedef struct {
    char* name;
    char* phone;
    char* email;
} Contact;

/* Function to create a new contact */
Contact* create_contact(const char* name, const char* phone, const char* email) {
    /* Allocate memory for the Contact structure */
    Contact* new_contact = (Contact*)malloc(sizeof(Contact));
    if (new_contact == NULL) return NULL;
    
    /* Allocate memory for each string and copy the data */
    new_contact->name = (char*)malloc(strlen(name) + 1);
    new_contact->phone = (char*)malloc(strlen(phone) + 1);
    new_contact->email = (char*)malloc(strlen(email) + 1);
   

    if (new_contact->name == NULL || new_contact->phone == NULL || new_contact->email == NULL) {
        if (new_contact->name) free(new_contact->name);
        if (new_contact->phone) free(new_contact->phone);
        if (new_contact->email) free(new_contact->email);
        free(new_contact);
        return NULL;
    }
    
    /* Copy the strings */
    strcpy(new_contact->name, name);
    strcpy(new_contact->phone, phone);
    strcpy(new_contact->email, email);
    
    return new_contact;
}

/* Function to free a contact */
void free_contact(Contact* contact) {
    if (contact) {
        free(contact->name);
        free(contact->phone);
        free(contact->email);
        free(contact);
    }
}

int main() {
    /* Create a dynamic array of contacts that can grow */
    Contact** contacts = NULL;
    int count = 0;
    int capacity = 0;
    
    while (1) {
        printf("\nContact Manager\n");
        printf("1. Add Contact\n");
        printf("2. List Contacts\n");
        printf("3. Exit\n");
        printf("Choose an option: ");
        
        int choice;
        scanf("%d", &choice);
        
        if (choice == 1) {
            char name[100], phone[20], email[100];
            printf("Enter name: ");
            scanf("%s", name);
            printf("Enter phone: ");
            scanf("%s", phone);
            printf("Enter email: ");
            scanf("%s", email);
            
            /* Create contact */
            Contact* new_contact = create_contact(name, phone, email);
            
            /* Resize the array if needed */
            if (count >= capacity) {
                capacity = capacity == 0 ? 1 : capacity * 2;
                contacts = (Contact**)realloc(contacts, capacity * sizeof(Contact*));
                if (contacts == NULL) {
                    printf("Memory allocation failed!\n");
                    exit(1);
                }
            }
            
            /* Add contact to the array */
            contacts[count++] = new_contact;
            printf("Contact added successfully!\n");
        }
        else if (choice == 2) {
            printf("\nContacts:\n");
            for (int i = 0; i < count; i++) {
                printf("%d. %s - %s - %s\n", i+1, 
                       contacts[i]->name, 
                       contacts[i]->phone,
                       contacts[i]->email);
            }
        }
        else if (choice == 3) {
            /* Remember to free your memory */
            for (int i = 0; i < count; i++) {
                free_contact(contacts[i]);
            }
            free(contacts);
            break;
        }
    }
    
    return 0;
}

This example illustrates the following:

1. Dynamic Allocation: We don’t know how many contacts the user will add or how long the name/phone/email strings will be, so we use malloc() to allocate exactly the right amount of memory.
2. Memory Persistence: The contacts remain in memory across multiple loop iterations. They’re accessible from anywhere in the program as long as we have the pointer.
3. Nested Allocations: Each Contact structure contains three string pointers, each pointing to its own heap allocation. This creates a tree-like structure of allocations.
4. Growing Collections: We use realloc() to resize the contacts array as needed.
5. Memory Cleanup: We carefully free all allocations when they’re no longer needed.

Here’s a neat visualization of the heap after adding two contacts:

HEAP
                     +--------------------------------+
                     |                                |
Contact** contacts   |    +----------------------+    |
(on stack) --------->|    |                      |    |
                     |    |  Contact* contacts[0]---->| Contact structure
                     |    |                      |    | - name* --------> "Bob"
                     |    |  Contact* contacts[1]---->| - phone* -------> "0712345678"
                     |    |                      |    | - email* -------> "bob@example.com"
                     |    +----------------------+    |
                     |                                |
                     |    +----------------------+    |
                     |    |                      |    |
                     |    | Contact structure    |    |
                     |    | - name* --------> "Alice" |
                     |    | - phone* -------> "0712345678"
                     |    | - email* -------> "alice@example.com"
                     |    |                      |    |
                     |    +----------------------+    |
                     |                                |
                     +--------------------------------+

However, the heap has a rather painful drawback, it’s slower than the stack since it requires complex memory management and doing this manually makes it prone to errors including memory leaks, dangling pointers, and double-free issues.

In the stack, our variables exist directly on the stack. In the heap, only pointers exist on the stack, pointing to data on the heap. This illustrates how pointers serve as the bridge between these two memory regions.

Common memory issues

/* Memory leak example */
void leak_example() {
  int *p = (int*)malloc(sizeof(int));
  *p = 42;
  /* Missing free(p) - memory leak! */
}

/* Dangling pointer example */
void dangling_example() {
  int *p = (int*)malloc(sizeof(int));
  *p = 42;
  free(p);
  printf("%d\n", *p);  /* Dangerous! Accessing freed memory */
}

/* Buffer overflow example */
void overflow_example() {
  int *array = (int*)malloc(5 * sizeof(int));
  for (int i = 0; i < 10; i++) {  /* Array only has 5 elements */
    array[i] = i;  /* Writing beyond allocated memory */
  }
  free(array);
}

Memory leaks occur when you allocate memory but don’t free it, gradually consuming all available memory. Dangling pointers happen when you access memory after freeing it, causing undefined behavior. Buffer overflows come from writing beyond allocated memory, potentially corrupting data or enabling security exploits. These issues can cause program crashes, data corruption, security vulnerabilities, or unpredictable behavior. They’re often difficult to debug because symptoms may appear far from the actual cause.

Golden Rules for Memory

• Match each malloc() with exactly one free()
• Never use memory after freeing it
• Never free memory that’s already been freed
• Check if memory allocation succeeded before using it
• Initialize pointers to NULL when they’re not pointing to valid memory

Understanding these concepts is key to writing efficient, bug-free C programs. While modern languages often handle memory for you, knowing how memory works "under the hood" makes you a better programmer regardless of your language choice (Don’t argue with me). C might be considered an old language by some, but it continues to power everything from operating systems to microcontrollers because of its efficiency and control.

By understanding this concept, you’re gaining skills that translate to better programming in any language. Happy coding, and remember to free your memory!