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}