Skip to main content

resident_fat/
file.rs

1//! Reading files.
2//!
3//! # Where the bytes go
4//!
5//! A read is split into three parts: a partial first block, a middle of
6//! whole blocks, and a partial last block. The middle is transferred
7//! **straight into the caller's buffer** — no intermediate copy, no
8//! per-block loop — and only the ragged ends go through a one-block
9//! scratch buffer.
10//!
11//! That split is why the scratch buffer is one block regardless of how much
12//! is being read. The obvious alternative, reading every block the request
13//! touches into a temporary and copying out of it, is one device call
14//! instead of up to three, but it needs a temporary as large as the read
15//! and copies every byte twice. For the megabyte-scale reads this crate is
16//! built for, two extra calls are cheaper than either.
17//!
18//! For a small read the balance tips the other way. A request of a few
19//! kilobytes at an arbitrary offset — what a C library's buffered `fread`
20//! issues after every `fseek` — would otherwise be three single-block
21//! calls, and a card charges per call, not per block. So a ragged read
22//! touching at most eight blocks (4 KiB) is one call into a stack scratch
23//! buffer that size, and copying a few kilobytes is far cheaper than the
24//! two calls it saves.
25//!
26//! An aligned read — which is what reading a whole file is — has no ragged
27//! ends at all, so it is one transfer per run and nothing is copied.
28
29use alloc::string::String;
30use alloc::vec;
31use alloc::vec::Vec;
32
33use crate::blockdev::{BLOCK_SIZE, BlockDevice};
34use crate::dir::{Attributes, ENTRY_SIZE};
35use crate::error::{Error, FatError, Result};
36use crate::fs::FileSystem;
37use crate::name::StoredName;
38use crate::time::DateTime;
39
40/// The most blocks a ragged read can touch and still be read in one
41/// device call through a scratch buffer, rather than split into a partial
42/// first block, whole blocks and a partial last block. See the module
43/// documentation for the trade.
44///
45/// Eight blocks is a 4 KiB scratch buffer on the stack: room for the
46/// buffer refills a C library issues, small enough for an embedded stack.
47const SMALL_SPAN_BLOCKS: usize = 8;
48
49/// Everything needed to read a file: where its data starts, and how much of
50/// it means anything.
51///
52/// Plain `Copy` data holding no borrow, so a caller can keep as many of
53/// these as it likes and still use the filesystem. There is no handle
54/// table to size at compile time and no position to get out of step —
55/// offsets are passed to each read instead.
56///
57/// # Staleness
58///
59/// The trade for holding no borrow is that a handle cannot be kept up to
60/// date. It records where its directory entry lives, and removing a file
61/// frees that slot for the next one created in the directory — so a handle
62/// outlives the file it names, and the entry it points at can come to belong
63/// to something else.
64///
65/// Every read and every write checks for this and reports
66/// [`Error::StaleFile`] rather than acting on the wrong entry. The rule a
67/// caller can rely on: **a handle is invalidated when its own file's
68/// directory entry is deleted, renamed or replaced** — by
69/// [`remove`](FileSystem::remove), by [`rename`](FileSystem::rename) from or
70/// over it, or by the deletion [`write_file`](FileSystem::write_file)
71/// performs when it replaces an existing file. Changes to other files in
72/// the same directory leave it alone, so a handle can be held open for as
73/// long as its file lives. Reopening the path is the remedy for a stale
74/// one, and costs a lookup in a resident directory.
75///
76/// The check costs no device traffic: it compares against the parsed
77/// directory, which is already resident.
78///
79/// Handles do not survive a remount, and nothing makes that a type error —
80/// `File` carries no lifetime tying it to the volume it came from. Reusing
81/// one against a second mount is caught in the ordinary case and is not
82/// something to rely on.
83#[derive(Debug, Clone, Copy, PartialEq, Eq)]
84pub struct File {
85    first_cluster: u32,
86    size: u32,
87    /// Where the file's directory entry lives, so a write can update the
88    /// recorded length and starting cluster without searching for it again.
89    directory: u32,
90    index: u32,
91    /// The first slot the file's name occupies, which is `index` unless it
92    /// has a long name in front of it. Deleting has to free the whole run.
93    first_slot: u32,
94    /// The 8.3 name the entry at `index` held when this handle was made.
95    ///
96    /// Carried so a write can tell that the slot is still this file's before
97    /// rewriting it — see the note on staleness above. The 8.3 name is what
98    /// is compared rather than the long one because every entry has one, and
99    /// it is the eleven bytes that physically occupy the slot.
100    short_name: crate::dir::ShortName,
101    /// The generation of the slot at `index` when this handle was made.
102    ///
103    /// The name alone cannot detect a file replaced by another of the same
104    /// name, which is what happens on every
105    /// [`write_file`](FileSystem::write_file) over an existing path. The
106    /// slot's generation moves whenever it is freed or repointed, so a
107    /// handle from before the replacement does not match one from after it.
108    generation: u32,
109}
110
111impl File {
112    pub(crate) fn new(
113        first_cluster: u32,
114        size: u32,
115        directory: u32,
116        index: u32,
117        first_slot: u32,
118        short_name: crate::dir::ShortName,
119        generation: u32,
120    ) -> Self {
121        File {
122            first_cluster,
123            size,
124            directory,
125            index,
126            first_slot,
127            short_name,
128            generation,
129        }
130    }
131
132    /// The file's 8.3 name, as its directory entry stores it.
133    pub fn short_name(&self) -> &crate::dir::ShortName {
134        &self.short_name
135    }
136
137    /// The first cluster of the file's data, or zero if it has none.
138    pub fn first_cluster(&self) -> u32 {
139        self.first_cluster
140    }
141
142    /// The file's length in bytes.
143    ///
144    /// The length from the directory entry, not the space the file
145    /// occupies: a cluster chain is a whole number of clusters, and the
146    /// slack in the last one is not part of the file.
147    pub fn len(&self) -> u32 {
148        self.size
149    }
150
151    /// Whether the file has no content.
152    pub fn is_empty(&self) -> bool {
153        self.size == 0
154    }
155}
156
157impl<D: BlockDevice> FileSystem<D> {
158    /// Opens the file at `path`.
159    ///
160    /// `/`-separated, matching either long or short names, case
161    /// insensitively — the same resolution
162    /// [`open_dir`](FileSystem::open_dir) does.
163    pub fn open(&mut self, path: &str) -> Result<File, D::Error> {
164        let (parent, name) = split_path(path);
165        let cluster = self.resolve_dir(parent)?;
166        let directory = self.read_dir(cluster)?;
167        let entry = directory.get(name).ok_or_else(|| Error::NotFound {
168            name: String::from(name),
169        })?;
170        if entry.is_directory() {
171            return Err(Error::IsADirectory {
172                name: String::from(name),
173            });
174        }
175        // Copied out so the borrow of the parsed directory ends here, which
176        // is what lets the slot's generation below be read from `self`.
177        let (first_cluster, size, index, first_slot, short_name) = (
178            entry.first_cluster(),
179            entry.len(),
180            entry.index(),
181            entry.first_slot(),
182            *entry.short_name(),
183        );
184
185        Ok(File::new(
186            first_cluster,
187            size,
188            cluster,
189            index,
190            first_slot,
191            short_name,
192            self.generation(cluster, index),
193        ))
194    }
195
196    /// Refuses a handle whose directory slot has stopped being its own.
197    ///
198    /// Guards every operation that writes. The damage it prevents is not to
199    /// the file named by the handle — that one is gone — but to whichever
200    /// file has since been given its slot: without this, writing through a
201    /// stale handle rewrites that entry's length and starting cluster, and
202    /// truncates a file the caller never opened.
203    ///
204    /// Costs no device traffic in the case that matters. The parsed
205    /// directory is resident and was read to produce the handle in the first
206    /// place, so this is a binary search in memory — which is why the check
207    /// can be unconditional rather than something a caller opts into.
208    ///
209    /// # Two tests, because one is not enough
210    ///
211    /// The slot's generation catches a slot that was freed and retaken,
212    /// which the name cannot when the new occupant has the same name — the
213    /// case [`write_file`](Self::write_file) produces every time it replaces
214    /// a file.
215    ///
216    /// The name catches what the generation cannot: a handle whose recorded
217    /// slot never belonged to it in the first place, which is the shape a
218    /// handle carried across mounts has, since every generation of a fresh
219    /// mount starts at zero.
220    fn check_live(&mut self, file: &File) -> Result<(), D::Error> {
221        let generation = self.generation(file.directory, file.index);
222        let live = generation == file.generation
223            && self
224                .read_dir(file.directory)?
225                .at(file.index)
226                .is_some_and(|entry| entry.short_name().as_bytes() == file.short_name.as_bytes());
227        if live {
228            return Ok(());
229        }
230        Err(Error::StaleFile {
231            name: file.short_name.to_display_string_with(self.codepage()),
232        })
233    }
234
235    /// Reads the whole file.
236    ///
237    /// Exactly [`File::len`] bytes — the slack in the last cluster is not
238    /// part of the file and does not come back. One device transfer per
239    /// run of the file's chain, so a contiguous file of any size is one
240    /// call.
241    ///
242    /// The whole file is buffered, and FAT32 allows one of nearly 4 GiB, so
243    /// this reports [`Error::OutOfMemory`] rather than aborting when the
244    /// host cannot hold it. [`read_at`](Self::read_at) is the way to take a
245    /// large file in pieces the caller sizes.
246    pub fn read_all(&mut self, file: &File) -> Result<Vec<u8>, D::Error> {
247        let mut data = crate::error::try_filled(0u8, u64::from(file.size))?;
248        let read = self.read_at(file, 0, &mut data)?;
249        debug_assert_eq!(read, data.len());
250        Ok(data)
251    }
252
253    /// Reads from `offset` into `into`, returning how many bytes arrived.
254    ///
255    /// Short only at the end of the file: a read starting at or past
256    /// [`File::len`] returns zero, and one that would run past the end
257    /// stops there. Anything else short would be a device error instead.
258    pub fn read_at(
259        &mut self,
260        file: &File,
261        offset: u64,
262        into: &mut [u8],
263    ) -> Result<usize, D::Error> {
264        let size = u64::from(file.size);
265        if offset >= size || into.is_empty() {
266            return Ok(0);
267        }
268        // A stale handle names another file's clusters, so reading through
269        // one hands back that file's bytes under a name the caller supplied
270        // — the same disclosure `create_with_size` refuses to make by
271        // recording a length over unwritten clusters. Free when the
272        // directory is resident, which it is on any path that just opened
273        // the file.
274        self.check_live(file)?;
275        let wanted = into.len().min((size - offset) as usize);
276        let into = &mut into[..wanted];
277
278        if file.first_cluster == 0 {
279            // A file with a length but no clusters is corrupt; one with
280            // neither is empty and was handled above.
281            return Err(FatError::BadCluster { cluster: 0 }.into());
282        }
283
284        let cluster_bytes = u64::from(self.boot_sector().cluster_bytes());
285        // Cached: a read walks no table entries when the chain was read
286        // before and the table hasn't changed since.
287        let runs = self.take_runs(file.first_cluster)?;
288
289        let mut done = 0usize;
290        let mut at = offset;
291        for run in &runs {
292            let run_start = u64::from(run.file_cluster) * cluster_bytes;
293            let run_len = run.bytes(cluster_bytes as u32);
294            let run_end = run_start + run_len;
295            if at >= run_end {
296                continue;
297            }
298
299            let take = (run_end - at).min((wanted - done) as u64) as usize;
300            let within_run = at - run_start;
301            let first_block = u64::from(self.boot_sector().cluster_sector(run.start_cluster))
302                + within_run / BLOCK_SIZE as u64;
303
304            self.read_span(
305                first_block,
306                (within_run % BLOCK_SIZE as u64) as usize,
307                &mut into[done..done + take],
308            )?;
309
310            done += take;
311            at += take as u64;
312            if done == wanted {
313                break;
314            }
315        }
316        self.keep_runs(file.first_cluster, runs);
317
318        if done != wanted {
319            // The chain ran out before the length in the directory entry
320            // did, which means the two disagree.
321            return Err(FatError::ChainShorterThanFile {
322                start: file.first_cluster,
323                size: file.size,
324            }
325            .into());
326        }
327        Ok(done)
328    }
329
330    /// Reads `into.len()` bytes starting `skip` bytes into `first_block`.
331    ///
332    /// The three-part split described in this module's header, or one call
333    /// through scratch for a small ragged read. Callers pass a range that
334    /// lies inside one contiguous run, so every block here is consecutive
335    /// on the device.
336    fn read_span(
337        &mut self,
338        first_block: u64,
339        skip: usize,
340        into: &mut [u8],
341    ) -> Result<(), D::Error> {
342        let ragged = skip != 0 || into.len() % BLOCK_SIZE != 0;
343        let span = (skip + into.len()).div_ceil(BLOCK_SIZE);
344        if ragged && span <= SMALL_SPAN_BLOCKS && span as u64 <= self.device().max_transfer_blocks()
345        {
346            let mut scratch = [0u8; SMALL_SPAN_BLOCKS * BLOCK_SIZE];
347            let scratch = &mut scratch[..span * BLOCK_SIZE];
348            self.read_blocks(first_block, scratch)?;
349            into.copy_from_slice(&scratch[skip..skip + into.len()]);
350            return Ok(());
351        }
352
353        let mut block = first_block;
354        let mut into = into;
355
356        // Leading partial block, when the read does not start on a
357        // boundary. One block through the scratch buffer, however large
358        // the overall read is.
359        if skip != 0 {
360            let take = (BLOCK_SIZE - skip).min(into.len());
361            let mut scratch = [0u8; BLOCK_SIZE];
362            self.read_blocks(block, &mut scratch)?;
363            into[..take].copy_from_slice(&scratch[skip..skip + take]);
364            into = &mut into[take..];
365            block += 1;
366        }
367
368        // Whole blocks, straight into the caller's buffer — no scratch, no
369        // copy. Split only where the device says it must be.
370        let whole = into.len() / BLOCK_SIZE;
371        if whole != 0 {
372            // Clamped at both ends. The upper bound is not cosmetic: an
373            // unlimited device reports `u64::MAX`, and `cap * BLOCK_SIZE`
374            // below would overflow.
375            let cap = usize::try_from(self.device().max_transfer_blocks())
376                .unwrap_or(usize::MAX)
377                .clamp(1, whole);
378            let (aligned, rest) = into.split_at_mut(whole * BLOCK_SIZE);
379            for (batch, chunk) in aligned.chunks_mut(cap * BLOCK_SIZE).enumerate() {
380                self.read_blocks(block + (batch * cap) as u64, chunk)?;
381            }
382            block += whole as u64;
383            into = rest;
384        }
385
386        // Trailing partial block.
387        if !into.is_empty() {
388            let mut scratch = [0u8; BLOCK_SIZE];
389            self.read_blocks(block, &mut scratch)?;
390            let take = into.len();
391            into.copy_from_slice(&scratch[..take]);
392        }
393
394        Ok(())
395    }
396}
397
398impl<D: BlockDevice> FileSystem<D> {
399    /// Creates an empty file at `path`.
400    pub fn create(&mut self, path: &str) -> Result<File, D::Error> {
401        self.create_with_size(path, 0)
402    }
403
404    /// Works out how a new name will be stored in `directory`, refusing it
405    /// if the name is already there.
406    ///
407    /// Both halves need the parsed directory: the collision check, and
408    /// choosing an 8.3 alias nothing else has. With the directory resident
409    /// neither costs a device call.
410    fn plan_name(&mut self, directory: u32, name: &str) -> Result<StoredName, D::Error> {
411        self.plan_name_except(directory, name, None, false)
412    }
413
414    /// [`plan_name`](Self::plan_name), for renaming the entry at `except`.
415    ///
416    /// That entry does not collide with the new name — it is the one being
417    /// renamed, and a name differing only in case finds it. Whether it
418    /// counts against the 8.3 alias is `reuse_alias`: yes when the new
419    /// entry is written over it, so the file can keep its alias; no when
420    /// the old entry is still live on the device while the new one is
421    /// written, since two live entries must not share one.
422    fn plan_name_except(
423        &mut self,
424        directory: u32,
425        name: &str,
426        except: Option<u32>,
427        reuse_alias: bool,
428    ) -> Result<StoredName, D::Error> {
429        let codepage = *self.codepage();
430        let parsed = self.read_dir(directory)?;
431        let other = |candidate: &str| {
432            parsed
433                .get(candidate)
434                .is_some_and(|entry| Some(entry.index()) != except)
435        };
436        if other(name) {
437            return Err(Error::AlreadyExists {
438                name: String::from(name),
439            });
440        }
441        crate::name::stored_name(name, &codepage, &mut |alias| {
442            if reuse_alias {
443                other(alias)
444            } else {
445                parsed.get(alias).is_some()
446            }
447        })
448    }
449
450    /// Lays a name's entries out ready to write: the long-name slots, then
451    /// the 8.3 entry that terminates them.
452    ///
453    /// `at` stamps every timestamp on the 8.3 entry, and comes from the
454    /// volume's clock — [`DateTime::EPOCH`] when nothing has supplied one,
455    /// which is a real date unlike the zeroes an entry would otherwise
456    /// carry. Taken as an argument rather than read here so that one
457    /// operation reads the clock once: a long name is several entries
458    /// written together, and a tick falling between them would leave a
459    /// file's own slots disagreeing about when it was made.
460    fn name_entries(
461        stored: &StoredName,
462        attributes: Attributes,
463        first_cluster: u32,
464        size: u32,
465        at: DateTime,
466    ) -> Vec<[u8; ENTRY_SIZE]> {
467        let mut entries = stored.slots.clone();
468        let mut short = [0u8; ENTRY_SIZE];
469        crate::dir::write_entry(
470            &mut short,
471            &stored.short,
472            attributes,
473            first_cluster,
474            size,
475            at,
476        );
477        entries.push(short);
478        entries
479    }
480
481    /// Creates a file at `path` with room for `size` bytes already
482    /// allocated.
483    ///
484    /// The size is a hint about the whole file, and it is what makes the
485    /// result contiguous: the allocator is asked for every cluster at once
486    /// and will find a single run if the volume has one, so the file can
487    /// afterwards be written — and read — in a single device transfer. A
488    /// file grown a write at a time gets whatever the allocator had spare
489    /// each time, which is how files become fragmented.
490    ///
491    /// # `size` reserves space; it does not set the length
492    ///
493    /// The file comes back **empty**, and its length grows as
494    /// [`write_at`](Self::write_at) fills the space in. The reservation is
495    /// real — the clusters are allocated and chained, so the contiguity is
496    /// already decided — but no length is recorded over bytes nothing has
497    /// written yet.
498    ///
499    /// That is deliberate, and it is the difference between reserving space
500    /// and lying about it. Recording `size` here would make the file
501    /// readable at its full length before a byte of it existed, and what
502    /// came back would be whatever the last file to own those clusters left
503    /// behind. FAT does not erase a chain when it frees one, so those bytes
504    /// are another file's data, handed to a caller that never opened it.
505    ///
506    /// Zeroing the clusters instead would fix the disclosure and cost the
507    /// write twice over — once with zeros and once with the data — which is
508    /// most of what this crate exists to avoid. So the length follows the
509    /// data rather than leading it.
510    ///
511    /// A file reserved and then never written stays zero length while
512    /// holding its clusters, until it is written or removed. `fsck.vfat`
513    /// describes that state as a file whose size does not account for its
514    /// chain and offers to truncate it to zero, which releases the
515    /// reservation and is the right repair — wasted space, and nothing
516    /// worse. Keeping the reservation attached to a named file is what makes
517    /// it visible and removable at all; a reservation held off the directory
518    /// entry would leak silently the moment the caller lost interest.
519    ///
520    /// # Ordering
521    ///
522    /// The clusters are allocated and chained before the directory entry
523    /// naming them is written. Interrupted between the two, the volume has
524    /// clusters belonging to nothing — a leak, which `fsck` reclaims. The
525    /// other order would publish a directory entry pointing at clusters
526    /// the allocator still believes are free, which is how two files come
527    /// to share data.
528    pub fn create_with_size(&mut self, path: &str, size: u32) -> Result<File, D::Error> {
529        let now = self.now();
530        let (parent, name) = split_path(path);
531        let directory = self.resolve_dir(parent)?;
532        let stored = self.plan_name(directory, name)?;
533
534        let cluster_bytes = self.boot_sector().cluster_bytes();
535        let clusters = size.div_ceil(cluster_bytes.max(1));
536        let runs = self.fat_mut().allocate(clusters)?;
537        let first_cluster = runs.first().map(|run| run.start_cluster).unwrap_or(0);
538
539        // Nothing names these clusters yet, so giving them back on the way
540        // out of a failure costs nothing and leaks nothing.
541        let undo = |volume: &mut Self| {
542            if first_cluster != 0 {
543                let _ = volume.fat_mut().free_chain(first_cluster);
544            }
545        };
546
547        let first_slot = match self.free_slots(directory, stored.entries()) {
548            Ok(index) => index,
549            Err(error) => {
550                undo(self);
551                return Err(error);
552            }
553        };
554
555        // The allocation reaches the device before the entry that names it.
556        // Interrupted here, the clusters are marked used and belong to
557        // nothing, which `fsck` reclaims. The other order would leave an
558        // entry pointing at clusters the allocator still offers to the next
559        // caller — verified: removing this flush makes `fsck` report
560        // "Contains a free cluster" instead of a plain leak.
561        if let Err(error) = self.flush_fat() {
562            undo(self);
563            return Err(error);
564        }
565
566        // Length zero, not `size`: the clusters are reserved but nothing has
567        // written them, and a length is a promise about content. See this
568        // method's documentation.
569        let entries = Self::name_entries(&stored, Attributes::ARCHIVE, first_cluster, 0, now);
570        if let Err(error) = self.write_entries(directory, first_slot, &entries) {
571            undo(self);
572            return Err(error);
573        }
574
575        let index = first_slot + stored.slots.len() as u32;
576        Ok(File::new(
577            first_cluster,
578            0,
579            directory,
580            index,
581            first_slot,
582            stored.short,
583            self.generation(directory, index),
584        ))
585    }
586
587    /// Creates a directory at `path`, returning its first cluster.
588    ///
589    /// The parent must exist; this makes one directory, not a chain of them.
590    ///
591    /// # Ordering
592    ///
593    /// The new directory's cluster is allocated, filled in with its `.` and
594    /// `..` entries, and linked into the table on the device — all before
595    /// the parent gains an entry naming it. Interrupted at any point, the
596    /// result is a leaked cluster holding a directory nothing points at. The
597    /// other order would publish a directory entry whose cluster still held
598    /// whatever the last file to own it left behind, and stale bytes in a
599    /// directory read as entries.
600    pub fn create_dir(&mut self, path: &str) -> Result<u32, D::Error> {
601        let now = self.now();
602        let (parent_path, name) = split_path(path);
603        let parent = self.resolve_dir(parent_path)?;
604        let stored = self.plan_name(parent, name)?;
605
606        let cluster = self.fat_mut().allocate(1)?[0].start_cluster;
607        let undo = |volume: &mut Self| {
608            let _ = volume.fat_mut().free_chain(cluster);
609        };
610
611        let first_slot = match self.free_slots(parent, stored.entries()) {
612            Ok(index) => index,
613            Err(error) => {
614                undo(self);
615                return Err(error);
616            }
617        };
618
619        // `..` names the parent — except when the parent is the root, where
620        // the format writes 0. The cluster an entry carries and the cluster
621        // the directory lives at are the same number everywhere else, and
622        // this is the one place they are not.
623        let parent_link = if parent == self.root_cluster() {
624            0
625        } else {
626            parent
627        };
628        let sectors = usize::from(self.boot_sector().sectors_per_cluster);
629        let mut data = vec![0u8; sectors * BLOCK_SIZE];
630        crate::dir::write_dot_entries(&mut data, cluster, parent_link, now);
631
632        let sector = u64::from(self.boot_sector().cluster_sector(cluster));
633        let published = self
634            .write_blocks(sector, &data)
635            .and_then(|()| self.flush_fat())
636            .and_then(|()| {
637                // A directory has no length: its size field is zero and its
638                // extent is its cluster chain.
639                let entries = Self::name_entries(&stored, Attributes::DIRECTORY, cluster, 0, now);
640                self.write_entries(parent, first_slot, &entries)
641            });
642        if let Err(error) = published {
643            undo(self);
644            return Err(error);
645        }
646
647        Ok(cluster)
648    }
649
650    /// Removes the empty directory at `path`.
651    ///
652    /// Refuses a directory that still holds anything. Removing one would
653    /// leave its contents allocated and unreachable — space no `fsck` run
654    /// reclaims, because the clusters really are referenced, by entries
655    /// nothing can find any more.
656    pub fn remove_dir(&mut self, path: &str) -> Result<(), D::Error> {
657        let (parent_path, name) = split_path(path);
658        let parent = self.resolve_dir(parent_path)?;
659
660        let (cluster, first_slot, index) = {
661            let parsed = self.read_dir(parent)?;
662            let entry = parsed.get(name).ok_or_else(|| Error::NotFound {
663                name: String::from(name),
664            })?;
665            if !entry.is_directory() {
666                return Err(Error::NotADirectory {
667                    name: String::from(name),
668                });
669            }
670            (entry.first_cluster(), entry.first_slot(), entry.index())
671        };
672
673        let occupied = self
674            .read_dir(cluster)?
675            .iter()
676            .filter(|entry| entry.name() != "." && entry.name() != "..")
677            .count();
678        if occupied != 0 {
679            return Err(Error::DirectoryNotEmpty {
680                name: String::from(name),
681            });
682        }
683
684        // The entry first, then the clusters, as everywhere else: a leak
685        // beats a directory entry naming space that has been handed out.
686        self.delete_entries(parent, first_slot, index)?;
687        self.fat_mut().free_chain(cluster)?;
688        self.flush_fat()?;
689        self.forget_directory(cluster);
690        Ok(())
691    }
692
693    /// Writes `data` at `offset`, growing the file if it needs to.
694    ///
695    /// The file's recorded length is updated when the write extends it.
696    /// `file` is updated to match, so it stays usable afterwards.
697    ///
698    /// # Writing past the end
699    ///
700    /// A write starting beyond [`File::len`] leaves a gap, and the gap is
701    /// filled with zeros before the new length publishes it. The clusters
702    /// under it hold whatever the last file to own them left behind — FAT
703    /// frees a chain without erasing it — so the alternative is handing a
704    /// caller another file's data under a length this crate wrote. The
705    /// zeroing costs one pass over the gap, and only a caller that actually
706    /// skips ahead pays it.
707    pub fn write_at(&mut self, file: &mut File, offset: u64, data: &[u8]) -> Result<(), D::Error> {
708        let now = self.now();
709        if data.is_empty() {
710            return Ok(());
711        }
712        // Before anything is allocated or written. A stale handle names
713        // another file's clusters as well as another file's entry, so the
714        // check has to come ahead of `write_chain` and not merely ahead of
715        // the entry update.
716        self.check_live(file)?;
717        let end = offset + data.len() as u64;
718        if end > u64::from(u32::MAX) {
719            return Err(FatError::DiskFull {
720                wanted: u32::MAX,
721                free: self.fat().free_clusters(),
722            }
723            .into());
724        }
725
726        self.reserve(file, end as u32)?;
727
728        // Before the data, so that an interruption between the two leaves a
729        // gap of zeros rather than a gap of somebody else's file.
730        if offset > u64::from(file.size) {
731            self.zero_range(file, u64::from(file.size), offset)?;
732        }
733
734        self.write_chain(file, offset, data)?;
735
736        if end as u32 > file.size {
737            let (first, size) = (file.first_cluster, end as u32);
738            self.edit_entry(file.directory, file.index, |entry| {
739                crate::dir::update_entry(entry, first, size, now);
740            })?;
741            file.size = size;
742        }
743        Ok(())
744    }
745
746    /// Creates `path` holding exactly `data`, replacing anything there.
747    ///
748    /// The shape most callers want, and the one that produces a contiguous
749    /// file: the length is known before a byte is written, so the whole
750    /// chain is allocated at once.
751    pub fn write_file(&mut self, path: &str, data: &[u8]) -> Result<File, D::Error> {
752        if self.open(path).is_ok() {
753            self.remove(path)?;
754        }
755        let mut file = self.create_with_size(path, data.len() as u32)?;
756        self.write_at(&mut file, 0, data)?;
757        Ok(file)
758    }
759
760    /// Sets the file's length, freeing or allocating clusters to match.
761    ///
762    /// Growing zeroes what it adds, the way every filesystem a caller has
763    /// met does: the clusters it reaches into hold whatever the last file to
764    /// own them left behind, and a length is a promise about content. See
765    /// [`write_at`](Self::write_at) on writing past the end, which is the
766    /// same gap by another route.
767    ///
768    /// # Ordering
769    ///
770    /// Shrinking writes the new length to the directory entry **first**,
771    /// and frees the tail of the chain afterwards. Interrupted between the
772    /// two, the volume has clusters nothing refers to — a leak. The other
773    /// order leaves a directory entry claiming clusters the allocator has
774    /// already handed to someone else, and two files sharing data is a
775    /// worse outcome than some space going unused until `fsck` runs.
776    pub fn truncate(&mut self, file: &mut File, size: u32) -> Result<(), D::Error> {
777        let now = self.now();
778        // Shrinking frees the tail of the chain, so a stale handle would
779        // hand another file's clusters back to the allocator.
780        self.check_live(file)?;
781        if size > file.size {
782            self.reserve(file, size)?;
783            // The zeros land before the length that publishes them, so an
784            // interruption between the two leaves the file its old length
785            // rather than a longer one ending in stale bytes.
786            self.zero_range(file, u64::from(file.size), u64::from(size))?;
787            let (first, new) = (file.first_cluster, size);
788            self.edit_entry(file.directory, file.index, |entry| {
789                crate::dir::update_entry(entry, first, new, now);
790            })?;
791            file.size = new;
792            return Ok(());
793        }
794        if size == file.size {
795            return Ok(());
796        }
797
798        let cluster_bytes = self.boot_sector().cluster_bytes();
799        let keep = size.div_ceil(cluster_bytes.max(1));
800        let first_cluster = if keep == 0 { 0 } else { file.first_cluster };
801
802        // The entry first, and only then the chain.
803        self.edit_entry(file.directory, file.index, |entry| {
804            crate::dir::update_entry(entry, first_cluster, size, now);
805        })?;
806
807        if file.first_cluster != 0 {
808            self.fat_mut().truncate_chain(file.first_cluster, keep)?;
809            // The freed tail reaches the device only after the entry has
810            // stopped claiming it.
811            self.flush_fat()?;
812        }
813        file.size = size;
814        file.first_cluster = first_cluster;
815        Ok(())
816    }
817
818    /// Deletes the file at `path`.
819    ///
820    /// The entry is marked deleted before the chain is freed, for the same
821    /// reason truncation shrinks first. A long name's slots go with it:
822    /// leaving them behind would produce the orphaned long-name parts
823    /// `fsck.vfat` reports, occupying directory space nothing could reuse.
824    pub fn remove(&mut self, path: &str) -> Result<(), D::Error> {
825        let file = self.open(path)?;
826        self.delete_entries(file.directory, file.first_slot, file.index)?;
827        if file.first_cluster != 0 {
828            self.fat_mut().free_chain(file.first_cluster)?;
829            self.flush_fat()?;
830        }
831        Ok(())
832    }
833
834    /// Renames or moves the file or directory at `from` to `to`, replacing a
835    /// file already at `to`.
836    ///
837    /// Nothing is copied: the data stays in its clusters, and only
838    /// directory entries change. Both paths are `/`-separated and resolve
839    /// the way [`open`](Self::open) does. A name differing from the old one
840    /// only in case is a rename; an identical one does nothing.
841    ///
842    /// Handles to `from` are stale afterwards, as are handles to a file it
843    /// replaced — see [`File`] on staleness.
844    ///
845    /// FAT has no atomic rename, so what an interruption leaves behind is
846    /// decided by the order of the writes, and the three cases below differ.
847    ///
848    /// # Replacing a file, and why that is the useful case
849    ///
850    /// The one way to change a file that an interruption cannot leave
851    /// half-written is to write the new contents under another name and
852    /// rename it over the old: `settings.new` → `settings.toml`. This makes
853    /// that work: **`to` always names a whole file**, the old one or the
854    /// new one, and never nothing and never part of one.
855    ///
856    /// `from`'s entry is deleted first, then `to`'s entry is repointed at
857    /// `from`'s data — first cluster, size, attributes and timestamps — in
858    /// one write of one sector, and only then is `to`'s old data freed.
859    /// Interrupted before the repoint, `to` is the old file and the new
860    /// data is allocated to nothing: the save did not happen, and `fsck`
861    /// reclaims the space. Interrupted after it, `to` is the new file and
862    /// the old data is what leaks. No cluster ever belongs to two names —
863    /// repointing first would have `to` and `from` sharing one chain until
864    /// `from` was deleted.
865    ///
866    /// Only a file replaces a file. A directory at `to`, or a directory at
867    /// `from` with anything at `to`, is [`Error::AlreadyExists`].
868    ///
869    /// # A new name in the same directory
870    ///
871    /// When the new name takes no more directory slots than the old one,
872    /// the entry is rewritten where it stands: the new long-name slots and
873    /// the 8.3 entry, in ascending order, over the old ones, and any the
874    /// shorter name no longer needs deleted afterwards. An interruption
875    /// can leave long-name slots whose checksum does not match the 8.3
876    /// entry after them, which every reader ignores — so the file is found
877    /// under its old or its new name, or at worst under its 8.3 alias, and
878    /// is never lost or shared.
879    ///
880    /// # Anything else
881    ///
882    /// A move to another directory, or a name longer than the slots it
883    /// has: the new entries are written first, then the old ones deleted.
884    /// This is the one case with no ordering free of a window. Interrupted
885    /// between the two, the file has both names — two entries sharing one
886    /// chain, which `fsck.vfat` reports and repairs by dropping one. The
887    /// other order would leave the data named by nothing, which `fsck`
888    /// reclaims as lost; sharing loses nothing, so it is the lesser.
889    ///
890    /// A directory moved to another parent has its `..` pointed at the new
891    /// one, between the two steps. Moving a directory inside itself or
892    /// anything it contains is [`Error::MoveIntoItself`].
893    pub fn rename(&mut self, from: &str, to: &str) -> Result<(), D::Error> {
894        let (from_parent, from_name) = split_path(from);
895        let (to_parent, to_name) = split_path(to);
896        for name in [from_name, to_name] {
897            if name.is_empty() || name == "." || name == ".." {
898                return Err(Error::BadName {
899                    name: String::from(name),
900                });
901            }
902        }
903        let from_dir = self.resolve_dir(from_parent)?;
904        let to_dir = self.resolve_dir(to_parent)?;
905
906        let source = self
907            .read_dir(from_dir)?
908            .get(from_name)
909            .map(Placed::of)
910            .ok_or_else(|| Error::NotFound {
911                name: String::from(from_name),
912            })?;
913        let target = self.read_dir(to_dir)?.get(to_name).map(Placed::of);
914
915        match target {
916            Some(target) if to_dir == from_dir && target.index == source.index => {
917                // The same entry: a change of case, or no change at all.
918                let current = self.read_dir(from_dir)?.at(source.index).map(|e| e.name());
919                if current == Some(to_name) {
920                    return Ok(());
921                }
922                self.rename_here(source, from_dir, to_name)
923            }
924            Some(target) => {
925                if target.is_directory || source.is_directory {
926                    return Err(Error::AlreadyExists {
927                        name: String::from(to_name),
928                    });
929                }
930                self.replace_file(source, from_dir, target, to_dir)
931            }
932            None if to_dir == from_dir => self.rename_here(source, from_dir, to_name),
933            None => self.move_to_new_name(source, from_dir, to_dir, to_name),
934        }
935    }
936
937    /// `rename`'s file-over-file case. See [`rename`](Self::rename) for why
938    /// the writes are in this order.
939    fn replace_file(
940        &mut self,
941        source: Placed,
942        from_dir: u32,
943        target: Placed,
944        to_dir: u32,
945    ) -> Result<(), D::Error> {
946        let contents = self.read_entry(from_dir, source.index)?;
947        // `from` goes first: from here until the repoint, the new data is
948        // named by nothing, which is a leak rather than two names on one
949        // chain.
950        self.delete_entries(from_dir, source.first_slot, source.index)?;
951        // A handle to what `to` held would otherwise still match its slot,
952        // and write into the chain freed below.
953        self.invalidate_slot(to_dir, target.index);
954        self.edit_entry(to_dir, target.index, |entry| {
955            crate::dir::take_contents(entry, &contents);
956        })?;
957        if target.first_cluster != 0 {
958            self.fat_mut().free_chain(target.first_cluster)?;
959            self.flush_fat()?;
960        }
961        Ok(())
962    }
963
964    /// `rename` within one directory. In place when the new name's slots
965    /// fit in the old one's run — see [`rename`](Self::rename) for why that
966    /// is the safe way — and by [`move_to_new_name`](Self::move_to_new_name)
967    /// when they do not.
968    fn rename_here(
969        &mut self,
970        source: Placed,
971        directory: u32,
972        to_name: &str,
973    ) -> Result<(), D::Error> {
974        // Rewritten in place, the new entry replaces the old one, so it may
975        // keep its 8.3 alias.
976        let stored = self.plan_name_except(directory, to_name, Some(source.index), true)?;
977        let have = source.index - source.first_slot + 1;
978        if stored.entries() > have {
979            // Not in place: the old entry stays live until the new one is
980            // written, so they must not share an alias.
981            let stored = self.plan_name_except(directory, to_name, Some(source.index), false)?;
982            return self.write_new_then_delete(source, directory, directory, &stored);
983        }
984
985        let mut short = self.read_entry(directory, source.index)?;
986        crate::dir::rename_entry(&mut short, &stored.short);
987        let mut entries = stored.slots.clone();
988        entries.push(short);
989
990        // The new run ends where the old one does, on the entry's own 8.3
991        // slot, and is written in ascending order so that slot goes last.
992        let new_first = source.index + 1 - stored.entries();
993        self.write_entries(directory, new_first, &entries)?;
994        if new_first > source.first_slot {
995            // The old name's leading slots, which the shorter one does not
996            // reach. Left, they would be long-name parts orphaned in front of
997            // a run that begins after them.
998            self.delete_entries(directory, source.first_slot, new_first - 1)?;
999        }
1000        Ok(())
1001    }
1002
1003    /// `rename` to another directory. See [`rename`](Self::rename) on the
1004    /// window this leaves, which is why it is not used within one.
1005    fn move_to_new_name(
1006        &mut self,
1007        source: Placed,
1008        from_dir: u32,
1009        to_dir: u32,
1010        to_name: &str,
1011    ) -> Result<(), D::Error> {
1012        if source.is_directory && self.is_within(to_dir, source.first_cluster)? {
1013            return Err(Error::MoveIntoItself {
1014                name: String::from(to_name),
1015            });
1016        }
1017        let stored = self.plan_name(to_dir, to_name)?;
1018        self.write_new_then_delete(source, from_dir, to_dir, &stored)
1019    }
1020
1021    /// New entries carrying `source`'s fields under `stored`'s name in
1022    /// `to_dir`, then `source`'s entries deleted — pointing a moved
1023    /// directory's `..` at its new parent in between.
1024    fn write_new_then_delete(
1025        &mut self,
1026        source: Placed,
1027        from_dir: u32,
1028        to_dir: u32,
1029        stored: &StoredName,
1030    ) -> Result<(), D::Error> {
1031        let moving_directory = source.is_directory && to_dir != from_dir;
1032        let mut short = self.read_entry(from_dir, source.index)?;
1033        crate::dir::rename_entry(&mut short, &stored.short);
1034        let mut entries = stored.slots.clone();
1035        entries.push(short);
1036
1037        // Finding the slots may have grown the directory, and its new
1038        // cluster has to be linked on the device before an entry is
1039        // written into it -- see `grow_directory`.
1040        let first_slot = self.free_slots(to_dir, stored.entries())?;
1041        self.flush_fat()?;
1042        self.write_entries(to_dir, first_slot, &entries)?;
1043
1044        if moving_directory {
1045            // `..` names the parent, and 0 when the parent is the root --
1046            // the one place a cluster an entry carries and the cluster a
1047            // directory lives at differ.
1048            let parent = if to_dir == self.root_cluster() {
1049                0
1050            } else {
1051                to_dir
1052            };
1053            self.edit_entry(source.first_cluster, 1, |entry| {
1054                crate::dir::set_first_cluster(entry, parent);
1055            })?;
1056        }
1057
1058        self.delete_entries(from_dir, source.first_slot, source.index)
1059    }
1060
1061    /// Whether `directory` is `ancestor` or lies anywhere beneath it,
1062    /// following `..` up to the root.
1063    fn is_within(&mut self, directory: u32, ancestor: u32) -> Result<bool, D::Error> {
1064        let root = self.root_cluster();
1065        let mut at = directory;
1066        // Bounded by the cluster count: a well-formed tree reaches the root
1067        // in fewer steps than there are clusters, and a `..` loop in a
1068        // damaged one must not hang the caller.
1069        for _ in 0..=self.fat().cluster_count() {
1070            if at == ancestor {
1071                return Ok(true);
1072            }
1073            if at == root {
1074                return Ok(false);
1075            }
1076            let parent = self
1077                .read_dir(at)?
1078                .get("..")
1079                .map(|entry| entry.first_cluster())
1080                .unwrap_or(0);
1081            at = if parent == 0 { root } else { parent };
1082        }
1083        Ok(false)
1084    }
1085
1086    /// Makes sure the file has clusters for at least `size` bytes.
1087    fn reserve(&mut self, file: &mut File, size: u32) -> Result<(), D::Error> {
1088        let now = self.now();
1089        let cluster_bytes = self.boot_sector().cluster_bytes().max(1);
1090        let wanted = size.div_ceil(cluster_bytes);
1091        if wanted == 0 {
1092            return Ok(());
1093        }
1094
1095        if file.first_cluster == 0 {
1096            let runs = self.fat_mut().allocate(wanted)?;
1097            let first = runs[0].start_cluster;
1098            // Table to the device first, then the entry that names it —
1099            // the same rule as `create_with_size`, for the same reason.
1100            self.flush_fat()?;
1101            let size_now = file.size;
1102            self.edit_entry(file.directory, file.index, |entry| {
1103                crate::dir::update_entry(entry, first, size_now, now);
1104            })?;
1105            file.first_cluster = first;
1106            return Ok(());
1107        }
1108
1109        let have = self.fat().chain_length(file.first_cluster)?;
1110        if wanted > have {
1111            let runs = self.fat().runs(file.first_cluster)?;
1112            let last = runs
1113                .last()
1114                .map(|run| run.start_cluster + run.clusters - 1)
1115                .expect("a chain has at least one cluster");
1116            self.fat_mut().append(last, wanted - have)?;
1117            // The longer chain has to be on the device before the entry
1118            // records a length that depends on it.
1119            self.flush_fat()?;
1120        }
1121        Ok(())
1122    }
1123
1124    /// Writes `data` at `offset` into the chain the file already has.
1125    ///
1126    /// One [`write_span`](Self::write_span) per run the range crosses, so a
1127    /// write landing inside one contiguous run is one device transfer
1128    /// however large it is. Growing the chain is [`reserve`](Self::reserve)'s
1129    /// job; this fails rather than extending, because a short chain here
1130    /// means the table and the directory entry disagree.
1131    fn write_chain(&mut self, file: &File, offset: u64, data: &[u8]) -> Result<(), D::Error> {
1132        let cluster_bytes = u64::from(self.boot_sector().cluster_bytes());
1133        let runs = self.runs(file.first_cluster)?;
1134
1135        let mut done = 0usize;
1136        let mut at = offset;
1137        for run in &runs {
1138            let run_start = u64::from(run.file_cluster) * cluster_bytes;
1139            let run_end = run_start + run.bytes(cluster_bytes as u32);
1140            if at >= run_end {
1141                continue;
1142            }
1143            let take = (run_end - at).min((data.len() - done) as u64) as usize;
1144            let within_run = at - run_start;
1145            let first_block = u64::from(self.boot_sector().cluster_sector(run.start_cluster))
1146                + within_run / BLOCK_SIZE as u64;
1147
1148            self.write_span(
1149                first_block,
1150                (within_run % BLOCK_SIZE as u64) as usize,
1151                &data[done..done + take],
1152            )?;
1153
1154            done += take;
1155            at += take as u64;
1156            if done == data.len() {
1157                break;
1158            }
1159        }
1160
1161        if done != data.len() {
1162            return Err(FatError::ChainShorterThanFile {
1163                start: file.first_cluster,
1164                size: (offset + data.len() as u64) as u32,
1165            }
1166            .into());
1167        }
1168        Ok(())
1169    }
1170
1171    /// Writes zeros over `from..to` of the file's existing chain.
1172    ///
1173    /// The bytes a file's recorded length covers but nothing has written:
1174    /// the gap under a write that starts past the end, and the extension a
1175    /// growing [`truncate`](Self::truncate) publishes. Both would otherwise
1176    /// hand back whatever the last file to own those clusters left behind.
1177    ///
1178    /// The zeros go through a fixed buffer rather than one sized to the
1179    /// range, so a gap of any size costs the same memory. The device sees
1180    /// full-length transfers regardless — [`write_span`](Self::write_span)
1181    /// splits only where the device says it must — so the buffer bounds the
1182    /// allocation and not the transfer.
1183    fn zero_range(&mut self, file: &File, from: u64, to: u64) -> Result<(), D::Error> {
1184        /// Bytes of zeros staged per pass. Large enough that the per-call
1185        /// overhead of re-walking the chain is lost against the transfer,
1186        /// small enough to be an unremarkable transient on a small heap.
1187        const ZERO_CHUNK: usize = 64 * 1024;
1188
1189        if from >= to {
1190            return Ok(());
1191        }
1192        let zeros = vec![0u8; ZERO_CHUNK.min((to - from) as usize)];
1193
1194        let mut at = from;
1195        while at < to {
1196            let take = ((to - at) as usize).min(zeros.len());
1197            self.write_chain(file, at, &zeros[..take])?;
1198            at += take as u64;
1199        }
1200        Ok(())
1201    }
1202
1203    /// Writes `from` starting `skip` bytes into `first_block`.
1204    ///
1205    /// The mirror of the read path's split, with one asymmetry: a partial
1206    /// block has to be read before it is written, because a device only
1207    /// accepts whole blocks and the bytes around the written part have to
1208    /// survive. Whole blocks go straight from the caller's slice.
1209    fn write_span(&mut self, first_block: u64, skip: usize, from: &[u8]) -> Result<(), D::Error> {
1210        let mut block = first_block;
1211        let mut from = from;
1212
1213        if skip != 0 {
1214            let take = (BLOCK_SIZE - skip).min(from.len());
1215            let mut scratch = [0u8; BLOCK_SIZE];
1216            self.read_blocks(block, &mut scratch)?;
1217            scratch[skip..skip + take].copy_from_slice(&from[..take]);
1218            self.write_blocks(block, &scratch)?;
1219            from = &from[take..];
1220            block += 1;
1221        }
1222
1223        let whole = from.len() / BLOCK_SIZE;
1224        if whole != 0 {
1225            let cap = usize::try_from(self.device().max_transfer_blocks())
1226                .unwrap_or(usize::MAX)
1227                .clamp(1, whole);
1228            let (aligned, rest) = from.split_at(whole * BLOCK_SIZE);
1229            for (batch, chunk) in aligned.chunks(cap * BLOCK_SIZE).enumerate() {
1230                self.write_blocks(block + (batch * cap) as u64, chunk)?;
1231            }
1232            block += whole as u64;
1233            from = rest;
1234        }
1235
1236        if !from.is_empty() {
1237            let mut scratch = [0u8; BLOCK_SIZE];
1238            self.read_blocks(block, &mut scratch)?;
1239            scratch[..from.len()].copy_from_slice(from);
1240            self.write_blocks(block, &scratch)?;
1241        }
1242        Ok(())
1243    }
1244}
1245
1246/// Where a directory entry is, and the little `rename` needs to know about
1247/// what it names — copied out of the parsed directory so its borrow ends.
1248#[derive(Debug, Clone, Copy)]
1249struct Placed {
1250    index: u32,
1251    first_slot: u32,
1252    first_cluster: u32,
1253    is_directory: bool,
1254}
1255
1256impl Placed {
1257    fn of(entry: &crate::dir::DirEntry) -> Self {
1258        Placed {
1259            index: entry.index(),
1260            first_slot: entry.first_slot(),
1261            first_cluster: entry.first_cluster(),
1262            is_directory: entry.is_directory(),
1263        }
1264    }
1265}
1266
1267/// Splits a path into its directory and its final component.
1268fn split_path(path: &str) -> (&str, &str) {
1269    match path.rfind('/') {
1270        Some(at) => (&path[..at], &path[at + 1..]),
1271        None => ("", path),
1272    }
1273}