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
#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;
}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ếp | Ví dụ |
|---|---|
| Biến cục bộ | int x; char bo_dem[256]; |
| Tham số hàm | Cá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ếp | Vùng cấp phát động | |
|---|---|---|
| Cấp phát | Một phép trừ | Tìm khối trống phù hợp, cập nhật sổ sách |
| Thu hồi | Một phép cộng | Ghép khối trống, cập nhật sổ sách |
| Thứ tự thu hồi | Bắt buộc ngược với thứ tự cấp | Tùy ý |
| Chi phí tương đối | Gần bằng không | Hàng chục tới hàng trăm chu kỳ |
| Ai quản lý | Trình biên dịch | Bạn |
| Có thể quên thu hồi | Không | Có, và đó là rò rỉ bộ nhớ |
#Kích thước và giới hạn
| Nền tảng | Kích thước mặc định | Cách xem hoặc đổi |
|---|---|---|
| Linux, luồng chính | 8 MB | ulimit -s |
| Linux, luồng phụ | 8 MB | pthread_attr_setstacksize |
| macOS, luồng chính | 8 MB | ulimit -s |
| macOS, luồng phụ | 512 KB | pthread_attr_setstacksize |
| Windows | 1 MB | cờ /STACK của trình liên kết |
| Hệ nhúng | Vài KB tới vài chục KB | Ghi trong tệp cấu hình liên kết |
8192 # đơn vị là kilobyte
#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
void f(void)
{
double a[1000][1000]; /* 8 MB, sập ngay khi vào hàm */
a[0][0] = 1.0;
}/* 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.
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ế
#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;
}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ụ
7ffd8c28b000-7ffd8c2ac000 rw-p 00000000 00:00 0 [stack]
ERROR: AddressSanitizer: stack-overflow on address 0x7ffc4e8a0ff8
Tự làm thử
- 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.
- Xem
ulimit -strê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. - 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.
- Thêm
staticvào mảng đó và chạy lại, giải thích vì sao giờ nó hoạt động. - Cài chương trình đo độ sâu ngăn xếp, chạy với
-O0và với-O2rồi so kết quả. - Bật
-Wframe-larger-than=1024lên một chương trình cũ của bạn và xem hàm nào bị cảnh báo. - 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-thanvà-Wvlađể trình biên dịch cảnh báo trước khi chuyện đó xảy ra.