從零開始實現簡易版Netty(八) MyNetty 實現Small規格的池化內存分配
從零開始實現簡易版Netty(八) MyNetty 實現Small規格的池化內存分配
1. Netty Small規格池化內存分配介紹
在上一篇博客中，lab7版本的MyNetty實現了PooledByteBuf對象的池化以及Normal規格的池化內存管理，并結合jemalloc的論文詳細分析了其背后的設計理念。
按照計劃，lab8版本的MyNetty需要實現Small規格的內存分配。
由于本文屬于系列博客，讀者需要對之前的博客內容有所了解才能更好地理解本文內容。
- lab1版本博客：從零開始實現簡易版Netty(一) MyNetty Reactor模式
- lab2版本博客：從零開始實現簡易版Netty(二) MyNetty pipeline流水線
- lab3版本博客：從零開始實現簡易版Netty(三) MyNetty 高效的數據讀取實現
- lab4版本博客：從零開始實現簡易版Netty(四) MyNetty 高效的數據寫出實現
- lab5版本博客：從零開始實現簡易版Netty(五) MyNetty FastThreadLocal實現
- lab6版本博客：從零開始實現簡易版Netty(六) MyNetty ByteBuf實現
- lab7版本博客：從零開始實現簡易版Netty(七) MyNetty 實現Normal規格的池化內存分配
在lab7的博客中提到，Netty中Normal規格的池化內存分配是參考自操作系統內核的伙伴算法實現的。
通過將內存塊視為一批大小相同的頁，在分配時按照所申請的大小將多個連續的內存頁邏輯上組合成一個內存段以滿足需求，并在回收時盡可能的將此前因為分配而被切割的、彼此直接相鄰的小內存段合并為更大、更完整的內存段。
Small規格的內存分配，使用伙伴算法是否合適？
在開始分析Small規格池化內存分配的實現細節之前，先思考一個問題：對于Small規格的內存分配，繼續延用伙伴算法是否合適？伙伴算法的優缺點是什么呢？
伙伴算法的優缺點
- 優點：以頁為基礎單位進行分配，相比于實際所申請的大小(規范化之前的大小)，對于Normal規格中較小級別的申請所浪費的內部碎片，最多不會超過1頁(比如極端情況實際申請3頁+1b，最終分配4頁)。而對于Normal規格中較大規格的申請(比如2MB+1b)，平均所浪費的內部碎片占所申請的大小比例依然較小。
- 缺點：分配時對連續內存段的拆分以及釋放時對連續內存段的合并操作，邏輯較為復雜，存在一定的時間開銷和鎖同步開銷。同時，runAvail數組等維護信息的元數據占用了一定的空間，產生了一些外部碎片。
使用伙伴算法實現Small規格內存分配的缺點
Normal規格的閾值為28Kb，這意味著在絕大多數應用中針對Small規格的內存申請次數會遠多于Normal規格。
如果使用伙伴算法，以16b這一最小分配級別作為管理單元，在面對高出幾個數量級的分配/回收申請下，對連續內存段的拆分以及合并操作的開銷對吞吐量的影響會被指數級放大。
同時，runAvail數組等元數據也會因為Small規格的大小排布過密，相比Normal規格，所占用的空間也會異常的多。
于此同時，使用伙伴算法實現28KB以下，且大多數都是16b、32b這種極小級別的內存申請，其節約的內部碎片也小的可憐(實際申請17b，最終分配32b，在最極端的情況下最多也就節約15b的內部空間)。
可以發現，如果使用伙伴算法實現Small規格的內存分配，其性能開銷、鎖的同步開銷都大的驚人，同時對于單次分配所節約出來的內部碎片，甚至不足以抵消其對應追蹤元數據所額外占用的空間。
因此Netty參考操作系統內核，針對申請的容量相對更小、申請更加頻繁的Small規格池化內存分配，不使用伙伴算法，而是在Normal規格分配能力的基礎上采用slab算法實現Small規格的池化內存分配管理功能。
2. MyNetty Small規格池化內存分配實現
下面我們開始分析Netty的Small規格池化內存分配的實現原理。
2.1 Slab算法介紹
slab算法是操作系統內核中專門用于小對象內存分配的算法。slab算法最核心的設計思想是內存對象池。
- slab為具有相同大小的內存塊對象預先創建對應的對象池，對象池通常由伙伴算法中所管理的連續內存頁段組成。與伙伴算法中將Chunk切割為一個個相同的頁類似，對象池將底層的連續內存段切割為N個相同大小的對象槽以供分配。
- 當申請對應大小的內存進行分配時，直接將對象池中的某一個槽對應的內存分配出去，并在元數據中將對應的槽從空閑狀態標記為已使用；而在回收內存時，則簡單的將之前所分配出去的對象槽還原為空閑態。
就像一個裝網球的盒子，里面有N個網球整齊的排布，當用戶想要用球時(分配內存)，就從盒子中拿一個分配給用戶，當用戶使用完后(釋放內存)，就放回到之前對應的格子中(不能錯放)。 - 一個對象池能夠緩存的對象數量是有限的，因此用于某一特定大小級別的對象池可以有多個。對象池有三種狀態，完全空閑(裝滿了網球的盒子)，部分空閑(部分網球已被分配的盒子)和已滿(空盒子)。
申請內存分配時，優先從部分空閑狀態的slab對象池中分配；并且在內存吃緊時自動的回收掉完全空閑，無人使用的對象池。隨著slab對象的不斷申請和回收，對象池也會在這幾種狀態中不斷地變化。
相比伙伴算法，slab算法的優缺點同樣明顯。
- 優點：進行內存的分配與釋放時，無需考慮內存塊的拆分與拼接，直接修改對應槽的狀態即可，時間性能非常好，修改元數據時需要防并發處理的臨界區也很小。
因為對象槽的大小與對應的申請的規格完全匹配，不會出現因為空閑內存不連續而導致較大級別內存申請無法分配的問題。 - 缺點：每一種大小級別都需要單獨的創建對象池，在大小級別設置較多的場景中，會創建大量的對象池。
由于對象池是預先分配的設計，在對象池剛被創建，或對象池使用率不高的場景中，預先緩存卻不被實際使用的對象槽會浪費大量的空間。
可以看到，slab算法相比伙伴算法，其時間復雜度更優，但空間復雜度較差。
但slab算法空間復雜度較差的問題，在所緩存對象普遍較小的場景下，問題并不嚴重。因此slab算法作為小對象的內存分配管理算法時，能夠做到揚長避短，只需浪費少量的內存空間，便可非常高效的完成小對象內存的分配與回收。
2.2 Netty Small規格內存分配功能入口
與Normal規格的內存分配的入口一樣，Small規格的內存分配入口同樣是PoolArena的allocate方法，唯一的區別在于所申請的實際大小。在被SizeClasses規范化計算后，如果被判定為是較小的Small規格的內存分配，則會執行tcacheAllocateSmall方法。
- tcacheAllocateSmall使用到了PoolArena中一個關鍵的成員屬性poolSubPages數組。
PoolSubPages數組的大小與SizeClasses中規范化后的Small規格大小的數量相同(默認存在16b，32b，... 24kb，28kb等規格大小，共39項)，每一個Small規格都對應一個PoolSubPage鏈表，該鏈表可以將其看做是對應規格的PoolSubPage的對象池(PoolSubPage是Small規格分配的核心數據結構，在下一節再分析)。 - 在進行分配時，基于規范化后的規格，去PoolSubPages中找到對應的鏈表，檢查其中是否有可用的PoolSubPage。
數組中的PoolSubPage鏈表的頭節點是默認存在的哨兵節點，如果發現head.next==head，則說明鏈表實際是空的，因此需要新創建一個空的PoolSubPage用于分配。
與內核中使用伙伴算法為slab算法分配連續內存段一樣，Netty中也通過Normal規格分配來為Small規格的PoolSubPage分配其底層的連續內存段。
而如果PoolSubPage鏈表不為空，則直接從中取出邏輯頭結點的PoolSubPage(head.next)進行Small規格的分配。 - 用于分配的PoolSubPage在被創建出來后，便會被掛載到對應規格的PoolSubPage鏈表中，當PoolSubPage已滿或者因為內存釋放而完全空閑時，會被從PoolSubPage鏈表中摘除。
特別的，當PoolSubPage鏈表中存在新節點后，后續將至少保證鏈表中至少存在一個可用的PoolSubPage節點，即使該節點是完全空閑狀態也不會被回收掉。具體的細節會在PoolSubPage的分析環節中結合源碼展開講解。
PoolSubPage數組結構圖
public abstract class MyPoolArena<T> {
// ...... 已省略無關邏輯
final MyPooledByteBufAllocator parent;
final MySizeClasses mySizeClasses;
private final MyPoolSubPage<T>[] myPoolSubPages;
private final ReentrantLock lock = new ReentrantLock();
public MyPoolArena(MyPooledByteBufAllocator parent) {
// ......
// 初始化用于small類型分配的SubPage雙向鏈表head節點集合，每一個subPage的規格都會有一個對應的雙向鏈表
// 參考linux內核的slab分配算法，對于小對象來說，區別于伙伴算法的拆分/合并，而是直接將申請的內存大小規范化后，將相同規格的內存塊同一管理起來
// 當需要分配某個規格的小內存時，直接去對應的SubPage鏈表中找到一個可用的分片，直接進行分配
// 不需要和normal那樣在分配時拆分，釋放時合并；雖然會浪費一些內存空間(內部碎片)，但因為只適用于small的小內存分配所以浪費的量很少
// 同時small類型的分配的場景又是遠高于normal的，以空間換時間(大幅提高分配速度，但只浪費了少量的內存)
int nSubPages = this.mySizeClasses.getNSubPage();
this.myPoolSubPages = new MyPoolSubPage[nSubPages];
for(int i=0; i<nSubPages; i++){
MyPoolSubPage<T> myPoolSubPageItem = new MyPoolSubPage<>(i);
// 初始化時，令每一個PoolSubPage的頭結點單獨構成一個雙向鏈表(頭尾指針都指向自己)
myPoolSubPageItem.prev = myPoolSubPageItem;
myPoolSubPageItem.next = myPoolSubPageItem;
this.myPoolSubPages[i] = myPoolSubPageItem;
}
// ......
}
/**
* 從當前PoolArena中申請分配內存，并將其包裝成一個PooledByteBuf返回
* */
MyPooledByteBuf<T> allocate(int reqCapacity, int maxCapacity) {
// 從對象池中獲取緩存的PooledByteBuf對象
MyPooledByteBuf<T> buf = newByteBuf(maxCapacity);
// 為其分配底層數組對應的內存
allocate(buf, reqCapacity);
return buf;
}
private void allocate(MyPooledByteBuf<T> buf, int reqCapacity) {
MySizeClassesMetadataItem sizeClassesMetadataItem = mySizeClasses.size2SizeIdx(reqCapacity);
switch (sizeClassesMetadataItem.getSizeClassEnum()){
case SMALL:
// small規格內存分配
tcacheAllocateSmall(buf, reqCapacity, sizeClassesMetadataItem);
return;
case NORMAL:
// normal規格內存分配
tcacheAllocateNormal(buf, reqCapacity, sizeClassesMetadataItem);
return;
case HUGE:
// 超過了PoolChunk大小的內存分配就是Huge級別的申請，每次分配使用單獨的非池化的新PoolChunk來承載
allocateHuge(buf, reqCapacity);
}
}
private void tcacheAllocateSmall(MyPooledByteBuf<T> buf, final int reqCapacity, final MySizeClassesMetadataItem sizeClassesMetadataItem) {
MyPoolSubPage<T> head = this.myPoolSubPages[sizeClassesMetadataItem.getTableIndex()];
boolean needsNormalAllocation;
head.lock();
try {
final MyPoolSubPage<T> s = head.next;
// 如果head.next = head自己，說明當前規格下可供分配的PoolSubPage內存段不存在，需要新分配一個內存段(needsNormalAllocation=true)
needsNormalAllocation = (s == head);
if (!needsNormalAllocation) {
// 走到這里，head節點下掛載了至少一個可供當前規格分配的使用的PoolSubPage，直接調用其allocate方法進行分配
long handle = s.allocate();
// 分配好，將對應的handle與buf進行綁定
s.chunk.initBufWithSubpage(buf, null, handle, reqCapacity);
}
} finally {
head.unlock();
}
// 需要申請一個新的run來進行small類型的subPage分配
if (needsNormalAllocation) {
lock();
try {
allocateNormal(buf, reqCapacity, sizeClassesMetadataItem);
} finally {
unlock();
}
}
}
MyPoolSubPage<T> findSubpagePoolHead(int sizeIdx) {
return myPoolSubPages[sizeIdx];
}
private void allocateNormal(MyPooledByteBuf<T> buf, int reqCapacity, MySizeClassesMetadataItem sizeIdx) {
// 優先從050的PoolChunkList開始嘗試分配，盡可能的復用已經使用較充分的PoolChunk。如果分配失敗，就嘗試另一個區間內的PoolChunk
// 分配成功則直接return快速返回
if (q050.allocate(buf, reqCapacity, sizeIdx)){
return;
}
if (q025.allocate(buf, reqCapacity, sizeIdx)){
return;
}
if (q000.allocate(buf, reqCapacity, sizeIdx)){
return;
}
if (qInit.allocate(buf, reqCapacity, sizeIdx)){
return;
}
if (q075.allocate(buf, reqCapacity, sizeIdx)){
return;
}
// 所有的PoolChunkList都嘗試過了一遍，都沒能分配成功，說明已經被創建出來的，所有有剩余空間的PoolChunk空間都不夠了(或者最初階段還沒有創建任何一個PoolChunk)
// MyNetty對sizeClass做了簡化，里面的規格都是寫死的，所以直接從sizeClass里取
int pageSize = this.mySizeClasses.getPageSize();
int nPSizes = this.mySizeClasses.getNPageSizes();
int pageShifts = this.mySizeClasses.getPageShifts();
int chunkSize = this.mySizeClasses.getChunkSize();
// 創建一個新的PoolChunk，用來進行本次內存分配
MyPoolChunk<T> c = newChunk(pageSize, nPSizes, pageShifts, chunkSize);
c.allocate(buf, reqCapacity, sizeIdx);
// 新創建的PoolChunk首先加入qInit(可能使用率較高，add方法里會去移動到合適的PoolChunkList中(nextList.add))
qInit.add(c);
}
}
PoolChunk實現Small規格分配
前面提到，在PoolArena中的PoolSubPages數組中嘗試尋找對應規格的可用PoolSubPage時，如果發現當前并沒有可用的PoolSubPage節點，則需要新創建一個PoolSubPage節點。
而新的PoolSubPage節點底層的內存空間，需要由PoolChunk中維護的連續內存段來承載，因此其中許多邏輯都與Normal規格的分配類似，但一些關鍵的不同點需要注意。
- PoolChunk處理PoolSubPage分配的入口同樣是allocate方法，在allocateSubpage方法的實際分配操作前，會通過PoolSubPage頭結點中的lock方法將對應規格的鏈表進行加鎖，避免并發調整相關的元數據結構與鏈表拓撲。
- PoolSubPage既然是使用連續內存段來承載內存空間，那么其大小同樣是以Page頁為單位，是頁大小的整數倍。那么分配時，具體應該分配多大的內存段呢?
jemalloc的論文中提到，內存分配管理中最重要的一點就是盡量減少內存碎片。因此，Netty中為PoolSubPage分配的連續內存頁段大小，取決于頁大小與PoolSubPage對應small規格大小的最小公倍數(calculateRunSize方法)。
一般情況下，small規格的申請會比較多，對應規格的PoolSubPage會被完全用完。這一設計使得在PoolSubPage被完全分配時其底層內存能夠被100%的使用，空間利用率更高，內部碎片更少。 - 在計算出所需的連續內存段大小后，便與Normal規格內存分配一樣，嘗試從當前PoolChunk中切割出一塊符合要求的連續內存段(如果無法分配，則返回-1分配失敗，重新找過一個PoolChunk)。
切割出的連續內存段與新創建的PoolSubPage對象進行綁定，在PoolSubPage的構造方法中，會將自己掛載到到對應規格的雙向鏈表中。隨后，從這個新的PoolSubPage中通過allocate方法分配一個handle以滿足此次Small規格的內存分配。
同時，為了在free釋放該small規格的handle內存段時能快速定位到對應的PoolSubPage，PoolChunk中還維護了一個PoolSubPage數組。在新的PoolSubPage被創建后還會將PoolSubPage存放在其中，數組中存放的位置與PoolSubPage底層內存段在當前PoolChunk中的offset偏移量一致。
/**
* 內存分配chunk
* */
public class MyPoolChunk<T> {
// 。。。 已省略無關邏輯
/**
* manage all subpages in this chunk
*/
private final MyPoolSubPage<T>[] subpages;
/**
* 用于small和normal類型分配的構造函數 unpooled為false，需要池化
* */
public MyPoolChunk(MyPoolArena<T> arena, Object base, T memory, int pageSize, int pageShifts, int chunkSize, int maxPageIdx) {
// PoolSubPage數組，用于管理PoolSubPage
this.subpages = new MyPoolSubPage[totalPages];
// ......
}
boolean allocate(MyPooledByteBuf<T> buf, int reqCapacity, MySizeClassesMetadataItem mySizeClassesMetadataItem) {
long handle;
if (mySizeClassesMetadataItem.getSizeClassEnum() == SizeClassEnum.SMALL) {
// small規格分配
handle = allocateSubpage(mySizeClassesMetadataItem);
if (handle < 0) {
// 如果handle為-1，說明當前的Chunk分配失敗，返回false
return false;
}
} else {
// 除了Small就只可能是Normal，huge的不去池化，進不來
// runSize must be multiple of pageSize(normal類型分配的連續內存段的大小必須是pageSize的整數倍)
int runSize = mySizeClassesMetadataItem.getSize();
handle = allocateRun(runSize);
if (handle < 0) {
// 如果handle為-1，說明當前的Chunk分配失敗，返回false
return false;
}
}
// 分配成功，將這個空的buf對象進行初始化
initBuf(buf,null,handle,reqCapacity);
return true;
}
void initBuf(MyPooledByteBuf<T> buf, ByteBuffer nioBuffer, long handle, int reqCapacity) {
if (isSubpage(handle)) {
initBufWithSubpage(buf, nioBuffer, handle, reqCapacity);
} else {
int maxLength = runSize(pageShifts, handle);
buf.init(this, nioBuffer, handle, runOffset(handle) << pageShifts,
reqCapacity, maxLength);
}
}
void initBufWithSubpage(MyPooledByteBuf<T> buf, ByteBuffer nioBuffer, long handle, int reqCapacity) {
int runOffset = runOffset(handle);
int bitmapIdx = bitmapIdx(handle);
MyPoolSubPage<T> s = subpages[runOffset];
int offset = (runOffset << pageShifts) + bitmapIdx * s.elemSize;
buf.init(this, nioBuffer, handle, offset, reqCapacity, s.elemSize);
}
/**
* Create / initialize a new PoolSubpage of normCapacity. Any PoolSubpage created / initialized here is added to
* subpage pool in the PoolArena that owns this PoolChunk
*/
private long allocateSubpage(MySizeClassesMetadataItem sizeClassesMetadataItem) {
MyPoolSubPage<T> head = arena.findSubpagePoolHead(sizeClassesMetadataItem.getTableIndex());
// 對頭結點上鎖，保證當前規格的small內存分配不會出現并發(鎖的粒度正好)
head.lock();
try {
// 計算出為當前規格small類型內存分配所需要申請的PoolSubPage大小
int runSize = calculateRunSize(sizeClassesMetadataItem);
// 根據計算出的內存段規格，嘗試從該PoolChunk劃分出一塊run內存段出來以供分配
long runHandle = allocateRun(runSize);
if (runHandle < 0) {
// 內存不足，分配不出來對應大小的規格，返回-1代表分配失敗
return -1;
}
int runOffset = runOffset(runHandle);
int elemSize = sizeClassesMetadataItem.getSize();
MyPoolSubPage<T> subpage = new MyPoolSubPage<>(head, this, pageShifts, runOffset,
runSize(pageShifts, runHandle), elemSize);
// 記錄一下用于分配PoolSubPage內存段的偏移量，等釋放內存的時候能根據handle中記錄的offset快速的找到所對應的PoolSubPage
subpages[runOffset] = subpage;
// 分配一個small類型的內存段出去(以handle的形式)
return subpage.allocate();
} finally {
head.unlock();
}
}
/**
* 計算出為當前規格small類型內存分配所需要申請的PoolSubPage大小
* */
private int calculateRunSize(MySizeClassesMetadataItem sizeClassesMetadataItem) {
// 一頁是8K，最小的規格是16b，所以最大的元素個數maxElements為8K/16b
int maxElements = 1 << (pageShifts - MySizeClasses.LOG2_QUANTUM);
int runSize = 0;
int nElements;
final int elemSize = sizeClassesMetadataItem.getSize();
// 獲得pageSize和elemSize的最小公倍數
// 首先，PoolChunk中的run內存段是以Page為單位進行分配的，所以分配出去的PoolSubPage大小一定要是Page的整數倍
// 而pageSize和elemSize的最小公倍數，在其期望上可以減少內部內存碎片。極端情況下可能不是最優策略，但是總體上來說是最節約空間的
// 舉個例子如果整個運行周期就只申請了一次1280字節的規格，那么最小公倍數的策略(8192 * 5 = 40960)就不如直接分配一個1頁大小的節約空間，但這畢竟是極端情況
do {
runSize += pageSize;
nElements = runSize / elemSize;
} while (nElements < maxElements && runSize != nElements * elemSize);
while (nElements > maxElements) {
runSize -= pageSize;
nElements = runSize / elemSize;
}
return runSize;
}
static int bitmapIdx(long handle) {
return (int) handle;
}
}
PoolSubPage解析
無論PoolSubPage鏈表中是否存在可用的PoolSubPage，最終的Small規格內存分配邏輯都落在了PoolSubPage的allocate方法上。可以說，整個Small規格內存分配的最核心的邏輯就集中在PoolSubPage這一專門的數據結構中。
- PoolSubPage作為PoolSubPages數組的鏈表節點，其包含了prev和next兩個引用，用于將自己掛載進PoolArena中poolSubPages數組對應規格的鏈表中。
特別的，head節點獨有的構造方法中為當前節點創建了一個用于防止并發修改鏈表結構的互斥鎖。 - 在2.1中提到，slab算法中會將一個連續內存段切割成N個大小相等的對象槽，并通過為每一個對象槽設置一個標識位來追蹤其使用狀態。通過一堆狀態位來維護元數據，很自然的能想到PoolSubPage中會有一個位圖結構(bitmap)來追蹤每個對象槽的狀態。
但PoolSubPage中的位圖并不是一個boolean數組，而是一個long數組，long是64位的，邏輯上一個long類型的數字可以等價于64個boolean。
使用long而不是boolean來實現位圖的一個優勢是可以充分的利用計算機底層的硬件能力。在64位的機器中，一次cpu的位計算就可以計算出當前long類型中是否存在可用的對象槽(每一個bit位中0標識為空閑，1標識為已分配，全部不可用則long的所有bit位全為1)。
在查找可用插槽時，在PoolSubPage中大多數對象槽均被分配時，比起挨個遍歷每一個bit位，使用long加位運算可以非常快的過濾掉不可用的插槽。即使這樣會讓代碼變得略顯復雜，但換來的卻是性能上的顯著提升。 - 在非哨兵的的普通PoolSubPage中，對象被創建時，便會在構造方法中通過addToPool方法將當前節點作為head哨兵節點的直接后繼插入鏈表。
在allocate方法中，如果當前PoolSubPage的最后一個空閑對象槽被分配掉之后，就無法再繼續分配了，會將自己從當前雙向鏈表中摘除掉(numAvail為0)。
而在free方法中，會將之前已分配的對象槽給釋放，此時如果發現之前PoolSubPage因為numAvail為0而被摘除，則會將自己重新放回到鏈表中。
而如果當前free方法釋放完成后，整個PoolSubPage完全空閑，則會嘗試將整個PoolSubPage回收掉(從鏈表摘除，回收資源觸發gc)，但會保證整個鏈表中至少有一個可用的PoolSubPage，避免在臨界點上反復的創建/銷毀。 - 在allocate方法尋找可用的插槽時，會優先返回最近一次free方法釋放的那個插槽(nextAvail屬性)。因為當前申請與上一次分配的很可能是同一個線程，之前釋放的內存塊很可能還在CPU的高速緩存中，復用這個內存塊用于當前分配能提高CPU緩存的局部性。
而當allocate分配nextAvail為null時(第一次分配，或者上一次分配已經使用了)，則會通過findNextAvail方法從頭開始遍歷整個位圖，以期找到可用的插槽。
正常來說一個long代表64個bit位，因此如果其存在為0的位則認為存在空閑插槽。但一個PoolSubPage所管理的對象槽數量并不總是64的整數倍，因此如果是末尾的long中存在為0的位，并不真的代表其為空閑(可能末尾的0是非法的位數)。因此，還需要完整的遍歷整個long中的所有bit位，只有不越界的0位才是實際能用的空閑插槽。 - PoolSubPage在初始化時，便記錄了當前底層的連續內存段在PoolChunk中的偏移量、大小等，因此在Small類型的分配中，同樣將自己的底層內存作為handle返回，用以標識和關聯當前對象槽。
其中lab7中提到的handle五個屬性中的isSubPage屬性均為1，并且bitmapIdx部分就是所分配對象槽在整個PoolSubPage中位圖的索引值。這樣，在釋放內存時，便可以快速的定位到對應的對象槽，將其狀態標識還原為空閑。
MyNetty PoolSubPage實現源碼
public class MyPoolSubPage<T> {
/**
* 當前PoolSubPage所屬的PoolChunk
* */
final MyPoolChunk<T> chunk;
/**
* 所維護的small類型內存項的大小
* */
final int elemSize;
/**
* 頁大小的log2
* */
private final int pageShifts;
/**
* 當前內存段在PoolChunk中的頁偏移量
* */
private final int runOffset;
/**
* 當前內存段的大小(單位：字節)
* */
private final int runSize;
/**
* 1個long有64位，可以維護64塊small類型的內存塊的使用情況(0為未分配，1為已分配)
* 具體需要多少個這樣的long，取決于elemSize的大小
* */
private final long[] bitmap;
final int headIndex;
private int bitmapLength;
/**
* 是否不需銷毀
* */
boolean doNotDestroy;
/**
* 可以維護的最大內存元素項個數
* */
private int maxNumElems;
/**
* 當前可分配的元素個數
* */
private int numAvail;
/**
* 下一個可用于分配的對象下標
* 最近釋放的small內存塊對應額下標會被設置為nextAvail，期望獲得更好的CPU高速緩存的局部性
* 因為剛釋放后如果同一線程再要求分配同樣規格的buf，可能對應的內存塊已經被映射加載到了高速緩存中，對性能會有所提升
* */
private int nextAvail;
/**
* 雙向鏈表節點
* */
MyPoolSubPage<T> prev;
MyPoolSubPage<T> next;
final ReentrantLock lock;
/**
* PoolArena維護的PoolSubPage鏈表的頭節點(頭節點是哨兵節點，本身不承擔small規格的內存分配)
* */
MyPoolSubPage(int headIndex) {
chunk = null;
lock = new ReentrantLock();
pageShifts = -1;
runOffset = -1;
elemSize = -1;
runSize = -1;
bitmap = null;
bitmapLength = -1;
maxNumElems = 0;
this.headIndex = headIndex;
}
/**
* 創建普通的PoolSubPage對象(實際進行small類型buf的分配)
* */
MyPoolSubPage(MyPoolSubPage<T> head, MyPoolChunk<T> chunk, int pageShifts, int runOffset, int runSize, int elemSize) {
this.headIndex = head.headIndex;
this.chunk = chunk;
this.pageShifts = pageShifts;
this.runOffset = runOffset;
this.runSize = runSize;
this.elemSize = elemSize;
doNotDestroy = true;
// 最大可分配對象數 = 內存段總大小 / 單個內存對象元素大小
maxNumElems = runSize / elemSize;
// 初始化時，當前可分配對象數 = 最大可分配對象數
numAvail = maxNumElems;
// bitMap中維護的是long類型64位，所以bitMap所需要的long元素的數量應該是最大元素數除以64(2^6)
int bitmapLength = maxNumElems >>> 6;
if ((maxNumElems & 63) != 0) {
// 除不盡，則bitMap長度向上取整補足
bitmapLength ++;
}
this.bitmapLength = bitmapLength;
bitmap = new long[bitmapLength];
// 初始化時，從第0號位置開始分配
nextAvail = 0;
lock = null;
// 將當前新的PoolSubPage掛載在對應head節點所在的雙向鏈表中
addToPool(head);
}
/**
* 選擇一個可用的內存塊進行small分配，包裝成handle返回
* @return -1代表分配失敗， 大于0則代表分配成功
*/
long allocate() {
if (numAvail == 0 || !doNotDestroy) {
// 當前SubPage無可分配內存塊，分配失敗返回-1
return -1;
}
final int bitmapIdx = getNextAvail();
int q = bitmapIdx >>> 6; // bitmap中的第幾個long 2^6=64
int r = bitmapIdx & 63; // 對應long中的第幾位，通過對64-1求模
// 將對應位數修正為1，標識為已分配出去
bitmap[q] |= 1L << r;
numAvail--;
if (numAvail == 0) {
// 如果是最后一個空閑位被分配出去了，說明當前PoolSubPage已滿，將當前PoolSubPage從雙向鏈表中摘出去
removeFromPool();
}
// 將當前分配的subPage內存塊轉換成handle返回
return toHandle(bitmapIdx);
}
/**
* 釋放bitmapIdx處所對應的small規格內存
* @return true 當前PoolSubPage依然需要被使用，不需回收
* 當前PoolSubPage已經完全空閑，并且不再需要被使用，需要回收掉
*/
boolean free(MyPoolSubPage<T> head, int bitmapIdx) {
if (elemSize == 0) {
// 特殊case，元素大小為0，不處理
return true;
}
int q = bitmapIdx >>> 6;
int r = bitmapIdx & 63;
// 找到當前bitmapIdx對應的位數，將其標識為0(標識釋放)
bitmap[q] ^= 1L << r;
// 記錄一下nextAvail，提高性能
this.nextAvail = bitmapIdx;
int oldNumAvail = numAvail;
this.numAvail++;
if (oldNumAvail == 0) {
// 如果之前PoolSubPage是滿的（oldNumAvail為0），那么將當前PoolSubPage放回到對應的雙向鏈表中去
addToPool(head);
/* When maxNumElems == 1, the maximum numAvail is also 1.
* Each of these PoolSubpages will go in here when they do free operation.
* If they return true directly from here, then the rest of the code will be unreachable
* and they will not actually be recycled. So return true only on maxNumElems > 1. */
if (maxNumElems > 1) {
// 對于maxNumElems == 1的邏輯不直接返回
return true;
}
}
if (numAvail != maxNumElems) {
// 回收掉當前small規格后，當前PoolSubPage沒有完全空閑
return true;
} else {
// 回收掉當前small規格后，當前PoolSubPage已經完全空閑了，嘗試著將其整個釋放掉以節約內存
if (prev == next) {
// Do not remove if this subpage is the only one left in the pool.
// 如果其是當前雙向鏈表中唯一存在的PoolSubPage(prev == next == head)
// 不進行回收
return true;
}else{
// Remove this subpage from the pool if there are other subpages left in the pool.
// 當前Arena內，還存在可用的PoolSubPage，將當前PoolSubPage銷毀掉以節約內存
doNotDestroy = false;
removeFromPool();
return false;
}
}
}
/**
* handle轉換邏輯和normal類型類似
* */
private long toHandle(int bitmapIdx) {
int pages = runSize >> pageShifts;
return (long) runOffset << MyPoolChunk.RUN_OFFSET_SHIFT
| (long) pages << MyPoolChunk.SIZE_SHIFT
| 1L << MyPoolChunk.IS_USED_SHIFT
| 1L << MyPoolChunk.IS_SUBPAGE_SHIFT
| bitmapIdx;
}
private int getNextAvail() {
// nextAvail >= 0，說明之前恰好有內存塊被回收了，就使用這個內存塊
// 因為剛釋放后如果同一線程再要求分配同樣規格的buf，可能對應的內存塊已經被映射加載到了高速緩存中，對性能會有所提升
int nextAvail = this.nextAvail;
if (nextAvail >= 0) {
// 分配后，將其標識為-1，避免重復分配
this.nextAvail = -1;
return nextAvail;
}
return findNextAvail();
}
private int findNextAvail() {
// 沒有最近被釋放的內存塊，從bitMap中小到大遍歷一遍，直到找到一個可分配的內存塊
final long[] bitmap = this.bitmap;
final int bitmapLength = this.bitmapLength;
for (int i = 0; i < bitmapLength; i ++) {
long bits = bitmap[i];
if (~bits != 0) {
// 當前long類型標識的64位中，存在至少一位為0，標識著大概率有空閑的內存可以分配
// 為什么說是大概率？因為可能最后一位的long，末尾并沒有映射實際的內存塊，就為0了，但這個情況的0不代表可以分配出去
// 所以還要在findNextAvail0里面繼續精確的判斷
return findNextAvail0(i, bits);
}else{
// 整個long所有的位數都是1，全滿，直接返回-1讓上層往bitMap后面的位數里找
}
}
// 遍歷完了，沒有可以空閑的內存塊
return -1;
}
private int findNextAvail0(int i, long bits) {
final int maxNumElems = this.maxNumElems;
final int baseVal = i << 6;
// 遍歷long類型64位中的每一位
for (int j = 0; j < 64; j ++) {
if ((bits & 1) == 0) {
// bits與上1為0，說明最后1位為0
int val = baseVal | j;
if (val < maxNumElems) {
// val小于maxNumElems，說明是合法的空閑位，直接返回
return val;
} else {
// val大于等于maxNumElems，說明已經越界了(bitmap最后一個long不滿補齊的場景)。
// 不合法，無法分配了，break后返回-1
break;
}
}
// 每次循環，推移1位，實現遍歷每一位的邏輯
bits >>>= 1;
}
return -1;
}
/**
* 將當前節點插入到head節點的直接后繼
* */
private void addToPool(MyPoolSubPage<T> head) {
prev = head;
next = head.next;
next.prev = this;
head.next = this;
}
/**
* 將當前節點從PoolSubPage雙向鏈表中刪除
* */
private void removeFromPool() {
prev.next = next;
next.prev = prev;
next = null;
prev = null;
}
void lock() {
lock.lock();
}
void unlock() {
lock.unlock();
}
}
2.3 Netty Small規格內存釋放原理解析
和Normal規格內存釋放一樣，Small規格的內存釋放核心邏輯入口同樣是PoolChunk類的free方法。在free方法中，基于參數handle判斷所要釋放的內存是否是subPage(isSubPage)，如果是則說明是Small規格的內存釋放。
- 首先基于其釋放的內存大小，從PoolArena的PoolSubPages數組中找到對應規格的PoolSubPage鏈表頭節點，通過頭節點中的互斥鎖來防止并發的修改。
加鎖可以保證當前規格的small內存的釋放時修改元數據的安全性，同時同一個PoolArena中不同的small規格分配/釋放互不影響，可以并發處理。
接著解析handle，從handle中提取出所對應的PoolSubPage在當前PoolChunk中的offset偏移量，通過subpages索引直接找到對應的PoolSubPage對象。 - PoolSubPage的free方法進行內存的釋放，釋放時會將bitmap中對應bit位由1(已使用)重置為0(空閑)。
同時還會判斷在本次釋放后當前PoolSubPage是否完全空閑。如果完全空閑，且當前PoolSubPage節點并不是當前鏈表中唯一的空閑節點，則會將自己從鏈表中摘除。 - 如果PoolSubPage的free方法返回false，則說明當前節點已完全空閑，且不再需要被使用，則會將當前PoolSubPage對象給回收掉。
釋放時首先將PoolChunk中的subpage數組中的索引刪除，然后和Normal規格內存釋放一樣，釋放出的內存段將回到PoolChunk中并嘗試合并為更大的連續內存段，以供分配。
總結
- 在本篇博客中，第一節中首先分析了實現Normal規格池化內存分配的伙伴算法的優缺點，然后借此引出slab算法，并介紹使用不同于伙伴算法的slab算法來實現Small規格池化內存的優勢。
而在第二節中則結合MyNetty的Small規格池化內存實現的源碼，分析了PoolArena、PoolChunk中實現Small規格池化內存的相關邏輯，同時重點分析了PoolSubPage這一核心數據結構的內部實現。 - 相比于lab7，lab8中Small規格的池化內存分配功能并不算復雜，因為Small規格內存分配中有大量與Normal規格內存分配復用的邏輯。按照計劃在lab9中MyNetty將實現線程本地緩存的功能，從而實現完整的池化內存管理功能。
可以發現，雖然Netty的池化內存分配功能非常復雜，設計到的組件非常多，但只要有機的將其拆分成幾個高內聚的模塊逐個分析，便能夠大幅降低理解的困難程度。
博客中展示的完整代碼在我的github上：https://github.com/1399852153/MyNetty (release/lab8_small_allocate 分支)，內容如有錯誤，還請多多指教。
浙公網安備 33010602011771號