Bài 59: Stack vs Heap — Refresher Cho Rust

Sau bài học, bạn sẽ:

• Hiểu hai vùng memory stack và heap ở mức mental model — không cần biết chi tiết kernel.
• Biết stack là LIFO contiguous, push/pop bằng cách chỉnh stack pointer (sp), mỗi function call tạo 1 stack frame, return là pop.
• Biết heap là vùng free-form lớn, cấp phát qua allocator (giống malloc/free của C nhưng Rust gói trong type), địa chỉ random, cần lưu metadata để free đúng.
• So sánh được tốc độ: stack alloc/dealloc O(1) gần như free, heap alloc tốn hơn nhiều bậc do phải tìm chỗ trống và có thể syscall.
• Biết size limit: stack thường 1-8 MB (Linux 8 MB, macOS 8 MB main thread, Windows 1 MB), heap lên tới nhiều GB tuỳ RAM/virtual address space.
• Phân loại từng kiểu Rust theo vùng memory: primitives, array cố định, reference → stack; Vec<T>, String, Box<T>, Rc<T>, Arc<T> → pointer trên stack, data trên heap.
• Hình dung được layout let s = String::from("hi") qua ASCII và biết chuyện gì xảy ra khi s ra khỏi scope.
• Hiểu vì sao ownership rules chính là cách Rust quản lý heap một cách an toàn không cần GC.

Stack là một vùng memory liên tục (contiguous), hoạt động theo nguyên tắc LIFO (Last In, First Out) — giống chồng đĩa: đĩa cuối cùng đặt lên trên cùng cũng là đĩa đầu tiên được lấy ra.

CPU duy trì một thanh ghi đặc biệt gọi là stack pointer (viết tắt sp, trên x86_64 là rsp), chứa địa chỉ của đỉnh stack hiện tại. Để "push" thêm dữ liệu: chỉ cần trừ sp đi số byte cần thiết (stack mọc xuống trên x86) rồi ghi giá trị vào. Để "pop": cộng sp trở lại. Toàn bộ thao tác = vài instruction CPU, không cần hỏi allocator gì cả.

Mỗi lần một function được gọi, runtime cấp một khối stack gọi là stack frame chứa: local variables, function parameters, return address, saved registers. Khi function return, frame bị pop (sp trả về vị trí cũ) → mọi local variable trong frame "biến mất" tự động. Không cần ai gọi free().

fn inner() {
    let y = 99i32;          // push 4 byte vào stack frame của inner
    println!("y = {y}");
}                            // frame inner pop - y biến mất TỰ ĐỘNG

fn outer() {
    let x = 42i32;          // push 4 byte vào stack frame của outer
    inner();                // tạo frame mới chồng lên frame outer
    println!("x = {x}");
}                            // frame outer pop

fn main() {
    outer();
}
// Thứ tự pop ngược thứ tự push: inner trước, outer sau, main cuối.

Yêu cầu bắt buộc của stack: compiler phải biết trước size của mỗi frame ở compile-time. Nếu một biến có size động (vd chuỗi nhập từ user nên không biết dài bao nhiêu byte), không thể đặt thẳng trên stack — phải dùng heap.

Analogy: stack giống chồng khay đồ ăn ở canteen tự phục vụ. Lấy khay ở đỉnh nhanh O(1), không phải đi tìm. Nhưng không thể đặt một cái khay khổng lồ chưa biết kích thước vào giữa chồng.

Heap là vùng memory tự do (free-form), lớn hơn stack nhiều bậc, dùng để chứa dữ liệu mà:

• Size không biết trước ở compile-time (vd String đọc từ stdin, Vec push động).
• Size quá lớn so với stack frame (vd buffer ảnh vài MB).
• Cần "sống lâu hơn" function tạo ra nó (vd cấu trúc dữ liệu trả về và giữ lại).

Chương trình không tự thao tác trực tiếp với heap — phải đi qua một allocator. Trong C, allocator phơi ra qua malloc/free. Trong Java/Go, allocator + GC tự động track và free. Trong Rust, allocator (mặc định là System wrapping malloc/free của OS) được gọi ngầm bởi type như Box, Vec, String; và được drop gọi free tự động khi value ra khỏi scope (đó chính là ownership).

Quy trình allocator khi xin một khối heap:

1. Nhận yêu cầu "xin n byte với alignment a".
2. Duyệt danh sách free chunk (các block còn trống trong vùng heap đã có) tìm block đủ lớn.
3. Nếu không có chunk phù hợp, gọi syscall (mmap trên Linux, VirtualAlloc trên Windows) xin OS cấp thêm một page mới.
4. Trả về địa chỉ + đánh dấu khối đó đã chiếm. Địa chỉ có thể "ngẫu nhiên" theo nghĩa nó phụ thuộc vào lịch sử alloc/free trước đó, không liên tục.

Khi free, allocator cần biết size của block (thường lưu trong metadata header ngay trước block). Đây là lý do Box<T>, Vec<T> trong Rust luôn lưu thông tin size trên stack — để khi drop biết chính xác bao nhiêu byte cần free.

Analogy: heap giống thuê chỗ trong một nhà kho lớn. Mỗi lần thuê phải báo thủ kho cần bao nhiêu, thủ kho tìm vị trí trống đủ rộng, ghi sổ. Khi trả phải đưa đúng địa chỉ và size đã thuê. Quá trình "tìm chỗ" và "ghi sổ" tốn thời gian hơn nhiều so với việc chỉ đặt thêm khay lên chồng đĩa ở canteen.

Khoảng cách tốc độ giữa stack alloc và heap alloc rất lớn — và đây là một trong những lý do Vec::with_capacity tồn tại, lý do pool/arena allocator phổ biến trong code performance-critical.

• Stack push/pop: 1-2 instruction CPU (sub/add rsp, mov register). Latency dưới 1 ns. Hầu như "miễn phí".
• Heap alloc: scan free list (10-100 ns trường hợp tốt), có thể syscall mmap nếu cần mở rộng (1000-10000 ns), trên hệ multi-thread còn phải lock allocator (hoặc dùng thread-local cache như jemalloc/mimalloc để tránh).
• Cache locality: stack frame của function đang chạy thường nằm trong L1 cache vì truy cập liên tục. Heap data nằm rải rác trong RAM, cache miss nhiều hơn — đặc biệt với LinkedList, HashMap chứa node phân tán.

use std::time::Instant;

fn main() {
    let n = 1_000_000;

    // Stack alloc / dealloc: tạo array nhỏ trong vòng lặp
    let t1 = Instant::now();
    let mut sum_stack: u64 = 0;
    for _ in 0..n {
        let arr = [1u32; 16];           // 64 byte trên stack - không syscall
        sum_stack += arr[0] as u64;
    }
    println!("stack:  {sum_stack:>10}  {:?}", t1.elapsed());

    // Heap alloc / dealloc: tạo Vec nhỏ trong vòng lặp
    let t2 = Instant::now();
    let mut sum_heap: u64 = 0;
    for _ in 0..n {
        let v: Vec<u32> = vec![1; 16];  // mỗi vòng allocator cấp + free 64 byte
        sum_heap += v[0] as u64;
    }
    println!("heap:   {sum_heap:>10}  {:?}", t2.elapsed());
}

// Chạy release thực tế: heap loop thường chậm hơn stack loop 5-50x
// tuỳ allocator. Kiểu hơn nữa: jemalloc/mimalloc nhanh, glibc default chậm hơn.

Rule of thumb khi viết Rust performance-aware: tránh alloc trong hot loop. Pre-allocate Vec::with_capacity(n) 1 lần ngoài loop, reuse buffer, dùng SmallVec/ArrayVec để inline trên stack khi size đủ nhỏ.

Stack không phải vô hạn. Nó là một vùng memory cố định được OS cấp khi thread khởi tạo. Default thực tế năm 2026:

• Linux: 8 MB cho main thread (xem qua ulimit -s), 2 MB cho thread spawn qua pthread (sửa được).
• macOS: 8 MB main thread, 512 KB cho thread phụ.
• Windows: 1 MB main thread, mặc định 1 MB cho thread mới (cấu hình qua linker flag /STACK).
• Embedded / no_std: có thể chỉ vài KB tuỳ vi điều khiển.

Heap thì lớn hơn nhiều bậc — bị giới hạn bởi RAM vật lý + swap + virtual address space (trên 64-bit thực tế nhiều TB).

Hệ quả thực tế: đặt array quá lớn trên stack hoặc đệ quy quá sâu sẽ gây stack overflow — crash chương trình ngay, không phải lỗi recoverable.

// Demo 1: array quá lớn trên stack
fn array_too_big() {
    // 10 triệu i64 = 80 MB - vượt xa stack 8 MB
    // let huge = [0i64; 10_000_000];  // STACK OVERFLOW khi chạy

    // Fix: chuyển sang heap qua Box hoặc Vec
    let huge = vec![0i64; 10_000_000];  // 80 MB trên heap - OK
    println!("len = {}", huge.len());
}

// Demo 2: đệ quy quá sâu - mỗi call thêm 1 frame
fn recurse(n: u64) -> u64 {
    if n == 0 { 0 } else { 1 + recurse(n - 1) }
}

fn main() {
    array_too_big();

    // Mỗi frame của recurse chiếm vài chục byte (n + return addr + saved reg).
    // n = 100_000: thường OK.
    // n = 10_000_000: stack overflow (frame * size > 8 MB).
    // println!("{}", recurse(10_000_000));  // CRASH

    println!("{}", recurse(10_000));        // OK
}
// Stack overflow KHÔNG phải panic - là OS signal (SIGSEGV trên Unix).
// Không catch được bằng catch_unwind. Phải tránh từ design.

Khi gặp recursion sâu (parser AST nested, traversal cây), pattern Rust là chuyển sang iterative với explicit stack (Vec làm worklist trên heap). Hoặc dùng stacker crate để tự grow stack.

Quy tắc đơn giản: nếu compiler biết chính xác size ở compile-time và không có heap allocation ngầm trong type, value sẽ nằm thẳng trên stack frame.

Các kiểu nằm trên stack mặc định:

• Tất cả primitives: i8..i128, u8..u128, isize/usize, f32, f64, bool, char.
• Tuple của primitives: (i32, f64, bool) = 16 byte (do padding alignment) trên stack.
• Array cố định [T; N]: size = N * size_of::<T>() biết trước → stack. Cẩn thận: [u8; 10_000_000] = 10 MB sẽ overflow.
• Struct chỉ chứa stack data: struct Point { x: i32, y: i32 } = 8 byte trên stack.
• Reference &T, &mut T: chỉ là một pointer (8 byte trên 64-bit) → bản thân pointer trên stack, target có thể ở đâu cũng được.
• Function pointer, raw pointer *const T/*mut T: 8 byte trên stack.

use std::mem::size_of;

#[derive(Debug)]
struct Point { x: i32, y: i32 }

fn main() {
    // size_of cho biết bao nhiêu byte type chiếm trên stack frame
    println!("i32      = {} byte", size_of::<i32>());            // 4
    println!("i64      = {} byte", size_of::<i64>());            // 8
    println!("f64      = {} byte", size_of::<f64>());            // 8
    println!("bool     = {} byte", size_of::<bool>());           // 1
    println!("char     = {} byte", size_of::<char>());           // 4 (Unicode Scalar Value)
    println!("(i32,f64)= {} byte", size_of::<(i32, f64)>());     // 16 (padding)
    println!("[i32;5]  = {} byte", size_of::<[i32; 5]>());       // 20
    println!("Point    = {} byte", size_of::<Point>());          // 8
    println!("&i32     = {} byte", size_of::<&i32>());           // 8 (64-bit pointer)
    println!("&mut i32 = {} byte", size_of::<&mut i32>());       // 8

    // Tất cả nằm trên stack frame của main:
    let a: i32 = 42;
    let b: f64 = 3.14;
    let p = Point { x: 1, y: 2 };
    let arr: [u8; 4] = [1, 2, 3, 4];
    let r: &i32 = &a;

    println!("{a} {b} {p:?} {arr:?} {r}");
}

Tất cả các type ở đây đều implement trait Copy (sẽ học ở bài 62) — bitwise copy khi assign vì rẻ và không cần track ownership của heap.

Các type "owner của heap" có một đặc điểm chung: bản thân chúng là một struct nhỏ trên stack chứa pointer trỏ tới data thực trên heap. Khi struct trên stack drop, destructor (Drop::drop) chạy để gọi allocator free vùng heap đã cấp.

Danh sách phổ biến:

• Box<T>: single ownership pointer tới 1 T trên heap. Struct stack = 1 pointer (8 byte). Use case đơn giản nhất: ép một value lớn xuống heap, hoặc làm recursive type (Box<Node>).
• Vec<T>: struct stack = (ptr, len, cap) = 3 word = 24 byte trên 64-bit. Data thực = cap * size_of::<T>() byte liên tục trên heap.
• String: bản chất là Vec<u8> với invariant UTF-8 → cấu trúc giống Vec, 24 byte stack + n byte heap.
• Rc<T>: reference-counted single-thread, struct stack = 1 pointer; heap allocation chứa (strong_count, weak_count, T).
• Arc<T>: tương tự Rc nhưng count atomic, an toàn multi-thread.
• HashMap, BTreeMap, VecDeque, LinkedList: tất cả collection đều có heap allocation (cấu trúc nội bộ khác nhau nhưng cùng pattern "header stack, data heap").

use std::mem::size_of;

fn main() {
    // Phần trên stack (header) - cùng size bất kể nội dung heap to nhỏ thế nào
    println!("Box<i32>    stack = {} byte", size_of::<Box<i32>>());           // 8
    println!("Box<[u8;1M]> stack = {} byte", size_of::<Box<[u8; 1_000_000]>>()); // 8
    println!("Vec<i32>    stack = {} byte", size_of::<Vec<i32>>());           // 24
    println!("String      stack = {} byte", size_of::<String>());              // 24

    let b: Box<i32> = Box::new(7);          // 4 byte trên heap, pointer trên stack
    let v: Vec<i32> = vec![1, 2, 3];        // 12 byte heap (3 * 4), header 24 byte stack
    let s: String   = String::from("hi");   // 2 byte heap, header 24 byte stack

    println!("b = {b}");
    println!("v = {v:?}  len={} cap={}", v.len(), v.capacity());
    println!("s = {s}    len={} cap={}", s.len(), s.capacity());
}
// Khi main kết thúc:
//   - Frame main pop -> b, v, s "biến mất" (như stack data thường)
//   - Drop::drop chạy cho từng cái -> free heap allocation tương ứng
//   - Heap byte trả lại allocator

Đây là tinh thần "RAII" (Resource Acquisition Is Initialization) thừa hưởng từ C++ và làm xương sống ownership của Rust: scope của value trên stack quyết định lifetime của resource trên heap.

Hình ảnh dưới đây là mental model chuẩn mà bạn nên có trong đầu mỗi khi đọc Rust code có String/Vec. Phần stack là một struct nhỏ kích thước cố định 24 byte (3 word 64-bit); phần heap chứa byte thật của chuỗi.

let s = String::from("hi");

  STACK                          HEAP
  +---------+----------+         +---+---+
  |  ptr    | 0x1F2A   | ------> | h | i |
  +---------+----------+         +---+---+
  |  len    |    2     |
  +---------+----------+
  |  cap    |    2     |
  +---------+----------+

Khi s ra khỏi scope:
  - Stack frame pop (s biến mất)
  - Drop::drop(s) chạy -> deallocate heap bytes 0x1F2A..0x1F2B

Diễn giải từng trường:

• ptr: pointer (8 byte) trỏ tới byte đầu tiên của data heap. Đây là địa chỉ allocator trả về khi String::from gọi alloc.
• len: số byte đang dùng (8 byte, kiểu usize). Ở đây "hi" = 2 byte ASCII.
• cap: số byte heap đã được cấp (8 byte). Có thể lớn hơn len nếu pre-allocate; ở đây bằng nhau vì String::from("hi") cấp đủ chỗ.

Code minh chứng cho từng con số trên:

fn main() {
    let s = String::from("hi");

    // Header trên stack
    let ptr  = s.as_ptr();
    let len  = s.len();
    let cap  = s.capacity();

    println!("ptr  = {ptr:p}");     // địa chỉ heap, vd 0x600003b1c020
    println!("len  = {len}");       // 2
    println!("cap  = {cap}");       // 2
    println!("size_of::<String>() = {}", std::mem::size_of::<String>());  // 24

    // Đọc raw byte trên heap qua slice
    let bytes: &[u8] = s.as_bytes();
    println!("heap bytes = {bytes:?}");  // [104, 105] = 'h' 'i'

    // Push thêm để thấy heap re-alloc:
    let mut s2 = String::from("hi");
    println!("trước push: len={}, cap={}, ptr={:p}", s2.len(), s2.capacity(), s2.as_ptr());
    s2.push_str(" world from rust");
    println!("sau push:  len={}, cap={}, ptr={:p}", s2.len(), s2.capacity(), s2.as_ptr());
    // ptr có thể đổi vì allocator cấp block mới lớn hơn rồi memcpy
}                                 // s, s2 drop -> free heap tương ứng

Khi gán let s2 = s; (move), chỉ 24 byte header trên stack được copy bitwise sang biến s2, pointer cũ vẫn trỏ tới cùng vùng heap. Để tránh double-free, Rust invalidate s tại compile-time — đây chính là move semantics sẽ học ở bài 61.

Đến đây bạn đã có đủ vocabulary để nhìn ownership đúng bản chất:

• Stack data tự manage: scope kết thúc → frame pop → biến mất, không ai cần "owner" để track. Vì vậy primitives được Copy: assign nhiều biến cũng không vấn đề, mỗi biến giữ bản sao bitwise riêng, scope hết thì frame pop cả lượt.
• Heap data thì khác hẳn: dữ liệu nằm ngoài stack frame, lifetime không gắn vào frame của ai cụ thể. Phải có một "kế toán" trả lời 2 câu hỏi: (1) ai chịu trách nhiệm gọi free khi không còn dùng? (2) làm sao đảm bảo không free 2 lần (double-free) và không truy cập sau khi free (use-after-free)?

Mỗi paradigm trả lời khác nhau:

• C: programmer trả lời. malloc trả pointer, programmer phải nhớ gọi free đúng 1 lần đúng người. Sai → leak hoặc UB.
• Java/Go: GC trả lời. Runtime quét tìm pointer còn reference, free các block không reach được. Trade-off: pause time, throughput overhead.
• Rust: ownership rules trả lời ở compile-time:
  1. Mỗi value heap có đúng 1 owner.
  2. Move = chuyển ownership, owner cũ invalid.
  3. Owner ra khỏi scope → drop chạy → free heap.
  Compiler verify static, không cần runtime tracking.

Tóm gọn: ownership tồn tại chính là để quản lý heap. Nếu chương trình của bạn không dùng heap (toàn primitives, no_std embedded với fixed buffer), ownership rules vẫn áp dụng nhưng "vô hình" vì stack tự pop. Khi bắt đầu dùng String, Vec, Box, Rc... ownership trở thành công cụ chính giữ chương trình khỏi 70% lỗi memory phổ biến mà C/C++ gặp.

fn main() {
    // Không heap - không cần lo ownership "thấy được"
    let a = 42i32;
    let b = a;       // Copy, cả a và b đều dùng tiếp được
    println!("{a} {b}");

    // Có heap - ownership active
    let s1 = String::from("hello");
    let s2 = s1;     // MOVE - s1 invalid từ đây
    // println!("{s1}");  // compile error: borrow of moved value
    println!("{s2}");
}                     // s2 drop -> free heap 1 lần duy nhất, đúng người

Bài 60 sẽ phát biểu chính xác 3 quy tắc ownership, bài 61 đi sâu vào move semantics — nhưng giờ bạn đã có nền tảng để các bài sau "click" ngay từ lần đọc đầu.

• Stack: LIFO contiguous, push/pop O(1) chỉ chỉnh sp, mỗi function call tạo 1 frame, return pop tự động. Size compile-time biết trước.
• Heap: free-form, cấp phát qua allocator (search free chunk, có thể syscall mmap), địa chỉ tuỳ ý, cần metadata size để free đúng.
• Tốc độ: stack alloc < 1 ns, heap alloc 10-10000 ns; cache locality stack tốt hơn. Tránh alloc trong hot loop.
• Size limit: stack 1-8 MB tuỳ OS (Linux/macOS 8 MB main, Windows 1 MB), heap lên tới nhiều GB. Array lớn hoặc đệ quy sâu → stack overflow.
• Trên stack (Rust): primitives, tuple/array/struct of stack data, reference &T, function pointer. Compiler biết size cố định.
• Trên heap (Rust): Box<T>, Vec<T>, String, Rc<T>, Arc<T>, mọi collection. Header nhỏ trên stack chứa pointer + metadata, data thực trên heap.
• let s = String::from("hi"): struct 24 byte (ptr/len/cap) trên stack, 2 byte trên heap. Drop tự free heap khi s ra scope.
• Ownership rules tồn tại chính để quản lý heap: trả lời "ai free và khi nào" ở compile-time, không cần GC, không phụ thuộc programmer nhớ free().

Tự trả lời, đáp án ở cuối:

1. Vì sao compiler bắt buộc biết size của một type ở compile-time để đặt nó trên stack? Type nào trong Rust không biết size compile-time và bắt buộc phải đi qua pointer (heap hoặc reference)?
2. Đoạn code let huge = [0u8; 9_000_000]; trong fn main() sẽ chạy thế nào trên Linux (stack 8 MB default)? Sửa thế nào để hoạt động được?
3. std::mem::size_of::<Box<[u8; 1_000_000]>>() trả về bao nhiêu? Giải thích vì sao số đó không phải 1_000_000.
4. Một developer thấy code chậm, profile ra thì hot path đang gọi vec![0u8; 1024] trong vòng lặp 1 triệu lần. Đề xuất 2 cách tối ưu giảm alloc, giải thích cơ chế.
5. Bạn có một String s = "hello" đang sống trong fn main, rồi gọi fn take(s: String) truyền s vào. Vẽ (mô tả bằng lời) trạng thái stack và heap trong khi take đang chạy, và sau khi take return. Heap byte của "hello" lúc nào được free?

Bài 60: 3 Quy Tắc Ownership Của Rust — chính thức phát biểu 3 quy tắc nền tảng: mỗi value có duy nhất 1 owner, chỉ 1 owner một lúc, owner ra khỏi scope thì value drop. Đi từ memory model bài này sang quy tắc ngôn ngữ để mọi đoạn move/borrow/lifetime sau này đều quy về 3 phát biểu đơn giản này.