#ring-buffer #data-structures #mpsc #data-stream #data-streaming #no-alloc #scrollback

no-std scroll-ring

An MPSC overwriting ring buffer tuned for character data scrollback

2 releases

0.1.2 Sep 13, 2024
0.1.1 Feb 10, 2023
0.1.0 Feb 10, 2023

#124 in No standard library

Download history 8/week @ 2024-06-13 53/week @ 2024-06-20 198/week @ 2024-06-27 348/week @ 2024-07-04 151/week @ 2024-07-11 24/week @ 2024-07-18 22/week @ 2024-07-25 150/week @ 2024-08-01 50/week @ 2024-08-08 166/week @ 2024-08-15 90/week @ 2024-08-22 244/week @ 2024-08-29 441/week @ 2024-09-05 671/week @ 2024-09-12 431/week @ 2024-09-19 291/week @ 2024-09-26

1,843 downloads per month
Used in 3 crates (2 directly)

MIT/Apache

24KB
286 lines

scroll-ring

Structures for MPSC text streaming

The goal of the data structure provided by this crate is to cater for the needs of stdout-style text streaming over a lossy network, which results in thee requirements:

  • store a byte data stream in a no-std/no-alloc buffer,
  • be multi-producer (so that threads or even signals/interrupts can write to it),
  • never block (calls may take O(n) time for the processed data, but even with much reading and writing it mustn't take significantly longer -- ideally constant-time, but given atomics are generally not constan-time, maybe "as fast as the atomics are"?),
  • not interleave contiguous writes,
  • not lose any writes (it's OK to admit overflows, but keep track of how many bytes overflew),
  • keep old data around for as long as possible until it is overwritten,
  • offer a reader a chance to get a reasonable chunk of data even when it's way too slow for the current writes (think taking a snapshot of data scolling by), and
  • overflow as little as possible.

Overflowing data may not even hit the buffer, for example when a slice larger than the buffer is written, or when (large amounts of) data is to be written while a read happens, or while a write from a slow process happens -- either way, the written bytes are counted, they're just not available for reading (just as they would have been if the reader were merely too slow).

This is the minimal implementation that solely on "overflow as little as possible" to get a waaaay easier implementation. Better options are:

  • A perfect implementation would have atomics everywhere, and as long as there are no reads (or no writes from threads with such low priority that higher priority writes wrap around before the low priority write is done memcpy'ing), there would be no overflow. That'd be ideal, but is really hard.

  • An intermediate implementation would allow parallel writes, but have a brief period of locking the administrative part of the data structure when operations start and stop. (Thus, overflows might happen merely because an interrupt triggers at an inopportune time).

    Both these versions would probably need a bitfield of valid bytes (or a list of busy writers), because due to variable thread priorities concurrent writes don't finish in the opposite order of being started.

  • What is currently provided is about the dumbest possible version. For the whole duration of reading or writing, the data structure stays locked, and any overflows are recorded into an atomic field next to the locked structure.

    The [ringbuf] data structures are used in single-threaded mode here; there is a multi-threaded mode that could go some way implementing the others.

License: MIT OR Apache-2.0

Dependencies

~1MB
~23K SLoC