分配算法描述

总述

image

image

概念

Netty中，PoolChunk实际上就代表了一次申请的内存空间，借助池的设计，达到多次重复使用的目的。一个PoolChunk默认会申请16M大小的内存空间。

page代表chunk中能被分配的最小单元, 那么chunk看起来就像是一个page的集合.

• chunkSize = 2^{maxOrder} * pageSize
  • 这里默认chunksize=16M, maxOrder代表最高层数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通过一个memoryMap将2^11(2048)个page用满二叉树的形式存放, 比如当我们需要申请4M的空间时, 我们直接去(chunkSize/2^2)也就是depth=2从左开始查找第一个还没有被使用的节点.

// memoryMap为2048长的byte数组
memoryMap = new byte[maxSubpageAllocs << 1];
// depthMap为memoryMap的辅助类
depthMap = new byte[memoryMap.length];
// memoryMap下标从1开始
int memoryMapIndex = 1;

// 遍历每层
for (int d = 0; d <= maxOrder; ++ d) { // move down the tree one level at a time
    // 拿到每层的节点数
    int depth = 1 << d;
    // 遍历每个节点
    for (int p = 0; p < depth; ++ p) {
        // in each level traverse left to right and set value to the depth of subtree
        // 在memoryMap和depthMap中保存每个节点的值为当前层数d.
        // depthMap中保存的不可更改, memoryMap中随着内存的分配会变更节点值
        memoryMap[memoryMapIndex] = (byte) d;
        depthMap[memoryMapIndex] = (byte) d;
        memoryMapIndex ++;
    }
}

算法

memoryMap上每个节点的值都默认等于它对应的depth, chunkSize/2^d的节点的值都是d.

• memoryMap[id] = depth_of_id => it is free / unallocated
  • 如果相等, 说明这个节点没有被占用, 可以用来分配
• 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, 至少说明它有子节点被占用或分配, 因为我们不能全部满足, 但是可以部分满足. 比如一个4M的节点之前被分配了2M, 那么还可以对外提供2M的空间申请.
• memoryMap[id] = maxOrder + 1 => the node is fully allocated & thus none of its children can be allocated, it is thus marked as unusable
  • 当节点的值等于maxOrder+1, 也就是12, 说明该节点的空间被全部分配, 没有多余的内存, 那么将被标记为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;
    // 默认为13, 1<<13=8K
    this.pageShifts = pageShifts;
    // memoryMap的最高层数 11
    this.maxOrder = maxOrder;
    // 16M
    this.chunkSize = chunkSize;
    // 设定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;

    // 构造memoryMap+depthMap
    ...
    
    // 创建2048个PoolSubpage与page相对应
    subpages = newSubpageArray(maxSubpageAllocs);
}

分配

allocate

long allocate(int normCapacity) {
    // 仔细观察subpageOverflowMask的值就发现不等于,必然申请的容量要大于或等于pageSize
    if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
        return allocateRun(normCapacity);
    } else {
        // 否则必然小于pagesize, 申请subpage
        return allocateSubpage(normCapacity);
    }
}

allocateRun

private long allocateRun(int normCapacity) {
    // 首先normCapacity必须是经过PoolArena#normalizeCapacity方法进行标准化的
    // 它要满足normCapacity>=pagesiz(8k)且为2的幂
    // 只有满足以上条件,才有可能将层数限制在maxOrder范围内
    // 公式就是求给定的容量应该在哪一层分配
    int d = maxOrder - (log2(normCapacity) - pageShifts);
    // 根据层数去请求可分配的节点
    int id = allocateNode(d);
    if (id < 0) {
        return id;
    }
    // 计算出id节点占用的大小,算出还剩下多少空间
    freeBytes -= runLength(id);
    return id;
}

runLength

private int runLength(int id) {
    // 很好理解, 2^24=16M, 而x层每一个节点的大小为2^(24-depth)
    // 16M=2^(24-0),那么x层的节点大小为2^(24-depth(id)),比如depth=2,算出来2^22=4M
    return 1 << log2ChunkSize - depth(id);
}

allocateNode

img

// 该方法用来查找指定depth的可用节点
private int allocateNode(int d) {
    // 需要注意的是memoryMap的root从1开始
    int id = 1;
    int initial = - (1 << d); // has last d bits = 0 and rest all = 1
    // 拿到节点值
    byte val = value(id);
    if (val > d) { // unusable
        return -1;
    }
    
    // 从根开始查找二叉树
    // 满足id & initial == 1 << d的才是d层的节点
    //      假定d=4,id=17, 17&(-16)=16=1<<4
    // 满足id & initial == 0 则表示所有d层之上的节点
    // 1. 节点值小于d, 说明有充足的空间可以分配, 当然要继续下钻到具体的d层节点
    // 2. 如果大于等于d, 说明空间已经被占用, 如果还没有到d层, 说明, 可能剩下空间可以分配
    while (val < d || (id & initial) == 0) { 
        // 找左节点
        id <<= 1;
        val = value(id);
        // 如果左子树被占用,找右节点,如此往复
        if (val > d) {
            id ^= 1;
            val = value(id);
        }
    }
    byte value = value(id);
    // 满足节点未被占用且位于d层
    assert value == d && (id & initial) == 1 << d : String.format("val = %d, id & initial = %d, d = %d", value, id & initial, d);
    // 标记该节点为unusable
    setValue(id, unusable); // mark as unusable
    updateParentsAlloc(id);
    return id;
}

img

updateParentsAlloc

// 从上面的图示看得更清楚
private void updateParentsAlloc(int id) {
    // 一直从id开始更新到root
    while (id > 1) {
        // 拿到父节点
        int parentId = id >>> 1;
        byte val1 = value(id);
        // 拿到兄弟节点
        byte val2 = value(id ^ 1);
        // 取他们两个较小的节点值,覆盖父节点
        byte val = val1 < val2 ? val1 : val2;
        setValue(parentId, val);
        id = parentId;
    }
}