diff --git a/libcxx/docs/Status/Cxx20Papers.csv b/libcxx/docs/Status/Cxx20Papers.csv --- a/libcxx/docs/Status/Cxx20Papers.csv +++ b/libcxx/docs/Status/Cxx20Papers.csv @@ -104,7 +104,7 @@ "`P0553R4 `__","LWG","Bit operations","Cologne","|Complete|","9.0" "`P0631R8 `__","LWG","Math Constants","Cologne","|Complete|","11.0" "`P0645R10 `__","LWG","Text Formatting","Cologne","|Complete| [#note-P0645]_","14.0" -"`P0660R10 `__","LWG","Stop Token and Joining Thread, Rev 10","Cologne","","" +"`P0660R10 `__","LWG","Stop Token and Joining Thread, Rev 10","Cologne","In Progress","" "`P0784R7 `__","CWG","More constexpr containers","Cologne","|Complete|","12.0" "`P0980R1 `__","LWG","Making std::string constexpr","Cologne","|Complete|","15.0" "`P1004R2 `__","LWG","Making std::vector constexpr","Cologne","|Complete|","15.0" diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -542,6 +542,10 @@ __ranges/zip_view.h __split_buffer __std_stream + __stop_token/stop_callback.h + __stop_token/stop_source.h + __stop_token/stop_state.h + __stop_token/stop_token.h __string/char_traits.h __string/extern_template_lists.h __support/android/locale_bionic.h @@ -850,6 +854,7 @@ stdint.h stdio.h stdlib.h + stop_token streambuf string string.h diff --git a/libcxx/include/__stop_token/stop_callback.h b/libcxx/include/__stop_token/stop_callback.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__stop_token/stop_callback.h @@ -0,0 +1,27 @@ +// -*- 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___STOP_TOKEN_STOP_CALLBACK_H +#define _LIBCPP___STOP_TOKEN_STOP_CALLBACK_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___STOP_TOKEN_STOP_TOKEN_H diff --git a/libcxx/include/__stop_token/stop_source.h b/libcxx/include/__stop_token/stop_source.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__stop_token/stop_source.h @@ -0,0 +1,96 @@ +// -*- 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___STOP_TOKEN_STOP_SOURCE_H +#define _LIBCPP___STOP_TOKEN_STOP_SOURCE_H + +#include <__config> +#include <__stop_token/stop_token.h> +#include <__stop_token/stop_state.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +struct nostopstate_t { + explicit nostopstate_t() = default; +}; + +inline constexpr nostopstate_t nostopstate{}; + +class stop_source { +public: + stop_source() : __ref_counted_state_(__ref_counted_stop_state::__new_state_from_stop_source_tag{}) {} + + explicit stop_source(nostopstate_t) noexcept {} + + stop_source(const stop_source& __other) noexcept : __ref_counted_state_(__other.__ref_counted_state_) { + if (__ref_counted_state_.__has_state()) { + __ref_counted_state_.get()->__increment_stop_source_counter(); + } + } + + stop_source(stop_source&& __other) noexcept = default; + + stop_source& operator=(const stop_source& __other) noexcept { + if (__ref_counted_state_ != __other.__ref_counted_state_) { + auto __tmp = std::move(__ref_counted_state_); + __ref_counted_state_ = __other.__ref_counted_state_; + if (__ref_counted_state_.__has_state()) { + __ref_counted_state_.get()->__increment_stop_source_counter(); + } + if (__tmp.__has_state()) { + __tmp.get()->__decrement_stop_source_counter(); + } + } + return *this; + } + + stop_source& operator=(stop_source&&) noexcept = default; + + ~stop_source() { + if (__ref_counted_state_.__has_state()) { + __ref_counted_state_.get()->__decrement_stop_source_counter(); + } + } + + void swap(stop_source& __other) noexcept { __ref_counted_state_.__swap(__other.__ref_counted_state_); } + + [[nodiscard]] stop_token get_token() const noexcept { return stop_token(__ref_counted_state_); } + + [[nodiscard]] bool stop_possible() const noexcept { return __ref_counted_state_.__has_state(); } + + [[nodiscard]] bool stop_requested() const noexcept { + return __ref_counted_state_.__has_state() && __ref_counted_state_.get()->__stop_requested(); + } + + bool request_stop() noexcept { + if (!__ref_counted_state_.__has_state()) { + return false; + } + return __ref_counted_state_.get()->__request_stop(); + } + + [[nodiscard]] friend bool operator==(const stop_source&, const stop_source&) noexcept = default; + + friend void swap(stop_source& __lhs, stop_source& __rhs) noexcept { __lhs.swap(__rhs); } + +private: + __ref_counted_stop_state __ref_counted_state_; +}; + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___STOP_TOKEN_STOP_SOURCE_H diff --git a/libcxx/include/__stop_token/stop_state.h b/libcxx/include/__stop_token/stop_state.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__stop_token/stop_state.h @@ -0,0 +1,291 @@ +// -*- 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___STOP_TOKEN_STOP_STATE_H +#define _LIBCPP___STOP_TOKEN_STOP_STATE_H + +#include <__config> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +struct __stop_callback_base { +protected: + friend struct __stop_state; + + using __callback_fn_t = void(__stop_callback_base*) noexcept; + explicit __stop_callback_base(__callback_fn_t* __callback_fn) : __callback_fn_(__callback_fn) {} + + void __invoke() noexcept { __callback_fn_(this); } + + __callback_fn_t* __callback_fn_; + __stop_callback_base* __next_ = nullptr; + __stop_callback_base* __prev_ = nullptr; + std::atomic __completed_ = false; +}; + +struct __stop_state { + static constexpr uint32_t __stop_requested_bit = 1; + static constexpr uint32_t __locked_bit = 1 << 1; + static constexpr uint32_t __stop_source_counter_shift = 2; + + __stop_callback_base* __cb_head_ = nullptr; + + // 31 - 2 | 1 | 0 | + // stop_source counter | locked | stop_requested | + std::atomic __state_ = 0; + + // reference count for stop_token + stop_callback + stop_source + // used by __ref_counted_stop_state, put it here for better layout + std::atomic __ref_count_ = 0; + + std::thread::id __requesting_thread_; + + __stop_state(uint32_t __state, uint32_t __ref_count) noexcept : __state_(__state), __ref_count_(__ref_count) {} + + void __increment_stop_source_counter() noexcept { + __state_.fetch_add(1 << __stop_source_counter_shift, std::memory_order_relaxed); + } + + void __decrement_stop_source_counter() noexcept { + __state_.fetch_sub(1 << __stop_source_counter_shift, std::memory_order_relaxed); + } + + bool __stop_requested() const noexcept { + // acquire because [thread.stoptoken.intro] A call to request_stop that returns true + // synchronizes with a call to stop_requested on an associated stop_token or stop_source + // object that returns true. + // request_stop's compare_exchange_week has release which syncs with this acquire + return (__state_.load(std::memory_order_acquire) & __stop_requested_bit) != 0; + } + + bool __stop_possible_for_stop_token() const noexcept { + // [stoptoken.mem] false if "a stop request was not made and there are no associated stop_source objects" + auto __curent_state = __state_.load(std::memory_order_acquire); + return ((__curent_state & __stop_requested_bit) != 0) || ((__curent_state >> __stop_source_counter_shift) != 0); + } + + bool __request_stop() noexcept { + if (!__try_lock_for_request_stop()) { + return false; + } + __requesting_thread_ = std::this_thread::get_id(); + + while (__cb_head_) { + auto __cb = __cb_head_; + __cb_head_ = __cb_head_->__next_; + if (__cb_head_) { + __cb_head_->__prev_ = nullptr; + } + + __unlock(); + + __cb->__invoke(); + + __cb->__completed_.store(true, std::memory_order_release); + + __lock(); + } + + __unlock(); + return true; + } + + bool __try_lock_for_request_stop() noexcept { + auto __current_state = __state_.load(std::memory_order_relaxed); + do { + while (true) { + if ((__current_state & __stop_requested_bit) != 0) { + // already stop requested + return false; + } else if ((__current_state & __locked_bit) != 0) { + // another thread is trying to lock the state to add/remove callbacks + // we need to wait + std::this_thread::yield(); + // We don't need the acq/rel ordering for adding callbacks at this stage + // as we are stuck in this loop. + // We only need it when we passe the compare_exchange_weak to run the callbacks + __current_state = __state_.load(std::memory_order_relaxed); + } else { + // for now, __stop_requested_bit == 0 && __locked_bit == 0 + // let's try compare_exchange_weak + break; + } + } + } while (!__state_.compare_exchange_weak( + __current_state, + __current_state | __locked_bit | __stop_requested_bit, // set locked and requested bit at the same time + // acq because [thread.stoptoken.intro] Registration of a callback synchronizes with the invocation of that callback. + // acquire so that we can see other threads writes to callbacks + // rel because [thread.stoptoken.intro] A call to request_stop that returns true synchronizes with a call + // to stop_requested on an associated stop_token or stop_source object that returns true. + std::memory_order_acq_rel, + std::memory_order_relaxed)); // on failure we are stuck in the loop and no need for memory order + + // successfully locked and set the requested bit + return true; + } + + void __unlock() noexcept { __state_.fetch_and(~__locked_bit, std::memory_order_release); } + + void __lock() noexcept { + auto __current_state = __state_.load(std::memory_order_relaxed); + do { + while ((__current_state & __locked_bit) != 0) { + std::this_thread::yield(); + __current_state = __state_.load(std::memory_order_relaxed); + } + } while (!__state_.compare_exchange_weak( + __current_state, __current_state | __locked_bit, std::memory_order_acquire, std::memory_order_relaxed)); + } + + void __add_callback(__stop_callback_base* __cb) noexcept { + auto __current_state = __state_.load(std::memory_order_relaxed); + do { + while (true) { + if ((__current_state & __stop_requested_bit) != 0) { + // already stop requested, synchronously run the callback + __cb->__invoke(); + return; + } else if ((__current_state >> __stop_source_counter_shift) == 0) { + // no stop source. no need to add callback + return; + } else if ((__current_state & __locked_bit) != 0) { + // another thread is trying to lock the state to add/remove callbacks, wait + std::this_thread::yield(); + __current_state = __state_.load(std::memory_order_relaxed); + } else { + break; + } + } + } while (!__state_.compare_exchange_weak( + __current_state, __current_state | __locked_bit, std::memory_order_acquire, std::memory_order_relaxed)); + + // locked now + + __cb->__next_ = __cb_head_; + if (__cb_head_) { + __cb_head_->__prev_ = __cb; + } + __cb_head_ = __cb; + + __unlock(); + // [thread.stoptoken.intro] Registration of a callback synchronizes with the invocation of that callback. + } + + void __remove_callback(__stop_callback_base* __cb) noexcept { + __lock(); + + if (__cb->__prev_) { + // previous exists, set its next to our next to skip __cb + __cb->__prev_->__next_ = __cb->__next_; + if (__cb->__next_) { + __cb->__next_->__prev_ = __cb->__prev_; + } + __unlock(); + return; + } else if (__cb == __cb_head_) { + // remove head + __cb_head_ = __cb_head_->__next_; + if (__cb_head_) { + __cb_head_->__prev_ = nullptr; + } + __unlock(); + return; + } else { + // __cb is not in the list. There is a stop request that attempts to call the callback (and removed it from the list) + + auto __requested_thread = __requesting_thread_; + __unlock(); + + if (std::this_thread::get_id() != __requested_thread) { + // [stopcallback.cons] If callback is concurrently executing on another thread, then the return + // from the invocation of callback strongly happens before ([intro.races]) callback is destroyed. + while (!__cb->__completed_.load(std::memory_order_acquire)) { + std::this_thread::yield(); + } + } + } + } +}; + +struct __ref_counted_stop_state { + struct __new_state_from_stop_source_tag {}; + + __ref_counted_stop_state() = default; + + __ref_counted_stop_state(__new_state_from_stop_source_tag) + : __stop_state_(new __stop_state(/*state=*/1 << __stop_state::__stop_source_counter_shift, /*__ref_count=*/1)) {} + + __ref_counted_stop_state(const __ref_counted_stop_state& __other) noexcept : __stop_state_(__other.__stop_state_) { + if (__stop_state_) { + __increment_ref_count(__stop_state_); + } + } + + __ref_counted_stop_state(__ref_counted_stop_state&& __other) noexcept : __stop_state_(__other.__stop_state_) { + __other.__stop_state_ = nullptr; + } + + __ref_counted_stop_state& operator=(const __ref_counted_stop_state& __other) noexcept { + if (__other.__stop_state_ != __stop_state_) { + if (__other.__stop_state_) { + __increment_ref_count(__other.__stop_state_); + } + if (__stop_state_) { + __decrement_ref_count(__stop_state_); + } + __stop_state_ = __other.__stop_state_; + } + return *this; + } + + __ref_counted_stop_state& operator=(__ref_counted_stop_state&& __other) noexcept { + std::swap(__stop_state_, __other.__stop_state_); + return *this; + } + + ~__ref_counted_stop_state() { + if (__stop_state_) { + __decrement_ref_count(__stop_state_); + } + } + + __stop_state* get() const noexcept { return __stop_state_; } + + bool __has_state() const noexcept { return __stop_state_ != nullptr; } + + void __swap(__ref_counted_stop_state& __other) { std::swap(__stop_state_, __other.__stop_state_); } + + friend bool constexpr operator==(const __ref_counted_stop_state&, const __ref_counted_stop_state&) = default; + +private: + __stop_state* __stop_state_ = nullptr; + + void __increment_ref_count(__stop_state* __state) { __state->__ref_count_.fetch_add(1, std::memory_order_relaxed); } + + void __decrement_ref_count(__stop_state* __state) { + if (__state->__ref_count_.fetch_sub(1, std::memory_order_acq_rel) == 1) { + delete __state; + } + } +}; + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___STOP_TOKEN_STOP_STATE_H diff --git a/libcxx/include/__stop_token/stop_token.h b/libcxx/include/__stop_token/stop_token.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__stop_token/stop_token.h @@ -0,0 +1,60 @@ +// -*- 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___STOP_TOKEN_STOP_TOKEN_H +#define _LIBCPP___STOP_TOKEN_STOP_TOKEN_H + +#include <__config> +#include <__stop_token/stop_state.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +class stop_token { +public: + stop_token() noexcept = default; + + stop_token(const stop_token&) noexcept = default; + stop_token(stop_token&&) noexcept = default; + stop_token& operator=(const stop_token&) noexcept = default; + stop_token& operator=(stop_token&&) noexcept = default; + ~stop_token() = default; + + void swap(stop_token& __other) noexcept { __ref_counted_state_.__swap(__other.__ref_counted_state_); } + + [[nodiscard]] bool stop_requested() const noexcept { + return __ref_counted_state_.__has_state() && __ref_counted_state_.get()->__stop_requested(); + } + + [[nodiscard]] bool stop_possible() const noexcept { + return __ref_counted_state_.__has_state() && __ref_counted_state_.get()->__stop_possible_for_stop_token(); + } + + [[nodiscard]] friend bool operator==(const stop_token&, const stop_token&) noexcept = default; + + friend void swap(stop_token& __lhs, stop_token& __rhs) noexcept { __lhs.swap(__rhs); } + +private: + __ref_counted_stop_state __ref_counted_state_; + +private: + friend class stop_source; + explicit stop_token(const __ref_counted_stop_state& __state) : __ref_counted_state_(__state) {} +}; + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___STOP_TOKEN_STOP_TOKEN_H diff --git a/libcxx/include/stop_token b/libcxx/include/stop_token new file mode 100644 --- /dev/null +++ b/libcxx/include/stop_token @@ -0,0 +1,35 @@ +// -*- 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_STOP_TOKEN +#define _LIBCPP_STOP_TOKEN + +/* + +namespace std { + // [stoptoken], class stop_token + class stop_token; + + // [stopsource], class stop_source + class stop_source; + + // no-shared-stop-state indicator + struct nostopstate_t { + explicit nostopstate_t() = default; + }; + inline constexpr nostopstate_t nostopstate{}; + + // [stopcallback], class template stop_callback + template + class stop_callback; + +*/ + +#endif // _LIBCPP_STOP_TOKEN + diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -573,6 +573,10 @@ #include <__ranges/zip_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/zip_view.h'}} #include <__split_buffer> // expected-error@*:* {{use of private header from outside its module: '__split_buffer'}} #include <__std_stream> // expected-error@*:* {{use of private header from outside its module: '__std_stream'}} +#include <__stop_token/stop_callback.h> // expected-error@*:* {{use of private header from outside its module: '__stop_token/stop_callback.h'}} +#include <__stop_token/stop_source.h> // expected-error@*:* {{use of private header from outside its module: '__stop_token/stop_source.h'}} +#include <__stop_token/stop_state.h> // expected-error@*:* {{use of private header from outside its module: '__stop_token/stop_state.h'}} +#include <__stop_token/stop_token.h> // expected-error@*:* {{use of private header from outside its module: '__stop_token/stop_token.h'}} #include <__string/char_traits.h> // expected-error@*:* {{use of private header from outside its module: '__string/char_traits.h'}} #include <__string/extern_template_lists.h> // expected-error@*:* {{use of private header from outside its module: '__string/extern_template_lists.h'}} #include <__thread/poll_with_backoff.h> // expected-error@*:* {{use of private header from outside its module: '__thread/poll_with_backoff.h'}} diff --git a/libcxx/utils/generate_header_inclusion_tests.py b/libcxx/utils/generate_header_inclusion_tests.py --- a/libcxx/utils/generate_header_inclusion_tests.py +++ b/libcxx/utils/generate_header_inclusion_tests.py @@ -73,6 +73,7 @@ "initializer_list": "11", "optional": "17", "ranges": "20", + "stop_token": "20", "string_view": "17", "syncstream": "20", "system_error": "11",