strat9_kernel/process/scheduler/

timer_ops.rs

use super::*;
use core::sync::atomic::{AtomicBool, AtomicU64};

// One-shot bootstrap nudge: ensure each CPU requests at least one preemption
// after entering Ring 3. This breaks "first task runs forever" scenarios when
// class accounting has not yet accumulated enough runtime to trigger resched.
static FIRST_TICK_FORCE_RESCHED: [AtomicBool; crate::arch::percpu::MAX_CPUS] =
    [const { AtomicBool::new(false) }; crate::arch::percpu::MAX_CPUS];

// Per-CPU local tick counter (incremented every timer tick, independent of
// the BSP-only global TICK_COUNT). Used for periodic force-resched below.
static CPU_LOCAL_TICKS: [AtomicU64; crate::arch::percpu::MAX_CPUS] =
    [const { AtomicU64::new(0) }; crate::arch::percpu::MAX_CPUS];

// Force a reschedule at least every N ticks per CPU, regardless of GLOBAL_SCHED_STATE
// lock availability. This guarantees kernel tasks (shell, idle) get CPU time
// even if timer_tick consistently loses the scheduler lock race with the other CPU.
const PERIODIC_RESCHED_TICKS: u64 = 5;

/// Timer interrupt handler - called from interrupt context.
///
/// Increments the global tick counter unconditionally on BSP so wall-clock
/// time never drifts even when the scheduler lock is contended. Secondary
/// bookkeeping (interval timers, wake deadlines, per-task accounting) is
/// deferred when the lock is unavailable.
///
/// Lock discipline: `tick_all_timers` and `check_wake_deadlines` each acquire
/// the scheduler lock themselves via `try_lock`. The per-task block below uses
/// its own `try_lock`. These are separate acquisitions by design - the inner
/// functions must not be called while the outer lock is held (that would deadlock).
pub fn timer_tick() {
    let _perf = super::perf_counters::PerfScope::new(
        &super::perf_counters::IRQ_TIMER_TSC,
        &super::perf_counters::IRQ_TIMER_COUNT,
    );

    // Feed TSC low bits into the entropy pool (every tick).
    crate::entropy::add_entropy(2, crate::arch::rdtsc());
    let cpu_idx = crate::arch::percpu::current_cpu_index();

    if cpu_is_valid(cpu_idx) {
        CPU_TOTAL_TICKS[cpu_idx].fetch_add(1, Ordering::Relaxed);
    }

    // BSP wall-clock: ALWAYS advance, regardless of any lock state.
    if cpu_idx == 0 {
        TICK_COUNT.fetch_add(1, Ordering::Relaxed);
    }

    // Per-CPU local tick counter (all CPUs, not just BSP).
    let local_tick = if cpu_is_valid(cpu_idx) {
        CPU_LOCAL_TICKS[cpu_idx].fetch_add(1, Ordering::Relaxed) + 1
    } else {
        0
    };

    // Lock-free bootstrap nudge: first local timer tick requests one resched
    // without touching GLOBAL_SCHED_STATE. This avoids pathological boot windows where
    // another CPU holds GLOBAL_SCHED_STATE and this CPU would otherwise defer the first
    // `need_resched` update indefinitely.
    if cpu_is_valid(cpu_idx) && !FIRST_TICK_FORCE_RESCHED[cpu_idx].swap(true, Ordering::AcqRel) {
        request_force_resched_hint(cpu_idx);
    }

    // Periodic force-resched: guarantee every CPU reschedules at least every
    // PERIODIC_RESCHED_TICKS ticks. This prevents starvation of kernel tasks
    // when timer_tick fails to acquire the scheduler lock repeatedly, or when
    // FairClassRq::update_current returns false (e.g., single-task queue).
    if cpu_is_valid(cpu_idx) && local_tick > 0 && local_tick % PERIODIC_RESCHED_TICKS == 0 {
        request_force_resched_hint(cpu_idx);
    }

    // Deferred tick processing: raise work items for processing at safe points
    // (finish_switch, finish_interrupt_switch, idle loop). This moves heavy
    // lock-acquiring work out of hardirq context, reducing IRQ latency.
    //
    // What remains in hardirq (lock-free only):
    //   - Counter increments (lock-free atomics)
    //   - FORCE_RESCHED_HINT (lock-free)
    //   - Force-resched hint every 5 ticks
    if cpu_idx == 0 {
        let tick = TICK_COUNT.load(Ordering::Relaxed);
        if tick % 200 == 0 {
            crate::hardware::thermal::poll();
        }
    }

    // Raise deferred work for all tick processing.
    // Timer processing (interval timers, wake deadlines) was previously done
    // inline on the BSP. Now ALL CPUs raise their own deferred work, and the
    // processing happens at safe points on each CPU independently.
    super::deferred_work::raise_tick_deferred_work();
}

/// Check wake deadlines for all tasks and wake up those whose sleep has expired.
///
/// Called from timer_tick() with interrupts disabled.
/// Uses try_lock() to avoid deadlock if called while scheduler lock is held.
///
/// # Lock discipline
///
/// The `BLOCKED_TASKS` lock is held **only** during the scan + re-enqueue phase.
/// The lock is explicitly dropped before sending IPIs (which may acquire
/// per-CPU data) and before any `Arc<Task>` drop (which reaches
/// `KernelStack::drop => free_frames => buddy_alloc.lock()`).
///
/// To guarantee this, every `Arc<Task>` removed from `blocked_tasks` is
/// moved into the `deferred_drops` array. Those Arcs are dropped after the
/// guard goes out of scope, ensuring `free_frames` is never called while the
/// scheduler lock is held.
pub(super) fn check_wake_deadlines(current_time_ns: u64) {
    let mut ipi_targets = [false; crate::arch::percpu::MAX_CPUS];
    let my_cpu = current_cpu_index();

    const BATCH: usize = 128;
    let mut deferred_drops: [Option<Arc<Task>>; BATCH] = [const { None }; BATCH];
    let mut drop_count = 0usize;

    {
        // Lock order: BLOCKED (rank 3) -> LOCAL (rank 4).
        lockdep_acquire(LockRank::Blocked, None);
        let mut blocked = match super::BLOCKED_TASKS.try_lock_no_irqsave() {
            Some(guard) => guard,
            None => {
                lockdep_release(LockRank::Blocked);
                return;
            }
        };

        let mut to_wake = [TaskId::from_u64(0); BATCH];
        let mut count = 0usize;
        for (id, task) in blocked.iter() {
            let deadline = task.wake_deadline_ns.load(Ordering::Relaxed);
            if deadline != 0 && current_time_ns >= deadline {
                if count < BATCH {
                    to_wake[count] = *id;
                    count += 1;
                } else {
                    break;
                }
            }
        }

        for id in to_wake.iter().copied().take(count) {
            if let Some(blocked_task) = blocked.remove(&id) {
                blocked_task.wake_deadline_ns.store(0, Ordering::Relaxed);
                blocked_task.set_state(TaskState::Ready);

                // --- CPU placement: prefer last_cpu, then home_cpu ---
                let last = blocked_task.last_cpu.load(Ordering::Relaxed);
                let home = blocked_task.home_cpu.load(Ordering::Relaxed);
                let n = active_cpu_count();
                let cpu = if last < n {
                    // Use try_lock to avoid blocking in IRQ context.
                    let last_ok = LOCAL_SCHEDULERS[last]
                        .try_lock_no_irqsave()
                        .and_then(|guard| {
                            let ok = guard
                                .as_ref()
                                .map(|c| c.class_rqs.runnable_len() <= 2)
                                .unwrap_or(false);
                            drop(guard);
                            Some(ok)
                        })
                        .unwrap_or(false);
                    if last_ok {
                        last
                    } else if home < n {
                        home
                    } else {
                        0
                    }
                } else if home < n {
                    home
                } else {
                    0
                };
                let class = {
                    use crate::process::sched::SchedClassId;
                    match blocked_task.sched_policy() {
                        crate::process::sched::SchedPolicy::RealTimeRR { .. }
                        | crate::process::sched::SchedPolicy::RealTimeFifo { .. } => {
                            SchedClassId::RealTime
                        }
                        crate::process::sched::SchedPolicy::Fair(_) => SchedClassId::Fair,
                        crate::process::sched::SchedPolicy::Idle => SchedClassId::Idle,
                    }
                };
                // Use try_lock to avoid blocking in IRQ context. If the target
                // CPU's LOCAL lock is contended, re-insert the task into
                // BLOCKED_TASKS so it will be retried on the next tick.
                match LOCAL_SCHEDULERS[cpu].try_lock_no_irqsave() {
                    Some(mut guard) => {
                        lockdep_acquire(LockRank::Local, Some(cpu));
                        if let Some(ref mut local_cpu) = *guard {
                            local_cpu.class_rqs.enqueue(class, blocked_task);
                            local_cpu.need_resched = true;
                            if cpu != my_cpu && cpu_is_valid(cpu) {
                                ipi_targets[cpu] = true;
                            }
                        } else {
                            // CPU slot not initialized — drop the task.
                            if drop_count < BATCH {
                                deferred_drops[drop_count] = Some(blocked_task);
                                drop_count += 1;
                            }
                        }
                        lockdep_release(LockRank::Local);
                        drop(guard);
                    }
                    None => {
                        // LOCAL lock contended — re-insert into BLOCKED_TASKS
                        // so the next tick retries this wake.
                        blocked_task.set_state(TaskState::Blocked);
                        blocked.insert(id, blocked_task);
                    }
                }
            }
        }
        lockdep_release(LockRank::Blocked);
        drop(blocked);
    }
    // Drop orphaned task Arcs outside the scheduler lock so that
    // KernelStack::drop => free_frames => buddy_alloc.lock() does not race
    // with any other GLOBAL_SCHED_STATE lock acquisition on this or another CPU.
    for slot in deferred_drops[..drop_count].iter_mut() {
        drop(slot.take());
    }

    for (cpu, send) in ipi_targets.iter().copied().enumerate() {
        if send {
            send_resched_ipi_to_cpu(cpu);
        }
    }
}

/// Get the current tick count
pub fn ticks() -> u64 {
    TICK_COUNT.load(Ordering::Relaxed)
}

/// Get a list of all tasks in the system (for timer checking).
/// Returns None if scheduler is not initialized or currently locked.
pub fn get_all_tasks() -> Option<alloc::vec::Vec<Arc<Task>>> {
    use alloc::vec::Vec;
    let scheduler = match GLOBAL_SCHED_STATE.try_lock() {
        Some(guard) => guard,
        None => {
            note_try_lock_fail();
            return None;
        }
    };
    if let Some(ref sched) = *scheduler {
        let mut tasks = Vec::with_capacity(sched.all_tasks.len());
        for (_, task) in sched.all_tasks.iter() {
            tasks.push(task.clone());
        }
        Some(tasks)
    } else {
        None
    }
}