malloc 背后的系统知识（虚拟内存地址）
內存優化總結:ptmalloc、tcmalloc和jemalloc：https://blog.csdn.net/junlon2006/article/details/77854898??
malloc的底層實現（ptmalloc）：https://blog.csdn.net/z_ryan/article/details/79950737
從操作系統層面來說，malloc 是考察面試者對操作系統底層的存儲管理理解的一個很好的方式，涉及到虛擬內存、分頁/分段等。下面逐個細說。
1. 虛擬內存
首先需要知道的是程序運行起來的話需要被加載的物理內存中，具體到計算機硬件就是內存條。操作系統啟動的時候先把自己加載到物理內存的固定位置（一般為底部），物理內存的其他位置就用來運行用戶程序。程序就是一堆指令，程序運行可以簡單抽象為把指令加載到內存中，然后 CPU 將指令從內存載入執行。
1. 為什么需要虛擬內存？
CPU 對內存的尋址最簡單的方式就是直接使用物理內存地址，這種方式一般叫做物理尋址。早期的 PC 使用物理尋址，而且像數字信號處理器、嵌入式微控制器也使用物理尋址。物理尋址的好處是簡單，壞處也有很多，比如：
不安全：操作系統的地址直接暴露給用戶程序，用戶程序可以破壞操作系統。這種解決方案是采用特殊的硬件保護。
同時運行多個程序比較困難：多個用戶程序如果都直接引用物理地址，很容易互相干擾。那么是不是可以通過不斷交換物理內存和磁盤來保證物理內存某一時間自由一個程序在運行呢？當時是可以的，但是這引入很多不必要和復雜的工作。
用戶程序大小受限：受制于物理內存大小。我們現在的錯覺是應用程序大小都小于物理內存，這主要是因為現在 PC 的物理內存都比較大。實際上只有 1G 物理內存的 PC 是可以運行 2G 的應用程序的。
?
綜合上面各種缺點，虛擬內存出現了。
2. 虛擬內存概覽
虛擬內存的基本思想是：每個程序擁有獨立的地址空間（也就是虛擬內存地址，或者稱作虛擬地址），互不干擾。地址空間被分割成多個塊，每一塊稱作一頁（page），每一頁有連續的地址范圍。虛擬地址的頁被映射到物理內存（通過 MMU，Memory Management Unit），但是并不是所有的頁都必須在內存中才能運行程序。當程序引用到一部分在物理內存中的地址空間時，由硬件立刻執行必要的映射。當程序引用到一部分不在物理內存中的地址空間時，由操作系統負責將確實的部分裝入物理內存。虛擬地址尋址（也叫做虛擬尋址）的示意圖如下。
3.虛擬內存實現
1.虛擬內存大小
一般是和 CPU 字長相關，比如 32 位對應的虛擬地址空間大小為：0 ~ 2^31。
2. MMU
CPU 將虛擬地址發送給 MMU，然后 MMU 將虛擬地址翻譯成物理地址，再尋址物理內存。那么虛擬地址和物理地址具體是怎么映射的呢？完成映射還需要另一個重要的數據結構的參與：頁表（page table）。頁表完成虛擬地址和物理地址的映射，MMU 每次翻譯的時候都需要讀取頁表。頁表的一種簡單表示如下。
這里頁大小為 p 位。虛擬內存的頁和物理內存的頁大小一樣。虛擬地址的高 n-p 位，又叫做虛擬頁號（Virtual Page Number, VPN），用來索引物理頁號（Physical Page Number，PPN），最后將 PPN 和低 p 位組合在一起就得到了物理地址。
3. 頁表的兩個問題
前面說到用 VPN 來做頁表索引，也就是說頁表的大小為虛擬地址位數 / 頁的大小。比如 32 位機器，頁大小一般為 4K ，則頁表項有 2^32 / 2^12 = 2^20 條目。如果機器字長 64 位，頁表項就更多了。那么怎么解決呢？一般有兩種方法：
倒排頁表。物理頁號做索引，映射到多個虛擬地址。通過虛擬地址查找的時候就需要通過虛擬地址的中間幾位來做索引了。
多級頁表。以兩級頁表為例。一級頁表中的每個 PTE （page table entry）映射虛擬地址空間的一個 4MB 的片，每一片由1024 個連續的頁面組成。一級 PTE 指向二級頁表的基址。這樣 32 位地址空間使用 1024 個一級 PTE 就可以表示。需要的二級頁表總條目還是 2^32 / 2^12 = 2^20 個。這里的關鍵在于如果一級 PTE i 中的頁面都未被分配，一級 PTE 就為空。多級頁面的一個簡單示意圖如下。
多級頁表減少內存占用的關鍵在于：
如果一級頁表中的一個 PTE 為空，那么相應的二級頁表就根本不會存在。這是一種巨大的潛在節約。
只有一級頁表才需要常駐內存。虛擬內存系統可以在需要時創建、頁面調入或者調出二級頁表，從而減輕內存的壓力。
第二個問題是頁表是在內存中，而 MMU 位于 CPU 芯片中，這樣每次地址翻譯可能都需要先訪問一次內存中的頁表（CPU L1,L2,L3 Cache Miss 的時候訪問內存），效率非常低下。對應的解決方案是引入頁表的高速緩存：TLB（Translation Lookaside Buffer）。加入 TLB，整個虛擬地址翻譯的過程如下兩圖所示。
什么是page fault
? ? ? ?當進程訪問它的虛擬地址空間中的PAGE時，如果這個PAGE目前還不在物理內存中，此時CPU是不能干活的，Linux會產生一個hard page fault中斷。系統需要從慢速設備（如磁盤）將對應的數據PAGE讀入物理內存，并建立物理內存地址與虛擬地址空間PAGE的映射關系。然后進程才能訪問這部分虛擬地址空間的內存。
page fault 又分為幾種，major page fault、 minor page fault、 invalid(segment fault)。
major page fault 也稱為 hard page fault, 指需要訪問的內存不在虛擬地址空間，也不在物理內存中，需要從慢速設備載入。從swap 回到物理內存也是 hard page fault。
minor page fault 也稱為 soft page fault, 指需要訪問的內存不在虛擬地址空間，但是在物理內存中，只需要MMU建立物理內存和虛擬地址空間的映射關系即可。
invalid fault 也稱為 segment fault，指進程需要訪問的內存地址不在它的虛擬地址空間范圍內，屬于越界訪問，內核會報 segment fault錯誤。
抖動在分頁存儲管理系統中，內存中只存放了那些經常使用的頁面， 而其它頁面則存放在外存中，當進程運行需要的內容不在內存時， 便啟動磁盤讀操作將所需內容調入內存，若內存中沒有空閑物理塊， 還需要將內存中的某頁面置換出去。也就是說，系統需要不斷地在內外存之間交換信息。 若在系統運行過程中，剛被淘汰出內存的頁面，過后不久又要訪問它， 需要再次將其調入。而該頁面調入內存后不久又再次被淘汰出內存，然后又要訪問它。 如此反復，使得系統把大部分時間用在了頁面的調入/換出上， 而幾乎不能完成任何有效的工作，這種現象稱為抖動。
2. 分段
1. 分段概述
前面介紹了分頁內存管理，可以說通過多級頁表，TLB 等，分頁內存管理方法已經相當不錯了。那么分頁有什么缺點呢？
共享困難：通過共享頁面來實現共享當然是可以的。這里的問題在于我們要保證頁面上只包含可以共享的內容并不是一件容易的事兒，因為進程空間是直接映射到頁面上的。這樣一個頁面上很可能包含不能共享的內容（比如既包含代碼又包含數據，代碼可以共享，而數據不能共享）。早期的 PDP-11 實現的一種解決方法是為指令和數據設置分離的地址空間，分別稱為 I 空間和 D 空間（其實這已經和分段很像了）。
程序地址空間受限于虛擬地址：我們將程序全部映射到一個統一的虛擬地址的問題在于不好擴張。不如我們程序的地址按先代碼放在一起，然后把數據放在一起，然后再放 XXX，這樣其中某一部分的空間擴張起來都會影響到相鄰的空間，非常不方便。
上面的問題一個比較直觀的解決方法是提供多個獨立的地址空間，也就是段（segment）。每個段的長度視具體的段不同而不同，而且是可以在運行期動態改變的。因為每個段都構成了一個獨立的地址空間，所以它們可以獨立的增長或者減小而不會影響到其他的段。如果一個段比較大，把它整個保存到內存中可能很不方便甚至是不可能的，因此可以對段采用分頁管理，只有那些真正需要的頁面才會被調入內存。
采用分段和分頁結合的方式管理內存，一個地址由兩個部分組成：段和段內地址。段內地址又進一步分為頁號和頁偏移。在進行內存訪問時，過程如下：
根據段號找到段描述符（存放段基址）。
檢查該段的頁表是否在內存中。如果在，則找到它的位置，如果不在，則產生段錯誤。
檢查所請求的虛擬頁面的頁表項，如果該頁面不在內存中則產生缺頁中斷，如果在內存中就從頁表項中取出這個頁面在內存中的起始地址。
將頁面起始地址和偏移量進行拼接得到物理地址，然后完成讀寫。
2. 進程的段
每個 Linux 程序都有一個運行時內存映像，也就是各個段的布局，簡單如下圖所示。
注意上圖只是一個相對位置圖，實際上這些段并不是相鄰的。主要的段包括只讀代碼段、讀寫段、運行時堆、映射區、用戶棧。在分配棧、堆段運行時地址的時候，鏈接器會使用空間地址空間布局隨機化（ASLR），但是相對位置不會變。上圖中 .data 等是對應進程中的不同數據的 section ，或者叫做節。簡介如下。
-
.text: 已編譯程序的機器代碼。
-
.rodata: 只讀數據。
-
.data: 已初始化的全局和靜態變量。局部變量保存在棧上。
-
.bss: 未初始化的全局和靜態變量，以及所有被初始化為 0 的全局或者靜態變量。在目標文件中這個節不占據實際的空間，它僅僅是一個占位符。
3. malloc 實現
1. 堆內存管理
我們常說的 malloc 函數是 glibc 提供的庫函數。
glibc 的內存管理使用的方法是 ptmalloc，除此之后還有很多其他內存管理方案，比如 tcmalloc （golang 使用的類似 tcmalloc）。
ptmalloc 對于申請內存小于 128KB 時，分配是在堆段，使用系統調用 brk() 或者 sbrk()。如果大于 128 KB 的話，分配在映射區，使用系統調用 mmap()。
2. brk, sbrk
在堆段申請的話，使用系統調用?brk?或者?sbrk。
int?brk(const?void?*addr);
void?*sbrk(intptr_t?incr);
brk?將 brk 指針放置到指定地址處，成功返回 0，否則返回 -1。sbrk?將 brk 指針向后移動指定字節，返回依賴于系統實現，或者返回移動前的 brk 位置，或者返回移動后的 brk 位置。下面使用?sbrk?實現一個巨簡單的 malloc。
void?*malloc(size_t?size)?{
????void?*p?=?sbrk(0);
????void?*request?=?sbrk(size);
????if?(request?==?(void*)?-1)?{
????????return?NULL;?// sbrk failed.
????}?else?{
????????assert(p?==?request);?// Not thread safe.
????????return?p;
????}
}
3. mmap
linux 系統調用 mmap 將一個文件或者其它對象映射進內存。
#include <sys/mman.h>
void?*mmap(void?*addr,?size_t?length,?int?prot,?int?flags,?int?fd,?off_t?offset);
mmap 的 flags 可選多種參數，當選擇?MAP_ANONYMOUS?時，不需要傳入文件描述符，malloc 使用的就是?MAP_ANONYMOUS?模式。mmap 申請的內存在操作系統的映射區。比如 32 位系統，映射區從 3G 虛擬地址粗向下生長，但是因為程序的其他段也會占用空間（比如代碼段必須以特定的地址開始），所以并不能申請 3G 的大小。
4. malloc 和物理內存有關系嗎？
可以說沒關系，malloc 申請的地址是線性地址，申請的時候并沒有進行映射。訪問到的時候觸發缺頁異常，這個時候才會進行物理地址映射。
5. ptmalloc
ptmalloc 只是 glibc 使用的內存管理策略，篇幅有限，這里就不細說了。
4. 參考：
《深入理解計算機系統》
《現代操作系統》
StackOverFlow
mmap manpage
tcmalloc 介紹
a malloc tutorial
malloc manpage
understanding glibc malloc
advanced memory allocation
總結
以上是生活随笔為你收集整理的malloc 背后的系统知识（虚拟内存地址）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C语言内存字节对齐小结
- 下一篇： 线程间同步的几种方法--互斥锁，条件变量