Implementation of C++20's P1135R6 for libcxx

[__simt__]

Summary

This is the first review of this code so there's a lot to look at, and I'm fully expecting a lot of changes will be requested.

This patch contains...

A) Changes to __threading_support that introduce:

1. Low-level semaphores on POSIX and Apple GCD, and futex on Linux.
2. Declarations for a sharded table of contention state in the dylib, used by atomic::wait.
3. Declarations for a thread_local variable in the dylib, used by barriers.

B) The <atomic> changes from P1135:

1. High QoI: multi-layered back-off, using either/both the state from 1b and futexes from 1a.
2. Low QoI: exponential time back-off, using chrono only.

C) Barrier:

1. High QoI: a tree barrier, using the acceleration state in 1c to amortize the extra round.
2. Low QoI: a central barrier, with a specialization for the empty completion function.

D) Semaphore:

1. All QoI: a general template semaphore for very large ptrdiff_t values.
2. High QoI: a specialization for “reasonable” ptrdiff_t values, using semaphores in 1a and acceleration atomics.
3. Low QoI: a specialization for unit count.

E) Latch:

1. All QoI (low): a central latch. (If there's a desire to see it, I could borrow the same QoI knobs from barrier, but sizeof() would grow a lot.)

F) The first basic tests for each facility from P1135.

G) Miscellaneous tweaks I needed to get this to build as libcu++ (the CUDA variant). We can drop these or you can take them as improvements. One of them is a legit macro bug.

[__simt__]

include/atomic

1557

This one is fun.

The model for a condition variable is that there is a lock that guards all reads and writes of the variable that has a condition evaluated on it. In this case here, that variable is an atomic, and we both read and write it outside the lock - we evaluate the condition outside the lock with much greater concurrency. However we're still exposed to a race here, because threads may be transitioning into the sleep state as we come to notify.

Taking the lock here resolves this race condition, even if we do nothing with the critical section.

include/barrier

81

It can be. How do we do that?

200

This one doesn't need to be. Removing.

217

That's not how it works in <atomic> and I patterned on that. Also it helps the CUDA port be less tedious.

If you feel strongly about this one I can obviously take the extra steps, but do you?

include/chrono

1065

No.

1571

Yes. CUDA can't make OS calls but we do have another way of implementing this. So I made it external-izable.

[EricWF]

Are the lock free algorithms used by this implementation published somewhere? That would give me a lot more confidence in their correctness.

[__simt__]

In D68480#1705203, @EricWF wrote:

Are the lock free algorithms used by this implementation published somewhere? That would give me a lot more confidence in their correctness.

Now that's getting to the meat of the matter! The short answer is no, and the long answer is that it depends on what we're going to call an algorithm.

The <latch> code is more-or-less the spec's exposition converted into code, but I think it needs to become more complex later, for QoI reasons. In <barrier> we have well-known barrier algorithms like linear/central and tree/hierarchical barriers, but the pseudocode you'll find in literature needs a lot of adaption to fit into C++ in general (which doesn't do thread-local non-static members for classes), and into the C++20 std::barrier interface in particular (which doesn't assign a dense index space of IDs to thread that could be used to access O(P)-sized internal structures) -- and all that adaptation is 90% of the code in that file, not the algorithm itself. Finally, the gnarly code in <semaphore> is not the semaphore algorithm proper either (because that's been left to the OS except for the fallback cases) but the acceleration layer that one would need to put on top of it in order to make it fast (avoid calling the OS when it's not strictly necessary).

To be clear, I am reasonably concerned that there are bugs in this code, as well. The simpler / lower-QoI paths which CUDA will eventually ship are decently solid, but the complex / high-QoI paths that a performant CPU implementation needs (read: existentially needs, even in ~6 core laptop) are not as well tested relative to their complexity.

On our end, I think our intentions are to write more fuzzer-like tests that apply stress on them. I also have in the back of my mind the idea of proposing a C++Now talk in the vein of "How-to P1135 @ High QoI", to capture more eyeballs / document the post-adaptation versions of the algorithms better.

Where would you like to take this chat next?

[griwes]

libcxx/include/semaphore

67 ↗

(On Diff #224121)

Use a reserved identifier for the template parameter.

409 ↗

(On Diff #224121)

Use a reserved identifier for the template parameter.

420 ↗

(On Diff #224121)

Use a reserved identifier for the template parameter.

libcxx/test/std/thread/thread.barrier/arrive.pass.cpp

19 ↗

(On Diff #224121)

This depends on CTAD, which makes it only work in C++17 and above. Instead it should probably say std::barrier<> b;.

Same comment for all the other barrier and semaphore tests.

[__simt__]

Refactored the semaphores into layers that each do one clear thing, and dispensed with a lot of #ifdefs. Moved as much semaphore code as possible out of the header and into the dylib.

Refactored the atomic code which previously necessitated type punning so it no longer does that, and narrowed the declarations of the contention state type. Made use of private contention state in the internal libcxx types that make use of wait/notify so they don't create contention with the user's uses of wait/notify.

Refactored some of the classes which previously used public inheritance of interface members, to use containment of the base type and forwarding member calls instead. This also let me simplify the bases to only define the core functionality and put the sugars on the one user interface type.

Removed asserts and alignas, and fixed several names which were not reserved before.

Fixed some issues Michał pointed out.

Fixed bugs where semaphores would randomly assert on APPLE.

Fixed bugs where semaphores would randomly fail timed waits on linux.

[__simt__]

Simplified how the contention state is conditionally-used.

Fixed several breaks in the CUDA version from the last patch.

[__simt__]

Fixed an incompatibility between the _Atomic(T) backend of <atomic> and the Futex function SFINAE in <__threading_support>.

[__simt__]

Added some documentation for the semaphore and barrier algorithms as comments.

Fixed a few issues hit on Linux when overriding to disable optimized paths.

[__simt__]

Oof, didn't attach the patch.

[zoecarver]

libcxx/include/atomic

1477 ↗

(On Diff #225670)

I think this can be a static_cast.

1533 ↗

(On Diff #225670)

Might be wrong but, can't this be a CAS (because you are both comparing and swapping 0)?

1535 ↗

(On Diff #225670)

Why do you lock, then immediately unlock the mutex here?

1563 ↗

(On Diff #225670)

Is this another "magic" number? If so, can it be a macro too?

1696 ↗

(On Diff #225670)

This should only be defined after C++17.

1697 ↗

(On Diff #225670)

You can use memory_order::seq_cst here.

1821 ↗

(On Diff #225670)

Is this available in C++03? If so, use typedef.

Actually, do we support any compilers that don't support using type aliases?

libcxx/include/semaphore

105 ↗

(On Diff #225670)

Does __cxx_atomic_notify_one always call out to __cxx_atomic_notify_all? If so, can we get rid of __cxx_atomic_notify_one?

[__simt__]

libcxx/include/atomic

1477 ↗

(On Diff #225670)

Actually it can and should go away now. I'll remove the cast.

1533 ↗

(On Diff #225670)

It's not conditionally exchanging, it's exchanging unconditionally and then conditionally taking a computation step.

1535 ↗

(On Diff #225670)

I answered that one here: https://reviews.llvm.org/D68480?id=223282#inline-618652

1563 ↗

(On Diff #225670)

Sure.

1696 ↗

(On Diff #225670)

That would be unfortunate, I think, <atomic> in general tries to offer its functionality in back versions.

Also, the CUDA port definitely doesn't want to be tied to '17 for quite some time.

Can we leave it on in all dialects that <atomic> supports, like the rest?

1697 ↗

(On Diff #225670)

Pending other comment's resolution.

1821 ↗

(On Diff #225670)

Will do.

[__simt__]

In this update I repaired the usefulness of <atomic> in C++03 mode. Other headers won't be supported there, but I'm avoiding regression to <atomic>.

[__simt__]

In this version I moved the tree barrier's core algorithm into the dylib so that any functional or performance issue found in it later could still be fixed without breaking ABI. By the same fact it narrows the visibility of the definition of the thread_local symbol it uses.

[__simt__]

This revision enables cross-ABI compatibility for building the dylib and the user application with different combinations of these options:

• _LIBCPP_HAS_NO_PLATFORM_WAIT
• _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE
• _LIBCPP_HAS_NO_PLATFORM_WAIT_STATE

When the ABIs are mixed, the total application still gets the best performance available for the facilities actually available in common. This is somewhat gnarly (apologies for the several void*...) but was requested offline, to allow for a platform to progress from not having Futex support (say, today) to having Futex (eventually, later).

What this ABI hardening does not include is support for changing the type of "__libcpp_platform_contention_t" from a uint32_t to a uint64_t, later. Once a platform chooses to expose Futex, it's an ABI break to change the size of that, so it's worth pondering whether the platform should be held back until it can support uint64_t Futex.

This revision also introduces an internal-only abstraction layer called "__atomic_positive_ptrdiff_t" which centralizes a lot of turning concerns for both latches and semaphores, when layered on top of atomics, for different configurations.

In this revision the APPLE configuration is a bit quirky: 1) the headers build as if Futex is enabled and is a uint64_t, but 2) the dylib builds as if Futex is disabled and leans on the cross-ABI compatibility to fall-back to mutexes and condvars. Also, this is not quirky but my new recommendation, on APPLE it no longer uses dispatch semaphores.

[__simt__]

Closing out some obsolete comments after changes and/or testing.

[__simt__]

Hi guys. Could I get some action items or other movement on this review? Would you like me to make it possible to merge it as disabled or as experimental, and send me DRs to fix afterwards?

[ldionne]

• _LIBCPP_HAS_NO_PLATFORM_WAIT
• _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE
• _LIBCPP_HAS_NO_PLATFORM_WAIT_STATE

It would be great to document these macros somewhere in the code or in a .rst document.

Also, this paper didn't add any feature-test macro?

libcxx/include/atomic

1850 ↗

(On Diff #226990)

Can we add a test for this?

1871 ↗

(On Diff #226990)

This too!

libcxx/include/chrono

1571 ↗

(On Diff #226990)

What's that?

libcxx/include/semaphore

77 ↗

(On Diff #226990)

Thanks for the comments in this file, I wish we did that more often.

libcxx/include/type_traits

4032 ↗

(On Diff #226990)

What are these drive-by fixes?

[__simt__]

libcxx/include/atomic

1850 ↗

(On Diff #226990)

Yes, I can do that.

1871 ↗

(On Diff #226990)

Ack.

libcxx/include/chrono

1571 ↗

(On Diff #226990)

Timed wait functions need <chrono>. That meant that I had to port <chrono> to CUDA as part of this effort. In CUDA you can't ask the OS for the time, you need to ask the silicon for the time. I followed the precedent of external threading to implement this as external clocks. Makes sense?

libcxx/include/semaphore

77 ↗

(On Diff #226990)

NP, Eric had requested something here. Feel free to ask for comments elsewhere.

libcxx/include/type_traits

4032 ↗

(On Diff #226990)

It's important for the CUDA port that there not be naked "namespace std { ... }" that don't use the macros, because we need to inject our namespace name. I tried to keep the drive-by to a minimum.

[zoecarver]

Thank you for all the work you've put into this patch. Here are a few more comments. Still working through all this code :)

I'm becoming increasingly worried about the amount of inline configuration and platform-specific code. I want to make sure we have tests for all of these (and ideally CI that can run all the tests).

libcxx/src/atomic.cpp

28 ↗

(On Diff #226990)

For what platforms is _LIBCPP_HAS_PLATFORM_WAIT_STATE false, and have you tested on those platforms? I'm worried that there might be compiler errors.

32 ↗

(On Diff #226990)

What's the point of this macro, ATOMIC_VAR_INIT (I realize you didn't add it, but I'm still curious)?

46 ↗

(On Diff #226990)

This is different if _LIBCPP_HAS_PLATFORM_WAIT_STATE is false, right?

129 ↗

(On Diff #226990)

Will this ever be true?

133 ↗

(On Diff #226990)

same as below

139 ↗

(On Diff #226990)

Is there a test for this case? What will be the effect of __s not getting updated?

148 ↗

(On Diff #226990)

Instead of having void pointers that are casted, I don't see any reason these couldn't be defined as their actual types (__cxx_atomic_impl* and __libcpp_platform_contention_t*).

162 ↗

(On Diff #226990)

Is __libcpp_platform_wait defined on non-linux machines?

libcxx/src/barrier.cpp

44 ↗

(On Diff #226990)

Will this ever not only happen on the first iteration (if so, move it out of the loop maybe)?

libcxx/src/semaphore.cpp

27 ↗

(On Diff #226990)

Why is this only needed for apple?

123 ↗

(On Diff #226990)

Where does 50 come from? Maybe make this a macro.

152 ↗

(On Diff #226990)

Is this the same as while (__old == 0)?

[__simt__]

No problem. I just want to know what I need to do in the next patch in order to move forward.

libcxx/src/atomic.cpp

28 ↗

(On Diff #226990)

It's false on CUDA. It would be false on platforms that can't rely on OS support for efficient waiting and have to fall back to polling with backoff.

32 ↗

(On Diff #226990)

Prior to P0883 merging into C++20, atomics are constructed in an uninitialized state. You're supposed to use this macro to give it a static initialization. This macro is deprecated after C++20.

46 ↗

(On Diff #226990)

If you have a platform wait state, then it's used by this facility.

If you don't have a platform wait state, then a condvar is used instead.

129 ↗

(On Diff #226990)

Oh yes. Every time that there is a contending waiter concurrent with this notifier. This condition is true whenever the facility's use is not trivial.

133 ↗

(On Diff #226990)

Answered below.

139 ↗

(On Diff #226990)

Undefined behavior. Usually a segfault.

148 ↗

(On Diff #226990)

This is the uglier part of the patch. We have this situation where one platform (Apple) is about to go from not having platform wait states, to having them. This API is trying to be able to take either kind of efficient wait structure in the application OR in the dylib, and provide efficient waiting either way.

I think it would not be unreasonable if you guys asked me to cut this part out in order to get a first commit of the facility, and then work in the background with Louis on recovering the capability in some way, with or without a public patch.

162 ↗

(On Diff #226990)

Yes.

libcxx/src/barrier.cpp

44 ↗

(On Diff #226990)

This needs to be inside the loop unfortunately. During the first round, we need to record our effective start (leaf) location in the tree. I could express it differently - record it only at the end of the first round - but it would remain in the loop nest.

What we could potentially do is dumb down this favorite barrier index concept, or remove it entirely. It's worth a relatively small amount of performance by comparison to using the tree barrier in the first place.

I would not be offended if you asked me to give you an ordered list of things I could delete and tell you what it costs you to delete them, approximately. Then we could stop where we are more comfortable.

libcxx/src/semaphore.cpp

27 ↗

(On Diff #226990)

Because of how GCD semaphores work, unfortunately.

We could delete this by sending all Apple semaphores to the generic template based on atomics.

Last I spoke with Louis, we thought that would be acceptable.

123 ↗

(On Diff #226990)

Yeah. Aren't there enough macros though? I think I might come back later with a different patch to propose a set of macros to configure back-offs.

152 ↗

(On Diff #226990)

It's not. This is masking the lower 32-bits of a 64-bit value, and then comparing that with 0.

[zoecarver]

libcxx/src/atomic.cpp

32 ↗

(On Diff #226990)

Heh. I didn't realize that was part of the standard (I was wondering why it wasn't mangled). Good to know.

46 ↗

(On Diff #226990)

I see. I got confused for a second while trying to follow the #ifs.

139 ↗

(On Diff #226990)

Isn't that a problem if _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE isn't defined?

148 ↗

(On Diff #226990)

I'll defer to others on this but, (assuming it wouldn't be much more work for you) it might be better to remove that from this patch and add it as a follow-up patch.

In general, the less code in this patch, the faster it can get committed.

libcxx/src/barrier.cpp

44 ↗

(On Diff #226990)

What we could potentially do is dumb down this favorite barrier index concept, or remove it entirely. It's worth a relatively small amount of performance by comparison to using the tree barrier in the first place.

I don't know enough about this piece of code or potential methods of implementation to comment on what we should do. I'll defer to you/others on this.

libcxx/src/semaphore.cpp

123 ↗

(On Diff #226990)

Yes, there are an unfortunate number of macros in this bit of code.

I don't feel strongly about adding a macro now or later, maybe add a comment, though (that the number isn't magic or referenced elsewhere).

152 ↗

(On Diff #226990)

I'm pretty sure they are the same. Look at this example. The first and last functions generate the same optimized assembly.

[__simt__]

A lot of changes in this patch, mostly simplifications based on the areas that got feedback about complexity.

For the most part, I have deleted code:

1. I deleted the condvar-based implementation of atomic_wait because no current platform would make use of it. That also allowed me to delete much of the complicated ABI tricks added in the last revision. That removed several configuration macros.
2. After discussing it with Louis, I switched the Apple config to use atomics-based semaphores. Not only did that delete a lot of code on its own, but it made some other optimizations in semaphores no longer needed, so I deleted them too. That removed several more configuration macros as well.
3. I deleted code dealing with the thread_local optimization in barrier. Using this_thread::get::id to inject a thread-stable search seed for the algorithm is about just as good, and everything for that already exists.
4. Latches, barriers and semaphores make more direct use of the wait/notify functionality now. Where they had "exceptions" with customized waiting, now there's a unified interface there, which deletes code.

In addition to this, the internal abstractions are much better now. I particularly like how natively-supported Futex types pass-through the intermediate layer now, it just works.

I hope you find this version is close enough that we might soon switch to delta patches on top, in trunk.

Cheers,

Olivier

[zoecarver]

Not finished looking through this but, here are some comments.

Overall, I really like this change. It looks fantastic. It seems like a much cleaner/simpler implementation. Thanks for all the time you've spent on this.

libcxx/include/__threading_support

29 ↗

(On Diff #240389)

Are all the platforms we support guaranteed to have this header (they very well might, I just don't know)?

31 ↗

(On Diff #240389)

Is this macro still needed?

33 ↗

(On Diff #240389)

This could be an else block, no?

77 ↗

(On Diff #240389)

Are there any platforms where SEM_VALUE_MAX doesn't exist? Maybe some BSD platform? Could you check that it is defined (or maybe that we're on a certain platform)?

libcxx/include/atomic

2447 ↗

(On Diff #240389)

I might just be missing it but, is this in the standard? Otherwise, could you mangle it?

2448 ↗

(On Diff #240389)

nit: space between the equals.

libcxx/include/barrier

274 ↗

(On Diff #240389)

Will __barrier_base be defined if _LIBCPP_HAS_NO_TREE_BARRIER isn't?

libcxx/include/latch

53 ↗

(On Diff #240389)

Can we make it so that these headers just don't exist before C++11 via cmake? That might be a nicer way to fail.

[__simt__]

Thanks Zoe!

Some responses ->

libcxx/include/__threading_support

29 ↗

(On Diff #240389)

This header is part of Pthreads and this #include is in the Pthreads section of the header, so I think the answer is yes. The Apple case is special in that they have deprecated this header.

31 ↗

(On Diff #240389)

Yes. We need a way to disable the platform native semaphores. Both Apple (in the current design) and CUDA need it.

33 ↗

(On Diff #240389)

It would have to be an #elif !defined(...) so that CUDA could trigger it too.

77 ↗

(On Diff #240389)

Like the header, it's mandated by Pthreads. It's conceivable that some BSD is non-conforming and we still want to work on it, but I don't have a BSD system handy to try.

libcxx/include/atomic

2447 ↗

(On Diff #240389)

It is, in C++20.

2448 ↗

(On Diff #240389)

OK.

libcxx/include/barrier

274 ↗

(On Diff #240389)

Yes. The macro ends up selecting between two different base classes -- one is the scalable tree barrier, the other is the simpler central barrier.

libcxx/include/latch

53 ↗

(On Diff #240389)

I don't have this skill. :^/

But I do think that we want to support them in C++11/14/17. This author's production team is going to present it to users in these dialects, for instance.

[ldionne]

This is looking pretty good, only a few nitpicks. Once the nitpicks are addressed we can commit this and then go incrementally.

libcxx/include/__threading_support

34 ↗

(On Diff #240389)

Any reason to introduce this macro instead of just use !defined(_LIBCPP_NO_NATIVE_SEMAPHORES) when you need it?

513 ↗

(On Diff #240389)

static constexpr?

libcxx/include/atomic

550 ↗

(On Diff #240389)

Just wondering: will this in any way make it harder to support <atomic> in freestanding?

1465 ↗

(On Diff #240389)

I'm not seeing this used anywhere -- am I missing something?

libcxx/include/semaphore

61 ↗

(On Diff #240389)

Olivier and I spoke offline, and it's reasonable to request C++14 at least here. Please do this in all the headers you're adding.

The idea is to avoid having headers that are supported in older dialects than they need to be (within reason), which is often a source of technical debt.

libcxx/src/atomic.cpp

47 ↗

(On Diff #240389)

In apple_availability.h, add:

#if defined(__ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__)
#if __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ >= 101500
#define _LIBCPP_USE_ULOCK
#endif
#elif defined(__ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__)
#if __ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__ >= 130000
#define _LIBCPP_USE_ULOCK
#endif
#elif defined(__ENVIRONMENT_TV_OS_VERSION_MIN_REQUIRED__)
#if __ENVIRONMENT_TV_OS_VERSION_MIN_REQUIRED__ >= 130000
#define _LIBCPP_USE_ULOCK
#endif
#elif defined(__ENVIRONMENT_WATCH_OS_VERSION_MIN_REQUIRED__)
#if __ENVIRONMENT_WATCH_OS_VERSION_MIN_REQUIRED__ >= 60000
#define _LIBCPP_USE_ULOCK
#endif
#endif // __ENVIRONMENT_.*_VERSION_MIN_REQUIRED__

That should do it for all platforms aligned to Mac OS 10.15. Feel free to use whatever name for _LIBCPP_USE_ULOCK -- _LIBCPP_USE_APPLE_ULOCK probably makes the most sense since it's an Apple-specific API.

Then, your #elif becomes #elif defined(__APPLE__) && defined(_LIBCPP_USE_APPLE_ULOCK).

[__simt__]

Replies. Also noting that I will include an update to the implementation status HTML page.

libcxx/include/__threading_support

34 ↗

(On Diff #240389)

I was going to say it’s more convenient for me, but I’m not even convinced.

I can streamline this.

513 ↗

(On Diff #240389)

Yes.

libcxx/include/atomic

550 ↗

(On Diff #240389)

A bit, yeah. There are a few ways to proceed.

1465 ↗

(On Diff #240389)

I intend to use that to implement the normative encouragement that atomic_signed/unsigned[...]_t should be the efficient ones for waiting. I added those types below, but they don’t follow that encouragement.

libcxx/include/semaphore

61 ↗

(On Diff #240389)

Yep

libcxx/src/atomic.cpp

47 ↗

(On Diff #240389)

Thanks!

[__simt__]

This revision addresses the outstanding comments, and incorporates Louis' recommended macros for ulock detection.

I also added missing max() members to barrier/latch that were added by NB comment resolution, and I implemented the normative encouragement for the lock-free types to match the ideal contention type, if there is one. I added tests for these things.

Finally, I further improved the ABI resilience of the barrier type so it's almost a full pimpl now.

[ldionne]

Thanks a lot for all the work and patience, Olivier. I think we're good to go now. Do you have commit access?

Also, can you please confirm that you meant to introduce all the following new symbols in the dylib, and nothing else:

std::__1::__libcpp_atomic_wait(std::__1::__cxx_atomic_impl<long long, std::__1::__cxx_atomic_base_impl<long long> > const volatile*, long long)
std::__1::__libcpp_atomic_wait(void const volatile*, long long)
std::__1::__cxx_atomic_notify_all(std::__1::__cxx_atomic_impl<long long, std::__1::__cxx_atomic_base_impl<long long> > const volatile*)
std::__1::__cxx_atomic_notify_all(void const volatile*)
std::__1::__cxx_atomic_notify_one(std::__1::__cxx_atomic_impl<long long, std::__1::__cxx_atomic_base_impl<long long> > const volatile*)
std::__1::__cxx_atomic_notify_one(void const volatile*)
std::__1::__libcpp_atomic_monitor(std::__1::__cxx_atomic_impl<long long, std::__1::__cxx_atomic_base_impl<long long> > const volatile*)
std::__1::__libcpp_atomic_monitor(void const volatile*)
std::__1::__arrive_barrier_algorithm_base(std::__1::__barrier_algorithm_base*, unsigned char)
std::__1::__destroy_barrier_algorithm_base(std::__1::__barrier_algorithm_base*)
std::__1::__construct_barrier_algorithm_base(long&)

Those will have to be added to the ABI list file (I can do that).

[ldionne]

libcxx/include/atomic

443 ↗

(On Diff #246218)

We forgot to update the synopsis for this header with the C++20 Synchronization Library. @__simt__ would you be willing to do that in a followup change?

[teemperor]

libcxx/include/module.modulemap

234 ↗

(On Diff #246218)

Maybe I'm missing something here, but due to this submodule we are always parsing the barrier header even when building the module with a language standard < C++14. This means that everyone using C++11 is no longer able to use the 'std' Clang module after this commit. Is this intentional?

[ldionne]

libcxx/include/module.modulemap

234 ↗

(On Diff #246218)

No, this is not intentional. Sorry, there were several failures that needed fixing after committing this (failures that were impossible to notice without throwing the change at all the build bots) -- we're getting there.

[davide]

This is the second time something like this happened. When you make such large scale changes -- make sure to run the lldb testsuite, or be ready to revert. We already had this discussion in the past, but clearly it didn't prevent the problem from happening again.

[teemperor]

libcxx/include/module.modulemap

234 ↗

(On Diff #246218)

No worries, pushed a fix in b61e83eb0e31c1e6006569b43bb98a61ff44ca4c

[ldionne]

In D68480#1889799, @davide wrote:

This is the second time something like this happened. When you make such large scale changes -- make sure to run the lldb testsuite, or be ready to revert. We already had this discussion in the past, but clearly it didn't prevent the problem from happening again.

Last time's discussion didn't get anywhere, as running the LLDB test suite on each commit we make to libc++ isn't a viable option.

Libc++'s test matrix is insanely large, and actually we can't even see all of it cause some uses are behind closed doors. Whenever we make a non-trivial change (and BTW this is a purely additive change), it breaks someone somewhere. And you can rest assured that we do run a lot of testing locally to make sure we don't break people before committing, but it can't catch everything. That's just the way it is, and we try to fix it as quickly as possible -- I've spent all day so far trying to fix the consequences of applying this patch. This is not a lack of diligence, it's just that the nature of libc++ makes it difficult to test comprehensively.

I don't know what this commit broke in LLDB, if anything, but instead it's more useful to comment here with a link to the failure so we can help fix it. Being combative is no help, as we're all in the same boat.

[davide]

In D68480#1889935, @ldionne wrote:

In D68480#1889799, @davide wrote:

This is the second time something like this happened. When you make such large scale changes -- make sure to run the lldb testsuite, or be ready to revert. We already had this discussion in the past, but clearly it didn't prevent the problem from happening again.

Last time's discussion didn't get anywhere, as running the LLDB test suite on each commit we make to libc++ isn't a viable option.

Libc++'s test matrix is insanely large, and actually we can't even see all of it cause some uses are behind closed doors. Whenever we make a non-trivial change (and BTW this is a purely additive change), it breaks someone somewhere. And you can rest assured that we do run a lot of testing locally to make sure we don't break people before committing, but it can't catch everything. That's just the way it is, and we try to fix it as quickly as possible -- I've spent all day so far trying to fix the consequences of applying this patch. This is not a lack of diligence, it's just that the nature of libc++ makes it difficult to test comprehensively.

I don't know what this commit broke in LLDB, if anything, but instead it's more useful to comment here with a link to the failure so we can help fix it. Being combative is no help, as we're all in the same boat.

I would like to reiterate that the policy in LLVM is that commit that break projects can be reverted willy-nilly.
I would also like to stress that my use cases are not behind closed doors -- LLDB is part of the LLVM umbrella.
I thought we reached an agreement last time, but looks like there was a miscommunication or misunderstanding on your side, so let me reiterate that you have two options:

1. Run the lldb testsuite for changes that impact layout of structures -- or in any case you consider non-trivial, or if you don't think you can do this, at least ping somebody from lldb to take a look at the changes before they're committed. This of course requires some judgement on your side. When in doubt ask, as sending an e-mail is cheap.
2. You commit without pre-commit checking lldb because you consider the additive cost of running ninja check-lldb is prohibitive. This is your choice, but don't be surprised if people will revert your commit if it breaks things.

Hopefully this clarifies my position.

[mstorsjo]

FWIW, this change broke building for windows. It seemed fairly straightforward to fix though, see D75102.

[leonardchan]

Hi, a bisect shows that this patch seems to cause time.h to not be found for us:

[1958/45287] CXX kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o
FAILED: kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o
../../../recipe_cleanup/clangEPCywe/bin/clang++ -MD -MF kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o.d -o kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o -DTOOLCHAIN_VERSION=/b/s/w/ir/k/recipe_cleanup/clangEPCywe/bin -DZX_ASSERT_LEVEL=2 -DWITH_FRAME_POINTERS=1 -D_LIBCPP_ENABLE_THREAD_SAFETY_ANNOTATIONS=1 -D_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS -DKERNEL_BASE=0xffffffff80100000 -DSMP_MAX_CPUS=32 -D_KERNEL -DLK -DENABLE_PANIC_SHELL -DWITH_DEBUG_LINEBUFFER -DZIRCON_TOOLCHAIN -DLK_DEBUGLEVEL=2 -DWITH_KERNEL_PCIE -DKERNEL_RETPOLINE=1 -DWITH_UNIFIED_SCHEDULER=1 -DSCHEDULER_TRACING_LEVEL=0 -DARCH_X86 -DKERNEL_LOAD_OFFSET=0x00100000 -D_LIBCPP_DISABLE_EXTERN_TEMPLATE -I../../zircon/kernel/include -I../../zircon/kernel/lib/libc/include -I../../zircon/kernel/lib/ktl/include -I../../zircon/kernel/lib/io/include -I../../zircon/kernel/lib/heap/include -I../../zircon/system/ulib/lazy_init/include -I../../zircon/system/ulib/lockdep/include -I../../zircon/system/ulib/ffl/include -I../../zircon/kernel/vm/include -I../../zircon/kernel/lib/user_copy/include -I../../zircon/system/ulib/zircon-internal/include -I../../zircon/kernel/lib/ktrace/include -I../../zircon/system/ulib/fbl/include -I../../zircon/kernel/lib/fbl/include -I../../zircon/system/public -I../../zircon/kernel/arch/x86/include -I../../zircon/system/ulib/bitmap/include -I../../zircon/kernel/arch/x86/page_tables/include -I../../zircon/system/ulib/hwreg/include -I../../zircon/kernel/lib/heap/include -I../../zircon/kernel/lib/io/include -I../../zircon/kernel/lib/ktl/include -idirafter ../../zircon/kernel/lib/libc/limits-dummy -fno-common --target=x86_64-fuchsia -mcx16 -march=x86-64 -fcrash-diagnostics-dir=clang-crashreports -fcolor-diagnostics -ffile-prefix-map=/b/s/w/ir/k/fuchsia/out/default.zircon=. -ffile-prefix-map=/b/s/w/ir/k/fuchsia/out=.. -ffile-prefix-map=/b/s/w/ir/k/fuchsia=../.. -no-canonical-prefixes -O2 -g3 -Wall -Wextra -Wno-unused-parameter -Wno-address-of-packed-member -Wnewline-eof -Wno-unknown-warning-option -Wno-c99-designator -Wno-int-in-bool-context -Wno-range-loop-analysis -fno-omit-frame-pointer -ffunction-sections -fdata-sections -Wthread-safety -Wimplicit-fallthrough -fvisibility=hidden -ftrivial-auto-var-init=pattern -Werror -Wno-error=deprecated-declarations -fpie -mretpoline -mretpoline-external-thunk -ffreestanding -include ../../zircon/kernel/include/hidden.h -fno-unwind-tables -mno-red-zone -Wformat=2 -Wvla -mno-red-zone -msoft-float -mno-mmx -mno-sse -mno-sse2 -mno-3dnow -mno-avx -mno-avx2 -mcmodel=kernel -fdata-sections -Wno-gnu-string-literal-operator-template -std=c++17 -Wconversion -Wno-sign-conversion -Wextra-semi -Wno-deprecated-copy -Wno-non-c-typedef-for-linkage -ftemplate-backtrace-limit=0 -fno-exceptions -fno-rtti -fno-threadsafe-statics -fvisibility-inlines-hidden -faligned-new=8 -fno-exceptions -c ../../zircon/kernel/lib/libc/snprintf.cc
In file included from ../../zircon/kernel/lib/libc/snprintf.cc:10:
In file included from ../../zircon/kernel/lib/ktl/include/ktl/algorithm.h:10:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/algorithm:643:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/memory:666:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/atomic:550:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/__threading_support:14:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/chrono:827:
../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/ctime:49:10: fatal error: 'time.h' file not found
#include <time.h>

Do you know if this is a known or unintended side effect of this patch? I don't think we changed anything on our side that would've caused this.

Builder: https://ci.chromium.org/p/fuchsia/builders/ci/clang_toolchain.fuchsia-x64-debug-subbuild/b8887404211928925456?

[ldionne]

In D68480#1893953, @leonardchan wrote:

Hi, a bisect shows that this patch seems to cause time.h to not be found for us:
[...]

Do you know if this is a known or unintended side effect of this patch? I don't think we changed anything on our side that would've caused this.

This must be cause we're now including <chrono> in <atomic>. This is not really something we can (or want to) workaround, since that's in the spec. Are you folks using some fancy C library that doesn't provide <time.h>? If so, I would argue that the fact it worked before this patch is just a coincidence.

[jfb]

In D68480#1893953, @leonardchan wrote:

Hi, a bisect shows that this patch seems to cause time.h to not be found for us:

[1958/45287] CXX kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o
FAILED: kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o
../../../recipe_cleanup/clangEPCywe/bin/clang++ -MD -MF kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o.d -o kernel-x64-clang/obj/kernel/lib/libc/libc.snprintf.cc.o -DTOOLCHAIN_VERSION=/b/s/w/ir/k/recipe_cleanup/clangEPCywe/bin -DZX_ASSERT_LEVEL=2 -DWITH_FRAME_POINTERS=1 -D_LIBCPP_ENABLE_THREAD_SAFETY_ANNOTATIONS=1 -D_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS -DKERNEL_BASE=0xffffffff80100000 -DSMP_MAX_CPUS=32 -D_KERNEL -DLK -DENABLE_PANIC_SHELL -DWITH_DEBUG_LINEBUFFER -DZIRCON_TOOLCHAIN -DLK_DEBUGLEVEL=2 -DWITH_KERNEL_PCIE -DKERNEL_RETPOLINE=1 -DWITH_UNIFIED_SCHEDULER=1 -DSCHEDULER_TRACING_LEVEL=0 -DARCH_X86 -DKERNEL_LOAD_OFFSET=0x00100000 -D_LIBCPP_DISABLE_EXTERN_TEMPLATE -I../../zircon/kernel/include -I../../zircon/kernel/lib/libc/include -I../../zircon/kernel/lib/ktl/include -I../../zircon/kernel/lib/io/include -I../../zircon/kernel/lib/heap/include -I../../zircon/system/ulib/lazy_init/include -I../../zircon/system/ulib/lockdep/include -I../../zircon/system/ulib/ffl/include -I../../zircon/kernel/vm/include -I../../zircon/kernel/lib/user_copy/include -I../../zircon/system/ulib/zircon-internal/include -I../../zircon/kernel/lib/ktrace/include -I../../zircon/system/ulib/fbl/include -I../../zircon/kernel/lib/fbl/include -I../../zircon/system/public -I../../zircon/kernel/arch/x86/include -I../../zircon/system/ulib/bitmap/include -I../../zircon/kernel/arch/x86/page_tables/include -I../../zircon/system/ulib/hwreg/include -I../../zircon/kernel/lib/heap/include -I../../zircon/kernel/lib/io/include -I../../zircon/kernel/lib/ktl/include -idirafter ../../zircon/kernel/lib/libc/limits-dummy -fno-common --target=x86_64-fuchsia -mcx16 -march=x86-64 -fcrash-diagnostics-dir=clang-crashreports -fcolor-diagnostics -ffile-prefix-map=/b/s/w/ir/k/fuchsia/out/default.zircon=. -ffile-prefix-map=/b/s/w/ir/k/fuchsia/out=.. -ffile-prefix-map=/b/s/w/ir/k/fuchsia=../.. -no-canonical-prefixes -O2 -g3 -Wall -Wextra -Wno-unused-parameter -Wno-address-of-packed-member -Wnewline-eof -Wno-unknown-warning-option -Wno-c99-designator -Wno-int-in-bool-context -Wno-range-loop-analysis -fno-omit-frame-pointer -ffunction-sections -fdata-sections -Wthread-safety -Wimplicit-fallthrough -fvisibility=hidden -ftrivial-auto-var-init=pattern -Werror -Wno-error=deprecated-declarations -fpie -mretpoline -mretpoline-external-thunk -ffreestanding -include ../../zircon/kernel/include/hidden.h -fno-unwind-tables -mno-red-zone -Wformat=2 -Wvla -mno-red-zone -msoft-float -mno-mmx -mno-sse -mno-sse2 -mno-3dnow -mno-avx -mno-avx2 -mcmodel=kernel -fdata-sections -Wno-gnu-string-literal-operator-template -std=c++17 -Wconversion -Wno-sign-conversion -Wextra-semi -Wno-deprecated-copy -Wno-non-c-typedef-for-linkage -ftemplate-backtrace-limit=0 -fno-exceptions -fno-rtti -fno-threadsafe-statics -fvisibility-inlines-hidden -faligned-new=8 -fno-exceptions -c ../../zircon/kernel/lib/libc/snprintf.cc
In file included from ../../zircon/kernel/lib/libc/snprintf.cc:10:
In file included from ../../zircon/kernel/lib/ktl/include/ktl/algorithm.h:10:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/algorithm:643:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/memory:666:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/atomic:550:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/__threading_support:14:
In file included from ../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/chrono:827:
../../../recipe_cleanup/clangEPCywe/bin/../include/c++/v1/ctime:49:10: fatal error: 'time.h' file not found
#include <time.h>

Do you know if this is a known or unintended side effect of this patch? I don't think we changed anything on our side that would've caused this.

Builder: https://ci.chromium.org/p/fuchsia/builders/ci/clang_toolchain.fuchsia-x64-debug-subbuild/b8887404211928925456?

Is zircon freestanding, and not providing chrono (which then includes time.h)? That would explain the issue, we'd need to fix freestanding atomic by not exposing time-related stuff if time.h ins't available.

[ldionne]

In D68480#1893987, @jfb wrote:

In D68480#1893953, @leonardchan wrote:

Hi, a bisect shows that this patch seems to cause time.h to not be found for us:

[...]

Do you know if this is a known or unintended side effect of this patch? I don't think we changed anything on our side that would've caused this.

Builder: https://ci.chromium.org/p/fuchsia/builders/ci/clang_toolchain.fuchsia-x64-debug-subbuild/b8887404211928925456?

Is zircon freestanding, and not providing chrono (which then includes time.h)? That would explain the issue, we'd need to fix freestanding atomic by not exposing time-related stuff if time.h ins't available.

So, actually, I think we need to have a discussion about the support of Freestanding in libc++. We should either implement it properly and have testers for it, or stop pretending that we do. Right now all I see us doing is adding complexity to our code to fix stuff that breaks on user configurations we don't know about, understand or test. As someone who has to maintain the code with that complexity, this concerns me.

And I do care about Freestanding -- I think it's important and we should support it. But I also think that we should not do it halfway like right now. In the current state of things, I literally have no way to ensure that we won't break that configuration again tomorrow. @leonardchan @phosek Is there a way that you could add a libc++ builder that runs freestanding?

[jfb]

In D68480#1894037, @ldionne wrote:

In D68480#1893987, @jfb wrote:

In D68480#1893953, @leonardchan wrote:

Hi, a bisect shows that this patch seems to cause time.h to not be found for us:

[...]

Do you know if this is a known or unintended side effect of this patch? I don't think we changed anything on our side that would've caused this.

Builder: https://ci.chromium.org/p/fuchsia/builders/ci/clang_toolchain.fuchsia-x64-debug-subbuild/b8887404211928925456?

Is zircon freestanding, and not providing chrono (which then includes time.h)? That would explain the issue, we'd need to fix freestanding atomic by not exposing time-related stuff if time.h ins't available.

So, actually, I think we need to have a discussion about the support of Freestanding in libc++. We should either implement it properly and have testers for it, or stop pretending that we do. Right now all I see us doing is adding complexity to our code to fix stuff that breaks on user configurations we don't know about, understand or test. As someone who has to maintain the code with that complexity, this concerns me.

And I do care about Freestanding -- I think it's important and we should support it. But I also think that we should not do it halfway like right now. In the current state of things, I literally have no way to ensure that we won't break that configuration again tomorrow. @leonardchan @phosek Is there a way that you could add a libc++ builder that runs freestanding?

Agreed, it seems like we want to figure out what individual freestanding subsets can "carve out" of regular C++, and how to do so cleanly. "time" seems like an easy thing to carve out, but it shouldn't just be done here, it should be part of the configuration header, applied consistently through libc++, and extensively tested. Ideally it wouldn't just be a builder: you'd have a directory which tests freestanding configuration options (i.e. "can I include atomic without time support?").

[leonardchan]

@leonardchan @phosek Is there a way that you could add a libc++ builder that runs freestanding?

We have it as a TODO but can bump it in priority.

Agreed, it seems like we want to figure out what individual freestanding subsets can "carve out" of regular C++, and how to do so cleanly. "time" seems like an easy thing to carve out, but it shouldn't just be done here, it should be part of the configuration header, applied consistently through libc++, and extensively tested. Ideally it wouldn't just be a builder: you'd have a directory which tests freestanding configuration options (i.e. "can I include atomic without time support?").

How simple would it be to carve specifically time.h out? I'm unfamiliar with libcxx internals + configurations. I'm also not insisting that progress on this patch be halted, but I'd like to know if there's anything we could do at least now to provide a workaround for freestanding targets,

[jfb]

In D68480#1894192, @leonardchan wrote:

@leonardchan @phosek Is there a way that you could add a libc++ builder that runs freestanding?

We have it as a TODO but can bump it in priority.

Agreed, it seems like we want to figure out what individual freestanding subsets can "carve out" of regular C++, and how to do so cleanly. "time" seems like an easy thing to carve out, but it shouldn't just be done here, it should be part of the configuration header, applied consistently through libc++, and extensively tested. Ideally it wouldn't just be a builder: you'd have a directory which tests freestanding configuration options (i.e. "can I include atomic without time support?").

How simple would it be to carve specifically time.h out? I'm unfamiliar with libcxx internals + configurations. I'm also not insisting that progress on this patch be halted, but I'd like to know if there's anything we could do at least now to provide a workaround for freestanding targets,

As a non-libc++ maintainer (so take what I say with some doubt), I'd imagine things being detected in libcxx/include/__config, say through __has_include(time.h), and then you'd have a macro which says "no time". I'd then figure out the transitive inclusions of time.h in all libc++ headers, figure out want pulls them it, and use the macro to not expose the corresponding functions / types on those platforms.

You'd then need a decent amount of testing to make sure this works well.

Concretely here, there are a few atomic functions which require chrono, so you'd want to conditionally include chrono and conditionally define those functions. I think the patch which does this should also handle time in other libc++ headers, so we're not in a situation of "we kinda support having no time.h, but not consistently".

[ldionne]

libcxx/include/atomic

443 ↗

(On Diff #246218)

Ping @__simt__

[__simt__]

libcxx/include/atomic

443 ↗

(On Diff #246218)

Yep. Thanks for the ping.

[theraven]

This appears to have baked in some ABI details that don't permit efficient implementation on some of our supported platforms. In the future, please can you post an RFC from things that need to integrate with platform-specific code? We're now stuck with this interface until we are willing to do an ABI-breaking change. In particular:

• OpenBSD provides a Linux-compatible futex that requires a 32-bit integer to be used as the key. This can't be used with the existing ABI, which has baked in 64-bit integers as the size for OpenBSD.
• FreeBSD's _umtx_op uses long and so is able to support the ABI on 64-bit platforms (LP64) but not on 32-bit ones.
• Windows' WaitOnAddress supports 1, 2, 4, and 8-byte objects, yet can be used only with 8-byte objects in this interface.
• The semaphore interface does not require exposing the underlying semaphore type, so could have been implemented directly with _umtx_op on FreeBSD, rather than with the wrapper. A binary semaphore is trivial to implement with a futex with the fast path in the uncontended case a single inline atomic op. This is not possible without breaking the ABI in the current design.

The atomic wait / wake problems could have been addressed by making the size an explicit argument, rather than relying on overload resolution. The semaphore issue could have been addressed by asking for contributions to the __threading_support bits before a release was cut.

[ldionne]

In D68480#3179355, @theraven wrote:

This appears to have baked in some ABI details that don't permit efficient implementation on some of our supported platforms.

This is unfortunate. Have you folks shipped this yet? Perhaps it's not too late to fix things now if you've only released it very recently.

In the future, please can you post an RFC from things that need to integrate with platform-specific code? We're now stuck with this interface until we are willing to do an ABI-breaking change.

With all due respect, I consider that the responsibility is yours. In May 2019, Olivier started a thread where he was gathering feedback on what was to become the synchronization library: https://lists.llvm.org/pipermail/libcxx-dev/2019-May/000396.html. The thread got very little traction (see the June 2019 archive for the only few replies). Then, this patch was created and it was under review for roughly 6 months. Anyone paying attention to libc++ development could have seen this go by.

The reality is that if you ship libc++ on your platform, you should have someone caring about libc++ development to ensure it plays well with your platform. There are so many people using libc++ in various ways (vendors and others) that it's difficult for the core contributors to make sure that everybody "gets the memo" whenever we do something. Don't get me wrong, I very often go out of my way to ensure that vendors get notified when we make potentially contentious changes (I often ping a bunch of people that I know vend the library). However, all of that is based on basically me knowing (or thinking I know) who vends the library for what platform. None of it is really formalized, and misses can and do happen.

Furthermore, I would like to point out that libc++ goes out of its way to ensure that these sorts of things don't happen. We have availability annotations, for example, that allow vendors to control when users are able to start relying on features. In this case, I used those annotations for solving exactly the problem you encountered: I ensured that users were not going to start relying on the synchronization library on Apple platforms until we could confirm it was ABI stable, and I only flipped the switch one year after it had been implemented (see D96790). I've set things up so that any vendor could take advantage of those (they were previously Apple-specific), and I've always been surprised that no other vendors cared enough about QoI on their platforms to start using that infrastructure. If you're not using the tools provided to control what you ship on your platform, you can't expect someone who might not even know your existence to do it for you.

I would also like to point out that more than one year after pre-commit CI has been set up, we still don't have a FreeBSD and OpenBSD bots in BuildKite. Technically, that makes those two platforms unsupported. They are important platforms and we definitely want to support them, but we need a bit more energy from the vendor side here. Not very much, just a bit.

So, concretely, here are some action items for OpenBSD and FreeBSD vendors to become a well-behaved citizen and make sure such issues don't happen again in the future:

1. Please set up BuildKite bots for OpenBSD and FreeBSD. I'll help you do it, it's easy. Then, we'll officially support those platforms and document it in our documentation.
2. If you vend libc++, please add yourself to this Herald group: https://reviews.llvm.org/project/view/109/. I created that group recently so I could formalize the notion of "begin a libc++ vendor" and make it easier to ping everybody.
3. Please have someone subscribe to libcxx-commits or use some Herald rules to be notified about reviews. This should ensure that, even if we don't ping the vendor group, there's some chance that you folks will see it. You don't have to engage in reviews or anything, but even just reviewing the subject lines once per week should be enough to ensure things like this don't happen again. That seems like a reasonable investment for an organization that ships libc++ on their platform.
4. Setup availability annotations for your platform. See libcxx/include/__availability for details.

Now, concretely, please let me know if you think it's feasible to fix this now that you've shipped it. If so, we can work together on that. Otherwise, I'm sorry this happened, and the steps above should ensure it doesn't again.

[theraven]

In D68480#3179526, @ldionne wrote:

In D68480#3179355, @theraven wrote:

This appears to have baked in some ABI details that don't permit efficient implementation on some of our supported platforms.

This is unfortunate. Have you folks shipped this yet? Perhaps it's not too late to fix things now if you've only released it very recently.

I am not sure who you mean when you say 'you' here. I am writing this as:

• A member of the LLVM project and libc++ contributor
• A libc++ consumer.

Since Howard's initial commit, libc++ has had strong ABI backwards compatibility guarantees for anything outside of the experimental namespace. Any time we define an interface between the library and the headers, that is an ABI that we need to support in the long term.

I came to this particular patch because one of my colleagues pointed me at atomic_wait as a possible replacement for platform-specific wrappers around futex-like abstractions in our code. I then tried to add FreeBSD and Windows support (the two platforms I care about for our code that do not have platform-specific code paths in libc++) and discovered that the ABI that we have committed to supporting cannot be implemented *at all* on 32-bit architectures with FreeBSD and cannot expose all of the functionality on Windows.

This is because this patch set decided to add a new pattern, rather than copying the same approach that every other atomic op uses: provide _1, _2, _4, _8, _16 and _n implementations. This also means that if Linux adds a futex64 system call (which I consider fairly probable, given that it is painful on Linux that you can't use a futex with pointers currently) then we can't take advantage of it without an ABI break.

In the future, please can you post an RFC from things that need to integrate with platform-specific code? We're now stuck with this interface until we are willing to do an ABI-breaking change.

With all due respect, I consider that the responsibility is yours. In May 2019, Olivier started a thread where he was gathering feedback on what was to become the synchronization library: https://lists.llvm.org/pipermail/libcxx-dev/2019-May/000396.html. The thread got very little traction (see the June 2019 archive for the only few replies). Then, this patch was created and it was under review for roughly 6 months. Anyone paying attention to libc++ development could have seen this go by.

The subject of that thread does not in any way mention that this requires platform-specific logic. Putting 'platform-specific futex-like' or similar in the subject would have made people pay attention. No one was tagged as a reviewer here to request perspectives from other platforms (dim or joerg, for example). It is the responsibility of the committer to ensure that a patch has adequate reviews. This did not happen here and we are now stuck with this ABI. I don't know how we can fix this, without adding a new version in the __2 namespace and eventually having a SONAME bump.

[ldionne]

In D68480#3216178, @theraven wrote:

In D68480#3179526, @ldionne wrote:

In D68480#3179355, @theraven wrote:

This appears to have baked in some ABI details that don't permit efficient implementation on some of our supported platforms.

This is unfortunate. Have you folks shipped this yet? Perhaps it's not too late to fix things now if you've only released it very recently.

I am not sure who you mean when you say 'you' here. I am writing this as:

• A member of the LLVM project and libc++ contributor
• A libc++ consumer.

Right, "you" might not be the appropriate target here, I was thinking about whoever vends libc++ on FreeBSD (I wrongly assumed you were working for that vendor). My point is that nobody cares about ABI breaks for a platform unless the library is vended on that platform, in which case that vendor is the one who cares about ABI stability. In this case, that vendor is FreeBSD, and I consider that whoever vends libc++ on FreeBSD unfortunately missed the boat on this review. In FreeBSD's defence, it's true that we were not as well organized as we are now when we shipped this patch -- we now have a more detailed support policy and ties between various vendors and developers are somewhat clearer.

I will argue that breaking this ABI on Windows is not a big deal since nobody's vending libc++ on Windows. Or at least if they do, they are completely invisible to us ("us" being the people who develop libc++).

Since Howard's initial commit, libc++ has had strong ABI backwards compatibility guarantees for anything outside of the experimental namespace. Any time we define an interface between the library and the headers, that is an ABI that we need to support in the long term.

While I agree to some extent, I think it is important to highlight that ABI stability is not a property of the library itself, but a property of a specific vended instance of the library. For example, Chrome uses libc++, but they don't care about ABI stability because they link it statically. So we provide them with knobs to change libc++ behavior in various ways that are not ABI stable. On the other hand, some vendors like Apple do care about ABI stability for various reasons, and those vendors ensure that the ABI isn't broken on their platform, with the flavor of libc++ that they ship. And similarly, libc++ provides various knobs to help these vendors NOT break the ABI on their platforms.

In other words, over time, libc++ has grown from "ABI stability at all costs" to "providing tools to tweak it the way you want and be ABI stable if you want, but ABI unstable if you don't". That was the response we came up with because different consumers have different use cases for the library.

Where I'm going with this is that when Olivier created this review, I saw it had ABI implications and did what I needed to do for the vendor I represent. In the presence of a vast number of consumers of libc++, it's impossible for Olivier, or I, or any individual, to know about all the consumers that might not like the specific ABI that was selected. It might be obvious to you cause you've looked into it, but in the general case, the responsibility is on the vendors of the library to be at least a bit aware of what's going on and make sure they know what they are shipping on their platform. Cause that's the root cause of the issue -- this sub-optimal ABI was shipped on FreeBSD (hence locking them into it) without FreeBSD even knowing about it. That's really unfortunate, but like I said, libc++ provides ways to help vendors control what they ship on their platform, and they need only minimal involvement for this to happen. For instance, I would really welcome FreeBSD (and other vendors) taking advantage of the availability annotations I maintain. If FreeBSD had used those, it might have given some indication that FreeBSD might not want to ship those new symbols immediately.

I came to this particular patch because one of my colleagues pointed me at atomic_wait as a possible replacement for platform-specific wrappers around futex-like abstractions in our code. I then tried to add FreeBSD and Windows support (the two platforms I care about for our code that do not have platform-specific code paths in libc++) and discovered that the ABI that we have committed to supporting cannot be implemented *at all* on 32-bit architectures with FreeBSD and cannot expose all of the functionality on Windows.

Would you be willing to open a patch showing what changes are necessary for each of those? I think we can totally break the ABI on Windows since nobody's shipping it. And on 32-bit FreeBSD, if things don't work at all right now, then we can also "break the ABI" on that configuration since nobody can be depending on something that doesn't work. Perhaps things are not as bad as they seem?

Also, on a different note: I'm pretty serious about FreeBSD needing to implement pre-commit CI if it wants to be supported officially. It's a small investment, but it needs to happen for libc++ to keep FreeBSD as part of its list of supported platforms. @dim can you help with this?

[mstorsjo]

In D68480#3218277, @ldionne wrote:

I will argue that breaking this ABI on Windows is not a big deal since nobody's vending libc++ on Windows. Or at least if they do, they are completely invisible to us ("us" being the people who develop libc++).

Would you be willing to open a patch showing what changes are necessary for each of those? I think we can totally break the ABI on Windows since nobody's shipping it.

I would like to add some nuance to these statements here.

I do ship shared linked libc++ on Windows (as part of the llvm-mingw toolchain distribution), but without any strong ABI guarantees. Ideally ABI wouldn't break between releases, but if it does (especially in a fringe area) it's probably tolerable.

MSYS2 also ships an environment where libc++ is the standard system C++ library, linked shared. That environment is considered somewhat experimental afaik (CC @mati865), so if it breaks some package (which can be fixed by rebuilding), I think they'd consider it tolerable. If none of their packages actually have ended up using and depending on the aspects that may change (I haven't followed closely exactly how widespread it is), the ABI break should be totally transparent though.

[dim]

In D68480#3218277, @ldionne wrote:

Also, on a different note: I'm pretty serious about FreeBSD needing to implement pre-commit CI if it wants to be supported officially. It's a small investment, but it needs to happen for libc++ to keep FreeBSD as part of its list of supported platforms. @dim can you help with this?

I'm a FreeBSD committer but I don't have the access to setup e.g. bots on FreeBSD infrastructure. I hope @emaste can assist with this, as a FreeBSD Foundation member; I have discussed it with him before, and he seemed to be willing but probably runs out of time all the time... :)

[mati865]

In D68480#3218341, @mstorsjo wrote:

In D68480#3218277, @ldionne wrote:

I will argue that breaking this ABI on Windows is not a big deal since nobody's vending libc++ on Windows. Or at least if they do, they are completely invisible to us ("us" being the people who develop libc++).

Would you be willing to open a patch showing what changes are necessary for each of those? I think we can totally break the ABI on Windows since nobody's shipping it.

I would like to add some nuance to these statements here.

I do ship shared linked libc++ on Windows (as part of the llvm-mingw toolchain distribution), but without any strong ABI guarantees. Ideally ABI wouldn't break between releases, but if it does (especially in a fringe area) it's probably tolerable.

MSYS2 also ships an environment where libc++ is the standard system C++ library, linked shared. That environment is considered somewhat experimental afaik (CC @mati865), so if it breaks some package (which can be fixed by rebuilding), I think they'd consider it tolerable. If none of their packages actually have ended up using and depending on the aspects that may change (I haven't followed closely exactly how widespread it is), the ABI break should be totally transparent though.

Thanks for pinging me.
Actually I'd not consider it that much experimental now, it's available by default using pacman, it's mentioned on the website and people are interested in it.
Personally I won't hold back small breakage when it's justified (like here). Ping about such change welcome though so we can better prepare for it.

[ldionne]

In D68480#3218341, @mstorsjo wrote:

In D68480#3218277, @ldionne wrote:

I will argue that breaking this ABI on Windows is not a big deal since nobody's vending libc++ on Windows. Or at least if they do, they are completely invisible to us ("us" being the people who develop libc++).

Would you be willing to open a patch showing what changes are necessary for each of those? I think we can totally break the ABI on Windows since nobody's shipping it.

I would like to add some nuance to these statements here.

I do ship shared linked libc++ on Windows (as part of the llvm-mingw toolchain distribution), but without any strong ABI guarantees. Ideally ABI wouldn't break between releases, but if it does (especially in a fringe area) it's probably tolerable.

MSYS2 also ships an environment where libc++ is the standard system C++ library, linked shared. That environment is considered somewhat experimental afaik (CC @mati865), so if it breaks some package (which can be fixed by rebuilding), I think they'd consider it tolerable. If none of their packages actually have ended up using and depending on the aspects that may change (I haven't followed closely exactly how widespread it is), the ABI break should be totally transparent though.

Thanks for clarifying, I wasn't aware of that. Like I said, it's incredibly difficult to keep track of everyone who ships libc++, and especially who provides what guarantees to their users.

I added @emaste and @mati865 to the libcxx-vendors "team" here so we can ping you in these situations.

[MBkkt]

libcxx/src/atomic.cpp

38 ↗

(On Diff #246218)

Why do you use timed wait here?
It's strange, and also different with macos(ulock) behavior

[__simt__]

libcxx/src/atomic.cpp

38 ↗

(On Diff #246218)

Because it would be incorrect otherwise.

There's an infinitesimal but not zero probability that the serial number being waited on can roll over, incremented by precisely the right value, and then you might think it didn't change when it did.

There are a lot of weird discussions we could have from here. Does this negate Futex? I don't think it should. Is it even worth worrying about (like, the computer might be hit by a neutron flying in from space much more often than this)? I think it's cheap to mitigate.

There's a judgement-call here about how long to wait. It's arbitrary.

We wouldn't need to do this if Linux supported 64-bit Futex. Partly because we would rarely use serial numbers like this, and also partly because 64-bit numbers don't roll over inside of the useful life span of computer hardware.

[MBkkt]

libcxx/src/atomic.cpp

38 ↗

(On Diff #246218)

First of thanks for answer.

But if I understand correctly it's only about not atomic<int> behavior (any atomic which use waiter pool)
So for atomic<int> it's not needed (also why unsigned int not used in wait without waiter pool?)

Another thought, for ulock behavior should be same?

include/__threading_support

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP_THREADING_SUPPORT
 #define _LIBCPP_THREADING_SUPPORT
 
 #include <__config>
 #include <chrono>
 #include <iosfwd>
 #include <errno.h>
+#include <climits>
+
+#if defined(__linux__)
+# include <unistd.h>
+# include <linux/futex.h>
+# include <sys/syscall.h>
+#endif
 
 #ifndef _LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER
 #pragma GCC system_header
 #endif
 
 #if defined(_LIBCPP_HAS_THREAD_API_EXTERNAL)
 # include <__external_threading>
 #elif !defined(_LIBCPP_HAS_NO_THREADS)
 
 #if defined(_LIBCPP_HAS_THREAD_API_PTHREAD)
 # include <pthread.h>
 # include <sched.h>
+# include <semaphore.h>
+# if defined(__APPLE__)
+#  include <dispatch/dispatch.h>
+# endif
 #endif
 
 #if defined(_LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL) || \
     defined(_LIBCPP_BUILDING_THREAD_LIBRARY_EXTERNAL) || \
     defined(_LIBCPP_HAS_THREAD_API_WIN32)
 #define _LIBCPP_THREAD_ABI_VISIBILITY _LIBCPP_FUNC_VIS
 #else
 #define _LIBCPP_THREAD_ABI_VISIBILITY inline _LIBCPP_INLINE_VISIBILITY

 #define _LIBCPP_MUTEX_INITIALIZER PTHREAD_MUTEX_INITIALIZER
 
 typedef pthread_mutex_t __libcpp_recursive_mutex_t;
 
 // Condition Variable
 typedef pthread_cond_t __libcpp_condvar_t;
 #define _LIBCPP_CONDVAR_INITIALIZER PTHREAD_COND_INITIALIZER
 
+// Semaphore
+#if defined(__APPLE__)
+typedef dispatch_semaphore_t __libcpp_semaphore_t;
+# define _LIBCPP_SEMAPHORE_MAX numeric_limits<long>::max()
+#else
+typedef sem_t __libcpp_semaphore_t;
+# define _LIBCPP_SEMAPHORE_MAX SEM_VALUE_MAX
+#endif
+
 // Execute once
 typedef pthread_once_t __libcpp_exec_once_flag;
 #define _LIBCPP_EXEC_ONCE_INITIALIZER PTHREAD_ONCE_INIT
 
 // Thread id
 typedef pthread_t __libcpp_thread_id;
 
 // Thread

 
 // Thread Local Storage
 typedef long __libcpp_tls_key;
 
 #define _LIBCPP_TLS_DESTRUCTOR_CC __stdcall
 #endif // !defined(_LIBCPP_HAS_THREAD_API_PTHREAD) && !defined(_LIBCPP_HAS_THREAD_API_EXTERNAL)
 
 #if !defined(_LIBCPP_HAS_THREAD_API_EXTERNAL)
+
+_LIBCPP_THREAD_ABI_VISIBILITY
+__libcpp_timespec_t __libcpp_to_timespec(const chrono::nanoseconds& __ns);
+
 // Mutex
 _LIBCPP_THREAD_ABI_VISIBILITY
 int __libcpp_recursive_mutex_init(__libcpp_recursive_mutex_t *__m);
 
 _LIBCPP_THREAD_ABI_VISIBILITY _LIBCPP_NO_THREAD_SAFETY_ANALYSIS
 int __libcpp_recursive_mutex_lock(__libcpp_recursive_mutex_t *__m);
 
 _LIBCPP_THREAD_ABI_VISIBILITY _LIBCPP_NO_THREAD_SAFETY_ANALYSIS

 
 _LIBCPP_THREAD_ABI_VISIBILITY _LIBCPP_NO_THREAD_SAFETY_ANALYSIS
 int __libcpp_condvar_timedwait(__libcpp_condvar_t *__cv, __libcpp_mutex_t *__m,
                                __libcpp_timespec_t *__ts);
 
 _LIBCPP_THREAD_ABI_VISIBILITY
 int __libcpp_condvar_destroy(__libcpp_condvar_t* __cv);
 
+// Semaphore
+_LIBCPP_THREAD_ABI_VISIBILITY 
+bool __libcpp_semaphore_init(__libcpp_semaphore_t* __sem, int __init);
+
+_LIBCPP_THREAD_ABI_VISIBILITY
+bool __libcpp_semaphore_destroy(__libcpp_semaphore_t* __sem);
+
+_LIBCPP_THREAD_ABI_VISIBILITY
+bool __libcpp_semaphore_post(__libcpp_semaphore_t* __sem);
+
+_LIBCPP_THREAD_ABI_VISIBILITY
+bool __libcpp_semaphore_wait(__libcpp_semaphore_t* __sem);
+
+_LIBCPP_THREAD_ABI_VISIBILITY
+bool __libcpp_semaphore_wait_timed(__libcpp_semaphore_t* __sem, chrono::nanoseconds const& __ns);
+
 // Execute once
 _LIBCPP_THREAD_ABI_VISIBILITY
 int __libcpp_execute_once(__libcpp_exec_once_flag *flag,
                           void (*init_routine)());
 
 // Thread id
 _LIBCPP_THREAD_ABI_VISIBILITY
 bool __libcpp_thread_id_equal(__libcpp_thread_id t1, __libcpp_thread_id t2);

 
 _LIBCPP_THREAD_ABI_VISIBILITY
 int __libcpp_thread_detach(__libcpp_thread_t *__t);
 
 _LIBCPP_THREAD_ABI_VISIBILITY
 void __libcpp_thread_yield();
 
 _LIBCPP_THREAD_ABI_VISIBILITY
+void __libcpp_thread_yield_processor();
+
+_LIBCPP_THREAD_ABI_VISIBILITY
 void __libcpp_thread_sleep_for(const chrono::nanoseconds& __ns);
 
+template<class _Fn>
+_LIBCPP_THREAD_ABI_VISIBILITY
+bool __libcpp_thread_poll_with_backoff(_Fn && __f, chrono::nanoseconds const& __max = chrono::nanoseconds::zero());
+
 // Thread local storage
 _LIBCPP_THREAD_ABI_VISIBILITY
 int __libcpp_tls_create(__libcpp_tls_key* __key,
                         void(_LIBCPP_TLS_DESTRUCTOR_CC* __at_exit)(void*));
 
 _LIBCPP_THREAD_ABI_VISIBILITY
 void *__libcpp_tls_get(__libcpp_tls_key __key);
 
 _LIBCPP_THREAD_ABI_VISIBILITY
 int __libcpp_tls_set(__libcpp_tls_key __key, void *__p);
 
 #endif // !defined(_LIBCPP_HAS_THREAD_API_EXTERNAL)
 
 #if (!defined(_LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL) || \
      defined(_LIBCPP_BUILDING_THREAD_LIBRARY_EXTERNAL)) && \
     defined(_LIBCPP_HAS_THREAD_API_PTHREAD)
 
+__libcpp_timespec_t __libcpp_to_timespec(const chrono::nanoseconds& __ns) {
+
+   using namespace chrono;
+   seconds __s = duration_cast<seconds>(__ns);
+   __libcpp_timespec_t __ts;
+   typedef decltype(__ts.tv_sec) ts_sec;
+   _LIBCPP_CONSTEXPR ts_sec __ts_sec_max = numeric_limits<ts_sec>::max();
+
+   if (__s.count() < __ts_sec_max)
+   {
+     __ts.tv_sec = static_cast<ts_sec>(__s.count());
+     __ts.tv_nsec = static_cast<decltype(__ts.tv_nsec)>((__ns - __s).count());
+   }
+   else
+   {
+     __ts.tv_sec = __ts_sec_max;
+     __ts.tv_nsec = 999999999; // (10^9 - 1)
+   }
+   return __ts;
+}
+
 int __libcpp_recursive_mutex_init(__libcpp_recursive_mutex_t *__m)
 {
   pthread_mutexattr_t attr;
   int __ec = pthread_mutexattr_init(&attr);
   if (__ec)
     return __ec;
   __ec = pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
   if (__ec) {
int __libcpp_condvar_timedwait(__libcpp_condvar_t *__cv, __libcpp_mutex_t *__m,
   return pthread_cond_timedwait(__cv, __m, __ts);
 }
 
 int __libcpp_condvar_destroy(__libcpp_condvar_t *__cv)
 {
   return pthread_cond_destroy(__cv);
 }
 
+// Semaphore
+#if defined(__APPLE__)
+
+bool __libcpp_semaphore_init(__libcpp_semaphore_t* __sem, int __init) 
+{
+    return (*__sem = dispatch_semaphore_create(__init)) != NULL;
+}
+
+bool __libcpp_semaphore_destroy(__libcpp_semaphore_t* __sem) 
+{
+    dispatch_release(*__sem);
+    return true;
+}
+
+bool __libcpp_semaphore_post(__libcpp_semaphore_t* __sem) 
+{
+    dispatch_semaphore_signal(*__sem);
+    return true;
+}
+
+bool __libcpp_semaphore_wait(__libcpp_semaphore_t* __sem) 
+{
+    return dispatch_semaphore_wait(*__sem, DISPATCH_TIME_FOREVER) == 0;
+}
+
+bool __libcpp_semaphore_wait_timed(__libcpp_semaphore_t* __sem, chrono::nanoseconds const& __ns) 
+{
+    return dispatch_semaphore_wait(*__sem, dispatch_time(DISPATCH_TIME_NOW, __ns.count())) == 0;
+}
+
+#else
+
+bool __libcpp_semaphore_init(__libcpp_semaphore_t* __sem, int __init) 
+{
+    return sem_init(__sem, 0, __init) == 0;
+}
+
+bool __libcpp_semaphore_destroy(__libcpp_semaphore_t* __sem) 
+{
+    return sem_destroy(__sem) == 0;
+}
+
+bool __libcpp_semaphore_post(__libcpp_semaphore_t* __sem) 
+{
+    return sem_post(__sem) == 0;
+}
+
+bool __libcpp_semaphore_wait(__libcpp_semaphore_t* __sem) 
+{
+    return sem_wait(__sem) == 0;
+}
+
+bool __libcpp_semaphore_wait_timed(__libcpp_semaphore_t* __sem, chrono::nanoseconds const& __ns) 
+{
+    auto __ts = __libcpp_to_timespec(__ns);
+    return sem_timedwait(__sem, &__ts) == 0;
+}
+
+#endif //__APPLE__
+
 // Execute once
 int __libcpp_execute_once(__libcpp_exec_once_flag *flag,
                           void (*init_routine)()) {
   return pthread_once(flag, init_routine);
 }
 
 // Thread id
 // Returns non-zero if the thread ids are equal, otherwise 0
int __libcpp_thread_detach(__libcpp_thread_t *__t)
   return pthread_detach(*__t);
 }
 
 void __libcpp_thread_yield()
 {
   sched_yield();
 }
 
-void __libcpp_thread_sleep_for(const chrono::nanoseconds& __ns)
+void __libcpp_thread_yield_processor()
 {
-   using namespace chrono;
-   seconds __s = duration_cast<seconds>(__ns);
-   __libcpp_timespec_t __ts;
-   typedef decltype(__ts.tv_sec) ts_sec;
-   _LIBCPP_CONSTEXPR ts_sec __ts_sec_max = numeric_limits<ts_sec>::max();
+#if defined(__aarch64__)
+  asm volatile ("yield" :::);
+#elif defined(__x86_64__)
+  asm volatile ("pause" :::);
+#elif defined (__powerpc__)
+  asm volatile ("or 27,27,27":::);
+#else
+  ;
+#endif
+}
 
-   if (__s.count() < __ts_sec_max)
-   {
-     __ts.tv_sec = static_cast<ts_sec>(__s.count());
-     __ts.tv_nsec = static_cast<decltype(__ts.tv_nsec)>((__ns - __s).count());
-   }
-   else
-   {
-     __ts.tv_sec = __ts_sec_max;
-     __ts.tv_nsec = 999999999; // (10^9 - 1)
+void __libcpp_thread_sleep_for(const chrono::nanoseconds& __ns)
+   auto __ts = __libcpp_to_timespec(__ns);
+   while (nanosleep(&__ts, &__ts) == -1 && errno == EINTR);
+
+template<class _Fn>
+bool __libcpp_thread_poll_with_backoff(_Fn && __f, chrono::nanoseconds const& __max) 
+    auto const __start = chrono::high_resolution_clock::now();
+    for(int __count = 0;;) {
+      if(__builtin_expect(__f(),1))
+        return true;
+      if(__count < 16) {
+        if(__count > 8)
+          __libcpp_thread_yield_processor();
+        __count += 1;
+        continue;
+      }
+      auto const __elapsed = chrono::high_resolution_clock::now() - __start;
+      if(__max != chrono::nanoseconds::zero() &&
+         __max < __elapsed)
+         return false;
+      auto const __step = __elapsed / 4;
+      if(__step >= chrono::milliseconds(1))
+        __libcpp_thread_sleep_for(chrono::milliseconds(1));
+      else if(__step >= chrono::microseconds(10))
+        __libcpp_thread_sleep_for(__step);
+      else
+        __libcpp_thread_yield();
     }
-
-   while (nanosleep(&__ts, &__ts) == -1 && errno == EINTR);
 }
 
 // Thread local storage
 int __libcpp_tls_create(__libcpp_tls_key *__key, void (*__at_exit)(void *))
 {
   return pthread_key_create(__key, __at_exit);
 }
 
 void *__libcpp_tls_get(__libcpp_tls_key __key)
 {
   return pthread_getspecific(__key);
 }
 
 int __libcpp_tls_set(__libcpp_tls_key __key, void *__p)
 {
     return pthread_setspecific(__key, __p);
 }
 
 #endif // !_LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL || _LIBCPP_BUILDING_THREAD_LIBRARY_EXTERNAL
 
+#if defined(__linux__) && !defined(_LIBCPP_HAS_NO_PLATFORM_WAIT)
+
+#define _LIBCPP_HAS_PLATFORM_WAIT
+
+using __libcpp_platform_wait_t = int;
+
+template<typename _Tp>
+struct __libcpp_platform_wait_uses_type {
+  enum { __value = is_same<typename remove_cv<_Tp>::type, __libcpp_platform_wait_t>::value };
+};
+
+template <class _Tp, typename enable_if<__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+void __libcpp_platform_wait(_Tp const* ptr, _Tp val, void const* timeout) {
+    syscall(SYS_futex, ptr, FUTEX_WAIT_PRIVATE, val, timeout, 0, 0);
+}
+
+template <class _Tp, typename enable_if<__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+void __libcpp_platform_wake(_Tp const* ptr, bool all) {
+    syscall(SYS_futex, ptr, FUTEX_WAKE_PRIVATE, all ? INT_MAX : 1, 0, 0, 0);
+}
+
+#endif // __linux__
+
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+
+struct alignas(64) __libcpp_contention_t {
+#if defined(_LIBCPP_HAS_PLATFORM_WAIT)
+    ptrdiff_t                __waiters = 0;
+    __libcpp_platform_wait_t __version = 0;
+#else
+    ptrdiff_t                __credit = 0;
+    __libcpp_mutex_t         __mutex = _LIBCPP_MUTEX_INITIALIZER;
+    __libcpp_condvar_t       __condvar = _LIBCPP_CONDVAR_INITIALIZER;
+#endif
+};
+
+_LIBCPP_FUNC_VIS
+__libcpp_contention_t * __libcpp_contention_state(void const volatile * p) _NOEXCEPT;
+
+#endif // _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+
+#if !defined(_LIBCPP_HAS_NO_TREE_BARRIER) && !defined(_LIBCPP_HAS_NO_THREAD_FAVORITE_BARRIER_INDEX)
+
+_LIBCPP_EXPORTED_FROM_ABI
+extern thread_local ptrdiff_t __libcpp_thread_favorite_barrier_index;
+
+#endif
+
 class _LIBCPP_TYPE_VIS thread;
 class _LIBCPP_TYPE_VIS __thread_id;
 
 namespace this_thread
 {
 
 _LIBCPP_INLINE_VISIBILITY __thread_id get_id() _NOEXCEPT;
 

include/atomic

 void atomic_thread_fence(memory_order m) noexcept;
 void atomic_signal_fence(memory_order m) noexcept;
 
 }  // std
 
 */
 
 #include <__config>
+#include <__threading_support>
 #include <cstddef>
 #include <cstdint>
 #include <type_traits>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
typedef enum memory_order {
   memory_order_acquire = __mo_acquire,
   memory_order_release = __mo_release,
   memory_order_acq_rel = __mo_acq_rel,
   memory_order_seq_cst = __mo_seq_cst,
 } memory_order;
 
 #endif // _LIBCPP_STD_VER > 17
 
+extern "C" int memcmp( const void * ptr1, const void * ptr2, size_t num );
+
+template <typename _Tp> _LIBCPP_INLINE_VISIBILITY
+bool __cxx_atomic_compare_equal(_Tp const& __lhs, _Tp const& __rhs) {
+    return memcmp(&__lhs, &__rhs, sizeof(_Tp)) == 0;
+}
+
 static_assert((is_same<underlying_type<memory_order>::type, __memory_order_underlying_t>::value),
   "unexpected underlying type for std::memory_order");
 
 #if defined(_LIBCPP_HAS_GCC_ATOMIC_IMP) || \
-  defined(_LIBCPP_ATOMIC_ONLY_USE_BUILTINS)
+  defined(_LIBCPP_ATOMIC_ONLY_USE_BUILTINS)
 
 // [atomics.types.generic]p1 guarantees _Tp is trivially copyable. Because
 // the default operator= in an object is not volatile, a byte-by-byte copy
 // is required.
 template <typename _Tp, typename _Tv> _LIBCPP_INLINE_VISIBILITY
 typename enable_if<is_assignable<_Tp&, _Tv>::value>::type
 __cxx_atomic_assign_volatile(_Tp& __a_value, _Tv const& __val) {
   __a_value = __val;
_Tp __cxx_atomic_fetch_xor(__cxx_atomic_base_impl<_Tp> volatile* __a, _Tp __pattern, memory_order __order) _NOEXCEPT {
     return __c11_atomic_fetch_xor(&__a->__a_value, __pattern, static_cast<__memory_order_underlying_t>(__order));
 }
 template<class _Tp>
 _LIBCPP_INLINE_VISIBILITY
 _Tp __cxx_atomic_fetch_xor(__cxx_atomic_base_impl<_Tp> * __a, _Tp __pattern, memory_order __order) _NOEXCEPT {
     return __c11_atomic_fetch_xor(&__a->__a_value, __pattern, static_cast<__memory_order_underlying_t>(__order));
 }
 
-#endif // _LIBCPP_HAS_GCC_ATOMIC_IMP, _LIBCPP_HAS_C_ATOMIC_IMP
+#endif // _LIBCPP_HAS_GCC_ATOMIC_IMP, _LIBCPP_HAS_C_ATOMIC_IMP 
 
 template <class _Tp>
 _LIBCPP_INLINE_VISIBILITY
 _Tp kill_dependency(_Tp __y) _NOEXCEPT
 {
     return __y;
 }
 
_Tp* __cxx_atomic_fetch_add(volatile __cxx_atomic_lock_impl<_Tp*>* __a,
   __cxx_atomic_assign_volatile(__old, __a->__a_value);
   __cxx_atomic_assign_volatile(__a->__a_value, __old + __delta);
   __a->__unlock();
   return __old;
 }
 template <typename _Tp, typename _Td>
 _LIBCPP_INLINE_VISIBILITY
 _Tp* __cxx_atomic_fetch_add(__cxx_atomic_lock_impl<_Tp*>* __a,
                             ptrdiff_t __delta, memory_order) {
   __a->__lock();
   _Tp* __old = __a->__a_value;
   __a->__a_value += __delta;
   __a->__unlock();
   return __old;
 }
 
 template <typename _Tp, typename _Td>
static_assert(is_trivially_copyable<_Tp>::value,
       "std::atomic<Tp> requires that 'Tp' be a trivially copyable type");
 #endif
 
   _LIBCPP_INLINE_VISIBILITY __cxx_atomic_impl() _NOEXCEPT _LIBCPP_DEFAULT
   _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR explicit __cxx_atomic_impl(_Tp value) _NOEXCEPT
     : _Base(value) {}
 };
 
+template<typename _Tp = int>
+__cxx_atomic_impl<_Tp>* __cxx_atomic_rebind(_Tp* __inst) {
+    static_assert(sizeof(__cxx_atomic_impl<_Tp>) == sizeof(_Tp),"");
+    static_assert(alignof(__cxx_atomic_impl<_Tp>) == alignof(_Tp),"");
+    return (__cxx_atomic_impl<_Tp>*)__inst;
+}
+
+#ifdef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_try_wait_slow_fallback(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp __val, memory_order __order) {
+    __libcpp_thread_poll_with_backoff([=] _LIBCPP_INLINE_VISIBILITY () -> bool {
+        return __cxx_atomic_load(__a, __order) != __val;
+    });
+}
+
+#endif
+
+#ifdef _LIBCPP_HAS_PLATFORM_WAIT
+
+template <class _Tp, typename enable_if<!__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_all(__cxx_atomic_impl<_Tp> const volatile* __a) {
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+    auto * const __c = __libcpp_contention_state(__a);
+    __cxx_atomic_fetch_add(__cxx_atomic_rebind(&__c->__version), (__libcpp_platform_wait_t)1, memory_order_relaxed);
+    __cxx_atomic_thread_fence(memory_order_seq_cst);
+    if (0 != __cxx_atomic_exchange(__cxx_atomic_rebind(&__c->__waiters), (ptrdiff_t)0, memory_order_relaxed))
+        __libcpp_platform_wake(&__c->__version, true);
+#endif
+}
+template <class _Tp, typename enable_if<!__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_one(__cxx_atomic_impl<_Tp> const volatile* __a) {
+    __cxx_atomic_notify_all(__a);
+}
+template <class _Tp, typename enable_if<!__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_try_wait_slow(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp const __val, memory_order __order) {
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+    auto * const __c = __libcpp_contention_state(__a);
+    __cxx_atomic_store(__cxx_atomic_rebind(&__c->__waiters), (ptrdiff_t)1, memory_order_relaxed);
+    __cxx_atomic_thread_fence(memory_order_seq_cst);
+    auto const __version = __cxx_atomic_load(__cxx_atomic_rebind(&__c->__version), memory_order_relaxed);
+    if (__builtin_expect(!__cxx_atomic_compare_equal(__cxx_atomic_load(__a, __order), __val), 1))
+        return;
+    if(sizeof(__libcpp_platform_wait_t) < 8) {
+        constexpr timespec __timeout = { 2, 0 }; // Hedge on rare 'int version' aliasing.
+        __libcpp_platform_wait(&__c->__version, __version, &__timeout);
+    }
+    else
+        __libcpp_platform_wait(&__c->__version, __version, nullptr);
+#else
+    __cxx_atomic_try_wait_slow_fallback(__a, __val, __order);
+#endif // _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+}
+
+template <class _Tp, typename enable_if<__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_try_wait_slow(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp __val, memory_order __order) {
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+    auto * const __c = __libcpp_contention_state(__a);
+    __cxx_atomic_fetch_add(__cxx_atomic_rebind(&__c->__waiters), (ptrdiff_t)1, memory_order_relaxed);
+    __cxx_atomic_thread_fence(memory_order_seq_cst);
+#endif
+    __libcpp_platform_wait((_Tp*)__a, __val, nullptr);
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+    __cxx_atomic_fetch_sub(__cxx_atomic_rebind(&__c->__waiters), (ptrdiff_t)1, memory_order_relaxed);
+#endif
+}
+template <class _Tp, typename enable_if<__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_all(__cxx_atomic_impl<_Tp> const volatile* __a) {
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+    auto * const __c = __libcpp_contention_state(__a);
+    __cxx_atomic_thread_fence(memory_order_seq_cst);
+    if (0 != __cxx_atomic_load(__cxx_atomic_rebind(&__c->__waiters), memory_order_relaxed))
+#endif
+        __libcpp_platform_wake((_Tp*)__a, true);
+}
+template <class _Tp, typename enable_if<__libcpp_platform_wait_uses_type<_Tp>::__value, int>::type = 1>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_one(__cxx_atomic_impl<_Tp> const volatile* __a) {
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+    auto * const __c = __libcpp_contention_state(__a);
+    __cxx_atomic_thread_fence(memory_order_seq_cst);
+    if (0 != __cxx_atomic_load(__cxx_atomic_rebind(&__c->__waiters), memory_order_relaxed))
+#endif
+        __libcpp_platform_wake((_Tp*)__a, false);
+}
+
+#elif !defined(_LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE)
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_all(__cxx_atomic_impl<_Tp> const volatile* __a) {
+    auto * const __c = __libcpp_contention_state(__a);
+    __cxx_atomic_thread_fence(memory_order_seq_cst);
+    if(__builtin_expect(0 == __cxx_atomic_load(__cxx_atomic_rebind(&__c->__credit), memory_order_relaxed), 1))
+        return;
+    if(0 != __cxx_atomic_exchange(__cxx_atomic_rebind(&__c->__credit), (ptrdiff_t)0, memory_order_relaxed)) {
+        __libcpp_mutex_lock(&__c->__mutex);
+        __libcpp_mutex_unlock(&__c->__mutex);
+        __libcpp_condvar_broadcast(&__c->__condvar);
+    }
+}
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_one(__cxx_atomic_impl<_Tp> const volatile* __a) {
+    __cxx_atomic_notify_all(__a);
+}
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_try_wait_slow(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp const __val, memory_order __order) {
+    auto * const __c = __libcpp_contention_state(__a);
+    __libcpp_mutex_lock(&__c->__mutex);
+    __cxx_atomic_store(__cxx_atomic_rebind(&__c->__credit), (ptrdiff_t)1, memory_order_relaxed);
+    __cxx_atomic_thread_fence(memory_order_seq_cst);
+    if (__cxx_atomic_compare_equal(__cxx_atomic_load(__a, __order), __val))
+        __libcpp_condvar_wait(&__c->__condvar, &__c->__mutex);
+    __libcpp_mutex_unlock(&__c->__mutex);
+}
+
+#else
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_try_wait_slow(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp __val, memory_order __order) {
+    __cxx_atomic_try_wait_slow_fallback(__a, __val, __order);
+}
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_one(__cxx_atomic_impl<_Tp> const volatile*) {
+}
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_all(__cxx_atomic_impl<_Tp> const volatile*) {
+}
+
+#endif // _LIBCPP_HAS_PLATFORM_WAIT || !defined(_LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE)
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_wait(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp const __val, memory_order __order) {
+#ifndef _LIBCPP_NO_SPINNING
+    for(int __i = 0; __i < 16; ++__i) {
+        if(!__cxx_atomic_compare_equal(__cxx_atomic_load(__a, __order), __val))
+            return;
+        if(__i < 12)
+            __libcpp_thread_yield_processor();
+        else
+            __libcpp_thread_yield();
+    }
+#endif
+    while(__cxx_atomic_compare_equal(__cxx_atomic_load(__a, __order), __val))
+        __cxx_atomic_try_wait_slow(__a, __val, __order);
+}
+
 // general atomic<T>
 
 template <class _Tp, bool = is_integral<_Tp>::value && !is_same<_Tp, bool>::value>
 struct __atomic_base  // false
 {
     mutable __cxx_atomic_impl<_Tp> __a_;
 
 #if defined(__cpp_lib_atomic_is_always_lock_free)
#endif
     bool compare_exchange_strong(_Tp& __e, _Tp __d,
                               memory_order __m = memory_order_seq_cst) volatile _NOEXCEPT
         {return __cxx_atomic_compare_exchange_strong(&__a_, &__e, __d, __m, __m);}
     _LIBCPP_INLINE_VISIBILITY
     bool compare_exchange_strong(_Tp& __e, _Tp __d,
                                  memory_order __m = memory_order_seq_cst) _NOEXCEPT
         {return __cxx_atomic_compare_exchange_strong(&__a_, &__e, __d, __m, __m);}
 
+    _LIBCPP_INLINE_VISIBILITY void wait(_Tp __v, memory_order __m = memory_order_seq_cst) const volatile _NOEXCEPT
+        {__cxx_atomic_wait(&__a_, __v, __m);}
+    _LIBCPP_INLINE_VISIBILITY void wait(_Tp __v, memory_order __m = memory_order_seq_cst) const _NOEXCEPT
+        {__cxx_atomic_wait(&__a_, __v, __m);}
+    _LIBCPP_INLINE_VISIBILITY void notify_one() volatile _NOEXCEPT
+        {__cxx_atomic_notify_one(&__a_);}
+    _LIBCPP_INLINE_VISIBILITY void notify_one() _NOEXCEPT
+        {__cxx_atomic_notify_one(&__a_);}
+    _LIBCPP_INLINE_VISIBILITY void notify_all() volatile _NOEXCEPT
+        {__cxx_atomic_notify_all(&__a_);}
+    _LIBCPP_INLINE_VISIBILITY void notify_all() _NOEXCEPT
+        {__cxx_atomic_notify_all(&__a_);}
+
     _LIBCPP_INLINE_VISIBILITY
     __atomic_base() _NOEXCEPT _LIBCPP_DEFAULT
 
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
     __atomic_base(_Tp __d) _NOEXCEPT : __a_(__d) {}
 
 #ifndef _LIBCPP_CXX03_LANG
     __atomic_base(const __atomic_base&) = delete;

 
 // atomic<T>
 
 template <class _Tp>
 struct atomic
     : public __atomic_base<_Tp>
 {
     typedef __atomic_base<_Tp> __base;
+    using value_type = _Tp;
     _LIBCPP_INLINE_VISIBILITY
     atomic() _NOEXCEPT _LIBCPP_DEFAULT
     _LIBCPP_INLINE_VISIBILITY
     _LIBCPP_CONSTEXPR atomic(_Tp __d) _NOEXCEPT : __base(__d) {}
 
     _LIBCPP_INLINE_VISIBILITY
     _Tp operator=(_Tp __d) volatile _NOEXCEPT
         {__base::store(__d); return __d;}
     _LIBCPP_INLINE_VISIBILITY
     _Tp operator=(_Tp __d) _NOEXCEPT
         {__base::store(__d); return __d;}
 };
 
 // atomic<T*>
 
 template <class _Tp>
 struct atomic<_Tp*>
     : public __atomic_base<_Tp*>
 {
     typedef __atomic_base<_Tp*> __base;
+    using value_type = _Tp*;
     _LIBCPP_INLINE_VISIBILITY
     atomic() _NOEXCEPT _LIBCPP_DEFAULT
     _LIBCPP_INLINE_VISIBILITY
     _LIBCPP_CONSTEXPR atomic(_Tp* __d) _NOEXCEPT : __base(__d) {}
 
     _LIBCPP_INLINE_VISIBILITY
     _Tp* operator=(_Tp* __d) volatile _NOEXCEPT
         {__base::store(__d); return __d;}

 atomic_compare_exchange_strong_explicit(atomic<_Tp>* __o, _Tp* __e,
                                         _Tp __d,
                                         memory_order __s, memory_order __f) _NOEXCEPT
   _LIBCPP_CHECK_EXCHANGE_MEMORY_ORDER(__s, __f)
 {
     return __o->compare_exchange_strong(*__e, __d, __s, __f);
 }
 
+// atomic_wait
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_wait(const volatile atomic<_Tp>* __o,
+                    typename atomic<_Tp>::value_type __v) _NOEXCEPT
+{
+    return __o->wait(__v);
+}
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_wait(const atomic<_Tp>* __o,
+                    typename atomic<_Tp>::value_type __v) _NOEXCEPT
+{
+    return __o->wait(__v);
+}
+
+// atomic_wait_explicit
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_wait_explicit(const volatile atomic<_Tp>* __o,
+                            typename atomic<_Tp>::value_type __v,
+                            memory_order __m) _NOEXCEPT
+  _LIBCPP_CHECK_LOAD_MEMORY_ORDER(__m)
+{
+    return __o->wait(__v, __m);
+}
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_wait_explicit(const atomic<_Tp>* __o,
+                            typename atomic<_Tp>::value_type __v,
+                            memory_order __m) _NOEXCEPT
+  _LIBCPP_CHECK_LOAD_MEMORY_ORDER(__m)
+{
+    return __o->wait(__v, __m);
+}
+
+// atomic_notify_one
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_notify_one(volatile atomic<_Tp>* __o) _NOEXCEPT
+{
+    __o->notify_one();
+}
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_notify_one(atomic<_Tp>* __o) _NOEXCEPT
+{
+    __o->notify_one();
+}
+
+// atomic_notify_one
+
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_notify_all(volatile atomic<_Tp>* __o) _NOEXCEPT
+{
+    __o->notify_all();
+}
+template <class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+void atomic_notify_all(atomic<_Tp>* __o) _NOEXCEPT
+{
+    __o->notify_all();
+}
+
 // atomic_fetch_add
 
 template <class _Tp>
 _LIBCPP_INLINE_VISIBILITY
 typename enable_if
 <
     is_integral<_Tp>::value && !is_same<_Tp, bool>::value,
     _Tp

 
 // flag type and operations
 
 typedef struct atomic_flag
 {
     __cxx_atomic_impl<_LIBCPP_ATOMIC_FLAG_TYPE> __a_;
 
     _LIBCPP_INLINE_VISIBILITY
+    bool test(memory_order __m = memory_order_seq_cst) const volatile _NOEXCEPT
+        {return _LIBCPP_ATOMIC_FLAG_TYPE(true)==__cxx_atomic_load(&__a_, __m);}
+    _LIBCPP_INLINE_VISIBILITY
+    bool test(memory_order __m = memory_order_seq_cst) const _NOEXCEPT
+        {return _LIBCPP_ATOMIC_FLAG_TYPE(true)==__cxx_atomic_load(&__a_, __m);}
+
+    _LIBCPP_INLINE_VISIBILITY
     bool test_and_set(memory_order __m = memory_order_seq_cst) volatile _NOEXCEPT
         {return __cxx_atomic_exchange(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(true), __m);}
     _LIBCPP_INLINE_VISIBILITY
     bool test_and_set(memory_order __m = memory_order_seq_cst) _NOEXCEPT
         {return __cxx_atomic_exchange(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(true), __m);}
     _LIBCPP_INLINE_VISIBILITY
     void clear(memory_order __m = memory_order_seq_cst) volatile _NOEXCEPT
         {__cxx_atomic_store(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(false), __m);}
     _LIBCPP_INLINE_VISIBILITY
     void clear(memory_order __m = memory_order_seq_cst) _NOEXCEPT
         {__cxx_atomic_store(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(false), __m);}
 
     _LIBCPP_INLINE_VISIBILITY
+    void wait(bool __v, memory_order __m = memory_order_seq_cst) const volatile _NOEXCEPT
+        {__cxx_atomic_wait(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(__v), __m);}
+    _LIBCPP_INLINE_VISIBILITY
+    void wait(bool __v, memory_order __m = memory_order_seq_cst) const _NOEXCEPT
+        {__cxx_atomic_wait(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(__v), __m);}
+    _LIBCPP_INLINE_VISIBILITY
+    void notify_one() volatile _NOEXCEPT
+        {__cxx_atomic_notify_one(&__a_);}
+    _LIBCPP_INLINE_VISIBILITY
+    void notify_one() _NOEXCEPT
+        {__cxx_atomic_notify_one(&__a_);}
+    _LIBCPP_INLINE_VISIBILITY
+    void notify_all() volatile _NOEXCEPT
+        {__cxx_atomic_notify_all(&__a_);}
+    _LIBCPP_INLINE_VISIBILITY
+    void notify_all() _NOEXCEPT
+        {__cxx_atomic_notify_all(&__a_);}
+
+    _LIBCPP_INLINE_VISIBILITY
     atomic_flag() _NOEXCEPT _LIBCPP_DEFAULT
 
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
     atomic_flag(bool __b) _NOEXCEPT : __a_(__b) {} // EXTENSION
 
 #ifndef _LIBCPP_CXX03_LANG
     atomic_flag(const atomic_flag&) = delete;
     atomic_flag& operator=(const atomic_flag&) = delete;
     atomic_flag& operator=(const atomic_flag&) volatile = delete;
 #else
 private:
     atomic_flag(const atomic_flag&);
     atomic_flag& operator=(const atomic_flag&);
     atomic_flag& operator=(const atomic_flag&) volatile;
 #endif
 } atomic_flag;
 
+
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+atomic_flag_test(const volatile atomic_flag* __o) _NOEXCEPT
+{
+    return __o->test();
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+atomic_flag_test(const atomic_flag* __o) _NOEXCEPT
+{
+    return __o->test();
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+atomic_flag_test_explicit(const volatile atomic_flag* __o, memory_order __m) _NOEXCEPT
+{
+    return __o->test(__m);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+atomic_flag_test_explicit(const atomic_flag* __o, memory_order __m) _NOEXCEPT
+{
+    return __o->test(__m);
+}
+
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 atomic_flag_test_and_set(volatile atomic_flag* __o) _NOEXCEPT
 {
     return __o->test_and_set();
 }
 
 inline _LIBCPP_INLINE_VISIBILITY

 
 inline _LIBCPP_INLINE_VISIBILITY
 void
 atomic_flag_clear_explicit(atomic_flag* __o, memory_order __m) _NOEXCEPT
 {
     __o->clear(__m);
 }
 
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_wait(const volatile atomic_flag* __o, bool __v) _NOEXCEPT
+{
+    __o->wait(__v);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_wait(const atomic_flag* __o, bool __v) _NOEXCEPT
+{
+    __o->wait(__v);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_wait_explicit(const volatile atomic_flag* __o, 
+                          bool __v, memory_order __m) _NOEXCEPT
+{
+    __o->wait(__v, __m);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_wait_explicit(const atomic_flag* __o, 
+                          bool __v, memory_order __m) _NOEXCEPT
+{
+    __o->wait(__v, __m);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_notify_one(volatile atomic_flag* __o) _NOEXCEPT
+{
+    __o->notify_one();
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_notify_one(atomic_flag* __o) _NOEXCEPT
+{
+    __o->notify_one();
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_notify_all(volatile atomic_flag* __o) _NOEXCEPT
+{
+    __o->notify_all();
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
+void
+atomic_flag_notify_all(atomic_flag* __o) _NOEXCEPT
+{
+    __o->notify_all();
+}
+
 // fences
 
 inline _LIBCPP_INLINE_VISIBILITY
 void
 atomic_thread_fence(memory_order __m) _NOEXCEPT
 {
     __cxx_atomic_thread_fence(__m);
 }

 
 typedef atomic<intptr_t>  atomic_intptr_t;
 typedef atomic<uintptr_t> atomic_uintptr_t;
 typedef atomic<size_t>    atomic_size_t;
 typedef atomic<ptrdiff_t> atomic_ptrdiff_t;
 typedef atomic<intmax_t>  atomic_intmax_t;
 typedef atomic<uintmax_t> atomic_uintmax_t;
 
+static_assert(ATOMIC_INT_LOCK_FREE, "This library assumes atomic<int> is lock-free.");
+
+typedef atomic<int>       atomic_signed_lock_free;
+typedef atomic<unsigned>  atomic_unsigned_lock_free;
+
 #define ATOMIC_FLAG_INIT {false}
 #define ATOMIC_VAR_INIT(__v) {__v}
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif  // _LIBCPP_ATOMIC

include/barrier

+// -*- C++ -*-
+//===--------------------------- barrier ----------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_BARRIER
+#define _LIBCPP_BARRIER
+
+/*
+    barrier synopsis
+
+namespace std 
+{
+
+  template<class CompletionFunction = see below>
+  class barrier 
+  {
+  public:
+    using arrival_token = see below;
+
+    constexpr explicit barrier(ptrdiff_t phase_count,
+                               CompletionFunction f = CompletionFunction());
+    ~barrier();
+
+    barrier(const barrier&) = delete;
+    barrier& operator=(const barrier&) = delete;
+
+    [[nodiscard]] arrival_token arrive(ptrdiff_t update = 1);
+    void wait(arrival_token&& arrival) const;
+
+    void arrive_and_wait();
+    void arrive_and_drop();
+
+  private:
+    CompletionFunction __completion; // exposition only
+  };
+
+}
+
+*/
+
+#include <__config>
+#include <__threading_support>
+#include <atomic>
+#include <cassert>
+# ifndef _LIBCPP_HAS_NO_TREE_BARRIER
+#  include <thread>
+#  include <vector>
+# endif
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+#ifdef _LIBCPP_HAS_NO_THREADS
+# error <barrier> is not supported on this single threaded system
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+struct __empty_completion 
+{
+    inline _LIBCPP_INLINE_VISIBILITY
+    void operator()() noexcept { }
+};
+
+#ifndef _LIBCPP_HAS_NO_TREE_BARRIER
+
+template<class _CompletionF = __empty_completion>
+class alignas(64) __barrier_base {
+
+    ptrdiff_t          __expected;
+    atomic<ptrdiff_t>  __expected_adjustment;
+    _CompletionF       __completion;
+
+    using __phase_t = uint8_t;
+    atomic<__phase_t>  __phase;
+
+    struct alignas(64) __state_t 
+    {
+        struct {
+            atomic<__phase_t> __phase = ATOMIC_VAR_INIT(0);
+        } __tickets[64];
+    };
+    vector<__state_t>   __state;
+
+    inline _LIBCPP_INLINE_VISIBILITY
+    bool __arrive(__phase_t const __old_phase)
+    {
+        __phase_t const __half_step = __old_phase + 1, __full_step = __old_phase + 2;
+#ifndef _LIBCPP_HAS_NO_THREAD_FAVORITE_BARRIER_INDEX
+        ptrdiff_t __current = __libcpp_thread_favorite_barrier_index, 
+#else
+        ptrdiff_t __current = 0, 
+#endif
+                  __current_expected = __expected, 
+                  __last_node = (__current_expected >> 1);
+        for(size_t __round = 0;; ++__round) {
+            assert(__round <= 63);
+            if(__current_expected == 1)
+                return true;
+            for(;;++__current) {
+#ifndef _LIBCPP_HAS_NO_THREAD_FAVORITE_BARRIER_INDEX
+                if(0 == __round) {
+                    if(__current >= __current_expected)
+                        __current = 0;
+                    __libcpp_thread_favorite_barrier_index = __current;
+                }
+#endif
+                assert(__current <= __last_node);
+                __phase_t expect = __old_phase;
+                if(__current == __last_node && (__current_expected & 1))
+                {
+                    if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
+                        break;    // I'm 1 in 1, go to next __round
+                    assert(expect == __full_step);
+                }
+                else if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __half_step, memory_order_acq_rel)) 
+                {
+                    return false; // I'm 1 in 2, done with arrival
+                }
+                else if(expect == __half_step)
+                {
+                    if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
+                        break;    // I'm 2 in 2, go to next __round
+                    assert(expect == __full_step);
+                }
+                assert(__round == 0 && expect == __full_step);
+            }
+            __current_expected = (__current_expected >> 1) + (__current_expected & 1);
+            __current &= ~( 1 << __round );
+            __last_node &= ~( 1 << __round );
+        }
+    }
+
+public:
+    using arrival_token = __phase_t;
+    
+    inline _LIBCPP_INLINE_VISIBILITY
+    __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF()) 
+            : __expected(__expected), __expected_adjustment(0), __completion(__completion), 
+              __phase(0), __state((__expected+1) >> 1)
+    { 
+        assert(__expected >= 0);
+    }
+
+    inline _LIBCPP_INLINE_VISIBILITY
+    ~__barrier_base() = default;
+
+    __barrier_base(__barrier_base const&) = delete;
+    __barrier_base& operator=(__barrier_base const&) = delete;
+
+    [[nodiscard]] inline _LIBCPP_INLINE_VISIBILITY
+    arrival_token arrive(ptrdiff_t update = 1) 
+    {
+        assert(update > 0);
+        auto __old_phase = __phase.load(memory_order_relaxed);
+        for(; update; --update)
+            if(__arrive(__old_phase)) {
+                __completion();
+                __expected += __expected_adjustment.load(memory_order_relaxed);
+                __expected_adjustment.store(0, memory_order_relaxed);
+                __phase.store(__old_phase + 2, memory_order_release);
+            }
+        return __old_phase;
+    }
+    inline _LIBCPP_INLINE_VISIBILITY
+    void wait(arrival_token&& __old_phase) const 
+    {
+        __libcpp_thread_poll_with_backoff([&]() -> bool {
+            return __phase.load(memory_order_acquire) != __old_phase;
+        });
+    }
+  inline _LIBCPP_INLINE_VISIBILITY
+    void arrive_and_wait() 
+    {
+        wait(arrive());
+  }
+    inline _LIBCPP_INLINE_VISIBILITY
+    void arrive_and_drop() 
+    {
+        __expected_adjustment.fetch_sub(1, memory_order_relaxed);
+        (void)arrive();
+    }
+};
+
+#else
+
+template<class _CompletionF>
+class __barrier_base {
+
+    alignas(64) atomic<ptrdiff_t> __expected, arrived;
+    alignas(64) _CompletionF      __completion;
+    alignas(64) atomic<bool>      __phase;
+public:
+    using arrival_token = bool;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF()) 
+        : __phase(false), __expected(__expected), arrived(__expected), __completion(__completion) 
+    {
+    }
+
+    ~__barrier_base() = default;
+
+    __barrier_base(__barrier_base const&) = delete;
+    __barrier_base& operator=(__barrier_base const&) = delete;
+
+    [[nodiscard]] _LIBCPP_INLINE_VISIBILITY
+    arrival_token arrive(ptrdiff_t update = 1) 
+    {
+        auto const __old_phase = __phase.load(memory_order_relaxed);
+        auto const __result = arrived.fetch_sub(update, memory_order_acq_rel) - update;
+        assert(__result >= 0);
+        auto const new_expected = __expected.load(memory_order_relaxed);
+        if(0 == __result) {
+            __completion();
+            arrived.store(new_expected, memory_order_relaxed);
+            __phase.store(!__old_phase, memory_order_release);
+            atomic_notify_all(&__phase);
+        }
+        return __old_phase;
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    void wait(arrival_token&& __old_phase) const 
+    {
+        __phase.wait(__old_phase, memory_order_acquire);
+    }
+  _LIBCPP_INLINE_VISIBILITY 
+    void arrive_and_wait() 
+    {
+        wait(arrive());
+  }
+    _LIBCPP_INLINE_VISIBILITY
+    void arrive_and_drop() 
+    {
+        __expected.fetch_sub(1, memory_order_relaxed);
+        (void)arrive();
+    }
+};
+
+template<>
+class __barrier_base<__empty_completion> {
+
+    static constexpr uint64_t __expected_unit = 1ull;
+    static constexpr uint64_t __arrived_unit = 1ull << 32;
+    static constexpr uint64_t __expected_mask = __arrived_unit - 1;
+    static constexpr uint64_t __phase_bit = 1ull << 63;
+    static constexpr uint64_t __arrived_mask = (__phase_bit - 1) & ~__expected_mask;
+
+    alignas(64) atomic<uint64_t> __phase_arrived_expected;
+
+    static inline _LIBCPP_INLINE_VISIBILITY
+    constexpr uint64_t __init(ptrdiff_t __count) _NOEXCEPT 
+    {
+        return (((1u << 31) - __count) << 32) 
+              | ((1u << 31) - __count);
+    }
+
+public:
+    using arrival_token = uint64_t;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __barrier_base(ptrdiff_t __count, __empty_completion = __empty_completion()) 
+        : __phase_arrived_expected(__init(__count)) { 
+    }
+
+    ~__barrier_base() = default;
+
+    __barrier_base(__barrier_base const&) = delete;
+    __barrier_base& operator=(__barrier_base const&) = delete;
+
+    [[nodiscard]] inline _LIBCPP_INLINE_VISIBILITY
+    arrival_token arrive(ptrdiff_t update = 1) 
+    {
+        auto const __inc = __arrived_unit * update;
+        auto const __old = __phase_arrived_expected.fetch_add(__inc, memory_order_acq_rel);
+        if((__old ^ (__old + __inc)) & __phase_bit) {
+            __phase_arrived_expected.fetch_add((__old & __expected_mask) << 32, memory_order_relaxed);
+            __phase_arrived_expected.notify_all();
+        }
+        return __old & __phase_bit;
+    }
+    inline _LIBCPP_INLINE_VISIBILITY 
+    void wait(arrival_token&& __phase) const
+    {
+        __libcpp_thread_poll_with_backoff([&]() -> bool
+        {
+            uint64_t const __current = __phase_arrived_expected.load(memory_order_acquire);
+            return ((__current & __phase_bit) != __phase);
+        });
+    }
+  inline _LIBCPP_INLINE_VISIBILITY
+    void arrive_and_wait() 
+    {
+        wait(arrive());
+  }
+    inline _LIBCPP_INLINE_VISIBILITY
+    void arrive_and_drop() 
+    {
+        __phase_arrived_expected.fetch_add(__expected_unit, memory_order_relaxed);
+        (void)arrive();
+    }
+};
+
+#endif //_LIBCPP_HAS_NO_TREE_BARRIER
+
+template<class _CompletionF = __empty_completion>
+class barrier : public __barrier_base<_CompletionF> {
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF()) 
+        : __barrier_base<_CompletionF>(__count, __completion) { 
+    }
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif //_LIBCPP_BARRIER

include/chrono

 public:
     typedef _Rep rep;
     typedef typename _Period::type period;
 private:
     rep __rep_;
 public:
 
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 #ifndef _LIBCPP_CXX03_LANG
         duration() = default;
 #else
         duration() {}
 #endif
 
     template <class _Rep2>
         _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
         explicit duration(const _Rep2& __r,

 {
     return __lhs.time_since_epoch() - __rhs.time_since_epoch();
 }
 
 //////////////////////////////////////////////////////////
 /////////////////////// clocks ///////////////////////////
 //////////////////////////////////////////////////////////
 
+#ifndef _LIBCPP_HAS_CLOCK_API_EXTERNAL
+
 class _LIBCPP_TYPE_VIS system_clock
 {
 public:
     typedef microseconds                     duration;
     typedef duration::rep                    rep;
     typedef duration::period                 period;
     typedef chrono::time_point<system_clock> time_point;
     static _LIBCPP_CONSTEXPR_AFTER_CXX11 const bool is_steady = false;
public:
     static time_point now() _NOEXCEPT;
 };
 
 typedef steady_clock high_resolution_clock;
 #else
 typedef system_clock high_resolution_clock;
 #endif
 
+#endif // _LIBCPP_HAS_CLOCK_API_EXTERNAL
+
 #if _LIBCPP_STD_VER > 17
+
+#ifndef _LIBCPP_HAS_CLOCK_API_EXTERNAL
+
 // [time.clock.file], type file_clock
 using file_clock = _VSTD_FS::_FilesystemClock;
 
 template<class _Duration>
 using file_time = time_point<file_clock, _Duration>;
 
 
 template <class _Duration>
 using sys_time    = time_point<system_clock, _Duration>;
 using sys_seconds = sys_time<seconds>;
 using sys_days    = sys_time<days>;
 
 struct local_t {};
 template<class Duration>
 using local_time  = time_point<local_t, Duration>;
 using local_seconds = local_time<seconds>;
 using local_days    = local_time<days>;
 
+#endif // _LIBCPP_HAS_CLOCK_API_EXTERNAL
 
 struct last_spec { explicit last_spec() = default; };
 
 class day {
 private:
     unsigned char __d;
 public:
     day() = default;

include/cstddef

 using ::max_align_t;
 #else
 typedef long double max_align_t;
 #endif
 
 _LIBCPP_END_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 14
+#ifdef _LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
+_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
+#else
 namespace std  // purposefully not versioned
 {
+#endif //_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
 enum class byte : unsigned char {};
 
 constexpr byte  operator| (byte  __lhs, byte __rhs) noexcept
 {
     return static_cast<byte>(
       static_cast<unsigned char>(
          static_cast<unsigned int>(__lhs) | static_cast<unsigned int>(__rhs)
     ));

 constexpr byte  operator~ (byte __b) noexcept
 {
     return static_cast<byte>(
       static_cast<unsigned char>(
         ~static_cast<unsigned int>(__b)
     ));
 }
 
+#ifdef _LIBCPP_END_NAMESPACE_STD_NOVERSION
+_LIBCPP_END_NAMESPACE_STD_NOVERSION
+#else
 }
+#endif //_LIBCPP_END_NAMESPACE_STD_NOVERSION
 
 #include <type_traits>  // rest of byte
 #endif
 
 #endif  // _LIBCPP_CSTDDEF

include/latch

+// -*- C++ -*-
+//===--------------------------- latch -----------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_LATCH
+#define _LIBCPP_LATCH
+
+/*
+    latch synopsis
+
+namespace std 
+{
+
+  class latch 
+  {
+  public:
+    constexpr explicit latch(ptrdiff_t __expected);
+    ~latch();
+
+    latch(const latch&) = delete;
+    latch& operator=(const latch&) = delete;
+    
+    void count_down(ptrdiff_t __update = 1);
+    bool try_wait() const noexcept;
+    void wait() const;
+    void arrive_and_wait(ptrdiff_t __update = 1);
+
+  private:
+    ptrdiff_t __counter; // exposition only
+  };
+  
+} 
+
+*/
+
+#include <__config>
+#include <__threading_support>
+#include <atomic>
+#include <cassert>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+#ifdef _LIBCPP_HAS_NO_THREADS
+# error <latch> is not supported on this single threaded system
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+class __latch_base
+{
+    alignas(64) atomic<ptrdiff_t> __counter;
+public:
+    inline _LIBCPP_INLINE_VISIBILITY
+    constexpr explicit __latch_base(ptrdiff_t __expected) 
+        : __counter(__expected) { }
+
+    ~__latch_base() = default;
+    __latch_base(const __latch_base&) = delete;
+    __latch_base& operator=(const __latch_base&) = delete;
+
+    inline _LIBCPP_INLINE_VISIBILITY
+    void count_down(ptrdiff_t __update = 1) 
+    {
+        assert(__update > 0);
+        auto const __old = __counter.fetch_sub(__update, memory_order_release);
+        assert(__old >= __update);
+        if(__old == __update)
+            __counter.notify_all();
+    }
+    inline _LIBCPP_INLINE_VISIBILITY
+    bool try_wait() const noexcept 
+    {
+        return __counter.load(memory_order_acquire) == 0;
+    }
+    inline _LIBCPP_INLINE_VISIBILITY
+    void wait() const 
+    {
+        while(1) {
+            auto const __current = __counter.load(memory_order_acquire);
+            if(__current == 0) 
+                return;
+            __counter.wait(__current, memory_order_relaxed)
+            ;
+        }
+    }
+    inline _LIBCPP_INLINE_VISIBILITY
+    void arrive_and_wait(ptrdiff_t __update = 1) 
+    {
+        count_down(__update);
+        wait();
+    }
+};
+
+using latch = __latch_base;
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif //_LIBCPP_LATCH

include/semaphore

+// -*- C++ -*-
+//===--------------------------- semaphore --------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_SEMAPHORE
+#define _LIBCPP_SEMAPHORE
+
+/*
+    semaphore synopsis
+
+namespace std {
+
+template<ptrdiff_t least_max_value = implementation-defined>
+class counting_semaphore 
+{
+public:
+static constexpr ptrdiff_t max() noexcept;
+
+constexpr explicit counting_semaphore(ptrdiff_t desired);
+~counting_semaphore();
+
+counting_semaphore(const counting_semaphore&) = delete;
+counting_semaphore& operator=(const counting_semaphore&) = delete;
+
+void release(ptrdiff_t __update = 1);
+void acquire();
+bool try_acquire() noexcept;
+template<class Rep, class Period>
+    bool try_acquire_for(const chrono::duration<Rep, Period>& __rel_time);
+template<class Clock, class Duration>
+    bool try_acquire_until(const chrono::time_point<Clock, Duration>& __abs_time);
+
+private:
+ptrdiff_t counter; // exposition only
+};
+
+using binary_semaphore = counting_semaphore<1>;
+
+}
+
+*/
+
+#include <__config>
+#include <__threading_support>
+#include <atomic>
+#include <cassert>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+#ifdef _LIBCPP_HAS_NO_THREADS
+# error <semaphore> is not supported on this single threaded system
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template<ptrdiff_t least_max_value>
+class __atomic_semaphore_base 
+{
+    _LIBCPP_INLINE_VISIBILITY
+    bool __fetch_sub_if_slow(ptrdiff_t __old) 
+    {
+        while (__old != 0) {
+            if (__count.compare_exchange_weak(__old, __old - 1, memory_order_acquire, memory_order_relaxed))
+                return true; 
+        }
+        return false;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __fetch_sub_if() 
+    {
+        ptrdiff_t __old = __count.load(memory_order_acquire);
+        if (__old == 0)
+            return false;
+        if(__count.compare_exchange_weak(__old, __old - 1, memory_order_acquire, memory_order_relaxed))
+            return true;
+        return __fetch_sub_if_slow(__old); // fail only if not __available
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __wait_slow() 
+    {
+        while (1) {
+            ptrdiff_t const __old = __count.load(memory_order_acquire);
+            if(__old != 0)
+                break;
+            __count.wait(__old, memory_order_relaxed);
+        }
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __acquire_slow_timed(chrono::nanoseconds const& __rel_time) 
+    {
+        return __libcpp_thread_poll_with_backoff([=]() {
+            ptrdiff_t const __old = __count.load(memory_order_acquire);
+            return __old != 0 && __fetch_sub_if_slow(__old);
+        }, __rel_time);
+    }
+    atomic<ptrdiff_t> __count;
+
+public:
+    static constexpr ptrdiff_t max() noexcept 
+    { 
+        return numeric_limits<ptrdiff_t>::max(); 
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __atomic_semaphore_base(ptrdiff_t __count) : __count(__count) { }
+
+    ~__atomic_semaphore_base() = default;
+
+    __atomic_semaphore_base(__atomic_semaphore_base const&) = delete;
+    __atomic_semaphore_base& operator=(__atomic_semaphore_base const&) = delete;
+
+    _LIBCPP_INLINE_VISIBILITY
+    void release(ptrdiff_t __update = 1) 
+    {
+        __count.fetch_add(__update, memory_order_release);
+        if(__update > 1)
+            __count.notify_all();
+        else
+            __count.notify_one();
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void acquire() 
+    {
+        while (!try_acquire())
+            __wait_slow();
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire() noexcept 
+    {
+        return __fetch_sub_if();
+    }
+
+    template <class Clock, class Duration>
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire_until(chrono::time_point<Clock, Duration> const& __abs_time) 
+    {
+        if (try_acquire())
+            return true;
+        else
+            return __acquire_slow_timed(__abs_time - Clock::now());
+    }
+
+    template <class Rep, class Period>
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire_for(chrono::duration<Rep, Period> const& __rel_time) 
+    {
+
+        if (try_acquire())
+            return true;
+        else
+            return __acquire_slow_timed(__rel_time);
+    }
+};
+
+#ifndef _LIBCPP_USE_NATIVE_SEMAPHORES
+
+template<>
+class __atomic_semaphore_base<1> {
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __acquire_slow_timed(chrono::nanoseconds const& __rel_time) 
+    {
+        return __libcpp_thread_poll_with_backoff([=]() {
+            return try_acquire();
+        }, __rel_time);
+    }
+    atomic<int> __available;
+
+public:
+    static constexpr ptrdiff_t max() noexcept { return 1; }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __atomic_semaphore_base(ptrdiff_t __available) : __available(__available) { }
+
+    ~__atomic_semaphore_base() = default;
+
+    __atomic_semaphore_base(__atomic_semaphore_base const&) = delete;
+    __atomic_semaphore_base& operator=(__atomic_semaphore_base const&) = delete;
+
+    _LIBCPP_INLINE_VISIBILITY
+    void release(ptrdiff_t __update = 1) 
+    {
+        assert(__update == 1);
+        __available.store(1, memory_order_release);
+        __available.notify_one();
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void acquire() 
+    {
+        while (!__builtin_expect(try_acquire(), 1))
+            __available.wait(0, memory_order_relaxed);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire() noexcept 
+    {
+        return 1 == __available.exchange(0, memory_order_acquire);
+    }
+
+    template <class Clock, class Duration>
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire_until(chrono::time_point<Clock, Duration> const& __abs_time) 
+    {
+        if (__builtin_expect(try_acquire(), 1))
+            return true;
+        else
+            return __acquire_slow_timed(__abs_time - Clock::now());
+    }
+
+    template <class Rep, class Period>
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire_for(chrono::duration<Rep, Period> const& __rel_time) 
+    {
+        if (__builtin_expect(try_acquire(), 1))
+            return true;
+        else
+            return __acquire_slow_timed(__rel_time);
+    }
+};
+
+#else
+
+class __sem_semaphore_base {
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __backfill(bool __success) 
+    {
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER
+        if(__success) {
+            auto const __back_amount = __backbuffer.fetch_sub(2, memory_order_acquire);
+            bool const __post_one = __back_amount > 0;
+            bool const __post_two = __back_amount > 1;
+            auto const __success = (!__post_one || __libcpp_semaphore_post(&__semaphore)) && 
+                                 (!__post_two || __libcpp_semaphore_post(&__semaphore));
+            assert(__success);
+            if(!__post_one || !__post_two)
+                __backbuffer.fetch_add(!__post_one ? 2 : 1, memory_order_relaxed);
+        }
+#endif
+        return __success;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __try_acquire_fast() 
+    {
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER
+
+        ptrdiff_t __old;
+        __libcpp_thread_poll_with_backoff([&]() {
+            __old = __frontbuffer.load(memory_order_relaxed);
+            return 0 != (__old >> 32);
+        }, chrono::microseconds(5));
+
+        // always steal if you can
+        while(__old >> 32)
+            if(__frontbuffer.compare_exchange_weak(__old, __old - (1ll << 32), memory_order_acquire))
+                return true;
+        // record we're waiting
+        __old = __frontbuffer.fetch_add(1ll, memory_order_release);
+        // ALWAYS steal if you can!
+        while(__old >> 32)
+            if(__frontbuffer.compare_exchange_weak(__old, __old - (1ll << 32), memory_order_acquire))
+                break;
+        // not going to wait after all
+        if(__old >> 32)
+            return __try_done(true);
+#endif
+        // the wait has begun...
+        return false;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __try_done(bool __success) 
+    {
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER
+        // record we're NOT waiting
+        __frontbuffer.fetch_sub(1ll, memory_order_release);
+#endif
+        return __backfill(__success);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __release_slow(ptrdiff_t __post_amount) 
+    {
+    #ifndef _LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER
+        bool const __post_one = __post_amount > 0;
+        bool const __post_two = __post_amount > 1;
+        if(__post_amount > 2)
+            __backbuffer.fetch_add(__post_amount - 2, memory_order_acq_rel);
+        auto const __success = (!__post_one || __libcpp_semaphore_post(&__semaphore)) && 
+                             (!__post_two || __libcpp_semaphore_post(&__semaphore));
+        assert(__success);
+    #else
+        for(; __post_amount; --__post_amount) {
+            auto const __success = __libcpp_semaphore_post(&__semaphore);
+            assert(__success);
+        }
+    #endif
+    }
+
+    __libcpp_semaphore_t __semaphore;
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER
+    atomic<ptrdiff_t> __frontbuffer;
+#endif
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER
+    atomic<ptrdiff_t> __backbuffer;
+#endif
+
+public:
+    static constexpr ptrdiff_t max() noexcept {
+        return _LIBCPP_SEMAPHORE_MAX;
+    }
+    
+    _LIBCPP_INLINE_VISIBILITY
+    __sem_semaphore_base(ptrdiff_t __count = 0) : __semaphore()
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER
+    , __frontbuffer(__count << 32)
+#endif
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER
+    , __backbuffer(0)
+#endif
+    { 
+        assert(__count <= max());
+        auto const __success = 
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER
+            __libcpp_semaphore_init(&__semaphore, 0);
+#else
+            __libcpp_semaphore_init(&__semaphore, __count);
+#endif
+        assert(__success);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    ~__sem_semaphore_base() {
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER
+        assert(0 == (__frontbuffer.load(memory_order_relaxed) & ~0u));
+#endif
+        auto const __success = __libcpp_semaphore_destroy(&__semaphore);
+        assert(__success);
+    }
+
+    __sem_semaphore_base(const __sem_semaphore_base&) = delete;
+    __sem_semaphore_base& operator=(const __sem_semaphore_base&) = delete;
+
+    _LIBCPP_INLINE_VISIBILITY
+    void release(ptrdiff_t __update = 1) 
+    {
+#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER
+        // boldly assume the semaphore is taken but uncontended
+        ptrdiff_t __old = 0;
+        // try to fast-release as long as it's uncontended
+        while(0 == (__old & ~0ul))
+            if(__frontbuffer.compare_exchange_weak(__old, __old + (__update << 32), memory_order_acq_rel))
+                return;
+#endif
+        // slow-release it is
+        __release_slow(__update);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void acquire() 
+    {
+        if(!__try_acquire_fast())
+            __try_done(__libcpp_semaphore_wait(&__semaphore));
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire() noexcept 
+    {
+        return try_acquire_for(chrono::nanoseconds(0));
+    }
+
+    template <class Clock, class Duration>
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire_until(chrono::time_point<Clock, Duration> const& __abs_time) 
+    {
+        auto const current = max(Clock::now(), __abs_time);
+        return try_acquire_for(chrono::duration_cast<chrono::nanoseconds>(__abs_time - current));
+    }
+
+    template <class Rep, class Period>
+    _LIBCPP_INLINE_VISIBILITY
+    bool try_acquire_for(chrono::duration<Rep, Period> const& __rel_time) 
+    {
+        return __try_acquire_fast() ||
+               __try_done(__libcpp_semaphore_wait_timed(&__semaphore, __rel_time));
+    }
+};
+
+#endif //_LIBCPP_HAS_NO_SEMAPHORES
+
+template<ptrdiff_t least_max_value>
+using __semaphore_base = 
+#ifdef _LIBCPP_USE_NATIVE_SEMAPHORES
+    typename conditional<least_max_value <= __sem_semaphore_base::max(), 
+                        __sem_semaphore_base, 
+                        __atomic_semaphore_base<least_max_value>>::type
+#else
+    __atomic_semaphore_base<least_max_value>
+#endif
+    ;
+
+template<ptrdiff_t least_max_value = INT_MAX>
+class counting_semaphore : public __semaphore_base<least_max_value> 
+{
+    static_assert(least_max_value <= __semaphore_base<least_max_value>::max(), "");
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    counting_semaphore(ptrdiff_t __count = 0) : __semaphore_base<least_max_value>(__count) { }
+    ~counting_semaphore() = default;
+
+    counting_semaphore(const counting_semaphore&) = delete;
+    counting_semaphore& operator=(const counting_semaphore&) = delete;
+};
+
+using binary_semaphore = counting_semaphore<1>;
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif //_LIBCPP_SEMAPHORE

include/stdexcept

public:
     ~__libcpp_refstring();
 
     const char* c_str() const _NOEXCEPT {return __imp_;}
 };
 #endif // !_LIBCPP_ABI_VCRUNTIME
 
 _LIBCPP_END_NAMESPACE_STD
 
-namespace std  // purposefully not using versioning namespace
+#ifdef _LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
+_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
+#else
+namespace std  // purposefully not versioned
 {
+#endif //_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
 
 class _LIBCPP_EXCEPTION_ABI logic_error
     : public exception
 {
 #ifndef _LIBCPP_ABI_VCRUNTIME
 private:
     _VSTD::__libcpp_refstring __imp_;
 public:
public:
     _LIBCPP_INLINE_VISIBILITY explicit underflow_error(const string& __s) : runtime_error(__s) {}
     _LIBCPP_INLINE_VISIBILITY explicit underflow_error(const char* __s)   : runtime_error(__s) {}
 
 #ifndef _LIBCPP_ABI_VCRUNTIME
     virtual ~underflow_error() _NOEXCEPT;
 #endif
 };
 
-}  // std
+#ifdef _LIBCPP_END_NAMESPACE_STD_NOVERSION
+_LIBCPP_END_NAMESPACE_STD_NOVERSION
+#else
+}
+#endif //_LIBCPP_END_NAMESPACE_STD_NOVERSION
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // in the dylib
 _LIBCPP_NORETURN _LIBCPP_FUNC_VIS void __throw_runtime_error(const char*);
 
 _LIBCPP_NORETURN inline _LIBCPP_INLINE_VISIBILITY
 void __throw_logic_error(const char*__msg)

include/type_traits

 
 template <class _CharT>
 using _IsCharLikeType = _And<is_standard_layout<_CharT>, is_trivial<_CharT> >;
 
 _LIBCPP_END_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 14
 // std::byte
+#ifdef _LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
+_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
+#else
 namespace std  // purposefully not versioned
 {
+#endif //_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION
 template <class _Integer>
   constexpr typename enable_if<is_integral_v<_Integer>, byte>::type &
   operator<<=(byte& __lhs, _Integer __shift) noexcept
   { return __lhs = __lhs << __shift; }
 
 template <class _Integer>
   constexpr typename enable_if<is_integral_v<_Integer>, byte>::type
   operator<< (byte  __lhs, _Integer __shift) noexcept
   { return static_cast<byte>(static_cast<unsigned char>(static_cast<unsigned int>(__lhs) << __shift)); }
 
 template <class _Integer>
   constexpr typename enable_if<is_integral_v<_Integer>, byte>::type &
   operator>>=(byte& __lhs, _Integer __shift) noexcept
   { return __lhs = __lhs >> __shift; }
 
 template <class _Integer>
   constexpr typename enable_if<is_integral_v<_Integer>, byte>::type
   operator>> (byte  __lhs, _Integer __shift) noexcept
   { return static_cast<byte>(static_cast<unsigned char>(static_cast<unsigned int>(__lhs) >> __shift)); }
 
 template <class _Integer>
   constexpr typename enable_if<is_integral_v<_Integer>, _Integer>::type
   to_integer(byte __b) noexcept { return static_cast<_Integer>(__b); }
 
+#ifdef _LIBCPP_END_NAMESPACE_STD_NOVERSION
+_LIBCPP_END_NAMESPACE_STD_NOVERSION
+#else
 }
+#endif //_LIBCPP_END_NAMESPACE_STD_NOVERSION
 #endif
 
 #endif  // _LIBCPP_TYPE_TRAITS

src/CMakeLists.txt

 set(LIBCXX_LIB_CMAKEFILES_DIR "${CMAKE_CURRENT_BINARY_DIR}${CMAKE_FILES_DIRECTORY}"  PARENT_SCOPE)
 
 # Get sources
 set(LIBCXX_SOURCES
   algorithm.cpp
   any.cpp
+  atomic.cpp
+  barrier.cpp
   bind.cpp
   charconv.cpp
   chrono.cpp
   condition_variable.cpp
   condition_variable_destructor.cpp
   debug.cpp
   exception.cpp
   functional.cpp

src/atomic.cpp

+//===------------------------- atomic.cpp ---------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_HAS_NO_THREADS
+#include "atomic"
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#ifndef _LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+
+__libcpp_contention_t __libcpp_contention_state_[ 256 /* < there's no magic in this number */ ];
+
+_LIBCPP_FUNC_VIS
+__libcpp_contention_t * __libcpp_contention_state(void const volatile * p) _NOEXCEPT {
+    return __libcpp_contention_state_ + ((std::uintptr_t)p & 255);
+}
+
+#endif //_LIBCPP_HAS_NO_THREAD_CONTENTION_TABLE
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif //_LIBCPP_HAS_NO_THREADS

src/barrier.cpp

+//===------------------------- barrier.cpp ---------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_HAS_NO_THREADS
+#include "barrier"
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_TREE_BARRIER) && !defined(_LIBCPP_HAS_NO_THREAD_FAVORITE_BARRIER_INDEX)
+
+_LIBCPP_EXPORTED_FROM_ABI
+thread_local ptrdiff_t __libcpp_thread_favorite_barrier_index = 0;
+
+#endif
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif //_LIBCPP_HAS_NO_THREADS

test/std/atomics/atomics.types.operations/atomics.types.operations.wait/atomic_wait.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+// XFAIL: c++98, c++03
+
+// <atomic>
+
+#include <atomic>
+#include <type_traits>
+#include <cassert>
+#include <thread>
+
+#include "test_macros.h"
+#include "../atomics.types.operations.req/atomic_helpers.h"
+
+template <class T>
+struct TestFn {
+  void operator()() const {
+    typedef std::atomic<T> A;
+
+    A t;
+    std::atomic_init(&t, T(1));
+    assert(std::atomic_load(&t) == T(1));
+    std::atomic_wait(&t, T(0));
+    std::thread t_([&](){ 
+      std::atomic_store(&t, T(3));
+      std::atomic_notify_one(&t);
+    });
+    std::atomic_wait(&t, T(1));
+    t_.join();
+
+    volatile A vt;
+    std::atomic_init(&vt, T(2));
+    assert(std::atomic_load(&vt) == T(2));
+    std::atomic_wait(&vt, T(1));
+    std::thread t2_([&](){ 
+      std::atomic_store(&vt, T(4));
+      std::atomic_notify_one(&vt);
+    });
+    std::atomic_wait(&vt, T(2));
+    t2_.join();
+  }
+};
+
+int main(int, char**)
+{
+    TestEachAtomicType<TestFn>()();
+
+  return 0;
+}

test/std/thread/thread.barrier/arrive.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <barrier>
+
+#include <barrier>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::barrier b(2);
+  
+  auto tok = b.arrive();
+  std::thread t([&](){ 
+    (void)b.arrive();
+  });
+  b.wait(std::move(tok));
+  t.join();
+
+  auto tok2 = b.arrive(2);
+  b.wait(std::move(tok2));
+  return 0;
+}

test/std/thread/thread.barrier/arrive_and_drop.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <barrier>
+
+#include <barrier>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::barrier b(2);
+
+  std::thread t([&](){ 
+    b.arrive_and_drop(); 
+  });
+
+  b.arrive_and_wait();
+  b.arrive_and_wait();
+  t.join();
+  return 0;
+}

test/std/thread/thread.barrier/arrive_and_wait.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <barrier>
+
+#include <barrier>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::barrier b(2);
+  
+  std::thread t([&](){ 
+    for(int i = 0; i < 10; ++i)
+      b.arrive_and_wait(); 
+  });
+  for(int i = 0; i < 10; ++i)
+    b.arrive_and_wait();
+  t.join();
+
+  return 0;
+}

test/std/thread/thread.barrier/completion.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <barrier>
+
+#include <barrier>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  int x = 0;
+  auto comp = [&]() { x += 1; };
+  std::barrier<decltype(comp)> b(2, comp);
+
+  std::thread t([&](){ 
+      for(int i = 0; i < 10; ++i)
+        b.arrive_and_wait(); 
+  });
+
+  for(int i = 0; i < 10; ++i)
+    b.arrive_and_wait();
+
+  assert(x == 10);
+  t.join();
+  return 0;
+}

test/std/thread/thread.barrier/version.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <barrier>
+
+#include <barrier>
+
+#include "test_macros.h"
+
+#ifndef _LIBCPP_VERSION
+#error _LIBCPP_VERSION not defined
+#endif
+
+int main(int, char**)
+{
+  return 0;
+}

test/std/thread/thread.latch/arrive_and_wait.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <latch>
+
+#include <latch>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::latch l(2);
+  
+  std::thread t([&](){ 
+      l.arrive_and_wait(); 
+  });
+  l.arrive_and_wait();
+  t.join();
+
+  return 0;
+}

test/std/thread/thread.latch/count_down.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <latch>
+
+#include <latch>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::latch l(2);
+  
+  l.count_down();
+  std::thread t([&](){ 
+    l.count_down();
+  });
+  l.wait();
+  t.join();
+
+  return 0;
+}

test/std/thread/thread.latch/try_wait.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <latch>
+
+#include <latch>
+#include <cassert>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::latch l(1);
+  
+  l.count_down();
+  bool const b = l.try_wait();
+  assert(b);
+
+  return 0;
+}

test/std/thread/thread.latch/version.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <latch>
+
+#include <latch>
+
+#include "test_macros.h"
+
+#ifndef _LIBCPP_VERSION
+#error _LIBCPP_VERSION not defined
+#endif
+
+int main(int, char**)
+{
+  return 0;
+}

test/std/thread/thread.semaphore/acquire.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <semaphore>
+
+#include <semaphore>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::counting_semaphore s(2);
+  
+  std::thread t([&](){ 
+    s.acquire();
+  });
+  t.join();
+
+  s.acquire();
+
+  return 0;
+}

test/std/thread/thread.semaphore/max.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <semaphore>
+
+#include <semaphore>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  static_assert(std::counting_semaphore<>::max() > 0);
+  static_assert(std::counting_semaphore<1>::max() >= 1);
+  static_assert(std::counting_semaphore<std::numeric_limits<int>::max()>::max() >= 1);
+  static_assert(std::counting_semaphore<std::numeric_limits<unsigned>::max()>::max() >= 1);
+  static_assert(std::counting_semaphore<std::numeric_limits<ptrdiff_t>::max()>::max() >= 1);
+  static_assert(std::counting_semaphore<1>::max() == std::binary_semaphore::max());  
+  return 0;
+}

test/std/thread/thread.semaphore/release.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <semaphore>
+
+#include <semaphore>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::counting_semaphore s(0);
+  
+  s.release();
+  s.acquire();
+
+  std::thread t([&](){ 
+    s.acquire();
+  });
+  s.release(2);
+  t.join();
+  s.acquire();
+
+  return 0;
+}

test/std/thread/thread.semaphore/timed.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <semaphore>
+
+#include <semaphore>
+#include <thread>
+#include <chrono>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  auto const start = std::chrono::steady_clock::now();
+
+  std::counting_semaphore s(0);
+  
+  assert(!s.try_acquire_until(start + std::chrono::milliseconds(250)));
+  assert(!s.try_acquire_for(std::chrono::milliseconds(250)));
+
+  std::thread t([&](){ 
+    std::this_thread::sleep_for(std::chrono::milliseconds(250));
+    s.release();
+    std::this_thread::sleep_for(std::chrono::milliseconds(250));
+    s.release();
+  });
+
+  assert(s.try_acquire_until(start + std::chrono::seconds(2)));
+  assert(s.try_acquire_for(std::chrono::seconds(2)));
+  t.join();
+
+  auto const end = std::chrono::steady_clock::now();
+  assert(end - start < std::chrono::seconds(10));
+
+  return 0;
+}

test/std/thread/thread.semaphore/try_acquire.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <semaphore>
+
+#include <semaphore>
+#include <thread>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+  std::counting_semaphore s(1);
+  
+  assert(s.try_acquire());
+  s.release();
+  assert(s.try_acquire());
+  s.release(2);
+  std::thread t([&](){ 
+    assert(s.try_acquire());
+  });
+  t.join();
+  assert(s.try_acquire());
+
+  return 0;
+}

test/std/thread/thread.semaphore/version.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: libcpp-has-no-threads
+
+// <semaphore>
+
+#include <semaphore>
+
+#include "test_macros.h"
+
+#ifndef _LIBCPP_VERSION
+#error _LIBCPP_VERSION not defined
+#endif
+
+int main(int, char**)
+{
+  return 0;
+}