Skip to content

FixedAllocators

Brad Bebee edited this page Feb 13, 2020 · 1 revision

The RWStore allocates slots of storage in fixed size amounts. For example: 64, 128, 256, 512 and 1024 bytes big.

A FixedAllocator manages allocations for a specific size, for example, 512 bytes. This would be described as a 512 byte FixedAllocator.

When the RWStore receives a request for an allocation, it identifies a FixedAllocator via a free list of FixedAllocators for each allocation size.

Internally each FixedAllocator manages a list of Allocation Blocks.

Allocation Blocks

An Allocation Block is a contiguous region of the store file reserved for allocations of a specific size.

It has a start address, which encodes the offset in the file, and a bit array to indicate which slots are available for allocation.

The Bit Arrays

Unlike the malloc and free of the standard C library, the allocation algorithms of the Allocation Blocks are transaction aware.

This is achieved with the use of three bit arrays:

  • committed
  • live
  • transient

The committed bit array represents the allocated slots at the last commit.

The live bit array is initialized as a clone of the committed bits, and represents the current allocated and freed slots

The transient bit array represents an ORing of the committed and the live bits. Only slots which are available in the transient bit array can be allocated. This prevents the reallocation of committed storage before the next commit.

On commit, the live bits are cloned to the committed and transient bit arrays.

An example should help with Committed bits, Live bits and Transient bits: Initial state

C-00000000
L-00000000
T-00000000

Make 3 allocations

C-00000000
L-11100000
T-11100000

Commit

C-11100000
L-11100000
T-11100000

Free 2 allocations and make one new one C-11100000 L-00110000 T-11110000

Commit

C-00110000
L-00110000
T-00110000

Now let's make four new allocations

C-00110000
L-11111100
T-11111100

Now we will free one of the original committed slots and one of the newly allocated slots

C-00110000
L-11100100
T-11110100

Note that we are able to free the newly allocated slot in the transient bit array. This allocation is now available to be re-used before the next commit.

This is the key functionality of the FixedAllocator, to support reallocation between commits while protecting previously committed storage.

Addressing

Every FixedAllocator is given an index when created. And each FixedAllocator is stored in a 1K meta-allocation. Therefore the maximum number of bits that can possibly be addressed is < 8K (8 bits * 1K bytes) So, if 13 bits are all that is required to define the bit offset, this provides 19 bits to specify the FixedAllocator index, giving a maximum of 256K FixedAllocators.

 FFFFFFFFFFFFFFFFFFFBBBBBBBBBBBBB

This addressing scheme provides very quick offset encoding and direct access to free current allocations.

It is worth addressing whether the int-based address is an unnecessary restriction. If we make some simple approximations then at an average allocation of 512 bytes, and 6K useful bits per FixedAllocator the RWStore would support 6K * 256K = ~1536M allocations within a 80GB store. If the average allocation is 4K, then the store would support the same number of allocations but in a 640GB store.

Clone this wiki locally
You can’t perform that action at this time.