Memory Management
& Virtual Memory

8.1 Stack vs Heap — đặc điểm

void example() {
    int x = 5;             // x trên STACK — tự free khi return
    int *p = malloc(100);  // 100 byte trên HEAP — phải free
    int arr[1000];          // 4000 byte trên STACK
    free(p);
}

Vì sao stack nhanh hơn heap?

• Stack chỉ cần tăng/giảm Stack Pointer — 1 instruction
• Heap cần allocator: tìm free block, split, link list... — nhiều thao tác
• Stack cache-friendly: liên tiếp trong RAM
• Heap có thể fragment, cần defragmentation

8.2 Memory Errors — phải biết phân biệt

Tools để debug memory error

• Valgrind: detect leak, use-after-free, invalid read/write (slow but thorough)
• AddressSanitizer (ASan): clang/gcc -fsanitize=address, faster
• Node.js heap snapshot: Chrome DevTools → Memory tab

8.3 Virtual Memory — phép màu của OS

Vấn đề thực tế:

• Máy có 16GB RAM, nhưng có hàng trăm process chạy
• Mỗi process cần nhiều memory, nhưng không đủ RAM cho tất cả
• Process cần được cô lập — không được đọc memory của process khác
• Process không biết trước nó sẽ ở vị trí RAM nào

Giải pháp: Virtual Memory. Mỗi process được OS "lừa" rằng nó có toàn bộ address space (vd 4GB cho 32-bit, 256TB cho 64-bit) — gọi là virtual address space. Thực tế, OS map các vùng đang dùng vào RAM thật, vùng không dùng có thể swap ra disk.

Lợi ích của VM

1. Cô lập: process không thấy memory của process khác
2. Mỗi process tưởng mình có cả RAM: không cần biết process khác đang dùng đâu
3. Ảo hoá hơn RAM: tổng VA của các process > RAM thật, OS swap ra disk khi cần
4. Lazy loading: chỉ load page khi truy cập (page on demand)
5. Memory sharing: nhiều process map cùng physical page (libc shared, fork CoW)
6. Memory protection: read-only page (text segment) không cho ghi

8.4 Virtual Address vs Physical Address

Khi process A và B cả hai có địa chỉ ảo 0x00400000, MMU dịch sang địa chỉ vật lý khác nhau (vd 0x12345 cho A, 0x67890 cho B). Cả hai cứ tưởng mình có địa chỉ đó, nhưng thực ra OS điều phối.

Linux x86_64 virtual address space

0xffff_ffff_ffff_ffff
                       │
   Kernel space (chia sẻ giữa mọi process, chỉ kernel mode mới đọc được)
                       │
0xffff_8000_0000_0000  ← split point
                       │
                       │
   User space (mỗi process riêng)
   ┌────────────┐
   │   Stack    │ tăng xuống
   │     ↓      │
   │            │
   │     ↑      │
   │   Heap     │ tăng lên
   │   BSS      │
   │   Data     │
   │   Text     │
   └────────────┘
0x0000_0000_0040_0000   (0x400000 = entrypoint mặc định cho ELF)

8.5 MMU — Memory Management Unit (phần cứng)

MMU là phần cứng nằm giữa CPU và RAM. Mỗi instruction đọc/ghi memory đều đi qua MMU:

1. CPU phát virtual address (vd 0x401000)
2. MMU tra page table của process hiện tại
3. MMU dịch sang physical address (vd 0x12345)
4. RAM trả data cho CPU

Vì mỗi instruction đều cần dịch, MMU phải cực nhanh. Kèm theo: TLB (Translation Lookaside Buffer) — cache cho page table (sẽ học chương 9).

Khi context switch giữa process A và B, kernel update CR3 register (x86) để trỏ vào page table của process mới. MMU tự dùng page table mới.

8.6 Paging — chia memory thành ô vuông

Paging: chia toàn bộ address space (cả virtual lẫn physical) thành các page kích thước cố định. Linux x86_64: page = 4 KB.

• Virtual page: đơn vị trong virtual address space
• Physical frame: đơn vị tương ứng trong RAM thật
• Page Table: ánh xạ virtual page → physical frame

Cách dịch địa chỉ

Virtual address 32-bit chia làm:

• 20 bit cao: Page Number (chỉ số page) — 2²⁰ = 1M page
• 12 bit thấp: Offset trong page (4KB = 2¹²)

Virtual address: 0x00401234
                  ┌──────────┬──────┐
                  │ Page #   │Offset│
                  │ 0x00401  │ 0x234│
                  └────┬─────┴───┬──┘
                       │         │
                  page table     │
                       │         │
                       ▼         │
                  Frame # 0x12345│
                       │         │
                       └─────────┴────▶ Physical: 0x12345234

Tại sao chọn 4KB?

• Đủ nhỏ để không lãng phí (process nhỏ chỉ dùng vài KB)
• Đủ lớn để page table không quá khổng lồ
• Một số kernel hỗ trợ "huge pages" 2MB/1GB cho workload đặc thù (DB, JVM)

8.7 Page Table Entry (PTE)

Mỗi entry trong page table chứa:

• Frame number: physical frame (~52 bit)
• Present bit: page có trong RAM chưa? (0 → page fault, đọc từ disk)
• Read/Write bit: read-only hay writable? (text segment = R only)
• User/Supervisor: user code có truy cập được không? (kernel page = supervisor only)
• Accessed bit: đã từng được đọc? (cho LRU)
• Dirty bit: đã bị ghi chưa? (nếu chưa dirty, swap out không cần ghi disk)
• NX bit (No-Execute): page có chứa code chạy được không? (chống buffer overflow exploit)

Vấn đề: Page Table khổng lồ

32-bit: 2²⁰ entry × 4 byte = 4 MB page table per process. Có 100 process = 400 MB chỉ cho page table.
64-bit: 2⁵² entry × 8 byte = 32 PB per process. Bất khả thi.

Giải pháp: Multi-level page table.

8.8 Multi-level Page Table

Thay vì 1 bảng phẳng khổng lồ, chia thành cây nhiều tầng. Phần nào không dùng thì không cần bảng con.

x86_64 — 4-level paging

Virtual address (48 bit):
   ┌──────┬──────┬──────┬──────┬──────────┐
   │ PML4 │ PDPT │ PD   │ PT   │  Offset  │
   │ 9 bit│ 9 bit│ 9 bit│ 9 bit│  12 bit  │
   └───┬──┴───┬──┴───┬──┴───┬──┴──────────┘
       │      │      │      │
       ▼      ▼      ▼      ▼
   PML4 ──▶ PDPT ──▶ PD  ──▶ PT  ──▶ Frame
   (root)

4 lookup → 4 memory access cho mỗi address translation
→ Slow! Nên cần TLB cache

Ưu điểm: process chỉ dùng 1 ít VA → các nhánh không dùng để rỗng. Nhược: 4 memory access cho mỗi translation.

Kernel mới hơn (Linux 4.14+) hỗ trợ 5-level paging để đạt 57-bit VA = 128 PB.

8.9 Segmentation — old approach

Trước paging, OS dùng segmentation: chia memory thành các segment có kích thước biến đổi (vd 1 segment cho code, 1 cho data, 1 cho stack).

• Address = (segment, offset)
• Mỗi segment có base + limit register
• Vấn đề: external fragmentation — sau khi free, RAM có "lỗ hổng" kích thước khác nhau, khó tìm chỗ trống đúng size

x86 32-bit còn segment registers (CS, DS, SS) nhưng modern OS chỉ set base = 0, limit = max → "flat segment" → effectively chỉ dùng paging.

8.10 Memory Mapping (mmap)

mmap là syscall map 1 file (hoặc anonymous memory) vào virtual address space của process. Sau đó đọc/ghi file = đọc/ghi memory.

int fd = open("data.bin", O_RDWR);
struct stat st; fstat(fd, &st);

// Map toàn bộ file vào memory
char *p = mmap(NULL, st.st_size, PROT_READ | PROT_WRITE,
                MAP_SHARED, fd, 0);

// Đọc/ghi file như memory
p[0] = 'A';      // ghi byte đầu
char c = p[100]; // đọc byte 100

munmap(p, st.st_size);
close(fd);

Lợi ích

• Truy cập ngẫu nhiên file rất nhanh — không cần seek + read
• OS quản lý cache tự động (page cache)
• Nhiều process map cùng file = chia sẻ memory tự nhiên
• Lazy loading: page chỉ load khi truy cập

Use case

• Database (LMDB, SQLite memory mode)
• Shared memory IPC (chương 5)
• Loading executable: kernel mmap binary → execute
• Đọc file lớn không cần load hết vào RAM

8.11 Garbage Collection — quan trọng cho JS dev

Trong C/C++, lập trình viên tự free. Nhưng JS, Java, Go, Python — runtime tự thu hồi memory không dùng nữa. Đây là Garbage Collection (GC).

Reachability — khái niệm cốt lõi

Object "reachable" = có thể đến được từ roots (global vars, stack vars, registers...). Object "unreachable" = không còn reference nào → có thể thu hồi.

Mark-and-Sweep (cổ điển)

1. Mark: từ roots, đi qua mọi reachable object, đánh dấu
2. Sweep: scan toàn bộ heap, free các object không có dấu

Nhược: có thể dừng app khá lâu ("stop-the-world" pause).

Generational GC (V8 dùng)

Quan sát: hầu hết object chết trẻ (vd biến tạm). Chỉ một số "sống dai" (config, cache). Chia heap thành:

• Young generation (Eden + Survivor): nơi object mới sinh; GC thường xuyên (Minor GC, fast)
• Old generation: object đã survive vài lần Minor GC; GC ít hơn (Major GC, slow)

V8 (Node.js, Chrome) dùng Scavenger cho young + Mark-Compact cho old.

Reference Counting (Python, Swift)

Mỗi object có counter "bao nhiêu reference đang trỏ đến mình". Khi counter = 0 → free ngay.
Nhược: circular reference không bao giờ giảm về 0 → leak. Phải có thêm cycle detector.

Memory leak trong language có GC?

Có! GC chỉ thu hồi unreachable. Nếu code "vô tình" giữ reference (vd thêm vào array global mà quên xoá), object sẽ "reachable" mãi → leak.

// Memory leak kinh điển trong JS
const cache = [];
function loadData(id) {
  const data = fetch('/api/' + id);
  cache.push(data);  // không bao giờ xoá → memory tăng vô hạn
  return data;
}

Tools: Chrome DevTools heap snapshot, node --inspect.

Bài tập

Tổng kết chương 8

• ✅ Stack tự động (function call) + nhanh; Heap động (malloc) + free thủ công hoặc GC
• ✅ Memory errors: Stack overflow, Buffer overflow, Memory leak, Use-after-free, Double free, Segfault
• ✅ Virtual Memory = ảo giác mỗi process có cả address space; cô lập + ảo hoá + lazy + sharing
• ✅ Virtual address ≠ Physical address; MMU dịch tự động qua page table
• ✅ Paging: chia thành 4KB page, mapping page→frame
• ✅ PTE: frame#, present, R/W, U/S, accessed, dirty, NX
• ✅ Multi-level page table: tiết kiệm memory cho 64-bit (4 hoặc 5 levels)
• ✅ mmap: map file vào memory — fast random access
• ✅ GC: reachability từ roots; Generational (V8) > Mark-and-sweep > Reference counting
• ✅ Memory leak xảy ra cả với GC nếu code giữ reference không cần