A concurrency model for the runtime

[erlingrj]

We lack a defined and thought-through "concurrency model" for our runtime. By this, I mean clear guidelines for how different execution contexts interact in our runtime, where there should be critical sections, and whether certain parts of the code only can be called from a certain context or whether it is always called inside or outside a critical section.

This problem surfaced because currently, too much of the runtime execution is done inside a critical section, and with logging: Debug, there is a lot of printing also (which is very slow on MCUs). This is only a problem on bare-metal because on bare-metal critical sections disable interrupts and prohibit any async context from executing. While on OS platforms, the critical section is a mutex, which allows async contexts to run, as long as they don't try to enter a critical section.

I don't have a clear picture of this yet, so this document will serve as a tool for exploring and understanding the problem.

The asymmetry of critical sections

On bare-metal platforms critical sections are implemented by disabling all interrupts and thus blocking any async context (such as an ISR receiving bytes from UART) from executing. This suggests that critical sections should be used sparingly and only for short periods.

On OS platforms critical sections are less "expensive" as we use a mutex and don't necessarily block other threads.

However, the runtime itself is platform-agnostic and should not be concerned with whether it is running bare-metal on Pico or on a OS. Also it should not need to know whether a network channel is interrupt-driven or has a thread running in the background.

Because of this we need to think about critical section as if we are on bare-metal. I.e. we must assume that whatever the NetworkChannels are doing in the background is halted whenever we are in a critical section. Meaning that we must keep them sparse and as short as possible.

Points of interaction between execution contexts

There are four main points of interaction between execution contexts

1. Scheduling of physical actions.
   This is the obvious one. The user can create an async context (thread/ISR) that schedules a physical action. This reads out the current time and modifies the event queue. Both of which need a critical section. The former because we are doing clock sync.

2. Polling the connection status of a NetworkChannel
   This is done from the runtime-side. And it might inspect the state of the NetworkChannel and it might also send messages or do other things to advance the connecting of the NetworkChannel. This might need a critical section wrt other threads/ISRs also modifying the NetworkChannel.

3.Sending data over the NetworkChannel
This also done from the runtime-side through chan->send_blocking(). This should be independent of the receive path, however, certain implementations (such as UartChannel) will also call chan->send_blocking() asynchronously to reply to custom UART connection messages. This implies that we need a critical section around send_blocking. Unfortunately, in the CoapChannel we depend on send_blocking being called OUTSIDE a critical section. Because it needs interrupts enabled to get the ACK.

4. Async context receiving data etc within the NetworkChannel
   Most likely, each NetworkChannel has some other execution context modifying it, either a thread or an ISR. Typically it is copying received data into some buffer, and possibly tries decoding this data. In some cases (e.g. UartChannel), it also can call send_blocking to implement its own protocol to ensure that we have a connection status. Finally, the async context will interact with the runtime in some way.

5. Received message callback
   When a NetworkChannel has received an entire message it will call the msg_received_cb which takes it into the runtime. This is a point of interaction where the async context is executing "within" the runtime with access to its data structures. As we have added the System Event Queue, this callback should only schedule an event or a system event and return. This must naturally be within a critical section such that the runtime is not modifying the event queue or system event queue at the same time. It will also update some fields of the input port structs (such as last_known_tag etc).

I think (1) and (5) are clear. It is a well-defined interaction and it is clear that the async context must enter a critical section before modifying the data structures. Also it is (mostly) clear where the runtime context must have critical sections. (When interacting with the event queue and the system event queue. And when looking at the last_known_tags of federated input ports.

It appears to me that (3) the runtime calling send_blocking is perhaps the most tricky problem. Because some channels (CoAP) require this to be done from outside a critical section, while at the same time, other channels (UART) want to do this also from the async context behind the scenes. This function is not reentrant, and it might not be possible to require that it is (because it copies data into a buffer and possible interacts with HW peripheral)

This thread will be continued next week

[erlingrj]

Two important points:

1. We should absolutely have nested critical sections, it makes it a lot harder to disallow this.
2. The default state should be that we are not in a critical section. Any function that assumes that it is in a critical section (because it somehow touches shared memory, or it calls other functions that assume a critical section) should be postfixed with _locked

Shared data structures

The following data structures are "shared", i.e. accessed from runtime-context, channel-context and async-context (physical action etc).

1. Event queue. (async-context and channel-context)
2. System event queue. (channel-context)
3. InputPort.last_known_tag. (when receiving a TaggedMessage the channel-context can update this)
4. Event Payload Pools. Payloads are allocated when scheduling events. And freed when handling them. This might be considered part of the event queue handling.
5. Physical clock offset and adjustment. This is subtle (and unfortunate). The runtime-context can modify the offset and adjustment of the physical clock (i.e. doing clock sync), this needs synchronization with reading out the current physical time.

What about the network channels?

1. Network channels can not assume that any of its API functions are called from a critical section.
2. NetworkChannel->send will only be called from the runtime context.
3. Network Channels must take care to implement the correct synchronization. E.g. in the UartPolledChannel, from the channel-context (which is an ISR), we directly reply to received messages, calling NetworkChannel->send. This means that in the UartPolledChannel the entire NetworkChannel->send should be in a critical section.

[erlingrj]

More thoughts here what concurrency primitives must be offered by the platform:

1. A mutex. This could be just disable/enable interrupts. But it could also be an OS mutex. This is needed to protect access to the shared data structures, such as event queue, payload pools, etc. We can have a single mutex for the entire runtime or more fine-grained, mutexes for each data structure.
2. Sleep. We need a way for the runtime context to sleep for a duration or until an absolute time point. This sleep can be performed while holding a mutex or not (but probably not a good idea to hold a mutex while doing this)
3. Interruptible sleep. A way to sleep for a duration, but wake up if an async context does something

[tanneberger]

I am very much in favor of trying to push as much as possible to the platform.

Implementing our own mutual exclusion primitive, is not really our "business".

I think the important point here is that we should still aim to keep the abstraction very slim, so I would advocate for getting rid of the enter_critical_section and leave_critical_section functions.

[tanneberger]

I would advocate that the platform book keeps potential platform specific mutex structs and the platform-agnostic part of the code gets an identifier as a mutex-type.

typedef int reactor_uc_mutex_t;

struct Platform {
    // other stuff
    
    lf_ret_t (*open_mutex)(Platform*, reactor_uc_mutex_t);
    lf_ret_t (*close_mutex)(Platform*, reactor_uc_mutex_t); 
}

and then we can add some sugar-coating:

struct Mutex {
    void* value;
    reactor_uc_mutex_t mutex;
    
    lf_ret_t (*open_mutex)(Mutex*);
    lf_ret_t (*close_mutex)(Mutex*); 
};

lf_ret_t Mutex_open_mutex(Mutex* self, void** ptr) {
    lf_ret_t ret = _lf_environment->platform->open_mutex(_lf_environment->platform, self->mutex);
    if (ret != LF_OK) {
        return ret;
    }
    *ptr = self->value;
    return LF_OK;
}

[erlingrj]

I dont follow your arguments here. First you say we should not implement our own mutex, and I do agree, lets not reinvent the wheel. But next you propose exactly this? A special data type with a pointer to the data which it protects? I don't think we should try to re-implement std::lock_guard or similar, and instead provide a very thin layer over the locks provided by the platforms we support.

Introducing our own integer file descriptors for locks will make it challenging to avoid dynamic memory allocation, because we need to allocate space for the actual locks, which might or might not fit in an integer. I think a better approach is to use a compile definition that is platform-dependent. This is exactly what I am doing in this PR #276 where I use MUTEX_T as the mutex type which will be provided by the platform files.

[erlingrj]

Our last meeting we had a discussion on how to enable the use of both interrupts and mutexes. The problem is that we want to use OS mutexes from Zephyr, RIOT and Posix when we have those available because we can then reduce the blocking between threads. If interrupts are disabled then no other thread can progress. If you just lock a mutex then other threads can execute, unless they try to acquire that lock.

However, such locks can not be acquired by interrupts. We discussed adding a parameter Mutex_ctor(Mutex *self, bool interrupts_safe). And we could make a lock interrupt safe if it needs to be acquired by an interrupt.

Unfortunately, this would affect most of the Mutexes we created in:
Action, PayloadPool, EventQueue, Scheduler.

I am going to think a little more on this problem. Perhaps we need a user-configured compile def that tells us if he will schedule any actions with interrupts.

[edwardalee]

Why did you reject the solution that reactor-c uses, which is to make a distinction between a critical section and a mutex?

[erlingrj]

I dont think that helps us. Reactor-c only exposes mutexes for the threaded runtime. We have a single concept Mutex that is supported by bare metal and OSes. We also decided against using critical sections (disabling all interrupts / grabbing a global lock) and instead add a Mutex to the data structures that needs protection.

For bare metal this is naturally implemented with disabling interrupts

[tanneberger]

And personally, I don't see a reason to support both. This would just unnecessarily bloat our platform abstraction.