Stack và stack frame — gọi hàm sống và chết thế nào

TL;DR: Khi một hàm được gọi, CPU dành một khối bộ nhớ liên tục trên stack gọi là stack frame — chứa tham số, biến cục bộ, và địa chỉ trả về (để biết quay lại đâu sau khi hàm xong). Frame được đẩy vào (push) khi gọi hàm và bật ra (pop) khi hàm trả về, theo đúng thứ tự LIFO (last in, first out). Vì biến cục bộ sống trong frame, chúng tự động biến mất khi hàm kết thúc — không cần dọn thủ công. Stack có kích thước cố định và nhỏ (thường 512 KB–8 MB); đệ quy quá sâu hoặc mảng cục bộ khổng lồ làm tràn stack, sinh StackOverflowError. Hiểu stack giải thích vì sao biến cục bộ nhanh, vì sao đệ quy tốn bộ nhớ, và vì sao không được trả về con trỏ tới biến cục bộ.

Bạn viết một hàm đệ quy tính giai thừa, quên điều kiện dừng, và chương trình chết với StackOverflowError sau vài nghìn lần gọi. Bạn tự hỏi: tại sao một hàm đơn giản với một biến int lại làm "tràn" thứ gì đó? Và "stack" đang tràn là cái gì?

Bài này giải thích stack là gì, một stack frame chứa gì, cách frame được tạo và huỷ qua mỗi lời gọi hàm, và hệ quả thực tế lên cách bạn viết hàm đệ quy và quản lý biến cục bộ.

1. Analogy — chồng đĩa trong nhà bếp

Hình dung một chồng đĩa: bạn chỉ thêm đĩa lên đỉnh và lấy đĩa cũng từ đỉnh. Đĩa bỏ vào sau cùng là đĩa lấy ra đầu tiên — đó là LIFO.

Mỗi lần bạn gọi một hàm, hệ thống đặt một "đĩa" mới lên đỉnh stack — đĩa đó là stack frame của hàm, chứa mọi thứ hàm cần: tham số, biến cục bộ, và một mẩu giấy ghi "gọi xong thì quay lại dòng nào". Khi hàm trả về, đĩa trên đỉnh bị lấy đi (pop), lộ ra đĩa của hàm đã gọi nó — và chương trình tiếp tục từ chỗ mẩu giấy chỉ.

2. Cơ chế — một stack frame chứa gì

Khi hàm B được gọi từ A, một frame mới cho B được push lên stack. Frame điển hình chứa:

• Tham số truyền vào B.
• Biến cục bộ khai báo trong B.
• Địa chỉ trả về — vị trí trong A để tiếp tục sau khi B xong.
• Saved registers — vài thanh ghi A đang dùng, lưu lại để khôi phục.

CPU theo dõi đỉnh stack bằng một thanh ghi đặc biệt: stack pointer (SP). Push một frame chỉ là dịch stack pointer đi một khoảng bằng kích thước frame — cực nhanh, một lệnh duy nhất. Đây là lý do cấp phát biến cục bộ gần như miễn phí so với heap.

Xét ví dụ:

int main() {
    int x = 5;
    int r = square(x);   // goi square, day frame
    return r;
}

int square(int n) {
    int result = n * n;  // n va result song trong frame cua square
    return result;       // pop frame, tra ve main
}

Stack tại thời điểm square đang chạy. Lưu ý quy ước phổ biến: stack "lớn xuống dưới", nghĩa là frame mới được push về phía địa chỉ thấp hơn — ngược hướng so với analogy chồng đĩa ở mục 1, nhưng vẫn là LIFO. Sơ đồ dưới vẽ theo địa chỉ: cao ở trên, thấp ở dưới, nên frame mới nhất (square) nằm dưới cùng:

Dia chi cao
   +---------------------------+
   | Frame main                |
   |   x = 5                   |
   |   r = ?                   |
   +---------------------------+
   | Frame square   <- dinh    |   <- stack pointer
   |   n = 5                   |
   |   result = 25             |
   |   return addr -> main     |
   +---------------------------+
Dia chi thap

Khi square chạy return result, frame của nó bị pop: stack pointer dịch ngược lên, n và result "biến mất" (vùng nhớ được tái dùng cho lời gọi sau). Giá trị 25 được chuyển về main qua thanh ghi, gán vào r. Không ai phải "giải phóng" n hay result — chúng chết tự động khi frame pop.

sequenceDiagram
  participant M as main
  participant S as square
  M->>S: goi square(5) — push frame
  Note over S: n=5, result=25
  S-->>M: return 25 — pop frame
  Note over M: r = 25

3. Đệ quy và stack overflow

Mỗi lời gọi hàm tốn một frame. Đệ quy nghĩa là hàm tự gọi chính nó — mỗi cấp đệ quy đẩy thêm một frame, tất cả cùng tồn tại trên stack cho tới khi cấp sâu nhất trả về.

long factorial(int n) {
    if (n <= 1) return 1;        // base case: dung de quy
    return n * factorial(n - 1); // moi lan goi day them mot frame
}

Gọi factorial(4) tạo một chuỗi frame chồng nhau:

factorial(4)  -> can factorial(3)
  factorial(3)  -> can factorial(2)
    factorial(2)  -> can factorial(1)
      factorial(1)  -> tra ve 1   (base case, bat dau pop nguoc)

Bốn frame cùng sống ở đỉnh điểm. Stack có giới hạn cứng — nếu đệ quy không có base case (hoặc base case không bao giờ đạt), frame chồng mãi cho tới khi vượt giới hạn stack và OS ném StackOverflowError:

int boom(int n) {
    return boom(n + 1);  // khong co base case -> StackOverflowError
}

Kích thước stack mặc định: thường 512 KB tới vài MB mỗi luồng. Một frame nhỏ (vài chục byte) cho phép vài chục nghìn cấp đệ quy; một frame có mảng cục bộ lớn (int[10000]) làm tràn nhanh hơn nhiều.

4. Áp dụng vào code của bạn

Hiểu vòng đời frame giúp bạn tránh hai bug nguy hiểm và chọn đúng chiến lược đệ quy.

Bug 1 — trả về con trỏ tới biến cục bộ (dangling pointer). Trong C, biến cục bộ chết khi frame pop; trả về địa chỉ của nó là trỏ tới vùng nhớ đã chết:

int* badCounter() {
    int count = 0;       // count song trong frame badCounter
    return &count;       // SAI: tra ve dia chi cua count
}                        // frame pop -> count chet -> con tro lo lung

// Goi: int *p = badCounter(); *p = 5;  // undefined behavior!

Vùng nhớ của count sẽ bị lời gọi hàm tiếp theo ghi đè. Java/Python miễn nhiễm bug này vì chúng đặt object trên heap và GC giữ chúng sống chừng nào còn tham chiếu — nhưng đây là lý do cốt lõi để hiểu vì sao object "thoát khỏi" hàm phải nằm trên heap, không phải stack.

Bug 2 — mảng cục bộ khổng lồ làm tràn stack:

void process() {
    int[] buffer = new int[2_000_000]; // ~8 MB
    // ...
}

Trong Java, mảng object thực ra nằm trên heap (chỉ tham chiếu trên stack), nên ví dụ này an toàn. Nhưng trong C/C++ với mảng trên stack (int buffer[2000000];), 8 MB vượt stack mặc định → tràn. Quy tắc: dữ liệu lớn hoặc kích thước không biết trước → đặt trên heap.

Chuyển đệ quy sâu thành iterative. Khi độ sâu đệ quy phụ thuộc input:

// De quy: rui ro tran stack voi cay sau
void traverse(Node node) {
    if (node == null) return;
    visit(node);
    traverse(node.left);
    traverse(node.right);
}

// Iterative: dung stack tuong minh tren heap (lon hon nhieu)
void traverse(Node root) {
    Deque<Node> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        visit(node);
        if (node.right != null) stack.push(node.right);
        if (node.left  != null) stack.push(node.left);
    }
}

Bản iterative dời "stack lời gọi" từ call stack (nhỏ, cố định) sang một ArrayDeque trên heap (lớn tới hàng GB), nên chịu được độ sâu lớn hơn nhiều bậc.

5. Đào sâu (tuỳ chọn)

6. Liên hệ các bài khác

• Bài 01 — Địa chỉ và con trỏ: biến cục bộ và địa chỉ trả về trong frame đều là địa chỉ; bug "trả về con trỏ tới biến cục bộ" chỉ hiểu được khi nắm con trỏ.
• Bài 03 — Heap và cấp phát động: dữ liệu cần sống lâu hơn hàm phải đặt trên heap, không phải stack — bài này giải thích heap làm điều đó thế nào.
• Bài 04 — Stack vs heap vs static: tổng hợp ba vùng nhớ và quy tắc chọn; stack là vùng nhanh nhất nhưng vòng đời bị ràng buộc theo frame.

7. Tóm tắt

• Stack là vùng nhớ LIFO; mỗi lời gọi hàm push một stack frame chứa tham số, biến cục bộ và địa chỉ trả về.
• Push/pop frame chỉ là dịch stack pointer — một lệnh, gần như miễn phí. Đây là lý do biến cục bộ rất nhanh.
• Biến cục bộ tự dọn khi frame pop: vòng đời trùng khít với frame, không cần free, không rò bộ nhớ.
• Stack có giới hạn cứng (512 KB–8 MB/luồng). Đệ quy quá sâu hoặc mảng cục bộ lớn làm tràn → StackOverflowError.
• Không trả về con trỏ tới biến cục bộ (C) — frame pop làm nó thành dangling pointer. Dữ liệu cần sống lâu hơn hàm phải nằm trên heap.
• Khi độ sâu đệ quy phụ thuộc input không kiểm soát được, chuyển sang iterative + stack tường minh trên heap.
• JVM không đảm bảo tail call optimization — đệ quy sâu trong Java vẫn tràn dù viết ở tail position.

8. Tự kiểm tra

Bài tiếp theo: Heap và cấp phát động