[RFC] Prototype for new Upstart state machine

[Casey Dahlin]

Scott James Remnant wrote:
> On Thu, 2008-11-06 at 10:45 -0500, Casey Dahlin wrote:
>
>   
>> I've written a prototype for a service state machine which will 
>> hopefully behave more simply and cleanly than the present event-driven 
>> upstart. I'm posting it here for general comments. Its written in ruby 
>> and consists of the implementation itself and a test suite. You should 
>> find it fairly easy to poke it in irb if you're curious.
>>
>> git clone git://fedorapeople.org/~sadmac/upstate.git
>>
>>     
> For those of us who are ruby impaired, could you explain it? :)
>
> Scott
>   
Gladly.

The user defines several state classes. Each state class contains
* A rising edge action (optional)
* A falling edge action (optional)
* A series of dependencies
* A series of expected hold parameters, which are key-pattern pairs

A dependency contains
* A reference to a state class
* A series of parameter requirements, which are key-pattern pairs

For any state class there may be one or more states. A state consists of
* A reference to its state class
* Zero or more holds
* A series of dependency-state tuples, where the dependency is one of 
the dependencies outlined in the state's class, and the state is a state 
which satisfies that dependency.
* Parameters, which are key-value pairs, and consist wholly of all the 
parameters of the states in the dependency-state tuples, and any 
parameters of the hold which match the class's expected hold parameters

Holds come in 3 types: Dependency, User, and System
- System holds are always placed when an event occurs. Their parameters 
are the same as the event's parameters
- User holds are placed when a user has explicitly told upstart to do 
something. The parameters are defined by the user
- Dependency holds are placed when a state depends on something. Their 
parameters are identical to the parameters of the depending state.

Two states are considered equal if they have the same parameters. At any 
given time no two equal states may exist. Attempting to create a state 
which is equal to another, or to cause a state to become equal to 
another, will yield the pre-existing state.

A state is defined as "up" if it has at least one hold, and "down" 
otherwise. When a "down" state has a hold placed on it, it will run the 
rising edge action for its state class, passing to it all of its 
parameters. If there is a failure in the rising edge action, then the 
attempt to place the hold will fail and the state will remain down. The 
hold will also not be placed if each of the state's class's expected 
hold parameters. Finally, before a state comes "up" it must place a 
Dependency holds on all the states in its dependency-state tuple list. 
If any of those hold placements fail, the state remains down, and this 
hold placement fails. Hold placement should /never/ fail if a state is 
already up at time of placement.

A state can be forced down by user intervention or some system cases. 
Forcing a state down consists of iterating the list of holds, "clearing" 
each of them, and then discarding them from the state's list of holds. 
For System and User holds, clearing is a no-op. For Dependency holds, 
clearing consists of forcing the dependant state down. Whenever the last 
hold is removed from a state's list of dependencies, it runs its class's 
falling edge action if present (failure is reported as an error, and 
otherwise ignored), then removes any holds it placed on other states 
when coming up.

It should be noted that because two states are judged to be equal or not 
based on their parameters, and parameters are partially taken from the 
first hold placed on a state, a state coming up may in some cases cease 
to be equal to what it was previously, meaning that a downed version of 
its former self can spring up alongside it (and necessarily will, as we 
will see in a moment). A state can also become equal to another state 
when a hold is placed on it. This causes the state to disappear, and it 
is ensured that no rising-edge action takes place when this occurs. 
Finally, a state can become equal to another state when its holds are 
removed. Again, the state disappears in this case, but the falling-edge 
action is still executed. (Implementation note: high level procedural 
languages hate these behaviors).

When the system comes online, there are several state classes, but no 
states. At this point, and every time a state moves from up to down, or 
down to up, depsolving occurs. The procedure is as follows:
1) All states which are presently down cease to exist.
2) For each state class:
A) For each dependency, find all states which meet the dependency, put 
this into a "list of dependency solutions"
B) If any of the dependencies can't be solved, go to the next state class
C) Generate a list of all possible ways to choose exactly one item from 
each list of dependency solutions (aggregate cross product)
D) Find each member of the above for which each state therein is "rooted 
in" that member. A state is "rooted in" a list of states if any 
dependency which /can/ be met by a member of the list /is/, and if all 
of its dependencies are rooted in the same list.
E) For each result from D, attempt to create a new state with the 
current class and dependencies from the given list.

At the start of the program, there are no "up" states, so the only new 
down states which will be created are ones with no dependencies.

Now events:

An event consists of:
* A name
* A key-value list of parameters

Every state class has a series of key-(list of key-pattern) pairs which 
say what events it responds to. If an event occurs which a given state 
class responds to, any down states of that class have a system hold 
placed on them. Failure to place the hold is reported as an error and 
otherwise ignored. The system hold's parameters are taken from the event.

There is a special event called Epsilon or ε, which is automatically 
generated by the state machine at certain times. It has no parameters, 
and is defined as occuring "whenever it would cause something to 
happen." You can think of defining a state class as responding to ε as 
defining it to start automatically, and indeed this is how the 
configuration interface will expose it.

Hope that made things interesting.

--CJD