分配算法描述

總述

image

image

概念

Netty中，PoolChunk實(shí)際上就代表了一次申請(qǐng)的內(nèi)存空間，借助池的設(shè)計(jì)，達(dá)到多次重復(fù)使用的目的。一個(gè)PoolChunk默認(rèn)會(huì)申請(qǐng)16M大小的內(nèi)存空間。

page代表chunk中能被分配的最小單元, 那么chunk看起來(lái)就像是一個(gè)page的集合.

• chunkSize = 2^{maxOrder} * pageSize
  • 這里默認(rèn)chunksize=16M, maxOrder代表最高層數(shù)11, 那么pagesize=16M/2^11=8192=8K

memoryMap

image

* The tree looks like this (the size of each node being mentioned in the parenthesis)
*
* depth=0        1 node (chunkSize)
* depth=1        2 nodes (chunkSize/2)
* ..
* ..
* depth=d        2^d nodes (chunkSize/2^d)
* ..
* depth=maxOrder 2^maxOrder nodes (chunkSize/2^{maxOrder} = pageSize)
*
* depth=maxOrder is the last level and the leafs consist of pages

可以看到Netty通過(guò)一個(gè)memoryMap將2^11(2048)個(gè)page用滿二叉樹(shù)的形式存放, 比如當(dāng)我們需要申請(qǐng)4M的空間時(shí), 我們直接去(chunkSize/2^2)也就是depth=2從左開(kāi)始查找第一個(gè)還沒(méi)有被使用的節(jié)點(diǎn).

// memoryMap為2048長(zhǎng)的byte數(shù)組
memoryMap = new byte[maxSubpageAllocs << 1];
// depthMap為memoryMap的輔助類
depthMap = new byte[memoryMap.length];
// memoryMap下標(biāo)從1開(kāi)始
int memoryMapIndex = 1;

// 遍歷每層
for (int d = 0; d <= maxOrder; ++ d) { // move down the tree one level at a time
    // 拿到每層的節(jié)點(diǎn)數(shù)
    int depth = 1 << d;
    // 遍歷每個(gè)節(jié)點(diǎn)
    for (int p = 0; p < depth; ++ p) {
        // in each level traverse left to right and set value to the depth of subtree
        // 在memoryMap和depthMap中保存每個(gè)節(jié)點(diǎn)的值為當(dāng)前層數(shù)d.
        // depthMap中保存的不可更改, memoryMap中隨著內(nèi)存的分配會(huì)變更節(jié)點(diǎn)值
        memoryMap[memoryMapIndex] = (byte) d;
        depthMap[memoryMapIndex] = (byte) d;
        memoryMapIndex ++;
    }
}

算法

memoryMap上每個(gè)節(jié)點(diǎn)的值都默認(rèn)等于它對(duì)應(yīng)的depth, chunkSize/2^d的節(jié)點(diǎn)的值都是d.

• memoryMap[id] = depth_of_id => it is free / unallocated
  • 如果相等, 說(shuō)明這個(gè)節(jié)點(diǎn)沒(méi)有被占用, 可以用來(lái)分配
• memoryMap[id] > depth_of_id => at least one of its child nodes is allocated, so we cannot allocate it, but some of its children can still be allocated based on their availability
  • 如果大于depth, 至少說(shuō)明它有子節(jié)點(diǎn)被占用或分配, 因?yàn)槲覀儾荒苋繚M足, 但是可以部分滿足. 比如一個(gè)4M的節(jié)點(diǎn)之前被分配了2M, 那么還可以對(duì)外提供2M的空間申請(qǐng).
• memoryMap[id] = maxOrder + 1 => the node is fully allocated & thus none of its children can be allocated, it is thus marked as unusable
  • 當(dāng)節(jié)點(diǎn)的值等于maxOrder+1, 也就是12, 說(shuō)明該節(jié)點(diǎn)的空間被全部分配, 沒(méi)有多余的內(nèi)存, 那么將被標(biāo)記為unusable

PoolChunk

PoolChunk(PoolArena<T> arena, T memory, int pageSize, int maxOrder, int pageShifts, int chunkSize) {
    unpooled = false;
    this.arena = arena;
    this.memory = memory;
    this.pageSize = pageSize;
    // 默認(rèn)為13, 1<<13=8K
    this.pageShifts = pageShifts;
    // memoryMap的最高層數(shù) 11
    this.maxOrder = maxOrder;
    // 16M
    this.chunkSize = chunkSize;
    // 設(shè)定12為unusable
    unusable = (byte) (maxOrder + 1);
    // log2(16M)=24
    log2ChunkSize = log2(chunkSize);
    // 11111111111111111110000000000000
    subpageOverflowMask = ~(pageSize - 1);
    // 初始有16M等待分配
    freeBytes = chunkSize;

    assert maxOrder < 30 : "maxOrder should be < 30, but is: " + maxOrder;
    // 能分配的最大的page大小為 1<<11 2048
    maxSubpageAllocs = 1 << maxOrder;

    // 構(gòu)造memoryMap+depthMap
    ...
    
    // 創(chuàng)建2048個(gè)PoolSubpage與page相對(duì)應(yīng)
    subpages = newSubpageArray(maxSubpageAllocs);
}

分配

allocate

long allocate(int normCapacity) {
    // 仔細(xì)觀察subpageOverflowMask的值就發(fā)現(xiàn)不等于,必然申請(qǐng)的容量要大于或等于pageSize
    if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
        return allocateRun(normCapacity);
    } else {
        // 否則必然小于pagesize, 申請(qǐng)subpage
        return allocateSubpage(normCapacity);
    }
}

allocateRun

private long allocateRun(int normCapacity) {
    // 首先normCapacity必須是經(jīng)過(guò)PoolArena#normalizeCapacity方法進(jìn)行標(biāo)準(zhǔn)化的
    // 它要滿足normCapacity>=pagesiz(8k)且為2的冪
    // 只有滿足以上條件,才有可能將層數(shù)限制在maxOrder范圍內(nèi)
    // 公式就是求給定的容量應(yīng)該在哪一層分配
    int d = maxOrder - (log2(normCapacity) - pageShifts);
    // 根據(jù)層數(shù)去請(qǐng)求可分配的節(jié)點(diǎn)
    int id = allocateNode(d);
    if (id < 0) {
        return id;
    }
    // 計(jì)算出id節(jié)點(diǎn)占用的大小,算出還剩下多少空間
    freeBytes -= runLength(id);
    return id;
}

runLength

private int runLength(int id) {
    // 很好理解, 2^24=16M, 而x層每一個(gè)節(jié)點(diǎn)的大小為2^(24-depth)
    // 16M=2^(24-0),那么x層的節(jié)點(diǎn)大小為2^(24-depth(id)),比如depth=2,算出來(lái)2^22=4M
    return 1 << log2ChunkSize - depth(id);
}

allocateNode

img

// 該方法用來(lái)查找指定depth的可用節(jié)點(diǎn)
private int allocateNode(int d) {
    // 需要注意的是memoryMap的root從1開(kāi)始
    int id = 1;
    int initial = - (1 << d); // has last d bits = 0 and rest all = 1
    // 拿到節(jié)點(diǎn)值
    byte val = value(id);
    if (val > d) { // unusable
        return -1;
    }
    
    // 從根開(kāi)始查找二叉樹(shù)
    // 滿足id & initial == 1 << d的才是d層的節(jié)點(diǎn)
    //      假定d=4,id=17, 17&(-16)=16=1<<4
    // 滿足id & initial == 0 則表示所有d層之上的節(jié)點(diǎn)
    // 1. 節(jié)點(diǎn)值小于d, 說(shuō)明有充足的空間可以分配, 當(dāng)然要繼續(xù)下鉆到具體的d層節(jié)點(diǎn)
    // 2. 如果大于等于d, 說(shuō)明空間已經(jīng)被占用, 如果還沒(méi)有到d層, 說(shuō)明, 可能剩下空間可以分配
    while (val < d || (id & initial) == 0) { 
        // 找左節(jié)點(diǎn)
        id <<= 1;
        val = value(id);
        // 如果左子樹(shù)被占用,找右節(jié)點(diǎn),如此往復(fù)
        if (val > d) {
            id ^= 1;
            val = value(id);
        }
    }
    byte value = value(id);
    // 滿足節(jié)點(diǎn)未被占用且位于d層
    assert value == d && (id & initial) == 1 << d : String.format("val = %d, id & initial = %d, d = %d", value, id & initial, d);
    // 標(biāo)記該節(jié)點(diǎn)為unusable
    setValue(id, unusable); // mark as unusable
    updateParentsAlloc(id);
    return id;
}

img

updateParentsAlloc

// 從上面的圖示看得更清楚
private void updateParentsAlloc(int id) {
    // 一直從id開(kāi)始更新到root
    while (id > 1) {
        // 拿到父節(jié)點(diǎn)
        int parentId = id >>> 1;
        byte val1 = value(id);
        // 拿到兄弟節(jié)點(diǎn)
        byte val2 = value(id ^ 1);
        // 取他們兩個(gè)較小的節(jié)點(diǎn)值,覆蓋父節(jié)點(diǎn)
        byte val = val1 < val2 ? val1 : val2;
        setValue(parentId, val);
        id = parentId;
    }
}