Expand description
A fixed capacity Multiple-Producer Multiple-Consumer (MPMC) lock-free queue
NOTE: This module requires atomic CAS operations. On targets where they’re not natively available,
they are emulated by the portable-atomic
crate.
§Example
This queue can be constructed in “const context”. Placing it in a static
variable lets all
contexts (interrupts / threads / main
) safely enqueue and dequeue items from it.
#![no_main]
#![no_std]
use panic_semihosting as _;
use cortex_m::{asm, peripheral::syst::SystClkSource};
use cortex_m_rt::{entry, exception};
use cortex_m_semihosting::hprintln;
use heapless::mpmc::Q2;
static Q: Q2<u8> = Q2::new();
#[entry]
fn main() -> ! {
if let Some(p) = cortex_m::Peripherals::take() {
let mut syst = p.SYST;
// configures the system timer to trigger a SysTick exception every second
syst.set_clock_source(SystClkSource::Core);
syst.set_reload(12_000_000);
syst.enable_counter();
syst.enable_interrupt();
}
loop {
if let Some(x) = Q.dequeue() {
hprintln!("{}", x).ok();
} else {
asm::wfi();
}
}
}
#[exception]
fn SysTick() {
static mut COUNT: u8 = 0;
Q.enqueue(*COUNT).ok();
*COUNT += 1;
}
§Benchmark
Measured on a ARM Cortex-M3 core running at 8 MHz and with zero Flash wait cycles
N | Q8::<u8>::enqueue().ok() (z ) | Q8::<u8>::dequeue() (z ) |
---|---|---|
0 | 34 | 35 |
1 | 52 | 53 |
2 | 69 | 71 |
N
denotes the number of interruptions. On Cortex-M, an interruption consists of an interrupt handler preempting the would-be atomic section of theenqueue
/dequeue
operation. Note that it does not matter if the higher priority handler uses the queue or not.- All execution times are in clock cycles. 1 clock cycle = 125 ns.
- Execution time is dependent of
mem::size_of::<T>()
. Both operations include onememcpy(T)
in their successful path. - The optimization level is indicated in parentheses.
- The numbers reported correspond to the successful path (i.e.
Some
is returned bydequeue
andOk
is returned byenqueue
).
§Portability
This module requires CAS atomic instructions which are not available on all architectures
(e.g. ARMv6-M (thumbv6m-none-eabi
) and MSP430 (msp430-none-elf
)). These atomics can be
emulated however with portable-atomic
, which is
enabled with the cas
feature and is enabled by default for thumbv6m-none-eabi
and riscv32
targets.
§References
This is an implementation of Dmitry Vyukov’s “Bounded MPMC queue” minus the cache padding.
Structs§
- MPMC queue with a capacity for N elements N must be a power of 2 The max value of N is u8::MAX - 1 if
mpmc_large
feature is not enabled.
Type Aliases§
- MPMC queue with a capability for 2 elements.
- MPMC queue with a capability for 4 elements.
- MPMC queue with a capability for 8 elements.
- MPMC queue with a capability for 16 elements.
- MPMC queue with a capability for 32 elements.
- MPMC queue with a capability for 64 elements.