转载

Netty内存池之PoolSubpage详解

在Netty内存池中，内存大小在8KB~16M的内存是由PoolChunk维护的，小于8KB的内存则是由PoolSubpage来维护的。而对于低于8KB的内存，Netty也是将其分成了两种情况0~496byte和512byte~8KB。其中，0~496byte的内存是由一个名称为tinySubpagePools的PoolSubpage的数组维护的，512byte~8KB的内存则是由名称为smallSubpagePools的PoolSubpage数组来维护的。本文首先会对tinySubpagePools和smallSubpagePools的整体结构进行说明，然后会讲解Netty是如何仅仅通过抽象出一种PoolSubpage的数据结构来实现对两种不同的内存区间的管理的，最后本文会从PoolSubpage的源码的角度来讲解PoolSubpage的实现原理。

1. tinySubpagePools和smallSubpagePools整体结构

这里我们直接查看这两个PoolSubpage数组的结构：

tinySubpagePools和smallSubpagePools在结构上都是由一个数组来实现的，只是tinySubpagePools的数组长度为32，但是其真正使用的只有其下标在1~31内的节点。而smallSubpagePools的数组长度为4，其每个节点都会使用；
在存储数据内存的划分上，图中，我们可以看到，两个数组的每个节点都是一个PoolSubpage的单向链表，而节点前面我们都使用了一个数字进行标注。这个数字的意思是，这个节点所对应的链表所能够申请的内存最大值，这样就可以达到将不同大小的内存申请进行了划分，并且加锁的时候可以减小锁的粒度，从而减小竞争。这里比如我们申请8byte的内存，那么其就会到tinySubpagePools的下标为1的链表中进行申请，需要注意的是，如果该下标位置的链表是空的，那么就会创建一个，但是一定会保证是在该下标处进行申请；
tinySubpagePools和smallSubpagePools的最大区别在于两者对于内存的划分。图中我们可以看到，tinySubpagePools的每个节点所指代的内存相差16byte，而smallSubpagePools的内存则是2的指数次幂；
在对内存的管理上，这里每一个PoolSubpage也都是维护的一个内存池，它们的大小永远都是8KB。这里比如tinySubpagePools的第1号位的每一个PoolSubpage，其能够申请的内存最大为16byte，由于每一个PoolSubpage的大小都为8KB，因而其链表中每个PoolSubpage都维护了8192 / 16 = 512个内存块；由比如smallSubpagePools的第2号位的每一个PoolSubpage，其能够申请的内存最大为2048byte，因而其链表中每一个PoolSubpage都维护了8192 / 2048 = 4个内存块；

在进行内存申请时，用户会传入一个其所希望的内存大小，但实际获取的大小，Netty都会进行扩容，这里我们以50byte内存的申请为例进行讲解：

首先Netty会判断目标内存，这里为50byte，是否小于8KB，只有小于8KB的内存才会交由tinySubpagePools和smallSubpagePools进行申请；进行了如此判断之后，Netty还会判断其是否小于512byte，从而判断其是应该从tinySubpagePools还是从smallSubpagePools中进行申请，这里50小于512，因而是从tinySubpagePools中进行申请；
将目标内存进行扩容，因为已经知道其是从tinySubpagePools中进行申请，由于tinySubpagePools中的内存阶梯是16的倍数，因而会将目标内存扩容为大于其值的第一个16的倍数，这里也就是64。如果目标内存是在smallSubpagePools中，那么就会将其扩容为大于该值的第一个2的指数次幂；
根据扩容后的大小计算出其在数组中的位置，这里就是64 / 16 = 4(在Netty源码中是直接将目标内存向右移动4位，即64 »> 4，这样也能达到除以16的目的)；
在目标链表中找到第一个PoolSubpage，从其剩余的内存中划分目标内存块，这里需要注意的是，第一个PoolSubpage中是一定会存在可划分的内存块的，因为如果链表中某个PoolSubpage中没有剩余的可划分内存块时，其将会被从当前链表中移除。关于PoolSubpage内存块的划分，后面会进行详细讲解。

2. PoolSubpage实现原理讲解

对于PoolSubpage的实现原理，其内部本质上是使用一个位图索引来表征某个内存块是否已经被占用了的。前面我们讲到，每个PoolSubpage的总内存大小都是8192byte，这里我们以tinySubpagePools的第1号位的大小为16字节的PoolSubpage为例进行讲解(其实从这里就可以看出，前面我们图中数组前面的数字就是表示当前节点链表中PoolSubpage所划分的内存块的大小)。

由于每个内存块大小为16字节，而总大小为8192字节，因而总会有8192 / 16 = 512个内存块。为了对这些内存块进行标记，那么就需要一个长度为512的二进制位图索引进行表征。Netty并没有使用jdk提供的BitMap这个类，而是使用了一个long型的数组。由于一个long占用的字节数为64，因而总共需要512 / 64 = 8个long型数字来表示。这也就是PoolSubpage中的long[] bitmap属性的作用。下图表示了PoolSubpage使用位图索引表示每个内存块是否被使用的一个示意图：

Netty内存池之PoolSubpage详解

这里需要说明的是，我们这里是以每个内存块的大小为16为例进行讲解的，而16是PoolSubpage所能维护的最小内存块，对于其他大小的内存块，其个数是比512要小的，但是PoolSubpage始终会声明一个长度为8的long型数组，并且声明一个bitmapLength来记录当前PoolSubpage中有几个long是用于标志内存块使用情况的。

3. PoolSubpage源码讲解

对于PoolSubpage的实现原理，我们这里首先对其各个属性进行讲解：

// 记录当前PoolSubpage的8KB内存块是从哪一个PoolChunk中申请到的
final PoolChunk<T> chunk;
// 当前PoolSubpage申请的8KB内存在PoolChunk中memoryMap中的下标索引
private final int memoryMapIdx;
// 当前PoolSubpage占用的8KB内存在PoolChunk中相对于叶节点的起始点的偏移量
private final int runOffset;
// 当前PoolSubpage的页大小，默认为8KB
private final int pageSize;
// 存储当前PoolSubpage中各个内存块的使用情况
private final long[] bitmap;

PoolSubpage<T> prev;	// 指向前置节点的指针
PoolSubpage<T> next;	// 指向后置节点的指针

boolean doNotDestroy;	// 表征当前PoolSubpage是否已经被销毁了
int elemSize;	// 表征每个内存块的大小，比如我们这里的就是16
private int maxNumElems;	// 记录内存块的总个数
private int bitmapLength;	// 记录总共可使用的bitmap数组的元素的个数
// 记录下一个可用的节点，初始为0，只要在该PoolSubpage中申请过一次内存，就会更新为-1，
// 然后一直不会发生变化
private int nextAvail;
// 剩余可用的内存块的个数
private int numAvail;

对于各个属性的初始化，我们可以通过构造函数进行讲解，如下是其构造函数源码：

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;	// 初始化当前PoolSubpage总内存大小，默认为8KB
  // 计算bitmap长度，这里pageSize >>> 10其实就是将pageSize / 1024，得到的是8，
  // 从这里就可以看出，无论内存块的大小是多少，这里的bitmap长度永远是8，因为pageSize始终是不变的
  bitmap = new long[pageSize >>> 10];
  // 对其余的属性进行初始化
  init(head, elemSize);
}

void init(PoolSubpage<T> head, int elemSize) {
  doNotDestroy = true;
  // elemSize记录了当前内存块的大小
  this.elemSize = elemSize;
  if (elemSize != 0) {
    // 初始时，numAvail记录了可使用的内存块个数，其个数可以通过pageSize / elemSize计算，
    // 我们这里就是8192 / 16 = 512。maxNumElems指的是最大可使用的内存块个数，
    // 初始时其是与可用内存块个数一致的。
    maxNumElems = numAvail = pageSize / elemSize;
    nextAvail = 0;	// 初始时，nextAvail是0
    // 这里bitmapLength记录了可以使用的bitmap的元素个数，这是因为，我们示例使用的内存块大小是16，
    // 因而其总共有512个内存块，需要8个long才能记录，但是对于一些大小更大的内存块，比如smallSubpagePools
    // 中内存块为1024字节大小，那么其只有8192 / 1024 = 8个内存块，也就只需要一个long就可以表示，
    // 此时bitmapLength就是8。
    // 这里的计算方式应该是bitmapLength = maxNumElems / 64，因为64是一个long的总字节数，
    // 但是Netty将其进行了优化，也就是这里的maxNumElems >>> 6，这是因为2的6次方正好为64
    bitmapLength = maxNumElems >>> 6;
    // 这里(maxNumElems & 63) != 0就是判断元素个数是否小于64，如果小于，则需要将bitmapLegth加一。
    // 这是因为如果其小于64，前面一步的位移操作结果为0，但其还是需要一个long来记录
    if ((maxNumElems & 63) != 0) {
      bitmapLength++;
    }

    // 对bitmap数组的值进行初始化
    for (int i = 0; i < bitmapLength; i++) {
      bitmap[i] = 0;
    }
  }
  
  // 将当前PoolSubpage添加到PoolSubpage的链表中，也就是最开始图中的链表
  addToPool(head);
}

这里对于PoolSubpage的初始化主要是对bitmap、numAvail、bitmapLength的初始化，下面我们看看其是如何通过这些属性来从PoolSubpage中申请内存的：

// 对于allocate()方法，其没有传入任何参数是因为当前PoolSubpage所能申请的内存块大小在构造方法中
// 已经通过elemSize指定了。
// 当前方法返回的是一个long型整数，这里是将要申请的内存块使用了一个long型变量进行表征了。由于一个内存块
// 是否使用是通过一个long型整数表示的，因而，如果想要表征当前申请到的内存块是这个long型整数中的哪一位，
// 只需要一个最大为63的整数即可(long最多为64位)，这只需要long型数的低6位就可以表示，由于我们使用的是一个
// long型数组，因而还需要记录当前是在数组中第几个元素，由于数组长度最多为8，因而对于返回值的7~10位则是记录
// 了当前申请的内存块是在bitmap数组的第几个元素中。总结来说，返回值的long型数的高32位中的低6位
// 记录了当前申请的是是bitmap中某个long的第几个位置的内存块，而高32位的7~10位则记录了申请的是bitmap数组
// 中的第几号元素。
// 这里说返回值的高32位是因为其低32位记录了当前8KB内存块是在PoolChunk中具体的位置，关于这一块的算法
// 读者可以阅读本人前面对PoolChunk进行讲解的文章
long allocate() {
  // 如果elemSize为0，则直接返回0
  if (elemSize == 0) {
    return toHandle(0);
  }

  // 如果当前PoolSubpage没有可用的元素，或者已经被销毁了，则返回-1
  if (numAvail == 0 || !doNotDestroy) {
    return -1;
  }

  // 计算下一个可用的内存块的位置
  final int bitmapIdx = getNextAvail();
  int q = bitmapIdx >>> 6;	// 获取该内存块是bitmap数组中的第几号元素
  int r = bitmapIdx & 63;		// 获取该内存块是bitmap数组中q号位元素的第多少位
  bitmap[q] |= 1L << r;	// 将bitmap数组中q号元素的目标内存块位置标记为1，表示已经使用

  // 如果当前PoolSubpage中可用的内存块为0，则将其从链表中移除
  if (--numAvail == 0) {
    removeFromPool();
  }

  // 将得到的bitmapIdx放到返回值的高32位中
  return toHandle(bitmapIdx);
}

这里allocate()方法首先会计算下一个可用的内存块的位置，然后将该位置标记为1，最后将得到的位置数据放到返回值的高32位中。这里我们继续看其是如何计算下一个可用的位置的，如下是getNextAvail()的源码：

private int getNextAvail() {
  int nextAvail = this.nextAvail;
  // 如果是第一次尝试获取数据，则直接返回bitmap第0号位置的long的第0号元素，
  // 这里nextAvail初始时为0，在第一次申请之后就会变为-1，后面将不再发生变化，
  // 通过该变量可以判断是否是第一次尝试申请内存
  if (nextAvail >= 0) {
    this.nextAvail = -1;
    return nextAvail;
  }
  
  // 如果不是第一次申请内存，则在bitmap中进行遍历获取
  return findNextAvail();
}

private int findNextAvail() {
  final long[] bitmap = this.bitmap;
  final int bitmapLength = this.bitmapLength;
  // 这里的基本思路就是对bitmap数组进行遍历，首先判断其是否有未使用的内存是否全部被使用过
  // 如果有未被使用的内存，那么就在该元素中找可用的内存块的位置
  for (int i = 0; i < bitmapLength; i++) {
    long bits = bitmap[i];
    if (~bits != 0) {	// 判断当前long型元素中是否有可用内存块
      return findNextAvail0(i, bits);
    }
  }
  return -1;
}

// 入参中i表示当前是bitmap数组中的第几个元素，bits表示该元素的值
private int findNextAvail0(int i, long bits) {
  final int maxNumElems = this.maxNumElems;
  final int baseVal = i << 6;	// 这里baseVal就是将当前是第几号元素放到返回值的第7~10号位置上

  // 对bits的0~63号位置进行遍历，判断其是否为0，为0表示该位置是可用内存块，从而将位置数据
  // 和baseVal进行或操作，从而得到一个表征目标内存块位置的整型数据
  for (int j = 0; j < 64; j++) {
    if ((bits & 1) == 0) {	// 判断当前位置是否为0，如果为0，则表示是目标内存块
      int val = baseVal | j;	// 将内存快的位置数据和其位置j进行或操作，从而得到返回值
      if (val < maxNumElems) {
        return val;
      } else {
        break;
      }
    }
    bits >>>= 1;	// 将bits不断的向右移位，以找到第一个为0的位置
  }
  return -1;
}

上面的查找过程非常的简单，其原理起始就是对bitmap数组进行遍历，首先判断当前元素是否有可用的内存块，如果有，则在该long型元素中进行遍历，找到第一个可用的内存块，最后将表征该内存块位置的整型数据返回。这里需要说明的是，上面判断bitmap中某个元素是否有可用内存块是使用的是 ~bits != 0 来计算的，该算法的原理起始就是，如果一个long中所有的内存块都被申请了，那么这个long必然所有的位都为1，从整体上，这个long型数据的值就为-1，而将其取反 ~bits 之后，值肯定就变为了0，因而这里只需要判断其取反之后是否等于0即可判断当前long型元素中是否有可用的内存块。

下面我们继续看PoolSubpage是如何对内存进行释放的，如下是free()方法的源码：

boolean free(PoolSubpage<T> head, int bitmapIdx) {
  if (elemSize == 0) {
    return true;
  }
  
  // 获取当前需要释放的内存块是在bitmap中的第几号元素
  int q = bitmapIdx >>> 6;
  // 获取当前释放的内存块是在q号元素的long型数的第几位
  int r = bitmapIdx & 63;
  // 将目标位置标记为0，表示可使用状态
  bitmap[q] ^= 1L << r;

  // 设置下一个可使用的数据
  setNextAvail(bitmapIdx);

  // numAvail如果等于0，表示之前已经被移除链表了，因而这里释放后需要将其添加到链表中
  if (numAvail++ == 0) {
    addToPool(head);
    return true;
  }

  // 如果可用的数量小于最大数量，则表示其还是在链表中，因而直接返回true
  if (numAvail != maxNumElems) {
    return true;
  } else {
    // else分支表示当前PoolSubpage中没有任何一个内存块被占用了
    // 这里如果当前PoolSubpage的前置节点和后置节点相等，这表示其都是默认的head节点，也就是
    // 说当前链表中只有一个可用于内存申请的节点，也就是当前PoolSubpage，这里就不会将其移除
    if (prev == next) {
      return true;
    }

    // 如果有多个节点，则将当前PoolSubpage移除
    doNotDestroy = false;
    removeFromPool();
    return false;
  }
}

可以看到，对于free()操作，主要是将目标位置标记为0，然后设置相关属性，并且判断是否需要将当前PoolSubpage添加到链表中或者从链表移除。