P: Safe Asynchronous Event-Driven Programming

Vivek Gupta, Ethan Jackson, Shaz Qadeer, Sriram Rajamani

MSR-TR-2012-116 |

We describe the design and implementation of P, a domain-specific language to write asynchronous event driven code. P allows the programmer to specify the system as a collection of interacting state machines, which communicate with each other using events. P unifies modeling and programming into one activity for the programmer. Not only can a P program be compiled into executable code, but it can also be verified using model checking. P allows the programmer to specify the environment, used to “close” the system during model checking, as nondeterministic ghost machines. Ghost machines are erased during compilation to executable code; a type system ensures that the erasure is semantics preserving.

The P language is carefully designed so that we can check if the systems being designed is responsive, i.e., it is able to handle every event in a timely manner. By default, a machine needs to handle every event that arrives in every state. The default safety checker looks for violations of this rule. Sometimes, handling every event at every state is impractical. The language provides a notion of deferred events where the programmer can annotate when she wants to delay processing an event. The language also provides default liveness checks that an event cannot be potentially deferred forever. Call transitions (which are like subroutines) are used to factor common event handling code, and allow programmers to write complicated state machines.

P was used to implement and verify the core of the USB device driver stack that ships with Microsoft Windows 8. The resulting driver is more reliable and performs better than its prior incarnation (which did not use P), and we have more confidence in the robustness of its design due to the language abstractions and verification provided by P.

P: Safe Asynchronous Event-Driven Programming

P: a domain specific language for writing asynchronous event-driven programs. This asynchronous language promotes a discipline of programming where deferrals need to be declared explicitly, and consequently leads to responsive systems. The main technical contribution of this work is an asynchronous model which forces each event in the queue to be handled as soon as the machine associated with the queue is scheduled, and has a chance to de-queue the event. The system's verifier systematically explores the state space of machines and ensures that there are no unhandled events. In certain circumstances, such as processing a high priority event, or processing a sequence of event exchanges during a transaction, some other lower priority events may have to be queued temporarily. P has features such as deferred events for a programmer to explicitly specify such deferrals.