Skip to main content

kernel/collections/
ring_buffer.rs

1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Implementation of a ring buffer.
6
7use crate::collections::queue;
8use core::mem::MaybeUninit;
9
10/// Queue implementation based on a contiguous buffer.
11///
12/// The buffer is assumed to be uninitialized when the [`RingBuffer`] is
13/// created. This can be safely created using uninitialized memory for the ring.
14pub struct RingBuffer<'a, T: Copy + 'a> {
15    /// Array of elements `T`. The buffer does not need to have initialized
16    /// elements `T`. The `RingBuffer` assumes that any element not tracked in
17    /// the ring based on head and tail are not initialized.
18    ring: &'a mut [MaybeUninit<T>],
19    head: usize,
20    tail: usize,
21}
22
23impl<'a, T: Copy> RingBuffer<'a, T> {
24    /// Create a [`RingBuffer`].
25    ///
26    /// The provided `ring` is assumed to be uninitialized and the ring starts
27    /// empty.
28    pub fn new(ring: &'a mut [MaybeUninit<T>]) -> RingBuffer<'a, T> {
29        RingBuffer {
30            head: 0,
31            tail: 0,
32            ring,
33        }
34    }
35
36    /// Returns the number of elements that can be enqueued until the ring buffer is full.
37    pub fn available_len(&self) -> usize {
38        // The maximum capacity of the queue is ring.len - 1, because head == tail for the empty
39        // queue.
40        self.ring.len().saturating_sub(1 + queue::Queue::len(self))
41    }
42
43    /// Returns up to 2 slices that together form the contents of the ring buffer.
44    ///
45    /// Returns:
46    /// - `(None, None)` if the buffer is empty.
47    /// - `(Some(slice), None)` if the head is before the tail (therefore all
48    ///   the contents is contiguous).
49    /// - `(Some(left), Some(right))` if the head is after the tail. In that
50    ///   case, the logical contents of the buffer is `[left, right].concat()`
51    ///   (although physically the "left" slice is stored after the "right"
52    ///   slice).
53    pub fn as_slices(&'a self) -> (Option<&'a [T]>, Option<&'a [T]>) {
54        let assume_init = |s: &[MaybeUninit<T>]| -> &[T] {
55            // SAFETY: Reinterprets &[MaybeUninit<T>] as &[T]. MaybeUninit<T> has the same layout as
56            // T, and every element in the returned slice falls within [head, tail) which has been
57            // written by enqueue/push, so reading those elements as T is valid.
58            unsafe { core::slice::from_raw_parts(s.as_ptr().cast::<T>(), s.len()) }
59        };
60
61        if self.head < self.tail {
62            (Some(assume_init(&self.ring[self.head..self.tail])), None)
63        } else if self.head > self.tail {
64            let (left, right) = self.ring.split_at(self.head);
65            (
66                Some(assume_init(right)),
67                if self.tail == 0 {
68                    None
69                } else {
70                    Some(assume_init(&left[..self.tail]))
71                },
72            )
73        } else {
74            (None, None)
75        }
76    }
77
78    /// Check if `index` into the internal `ring` contains a valid element
79    /// stored in the [`RingBuffer`].
80    fn is_valid(&self, index: usize) -> bool {
81        let capacity = self.ring.len();
82        let position_in_ring = (index + capacity - self.head) % capacity;
83
84        // Check if the position in the ring of `index` is not actually within
85        // the populated ring holding valid elements. If so, return true.
86        // Otherwise, return false.
87        position_in_ring < queue::Queue::len(self)
88    }
89
90    /// Get the element stored at `index` in the `ring` if there is a valid
91    /// element at that index.
92    fn get_internal(&self, index: usize) -> Option<T> {
93        // Check if the position in the ring of `index` is not actually within
94        // the populated ring holding valid elements. If so, this `get()` fails
95        // and we return `None`.
96        if !self.is_valid(index) {
97            None
98        } else {
99            let element = self.ring.get(index);
100            element.map(|e| {
101                // SAFETY: It is safe to read the element from this location in the ring and
102                // assume it is initialized because we verified that the index is
103                // within the populated elements of the ring. Our invariant is that
104                // any index with head and tail _must_ be initialized.
105                unsafe { e.assume_init() }
106            })
107        }
108    }
109
110    /// Get a reference to the element stored at `index` in the `ring` if there
111    /// is a valid element at that index.
112    fn get_internal_ref(&self, index: usize) -> Option<&T> {
113        // Check if the position in the ring of `index` is not actually within
114        // the populated ring holding valid elements. If so, this `get()` fails
115        // and we return `None`.
116        if !self.is_valid(index) {
117            None
118        } else {
119            let element = self.ring.get(index);
120            element.map(|e| {
121                // SAFETY: It is safe to read the element from this location in the ring and
122                // assume it is initialized because we verified that the index is
123                // within the populated elements of the ring. Our invariant is that
124                // any index with head and tail _must_ be initialized.
125                unsafe { e.assume_init_ref() }
126            })
127        }
128    }
129}
130
131impl<'a, T: Copy + Eq> RingBuffer<'a, T> {
132    /// Returns whether the specified value is contained in the ring buffer.
133    pub fn contains(&'a self, val: T) -> bool {
134        let (left, right) = self.as_slices();
135
136        if let Some(left) = left {
137            if left.contains(&val) {
138                return true;
139            }
140        }
141
142        if let Some(right) = right {
143            if right.contains(&val) {
144                return true;
145            }
146        }
147
148        false
149    }
150}
151
152impl<T: Copy> queue::Queue<T> for RingBuffer<'_, T> {
153    fn has_elements(&self) -> bool {
154        self.head != self.tail
155    }
156
157    fn is_full(&self) -> bool {
158        self.head == ((self.tail + 1) % self.ring.len())
159    }
160
161    fn len(&self) -> usize {
162        if self.tail > self.head {
163            self.tail - self.head
164        } else if self.tail < self.head {
165            (self.ring.len() - self.head) + self.tail
166        } else {
167            // head equals tail, length is zero
168            0
169        }
170    }
171
172    fn enqueue(&mut self, val: T) -> bool {
173        if self.is_full() {
174            // Incrementing tail will overwrite head
175            false
176        } else {
177            self.ring[self.tail].write(val);
178            self.tail = (self.tail + 1) % self.ring.len();
179            true
180        }
181    }
182
183    fn push(&mut self, val: T) -> Option<T> {
184        let result = if self.is_full() {
185            let old = self.get_internal(self.head);
186            self.head = (self.head + 1) % self.ring.len();
187            old
188        } else {
189            None
190        };
191
192        self.ring[self.tail].write(val);
193        self.tail = (self.tail + 1) % self.ring.len();
194        result
195    }
196
197    fn dequeue(&mut self) -> Option<T> {
198        if self.has_elements() {
199            let val = self.get_internal(self.head);
200            self.head = (self.head + 1) % self.ring.len();
201            val
202        } else {
203            None
204        }
205    }
206
207    /// Finds the first element for which the provided closure returns `true`.
208    ///
209    /// This walks the ring buffer and, upon finding a matching element, returns a
210    /// reference to it.
211    fn find_first_matching<F>(&mut self, f: F) -> Option<&T>
212    where
213        F: Fn(&T) -> bool,
214    {
215        let len = self.ring.len();
216        let mut slot = self.head;
217        while slot != self.tail {
218            if let Some(e) = self.get_internal_ref(slot) {
219                if f(e) {
220                    return Some(e);
221                }
222                slot = (slot + 1) % len;
223            }
224        }
225        None
226    }
227
228    /// Removes the first element for which the provided closure returns `true`.
229    ///
230    /// This walks the ring buffer and, upon finding a matching element, removes
231    /// it. It then shifts all subsequent elements forward (filling the hole
232    /// created by removing the element).
233    ///
234    /// If an element was removed, this function returns it as `Some(elem)`.
235    fn remove_first_matching<F>(&mut self, f: F) -> Option<T>
236    where
237        F: Fn(&T) -> bool,
238    {
239        let len = self.ring.len();
240        let mut slot = self.head;
241        while slot != self.tail {
242            if let Some(e) = self.get_internal_ref(slot) {
243                if f(e) {
244                    // This is the desired element, remove it and return it.
245                    let val = self.get_internal(slot);
246
247                    let mut next_slot = (slot + 1) % len;
248                    // Move everything past this element forward in the ring.
249                    while next_slot != self.tail {
250                        if let Some(to_move) = self.get_internal(next_slot) {
251                            self.ring[slot].write(to_move);
252                            slot = next_slot;
253                            next_slot = (next_slot + 1) % len;
254                        }
255                    }
256                    self.tail = slot;
257                    return val;
258                }
259                slot = (slot + 1) % len;
260            }
261        }
262        None
263    }
264
265    fn empty(&mut self) {
266        self.head = 0;
267        self.tail = 0;
268    }
269
270    fn retain<F>(&mut self, mut f: F)
271    where
272        F: FnMut(&T) -> bool,
273    {
274        let len = self.ring.len();
275        // Index over the elements before the retain operation.
276        let mut src = self.head;
277        // Index over the retained elements.
278        let mut dst = self.head;
279
280        while src != self.tail {
281            if let Some(e) = self.get_internal_ref(src) {
282                if f(e) {
283                    // When the predicate is true, move the current element to the
284                    // destination if needed, and increment the destination index.
285                    if src != dst {
286                        if let Some(to_move) = self.get_internal(src) {
287                            self.ring[dst].write(to_move);
288                        }
289                    }
290                    dst = (dst + 1) % len;
291                }
292                src = (src + 1) % len;
293            }
294        }
295
296        self.tail = dst;
297    }
298}
299
300#[cfg(test)]
301mod test {
302    use super::super::queue::Queue;
303    use super::RingBuffer;
304    use core::mem::MaybeUninit;
305
306    #[test]
307    fn test_enqueue_dequeue() {
308        const LEN: usize = 10;
309        let mut ring: [MaybeUninit<usize>; LEN] = [MaybeUninit::uninit(); LEN];
310        let mut buf = RingBuffer::new(&mut ring);
311
312        for _ in 0..2 * LEN {
313            assert!(buf.enqueue(42));
314            assert_eq!(buf.len(), 1);
315            assert!(buf.has_elements());
316
317            assert_eq!(buf.dequeue(), Some(42));
318            assert_eq!(buf.len(), 0);
319            assert!(!buf.has_elements());
320        }
321    }
322
323    #[test]
324    fn test_push() {
325        const LEN: usize = 10;
326        const MAX: usize = 100;
327        let mut ring: [MaybeUninit<usize>; LEN + 1] = [MaybeUninit::uninit(); LEN + 1];
328        let mut buf = RingBuffer::new(&mut ring);
329
330        for i in 0..LEN {
331            assert_eq!(buf.len(), i);
332            assert!(!buf.is_full());
333            assert_eq!(buf.push(i), None);
334            assert!(buf.has_elements());
335        }
336
337        for i in LEN..MAX {
338            assert!(buf.is_full());
339            assert_eq!(buf.push(i), Some(i - LEN));
340        }
341
342        for i in 0..LEN {
343            assert!(buf.has_elements());
344            assert_eq!(buf.len(), LEN - i);
345            assert_eq!(buf.dequeue(), Some(MAX - LEN + i));
346            assert!(!buf.is_full());
347        }
348
349        assert!(!buf.has_elements());
350    }
351
352    // Enqueue integers 1 <= n < len, checking that it succeeds and that the
353    // queue is full at the end.
354    // See std::iota in C++.
355    fn enqueue_iota(buf: &mut RingBuffer<usize>, len: usize) {
356        for i in 1..len {
357            assert!(!buf.is_full());
358            assert!(buf.enqueue(i));
359            assert!(buf.has_elements());
360            assert_eq!(buf.len(), i);
361        }
362
363        assert!(buf.is_full());
364        assert!(!buf.enqueue(0));
365        assert!(buf.has_elements());
366    }
367
368    // Dequeue all elements, expecting integers 1 <= n < len, checking that the
369    // queue is empty at the end.
370    // See std::iota in C++.
371    fn dequeue_iota(buf: &mut RingBuffer<usize>, len: usize) {
372        for i in 1..len {
373            assert!(buf.has_elements());
374            assert_eq!(buf.len(), len - i);
375            assert_eq!(buf.dequeue(), Some(i));
376            assert!(!buf.is_full());
377        }
378
379        assert!(!buf.has_elements());
380        assert_eq!(buf.len(), 0);
381    }
382
383    // Move the head by `count` elements, by enqueueing/dequeueing `count`
384    // times an element.
385    // This assumes an empty queue at the beginning, and yields an empty queue.
386    fn move_head(buf: &mut RingBuffer<usize>, count: usize) {
387        assert!(!buf.has_elements());
388        assert_eq!(buf.len(), 0);
389
390        for _ in 0..count {
391            assert!(buf.enqueue(0));
392            assert_eq!(buf.dequeue(), Some(0));
393        }
394
395        assert!(!buf.has_elements());
396        assert_eq!(buf.len(), 0);
397    }
398
399    #[test]
400    fn test_fill_once() {
401        const LEN: usize = 10;
402        let mut ring: [MaybeUninit<usize>; LEN] = [MaybeUninit::uninit(); LEN];
403        let mut buf = RingBuffer::new(&mut ring);
404
405        assert!(!buf.has_elements());
406        assert_eq!(buf.len(), 0);
407
408        enqueue_iota(&mut buf, LEN);
409        dequeue_iota(&mut buf, LEN);
410    }
411
412    #[test]
413    fn test_refill() {
414        const LEN: usize = 10;
415        let mut ring: [MaybeUninit<usize>; LEN] = [MaybeUninit::uninit(); LEN];
416        let mut buf = RingBuffer::new(&mut ring);
417
418        for _ in 0..10 {
419            enqueue_iota(&mut buf, LEN);
420            dequeue_iota(&mut buf, LEN);
421        }
422    }
423
424    #[test]
425    fn test_retain() {
426        const LEN: usize = 10;
427        let mut ring: [MaybeUninit<usize>; LEN] = [MaybeUninit::uninit(); LEN];
428        let mut buf = RingBuffer::new(&mut ring);
429
430        move_head(&mut buf, LEN - 2);
431        enqueue_iota(&mut buf, LEN);
432
433        buf.retain(|x| x % 2 == 1);
434        assert_eq!(buf.len(), LEN / 2);
435
436        assert_eq!(buf.dequeue(), Some(1));
437        assert_eq!(buf.dequeue(), Some(3));
438        assert_eq!(buf.dequeue(), Some(5));
439        assert_eq!(buf.dequeue(), Some(7));
440        assert_eq!(buf.dequeue(), Some(9));
441        assert_eq!(buf.dequeue(), None);
442    }
443}
444
445// ===== Flux code ========
446// Flux by-default checks:
447// 1. There are no division-by-zero errors
448// 2. There are no array bounds violations
449//
450// This spec is sufficient to prove the above two properties for RingBuffer,
451// as well as to prove some related, but stronger, well-formedness properties about RingBuffer
452// (e.g., indexes into the RingBuffer are always valid)
453//
454// If any of these properties could be violated either in the RingBuffer implementation or how it
455// is used anywhere in Tock, Flux will raise an error.
456#[cfg(feature = "flux")]
457mod flux_specs {
458    // Prelude: Here we provide some specifications for methods/types in the core library.
459    // This allows Flux to make use of these specs for proving useful things about RingBuffer.
460    // Generally, these specs are per-project---if we verified many modules in
461    // Tock, there would only be 1 centralized set of these specs for all of Tock.
462    #[flux_rs::extern_spec]
463    impl<T> [T] {
464        // Need to tell Flux what slice.len() does
465        #[flux_rs::sig(fn(&[T][@len]) -> usize[len])]
466        fn len(v: &[T]) -> usize;
467
468        // Need to tell Flux what slice.split_at_mut() does (for our tests)
469        #[flux_rs::sig(fn(&mut [T][@len], usize[@mid]) -> (&mut [T][mid], &mut [T][len - mid]))]
470        fn split_at_mut(v: &mut [T], mid: usize) -> (&mut [T], &mut [T]);
471    }
472
473    // Need to tell Flux what an Option<T> is:
474    // Here, we refine Option<T> with a bool, denoting whether it is `Some` or `None`
475    #[flux_rs::extern_spec]
476    #[flux_rs::refined_by(b: bool)]
477    enum Option<T> {
478        #[variant(Option<T>[false])]
479        None,
480        #[variant({T} -> Option<T>[true])]
481        Some(T),
482    }
483
484    // ======= RingBuffer spec ===========
485    #[allow(unused_imports)]
486    use crate::collections::list::ListIterator;
487    use crate::collections::queue::Queue;
488    use crate::collections::ring_buffer::RingBuffer;
489    use core::mem::MaybeUninit;
490
491    #[flux::specs {
492        // Specify well-formedness for RingBuffer<T>.
493        // A well-formed RingBuffer has an internal slice (`ring`) that can store at least 1 element, and
494        // a `head` and `tail` index, each of which must be less than the length of the internal slice.
495        // This ensures that all indices `ring[head]` and `ring[tail]` are valid.
496        #[refined_by(ring_len: int, hd: int, tl: int)]
497        struct RingBuffer<T> {
498            ring: {&mut [MaybeUninit<T>][ring_len] | ring_len > 0},
499            head: {usize[hd] | hd < ring_len},
500            tail: {usize[tl] | tl < ring_len},
501        }
502
503        impl RingBuffer<T> {
504            // A simple function-level spec for the RingBuffer<T> constructor.
505            //
506            // It has a precondition that the input slice is length > 1, so
507            // every time RingBuffer::new() is called (throughout Tock),
508            // Flux will ensure the slice passed in has length > 1.
509            //
510            // It also has a postcondition that the output RingBuffer has a head and tail of zero.
511            // Flux will check the implementation of `new` to ensure this is true.
512            //
513            // Design note: This contract has the strongest possible postcondition (head == 0 and tail == 0),
514            // but we could also make the postcondition something "weaker" like `result.head == result.tail`.
515            // Weaker vs stronger contracts is a design decision: it is easier to prove that a weak contract
516            // holds in the implementation, but it lets you prove less in the rest of Tock (e.g., if there was code
517            // that was only safe if head/tail was 0 after it called new, we could prove its safety only with the stronger contract).
518            fn new({&mut [MaybeUninit<T>][@ring_len] | ring_len > 0}) -> RingBuffer<T>[ring_len, 0, 0];
519        }
520
521        impl Queue<T> for RingBuffer<T> {
522            // These specs of the form: `(self: RingBuffer) ensures RingBuffer`
523            // are present to compensate for a current technical limitation of Flux,
524            // and should be gone in the near future.
525            fn empty(self: &mut RingBuffer<T>[@old])
526                ensures self: RingBuffer<T>;
527
528            fn enqueue(self: &mut RingBuffer<T>, val: T) -> bool
529                ensures self: RingBuffer<T>;
530
531            fn push(self: &mut RingBuffer<T>, val: T) -> Option<T>
532                ensures self: RingBuffer<T>;
533
534            fn dequeue(self: &mut RingBuffer<T>) -> Option<T>
535                ensures self: RingBuffer<T>;
536
537            fn remove_first_matching<F>(self: &mut RingBuffer<T>, _) -> Option<T>
538                ensures self: RingBuffer<T>;
539
540            fn retain<F>(self: &mut RingBuffer<T>, _)
541                ensures self: RingBuffer<T>;
542        }
543
544        impl core::iter::Iterator for ListIterator<T> {
545            fn next(self: &mut ListIterator<T>) -> Option<&T>
546                ensures self: ListIterator<T>;
547        }
548
549    }]
550    const _: () = ();
551
552    // ========= Flux tests ==============
553    // These functions will fail verification, and demonstrate the sorts of
554    // errors that our RingBuffer spec protects us against. Specifically:
555    // 1. Bad usage of the RingBuffer API that leads to kernel panics
556    // 2. Bad implementation of the RingBuffer API that leads to kernel panics
557
558    // 1. Flux will prevent Tock from using the RingBuffer API incorrectly,
559    // leading to panics
560    #[allow(dead_code)]
561    #[flux_rs::should_fail]
562    fn bad_split_into_ringbuffers<'a, T: Copy>(
563        buf: &'a mut [MaybeUninit<T>],
564        output_len: usize,
565    ) -> (RingBuffer<'a, T>, RingBuffer<'a, T>) {
566        // If `output_len` is `0` or `buf.len()`, then `output_ringbuf`
567        // or `internal_ringbuf` will have a length of `0`.
568        // This is bad, because if the `len` of a RingBuffer is `0`,
569        // then functions like `is_full` will panic.
570        let (output_buf, internal_buf) = buf.split_at_mut(output_len);
571        let output_ringbuf = RingBuffer::new(output_buf);
572        let internal_ringbuf = RingBuffer::new(internal_buf);
573        (output_ringbuf, internal_ringbuf)
574    }
575
576    // 2. Here, Flux will prevent RingBuffer implementations from panicing via
577    // out-of-bounds memory access or divide by zero.
578    #[allow(dead_code)]
579    #[flux_rs::should_fail]
580    #[flux_rs::spec(fn bad_enqueue(self: &mut RingBuffer<T>, val: T) -> bool
581                        ensures self: RingBuffer<T>)]
582    fn bad_enqueue<T: Copy>(rb: &mut RingBuffer<T>, val: T) -> bool {
583        // This function will not panic as long as rb.tail < rb.ring.len().
584        // However, for this to be true, every RingBuffer method needs to
585        // maintain this invariant (which is encoded in our RingBuffer spec).
586        // This function does not maintain this invariant, as it increases
587        // tail without checking ring.len(), and will throw an error.
588        if rb.is_full() {
589            false
590        } else {
591            rb.ring[rb.tail].write(val);
592            // CORRECT: rb.tail = (rb.tail + 1) % rb.ring.len();
593            rb.tail = rb.tail + 1;
594            true
595        }
596    }
597}