BỘ NHỚ STACK LÀ GÌ? TẠI SAO LẠI CÓ LỖI STACK OVERFLOW?

Hiểu về Stack để tránh Stack Overflow!Các bạn mới lập trình chắc hay thấy lỗi này, đặc biệt là khi học đến phần đệ quy, vậy bản chất của nó là gì?

Lưu ý: bài này chỉ dành cho ai muốn hiểu sâu về kỹ thuật – không chỉ định với người thích ăn xổi

Mỗi chương trình khi được tải vào máy tính để thực thi sẽ được cung cấp một phần bộ nhớ, phần bộ nhớ này sẽ được chia ra làm nhiều loại, với mục đích khác nhau. Một phần sẽ được dùng để chứa mã lệnh, thường thì phần này sẽ chỉ để đọc và chạy các lệnh chứa trong đó, một phần khác lại được dùng để chứa dữ liệu, bạn có thể đọc và ghi thoải mái, nhưng phải xin cấp phát trước khi dùng (malloc, new…) để tránh ghi đè lên dữ liệu của ứng dụng khác (ta hay gọi là bộ nhớ Heap).

Đọc thêm bài con trỏ để hiểu hơn về bộ nhớ máy tính: https://www.facebook.com/namdotnet/posts/1283909971794016

Còn một phần đặc biệt nữa gọi là bộ nhớ Stack

Trong môn cấu trúc dữ liệu, bạn sẽ được học một dạng cấu trúc dữ liệu tên là Stack, tạm hiểu nó như một mảng và mình chỉ có thể bỏ dữ liệu vào, hay lấy dữ liệu ra từ một đầu. Vậy nên cái nào đẩy vào (PUSH) sau cùng thì sẽ được lấy ra (POP) đầu tiên (LIFO).

Bộ nhớ Stack cũng vậy, nó là một phần bộ nhớ dùng để hỗ trợ việc gọi hàm (function). Bạn có thấy mỗi khi ta gọi 1 function, như x_and_y trong hình vẽ, việc thực thi sẽ được chuyển đến vị trí bắt đầu của hàm: ta đang ở dòng 14, thoắt cái nhảy lên dòng 5, thực hiện xong lại nhảy về dòng kế tiếp để thực thi. Nếu gặp một câu lệnh return trong x_and_y, nó cũng sẽ trở về đúng dòng 16 – dòng kế tiếp sau lời gọi hàm.

Máy tính thực hiện điều này bằng cách nào? Khi gặp một lời gọi hàm, trước lúc nhảy đến hàm được gọi, nó sẽ lấy địa chỉ câu lệnh kế tiếp (trong ví dụ này là 16) đẩy vào trong Stack, sau đó mới nhảy đến đầu function x_and_y để thực hiện, nếu trong x_and_y lại gặp một lời gọi hàm nữa, nó sẽ lại tiếp tục đẩy địa chỉ-kế tiếp-hiện tại vào Stack. Bây giờ, mỗi khi thực hiện xong một function, nó chỉ cần lấy địa chỉ bên trong Stack ra và thực hiện tiếp câu lệnh ở đó. Nhờ cơ chế LIFO (vào sau ra trước) mà máy tính sẽ luôn lấy ra được địa chỉ cần thực thi sau lời gọi CUỐI CÙNG, và nó sẽ luôn trở về đúng chỗ.

Ngoài việc lưu trữ địa chỉ trở về, Stack còn là nơi chứa các tham số, và các biến địa phương (local) – tức các biến được khai báo bên trong function. Mỗi lần bạn gọi một function, các giá trị của bạn sẽ được đưa vào Stack, sau đó đến địa chỉ trở về, rồi tới các biến local. Có nghĩa là mỗi lần gọi hàm, bạn sẽ lấy mất một phần trong Stack, phần này chỉ được trả lại khi bạn thoát ra khỏi hàm (tới đây bạn cũng sẽ hiểu tại sao các tham số và biến local chỉ có thể tồn tại bên trong phạm vi hàm đó). Bạn có thể nhìn trong hình minh họa để thấy chúng được lưu như thế nào.Bây giờ bạn đã thấy cứ mỗi lần gọi hàm, bộ nhớ Stack trống sẽ giảm đi một phần bằng với kích thước các tham số + địa chỉ trở về + kích thước các biến local, càng gọi phần Stack trống càng bé lại, đến lúc nào đó sẽ bị đầy, bạn sẽ không thể gọi hàm thêm được nữa, ngược lại vẫn cố gọi sẽ xảy ra lỗi Stack overflow – ứng dụng đi đứt, khách hàng cắt hợp đồng, sếp mắng chửi và bạn bị thôi việc.

Vậy làm sao để tránh lỗi này?Nếu đã hiểu lý do tạo ra lỗi, thì việc tránh rất đơn giản:- Không nên truyền qua tham số các biến có kích thước quá lớn.- Không nên dùng các biến local có kích thước quá lớn. Bạn có thể sử dụng con trỏ và xin cấp phát vùng nhớ trên Heap thay cho việc khai báo các biến hoặc các tham số có kích thước lớn.- Không gọi hàm quá sâu, lỗi này hay gặp trong lúc viết các function dạng đệ quy, khi chương trình đệ quy quá nhiều mà vẫn không gặp điều kiện thoát. Trường hợp bạn phải gọi đệ quy nhiều thì nên cân nhắc chuyển về dùng vòng lặp.

Ghi chú 1: Trong Windows, kích thước Stack mặc nhiên là 1MB, giá trị này có thể thay đổi bởi người lập trình hoặc thiết đặt hệ thống. Trong thực tế nếu dùng đúng cách thì 1MB là quá đủ, bạn có thể phải gọi đệ quy hàng trăm hàng ngàn lần mới tạo ra lỗi này, thậm chí có thể hơn, tuy nhiên một thuật toán phải gọi đệ quy nhiều đến như vậy thì cần xem xét lại về hiệu năng và độ ổn định.

Ghi chú 2: Trong hình minh họa ta sẽ thấy Stack nằm lộn ngược từ trên xuống, đó cũng là cách bộ nhớ Stack được tổ chức trong thực tế, nhờ phát triển từ địa chỉ cao xuống địa chỉ thấp mà CPU có thể phát hiện ra lỗi Stack overflow một cách dễ dàng (so sánh với 0).

Vì có một số bạn phàn nàn hình không chính xác nên mình post thêm cái hình chính xác hơn lên.

Tuy nhiên, đây là bài viết dành cho người lần đầu biết đến Stack nên hình thứ nhất hoàn toàn có thể giúp bạn hiểu được vấn đề.

Stack không phải là thứ chỉ có trên các CPU x86, do vậy nếu đi vào chi tiết, cái đúng trên bộ xử lý này có thể là sai trên bộ xử lý khác, và việc đi vào chi tiết vào bộ xử lý là không phù hợp trong bài viết này.