Documentation / Examples -- Queue Handling and Safety

[elcritch]

Great little project! I've been reading through it and think I'll be able to use for an upcoming project. Ideally I'd like to try adding some support for SCXML. Looks like almost everything needed is present aside from the variables in events.

However, I haven't been able to understand how the queue interacts with the events. Is it all supposed to be driven from the outside, like in the test_process function? In the simple example you just call process_event.

Ideally, I'd like to be able to have a state add an event to do a self-transitions or triggers. It looks like it'd be possible, but I'm not sure if it'd be safe/possible to enqueue an event from an entry/exit action.

[jonasblixt]

Thank you, I hope it will be useful for you.

I've deliberately not included variables in events because of the complexity it would add to the queuing, but I welcome a discussion/suggestions on how this could be done. I've just not found a way that I'm happy with yet.

It's possible to use uFSM without the queue, but with some limitations;

• Completion events will not work, so all transitions must have explicit triggers
• DO activities will not work, since these need to be de-coupled from the rest of the transition algorithm. A good example would be a DO activity that starts a thread and at some point later, when this thread finishes its work, it calls the completion handler that is passed as an argument to the DO activity start function.
• Triggering new events within any handlers called by uFSM

I think generally you would want to use the queue function but there are cases where it might not be needed, for example the test cases, as you have noted, the queue is not needed for some of them.

I wanted to allow for some flexibility with the queue to support different kind of locking mechanisms. The queue has a few optional event handlers, 'on_data', 'lock' and 'unlock'.

the dhcpclient example, although not complete, might be a good example to show how these can be used in a linux program. The lock/unlock tries to lock a mutex.

I imagined that in an embedded application the 'main loop' would try to de-queue an event and post it with the ufsm_process function and if there are no more events for processing it would run the 'WFI' instruction, stopping the CPU until the next interrupt.

In the embedded context, the lock/unlock would disable/enable global interrupts. That's why only the get function calls on these callbacks, I wanted a non blocking put-function that can be called from an interrupt context.

I think you should be able to do what you want in a safe way. Have a look at the dhcpclient -example.

Hope this helps!

[jonasblixt]

Actually thinking about this I need to make some adjustments to the queueing system. I think it could work for a scenario where there is one producer and one consumer, but with many thread or nested IRQ's it will probably break.

[elcritch]

Thanks! I like the elegant design of the system overall.

I'm having some difficulty understanding some of the semantics and mapping those into my embedded use case. The semantics of SCXML are still much more clear to me, though the XMI events are starting to make a bit of sense. The SCXML spec includes a lot more details on what data events need to have, etc but most concepts have a mapping.

I imagined that in an embedded application the 'main loop' would try to de-queue an event and post it with the ufsm_process function and if there are no more events for processing it would run the 'WFI' instruction, stopping the CPU until the next interrupt.

That is very similar to what I'd like to do. The main difference is that I want to have states which repeat until some condition is met (timeout, counting, or value based). A good example would be a sensor reading:

_$Sensor Reading State:_
1. Invoke SPI - xfer 0x01;  // start sensor reading  
2. Delay 20 µS
3. Invoke SPI - xfer 0x0; // read sensor value 
4. Store SPI Value in ReadingsBuffer

_$Sensor Readings Repeat:_ 
1. Set var count = 10
2. Cond count-- > 0 
       - true: Add event "$sensor reading"
       - false: Finish 

Most of this could be done readily with global variables and custom functions. Ideally for a fully user-configurable system, only base functions like SPI xfers and a general count functionality would be needed. Then if you flash an Arduino with a a general Sensor SM, one could read / write arbitrary sensors without needing to re-flash the device, just send a new SC description. The last part would require a system to create the states/transitions, but wouldn't be too tricky with MessagePack and some fiddly.

But can't think of how to do that without some sort of event data. I'll keep pondering that and post any ideas if they come up.

[elcritch]

I've been reviewing the uSCXML library, which emits a C code based SCXML state machine. It's mostly similar to uFSM but targets SCXML and has support for event data. It mainly uses void * pointers and allows the user defined functions to cast it as they see fit.

It'd be possible to tweak uFSM to be able to support user defined data models, at least for single-threaded uses by modifying a few things. First would be passing ufsm_machine* and ufsm_state* to entry, exit, and guards as is done for do_actions. Next adding _event_info and data pointers to the ufsm_machine struct. Lastly adding a "meta pointer" field to ufsm_state structs to support extra fields usable for scxml w/o cluttering up the structs.

That can all be done using global variables (at least single threaded) but would be much cleaner and stable if added to the state machine context. BTW, is there currently a way for do_actions to get the current event safely?

Between that and figuring out how to get a state to run to completion or add new events, I would be able to to add some sort of SCXML support! I'll try and add at least some sort of basic support for data contexts in the next week or so on my fork and see how it turns out...

[jonasblixt]

I think understand what you are trying to do. I do belive that this will quickly become quite complicated.

Getting pointers to various things through to the event handlers is probably easy, it's also easy to pass along which transition (and event) triggered entry into a specific state.

But... How would this work if you queue more than one event of the same type but with different data/parameters? Smells like you would need dynamic memory to do this and also the concurrency problem you have noted, which again could be solved by copying the data to the queue / dynamic memory. As far I have thought about this, to acomplish this, data would need to be copied to the queue buffer, this would be greatly simplified if there always is auxillary data on events and they always have the same size, but I think the benefit / added complexity equation is not favorable.

At the moment there is no safe way to extract the current state, this would not be so difficult to add using a locking mechanism for the transition algorithm. But I do wonder when you would need this, if you actually need current state information outside of the actual state machine, doesn't that imply that your are building logic and making descisions that could be done inside the machine?

Also, another note on the current state, this could be several states, sometimes because states can be nested in composit states and sometimes because of orthogonal regions in a composite state (or combinations). This can of course be extracted but could be a computationally intense operation if there are deeply nested regions.

A final comment on your SPI example, if we're taking micro seconds and sampling of sensors we likely have hard, real time, requirements to consider. This might work for the simplest state machines but scheduling would quickley become difficult, I think. Maybe another way would be to have the sampling part outside of the state machine and trigger an event in the state machine when enought samples are collected. I realize that this would not really work with what you are trying to do and I dont't really have any good suggestions on how to solve this.

By the way, what tools are you using to draw SCXML? so far I've only found / tested the SCXML -tool built into "QT desiger"

[elcritch]

Good comments! I went over and modified the code last night to pass the state / transition pointers. That was pretty easy. But handling the data and the events is where it got interesting... I'm mulling over how to handle data. Especially the benefit / complexity tradeoffs. I like the library because it's simple and flexible, adding complexity would be counter productive.

For locking the data, it looks like there's already on_data, lock, and unlock calls on the event queue. I'm thinking it might be simpler to have helper methods which enable a user to add an event data queue externally, but not complicate the internal system. The only other option I could think would be to have event's be structs with an enum type and a pointer to void *data. It'd be easy to extend the public api to support raw enum's or structs with enums and user defined data pointers.

Personally, I'm planning on using dynamic allocation external to the library for loading. If the main library can have "slots" for user data with void pointers, it'd let the end user decide if they want it all static (say a static queue) of dynamic, or pools, etc.

My current use case is building on the BeagleBone PRU's. They're single threaded and no interrupts. However, they're very deterministic which is what I'm going for, so having allocations during execution wouldn't work. I'd allocate any data upon loading the SM, but otherwise it should be static while running.

[elcritch]

About needing the state machine contexts external to the SM (in the guards, actions, etc).. I looked through it a bit more. the uSCXML library had them so I'd assumed they're necessary for some SCXML support.

I'm not so sure after looking through the SCXML spec (grepping for "must" is pretty handy). The only thing I could find was related to parallel (orthogonal in xmi (?)) states where a transition can be conditional based on the sibling states <transition cond="In('open')" target="idle"/> where the In('open') is a predicate for detecting the current state. It could potentially be handled internally to the SM.

  <parallel id="oven">
      ...
    <state id="engine">
        ...
        <state id="cooking">
          <transition cond="In('open')" target="idle"/>
          <!-- a 'time' event is seen once a second -->
          <transition event="time">
            <assign location="timer" expr="timer + 1"/>
          </transition>
        </state>
      </state>
    </state>

    <!-- this region tracks the microwave door state -->
    <state id="door">
      ...
      <state id="closed">
        <transition event="door.open" target="open"/>
      </state>
      ...
    </state>
  </parallel>

Though having a way to support something like <assign location="timer" expr="timer + 1"/> would be great, I'll probably start with just pre-set setters (like you do in the guard examples and setting flags). But even then the transition / entries / exits would only need access to the current data model.

Currently I'm writing SCXML just by hand. I find it pretty easy to read & write (at least for smaller examples). Much easier than the XMI format. If I need to move toward graphical editing I'd like to take up creating a vuejs or web-component renderer / editor. I'd experimented with the idea before, and it'd pretty easy using web-components to create components which map to SCXML elements with a simple prefix/name mapping. There's some pure JS libraries out there that handle SCXML as well.

[jonasblixt]

Storing <int, void*> pair's on the queue would be straight forward. That way it would also be possible to preserve the way the API is today. I'm thinking that we could add another queue_put -function.

The 'ufsm_queue_put(struct ufsm_queue q, uint32_t ev)' is kept as is but we add another function 'ufsm_queue_put2(struct ufsm_queue q, uint32_t ev, void *data)'. The original function would just add the event and NULL pointers.

I started a small branch to test some of this stuff: https://github.com/jonpe960/ufsm/tree/queuetest

One thing that occurred to me while doing this was how to manage the life cycle of the allocated event data. Let's imagine the following scenario:

1) Allocate some data and post event to queue

2a) Event could not be processed -> Callback to de-allocate data 2b) Transition reaches a pseudo state (Entry, Exit or connection point reference), here we likely would want to copy the data pointer over to the "other side". This makes it tricky to understand when the transition has completed and when it is OK to de-allocate data 2c) Reaches a state with a DO activity -> de-allocate callback when state completes or callback when state is exited while the DO acitivity is still running 2d) Reaches a history state, if the history state has a transition carrying data to another state this data would have to be preserved as well, even when the owning state is not active. De-allocation could only happen when the history state is not pointing to a state that does not expect any event data.

//Jonas

On Thu, Jun 14, 2018 at 12:14 AM Jaremy Creechley notifications@github.com wrote:

About needing the state machine contexts external to the SM (in the guards, actions, etc).. I looked through it a bit more. the uSCXML library had them so I'd assumed they're necessary for some SCXML support.

I'm not so sure after looking through the SCXML spec (grepping for "must" is pretty handy). The only thing I could find was related to parallel states where a transition can be conditional based on the sibling states <transition cond="In('open')" target="idle"/> where the In('open') is a predicate for detecting the current state. It could potentially be handled internally to the SM or via the data model purely by users.

... ... ... ...

Though having a way to support something like <assign location="timer" expr="timer + 1"/> would be great, I'll probably start with just pre-set setters (like you do in the guard examples and setting flags). But even then the transition / entries / exits would only need access to the current data model.

Currently I'm writing SCXML just by hand. I find it pretty easy to read & write (at least for smaller examples). Much easier than the XMI format. If I need to move toward graphical editing I'd like to take up creating a vuejs or web-component renderer / editor. I'd experimented with the idea before, and it'd pretty easy using web-components to create components which map to SCXML elements with a simple prefix/name mapping. There's some pure JS libraries out there that handle SCXML as well.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/jonpe960/ufsm/issues/5#issuecomment-397104847, or mute the thread https://github.com/notifications/unsubscribe-auth/ANUXFdFPXJNscGB8PFrexrOGf55itMWdks5t8Y62gaJpZM4UhChH .

[elcritch]

That's looking promising. I'll try it out with some simple data models. Wonder if I could get a "count down" working...

[elcritch]

Made a simple test for the equivalent of an SCXML send by just calling the queue_put. I made the test just do a simple repeat (which is surprisingly handy). Next I'll try passing the machine and data pointer to the action/guard. With that I think it'd be possible to implement a SCXML -> UFSM importer tool. Well at least a pretty basic one. :-)

https://github.com/elcritch/ufsm/blob/3c4fcf842f1cf06b434acfb907a0df6860902d9d/src/tests/test_guard_repeat.c#L46