Function call আর stack — calling convention, stack frame আর recursion

১ · একটি function call-এর ছয়টি কাজ

C-তে y = sq(x); লেখা খুব সহজ। কিন্তু CPU-র কাছে “function” বলে কিছু নেই — আছে শুধু register, মেমরি আর একটি program counter (PC), যা বলে দেয় পরের instruction কোথায়। তাহলে একটি function ডাকা আর সেখান থেকে ঠিক জায়গায় ফিরে আসা machine-এর ভাষায় আসলে কী? এই পর্বের পুরো গল্পটা এই প্রশ্নের উত্তর।

Patterson আর Hennessy তাঁদের Computer Organization and Design বইয়ে একটি procedure (function) call-কে ছয়টি ধাপে ভেঙেছেন। বিশ্ববিদ্যালয় আর চাকরির লিখিত পরীক্ষায় এই তালিকা প্রায়ই চাওয়া হয়:

ছয় নম্বর ধাপটিই সবচেয়ে মজার। একটি function প্রোগ্রামের অনেক জায়গা থেকে ডাকা হতে পারে — printf একটি প্রোগ্রামে হয়তো দুশো জায়গা থেকে ডাকা হয়। তাই ফেরার ঠিকানা function-এর ভেতরে স্থির করে লেখা যায় না; প্রতিটি call-এর সময় caller-কেই তা জানিয়ে দিতে হয়। শুরুর দিকের কিছু কম্পিউটারে ফেরার ঠিকানা function-এর কোডের ভেতরেই একটি নির্দিষ্ট ঘরে লিখে রাখা হতো, ফলে একটি function নিজেকে ডাকতে (recursion) পারত না — দ্বিতীয় call প্রথমটির ঠিকানা মুছে দিত। Stack সেই সমস্যার স্থায়ী সমাধান, যা আমরা অংশ ৪-এ দেখব।

২ · jal আর jalr — ডাকা আর ফেরা

পর্ব ২৯-এ শাখা আর লুপ লিখতে আপনি jal আর jalr-এর প্রাথমিক রূপ দেখেছেন। এবার এদের আসল কাজ — function call. নিয়ম দুটি এক লাইনে:

jal (jump and link) একটি J-type instruction (encoding পর্ব ২৭-এ): এর offset ২০ বিটের, ২ byte-এর এককে, তাই নিজের অবস্থান থেকে প্রায় ±১ MiB দূর পর্যন্ত লাফ দেওয়া যায়। “Link” মানে ফেরার ঠিকানা রেখে দেওয়া — PC + 4, অর্থাৎ jal-এর ঠিক পরের instruction. Function call-এ rd হিসেবে প্রায় সবসময় ra (x1) ব্যবহার হয়। jalr একটি I-type instruction: লাফের ঠিকানা আসে একটি register থেকে, তাই যেকোনো জায়গায় যাওয়া যায় — function থেকে ফেরা, function pointer দিয়ে ডাকা, বা অনেক দূরের function. ঠিকানার শেষ বিটটি শূন্য করা হয় (& ~1).

Assembler কয়েকটি pseudo-instruction দেয়, যেগুলো আসলে এই দুটিরই ছদ্মবেশ:

খেয়াল করুন, ret-এ rd = x0. x0-তে লেখা সবসময় হারিয়ে যায়, তাই “ফেরার সময় আবার ফেরার ঠিকানা রাখা”-র কোনো ফল থাকে না। এবার একটি leaf function — যে নিজে আর কাউকে ডাকে না — ডাকা আর তার ফেরা ধাপে ধাপে দেখুন। প্রতিটি ধাপে দাগ দেওয়া instruction-টি এইমাত্র চলেছে:

100001000 main: addi a0, zero, 7200001004       jal  ra, sq     # call300001008       addi a1, a0, 0  # mv a1, a040000100c       ...5600002000 sq:   mul  a0, a0, a0700002004       jalr zero, 0(ra) # ret

এখন সমস্যাটি স্পষ্ট: sq যদি নিজে আরেকটি function ডাকত, তার jal ra-কে নতুন ঠিকানা দিয়ে মুছে দিত, আর sq আর কখনো main-এ ফিরতে পারত না। তাই যে function অন্যকে ডাকে — non-leaf function — সে শুরুতেই নিজের ra মেমরিতে (stack-এ) রেখে দেয়, আর ফেরার আগে ফিরিয়ে আনে। কোন register-এর ক্ষেত্রে এমন সাবধানতা কার দায়িত্ব, সেটাই পরের অংশের বিষয়।

৩ · Calling convention — কোন register কার দায়িত্বে

RV32I-এর ৩২টি integer register-এর প্রতিটির একটি ABI নাম আছে (পূর্ণ নামের টেবিল পর্ব ২৬-এ)। Function call-এর দিক থেকে প্রশ্ন একটাই: একটি call-এর পরে এই register-এর মান কি আগের মতো থাকবে? RISC-V psABI-এর উত্তর:

দুটি শব্দ পরিষ্কার করে নিই। Caller-saved (একে “volatile” বা “call-clobbered”-ও বলে) register মানে: callee এটি যা খুশি বদলাতে পারে, ফেরত দেওয়ার দায় নেই। Caller-এর যদি call-এর পরে মানটি দরকার হয়, সে নিজে call-এর আগে কোথাও রেখে দেবে। Callee-saved (“non-volatile”, “call-preserved”) register মানে: callee এটি ব্যবহার করতে চাইলে আগে পুরোনো মান stack-এ রাখবে আর ফেরার আগে ফিরিয়ে দেবে — caller নিশ্চিন্তে ধরে নিতে পারে, call-এর পরে মান অক্ষত।

Floating-point register (F/D extension থাকলে) একই নকশা মানে: fa0–fa7 argument, ft0–ft11 temporary, fs0–fs11 callee-saved. আর অনেক সময় বলা হয় “ra caller-saved” — এর মানে, jal নিজেই ra বদলায়, তাই যার পুরোনো ra দরকার (অর্থাৎ non-leaf function নিজে), তাকেই সেটি রাখতে হবে।

কেন দুই ভাগে ভাগ — একটি হিসাব

ধরুন একটি function F-এর একটি লুপ ১০০ বার G-কে ডাকে, আর পুরো লুপ জুড়ে F-এর তিনটি মান (যেমন সূচক, যোগফল, একটি pointer) বাঁচিয়ে রাখা দরকার। G একটি ছোট leaf function, যে নিজের কাজে কয়েকটি register ব্যবহার করে।

• সব register caller-saved হলে: প্রতিটি call-এর আগে F তিনটি মান stack-এ লিখবে, পরে তিনটি পড়বে। মোট ১০০ × (৩ + ৩) = ৬০০টি মেমরি-কাজ — অথচ G হয়তো ওই register-গুলো ছুঁতই না।
• সব register callee-saved হলে: G যে register-ই ব্যবহার করুক, প্রতিটি call-এ তা সংরক্ষণ আর ফেরত দেবে — ধরা যাক ৩টি, তাহলেও ১০০ × ৬ = ৬০০; আর যে G কিছুই বাঁচিয়ে রাখার দরকার বোঝে না, সেও অকারণে খরচ করবে।
• ভাগ থাকলে: F তিনটি মান s1, s2, s3-এ রাখে, আর prologue-এ একবার সেগুলোর পুরোনো মান সংরক্ষণ করে, epilogue-এ একবার ফেরত দেয়: মোট ৬টি মেমরি-কাজ. G নিজের কাজ t আর a register-এ সারে: ০টি. হিসাব ৬০০ থেকে নেমে এলো ৬-এ।

এই হিসাবের পেছনের পর্যবেক্ষণ দুটি: (১) চলার সময় যত call হয়, তার বড় অংশ যায় leaf function-এ, যাদের স্বল্পায়ু মানের জন্য “বিনা খরচের” temporary register দরকার; (২) দীর্ঘায়ু মান (যা অনেকগুলো call পেরিয়ে বাঁচে) একবার সংরক্ষণ করা প্রতিবার সংরক্ষণের চেয়ে সস্তা। তাই compiler-এর register allocation নিয়ম সহজ: call পেরিয়ে যে মান বাঁচবে, সে পায় একটি s register; বাকিরা পায় t বা a register. কতগুলো কোন ভাগে থাকবে, তা একটি নকশা-সিদ্ধান্ত — RISC-V ১২টি s register রেখেছে, MIPS-এর পুরোনো o32 convention-এ ছিল ৮টি ($s0–$s7).

নিচের stepper-এ একটি caller একটি মান t0-তে আর আরেকটি s1-এ রেখে একটি function ডাকছে। Callee দুটিই ব্যবহার করে — কিন্তু নিয়ম মেনে। দেখুন call-এর পরে কোনটি টিকল:

1caller: addi t0, zero, 10   # li t0, 102        addi s1, zero, 20   # li s1, 203        jal  ra, work4        add  a0, t0, s1     # expects 30?56work:   addi sp, sp, -167        sw   s1, 12(sp)     # save s1 first8        addi t0, zero, 99   # t0: free to use9        addi s1, zero, 77   # s1: saved, so OK10        lw   s1, 12(sp)     # restore s111        addi sp, sp, 1612        jalr zero, 0(ra)    # ret

Leaf বনাম non-leaf

৪ · Stack আর stack frame — ঠিকানাসহ ছবি

Register মাত্র ৩২টি, কিন্তু function-এর ডাক এক ডজন স্তর গভীর হতে পারে, আর প্রতিটির নিজের ra, নিজের local, নিজের সংরক্ষিত register আছে। এগুলো রাখার জায়গা হলো মেমরির একটি অংশ, যার নাম stack. এটি একটি LIFO (last in, first out) কাঠামো — রান্নাঘরে ধোয়া প্লেটের স্তূপের মতো: সবচেয়ে পরে রাখা প্লেটটিই প্রথমে তোলা হয়। Function call-এর ধরনও ঠিক তাই: যে function সবচেয়ে পরে ডাকা হয়েছে, সে-ই সবচেয়ে আগে ফেরে।

মেমরির মানচিত্রে stack কোথায়

একটি চলমান প্রোগ্রামের (process) ঠিকানা-জগৎ মোটামুটি চার ভাগে সাজানো থাকে — বিস্তারিত দেখুন OS কোর্সের প্রসেস পর্বে আর C-এর দিক থেকে C কোর্সের scope ও storage পর্বে। নিচের ছবিটি একটি সাধারণ Linux-ধাঁচের বিন্যাস; আসল ঠিকানা OS, ISA আর ASLR-এর ওপর নির্ভর করে।

RISC-V psABI-তে stack নিচের দিকে বাড়ে (grows downward): জায়গা নিতে sp থেকে বিয়োগ, ছাড়তে যোগ। sp সবসময় stack-এর বর্তমান “শেষ ব্যবহৃত” byte-কে দেখায়। আর একটি কঠোর নিয়ম: sp সবসময় ১৬ byte-এ aligned থাকবে (RV32I আর RV64I দুটিতেই; শুধু ছোট embedded “E” রূপের ilp32e ABI-তে ৪ byte). কারণ: ৮ বা ১৬ byte-এর ডেটা (double, long long, vector) stack-এ রাখলে তা স্বাভাবিকভাবে aligned থাকে, আর caller-callee দুজনেই একই অনুমান করতে পারে। তাই প্রতিটি stack frame-এর আকার ১৬-এর গুণিতকে গোল (round up) করা হয়।

একটি stack frame-এর ভেতরে

ধরুন একটি non-leaf function, যে s0 আর s1 ব্যবহার করে, দুটি int local রাখে, আর নিজে এমন একটি function ডাকে যার ১০টি argument (তাই দুটি argument stack-এ যায় — অংশ ৬)। Caller-এর sp ছিল 0x7fffffe0. Callee-র prologue শেষে frame এমন:

হিসাব: ra ৪ + s0 ৪ + s1 ৪ + দুটি local ৮ + outgoing argument ৮ = ২৮ byte, ১৬-এর পরের গুণিতক ৩২; তাই ৪ byte padding. Frame-এর ভেতরের ক্রম (ra সবার ওপরে, outgoing argument সবার নিচে, sp-তে) psABI বাধ্যতামূলক করে না — শুধু stack-argument যে caller-এর sp থেকে শুরু হবে আর alignment ১৬ — এটুকুই চুক্তি। বাকিটা compiler-এর পছন্দ; GCC আর Clang সাধারণত ra আর s0-কে frame-এর মাথায় রাখে।

Frame pointer (s0, যাকে fp-ও বলা হয়) হলো একটি স্থির খুঁটি: prologue-এ addi s0, sp, 32 করলে s0 থাকে frame-এর মাথায় (caller-এর sp-তে)। function-এর মাঝখানে sp বদলালেও (যেমন C-এর variable-length array বা alloca) local খুঁজে পাওয়া যায় s0 থেকে। আর debugger বা profiler saved-s0-এর শিকল ধরে ধরে পুরো call-chain হাঁটতে পারে। তবে frame pointer ঐচ্ছিক: optimization চালু থাকলে GCC সাধারণত -fomit-frame-pointer করে s0-কে আরেকটি সাধারণ saved register বানিয়ে ফেলে, আর debugger তখন compiler-এর লেখা unwind তথ্য (DWARF CFI) পড়ে। Profiling সহজ করতে কিছু Linux distribution সম্প্রতি আবার frame pointer চালু রেখে package build করছে।

Prologue আর epilogue — একটি non-leaf function

এবার পুরো একটি উদাহরণ হাতে লিখি: int sum_sq(int a, int b) { return sq(a) + sq(b); }. প্রথম call-এর সময় b বাঁচিয়ে রাখতে হবে, আর দ্বিতীয় call-এর সময় sq(a)-এর ফল — দুটিই call পেরোনো মান, তাই s register-এ যাবে। ra-ও রাখতে হবে, কারণ sum_sq নিজে ডাকছে। মোট ৩টি word = ১২ byte → frame ১৬ byte.

sq:                         # leaf: no frame at all
    mul  a0, a0, a0         # (M extension)
    ret

sum_sq:                     # a in a0, b in a1
    addi sp, sp, -16        # --- prologue: take a 16-byte frame
    sw   ra, 12(sp)         #     we call others -> save ra
    sw   s0, 8(sp)          #     we will use s0 and s1 -> save the caller's values
    sw   s1, 4(sp)
    mv   s1, a1             # keep b alive across the first call
    call sq                 # a0 = sq(a)
    mv   s0, a0             # keep sq(a) alive across the second call
    mv   a0, s1
    call sq                 # a0 = sq(b)
    add  a0, s0, a0         # return value in a0
    lw   s1, 4(sp)          # --- epilogue: undo the prologue in reverse
    lw   s0, 8(sp)
    lw   ra, 12(sp)
    addi sp, sp, 16
    ret

Prologue আর epilogue আয়নার মতো: prologue sp কমায় আর register রাখে; epilogue উল্টো ক্রমে register ফেরায় আর sp বাড়ায়। মাঝে যা-ই হোক, ফেরার মুহূর্তে sp, s0, s1 হুবহু আগের মতো — caller-এর কাছে মনে হবে কিছুই বদলায়নি, শুধু a0-তে ফল এসেছে। বিকল্প নকশাও সম্ভব: b-কে s1-এ না রেখে সরাসরি frame-এ (sw a1, 0(sp)) রেখে পরে পড়া — একই সংখ্যক মেমরি-কাজ। কোনটি ভালো, compiler আশপাশের কোড দেখে ঠিক করে।

নিচের visualiser আরেকটি non-leaf function-এর prologue আর epilogue চালায় — এবার s0-কে frame pointer হিসেবে, আর দুটি local সরাসরি frame-এ। প্রতিটি অবস্থায় মেমরির প্রতিটি word ঠিকানাসহ ছাপে:

// Stack-frame visualiser for one non-leaf RV32 function:
//   int f(int a, int b) { int buf[2] = {a, b}; return twice(buf[0]) + buf[1]; }
const hex = v => "0x" + (v >>> 0).toString(16).padStart(8, "0");
const x = { zero: 0, ra: 0x00010040, sp: 0x7fffffe0, s0: 0x7ffffff0, a0: 7, a1: 5 };   // at entry to f
const mem = new Map([[0x7fffffec, [0x00010100, "caller: saved ra"]], [0x7fffffe8, [0x80000000, "caller: saved s0"]],
                     [0x7fffffe4, [42, "caller: local"]], [0x7fffffe0, [0, "caller: local"]]]);
const NAME = { "ra,12": "saved ra", "s0,8": "saved s0 (caller fp)", "a0,-16": "buf[0] = a", "a1,-12": "buf[1] = b" };
function exec(line) {
  const [op, rd, off, base] = line.split(/[\s,()]+/);
  if (op === "addi") x[rd] = x[off] + +base;                          // addi rd, rs, imm
  if (op === "sw") mem.set(x[base] + +off, [x[rd], NAME[rd + "," + off]]);
  if (op === "lw") x[rd] = mem.get(x[base] + +off)[0];
  if (op === "call") x.ra = 0x00010218;                               // callee's jal overwrites ra
}
function show(title, lines, rows = true) {
  lines.forEach(exec);
  console.log(`--- ${title} ---   sp=${hex(x.sp)}  s0(fp)=${hex(x.s0)}  ra=${hex(x.ra)}`);
  for (let a = 0x7fffffec; rows && a >= 0x7fffffd0; a -= 4) {
    const [v, what] = mem.get(a) ?? [null, "(never written)"];
    const live = a >= x.sp ? "" : "   [below sp: free]", tag = a === x.sp ? " <- sp" : "";
    console.log(`${hex(a)}  ${v === null ? "     ?    " : hex(v)}  ${what}${tag}${live}`);
  }
}
show("1. at entry (before prologue)", []);
show("2. after prologue", ["addi sp,sp,-16", "sw ra,12(sp)", "sw s0,8(sp)", "addi s0,sp,16",
                           "sw a0,-16(s0)", "sw a1,-12(s0)"]);
show("3. after call twice (ra clobbered, frame intact)", ["call twice"], false);
show("4. after epilogue (ret jumps to ra)", ["lw ra,12(sp)", "lw s0,8(sp)", "addi sp,sp,16"]);
console.log(`frame size = 16 bytes (multiple of 16: ${16 % 16 === 0}); return to ${hex(x.ra)}`);

--- 1. at entry (before prologue) ---   sp=0x7fffffe0  s0(fp)=0x7ffffff0  ra=0x00010040
0x7fffffec  0x00010100  caller: saved ra
0x7fffffe8  0x80000000  caller: saved s0
0x7fffffe4  0x0000002a  caller: local
0x7fffffe0  0x00000000  caller: local <- sp
0x7fffffdc       ?      (never written)   [below sp: free]
0x7fffffd8       ?      (never written)   [below sp: free]
0x7fffffd4       ?      (never written)   [below sp: free]
0x7fffffd0       ?      (never written)   [below sp: free]
--- 2. after prologue ---   sp=0x7fffffd0  s0(fp)=0x7fffffe0  ra=0x00010040
0x7fffffec  0x00010100  caller: saved ra
0x7fffffe8  0x80000000  caller: saved s0
0x7fffffe4  0x0000002a  caller: local
0x7fffffe0  0x00000000  caller: local
0x7fffffdc  0x00010040  saved ra
0x7fffffd8  0x7ffffff0  saved s0 (caller fp)
0x7fffffd4  0x00000005  buf[1] = b
0x7fffffd0  0x00000007  buf[0] = a <- sp
--- 3. after call twice (ra clobbered, frame intact) ---   sp=0x7fffffd0  s0(fp)=0x7fffffe0  ra=0x00010218
--- 4. after epilogue (ret jumps to ra) ---   sp=0x7fffffe0  s0(fp)=0x7ffffff0  ra=0x00010040
0x7fffffec  0x00010100  caller: saved ra
0x7fffffe8  0x80000000  caller: saved s0
0x7fffffe4  0x0000002a  caller: local
0x7fffffe0  0x00000000  caller: local <- sp
0x7fffffdc  0x00010040  saved ra   [below sp: free]
0x7fffffd8  0x7ffffff0  saved s0 (caller fp)   [below sp: free]
0x7fffffd4  0x00000005  buf[1] = b   [below sp: free]
0x7fffffd0  0x00000007  buf[0] = a   [below sp: free]
frame size = 16 bytes (multiple of 16: true); return to 0x00010040

৫ · Recursion — factorial আর fibonacci assembly-তে

Recursion-এ hardware-এর জন্য নতুন কিছু নেই — একটি function নিজেকে ডাকছে মানে আরেকটি সাধারণ call, শুধু callee-র নাম আর caller-এর নাম এক। আর প্রতিটি call নিজের frame পায় বলে প্রতিটি “n” আলাদা আলাদা জায়গায় থাকে, কেউ কাউকে মোছে না। C-এর দিক থেকে ধারণাটি দেখুন C কোর্সের recursion পর্বে। পরীক্ষার সবচেয়ে চেনা উদাহরণ factorial:

int fact(int n) { if (n < 2) return 1; return n * fact(n - 1); }

00010000 main: addi a0, zero, 3     # li a0, 3
00010004       jal  ra, fact         # fact(3)
00010008       ebreak                # stop here
0001000c fact: addi sp, sp, -16      # frame: ra at 12(sp), n at 8(sp)
00010010       sw   ra, 12(sp)
00010014       sw   a0, 8(sp)        # save n: we need it after the call
00010018       addi t0, zero, 2      # li t0, 2
0001001c       bge  a0, t0, rec      # n >= 2 -> recursive case
00010020       addi a0, zero, 1      # base case (n < 2): return 1
00010024       addi sp, sp, 16
00010028       jalr zero, 0(ra)      # ret (ra was never changed here)
0001002c rec:  addi a0, a0, -1       # argument n - 1
00010030       jal  ra, fact         # a0 = fact(n - 1)
00010034       lw   t1, 8(sp)        # reload OUR n from OUR frame
00010038       mul  a0, t1, a0       # n * fact(n - 1)
0001003c       lw   ra, 12(sp)       # our return address
00010040       addi sp, sp, 16
00010044       jalr zero, 0(ra)      # ret

কেন n-কে stack-এ রাখতে হলো? কারণ a0 একটি caller-saved register, আর jal ra, fact-এর পরে a0-তে থাকবে fact(n − 1)-এর ফল — আমাদের n হারিয়ে যাবে। বিকল্প হতো n-কে s0-এ রাখা; তখন s0-এর পুরোনো মান সংরক্ষণ করতে হতো — একই খরচ। এবার fact(3)-এর পুরো জীবন frame ধরে ধরে দেখুন — বিশ্ববিদ্যালয় আর চাকরির পরীক্ষায় এই trace প্রায়ই চাওয়া হয়:

0x7ffffff0  ── main-এর এলাকা ──    ← sp
            (নিচে সব মুক্ত)
a0 = 3

0x7ffffff0  ── main-এর এলাকা ──
0x7fffffec  ra = 0x00010008   (main-এ ফেরা)
0x7fffffe8  n  = 3
0x7fffffe4  (ফাঁকা)
0x7fffffe0  (ফাঁকা)              ← sp
3 ≥ 2 → rec: a0 = 2, jal

0x7fffffec  ra = 0x00010008   n = 3      fact(3)
0x7fffffdc  ra = 0x00010034   n = 2      fact(2)
0x7fffffd0  ← sp
2 ≥ 2 → rec: a0 = 1, jal

0x7fffffec  ra = 0x00010008   n = 3      fact(3)
0x7fffffdc  ra = 0x00010034   n = 2      fact(2)
0x7fffffcc  ra = 0x00010034   n = 1      fact(1)
0x7fffffc0  ← sp   (মোট 48 byte ব্যবহৃত)
1 < 2 → base case: a0 = 1

0x7fffffec  ra = 0x00010008   n = 3      fact(3)
0x7fffffdc  ra = 0x00010034   n = 2      fact(2)
0x7fffffd0  ← sp   (fact(1)-এর frame মুক্ত)
PC = 0x00010034: lw t1 = 2; a0 = 2 × 1 = 2

0x7fffffec  ra = 0x00010008   n = 3      fact(3)
0x7fffffe0  ← sp
PC = 0x00010034: lw t1 = 3; a0 = 3 × 2 = 6

0x7ffffff0  ── main-এর এলাকা ──    ← sp
PC = 0x00010008 (main), a0 = 6
call ৩টি, সর্বোচ্চ depth ৩, stack ব্যবহার 48 byte

নিচের simulator একটি ছোট RV32I interpreter — register, sp, sw/lw দিয়ে আসল stack মেমরি, আর jal/jalr. এটি উপরের fact-এর কোডই চালায় (n = ৫), আর fibonacci-র একটি সংস্করণ, যেখানে fib(n − 1)-এর ফল দ্বিতীয় call পেরিয়ে বাঁচাতে callee-saved s0 ব্যবহার হয়েছে। প্রতিটি call আর return-এ sp আর frame-এর ভেতরের মান ছাপে:

// Tiny RV32I (+ mul from the M extension) interpreter with a real stack in memory.
const REG = { zero: 0, ra: 1, sp: 2, t0: 5, t1: 6, s0: 8, a0: 10 }, SP0 = 0x7ffffff0, r = t => REG[t];
const hex = v => "0x" + (v >>> 0).toString(16).padStart(8, "0");
const FACT = `fact: addi sp,sp,-16; sw ra,12(sp); sw a0,8(sp); addi t0,zero,2; bge a0,t0,rec
  addi a0,zero,1; addi sp,sp,16; jalr zero,0(ra)
  rec: addi a0,a0,-1; jal ra,fact; lw t1,8(sp); mul a0,t1,a0; lw ra,12(sp); addi sp,sp,16; jalr zero,0(ra)`;
const FIB = `fib: addi sp,sp,-16; sw ra,12(sp); sw s0,8(sp); sw a0,4(sp); addi t0,zero,2; blt a0,t0,done
  addi a0,a0,-1; jal ra,fib; addi s0,a0,0; lw a0,4(sp); addi a0,a0,-2; jal ra,fib; add a0,s0,a0
  done: lw s0,8(sp); lw ra,12(sp); addi sp,sp,16; jalr zero,0(ra)`;
function run(src, entry, n, slots, trace) {
  const code = [], lab = {}, x = new Array(32).fill(0), mem = new Map(), ld = a => mem.get(a) ?? 0;
  for (const s of `main: addi a0,zero,${n}; jal ra,${entry}; ebreak; ${src}`.split(/[;\n]/)) {
    const m = s.trim().match(/^(?:(\w+):\s*)?(.*)$/);
    if (m[1]) lab[m[1]] = 0x10000 + 4 * code.length; code.push(m[2].split(/[\s,()]+/));
  }
  let pc = 0x10000, minSp = SP0, depth = 0, maxDepth = 0, calls = 0, steps = 0; x[2] = SP0;
  for (;;) {
    const [op, a, b, c] = code[(pc - 0x10000) / 4], pad = "  ".repeat(depth); let next = pc + 4;
    if (op === "ebreak") break; steps++;
    if (op === "addi") x[r(a)] = (x[r(b)] + +c) | 0;
    else if (op === "add") x[r(a)] = (x[r(b)] + x[r(c)]) | 0;
    else if (op === "mul") x[r(a)] = Math.imul(x[r(b)], x[r(c)]);
    else if (op === "sw") mem.set(x[r(c)] + +b, x[r(a)]);               // sw rs2, imm(rs1)
    else if (op === "lw") x[r(a)] = ld(x[r(c)] + +b);
    else if (op === "bge" || op === "blt") { if ((x[r(a)] >= x[r(b)]) === (op === "bge")) next = lab[c]; }
    else if (op === "jal") { x[r(a)] = pc + 4; next = lab[b]; calls++; maxDepth = Math.max(maxDepth, ++depth);
      if (trace) console.log(`${pad}call ${b}(${x[10]})  sp=${hex(x[2])}  ra=${hex(pc + 4)}`); }
    else if (op === "jalr") { next = (x[r(c)] + +b) & ~1; x[r(a)] = pc + 4; const f = x[2] - 16; depth--;
      if (trace) console.log(`${pad.slice(2)}ret  a0=${x[10]}  sp=${hex(x[2])}  popped ` + Object.entries(slots)
        .map(([o, nm]) => nm + "=" + (nm === "ra" ? hex(ld(f + +o)) : ld(f + +o))).join(" ")); }
    x[0] = 0; pc = next; minSp = Math.min(minSp, x[2]); }
  console.log(`${entry}(${n}) = ${x[10]} | calls=${calls}, max depth=${maxDepth}, stack used=${SP0 - minSp} bytes, lowest sp=${hex(minSp)}, instructions=${steps}`);
}
run(FACT, "fact", 5, { 12: "ra", 8: "n" }, true);
run(FIB, "fib", 6, { 12: "ra", 8: "s0", 4: "n" }, false);   // true = print all 25 calls

call fact(5)  sp=0x7ffffff0  ra=0x00010008
  call fact(4)  sp=0x7fffffe0  ra=0x00010034
    call fact(3)  sp=0x7fffffd0  ra=0x00010034
      call fact(2)  sp=0x7fffffc0  ra=0x00010034
        call fact(1)  sp=0x7fffffb0  ra=0x00010034
        ret  a0=1  sp=0x7fffffb0  popped n=1 ra=0x00010034
      ret  a0=2  sp=0x7fffffc0  popped n=2 ra=0x00010034
    ret  a0=6  sp=0x7fffffd0  popped n=3 ra=0x00010034
  ret  a0=24  sp=0x7fffffe0  popped n=4 ra=0x00010034
ret  a0=120  sp=0x7ffffff0  popped n=5 ra=0x00010008
fact(5) = 120 | calls=5, max depth=5, stack used=80 bytes, lowest sp=0x7fffffa0, instructions=58
fib(6) = 8 | calls=25, max depth=6, stack used=96 bytes, lowest sp=0x7fffff90, instructions=336

Stack-এর গভীরতা আর stack overflow

Recursion-এর stack-খরচের সূত্র সরল: সর্বোচ্চ stack ব্যবহার = সর্বোচ্চ গভীরতা × প্রতিটি frame-এর আকার (frame-এর আকার ভিন্ন হলে প্রতিটির যোগফল)। fact(n)-এর গভীরতা n, তাই ১৬-byte frame-এ fact(১০০০০) লাগবে ১,৬০,০০০ byte. Stack-এর একটি সীমা আছে; সীমা পেরোলে stack overflow — Linux-এ সাধারণত stack-এর নিচে রাখা একটি “guard page” ছুঁয়ে ফেলায় page fault, আর OS প্রোগ্রামটিকে SIGSEGV দিয়ে বন্ধ করে দেয় (C-এর দিক থেকে দেখুন C কোর্সের stack overflow অংশ)। বাস্তবের একটি compiled প্রোগ্রামে frame কত বড়, চলুন মেপে দেখি। নিচের C প্রোগ্রাম পরপর recursive call-এ একটি local-এর ঠিকানা কতটা সরে, তা ছাপে (পূর্ণ ঠিকানা নয় — সেগুলো ASLR-এর কারণে প্রতিবার বদলায়), আর দেখায় যে pointer দিয়ে callee caller-এর frame-এ লিখতে পারে:

#include <stdio.h>
#include <stdint.h>

static intptr_t where[6];            /* address of 'local' in each recursive call */

__attribute__((noinline)) static int depth(int n) {
    volatile int local = n;          /* lives in THIS call's stack frame */
    where[n] = (intptr_t)&local;
    if (n == 5) return local;
    return depth(n + 1) + local;     /* work after the call: not a tail call */
}

__attribute__((noinline)) static void add_bonus(int *p) {
    volatile int mine = 0;           /* the callee's own local */
    *p += 100;                       /* writes into the CALLER's frame */
    printf("callee: p is %s my own local\n", (intptr_t)p > (intptr_t)&mine ? "ABOVE" : "below");
}

int main(void) {
    printf("depth(0) returned %d\n", depth(0));
    for (int i = 1; i < 6; i++)
        printf("call %d -> call %d: &local moved down by %ld bytes\n",
               i - 1, i, (long)(where[i - 1] - where[i]));
    int marks = 70;
    add_bonus(&marks);
    printf("main: marks = %d after add_bonus(&marks)\n", marks);
    return 0;
}

depth(0) returned 15
call 0 -> call 1: &local moved down by 48 bytes
call 1 -> call 2: &local moved down by 48 bytes
call 2 -> call 3: &local moved down by 48 bytes
call 3 -> call 4: &local moved down by 48 bytes
call 4 -> call 5: &local moved down by 48 bytes
callee: p is ABOVE my own local
main: marks = 170 after add_bonus(&marks)

এবার জানি stack-এর সীমা কত। Linux-এ main thread-এর stack-এর সীমা shell-এর ulimit -s দিয়ে দেখা যায় (KiB এককে)। কোর্সের runner-এ চালিয়ে দেখুন:

# How big may the main thread's stack grow here? (ulimit is a bash builtin)
soft=$(ulimit -s 2>/dev/null || echo "?")
hard=$(ulimit -Hs 2>/dev/null || echo "?")
echo "stack limit in KiB: soft=$soft hard=$hard"
if [ -r /proc/self/limits ]; then
  grep -i "max stack size" /proc/self/limits
else
  echo "/proc/self/limits not available"
fi
case "$soft" in
  ''|*[!0-9]*) echo "no numeric limit, skipping the estimate" ;;
  *) echo "48-byte frames that fit: about $(( soft * 1024 / 48 ))"
     echo "1 KiB frames that fit:   about $(( soft ))" ;;
esac

stack limit in KiB: soft=8192 hard=unlimited
Max stack size            8388608              unlimited            bytes
48-byte frames that fit: about 174762
1 KiB frames that fit:   about 8192

৬ · আটটির বেশি argument, struct, varargs আর tail call

আটটির বেশি argument

a0–a7 ভরে গেলে বাকি argument যায় stack-এ। নিয়মটি হলো: call-এর মুহূর্তে caller-এর sp থেকে শুরু করে — নবম argument 0(sp)-এ, দশম 4(sp)-এ (RV32-এ প্রতিটি int ৪ byte), এভাবে ওপরের দিকে। Caller এই জায়গা নিজের frame-এর তলায় আগেই রেখে দেয় (অংশ ৪-এর টেবিলের “outgoing argument”), আর callee নিজের frame নেওয়ার পরে সেগুলো পড়ে নিজের frame-এর ওপারে: নিজের frame ৩২ byte হলে নবম argument 32(sp)-এ। বাস্তবে আটটির বেশি argument বিরল, আর প্রতিটি বাড়তি argument মানে একটি মেমরি-লেখা ও মেমরি-পড়া; এজন্য অনেক argument লাগলে সেগুলো একটি struct-এ জড়ো করে pointer পাঠানো প্রচলিত কৌশল।

Struct আর বড় return value

RISC-V psABI-র নিয়ম মোটামুটি এমন (বিস্তারিত নিয়মে বেশ কিছু ব্যতিক্রম আছে, যেমন float-সদস্যের struct — আসল নথি দেখুন): যে struct দুই word (২ × XLEN) পর্যন্ত বড়, তা register-এ যায় — এক বা দুটি a register-এ, register ফুরিয়ে গেলে অংশত stack-এ। এর চেয়ে বড় struct-এর জন্য caller একটি কপি বানিয়ে তার ঠিকানা পাঠায় (pass by reference). Return value-ও একই ধাঁচে: দুই word পর্যন্ত a0/a1-এ; আরও বড় হলে caller ফলের জন্য জায়গা নিয়ে তার ঠিকানা একটি লুকানো প্রথম argument হিসেবে a0-তে দেয়, আর callee সেখানে লেখে। RV32-এ ৬৪-বিটের long long বা double (soft-float) এক জোড়া register নেয়: a0 নিচের word, a1 ওপরের word.

Varargs — printf-এর মতো function

printf(const char *fmt, ...)-এর মতো variadic function-এ callee আগে জানে না কয়টি argument এসেছে। RISC-V-এ variadic argument-ও সাধারণ integer register-এ (a register-এ) আসে, তবে কিছু বিশেষ নিয়মসহ (যেমন RV32-এ ৮-byte-এ aligned মান একটি জোড়-বিজোড় register-জোড়ায়)। Callee-র prologue সাধারণত বাকি a register-গুলো stack-এ লিখে ফেলে, যাতে stack-এ রাখা argument-এর ঠিক পাশে একটি অবিচ্ছিন্ন সারি তৈরি হয়; তারপর va_arg সেই মেমরি-সারি ধরে একটি একটি করে পড়ে। কয়টি আর কোন ধরনের argument, তা জানার একমাত্র উপায় format string — তাই printf("%d %d", x) লিখলে দ্বিতীয় %d যা-ই পড়ে, তা আবর্জনা। অন্য ABI-তে variadic নিয়ম আলাদা হতে পারে (যেমন Apple-এর ARM64-এ variadic argument সবসময় stack-এ)।

Tail call — jal-এর বদলে j

একটি function-এর শেষ কাজ যদি অন্য একটি function ডেকে তার ফলই ফেরত দেওয়া হয় — return g(x + 1); — তাহলে নিজের frame রেখে অপেক্ষা করার কিছু নেই। g-এর ফল সরাসরি আমাদের caller-এর কাছে গেলেই চলে। তাই compiler আমাদের frame খুলে ফেলে, ra যেমন আছে তেমন রেখে (ra-তে তো আমাদের caller-এর ঠিকানাই আছে), jal-এর বদলে শুধু লাফ দেয় — j g বা tail g. g যখন ret করবে, সোজা আমাদের caller-এ ফিরবে। একে বলে tail call optimization. Wandbox-এর gcc (x86-64) -O2-এ এই দুটি function যা বানাল, আর RISC-V-এ একই জিনিস কেমন দেখায়:

/* C */
int f(int x) { return g(x + 1); }     /* tail call      */
int h(int x) { return g(x) + 1; }     /* NOT a tail call */

# x86-64, gcc -O2              # RV32 equivalent
f:  addl  $1, %edi             f:  addi a0, a0, 1
    jmp   g        # tail call      tail g          # jump, ra untouched
h:  subq  $8, %rsp # align 16  h:  addi sp, sp, -16
    call  g                         sw   ra, 12(sp)
    addq  $8, %rsp                  call g
    addl  $1, %eax                  lw   ra, 12(sp)
    ret                             addi a0, a0, 1
                                    addi sp, sp, 16
                                    ret

f-এ কোনো frame নেই, ফেরার ঠিকানাও রাখা হয়নি — একটি যোগ আর একটি লাফ। h-এ g-এর পরে আরও কাজ (+১) আছে, তাই tail call সম্ভব নয়: পুরো call-return লাগল। x86-64-এর subq $8, %rsp-টি মজার — কোনো local রাখার জন্য নয়, শুধু alignment-এর জন্য (অংশ ৭). Recursion-এ tail call আরও বড় উপকার করে: fact_acc(n, acc) { return n < 2 ? acc : fact_acc(n − 1, n * acc); }-এর মতো tail-recursive function stack-এ একটিও নতুন frame না নিয়ে একটি লুপ হয়ে যায়। এমনকি আমাদের সাধারণ fact-কেও gcc -O2 (এই পর্ব লেখার সময় Wandbox-এ পরীক্ষা করা) পুরোপুরি একটি গুণের লুপে বদলে ফেলেছে — কোনো call-ই নেই। তবে C standard tail call-এর কোনো নিশ্চয়তা দেয় না; optimization বন্ধ থাকলে (-O0) বা function-এর local-এর ঠিকানা বাইরে গেলে তা হয় না। Scheme-এর মতো কিছু ভাষা নিয়মেই tail call বাধ্যতামূলক করে; আর Clang-এ [[clang::musttail]] নামে একটি extension আছে।

৭ · অন্য ISA-র convention — x86-64, Windows x64 আর ARM64

চিন্তা সব জায়গায় একই — argument register, caller/callee-saved ভাগ, নিচে-নামা stack, ১৬-byte alignment. পার্থক্য register-এর নাম-সংখ্যায় আর ফেরার ঠিকানা কোথায় থাকে তাতে। নিচের টেবিল মূল কথাগুলো ধরে; প্রতিটি ABI-তে আরও অনেক খুঁটিনাটি নিয়ম আছে (float, struct, variadic), যার জন্য আসল নথি দেখুন। C থেকে কোন compiler কী বানায়, তা বিস্তারিত পর্ব ৩১-এ।

x86-64-এ return address stack-এ। x86-এর call instruction নিজেই ফেরার ঠিকানা (৮ byte) stack-এ push করে, আর ret তা pop করে লাফ দেয়; push/pop instruction-ও আছে যা rsp বদলায় আর একই সাথে মেমরিতে লেখে বা পড়ে। ফলে leaf function-এও প্রতিটি call-এ একটি মেমরি-লেখা আর একটি মেমরি-পড়া হয় — RISC-V বা ARM-এর leaf function-এ যা লাগে না। আর alignment-এর নিয়মটি “call-এর আগে rsp ১৬-এর গুণিতক” বলে, callee-তে ঢোকার মুহূর্তে rsp থাকে ১৬-এর গুণিতক + ৮ (return address-এর জন্য)। এজন্যই উপরের h-এ gcc subq $8, %rsp লিখেছিল: আরেকটি call-এর আগে আবার ১৬-এ মেলাতে।

Red zone (System V): leaf function rsp না কমিয়েই rsp-এর নিচের ১২৮ byte নিজের local-এর জন্য ব্যবহার করতে পারে — চুক্তি হলো, signal handler বা interrupt এই এলাকা মুছবে না। এতে ছোট leaf function-এ sp বদলানোর দুটি instruction বাঁচে। Linux kernel নিজের কোডে red zone বন্ধ রাখে (-mno-red-zone), কারণ সেখানে interrupt একই stack ব্যবহার করে। Shadow space (Windows x64; একে home space-ও বলে): caller সবসময় stack-এ ৩২ byte জায়গা রেখে দেয়, যেখানে callee চাইলে চারটি register-argument লিখে রাখতে পারে — debugging আর variadic function সহজ হয়। RISC-V-এ এর কোনোটিই নেই।

ARM64 নকশায় RISC-V-এর সবচেয়ে কাছে: bl f ফেরার ঠিকানা রাখে link register x30 (lr)-এ, ret সেখানে ফেরে, আর non-leaf function prologue-এ সাধারণত stp x29, x30, [sp, #-16]! দিয়ে frame pointer আর lr একসাথে stack-এ রাখে। x9–x15 temporary (caller-saved), x19–x28 callee-saved. Apple-এর platform-এর ABI কিছু জায়গায় আলাদা (যেমন x18 সংরক্ষিত)। ৩২-বিটের পুরোনো ARM (AAPCS32)-এ argument ছিল r0–r3, lr = r14.

৮ · Stack আর নিরাপত্তা — return address রক্ষা করা

Stack frame-এ দুটি ভিন্ন জাতের জিনিস পাশাপাশি থাকে: প্রোগ্রামের ডেটা (local array, যেমন একটি নামের buffer) আর প্রোগ্রামের নিয়ন্ত্রণ-তথ্য (saved ra — কোথায় ফিরতে হবে)। আর একটি সূক্ষ্ম জ্যামিতি আছে: stack নিচের দিকে বাড়ে, কিন্তু একটি array-র উপাদান থাকে ওপরের দিকে (buf[0], buf[1], … ক্রমে বড় ঠিকানায়)। ফলে কোনো কোড যদি একটি local array-তে তার আকারের চেয়ে বেশি byte লেখে, বাড়তি byte গিয়ে পড়ে array-র ওপরে — যেখানে সাধারণত saved register আর saved return address থাকে। একে বলে stack buffer overflow.

সবচেয়ে নিরীহ ফল হলো crash — ret একটি অর্থহীন ঠিকানায় লাফ দেয় আর OS প্রোগ্রাম বন্ধ করে। কিন্তু input যদি বাইরের কারও নিয়ন্ত্রণে থাকে (নেটওয়ার্ক থেকে আসা ডেটা, একটি ফাইল), সে saved return address-এর জায়গায় নিজের পছন্দের মান বসিয়ে প্রোগ্রামের নিয়ন্ত্রণ নিতে পারে। ১৯৮৮ সালের Morris worm-এর ছড়ানোর একটি পথ ছিল ঠিক এমন একটি ত্রুটি — Unix-এর fingerd সার্ভিস gets() দিয়ে সীমাহীনভাবে input পড়ত। কয়েক দশক ধরে এই এক শ্রেণির বাগ বহু গুরুতর নিরাপত্তা-ঘটনার কারণ হয়েছে। এখানে আমরা শুধু ধারণা আর প্রতিরক্ষা দেখব; আক্রমণের কৌশল এই কোর্সের বিষয় নয়।

প্রতিরক্ষার স্তরগুলো

এগুলো সব “দ্বিতীয় দেয়াল”। প্রথম আর সবচেয়ে কার্যকর দেয়াল হলো বাগটিই না রাখা: input-এর আকার যাচাই, আর এমন API ব্যবহার যা buffer-এর আকার জানে — bounds checking. নিচে ঝুঁকিপূর্ণ আর নিরাপদ রূপ পাশাপাশি (শুধু উদাহরণ; চালানোর জন্য নয়)। বিস্তারিত দেখুন C কোর্সের undefined behavior ও নিরাপদ কোডিং পর্বে আর OS-এর দিক থেকে OS নিরাপত্তা পর্বে।

char name[16];

/* risky: no idea how big 'name' is */
strcpy(name, input);                  /* overflows if input has 16+ chars */
gets(name);                           /* removed from C11 -- never use    */

/* safer: the size travels with the buffer */
snprintf(name, sizeof name, "%s", input);   /* truncates, always ends with '\0' */
fgets(name, sizeof name, stdin);            /* reads at most 15 chars + '\0'   */
if (strlen(input) >= sizeof name) { /* reject the input explicitly */ }

আরও কয়েকটি অভ্যাস: compiler warning চালু রাখা (-Wall -Wextra), পরীক্ষার সময় AddressSanitizer (-fsanitize=address) — যা সীমার বাইরের প্রতিটি লেখা হাতেনাতে ধরে, -D_FORTIFY_SOURCE=2-এর মতো library-যাচাই, আর যেখানে সম্ভব Rust-এর মতো memory-safe ভাষা। বড় সফটওয়্যার কোম্পানি আর সরকারি নিরাপত্তা সংস্থাগুলোও সাম্প্রতিক বছরগুলোতে memory-safe ভাষার দিকে যাওয়ার পরামর্শ দিচ্ছে।

৯ · AI-এর যুগে calling convention আর stack

AI টুল assembly-তে একটি recursive function দ্রুত লিখে দিতে পারে, কিন্তু এই বিষয়ে তার ভুলগুলো খুব চেনা — আর বেশিরভাগই এমন, যা কোড চালানো পর্যন্ত ধরা পড়ে না, বা কাকতালীয়ভাবে চলে যায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Register-এর নাম আর instruction সব RISC-V-এর — কোনো $-চিহ্ন, jr $ra বা x86-এর push ঢুকে পড়েনি
• প্রতিটি non-leaf function prologue-এ ra রাখে আর epilogue-এ ফিরিয়ে আনে; ব্যবহৃত প্রতিটি s register-ও
• প্রতিটি jal/call-এর পরে কোনো t বা a register-এর পুরোনো মান পড়া হচ্ছে না
• Frame-এর আকার ১৬-এর গুণিতক, আর prologue-epilogue-এর offset হুবহু মেলে
• ছোট একটি input-এ হাতে trace করে দেখেছি: ফেরার সময় sp শুরুর মানে ফেরে আর ফল ঠিক
• Simulator বা আসল hardware-এ চালিয়েছি; x86/ARM-এর দাবি থাকলে ABI নথি বা Compiler Explorer-এ মিলিয়েছি