C: memory, pointers, structs, headers, and the C11 toolchain

Overview

Module	lang.03 · practice · C and Python · Pass 1 · 4 to 6 h
You build	primers/lang.03/vec.c: a growable array of int written against the given vec.h, checked as a standalone C program
Contract	none: a standalone primer exercise against the given vec.h interface
Tests	course/tests/lang.03/, run by its check script (what they check: section 4)
Needs	reading: lang.01 (Python, numpy, uv) and lang.02 (compiling, linking, make, exit codes)
Used by	no code call site (a primer). It introduces C memory and standalone C tests; optional C modules remain independent exercises
Milestone	MS-L9, the optional standalone C exercise group
Optional depth	Jens Gustedt, Modern C (free, levels 1 and 2); Kernighan and Ritchie, The C Programming Language, ch. 5 and 6; the C11 draft N1570 (free), 6.2.5 types, 6.5.6 pointer arithmetic, 6.7.2.1 structs, 7.22.3 memory management

Key Takeaways

• Memory is a sequence of bytes with numeric addresses. A C pointer is one of those addresses plus the type of what lives there, and p[i] is the object i * sizeof(*p) bytes past p.
• C checks nothing at run time. An index past the end, a freed pointer, or a signed overflow is undefined behavior: no exception, just wrong bytes. AddressSanitizer and UndefinedBehaviorSanitizer turn most of it into a crash with a report, so you build and test with them on.
• realloc may move the buffer and may fail. Keep the old pointer until it succeeds, and grow geometrically (double), or pushing n elements costs O(n²).
• A struct has padding. Each field starts at a multiple of its alignment, so {int32_t id; double score;} is 16 bytes with score at offset 8, and Python must mirror that layout field for field.
• A header is a contract between C translation units. Include it in both the implementation and test source so the compiler checks declarations against definitions.

How to work this chapter

ol start lang.03     # records the start
ol check lang.03     # the first run writes the starter files into primers/lang.03/, then checks them
ol tests lang.03     # read the test catalog
ol check lang.03     # again after each change; exit code is the verdict

The first ol check writes the starter vec.h and a compiling stub for vec.c into primers/lang.03/. It never overwrites a file. The stub compiles and fails; implement the vector until its standalone sanitizer check passes.

---

1. Why now

The course’s C material consists of optional standalone exercises. In Python, a[7] on a 6-element list raises IndexError. In C, A[7] on a 6-element array reads whatever 4 bytes happen to follow it, quietly, and a kernel can return a plausible number that is wrong. In C, a buffer you forget to free leaks, and one you free twice corrupts the allocator. This primer gives you the model of memory that C assumes and the tools that catch its failures (sanitizers), on exercises small enough to reason about completely.

2. Principles

Notation used in this chapter:

Symbol	Meaning	Type / shape
T	any C type (int, float, a struct)
sizeof(T)	bytes one object of type T occupies	size_t
_Alignof(T)	T’s alignment: its address must be a multiple of this	size_t, a power of two
&x	the address of object x	T *
*p	the object at address p	T
p + i	the address $p + i \cdot \mathrm{sizeof}(T)$	T *
p[i]	the same as *(p + i)	T
offsetof(S, f)	bytes from the start of struct S to its field f	size_t
$\mathrm{roundup}(x, a)$	the smallest multiple of $a$ that is $\ge x$: $\lfloor (x + a - 1) / a \rfloor \cdot a$	integer
$n$, $\mathit{len}$, $\mathit{cap}$	element counts in section 2.4 and 3	size_t

2.1 Bytes, addresses, and types

Memory, as a C program sees it, is one long array of bytes. Each byte has an address, an integer (on a 64-bit machine, 64 bits wide). A C object is a run of consecutive bytes, and its type says how many and how to read them:

Type	sizeof on a 64-bit Mac or Linux	Holds
char, int8_t, uint8_t	1	a byte
int32_t, uint32_t, float	4	a 32-bit integer; a 32-bit IEEE 754 float
int64_t, uint64_t, double	8	a 64-bit integer; a 64-bit float
int	4 (the standard only promises at least 2)	the “natural” integer
size_t	8	a size or an index; unsigned, so 0 - 1 wraps to the largest value
any pointer T *	8	an address

Use the fixed-width types from <stdint.h> (int32_t, int64_t) whenever the width matters, which is always at a language boundary: Python and Rust must agree with C on every byte.

2.2 Pointers and pointer arithmetic

A pointer T *p holds an address and remembers the type at that address. &x takes the address of x; *p is the object at p. NULL is the address no object has; dereferencing it is an error. Arithmetic on a pointer counts in elements, not bytes: if p points at an int32_t at address 4096, p + 3 is 4096 + 3 · 4 = 4108. Indexing is defined as arithmetic: p[i] means *(p + i).

An array int32_t xs[5] is 5 objects back to back, 20 bytes. In almost every expression the array’s name decays to a pointer to its first element, which is why a function that takes const int32_t *xs can receive an array, and why it must also receive the length separately: the pointer does not carry it. const T *p promises the function will not write through p; the compiler holds you to it.

A matrix is stored the same way, as one flat run of numbers. Row-major order puts row 0 first, then row 1, so element $(i, k)$ of an $M \times K$ matrix is A[i * K + k]. M03.1 builds on exactly this.

2.3 Structs, alignment, and padding

A struct groups fields into one object. The hardware reads an 8-byte double fastest (on some machines, only) at an address that is a multiple of 8, so every type has an alignment, and the compiler places each field at the next offset that is a multiple of the field’s alignment:

$\mathrm{offset}_k = \mathrm{roundup}(\mathrm{offset}_{k-1} + \mathrm{sizeof}(\mathrm{field}_{k-1}),\ \mathrm{alignof}(\mathrm{field}_k)), \qquad \mathrm{offset}_0 = 0$

The unused bytes between fields are padding. The struct’s own alignment is its largest field alignment, and its size is rounded up to a multiple of that, so that in an array of structs every element’s fields stay aligned. The compiler never reorders fields. Section 3 works one layout by hand.

2.4 Where objects live: stack, static, heap

Storage	How you get it	Lifetime
automatic (“the stack”)	a local variable float x[4];	until the function returns; a pointer to it afterwards dangles
static	a variable at file scope, or static inside a function	the whole program
allocated (“the heap”)	malloc(n), calloc(k, n), realloc(p, n)	until you free(p)

malloc(n) returns a pointer to n fresh, uninitialized bytes, or NULL when it cannot. free(p) gives them back; free(NULL) does nothing. Ownership is the rule you keep in your head: exactly one piece of code is responsible for freeing each block, exactly once.

realloc(p, n) resizes the block at p to n bytes. It may grow it in place, or allocate a new block, copy the old bytes, free the old block, and return the new address: every pointer into the old block is then dangling. If it fails it returns NULL and leaves the old block untouched and still yours. realloc(NULL, n) is malloc(n). realloc(p, 0) is implementation-defined in C11 and undefined in C23: do not use it.

A growable array keeps $\mathit{len}$ elements in a buffer of capacity $\mathit{cap} \ge \mathit{len}$. When a push finds $\mathit{len} = \mathit{cap}$ it must grow. Growing by a constant $c$ copies $\mathit{len}$ elements every $c$ pushes, about $n^2 / (2c)$ copies for $n$ pushes. Growing by a factor $g > 1$ (doubling, $g = 2$) copies at most $n (1 + 1/g + 1/g^2 + \dots) = n \cdot g / (g - 1)$ elements in total, a constant amount per push on average (amortized O(1)).

2.5 Undefined behavior and the sanitizers

The C standard lists operations whose result is undefined: reading or writing outside an object, using memory after free, freeing twice, dereferencing NULL, reading an uninitialized variable, overflowing a signed integer (int32_t 2,000,000,000 + 2,000,000,000), shifting by the width or more. “Undefined” does not mean “crashes”. The compiler optimizes on the assumption that it never happens, so the program may appear to work, return a wrong number, or fail somewhere far away. Unsigned arithmetic (size_t, uint32_t) is defined: it wraps around modulo $2^{w}$.

Two compiler-inserted checkers find most of it at run time:

Flag	Name	Catches
-fsanitize=address	AddressSanitizer (ASan)	out-of-bounds reads and writes on heap, stack, and globals; use after free; double free. It surrounds every block with poisoned “redzones” and keeps freed memory poisoned for a while
-fsanitize=undefined	UndefinedBehaviorSanitizer (UBSan)	signed overflow, misaligned pointers, NULL dereference, bad shifts, out-of-range conversions
-fno-sanitize-recover=undefined		make UBSan stop the program at the first report instead of printing and continuing

Apple’s clang has no LeakSanitizer (the Linux leak checker), so the course detects leaks by counting allocations: the test routes your malloc, realloc, and free through wrappers that keep a live-block count and fails any test that ends above zero. The standalone C tests use this hook locally to count allocations.

2.6 Headers, declarations, and linkage

lang.02 showed the two build stages: compile each .c to an object file, then link the objects. What crosses between files is names:

• A declaration says a name exists and what its type is: int vec_push(Vec *v, int x);. A definition creates it: the function with its body, or a variable with its storage. A name may be declared many times and defined once.
• A header is a file of declarations that every .c using them #includes. The preprocessor pastes it in textually, so a header is protected by an include guard (#ifndef VEC_H / #define VEC_H / #endif) against being pasted twice into one file.
• Linkage decides who can see a name. A function or file-scope variable has external linkage by default: its name is exported from the object file as a symbol, and the linker resolves every other file’s use of it. Marked static, it has internal linkage: visible only inside its own file, and no symbol is exported.

nm file.o lists an object’s symbols: T for a function defined here and U for one used here but defined elsewhere. On macOS every C symbol carries a leading underscore (_vec_push). Separate compilation checks how independently compiled C files agree at link time. The optional C exercises link objects into standalone test binaries.

2.7 The flags you will use

Flag	Meaning
-std=c11	compile as ISO C11 (the course’s C)
-pedantic	warn about anything C11 does not allow, including compiler extensions
-Wall -Wextra	the common warnings and then some
-Werror	treat every warning as an error: a warning is a bug you have not found yet
-Wno-unused-parameter	except one: a parameter a function does not read yet (a stub’s) is allowed
-O1 -g	light optimization (sanitizers need some) with debug information for readable reports
-c, -o out	compile only (stop at the object file); name the output
-I dir	also look in dir for #include "..."
-include file.h	paste file.h at the top of the source before anything else (the check uses it to wrap your malloc)
-c	compile a source file into an object for a standalone test binary

2.8 Headers and separate compilation

A C header lets independently compiled source files agree on types and function signatures. Include the header in both the implementation and the test program; a missing or mismatched declaration then becomes a compiler error. Link the object files into a standalone test executable. This keeps the C exercise testable without loading a native library into another language runtime.

3. Worked example by hand

Growing a vector. Start from vec_init ($\mathit{len} = \mathit{cap} = 0$, data == NULL) and push 10, 20, 30, 40, 50, doubling from a first capacity of 4:

Push	$\mathit{len}$ before	$\mathit{cap}$ before	Grows?	Call	$\mathit{cap}$ after	Buffer bytes
10	0	0	yes	realloc(NULL, 16) (a malloc)	4	16
20	1	4	no		4	16
30	2	4	no		4	16
40	3	4	no		4	16
50	4	4	yes	realloc(data, 32): may move, copies 16 bytes	8	32

After three pushes, vec_get(&v, 1) reads *(data + 1), the 4 bytes at data + 4: 20. This is the first test, push_and_get_by_hand. If realloc at push 50 had failed, it would return NULL with the 16-byte block still holding 10, 20, 30, 40, which is why the old pointer must survive the call.

4. The exercise and its check

Two files in primers/lang.03/:

File	Given or yours	What it holds
vec.h	given	the Vec struct and six functions (vec_init, vec_push, vec_pop, vec_get, vec_reserve, vec_free), each with its contract in a comment
vec.c	yours	their definitions; standard library only; double the capacity from 4

ol check lang.03 runs course/tests/lang.03/check in your repo. It compiles vec.c with -std=c11 -pedantic -Wall -Wextra -Wno-unused-parameter -Werror under sanitizers, with -include count_alloc.h for the vector allocator counters, links each with its standalone C test binary, and runs the vector test binary. Any failure fails the check.

Test	KIND	Checks
init_allocates_nothing	unit	vec_init sets the zero state and calls no allocator
push_and_get_by_hand	unit	section 3’s pushes read back in order; nothing leaks
pop_is_lifo	boundary	last in, first out; -1 on an empty vector
reserve_does_not_change_len	unit	capacity grows ahead, length does not, and reserve never shrinks
growth_preserves_every_element	property	10,000 pushes through many moves keep every value
growth_is_geometric	property	4,096 pushes take at most 40 reallocations
failed_growth_leaves_the_vec_unchanged	fault	a failing realloc returns -1 and leaves data, len, cap as they were
free_is_idempotent	boundary	a second vec_free is harmless; the vector is reusable

Every test file names the reason for each case in its WHY: line: ol tests lang.03.

5. Pitfalls

Pitfall	Symptom	Caught by
v->data = realloc(v->data, ...)	when realloc fails, the only pointer to the old buffer is lost: the elements are gone and the block leaks	failed_growth_leaves_the_vec_unchanged
growing by one (or any constant)	correct but quadratic: a million pushes take seconds	growth_is_geometric
vec_pop reading data[len - 1] without checking len	len - 1 on a size_t 0 wraps to $2^{64} - 1$; ASan reports a wild read	pop_is_lifo
vec_free leaving data set	the second call frees the same block twice	free_is_idempotent

6. Where it’s used next

Direction	Module	How it uses this
Back	lang.01	numpy arrays are the buffers you hand to C: row-major bytes and strides
Back	lang.02	compile, link, make, and exit codes; ol check is a process whose status is the verdict
Forward	optional C modules	standalone C implementations and their own sanitizer-enabled test binaries
Forward	M03.1	an optional matmul exercise over const float * buffers with explicit leading dimensions, run under sanitizers
Forward	ds.01	an optional type-erased growable array, checked as standalone C

Going further

Your piece	Production equivalent	What it adds	Where to look
Vec doubling from 4	CPython list	grows by about 1.125 plus a constant, trading more frequent copies for less unused memory	Objects/listobject.c, list_resize
Vec	Rust Vec<T>, C++ std::vector<T>	generic element types, move semantics, a growth factor of 2 (Rust) or 1.5 (MSVC)	Rust alloc/src/raw_vec.rs; the libstdc++ and MSVC STL sources
the counting wrappers	jemalloc and mimalloc statistics, LeakSanitizer	per-size-class counters; leak reports with stack traces (Linux)	MALLOC_CONF=stats_print:true; ASAN_OPTIONS=detect_leaks=1