planarian_schema/
gc.rs

1//! Garbage-collection planning under the §12b bounds. Pure: the backends
2//! measure, this decides.
3//!
4//! Two bounds hold at once: keep at most `keep` generations, and keep their
5//! store closures within `max_bytes`. Whichever is exceeded, generations are
6//! collected oldest first until both hold. The protected set (I3) is never
7//! collected; if it alone exceeds the space bound, everything unprotected is
8//! collected and the shortfall is reported (`BudgetUnsatisfiable`): the budget
9//! is then a target, not a guarantee.
10
11use crate::ids::{GenerationId, Timestamp};
12use serde::{Deserialize, Serialize};
13
14/// Owner settings (`services.planarian.gc`), not manifest options.
15#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
16#[serde(rename_all = "camelCase", default)]
17pub struct GcBudget {
18    /// Generations to keep at most (§12b default 10).
19    pub keep_generations: usize,
20    /// Generations may use at most this share of the Nix store's
21    /// filesystem, in tenths of a percent (§12b default 20% = 200).
22    pub generations_permille: u32,
23    /// Generations to keep at most in an emergency (the store or journal
24    /// filesystem is nearly full).
25    pub keep_emergency: usize,
26    /// `services.planarian.gc.retainAllGenerations`: never collect a
27    /// generation, even in an emergency (a full history, or generations kept
28    /// for export). Other store garbage is still collected; a space bound the
29    /// generations exceed is reported, never enforced.
30    pub retain_all: bool,
31}
32
33impl Default for GcBudget {
34    fn default() -> Self {
35        GcBudget { keep_generations: 10, generations_permille: 200, keep_emergency: 3, retain_all: false }
36    }
37}
38
39impl GcBudget {
40    /// The space bound for a filesystem of `fs_bytes`.
41    pub fn max_bytes(&self, fs_bytes: u64) -> u64 {
42        (fs_bytes as u128 * self.generations_permille as u128 / 1000) as u64
43    }
44
45    /// The generations `plan` may not collect: the I3 set, and with
46    /// `retain_all` every generation on disk.
47    pub fn protected(&self, on_disk: &[GenerationId], protect: &[GenerationId]) -> Vec<GenerationId> {
48        if self.retain_all { on_disk.to_vec() } else { protect.to_vec() }
49    }
50}
51
52#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
53pub struct GcPlan {
54    /// Oldest first.
55    pub delete: Vec<GenerationId>,
56    pub kept: Vec<GenerationId>,
57    /// Size of the kept generations' closures, when known.
58    pub kept_bytes: u64,
59    pub max_bytes: u64,
60    /// `BudgetUnsatisfiable`: the protected set alone is this far over the space bound.
61    pub shortfall: Option<u64>,
62}
63
64/// Plan a collection. `gens` are the generations on disk, `protect` the I3
65/// set; `measure` gives the size of a set of generations' combined closures.
66pub fn plan(
67    gens: &[GenerationId],
68    protect: &[GenerationId],
69    keep: usize,
70    max_bytes: u64,
71    mut measure: impl FnMut(&[GenerationId]) -> u64,
72) -> GcPlan {
73    let mut kept: Vec<GenerationId> = gens.to_vec();
74    kept.sort();
75    kept.dedup();
76    let mut delete = vec![];
77    let mut bytes = measure(&kept);
78    loop {
79        if kept.len() <= keep && bytes <= max_bytes {
80            break;
81        }
82        let Some(i) = kept.iter().position(|g| !protect.contains(g)) else { break };
83        delete.push(kept.remove(i));
84        bytes = measure(&kept);
85    }
86    let shortfall = (bytes > max_bytes).then(|| bytes - max_bytes);
87    GcPlan { delete, kept, kept_bytes: bytes, max_bytes, shortfall }
88}
89
90/// The last collection's result, for `planarian status` and the console.
91#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
92pub struct SpaceReport {
93    pub at: Timestamp,
94    pub generations: usize,
95    pub bytes: u64,
96    pub max_bytes: u64,
97    pub collected: usize,
98    pub shortfall: Option<u64>,
99}
100
101impl SpaceReport {
102    pub fn of(plan: &GcPlan, at: Timestamp) -> SpaceReport {
103        SpaceReport {
104            at,
105            generations: plan.kept.len(),
106            bytes: plan.kept_bytes,
107            max_bytes: plan.max_bytes,
108            collected: plan.delete.len(),
109            shortfall: plan.shortfall,
110        }
111    }
112}
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117
118    fn g(n: u64) -> GenerationId {
119        GenerationId(n)
120    }
121
122    const GB: u64 = 1 << 30;
123
124    /// Each generation's closure is 2 GB with nothing shared.
125    fn size(gs: &[GenerationId]) -> u64 {
126        gs.len() as u64 * 2 * GB
127    }
128
129    #[test]
130    fn retain_all_collects_no_generation_and_reports_the_overrun() {
131        let gens: Vec<_> = (1..=13).map(g).collect();
132        let b = GcBudget { retain_all: true, ..GcBudget::default() };
133        let p = plan(&gens, &b.protected(&gens, &[g(13)]), b.keep_emergency, 7 * GB, size);
134        assert!(p.delete.is_empty());
135        assert_eq!(p.kept.len(), 13);
136        assert_eq!(p.shortfall, Some(26 * GB - 7 * GB));
137    }
138
139    #[test]
140    fn count_bound_collects_oldest_first() {
141        let gens: Vec<_> = (1..=13).map(g).collect();
142        let p = plan(&gens, &[g(2), g(13)], 10, u64::MAX, size);
143        assert_eq!(p.delete, vec![g(1), g(3), g(4)]);
144        assert_eq!(p.kept.len(), 10);
145        assert!(p.kept.contains(&g(2)), "protected stays even when oldest");
146        assert_eq!(p.shortfall, None);
147    }
148
149    #[test]
150    fn space_bound_collects_below_the_count() {
151        let gens: Vec<_> = (1..=6).map(g).collect();
152        let p = plan(&gens, &[g(6)], 10, 7 * GB, size);
153        assert_eq!(p.delete, vec![g(1), g(2), g(3)]);
154        assert_eq!(p.kept_bytes, 6 * GB);
155        assert_eq!(p.shortfall, None);
156    }
157
158    #[test]
159    fn unsatisfiable_budget_never_touches_the_protected_set() {
160        let gens: Vec<_> = (1..=5).map(g).collect();
161        let protect = [g(1), g(4), g(5)];
162        let p = plan(&gens, &protect, 10, GB, size);
163        assert_eq!(p.delete, vec![g(2), g(3)]);
164        assert_eq!(p.kept, protect.to_vec());
165        assert_eq!(p.shortfall, Some(5 * GB));
166    }
167
168    #[test]
169    fn within_both_bounds_collects_nothing() {
170        let gens: Vec<_> = (1..=4).map(g).collect();
171        let p = plan(&gens, &[], 10, 100 * GB, size);
172        assert!(p.delete.is_empty());
173    }
174
175    #[test]
176    fn budget_share() {
177        assert_eq!(GcBudget::default().max_bytes(100 * GB), 20 * GB);
178    }
179}
planarian_schema/gc.rs

planarian_schema/
gc.rs
