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

microsandbox_utils/
extent.rs
