// Copyright (c) 2026 Rigless Labs.
// SPDX-License-Identifier: MIT OR Apache-2.0
//! The virtual clock every access and every event is stamped with, and the events waiting on it.
//!
//! Every access reaches the bus at an instant of the virtual clock, `VirtualNanos`, the same clock the emulator's `icount` runs under, and a model sees that instant and nothing else about time through the `DeviceContext` every method receives: `now`, `schedule` for an event at an absolute instant, and `raise` and `lower` for the instance's interrupts. An event is QEMU's virtual-clock timer in this vocabulary: nothing ticks and nothing polls, the emulator runs to the earliest event as its deadline, and `Device::on_event` is called at that exact instant with the id `schedule` returned, whether or not the firmware touched the peripheral meanwhile. There is no cancel. A model keeps the id of the event it last scheduled and ignores any other, and an instance asking again for an instant it already has an event at gets that event's id back rather than a second one, so an instant fires once per instance however often it was asked for. Two instances' events at one instant fire in the order they were scheduled, and an instant already passed is the instant of the access or event that asked for it, so every run orders them the same way.
use std::collections::BTreeMap;
/// An instant on the virtual clock, or a distance between two, in nanoseconds.
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct VirtualNanos(pub u64);
/// Names an event to the model that scheduled it, unique within its queue and never reused until a
/// reset empties the queue.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct EventId(u64);
/// The events waiting on the virtual clock, each an absolute instant and the instance that scheduled it.
///
/// This is QEMU's virtual-clock timer list in the runtime's vocabulary: nothing ticks and nothing polls, an event
/// fires because the emulator reached its instant, and two instances' events at one instant fire in the order they
/// were scheduled, on every run. There is no cancel. A model keeps the id of the event it last scheduled and
/// ignores any other, and an instance holds at most one event per instant.
#[derive(Debug, Default)]
pub(crate) struct EventQueue {
due: BTreeMap<(VirtualNanos, u64), usize>,
next_sequence: u64,
}
impl EventQueue {
/// Adds an event at `at` for the instance at `owner`, or returns the one it already has there.
pub(crate) fn schedule(&mut self, at: VirtualNanos, owner: usize) -> EventId {
// One event per instance per instant. A model whose next instant flips between a near one and
// a far one asks for the far one again on every flip, and with no cancel each ask would pile
// another event on that instant: a free-running counter's overflow gathered one per alarm for
// an hour, and the run that reached it fired them all at once.
let mut same_instant = self.due.range((at, 0)..=(at, u64::MAX));
if let Some((&(_, sequence), _)) = same_instant.find(|&(_, &held)| held == owner) {
return EventId(sequence);
}
let sequence = self.next_sequence;
self.next_sequence += 1;
self.due.insert((at, sequence), owner);
EventId(sequence)
}
/// The instant of the earliest event, if any waits.
pub(crate) fn next_at(&self) -> Option<VirtualNanos> {
self.due.keys().next().map(|(at, _sequence)| *at)
}
/// Removes and returns the earliest event due by `now`.
pub(crate) fn pop_due(&mut self, now: VirtualNanos) -> Option<(EventId, usize, VirtualNanos)> {
let (&(at, _sequence), _owner) = self.due.first_key_value()?;
if at > now {
return None;
}
self.due
.pop_first()
.map(|((at, sequence), owner)| (EventId(sequence), owner, at))
}
}
#[cfg(test)]
mod tests {
use super::*;
const EARLY: VirtualNanos = VirtualNanos(100);
const LATE: VirtualNanos = VirtualNanos(200);
const FIRST_OWNER: usize = 1;
const SECOND_OWNER: usize = 2;
#[test]
fn an_instance_asking_again_for_an_instant_it_holds_gets_the_same_event() {
let mut queue = EventQueue::default();
let first = queue.schedule(LATE, FIRST_OWNER);
assert_eq!(
queue.schedule(LATE, FIRST_OWNER),
first,
"the same instant, the same event"
);
let other = queue.schedule(LATE, SECOND_OWNER);
assert_ne!(
other, first,
"another instance's event at that instant is its own"
);
assert_eq!(queue.pop_due(LATE), Some((first, FIRST_OWNER, LATE)));
assert_eq!(queue.pop_due(LATE), Some((other, SECOND_OWNER, LATE)));
assert_eq!(queue.pop_due(LATE), None, "asked for twice, fired once");
assert_ne!(
queue.schedule(LATE, FIRST_OWNER),
first,
"once fired, the instant can be asked for again"
);
}
#[test]
fn events_fire_by_instant_then_by_the_order_scheduled() {
let mut queue = EventQueue::default();
let late = queue.schedule(LATE, FIRST_OWNER);
let early_first = queue.schedule(EARLY, FIRST_OWNER);
let early_second = queue.schedule(EARLY, SECOND_OWNER);
assert_eq!(queue.next_at(), Some(EARLY));
assert_eq!(queue.pop_due(LATE), Some((early_first, FIRST_OWNER, EARLY)));
assert_eq!(
queue.pop_due(LATE),
Some((early_second, SECOND_OWNER, EARLY))
);
// Popped while advancing to LATE, the late event still reports the instant it was scheduled at.
assert_eq!(queue.pop_due(LATE), Some((late, FIRST_OWNER, LATE)));
assert_eq!(queue.pop_due(LATE), None);
assert_eq!(queue.next_at(), None);
}
#[test]
fn nothing_pops_before_its_instant() {
let mut queue = EventQueue::default();
let event = queue.schedule(LATE, FIRST_OWNER);
assert_eq!(queue.pop_due(EARLY), None);
assert_eq!(queue.pop_due(VirtualNanos(LATE.0 - 1)), None);
assert_eq!(queue.pop_due(LATE), Some((event, FIRST_OWNER, LATE)));
}
#[test]
fn ids_are_never_reused() {
let mut queue = EventQueue::default();
let first = queue.schedule(EARLY, FIRST_OWNER);
queue.pop_due(EARLY);
let second = queue.schedule(EARLY, FIRST_OWNER);
assert_ne!(first, second);
}
}