Netty源码解析 -- PoolChunk实现原理(jemalloc 3的算法)

前面文章已经分享了Netty如何引用jemalloc 4算法管理内存。
本文主要分享Netty 4.1.52之前版本中,PoolChunk如何使用jemalloc 3算法管理内存。
感兴趣的同学可以对比两种算法。
源码分析基于Netty 4.1.29

首先说明PoolChunk内存组织方式。
PoolChunk的内存大小默认是16M,它将内存组织成为一颗完美二叉树。
二叉树的每一层每个节点所代表的内存大小都是均等的,并且每一层节点所代表的内存大小总和加起来都是16M。
每一层节点可分配内存是父节点的1/2。整颗二叉树的总层数为12,层数从0开始。

示意图如下

先看一下PoolChunk的构造函数

PoolChunk(PoolArena arena, T memory, int pageSize, int maxOrder, int pageShifts, int chunkSize, int offset) {
    unpooled = false;
    this.arena = arena;
    this.memory = memory;
    this.pageSize = pageSize;
    this.pageShifts = pageShifts;
    this.maxOrder = maxOrder;
    this.chunkSize = chunkSize;
    this.offset = offset;
    unusable = (byte) (maxOrder + 1);
    log2ChunkSize = log2(chunkSize);
    subpageOverflowMask = ~(pageSize - 1);
    freeBytes = chunkSize;

    assert maxOrder < 30 : "maxOrder should be < 30, but is: " + maxOrder;
    maxSubpageAllocs = 1 << maxOrder;

    // Generate the memory map.
    memoryMap = new byte[maxSubpageAllocs << 1];
    depthMap = new byte[memoryMap.length];
    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[memoryMapIndex] = (byte) d;
            depthMap[memoryMapIndex] = (byte) d;
            memoryMapIndex ++;
        }
    }

    subpages = newSubpageArray(maxSubpageAllocs);
}

unpooled: 是否使用内存池
arena:该PoolChunk所属的PoolArena
memory:底层的内存块,对于堆内存,它是一个byte数组,对于直接内存,它是(jvm)ByteBuffer,但无论是哪种形式,其内存大小默认都是16M。
pageSize:叶子节点大小,默认为8192,即8K。
maxOrder:表示二叉树最大的层数,从0开始。默认为11。
chunkSize:整个PoolChunk的内存大小,默认为16777216,即16M。
offset:底层内存对齐偏移量,默认为0。
unusable:表示节点已被分配,不用了,默认为12。
freeBytes:空闲内存字节数。
每个PoolChunk都要按内存使用率关联到一个PoolChunkList上,内存使用率正是通过freeBytes计算。
maxSubpageAllocs:叶子节点数量,默认为2048,即2^11。

log2ChunkSize:用于计算偏移量,默认为24。
subpageOverflowMask:用于判断申请内存是否为PoolSubpage,默认为-8192。
pageShifts:用于计算分配内存所在二叉树层数,默认为13。

memoryMap:初始化内存管理二叉树,将每一层节点值设置为层数d。
使用数组维护二叉树,第d层的开始下标为 1<。(数组第0个元素不使用)。
depthMap:保存二叉树的层数,用于通过位置下标找到其在整棵树中对应的层数。
注意:depthMap的值代表二叉树的层数,初始化后不再变化。
memoryMap的值代表当前节点最大可申请内存块,在分配内存过程中不断变化。
节点最大可申请内存块可以通过层数d计算,为2 ^ (pageShifts + maxOrder - d)

PoolChunk#allocate

long allocate(int normCapacity) {
    if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
        return allocateRun(normCapacity);
    } else {
        return allocateSubpage(normCapacity);
    }
}

若申请内存大于pageSize,调用allocateRun方法分配Chunk级别的内存。
否则调用allocateSubpage方法分配PoolSubpage,再在PoolSubpage上分配所需内存。

PoolChunk#allocateRun

private long allocateRun(int normCapacity) {
    // #1
    int d = maxOrder - (log2(normCapacity) - pageShifts);
    // #2
    int id = allocateNode(d);
    if (id < 0) {
        return id;
    }
    // #2
    freeBytes -= runLength(id);
    return id;
}

#1 计算应该在哪层分配分配内存
maxOrder - (log2(normCapacity) - pageShifts),如16K, 即2^14,计算结果为10,即在10层分配。
#2 减少空闲内存字节数。

PoolChunk#allocateNode,在d层分配一个节点

private int allocateNode(int d) {
    int id = 1;
    int initial = - (1 << d); // has last d bits = 0 and rest all = 1
    // #1
    byte val = value(id);
    if (val > d) { // unusable
        return -1;
    }
    // #2
    while (val < d || (id & initial) == 0) { // id & initial == 1 << d for all ids at depth d, for < d it is 0
        // #3
        id <<= 1;
        val = value(id);
        // #4
        if (val > d) {
            // #5
            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);
    // #6
    setValue(id, unusable); // mark as unusable
    // #7
    updateParentsAlloc(id);
    return id;
}

#1 memoryMap[1] > d,第0层的可分配内存不足,表明该PoolChunk内存不能满足分配,分配失败。
#2 遍历二叉树,找到满足内存分配的节点。
val < d,即该节点内存满足分配。
id & initial = 0,即 id < 1<, d层之前循环继续执行。这里并不会出现val > d的场景,但会出现val == d的场景,如
PoolChunk当前可分配内存为2M,即memoryMap[1] = 3,这时申请2M内存,在0-2层,都是val == d。可参考后面的实例。
#3 向下找到下一层下标,注意,子树左节点的下标是父节点下标的2倍。
#4 val > d,表示当前节点不能满足分配
#5 id ^= 1,查找同一父节点下的兄弟节点,在兄弟节点上分配内存。
id ^= 1,当id为偶数,即为id+=1, 当id为奇数,即为id-=1
由于前面通过id <<= 1找到下一层下标都是偶数,这里等于id+=1。
#6
因为一开始判断了PoolChunk内存是否足以分配,所以这里一定可以找到一个可分配节点。
这里标注找到的节点已分配。
#7 更新找到节点的父节点最大可分配内存块大小

private void updateParentsAlloc(int id) {
    // #1
    while (id > 1) {
        // #2
        int parentId = id >>> 1;
        byte val1 = value(id);
        byte val2 = value(id ^ 1);
        byte val = val1 < val2 ? val1 : val2;
        setValue(parentId, val);
        id = parentId;
    }
}

#1 向父节点遍历,直到根节点
#2 id >>> 1,找到父节点
取当前节点和兄弟节点中较小值,作为父节点的值,表示父节点最大可分配内存块大小。

如memoryMap[1] = 0,表示最大可分配内存块为16M。
分配8M后,memoryMap[1] = 1,表示当前最大可分配内存块为8M。

下面看一则实例,大家可以结合实例理解上面的代码

内存释放

PoolChunk#free

void free(long handle) {
    // #1
    int memoryMapIdx = memoryMapIdx(handle);
    int bitmapIdx = bitmapIdx(handle);
    // #2
    if (bitmapIdx != 0) { // free a subpage
        ...
    }
    freeBytes += runLength(memoryMapIdx);
    setValue(memoryMapIdx, depth(memoryMapIdx));
    updateParentsFree(memoryMapIdx);
}

#1 获取memoryMapIdx和bitmapIdx
#2 内存块在PoolSubpage中分配,通过PoolSubpage释放内存。
#3 处理到这里,就是释放Chunk级别的内存块了。
增加空闲内存字节数。
设置二叉树中对应的节点为未分配
对应修改该节点的父节点。

另外,Netty 4.1.52对PoolArena内存级别划分的算法也做了调整。
Netty 4.1.52的具体算法前面文章《Netty内存池与PoolArena》已经说过了,这里简单说一下Netty 4.1.52前的算法。
PoolArena中将维护的内存块按大小划分为以下级别:
Tiny < 512
Small < 8192(8K)
Chunk < 16777216(16M)
Huge >= 16777216

PoolArena#tinySubpagePools,smallSubpagePools两个数组用于维护Tiny,Small级别的内存块。
tinySubpagePools,32个元素,每个数组之间差16个字节,大小分别为0,16,32,48,64, ... ,496
smallSubpagePools,4个元素,每个数组之间大小翻倍,大小分别为512,1025,2048,4096
这两个数组都是PoolSubpage数组,PoolSubpage大小默认都是8192,Tiny,Small级别的内存都是在PoolSubpage上分配的。
Chunk内存块则都是8192的倍数。
在Netty 4.1.52,已经删除了Small级别内存块,并引入了SizeClasses计算对齐内存块或计算对应的索引。
SizeClasses默认将16M划分为75个内存块size,内存划分更细,也可以减少内存对齐的空间浪费,更充分利用内存。感兴趣的同学可以参考前面的文章《内存对齐类SizeClasses》。

如果您觉得本文不错,欢迎关注我的微信公众号,系列文章持续更新中。您的关注是我坚持的动力!