# 記憶體分配:stack與heap

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

## 程式的記憶體分配
> 記憶體分配的示意圖。[圖源](https://visualgdb.com/documentation/embedded/stackheap/)

一個程式在分配到記憶體後，會被分配為四個部分：
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。
:::spoiler 有關推入stack的資訊
>在一個函式進入stack時，會推入函式的回傳地址、區域變數的資訊和函式的參數。這一系列在stack中的資訊，稱為stack-frame
:::

3. main()呼叫foo(a,b)，將foo()的stack-frame推入stack，將程式控制權暫時移轉給foo()。
4. foo()呼叫bar(x+y)，同樣將bar()的stack-frame推入stack，移轉控制權。
5. bar()結束，回傳資訊到回傳地址，並將bar()的stack-frame pop掉，控制權回到foo()。
6. foo()結束，回傳資料到回傳地址，並將foo()的stack-frame pop掉，控制權回到main()。
7. main()結束，將main()的stack-frame pop掉，控制權移轉回作業系統。
8. 釋放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/%E5%91%BC%E5%8F%AB%E5%A0%86%E7%96%8A
https://www.laioffer.com/zh/news/2017-06-22-what-is-call-stack/
https://en.wikipedia.org/wiki/Call_stack