Try   HackMD

記憶體分配:stack與heap

記憶體的功用,是提供處理器存取資料,在需要時再進行存取。因此,記憶體對於每個程式而言,都是珍貴的資源。而負責分配記憶體的工作,是由作業系統負責。本文將介紹有關記憶體在一個程式中的分配。

程式的記憶體分配

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

記憶體分配的示意圖。圖源

一個程式在分配到記憶體後,會被分配為四個部分:
Code, Static/Global, Stack和Heap。

  • Code的部分會儲存程式所需要的指令。
  • Static/Global的部分儲存全域變數,用於程式中跨越多個函數皆需要的變數。
  • Stack的部分用來儲存函式的呼叫和區域變數的資訊,在函式結束會被釋放。
  • Heap是可以用來動態分配的記憶體。

Stack 介紹

我們以以下程式為例:

#include<stdio.h> using namespace std; int total = 0; int bar(int z){ total++; return z*z; } int foo(int x,int y){ total++; int k = bar(x+y); return k; } int main(){ total++; int a = 1; int b = 2; int c = foo(a,b); printf("%d \n",c); }

當電腦呼叫main()後,main()呼叫了foo(),foo()又呼叫了bar()。如果以記憶體的觀點,實際做到的事情如下:

  1. total變數放入global。
  2. main()被呼叫,將main()相關的資訊推入Stack。
有關推入stack的資訊

在一個函式進入stack時,會推入函式的回傳地址、區域變數的資訊和函式的參數。這一系列在stack中的資訊,稱為stack-frame

  1. main()呼叫foo(a,b),將foo()的stack-frame推入stack,將程式控制權暫時移轉給foo()。
  2. foo()呼叫bar(x+y),同樣將bar()的stack-frame推入stack,移轉控制權。
  3. bar()結束,回傳資訊到回傳地址,並將bar()的stack-frame pop掉,控制權回到foo()。
  4. foo()結束,回傳資料到回傳地址,並將foo()的stack-frame pop掉,控制權回到main()。
  5. main()結束,將main()的stack-frame pop掉,控制權移轉回作業系統。
  6. 釋放global的資訊

由於stack不會隨著程式的增長而增加,所以如果函式呼叫的深度過大,stack的容量會不夠,此時會導致程式崩潰,此現象稱為stack-overflow,通常在不小心出現無限遞迴時發生。

因為stack的固定大小,如果我們要宣告一個大陣列,宣告在區域變數會有些問題,其中一個解法是將陣列宣告在global。然而,由於global的資料在程式一開始就佔據,我們無法隨著程式的進行而動態分配記憶體大小,讓空間被浪費。因此,heap就是被用來處理分配動態記憶體的問題。

heap介紹

heap又被稱為動態記憶體(dynamic memory)。有別於stack,heap的大小在程式的運行中不固定,因此我們可以自由地請求或釋放heap的記憶體。(當然,這同時也是件危險的事,畢竟你要注意記憶體是否被用完)

在C中使用heap,會需要以下函式:

  • malloc()
  • calloc()
  • realloc()
  • free()

以下面的程式碼為例:

#include<stdio.h> #include<stdlib.h> using namespace std; int main(){ int a = 1; int* p; p = (int*) malloc(sizeof(int)); *p = 10; //free(p); p = (int*) malloc(sizeof(int)); *p = 20; }

在main()的stack-frame中,會包含區域變數a和指標p。在第一次的malloc被呼叫後,在heap中會被請求4bytes(int的大小)的空間(假設開頭的位置在0x0400),並且p會指向0x0400。在第八行即是設定該位置的值。

在第二次呼叫malloc()時,又會再次請求4bytes的記憶體(假設位置在0x0100),此時p會改為指向0x0100的位置。

然而,即便原本0x0001的位置沒有指標指向它,他仍會佔據heap的空間,因此,要有效地管理記憶體,必須執行free()來釋放無用的記憶體。

讓我們塞爆heap吧!

在稍早的示意圖中,可以看到stack和heap是相連的,只是一個向下生長,一個向上生長。如果我們能利用一些黑魔法讓資料超出heap,似乎有可能可以改寫到stack的內容,而這種攻擊方式稱為buffer-overflow。

參考資料

https://www.youtube.com/watch?v=_8-ht2AKyH4&ab_channel=freeCodeCamp.org
https://www.youtube.com/watch?v=Q2sFmqvpBe0&ab_channel=ComputerScience
https://zh.wikipedia.org/wiki/呼叫堆疊
https://www.laioffer.com/zh/news/2017-06-22-what-is-call-stack/
https://en.wikipedia.org/wiki/Call_stack