rust-kernel

//! Timers that send signals (stage 17): alarm, setitimer/getitimer and
//! the POSIX timers (timer_create, timer_settime, ...).
//!
//! A timer is a deadline, maybe with an interval to repeat at, and what to
//! do when it's reached: send a signal (SIGALRM for alarm and setitimer;
//! any signal, maybe to one thread, for timer_create).
//!
//! All timers live in one table. One kernel thread, "timerd", sleeps until
//! the nearest deadline, sends the signals that are due, and goes back to
//! sleep. Why a thread and not the timer interrupt? Sending a signal takes
//! locks and may wake threads; doing that from normal thread context keeps
//! the interrupt handler tiny and follows the locking rules in thread.rs.
//! timerd is started at boot (stage 18; it used to start the first time
//! anyone armed a timer).
//!
//! Resolution: timerd sleeps in PIT ticks (~55 ms), so a timer fires up
//! to ~110 ms late, never early. A periodic timer whose signals come late
//! counts the periods it missed as "overruns" (timer_getoverrun), like
//! Linux does when a signal is still pending.
//!
//! Lifetime, as on Linux: fork doesn't copy timers; execve deletes the
//! POSIX timers but keeps the alarm / ITIMER_REAL; exit deletes them all.
//!
//! Stage 20: timerfd. A timer that is a *file*: instead of a signal, each
//! expiration adds 1 to a counter that `read` returns (and resets), and
//! poll/select/epoll see the fd as readable while the counter isn't 0. It
//! lives in the same table (owner `TIMERFD_PID`, kind `NOTIFY_TIMERFD`), is
//! fired by the same timerd, and goes away when its last fd is closed --
//! not at exec or exit, since an fd can outlive (or be passed to) a process.
//! Same ~55 ms resolution as the rest.

use crate::errno::Errno;
use crate::process;
use crate::signal::{self, SigInfo};
use crate::thread::WaitQueue;
use crate::time;
use alloc::vec::Vec;
use core::sync::atomic::{AtomicBool, Ordering};
use spin::Mutex;
use x86_64::instructions::interrupts::without_interrupts;

/// si_code for a POSIX timer's signal.
pub const SI_TIMER: i32 = -2;

// The clocks timer_create understands.
pub const CLOCK_REALTIME: u64 = 0;
pub const CLOCK_MONOTONIC: u64 = 1;
pub const CLOCK_BOOTTIME: u64 = 7;

// sigev_notify: what to do when it fires.
pub const SIGEV_SIGNAL: i32 = 0; // send sigev_signo to the process
pub const SIGEV_NONE: i32 = 1; // nothing (the program polls timer_gettime)
pub const SIGEV_THREAD_ID: i32 = 4; // send sigev_signo to thread sigev_tid
/// Ours, not Linux's: "count it in a timerfd" (user space can't ask for it).
const NOTIFY_TIMERFD: i32 = -1;
/// The owner of every timerfd's table entry (no real process has this pid).
const TIMERFD_PID: u64 = u64::MAX;

/// At most this many POSIX timers per process: EAGAIN after that.
const MAX_TIMERS: usize = 32;
/// The id we use for a process's ITIMER_REAL (POSIX ids are 0..MAX_TIMERS).
const ITIMER_ID: i32 = -1;

#[derive(Clone, Copy)]
struct Timer {
    pid: u64,
    /// timer_create's id, or ITIMER_ID.
    id: i32,
    clock: u64,
    /// Next expiry, in `time::now_us` microseconds (None = disarmed).
    next: Option<u64>,
    /// Repeat every this many microseconds (0 = once).
    interval: u64,
    signo: u32,
    notify: i32,
    /// SIGEV_THREAD_ID's thread.
    tid: u64,
    sigval: u64,
    /// Expirations counted since the signal was sent, while it is still
    /// pending (stage 18 fix: this *adds up*; it used to be overwritten).
    /// For a timerfd: expirations since the last read.
    overrun: u64,
    /// What timer_getoverrun reports: `overrun` as it was when the last
    /// signal was delivered (0 before the first delivery), like Linux.
    overrun_last: u64,
}

static TIMERS: Mutex<Vec<Timer>> = Mutex::new(Vec::new());
/// timerd sleeps here; poked when the table changes.
static CHANGED_QUEUE: WaitQueue = WaitQueue::new();
static CHANGED: AtomicBool = AtomicBool::new(false);
static STARTED: AtomicBool = AtomicBool::new(false);

fn with_table<R>(f: impl FnOnce(&mut Vec<Timer>) -> R) -> R {
    without_interrupts(|| f(&mut TIMERS.lock()))
}

/// Start timerd. The kernel does this at boot (stage 18: before, the
/// first timer started it, so its stack showed up in the frame count of
/// whatever program armed a timer first). Calling it again does nothing.
pub fn start() {
    if !STARTED.swap(true, Ordering::AcqRel) {
        crate::thread::spawn("timerd", timerd);
    }
}

/// Tell timerd to look again (starting it, if nobody did yet: the test
/// kernels in tests/ don't run the boot code).
fn poke() {
    start();
    CHANGED.store(true, Ordering::Release);
    CHANGED_QUEUE.wake_all();
}

/// How far CLOCK_REALTIME is ahead of the monotonic clock (µs), to turn
/// absolute wall-clock deadlines into ours.
fn realtime_offset() -> u64 {
    time::realtime_us().saturating_sub(time::now_us())
}

/// The kernel thread that fires timers (see the top).
fn timerd() {
    loop {
        let now = time::now_us();
        let mut due = Vec::new();
        let next = with_table(|t| {
            for timer in t.iter_mut() {
                let Some(at) = timer.next else { continue };
                if at > now {
                    continue;
                }
                // Periods that went by since `at` without a wake-up of
                // ours (timerd sleeps in ~55 ms ticks): expirations too.
                let missed = if timer.interval > 0 { (now - at) / timer.interval } else { 0 };
                timer.next = (timer.interval > 0).then(|| at + (missed + 1) * timer.interval);
                due.push((*timer, missed));
            }
            t.iter().filter_map(|t| t.next).min()
        });
        for (timer, missed) in due {
            // A POSIX timer whose last signal hasn't been delivered yet
            // (blocked, say) doesn't send another: like Linux, it counts
            // the expirations as overruns, which the delivery reports.
            // (Checked outside the table lock: signal locks come first.)
            if timer.notify == NOTIFY_TIMERFD {
                with_table(|t| {
                    if let Some(x) = t.iter_mut().find(|x| x.pid == timer.pid && x.id == timer.id) {
                        x.overrun = x.overrun.saturating_add(1 + missed);
                    }
                });
                TIMERFD_WAIT.wake_all();
                crate::poll::notify();
                continue;
            }
            let posix = timer.id != ITIMER_ID && timer.notify != SIGEV_NONE;
            let still_pending = posix && process::get(timer.pid).is_some_and(|p| signal::timer_pending(&p, timer.signo, timer.id));
            let send = with_table(|t| {
                let Some(x) = t.iter_mut().find(|x| x.pid == timer.pid && x.id == timer.id) else { return false };
                if still_pending {
                    x.overrun = x.overrun.saturating_add(1 + missed);
                } else {
                    x.overrun = missed;
                }
                !still_pending
            });
            if send {
                fire(&timer);
            }
        }
        let changed = || CHANGED.swap(false, Ordering::AcqRel).then_some(());
        match next {
            Some(at) => {
                let deadline = time::deadline_after_us(at.saturating_sub(time::now_us()));
                let _ = CHANGED_QUEUE.wait_until_deadline(deadline, changed);
            }
            None => CHANGED_QUEUE.wait_until(changed),
        }
    }
}

/// Send a due timer's signal.
fn fire(timer: &Timer) {
    if timer.notify == SIGEV_NONE {
        return;
    }
    let Some(p) = process::get(timer.pid) else { return };
    let info = if timer.id == ITIMER_ID {
        SigInfo::from_pid(timer.signo, 0) // SI_KERNEL, like Linux's itimers
    } else {
        let mut info = SigInfo::new(timer.signo, SI_TIMER);
        info.fields[0] = timer.id as u32 as u64; // si_tid; si_overrun is filled in at delivery (`delivered`)
        info.fields[1] = timer.sigval; // si_value
        info
    };
    if timer.notify == SIGEV_THREAD_ID {
        if let Some(t) = p.tasks().into_iter().find(|t| t.tid() == timer.tid) {
            signal::send_thread(&t, timer.signo, info);
        }
        return;
    }
    signal::send(&p, timer.signo, info);
}

/// (value, interval) of a timer in microseconds: time left, and the period.
fn read(timer: &Timer, now: u64) -> (u64, u64) {
    (timer.next.map_or(0, |at| at.saturating_sub(now).max(1)), timer.interval)
}

// --- setitimer / getitimer / alarm ---------------------------------------

/// getitimer(ITIMER_REAL): (time left, interval), in microseconds.
pub fn get_itimer(pid: u64) -> (u64, u64) {
    let now = time::now_us();
    with_table(|t| t.iter().find(|x| x.pid == pid && x.id == ITIMER_ID).map_or((0, 0), |x| read(x, now)))
}

/// setitimer(ITIMER_REAL, value, interval) (µs; value 0 disarms). Returns
/// the old (value, interval).
pub fn set_itimer(pid: u64, value: u64, interval: u64) -> (u64, u64) {
    let now = time::now_us();
    let old = with_table(|t| {
        let old = t.iter().position(|x| x.pid == pid && x.id == ITIMER_ID).map(|i| t.remove(i));
        if value > 0 {
            t.push(Timer {
                pid,
                id: ITIMER_ID,
                clock: CLOCK_MONOTONIC,
                next: Some(now + value),
                interval,
                signo: signal::SIGALRM,
                notify: SIGEV_SIGNAL,
                tid: 0,
                sigval: 0,
                overrun: 0,
                overrun_last: 0,
            });
        }
        old.map_or((0, 0), |x| read(&x, now))
    });
    if value > 0 {
        poke();
    }
    old
}

// --- POSIX timers --------------------------------------------------------

/// What timer_create's `struct sigevent` asked for.
pub struct SigEvent {
    pub notify: i32,
    pub signo: u32,
    pub tid: u64,
    /// None: no sigevent was given, so the value is the timer's id.
    pub sigval: Option<u64>,
}

/// timer_create: a new, disarmed timer. Returns its id.
pub fn create(pid: u64, clock: u64, ev: SigEvent) -> Result<i32, Errno> {
    with_table(|t| {
        let ids: Vec<i32> = t.iter().filter(|x| x.pid == pid && x.id != ITIMER_ID).map(|x| x.id).collect();
        if ids.len() >= MAX_TIMERS {
            return Err(Errno::EAGAIN);
        }
        let id = (0..).find(|i| !ids.contains(i)).unwrap();
        // No sigevent: SIGALRM with the timer id as the value (Linux's default).
        let sigval = ev.sigval.unwrap_or(id as u64);
        t.push(Timer { pid, id, clock, next: None, interval: 0, signo: ev.signo, notify: ev.notify, tid: ev.tid, sigval, overrun: 0, overrun_last: 0 });
        Ok(id)
    })
}

/// timer_settime: arm (value > 0) or disarm. `absolute`: value is a time on
/// the timer's clock, not a delay. Returns the old (value, interval).
pub fn settime(pid: u64, id: i32, absolute: bool, value: u64, interval: u64) -> Result<(u64, u64), Errno> {
    let now = time::now_us();
    let old = with_table(|t| {
        let timer = t.iter_mut().find(|x| x.pid == pid && x.id == id && id != ITIMER_ID).ok_or(Errno::EINVAL)?;
        let old = read(timer, now);
        timer.overrun = 0;
        timer.overrun_last = 0;
        timer.interval = interval;
        timer.next = match (value, absolute) {
            (0, _) => None,
            (v, false) => Some(now + v),
            (v, true) if timer.clock == CLOCK_REALTIME => Some(v.saturating_sub(realtime_offset()).max(1)),
            (v, true) => Some(v.max(1)), // MONOTONIC/BOOTTIME: our own clock
        };
        Ok(old)
    })?;
    if value > 0 {
        poke();
    }
    Ok(old)
}

/// timer_gettime: (time left, interval) in microseconds.
pub fn gettime(pid: u64, id: i32) -> Result<(u64, u64), Errno> {
    let now = time::now_us();
    with_table(|t| t.iter().find(|x| x.pid == pid && x.id == id && id != ITIMER_ID).map(|x| read(x, now)).ok_or(Errno::EINVAL))
}

/// timer_getoverrun: the overrun count of the last *delivered* signal.
pub fn getoverrun(pid: u64, id: i32) -> Result<u64, Errno> {
    with_table(|t| t.iter().find(|x| x.pid == pid && x.id == id && id != ITIMER_ID).map(|x| x.overrun_last.min(i32::MAX as u64)).ok_or(Errno::EINVAL))
}

/// A signal was just taken off a pending set to be delivered (or picked up
/// by sigwaitinfo). If it is a POSIX timer's, latch that timer's overrun
/// count: it goes into si_overrun and becomes what timer_getoverrun says,
/// and counting starts again from 0. Call without signal locks held.
pub fn delivered(pid: u64, info: &mut SigInfo) {
    if info.code != SI_TIMER {
        return;
    }
    let id = info.fields[0] as u32 as i32;
    let overrun = with_table(|t| {
        let x = t.iter_mut().find(|x| x.pid == pid && x.id == id && id != ITIMER_ID)?;
        x.overrun_last = x.overrun;
        x.overrun = 0;
        Some(x.overrun_last.min(i32::MAX as u64))
    });
    if let Some(n) = overrun {
        info.fields[0] = id as u32 as u64 | n << 32; // si_tid, si_overrun
    }
}

/// timer_delete.
pub fn delete(pid: u64, id: i32) -> Result<(), Errno> {
    with_table(|t| {
        let i = t.iter().position(|x| x.pid == pid && x.id == id && id != ITIMER_ID).ok_or(Errno::EINVAL)?;
        t.remove(i);
        Ok(())
    })
}

/// execve: POSIX timers go, the alarm stays.
pub fn exec(pid: u64) {
    with_table(|t| t.retain(|x| x.pid != pid || x.id == ITIMER_ID));
}

/// The process ended: all its timers go.
pub fn process_exited(pid: u64) {
    with_table(|t| t.retain(|x| x.pid != pid));
}

/// How many timers exist (tests: nothing left behind).
pub fn count() -> usize {
    with_table(|t| t.len())
}

// --- timerfd (stage 20) ---------------------------------------------------

use crate::fs::file::{File, Stat};
use core::sync::atomic::AtomicI32;

/// Readers of every timerfd sleep here (one queue for all: timerfds are
/// few, and a reader that wakes for another fd's timer just sleeps again).
static TIMERFD_WAIT: WaitQueue = WaitQueue::new();

/// An open timerfd. Its timer is the table entry (TIMERFD_PID, `id`).
pub struct TimerFd {
    id: i32,
    nonblocking: AtomicBool,
}

/// timerfd_create: a new, disarmed timer on `clock` (already checked).
pub fn timerfd_new(clock: u64, nonblocking: bool) -> TimerFd {
    static NEXT_ID: AtomicI32 = AtomicI32::new(0);
    let id = NEXT_ID.fetch_add(1, Ordering::Relaxed) & i32::MAX; // never ITIMER_ID
    let notify = NOTIFY_TIMERFD;
    with_table(|t| t.push(Timer { pid: TIMERFD_PID, id, clock, next: None, interval: 0, signo: 0, notify, tid: 0, sigval: 0, overrun: 0, overrun_last: 0 }));
    TimerFd { id, nonblocking: AtomicBool::new(nonblocking) }
}

impl TimerFd {
    /// timerfd_settime: like timer_settime (this also zeroes the count).
    pub fn settime(&self, absolute: bool, value: u64, interval: u64) -> (u64, u64) {
        let old = settime(TIMERFD_PID, self.id, absolute, value, interval).unwrap_or((0, 0));
        crate::poll::notify(); // the count went back to 0: not readable any more
        old
    }
    /// timerfd_gettime: (time left, interval) in microseconds.
    pub fn gettime(&self) -> (u64, u64) {
        gettime(TIMERFD_PID, self.id).unwrap_or((0, 0))
    }
    /// Expirations since the last read (without resetting them).
    fn count(&self) -> u64 {
        with_table(|t| t.iter().find(|x| x.pid == TIMERFD_PID && x.id == self.id).map_or(0, |x| x.overrun))
    }
}

impl Drop for TimerFd {
    /// The last fd is closed: the timer goes too.
    fn drop(&mut self) {
        let _ = delete(TIMERFD_PID, self.id);
    }
}

impl File for TimerFd {
    /// An 8-byte count of expirations since the last read, then back to 0.
    /// None yet: wait for one (EAGAIN if non-blocking).
    fn read(&self, buf: &mut [u8]) -> Result<usize, Errno> {
        if buf.len() < 8 {
            return Err(Errno::EINVAL);
        }
        let nonblocking = self.nonblocking();
        let count = TIMERFD_WAIT.wait_until_intr(|| {
            let n = with_table(|t| {
                let x = t.iter_mut().find(|x| x.pid == TIMERFD_PID && x.id == self.id)?;
                Some(core::mem::take(&mut x.overrun))
            })
            .unwrap_or(0);
            match n {
                0 if nonblocking => Some(Err(Errno::EAGAIN)),
                0 => None,
                n => Some(Ok(n)),
            }
        })??;
        buf[..8].copy_from_slice(&count.to_le_bytes());
        crate::poll::notify();
        Ok(8)
    }
    fn write(&self, _buf: &[u8]) -> Result<usize, Errno> {
        Err(Errno::EINVAL)
    }
    fn stat(&self) -> Result<Stat, Errno> {
        Ok(Stat { kind: crate::fs::file::KIND_DEVICE, size: 0, mode: 0o600 })
    }
    fn poll(&self) -> u16 {
        if self.count() > 0 { crate::poll::POLLIN } else { 0 }
    }
    fn set_nonblocking(&self, on: bool) {
        self.nonblocking.store(on, Ordering::Relaxed);
    }
    fn nonblocking(&self) -> bool {
        self.nonblocking.load(Ordering::Relaxed)
    }
    fn status_flags(&self) -> u64 {
        2 // O_RDWR, like Linux's anon inode
    }
    fn as_timerfd(&self) -> Option<&TimerFd> {
        Some(self)
    }
}