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

cu29_runtime/
copperlist.rs
