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

5.1.16 · D3 · Coding › C Programming › Stack frames — how function calls work at the memory level

Yeh page parent note on stack frames ka exhaustive worked-examples lab hai. Parent ne tumhe machinery sikhaayi thi: ek frame ek private scratch desk hota hai jisme locals, ek saved base pointer, aur ek return address hote hain, aur desks LIFO (last-in, first-out) order mein pile up hoti hain. Yahan hum us machinery ko har case class ke against test karenge — stack ke har direction, har degenerate call, sabse deep recursion, buggy pointer, aur ek exam trap.

Agar koi word neeche unfamiliar lage, toh woh parent mein build kiya gaya tha. Do terms jo tum baar baar use karoge:

• Stack pointer (SP) ::: woh register jo stack ke top (newest byte) ka address hold karta hai.
• Base pointer (BP) ::: current frame ke andar ek fixed reference address, taaki locals constant offsets par rahen chahe SP move kare.

---

The scenario matrix

Examples karne se pehle, chaliye list karte hain har tarah ke situation jo ek stack frame face kar sakta hai. Baad ke har example mein woh cell tagged hai jise woh cover karta hai, aur saath milke yeh poora grid fill karte hain.

#	Case class	Ismein kya special hai	Covered by
A	Single flat call (baseline)	ek caller, ek callee, koi nesting nahi	Example 1
B	Nested calls (call ke andar call)	do live frames stacked	Example 2
C	Downward-growing stack, address arithmetic	BP se real offsets compute karo	Example 3 (figure)
D	Upward-growing stack (opposite sign)	kuch CPUs / textbooks direction flip karte hain	Example 4 (figure)
E	Zero-work / degenerate frame	function jisme koi locals nahi, koi args nahi	Example 5
F	Deep recursion → limiting behaviour	frames pile hote hain jab tak stack overflow nahi ho jaata	Example 6
G	Dangling pointer to a freed local	pointer apne frame se zyada jee jaata hai	Example 7 (figure)
H	Real-world word problem	real stack depth bytes mein measure karo	Example 8
I	Exam-style twist (ARM link register)	return address pehle stack par nahi	Example 9 (figure)
J	Frame alignment / padding	total 16-byte boundary par round kiya jaata hai	Example 10
K	Optimised-away frame (tail call, register args, shadow space)	conventions jo frame ko skip ya reshape karte hain	Example 11

Jahan bhi numbers aate hain hum stack ko explicitly bytes mein track karte hain, taaki har claim checkable ho.

---

Example 1 — baseline single call (cell A)

1. Return address push karo. CALL 8 subtract karta hai: $SP=1000-8=992$. Yeh step kyun? x86 par CALL stack par return address store karta hai taaki f ko pata ho kahan wapas jaana hai; ek push SP ko lower addresses ki taraf move karta hai.
2. Saved BP push karo. Prologue 8 subtract karta hai: $SP=992-8=984$. Yeh step kyun? f ko main ka BP overwrite karne se pehle save karna hai, warna main apna frame reference kho deta hai.
3. BP = SP set karo. Ab $BP=984$. Yeh f ka anchor hai; yeh SP move nahi karta. Yeh step kyun? Locals is fixed point ke relative address honge.
4. 16 bytes locals carve karo. $SP=984-16=968$. Yeh step kyun? Local variables ko downward stack par BP ke neeche reserved space chahiye.

Answer: f ke andar, $SP=968$. Frame cost $=1000-968=32$ bytes. Frame isliye byte range $[968,1000)$ span karta hai — naye top se lekar (lekin include nahi karta) wahan tak jahan main ka frame resume hota hai.

---

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

1. f ka frame push hua. $SP=2000-24=1976$. Yeh step kyun? f ko call karna f ka frame main ke (neeche) upar build karta hai.
2. g ka frame push hua. $SP=1976-24=1952$. Yeh step kyun? f ka g ko call karna f ke neeche ek aur frame build karta hai. Ab ek saath teen frames live hain — yeh sabse deep moment hai.
3. g return karta hai. SP 24 se upar reset hota hai: $SP=1952+24=1976$. Yeh step kyun? Cleanup sirf SP ko wapas move karna hai; g ki desk disappear ho jaati hai.
4. f return karta hai. $SP=1976+24=2000$, main ke andar wapas. Yeh step kyun? LIFO — g (last created) pehle mara, phir f.

Answer: deepest $SP=1952$; destruction order hai g, phir f, phir main (creation ka reverse).

---

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

1. local0 BP se 8 neeche hai. $500-8=492$. Toh ${\text{offset}}_0=8$. Yeh step kyun? BP ke baad push hone wala pehla local next lower 8-byte slot mein jaata hai.
2. local1 BP se 16 neeche hai. $500-16=484$. Toh ${\text{offset}}_1=16$. Yeh step kyun? Doosra local ek word aur neeche hai.
3. arg0 BP se 16 upar hai. $500+16=516$. Toh $\text{offset}=16$ (beech mein saved BP ke liye 8 + return address ke liye 8). Yeh step kyun? Arguments call se pehle push hue the, isliye woh BP ke upar rehte hain; unhe reach karne ke liye saved BP aur return address step over karne padte hain.

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

---

Example 4 — UPWARD-growing stack (cell D)

1. Return address push karo. SP 8 se increase hota hai: $SP=700+8=708$. Yeh step kyun? "Grows upward" matlab har push SP mein subtract ki jagah add karta hai.
2. Saved BP push karo. SP aur 8 se increase hota hai: $SP=708+8=716$. Yeh step kyun? Growth direction tumhe caller ka BP save karne se excuse nahi karta — yeh har architecture par mandatory hai, warna caller apna frame reference kho deta hai. Ise skip karna woh flaw tha jo ek earlier draft mein tha.
3. BP = SP = 716 set karo, phir locals upward carve karo. $SP=716+16=732$. Yeh step kyun? Locals ab BP ke upar rehte hain, toh formula ${\text{addr(local}}_k)=BP+{\text{offset}}_k$ par flip ho jaata hai.
4. local0 $716+0=716$ par hai, local1 $716+8=724$ par. Yeh step kyun? Kyunki growth upward hai, higher offset = higher address.

Answer: $SP=732$; locals BP ke upar hain; address formula mein sign + par flip ho jaata hai; frame cost $=8+8+16=32$ bytes — Example 1 jaisi total, sirf direction reverse ho gayi.

---

Example 5 — degenerate frame: koi args nahi, koi locals nahi (cell E)

1. CALL phir bhi 8-byte return address push karta hai. $SP=300-8=292$. Yeh step kyun? Ek no-op ko bhi pata hona chahiye kahan wapas jaana hai — return address non-optional hai.
2. Prologue omit ho sakta hai. Ek smart compiler BP save karna aur locals carve karna skip kar deta hai kyunki anchor karne ke liye kuch hai hi nahi. Yeh step kyun? Koi locals nahi ⇒ stable BP reference ki zaroorat nahi ⇒ prologue pure overhead hai aur remove ho jaata hai (yahi "frame-pointer omission" hai).
3. RET return address pop karta hai. $SP=292+8=300$, fully restored. Yeh step kyun? Single push single pop se undo hota hai.

Answer: minimum stack change 8 bytes hai (sirf return address); BP ki zaroorat nahi.

---

Example 6 — deep recursion aur overflow limit (cell F)

1. Har level 512 bytes cost karta hai aur mid-recursion mein koi free nahi hota. Deepest point par saare frames simultaneously live hote hain. Yeh step kyun? Recursion ek frame tab tak free nahi karti jab tak uski call return nahi hoti; maximum depth par har frame abhi bhi live hai.
2. Total ko per-frame cost se divide karo. $\frac{8388608}{512}=16384$ levels. Yeh step kyun? Total budget ÷ cost per frame = kitne fit hote hain region khatam hone se pehle.
3. Level 16385 boundary ke baad push karta hai → stack overflow. Yeh step kyun? Jab SP guard page cross karta hai, OS fault karta hai; parent ne ise "too deep ⇒ stack overflow" kaha tha.

Answer: lagbhag 16384 levels; agli wali overflow karta hai.

---

Example 7 — freed local par dangling pointer (cell G)

1. bad ke return karne ke baad, SP 1000 par wapas chala jaata hai. Poora range $[968,1000)$ — address 976 sameta — ab reserved nahi raha. Yeh step kyun? Cleanup = SP ko wahan reset karna jahan woh call se pehle tha; bad ka poora 32-byte frame logically destroy ho jaata hai jaise hi woh return karta hai, sirf ek part nahi.
2. p abhi bhi 976 point karta hai. Pointer value unchanged hai — yeh sirf unowned memory ki taraf aim karta hai ab. Yeh step kyun? &local return karna address copy karta hai, aur address survive karta hai chahe storage nahi karta.
3. g ko call karna same region $[968,1000)$ mein 32-byte frame rebuild karta hai. Kyunki g $SP=1000$ se start karta hai aur 8 (retaddr) + 8 (saved BP) + 16 (locals) = 32 bytes push karta hai, uska frame exactly un addresses par land karta hai jo bad ne abhi khali kiye — address 976 ab g ka hai. Yeh step kyun? Stack same low addresses next frame ke liye recycle karta hai; same size ⇒ same footprint ⇒ 976 par guaranteed collision.
4. *p ab woh kuch read karta hai jo g ne 976 par likha — ek saved BP byte ya g ka local, 42 nahi. Yeh step kyun? 42 overwrite ho gaya; ise read karna undefined behaviour hai — yeh 42 read kar sakta hai luck se before kisi call ke, garbage after.

Answer: *p undefined hai; commonly 42 return ke immediately baad (bytes untouched), phir garbage jab g ka 32-byte frame $[968,1000)$ reuse karta hai aur 976 overwrite karta hai. Fix: value se return karo ya malloc (heap) use karo.

---

Example 8 — real-world word problem: depth bytes mein measure karna (cell H)

1. Dono stack pointers ko plain numbers ki tarah read karo. $0x7fffffffe200$ hai "top of main", $0x7fffffffe040$ hai "deepest point". Yeh step kyun? "Kitna deep" ek distance hai do addresses ke beech, aur distance ek subtraction hai — toh hume dono SP values ko ordinary integers ki tarah treat karna hai jo hum subtract kar sakein, opaque labels ki tarah nahi.
2. Notice karo ki dono addresses saare high bits share karte hain. Dono 0x7fffffffe0__ hain; woh sirf final teen hex digits mein differ karte hain, 200 versus 040. Kyunki high halves identical hain, unhe subtract karne par wahan zero milega, aur koi borrow us shared prefix mein climb nahi kar sakta. Yeh step kyun? Jab do numbers apne leading bits par agree karte hain, saara difference low bits mein rehta hai — toh hum sirf differing tails subtract kar sakte hain aur safely identical prefix ignore kar sakte hain.
3. Downward stack par top address bada hota hai, toh depth = top − deep. Tails compute karo: $0x200-0x040=0x1c0$. Yeh step kyun? Stack main se downward grow hua, toh used bytes deep (chhote) address se main ke (bade) start tak stretch karte hain; positive difference us span mein bytes ki count hai.
4. $0x1c0$ ko decimal mein convert karo. $0x1c0=1\times 16^2+12\times 16^1+0=256+192+0=448$. Yeh step kyun? Hex base-16 hai; har digit 16 ki power se weighted hai, aur $c$ 12 ka hex digit hai.

Answer: call chain us moment mein 448 bytes (0x1c0) deep hai.

---

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

1. BL g g ka return address LR mein daalta hai. Stack abhi tak unchanged: $SP=4000$. Yeh step kyun? ARM ka branch-and-link ek register write hai, push nahi — x86 ke memory push se sasta, toh return address ka pehla hop ek register hai, stack nahi.
2. g abhi BL h karne wala hai, jo LR overwrite karega. Toh g pehle apna LR stack par push (spill) karta hai: $SP=4000-8=3992$. Yeh step kyun? BL h LR ko h ke return address se overwrite karega. Agar g ne LR pehle save nahi kiya, toh h ko call karna g ka apna return address destroy kar deta aur g kabhi f par wapas nahi ja sakta. Stack par spill karna use park karta hai jahan BL h touch nahi kar sakta.
3. g run karta hai, phir return se pehle LR restore karta hai spilled value wapas pop karke: $SP=3992+8=4000$. Yeh step kyun? g ko apna return address LR mein (ya RET ke liye stack par) chahiye f par wapas jaane ke liye; epilogue spill undo karta hai, aur SP wahan wapas jaata hai jahan woh tha.
4. Ek leaf function (jo kisi ko call nahi karta) steps 2–3 skip karta hai. Woh apna return address poore time LR mein rakhta hai aur iske liye kabhi stack touch nahi karta. Yeh step kyun? Ek leaf kabhi doosra BL execute nahi karta, toh LR kabhi clobber nahi hota — protect karne ke liye kuch nahi, toh koi spill needed nahi. Exactly yahi reason hai ki leaf functions ARM par saste hote hain.

Answer: spill ke baad, $SP=3992$ (aur matching restore ke baad $4000$ wapas); spill sirf non-leaf functions ke liye mandatory hai, kyunki sirf woh ek inner BL issue karte hain jo LR overwrite karta.

---

Example 10 — frame alignment aur padding (cell J)

1. Local size ko next 16-byte multiple par round up karo. $20\to 32$ (kyunki $16<20\le 32$). Extra $32-20=12$ bytes padding hain — unused filler. Yeh step kyun? Convention demand karta hai ki SP 16-aligned rahe taaki SIMD instructions (jo aligned memory require karte hain) aur next call correctly kaam kare. 16 ka non-multiple carve karna SP ko misalign kar deta.
2. Rounded size subtract karo. $SP=8016-32=7984$. Yeh step kyun? Downward stack ⇒ locals carve karna subtract karta hai; hum padded 32 subtract karte hain, raw 20 nahi.
3. Alignment check karo. $7984÷16=499$ exactly, toh $7984$ 16-aligned hai. ✓ Yeh step kyun? Confirm karta hai ki padding ne apna kaam kiya — SP ek 16-byte boundary par land kiya, next call ke liye ready.

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

---

Example 11 — frames jo optimise away ya reshape ho jaate hain (cell K)

1. (a) Tail call f ka frame reuse karta hai new frame stack karne ki jagah. Kyunki f g ke return karne ke baad kuch nahi karta, uska frame dead weight hai; TCO f ka frame pehle tear down karta hai, phir g mein jump karta hai taaki g same space reuse kare. Yeh step kyun? Agar call ke baad f mein kuch run nahi hota, toh g ke dauran f ke locals aur saved BP useless hain — unhe rakhna sirf depth pile karega. TCO call ko ek jump mein convert karta hai, toh net depth added = 0 aur infinite tail recursion overflow nahi kar sakta (Example 6 ke unlike). Non-tail recursion mein aisa escape nahi hota.
2. (b) Register args stack bytes zero cost karte hain arguments ke liye. Saare 4 ints registers mein hone se koi arguments push nahi hote; agar g ke koi locals bhi nahi hain aur yeh leaf hai, toh uska poora frame sirf 8-byte return address hai. Yeh step kyun? System V convention (dekho Calling conventions (cdecl, stdcall)) pehle kai integer args registers mein isliye pass karta hai taaki stack traffic avoid ho — toh parent ke diagram ka "push arguments" step simply vanish ho jaata hai. Frame cost yahan = 8 bytes, same minimum jaise degenerate Example 5.
3. (c) Windows shadow space 32 extra caller bytes force karta hai. Chahe 4 args registers mein hon, caller ko abhi bhi 32 bytes subtract karne padte hain taaki callee ke paas un register args ko spill karne ki scratch room ho agar chahe. Yeh step kyun? Different conventions alag trade-offs karte hain: Microsoft x64 debuggability aur uniform arg handling ke liye yeh reserved slot mandate karta hai, toh wahan ek call 32 (shadow) + 8 (return address) = 40 bytes minimum cost karta hai — System V ke 8 se zyada, exact same source code ke liye.

Answer: (a) net 0 bytes (frame reused); (b) 8 bytes (sirf return address); (c) 40 bytes minimum (32 shadow + 8 return address). Same call, teen depths, convention par depend karta hai.

---

Recall Self-test: har scenario ke liye cell name bolo

Ek saath do live frames ::: cell B (nested calls) Ek function jisme koi args aur locals nahi ::: cell E (degenerate frame) Return address pehle register mein rakha ::: cell I (ARM link register) Pointer jo apne frame se zyada jeeta hai ::: cell G (dangling pointer) Frames pile hote hain jab tak region khatam nahi ho jaata ::: cell F (deep recursion / overflow) Stack jahan ek push SP increase karta hai ::: cell D (upward-growing) Frame size 16-byte boundary par round up hoti hai ::: cell J (alignment / padding) Tail call jo zero stack depth add karta hai ::: cell K (optimised-away frame)