Skip to main content

mnemo_engine/shared/
lock.rs

1//! The per-call lock loop (12.4 design note, "The protocol" steps 2 to 4 and
2//! 9, "Writer preference", "Long operations"): one deadline and a cancel per
3//! call, jittered backoff, writer preference through the sidecar's intent
4//! lock with a reader that holds it for one try only, and the identity check
5//! once the main lock is held.
6//!
7//! Every lock here goes through [`LockedFile`], so it's unlocked explicitly
8//! before its descriptor closes (FLAKE-1).
9
10use std::fs::{File, OpenOptions};
11use std::path::{Path, PathBuf};
12use std::sync::Arc;
13use std::time::{Duration, SystemTime, UNIX_EPOCH};
14
15use fs4::fs_std::FileExt;
16
17use super::call::{Call, CancelToken};
18use super::fscheck;
19use super::sidecar::{self, Sidecar, SidecarState, INTENT, VALVE};
20use crate::error::{MnemoError, Result};
21use crate::pager::LockedFile;
22use crate::store::{is_file_at, is_lock_conflict};
23
24/// Options for a shared-mode handle (12.4).
25#[derive(Clone, Debug)]
26#[non_exhaustive]
27pub struct SharedOptions {
28    /// How long one call may wait for the file's lock before it fails with
29    /// [`MnemoError::Locked`]. One deadline covers both locks and the
30    /// retries after a compaction. Default 10 s; hooks pass 2 s.
31    pub deadline: Duration,
32    /// Use shared mode on a network or synced filesystem anyway, where the
33    /// lock may not reach every process that opens the file.
34    ///
35    /// The check refuses network filesystems (on Linux, anything but ext4,
36    /// xfs, btrfs, tmpfs, f2fs, overlayfs and zfs; overlayfs assumes Linux
37    /// 4.19 or later) and, on macOS, iCloud Drive and File Provider folders.
38    /// On Windows it refuses UNC paths; a drive letter mapped to a network
39    /// share may not be detected.
40    pub allow_network_fs: bool,
41    /// Cancels the handle's waiting calls from another thread.
42    pub cancel: Option<CancelToken>,
43}
44
45impl Default for SharedOptions {
46    fn default() -> Self {
47        SharedOptions {
48            deadline: Duration::from_secs(10),
49            allow_network_fs: false,
50            cancel: None,
51        }
52    }
53}
54
55/// Which lock a call takes.
56#[derive(Clone, Copy, PartialEq, Eq, Debug)]
57pub(crate) enum LockKind {
58    /// Reads.
59    Shared,
60    /// Writes.
61    Exclusive,
62}
63
64/// The lock layer for one brain: where it is, its sidecar, and the notices
65/// to give once.
66#[derive(Debug)]
67pub(crate) struct BrainLocks {
68    /// The path as given (made absolute), which the locks open and the
69    /// identity check compares.
70    path: PathBuf,
71    /// The path with symlinks resolved, where the sidecar directory lives.
72    resolved: PathBuf,
73    sidecar: Option<Arc<Sidecar>>,
74    notices: Vec<String>,
75    /// A plain long operation's layer ([`BrainLocks::for_plain`]): it never
76    /// creates the sidecar, but looks for it again before each wait
77    /// (RB-008.3 item 5).
78    plain: bool,
79    /// LOCK-2: how many times this layer's writers took the valve (for the
80    /// tests and the bench).
81    valve_takes: u64,
82}
83
84/// LOCK-2: how long a writer waits before it takes the valve. 500 ms, by
85/// the bench's sweep rule (12.4 design note, "LOCK-2"); a `dev-hooks` build
86/// reads `MNEMO_DEV_VALVE_MS` for the sweep.
87const VALVE_AFTER: Duration = Duration::from_millis(500);
88
89/// The bench's baseline: a `dev-hooks` build with `MNEMO_DEV_NO_VALVE` set
90/// runs without the valve (readers don't check it, writers don't take it).
91fn valve_off() -> bool {
92    #[cfg(feature = "dev-hooks")]
93    {
94        static OFF: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
95        *OFF.get_or_init(|| std::env::var_os("MNEMO_DEV_NO_VALVE").is_some())
96    }
97    #[cfg(not(feature = "dev-hooks"))]
98    false
99}
100
101fn valve_after() -> Duration {
102    #[cfg(feature = "dev-hooks")]
103    {
104        static AFTER: std::sync::OnceLock<Duration> = std::sync::OnceLock::new();
105        *AFTER.get_or_init(|| {
106            std::env::var("MNEMO_DEV_VALVE_MS")
107                .ok()
108                .and_then(|v| v.parse().ok())
109                .map(Duration::from_millis)
110                .unwrap_or(VALVE_AFTER)
111        })
112    }
113    #[cfg(not(feature = "dev-hooks"))]
114    VALVE_AFTER
115}
116
117/// The Windows refusal before Rust 1.85 (see `build.rs`).
118pub(crate) const WINDOWS_OLD_RENAME: bool = cfg!(mnemo_windows_old_rename);
119
120impl BrainLocks {
121    /// Set up the lock layer for the brain at `path`. Refuses a Windows
122    /// build before Rust 1.85, a missing file (never creates one), and a
123    /// network or synced filesystem unless `allow_network_fs`.
124    pub(crate) fn new(path: &Path, opts: &SharedOptions) -> Result<Self> {
125        Self::with_sidecar(path, opts, true)
126    }
127
128    /// [`BrainLocks::new`] for a plain long operation (compaction, an
129    /// import, a rekey): it uses the sidecar directory only if one is
130    /// already there. A shared handle makes it when it opens, so without
131    /// one there's no shared caller to queue against, and a brain nobody
132    /// opens in shared mode gains no sibling.
133    pub(crate) fn for_plain(path: &Path, opts: &SharedOptions) -> Result<Self> {
134        Self::with_sidecar(path, opts, false)
135    }
136
137    fn with_sidecar(path: &Path, opts: &SharedOptions, create: bool) -> Result<Self> {
138        if WINDOWS_OLD_RENAME {
139            return Err(MnemoError::Unsupported(
140                "shared mode on Windows needs a build with Rust 1.85 or later (this one was \
141                 built with an older compiler, whose std::fs::rename can't replace an open \
142                 file)"
143                    .into(),
144            ));
145        }
146        let path = if path.is_absolute() {
147            path.to_path_buf()
148        } else {
149            std::env::current_dir()?.join(path)
150        };
151        // Symlinks resolved, so two paths through a symlinked directory find
152        // one sidecar. A missing file is an error here: shared mode never
153        // creates the brain.
154        let resolved = std::fs::canonicalize(&path)?;
155        let mut notices = fscheck::check(&resolved, opts.allow_network_fs)?;
156        let present = std::fs::symlink_metadata(sidecar::sidecar_path(&resolved)).is_ok();
157        let sidecar = if !create && !present {
158            None
159        } else {
160            match sidecar::open(&resolved) {
161                SidecarState::Ready(s) => {
162                    // LOCK-2: a v0.15 shared handle makes the valve file up
163                    // front, so readers can keep its descriptor.
164                    if create {
165                        let _ = s.lock_file(VALVE);
166                    }
167                    Some(Arc::new(s))
168                }
169                SidecarState::Unavailable(why) => {
170                    notices.push(format!(
171                        "not using the sidecar directory: {why}; each call takes the main \
172                         lock alone, without writer preference or a lock-info note"
173                    ));
174                    None
175                }
176            }
177        };
178        Ok(BrainLocks {
179            path,
180            resolved,
181            sidecar,
182            notices,
183            plain: !create,
184            valve_takes: 0,
185        })
186    }
187
188    /// The warnings to show once: a sidecar that can't be used, a synced
189    /// folder, an allowed network filesystem.
190    pub(crate) fn notices(&self) -> &[String] {
191        &self.notices
192    }
193
194    /// Whether the sidecar directory is in use.
195    pub(crate) fn has_sidecar(&self) -> bool {
196        self.sidecar.is_some()
197    }
198
199    /// The sidecar directory, when in use.
200    pub(crate) fn sidecar_path(&self) -> Option<&Path> {
201        self.sidecar.as_deref().map(Sidecar::path)
202    }
203
204    /// LOCK-2: how many times this layer's writers took the valve.
205    pub(crate) fn valve_takes(&self) -> u64 {
206        self.valve_takes
207    }
208
209    /// Take the main lock for one call, within the call's deadline, unless
210    /// cancelled. Writers queue on the intent lock: a writer holds it
211    /// exclusively while it waits for the main lock, so new readers queue
212    /// behind it. But readers already waiting go first, so readers looping
213    /// back to back slow a writer, and enough of them can keep it out past
214    /// its deadline (`Locked`; `docs/shared-mode.md`, "How busy a file can
215    /// get"; LOCK-2 is the planned fix).
216    ///
217    /// A reader takes the intent lock shared and tries the main lock. When
218    /// the main lock is free or held shared, it gets in (RB-006.4 rec. 1).
219    /// When the main lock is held exclusively (a shared try fails only
220    /// then), the reader **keeps** the intent lock shared while it waits
221    /// for that writer (since step 5): the next writer can't take the intent
222    /// lock and queues behind the waiting readers, which get in together
223    /// when the commit ends. Writers and batches of readers alternate, so a
224    /// writer committing back to back can't starve readers either.
225    ///
226    /// One [`Call`] covers every lock a shared handle's window takes, so a
227    /// read that has to take the exclusive lock to heal the file still
228    /// waits one deadline in all (RB-007.8 item 2).
229    ///
230    /// **LOCK-2, the writer safety valve:** a writer that has waited past
231    /// [`VALVE_AFTER`] also takes `writer.lock` exclusively, and from then
232    /// on retries every 1 to 2 ms. A reader tries that lock shared, without
233    /// waiting, before the intent lock, and backs off while a writer holds
234    /// it, until it has itself waited past the threshold (then it queues on
235    /// the intent lock as before, so a chain of writers past the threshold
236    /// can't starve it). So new readers stop arriving, the ones inside
237    /// drain, and the writer gets the intent lock and the main lock. It lets
238    /// the valve go as soon as it holds the main lock.
239    pub(crate) fn acquire(&mut self, kind: LockKind, call: &mut Call) -> Result<Held> {
240        let mut replaced_once = false;
241        let mut valve: Option<LockedFile> = None;
242        'call: loop {
243            call.check()?;
244            // A reader that has itself waited past the threshold stops
245            // deferring to the valve, so writers handing it on to each other
246            // can't keep readers out (the bench's 8-writer mix).
247            if kind == LockKind::Shared
248                && !valve_off()
249                && call.waited() < valve_after()
250                && self.valve_held()
251            {
252                self.wait(kind, call, &mut valve)?;
253                continue;
254            }
255            let intent = match self.try_intent(kind, call)? {
256                Intent::Held(f) => Some(f),
257                Intent::NotUsed => None,
258                Intent::Busy => {
259                    self.wait(kind, call, &mut valve)?;
260                    continue;
261                }
262            };
263            loop {
264                #[cfg(any(test, feature = "failpoints"))]
265                crate::__failpoints::count_shared_main_try();
266                match self.try_main(kind)? {
267                    Main::Got(file) => {
268                        drop(valve);
269                        drop(intent);
270                        return Ok(Held {
271                            file: Some(file),
272                            sidecar: self.sidecar.clone(),
273                            announced: false,
274                        });
275                    }
276                    // A compaction renamed a new file over the path between
277                    // our open and our lock: open the new one, at once the
278                    // first time, then with the backoff, so a path that
279                    // keeps failing the check can't spin a core until the
280                    // deadline. The backoff sleeps without the intent lock
281                    // (RB-007.8 item 3): a reader holds it for one try only,
282                    // and a writer queues for it again.
283                    Main::Replaced => {
284                        call.check()?;
285                        if call.past_deadline() {
286                            return Err(self.locked());
287                        }
288                        if replaced_once {
289                            drop(intent);
290                            self.wait(kind, call, &mut valve)?;
291                            continue 'call;
292                        }
293                        replaced_once = true;
294                        continue;
295                    }
296                    Main::Busy => {}
297                }
298                if intent.is_none() {
299                    break;
300                }
301                // A writer keeps the intent lock while it waits, so new
302                // readers queue behind it. A reader keeps it too, shared,
303                // while a writer holds the main lock (the only time its
304                // shared try fails), so the next writer queues behind it
305                // (step 5; before, readers let it go and starved).
306                self.wait(kind, call, &mut valve)?;
307            }
308            drop(intent);
309            self.wait(kind, call, &mut valve)?;
310        }
311    }
312
313    /// One backoff; past the deadline, `Locked` with what holds the file.
314    /// Before it sleeps: a plain long operation looks for a sidecar that
315    /// shared handles made meanwhile, and a writer past the threshold takes
316    /// the valve (LOCK-2).
317    fn wait(
318        &mut self,
319        kind: LockKind,
320        call: &mut Call,
321        valve: &mut Option<LockedFile>,
322    ) -> Result<()> {
323        self.find_sidecar();
324        if kind == LockKind::Exclusive
325            && valve.is_none()
326            && !valve_off()
327            && call.waited() >= valve_after()
328        {
329            call.hurry();
330            *valve = self.take_valve(call);
331        }
332        // A reader past the threshold hurries too (LOCK-2 round 3): it has
333        // stopped deferring to the valve and queues on the intent lock, and
334        // with the doubling backoff (up to 50 ms) it almost never found the
335        // gap between hurried writers there (the macOS runner's 8-writer
336        // test). Once it holds the intent lock it keeps it, shared, until it
337        // gets the main lock (the inner loop), so readers come first again.
338        if kind == LockKind::Shared && !valve_off() && call.waited() >= valve_after() {
339            call.hurry();
340        }
341        if call.back_off()? {
342            Ok(())
343        } else {
344            Err(self.locked())
345        }
346    }
347
348    /// RB-008.3 item 5: a plain long operation's layer, with no sidecar,
349    /// checks whether one has appeared (one `lstat`), and uses it once it
350    /// has, with every check. It never creates one.
351    fn find_sidecar(&mut self) {
352        if !self.plain || self.sidecar.is_some() {
353            return;
354        }
355        if std::fs::symlink_metadata(sidecar::sidecar_path(&self.resolved)).is_err() {
356            return;
357        }
358        if let SidecarState::Ready(s) = sidecar::open(&self.resolved) {
359            self.sidecar = Some(Arc::new(s));
360        }
361    }
362
363    /// LOCK-2: the valve, exclusively, without waiting: `None` while
364    /// another writer holds it, or when it can't be used (no sidecar, a
365    /// directory this caller can't write in: said once, and the call goes
366    /// on without it).
367    fn take_valve(&mut self, call: &mut Call) -> Option<LockedFile> {
368        let side = self.sidecar.clone()?;
369        let f = match side.lock_file(VALVE) {
370            Ok(f) => f,
371            // The directory may have been removed or replaced since the
372            // handle opened it (RB-007.7): open it again by path, once per
373            // call, as the intent lock does.
374            Err(_) if !call.sidecar_reopened => {
375                call.sidecar_reopened = true;
376                let SidecarState::Ready(s) = sidecar::open(&self.resolved) else {
377                    return None;
378                };
379                let s = Arc::new(s);
380                self.sidecar = Some(s.clone());
381                match s.lock_file(VALVE) {
382                    Ok(f) => f,
383                    Err(e) => return self.no_valve(&s, e),
384                }
385            }
386            Err(e) => return self.no_valve(&side, e),
387        };
388        match FileExt::try_lock_exclusive(&f) {
389            Ok(()) => {
390                self.valve_takes += 1;
391                Some(LockedFile::new(f))
392            }
393            Err(_) => None,
394        }
395    }
396
397    /// The valve can't be made or opened: said once (something else at its
398    /// name, a directory that refuses it), but not for a directory being
399    /// removed (`NotFound`, which the next call recovers from). The call goes
400    /// on without the valve either way.
401    fn no_valve(&mut self, side: &Sidecar, e: std::io::Error) -> Option<LockedFile> {
402        if e.kind() != std::io::ErrorKind::NotFound {
403            self.notice(format!(
404                "can't use {}: {e}; a write that waits goes on without the writer safety valve",
405                side.path().join(VALVE).display()
406            ));
407        }
408        None
409    }
410
411    /// LOCK-2: whether a writer holds the valve. A reader's shared try,
412    /// without waiting, and the unlock: about two system calls. Anything
413    /// but a conflict (no sidecar, no valve file yet, an error) is "no".
414    fn valve_held(&self) -> bool {
415        let Some(f) = self.sidecar.as_ref().and_then(|s| s.valve_for_reading()) else {
416            return false;
417        };
418        match FileExt::try_lock_shared(f) {
419            Ok(()) => {
420                let _ = FileExt::unlock(f);
421                false
422            }
423            Err(e) => is_lock_conflict(&e),
424        }
425    }
426
427    fn locked(&self) -> MnemoError {
428        MnemoError::Locked {
429            path: self.path.clone(),
430            holder: self.holder(),
431        }
432    }
433
434    fn try_intent(&mut self, kind: LockKind, call: &mut Call) -> Result<Intent> {
435        let Some(side) = &self.sidecar else {
436            return Ok(Intent::NotUsed);
437        };
438        let f = match side.lock_file(INTENT) {
439            Ok(f) => f,
440            // The directory may have been removed (`git clean -fdx`) or
441            // replaced since the handle opened it, and the handle's
442            // descriptor still names the old one. Open it again by path,
443            // with every check, once per call (RB-007.7).
444            Err(_) if !call.sidecar_reopened => {
445                call.sidecar_reopened = true;
446                match sidecar::open(&self.resolved) {
447                    SidecarState::Ready(s) => {
448                        let s = Arc::new(s);
449                        self.sidecar = Some(s.clone());
450                        match s.lock_file(INTENT) {
451                            Ok(f) => f,
452                            Err(e) => {
453                                self.notice(format!(
454                                    "can't use {}: {e}; this call takes the main lock alone, \
455                                     without writer preference",
456                                    s.path().join(INTENT).display()
457                                ));
458                                return Ok(Intent::NotUsed);
459                            }
460                        }
461                    }
462                    SidecarState::Unavailable(why) => {
463                        self.notice(format!(
464                            "not using the sidecar directory: {why}; calls take the main \
465                             lock alone, without writer preference or a lock-info note"
466                        ));
467                        return Ok(Intent::NotUsed);
468                    }
469                }
470            }
471            // A lock file that can't be opened safely (something else is at
472            // the name) costs writer preference for this call, never the
473            // call.
474            Err(_) => return Ok(Intent::NotUsed),
475        };
476        match try_lock(&f, kind) {
477            Ok(()) => Ok(Intent::Held(LockedFile::new(f))),
478            Err(e) if is_lock_conflict(&e) => Ok(Intent::Busy),
479            Err(e) => Err(MnemoError::Io(e)),
480        }
481    }
482
483    /// Add `text` to the notices, once.
484    pub(crate) fn notice(&mut self, text: String) {
485        if !self.notices.contains(&text) {
486            self.notices.push(text);
487        }
488    }
489
490    fn try_main(&self, kind: LockKind) -> Result<Main> {
491        let mut o = OpenOptions::new();
492        o.read(true);
493        if kind == LockKind::Exclusive {
494            o.write(true);
495        }
496        // Never creates: a missing file is an error (`NotFound`).
497        let f = match o.open(&self.path) {
498            Ok(f) => f,
499            // A file this process can only read (RB-007.8 item 5).
500            Err(e) if kind == LockKind::Exclusive && is_permission_denied(&e) => {
501                return Err(MnemoError::Io(std::io::Error::new(
502                    std::io::ErrorKind::PermissionDenied,
503                    format!(
504                        "{} isn't writable by this process ({e}), so a shared-mode write \
505                         can't take its lock; reads still work",
506                        self.path.display()
507                    ),
508                )))
509            }
510            Err(e) => return Err(MnemoError::Io(e)),
511        };
512        match try_lock(&f, kind) {
513            Ok(()) => {
514                let f = LockedFile::new(f);
515                #[cfg(any(test, feature = "failpoints"))]
516                if crate::__failpoints::take_shared_replaced() {
517                    return Ok(Main::Replaced);
518                }
519                if is_file_at(&f, &self.path)? {
520                    Ok(Main::Got(f))
521                } else {
522                    Ok(Main::Replaced)
523                }
524            }
525            Err(e) if is_lock_conflict(&e) => Ok(Main::Busy),
526            Err(e) => Err(MnemoError::Io(e)),
527        }
528    }
529
530    /// The live holder's note, if there is one and its process still runs.
531    fn holder(&self) -> Option<String> {
532        let line = self.sidecar.as_ref()?.read_lock_info()?;
533        let info = LockInfo::parse(&line)?;
534        sidecar::pid_alive(info.pid).then(|| info.describe())
535    }
536}
537
538enum Intent {
539    Held(LockedFile),
540    Busy,
541    NotUsed,
542}
543
544enum Main {
545    Got(LockedFile),
546    Busy,
547    Replaced,
548}
549
550/// Whether opening the brain for writing failed for lack of permission.
551pub(crate) fn is_permission_denied(e: &std::io::Error) -> bool {
552    e.kind() == std::io::ErrorKind::PermissionDenied
553}
554
555fn try_lock(f: &File, kind: LockKind) -> std::io::Result<()> {
556    match kind {
557        LockKind::Shared => FileExt::try_lock_shared(f),
558        LockKind::Exclusive => FileExt::try_lock_exclusive(f),
559    }
560}
561
562/// The main lock for one call. Dropping it removes this call's `lock-info`
563/// note, if it wrote one, and then unlocks.
564pub(crate) struct Held {
565    file: Option<LockedFile>,
566    sidecar: Option<Arc<Sidecar>>,
567    announced: bool,
568}
569
570impl Held {
571    /// The locked file.
572    pub(crate) fn file(&self) -> &File {
573        self.file.as_ref().expect("held until dropped")
574    }
575
576    /// Hand the locked file to the caller (a shared handle's pager), which
577    /// then owns the lock. Drop this `Held` first, so its `lock-info` note
578    /// goes before the caller's unlock.
579    pub(crate) fn take_file(&mut self) -> LockedFile {
580        self.file.take().expect("taken once")
581    }
582
583    /// Say what this exclusive call is doing, for callers that time out
584    /// waiting: written after the lock is held, by temp name and rename,
585    /// and removed before the unlock. A note that can't be written is
586    /// skipped (it's a hint).
587    pub(crate) fn announce(&mut self, op: &str) {
588        if let Some(side) = &self.sidecar {
589            let line = LockInfo::current(op).encode();
590            if side.write_lock_info(&line).is_ok() {
591                self.announced = true;
592            }
593        }
594    }
595}
596
597impl Drop for Held {
598    fn drop(&mut self) {
599        if self.announced {
600            if let Some(side) = &self.sidecar {
601                side.remove_lock_info();
602            }
603        }
604        drop(self.file.take());
605    }
606}
607
608/// The `lock-info` line: operation, pid, start time, tool, tab-separated.
609struct LockInfo {
610    op: String,
611    pid: u32,
612    since: u64,
613    tool: String,
614}
615
616impl LockInfo {
617    fn current(op: &str) -> Self {
618        let tool = std::env::current_exe()
619            .ok()
620            .and_then(|p| p.file_stem().map(|s| s.to_string_lossy().into_owned()))
621            .unwrap_or_else(|| "mnemo".into());
622        LockInfo {
623            op: clean(op),
624            pid: std::process::id(),
625            since: SystemTime::now()
626                .duration_since(UNIX_EPOCH)
627                .map_or(0, |d| d.as_secs()),
628            tool: clean(&tool),
629        }
630    }
631
632    fn encode(&self) -> String {
633        format!("{}\t{}\t{}\t{}", self.op, self.pid, self.since, self.tool)
634    }
635
636    fn parse(line: &str) -> Option<Self> {
637        let mut f = line.split('\t');
638        Some(LockInfo {
639            op: clean(f.next()?),
640            pid: f.next()?.parse().ok()?,
641            since: f.next()?.parse().ok()?,
642            tool: clean(f.next()?),
643        })
644    }
645
646    /// "compact since 12:01:05 UTC (pid 4242, mnemo)".
647    fn describe(&self) -> String {
648        let s = self.since % 86_400;
649        format!(
650            "{} since {:02}:{:02}:{:02} UTC (pid {}, {})",
651            self.op,
652            s / 3600,
653            s % 3600 / 60,
654            s % 60,
655            self.pid,
656            self.tool
657        )
658    }
659}
660
661/// Printable, short, no tabs or line breaks: the note is shown in error
662/// messages, and another process wrote it.
663fn clean(s: &str) -> String {
664    s.chars().filter(|c| !c.is_control()).take(64).collect()
665}