Stack Overflow Là Gì? Vì Sao Đệ Quy Lại Dễ Gây Tràn Stack?

Trong nội dung bài này, mình sẽ giải thích vì sao lại có hiện tượng tràn bộ nhớ Stack, và đặc biệt hay xảy ra khi gọi đệ quy.

Một số khái niệm

Bộ nhớ Stack: bộ nhớ dành riêng cho việc lưu trữ các biến cục bộ, tham số, kết quả trả về, và ghi nhớ các thanh ghi. Bộ nhớ này có giới hạn về kích thước.

Push: thao tác push và stack

Pop: thao tác lấy ra từ stack.

RBP – register base pointer – thanh ghi chứa địa chỉ bắt đầu của stack được sử dụng trong chương trình con hiện tại.

RSP – register stack pointer – đỉnh của stack hiện tại. Giá trị địa chỉ của stack sẽ giảm dần khi mình tăng kích thước của stack.

Vào bài thôi

Xét một hàm đơn giản như sau:

int add(int a, int b) {  return a + b; }

Ta thấy trong hàm này có 2 tham số là a và b. Khi biên dịch hàm này trên chip Intel 64bit ta có kết quả như sau:

_add:
 pushq %rbp  # đẩy giá trị của rbp vào bộ nhớ stack
 movq  %rsp, %rbp # gán địa chỉ bắt đầu bằng đỉnh của stack.
 movl %edi, -4(%rbp)  # chuyển giá trị của tham số thứ nhất từ thanh ghi %edi vào ô nhớ có địa chỉ %rbp - 4 (số int có kích thước 4 byte)
 movl %esi, -8(%rbp) # chuyển giá trị của tham số thứ hai (b) từ thanh ghi %esi vào ô nhớ có địa chỉ %rbp - 8
 movl -4(%rbp), %eax # gán a cho thanh ghi %eax - thanh ghi %eax sẽ chứa giá trị trả về của hàm
 addl -8(%rbp) %eax # cộng b cho thanh ghi %eax
 popq %rbp # phục hồi lại địa chỉ bắt đầu stack cho %rbp  
 retq # trở lại

Ta thấy hàm này này sử dụng tổng cộng 16 bytes trên stack (8 bytes để lưu %rbp và 8 bytes để lưu tham số a, b), khi gọi hàm này thì đỉnh của stack giảm đi 16 bytes. Sau khi kết thúc lời gọi hàm này thì bộ nhớ stack được giải phóng (tăng lên lại 16 bytes), đơn giản chưa mọi người?

Bây giờ ta sẽ xét tiếp trường hợp một hàm đệ quy:

Xét đoạn code sau:

int factorial(int n) {  if (n == 0) {    return 1;  }  return n * factorial(n - 1); }

Đoạn này sẽ được dịch ra Assembly như sau:

_factorial:
 pushq %rbp  # tương tự, đẩy giá trị của rbp vào bộ nhớ stack
 movq  %rsp, %rbp # gán địa chỉ bắt đầu bằng đỉnh của stack.
 subq $16, %rsp # trừ bộ nhớ stack đi thêm 16 bytes
 ….
 callq _factorial # gọi đệ quy
 …
 addq $16, %rsp # cộng đỉnh stack lại 16 bytes
 popq %rbp # phục hồi địa chỉ bắt đầu của stack
 retq       # trả về

Top việc làm C++ hấp dẫn trên TopDev đang chờ bạn ứng tuyển nè

Khi trong hàm chúng ta có lời gọi hàm thì chương trình sẽ tính lại đỉnh của stack (trong trường hợp này là -16 bytes, để dành 16 bytes để lưu các giá trị tính toán trung gian trong hàm). Trong hàm này, tổng cộng bộ nhớ stack được sử dụng là 24 bytes (16 bytes + 8 bytes để lưu con trỏ %rbp). Sau khi gọi hàm thì 24 bytes này sẽ được phục hồi và trả về lại trên hệ thống.

Nếu chúng ta gọi đệ quy thì bộ nhớ stack sẽ tăng liên tục sau mỗi lời gọi hàm, do bộ nhớ STACK có giới hạn, nên sẽ bị TRÀN STACK!!

Tada!! quá dễ sao nói rườm rà vậy?? Hy vọng lời giải thích rườm rà này sẽ giúp các bạn hiểu ra bản chất của vấn đề.

Tái bút:

• Thêm 1 lí do để viết Assembly vì hàm add trên trình duyệt làm hơi rườm rà, không cần xài stack luôn.

_add:
 movl %edi, %eax
 addl %esi, %eax
 retq

• Gọi là “Tràn Stack” có vẻ hơi sai vì địa chỉ stack được đánh giá ngược nên nó giảm cho đến khi bị tràn, chắc phải gọi là hụt stack mới đúng.
• Bộ nhớ stack không tự động bị xoá đi sau khi kết thúc lời gọi hàm, nên password, key, không nên lưu trữ dạng raw trong bộ nhớ để tránh bị quét bộ nhớ. Sau khi xử lí nhớ dọn dẹp.
• Hy vọng chưa có ai bị nổ não.

Bài viết gốc được đăng tải trên fanpage Khiem Tran – Programmer