capsules_core/virtualizers/
virtual_alarm.rs

1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Virtualize the Alarm interface to enable multiple users of an underlying
6//! alarm hardware peripheral.
7
8use core::cell::Cell;
9
10use kernel::collections::list::{List, ListLink, ListNode};
11use kernel::hil::time::{self, Alarm, Ticks, Time};
12use kernel::utilities::cells::OptionalCell;
13use kernel::ErrorCode;
14
15#[derive(Copy, Clone)]
16struct TickDtReference<T: Ticks> {
17    /// Reference time point when this alarm was setup.
18    reference: T,
19    /// Duration of this alarm w.r.t. the reference time point. In other words, this alarm should
20    /// fire at `reference + dt`.
21    dt: T,
22    /// True if this dt only represents a portion of the original dt that was requested. If true,
23    /// then we need to wait for another max_tick/2 after an internal extended dt reference alarm
24    /// fires. This ensures we can wait the full max_tick even if there is latency in the system.
25    extended: bool,
26}
27
28impl<T: Ticks> TickDtReference<T> {
29    #[inline]
30    fn reference_plus_dt(&self) -> T {
31        self.reference.wrapping_add(self.dt)
32    }
33}
34
35/// An object to multiplex multiple "virtual" alarms over a single underlying alarm. A
36/// `VirtualMuxAlarm` is a node in a linked list of alarms that share the same underlying alarm.
37pub struct VirtualMuxAlarm<'a, A: Alarm<'a>> {
38    /// Underlying alarm which multiplexes all these virtual alarm.
39    mux: &'a MuxAlarm<'a, A>,
40    /// Reference and dt point when this alarm was setup.
41    dt_reference: Cell<TickDtReference<A::Ticks>>,
42    /// Whether this alarm is currently armed, i.e. whether it should fire when the time has
43    /// elapsed.
44    armed: Cell<bool>,
45    /// Next alarm in the list.
46    next: ListLink<'a, VirtualMuxAlarm<'a, A>>,
47    /// Alarm client for this node in the list.
48    client: OptionalCell<&'a dyn time::AlarmClient>,
49}
50
51impl<'a, A: Alarm<'a>> ListNode<'a, VirtualMuxAlarm<'a, A>> for VirtualMuxAlarm<'a, A> {
52    fn next(&self) -> &'a ListLink<VirtualMuxAlarm<'a, A>> {
53        &self.next
54    }
55}
56
57impl<'a, A: Alarm<'a>> VirtualMuxAlarm<'a, A> {
58    /// After calling new, always call setup()
59    pub fn new(mux_alarm: &'a MuxAlarm<'a, A>) -> VirtualMuxAlarm<'a, A> {
60        let zero = A::Ticks::from(0);
61        VirtualMuxAlarm {
62            mux: mux_alarm,
63            dt_reference: Cell::new(TickDtReference {
64                reference: zero,
65                dt: zero,
66                extended: false,
67            }),
68            armed: Cell::new(false),
69            next: ListLink::empty(),
70            client: OptionalCell::empty(),
71        }
72    }
73
74    /// Call this method immediately after new() to link this to the mux, otherwise alarms won't
75    /// fire
76    pub fn setup(&'a self) {
77        self.mux.virtual_alarms.push_head(self);
78    }
79}
80
81impl<'a, A: Alarm<'a>> Time for VirtualMuxAlarm<'a, A> {
82    type Frequency = A::Frequency;
83    type Ticks = A::Ticks;
84
85    fn now(&self) -> Self::Ticks {
86        self.mux.alarm.now()
87    }
88}
89
90impl<'a, A: Alarm<'a>> Alarm<'a> for VirtualMuxAlarm<'a, A> {
91    fn set_alarm_client(&self, client: &'a dyn time::AlarmClient) {
92        self.client.set(client);
93    }
94
95    fn disarm(&self) -> Result<(), ErrorCode> {
96        if !self.armed.get() {
97            return Ok(());
98        }
99
100        self.armed.set(false);
101
102        let enabled = self.mux.enabled.get() - 1;
103        self.mux.enabled.set(enabled);
104
105        // If there are not more enabled alarms, disable the underlying alarm
106        // completely.
107        if enabled == 0 {
108            let _ = self.mux.alarm.disarm();
109        }
110        Ok(())
111    }
112
113    fn is_armed(&self) -> bool {
114        self.armed.get()
115    }
116
117    fn set_alarm(&self, reference: Self::Ticks, dt: Self::Ticks) {
118        let enabled = self.mux.enabled.get();
119        let half_max = Self::Ticks::half_max_value();
120        // If the dt is more than half of the available time resolution, then we need to break
121        // up the alarm into two internal alarms. This ensures that our internal comparisons of
122        // now outside of range [ref, ref + dt) will trigger correctly even with latency in the
123        // system
124        let dt_reference = if dt > half_max.wrapping_add(self.minimum_dt()) {
125            TickDtReference {
126                reference,
127                dt: dt.wrapping_sub(half_max),
128                extended: true,
129            }
130        } else {
131            TickDtReference {
132                reference,
133                dt,
134                extended: false,
135            }
136        };
137        self.dt_reference.set(dt_reference);
138        // Ensure local variable has correct value when used below
139        let dt = dt_reference.dt;
140
141        if !self.armed.get() {
142            self.mux.enabled.set(enabled + 1);
143            self.armed.set(true);
144        }
145
146        // First alarm, so set it
147        if enabled == 0 {
148            //debug!("virtual_alarm: first alarm: set it.");
149            self.mux.set_alarm(reference, dt);
150        } else if !self.mux.firing.get() {
151            // If firing is true, the mux will scan all the alarms after
152            // firing and pick the soonest one so do not need to modify the
153            // mux. Otherwise, this is an alarm
154            // started in a separate code path (e.g., another event).
155            // This new alarm fires sooner if two things are both true:
156            //    1. The current earliest alarm expiration doesn't fall
157            //    in the range of [reference, reference+dt): this means
158            //    it is either in the past (before reference) or the future
159            //    (reference + dt), AND
160            //    2. now falls in the [reference, reference+dt)
161            //    window of the current earliest alarm. This means the
162            //    current earliest alarm hasn't fired yet (it is in the future).
163            // -pal
164            let cur_alarm = self.mux.alarm.get_alarm();
165            let now = self.mux.alarm.now();
166            let expiration = reference.wrapping_add(dt);
167            if !cur_alarm.within_range(reference, expiration) {
168                let next = self.mux.next_tick_vals.get();
169                if next.is_none_or(|(next_reference, next_dt)| {
170                    now.within_range(next_reference, next_reference.wrapping_add(next_dt))
171                }) {
172                    self.mux.set_alarm(reference, dt);
173                }
174            } else {
175                // current alarm will fire earlier, keep it
176            }
177        }
178    }
179
180    fn get_alarm(&self) -> Self::Ticks {
181        let dt_reference = self.dt_reference.get();
182        let extension = if dt_reference.extended {
183            Self::Ticks::half_max_value()
184        } else {
185            Self::Ticks::from(0)
186        };
187        dt_reference.reference_plus_dt().wrapping_add(extension)
188    }
189
190    fn minimum_dt(&self) -> Self::Ticks {
191        self.mux.alarm.minimum_dt()
192    }
193}
194
195impl<'a, A: Alarm<'a>> time::AlarmClient for VirtualMuxAlarm<'a, A> {
196    fn alarm(&self) {
197        self.client.map(|client| client.alarm());
198    }
199}
200
201/// Structure to control a set of virtual alarms multiplexed together on top of a single alarm.
202pub struct MuxAlarm<'a, A: Alarm<'a>> {
203    /// Head of the linked list of virtual alarms multiplexed together.
204    virtual_alarms: List<'a, VirtualMuxAlarm<'a, A>>,
205    /// Number of virtual alarms that are currently enabled.
206    enabled: Cell<usize>,
207    /// Underlying alarm, over which the virtual alarms are multiplexed.
208    alarm: &'a A,
209    /// Whether we are firing; used to delay restarted alarms
210    firing: Cell<bool>,
211    /// Reference to next alarm
212    next_tick_vals: Cell<Option<(A::Ticks, A::Ticks)>>,
213}
214
215impl<'a, A: Alarm<'a>> MuxAlarm<'a, A> {
216    pub const fn new(alarm: &'a A) -> MuxAlarm<'a, A> {
217        MuxAlarm {
218            virtual_alarms: List::new(),
219            enabled: Cell::new(0),
220            alarm,
221            firing: Cell::new(false),
222            next_tick_vals: Cell::new(None),
223        }
224    }
225
226    pub fn set_alarm(&self, reference: A::Ticks, dt: A::Ticks) {
227        self.next_tick_vals.set(Some((reference, dt)));
228        self.alarm.set_alarm(reference, dt);
229    }
230
231    pub fn disarm(&self) {
232        self.next_tick_vals.set(None);
233        let _ = self.alarm.disarm();
234    }
235}
236
237impl<'a, A: Alarm<'a>> time::AlarmClient for MuxAlarm<'a, A> {
238    /// When the underlying alarm has fired, we have to multiplex this event back to the virtual
239    /// alarms that should now fire.
240    fn alarm(&self) {
241        // Check whether to fire each alarm. At this level, alarms are one-shot,
242        // so a repeating client will set it again in the alarm() callback.
243        self.firing.set(true);
244        self.virtual_alarms
245            .iter()
246            .filter(|cur| {
247                let dt_ref = cur.dt_reference.get();
248                // It is very important to get the current now time as the reference could have been
249                // set from now in the previous for_each iteration. We rely on the reference always
250                // being in the past when compared to now.
251                let now = self.alarm.now();
252                cur.armed.get() && !now.within_range(dt_ref.reference, dt_ref.reference_plus_dt())
253            })
254            .for_each(|cur| {
255                let dt_ref = cur.dt_reference.get();
256                if dt_ref.extended {
257                    // The first part of the extended alarm just fired, leave alarm armed with
258                    // remaining time.
259                    cur.dt_reference.set(TickDtReference {
260                        reference: dt_ref.reference_plus_dt(),
261                        dt: A::Ticks::half_max_value(),
262                        extended: false,
263                    });
264                } else {
265                    // Alarm fully expired, disarm and fire callback
266                    cur.armed.set(false);
267                    self.enabled.set(self.enabled.get() - 1);
268                    //debug!("  Virtualizer: {:?} outside {:?}-{:?}, fire!", now, cur.reference.get(), cur.reference.get().wrapping_add(cur.dt.get()));
269                    cur.alarm();
270                }
271            });
272        self.firing.set(false);
273        // Find the soonest alarm client (if any) and set the "next" underlying
274        // alarm based on it.  This needs to happen after firing all expired
275        // alarms since those may have reset new alarms.
276        let now = self.alarm.now();
277        let next = self
278            .virtual_alarms
279            .iter()
280            .filter(|cur| cur.armed.get())
281            .min_by_key(|cur| {
282                let when = cur.dt_reference.get();
283                // If the alarm has already expired, then it should be
284                // considered as the earliest possible (0 ticks), so it
285                // will trigger as soon as possible. This can happen
286                // if the alarm expired *after* it was examined in the
287                // above loop.
288                if !now.within_range(when.reference, when.reference_plus_dt()) {
289                    A::Ticks::from(0u32)
290                } else {
291                    when.reference_plus_dt().wrapping_sub(now)
292                }
293            });
294
295        // Set the alarm.
296        if let Some(valrm) = next {
297            let dt_reference = valrm.dt_reference.get();
298            self.set_alarm(dt_reference.reference, dt_reference.dt);
299        } else {
300            self.disarm();
301        }
302    }
303}
304
305#[cfg(test)]
306mod tests {
307    use super::*;
308    use time::*;
309
310    struct FakeAlarm<'a> {
311        now: Cell<Ticks32>,
312        reference: Cell<Ticks32>,
313        dt: Cell<Ticks32>,
314        armed: Cell<bool>,
315        client: OptionalCell<&'a dyn AlarmClient>,
316    }
317
318    impl FakeAlarm<'_> {
319        fn new() -> Self {
320            Self {
321                now: Cell::new(1_000u32.into()),
322                reference: Cell::new(0u32.into()),
323                dt: Cell::new(0u32.into()),
324                armed: Cell::new(false),
325                client: OptionalCell::empty(),
326            }
327        }
328
329        /// The emulated delay from when hardware timer to when kernel loop will
330        /// run to check if alarms have fired or not.
331        pub fn hardware_delay(&self) -> Ticks32 {
332            Ticks32::from(10)
333        }
334
335        /// Fast forwards time to the next time we would fire an alarm and call client. Returns if
336        /// alarm is still armed after triggering client
337        pub fn trigger_next_alarm(&self) -> bool {
338            if !self.is_armed() {
339                return false;
340            }
341            self.now.set(
342                self.reference
343                    .get()
344                    .wrapping_add(self.dt.get())
345                    .wrapping_add(self.hardware_delay()),
346            );
347            self.client.map(|c| c.alarm());
348            self.is_armed()
349        }
350
351        /// Runs for the specified number of ticks as long as there are alarms armed.
352        pub fn run_for_ticks(&self, left: Ticks32) {
353            let final_now = self.now.get().wrapping_add(left);
354            let mut left = left.into_u32();
355
356            while self.is_armed() {
357                // Ensure that we have enough remaining ticks to handle the next alarm. Reference is
358                // always in the past, so we need to figure out the difference between the reference
359                // and now to discount the DT the alarm needs to wait by.
360                let ticks_from_reference = self.now.get().wrapping_sub(self.reference.get());
361                let dt = self
362                    .dt
363                    .get()
364                    .into_u32()
365                    .saturating_sub(ticks_from_reference.into_u32());
366                if dt <= left {
367                    left -= dt;
368                    self.trigger_next_alarm();
369                } else {
370                    break;
371                }
372            }
373            // Ensure that we ate up all of the time we were suppose to run for
374            self.now.set(final_now);
375        }
376    }
377
378    impl Time for FakeAlarm<'_> {
379        type Ticks = Ticks32;
380        type Frequency = Freq1KHz;
381
382        fn now(&self) -> Ticks32 {
383            // Every time we get now, it needs to increment to represent a free running timer
384            let new_now = Ticks32::from(self.now.get().into_u32() + 1);
385            self.now.set(new_now);
386            new_now
387        }
388    }
389
390    impl<'a> Alarm<'a> for FakeAlarm<'a> {
391        fn set_alarm_client(&self, client: &'a dyn AlarmClient) {
392            self.client.set(client);
393        }
394
395        fn set_alarm(&self, reference: Self::Ticks, dt: Self::Ticks) {
396            self.reference.set(reference);
397            self.dt.set(dt);
398            self.armed.set(true);
399        }
400
401        fn get_alarm(&self) -> Self::Ticks {
402            self.reference.get().wrapping_add(self.dt.get())
403        }
404
405        fn disarm(&self) -> Result<(), ErrorCode> {
406            self.armed.set(false);
407            Ok(())
408        }
409
410        fn is_armed(&self) -> bool {
411            self.armed.get()
412        }
413
414        fn minimum_dt(&self) -> Self::Ticks {
415            0u32.into()
416        }
417    }
418
419    struct ClientCounter(Cell<usize>);
420    impl ClientCounter {
421        fn new() -> Self {
422            Self(Cell::new(0))
423        }
424        fn count(&self) -> usize {
425            self.0.get()
426        }
427    }
428    impl AlarmClient for ClientCounter {
429        fn alarm(&self) {
430            self.0.set(self.0.get() + 1);
431        }
432    }
433
434    fn run_until_disarmed(alarm: &FakeAlarm) {
435        // Don't loop forever if we never disarm
436        for _ in 0..20 {
437            if !alarm.trigger_next_alarm() {
438                return;
439            }
440        }
441    }
442
443    #[test]
444    fn test_single_max_ticks_dt() {
445        let alarm = FakeAlarm::new();
446        let client = ClientCounter::new();
447        let dt = u32::MAX.into();
448
449        let mux = MuxAlarm::new(&alarm);
450        alarm.set_alarm_client(&mux);
451
452        let valarm = VirtualMuxAlarm::new(&mux);
453        valarm.setup();
454        valarm.set_alarm_client(&client);
455        valarm.set_alarm(valarm.now(), dt);
456
457        run_until_disarmed(&alarm);
458
459        assert_eq!(client.count(), 1);
460    }
461
462    #[test]
463    fn test_multiple_max_ticks_dt() {
464        let alarm = FakeAlarm::new();
465        let client = ClientCounter::new();
466        let dt = u32::MAX.into();
467
468        let mux = MuxAlarm::new(&alarm);
469        alarm.set_alarm_client(&mux);
470
471        let v_alarms = &[
472            VirtualMuxAlarm::new(&mux),
473            VirtualMuxAlarm::new(&mux),
474            VirtualMuxAlarm::new(&mux),
475        ];
476
477        for (i, v) in v_alarms.iter().enumerate() {
478            v.setup();
479            v.set_alarm_client(&client);
480            // Start with reference in the past since fake alarm now start with 1000 as now()
481            v.set_alarm((i as u32).into(), dt);
482        }
483        run_until_disarmed(&alarm);
484
485        assert_eq!(client.count(), 3);
486    }
487
488    struct SetAlarmClient<'a> {
489        alarm: &'a VirtualMuxAlarm<'a, FakeAlarm<'a>>,
490        dt: u32,
491    }
492
493    impl<'a> SetAlarmClient<'a> {
494        fn new(alarm: &'a VirtualMuxAlarm<'a, FakeAlarm<'a>>, dt: u32) -> Self {
495            Self { alarm, dt }
496        }
497    }
498
499    impl AlarmClient for SetAlarmClient<'_> {
500        fn alarm(&self) {
501            self.alarm.set_alarm(self.alarm.now(), self.dt.into());
502        }
503    }
504
505    #[test]
506    fn test_second_alarm_set_during_first_alarm_firing() {
507        let alarm = FakeAlarm::new();
508        let mux = MuxAlarm::new(&alarm);
509        alarm.set_alarm_client(&mux);
510
511        // It is important that 0 is setup last so it is first in the linked list
512        let v_alarms = &[VirtualMuxAlarm::new(&mux), VirtualMuxAlarm::new(&mux)];
513        v_alarms[1].setup();
514        v_alarms[0].setup();
515
516        let set_v1_alarm = SetAlarmClient::new(&v_alarms[1], 100);
517        v_alarms[0].set_alarm_client(&set_v1_alarm);
518
519        let counter = ClientCounter::new();
520        v_alarms[1].set_alarm_client(&counter);
521
522        // Set the first alarm for 10 ticks in the future. This should then set the second alarm,
523        // but not call fired for the second alarm until the timer gets to 100
524        v_alarms[0].set_alarm(0.into(), 10.into());
525        let still_armed = alarm.trigger_next_alarm();
526
527        // Second alarm should not have triggered yet
528        assert!(alarm.now().into_u32() < 100);
529        assert_eq!(counter.count(), 0);
530        assert!(still_armed);
531
532        let still_armed = alarm.trigger_next_alarm();
533
534        assert!(alarm.now().into_u32() > 100);
535        assert_eq!(counter.count(), 1);
536        assert!(!still_armed);
537    }
538
539    #[test]
540    fn test_quick_alarms_not_skipped() {
541        let alarm = FakeAlarm::new();
542        let client = ClientCounter::new();
543
544        let mux = MuxAlarm::new(&alarm);
545        alarm.set_alarm_client(&mux);
546
547        let v_alarms = &[
548            VirtualMuxAlarm::new(&mux),
549            VirtualMuxAlarm::new(&mux),
550            VirtualMuxAlarm::new(&mux),
551            VirtualMuxAlarm::new(&mux),
552            VirtualMuxAlarm::new(&mux),
553            VirtualMuxAlarm::new(&mux),
554        ];
555
556        // Precalculated the now and dt for all alarms. The DT should be large enough that the
557        // initial check for firing is not true, but after evaluating all alarms, they would all
558        // be firing. This happens since time "progresses" every time now() is called, which
559        // emulates the clock progressing in real time.
560        let now = alarm.now();
561        let dt = alarm
562            .hardware_delay()
563            .wrapping_add(Ticks32::from(v_alarms.len() as u32));
564
565        for v in v_alarms {
566            v.setup();
567            v.set_alarm_client(&client);
568            v.set_alarm(now, dt);
569        }
570
571        // Set one alarm to trigger immediately (at the hardware delay) and the other alarm to
572        // trigger in the future by some large degree
573        v_alarms[0].set_alarm(now, 0.into());
574        v_alarms[1].set_alarm(now, 1_000.into());
575
576        // Run the alarm long enough for every alarm but the longer alarm to fire, and all other
577        // alarms should have fired once
578        alarm.run_for_ticks(Ticks32::from(750));
579        assert_eq!(client.count(), v_alarms.len() - 1);
580        // Run the alarm long enough for the longer alarm to fire as well and verify count
581        alarm.run_for_ticks(Ticks32::from(750));
582        assert_eq!(client.count(), v_alarms.len());
583    }
584}
capsules_core/virtualizers/virtual_alarm.rs

capsules_core/virtualizers/
virtual_alarm.rs
