Skip to main content

rustorb_naming/
store.rs

1//! Where the naming service keeps its bindings: the [`Store`] trait, the
2//! in-memory [`MemoryStore`] and the default [`LogStore`] (an append-only
3//! log and checkpoints).
4
5use std::collections::BTreeMap;
6use std::fmt::Write as _;
7use std::fs::{self, File, OpenOptions};
8use std::io::{self, BufWriter, Read, Write};
9use std::path::{Path, PathBuf};
10use std::time::{Duration, Instant};
11
12use rustorb_core::name::{self, NameComponent};
13
14use crate::BindingType;
15
16/// One binding as stored: what it is bound to, and the stringified IOR of
17/// the object or context.
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct StoredBinding {
20    /// Object or context.
21    pub binding_type: BindingType,
22    /// The stringified IOR (`IOR:...`); a nil reference is stored as the
23    /// nil IOR.
24    pub ior: String,
25}
26
27/// The whole state of a naming service: its contexts by id, and the
28/// bindings of each context by name component.
29#[derive(Debug, Clone, Default, PartialEq, Eq)]
30pub struct Snapshot {
31    /// The contexts and their bindings.
32    pub contexts: BTreeMap<String, BTreeMap<NameComponent, StoredBinding>>,
33}
34
35/// One update of a [`Snapshot`].
36#[derive(Debug, Clone, PartialEq, Eq)]
37pub enum Change {
38    /// A context was created (`new_context`, `bind_new_context`).
39    CreateContext(String),
40    /// A context was destroyed.
41    DestroyContext(String),
42    /// A name was bound or rebound in a context.
43    Bind {
44        /// The context id.
45        context: String,
46        /// The name in the context.
47        component: NameComponent,
48        /// What it is bound to.
49        binding: StoredBinding,
50    },
51    /// A name was unbound from a context.
52    Unbind {
53        /// The context id.
54        context: String,
55        /// The name in the context.
56        component: NameComponent,
57    },
58}
59
60impl Snapshot {
61    /// Applies `change`. A change is applied the same way whatever the
62    /// state, so replaying a log over a newer checkpoint gives the same
63    /// result: creating a context that exists keeps its bindings, binding
64    /// in a context that does not exist creates it, and unbinding or
65    /// destroying what does not exist does nothing.
66    pub fn apply(&mut self, change: &Change) {
67        match change {
68            Change::CreateContext(id) => {
69                self.contexts.entry(id.clone()).or_default();
70            }
71            Change::DestroyContext(id) => {
72                self.contexts.remove(id);
73            }
74            Change::Bind {
75                context,
76                component,
77                binding,
78            } => {
79                self.contexts
80                    .entry(context.clone())
81                    .or_default()
82                    .insert(component.clone(), binding.clone());
83            }
84            Change::Unbind { context, component } => {
85                if let Some(bindings) = self.contexts.get_mut(context) {
86                    bindings.remove(component);
87                }
88            }
89        }
90    }
91
92    /// The changes that build this snapshot from an empty one.
93    pub fn changes(&self) -> impl Iterator<Item = Change> + '_ {
94        let creates = self
95            .contexts
96            .keys()
97            .map(|id| Change::CreateContext(id.clone()));
98        let binds = self.contexts.iter().flat_map(|(id, bindings)| {
99            bindings
100                .iter()
101                .map(move |(component, binding)| Change::Bind {
102                    context: id.clone(),
103                    component: component.clone(),
104                    binding: binding.clone(),
105                })
106        });
107        creates.chain(binds)
108    }
109}
110
111/// The storage of a naming service. The service calls
112/// [`record`](Store::record) for every update before it applies it and
113/// replies, and offers a [`checkpoint`](Store::checkpoint) after each
114/// update.
115pub trait Store: Send {
116    /// The state to start from. Called once, before anything else.
117    fn load(&mut self) -> io::Result<Snapshot>;
118
119    /// Records `change`. When this returns, the change must survive a
120    /// crash; an error fails the operation with `PERSIST_STORE`.
121    fn record(&mut self, change: &Change) -> io::Result<()>;
122
123    /// Called after each update with the state that includes it, so that
124    /// the store can write a checkpoint when it sees fit.
125    fn checkpoint(&mut self, state: &Snapshot) -> io::Result<()> {
126        let _ = state;
127        Ok(())
128    }
129}
130
131/// A store that keeps nothing: the service starts empty every time.
132#[derive(Debug, Default)]
133pub struct MemoryStore;
134
135impl Store for MemoryStore {
136    fn load(&mut self) -> io::Result<Snapshot> {
137        Ok(Snapshot::default())
138    }
139
140    fn record(&mut self, _change: &Change) -> io::Result<()> {
141        Ok(())
142    }
143}
144
145/// The first word of the header line of both files.
146const MAGIC: &str = "rustorb-naming";
147/// The format version, the second word of the header line.
148const FORMAT: u32 = 1;
149const CHECKPOINT_FILE: &str = "naming.ckp";
150const LOG_FILE: &str = "naming.log";
151
152/// The default store: every update is appended to a log file and synced
153/// before the service replies, and every so often the whole state is
154/// written as a checkpoint and the log emptied.
155///
156/// The directory holds `naming.ckp`, the last checkpoint, and
157/// `naming.log`, the updates since. Both are text with one record per
158/// line, starting with a header `rustorb-naming 1 GENERATION`:
159///
160/// ```text
161/// rustorb-naming 1 3
162/// context NameService
163/// bind NameService o app.kind IOR:0100...
164/// bind NameService c sub IOR:0100...
165/// unbind NameService app.kind
166/// destroy 5f3a9c0e12ab44d1
167/// ```
168///
169/// A name component is written in the stringified name form
170/// (`id.kind`, with `\` escapes), and `%`, spaces and control characters
171/// in it as `%XX`. A checkpoint ends with an `end` line.
172///
173/// A checkpoint is written to a temporary file, synced and renamed over
174/// `naming.ckp`; then the log is started again with the checkpoint's
175/// generation. At load, a log of an older generation than the checkpoint
176/// (a crash between the two steps) is ignored, and a last line without
177/// its newline (a crash while appending) is dropped.
178#[derive(Debug)]
179pub struct LogStore {
180    dir: PathBuf,
181    generation: u64,
182    log: Option<BufWriter<File>>,
183    records: usize,
184    last_checkpoint: Instant,
185    checkpoint_records: usize,
186    checkpoint_interval: Option<Duration>,
187}
188
189impl LogStore {
190    /// A store in the directory `dir`, created if needed. A checkpoint is
191    /// written every 1000 updates.
192    pub fn new(dir: impl Into<PathBuf>) -> LogStore {
193        LogStore {
194            dir: dir.into(),
195            generation: 0,
196            log: None,
197            records: 0,
198            last_checkpoint: Instant::now(),
199            checkpoint_records: 1000,
200            checkpoint_interval: None,
201        }
202    }
203
204    /// Writes a checkpoint after `records` updates (at least 1).
205    pub fn checkpoint_every(mut self, records: usize) -> LogStore {
206        self.checkpoint_records = records.max(1);
207        self
208    }
209
210    /// Also writes a checkpoint at the first update after `interval` has
211    /// passed since the last one.
212    pub fn checkpoint_interval(mut self, interval: Duration) -> LogStore {
213        self.checkpoint_interval = Some(interval);
214        self
215    }
216
217    /// The directory of the files.
218    pub fn dir(&self) -> &Path {
219        &self.dir
220    }
221
222    fn path(&self, file: &str) -> PathBuf {
223        self.dir.join(file)
224    }
225
226    /// Writes `state` as the checkpoint of the next generation and starts
227    /// an empty log for it.
228    fn write_checkpoint(&mut self, state: &Snapshot) -> io::Result<()> {
229        let generation = self.generation + 1;
230        let tmp = self.path("naming.ckp.tmp");
231        {
232            let mut out = BufWriter::new(File::create(&tmp)?);
233            writeln!(out, "{MAGIC} {FORMAT} {generation}")?;
234            for change in state.changes() {
235                out.write_all(format_change(&change).as_bytes())?;
236            }
237            writeln!(out, "end")?;
238            out.into_inner().map_err(|e| e.into_error())?.sync_all()?;
239        }
240        fs::rename(&tmp, self.path(CHECKPOINT_FILE))?;
241        sync_dir(&self.dir);
242        self.generation = generation;
243        self.start_log()?;
244        self.records = 0;
245        self.last_checkpoint = Instant::now();
246        Ok(())
247    }
248
249    fn start_log(&mut self) -> io::Result<()> {
250        self.log = None;
251        let mut file = File::create(self.path(LOG_FILE))?;
252        writeln!(file, "{MAGIC} {FORMAT} {}", self.generation)?;
253        file.sync_all()?;
254        sync_dir(&self.dir);
255        self.log = Some(BufWriter::new(file));
256        Ok(())
257    }
258}
259
260impl Store for LogStore {
261    fn load(&mut self) -> io::Result<Snapshot> {
262        fs::create_dir_all(&self.dir)?;
263        let mut state = Snapshot::default();
264        let mut generation = 0;
265        if let Some(text) = read_optional(&self.path(CHECKPOINT_FILE))? {
266            let (header, lines) = parse_file(&text, CHECKPOINT_FILE)?;
267            generation = header;
268            let mut ended = false;
269            for (n, line) in lines {
270                if ended {
271                    return Err(bad_data(CHECKPOINT_FILE, n, "record after `end`"));
272                }
273                if line == "end" {
274                    ended = true;
275                    continue;
276                }
277                state.apply(&parse_change(line).ok_or_else(|| bad_record(CHECKPOINT_FILE, n))?);
278            }
279            if !ended {
280                return Err(bad_data(CHECKPOINT_FILE, 0, "no `end` line"));
281            }
282        }
283        let mut replayed = 0;
284        if let Some(text) = read_optional(&self.path(LOG_FILE))? {
285            // A crash while appending leaves a last line without its
286            // newline: that update was never acknowledged.
287            let complete = match text.rfind('\n') {
288                Some(end) => &text[..=end],
289                None => "",
290            };
291            if !complete.is_empty() {
292                let (log_generation, lines) = parse_file(complete, LOG_FILE)?;
293                if log_generation > generation {
294                    return Err(bad_data(LOG_FILE, 1, "newer than the checkpoint"));
295                }
296                if log_generation == generation {
297                    for (n, line) in lines {
298                        state.apply(&parse_change(line).ok_or_else(|| bad_record(LOG_FILE, n))?);
299                        replayed += 1;
300                    }
301                }
302            }
303        }
304        self.generation = generation;
305        if replayed > 0 || generation == 0 {
306            self.write_checkpoint(&state)?;
307        } else {
308            let file = OpenOptions::new()
309                .append(true)
310                .open(self.path(LOG_FILE))
311                .or_else(|_| {
312                    self.start_log()?;
313                    OpenOptions::new().append(true).open(self.path(LOG_FILE))
314                })?;
315            self.log = Some(BufWriter::new(file));
316        }
317        Ok(state)
318    }
319
320    fn record(&mut self, change: &Change) -> io::Result<()> {
321        let log = self
322            .log
323            .as_mut()
324            .ok_or_else(|| io::Error::other("the log store was not loaded"))?;
325        log.write_all(format_change(change).as_bytes())?;
326        log.flush()?;
327        log.get_ref().sync_data()?;
328        self.records += 1;
329        Ok(())
330    }
331
332    fn checkpoint(&mut self, state: &Snapshot) -> io::Result<()> {
333        let due = self.records >= self.checkpoint_records
334            || self
335                .checkpoint_interval
336                .is_some_and(|i| self.records > 0 && self.last_checkpoint.elapsed() >= i);
337        if due {
338            self.write_checkpoint(state)?;
339        }
340        Ok(())
341    }
342}
343
344fn read_optional(path: &Path) -> io::Result<Option<String>> {
345    match File::open(path) {
346        Ok(mut file) => {
347            let mut text = String::new();
348            file.read_to_string(&mut text)?;
349            Ok(Some(text))
350        }
351        Err(e) if e.kind() == io::ErrorKind::NotFound => Ok(None),
352        Err(e) => Err(e),
353    }
354}
355
356/// Makes a rename or a new file in `dir` durable. Not every platform can
357/// open a directory, so failures are ignored.
358fn sync_dir(dir: &Path) {
359    if let Ok(d) = File::open(dir) {
360        let _ = d.sync_all();
361    }
362}
363
364/// The generation in the header, and the numbered lines after it.
365fn parse_file<'a>(
366    text: &'a str,
367    file: &str,
368) -> io::Result<(u64, impl Iterator<Item = (usize, &'a str)>)> {
369    let mut lines = text.lines().enumerate().map(|(i, l)| (i + 1, l));
370    let header = lines.next().map(|(_, l)| l).unwrap_or("");
371    let mut words = header.split(' ');
372    if words.next() != Some(MAGIC) {
373        return Err(bad_data(file, 1, "not a rustorb naming file"));
374    }
375    if words.next() != Some(&FORMAT.to_string()) {
376        return Err(bad_data(file, 1, "unknown format version"));
377    }
378    let generation = words
379        .next()
380        .and_then(|g| g.parse().ok())
381        .ok_or_else(|| bad_data(file, 1, "bad generation"))?;
382    Ok((generation, lines))
383}
384
385fn bad_data(file: &str, line: usize, what: &str) -> io::Error {
386    io::Error::new(io::ErrorKind::InvalidData, format!("{file}:{line}: {what}"))
387}
388
389fn bad_record(file: &str, line: usize) -> io::Error {
390    bad_data(file, line, "malformed record")
391}
392
393/// A change as one line of the log, newline included.
394fn format_change(change: &Change) -> String {
395    match change {
396        Change::CreateContext(id) => format!("context {id}\n"),
397        Change::DestroyContext(id) => format!("destroy {id}\n"),
398        Change::Bind {
399            context,
400            component,
401            binding,
402        } => {
403            let t = match binding.binding_type {
404                BindingType::Object => 'o',
405                BindingType::Context => 'c',
406            };
407            format!(
408                "bind {context} {t} {} {}\n",
409                format_component(component),
410                binding.ior
411            )
412        }
413        Change::Unbind { context, component } => {
414            format!("unbind {context} {}\n", format_component(component))
415        }
416    }
417}
418
419fn parse_change(line: &str) -> Option<Change> {
420    let mut words = line.split(' ');
421    let change = match words.next()? {
422        "context" => Change::CreateContext(id(words.next()?)?),
423        "destroy" => Change::DestroyContext(id(words.next()?)?),
424        "bind" => {
425            let context = id(words.next()?)?;
426            let binding_type = match words.next()? {
427                "o" => BindingType::Object,
428                "c" => BindingType::Context,
429                _ => return None,
430            };
431            let component = parse_component(words.next()?)?;
432            let ior = words.next()?.to_owned();
433            if !ior.starts_with("IOR:") {
434                return None;
435            }
436            Change::Bind {
437                context,
438                component,
439                binding: StoredBinding { binding_type, ior },
440            }
441        }
442        "unbind" => Change::Unbind {
443            context: id(words.next()?)?,
444            component: parse_component(words.next()?)?,
445        },
446        _ => return None,
447    };
448    words.next().is_none().then_some(change)
449}
450
451fn id(word: &str) -> Option<String> {
452    (!word.is_empty()).then(|| word.to_owned())
453}
454
455/// A name component in the stringified name form, with `%`, spaces and
456/// control characters escaped as `%XX`.
457fn format_component(component: &NameComponent) -> String {
458    let s = name::to_string(std::slice::from_ref(component)).expect("one component is a name");
459    let mut out = String::with_capacity(s.len());
460    for c in s.chars() {
461        if c == '%' || c == ' ' || c.is_control() {
462            let mut buf = [0; 4];
463            for b in c.encode_utf8(&mut buf).bytes() {
464                let _ = write!(out, "%{b:02X}");
465            }
466        } else {
467            out.push(c);
468        }
469    }
470    out
471}
472
473fn parse_component(word: &str) -> Option<NameComponent> {
474    let mut bytes = Vec::with_capacity(word.len());
475    let mut rest = word.as_bytes();
476    while let Some((&b, tail)) = rest.split_first() {
477        if b == b'%' {
478            let hex = std::str::from_utf8(tail.get(..2)?).ok()?;
479            bytes.push(u8::from_str_radix(hex, 16).ok()?);
480            rest = &tail[2..];
481        } else {
482            bytes.push(b);
483            rest = tail;
484        }
485    }
486    let mut name = name::to_name(&String::from_utf8(bytes).ok()?).ok()?;
487    (name.len() == 1).then(|| name.remove(0))
488}
489
490#[cfg(test)]
491mod tests {
492    use super::*;
493
494    fn nc(id: &str, kind: &str) -> NameComponent {
495        NameComponent::new(id, kind)
496    }
497
498    fn bind(context: &str, component: NameComponent, ior: &str) -> Change {
499        Change::Bind {
500            context: context.into(),
501            component,
502            binding: StoredBinding {
503                binding_type: BindingType::Object,
504                ior: ior.into(),
505            },
506        }
507    }
508
509    #[test]
510    fn records_read_back() {
511        let changes = [
512            Change::CreateContext("NameService".into()),
513            Change::DestroyContext("0123abcd".into()),
514            bind("NameService", nc("a b%c", "k\nd"), "IOR:00"),
515            bind("NameService", nc("", ""), "IOR:01"),
516            bind("x", nc("dots.and/slash\\", "日本"), "IOR:02"),
517            Change::Unbind {
518                context: "x".into(),
519                component: nc("a", ""),
520            },
521        ];
522        for change in changes {
523            let line = format_change(&change);
524            assert_eq!(line.matches('\n').count(), 1, "{line:?}");
525            assert_eq!(parse_change(line.trim_end_matches('\n')), Some(change));
526        }
527        assert_eq!(parse_change("bind x o a IOR:00 extra"), None);
528        assert_eq!(parse_change("bind x z a IOR:00"), None);
529        assert_eq!(parse_change("unbind x a//b"), None);
530        assert_eq!(parse_change("frobnicate x"), None);
531    }
532
533    fn temp_dir(name: &str) -> PathBuf {
534        let dir = std::env::temp_dir().join(format!(
535            "rustorb-naming-store-{name}-{}",
536            std::process::id()
537        ));
538        let _ = fs::remove_dir_all(&dir);
539        dir
540    }
541
542    fn update(store: &mut LogStore, state: &mut Snapshot, change: Change) {
543        store.record(&change).unwrap();
544        state.apply(&change);
545        store.checkpoint(state).unwrap();
546    }
547
548    #[test]
549    fn log_and_checkpoints_survive_a_restart() {
550        let dir = temp_dir("restart");
551        let mut store = LogStore::new(&dir).checkpoint_every(3);
552        let mut state = store.load().unwrap();
553        assert_eq!(state, Snapshot::default());
554        update(&mut store, &mut state, Change::CreateContext("root".into()));
555        for i in 0..4 {
556            update(
557                &mut store,
558                &mut state,
559                bind("root", nc(&format!("n{i}"), ""), "IOR:00"),
560            );
561        }
562        update(
563            &mut store,
564            &mut state,
565            Change::Unbind {
566                context: "root".into(),
567                component: nc("n1", ""),
568            },
569        );
570        drop(store);
571
572        let mut again = LogStore::new(&dir);
573        assert_eq!(again.load().unwrap(), state);
574        // Loading folded the log into a checkpoint.
575        let log = fs::read_to_string(dir.join(LOG_FILE)).unwrap();
576        assert_eq!(log.lines().count(), 1, "{log}");
577        update(
578            &mut again,
579            &mut state,
580            Change::DestroyContext("root".into()),
581        );
582        drop(again);
583        assert_eq!(LogStore::new(&dir).load().unwrap(), state);
584        fs::remove_dir_all(&dir).unwrap();
585    }
586
587    #[test]
588    fn a_torn_last_record_is_dropped() {
589        let dir = temp_dir("torn");
590        let mut store = LogStore::new(&dir);
591        let mut state = store.load().unwrap();
592        update(&mut store, &mut state, Change::CreateContext("root".into()));
593        drop(store);
594        let mut log = OpenOptions::new()
595            .append(true)
596            .open(dir.join(LOG_FILE))
597            .unwrap();
598        log.write_all(b"bind root o half IOR:0").unwrap();
599        drop(log);
600        assert_eq!(LogStore::new(&dir).load().unwrap(), state);
601        fs::remove_dir_all(&dir).unwrap();
602    }
603
604    #[test]
605    fn a_log_older_than_the_checkpoint_is_ignored() {
606        let dir = temp_dir("stale");
607        let mut store = LogStore::new(&dir);
608        let mut state = store.load().unwrap();
609        update(&mut store, &mut state, Change::CreateContext("root".into()));
610        update(&mut store, &mut state, bind("root", nc("a", ""), "IOR:00"));
611        let stale_log = fs::read_to_string(dir.join(LOG_FILE)).unwrap();
612        // A checkpoint is written, but the crash comes before the log is
613        // started again.
614        update(
615            &mut store,
616            &mut state,
617            Change::Unbind {
618                context: "root".into(),
619                component: nc("a", ""),
620            },
621        );
622        store.write_checkpoint(&state).unwrap();
623        drop(store);
624        fs::write(dir.join(LOG_FILE), stale_log).unwrap();
625        assert_eq!(LogStore::new(&dir).load().unwrap(), state);
626        fs::remove_dir_all(&dir).unwrap();
627    }
628
629    #[test]
630    fn a_damaged_file_is_an_error() {
631        let dir = temp_dir("damaged");
632        fs::create_dir_all(&dir).unwrap();
633        fs::write(dir.join(CHECKPOINT_FILE), "rustorb-naming 1 1\ncontext a\n").unwrap();
634        let err = LogStore::new(&dir).load().unwrap_err();
635        assert_eq!(err.kind(), io::ErrorKind::InvalidData);
636        fs::write(dir.join(CHECKPOINT_FILE), "rustorb-naming 1 1\nend\n").unwrap();
637        fs::write(dir.join(LOG_FILE), "rustorb-naming 1 1\nnonsense\n").unwrap();
638        let err = LogStore::new(&dir).load().unwrap_err();
639        assert_eq!(err.kind(), io::ErrorKind::InvalidData);
640        fs::remove_dir_all(&dir).unwrap();
641    }
642}