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

cu29_runtime/
copperlist.rs
