Timers in Chrono

Chrono timers are implemented much the same way as in embassy. We have a queue of timers and a main time driver that processes all the timers in that queue.

The queue is an intrusive doubly linked list. A task has pointers directly embedded into it that point to the previous and next timer. When a timer is scheduled, it is added to the end of the queue. When the runtime processes timers, it walks through them from head to tail. We'll go through how sleep is implemented to understand how the system works in detail.

chrono::time::sleep is a function that returns a future Sleep.

pub struct Sleep {
    deadline: Instant,
}

It has a deadline that specifies when it is over. The trait Future is implemented for Sleep (obviously).

impl Future for Sleep {
    type Output = ();

    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
        if self.done() {
            Poll::Ready(())
        } else {
            let header = waker::header(cx.waker());
            unsafe { ((*header).vtable.schedule_timer)(waker::ptr(cx.waker()), self.deadline) }
            Poll::Pending
        }
    }
}

If the future is not done, we schedule a timer (i.e insert to the end of the timer queue). This updates all the necessary pointers for each task. The timer queue also contains a deadline. This is the closest deadline of all tasks. For example if we had task A that expires in 5 seconds and task B that expires in 3 seconds, the timer queue will have a deadline set to 3 seconds from now. Once that time is over, we process all the timers and reset the timer deadline to the shortest of the remaining timers and so on.

    unsafe fn schedule_timer(ptr: *const (), deadline: Instant) {
        ...
        ...
        timer_queue.as_mut().unwrap().push_back(task_ptr);
    }

The runtime processes all these timers.

pub fn block_on<F: Future>(&mut self, future: F) -> F::Output {
  if let Poll::Ready(v) = future.as_mut().poll(cx) {
    return v;
  }

  let queue = unsafe { &mut (*self.queue) };
  if queue.is_empty() {
    defmt::debug!("Queue empty. Waiting for event");
    cortex_m::asm::wfe()
  }

  // IMPORTANT PART HERE:
  // 1. Process timers and schedule any the task associated that are ready to be polled
  // 2. Start the timer driver's countdown 
  // 3. Poll the tasks

  // Process timers. Populates the queue with tasks that are ready to execute
  let timer_queue = unsafe { &mut (*self.timer_queue) };
  let now = Instant::now();
  timer_queue.process(now);

  // Start the timer
  if let Some(deadline) = timer_queue.deadline() {
    let dur = deadline - Instant::now();
    timer::timer().start(dur);
    defmt::debug!("Started timer. Deadline in {}", dur);
  }

  loop {
    let task = queue.pop();
    match task {
      Some(task) => {
        defmt::debug!("Running task {}:", task.id);
        task.run()
      }
      None => break,
    }
  }

Processing the timers is pretty wacky since we actually don't have any ordering guarantees. That is, a task may have a timer associated with it that is anywhere in the timer queue - it could the head, the tail or a random element somewhere in the queue. We don't know! We have to find out which pointers we need to update (depending on where the task is positioned) and if it is ready, we schedule the task associated with it which is then polled again.

During the processing stage, we set the deadline of the timer queue and start the countdown timer. This will fire off once it hits zero, waking up the executor (if it sleeping).