1use std::process::Command;
39use std::sync::atomic::{AtomicU8, AtomicU64, Ordering};
40use std::sync::{Arc, Condvar, Mutex, OnceLock, PoisonError};
41use std::thread::JoinHandle;
42use std::time::{Duration, Instant};
43
44pub const START_FAILURE_CODE: &str = "DIVE-R0001";
46
47pub const MEASUREMENT_FAILURE_CODE: &str = "DIVE-R0002";
49
50#[derive(Clone, Copy, Debug, PartialEq, Eq)]
52pub enum SamplePoint {
53 Initial,
55 Periodic,
57 Final,
59}
60impl SamplePoint {
61 #[must_use]
63 pub const fn name(self) -> &'static str {
64 match self {
65 Self::Initial => "initial",
66 Self::Periodic => "periodic",
67 Self::Final => "final",
68 }
69 }
70 const fn flag(self) -> u8 {
71 match self {
72 Self::Initial => 1,
73 Self::Periodic => 2,
74 Self::Final => 3,
75 }
76 }
77 fn from_flag(flag: u8) -> Self {
78 match flag {
79 1 => Self::Initial,
80 3 => Self::Final,
81 _ => Self::Periodic,
82 }
83 }
84}
85
86#[derive(Clone, Copy, Debug, PartialEq, Eq)]
88pub struct MeasurementError {
89 pub point: SamplePoint,
91 pub kind: MeasurementKind,
93}
94#[derive(Clone, Copy, Debug, PartialEq, Eq)]
96#[non_exhaustive]
97pub enum MeasurementKind {
98 Process,
100 DefaultCeiling,
102}
103impl MeasurementKind {
104 #[must_use]
106 pub const fn name(self) -> &'static str {
107 match self {
108 Self::Process => "process-memory",
109 Self::DefaultCeiling => "default-ceiling",
110 }
111 }
112}
113
114impl MeasurementError {
115 #[must_use]
117 pub const fn default_ceiling_unavailable() -> Self {
118 Self {
119 point: SamplePoint::Initial,
120 kind: MeasurementKind::DefaultCeiling,
121 }
122 }
123
124 #[must_use]
126 pub const fn unavailable(point: SamplePoint) -> Self {
127 Self {
128 point,
129 kind: MeasurementKind::Process,
130 }
131 }
132}
133impl std::fmt::Display for MeasurementError {
134 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
135 write!(
136 f,
137 "{MEASUREMENT_FAILURE_CODE}: {} at the {} sample; retry on a supported host or pass --max-memory none",
138 match self.kind {
139 MeasurementKind::Process => "cannot measure the current process's memory",
140 MeasurementKind::DefaultCeiling =>
141 "cannot determine the default memory ceiling because physical RAM is unavailable",
142 },
143 self.point.name()
144 )
145 }
146}
147impl std::error::Error for MeasurementError {}
148
149#[derive(Debug)]
152#[non_exhaustive]
153pub enum StartError {
154 Thread(std::io::Error),
156 Measurement(MeasurementError),
158}
159impl std::fmt::Display for StartError {
160 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
161 match self {
162 Self::Thread(error) => write!(
163 f,
164 "{START_FAILURE_CODE}: cannot start the budget watchdog: {error}; free host resources and retry, or pass --time-limit none --max-memory none"
165 ),
166 Self::Measurement(error) => error.fmt(f),
167 }
168 }
169}
170impl std::error::Error for StartError {
171 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
172 Some(match self {
173 Self::Thread(error) => error,
174 Self::Measurement(error) => error,
175 })
176 }
177}
178
179#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
181pub struct MemorySamples {
182 pub count: u64,
184 pub maximum: Option<u64>,
186 pub initial: bool,
188 pub final_sample: bool,
190 pub unavailable: Option<SamplePoint>,
192}
193
194const TICK: Duration = Duration::from_millis(50);
196
197pub const MEMORY_EVERY: Duration = if cfg!(target_os = "linux") {
200 Duration::from_millis(100)
201} else {
202 Duration::from_millis(500)
203};
204
205#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
207#[non_exhaustive]
208pub enum Resource {
209 Time,
211 Memory,
213 States,
215 Depth,
217}
218
219impl Resource {
220 #[must_use]
222 pub const fn name(self) -> &'static str {
223 match self {
224 Self::Time => "time",
225 Self::Memory => "memory",
226 Self::States => "states",
227 Self::Depth => "depth",
228 }
229 }
230
231 #[must_use]
234 pub const fn unit(self) -> &'static str {
235 match self {
236 Self::Time => "ms",
237 Self::Memory => "bytes",
238 Self::States => "states",
239 Self::Depth => "levels",
240 }
241 }
242
243 const fn flag(self) -> u8 {
244 match self {
245 Self::Time => 1,
246 Self::Memory => 2,
247 Self::States => 3,
248 Self::Depth => 4,
249 }
250 }
251}
252
253#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
255#[non_exhaustive]
256pub enum Phase {
257 Startup,
259 Binding,
261 Finalization,
263 Search,
265 Simulation,
267 Dfid,
269 Capture,
271 Temporal,
273 Validation,
275}
276
277impl Phase {
278 #[must_use]
280 pub const fn name(self) -> &'static str {
281 match self {
282 Self::Startup => "check-startup",
283 Self::Binding => "model-binding",
284 Self::Finalization => "finalization",
285 Self::Search => "safety-search",
286 Self::Simulation => "simulation",
287 Self::Dfid => "dfid",
288 Self::Capture => "graph-capture",
289 Self::Temporal => "temporal-analysis",
290 Self::Validation => "trace-validation",
291 }
292 }
293}
294
295#[derive(Clone, Debug, PartialEq, Eq)]
297pub struct Stopped {
298 pub resource: Resource,
300 pub limit: u64,
302 pub observed: u64,
305 pub elapsed_ms: u64,
307 pub phase: Phase,
309}
310
311impl Stopped {
312 #[must_use]
315 pub fn hint(&self) -> &'static str {
316 match self.resource {
317 Resource::Time => {
318 "raise --time-limit, or pass --time-limit=none; the run made no claim about the model"
319 }
320 Resource::Memory => {
321 "raise --max-memory, or pass --max-memory=none; the run made no claim about the model"
322 }
323 Resource::States => {
324 "raise --max-states, or pass --max-states=none; the run made no claim about the model"
325 }
326 Resource::Depth => {
327 "raise --max-depth, or pass --max-depth=none; the run made no claim about the model"
328 }
329 }
330 }
331}
332
333impl std::fmt::Display for Stopped {
334 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
335 match self.resource {
336 Resource::Time => write!(
337 f,
338 "stopped during {} after {} ms: the time limit is {} ms",
339 self.phase.name(),
340 self.observed,
341 self.limit
342 ),
343 Resource::Memory => write!(
344 f,
345 "stopped during {}: resident memory {} bytes exceeds the ceiling of {} bytes",
346 self.phase.name(),
347 self.observed,
348 self.limit
349 ),
350 Resource::States | Resource::Depth => write!(
351 f,
352 "stopped during {}: the next {} would be {}, exceeding the limit of {}",
353 self.phase.name(),
354 self.resource.name(),
355 self.observed,
356 self.limit
357 ),
358 }
359 }
360}
361
362#[derive(Clone, Copy, Debug, PartialEq, Eq)]
364pub struct Exhausted {
365 pub resource: Resource,
367 pub limit: u64,
369 pub observed: u64,
371 pub elapsed_ms: u64,
373}
374
375impl Exhausted {
376 #[must_use]
378 pub const fn during(self, phase: Phase) -> Stopped {
379 Stopped {
380 resource: self.resource,
381 limit: self.limit,
382 observed: self.observed,
383 elapsed_ms: self.elapsed_ms,
384 phase,
385 }
386 }
387}
388
389const MEASUREMENT_FAILED: u8 = 5;
390const PUBLISHING: u8 = 6;
391
392#[derive(Default)]
393enum Sampler {
394 #[default]
395 Native,
396 #[cfg(test)]
397 Injected(Arc<dyn Fn() -> Option<u64> + Send + Sync>),
398}
399impl std::fmt::Debug for Sampler {
400 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
401 f.write_str("process-memory sampler")
402 }
403}
404impl Sampler {
405 fn read(&self) -> Option<u64> {
406 match self {
407 Self::Native => resident_bytes(),
408 #[cfg(test)]
409 Self::Injected(sample) => sample(),
410 }
411 }
412}
413
414#[derive(Debug)]
415struct Inner {
416 tripped: AtomicU8,
417 observed: AtomicU64,
418 unavailable: AtomicU8,
419 sample_count: AtomicU64,
420 sample_maximum: AtomicU64,
421 sample_points: AtomicU8,
422 sampler: Sampler,
423 started: Instant,
424 done: Mutex<bool>,
425 wake: Condvar,
426}
427impl Inner {
428 fn publish(&self, flag: u8, observed: u64) {
429 if self
430 .tripped
431 .compare_exchange(0, PUBLISHING, Ordering::Acquire, Ordering::Relaxed)
432 .is_ok()
433 {
434 self.observed.store(observed, Ordering::Relaxed);
435 self.tripped.store(flag, Ordering::Release);
436 }
437 }
438 fn trip(&self, resource: Resource, observed: u64) {
439 self.publish(resource.flag(), observed);
440 }
441 fn record_sample(
442 &self,
443 point: SamplePoint,
444 value: Option<u64>,
445 ceiling: u64,
446 ) -> Result<(), MeasurementError> {
447 let Some(bytes) = value else {
448 let _ = self.unavailable.compare_exchange(
449 0,
450 point.flag(),
451 Ordering::Relaxed,
452 Ordering::Relaxed,
453 );
454 self.publish(MEASUREMENT_FAILED, 0);
455 return Err(MeasurementError::unavailable(point));
456 };
457 self.sample_maximum.fetch_max(bytes, Ordering::Relaxed);
458 self.sample_count.fetch_add(1, Ordering::Relaxed);
459 self.sample_points
460 .fetch_or(1 << point.flag(), Ordering::Release);
461 if bytes > ceiling {
462 self.trip(Resource::Memory, bytes);
463 }
464 Ok(())
465 }
466 fn sample(&self, point: SamplePoint, ceiling: u64) -> Result<(), MeasurementError> {
467 self.record_sample(point, self.sampler.read(), ceiling)
468 }
469}
470
471#[derive(Clone, Debug, Default)]
474pub struct Budget {
475 pub time: Option<Duration>,
477 pub memory: Option<u64>,
480 signal: Option<Arc<Inner>>,
481}
482
483impl Budget {
484 #[cfg(test)]
487 #[doc(hidden)]
488 pub fn trip_for_test(&self) {
489 if let Some(inner) = &self.signal {
490 inner.trip(Resource::Time, millis(inner.started.elapsed()));
491 }
492 }
493
494 #[must_use]
496 pub const fn unlimited() -> Self {
497 Self {
498 time: None,
499 memory: None,
500 signal: None,
501 }
502 }
503
504 #[must_use]
506 pub const fn new(time: Option<Duration>, memory: Option<u64>) -> Self {
507 Self {
508 time,
509 memory,
510 signal: None,
511 }
512 }
513
514 #[must_use]
516 pub const fn is_unlimited(&self) -> bool {
517 self.time.is_none() && self.memory.is_none()
518 }
519
520 #[must_use]
523 pub const fn is_armed(&self) -> bool {
524 self.signal.is_some()
525 }
526
527 pub fn start(&self) -> Result<Option<Watchdog>, StartError> {
534 self.start_with_sampler(
535 |watched, time, memory| {
536 std::thread::Builder::new()
537 .name("dive-budget".into())
538 .spawn(move || watch(&watched, time, memory))
539 },
540 Sampler::Native,
541 )
542 }
543
544 #[cfg(test)]
545 fn start_with(
546 &self,
547 spawn: impl FnOnce(Arc<Inner>, Option<Duration>, Option<u64>) -> std::io::Result<JoinHandle<()>>,
548 ) -> Result<Option<Watchdog>, StartError> {
549 self.start_with_sampler(spawn, Sampler::Native)
550 }
551
552 fn start_with_sampler(
553 &self,
554 spawn: impl FnOnce(Arc<Inner>, Option<Duration>, Option<u64>) -> std::io::Result<JoinHandle<()>>,
555 sampler: Sampler,
556 ) -> Result<Option<Watchdog>, StartError> {
557 if self.is_unlimited() || self.is_armed() {
558 return Ok(None);
559 }
560 let inner = Arc::new(Inner {
561 tripped: AtomicU8::new(0),
562 observed: AtomicU64::new(0),
563 unavailable: AtomicU8::new(0),
564 sample_count: AtomicU64::new(0),
565 sample_maximum: AtomicU64::new(0),
566 sample_points: AtomicU8::new(0),
567 sampler,
568 started: Instant::now(),
569 done: Mutex::new(false),
570 wake: Condvar::new(),
571 });
572 let (time, memory) = (self.time, self.memory);
573 if time == Some(Duration::ZERO) {
574 inner.trip(Resource::Time, millis(inner.started.elapsed()));
575 }
576 if let Some(ceiling) = memory {
577 inner
578 .sample(SamplePoint::Initial, ceiling)
579 .map_err(StartError::Measurement)?;
580 }
581 let thread = spawn(inner.clone(), time, memory).map_err(StartError::Thread)?;
582 Ok(Some(Watchdog {
583 budget: Self {
584 time,
585 memory,
586 signal: Some(inner),
587 },
588 thread: Some(thread),
589 finished: false,
590 }))
591 }
592
593 #[inline]
600 pub fn poll(&self) -> Result<Option<Exhausted>, MeasurementError> {
601 let Some(inner) = &self.signal else {
602 return Ok(None);
603 };
604 let mut flag = inner.tripped.load(Ordering::Relaxed);
605 if flag == 0 {
606 return Ok(None);
607 }
608 flag = inner.tripped.load(Ordering::Acquire);
609 while flag == PUBLISHING {
610 std::hint::spin_loop();
611 flag = inner.tripped.load(Ordering::Acquire);
612 }
613 if flag == MEASUREMENT_FAILED {
614 return Err(MeasurementError::unavailable(SamplePoint::from_flag(
615 inner.unavailable.load(Ordering::Relaxed),
616 )));
617 }
618 let resource = if flag == 1 {
619 Resource::Time
620 } else {
621 Resource::Memory
622 };
623 let limit = match resource {
624 Resource::Time => self
625 .time
626 .map_or(0, |t| u64::try_from(t.as_millis()).unwrap_or(u64::MAX)),
627 Resource::Memory => self.memory.unwrap_or(0),
628 Resource::States | Resource::Depth => 0,
629 };
630 Ok(Some(Exhausted {
631 resource,
632 limit,
633 observed: inner.observed.load(Ordering::Relaxed),
634 elapsed_ms: millis(inner.started.elapsed()),
635 }))
636 }
637
638 #[must_use]
640 pub fn memory_samples(&self) -> Option<MemorySamples> {
641 let inner = self.signal.as_ref()?;
642 let points = inner.sample_points.load(Ordering::Acquire);
643 let count = inner.sample_count.load(Ordering::Relaxed);
644 let unavailable = inner.unavailable.load(Ordering::Relaxed);
645 Some(MemorySamples {
646 count,
647 maximum: (count != 0).then(|| inner.sample_maximum.load(Ordering::Relaxed)),
648 initial: points & (1 << 1) != 0,
649 final_sample: points & (1 << 3) != 0,
650 unavailable: (unavailable != 0).then(|| SamplePoint::from_flag(unavailable)),
651 })
652 }
653}
654
655pub fn finish_result(
659 result: &mut crate::CheckResult,
660 finished: Result<Option<Exhausted>, MeasurementError>,
661 phase: Phase,
662) {
663 if result.verdict != crate::Verdict::Success {
664 return;
665 }
666 result.verdict = match finished {
667 Ok(Some(exhausted)) => crate::Verdict::Stopped(Box::new(exhausted.during(phase))),
668 Err(error) => crate::Verdict::BudgetMeasurement { error },
669 Ok(None) => return,
670 };
671 result.counterexample = None;
672 result.collision = None;
673 result.tlc_prints_stats = false;
674}
675
676fn millis(d: Duration) -> u64 {
677 u64::try_from(d.as_millis()).unwrap_or(u64::MAX)
678}
679
680pub fn arm(
700 opts: &crate::CheckOptions,
701) -> Result<(Option<Watchdog>, std::borrow::Cow<'_, crate::CheckOptions>), StartError> {
702 match opts.budget.start()? {
703 Some(watchdog) => {
704 let armed = crate::CheckOptions {
705 budget: watchdog.budget().clone(),
706 ..opts.clone()
707 };
708 Ok((Some(watchdog), std::borrow::Cow::Owned(armed)))
709 }
710 None => Ok((None, std::borrow::Cow::Borrowed(opts))),
711 }
712}
713
714#[derive(Debug)]
716pub struct Watchdog {
717 budget: Budget,
718 thread: Option<JoinHandle<()>>,
719 finished: bool,
720}
721
722impl Watchdog {
723 #[must_use]
725 pub const fn budget(&self) -> &Budget {
726 &self.budget
727 }
728
729 pub fn finish(&mut self) -> Result<Option<Exhausted>, MeasurementError> {
735 if self.finished {
736 return self.budget.poll();
737 }
738 self.finished = true;
739 let earlier = self.budget.poll();
740 if let Some(inner) = &self.budget.signal {
741 *inner.done.lock().unwrap_or_else(PoisonError::into_inner) = true;
742 inner.wake.notify_all();
743 if let Some(ceiling) = self.budget.memory {
744 let _ = inner.sample(SamplePoint::Final, ceiling);
745 }
746 if let Some(limit) = self.budget.time {
747 let elapsed = inner.started.elapsed();
748 if elapsed >= limit {
749 inner.trip(Resource::Time, millis(elapsed));
750 }
751 }
752 }
753 match earlier {
754 Ok(None) => self.budget.poll(),
755 prior => prior,
756 }
757 }
758}
759
760impl Drop for Watchdog {
761 fn drop(&mut self) {
764 if let Some(inner) = &self.budget.signal {
765 *inner.done.lock().unwrap_or_else(PoisonError::into_inner) = true;
766 inner.wake.notify_all();
767 }
768 if let Some(thread) = self.thread.take()
769 && thread.is_finished()
770 {
771 let _ = thread.join();
772 }
773 }
774}
775
776fn watch(inner: &Inner, time: Option<Duration>, memory: Option<u64>) {
777 let started = inner.started;
778 let mut sampled = started;
781 let tick = time.map_or(TICK, |t| (t / 10).clamp(Duration::from_millis(1), TICK));
782 let mut done = inner.done.lock().unwrap_or_else(PoisonError::into_inner);
783 loop {
784 if *done || inner.tripped.load(Ordering::Relaxed) != 0 {
785 return;
786 }
787 let elapsed = started.elapsed();
788 if let Some(limit) = time
789 && elapsed >= limit
790 {
791 inner.trip(Resource::Time, millis(elapsed));
792 return;
793 }
794 if let Some(ceiling) = memory
795 && sampled.elapsed() >= MEMORY_EVERY
796 {
797 sampled = Instant::now();
798 drop(done);
799 let rss = inner.sampler.read();
800 done = inner.done.lock().unwrap_or_else(PoisonError::into_inner);
801 if *done {
802 return;
803 }
804 if inner
805 .record_sample(SamplePoint::Periodic, rss, ceiling)
806 .is_err()
807 {
808 return;
809 }
810 }
811 done = inner
812 .wake
813 .wait_timeout(done, tick)
814 .unwrap_or_else(PoisonError::into_inner)
815 .0;
816 }
817}
818
819#[must_use]
823pub fn resident_bytes() -> Option<u64> {
824 if cfg!(target_os = "linux") {
825 let text = std::fs::read_to_string("/proc/self/status").ok()?;
826 linux_process_bytes(&text)
827 } else {
828 native_resident_bytes()
829 }
830}
831
832#[cfg(target_os = "macos")]
833fn native_resident_bytes() -> Option<u64> {
834 memory_stats::memory_stats().and_then(|sample| u64::try_from(sample.physical_mem).ok())
835}
836#[cfg(not(target_os = "macos"))]
837fn native_resident_bytes() -> Option<u64> {
838 None
839}
840
841#[must_use]
844pub fn physical_bytes() -> Option<u64> {
845 static PHYSICAL: OnceLock<Option<u64>> = OnceLock::new();
846 *PHYSICAL.get_or_init(|| {
847 if cfg!(target_os = "linux") {
848 std::fs::read_to_string("/proc/meminfo")
849 .ok()
850 .and_then(|text| kib_field(&text, "MemTotal:"))
851 } else if cfg!(target_os = "macos") {
852 command_number(Command::new("/usr/sbin/sysctl").args(["-n", "hw.memsize"]))
853 } else {
854 None
855 }
856 })
857}
858
859#[must_use]
873pub fn default_memory() -> Option<u64> {
874 physical_bytes()
875 .map(|bytes| bytes / 2)
876 .filter(|bytes| *bytes != 0)
877}
878
879fn linux_process_bytes(text: &str) -> Option<u64> {
880 kib_field(text, "VmRSS:")?.checked_add(kib_field(text, "VmSwap:")?)
881}
882
883fn kib_field(text: &str, key: &str) -> Option<u64> {
884 let line = text.lines().find(|line| line.starts_with(key))?;
885 let kib: u64 = line
886 .strip_prefix(key)?
887 .trim()
888 .strip_suffix("kB")?
889 .trim()
890 .parse()
891 .ok()?;
892 kib.checked_mul(1024)
893}
894
895fn command_number(command: &mut Command) -> Option<u64> {
896 let output = command.output().ok()?;
897 if !output.status.success() {
898 return None;
899 }
900 String::from_utf8(output.stdout).ok()?.trim().parse().ok()
901}
902
903#[cfg(test)]
904mod tests {
905 #![allow(clippy::expect_used, reason = "watchdog controls")]
906 use super::*;
907
908 fn wait_for(budget: &Budget) -> Option<Exhausted> {
909 let started = Instant::now();
910 while started.elapsed() < Duration::from_secs(10) {
911 if let Some(e) = budget.poll().expect("measurement") {
912 return Some(e);
913 }
914 std::thread::sleep(Duration::from_millis(5));
915 }
916 None
917 }
918
919 #[test]
920 fn a_spawn_failure_is_distinct_from_an_unlimited_budget() {
921 let limited = Budget::new(Some(Duration::from_secs(60)), None);
922 let error = limited
923 .start_with(|_, _, _| Err(std::io::Error::other("injected thread exhaustion")))
924 .expect_err("a requested watchdog must not disappear");
925 assert!(error.to_string().contains(START_FAILURE_CODE));
926 assert!(error.to_string().contains("injected thread exhaustion"));
927 assert!(
928 error
929 .to_string()
930 .contains("--time-limit none --max-memory none")
931 );
932 assert!(std::error::Error::source(&error).is_some());
933 assert!(!limited.is_armed());
934 assert!(!limited.is_unlimited());
935
936 let attempted = std::cell::Cell::new(false);
937 let unlimited = Budget::unlimited()
938 .start_with(|_, _, _| {
939 attempted.set(true);
940 Err(std::io::Error::other(
941 "must not attempt an unlimited watchdog",
942 ))
943 })
944 .expect("unlimited needs no host resource");
945 assert!(unlimited.is_none());
946 assert!(!attempted.get());
947 }
948
949 #[test]
950 fn an_expired_time_limit_trips_with_the_elapsed_time() {
951 let watchdog = Budget::new(Some(Duration::from_millis(20)), None)
952 .start()
953 .expect("watchdog thread starts")
954 .expect("watchdog");
955 let e = wait_for(watchdog.budget()).expect("trips");
956 assert_eq!(e.resource, Resource::Time);
957 assert_eq!(e.limit, 20);
958 assert!(e.observed >= 20);
959 }
960
961 #[test]
962 fn a_memory_ceiling_below_the_footprint_trips_where_memory_is_known() {
963 if resident_bytes().is_none() {
964 return;
965 }
966 let watchdog = Budget::new(None, Some(1))
967 .start()
968 .expect("watchdog thread starts")
969 .expect("watchdog");
970 let e = wait_for(watchdog.budget()).expect("trips");
971 assert_eq!((e.resource, e.limit), (Resource::Memory, 1));
972 assert!(e.observed > 1);
973 }
974
975 #[test]
976 fn generous_limits_and_unarmed_budgets_never_trip() {
977 let watchdog = Budget::new(Some(Duration::from_secs(3600)), Some(u64::MAX))
978 .start()
979 .expect("watchdog thread starts")
980 .expect("watchdog");
981 std::thread::sleep(Duration::from_millis(150));
982 assert!(watchdog.budget().poll().expect("measurement").is_none());
983 assert!(
984 Budget::new(Some(Duration::ZERO), None)
985 .poll()
986 .expect("measurement")
987 .is_none()
988 );
989 assert!(Budget::unlimited().start().expect("unlimited").is_none());
990 assert!(watchdog.budget().start().expect("armed").is_none());
992 }
993
994 #[test]
995 fn linux_memory_requires_both_checked_components() {
996 assert_eq!(
997 linux_process_bytes("VmRSS: 2 kB\nVmSwap: 3 kB\n"),
998 Some(5 * 1024)
999 );
1000 for text in [
1001 "VmRSS: 2 kB\n",
1002 "VmRSS: 2 kB\nVmSwap: bad kB\n",
1003 "VmRSS: 2 kB\nVmSwap: 18446744073709551615 kB\n",
1004 "VmRSS: 18014398509481983 kB\nVmSwap: 1 kB\n",
1005 ] {
1006 assert_eq!(linux_process_bytes(text), None, "{text}");
1007 }
1008 }
1009
1010 #[test]
1011 fn the_platform_reports_memory_on_linux_and_macos() {
1012 if cfg!(any(target_os = "linux", target_os = "macos")) {
1013 assert!(resident_bytes().is_some_and(|b| b > 0));
1014 assert!(physical_bytes().is_some_and(|b| b > resident_bytes().unwrap_or(0)));
1015 }
1016 }
1017 fn injected(sample: impl Fn() -> Option<u64> + Send + Sync + 'static) -> Watchdog {
1018 Budget::new(None, Some(100))
1019 .start_with_sampler(
1020 |inner, time, memory| {
1021 std::thread::Builder::new().spawn(move || watch(&inner, time, memory))
1022 },
1023 Sampler::Injected(Arc::new(sample)),
1024 )
1025 .expect("initial observation succeeds")
1026 .expect("finite budget")
1027 }
1028
1029 #[test]
1030 fn an_initial_measurement_failure_never_starts_an_unguarded_run() {
1031 let attempted = std::cell::Cell::new(false);
1032 let error = Budget::new(None, Some(100))
1033 .start_with_sampler(
1034 |_, _, _| {
1035 attempted.set(true);
1036 Err(std::io::Error::other("must not spawn"))
1037 },
1038 Sampler::Injected(Arc::new(|| None)),
1039 )
1040 .expect_err("observation must fail closed");
1041 assert!(matches!(
1042 error,
1043 StartError::Measurement(MeasurementError {
1044 point: SamplePoint::Initial,
1045 kind: MeasurementKind::Process
1046 })
1047 ));
1048 assert!(!attempted.get());
1049 assert!(error.to_string().contains(MEASUREMENT_FAILURE_CODE));
1050 }
1051
1052 #[test]
1053 fn initial_and_final_samples_are_shared_and_finish_is_idempotent() {
1054 let calls = Arc::new(std::sync::atomic::AtomicUsize::new(0));
1055 let reads = calls.clone();
1056 let mut watchdog = injected(move || {
1057 Some(if reads.fetch_add(1, Ordering::Relaxed) == 0 {
1058 10
1059 } else {
1060 20
1061 })
1062 });
1063 assert!(watchdog.budget().start().expect("already armed").is_none());
1064 assert_eq!(watchdog.finish(), Ok(None));
1065 assert_eq!(watchdog.finish(), Ok(None));
1066 assert_eq!(calls.load(Ordering::Relaxed), 2);
1067 assert_eq!(
1068 watchdog.budget().memory_samples(),
1069 Some(MemorySamples {
1070 count: 2,
1071 maximum: Some(20),
1072 initial: true,
1073 final_sample: true,
1074 unavailable: None
1075 })
1076 );
1077 }
1078
1079 #[test]
1080 fn final_unknown_memory_is_a_typed_error_never_a_zero_byte_stop() {
1081 let calls = std::sync::atomic::AtomicUsize::new(0);
1082 let mut watchdog =
1083 injected(move || (calls.fetch_add(1, Ordering::Relaxed) == 0).then_some(10));
1084 assert_eq!(
1085 watchdog.finish(),
1086 Err(MeasurementError::unavailable(SamplePoint::Final))
1087 );
1088 assert_eq!(
1089 watchdog.budget().poll(),
1090 Err(MeasurementError::unavailable(SamplePoint::Final))
1091 );
1092 assert_eq!(
1093 watchdog.budget().memory_samples(),
1094 Some(MemorySamples {
1095 count: 1,
1096 maximum: Some(10),
1097 initial: true,
1098 final_sample: false,
1099 unavailable: Some(SamplePoint::Final)
1100 })
1101 );
1102 }
1103
1104 #[test]
1105 fn final_excess_has_the_real_observed_bytes() {
1106 let calls = std::sync::atomic::AtomicUsize::new(0);
1107 let mut watchdog = injected(move || {
1108 Some(if calls.fetch_add(1, Ordering::Relaxed) == 0 {
1109 10
1110 } else {
1111 101
1112 })
1113 });
1114 let stopped = watchdog.finish().expect("measurement").expect("excess");
1115 assert_eq!(
1116 (stopped.resource, stopped.limit, stopped.observed),
1117 (Resource::Memory, 100, 101)
1118 );
1119 assert_eq!(
1120 watchdog.budget().memory_samples().expect("armed").maximum,
1121 Some(101)
1122 );
1123 }
1124
1125 #[test]
1126 fn a_periodic_sensor_failure_interrupts_without_fabricating_exhaustion() {
1127 let calls = std::sync::atomic::AtomicUsize::new(0);
1128 let mut watchdog =
1129 injected(move || (calls.fetch_add(1, Ordering::Relaxed) == 0).then_some(10));
1130 let started = Instant::now();
1131 while watchdog.budget().poll() == Ok(None) && started.elapsed() < Duration::from_secs(5) {
1132 std::thread::sleep(Duration::from_millis(5));
1133 }
1134 let expected = Err(MeasurementError::unavailable(SamplePoint::Periodic));
1135 assert_eq!(watchdog.budget().poll(), expected);
1136 assert_eq!(
1137 watchdog.finish(),
1138 expected,
1139 "retain the first observed failure"
1140 );
1141 }
1142
1143 #[test]
1144 fn zero_time_is_known_before_the_watchdog_can_run() {
1145 let mut watchdog = Budget::new(Some(Duration::ZERO), None)
1146 .start_with(|_, _, _| std::thread::Builder::new().spawn(|| {}))
1147 .expect("spawn")
1148 .expect("finite");
1149 let stop = watchdog
1150 .budget()
1151 .poll()
1152 .expect("clock")
1153 .expect("zero budget");
1154 assert_eq!((stop.resource, stop.limit), (Resource::Time, 0));
1155 assert_eq!(
1156 watchdog.finish().expect("clock").expect("stop").resource,
1157 Resource::Time
1158 );
1159 }
1160
1161 #[test]
1162 fn final_clock_check_does_not_depend_on_watchdog_scheduling() {
1163 let mut watchdog = Budget::new(Some(Duration::from_millis(1)), None)
1164 .start_with(|_, _, _| std::thread::Builder::new().spawn(|| {}))
1165 .expect("spawn")
1166 .expect("finite");
1167 std::thread::sleep(Duration::from_millis(3));
1168 assert_eq!(
1169 watchdog.budget().poll(),
1170 Ok(None),
1171 "injected watchdog performs no checks"
1172 );
1173 let stop = watchdog.finish().expect("clock").expect("deadline");
1174 assert_eq!((stop.resource, stop.limit), (Resource::Time, 1));
1175 assert!(stop.observed >= 1);
1176 }
1177}
1178
1179#[derive(Debug)]
1184pub struct EvaluationControl {
1185 budget: Budget,
1186 phase: Phase,
1187 identity: u64,
1188}
1189
1190impl dive_eval::HostControl for EvaluationControl {
1191 fn check(&self) -> Result<(), dive_eval::Interrupted> {
1192 match self.budget.poll() {
1193 Ok(None) => Ok(()),
1194 Ok(Some(_)) | Err(_) => Err(dive_eval::Interrupted::new(self.identity)),
1195 }
1196 }
1197}
1198
1199#[doc(hidden)]
1202#[must_use]
1203pub fn check_assumptions(model: &dive_model::Model, budget: &Budget) -> Option<crate::Verdict> {
1204 let control = match EvaluationControl::new(budget, Phase::Startup) {
1205 Ok(control) => control,
1206 Err(error) => {
1207 return Some(crate::Verdict::InternalError {
1208 message: error.to_string(),
1209 });
1210 }
1211 };
1212 let _scope = match control.enter(&model.evaluator) {
1213 Ok(scope) => scope,
1214 Err(error) => {
1215 return Some(crate::Verdict::InternalError {
1216 message: error.to_string(),
1217 });
1218 }
1219 };
1220 match model.check_assumptions() {
1221 dive_eval::AssumptionOutcome::AllTrue => None,
1222 dive_eval::AssumptionOutcome::False {
1223 property, message, ..
1224 } => Some(crate::Verdict::AssumptionFalse { property, message }),
1225 dive_eval::AssumptionOutcome::Error { error, message, .. } => Some(
1226 control
1227 .verdict(&error)
1228 .unwrap_or_else(|| crate::class::assumption_error(&error, message)),
1229 ),
1230 }
1231}
1232
1233impl EvaluationControl {
1234 pub fn new(budget: &Budget, phase: Phase) -> Result<Arc<Self>, dive_eval::HostControlConflict> {
1239 let identity = budget
1242 .signal
1243 .as_ref()
1244 .map_or(Ok(0), |signal| u64::try_from(Arc::as_ptr(signal) as usize))
1245 .map_err(|_| dive_eval::HostControlConflict)?;
1246 Ok(Arc::new(Self {
1247 budget: budget.clone(),
1248 phase,
1249 identity,
1250 }))
1251 }
1252
1253 pub fn enter(
1260 self: &Arc<Self>,
1261 evaluator: &dive_eval::Evaluator,
1262 ) -> Result<dive_eval::HostControlScope, dive_eval::HostControlConflict> {
1263 evaluator.host_control(Some(self.clone()))
1264 }
1265
1266 #[must_use]
1269 pub fn verdict(&self, error: &dive_eval::EvalError) -> Option<crate::Verdict> {
1270 if !self.owns(error) {
1271 return None;
1272 }
1273 match self.budget.poll() {
1274 Ok(Some(exhausted)) => Some(crate::Verdict::Stopped(Box::new(
1275 exhausted.during(self.phase),
1276 ))),
1277 Err(error) => Some(crate::Verdict::BudgetMeasurement { error }),
1278 Ok(None) => None,
1279 }
1280 }
1281
1282 #[must_use]
1285 pub fn owns(&self, error: &dive_eval::EvalError) -> bool {
1286 self.identity != 0
1287 && self.budget.is_armed()
1288 && !self.budget.is_unlimited()
1289 && error
1290 .interruption()
1291 .is_some_and(|interruption| interruption.token() == self.identity)
1292 }
1293}
1294
1295#[cfg(test)]
1296#[allow(clippy::expect_used, reason = "deterministic armed-control evidence")]
1297mod evaluator_controls {
1298 use super::*;
1299 use dive_eval::HostControl;
1300
1301 #[test]
1302 fn measurement_failure_interrupts_only_its_owner_and_never_fabricates_exhaustion() {
1303 let watchdog = Budget::new(None, Some(100))
1304 .start_with_sampler(
1305 |_, _, _| std::thread::Builder::new().spawn(|| {}),
1306 Sampler::Injected(Arc::new(|| Some(10))),
1307 )
1308 .expect("initial measurement")
1309 .expect("finite budget");
1310 let control = EvaluationControl::new(watchdog.budget(), Phase::Search).expect("control");
1311 assert_eq!(control.check(), Ok(()));
1312 let failure = MeasurementError::unavailable(SamplePoint::Periodic);
1313 assert_eq!(
1314 watchdog
1315 .budget()
1316 .signal
1317 .as_ref()
1318 .expect("armed")
1319 .record_sample(SamplePoint::Periodic, None, 100),
1320 Err(failure)
1321 );
1322 let error = dive_eval::EvalError::interrupted(control.check().expect_err("interrupt"));
1323 assert_eq!(
1324 control.verdict(&error),
1325 Some(crate::Verdict::BudgetMeasurement { error: failure })
1326 );
1327 let temporal =
1328 EvaluationControl::new(watchdog.budget(), Phase::Temporal).expect("same run");
1329 assert_eq!(
1330 temporal.verdict(&error),
1331 Some(crate::Verdict::BudgetMeasurement { error: failure })
1332 );
1333 let genuine = dive_eval::EvalError::general("host interrupted evaluation");
1334 assert!(control.verdict(&genuine).is_none());
1335 let other = Budget::new(Some(Duration::from_secs(3600)), None)
1336 .start()
1337 .expect("thread")
1338 .expect("watchdog");
1339 let other = EvaluationControl::new(other.budget(), Phase::Search).expect("other owner");
1340 assert!(other.verdict(&error).is_none());
1341 }
1342
1343 #[test]
1344 fn contexts_require_actual_exhaustion_of_the_same_signal_and_keep_the_current_phase() {
1345 let watchdog = Budget::new(Some(Duration::from_secs(3600)), None)
1346 .start()
1347 .expect("thread")
1348 .expect("watchdog");
1349 let budget = watchdog.budget();
1350 let search = EvaluationControl::new(budget, Phase::Search).expect("search control");
1351 let temporal = EvaluationControl::new(budget, Phase::Temporal).expect("temporal control");
1352 let fake = dive_eval::EvalError::interrupted(dive_eval::Interrupted::new(search.identity));
1353 assert!(search.owns(&fake));
1354 assert!(
1355 search.verdict(&fake).is_none(),
1356 "identity alone is not exhaustion"
1357 );
1358 budget.trip_for_test();
1359 let error = std::thread::scope(|scope| {
1360 scope
1361 .spawn(|| {
1362 dive_eval::EvalError::interrupted(search.check().expect_err("interrupted"))
1363 })
1364 .join()
1365 .expect("worker")
1366 });
1367 assert!(
1368 matches!(search.verdict(&error),Some(crate::Verdict::Stopped(stop)) if stop.phase==Phase::Search)
1369 );
1370 assert!(
1371 matches!(temporal.verdict(&error),Some(crate::Verdict::Stopped(stop)) if stop.phase==Phase::Temporal)
1372 );
1373 let other_watchdog = Budget::new(Some(Duration::from_secs(3600)), None)
1374 .start()
1375 .expect("thread")
1376 .expect("watchdog");
1377 other_watchdog.budget().trip_for_test();
1378 let other =
1379 EvaluationControl::new(other_watchdog.budget(), Phase::Capture).expect("other run");
1380 assert!(!other.owns(&error));
1381 assert!(other.verdict(&error).is_none());
1382 for unarmed in [Budget::unlimited(), Budget::new(Some(Duration::ZERO), None)] {
1383 let control = EvaluationControl::new(&unarmed, Phase::Search).expect("control");
1384 assert!(!control.owns(&error));
1385 assert!(control.verdict(&error).is_none());
1386 }
1387 let genuine = dive_eval::EvalError::general("host interrupted evaluation");
1388 assert!(search.verdict(&genuine).is_none());
1389 }
1390}
1391
1392#[cfg(test)]
1393#[allow(
1394 clippy::expect_used,
1395 clippy::panic,
1396 reason = "deterministic assumption control evidence"
1397)]
1398mod assumption_controls {
1399 use super::*;
1400
1401 const LOOP: &str = "PrintT(\"before-loop\") /\\ (\\A i \\in 1..4096: i = i)";
1402
1403 fn model(assumption: &str, options: &crate::CheckOptions) -> dive_model::Model {
1404 let source = format!(
1405 "---- MODULE ControlledAssume ----\nEXTENDS Naturals, TLC\nVARIABLE x\n\
1406 ASSUME {assumption}\nInit == x = 0\nNext == x' = x\n====\n"
1407 );
1408 let analysis = dive_sema::analyze_source(
1409 "ControlledAssume.tla",
1410 &source,
1411 &dive_sema::Options::default(),
1412 );
1413 let ir = Arc::new(dive_ir::lower(&analysis).expect("IR"));
1414 let config = dive_config::parse("INIT Init\nNEXT Next\n")
1415 .into_config()
1416 .expect("config");
1417 dive_model::bind(
1418 ir,
1419 &config,
1420 &dive_model::BindOptions {
1421 eval: options.eval,
1422 symmetry_liveness: options.symmetry_liveness,
1423 no_deadlock: false,
1424 host: None,
1425 },
1426 )
1427 .expect("bind")
1428 }
1429
1430 #[test]
1431 fn producer_assumption_loops_stop_with_their_owner_and_restore_control() {
1432 for options in [crate::CheckOptions::tlc(0, 0), crate::CheckOptions::dive(0)] {
1433 let model = model(LOOP, &options);
1434 let watchdog = Budget::new(Some(Duration::from_secs(3600)), None)
1435 .start()
1436 .expect("watchdog")
1437 .expect("finite budget");
1438 watchdog.budget().trip_for_test();
1439 assert!(matches!(
1440 check_assumptions(&model, watchdog.budget()),
1441 Some(crate::Verdict::Stopped(stop)) if stop.phase == Phase::Startup
1442 ));
1443 let prints = model.take_output();
1444 assert_eq!(prints.len(), 1);
1445 assert!(prints[0].contains("before-loop"));
1446 assert!(matches!(
1449 model.check_assumptions(),
1450 dive_eval::AssumptionOutcome::AllTrue
1451 ));
1452 assert_eq!(model.take_output().len(), 1);
1453 }
1454 }
1455
1456 #[test]
1457 fn real_assumption_failures_keep_their_class_before_a_checkpoint() {
1458 for options in [crate::CheckOptions::tlc(0, 0), crate::CheckOptions::dive(0)] {
1459 let watchdog = Budget::new(Some(Duration::from_secs(3600)), None)
1460 .start()
1461 .expect("watchdog")
1462 .expect("finite budget");
1463 watchdog.budget().trip_for_test();
1464 for budget in [&Budget::unlimited(), watchdog.budget()] {
1467 assert!(matches!(
1468 check_assumptions(&model("FALSE", &options), budget),
1469 Some(crate::Verdict::AssumptionFalse { .. })
1470 ));
1471 assert!(matches!(
1472 check_assumptions(&model("1 \\div 0 = 0", &options), budget),
1473 Some(crate::Verdict::EvaluationError {
1474 site: crate::ErrorSite::Assumption,
1475 code: 2105,
1476 reported: 2105,
1477 ..
1478 })
1479 ));
1480 assert_eq!(check_assumptions(&model("TRUE", &options), budget), None);
1481 }
1482 }
1483 }
1484
1485 #[test]
1486 fn assumption_measurement_failure_remains_a_measurement_failure() {
1487 for options in [crate::CheckOptions::tlc(0, 0), crate::CheckOptions::dive(0)] {
1488 let model = model(LOOP, &options);
1489 let watchdog = Budget::new(None, Some(100))
1490 .start_with_sampler(
1491 |_, _, _| std::thread::Builder::new().spawn(|| {}),
1492 Sampler::Injected(Arc::new(|| Some(10))),
1493 )
1494 .expect("initial measurement")
1495 .expect("finite budget");
1496 let failure = MeasurementError::unavailable(SamplePoint::Periodic);
1497 assert_eq!(
1498 watchdog
1499 .budget()
1500 .signal
1501 .as_ref()
1502 .expect("armed")
1503 .record_sample(SamplePoint::Periodic, None, 100),
1504 Err(failure)
1505 );
1506 assert_eq!(
1507 check_assumptions(&model, watchdog.budget()),
1508 Some(crate::Verdict::BudgetMeasurement { error: failure })
1509 );
1510 assert_eq!(model.take_output().len(), 1);
1511 }
1512 }
1513}