堆分配函數(shù)與內(nèi)存結(jié)構(gòu)

malloc?通過brk()或mmap()?系統(tǒng)調(diào)用來獲取內(nèi)存，其區(qū)別點在于申請的內(nèi)存是否大于128KB.

拿來一張超經(jīng)典的圖來說事

brk()

brk()?通過（發(fā)生中斷）上移程序的brk指針來向內(nèi)核申請獲取內(nèi)存。

最初start_brk和brk指向相同的位置

其中關(guān)于Random brk offset：

• 關(guān)閉ASLR：start_brk和brk?初始指向數(shù)據(jù)段（.data?）/.bss?段的結(jié)尾end_data
• 開啟ASLR：start_brk和brk?初始指向數(shù)據(jù)段（.data?）/.bss?段的結(jié)尾end_data + Random brk offset

mmap()

malloc?使用mmap創(chuàng)建 私有匿名映射段。

私有匿名映射的主要目的是分配新內(nèi)存（用0填充），并且這個新內(nèi)存將由調(diào)用進程獨占使用。

位于圖中的Memory Mapping Segment段。

各個階段堆內(nèi)存分布

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>
void* threadFunc(void* arg) 
{
        // int locate = 1;
        printf("Before malloc in thread 1\\n");
        getchar();
        char* addr = (char*) malloc(1000);
        printf("After malloc and before free in thread 1\\n");
        getchar();
        free(addr);
        printf("After free in thread 1\\n");
        getchar();
}
int main() 
{
        pthread_t t1;
        void* s;
        int ret;
        char* addr;
        // printf("Welcome to per thread arena example::%d\\n",getpid());
        // printf("Before malloc in main thread\\n");
        // getchar();
        addr = (char*) malloc(1000);
        printf("After malloc and before free in main thread\\n");
        getchar();
        free(addr);
        printf("After free in main thread\\n");
        getchar();
        ret = pthread_create(&t1, NULL, threadFunc, NULL);
        if(ret)
        {
                printf("Thread creation error\\n");
                return -1;
        }
        ret = pthread_join(t1, &s);
        if(ret)
        {
                printf("Thread join error\\n");
                return -1;
        }
        return 0;
}

主線程調(diào)用malloc之前 __in main thread

此時由于沒有調(diào)用malloc?所以內(nèi)存中并不會存在heap段，并且在線程創(chuàng)建前也是沒有線程堆棧的。

但注意，此處會有一個小的 “意外”：

注意關(guān)注main?函數(shù)注釋掉的三行，將他們注釋掉的原因在于方便我們更清晰的關(guān)注malloc的分配策略：

首先說明，printf?的實現(xiàn)中，會調(diào)用 __vfprintf_internal這個內(nèi)部函數(shù)：該函數(shù)主要用于將可變參數(shù)列表格式化為字符串并將其寫入指定流。

在下列情況中它可能會申請堆空間來存儲這些字符串：

• 可變參數(shù)列表中包含的參數(shù)數(shù)量較多，導(dǎo)致格式化后的字符串需要較多的內(nèi)存來存儲。
• 可變參數(shù)列表中包含的參數(shù)類型不確定，因此無法預(yù)先確定格式化后的字符串長度。

在這些情況下，__vfprintf_internal函數(shù)可能會動態(tài)申請堆空間來存儲格式化后的字符串，以確保有足夠的內(nèi)存來容納這些字符串。

于是就會出現(xiàn)這樣的情況：

為了探明到底是誰調(diào)用了malloc于是在跟著往里走走，便發(fā)現(xiàn)：

果然在 __vfprintf_internal?中發(fā)生了malloc的調(diào)用（可真靠里啊….）

所以先將前面的printf注釋掉：

此時沒有調(diào)用malloc?前，并沒有產(chǎn)生heap段。

主線程調(diào)用malloc__in main thread

之后主線程通過malloc?申請了1000?字節(jié)的空間，這明顯是小于128KB?這個界限值的，所以此時會通過系統(tǒng)調(diào)用brk()上移堆區(qū)指針分配空間，一共分配了：

0x59000 - 0x7a000 = 0x21000?字節(jié)的空間，也就是135148 / 1024 = 132 KB?的空間，遠遠大于我們需要的1000字節(jié)的空間。

這132 KB?的空間的 “名號” 為：arena.

又因為他是在主線程中分配的，所以又被稱為main arena.

每個arena?中又有多個以鏈表組織的chunk?，剛剛malloc?分配的1000?字節(jié)空間就屬于main arena?下的一個chunk塊。

看其中的Uable size?表示的就是可用大小，也就是剛剛申請的1000?字節(jié)，至于為啥塊的總大小為1008字節(jié)會在后續(xù)說明。

為什么分配遠大于申請的空間？

由于若每次分配都要進行系統(tǒng)調(diào)用切換狀態(tài)是非常低效的，所以會維持一個類似內(nèi)存池的結(jié)構(gòu)，比方說上述例子，第一次在主線程中申請后堆空間后，若后續(xù)再繼續(xù)申請堆空間，則會先從這分配的132 KB中剩余的部分申請。

直到不夠的時候才會通過增加brk()?（視申請的空間大小而定）上移堆指針（增加program break location?）的方式（申請過大則使用mmap?內(nèi)存映射）來增加main arena的大小。

同理，當main arena?中有過多空閑內(nèi)存的時候，也會通過減小program break location?的方式來縮小main arena的大小。

主線程調(diào)用free__in main thread

可以看到，在主線程中free?掉剛剛申請的空間后，heap?段并沒有被釋放，有前面的描述這里很好理解，因為后續(xù)還有可能要申請堆空間所以堆空間不會直接還給系統(tǒng)，交給內(nèi)存分配器ptmalloc來管理。

釋放掉返還的空間并不會直接加入main arena?中的鏈表中，而是被加入到main arena bin?中，這是一種專門用于存儲同類型free chunk的雙鏈表。

【但注意，該雙向鏈表并不是一個全新的結(jié)構(gòu)，而是依次指向了原main arena?中被釋放的chunk塊】

這類用于記錄釋放后的空閑空間的雙向鏈表稱為bins.

只要有空間被free?后，加入了bins?，那么之后再通過malloc?申請空間時，就會先從bins?雙鏈表中尋找符合要求的chunk.

thread 1調(diào)用malloc__in (thread 1) thread

為了通過gdb?觀察thread 1?，直接在threadFunc打斷點運行即可

由于Linux?中子線程是通過mmap?映射內(nèi)存空間，所以其堆是通過mmap映射而來，且棧也位于內(nèi)存映射區(qū)

詳情見：

Where are the stacks for the other threads located in a process virtual address space?

此處若要向確認其?？臻g確實位于mmap?的內(nèi)存映射區(qū)可以用一個最簡單的方案，在線程函數(shù)中創(chuàng)建一個變量，觀察其地址int locate = 1;（原代碼中已注釋掉）

而由于該區(qū)域是緊鄰libc.so.6這個位于映射區(qū)的動態(tài)庫的，所以可以確認子線程的?？臻g確實位于內(nèi)存映射區(qū)中。

根據(jù)剛剛的內(nèi)存分布圖，內(nèi)存中 棧區(qū) 內(nèi)存映射去 堆區(qū) 的虛擬內(nèi)存地址是依次遞減的。

所以為該進程分配的堆區(qū)也確實位于剛剛棧區(qū)的上方（低地址），其大小于主線程中通過brk()?分配的大小相同，也是0x21000?也就是132 KB即thread1的arena.

thread 1調(diào)用free__in (thread 1) thread

流程同主線程

關(guān)于 Arena

結(jié)合前面的介紹，可知arena是一種用于組織堆分配塊的數(shù)據(jù)結(jié)構(gòu)。

該單詞"arena"?的原意是一個大型的比賽場館或活動場所，比如一個體育館或劇院。在這種情況下，arena可能是因為它用來組織和管理大量的內(nèi)存塊，類似于一個體育館用來組織和管理大量的比賽或活動

下述參考來源于網(wǎng)絡(luò)，并沒有進行驗證：

雖然看似上述程序中每個進程申請堆空間時都會有一個獨立的arena?，但arena的數(shù)量并不是可以隨著現(xiàn)成的增加隨意增加的，是有著最大值限制的。

若核心數(shù)對應(yīng)的最大arena?數(shù)不足以支撐新產(chǎn)生的線程，則ptmalloc?則會遍歷所有可用的arena?，并嘗試加鎖，若加鎖成功則將該arena?返回給申請的線程，此arena?會被當前子線程和原來使用的線程共享使用，若找不到（當前所有的arena?都在使用中）則當前子線程的malloc被阻塞等待。

堆內(nèi)存管理

在ptmalloc?中對于堆的管理，主要涉及到3種數(shù)據(jù)結(jié)構(gòu)，但若是直接列出每種數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)體，未免過于枯燥且難以理解，所以我們還是從剛剛的程序分析，分析結(jié)構(gòu)體中的每一個字段在內(nèi)存中的位置。

首先出場的是_heap_info這個結(jié)構(gòu)體

_heap_info

注意：該結(jié)構(gòu)體main arena?中并不存在，子線程thread arena?中是存在的，而且每當剩余空間不足重新申請一塊heap的時候就會產(chǎn)生一個該結(jié)構(gòu)體。

其作用一種用于在程序中存儲堆信息的數(shù)據(jù)結(jié)構(gòu)，具體存儲了什么信息先來看他的結(jié)構(gòu)體。

typedef struct _heap_info
{
  mstate ar_ptr;                /* arena for this heap. */
  struct _heap_info *prev;      /* Previous heap. */
  size_t size;                  /* Current size in bytes. */
  size_t mprotect_size;         /* Size in bytes that has been mprotected
                                   PROT_READ|PROT_WRITE.  */
   /* Make sure the following data is properly aligned, particularly
      that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
      MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

// pad字段用來確保該結(jié)構(gòu)在內(nèi)存中是正確對齊的，無需特別關(guān)注其計算含義。

單 heap segment 情況

單heap?段時只有一個_heap_info結(jié)構(gòu)，位于堆區(qū)的最開始。

拿出一張很經(jīng)典的圖

不過目前來說它過于復(fù)雜，所以先畫一個簡化版，再慢慢豐富它。

嗯~這樣就簡單多啦！

此處就以剛剛程序中，線程里通過內(nèi)存映射創(chuàng)建的一塊堆區(qū)為示例：

【 注意：此處堆區(qū)指的是通過brk?上移獲取的堆空間與通過mmap映射的內(nèi)存空間】

線程thread 1中的堆區(qū)范圍：

我們來看看這段堆區(qū)中_heap_info?結(jié)構(gòu)體中的數(shù)值是什么（由于從第4 * 8 = 32?字節(jié)開始都為填充部分，所以只看前32字節(jié)的數(shù)據(jù)）。

依次對應(yīng)下來：

• ar_ptr：0x00007ffff0000030?指向malloc_state?結(jié)構(gòu)體的指針接下來會詳細來講
• prev：0x0000000000000000?指向上一個堆的指針由于就一塊所以為?NULL
• size：0x0000000000021000?當前堆的字節(jié)大小和剛才算出的一樣?132 KB
• mprotect_size：0x0000000000021000?當前已被標記為可讀寫的堆的字節(jié)大小和剛才算出的一樣?132 KB從剛剛的截圖也可看出這段空間都是可讀可寫的

多 heap segment 情況

這很好理解，啟用剛剛為NULL的prev指針就可以啦！

但注意，上面說了，prev?是指向上一個堆的指針，所以是將第二個heap_info?結(jié)構(gòu)體的prev?成員指向了第一個heap_info?結(jié)構(gòu)體的起始位置（ar_ptr），這樣就構(gòu)成了一個單鏈表，方便后續(xù)管理。

【先提前說一下：malloc_state?這個結(jié)構(gòu)體只存在于第一塊heap中，后續(xù)映射來的 heap 中是不存在該結(jié)構(gòu)體的】

所以簡化后的示意圖為：

malloc_chunk

由于malloc_state?涉及到了整個arena?的管理，所以先介紹chunk?塊的結(jié)構(gòu)與其他的機制，最后再回歸到malloc_state中將會更好理解。

前面說過，為了便于管理和更加高效的利用內(nèi)存，第一次申請堆空間時，實際上是申請了一大塊遠大于所申請空間的arena?，而真正返回給用戶實際申請大小的是 arena?中的一個 chunk?，但剛剛也同樣觀測到，最終返回的大小比用戶實際申請的空間還要大8?字節(jié)，其中每個 chunk?都由一個結(jié)構(gòu)體 malloc_chunk?表示，也稱為 chunk header.

任何的堆管理器都是以chunk?為單位進行堆內(nèi)存管理的，所以對于每一個 chunk 塊中肯定要存在著控制信息，用于指示當前chunk的基本信息。

struct malloc_chunk 
{
  /* #define INTERNAL_SIZE_T size_t */
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. 這兩個指針只在free chunk中存在*/
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

堆內(nèi)存管理器要求每個chunk?塊的大小必須為8?的整數(shù)倍，而通過上述結(jié)構(gòu)體的size?字段正是用于描述當前chunk?塊大小的，既然必須是8?的整數(shù)倍，那么對于size?這個數(shù)二進制下，低3?位就無效了。（簡單來說：一旦這三位有哪些位被置1?了，都會導(dǎo)致最終的數(shù)一定不是8的倍數(shù)）

所以這空出來的3?位，就被當作了當前chunk?的標志位，每一位都表示這當前chunk塊一個狀態(tài)信息，具體的含義會在接下來說明。

chunk 塊的分類

chunk?總共分為4類：

• allocated chunk已被分配使用的 chunk 塊
• free chunk未被分配未使用的 chunk 塊
• top chunk
• last remainder chunk

chunk 的組織結(jié)構(gòu)

先簡單介紹一下 chunk 塊的組織結(jié)構(gòu)，詳細的介紹，將在會后面說明。

chunk 在堆內(nèi)存中是連續(xù)的，并不是直接由指針構(gòu)成的鏈表，而是通過 prev_size 和 size 構(gòu)成的隱式鏈表。

這樣做的好處在于：在進行分配操作的時候，堆內(nèi)存管理器可以通過遍歷整個堆內(nèi)存的 chunk，分析每個 chunk 的 size 字段，進而找到合適的 chunk，而且在合并不同 chunk 時，可以減少內(nèi)存碎片。

若不這么做，chunk 的合并只能向下合并，必須從頭遍歷整個堆，然后加以合并，意味著每次進行 chunk 釋放操作消耗的時間與堆的大小成線性關(guān)系。

allocated chunk

已被分配使用的chunk塊

圖 1-1

下圖可能與上圖存在差異，這并不是錯誤，后面會進行介紹：

圖 1-2

相關(guān)參數(shù)含義：

• prev_size ：該參數(shù)為 malloc_chunk 中第一個字段，也就是上圖中自上而下第一個的大方框中，根據(jù)當前 chunk 前一個 chunk 類型的不同，此處有兩種含義：

若前一個 chunk 為 free chunk 則 prev_size 表示前一個 free chunk 的大小

若前一個 chunk 為 allocated chunk 則 prev_size 沒有特殊含義，此處保存的是上一個 allocated chunk 塊剩余的用戶數(shù)據(jù)（主要是為了復(fù)用該控件）

• size ：該參數(shù)為 malloc_chunk 中第二個字段，也就是上圖中自上而下第二個大方框中，該字段共由 4 部分組成：

前三位

• N PREV_INUSE             前一個 chunk 是否為 allocated chunk
• M IS_MAPPED             當前 chunk 是否是通過 mmap 系統(tǒng)調(diào)用產(chǎn)生的
• P NON_MAIN_ARENA 當前 chunk 是否屬于 main arena (也就是主線程的 arena)

拿來之前的一張圖來，當前可以看 flags ：

• PREV_INUSE 置位，說明前一個 chunk 為已分配 chunk 這么解釋對于除第一個被分配的內(nèi)存塊的 size 字段以外內(nèi)存塊的 P 位是正確的，但由于該圖中的分配是主線程中的第一次分配，對于堆中第一個被分配的內(nèi)存塊的 size 字段的 P 位都會被置為 1【目的在于：防止非法訪問前面的內(nèi)存】
• IS_MMAPPED 沒置位，說明當前堆是通過 brk() 上移分配的
• NON_MAIN_ARENA 沒置位，說明當前為主線程 arena

其余位：當前 chunk 大小大小必須是 SIZE_SZ 的整數(shù)倍，如果申請的大小不是其整數(shù)倍，會被填充。

• 32位系統(tǒng)  SIZE_SZ = 4
• 64位系統(tǒng)  SIZE_SZ = 8

上圖中我們用 malloc 申請了 1000 字節(jié)的空間最終分配了 1008 字節(jié)的原因在于，由于該 chunk 的前一塊不是 free chunk 所以并不存在第一個 prev_size 或者說 prev_size 的位置保存的是前一塊中的數(shù)據(jù)，那么其實附加信息只有 size ，由于 64 位系統(tǒng)/程序 所以附加了 8 字節(jié)的空間，又因為 1008 是 2 * SIZE_SZ 的倍數(shù)，所以無需填充。

用戶數(shù)據(jù) for user_data用戶數(shù)據(jù)區(qū)域會被置 0 ，準備存入用戶的數(shù)據(jù)

free chunk

圖 1-3

有了前面的圖，此處就直接看原圖了。

prev_size ：為了防止碎片化，堆中不存在兩個相鄰的 free chunk （如果存在，則會被堆管理器合并為一個），因此對于 free chunk ，其 prev_size 區(qū)域中一定包含的是上一個 chunk 中一部分的有效數(shù)據(jù)或者為了地址對齊所做的填充對齊 padding

size ：與 allocated chunk 一致，表示當前 chunk 的大小，其標志位 N M P 也同上述含義相同

fd ：前向指針指向當前 free chunk 在同一個 bin（一種用于加快內(nèi)存分配和釋放效率的顯示鏈表）的下一個 free chunk

bk ：后向指針指向當前 free chunk 在同一個 bin 的上一個 free chunk

top chunk

該 chunk 位于一個 arena 的最頂部（即最高內(nèi)存地址處），不屬于任何 bin.

在當前的 heap 所有的 free chunk（無論哪種 bin 中）都無法滿足用戶請求的內(nèi)存大小的時候，將會將該 chunk 的空間 ，分配給用戶使用。

如果 top chunk 的大小比用戶請求的大小要大的話，就將該 top chunk 分作兩部分：用戶請求的 chunk 和 剩余的部分。（成為新的 top chunk）

否則，就需要擴展 heap 或分配新的 heap 了，在 main arena 中通過 sbrk 擴展 heap，而在 thread arena 中通過 mmap 分配新的 heap.

Last Remainder Chunk

該 chunk 涉及到另一個非常重要的顯示鏈表 bin ，在介紹完 bin 后再回來說他。

隱式鏈表

若不對 chunk 塊進行分類，則默認所有的 chunk 塊都是長成這個樣子的：

假設(shè)當前有三個 chunk 塊，分別將其命名為：

• FREE_A
• ALLOCATE_B
• FREE_C

通過其名字就可以知道當前三個 chunk 塊的結(jié)構(gòu)關(guān)系為：一個已經(jīng)分配的塊在兩個未使用的塊之間

那么就有了這樣的問題，若要釋放當前的 ALLOCATE_B 塊，該如何將 FREE_A ALLOCATE_B FREE_C 合成一個 free chunk (之前說過是不存在相鄰 free chunk 的)？

這里主要的問題在于如何合并 FREE_A 與 ALLOCATE_B FREE_C，因為 ALLOCATE_B 和 FREE_C 是很好合并的，ALLOCATE_B 只要向下獲取到 FREE_C 的 chunk size 參數(shù)，也就知道了 FREE_C 的大小，直接合并即可。

但 ALLOCATE_B 塊 和 FREE_A 之間該如何合并呢？

這就提出了帶邊界的標記的合并技術(shù)，而且要對 chunk 塊進行分類，因為 allocated chunk 是不需要合并的，自然也就不存在這個問題。

所謂的帶邊界標記中的邊界標記，也就是在原默認 chunk 塊的邊界處附加一個相鄰 chunk 塊的信息，于是自然而然，當前 chunk 塊為 free chunk 時，就會為當前 free chunk 塊 附加一個尾部，該尾部與其頭部 size 字段一致。

【allocated chunk 是不會附加該尾部的】

但此時還是擁有優(yōu)化空間的，當前 free chunk 沒有必要完全復(fù)制一份其首部 chunk size到尾部，因為若該尾部交給 free chunk 來添加，那無論該 free chunk 所處什么位置，都需要添加一個尾部，所以完全可以將這個任務(wù)交給 allocated chunk 來完成，只有當 allocated chunk 前為 free chunk 時，在 allocated chunk 的 chunk size 前記錄前一個 free chunk 的大小 size 即可，于是我們最常見的一種格式（圖 1-2）便出現(xiàn)了：

若前面不是 free chunk 則 prev_size 用于保存前一個 chunk 塊的剩余數(shù)據(jù)或 padding 填充即可

有了這樣的結(jié)構(gòu)，F(xiàn)REE_A 與 ALLOCATE_B 的合并就變得簡單了。

malloc_state

malloc_state 用于表示 arena 的信息，因此也被稱為 arena header ，每個線程只含有個 arena header.

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;
  
  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  */
  struct malloc_state *next_free;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

該結(jié)構(gòu)的介紹同樣需要先說 bin ，所以也在后續(xù)說明。