Skip to content
  • Philippe Gerum's avatar
    boilerplate: add heapmem allocator · dc63a21a
    Philippe Gerum authored
    This is the umpteenth incarnation of the McKusick allocator, aimed at
    replacing other allocators which have serious issues:
    
    - TLSF is fast but not that good when it comes to memory overhead with
      small sizes (i.e. < 512 bytes) on 64bit.
    
    - heapobj-pshared has decent overhead figures but may be insanely slow
      at deallocating blocks from large, hot heaps.
    
    - the Cobalt core allocator is even worse than heapobj-pshared in
      deallocating blocks, although the system heap should be generally
      small enough not to trigger the most pathological cases in practice,
      hopefully. Nevertheless, the performances are unacceptable.
    
    The original McKusick algorithm implements a quick fit allocation
    scheme, based on bucket management of ^2-sized chunks, which
    automatically switches to a page-based allocation method for blocks
    larger than twice the base page size.
    
    This variant maintains the free page list in AVL trees for fast
    lookups of multi-page memory ranges, and pages holding bucketed memory
    have a quick allocation bitmap to manage their blocks internally.
    
    The current implementation can replace TLSF for delivering
    process-local memory with similar performances but lesser overhead
    with small sizes. Most importantly, a kernel variant of HEAPMEM should
    replace the Cobalt core allocator. Likewise, heapobj-pshared which is
    beyond repair should be replaced with a process-shareable variant as
    well, assuming the average size and allocation patterns of real-time
    objects are similar in all contexts.
    dc63a21a