path: root/rust/kernel/time/hrtimer.rs

// SPDX-License-Identifier: GPL-2.0

//! Intrusive high resolution timers.
//!
//! Allows running timer callbacks without doing allocations at the time of
//! starting the timer. For now, only one timer per type is allowed.
//!
//! # Vocabulary
//!
//! States:
//!
//! - Stopped: initialized but not started, or cancelled, or not restarted.
//! - Started: initialized and started or restarted.
//! - Running: executing the callback.
//!
//! Operations:
//!
//! * Start
//! * Cancel
//! * Restart
//!
//! Events:
//!
//! * Expire
//!
//! ## State Diagram
//!
//! ```text
//!                                                   Return NoRestart
//!                       +---------------------------------------------------------------------+
//!                       |                                                                     |
//!                       |                                                                     |
//!                       |                                                                     |
//!                       |                                         Return Restart              |
//!                       |                                      +------------------------+     |
//!                       |                                      |                        |     |
//!                       |                                      |                        |     |
//!                       v                                      v                        |     |
//!           +-----------------+      Start      +------------------+           +--------+-----+--+
//!           |                 +---------------->|                  |           |                 |
//! Init      |                 |                 |                  |  Expire   |                 |
//! --------->|    Stopped      |                 |      Started     +---------->|     Running     |
//!           |                 |     Cancel      |                  |           |                 |
//!           |                 |<----------------+                  |           |                 |
//!           +-----------------+                 +---------------+--+           +-----------------+
//!                                                     ^         |
//!                                                     |         |
//!                                                     +---------+
//!                                                      Restart
//! ```
//!
//!
//! A timer is initialized in the **stopped** state. A stopped timer can be
//! **started** by the `start` operation, with an **expiry** time. After the
//! `start` operation, the timer is in the **started** state. When the timer
//! **expires**, the timer enters the **running** state and the handler is
//! executed. After the handler has returned, the timer may enter the
//! **started* or **stopped** state, depending on the return value of the
//! handler. A timer in the **started** or **running** state may be **canceled**
//! by the `cancel` operation. A timer that is cancelled enters the **stopped**
//! state.
//!
//! A `cancel` or `restart` operation on a timer in the **running** state takes
//! effect after the handler has returned and the timer has transitioned
//! out of the **running** state.
//!
//! A `restart` operation on a timer in the **stopped** state is equivalent to a
//! `start` operation.
//!
//! When a type implements both `HrTimerPointer` and `Clone`, it is possible to
//! issue the `start` operation while the timer is in the **started** state. In
//! this case the `start` operation is equivalent to the `restart` operation.
//!
//! # Examples
//!
//! ## Using an intrusive timer living in a [`Box`]
//!
//! ```
//! # use kernel::{
//! #     alloc::flags,
//! #     impl_has_hr_timer,
//! #     prelude::*,
//! #     sync::{
//! #         atomic::{ordering, Atomic},
//! #         completion::Completion,
//! #         Arc,
//! #     },
//! #     time::{
//! #         hrtimer::{
//! #             RelativeMode, HrTimer, HrTimerCallback, HrTimerPointer,
//! #             HrTimerRestart, HrTimerCallbackContext
//! #         },
//! #         Delta, Monotonic,
//! #     },
//! # };
//!
//! #[pin_data]
//! struct Shared {
//!     #[pin]
//!     flag: Atomic<u64>,
//!     #[pin]
//!     cond: Completion,
//! }
//!
//! impl Shared {
//!     fn new() -> impl PinInit<Self> {
//!         pin_init!(Self {
//!             flag <- Atomic::new(0),
//!             cond <- Completion::new(),
//!         })
//!     }
//! }
//!
//! #[pin_data]
//! struct BoxIntrusiveHrTimer {
//!     #[pin]
//!     timer: HrTimer<Self>,
//!     shared: Arc<Shared>,
//! }
//!
//! impl BoxIntrusiveHrTimer {
//!     fn new() -> impl PinInit<Self, kernel::error::Error> {
//!         try_pin_init!(Self {
//!             timer <- HrTimer::new(),
//!             shared: Arc::pin_init(Shared::new(), flags::GFP_KERNEL)?,
//!         })
//!     }
//! }
//!
//! impl HrTimerCallback for BoxIntrusiveHrTimer {
//!     type Pointer<'a> = Pin<KBox<Self>>;
//!
//!     fn run(this: Pin<&mut Self>, _ctx: HrTimerCallbackContext<'_, Self>) -> HrTimerRestart {
//!         pr_info!("Timer called\n");
//!
//!         let flag = this.shared.flag.fetch_add(1, ordering::Full);
//!         this.shared.cond.complete_all();
//!
//!         if flag == 4 {
//!             HrTimerRestart::NoRestart
//!         } else {
//!             HrTimerRestart::Restart
//!         }
//!     }
//! }
//!
//! impl_has_hr_timer! {
//!     impl HasHrTimer<Self> for BoxIntrusiveHrTimer {
//!         mode: RelativeMode<Monotonic>, field: self.timer
//!     }
//! }
//!
//! let has_timer = Box::pin_init(BoxIntrusiveHrTimer::new(), GFP_KERNEL)?;
//! let shared = has_timer.shared.clone();
//! let _handle = has_timer.start(Delta::from_micros(200));
//!
//! while shared.flag.load(ordering::Relaxed) != 5 {
//!     shared.cond.wait_for_completion();
//! }
//!
//! pr_info!("Counted to 5\n");
//! # Ok::<(), kernel::error::Error>(())
//! ```
//!
//! ## Using an intrusive timer in an [`Arc`]
//!
//! ```
//! # use kernel::{
//! #     alloc::flags,
//! #     impl_has_hr_timer,
//! #     prelude::*,
//! #     sync::{
//! #         atomic::{ordering, Atomic},
//! #         completion::Completion,
//! #         Arc, ArcBorrow,
//! #     },
//! #     time::{
//! #         hrtimer::{
//! #             RelativeMode, HrTimer, HrTimerCallback, HrTimerPointer, HrTimerRestart,
//! #             HasHrTimer, HrTimerCallbackContext
//! #         },
//! #         Delta, Monotonic,
//! #     },
//! # };
//!
//! #[pin_data]
//! struct ArcIntrusiveHrTimer {
//!     #[pin]
//!     timer: HrTimer<Self>,
//!     #[pin]
//!     flag: Atomic<u64>,
//!     #[pin]
//!     cond: Completion,
//! }
//!
//! impl ArcIntrusiveHrTimer {
//!     fn new() -> impl PinInit<Self> {
//!         pin_init!(Self {
//!             timer <- HrTimer::new(),
//!             flag <- Atomic::new(0),
//!             cond <- Completion::new(),
//!         })
//!     }
//! }
//!
//! impl HrTimerCallback for ArcIntrusiveHrTimer {
//!     type Pointer<'a> = Arc<Self>;
//!
//!     fn run(
//!         this: ArcBorrow<'_, Self>,
//!         _ctx: HrTimerCallbackContext<'_, Self>,
//!     ) -> HrTimerRestart {
//!         pr_info!("Timer called\n");
//!
//!         let flag = this.flag.fetch_add(1, ordering::Full);
//!         this.cond.complete_all();
//!
//!         if flag == 4 {
//!             HrTimerRestart::NoRestart
//!         } else {
//!             HrTimerRestart::Restart
//!         }
//!     }
//! }
//!
//! impl_has_hr_timer! {
//!     impl HasHrTimer<Self> for ArcIntrusiveHrTimer {
//!         mode: RelativeMode<Monotonic>, field: self.timer
//!     }
//! }
//!
//! let has_timer = Arc::pin_init(ArcIntrusiveHrTimer::new(), GFP_KERNEL)?;
//! let _handle = has_timer.clone().start(Delta::from_micros(200));
//!
//! while has_timer.flag.load(ordering::Relaxed) != 5 {
//!     has_timer.cond.wait_for_completion();
//! }
//!
//! pr_info!("Counted to 5\n");
//! # Ok::<(), kernel::error::Error>(())
//! ```
//!
//! ## Using a stack-based timer
//!
//! ```
//! # use kernel::{
//! #     impl_has_hr_timer,
//! #     prelude::*,
//! #     sync::{
//! #         atomic::{ordering, Atomic},
//! #         completion::Completion,
//! #     },
//! #     time::{
//! #         hrtimer::{
//! #             ScopedHrTimerPointer, HrTimer, HrTimerCallback, HrTimerPointer, HrTimerRestart,
//! #             HasHrTimer, RelativeMode, HrTimerCallbackContext
//! #         },
//! #         Delta, Monotonic,
//! #     },
//! # };
//! # use pin_init::stack_pin_init;
//!
//! #[pin_data]
//! struct IntrusiveHrTimer {
//!     #[pin]
//!     timer: HrTimer<Self>,
//!     #[pin]
//!     flag: Atomic<u64>,
//!     #[pin]
//!     cond: Completion,
//! }
//!
//! impl IntrusiveHrTimer {
//!     fn new() -> impl PinInit<Self> {
//!         pin_init!(Self {
//!             timer <- HrTimer::new(),
//!             flag <- Atomic::new(0),
//!             cond <- Completion::new(),
//!         })
//!     }
//! }
//!
//! impl HrTimerCallback for IntrusiveHrTimer {
//!     type Pointer<'a> = Pin<&'a Self>;
//!
//!     fn run(this: Pin<&Self>, _ctx: HrTimerCallbackContext<'_, Self>) -> HrTimerRestart {
//!         pr_info!("Timer called\n");
//!
//!         this.flag.store(1, ordering::Release);
//!         this.cond.complete_all();
//!
//!         HrTimerRestart::NoRestart
//!     }
//! }
//!
//! impl_has_hr_timer! {
//!     impl HasHrTimer<Self> for IntrusiveHrTimer {
//!         mode: RelativeMode<Monotonic>, field: self.timer
//!     }
//! }
//!
//! stack_pin_init!( let has_timer = IntrusiveHrTimer::new() );
//! has_timer.as_ref().start_scoped(Delta::from_micros(200), || {
//!     while has_timer.flag.load(ordering::Relaxed) != 1 {
//!         has_timer.cond.wait_for_completion();
//!     }
//! });
//!
//! pr_info!("Flag raised\n");
//! # Ok::<(), kernel::error::Error>(())
//! ```
//!
//! ## Using a mutable stack-based timer
//!
//! ```
//! # use kernel::{
//! #     alloc::flags,
//! #     impl_has_hr_timer,
//! #     prelude::*,
//! #     sync::{
//! #         atomic::{ordering, Atomic},
//! #         completion::Completion,
//! #         Arc,
//! #     },
//! #     time::{
//! #         hrtimer::{
//! #             ScopedHrTimerPointer, HrTimer, HrTimerCallback, HrTimerPointer, HrTimerRestart,
//! #             HasHrTimer, RelativeMode, HrTimerCallbackContext
//! #         },
//! #         Delta, Monotonic,
//! #     },
//! # };
//! # use pin_init::stack_try_pin_init;
//!
//! #[pin_data]
//! struct Shared {
//!     #[pin]
//!     flag: Atomic<u64>,
//!     #[pin]
//!     cond: Completion,
//! }
//!
//! impl Shared {
//!     fn new() -> impl PinInit<Self> {
//!         pin_init!(Self {
//!             flag <- Atomic::new(0),
//!             cond <- Completion::new(),
//!         })
//!     }
//! }
//!
//! #[pin_data]
//! struct IntrusiveHrTimer {
//!     #[pin]
//!     timer: HrTimer<Self>,
//!     shared: Arc<Shared>,
//! }
//!
//! impl IntrusiveHrTimer {
//!     fn new() -> impl PinInit<Self, kernel::error::Error> {
//!         try_pin_init!(Self {
//!             timer <- HrTimer::new(),
//!             shared: Arc::pin_init(Shared::new(), flags::GFP_KERNEL)?,
//!         })
//!     }
//! }
//!
//! impl HrTimerCallback for IntrusiveHrTimer {
//!     type Pointer<'a> = Pin<&'a mut Self>;
//!
//!     fn run(this: Pin<&mut Self>, _ctx: HrTimerCallbackContext<'_, Self>) -> HrTimerRestart {
//!         pr_info!("Timer called\n");
//!
//!         let flag = this.shared.flag.fetch_add(1, ordering::Full);
//!         this.shared.cond.complete_all();
//!
//!         if flag == 4 {
//!             HrTimerRestart::NoRestart
//!         } else {
//!             HrTimerRestart::Restart
//!         }
//!     }
//! }
//!
//! impl_has_hr_timer! {
//!     impl HasHrTimer<Self> for IntrusiveHrTimer {
//!         mode: RelativeMode<Monotonic>, field: self.timer
//!     }
//! }
//!
//! stack_try_pin_init!( let has_timer =? IntrusiveHrTimer::new() );
//! let shared = has_timer.shared.clone();
//!
//! has_timer.as_mut().start_scoped(Delta::from_micros(200), || {
//!     while shared.flag.load(ordering::Relaxed) != 5 {
//!         shared.cond.wait_for_completion();
//!     }
//! });
//!
//! pr_info!("Counted to 5\n");
//! # Ok::<(), kernel::error::Error>(())
//! ```
//!
//! [`Arc`]: kernel::sync::Arc

use super::{ClockSource, Delta, Instant};
use crate::{prelude::*, types::Opaque};
use core::{marker::PhantomData, ptr::NonNull};
use pin_init::PinInit;

/// A type-alias to refer to the [`Instant<C>`] for a given `T` from [`HrTimer<T>`].
///
/// Where `C` is the [`ClockSource`] of the [`HrTimer`].
pub type HrTimerInstant<T> = Instant<<<T as HasHrTimer<T>>::TimerMode as HrTimerMode>::Clock>;

/// A timer backed by a C `struct hrtimer`.
///
/// # Invariants
///
/// * `self.timer` is initialized by `bindings::hrtimer_setup`.
#[pin_data]
#[repr(C)]
pub struct HrTimer<T> {
    #[pin]
    timer: Opaque<bindings::hrtimer>,
    _t: PhantomData<T>,
}

// SAFETY: Ownership of an `HrTimer` can be moved to other threads and
// used/dropped from there.
unsafe impl<T> Send for HrTimer<T> {}

// SAFETY: Timer operations are locked on the C side, so it is safe to operate
// on a timer from multiple threads.
unsafe impl<T> Sync for HrTimer<T> {}

impl<T> HrTimer<T> {
    /// Return an initializer for a new timer instance.
    pub fn new() -> impl PinInit<Self>
    where
        T: HrTimerCallback,
        T: HasHrTimer<T>,
    {
        pin_init!(Self {
            // INVARIANT: We initialize `timer` with `hrtimer_setup` below.
            timer <- Opaque::ffi_init(move |place: *mut bindings::hrtimer| {
                // SAFETY: By design of `pin_init!`, `place` is a pointer to a
                // live allocation. hrtimer_setup will initialize `place` and
                // does not require `place` to be initialized prior to the call.
                unsafe {
                    bindings::hrtimer_setup(
                        place,
                        Some(T::Pointer::run),
                        <<T as HasHrTimer<T>>::TimerMode as HrTimerMode>::Clock::ID,
                        <T as HasHrTimer<T>>::TimerMode::C_MODE,
                    );
                }
            }),
            _t: PhantomData,
        })
    }

    /// Get a pointer to the contained `bindings::hrtimer`.
    ///
    /// This function is useful to get access to the value without creating
    /// intermediate references.
    ///
    /// # Safety
    ///
    /// `this` must point to a live allocation of at least the size of `Self`.
    unsafe fn raw_get(this: *const Self) -> *mut bindings::hrtimer {
        // SAFETY: The field projection to `timer` does not go out of bounds,
        // because the caller of this function promises that `this` points to an
        // allocation of at least the size of `Self`.
        unsafe { Opaque::cast_into(core::ptr::addr_of!((*this).timer)) }
    }

    /// Cancel an initialized and potentially running timer.
    ///
    /// If the timer handler is running, this function will block until the
    /// handler returns.
    ///
    /// Note that the timer might be started by a concurrent start operation. If
    /// so, the timer might not be in the **stopped** state when this function
    /// returns.
    ///
    /// Users of the `HrTimer` API would not usually call this method directly.
    /// Instead they would use the safe [`HrTimerHandle::cancel`] on the handle
    /// returned when the timer was started.
    ///
    /// This function is useful to get access to the value without creating
    /// intermediate references.
    ///
    /// # Safety
    ///
    /// `this` must point to a valid `Self`.
    pub(crate) unsafe fn raw_cancel(this: *const Self) -> bool {
        // SAFETY: `this` points to an allocation of at least `HrTimer` size.
        let c_timer_ptr = unsafe { HrTimer::raw_get(this) };

        // If the handler is running, this will wait for the handler to return
        // before returning.
        // SAFETY: `c_timer_ptr` is initialized and valid. Synchronization is
        // handled on the C side.
        unsafe { bindings::hrtimer_cancel(c_timer_ptr) != 0 }
    }

    /// Forward the timer expiry for a given timer pointer.
    ///
    /// # Safety
    ///
    /// - `self_ptr` must point to a valid `Self`.
    /// - The caller must either have exclusive access to the data pointed at by `self_ptr`, or be
    ///   within the context of the timer callback.
    #[inline]
    unsafe fn raw_forward(self_ptr: *mut Self, now: HrTimerInstant<T>, interval: Delta) -> u64
    where
        T: HasHrTimer<T>,
    {
        // SAFETY:
        // * The C API requirements for this function are fulfilled by our safety contract.
        // * `self_ptr` is guaranteed to point to a valid `Self` via our safety contract
        unsafe {
            bindings::hrtimer_forward(Self::raw_get(self_ptr), now.as_nanos(), interval.as_nanos())
        }
    }

    /// Conditionally forward the timer.
    ///
    /// If the timer expires after `now`, this function does nothing and returns 0. If the timer
    /// expired at or before `now`, this function forwards the timer by `interval` until the timer
    /// expires after `now` and then returns the number of times the timer was forwarded by
    /// `interval`.
    ///
    /// This function is mainly useful for timer types which can provide exclusive access to the
    /// timer when the timer is not running. For forwarding the timer from within the timer callback
    /// context, see [`HrTimerCallbackContext::forward()`].
    ///
    /// Returns the number of overruns that occurred as a result of the timer expiry change.
    pub fn forward(self: Pin<&mut Self>, now: HrTimerInstant<T>, interval: Delta) -> u64
    where
        T: HasHrTimer<T>,
    {
        // SAFETY: `raw_forward` does not move `Self`
        let this = unsafe { self.get_unchecked_mut() };

        // SAFETY: By existence of `Pin<&mut Self>`, the pointer passed to `raw_forward` points to a
        // valid `Self` that we have exclusive access to.
        unsafe { Self::raw_forward(this, now, interval) }
    }

    /// Conditionally forward the timer.
    ///
    /// This is a variant of [`forward()`](Self::forward) that uses an interval after the current
    /// time of the base clock for the [`HrTimer`].
    pub fn forward_now(self: Pin<&mut Self>, interval: Delta) -> u64
    where
        T: HasHrTimer<T>,
    {
        self.forward(HrTimerInstant::<T>::now(), interval)
    }

    /// Return the time expiry for this [`HrTimer`].
    ///
    /// This value should only be used as a snapshot, as the actual expiry time could change after
    /// this function is called.
    pub fn expires(&self) -> HrTimerInstant<T>
    where
        T: HasHrTimer<T>,
    {
        // SAFETY: `self` is an immutable reference and thus always points to a valid `HrTimer`.
        let c_timer_ptr = unsafe { HrTimer::raw_get(self) };

        // SAFETY:
        // - Timers cannot have negative ktime_t values as their expiration time.
        // - There's no actual locking here, a racy read is fine and expected
        unsafe {
            Instant::from_ktime(
                // This `read_volatile` is intended to correspond to a READ_ONCE call.
                // FIXME(read_once): Replace with `read_once` when available on the Rust side.
                core::ptr::read_volatile(&raw const ((*c_timer_ptr).node.expires)),
            )
        }
    }
}

/// Implemented by pointer types that point to structs that contain a [`HrTimer`].
///
/// `Self` must be [`Sync`] because it is passed to timer callbacks in another
/// thread of execution (hard or soft interrupt context).
///
/// Starting a timer returns a [`HrTimerHandle`] that can be used to manipulate
/// the timer. Note that it is OK to call the start function repeatedly, and
/// that more than one [`HrTimerHandle`] associated with a [`HrTimerPointer`] may
/// exist. A timer can be manipulated through any of the handles, and a handle
/// may represent a cancelled timer.
pub trait HrTimerPointer: Sync + Sized {
    /// The operational mode associated with this timer.
    ///
    /// This defines how the expiration value is interpreted.
    type TimerMode: HrTimerMode;

    /// A handle representing a started or restarted timer.
    ///
    /// If the timer is running or if the timer callback is executing when the
    /// handle is dropped, the drop method of [`HrTimerHandle`] should not return
    /// until the timer is stopped and the callback has completed.
    ///
    /// Note: When implementing this trait, consider that it is not unsafe to
    /// leak the handle.
    type TimerHandle: HrTimerHandle;

    /// Start the timer with expiry after `expires` time units. If the timer was
    /// already running, it is restarted with the new expiry time.
    fn start(self, expires: <Self::TimerMode as HrTimerMode>::Expires) -> Self::TimerHandle;
}

/// Unsafe version of [`HrTimerPointer`] for situations where leaking the
/// [`HrTimerHandle`] returned by `start` would be unsound. This is the case for
/// stack allocated timers.
///
/// Typical implementers are pinned references such as [`Pin<&T>`].
///
/// # Safety
///
/// Implementers of this trait must ensure that instances of types implementing
/// [`UnsafeHrTimerPointer`] outlives any associated [`HrTimerPointer::TimerHandle`]
/// instances.
pub unsafe trait UnsafeHrTimerPointer: Sync + Sized {
    /// The operational mode associated with this timer.
    ///
    /// This defines how the expiration value is interpreted.
    type TimerMode: HrTimerMode;

    /// A handle representing a running timer.
    ///
    /// # Safety
    ///
    /// If the timer is running, or if the timer callback is executing when the
    /// handle is dropped, the drop method of [`Self::TimerHandle`] must not return
    /// until the timer is stopped and the callback has completed.
    type TimerHandle: HrTim