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, zero, and repeat, (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 and the two lifetime-extending reborrow helpers behind bstack_unsafe_reborrow! / bstack_unsafe_reborrow_mut! (see the reborrow module).

§File format

Every file begins with a fixed 32-byte header, then the concatenated payload (push 0, push 1, …):

  bytes      field
  ─────      ─────
   0 ..  8   magic[8]
   8 .. 16   clen      — committed payload length (u64 LE)
  16 .. 24   wip_ptr   — write-in-progress journal target (u64 LE; 0 when idle)
  24 .. 32   wip_aux   — write-in-progress journal mode (u64 LE)
  32 ..      payload   — push 0, push 1, … concatenated

magic — 8 bytes: BSTK + major(1 B) + minor(1 B) + patch(1 B) + reserved(1 B). This version writes BSTK\x00\x04\x04\x00 (0.4.4). open accepts any file whose first 6 bytes match BSTK\x00\x04 (any 0.4.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.
wip_ptr / wip_aux — two little-endian u64 fields holding the write-in-progress journal that makes in-place mutations crash-atomic. wip_ptr is the physical offset an interrupted in-place write must be replayed into (0 in the steady state); wip_aux names the journal mode (Set — verbatim replay of the staged tail; Repeat — repeat a staged pattern; Copy — replay a disjoint copy from its still-intact source, of which only the coordinate is staged; SpliceGrow/SpliceShrink — a length-changing tail replace, whose new committed length recovery derives from the file size and the recorded direction). Recovery interprets them on open — see Crash recovery. Legacy 0.1.x files (16-byte header) are upgraded in place by BStack::migrate.

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

§Crash recovery

On open, recovery first checks the write-in-progress journal (wip_ptr); if disarmed, it reconciles the committed length against the file size:

Condition	Cause	Recovery
`wip_ptr != 0`, `wip_aux = Set`	an in-place `set`/`swap`/`cas`/`copy`/`cross_exchange` crashed mid-commit	replay the staged tail verbatim into `[wip_ptr, …)`, disarm, truncate to `32 + clen`
`wip_ptr != 0`, `wip_aux = Repeat`	a `zero`/`repeat` crashed mid-fill	write `count` copies of the staged pattern into `[wip_ptr, …)`, disarm, truncate
`wip_ptr != 0`, `wip_aux = Copy`	a disjoint `copy` crashed mid-copy	replay `move_chunked(src → wip_ptr)` from the untouched source (the tail stages only `[src \| n]`), disarm, truncate
`wip_ptr != 0`, `wip_aux = SpliceGrow`/`SpliceShrink`	a length-changing `atrunc`/`splice`/`splice_into`/`replace` crashed mid-replace	derive `clen'` from the file size and direction, replay the staged new tail into `[wip_ptr, …)`, commit `clen'` while disarming, truncate
`wip_ptr != 0`, `wip_aux` unrecognized	a mode armed by a newer build	roll back: disarm, truncate to `32 + clen`
`wip_ptr == 0`, `wip_aux = MultiWrite`	a `set_batched`/`inplace_gen` multi-write batch crashed after all blocks were staged	replay each staged `[s \| e \| data]` block into `[s, e)`, disarm, truncate to `32 + clen` (a corrupt tail rolls back, applying nothing)
`wip_ptr == 0`, `file_size − 32 > clen`	partial tail write (push, or a crashed journal or multi-write stage) before the header update	truncate to `32 + clen`
`wip_ptr == 0`, `file_size − 32 < clen`	partial truncation (pop crashed before the header update)	set `clen = file_size − 32`

Each replay is idempotent — the staged tail is immutable and disjoint from its target — so a crash during recovery itself is safe to re-run. After recovery a durable_sync ensures the repaired state is on stable storage before any caller can observe or modify the file.

§Deferred replay

A BStack stays usable after a write fails, with no reopen: the next write repairs the file before doing anything else, and reads refuse until it has.

A write that fails after its first mutating I/O can leave the states above — an armed journal, or a stale tail past the committed length — on a handle that stays open. The failed call returns its error unchanged and the repair is deferred to the next write, through an in-memory replay_needed flag under the BStack rwlock. While it is set:

The next write replays first, silently, before validating its own arguments — a stale tail would inflate the payload size every mutator derives from the file end — then proceeds normally. The flag clears only once the replay succeeds; a failing replay returns its own error.
Reads fail with InterruptedWrite, until a write replays or recover is called to replay on its own. This covers every read that consults the file or the cached committed length — len, and a zero-length get(n, n) too, since it still checks n against the payload size. Unaffected are the calls that return before taking the lock (peek_into/get_into on an empty buffer, get_batched/get_batched_into on no entries) and lock-free reads of the immutable locked prefix.

§Durability

In-place same-length writes — set, zero, repeat, swap, swap_into, cas, copy, cross_exchange, process, set_batched, inplace_gen, and the crds family — leave the payload length unchanged and are each crash-atomic, committing by one of three strategies (recovered on the next open; see Crash recovery):

Aligned-block write — when the target lies within one power-fail-atomic block, a single write + durable_sync is already all-or-nothing; no journal is armed.
Write-in-progress journal — otherwise: stage a backup past clen → durable_sync → arm wip_ptr → durable_sync → write in place → durable_sync → clear wip_ptr → durable_sync → ftruncate the backup. zero/repeat stage only [count | pattern]; cross_exchange stages one region and commits at a single atomic wip_ptr flip; moves and fills stream through a bounded buffer (O(1) memory).
Multi-write journal — set_batched and inplace_gen commit several non-overlapping in-place writes as one unit: stage every [s | e | data] block past clen → durable_sync → arm the MultiWrite sentinel (wip_ptr stays 0, so it never collides with a single-region journal) → durable_sync → replay each block in place → durable_sync → disarm → ftruncate. A batch that reduces to one write falls back to the single-write strategies above.

Below, commit denotes whichever of those two strategies applies to the bytes being written; anything before it is read/compare/callback work under the lock.

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`
`extend_sparse`, `extend_sparse_batched`	`set_len(new_end)` → `write` each buffer into the grown region (gaps left zero) → `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)	commit `data`
`zero`, `repeat` (feature)	commit the repeated pattern (the journal stages only `[count \| pattern]`)
`atrunc` (feature: atomic)	dispatch on the tail-replace shape: pure truncation → `ftruncate` → commit `clen`; pure append → `set_len(new_end)` → `write(buf)` → `durable_sync` → commit `clen`; same-length → commit `buf` in place; length change → splice journal (stage the new tail past the payload → arm `SpliceGrow`/`SpliceShrink` → replay into place → atomically commit `clen'` + disarm → truncate, a `durable_sync` at each barrier)
`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
`try_extend_sparse`, `try_extend_sparse_batched` (feature: atomic)	`lseek(END)` — conditional `extend_sparse` / `extend_sparse_batched` sequence if size matches
`swap`, `swap_into` (features: set+atomic)	`read` old bytes → commit `buf`
`cas` (features: set+atomic)	`read` → compare — conditional commit of `new`
`process` (features: set+atomic)	`read(start..end)` → (callback) → commit the buffer
`process_gen` (features: set+atomic)	closure-driven reads, ending in at most one mutating step: `Write` commits; `Swap` uses the exchange journal (as `cross_exchange`); `Push`/`Pop`/`Discard`/`Atrunc`/`Splice`/`Sparse` behave as their standalone forms
`set_batched` (features: set+atomic)	validate + reject overlap → multi-write journal: stage every `[s \| e \| data]` block past `clen` → arm the `MultiWrite` sentinel (`wip_ptr` stays `0`) → replay each block in place → disarm → `ftruncate` (a `durable_sync` at each barrier); a lone effective write takes the ordinary single-write commit
`inplace_gen` (features: set+atomic)	closure-driven reads (each overlaid with the batch-so-far edits) interleaved with accumulated `Write`s (later overrides earlier on overlap); on `None` the pending edits commit together via the multi-write journal (as `set_batched`)
`replace` (feature: atomic)	`lseek(tail)` → `read(n)` → (callback) → (then as `atrunc`)
`cross_exchange` (features: set+atomic)	`read(a)`, `read(b)` → exchange journal: stage `a` → arm at `a` → write `b`→`a` → flip `wip_ptr` to `b` → write `a`→`b` → disarm → `ftruncate` (a `durable_sync` at each barrier)
`copy` (features: set+atomic)	same-location → no-op; single-block dest → commit; overlapping → stream source→tail→dest (`Set` journal); disjoint → copy journal (stage only `[src \| n]` → arm `Copy` → stream source→dest → disarm; recovery replays from the untouched source)
`eq_crds`, `ne_crds` (features: set+atomic)	`read(a)` → compare — conditional commit of `b_buf`
`masked_eq_crds`, `masked_ne_crds` (features: set+atomic)	`read(a)` → mask+compare — conditional commit of `b_buf`
`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.

The debug-only debug-no-sync Cargo feature skips durable_sync entirely (writes still happen, just unsynced) for faster fault-injection test iteration. Not for production use.

§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. The committed payload length is also cached in memory and kept in sync with the on-disk header by every write-lock-held operation, so len and is_empty can be answered under the read lock without any File::metadata syscall.

Operation	Lock (Unix / Windows)	Lock (other)
`push`, `extend`, `extend_sparse`, `extend_sparse_batched`, `pop`, `pop_into`, `discard`	write	write
`set`, `zero`, `repeat` (feature)	write	write
`atrunc`, `splice`, `splice_into`, `try_extend`, `try_extend_zeros`, `try_extend_sparse`, `try_extend_sparse_batched` (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`, `process_gen`, `set_batched`, `inplace_gen` (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.

Unlike get_batched_gen, which only ever takes the read lock (Unix/Windows), process_gen and inplace_gen always take the write lock — even for sequences that turn out to be read-only and end in None — because the closure may decide, only after seeing earlier reads, to mutate; the lock therefore has to be acquired before the first read so the whole sequence runs as one indivisible step.

§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, repeat, 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.4.4"`) 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

set — In-place overwrite of existing payload bytes without changing the file size (BStack::set, BStack::zero, BStack::repeat).
alloc — Region-based sub-allocation over a BStack payload. Adds the allocator traits, handle types (BStackRange, BStackOwnedSlice, BStackSlice, BStackChunk), LinearBStackAllocator, and DebugCheckingAllocator. Combined with set, also enables BStackSliceWriter, FirstFitBStackAllocator, GhostTreeBstackAllocator, SlabBStackAllocator, CheckedSlabBStackAllocator, SegregatedBStackAllocator (experimental), and BStackByteVec.
atomic — Compound read-modify-write operations that hold the write lock across what would otherwise be separate calls. Combined with set, also enables atomic swap, CAS, in-place batch writes, and cross-region operations.

Enable with:

[dependencies]
bstack = { version = "0.4", features = ["set"] }
# or
bstack = { version = "0.4", features = ["alloc"] }
# or both
bstack = { version = "0.4", 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.
BStackUninitAllocator — opt-in extension trait for BStackAllocator whose alloc_uninit / realloc_uninit skip zero-initialising newly allocated or grown bytes. The returned bytes are unspecified (leftover from a prior allocation) but always valid to read, saving the zero-fill write for callers that overwrite the region before reading it. Existing bytes are preserved exactly as realloc. Implementing it is optional and signals that the allocator actually has a cheaper uninitialised path. Implemented by SlabBStackAllocator, GhostTreeBstackAllocator, CheckedSlabBStackAllocator, SegregatedBStackAllocator and FirstFitBStackAllocator, and forwarded by DebugCheckingAllocator when its inner allocator implements it. LinearBStackAllocator deliberately does not: a bump allocator only ever hands out freshly extended tail, whose zeroes cost no write I/O.
BStackAllocError<'a, A> — error returned by realloc / dealloc. Carries the failing source plus handle: Option<A::Allocated<'a>>, the surviving allocation handed back to the caller so a failed resize/free is not a silent leak. BStackBulkAllocError is its dealloc_bulk counterpart, returning a Vec of the handles it did not free.
BStackRange — raw (offset, len) pair; Copy, no pointer, no I/O. Serialises to/from [u8; 16] for persistent bookkeeping.
BStackOwnedSlice<'a, A> — ownership handle returned by alloc / realloc. Non-Copy, non-Clone; owns the allocation lifetime 'a. Exposes as_slice() / as_slice_mut() to obtain a borrowed view, and also provides convenience read* / write* / zero* methods that delegate via those views. Passed by value to realloc and dealloc; Drop is a no-op.
BStackSlice<'a> — borrowed I/O view over a region. Non-Copy; obtained from BStackOwnedSlice::as_slice[_mut]() or directly from BStackSlice::from_raw_parts. 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> — 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. Requires both alloc and set features. Send in all configurations; Send + Sync with the atomic feature, where an internal Mutex serialises AVL tree mutations.
SlabBStackAllocator — 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; with atomic additionally implements BStackBulkAllocator (alloc_bulk/dealloc_bulk).
CheckedSlabBStackAllocator — 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; with atomic additionally implements BStackBulkAllocator (alloc_bulk/dealloc_bulk).
SegregatedBStackAllocator — experimental segregated (binned) free-list allocator. Generalises CheckedSlabBStackAllocator from one block size to 33 size classes sharing a single arena: 16 linear classes (16‥256 B, step 16), 16 geometric classes (320‥4096 B, 4 per octave), and one shared oversized bucket. Each class is an independent intrusive free list; the class is computed from the request with register arithmetic (no tables), giving O(1) classed alloc/dealloc. Every block carries the same 8-byte overhead tag as the checked slab, so leaked blocks are reclaimable by a linear scan and double-frees are caught. A single new constructor initialises an empty stack or reopens one (running recovery automatically). Requires both alloc and set; Send in all configurations, Send + Sync with atomic (no allocator-level lock — free-list splices ride BStack::process_gen/BStack::inplace_gen), where it additionally implements BStackBulkAllocator (alloc_bulk/dealloc_bulk, work bounded by the classes touched, with oversized requests matched largest-first against the oversized free list). Experimental: the on-disk format and API may change, some resize paths differ between the atomic and non-atomic builds, and the deep in-use-leak GC is not yet implemented (the free-neighbour coalescer, coalesce, now is — atomic only).
DebugCheckingAllocator<A> — transparent debug wrapper. Wraps any allocator whose Allocated type is BStackOwnedSlice and whose Error is io::Error. Tracks allocated and freed regions in memory and panics on overlapping allocations, double-frees, partial-frees, and multi-span frees. When the inner allocator reports a lost handle (handle: None in BStackAllocError), the region is removed from tracking entirely — its fate is unknown, so neither “live” nor “freed” would be correct. Intended for tests and debugging; O(n) per-operation overhead. Requires alloc only.
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, extend_from_slice, pop, get, set, read_bytes, as_slice, truncate, clear, fill, reserve, reserve_exact, resize, shrink_to, shrink_to_fit, and iter. With the atomic feature it also gains the crash-atomic byte movers insert, remove, swap_remove, extend_from_within, and the cross-slice extend_from_bstack_slice, copy_into_bstack_slice, append_from_owned, and move_tail_into. 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

BStackOwnedSlice<'a, A> borrows the allocator for 'a. The borrow checker statically prevents calling BStackAllocator::into_stack — which consumes the allocator by value — while any owned slice is still in scope. BStackSlice<'a> views obtained via as_slice[_mut]() have a shorter lifetime tied to the borrow of the owned slice, preventing them from outliving the handle that owns the region.

What lifetimes cannot express is that a handle goes back to the allocator that issued it: two allocators of the same type are the same type, so a2.dealloc(h1) compiles. That is not a soundness problem — handles are (offset, len) coordinates into a file, not pointers — but it would corrupt a2’s bookkeeping, so every allocator rejects a foreign handle at run time with io::ErrorKind::InvalidInput, returning the handle intact and its own metadata untouched. BStackOwnedSlice::is_from is the check, for custom allocators that need it.

§Quick example

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

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

let mut 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);

§Fault injection (`fault-injection` feature)

This build has the dev/test-only fault-injection feature active, so BStack I/O can be made to fail on demand. Implement FaultPolicy and arm it with BStack::with_fault_policy (at construction) or BStack::set_fault_policy (arm, re-arm, or disarm mid-test); every I/O method then consults the policy once, after validating its arguments. This exercises error-handling and rollback paths that a successful sequence of calls can never reach. The whole mechanism is gated on all(debug_assertions, feature = "fault-injection"), so a --release build carries none of it and its performance is unaffected. See the fault module for details.

Re-exports§

pub use fault::FaultPolicy;
pub use fault::FaultState;

Modules§

fault: Deterministic I/O-fault injection at the BStack API level.
reborrow: Lifetime-extending reborrows for generator call sites.

Macros§

bstack_unsafe_reborrow: Extends a shared borrow so it can escape a process_gen / inplace_gen generator closure.
bstack_unsafe_reborrow_mut: Extends a mutable borrow so it can escape a process_gen / inplace_gen generator closure.

Structs§

BStack: A persistent, fsync-durable binary stack backed by a single file.
BStackAllocError: Error returned by BStackAllocator::realloc and BStackAllocator::dealloc when the operation fails.
BStackBulkAllocError: Error returned by BStackBulkAllocator::dealloc_bulk when the bulk free fails, carrying back the handles that were not freed.
BStackByteVec: A growable byte vector backed by a crate::BStack allocation.
BStackByteVecIter: An iterator over the bytes of a BStackByteVec.
BStackChunk: A fixed-size-record view over a BStackSlice — a slice with a stride.
BStackChunkIter: A lazy, zero-I/O iterator over the chunks of a BStackChunk.
BStackJoinError: Error returned by BStackOwnedSlice::try_join and try_join_inplace when the concatenation fails.
BStackOwnedSlice: An owned allocation handle for a region managed by a BStackAllocator.
BStackRange: A raw (offset, len) coordinate pair with no backing reference.
BStackReader: A cursor-based reader over a BStack payload.
BStackSlice: A borrowed, non-owning view of a contiguous region within a BStack payload.
BStackSliceError: Error returned by BStackOwnedSlice::try_subslice and try_subslice_inplace when the narrowing fails.
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.
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.
InterruptedWrite: The error a read carries while an interrupted write is pending replay.
LinearBStackAllocator: A simple bump allocator that owns a BStack and allocates regions sequentially by appending to the tail.
SegregatedBStackAllocator: A segregated free-list allocator implementing BStackAllocator on top of a BStack.
SlabBStackAllocator: A fixed-block slab allocator implementing BStackAllocator on top of a BStack.

Enums§

BStackGenOp: A request to read from, or write to, a region of the payload.

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.
BStackInPlaceResizeAllocator: Extension trait for allocators that can resize a region at either edge without relocating its retained bytes.
BStackOwnedSliceAllocator: Convenience supertrait for the common case of a BStackAllocator whose handle type is BStackOwnedSlice and whose error type is io::Error.
BStackUninitAllocator: Extension trait for allocators that can skip zero-initialisation of newly allocated or grown regions.

Crate bstack

Crate bstack Copy item path

§Overview

§File format

§Crash recovery

§Deferred replay

§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

§Fault injection (fault-injection feature)

Re-exports§

Modules§

Macros§

Structs§

Enums§

Traits§

Crate bstack

§Locked region (`lock_up_to`)

§`BStack`

§`BStackReader`

§Allocator (`alloc` feature)

§Fault injection (`fault-injection` feature)