feature: implement WAIT & WAKE operations of FreeBSD _umtx_op syscall for Futex support

5 files changed, 521 insertions, 1 deletions

diff --git a/src/tools/miri/ci/ci.sh b/src/tools/miri/ci/ci.sh
index 7155d692ee5..b690bd9cd2b 100755
--- a/src/tools/miri/ci/ci.sh
+++ b/src/tools/miri/ci/ci.sh
@@ -164,7 +164,7 @@ case $HOST_TARGET in
     # Partially supported targets (tier 2)
     BASIC="empty_main integer heap_alloc libc-mem vec string btreemap" # ensures we have the basics: pre-main code, system allocator
     UNIX="hello panic/panic panic/unwind concurrency/simple atomic libc-mem libc-misc libc-random env num_cpus" # the things that are very similar across all Unixes, and hence easily supported there
-    TEST_TARGET=x86_64-unknown-freebsd run_tests_minimal $BASIC $UNIX time hashmap random threadname pthread fs libc-pipe
+    TEST_TARGET=x86_64-unknown-freebsd run_tests_minimal $BASIC $UNIX time hashmap random threadname pthread fs libc-pipe concurrency sync
     TEST_TARGET=i686-unknown-freebsd   run_tests_minimal $BASIC $UNIX time hashmap random threadname pthread fs libc-pipe
     TEST_TARGET=aarch64-linux-android  run_tests_minimal $BASIC $UNIX time hashmap random sync concurrency thread epoll eventfd
     TEST_TARGET=wasm32-wasip2          run_tests_minimal $BASIC wasm
diff --git a/src/tools/miri/src/shims/unix/freebsd/foreign_items.rs b/src/tools/miri/src/shims/unix/freebsd/foreign_items.rs
index 08d06fe5d4c..21a386b2927 100644
--- a/src/tools/miri/src/shims/unix/freebsd/foreign_items.rs
+++ b/src/tools/miri/src/shims/unix/freebsd/foreign_items.rs
@@ -2,6 +2,7 @@ use rustc_middle::ty::Ty;
 use rustc_span::Symbol;
 use rustc_target::callconv::{Conv, FnAbi};
 
+use super::sync::EvalContextExt as _;
 use crate::shims::unix::*;
 use crate::*;
 
@@ -55,6 +56,13 @@ pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
                 this.write_scalar(res, dest)?;
             }
 
+            // Synchronization primitives
+            "_umtx_op" => {
+                let [obj, op, val, uaddr, uaddr2] =
+                    this.check_shim(abi, Conv::C, link_name, args)?;
+                this._umtx_op(obj, op, val, uaddr, uaddr2, dest)?;
+            }
+
             // File related shims
             // For those, we both intercept `func` and `call@FBSD_1.0` symbols cases
             // since freebsd 12 the former form can be expected.
diff --git a/src/tools/miri/src/shims/unix/freebsd/mod.rs b/src/tools/miri/src/shims/unix/freebsd/mod.rs
index 09c6507b24f..50fb2b9d328 100644
--- a/src/tools/miri/src/shims/unix/freebsd/mod.rs
+++ b/src/tools/miri/src/shims/unix/freebsd/mod.rs
@@ -1 +1,2 @@
 pub mod foreign_items;
+pub mod sync;
diff --git a/src/tools/miri/src/shims/unix/freebsd/sync.rs b/src/tools/miri/src/shims/unix/freebsd/sync.rs
new file mode 100644
index 00000000000..54650f35b2c
--- /dev/null
+++ b/src/tools/miri/src/shims/unix/freebsd/sync.rs
@@ -0,0 +1,251 @@
+//! Contains FreeBSD-specific synchronization functions
+
+use core::time::Duration;
+
+use crate::concurrency::sync::FutexRef;
+use crate::*;
+
+pub struct FreeBsdFutex {
+    futex: FutexRef,
+}
+
+/// Extended variant of the `timespec` struct.
+pub struct UmtxTime {
+    timeout: Duration,
+    abs_time: bool,
+    timeout_clock: TimeoutClock,
+}
+
+impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
+pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
+    /// Implementation of the FreeBSD [`_umtx_op`](https://man.freebsd.org/cgi/man.cgi?query=_umtx_op&sektion=2&manpath=FreeBSD+14.2-RELEASE+and+Ports) syscall.
+    /// This is used for futex operations on FreeBSD.
+    ///
+    /// `obj`: a pointer to the futex object (can be a lot of things, mostly *AtomicU32)
+    /// `op`: the futex operation to run
+    /// `val`: the current value of the object as a `c_long` (for wait/wake)
+    /// `uaddr`: `op`-specific optional parameter, pointer-sized integer or pointer to an `op`-specific struct
+    /// `uaddr2`: `op`-specific optional parameter, pointer-sized integer or pointer to an `op`-specific struct
+    /// `dest`: the place this syscall returns to, 0 for success, -1 for failure
+    ///
+    /// # Note
+    /// Curently only the WAIT and WAKE operations are implemented.
+    fn _umtx_op(
+        &mut self,
+        obj: &OpTy<'tcx>,
+        op: &OpTy<'tcx>,
+        val: &OpTy<'tcx>,
+        uaddr: &OpTy<'tcx>,
+        uaddr2: &OpTy<'tcx>,
+        dest: &MPlaceTy<'tcx>,
+    ) -> InterpResult<'tcx> {
+        let this = self.eval_context_mut();
+
+        let obj = this.read_pointer(obj)?;
+        let op = this.read_scalar(op)?.to_i32()?;
+        let val = this.read_target_usize(val)?;
+        let uaddr = this.read_target_usize(uaddr)?;
+        let uaddr2 = this.read_pointer(uaddr2)?;
+
+        let wait = this.eval_libc_i32("UMTX_OP_WAIT");
+        let wait_uint = this.eval_libc_i32("UMTX_OP_WAIT_UINT");
+        let wait_uint_private = this.eval_libc_i32("UMTX_OP_WAIT_UINT_PRIVATE");
+
+        let wake = this.eval_libc_i32("UMTX_OP_WAKE");
+        let wake_private = this.eval_libc_i32("UMTX_OP_WAKE_PRIVATE");
+
+        let timespec_layout = this.libc_ty_layout("timespec");
+        let umtx_time_layout = this.libc_ty_layout("_umtx_time");
+        assert!(
+            timespec_layout.size != umtx_time_layout.size,
+            "`struct timespec` and `struct _umtx_time` should have different sizes."
+        );
+
+        match op {
+            // UMTX_OP_WAIT_UINT and UMTX_OP_WAIT_UINT_PRIVATE only differ in whether they work across
+            // processes or not. For Miri, we can treat them the same.
+            op if op == wait || op == wait_uint || op == wait_uint_private => {
+                let obj_layout =
+                    if op == wait { this.machine.layouts.isize } else { this.machine.layouts.u32 };
+                let obj = this.ptr_to_mplace(obj, obj_layout);
+
+                // Read the Linux futex wait implementation in Miri to understand why this fence is needed.
+                this.atomic_fence(AtomicFenceOrd::SeqCst)?;
+                let obj_val = this
+                    .read_scalar_atomic(&obj, AtomicReadOrd::Acquire)?
+                    .to_bits(obj_layout.size)?; // isize and u32 can have different sizes
+
+                if obj_val == u128::from(val) {
+                    // This cannot fail since we already did an atomic acquire read on that pointer.
+                    // Acquire reads are only allowed on mutable memory.
+                    let futex_ref = this
+                        .get_sync_or_init(obj.ptr(), |_| FreeBsdFutex { futex: Default::default() })
+                        .unwrap()
+                        .futex
+                        .clone();
+
+                    // From the manual:
+                    // The timeout is specified by passing either the address of `struct timespec`, or its
+                    // extended variant, `struct _umtx_time`, as the `uaddr2` argument of _umtx_op().
+                    // They are distinguished by the `uaddr` value, which must be equal
+                    // to the size of the structure pointed to by `uaddr2`, casted to uintptr_t.
+                    let timeout = if this.ptr_is_null(uaddr2)? {
+                        // no timeout parameter
+                        None
+                    } else {
+                        if uaddr == umtx_time_layout.size.bytes() {
+                            // `uaddr2` points to a `struct _umtx_time`.
+                            let umtx_time_place = this.ptr_to_mplace(uaddr2, umtx_time_layout);
+
+                            let umtx_time = match this.read_umtx_time(&umtx_time_place)? {
+                                Some(ut) => ut,
+                                None => {
+                                    return this
+                                        .set_last_error_and_return(LibcError("EINVAL"), dest);
+                                }
+                            };
+
+                            let anchor = if umtx_time.abs_time {
+                                TimeoutAnchor::Absolute
+                            } else {
+                                TimeoutAnchor::Relative
+                            };
+
+                            Some((umtx_time.timeout_clock, anchor, umtx_time.timeout))
+                        } else if uaddr == timespec_layout.size.bytes() {
+                            // RealTime clock can't be used in isolation mode.
+                            this.check_no_isolation("`_umtx_op` with `timespec` timeout")?;
+
+                            // `uaddr2` points to a `struct timespec`.
+                            let timespec = this.ptr_to_mplace(uaddr2, timespec_layout);
+                            let duration = match this.read_timespec(&timespec)? {
+                                Some(duration) => duration,
+                                None => {
+                                    return this
+                                        .set_last_error_and_return(LibcError("EINVAL"), dest);
+                                }
+                            };
+
+                            // FreeBSD does not seem to document which clock is used when the timeout
+                            // is passed as a `struct timespec*`. Based on discussions online and the source
+                            // code (umtx_copyin_umtx_time() in kern_umtx.c), it seems to default to CLOCK_REALTIME,
+                            // so that's what we also do.
+                            // Discussion in golang: https://github.com/golang/go/issues/17168#issuecomment-250235271
+                            Some((TimeoutClock::RealTime, TimeoutAnchor::Relative, duration))
+                        } else {
+                            return this.set_last_error_and_return(LibcError("EINVAL"), dest);
+                        }
+                    };
+
+                    let dest = dest.clone();
+                    this.futex_wait(
+                        futex_ref,
+                        u32::MAX, // we set the bitset to include all bits
+                        timeout,
+                        callback!(
+                            @capture<'tcx> {
+                                dest: MPlaceTy<'tcx>,
+                            }
+                            |ecx, unblock: UnblockKind| match unblock {
+                                UnblockKind::Ready => {
+                                    // From the manual:
+                                    // If successful, all requests, except UMTX_SHM_CREAT and UMTX_SHM_LOOKUP
+                                    // sub-requests of the UMTX_OP_SHM request, will return zero.
+                                    ecx.write_int(0, &dest)
+                                }
+                                UnblockKind::TimedOut => {
+                                    ecx.set_last_error_and_return(LibcError("ETIMEDOUT"), &dest)
+                                }
+                            }
+                        ),
+                    );
+                    interp_ok(())
+                } else {
+                    // The manual doesn’t specify what should happen if the futex value doesn’t match the expected one.
+                    // On FreeBSD 14.2, testing shows that WAIT operations return 0 even when the value is incorrect.
+                    this.write_int(0, dest)?;
+                    interp_ok(())
+                }
+            }
+            // UMTX_OP_WAKE and UMTX_OP_WAKE_PRIVATE only differ in whether they work across
+            // processes or not. For Miri, we can treat them the same.
+            op if op == wake || op == wake_private => {
+                let Some(futex_ref) =
+                    this.get_sync_or_init(obj, |_| FreeBsdFutex { futex: Default::default() })
+                else {
+                    // From Linux implemenation:
+                    // No AllocId, or no live allocation at that AllocId.
+                    // Return an error code. (That seems nicer than silently doing something non-intuitive.)
+                    // This means that if an address gets reused by a new allocation,
+                    // we'll use an independent futex queue for this... that seems acceptable.
+                    return this.set_last_error_and_return(LibcError("EFAULT"), dest);
+                };
+                let futex_ref = futex_ref.futex.clone();
+
+                // Saturating cast for when usize is smaller than u64.
+                let count = usize::try_from(val).unwrap_or(usize::MAX);
+
+                // Read the Linux futex wake implementation in Miri to understand why this fence is needed.
+                this.atomic_fence(AtomicFenceOrd::SeqCst)?;
+
+                // `_umtx_op` doesn't return the amount of woken threads.
+                let _woken = this.futex_wake(
+                    &futex_ref,
+                    u32::MAX, // we set the bitset to include all bits
+                    count,
+                )?;
+
+                // From the manual:
+                // If successful, all requests, except UMTX_SHM_CREAT and UMTX_SHM_LOOKUP
+                // sub-requests of the UMTX_OP_SHM request, will return zero.
+                this.write_int(0, dest)?;
+                interp_ok(())
+            }
+            op => {
+                throw_unsup_format!("Miri does not support `_umtx_op` syscall with op={}", op)
+            }
+        }
+    }
+
+    /// Parses a `_umtx_time` struct.
+    /// Returns `None` if the underlying `timespec` struct is invalid.
+    fn read_umtx_time(&mut self, ut: &MPlaceTy<'tcx>) -> InterpResult<'tcx, Option<UmtxTime>> {
+        let this = self.eval_context_mut();
+        // Only flag allowed is UMTX_ABSTIME.
+        let abs_time = this.eval_libc_u32("UMTX_ABSTIME");
+
+        let timespec_place = this.project_field(ut, 0)?;
+        // Inner `timespec` must still be valid.
+        let duration = match this.read_timespec(&timespec_place)? {
+            Some(dur) => dur,
+            None => return interp_ok(None),
+        };
+
+        let flags_place = this.project_field(ut, 1)?;
+        let flags = this.read_scalar(&flags_place)?.to_u32()?;
+        let abs_time_flag = flags == abs_time;
+
+        let clock_id_place = this.project_field(ut, 2)?;
+        let clock_id = this.read_scalar(&clock_id_place)?.to_i32()?;
+        let timeout_clock = this.translate_umtx_time_clock_id(clock_id)?;
+
+        interp_ok(Some(UmtxTime { timeout: duration, abs_time: abs_time_flag, timeout_clock }))
+    }
+
+    /// Translate raw FreeBSD clockid to a Miri TimeoutClock.
+    /// FIXME: share this code with the pthread and clock_gettime shims.
+    fn translate_umtx_time_clock_id(&mut self, raw_id: i32) -> InterpResult<'tcx, TimeoutClock> {
+        let this = self.eval_context_mut();
+
+        let timeout = if raw_id == this.eval_libc_i32("CLOCK_REALTIME") {
+            // RealTime clock can't be used in isolation mode.
+            this.check_no_isolation("`_umtx_op` with `CLOCK_REALTIME` timeout")?;
+            TimeoutClock::RealTime
+        } else if raw_id == this.eval_libc_i32("CLOCK_MONOTONIC") {
+            TimeoutClock::Monotonic
+        } else {
+            throw_unsup_format!("unsupported clock id {raw_id}");
+        };
+        interp_ok(timeout)
+    }
+}
diff --git a/src/tools/miri/tests/pass-dep/concurrency/freebsd-futex.rs b/src/tools/miri/tests/pass-dep/concurrency/freebsd-futex.rs
new file mode 100644
index 00000000000..38a0bf58148
--- /dev/null
+++ b/src/tools/miri/tests/pass-dep/concurrency/freebsd-futex.rs
@@ -0,0 +1,260 @@
+//@only-target: freebsd
+//@compile-flags: -Zmiri-preemption-rate=0 -Zmiri-disable-isolation
+
+use std::mem::{self, MaybeUninit};
+use std::ptr::{self, addr_of};
+use std::sync::atomic::AtomicU32;
+use std::time::Instant;
+use std::{io, thread};
+
+fn wait_wake() {
+    fn wake_nobody() {
+        // Current thread waits on futex.
+        // New thread wakes up 0 threads waiting on that futex.
+        // Current thread should time out.
+        static mut FUTEX: u32 = 0;
+
+        let waker = thread::spawn(|| {
+            unsafe {
+                assert_eq!(
+                    libc::_umtx_op(
+                        addr_of!(FUTEX) as *mut _,
+                        libc::UMTX_OP_WAKE_PRIVATE,
+                        0, // wake up 0 waiters
+                        ptr::null_mut::<libc::c_void>(),
+                        ptr::null_mut::<libc::c_void>(),
+                    ),
+                    0
+                );
+            }
+        });
+
+        // 10ms should be enough.
+        let mut timeout = libc::timespec { tv_sec: 0, tv_nsec: 10_000_000 };
+        let timeout_size_arg =
+            ptr::without_provenance_mut::<libc::c_void>(mem::size_of::<libc::timespec>());
+        unsafe {
+            assert_eq!(
+                libc::_umtx_op(
+                    addr_of!(FUTEX) as *mut _,
+                    libc::UMTX_OP_WAIT_UINT_PRIVATE,
+                    0,
+                    timeout_size_arg,
+                    &mut timeout as *mut _ as _,
+                ),
+                -1
+            );
+            // Main thread did not get woken up, so it timed out.
+            assert_eq!(io::Error::last_os_error().raw_os_error().unwrap(), libc::ETIMEDOUT);
+        }
+
+        waker.join().unwrap();
+    }
+
+    fn wake_two_of_three() {
+        // We create 2 threads that wait on a futex with a 100ms timeout.
+        // The main thread wakes up 2 threads waiting on this futex and after this
+        // checks that only those threads woke up and the other one timed out.
+        static mut FUTEX: u32 = 0;
+
+        fn waiter() -> bool {
+            let mut timeout = libc::timespec { tv_sec: 0, tv_nsec: 100_000_000 };
+            let timeout_size_arg =
+                ptr::without_provenance_mut::<libc::c_void>(mem::size_of::<libc::timespec>());
+            unsafe {
+                libc::_umtx_op(
+                    addr_of!(FUTEX) as *mut _,
+                    libc::UMTX_OP_WAIT_UINT_PRIVATE,
+                    0, // FUTEX is 0
+                    timeout_size_arg,
+                    &mut timeout as *mut _ as _,
+                );
+                // Return true if this thread woke up.
+                io::Error::last_os_error().raw_os_error().unwrap() != libc::ETIMEDOUT
+            }
+        }
+
+        let t1 = thread::spawn(waiter);
+        let t2 = thread::spawn(waiter);
+        let t3 = thread::spawn(waiter);
+
+        // Run all the waiters, so they can go to sleep.
+        thread::yield_now();
+
+        // Wake up 2 thread and make sure 1 is still waiting.
+        unsafe {
+            assert_eq!(
+                libc::_umtx_op(
+                    addr_of!(FUTEX) as *mut _,
+                    libc::UMTX_OP_WAKE_PRIVATE,
+                    2,
+                    ptr::null_mut::<libc::c_void>(),
+                    ptr::null_mut::<libc::c_void>(),
+                ),
+                0
+            );
+        }
+
+        // Treat the booleans as numbers to simplify checking how many threads were woken up.
+        let t1 = t1.join().unwrap() as usize;
+        let t2 = t2.join().unwrap() as usize;
+        let t3 = t3.join().unwrap() as usize;
+        let woken_up_count = t1 + t2 + t3;
+        assert!(woken_up_count == 2, "Expected 2 threads to wake up got: {woken_up_count}");
+    }
+
+    wake_nobody();
+    wake_two_of_three();
+}
+
+fn wake_dangling() {
+    let futex = Box::new(0);
+    let ptr: *const u32 = &*futex;
+    drop(futex);
+
+    // Expect error since this is now "unmapped" memory.
+    unsafe {
+        assert_eq!(
+            libc::_umtx_op(
+                ptr as *const AtomicU32 as *mut _,
+                libc::UMTX_OP_WAKE_PRIVATE,
+                0,
+                ptr::null_mut::<libc::c_void>(),
+                ptr::null_mut::<libc::c_void>(),
+            ),
+            -1
+        );
+        assert_eq!(io::Error::last_os_error().raw_os_error().unwrap(), libc::EFAULT);
+    }
+}
+
+fn wait_wrong_val() {
+    let futex: u32 = 123;
+
+    // Wait with a wrong value just returns 0
+    unsafe {
+        assert_eq!(
+            libc::_umtx_op(
+                ptr::from_ref(&futex).cast_mut().cast(),
+                libc::UMTX_OP_WAIT_UINT_PRIVATE,
+                456,
+                ptr::null_mut::<libc::c_void>(),
+                ptr::null_mut::<libc::c_void>(),
+            ),
+            0
+        );
+    }
+}
+
+fn wait_relative_timeout() {
+    fn without_timespec() {
+        let start = Instant::now();
+
+        let futex: u32 = 123;
+
+        let mut timeout = libc::timespec { tv_sec: 0, tv_nsec: 200_000_000 };
+        let timeout_size_arg =
+            ptr::without_provenance_mut::<libc::c_void>(mem::size_of::<libc::timespec>());
+        // Wait for 200ms, with nobody waking us up early
+        unsafe {
+            assert_eq!(
+                libc::_umtx_op(
+                    ptr::from_ref(&futex).cast_mut().cast(),
+                    libc::UMTX_OP_WAIT_UINT_PRIVATE,
+                    123,
+                    timeout_size_arg,
+                    &mut timeout as *mut _ as _,
+                ),
+                -1
+            );
+            assert_eq!(io::Error::last_os_error().raw_os_error().unwrap(), libc::ETIMEDOUT);
+        }
+
+        assert!((200..1000).contains(&start.elapsed().as_millis()));
+    }
+
+    fn with_timespec() {
+        let futex: u32 = 123;
+        let mut timeout = libc::_umtx_time {
+            _timeout: libc::timespec { tv_sec: 0, tv_nsec: 200_000_000 },
+            _flags: 0,
+            _clockid: libc::CLOCK_MONOTONIC as u32,
+        };
+        let timeout_size_arg =
+            ptr::without_provenance_mut::<libc::c_void>(mem::size_of::<libc::_umtx_time>());
+
+        let start = Instant::now();
+
+        // Wait for 200ms, with nobody waking us up early
+        unsafe {
+            assert_eq!(
+                libc::_umtx_op(
+                    ptr::from_ref(&futex).cast_mut().cast(),
+                    libc::UMTX_OP_WAIT_UINT_PRIVATE,
+                    123,
+                    timeout_size_arg,
+                    &mut timeout as *mut _ as _,
+                ),
+                -1
+            );
+            assert_eq!(io::Error::last_os_error().raw_os_error().unwrap(), libc::ETIMEDOUT);
+        }
+        assert!((200..1000).contains(&start.elapsed().as_millis()));
+    }
+
+    without_timespec();
+    with_timespec();
+}
+
+fn wait_absolute_timeout() {
+    let start = Instant::now();
+
+    // Get the current monotonic timestamp as timespec.
+    let mut timeout = unsafe {
+        let mut now: MaybeUninit<libc::timespec> = MaybeUninit::uninit();
+        assert_eq!(libc::clock_gettime(libc::CLOCK_MONOTONIC, now.as_mut_ptr()), 0);
+        now.assume_init()
+    };
+
+    // Add 200ms.
+    timeout.tv_nsec += 200_000_000;
+    if timeout.tv_nsec > 1_000_000_000 {
+        timeout.tv_nsec -= 1_000_000_000;
+        timeout.tv_sec += 1;
+    }
+
+    // Create umtx_timeout struct with that absolute timeout.
+    let umtx_timeout = libc::_umtx_time {
+        _timeout: timeout,
+        _flags: libc::UMTX_ABSTIME,
+        _clockid: libc::CLOCK_MONOTONIC as u32,
+    };
+    let umtx_timeout_ptr = &umtx_timeout as *const _;
+    let umtx_timeout_size = ptr::without_provenance_mut(mem::size_of_val(&umtx_timeout));
+
+    let futex: u32 = 123;
+
+    // Wait for 200ms from now, with nobody waking us up early.
+    unsafe {
+        assert_eq!(
+            libc::_umtx_op(
+                ptr::from_ref(&futex).cast_mut().cast(),
+                libc::UMTX_OP_WAIT_UINT_PRIVATE,
+                123,
+                umtx_timeout_size,
+                umtx_timeout_ptr as *mut _,
+            ),
+            -1
+        );
+        assert_eq!(io::Error::last_os_error().raw_os_error().unwrap(), libc::ETIMEDOUT);
+    }
+    assert!((200..1000).contains(&start.elapsed().as_millis()));
+}
+
+fn main() {
+    wait_wake();
+    wake_dangling();
+    wait_wrong_val();
+    wait_relative_timeout();
+    wait_absolute_timeout();
+}