8.3 Runtime Environments: Activation Records, Storage Allocation & Parameter Passing

Back to DBMS Notes

📚Module 01Runtime Environments & Storage Allocation⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Office Desk Stack and Call Logs

Imagine an executive managing an engineering firm:

• The Call Stack: Whenever the manager delegates a sub-task to a specialist, the specialist arrives and places a dedicated folder (Activation Record / Stack Frame) on top of the desk. When finished, they remove their folder, exposing the manager's desk exactly as it was left.
• Dynamic Link (The Return Phone Number): A bookmark inside the folder noting: "When I finish this sub-task, hand the desk back to whoever called me (the runtime caller)."
• Static Link (The Corporate Org Chart): A pointer pointing to the department director who authored the departmental rulebook (lexical enclosing scope), regardless of who dialed the phone!
• Call by Value vs Reference: Handing the specialist a photocopied paper sheet (Call by Value) versus handing them the physical keys to the master filing cabinet (Call by Reference). If the specialist spills coffee on the photocopy, the master cabinet is safe. If they spill coffee in the master cabinet, the company's ground-truth data is permanently altered!

💻 Bridging to Computer Science: Virtual Address Spaces & Call Frame Lifecycles

During compilation, source variables and procedures are mapped onto a target architecture's virtual memory space:

• The compiler partitions the virtual address space into distinct segments: Code (Text), Static Data, Heap, and Stack.
• Dynamic procedure invocations require allocating an Activation Record (AR) or Stack Frame to store parameters, return addresses, saved registers, local variables, and temporaries.
• Resolving non-local identifiers requires either pointer chains (Static Links) or an indexed pointer table (Displays).
• Transmission of arguments across procedure boundaries is governed by parameter-passing protocols: Call by Value, Call by Reference, Call by Value-Result, and Call by Name.

📑Table of Contents

• 🏗️ Architectural Foundations: Storage Allocation Strategies (Static vs Stack vs Heap)
  • Comparative Storage Allocation Paradigms
• 🧱 Activation Record (Stack Frame) Anatomy
  • 🔍 Field Mechanics & Responsibilities
• 🌐 Non-Local Variable Resolution: Static Links vs Displays
  • 1️⃣ Static Links (Access Links)
  • 2️⃣ Display Registers
• 🔄 Parameter Passing Mechanisms
  • 1️⃣ Call by Value (Pass by Copy)
  • 2️⃣ Call by Reference (Pass by Pointer / Address)
  • 3️⃣ Call by Value-Result (Copy-In / Copy-Out)
  • 4️⃣ Call by Name (Algol 60 Lazy Substitution)
• 🏭 Real-World Production Context: System V AMD64 ABI & Calling Conventions
• 📐 Numerical Applications & Worked Examples
  • Example 1: Output Comparison Across All Parameter Passing Modes
  • Example 2: Jensen's Device and Call by Name Dynamic Re-Evaluation
  • Example 3: Static Link Traversal vs Display Resolution
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: Storage Allocation Strategies (Static vs Stack vs Heap)

The compiler organizes the target machine's virtual address space into specialized segments managing three distinct storage classes:

Process Virtual Address Space Architecture

Standard 4-Section memory layout from High Memory down to Low Memory

High Memory

Stack Segment (Grows Downward ⬇)

📚

LIFO call stack containing activation records, local variables, and saved CPU registers.

Activation RecordsDynamic LinksSaved RBP/RSPTemporaries

↓unallocated growth buffer

Dynamic

Heap Segment (Grows Upward ⬆)

📦

Dynamic memory allocation managed at runtime (malloc, free, new, garbage collector).

Dynamic ArraysLinked ObjectsPersistent Structs

↓managed above

Static

Data / BSS Segment (Fixed Size)

🏛️

Global variables, static constants, and uninitialized BSS buffers fixed at compile time.

Global VariablesStatic BuffersString Literals

↓precedes

Low Memory

Code / Text Segment (Base 0x00000000)

⚡

Read-only compiled machine instructions with hardware page protection.

Machine InstructionsRead-Only Page TablesInterrupt Vectors

Comparative Storage Allocation Paradigms

Storage Allocation Paradigms: Static vs Stack vs Heap

Contrasting allocation timing, lifetime predictability, and execution overhead

Static

Static Storage Allocation

🏛️

Dominant Architecture / DomainGlobal Variables, Early Fortran 77, Embedded Microcontrollers

• •Memory addresses are permanently bound at compile/link time.
• •Zero runtime allocation or deallocation overhead.
• •Variables retain values across multiple procedure invocations.
• •Cannot support recursion: all calls share identical memory cells!

"Compile-time certainty with zero recursion capability."

Stack

Stack-Based Dynamic Allocation

📚

Dominant Architecture / DomainC, C++, Java, Rust Local Variables, Recursive Procedures

• •Allocated and freed in strict Last-In-First-Out (LIFO) call order.
• •Naturally supports unbounded recursive function invocations.
• •Allocated at negligible cost via single stack pointer adjustments.
• •Lifetimes are strictly bound to function entry and exit points.

"LIFO discipline enables elegant recursive scoping at hardware speed."

---

🧱 Activation Record (Stack Frame) Anatomy

An Activation Record is a contiguous block of memory allocated on the call stack every time a procedure or function is invoked. It contains all runtime data necessary to manage procedure execution and resume the caller upon return.

The 7 Canonical Fields of an Activation Record

Stack frame anatomy from High Memory (caller context) to Low Memory (top of stack)

High Memory

1. Actual Parameters & Arguments

📥

Values or pointer references pushed by the caller prior to function invocation.

Argument 1Argument 2Passed Structs

↓precedes

Output

2. Returned Value Slot

📤

Dedicated memory reserved for the callee to return its computed result to the caller.

Scalar ResultPointer / Struct Reference

↓precedes

Dynamic Link

3. Control Link (Dynamic Link)

🔄

Pointer to the base of the calling procedure's activation record (Saved Frame Pointer RBP).

Saved Caller RBPFrame Restoration Target

↓precedes

Static Link

4. Access Link (Static Link)

🔗

Pointer to the activation record of the lexically enclosing procedure in source text.

Lexical Scope ResolutionNested Function Access

↓precedes

State

5. Saved Machine Status

💾

Return address (Program Counter RIP) and callee-saved CPU general-purpose registers.

Return Address (RIP)Saved Callee Registers (RBX, R12-R15)

↓precedes

Local Scope

6. Local Variables & Data Arrays

📦

Scalars, structures, and arrays declared locally within the procedure body.

Local PrimitivesStack Buffers

↓precedes

Low Memory

7. Temporaries & Evaluation Stack

⚡

Temporary locations for evaluating complex arithmetic expressions (Top of Stack RSP).

Expression TempsAligned Stack Boundary

🔍 Field Mechanics & Responsibilities

1. Actual Parameters: Pushed by the caller or passed in registers; formal parameters inside the callee reference these offsets.
2. Returned Value: Memory location where the callee places its output so the caller can read it immediately following stack unwinding.
3. Control Link (Dynamic Link): Points to the activation record of the caller. When the callee returns, the runtime restores the stack frame pointer via:

$$\text{RSP} = \text{RBP}; \quad \text{RBP} = \text{Memory}[\text{Dynamic Link}]$$

4. Access Link (Static Link): Points to the activation record of the immediate lexical parent in nested block-structured languages (Pascal, Ada, Python).
5. Saved Machine Status: Contains the return instruction pointer (%rip) and contents of registers that must remain invariant across the call.
6. Local Data: Stores automatic local variables whose sizes are known at compile time.
7. Temporaries: Temporary variables generated during intermediate three-address code evaluation when available CPU registers are exhausted.

---

🌐 Non-Local Variable Resolution: Static Links vs Displays

When a procedure $P$ accesses a variable $x$ declared in an outer enclosing procedure $Q$, how does the runtime resolve the address of $x$?

1️⃣ Static Links (Access Links)

Each activation record contains a pointer to the most recent activation record of its immediate lexical parent.

• If procedure $P$ is nested at depth $d_P$, and accesses variable $x$ declared at nesting depth $d_Q$:
  • The runtime must traverse $(d_P - d_Q)$ static links to reach $Q$'s frame.
  • The variable is accessed using a fixed compile-time offset within that frame:

$$\text{Address}(x) = \text{FramePtr}_{Q} + \text{Offset}(x)$$

• Complexity Trade-Off: Accessing deeply nested variables requires $O(k)$ pointer dereferences, introducing memory traversal latency.

2️⃣ Display Registers

To achieve $O(1)$ constant-time non-local access, compilers maintain an auxiliary array of pointers called a Display:

• $\text{Display}[d]$ always stores a pointer to the most recent activation record of the procedure at lexical nesting depth $d$.
• Accessing any non-local variable at depth $d$ requires a single array lookup and offset addition:

$$\text{Address}(x) = \text{Display}[d] + \text{offset}(x)$$

• Maintenance Cost: When a procedure at depth $d$ is entered, it saves the old value of $\text{Display}[d]$ in its activation record and updates $\text{Display}[d]$ to its own frame pointer. On return, it restores the previous value.

---

🔄 Parameter Passing Mechanisms

How arguments are passed between caller and callee defines a programming language's runtime semantics and data-sharing properties:

Architecture Flow

The 4 Foundational Parameter Passing Protocols

From pass-by-copy safety to call-by-name lazy evaluation

📋Value

Call by Value

Caller evaluates actual expression; passes a distinct local copy to callee.

→

Isolated Copy

🔗Reference

Call by Reference

Caller passes the actual memory address (l-value). Callee mutates original cell directly.

→

Direct Alias

🔄Copy-Restore

Call by Value-Result

Pass copy in on call; write modified copy back to caller variable upon procedure return.

→

Deferred Writeback

📜Name

Call by Name

Textual macro substitution evaluated lazily on every access via an anonymous helper thunk.

1️⃣ Call by Value (Pass by Copy)

• The caller evaluates the actual parameter expression and places its r-value into the callee's formal parameter slot.
• Assignments inside the callee modify only the callee's local memory cell.
• The caller's variables remain strictly isolated and protected from side effects.

2️⃣ Call by Reference (Pass by Pointer / Address)

• The caller passes the memory address (l-value) of the actual variable.
• Any assignment to the formal parameter mutates the caller's actual variable immediately.
• Enables side effects and avoids copying large structures, but introduces aliasing risks when multiple parameters point to the same variable.

3️⃣ Call by Value-Result (Copy-In / Copy-Out)

• A two-phase hybrid mechanism:
  1. Copy-In: On procedure entry, actual values are copied into local formal variables.
  2. Local Execution: Operations modify the local copies.
  3. Copy-Out: Upon return, final values of formal parameters are copied back into the caller's actual variables.
• Aliasing Anomaly: If two formal parameters represent the same caller variable (e.g., swap(x, x)), the final value of $x$ depends strictly on the compiler's copy-out evaluation order (left-to-right vs. right-to-left)!

4️⃣ Call by Name (Algol 60 Lazy Substitution)

• The actual argument expression is textually substituted into the callee's body wherever the formal parameter occurs.
• Evaluated lazily on every single access.
• Implemented by compiling an anonymous parameterless subroutine called a Thunk that evaluates the argument expression within the caller's lexical context.

---

🏭 Real-World Production Context: System V AMD64 ABI & Calling Conventions

In modern 64-bit production environments (Linux, macOS, BSD on x86-64):

• Register Argument Passing: Allocating and reading arguments on memory stacks incurs memory bus stalls. The System V AMD64 ABI mandates passing the first 6 integer or pointer arguments directly in high-speed hardware CPU registers:
  1. RDI (First Argument)
  2. RSI (Second Argument)
  3. RDX (Third Argument)
  4. RCX (Fourth Argument)
  5. R8 (Fifth Argument)
  6. R9 (Sixth Argument)
• Arguments 7 and beyond are pushed onto the stack in right-to-left order.
• Floating-point arguments are passed in vector registers XMM0 through XMM7.
• 16-Byte Stack Alignment: The ABI dictates that RSP + 8 must be a multiple of 16 immediately before a call instruction is executed. The call instruction pushes the 8-byte return address, ensuring that upon callee entry, RSP is precisely 16-byte aligned for vector SSE/AVX memory operations.

---

📐 Numerical Applications & Worked Examples

Example 1: Output Comparison Across All Parameter Passing Modes

Consider the following program written in pseudo-C syntax:

int x = 10;

void swap(int a, int b) {
    x = x + 1;
    a = a + 5;
    b = b + 10;
}

int main() {
    x = 10;
    swap(x, x);
    print(x);
    return 0;
}

Determine the printed value of variable $x$ under:

1. Call by Value
2. Call by Reference
3. Call by Value-Result (under both left-to-right and right-to-left copy-out orders)

Step-by-Step Analytical Trace:

1. Call by Value Trace:

   • In main(): $x = 10$.
   • swap(x, x) is invoked:
     • Formal parameter $a = 10$, $b = 10$ (isolated local stack cells).
   • Inside swap():
     • $x = x + 1 \implies$ Global $x$ becomes $10 + 1 = 11$.
     • $a = a + 5 \implies a = 15$ (local to swap).
     • $b = b + 10 \implies b = 20$ (local to swap).
   • On return:
     • Local variables $a$ and $b$ are deallocated.
     • Global $x$ remains $11$.
   • Printed Result: 11

2. Call by Reference Trace:

   • In main(): $x = 10$.
   • swap(x, x) is invoked:
     • Both formal parameters $a$ and $b$ receive the address of $x$ ($\&x$).
     • Thus, $a$, $b$, and global $x$ are exact aliases for the same physical memory cell!
   • Inside swap():
     • Line 1: $x = x + 1 \implies x = 10 + 1 = 11$.
     • Line 2: $a = a + 5 \implies x = 11 + 5 = 16$.
     • Line 3: $b = b + 10 \implies x = 16 + 10 = 26$.
   • On return:
     • Memory cell for $x$ contains $26$.
   • Printed Result: 26

3. Call by Value-Result (Copy-In / Copy-Out) Trace:

   • In main(): $x = 10$.
   • On entry to swap(x, x):
     • Copy-In: $a = 10$, $b = 10$.
   • Inside swap():
     • $x = x + 1 \implies$ Global $x$ becomes $11$.
     • $a = a + 5 = 15$.
     • $b = b + 10 = 20$.
   • On return (Copy-Out Phase):
     • Case A: Left-to-Right Copy-Out:
       • First restore $a \implies x = a = 15$.
       • Next restore $b \implies x = b = 20$ (overwrites 15!).
       • Final $x = \mathbf{20}$.
     • Case B: Right-to-Left Copy-Out:
       • First restore $b \implies x = b = 20$.
       • Next restore $a \implies x = a = 15$ (overwrites 20!).
       • Final $x = \mathbf{15}$.
   • Notice that the intermediate update to global $x$ ($x = 11$) was completely obliterated during the copy-out phase!

---

Example 2: Jensen's Device and Call by Name Dynamic Re-Evaluation

Consider the following program evaluated under Call by Name:

int i = 1;
int a[3] = {10, 20, 30}; // 1-indexed array: a[1]=10, a[2]=20, a[3]=30

void modify(int index, int val) {
    index = index + 1;
    val = val + 5;
}

int main() {
    modify(i, a[i]);
    print(a[1], a[2]);
    return 0;
}

Determine the final values of $a[1]$ and $a[2]$ printed by main().

Step-by-Step Analytical Trace:

Under Call by Name, formal parameter names are textually substituted with the caller's expressions via thunks:

• index is bound to the expression i.
• val is bound to the expression a[i] (evaluated dynamically on each access!).

1. Inside modify():
   • Statement 1: index = index + 1:
     • Expands to: $i = i + 1$.
     • Since $i$ was $1$, variable $i$ becomes $2$.
   • Statement 2: val = val + 5:
     • Expands to: $a[i] = a[i] + 5$.
     • Dynamic Thunk Re-evaluation: Because variable $i$ is now $2$, the expression $a[i]$ evaluates to $a[2]$, not $a[1]$!
     • Therefore: $a[2] = a[2] + 5 = 20 + 5 = 25$.
2. In main():
   • $a[1]$ was never modified: $a[1] = 10$.
   • $a[2]$ was modified: $a[2] = 25$.

• Printed Result: 10, 25

---

Example 3: Static Link Traversal vs Display Resolution

Suppose a program has four nested procedures: $P_1$ (depth 1), $P_2$ (depth 2), $P_3$ (depth 3), and $P_4$ (depth 4), where $P_4$ is lexically enclosed in $P_3$, $P_3$ in $P_2$, and $P_2$ in $P_1$.

Suppose during execution, $P_4$ references variable $z$ declared in $P_1$.

1. How many static link dereferences are required to access $z$?
2. How many memory accesses are required using a Display?

Step-by-Step Analytical Trace:

1. Static Link Resolution:
   • Number of links to traverse $= \text{depth}(P_4) - \text{depth}(P_1) = 4 - 1 = 3$.
   • Memory operations:
     1. Dereference $P_4$'s static link to reach $P_3$'s frame.
     2. Dereference $P_3$'s static link to reach $P_2$'s frame.
     3. Dereference $P_2$'s static link to reach $P_1$'s frame.
     4. Access $z$ at $\text{FramePtr}_{P_1} + \text{offset}(z)$.
   • Total pointer traversals: 3 static link traversals ($4$ memory reads total).
2. Display Resolution:
   • Display lookup: Read $\text{Display}[1]$ (stores $P_1$'s frame pointer directly).
   • Access $z$ at $\text{Display}[1] + \text{offset}(z)$.
   • Total accesses: 1 Display read + 1 memory read ($O(1)$ constant time).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why can a language that uses purely static memory allocation not support recursion?"
Key Focus Points:

• In static allocation, each variable and procedure has a single, fixed memory location bound at compile or link time.
• If a procedure calls itself recursively, the new activation writes its parameters and local variables into the exact same memory cells as the caller activation, destroying the caller's state.
• Supporting recursion requires a dynamic stack, where each activation receives its own distinct activation record on the call stack.

Question 2: "What is the difference between a Dynamic Link (Control Link) and a Static Link (Access Link)?"
Key Focus Points:

• Dynamic Link: Points to the activation record of the caller in time. It reflects the dynamic call graph ($A \to B \to C$) and is used to restore the caller's stack frame upon return.
• Static Link: Points to the activation record of the lexically enclosing procedure in source text space. It reflects the static syntactic nesting structure and is used to access non-local variables.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Returning the address of a local stack variable in C/C++.
Answer: Catastrophic dangling pointer. When a function returns, its activation record is popped and its stack memory is reclaimed. Returning &local_var produces a pointer to unallocated memory. Any subsequent function call will overwrite that memory segment, causing erratic data corruption or segmentation faults.

Trap 2: Assuming Call by Value-Result is identical to Call by Reference.
Answer: False under aliasing. When two parameters reference the same variable (or one parameter references a global variable modified in the procedure), Call by Reference mutates the variable immediately in place. Call by Value-Result works on isolated local copies and writes them back only upon return. If copy-back order changes, the resulting value changes.

Trap 3: Stack smashing via buffer overflow.
Answer: Security vulnerability. In an activation record, local array buffers are situated adjacent to the saved frame pointer and return address. Unbounded writes (e.g. strcpy) overwrite the saved return address. When the function executes ret, the CPU jumps to attacker-controlled instructions. Modern compilers mitigate this using Stack Canaries (-fstack-protector).

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic8.2 Principal Sources of Code OptimizationNext Topic →8.4 Target Code Generation, Register Allocation & Peephole Optimization