Paging আর Page Table — ভার্চুয়াল ঠিকানাকে সত্যিকারের RAM-এ অনুবাদ করার যন্ত্র

এই প্রোগ্রামটা এই লেসনের সব হিসাব একসাথে করে: বিট-ভাঙা, pagemap পড়া, আর দুইটা মিলিয়ে যাচাই।

/* vaddr_decode.c — একটা virtual address-এর page table index গুলো হাতে বের করে
 *                  এবং /proc/self/pagemap থেকে প্রকৃত PFN নিয়ে মিলিয়ে দেখে।
 *
 * বানান:  gcc -O2 -Wall -o vaddr_decode vaddr_decode.c
 * চালান:  ./vaddr_decode          (PFN শূন্য দেখাবে)
 *         sudo ./vaddr_decode     (প্রকৃত PFN দেখাবে)
 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>

#define PAGE_SHIFT 12
#define PAGE_SIZE  (1UL << PAGE_SHIFT)
#define IDX_MASK   0x1FFUL              /* ৯ বিট: ০..৫১১ */

/* --- অংশ ১: বিশুদ্ধ bit arithmetic, কোনো kernel সাহায্য ছাড়া --- */

struct vaddr_parts {
    unsigned pml4, pdpt, pd, pt;
    unsigned long offset;
    unsigned long sign_ext;             /* উপরের ১৬ বিট */
};

static struct vaddr_parts decode(unsigned long v) {
    struct vaddr_parts p;
    p.sign_ext = v >> 48;
    p.pml4     = (v >> 39) & IDX_MASK;
    p.pdpt     = (v >> 30) & IDX_MASK;
    p.pd       = (v >> 21) & IDX_MASK;
    p.pt       = (v >> 12) & IDX_MASK;
    p.offset   =  v & (PAGE_SIZE - 1);
    return p;
}

static int is_canonical(unsigned long v) {
    /* বিট ৬৩..৪৮ অবশ্যই বিট ৪৭-এর অনুলিপি হতে হবে */
    unsigned long top = v >> 47;
    return top == 0 || top == 0x1FFFFUL;
}

static void print_bits(unsigned long v) {
    for (int b = 63; b >= 0; b--) {
        putchar((v >> b) & 1 ? '1' : '0');
        if (b == 48 || b == 39 || b == 30 || b == 21 || b == 12) putchar(' ');
    }
    putchar('\n');
    printf("|--- sign ------| |-PML4--| |-PDPT--| |--PD---| |--PT---| |-- offset --|\n");
}

/* --- অংশ ২: kernel কী বলে — /proc/self/pagemap --- */

struct pm_entry {
    int      valid;                     /* entry পড়া গেছে? */
    int      present, swapped, exclusive, file_shared;
    uint64_t pfn;
    uint64_t raw;
};

static struct pm_entry pagemap_lookup(unsigned long vaddr) {
    struct pm_entry e;
    memset(&e, 0, sizeof e);

    int fd = open("/proc/self/pagemap", O_RDONLY);
    if (fd < 0) { perror("open pagemap"); return e; }

    off_t off = (off_t)(vaddr / PAGE_SIZE) * sizeof(uint64_t);
    uint64_t raw = 0;
    if (pread(fd, &raw, sizeof raw, off) != sizeof raw) {
        perror("pread pagemap");
        close(fd);
        return e;
    }
    close(fd);

    e.valid       = 1;
    e.raw         = raw;
    e.present     = (raw >> 63) & 1;
    e.swapped     = (raw >> 62) & 1;
    e.file_shared = (raw >> 61) & 1;
    e.exclusive   = (raw >> 56) & 1;
    e.pfn         = raw & ((1ULL << 55) - 1);
    return e;
}

/* --- অংশ ৩: একটা ঠিকানার পূর্ণ প্রতিবেদন --- */

static void report(const char *label, unsigned long v) {
    struct vaddr_parts p = decode(v);
    struct pm_entry    e = pagemap_lookup(v);

    printf("\n=== %s : 0x%016lx ===\n", label, v);
    print_bits(v);
    printf("canonical           : %s\n", is_canonical(v) ? "হ্যাঁ" : "না (#GP হবে)");
    printf("  sign-extension    : 0x%04lx\n", p.sign_ext);
    printf("  PML4 index        : %4u   (0x%03x)   → CR3 + %u*8 = +0x%x\n",
           p.pml4, p.pml4, p.pml4, p.pml4 * 8);
    printf("  PDPT index        : %4u   (0x%03x)   → PDPT_base + 0x%x\n",
           p.pdpt, p.pdpt, p.pdpt * 8);
    printf("  PD   index        : %4u   (0x%03x)   → PD_base   + 0x%x\n",
           p.pd, p.pd, p.pd * 8);
    printf("  PT   index        : %4u   (0x%03x)   → PT_base   + 0x%x\n",
           p.pt, p.pt, p.pt * 8);
    printf("  page offset       : %4lu   (0x%03lx)\n", p.offset, p.offset);
    printf("  virtual page num  : 0x%lx\n", v >> PAGE_SHIFT);

    if (!e.valid) { printf("  pagemap           : পড়া যায়নি\n"); return; }

    printf("  pagemap raw       : 0x%016llx\n", (unsigned long long)e.raw);
    printf("  present / swapped : %d / %d\n", e.present, e.swapped);
    printf("  exclusive / file  : %d / %d\n", e.exclusive, e.file_shared);

    if (e.present && e.pfn) {
        unsigned long phys = (e.pfn << PAGE_SHIFT) | p.offset;
        printf("  PFN               : 0x%llx  (%llu)\n",
               (unsigned long long)e.pfn, (unsigned long long)e.pfn);
        printf("  PHYSICAL ADDRESS  : 0x%lx\n", phys);
        printf("                      = (PFN << 12) | offset\n");
    } else if (e.present) {
        printf("  PFN               : ০ — root ছাড়া চালাচ্ছেন (CAP_SYS_ADMIN দরকার)\n");
    } else {
        printf("  PFN               : mapping present নয় — এখনো fault-in হয়নি\n");
    }
}

int main(void) {
    /* ছোঁয়া হয়নি এমন একটা page — present বিট ০ থাকবে */
    char *untouched = mmap(NULL, PAGE_SIZE * 2, PROT_READ | PROT_WRITE,
                           MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (untouched == MAP_FAILED) { perror("mmap"); return 1; }

    report("mmap করা কিন্তু ছোঁয়া হয়নি", (unsigned long)untouched);

    untouched[0] = 'A';                 /* এখন fault-in হলো */
    report("একই page, ছোঁয়ার পর", (unsigned long)untouched);

    /* পাশের page — শুধু PT index এক বাড়া উচিত */
    untouched[PAGE_SIZE] = 'B';
    report("পাশের page (+4096)", (unsigned long)untouched + PAGE_SIZE);

    /* stack-এ থাকা একটা local variable — সম্পূর্ণ ভিন্ন অঞ্চল */
    int on_stack = 0;
    report("stack-এ একটা local", (unsigned long)&on_stack);

    /* একটা অ-canonical ঠিকানা — শুধু গণনা, dereference করবেন না! */
    report("অ-canonical উদাহরণ", 0x0000800000000000UL);

    munmap(untouched, PAGE_SIZE * 2);
    return 0;
}

চালানোর পর (root হিসেবে) যা দেখতে পাবেন, সংক্ষেপে:

=== mmap করা কিন্তু ছোঁয়া হয়নি : 0x00007f2b41c3a000 ===
canonical           : হ্যাঁ
  PML4 index        :  254   (0x0fe)
  PDPT index        :  173   (0x0ad)
  PD   index        :   30   (0x01e)
  PT   index        :   58   (0x03a)
  page offset       :    0   (0x000)
  pagemap raw       : 0x0000000000000000
  present / swapped : 0 / 0
  PFN               : mapping present নয় — এখনো fault-in হয়নি

=== একই page, ছোঁয়ার পর : 0x00007f2b41c3a000 ===
  pagemap raw       : 0x8500000000163b71
  present / swapped : 1 / 0
  PFN               : 0x163b71  (1456497)
  PHYSICAL ADDRESS  : 0x163b71000

=== পাশের page (+4096) : 0x00007f2b41c3b000 ===
  PT   index        :   59   (0x03b)        ← ৫৮ থেকে ৫৯, শুধু PT index বাড়ল
  PFN               : 0x1a04c2  (1704130)   ← কিন্তু PFN সম্পূর্ণ অসংলগ্ন!

এই আউটপুটের তিনটা পর্যবেক্ষণ এই লেসনের কেন্দ্রীয় দাবিগুলোর প্রত্যক্ষ প্রমাণ:

1. mmap করা মানেই মেমরি বরাদ্দ না — প্রথম রিপোর্টে present=0, কোনো physical frame নেই। mmap শুধু একটা প্রতিশ্রুতি; প্রকৃত frame আসে প্রথম স্পর্শে।
2. সংলগ্ন virtual, অসংলগ্ন physical — পাশাপাশি দুইটা virtual page (...a000 আর ...b000) সম্পূর্ণ ভিন্ন, অসংলগ্ন physical frame-এ (0x163b71 আর 0x1a04c2) বসেছে। এটাই paging-এর সেই সুবিধা যা external fragmentation দূর করে।
3. শুধু PT index বদলাল — পাশের page-এ যাওয়ায় শুধু নিচের স্তরের index এক বাড়ল, উপরের তিনটা index অপরিবর্তিত। এর মানে দুইটা page একই PT ভাগ করে — একই PT ৫১২টা page, অর্থাৎ ২ MB পর্যন্ত ঢাকে।

নিজে বাড়ান

1. PTE-র উপরের বিটগুলোও দেখান। pagemap swapped page-এর জন্য বিট ০-৪-এ swap type আর ৫-৫৪-এ swap offset রাখে। একটা প্রোগ্রাম লিখুন যা প্রচুর memory বরাদ্দ করে swap-এ ঠেলে দেয় (swapoff -a না চালিয়ে!), তারপর একটা swapped page-এর entry decode করে swap type + offset ছাপে।
2. /proc/kpageflags যোগ করুন। PFN হাতে পেলে /proc/kpageflags-এ PFN * 8 offset-এ সেই physical frame-এর kernel flag (KPF_ANON, KPF_DIRTY, KPF_HUGE, KPF_REFERENCED) পড়া যায়। রিপোর্টে সেই flag-গুলো নাম ধরে ছাপুন।
3. Huge page শনাক্ত করুন। madvise(ptr, 2*1024*1024, MADV_HUGEPAGE) দিয়ে একটা ২ MB-সারিবদ্ধ অঞ্চল নিন, ছুঁয়ে ফেলুন, তারপর তার ভেতরের ৫১২টা ৪KB page-এর pagemap entry পড়ুন — সবগুলোর PFN কি ধারাবাহিক? (হ্যাঁ হওয়া উচিত, আর প্রথমটা ৫১২-এর গুণিতক হওয়া উচিত।) এই পরীক্ষাটাই huge page শনাক্ত করার একটা নির্ভরযোগ্য উপায়।
4. দুইটা process, একই ফাইল। একই ফাইল দুইটা process-এ MAP_SHARED দিয়ে mmap করুন, দুই দিক থেকে PFN ছাপুন — একই PFN পাওয়া উচিত, কারণ shared mapping মানে একই physical frame দুইটা page table-এ দুইবার উল্লেখ করা। তারপর MAP_PRIVATE দিয়ে একই পরীক্ষা করুন এবং একজন লেখার পর PFN কীভাবে বদলে যায় দেখুন — সেটাই copy-on-write, লেসন ১৩-এর বিষয়।
5. ৫-স্তর সমর্থন যোগ করুন। /proc/cpuinfo-তে la57 flag আছে কি না দেখে, থাকলে একটা পঞ্চম index ((v >> 48) & 0x1FF) বের করুন এবং sign-extension ক্ষেত্রটা ১৬ থেকে ৭ বিটে সংকুচিত করুন।