[RFC] Restartable sequences

[jmgao]

Summary

Add functionality similar to Linux's restartable sequences, which allows for the running of code sequences atomically, without disabling interrupt handlers.

Motivation

This allows the execution of side-effect-free code atomically without blocking interrupts. For example, a device could repeatedly poll its input pins in the idle task, and continuously commit a fresh, but consistent, view of the state of its inputs to be read and used by other tasks.

Design

Add a per-core sequence number that's atomically incremented at the beginning of every interrupt handler, and run a given lambda until we have the same sequence number before and after.

The implementation should hopefully be fairly straight-forward, and will probably resemble something like the following:

struct RSeq<T, F: Fn() -> Result<T, ()>> {
  f: F,
}

impl<T: Copy, F: Fn() -> Result<T, ()>> RSeq<T, F> {
  fn new(f: F) -> RSeq<T, F> {
    RSeq {
      f
    }
  }

  /// Get the result of an atomically executed restartable sequence.
  fn run(self) -> Result<T, ()> {
    loop {
      let before: u32 = get_sequence_number();
      let value = (self.f)()?;
      let after: u32 = get_sequence_number();
      if before == after {
        return Ok(value);
      }
    }
  }

  /// Execute a restartable sequence and commit its result, atomically.
  fn commit<U>(self, g: impl Fn(T) -> U) -> Result<U, ()> {
    loop {
      let before: u32 = get_sequence_number();
      let value = (self.f)()?;

      let commit = interrupt::free(|| {
        let after: u32 = get_sequence_number();
        if before == after {
          Some(g(value))
        } else {
          None
        }
      });

      if let Some(result) = commit {
        return Ok(result);
      }
    }
  }
}

Example

(handwavey strawman)

static mut INPUT_VALUE: AtomicUsize = AtomicBool::new(0);
static mut BUTTON0_PIN: Option<gpio::gpioa::PA0<gpio::Input<gpio::PullUp>>> = None;
static mut BUTTON1_PIN: Option<gpio::gpioa::PA1<gpio::Input<gpio::PullUp>>> = None;
static mut BUTTON2_PIN: Option<gpio::gpioa::PA2<gpio::Input<gpio::PullUp>>> = None;
static mut BUTTON3_PIN: Option<gpio::gpioa::PA3<gpio::Input<gpio::PullUp>>> = None;

#[app(device = stm32f1xx_hal::stm32)]
const APP: () = {
  #[init]
  fn init() {
    let mut gpioa = device.GPIOA.split(&mut rcc.apb2);

    unsafe {
      BUTTON0_PIN = Some(gpioa.pa0.into_pull_up_input(&mut gpioa.crl))
      BUTTON1_PIN = Some(gpioa.pa1.into_pull_up_input(&mut gpioa.crl))
      BUTTON2_PIN = Some(gpioa.pa2.into_pull_up_input(&mut gpioa.crl))
      BUTTON3_PIN = Some(gpioa.pa3.into_pull_up_input(&mut gpioa.crl))
    };
  }

  #[interrupt]
  fn USB_HP_CXN_TX() {
    // Send the inputs across USB.
  }

  #[idle]
  fn idle() -> ! {
    loop {
      RSeq::new(|| {
        unsafe {
          Ok((
            BUTTON0_PIN.as_ref().unwrap().is_low(),
            BUTTON1_PIN.as_ref().unwrap().is_low(),
            BUTTON2_PIN.as_ref().unwrap().is_low(),
            BUTTON3_PIN.as_ref().unwrap().is_low(),
          ))
        }
      }).commit(|(b0, b1, b2, b3)| {
        unsafe {
          INPUT_VALUE.store(convert_to_bits(b0, b1, b2, b3));
        }
      });
    }
  }
};

Unresolved questions

What should the return type of a restartable sequence be?

Three obvious options:

• T
• Option<T> (or Result<T, ()>
  • +: lets the sequence bail out in commit without taking a critical section
• Result<T, E>
  • +: lets the user return an error while bailing out in commit without taking a critical section
  • +: maybe lets the compiler generate the better code if the error type is !?
  • -: breaks type inference?

What do we do if we can never finish?

If there's too much work in the restartable sequence relative to the frequency of interrupts, we might never actually commit, and it probably won't be super obvious what's happening. Should we have a cap (user specified? hard-coded assumption?) on the number of retries we attempt before we assume that we're never going to succeed, so that we can return failure instead of just silently doing nothing but generating heat?

Is it possible to get rid of the horrible unsafes?

Shared access to resources (#129) might help?

[perlindgren]

Hi

Is this not a special case to determine (for some reason) that a code block has executed without preemptions? Or in a more general setting, atomic implies that the number of preemptions the code has been exposed to is 0.

This is not currently a notion of RTFM (but can be encoded by hand if so wished by manually inserting some entry code in each handler similarly to your suggestion). Alternatively one could think of exploiting the underlying debugging features (not sure exactly how, but I think there are probing counters for interrupts). If this is to be a feature of RTFM either the OH should be 0 when not used, or explicitly opted in. It would require some changes to RTFM app analysis and code generation.

Regarding the implementation:
What you implement is some sort of double buffering for a consistent view. This can likely NOT be implemented in safe Rust, but can be useful here and in other scenarios. I suggest looking at the lock free implementations of SPSC/MPSC in heapless, perhaps double buffer could go there. (Idea is to access the double buffered state through an atomically updated reference).

Best regards
Per

[jmgao]

Is this not a special case to determine (for some reason) that a code block has executed without preemptions? Or in a more general setting, atomic implies that the number of preemptions the code has been exposed to is 0.

Correct.

This is not currently a notion of RTFM (but can be encoded by hand if so wished by manually inserting some entry code in each handler similarly to your suggestion).

I might be mistaken, but it seems like you can't actually add any code to handlers used for software tasks. (Instead of supporting this directly, would adding something more general to allow this be preferred instead? Maybe something like #[interrupt_{prologue, epilogue}]? Or something less general, like generating and exposing an interrupt sequence number?)

Alternatively one could think of exploiting the underlying debugging features (not sure exactly how, but I think there are probing counters for interrupts).

I searched for a bit but couldn't find one for the cortex-m3, at least.

If this is to be a feature of RTFM either the OH should be 0 when not used, or explicitly opted in. It would require some changes to RTFM app analysis and code generation.

Gating it behind a feature seems like the easiest option for this.

What you implement is some sort of double buffering for a consistent view. This can likely NOT be implemented in safe Rust, but can be useful here and in other scenarios. I suggest looking at the lock free implementations of SPSC/MPSC in heapless, perhaps double buffer could go there. (Idea is to access the double buffered state through an atomically updated reference).

Sure, a better implementation could commit with a double (or triple) buffer (and avoid blocking interrupts entirely), but that's up to the user. A double/triple buffer allows you to publish a consistent view, this proposal allows you to generate the consistent view that you're publishing to your buffer.

[perlindgren]

Any further thoughts on this?