Bài 212: Box<T> — Heap Allocation

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

• Hiểu Box<T> là smart pointer cấp phát T trên heap; bản thân Box là một struct nhỏ giữ pointer (8 byte trên hệ 64-bit) nằm trên stack.
• Biết cú pháp tạo Box::new(value) và truy cập qua deref *b; biết vì sao deref hoạt động (nhờ trait Deref sẽ học ở Bài 213).
• Liệt kê được bốn use case chính của Box: recursive type, large struct tránh stack overflow, trait object polymorphism, transfer ownership large data tránh copy.
• Viết được recursive enum kiểu cons-list enum List { Cons(i32, Box<List>), Nil } và giải thích vì sao thiếu Box thì compiler báo lỗi vô hạn size.
• Dùng Box<dyn Trait> để tạo collection heterogeneous, ôn lại preview từ Nhóm 22 (Trait Objects).
• Hiểu cơ chế Drop tự động giải phóng heap khi Box ra khỏi scope — không cần manual free, không leak nếu ownership đi đúng đường.
• Biết Box::leak chuyển Box thành &'static mut T — leak có chủ ý phục vụ global config khởi tạo runtime.
• Đánh giá được chi phí của heap allocation (chậm hơn stack 10-100 lần), nguyên tắc "chỉ dùng Box khi cần".

Bài tiếp theo (213) đi sâu vào Deref trait và Deref coercion — cơ chế giúp Box<T> hành xử như reference &T trong nhiều ngữ cảnh, và là chìa khoá để các smart pointer khác (Rc, Arc, RefCell) cũng "đi qua được" mọi nơi nhận reference.

Box<T> là smart pointer đơn giản nhất trong stdlib Rust — một struct sở hữu một giá trị kiểu T được cấp phát trên heap. Khác với reference &T (mượn) hay *const T (raw pointer), Box own giá trị: khi Box bị drop, vùng heap mà nó trỏ tới được giải phóng. Đó là lý do gọi là smart — không chỉ là con trỏ, mà còn quản lý lifetime của data được trỏ tới.

Về layout, Box là một struct rất gọn: trên hệ 64-bit nó chỉ chứa đúng một pointer 8 byte (cùng kích thước với &T hay *const T). Pointer này nằm trên stack (cùng frame với biến Box) và trỏ tới vùng heap chứa giá trị thật. Khi bạn viết let b = Box::new(5_i32), runtime sẽ cấp phát 4 byte heap cho i32, ghi giá trị 5 vào đó, rồi gán pointer của vùng heap đó vào biến b trên stack.

So sánh nhanh với stack allocation: let x = 5_i32 sẽ đặt 4 byte ngay trên stack frame, không cấp phát heap. Stack alloc rẻ (chỉ tăng/giảm stack pointer — vài nanosecond), heap alloc đắt (gọi allocator, có thể syscall — hàng trăm nanosecond). Nguyên tắc Rust idiomatic: mặc định stack; chỉ đẩy lên heap khi có lý do. Box chính là công cụ để "có lý do" một cách rõ ràng, an toàn, và RAII.

Tạo Box bằng associated function Box::new(value) — nhận giá trị bằng value (move), cấp phát heap, đưa giá trị vào và trả về Box<T>. Truy cập lại bằng deref *b — Box implement trait Deref nên syntax giống reference.

fn main() {
    // 1) i32 trên heap, pointer trên stack
    let b: Box<i32> = Box::new(5);
    println!("b = {b}");          // 5 — auto deref qua Display
    println!("*b = {}", *b);      // 5 — deref tường minh
    println!("b + 1 = {}", *b + 1); // 6

    // 2) Move giá trị vào Box
    let s = String::from("Rust");
    let bs = Box::new(s);
    // println!("{s}"); // ERROR: s đã move vào bs
    println!("{}", *bs);          // Rust

    // 3) Lấy lại giá trị ra khỏi Box (consume)
    let n = *bs.into_inner_value_alternative(); // pseudo — thực tế dùng *bs
    // Đúng cú pháp:
    let bs2 = Box::new(String::from("Hello"));
    let inner: String = *bs2;     // move ra, Box bị consume
    println!("{inner}");
}

Hai điểm quan trọng. Một, Box thừa hưởng quy tắc ownership của Rust: khi gán let bs = Box::new(s), giá trị s bị move vào Box (không phải copy, trừ khi T là Copy). Hai, deref *b hoạt động nhờ impl Deref for Box<T> — chi tiết sẽ học ở Bài 213. Tạm hiểu: ở hầu hết các vị trí cần &T, bạn truyền &Box<T> cũng được vì compiler tự coerce.

Stack là default, dùng Box khi gặp các tình huống sau:

1. Recursive type: enum hoặc struct tham chiếu chính nó cần một mức indirect để compiler tính được size hữu hạn. Ví dụ kinh điển là linked list, cây AST, JSON value lồng nhau. Không có Box, compiler báo recursive type has infinite size.
2. Large struct: nếu struct có size lớn (vài KB trở lên) mà bạn lại move qua nhiều function, mỗi lần move là copy vài KB bytes trên stack — chậm và có nguy cơ stack overflow. Bọc trong Box thì move chỉ copy 8 byte pointer, dữ liệu thật ở yên trên heap.
3. Trait object polymorphism: Box<dyn Trait> cho phép giữ giá trị của nhiều kiểu khác nhau miễn cùng implement Trait, vào chung một biến hoặc collection. Đây là cách Rust làm runtime polymorphism — không thể làm với dyn Trait trần vì size không biết tại compile time.
4. Transfer ownership large data: khi bạn muốn return một large struct từ function, hoặc đẩy nó vào một channel/thread, Box giúp truyền ownership với cost chỉ là 8 byte pointer — không copy bytes thực tế.

Nguyên tắc ngược lại cũng đáng nhớ: nếu kiểu của bạn nhỏ (vài chục byte), không recursive, không cần polymorphism, thì đừng dùng Box. Stack alloc nhanh hơn, cache-friendly hơn, và Rust borrow checker giúp bạn an toàn mà không cần smart pointer.

Ví dụ kinh điển nhất của Box là cons-list (linked list kiểu Lisp). Mỗi node hoặc là Cons(value, next), hoặc là Nil kết thúc. Vấn đề: trường next cùng kiểu List — recursive — nếu khai báo trực tiếp thì compiler không tính được size:

// SAI: compiler báo "recursive type `List` has infinite size"
// enum List {
//     Cons(i32, List),
//     Nil,
// }

// ĐÚNG: Box phá vô hạn size
enum List {
    Cons(i32, Box<List>),
    Nil,
}

use List::{Cons, Nil};

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));

    // Duyệt
    let mut cur = &list;
    while let Cons(v, next) = cur {
        print!("{v} -> ");
        cur = next;
    }
    println!("Nil"); // 1 -> 2 -> 3 -> Nil
}

Vì sao Box "phá" vô hạn size? Compiler tính size enum bằng max size của các variant. Trước khi có Box, variant Cons(i32, List) cần size = sizeof(i32) + sizeof(List) — mà sizeof(List) lại phụ thuộc chính nó, đệ quy vô hạn. Khi bọc trong Box<List>, size của variant trở thành sizeof(i32) + sizeof(Box<List>) = 4 + 8 = 12 byte (cố định, vì Box luôn là 1 pointer). Recursion bị "cắt" ở mức indirect — node nằm đâu đó trên heap, Box chỉ giữ địa chỉ.

Nhóm 22 đã giới thiệu trait object. Ôn nhanh: dyn Trait là kiểu "có lớp lớn vô hạn" — đại diện cho mọi type implement Trait — nên size không biết tại compile time. Để dùng được, phải bọc qua một con trỏ có size cố định: &dyn Trait, Box<dyn Trait>, Rc<dyn Trait>... Trong đó Box<dyn Trait> là phổ biến nhất khi cần own trait object — ví dụ heterogeneous collection:

trait Animal {
    fn speak(&self) -> String;
}

struct Dog;
struct Cat;
struct Cow;

impl Animal for Dog { fn speak(&self) -> String { "Woof".into() } }
impl Animal for Cat { fn speak(&self) -> String { "Meow".into() } }
impl Animal for Cow { fn speak(&self) -> String { "Moo".into() } }

fn main() {
    // Vec chứa nhiều kiểu khác nhau qua Box<dyn Animal>
    let zoo: Vec<Box<dyn Animal>> = vec![
        Box::new(Dog),
        Box::new(Cat),
        Box::new(Cow),
    ];

    for a in &zoo {
        println!("{}", a.speak());
    }
    // Woof / Meow / Moo
}

Mỗi Box<dyn Animal> là một fat pointer 16 byte: một pointer trỏ tới object trên heap, một pointer trỏ tới vtable của type cụ thể. Khi gọi a.speak(), runtime lookup vtable, gọi đúng method tương ứng. Đây là cách Rust làm runtime dispatch — đánh đổi một chút overhead lấy khả năng dùng nhiều kiểu cùng một interface.

Một trong những lý do gọi Box là smart pointer (chứ không phải dumb pointer như void* trong C) là quản lý lifetime: khi Box ra khỏi scope, Rust tự gọi Drop::drop — giải phóng heap, không leak. Bạn không cần (và không nên) gọi free thủ công.

struct Big {
    data: [u8; 1024], // 1 KB
}

impl Drop for Big {
    fn drop(&mut self) {
        println!("Big bị drop, free heap 1 KB");
    }
}

fn main() {
    {
        let b = Box::new(Big { data: [0; 1024] });
        println!("Box tạo xong, kích thước b trên stack = {} byte", std::mem::size_of_val(&b));
        // ... dùng b ở đây
    } // Hết scope → b drop → Drop::drop chạy → heap được free

    println!("Sau scope, không leak");
}
// Output:
// Box tạo xong, kích thước b trên stack = 8 byte
// Big bị drop, free heap 1 KB
// Sau scope, không leak

Cơ chế: Box implement trait Drop. Khi compiler thấy biến Box hết scope, nó sinh code gọi drop(b) — code này sẽ (1) gọi Drop::drop trên giá trị bên trong nếu nó cũng implement Drop, và (2) gọi allocator để trả vùng heap về system. Toàn bộ chuyện này là compile-time inserted, không có garbage collector chạy ngầm. Hiệu năng deterministic — bạn biết chính xác khi nào heap được free.

Đôi khi bạn muốn cấp phát một giá trị, dùng nó suốt vòng đời chương trình, và không bao giờ giải phóng — biến nó thành reference 'static. Box::leak làm chính việc đó: nhận Box<T>, trả về &'static mut T, đồng thời ngăn destructor chạy (intentional leak).

struct Config {
    db_url: String,
    port: u16,
}

fn load_config() -> &'static Config {
    let cfg = Box::new(Config {
        db_url: std::env::var("DB_URL").unwrap_or_else(|_| "localhost".into()),
        port: 5432,
    });

    // Convert Box<Config> -> &'static mut Config
    // Sau dòng này, Config không bao giờ bị drop (intentional leak)
    Box::leak(cfg)
}

fn main() {
    let cfg: &'static Config = load_config();
    println!("DB: {}, Port: {}", cfg.db_url, cfg.port);

    // cfg sống đến hết chương trình — OS sẽ thu hồi memory khi process exit
}

Use case điển hình: global config khởi tạo runtime từ env var / file mà const hay static không làm được (vì cần runtime computation). Vì OS sẽ thu hồi toàn bộ memory khi process exit, leak này không gây hại nếu bạn chỉ leak một lần lúc khởi tạo. Tuyệt đối không gọi Box::leak trong loop hay request handler — nó sẽ leak từng phát, tích lũy thành memory leak thật.

Heap allocation không miễn phí. So với stack alloc (chỉ tăng/giảm stack pointer, vài cycle CPU), heap alloc phải gọi memory allocator — tìm vùng free phù hợp, có thể syscall mmap / sbrk, cập nhật metadata. Chi phí thực tế: stack ~1-2 ns, heap ~50-500 ns — chậm hơn khoảng 10-100 lần. Chưa kể cache miss: data trên heap thường rời rạc, kém cache-friendly so với data trên stack.

// Đo nhanh sự khác biệt
fn main() {
    let n = 1_000_000;

    // Stack alloc (i32 trên stack) — gần như free
    let t1 = std::time::Instant::now();
    for i in 0..n {
        let _x: i32 = i;
        std::hint::black_box(_x);
    }
    println!("Stack: {:?}", t1.elapsed());

    // Heap alloc (Box::new mỗi lần) — chậm hơn nhiều
    let t2 = std::time::Instant::now();
    for i in 0..n {
        let _x = Box::new(i);
        std::hint::black_box(&_x);
    }
    println!("Heap:  {:?}", t2.elapsed());
    // Trên máy điển hình: Stack vài ms, Heap vài chục đến trăm ms
}

Bài học rút ra: đừng Box mọi thứ "cho an toàn". Stack luôn là default tốt nhất. Chỉ Box khi (1) bắt buộc về mặt ngữ nghĩa (recursive, trait object), (2) struct thật sự lớn (vài KB), (3) có lý do nghiệp vụ rõ ràng (transfer ownership tránh copy, share heap data sau này qua Rc/Arc). Nếu chỉ là một i32 hay struct vài chục byte, không có lý do gì để bỏ vào Box.

• Box<T> là smart pointer cấp phát T trên heap; bản thân Box là struct nhỏ giữ pointer 8 byte trên stack.
• Cú pháp: Box::new(value) để tạo, deref *b để truy cập (nhờ trait Deref).
• Bốn use case chính: recursive type, large struct tránh stack overflow, trait object Box<dyn Trait>, transfer ownership large data.
• Recursive enum cần Box để compiler tính được size hữu hạn — kinh điển là cons-list enum List { Cons(i32, Box<List>), Nil }.
• Drop chạy tự động khi Box ra khỏi scope — heap được free, không leak, không cần manual free.
• Box::leak(b) convert Box<T> thành &'static mut T — intentional leak, useful cho global config khởi tạo runtime.
• Heap alloc chậm hơn stack 10-100 lần — chỉ dùng Box khi thực sự cần, default vẫn là stack.

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

1. Viết enum Tree { Leaf(i32), Node(Box<Tree>, Box<Tree>) } rồi tạo một cây nhị phân với root là Node và 2 lá lần lượt 1 và 2. Viết hàm sum_leaves(t: &Tree) -> i32 tính tổng các lá.
2. Trait Shape có method area(&self) -> f64. Implement cho Circle và Rect. Tạo Vec<Box<dyn Shape>> chứa cả hai, tính tổng diện tích.
3. Vì sao đoạn code enum L { Cons(i32, L), Nil } không compile? Sửa lại bằng Box và giải thích size của variant Cons sau khi sửa.
4. Viết function load_settings() -> &'static str trả về một string đọc từ env var APP_NAME (default "MyApp"), dùng Box::leak.
5. So sánh: let b = Box::new(5_i32); chiếm bao nhiêu byte trên stack? Bao nhiêu byte trên heap? Total là bao nhiêu?

Bài 213: Deref Trait & Deref Coercion — đào sâu cơ chế giúp Box<T> (và mọi smart pointer khác) hành xử như reference &T ở hầu hết các vị trí. Bạn sẽ implement Deref cho một smart pointer tự viết, hiểu vì sao &Box<String> tự coerce thành &String rồi tiếp tục thành &str qua nhiều bước, và biết khi nào Deref coercion xảy ra (function call, method call, field access) — kiến thức nền tảng để dùng thành thạo mọi smart pointer còn lại của Nhóm 27.