Dynamic memory allocation

C programming · CM10 · 90 minutes

Louis Ledoux

ISTIC · University of Rennes

2026–2027

Start with a small program

int total = 0;
void visit(void) {
    int values[4] = {10, 20, 30, 40};
    total += values[0];
}

Call visit() twice. What survives between the calls?

0–3 min. Run the complete program: total is 20. Draw attention to the global object and the automatic array before introducing any errors. The implementation may optimise storage; this unoptimised teaching model represents ordinary locals with stack frames.

Where does the program keep its data?

A typical layout, not a C language guarantee. Not to scale.

3–6 min. Point to total in static storage and values in the visit stack frame. New calls add frames, returns remove them. Draw opposing growth arrows explicitly. Heap allocations are introduced next; they need not be adjacent to each other. Modern allocators also use separate virtual-memory mappings. Do not infer a fixed numerical distance, size, or allocation order from this sketch.

Who controls an object’s lifetime?

Static storage

Globals and static objects exist for the whole program. Storage is reserved before execution.

Automatic storage

An ordinary local exists during its block execution. Each recursive call gets its own locals.

The implementation manages their storage. Deep recursion can exhaust the stack.

6–8 min. The source’s static allocation at compile time describes preparation of storage; the object exists during execution, from program startup to termination. Ordinary fixed-size local arrays have fixed extent; C also has variable-length arrays in some environments. Their automatic lifetime is still tied to their scope. Stack storage is normally contiguous within frames, subject to layout/padding; heap blocks have no adjacency guarantee.

What if the size comes from the user?

size_t count;
if (scanf("%zu", &count) != 1) return EXIT_FAILURE;
if (count == 0 || count > 1000) return EXIT_FAILURE;
int *p = malloc(count * sizeof *p);
if (p == NULL) return EXIT_FAILURE;

The size is chosen during execution. The allocation can outlive the function that creates it.

8–12 min. Enter 4, then 100 in standard input and rerun. Introduce stdlib.h and malloc as a request for storage. The upper bound keeps count * sizeof *p safe in this example; do not turn this into an input-parsing lecture. Motivation retained from slide 284: runtime size, control of lifetime, and finite stack capacity (deep recursion can exhaust it). Heap space is also finite; failure must be handled. Dynamic allocations need not be contiguous with one another; each successful malloc gives one contiguous block.

Request storage for 100 integers

size_t count = 100;
int *p = malloc(count * sizeof *p);
if (p == NULL) {
    fputs("Allocation failed\n", stderr);
    return EXIT_FAILURE;
}

malloc returns the block’s address, or NULL on failure. The contents are uninitialised.

12–15 min. Reconstruct the inherited 100-integer example from source slide 292, in two steps. Its allocation-failure branch is retained, with English names/messages. Include stdlib.h. Check the pointer before any access. No cast is required in C.

Count elements, request bytes

void *malloc(size_t size);   // From <stdlib.h>
int *p = malloc(100 * sizeof *p);

• size_t is unsigned, with at least 16 value bits.
• sizeof is an operator giving a size in bytes.
• sizeof *p is the size of one int, not the pointer.

Sizes depend on the platform. In C, the void * result needs no cast.

15–17 min. Preserve the type-based form: malloc(count * sizeof(int)) is equivalent here; generically count * sizeof(type). size_t can represent at least 0 through 65535 (SIZE_MAX >= 65535), as required by C17. For a fixed int type, sizeof *p does not evaluate/dereference p. For unrestricted external counts, check multiplication overflow before allocating. Explicit correction: sizeof is not a function, and the original mandatory-cast claim is wrong for C.

Initialise, then use the block

for (size_t i = 0; i < count; ++i)
    p[i] = 0;
printf("first=%d, last=%d\n", p[0], p[count - 1]);

One contiguous allocation

Valid indices are 0 ≤ i < count. Write each value before reading it.

17–19 min. Run the complete 100-integer program. Change the initial value from 0 to 7 and rerun. Ask for the byte count on this machine, then check sizeof(int). The complete file ends with free(p); reveal that operation next.

Finish the job with free

void free(void *pointer);   // From <stdlib.h>
free(p);                   // After the last use.
p = NULL;

End the allocation's lifetime

Pass the start address of a live allocation from malloc, calloc or realloc. free returns no value.

free(NULL) has no effect. Free each allocation once.

Invalid or repeated free is undefined behaviour.

19–21 min. The useful sequence is request → check → initialise/use → release. free releases the block, not the pointer variable. Assigning NULL afterwards is a separate operation and does not update aliases. Explain invalid arguments (interior pointers, local objects, a previously freed allocation) as undefined behaviour; actual error investigations follow only after the working baseline.

Four functions in <stdlib.h>

Function	Purpose
malloc(bytes)	Allocate uninitialised storage
calloc(count, size)	Allocate storage with all bits zero
realloc(p, bytes)	Resize an allocation; it may move
free(p)	Release an allocation

21–22 min. Original overview, not a new calloc/realloc lesson. For nonzero size, realloc failure leaves the old block valid: use a temporary pointer. calloc’s all-bits-zero guarantee is not a universal guarantee for pointer/floating representations. We focus on malloc/free today.

Compile, run, then inspect

gcc -std=c17 -Wall -Wextra -g -O0 main.c -o program
./program
valgrind --leak-check=full ./program

Read the error summary, then the heap summary. A program can print the expected result and still misuse memory.

22–25 min. Open the four-integer example, first run normally, then choose Valgrind and run again. Explain -g (source locations) and -O0 (simple debug build). Memcheck is the default Valgrind tool; –tool=memcheck is also valid, as in inherited source slide 145. Look for zero reported errors and all blocks freed. Do not present that as proof over all inputs. All output is generated live; make valgrind is the equivalent terminal action.

One character creates an overrun

int *a = malloc(4 * sizeof *a);
if (!a) return EXIT_FAILURE;
for (size_t i = 0; i <= 4; ++i)
    a[i] = (int)(10 * (i + 1));

Which iteration writes outside the allocation?

25–29 min. Predict, compile, run under Valgrind. Locate “Invalid write”, the source line, and the allocation location. Relate “0 bytes after a block” to index 4. Change <= to < in the live editor and rerun until the diagnostic disappears. Compiler success and ordinary execution do not establish memory safety. This investigation makes the source’s array bounds concrete without expanding the syllabus.

Allocated does not mean initialised

int *a = malloc(4 * sizeof *a);
if (!a) return EXIT_FAILURE;
printf("a[0] = %d\n", a[0]);

valgrind --track-origins=yes ./program

29–31 min. Brief second mutation: remove the initialisation. A printed zero is not evidence of initialisation. Follow the uninitialised-value origin back to malloc; add a[0] = 10 before printf and rerun. The live runner combines –track-origins=yes with –leak-check=full. If time is tight, ask the prediction and show the repair without a second terminal transition.

Memory leak: lose the address

p = NULL;  // No free before the only address is lost.

31–34 min. This is a memory leak: allocated memory is no longer useful/reachable and was not released. Under Valgrind, locate “definitely lost” and the allocation call site. The diagnostic identifies where the block was allocated, not necessarily where its last address was overwritten. Add free(p) before p = NULL, then rerun. Repeated leaks increase memory use over time. Releasing at process exit does not fix a long-running program’s lifetime management.

Dangling pointer: the object is gone

free(p);
printf("%d\n", *p);  // Use after free: undefined behaviour.

34–37 min. Predict then run under Valgrind. Trace invalid read → free → allocation, in that order. Move printf before free to repair it. GCC may also warn; that is useful but not a substitute for understanding lifetime. free does not set p to NULL; no remaining alias may dereference the object. A second free of the same allocation is also invalid. Contrast with the previous slide: a leak keeps the storage; a dangling pointer outlives the storage.

Local objects can expire too

int *bad_result(void) {
    int value = 42;
    return &value;  // The local dies when this call ends.
}

A dangling pointer need not come from free

Returning an address does not extend an automatic object’s lifetime.

37–38 min. Tie this back to the stack frame in the opening diagram. Do not execute the invalid access. A function may instead return the value, fill caller-owned storage, or allocate a result with an agreed owner. Memcheck does not detect every stack lifetime error; the C lifetime rule is what matters here.

Who is responsible for reclamation?

C: explicit responsibility

For every successful allocation, decide who will release it and when. Repeated leaks consume more memory.

Java: garbage collection

The runtime can reclaim unreachable objects automatically.

38–39 min. Source slide 287 comparison. Garbage collection is not necessarily immediate and cannot reclaim reachable-but-unwanted objects. This is a short recap of responsibility, after students have observed a leak rather than before their first allocation.

Checkpoint · questions 1–5

Answer questions 1–5, then discuss your reasoning.

Open the allocation quiz.

39–43 min. Retain the inherited question set and order. Its file/title use older CM numbering; the chosen PowerPoint calls this CM10. Do not silently renumber the original quiz asset.

A one-dimensional integer array

int *a = malloc(4 * sizeof *a);

Use a[i], equivalently *(a + i), for 0 ≤ i < 4.

43–45 min. Return to the working four-element example after the quiz. Generic allocation: type a = malloc(count sizeof *a). The source’s 0x1000 addresses are illustrative, with sizeof(int)=4 for that drawing; real addresses and sizes may vary.

A character array can hold a string

char *s = malloc(4 * sizeof *s);

Three letters need four bytes, including '\0'.

45–47 min. A char is one C byte, so sizeof(char) is 1. The generic form is count * sizeof(char). Check allocation, copy or assign characters including the terminator, use the string, then free. Bounds and lifetime rules do not change with the element type.

Assigning a pointer is not copying text

char *s = malloc(100);
if (!s) return EXIT_FAILURE;
s = "hello";
char *p = s;
s = "bye";

Predict the values of p and s, and the fate of the allocation.

47–49 min. Keep all three assignments from source slide 296. Run once normally to observe hello/bye; optionally run Valgrind to connect this example to the earlier leak. There is no copy of the text when assigning a pointer. Trace all three states on the next slide.

Follow the three assignments

The literals are separate from the lost heap block. Neither pointer can now be passed to free.

49–50 min. Literals have static storage duration and must not be modified. The three panels show pointer assignments, not character moves. The red orphan block is the same original allocation throughout. Uninitialised p is never read; it first appears when declared.

Copy characters into owned storage

char *s = malloc(6);
if (!s) return EXIT_FAILURE;
strcpy(s, "hello");  // Include <string.h>.
printf("%s\n", s);
free(s);

Alternatively, just reference a literal

Use const char *s = "hello"; when no writable copy is needed.

50–51 min. Repair the existing live string example by copying into the allocation and freeing its original address. strcpy needs enough room, including ‘\0’; it does not allocate storage. Keep this to one minute: it repairs the inherited pointer-assignment example, not a general string-library lesson.

A 2D array in one block

int *m = malloc(4 * 3 * sizeof *m);
/* After checking m: element (i, j) is m[i * 3 + j]. */

One allocation, one free(m).

51–54 min. Generalise to rows * columns * sizeof(type). Index = i * columns + j. Count rows/columns and bytes; do not confuse the flat pointer with an int**. The complete example checks malloc.

An array of row pointers

int *m[4];  // Automatic table of four pointers.
for (size_t i = 0; i < 4; ++i)
    m[i] = malloc(3 * sizeof *m[i]);

Check each row. Use m[i][j]; free each row, not m.

54–57 min. Generic type *m[ROWS], with each row allocated separately. Rows need not be adjacent; the pointer table is automatic. The full live file handles partial allocation failure by freeing the earlier rows. Ask which part disappears automatically and which part needs free.

Allocate the pointer table too

int **m = malloc(4 * sizeof *m);
for (size_t i = 0; i < 4; ++i)
    m[i] = malloc(3 * sizeof *m[i]);

Check m first, then each row. Free rows first, then free(m).

57–60 min. Five allocations and five releases. sizeof m is a pointer size; sizeof m[i] is an integer size. The displayed loop assumes the table allocation has already been checked; the runnable file includes all checks and partial-failure cleanup. Ask students to locate each allocation in the diagram.

Checkpoint · questions 6–8

Answer questions 6–8, then discuss your reasoning.

Open the allocation quiz.

60–63 min. Preserve source slide 300 checkpoint. Matrix examples are explanatory comparisons, not three additional full coding sessions.

User-defined types

Three tools

enum names integer constants. struct groups members. typedef introduces a name for a type.

Use them to describe more complex data, including list nodes.

63–64 min. The authoritative allocation CM also includes these types. Keep the complete section; do not drop it to make room for the demonstration sequence.

Enumerations

enum day { mon, tue, wed, thu, fri, sat, sun };
enum day today;
today = wed;

By default, values start at 0 and increase by 1.

Named integer constants

mon is 0; wed is 2; sun is 6.

64–66 min. Generic syntax: enum tag { enumerators }; then enum tag variable. Preserve separate type definition, variable definition and assignment from source slide 302. Names can also have explicitly assigned integer values, but no additional exercise is needed.

A structure groups several members

struct address {
    char street[100];
    int number;
};

A type definition

Members may be integers, floating-point values, arrays, pointers or other structures. No address object exists yet.

66–68 min. Retain the source’s generic structure syntax and member-type list. Defining a type does not allocate an instance. A member declaration inside a C struct cannot have an object initializer; initialise a variable of that type instead.

Define a type, then create objects

struct address home;
struct address office;

These definitions allocate two distinct objects of the same type.

Local objects need initialisation

Ordinary local members have indeterminate values until initialised or assigned. The type definition alone sets no values.

68–69 min. Source slide 304 distinguishes type definition from variable definition and initialisation. Static objects would instead receive zero initialisation. Keep the automatic-local context explicit.

Initialising a structure

struct address home = { "Paul Bert", 12 };

Or combine the type and object definitions:

struct address {
    char street[100];
    int number;
} home = { "Paul Bert", 12 };

69–71 min. These are alternative forms, not declarations to place together in one scope. Initialisers follow member order; omitted members are zero-initialised. Allocation size includes any implementation-required padding, introduced next.

Structure layout and alignment

Padding

The implementation may insert unused bytes between members and at the end to satisfy alignment requirements.

• Members appear in declaration order.
• sizeof(struct T) includes padding.
• Layout and alignment depend on the implementation.

71–73 min. Preserve the source’s hardware motivation: alignment can simplify or speed memory access and may be required by the architecture. Correct its blanket claim that every processor always reads one word. No padding appears before the first member. Member alignment is type/platform dependent, not a universal single word size.

Same members, different order

struct grouped {
    int id1, id2;
    char c1, c2;
    float ratio;
};
struct interleaved {
    int id1; char c1;
    int id2; char c2;
    float ratio;
};

73–74 min. Restore both actual structure definitions from source slide 307, ahead of the byte diagram. Ask whether equal member types imply equal total size. The executable uses these same members/order, with descriptive type names.

See where the padding goes

16 vs 20 bytes in this layout. Measure with sizeof and offsetof.

74–76 min. Run and connect output to the exact two definitions. Four-byte int/float and their alignment are assumptions of the illustration, not C guarantees. Offsets are measured in bytes from the object start. The original 0x1000-based addresses are equivalent to these more portable relative offsets.

Access members through an object

struct address home = { "Paul Bert", 12 };
strcpy(home.street, "Rue de Paris");
home.number = 14;

The dot operator

Use . with a structure object.

strcpy needs <string.h> and enough space for the terminator.

76–78 min. Preserve both the string-member update and integer-member update. An array member cannot be assigned a string literal after definition; copying its characters is a different operation.

Access members through a pointer

struct address *p = &home;
strcpy(p->street, "Rue de Paris");
p->number = 16;

The arrow operator

Use -> with a pointer. p->number is the same member as (*p).number.

Both forms above modify home.

78–79 min. Restores the source’s explicit strcpy via ->, not just an integer assignment. No new structure is copied or allocated by taking &home.

typedef: a name for a type

typedef int LENGTH;
typedef enum { FALSE, TRUE } BOOLEAN;
typedef struct date DATE;

Alias

A typedef introduces a type name, not an object or a distinct underlying type. Then write LENGTH width;.

79–81 min. Generic syntax in the original is typedef type IDENTIFIER; correct its LENGHT typo. BOOLEAN uses an anonymous enum: no enum tag is needed. DATE avoids repeatedly writing struct date (its definition appears next). This is C17; FALSE/TRUE are the original teaching example, not a replacement for the standard bool interface.

Combine a date and a day of the week

struct date { short day, month; int year; };
typedef enum { mon, tue, wed, thu, fri, sat, sun } DAY;
typedef struct { DAY day; struct date date; } A_DATE;

A nested structure

A_DATE contains a DAY and a complete struct date.

81–83 min. Transcribe both source images: short day/month, int year; enum of seven weekdays; anonymous structure typedef combining the enum and date. English names replace JOUR/UNE_DATE, without changing layout or nesting.

Access nested members

A_DATE today = { wed, { 3, 9, 2014 } };
today.day = wed;
today.date.year = 2014;
A_DATE *p = &today;
p->day = today.day;
p->date.year = 2026;

p->date.year reaches the nested member of the same object.

83–85 min. Keep the original 3 September 2014 initializer and object/pointer access chain. The final year changes to 2026 in the executable to make aliasing observable; the original repeats 2014. Run once, or predict together if needed to preserve the final quiz time.

Checkpoint · questions 9–12

Answer questions 9–12, then discuss your reasoning.

Open the allocation quiz.

85–90 min. Retain all three source quiz groups. See docs/allocation-runbook.md for pacing, terminal commands, expected diagnostic families and repairs. The 41 slides are visual steps within one 90-minute class, not 40 independent activities.