Package one.nio.mem

Class Malloc

  • All Implemented Interfaces:
    Allocator, MallocMXBean
    Direct Known Subclasses:
    MallocMT
    public class Malloc
extends java.lang.Object
implements Allocator, MallocMXBean
    A simplified implementation of Doug Lea's Memory Allocator. Allocates up to 25% larger memory chunks rounded to the bin size.

    Memory format:

    • SIGNATURE int64 format version magic bytes
    • CAPACITY int64 size of the allocated memory
    • BASE int64 base address of the memory
    • padding up to 64 bytes
    • Bins:
      • BIN_0_CHUNK int64
      • BIN_1_CHUNK int64
      • ...
      • BIN_N_CHUNK int64

    There are 2 types of chunks: free and occupied. Chunks are aligned to 8 byte boundary.

    Free chunk format (8 byte header + 2 x 64-bit references = 24 bytes min chunk): 

    
 +--------------+--------------+
 | size (int32) | left (int32) |
 +--------------+--------------+
 |         next (int64)        |
 +-----------------------------+
 |       previous (int64)      |
 +-----------------------------+
    left is the offset to the beginning of a previous chunk. Free chunks have MSB of the size unset. Free chunks are linked by double-linked lists (using next and previous) starting from the corresponding bin.

    Occupied chunk format (8 byte header + payload): 

    
 +--------------+--------------+
 | size (int32) | left (int32) |
 +--------------+--------------+
 |          user data          |
 +-----------------------------+
    Occupied chunks have MSB of the size set.

    Invariants:

    • Each chunk is linked to the bin according to chunk size
    • Two free chunks are coalesced if they are physical neighbours
    • Free chunks are always interleaved with occupied chunks

    Bins contain chunks with sizes from the bin size inclusive up to the next bin size exclusive (see chooseBin(int)).

    malloc(int):

    1. Round the user requested size up to the nearest bin size
    2. Start looking for the first chunk starting from the corresponding bin up to the last bin:
      • If there is no chunk in the current bin, go to the next bin
      • If the first chunk is appropriately sized, remove it from the list of chunks and return it to the user
      • If the first chunk is too large, split it, insert the tail into the list of chunks in the corresponding bin and return the head to the user
      • If nothing is found, throw OutOfMemoryException

    free(long):

    1. Try to coalesce with left and right neighbours if they are free
    2. Insert the resulting chunk into the corresponding bin

    • Constructor Detail

      • Malloc

        public Malloc​(long capacity)

      • Malloc

        public Malloc​(long base,
              long capacity)

    • Method Detail

      • getBin

        static int getBin​(int size)

      • binSize

        static int binSize​(int bin)

      • chooseBin

        static int chooseBin​(int size)

      • base

        public final long base()

      • calloc

        public long calloc​(int size)
        Specified by:
        calloc in interface Allocator

      • malloc

        public long malloc​(int size)
        Specified by:
        malloc in interface Allocator

      • mallocImpl

        final long mallocImpl​(int bin,
                      int size)

      • free

        public void free​(long address)
        Specified by:
        free in interface Allocator

      • allocatedSize

        public int allocatedSize​(long address)

      • verify

        public void verify()
        Description copied from interface: Allocator
        Verify the layout of the heap. Expensive operation, used only for debugging purposes.
        Specified by:
        verify in interface Allocator

      • init

        void init()

      • relocate

        private void relocate​(long delta)

      • upgradeBinFormat

        private void upgradeBinFormat()

      • addBoundary

        private void addBoundary​(long address)

      • getChunk

        private long getChunk​(int bin,
                      int size)

      • addFreeChunk

        private void addFreeChunk​(long address,
                          int size)

      • removeFreeChunk

        private void removeFreeChunk​(long address)