Crate bstack 

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\x0e\x00 (0.1.14). 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
try_extend_zeros (feature: atomic)	lseek(END) — conditional extend(n) 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)
cross_exchange (features: set+atomic)	lseek(a) → read(n) → lseek(b) → read(n) → lseek(a) → write → lseek(b) → write → durable_sync
copy (features: set+atomic)	lseek(from) → read(n) → lseek(to) → write(n) → durable_sync
eq_crds, ne_crds (features: set+atomic)	lseek(a) → read → compare — conditional lseek(b) → write(b_buf) → durable_sync
masked_eq_crds, masked_ne_crds (features: set+atomic)	lseek(a) → read → mask+compare — conditional lseek(b) → write(b_buf) → durable_sync
peek, peek_into, get, get_into, get_batched, get_batched_into, get_batched_gen	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, try_extend_zeros (feature: atomic)	write	write
try_discard(s, n > 0) (feature: atomic)	write	write
try_discard(s, 0) (feature: atomic)	read	read
get_batched, get_batched_into, get_batched_gen (feature: atomic)	read	write
swap, swap_into, cas (features: set+atomic)	write	write
cross_exchange, copy, process (features: set+atomic)	write	write
eq_crds, ne_crds, masked_eq_crds, masked_ne_crds (features: set+atomic)	write	write
replace (feature: atomic)	write	write
peek, peek_into, get, get_into	read	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. For get and get_into, reads that lie entirely within the locked region bypass the rwlock — 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.

Opening with open_cached (or open_locked_up_to_cached) enables an in-memory mirror of the locked region: each lock_up_to call reads the newly locked bytes from disk into a heap buffer, and subsequent reads whose range falls entirely within the cached region are served with no syscall.

Effects

• get/get_into fast-path reads. When get or get_into are called with a range that lies entirely within the locked region, the internal RwLock is bypassed.

  • On non-cached stacks (Unix/Windows), reads are lock-free and use pread(2) (Unix) or ReadFile + OVERLAPPED (Windows).
  • On cached stacks (all platforms), reads are served from the in-memory buffer under a Mutex (so RwLock-free, but not lock-free). The fstat size check is skipped on this path — the locked length is a sufficient upper bound.

• Write protection. set, zero, swap, swap_into, cas, process, cross_exchange, copy (destination only), eq_crds, ne_crds, masked_eq_crds, and masked_ne_crds (region B) return io::ErrorKind::InvalidInput when their write 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. Locked-region fast-path 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.

On cached stacks the cache Mutex is acquired and fully populated before locked is advanced with the Release store. A reader that Acquire-loads locked and then locks the cache Mutex therefore always sees a buffer whose valid range covers at least [0, locked).

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 cached stacks this locked-region fast path is available on all platforms (served from the cache under a Mutex).

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. Combined with set, also enables BStackSliceWriter, FirstFitBStackAllocator, GhostTreeBstackAllocator, and BStackByteVec.
atomic	Enables BStack::atrunc, BStack::splice, BStack::splice_into, BStack::try_extend, BStack::try_extend_zeros, BStack::try_discard, BStack::replace, BStack::get_batched, BStack::get_batched_into, and BStack::get_batched_gen — compound read-modify-write operations that hold the lock across what would otherwise be separate calls. Combined with set, also enables BStack::swap, BStack::swap_into, BStack::cas, BStack::process, BStack::cross_exchange, BStack::copy, BStack::eq_crds, BStack::ne_crds, BStack::masked_eq_crds, and BStack::masked_ne_crds.

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 (or BStack::try_discard with atomic); non-tail deallocations are a no-op. Every operation maps to exactly one BStack call and is crash-safe by inheritance. Send in all configurations; also Sync with the atomic feature. Implements BStackAllocator and BStackBulkAllocator.

• FirstFitBStackAllocator — A persistent first-fit free-list allocator that reuses freed regions to prevent unbounded file growth. Requires both alloc and set features. Send in all configurations; also Sync with the atomic feature, where an internal Mutex serializes free-list mutation and stack extension.

• 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. Send in all configurations; Send + Sync with the atomic feature, where an internal Mutex serialises AVL tree mutations.

• SlabBStackAllocator — Experimental. Fixed-block slab allocator. All blocks are exactly block_size bytes with no per-block header or footer; freed blocks are tracked via an intrusive singly-linked free list stored in the first 8 bytes of each free block. O(1) alloc and dealloc. Use SlabBStackAllocator::new to initialise an empty stack and SlabBStackAllocator::open to reopen an existing one. Requires both alloc and set features.

• CheckedSlabBStackAllocator — Experimental. Crash-recoverable variant of SlabBStackAllocator. Prefixes every block with an 8-byte overhead field (zero when free, high bit set with a block count when in use) so leaked blocks are recoverable by a linear scan and double-frees are caught at runtime before the free list can be corrupted. Constructor takes data_size (usable bytes per block, ≥ 8); the on-disk block_size is data_size + 8. Use CheckedSlabBStackAllocator::new to initialise an empty stack and CheckedSlabBStackAllocator::open to reopen one (open runs recover automatically). Requires both alloc and set features.

• DebugCheckingAllocator — Debug/test wrapper around any BStackAllocator. Tracks allocated and freed regions in memory and panics on overlapping allocations, double-frees, or partial frees. Not for production use.

• BStackByteVec<'a, A> — a growable byte (u8) vector backed by a BStack allocation (requires alloc + set). Mirrors the core Vec<u8> API: new, with_capacity, from_slice, push, pop, get, read_bytes, as_slice, truncate, clear, reserve, resize, and iter. The block stores a 16-byte header (len, cap) followed by the byte data; the header is re-read on every call for crash recoverability. push doubles capacity (minimum 4); pop decrements len then zeros the vacated slot; truncate writes len then zeros all removed slots.

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.

BStackByteVec

A growable byte vector backed by a crate::BStack allocation.

BStackByteVecIter

An iterator over the bytes of a BStackByteVec.

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.

CheckedSlabBStackAllocator

A crash-recoverable fixed-block slab allocator implementing BStackAllocator on top of a BStack.

DebugCheckingAllocator

Debug-only allocator wrapper that validates allocations and deallocations.

DebugHandle

Handle type for DebugCheckingAllocator.

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.

SlabBStackAllocator

A fixed-block slab allocator implementing BStackAllocator on top of a BStack.

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.