So what I not understand about this design is how one uses it. In the classic condvar application one waits atomically with the lock because otherwise the other thread may deliver the signal before the wait happens, leading to a deadlock.
Here it seems there is no atomicity. How does this get used?
You are correct that deadlocks can be caused by signals occurring before the wait starts, and thus some sort of mechanism to ensure this does not happen is needed, but I explained as much in the article. The point of this API is that the atomic lock-switch is not restricted to just locks; and further, in some situations, no lock-switch is needed at all.
The former is simple enough, and directly equivalent to what FreeBSD's API allows you to do (and what Haiku's API provides as "convenience methods", as the article notes), and is "atomic" -- it just pushes the atomicity up a level and lets the programmer control it more directly:
ConditionVariableEntry entry;
gSomeConditionVariable->Add(&entry);
mutex_unlock(&someLock);
/* (I could unlock more locks here, if needed, I'm not limited to 1) */
entry.Wait();
mutex_lock(&someLock);
The latter case is the more interesting and unique one, and the article references one place it is actually used in practice (team/process creation), though it doesn't give a pseudocode example, so let me try to give one here:
ConditionVariableEntry entry;
someLongRunningOperation.conditionVariable->Add(&entry);
someLongRunningOperation.start();
/* (I can do whatever I want here, no need to Wait immediately) */
entry.Wait();
Since this "long-running operation" is not even started until after the local Entry has been Add'ed to the Variable, there's no possible way for this operation to complete and signal before we have started 'waiting' (because, even if the Wait() call is at the end, it's the Add() call that counts.)
> Since this "long-running operation" is not even started until after the local Entry has been Add'ed to the Variable, there's no possible way for this operation to complete and signal before we have started 'waiting'
What you've got there is a "Happens before" constraint. Your "no possible way" is assuming Sequential Consistency, but I assure you that your CPU does not in fact provide Sequentially Consistent ordering of individual CPU operations across multiple cores.
You need some way to reliably Order the events. It's possible that the vaguely named "atomic" operations in Haiku provide you with adequate ordering, but who knows since they don't specify.
> Your "no possible way" is assuming Sequential Consistency,
I am assuming events cannot finish before they are started, yes! I am pretty sure that even the (in)famous DEC Alpha could not possibly have time-traveling results.
Once again: there is a distinction between the API itself, and the API's implementation. Once the "Add" function returns, the "Entry" is now waiting on the "Variable". How the "Add" function ensures that is entirely abstracted away from the consumers of the API.
The implementation of "Add", at least, is synchronized using a very standard spinlock, just like similar operations are for mutexes, semaphores, etc. not just on Haiku, but on all the BSDs and Linux. We don't even need to think about CPU operations ordering for that, the spinlock takes care of it for us.
I am pretty sure Linux (and every other operating system, ever) would be in all kinds of trouble if you could read stale values from memory protected by spinlocks, so I don't know why you are casting doubt on these things.
> It's possible that the vaguely named "atomic" operations in Haiku provide you with adequate ordering
Hey, you already wrote a comment elsewhere in this thread about this point, and I replied to your comment with a bunch of information proving definitively: they do, in fact, provide that ordering. But in the cases I described in the parent comment here, it does not matter, because here we are talking about API consumption, not implementation.
BeOS, which is the foundation for most of this work, is from the 1990s. But in the 1990s C++ didn't yet have a clearly defined Memory Model for the purposes of concurrent algorithms and BeOS doesn't try to come up with one.
In the subsequent 25+ years, C++ developed a Memory Model which distinguishes ordering for these atomic operations. Because BeOS pre-dates that, it doesn't document an ordering, let alone provide a mechanism to pick one. Unfortunately different concurrent algorithms have different ordering requirements, if what you're given is looser the algorithms may malfunction, if it's stricter the performance may be hampered.
I reckon that before trying to claim you've innovated here it might be a good sense check to compare baseline. What exactly are the Haiku atomic operations, in terms of the C++ 11 Memory Model ? If you were Linux (or to some extent Windows) you could trail blaze here, because you're innovating before 2011, you're inventing the model - but this is 2023, so Haiku is off in the jungle on its own and everybody else has a map now, figure out where you are on that map first.
Haiku uses the System V ABI (mostly.) So, we're doing the same things Linux and the BSDs are here, simply by using GCC or Clang without any special tuning here.
> I reckon that before trying to claim you've innovated here it might be a good sense check to compare baseline.
The baseline is "what are other operating systems' kernel- and userland-level condition variables APIs?" And none of the ones I looked at had anything like what Haiku has here, they all have something which is the more classical "lock-switched condvars" just like POSIX has.
The API itself does not depend on what memory ordering semantics are any more than a "mutex_lock()" API does. The implementation will be somewhat contingent on it, of course, but those are two separate matters.
> What exactly are the Haiku atomic operations, in terms of the C++ 11 Memory Model?
The atomic_() functions are (on most architectures, x86 included) implemented using GCC/Clang's __atomic_* functions, with various __ATOMIC_* orderings chosen as appropriate. You can see them defined in the system header here: https://github.com/haiku/haiku/blob/master/headers/os/suppor...
> because you're innovating before 2011, you're inventing the model
No, not really? GCC has had atomic builtins since at least 4.1.0 in 2006. The documentation (https://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins...) says: "In most cases, these builtins are considered a full barrier. That is, no memory operand will be moved across the operation, either forward or backward." -- which is basically equivalent to today's __ATOMIC_SEQ_CST.
> so Haiku is off in the jungle on its own and everybody else has a map now, figure out where you are on that map first.
We already did that years ago. The atomic_*() functions linked above in SupportDefs.h have been implemented using the C++11-standard GCC builtins since 2014, and the older __sync_* builtins for years before that.
Anyway, the algorithm described in this article, even if Haiku's atomic functions were not 1:1 with C++11-standard definitions (which they are, as noted above), is clearly portable to other OS kernels. So I am not sure what basis your comment has, regardless.
> The atomic_() functions are (on most architectures, x86 included) implemented using GCC/Clang's __atomic_* functions, with various __ATOMIC_* orderings chosen as appropriate.
There is no one-size-fits-all choice here, so "as appropriate" is almost definitionally a mistake. It turns out that "as appropriate" for Haiku means Sequential Consistency except on simple load and store, which have Acquire-release semantics instead for some (unexplained in my brief exploration) reason.
Still that does answer the question of why these structures seem to work for Haiku despite the lack of what you'd ordinarily expect in terms of ordering guarantees, it's eating a Fence for each Entry and a Fence for each mutex operation. It's a steeplechase!
Here it seems there is no atomicity. How does this get used?
reply