Transports

Overview

The core of AlephZero’s offering is an interprocess-safe datastructure.

The datastructure is, effectively, a circular linked-list, layed out within a given arena. It can be thought of as a simple allocator.

The transport holds a list of frames, where each frame is a contains a user-provided byte string.

The frames are layed out in the given arena, one after the other, max-aligned in case the bytes needs to be reinterpreted as a struct.

Once the arena is exhausted, and the next requested frame cannot be added without overrunning the arena, the oldest frames will be evicted to make space.

A transport has a single exclusive lock that must be acquired before reading or writing frames. This is to prevent a frame from being erased while another process is reading the frame. A general reader-writer-lock prevents consistency guarantees, but we may allow for a fixed, limited, number of simultanious readers in the future.

The layout of the transport is guaranteed to be consistent on the same machine, regardless of libc implementations.

Constructing

A transport exists in an arena, a flat contiguous memory buffer.

Accessing

transport keeps an external pointer into the arena that is used to iterate through frames.

To access frames within the arena, the transport must be locked. To help prevent bugs associated with unlocked access, all access functions require a a0_transport_locked_t object, returned by a0_transport_lock. The lock should be freed with a0_transport_unlock.

Since frames are organized in a linked-list format, iteration and access follows from standard linked-list api. You MUST begin by setting the pointer to an existing node via a0_transport_jump_head or a0_transport_jump_tail. Afterwards, you may proceed via a0_transport_prev and a0_transport_next. To check if a previous or next exist, you may use the a0_transport_has_prev and a0_transport_has_next.

Note

a0_transport_next does not necessarily refer to the sequentially next. If the transport was exhasted and frames evicted, a0_transport_has_next refers to the existance of some frame added after the one currently pointed to.

If a0_transport_has_next returns true, then it will remain true across unlock-relock. That is not the case for a0_transport_has_prev.

a0_transport_frame returns a frame pointer into the arena.

If the transport is unlocked and relocked, the pointer may no longer be valid. To check for validity, you can use a0_transport_iter_valid. You can use a0_transport_has_next and a0_transport_next regardless of whether the pointer is still valid.

Writing

To write a frame to the transport, we begin by allocating space with a0_transport_alloc. This will return a frame pointing into the arena. Once the frame written to, the user MUST call a0_transport_commit.

There should only be one outstanding allocation before a commit. Multiple allocations before a commit may result in lost sequence numbers based on the current consistency model.

Allocation may cause eviction, even if not committed. To see if an allocation would cause an eviction, use a0_transport_alloc_evicts.

Frame Structure

A frame is a simple container with a header and user provided byte string. The header has a pointer to the next and previous element, as well as a sequence number, and data size.

Notifications

The transport provides a simple condition-variable style wait/notify. a0_transport_wait atomically unlocks the transport and will be awoken when a given predicate is satisfied.

The predicate is checked immediately, then whenever the transport is unlocked following a commit or eviction.

Consistency

The state of the transport is double-buffered and updated atomically during a commit.

The transport uses a robust lock that will detect if the owner dies and will free the lock for the next user. Because of the double-buffered state, the transport is always consistent.

References