掘金 后端 ( ) • 2022-01-17 15:13

看别的大佬一篇文章理解了三天,终于搞懂了Netty是怎么管理内存的了。现在自己归纳一波。这篇文章省略了位运算的推导。先以一个总览的方式了解Netty到底在干嘛

概述

Netty管理内存用最简单的话来说就是找操作系统先申请一个 16M的空间自己管理,在用户层面创建一个 ByteBuf想要进行数据的读写,其实这个 ByteBuf只是一个指向 16M空间的一个 offset而已。不同的 ByteBuf 只是指向这个空间的不同的 offset不同罢了。当然Netty不是真的这么简单一个空间,只是一个大概的思路

image.png

Jemalloc中伙伴算法实现

Jemalloc算法是伙伴算法slab算法的结合,具体细节自行百度。Netty中的 PoolChunk类是该算法的实现,我们来看看代码

final class PoolChunk implements PoolChunkMetric {
    final T memory;
    private final byte[] memoryMap;
}

这次主要是为了理解 Jemalloc算法的实现,其他的东西就可以不用看,越看越乱。这个 PoolChunk代表着一个16M的内存数据,存放到 memory变量中,如果是非堆内存就是一个 DirectByteBuffer 如果是堆内存就是一个 byte[16M] 的一个数组。PoolChunk用一个 满二叉树来管理这16M的内存数据,memoryMap数组就是这个二叉树的实现。 已知高度为h的满二叉树节点总数为 (2^h)-1,用一个长度为 2^h的数组,第一位空出,从下标为1开始和二叉树对应如图

image.png 这张图有几个知识点需要注意,记得这个图是 PoolChunk为了管理16M内存而抽象出来的一棵树

  1. 树的第0层表示可以分配16M空间。往下分了两个子节点,每个子节点就是可以分配8M空间,以此类推
  2. memoryMap数组对应的value的含义是 第几层是可以分配数据的 这点非常重要,会帮助理解之后的代码
  3. 用户来找Netty想要内存空间的时候,会先来这个树上注册一个节点,如果能注册成功才表示可以使用该ChunkPool申请的16M空间。

源码阶段

看了大概的一个思想,我们就来看看具体 PoolChunk是如何管理这 16M的数据的

# 注册一个叶子节点这个方法外部调用的时候加了锁,所以没有线程问题,我感觉还是再这个方法里面加锁比较好,更安全点
# 返回值就是注册成功的树的序号,如果没有注册成功返回-1
long allocate(int normCapacity) {
    if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
        return allocateRun(normCapacity);
    } else {
        return allocateSubpage(normCapacity);
    }
}
# 如果上面的方法成功注册了二叉树的节点,那么就给这个 ByteBuf分配一个offset去操作16M内存
void initBuf(PooledByteBuf buf, long handle, int reqCapacity) {
    int memoryMapIdx = memoryMapIdx(handle);
    int bitmapIdx = bitmapIdx(handle);
    if (bitmapIdx == 0) {
        # 判断这个节点是不是已经被注册了
        byte val = value(memoryMapIdx);
        assert val == unusable : String.valueOf(val);
        # 给这个ByteBuf分配offset
        buf.init(this, handle, runOffset(memoryMapIdx) + offset, reqCapacity, runLength(memoryMapIdx),
                 arena.parent.threadCache());
    } else {
        initBufWithSubpage(buf, handle, bitmapIdx, reqCapacity);
    }
}

上面两个方法已经从最上层看到,想要找 PoolChunk使用内存就是调用 allocate方法,然后就会返回一个节点id,然后拿着这个节点id再调用 initBuf方法,传入的ByteBuf就指向真正的内存,可以开始读写了。所以重点就是看看allocate方法是如何返回节点id的。 allocateSubpage分支在slab算法的时候再说

private long allocateRun(int normCapacity) {
    # d 就是申请的数据大小应该的树深度
    int d = maxOrder - (log2(normCapacity) - pageShifts);
    # 拿着深度看看树里面有没有这个深度的可用节点
    int id = allocateNode(d);
    if (id < 0) {
        return id;
    }
    # 如果有的话,算出这个需要的大小,把当前 可用容量减去大小返回
    freeBytes -= runLength(id);
    return id;
}

关键的方法来了,算有没有可用节点的方法看懂下面方法之前,需要有几个前置的位运算知识补充

  1. id^=1如果id是奇数则id=id-1.如果是偶数则id=id+1. 这里是为了获取树的兄弟节点
  2. id <<= 1 表示从当前节点跳到id的左子节点上 id = 2 的时候,他的左子节点 = 4
  3. initial = - (1 << d) 1左移d然后取反,相当于一个掩码,看下个知识点
  4. (id & initial) == 0 id & initial 等于0 表示当前id处于的树深度还没达到目标深度 再来回忆一下为什么需要目标深度,重新看这个图,当深度是0时候表示你可以获取16M数据,深度是1的时候表示可以获取8M数据,所以当用户想要获取 2048k 的数据的时候,首先是需要去 2^10 = 2048, 也就是第10层去找。

image.png 还有一个关键知识点 下面value(id) 方法含义就返回这个id可以分配数据的深度

    private int allocateNode(int d) {
        int id = 1;
        int initial = - (1 << d); // has last d bits = 0 and rest all = 1
        # 首先先看id = 1 也就是树的根节点的可以使用的数据深度
        byte val = value(id);
        if (val > d) { // unusable
        # 如果根节点的可用数据深度都不满足需求深度,直接不用遍历了。例如根节点下面只有深度为4的一个数据,但是我要分配一个8M 数据,也就是需求深度是1,那么这个chunk就不能满足分配要求
            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);
            # 如果跳到左子节点之后发现 val > d 也就是当前节点下没有可以分配的节点
            if (val > d) {
                # 那么就跳到右节点上去再重复寻找
                id ^= 1;
                val = value(id);
            }
        }
        # 跳出循环表示已经找到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);
        # 标记当前节点为以使用
        setValue(id, unusable); // mark as unusable
        # 把父节点的数据也一起修改,因为子节点的数据被用完了,父节点也要收到通知。
        updateParentsAlloc(id);
        return id;
    }
    # 就是返回数组对应的下标
    private byte value(int id) {
        return memoryMap[id];
    }

至此伙伴算法的分配就已经实现完成,接下来看看伙伴算法的合并数据的逻辑。合并就是把子节点的value更新之后也同步更新父节点的value。没有做什么特比的事情。需要关注free的时机,我还不知道,先TODO一下

void free(long handle) {
    int memoryMapIdx = memoryMapIdx(handle);
    int bitmapIdx = bitmapIdx(handle);
    
    # 释放子页,先不管
    if (bitmapIdx != 0) { // free a subpage
        PoolSubpage subpage = subpages[subpageIdx(memoryMapIdx)];
        assert subpage != null && subpage.doNotDestroy;

        // Obtain the head of the PoolSubPage pool that is owned by the PoolArena and synchronize on it.
        // This is need as we may add it back and so alter the linked-list structure.
        PoolSubpage head = arena.findSubpagePoolHead(subpage.elemSize);
        synchronized (head) {
            if (subpage.free(head, bitmapIdx & 0x3FFFFFFF)) {
                return;
            }
        }
    }
    # 可用数据加上去
    freeBytes += runLength(memoryMapIdx);
    # 更新自己和父节点的value值
    setValue(memoryMapIdx, depth(memoryMapIdx));
    updateParentsFree(memoryMapIdx);
}

Jemalloc中slab算法实现

当用户申请的数据小于 8K的时候,Netty就会采用slab算法来分配数据。

image.png 简单的来说,不同于伙伴算法的满二叉树,slab算法是把一个8k的数据拆分成N个小块,然后通过 位图 bitmap来计算使用情况。当申请数据小于8K的时候, Netty会判断是属于 Tiny还是Small类型(在Jemalloc4.x只有Small)。然后划分为不同的维度。 Tiny分出了31个维度,而Small分出了4个维度,当申请的数据属于其中一个的时候,就会判断数组里面有没有PoolSubpage。如果有SubPage则表示可以在这个Subpage里面分配到数据。看代码

private long allocateSubpage(int normCapacity) {
    # 先锁定需要创建的数据处在 subpages数组的哪个下标下
    PoolSubpage head = arena.findSubpagePoolHead(normCapacity);
    # 只锁一个头部然后allocateNode方法,但其实外面还有一个整个arena的锁,不知为何
    synchronized (head) {
        int d = maxOrder; // subpages are only be allocated from pages i.e., leaves
        # 直接申请深度为11的叶子节点获取空间
        int id = allocateNode(d);
        if (id < 0) {
            return id;
        }
        # 获取到了就把可用空间减去 8K
        final PoolSubpage[] subpages = this.subpages;
        final int pageSize = this.pageSize;
        freeBytes -= pageSize;

        # 找到对应的subpages下标
        int subpageIdx = subpageIdx(id);
        PoolSubpage subpage = subpages[subpageIdx];
        # 如果没有就创建,有就初始化
        if (subpage == null) {
            subpage = new PoolSubpage(head, this, id, runOffset(id), pageSize, normCapacity);
            subpages[subpageIdx] = subpage;
        } else {
            subpage.init(head, normCapacity);
        }
        # 给subpage分配数据
        return subpage.allocate();
    }
}

可以看到 PollSubpage在创建的时候没有把真正的内存对象传递进去,所以在subpage#allocate分配的时候其实也是记录一个下标。位图是8个long的数组,因为最小分配单位是 16byte,一页8k可以拆分成 8192/16 = 64*8 = 512个数据,所以 bitmap上long的每一个字节都表示一个 slab分出来的小页的使用情况

long allocate() {
    if (elemSize == 0) {
        return toHandle(0);
    }
    if (numAvail == 0 || !doNotDestroy) {
        return -1;
    }
    # 这一段都是在计算一个合适的位图坐标
    final int bitmapIdx = getNextAvail();
    int q = bitmapIdx >>> 6;
    int r = bitmapIdx & 63;
    assert (bitmap[q] >>> r & 1) == 0;
    bitmap[q] |= 1L << r;

    # 判断可用空间是否还有,如果没有就自己从队列中移除
    if (-- numAvail == 0) {
        removeFromPool();
    }
    # 把位图坐标和当前页对应的PoolChunk的memoryMap的坐标进行合并到一个64位的long里面返回
    return toHandle(bitmapIdx);
}

总结

Jemalloc的核心思想就是通过一个long类型的handler来定位真实内存的下标。不同的创建方式生成的handler不同。如果是伙伴算法则是高位为0低位表示满二叉树的坐标,如果是slab算法,把某个二叉树的下标组合位图的坐标返回的handler。