同步操作将从 doocs/source-code-hunter 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
该文所涉及的 netty 源码版本为 4.1.16。
在 Netty 的内存池的 PoolChunk 中,先要明确以下几个概念。
2^maxOrder * pageSize
,其中 2^maxOrder 是 PoolChunk 中的完全二叉树叶子结点的数量,pageSize 则是单个 page 的大小。综合如上所述,举一个数字上的例子,默认情况下,单个 Page 的大小为 8192,也就是 8kb,maxOrder 默认情况下是 11,因此在这个情况下 PoolChunk 中的二叉树的叶子节点数量是 2048,chunkSize 的大小则是 2048*8kb 为 16M。
PoolChunk 中的 page 通过一颗完全二叉树来达到快速访达及操作,而不需要通过 O(n)的时间复杂度来进行遍历,并耗费相当大的空间来记录各个 page 的使用情况。一颗完全二叉树的结构如下所示:
在这棵树的帮助下,当我们要申请 x 大小的内存的时候 ,得到比 x 最接近的 chunkSize/2^k 的大小,也就是说只要从左开始找到 k 层第一个没有被使用的节点即可开始将其子树的叶子结点的 page 进行分配。
单依靠上述的完全二叉树是无法达到内存池设计的目的的,因为缺少了 page 的使用情况,仍旧需要一个数据结构来辅助记录各个节点的使用情况。
PoolChunk 中还给出了一个 byte 数组 memoryMap,大小为完全二叉树所有节点的个数,在之前的例子中这个 byte 数组就为 4096。在初始情况下,这个数组每个位置上的初始指为该位置的节点在完全二叉树中的高度。因此,这个数组 memoryMap 就有了以下几种状态。
private int allocateNode(int d) {
int id = 1;
int initial = - (1 << d); // has last d bits = 0 and rest all = 1
byte val = value(id);
if (val > d) { // unusable
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);
if (val > d) {
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);
setValue(id, unusable); // mark as unusable
updateParentsAlloc(id);
return id;
}
allocateNode(int d)方法用来在完全二叉树中以从左开始的顺序获取一颗高度为 d 的没有被使用过的子树。具体顺序如下:
private long allocateRun(int normCapacity) {
int d = maxOrder - (log2(normCapacity) - pageShifts);
int id = allocateNode(d);
if (id < 0) {
return id;
}
freeBytes -= runLength(id);
return id;
}
allocateRun()方法就是在上文的 allocateNode()的前提下,根据指定的大小的内存在二叉树上分配指定大小的子树。比如说在上述 16M 大小每个 page8kb 的 chunk 中寻求 64k 的内存的时候,需要 8 个 page 叶子结点,那么就是需要一个高度为 4 的完全二叉树,那么也就是只要在 PoolChunk 中通过 allocateNode()方法从完全二叉树的第 7 层开始从左往右找到一颗可以使用的子树即可。
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.
PoolSubpage<T> head = arena.findSubpagePoolHead(normCapacity);
synchronized (head) {
int d = maxOrder; // subpages are only be allocated from pages i.e., leaves
int id = allocateNode(d);
if (id < 0) {
return id;
}
final PoolSubpage<T>[] subpages = this.subpages;
final int pageSize = this.pageSize;
freeBytes -= pageSize;
int subpageIdx = subpageIdx(id);
PoolSubpage<T> subpage = subpages[subpageIdx];
if (subpage == null) {
subpage = new PoolSubpage<T>(head, this, id, runOffset(id), pageSize, normCapacity);
subpages[subpageIdx] = subpage;
} else {
subpage.init(head, normCapacity);
}
return subpage.allocate();
}
}
当向 PoolChunk 申请的内存大小小于 pageSize 的时候,将直接通过 allocateSubpage()方法尝试直接在叶子结点,也就是二叉树的最后一层选择一个空的还未使用的叶子结点,在选择的叶子结点中构造一个 PoolSubPage 来返回,而不需要耗费整整一个叶子结点导致内存占用浪费。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。