Netty分享之内存竞技场(二)

gris 转载请注明原创出处，谢谢！

上篇文章中我们已经大概了解了PoolChunk分配内存的原理和过程，并且知道了以下几个重要的结论：

• PoolChunk中有两种内存单元：page和chunk
• 一个page默认大小8K，一个chunk默认有2048个page
• chunk中的page通过一个叫memoryMap的数组以完全二叉树的形式进行管理
• 完全二叉树总共有4096个节点
• 深度越深，节点越多，但是节点的容量越小
• 一个父节点的容量等于两个子节点的容量
• 当一个节点被分配出去了，该节点的深度要被设置为unusable
• 递归更新被分配出去节点的父节点的深度

下面让我们了解下具体的代码实现吧，最终的内存分配就是调用的allocate方法，该方法实现如下：

long allocate(int normCapacity) {
    // 如果normCapacity大于pageSize，则说明一个SubPage无法分配，
    // 需要至少两个连续的SubPage来分配，通过allocateRun方法进行分配
    if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
        return allocateRun(normCapacity);
    // 一个SubPage就可以满足容量需求，通过allocateSubpage进行分配
    } else {
        return allocateSubpage(normCapacity);
    }
}

上一篇文章中说过，为了方便内存的分配，请求的内存大小是经过统一的normalizeCapacity方法处理过的，就是说参数normCapacity的容量总是小于pageSize或者是pageSize的整数倍。如果normCapacity小于pageSize则会在PoolArena中进行分配(但是会先在PoolThreadCache中尝试分配)，否则会创建一个新的PoolChunk，然后由PoolChunk负责分配。

当normCapacity大于等于pageSize时，就调用allocateRun方法进行分配，否则调用allocateSubpage进行分配。allocateRun会分配至少一个page的内存，而allocateSubpage则只会分配一个page的内存，因此subpage只会从叶子节点上进行分配。

让我们看下allocateRun的方法，方法的注释上标注了：Allocate a run of pages (>=1)，表示该方法用来分配一个连续的pages，至少一个page。代码如下：

/**
 * Allocate a run of pages (>=1)
 * 分配一个连续的pages，至少一个page
 * @param normCapacity normalized capacity
 * @return index in memoryMap
 */
private long allocateRun(int normCapacity) {
    System.out.println("allocateRun normCapacity="+normCapacity);
    // 根据容量normCapacity得到该容量的节点应该在树的第几层，计算得到d
    int d = maxOrder - (log2(normCapacity) - pageShifts);
    // 遍历节点，得到满足条件的节点，并返回该节点的id，即在memoryMap数组中的下标
    int id = allocateNode(d);
    if (id < 0) {
        return id;
    }
    freeBytes -= runLength(id);
    return id;
}

首先根据容量normCapacity得到该节点应该在树中所属的深度d，然后遍历节点，找到一个深度为d的节点，并返回该节点的id，具体的遍历方法在allocateNode中，看下源代码：

private int allocateNode(int d) {
    // 从树的第一个节点开始遍历
    int id = 1;
    int initial = - (1 << d); // has last d bits = 0 and rest all = 1
    // 计算节点的深度
    byte val = value(id);
    // 如果根节点的深度大于d，则说明根节点也无法分配，直接返回
    if (val > d) { // unusable
        return -1;
    }
    // 如果当前节点的深度小于d，则从树的下一层开始匹配，直到找到深度和d相等的那一层
    while (val < d || (id & initial) == 0) { // id & initial == 1 << d for all ids at depth d, for < d it is 0
        // 从树的下一层开始匹配 id = id*2
        id <<= 1;
        val = value(id);
        // 如果当前节点的深度大于d，则说明当前节点有子节点被分配了，则从id的兄弟节点进行匹配
        if (val > d) {
            // 从当前节点右边的兄弟节点开始匹配
            id ^= 1;
            val = value(id);
        }
    }
    byte value = value(id);
    assert value == d && (id & initial) == 1 << d : String.format("val = %d, id & initial = %d, d = %d",value, id & initial, d);
    // 将当前节点id标记为不可用，防止其他线程分配
    setValue(id, unusable); // mark as unusable
    // 更新当前节点的父节点
    updateParentsAlloc(id);
    return id;
}

1、首先从树的第一个节点开始查找，如果节点的深度大于d，则说明没有符合该深度的节点了

2、否则如果节点的深度小于d，则说明该节点还有子节点可以被用来进行分配

3、从该节点的子节点开始匹配

4、如果当前节点的深度大于d，则说明该节点有子节点已经被分配了，则从兄弟节点进行匹配

5、如果找到一个节点的深度等于d，则说明该节点符合要求可以进行分配，那么将该节点标记为unusable，防止下次再被分配，并递归更新当前节点的父节点的深度

可能以上的代码理解起来比较枯燥，那我们可以通过一个具体的例子来进行分析，在分配的方法里面打印一些信息来帮助我们理解。如下面的代码，我们将申请三个ByteBuf，内存容量各不相同：

public static void pooled(){
    // 1 page
    ByteBuf buf1 = PooledByteBufAllocator.DEFAULT.heapBuffer(1025);
    // 2 pages
    ByteBuf buf2 = PooledByteBufAllocator.DEFAULT.heapBuffer(10024);
    // 2 pages
    ByteBuf buf3 = PooledByteBufAllocator.DEFAULT.heapBuffer(10035);
}

从之前的文章中我们可以知道，申请1025byte的容量需要分配1个page，而申请10024和10035都需要分配2个pages，因为他们的容量都超过了pageSize(8192)。为了更清楚的了解节点的查找匹配过程，让我们在allocateNode方法中打印一些信息来帮助我们定位，具体如下：

private int allocateNode(int d) {
    System.out.println("try to find node with depth="+d+"\n-------------------------------");
    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;
    }
    while (val < d || (id & initial) == 0) { // id & initial == 1 << d for all ids at depth d, for < d it is 0
        id <<= 1;
        val = value(id);
        System.out.println("check node id="+id+",depth="+val);
        if (val > d) {
            id ^= 1;
            val = value(id);
            System.out.println("check brother node id="+id+",depth="+val);
        }
    }
    byte value = value(id);
    assert value == d && (id & initial) == 1 << d : String.format("val = %d, id & initial = %d, d = %d",
            value, id & initial, d);
    System.out.println("-------------------------------\nmatch node it="+id+",depth="+value+"\n-------------------------------");
    setValue(id, unusable); // mark as unusable
    updateParentsAlloc(id);
    return id;
}

然后让我们执行刚刚的三个ByteBuf分配的代码，执行后将打印出以下内容：

allocateSubpage normCapacity=2048
try to find node with depth=11
-------------------------------
check node id=2,depth=1
check node id=4,depth=2
check node id=8,depth=3
check node id=16,depth=4
check node id=32,depth=5
check node id=64,depth=6
check node id=128,depth=7
check node id=256,depth=8
check node id=512,depth=9
check node id=1024,depth=10
check node id=2048,depth=11
-------------------------------
match node it=2048,depth=11
-------------------------------
allocateRun normCapacity=16384
try to find node with depth=10
-------------------------------
check node id=2,depth=2
check node id=4,depth=3
check node id=8,depth=4
check node id=16,depth=5
check node id=32,depth=6
check node id=64,depth=7
check node id=128,depth=8
check node id=256,depth=9
check node id=512,depth=10
check node id=1024,depth=11
check brother node id=1025,depth=10
-------------------------------
match node it=1025,depth=10
-------------------------------
allocateRun normCapacity=16384
try to find node with depth=10
-------------------------------
check node id=2,depth=2
check node id=4,depth=3
check node id=8,depth=4
check node id=16,depth=5
check node id=32,depth=6
check node id=64,depth=7
check node id=128,depth=8
check node id=256,depth=9
check node id=512,depth=11
check brother node id=513,depth=9
check node id=1026,depth=10
-------------------------------
match node it=1026,depth=10
-------------------------------

申请的第一个ByteBuf大小为1025，超过了1024但是小于8192，所以实际分配的内存为2048。而2048的容量只需要分配一个page就够了，因此从二叉树中从第一个节点，往下一层一层的查找，找到第11层的第2048个节点就正好符合该内存申请的条件，于是将该节点分配出去，并将2048节点标记为不可用(实际的做法就是将2048节点的深度设置为12)，然后将2048的所有父节点的深度更新。比如1024节点的深度从原来的10更新为11，因为1024节点的其中一个子节点2048已经被分配出去了，所以1024节点的深度应该和2049节点的深度保持一致。以此类推，512节点的深度由原来的9更新为10，一直更新到节点2为止。

当申请容量为10024的节点时，按照之前的规律，需要分配2个page。也就是需要找到一个深度为10的节点才能进行分配。仍然从第一个节点开始往下一层一层的查找，当找到512节点时发现(id & initial) == 0，也就是说512节点还是不是最终要找的节点，仍然可以往下一层进行查找。往下一层之后发现1024节点的深度为11，大于要找的深度10，所以找1024的兄弟节点1025，结果发现1025节点的深度正好是10，那么1025节点就是我们所要找的节点了。将1025节点返回，然后将他标记为不可用，并递归更新1025节点的父节点。

第三个ByteBuf对象内存的申请也跟上面两个申请的过程一样，这里就不再详细说明了。

至此PoolChunk对于节点的分配过程我们应该有了一个比较深入的了解了，下一篇文章让我们深入的了解当申请的内存小于一个page的时候，是如何进行分配的，这涉及到了PoolSubpage和PoolThreadCache类。

我是逅弈，如果文章对您有帮助，欢迎您点赞加关注，并欢迎您关注我的公众号：

欢迎关注微信公众号