Netty学习之旅:源码分析Netty内存池分配基础数据结构(PoolArena、PoolChunk、PoolSubpage)

 2020-01-09 16:26  阅读(1723)
文章分类:架构设计

1、Netty 内存分配基础数据结构

Netty 预先申请一大块连续的内存(用 PoolArena 类表示),然后每一 PoolArena 包含一系列的 Chunk, 用 PoolChunk 表示,然后每一个 Chunk 包含一列的 PoolSubpage,每个 PoolSubpage 由大小相等的块(Region)组成,每个 PoolSubpage 块大小由第一次从 PoolSubpage申请的大小来决定。

Netty 关于 PooledByteBuf(池ByteBuf)的学习研究,可以debug如下代码,揭开Netty内存分配的流程,为了帮助大家理解,我想从 Netty 内存存储相关类的数据结构开始分析梳理,为进一步揭开Netty内存分配算法打下坚实的基础。

PooledByteBufAllocator a = new PooledByteBufAllocator(false);
    ByteBuf buf = a.heapBuffer(252);
    System.out.println(buf);

Netty内存存储(数据结构)涉及如下类:

  • PooledByteBufAllocator
  • PoolArena
  • PoolChunk
  • PoolSubpage
  • PoolChunkList

2、源码分析 PooledByteBufAllocator 数据结构

从 Netty 学习系列的文章中可以了解到 Netty 将单独分配内存用 ByteBufAllocator 分配接口进行抽象化,PooledByteBufAllocator就是内存池的分配原理实现。

2.1 PooledByteBufAllocator 静态变量、初始化分析

private static final int DEFAULT_NUM_HEAP_ARENA;
    private static final int DEFAULT_NUM_DIRECT_ARENA;
    private static final int DEFAULT_PAGE_SIZE;
    private static final int DEFAULT_MAX_ORDER; 
    private static final int DEFAULT_TINY_CACHE_SIZE;
    private static final int DEFAULT_SMALL_CACHE_SIZE;
    private static final int DEFAULT_NORMAL_CACHE_SIZE;
    private static final int DEFAULT_MAX_CACHED_BUFFER_CAPACITY;
    private static final int DEFAULT_CACHE_TRIM_INTERVAL;
    private static final int MIN_PAGE_SIZE = 4096;
    private static final int MAX_CHUNK_SIZE = (int) (((long) Integer.MAX_VALUE + 1) / 2);
  • DEFAULT_NUM_HEAP_ARENA
    PoolArena 的个数,从下文的初始化中可以看出,取值为 CPU 核心逻辑线程数与 (最大运行内存【堆内存或堆外内存】的大小的二分之一 除以每个 Chunk-size, 并除以3,是确保每个 PoolArena 包含三个 Chunk)。
  • DEFAULT_NUM_DIRECT_ARENA
    与上述含义是一样,堆外内存。
  • DEFAULT_PAGE_SIZE
    默认 pageSize 大小, 最小为4K, 默认为8K。
  • DEFAULT_MAX_ORDER
    每个 chunk 中的 page 用平衡二叉树映射管理每个 PoolSubpage 是否被分配,maxOrder 为树的深度,深度为 maxOrder 层的节点数量为 1 << maxOrder。
  • DEFAULT_TINY_CACHE_SIZE : 512
  • DEFAULT_SMALL_CACHE_SIZE : 256
  • DEFAULT_NORMAL_CACHE_SIZE 64
  • MAX_CHUNK_SIZE 等于2的30次方,1G。

静态代码初始化源码分析:

static {
            int defaultPageSize = SystemPropertyUtil.getInt("io.netty.allocator.pageSize", 8192);   // @1 start
            Throwable pageSizeFallbackCause = null;
            try {
                validateAndCalculatePageShifts(defaultPageSize);
            } catch (Throwable t) {
                pageSizeFallbackCause = t;
                defaultPageSize = 8192;
            }
            DEFAULT_PAGE_SIZE = defaultPageSize;    //@1 end

            int defaultMaxOrder = SystemPropertyUtil.getInt("io.netty.allocator.maxOrder", 11);  //@2 start
            Throwable maxOrderFallbackCause = null;
            try {
                validateAndCalculateChunkSize(DEFAULT_PAGE_SIZE, defaultMaxOrder);
            } catch (Throwable t) {
                maxOrderFallbackCause = t;
                defaultMaxOrder = 11;
            }
            DEFAULT_MAX_ORDER = defaultMaxOrder;                                                                         //@2 end

            // Determine reasonable default for nHeapArena and nDirectArena.
            // Assuming each arena has 3 chunks, the pool should not consume more than 50% of max memory.
            final Runtime runtime = Runtime.getRuntime();
            final int defaultChunkSize = DEFAULT_PAGE_SIZE << DEFAULT_MAX_ORDER;     //@3
            DEFAULT_NUM_HEAP_ARENA = Math.max(0,                                                                     //@4 start
                    SystemPropertyUtil.getInt(
                            "io.netty.allocator.numHeapArenas",
                            (int) Math.min(
                                    runtime.availableProcessors(),
                                    Runtime.getRuntime().maxMemory() / defaultChunkSize / 2 / 3)));
            DEFAULT_NUM_DIRECT_ARENA = Math.max(0,
                    SystemPropertyUtil.getInt(
                            "io.netty.allocator.numDirectArenas",
                            (int) Math.min(
                                    runtime.availableProcessors(),
                                    PlatformDependent.maxDirectMemory() / defaultChunkSize / 2 / 3)));    //@4 end

            // cache sizes     @5start
            DEFAULT_TINY_CACHE_SIZE = SystemPropertyUtil.getInt("io.netty.allocator.tinyCacheSize", 512);
            DEFAULT_SMALL_CACHE_SIZE = SystemPropertyUtil.getInt("io.netty.allocator.smallCacheSize", 256);
            DEFAULT_NORMAL_CACHE_SIZE = SystemPropertyUtil.getInt("io.netty.allocator.normalCacheSize", 64);

            // 32 kb is the default maximum capacity of the cached buffer. Similar to what is explained in
            // 'Scalable memory allocation using jemalloc'
            DEFAULT_MAX_CACHED_BUFFER_CAPACITY = SystemPropertyUtil.getInt(
                    "io.netty.allocator.maxCachedBufferCapacity", 32 * 1024);

            // the number of threshold of allocations when cached entries will be freed up if not frequently used
            DEFAULT_CACHE_TRIM_INTERVAL = SystemPropertyUtil.getInt(
                    "io.netty.allocator.cacheTrimInterval", 8192);           // @5 end

            // 日志输出代码省略
            }
        }
    private static int validateAndCalculatePageShifts(int pageSize) {
            if (pageSize < MIN_PAGE_SIZE) {
                throw new IllegalArgumentException("pageSize: " + pageSize + " (expected: " + MIN_PAGE_SIZE + "+)");
            }

            if ((pageSize & pageSize - 1) != 0) {
                throw new IllegalArgumentException("pageSize: " + pageSize + " (expected: power of 2)");
            }

            // Logarithm base 2. At this point we know that pageSize is a power of two.
            return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(pageSize);
        }

        private static int validateAndCalculateChunkSize(int pageSize, int maxOrder) {
            if (maxOrder > 14) {
                throw new IllegalArgumentException("maxOrder: " + maxOrder + " (expected: 0-14)");
            }

            // Ensure the resulting chunkSize does not overflow.
            int chunkSize = pageSize;
            for (int i = maxOrder; i > 0; i --) {
                if (chunkSize > MAX_CHUNK_SIZE / 2) {
                    throw new IllegalArgumentException(String.format(
                            "pageSize (%d) << maxOrder (%d) must not exceed %d", pageSize, maxOrder, MAX_CHUNK_SIZE));
                }
                chunkSize <<= 1;
            }
            return chunkSize;
        }

代码@1:初始化 DEFAULT_PAGE_SIZE 为默认的8K, PageSize 不能小于4K 并必须是2的幂。

代码@2:初始化 maxOrder,maxOrder 为树的深度,一个chunk 的 2的 maxOrder 幂。

代码@3 :初始化默认 chunk 的大小,为 PageSize * (2 的 maxOrder幂)。

代码@4:计算 PoolAreana 的个数,PoolArena 为 cpu 核心线程数与(最大堆内存 / 2 ,然后再除以三,确保系统分配的PoolArena 占用的内存不超过系统可用内存的一半,并且保证每个 PoolArena 至少可以由3个 PoolChunk组成)。

代码@5:与本地线程分配有关,tiny内存、small内存的数量,在内存分配算法时重点剖析。

2.2 构造方法

/**
     *    @param preferDirect 是否倾向于使用直接内存
     *    @param nHeapArena  连续的堆内存数量(PoolArena)的个数
     *    @param nDirectArena 连续的堆外内存数量(PoolArena)的个数
     *    @param pageSize  页的内存大小,默认8192 8K
     *    @param maxOrder chunk的组织是用一颗平衡二叉树来表示的,maxOrder树的深度,一个chunk由2的maxOrder幂组成,maxOrder默认为11,最大为14
     *    @param tinyCacheSize,默认512,
     *    @param smallCacheSize默认为256
     *    @param normalCacheSize 默认为64
     */
    public PooledByteBufAllocator(boolean preferDirect, int nHeapArena, int nDirectArena, int pageSize, int maxOrder,
                                      int tinyCacheSize, int smallCacheSize, int normalCacheSize) {
            super(preferDirect);
            threadCache = new PoolThreadLocalCache();   // @1
            this.tinyCacheSize = tinyCacheSize;
            this.smallCacheSize = smallCacheSize;
            this.normalCacheSize = normalCacheSize;
            final int chunkSize = validateAndCalculateChunkSize(pageSize, maxOrder);

            if (nHeapArena < 0) {
                throw new IllegalArgumentException("nHeapArena: " + nHeapArena + " (expected: >= 0)");
            }
            if (nDirectArena < 0) {
                throw new IllegalArgumentException("nDirectArea: " + nDirectArena + " (expected: >= 0)");
            }

            int pageShifts = validateAndCalculatePageShifts(pageSize);    // @2

            if (nHeapArena > 0) {    //@3 start 
                heapArenas = newArenaArray(nHeapArena);
                for (int i = 0; i < heapArenas.length; i ++) {
                    heapArenas[i] = new PoolArena.HeapArena(this, pageSize, maxOrder, pageShifts, chunkSize);
                }
            } else {
                heapArenas = null;
            }

            if (nDirectArena > 0) {
                directArenas = newArenaArray(nDirectArena);
                for (int i = 0; i < directArenas.length; i ++) {
                    directArenas[i] = new PoolArena.DirectArena(this, pageSize, maxOrder, pageShifts, chunkSize);
                }
            } else {
                directArenas = null;
            }  // @3 end
        }

代码@1:PoolThreadLocalCache该类在内存分配事将重点讲解,目前先这样理解,在一个线程的上下文,线程从相同的PoolArena中去申请内存。

代码@2:pageShifts,比如pageSize为8192, 2的13次方法,那pageShifts为Integer.SIZE - 1 - Integer.numberOfLeadingZeros(pageSize) = 13,其中Integer.numberOfLeadingZeros返回高位连续的0的个数,8192为2的13次方,所有8192的二进制的高位有18个0,所以pageShifts为13。

pageShifts 在计算 numSmallPoolSubpages 大小是用到,numSmallPoolSubpages 是数组 smallPoolSubpages[] 的长度,因为Netty 中关于 small 内存的大小定义是 [1024,pageSize), 而且是翻倍存放,比如 1024 2048 4096等,该值在讲解 PoolArena 数据结构时还会详细介绍。

3、PoolArena 源码分析

PoolArena,该类是逻辑意义上一块连续的内存,之所以说它是逻辑的,因为该类不涉及到具体的内存存储。什么是具体的内存呢?我们一般用 byte[] 字节数组表示堆内存,用 java.nio.ByteBuffer 来表示堆外内存。所以 PoolArena 中并不会直接与 byte[] 或java.nio.ByteBuffer 打交道,而是维护一系列的 PoolChunk。我们从如下几个方面来讲解 PoolArena。

  1. 内部数据结构与构造方法
  2. 简单介绍PoolArena.HeapArena与PoolArena.DirectArena
  3. 分配与内存释放算法;这个统一放到内存的分配与释放时统一讲解。

3.1 内部数据结构与构造方法

static final int numTinySubpagePools = 512 >>> 4;

        final PooledByteBufAllocator parent; // @1 start

        private final int maxOrder;
        final int pageSize;
        final int pageShifts;
        final int chunkSize;                             //@1 end        

        final int subpageOverflowMask;        //@2
        final int numSmallSubpagePools;      //@3
        private final PoolSubpage<T>[] tinySubpagePools;          //@4
        private final PoolSubpage<T>[] smallSubpagePools;       //@5

        private final PoolChunkList<T> q050;                               //@6 start
        private final PoolChunkList<T> q025;
        private final PoolChunkList<T> q000;
        private final PoolChunkList<T> qInit;
        private final PoolChunkList<T> q075;
        private final PoolChunkList<T> q100;                               //@6 end

        // TODO: Test if adding padding helps under contention
        //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;

        protected PoolArena(PooledByteBufAllocator parent, int pageSize,
            int maxOrder, int pageShifts, int chunkSize) {
            this.parent = parent;
            this.pageSize = pageSize;
            this.maxOrder = maxOrder;
            this.pageShifts = pageShifts;
            this.chunkSize = chunkSize;
            subpageOverflowMask = ~(pageSize - 1);
            tinySubpagePools = newSubpagePoolArray(numTinySubpagePools);
            for (int i = 0; i < tinySubpagePools.length; i ++) {
                tinySubpagePools[i] = newSubpagePoolHead(pageSize);
            }

            numSmallSubpagePools = pageShifts - 9;
            smallSubpagePools = newSubpagePoolArray(numSmallSubpagePools);
            for (int i = 0; i < smallSubpagePools.length; i ++) {
                smallSubpagePools[i] = newSubpagePoolHead(pageSize);
            }

            q100 = new PoolChunkList<T>(this, null, 100, Integer.MAX_VALUE);
            q075 = new PoolChunkList<T>(this, q100, 75, 100);
            q050 = new PoolChunkList<T>(this, q075, 50, 100);
            q025 = new PoolChunkList<T>(this, q050, 25, 75);
            q000 = new PoolChunkList<T>(this, q025, 1, 50);
            qInit = new PoolChunkList<T>(this, q000, Integer.MIN_VALUE, 25);

            q100.prevList = q075;
            q075.prevList = q050;
            q050.prevList = q025;
            q025.prevList = q000;
            q000.prevList = null;
            qInit.prevList = qInit;
        }

代码@1:PooledByteBufAllocator parent:分配 PoolArena 的类,也就是 PoolArena 的构造方法被 PooledByteBufAllocator 调用。

  • maxOrder:最大深度,来自 PooledByteBufAllocator parent。
  • pageSize、pageShifts、chunkSize均来源于PooledByteBufAllocator parent。

@代码@2:subpageOverflowMask,判断需要分片的容量是否超过 pageSize, 由于 pageSize 是2的幂,故如果要判断一个数小于 pageSize,位运算的操作是 anum & ~(pageSize-1) == 0 的话,说明 anum 小于 pageSize。这里的 subpageOverflowMask 就等于 ~(pageSize-1)

代码@4:PoolSubpage[] tinySubpagePools,数组默认长度为32(512 >>4),这里的设计这些是这样的,Netty认为小于512子节的内存为小内存,英文为tiny,tiny按照16字节递增,比如16,32,48,而PoolSubpage本身就是一个链表结构,所以在运行中tinySubpagePools的实际表现是: tinySubpagePools[0] 存放的是(PoolSubpage)第一次分配的内存是([0-15)个字节的PoolSubpage,第一次分配的内存是[16-31)的PoolSubpage放入在tinySubpagePools[1]中,也就是tinySubpagePools[31],存放的是第一次分配了[496,511)的poolSubpage。在这里我们要明白两点,首先PoolSubpage里面可以再次分成大小相等的内存空间,因为一个PoolSubpage的内存大小默认为8K,当一个线程需要申请16个字节时,如果存在一个PoolSubpage,里面每一小块的空间为16个字节的PoolSubpage,并且未被全部占有,直接在Poolsubpage中分配,如果不存在,则首先分配一个PoolSubpage,然后将初始化为每个块容量为16字节,然后将该PoolSubpage放入到PoolArena的tinySubpagePools数组的下表为1的地方,如果该地方已经有元素了,则tinySubpagePools[1]会维护一条链。

代码@5:PoolSubpage[] smallSubpagePools,存储思维与tinySubpagePools一样。怎么计算smallSubpagePools的数组长度呢?首先,Netty把大于等于512小于pageSize(8192)的内存空间看出为small。small内存是翻倍来组织,也就是会产生[0,1024),[1024,2048),[2048,4096),[4096,8192),首先,根据约定small的区间是1024的翻倍,其实我们只要先求出 pageSize的幂,pageShifts ,然后减去9(1024是2的10次幂),故默认smallSubpagePools数组长度为4。

代码@6:PoolChunlList其实这个的存储与上述的smallSubpagePools的存储类似,首先PoolChunList本身就是一个链表,下一个元素是PoolChunkList,PoolChunkList的连接为 qInit(-Integer.MIN_VALUE) ---> q000(使用率1-50)--q025(25-75)-->q50(50-100)->q075(75-100)-->q100(100,Integer.MAX_VALUE);然后每个PoolChunkList中用head字段维护一个PoolChunk链表的头部,每个PoolChunk中有prev,next字段。而PoolChunkList内部维护者一个PoolChunk链表头部。

3.2 相关工具方法

上述关于 tinySubpagePools 与关于 tiny 内存大小,small 内存大小的定义,全部是基于如下方法得出结论:

int normalizeCapacity(int reqCapacity) {
            if (reqCapacity < 0) {
                throw new IllegalArgumentException("capacity: " + reqCapacity + " (expected: 0+)");
            }
            if (reqCapacity >= chunkSize) {
                return reqCapacity;
            }

            if (!isTiny(reqCapacity)) { // >= 512
                // Doubled

                int normalizedCapacity = reqCapacity;
                normalizedCapacity --;
                normalizedCapacity |= normalizedCapacity >>>  1;
                normalizedCapacity |= normalizedCapacity >>>  2;
                normalizedCapacity |= normalizedCapacity >>>  4;
                normalizedCapacity |= normalizedCapacity >>>  8;
                normalizedCapacity |= normalizedCapacity >>> 16;
                normalizedCapacity ++;

                if (normalizedCapacity < 0) {
                    normalizedCapacity >>>= 1;
                }

                return normalizedCapacity;
            }

            // Quantum-spaced
            if ((reqCapacity & 15) == 0) {
                return reqCapacity;
            }

            return (reqCapacity & ~15) + 16;
        }

代码解读:参数reqCapacity,表示需要申请的最小内存大小。

从isTiny方法可以看出,tiny 内存大小是小于512字节的大小。

如果申请的内存,小于512,将返回大于reqCapacity的第一个以16字节的整数,也就是说tiny块大小以16递增。

如果申请大于512,则是double,比如,申请512或513字节,都将返回1024,如果申请1025字节,将返回2048字节。

这个方法的逻辑决定了 tinySubpagePools 数组的下标定义,也决定了 smallSubpagePools 数组的下标对位,也就有了 tinyIdx 与 smallIdex 的实现。

static int tinyIdx(int normCapacity) {
            return normCapacity >>> 4;
        }

        static int smallIdx(int normCapacity) {
            int tableIdx = 0;
            int i = normCapacity >>> 10;
            while (i != 0) {
                i >>>= 1;
                tableIdx ++;
            }
            return tableIdx;
        }

        // capacity < pageSize
        boolean isTinyOrSmall(int normCapacity) {
            return (normCapacity & subpageOverflowMask) == 0;
        }

        // normCapacity < 512
        static boolean isTiny(int normCapacity) {
            return (normCapacity & 0xFFFFFE00) == 0;
        }

3.3 PoolArena.HeapPoolArena 与 PoolArena.DirectPoolArena

PoolArena.HeapPoolArena是堆内存的实现,而DirectPoolArena是直接内存的实现。

4、PoolChunk 内部数据结构分析

4.1 PoolChunk 数据结构分析

final class PoolChunk<T> {    // PoolChunk会涉及到具体的内存,泛型T表示byte[](堆内存)、或java.nio.ByteBuffer(堆外内存)

        final PoolArena<T> arena;   //PoolArena arena;该PoolChunk所属的PoolArena。
        final T memory;                    // 具体用来表示内存;byte[]或java.nio.ByteBuffer。
        final boolean unpooled;       // 是否是可重用的,unpooled=false表示可重用

        private final byte[] memoryMap;  //PoolChunk的物理视图是连续的PoolSubpage,用PoolSubpage保持,而memoryMap是所有PoolSubpage的                                                             //逻辑映射,映射为一颗平衡二叉数,用来标记每一个PoolSubpage是否被分配。下文会更进一步说明
        private final byte[] depthMap;     
        private final PoolSubpage<T>[] subpages;  // 该PoolChunk所包含的PoolSupage。也就是PoolChunk连续的可用内存。
        /** Used to determine if the requested capacity is equal to or greater than pageSize. */
        private final int subpageOverflowMask;  //用来判断申请的内存是否超过pageSize的掩码,等于  ~(pageSize-1)
        private final int pageSize;                         //每个PoolSubpage的大小,默认为8192个字节(8K)
        private final int pageShifts;                      //pageSize 2的 pageShifts幂
        private final int maxOrder;                      // 平衡二叉树的深度,一个PoolChunk包含 2的 maxOrder幂(  1 << maxOrder ) 个PoolSubpage。                                                                                  // maxOrder最大值为14
        private final int chunkSize;                      //PoolChunk的总内存大小,chunkSize =   (1<<maxOrder) * pageSize。
        private final int log2ChunkSize;              // chunkSize 是  2的 log2ChunkSize幂,如果chunkSize = 2 的 10次幂,那么 log2ChunkSize=10
        private final int maxSubpageAllocs;       // PoolChunk由maxSubpageAllocs个PoolSubpage组成。
        /** Used to mark memory as unusable */
        private final byte unusable;                    //标记为已被分配的值,该值为 maxOrder + 1

        private int freeBytes;                              //当前PoolChunk空闲的内存。

        PoolChunkList<T> parent;                    //一个PoolChunk分配后,会根据使用率挂在一个PoolChunkList中,在(PoolArena的PoolChunkList上)
        PoolChunk<T> prev;                             // PoolChunk本身设计为一个链表结构。
        PoolChunk<T> next;                             

        // TODO: Test if adding padding helps under contention
        //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;

        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;
            this.pageShifts = pageShifts;
            this.maxOrder = maxOrder;
            this.chunkSize = chunkSize;
            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);
        }

        /** Creates a special chunk that is not pooled. */
        PoolChunk(PoolArena<T> arena, T memory, int size) {
            unpooled = true;
            this.arena = arena;
            this.memory = memory;
            memoryMap = null;
            depthMap = null;
            subpages = null;
            subpageOverflowMask = 0;
            pageSize = 0;
            pageShifts = 0;
            maxOrder = 0;
            unusable = (byte) (maxOrder + 1);
            chunkSize = size;
            log2ChunkSize = log2(chunkSize);
            maxSubpageAllocs = 0;
        }

构造方法,我们重点解析一下 memoryMap 与 depthMap,PoolChunk 中所有的 PoolSubpage 都放在 PoolSubpage[] subpages中,为了更好的分配,Netty 用一颗平衡二叉树记录每个 PoolSubpage 的分配情况。为了直观的举例,我以一个 maxOrder=3 的PoolChunk 来说明 memoryMap 中存放的数据

order(dept)=0 0

/ \

order(dept) =1 1 1

/ \ / \

order(dept) =2 2 2 2 2

/ \ / \ /\ /\

order(dept) =3 3 3 3 3 3 3 3 3

根据上述讲解,maxOrder=3,表示一个PoolChunk中有8个PoolSubpage。发现没,该平衡二叉树的最后一层的节点数就是8个,那memoryMap存放数据如下

[ | 0, 1,1 ,2,2,2,2,3,3,3,3 ] memoryMap数组元素长度为 1<<(maxOrder),memoryMap[1]代表根节点,memoryMap 索引为i,i+1 的父节点为i>1;如果在索引i=1的值,如果memoryMap[i] = maxOrder+1,就表示该位置的PoolSubpage已被分配。而depthMap记录的就是索引id在树中对应的深度。在Netty源码中,用id来表示memoryMap的下标。

4.2 工具方法

本文主要关注如下两个工具方法,因为PoolSubpage的基本数据结构中包含这两个工具的运算结果。

private int runLength(int id) {
            // represents the size in #bytes supported by node 'id' in the tree
            return 1 << log2ChunkSize - depth(id);
           // return 1 << (log2ChunkSize-depth(id));
        }

该方法返回memoryMap[id]处节点代表的内存大小。memoryMap[1]代表根节点,表示整个PoolChunk的大小,而 memoryMap[2],memoryMap[3]的大小为 chunkSize >> 1,等于

private int runOffset(int id) {
            // represents the 0-based offset in #bytes from start of the byte-array chunk
            int shift = id ^ 1 << depth(id);
            // int shift = id ^ ( 1 << depth(id));
            return shift * runLength(id);
        }

//返回 id 在该同级节点(兄弟节点从左--》右)的偏移量。比如上中,id=8,8所在的深度为3,那么该层一共有 1<<3 ,8个节点,shift的值等于id在该兄弟中的偏移量,比如id=8,是深度为3的第一个节点,返回0,而id=9,则是该8个节点中的第二个。因为真正表示内存的是深度为maxOrder的节点,也就是PoolSubpage,故这里的runOffset,就是运行时每个PoolSubpage的内存偏移量。

4.3 PoolSubpage数据结构分析

final class PoolSubpage<T> {
        final PoolChunk<T> chunk;                 // 所属的PoolChunk
        private final int memoryMapIdx;       // 在memoryMap的索引 id memoryMap[id]
        private final int runOffset;                  // 在PoolChunk的运行时内存偏移量
        private final int pageSize;                  // pageSize
        private final long[] bitmap;                
        PoolSubpage<T> prev;
        PoolSubpage<T> next;
        boolean doNotDestroy;
        int elemSize;
        private int maxNumElems;
        private int bitmapLength;                   // bitmap中实际使用的长度
        private int nextAvail;                           //下一个可分配的elemSize块
        private int numAvail;                          //目前可用的elemSize块数量。
        // TODO: Test if adding padding helps under contention
        //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
        /** Special constructor that creates a linked list head */
        PoolSubpage(int pageSize) {
            chunk = null;
            memoryMapIdx = -1;
            runOffset = -1;
            elemSize = -1;
            this.pageSize = pageSize;
            bitmap = null;
        }
        PoolSubpage(PoolChunk<T> chunk, int memoryMapIdx, int runOffset, int pageSize, int elemSize) {
            this.chunk = chunk;
            this.memoryMapIdx = memoryMapIdx;
            this.runOffset = runOffset;
            this.pageSize = pageSize;
            bitmap = new long[pageSize >>> 10]; // pageSize / 16 / 64
            init(elemSize);
        }

重点分析一下bitmap,首先PoolSubpage由大小相等的elemSize组成,elemSize表示第一次在该PoolSubpage中申请内存的大小,用 bitmap来表示每一个elemSize是否被占用,值得注意的是elemSize是经过处理的,肯定是2的幂,更加准确的说,是tiny,或small内存的大小。bitmap设置为long[],那么对于一个PoolSubpage,怎么计算bitmap呢?我们可算出最大的长度,就是elemSize=16字节,一个最小的tiny内存,而一个long有8个字节64位,故bitmap数组最大的长度为 pageSize / 16 / 64 = pageSize >>> 10 (4,6)。

void init(int elemSize) {
            doNotDestroy = true;
            this.elemSize = elemSize;
            if (elemSize != 0) {
                maxNumElems = numAvail = pageSize / elemSize;   
                nextAvail = 0;
                bitmapLength = maxNumElems >>> 6; // @1
                if ((maxNumElems & 63) != 0) {  //@2
                    bitmapLength ++;
                }
                for (int i = 0; i < bitmapLength; i ++) {
                    bitmap[i] = 0;
                }
            }
            addToPool();
        }

这里主要是计算maxNumElems,numAvail,这个好理解。bitmapLenth 为bitmap 实际需要的长度。其实等于 maxNumElems /64 = maxNumElems >>>6。

代码@2,如果 maxNumElems 如果小于64,那么maxNumElems>>>6 则等为0,故需要加一。

private void addToPool() {
            PoolSubpage<T> head = chunk.arena.findSubpagePoolHead(elemSize);
            assert prev == null && next == null;
            prev = head;
            next = head.next;
            next.prev = this;
            head.next = this;
        }

addToPool,不知大家还记得不 PoolArena 中按照 PoolSubpage中elemSize 的大小分类存储了 PoolSubpages[], 就是 tinySubpagePools[] 与 smallSubpaegPools[]。这里就是将 PoolSubpage 加入到这两个数组中合适的位置。

5、 PoolChunlList

PoolChunkList 在讲解 PoolArena 的内部数据结构时已经梳理一遍了。再这就不做过多的讲解。

到此,Netty内存相关的数据结构解析到此结束了,下一篇将重点分析内存的分配、回收机制。


来源:https://blog.csdn.net/prestigeding/article/details/53977445

点赞(1)
版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> Netty学习之旅:源码分析Netty内存池分配基础数据结构(PoolArena、PoolChunk、PoolSubpage)

相关推荐