前言
大家好,我的朋友們!
CPU、IO、磁盤、內(nèi)存可以說是影響計算機性能關鍵因素,今天就聊探究下內(nèi)存的那些事兒。

內(nèi)存為進程的運行提供物理空間,同時作為快速CPU和慢速磁盤之間的適配器,可以說是個非常重要的角色。

通過本文你將了解到以下內(nèi)容:

本文均圍繞Linux操作系統(tǒng)展開,話不多說,我們開始吧!
虛擬內(nèi)存機制
當要學習一個新知識點時,比較好的過程是先理解出現(xiàn)這個技術點的背景原因,同期其他解決方案,新技術點解決了什么問題以及它存在哪些不足和改進之處,這樣整個學習過程是閉環(huán)的。
內(nèi)存為什么需要管理
老子的著名觀點是無為而治,簡單說就是不過多干預而充分依靠自覺就可以有條不紊地運作,理想是美好的,現(xiàn)實是殘酷的。
Linux系統(tǒng)如果以一種原始簡單的方式管理內(nèi)存是存在一些問題:
進程空間隔離問題
假如現(xiàn)在有ABC三個進程運行在Linux的內(nèi)存空間,設定OS給進程A分配的地址空間是0-20M,進程B地址空間30-80M,進程C地址空間90-120M。
雖然分配給每個進程的空間是無交集的,但是仍然無法避免進程在某些情況下出現(xiàn)訪問異常的情況,如圖:

比如進程A訪問了屬于進程B的空間,進程B訪問了屬于進程C的空間,甚至修改了空間的值,這樣就會造成混亂和錯誤,實際中是不允許發(fā)生的。
所以我們需要的是每個進程有獨立且隔離的安全空間。
內(nèi)存效率低下問題
機器的內(nèi)存是有限資源,而進程數(shù)量是動態(tài)且無法確定的,這樣就會出現(xiàn)幾個必須要考慮的問題:
-
如果已經(jīng)啟動的進程們占據(jù)了幾乎所有內(nèi)存空間,沒有新內(nèi)存可分配了,此時新進程將無法啟動。
-
已經(jīng)啟動的進程有時候是在睡大覺,也就是給了內(nèi)存也不用,占著茅坑不拉屎。
-
連續(xù)內(nèi)存實在是很珍貴,大部分時候我們都無法給進程分配它想要的連續(xù)內(nèi)存,離散化內(nèi)存才是我們需要面對的現(xiàn)實。

定位調(diào)試和編譯運行問題
由于程序運行時的位置是不確定的,我們在定位問題、調(diào)試代碼、編譯執(zhí)行時都會存在很多問題。
我們希望每個進程有一致且完整的地址空間,同樣的起始位置放置了堆、棧以及代碼段等,從而簡化編譯和執(zhí)行過程中的鏈接器、加載器的使用。
換句話說,如果所有進程的空間地址分配都是一樣的,那么Linux在設計編譯和調(diào)試工具時就非常簡單了,否則每個進程都可能是定制化的。
綜上,面對眾多問題,我們需要一套內(nèi)存管理機制。
中間層的引入
大家一定聽過這句計算機諺語:
Any problem in computer science can be solved by another layer of indirection.
計算機科學領域的任何問題都可以通過增加一個中間層來解決,解決內(nèi)存問題也不例外。

Linux的虛擬內(nèi)存機制簡單來說就是在物理內(nèi)存和進程之間請了個管家,內(nèi)存管家上任之后做了以下幾件事情:
- 給每個進程分配完全獨立的虛擬空間,每個進程終于有只屬于自己的活動場地了
- 進程使用的虛擬空間最終還要落到物理內(nèi)存上,因此設置了一套完善的虛擬地址和物理地址的映射機制
- 引入缺頁異常機制實現(xiàn)內(nèi)存的惰性分配,啥時候用啥時候再給
- 引入swap機制把不活躍的數(shù)據(jù)換到磁盤上,讓每塊內(nèi)存都用在刀刃上
- 引入OOM機制在內(nèi)存緊張的情況下干掉那些內(nèi)存殺手
- ......
虛擬內(nèi)存下數(shù)據(jù)讀寫問題
引入虛擬機制后,進程在獲取CPU資源讀取數(shù)據(jù)時的流程也發(fā)生了一些變化。

CPU并不再直接和物理內(nèi)存打交道,而是把地址轉換的活外包給了MMU,MMU是一種硬件電路,其速度很快,主要工作是進行內(nèi)存管理,地址轉換只是它承接的業(yè)務之一。

頁表的存儲和檢索問題
每個進程都會有自己的頁表Page Table,頁表存儲了進程中虛擬地址到物理地址的映射關系,所以就相當于一張地圖,MMU收到CPU的虛擬地址之后開始查詢頁表,確定是否存在映射以及讀寫權限是否正常,如圖:

當機器的物理內(nèi)存越來越大,頁表這個地圖也將非常大,于是問題出現(xiàn)了:
- 對于4GB的虛擬地址且大小為4KB頁,一級頁表將有2^20個表項,頁表占有連續(xù)內(nèi)存并且存儲空間大
- 多級頁表可以有效降低頁表的存儲空間以及內(nèi)存連續(xù)性要求,但是多級頁表同時也帶來了查詢效率問題

我們以2級頁表為例,MMU要先進行兩次頁表查詢確定物理地址,在確認了權限等問題后,MMU再將這個物理地址發(fā)送到總線,內(nèi)存收到之后開始讀取對應地址的數(shù)據(jù)并返回。

MMU在2級頁表的情況下進行了2次檢索和1次讀寫,那么當頁表變?yōu)镹級時,就變成了N次檢索+1次讀寫。
可見,頁表級數(shù)越多查詢的步驟越多,對于CPU來說等待時間越長,效率越低,這個問題還需要優(yōu)化才行。
本段小結 敲黑板 劃重點
頁表存在于進程的內(nèi)存之中,MMU收到虛擬地址之后查詢Page Table來獲取物理地址。
單級頁表對連續(xù)內(nèi)存要求高,于是引入了多級頁表。
多級頁表也是一把雙刃劍,在減少連續(xù)存儲要求且減少存儲空間的同時降低了查詢效率。
MMU和TLB這對黃金搭檔
CPU覺得MMU干活雖然賣力氣,但是效率有點低,不太想繼續(xù)外包給它了,這一下子把MMU急壞了。
MMU于是找來了一些精通統(tǒng)計的朋友,經(jīng)過一番研究之后發(fā)現(xiàn)CPU用的數(shù)據(jù)經(jīng)常是一小搓,但是每次MMU都還要重復之前的步驟來檢索,害,就知道埋頭干活了,也得講究方式方法呀!
找到瓶頸之后,MMU引入了新武器,江湖人稱快表的TLB,別看TLB容量小,但是正式上崗之后干活還真是不含糊。

當CPU給MMU傳新虛擬地址之后,MMU先去問TLB那邊有沒有,如果有就直接拿到物理地址發(fā)到總線給內(nèi)存,齊活。
TLB容量比較小,難免發(fā)生Cache Miss,這時候MMU還有保底的老武器頁表 Page Table,在頁表中找到之后MMU除了把地址發(fā)到總線傳給內(nèi)存,還把這條映射關系給到TLB,讓它記錄一下刷新緩存。
TLB容量不滿的時候就直接把新記錄存儲了,當滿了的時候就開啟了淘汰大法把舊記錄清除掉,來保存新記錄,仿佛完美解決了問題。

本段小結 敲黑板 劃重點
MMU也是個聰明的家伙,集成了TLB來存儲CPU最近常用的頁表項來加速尋址,TLB找不到再去全量頁表尋址,可以認為TLB是MMU的緩存。
缺頁異常來了
假如目標內(nèi)存頁在物理內(nèi)存中沒有對應的頁幀或者存在但無對應權限,CPU 就無法獲取數(shù)據(jù),這種情況下CPU就會報告一個缺頁錯誤。
由于CPU沒有數(shù)據(jù)就無法進行計算,CPU罷工了用戶進程也就出現(xiàn)了缺頁中斷,進程會從用戶態(tài)切換到內(nèi)核態(tài),并將缺頁中斷交給內(nèi)核的 Page Fault Handler 處理。

缺頁中斷會交給PageFaultHandler處理,其根據(jù)缺頁中斷的不同類型會進行不同的處理:
-
Hard Page Fault
也被稱為Major Page Fault,翻譯為硬缺頁錯誤/主要缺頁錯誤,這時物理內(nèi)存中沒有對應的頁幀,需要CPU打開磁盤設備讀取到物理內(nèi)存中,再讓MMU建立VA和PA的映射。 -
Soft Page Fault
也被稱為Minor Page Fault,翻譯為軟缺頁錯誤/次要缺頁錯誤,這時物理內(nèi)存中是存在對應頁幀的,只不過可能是其他進程調(diào)入的,發(fā)出缺頁異常的進程不知道而已,此時MMU只需要建立映射即可,無需從磁盤讀取寫入內(nèi)存,一般出現(xiàn)在多進程共享內(nèi)存區(qū)域。 -
Invalid Page Fault
翻譯為無效缺頁錯誤,比如進程訪問的內(nèi)存地址越界訪問,又比如對空指針解引用內(nèi)核就會報segment fault錯誤中斷進程直接掛掉。

不同類型的Page Fault出現(xiàn)的原因也不一樣,常見的幾種原因包括:
-
非法操作訪問越界
這種情況產(chǎn)生的影響也是最大的,也是Coredump的重要來源,比如空指針解引用或者權限問題等都會出現(xiàn)缺頁錯誤。 -
使用malloc新申請內(nèi)存
malloc機制是延時分配內(nèi)存,當使用malloc申請內(nèi)存時并未真實分配物理內(nèi)存,等到真正開始使用malloc申請的物理內(nèi)存時發(fā)現(xiàn)沒有才會啟動申請,期間就會出現(xiàn)Page Fault。 -
訪問數(shù)據(jù)被swap換出
物理內(nèi)存是有限資源,當運行很多進程時并不是每個進程都活躍,對此OS會啟動內(nèi)存頁面置換將長時間未使用的物理內(nèi)存頁幀放到swap分區(qū)來騰空資源給其他進程,當存在于swap分區(qū)的頁面被訪問時就會觸發(fā)Page Fault從而再置換回物理內(nèi)存。

本段小結 敲黑板 劃重點
缺頁異常在虛擬機制下是必然會出現(xiàn)的,原因非常多,沒什么大不了的,在缺頁異常的配合下合法的內(nèi)存訪問才能得到響應。
我們基本弄清楚了為什么需要內(nèi)存管理、虛擬內(nèi)存機制主要做什么、虛擬機制下數(shù)據(jù)的讀寫流程等等。

內(nèi)存分配
虛擬機制下每個進程都有獨立的地址空間,并且地址空間被劃分為了很多部分,如圖為32位系統(tǒng)中虛擬地址空間分配:

64位系統(tǒng)也是類似的,只不過對應的空間都擴大為128TB。
來看看各個段各自特點和相互聯(lián)系:
-
text段包含了當前運行進程的二進制代碼,所以又被稱為代碼段,在32位和64位系統(tǒng)中代碼段的起始地址都是確定的,并且大小也是確定的。
-
data段存儲已初始化的全局變量,和text段緊挨著,中間沒有空隙,因此起始地址也是固定的,大小也是確定的。
-
bss段存儲未初始化的全局變量,和data段緊挨著,中間沒有空隙,因此起始地址也是固定的,大小也是確定的。
-
heap段和bss段并不是緊挨著的,中間會有一個隨機的偏移量,heap段的起始地址也被稱為start_brk,由于heap段是動態(tài)的,頂部位置稱為program break brk。
-
在heap段上方是內(nèi)存映射段,該段是mmap系統(tǒng)調(diào)用映射出來的,該段的大小也是不確定的,并且夾在heap段和stack段中間,該段的起始地址也是不確定的。
-
stack段算是用戶空間地址最高的一部分了,它也并沒有和內(nèi)核地址空間緊挨著,中間有隨機偏移量,同時一般stack段會設置最大值RLIMIT_STACK(比如8MB),在之下再加上一個隨機偏移量就是內(nèi)存映射段的起始地址了。
看到這里,大家可能暈了我們抓住幾點:
- 進程虛擬空間的各個段,并非緊挨著,也就是有的段的起始地址并不確定,大小也并不確定
- 隨機的地址是為了防止黑客的攻擊,因為固定的地址被攻擊難度低很多
我把heap段、stack段、mmap段再細化一張圖:

從圖上我們可以看到各個段的布局關系和隨機偏移量的使用,多看幾遍就清楚啦!
內(nèi)存區(qū)域的組織
從前面可以看到進程虛擬空間就是一塊塊不同區(qū)域的集合,這些區(qū)域就是我們上面的段,每個區(qū)域在Linux系統(tǒng)中使用vm_area_struct這個數(shù)據(jù)結構來表示的。
內(nèi)核為每個進程維護了一個單獨的任務結構task_strcut,該結構中包含了進程運行時所需的全部信息,其中有一個內(nèi)存管理(memory manage)相關的成員結構mm_struct:
structmm_struct*mm;
structmm_struct*active_mm;
結構mm_strcut的成員非常多,其中gpd和mmap是我們需要關注的:
- pgd指向第一級頁表的基地址,是實現(xiàn)虛擬地址和物理地址的重要部分
- mmap指向一個雙向鏈表,鏈表節(jié)點是vm_area_struct結構體,vm_area_struct描述了虛擬空間中的一個區(qū)域
- mm_rb指向一個紅黑樹的根結點,節(jié)點結構也是vm_area_struct

我們看下vm_area_struct的結構體定義,后面要用到,注意看哈:

vm_area_start作為鏈表節(jié)點串聯(lián)在一起,每個vm_area_struct表示一個虛擬內(nèi)存區(qū)域,由其中的vm_start和vm_end指向了該區(qū)域的起始地址和結束地址,這樣多個vm_area_struct就將進程的多個段組合在一起了。

我們同時注意到vm_area_struct的結構體定義中有rb_node的相關成員,不過有的版本內(nèi)核是AVL-Tree,這樣就和mm_struct對應起來了:

這樣vm_area_struct通過雙向鏈表和紅黑樹兩種數(shù)據(jù)結構串聯(lián)起來,實現(xiàn)了兩種不同效率的查找,雙向鏈表用于遍歷vm_area_struct,紅黑樹用于快速查找符合條件的vm_area_struct。
內(nèi)存分配器概述
有內(nèi)存分配和回收的地方就可能有內(nèi)存分配器。
以glibc為例,我們先捋一下:
- 在用戶態(tài)層面,進程使用庫函數(shù)malloc分配的是虛擬內(nèi)存,并且系統(tǒng)是延遲分配物理內(nèi)存的,由缺頁中斷來完成分配
- 在內(nèi)核態(tài)層面,內(nèi)核也需要物理內(nèi)存,并且使用了另外一套不同于用戶態(tài)的分配機制和系統(tǒng)調(diào)用函數(shù)
從而就引出了,今天的主線圖:

從圖中我們來闡述幾個重點:
- 伙伴系統(tǒng)和slab屬于內(nèi)核級別的內(nèi)存分配器,同時為內(nèi)核層面內(nèi)存分配和用戶側面內(nèi)存分配提供服務,算是終極boss的趕腳
- 內(nèi)核有自己單獨的內(nèi)存分配函數(shù)kmalloc/vmalloc,和用戶態(tài)的不一樣,畢竟是中樞機構嘛
- 用戶態(tài)的進程通過庫函數(shù)malloc來玩轉內(nèi)存,malloc調(diào)用了brk/mmap這兩個系統(tǒng)調(diào)用,最終觸達到伙伴系統(tǒng)實現(xiàn)內(nèi)存分配
- 內(nèi)存分配器分為兩大類:用戶態(tài)和內(nèi)核態(tài),用戶態(tài)分配和釋放內(nèi)存最終還是通過內(nèi)核態(tài)來實現(xiàn)的,用戶態(tài)分配器更加貼合進程需求,有種社區(qū)居委會的感覺
常見用戶態(tài)內(nèi)存分配器
進程的內(nèi)存分配器工作于內(nèi)核和用戶程序之間,主要是為了實現(xiàn)用戶態(tài)的內(nèi)存管理。
分配器響應進程的內(nèi)存分配請求,向操作系統(tǒng)申請內(nèi)存,找到合適的內(nèi)存后返回給用戶程序,當進程非常多或者頻繁內(nèi)存分配釋放時,每次都找內(nèi)核老大哥要內(nèi)存/歸還內(nèi)存,可以說十分麻煩。
總麻煩大哥,也不是個事兒,于是分配器決定自己搞管理!
- 分配器一般都會預先分配一塊大于用戶請求的內(nèi)存,然后管理這塊內(nèi)存
- 進程釋放的內(nèi)存并不會立即返回給操作系統(tǒng),分配器會管理這些釋放掉的內(nèi)存從而快速響應后續(xù)的請求

說到管理能力,每個人每個國家都有很大差別,分配器也不例外,要想管好這塊內(nèi)存也挺難的,場景很多要求很多,于是就出現(xiàn)了很多分配器:

- dlmalloc
dlmalloc是一個著名的內(nèi)存分配器,最早由Doug Lea在1980s年代編寫,由于早期C庫的內(nèi)置分配器在某種程度上的缺陷,dlmalloc出現(xiàn)后立即獲得了廣泛應用,后面很多優(yōu)秀分配器中都能看到dlmalloc的影子,可以說是鼻祖了。
http://gee.cs.oswego.edu/dl/html/malloc.html
- ptmalloc2
ptmalloc是在dlmalloc的基礎上進行了多線程改造,認為是dlmalloc的擴展版本,它也是目前glibc中使用的默認分配器,不過后續(xù)各自都有不同的修改,因此ptmalloc2和glibc中默認分配器也并非完全一樣。
- tcmalloc
tcmalloc 出身于 Google,全稱是 thread-caching malloc,所以 tcmalloc 最大的特點是帶有線程緩存,tcmalloc 非常出名,目前在 Chrome、Safari 等知名產(chǎn)品中都有所應有。
tcmalloc 為每個線程分配了一個局部緩存,對于小對象的分配,可以直接由線程局部緩存來完成,對于大對象的分配場景,tcmalloc 嘗試采用自旋鎖來減少多線程的鎖競爭問題。
- jemalloc
jemalloc 是由 Jason Evans 在 FreeBSD 項目中引入的新一代內(nèi)存分配器。
它是一個通用的 malloc 實現(xiàn),側重于減少內(nèi)存碎片和提升高并發(fā)場景下內(nèi)存的分配效率,其目標是能夠替代 malloc。
jemalloc 應用十分廣泛,在 Firefox、Redis、Rust、Netty 等出名的產(chǎn)品或者編程語言中都有大量使用。
具體細節(jié)可以參考 Jason Evans 發(fā)表的論文 《A Scalable Concurrent malloc Implementation for FreeBSD》
論文鏈接:https://www.bsdcan.org/2006/papers/jemalloc.pdf
glibc malloc原理分析
我們在使用malloc進行內(nèi)存分配,malloc只是glibc提供的庫函數(shù),它仍然會調(diào)用其他函數(shù)從而最終觸達到物理內(nèi)存,所以是個很長的鏈路。
我們先看下malloc的特點:
- malloc 申請分配指定size個字節(jié)的內(nèi)存空間,返回類型是 void* 類型,但是此時的內(nèi)存只是虛擬空間內(nèi)的連續(xù)內(nèi)存,無法保證物理內(nèi)存連續(xù)
- mallo并不關心進程用申請的內(nèi)存來存儲什么類型的數(shù)據(jù),void*類型可以強制轉換為任何其它類型的指針,從而做到通用性
/*mallocexample*/
#include
#include
intmain()
{
inti,n;
char*buffer;
scanf("%d",&i);
buffer=(char*)malloc(i+1);
if(buffer==NULL)exit(1);
for(n=0;n'a';
buffer[i]='?';
free(buffer);
return0;
}
上面是malloc作為庫函數(shù)和用戶交互的部分,如果不深究原理,掌握上面這些就可以使用malloc了,但是對于我們這些追求極致的人來說,還遠遠不夠。
繼續(xù)我看下 malloc是如何觸達到物理內(nèi)存的:
#include
intbrk(void*addr);
void*sbrk(intptr_tincrement);
- brk函數(shù)將break指針直接設置為某個地址,相當于絕對值
- sbrk將break指針從當前位置移動increment所指定的增量,相當于相對值
- 本質上brk和sbrk作用是一樣的都是移動break指針的位置來擴展內(nèi)存
畫外音:我原來以為sbrk是brk的什么safe版本,還真是無知了
#include
void*mmap(void*addr,size\_tlength,intprot,intflags,intfd,off\_toffset);
intmunmap(void*addr,size_tlength);
- mmap和munmap是一對函數(shù),一個負責申請,一個負責釋放
- mmap有兩個功能:實現(xiàn)文件映射到內(nèi)存區(qū)域 和 分配匿名內(nèi)存區(qū)域,在malloc中使用的就是匿名內(nèi)存分配,從而為程序存放數(shù)據(jù)開辟空間

malloc底層數(shù)據(jù)結構
malloc的核心工作就是組織管理內(nèi)存,高效響應進程的內(nèi)存使用需求,同時保證內(nèi)存的使用率,降低內(nèi)存碎片化。
那么malloc是如何解決這些問題呢?

malloc為了解決這些問題,采用了多種數(shù)據(jù)結構和策略來實現(xiàn)內(nèi)存分配,這就是我們接下來研究的事情:
- 什么樣的數(shù)據(jù)結構
- 什么樣的組織策略
事情沒有一蹴而就,我們很難理解內(nèi)存分配器設計者面臨的復雜問題,因此當我們看到malloc底層復雜的設計邏輯時難免沒有頭緒,所以要忽略細節(jié)抓住主線多看幾遍。
malloc將內(nèi)存分成了大小不同的chunk,malloc將相似大小的chunk用雙向鏈表鏈接起來,這樣一個鏈表被稱為一個bin。
這些空閑的不同大小的內(nèi)存塊chunk通過bin來組織起來,換句話說bin是空閑內(nèi)存塊chunk的容器。
malloc一共維護了128個bin,并使用一個數(shù)組來存儲這些bin。

malloc中128個bin的bins數(shù)組存儲的chunk情況如下:

- bins[0]目前沒有使用
- bins[1]的鏈表稱為unsorted_list,用于維護free釋放的chunk。
- bins[2,63]總計長度為62的區(qū)間稱為small_bins,用于維護<512B的內(nèi)存塊,其中每個bin中對應的鏈表中的chunk大小相同,相鄰bin的大小相差8字節(jié),范圍為16字節(jié)到504字節(jié)。

- bins[64,126]總計長度為63的區(qū)間稱為large_bins,用于維護大于等于512字節(jié)的內(nèi)存塊,每個元素對應的鏈表中的chunk大小不同,數(shù)組下標越大鏈表中chunk的內(nèi)存越大,large bins中的每一個bin分別包含了一個給定范圍內(nèi)的chunk,其中的chunk按大小遞減排序,最后一組的largebin鏈中的chunk大小無限制,該bins的使用頻率低于small bins。
malloc有兩種特殊類型的bin:
- fast bin
malloc對于釋放的內(nèi)存并不會立刻進行合并,如何將剛釋放的兩個相鄰小chunk合并為1個大chunk,此時進程分配仍然是小chunk則可能還需要分割大chunk,來來回回確實很低效,于是出現(xiàn)了fast bin。
fast bin存儲在fastbinY數(shù)組中,一共有10個,每個fast bin都是一個單鏈表,每個單鏈表中的chunk大小是一樣的,多個鏈表的chunk大小不同,這樣在找特定大小的chunk的時候就不用挨個找,只需要計算出對應鏈表的索引即可,提高了效率。
//http://gee.cs.oswego.edu/pub/misc/malloc-2.7.2.c
/*Themaximumfastbinrequestsizewesupport*/
#defineMAX_FAST_SIZE80
#defineNFASTBINS(fastbin_index(request2size(MAX_FAST_SIZE))+1)
多個fast bin鏈表存儲的chunk大小有16, 24, 32, 40, 48, 56, 64, 72, 80, 88字節(jié)總計10種大小。
fast bin是除tcache外優(yōu)先級最高的,如果fastbin中有滿足需求的chunk就不需要再到small bin和large bin中尋找。當在fast bin中找到需要的chunk后還將與該chunk大小相同的所有chunk放入tcache,目的就是利用局部性原理提高下一次內(nèi)存分配的效率。
對于不超過max_fast的chunk被釋放后,首先會被放到 fast bin中,當給用戶分配的 chunk 小于或等于 max_fast 時,malloc 首先會在 fast bin 中查找相應的空閑塊,找不到再去找別的bin。
- unsorted bin
當小塊或大塊內(nèi)存被釋放時,它們會被添加到 unsorted bin 里,相當于malloc給了最近被釋放的內(nèi)存被快速二次利用的機會,在內(nèi)存分配的速度上有所提升。
當用戶釋放的內(nèi)存大于max_fast或者fast bins合并后的chunk都會首先進入unsorted bin上,unsorted bin中的chunk大小沒有限制。
在進行 malloc 操作的時候,如果在 fast bins 中沒有找到合適的 chunk,則malloc 會先在 unsorted bin 中查找合適的空閑 chunk。
unsorted bin里面的chunk是最近回收的,但是并不能全部再被快速利用,因此在遍歷unsorted bins的過程中會把不同大小的chunk再分配到small bins或者large bins。
malloc在chunk和bin的結構之上,還有兩種特殊的chunk:
- top chunk
top chunk不屬于任何bin,它是始終位于堆內(nèi)存的頂部。
當所有的bin里的chunk都無法滿足分配要求時,malloc會從top chunk分配內(nèi)存,如果大小不合適會進行分割,剩余部分形成新的top chunk。
如果top chunk也無法滿足用戶的請求,malloc只能向系統(tǒng)申請更多的堆空間,所以top chunk可以認為是各種bin的后備力量,尤其在分配大內(nèi)存時,large bins也無法滿足時大哥就得頂上了。
- last remainder chunk
當unsorted bin只有1個chunk,并且這個chunk是上次剛剛被使用過的內(nèi)存塊,那么它就是last remainder chunk。
當進程分配一個small chunk,在small bins中找不到合適的chunk,這時last remainder chunk就上場了。
- 如果last remainder chunk大于所需的small chunk大小,它會被分裂成兩個chunk,其中一個chunk返回給用戶,另一個chunk變成新的last remainder chunk。
這種特殊chunk主要用于分配內(nèi)存非常小的情況下,當fast bin和small bin都無法滿足時,還會再次從last remainder chunk進行分配,這樣就很好地利用了程序局部性原理。
malloc內(nèi)存分配流程
前面我們了解到malloc為了實現(xiàn)內(nèi)存的分配,采用了一些數(shù)據(jù)結構和組織策略,接著我們來看看實際的內(nèi)存分配流程以及這些數(shù)據(jù)結構之間的關系。

在上圖中有幾個點需要說明:
-
內(nèi)存釋放后,size小于max_fast則放到fast bin中,size大于max_fast則放到unsorted bin中,fast bin和unsorted bin可以看作是剛釋放內(nèi)存的容器,目的是給這些釋放內(nèi)存二次被利用的機會。
-
fast bin中的fast chunk被設置為不可合并,但是如果一直不合并也就爆了,因此會定期合并fast chunk到unsorted bin中。
-
unsorted bin很特殊,可以認為是個中間過渡bin,在large bin分割chunk時也會將下腳料chunk放到unsorted bin中等待后續(xù)合并以及再分配到small bin和large bin中。
-
由于small bin和large bin鏈表很多并且大小各不相同,遍歷查找合適chunk過程是很耗時的,為此引入binmap結構來加速查找,binmap記錄了bins的是否為空等情況,可以提高效率。
當用戶申請的內(nèi)存比較小時,分配過程會比較復雜,我們再嘗試梳理下該情況下的分配流程:

查找合適空閑內(nèi)存塊的過程涉及循環(huán)過程,因此把各個步驟標記順序來表述過程。
- 將進程需要分配的內(nèi)存轉換為對應空閑內(nèi)存塊的大小,記做chunk_size。
- 當chunk_size小于等于max_fast,則在fast bin中搜索合適的chunk,找到則返回給用戶,否則跳到第3步。
- 當chunk_size<=512字節(jié),那么可能在small bin的范圍內(nèi)有合適的chunk,找到合適的則返回,否則跳到第4步。
- 在fast bin和small bin都沒有合適的chunk,那么就對fast bin中的相鄰chunk進行合并,合并后的更大的chunk放到unsorted bin中,跳轉到第5步。
- 如果chunk_size屬于small bins,unsorted bin 中只有一個 chunk,并且該 chunk 大于等于需要分配的大小,此時將該 chunk 進行切割,一部分返回給用戶,另外一部分形成新的last remainder chunk分配結束,否則將 unsorted bin 中的 chunk 放入 small bins 或者 large bins,進入第6步。
- 現(xiàn)在看chunk_size屬于比較大的,因此在large bins進行搜索,滿足要求則返回,否則跳到第7步。
- 至此fast bin和另外三組bin都無法滿足要求,就輪到top chunk了,在top chunk滿足則返回,否則跳到第8步。
- 如果chunk_size大于等于mmap分配閾值,使用mmap向內(nèi)核伙伴系統(tǒng)申請內(nèi)存,chunk_size小于mmap閾值則使用brk來擴展top chunk滿足要求。
特別地,搜索合適chunk的過程中,fast bins 和small bins需要大小精確匹配,而在large bins中遵循“smallest-first,best-fit”的原則,不需要精確匹配,因此也會出現(xiàn)較多的碎片。
內(nèi)存回收
內(nèi)存回收的必要性顯而易見,試想一直分配不回收,當進程們需要新大塊內(nèi)存時肯定就沒內(nèi)存可用了,為此內(nèi)存回收必須要搞起來。
頁面回收
內(nèi)存回收就是釋放掉比如緩存和緩沖區(qū)的內(nèi)存,通常他們被稱為文件頁page cache,對于通過mmap生成的用于存放程序數(shù)據(jù)而非文件數(shù)據(jù)的內(nèi)存頁稱為匿名頁。
- 文件頁 有外部的文件介質形成映射關系
- 匿名頁 沒有外部的文件形成映射關系
這兩種物理頁面在某些情況下是可以回收的,但是處理方式并不同。
文件頁回收
page cache常被用于緩沖磁盤文件的數(shù)據(jù),讓磁盤數(shù)據(jù)放到內(nèi)存中來實現(xiàn)CPU的快速訪問。
page cache中有非常多page frame,要回收這些page frame需要確定這些物理頁是否還在用,為了解決這個問題出現(xiàn)了反向映射技術。
正向映射是通過虛擬地址根據(jù)頁表找到物理內(nèi)存,反向映射就是通過物理地址找到哪些虛擬地址使用它,也就是當我們在決定page frame是否可以回收時,需要使用反向映射來查看哪些進程被映射到這塊物理頁了,進一步判斷是否可以回收。
反向映射技術最早并沒有在內(nèi)核中出現(xiàn),從誕生到被廣泛推廣也經(jīng)歷了很多波折,并且細節(jié)很多,要展開說估計還得萬八千字,所以我找了一篇關于反向映射很棒的文章:
https://cclinuxer.github.io/2020/11/Linux%E5%8F%8D%E5%90%91%E6%98%A0%E5%B0%84%E6%9C%BA%E5%88%B6/
找到可以回收的page frame之后內(nèi)核使用LRU算法進行回收,Linux采用的方法是維護2個雙向鏈表,一個是包含了最近使用頁面的active list,另一個是包含了最近不使用頁面的inactive list。
- active_list 活躍內(nèi)存頁鏈表,這里存放的是最近被訪問過的內(nèi)存頁,屬于安全區(qū)。
- inactive_list 不活躍內(nèi)存頁鏈表,這里存放的是很少被訪問的內(nèi)存頁,屬于毒區(qū)。
匿名頁回收
匿名頁沒有對應的文件形成映射,因此也就沒有像磁盤那樣的低速備份。
在回收匿名頁的時候,需要先保存匿名頁上的內(nèi)容到特定區(qū)域,這樣才能避免數(shù)據(jù)丟失保證后續(xù)的訪問。
匿名頁在進程中是非常普遍的,動態(tài)分配的堆內(nèi)存都可以說是匿名頁,Linux為回收匿名頁,特地開辟了swap space來存儲內(nèi)存上的數(shù)據(jù),關于swap機制的文章太多了,這算是個常識的東西了,所以本文不啰嗦啦!
內(nèi)核傾向于回收page cache中的物理頁面,只有當內(nèi)存很緊張并且內(nèi)核配置允許swap機制時,才會選擇回收匿名頁。
回收匿名頁意味著將數(shù)據(jù)放到了低速設備,一旦被訪問性能損耗也很大,因此現(xiàn)在大內(nèi)存的物理機器經(jīng)常關閉swap來提高性能。
kswapd線程和waterMark
NUMA架構下每個CPU都有自己的本地內(nèi)存來加速訪問避免總線擁擠,在本地內(nèi)存不足時又可以訪問其他Node的內(nèi)存,但是訪問速度會下降。

每個CPU加本地內(nèi)存被稱作Node,一個node又被劃分為多個zone,每個zone有自己一套內(nèi)存水位標記,來記錄本zone的內(nèi)存水平,同時每個node有一個kswapd內(nèi)核線程來回收內(nèi)存。
Linux內(nèi)核中有一個非常重要的內(nèi)核線程kswapd,負責在內(nèi)存不足的情況下回收頁面,系統(tǒng)初始化時,會為每一個NUMA內(nèi)存節(jié)點創(chuàng)建一個名為kswapd的內(nèi)核線程。
在內(nèi)存不足時內(nèi)核通過wakeup_kswapd()函數(shù)喚醒kswapd內(nèi)核線程來回收頁面,以便釋放一些內(nèi)存,kswapd的回收方式又被稱為background reclaim。
Linux內(nèi)核使用水位標記(watermark)的概念來描述這個壓力情況。
Linux為內(nèi)存的使用設置了三種內(nèi)存水位標記,high、low、min,當內(nèi)存處于不同階段會觸發(fā)不同的內(nèi)存回收機制,來保證內(nèi)存的供應,如圖:

他們所標記的分別含義為:
-
水位線在high以上表示內(nèi)存剩余較多,目前內(nèi)存使用壓力不大,kswapd處于休眠狀態(tài)
-
水位線在high-low的范圍表示目前雖然還有剩余內(nèi)存但是有點緊張,kswapd開始工作進行內(nèi)存回收
-
水位線在low-min表示剩余可用內(nèi)存不多了壓力山大,min是最小的水位標記,當剩余內(nèi)存達到這個狀態(tài)時,就說明內(nèi)存面臨很大壓力。
-
水位線低于min這部分內(nèi)存,就會觸發(fā)直接回收內(nèi)存。
OOM機制
OOM(Out Of Memory)是Linux內(nèi)核在可用內(nèi)存較少或者某個進程瞬間申請并使用超額的內(nèi)存,此時空閑的物理內(nèi)存是遠遠不夠的,此時就會觸發(fā)OOM。
為了保證其他進程兄弟們能正常跑,內(nèi)核會讓OOM Killer根據(jù)設置參數(shù)和策略選擇認為最值得被殺死的進程,殺掉它然后釋放內(nèi)存來保證大盤的穩(wěn)定。
OOM Killer這個殺手很多時候不夠智慧,經(jīng)常會遇到進程A是個重要程序,正在歡快穩(wěn)定的跑著,此時殺出來個進程B,瞬間要申請大量內(nèi)存,Linux發(fā)現(xiàn)滿足不了這個程咬金,于是就祭出大招OOM Killer,但是結果卻是把進程A給殺了。
在oom的源碼中可以看到,作者關于如何選擇最優(yōu)進程的一些說明:
https://github.com/torvalds/linux/blob/master/mm/oom_kill.c
oom_killer在選擇最優(yōu)進程時決策并不完美,只是做到了"還行",根據(jù)策略對進程打分,選擇分數(shù)最高的進程殺掉。
具體的計算在oom_badness函數(shù)中進行的,如下為分數(shù)的計算:
其中涉及進程正在使用的物理內(nèi)存RSS+swap分區(qū)+頁面緩沖,再對比總內(nèi)存大小,同時還有一些配置來避免殺死最重要的進程。

進程設置OOM_SCORE_ADJ_MIN時,說明該進程為不可被殺死,返回的得分就非常低,從而被oom killer豁免。
總結
本文首先介紹虛擬內(nèi)存機制產(chǎn)生的原因,以及Linux虛擬內(nèi)存機制的基本原理、同時引入了實現(xiàn)的數(shù)據(jù)結構和段頁機制。
其次重點介紹了內(nèi)存分配器、并以glibc的malloc為藍本講述該內(nèi)存分配器采用何種數(shù)據(jù)結構來實現(xiàn)空閑內(nèi)存管理。
最后闡述內(nèi)存回收的原理,介紹了匿名頁和文件頁的回收差異性,同時介紹了kswapd內(nèi)核線程和內(nèi)存watermark機制。
篇幅和能力所限,本文只能給出一條主線來展示內(nèi)存如何被組織、使用、回收等,如果不是內(nèi)核開發(fā)人員,單純的業(yè)務開發(fā)人員足以應付面試和日常工作。
最后,感謝大家的耐心閱讀,有疑問請直接交流。
審核編輯 :李倩
-
cpu
+關注
關注
68文章
11039瀏覽量
216041 -
Linux
+關注
關注
87文章
11465瀏覽量
212825 -
內(nèi)存
+關注
關注
8文章
3109瀏覽量
75003
原文標題:圖解|Linux內(nèi)存背后的那些神秘往事
文章出處:【微信號:yikoulinux,微信公眾號:一口Linux】歡迎添加關注!文章轉載請注明出處。
發(fā)布評論請先 登錄
RISC-V“安全”那些事兒

Linux系統(tǒng)中通過預留物理內(nèi)存實現(xiàn)ARM與FPGA高效通信的方法

揭秘工控機價格:背后的秘密與門道

Linux內(nèi)核編譯失敗?移動硬盤和虛擬機的那些事兒

永磁電機與充磁的那些事兒
Linux下如何管理虛擬內(nèi)存 使用虛擬內(nèi)存時的常見問題
如何優(yōu)化RAM內(nèi)存使用
Linux內(nèi)存泄露案例分析和內(nèi)存管理分享

Linux內(nèi)存管理中HVO的實現(xiàn)原理

關于IP地址的那些事兒
內(nèi)存管理的硬件結構

linux開發(fā)板與樹莓派的區(qū)別
如何檢測內(nèi)存泄漏
buffers內(nèi)存與cached內(nèi)存的區(qū)別

評論