Netty 是一個(gè)高性能的網(wǎng)絡(luò)應(yīng)用程序框架，主要就是進(jìn)行數(shù)據(jù)的交互，所以必須有一個(gè)高效的內(nèi)存分配器。
內(nèi)存分配器的功能就兩個(gè)：

• 用戶申請內(nèi)存時(shí)，分配給它內(nèi)存塊。
• 用戶主動(dòng)釋放內(nèi)存時(shí)，回收這個(gè)內(nèi)存塊。

一般我們的做法是：

• 先申請一個(gè)較大的內(nèi)存塊。
• 當(dāng)用戶申請內(nèi)存時(shí)，從這個(gè)內(nèi)存塊中，分割符合申請內(nèi)存大小的內(nèi)存塊給用戶。
• 用戶主動(dòng)釋放內(nèi)存時(shí)，再將這個(gè)內(nèi)存塊回收。

但是這么做有個(gè)問題，因?yàn)橛脩羯暾垉?nèi)存的大小各不相同，分配的內(nèi)存塊大小就不一樣，回收以后就是各種尺寸的內(nèi)存碎片。

• 例如，我們有一個(gè)20大小的總內(nèi)存塊，分配給用戶兩個(gè)大小為5 內(nèi)存塊，和一個(gè)內(nèi)存為 4 內(nèi)存塊，兩個(gè)內(nèi)存為2 內(nèi)存塊;
• 之后都回收了，就有兩個(gè)為 5,一個(gè)為4,三個(gè)為2 的內(nèi)存碎片。
• 這個(gè)時(shí)候在申請內(nèi)存為 6 的內(nèi)存塊時(shí)，發(fā)現(xiàn)沒有辦法分配了。

為了解決這個(gè)問題，能夠高效地進(jìn)行內(nèi)存分配，就要使用內(nèi)存分配算法了。

• 在 Netty 4.1.45版本之前使用的是 jemalloc3 算法來進(jìn)行內(nèi)存分配的；
• 而在4.1.45版本之后使用的是 jemalloc4 算法來進(jìn)行內(nèi)存分配的。
• 本篇文章我們先介紹 jemalloc3 算法實(shí)現(xiàn)。

一. 劃分內(nèi)存規(guī)格

產(chǎn)生內(nèi)存碎片最主要的原因就是因?yàn)橛脩羯暾埖膬?nèi)存大小不一樣。

那么如果用戶申請的內(nèi)存大小都一樣，那么不就沒有內(nèi)存碎片了么。

想法雖然是好的，但是明顯是不可能的，因?yàn)槌绦蜻\(yùn)行過程中，需要的內(nèi)存本來就是不同的。
那么我們就換一個(gè)思路，雖然不能要求申請的內(nèi)存大小都一樣，但是可以提前劃分好不同規(guī)格的內(nèi)存，然后根據(jù)請的內(nèi)存大小不同，分配不同規(guī)格的內(nèi)存快。

jemalloc3_內(nèi)存規(guī)格.png

如上圖所示，jemalloc3 一共將內(nèi)存分為四種類型:

因此就可以根據(jù)用戶申請的內(nèi)存大小，直接對應(yīng)規(guī)格的內(nèi)存塊。

• 例如申請 40B, 那么就分配 48B 規(guī)格的內(nèi)存塊，雖然有 8B 的字節(jié)被浪費(fèi)了，但是避免了內(nèi)存碎片的產(chǎn)生。
• 你會(huì)發(fā)現(xiàn)從Small 開始，每個(gè)規(guī)格內(nèi)存塊相差都是一倍，這就可以導(dǎo)致 50% 的內(nèi)存浪費(fèi)；例如我們申請 513B 大小，那么只能分配1KB 規(guī)格的內(nèi)存塊。這個(gè)是 jemalloc3 算法的缺陷，只能使用 jemalloc4 算法進(jìn)行改進(jìn)，以后我們會(huì)說到。

二. 內(nèi)存規(guī)格算法實(shí)現(xiàn)

內(nèi)存規(guī)格的劃分作用和意義我們已經(jīng)了解了，那么怎么實(shí)現(xiàn)它呢?
在Netty 中使用 PoolChunk 來進(jìn)行內(nèi)存分配：

• PoolChunk 先申請一大塊內(nèi)存memory(可以是字節(jié)數(shù)組，也可以是DirectByteBuffer)，大小就是chunkSize(16MB)。
• 我們知道 Normal 規(guī)格最小內(nèi)存塊是 pageSize(8KB) 容量，那么就要能記錄最小 Normal 規(guī)格內(nèi)存塊使用情況。
• Tiny 和 Small 規(guī)格內(nèi)存塊小于 pageSize 大小，可以使用一個(gè)最小 Normal 規(guī)格內(nèi)存塊來分配多個(gè) Tiny 和 Small 規(guī)格內(nèi)存塊。

內(nèi)存規(guī)格算法實(shí)現(xiàn).png

如圖所示：

• PoolChunk 使用一個(gè)滿二叉樹(用數(shù)組實(shí)現(xiàn))來記錄內(nèi)存塊的分配使用情況。

  • 因?yàn)?code>chunkSize == 16MB，且 pageSize == 8KB，那么樹的深度depth 一共 12 層(從0 到11)。
  • 根據(jù)不同深度，就可以獲得不同大小的內(nèi)存塊，例如最底層即11層所有節(jié)點(diǎn)對應(yīng)的內(nèi)存塊大小就是8KB。

• 使用數(shù)組來實(shí)現(xiàn)這個(gè)滿二叉樹。

  • 這里有兩個(gè)數(shù)組 memoryMap和 depthMap，大小都是4096。做了特殊處理，下標(biāo)0 這個(gè)位置沒有任何意義，從下標(biāo) 1 開始。
  • depthMap 的值表示當(dāng)前下標(biāo)對應(yīng)在二叉樹中的層數(shù)。例如下標(biāo)為1的值是 0,表示第 0 層;下標(biāo)為 6 的值是 2,表示第 2 層;下標(biāo)為 2048 的值是 11,表示第 11 層。
  • memoryMap 的值表示當(dāng)前這個(gè)節(jié)點(diǎn)能分配的內(nèi)存塊大小。剛開始時(shí)和depthMap 的值是一樣的，但是當(dāng)它的子節(jié)點(diǎn)被分配了，那么值就會(huì)變。例如剛開始時(shí)，下標(biāo)為 4 的值是 2，表示能分配 4MB 內(nèi)存塊大?。蝗绻囊粋€(gè)子節(jié)點(diǎn)被分配了，那么它的值就會(huì)變成 3，表示只能分配 2MB 內(nèi)存塊大小。

• 使用 bitmap 數(shù)據(jù)記錄Tiny和Small規(guī)格內(nèi)存使用情況

  • 最底層的內(nèi)存塊可以在分成 Tiny和Small規(guī)格小內(nèi)存塊。
  • 一旦在最底層的內(nèi)存塊分配了一個(gè) Tiny和Small規(guī)格小內(nèi)存塊，那么這個(gè)最底層的內(nèi)存塊就表示被使用了，而且這個(gè)內(nèi)存塊只能分配剛分配那個(gè)大小的規(guī)格的小內(nèi)存塊，直到它被回收(即由它分配的小內(nèi)存快都被釋放)，進(jìn)行重新分配，那么可以分配其他大小的規(guī)格的小內(nèi)存塊。即由第一次分配的規(guī)格大小來決定。
  • 通過bitmap 位圖數(shù)組來記錄，已經(jīng)在最底層的內(nèi)存塊上分配了那些小內(nèi)存塊。因?yàn)樽钚?nèi)存塊大小是16B，而最底層的內(nèi)存塊大小是8KB,因此最多可以分512塊；一個(gè) long 類型有64 位二進(jìn)制數(shù)，所以最多需要8 個(gè)long 類型就可以記錄。
  • 通過 bitmapIdx 的值，可以得到在bitmap 位圖數(shù)組中的那一個(gè)long 類型的那一位。通過 bitmapIdx >>> 6 (即除以64) 得到bitmap 位圖數(shù)組的下標(biāo)；通過 bitmapIdx & 63(即整除64 的余數(shù))得到占據(jù)long 類型那一位。

• 通過 handle 來記錄偏移量和內(nèi)存塊大小

  • 高32 位用來記錄 bitmapIdx，從前面介紹 bitmapIdx的值很小的，最大值就是 64 * 8。最高位肯定是0，次高位(0x4000000000000000L)其實(shí)是用來記錄是不是Tiny和Small類型規(guī)格。
  • 低 32 位用來記錄 memoryMapIdx。
  • 如果是 Normal規(guī)格，高32 位的值肯定是0；通過memoryMapIdx從 depthMap數(shù)組獲取對應(yīng)層數(shù)，這樣就能得到內(nèi)存塊大小了；根據(jù) memoryMapIdx 可以計(jì)算在當(dāng)前這一層的偏移值。例如 memoryMapIdx = 2050，那么是第11 層，大小就是8KB；偏移值就是 2050 - 2048 = 2，那么偏移量就是 16KB；因此我們就在偏移量16KB處分割一塊8KB大小的內(nèi)存塊給用戶使用。
  • 如果是Tiny和Small規(guī)格，那么肯定是在最底層，先通過memoryMapIdx 計(jì)算偏移值，得到偏移量，然后得到這個(gè)最底層內(nèi)存塊分割成小內(nèi)存的大小，再根據(jù)bitmapIdx值得到在這個(gè)最底層內(nèi)存塊上的偏移量，最后就能得到最終偏移量和分割內(nèi)存塊大小了。

三. 源碼實(shí)現(xiàn)

3.1 PoolSubpage 類

3.1.1 初始化

    PoolSubpage(PoolSubpage<T> head, PoolChunk<T> chunk, int memoryMapIdx, int runOffset, int pageSize, int elemSize) {
        this.chunk = chunk;
        this.memoryMapIdx = memoryMapIdx;
        this.runOffset = runOffset;
        this.pageSize = pageSize;
        // 因?yàn)?long 類型是8個(gè)字節(jié)，64位二進(jìn)制數(shù)；
        // 而 Tiny 類型最小容量都是 16 個(gè)字節(jié)。
        // 所以 bitmap 位圖數(shù)組最大長度就是  pageSize / 16/ 64
        bitmap = new long[pageSize >>> 10]; // pageSize / 16 / 64
        init(head, elemSize);
    }

    void init(PoolSubpage<T> head, int elemSize) {
        doNotDestroy = true;
        // 當(dāng)前這 PoolSubpage 只會(huì)分配 elemSize 大小容量的內(nèi)存
        this.elemSize = elemSize;
        if (elemSize != 0) {
            // PoolSubpage 一共可以分配多少塊這個(gè)容量的內(nèi)存
            maxNumElems = numAvail = pageSize / elemSize;
            nextAvail = 0;
            // 無符號右移6位，也就是除以64，因?yàn)橐粋€(gè) long 有64個(gè)二進(jìn)制位
            bitmapLength = maxNumElems >>> 6;
            // 如果 maxNumElems 不能整除 64，那么就要將 bitmapLength 加一
            if ((maxNumElems & 63) != 0) {
                bitmapLength ++;
            }

            for (int i = 0; i < bitmapLength; i ++) {
                bitmap[i] = 0;
            }
        }
        // 添加到 PoolArena 中對應(yīng)尺寸容量的PoolSubpage鏈表中
        addToPool(head);
    }

• 剛開始創(chuàng)建的時(shí)候，主要是創(chuàng)建 bitmap 位圖數(shù)組，數(shù)組長度就是 pageSize >>> 10，即除以64位二進(jìn)制數(shù)，和最小Tiny類型規(guī)格都是16 個(gè)字節(jié)。
• init(...) 初始化方法，剛創(chuàng)建的時(shí)候或者PoolSubpage被回收重新使用的時(shí)候調(diào)用。
• 確定當(dāng)前PoolSubpage分配內(nèi)存塊大小elemSize；
• 計(jì)算最多分配多少這個(gè)大小的內(nèi)存塊。
• 計(jì)算真實(shí) bitmap位圖數(shù)組長度bitmapLength。
• 將這個(gè)PoolSubpage添加到PoolArena中對應(yīng)尺寸容量的PoolSubpage鏈表中，這樣就不需要需要查找，加快內(nèi)存塊分配速度。

3.1.2 分配內(nèi)存塊

    /**
     * 返回子頁面內(nèi)存分配的位圖索引
     * 使用 long 類型每個(gè)二進(jìn)制位數(shù)`0`或 `1` 來記錄這塊內(nèi)存有沒有被分配過，
     * 因?yàn)?long 是8個(gè)字節(jié)，64位二進(jìn)制數(shù)，所以可以表示 64 個(gè)內(nèi)存塊分配情況。
     */
    long allocate() {
        if (elemSize == 0) {
            return toHandle(0);
        }

        if (numAvail == 0 || !doNotDestroy) {
            return -1;
        }

        // 得到下一個(gè)可用的位圖 bitmap 索引
        final int bitmapIdx = getNextAvail();
        // 除以 64 得到的整數(shù)，即 bitmap[] 數(shù)組的下標(biāo)
        int q = bitmapIdx >>> 6;
        // 與 64 的余數(shù)，即占據(jù)的 long 類型的位數(shù)
        int r = bitmapIdx & 63;
        // 必須是 0， 表示這一塊內(nèi)存沒有被分配
        assert (bitmap[q] >>> r & 1) == 0;
        // 將r對應(yīng)二進(jìn)制位設(shè)置為1，表示這一位代表的內(nèi)存塊已經(jīng)被分配了
        bitmap[q] |= 1L << r;

        if (-- numAvail == 0) {
            // 如果可分配內(nèi)存塊的數(shù)量numAvail為0，
            // 那么就要這個(gè) PoolSubpage 從 PoolArena 中
            // 對應(yīng)尺寸容量的PoolSubpage鏈表中移除。
            removeFromPool();
        }

        // 使用 long類型的高32位儲存 bitmapIdx 的值，即使用 PoolSubpage 中那一塊的內(nèi)存；
        // 低32位儲存 memoryMapIdx 的值，即表示使用那一個(gè) PoolSubpage
        return toHandle(bitmapIdx);
    }

    private long toHandle(int bitmapIdx) {
        // 雖然我們使用高 32 為表示 bitmapIdx，但是當(dāng)bitmapIdx = 0 時(shí)，
        // 就無法確定是否表示 bitmapIdx 的值。
        // 所以這里就 0x4000000000000000L | (long) bitmapIdx << 32，那進(jìn)行區(qū)分。
        // 放心  bitmapIdx << 32 是不可能超過 0x4000000000000000L
        return 0x4000000000000000L | (long) bitmapIdx << 32 | memoryMapIdx;
    }

方法流程:

• 如果沒有可用內(nèi)存塊了，就直接返回 -1。
• 通過 getNextAvail() 方法，獲取下一個(gè)能分配的內(nèi)存塊的位圖索引bitmapIdx。
• 根據(jù)位圖索引bitmapIdx 將bitmap 位圖數(shù)組中對應(yīng)二進(jìn)制位設(shè)置為1，表示已經(jīng)被分配了。
• 如果分配之后沒有內(nèi)存塊了，就將這個(gè)PoolSubpage從PoolArena中對應(yīng)尺寸容量的PoolSubpage鏈表中刪除，因?yàn)橐呀?jīng)不能分配了。
• 通過 toHandle(bitmapIdx) 返回 handle 值。

3.1.3 回收內(nèi)存塊

 /**
     * 返回 true，表示這個(gè) PoolSubpage 還在使用，即上面還有其他小內(nèi)存塊被使用；
     * 返回 false，表示這個(gè) PoolSubpage 上面分配的小內(nèi)存塊都釋放了，可以回收整個(gè) PoolSubpage。
     */
    boolean free(PoolSubpage<T> head, int bitmapIdx) {
        if (elemSize == 0) {
            return true;
        }
        // 得到位圖 bitmap 中的下標(biāo)
        int q = bitmapIdx >>> 6;
        // 得到使用 long 類型中那一位
        int r = bitmapIdx & 63;
        // 必須不能是 0， 表示這個(gè) bitmapIdx 對應(yīng)內(nèi)存塊肯定是在被使用
        assert (bitmap[q] >>> r & 1) != 0;
        // 將r對應(yīng)二進(jìn)制位設(shè)置為0，表示這一位代表的內(nèi)存塊已經(jīng)被釋放了
        bitmap[q] ^= 1L << r;

        // 將 bitmapIdx 設(shè)置為下一個(gè)可以使用的內(nèi)存塊索引，
        // 因?yàn)閯偙会尫?，這樣就不用進(jìn)行搜索來查找可用內(nèi)存塊索引。
        setNextAvail(bitmapIdx);

        if (numAvail ++ == 0) {
            // 如果可分配內(nèi)存塊的數(shù)量numAvail從0開始增加，
            // 那么就要重新添加到 PoolArena 中對應(yīng)尺寸容量的PoolSubpage鏈表中
            addToPool(head);
            return true;
        }

        if (numAvail != maxNumElems) {
            return true;
        } else {
            // 子頁面未使用(numAvail == maxNumElems)
            if (prev == next) {
                // 如果 prev == next，即 subpage 組成的鏈表中沒有其他 subpage，不能刪除它
                return true;
            }

            // 如果 prev != next，即 subpage 組成的鏈表中還有其他 subpage，那么就刪除它
            doNotDestroy = false;
            removeFromPool();
            return false;
        }
    }

• 根據(jù)位圖索引bitmapIdx 將bitmap 位圖數(shù)組中對應(yīng)二進(jìn)制位設(shè)置為0，表示已經(jīng)被釋放了。
• 調(diào)用 setNextAvail(bitmapIdx)，加快下一次分配內(nèi)存塊的速度，不需要重新查找了。
• 最后再處理一下 PoolArena中對應(yīng)尺寸容量的PoolSubpage鏈表。

3.2 PoolChunk 類

3.2.1 分配內(nèi)存塊

3.2.1.1 allocate 方法

boolean allocate(PooledByteBuf<T> buf, int reqCapacity, int normCapacity) {
        final long handle;
        if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
            //  >= pageSize，即 Normal 規(guī)格類型內(nèi)存塊，通過 allocateRun 方法分配
            handle =  allocateRun(normCapacity);
        } else {
            // 分配 Tiny 和 Small 規(guī)格類型內(nèi)存塊
            handle = allocateSubpage(normCapacity);
        }

        if (handle < 0) {
            // 小于 0， 說明當(dāng)前PoolChunk都被分配完了
            return false;
        }
        ByteBuffer nioBuffer = cachedNioBuffers != null ? cachedNioBuffers.pollLast() : null;
        // 使用 handle 來初始化 池化緩存區(qū)PooledByteBuf
        initBuf(buf, nioBuffer, handle, reqCapacity);
        return true;
    }

• 通過 allocateRun(...) 方法，分配 Normal 規(guī)格類型內(nèi)存塊;通過 allocateSubpage(normCapacity)方法，分配Tiny 和 Small 規(guī)格類型內(nèi)存塊。
• 通過 initBuf(...) 方法，使用申請的內(nèi)存塊handle 來初始化池化緩存區(qū)PooledByteBuf。

3.2.1.2 allocateRun 方法

    private long allocateRun(int normCapacity) {
        /**
         * 默認(rèn)情況下，maxOrder=11，pageShifts=13
         * normCapacity肯定是大于或者等于pageSize，即 log2(normCapacity) >= pageShifts
         *
         * d 表示在第幾層可以分配這個(gè)尺寸容量normCapacity 的內(nèi)存塊。
         * 最底層，即11層，最多只能分配 pageSize尺寸容量的內(nèi)存塊。
         */
        int d = maxOrder - (log2(normCapacity) - pageShifts);
        /**
         * 得到尺寸容量normCapacity 內(nèi)存塊的索引id
         */
        int id = allocateNode(d);
        if (id < 0) {
            // 小于 0， 說明當(dāng)前PoolChunk都被分配完了
            return id;
        }
        freeBytes -= runLength(id);
        return id;
    }

• 通過 allocateNode(d) 方法獲取 memoryMapIdx 的值。
• 減少當(dāng)前 PoolChunk 可用內(nèi)存字節(jié)數(shù)freeBytes。

3.2.1.3 allocateNode 方法

     private int allocateNode(int d) {
        // d 代表層數(shù)，其實(shí)也代表需要的內(nèi)存容量，(1 << (maxOrder - d)) * pageSize
        // 當(dāng) d 和 maxOrder 相等，即需要內(nèi)存容量就是 pageSize
        int id = 1;
        /**
         * 例如 d = 11
         * 那么 1 << d   就是 100000000000
         *  - (1 << d)  就是 1111111111111111111111111111111111111111111111111111100000000000
         *  所以 initial的作用就是用來快速判斷某個(gè)值是不是小于 (1 << d)
         */
        int initial = - (1 << d); // has last d bits = 0 and rest all = 1
        byte val = value(id);
        if (val > d) { // unusable
            return -1;
        }
        /**
         * val < d 表示當(dāng)前節(jié)點(diǎn)id對應(yīng)的內(nèi)存容量還大于 d 對應(yīng)的內(nèi)存容量，繼續(xù)尋找。
         * (id & initial) == 0 只有當(dāng) id < (1 << d) 時(shí)成立，保證 id 是 d層的。
         */
        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);
            if (val > d) {
                /**
                 * val > d，表示從 id 節(jié)點(diǎn)對應(yīng)的內(nèi)存容量已經(jīng)不足要求內(nèi)存塊的大小了，
                 * 但是它能走到這一個(gè)判斷，說明 id 節(jié)點(diǎn)的父節(jié)點(diǎn)對應(yīng)的內(nèi)存容量是可以滿足內(nèi)存塊的大小的；
                 * 那一定是因?yàn)?id 節(jié)點(diǎn)兄弟節(jié)點(diǎn)對應(yīng)內(nèi)存容量能滿足內(nèi)存塊的大小。
                 *
                 * id ^= 1 就是得到 id 節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
                 */
                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);
        // 將當(dāng)前 memoryMap 的下標(biāo)id 的值設(shè)置為 unusable，
        // 表示它已經(jīng)被使用了， unusable = maxOrder + 1
        setValue(id, unusable); // mark as unusable
        // 更新這個(gè) id 之上所有父節(jié)點(diǎn)的值，
        // 因?yàn)閕d 節(jié)點(diǎn)被使用了，那么它之上所有父節(jié)點(diǎn)代表的內(nèi)存容量都收到影響。
        updateParentsAlloc(id);
        return id;
    }

    private void updateParentsAlloc(int id) {
        // 通過循環(huán)更新所有父節(jié)點(diǎn)的值。
        while (id > 1) {
            int parentId = id >>> 1;
            byte val1 = value(id);
            byte val2 = value(id ^ 1);
            // 尋找父節(jié)點(diǎn)對應(yīng)子節(jié)點(diǎn)中較小的值
            byte val = val1 < val2 ? val1 : val2;
            setValue(parentId, val);
            id = parentId;
        }
    }

• 現(xiàn)在滿二叉樹中，在d 對應(yīng)的那層中尋找還沒有被分配的節(jié)點(diǎn)(從左到右尋找)，返回這個(gè)節(jié)點(diǎn)的下標(biāo)值(即memoryMapIdx)。
• 通過 setValue(id, unusable) 方法，將這個(gè)節(jié)點(diǎn)值設(shè)置成unusable,表示這個(gè)節(jié)點(diǎn)已經(jīng)被分配了。
• 通過 updateParentsAlloc(id) 方法更新父節(jié)點(diǎn)可分配的內(nèi)存大小。
• 因?yàn)?d 層有個(gè)節(jié)點(diǎn)被分配了，那么這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)以及父節(jié)點(diǎn)的父節(jié)點(diǎn)等，它們的可分配的內(nèi)存大小就和它們未分配的那個(gè)子節(jié)點(diǎn)大小一樣了。

3.2.1.4 allocateNode 方法

    private long allocateSubpage(int normCapacity) {
        // 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.
        // 得到 PoolArena 中對應(yīng)尺寸容量的PoolSubpage鏈表頭
        PoolSubpage<T> head = arena.findSubpagePoolHead(normCapacity);
        // 因?yàn)?Tiny 或者 Small類型容量都小于 pageSize,
        // 所以它們肯定只使用最低層一個(gè) PoolSubpage
        int d = maxOrder;
        synchronized (head) {
            // 尋找沒有被分配的 PoolSubpage 索引id
            int id = allocateNode(d);
            if (id < 0) {
                // 小于 0， 說明當(dāng)前PoolChunk都被分配完了
                return id;
            }

            final PoolSubpage<T>[] subpages = this.subpages;
            final int pageSize = this.pageSize;

            // 當(dāng)前PoolChunk 可用字節(jié)數(shù)
            freeBytes -= pageSize;

            // 得到 this.subpages 的下標(biāo)
            int subpageIdx = subpageIdx(id);
            // 需要容量normCapacity的內(nèi)存就從這個(gè) subpage 中分配
            // 分配之后，這個(gè) subpage 就只能存放這個(gè)尺寸容量normCapacity的內(nèi)存
            // 這里的 subpage 肯定是沒有分配過內(nèi)存的，
            // 因?yàn)橥ㄟ^ allocateNode(d) 找到的肯定是沒有分配過內(nèi)存的，
            PoolSubpage<T> subpage = subpages[subpageIdx];
            if (subpage == null) {
                // 創(chuàng)建 PoolSubpage 實(shí)例，構(gòu)造方法中會(huì)調(diào)用 subpage.init(head, normCapacity) 方法
                subpage = new PoolSubpage<T>(head, this, id, runOffset(id), pageSize, normCapacity);
                subpages[subpageIdx] = subpage;
            } else {
                // 這個(gè) PoolSubpage 之前被用過，但是被釋放了。
                // 初始化, 將這個(gè) PoolSubpage 能分配的容量尺寸就是 normCapacity
                // 再將這個(gè) PoolSubpage 添加到 PoolArena 對應(yīng)容量尺寸 PoolSubpage<T> 數(shù)組中
                // 這樣下次再請求這個(gè)尺寸的內(nèi)存時(shí)，直接從 PoolSubpage<T> 數(shù)組中找到這個(gè) PoolSubpage，
                // 進(jìn)行內(nèi)存分配
                subpage.init(head, normCapacity);
            }
            // 在PoolSubpage上進(jìn)行內(nèi)存分配
            return subpage.allocate();
        }
    }

• 通過 allocateNode(d) 方法在最底層尋找未分配的內(nèi)存塊。
• 減少當(dāng)前 PoolChunk 可用內(nèi)存字節(jié)數(shù) freeBytes。
• 初始化一個(gè) PoolSubpage, 通過它的subpage.allocate() 方法進(jìn)行Tiny 和 Small 規(guī)格類型內(nèi)存塊分配。

3.2.1.5 initBuf 方法

    void initBuf(PooledByteBuf<T> buf, ByteBuffer nioBuffer, long handle, int reqCapacity) {
        // 因?yàn)?handle 高32位表示 bitmapIdx， 低32位表示 memoryMapIdx
        int memoryMapIdx = memoryMapIdx(handle);
        int bitmapIdx = bitmapIdx(handle);
        // 因?yàn)?0x4000000000000000L | (long) bitmapIdx << 32，
        // 所以 bitmapIdx == 0時(shí)，一定是 Normal 類型
        if (bitmapIdx == 0) {
            byte val = value(memoryMapIdx);
            // 肯定是被使用狀態(tài)
            assert val == unusable : String.valueOf(val);
            // runOffset(memoryMapIdx) 表示在當(dāng)前這個(gè) PoolChunk 的字節(jié)偏移量
            // runLength(memoryMapIdx) 這個(gè)內(nèi)存塊容量
            buf.init(this, nioBuffer, handle, runOffset(memoryMapIdx) + offset,
                    reqCapacity, runLength(memoryMapIdx), arena.parent.threadCache());
        } else {

            initBufWithSubpage(buf, nioBuffer, handle, bitmapIdx, reqCapacity);
        }
    }

    private int runOffset(int id) {
        // depth(id) 得到id對應(yīng)層數(shù)
        // id ^ 1 << depth(id) 就是這個(gè)id節(jié)點(diǎn)在這一層的偏移值
        // 例如 id = 2049，depth(id) 就是 11，1 << depth(id) 就是 2048
        // 2049 ^ 2048 = 1
        int shift = id ^ 1 << depth(id);
        // 偏移量shift乘以 id對應(yīng)內(nèi)存塊容量runLength(id)，
        // 就得到最后的字節(jié)偏移量
        return shift * runLength(id);
    }

    private int runLength(int id) {
        // represents the size in #bytes supported by node 'id' in the tree
        // 節(jié)點(diǎn)id對應(yīng)的內(nèi)存塊大小，單位是字節(jié)，一個(gè)字節(jié)就是8位bits
        // log2ChunkSize 是 chunkSize 的log2 的對數(shù)，
        // 而 chunkSize = pageSize * maxOrder, depth(id) 就是求id節(jié)點(diǎn)對應(yīng)的層數(shù)，最低層就是maxOrder，
        // 所以id節(jié)點(diǎn)在最底層，那么depth(id)就是maxOrder，那么結(jié)果值就是 pageSize。
        return 1 << log2ChunkSize - depth(id);
    }

初始化 Normal 規(guī)格的 PooledByteBuf, 通過 runOffset(memoryMapIdx) 方法計(jì)算偏移量，通過 runLength(memoryMapIdx) 方法計(jì)算內(nèi)存塊大小。

3.2.1.6 initBuf 方法

    private void initBufWithSubpage(PooledByteBuf<T> buf, ByteBuffer nioBuffer,
                                    long handle, int bitmapIdx, int reqCapacity) {
        assert bitmapIdx != 0;

        int memoryMapIdx = memoryMapIdx(handle);

        // 通過 memoryMapIdx 找到 PoolSubpage
        PoolSubpage<T> subpage = subpages[subpageIdx(memoryMapIdx)];
        assert subpage.doNotDestroy;
        // 容量必須小于或等于 PoolSubpage 對應(yīng)的塊容量elemSize
        assert reqCapacity <= subpage.elemSize;

        // runOffset(memoryMapIdx) 表示這個(gè) PoolSubpage 在當(dāng)前這個(gè) PoolChunk 的字節(jié)偏移量；
        // (bitmapIdx & 0x3FFFFFFF) * subpage.elemSize
        // 就是表示這個(gè) Tiny或者Small類型內(nèi)存塊在 中PoolSubpage 偏移量。
        buf.init(
            this, nioBuffer, handle,
            runOffset(memoryMapIdx) + (bitmapIdx & 0x3FFFFFFF) * subpage.elemSize + offset,
                reqCapacity, subpage.elemSize, arena.parent.threadCache());
    }

初始化 Tiny 和 Small 規(guī)格類型的 PooledByteBuf, 內(nèi)存塊大小通過 PoolSubpage 的 elemSize 獲取，偏移量要增加 (bitmapIdx & 0x3FFFFFFF) * subpage.elemSize 的值。

3.2.2 回收內(nèi)存塊

    void free(long handle, ByteBuffer nioBuffer) {
        int memoryMapIdx = memoryMapIdx(handle);
        int bitmapIdx = bitmapIdx(handle);

        if (bitmapIdx != 0) { // free a subpage
            // bitmapIdx != 0 說明它是一個(gè)Tiny 或者 Small類型
            // 通過 memoryMapIdx 找到對應(yīng)的PoolSubpage
            PoolSubpage<T> subpage = subpages[subpageIdx(memoryMapIdx)];
            assert subpage != null && subpage.doNotDestroy;

            // 獲取 PoolArena 中對應(yīng)尺寸容量的PoolSubpage鏈表頭
            PoolSubpage<T> head = arena.findSubpagePoolHead(subpage.elemSize);
            synchronized (head) {

                // 釋放PoolSubpage中 bitmapIdx 對應(yīng)那一個(gè)內(nèi)存塊
                if (subpage.free(head, bitmapIdx & 0x3FFFFFFF)) {
                    // 如果 free(...) 方法返回true，說明這個(gè)PoolSubpage還在被使用，
                    // 不能被回收，那么直接返回
                    return;
                }
            }
        }
        /**
         * 運(yùn)行到這里，
         * 要么它是一個(gè) Normal 類型內(nèi)存塊，那就釋放這個(gè)內(nèi)存塊。
         * 要么它是一個(gè) Tiny 或者 Small類型，但是它對應(yīng) PoolSubpage 那一塊內(nèi)存塊都被釋放了，這里就釋放它
         */
        freeBytes += runLength(memoryMapIdx);
        // 將  memoryMapIdx 對應(yīng)節(jié)點(diǎn)設(shè)置回原來值，又可以進(jìn)行內(nèi)存塊分配了
        setValue(memoryMapIdx, depth(memoryMapIdx));
        // 因?yàn)樽庸?jié)點(diǎn)內(nèi)存塊釋放，更新父節(jié)點(diǎn)的可分配容量
        updateParentsFree(memoryMapIdx);

        if (nioBuffer != null && cachedNioBuffers != null &&
                cachedNioBuffers.size() < PooledByteBufAllocator.DEFAULT_MAX_CACHED_BYTEBUFFERS_PER_CHUNK) {
            cachedNioBuffers.offer(nioBuffer);
        }
    }

• 如果是Tiny 和 Small 規(guī)格類型的內(nèi)存塊，那么就要使用 PoolSubpage 的free(...) 方法釋放內(nèi)存塊。如果返回 true，表示這個(gè) PoolSubpage 還在使用，直接返回；如果返回 false，表示這個(gè) PoolSubpage 不在使用，可以被回收了，就要回收對應(yīng)的整個(gè)內(nèi)存塊。
• 增加當(dāng)前 PoolChunk 可用內(nèi)存字節(jié)數(shù) freeBytes。
• 通過 setValue(...) 方法，將 memoryMapIdx 對應(yīng)節(jié)點(diǎn)值改成初始層數(shù)值，表示這個(gè)節(jié)點(diǎn)有可以分配了。
• 通過 updateParentsFree(memoryMapIdx) 方法，更新父節(jié)點(diǎn)的節(jié)點(diǎn)值，因?yàn)樽庸?jié)點(diǎn)內(nèi)存塊被釋放，那么父節(jié)點(diǎn)可分配內(nèi)存大小變了。

    private void updateParentsFree(int id) {
        int logChild = depth(id) + 1;
        while (id > 1) {
            // 父節(jié)點(diǎn)
            int parentId = id >>> 1;
            // 左子節(jié)點(diǎn)
            byte val1 = value(id);
            // 右子節(jié)點(diǎn)
            byte val2 = value(id ^ 1);
            // 子節(jié)點(diǎn)的標(biāo)準(zhǔn)值
            logChild -= 1; // in first iteration equals log, subsequently reduce 1 from logChild as we traverse up

            if (val1 == logChild && val2 == logChild) {
                // 左子節(jié)點(diǎn)和右子節(jié)點(diǎn)都是標(biāo)準(zhǔn)值，說明兩個(gè)子節(jié)點(diǎn)都是空閑的
                // 那么父節(jié)點(diǎn)的容量就是兩倍
                setValue(parentId, (byte) (logChild - 1));
            } else {
                // 取左子節(jié)點(diǎn)和右子節(jié)點(diǎn)中較大的容量，也是val比較小的值。
                byte val = val1 < val2 ? val1 : val2;
                setValue(parentId, val);
            }

            id = parentId;
        }
    }

• 如果左子節(jié)點(diǎn)和右子節(jié)點(diǎn)都是標(biāo)準(zhǔn)值，說明兩個(gè)子節(jié)點(diǎn)都是空閑的，么父節(jié)點(diǎn)的容量就是兩倍。
• 如果不是，那么就取左子節(jié)點(diǎn)和右子節(jié)點(diǎn)中較小值，即可分配內(nèi)存大小更大。

3.3 PoolArena 類

3.3.1 allocate 方法

    PooledByteBuf<T> allocate(PoolThreadCache cache, int reqCapacity, int maxCapacity) {
        PooledByteBuf<T> buf = newByteBuf(maxCapacity);
        allocate(cache, buf, reqCapacity);
        return buf;
    }

先通過 newByteBuf(maxCapacity) 方法，創(chuàng)建對應(yīng)類型的池化緩存區(qū)PooledByteBuf，然后調(diào)用allocate(cache, buf, reqCapacity) 方法進(jìn)行內(nèi)存分配。

  private void allocate(PoolThreadCache cache, PooledByteBuf<T> buf, final int reqCapacity) {
        final int normCapacity = normalizeCapacity(reqCapacity);
        if (isTinyOrSmall(normCapacity)) { // capacity < pageSize
            // 如果容量小于 pageSize 值，即是 Tiny 或者 Small類型
            int tableIdx;
            PoolSubpage<T>[] table;
            boolean tiny = isTiny(normCapacity);
            if (tiny) { // < 512
                if (cache.allocateTiny(this, buf, reqCapacity, normCapacity)) {
                    // 先從當(dāng)前線程緩存中獲取，如果能得到，直接返回
                    return;
                }
                // 得到Tiny 類型索引，因?yàn)?Tiny 類型是每個(gè)相隔16，所以索引就是 normCapacity >>> 4
                tableIdx = tinyIdx(normCapacity);
                table = tinySubpagePools;
            } else {
                if (cache.allocateSmall(this, buf, reqCapacity, normCapacity)) {
                    // 先從當(dāng)前線程緩存中獲取，如果能得到，直接返回
                    return;
                }
                // 得到Small 類型索引，每個(gè)Small 類型是成倍擴(kuò)展的，即 512 1024 2048 4096, 小于 pageSize 的大小
                tableIdx = smallIdx(normCapacity);
                table = smallSubpagePools;
            }

            // 得到符合容量尺寸的頭PoolSubpage
            final PoolSubpage<T> head = table[tableIdx];

            /**
             * Synchronize on the head. This is needed as {@link PoolChunk#allocateSubpage(int)} and
             * {@link PoolChunk#free(long)} may modify the doubly linked list as well.
             */
            synchronized (head) {
                // 使用 synchronized 防止并發(fā)
                final PoolSubpage<T> s = head.next;
                if (s != head) {
                    // 有這種尺寸容量的 PoolSubpage， 容量必須是 normCapacity
                    assert s.doNotDestroy && s.elemSize == normCapacity;
                    // 從 PoolSubpage 中分配內(nèi)存
                    long handle = s.allocate();
                    assert handle >= 0;
                    // 將分配的
                    s.chunk.initBufWithSubpage(buf, null, handle, reqCapacity);
                    incTinySmallAllocation(tiny);
                    return;
                }
            }
            synchronized (this) {
                // 運(yùn)行到這里，表示目前沒有這個(gè)尺寸的 PoolSubpage，
                // 那么從PoolChunk 中分配
                allocateNormal(buf, reqCapacity, normCapacity);
            }

            // 增加計(jì)數(shù)
            incTinySmallAllocation(tiny);
            return;
        }
        if (normCapacity <= chunkSize) {
            if (cache.allocateNormal(this, buf, reqCapacity, normCapacity)) {
                // was able to allocate out of the cache so move on
                return;
            }
            synchronized (this) {
                allocateNormal(buf, reqCapacity, normCapacity);
                ++allocationsNormal;
            }
        } else {
            // Huge類型的內(nèi)存塊肯定不會(huì)緩存在當(dāng)前線程中，直接調(diào)用 allocateHuge 分配
            allocateHuge(buf, reqCapacity);
        }
    }

這個(gè)方法看起來很復(fù)雜，但是其實(shí)邏輯很簡單:

• 通過 normalizeCapacity(reqCapacity) 方法來將用戶申請內(nèi)存大小轉(zhuǎn)成規(guī)格化大小，例如 18 就變成 32; 990 就變成 1024。
• 根據(jù) Tiny,Small,Normal 和 Huge 不同類型，進(jìn)行不同內(nèi)存塊分配。
• 對于 Tiny和Small 規(guī)格類型:

  • 先從線程緩存PoolThreadCache 中獲取，如果獲取到，就直接返回，獲取不到就繼續(xù)下面步驟。
  • 再通過tinySubpagePools或 smallSubpagePools 進(jìn)行快速分配內(nèi)存塊，如果 tinySubpagePools 中有對應(yīng)的 PoolSubpage，那么就直接分配，如果沒有，那么繼續(xù)下面步驟。
  • 通過 allocateNormal(buf, reqCapacity, normCapacity) 方法進(jìn)行內(nèi)存塊的分配。

• 對于Normal 規(guī)格類型：

  • 先從線程緩存PoolThreadCache 中獲取，如果獲取到，就直接返回，獲取不到就繼續(xù)下面步驟。
  • 通過 allocateNormal(buf, reqCapacity, normCapacity) 方法進(jìn)行內(nèi)存塊的分配。

• 對于Huge 規(guī)格類型：

  這種規(guī)格是沒有線程緩存的，所以直接通過 allocateHuge(buf, reqCapacity) 方法進(jìn)行內(nèi)存塊的分配。

3.3.2 normalizeCapacity 方法

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

        // 大于 chunkSize，表示是一個(gè) Huge 類型
        if (reqCapacity >= chunkSize) {
            // 是否需要進(jìn)行內(nèi)存對齊
            return directMemoryCacheAlignment == 0 ? reqCapacity : alignCapacity(reqCapacity);
        }

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

            // 得到與 reqCapacity 最近的 2的冪數(shù)，
            // 如果 reqCapacity 就是2的冪數(shù)，那么就是它自己
            int normalizedCapacity = reqCapacity;
            // 先減一，防止 reqCapacity 就是 2的冪數(shù)，導(dǎo)致結(jié)果值是 reqCapacity 的兩步
            normalizedCapacity --;
            normalizedCapacity |= normalizedCapacity >>>  1;
            normalizedCapacity |= normalizedCapacity >>>  2;
            normalizedCapacity |= normalizedCapacity >>>  4;
            normalizedCapacity |= normalizedCapacity >>>  8;
            normalizedCapacity |= normalizedCapacity >>> 16;
            normalizedCapacity ++;

            if (normalizedCapacity < 0) {
                normalizedCapacity >>>= 1;
            }
            assert directMemoryCacheAlignment == 0 || (normalizedCapacity & directMemoryCacheAlignmentMask) == 0;

            //
            return normalizedCapacity;
        }

        // 小于 512 數(shù)，Tiny 類型的數(shù)，是否需要進(jìn)行內(nèi)存對齊
        if (directMemoryCacheAlignment > 0) {
            return alignCapacity(reqCapacity);
        }

        // 能夠被 16 整除，那么就直接返回
        if ((reqCapacity & 15) == 0) {
            return reqCapacity;
        }

        // 結(jié)果值是 16 的倍數(shù)
        return (reqCapacity & ~15) + 16;
    }

• 對于 Huge 規(guī)格類型，只考慮是否需要進(jìn)行內(nèi)存對齊，即需要的內(nèi)存塊大小必須是某個(gè)數(shù)倍數(shù)；這個(gè)數(shù)必須是 2 的冪數(shù)。例如內(nèi)存對齊數(shù)directMemoryCacheAlignment 是16，那么內(nèi)存塊大小必須能整除 16，也就是低四位都是 0。
• Small 和 Normal 規(guī)格類型，它們相隔都是1倍，那么只需要尋找最近的 2 的冪數(shù)就行了。
• Tiny 規(guī)格類型，最小值是16，因此只需要16的倍數(shù)就可以了。

3.3.3 allocateNormal 方法

    private void allocateNormal(PooledByteBuf<T> buf, int reqCapacity, int normCapacity) {
        // 從 PoolChunkList 中分配內(nèi)存
        if (q050.allocate(buf, reqCapacity, normCapacity) || q025.allocate(buf, reqCapacity, normCapacity) ||
            q000.allocate(buf, reqCapacity, normCapacity) || qInit.allocate(buf, reqCapacity, normCapacity) ||
            q075.allocate(buf, reqCapacity, normCapacity)) {
            return;
        }

        // 如果沒有從 PoolChunkList 中分配內(nèi)存，
        // 那么就要新創(chuàng)建 PoolChunk 對象，
        // 默認(rèn)情況下 pageSize=8192 maxOrder=11 pageShifts=13 chunkSize=16777216
        PoolChunk<T> c = newChunk(pageSize, maxOrder, pageShifts, chunkSize);
        boolean success = c.allocate(buf, reqCapacity, normCapacity);
        assert success;
        // 將新創(chuàng)建的 PoolChunk 添加到 qInit 中
        qInit.add(c);
    }

• 先從 PoolChunkList 中尋找可用 PoolChunk 進(jìn)行內(nèi)存分配。
• 找不到，那么就創(chuàng)建新的 PoolChunk 實(shí)例。
• 通過 PoolChunk 的 allocate(buf, reqCapacity, normCapacity) 方法進(jìn)行內(nèi)存分配；這個(gè)上面已經(jīng)介紹。
• 最后將這個(gè) PoolChunk 添加到 PoolChunkList 中。

3.3.4 allocateHuge 方法

    private void allocateHuge(PooledByteBuf<T> buf, int reqCapacity) {
        // 創(chuàng)建 Huge 類型的PoolChunk，不會(huì)放在內(nèi)存池中 unpooled = true
        PoolChunk<T> chunk = newUnpooledChunk(reqCapacity);
        activeBytesHuge.add(chunk.chunkSize());
        buf.initUnpooled(chunk, reqCapacity);
        allocationsHuge.increment();
    }

Huge 規(guī)格的內(nèi)存塊是不會(huì)進(jìn)入內(nèi)存池的。

3.3.5 釋放內(nèi)存塊

    void free(PoolChunk<T> chunk, ByteBuffer nioBuffer, long handle, int normCapacity, PoolThreadCache cache) {
        if (chunk.unpooled) {
            // 非池中內(nèi)存塊，直接回收
            int size = chunk.chunkSize();
            destroyChunk(chunk);
            activeBytesHuge.add(-size);
            deallocationsHuge.increment();
        } else {
            SizeClass sizeClass = sizeClass(normCapacity);
            // 根據(jù)不同內(nèi)存規(guī)格，將回收的內(nèi)存塊優(yōu)先放入線程緩存中
            if (cache != null && cache.add(this, chunk, nioBuffer, handle, normCapacity, sizeClass)) {
                // cached so not free it.
                return;
            }

            // 線程緩存已經(jīng)滿了，那么就釋放內(nèi)存塊
            freeChunk(chunk, handle, sizeClass, nioBuffer);
        }
    }

 void freeChunk(PoolChunk<T> chunk, long handle, SizeClass sizeClass, ByteBuffer nioBuffer) {
        final boolean destroyChunk;
        synchronized (this) {
            switch (sizeClass) {
            case Normal:
                ++deallocationsNormal;
                break;
            case Small:
                ++deallocationsSmall;
                break;
            case Tiny:
                ++deallocationsTiny;
                break;
            default:
                throw new Error();
            }
            // 調(diào)用 PoolChunkList 方法進(jìn)行內(nèi)存塊釋放，需要改變 PoolChunkList 中的一些值
            destroyChunk = !chunk.parent.free(chunk, handle, nioBuffer);
        }
        if (destroyChunk) {
            // destroyChunk not need to be called while holding the synchronized lock.
            destroyChunk(chunk);
        }
    }

• Huge 規(guī)格類型的內(nèi)存塊直接釋放。
• Tiny,Small和Normal 規(guī)格類型的內(nèi)存塊，優(yōu)先放入線程緩存中，如果對應(yīng)的線程緩存已經(jīng)滿了，那么才釋放。