Module gc 

Mark–sweep garbage collection for the blob store.

The reference model (read this first)

cas-kit objects are opaque blobs: an object never references another object. There are no tree objects and no embedded pointers; the pack manifest (.idx) is a flat digest → offset map and expresses storage location, not reachability. Reachability therefore cannot be derived from store contents — the host application owns the reference graph (its manifests, message attachments, index rows, …).

Garbage collection is consequently an honest set difference:

1. Mark (mark) — the caller supplies every hash it still considers live (the roots). There is no transitive closure to walk: the mark phase validates the root set against what is physically present (loose files ∪ packed objects) and reports roots that resolve to nothing. Roots are the live set.
2. Plan (plan_sweep) — enumerate everything on disk, classify present − live as garbage, and decide per pack whether it can be removed outright or must be rewritten without its garbage (see Pack handling).
3. Sweep (sweep) — execute a plan in one of three modes: SweepMode::DryRun (change nothing), SweepMode::Trash (move garbage to <root>/trash/, recoverable) or SweepMode::Delete (unlink permanently).

If your application has internal references (e.g. a manifest blob listing chunk hashes), expand your roots to the full transitive closure before calling mark — the store cannot walk your graph for you.

Pack handling

Packs are immutable and have no per-blob delete, so packed garbage is reclaimed at pack granularity using a coverage rule:

• A pack whose objects are all garbage is removed (.idx first, then .pack).
• A pack with no garbage is left untouched, and its objects count as covered (they will survive elsewhere no matter what).
• A partial pack (some garbage) is rewritten with only the live objects it uniquely covers — needed = live-in-pack − covered, where covered starts as live loose objects plus all untouched packs. If needed is empty (every live object in the pack is also loose or in a healthy pack) the pack is removed without a rewrite; otherwise a new content-named pack is created holding exactly needed, and the old pair is removed. The rewrite is refcount-aware: an object that survives in some other location is not copied into a new pack.

Rewrites are ordered by pack path and the covered set grows as they proceed, so two overlapping partial packs never both copy the same object. Set SweepOptions::rewrite_partial_packs to false to leave all partial packs untouched (loose garbage is still reclaimed).

Crash safety

Every destructive step is a single file operation, and phases are ordered so a crash can lose garbage reclamation, never live data:

1. Rewrites run first and are additive: the replacement pack is fully written (.pack then .idx) before any old file is removed. A crash here leaves an extra pack — harmless duplicate storage that the next sweep reclaims (identical object sets produce identical content-derived pack names, so re-running converges). One narrow window exists: if the replacement pack’s name already exists from an earlier interrupted run, its .pack is truncated and rewritten in place; a crash mid-write leaves a torn pack whose objects may transiently fail reads with HashMismatch. No data is lost — the old packs are only removed after the new pair is fully written — and re-running the sweep repairs the torn pack.
2. Loose deletions unlink (or trash) one immutable file per call. A crash mid-loop leaves the remaining garbage for the next sweep.
3. Pack removals delete the .idx before the .pack; a crash between the two leaves an orphan .pack that no reader will ever open (packs without an index are skipped by crate::PackCache) and that the next sweep collects via the plan’s orphan list.
4. Trash mode moves files with rename(2) within the store root — atomic per file on POSIX. A crash mid-sweep leaves some garbage in <root>/trash/ and the rest in place; either way the store is consistent and a later sweep (or a manual restore) finishes the job.

Concurrency

• Reads of live objects are safe throughout a sweep: sweep never touches a file whose hash is in the live set. (POSIX: an in-flight read on an unlinked file keeps its fd; Windows: the unlink may fail with a sharing violation, surfacing as an I/O error — retry the sweep.)
• Writers racing the sweep: if a host re-puts a blob between enumeration and deletion, the sweep will delete the fresh copy (the address was classified garbage before the re-put). Quiesce writers with the same application-level lock your writers use, or re-run mark + sweep until the report is stable.
• Transient read errors during pack rewrites: a reader holding a stale in-memory pack index can hit a pack that was just removed; live objects remain readable via their other copies once the reader reloads its cache (crate::BlobStore::invalidate_pack_cache is called in-process; other processes see fresh state on next open). Retry the read, or schedule sweeps for windows where readers can tolerate a transient BlobNotFound.

Recoverability (trash mode)

SweepMode::Trash mirrors the removed relative paths under <root>/trash/ (trash/objects/<2-hex>/<62-hex>, trash/objects/pack/pack-<hex>.pack|.idx). Restoring is a reverse rename of the mirrored path; a colliding trash entry (same hash trashed twice) is overwritten with the newer copy. The trash directory is outside objects/, so the store never reads from it — leftover trash costs disk space only. Empty it once you are confident no restore is needed.

Async

The module is synchronous, matching the rest of the crate (filesystem operations dominate GC and blocking is the honest model). With the optional tokio feature, [mark_async] and [sweep_async] run the same code on the blocking thread pool; they take Arc<BlobStore> so the store can be moved into the spawned task.

Example

use std::collections::HashSet;

use cas_kit::gc::{self, SweepMode, SweepOptions};
use cas_kit::{BlobStore, Hash};

let store = BlobStore::new("/tmp/my-store")?;

// The host decides what is live (here: one blob, in general the whole
// transitive closure of your reference graph).
let roots: HashSet<Hash> = HashSet::from([store.put_blob(b"keep me")?]);
store.put_blob(b"garbage")?;

let live = gc::mark(&store, &roots)?;
assert!(live.missing.is_empty());

let live_set: HashSet<Hash> = live.live.iter().copied().collect();
let report = gc::sweep(&store, &live_set, SweepOptions {
    mode: SweepMode::Trash,
    ..SweepOptions::default()
})?;
assert_eq!(report.plan.garbage, 1);
assert_eq!(report.loose_removed, 1);

Structs

LiveSet

Result of the mark phase: the validated live set.

PackRewrite

A pack scheduled to be rewritten without some of its objects.

SweepOptions

Options for sweep.

SweepPlan

The result of enumerating the store and classifying garbage.

SweepReport

Outcome of an executed (or dry-run) sweep.

Enums

SweepMode

What to do with garbage during sweep.

Constants

TRASH_DIR

Name of the trash directory created under the store root when a sweep runs in SweepMode::Trash mode. Mirrored paths under this directory restore by renaming back into objects/.

Functions

mark

Validate the host’s live set against what the store physically holds.

plan_sweep

Enumerate the store, classify garbage, and decide pack handling without touching the filesystem.

sweep

Sweep the store: remove everything not in live, according to SweepOptions::mode.