✨Lỗi tràn ngăn xếp

Trong lập trình, lỗi tràn ngăn xếp xảy ra nếu các con trỏ ngăn xếp vượt quá giới hạn của ngăn xếp. Ngăn xếp có thể bao gồm một lượng hữu hạn các địa chỉ không gian, thường được xác định điểm bắt đầu của chương trình. Kích thước của ngăn xếp phụ thuộc vào nhiều yếu tố, bao gồm cả các chương trình, ngôn ngữ lập trình, kiến trúc, đơn/đa luồng, và lượng bộ nhớ có sẵn. Khi một chương trình cố gắng sử dụng nhiều không gian bộ nhớ hơn lượng bộ nhớ có sẵn trong ngăn xếp (nói cách khác, khi chương trình cố gắng truy cập vùng bộ nhớ ngoài giới hạn ngăn xếp, mà bản chất là lỗi tràn bộ nhớ đệm), ngăn xếp sẽ được coi là tràn và_ _thường dẫn đến chương trình lỗi hoặc chạy sai.

Phép đệ quy vô hạn

Nguyên nhân phổ biến nhất của lỗi tràn ngăn xếp là đệ quy quá sâu hoặc đệ quy vô hạn, trong đó có một hàm tự gọi mình quá nhiều lần làm không gian cần thiết để lưu trữ các biến và thông tin liên kết với mỗi lần gọi nhiều hơn kích thước ngăn xếp hiện có.

Một ví dụ về đệ quy vô hạn trong C.

int foo() { return foo(); }

Hàm foo, khi được gọi, nó tiếp tục gọi tự phân bổ thêm không gian trên ngăn xếp, cho đến khi ngăn xếp tràn, gây ra lỗi segmentation fault. Tuy nhiên, một số trình dịch thực hiện đệ quy đuôi, cho phép đệ quy vô hạn mà không bị tràn ngăn xếp. Bởi vì gọi đệ quy đuôi sẽ không mất thêm không gian của ngăn xếp.

Các trình biên dịch C sẽ có hiệu quả khi gọi đệ quy đuôi; Khi biên dịch chương trình đơn trên sử dụng gcc với đối số -O1 sẽ dẫn đến lỗi segmentation fault, nhưng lại không gây ra lỗi khi sử dụng đối số -O2 hoặc -O3, vì những chúng chỉ đến đối số -foptimize-sibling-calls trong tùy chọn trình biên dịch. Các ngôn ngữ khác, chẳng hạn như Scheme, yêu cầu tất cả các chỉ định để gọi đệ quy đuôi như là một phần của tiêu chuẩn ngôn ngữ.

Lỗi đệ quy quá sâu

Một hàm đệ quy hữu hạn theo lý thuyết nhưng gây ra lỗi tràn bộ đệm ngăn xếp trong thực tế có thể được sửa bằng cách chuyển đổi đệ quy thành một vòng lặp và lưu trữ các đối số chức năng trong một ngăn xếp. Điều này luôn luôn có thể, bởi vì lớp các hàm đệ quy ban đầu tương đương với lớp các hàm tính toán LOOP. Hãy xem xét ví dụ này trong mã giả như-C++ sau: void function (argument) { if (condition) { function (argument.next); } }

Khử đệ quy bằng cách tạo một vòng lặp: stack.push(argument); while (!stack.empty()) { argument = stack.pop(); if (condition) stack.push(argument.next); }

Ngăn xếp quá lớn

Một nguyên nhân khác gây ra tràn ngăn xếp là cấp phát bộ nhớ quá nhiều cho ngăn xếp, ví dụ như việc tạo các biến mảng cục bộ quá lớn. Vì lý do này, một số tác giả khuyên các mảng lớn hơn một vài kilobyt nên được cấp phát bộ nhớ động thay vì như là một biến cục bộ. 

Đây là một ví dụ của biến ngăn xếp quá lớn trong C: int foo() { double x[1048576]; }

Trong đoạn mã này, mảng x đã sử dụng 8 mebibytes dữ liệu (giả thiết mỗi biến _double_ là 8 bytes). Nếu lượng bộ nhớ này nhiều bộ nhớ hơn bộ nhớ có sẵn trong ngăn xếp (được thiết lập bởi số luồng xử lí hoặc do giới hạn hệ điều hành) thì sẽ xảy ra lỗi tràn ngăn xếp.

Lỗi tràn ngăn xếp sẽ trở nên tồi tệ hơn bởi bất cứ điều gì làm giảm kích thước ngăn xếp một cách hiệu quả của một chương trình nhất định. Ví dụ, cùng một chương trình đang chạy mà không sử dụng kiến trúc đa luồng có thể hoạt động tốt, nhưng khi được kích hoạt kiến trúc đa luồng, chương trình sẽ "sập". Điều này là bởi vì hầu hết các chương trình đa luồng có ít không gian ngăn xếp cho mỗi luồng hơn một chương trình không có hỗ trợ đa luồng. Bởi vì nhân hệ điều hành nói chung là dựa trên kiến trúc đa luồng nên những nhà phát triển nhân hệ điều hành thường không khuyến khích sử dụng các thuật toán đệ quy hoặc có bộ đệm ngăn xếp lớn.