Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 14.118 phút đọc

Ngăn xếp

Sau bài này bạn sẽ làm được

  • Mô tả cách ngăn xếp cấp phát và thu hồi trong một phép tính duy nhất
  • Biết kích thước ngăn xếp mặc định trên từng nền tảng
  • Nhận ra ba nguyên nhân tràn ngăn xếp
  • Đo được độ sâu ngăn xếp thực tế của chương trình

Ngăn xếp là vùng nhớ bạn đã dùng suốt khóa học mà không cần nghĩ tới. Mọi biến cục bộ, mọi tham số, mọi lời gọi hàm đều nằm ở đó. Chương này bắt đầu bằng nó, vì hiểu ngăn xếp là điều kiện để hiểu vì sao vùng cấp phát động tồn tại.

#Cách ngăn xếp hoạt động

Ngăn xếp
Vùng nhớ hoạt động theo nguyên tắc vào sau ra trước. Cấp phát là giảm một thanh ghi, thu hồi là tăng lại thanh ghi đó. Toàn bộ việc quản lý do trình biên dịch sinh mã tự động.
Khung của hàm được gọi nằm ngay dưới khung của hàm gọi. Khi hàm kết thúc, cả khung biến mất bằng đúng một phép cộng.
ngan-xep.c
#include <stdio.h>

void c(void)
{
    int x = 3;

    printf("c: %p\n", (void *)&x);
}

void b(void)
{
    int x = 2;

    printf("b: %p\n", (void *)&x);
    c();
}

void a(void)
{
    int x = 1;

    printf("a: %p\n", (void *)&x);
    b();
}

int main(void)
{
    int x = 0;

    printf("main: %p\n", (void *)&x);
    a();

    return 0;
}
terminal
./ngan-xep
main: 0x7ffd8c2a1e4c
a: 0x7ffd8c2a1e2c
b: 0x7ffd8c2a1e0c
c: 0x7ffd8c2a1dec

Bốn địa chỉ giảm dần, mỗi khung cách nhau 32 byte. Đó là bằng chứng trực tiếp rằng ngăn xếp lớn dần về phía địa chỉ thấp, và mỗi lời gọi chiếm một khối liền nhau.

Thứ nằm trên ngăn xếpVí dụ
Biến cục bộint x; char bo_dem[256];
Tham số hàmCác đối số vượt quá số thanh ghi dành cho chúng
Địa chỉ trở vềChỗ cần quay về khi hàm kết thúc
Con trỏ khung đã lưuĐể khôi phục khung của hàm gọi
Thanh ghi cần giữNhững thanh ghi mà hàm này ghi đè

#Vì sao nó nhanh tới vậy

; Cấp phát 64 byte biến cục bộ: đúng MỘT lệnh
sub  rsp, 64

; Thu hồi toàn bộ: cũng đúng một lệnh
add  rsp, 64
Ngăn xếpVùng cấp phát động
Cấp phátMột phép trừTìm khối trống phù hợp, cập nhật sổ sách
Thu hồiMột phép cộngGhép khối trống, cập nhật sổ sách
Thứ tự thu hồiBắt buộc ngược với thứ tự cấpTùy ý
Chi phí tương đốiGần bằng khôngHàng chục tới hàng trăm chu kỳ
Ai quản lýTrình biên dịchBạn
Có thể quên thu hồiKhôngCó, và đó là rò rỉ bộ nhớ

#Kích thước và giới hạn

Nền tảngKích thước mặc địnhCách xem hoặc đổi
Linux, luồng chính8 MBulimit -s
Linux, luồng phụ8 MBpthread_attr_setstacksize
macOS, luồng chính8 MBulimit -s
macOS, luồng phụ512 KBpthread_attr_setstacksize
Windows1 MBcờ /STACK của trình liên kết
Hệ nhúngVài KB tới vài chục KBGhi trong tệp cấu hình liên kết
terminal
ulimit -s
8192      # đơn vị là kilobyte
# Nâng tạm thời cho phiên hiện tại
ulimit -s 16384 && ./chuong-trinh
# Trên Windows, đặt lúc liên kết
cl /F 4194304 bai.c

#Ba cách làm tràn ngăn xếp

Cách 1: đệ quy quá sâu

void vo_han(int n)
{
    printf("%d\n", n);
    vo_han(n + 1);      /* thiếu điều kiện dừng */
}

Bài 8.10 đã tính: với ngăn xếp 8 megabyte và khung khoảng 64 byte, độ sâu tối đa vào khoảng một trăm ba mươi nghìn tầng. Con số cụ thể phụ thuộc số biến cục bộ của hàm.

Cách 2: mảng cục bộ quá lớn

Mảng lớn trên ngăn xếp
void f(void)
{
    double a[1000][1000];      /* 8 MB, sập ngay khi vào hàm */

    a[0][0] = 1.0;
}
Ba cách thay thế
/* Cách 1: static, chuyển sang vùng .bss */
void f(void)
{
    static double a[1000][1000];      /* an toàn, nhưng chỉ có một bản dùng chung */

    a[0][0] = 1.0;
}

/* Cách 2: cấp phát động, học ở Bài 14.6 */
void f(void)
{
    double *a = malloc(1000 * 1000 * sizeof *a);

    if (a == NULL) return;

    a[0] = 1.0;

    free(a);
}

/* Cách 3: người gọi cấp, hàm chỉ dùng */
void f(double *a, size_t hang, size_t cot)
{
    a[0] = 1.0;
}

Cách 3: mảng có độ dài thay đổi

void f(size_t n)
{
    int a[n];      /* nếu n lớn, sập ngay, và KHÔNG có cách nào kiểm tra */

    a[0] = 1;
}

f(10000000);       /* 40 MB trên ngăn xếp */

Bài 9.2 đã cấm dùng mảng có độ dài thay đổi trong khóa học này, và đây là lý do chính. Khác với malloc trả về NULL khi hết bộ nhớ, mảng độ dài thay đổi không có cách nào báo thất bại.

terminal
gcc -std=c17 -Wall -Wextra -Wvla -Wframe-larger-than=16384 bai.c -o bai
bai.c:5:1: warning: the frame size of 8000016 bytes is larger than 16384 bytes [-Wframe-larger-than=]
bai.c:3:5: warning: ISO C90 forbids variable length array 'a' [-Wvla]

#Đo độ sâu thực tế

do-sau.c
#include <stddef.h>
#include <stdio.h>

static char *dinh_dau;

static void do_sau(int n)
{
    char moc;      /* biến này nằm trên khung hiện tại */

    if (n == 0) {
        dinh_dau = &moc;
        printf("khung dau : %p\n", (void *)&moc);
    }

    if (n == 10000) {
        ptrdiff_t tong  = dinh_dau - &moc;      /* tổng của 10000 khung */
        ptrdiff_t khung = tong / 10000;         /* một khung */

        printf("khung 10000: %p\n", (void *)&moc);
        printf("moi khung ton %td byte\n", khung);
        printf("do sau toi da uoc tinh: %td\n",
               (ptrdiff_t)(8L * 1024 * 1024) / khung);

        return;
    }

    do_sau(n + 1);
}

int main(void)
{
    do_sau(0);

    return 0;
}
terminal
gcc -std=c17 -O0 do-sau.c -o do-sau && ./do-sau
khung dau : 0x7ffd8c2a1e2f
khung 10000: 0x7ffd8c22cb2f
moi khung ton 48 byte
do sau toi da uoc tinh: 174762

Xem ngăn xếp bằng công cụ

terminal
# Xem vùng ngăn xếp thật trong bản đồ bộ nhớ
grep stack /proc/self/maps
7ffd8c28b000-7ffd8c2ac000 rw-p 00000000 00:00 0    [stack]
# Trình dò lỗi địa chỉ nói rõ khi tràn ngăn xếp
gcc -fsanitize=address -g bai.c -o bai && ./bai
ERROR: AddressSanitizer: stack-overflow on address 0x7ffc4e8a0ff8
# gdb cho thấy hàng nghìn khung giống nhau
gdb -q ./bai -ex run -ex 'bt 5'

Tự làm thử

  1. Cài chuỗi bốn hàm gọi lồng nhau, in địa chỉ biến cục bộ ở từng tầng và tính khoảng cách giữa các khung.
  2. Xem ulimit -s trên máy bạn, rồi nâng nó lên gấp đôi và chạy lại một chương trình đệ quy sâu.
  3. Khai báo mảng 8 megabyte làm biến cục bộ, chạy và quan sát chương trình sập ngay khi vào hàm.
  4. Thêm static vào mảng đó và chạy lại, giải thích vì sao giờ nó hoạt động.
  5. Cài chương trình đo độ sâu ngăn xếp, chạy với -O0 và với -O2 rồi so kết quả.
  6. Bật -Wframe-larger-than=1024 lên một chương trình cũ của bạn và xem hàm nào bị cảnh báo.
  7. Tạo tràn ngăn xếp rồi kiểm chứng đủ bốn dấu hiệu nhận biết trong bài.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Ngăn xếp cấp phát bằng một phép trừ và thu hồi bằng một phép cộng, nên nó gần như miễn phí.
  • Cái giá là kích thước phải biết lúc biên dịch, vòng đời gắn với khối lệnh, và dung lượng chỉ vài megabyte.
  • Ba cách làm tràn: đệ quy quá sâu, mảng cục bộ quá lớn, và mảng có độ dài thay đổi.
  • Chương trình tràn ngăn xếp do mảng lớn sẽ sập ngay khi vào hàm, trước cả câu lệnh đầu tiên.
  • Bật -Wframe-larger-than-Wvla để trình biên dịch cảnh báo trước khi chuyện đó xảy ra.