Design and implement Storage Allocator

[Robbepop]

Design: Storage Allocator

This issue tracks the design of an initial, simple and efficient storage allocator.

Problem

To dynamically create objects on the storage we have to have a way to allocate and deallocate them.

Since we are currently lacking an implementation of a storage allocator we cannot do these things in a sane and user friendly way.

Requirements

The requirements for a storage allocator are the following:

• Operations alloc and dealloc shall perform in constant time
• As few storage accesses as possible
• Allocations must not overlap

Design Basis

The Allocator trait that should be used for that purpose should ideally be something like this:

trait Allocator {
	/// Allocates a storage area.
	fn alloc(size: u32) -> Key;
	/// Deallocates a storage area.
	fn dealloc(at: Key);
}

Design 1: Cell & Chunk Allocator

This allocator is specialized in allocating only for single cells or chunks of cells of size 2^32.
One may think that this constraint is too limiting, however, since the entire storage space allows for 2^256 different cells we would still have 2^224 different chunks if we partitioned this space in 2^32 big chunks.

So for every alloc(1) this allocator tries to allocate for a single cell and for everything else it will default to allocating an entire 2^32 large chunk of cells.

This has some serious advantages.
By separating storage regions into single-cells and cell-chunk regions we do no longer have to memorize the exact size of an allocation.
For the underlying implementation we could use something similar to a stash that works on the contract storage.

Other ideas are welcome.

[Robbepop]

Commit d0800b2 adds an initial implementation of a storage allocator.

The design of this allocator foresees a generic Allocator trait to have multiple possible implementations.
Also it features a concrete CellChunkAlloc that is specialized for just two different allocation sizes: You can either allocate exactly one cell, or a chunk of 2^32 cells. There can be up to 2^32 allocated entities of both types at the same time. This should suffice all needs smart contracts could have.

The allocate and deallocate complexities of CellChunkAlloc are O(1).
It guarantees non aliasing allocated memory reagions but requires some storage slots itself.

Some open questions:

Should the allocator be merged with the Env trait or similar or should it be standalone in the form of a global fn alloc(size: u32) -> Key and fn deallocate(key: Key) free functions independent from a given environment?

[Robbepop]

Commit 4101e0a implement the ForwardAlloc that is especially useful for allocations during compilation time of a contract.
Compilation time in this sense means the time during a run of the upcoming pdsl_derive functionality that generates code around contract definitions.

[Robbepop]

Open Question

How to instantiate, access and use the allocator?

Instantiation

The current idea is to let the upcoming pdsl_derive do all the organizational work surrounding allocators.
It will use the simple ForwardAlloc in order to allocate keys for the storage fields in a deterministic order and after all of that has been done will instantiate a CellChunkAlloc on the storage.
All of the above is done lazily - so for example the CellChunkAlloc for dynamic allocations during contract execution is only ever instantiated if the pdsl_derive finds out that it will be needed at any time during a possible contract execution. Of course the check for this is conservative since we cannot solve the halting problem.

Usage

The pdsl_derive is also going to create global free functions fn alloc(size: u32) -> Key and fn dealloc(key: Key) in order to access to created CellChunkAlloc created by it during contract compile-time.
This again should be done lazily.

[Robbepop]

Commit 94f9ddc adds new_using_alloc unsafe constructor to use the given concrete allocator for storage allocation. This is the new foundational building block that is later to be used by pdsl_derive and fixes a problem with examples/enzyme.

[Robbepop]

Besides fixing a major issue with the CellChunkAlloc this commit also introduces a way to instantiate a CellChunkAlloc using another allocator - preferrably ForwardAlloc.

[Robbepop]

Commit c2ad3fe introduces the DynAlloc which is yet another storage allocator made for dynamic allocations. It should be far more efficient than the current CellChunkAlloc in terms of memory usage. Also it might be more efficient even for new allocations as long as the total number of all dynamic allocations is below a certain threshold, like < 3000-4000 entities.

[Robbepop]

Implemented long time ago. Current implementation suffices needs. Closed.