參考：《深入理解計算機系統》 本文需要比較多的前言基礎，在前面的文章中都有體現

malloc實現原理 這位大佬寫得也很不錯，部分內容參考這裡。

要看這個malloc,得先了解靜態內存分配和動態內存分配。下面是這兩者的區別：（靜態內存分配在書中一直沒找到。。）

內存的靜態分配和動態分配的區別主要是兩個：

一是時間不同。靜態分配發生在程序編譯和連接的時候。動態分配則發生在程序調入和執行的時候。

二是空間不同。堆都是動態分配的，沒有靜態分配的堆。棧有2種分配方式：靜態分配和動態分配。靜態分配是編譯器完成的，比如局部變數的分配。動態分配由函數malloc進行分配。不過棧的動態分配和堆不同，他的動態分配是由編譯器進行釋放，無需我們手工實現。

對於一個進程的內存空間而言，可以在邏輯上分成3個部份：代碼區，靜態數據區和動態數據區。動態數據區一般就是「堆棧」。「棧(stack)」和「堆(heap)」是兩種不同的動態數據區，棧是一種線性結構，堆是一種鏈式結構。進程的每個線程都有私有的「棧」，所以每個線程雖然代碼一樣，但本地變數的數據都是互不幹擾。一個堆棧可以通過「基地址」和「棧頂」地址來描述。全局變數和靜態變數分配在靜態數據區，本地變數分配在動態數據區，即堆棧中。程序通過堆棧的基地址和偏移量來訪問本地變數。

---------------------

作者：liuchao1986105

來源：CSDN

原文：blog.csdn.net/liuchao19

版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

總結一下就是，動態內存分配可以在程序運行的時候動態地獲取和使用內存，然後是動態內存分配的區間不同。

動態內存分配器更方便，也有更好的移植性。它維護者一個進程的虛擬內存區域，稱為堆（heap）。它在未初始化數據的上邊，然後向上生長（即向更高的地址），對於每個進程來說，內核維護著一個brk(break)變數，它指向堆的頂部，如下圖：

分配器將堆視為一組不同大小的塊（block）的集合來維護。每個塊就是一個連續的虛擬內存片（chunk）,要麼是已分配的，要麼是空閑的。已分配的塊顯式地保留為供程序使用。空閑塊可用來分配。空閑塊保持空閑，直到它顯式地被應用所分配。一個已分配的塊保持已分配狀態，直到它被釋放，這種釋放要麼是應用程序顯式執行的，要麼是內存分配器自身隱式執行。（忽然很慶幸自己學習了一波多級頁表，所以對裡面這個模型比較容易理解 可參考 何柄融：linux 多級頁表 cpu取虛擬地址 TLB 特別是裡面的 chunk ）

然後動態的分配器有兩種基本風格：顯式和隱式。兩種風格都要求應用顯式地分配塊。它們的不同之處在於由哪個實體來負責釋放已經分配的塊。

顯式分配器：要求應用顯式地釋放任何已經分配的塊。例如c標準庫中的malloc. c程序通過調用malloc函數來分配一個塊，並通過調用free函數來釋放一個塊。c++中的new和delete操作符和c中搞得malloc和free相當。（就是自己手動釋放內存）

隱式分配器：要求分配器檢測一個已分配塊何時不再被程序所使用，那麼就釋放這個塊。隱式分配器也叫做垃圾收集器，而自動釋放未使用的已分配的塊的過程叫做垃圾收集。例如java，ML，Lisp之類的高級語言就依賴垃圾收集來釋放已分配的塊。（就是不用程序猿自己手動釋放內存）

例如：圖形處理密集的應用程序就經常使用標準分配器來要求獲得一大塊的虛擬內存，然後使用與應用相關的分配器來管理內存，在該快中創建和銷毀圖形的節點。（總不能自己手動釋放這些內存吧，那多難受啊）

然後我們先討論顯式內存分配器：

c標準庫提供了一個稱為malloc程序包的顯式分配器。程序通過調用malloc函數來從堆中分配塊。

void *malloc(size_t size) ;
返回：若成功則為已分配塊的指針，若出錯則為null.

malloc函數返回一個指針，指向大小至少為size位元組的內存塊，這個塊會為可能包含在這個塊內的任何數據對象類型做對齊。（這個會根據系統位數返回相應規格的地址）

如果malloc遇到問題（例如，程序要求的內存塊比可用的虛擬內存還要大），那麼它就返回null.並設置errno。malloc不初始化它返回的內存。

下面很大一部分參考自文首鏈接：malloc實現原理

然後來深入瞭解malloc:

先了解：brk()和sbrk()函數

int brk( const void *addr )
void* sbrk ( intptr_t incr );

這兩個函數的作用主要是擴展heap的上界brk。第一個函數的參數為設置的新的brk上界地址，如果成功返回0，失敗返回-1。第二個函數的參數為需要申請的內存的大小，然後返回heap新的上界brk地址。如果sbrk的參數為0，則返回的為原來的brk地址。

然後來瞭解：mmap

mmap函數第一種用法是映射磁碟文件到內存中（前面講進程通信的時候講過）；而malloc使用的mmap函數的第二種用法，即匿名映射，匿名映射不映射磁碟文件，而是向映射區申請一塊內存。

void *mmap(void *addr, size\_t length, int prot, int flags, int fd, off\_t offset);
int munmap(void *addr, size_t length);

這裡不重複囉嗦了，對mmap不熟悉的同學可以參考何柄融：linux 進程通信方式 pipe無名管道 fifo有名管道 共享內存映射 socket 消息隊列 或者文章最前面的連接（感覺我寫得比較好，哈哈）

這裡要注意的是fd參數，fd為映射的文件描述符，如果是匿名映射，可以設為-1；

當申請小內存的時，malloc使用sbrk分配內存；當申請大內存時，使用mmap函數申請內存；但是這只是分配了虛擬內存，還沒有映射到物理內存，當訪問申請的內存時，才會因為缺頁異常，內核分配物理內存。

然後接著深入：

由於brk/sbrk/mmap屬於系統調用，如果每次申請內存，都調用這三個函數中的一個，那麼每次都要產生系統調用開銷（即cpu從用戶態切換到內核態的上下文切換，這裡要保存用戶態數據，等會還要切換回用戶態），這是非常影響性能的；其次，這樣申請的內存容易產生碎片，因為堆是從低地址到高地址，如果低地址的內存沒有被釋放，高地址的內存就不能被回收。

鑒於此，malloc採用的是內存池的實現方式，malloc內存池實現方式更類似於STL分配器和memcached的內存池，先申請一大塊內存，然後將內存分成不同大小的內存塊，然後用戶申請內存時，直接從內存池中選擇一塊相近的內存塊即可。

由於文首的鏈接裏沒圖，所以從 glibc內存管理那些事兒 這個鏈接裏盜來幾張圖，而且這個鏈接講的內存池也很不錯。

先看內存池的整體結構：（感覺下面的都很核心！）

（第一眼看上去有沒有很像哈希表？哈哈。）

malloc將內存分成了大小不同的chunk，然後通過bins來組織起來。malloc將相似大小的chunk（圖中可以看出同一鏈表上的chunk大小差不多）用雙向鏈錶鏈接起來，這樣一個鏈表被稱為一個bin。malloc一共維護了128個bin，並使用一個數組來存儲這些bin。數組中第一個為unsorted bin,數組從2開始編號，前64個bin為small bins，同一個small bin中的chunk具有相同的大小，兩個相鄰的small bin中的chunk大小相差8bytes。small bins後面的bin被稱作large bins。large bins中的每一個bin分別包含了一個給定範圍內的chunk，其中的chunk按大小序排列。large bin的每個bin相差64位元組。（這裡我本來想計算一下加深理解的，8x64=512b, 64x64=4096b 然後加起來發現和圖片裏的不太匹配，所以不知道自己哪裡理解錯了？可是前面的88又對啊，怎麼後面就12k那麼大呢？）

malloc除了有unsorted bin，small bin,large bin三個bin之外，還有一個fast bin。一般的情況是,程序在運行時會經常需要申請和釋放一些較小的內存空間。當分配器合併了相鄰的幾個小的 chunk 之後,也許馬上就會有另一個小塊內存的請求,這樣分配器又需要從大的空閑內存中切分出一塊,這樣無疑是比較低效的,故而,malloc 中在分配過程中引入了 fast bins,不大於 max_fast(默認值為 64B)的 chunk 被釋放後,首先會被放到 fast bins中,fast bins 中的 chunk 並不改變它的使用標誌 P。這樣也就無法將它們合併,當需要給用戶分配的 chunk 小於或等於 max_fast 時,malloc 首先會在 fast bins 中查找相應的空閑塊,然後才會去查找 bins 中的空閑 chunk。在某個特定的時候,malloc 會遍歷 fast bins 中的 chunk,將相鄰的空閑 chunk 進行合併,並將合併後的 chunk 加入 unsorted bin 中,然後再將 usorted bin 裏的 chunk 加入 bins 中。

unsorted bin 的隊列使用 bins 數組的第一個,如果被用戶釋放的 chunk 大於 max_fast,或者 fast bins 中的空閑 chunk 合併後,這些 chunk 首先會被放到 unsorted bin 隊列中,在進行 malloc 操作的時候,如果在 fast bins 中沒有找到合適的 chunk,則malloc 會先在 unsorted bin 中查找合適的空閑 chunk,然後才查找 bins。如果 unsorted bin 不能滿足分配要求。 malloc便會將 unsorted bin 中的 chunk 加入 bins 中。然後再從 bins 中繼續進行查找和分配過程。從這個過程可以看出來,unsorted bin 可以看做是 bins 的一個緩衝區,增加它只是為了加快分配的速度。（其實感覺在這裡還利用了局部性原理，常用的內存塊大小差不多，從unsorted bin這裡取就行了，這個和TLB之類的都是異曲同工之妙啊！）

除了上述四種bins之外，malloc還有三種內存區。

  1. 當fast bin和bins都不能滿足內存需求時，malloc會設法在top chunk中分配一塊內存給用戶；top chunk為在mmap區域分配一塊較大的空閑內存模擬sub-heap。（比較大的時候）
  2. 當chunk足夠大，fast bin和bins都不能滿足要求，甚至top chunk都不能滿足時，malloc會從mmap來直接使用內存映射來將頁映射到進程空間，這樣的chunk釋放時，直接解除映射，歸還給操作系統。（極限大的時候）
  3. Last remainder是另外一種特殊的chunk，就像top chunk和mmaped chunk一樣，不會在任何bins中找到這種chunk。當需要分配一個small chunk,但在small bins中找不到合適的chunk，如果last remainder chunk的大小大於所需要的small chunk大小，last remainder chunk被分裂成兩個chunk，其中一個chunk返回給用戶，另一個chunk變成新的last remainder chunk。（這個應該是fast bins中也找不到合適的時候，用於極限小的）

malloc內存分配（下面算是正常一般的情況了）

一開始時，brk和start_brk是相等的，這時實際heap大小為0；如果第一次用戶請求的內存大小小於mmap分配閾值，則malloc會申請(chunk_size+128kb) align 4kb大小的空間作為初始的heap。初始化heap之後，第二次申請的內存如果還是小於mmap分配閾值時，malloc會先查找fast bins,如果不能找到匹配的chunk，則查找small bins。若還是不行，合併fast bins,把chunk 加入到unsorted bin，在unsorted bin中查找，若還是不行，把unsorted bin中的chunk全加入large bins中，並查找large bins。在fast bins和small bins中查找都需要精確匹配，而在large bins中查找時，則遵循"smalest-first,best-fit"的原則，不需要精確匹配。

若以上都失敗了，malloc則會考慮使用top chunk。若top chunk也不能滿足分配，且所需的chunk大小大於mmap分配閾值，則使用mmap進行分配。否則增加heap，增加top chunk，以滿足分配要求。

現在來不上chunk的結構圖：

malloc利用chunk結構來管理內存塊，malloc就是由不同大小的chunk鏈表組成的。一個使用中的chunk的結構如下圖:

malloc會給用戶分配的空間的前後加上一些控制信息，用這樣的方法來記錄分配的信息，以便完成分配和釋放工作。chunk指針指向chunk開始的地方,圖中的mem指針纔是真正返回給用戶的內存指針。

  1. chunk 的第二個域的最低一位為 P,它表示前一個塊是否在使用中,P 為 0 則表示前一個 chunk 為空閑,這時chunk的第一個域 prev_size 纔有效,prev_size 表示前一個 chunk 的 size,程序可以使用這個值來找到前一個 chunk 的開始地址。當 P 為 1 時,表示前一個 chunk 正在使用中,prev_size程序也就不可以得到前一個 chunk 的大小。不能對前一個 chunk 進行任何操作。malloc分配的第一個塊總是將 P 設為 1,以防止程序引用到不存在的區域。(這裡就很細！)
  2. Chunk 的第二個域的倒數第二個位為 M,他表示當前 chunk 是從哪個內存區域獲得的虛擬內存。M 為 1 表示該 chunk 是從 mmap 映射區域分配的,否則是從 heap 區域分配的。
  3. Chunk 的第二個域倒數第三個位為 A,表示該 chunk 屬於主分配區或者非主分配區,如果屬於非主分配區,將該位置為 1,否則置為 0。

右邊圖是空閑的chunk:

當chunk空閑時，其M狀態是不存在的，只有AP狀態，原本是用戶數據區的地方存儲了四個指針，指針fd指向後一個空閑的chunk,而bk指向前一個空閑的chunk，malloc通過這兩個指針將大小相近的chunk連成一個雙向鏈表。在large bin中的空閑chunk，還有兩個指針，fd_nextsize和bk_nextsize，用於加快在large bin中查找最近匹配的空閑chunk。不同的chunk鏈表又是通過bins或者fastbins來組織的。（這裡就很符合網上大多數人說的鏈表理論了）

以上內容大部分參考阿里華庭寫的Glibc內存管理，Ptmalloc2源代碼分析。

感覺從這個人這裡學到了很多東西，是個大佬。

然後結合網上的一般回答：

鏈接：nowcoder.com/questionTe

來源：牛客網

malloc可以分別由夥伴系統或基於鏈表的實現；

1、它有一個將可用的內存塊連接為一個長長的列表的所謂空閑鏈表；

2、 調用malloc函數時，它沿連接表尋找一個大到足以滿足用戶請求所需要的內存塊。然後，將該內存塊一分為二（一塊的大小與用戶請求的大小相等，另一塊的大小就是剩下的位元組）。接下來，將分配給用戶的那塊內存傳給用戶，並將剩下的那塊（如果有的話）返回到連接表上。

3、 調用free函數時，它將用戶釋放的內存塊連接到空閑鏈上。到最後，空閑鏈會被切成很多的小內存片段，如果這時用戶申請一個大的內存片段，那麼空閑鏈上可能沒有可以滿足用戶要求的片段了。於是，malloc函數請求延時，並開始在空閑鏈上翻箱倒櫃地檢查各內存片段，對它們進行整理，將相鄰的小空閑塊合併成較大的內存塊。

雖然這個答案比較粗糙，但是也有大概的思想了。

malloc和free的實現原理 這位大哥講得也不錯，可以參考一下。

最後可以結合 騰訊雲技術社區：十問 Linux 虛擬內存管理 (glibc) (一) 騰訊的這個實踐來理論聯繫實踐。下面參考於這個騰訊的鏈接（建議可以去點個贊）：

malloc 是 glibc 中內存分配函數，也是最常用的動態內存分配函數，其內存必須通過 free 進行釋放，否則導致內存泄露。

關於 malloc 獲得虛存空間的實現，與 glibc 的版本有關，但大體邏輯是：

  1. 若分配內存小於 128k ，調用 sbrk() ，將堆頂指針向高地址移動，獲得新的虛存空間。
  2. 若分配內存大於 128k ，調用 mmap() ，在文件映射區域中分配匿名虛存空間。
  3. 這裡討論的是簡單情況，如果涉及並發可能會複雜一些，不過先不討論。

其中 sbrk 就是修改棧頂指針位置，而 mmap 可用於生成文件的映射以及匿名頁面的內存，這裡指的是匿名頁面。而這個 128k ，是 glibc 的默認配置，可通過函數 mallopt 來設置

接著： VSZ為虛擬內存 RSS為物理內存

  1. VSZ 並不是每次 malloc 後都增長，是與上一節說的堆頂沒發生變化有關，因為可重用堆頂內剩餘的空間，這樣的 malloc 是很輕量快速的。
  2. 但如果 VSZ 發生變化，基本與分配內存量相當，因為 VSZ 是計算虛擬地址空間總大小。
  3. RSS 的增量很少，是因為 malloc 分配的內存並不就馬上分配實際存儲空間，只有第一次使用，如第一次 memset 後才會分配。
  4. 由於每個物理內存頁面大小是 4k ，不管 memset 其中的 1k 還是 5k 、 7k ，實際佔用物理內存總是 4k 的倍數。所以 RSS 的增量總是 4k 的倍數。
  5. 因此，不是 malloc 後就馬上佔用實際內存，而是第一次使用時發現虛存對應的物理頁面未分配，產生缺頁中斷，才真正分配物理頁面，同時更新進程頁面的映射關係。這也是 Linux 虛擬內存管理的核心概念之一。

相信到這裡大家應該對malloc有比較深入的理解了。還是慢慢啃書先吧。。。

嗯，有點晚了，睡了

歡迎交流討論

推薦閱讀：

相關文章