Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Haiku's (Kernel) Condition Variables API: Design and Implementation

haiku-os.org

Post reply on HN
Print view View original

11–17 of 17 posts

Re: Haiku's (Kernel) Condition Variables API: Design and Implementation

#11

Post by tialaramex »

saagarjha wrote: post #10
tialaramex wrote: post #6

Earlier quoted context omitted.

> 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 orderin…

FWIW your response comes across to me as quite rude and patronizing. I assume you didn’t mean this but the fact that you’ve decided to capitalize terms as if you have some sort of true definition for them, plus you dragging this conversation towards the specific complaint you had in another comment (Haiku might use sequential consistency when it doesn’t need to…although it’s not even clear if you’ve done the appropri…

The capitalization reflects terms of art in the C++ 11 memory model. So, not my "true definition" but the one provided by the language used, in this case C++. This matters because Haiku is written in languages which use this model (or in some cases languages which don't specify any model but in practice conform to the C++ 11 model)

If you're Linus Torvalds you can insist compiler vendors adjust things as you prefer to some extent, thus the Linux memory model isn't quite the C++ 11 memory model despite the fact that GCC is used to compile Linux and GCC notionally confirms to C11 (and thus has the C++ 11 memory model), much of what Linux does is not conforming to the ISO document. Haiku can't expect the same benefit of the doubt.

The question of whether Haiku needs sequential consistency where it has it is vexed. Hyrum's law applies. The least scary approach might be to follow C++ and provide sequential consistency by default with an opt-out, then introduce use of the opt-out carefully.

Re: Haiku's (Kernel) Condition Variables API: Design and Implementation

#13

Post by waddlesplash »

tialaramex wrote: post #9
waddlesplash wrote: post #7

Earlier quoted context omitted.

> 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 ens…

> 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. You seem to think this is a joke, but it isn't. Obviously from the CPU's point of view there is no "time travel" but that's cold comfort for users. The Alpha doesn't promise that there's any coherent ordering at all unless you've imposed one, which the…

> The Alpha doesn't promise that there's any coherent ordering at all unless you've imposed one

Yes. But why did you bring this up in this thread about API usage? It's the implementation's problem to make this work out. "Add()" should be the equivalent of a full memory barrier (at least for the condition variable's memory) no matter how that happens internally.

> This price isn't unique to Haiku, but the choice to pay it (almost) everywhere is, at least in terms of operating systems people would be using today.

Haiku is, in many ways, poorly optimized when compared on such details with Linux or FreeBSD, all the developers know this fact, and we make no secret of it. If this was your entire point in the first place, why not just say so?

By the way, as far as I can tell, OpenBSD's kernel atomics (sys/atomic.h) do not have different versions for different memory orderings; in fact they use the older-style GCC builtins and not the C++11-style ones, so they are also using sequential consistency everywhere they use atomics. Is OpenBSD not a "modern operating system people would be using today"?

Re: Haiku's (Kernel) Condition Variables API: Design and Implementation

#14

Post by wbl »

waddlesplash wrote: post #3
wbl wrote: post #2

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 Fre…

Ah so the add starts the period during which notifications will be caught ahead of the wait call.

Re: Haiku's (Kernel) Condition Variables API: Design and Implementation

#15

Post by tialaramex »

waddlesplash wrote: post #13
tialaramex wrote: post #9

Earlier quoted context omitted.

> 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. You seem to think this is a joke, but it isn't. Obviously from the CPU's point of view there is no "time travel" but that's cold comfort for users. The Alpha doesn't promise that there's any coherent ordering at all unless you've imposed one, which the…

> The Alpha doesn't promise that there's any coherent ordering at all unless you've imposed one Yes. But why did you bring this up in this thread about API usage ? It's the implementation's problem to make this work out. "Add()" should be the equivalent of a full memory barrier (at least for the condition variable's memory) no matter how that happens internally. > This price isn't unique to Haiku, but the choice to p…

I guess, ultimately if the argument is we don't care about performance or capability then, you know, fine, although if you don't care it's weird to do two rewrites focused on performance and write a blog post to highlight the work.

AIUI OpenBSD doesn't lean exclusively on those primitives, you might notice for example it has futexes these days. On the other hand I also don't know anybody who runs OpenBSD.

Re: Haiku's (Kernel) Condition Variables API: Design and Implementation

#16

Post by wbl »

tialaramex wrote: post #6
waddlesplash wrote: post #3

Earlier quoted context omitted.

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 Fre…

> 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 orderin…

Huh? Happens before subsumes in thread order. Any events that are caused by long running operation must happen after the addition of the event to the condvar.

Re: Haiku's (Kernel) Condition Variables API: Design and Implementation

#17

Post by saagarjha »

tialaramex wrote: post #11
saagarjha wrote: post #10

Earlier quoted context omitted.

FWIW your response comes across to me as quite rude and patronizing. I assume you didn’t mean this but the fact that you’ve decided to capitalize terms as if you have some sort of true definition for them, plus you dragging this conversation towards the specific complaint you had in another comment (Haiku might use sequential consistency when it doesn’t need to…although it’s not even clear if you’ve done the appropri…

The capitalization reflects terms of art in the C++ 11 memory model. So, not my "true definition" but the one provided by the language used, in this case C++. This matters because Haiku is written in languages which use this model (or in some cases languages which don't specify any model but in practice conform to the C++ 11 model) If you're Linus Torvalds you can insist compiler vendors adjust things as you prefer t…

I'll respond to your comment anyways but I do want to remind you that I think it's more a reflection of you talking about what you want to talk about rather than being particularly relevant to this thread.

Operating systems are often written in C or C++. Both of these share a formal memory model to provide a set of useful semantics for well-formed programs. For most code the choice to adhere to this model is the right one. In fact, in many cases it can be appropriate to pick more "heavyweight" constructs despite the fact that they can be a bit slower because they are easier to reason about. LLVM's libc used sequential consistency for its shared_ptr implementation for quite a while until it was updated to use a more efficient set of primitives.

On the flip side, sometimes it is not appropriate to use this memory model. Linux has its own because it predates the C(++)11 memory model. Other good reasons to use your own model can be if the standard one doesn't efficiently map to what you are trying to do on the hardware you're on, or if the operations you need to perform are not encoded in the standard. These kinds of things are actually quite common in operating systems, which is why most of them do not strictly conform: C11 has no concept if "this region of code runs with interrupts disabled" or "I need a full serializing barrier for device memory". Haiku chooses to do its own thing, which may or may not be appropriate for its use case. Coming in and claiming immediately that whatever it's doing must be bad is inappropriate and lacks context.

Post reply on HN