Package io.netty.buffer
Class PoolChunk<T>
- java.lang.Object
-
- io.netty.buffer.PoolChunk<T>
-
- All Implemented Interfaces:
PoolChunkMetric
final class PoolChunk<T> extends java.lang.Object implements PoolChunkMetric
Description of algorithm for PageRun/PoolSubpage allocation from PoolChunk Notation: The following terms are important to understand the code > page - a page is the smallest unit of memory chunk that can be allocated > chunk - a chunk is a collection of pages > in this code chunkSize = 2^{maxOrder} * pageSize To begin we allocate a byte array of size = chunkSize Whenever a ByteBuf of given size needs to be created we search for the first position in the byte array that has enough empty space to accommodate the requested size and return a (long) handle that encodes this offset information, (this memory segment is then marked as reserved so it is always used by exactly one ByteBuf and no more) For simplicity all sizes are normalized according to PoolArena#normalizeCapacity method This ensures that when we request for memory segments of size >= pageSize the normalizedCapacity equals the next nearest power of 2 To search for the first offset in chunk that has at least requested size available we construct a complete balanced binary tree and store it in an array (just like heaps) - memoryMap The tree looks like this (the size of each node being mentioned in the parenthesis) depth=0 1 node (chunkSize) depth=1 2 nodes (chunkSize/2) .. .. depth=d 2^d nodes (chunkSize/2^d) .. depth=maxOrder 2^maxOrder nodes (chunkSize/2^{maxOrder} = pageSize) depth=maxOrder is the last level and the leafs consist of pages With this tree available searching in chunkArray translates like this: To allocate a memory segment of size chunkSize/2^k we search for the first node (from left) at height k which is unused Algorithm: ---------- Encode the tree in memoryMap with the notation memoryMap[id] = x => in the subtree rooted at id, the first node that is free to be allocated is at depth x (counted from depth=0) i.e., at depths [depth_of_id, x), there is no node that is free As we allocate & free nodes, we update values stored in memoryMap so that the property is maintained Initialization - In the beginning we construct the memoryMap array by storing the depth of a node at each node i.e., memoryMap[id] = depth_of_id Observations: ------------- 1) memoryMap[id] = depth_of_id => it is free / unallocated 2) memoryMap[id] > depth_of_id => at least one of its child nodes is allocated, so we cannot allocate it, but some of its children can still be allocated based on their availability 3) memoryMap[id] = maxOrder + 1 => the node is fully allocated & thus none of its children can be allocated, it is thus marked as unusable Algorithm: [allocateNode(d) => we want to find the first node (from left) at height h that can be allocated] ---------- 1) start at root (i.e., depth = 0 or id = 1) 2) if memoryMap[1] > d => cannot be allocated from this chunk 3) if left node value <= h; we can allocate from left subtree so move to left and repeat until found 4) else try in right subtree Algorithm: [allocateRun(size)] ---------- 1) Compute d = log_2(chunkSize/size) 2) Return allocateNode(d) Algorithm: [allocateSubpage(size)] ---------- 1) use allocateNode(maxOrder) to find an empty (i.e., unused) leaf (i.e., page) 2) use this handle to construct the PoolSubpage object or if it already exists just call init(normCapacity) note that this PoolSubpage object is added to subpagesPool in the PoolArena when we init() it Note: ----- In the implementation for improving cache coherence, we store 2 pieces of information depth_of_id and x as two byte values in memoryMap and depthMap respectively memoryMap[id]= depth_of_id is defined above depthMap[id]= x indicates that the first node which is free to be allocated is at depth x (from root)
-
-
Field Summary
Fields Modifier and Type Field Description (package private) PoolArena<T>arenaprivate java.util.Deque<java.nio.ByteBuffer>cachedNioBuffersprivate intchunkSizeprivate byte[]depthMap(package private) intfreeBytesprivate static intINTEGER_SIZE_MINUS_ONEprivate intlog2ChunkSizeprivate intmaxOrderprivate intmaxSubpageAllocs(package private) Tmemoryprivate byte[]memoryMap(package private) PoolChunk<T>next(package private) intoffsetprivate intpageShiftsprivate intpageSize(package private) PoolChunkList<T>parent(package private) PoolChunk<T>prevprivate intsubpageOverflowMaskUsed to determine if the requested capacity is equal to or greater than pageSize.private PoolSubpage<T>[]subpages(package private) booleanunpooledprivate byteunusableUsed to mark memory as unusable
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) booleanallocate(PooledByteBuf<T> buf, int reqCapacity, int normCapacity, PoolThreadCache threadCache)private intallocateNode(int d)Algorithm to allocate an index in memoryMap when we query for a free node at depth dprivate longallocateRun(int normCapacity)Allocate a run of pages (>=1)private longallocateSubpage(int normCapacity)Create / initialize a new PoolSubpage of normCapacity Any PoolSubpage created / initialized here is added to subpage pool in the PoolArena that owns this PoolChunkprivate static intbitmapIdx(long handle)intchunkSize()Return the size of the chunk in bytes, this is the maximum of bytes that can be served out of the chunk.private bytedepth(int id)(package private) voiddestroy()(package private) voidfree(long handle, java.nio.ByteBuffer nioBuffer)Free a subpage or a run of pages When a subpage is freed from PoolSubpage, it might be added back to subpage pool of the owning PoolArena If the subpage pool in PoolArena has at least one other PoolSubpage of given elemSize, we can completely free the owning Page so it is available for subsequent allocationsintfreeBytes()Return the number of free bytes in the chunk.(package private) voidinitBuf(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int reqCapacity, PoolThreadCache threadCache)private voidinitBufWithSubpage(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int bitmapIdx, int reqCapacity, PoolThreadCache threadCache)(package private) voidinitBufWithSubpage(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int reqCapacity, PoolThreadCache threadCache)private static intlog2(int val)private static intmemoryMapIdx(long handle)private PoolSubpage<T>[]newSubpageArray(int size)private intrunLength(int id)private intrunOffset(int id)private voidsetValue(int id, byte val)private intsubpageIdx(int memoryMapIdx)java.lang.StringtoString()private voidupdateParentsAlloc(int id)Update method used by allocate This is triggered only when a successor is allocated and all its predecessors need to update their state The minimal depth at which subtree rooted at id has some free spaceprivate voidupdateParentsFree(int id)Update method used by free This needs to handle the special case when both children are completely free in which case parent be directly allocated on request of size = child-size * 2intusage()Return the percentage of the current usage of the chunk.private intusage(int freeBytes)private bytevalue(int id)
-
-
-
Field Detail
-
INTEGER_SIZE_MINUS_ONE
private static final int INTEGER_SIZE_MINUS_ONE
- See Also:
- Constant Field Values
-
memory
final T memory
-
unpooled
final boolean unpooled
-
offset
final int offset
-
memoryMap
private final byte[] memoryMap
-
depthMap
private final byte[] depthMap
-
subpages
private final PoolSubpage<T>[] subpages
-
subpageOverflowMask
private final int subpageOverflowMask
Used to determine if the requested capacity is equal to or greater than pageSize.
-
pageSize
private final int pageSize
-
pageShifts
private final int pageShifts
-
maxOrder
private final int maxOrder
-
chunkSize
private final int chunkSize
-
log2ChunkSize
private final int log2ChunkSize
-
maxSubpageAllocs
private final int maxSubpageAllocs
-
unusable
private final byte unusable
Used to mark memory as unusable
-
cachedNioBuffers
private final java.util.Deque<java.nio.ByteBuffer> cachedNioBuffers
-
freeBytes
int freeBytes
-
parent
PoolChunkList<T> parent
-
-
Method Detail
-
newSubpageArray
private PoolSubpage<T>[] newSubpageArray(int size)
-
usage
public int usage()
Description copied from interface:PoolChunkMetricReturn the percentage of the current usage of the chunk.- Specified by:
usagein interfacePoolChunkMetric
-
usage
private int usage(int freeBytes)
-
allocate
boolean allocate(PooledByteBuf<T> buf, int reqCapacity, int normCapacity, PoolThreadCache threadCache)
-
updateParentsAlloc
private void updateParentsAlloc(int id)
Update method used by allocate This is triggered only when a successor is allocated and all its predecessors need to update their state The minimal depth at which subtree rooted at id has some free space- Parameters:
id- id
-
updateParentsFree
private void updateParentsFree(int id)
Update method used by free This needs to handle the special case when both children are completely free in which case parent be directly allocated on request of size = child-size * 2- Parameters:
id- id
-
allocateNode
private int allocateNode(int d)
Algorithm to allocate an index in memoryMap when we query for a free node at depth d- Parameters:
d- depth- Returns:
- index in memoryMap
-
allocateRun
private long allocateRun(int normCapacity)
Allocate a run of pages (>=1)- Parameters:
normCapacity- normalized capacity- Returns:
- index in memoryMap
-
allocateSubpage
private long allocateSubpage(int normCapacity)
Create / initialize a new PoolSubpage of normCapacity Any PoolSubpage created / initialized here is added to subpage pool in the PoolArena that owns this PoolChunk- Parameters:
normCapacity- normalized capacity- Returns:
- index in memoryMap
-
free
void free(long handle, java.nio.ByteBuffer nioBuffer)Free a subpage or a run of pages When a subpage is freed from PoolSubpage, it might be added back to subpage pool of the owning PoolArena If the subpage pool in PoolArena has at least one other PoolSubpage of given elemSize, we can completely free the owning Page so it is available for subsequent allocations- Parameters:
handle- handle to free
-
initBuf
void initBuf(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int reqCapacity, PoolThreadCache threadCache)
-
initBufWithSubpage
void initBufWithSubpage(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int reqCapacity, PoolThreadCache threadCache)
-
initBufWithSubpage
private void initBufWithSubpage(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int bitmapIdx, int reqCapacity, PoolThreadCache threadCache)
-
value
private byte value(int id)
-
setValue
private void setValue(int id, byte val)
-
depth
private byte depth(int id)
-
log2
private static int log2(int val)
-
runLength
private int runLength(int id)
-
runOffset
private int runOffset(int id)
-
subpageIdx
private int subpageIdx(int memoryMapIdx)
-
memoryMapIdx
private static int memoryMapIdx(long handle)
-
bitmapIdx
private static int bitmapIdx(long handle)
-
chunkSize
public int chunkSize()
Description copied from interface:PoolChunkMetricReturn the size of the chunk in bytes, this is the maximum of bytes that can be served out of the chunk.- Specified by:
chunkSizein interfacePoolChunkMetric
-
freeBytes
public int freeBytes()
Description copied from interface:PoolChunkMetricReturn the number of free bytes in the chunk.- Specified by:
freeBytesin interfacePoolChunkMetric
-
toString
public java.lang.String toString()
- Overrides:
toStringin classjava.lang.Object
-
destroy
void destroy()
-
-