Memory management in software

What is memory management? #

As a computer program runs and creates data, it needs to store that data in memory. The program will request the operating system to allocate some size of memory. The OS will then return an address in memory and the program can write its data to that location.

When the program is done using that data, it no longer needs to use that memory. It then requests the OS to deallocate that memory.

That’s all memory management is at the basic level.

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

int main() {
    uint8_t *pointerToAByte = malloc(sizeof(uint8_t));
    *pointerToAByte = 5;
    printf("%d\n", *pointerToAByte);

    free(pointerToAByte);

    return 0;
}

Pitfalls with memory management #

Managing memory seems deceptively simple, but it’s easy to run into problems, such as with memory safety.

Memory leaks #

This is when a program allocates memory and never frees it. While the program is running, it performs operations that request more and more memory. Suppose the program never frees that memory.

At a certain threshold limit, the OS will kill the process. If the program was doing critical work, then this is a major problem!

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

char* createMessage(const char* name) {
    char* message = malloc(strlen(name) + 8);
    sprintf(message, "Hello, %s!", name);
    return message;
}

int main() {
    char* msg = createMessage("elephant");
    printf("%s\n", msg);

    return 0;
}

Use after free #

This is when a program attempts to reference memory that has already been deallocated.

At the very least, this could cause incorrect behavior, maybe the program will operate on invalid data.

At worst, the program could modify memory that’s being used for different data or by a different application. If the memory was re-allocated, then use-after-free leads to data corruption. If the memory was unmapped or becomes forbidden to use, then this can cause a segmentation fault¹.

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

int main() {
  uint8_t *pointerToAByte = malloc(sizeof(uint8_t));
  *pointerToAByte = 10;

  printf("Value before free: %d\n", *pointerToAByte);

  free(pointerToAByte);

  uint8_t someNumber = 7;

  // Indeterminate behavior! It's not clear what will be printed.
  printf("Value after free: %d\n", *pointerToAByte + someNumber);

  return 0;
}

Buffer overflow #

This occurs when a program writes more data than it has allocated space for. The program might actually be able to write, but it’s uncertain behavior. It could run out of space in memory, could corrupt data used by other processes, or might induce a segfault.

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

void writeToBuffer(const char *input) {
    struct {
        int canary1;
        char buffer[5];
        int canary2;
    } data;

    strcpy(data.buffer, input);

    printf("Buffer contains: %s\n", data.buffer);
}

int main() {
    const char *normalInput = "Hi!";
    writeToBuffer(normalInput);

    const char *longInput = "This string is definitely too long";
    writeToBuffer(longInput);

    return 0;
}

Double free #

A double free is exactly like it sounds: a program attempts to free memory that it has already deallocated. This leads to undefined behavior or the program could just crash.

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

void cleanup_data(int* data) {
    free(data);
}

void handle_error(int* data) {
    // Assume there is some error handling here
    // ...

    cleanup_data(data);
}

int process_data(int* data) {
    if (*data < 0) {
        handle_error(data);
    }

    cleanup_data(data);
    return 0;
}

int main() {
    int* data = malloc(sizeof(int));
    *data = -5;

    process_data(data);

    return 0;
}

Automatic memory management #

Since managing memory is fraught with problems, automatic memory management techniques were introduced.

The main approaches are Garbage Collection and Reference Counting.

Garbage collection #

Many programming language runtimes, in addition to executing code, also run a garbage collector (GC) in the background. The GC traces what objects can be reached and through what chains of references. It tries to clean up any objects that are not reachable.

Java, JavaScript, Python, Golang, C# all have garbage collectors.

Here are some of the common techniques, some languages may use a combination of techniques:

Mark-and-sweep: the “mark” step traces the reference chains and indicates which objects are reachable. The “sweep” step looks through the heap and reclaims memory from unmarked objects.

Generational: the GC divides the heap by the age of objects (old vs. new). Objects in the “new” space are collected first and more frequently than objects in the “old” space. Any object collected in the “new” space is moved to the “old” space.

Mark-and-compact: the “mark” steps is the same as mark-and-sweep. Instead of the “sweep” step, the GC moves live objects to one side of the heap. This reduces fragmentation.

Automatic reference counting #

Some programming languages can add code at compile time that help track the number of references to objects as the program is executed.

If a new reference is created, the counter is incremented, and if a reference is removed, the counter is decremented. When the counter reaches zero, the object is deallocated.

Currently, only Objective-C and Swift use automatic reference counting.