Skip to main content

resident_fat/
fs.rs

1//! Mounting a volume, and what you get when you have.
2
3use alloc::collections::BTreeMap;
4use alloc::string::ToString;
5use alloc::vec;
6use alloc::vec::Vec;
7
8use crate::blockdev::{BLOCK_SIZE, BlockDevice};
9use crate::boot::{BootSector, FsInfo};
10use crate::codepage::Codepage;
11use crate::dir::{Directory, ENTRY_SIZE};
12use crate::error::{Error, FatError, Result};
13use crate::fat::{Fat, Run};
14
15/// How many slots one 512-byte block holds.
16const SLOTS_PER_BLOCK: u32 = (BLOCK_SIZE / ENTRY_SIZE) as u32;
17
18/// The most clusters a directory is grown by while looking for room for one
19/// name.
20///
21/// Two would do. A name needs at most 21 slots — twenty long-name slots and
22/// the 8.3 entry — and the smallest cluster a volume can have is one 512-byte
23/// sector, holding 16; slot numbering runs continuously across a directory's
24/// chain, so two such clusters always yield a free run of 32. Four is slack
25/// over that, not a second calculation.
26///
27/// The bound exists so that a directory whose chain does not behave as
28/// expected fails rather than growing until the volume is full. Reaching it
29/// means something is wrong with the directory, not that the name was
30/// unusually long.
31const MAX_DIRECTORY_GROWTH: u32 = 4;
32
33/// A mounted FAT32 volume.
34///
35/// Owns its block device. Methods take `&mut self` and there is no interior
36/// mutability: a consumer that needs to share a volume picks its own
37/// strategy — a mutex, a worker on another core, or sole ownership — rather
38/// than paying for one this crate guessed at.
39pub struct FileSystem<D: BlockDevice> {
40    device: D,
41    boot: BootSector,
42    fs_info: FsInfo,
43    fat: Fat,
44    first_block: u64,
45    /// Parsed directories, keyed by first cluster.
46    ///
47    /// Never evicted. A directory costs a few tens of kilobytes parsed and
48    /// a volume holds a handful that anything actually walks, so a cache
49    /// policy would be machinery guarding against a problem this crate's
50    /// premise says does not arise. If that stops being true, eviction
51    /// belongs here and nowhere else.
52    directories: BTreeMap<u32, Directory>,
53    /// How many times each directory slot has been freed or repointed, by
54    /// directory first cluster and slot index. A slot never touched has
55    /// generation zero and no entry.
56    ///
57    /// A [`File`](crate::File) handle records the generation of its own
58    /// 8.3 slot when it is made, and is refused once that has moved. That is
59    /// what makes a handle held across a deletion detectable at all:
60    /// deleting frees the slot, the next file created takes it, and the
61    /// eleven name bytes the handle also checks are no help when the name is
62    /// the same — which is exactly what replacing a file does. The slot's
63    /// generation moved when it was freed, so the old handle no longer
64    /// matches, whatever now occupies it.
65    ///
66    /// Per slot rather than per directory, so deleting a file leaves handles
67    /// to its *siblings* alone. A per-directory count also caught
68    /// replacement, but staled every other handle in the directory with it:
69    /// a program holding a file open while deleting beside it — a game
70    /// keeping its data file open while it replaces saves in the same
71    /// directory — failed every read after the first deletion.
72    ///
73    /// Never pruned: forgetting a generation would make the handles it was
74    /// guarding valid again. It holds one entry per slot ever freed, which
75    /// is bounded by the directories' own size, since a slot that is reused
76    /// and freed again moves its existing entry rather than adding one.
77    generations: BTreeMap<(u32, u32), u32>,
78    /// How 8.3 names are read and written. See [`crate::codepage`].
79    codepage: Codepage,
80    /// Where the timestamps on new entries come from. See
81    /// [`crate::time::Clock`].
82    ///
83    /// Boxed rather than a type parameter on `FileSystem`, which would
84    /// spread through every signature that mentions a volume for the sake of
85    /// one call per file created — and boxed rather than a bare function
86    /// pointer, because a clock reasonably owns something: an offset, a
87    /// peripheral handle, a fixed value a test wants to control.
88    /// [`crate::time::FnClock`] covers the stateless case.
89    clock: alloc::boxed::Box<dyn crate::time::Clock>,
90    /// Whether this mount has set the volume's dirty flag.
91    ///
92    /// Also the record of whether anything has been written at all, which is
93    /// what lets a sync with nothing to do cost nothing.
94    marked_dirty: bool,
95    /// The runs of chains recently read through
96    /// [`read_at`](Self::read_at), by first cluster.
97    ///
98    /// Walking a chain is a pass over its every table entry, and `read_at`
99    /// needs the runs on every call, however small: without this, a
100    /// program reading a large file a kilobyte at a time — a game reading
101    /// lumps out of its data file — spends most of each read walking the
102    /// same chain again.
103    run_cache: RunCache,
104}
105
106/// See [`FileSystem::run_cache`].
107///
108/// Valid only while the table is unchanged since `changes` was taken from
109/// [`Fat::changes`]: every write to the table goes through one method that
110/// counts it, so a cache that sees the count move throws everything away
111/// rather than working out which chains a write touched.
112#[derive(Default)]
113struct RunCache {
114    changes: u64,
115    chains: BTreeMap<u32, Vec<Run>>,
116}
117
118/// The most chains [`RunCache`] holds. It is cleared outright when full:
119/// the reads it serves come from a handful of open files, and a volume
120/// read across more than this many files at once loses only the caching.
121const RUN_CACHE_CHAINS: usize = 16;
122
123impl<D: BlockDevice + core::fmt::Debug> core::fmt::Debug for FileSystem<D> {
124    /// Written out rather than derived, because a clock is a trait object
125    /// and requiring every implementation of [`Clock`](crate::time::Clock)
126    /// to be `Debug` would be a tax on implementors for the sake of one line
127    /// of output. The parsed directories are summarised rather than printed:
128    /// a volume that has walked a ROM directory would otherwise put three
129    /// hundred entries into the first panic message that mentions it.
130    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
131        f.debug_struct("FileSystem")
132            .field("device", &self.device)
133            .field("first_block", &self.first_block)
134            .field("clusters", &self.fat.cluster_count())
135            .field("cached_directories", &self.directories.len())
136            .field("marked_dirty", &self.marked_dirty)
137            .finish_non_exhaustive()
138    }
139}
140
141impl<D: BlockDevice> FileSystem<D> {
142    /// Mounts the volume that begins at block 0 of `device`.
143    ///
144    /// Right for a device formatted as one volume, which is what a card
145    /// written by `mkfs.vfat` onto a raw device is.
146    ///
147    /// A card with a partition table — anything an imaging tool wrote —
148    /// needs one of the other two ways in: `mount_partition`, behind the
149    /// `mbr` feature, which finds the volume itself; or
150    /// [`mount_at`](Self::mount_at) with a block number the caller already
151    /// knows.
152    ///
153    /// (`mount_partition` is named rather than linked because a link to it
154    /// does not resolve when the `mbr` feature is off, which would make
155    /// `cargo doc` warn in every build that does not enable it.)
156    pub fn mount(device: D) -> Result<Self, D::Error> {
157        Self::mount_at(device, 0)
158    }
159
160    /// Mounts the volume that begins at `first_block`.
161    ///
162    /// Every block number the volume uses is relative to this, so a
163    /// partitioned card works by passing the partition's first block.
164    pub fn mount_at(device: D, first_block: u64) -> Result<Self, D::Error> {
165        Self::mount_with(device, first_block, Codepage::ASCII)
166    }
167
168    /// Mounts with a codepage for the volume's 8.3 names.
169    ///
170    /// Only worth supplying for a card whose short names really are not
171    /// ASCII — see [`crate::codepage`]. It changes how a name is rendered
172    /// and which characters can be stored in an alias; it does not change
173    /// the bytes on the volume, and it does not affect long names, which are
174    /// UCS-2 and need no codepage at all.
175    ///
176    /// Set here and not afterwards, and read back with
177    /// [`codepage`](Self::codepage). There is no setter on purpose: the 8.3
178    /// name a directory was parsed under is the key it is cached by, so
179    /// changing the codepage under a mounted volume would leave entries
180    /// findable only by the name they were read as. Mount again to change
181    /// it.
182    pub fn mount_with(device: D, first_block: u64, codepage: Codepage) -> Result<Self, D::Error> {
183        Self::mount_within(device, first_block, codepage, None)
184    }
185
186    /// The mount every other one is built on.
187    ///
188    /// `limit` is how many blocks the volume is allowed to occupy from
189    /// `first_block`, when something already knows — a partition table entry
190    /// says so, and a volume claiming more sectors than the partition
191    /// holding it is as wrong as one claiming more than the device.
192    fn mount_within(
193        mut device: D,
194        first_block: u64,
195        codepage: Codepage,
196        limit: Option<u64>,
197    ) -> Result<Self, D::Error> {
198        let mut block = [0u8; BLOCK_SIZE];
199        device
200            .read(first_block, &mut block)
201            .map_err(Error::device)?;
202
203        let boot = BootSector::parse(&block)?;
204
205        // The volume must fit inside whatever contains it. Believing a boot
206        // sector that claims more is how a read runs off the end later,
207        // somewhere less obviously connected to the cause.
208        //
209        // Two bounds, and the tighter one wins: the device's own size, which
210        // it may decline to report — see `BlockDevice::block_count`, where
211        // `None` is an answer rather than a failure — and the partition's,
212        // when the caller came in through a partition table. With neither,
213        // the check is skipped.
214        let device_blocks = device.block_count().map_err(Error::device)?;
215        let bound = match (device_blocks, limit.map(|blocks| first_block + blocks)) {
216            (Some(device_end), Some(partition_end)) => Some(device_end.min(partition_end)),
217            (device_end, partition_end) => device_end.or(partition_end),
218        };
219        if let Some(bound) = bound {
220            let volume_blocks = u64::from(boot.total_sectors) * u64::from(boot.bytes_per_sector)
221                / BLOCK_SIZE as u64;
222            let end = first_block + volume_blocks;
223            if end > bound {
224                // Its own variant, and not `DataBeyondVolume`: that one is
225                // the boot sector's fields contradicting each other, and its
226                // two numbers say nothing about the bound that was actually
227                // exceeded here.
228                return Err(crate::error::BootError::BadGeometry(
229                    crate::error::Geometry::VolumeTooLarge {
230                        first_block,
231                        end,
232                        bound,
233                    },
234                )
235                .into());
236            }
237        }
238
239        let fs_info = match boot.fs_info_sector {
240            Some(sector) => {
241                device
242                    .read(first_block + u64::from(sector), &mut block)
243                    .map_err(Error::device)?;
244                FsInfo::parse(&block, &boot)
245            }
246            None => FsInfo::default(),
247        };
248
249        let fat = Fat::load(&mut RelativeDevice::new(&mut device, first_block), &boot)?;
250
251        Ok(FileSystem {
252            device,
253            boot,
254            fs_info,
255            fat,
256            first_block,
257            directories: BTreeMap::new(),
258            generations: BTreeMap::new(),
259            codepage,
260            clock: alloc::boxed::Box::new(crate::time::EpochClock),
261            marked_dirty: false,
262            run_cache: RunCache::default(),
263        })
264    }
265
266    /// The codepage 8.3 names are read and written through.
267    pub fn codepage(&self) -> &Codepage {
268        &self.codepage
269    }
270
271    /// Supplies the clock new entries are stamped from.
272    ///
273    /// Optional. Without one, everything written carries the FAT epoch,
274    /// which is a real date and is the right answer for a board that does
275    /// not know the time — see [`crate::time::Clock`] for why that is the
276    /// default rather than a failure.
277    ///
278    /// Affects only what is written afterwards. Entries already on the
279    /// volume keep the timestamps they were given, and this does not go back
280    /// and correct them: a device that learns the time from the network
281    /// halfway through its life has files from both eras, and inventing a
282    /// timestamp for the older ones would be worse than leaving them honest.
283    pub fn set_clock(&mut self, clock: alloc::boxed::Box<dyn crate::time::Clock>) {
284        self.clock = clock;
285    }
286
287    /// What the clock says, for stamping an entry.
288    pub(crate) fn now(&self) -> crate::time::DateTime {
289        self.clock.now()
290    }
291
292    /// Mounts the volume in partition-table slot `index`.
293    ///
294    /// The third of the three ways in, and the one for a card written by an
295    /// imaging tool: it reads the master boot record and mounts the
296    /// partition that slot describes. `index` is the raw table slot, 0 to 3,
297    /// rather than a count of the partitions in use — a card whose volume
298    /// sits in slot 1 with slot 0 empty is a real arrangement, and numbering
299    /// by use would silently mount the wrong one.
300    ///
301    /// [`crate::mbr::PartitionTable`] is public for the cases this does not cover:
302    /// finding the FAT partition when its slot is not known, or handling a
303    /// device that might have no table at all.
304    ///
305    /// The volume is held to the partition's length as well as the device's,
306    /// so a boot sector claiming more sectors than the partition it sits in
307    /// is refused here even on a device that cannot report its own size.
308    ///
309    /// # Errors
310    ///
311    /// [`Error::NoPartitionTable`] when block 0 is not a partition table —
312    /// including when it is a boot sector, which is the shape [`mount`]
313    /// handles. [`Error::NoSuchPartition`] when the slot is empty or out of
314    /// range.
315    ///
316    /// [`mount`]: Self::mount
317    #[cfg(feature = "mbr")]
318    #[cfg_attr(docsrs, doc(cfg(feature = "mbr")))]
319    pub fn mount_partition(mut device: D, index: usize) -> Result<Self, D::Error> {
320        let table =
321            crate::mbr::PartitionTable::read(&mut device)?.ok_or(Error::NoPartitionTable)?;
322        let partition = *table.get(index).ok_or(Error::NoSuchPartition { index })?;
323        if partition.is_protective_gpt() {
324            return Err(Error::NoPartitionTable);
325        }
326        Self::mount_within(
327            device,
328            partition.first_block,
329            Codepage::ASCII,
330            Some(partition.blocks),
331        )
332    }
333
334    /// Mounts the device's FAT volume, whichever way it was formatted.
335    ///
336    /// For a card whose layout is not known in advance, which is most of
337    /// them. With a partition table, this mounts the first partition whose
338    /// type byte says FAT — by type rather than by slot, because imaging
339    /// tools usually put the volume in slot 0 but not always, and a card
340    /// with a separate data partition has more than one entry. Like
341    /// [`mount_partition`], the volume is held to that partition's length.
342    /// With no table, the device is one bare volume, as some tools format a
343    /// small card, and this is [`mount`].
344    ///
345    /// Telling the two apart is the part worth not writing by hand: a boot
346    /// sector and a partition table end with the same `0x55AA`, so the
347    /// obvious check answers yes to either — see
348    /// [`crate::mbr::PartitionTable::read`].
349    ///
350    /// # Errors
351    ///
352    /// [`Error::NoFatPartition`] when there is a table and nothing in it is
353    /// FAT. [`Error::NoPartitionTable`] for the placeholder table a GPT disk
354    /// carries, which this declines as [`mount_partition`] does. Otherwise
355    /// whatever mounting the volume found.
356    ///
357    /// [`mount`]: Self::mount
358    /// [`mount_partition`]: Self::mount_partition
359    #[cfg(feature = "mbr")]
360    #[cfg_attr(docsrs, doc(cfg(feature = "mbr")))]
361    pub fn mount_first_fat(mut device: D) -> Result<Self, D::Error> {
362        let Some(table) = crate::mbr::PartitionTable::read(&mut device)? else {
363            return Self::mount(device);
364        };
365        if table.iter().any(|partition| partition.is_protective_gpt()) {
366            return Err(Error::NoPartitionTable);
367        }
368        let partition = *table.first_fat().ok_or(Error::NoFatPartition)?;
369        Self::mount_within(
370            device,
371            partition.first_block,
372            Codepage::ASCII,
373            Some(partition.blocks),
374        )
375    }
376
377    /// The device block the volume begins at: 0 for a bare volume, the
378    /// partition's first block for one mounted through a table.
379    ///
380    /// For a board's console line about what it mounted, which is where a
381    /// card imaged differently from the last one first shows.
382    pub fn first_block(&self) -> u64 {
383        self.first_block
384    }
385
386    /// The volume's validated geometry.
387    pub fn boot_sector(&self) -> &BootSector {
388        &self.boot
389    }
390
391    /// The volume's free-space hints, such as they are.
392    pub fn fs_info(&self) -> &FsInfo {
393        &self.fs_info
394    }
395
396    /// The resident allocation table.
397    pub fn fat(&self) -> &Fat {
398        &self.fat
399    }
400
401    /// The resident allocation table, mutably.
402    ///
403    /// Allocating or freeing through this changes what the volume records
404    /// as in use without changing any directory entry, so the two can be
405    /// made to disagree. It exists because the file operations in
406    /// [`crate::file`] need it; reach for those instead.
407    pub(crate) fn fat_mut(&mut self) -> &mut Fat {
408        &mut self.fat
409    }
410
411    /// Whether the volume was already marked dirty when this mount found
412    /// it.
413    ///
414    /// True means the last writer did not finish: either it never synced, or
415    /// it lost power partway through. It says nothing about what is wrong,
416    /// only that something might be — under this crate's write ordering the
417    /// likely damage is leaked clusters, which cost space and nothing else,
418    /// but the volume may equally have been written by something with weaker
419    /// ordering.
420    ///
421    /// This reports what was on the volume at mount, and does not change
422    /// when this mount sets the flag for its own writes.
423    pub fn is_dirty(&self) -> bool {
424        self.boot.dirty
425    }
426
427    /// Marks the volume as having a writer, unless it already is marked.
428    ///
429    /// Called from [`write_blocks`](Self::write_blocks) rather than from
430    /// each operation that mutates, so that it cannot be forgotten by
431    /// something added later — and so that it necessarily happens *before*
432    /// the write it is warning about, which is the only ordering that makes
433    /// the flag mean anything.
434    ///
435    /// It costs one read and one write, once, on the first change after a
436    /// mount or a sync. A volume that is only read is never written to,
437    /// which matters for a card that is physically or deliberately
438    /// read-only.
439    fn mark_dirty(&mut self) -> Result<(), D::Error> {
440        if self.marked_dirty {
441            return Ok(());
442        }
443        // Set before the write rather than after, so the flag is already on
444        // the volume if the caller's next write is the one interrupted.
445        self.marked_dirty = true;
446        self.set_dirty_flag(true).inspect_err(|_| {
447            // ...and put back if the flag never reached the volume, or
448            // every later write would skip this and go to a volume nothing
449            // had marked. The caller sees the failure either way; what this
450            // protects is the write after the one it retries.
451            self.marked_dirty = false;
452        })
453    }
454
455    /// Writes the volume state byte in the boot sector.
456    ///
457    /// Goes to the device directly rather than through
458    /// [`write_blocks`](Self::write_blocks), which would ask for the flag to
459    /// be set as a result of setting it.
460    fn set_dirty_flag(&mut self, dirty: bool) -> Result<(), D::Error> {
461        const STATE: usize = 0x41;
462        const STATE_DIRTY: u8 = 0x01;
463
464        let mut block = [0u8; BLOCK_SIZE];
465        self.device
466            .read(self.first_block, &mut block)
467            .map_err(Error::device)?;
468        if dirty {
469            block[STATE] |= STATE_DIRTY;
470        } else {
471            block[STATE] &= !STATE_DIRTY;
472        }
473        self.device
474            .write(self.first_block, &block)
475            .map_err(Error::device)
476    }
477
478    /// The runs the chain starting at `cluster` occupies.
479    ///
480    /// Reported through this volume's error type rather than the table's, so
481    /// a caller mixing it with reads and writes has one type to handle. Ask
482    /// [`fat`](Self::fat) directly for the narrower [`FatError`].
483    pub fn runs(&self, cluster: u32) -> Result<Vec<Run>, D::Error> {
484        Ok(self.fat.runs(cluster)?)
485    }
486
487    /// The runs of the chain starting at `cluster`, from the cache if they
488    /// are there and the table hasn't changed since, walked otherwise.
489    ///
490    /// Taken out of the cache rather than borrowed from it, so the caller
491    /// can go on to read through `self`; hand them back with
492    /// [`keep_runs`](Self::keep_runs) to keep them cached.
493    pub(crate) fn take_runs(&mut self, cluster: u32) -> Result<Vec<Run>, D::Error> {
494        if self.run_cache.changes != self.fat.changes() {
495            self.run_cache.chains.clear();
496            self.run_cache.changes = self.fat.changes();
497        }
498        match self.run_cache.chains.remove(&cluster) {
499            Some(runs) => Ok(runs),
500            None => self.runs(cluster),
501        }
502    }
503
504    /// Returns runs from [`take_runs`](Self::take_runs) to the cache —
505    /// unless the table changed in the meantime, when they may be wrong.
506    pub(crate) fn keep_runs(&mut self, cluster: u32, runs: Vec<Run>) {
507        if self.run_cache.changes != self.fat.changes() {
508            return;
509        }
510        if self.run_cache.chains.len() >= RUN_CACHE_CHAINS {
511            self.run_cache.chains.clear();
512        }
513        self.run_cache.chains.insert(cluster, runs);
514    }
515
516    /// Reads a run's clusters into `into`, in one device transfer.
517    ///
518    /// `into` must be exactly the run's length in bytes; anything else is
519    /// [`Error::BufferLength`]. One call per run is the property everything
520    /// else is arranged to make possible, so this deliberately offers no way
521    /// to read a run piecemeal.
522    ///
523    /// Both ends of the run are checked against the volume, not just the
524    /// first. [`Run`]'s fields are public, so a run a caller assembled — as
525    /// opposed to one [`runs`](Self::runs) returned — can start inside the
526    /// volume and end outside it, and the transfer would then continue off
527    /// the end of the data area into whatever follows it. On a partitioned
528    /// card that is another filesystem.
529    pub fn read_run(&mut self, run: &Run, into: &mut [u8]) -> Result<(), D::Error> {
530        // The run is checked before the buffer, and that order is the useful
531        // one: the buffer has to be exactly the run's length, so validating
532        // it first would oblige a caller holding a nonsensical run to
533        // allocate a buffer to match it before being told the run is
534        // nonsense. A run of `u32::MAX` clusters would ask for terabytes.
535        if run.clusters != 0 {
536            if !self.fat.is_valid_cluster(run.start_cluster) {
537                return Err(FatError::BadCluster {
538                    cluster: run.start_cluster,
539                }
540                .into());
541            }
542            // In `u64`, because a run long enough to wrap `u32` is exactly
543            // the shape being rejected and must not wrap into a
544            // valid-looking one.
545            let last = u64::from(run.start_cluster) + u64::from(run.clusters) - 1;
546            let reported = last.min(u64::from(u32::MAX)) as u32;
547            if last > u64::from(u32::MAX) || !self.fat.is_valid_cluster(reported) {
548                return Err(FatError::BadCluster { cluster: reported }.into());
549            }
550        }
551
552        let expected = run.bytes(self.boot.cluster_bytes());
553        if into.len() as u64 != expected {
554            return Err(Error::BufferLength {
555                expected,
556                actual: into.len(),
557            });
558        }
559        if run.clusters == 0 {
560            // Nothing to transfer. Returned here rather than falling through,
561            // because the device would otherwise be handed a zero-length
562            // read — which the trait does not describe and drivers need not
563            // accept.
564            return Ok(());
565        }
566
567        let sector = self.boot.cluster_sector(run.start_cluster);
568        self.read_blocks(u64::from(sector), into)
569    }
570
571    /// Reads consecutive volume-relative blocks into `into`.
572    ///
573    /// One device call, unless the device says it cannot move that many
574    /// blocks at once — see
575    /// [`max_transfer_blocks`](BlockDevice::max_transfer_blocks). Splitting
576    /// here rather than inside the device keeps the transfer count
577    /// something a test can see.
578    pub(crate) fn read_blocks(&mut self, block: u64, into: &mut [u8]) -> Result<(), D::Error> {
579        let blocks = into.len() / BLOCK_SIZE;
580        let cap = usize::try_from(self.device.max_transfer_blocks())
581            .unwrap_or(usize::MAX)
582            .max(1);
583
584        if blocks <= cap {
585            return self
586                .device
587                .read(self.first_block + block, into)
588                .map_err(Error::device);
589        }
590
591        // Past this point `cap < blocks`, so the multiplication below
592        // cannot overflow however large a limit the device reported.
593        debug_assert!(cap < blocks);
594
595        for (batch, chunk) in into.chunks_mut(cap * BLOCK_SIZE).enumerate() {
596            self.device
597                .read(self.first_block + block + (batch * cap) as u64, chunk)
598                .map_err(Error::device)?;
599        }
600        Ok(())
601    }
602
603    /// Reads the whole chain beginning at `cluster`, one transfer per run.
604    ///
605    /// Returns every byte of every cluster, so the caller truncates to the
606    /// file's recorded size — the chain knows how much space a file
607    /// occupies, not how much of it is meaningful.
608    ///
609    /// The buffer is as large as the chain, and the chain's length comes off
610    /// the volume, so this reports [`Error::OutOfMemory`] rather than
611    /// aborting when it will not fit — see that variant. A corrupt chain can
612    /// be as long as the volume has clusters.
613    pub fn read_chain(&mut self, cluster: u32) -> Result<Vec<u8>, D::Error> {
614        let runs = self.runs(cluster)?;
615        let cluster_bytes = self.boot.cluster_bytes();
616        let total: u64 = runs.iter().map(|run| run.bytes(cluster_bytes)).sum();
617
618        let mut data = crate::error::try_filled(0u8, total)?;
619        let mut at = 0usize;
620        for run in &runs {
621            let length = run.bytes(cluster_bytes) as usize;
622            self.read_run(run, &mut data[at..at + length])?;
623            at += length;
624        }
625        Ok(data)
626    }
627
628    /// The first cluster of the root directory.
629    pub fn root_cluster(&self) -> u32 {
630        self.boot.root_cluster
631    }
632
633    /// The directory whose chain begins at `cluster`, reading and parsing
634    /// it if this is the first time it has been asked for.
635    ///
636    /// One transfer per run of the directory's chain on the first call, and
637    /// **no device traffic at all** afterwards. That second property is
638    /// what makes opening several files in one directory cheap, and it is
639    /// the thing a per-block implementation cannot offer however good its
640    /// caching is.
641    pub fn read_dir(&mut self, cluster: u32) -> Result<&Directory, D::Error> {
642        if !self.directories.contains_key(&cluster) {
643            let data = self.read_chain(cluster)?;
644            let parsed = Directory::parse(&data, &self.codepage)?;
645            self.directories.insert(cluster, parsed);
646        }
647        Ok(&self.directories[&cluster])
648    }
649
650    /// The root directory.
651    pub fn root_dir(&mut self) -> Result<&Directory, D::Error> {
652        self.read_dir(self.boot.root_cluster)
653    }
654
655    /// The directory at `path`, which is `/`-separated and may name either
656    /// long or short names.
657    ///
658    /// A leading slash is optional and `.` components are skipped, so
659    /// `/ROMS`, `ROMS` and `./ROMS` are the same directory.
660    pub fn open_dir(&mut self, path: &str) -> Result<&Directory, D::Error> {
661        let cluster = self.resolve_dir(path)?;
662        self.read_dir(cluster)
663    }
664
665    /// The first cluster of the directory at `path`.
666    ///
667    /// The half of [`open_dir`](Self::open_dir) that does not borrow the
668    /// cache, so a caller can go on to mutate the directory it found.
669    pub(crate) fn resolve_dir(&mut self, path: &str) -> Result<u32, D::Error> {
670        let mut cluster = self.boot.root_cluster;
671
672        for component in path.split('/') {
673            if component.is_empty() || component == "." {
674                continue;
675            }
676
677            // The cluster is copied out before the next iteration borrows
678            // the cache again, which is also where `..` needs care.
679            let next = {
680                let directory = self.read_dir(cluster)?;
681                let entry = directory.get(component).ok_or_else(|| Error::NotFound {
682                    name: component.to_string(),
683                })?;
684                if !entry.is_directory() {
685                    return Err(Error::NotADirectory {
686                        name: component.to_string(),
687                    });
688                }
689                entry.first_cluster()
690            };
691
692            // `..` in a child of the root holds 0 rather than the root's
693            // own cluster number. Following it literally would look up
694            // cluster 0, which is reserved.
695            cluster = if next == 0 {
696                self.boot.root_cluster
697            } else {
698                next
699            };
700        }
701
702        Ok(cluster)
703    }
704
705    /// Forgets every parsed directory.
706    ///
707    /// Only needed if something outside this crate has written to the
708    /// volume underneath it, which is not a supported arrangement — but
709    /// the alternative to offering this is a caller with a stale cache and
710    /// no way to say so.
711    pub fn forget_directories(&mut self) {
712        self.directories.clear();
713    }
714
715    /// Forgets one parsed directory, for when it has stopped existing.
716    pub(crate) fn forget_directory(&mut self, cluster: u32) {
717        self.directories.remove(&cluster);
718    }
719
720    /// Writes every change made since the last sync to the device.
721    ///
722    /// Each dirty stretch of the allocation table is written once per copy
723    /// the volume carries, and the free-space hints are refreshed. Until
724    /// this is called, allocations and truncations exist only in memory.
725    ///
726    /// Directory entries are *not* deferred — see the ordering notes on
727    /// [`create_with_size`](FileSystem::create_with_size) and
728    /// [`truncate`](FileSystem::truncate). They go to the device when they
729    /// are written, because their order relative to table changes is what
730    /// decides what a power cut leaves behind.
731    ///
732    /// # The dirty flag
733    ///
734    /// Finishing clears the volume's dirty flag, so a volume synced before
735    /// being put away mounts clean and one dropped without a sync does not.
736    /// That flag is the only way an unclean shutdown is detectable at all;
737    /// nothing else on the volume records that a writer was interrupted.
738    ///
739    /// Only the flag *this* mount set is cleared. A volume that arrived
740    /// dirty and was never written to keeps its warning: this crate has not
741    /// repaired anything, and clearing a flag it did not set would throw
742    /// away the one signal that something needs looking at.
743    ///
744    /// A sync with nothing to write does nothing at all, so calling it more
745    /// often than necessary costs nothing.
746    pub fn sync(&mut self) -> Result<(), D::Error> {
747        if !self.marked_dirty {
748            return Ok(());
749        }
750        self.flush_fat()?;
751        self.write_fs_info()?;
752        // Last, and only once everything it was warning about has landed.
753        self.marked_dirty = false;
754        self.set_dirty_flag(false)
755    }
756
757    /// Syncs, and gives the block device back.
758    ///
759    /// The tidy way to finish with a volume. `FileSystem` cannot do this
760    /// when it is dropped, because writing to a device can fail and a drop
761    /// has nowhere to report that to — so an unsynced volume that is simply
762    /// dropped stays marked dirty, which is the correct outcome rather than
763    /// a silent one.
764    pub fn unmount(mut self) -> Result<D, D::Error> {
765        self.sync()?;
766        Ok(self.device)
767    }
768
769    /// Writes the dirty stretches of the allocation table, to every copy.
770    ///
771    /// Called by the file operations at the point their ordering requires
772    /// it, not only by [`sync`](Self::sync) — and that is the whole reason
773    /// it is separate.
774    ///
775    /// Deferring table changes while writing directory entries straight
776    /// through would make the order they reach the *device* the reverse of
777    /// the order they happen in memory. An entry naming clusters the
778    /// on-disk table still shows as free is precisely the cross-link this
779    /// crate's ordering rules exist to prevent: the next allocation would
780    /// hand those clusters to another file.
781    ///
782    /// Batching still does its job, because this collapses everything one
783    /// operation touched into one write per stretch per copy. Linking a
784    /// thousand-cluster chain is a handful of sectors, not a thousand
785    /// writes.
786    pub(crate) fn flush_fat(&mut self) -> Result<(), D::Error> {
787        let runs = self.fat.dirty_runs();
788        if runs.is_empty() {
789            return Ok(());
790        }
791        let starts: Vec<u32> = self.fat.copy_starts().collect();
792        for (sector, count) in runs {
793            let bytes = self.fat.sector_bytes(sector, count);
794            for start in &starts {
795                self.write_blocks(u64::from(start + sector), &bytes)?;
796            }
797        }
798        self.fat.clear_dirty();
799        Ok(())
800    }
801
802    /// Refreshes the volume's free-space hints.
803    ///
804    /// Best effort by design: these are hints, and a reader that trusts
805    /// them over the table is wrong to. Writing them keeps other
806    /// implementations from rescanning, and nothing here depends on them.
807    fn write_fs_info(&mut self) -> Result<(), D::Error> {
808        let Some(sector) = self.boot.fs_info_sector else {
809            return Ok(());
810        };
811        let mut block = [0u8; BLOCK_SIZE];
812        self.read_blocks(u64::from(sector), &mut block)?;
813
814        const LEAD_SIGNATURE: u32 = 0x4161_5252;
815        const STRUCT_SIGNATURE: u32 = 0x6141_7272;
816        let lead = u32::from_le_bytes([block[0], block[1], block[2], block[3]]);
817        let structure =
818            u32::from_le_bytes([block[0x1E4], block[0x1E5], block[0x1E6], block[0x1E7]]);
819        if lead != LEAD_SIGNATURE || structure != STRUCT_SIGNATURE {
820            return Ok(());
821        }
822
823        block[0x1E8..0x1EC].copy_from_slice(&self.fat.free_clusters().to_le_bytes());
824        block[0x1EC..0x1F0].copy_from_slice(&self.fat.next_free_hint().to_le_bytes());
825        self.write_blocks(u64::from(sector), &block)?;
826
827        self.fs_info = FsInfo {
828            free_clusters: Some(self.fat.free_clusters()),
829            next_free: Some(self.fat.next_free_hint()),
830        };
831        Ok(())
832    }
833
834    /// Writes consecutive volume-relative blocks, splitting only where the
835    /// device says it must.
836    ///
837    /// Every change to the volume goes through here, which is why this is
838    /// where the dirty flag is set: no operation can forget to.
839    pub(crate) fn write_blocks(&mut self, block: u64, from: &[u8]) -> Result<(), D::Error> {
840        self.mark_dirty()?;
841
842        let blocks = from.len() / BLOCK_SIZE;
843        let cap = usize::try_from(self.device.max_transfer_blocks())
844            .unwrap_or(usize::MAX)
845            .max(1);
846
847        if blocks <= cap {
848            return self
849                .device
850                .write(self.first_block + block, from)
851                .map_err(Error::device);
852        }
853
854        debug_assert!(cap < blocks);
855        for (batch, chunk) in from.chunks(cap * BLOCK_SIZE).enumerate() {
856            self.device
857                .write(self.first_block + block + (batch * cap) as u64, chunk)
858                .map_err(Error::device)?;
859        }
860        Ok(())
861    }
862
863    /// The block holding directory entry `index` of the directory whose
864    /// chain begins at `cluster`, and the entry's offset within it.
865    pub(crate) fn entry_location(
866        &self,
867        cluster: u32,
868        index: u32,
869    ) -> Result<(u64, usize), D::Error> {
870        let block_in_dir = index / SLOTS_PER_BLOCK;
871        let offset = (index % SLOTS_PER_BLOCK) as usize * ENTRY_SIZE;
872
873        let sectors_per_cluster = u32::from(self.boot.sectors_per_cluster);
874        let cluster_index = block_in_dir / sectors_per_cluster;
875        let block_in_cluster = block_in_dir % sectors_per_cluster;
876
877        // Walk the runs rather than the chain: the same information, but
878        // already collapsed, so a directory spanning several clusters costs
879        // one lookup instead of a step per cluster.
880        let runs = self.fat.runs(cluster)?;
881        let mut seen = 0u32;
882        for run in &runs {
883            if cluster_index < seen + run.clusters {
884                let target = run.start_cluster + (cluster_index - seen);
885                let sector = self.boot.cluster_sector(target) + block_in_cluster;
886                return Ok((u64::from(sector), offset));
887            }
888            seen += run.clusters;
889        }
890        Err(Error::DirectoryFull)
891    }
892
893    /// One directory entry, as the device holds it.
894    ///
895    /// For an operation that has to carry fields this crate does not model
896    /// from one entry to another — a rename keeps a file's timestamps and
897    /// attributes exactly — rather than rebuild them from the parsed view.
898    pub(crate) fn read_entry(
899        &mut self,
900        directory: u32,
901        index: u32,
902    ) -> Result<[u8; ENTRY_SIZE], D::Error> {
903        let (block, offset) = self.entry_location(directory, index)?;
904        let mut buffer = [0u8; BLOCK_SIZE];
905        self.read_blocks(block, &mut buffer)?;
906        let mut entry = [0u8; ENTRY_SIZE];
907        entry.copy_from_slice(&buffer[offset..offset + ENTRY_SIZE]);
908        Ok(entry)
909    }
910
911    /// Makes every handle to slot `index` of `directory` stale, as deleting
912    /// it would.
913    ///
914    /// For a change that repoints an entry at other clusters without freeing
915    /// its slot: a handle to what the entry used to name would still pass
916    /// the name check, and write into clusters that are about to be freed.
917    pub(crate) fn invalidate_slot(&mut self, directory: u32, index: u32) {
918        *self.generations.entry((directory, index)).or_insert(0) += 1;
919    }
920
921    /// Reads, changes and writes back one directory entry.
922    ///
923    /// The whole block is rewritten because a block is the smallest thing a
924    /// device will accept — which is also why the read comes first.
925    pub(crate) fn edit_entry(
926        &mut self,
927        directory: u32,
928        index: u32,
929        edit: impl FnOnce(&mut [u8]),
930    ) -> Result<(), D::Error> {
931        let (block, offset) = self.entry_location(directory, index)?;
932        let mut buffer = [0u8; BLOCK_SIZE];
933        self.read_blocks(block, &mut buffer)?;
934        edit(&mut buffer[offset..offset + ENTRY_SIZE]);
935        self.write_blocks(block, &buffer)?;
936        self.directories.remove(&directory);
937        Ok(())
938    }
939
940    /// Writes a run of consecutive directory slots, starting at `index`.
941    ///
942    /// One read-modify-write per block the run covers, in ascending order —
943    /// which puts the run's *last* entry on the device last, and that is the
944    /// ordering the caller needs.
945    ///
946    /// A name's long-name slots come before the 8.3 entry that terminates
947    /// them, so writing in this order means an interruption leaves slots
948    /// with no entry after them. Every reader, this one included, treats
949    /// those as nothing at all; `fsck.vfat` calls them an orphaned long
950    /// name and offers to remove them. The other order would be worse than
951    /// untidy: an 8.3 entry written past a still-unwritten run sits after
952    /// the directory's end marker, where no reader will look for it.
953    pub(crate) fn write_entries(
954        &mut self,
955        directory: u32,
956        index: u32,
957        entries: &[[u8; ENTRY_SIZE]],
958    ) -> Result<(), D::Error> {
959        debug_assert!(!entries.is_empty());
960        let last = index + entries.len() as u32 - 1;
961        let mut buffer = [0u8; BLOCK_SIZE];
962
963        for block_in_dir in (index / SLOTS_PER_BLOCK)..=(last / SLOTS_PER_BLOCK) {
964            let (block, _) = self.entry_location(directory, block_in_dir * SLOTS_PER_BLOCK)?;
965            self.read_blocks(block, &mut buffer)?;
966            for slot in 0..SLOTS_PER_BLOCK {
967                let at = block_in_dir * SLOTS_PER_BLOCK + slot;
968                if at < index || at > last {
969                    continue;
970                }
971                let offset = slot as usize * ENTRY_SIZE;
972                buffer[offset..offset + ENTRY_SIZE]
973                    .copy_from_slice(&entries[(at - index) as usize]);
974            }
975            self.write_blocks(block, &buffer)?;
976        }
977
978        self.directories.remove(&directory);
979        Ok(())
980    }
981
982    /// Marks slots `first..=last` of `directory` deleted.
983    ///
984    /// The 8.3 entry at `last` goes first, because that is the one that
985    /// makes the file exist; the long-name slots in front of it follow.
986    /// Interrupted between the two, the file is gone and its long name is
987    /// orphaned — untidy, and reclaimable. The other order would briefly
988    /// leave a file whose long name had been deleted out from under it,
989    /// which is a file appearing under a name nobody gave it.
990    pub(crate) fn delete_entries(
991        &mut self,
992        directory: u32,
993        first: u32,
994        last: u32,
995    ) -> Result<(), D::Error> {
996        // Before the writes, so a handle is never usable against a slot that
997        // has already been freed on the device. Counted even if the writes
998        // below fail: the 8.3 entry goes first, so a failure part-way has
999        // already freed the slot that matters.
1000        //
1001        // Every slot, not just the 8.3 entry's, though a handle only ever
1002        // records an 8.3 slot: a file created next can put its 8.3 entry
1003        // where this one's long name was, and must not inherit a
1004        // generation some older handle to that slot still matches.
1005        for index in first..=last {
1006            self.invalidate_slot(directory, index);
1007        }
1008
1009        self.edit_entry(directory, last, crate::dir::mark_deleted)?;
1010        for index in (first..last).rev() {
1011            self.edit_entry(directory, index, crate::dir::mark_deleted)?;
1012        }
1013        Ok(())
1014    }
1015
1016    /// The generation of slot `index` of `directory` under this mount.
1017    ///
1018    /// Stamped onto a [`File`](crate::File) when it is opened and compared
1019    /// when it is read or written through; see the field this reads.
1020    pub(crate) fn generation(&self, directory: u32, index: u32) -> u32 {
1021        self.generations
1022            .get(&(directory, index))
1023            .copied()
1024            .unwrap_or(0)
1025    }
1026
1027    /// The first of `count` consecutive free slots in `directory`, growing
1028    /// it if it has no run that long.
1029    ///
1030    /// The search itself touches no device at all: the free runs were
1031    /// recorded when the directory was parsed. A long name needs a run of up
1032    /// to 21 slots, and looking for one by reading the directory back a
1033    /// block at a time would cost a transfer per block for every file
1034    /// created.
1035    pub(crate) fn free_slots(&mut self, directory: u32, count: u32) -> Result<u32, D::Error> {
1036        for _ in 0..MAX_DIRECTORY_GROWTH {
1037            if let Some(index) = self.read_dir(directory)?.free_run(count) {
1038                return Ok(index);
1039            }
1040            self.grow_directory(directory)?;
1041        }
1042        // One last look, after the final growth. Without it the loop would
1043        // add a cluster and then give up without checking whether it helped,
1044        // leaving the directory permanently one cluster larger for nothing.
1045        self.read_dir(directory)?
1046            .free_run(count)
1047            .ok_or(Error::DirectoryFull)
1048    }
1049
1050    /// Adds one cluster to a directory's chain.
1051    ///
1052    /// The order is load-bearing, and it is allocate, zero, *then* link:
1053    ///
1054    ///   * allocating without linking reserves the cluster so nothing else
1055    ///     can take it, while leaving it reachable from nothing;
1056    ///   * zeroing it makes it an empty directory rather than whatever the
1057    ///     last file to own those bytes left behind, since stale bytes in a
1058    ///     directory read as entries;
1059    ///   * linking last is what makes it part of the directory.
1060    ///
1061    /// Interrupted anywhere, this leaks one cluster. Linking before zeroing
1062    /// would instead give the directory a cluster full of nonsense, which is
1063    /// not a leak but corruption.
1064    ///
1065    /// # What this does not do
1066    ///
1067    /// The link reaches the *device* later, not here: [`Fat::set_entry`]
1068    /// only marks the table's sector dirty. Publishing is the caller's
1069    /// [`flush_fat`](Self::flush_fat), and both callers
1070    /// ([`create_with_size`](FileSystem::create_with_size) and
1071    /// [`create_dir`](FileSystem::create_dir)) flush before writing the
1072    /// entry that names the new slots — which is what keeps a directory
1073    /// entry from pointing into a cluster the on-disk table still shows as
1074    /// free. A caller added later that grows a directory and writes into it
1075    /// without flushing between would break that, and this is the note
1076    /// saying so.
1077    fn grow_directory(&mut self, directory: u32) -> Result<(), D::Error> {
1078        let runs = self.fat.runs(directory)?;
1079        let last = runs
1080            .last()
1081            .map(|run| run.start_cluster + run.clusters - 1)
1082            .ok_or(Error::DirectoryFull)?;
1083
1084        let added = self.fat.allocate(1)?;
1085        let new_cluster = added[0].start_cluster;
1086
1087        let sectors_per_cluster = usize::from(self.boot.sectors_per_cluster);
1088        let zeros = vec![0u8; sectors_per_cluster * BLOCK_SIZE];
1089        let sector = self.boot.cluster_sector(new_cluster);
1090        self.write_blocks(u64::from(sector), &zeros)?;
1091
1092        self.fat.set_entry(last, new_cluster)?;
1093
1094        self.directories.remove(&directory);
1095        Ok(())
1096    }
1097
1098    /// The block device this volume sits on.
1099    pub fn device(&self) -> &D {
1100        &self.device
1101    }
1102
1103    /// The block device, mutably.
1104    ///
1105    /// Reaching past the filesystem to its device is a way to corrupt a
1106    /// mounted volume, so this exists for devices that carry their own
1107    /// state worth reaching — an instrumented one that counts transfers,
1108    /// say — rather than for writing blocks behind the filesystem's back.
1109    pub fn device_mut(&mut self) -> &mut D {
1110        &mut self.device
1111    }
1112
1113    /// Gives the block device back.
1114    pub fn into_device(self) -> D {
1115        self.device
1116    }
1117}
1118
1119/// Shifts a device's block numbers by a volume's starting offset.
1120///
1121/// Exists so [`Fat::load`] can be written against plain volume-relative
1122/// block numbers rather than threading the partition offset through every
1123/// call that reads the table.
1124struct RelativeDevice<'d, D> {
1125    device: &'d mut D,
1126    first_block: u64,
1127}
1128
1129impl<'d, D> RelativeDevice<'d, D> {
1130    fn new(device: &'d mut D, first_block: u64) -> Self {
1131        Self {
1132            device,
1133            first_block,
1134        }
1135    }
1136}
1137
1138impl<D: BlockDevice> BlockDevice for RelativeDevice<'_, D> {
1139    type Error = D::Error;
1140
1141    fn read(&mut self, start_block: u64, blocks: &mut [u8]) -> core::result::Result<(), D::Error> {
1142        self.device.read(self.first_block + start_block, blocks)
1143    }
1144
1145    fn write(&mut self, start_block: u64, blocks: &[u8]) -> core::result::Result<(), D::Error> {
1146        self.device.write(self.first_block + start_block, blocks)
1147    }
1148
1149    fn block_count(&mut self) -> core::result::Result<Option<u64>, D::Error> {
1150        self.device.block_count()
1151    }
1152
1153    /// Forwarded, not defaulted. A wrapper that let this fall back to the
1154    /// provided implementation would report "no limit" for a device that
1155    /// has one, and the transfer it then permitted would fail at the
1156    /// hardware.
1157    fn max_transfer_blocks(&self) -> u64 {
1158        self.device.max_transfer_blocks()
1159    }
1160}