Module `0x1::storage_slots_allocator`

Abstraction to having “addressable” storage slots (i.e. items) in global storage. Addresses are local u64 values (unique within a single StorageSlotsAllocator instance, but can and do overlap across instances).

Allows optionally to initialize slots (and pay for them upfront), and then reuse them, providing predictable storage costs.

If we need to mutate multiple slots at the same time, we can workaround borrow_mut preventing us from that, via provided pair of remove_and_reserve and fill_reserved_slot methods, to do so in non-conflicting manner.

Similarly allows getting an address upfront via reserve_slot, for a slot created later (i.e. if we need address to initialize the value itself).

In the future, more sophisticated strategies can be added, without breaking/modifying callers, for example:

inlining some nodes
having a fee-payer for any storage creation operations

Enum Link
Enum StorageSlotsAllocator
Struct ReservedSlot
Struct StoredSlot
Constants
Function new
Function allocate_spare_slots
Function get_num_spare_slot_count
Function add
Function remove
Function destroy_empty
Function borrow
Function borrow_mut
Function reserve_slot
Function fill_reserved_slot
Function remove_and_reserve
Function free_reserved_slot
Function reserved_to_index
Function stored_to_index
Function is_null_index
Function is_special_unused_index
Function maybe_pop_from_reuse_queue
Function maybe_push_to_reuse_queue
Function next_slot_index
Function add_link
Function remove_link
Specification
- Function allocate_spare_slots
- Function add
- Function remove
- Function borrow
- Function borrow_mut
- Function reserve_slot
- Function fill_reserved_slot
- Function remove_and_reserve
- Function free_reserved_slot

use 0x1::error;
use 0x1::option;
use 0x1::table_with_length;

Enum `Link`

Data stored in an individual slot

enum Link<T: store> has store

Variants

Occupied

Fields

value: T

Vacant

Fields

next: u64

Enum `StorageSlotsAllocator`

enum StorageSlotsAllocator<T: store> has store

Variants

Fields

slots: option::Option<table_with_length::TableWithLength<u64, storage_slots_allocator::Link<T>>>
new_slot_index: u64
should_reuse: bool
reuse_head_index: u64
reuse_spare_count: u32

Struct `ReservedSlot`

Handle to a reserved slot within a transaction. Not copy/drop/store-able, to guarantee reservation is used or released within the transaction.

struct ReservedSlot

Fields

slot_index: u64

Struct `StoredSlot`

Ownership handle to a slot. Not copy/drop-able to make sure slots are released when not needed, and there is unique owner for each slot.

struct StoredSlot has store

Fields

slot_index: u64

Constants

const ECANNOT_HAVE_SPARES_WITHOUT_REUSE: u64 = 2;

const EINTERNAL_INVARIANT_BROKEN: u64 = 7;

const EINVALID_ARGUMENT: u64 = 1;

const FIRST_INDEX: u64 = 10;

const NULL_INDEX: u64 = 0;

Function `new`

public fun new<T: store>(should_reuse: bool): storage_slots_allocator::StorageSlotsAllocator<T>

Implementation

public fun new<T: store>(should_reuse: bool): StorageSlotsAllocator<T> {
    StorageSlotsAllocator::V1 {
        slots: option::none(),
        new_slot_index: FIRST_INDEX,
        should_reuse,
        reuse_head_index: NULL_INDEX,
        reuse_spare_count: 0,
    }
}

Function `allocate_spare_slots`

public fun allocate_spare_slots<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, num_to_allocate: u64)

Implementation

public fun allocate_spare_slots<T: store>(self: &mut StorageSlotsAllocator<T>, num_to_allocate: u64) {
    assert!(self.should_reuse, error::invalid_argument(ECANNOT_HAVE_SPARES_WITHOUT_REUSE));
    for (i in 0..num_to_allocate) {
        let slot_index = self.next_slot_index();
        self.maybe_push_to_reuse_queue(slot_index);
    };
}

Function `get_num_spare_slot_count`

public fun get_num_spare_slot_count<T: store>(self: &storage_slots_allocator::StorageSlotsAllocator<T>): u32

Implementation

public fun get_num_spare_slot_count<T: store>(self: &StorageSlotsAllocator<T>): u32 {
    assert!(self.should_reuse, error::invalid_argument(ECANNOT_HAVE_SPARES_WITHOUT_REUSE));
    self.reuse_spare_count
}

Function `add`

public fun add<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, val: T): storage_slots_allocator::StoredSlot

Implementation

public fun add<T: store>(self: &mut StorageSlotsAllocator<T>, val: T): StoredSlot {
    let (stored_slot, reserved_slot) = self.reserve_slot();
    self.fill_reserved_slot(reserved_slot, val);
    stored_slot
}

Function `remove`

public fun remove<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot: storage_slots_allocator::StoredSlot): T

Implementation

public fun remove<T: store>(self: &mut StorageSlotsAllocator<T>, slot: StoredSlot): T {
    let (reserved_slot, value) = self.remove_and_reserve(slot.stored_to_index());
    self.free_reserved_slot(reserved_slot, slot);
    value
}

Function `destroy_empty`

public fun destroy_empty<T: store>(self: storage_slots_allocator::StorageSlotsAllocator<T>)

Implementation

public fun destroy_empty<T: store>(self: StorageSlotsAllocator<T>) {
    loop {
        let reuse_index = self.maybe_pop_from_reuse_queue();
        if (reuse_index == NULL_INDEX) {
            break;
        };
    };
    match (self) {
        V1 {
            slots,
            new_slot_index: _,
            should_reuse: _,
            reuse_head_index,
            reuse_spare_count: _,
        } => {
            assert!(reuse_head_index == NULL_INDEX, EINTERNAL_INVARIANT_BROKEN);
            if (slots.is_some()) {
                slots.destroy_some().destroy_empty();
            } else {
                slots.destroy_none();
            }
        },
    };
}

Function `borrow`

public fun borrow<T: store>(self: &storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64): &T

Implementation

public fun borrow<T: store>(self: &StorageSlotsAllocator<T>, slot_index: u64): &T {
    &self.slots.borrow().borrow(slot_index).value
}

Function `borrow_mut`

public fun borrow_mut<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64): &mut T

Implementation

public fun borrow_mut<T: store>(self: &mut StorageSlotsAllocator<T>, slot_index: u64): &mut T {
    &mut self.slots.borrow_mut().borrow_mut(slot_index).value
}

Function `reserve_slot`

public fun reserve_slot<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>): (storage_slots_allocator::StoredSlot, storage_slots_allocator::ReservedSlot)

Implementation

public fun reserve_slot<T: store>(self: &mut StorageSlotsAllocator<T>): (StoredSlot, ReservedSlot) {
    let slot_index = self.maybe_pop_from_reuse_queue();
    if (slot_index == NULL_INDEX) {
        slot_index = self.next_slot_index();
    };

    (
        StoredSlot { slot_index },
        ReservedSlot { slot_index },
    )
}

Function `fill_reserved_slot`

public fun fill_reserved_slot<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot: storage_slots_allocator::ReservedSlot, val: T)

Implementation

public fun fill_reserved_slot<T: store>(self: &mut StorageSlotsAllocator<T>, slot: ReservedSlot, val: T) {
    let ReservedSlot { slot_index } = slot;
    self.add_link(slot_index, Link::Occupied { value: val });
}

Function `remove_and_reserve`

Remove storage slot, but reserve it for later.

public fun remove_and_reserve<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64): (storage_slots_allocator::ReservedSlot, T)

Implementation

public fun remove_and_reserve<T: store>(self: &mut StorageSlotsAllocator<T>, slot_index: u64): (ReservedSlot, T) {
    let Link::Occupied { value } = self.remove_link(slot_index);
    (ReservedSlot { slot_index }, value)
}

Function `free_reserved_slot`

public fun free_reserved_slot<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, reserved_slot: storage_slots_allocator::ReservedSlot, stored_slot: storage_slots_allocator::StoredSlot)

Implementation

public fun free_reserved_slot<T: store>(self: &mut StorageSlotsAllocator<T>, reserved_slot: ReservedSlot, stored_slot: StoredSlot) {
    let ReservedSlot { slot_index } = reserved_slot;
    assert!(slot_index == stored_slot.slot_index, EINVALID_ARGUMENT);
    let StoredSlot { slot_index: _ } = stored_slot;
    self.maybe_push_to_reuse_queue(slot_index);
}

Function `reserved_to_index`

public fun reserved_to_index(self: &storage_slots_allocator::ReservedSlot): u64

Implementation

public fun reserved_to_index(self: &ReservedSlot): u64 {
    self.slot_index
}

Function `stored_to_index`

public fun stored_to_index(self: &storage_slots_allocator::StoredSlot): u64

Implementation

public fun stored_to_index(self: &StoredSlot): u64 {
    self.slot_index
}

Function `is_null_index`

public fun is_null_index(slot_index: u64): bool

Implementation

public fun is_null_index(slot_index: u64): bool {
    slot_index == NULL_INDEX
}

Function `is_special_unused_index`

public fun is_special_unused_index(slot_index: u64): bool

Implementation

public fun is_special_unused_index(slot_index: u64): bool {
    slot_index != NULL_INDEX && slot_index < FIRST_INDEX
}

Function `maybe_pop_from_reuse_queue`

fun maybe_pop_from_reuse_queue<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>): u64

Implementation

fun maybe_pop_from_reuse_queue<T: store>(self: &mut StorageSlotsAllocator<T>): u64 {
    let slot_index = self.reuse_head_index;
    if (slot_index != NULL_INDEX) {
        let Link::Vacant { next } = self.remove_link(slot_index);
        self.reuse_head_index = next;
        self.reuse_spare_count -= 1;
    };
    slot_index
}

Function `maybe_push_to_reuse_queue`

fun maybe_push_to_reuse_queue<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64)

Implementation

fun maybe_push_to_reuse_queue<T: store>(self: &mut StorageSlotsAllocator<T>, slot_index: u64) {
    if (self.should_reuse) {
        let link = Link::Vacant { next: self.reuse_head_index };
        self.add_link(slot_index, link);
        self.reuse_head_index = slot_index;
        self.reuse_spare_count += 1;
    };
}

Function `next_slot_index`

fun next_slot_index<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>): u64

Implementation

fun next_slot_index<T: store>(self: &mut StorageSlotsAllocator<T>): u64 {
    let slot_index = self.new_slot_index;
    self.new_slot_index += 1;
    if (self.slots.is_none()) {
        self.slots.fill(table_with_length::new<u64, Link<T>>());
    };
    slot_index
}

Function `add_link`

fun add_link<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64, link: storage_slots_allocator::Link<T>)

Implementation

fun add_link<T: store>(self: &mut StorageSlotsAllocator<T>, slot_index: u64, link: Link<T>) {
    self.slots.borrow_mut().add(slot_index, link);
}

Function `remove_link`

fun remove_link<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64): storage_slots_allocator::Link<T>

Implementation

fun remove_link<T: store>(self: &mut StorageSlotsAllocator<T>, slot_index: u64): Link<T> {
    self.slots.borrow_mut().remove(slot_index)
}

Specification

Function `allocate_spare_slots`

public fun allocate_spare_slots<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, num_to_allocate: u64)

aborts_if !self.should_reuse;
pragma aborts_if_is_partial;

Function `add`

public fun add<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, val: T): storage_slots_allocator::StoredSlot

pragma opaque;
aborts_if self.reuse_head_index == 0 && self.new_slot_index + 1 > MAX_U64;
pragma aborts_if_is_partial;
ensures self.slots.is_some();
ensures table_with_length::spec_contains(option::borrow(self.slots), result.slot_index);
ensures table_with_length::spec_get(option::borrow(self.slots), result.slot_index) is Link::Occupied;
ensures table_with_length::spec_get(option::borrow(self.slots), result.slot_index).value == val;

Function `remove`

public fun remove<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot: storage_slots_allocator::StoredSlot): T

pragma opaque;
aborts_if self.slots.is_none();
aborts_if !table_with_length::spec_contains(option::borrow(self.slots), slot.slot_index);
aborts_if !(table_with_length::spec_get(option::borrow(self.slots), slot.slot_index) is Link::Occupied);
pragma aborts_if_is_partial;
ensures result == old(table_with_length::spec_get(option::borrow(self.slots), slot.slot_index)).value;
ensures self.slots.is_some();

Function `borrow`

public fun borrow<T: store>(self: &storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64): &T

pragma opaque;
aborts_if self.slots.is_none();
aborts_if !table_with_length::spec_contains(option::borrow(self.slots), slot_index);
aborts_if !(table_with_length::spec_get(option::borrow(self.slots), slot_index) is Link::Occupied);
ensures result == table_with_length::spec_get(option::borrow(self.slots), slot_index).value;

Function `borrow_mut`

public fun borrow_mut<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64): &mut T

pragma opaque;
aborts_if self.slots.is_none();
aborts_if !table_with_length::spec_contains(option::borrow(self.slots), slot_index);
aborts_if !(table_with_length::spec_get(option::borrow(self.slots), slot_index) is Link::Occupied);
ensures result == table_with_length::spec_get(option::borrow(self.slots), slot_index).value;

Function `reserve_slot`

public fun reserve_slot<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>): (storage_slots_allocator::StoredSlot, storage_slots_allocator::ReservedSlot)

aborts_if self.reuse_head_index == 0 && self.new_slot_index + 1 > MAX_U64;
pragma aborts_if_is_partial;
ensures result_1.slot_index == result_2.slot_index;

Function `fill_reserved_slot`

public fun fill_reserved_slot<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot: storage_slots_allocator::ReservedSlot, val: T)

pragma opaque;
aborts_if self.slots.is_none();
aborts_if table_with_length::spec_contains(option::borrow(self.slots), slot.slot_index);
ensures table_with_length::spec_contains(option::borrow(self.slots), slot.slot_index);
ensures table_with_length::spec_get(option::borrow(self.slots), slot.slot_index) is Link::Occupied;
ensures table_with_length::spec_get(option::borrow(self.slots), slot.slot_index).value == val;
ensures self.slots.is_some();

Function `remove_and_reserve`

public fun remove_and_reserve<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, slot_index: u64): (storage_slots_allocator::ReservedSlot, T)

pragma opaque;
aborts_if self.slots.is_none();
aborts_if !table_with_length::spec_contains(option::borrow(self.slots), slot_index);
aborts_if !(table_with_length::spec_get(option::borrow(self.slots), slot_index) is Link::Occupied);
ensures result_1.slot_index == slot_index;
ensures result_2 == old(table_with_length::spec_get(option::borrow(self.slots), slot_index)).value;
ensures self.slots.is_some();

Function `free_reserved_slot`

public fun free_reserved_slot<T: store>(self: &mut storage_slots_allocator::StorageSlotsAllocator<T>, reserved_slot: storage_slots_allocator::ReservedSlot, stored_slot: storage_slots_allocator::StoredSlot)

aborts_if reserved_slot.slot_index != stored_slot.slot_index;
aborts_if self.should_reuse && self.slots.is_none();
pragma aborts_if_is_partial;

Keyboard shortcuts

The Aptos Framework Book