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>
arena
private java.util.Deque<java.nio.ByteBuffer>
cachedNioBuffers
private int
chunkSize
private byte[]
depthMap
(package private) int
freeBytes
private static int
INTEGER_SIZE_MINUS_ONE
private int
log2ChunkSize
private int
maxOrder
private int
maxSubpageAllocs
(package private) T
memory
private byte[]
memoryMap
(package private) PoolChunk<T>
next
(package private) int
offset
private int
pageShifts
private int
pageSize
(package private) PoolChunkList<T>
parent
(package private) PoolChunk<T>
prev
private int
subpageOverflowMask
Used to determine if the requested capacity is equal to or greater than pageSize.private PoolSubpage<T>[]
subpages
(package private) boolean
unpooled
private byte
unusable
Used to mark memory as unusable
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) boolean
allocate(PooledByteBuf<T> buf, int reqCapacity, int normCapacity, PoolThreadCache threadCache)
private int
allocateNode(int d)
Algorithm to allocate an index in memoryMap when we query for a free node at depth dprivate long
allocateRun(int normCapacity)
Allocate a run of pages (>=1)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 PoolChunkprivate static int
bitmapIdx(long handle)
int
chunkSize()
Return the size of the chunk in bytes, this is the maximum of bytes that can be served out of the chunk.private byte
depth(int id)
(package private) void
destroy()
(package private) 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 allocationsint
freeBytes()
Return the number of free bytes in the chunk.(package private) void
initBuf(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int reqCapacity, PoolThreadCache threadCache)
private void
initBufWithSubpage(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int bitmapIdx, int reqCapacity, PoolThreadCache threadCache)
(package private) void
initBufWithSubpage(PooledByteBuf<T> buf, java.nio.ByteBuffer nioBuffer, long handle, int reqCapacity, PoolThreadCache threadCache)
private static int
log2(int val)
private static int
memoryMapIdx(long handle)
private PoolSubpage<T>[]
newSubpageArray(int size)
private int
runLength(int id)
private int
runOffset(int id)
private void
setValue(int id, byte val)
private int
subpageIdx(int memoryMapIdx)
java.lang.String
toString()
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 spaceprivate 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 * 2int
usage()
Return the percentage of the current usage of the chunk.private int
usage(int freeBytes)
private byte
value(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:PoolChunkMetric
Return the percentage of the current usage of the chunk.- Specified by:
usage
in 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:PoolChunkMetric
Return the size of the chunk in bytes, this is the maximum of bytes that can be served out of the chunk.- Specified by:
chunkSize
in interfacePoolChunkMetric
-
freeBytes
public int freeBytes()
Description copied from interface:PoolChunkMetric
Return the number of free bytes in the chunk.- Specified by:
freeBytes
in interfacePoolChunkMetric
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
destroy
void destroy()
-
-