Dynamic memory · about 45 min

malloc and free

Why this matters

Real programs rarely know their sizes in advance. A text editor does not know how long the file will be, a server does not know how many clients will connect, and a program reading numbers does not know how many will arrive. malloc and free are how C gets memory of any size, at run time, that lives as long as you need it. They are also the source of the most famous C bugs, so this lesson is precise about the rules.

The functions

Both are declared in <stdlib.h>:

void *malloc(size_t size);
void free(void *ptr);

malloc(size) reserves a block of at least size bytes on the heap and returns the address of its first byte. The contents are not initialized: they are whatever was there before. If the allocator cannot satisfy the request, it returns NULL.
free(ptr) gives a block back. ptr must be exactly a value returned by malloc (or calloc/realloc) that has not already been freed. free(NULL) is allowed and does nothing.

Two types appear here that deserve a word:

size_t is the unsigned integer type used for sizes and counts of bytes. It is what sizeof produces, 8 bytes on 64-bit Linux, and printed with %zu.
void * is a "pointer to anything": an address with no type attached. You cannot dereference it directly, but in C it converts automatically to any other object pointer type on assignment. So int *p = malloc(...) needs no cast. (C++ requires a cast; C does not, and adding one can hide a missing #include <stdlib.h> in old compilers, so C style is to leave it out.)

A complete example

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

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) {
        printf("need a positive count\n");
        return 1;
    }

    int *values = malloc(n * sizeof *values);
    if (values == NULL) {
        printf("out of memory\n");
        return 1;
    }

    for (int i = 0; i < n; i++)
        values[i] = i * 10;

    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += values[i];
    printf("%d values, sum %d\n", n, sum);

    free(values);
    return 0;
}

$ echo 4 | ./prog
4 values, sum 60

Walking through the important lines:

malloc(n * sizeof *values) asks for n elements times the size of one element. sizeof *values means "the size of the thing values points to", here sizeof(int), 4. It does not evaluate *values (which would be invalid before the assignment); sizeof only looks at the type. The idiom keeps working if you change int to long later.
The NULL check comes immediately. On Linux small allocations practically never fail, but large ones can, and writing through a null pointer crashes. Checking is a habit worth having from day one.
values[i] works exactly as with an array, because array indexing is pointer arithmetic: the heap block is a contiguous run of n ints.
free(values) returns the block. After this line, values still holds the old address, but the memory no longer belongs to you.

What happens in memory:

  stack (main's frame)              heap
  +----------------------+         +----+----+----+----+
  | n      = 4           |         |  0 | 10 | 20 | 30 |   16 bytes from malloc
  | values = 0x5a1c2a0 --+-------> +----+----+----+----+
  | sum    = 60          |
  +----------------------+

  after free(values):
  +----------------------+         +-------------------+
  | values = 0x5a1c2a0 --+-------> | (allocator's now) |   dangling pointer
  +----------------------+         +-------------------+

The pointer variable lives on the stack; the block it points to lives on the heap. Freeing the block does not touch the pointer, which becomes dangling. A common defensive habit is to set it to NULL right after freeing (free(values); values = NULL;), so that a mistaken later use crashes clearly instead of silently corrupting memory, and a second free becomes harmless.

How the allocator works, roughly

The allocator (glibc's malloc on Linux) keeps the heap as a collection of chunks. Each chunk has a small header just before the address you get, recording its size and whether it is in use. malloc searches its free lists for a chunk big enough (splitting a larger one if needed); free reads the header to learn the size and puts the chunk back on a free list, merging it with free neighbors. When it runs out, it asks the kernel for more address space.

   [hdr|  your 16 bytes  ][hdr|  someone else's 32 bytes  ][hdr| free ...
        ^
        pointer malloc returned

That is why free takes only a pointer: the size is in the header. It is also why heap bugs are so damaging: writing past the end of your block overwrites the next chunk's header, and the allocator may only notice much later, inside some unrelated malloc or free call, with a message such as malloc(): corrupted top size followed by Aborted.

Returning heap memory from a function

The heap solves the problem from the previous lesson: a function can create data that outlives its frame.

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

/* Returns a new array of n squares. The caller must free it. */
int *make_squares(int n)
{
    int *sq = malloc(n * sizeof *sq);
    if (sq == NULL)
        return NULL;
    for (int i = 0; i < n; i++)
        sq[i] = i * i;
    return sq;
}

int main(void)
{
    int *s = make_squares(5);
    if (s == NULL)
        return 1;
    for (int i = 0; i < 5; i++)
        printf("%d ", s[i]);
    printf("\n");
    free(s);
    return 0;
}

0 1 4 9 16

The comment "The caller must free it" is part of the function's contract. C has no way to express ownership in the type system, so documentation and naming conventions carry it. You will see this pattern everywhere: the standard strdup function, for example, returns a malloced copy of a string that you must free.

Checking your work with valgrind

valgrind runs your program on a simulated CPU and watches every memory access and every allocation. At exit it reports what was never freed:

$ echo 4 | valgrind ./prog
==10== Memcheck, a memory error detector
==10== Command: ./prog
==10==
4 values, sum 60
==10==
==10== HEAP SUMMARY:
==10==     in use at exit: 0 bytes in 0 blocks
==10==   total heap usage: 3 allocs, 3 frees, 8,208 bytes allocated
==10==
==10== All heap blocks were freed -- no leaks are possible
==10==
==10== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

The number between == is the process id and varies. "3 allocs" when you only called malloc once? The C library allocated buffers for stdin and stdout on your behalf (and freed them at exit). Lesson 4 of this module covers valgrind's error reports in detail; the exercises already use it to check your code.

Common mistakes

Forgetting sizeof: malloc(n) gives n bytes, not n ints. Writing n ints into it overflows the block. valgrind reports Invalid write of size 4.
Forgetting the terminator for strings: a copy of a 5-character string needs 6 bytes.
Using memory after free. It may appear to work. It is undefined behavior.

Freeing twice. glibc often detects it and aborts:

free(): double free detected in tcache 2
Aborted (core dumped)

Freeing something that did not come from malloc, such as a local array or a pointer into the middle of a block: free(): invalid pointer, then abort.
Assuming new memory is zeroed. It is not; use calloc (next lesson) or initialize it.
Losing the pointer (p = malloc(...); p = malloc(...);). The first block can never be freed: a leak.

Recap

malloc(bytes) returns uninitialized heap memory or NULL; always check.
Size requests are in bytes: malloc(n * sizeof *p).
void * converts to any object pointer without a cast in C.
free(p) releases exactly what malloc returned, once. free(NULL) is a no-op. Afterwards p dangles; set it to NULL if it stays in scope.
Functions may return heap memory; document that the caller must free it.

Going further: the malloc(3) manual page lists the whole family, including malloc_usable_size (the sandbox does not include the C library manual pages; read it with man 3 malloc on a system with the manpages-dev package, or at man7.org). Try valgrind ./prog on a program that forgets its free and read the "definitely lost" line.

Exercises

Exercise 1 · quiz

Asking for the right number of bytes

You need room for n values of type double, stored through double *d. Which allocations are correct? Select all that apply.

d = malloc(n);
d = malloc(n * sizeof(double));
d = malloc(n * sizeof *d);
d = malloc(sizeof(d) * n);

Answer

d = malloc(n * sizeof(double));
d = malloc(n * sizeof *d);

malloc counts bytes, not elements, so the count has to be multiplied by the size of one element. sizeof *d is the size of what d points to (a double, 8 bytes), and it stays correct if you later change d's type, which is why many C programmers prefer it. sizeof(d) is the size of the pointer itself, which happens to be 8 on x86-64 as well, so that line works by accident and breaks as soon as the element type is not 8 bytes. malloc(n) gives only n bytes: room for n/8 doubles.

Exercise 2 · write code

Reverse a list of any length

Read a count n from standard input, then n integers. Store them in an array allocated with malloc (you do not know n until the program runs), then print them in reverse order on one line, separated by single spaces, followed by a newline.

If the count is missing, not a number, or not positive, print bad count and exit with status 1.
If malloc returns NULL, print out of memory and exit with status 1.
Free the array before returning. The check runs your program under valgrind and fails if any memory leaks or any invalid read or write happens.

Example: input 5 then 1 2 3 4 5 prints 5 4 3 2 1.

File: main.c

Starting point

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

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) {
        printf("bad count\n");
        return 1;
    }

    /* allocate room for n ints, check for NULL */

    /* read n ints into the array */

    /* print them in reverse, then free the array */

    return 0;
}

Example

input

5
1 2 3 4 5

expected output

5 4 3 2 1

Example

input

1
42

expected output

Hint 1

int *values = malloc(n * sizeof *values); then if (values == NULL) { ... }.

Hint 2

Read with scanf("%d", &values[i]) in a loop from 0 to n-1, print with a loop from n-1 down to 0.

Hint 3

Print the first number without a leading space and the others with " %d", then a final newline, then free(values);.

Reference solution

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

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) {
        printf("bad count\n");
        return 1;
    }

    int *values = malloc(n * sizeof *values);
    if (values == NULL) {
        printf("out of memory\n");
        return 1;
    }

    for (int i = 0; i < n; i++) {
        if (scanf("%d", &values[i]) != 1)
            values[i] = 0;
    }

    for (int i = n - 1; i >= 0; i--)
        printf(i == n - 1 ? "%d" : " %d", values[i]);
    printf("\n");

    free(values);
    return 0;
}

Exercise 3 · write code

Return a new string from a function

Write a function

char *repeat(const char *s, int times);

that returns a newly allocated string containing s repeated times times, for example repeat("ab", 3) returns "ababab" and repeat("x", 0) returns "" (an empty string, still allocated). The caller owns the result and frees it. Return NULL if malloc fails.

Remember the null terminator when computing the size. main is up to you (the starter has a small demo that should print ababab); the check calls repeat directly from a test program and runs it under valgrind, which will catch writing one byte past the end of your allocation.

File: main.c

Starting point

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

char *repeat(const char *s, int times)
{
    /* allocate strlen(s) * times + 1 bytes, fill it, terminate it */
    return NULL;
}

int main(void)
{
    char *r = repeat("ab", 3);
    if (r != NULL) {
        printf("%s\n", r);
        free(r);
    }
    return 0;
}

Example

expected output

ababab

Hint 1

The result needs strlen(s) * times characters plus one byte for the '\0'.

Hint 2

Copy s into position i * len for each i, with memcpy or a loop over the characters.

Hint 3

Do not forget out[len * times] = '\0'; before returning.

Reference solution

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

char *repeat(const char *s, int times)
{
    size_t len = strlen(s);
    char *out = malloc(len * times + 1);
    if (out == NULL)
        return NULL;
    for (int i = 0; i < times; i++)
        memcpy(out + i * len, s, len);
    out[len * times] = '\0';
    return out;
}

int main(void)
{
    char *r = repeat("ab", 3);
    if (r != NULL) {
        printf("%s\n", r);
        free(r);
    }
    return 0;
}