fusee_sim/
disk.rs

1//! A simulated disk.
2//!
3//! Every file has a durable image and a list of writes issued since its last
4//! flush. Reads see both (the page cache). A flush makes the pending writes
5//! durable. A crash resolves each pending write at random: lost, landed in
6//! full, or torn (some sectors landed, possibly with garbage), in no
7//! particular order, which is what a real drive with a volatile cache and an
8//! operating system that reorders writeback can do.
9
10use crate::rng::Rng;
11use std::collections::BTreeMap;
12
13const SECTOR: usize = 512;
14
15#[derive(Clone, Debug, Default)]
16pub struct SimFile {
17    pub durable: Vec<u8>,
18    pending: Vec<(u64, Vec<u8>)>,
19}
20
21fn apply(img: &mut Vec<u8>, off: u64, bytes: &[u8]) {
22    let off = off as usize;
23    if img.len() < off + bytes.len() {
24        img.resize(off + bytes.len(), 0);
25    }
26    img[off..off + bytes.len()].copy_from_slice(bytes);
27}
28
29impl SimFile {
30    pub fn view(&self) -> Vec<u8> {
31        let mut img = self.durable.clone();
32        for (off, b) in &self.pending {
33            apply(&mut img, *off, b);
34        }
35        img
36    }
37
38    pub fn read(&self, off: u64, len: usize) -> Option<Vec<u8>> {
39        let img = self.view();
40        img.get(off as usize..off as usize + len)
41            .map(<[u8]>::to_vec)
42    }
43
44    pub fn write(&mut self, off: u64, bytes: &[u8]) {
45        self.pending.push((off, bytes.to_vec()));
46    }
47
48    pub fn flush(&mut self) {
49        let pending = std::mem::take(&mut self.pending);
50        for (off, b) in pending {
51            apply(&mut self.durable, off, &b);
52        }
53    }
54
55    pub fn has_pending(&self) -> bool {
56        !self.pending.is_empty()
57    }
58
59    pub fn truncate(&mut self, len: u64) {
60        self.flush();
61        self.durable.truncate(len as usize);
62    }
63
64    /// Resolves pending writes as a power loss would.
65    pub fn crash(&mut self, rng: &mut Rng, tear: bool) {
66        let mut pending = std::mem::take(&mut self.pending);
67        // The device may complete writes in any order.
68        rng.shuffle(&mut pending);
69        for (off, b) in pending {
70            match rng.below(100) {
71                0..=34 => {}
72                35..=69 => apply(&mut self.durable, off, &b),
73                _ if !tear => apply(&mut self.durable, off, &b),
74                _ => {
75                    // Torn: a random subset of sectors lands; the first
76                    // missing one may hold garbage.
77                    let sectors = b.len().div_ceil(SECTOR);
78                    for s in 0..sectors {
79                        let lo = s * SECTOR;
80                        let hi = ((s + 1) * SECTOR).min(b.len());
81                        match rng.below(10) {
82                            0..=5 => apply(&mut self.durable, off + lo as u64, &b[lo..hi]),
83                            6 => {
84                                let junk: Vec<u8> =
85                                    (lo..hi).map(|_| rng.below(256) as u8).collect();
86                                apply(&mut self.durable, off + lo as u64, &junk);
87                            }
88                            _ => {}
89                        }
90                    }
91                }
92            }
93        }
94    }
95}
96
97#[derive(Clone, Debug, Default)]
98pub struct SimDisk {
99    pub files: BTreeMap<String, SimFile>,
100}
101
102impl SimDisk {
103    pub fn file(&mut self, name: &str) -> &mut SimFile {
104        self.files.entry(name.to_owned()).or_default()
105    }
106
107    pub fn get(&self, name: &str) -> Option<&SimFile> {
108        self.files.get(name)
109    }
110
111    pub fn remove(&mut self, name: &str) {
112        self.files.remove(name);
113    }
114
115    pub fn names_with_prefix(&self, prefix: &str) -> Vec<String> {
116        self.files
117            .keys()
118            .filter(|k| k.starts_with(prefix))
119            .cloned()
120            .collect()
121    }
122
123    pub fn crash(&mut self, rng: &mut Rng, tear: bool) {
124        for f in self.files.values_mut() {
125            f.crash(rng, tear);
126        }
127    }
128
129    /// Flips one bit in a durable byte of some file whose name starts with
130    /// `prefix` (detectable corruption).
131    pub fn corrupt(&mut self, rng: &mut Rng, prefix: &str) -> Option<(String, usize)> {
132        let names: Vec<String> = self
133            .files
134            .iter()
135            .filter(|(k, f)| k.starts_with(prefix) && f.durable.len() > 4096)
136            .map(|(k, _)| k.clone())
137            .collect();
138        if names.is_empty() {
139            return None;
140        }
141        let name = names[rng.below(names.len() as u64) as usize].clone();
142        let f = self.files.get_mut(&name)?;
143        let used = f.durable.iter().rposition(|b| *b != 0)?;
144        if used <= 4096 {
145            return None;
146        }
147        let at = 4096 + rng.below((used - 4096) as u64) as usize;
148        f.durable[at] ^= 1 << rng.below(8);
149        Some((name, at))
150    }
151}
152
153#[cfg(test)]
154mod tests {
155    use super::*;
156
157    #[test]
158    fn flushed_data_survives_crashes() {
159        let mut rng = Rng::new(7);
160        let mut f = SimFile::default();
161        f.write(0, &[1; 1000]);
162        f.flush();
163        f.write(1000, &[2; 1000]);
164        f.crash(&mut rng, true);
165        assert_eq!(&f.durable[..1000], &[1; 1000][..]);
166    }
167}
fusee_sim/disk.rs

fusee_sim/
disk.rs
