08 Implicit Memory Management and Garbage Collection, Debugging, Testing, Design

Lecture from: 08.10.2025 | Video: Videos ETHZ

Implicit Memory Management: Garbage Collection

We now switch gears to discuss the alternative to C’s manual free(): garbage collection (GC), the automatic reclamation of heap-allocated storage.

The core question for a GC is: How does the memory manager know when memory can be freed?

The answer is based on the concept of reachability. A block of memory is considered “garbage” if it is no longer possible for the application to reach it.

Memory as a Graph

We can view all of memory as a directed graph:

• Nodes: Each allocated block in the heap is a node.
• Edges: A pointer from one block to another is a directed edge.
• Root Nodes: These are locations outside the heap that contain pointers into the heap. The roots are the starting points for all memory access. They include:
  • Global variables.
  • Local variables on the stack.
  • CPU registers.

Reachability

A heap block is reachable if there is a path of pointers from any root node to that block. Any block that is not reachable is garbage and can be safely reclaimed.

Mark-and-Sweep Collection

A classic and influential GC algorithm is Mark-and-Sweep, first developed by John McCarthy in 1960 for Lisp.

It operates in two phases when the system runs out of memory:

1. Mark Phase: Traverses the memory graph starting from the root nodes. It follows every pointer and sets a special mark bit in the header of every reachable block.
2. Sweep Phase: Scans the entire heap from beginning to end. For each block it encounters:
   • If the mark bit is set, it means the block is reachable. The bit is cleared for the next GC cycle.
   • If the mark bit is not set, it means the block is unreachable garbage. The block is freed and added back to the free list.

Conservative Garbage Collection for C

Can we have GC for C? Yes, but it’s tricky. In a language like Java, the runtime knows exactly which variables are pointers and which are not. In C, a long and a pointer can have the same bit pattern.

A conservative garbage collector for C handles this by making an assumption: if a value on the stack or in a register looks like it could be a pointer into the heap (i.e., its numeric value falls within the heap’s address range), the collector conservatively assumes it is a pointer and marks the corresponding block as reachable. This means it might fail to collect some garbage (if an integer happens to look like a pointer), but it will never accidentally free memory that is still in use.

Common Memory Pitfalls

Manual memory management is unforgiving. Here is a rogue’s gallery of common memory-related bugs in C.

• Dereferencing Bad Pointers: The most common error is passing a variable itself when a pointer to it is expected.

  // WRONG
  int val;
  scanf("%d", val); // scanf expects an address, but gets garbage value of val
   
  // CORRECT
  scanf("%d", &val); // Pass the address of val

• Reading Uninitialized Memory: malloc gives you garbage. If you read from it before writing to it, your program’s behavior is undefined.

  // WRONG
  int *y = malloc(N * sizeof(int));
  for (i=0; i<N; i++) {
      for (j=0; j<N; j++) {
          y[i] += A[i][j] * x[j]; // Reads uninitialized y[i]!
      }
  }
   
  // CORRECT: Use calloc or initialize y[i] to 0 in the outer loop.

• Overwriting Memory:

  • Allocating the wrong size: A classic error is allocating space for an array of ints but using sizeof(int) instead of sizeof(int *) for an array of pointers.

    // WRONG: Allocates space for N ints, not N int pointers.
    int **p = malloc(N * sizeof(int));

  • Off-by-one errors: Using <= instead of < in a loop condition is a common way to write one element past the end of an array.
  • Unbounded string copies: Using dangerous functions like gets() which don’t check buffer sizes is an invitation for buffer overflow attacks. Never use gets().

• Referencing Nonexistent Variables: Never return a pointer to a local variable. The variable’s memory on the stack becomes invalid the moment the function returns.

  // WRONG: Returns a pointer to memory that is about to be deallocated.
  int *foo() {
      int val;
      return &val; // Dangling pointer!
  }

• Forgetting to free (Memory Leaks): If you malloc memory in a function and don’t free it or return the pointer, the memory is leaked.

  // WRONG: Leaks the entire linked list except for the head.
  free(head); // Only frees the first node!

• Freeing/Referencing Freed Blocks: Double-freeing or using a pointer after it has been freed can corrupt the allocator’s internal data structures, leading to bizarre and hard-to-debug crashes later in the program.

Design and Debugging

Writing code is only part of a programmer’s job. Writing good code, code that is correct, robust, maintainable, and understandable, is a much harder and more important skill. This chapter is about the philosophy and practice of designing clean code and the systematic art of finding and fixing bugs when things go wrong.

The Origin of “Bug”

The term “bug” in computing has a famous, literal origin. On September 9, 1947, engineers at Harvard working on the Mark II computer found the source of a malfunction: a moth trapped in a relay. They taped the insect into their logbook with the note: “First actual case of bug being found.” The act of removing it was, literally, “debugging.”

Defects, Errors, & Failures

In software engineering, we use more precise terminology to describe the lifecycle of a bug.

1. A programmer creates a defect (or a “bug”). This is a mistake in the code, like using < instead of <=.
2. The defect, when executed under certain conditions, may cause an error. This is an incorrect internal state in the program, like a wrong value in a variable or an incorrect control flow path.
3. The error propagates. The incorrect state may be used in subsequent calculations, corrupting more of the program’s state.
4. Eventually, the error may cause a failure. This is when the program produces an observable, incorrect result at an interface (e.g., wrong output, a crash).

Why is an error not necessarily a failure?

An error might be corrected by later code (e.g., a wrong value is overwritten before it’s used). It might affect a part of the program state that doesn’t influence the final output. Or the program might terminate before the error has a chance to cause a visible failure.

The Curse of Testing

This leads to a fundamental truth about software quality, famously articulated by Edsger Dijkstra:

“Testing can only show the presence of bugs – not their absence.”

Not every defect causes a failure on every run.

• A defect can be latent, hidden in code that is rarely executed.
• A defect might only become active under a specific combination of inputs or system states.

This is why thorough testing is so critical. We must try to create the conditions that turn latent defects into observable failures.

Debugging: The Classic Mystery Game

Debugging is the process of working backward from an observed failure to find and remove the underlying defect.

Testing Your Code

Good debugging starts with good testing. Don’t treat testing as an afterthought.

• Test Incrementally: Write tests as you develop your code. After adding a new function or feature, immediately write a test for it. This makes it much easier to pinpoint the source of a bug, it’s likely in the code you just wrote.
• Test the Simple Parts First: Build confidence in your simple helper functions before you test the complex functions that rely on them.
• Test Boundary Conditions: This is where many bugs hide. Always test:
  • Empty inputs (e.g., an empty list, an empty string).
  • Single-item inputs.
  • The smallest and largest possible values.
  • Inputs that are exactly at the limit (e.g., a full array).

Example: Test Cases for a Sorted Linked List

Let’s consider a function to insert a value into a sorted linked list. What are the essential test cases?

1. Empty list: Inserting into a NULL list. This is a crucial base case.
2. Single-item list:
   • Insert a value that already exists (should only increment frequency).
   • Insert a smaller value (should become the new head).
   • Insert a larger value (should be appended to the end).
3. Multi-item list:
   • Insert at the beginning.
   • Insert at the end.
   • Insert in the middle.
   • Insert an existing value in the middle.

Thinking through these cases before you write the code is a powerful design technique.

General Debugging Advice

When you encounter a failure, a systematic approach is your best weapon.

1. Examine the Most Recent Change: If you’ve been testing iteratively, the bug is almost certainly in the code you just added or modified.
2. Simplify the Input: Find the smallest, simplest test case that still triggers the failure. A bug that happens with input="a" is much easier to trace than one that only happens with a 1000-character string.
3. Use a Debugger (gdb): For crashes (like segmentation faults), a debugger is essential. The first thing to do is get a stack trace (bt in gdb) to see which function was executing when the crash occurred.
4. Sanity-Check Intermediate Results: Don’t assume your code is doing what you think it’s doing.
   • Use printf statements to trace the flow of execution and inspect the values of variables at key points.
   • Learn to use the debugger to step through your code line by line (step, next) and inspect variables (print var).
5. Understand the Root Cause: Resist the temptation to apply a quick fix that “seems to work.” If you don’t understand why the fix works, you haven’t truly solved the problem. The bug will likely reappear in a different form later.
6. Check for Similar Mistakes: Once you find and understand a bug, ask yourself: “Did I make this same logical error anywhere else in my code?” It’s common for a misunderstanding to lead to similar bugs in multiple places.

Diagnosing Failures: The Scientific Method

Debugging is essentially applying the scientific method to your code.

1. Observe: Know what output you expect for a given input. The difference between the expected and actual output is the failure.
2. Hypothesize: Form a specific, testable hypothesis to explain the failure. “The loop is terminating one iteration too early because I used < instead of <=.”
3. Predict & Test: Use your hypothesis to develop a fix. Before running the code, predict what the new output will be.
4. Confirm: Run the test. Does the fix resolve the failure? Does it pass all your other test cases?

Correlation Does Not Imply Causation

Be wary of the post hoc fallacy. Just because a change made the bug go away doesn’t mean the change was the correct fix. It might have just shifted the memory layout or hidden the bug in a different way. You must understand why the defect and the fix are related.

Debugging Tools

• Debugger (gdb): Your primary tool for inspecting program state. It lets you see the call stack, variable values, and the path of execution.
• valgrind: An essential tool for C programmers. It can detect a wide range of memory errors that gdb can’t, such as reading uninitialized variables, memory leaks, and accessing memory out-of-bounds.

Design: Managing Complexity and Communication

The final part of this lecture moves from fixing broken code to designing code that is less likely to break in the first place. Good software design aims to achieve many goals: performance, security, testability, etc. But these can be unified under two main themes:

1. Complexity Management: Software is inherently complex. Good design uses techniques to keep this complexity manageable.
2. Communication: Code is not just for computers. It’s for people.

The overarching goal is simple: your code must be readable.

Complexity Management Techniques

• Separation of Concerns: Each function or module should do “one thing” and do it well. Avoid giant, monolithic functions that try to do everything.
• Modularity & Encapsulation: Break your system into independent modules. Each module should be responsible for its own internal state and expose a clean, well-defined interface. No outside code should “intrude” on the inner workings of another module.
• Abstraction: Hide implementation details behind a simple interface. The user of a module shouldn’t need to know how it works, only what it does.

Communication

When you write code, you are communicating with multiple audiences:

• The machine.
• Other developers on your team.
• Code reviewers.
• Your future self, who will have forgotten why you made that strange design choice six months ago.

Techniques for good communication include writing good tests, using clear names, and writing effective comments.

Naming is Understanding

“If you don’t know what a thing should be called, you cannot know what it is. If you don’t know what it is, you cannot sit down and write the code.” - Sam Gardiner

• Convey Meaning and be Accurate: Names should describe what a variable or function is or does. Avoid meaningless names like a, foo, data, or info. Be specific. subTreeNumNodes is much better than size.
• Use Short Names for Locals, Longer for Globals: A short name like i is fine for a 3-line loop. A global variable, which can be accessed from anywhere, needs a more descriptive name like global_user_config_path.
• Be Consistent: Pick a naming convention (e.g., camelCase or snake_case) and stick to it. Use opposites consistently (first/last, add/remove).

Comments: The Why, Not the What

The most common mistake with comments is explaining what the code does. The code itself should make that clear. Good comments explain why.

Comment Don'ts

• Don’t say what the code does: i++; // Increment i is a useless comment.
• Don’t explain awkward logic: If the code is so confusing it needs a long explanation, rewrite the code to be clearer.
• Don’t add too many comments: They clutter the code and quickly get out of date.

What Comments Should Do

Good comments answer the high-level questions:

• Why does this code exist? What problem does it solve?
• What are the pre-conditions and post-conditions? When should I use this?
• Are there any non-obvious limitations or edge cases? When shouldn’t I use this?
• Are there alternatives to be aware of?

A great technique is to code by commenting. Before writing a complex function, outline its logic with a series of one-line comments. This helps you think through the design first and provides a ready-made structure for your code.

// Example for quick sort:
// Initialize locals
// Pick a pivot value
// Reorder array around the pivot
// Recurse