367
Glibc 的malloc源代碼分析
Glibc 的 malloc 源代碼分析
有人寫了一個測試程序
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <malloc.h>
main()
{
int alloc_time = 20000;
char* a[alloc_time];
char* b[alloc_time];
for(int j=0; j<5; j++)
{
for(int i=0; i<alloc_time; i++)
{
a[i] = (char*)malloc(52722);
memset(a[i], 1, 52722);
b[i] = (char*)malloc(1);
memset(b[i], 1, 1);
}
for(int i=0; i<alloc_time; i++)
{
free(a[i]);
free(b[i]);
}
}
while(1)
{
sleep(10);
}
}
發現 該程序在測試機上運行會占用 1G 內存，不釋放，為了解決這個問題，特別去研究了一下glibc 中malloc 的源代碼。
一．對於小於 128k 的塊在 heap 中分配。
1. 堆是通過 brk 的方式來增長或壓縮的，如果在現有的堆中不能找到合適的 chunk ，會通過增長堆的方式來滿足分配，如果堆頂的空閑塊超過一定的閥值會收縮堆，所以隻要堆頂的空間沒釋放，堆是一直不會收縮的。
2. 堆中的分配信息是通過兩個方式來記錄。
第一．是通過 chunk 的頭， chunk 中的頭一個字是記錄前一個 chunk 的大小，第二個字是記錄當前 chunk 的大小和一些標誌位，從第三個字開始是要使用的內存。所以通過內存地址可以找到 chunk ，通過 chunk 也可以找到內存地址。還可以找到相鄰的下一個 chunk ，和相鄰的前一個 chunk 。一個堆完全是由 n 個 chunk 組成 。
第二．是由 3 種隊列記錄 ，隻用空閑 chunk 才會出現在隊列中，使用的 chunk 不會出現在隊列中。如果內存塊是空閑的它會掛到其中一個隊列中，它是通過內存複用的方式，使用空閑 chunk 的第 3 個字和第 4 個字當作它的前鏈和後鏈（變長塊是第 5 個字和第 6 個字），省的再分配空間給它。
第一種隊列是 bins ， bins 有 128 個隊列，前 64 個隊列是定長的，每隔 8 個字節大小的塊分配在一個隊列，後麵的 64 個隊列是不定長的，就是在一個範圍長度的都分配在一個隊列中。所有長度小於 512 字節（大約）的都分配在定長的隊列中 。後麵的 64 個隊列是變長的隊列，每個隊列中的 chunk 都是從小到大排列的。
第二種隊列是 unsort 隊列（隻有一個隊列），（是一個緩衝）所有 free 下來的如果要進入 bins 隊列中都要經過 unsort 隊列。
第三種隊列是 fastbins ，大約有 10 個定長隊列，（是一個高速緩衝）所有 free 下來的並且長度是小於 80 的 chunk 就會進入這種隊列中。進入此隊列的 chunk 在 free 的時候並不修改使用位，目的是為了避免被相鄰的塊合並掉。
3.malloc 的步驟
l 先在 fastbins 中找，如果能找到，從隊列中取下後（不需要再置使用位為 1 了）立刻返回。
l 判斷需求的塊是否在小箱子 （ bins 的前 64 個 bin ）範圍，如果在小箱子的範圍，並且剛好有需求的塊，則直接返回內存地址；如果範圍在大箱子（ bins 的後 64 個 bin ）裏，則觸發 consolidate 。（因為在大箱子找一般都要切割，所以要優先合並，避免過多碎片）
l 然後在 unsort 中取出一個 chunk ，如果能找到剛好和想要的 chunk 相同大小的 chunk ，立刻返回，如果不是想要 chunk 大小的 chunk ，就把他插入到 bins 對應的隊列中去。轉 3 ，直到清空，或者一次循環了 10000 次。
l 然後才在 bins 中找，找到一個最小的能符合需求的 chunk 從隊列中取下，如果剩下的大小還能建一個 chunk ，就把 chunk 分成兩個部分，把剩下的 chunk 插入到 unsort 隊列中去，把 chunk 的內存地址返回。
l 在 topchunk （是堆頂的一個 chunk ，不會放到任何一個隊列裏的）找，如果能切出符合要求的，把剩下的一部分當作 topchunk ，然後返回內存地址。
l 如果 fastbins 不為空，觸發 consolidate 即把所有的 fanbins 清空 （是把 fanbins 的使用位置 0 ，把相鄰的塊合並起來，然後掛到 unsort 隊列中去），然後繼續第 3 步。
l 還找不到話就調用 sysalloc ，其實就是增長堆了。然後返回內存地址。
4.free 的步驟
l 如果和 topchunk 相鄰，直接和 topchunk 合並，不會放到其他的空閑隊列中去。
l 如果釋放的大小小於 80 字節，就把它掛到 fastbins 中去，使用位仍然為 1 ，當然更不會去合並相鄰塊。
l 如果釋放塊大小介於 80-128k ，把 chunk 的使用位置成 0 ，然後試圖合並相鄰塊，掛到 unsort 隊列中去，如果合並後的大小大於 64k ，也會觸發 consolidate ，（可能是周圍比較多小塊了吧），然後才試圖去收縮堆。（收縮堆的條件是當前 free 的塊大小加上前後能合並 chunk 的大小大於 64k ，並且要堆頂的大小要達到閥值，才有可能收縮堆）
l 對於大於 128k 的塊，直接 munmap
二．大於 128k 的塊通過 mmap 的方式來分配。
根據以上的分析，我們可以得出為什麼會還占用 1G 的內存。
測試程序有兩重循環，內層循環先分配 1G ，然後全部釋放，外層執行這個步驟 5 次，但為什麼最後一次釋放會不成功呢。
主要是因為按照這個程序分配後，內存變成由小塊和大塊交替出現，釋放小塊的時候，直接把小塊放到 fastbins 中去，而且他的使用位還是 1 ，釋放大塊的時候，它試圖合並相鄰的塊，但是和它相鄰的塊的使用位還是 1 ，所以它不能把相鄰的塊合並去來，而且釋放的塊的大小小於 64k ，也不會觸發 consolidate ，即不會把 fastbins 清空 ，所以當所有的塊都被釋放完後，所有的小塊都在 fastbins 裏麵，使用位都為 1 ，大塊都掛在 unsort 隊列裏麵。全部都無法合並。所以使用的堆更加無法壓縮。
如果在外循環後麵再分配 2000 字節然後釋放的話，所有內存將全部清空。這是因為在申請 2000 字節的時候，由 malloc 的第二步，程序會先調用 consolidate ，即把所有的 fastbins 清空，同時把相鄰的塊合並起來，等到所有的 fastbins 清空的時候，所有的塊也被合並去來了，然後調用 free2000 字節的時候，這塊被將被合並起來 ，成為 topchunk ，並且大小遠大於 64k ，所有堆將會收縮，內存歸還給係統。
轉帖自：https://blog.chinaunix.net/u3/94916/showart_1908306.html
最後更新：2017-04-02 03:42:38