06 The Stack and the Heap: Dynamic Memory and Ownership

Learning objectives

After this chapter you should be able to:

Do unaided:

1. Draw the stack and heap after each line of a short program, marking every pointer, block and owner.
2. Write correct calls to malloc, calloc, realloc and free, including the null check and the realloc pattern that keeps the original block on failure.
3. Write an ownership rule (caller owns, callee owns or borrowed) as a comment before writing a function that allocates, frees or receives a pointer.
4. Explain why leaks, double frees, use-after-free, dangling pointers and returned pointers to locals are wrong, and predict which instrument reports each.
5. Read an AddressSanitizer, LeakSanitizer or Valgrind report line by line and name the bad access, the allocation site and the free site.

May delegate:

1. Ask the tutor to explain one line of a sanitizer or Valgrind report, after writing your own hypothesis about it.

Opening case

A composite case, not a real student or course.

Jonah writes the median function for the station's daily report in 20 minutes. It copies the day's 1,440 humidity readings into a scratch buffer, sorts the copy and picks the middle value. He is pleased with the NaN check: a faulty sensor will not poison the report. Before submitting, he pastes it into a chat tutor and asks: "Does this leak memory?"

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Tutor phase.

1. Predictdraw the stack and heap after each line of Listing 6.13 and predict the leak report, with your confidence.

   Step 1 of 6 · You, no AI

   What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

   Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

   The first prediction is never delegated.

   Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

   Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 5 · Predict in Chapter 7 →

2. Writeby hand, a function that returns a new buffer of readings, its ownership comment written first.

   Step 2 of 6 · You, no AI

   What you hand in: One small piece written by hand, to build the mental model.

   Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

   Ask yourself: Could I write this piece again tomorrow without notes?

   Browse the companion code · Write in every chapter · ← Write in Chapter 5 · Write in Chapter 7 →

3. Specifya question for the tutor about one report line, with your hypothesis.

   Step 3 of 6 · You

   What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

   Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

   Tutor In the Tutor phase you specify a question instead of code: what you want explained, quizzed or drilled.

   The ownership and lifetime section of a specification is never delegated.

   Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

   Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 5 · Specify in Chapter 7 →

4. Delegatethe tutor explains that line by asking questions, without code.

   Step 4 of 6 · The agent

   What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

   Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

   Tutor Tutor phase: the agent explains, quizzes and makes practice problems. It writes no code you submit.

   Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

   Prompt templates · Delegate in every chapter · ← Delegate in Chapter 5 · Delegate in Chapter 7 →

5. AuditASan and LSan, Valgrind on the -O0 build, and the fail-the-k-th sweep.

   Step 5 of 6 · You and the tools

   What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

   Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

   Tutor In the Tutor phase the audit checks the tutor's claims as well as your own code.

   The final judgment that the code is correct is never delegated.

   Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

   The Audit Report template · Audit in every chapter · ← Audit in Chapter 5 · Audit in Chapter 7 →

6. Defendfor every pointer, say who owns it after each line and where it is freed on each path.

   Step 6 of 6 · You, live

   What you hand in: A five-minute oral defense.

   Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

   Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

   How the loop works · Defend in every chapter · ← Defend in Chapter 5 · Defend in Chapter 7 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

What the chapter covers

1. 6.1 The concept, by hand
   • 6.1.1 Why a heap exists
   • 6.1.2 The malloc family
   • 6.1.3 realloc and losing the original pointer
   • 6.1.4 free does not reset the pointer
   • 6.1.5 Ownership: one owner who frees
   • 6.1.6 Leaks, dangling pointers, use-after-free and double frees
   • 6.1.7 Returning a pointer to a local: the Chapter 3 preview, explained
   • 6.1.8 Reading the reports line by line
   • 6.1.9 Testing error paths: fail the k-th allocation
   • 6.1.10 PA2 begins: the rvec and rlist interfaces
2. 6.2 Predict and check
3. 6.3 What agents get wrong here
   • 6.3.1 Freeing on one path and not another
   • 6.3.2 Returning a pointer to a local
   • 6.3.3 realloc assigned straight back to the same pointer
4. 6.4 Working with the agent
5. 6.5 Lab: The agent says "no leaks"; Valgrind decides
6. 6.6 Defend it

Cost thread

This chapter counts allocator calls; Valgrind reports them as total heap usage: N allocs. A companion program (ch06/alloc_cost.c) stores 1,000,000 readings two ways.

Summary

• Stack frames die at return and the stack is small; heap blocks live until freed and can be large.
• Every allocation can return NULL, and every error path must leave nothing allocated. Assign realloc to a temporary; on failure the old block is still yours.
• free(p) returns the block and leaves p unchanged; that pointer and every copy of it now dangle.
• Every allocation has exactly one owner. Write the rule (caller owns, callee owns, borrowed) and its failure clause before the code.
• ASan, LSan and Valgrind name the access, the allocation and the free, but only on paths that run. Valgrind needs a build without sanitizers; 0 allocs means the wrong binary ran.
• Failing the k-th allocation on purpose runs error paths that otherwise run only in the field.

Key terms

Companion code

5 files for this chapter, compiled with the book's flags.

Read the code Download ch06.zip

Connections

Where this chapter and another point to each other most often.

• Chapter 2: The Working Loop
  After the tutor prompt from Chapter 1, use this pattern: Log the hypothesis and confidence before sending (Chapter 2).
• Chapter 3: Control Flow, Functions, Recursion, and Counting Operations
  This chapter answers it: where copy lives, who owns it, what each instrument can see, and how to make every error path run before you trust a clean report. ## 6.1 The concept, by hand ### 6.1.1 Why a heap exists Every call gets a stack frame that disappears at the return (Chapter 3).
• Chapter 4: Pointers
  The function takes double **buf (Chapter 4) because it may change where the caller's pointer points.
• Chapter 5: Arrays, Strings, and Matrices: n, n², n³
  malloc succeeds and returns 8 bytes, room for one reading, and the loop that follows writes 2⁶¹ + 1 of them: an out-of-bounds write (Chapter 5).
• Chapter 7: Structs, Headers, and Multi-File Programs
  Chapter 7 defines struct reading and makes these real headers; Chapter 8 teaches growth and linking, and PA2 is due there with a hidden timing test of 1,000,000 appends.
• Chapter 8: Growable Arrays and Linked Lists: The Cost of Growth
  How much to grow by is Chapter 8's subject. ### 6.1.4 free does not reset the pointer The most common misconception in this chapter is that free(p) sets p to NULL.
• Chapter 11: Specify First: Abstract Data Types
  From Chapter 11: The station's rvec and sensor_db follow the rule set in Chapter 6 and kept in Chapter 7: a container stores copies of the readings it is given, and the caller keeps whatever it passes in.
• Chapter 12: Moving to C++: Is It Really C++?
  Do not cast the result; C converts void * by itself (C++ differs, Chapter 12).
• Chapter 14: Resource Ownership: RAII, the Rules of Zero, Three, and Five, and Smart Pointers
  Chapter 14 returns to this. ## Further reading - Kernighan and Ritchie (1988), Sections 5.4 and 8.7: a short storage allocator; what malloc and free do inside. - Serebryany et al.

See it on the map

Further reading

• Kernighan and Ritchie (1988), Sections 5.4 and 8.7: a short storage allocator; what malloc and free do inside.
• Serebryany et al. (2012): the AddressSanitizer paper; read it for shadow memory and redzones.
• MITRE (2024, CWE-416) and MITRE (2024, CWE-401): why use-after-free and leaks are security bugs.