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}