gonzalo_core/
gc.rs

1//! Mark-sweep garbage collection for content-addressed slices (ADR 0012).
2//!
3//! A slice blob is *live* iff some live manifest references its hash. GC marks
4//! the union of every live manifest's hashes, then sweeps any stored blob
5//! outside that set. Liveness is derived from the manifests themselves rather
6//! than a maintained refcount, so it is self-correcting: a missed event can
7//! leave a slice briefly un-swept, never wrongly deleted, and never leaked
8//! forever the way a drifted refcount would.
9
10use crate::{BlobStore, ContentHash, Manifest, Result};
11use std::collections::BTreeSet;
12
13/// What a GC sweep did.
14#[derive(Clone, Debug, Default, PartialEq, Eq)]
15pub struct GcReport {
16    /// Hashes of blobs deleted because no live manifest referenced them.
17    pub freed: Vec<ContentHash>,
18    /// Count of blobs kept because they are still referenced.
19    pub retained: usize,
20}
21
22/// The mark set: every slice hash referenced by any of the `manifests`.
23pub fn live_slice_hashes<'a>(
24    manifests: impl IntoIterator<Item = &'a Manifest>,
25) -> BTreeSet<ContentHash> {
26    manifests
27        .into_iter()
28        .flat_map(|m| m.entries.values().cloned())
29        .collect()
30}
31
32/// The sweep set: hashes present in `all` but referenced by no live manifest,
33/// returned sorted (`all - live`).
34pub fn unreferenced_slices(all: &[ContentHash], live: &BTreeSet<ContentHash>) -> Vec<ContentHash> {
35    let mut garbage: Vec<ContentHash> =
36        all.iter().filter(|h| !live.contains(*h)).cloned().collect();
37    garbage.sort();
38    garbage.dedup();
39    garbage
40}
41
42/// Sweep `blobs`: delete every stored slice no `live_manifests` entry
43/// references, and report what was freed vs. retained. Mark-sweep — see the
44/// module docs for why this is preferred over refcounting.
45pub async fn gc_blobs<B: BlobStore>(blobs: &B, live_manifests: &[Manifest]) -> Result<GcReport> {
46    let all = blobs.list_blobs().await?;
47    let live = live_slice_hashes(live_manifests);
48    let freed = unreferenced_slices(&all, &live);
49    for hash in &freed {
50        blobs.delete_blob(hash).await?;
51    }
52    // `all` may list a hash more than once (unspecified order, no dedup
53    // guarantee), while `freed` is deduplicated. Count retained from a
54    // deduplicated set of all hashes so a repeated hash doesn't inflate the
55    // total and skew `retained`.
56    let distinct = all.iter().cloned().collect::<BTreeSet<_>>().len();
57    let retained = distinct - freed.len();
58    Ok(GcReport { freed, retained })
59}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    fn h(s: &str) -> ContentHash {
66        ContentHash::of(s.as_bytes())
67    }
68
69    #[test]
70    fn live_set_unions_all_manifest_references() {
71        let mut a = Manifest::new();
72        a.insert("x.rs", h("1"));
73        a.insert("y.rs", h("2"));
74        let mut b = Manifest::new();
75        b.insert("z.rs", h("2")); // shared slice, counted once
76        b.insert("w.rs", h("3"));
77
78        let live = live_slice_hashes([&a, &b]);
79        assert_eq!(live, BTreeSet::from([h("1"), h("2"), h("3")]));
80    }
81
82    #[test]
83    fn live_set_of_no_manifests_is_empty() {
84        assert!(live_slice_hashes([]).is_empty());
85    }
86
87    #[test]
88    fn unreferenced_is_all_minus_live_sorted() {
89        let all = vec![h("keep"), h("drop"), h("keep2")];
90        let live = BTreeSet::from([h("keep"), h("keep2")]);
91        let garbage = unreferenced_slices(&all, &live);
92        let mut want = vec![h("drop")];
93        want.sort();
94        assert_eq!(garbage, want);
95    }
96
97    #[test]
98    fn unreferenced_dedups_repeated_input_hashes() {
99        let all = vec![h("dup"), h("dup"), h("live")];
100        let live = BTreeSet::from([h("live")]);
101        assert_eq!(unreferenced_slices(&all, &live), vec![h("dup")]);
102    }
103
104    #[test]
105    fn nothing_unreferenced_when_all_are_live() {
106        let all = vec![h("a"), h("b")];
107        let live = BTreeSet::from([h("a"), h("b")]);
108        assert!(unreferenced_slices(&all, &live).is_empty());
109    }
110
111    /// A `BlobStore` whose `list_blobs` returns a fixed, possibly-duplicated
112    /// list of hashes and records which hashes `delete_blob` was called on.
113    #[derive(Default)]
114    struct FakeBlobs {
115        listed: Vec<ContentHash>,
116        deleted: std::sync::Mutex<Vec<ContentHash>>,
117    }
118
119    #[async_trait::async_trait]
120    impl BlobStore for FakeBlobs {
121        async fn put_blob(&self, content: &[u8]) -> Result<ContentHash> {
122            Ok(ContentHash::of(content))
123        }
124        async fn get_blob(&self, _hash: &ContentHash) -> Result<Option<Vec<u8>>> {
125            Ok(None)
126        }
127        async fn list_blobs(&self) -> Result<Vec<ContentHash>> {
128            Ok(self.listed.clone())
129        }
130        async fn delete_blob(&self, hash: &ContentHash) -> Result<()> {
131            self.deleted.lock().unwrap().push(hash.clone());
132            Ok(())
133        }
134    }
135
136    #[tokio::test]
137    async fn retained_counts_distinct_blobs_despite_duplicate_listing() {
138        // `list_blobs` reports `keep` twice and one unreferenced `drop`. There
139        // are two distinct blobs; one is freed, so exactly one is retained — the
140        // duplicate listing must not inflate `retained` to 2 (regression: #156).
141        let blobs = FakeBlobs {
142            listed: vec![h("keep"), h("keep"), h("drop")],
143            deleted: Default::default(),
144        };
145        let mut m = Manifest::new();
146        m.insert("f.rs", h("keep"));
147
148        let report = gc_blobs(&blobs, &[m]).await.unwrap();
149
150        assert_eq!(report.freed, vec![h("drop")]);
151        assert_eq!(report.retained, 1);
152        assert_eq!(*blobs.deleted.lock().unwrap(), vec![h("drop")]);
153    }
154}
gonzalo_core/gc.rs

gonzalo_core/
gc.rs
