Worked examples — Stack frames — how function calls work at the memory level

This page is the exhaustive worked-examples lab for the parent note on stack frames. The parent taught you the machinery: a frame is a private scratch desk holding locals, a saved base pointer, and a return address, and desks pile up LIFO (last-in, first-out). Here we hammer that machinery against every case class — every direction the stack can grow, every degenerate call, the deepest recursion, the buggy pointer, and an exam trap.

If any word below feels unfamiliar, it was built in the parent. Two you will use constantly:

• Stack pointer (SP) ::: the register holding the address of the top (newest byte) of the stack.
• Base pointer (BP) ::: a fixed reference address inside the current frame, so locals sit at constant offsets even while SP moves.

---

The scenario matrix

Before working examples, let us list every kind of situation a stack frame can face. Each later example is tagged with the cell it covers, and together they fill the whole grid.

#	Case class	What is special about it	Covered by
A	Single flat call (baseline)	one caller, one callee, no nesting	Example 1
B	Nested calls (call inside a call)	two live frames stacked	Example 2
C	Downward-growing stack, address arithmetic	compute real offsets from BP	Example 3 (figure)
D	Upward-growing stack (opposite sign)	some CPUs / textbooks flip direction	Example 4 (figure)
E	Zero-work / degenerate frame	function with no locals, no args	Example 5
F	Deep recursion → limiting behaviour	frames pile until stack overflow	Example 6
G	Dangling pointer to a freed local	pointer outlives its frame	Example 7 (figure)
H	Real-world word problem	measure real stack depth in bytes	Example 8
I	Exam-style twist (ARM link register)	return address NOT on stack first	Example 9 (figure)
J	Frame alignment / padding	total rounded to a 16-byte boundary	Example 10
K	Optimised-away frame (tail call, register args, shadow space)	conventions that skip or reshape the frame	Example 11

We track the stack explicitly in bytes wherever numbers appear, so every claim is checkable.

---

Example 1 — the baseline single call (cell A)

1. Push the return address. CALL subtracts 8: $SP=1000-8=992$. Why this step? On x86 CALL stores the return address on the stack so f knows where to jump back to; a push moves SP toward lower addresses.
2. Push saved BP. Prologue subtracts 8: $SP=992-8=984$. Why this step? f must save main's BP before overwriting BP with its own, or main loses its frame reference.
3. Set BP = SP. Now $BP=984$. This is f's anchor; it does not move SP. Why this step? Locals will be addressed relative to this fixed point.
4. Carve 16 bytes of locals. $SP=984-16=968$. Why this step? Local variables need reserved space below BP on a downward stack.

Answer: inside f, $SP=968$. Frame cost $=1000-968=32$ bytes. The frame therefore spans the byte range $[968,1000)$ — everything from the new top up to (but not including) where main's frame resumes.

---

Example 2 — nested calls, two live frames (cell B)

1. f's frame pushed. $SP=2000-24=1976$. Why this step? Calling f builds f's frame on top of (below) main's.
2. g's frame pushed. $SP=1976-24=1952$. Why this step? f calling g builds another frame below f's. Now three frames are live at once — this is the deepest moment.
3. g returns. SP resets up by 24: $SP=1952+24=1976$. Why this step? Cleanup is just moving SP back; g's desk vanishes.
4. f returns. $SP=1976+24=2000$, back inside main. Why this step? LIFO — g (last created) died first, then f.

Answer: deepest $SP=1952$; destruction order is g, then f, then main (reverse of creation).

---

Example 3 — real offset arithmetic on a downward stack (cell C)

1. local0 sits 8 below BP. $500-8=492$. So ${\text{offset}}_0=8$. Why this step? First local pushed after BP goes to the next lower 8-byte slot.
2. local1 sits 16 below BP. $500-16=484$. So ${\text{offset}}_1=16$. Why this step? Second local is one word further down.
3. arg0 sits 16 above BP. $500+16=516$. So $\text{offset}=16$ (8 for saved BP + 8 for return address in between). Why this step? Arguments were pushed before the call, so they live above BP; you must step over saved BP and the return address to reach them.

Answer: local0 @ 492, local1 @ 484, arg0 @ 516.

---

Example 4 — an UPWARD-growing stack (cell D)

1. Push return address. SP increases by 8: $SP=700+8=708$. Why this step? "Grows upward" means each push adds to SP instead of subtracting.
2. Push saved BP. SP increases by 8 again: $SP=708+8=716$. Why this step? Direction of growth does not excuse you from saving the caller's BP — it is mandatory on every architecture, or the caller loses its frame reference. Skipping it was the flaw an earlier draft had.
3. Set BP = SP = 716, then carve locals upward. $SP=716+16=732$. Why this step? Locals now live above BP, so the formula flips to ${\text{addr(local}}_k)=BP+{\text{offset}}_k$.
4. local0 is at $716+0=716$, local1 at $716+8=724$. Why this step? Because growth is upward, higher offset = higher address.

Answer: $SP=732$; locals sit above BP; the sign in the address formula flips to +; frame cost $=8+8+16=32$ bytes — same total as Example 1, only the direction reversed.

---

Example 5 — the degenerate frame: no args, no locals (cell E)

1. CALL still pushes the 8-byte return address. $SP=300-8=292$. Why this step? Even a no-op must know where to come back — the return address is non-optional.
2. Prologue may be omitted. A smart compiler skips saving BP and carving locals because there is nothing to anchor. Why this step? No locals ⇒ no need for a stable BP reference ⇒ the prologue is pure overhead and gets removed (this is "frame-pointer omission").
3. RET pops the return address. $SP=292+8=300$, fully restored. Why this step? The single push is undone by the single pop.

Answer: minimum stack change is 8 bytes (just the return address); BP is not needed.

---

Example 6 — deep recursion and the overflow limit (cell F)

1. Each level costs 512 bytes and none are freed mid-recursion. The deepest point holds all frames simultaneously. Why this step? Recursion only frees a frame after its call returns; at maximum depth every frame is still live.
2. Divide total by per-frame cost. $\frac{8388608}{512}=16384$ levels. Why this step? Total budget ÷ cost per frame = how many fit before we run out of region.
3. Level 16385 pushes past the boundary → stack overflow. Why this step? Once SP crosses the guard page, the OS faults; the parent called this "too deep ⇒ stack overflow."

Answer: about 16384 levels; the next one overflows.

---

Example 7 — dangling pointer to a freed local (cell G)

1. After bad returns, SP moves back up to 1000. The entire range $[968,1000)$ — including address 976 — is no longer reserved. Why this step? Cleanup = resetting SP to where it was before the call; bad's whole 32-byte frame is logically destroyed the instant it returns, not just part of it.
2. p still points at 976. The pointer value is unchanged — it just aims at unowned memory now. Why this step? Returning &local copies the address, and the address survives even though the storage does not.
3. Calling g rebuilds a 32-byte frame in the same region $[968,1000)$. Because g starts from $SP=1000$ and pushes 8 (retaddr) + 8 (saved BP) + 16 (locals) = 32 bytes, its frame lands on exactly the addresses bad just vacated — address 976 now belongs to g. Why this step? The stack recycles the same low addresses for the next frame; identical size ⇒ identical footprint ⇒ a guaranteed collision at 976.
4. *p now reads whatever g wrote at 976 — a saved BP byte or a local of g, not 42. Why this step? The 42 was overwritten; reading it is undefined behaviour — it might read 42 by luck before any call, garbage after.

Answer: *p is undefined; commonly 42 immediately after return (bytes untouched), then garbage once g's 32-byte frame reuses $[968,1000)$ and overwrites 976. Fix: return by value or malloc (heap).

---

Example 8 — real-world word problem: measuring depth in bytes (cell H)

1. Read both stack pointers as plain numbers. $0x7fffffffe200$ is "top of main", $0x7fffffffe040$ is "deepest point". Why this step? "How deep" is a distance between two addresses, and distance is a subtraction — so we must treat the two SP values as ordinary integers we can subtract, not as opaque labels.
2. Notice the two addresses share every high bit. Both are 0x7fffffffe0__; they differ only in the final three hex digits, 200 versus 040. Since the high halves are identical, subtracting them gives zero there, and no borrow can climb into that shared prefix. Why this step? When two numbers agree on their leading bits, all of the difference lives in the low bits — so we may subtract just the differing tails and safely ignore the identical prefix.
3. On a downward stack the top address is the larger one, so depth = top − deep. Compute the tails: $0x200-0x040=0x1c0$. Why this step? The stack grew downward from main, so used bytes stretch from the deep (small) address up to main's (large) start; the positive difference is the number of bytes in that span.
4. Convert $0x1c0$ to decimal. $0x1c0=1\times 16^2+12\times 16^1+0=256+192+0=448$. Why this step? Hex is base-16; each digit is weighted by a power of 16, and $c$ is the hex digit for 12.

Answer: the call chain is 448 bytes (0x1c0) deep at that moment.

---

Example 9 — exam twist: ARM link register (cell I)

1. BL g puts g's return address in LR. Stack unchanged so far: $SP=4000$. Why this step? ARM's branch-and-link is a register write, not a push — cheaper than x86's memory push, so the first hop of the return address is a register, not the stack.
2. g is about to BL h, which overwrites LR. So g first pushes (spills) its LR to the stack: $SP=4000-8=3992$. Why this step? BL h will overwrite LR with h's return address. If g did not save LR first, calling h would destroy g's own return address and g could never get back to f. Spilling to the stack parks it somewhere BL h cannot touch.
3. g runs, then before returning it restores LR by popping the spilled value back: $SP=3992+8=4000$. Why this step? g needs its return address in LR (or on the stack for RET) to branch back to f; the epilogue undoes the spill, and SP returns to where it started.
4. A leaf function (one that calls nobody) skips steps 2–3 entirely. It keeps its return address in LR the whole time and never touches the stack for it. Why this step? A leaf never executes a second BL, so LR is never clobbered — there is nothing to protect, so no spill is needed. This is exactly why leaf functions are cheaper on ARM.

Answer: after the spill, $SP=3992$ (and back to $4000$ after the matching restore); the spill is mandatory for non-leaf functions only, because only they issue an inner BL that would overwrite LR.

---

Example 10 — frame alignment and padding (cell J)

1. Round the local size up to the next 16-byte multiple. $20\to 32$ (since $16<20\le 32$). The extra $32-20=12$ bytes are padding — unused filler. Why this step? The convention demands SP stay 16-aligned so that SIMD instructions (which require aligned memory) and the next call work correctly. Carving a non-multiple of 16 would misalign SP.
2. Subtract the rounded size. $SP=8016-32=7984$. Why this step? Downward stack ⇒ carving locals subtracts; we subtract the padded 32, not the raw 20.
3. Check alignment. $7984÷16=499$ exactly, so $7984$ is 16-aligned. ✓ Why this step? Confirms the padding did its job — SP lands on a 16-byte boundary, ready for the next call.

Answer: the compiler subtracts 32 bytes (20 needed + 12 padding); final $SP=7984$, still 16-aligned.

---

Example 11 — frames that get optimised away or reshaped (cell K)

1. (a) Tail call reuses f's frame instead of stacking a new one. Because f does nothing after g returns, its frame is dead weight; TCO tears f's frame down first, then jumps into g so g reuses that same space. Why this step? If nothing in f runs after the call, f's locals and saved BP are useless during g — keeping them would only pile depth. TCO turns the call into a jump, so net depth added = 0 and infinite tail recursion cannot overflow (unlike Example 6). Non-tail recursion has no such escape.
2. (b) Register args cost zero stack bytes for the arguments. With all 4 ints in registers, no arguments are pushed; if g also has no locals and is a leaf, its whole frame is just the 8-byte return address. Why this step? The System V convention (see Calling conventions (cdecl, stdcall)) passes the first several integer args in registers precisely to avoid stack traffic — so the "push arguments" step from the parent's diagram simply vanishes. Frame cost here = 8 bytes, same minimum as the degenerate Example 5.
3. (c) Windows shadow space forces 32 extra caller bytes. Even though the 4 args ride in registers, the caller must still subtract 32 bytes so the callee has scratch room to spill those register args if it wants. Why this step? Different conventions make different trade-offs: Microsoft x64 mandates this reserved slot for debuggability and uniform arg handling, so a call there costs 32 (shadow) + 8 (return address) = 40 bytes minimum — more than System V's 8, for the exact same source code.

Answer: (a) net 0 bytes (frame reused); (b) 8 bytes (return address only); (c) 40 bytes minimum (32 shadow + 8 return address). Same call, three depths, depending on convention.

---

Recall Self-test: name the cell for each scenario

Two live frames at once ::: cell B (nested calls) A function with no args and no locals ::: cell E (degenerate frame) Return address kept in a register first ::: cell I (ARM link register) Pointer that outlives its frame ::: cell G (dangling pointer) Frames piling until the region runs out ::: cell F (deep recursion / overflow) Stack where a push increases SP ::: cell D (upward-growing) Frame size rounded up to a 16-byte boundary ::: cell J (alignment / padding) A tail call that adds zero stack depth ::: cell K (optimised-away frame)