Netty 内存分配之PoolChunk

本文基于Netty 4.1.6.Final版本

在程序运行过程中，内存的申请和回收是非常频繁的操作。所以在这个过程里，如何高效得申请和回收就显得尤为重要，因此衍生出了许多内存管理相关的算法，比如jemalloc、slab等。Netty的内存管理引入了内存池的概念，极大的提高了内存管理的效率。

池可以做到一次申请，多次使用

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

// 使用的就是这块内存
memory = new byte[16M];

如何组织这块内存空间

尽管物理上PoolChunk是一个16M的内存空间，但逻辑上会按照下面的树状结构来维护：

PoolChunk

关于这颗树有几点要说明：

1. PoolChunk会按照层数将16M的内存等分，第零层1个16M，第一层2个8M，第三层4个4M，依次类推直到第十一层，分成了2048个8K；
2. 叶子节点的大小为8K；
3. 为了快速找到节点层数，大小等关系，PoolChunk里维护了两个数组，depthMap维护了节点处在第几层，初始化后不能改变；memoryMap的值和depthMap完全相同，只是后面会改变，表示该节点是否可用；

private final byte[] memoryMap;
private final byte[] depthMap;

depthMap的结构如下，从第1个元素开始，黄色的下标和上面的树一致，数组的元素代表层数，最大为11；memoryMap中可以改变的地方就是这里的值，当一个节点代表的内存被分配了，对应位置的值会改为12，当内存使用完释放的时候，对应的值就会改为初始值(初始值可以在depthMap中查到)；

depthMap & memoryMap

4. PoolChunk中实际上并没有维护存储节点大小的二叉树，而是维护了如上图存储各节点层数的二叉树，分配内存的时候，总是根据需要的内存大小定位到层数，然后在memoryMap中寻找合适的节点；

如何分配内存

比如一个线程先申请3M的内存，接着申请2M，过程如下：

1. 确定内存大小，为了便于管理，对于>=8K的内存，Netty会默认返回2的n次幂的内存大小给申请者，所以Netty会申请4M的内存给调用者；
2. 计算层数：log2(16M) - log2(4M) = 24 - 22 = 2;
3. 根据层数去memoryMap中查找合适的节点，并循环更新上层节点的值，新的值为左右子节点中较小的值；
4. 申请2M的内存，重复2，3步；步骤如下图所示，找到合适的节点后，将该节点的值更新为12；

memoryMap状态变更

其中查找节点的代码如下：

//d就是根据大小计算得出的层数；id就是黄色下标，也是memoryMap的角标
private int allocateNode(int d) {
        int id = 1;
        int initial = - (1 << d); // has last d bits = 0 and rest all = 1
        //根节点的层数，刚开始=0
        byte val = value(id);
        //根节点要么=12，表示被分配了；要么=0
        if (val > d) { // unusable
            return -1;
        }
        // id & initial == 1 << d for all ids at depth d, for < d it is 0
        while (val < d || (id & initial) == 0) { 
            //先判断左节点
            id <<= 1;
            val = value(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);
        //设置当前节点为12，表示已经分配
        setValue(id, unusable); // mark as unusable
        //循环更新父节点直到根节点
        updateParentsAlloc(id);
        return id;
}

以层数的视角说明内存分配的过程不是很清晰，现在以内存大小的视角再走一遍上述分配内存的过程；

内存变化

1. 3M在内部会申请4M的大小，因此找到index=4的节点并标识节点被分配；接着更新父节点大小，index=2的节点本来可以分配8M，现在分配了4M出去，还剩4M；虽然总的还剩下12M可以用并且是连续的，但是由于以2的n次幂分配内存的缘故，该chunk一次最大可申请的内存为8M，故根节点(index=1)置为8M(整个右子树的大小)；如果申请12M的话(实际会申请16M)，则会创建新的chunk，该chunk内存已不够；
2. 申请2M的内存，查找节点定位到index=10的节点并标识节点被分配；接着更新index=5，2，1的节点大小；index=5的节点之前可分配4M，现在只剩2M；index=2的节点也只剩下2M可用，对于左子树而言，实际就只剩下index=11的节点可以分配；index=1还剩8M；

从上述过程可以看出，PoolChunk查找内存块的过程，实际上就是二分查找定位的过程；拿最后一个树的状态再说明一下：
index=1，8M：当前最大能分配8M(已经分配了6M)；
index=2，2M：左半区间最大能分配2M；index=3，8M：右半区间最大分配8M；
index=4: 左半区间的左半区间已分配，余额0M；index=5，2M：左半区间的右半区间还可用2M；

申请的内存小于8K

PoolSubpage负责tiny或small类型内存的分配；

当申请的内存小于8K时，PoolChunk会在叶子节点(8K)中分配。但是这里查找的方式与上面的二分查找不同。PoolChunk会将叶子节点进行划分，划分的方式与申请的内存大小有关，可以分成下面4种：

内存类型	范围	说明
tiny	(0, 512)	-
small	[512, pageSize)	pageSize = 8K
normal	[pageSize, chunkSize]	chunkSize = 16M
huge	(chunkSize, ......)	-

申请的内存属于tiny类型，则会将叶节点按照16byte、32byte、48byte....、496byte中的一种进行划分。比如申请10byte的内存，则会按照16byte均等地划分8K节点并返回16byte给调用者。
申请的内存属于small类型，则会按照512byte、1024byte、2048byte和4096byte中的一种划分。

对应tiny和small类型的内存，并不是按照2的n次幂进行申请，而是按照上述若干固定的大小进行分配。比如申请9byte，实际会申请16byte；申请40byte，实际会申请48byte

在申请normal类型的内存时，使用了memoryMap记录节点的层数位置等信息；均分的page使用了一个bitMap记录分配的位置；比如申请10byte，则会促使一个叶子节点按照16byte进行划分，总共划分了 8K / 16byte = 512个，则bitMap = new long[512 / Long.SIZE] = new long[8];

private final long[] bitmap;

总的来讲，Netty中内存的视图是下面的样子：

总视图

Handle

在分配和释放内存的时候，总会看见一个变量handle。handle用来定位当前正在使用的这段内存的位置(offset)。

handle是一个long型变量，64位，前32位可以定位tiny或small的位置，后32位可以定位memoryMap的一个元素；对于>=8K的内存，其handle的前32位为0。

例子

按照上述的方式，依次申请3M、2M、3M、512Byte、1M的大小，物理内存的实际分布如下，深色的区域为分配出去的内存。

物理内存分布