kache_fs/
ledger.rs

1//! Hard-link accounting.
2//!
3//! A hard-linked file frees nothing until its *last* name goes, so a sum that
4//! counts each name separately overstates reclaim. The ledger counts an inode
5//! once, and tracks which inodes still have links *outside* the measured set —
6//! those bytes will not actually come back, and callers must be able to say so.
7
8use std::collections::HashMap;
9
10use crate::FileSizing;
11
12/// Filesystem-unique file identity.
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15pub struct InodeId {
16    pub dev: u64,
17    pub ino: u64,
18}
19
20#[derive(Debug, Clone, Copy)]
21struct Entry {
22    links_seen: u64,
23    nlink: u64,
24    allocated: u64,
25    unique: u64,
26}
27
28#[derive(Debug, Default)]
29pub struct InodeLedger {
30    seen: HashMap<InodeId, Entry>,
31}
32
33impl InodeLedger {
34    pub fn new() -> Self {
35        Self::default()
36    }
37
38    /// Should this file's bytes be added to the running total?
39    ///
40    /// `false` for a second or later link to an inode already counted.
41    pub fn admit(&mut self, s: &FileSizing) -> bool {
42        if s.nlink <= 1 {
43            return true;
44        }
45        match self.seen.get_mut(&s.inode) {
46            Some(e) => {
47                e.links_seen += 1;
48                false
49            }
50            None => {
51                self.seen.insert(
52                    s.inode,
53                    Entry {
54                        links_seen: 1,
55                        nlink: s.nlink,
56                        allocated: s.allocated,
57                        unique: s.unique.unwrap_or(0),
58                    },
59                );
60                true
61            }
62        }
63    }
64
65    /// Inodes counted that still have names outside the measured set. Their
66    /// bytes were included in the total but will NOT be freed by deleting the
67    /// set — report this rather than over-promising.
68    pub fn pinned_outside(&self) -> PinnedOutside {
69        let mut p = PinnedOutside::default();
70        for e in self.seen.values() {
71            if e.links_seen < e.nlink {
72                p.inodes += 1;
73                p.bytes += e.allocated;
74                p.unique_bytes += e.unique;
75            }
76        }
77        p
78    }
79
80    pub fn distinct_inodes(&self) -> usize {
81        self.seen.len()
82    }
83}
84
85/// Multiply-linked data counted in a total but retained by names elsewhere.
86#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
87#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
88pub struct PinnedOutside {
89    pub inodes: u64,
90    /// Allocated bytes retained by another hard-link name.
91    pub bytes: u64,
92    /// Bytes that would otherwise have been counted as physically reclaimable.
93    #[cfg_attr(feature = "serde", serde(default))]
94    pub unique_bytes: u64,
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100    use crate::Sharing;
101
102    fn f(ino: u64, nlink: u64, allocated: u64) -> FileSizing {
103        FileSizing {
104            logical: allocated,
105            allocated,
106            unique: Some(allocated),
107            sharing: Sharing::None,
108            inode: InodeId { dev: 1, ino },
109            nlink,
110            clone_id: None,
111            clone_refcount: None,
112        }
113    }
114
115    #[test]
116    fn counts_an_inode_once_regardless_of_link_count() {
117        let mut l = InodeLedger::new();
118        assert_eq!(l.distinct_inodes(), 0);
119        assert!(l.admit(&f(7, 2, 100)));
120        assert!(!l.admit(&f(7, 2, 100)));
121        assert_eq!(l.distinct_inodes(), 1);
122        assert!(l.admit(&f(8, 2, 100)));
123        assert_eq!(l.distinct_inodes(), 2);
124    }
125
126    #[test]
127    fn unlinked_files_always_admitted() {
128        let mut l = InodeLedger::new();
129        assert!(l.admit(&f(1, 1, 10)));
130        assert!(l.admit(&f(2, 1, 10)));
131        assert_eq!(l.pinned_outside(), PinnedOutside::default());
132    }
133
134    #[test]
135    fn reports_bytes_pinned_by_links_outside_the_set() {
136        let mut l = InodeLedger::new();
137        // nlink=3 but only two names live inside the walked set.
138        l.admit(&f(9, 3, 4096));
139        l.admit(&f(9, 3, 4096));
140        assert_eq!(
141            l.pinned_outside(),
142            PinnedOutside {
143                inodes: 1,
144                bytes: 4096,
145                unique_bytes: 4096,
146            }
147        );
148    }
149
150    #[test]
151    fn fully_contained_hardlinks_are_not_pinned() {
152        let mut l = InodeLedger::new();
153        l.admit(&f(9, 2, 4096));
154        l.admit(&f(9, 2, 4096));
155        assert_eq!(l.pinned_outside(), PinnedOutside::default());
156    }
157}
kache_fs/ledger.rs

kache_fs/
ledger.rs
