Two types of memory: the stack and the heap

Up until now, the only variables we have encountered have been arguments or those declared at the top of a function. Any arrays we have encountered have had a fixed length based on their declaration. While this allows you to do quite a bit, it is very limited. We have yet to see, for example, a way to declare an array with a length that does not come from a constant. In order to get around some of these difficulties, we use dynamic memory allocation. Before we see any actual code, we need to start with a bit of theory.

The problem of memory allocation

The memory in your computer is one big long array of bits. These bits are divided into blocks called bytes (usually 8 bits to a byte) and each byte is given an address. Every single variable in your program has to be put somewhere in memory. The process of deciding what goes where is called allocation.

Imagine that you were put in charge of organizing a large library (the size of Parks) with very picky customers. In order to keep your customers happy, you have to follow a few rules:

  1. Once a book is placed on the shelf and recorded in the card catalog, it can never be moved until it is removed from the collection.

  2. Every series of books or periodicals must be placed on the shelves contiguously (you can’t have part of it on one place and part in another).

As you can imagine, organizing this library is a very difficult task. The books have to be arranged in such a way that they all fit on the shelves without breaking the rules. However, your computer is performing this task every second you use it. In order to make the concepts simpler, we are going to assume that only one program is running and it has access to the entire block of RAM without having to share it with other programs.

Static memory allocation and the stack

The variables that you declare at the top of a function or as arguments are called local variables. These variables can be statically allocated meaning that the computer knows everything about them at the time the program is compiled and only has to worry about arranging them once. Statically allocated variables are arranged the same way (and possibly have the same memory address) every time the program is run.

The way the computer arranges these variables is by using something called the stack. The variables and arguments associated with each function are grouped together into a block of memory called a frame. The frames are then stacked on top of each other in the order the functions are called. When a function gets called, a new frame is created right next to the previous one and as functions return their frames are destroyed so that the frame’s memory can be used for something else. If we were to call our binomial function from the main function, the stack would look something like this:

Example of a Stack

This method of arranging memory is very simple and efficient. In order to compute the address of a variable declared in a function, the computer simply adds the variable’s position within its frame to the address where previous frame ends.

This brings us to a very important warning about pointers. You should never declare a variable in a function and then return a pointer to it. This is because, once the function has returned, its frame no longer exists and that memory may be used for something else. Consider the following example:

int *
function()
{
    int value;

    value = 7;
    return &value;
}

int
main(int argc, char **argv)
{
    int *ptr;

    ptr = function1();
    printf("We got a pointer!\n", *ptr);
    printf("The value of the pointer is %d\n", *ptr);
}

What happens when we the main function runs? First, it calls function which assigns a value of 7 to the variable value and then returns the address of value which is stored in ptr. Once function returns, it’s stack frame no longer exists but the value 7 is still sitting in memory and ptr still points to it. The next thing that happens is printf gets called. We have no idea what a stack frame for printf looks like, but we do know it was placed where the stack frame for function used to be. What this means is that ptr now points to something (we don’t know what) inside of the stack frame for printf. When we get to the second printf call, we have no idea what value we will get by evaluating *ptr.

On the other hand, it is safe to pass pointers to local variables into functions you call as long as those functions don’t store them anywhere. This is because, if I have a function a that calls a function b, the stack frame for a will not be removed until a returns which will not happen until b returns. Therefore, it is safe for a to pass the address of a local variable to b.

Dynamic memory allocation and the heap

In addition to the stack, memory in the computer can be dynamically allocated. This means that the computer knows nothing about the piece of memory when the program is compiled but has allocate it at runtime. Dynamically allocated memory is usually placed at the other end of the memory from the stack and they grow towards each other.

In order to do this, C provides two functions: malloc and free which are both found in the stdlib.h header file. The malloc function finds and allocates a block of memory of the requested size and returns a pointer to it. The free function deallocates the memory (marks it as no longer in use) so that it can be used again for something else later. Neither malloc nor free know anything about the type of data you are planning to put in the requested memory. Because of this, the size of the requested block of memory must be given in bytes.

For example, let’s say we wanted to make a structure representing a vector of arbitrary size. We could do so like this:

#include <stdlib.h>

struct vector {
    double *data;
    unsigned int size;
};

void
vector_create(struct vector* vector, unsigned int size)
{
    vector.data = malloc(size * sizeof(double));
    vector.size == size;
}

void
vector_destroy(struct vector *vector)
{
    free(vector.data);
    vector.data = NULL;
    vector.size = 0;
}

void
vector_add(struct vector *in1, struct vector *in2, struct vector *out)
{
    unsigned int i;

    for (i = 0; i < in1->size; ++i) {
        out->data[i] = in1->data[i] + in2->data[i];
    }
}

Let’s first look at the expression malloc(size * sizeof(double)). This function call tells the computer to go out and find a block of memory of the given size and return a pointer to it. Because we have to specify the size of the memory in bytes, we use size * sizeof(double). Next, look at the vector_destroy function. The first line frees the memory so that it can be used by something else later. The next two lines are there to mark this struct vector as not having any data associated with it. The NULL value represents an invalid pointer; this way we know not to try and access it.

Notice that everything in the above example used pass-by-reference. You will frequently see this model when using structures that involve dynamic memory allocation. This is because it ensures that we only have one copy of the given structure in our program; that way we can tell if the pointer is valid (by checking for null for example).

Dynamic memory allocation pitfalls

Dynamic memory allocation is both extremely powerful and extremely dangerous. Because you are manually allocating and deallocating memory, it is up to you, the programmer, to manage it all. If you don’t manage your memory correctly, there are a number of things that can go wrong.

Memory leaks

The most basic rule of dynamically allocated memory is: If you malloc it, make sure to free it. Making sure your program properly cleans up after itself is important because the computer only has a finite amount of memory. Allocating memory without bothering to free it is referred to as a memory leak. If your program has a memory leak, it will continue to take up more and more memory until, eventually, the computer runs out. When this happens, the operating system may forcefully shut your program down, or it may just freeze or crash. Throughout the course, we will learn a variety of techniques for managing memory to try and prevent this problem.

The one exception to this rule is if you plan to allocate a block of memory and use it for the duration of the program’s execution. When your program exits, the operating system will automatically free all of the memory it allocated. That being said, it doesn’t hurt anything to manually free your memory and it’s good to be in the habit of freeing everything you allocate.

Segmentation faults

You will not be programming for very long before you see one of your programs crash with a “segmentation fault” or SIGSEGEV error. A segmentation fault occurs when a program tries to access an invalid block of memory. This can happen in a number of different ways:

This list isn’t meant to scare you, it’s simply meant as a reference for when you encounter this error. Segmentation faults are among the most common errors that occur when writing software. They can also be very hard to find because they are usually caused by a bug in a different place than where the software actually crashed. Eventually, you will get pretty good at mitigating the risk of segmentation faults and finding them when they happen.

Double frees

Another common dynamic memory problem is if you try and free a piece of memory twice. This is called a double free and will most likely crash your program. One way to eliminate this issue is to always set a pointer to NULL after you free it and try to avoid having extra pointers lying around to any given block of memory. The best way to watch out for this is simply to have well-organized code with an organized system for who allocates and frees memory. We will talk about that a bit more in the next section and even more when we get to C++.

Stack overflows

This doesn’t technically have to do with dynamic allocation, but we’ll put it here anyway. A stack overflow is what happens when your stack gets too big. This means that the chain of one function calling another has gotten too long and the system no longer has enough memory to handle it. The usual way this happens is when you have a recursive function that is no longer reaching a base case and returning.

An Example: A dynamic array based list

We will conclude with the following example of a list of items that automatically allocates memory for new items. I have only implemented some of the functions you might want, but it should be enough to demonstrate the concept. Also, you will see my use of the size_t type. This is just an unsigned integer type that is frequently used to represent memory sizes. The system guarantees that if it’s a valid size in memory then size_t is big enough to hold it.

/* array_list.c: An array-based list structure */

#include <stdlib.h>

struct data_struct
{
    /* Some data goes here */
    int integer;
    double real;
};

struct data_array_list
{
    size_t alloc;
    size_t size;
    struct data_struct *data;
};

void
data_array_list_init(struct data_array_list *list)
{
    list->size = 0;
    list->data = NULL;
    list->alloc = 0;
}

void
data_array_list_destroy(struct data_array_list *list)
{
    free(list->data);
    list->size = 0;
    list->data = NULL;
    list->alloc = 0;
}

void
data_array_list_add_array(struct data_array_list *list,
        struct data_struct *data, size_t num_elements)
{
    size_t new_alloc, new_size, i;
    struct data_struct *new_data;

    /* See if the list is big enough */
    if (list->alloc < list->size + num_elements) {

        new_alloc = list->alloc * 2;

        if (new_alloc < list->size + num_elements) {
            new_alloc = list->size + num_elements;
        }

        new_data = malloc(new_alloc * sizeof(*list->data));
        
        /* Copy the old data over to the new list */
        for (i = 0; i < list->size; ++i) {
            new_data[i] = list->data[i];
        }

        free(list->data);
        list->data = new_data;
    }

    /* Copy the data in */
    for (i = 0; i < num_elements; ++i) {
        list->data[i + list->size] = data[i];
    }
    list->size += num_elements;
}

void
data_array_list_add(struct data_array_list *list, struct data_struct data)
{
    data_array_list_add_array(list, &data, 1);
}