ptmalloc：從內存虛擬化說起

前言

本文并不局限于ptmalloc的原理，而是從linux的內存虛擬化和系統調用原理出發，結合各種語言實現，講明內存分配方面的trade off，力圖事無巨細，追根究底。本文內容包括但不限于：NIO原理、0拷貝原理、內存虛擬化、GC和內存分配、PCB結構、mmap原理和場景、JVM內存分配細節、缺頁異常中斷、PTE、物理頁分配、駐留內存、malloc分配原理、ptmalloc的設計和缺陷、mimalloc設計。

什么是glibc和ptmalloc

glibc提供了一組在所有Linux發行版上都可用的標準化函數。包括ISO C standard library、POSIX實現、內存管理等。其中的內存分配函數ptmalloc2被包括C++、JVM（Native Heap）、Python在內廣泛使用。
ptmalloc2遵循malloc函數的慣例：小內存使用brk分配，大內存使用mmap分配。
同時，ptmalloc2也因為它的內存碎片、內存泄漏和線程間鎖爭用問題而廣受詬病，因此谷歌推出了tcmalloc，facebook推出jemalloc，微軟推出mimalloc來取代它。一般在生產環境也建議根據不同的情況選用不同的內存分配庫替換掉glibc的實現。

思考題1：ptmalloc2的問題會對哪些語言造成影響？為什么？

答案：
對C++、JVM（Native Heap）、Python都有影響。但是對JVM影響較小。
要理解這個問題首先要理解JVM的內存分配。
首先我們看JVM的內存劃分：

主流GC的中，GC要么是Partial GC要么是Full GC：

Partial GC：并不收集整個GC堆的模式
- Young GC：只收集young gen的GC
- Old GC：只收集old gen的GC。只有CMS的concurrent collection是這個模式
- Mixed GC：收集整個young gen以及部分old gen的GC。只有G1有這個模式
Full GC：收集整個堆，包括young gen、old gen、perm gen（如果存在的話）等所有部分的模式。

所以內存回收的粒度是比較大的，對于mimalloc并非像C++和Python那么敏感。這個影響跟G1的-XX:MaxGCPAuseMillS參數也有關系。如果這個jvm參數設置的太低的話，就會導致每次G1 回收的內存很少，受到的底層回收算法影響更大。
更多的關于GC的細節，可以參考下面的簡單聊聊GC場景下的內存釋放。
那么什么時候知道glibc對JVM產生了影響呢？通過RSS（進程駐留內存）來看：

內存增長模型

虛擬地址空間由地址總線寬度決定：

64位linux進程虛擬地址空間的內存增長模型如下所示：

思考題2: NIO bytebuffer分配的內存屬于堆內內存還是堆外內存？屬于user space還是kernal space？

答案：既可能是堆內內存也可能是堆外內存，既可能屬于user space也可能屬于kernal space。

虛擬地址空間、brk和mmap

分配小于128k內存時虛擬地址空間的情況

分配內存大于128k時的情況：

brk分配的內存需要等到高地址內存釋放以后才能釋放（例如，在B釋放之前，A是不可能釋放的，這就是內存碎片產生的原因），而mmap分配的內存可以單獨釋放。
mmap函數的作用就是分配/映射一段虛擬地址空間：

這兩種方式分配的都是虛擬內存，沒有分配物理內存。在第一次訪問已分配的虛擬地址空間的時候，發生缺頁中斷，操作系統負責分配物理內存，然后建立虛擬內存和物理內存之間的映射關系（寫時復制）。
mmap能解決那些性能問題？

用戶態到內核態的過程中，內存拷貝問題
內核態把臟數據寫回到塊設備的過程中，內存拷貝的問題
4K對齊問題
零拷貝（實際上是通過映射）問題

通過下面的流程圖可以很直觀的明白mmap的作用：

思考題：

swap space大小影響虛擬空間地址大小嗎？
malloc調用的mmap會設置flags為MAP_ANONYMOUS嗎？也就是說malloc會映射到文件嗎？
mmap什么時候回寫到文件？
mmap在文件映射時導致的臟頁在回寫之后怎么再次標記為臟頁觸發回寫？為什么跟write不一樣？
mmap在文件映射時物理內存+swap spcae不夠怎么辦？
mmap怎么保證文件頁緩存一致性？

答案：

不會
不會

dirty pages的物理頁可以通過address_space 中的Radix樹快速找到并且被pdflush回寫。

struct mm_struct?
struct mm_struct 包含所有與進程相關的內存區域。 The mm field of struct task_struct is a pointer to the struct mm_struct of the current process.
struct vm_area_struct?
A struct vm_area_struct is created at each mmap() call issued from user space. A driver that supports the mmap() operation must complete and initialize the associated struct vm_area_struct. The most important fields of this structure are:

vm_start, vm_end - the beginning and the end of the memory area, respectively (these fields also appear in /proc//maps);
vm_file - the pointer to the associated file structure (if any);
vm_pgoff - the offset of the area within the file;
vm_flags - a set of flags;
vm_ops - a set of working functions for this area
vm_next, vm_prev - the areas of the same process are chained by a list structure

TCB結構圖

回寫的頁會變成寫保護，寫會再次觸發缺頁

PTE中R/W位標志是否寫保護

為什么跟write不一樣？我們先看看write的過程：

根本原因當然是再次寫不能切換到內核態無法修改PTE，只能通過寫保護再次觸發寫時復制缺頁異常，標記為臟頁。

mmap觸發的缺頁異常并不會一次將所有文件內容讀到內存中。

linux將缺頁異常分為幾種情況分別分配內存，包括PTE是否為空，是匿名映射還是文件映射、是讀文件還是寫文件、頁面是否換出、是否滿足COW等等情況。
如果是文件映射導致的缺頁異常，最終的調用是這樣的：

	//如果map_pages函數不為空并且fault_around_bytes有效，//map_pages就是之前講過的預讀的操作函數，fault_around_bytes控制預讀長度，一般64kif (vma->vm_ops->map_pages && fault_around_bytes >> PAGE_SHIFT > 1) {//調用do_fault_around預讀幾個頁的文件內容讀取到vmf->page，為了減少頁錯誤異常的次數ret = do_fault_around(vmf);if (ret)return ret;}

可以通過MADV_SEQUENTIAL來更激進地申請mmap內存，也可以通過MAP_POPULATE直接將文件全部加載到內存中，這也意味著內存會被更快的釋放。

內核態申請的PTE是共享的 PTE中的G位表示是否共享

ptmalloc

memory
應用地址空間，由RAM或swap提供
chunk
可以在應用中分配、在glibc中釋放或與相鄰chunk組合成較大范圍的小范圍內存。請注意，chunk是給定給應用的memory的包裝器。每個chunk存在于一個heap中，屬于一個arena。
heap
memory中的一個連續區域，它被細分為要分配的chunk。每個heap恰好屬于一個arena。
arena
一種在一個或多個線程之間共享的結構，其中包含對一個或更多heap的引用，以及這些heap中“空閑”的chunk的鏈表。分配給每個arena的線程將從該arena的空閑列表（bins）中分配內存。

chunk

使用中的chunk
1、heap中有chunk指針和mem指針 chunk指針指向chunk開始的地址；mem指針指向用戶內存塊開始的地址。
2、 p=0時，表示前一個chunk為空閑，prev_size才有效
3、p=1時，表示前一個chunk正在使用，prev_size無效 p主要用于內存塊的合并操作；ptmalloc 分配的第一個塊總是將p設為1, 以防止程序引用到不存在的區域
4、M=1 為mmap映射區域分配；M=0為heap區域分配
5、 A=0 為主分配區分配；A=1 為非主分配區分配。
空閑的chunk
1、當chunk空閑時，其M狀態是不存在的，只有AP狀態，
２、原本是用戶數據區的地方存儲了四個指針，
指針fd指向后一個空閑的chunk,而bk指向前一個空閑的chunk，malloc通過這兩個指針將大小相近的chunk連成一個雙向鏈表。
在large bin中的空閑chunk，還有兩個指針，fd_nextsize和bk_nextsize，用于加快在large bin中查找最近匹配的空閑chunk。不同的chunk鏈表又是通過bins或者fastbins來組織的。

arenas和heaps

為了有效地處理多線程應用程序，glibc的malloc允許一次活動多個內存區域。因此，不同的線程可以訪問存儲器的不同區域，而不會相互干擾。這些記憶區域統稱為“arena”。有一個主mrena，即“main arena”，對應于應用程序的初始heap。malloc代碼中有一個靜態變量指向這個arena，每個arena都有一個下一個指針來鏈接其他arena。
隨著線程碰撞的壓力增加，glibc通過mmap創建了額外的arena來緩解壓力。arena的數量上限為系統中CPU數量的八倍，這意味著重線程應用程序仍會出現一些爭用，但代價是碎片會減少。
每個arena中都有一個mutex，用于控制對該arena的訪問。一些操作，例如訪問fastbins，可以使用原子操作來完成，并且不需要鎖定arena。所有其他操作都要求線程鎖定arena。對這個mutex的爭用是創建多個arena的原因——分配給不同arena的線程不需要相互等待。如果有爭用，線程將自動切換到未使用（未鎖定）的arenas。
每個arenas都從一個或多個堆中獲得內存。main arenas使用程序的初始堆（從.bss之后開始），可以使用mmap和brk分配內存。其它的arenas只能通過mmap為它們的堆分配內存，每個競技場都會跟蹤一個特殊的“頂部”chunk，這通常是最大的可用chunk，同時指向最近分配的heap。
總結：
1. 主分配區和非主分配區形成一個環形鏈表進行管理。
2. 每一個分配區利用互斥鎖使線程對于該分配區的訪問互斥。
3. 每個進程只有一個主分配區，也可以允許有多個非主分配區。
4. ptmalloc根據系統對分配區的爭用動態增加分配區的大小
5. 主分配區可以使用brk和mmap來分配，而非主分配區只能使用mmap來映射內存塊
6. 申請小內存時會產生很多內存碎片，ptmalloc在整理時也需要對分配區做加鎖操作

bins

為了避免頻繁的系統調用，應用free的內存塊，ptmalloc會根據size和歷史存儲在不同的bins中。

fast bins

fast bins是bins的高速緩沖區，大約有10個定長隊列。每個fast bin都記錄著一條free chunk的單鏈表（稱為binlist ，采用單鏈表是出于fast bin中鏈表中部的chunk不會被摘除的特點），增刪chunk都發生在鏈表的前端。
fastbin中的chunks可以根據需要移動到其他bins中。fast bins 記錄著大小以8字節遞增的bin鏈表。當用戶釋放一塊不大于max_fast（默認值64B）的chunk的時候，會默認會被放到fast bins上。當需要給用戶分配的 chunk 小于或等于 max_fast 時,malloc 首先會到fast bins上尋找是否有合適的chunk，除非特定情況，兩個毗連的空閑chunk并不會被合并成一個空閑chunk。不合并可能會導致碎片化問題，但是卻可以大大加速釋放的過程。

unsorted bins

unsorted bin 的隊列使用 bins 數組的第一個，是bins的一個緩沖區，加快分配的速度。當用戶釋放的內存大于max_fast或者fast bins合并后的chunk都會首先進入unsorted bin上。unsorted bins無尺寸限制，任何大小chunk都可以添加進這里。unsorted bins的設計主要是為了一個最近釋放的復用。
用戶malloc時，如果在 fast bins 中沒有找到合適的 chunk,則malloc 會先在 unsorted bin 中查找合適的空閑 chunk，如果沒有合適的bin，ptmalloc會將unsorted bin上的chunk放入bins上，然后到bins上查找合適的空閑chunk。

small bins

大小小于512字節的chunk被稱為small chunk，而保存small chunks的bin被稱為small bin。數組從2開始編號，前64個bin為small bins，small bin每個bin之間相差8個字節，同一個small bin中的chunk具有相同大小。每個small bin都包括一個空閑區塊的雙向循環鏈表（也稱binlist）。
free掉的chunk添加在鏈表的前端，而所需chunk則從鏈表后端摘除。兩個毗連的空閑chunk會被合并成一個空閑chunk。合并消除了碎片化的影響但是減慢了free的速度。分配時，當samll bin非空后，相應的bin會摘除binlist中最后一個chunk并返回給用戶。在free一個chunk的時候，檢查其前或其后的chunk是否空閑，若是則合并，也即把它們從所屬的鏈表中摘除并合并成一個新的chunk，新chunk會添加在unsorted bin鏈表的前端。

large bins

大小大于等于512字節的chunk被稱為large chunk，而保存large chunks的bin被稱為large bin，位于small bins后面。large bins中的每一個bin分別包含了一個給定范圍內的chunk，其中的chunk按大小遞減排序，大小相同則按照最近使用時間排列。
兩個毗連的空閑chunk會被合并成一個空閑chunk。
分配時，遵循原則“smallest-first , best-fit”,從頂部遍歷到底部以找到一個大小最接近用戶需求的chunk。一旦找到，相應chunk就會分成兩塊User chunk（用戶請求大小）返回給用戶。Remainder chunk（剩余大小添加到unsorted bin。free時和small bin 類似。

三種特殊chunks

有三種特殊chunks不會存儲到bins中：

Top chunk
top chunk相當于分配區的頂部空閑內存，當bins上都不能滿足內存分配要求的時候，就會來top chunk上分配。
當top chunk大小比用戶所請求大小還大的時候，top chunk會分為兩個部分：User chunk（用戶請求大小）和Remainder chunk（剩余大小）。其中Remainder chunk成為新的top chunk。
當top chunk大小小于用戶所請求的大小時，top chunk就通過sbrk（main arena）或mmap（thread arena）系統調用來擴容。
mmaped chunk
當分配的內存非常大（大于分配閥值，默認128K）的時候，需要被mmap映射，則會放到mmaped chunk上，當釋放mmaped chunk上的內存的時候會直接交還給操作系統。
3、Last remainder chunk
當在small bins中找不到合適的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk就會被分裂成兩個chunk，其中一個chunk返回給用戶，另一個chunk變成新的last remainder chunk。

tccache

線程會在thread local中記住用過的main arenas，如果這個arenas被占用，那么就會阻塞等待其釋放。
線程也有自己的cache，被稱為_tcache，這個塊大小受到限制，_分配時不需要使用arenas，而回退時需要使用arenas。

內存分配算法

如果在tcache中有一個合適的（精確匹配）塊，它就會返回給調用者。沒有則嘗試使用來自較大大小的bins的可用塊。
如果請求足夠大，則使用mmap（）直接從操作系統請求內存。請注意，mmap的閾值是動態的，可以通過M_mmap_threshold參數修改，并且同時可以有多少mmap是有限制的。
如果合適的fastbin中有一個chunk，請使用它。如果有其他chunk可用，也可以預填充tcache。
如果適當的smallbin中有一個chunk，請使用它，可能還會在此處預填充tcache。
如果請求“很大”，花點時間把fast bins里的所有東西都拿走，然后把它們移到unsorted bins里，邊走邊合并。
開始從unsorted bins中取出塊，并將它們移到小/大的bins中，邊走邊合并（注意，這是代碼中唯一將塊放入小/大bins的地方）。如果看到一個合適大小的chunk，則使用它。
如果請求是“大”的，則搜索相應的大bin，然后依次搜索更大的bin，直到找到足夠大的chunk。
如果我們在fastbin中仍然有塊（這可能發生在“小”請求中），請合并這些塊并重復前兩個步驟。

內存釋放算法

free()調用并不會真正將內存返還到操作系統，而僅標記為可被應用程序重用。如果top chunk內存足夠大，那么可能會取消映射。

如果tcache中有空間，則將塊存儲在那里并返回。
如果區塊足夠小，請將其放入適當的fast bins中。
如果這個區塊是mmap的，就對它進行munmap。
查看此bins是否與另一個可用bins相鄰，如果相鄰則合并。
將區塊放在unsorted bins中，除非它現在是top trunk。
如果thunk足夠大，合并所有fastbin，然后如果頂部的thunk是否足夠大，將會在os中取消映射。出于性能原因，這一步驟可能會被推遲，并在malloc或其他調用期間發生。

簡單聊聊GC場景下的內存釋放

結合上面文章，主要是考慮GC一次回收的粒度問題。
以目前jdk默認的G1為例。
按照分代收集理論，新生代會比老年代有更頻繁的gc調用。

參考資料

https://ionutbalosin.com/2020/01/hotspot-jvm-performance-tuning-guidelines/
https://man7.org/linux/man-pages/man2/mmap.2.html
https://zhuanlan.zhihu.com/p/166576293
https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf
https://zhuanlan.zhihu.com/p/658307892
https://openjdk.org/groups/hotspot/docs/RuntimeOverview.html#Thread%20Management|outline
https://www.oracle.com/technetwork/java/javase/memorymanagement-whitepaper-150215.pdf
https://tldp.org/LDP/lki/lki-4.html
https://keys961.github.io/2019/04/10/Linux%E5%86%85%E6%A0%B8-%E9%A1%B5%E9%AB%98%E9%80%9F%E7%BC%93%E5%AD%98%E4%B8%8E%E9%A1%B5%E5%9B%9E%E5%86%99/
https://www.kernel.org/doc/gorman/html/understand/understand005.html
https://www.infradead.org/~mchehab/rst_conversion/filesystems/vfs.html