malloc（）如何在內部實現？

Question

任何人都可以解釋malloc()內部工作嗎？

我有時做strace program，我看到了很多的sbrk系統調用，做這件事man sbrk會談malloc()正在使用但沒有更多。

Answer 1

系統調用sbrk移動數據段的「邊界」。這意味着它移動了一個程序可以讀/寫數據的區域的邊界（讓它增長或縮小，儘管AFAIK沒有malloc確實使用該方法將內存段返回給內核）。除此之外，還有mmap用於將文件映射到內存中，但也用於分配內存（如果您需要分配共享內存，mmap是您的操作方式）。

所以你有兩種從內核獲取更多內存的方法：sbrk和mmap。關於如何組織你從內核獲得的內存有各種策略。

一種天真的方式是將其分區爲通常稱爲「桶」的區域，這些區域專用於特定的結構尺寸。例如，malloc實現可以爲16,64,256和1024字節結構創建存儲桶。如果您要求malloc爲您提供給定大小的記憶，則會將該數字四捨五入到下一個存儲桶大小，然後爲您提供該存儲桶中的一個元素。如果你需要更大的區域malloc可以使用mmap直接與內核分配。如果某個尺寸的存儲桶爲空，malloc可以使用sbrk爲新存儲桶獲取更多空間。

有各種各樣的malloc設計，因爲您需要在速度，開銷和避免碎片/空間有效性之間做出妥協，所以沒有人會真正實施malloc。例如，如果一個存儲桶中的元素耗盡，實現可能會從一個更大的存儲桶中獲取一個元素，將其分解並將其添加到耗盡元素的存儲桶中。這將是相當節省空間，但不可能與每個設計。如果你通過sbrk/mmap獲得另一個桶，這可能會更快，更容易，但不是空間效率高。此外，設計當然必須考慮到「免費」需要以某種方式再次向malloc提供空間。你不只是分配內存而不重用它。

如果你有興趣，在OpenSER的/ Kamailio SIP代理有兩個malloc實現（他們需要自己的，因爲他們大量使用共享內存和malloc不支持共享內存系統）。見：https://github.com/OpenSIPS/opensips/tree/master/mem

然後，你也可以看看GNU libc malloc implementation，但這是一個非常複雜，IIRC。

Answer 2

簡單地malloc和free的工作是這樣的：

的malloc提供訪問進程的堆。堆是C核心庫（通常爲libc）中的一個構造，它允許對象獲得進程堆上某些空間的獨佔訪問權。

堆上的每個分配稱爲堆單元。這通常由一個頭部組成，該頭部保存關於單元大小的信息以及指向下一個堆單元的指針。這使得一個堆有效地成爲一個鏈表。

當啓動一個進程時，堆包含一個單元，其中包含啓動時分配的所有堆空間。這個單元格存在於堆的空閒列表中。

當一個調用malloc，存儲器從大堆單元，其通過malloc返回截取。其餘部分形成一個由所有其餘內存組成的新堆單元。

當一個釋放內存，堆小區被添加到堆的空閒列表的末尾。隨後的malloc在空閒列表中尋找合適大小的單元格。

可以預料，堆可能會碎片化，堆管理器可能會不時嘗試合併相鄰的堆單元。

當沒有留下所需的分配空閒列表上的內存，malloc的調用BRK或SBRK這是系統調用請求從操作系統中多個存儲頁。

現在有一些修改，以優化堆操作。

• 對於大的存儲器分配 （典型地> 512個字節，堆 管理器可以直接進入OS和 分配一個完整的存儲器頁面。
• 堆 可以指定 分配的最小尺寸，以防止大量碎片 。
• 堆也可能本身分爲頻段的一個爲小分配和一個較大的分配做出了較大的分配速度更快。
• 還有人如此巧妙的機制來優化多線程堆分配。

Answer 3

同樣重要的是要認識到，簡單地brk和sbrk走動的程序中斷指針實際上並不分配內存，它只是設置了地址空間。在Linux上，例如，該內存將被「支持」通過時地址範圍訪問實際的物理頁面，這將導致頁面錯誤，並最終導致內核調用到頁面分配器獲得的支持頁面。