Module mpmc

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 the enqueue / 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 one memcpy(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 by dequeue and Ok is returned by enqueue).

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

• MpMcQueue
  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

• Q2
  MPMC queue with a capability for 2 elements.
• Q4
  MPMC queue with a capability for 4 elements.
• Q8
  MPMC queue with a capability for 8 elements.
• Q16
  MPMC queue with a capability for 16 elements.
• Q32
  MPMC queue with a capability for 32 elements.
• Q64
  MPMC queue with a capability for 64 elements.