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: u64,
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: u64, 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: u64,
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    /// Returns the next copper-list id that will be assigned by [`create`](Self::create).
208    #[inline]
209    pub fn next_cl_id(&self) -> u64 {
210        self.current_cl_id
211    }
212
213    /// Returns the most recently assigned copper-list id.
214    ///
215    /// Before the first call to [`create`](Self::create), this returns `0`.
216    #[inline]
217    pub fn last_cl_id(&self) -> u64 {
218        self.current_cl_id.saturating_sub(1)
219    }
220
221    /// Peeks at the last element in the queue.
222    #[inline]
223    pub fn peek(&self) -> Option<&CopperList<P>> {
224        if self.length == 0 {
225            return None;
226        }
227        let index = if self.insertion_index == 0 {
228            N - 1
229        } else {
230            self.insertion_index - 1
231        };
232        Some(&self.data[index])
233    }
234
235    #[inline]
236    #[allow(dead_code)]
237    fn drop_last(&mut self) {
238        if self.length == 0 {
239            return;
240        }
241        if self.insertion_index == 0 {
242            self.insertion_index = N - 1;
243        } else {
244            self.insertion_index -= 1;
245        }
246        self.length -= 1;
247    }
248
249    #[inline]
250    pub fn pop(&mut self) -> Option<&mut CopperList<P>> {
251        if self.length == 0 {
252            return None;
253        }
254        if self.insertion_index == 0 {
255            self.insertion_index = N - 1;
256        } else {
257            self.insertion_index -= 1;
258        }
259        self.length -= 1;
260        Some(&mut self.data[self.insertion_index])
261    }
262
263    /// Returns an iterator over the queue's contents.
264    ///
265    /// The iterator goes from the most recently pushed items to the oldest ones.
266    ///
267    #[inline]
268    pub fn iter(&self) -> Iter<'_, CopperList<P>> {
269        let (a, b) = self.data[0..self.length].split_at(self.insertion_index);
270        a.iter().rev().chain(b.iter().rev())
271    }
272
273    /// Returns a mutable iterator over the queue's contents.
274    ///
275    /// The iterator goes from the most recently pushed items to the oldest ones.
276    ///
277    #[inline]
278    pub fn iter_mut(&mut self) -> IterMut<'_, CopperList<P>> {
279        let (a, b) = self.data.split_at_mut(self.insertion_index);
280        a.iter_mut().rev().chain(b.iter_mut().rev())
281    }
282
283    /// Returns an ascending iterator over the queue's contents.
284    ///
285    /// The iterator goes from the least recently pushed items to the newest ones.
286    ///
287    #[inline]
288    pub fn asc_iter(&self) -> AscIter<'_, CopperList<P>> {
289        let (a, b) = self.data.split_at(self.insertion_index);
290        b.iter().chain(a.iter())
291    }
292
293    /// Returns a mutable ascending iterator over the queue's contents.
294    ///
295    /// The iterator goes from the least recently pushed items to the newest ones.
296    ///
297    #[inline]
298    pub fn asc_iter_mut(&mut self) -> AscIterMut<'_, CopperList<P>> {
299        let (a, b) = self.data.split_at_mut(self.insertion_index);
300        b.iter_mut().chain(a.iter_mut())
301    }
302}
303
304#[cfg(test)]
305mod tests {
306    use super::*;
307    use cu29_traits::{ErasedCuStampedData, ErasedCuStampedDataSet, MatchingTasks};
308    use serde::{Deserialize, Serialize, Serializer};
309
310    #[derive(Debug, Encode, Decode, PartialEq, Clone, Copy, Serialize, Deserialize, Default)]
311    struct CuStampedDataSet(i32);
312
313    impl ErasedCuStampedDataSet for CuStampedDataSet {
314        fn cumsgs(&self) -> Vec<&dyn ErasedCuStampedData> {
315            Vec::new()
316        }
317    }
318
319    impl MatchingTasks for CuStampedDataSet {
320        fn get_all_task_ids() -> &'static [&'static str] {
321            &[]
322        }
323    }
324
325    impl CuListZeroedInit for CuStampedDataSet {
326        fn init_zeroed(&mut self) {}
327    }
328
329    #[test]
330    fn empty_queue() {
331        let q = CuListsManager::<CuStampedDataSet, 5>::new();
332
333        assert!(q.is_empty());
334        assert!(q.iter().next().is_none());
335    }
336
337    #[test]
338    fn partially_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
344        assert!(!q.is_empty());
345        assert_eq!(q.len(), 3);
346
347        let res: Vec<i32> = q.iter().map(|x| x.msgs.0).collect();
348        assert_eq!(res, [3, 2, 1]);
349    }
350
351    #[test]
352    fn 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_eq!(q.len(), 5);
360
361        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
362        assert_eq!(res, [5, 4, 3, 2, 1]);
363    }
364
365    #[test]
366    fn over_full_queue() {
367        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
368        q.create().unwrap().msgs.0 = 1;
369        q.create().unwrap().msgs.0 = 2;
370        q.create().unwrap().msgs.0 = 3;
371        q.create().unwrap().msgs.0 = 4;
372        q.create().unwrap().msgs.0 = 5;
373        assert!(q.create().is_none());
374        assert_eq!(q.len(), 5);
375
376        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
377        assert_eq!(res, [5, 4, 3, 2, 1]);
378    }
379
380    #[test]
381    fn clear() {
382        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
383        q.create().unwrap().msgs.0 = 1;
384        q.create().unwrap().msgs.0 = 2;
385        q.create().unwrap().msgs.0 = 3;
386        q.create().unwrap().msgs.0 = 4;
387        q.create().unwrap().msgs.0 = 5;
388        assert!(q.create().is_none());
389        assert_eq!(q.len(), 5);
390
391        q.clear();
392
393        assert_eq!(q.len(), 0);
394        assert!(q.iter().next().is_none());
395
396        q.create().unwrap().msgs.0 = 1;
397        q.create().unwrap().msgs.0 = 2;
398        q.create().unwrap().msgs.0 = 3;
399
400        assert_eq!(q.len(), 3);
401
402        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
403        assert_eq!(res, [3, 2, 1]);
404    }
405
406    #[test]
407    fn mutable_iterator() {
408        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
409        q.create().unwrap().msgs.0 = 1;
410        q.create().unwrap().msgs.0 = 2;
411        q.create().unwrap().msgs.0 = 3;
412        q.create().unwrap().msgs.0 = 4;
413        q.create().unwrap().msgs.0 = 5;
414
415        for x in q.iter_mut() {
416            x.msgs.0 *= 2;
417        }
418
419        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
420        assert_eq!(res, [10, 8, 6, 4, 2]);
421    }
422
423    #[test]
424    fn test_drop_last() {
425        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
426        q.create().unwrap().msgs.0 = 1;
427        q.create().unwrap().msgs.0 = 2;
428        q.create().unwrap().msgs.0 = 3;
429        q.create().unwrap().msgs.0 = 4;
430        q.create().unwrap().msgs.0 = 5;
431        assert_eq!(q.len(), 5);
432
433        q.drop_last();
434        assert_eq!(q.len(), 4);
435
436        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
437        assert_eq!(res, [4, 3, 2, 1]);
438    }
439
440    #[test]
441    fn test_pop() {
442        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
443        q.create().unwrap().msgs.0 = 1;
444        q.create().unwrap().msgs.0 = 2;
445        q.create().unwrap().msgs.0 = 3;
446        q.create().unwrap().msgs.0 = 4;
447        q.create().unwrap().msgs.0 = 5;
448        assert_eq!(q.len(), 5);
449
450        let last = q.pop().unwrap();
451        assert_eq!(last.msgs.0, 5);
452        assert_eq!(q.len(), 4);
453
454        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
455        assert_eq!(res, [4, 3, 2, 1]);
456    }
457
458    #[test]
459    fn test_peek() {
460        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
461        q.create().unwrap().msgs.0 = 1;
462        q.create().unwrap().msgs.0 = 2;
463        q.create().unwrap().msgs.0 = 3;
464        q.create().unwrap().msgs.0 = 4;
465        q.create().unwrap().msgs.0 = 5;
466        assert_eq!(q.len(), 5);
467
468        let last = q.peek().unwrap();
469        assert_eq!(last.msgs.0, 5);
470        assert_eq!(q.len(), 5);
471
472        let res: Vec<_> = q.iter().map(|x| x.msgs.0).collect();
473        assert_eq!(res, [5, 4, 3, 2, 1]);
474    }
475
476    #[test]
477    fn next_and_last_cl_id_track_assigned_ids() {
478        let mut q = CuListsManager::<CuStampedDataSet, 5>::new();
479
480        // Before first allocation, next id is 0 and last id saturates to 0.
481        assert_eq!(q.next_cl_id(), 0);
482        assert_eq!(q.last_cl_id(), 0);
483
484        let cl0 = q.create().unwrap();
485        assert_eq!(cl0.id, 0);
486        assert_eq!(q.next_cl_id(), 1);
487        assert_eq!(q.last_cl_id(), 0);
488
489        let cl1 = q.create().unwrap();
490        assert_eq!(cl1.id, 1);
491        assert_eq!(q.next_cl_id(), 2);
492        assert_eq!(q.last_cl_id(), 1);
493    }
494
495    #[derive(Decode, Encode, Debug, PartialEq, Clone, Copy)]
496    struct TestStruct {
497        content: [u8; 10_000_000],
498    }
499
500    impl Default for TestStruct {
501        fn default() -> Self {
502            TestStruct {
503                content: [0; 10_000_000],
504            }
505        }
506    }
507
508    impl ErasedCuStampedDataSet for TestStruct {
509        fn cumsgs(&self) -> Vec<&dyn ErasedCuStampedData> {
510            Vec::new()
511        }
512    }
513
514    impl Serialize for TestStruct {
515        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
516        where
517            S: Serializer,
518        {
519            serializer.serialize_i8(0)
520        }
521    }
522
523    impl MatchingTasks for TestStruct {
524        fn get_all_task_ids() -> &'static [&'static str] {
525            &[]
526        }
527    }
528
529    impl CuListZeroedInit for TestStruct {
530        fn init_zeroed(&mut self) {}
531    }
532
533    #[test]
534    fn be_sure_we_wont_stackoverflow_at_init() {
535        let _ = CuListsManager::<TestStruct, 3>::new();
536    }
537}
cu29_runtime/copperlist.rs

cu29_runtime/
copperlist.rs
