kernel/platform/
scheduler_timer.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
// Licensed under the Apache License, Version 2.0 or the MIT License.
// SPDX-License-Identifier: Apache-2.0 OR MIT
// Copyright Tock Contributors 2022.

//! Scheduler Timer for enforcing Process Timeslices
//!
//! Interface for use by the Kernel to configure timers which can preempt
//! userspace processes.

use crate::hil::time::{self, Frequency, Ticks};

use core::num::NonZeroU32;

/// Interface for the system scheduler timer.
///
/// A system scheduler timer provides a countdown timer to enforce process
/// scheduling time quanta. Implementations should have consistent timing while
/// the CPU is active, but need not operate during sleep. Note, many scheduler
/// implementations also charge time spent running the kernel on behalf of the
/// process against the process time quantum.
///
/// The primary requirement an implementation of this interface must satisfy is
/// it must be capable of generating an interrupt when the timer expires. This
/// interrupt will interrupt the executing process, returning control to the
/// kernel, and allowing the scheduler to make decisions about what to run next.
///
/// On most chips, this interface will be implemented by a core peripheral (e.g.
/// the ARM core SysTick peripheral). However, some chips lack this optional
/// peripheral, in which case it might be implemented by another timer or alarm
/// peripheral, or require virtualization on top of a shared hardware timer.
///
/// The `SchedulerTimer` interface is carefully designed to be rather general to
/// support the various implementations required on different hardware
/// platforms. The general operation is the kernel will start a timer, which
/// starts the time quantum assigned to a process. While the process is running,
/// the kernel will arm the timer, telling the implementation it must ensure
/// that an interrupt will occur when the time quantum is exhausted. When the
/// process has stopped running, the kernel will disarm the timer, indicating to
/// the implementation that an interrupt is no longer required. To check if the
/// process has exhausted its time quantum the kernel will explicitly ask the
/// implementation. The kernel itself does not expect to get an interrupt to
/// handle when the time quantum is exhausted. This is because the time quantum
/// may end while the kernel itself is running, and the kernel does not need to
/// effectively preempt itself.
///
/// The `arm()` and `disarm()` functions in this interface serve as an optional
/// optimization opportunity. This pair allows an implementation to only enable
/// the interrupt when it is strictly necessary, i.e. while the process is
/// actually executing. However, a correct implementation can have interrupts
/// enabled anytime the scheduler timer has been started. What the
/// implementation must ensure is that the interrupt is enabled when `arm()` is
/// called.
///
/// Implementations must take care when using interrupts. Since the
/// `SchedulerTimer` is used in the core kernel loop and scheduler, top half
/// interrupt handlers may not have executed before `SchedulerTimer` functions
/// are called. In particular, implementations on top of virtualized timers may
/// receive the interrupt fired upcall "late" (i.e. after the kernel calls
/// `has_expired()`). Implementations should ensure that they can reliably check
/// for timeslice expirations.
pub trait SchedulerTimer {
    /// Start a timer for a process timeslice. The `us` argument is the length
    /// of the timeslice in microseconds.
    ///
    /// This must set a timer for an interval as close as possible to the given
    /// interval in microseconds. Interrupts do not need to be enabled. However,
    /// if the implementation cannot separate time keeping from interrupt
    /// generation, the implementation of `start()` should enable interrupts and
    /// leave them enabled anytime the timer is active.
    ///
    /// Callers can assume at least a 24-bit wide clock. Specific timing is
    /// dependent on the driving clock. For ARM boards with a dedicated SysTick
    /// peripheral, increments of 10ms are most accurate thanks to additional
    /// hardware support for this value. ARM SysTick supports intervals up to
    /// 400ms.
    fn start(&self, us: NonZeroU32);

    /// Reset the SchedulerTimer.
    ///
    /// This must reset the timer, and can safely disable it and put it in a low
    /// power state. Calling any function other than `start()` immediately after
    /// `reset()` is invalid.
    ///
    /// Implementations _should_ disable the timer and put it in a lower power
    /// state. However, not all implementations will be able to guarantee this
    /// (for example depending on the underlying hardware or if the timer is
    /// implemented on top of a virtualized timer).
    fn reset(&self);

    /// Arm the SchedulerTimer timer and ensure an interrupt will be generated.
    ///
    /// The timer must already be started by calling `start()`. This function
    /// guarantees that an interrupt will be generated when the already started
    /// timer expires. This interrupt will preempt the running userspace
    /// process.
    ///
    /// If the interrupt is already enabled when `arm()` is called, this
    /// function should be a no-op implementation.
    fn arm(&self);

    /// Disarm the SchedulerTimer timer indicating an interrupt is no longer
    /// required.
    ///
    /// This does not stop the timer, but indicates to the SchedulerTimer that
    /// an interrupt is no longer required (i.e. the process is no longer
    /// executing). By not requiring an interrupt this may allow certain
    /// implementations to be more efficient by removing the overhead of
    /// handling the interrupt.
    ///
    /// If the implementation cannot disable the interrupt without stopping the
    /// time keeping mechanism, this function should be a no-op implementation.
    fn disarm(&self);

    /// Return the number of microseconds remaining in the process's timeslice
    /// if the timeslice is still active.
    ///
    /// If the timeslice is still active, this returns `Some()` with the number
    /// of microseconds remaining in the timeslice. If the timeslice has
    /// expired, this returns `None`.
    ///
    /// This function may not be called after it has returned `None` (signifying
    /// the timeslice has expired) for a given timeslice until `start()` is
    /// called again (to start a new timeslice). If `get_remaining_us()` is
    /// called again after returning `None` without an intervening call to
    /// `start()`, the return value is unspecified and implementations may
    /// return whatever they like.
    fn get_remaining_us(&self) -> Option<NonZeroU32>;
}

/// A dummy `SchedulerTimer` implementation in which the timer never expires.
///
/// Using this implementation is functional, but will mean the scheduler cannot
/// interrupt non-yielding processes.
impl SchedulerTimer for () {
    fn reset(&self) {}

    fn start(&self, _: NonZeroU32) {}

    fn disarm(&self) {}

    fn arm(&self) {}

    fn get_remaining_us(&self) -> Option<NonZeroU32> {
        NonZeroU32::new(10000) // choose arbitrary large value
    }
}

/// Implementation of SchedulerTimer trait on top of a virtual alarm.
///
/// Currently, this implementation depends slightly on the virtual alarm
/// implementation in capsules -- namely it assumes that get_alarm will still
/// return the passed value even after the timer is disarmed. Thus this should
/// only be implemented with a virtual alarm. If a dedicated hardware timer is
/// available, it is more performant to implement the scheduler timer directly
/// for that hardware peripheral without the alarm abstraction in between.
///
/// This mostly handles conversions from wall time, the required inputs to the
/// trait, to ticks, which are used to track time for alarms.
pub struct VirtualSchedulerTimer<A: 'static + time::Alarm<'static>> {
    alarm: &'static A,
}

impl<A: 'static + time::Alarm<'static>> VirtualSchedulerTimer<A> {
    pub fn new(alarm: &'static A) -> Self {
        Self { alarm }
    }
}

impl<A: 'static + time::Alarm<'static>> SchedulerTimer for VirtualSchedulerTimer<A> {
    fn reset(&self) {
        let _ = self.alarm.disarm();
    }

    fn start(&self, us: NonZeroU32) {
        let tics = {
            // We need to convert from microseconds to native tics, which could overflow in 32-bit
            // arithmetic. So we convert to 64-bit. 64-bit division is an expensive subroutine, but
            // if `us` is a power of 10 the compiler will simplify it with the 1_000_000 divisor
            // instead.
            let us = us.get() as u64;
            let hertz = A::Frequency::frequency() as u64;

            (hertz * us / 1_000_000) as u32
        };

        let reference = self.alarm.now();
        self.alarm.set_alarm(reference, A::Ticks::from(tics));
    }

    fn arm(&self) {
        //self.alarm.arm();
    }

    fn disarm(&self) {
        //self.alarm.disarm();
    }

    fn get_remaining_us(&self) -> Option<NonZeroU32> {
        // We need to convert from native tics to us, multiplication could overflow in 32-bit
        // arithmetic. So we convert to 64-bit.

        let diff = self
            .alarm
            .get_alarm()
            .wrapping_sub(self.alarm.now())
            .into_u32() as u64;

        // If next alarm is more than one second away from now, alarm must have expired.
        // Use this formulation to protect against errors when now has passed alarm.
        // 1 second was chosen because it is significantly greater than the 400ms max value allowed
        // by start(), and requires no computational overhead (e.g. using 500ms would require
        // dividing the returned ticks by 2)
        // However, if the alarm frequency is slow enough relative to the cpu frequency, it is
        // possible this will be evaluated while now() == get_alarm(), so we special case that
        // result where the alarm has fired but the subtraction has not overflowed
        if diff >= A::Frequency::frequency() as u64 {
            None
        } else {
            let hertz = A::Frequency::frequency() as u64;
            NonZeroU32::new(((diff * 1_000_000) / hertz) as u32)
        }
    }
}