Return address stack: Visual walkthrough — Hinglish deep dive

5.3.12 · D2 · Hardware › Advanced Microarchitecture › Return address stack

Yeh page RAS topic ka central result bilkul scratch se rebuild karti hai — koi bhi jargon assume nahi kiya gaya. Hum ek hi sawaal ka jawab pictures ke saath dhundhna chahte hain:

Jab ek program kisi function se return karta hai, toh processor kaise guess karta hai ki woh kahan ja raha hai — actually jaanne se pehle?

End tak aap step by step dekhenge ki kyun jawaab ek chhoti si hardware stack hai, aur exactly kab yeh fail hoti hai. Agar aapne kabhi "stack" ya "return" shabd nahi suna, toh Step 1 se shuru karein — sab kuch aapke liye build kiya gaya hai.

Step 1 — "Call" aur "return" kya hota hai?

KYA HAI. Ek program instructions ki ek list hota hai, har instruction ek numbered address par rehta hai (jaise street par ghar ke numbers). Call ek instruction hai jo kehta hai: "wahan jaao aur instructions ka woh block chalao, lekin kaam ho jaane ke baad yahan wapas aao." Return woh instruction hai us block ke end par jo kehta hai: "theek hai, wapas jaao."

YEH KYUN MATTER KARTA HAI. Processor instructions ko bahut aage padhta hai taaki fast rahe (dekho Instruction Fetch). Jab yeh kisi return se milta hai, toh ise turant woh address jaanna chahiye jahan jump back karna hai — lekin woh address is baat par depend karta hai ki kisne is function ko call kiya. Alag-alag callers ⇒ same return instruction ke liye alag-alag return addresses.

PICTURE. Neeche, main low addresses par rehta hai, foo unse zyada par. Red arrow call hai jo aage jump karta hai; black dashed arrow return hai jo wapas jump karta hai. Note karein ki return, call ke baad waale instruction par land karta hai.

Step 2 — Nesting: calls ek dusre ke andar stack hote hain

KYA HAI. Functions, functions ko call karte hain. main, foo ko call karta hai; foo ke finish hone se pehle, foo, bar ko call karta hai. Ab do returns "hone ka wait kar rahe hain."

KYUN. Order program ke meaning ke hisaab se forced hai: bar zaroor finish ho aur return kare tab hi foo finish ho sakta hai aur return kar sakta hai. Jab tak aap bar ke andar hain, tab tak foo se return nahi ho sakta. Yahi woh poora secret hai jise hum exploit karenge.

PICTURE. Nesting ko measuring cups ki tarah padho jo ek dusre ke andar baithe hain. Sabse recently-open function (innermost, red) woh pehla hai jise close karna zaroori hai.

Step 3 — Nesting ko ek Last-In-First-Out list mein badlo

KYA HAI. Ab hum "waiting" return addresses ko ek vertical list mein likhte hain. Har baar jab hum call karte hain, hum ek return address upar ( $push$ ) karte hain. Har baar jab hum return karte hain, hum address upar se ( $pop$ ) lete hain.

YEH EXACT RULE KYUN. Step 2 se, hume aage jo return chahiye woh hamesha sabse recent unfinished call ka hota hai. "Sabse recent in, pehla out" ka ek naam hai: LIFO — Last In, First Out. Ek aisi list jo sirf upar se add aur remove karti hai use stack kehte hain.

PICTURE. Stack ke top (red slot) ko dekhte raho. Push se woh upar badhta hai; pop se woh chhota hota hai. Red slot hamesha exactly woh address hota hai jo next return chahta hai.

Step 4 — Ek poora call/return chain trace karo

KYA HAI. Chaliye ek real sequence chalate hain aur stack ko "breathe" karte dekhte hain. Addresses: main, foo ko call karta hai (return 0x1004), foo, bar ko call karta hai (return 0x2004), phir do returns.

KYUN. Yeh dekhne ke liye ki dono returns correctly predict kiye gaye hain — stack top har baar true destination se match karta hai.

PICTURE. Chhah snapshots left→right. Red slot current top hai. Follow karo ise: pushed 1004, pushed 2004, popped 2004 (correct!), popped 1004 (correct!), empty.

Cycle	Event	RAS action	Stack (bottom→top)	Top (red)
1	`CALL foo`	push `0x1004`	`[0x1004]`	`0x1004`
2	`CALL bar`	push `0x2004`	`[0x1004, 0x2004]`	`0x2004`
3	`RET` (bar)	pop → `0x2004`	`[0x1004]`	`0x1004`
4	`RET` (foo)	pop → `0x1004`	`[]`	—

Dono returns zero pipeline flushes ke saath predict kiye gaye — pipeline mein koi wasted work nahi.

Step 5 — Pointer arithmetic (hardware actually kaise store karta hai)

KYA HAI. Real hardware ek list ko infinitely nahi badhata; yeh $N$ slots ki ek fixed ring use karta hai aur ek pointer jise TOS (Top-Of-Stack) kehte hain jo ring ke around chalata hai. Ek alag count yaad rakhta hai ki kitne slots actually live hain.

RING + COUNT KYUN? Silicon finite hai, isliye hum slots ko ek circle mein reuse karte hain. Lekin ek plain circle "empty" aur "full" mein fark nahi kar sakta — dono cases mein pointer kahin na kahin hota hai. count (occupancy) yeh fix karta hai: yeh batata hai ki pop legal hai ya nahi, aur push purane data ko evict kar raha hai ya nahi.

PICTURE. $N = 4$ slots ka ek circular buffer. Red arrow TOS hai. Push ise ek taraf rotate karta hai; pop ise wapas rotate karta hai.

Step 6 — Degenerate case: empty stack par pop (underflow)

KYA HAI. Kya hoga agar ek return predict kiya gaya ho lekin stack empty ho (count = 0)? Shayad hum kisi function ke andar se run karna shuru kar rahe hain jiska call humne kabhi dekha hi nahi.

YEH DANGEROUS KYUN HAI. Bare (TOS-1) mod N phir bhi koi na koi slot produce karta hai — lekin us slot mein kisi previous program ka stale garbage hota hai. Ise use karna ek confident galat prediction hogi: ek guaranteed misprediction flush.

PICTURE. Left: empty ring, count = 0. Ek naive pop TOS ko ek aisi slot par rotate karta hai jisme purana junk hai (red mein ek trap ki tarah dikhaya gaya). Right: guarded behaviour — agar count = 0 hai, toh RAS "no prediction" kehta hai aur ek fallback predictor ko handle karne deta hai.

Step 7 — Degenerate case: full stack par push (overflow)

KYA HAI. Ab ulta: call chain $N$ slots se zyada deep hai. $N = 4$ ke saath, ek 5th nested call ke liye koi naya slot nahi hai.

OVERFLOW TOLERATED KYUN HAI, FIX KYUN NAHI. Hum jaanboojhkar sabse purani entry (outermost caller ki) overwrite karte hain. Sabse purani kyun? Kyunki woh entry hai jiska return sabse zyada future mein hona hai — usse pehle hamare paas sabse zyada time hota hai, aur innermost returns (jo soonest chahiye hain) intact aur correct rehte hain.

PICTURE. Paanch nested calls ek 4-slot ring mein. Red slot ret_A (sabse purana) ret_E se stamp ho jaata hai. A ke return ko chhodkar har return phir bhi correct hai; sirf A ka return mispredict hota hai.

Event	Stack (bottom→top)	Note
A→B→C→D	`[ret_A, ret_B, ret_C, ret_D]`	full, `count = 4`
D→E	`[ret_B, ret_C, ret_D, ret_E]`	`ret_A` evicted, `count` 4 hi rehta hai
E,D,C,B return karte hain	har baar correct	innermost survivors
A returns	✗ misprediction	`ret_A` lost ho gaya tha

Isliye depth matter karti hai: 4 entries ≈ 85% accuracy, 16 entries ≈ 97%, 32 entries ≈ 98.5%. Dekho Branch Prediction Basics.

Step 8 — Degenerate case: speculation ne galat tarike se stack touch kiya

KYA HAI. Processor branches ko pehle guess karta hai, yeh jaanne se pehle ki woh sahi the (Speculative Execution). Woh ek aisi path par RAS ko push/pop kar sakta hai jo baad mein galat nikle aur throw away kar di jaye.

CHECKPOINT KYUN. Agar ek speculative call A → call B → return ne B pop kiya, lekin call A khud mispredict tha, toh woh pop undo hona chahiye. Cure yeh hai: puri stack state (TOS aur count) ka har risky branch par snapshot lo, aur flush par use restore kar do.

PICTURE. Do side-by-side stacks: ek committed (sirf real, retired calls) aur ek speculative wala. Flush par, ek arrow committed snapshot ko speculative stack par wapas copy karta hai.

Ek-picture summary

Upar ki sab cheez ek hi frame mein: nesting reverse-order returns force karti hai → LIFO → TOS pointer aur count ke saath slots ki ek ring → underflow, overflow, aur speculation se guarded.

Recall Feynman retelling (bolke sunao, koi jargon nahi)

Plates stack karne ki imagine karo. Har baar jab aap koi function call karte ho, aap ek plate par likhte ho "yahan wapas aao" aur pile ke upar rakh dete ho. Kyunki koi function tabhi finish ho sakta hai jab usne jo bhi shuru kiya sab finish ho jaaye, isliye aapko jo plate next chahiye woh hamesha upar waali hoti hai — toh jab return hota hai, aap top waali plate uthate ho aur wahan jump karte ho. Yahi poora trick hai: sabse aakhir mein rakhi plate pehli uthti hai.

Real hardware ek chhoti round tray use karta hai fixed number of spots ke saath aur ek finger (TOS) jo top plate ko point karta hai, plus ek tally ki tray par actually kitni plates hain. Agar koi plate try kare grab karna jab tray empty ho, toh tally kehti hai "yahan kuch nahi hai — main guess nahi karunga." Agar pile tray se zyada tall ho jaaye, toh sab se neeche waali sabse purani plate crush ho jaati hai — hum woh plate khote hain, lekin yeh woh plate hai jise hume sabse zyada time baad chahiye, isliye yeh sacrifice karna sabse safe hai. Aur kyunki processor kabhi kabhi aise guesses play out karta hai jo galat nikle, woh real tray ki ek photograph rakhta hai aur woh photo wapas neeche rakh deta hai jab bhi koi guess cancel ho jaata hai.

Recall

Returns ke liye stack (LIFO) sahi structure kyun hai? ::: Kyunki program nesting returns ko calls ke exact reverse order mein hone par force karta hai, isliye next chahiye wala return hamesha sabse recent unfinished call ka hota hai — stack ka top. count == 0 par pop kya return karta hai, aur ring pointer par sirf trust kyun nahi karte? ::: Yeh "no prediction" return karta hai; ek bare ring pointer hamesha kisi na kisi slot par point karta hai, jo pehle se stale garbage hoga — ek guaranteed misprediction. Overflow par, kaun si entry overwrite hoti hai aur yeh sabse safe choice kyun hai? ::: Sabse purani (outermost caller ki) entry; uska return sabse zyada future mein hai, isliye hamare paas uski loss matter karne se pehle sabse zyada time hai aur saare jaldi wale returns correct rehte hain. Speculative flush ke baad kaunsi do values ek saath restore honi chahiye? ::: TOS pointer aur occupancy count (committed snapshot se).