Why Dynamic Memory: Sizes You Do Not Know Yet

Amara's marks report from the Module 9 project kept the class in int marks[MAX_S][MAX_M], with MAX_S set to 100. A sheet for 101 students got two words back: invalid size.

This term the office will not say how many students there are. The first line of the sheet will say, and it may say 12 or 3,000.

An array's size is fixed before the program is compiled, and this number arrives with the input. This lesson asks for the boxes once the number is known.

Three answers to a size you do not know yet

The first two answers are Module 9's, and the third is this module's.

The constant is honest about its limit, and the limit is the problem. The day a school merges two classes, the program refuses real data.

The huge static array costs less than it looks. Module 9 lesson 3 measured a 280 MB static array on the Playground, and it passed using 416 KB. The operating system hands out memory in pages of 4,096 bytes, and counts a page only when the program first touches it. So the real cost is the ceiling that remains, and a program that says "a million" where it means "however many".

malloc asks for exactly n boxes after n is read, with no ceiling in the code. The price is two new duties: check what came back, and give it back when you are done.

So a constant and a static array both fix the ceiling when the program is compiled, and malloc sets the size while it runs.

The heap: the box Module 11 drew dashed

Module 7 lesson 5 promised a third area of memory, and Module 11 lesson 1 drew it as a dashed box marked Module 14. It is the heap: a region of memory a program asks for, piece by piece, while it runs.

Asking is called allocating, and one piece is a block: bytes side by side, like an array with no name. Memory handled this way is dynamic memory, because its size and its lifetime are decided while the program runs.

You reach a block through a pointer that holds its address, and that pointer is an ordinary local. In the picture, marks sits in main's frame on the stack, and the five boxes it points at sit in the heap.

The heap grows upward as the program asks for more, and the stack grows downward (Module 8 lesson 2). Lesson 6 shows how the C library makes the heap bigger.

A local dies at its function's closing brace. A block stays until the program calls free on it, so a function can allocate a block and return its address. Example 2 does exactly that.

So the pointer is a local on the stack, and the boxes it points at live in the heap until you free them.

malloc, read aloud part by part

malloc (short for "memory allocate") comes from <stdlib.h>. It takes a number of bytes and returns the address of the first byte of a fresh block. When it cannot give the block, it returns NULL.

int *marks = malloc(n * sizeof *marks);

Why not sizeof(int)? Both give 4 here. If marks later becomes a long long *, sizeof *marks follows it to 8. sizeof(int) stays 4, and the block comes out half size. Parentheses are needed only around a type name.

Here is the whole idiom in Amara's program, which prints the first and the last mark.

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

int main(void)
{
    int n = 0;
    int *marks = NULL;

    if (scanf("%d", &n) != 1 || n < 1) {
        printf("no marks\n");
        return 0;
    }
    marks = malloc(n * sizeof *marks);
    if (marks == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &marks[i]);
    }
    printf("students: %d\n", n);
    printf("first mark: %d, last mark: %d\n", marks[0], marks[n - 1]);
    free(marks);
    return 0;
}

students: 5
first mark: 90, last mark: 51

That output is for the input 5, then 90 72 64 88 51. With n = 5 the call asks for 5 × 4 = 20 bytes. No message at any command line: the Playground, -Wall and -Wall -Wextra all stay silent.

So malloc(n * sizeof *marks) reads aloud as "n boxes, each the size of the box marks points at".

Check the answer: NULL, and what fails on the Playground

When malloc cannot give the block, it returns NULL, the pointer to nothing (Module 11 lesson 2). Writing through NULL is undefined behaviour, so this track checks every allocation on the very next line. In main, the check prints out of memory on stderr and returns 1.

How often does that happen? Less often than you might think. Measured on the live Playground, whose memory limit is 256,000 KB:

So malloc hands out address space, not memory. The limit counts only the pages a program touches, the rule that let Module 9's static array pass. A request far past the limit still gets a pointer, and the run ends when the program writes into too much. NULL came back only for a request the machine refused outright. That line moves with the machine: on Compiler Explorer, 12 GB got a pointer and 16 GB got NULL.

Then why check? Because some requests do fail, and one is easy to make by accident. Zara tries odd inputs first, so she feeds this program -1.

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

int main(void)
{
    int n = 0;
    int *marks = NULL;

    if (scanf("%d", &n) != 1) {
        return 1;
    }
    marks = malloc(n * sizeof *marks);
    if (marks == NULL) {
        printf("malloc returned NULL for n = %d\n", n);
        return 1;
    }
    printf("got a block for n = %d\n", n);
    free(marks);
    return 0;
}

No message at any command line. Measured on the live Playground, the run printed malloc returned NULL for n = -1, and return 1; showed Runtime error with Exit: 1. sizeof gives an unsigned size_t, so the -1 wraps around to the largest size_t. Times 4, that is 18,446,744,073,709,551,612 bytes.

With the -1 written into the program instead, GCC 12 sees the size while compiling. The Playground shows it in the amber Compile output tab: warning: argument 1 value '18446744073709551612' exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]. Read from the input, the mistake is silent, so the program must check n itself.

That is why Amara's program above tests n < 1 first: for -1 or 0 it prints no marks and never calls malloc. The NULL check stays too, for a machine with less room and a program that keeps asking for months. A program that assumes malloc never fails has not met Zara yet.

So check n before you allocate, and check the pointer after.

Use the block like an array, then free it

Once the check passes, the block is used exactly like an array. marks[i] means *(marks + i) (Module 11 lesson 3): start at the block's address, step i boxes, and use the box there. Indexes run from 0 to n - 1, as in every array, and nothing checks them for you.

When you are done, free(marks) gives the block back to the allocator, the part of the C library that hands out blocks. After that, marks is a dangling pointer (Module 11 lesson 7): it holds an address, but the block is no longer yours. Lesson 2 adds marks = NULL; for a pointer that stays in use; right before return, free alone is enough.

A block that nothing points at any more, and that was never freed, is a leak. A leak changes no output. When a program ends, the operating system takes back every page it had. So on the Playground, a missing free costs nothing you can see.

The habit still matters, because not every program ends. A web server runs for months and allocates for every request. If each request leaks a block, its memory grows until the machine refuses it; lesson 5 measures one such leak. So this track frees every block on every path, the early returns included.

So index the block like an array, and free it on every path out of the program.

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

int main(void)
{
    int *scores = malloc(3 * sizeof *scores);

    if (scores == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    scores[0] = 70;
    scores[1] = 85;
    scores[2] = 91;
    printf("Kenji's scores: %d %d %d\n", scores[0], scores[1], scores[2]);
    free(scores);
    return 0;
}

Kenji's scores: 70 85 91

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

#define PASS_MARK 40

int *read_marks(int n);
int count_passed(const int *marks, int n);

int main(void)
{
    int n = 0;
    int *marks = NULL;

    if (scanf("%d", &n) != 1 || n < 1) {
        printf("no marks\n");
        return 0;
    }
    marks = read_marks(n);
    if (marks == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    printf("passed: %d of %d\n", count_passed(marks, n), n);
    for (int i = 0; i < n; i++) {
        if (marks[i] < PASS_MARK) {
            printf("needs help: student %d with %d\n", i + 1, marks[i]);
        }
    }
    free(marks);
    return 0;
}

int *read_marks(int n)
{
    int *marks = malloc(n * sizeof *marks);

    if (marks == NULL) {
        return NULL;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &marks[i]);
    }
    return marks;
}

int count_passed(const int *marks, int n)
{
    int passed = 0;

    for (int i = 0; i < n; i++) {
        if (marks[i] >= PASS_MARK) {
            passed = passed + 1;
        }
    }
    return passed;
}

passed: 4 of 6
needs help: student 2 with 35
needs help: student 6 with 22

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

int main(void)
{
    int n = 0;
    int *prices = NULL;
    int total = 0;

    if (scanf("%d", &n) != 1 || n < 1) {
        printf("empty receipt\n");
        return 0;
    }
    prices = malloc(n * sizeof *prices);
    if (prices == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &prices[i]);
        total = total + prices[i];
    }
    printf("receipt: %d items, total %d\n", n, total);
    for (int i = 0; i < n; i++) {
        printf("  item %d: %d\n", i + 1, prices[i]);
    }
    free(prices);
    return 0;
}

receipt: 3 items, total 285
  item 1: 65
  item 2: 180
  item 3: 40

#include <stdio.h>

int main(void)
{
    int n = 5;
    int *marks = malloc(n * sizeof *marks);

marks = malloc(n);
if (marks == NULL) {
    fprintf(stderr, "out of memory\n");
    return 1;
}

for (int i = 0; i <= n; i++) {
    total = total + prices[i];
}

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

int main(void)
{
    int *marks = malloc(0);

    if (marks == NULL) {
        printf("malloc(0) gave NULL\n");
    } else {
        printf("malloc(0) gave a pointer\n");
    }
    free(marks);
    return 0;
}

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

int *read_marks(int n);
void print_report(const int *marks, int n);

int main(void)
{
    int n = 0;
    int *marks = NULL;

    scanf("%d", &n);
    marks = read_marks(n);
    if (n > 0 && marks == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    print_report(marks, n);
    free(marks);
    return 0;
}

int *read_marks(int n)
{
    /* Ask malloc for exactly n boxes, check the answer for NULL,
       read n marks into the boxes and return the block. */
    return NULL;
}

void print_report(const int *marks, int n)
{
    /* Print "mean: X.XX" and "max: M" on two lines, or "no marks" when n is 0. */
}

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

long long *make_squares(int n);

int main(void)
{
    int n = 0;
    long long *squares = NULL;
    long long sum = 0;

    scanf("%d", &n);
    squares = make_squares(n);
    if (n > 0 && squares == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }
    /* Print box 0 to box n - 1, one per line, and add each one to sum. */
    printf("sum: %lld\n", sum);
    free(squares);
    return 0;
}

long long *make_squares(int n)
{
    /* For n = 0, allocate nothing and return NULL. Otherwise ask malloc
       for exactly n boxes, check for NULL, and put (i + 1) squared in box i. */
    return NULL;
}

Next, Bob grows a block and loses it on the one run where realloc says no. Lesson 2 opens the four calls, malloc, calloc, realloc and free, and measures what each one promises.