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}