Skip to main content

gwr_engine/time/
clock.rs

1// Copyright (c) 2023 Graphcore Ltd. All rights reserved.
2
3//! This module represents the time during a simulation.
4//!
5//! Time is made up of a tick count and a phase.
6
7use core::cmp::Ordering;
8use std::cell::{Cell, RefCell};
9use std::future::Future;
10use std::pin::Pin;
11use std::rc::Rc;
12use std::task::{Context, Poll, Waker};
13
14use futures::future::FusedFuture;
15
16use crate::traits::{Resolve, Resolver};
17use crate::types::{SimError, SimResult};
18
19pub mod phase {
20    pub const BEGIN: u32 = 0;
21    pub const END: u32 = u32::MAX;
22}
23
24/// ClockTick structure for representing a number of Clock ticks and a phase.
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub struct ClockTick {
27    /// Clock ticks.
28    tick: u64,
29
30    /// Clock phase.
31    phase: u32,
32}
33
34impl ClockTick {
35    #[must_use]
36    pub fn new() -> Self {
37        Self {
38            tick: 0,
39            phase: phase::BEGIN,
40        }
41    }
42
43    /// Get the current clock tick.
44    #[must_use]
45    pub fn tick(&self) -> u64 {
46        self.tick
47    }
48
49    /// Get the current clock phase.
50    #[must_use]
51    pub fn phase(&self) -> u32 {
52        self.phase
53    }
54
55    /// Change the default constructor value of `tick`.
56    pub fn set_tick(&mut self, tick: u64) -> ClockTick {
57        self.tick = tick;
58        *self
59    }
60
61    /// Change the default constructor value of `phase`.
62    pub fn set_phase(&mut self, phase: u32) -> ClockTick {
63        self.phase = phase;
64        *self
65    }
66}
67
68impl Default for ClockTick {
69    fn default() -> Self {
70        Self::new()
71    }
72}
73
74/// Define the comparison operation for SimTime.
75impl Ord for ClockTick {
76    fn cmp(&self, other: &Self) -> Ordering {
77        match self.tick.cmp(&other.tick) {
78            Ordering::Greater => Ordering::Greater,
79            Ordering::Less => Ordering::Less,
80            Ordering::Equal => self.phase.cmp(&other.phase),
81        }
82    }
83}
84
85impl PartialOrd for ClockTick {
86    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
87        Some(self.cmp(other))
88    }
89}
90
91impl std::fmt::Display for ClockTick {
92    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
93        write!(f, "{}.{:?}", self.tick, self.phase)
94    }
95}
96
97/// State representing a clock.
98#[derive(Clone)]
99pub struct Clock {
100    /// Frequency of the clock in MHz.
101    /// *Note*: Should never be changed as it is registered at this frequency.
102    freq_mhz: f64,
103
104    pub shared_state: Rc<ClockState>,
105}
106
107pub struct TaskWaker {
108    /// Internal identifier for a scheduled clock wait.
109    pub id: u64,
110
111    /// The Waker to use to make a task active again.
112    pub waker: Waker,
113
114    /// When a task is scheduled in the future it may be a background task
115    /// that will simply run forever in which case it will set `can_exit` to
116    /// true.
117    pub can_exit: bool,
118}
119
120/// Shared state between futures using a Clock and the Clock itself.
121pub struct ClockState {
122    now: RefCell<ClockTick>,
123
124    next_waiter_id: Cell<u64>,
125
126    /// Queue of futures waiting for the right time.
127    pub waiting: RefCell<Vec<Vec<TaskWaker>>>,
128
129    /// Queue of times at which those futures are to be woken. This is kept
130    /// sorted by time so that the last entry is the next to be woken.
131    pub waiting_times: RefCell<Vec<ClockTick>>,
132
133    /// Registered [`Resolve`] functions.
134    pub to_resolve: RefCell<Vec<Rc<dyn Resolve + 'static>>>,
135}
136
137impl ClockState {
138    fn schedule(&self, schedule_time: ClockTick, cx: &mut Context<'_>, can_exit: bool) -> u64 {
139        let waiter_id = self.next_waiter_id.get();
140        self.next_waiter_id.set(waiter_id + 1);
141
142        let mut waiting_times = self.waiting_times.borrow_mut();
143        let mut waiting = self.waiting.borrow_mut();
144        let task_waker = TaskWaker {
145            id: waiter_id,
146            waker: cx.waker().clone(),
147            can_exit,
148        };
149        // Deadlines are descending so the earliest bucket can be popped from
150        // the back.
151        match waiting_times.binary_search_by(|time| schedule_time.cmp(time)) {
152            Ok(index) => waiting[index].push(task_waker),
153            Err(index) => {
154                waiting_times.insert(index, schedule_time);
155                waiting.insert(index, vec![task_waker]);
156            }
157        }
158
159        waiter_id
160    }
161
162    fn unschedule(&self, schedule_time: ClockTick, waiter_id: u64) {
163        let mut waiting_times = self.waiting_times.borrow_mut();
164        let mut waiting = self.waiting.borrow_mut();
165
166        if let Ok(time_index) = waiting_times.binary_search_by(|time| schedule_time.cmp(time))
167            && let Some(waiter_index) = waiting[time_index].iter().position(|w| w.id == waiter_id)
168        {
169            waiting[time_index].remove(waiter_index);
170            if waiting[time_index].is_empty() {
171                waiting.remove(time_index);
172                waiting_times.remove(time_index);
173            }
174        }
175    }
176
177    fn advance_time(&self, to_time: ClockTick) {
178        self.resolve();
179
180        assert!(to_time >= *self.now.borrow(), "Time moving backwards");
181        *self.now.borrow_mut() = to_time;
182    }
183
184    fn resolve(&self) {
185        for r in self.to_resolve.borrow_mut().drain(..) {
186            r.resolve();
187        }
188    }
189}
190
191impl Clock {
192    /// Create a new [Clock] at the specified frequency.
193    #[must_use]
194    pub fn new(freq_mhz: f64) -> Self {
195        let shared_state = Rc::new(ClockState {
196            now: RefCell::new(ClockTick {
197                tick: 0,
198                phase: phase::BEGIN,
199            }),
200            next_waiter_id: Cell::new(0),
201            waiting: RefCell::new(Vec::new()),
202            waiting_times: RefCell::new(Vec::new()),
203            to_resolve: RefCell::new(Vec::new()),
204        });
205
206        Self {
207            freq_mhz,
208            shared_state,
209        }
210    }
211
212    /// Advance the time on this clock
213    pub fn advance_time(&self, to_time: ClockTick) {
214        self.shared_state.advance_time(to_time);
215    }
216
217    /// Returns the clocks frequency in MHz.
218    #[must_use]
219    pub fn freq_mhz(&self) -> f64 {
220        self.freq_mhz
221    }
222
223    /// Returns the current [ClockTick].
224    #[must_use]
225    pub fn tick_now(&self) -> ClockTick {
226        *self.shared_state.now.borrow()
227    }
228
229    /// Returns the current time in `ns`.
230    #[must_use]
231    pub fn time_now_ns(&self) -> f64 {
232        let now = *self.shared_state.now.borrow();
233        self.to_ns(&now)
234    }
235
236    /// Returns the time in `ns` of the next event registered with this clock.
237    #[must_use]
238    pub fn time_of_next(&self) -> f64 {
239        match self.shared_state.waiting_times.borrow().last() {
240            Some(clock_time) => self.to_ns(clock_time),
241            None => f64::MAX,
242        }
243    }
244
245    /// Returns the phase of the next event registered with this clock.
246    #[must_use]
247    pub fn phase_of_next(&self) -> u32 {
248        match self.shared_state.waiting_times.borrow().last() {
249            Some(clock_time) => clock_time.phase(),
250            None => u32::MAX,
251        }
252    }
253
254    /// Convert the given [ClockTick] to a time in `ns` for this clock.
255    #[must_use]
256    pub fn to_ns(&self, clock_time: &ClockTick) -> f64 {
257        clock_time.tick as f64 / self.freq_mhz * 1000.0
258    }
259
260    /// Returns a [ClockDelay] future which must be `await`ed to delay the
261    /// specified number of ticks, rejecting a deadline that overflows.
262    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
263    pub fn wait_ticks(&self, ticks: u64) -> Result<ClockDelay, SimError> {
264        let mut until = self.tick_now();
265        until.tick = until
266            .tick
267            .checked_add(ticks)
268            .ok_or_else(|| SimError("clock wait deadline overflows".into()))?;
269        until.phase = phase::BEGIN;
270        Ok(ClockDelay {
271            shared_state: self.shared_state.clone(),
272            until,
273            can_exit: false,
274            waiter_id: None,
275            done: false,
276        })
277    }
278
279    /// Returns a [ClockDelay] future which must be `await`ed to delay the
280    /// specified number of ticks. However, if the remainder of the simulation
281    /// completes then this future is allowed to not complete. This allows the
282    /// user to create tasks that can run continuously as long as the rest of
283    /// the simulation continues to run. Returns an error if the deadline
284    /// overflows.
285    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
286    pub fn wait_ticks_or_exit(&self, ticks: u64) -> Result<ClockDelay, SimError> {
287        let mut delay = self.wait_ticks(ticks)?;
288        delay.can_exit = true;
289        Ok(delay)
290    }
291
292    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
293    pub fn next_tick_and_phase(&self, phase: u32) -> Result<ClockDelay, SimError> {
294        let mut delay = self.wait_ticks(1)?;
295        delay.until.phase = phase;
296        Ok(delay)
297    }
298
299    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
300    pub fn wait_phase(&self, phase: u32) -> ClockDelay {
301        let mut until = self.tick_now();
302        assert!(phase >= until.phase, "Time going backwards");
303        until.phase = phase;
304        ClockDelay {
305            shared_state: self.shared_state.clone(),
306            until,
307            can_exit: false,
308            waiter_id: None,
309            done: false,
310        }
311    }
312
313    /// Advance to the next tick after the specified time, rejecting
314    /// unrepresentable durations and tick overflow.
315    pub fn advance_to(&self, time_ns: f64) -> SimResult {
316        let now_ns = self.time_now_ns();
317        assert!(now_ns < time_ns);
318        let diff_ns = time_ns - now_ns;
319        let ticks = (diff_ns * (self.freq_mhz / 1000.0)).ceil();
320        // u64::MAX rounds up to 2^64 as f64, so the upper bound is exclusive.
321        if !ticks.is_finite() || !(0.0..u64::MAX as f64).contains(&ticks) {
322            return Err(SimError(
323                "clock advance duration is outside u64 range".into(),
324            ));
325        }
326
327        let mut until = self.tick_now();
328        until.tick = until
329            .tick
330            .checked_add(ticks as u64)
331            .ok_or_else(|| SimError("clock advance deadline overflows".into()))?;
332        until.phase = phase::BEGIN;
333
334        self.shared_state.advance_time(until);
335        Ok(())
336    }
337}
338
339/// The default clocks is simply to use a 1GHz clock so ticks are 1ns.
340impl Default for Clock {
341    fn default() -> Self {
342        Self::new(1000.0)
343    }
344}
345
346/// The comparison operators for Clocks - use the next pending Waker time.
347impl PartialEq for Clock {
348    fn eq(&self, other: &Self) -> bool {
349        self.time_of_next() == other.time_of_next() && self.phase_of_next() == other.phase_of_next()
350    }
351}
352impl Eq for Clock {}
353
354impl Ord for Clock {
355    fn cmp(&self, other: &Self) -> Ordering {
356        self.time_of_next()
357            .total_cmp(&other.time_of_next())
358            .then_with(|| self.phase_of_next().cmp(&other.phase_of_next()))
359    }
360}
361
362impl PartialOrd for Clock {
363    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
364        Some(self.cmp(other))
365    }
366}
367
368impl Resolver for Clock {
369    fn add_resolve(&self, resolve: Rc<dyn Resolve + 'static>) {
370        self.shared_state.to_resolve.borrow_mut().push(resolve);
371    }
372}
373
374/// Future returned by the clock to manage advancing time using async functions.
375pub struct ClockDelay {
376    shared_state: Rc<ClockState>,
377    until: ClockTick,
378    can_exit: bool,
379    waiter_id: Option<u64>,
380    done: bool,
381}
382
383impl Future for ClockDelay {
384    type Output = ();
385    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
386        if self.done {
387            return Poll::Ready(());
388        }
389
390        if self.until > *self.shared_state.now.borrow() {
391            if let Some(waiter_id) = self.waiter_id {
392                self.shared_state.unschedule(self.until, waiter_id);
393            }
394            let waiter_id = self.shared_state.schedule(self.until, cx, self.can_exit);
395            self.waiter_id = Some(waiter_id);
396            Poll::Pending
397        } else {
398            self.waiter_id = None;
399            self.done = true;
400            Poll::Ready(())
401        }
402    }
403}
404
405impl FusedFuture for ClockDelay {
406    fn is_terminated(&self) -> bool {
407        self.done
408    }
409}
410
411impl Drop for ClockDelay {
412    fn drop(&mut self) {
413        if let Some(waiter_id) = self.waiter_id.take() {
414            self.shared_state.unschedule(self.until, waiter_id);
415        }
416    }
417}
418
419#[cfg(test)]
420mod tests {
421    use std::mem::drop;
422    use std::pin::Pin;
423    use std::task::Context;
424
425    use futures::future::FusedFuture;
426    use futures::task::noop_waker;
427
428    use super::*;
429
430    #[test]
431    fn wait_ticks_or_exit_rejects_overflow_and_accepts_maximum_deadline() {
432        let clock = Clock::default();
433        clock.advance_time(ClockTick::new().set_tick(u64::MAX - 1));
434        assert!(clock.wait_ticks_or_exit(2).is_err());
435        let delay = clock.wait_ticks_or_exit(1).unwrap();
436        assert_eq!(delay.until.tick(), u64::MAX);
437        assert_eq!(delay.until.phase(), phase::BEGIN);
438        assert!(delay.can_exit);
439        assert!(clock.shared_state.waiting_times.borrow().is_empty());
440    }
441
442    #[test]
443    fn next_tick_and_phase_rejects_overflow_and_preserves_phase() {
444        let clock = Clock::default();
445        clock.advance_time(ClockTick::new().set_tick(u64::MAX - 1));
446        let delay = clock.next_tick_and_phase(3).unwrap();
447        assert_eq!(delay.until.tick(), u64::MAX);
448        assert_eq!(delay.until.phase(), 3);
449        clock.advance_time(ClockTick::new().set_tick(u64::MAX));
450        assert!(clock.next_tick_and_phase(3).is_err());
451        assert!(clock.shared_state.waiting_times.borrow().is_empty());
452    }
453
454    #[test]
455    fn advance_to_rejects_tick_overflow_without_advancing_time() {
456        let clock = Clock::default();
457        // The duration is a representable 2048 ticks, but its deadline is 2^64.
458        let start_tick = u64::MAX - 2047;
459        clock.advance_time(ClockTick::new().set_tick(start_tick));
460        assert!(clock.advance_to(u64::MAX as f64).is_err());
461        assert_eq!(clock.tick_now().tick(), start_tick);
462    }
463
464    #[test]
465    fn advance_to_rejects_duration_at_u64_upper_bound() {
466        let clock = Clock::default();
467        assert!(clock.advance_to(u64::MAX as f64).is_err());
468        assert_eq!(clock.tick_now(), ClockTick::default());
469    }
470
471    #[test]
472    fn advance_to_rejects_infinite_duration() {
473        let clock = Clock::default();
474        assert!(clock.advance_to(f64::INFINITY).is_err());
475        assert_eq!(clock.tick_now(), ClockTick::default());
476    }
477
478    #[test]
479    fn advance_to_accepts_largest_f64_duration_below_u64_upper_bound() {
480        let clock = Clock::default();
481        // The largest f64 below 2^64 is 2^64 - 2048.
482        let ticks = 18_446_744_073_709_549_568_u64;
483        clock.advance_to(ticks as f64).unwrap();
484        assert_eq!(clock.tick_now().tick(), ticks);
485        assert_eq!(clock.tick_now().phase(), phase::BEGIN);
486    }
487
488    #[test]
489    fn wait_ticks_rejects_deadline_overflow() {
490        let clock = Clock::default();
491        clock.advance_time(ClockTick::new().set_tick(u64::MAX - 1));
492        assert!(clock.wait_ticks(2).is_err());
493        assert!(clock.shared_state.waiting_times.borrow().is_empty());
494        assert!(clock.shared_state.waiting.borrow().is_empty());
495    }
496
497    #[test]
498    fn wait_ticks_accepts_maximum_deadline_and_zero_wait() {
499        let clock = Clock::default();
500        clock.advance_time(ClockTick::new().set_tick(u64::MAX - 1));
501        let delay = clock.wait_ticks(1).unwrap();
502        assert_eq!(delay.until.tick(), u64::MAX);
503        clock.advance_time(ClockTick::new().set_tick(u64::MAX));
504        let delay = clock.wait_ticks(0).unwrap();
505        assert_eq!(delay.until.tick(), u64::MAX);
506    }
507
508    #[test]
509    fn convert_to_ns() {
510        let clk_ghz = Clock::new(1000.0);
511        assert_eq!(1.0, clk_ghz.to_ns(&ClockTick::new().set_tick(1)));
512
513        let slow_clk = Clock::new(0.5);
514        assert_eq!(2000.0, slow_clk.to_ns(&ClockTick::new().set_tick(1)));
515    }
516
517    #[test]
518    fn clock_tick_accessors_default_display_and_ordering() {
519        let default_tick = ClockTick::default();
520        assert_eq!(default_tick.tick(), 0);
521        assert_eq!(default_tick.phase(), phase::BEGIN);
522        assert_eq!(default_tick.to_string(), "0.0");
523
524        let earlier = ClockTick::new().set_tick(1);
525        let later = ClockTick::new().set_tick(2);
526        assert!(earlier < later);
527        assert_eq!(earlier.partial_cmp(&later), Some(Ordering::Less));
528    }
529
530    #[test]
531    fn clock_tick_phase_accessors_display_and_ordering() {
532        let tick = ClockTick::new().set_tick(1).set_phase(2);
533        assert_eq!(tick.phase(), 2);
534        assert_eq!(tick.to_string(), "1.2");
535
536        let earlier_phase = ClockTick::new().set_tick(1).set_phase(1);
537        assert!(earlier_phase < tick);
538
539        let later_tick = ClockTick::new().set_tick(2).set_phase(0);
540        assert!(later_tick > tick);
541    }
542
543    #[test]
544    fn clock_default_advance_and_ordering() {
545        let clock = Clock::default();
546        assert_eq!(clock.freq_mhz(), 1000.0);
547
548        clock.advance_to(2.1).unwrap();
549        assert_eq!(clock.tick_now().tick(), 3);
550        assert_eq!(clock.tick_now().phase(), phase::BEGIN);
551        assert_eq!(clock.time_now_ns(), 3.0);
552
553        let earlier = Clock::new(1000.0);
554        let later = Clock::new(1000.0);
555        drop(earlier.wait_ticks(1).unwrap());
556        drop(later.wait_ticks(2).unwrap());
557
558        assert!(earlier == later);
559        assert_eq!(earlier.partial_cmp(&later), Some(Ordering::Equal));
560    }
561
562    #[test]
563    fn unschedule_unknown_waiter_is_a_noop() {
564        let clock = Clock::new(1000.0);
565        let scheduled_time = ClockTick::new().set_tick(1);
566
567        clock
568            .shared_state
569            .waiting_times
570            .borrow_mut()
571            .push(scheduled_time);
572        clock.shared_state.waiting.borrow_mut().push(Vec::new());
573
574        clock.shared_state.unschedule(scheduled_time, 7);
575
576        assert_eq!(clock.shared_state.waiting_times.borrow().len(), 1);
577        assert_eq!(clock.shared_state.waiting.borrow().len(), 1);
578    }
579
580    #[test]
581    fn unschedule_waiter_keeps_time_when_other_waiters_remain() {
582        let clock = Clock::new(1000.0);
583        let scheduled_time = ClockTick::new().set_tick(1);
584        let waker = noop_waker();
585        let mut cx = Context::from_waker(&waker);
586
587        let first_waiter_id = clock.shared_state.schedule(scheduled_time, &mut cx, false);
588        let second_waiter_id = clock.shared_state.schedule(scheduled_time, &mut cx, false);
589
590        clock
591            .shared_state
592            .unschedule(scheduled_time, first_waiter_id);
593
594        let waiting_times = clock.shared_state.waiting_times.borrow();
595        let waiting = clock.shared_state.waiting.borrow();
596
597        assert_eq!(waiting_times.as_slice(), &[scheduled_time]);
598        assert_eq!(waiting.len(), 1);
599        assert_eq!(waiting[0].len(), 1);
600        assert_eq!(waiting[0][0].id, second_waiter_id);
601    }
602
603    #[test]
604    fn clock_delay_is_fused_after_completion() {
605        let clock = Clock::new(1000.0);
606        let waker = noop_waker();
607        let mut cx = Context::from_waker(&waker);
608        let mut delay = clock.wait_ticks(1).unwrap();
609
610        assert!(!delay.is_terminated());
611        assert_eq!(Pin::new(&mut delay).poll(&mut cx), Poll::Pending);
612        assert!(!delay.is_terminated());
613
614        clock.advance_time(ClockTick::new().set_tick(1));
615        assert_eq!(Pin::new(&mut delay).poll(&mut cx), Poll::Ready(()));
616        assert!(delay.is_terminated());
617        assert_eq!(Pin::new(&mut delay).poll(&mut cx), Poll::Ready(()));
618        assert!(delay.is_terminated());
619    }
620
621    #[test]
622    fn phase_wait_helpers_schedule_phase_delays() {
623        let clock = Clock::new(1000.0);
624
625        let next_tick = clock.next_tick_and_phase(3).unwrap();
626        assert_eq!(next_tick.until.tick(), 1);
627        assert_eq!(next_tick.until.phase(), 3);
628
629        let same_tick = clock.wait_phase(1);
630        assert_eq!(same_tick.until.tick(), 0);
631        assert_eq!(same_tick.until.phase(), 1);
632    }
633
634    #[test]
635    fn tick_waits_resume_in_end_phase() {
636        let clock = Clock::new(1000.0);
637
638        let begin = clock.wait_phase(phase::END);
639        assert_eq!(begin.until.tick(), 0);
640        assert_eq!(begin.until.phase(), phase::END);
641
642        clock.advance_time(ClockTick::new().set_phase(phase::END));
643
644        let delay = clock.wait_ticks(1).unwrap();
645        assert_eq!(delay.until.tick(), 1);
646        assert_eq!(delay.until.phase(), phase::BEGIN);
647    }
648}