Class Malloc

java.lang.Object
one.nio.mem.Malloc
All Implemented Interfaces:
Allocator, MallocMXBean
Direct Known Subclasses:
MallocMT
public class Malloc extends 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

  • Field Details

  • Constructor Details

    • Malloc

      public Malloc(long capacity)

    • Malloc

      public Malloc(long base, long capacity)

    • Malloc

      public Malloc(MappedFile mmap)

  • Method Details

    • getBin

      static int getBin(int size)

    • binSize

      static int binSize(int bin)

    • chooseBin

      static int chooseBin(int size)

    • base

      public final long base()

    • getTotalMemory

      public long getTotalMemory()
      Specified by:
      getTotalMemory in interface MallocMXBean

    • getFreeMemory

      public long getFreeMemory()
      Specified by:
      getFreeMemory in interface MallocMXBean

    • getUsedMemory

      public long getUsedMemory()
      Specified by:
      getUsedMemory in interface MallocMXBean

    • 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)