Class 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)
    • Constructor Summary

      Constructors 
      Constructor Description
      PoolChunk​(PoolArena<T> arena, T memory, int size, int offset)
      Creates a special chunk that is not pooled.
      PoolChunk​(PoolArena<T> arena, T memory, int pageSize, int maxOrder, int pageShifts, int chunkSize, int offset)  
    • 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 d
      private 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 PoolChunk
      private 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 allocations
      int 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 space
      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
      int usage()
      Return the percentage of the current usage of the chunk.
      private int usage​(int freeBytes)  
      private byte value​(int id)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • 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
      • 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
    • Constructor Detail

      • PoolChunk

        PoolChunk​(PoolArena<T> arena,
                  T memory,
                  int pageSize,
                  int maxOrder,
                  int pageShifts,
                  int chunkSize,
                  int offset)
      • PoolChunk

        PoolChunk​(PoolArena<T> arena,
                  T memory,
                  int size,
                  int offset)
        Creates a special chunk that is not pooled.
    • 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 interface PoolChunkMetric
      • usage

        private int usage​(int freeBytes)
      • 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
      • 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 interface PoolChunkMetric
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • destroy

        void destroy()