Arrays and dynamic memory recap

Chapter 3 gave every object a lifetime you did not choose, since a call pushed the frame that held it and a return popped it. This chapter put many objects under one name and then handed that decision back to you. One picture explains all five lessons, and it is a run of same-typed objects sitting back to back with nothing between them. That run has two homes, a frame that ends at a closing brace or a heap block that ends when you say so, and it behaves identically in both, which is why lesson 2's rules carried into lesson 3 without a word of amendment. Because the run carries no length of its own, everything you do with it travels as a pair, a pointer to the first element and a count beside it, and that pair is the spine of the chapter. Miss the count by one and chapter 2's fencepost stops being an extra loop pass and becomes memory that was never yours. Lose the last pointer and the block becomes memory nobody can give back. Let's review each lesson before you test yourself.

Arrays: Contiguous Memory

An array is a fixed number of objects of one type laid out one after another under a single name, so int scores[5]; reserves five ints and the number in brackets is the element count, a literal the compiler reads while compiling. The brackets then do a second, different job in an expression, where [2] is an index rather than a count, and C counts from 0 because an index is a distance from the start: scores[0] is the element zero places along, the valid subscripts are 0 through 4, and there is no scores[5]. An initializer list in braces starts the array off, and its rule pays for itself at once, because a list shorter than the array zero-initializes every remaining element, which is what makes int counts[5] = {0}; the idiom that zeroes an array of any size in one line that cannot get its bounds wrong. Leave the initializer off and chapter 1's rule applies element by element, since an automatic array holds indeterminate values and reading one before writing it is undefined behaviour. "One after another" is a claim you checked with %p, and the addresses rose by exactly 4 on an array of int, but only half of what you saw was promised. Contiguity is a language guarantee, so &scores[i + 1] is always sizeof(scores[0]) bytes past &scores[i] with no gaps between them, while where the array sits is not promised at all and address space layout randomization moves it on every run. That guarantee is what lets sizeof(scores) / sizeof(scores[0]) report the element count, and it answers the question at compile time from the declaration, because at run time an array carries no length, no bounds and no marker saying where the filled part stops. How many elements you have actually filled is therefore a fact only you know, and the only place to keep it is a variable of your own: guard the fill with count < 5 && scanf("%d", &value) == 1 so that short-circuit evaluation stops before the array overflows, then bound every later loop with i < count rather than with the declared size. Get that one character wrong and for (int i = 0; i <= 5; ++i) assigns to scores[5], and indexing outside an array is undefined behaviour, for reads as much as for writes. gcc caught that particular one as array subscript 5 is above array bounds [-Warray-bounds=] only because the bound was a constant it could reason about, which makes the diagnostic luck rather than protection; AddressSanitizer caught it as stack-buffer-overflow and named scores inside the frame.

Pointer Arithmetic and Array Decay

Chapter 3 said a pointer's type is what makes a dereference mean anything, and here that type takes on a second job. p + i is i * sizeof(*p) bytes past p, so one step means one element and never one byte: the identical + 1 moved 4 bytes on an int * and 8 on a double * with nothing in the source naming either number. The arithmetic means something only inside an array, and it means something there precisely because lesson 1 guaranteed the elements sit back to back. Out of that falls the identity tying the chapter's two halves together, since a[i] is defined as *(a + i), so indexing is pointer arithmetic in friendlier spelling, which is why a pointer can be indexed and an array name can be added to. An array name can be added to because in almost every expression an array name decays to a pointer to its first element. "Almost" has exactly three exceptions worth knowing by name: sizeof arr, which is the entire reason lesson 1's count idiom worked; &arr, which produces the address of the whole array; and a string literal initializing an array, which belongs to chapter 5. Decay is not a curiosity, because it is what happens at every call. Passing an array passes a pointer, so void f(int *a), void f(int a[]) and void f(int a[10]) all declare the same function, a parameter cannot have array type in C, and a bound written in those brackets is documentation that nothing at run time enforces. The length has to travel as a parameter of its own, which makes void print_values(const int *values, int count) the shape every array function in this course uses, with const being chapter 3's read-only promise applied to arrays. Then comes the trap that catches nearly every C programmer exactly once. Inside such a function sizeof(values) / sizeof(values[0]) divides the size of a pointer by the size of an element, and it does not fail, it lies, reporting 2 for an array of 5 while main reports 5 from the identical expression. -Wsizeof-pointer-div may recognise the shape, but assigning the two sizes to variables and dividing those hides the warning without changing the answer, so the rule that survives the compiler not noticing is to pass the length every time. Last, for (const int *p = values; p < values + count; ++p) visits the same objects as the indexed loop, and it is correct because C explicitly permits forming the one-past-the-end address so that loops may use it as a limit. Form it and compare against it; dereferencing it is out of bounds by lesson 1's rule, and the sanitizer reports that read.

The Heap: malloc and free

Every array so far had its size settled before the program started, and a program does not meet its data until it runs. The heap is the region chapter 1 labelled as memory you ask for by hand, and malloc from <stdlib.h> is the asking: you name a number of bytes and you get back a pointer to that many consecutive uninitialized bytes, or NULL because it could not find them. Three habits around that call carry the whole contract. Size the request from the object, as malloc(count * sizeof *values), because sizeof measures its operand's type without evaluating anything and this form names the type only once, in the declaration, where count * sizeof(int) goes on quietly asking for 4 bytes an element the day you change the pointer to long *. Do not cast the result, since void * converts implicitly in C and a cast merely puts the type in a second place that has to be kept in step (C++ is the opposite language here and requires it). And check every allocation against NULL with a branch that does something deliberate, because an unchecked failure turns the first values[i] into chapter 3's SEGV on unknown address 0x000000000000 on the day the machine is short of memory rather than the day you tested. What comes back is not a new kind of thing: the bytes are contiguous, so values[i] is still *(values + i), values + count is still the address you may form and must not dereference, and a function taking a pointer and a count accepts the block without ever learning where it came from. Only two facts are new. The block arrives uninitialized, so reading an element before writing it is undefined behaviour, and this is the one memory mistake in the chapter that AddressSanitizer does not catch, printing a fill pattern such as -1094795586 and running happily on; calloc(count, size) zeroes for you when zero is genuinely the value you want. And nothing in the program decides when the block ends. Every allocation gets exactly one free, at a moment you choose, with no closing brace and no popped frame to choose it for you, which is exactly the lifetime chapter 3 promised, and free(NULL) is a defined no-op. Because the block has no frame to die with, a function may return a pointer to memory it allocated, which the dangling &answer never could. Touch the block after the free and you get heap-use-after-free; free it twice and you get attempting double-free; both are undefined behaviour, and the danger in the first is that the bytes usually still hold the old value, so a wrong program prints the right answer. Writing values = NULL; after the free disarms that one pointer and no copy of it.

Ownership and Leaks

Ownership is the name for the obligation that comes back alongside the pointer: at every moment, for every live block, exactly one piece of code is responsible for the free, not zero pieces and not two. C checks none of it. There is no annotation to write and nothing in the type system separating an int * you must free from an int * you must leave alone, so ownership lives in conventions, in function names and in what you wrote down, and a chapter that opened on array indexing closes on a habit because on the heap the habit is the only thing there is. Every heap bug here is that one rule broken in one of three directions. Free a block twice and it had two owners, each believing the duty was its own. Use a block after freeing it and you touched memory you no longer owned. Both of those are undefined behaviour, which is why the sanitizer ends the run on the spot. The third direction differs in kind: a leak is a live block with no owner left, its last pointer overwritten, gone out of scope, or never handed to anybody, so the matching free can never be written by anyone. Hold this distinction precisely, because a leak is not undefined behaviour. A leaking program is well-defined C, every statement means what the standard says it means, its output is trustworthy, and it has simply lost memory permanently. That is a real cost and in a server a fatal one, but it is a cost of the ordinary kind that you can reason about, which undefined behaviour never is. The timing makes the difference visible: the leaking program ran to completion and exited 0, printed exactly the message it meant to print, and only afterwards did LeakSanitizer write Direct leak of 12 byte(s) in 1 object(s) to standard error, with a stack naming the allocation rather than any leak site, because there is no line where a leak happens. Watch the object count, since one object leaked once is a bug while a thousand from one line is a loop with no free in it, and note that this platform fails an exercise with fail_on_memory_leak on that report despite the zero exit status. Three shapes cover most leaks: overwriting the only pointer, an early return that skips the free the happy path performs, and allocating in a loop with the free outside it. Ask at every return and every assignment what you own right now. Across a function boundary the obligation either travels with the pointer or it does not, and nothing in the code says which, so the convention has to be loud: returning a heap pointer transfers ownership to the caller, which the make_ prefix and a comment should announce, while a const int * parameter borrows the block for the length of the call and the caller still frees it afterwards. When one function holds two blocks and has three ways out, jump forward to a single cleanup label that frees in reverse order and returns, with both pointers initialized to NULL at the top so the label is safe from every exit. Forward only, one label, never into a block: that is goto's one legitimate job, and outside those rules it is exactly as bad as its reputation.

Reading AddressSanitizer Reports

The reports this course had been handing you turned out to be a form with fixed fields rather than a wall of hexadecimal, and reading one is four lookups. The kind sits on the ERROR line and narrows the search before you read anything else, so heap-buffer-overflow says a malloc block was touched outside itself where stack-buffer-overflow says the same of an automatic array and can name the offending variable inside the frame, which the heap version cannot do. The operation is the READ or WRITE of size N line, and 4 is one int. The location is the first stack trace, read with one rule: start at #0 and go down to the first frame naming a file you wrote, which is often not #0, since in an allocation stack #0 is malloc inside the sanitizer's own library and your line is #1. Then the line beginners skip, which is the one that solves the case. is located 0 bytes after 16-byte region states the relationship between the address you touched and a block the sanitizer knows about, and both of its numbers divide: a 16-byte region of int is four elements, so the first byte past it is index 4 and the loop said i <= count where it meant i < count, while 8 bytes after would be two elements past, at index 6. Change that one field and the case changes completely, because in the second program the region was 4 bytes, and four bytes is a single int when the loop wanted four of them, so the index was right and the allocation was wrong, malloc(count) having asked for bytes where it meant elements. That is the habit worth keeping, that the failing line is not always the wrong line, which is exactly why allocated by and freed by are printed at all. The workflow is fixed: kind, failing line, the memory's story, hypothesis, fix, and re-run until clean, since the sanitizer stops at the first error it meets and has nothing to say about anything after it. One structural fact decides how you read the output, which is that a memory access error aborts the run at the offending instruction so output the program had not yet printed never arrives, while a leak is reported only after a complete and successful run. And here is the conclusion the chapter refuses to let you draw: a clean run never proves the absence of undefined behaviour. Signed integer overflow, shifting by the width of a type, dividing by zero and reading uninitialized memory all pass through undetected, as does every plain logic error, so the sanitizer is one check standing beside compiler warnings and the discipline of writing defined code. Here is the chapter in one program.

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

int sum_values(const int *values, int count)
{
    int total = 0;

    for (int i = 0; i < count; ++i)
    {
        total += values[i];
    }

    return total;
}

int main(void)
{
    int count = 0;

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

    int *values = malloc(count * sizeof *values);

    if (values == NULL)
    {
        printf("could not allocate\n");
        return 0;
    }

    for (int i = 0; i < count; ++i)
    {
        values[i] = (i + 1) * 10;
    }

    printf("last is %d and the total is %d\n", values[count - 1], sum_values(values, count));
    free(values);
    return 0;
}

Given 4 on standard input that prints last is 40 and the total is 100, with nothing at all on standard error. Every rule of the chapter is in that one program and not one of them is decoration. The count arrives while the program runs, so the storage has to be a heap block, and the request is sized from the object rather than from a type spelled out in two places. The NULL check decides the failure path instead of merely noticing it. The fill loop and the sum both stop at i < count, one character away from the report lesson 5 taught you to read, and values[count - 1] is the last element for the same reason. sum_values never learns where its block came from, because a pointer and a count is all any function gets and const says this one only reads. And main allocated, so main frees, exactly once: both early exits happen before there is anything to give back, which is why this program needs no cleanup label.

Key Terminology

  • Array and element count: a fixed number of objects of one type laid back to back under one name, whose valid indices run from 0 to the count minus one, because an index is a distance from the start
  • Initializer list: braces that start an array off, where a short list zero-initializes the rest so = {0} zeroes the whole thing, and where no initializer at all leaves every element indeterminate
  • Contiguity: the language guarantee that consecutive elements sit sizeof one element apart with no gaps, holding equally for a declared array and a malloc block, unlike the address, which is promised nothing
  • Decay and the sizeof parameter trap: an array name becoming a pointer to its first element in almost every expression, the exceptions being sizeof arr, &arr and a string literal initializing an array, which is why the count idiom is right in the declaring scope and, inside a function, divides pointer size by element size and lies
  • Pointer arithmetic, one-past-the-end, and the pointer plus count pair: p + i moving i elements because the type supplies the scale, with p + count legal to form and compare against and undefined to dereference, and with that pair the only way an array travels, since nothing carries its length at run time
  • malloc and free: bytes requested while the program runs or NULL, sized as count * sizeof *p, checked before use, uninitialized on arrival, and released by exactly one free that you choose to write
  • Ownership: the rule that exactly one piece of code must free each live block, inexpressible in C's type system, transferred by returning a pointer, borrowed by a const T * parameter, and defended in a multi-block function by a single forward goto cleanup label
  • Leak: a live block whose last pointer is gone, a permanent loss of memory in a program that remains well-defined, unlike double free and use after free, and reported only after a successful run
  • stack-buffer-overflow and heap-buffer-overflow: one out-of-bounds mistake reported from the chapter's two homes, where the stack version can name the offending variable inside the frame and the heap version gives the block's size and an allocated by stack instead
  • The is located line: the field that names a block's size and your distance from it, so dividing by the element size tells you whether the index was wrong or the allocation was

Looking Forward

You can now put many values under one name, hand any run of them to a function as a pointer and a count, ask for memory whose size nothing knew until the program ran, and put the chapter's two questions to every line that touches a block: am I inside the bounds, and who frees this? Chapter 5 spends all of it. A C string is an array of char ending in a null terminator, which is why it had to wait for arrays and pointers, and that one byte is the whole contract: the string library reads it to find where strlen stops counting and where strcmp stops comparing, and a copy that loses it walks off the end into the very report you just learned to read. From there, fgets reads whole lines into a buffer whose size you supply rather than trusting input to be short, strings move onto the heap under this chapter's ownership rules with one extra byte remembered for the terminator, and realloc grows a buffer as input arrives, failing in a way that leaks the original block unless you handle it exactly right.