Project 6: Stack Frame and Unwind Explorer

A tool that reads unwind metadata and reconstructs a call stack view.

Quick Reference

Attribute	Value
Difficulty	Level 4
Time Estimate	2-3 weeks
Main Programming Language	Python or C (Alternatives: Rust, Go)
Alternative Programming Languages	Rust, Go
Coolness Level	Level 4
Business Potential	1
Prerequisites	Control Flow, Stack, and Calling Conventions, Object Files, Linking, and Relocations
Key Topics	Control Flow, Stack, and Calling Conventions, Object Files, Linking, and Relocations

1. Learning Objectives

By completing this project, you will:

Explain why stack frame and unwind explorer reveals key x86-64 behaviors.
Build a deterministic tool with clear, inspectable output.
Validate correctness against a golden reference output.
Connect the tool output to ABI and architecture rules.
Unwind info exposes the real stack discipline used by compilers.

2. All Theory Needed (Per-Concept Breakdown)

Control Flow, Stack, and Calling Conventions

Fundamentals Control flow in x86-64 is built from instruction pointer changes: calls, returns, jumps, and conditional branches. The stack provides a structured way to save state, pass arguments, and return values. Calling conventions define the contract between caller and callee: which registers hold arguments, which registers must be preserved, how the stack is aligned, and where return values appear. The two dominant 64-bit ABIs are System V AMD64 (used by Linux and macOS) and the Windows x64 convention. They share ideas but differ in register usage, red zone rules, and stack shadow space. These conventions are defined in official ABI documents and OS documentation. (Sources: System V AMD64 ABI, Microsoft x64 calling convention docs)

Deep Dive The stack is a contiguous region of memory that grows downward. Every call pushes a return address and often creates a stack frame for local storage and saved registers. A function prologue typically adjusts the stack pointer, saves callee-saved registers, and sets up a frame pointer (optional). The epilogue reverses these steps and returns to the caller. This is a convention, not a requirement; optimized code can omit a frame pointer or use a leaf function that never touches the stack. Still, understanding the standard layout is critical for debugging, unwinding, and ABI interoperability.

System V AMD64 ABI defines the primary calling convention for UNIX-like systems. The first six integer or pointer arguments are passed in registers; additional arguments are passed on the stack. Return values are placed in a designated register. The stack must be aligned to a 16-byte boundary at call sites. The ABI also defines a red zone: a small region below the stack pointer that is not touched by signal handlers, allowing leaf functions to use it without adjusting the stack. This subtle rule impacts code generation and is why some stack probes are optional in user code. The ABI also specifies which registers are caller-saved and callee-saved. Caller-saved registers can be clobbered by the callee; callee-saved must be preserved across the call. Understanding these rules allows you to read disassembly and reconstruct the calling context.

Windows x64 uses a different register assignment and requires a 32-byte shadow space (home space) on the stack for the first four arguments, even if they are passed in registers. The callee can use this space to spill arguments, and the caller must allocate it. Windows x64 does not define a red zone, so leaf functions cannot safely use space below the stack pointer. This means that calling convention errors between platforms are common sources of crashes when interfacing with mixed environments or when porting low-level code.

Control flow also includes indirect calls and jumps, which use register or memory operands. These are common in virtual dispatch, function pointers, and dynamic linking. Understanding the ABI rules helps you determine whether a given register contains a valid function pointer or an argument. The stack alignment rule is critical for SIMD operations; misalignment can cause crashes or performance penalties. The ABI is therefore both a functional contract and a performance contract.

Unwinding is another piece of the puzzle. Debuggers and exception handlers need to reconstruct call stacks after a crash or during stack walking. This uses metadata (DWARF on UNIX, PDB on Windows) that describes how to restore registers and adjust the stack. Even if you are not writing that metadata, you must follow the ABI so that compilers and tools can generate it correctly.

How this fits on projects

Projects 5 and 6 are focused on calling conventions, stack layout, and unwinding.
Projects 7-8 rely on accurate control flow interpretation to map syscalls and exceptions.

Definitions & key terms

Calling convention: Contract between caller and callee.
Callee-saved: Registers preserved by the callee.
Caller-saved: Registers that may be clobbered by the callee.
Red zone: Stack space below SP reserved for leaf functions (SysV).
Shadow space: Stack space reserved for argument spilling (Windows).

Mental model diagram

CALLER STACK (higher addresses)
+----------------------------+
| argN (stack)               |
| ...                        |
| return address             | <-- pushed by call
| saved regs / locals        |
+----------------------------+
| red zone (SysV only)       |
+----------------------------+ <-- current SP

CALLER REGISTERS (SysV)
ARG1..ARG6 -> REG_A..REG_F
RETURN      -> REG_RET

How it works

Caller places arguments in registers/stack per ABI.
Caller ensures stack alignment and reserves shadow space (Windows).
Call instruction pushes return address and jumps to callee.
Callee saves required registers and sets up locals.
Callee returns value in return register.
Callee restores registers and returns to caller.

Invariants and failure modes:

Invariant: Stack alignment at call boundaries.
Failure: Misalignment breaks SIMD usage or ABI compliance.
Invariant: Callee-saved registers are preserved.
Failure: Clobbered callee-saved registers corrupt callers.

Minimal concrete example (pseudo-assembly, not real code)

# PSEUDOCODE ONLY
CALLER:
  ARG_REG1 = VAL1
  ARG_REG2 = VAL2
  ALIGN_STACK_16
  CALL FUNC_X
  RESULT = RET_REG

Common misconceptions

“Calling conventions are optional.” They are required for interoperability.
“Stack alignment only matters for performance.” It can break correctness.
“Red zone exists everywhere.” It is SysV-only and not on Windows.

Check-your-understanding questions

Why does Windows require shadow space?
Why do ABIs define caller-saved vs callee-saved registers?
What breaks if stack alignment is wrong?

Check-your-understanding answers

It gives the callee guaranteed spill space for register arguments.
It establishes a clear contract and enables efficient codegen.
SIMD operations and ABI compliance can fail or crash.

Real-world applications

ABI debugging and crash analysis
Interfacing assembly with C/C++
Reverse engineering function boundaries

Where you will apply it Projects 5, 6, 7

References

System V AMD64 ABI Draft 0.99.7
Microsoft x64 calling convention documentation
“The Art of 64-Bit Assembly, Volume 1” by Randall Hyde - Ch. 4-6

Key insights ABIs are the social contract that makes assembly code usable across compilers and OSes.

Summary Control flow and the stack are simple ideas, but ABIs make them reliable and interoperable.

Homework/Exercises to practice the concept

Draw a stack frame for a function with 2 arguments and 3 locals.
Identify which registers must be preserved in SysV and Windows.

Solutions to the homework/exercises

Include return address, saved registers, locals, and alignment padding.
SysV preserves specific callee-saved regs; Windows preserves its own set.
Object Files, Linking, and Relocations

Fundamentals Object files are containers for machine code, data, symbols, and relocation information. The linker merges object files into executables or shared libraries, resolving symbols and applying relocations. x86-64 systems primarily use ELF on Linux and macOS (Mach-O on macOS) and PE on Windows. The System V ABI defines the general ABI and the x86-64 psABI specifies details for ELF. Understanding sections, symbols, and relocations is required for interpreting binaries, debugging linking errors, and building tooling that inspects executables. (Sources: System V gABI, System V AMD64 ABI, Linux Foundation refspecs)

Deep Dive The object file is the bridge between assembly and execution. It holds code and data in sections, along with metadata that tells the linker how to connect references across compilation units. A symbol is a named addressable entity: a function, a global variable, or a section. Relocations are placeholders that tell the linker or loader to adjust addresses when the final layout is known. Without relocation, code would need fixed addresses and would not be portable or shareable.

In ELF, sections such as .text, .data, and .bss hold code and data. The section headers describe offsets, sizes, and flags. The symbol table maps symbol names to section offsets and attributes. Relocation entries refer to symbols and specify how to patch the code or data. The relocation types indicate whether a relocation is absolute, PC-relative, or uses a GOT/PLT indirection. The x86-64 psABI defines these relocation types and their semantics, which is essential for interpreting dynamic linking and position-independent code.

The linker performs symbol resolution: it decides which definition of a symbol to use and patches references accordingly. Static linking resolves all symbols at link time. Dynamic linking defers some resolution to runtime, using the dynamic loader and data structures such as the Global Offset Table (GOT) and Procedure Linkage Table (PLT). The GOT holds addresses of global symbols and is updated by the loader. The PLT provides a stub that jumps through the GOT, enabling lazy binding. This mechanism is central to shared libraries and is a common target for debugging and security analysis.

PE on Windows uses a different layout but similar ideas: sections, import tables, and relocation entries. The import table lists external functions that must be resolved at load time. Base relocations allow the loader to rebase the executable if it cannot be loaded at the preferred address. While the details differ, the mental model is the same: object files are templates, and the loader fills in the addresses.

Relocations also matter for reverse engineering. If you see a relocation against a symbol, you know that the code depends on that symbol even if the address is not fixed. This is how tools recover call graphs and identify external dependencies. It is also how you can locate jump tables, vtables, and other data-driven control flow constructs.

Finally, debugging symbols and unwind info live alongside code in the object file. These sections are optional but invaluable for debugging and profiling. Understanding them helps you build tools that can show file/line information, variable locations, and call stacks, even in optimized binaries.

How this fits on projects

Projects 9 and 10 are focused on ELF/PE parsing and relocation resolution.
Project 6 uses unwind metadata to visualize stack frames.

Definitions & key terms

Object file: Compiled code and metadata before linking.
Section: A region of an object file with a specific purpose.
Symbol: Named reference to code or data.
Relocation: A patch applied by the linker or loader.
GOT/PLT: Indirection tables for dynamic linking.

Mental model diagram

SOURCE -> OBJECT (.o) -> LINKER -> EXECUTABLE -> LOADER -> RUNNING

OBJECT:
  [ .text ] [ .data ] [ .bss ] [ .symtab ] [ .rel.* ]

LINKER:
  resolve symbols + apply relocations

LOADER:
  map segments + resolve dynamic relocations

How it works

Compiler/assembler emits object file with symbols and relocations.
Linker merges sections and resolves symbols.
Linker applies relocations or marks them for runtime.
Loader maps segments and resolves dynamic relocations.

Invariants and failure modes:

Invariant: Relocations reference valid symbols.
Failure: Missing symbols cause link errors or runtime crashes.
Invariant: Section permissions match content (code vs data).
Failure: Incorrect permissions can cause execution faults.

Minimal concrete example (pseudo-structure)

# PSEUDOCODE ONLY
SECTION .text:
  CALL SYMBOL_F
RELOCATION:
  at .text+0x10 -> SYMBOL_F (PC_REL)

Common misconceptions

“Linking is just concatenation.” It includes symbol resolution and relocation.
“GOT/PLT is only for performance.” It is required for dynamic linking.
“Object files are the final executable.” They are templates.

Check-your-understanding questions

Why do relocation entries exist at all?
What problem does the PLT solve?
How does a loader differ from a linker?

Check-your-understanding answers

Addresses are not final until link or load time.
It enables lazy binding of external functions.
The linker combines objects; the loader maps and relocates at runtime.

Real-world applications

Diagnosing link errors and symbol conflicts
Reverse engineering binary dependencies
Building binary inspection tools

Where you will apply it Projects 6, 9, 10

References

System V ABI / gABI (Linux Foundation refspecs)
System V AMD64 ABI Draft 0.99.7
“Computer Systems: A Programmer’s Perspective” by Bryant and O’Hallaron - Ch. 7

Key insights Relocations and symbols are the invisible glue that makes binaries runnable.

Summary Understanding object files and linking turns binaries from opaque blobs into structured systems.

Homework/Exercises to practice the concept

Sketch the sections of a minimal object file and label their purpose.
Explain how a call to an external function is resolved.

Solutions to the homework/exercises

Include .text, .data, .bss, .symtab, and relocation sections.
Linker or loader patches a placeholder using relocation info.

3. Project Specification

3.1 What You Will Build

A tool that reads unwind metadata and reconstructs a call stack view.

Why this teaches x86-64: Unwind info exposes the real stack discipline used by compilers.

Included:

Deterministic CLI output for a fixed input
Clear mapping between inputs and architectural meaning
A small test suite with edge cases

Excluded:

Full compiler or full disassembler coverage
Production-grade UI or packaging

3.2 Functional Requirements

Deterministic Output: Same input yields identical output.
Architecture-Aware: Output references ABI/ISA rules where relevant.
Validation Mode: Provide a compare mode against a golden output.

3.3 Non-Functional Requirements

Performance: Fast enough for small inputs and interactive use.
Reliability: Handles malformed inputs with clear errors.
Usability: Outputs are readable and documented.

3.4 Example Usage / Output

$ x64unwind demo.elf

FRAME 0: func_current
  SP=0x7fffffffe0c0  BP=0x7fffffffe0e0
  SAVED: REG_B, REG_C

FRAME 1: func_parent
  SP=0x7fffffffe110  BP=0x7fffffffe130
  SAVED: REG_B

FRAME 2: main
  SP=0x7fffffffe160  BP=0x7fffffffe180

3.5 Data Formats / Schemas / Protocols

Input format: line-oriented text or hex bytes (documented in README)
Output format: stable, human-readable report with labeled fields

3.6 Edge Cases

Empty input or missing fields
Invalid numeric values or malformed hex
Inputs that exercise maximum/minimum bounds

3.7 Real World Outcome

This section is your golden reference. Match it exactly.

3.7.1 How to Run (Copy/Paste)

Build: (if needed) make or equivalent
Run: P06-stack-frame-unwind-explorer with sample input
Working directory: project root

3.7.2 Golden Path Demo (Deterministic)

Run with the provided demo input and confirm output matches the transcript.

3.7.3 If CLI: exact terminal transcript

$ x64unwind demo.elf

FRAME 0: func_current
  SP=0x7fffffffe0c0  BP=0x7fffffffe0e0
  SAVED: REG_B, REG_C

FRAME 1: func_parent
  SP=0x7fffffffe110  BP=0x7fffffffe130
  SAVED: REG_B

FRAME 2: main
  SP=0x7fffffffe160  BP=0x7fffffffe180

4. Solution Architecture

4.1 High-Level Design

INPUT -> PARSER -> MODEL -> RENDERER -> REPORT

4.2 Key Components

Component	Responsibility	Key Decisions
Parser	Turn input into structured records	Strict vs permissive parsing
Model	Apply ISA/ABI rules	Deterministic state transitions
Renderer	Produce readable output	Stable formatting

4.4 Data Structures (No Full Code)

Record: holds one instruction/event with decoded fields
State: represents register/flag or address state
Report: list of formatted output lines

4.4 Algorithm Overview

Key Algorithm: Parse and Evaluate

Parse input into records.
Apply rules to update state.
Render the state and summary output.

Complexity Analysis:

Time: O(n) over input records
Space: O(n) for report output

5. Implementation Guide

5.1 Development Environment Setup

# Ensure basic tools are installed
# build-essential or clang, plus objdump/readelf if needed

5.2 Project Structure

project-root/
├── src/
│   ├── main.*
│   ├── parser.*
│   └── model.*
├── tests/
│   └── test_cases.*
└── README.md

5.3 The Core Question You’re Answering

How can a debugger reconstruct a call stack without executing the code?

5.4 Concepts You Must Understand First

Stack frames
- How do frames store return addresses and saved registers?
- Book Reference: “The Art of 64-Bit Assembly, Volume 1” - Ch. 4-6
Object file metadata
- Where is unwind info stored in ELF?
- Book Reference: “Computer Systems: A Programmer’s Perspective” - Ch. 7

5.5 Questions to Guide Your Design

Metadata parsing
- Which sections hold unwind data?
- How will you interpret rules for stack pointer recovery?
Visualization
- How will you present each frame to be human-readable?
- How will you handle missing frame pointers?

5.6 Thinking Exercise

Frame Reconstruction

Given a stack pointer and a saved base pointer, draw the frame layout and indicate where the return address lives.

Questions to answer:

How would a debugger find the previous frame?
Why do compilers sometimes omit frame pointers?

5.7 The Interview Questions They’ll Ask

“What is unwind metadata used for?”
“How does a debugger walk a stack without frame pointers?”
“Why would a compiler omit a frame pointer?”
“What is the difference between .eh_frame and .debug_frame?”
“How does exception unwinding differ from stack tracing?”

5.8 Hints in Layers

Hint 1: Starting Point Use readelf or llvm-dwarfdump to locate unwind sections and inspect them.

Hint 2: Next Level Build a parser that maps unwind rules to register restore operations.

Hint 3: Technical Details Simulate the unwind process using a synthetic register snapshot.

Hint 4: Tools/Debugging Compare your reconstructed frames with gdb backtraces.

5.9 Books That Will Help

Topic	Book	Chapter
Debugging	“The Art of Debugging with GDB”	Ch. 5-7
Linking and symbols	“Computer Systems: A Programmer’s Perspective”	Ch. 7

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Goals:

Parse input format
Produce a minimal output Tasks:
1. Define input grammar and example files.
2. Implement a minimal parser and renderer. Checkpoint: Golden output matches a small input.

Phase 2: Core Functionality (1 week)

Goals:

Implement full rule set
Add validation and errors Tasks:
1. Implement rule engine for core cases.
2. Add error handling for invalid inputs. Checkpoint: All core tests pass.

Phase 3: Polish & Edge Cases (2-3 days)

Goals:

Add edge-case coverage
Improve output readability Tasks:
1. Add edge-case tests.
2. Refine output formatting and summary. Checkpoint: Output matches golden transcript for all cases.

5.11 Key Implementation Decisions

Decision	Options	Recommendation	Rationale
Input format	Text, JSON	Text	Easiest to audit and diff
Output format	Plain text, JSON	Plain text	Matches CLI tooling

6. Testing Strategy

6.1 Test Categories

Category	Purpose	Examples
Unit Tests	Validate parsing and rule application	Valid/invalid inputs
Integration Tests	End-to-end output comparison	Golden transcripts
Edge Case Tests	Stress unusual inputs	Empty input, max values

6.2 Critical Test Cases

Minimal Input: One record, verify output.
Boundary Values: Largest/smallest values.
Malformed Input: Ensure clean error messages.

6.3 Test Data

INPUT: sample_min.txt
EXPECTED: matches golden transcript

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall	Symptom	Solution
Wrong assumptions	Output mismatches	Re-read ABI/ISA rules
Off-by-one parsing	Missing fields	Add explicit length checks
Ambiguous output	Hard to verify	Add labels and separators

Project-specific pitfalls

Problem 1: “Stack frames look inconsistent”

Why: Unwind rules were misinterpreted or missing.
Fix: Cross-check with gdb and confirm register restore rules.
Quick test: Use a binary compiled with frame pointers enabled.

7.2 Debugging Strategies

Golden diffing: Use diff to compare outputs line by line.
State logging: Print intermediate state after each step.

7.3 Performance Traps

Avoid over-optimizing; correctness and determinism matter most.

8. Extensions & Challenges

8.1 Beginner Extensions

Add a new input case and golden output
Add a summary line with counts

8.2 Intermediate Extensions

Add JSON output mode
Add validation warnings for suspicious inputs

8.3 Advanced Extensions

Support additional ABI or instruction variants
Integrate with a real binary to collect inputs

9. Real-World Connections

9.1 Industry Applications

Profilers and tracers: Use similar decoding and state models.
Security analysis: Use precise ABI knowledge to interpret crashes.

objdump: reference tool for binary inspection.
llvm-objdump: LLVM-based disassembly and inspection.

9.3 Interview Relevance

ABI and calling conventions are common systems interview topics.
Explaining decoding and linking demonstrates low-level fluency.

10. Resources

10.1 Essential Reading

Intel 64 and IA-32 Architectures Software Developer’s Manual - ISA reference
System V AMD64 ABI Draft 0.99.7 - calling convention rules

10.2 Video Resources

Vendor and university lectures on x86-64 and ABIs (search official channels)

Project 6: Stack Frame and Unwind Explorer

Quick Reference

1. Learning Objectives

2. All Theory Needed (Per-Concept Breakdown)

Control Flow, Stack, and Calling Conventions

Object Files, Linking, and Relocations

3. Project Specification

3.1 What You Will Build

3.2 Functional Requirements

3.3 Non-Functional Requirements

3.4 Example Usage / Output

3.5 Data Formats / Schemas / Protocols

3.6 Edge Cases

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

3.7.2 Golden Path Demo (Deterministic)

3.7.3 If CLI: exact terminal transcript

4. Solution Architecture

4.1 High-Level Design

4.2 Key Components

4.4 Data Structures (No Full Code)

4.4 Algorithm Overview

5. Implementation Guide

5.1 Development Environment Setup

5.2 Project Structure

5.3 The Core Question You’re Answering

5.4 Concepts You Must Understand First

5.5 Questions to Guide Your Design

5.6 Thinking Exercise

5.7 The Interview Questions They’ll Ask

5.8 Hints in Layers

5.9 Books That Will Help

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Phase 2: Core Functionality (1 week)

Phase 3: Polish & Edge Cases (2-3 days)

5.11 Key Implementation Decisions

6. Testing Strategy

6.1 Test Categories

6.2 Critical Test Cases

6.3 Test Data

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

7.2 Debugging Strategies

7.3 Performance Traps

8. Extensions & Challenges

8.1 Beginner Extensions

8.2 Intermediate Extensions

8.3 Advanced Extensions

9. Real-World Connections

9.1 Industry Applications

9.2 Related Open Source Projects

9.3 Interview Relevance

10. Resources

10.1 Essential Reading

10.2 Video Resources