shuyi_ui/storage/
power_cut.rs

1//! The power-cut suite (ticket 3045): what "a save survives a power cut"
2//! means, for every backend's [`Storage`]. A backend fakes its medium (a
3//! folder of files, a flash chip) in a [`PowerCutRig`] that can lose the
4//! power after any operation, and runs [`power_cut_suite`] over it.
5
6use super::{Storage, StorageError};
7use crate::prelude::*;
8
9/// A [`Storage`] over a fake of its medium, which can lose the power: what
10/// a backend writes to run [`power_cut_suite`].
11pub trait PowerCutRig {
12    /// The storage as the game sees it.
13    fn storage(&mut self) -> &mut dyn Storage;
14    /// The power goes after `ops` more operations on the medium (a file
15    /// written, renamed or removed, a folder synced; a flash sector
16    /// erased), and every operation after that fails.
17    fn cut_after(&mut self, ops: u32);
18    /// The power comes back. The medium keeps only what it had made
19    /// durable, the storage is opened again over it, as at the game's next
20    /// start, and no cut is pending.
21    fn restart(&mut self);
22}
23
24/// The key the operations run on.
25const KEY: &str = "save-slot-1";
26/// Another key, written once at the start.
27const OTHER: &str = "settings";
28const OTHER_VALUE: &str = "(volume: 80)";
29/// The value before the operation. [`NEW`] is longer, so a torn write shows
30/// as a prefix of it.
31const OLD: &str = "(slot: 1, gold: 10)";
32const NEW: &str = "(slot: 1, gold: 250, items: [lamp, rope, map])";
33/// What the suite writes with the power on, after each cut.
34const AFTER: &str = "(slot: 1, gold: 0)";
35/// The most operations of the medium a write or a delete may take.
36const MAX_OPS: u32 = 10_000;
37
38// check-text: not player text (the suite's panics)
39const PROMISES: [&str; 7] = [
40    "a write over an old value reads the old value or the new one",
41    "a first write reads nothing or the new value",
42    "a delete reads the old value or nothing",
43    "a write or delete that returned Ok reads its result after the restart",
44    "another key reads the same after every restart",
45    "list() names exactly the keys that read Some",
46    "with the power on, a write after the cut works and reads back",
47];
48
49/// One of the operations the suite cuts the power in.
50#[derive(Debug, Clone, Copy)]
51enum Op {
52    Overwrite,
53    FirstWrite,
54    Delete,
55}
56
57impl Op {
58    // check-text: not player text (the suite's panics)
59    fn name(self) -> &'static str {
60        match self {
61            Self::Overwrite => "a write over an old value",
62            Self::FirstWrite => "a first write",
63            Self::Delete => "a delete",
64        }
65    }
66
67    /// The promise (1 to 3) of what the key reads after a cut in it.
68    fn promise(self) -> usize {
69        match self {
70            Self::Overwrite => 1,
71            Self::FirstWrite => 2,
72            Self::Delete => 3,
73        }
74    }
75
76    /// What the key holds before the operation.
77    fn before(self) -> Option<&'static str> {
78        match self {
79            Self::Overwrite | Self::Delete => Some(OLD),
80            Self::FirstWrite => None,
81        }
82    }
83
84    /// What the key holds once the operation is done.
85    fn after(self) -> Option<&'static str> {
86        match self {
87            Self::Overwrite | Self::FirstWrite => Some(NEW),
88            Self::Delete => None,
89        }
90    }
91
92    fn run(self, storage: &mut dyn Storage) -> Result<(), StorageError> {
93        match self.after() {
94            Some(value) => storage.write(KEY, value),
95            None => storage.delete(KEY),
96        }
97    }
98}
99
100/// Cuts the power in a write over an old value, a first write and a
101/// delete, after each number of operations of the medium in turn, until
102/// the operation finishes, and checks what the storage reads after each
103/// restart. Panics with the promise broken, the operation and the cut.
104///
105/// The promises:
106/// 1. a write over an old value reads the old value or the new one: never
107///    `None`, a mix or an error;
108/// 2. a first write reads `None` or the new value;
109/// 3. a delete reads the old value or `None`;
110/// 4. a write or delete that returned `Ok` reads its result after the
111///    restart (the restart is a power cut too);
112/// 5. another key, written once at the start, reads the same after every
113///    restart;
114/// 6. `list()` names exactly the keys that read `Some`;
115/// 7. with the power on, a write after the cut works and reads back.
116///
117/// An operation that needs more than 10 000 operations of the medium fails
118/// the suite.
119pub fn power_cut_suite(rig: &mut dyn PowerCutRig) {
120    rig.restart();
121    if let Err(e) = rig.storage().write(OTHER, OTHER_VALUE) {
122        fail(5, None, &format!("writing {OTHER} failed: {e}"));
123    }
124    for op in [Op::Overwrite, Op::FirstWrite, Op::Delete] {
125        check_op(rig, op);
126    }
127}
128
129fn check_op(rig: &mut dyn PowerCutRig, op: Op) {
130    for ops in 0..=MAX_OPS {
131        let cut = Some((op, ops));
132        let set_back = match op.before() {
133            Some(value) => rig.storage().write(KEY, value),
134            None => rig.storage().delete(KEY),
135        };
136        if let Err(e) = set_back {
137            fail(7, cut, &format!("setting {KEY} back failed: {e}"));
138        }
139        rig.restart();
140        expect_read(rig, KEY, op.before(), 4, cut, " set back with the power on");
141
142        rig.cut_after(ops);
143        let result = op.run(rig.storage());
144        rig.restart();
145
146        let read = rig.storage().read(KEY);
147        if !matches!(&read, Ok(value) if *value == op.before().map(ToOwned::to_owned)
148            || *value == op.after().map(ToOwned::to_owned))
149        {
150            fail(op.promise(), cut, &format!("{KEY} read {read:?}"));
151        }
152        if result.is_ok() {
153            expect_read(rig, KEY, op.after(), 4, cut, " after an Ok");
154        }
155        expect_read(rig, OTHER, Some(OTHER_VALUE), 5, cut, "");
156        check_list(rig, cut);
157
158        if let Err(e) = rig.storage().write(KEY, AFTER) {
159            fail(7, cut, &format!("the write failed: {e}"));
160        }
161        expect_read(rig, KEY, Some(AFTER), 7, cut, "");
162
163        if result.is_ok() {
164            return;
165        }
166    }
167    // check-text: not player text (the suite's panics)
168    panic!(
169        "power-cut suite: {} still fails after {MAX_OPS} operations of the medium",
170        op.name()
171    );
172}
173
174fn expect_read(
175    rig: &mut dyn PowerCutRig,
176    key: &str,
177    expected: Option<&str>,
178    promise: usize,
179    cut: Option<(Op, u32)>,
180    when: &str,
181) {
182    let read = rig.storage().read(key);
183    if read != Ok(expected.map(ToOwned::to_owned)) {
184        fail(
185            promise,
186            cut,
187            &format!("{key}{when} read {read:?}, not {expected:?}"),
188        );
189    }
190}
191
192fn check_list(rig: &mut dyn PowerCutRig, cut: Option<(Op, u32)>) {
193    let storage = rig.storage();
194    let mut reading = Vec::new();
195    for key in [KEY, OTHER] {
196        if matches!(storage.read(key), Ok(Some(_))) {
197            reading.push(key.to_owned());
198        }
199    }
200    let mut listed = match storage.list() {
201        Ok(keys) => keys,
202        Err(e) => fail(6, cut, &format!("list() failed: {e}")),
203    };
204    listed.sort();
205    if listed != reading {
206        fail(
207            6,
208            cut,
209            &format!("list() named {listed:?}, but the keys that read are {reading:?}"),
210        );
211    }
212}
213
214// check-text: not player text (the suite's panics)
215fn fail(promise: usize, cut: Option<(Op, u32)>, what: &str) -> ! {
216    let text = PROMISES[promise - 1];
217    match cut {
218        Some((op, ops)) => panic!(
219            "power-cut suite, promise {promise} ({text}): {}, power cut after {ops} operations: {what}",
220            op.name()
221        ),
222        None => panic!("power-cut suite, promise {promise} ({text}): {what}"),
223    }
224}
225
226#[cfg(test)]
227mod tests {
228    use super::*;
229    use alloc::collections::BTreeMap;
230
231    /// How [`MemoryRig`] writes.
232    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
233    enum Mode {
234        /// A write is one operation, durable at once.
235        Atomic,
236        /// A write empties the value, then sets it, and a delete empties
237        /// it, then removes it: two operations each.
238        InPlace,
239        /// A write returns `Ok`, but the restart loses it.
240        Forgetful,
241        /// Atomic, but `list()` names no key.
242        Unlisted,
243    }
244
245    /// A rig over a map, which is its own storage.
246    #[derive(Debug)]
247    struct MemoryRig {
248        mode: Mode,
249        values: BTreeMap<String, String>,
250        durable: BTreeMap<String, String>,
251        ops_left: Option<u32>,
252        /// Every write (`Some`) and delete (`None`) the suite asked for.
253        asked: Vec<(String, Option<String>)>,
254    }
255
256    impl MemoryRig {
257        fn new(mode: Mode) -> Self {
258            Self {
259                mode,
260                values: BTreeMap::new(),
261                durable: BTreeMap::new(),
262                ops_left: None,
263                asked: Vec::new(),
264            }
265        }
266
267        /// One operation of the medium: fails once the power is off.
268        fn op(&mut self) -> Result<(), StorageError> {
269            match self.ops_left {
270                Some(0) => Err(StorageError::Backend("the power is off".to_owned())),
271                Some(left) => {
272                    self.ops_left = Some(left - 1);
273                    Ok(())
274                }
275                None => Ok(()),
276            }
277        }
278
279        fn set(&mut self, key: &str, value: &str) -> Result<(), StorageError> {
280            self.op()?;
281            self.values.insert(key.to_owned(), value.to_owned());
282            if self.mode != Mode::Forgetful {
283                self.durable.insert(key.to_owned(), value.to_owned());
284            }
285            Ok(())
286        }
287    }
288
289    impl Storage for MemoryRig {
290        fn read(&self, key: &str) -> Result<Option<String>, StorageError> {
291            Ok(self.values.get(key).cloned())
292        }
293
294        fn write(&mut self, key: &str, value: &str) -> Result<(), StorageError> {
295            self.asked.push((key.to_owned(), Some(value.to_owned())));
296            if self.mode == Mode::InPlace {
297                self.set(key, "")?;
298            }
299            self.set(key, value)
300        }
301
302        fn delete(&mut self, key: &str) -> Result<(), StorageError> {
303            self.asked.push((key.to_owned(), None));
304            if self.mode == Mode::InPlace {
305                self.set(key, "")?;
306            }
307            self.op()?;
308            self.values.remove(key);
309            self.durable.remove(key);
310            Ok(())
311        }
312
313        fn list(&self) -> Result<Vec<String>, StorageError> {
314            if self.mode == Mode::Unlisted {
315                return Ok(Vec::new());
316            }
317            Ok(self.values.keys().cloned().collect())
318        }
319    }
320
321    impl PowerCutRig for MemoryRig {
322        fn storage(&mut self) -> &mut dyn Storage {
323            self
324        }
325
326        fn cut_after(&mut self, ops: u32) {
327            self.ops_left = Some(ops);
328        }
329
330        fn restart(&mut self) {
331            self.values = self.durable.clone();
332            self.ops_left = None;
333        }
334    }
335
336    #[test]
337    fn an_atomic_storage_passes() {
338        power_cut_suite(&mut MemoryRig::new(Mode::Atomic));
339    }
340
341    /// The suite writes the old value and the new one, and deletes, on the
342    /// key it checks.
343    #[test]
344    fn the_suite_writes_the_old_and_the_new_value_and_deletes() {
345        let mut rig = MemoryRig::new(Mode::Atomic);
346        power_cut_suite(&mut rig);
347        for asked in [Some(OLD), Some(NEW), None] {
348            let asked = (KEY.to_owned(), asked.map(ToOwned::to_owned));
349            assert!(rig.asked.contains(&asked), "{asked:?}");
350        }
351    }
352
353    #[test]
354    #[should_panic(
355        expected = "promise 2 (a first write reads nothing or the new value): a first write, power cut after 1 operations"
356    )]
357    fn a_first_write_in_place_fails_promise_2() {
358        let mut rig = MemoryRig::new(Mode::InPlace);
359        rig.write(OTHER, OTHER_VALUE).unwrap();
360        check_op(&mut rig, Op::FirstWrite);
361    }
362
363    #[test]
364    #[should_panic(
365        expected = "promise 3 (a delete reads the old value or nothing): a delete, power cut after 1 operations"
366    )]
367    fn a_delete_in_place_fails_promise_3() {
368        let mut rig = MemoryRig::new(Mode::InPlace);
369        rig.write(OTHER, OTHER_VALUE).unwrap();
370        check_op(&mut rig, Op::Delete);
371    }
372
373    #[test]
374    #[should_panic(expected = "promise 6 (list() names exactly the keys that read Some)")]
375    fn a_storage_that_lists_no_key_fails() {
376        power_cut_suite(&mut MemoryRig::new(Mode::Unlisted));
377    }
378
379    #[test]
380    #[should_panic(
381        expected = "promise 1 (a write over an old value reads the old value or the new one): a write over an old value, power cut after 1 operations"
382    )]
383    fn a_storage_that_writes_in_place_fails() {
384        power_cut_suite(&mut MemoryRig::new(Mode::InPlace));
385    }
386
387    #[test]
388    #[should_panic(
389        expected = "promise 4 (a write or delete that returned Ok reads its result after the restart)"
390    )]
391    fn a_storage_that_forgets_its_writes_fails() {
392        power_cut_suite(&mut MemoryRig::new(Mode::Forgetful));
393    }
394
395    /// A rig whose cut never comes: every write fails, so the suite gives
396    /// up rather than loop for ever.
397    #[test]
398    #[should_panic(expected = "a write over an old value still fails after 10000 operations")]
399    fn an_operation_that_never_finishes_fails() {
400        #[derive(Debug)]
401        struct Failing(MemoryRig);
402        impl Storage for Failing {
403            fn read(&self, key: &str) -> Result<Option<String>, StorageError> {
404                self.0.read(key)
405            }
406            fn write(&mut self, key: &str, value: &str) -> Result<(), StorageError> {
407                if self.0.ops_left.is_some() {
408                    return Err(StorageError::Backend("always".to_owned()));
409                }
410                self.0.write(key, value)
411            }
412            fn delete(&mut self, key: &str) -> Result<(), StorageError> {
413                self.0.delete(key)
414            }
415            fn list(&self) -> Result<Vec<String>, StorageError> {
416                self.0.list()
417            }
418        }
419        impl PowerCutRig for Failing {
420            fn storage(&mut self) -> &mut dyn Storage {
421                self
422            }
423            fn cut_after(&mut self, ops: u32) {
424                self.0.cut_after(ops);
425            }
426            fn restart(&mut self) {
427                self.0.restart();
428            }
429        }
430        power_cut_suite(&mut Failing(MemoryRig::new(Mode::Atomic)));
431    }
432}
shuyi_ui/storage/power_cut.rs

shuyi_ui/storage/
power_cut.rs
