Bounded nonallocating task communication is needed.

Issue by sstewartgallus
Saturday Mar 08, 2014 at 19:02 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/12767

This issue was labelled with: in the Rust repository

For certain safety critical or memory constrained situations something
much like POSIX message queues is needed (an actual binding to them
might be needed if we move forward on work for full operating system
process isolation).

Requirements:

• No memory allocations (memory allocations can fail) in the normal
  use.
• Safety, in the event of a misbehaving or buggy task.
• Determinism for easy testability.

Possible solutions:

• A synchronous, bounded, one message at a time queue (this seems to
  be the traditional solution for embedded developers).
  • Because the queue is bounded all memory can be allocated ahead of
    time.
  • Because the queue is bounded a misbehaving or buggy task cannot
    flood the queue with messages and interfere with other
    tasks. However, a reader task can stop removing messages from the
    queue and so halt writer tasks. As well, one writer task can halt
    other writer tasks by flooding the queue with messages (but only
    if the queue is not fair). Also, a writer task can refuse to write
    messages and halt readers that wait on it. Note that to some
    degree hang check timers as heavily used in embedded development
    can help solve this problem.
  • Because the queue is one message at a time task behaviour is much
    more deterministic.
• A nonblocking, one message at a time queue
  • Like the previous queue type all memory can be allocated ahead of
    time.
  • Like the previous queue type a misbehaving or buggy task cannot
    interfere with other tasks. In addition, because the queue is
    nonblocking there are not the problems with buggy tasks stopping
    other tasks.
  • Because the queue is not synchronous there are determinism
    problems.

Two examples of C code that use this kind of feature (I can't use Rust
examples because the facility hasn't been written yet!):

• A game simulator loop:
  The simulator loop needs to wait for several different events such
  as timer ticks, shutdown events, controller events and gui
  availability for updating events so the ability to select among them
  is critical (an earlier version of the simulator that used a spawn a
  new thread update notification method was buggy and ugly). The
  simulator works best with a nonblocking, one element gui update
  queue because the gui updates overwrite the previous updates.
• A game gui loop:
  The gui loop needs to wait for several different events such as
  window events, update events and controllable writeable events. The
  gui does not block when the simulator lags.

Because the gui update queue is nonblocking a buggy gui can't cause
the simulator to halt. As well, the simulator can't cause the gui to
halt.

I'd appreciate better examples of code that needs this feature. These
samples are just part of my own personal project and not real world,
working examples by experienced professionals.

Additionally, we might wish to expose a priority feature like POSIX
message queues do. Personally, I feel this use case is best dealt with
by simply having multiple message queues but someone else might think
differently.

Prior work:

• Ada Rendezvous (note that the Ravenscar profile gives the
  feature significant and important limitations which we should consider using).
• POSIX style message queues (see The Open Group)
• SysV style message queues (see The Open Group)

A few people who might be interested in this issue: @alexcrichton @pcwalton

Start with the earlier discussion in Rust issue #12767, then review the linked game simulator and GUI C examples to understand the communication patterns. The issue does not name Rust files or tests, and done would require an agreed design and concrete acceptance criteria for bounded, nonallocating task communication.