cu29_runtime/
copperlist.rs

1//! CopperList is the main data structure used by Copper to communicate between tasks.
2//! It is a queue that can be used to store preallocated messages between tasks in memory order.
3#[cfg(not(feature = "std"))]
4extern crate alloc;
5
6use alloc::alloc::{alloc_zeroed, handle_alloc_error};
7use alloc::boxed::Box;
8use alloc::vec::Vec;
9use core::alloc::Layout;
10
11use bincode::{Decode, Encode};
12use core::fmt;
13
14use core::fmt::Display;
15use core::iter::{Chain, Rev};
16use core::slice::{Iter as SliceIter, IterMut as SliceIterMut};
17use cu29_traits::{CopperListTuple, ErasedCuStampedData, ErasedCuStampedDataSet};
18use serde_derive::{Deserialize, Serialize};
19
20const MAX_TASKS: usize = 512;
21
22/// Not implemented yet.
23/// This mask will be used to for example filter out necessary regions of a copper list between remote systems.
24#[derive(Debug, Encode, Decode, PartialEq, Clone, Copy)]
25pub struct CopperLiskMask {
26    #[allow(dead_code)]
27    mask: [u128; MAX_TASKS / 128 + 1],
28}
29
30/// Those are the possible states along the lifetime of a CopperList.
31#[derive(Debug, Encode, Decode, Serialize, Deserialize, PartialEq, Copy, Clone)]
32pub enum CopperListState {
33    Free,
34    Initialized,
35    Processing,
36    DoneProcessing,
37    BeingSerialized,
38}
39
40impl Display for CopperListState {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        match self {
43            CopperListState::Free => write!(f, "Free"),
44            CopperListState::Initialized => write!(f, "Initialized"),
45            CopperListState::Processing => write!(f, "Processing"),
46            CopperListState::DoneProcessing => write!(f, "DoneProcessing"),
47            CopperListState::BeingSerialized => write!(f, "BeingSerialized"),
48        }
49    }
50}
51
52#[derive(Debug, Encode, Decode, Serialize, Deserialize)]
53pub struct CopperList<P: CopperListTuple> {
54    pub id: u32,
55    state: CopperListState,
56    pub msgs: P, // This is generated from the runtime.
57}
58
59impl<P: CopperListTuple> Default for CopperList<P> {
60    fn default() -> Self {
61        CopperList {
62            id: 0,
63            state: CopperListState::Free,
64            msgs: P::default(),
65        }
66    }
67}
68
69impl<P: CopperListTuple> CopperList<P> {
70    // This is not the usual way to create a CopperList, this is just for testing.
71    pub fn new(id: u32, msgs: P) -> Self {
72        CopperList {
73            id,
74            state: CopperListState::Initialized,
75            msgs,
76        }
77    }
78
79    pub fn change_state(&mut self, new_state: CopperListState) {
80        self.state = new_state; // TODO: probably wise here to enforce a state machine.
81    }
82
83    pub fn get_state(&self) -> CopperListState {
84        self.state
85    }
86}
87
88impl<P: CopperListTuple> ErasedCuStampedDataSet for CopperList<P> {
89    fn cumsgs(&self) -> Vec<&dyn ErasedCuStampedData> {
90        self.msgs.cumsgs()
91    }
92}
93
94/// This structure maintains the entire memory needed by Copper for one loop for the inter tasks communication within a process.
95/// P or Payload is typically a Tuple of various types of messages that are exchanged between tasks.
96/// N is the maximum number of in flight Copper List the runtime can support.
97pub struct CuListsManager<P: CopperListTuple, const N: usize> {
98    data: Box<[CopperList<P>; N]>,
99    length: usize,
100    insertion_index: usize,
101    current_cl_id: u32,
102}
103
104impl<P: CopperListTuple + fmt::Debug, const N: usize> fmt::Debug for CuListsManager<P, N> {
105    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
106        f.debug_struct("CuListsManager")
107            .field("data", &self.data)
108            .field("length", &self.length)
109            .field("insertion_index", &self.insertion_index)
110            // Do not include on_drop field
111            .finish()
112    }
113}
114
115pub type Iter<'a, T> = Chain<Rev<SliceIter<'a, T>>, Rev<SliceIter<'a, T>>>;
116pub type IterMut<'a, T> = Chain<Rev<SliceIterMut<'a, T>>, Rev<SliceIterMut<'a, T>>>;
117pub type AscIter<'a, T> = Chain<SliceIter<'a, T>, SliceIter<'a, T>>;
118pub type AscIterMut<'a, T> = Chain<SliceIterMut<'a, T>, SliceIterMut<'a, T>>;
119
120/// Initializes fields that cannot be zeroed after allocating a zeroed
121/// [`CopperList`].
122pub trait CuListZeroedInit: CopperListTuple {
123    /// Fixes up a zero-initialized copper list so that all internal fields are
124    /// in a valid state.
125    fn init_zeroed(&mut self);
126}
127
128impl<P: CopperListTuple + CuListZeroedInit, const N: usize> Default for CuListsManager<P, N> {
129    fn default() -> Self {
130        Self::new()
131    }
132}
133
134impl<P: CopperListTuple, const N: usize> CuListsManager<P, N> {
135    pub fn new() -> Self
136    where
137        P: CuListZeroedInit,
138    {
139        // SAFETY: We allocate zeroed memory and immediately initialize required fields.
140        let data = unsafe {
141            let layout = Layout::new::<[CopperList<P>; N]>();
142            let ptr = alloc_zeroed(layout) as *mut [CopperList<P>; N];
143            if ptr.is_null() {
144                handle_alloc_error(layout);
145            }
146            Box::from_raw(ptr)
147        };
148        let mut manager = CuListsManager {
149            data,
150            length: 0,
151            insertion_index: 0,
152            current_cl_id: 0,
153        };
154
155        for cl in manager.data.iter_mut() {
156            cl.msgs.init_zeroed();
157        }
158
159        manager
160    }
161
162    /// Returns the current number of elements in the queue.
163    ///
164    #[inline]
165    pub fn len(&self) -> usize {
166        self.length
167    }
168
169    /// Returns `true` if the queue contains no elements.
170    ///
171    #[inline]
172    pub fn is_empty(&self) -> bool {
173        self.length == 0
174    }
175
176    /// Returns `true` if the queue is full.
177    ///
178    #[inline]
179    pub fn is_full(&self) -> bool {
180        N == self.len()
181    }
182
183    /// Clears the queue.
184    ///
185    #[inline]
186    pub fn clear(&mut self) {
187        self.insertion_index = 0;
188        self.length = 0;
189    }
190
191    #[inline]
192    pub fn create(&mut self) -> Option<&mut CopperList<P>> {
193        if self.is_full() {
194            return None;
195        }
196        let result = &mut self.data[self.insertion_index];
197        self.insertion_index = (self.insertion_index + 1) % N;
198        self.length += 1;
199
200        // We assign a unique id to each CopperList to be able to track them across their lifetime.
201        result.id = self.current_cl_id;
202        self.current_cl_id += 1;
203
204        Some(result)
205    }
206
207    /// Peeks at the last element in the queue.
208    #[inline]
209    pub fn peek(&self) -> Option<&CopperList<P>> {
210        if self.length == 0 {
211            return None;
212        }
213        let index = if self.insertion_index == 0 {
214            N - 1
215        } else {
216            self.insertion_index - 1
217        };
218        Some(&self.data[index])
219    }
220
221    #[inline]
222    #[allow(dead_code)]
223    fn drop_last(&mut self) {
224        if self.length == 0 {
225            return;
226        }
227        if self.insertion_index == 0 {
228            self.insertion_index = N - 1;
229        } else {
230            self.insertion_index -= 1;
231        }
232        self.length -= 1;
233    }
234
235    #[inline]
236    pub fn pop(&mut self) -> Option<&mut CopperList<P>> {
237        if self.length == 0 {
238            return None;
239        }
240        if self.insertion_index == 0 {
241            self.insertion_index = N - 1;
242        } else {
243            self.insertion_index -= 1;
244        }
245        self.length -= 1;
246        Some(&mut self.data[self.insertion_index])
247    }
248
249    /// Returns an iterator over the queue's contents.
250    ///
251    /// The iterator goes from the most recently pushed items to the oldest ones.
252    ///
253    #[inline]
254    pub fn iter(&self) -> Iter<'_, CopperList<P>> {
255        let (a, b) = self.data[0..self.length].split_at(self.insertion_index);
256        a.iter().rev().chain(b.iter().rev())
257    }
258
259    /// Returns a mutable iterator over the queue's contents.
260    ///
261    /// The iterator goes from the most recently pushed items to the oldest ones.
262    ///
263    #[inline]
264    pub fn iter_mut(&mut self) -> IterMut<'_, CopperList<P>> {
265        let (a, b) = self.data.split_at_mut(self.insertion_index);
266        a.iter_mut().rev().chain(b.iter_mut().rev())
267    }
268
269    /// Returns an ascending iterator over the queue's contents.
270    ///
271    /// The iterator goes from the least recently pushed items to the newest ones.
272    ///
273    #[inline]
274    pub fn asc_iter(&self) -> AscIter<'_, CopperList<P>> {
275        let (a, b) = self.data.split_at(self.insertion_index);
276        b.iter().chain(a.iter())
277    }
278
279    /// Returns a mutable ascending iterator over the queue's contents.
280    ///
281    /// The iterator goes from the least recently pushed items to the newest ones.
282    ///
283    #[inline]
284    pub fn asc_iter_mut(&mut self) -> AscIterMut<'_, CopperList<P>> {
285        let (a, b) = self.data.split_at_mut(self.insertion_index);
286        b.iter_mut().chain(a.iter_mut())
287    }
288}
289
290#[cfg(test)]
291mod tests {
292    use super::*;
293    use cu29_traits::{ErasedCuStampedData, ErasedCuStampedDataSet, MatchingTasks};
294    use serde::{Deserialize, Serialize, Serializer};
295
296    #[derive(Debug, Encode, Decode, PartialEq, Clone, Copy, Serialize, Deserialize, Default)]
297    struct CuStampedDataSet(i32);
298
299    impl ErasedCuStampedDataSet for CuStampedDataSet {
300        fn cumsgs(&self) -> Vec<&dyn ErasedCuStampedData> {
301            Vec::new()
302        }
303    }
304
305    impl MatchingTasks for CuStampedDataSet {
306        fn get_all_task_ids() -> &'static [&'static str] {
307            &[]
308        }
309    }
310
311    impl CuListZeroedInit for CuStampedDataSet {
312        fn init_zeroed(&mut self) {}
313    }
314
315    #[test]
316    fn empty_queue() {
317        let q = CuListsManager::<CuStampedDataSet, 5>::new();
318
319        assert!(q.is_empty());
320        assert!(q.iter().next().is_none());
321    }
322
323    #[test]
324    fn partially_full_queue() {
325        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
326        q.create().unwrap().msgs.0 = 1;
327        q.create().unwrap().msgs.0 = 2;
328        q.create().unwrap().msgs.0 = 3;
329
330        assert!(!q.is_empty());
331        assert_eq!(q.len(), 3);
332
333        let res: Vec<i32> = q.iter().map(|x| x.msgs.0).collect();
334        assert_eq!(res, [3, 2, 1]);
335    }
336
337    #[test]
338    fn full_queue() {
339        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
340        q.create().unwrap().msgs.0 = 1;
341        q.create().unwrap().msgs.0 = 2;
342        q.create().unwrap().msgs.0 = 3;
343        q.create().unwrap().msgs.0 = 4;
344        q.create().unwrap().msgs.0 = 5;
345        assert_eq!(q.len(), 5);
346
347        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
348        assert_eq!(res, [5, 4, 3, 2, 1]);
349    }
350
351    #[test]
352    fn over_full_queue() {
353        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
354        q.create().unwrap().msgs.0 = 1;
355        q.create().unwrap().msgs.0 = 2;
356        q.create().unwrap().msgs.0 = 3;
357        q.create().unwrap().msgs.0 = 4;
358        q.create().unwrap().msgs.0 = 5;
359        assert!(q.create().is_none());
360        assert_eq!(q.len(), 5);
361
362        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
363        assert_eq!(res, [5, 4, 3, 2, 1]);
364    }
365
366    #[test]
367    fn clear() {
368        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
369        q.create().unwrap().msgs.0 = 1;
370        q.create().unwrap().msgs.0 = 2;
371        q.create().unwrap().msgs.0 = 3;
372        q.create().unwrap().msgs.0 = 4;
373        q.create().unwrap().msgs.0 = 5;
374        assert!(q.create().is_none());
375        assert_eq!(q.len(), 5);
376
377        q.clear();
378
379        assert_eq!(q.len(), 0);
380        assert!(q.iter().next().is_none());
381
382        q.create().unwrap().msgs.0 = 1;
383        q.create().unwrap().msgs.0 = 2;
384        q.create().unwrap().msgs.0 = 3;
385
386        assert_eq!(q.len(), 3);
387
388        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
389        assert_eq!(res, [3, 2, 1]);
390    }
391
392    #[test]
393    fn mutable_iterator() {
394        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
395        q.create().unwrap().msgs.0 = 1;
396        q.create().unwrap().msgs.0 = 2;
397        q.create().unwrap().msgs.0 = 3;
398        q.create().unwrap().msgs.0 = 4;
399        q.create().unwrap().msgs.0 = 5;
400
401        for x in q.iter_mut() {
402            x.msgs.0 *= 2;
403        }
404
405        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
406        assert_eq!(res, [10, 8, 6, 4, 2]);
407    }
408
409    #[test]
410    fn test_drop_last() {
411        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
412        q.create().unwrap().msgs.0 = 1;
413        q.create().unwrap().msgs.0 = 2;
414        q.create().unwrap().msgs.0 = 3;
415        q.create().unwrap().msgs.0 = 4;
416        q.create().unwrap().msgs.0 = 5;
417        assert_eq!(q.len(), 5);
418
419        q.drop_last();
420        assert_eq!(q.len(), 4);
421
422        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
423        assert_eq!(res, [4, 3, 2, 1]);
424    }
425
426    #[test]
427    fn test_pop() {
428        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
429        q.create().unwrap().msgs.0 = 1;
430        q.create().unwrap().msgs.0 = 2;
431        q.create().unwrap().msgs.0 = 3;
432        q.create().unwrap().msgs.0 = 4;
433        q.create().unwrap().msgs.0 = 5;
434        assert_eq!(q.len(), 5);
435
436        let last = q.pop().unwrap();
437        assert_eq!(last.msgs.0, 5);
438        assert_eq!(q.len(), 4);
439
440        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
441        assert_eq!(res, [4, 3, 2, 1]);
442    }
443
444    #[test]
445    fn test_peek() {
446        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
447        q.create().unwrap().msgs.0 = 1;
448        q.create().unwrap().msgs.0 = 2;
449        q.create().unwrap().msgs.0 = 3;
450        q.create().unwrap().msgs.0 = 4;
451        q.create().unwrap().msgs.0 = 5;
452        assert_eq!(q.len(), 5);
453
454        let last = q.peek().unwrap();
455        assert_eq!(last.msgs.0, 5);
456        assert_eq!(q.len(), 5);
457
458        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
459        assert_eq!(res, [5, 4, 3, 2, 1]);
460    }
461
462    #[derive(Decode, Encode, Debug, PartialEq, Clone, Copy)]
463    struct TestStruct {
464        content: [u8; 10_000_000],
465    }
466
467    impl Default for TestStruct {
468        fn default() -> Self {
469            TestStruct {
470                content: [0; 10_000_000],
471            }
472        }
473    }
474
475    impl ErasedCuStampedDataSet for TestStruct {
476        fn cumsgs(&self) -> Vec<&dyn ErasedCuStampedData> {
477            Vec::new()
478        }
479    }
480
481    impl Serialize for TestStruct {
482        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
483        where
484            S: Serializer,
485        {
486            serializer.serialize_i8(0)
487        }
488    }
489
490    impl MatchingTasks for TestStruct {
491        fn get_all_task_ids() -> &'static [&'static str] {
492            &[]
493        }
494    }
495
496    impl CuListZeroedInit for TestStruct {
497        fn init_zeroed(&mut self) {}
498    }
499
500    #[test]
501    fn be_sure_we_wont_stackoverflow_at_init() {
502        let _ = CuListsManager::<TestStruct, 3>::new();
503    }
504}
cu29_runtime/copperlist.rs

cu29_runtime/
copperlist.rs
