Crate bstack

Expand description

A persistent, fsync-durable binary stack backed by a single file.

§Overview

BStack treats a file as a flat byte buffer that grows and shrinks from the tail. Every mutating operation — push, extend, pop, discard, (with the set feature) set and zero, (with the atomic feature) replace, and (with both set and atomic) process — calls a durable sync before returning, so the data survives a process crash or an unclean system shutdown. Read-only operations — peek, peek_into, get, and get_into — never modify the file and on Unix and Windows can run concurrently with each other. pop_into is the buffer-passing counterpart of pop, carrying the same durability and atomicity guarantees. discard is like pop but discards the removed bytes without reading or returning them, avoiding any allocation or copy.

The crate depends on libc (Unix) and windows-sys (Windows) for platform-specific syscalls, and uses no unsafe code beyond the required FFI calls.

§File format

Every file begins with a fixed 16-byte header:

┌────────────────────────┬──────────────┬──────────────┐
│      header (16 B)     │  payload 0   │  payload 1   │  ...
│  magic[8] | clen[8 LE] │              │              │
└────────────────────────┴──────────────┴──────────────┘
^                        ^              ^              ^
file offset 0         offset 16      16+n0          EOF

magic — 8 bytes: BSTK + major(1 B) + minor(1 B) + patch(1 B) + reserved(1 B). This version writes BSTK\x00\x01\x0a\x00 (0.1.10). open accepts any file whose first 6 bytes match BSTK\x00\x01 (any 0.1.x) and rejects anything with a different major or minor.
clen — little-endian u64 recording the committed payload length. It is updated atomically with each push or pop and is used for crash recovery on the next open.

All user-visible offsets are logical (0-based from the start of the payload region, i.e. from file byte 16).

§Crash recovery

On open, the header’s committed length is compared against the actual file size:

Condition	Cause	Recovery
`file_size − 16 > clen`	partial tail write (push crashed before header update)	truncate to `16 + clen`
`file_size − 16 < clen`	partial truncation (pop crashed before header update)	set `clen = file_size − 16`

After recovery a durable_sync ensures the repaired state is on stable storage before any caller can observe or modify the file.

§Durability

Operation	Syscall sequence
`push`	`lseek(END)` → `write(data)` → `lseek(8)` → `write(clen)` → `durable_sync`
`extend`	`lseek(END)` → `set_len(new_end)` → `lseek(8)` → `write(clen)` → `durable_sync`
`pop`, `pop_into`	`lseek` → `read` → `ftruncate` → `lseek(8)` → `write(clen)` → `durable_sync`
`discard`	`ftruncate` → `lseek(8)` → `write(clen)` → `durable_sync`
`set` (feature)	`lseek(offset)` → `write(data)` → `durable_sync`
`zero` (feature)	`lseek(offset)` → `write(zeros)` → `durable_sync`
`atrunc` (feature: atomic, net extension)	`set_len(new_end)` → `lseek(tail)` → `write(buf)` → `durable_sync` → `lseek(8)` → `write(clen)`
`atrunc` (feature: atomic, net truncation)	`lseek(tail)` → `write(buf)` → `set_len(new_end)` → `durable_sync` → `lseek(8)` → `write(clen)`
`splice`, `splice_into` (feature: atomic)	`lseek(tail)` → `read(n)` → (then as `atrunc`)
`try_extend` (feature: atomic)	`lseek(END)` — conditional `push` sequence if size matches
`try_discard` (feature: atomic)	`lseek(END)` — conditional `discard` sequence if size matches
`swap`, `swap_into` (features: set+atomic)	`lseek(offset)` → `read` → `lseek(offset)` → `write(buf)` → `durable_sync`
`cas` (features: set+atomic)	`lseek(offset)` → `read` → compare — conditional `lseek(offset)` → `write(new)` → `durable_sync`
`process` (features: set+atomic)	`lseek(start)` → `read(end−start)` → (callback) → `lseek(start)` → `write(buf)` → `durable_sync`
`replace` (feature: atomic)	`lseek(tail)` → `read(n)` → (callback) → (then as `atrunc`)
`peek`, `peek_into`, `get`, `get_into`	`pread(2)` on Unix; `ReadFile`+`OVERLAPPED` on Windows; `lseek` → `read` elsewhere (no sync — read-only)

durable_sync on macOS issues fcntl(F_FULLFSYNC), which flushes the drive’s hardware write cache. Plain fdatasync is not sufficient on macOS because the kernel may acknowledge it before the drive controller has committed the data. If F_FULLFSYNC is not supported by the device the implementation falls back to sync_data (fdatasync).

durable_sync on other Unix calls sync_data (fdatasync), which is sufficient on Linux and BSD.

durable_sync on Windows calls sync_data, which maps to FlushFileBuffers. This flushes the kernel write-back cache and waits for the drive to acknowledge, providing equivalent durability to fdatasync.

§Multi-process safety

On Unix, open acquires an exclusive advisory flock on the file (LOCK_EX | LOCK_NB). If another process already holds the lock, open returns immediately with io::ErrorKind::WouldBlock rather than blocking indefinitely. The lock is released automatically when the BStack is dropped (the underlying file descriptor is closed).

On Windows, open acquires an exclusive LockFileEx lock (LOCKFILE_EXCLUSIVE_LOCK | LOCKFILE_FAIL_IMMEDIATELY) covering the entire file range. If another process already holds the lock, open returns immediately with io::ErrorKind::WouldBlock (ERROR_LOCK_VIOLATION). The lock is released when the BStack is dropped (the underlying file handle is closed).

Note: Both flock (Unix) and LockFileEx (Windows) are advisory and per-process. They prevent well-behaved concurrent opens across processes but do not protect against processes that bypass the lock or against raw writes to the file.

§Correct usage

bstack files must only be opened through this crate or a compatible implementation that understands the file format, the header protocol, and the locking semantics. Reading or writing the underlying file with raw tools or syscalls while a BStack instance is live — or manually editing the header fields — can silently corrupt the committed-length sentinel or bypass the advisory lock.

The authors make no guarantees about the behaviour of this crate — including freedom from data loss or logical corruption — when the file has been accessed outside of this crate’s controlled interface.

§Thread safety

BStack wraps the file in a std::sync::RwLock.

Operation	Lock (Unix / Windows)	Lock (other)
`push`, `extend`, `pop`, `pop_into`, `discard`	write	write
`set`, `zero` (feature)	write	write
`atrunc`, `splice`, `splice_into`, `try_extend` (feature: atomic)	write	write
`try_discard(s, n > 0)` (feature: atomic)	write	write
`try_discard(s, 0)` (feature: atomic)	read	read
`swap`, `swap_into`, `cas` (features: set+atomic)	write	write
`process` (features: set+atomic)	write	write
`replace` (feature: atomic)	write	write
`peek`, `peek_into`, `get`, `get_into`	read (or none for ranges entirely within the locked region)	write
`len`	read	read

On Unix and Windows, peek, peek_into, get, and get_into use a cursor-safe positional read (pread(2) on Unix; ReadFile with OVERLAPPED on Windows) that does not modify the file-position cursor. This allows multiple concurrent calls to any of these methods to run in parallel while any ongoing push, pop, or pop_into still serialises all writers via the write lock. When a read range lies entirely within the locked region, the rwlock is bypassed altogether — see that section for the concurrency model.

On other platforms a seek is required, so peek, peek_into, get, and get_into fall back to the write lock and all reads serialise.

§Locked region (`lock_up_to`)

BStack maintains an in-memory monotonically growing partition boundary named the locked region. Bytes in [0, locked_len()) are declared permanently immutable for the lifetime of the open file.

The locked length starts at 0 on every open and is not persisted to disk — the file format is unchanged. Callers extend the boundary by calling lock_up_to (or open and lock in one step with open_locked_up_to). It can only grow; attempts to shrink it return io::ErrorKind::InvalidInput.

§Effects

Lock-free reads on Unix and Windows. When get, get_into, or peek_into are called with a range that lies entirely within the locked region, the rwlock is bypassed and the read is served directly by pread(2) (Unix) or ReadFile + OVERLAPPED (Windows). The fstat size check is skipped too — the locked length is a sufficient upper bound.
Write protection. set, zero, swap, swap_into, cas, and process return io::ErrorKind::InvalidInput when their target range overlaps the locked region. atrunc, splice, splice_into, and replace return the same error when the operation would modify bytes inside it.
Shrink protection. pop, pop_into, discard, and try_discard return io::ErrorKind::InvalidInput when they would shrink the payload below the locked length.

Callers that never invoke lock_up_to see no behavioural change — every read and write path adds only a single uncontended AtomicU64::load and a comparison.

§Concurrency model

lock_up_to(n) acquires the exclusive write lock before publishing the new boundary with a Release store. Lock-free readers Acquire-load locked before each call. Two consequences follow:

A stale load is always safe. If a reader sees an older (smaller) locked value, it falls through to the rwlock path; if it sees a newer value, the entire range it now reads is by definition immutable.
Locked-region checks on writers are evaluated under the write lock, so they cannot race against a concurrent lock_up_to extending the boundary across the write target.

§Typical use

use bstack::BStack;

// A fixed 64-byte metadata block at the head of the file, read by many
// threads but never modified after first write.
let stack = BStack::open_locked_up_to("meta.bin", 64)?;
assert_eq!(stack.locked_len(), 64);

// Reads of the metadata bypass the rwlock on Unix and Windows.
let header = stack.get(0, 64)?;

On platforms other than Unix and Windows the boundary still enforces immutability through the rwlock path; only the lock-free read fast path is platform-gated.

§Standard I/O adapters

§Writing

BStack implements std::io::Write (and so does &BStack, mirroring [std::io::Write for &File]). Each call to write is forwarded to push, so every write is atomically appended and durably synced before returning. flush is a no-op.

use std::io::Write;
use bstack::BStack;

let mut stack = BStack::open("log.bin")?;
stack.write_all(b"hello")?;
stack.write_all(b"world")?;

§Reading

BStackReader wraps a &BStack with a cursor and implements std::io::Read and std::io::Seek. Use BStack::reader or BStack::reader_at to construct one.

use std::io::{Read, Seek, SeekFrom};
use bstack::BStack;

let stack = BStack::open("log.bin")?;
stack.push(b"hello world")?;

let mut reader = stack.reader();
let mut buf = [0u8; 5];
reader.read_exact(&mut buf)?;  // b"hello"
reader.seek(SeekFrom::Start(6))?;
reader.read_exact(&mut buf)?;  // b"world"

§Trait implementations

§`BStack`

Trait	Semantics
`Debug`	Shows `version` (semver string from the magic header, e.g. `"0.1.6"`) and `len` (`Option<u64>`, `None` on I/O failure).
`PartialEq` / `Eq`	Pointer identity. Two values are equal iff they are the same instance. No two distinct `BStack` values in one process can refer to the same file.
`Hash`	Hashes the instance address — consistent with pointer-identity `PartialEq`.

§`BStackReader`

Trait	Semantics
`PartialEq` / `Eq`	Equal when both the `BStack` pointer (identity) and the cursor `offset` match.
`Hash`	Hashes `(BStack pointer, offset)` — consistent with `PartialEq`.
`PartialOrd` / `Ord`	Ordered by `BStack` instance address, then by cursor `offset`. Groups all readers over the same stack and within that group orders by position.

§Feature flags

Feature	Description
`set`	Enables `BStack::set` and `BStack::zero` — in-place overwrite of existing payload bytes (or with zeros) without changing the file size.
`alloc`	Enables `BStackAllocator`, `BStackBulkAllocator`, `BStackSlice`, `BStackSliceReader`, and `LinearBStackAllocator` — region-based allocation over a `BStack` payload.
`atomic`	Enables `BStack::atrunc`, `BStack::splice`, `BStack::splice_into`, `BStack::try_extend`, `BStack::try_discard`, and `BStack::replace` — compound read-modify-write operations that hold the write lock across what would otherwise be separate calls. Combined with `set`, also enables `BStack::swap`, `BStack::swap_into`, `BStack::cas`, and `BStack::process`.

Enable with:

[dependencies]
bstack = { version = "0.1", features = ["set"] }
# or
bstack = { version = "0.1", features = ["alloc"] }
# or both
bstack = { version = "0.1", features = ["alloc", "set"] }

§Allocator (`alloc` feature)

The alloc feature adds a region-management layer on top of BStack.

§Key types

BStackAllocator — trait for types that own a BStack and manage contiguous byte regions within its payload. Requires stack(), into_stack(), alloc(), and realloc(); provides a default no-op dealloc() and delegation helpers len() / is_empty().
BStackBulkAllocator — extension trait for BStackAllocator that adds atomic bulk operations. Both methods are required with no default; on error the backing store is left unchanged unless a crash occur.
BStackSlice<'a, A> — lightweight Copy handle (allocator reference + offset + length) to a contiguous region. Exposes read, read_into, read_range_into, subslice, subslice_range, reader, reader_at, and (with the set feature) write, write_range, zero, zero_range.
BStackSliceReader<'a, A> — cursor-based reader over a BStackSlice, implementing io::Read and io::Seek in the slice’s coordinate space.
LinearBStackAllocator — reference bump allocator that appends regions sequentially. realloc is O(1) for the tail allocation and returns Unsupported for non-tail slices. dealloc reclaims the tail via BStack::discard; non-tail deallocations are a no-op. Every operation maps to exactly one BStack call and is crash-safe by inheritance. Implements BStackAllocator and BStackBulkAllocator.
FirstFitBStackAllocator — Experimental: a persistent first-fit free-list allocator that reuses freed regions to prevent unbounded file growth. Requires both alloc and set features.
GhostTreeBstackAllocator — A pure-AVL general-purpose allocator with zero-overhead live allocations. Free blocks store their AVL node inline, and the tree is keyed on (size, address) for best-fit allocation. Provides O(log n) allocation and deallocation with crash recovery through tree rebalancing on mount.

§Lifetime model

BStackSlice<'a, A> borrows the allocator for 'a, not the BStack directly. As a result the borrow checker statically prevents calling BStackAllocator::into_stack — which consumes the allocator by value — while any slice is still in scope.

§Quick example

use bstack::{BStack, BStackAllocator, LinearBStackAllocator};

# fn main() -> std::io::Result<()> {
let alloc = LinearBStackAllocator::new(BStack::open("data.bstack")?);

let slice = alloc.alloc(128)?;          // reserve 128 zero bytes
let data  = slice.read()?;              // read them back
alloc.dealloc(slice)?;                  // release (tail, so O(1))

let stack = alloc.into_stack();         // reclaim the BStack
# Ok(())
# }

§Examples

use bstack::BStack;

let stack = BStack::open("log.bin")?;

// push returns the logical byte offset where the payload starts.
let off0 = stack.push(b"hello")?;  // 0
let off1 = stack.push(b"world")?;  // 5

assert_eq!(stack.len()?, 10);

// peek reads from a logical offset to the end without removing anything.
assert_eq!(stack.peek(off1)?, b"world");

// get reads an arbitrary half-open logical byte range.
assert_eq!(stack.get(3, 8)?, b"lowor");

// pop removes bytes from the tail and returns them.
assert_eq!(stack.pop(5)?, b"world");
assert_eq!(stack.len()?, 5);

Structs§

BStack: A persistent, fsync-durable binary stack backed by a single file.
BStackReader: A cursor-based reader over a BStack payload.
BStackSlice: A lifetime-coupled handle to a contiguous region of a BStack payload.
BStackSliceReader: A cursor-based reader over a BStackSlice.
BStackSliceWriter: A cursor-based writer over a BStackSlice.
FirstFitBStackAllocator: A persistent first-fit free-list allocator implementing BStackAllocator on top of a BStack.
GhostTreeBstackAllocator: A pure-AVL general-purpose allocator built on top of a BStack.
LinearBStackAllocator: A simple bump allocator that owns a BStack and allocates regions sequentially by appending to the tail.
ManualAllocator: A singleton allocator that carries no underlying BStack and never allocates.

Traits§

BStackAllocator: A trait for types that own a BStack and manage contiguous byte regions within its payload.
BStackAtomicGuardedSlice: Marker trait for BStackGuardedSlice implementations that guarantee atomicity and crash safety.
BStackAtomicGuardedSliceSubview: Marker trait for BStackGuardedSliceSubview implementations that also satisfy BStackAtomicGuardedSlice’s atomicity and crash-safety contract.
BStackBulkAllocator: Extension trait for allocators that support batching multiple allocations and deallocations in a single operation.
BStackGuardedSlice: A BStackSlice abstraction with lifecycle hooks for transparent I/O interception.
BStackGuardedSliceSubview: Extension trait for BStackGuardedSlice implementations that can produce a narrowed sub-view while preserving the full hook scope of the parent.
BStackSliceAllocator: Convenience supertrait for the common case of a BStackAllocator whose handle type is BStackSlice and whose error type is io::Error.

Crate bstack

Crate bstack Copy item path

§Overview

§File format

§Crash recovery

§Durability

§Multi-process safety

§Correct usage

§Thread safety

§Locked region (lock_up_to)

§Effects

§Concurrency model

§Typical use

§Standard I/O adapters

§Writing

§Reading

§Trait implementations

§BStack

§BStackReader

§Feature flags

§Allocator (alloc feature)

§Key types

§Lifetime model

§Quick example

§Examples

Structs§

Traits§

Crate bstack

§Locked region (`lock_up_to`)

§`BStack`

§`BStackReader`

§Allocator (`alloc` feature)