xv6 — একটি ছোট শিক্ষণ-OS-এর ভেতরে ঘোরা

১ · কেন একটি “খেলনা” OS — আসলে খেলনা নয়

এতগুলো পর্বে আপনি process, scheduling, lock, paging আর file system আলাদা আলাদা শিখেছেন। কিন্তু একটি প্রশ্ন থেকেই যায়: এগুলো একটি আসল kernel-এ একসাথে কীভাবে বসে? Linux kernel-এ উত্তর আছে, কিন্তু তার সোর্স কয়েক কোটি লাইনের। একজন মানুষ সারাজীবনেও পুরোটা পড়তে পারবেন না।

সমাধান হলো একটি শিক্ষণ-OS — এমন একটি সম্পূর্ণ, চালানো যায় এমন অপারেটিং সিস্টেম, যা ইচ্ছা করেই ছোট আর সরল রাখা হয়েছে। এতে আসল process, আসল page table, আসল disk driver আছে; শুধু অপ্রয়োজনীয় জটিলতা নেই।

xv6-এর সঙ্গী একটি ছোট বই: “xv6: a simple, Unix-like teaching operating system”, লেখক Russ Cox, Frans Kaashoek আর Robert Morris — MIT-র ওয়েবসাইটে বিনামূল্যে পাওয়া যায়। এই পর্বের প্রতিটি অংশ ওই বইয়ের এক-একটি অধ্যায়ের সাথে মেলে; পর্বটি শেষ করে বইটি ধরলে অনেক সহজ লাগবে।

সোর্সের মানচিত্র — কোন ফাইলে কী

xv6-এর repository-তে দুটি প্রধান ফোল্ডার: kernel/ আর user/. ২০২৬ সালের অক্টোবরের riscv branch-এ kernel/-এর ৪৪টি ফাইলে মোট প্রায় ৬,৬০০ লাইন — header আর assembly মিলিয়ে। সংখ্যাটি version-ভেদে কিছুটা বদলায়, কিন্তু মাত্রাটা একই: কয়েক হাজার লাইন, কয়েক কোটি নয়।

নিচের টেবিলটি এই পর্বের মানচিত্র। ডান দিকের কলাম বলছে, কোর্সের কোন পর্বের ধারণা কোন ফাইলে কোড হয়ে বসেছে।

Hardware হিসেবে xv6 চলে QEMU-র virt নামের একটি কাল্পনিক RISC-V বোর্ডে: ১২৮ MiB RAM, একটি UART serial port (কীবোর্ড আর স্ক্রিন), একটি virtio disk, একটি PLIC interrupt controller আর ডিফল্টভাবে ৩টি CPU core — RISC-V-এর ভাষায় ৩টি hart. Physical memory-র মানচিত্র memlayout.h-এ লেখা: UART থাকে 0x10000000-এ, disk 0x10001000-এ, আর RAM শুরু হয় 0x80000000 থেকে।

২ · বুট — বিদ্যুৎ থেকে $ prompt পর্যন্ত

পর্ব ০৭-এ দেখেছিলেন, একটি PC-তে firmware (BIOS বা UEFI) → bootloader → kernel → init — এই শিকল। xv6-এ শিকলটি অনেক ছোট, কারণ QEMU নিজেই kernel ফাইলটি RAM-এর 0x80000000 ঠিকানায় বসিয়ে দেয়; আলাদা bootloader লাগে না। প্রতিটি CPU core সেখান থেকে চলা শুরু করে।

RISC-V-এ তিনটি privilege স্তর আছে। সবচেয়ে ক্ষমতাবান machine mode (M) — চালু হওয়ার সময় CPU এখানে থাকে। Kernel চলে supervisor mode-এ (S), আর সাধারণ প্রোগ্রাম user mode-এ (U). xv6 machine mode-এ থাকে মাত্র কয়েক লাইন — দরকারি সেটিং করেই নেমে আসে supervisor mode-এ।

// start() jumps here in supervisor mode on all CPUs.
void
main()
{
  if (cpuid() == 0) {
    consoleinit();
    printkinit();
    printk("\n");
    printk("xv6 kernel is booting\n");
    printk("\n");
    kinit();            // physical page allocator
    kvminit();          // create kernel page table
    kvminithart();      // turn on paging
    procinit();         // process table
    trapinit();         // trap vectors
    trapinithart();     // install kernel trap vector
    plicinit();         // set up interrupt controller
    plicinithart();     // ask PLIC for device interrupts
    binit();            // buffer cache
    iinit();            // inode table
    fileinit();         // file table
    virtio_disk_init(); // emulated hard disk
    userinit();         // first user process
    /* ... then tell the other harts to start ... */
  }
  /* ... other harts: kvminithart(), trapinithart(), plicinithart() ... */
  scheduler();
}

লক্ষ করুন, main() নিজেই একটি সূচিপত্র — প্রতিটি লাইন একটি subsystem, আর প্রায় প্রতিটি কোর্সের একটি পর্ব। ক্রমটিও অর্থপূর্ণ: page table বানাতে খালি পাতা লাগে, তাই kinit() আগে; প্রথম প্রসেস বানাতে প্রসেস টেবিল লাগে, তাই procinit() আগে। নিচের stepper-এ পুরো যাত্রাটি দেখুন:

1 QEMU: kernel -> RAM 0x800000002 entry.S: sp = stack0 + (hartid+1)*40963 start(): mepc = main; mret -> S-mode4 main(): kinit ... virtio_disk_init5 userinit(): allocproc -> pid 16 scheduler(): swtch -> forkret7 forkret(): fsinit; kexec("/init")8 init: open console; fork; exec("sh")9 sh: write(2, "$ ", 2)

৩ · প্রসেস, scheduler আর swtch

পর্ব ০৮-এ xv6-এর struct proc পুরোটা দেখেছিলেন — state, pid, parent, kernel stack, page table, trapframe, context, খোলা ফাইলের অ্যারে। এখানে মনে রাখুন শুধু ছয়টি অবস্থা:

enum procstate { UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };

পাঠ্যবইয়ের পাঁচ-অবস্থার মডেলের (পর্ব ০৮) সাথে মিলিয়ে নিন: RUNNABLE হলো ready, SLEEPING হলো waiting/blocked, ZOMBIE হলো terminated কিন্তু parent এখনো wait() করেনি (zombie). বাড়তি দুটি — UNUSED মানে টেবিলের ঘরটি খালি, আর USED মানে ঘরটি নেওয়া হয়েছে কিন্তু প্রসেস তৈরি এখনো শেষ হয়নি। xv6-এ প্রসেস টেবিল একটি স্থির অ্যারে, struct proc proc[NPROC], যেখানে NPROC = ৬৪ — তাই ৬৫তম প্রসেস তৈরি হয় না, fork() −১ ফেরত দেয়।

Scheduler — একটি অন্তহীন লুপ

পর্ব ১৮-এর round robin মনে আছে? xv6-এর scheduler তার সবচেয়ে সরল রূপ। প্রতিটি CPU-র নিজের একটি scheduler লুপ, যা প্রসেস টেবিলের ওপর দিয়ে বারবার ঘোরে আর প্রথম যে RUNNABLE প্রসেস পায়, তাকে চালায়:

void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();

  c->proc = 0;
  for (;;) {
    intr_on();
    intr_off();

    int found = 0;
    for (p = proc; p < &proc[NPROC]; p++) {
      acquire(&p->lock);
      if (p->state == RUNNABLE) {
        p->state = RUNNING;
        c->proc = p;
        swtch(&c->context, &p->context);

        // Don't re-enable interrupts on release.
        mycpu()->intena = 0;

        c->proc = 0;
        found = 1;
      }
      release(&p->lock);
    }
    if (found == 0) {
      // nothing to run; stop running on this core until an interrupt.
      asm volatile("wfi");
    }
  }
}

কোনো priority নেই, কোনো আলাদা ready queue নেই — ready queue আসলে পুরো proc[] অ্যারে, আর “ক্রম” হলো অ্যারের সূচি। Time quantum হলো timer interrupt-এর ব্যবধান: start.c প্রথম timer বসায় ১০ লাখ টিক পরে (QEMU-তে মোটামুটি ১০০ মিলিসেকেন্ড), আর প্রতিটি timer interrupt-এ usertrap() চলমান প্রসেসকে yield() করায়। কিছুই চালানোর না থাকলে wfi (wait for interrupt) — CPU ঘুমায়, বিদ্যুৎ বাঁচে।

swtch — ১৪টি register রাখা, ১৪টি ফেরত আনা

পর্ব ০৯-এ context switch-এর তত্ত্ব দেখেছিলেন। xv6-এ পুরো কাজটি swtch.S-এর একটি ফাংশন: আগের context-এ ra, sp আর s0–s11 লেখে (১৪টি sd), তারপর নতুন context থেকে একই ১৪টি পড়ে (১৪টি ld), তারপর ret. মোট ২৯টি instruction.

মাত্র ১৪টি কেন, ৩২টি নয়? কারণ swtch একটি সাধারণ C ফাংশনের মতো ডাকা হয়। RISC-V-এর calling convention বলে, ডাকা ফাংশন (callee) শুধু callee-saved register-গুলো (s0–s11, সাথে sp) অক্ষত রাখার দায় নেয়; বাকিগুলো ডাকার আগে caller-এর compiler নিজেই প্রয়োজনমতো stack-এ রেখে দেয়। আর user প্রোগ্রামের সব register? সেগুলো আগেই trapframe-এ জমা হয়েছে, kernel-এ ঢোকার মুহূর্তে (অংশ ৪)।

আরেকটি সূক্ষ্ম বিষয়: xv6-এ এক প্রসেস থেকে সরাসরি আরেক প্রসেসে switch হয় না। পথটি সবসময় প্রসেস A → সেই CPU-র scheduler → প্রসেস B — দুটি swtch. প্রসেস A sched() ডেকে swtch(&p->context, &mycpu()->context) করে scheduler-এ ফেরে, আর scheduler তখন ঠিক swtch-এর পরের লাইন থেকে চলতে থাকে — যেন ফাংশনটি সবে ফেরত এসেছে।

Sleep আর wakeup — condition variable-এর পূর্বপুরুষ

প্রসেস যখন কিছুর জন্য অপেক্ষা করে (disk-এর ব্লক, pipe-এ ডেটা, সন্তানের exit), তখন সে CPU আটকে রাখে না — ঘুমায়। ঘুমায় একটি channel-এর ওপর, যা আসলে যেকোনো একটি ঠিকানা (যেমন disk buffer-এর ঠিকানা)। যে ঘটনাটি ঘটায়, সে wakeup(chan) ডাকে, আর সেই channel-এ ঘুমন্ত সবাই RUNNABLE হয়। বইয়ে আর ২০২৫ সালের সংস্করণে (git tag xv6-riscv-rev5) sleep দেখতে এমন:

void
sleep(void *chan, struct spinlock *lk)
{
  struct proc *p = myproc();

  acquire(&p->lock);  //DOC: sleeplock1
  release(lk);

  // Go to sleep.
  p->chan = chan;
  p->state = SLEEPING;

  sched();

  // Tidy up.
  p->chan = 0;

  // Reacquire original lock.
  release(&p->lock);
  acquire(lk);
}

পর্ব ২৫-এর condition variable-এর সাথে মিলটি স্পষ্ট: pthread_cond_wait(&cv, &m) যেমন mutex ছেড়ে ঘুমায় আর জেগে আবার mutex নেয়, এখানেও তাই। কেন lk নিয়ে ঢুকতে হয়? কারণ “শর্ত মিথ্যা দেখলাম” আর “ঘুমিয়ে পড়লাম” — এর মাঝখানে কেউ wakeup ডেকে ফেললে সংকেতটি হারিয়ে যায় (lost wakeup), আর প্রসেস চিরকাল ঘুমায়। এখানে p->lock ধরার পরে lk ছাড়া হয়, আর wakeup-কেও p->lock নিতে হয় — তাই মাঝখানে ফাঁক থাকে না। জেগে ওঠার পর শর্তটি আবার যাচাই করতে হয় (while লুপে), কারণ একই channel-এ একাধিকজন জাগতে পারে।

৪ · System call — একটি write-এর পুরো যাত্রা

পর্ব ০৫-এ system call-কে বলেছিলেন user mode থেকে kernel mode-এ যাওয়ার নিয়ন্ত্রিত দরজা। xv6-এ দরজাটির প্রতিটি কবজা দেখা যায়। শুরু user দিক থেকে। user/usys.pl নামের একটি Perl script প্রতিটি system call-এর জন্য তিন লাইনের assembly stub তৈরি করে:

.global write
write:
 li a7, SYS_write     # system call number (16) into a7
 ecall                # trap into the kernel
 ret                  # a0 now holds the return value

RISC-V-এর calling convention অনুযায়ী write(fd, buf, n)-এর তিনটি argument আগে থেকেই a0, a1, a2-তে আছে। Stub শুধু নম্বরটি a7-এ রাখে আর ecall চালায়। ecall একটি বিশেষ instruction: CPU সাথে সাথে supervisor mode-এ যায়, কারণ-register scause-এ লেখে ৮ (“user mode থেকে ecall”), sepc-তে রাখে ecall-এর নিজের ঠিকানা, আর লাফ দেয় stvec register যে ঠিকানা দেখায় সেখানে — xv6-এ সেটি uservec.

এখানে একটি মজার সমস্যা আছে। ecall-এর পরেও CPU চলছে user-এর page table দিয়ে — RISC-V নিজে থেকে page table বদলায় না। তাহলে kernel-এর কোড user-এর ঠিকানা-জগতে কীভাবে দেখা যাবে? xv6-এর উত্তর trampoline page: trampoline.S-এর কোড একটি পাতায় রাখা হয়, আর সেই পাতাটি প্রতিটি user page table-এ এবং kernel page table-এ একই virtual address-এ (TRAMPOLINE, ঠিকানা-জগতের একদম ওপরে) map করা থাকে। ফলে page table বদলানোর মুহূর্তেও পরের instruction একই ঠিকানায় পাওয়া যায়। তার ঠিক নিচের পাতায় থাকে প্রতিটি প্রসেসের trapframe — user-এর ৩১টি general register (x0 সবসময় শূন্য, তাই সেটি বাদ) আর কয়েকটি kernel-তথ্য জমা রাখার জায়গা।

1 sh getcmd(): write(2, "$ ", 2)2 usys.S: li a7, 16; ecall3 uservec: regs -> TRAPFRAME; satp = kernel4 usertrap(): scause 8; epc += 4; syscall()5 syscall(): syscalls[16] = sys_write6 sys_write: argaddr/argint/argfd7 filewrite -> consolewrite -> uartwrite8 a0 = 2; prepare_return; userret; sret

বণ্টনের হৃদয়টি মাত্র কয়েক লাইন। syscalls হলো function pointer-এর একটি অ্যারে, যার সূচি system call নম্বর — পর্ব ০৫-এর syscall table-এর সবচেয়ে স্বচ্ছ রূপ:

static uint64 (*syscalls[])(void) = {
  [SYS_fork]    = sys_fork,
  [SYS_exit]    = sys_exit,
  /* ... */
  [SYS_getpid]  = sys_getpid,
  /* ... */
  [SYS_write]   = sys_write,
  /* ... */
};

void
syscall(void)
{
  int num;
  struct proc *p = myproc();

  num = p->trapframe->a7;
  if (num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();
  } else {
    printk("%d %s: unknown sys call %d\n", p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

এবার একই কাঠামো একটি ছোট simulator-এ চালিয়ে দেখুন। এখানে trapframe একটি সাধারণ JavaScript object, user মেমরি একটি ছোট map, আর নম্বরগুলো xv6-এর আসল syscall.h থেকে নেওয়া:

// xv6-style system call dispatch, simulated. Numbers from kernel/syscall.h.
const SYS_getpid = 11, SYS_uptime = 14, SYS_write = 16, NOFILE = 16;
const proc = { pid: 2, name: "sh", ofile: ["console", "console", "console"], trapframe: {} };
const umem = { 0x1f40: "$ " };           // pretend user memory: address -> bytes
let screen = "";
const argraw = n => proc.trapframe["a" + n];
const argint = n => argraw(n) | 0;       // 32-bit integer argument
const argaddr = n => argraw(n);          // pointer argument, checked later by copyin
function sys_getpid() { return proc.pid; }
function sys_uptime() { return 37; }     // ticks since boot (fixed for the demo)
function sys_write() {
  const p = argaddr(1), n = argint(2), fd = argint(0);
  if (fd < 0 || fd >= NOFILE || !proc.ofile[fd]) return -1;  // argfd() fails
  const bytes = (umem[p] || "").slice(0, n);                  // copyin from user memory
  screen += bytes;
  return bytes.length;
}
const syscalls = [];
syscalls[SYS_getpid] = sys_getpid; syscalls[SYS_uptime] = sys_uptime; syscalls[SYS_write] = sys_write;
function syscall() {
  const num = proc.trapframe.a7;
  if (num > 0 && num < syscalls.length && syscalls[num]) proc.trapframe.a0 = syscalls[num]();
  else { console.log(proc.pid + " " + proc.name + ": unknown sys call " + num); proc.trapframe.a0 = -1; }
}
function ecall(num, a0 = 0, a1 = 0, a2 = 0) {   // what the stub + uservec + usertrap do
  proc.trapframe = { a0, a1, a2, a7: num };
  syscall();
  return proc.trapframe.a0;
}
console.log("getpid()             a0 =", ecall(SYS_getpid));
console.log("write(2, 0x1f40, 2)  a0 =", ecall(SYS_write, 2, 0x1f40, 2), " screen:", JSON.stringify(screen));
console.log("write(9, 0x1f40, 2)  a0 =", ecall(SYS_write, 9, 0x1f40, 2));
console.log("uptime()             a0 =", ecall(SYS_uptime));
console.log("ecall 22 (sync)      a0 =", ecall(22));
console.log("table length", syscalls.length, "- slots filled:", syscalls.filter(Boolean).length);

getpid()             a0 = 2
write(2, 0x1f40, 2)  a0 = 2  screen: "$ "
write(9, 0x1f40, 2)  a0 = -1
uptime()             a0 = 37
2 sh: unknown sys call 22
ecall 22 (sync)      a0 = -1
table length 17 - slots filled: 3

৫ · মেমরি — Sv39, walk() আর kalloc

খালি পাতার হিসাব — kalloc.c

পর্ব ৩১-এ বিভিন্ন allocator দেখেছিলেন — first fit, buddy, slab. xv6-এর physical memory allocator সবচেয়ে সরল: সব পাতা একই আকারের (৪০৯৬ byte), তাই fragmentation-এর প্রশ্নই নেই। খালি পাতাগুলো একটি free list-এ সাজানো, আর সেই list-এর next pointer রাখা থাকে খালি পাতার ভেতরেই — আলাদা কোনো হিসাবের খাতা লাগে না।

struct run {
  struct run *next;
};

void
kfree(void *pa)
{
  struct run *r;
  /* ... panic if pa is not page-aligned or outside [end, PHYSTOP) ... */
  memset(pa, 1, PGSIZE);   // Fill with junk to catch dangling refs.
  r = (struct run *)pa;
  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

void *
kalloc(void)
{
  struct run *r;
  acquire(&kmem.lock);
  r = kmem.freelist;
  if (r)
    kmem.freelist = r->next;
  release(&kmem.lock);
  if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk
  return (void *)r;
}

kinit() kernel-এর শেষ (end) থেকে PHYSTOP (0x80000000 + ১২৮ MiB) পর্যন্ত প্রতিটি পাতায় kfree ডাকে। ফলে list-এর মাথায় থাকে সবচেয়ে উঁচু ঠিকানার পাতা। একই ধারণাটি নিচে user space-এ, একটি static অ্যারের ওপর — চারটি “পাতা” নিয়ে। ঠিকানা প্রতিবার আলাদা হতে পারে, তাই প্রোগ্রাম ঠিকানা না ছেপে পাতার ক্রমিক নম্বর ছাপে:

#include <stdio.h>
#include <string.h>
#define PGSIZE 4096
#define NPAGES 4
struct run { struct run *next; };                  // same trick as xv6's kalloc.c
static _Alignas(PGSIZE) char mem[NPAGES * PGSIZE]; // our fake "physical memory"
static struct run *freelist;
static int pg(void *p) { return (int)(((char *)p - mem) / PGSIZE); }
static void kfree(void *pa) {
  char *c = pa;
  if (c < mem || c >= mem + sizeof mem || (c - mem) % PGSIZE) { printf("panic: kfree\n"); return; }
  memset(pa, 1, PGSIZE);                           // junk, to catch dangling pointers
  struct run *r = pa; r->next = freelist; freelist = r;   // push on the front
}
static void *kalloc(void) {
  struct run *r = freelist;                        // pop from the front
  if (r) { freelist = r->next; memset(r, 5, PGSIZE); }  return r;
}
static void show(const char *what) {
  printf("%-20s free:", what);
  for (struct run *r = freelist; r; r = r->next) printf(" [%d]", pg(r));
  printf("%s\n", freelist ? "" : " (empty)");
}
int main(void) {
  for (char *p = mem; p + PGSIZE <= mem + sizeof mem; p += PGSIZE) kfree(p);  // kinit
  show("after kinit");
  char *a = kalloc(), *b = kalloc();
  printf("kalloc -> page %d, page %d; a[0] = %d, a[100] = %d\n", pg(a), pg(b), a[0], a[100]);
  show("after 2 kallocs");
  kfree(a);  show("after kfree(a)");
  char *c = kalloc();  printf("next kalloc -> page %d (same as a: %s)\n", pg(c), c == a ? "yes" : "no");
  kalloc(); kalloc();  show("after 2 more");
  printf("kalloc on empty list -> %s\n", kalloc() ? "page" : "0 (out of memory)");
  kfree(mem + 100);               // not page-aligned
}

after kinit          free: [3] [2] [1] [0]
kalloc -> page 3, page 2; a[0] = 5, a[100] = 5
after 2 kallocs      free: [1] [0]
after kfree(a)       free: [3] [1] [0]
next kalloc -> page 3 (same as a: yes)
after 2 more         free: (empty)
kalloc on empty list -> 0 (out of memory)
panic: kfree

Sv39 — তিন স্তরের page table

পর্ব ৩৩-এ x86-64-এর চার স্তরের টেবিল দেখেছিলেন। RISC-V-এর Sv39 একই ধারণা, তিন স্তরে। Virtual address ৩৯ bit (২^৩৯ byte = ৫১২ GiB): ওপরের ৯ bit স্তর ২-এর সূচি, পরের ৯ bit স্তর ১-এর, তার পরের ৯ bit স্তর ০-এর, আর শেষ ১২ bit পাতার ভেতরের offset. প্রতিটি page-table পাতায় ৫১২টি ৮-byte-এর PTE — ঠিক এক পাতা (৫১২ × ৮ = ৪০৯৬). xv6 এর মধ্যে ব্যবহার করে ৩৮ bit (MAXVA = ২^৩৮), যাতে sign-extension-এর ঝামেলা না থাকে।

#define PGSHIFT 12   // bits of offset within a page
#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // user can access
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
#define PTE2PA(pte) (((pte) >> 10) << 12)
#define PXMASK         0x1FF // 9 bits
#define PXSHIFT(level) (PGSHIFT + (9 * (level)))
#define PX(level, va)  ((((uint64)(va)) >> PXSHIFT(level)) & PXMASK)

pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if (va >= MAXVA)
    panic("walk");

  for (int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    if (*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {
      if (!alloc || (pagetable = (pde_t *)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];
}

walk() হলো hardware যা করে, তার software অনুকরণ — kernel-কে নিজেও টেবিল ভরতে হয়, তাই হাঁটতে জানতে হয়। alloc ১ হলে মাঝের কোনো টেবিল না থাকলে kalloc() দিয়ে নতুন পাতা এনে শূন্য করে বসিয়ে দেয়। এর ওপর দাঁড়িয়ে mappages() — একটি পরিসরের প্রতিটি পাতার জন্য walk(…, 1) ডেকে leaf PTE-তে লেখে PA2PTE(pa) | perm | PTE_V. আর uvmalloc() প্রসেসের মেমরি বাড়ায়: প্রতিটি নতুন পাতার জন্য kalloc(), তারপর mappages(). লক্ষ করুন, মাঝের স্তরের PTE-তে শুধু PTE_V; R, W, X তিনটিই শূন্য থাকলে hardware বোঝে “এটি leaf নয়, পরের টেবিলের ঠিকানা”।

নিচের stepper-এ একটি উদাহরণ-ঠিকানা 0x1234567ABC হাতে হাতে অনুবাদ করুন। ঠিকানাটি এমনভাবে বাছা, যাতে তিনটি সূচিই শূন্য নয়। Page-table পাতাগুলোর physical ঠিকানাও উদাহরণ, তবে বাস্তবসম্মত — kalloc উঁচু ঠিকানা থেকে দেয়, তাই PHYSTOP (0x88000000)-এর ঠিক নিচে।

1 VA -> L2 = 72, L1 = 418, L0 = 359, off = 0xABC2 satp -> root table @ PA 0x87FFF0003 root[72] = 0x21FFF401 -> next @ 0x87FFD0004 L1[418] = 0x21FFF001 -> next @ 0x87FFC0005 L0[359] = 0x21FD2817 -> leaf, V R W U6 PA = 0x87F4A000 | 0xABC = 0x87F4AABC

একই হিসাব একটি ছোট C প্রোগ্রামে, xv6-এর PX macro হুবহু ব্যবহার করে — xv6-এর নিজের দুটি বিশেষ পাতা, trampoline আর trapframe-সহ:

#include <stdio.h>
#include <stdint.h>
typedef uint64_t uint64;
#define PGSIZE 4096
#define PGSHIFT 12                                   // the next five lines are as in xv6
#define PXMASK 0x1FF
#define PXSHIFT(level) (PGSHIFT + (9 * (level)))
#define PX(level, va) ((((uint64)(va)) >> PXSHIFT(level)) & PXMASK)
#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))
#define TRAMPOLINE (MAXVA - PGSIZE)
#define TRAPFRAME (TRAMPOLINE - PGSIZE)

static void show(const char *name, uint64 va) {
  if (va >= MAXVA) { printf("%-11s 0x%010llx  >= MAXVA: walk() would panic\n", name, (unsigned long long)va); return; }
  printf("%-11s 0x%010llx  L2=%3u L1=%3u L0=%3u off=0x%03x\n", name, (unsigned long long)va,
         (unsigned)PX(2, va), (unsigned)PX(1, va), (unsigned)PX(0, va), (unsigned)(va & 0xFFF));
}
int main(void) {
  show("text start", 0x0);
  show("data", 0x2A7C);
  show("example", 0x1234567ABCULL);
  show("TRAPFRAME", TRAPFRAME);
  show("TRAMPOLINE", TRAMPOLINE);
  show("too high", (uint64)MAXVA);
  printf("MAXVA = 2^38 = %llu GiB; one L2 entry covers %d GiB, one L1 entry %d MiB\n",
         (unsigned long long)(MAXVA >> 30), 1, 512 * 4096 / (1 << 20));
  return 0;
}

text start  0x0000000000  L2=  0 L1=  0 L0=  0 off=0x000
data        0x0000002a7c  L2=  0 L1=  0 L0=  2 off=0xa7c
example     0x1234567abc  L2= 72 L1=418 L0=359 off=0xabc
TRAPFRAME   0x3fffffe000  L2=255 L1=511 L0=510 off=0x000
TRAMPOLINE  0x3ffffff000  L2=255 L1=511 L0=511 off=0x000
too high    0x4000000000  >= MAXVA: walk() would panic
MAXVA = 2^38 = 256 GiB; one L2 entry covers 1 GiB, one L1 entry 2 MiB

৬ · File system — সাত তলার দালান

পর্ব ৪১–৪৪-এ file system-এর interface, directory, inode আর journaling আলাদা দেখেছিলেন। xv6 এগুলোকে পরিষ্কার স্তরে সাজায় — প্রতিটি স্তর শুধু ঠিক নিচের স্তরটিকে ব্যবহার করে:

Buffer cache (buffer cache) দুটি কাজ করে: ধীর disk-এর বারবার পড়া এড়ানো, আর নিশ্চিত করা যে একটি block-এর মেমরি-কপি একটিই থাকে — দুটি প্রসেস একই block-এর দুই কপি আলাদাভাবে বদলালে একটির কাজ হারাত। bread() block-টি এনে তার sleeplock ধরে দেয়, brelse() ছেড়ে দেয়। xv6-এ buffer মাত্র ৩০টি (NBUF) — শেখার জন্য যথেষ্ট, বাস্তবের জন্য খুবই ছোট।

Logging হলো পর্ব ৪৪-এর write-ahead logging-এর সবচেয়ে সরল রূপ। প্রতিটি file system system call begin_op() আর end_op()-এর মাঝে চলে; মাঝখানের সব বদলানো block প্রথমে disk-এর log এলাকায় লেখা হয়, তারপর log-এর header block-এ সংখ্যা লেখা হয় — এই একটি লেখাই “commit”. তারপর block-গুলো আসল জায়গায় কপি, আর শেষে header মুছে ফেলা। মাঝপথে বিদ্যুৎ গেলে বুটের সময় recover_from_log() header দেখে: commit হয়ে থাকলে আবার কপি করে (redo), না হলে log উপেক্ষা করে। এজন্যই filewrite() বড় লেখাকে কয়েক block-এর টুকরোয় ভাঙে — একটি transaction-এ log-এ সর্বোচ্চ ১০টি block (MAXOPBLOCKS).

Inode আর সর্বোচ্চ ফাইল-আকার — একটি পূর্ণ হিসাব

#define BSIZE   1024 // block size

#define NDIRECT   12
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE   (NDIRECT + NINDIRECT)

// On-disk inode structure
struct dinode {
  short type;              // File type
  short major;             // Major device number (T_DEVICE only)
  short minor;             // Minor device number (T_DEVICE only)
  short nlink;             // Number of links to inode in file system
  uint size;               // Size of file (bytes)
  uint addrs[NDIRECT + 1]; // Data block addresses
};

অর্থাৎ inode-এ ১২টি direct block pointer আর একটি single indirect block-এর pointer (addrs[12]). Double বা triple indirect নেই। এবার পরীক্ষার ধাঁচে হিসাব:

২৬৮ KiB খুবই ছোট — একটি ছবিও ধরে না। এজন্যই xv6-এর একটি পরিচিত lab হলো “big files”: একটি direct pointer-কে double indirect বানিয়ে সীমা বাড়ানো (অনুশীলন ১-এ হিসাবটি করবেন)। Linux-এর ext2/ext3-এ একই ১২টি direct pointer, সাথে single, double আর triple indirect; ext4 এর বদলে extent ব্যবহার করে (পর্ব ৪৩).

৭ · Lock — spinlock, push_off আর sleeplock

xv6 multicore — তিনটি hart একসাথে kernel-এর ভেতরে থাকতে পারে, তাই প্রায় প্রতিটি ভাগ করা ডেটার নিজস্ব lock. পর্ব ২৩-এর spinlock এখানে সরাসরি:

void
acquire(struct spinlock *lk)
{
  push_off(); // disable interrupts to avoid deadlock.
  if (holding(lk))
    panic("acquire");

  while (__atomic_exchange_n(&lk->locked, 1, __ATOMIC_ACQUIRE) != 0)
    ;

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();
}

__atomic_exchange_n RISC-V-এ একটি amoswap.w.aq instruction হয়ে যায় — “১ লেখা আর পুরোনো মানটি ফেরত দেওয়া, একই মুহূর্তে”, ঠিক পর্ব ২৩-এর test-and-set. পুরোনো মান ০ হলে lock পাওয়া গেল; ১ হলে অন্য কেউ ধরে আছে, তাই আবার চেষ্টা — ঘুরতে থাকা। __ATOMIC_ACQUIRE compiler আর CPU-কে বলে, critical section-এর কোনো পড়া-লেখা যেন lock নেওয়ার আগে সরে না যায় (memory barrier); release()-এ উল্টো দিকের __ATOMIC_RELEASE.

কিন্তু প্রথম লাইনে interrupt বন্ধ কেন? ধরুন একটি hart tickslock ধরে আছে, আর ঠিক তখন timer interrupt এলো। Interrupt handler-ও tickslock নিতে চায়, তাই ঘুরতে থাকে — কিন্তু lock-টি ছাড়বে যে কোড, সে তো এই একই CPU-তে থেমে আছে handler শেষ হওয়ার অপেক্ষায়। চিরস্থায়ী deadlock, মাত্র একটি CPU-তেই। সমাধান: lock ধরে থাকার পুরো সময় সেই CPU-তে interrupt বন্ধ (interrupt masking). push_off()/pop_off() জোড়ায় জোড়ায় গোনে (noff), কারণ একটি lock ধরে আরেকটি ধরা যায়; শেষ lock ছাড়লে তবেই, আর শুরুতে interrupt চালু থাকলে তবেই (intena), আবার চালু হয়।

Spinlock অল্প সময়ের জন্য ভালো, কিন্তু disk-এর জন্য কয়েক মিলিসেকেন্ড অপেক্ষায় CPU ঘুরিয়ে নষ্ট করা অপচয় — আর interrupt বন্ধ রেখে disk-এর কাজ শেষ হওয়ার খবরও আসবে না। তাই buffer আর inode-এর জন্য xv6-এ sleeplock: ভেতরে একটি ছোট spinlock আর একটি locked ফ্ল্যাগ; lock ব্যস্ত পেলে acquiresleep() sleep করে, ছাড়ার সময় releasesleep() wakeup করে। Sleeplock ধরে থাকা অবস্থায় interrupt চালু থাকে, প্রসেস ঘুমাতেও পারে — কিন্তু interrupt handler-এ এটি ব্যবহার করা যায় না, কারণ handler ঘুমাতে পারে না।

৮ · Shell — sh.c-এ fork, exec আর pipe

পর্ব ১০ আর ১১-এ shell-এর মূল লুপ দেখেছিলেন: কমান্ড পড়া, fork(), সন্তানে exec(), অভিভাবকে wait(). xv6-এর sh.c মাত্র প্রায় ৫০০ লাইনে এটি করে — একটি ছোট recursive-descent parser দিয়ে কমান্ডকে একটি গাছে (EXEC, REDIR, PIPE, LIST, BACK) ভাঙে, তারপর runcmd() গাছটি চালায়। cd একমাত্র ব্যতিক্রম — সেটি সন্তানে চালালে শুধু সন্তানের directory বদলাত, তাই shell নিজেই chdir করে। Pipe-এর অংশটি পড়ার মতো:

  case PIPE:
    pcmd = (struct pipecmd *)cmd;
    if (pipe(p) < 0)
      panic("pipe");
    if (fork1() == 0) {
      close(1);
      dup(p[1]);
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->left);
    }
    if (fork1() == 0) {
      close(0);
      dup(p[0]);
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->right);
    }
    close(p[0]);
    close(p[1]);
    wait(0);
    wait(0);
    break;

ls | wc-এর জন্য: বাঁ দিকের সন্তান fd ১ বন্ধ করে dup(p[1]) — dup সবসময় সবচেয়ে ছোট খালি fd দেয়, তাই pipe-এর লেখার মুখ এখন fd ১. ডান দিকের সন্তান একইভাবে pipe-এর পড়ার মুখকে fd ০ বানায়। এই “আগে বন্ধ, তারপর dup” কৌশলটিই Unix-এর redirection-এর মূল, আর Linux-এর dup2() একে এক ধাপে করে। অপ্রয়োজনীয় মুখগুলো বন্ধ করা জরুরি: পড়ার দিক কখনো end-of-file পায় না, যতক্ষণ কোথাও লেখার মুখ খোলা থাকে (পর্ব ১২). xv6-এর shell-এ job control, signal বা quoting নেই — Bash-এর তুলনায় খুবই ছোট, কিন্তু মূল যন্ত্রটি হুবহু একই।

৯ · নিজে চালান আর নিজে বদলান

xv6 পড়া এক জিনিস, চালিয়ে একটি লাইন বদলে দেখা আরেক জিনিস। দরকার দুটি জিনিস: একটি RISC-V cross-compiler (আপনার x86 বা ARM কম্পিউটারে বসে RISC-V-এর machine code বানায়) আর QEMU (qemu-system-riscv64; এখনকার Makefile অন্তত version 7.2 চায়)। Linux বা WSL-এ সবচেয়ে সহজ; macOS-এ Homebrew দিয়ে। নিচের কমান্ডগুলো এই পাতায় চালানো যাবে না — নিজের terminal-এ চালাবেন; প্যাকেজের নাম distro-ভেদে আলাদা হতে পারে, তাই MIT-র 6.1810 কোর্স-পাতার “tools” নির্দেশনা মিলিয়ে নিন।

# toolchain + QEMU (package names can differ on your distro/version)
sudo apt install git build-essential gcc-riscv64-linux-gnu qemu-system-misc

git clone https://github.com/mit-pdos/xv6-riscv.git
cd xv6-riscv
make qemu

# ... a few seconds of compiling, then:
xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ ls
$ echo hello xv6
hello xv6

# to leave QEMU: press Ctrl-a, release, then press x

QEMU থেকে বেরোতে Ctrl+a চেপে ছেড়ে দিন, তারপর x. make qemu-gdb দিয়ে চালালে QEMU একটি debugger-এর জন্য অপেক্ষা করে; আরেকটি terminal থেকে RISC-V-সক্ষম gdb জুড়ে break syscall দিয়ে উপরের stepper-এর প্রতিটি ধাপ আসল CPU-তে দেখতে পারবেন। user/-এ নতুন একটি প্রোগ্রাম লিখলে Makefile-এর UPROGS তালিকায় নামটি যোগ করতে হয়, নইলে সেটি disk image-এ ঢুকবে না।

কোথা থেকে শুরু — ক্লাসিক অনুশীলনী

MIT-র কোর্সের lab-গুলো বছরে বছরে কিছুটা বদলায়, তবে কয়েকটি ধারণা বহু বছর ধরে ঘুরে ফিরে আসে। নিচে শুধু দিকনির্দেশনা — সমাধান নয়; নিজে করাটাই শেখা, আর কোনো কোর্সের অংশ হিসেবে করলে সেই কোর্সের সততার নিয়ম মানুন।

একটি খবর: xv6-এর সাম্প্রতিক সংস্করণে (২০২৫ থেকে) sbrk-এর lazy allocation-এর একটি সরল রূপ মূল কোডেই এসে গেছে — usertrap()-এ vmfault() দেখতে পাবেন। তাই পুরোনো lab-নির্দেশনা নতুন কোডে হুবহু না মিলতে পারে; যে বছরের lab করছেন, সেই বছরের branch ব্যবহার করুন।

১০ · AI-এর যুগে xv6 পড়া

AI xv6 সম্পর্কে অনেক কিছু “জানে”, কারণ সোর্স আর বই দুটোই বহু বছর ধরে ইন্টারনেটে আছে। সমস্যা হলো, xv6-এর অন্তত তিনটি আলাদা যুগ — x86 সংস্করণ, ২০১৯–২০২৪-এর RISC-V সংস্করণ, আর ২০২৫-এর পরের বদলানো কোড — AI-এর উত্তরে প্রায়ই মিশে যায়।

AI-এর উত্তর মানার আগে — চেকলিস্ট

• উত্তরে যে ফাংশন বা ফাইলের নাম এসেছে, প্রতিটি নিজের checkout-এ grep করে পেয়েছি
• উত্তরটি x86 xv6, পুরোনো RISC-V না সাম্প্রতিক RISC-V-এর — সেটি নিশ্চিত হয়েছি
• সংখ্যার দাবি (NPROC, BSIZE, NDIRECT, MAXVA) param.h, fs.h, riscv.h-এ মিলিয়েছি, আর হিসাব নিজে হাতে করেছি
• Kernel-এ কোনো বদল করলে usertests (আর lab-এর নিজস্ব test) চালিয়েছি — শুধু “boot হলো” দেখে থামিনি; একাধিক CPU-তে (CPUS বদলে) চালিয়ে race খুঁজেছি
• নতুন lock-এর কোডে ভেবে দেখেছি: interrupt handler-ও কি এই lock নেয়? দুটি lock কি সবসময় একই ক্রমে নেওয়া হয়?
• AI-এর দেওয়া toolchain-ইনস্টলের কমান্ড আমার OS আর distro-র জন্য কি না দেখেছি, আর অপ্রয়োজনীয় sudo বা chmod 777 চালাইনি