Memory

So far, you probably haven't given much thought about how a program works or how it runs. Well, most of us know that a program is a file that is loaded into memory at some undefined point. So given the following code below, where are a, b, and c kept?

int main(void) {
    int a = 10;
    int b = 1;
    a -= 2;
    int c = 21;
    return c + (a/b);
}

A basic representation of the stack.

a, b, and c are all kept on the stack, which is a fancy word for a small memory region where temporary variables are added and removed in a special way. Everything is added and removed starting at the top, much like a stack of cards. You usually take cards off the top and sometimes you might put them on the top; these stack operations are called pop and push respectively. So we can use deductive reasoning to say that a is pushed onto the stack, followed by b and c. The great thing about allocating memory on the stack is its ease of use. The memory is allocated rather fast with minimal overhead costs. When you're done using the memory, the memory is automatically released. This means we don't need to manage the memory.

Although this is a great way to allocate memory, it was mentioned that the stack is usually small, meaning you don't want to put large variables onto the stack; mainly large arrays and large structures. If you don't want to waste your precious stack space, where and how can you allocate large amounts of memory? Luckily, there's a large memory region reserved for just that. This area is called the heap. Essentially, the heap is a very large memory pool where certain parts of it may be used or unused. Thankfully, the operating system takes care of the complex task of managing it; all we need to know is how to allocate the memory and release it. Unfortunately, if you don't release the allocated memory, it will remain allocated until you do. This could lead to a memory leak, in which you lose the location of the allocated memory and you'll never be able to release it. This could impact performance and eventually could cause your program to run out of memory, thereby crashing it. One needs to be extra cautious when working with dynamic memory allocation.

All in all, allocating memory in the heap is great for large variables, while using the stack is best suited for small variables.

Allocating Memory

Before we get started with some examples, it's important to know that all of the memory allocation functions are kept in the header file stdlib.h. The first function we'll be working with is malloc which stands for memory allocation. This function takes one parameter, the size of the allocated memory in size_t. size_t is basically the largest number used for addressing memory on a computer, so for example, on a 32-bit computer size_t would be able to express 4 GiB.

Note: The actual size of the type size_t itself would only be 4 bytes on a 32-bit computer, not 4 GiB! size_t is able to, for example, hold the address of the second GiB within its 4 bytes. Rationally, we can say that size_t is able to address any location of a computer's memory.

Now that we know how to allocate memory, let's try it.

#include <stdlib.h> /* malloc */

int main(void) {
    char *array = malloc(10);
    return 0;
}

We just made a ten byte dynamic array, but to avoid errors you should always multiply the number of variables you want by the size of the variable's data type. Take a look at the next example and notice the use of the sizeof operator.

#include <stdlib.h> /* malloc */

int main(void) {
    int *array = malloc(sizeof(int) * 10);
    return 0;
}

array is now guaranteed to hold ten int types. Using the sizeof operator allows us to keep our code portable and platform-independent, since the number of actual bytes don't concern us.

Sometimes there just isn't enough memory, meaning that malloc isn't guaranteed to return a pointer to usable memory. If it isn't able to allocate memory, it will return a null pointer, NULL. If you allocate memory, you should always check to make sure you got usable memory as shown in the following example.

#include <stdlib.h> /* malloc, NULL */
#include <stdio.h> /* fprintf, stderr */

int main(void) {
    int *array = malloc(sizeof(int) * 10);
    if (array == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for array!\n");
        return -1;
    }
    return 0;
}

Still, this code needs one final touch-up. malloc returns a void pointer, so it should be cast to the appropriate data type as shown below.

#include <stdlib.h> /* malloc, NULL */
#include <stdio.h> /* fprintf, stderr */

int main(void) {
    int *array = (int*) malloc(sizeof(int) * 10);
    if (array == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for array!\n");
        return -1;
    }
    return 0;
}

Warning: Before you start allocating memory like crazy, you need to make sure that you don't allocate "nothing". This happens when you try something like malloc(0), which won't allocate any memory for you. Worse, it might return a null pointer, but that's not guaranteed. This means that it's possible to get a pointer to memory you shouldn't touch, which will certainly aid in crashing your program.

Releasing Allocated Memory

Now that you've allocated memory, your program will keep it as long as it lives. That means allocating large chunks of memory can drain your computer's resources. At some point you're going to want to give back that memory. The free function can help us here. It deallocates the allocated memory, therefore allowing the computer to allocate more later on. Using free is simple; all it takes is one parameter, the pointer to the allocated memory. A demonstration is given below.

#include <stdlib.h> /* malloc, free, NULL */
#include <stdio.h> /* fprintf, stderr */

int main(void) {
    int *array = (int*) malloc(sizeof(int) * 10);
    if (array == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for array!\n");
        return -1;
    }

    /* I have no use for array, I better free it. */
    free(array);

    return 0;
}

Warning: Giving free a pointer that isn't allocated will cause undefined behavior. Fortunately, free won't do anything if you try to deallocate a null pointer. Never try to deallocate anything that was never allocated in the first place!

Resizing Allocated Memory

Well, it's great that we can allocate and deallocate memory, but what if we want to change the size of the allocated memory? It's possible to do this via the realloc function. This function takes two parameters, the pointer to the allocated memory and its new size. Depending on unseen variables, the realloc could change the location of the original. Luckily, it returns the new location for us.

#include <stdlib.h> /* malloc, realloc, free, NULL */
#include <stdio.h> /* fprintf, stderr */

int main(void) {
    /* Let's allocate memory for array. */
    int *array = (int*) malloc(sizeof(int) * 2);

    /* Check to make sure that we got the allocated memory. */
    if (array == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for array!\n");
        return -1;
    }

    /* Let's actually use array. */
    *array = 10;
    *(array + 1) = 20;

    /* Oh no! array doesn't have any more space, We better get more! */
    int *array = (int*) realloc(array, sizeof(int) * 4);

    /* Check to make sure that we got the allocated memory. */
    if (array == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for array!\n");
        return -1;
    }

    /* Let's use array a little more. */
    *(array + 2) = 30;
    *(array + 3) = 40;

    /* We have no more use for array, we better free it. */
    free(array);

    /* Everything went fine! */
    return 0;
}

As you probably noticed realloc returns a void pointer which we should cast into our variable's type. It should be assumed any new memory from realloc isn't set to zero. If you resize the allocated memory smaller than it was before, it will cause the end of the allocated memory to be truncated.

Warning: Whilst it is possible to free allocated memory by setting the size to zero, standard library implementations may differ. Consequently, you should always use free to deallocate memory.

Allocating Clean Memory

Using malloc to allocate our memory is great, but it still has its flaws. malloc doesn't worry about the state of the allocated memory, meaning that each byte could have an undefined value. This can be problematic with the array we've been using. When it's allocated, the array may contain undefined values. Usually, when we allocate an array we want everything to be zero. Fortunately, the last function discussed in this lesson allocates memory and guarantees that all of the memory is set to zero. This function is called calloc and it takes two parameters: the number of items that you want allocated and their size. calloc is demonstrated in the example below.

#include <stdlib.h> /* malloc, calloc, free, NULL */
#include <stdio.h> /* printf, fprintf, stderr */

int main(void) {
    /* Let's allocate memory for array. */
    int *array = (int*) calloc(5, sizeof(int));

    /* Check to make sure that we got the allocated memory. */
    if (array == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for array!\n");
        return -1;
    }

    /* Let's use some parts of array. */
    *array = 15;
    *(array + 1) = 7;
    *(array + 3) = 23;

    for (int i = 0; i < 5; i++) printf("%d: %d\n", i, *(array+i));

    /* We have no more use for array, we better free it. */
    free(array);

    /* Everything went fine! */
    return 0;
}

The output should be:

0: 15
1: 7
2: 0
3: 23
4: 0

Warning: Just like malloc, you must never allocate nothing, i.e., calloc(0).

Memory Management Problems

Unlike some newer languages, C requires you to manually allocate and deallocate memory. Thus, the task of managing your program's memory falls solely on you, the programmer. No matter how much experience you have with memory management, you'll still make mistakes when working with dynamic memory. The important thing is to realise the types of problems you may encounter and understand how to correct and prevent them. Luckily, a good number of these problems will be discussed in this section.

Memory Leaks

This is the most well known problem you'll encounter when working with memory. A memory leak occurs when you lose a pointer to allocated memory. Since you no longer know of its location, you aren't able to deallocate the memory. This leads to a chain reaction in which you won't be able to use that memory for the rest of the program's life, eventually the program could completely crash and burn. An example of such a memory leak is given below.

#include <stdlib.h> /* malloc, free, NULL */
#include <stdio.h> /*  fprintf, stderr */

int main(void) {
    /* Let's allocate memory. */
    char *mem = (char*) malloc( sizeof(char) * 20);

    /* Check to make sure that we got the allocated memory. */
    if (mem == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for mem!\n");
        return -1;
    }

    /* Let's allocate more memory. We just lost the pointer to the older memory. */
    mem = (char*) malloc( sizeof(char) * 30);

    /* Check to make sure that we got the allocated memory. */
    if (mem == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for array!\n");
        return -1;
    }

    /* We have no more use for mem, we better free it. */
    free(mem);

    /* The first allocated memory still hasn't be freed! Thankfully,
     when the program ends, it will all be deallocated by the OS. */

    /* Everything went fine! */
    return 0;
}

See how only the second allocated memory was deallocated and not the first? If a long living program slowly leaked memory, eventually it wouldn't be able to allocate any more, because the memory available for allocation to the program has diminished. This is one of the most common memory problems you'll encounter and is usually easy to correct. The best way to combat memory leaks is to make sure that you always deallocate allocated memory at the end of the pointer's scope, for example the end of a function.

Dangling Pointers

These pointers can cause a lot of problems in C. A dangling pointer is a pointer that points to a memory region that was previously deallocated. Unfortunately, having a pointer that points to a now freed memory region will surely cause problems, if used. Here is an example of a dangling pointer.

#include <stdlib.h> /* malloc, free, NULL */
#include <stdio.h> /*  puts, fprintf, stderr */

int main(void) {
    /* Let's allocate a string. */
    char *str = (char*) malloc( sizeof(char) * 4);


    /* Check to make sure that we got the allocated memory. */
    if (str == NULL) {
        fprintf(stderr, "Unable to allocate enough memory for str!\n");
        return -1;
    }

    /* Put "Hi!", in the string */
    *str = 'H';
    *(str+1) = 'i';
    *(str+2) = '!';
    *(str+3) = '\0';

    /* Print the string. */
    puts(str);

    /* We have no more use for str, we better free it. */
    free(str);

    /* Trying to print the string again will cause undefined behavior! */
    puts(str);

    /* Everything went fine! Note: The program will likely crash before
       this return actually sends that signal back to whatever executed it. */
    return 0;
}

The best way to fight dangling pointer is to:

1. Just don't use them! This is easier said than done, especially in large applications.
2. Set the dangling pointer to NULL. By comparing against NULL, you now know if the pointer's good for use.

Don't forget that these steps must be done on every pointer to any recently freed memory region.

Unavailable Memory

Another common mistake addressed earlier is the assumption that malloc will always returns a pointer to valid memory, like in this example.

#include <stdlib.h> /* malloc, free */

int main(void) {
    /* Let's allocate some memory. */
    char *array = (char*) malloc( sizeof(char) * 120000);

    /* Note the lack of code that checks to see
       if this is a valid pointer.*/

    /* We have no more use for the array, we better free it.
       Hopefully it's allocate memory.*/
    free(array);

    /* Everything went fine, I hope. */
    return 0;
}

You should learn from this example and always check to see if you've received NULL. Assuming that the newly allocated memory is valid will lead to a crash. If you feel it's too time consuming to type up such safety, try using a macro to shorten the amount of code needed. This can save time and money, while reducing the amount of redundancy in your code.

External Fragmentation

An example of external fragmentation.

This problem is really unfair to programmers, even if they did everything right. External fragmentation happens when allocated memory within other allocated memory is deallocated. Only something of that exact size or smaller will be able to fit into the newly deallocated memory region. This can cause a program to run out of memory even if there's lots available. An example is shown on the right.

It's up to allocator to be able to avoid this kind of problem. Sometimes, custom memory managers are used to avoid problems like this, though this problem is really just out of your hands.

Other Problems

Other problems of less importance still exist. It's important to be wary of creating dangling global pointers and elsewhere. Generally, many other problems depend on your memory manager and how well it works. All in all, memory management problems won't likely hinder any part of this course.