Memory

When we define functions and variables, how do our computers store that information? There are many complicated things going on behind the scenes, but as a C programmer, you just need to have this one mental model of how memory is managed, displayed below.

At the top, you have compiled code and static variables, which have a fixed size and live until the whole program finishes its execution. Then, you have the stack, which has a variable size and stores all the important details (parameters, local variables, and return addresses) of the functions that are running.

How Stack Works

To understand how the stack works, let's look at the following code in C.

int add (int a, int b) {
    return a + b;
}
 
int main () {
    int x = 1;
    int y = 2;
    int z = add(1, 2);
    return 0;
}

Let's run the above program and track how the stack changes over time. When you start the program, it will automatically look for main and place the main stack frame at the top of the stack, containing parameters, local variables, and the return address. In this scenario, we will store the return address and local variables x and y on a stack like stack a.

Then, the main function calls another function, add, where we add another stack frame for add, like stack b. As we have access to all the values required to compute the output for add, we compute the output for add and replace the value at the return address with the output. When this happens, all the parameters and local variables for add will get deleted, and the result will be part of the main stack frame, like stack c. Then, as all of the computations are executed, we replace the return link with 0, which results in an empty stack like stack d at the end of the execution of the whole program.

The stack stores relevant data next to each other so that we can have quicker access to them (higher chance of cache hit and efficient use of memory), and it automatically deletes the data that is no longer used. For the stack to be able to store data next to each other, though, it needs to know how much memory must be allocated to each variable. This is why compilers require us to specify types of the variables, which can be used to deduce the amount of memory to allocate for the variables.

When the stack gets full (which can happen in many ways, such as too many recursive function calls and too much data consumption), we will get a stack overflow error. (Yes, this is where that website's name comes from!)

Heap

The stack is great, but automatically deleting the data after function execution is sometimes not desirable. Let's look at an example of when it is undesirable for variables to be automatically discarded.

void slice (int **arr, int start, int end) {
    if (start < end) {
        int copy[end - start];
        int index = 0;
        int *p = *arr;
        for (int i = start; i <= end; i++) {
            copy[index] = p[i];
            index++;
        }
        *arr = copy;
    }
}
 
int main () {
    int xs[6] = {1,4,4,2,8,6};
    int *p = xs;
 
    slice(&p, 1, 4);
    printf("%d %d %d %d", p[0], p[1], p[2], p[3]); // => corrupted
    return 0;
}

Here, we defined the slice function, which takes the array pointer and creates a sliced array. We pass a pointer instead of the array itself because arrays cannot be reassigned while pointers can. The slice function aims to first create a sliced array in the stack and change where the pointer is pointed to the newly created array. However, this does not work properly because the variable copy is in the stack and will get deleted from the stack once slice finishes its execution.

Can we store data even after the function that the data lives finishes its execution? Is there a way that we can control when the memory gets deleted and how much memory gets allocated freely? The answer is yes. With the heap, we can dynamically allocate memory, meaning we get to control how much memory is allocated and when it gets deleted.

Dynamic Memory Allocation

Let's rewrite the slice using dynamic memory allocation so that copy does not get deleted after the function execution ends.

void slice (int **arr, int start, int end) {
    if (start < end) {
        // Dynamically allocate memory
        int size = end - start + 1;
        int *copy = malloc(sizeof(int)*size);
 
        int index = 0;
        int *p = *arr;
        for (int i = start; i <= end; i++) {
            copy[index] = p[i];
            index++;
        }
        *arr = copy;
    }   
}
 
int main () {
    int xs[6] = {1,4,4,2,8,6};
    int *p = xs;
 
    slice(&p, 1, 4);
    printf("%d %d %d %d", p[0], p[1], p[2], p[3]); // => 4, 4, 2, 8
 
    // Free memory
    free(p);
 
    return 0;
}

We can dynamically allocate memory with the malloc (memory allocation) function, which takes the size of the memory you want to allocate. You can refer to the values of that allocated memory by dereferencing the pointer that it returns. You can also achieve the same thing with the calloc (contiguous allocation) function, which sets all the values of that memory to 0. Although the behavior is more predictable with calloc as there is no risk of accidentally having random values already stored in the heap and performing operations on those values, it tends to take significantly more time to access each value and set it to 0. (Safety vs. Speed tradeoff)

Once memory is allocated in the heap, it never gets deleted even after execution unless you free up that memory with the free function. This gives us great flexibility and power in manipulating memory. However, great power always comes with great responsibility. If you forget to free up that memory, it will be reserved and remain untouched even after executing the whole program and losing the pointer to access that memory, making the memory unusable forever. This scary event is called a memory leak, and we need to avoid it at all costs by using free at all times.

Memory Reallocation

In some cases, you might want to resize the memory allocated to the pointers. In such cases, the realloc (reallocation) function comes in handy.

int main () {
 
    int *p = malloc(sizeof(int)*2);
 
    p[0] = 1;
    p[1] = 2;
 
    // Add more memory
    p = realloc(p, sizeof(int)*3);
 
    p[2] = 3;
 
    free(p);
 
    return 0;
}

When you call realloc with a smaller size, you are effectively freeing up some spaces previously reserved for that pointer. However, the memory will still be there, so it is important to be reminded of that for heap security.

When realloc receives a bigger size than the pointer, it will first try expanding the memory at the same location. If expanding does not interfere with other memory, then it will expand at the same address. Else, it looks for other spaces and reallocates it to the other address. When you reallocate, the memory will still be there, so you need to handle it properly. Also, if there is no available contiguous space in the heap, it returns NULL. You need to handle that case properly as well. The following is an example of how you might want to handle those cases.

int *p = malloc(sizeof(int)*2);
 
    p[0] = 1;
    p[1] = 2;
 
    // Add more memory
    int *temp; // temp pointer for not losing address in p
    temp = realloc(p, sizeof(int)*3);
 
    if (temp == NULL) {
        return 1;
    }
    
    // Set numbers to 0 when address changes
    if (p != temp) {
        p[0] = 0;
        p[1] = 0;
    }
 
    p = temp;
    p[2] = 3;
    
    free(temp);
    free(p);
 
    return 0;
 

Heap security is a critical thing to keep in mind when storing sensitive data in the heap with malloc, calloc, or realloc. You might want to simply perform encryption when storing sensitive data or set them to 0, like the above, when you finish using them.

Garbage Collector

Unfortunately, history has revealed that we humans are not very good at managing heaps like the above for preventing memory leaks and ensuring heap security. It also turns out that it quickly becomes almost impossible to keep track of pointers as codebases scale. Therefore, many smart individuals have developed garbage collectors in higher-level languages (Python, Haskell, etc.), which run alongside the program to keep track of the heap and free up unused memory automatically. Also, developers have abstracted away the details of pointers altogether in higher-level languages, so that they do not have to worry about how variables are stored in memory. Then, it seems like it is better to use higher-level languages for higher productivity and lower barriers of entry. So, why have we been learning C?

Remember, there are always advantages and disadvantages to everything. Although a garbage collector can ease our programming experiences, it needs to run alongside the program during runtime, which inevitably consumes more memory and makes the execution speed of the program much slower (even though garbage collectors are improving). Also, abstracting away the concept of pointers takes away the flexibility of manipulating memory, which is critical for system-level programming and embedded programming, and helpful for writing faster and more lightweight code.

Hence, whether to use a higher-level language or a low-level language depends on the objective of writing code. If you care more about building things of acceptable quality quickly (not system or embedded programming), then you should probably be better off using a higher-level language. However, if you care more about the quality of the things you build (including system and embedded programming), then you should endure a not-so-smooth programming experience and use a lower-level language. Though, I think learning a low-level language is great and can make you a better programmer even if you might not use it, as I have already said in the first article of this series.

Exercises

From this article, there will be an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• Portfolio Courses. 2021. Dynamic Memory Allocation | C Programming Tutorial. YouTube.
• Portfolio Courses. 2021. realloc Security Vulnerability | C Programming Tutorial YouTube.