ferrosys 0.8.0

Pure-Rust filesystem formatter and reader: ext4, ext3, ext2, FAT32, FAT16, FAT12, exFAT, btrfs, and APFS — rootless, in userspace, byte-reproducible
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
//! The metadata-checksum seam.
//!
//! ext4's `metadata_csum` feature protects every metadata object — the
//! superblock, group descriptors, inodes, bitmaps, extent-tree blocks, and
//! directory blocks — with a crc32c whose field lives inside the object. The
//! checksum algorithm sits behind the [`Checksummer`] trait, so the code that lays
//! objects out is independent of whether checksums are on.
//!
//! This module is pure and side-effect free. When the feature is on, [`Crc32c`] is
//! the active implementation: it reports [`CsumScheme::Crc32c`] and computes a real
//! crc32c seeded from the filesystem UUID. When it is off, [`NullCsum`] reports
//! [`CsumScheme::None`] and computes zero. Every checksum field is written through
//! this seam, so choosing between them is a change of implementation at one
//! construction site — the materializer picks the one the feature set calls for.

/// Which checksums a filesystem's metadata carries.
///
/// ext defines more than the two states "checksummed" and "not". `metadata_csum`
/// ([`Crc32c`](CsumScheme::Crc32c)) protects every metadata object with a crc32c; the
/// older `uninit_bg` (`GDT_CSUM`) protects the group descriptors alone with a crc16,
/// while carrying the same uninitialized-bitmap accounting; and a filesystem may have
/// neither. The two questions a caller asks — *is there a checksum field to fill in* and
/// *do the uninit descriptor flags mean anything* — have the same answer under the first
/// and the last scheme and different answers under the middle one, so they are asked
/// separately rather than through one flag.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum CsumScheme {
    /// No metadata checksums. Every checksum field is zero and the uninitialized-bitmap
    /// accounting does not apply.
    #[default]
    None,
    /// `metadata_csum`: a crc32c inside every metadata object, and the
    /// uninitialized-bitmap accounting.
    Crc32c,
}

impl CsumScheme {
    /// Whether metadata objects carry an in-object checksum field this crate fills in.
    ///
    /// Gates the per-object checksum writes: the superblock, inodes, extent nodes,
    /// directory blocks, bitmaps, and attribute blocks.
    #[must_use]
    pub const fn writes_object_checksums(self) -> bool {
        match self {
            Self::None => false,
            Self::Crc32c => true,
        }
    }

    /// Whether the `INODE_UNINIT` / `BLOCK_UNINIT` / `ITABLE_ZEROED` descriptor flags and
    /// the `bg_itable_unused` counts carry their meaning.
    ///
    /// A scheme without them writes `bg_flags` zero, because a flag no feature backs is
    /// one a checker faults.
    #[must_use]
    pub const fn uninit_bg_semantics(self) -> bool {
        match self {
            Self::None => false,
            Self::Crc32c => true,
        }
    }
}

/// Computes the checksums ext4 stores inside its metadata objects.
///
/// The one primitive is a seeded crc32c ([`crc32c`](Checksummer::crc32c)); each
/// metadata object seeds it from the filesystem seed and its own identity (inode
/// number, group number, block number) and feeds it the object's bytes. The
/// [`scheme`](Checksummer::scheme) an implementation reports says which checksums the
/// filesystem carries, and a caller gates every checksum field and every uninit
/// descriptor flag on it.
///
/// The trait is sealed: [`Crc32c`] and [`NullCsum`] are its implementations and no other
/// is possible. It is a seam so that laying objects out is independent of whether
/// checksums are on, not an extension point — a substitute that compiled but computed
/// the wrong value would produce an image this crate claims is checksummed and no
/// checker accepts.
pub trait Checksummer: crate::sealed::Sealed {
    /// Which checksums this filesystem carries.
    fn scheme(&self) -> CsumScheme;

    /// The base filesystem checksum seed — crc32c of the filesystem UUID — from
    /// which per-object seeds are derived. Zero when checksums are disabled.
    fn base_seed(&self) -> u32;

    /// crc32c of `data` continued from `seed`.
    ///
    /// Seeding lets a caller chain the filesystem seed and an object's identity
    /// before the object bytes, matching ext4's per-object checksum construction.
    /// Returns zero when checksums are disabled.
    fn crc32c(&self, seed: u32, data: &[u8]) -> u32;
}

/// The disabled checksummer: reports [`CsumScheme::None`] and computes zero.
///
/// This is the active implementation while `metadata_csum` is off. It writes no
/// checksum bytes and requests none of the uninit-bg descriptor semantics, so an
/// image built with it carries zeroed checksum fields — exactly what an external
/// checker expects when the feature bit is clear.
#[derive(Clone, Copy, Debug, Default)]
pub struct NullCsum;

impl crate::sealed::Sealed for NullCsum {}

impl Checksummer for NullCsum {
    fn scheme(&self) -> CsumScheme {
        CsumScheme::None
    }

    fn base_seed(&self) -> u32 {
        0
    }

    fn crc32c(&self, _seed: u32, _data: &[u8]) -> u32 {
        0
    }
}

/// The active checksummer when `metadata_csum` is on: a real crc32c seeded from the
/// filesystem UUID.
///
/// The base seed is `crc32c(!0, uuid)`, the value ext4 derives when the separate
/// `metadata_csum_seed` feature is absent, and every per-object checksum a caller builds
/// continues from it. `crc32c` is the raw continuation primitive, so a caller folds
/// the object's identity (inode number, group number, block number) and then its
/// bytes on top of a seed of its choice — the base seed for most objects, or `!0`
/// for the superblock, whose checksum ext4 seeds from `!0` rather than the UUID.
#[derive(Clone, Copy, Debug)]
pub struct Crc32c {
    base_seed: u32,
}

impl Crc32c {
    /// Build the checksummer for a filesystem with UUID `uuid`.
    #[must_use]
    pub fn new(uuid: &[u8; 16]) -> Self {
        Self {
            base_seed: crate::crc32c::crc32c(!0, uuid),
        }
    }

    /// Build the checksummer for a filesystem that stores its seed (`metadata_csum_seed`) rather
    /// than deriving it from the UUID. The stored seed is what its checksums were
    /// computed from, which the UUID need not agree with.
    #[must_use]
    pub fn with_seed(base_seed: u32) -> Self {
        Self { base_seed }
    }
}

impl crate::sealed::Sealed for Crc32c {}

impl Checksummer for Crc32c {
    fn scheme(&self) -> CsumScheme {
        CsumScheme::Crc32c
    }

    fn base_seed(&self) -> u32 {
        self.base_seed
    }

    fn crc32c(&self, seed: u32, data: &[u8]) -> u32 {
        crate::crc32c::crc32c(seed, data)
    }
}

// -- the per-object recipes -------------------------------------------------------------
//
// The seam above standardizes the primitive and the on/off decision. What each object folds
// into it before its own bytes — the seed, the identity words, which field participates as
// zero — is the format, and it is stated here once rather than once per direction. A writer
// stamping an object and a reader verifying one call the same function, so a recipe cannot be
// corrected on one side alone.
//
// Two recipes are deliberately not here, and each says why at its site: the superblock's,
// which is seeded from `!0` rather than through this seam and so lives with the record's
// layout in `ondisk::superblock`; and a hash-tree index block's, where the writer folds a
// tail it wrote and the reader folds the tail it found, which is a real difference and not a
// transcription.

/// The seed every metadata object belonging to one inode continues from: the filesystem seed
/// folded with the inode's number and its generation.
///
/// An extent node's tail, a directory block's tail, and an orphan block's all chain from
/// this, which is what makes a block moved between two inodes fail its checksum rather than
/// verify under its new owner.
pub(crate) fn inode_seed(csum: &dyn Checksummer, ino: u32, generation: u32) -> u32 {
    let c = csum.crc32c(csum.base_seed(), &ino.to_le_bytes());
    csum.crc32c(c, &generation.to_le_bytes())
}

/// The 16-bit crc32c a group descriptor carries in `bg_checksum`: the filesystem seed folded
/// with the group number, then the descriptor's own bytes.
///
/// `bytes` is the descriptor as it sits on disk *with `bg_checksum` zeroed* — the field
/// participates in its own checksum as two zero bytes, and every other byte participates as
/// it is, including any this crate does not model.
pub(crate) fn group_descriptor(csum: &dyn Checksummer, group: u32, bytes: &[u8]) -> u16 {
    let c = csum.crc32c(csum.base_seed(), &group.to_le_bytes());
    (csum.crc32c(c, bytes) & 0xffff) as u16
}

/// The crc16 a group descriptor carries in `bg_checksum` under `uninit_bg`, the scheme
/// `metadata_csum` supersedes: over the filesystem's UUID, the group number, and the
/// descriptor's own bytes with `bg_checksum` left out.
///
/// Documented: `uninit_bg` checksums a descriptor with a crc16 over the UUID, the group
/// number, and the descriptor. Observed on every descriptor the pinned `mke2fs` 1.47.0 wrote
/// under `uninit_bg`, in the 32-byte and the 64-byte form: the CRC-16 whose reflected
/// polynomial is `0xA001`, started at `0xFFFF`, with the two checksum bytes skipped rather
/// than zeroed and the group number four bytes little-endian.
pub(crate) fn group_descriptor_crc16(uuid: &[u8; 16], group: u32, desc: &[u8]) -> u16 {
    let field = crate::ondisk::GroupDescriptor::CHECKSUM_OFFSET;
    let after = desc.get(field + 2..).unwrap_or_default();
    [
        uuid.as_slice(),
        &group.to_le_bytes(),
        &desc[..field.min(desc.len())],
        after,
    ]
    .iter()
    .flat_map(|part| part.iter())
    .fold(0xFFFF_u16, |crc, &byte| {
        (0..8).fold(crc ^ u16::from(byte), |c, _| {
            if c & 1 == 0 {
                c >> 1
            } else {
                (c >> 1) ^ 0xA001
            }
        })
    })
}

/// The crc32c an inode carries: the filesystem seed folded with the inode's number and
/// generation, then the inode's own bytes with its checksum fields zeroed.
///
/// `has_hi` is whether the inode is large enough for `i_checksum_hi`. Without it the result
/// is sixteen bits wide, because there is no high half stored to compare a full-width value
/// against (the ext4 documentation's Checksums page). `mke2fs` leaves the reserved inodes in
/// exactly that state, so on any filesystem it formatted, checking them at full width rejects
/// seven healthy inodes.
pub(crate) fn inode(
    csum: &dyn Checksummer,
    number: u32,
    generation: u32,
    bytes: &[u8],
    has_hi: bool,
) -> u32 {
    let c = csum.crc32c(inode_seed(csum, number, generation), bytes);
    if has_hi { c } else { c & 0xffff }
}

/// The crc32c a multiple-mount protection block carries: the filesystem seed folded with every
/// byte of the block's record before the checksum's own word (observed on the pinned `mke2fs`,
/// whose blocks carry exactly this).
pub(crate) fn mmp_block(csum: &dyn Checksummer, record: &[u8]) -> u32 {
    csum.crc32c(
        csum.base_seed(),
        &record[..crate::ondisk::MMP_CHECKSUM_OFFSET],
    )
}

/// The crc32c a block or inode bitmap carries: the filesystem seed folded with the bytes the
/// kernel counts as covered.
///
/// How many bytes those are is [`block_bitmap_len`] and [`inode_bitmap_len`]; the two differ,
/// and getting either wrong produces a checksum no checker accepts.
pub(crate) fn bitmap(csum: &dyn Checksummer, covered: &[u8]) -> u32 {
    csum.crc32c(csum.base_seed(), covered)
}

/// The bytes of a block bitmap its checksum covers: the whole bitmap (the ext4 documentation's
/// Checksums page), one bit per block. A group's block count is a multiple of eight on every
/// filesystem the planner or `mke2fs` writes, so that is exactly `blocks_per_group / 8` bytes.
pub(crate) const fn block_bitmap_len(blocks_per_group: u32) -> usize {
    (blocks_per_group / 8) as usize
}

/// The bytes of an inode bitmap its checksum covers: one bit per inode, **rounded up**, so a
/// count that is not a multiple of eight still has its final partial byte covered.
///
/// The planner and `mke2fs` both round the inode count down to a multiple of eight, so the
/// rounding decides nothing on any image either writes, and the pinned tools' checksum of
/// each inode bitmap is the one this computes (the full-dump differential). Rounding up is
/// this crate's choice for a count that is not a multiple of eight: it covers every bit the
/// bitmap holds.
pub(crate) const fn inode_bitmap_len(inodes_per_group: u32) -> usize {
    inodes_per_group.div_ceil(8) as usize
}

/// The crc32c an orphan-file block's tail carries: the file's identity, then the block's own
/// number, then its entry array.
///
/// The block number is in the chain because the file is an array of identical zeroed entry
/// blocks — without it every block of a fresh orphan file would carry the same checksum, and
/// one copied over another would verify.
pub(crate) fn orphan_block(
    csum: &dyn Checksummer,
    ino: u32,
    generation: u32,
    block: u64,
    entries: &[u8],
) -> u32 {
    let c = csum.crc32c(inode_seed(csum, ino, generation), &block.to_le_bytes());
    csum.crc32c(c, entries)
}

/// The crc32c an external attribute block carries in `h_checksum`: the filesystem seed folded
/// with the block number as a little-endian 64-bit value, then the whole block.
///
/// `bytes` is the block as it sits on disk *with `h_checksum` zeroed*. The block number rather
/// than the owning inode is what identifies it, because one attribute block may be shared by
/// several inodes.
pub(crate) fn xattr_block(csum: &dyn Checksummer, block: u64, bytes: &[u8]) -> u32 {
    let c = csum.crc32c(csum.base_seed(), &block.to_le_bytes());
    csum.crc32c(c, bytes)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn a_scheme_answers_the_two_questions_separately() {
        // The two questions agree under both schemes this crate writes; they are asked
        // separately because a third scheme — the crc16 `uninit_bg` group-descriptor
        // checksum, which a foreign image may carry — answers them differently, and a
        // single flag would have no way to say so.
        assert!(!CsumScheme::None.writes_object_checksums());
        assert!(!CsumScheme::None.uninit_bg_semantics());
        assert!(CsumScheme::Crc32c.writes_object_checksums());
        assert!(CsumScheme::Crc32c.uninit_bg_semantics());
        // A filesystem with no checksums is the default: a scheme is something a feature
        // set turns on.
        assert_eq!(CsumScheme::default(), CsumScheme::None);
    }

    #[test]
    fn null_csum_is_disabled_and_zero() {
        let c = NullCsum;
        assert_eq!(c.scheme(), CsumScheme::None);
        assert_eq!(c.base_seed(), 0);
        assert_eq!(c.crc32c(0, b"anything"), 0);
        assert_eq!(c.crc32c(0xdead_beef, &[1, 2, 3, 4]), 0);
    }

    #[test]
    fn null_csum_is_usable_as_a_trait_object() {
        // The seam is consumed dynamically by the materializer; make sure it is
        // object-safe so the construction site can hold `&dyn Checksummer`.
        let c: &dyn Checksummer = &NullCsum;
        assert_eq!(c.scheme(), CsumScheme::None);
        assert_eq!(c.crc32c(1, b""), 0);
    }

    #[test]
    fn crc32c_seeds_from_the_uuid() {
        // The base seed is crc32c(!0, uuid). This UUID is the one the host-tool
        // baseline uses, and the seed matches what e2fsprogs derives for it.
        let uuid = [
            0xf0, 0xe1, 0x70, 0x55, 0, 0, 0x40, 0, 0x80, 0, 0, 0, 0, 0, 0, 0,
        ];
        let c = Crc32c::new(&uuid);
        assert_eq!(c.scheme(), CsumScheme::Crc32c);
        assert_eq!(c.base_seed(), 0x33D2_8425);
        // The primitive is the raw continuation, so an empty feed returns the seed.
        assert_eq!(c.crc32c(c.base_seed(), b""), 0x33D2_8425);
    }

    #[test]
    fn crc32c_is_usable_as_a_trait_object() {
        let uuid = [0u8; 16];
        let c: &dyn Checksummer = &Crc32c::new(&uuid);
        assert_eq!(c.scheme(), CsumScheme::Crc32c);
    }

    #[test]
    fn a_recipe_binds_an_object_to_the_identity_it_was_written_under() {
        // The property every chain above exists for, checked on the two that carry the most
        // identity: the same bytes under a different owner, generation, group, or block are a
        // different checksum. Without it a metadata block moved or copied inside an image
        // would verify in its new place.
        let c = Crc32c::new(&[0u8; 16]);
        let bytes = b"the object's own bytes";

        assert_ne!(inode_seed(&c, 12, 7), inode_seed(&c, 13, 7));
        assert_ne!(inode_seed(&c, 12, 7), inode_seed(&c, 12, 8));
        assert_ne!(
            orphan_block(&c, 12, 7, 100, bytes),
            orphan_block(&c, 12, 7, 101, bytes)
        );
        assert_ne!(
            group_descriptor(&c, 0, bytes),
            group_descriptor(&c, 1, bytes)
        );
        assert_ne!(xattr_block(&c, 100, bytes), xattr_block(&c, 101, bytes));

        // An inode without the high half of its checksum field answers sixteen bits wide,
        // because there is no high half stored to compare a wider value against.
        assert_eq!(inode(&c, 12, 7, bytes, false) >> 16, 0);
        assert_eq!(
            inode(&c, 12, 7, bytes, false),
            inode(&c, 12, 7, bytes, true) & 0xffff
        );

        // With checksums off every recipe answers zero, because the primitive does.
        let off = NullCsum;
        assert_eq!(inode(&off, 12, 7, bytes, true), 0);
        assert_eq!(group_descriptor(&off, 0, bytes), 0);
        assert_eq!(orphan_block(&off, 12, 7, 100, bytes), 0);
    }

    #[test]
    fn a_block_bitmap_is_covered_whole_and_an_inode_bitmap_rounded_up() {
        // The block bitmap divides exactly; the inode bitmap rounds up, so a count that is
        // not a multiple of eight still has its final partial byte covered.
        assert_eq!(block_bitmap_len(32_768), 4096);
        assert_eq!(inode_bitmap_len(8192), 1024);
        assert_eq!(inode_bitmap_len(8185), 1024);
        assert_eq!(inode_bitmap_len(8193), 1025);
    }
}