內(nèi)存违孝、棧刹前、堆的一點小總結

• 程序的內(nèi)存布局
  【前言】在32位系統(tǒng)中，大家可能認為我們可以用一個32位的指針訪問任意內(nèi)存地址等浊。如下：
  int *p = (int *)0x12345678;
++*p;
  ??但事實上用戶可以直接讀取的內(nèi)存大小是達不到4GB的。大多數(shù)操作系統(tǒng)都會將其中的一部分分配給內(nèi)核使用摹蘑，應用程序是無法直接訪問這一段內(nèi)存的筹燕，這部分被稱為內(nèi)核空間。Linux默認將高地址的1GB空間分配給內(nèi)核；win默認下將高地址的2GB分配給內(nèi)核撒踪，但是也可以人為配置成1GB过咬。（前面已介紹）
  ??但是處理上述的內(nèi)核空間之外的用戶空間中也有一些特殊的空間有特殊的用處，而應用程序能用的內(nèi)存空間是如下的“默認區(qū)域”：

  • 棧
    ??用于維護函數(shù)調(diào)用的上下文制妄，離開了棧掸绞，函數(shù)的調(diào)用就辦法實現(xiàn)了。棧通常在用戶更高的地址空間處分配耕捞，通常有數(shù)兆字節(jié)的大小衔掸。
  • 堆
    ??堆用來容納應用程序動態(tài)分配的內(nèi)存區(qū)域，當程序使用malloc或new的時候就是得到來自堆中的內(nèi)存俺抽。堆統(tǒng)稱在棧的下方（低地址方向敞映，但是不是緊鄰的）。堆一般比棧要更大一點磷斧，一般會達到幾十甚至是數(shù)百兆字節(jié)振愿。
  • 可執(zhí)行文件映像
    ??顧名思義，這里存儲著可執(zhí)行文件在內(nèi)存里的映像弛饭。裝載器在裝載的時候會將可執(zhí)行文件讀取或者映射到這里冕末。
  • 保留區(qū)
    ??是對內(nèi)存中受到保護而禁止訪問的內(nèi)存區(qū)域的總稱。這個區(qū)域大家應該都比較熟悉侣颂，比如档桃，大多數(shù)操作系統(tǒng)中，極小的地址區(qū)域都是不允許訪問的横蜒，如NULL胳蛮。
    ??相關的內(nèi)存布局如下：
    
    
    
    ??上圖中還有一個區(qū)域，“動態(tài)鏈接庫映射區(qū)”丛晌，這個區(qū)域用于映射裝載的動態(tài)鏈接庫仅炊。比如，如果可執(zhí)行文件依賴于其他的共享庫澎蛛，那么系統(tǒng)就會為他從0x40000000開始的地址分配相應的空間抚垄，并將該共享庫載入到該空間（動態(tài)鏈接共享對象的內(nèi)存地址分配）。
    ??【注意】棧向低地址增長谋逻；堆向高地址增長呆馁。當棧或者堆的現(xiàn)有大小不夠用的時候毁兆，它將按照圖中的增長方向擴大自身的尺寸浙滤，直到預留的空間（unused）被用完。
    ??【補充】在Linux或者是win內(nèi)存中气堕，有些地址是始終不能讀寫的纺腊，例如0地址畔咧，當指針指向這些地址的時候，就會出現(xiàn)“段錯誤（segment fault）”揖膜。造成這種情況的兩種最普遍的原因：
    1.程序員將指針初始化為NULL誓沸，但是沒有賦予合理的初值就開始使用。
    2.程序員沒有初始化棧上的指針壹粟，指針的值一般是隨機數(shù)拜隧，之后就開始使用該指針。

• 棧

  • 在經(jīng)典的操作系統(tǒng)中趁仙，椇樘恚總是向下（低地址）增長的。
  • 堆棧幀或活動記錄
    ??棧保存一個函數(shù)調(diào)用所需要的維護信息幸撕，常備稱為堆棧幀或者是活動記錄薇组，堆棧幀一般包括：
    （1）函數(shù)的返回地址和參數(shù)；
    （2）臨時變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器生成的其他局部變量坐儿；
    （3）保存的上下文：包括在函數(shù)調(diào)用前后保持不變的寄存器律胀。
  • 棧中有兩個重要的寄存器：esp和ebp
    （1）esp
    ??該寄存器標明棧頂，在棧上壓入數(shù)據(jù)會導致esp減小貌矿，反之esp增大炭菌。再者，減小esp的值等于在棧上開辟空間逛漫，而增大esp的值等效于在棧上回收空間黑低。
    ??esp不僅僅指向棧的頂部，同時也就意味著指向當前整個函數(shù)活動記錄的頂部（見下圖）酌毡。
    （2）ebp
    ??ebp寄存器指向函數(shù)活動記錄的一個固定位置克握。ebp寄存器又被稱為幀指針。如下：
    
    
    
    ??ebp具體的固定位置如上圖所示枷踏。如圖菩暗，（注意棧向低地址增長）ebp之前是該函數(shù)的返回地址，再之前是壓入棧中的參數(shù)旭蠕。而ebp指向的數(shù)據(jù)是調(diào)用該函數(shù)之前的ebp的值停团，保存舊的ebp的值的原因是，函數(shù)返回時掏熬，可以通過讀取該值恢復到調(diào)用之前的ebp的值（回到之前指向的位置）佑稠。

• 調(diào)用慣例

  • 概念
    ??函數(shù)的調(diào)用方和被調(diào)用方對于函數(shù)如何調(diào)用需要有一個明確的約定（比如參數(shù)入棧的順序等）。這樣的約定就被稱為調(diào)用慣例旗芬。
  • 調(diào)用慣例一般包括：
    （1）函數(shù)參數(shù)的傳遞順序和方式舌胶。可以有很多方式疮丛，最常見的就是通過棧傳遞幔嫂，參數(shù)入棧的順序要事先由調(diào)用慣例確定漱办；有些調(diào)用慣例為了提升性能還會選擇用寄存器進行參數(shù)傳遞。
    （2）棧的維護方式婉烟。參數(shù)入棧后，函數(shù)體會被調(diào)用暇屋，參數(shù)使用的時候會被彈出的似袁，可以是函數(shù)調(diào)用方進行參數(shù)的彈出或者是由函數(shù)本身進行參數(shù)的彈出。
    （3）名字修飾的策略。C語言實際上存在多種調(diào)用慣例，一般默認的（沒有顯示指定的情況下）是cdecl（不同的編輯器寫法有別）：
    int _cdecl foo(int n, float m);

  • foo函數(shù)布局
    具體如下圖所示：

    
    
    
    
    

    ??當foo函數(shù)返回的時候惦界，程序會首先使用pop恢復保存在棧中的寄存器残拐，然后從棧里取出返回地址，并返回至調(diào)用方吨掌，調(diào)用方再調(diào)整esp將堆棧恢復。下面給出一個具體的多級調(diào)用棧的布局：

    
    
    
    
    
    

• 函數(shù)返回值傳遞

  • 如果返回值的可以用4個字節(jié)表達啼县，我們經(jīng)常講返回值保存在eax寄存器里面。返回后沸久，函數(shù)的調(diào)用方將讀取eax寄存器中的值即可季眷。
  • 對于返回4~8字節(jié)對象的情況，幾乎所有的調(diào)用慣例都采用eax和edx聯(lián)合返回的方式進行的卷胯。
  • 超過8字節(jié)的返回值（大致思路）：
    先看一段代碼：

#include<stdio.h>
typedef struct big_thing
{
　　char buf[128];
}big_thing;
big_thing return_test()
{
　　big_thing b;
　　b.buf[0] = 0;
　　return b;
}
int main()
{
　　big_thing n = return_test();
　　return 0;
}

- 大致解讀
    - 首先main函數(shù)在棧上額外開辟一片空間子刮，并將這塊空間的一部分作為傳遞返回值的臨時對象，這里稱為temp窑睁；
    - 將temp對象的地址作為隱藏參數(shù)傳遞給return_test函數(shù)挺峡；
    - return_test函數(shù)將數(shù)據(jù)拷貝給temp對象，并將temp的地址用eax傳出担钮；
    - return_test函數(shù)返回后橱赠，main函數(shù)將eax指向的temp對象的內(nèi)容拷貝給了n。
    
返回值傳遞流程如下：
![](http://7xl3j2.com1.z0.glb.clouddn.com/cxy-19.jpg)
**【注意】結果返回值對象會被拷貝兩次裳朋，所以不到萬不得已不要返回大尺寸的對象病线。**

• 堆
  • 簡介
    ??堆是一塊巨大的內(nèi)存空間，常常占用整個虛擬空間的絕大部分鲤嫡。在這片空間里送挑，程序可以請求一塊連續(xù)內(nèi)存，并自由使用暖眼，這塊內(nèi)存在程序主動放棄之前都會一直保存惕耕。
  • malloc的實現(xiàn)
    ??不能采用系統(tǒng)調(diào)用的方式，開銷較大诫肠；較好的做法是程序向操作系統(tǒng)申請一會適合大小的堆空間司澎，然后由程序自己管理這塊空間欺缘，具體來講，管理著堆空間分配的往往是程序的運行庫挤安。
    ??運行庫相當于向操作系統(tǒng)”批發(fā)“了一塊較大的堆空間谚殊，之后”零售“給程序使用，如全部售完或者程序有大量的內(nèi)存需求蛤铜，再根據(jù)實際情況向操作系統(tǒng)“進貨”嫩絮。
  • Linux進程堆管理
    ??提供兩種堆分配方式，即兩個系統(tǒng)調(diào)用：brk()系統(tǒng)調(diào)用围肥；mmap()系統(tǒng)調(diào)用剿干。
    • brk()
      該函數(shù)的C語言聲明如下：
      int brk(void *end_data_segment)
      ??該函數(shù)申請堆的方式是：設置進程的數(shù)據(jù)段的結束地址，即可以擴大或者是縮小數(shù)據(jù)段（Linux下數(shù)據(jù)段和BSS段合稱數(shù)據(jù)段）穆刻。如果我們將數(shù)據(jù)段的結束地址向高地質移動（數(shù)據(jù)段變兄枚），那么擴大的那部分空間常常用來作為堆空間氢伟。
    • mmap()
      ??該函數(shù)的作用是向操作系統(tǒng)申請一段虛擬空間榜轿，這塊虛擬地址空間可以映射到某個文件，當它不進行映射的時候朵锣，我么又稱這塊空間為匿名空間差导，匿名空間就可以用來作為堆空間。
      ??glibc的malloc函數(shù)是這樣處理用戶的空間請求的：
      （1）對于小于128kb的請求猪勇，它會在現(xiàn)有的堆空間里面设褐，按照堆空間分配算法為其分配一塊地址并返回；
      （2）對于大于128kb的請求泣刹，它會使用mmap()函數(shù)為它分配一塊匿名空間助析。使用mmap()函數(shù)實現(xiàn)malloc的代碼如下：

void *malloc(size_t  nbytes)
{
　   void *ret = mmap(0,nbytes,PROT_READ | PROT_WRTIE, MAP_PRIVATE | MAP_ANONYMOUS,0,0);
　   if(ret == MAP_FAILED)
　　      return 0;
　   return ret;
}

    【需要注意的是】mmap()函數(shù)和VirtualAloc()類似，他們都是虛擬空間的申請函數(shù)椅您，**它們申請的空間的其實地址和大小必須是系統(tǒng)頁的大小的整數(shù)倍**外冀。

• 堆分配算法
  • 空閑鏈表法
    • 簡介
      ??該方法將堆中的各個空閑塊按照鏈表的方式連接起來，當用戶請求一塊空間的時候掀泳，可以遍歷整個鏈表雪隧，直到找到合適大小的塊并將它拆分，當用戶釋放空間的時候將他合并到空閑鏈表中员舵。

    • 結構
      ??在堆里的每一個空閑空間的開頭（或結尾）有一個頭（header）脑沿，頭結構里面有兩個指針prev和next，如下圖：

      
      
      
    • 操作過程
      ??首先在空閑鏈表查找足夠容納請求大小的一個空閑塊马僻，然后將這個塊分為兩部分庄拇，一部分是程序請求的空間，另一部分是剩余的空閑空間。
      【注意】當采用空閑鏈表的方式時需要釋放空閑空間的時候措近，有一個簡單的解決方法：當用戶請求k個字節(jié)的時候溶弟，我們實際分配k+4個字節(jié)，這四個字節(jié)用來存儲該分配的大小瞭郑。
  • 位圖
    • 核心思想
      ??將整個堆劃分為大量的大小相等的“塊”辜御。當用戶請求的時候，總是分配整數(shù)個塊的空間給用戶屈张。分配的塊中我抠，第一個塊我們稱為已分配區(qū)域的頭（Head），其余的稱為已分配區(qū)域的主體（Body）袜茧。我們使用整數(shù)數(shù)組來記錄塊的使用情況，由于每個塊只有頭/主體/空閑三種狀態(tài)瓣窄，因此可以使用兩個bit位來表示一個塊笛厦。
    • 舉例
      ??假設堆的大小為1MB，那么我們讓一個塊大小為128字節(jié)俺夕，則總的塊數(shù)：8k/(32/2)=512個int來存儲裳凸，。這有512個int的數(shù)組就是一個位圖劝贸，其中每兩個bit位代表一個塊姨谷。
    • 優(yōu)點
      （1）速度快。由于整個堆的空閑信息都存儲在一個數(shù)組內(nèi)映九，因此訪問該數(shù)據(jù)的時候cache容易命中梦湘。
      （2）穩(wěn)定性好。為避免用戶越界讀寫破壞數(shù)據(jù)件甥，我們只需簡單地備份一下位圖即可捌议。而且即使部分數(shù)據(jù)被破壞，也不會導致整個堆無法工作引有。
      （3）塊不需要額外信息瓣颅，易于管理
    • 缺點
      （1）分配內(nèi)存的時候容易產(chǎn)生碎片。例如譬正，分配300字節(jié)時宫补，實際上分配了3個塊即384個字節(jié)，這樣就浪費了84個字節(jié)（128*3曾我，按照整數(shù)個塊進行分配）粉怕。
      （2）如果堆很大但是設定的塊很小（這樣可以減少碎片的數(shù)量）抒巢，但同時也會導致位圖的規(guī)模很大斋荞，可能會失去cache命中率高的優(yōu)勢，同時也會浪費一定的空間虐秦。針對這種情況平酿，我們可以使用多級位圖（不在介紹）凤优。
  • 對象池
    • 使用情況
      ??被分配的大小是較為固定的幾個值。
    • 大致思路
      ??如果每次分配的空間大小都一樣蜈彼，那么就可以按照這個每次請求分配的大小作為一個單位筑辨，把整個堆空間劃分為大量的小塊，每次請求的時候只需要找到一個小塊就可以了幸逆。
    • 管理
      ??對象池的管理方法可以是空閑鏈表或者是位圖棍辕。
  • 實際應用
    ??實際的應用中，堆的分配算法其實是采取多種算法的復合还绘。