BitmappedBlock

BitmappedBlock implements a simple heap consisting of one contiguous area of memory organized in blocks, each of size theBlockSize. A block is a unit of allocation. A bitmap serves as bookkeeping data, more precisely one bit per block indicating whether that block is currently allocated or not.

Passing NullAllocator as ParentAllocator (the default) means user code manages allocation of the memory block from the outside; in that case BitmappedBlock must be constructed with a void[] preallocated block and has no responsibility regarding the lifetime of its support underlying storage. If another allocator type is passed, BitmappedBlock defines a destructor that uses the parent allocator to release the memory block. That makes the combination of AllocatorList, BitmappedBlock, and a back-end allocator such as MmapAllocator a simple and scalable solution for memory allocation.

There are advantages to storing bookkeeping data separated from the payload (as opposed to e.g. using AffixAllocator to store metadata together with each allocation). The layout is more compact (overhead is one bit per block), searching for a free block during allocation enjoys better cache locality, and deallocation does not touch memory around the payload being deallocated (which is often cold).

Allocation requests are handled on a first-fit basis. Although linear in complexity, allocation is in practice fast because of the compact bookkeeping representation, use of simple and fast bitwise routines, and caching of the first available block position. A known issue with this general approach is fragmentation, partially mitigated by coalescing. Since BitmappedBlock does not need to maintain the allocated size, freeing memory implicitly coalesces free blocks together. Also, tuning blockSize has a considerable impact on both internal and external fragmentation.

The size of each block can be selected either during compilation or at run time. Statically-known block sizes are frequent in practice and yield slightly better performance. To choose a block size statically, pass it as the blockSize parameter as in BitmappedBlock!(Allocator, 4096). To choose a block size parameter, use BitmappedBlock!(Allocator, chooseAtRuntime) and pass the block size to the constructor.

struct BitmappedBlock (

size_t theBlockSize

uint theAlignment = platformAlignment

ParentAllocator = NullAllocator

) {

import stdx.allocator.internal : Ternary;;

import mir.functional : RefTuple;;

alias blockSize = theBlockSize;

static if(!(theBlockSize != chooseAtRuntime))

uint blockSize [@property getter];

static if(!(theBlockSize != chooseAtRuntime))

uint blockSize [@property setter];

alias alignment = theAlignment;

static if(stateSize!ParentAllocator)

ParentAllocator parent;

alias parent = ParentAllocator.instance;

this(ubyte[] data);

this(size_t capacity);

this(ubyte[] data, uint blockSize);

~this();

size_t goodAllocSize(size_t n);

void[] allocate(size_t s);

void[] alignedAllocate(size_t n, uint a);

void[] allocateAll();

Ternary owns(void[] b);

bool expand(void[] b, size_t delta);

bool reallocate(void[] b, size_t newSize);

bool alignedReallocate(void[] b, size_t newSize, uint a);

bool deallocate(void[] b);

bool deallocateAll();

Ternary empty();

debug(std_experimental_allocator_bitmapped_block)

void dump();

}

Constructors

this this(ubyte[] data)
this(size_t capacity): Constructs a block allocator given a hunk of memory, or a desired capacity in bytes.
this this(ubyte[] data, uint blockSize): Undocumented in source.

Destructor

~this ~this(): If ParentAllocator is not NullAllocator and defines deallocate, the destructor is defined to deallocate the block held.

Members

Aliases

alignment alias alignment = theAlignment: The alignment offered is user-configurable statically through parameter theAlignment, defaulted to platformAlignment.
blockSize alias blockSize = theBlockSize: If blockSize == chooseAtRuntime, BitmappedBlock offers a read/write property blockSize. It must be set before any use of the allocator. Otherwise (i.e. theBlockSize is a legit constant), blockSize is an alias for theBlockSize. Whether constant or variable, must also be a multiple of alignment. This constraint is asserted statically and dynamically.
parent alias parent = ParentAllocator.instance: Undocumented in source.

Functions

alignedAllocate void[] alignedAllocate(size_t n, uint a): Allocates a block with specified alignment a. The alignment must be a power of 2. If a <= alignment, function forwards to allocate. Otherwise, it attempts to overallocate and then adjust the result for proper alignment. In the worst case the slack memory is around two blocks.
alignedReallocate bool alignedReallocate(void[] b, size_t newSize, uint a): Reallocates a block previously allocated with alignedAllocate. Contractions do not occur in place.
allocate void[] allocate(size_t s): Allocates s bytes of memory and returns it, or null if memory could not be allocated.
allocateAll void[] allocateAll(): If the BitmappedBlock object is empty (has no active allocation), allocates all memory within and returns a slice to it. Otherwise, returns null (i.e. no attempt is made to allocate the largest available block).
deallocate bool deallocate(void[] b): Deallocates a block previously allocated with this allocator.
deallocateAll bool deallocateAll(): Forcibly deallocates all memory allocated by this allocator, making it available for further allocations. Does not return memory to ParentAllocator.
dump void dump(): Undocumented in source. Be warned that the author may not have intended to support it.
empty Ternary empty(): Returns Ternary.yes if no memory is currently allocated with this allocator, otherwise Ternary.no. This method never returns Ternary.unknown.
expand bool expand(void[] b, size_t delta): Expands an allocated block in place.
goodAllocSize size_t goodAllocSize(size_t n): Returns the actual bytes allocated when n bytes are requested, i.e. n.roundUpToMultipleOf(blockSize).
owns Ternary owns(void[] b): Returns Ternary.yes if b belongs to the BitmappedBlock object, Ternary.no otherwise. Never returns Ternary.unkown. (This method is somewhat tolerant in that accepts an interior slice.)
reallocate bool reallocate(void[] b, size_t newSize): Reallocates a previously-allocated block. Contractions occur in place.

Properties

blockSize uint blockSize [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
blockSize uint blockSize [@property setter]: Undocumented in source. Be warned that the author may not have intended to support it.

Variables

parent ParentAllocator parent;: The parent allocator. Depending on whether ParentAllocator holds state or not, this is a member variable or an alias for ParentAllocator.instance.

Examples

// Create a block allocator on top of a 10KB stack region.
import stdx.allocator.building_blocks.region : InSituRegion;
InSituRegion!(10_240, 64) r;
auto a = BitmappedBlock!(64, 64)(cast(ubyte[])(r.allocateAll()));
static assert(__traits(hasMember, InSituRegion!(10_240, 64), "allocateAll"));
const b = a.allocate(100);
assert(b.length == 100);