Oregami
Repositories/oxedyne/ore

oxedyne/ore/store/src/verdict.rs

11.4 KiB, 36 runs

created by r2848102244:753, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! What has already been checked here, so that it is not checked again.
2//!
3//! A signature that verified yesterday verifies today, because nothing in an Ore
4//! repository is ever removed and a sealed segment's bytes never move again, so
5//! checking every operation on every command is re-deriving a constant. Measured
6//! on a 44,541 operation history: reading and decoding the whole log costs
7//! 0.34 s, and checking every signature on the way takes it to 0.99 s.
8//!
9//! A verdict is filed under a fold of the segment's record digests: SHA-256 over
10//! `d(0) || ... || d(n-1) || the header`, where `d(i)` is the digest the reader
11//! computes to check record `i` anyway. Those digests cover `[kind] || body` of
12//! every record and a sealed entry's body is its whole envelope, so the fold
13//! names the signer, the signature and the payload of every operation in the
14//! file. One bit anywhere and the fold is a different fold.
15//!
16//! **A file name, a length and a modification time decide whether to GAMBLE, and
17//! never whether something verified.** A segment that looks untouched is read
18//! without its signatures being checked, and the fold taken over that read is put
19//! to [`Verdicts::holds`] before a byte of it is believed. A gamble that loses
20//! costs a second pass and nothing else. Nothing is ever accepted on the strength
21//! of a timestamp.
22//!
23//! The file sits beside `log/` and not in it, and losing it costs one verified
24//! replay. That is what makes it safe, and it is why a file that will not read,
25//! or holds one line this build does not understand, is treated as empty rather
26//! than as an error.
27//!
28//! **It never crosses a wire.** What a peer is owed is the signature; a verdict
29//! is this replica saying it checked one, which a peer would have to take on
30//! trust, and that is the opposite of what a signature is for. Anyone putting one
31//! in a segment, a sync message or a served page is designing a different feature
32//! with a trust decision inside it.
33//!
34//! It is not a security boundary. Whoever can write this file can write `log/`
35//! and `key` too, so it is worth what the directory around it is worth. What it
36//! does buy is that a segment rewritten by anything -- a botched copy, a restored
37//! backup, a repack, a forger -- misses.
38//!
39//! # A verdict goes off
40//!
41//! Each note carries the time it was made, and [`Verdicts::expected`] refuses one
42//! older than the caller's bar. That is what turns a skipped check into a
43//! deferred one.
44//!
45//! The reason is [`oxedyne_fe2o3_ore::segment::Integrity::Vouched`], which reads
46//! a vouched segment without hashing its bodies. The digest was the last thing
47//! catching a body byte that flipped on the disk -- the length and the
48//! modification time do not move, and the fold is over the digests recorded
49//! beside the bodies rather than over the bodies -- so a store read only on
50//! verdicts is a store nothing checks. With an age bar it is a store checked
51//! every [`VERDICT_LIFE`], by whichever comes first: [`crate::sweep`] on a timer,
52//! or the next command, which pays for it and files fresh notes.
53//!
54//! **This is what makes the sweep's own failure visible.** A timer that stopped
55//! six months ago leaves notes that went off five months and three weeks ago, and
56//! every command since has been reading the log the slow, checked way. The
57//! symptom of a sweep nobody is running is cost coming back, which somebody
58//! notices and asks about; it is not a line of output that scrolls past.
59
60use crate::keys::{
61 bytes_of,
62 text_of,
63};
64
65use oxedyne_fe2o3_core::prelude::*;
66
67use std::collections::BTreeMap;
68use std::fs;
69use std::path::{
70 Path,
71 PathBuf,
72};
73
74
75// The file, and what it says about itself
76pub const VERDICT_FILE: &str = "verified";
77pub const VERDICT_FORMAT: &str = "ORECHK 2"; // a later format is left alone, not misread
78
79pub const FOLD_LEN: usize = 32; // a SHA-256 digest
80
81/// How long a verdict is worth acting on, in nanoseconds: seven days.
82///
83/// The thing a verdict now stands in front of is bit rot, which happens on a
84/// timescale of years, so the bar is set by what re-checking costs rather than
85/// by how fast a disk decays. A whole checked replay of the largest history here
86/// -- 35,408 operations in 85 MB -- is under a second, so seven days buys fifty
87/// re-checks a year for about a second of somebody's time in total, and the
88/// window in which a flipped byte could be read and believed is a week rather
89/// than for ever.
90pub const VERDICT_LIFE: u128 = 7 * 24 * 60 * 60 * 1_000_000_000;
91
92
93/// A digest of every record digest in one segment, in order, and its header.
94pub type Fold = [u8; FOLD_LEN];
95
96
97/// What was last read at one segment file.
98#[derive(Clone, Debug, Eq, PartialEq)]
99struct Note {
100 len: u64, // size the file had when it was read
101 modified: u128, // nanoseconds since the epoch, as the filesystem reported them
102 fold: Fold, // what the records in it folded to
103 checked: u128, // wall clock time the read that earned this note finished
104}
105
106
107/// Nanoseconds since the epoch, or zero where the clock will not say.
108///
109/// A clock that will not answer gives the oldest time there is, so every verdict
110/// reads as expired and every segment is checked. Being slow is the safe way to
111/// be wrong about the time.
112pub fn now() -> u128 {
113 match std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH) {
114 Ok(d) => d.as_nanos(),
115 Err(_) => 0,
116 }
117}
118
119
120/// The segments whose signatures have been checked here.
121///
122/// One entry per sealed segment. The tail is never entered, because its bytes
123/// are still growing and a fold over them would name a state that has already
124/// gone.
125#[derive(Clone, Debug, Default, Eq, PartialEq)]
126pub struct Verdicts {
127 held: BTreeMap<String, Note>, // segment file name to what was last read there
128}
129
130impl Verdicts {
131
132 pub fn new() -> Self {
133 Self { held: BTreeMap::new() }
134 }
135
136 pub fn path_of(dir: &Path) -> PathBuf {
137 dir.join(VERDICT_FILE)
138 }
139
140 /// Reads what has been recorded at `dir`, and never fails.
141 ///
142 /// Every way of not being able to read it -- absent, unreadable, a format
143 /// this build does not know, a line that is not four fields, a fold that is
144 /// not thirty-two bytes -- gives the same answer, which is that nothing is
145 /// known. That is the whole of the failure handling this file needs, because
146 /// the only consequence of knowing nothing is verifying what could have been
147 /// skipped. A partial read is refused too: a file half of which parses is a
148 /// file something is wrong with, and half a cache is not worth the question
149 /// of which half.
150 pub fn read(dir: &Path) -> Self {
151 let text = match fs::read_to_string(Self::path_of(dir)) {
152 Ok(t) => t,
153 Err(_) => return Self::new(),
154 };
155 let mut lines = text.lines();
156 match lines.next() {
157 Some(first) if first.trim() == VERDICT_FORMAT => (),
158 _ => return Self::new(),
159 }
160 let mut held = BTreeMap::new();
161 for line in lines {
162 if line.trim().is_empty() {
163 continue;
164 }
165 let field: Vec<&str> = line.split_whitespace().collect();
166 if field.len() != 5 {
167 return Self::new();
168 }
169 let len = match field[1].parse::<u64>() {
170 Ok(n) => n,
171 Err(_) => return Self::new(),
172 };
173 let modified = match field[2].parse::<u128>() {
174 Ok(n) => n,
175 Err(_) => return Self::new(),
176 };
177 let bytes = match bytes_of(field[3]) {
178 Ok(b) => b,
179 Err(_) => return Self::new(),
180 };
181 let mut fold = [0u8; FOLD_LEN];
182 if bytes.len() != FOLD_LEN {
183 return Self::new();
184 }
185 fold.copy_from_slice(&bytes);
186 let checked = match field[4].parse::<u128>() {
187 Ok(n) => n,
188 Err(_) => return Self::new(),
189 };
190 held.insert(fmt!("{}", field[0]), Note { len, modified, fold, checked });
191 }
192 Self { held }
193 }
194
195 /// The fold to expect at a segment file that looks untouched, where a note
196 /// was recorded and is not older than `life`.
197 ///
198 /// **This is a guess and the caller must treat it as one.** It says that a
199 /// file of this name, this length and this modification time folded to this
200 /// once; it does not say that the file on the disk now is that file. What
201 /// makes it safe to act on is that the fold actually computed is put to
202 /// [`Verdicts::holds`] afterwards.
203 ///
204 /// A note from after `at` is a clock that has gone backwards, and it is
205 /// refused for the same reason an old one is: the only judgements this can
206 /// make about time are the ones that cost a check rather than skip one.
207 /// `life` of zero asks what was recorded and nothing about its age, which is
208 /// what [`crate::sweep`] wants when it is about to check the file anyway.
209 ///
210 /// # Arguments
211 ///
212 /// `at` and `life` are nanoseconds, the first since the epoch and the second
213 /// a span; see [`VERDICT_LIFE`].
214 pub fn expected(&self, name: &str, len: u64, modified: u128, at: u128, life: u128)
215 -> Option<Fold>
216 {
217 let note = match self.held.get(name) {
218 Some(note) if note.len == len && note.modified == modified => note,
219 _ => return None,
220 };
221 if life == 0 {
222 return Some(note.fold);
223 }
224 match at.checked_sub(note.checked) {
225 Some(age) if age <= life => Some(note.fold),
226 _ => None,
227 }
228 }
229
230 /// When the note about this segment was made, in nanoseconds since the epoch.
231 pub fn checked(&self, name: &str) -> Option<u128> {
232 self.held.get(name).map(|note| note.checked)
233 }
234
235 /// The oldest note in the file, which is how long ago the whole store was
236 /// last known good.
237 pub fn oldest(&self) -> Option<u128> {
238 self.held.values().map(|note| note.checked).min()
239 }
240
241 /// Forgets what was recorded about one segment, so that the next read of it
242 /// checks every record and every signature.
243 ///
244 /// This is what [`crate::sweep`] does with a segment it found damage in. It
245 /// does not repair anything and is not meant to: it withdraws the licence to
246 /// skip, and the ordinary checked read that follows is what refuses the
247 /// history and names the operation.
248 pub fn forget(&mut self, name: &str) {
249 self.held.remove(name);
250 }
251
252 /// Did every signature over these exact bytes verify here?
253 pub fn holds(&self, fold: &Fold) -> bool {
254 self.held.values().any(|note| note.fold == *fold)
255 }
256
257 /// Says that a segment of this name, length and modification time folded to
258 /// `fold`, that every signature in it verified, and that this happened at
259 /// `at`.
260 pub fn record(&mut self, name: &str, len: u64, modified: u128, fold: Fold, at: u128) {
261 self.held.insert(fmt!("{}", name), Note { len, modified, fold, checked: at });
262 }
263
264 pub fn is_empty(&self) -> bool {
265 self.held.is_empty()
266 }
267
268 /// Writes the verdicts to `dir`, replacing whatever was there.
269 ///
270 /// Written aside and renamed over, because two commands reading one store may
271 /// both reach here and a half-written file is a file the next reader would
272 /// discard. Both writers are right, so the last one wins and nothing is lost
273 /// but a little work.
274 pub fn write(&self, dir: &Path)
275 -> Outcome<()>
276 {
277 let path = Self::path_of(dir);
278 let mut text = fmt!("{}\n", VERDICT_FORMAT);
279 for (name, note) in &self.held {
280 text.push_str(&fmt!("{} {} {} {} {}\n",
281 name, note.len, note.modified, text_of(&note.fold), note.checked));
282 }
283 let aside = path.with_extension("new");
284 match fs::write(&aside, text.as_bytes()) {
285 Ok(()) => (),
286 Err(e) => return Err(err!(e,
287 "The verdicts could not be written aside to {:?}.", aside;
288 IO, File, Write)),
289 }
290 match fs::rename(&aside, &path) {
291 Ok(()) => Ok(()),
292 Err(e) => {
293 let _ = fs::remove_file(&aside);
294 Err(err!(e,
295 "The verdicts written to {:?} could not be moved over {:?}.",
296 aside, path;
297 IO, File, Write))
298 },
299 }
300 }
301}