如果你還對jemalloc分配算法不太了解槐雾，可以查看前情回顧：jemalloc分配算法鸟妙。
1. 伙伴分配算法
JEMalloc分配算法使用伙伴分配算法分配Chunk中的Page節(jié)點寇壳。Netty實現(xiàn)的伙伴分配算法中，構(gòu)造了兩棵滿二叉樹荒揣，滿二叉樹非常適合使用數(shù)組存儲良哲，Netty使用兩個字節(jié)數(shù)組memoryMap和depthMap來表示兩棵二叉樹，其中MemoryMap存放分配信息矗钟，depthMap存放節(jié)點的高度信息唆香。為了更好的理解這兩棵二叉樹，參考下圖：
左圖表示每個節(jié)點的編號吨艇，注意從1開始躬它，省略0是因為這樣更容易計算父子關(guān)系：子節(jié)點加倍，父節(jié)點減半东涡，比如512的子節(jié)點為1024=512 * 2冯吓。右圖表示每個節(jié)點的深度倘待，注意從0開始。在代表二叉樹的數(shù)組中组贺，左圖中節(jié)點上的數(shù)字作為數(shù)組索引即id凸舵，右圖節(jié)點上的數(shù)字作為值。初始狀態(tài)時失尖，
memoryMap和depthMap相等啊奄，可知一個id為512節(jié)點的初始值為9，即：
memoryMap[512] = depthMap[512] = 9;
depthMap的值初始化后不再改變掀潮，memoryMap的值則隨著節(jié)點分配而改變菇夸。當(dāng)一個節(jié)點被分配以后，該節(jié)點的值設(shè)置為12（最大高度+1）表示不可用仪吧，并且會更新祖先節(jié)點的值峻仇。下圖表示隨著4號節(jié)點分配而更新祖先節(jié)點的過程，其中每個節(jié)點的第一個數(shù)字表示節(jié)點編號邑商，第二個數(shù)字表示節(jié)點高度值。
分配過程如下：
- 4號節(jié)點被完全分配凡蚜，將高度值設(shè)置為12表示不可用人断。
- 4號節(jié)點的父親節(jié)點即2號節(jié)點，將高度值更新為兩個子節(jié)點的較小值朝蜘；其他祖先節(jié)點亦然恶迈，直到高度值更新至根節(jié)點。
可推知谱醇，memoryMap數(shù)組的值有如下三種情況：
- memoryMap[id] = depthMap[id] -- 該節(jié)點沒有被分配
- memoryMap[id] > depthMap[id] -- 至少有一個子節(jié)點被分配暇仲，不能再分配該高度滿足的內(nèi)存，但可以根據(jù)實際分配較小一些的內(nèi)存副渴。比如奈附，上圖中分配了4號子節(jié)點的2號節(jié)點，值從1更新為2煮剧，表示該節(jié)點不能再分配8MB的只能最大分配4MB內(nèi)存斥滤，因為分配了4號節(jié)點后只剩下5號節(jié)點可用。
- mempryMap[id] = 最大高度 + 1（本例中12） -- 該節(jié)點及其子節(jié)點已被完全分配勉盅， 沒有剩余空間佑颇。
明白了這些，再深入源碼分析Netty的實現(xiàn)細(xì)節(jié)草娜。
2. 源碼實現(xiàn)
首先看關(guān)鍵成員變量：
private final byte[] memoryMap; // 分配信息二叉樹
private final byte[] depthMap; // 高度信息二叉樹
private final PoolSubpage<T>[] subpages; // subpage節(jié)點數(shù)組
private final int subpageOverflowMask; // 判斷分配請求為Tiny/Small即分配subpage
private final int pageSize; // 頁大小挑胸，默認(rèn)8KB=8192
private final int pageShifts; // 從1開始左移到頁大小的位置，默認(rèn)13宰闰，1<<13 = 8192
private final int maxOrder; // 最大高度茬贵，默認(rèn)11
private final int chunkSize; // chunk塊大小簿透，默認(rèn)16MB
private final int log2ChunkSize; // log2(16MB) = 24
private final int maxSubpageAllocs; // 可分配subpage的最大節(jié)點數(shù)即11層節(jié)點數(shù)，默認(rèn)2048
private final byte unusable; // 標(biāo)記節(jié)點不可用闷沥，最大高度 + 1萎战， 默認(rèn)12
private int freeBytes; // 可分配字節(jié)數(shù)
此外，還有一些非關(guān)鍵成員變量：
final PoolArena<T> arena; // chunk所屬的arena
final T memory; // 實際的內(nèi)存塊
final boolean unpooled; // 是否非池化
final int offset; // ?
PoolChunkList<T> parent; // poolChunkList專用
PoolChunk<T> prev;
PoolChunk<T> next;
該類有兩個構(gòu)造方法舆逃，一個用于普通初始化蚂维，另一個用于非池化初始化（Huge分配請求）。關(guān)注一下對某些值的計算：
unusable = (byte) (maxOrder + 1);
log2ChunkSize = log2(chunkSize);
subpageOverflowMask = ~(pageSize - 1);
freeBytes = chunkSize;
maxSubpageAllocs = 1 << maxOrder;
subpages = new PoolSubpage[maxSubpageAllocs];
在構(gòu)造方法中對兩棵二叉樹的初始化代碼如下：
memoryMap = new byte[maxSubpageAllocs << 1];
depthMap = new byte[memoryMap.length];
int memoryMapIndex = 1;
for (int d = 0; d <= maxOrder; ++ d) {
int depth = 1 << d;
for (int p = 0; p < depth; ++ p) {
memoryMap[memoryMapIndex] = (byte) d; // 設(shè)置高度
depthMap[memoryMapIndex] = (byte) d;
memoryMapIndex ++;
}
}
接下來分析關(guān)鍵的分配方法allocate()：
long allocate(int normCapacity) {
if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize即Normal請求
return allocateRun(normCapacity);
} else { // Tiny和Small請求
return allocateSubpage(normCapacity);
}
}
首先看Normal請求路狮，該請求需要分配至少一個Page的內(nèi)存虫啥，代碼實現(xiàn)如下：
private long allocateRun(int normCapacity) {
// 計算滿足需求的節(jié)點的高度
int d = maxOrder - (log2(normCapacity) - pageShifts);
// 在該高度層找到空閑的節(jié)點
int id = allocateNode(d);
if (id < 0) {
return id; // 沒有找到
}
freeBytes -= runLength(id); // 分配后剩余的字節(jié)數(shù)
return id;
}
在某一層尋找可用節(jié)點的代碼如下：
private int allocateNode(int d) {
int id = 1;
// 所有高度<d 的節(jié)點 id & initial = 0
int initial = - (1 << d);
byte val = value(id); // = memoryMap[id]
if (val > d) { // 沒有滿足需求的節(jié)點
return -1;
}
// val<d 子節(jié)點可滿足需求
// id & initial == 0 高度<d
while (val < d || (id & initial) == 0) {
id <<= 1; // 高度加1，進入子節(jié)點
val = value(id); // = memoryMap[id]
if (val > d) { // 左節(jié)點不滿足
id ^= 1; // 右節(jié)點
val = value(id);
}
}
// 此時val = d
setValue(id, unusable); // 找到符合需求的節(jié)點并標(biāo)記為不可用
updateParentsAlloc(id); // 更新祖先節(jié)點的分配信息
return id;
}
這部分代碼含有大量位運算奄妨，需要仔細(xì)體會其中的用法涂籽。Netty為了追求性能，位運算也是用到了極致砸抛。接著分析更新祖先節(jié)點的分配信息的代碼如下：
private void updateParentsAlloc(int id) {
while (id > 1) {
int parentId = id >>> 1;
byte val1 = value(id); // 父節(jié)點值
byte val2 = value(id ^ 1); // 父節(jié)點的兄弟（左或者右）節(jié)點值
byte val = val1 < val2 ? val1 : val2; // 取較小值
setValue(parentId, val);
id = parentId; // 遞歸更新
}
}
至此评雌，Normal請求的分配過程分析完畢。為了更好的理解分配過程直焙，以一個Page大小為8KB景东，pageShifts=13，maxOrder=11的配置為例分析分配32KB=2^15B內(nèi)存的過程（假設(shè)該Chunk首次分配）：
- 計算滿足所需內(nèi)存的高度d奔誓，d= maxOrder-(log2(normCapacity)-pageShifts) = 11-(log2(2^15)-13) = 9斤吐。可知厨喂，滿足需求的節(jié)點的最大高度d = 9和措。
- 在高度<9的層從左到右尋找滿足需求的節(jié)點。由于二叉樹不便于按層遍歷蜕煌，故需要從根節(jié)點1開始遍歷派阱。本例中，找到id為512的節(jié)點幌绍，滿足需求颁褂，將memory[512]設(shè)置為12表示分配。
- 從512節(jié)點開始傀广，依次更新祖先節(jié)點的分配信息颁独。
接著分析Tiny/Small請求的分配實現(xiàn)allocateSubpage()，代碼如下：
private long allocateSubpage(int normCapacity) {
// 找到arena中對應(yīng)的subpage頭節(jié)點
PoolSubpage<T> head = arena.findSubpagePoolHead(normCapacity);
// 加鎖伪冰，分配過程會修改鏈表結(jié)構(gòu)
synchronized (head) {
int d = maxOrder; // subpage只能在二叉樹的最大高度分配即分配葉子節(jié)點
int id = allocateNode(d);
if (id < 0) {
return id; // 葉子節(jié)點全部分配完畢
}
final PoolSubpage<T>[] subpages = this.subpages;
final int pageSize = this.pageSize;
freeBytes -= pageSize;
// 得到葉子節(jié)點的偏移索引誓酒，從0開始，即2048-0,2049-1,...
int subpageIdx = subpageIdx(id);
PoolSubpage<T> subpage = subpages[subpageIdx];
if (subpage == null) {
subpage = new PoolSubpage<T>(head, this, id,
runOffset(id), pageSize, normCapacity);
subpages[subpageIdx] = subpage;
} else {
subpage.init(head, normCapacity);
}
return subpage.allocate();
}
}
由于Small/Tiny請求分配的內(nèi)存小于PageSize，所以分配的節(jié)點必然在二叉樹的最高層靠柑。找到最高層合適的節(jié)點后寨辩，新建或初始化subpage并加入到chunk的subpages數(shù)組，同時將subpage加入到arena的subpage雙向鏈表中歼冰，最后完成分配請求的內(nèi)存靡狞。代碼中，subpage != null的情況產(chǎn)生的原因是：subpage初始化后分配了內(nèi)存隔嫡，但一段時間后該subpage分配的內(nèi)存釋放并從arena的雙向鏈表中刪除甸怕，此時subpage不為null，當(dāng)再次請求分配時腮恩，只需要調(diào)用init()將其加入到areana的雙向鏈表中即可梢杭。
Netty優(yōu)化計算內(nèi)存相關(guān)數(shù)據(jù)的基本方法， 代碼如下：
// 得到第11層節(jié)點的偏移索引秸滴，= id - 2048
private int subpageIdx(int memoryMapIdx) {
return memoryMapIdx ^ maxSubpageAllocs;
}
// 得到節(jié)點對應(yīng)可分配的字節(jié)武契，1號節(jié)點為16MB-ChunkSize，2048節(jié)點為8KB-PageSize
private int runLength(int id) {
return 1 << log2ChunkSize - depth(id);
}
// 得到節(jié)點在chunk底層的字節(jié)數(shù)組中的偏移量
// 2048-0, 2049-8K荡含，2050-16K
private int runOffset(int id) {
int shift = id ^ 1 << depth(id);
return shift * runLength(id);
}
注意到PoolSubpage分配的最后結(jié)果是一個long整數(shù)咒唆，其中低32位表示二叉樹中的分配的節(jié)點，高32位表示subPage中分配的具體位置释液。相關(guān)的計算如下：
private static int memoryMapIdx(long handle) {
return (int) handle;
}
private static int bitmapIdx(long handle) {
return (int) (handle >>> Integer.SIZE);
}
明白了這些钧排，接著分析內(nèi)存釋放過程，代碼如下：
void free(long handle) {
int memoryMapIdx = memoryMapIdx(handle);
int bitmapIdx = bitmapIdx(handle);
if (bitmapIdx != 0) { // 需要釋放subpage
PoolSubpage<T> subpage = subpages[subpageIdx(memoryMapIdx)];
PoolSubpage<T> head = arena.findSubpagePoolHead(subpage.elemSize);
synchronized (head) {
if (subpage.free(head, bitmapIdx & 0x3FFFFFFF)) {
return; // 此時釋放了subpage中的一部分內(nèi)存（即請求的）
}
// 此時subpage完全釋放均澳，可以刪除二叉樹中的節(jié)點
}
}
freeBytes += runLength(memoryMapIdx);
setValue(memoryMapIdx, depth(memoryMapIdx)); // 節(jié)點分配信息還原為高度值
updateParentsFree(memoryMapIdx); // 更新祖先節(jié)點的分配信息
}
釋放過程相對簡單，釋放時更新祖先節(jié)點的分配信息是分配時的逆過程符衔，代碼如下：
private void updateParentsFree(int id) {
int logChild = depth(id) + 1;
while (id > 1) {
int parentId = id >>> 1;
byte val1 = value(id);
byte val2 = value(id ^ 1);
logChild -= 1;
if (val1 == logChild && val2 == logChild) {
// 此時子節(jié)點均空閑找前，父節(jié)點值高度-1
setValue(parentId, (byte) (logChild - 1));
} else {
// 此時至少有一個子節(jié)點被分配，取最小值
byte val = val1 < val2 ? val1 : val2;
setValue(parentId, val);
}
id = parentId;
}
}
至此判族，PoolChunk分析完畢躺盛。
相關(guān)鏈接：
