riot_rs_runqueue/
runqueue.rs

1use core::mem;
2
3use self::clist::CList;
4
5const USIZE_BITS: usize = mem::size_of::<usize>() * 8;
6
7pub type RunqueueId = u8;
8pub type ThreadId = u8;
9
10/// Runqueue for N_QUEUES, supporting N_THREADS total.
11///
12/// assumptions:
13/// - higher runqueue number means higher priority
14/// - runqueue numbers (corresponding priorities) are 0..N_QUEUES (exclusive)
15/// - runqueue numbers fit in usize bits (supporting max 32 priority levels)
16/// - pids range from 0..N_THREADS
17/// - N_THREADS is <255 (as u8 is used to store them, but 0xFF is used as
18///   special value)
19///
20///   The current implementation needs an usize for the bit cache,
21///   an [u8; N_QUEUES] array for the list tail indexes
22///   and an [u8; N_THREADS] for the list next indexes.
23pub struct RunQueue<const N_QUEUES: usize, const N_THREADS: usize> {
24    bitcache: usize,
25    queues: clist::CList<N_QUEUES, N_THREADS>,
26}
27
28impl<const N_QUEUES: usize, const N_THREADS: usize> RunQueue<{ N_QUEUES }, { N_THREADS }> {
29    pub const fn new() -> RunQueue<{ N_QUEUES }, { N_THREADS }> {
30        // unfortunately we cannot assert!() on N_QUEUES and N_THREADS,
31        // as panics in const fn's are not (yet) implemented.
32        RunQueue {
33            bitcache: 0,
34            queues: CList::new(),
35        }
36    }
37
38    /// add thread with pid n to runqueue number rq
39    pub fn add(&mut self, n: ThreadId, rq: RunqueueId) {
40        debug_assert!((n as usize) < N_THREADS);
41        debug_assert!((rq as usize) < N_QUEUES);
42        self.bitcache |= 1 << rq;
43        self.queues.push(n, rq);
44    }
45
46    /// remove thread with pid n from runqueue number rq
47    /// @note: this implementation fails if "n" is not the queue's head.
48    /// This is fine, RIOT-rs only ever calls del() for the current thread.
49    pub fn del(&mut self, n: ThreadId, rq: RunqueueId) {
50        debug_assert!((n as usize) < N_THREADS);
51        debug_assert!((rq as usize) < N_QUEUES);
52        let popped = self.queues.pop_head(rq);
53        //
54        assert_eq!(popped, Some(n as u8));
55        if self.queues.is_empty(rq) {
56            self.bitcache &= !(1 << rq);
57        }
58    }
59
60    fn ffs(val: usize) -> u32 {
61        USIZE_BITS as u32 - val.leading_zeros()
62    }
63
64    /// get pid that should run next
65    /// returns the next runnable thread of
66    /// the runqueue with the highest index
67    pub fn get_next(&self) -> Option<u8> {
68        let rq_ffs = Self::ffs(self.bitcache);
69        if rq_ffs > 0 {
70            let rq = (rq_ffs - 1) as RunqueueId;
71            self.queues.peek_head(rq)
72        } else {
73            None
74        }
75    }
76
77    /// advance runqueue number rq
78    /// (this is used to "yield" to another thread of *the same* priority)
79    pub fn advance(&mut self, rq: RunqueueId) {
80        debug_assert!((rq as usize) < N_QUEUES);
81        self.queues.advance(rq)
82    }
83}
84
85mod clist {
86    // this module implements an array of N_QUEUES circular linked lists over an
87    // array of size N_THREADS.
88    // the array is used for "next" pointers, so each integer value in the array
89    // corresponds to one element, which can only be in one of the lists.
90    use super::{RunqueueId, ThreadId};
91
92    #[derive(Debug, Copy, Clone)]
93    pub struct CList<const N_QUEUES: usize, const N_THREADS: usize> {
94        tail: [u8; N_QUEUES],
95        next_idxs: [u8; N_THREADS],
96    }
97
98    impl<const N_QUEUES: usize, const N_THREADS: usize> CList<N_QUEUES, N_THREADS> {
99        pub const fn new() -> Self {
100            // TODO: ensure N fits in u8
101            // assert!(N<255); is not allowed in const because it could panic
102            CList {
103                tail: [Self::sentinel(); N_QUEUES],
104                next_idxs: [Self::sentinel(); N_THREADS],
105            }
106        }
107
108        pub const fn sentinel() -> u8 {
109            0xFF
110        }
111
112        pub fn is_empty(&self, rq: RunqueueId) -> bool {
113            self.tail[rq as usize] == Self::sentinel()
114        }
115
116        pub fn push(&mut self, n: ThreadId, rq: RunqueueId) {
117            assert!(n < Self::sentinel());
118            if self.next_idxs[n as usize] == Self::sentinel() {
119                if self.tail[rq as usize] == Self::sentinel() {
120                    // rq is empty, link both tail and n.next to n
121                    self.tail[rq as usize] = n;
122                    self.next_idxs[n as usize] = n;
123                } else {
124                    // rq has an entry already, so
125                    // 1. n.next = old_tail.next ("first" in list)
126                    self.next_idxs[n as usize] = self.next_idxs[self.tail[rq as usize] as usize];
127                    // 2. old_tail.next = n
128                    self.next_idxs[self.tail[rq as usize] as usize] = n;
129                    // 3. tail = n
130                    self.tail[rq as usize] = n;
131                }
132            }
133        }
134
135        pub fn pop_head(&mut self, rq: RunqueueId) -> Option<u8> {
136            if self.tail[rq as usize] == Self::sentinel() {
137                // rq is empty, do nothing
138                None
139            } else {
140                let head = self.next_idxs[self.tail[rq as usize] as usize];
141                if head == self.tail[rq as usize] {
142                    // rq's tail bites itself, so there's only one entry.
143                    // so, clear tail.
144                    self.tail[rq as usize] = Self::sentinel();
145                    // rq is now empty
146                } else {
147                    // rq has multiple entries,
148                    // so set tail.next to head.next (second in list)
149                    self.next_idxs[self.tail[rq as usize] as usize] = self.next_idxs[head as usize];
150                }
151
152                // now clear head's next value
153                self.next_idxs[head as usize] = Self::sentinel();
154                Some(head)
155            }
156        }
157
158        pub fn peek_head(&self, rq: RunqueueId) -> Option<u8> {
159            if self.tail[rq as usize] == Self::sentinel() {
160                None
161            } else {
162                Some(self.next_idxs[self.tail[rq as usize] as usize])
163            }
164        }
165
166        pub fn advance(&mut self, rq: RunqueueId) {
167            if self.tail[rq as usize] != Self::sentinel() {
168                self.tail[rq as usize] = self.next_idxs[self.tail[rq as usize] as usize];
169            }
170        }
171    }
172
173    #[cfg(test)]
174    mod tests {
175        use super::*;
176
177        #[test]
178        fn test_clist_basic() {
179            let mut clist: CList<8, 32> = CList::new();
180            assert!(clist.is_empty(0));
181            clist.push(0, 0);
182            assert_eq!(clist.pop_head(0), Some(0));
183            assert_eq!(clist.pop_head(0), None);
184        }
185
186        #[test]
187        fn test_clist_push_already_in_list() {
188            let mut clist: CList<8, 32> = CList::new();
189            assert!(clist.is_empty(0));
190            clist.push(0, 0);
191            clist.push(0, 0);
192            assert_eq!(clist.pop_head(0), Some(0));
193            assert_eq!(clist.pop_head(0), None);
194            assert!(clist.is_empty(0));
195        }
196
197        #[test]
198        fn test_clist_push_two() {
199            let mut clist: CList<8, 32> = CList::new();
200            assert!(clist.is_empty(0));
201            clist.push(0, 0);
202            clist.push(1, 0);
203            assert_eq!(clist.pop_head(0), Some(0));
204            assert_eq!(clist.pop_head(0), Some(1));
205            assert_eq!(clist.pop_head(0), None);
206            assert!(clist.is_empty(0));
207        }
208
209        #[test]
210        fn test_clist_push_all() {
211            const N: usize = 255;
212            let mut clist: CList<8, N> = CList::new();
213            assert!(clist.is_empty(0));
214            for i in 0..(N - 1) {
215                println!("pushing {}", i);
216                clist.push(i as u8, 0);
217            }
218            for i in 0..(N - 1) {
219                println!("{}", i);
220                assert_eq!(clist.pop_head(0), Some(i as u8));
221            }
222            assert_eq!(clist.pop_head(0), None);
223            assert!(clist.is_empty(0));
224        }
225
226        #[test]
227        fn test_clist_advance() {
228            let mut clist: CList<8, 32> = CList::new();
229            assert!(clist.is_empty(0));
230            clist.push(0, 0);
231            clist.push(1, 0);
232            clist.advance(0);
233            assert_eq!(clist.pop_head(0), Some(1));
234            assert_eq!(clist.pop_head(0), Some(0));
235            assert_eq!(clist.pop_head(0), None);
236            assert!(clist.is_empty(0));
237        }
238
239        #[test]
240        fn test_clist_peek_head() {
241            let mut clist: CList<8, 32> = CList::new();
242            assert!(clist.is_empty(0));
243            clist.push(0, 0);
244            clist.push(1, 0);
245            assert_eq!(clist.peek_head(0), Some(0));
246            assert_eq!(clist.peek_head(0), Some(0));
247            assert_eq!(clist.pop_head(0), Some(0));
248            assert_eq!(clist.peek_head(0), Some(1));
249            assert_eq!(clist.pop_head(0), Some(1));
250            assert_eq!(clist.peek_head(0), None);
251            assert_eq!(clist.peek_head(0), None);
252            assert_eq!(clist.pop_head(0), None);
253            assert!(clist.is_empty(0));
254        }
255    }
256}
riot_rs_runqueue/runqueue.rs

riot_rs_runqueue/
runqueue.rs
