Crate swim_mem

Dynamic Memory Model

An advanced dynamic memory model that scales from resource-constrained embedded devices to high-performance super computers.

Design goals

The dynamic memory model was designed to meet a strict set of requirements:

Bare metal
No dependence on a system memory allocator; operable out of a statically declared memory region.

Robust
Handle out-of-memory conditions rigorously, and recoverably.

Deterministic
Guarantee constant allocation and deallocation times.

Relocatable
Safely and deterministically move dynamic memory allocations, without the use of a garbage collector.

Scoped
Constrain dynamic memory allocations to their usage context, by statically bounding memory allocator lifetimes.

Safe
Conform to Rust's data-race-free ownership model. Statically prevent common memory management errors; dynamically detect memory leaks, and semantic memory model violations.

Low fragmentation
Prevent memory fragmentation from accruing by relocating and compacting all memory allocations that outlive a usage context.

Good locality
Maximize data locality by recursively allocating and compacting complex data structures into adjacent cache lines.

Low overhead
Only a single pointer size of memory overhead per dynamic allocation.

High performance
Only hundred or so instructions per allocation.

Concurrent
Thread-safe, lock-free algorithms.

Comprehensive
Complete set of smart pointer types, including cycle-safe soft references.

Terminology

• Memory block: a sequential range of memory addresses.
• Memory object: a memory block that back-references the allocator from whence it came.
• Managed pointer: a pointer-like type that controls the lifetime of a dynamically allocated memory block.
• Governed pointer: a pointer-like type that imposes access restrictions on a memory block.
• Memory lease: ownership and access restrictions on a particular reference to a memory block.
• Memory resident: the usage pattern of a memory block, i.e. single value, vs. dynamically sized array of values, vs. ring buffer of values.
• Relocation: the atomic movement of a memory resident from one memory block to another memory block, after which all managed pointer dereferences will resolve to the relocated resident.
• Stow: the recursive relocation of data structure to extend its lifetime to that of a new allocator.

Components

The implementation breaks down into five major categories:

Physical memory model
Types that facilitate working with extents of raw memory:

• Block: the address and size of a particular memory block.
• Layout: size and alignment constraints for a memory block.

Logical memory model
Traits that generically define the dynamic memory model:

• Heap: an abstract memory block allocator.
• Hold: an abstract memory object allocator.
• Lease: an abstract pointer to a memory block, with associated metadata.
• DynamicLease: an abstract pointer to a resizeable memory block, with associated metadata.
• Resident: a typeclass for generically managing the occupant of a memory block using associated metadata.

Memory allocators
Concrete Heap and Hold allocator implementations:

• AddrSpace: Lock-free Heap allocator of page-aligned memory extents from some address range.
• Slab: Heap allocating from a hunk of memory partitioned into fixed size memory blocks.
• Pack: Pointer-bumping Hold allocating from a hunk of memory.
• Pool: Pointer-bumping Hold allocating from a growable set of Heap-allocated memory hunks.

Memory leases
Concrete Lease implementations:

• Raw: a mutably dereferenceable, relocatable, exlusive reference to a memory resident, with resident metadata stored with the pointer.
• Ptr: a mutably dereferenceable, relocatable, exlusive reference to a memory resident, with resident metadata stored within the allocation.
• Mut: a mutably dereferenceable, unrelocatable, strong reference to a memory resident.
• Ref: an immutably dereferenceable, unrelocatable, strong reference to a memory resident.
• Hard: an undereferenceable, relocatable, strong reference to a memory resident.
• Soft: an undereferenceable, relocatable, weak reference to a memory resident.

Memory residents
Concrete Resident implementations:

• Box: stores a single value in a Lease.
• Buf: stores an array of values in a Lease.
• String: stores a Unicode code unit sequence in a Lease.

Modules

alloc	Dynamic memory allocators and operators.
block	Untyped memory model.
lease	Memory ownership and access model.
resident	Memory usage model.

Macros

addr_space
hold_scope