[riot-devel] Condition Variables and IPC

Dominik Charousset charou_d at informatik.haw-hamburg.de
Sat Feb 15 02:30:57 CET 2014

Dear rioters,

in preparation for the next status meeting, we have collected some issues and open questions with libcppa on RIOT and C++ support in general.

=== Condition Variables ===

The main issue we have right now - in fact, it's a blocker for us - is the lack of condition variables on RIOT. At first glance, it seemed it might be possible to write condition variables on top of a mutex and the thread_sleep/thread_wakeup function pair. However, this approach is neither save nor would it support timed wait operations.

To implement condition variables in userspace, we thought of using a Mutex M and a list of waiting threads L. However, this approach can lead to a deadlock:
- (1) Thread A grabs M, (2) checks the condition (false), (3) adds itself to L, (4) unlocks M and (5) calls thread_sleep()
- (a) Thread B grabs M, (b) sets the condition to true, (c) calls thread_wakeup() for each thread in L, (d) unlocks the mutex
A deadlock occurs if thread A gets suspended after (4) but before (5) and thread B performs (c) in the meantime, before A calls thread_sleep().

Since condition variables are a very basic and commonly used synchronization primitive, it would make sense to implement it in RIOT directly, maybe using an API like this:
(I) cv_notify_one(...)  // notifies one waiting thread
(II) cv_notify_all(...) // notifies all waiting threads
(III) cv_wait(...)      // blocks the caller until it is notified by another thread
(IV) cv_wait_for(...)   // blocks the caller until it is notified or until the specified timeout duration is reached
(V) cv_wait_until(...)  // blocks the caller until it is notified or until the specified time point has been reached
The difference between (IV) and (V) is that the first one uses a relative timeout whereas the latter uses an absolute timeout. Function (V) is particularly useful for dealing with the problem of spurious wakeup.

All wait functions take a mutex that must be locked when calling the wait function. After the thread has been woken up again, the mutex is locked again. This cannot be guaranteed in userspace unless RIOT would offer a function like "mutex_unlock_and_sleep" which *atomically* unlocks the mutex and puts the calling thread to sleep mode. It then would be safe to use the algorithm described earlier, as there would be no possible way for thread A to get interrupted between step (4) and (5). Still, functions (IV) and (V) would be hard, if not impossible, to implement properly in userspace.

Are there any plans to add condition variables to RIOT?

=== C++ support on RIOT === 

As far as C++ support is concerned: std::thread is broken on GCC. The code does compile, but the program crashes at runtime. We have traced down the issue and have found that GCC uses the glib (which does not work on RIOT) to implement the STL. This means that C++ is supported only partially on RIOT, as some parts of the STL simply do not work. This is unfortunate, but at least we have the compiler running. Unless there is a skillful GNU developer with too much time in the RIOT team that fixes the glib right away, we would fall back to the POSIX wrapper or native interface for threading in our code base. So... "C++ Support" on http://www.riot-os.org/#features should actually show an orange dot instead, unless you cheat your way around by saying it's C++98 support or by excluding the STL. ;)

=== Semantics of IPC ===

The function msg_send allows a thread to send any kind of message to another thread by passing a void pointer. My question is: I browsed through the code as well as the documentation and it seems the memory is passed without any copying in the kernel, but this is not stated in the documentation explicitly. Is the passed memory guaranteed to never be copied? If so, this would in turn mean that RIOT could never run using an MMU, wouldn't it? I'm asking, because we wanted to send a C++ object from one thread to another. In this case, we need to know whether or not the kernel is allowed to copy the data on some platforms/in a future release. This is important to us, as allocating an object on one end using new() and releasing it with free() is undefined behavior. So is calling delete() on a memory block allocated using malloc(). Byte-copying an object also breaks virtual functions.

=== Overhead/Performance of IPC ===

Do you have any benchmarking results or overhead analysis available for the IPC performance on RIOT?

Best regards,
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.riot-os.org/pipermail/devel/attachments/20140215/f59f97d9/attachment.html>

More information about the devel mailing list