1use std::ffi::OsString;
6use std::fs::{File, OpenOptions};
7use std::io::{self, Write};
8use std::path::Path;
9
10pub trait Fs: Send + Sync {
12 fn write_new(&self, path: &Path, data: &[u8]) -> io::Result<()>;
15 fn sync_file(&self, path: &Path) -> io::Result<()>;
17 fn rename(&self, from: &Path, to: &Path) -> io::Result<()>;
19 fn sync_dir(&self, dir: &Path) -> io::Result<()>;
22 fn read(&self, path: &Path) -> io::Result<Vec<u8>>;
24 fn remove(&self, path: &Path) -> io::Result<()>;
26 fn list(&self, dir: &Path) -> io::Result<Vec<OsString>>;
28 fn create_dir_all(&self, dir: &Path) -> io::Result<()>;
31 fn remove_dir_all(&self, dir: &Path) -> io::Result<()>;
34}
35
36pub struct OsFs;
40
41impl Fs for OsFs {
42 fn write_new(&self, path: &Path, data: &[u8]) -> io::Result<()> {
43 OpenOptions::new()
44 .write(true)
45 .create_new(true)
46 .open(path)?
47 .write_all(data)
48 }
49
50 fn sync_file(&self, path: &Path) -> io::Result<()> {
51 File::open(path)?.sync_all()
52 }
53
54 fn rename(&self, from: &Path, to: &Path) -> io::Result<()> {
55 std::fs::rename(from, to)
56 }
57
58 fn sync_dir(&self, dir: &Path) -> io::Result<()> {
59 File::open(dir)?.sync_all()
60 }
61
62 fn read(&self, path: &Path) -> io::Result<Vec<u8>> {
63 std::fs::read(path)
64 }
65
66 fn remove(&self, path: &Path) -> io::Result<()> {
67 std::fs::remove_file(path)
68 }
69
70 fn list(&self, dir: &Path) -> io::Result<Vec<OsString>> {
71 let mut names = std::fs::read_dir(dir)?
72 .map(|entry| entry.map(|e| e.file_name()))
73 .collect::<io::Result<Vec<_>>>()?;
74 names.sort();
75 Ok(names)
76 }
77
78 fn create_dir_all(&self, dir: &Path) -> io::Result<()> {
79 std::fs::create_dir_all(dir)
80 }
81
82 fn remove_dir_all(&self, dir: &Path) -> io::Result<()> {
83 std::fs::remove_dir_all(dir)
84 }
85}
86
87#[cfg(test)]
88pub(crate) use crash::{CrashFs, Op};
89
90#[cfg(test)]
91mod crash {
92 use std::collections::BTreeMap;
93 use std::ffi::OsString;
94 use std::io;
95 use std::path::{Path, PathBuf};
96 use std::sync::Mutex;
97
98 use super::Fs;
99
100 #[derive(Debug, Clone, PartialEq, Eq)]
102 pub(crate) enum Op {
103 Write(PathBuf),
104 SyncFile(PathBuf),
105 Rename(PathBuf, PathBuf),
106 SyncDir(PathBuf),
107 Remove(PathBuf),
108 CreateDir(PathBuf),
109 RemoveDir(PathBuf),
110 }
111
112 pub(crate) struct CrashFs {
125 state: Mutex<State>,
126 }
127
128 struct State {
129 root: PathBuf,
130 dirs: BTreeMap<PathBuf, Dir>,
131 files: Vec<File>,
132 log: Vec<Op>,
133 fail_from: Option<usize>,
135 }
136
137 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
138 enum Entry {
139 File(usize),
141 Dir,
142 }
143
144 #[derive(Default)]
146 struct Dir {
147 now: BTreeMap<OsString, Entry>,
148 synced: BTreeMap<OsString, Entry>,
149 }
150
151 struct File {
152 now: Vec<u8>,
153 synced: Vec<u8>,
154 }
155
156 fn not_found() -> io::Error {
157 io::Error::from(io::ErrorKind::NotFound)
158 }
159
160 fn split(path: &Path) -> io::Result<(PathBuf, OsString)> {
162 match (path.parent(), path.file_name()) {
163 (Some(dir), Some(name)) => Ok((dir.to_owned(), name.to_owned())),
164 _ => Err(io::Error::from(io::ErrorKind::InvalidInput)),
165 }
166 }
167
168 impl State {
169 fn alive(&self) -> io::Result<()> {
171 match self.fail_from {
172 Some(n) if self.log.len() >= n => Err(io::Error::other("the process has died")),
173 _ => Ok(()),
174 }
175 }
176
177 fn exists(&self, dir: &Path) -> bool {
180 if dir == self.root {
181 return true;
182 }
183 let Ok((parent, name)) = split(dir) else {
184 return false;
185 };
186 self.exists(&parent)
187 && self
188 .dirs
189 .get(&parent)
190 .is_some_and(|p| p.now.get(&name) == Some(&Entry::Dir))
191 }
192
193 fn dir(&mut self, dir: &Path) -> io::Result<&mut Dir> {
194 if !self.exists(dir) {
195 return Err(not_found());
196 }
197 self.dirs.get_mut(dir).ok_or_else(not_found)
198 }
199
200 fn file(&mut self, path: &Path) -> io::Result<usize> {
201 let (dir, name) = split(path)?;
202 match self.dir(&dir)?.now.get(&name) {
203 Some(Entry::File(index)) => Ok(*index),
204 _ => Err(not_found()),
205 }
206 }
207 }
208
209 impl CrashFs {
210 pub(crate) fn new(root: &Path) -> CrashFs {
212 CrashFs {
213 state: Mutex::new(State {
214 root: root.to_owned(),
215 dirs: BTreeMap::from([(root.to_owned(), Dir::default())]),
216 files: Vec::new(),
217 log: Vec::new(),
218 fail_from: None,
219 }),
220 }
221 }
222
223 fn state(&self) -> std::sync::MutexGuard<'_, State> {
224 self.state
225 .lock()
226 .expect("no test panicked holding the lock")
227 }
228
229 pub(crate) fn crash(&self) {
231 let mut state = self.state();
232 state.fail_from = None;
233 for dir in state.dirs.values_mut() {
234 dir.now = dir.synced.clone();
235 }
236 for file in &mut state.files {
237 file.now = file.synced.clone();
238 }
239 }
240
241 pub(crate) fn fail_from(&self, n: usize) {
245 self.state().fail_from = Some(n);
246 }
247
248 pub(crate) fn log(&self) -> Vec<Op> {
250 self.state().log.clone()
251 }
252 }
253
254 impl Fs for CrashFs {
255 fn write_new(&self, path: &Path, data: &[u8]) -> io::Result<()> {
256 let (dir, name) = split(path)?;
257 let mut state = self.state();
258 state.alive()?;
259 let index = state.files.len();
260 let entries = &mut state.dir(&dir)?.now;
261 if entries.contains_key(&name) {
262 return Err(io::Error::from(io::ErrorKind::AlreadyExists));
263 }
264 entries.insert(name, Entry::File(index));
265 state.files.push(File {
266 now: data.to_vec(),
267 synced: Vec::new(),
268 });
269 state.log.push(Op::Write(path.to_owned()));
270 Ok(())
271 }
272
273 fn sync_file(&self, path: &Path) -> io::Result<()> {
274 let mut state = self.state();
275 state.alive()?;
276 let index = state.file(path)?;
277 let file = &mut state.files[index];
278 file.synced = file.now.clone();
279 state.log.push(Op::SyncFile(path.to_owned()));
280 Ok(())
281 }
282
283 fn rename(&self, from: &Path, to: &Path) -> io::Result<()> {
284 let ((from_dir, from_name), (to_dir, to_name)) = (split(from)?, split(to)?);
285 let mut state = self.state();
286 state.alive()?;
287 let index = state.file(from)?;
288 state.dir(&to_dir)?;
289 state.dir(&from_dir)?.now.remove(&from_name);
290 state.dir(&to_dir)?.now.insert(to_name, Entry::File(index));
291 state.log.push(Op::Rename(from.to_owned(), to.to_owned()));
292 Ok(())
293 }
294
295 fn sync_dir(&self, dir: &Path) -> io::Result<()> {
296 let mut state = self.state();
297 state.alive()?;
298 let entries = state.dir(dir)?;
299 entries.synced = entries.now.clone();
300 state.log.push(Op::SyncDir(dir.to_owned()));
301 Ok(())
302 }
303
304 fn read(&self, path: &Path) -> io::Result<Vec<u8>> {
305 let mut state = self.state();
306 let index = state.file(path)?;
307 Ok(state.files[index].now.clone())
308 }
309
310 fn remove(&self, path: &Path) -> io::Result<()> {
311 let (dir, name) = split(path)?;
312 let mut state = self.state();
313 state.alive()?;
314 state.file(path)?;
315 state.dir(&dir)?.now.remove(&name);
316 state.log.push(Op::Remove(path.to_owned()));
317 Ok(())
318 }
319
320 fn list(&self, dir: &Path) -> io::Result<Vec<OsString>> {
321 Ok(self.state().dir(dir)?.now.keys().cloned().collect())
322 }
323
324 fn create_dir_all(&self, dir: &Path) -> io::Result<()> {
325 let mut state = self.state();
326 state.alive()?;
327 let below = dir
328 .strip_prefix(&state.root)
329 .map_err(|_| io::Error::from(io::ErrorKind::InvalidInput))?
330 .to_owned();
331 let mut path = state.root.clone();
334 let mut missing = Vec::new();
335 for part in &below {
336 let next = path.join(part);
337 let parent = std::mem::replace(&mut path, next);
338 if !missing.is_empty() {
339 missing.push(path.clone());
340 continue;
341 }
342 match state.dir(&parent)?.now.get(part) {
343 Some(Entry::Dir) => {}
344 Some(Entry::File(_)) => {
345 return Err(io::Error::from(io::ErrorKind::AlreadyExists));
346 }
347 None => missing.push(path.clone()),
348 }
349 }
350 if missing.is_empty() {
351 return Ok(());
352 }
353 std::fs::create_dir_all(dir)?;
354 for path in missing {
355 let (parent, name) = split(&path)?;
356 state.dir(&parent)?.now.insert(name, Entry::Dir);
357 state.dirs.insert(path, Dir::default());
358 }
359 state.log.push(Op::CreateDir(dir.to_owned()));
360 Ok(())
361 }
362
363 fn remove_dir_all(&self, dir: &Path) -> io::Result<()> {
364 let (parent, name) = split(dir)?;
365 let mut state = self.state();
366 state.alive()?;
367 if !state.exists(dir) {
368 return Err(not_found());
369 }
370 state.dir(&parent)?.now.remove(&name);
371 state.log.push(Op::RemoveDir(dir.to_owned()));
372 Ok(())
373 }
374 }
375}
376
377#[cfg(test)]
378mod tests {
379 use std::io::ErrorKind::{AlreadyExists, NotFound};
380 use std::path::PathBuf;
381
382 use super::*;
383
384 fn behaves_like_a_filesystem(fs: &dyn Fs, root: &Path) {
386 let dir = root.join("objects");
387 let (a, b) = (dir.join("a"), dir.join("b"));
388 assert_eq!(
389 fs.write_new(&a, b"x").map_err(|e| e.kind()),
390 Err(NotFound),
391 "no dir yet"
392 );
393 fs.create_dir_all(&dir).expect("create the dir");
394 fs.create_dir_all(&dir).expect("create it again");
395 fs.write_new(&a, b"one").expect("write");
396 assert_eq!(
397 fs.write_new(&a, b"two").map_err(|e| e.kind()),
398 Err(AlreadyExists)
399 );
400 assert!(fs.create_dir_all(&a).is_err(), "a file has the name");
401 assert!(
402 fs.create_dir_all(&a.join("d")).is_err(),
403 "a file stands in the way"
404 );
405 assert!(!a.join("d").exists(), "and nothing is made on disk");
406 assert_eq!(fs.read(&a).expect("read"), b"one");
407 fs.sync_file(&a).expect("sync the file");
408 fs.sync_dir(&dir).expect("sync the dir");
409 fs.rename(&a, &b).expect("rename");
410 assert_eq!(fs.read(&a).map_err(|e| e.kind()), Err(NotFound));
411 assert_eq!(fs.read(&b).expect("read"), b"one");
412 fs.rename(&b, &b).expect("rename onto itself");
413 assert_eq!(fs.read(&b).expect("read"), b"one");
414 fs.write_new(&a, b"three").expect("write again");
415 fs.rename(&a, &b).expect("rename over");
416 assert_eq!(fs.read(&b).expect("read"), b"three");
417 fs.write_new(&a, b"four").expect("write");
418 fs.create_dir_all(&dir.join("c"))
419 .expect("a directory inside");
420 assert_eq!(
421 fs.list(&dir).expect("list"),
422 ["a", "b", "c"].map(OsString::from),
423 "files and directories, sorted"
424 );
425 assert_eq!(
426 fs.write_new(&dir.join("c"), b"x").map_err(|e| e.kind()),
427 Err(AlreadyExists),
428 "a directory's name is taken"
429 );
430 assert!(
431 fs.remove(&dir.join("c")).is_err(),
432 "remove takes only a file"
433 );
434 assert!(
435 fs.remove_dir_all(&a).is_err(),
436 "remove_dir_all takes only a directory"
437 );
438 fs.create_dir_all(&dir.join("c/d"))
439 .expect("a directory inside c");
440 fs.write_new(&dir.join("c/f"), b"x")
441 .expect("a file inside c");
442 fs.remove_dir_all(&dir.join("c"))
443 .expect("remove c and all in it");
444 assert_eq!(fs.list(&dir.join("c")).map_err(|e| e.kind()), Err(NotFound));
445 assert_eq!(
446 fs.remove_dir_all(&dir.join("c")).map_err(|e| e.kind()),
447 Err(NotFound)
448 );
449 fs.create_dir_all(&dir.join("c")).expect("c again");
450 fs.remove(&a).expect("remove");
451 fs.remove(&b).expect("remove");
452 assert_eq!(fs.list(&dir).expect("list"), [OsString::from("c")]);
453 assert_eq!(fs.remove(&b).map_err(|e| e.kind()), Err(NotFound));
454 assert_eq!(fs.sync_file(&b).map_err(|e| e.kind()), Err(NotFound));
455 assert_eq!(
456 fs.sync_dir(&root.join("none")).map_err(|e| e.kind()),
457 Err(NotFound)
458 );
459 assert_eq!(
460 fs.list(&root.join("none")).map_err(|e| e.kind()),
461 Err(NotFound)
462 );
463 }
464
465 #[test]
466 fn the_os_filesystem_behaves_like_a_filesystem() {
467 let root = tempfile::tempdir().expect("temp dir");
468 behaves_like_a_filesystem(&OsFs, root.path());
469 }
470
471 #[test]
472 fn the_crash_filesystem_behaves_like_a_filesystem() {
473 let root = tempfile::tempdir().expect("temp dir");
474 behaves_like_a_filesystem(&CrashFs::new(root.path()), root.path());
475 }
476
477 struct Model {
479 root: tempfile::TempDir,
480 fs: CrashFs,
481 }
482
483 impl Model {
484 fn new() -> Model {
485 let root = tempfile::tempdir().expect("temp dir");
486 let fs = CrashFs::new(root.path());
487 Model { root, fs }
488 }
489
490 fn root(&self) -> &Path {
491 self.root.path()
492 }
493
494 fn dir(&self) -> PathBuf {
496 self.root().join("objects")
497 }
498
499 fn f(&self) -> PathBuf {
500 self.dir().join("f")
501 }
502 }
503
504 fn after(steps: impl FnOnce(&CrashFs, &Path)) -> Model {
506 let m = Model::new();
507 m.fs.create_dir_all(&m.dir()).expect("create the dir");
508 m.fs.sync_dir(m.root()).expect("sync the root");
509 steps(&m.fs, &m.f());
510 m
511 }
512
513 fn synced(fs: &CrashFs, f: &Path) {
514 fs.write_new(f, b"data").expect("write");
515 fs.sync_file(f).expect("sync the file");
516 fs.sync_dir(f.parent().expect("a dir"))
517 .expect("sync the dir");
518 }
519
520 #[test]
521 fn a_crash_drops_a_file_whose_entry_was_not_synced() {
522 for sync_data in [false, true] {
523 let m = after(|fs, f| {
524 fs.write_new(f, b"data").expect("write");
525 if sync_data {
526 fs.sync_file(f).expect("sync the file");
527 }
528 });
529 m.fs.crash();
530 assert_eq!(m.fs.read(&m.f()).map_err(|e| e.kind()), Err(NotFound));
531 }
532 }
533
534 #[test]
535 fn a_crash_empties_a_file_whose_data_was_not_synced() {
536 let m = after(|fs, f| {
537 fs.write_new(f, b"data").expect("write");
538 fs.sync_dir(f.parent().expect("a dir"))
539 .expect("sync the dir");
540 });
541 m.fs.crash();
542 assert_eq!(m.fs.read(&m.f()).expect("the entry survives"), b"");
543 }
544
545 #[test]
546 fn a_crash_keeps_a_file_synced_in_both_ways() {
547 let m = after(synced);
548 m.fs.crash();
549 assert_eq!(m.fs.read(&m.f()).expect("survives"), b"data");
550 }
551
552 #[test]
553 fn a_rename_or_remove_survives_a_crash_only_once_the_dir_is_synced() {
554 for sync in [false, true] {
555 let renamed = after(|fs, f| {
556 synced(fs, f);
557 fs.rename(f, &f.with_file_name("g")).expect("rename");
558 if sync {
559 fs.sync_dir(f.parent().expect("a dir"))
560 .expect("sync the dir");
561 }
562 });
563 renamed.fs.crash();
564 let names = if sync { ["g"] } else { ["f"] };
565 assert_eq!(
566 renamed.fs.list(&renamed.dir()).expect("list"),
567 names.map(OsString::from),
568 "rename, sync {sync}"
569 );
570 assert_eq!(
571 renamed
572 .fs
573 .read(&renamed.dir().join(names[0]))
574 .expect("read"),
575 b"data"
576 );
577
578 let removed = after(|fs, f| {
579 synced(fs, f);
580 fs.remove(f).expect("remove");
581 if sync {
582 fs.sync_dir(f.parent().expect("a dir"))
583 .expect("sync the dir");
584 }
585 });
586 removed.fs.crash();
587 let left = removed.fs.list(&removed.dir()).expect("list").len();
588 assert_eq!(left, usize::from(!sync), "remove, sync {sync}");
589 }
590 }
591
592 #[test]
593 fn a_new_directory_survives_a_crash_only_once_its_parent_is_synced() {
594 let m = Model::new();
595 let (a, b) = (m.root().join("a"), m.root().join("a/b"));
596 m.fs.create_dir_all(&b).expect("create a/b");
597 m.fs.crash();
598 assert_eq!(m.fs.list(m.root()).expect("list"), Vec::<OsString>::new());
599 assert_eq!(m.fs.list(&a).map_err(|e| e.kind()), Err(NotFound));
600
601 m.fs.create_dir_all(&b).expect("create a/b");
602 m.fs.sync_dir(&a).expect("sync a, not the root");
603 m.fs.crash();
604 assert_eq!(
605 m.fs.list(&b).map_err(|e| e.kind()),
606 Err(NotFound),
607 "b is lost with a"
608 );
609
610 m.fs.create_dir_all(&b).expect("create a/b");
611 m.fs.sync_dir(m.root()).expect("sync the root");
612 m.fs.crash();
613 assert_eq!(m.fs.list(m.root()).expect("list"), [OsString::from("a")]);
614 assert_eq!(
615 m.fs.list(&a).expect("a survives"),
616 Vec::<OsString>::new(),
617 "b's entry in a was never synced"
618 );
619
620 m.fs.create_dir_all(&b).expect("create b");
621 m.fs.sync_dir(&a).expect("sync a");
622 m.fs.crash();
623 assert_eq!(m.fs.list(&b).expect("b survives"), Vec::<OsString>::new());
624 }
625
626 #[test]
627 fn a_lost_directory_takes_its_synced_files_with_it() {
628 let m = Model::new();
629 let a = m.root().join("a");
630 m.fs.create_dir_all(&a).expect("create a");
631 synced(&m.fs, &a.join("f"));
632 m.fs.crash();
633 assert_eq!(m.fs.list(m.root()).expect("list"), Vec::<OsString>::new());
634 m.fs.create_dir_all(&a).expect("create a again");
635 assert_eq!(
636 m.fs.list(&a).expect("list"),
637 Vec::<OsString>::new(),
638 "a new directory starts empty"
639 );
640 }
641
642 #[test]
643 fn a_directory_removal_survives_a_crash_only_once_its_parent_is_synced() {
644 for sync in [false, true] {
645 let m = Model::new();
646 let a = m.root().join("a");
647 m.fs.create_dir_all(&a).expect("create a");
648 synced(&m.fs, &a.join("f"));
649 m.fs.sync_dir(m.root()).expect("sync the root");
650 m.fs.remove_dir_all(&a).expect("remove a");
651 if sync {
652 m.fs.sync_dir(m.root()).expect("sync the root");
653 }
654 m.fs.crash();
655 if sync {
656 assert_eq!(m.fs.list(&a).map_err(|e| e.kind()), Err(NotFound));
657 } else {
658 assert_eq!(m.fs.read(&a.join("f")).expect("back"), b"data");
659 }
660 }
661 }
662
663 #[test]
666 fn a_directory_is_removed_only_from_the_model() {
667 let m = Model::new();
668 let a = m.root().join("a");
669 m.fs.create_dir_all(&a).expect("create a");
670 m.fs.remove_dir_all(&a).expect("remove a");
671 assert!(a.is_dir());
672 }
673
674 #[test]
677 fn a_directory_is_also_made_on_disk() {
678 let m = Model::new();
679 let b = m.root().join("a/b");
680 m.fs.create_dir_all(&b).expect("create a/b");
681 assert!(b.is_dir());
682 }
683
684 #[test]
685 fn nothing_outside_the_root_can_be_made() {
686 let m = Model::new();
687 let outside = m.root().with_file_name("elsewhere-5c1e");
688 assert!(m.fs.create_dir_all(&outside).is_err());
689 assert!(!outside.exists());
690 }
691
692 #[test]
693 fn every_call_that_changes_state_is_logged_in_order() {
694 let m = Model::new();
695 let (dir, f, g) = (m.dir(), m.f(), m.dir().join("g"));
696 m.fs.create_dir_all(&dir).expect("create the dir");
697 m.fs.create_dir_all(&dir).expect("already there: no change");
698 synced(&m.fs, &f);
699 m.fs.rename(&f, &g).expect("rename");
700 m.fs.remove(&g).expect("remove");
701 m.fs.remove_dir_all(&dir).expect("remove the dir");
702 assert_eq!(
703 m.fs.log(),
704 [
705 Op::CreateDir(dir.clone()),
706 Op::Write(f.clone()),
707 Op::SyncFile(f.clone()),
708 Op::SyncDir(dir.clone()),
709 Op::Rename(f, g.clone()),
710 Op::Remove(g),
711 Op::RemoveDir(dir),
712 ]
713 );
714 }
715
716 #[test]
717 fn from_the_fail_point_on_no_change_happens_until_a_crash() {
718 let m = after(|fs, f| fs.write_new(f, b"data").expect("write"));
719 let ops = m.fs.log().len();
720 m.fs.fail_from(ops);
721 let (f, g) = (m.f(), m.dir().join("g"));
722 assert!(m.fs.sync_file(&f).is_err(), "sync");
723 assert!(m.fs.write_new(&g, b"x").is_err(), "write");
724 assert!(m.fs.rename(&f, &g).is_err(), "rename");
725 assert!(m.fs.sync_dir(&m.dir()).is_err(), "sync dir");
726 assert!(m.fs.remove(&f).is_err(), "remove");
727 assert!(
728 m.fs.create_dir_all(&m.dir().join("d")).is_err(),
729 "create dir"
730 );
731 assert!(m.fs.remove_dir_all(&m.dir()).is_err(), "remove dir");
732 assert!(!m.dir().join("d").exists(), "not made on disk either");
733 assert_eq!(m.fs.log().len(), ops, "nothing changed");
734 assert_eq!(m.fs.read(&f).expect("reads still work"), b"data");
735 m.fs.crash();
736 m.fs.write_new(&g, b"x")
737 .expect("works again after the crash");
738 }
739}