microsandbox_utils/
extent.rs

1//! Filesystem allocation-map scanning.
2//!
3//! Answers one question — "which byte ranges of this file are actually allocated?" — with the same `(offset, length)` shape on every supported platform: `SEEK_DATA`/`SEEK_HOLE` on
4//! unix, `FSCTL_QUERY_ALLOCATED_RANGES` on Windows. Consumers (sparse snapshot export, integrity verification, capture) never branch on OS; only the scan backend does.
5//!
6//! Also home to the hole-restoration primitives that the scan's consumers need on platforms where "just don't write the hole" is not enough: NTFS only keeps unwritten ranges
7//! unallocated on files flagged sparse ([`mark_sparse`]), and APFS densifies files on any write, so holes must be punched explicitly ([`punch_hole_aligned`]).
8
9use std::fs::File;
10use std::io;
11use std::path::Path;
12
13#[cfg(unix)]
14use std::os::unix::io::AsRawFd;
15#[cfg(windows)]
16use std::os::windows::io::AsRawHandle;
17#[cfg(windows)]
18use std::ptr;
19
20#[cfg(windows)]
21use windows_sys::Win32::Foundation::{ERROR_MORE_DATA, HANDLE};
22#[cfg(windows)]
23use windows_sys::Win32::System::IO::DeviceIoControl;
24#[cfg(windows)]
25use windows_sys::Win32::System::Ioctl::{
26    FILE_ALLOCATED_RANGE_BUFFER, FSCTL_QUERY_ALLOCATED_RANGES, FSCTL_SET_SPARSE,
27};
28
29//--------------------------------------------------------------------------------------------------
30// Types
31//--------------------------------------------------------------------------------------------------
32
33/// Allocation map of a file: logical length plus sorted, non-overlapping, byte-granular data extents.
34#[derive(Debug, Clone, PartialEq, Eq)]
35pub struct ExtentMap {
36    /// Logical (apparent) file size in bytes.
37    pub len: u64,
38    /// Sorted `(offset, length)` allocated ranges. Everything outside them reads as zeros.
39    pub extents: Vec<(u64, u64)>,
40}
41
42//--------------------------------------------------------------------------------------------------
43// Methods
44//--------------------------------------------------------------------------------------------------
45
46impl ExtentMap {
47    /// Scan `path`'s allocation map.
48    ///
49    /// Returns `Ok(None)` when the filesystem cannot enumerate extents (no `SEEK_DATA` / allocated-ranges support); callers should then treat the file as fully dense. A dense file
50    /// on a capable filesystem scans as `Some` with a single `(0, len)` extent.
51    ///
52    /// **Blocking.** Callers in async contexts should wrap in `tokio::task::spawn_blocking`.
53    pub fn scan(path: &Path) -> io::Result<Option<ExtentMap>> {
54        let file = File::open(path)?;
55        Self::scan_file(&file)
56    }
57
58    /// [`ExtentMap::scan`] over an already-open file.
59    pub fn scan_file(file: &File) -> io::Result<Option<ExtentMap>> {
60        let len = file.metadata()?.len();
61        if len == 0 {
62            return Ok(Some(ExtentMap {
63                len,
64                extents: Vec::new(),
65            }));
66        }
67        scan_impl(file, len)
68    }
69
70    /// Sum of extent lengths — the bytes a sparse-aware reader must actually move.
71    pub fn data_bytes(&self) -> u64 {
72        self.extents.iter().map(|(_, len)| len).sum()
73    }
74
75    /// True when some of the logical range is unallocated.
76    pub fn has_holes(&self) -> bool {
77        self.data_bytes() < self.len
78    }
79}
80
81//--------------------------------------------------------------------------------------------------
82// Functions
83//--------------------------------------------------------------------------------------------------
84
85/// Flag `file` as sparse so NTFS keeps unwritten ranges unallocated. No-op semantics on filesystems where files are implicitly hole-capable is handled by the unix definition
86/// below.
87#[cfg(windows)]
88pub fn mark_sparse(file: &File) -> io::Result<()> {
89    let mut bytes_returned = 0;
90    let ok = unsafe {
91        DeviceIoControl(
92            file.as_raw_handle() as HANDLE,
93            FSCTL_SET_SPARSE,
94            ptr::null(),
95            0,
96            ptr::null_mut(),
97            0,
98            &mut bytes_returned,
99            ptr::null_mut(),
100        )
101    };
102    if ok == 0 {
103        return Err(io::Error::last_os_error());
104    }
105    Ok(())
106}
107
108/// Unix files are hole-capable without any flag; kept so callers can mark destinations unconditionally.
109#[cfg(unix)]
110pub fn mark_sparse(_file: &File) -> io::Result<()> {
111    Ok(())
112}
113
114/// Punch a hole over as much of `[offset, offset + len)` as the filesystem's allocation block size allows, shrinking the range inward to block alignment. Ranges smaller than one
115/// block are left allocated. Needed on APFS, which densifies a file on any write — unwritten ranges do not stay holes the way they do on ext4/XFS.
116#[cfg(target_os = "macos")]
117pub fn punch_hole_aligned(file: &File, offset: u64, len: u64) -> io::Result<()> {
118    let block = allocation_block_size(file)?;
119    let start = offset.div_ceil(block).saturating_mul(block);
120    let end = (offset.saturating_add(len) / block).saturating_mul(block);
121    if end <= start {
122        return Ok(());
123    }
124    let args = libc::fpunchhole_t {
125        fp_flags: 0,
126        reserved: 0,
127        fp_offset: start as libc::off_t,
128        fp_length: (end - start) as libc::off_t,
129    };
130    let rc = unsafe { libc::fcntl(file.as_raw_fd(), libc::F_PUNCHHOLE, &args) };
131    if rc != 0 {
132        return Err(io::Error::last_os_error());
133    }
134    Ok(())
135}
136
137/// Hole punching is unnecessary outside macOS: on ext4/XFS/btrfs (and on NTFS files flagged via [`mark_sparse`]) ranges that are never written stay unallocated.
138#[cfg(not(target_os = "macos"))]
139pub fn punch_hole_aligned(_file: &File, _offset: u64, _len: u64) -> io::Result<()> {
140    Ok(())
141}
142
143//--------------------------------------------------------------------------------------------------
144// Functions: Helpers
145//--------------------------------------------------------------------------------------------------
146
147#[cfg(unix)]
148fn scan_impl(file: &File, len: u64) -> io::Result<Option<ExtentMap>> {
149    let fd = file.as_raw_fd();
150
151    let mut extents: Vec<(u64, u64)> = Vec::new();
152    let mut off: i64 = 0;
153    while (off as u64) < len {
154        let data_start = unsafe { libc::lseek(fd, off, libc::SEEK_DATA) };
155        if data_start < 0 {
156            let err = io::Error::last_os_error();
157            match err.raw_os_error() {
158                // No more data past this offset: trailing hole.
159                Some(libc::ENXIO) => break,
160                // Filesystem doesn't implement the seek flags — report "can't enumerate" rather than failing the caller. ENOTSUP and EOPNOTSUPP are distinct on macOS / BSDs.
161                Some(libc::EINVAL) | Some(libc::ENOTSUP) => return Ok(None),
162                #[cfg(not(target_os = "linux"))]
163                Some(libc::EOPNOTSUPP) => return Ok(None),
164                _ => return Err(err),
165            }
166        }
167        let data_end = unsafe { libc::lseek(fd, data_start, libc::SEEK_HOLE) };
168        if data_end < 0 {
169            return Err(io::Error::last_os_error());
170        }
171        let data_end = (data_end as u64).min(len);
172        let data_start = data_start as u64;
173        if data_end <= data_start {
174            break;
175        }
176        extents.push((data_start, data_end - data_start));
177        off = data_end as i64;
178    }
179
180    Ok(Some(ExtentMap { len, extents }))
181}
182
183#[cfg(windows)]
184fn scan_impl(file: &File, len: u64) -> io::Result<Option<ExtentMap>> {
185    // Query in batches; ERROR_MORE_DATA means the output buffer filled and the walk continues from the end of the last returned range.
186    const BATCH: usize = 64;
187
188    let handle = file.as_raw_handle() as HANDLE;
189    let mut extents: Vec<(u64, u64)> = Vec::new();
190    let mut next_offset: u64 = 0;
191
192    while next_offset < len {
193        let query = FILE_ALLOCATED_RANGE_BUFFER {
194            FileOffset: next_offset as i64,
195            Length: (len - next_offset) as i64,
196        };
197        let mut out = [FILE_ALLOCATED_RANGE_BUFFER {
198            FileOffset: 0,
199            Length: 0,
200        }; BATCH];
201        let mut bytes_returned: u32 = 0;
202        let ok = unsafe {
203            DeviceIoControl(
204                handle,
205                FSCTL_QUERY_ALLOCATED_RANGES,
206                &query as *const _ as *const _,
207                size_of::<FILE_ALLOCATED_RANGE_BUFFER>() as u32,
208                out.as_mut_ptr() as *mut _,
209                (size_of::<FILE_ALLOCATED_RANGE_BUFFER>() * BATCH) as u32,
210                &mut bytes_returned,
211                ptr::null_mut(),
212            )
213        };
214        let more = if ok == 0 {
215            let err = io::Error::last_os_error();
216            if err.raw_os_error() == Some(ERROR_MORE_DATA as i32) {
217                true
218            } else {
219                // Filesystem without allocated-range support (FAT, network shares): report "can't enumerate".
220                return Ok(None);
221            }
222        } else {
223            false
224        };
225
226        let count = bytes_returned as usize / size_of::<FILE_ALLOCATED_RANGE_BUFFER>();
227        if count == 0 {
228            break;
229        }
230        for range in &out[..count] {
231            let start = range.FileOffset as u64;
232            let end = (start + range.Length as u64).min(len);
233            if end > start {
234                extents.push((start, end - start));
235            }
236        }
237        let (last_off, last_len) = extents[extents.len() - 1];
238        next_offset = last_off + last_len;
239        if !more {
240            break;
241        }
242    }
243
244    Ok(Some(ExtentMap { len, extents }))
245}
246
247/// Fundamental allocation block size of the filesystem hosting `file`.
248#[cfg(target_os = "macos")]
249fn allocation_block_size(file: &File) -> io::Result<u64> {
250    let mut stat: libc::statfs = unsafe { std::mem::zeroed() };
251    let rc = unsafe { libc::fstatfs(file.as_raw_fd(), &mut stat) };
252    if rc != 0 {
253        return Err(io::Error::last_os_error());
254    }
255    Ok((stat.f_bsize as u64).max(512))
256}
257
258//--------------------------------------------------------------------------------------------------
259// Tests
260//--------------------------------------------------------------------------------------------------
261
262#[cfg(test)]
263mod tests {
264    use std::io::{Seek, SeekFrom, Write};
265
266    use super::*;
267
268    #[test]
269    fn dense_file_scans_as_single_extent_or_unsupported() {
270        let dir = tempfile::tempdir().unwrap();
271        let path = dir.path().join("dense.bin");
272        std::fs::write(&path, vec![0xAB; 8192]).unwrap();
273
274        match ExtentMap::scan(&path).unwrap() {
275            None => {} // FS can't enumerate; callers treat as dense
276            Some(map) => {
277                assert_eq!(map.len, 8192);
278                assert_eq!(map.data_bytes(), 8192);
279                assert!(!map.has_holes());
280            }
281        }
282    }
283
284    #[test]
285    fn empty_file_scans_as_empty_map() {
286        let dir = tempfile::tempdir().unwrap();
287        let path = dir.path().join("empty.bin");
288        std::fs::write(&path, b"").unwrap();
289
290        let map = ExtentMap::scan(&path).unwrap().unwrap();
291        assert_eq!(map.len, 0);
292        assert!(map.extents.is_empty());
293        assert!(!map.has_holes());
294    }
295
296    #[test]
297    fn sparse_file_scan_covers_all_data() {
298        let dir = tempfile::tempdir().unwrap();
299        let path = dir.path().join("sparse.bin");
300        let len: u64 = 8 * 1024 * 1024;
301        let mut f = std::fs::OpenOptions::new()
302            .read(true)
303            .write(true)
304            .create(true)
305            .truncate(true)
306            .open(&path)
307            .unwrap();
308        // Mark before extending so NTFS keeps the gap a hole.
309        mark_sparse(&f).unwrap();
310        f.set_len(len).unwrap();
311        f.seek(SeekFrom::Start(0)).unwrap();
312        f.write_all(&[0x11; 4096]).unwrap();
313        f.seek(SeekFrom::Start(4 * 1024 * 1024)).unwrap();
314        f.write_all(&[0x22; 4096]).unwrap();
315        f.sync_all().unwrap();
316        punch_hole_aligned(&f, 4096, 4 * 1024 * 1024 - 4096).unwrap();
317        punch_hole_aligned(&f, 4 * 1024 * 1024 + 4096, len - (4 * 1024 * 1024 + 4096)).unwrap();
318        drop(f);
319
320        let Some(map) = ExtentMap::scan(&path).unwrap() else {
321            eprintln!("filesystem can't enumerate extents; scan not exercised");
322            return;
323        };
324        assert_eq!(map.len, len);
325        // Extents must cover both data ranges (a densifying FS may report more than the written bytes, never less).
326        let covers = |target: u64| {
327            map.extents
328                .iter()
329                .any(|(off, l)| *off <= target && target < off + l)
330        };
331        assert!(covers(0), "extent map misses data at 0: {:?}", map.extents);
332        assert!(
333            covers(4 * 1024 * 1024),
334            "extent map misses data at 4 MiB: {:?}",
335            map.extents
336        );
337    }
338}
microsandbox_utils/extent.rs

microsandbox_utils/
extent.rs
