libstdc++-v3/include/std/barrier - rust-lang/gcc - Git at Google

 // <barrier> -*- C++ -*-

 // Copyright (C) 2020-2025 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
 // terms of the GNU General Public License as published by the
 // Free Software Foundation; either version 3, or (at your option)
 // any later version.

 // This library is distributed in the hope that it will be useful,
 // but WITHOUT ANY WARRANTY; without even the implied warranty of
 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 // GNU General Public License for more details.

 // Under Section 7 of GPL version 3, you are granted additional
 // permissions described in the GCC Runtime Library Exception, version
 // 3.1, as published by the Free Software Foundation.

 // You should have received a copy of the GNU General Public License and
 // a copy of the GCC Runtime Library Exception along with this program;
 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 // <http://www.gnu.org/licenses/>.

 // This implementation is based on libcxx/include/barrier
 //===-- barrier.h --------------------------------------------------===//
 //
 // 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
 //
 //===---------------------------------------------------------------===//

 /** @file include/barrier
  *  This is a Standard C++ Library header.
  */

 #ifndef _GLIBCXX_BARRIER
 #define _GLIBCXX_BARRIER 1

 #ifdef _GLIBCXX_SYSHDR
 #pragma GCC system_header
 #endif

 #include <bits/requires_hosted.h> // threading primitive

 #define __glibcxx_want_barrier
 #include <bits/version.h>

 #ifdef __cpp_lib_barrier // C++ >= 20 && __cpp_aligned_new && lib_atomic_wait
 #include <bits/atomic_base.h>
 #include <bits/std_thread.h>
 #include <bits/unique_ptr.h>

 #include <array>

 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION

   struct __empty_completion
   {
     _GLIBCXX_ALWAYS_INLINE void
     operator()() noexcept
     { }
   };

 /*

 The default implementation of __tree_barrier is a classic tree barrier.

 It looks different from literature pseudocode for two main reasons:
  1. Threads that call into std::barrier functions do not provide indices,
     so a numbering step is added before the actual barrier algorithm,
     appearing as an N+1 round to the N rounds of the tree barrier.
  2. A great deal of attention has been paid to avoid cache line thrashing
     by flattening the tree structure into cache-line sized arrays, that
     are indexed in an efficient way.

 */

   enum class __barrier_phase_t : unsigned char { };

   struct __tree_barrier_base
   {
     static constexpr ptrdiff_t
     max() noexcept
     { return __PTRDIFF_MAX__ - 1; }

   protected:
     using __atomic_phase_ref_t = std::__atomic_ref<__barrier_phase_t>;
     using __atomic_phase_const_ref_t = std::__atomic_ref<const __barrier_phase_t>;
     static constexpr auto __phase_alignment =
 		    __atomic_phase_ref_t::required_alignment;

     using __tickets_t = std::array<__barrier_phase_t, 64>;
     struct alignas(64) /* naturally-align the heap state */ __state_t
     {
       alignas(__phase_alignment) __tickets_t __tickets;
     };

     ptrdiff_t _M_expected;
     __atomic_base<__state_t*> _M_state{nullptr};
     __atomic_base<ptrdiff_t> _M_expected_adjustment{0};
     alignas(__phase_alignment) __barrier_phase_t  _M_phase{};

     explicit constexpr
     __tree_barrier_base(ptrdiff_t __expected)
     : _M_expected(__expected)
     {
       __glibcxx_assert(__expected >= 0 && __expected <= max());

       if (!std::is_constant_evaluated())
 	_M_state.store(_M_alloc_state().release(), memory_order_release);
     }

     unique_ptr<__state_t[]>
     _M_alloc_state()
     {
       size_t const __count = (_M_expected + 1) >> 1;
       return std::make_unique<__state_t[]>(__count);
     }

     bool
     _M_arrive(__barrier_phase_t __old_phase, size_t __current)
     {
       const auto __old_phase_val = static_cast<unsigned char>(__old_phase);
       const auto __half_step =
 			 static_cast<__barrier_phase_t>(__old_phase_val + 1);
       const auto __full_step =
 			 static_cast<__barrier_phase_t>(__old_phase_val + 2);

       size_t __current_expected = _M_expected;
       __current %= ((_M_expected + 1) >> 1);

       __state_t* const __state = _M_state.load(memory_order_relaxed);

       for (int __round = 0; ; ++__round)
 	{
 	  if (__current_expected <= 1)
 	      return true;
 	  size_t const __end_node = ((__current_expected + 1) >> 1),
 		       __last_node = __end_node - 1;
 	  for ( ; ; ++__current)
 	    {
 	      if (__current == __end_node)
 		__current = 0;
 	      auto __expect = __old_phase;
 	      __atomic_phase_ref_t __phase(__state[__current]
 					      .__tickets[__round]);
 	      if (__current == __last_node && (__current_expected & 1))
 		{
 		  if (__phase.compare_exchange_strong(__expect, __full_step,
 						      memory_order_acq_rel))
 		    break;     // I'm 1 in 1, go to next __round
 		}
 	      else if (__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 (__phase.compare_exchange_strong(__expect, __full_step,
 						      memory_order_acq_rel))
 		    break;    // I'm 2 in 2, go to next __round
 		}
 	    }
 	  __current_expected = __last_node + 1;
 	  __current >>= 1;
 	}
     }
   };

   template<typename _CompletionF>
     class __tree_barrier : public __tree_barrier_base
     {
       [[no_unique_address]] _CompletionF _M_completion;

       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 3898. Possibly unintended preconditions for completion functions
       void _M_invoke_completion() noexcept { _M_completion(); }

     public:
       using arrival_token = __barrier_phase_t;

       constexpr
       __tree_barrier(ptrdiff_t __expected, _CompletionF __completion)
       : __tree_barrier_base(__expected), _M_completion(std::move(__completion))
       { }

       [[nodiscard]] arrival_token
       arrive(ptrdiff_t __update)
       {
 	__glibcxx_assert(__update > 0);
 	// FIXME: Check that update is less than or equal to the expected count
 	// for the current barrier phase.

 	std::hash<std::thread::id> __hasher;
 	size_t __current = __hasher(std::this_thread::get_id());
 	__atomic_phase_ref_t __phase(_M_phase);
 	const auto __old_phase = __phase.load(memory_order_relaxed);
 	const auto __cur = static_cast<unsigned char>(__old_phase);

 	if (__cur == 0 && !_M_state.load(memory_order_relaxed)) [[unlikely]]
 	  {
 	    auto __p = _M_alloc_state();
 	    __state_t* __val = nullptr;
 	    if (_M_state.compare_exchange_strong(__val, __p.get(),
 						 memory_order_seq_cst,
 						 memory_order_acquire))
 	      __p.release();
 	  }

 	for (; __update; --__update)
 	  {
 	    if (_M_arrive(__old_phase, __current))
 	      {
 		_M_invoke_completion();
 		_M_expected += _M_expected_adjustment.load(memory_order_relaxed);
 		_M_expected_adjustment.store(0, memory_order_relaxed);
 		auto __new_phase = static_cast<__barrier_phase_t>(__cur + 2);
 		__phase.store(__new_phase, memory_order_release);
 		__phase.notify_all();
 	      }
 	  }
 	return __old_phase;
       }

       void
       wait(arrival_token&& __old_phase) const
       {
 	__atomic_phase_const_ref_t __phase(_M_phase);
 	__phase.wait(__old_phase, memory_order_acquire);
       }

       void
       arrive_and_drop()
       {
 	_M_expected_adjustment.fetch_sub(1, memory_order_relaxed);
 	(void)arrive(1);
       }
     };

   template<typename _CompletionF = __empty_completion>
     class barrier
     {
       static_assert(is_invocable_v<_CompletionF&>);

       // Note, we may introduce a "central" barrier algorithm at some point
       // for more space constrained targets
       using __algorithm_t = __tree_barrier<_CompletionF>;
       __algorithm_t _M_b;

     public:
       class arrival_token final
       {
       public:
 	arrival_token(arrival_token&&) = default;
 	arrival_token& operator=(arrival_token&&) = default;
 	~arrival_token() = default;

       private:
 	friend class barrier;
 	using __token = typename __algorithm_t::arrival_token;
 	explicit arrival_token(__token __tok) noexcept : _M_tok(__tok) { }
 	__token _M_tok;
       };

       static constexpr ptrdiff_t
       max() noexcept
       { return __algorithm_t::max(); }

       constexpr explicit
       barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
       : _M_b(__count, std::move(__completion))
       { }

       barrier(barrier const&) = delete;
       barrier& operator=(barrier const&) = delete;

       [[nodiscard]] arrival_token
       arrive(ptrdiff_t __update = 1)
       { return arrival_token{_M_b.arrive(__update)}; }

       void
       wait(arrival_token&& __phase) const
       { _M_b.wait(std::move(__phase._M_tok)); }

       void
       arrive_and_wait()
       { wait(arrive()); }

       void
       arrive_and_drop()
       { _M_b.arrive_and_drop(); }
     };

 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 #endif // __cpp_lib_barrier
 #endif // _GLIBCXX_BARRIER
	// <barrier> -- C++ --

	// Copyright (C) 2020-2025 Free Software Foundation, Inc.
	//
	// This file is part of the GNU ISO C++ Library. This library is free
	// software; you can redistribute it and/or modify it under the
	// terms of the GNU General Public License as published by the
	// Free Software Foundation; either version 3, or (at your option)
	// any later version.

	// This library is distributed in the hope that it will be useful,
	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	// GNU General Public License for more details.

	// Under Section 7 of GPL version 3, you are granted additional
	// permissions described in the GCC Runtime Library Exception, version
	// 3.1, as published by the Free Software Foundation.

	// You should have received a copy of the GNU General Public License and
	// a copy of the GCC Runtime Library Exception along with this program;
	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	// <http://www.gnu.org/licenses/>.

	// This implementation is based on libcxx/include/barrier
	//===-- barrier.h --------------------------------------------------===//
	//
	// 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
	//
	//===---------------------------------------------------------------===//

	/** @file include/barrier
	* This is a Standard C++ Library header.
	*/

	#ifndef _GLIBCXX_BARRIER
	#define _GLIBCXX_BARRIER 1

	#ifdef _GLIBCXX_SYSHDR
	#pragma GCC system_header
	#endif

	#include <bits/requires_hosted.h> // threading primitive

	#define __glibcxx_want_barrier
	#include <bits/version.h>

	#ifdef __cpp_lib_barrier // C++ >= 20 && __cpp_aligned_new && lib_atomic_wait
	#include <bits/atomic_base.h>
	#include <bits/std_thread.h>
	#include <bits/unique_ptr.h>

	#include <array>

	namespace std _GLIBCXX_VISIBILITY(default)
	{
	_GLIBCXX_BEGIN_NAMESPACE_VERSION

	struct __empty_completion
	{
	_GLIBCXX_ALWAYS_INLINE void
	operator()() noexcept
	{ }
	};

	/*

	The default implementation of __tree_barrier is a classic tree barrier.

	It looks different from literature pseudocode for two main reasons:
	1. Threads that call into std::barrier functions do not provide indices,
	so a numbering step is added before the actual barrier algorithm,
	appearing as an N+1 round to the N rounds of the tree barrier.
	2. A great deal of attention has been paid to avoid cache line thrashing
	by flattening the tree structure into cache-line sized arrays, that
	are indexed in an efficient way.

	*/

	enum class __barrier_phase_t : unsigned char { };

	struct __tree_barrier_base
	{
	static constexpr ptrdiff_t
	max() noexcept
	{ return __PTRDIFF_MAX__ - 1; }

	protected:
	using __atomic_phase_ref_t = std::__atomic_ref<__barrier_phase_t>;
	using __atomic_phase_const_ref_t = std::__atomic_ref<const __barrier_phase_t>;
	static constexpr auto __phase_alignment =
	__atomic_phase_ref_t::required_alignment;

	using __tickets_t = std::array<__barrier_phase_t, 64>;
	struct alignas(64) /* naturally-align the heap state */ __state_t
	{
	alignas(__phase_alignment) __tickets_t __tickets;
	};

	ptrdiff_t _M_expected;
	__atomic_base<__state_t*> _M_state{nullptr};
	__atomic_base<ptrdiff_t> _M_expected_adjustment{0};
	alignas(__phase_alignment) __barrier_phase_t _M_phase{};

	explicit constexpr
	__tree_barrier_base(ptrdiff_t __expected)
	: _M_expected(__expected)
	{
	__glibcxx_assert(__expected >= 0 && __expected <= max());

	if (!std::is_constant_evaluated())
	_M_state.store(_M_alloc_state().release(), memory_order_release);
	}

	unique_ptr<__state_t[]>
	_M_alloc_state()
	{
	size_t const __count = (_M_expected + 1) >> 1;
	return std::make_unique<__state_t[]>(__count);
	}

	bool
	_M_arrive(__barrier_phase_t __old_phase, size_t __current)
	{
	const auto __old_phase_val = static_cast<unsigned char>(__old_phase);
	const auto __half_step =
	static_cast<__barrier_phase_t>(__old_phase_val + 1);
	const auto __full_step =
	static_cast<__barrier_phase_t>(__old_phase_val + 2);

	size_t __current_expected = _M_expected;
	__current %= ((_M_expected + 1) >> 1);

	__state_t* const __state = _M_state.load(memory_order_relaxed);

	for (int __round = 0; ; ++__round)
	{
	if (__current_expected <= 1)
	return true;
	size_t const __end_node = ((__current_expected + 1) >> 1),
	__last_node = __end_node - 1;
	for ( ; ; ++__current)
	{
	if (__current == __end_node)
	__current = 0;
	auto __expect = __old_phase;
	__atomic_phase_ref_t __phase(__state[__current]
	.__tickets[__round]);
	if (__current == __last_node && (__current_expected & 1))
	{
	if (__phase.compare_exchange_strong(__expect, __full_step,
	memory_order_acq_rel))
	break; // I'm 1 in 1, go to next __round
	}
	else if (__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 (__phase.compare_exchange_strong(__expect, __full_step,
	memory_order_acq_rel))
	break; // I'm 2 in 2, go to next __round
	}
	}
	__current_expected = __last_node + 1;
	__current >>= 1;
	}
	}
	};

	template<typename _CompletionF>
	class __tree_barrier : public __tree_barrier_base
	{
	[[no_unique_address]] _CompletionF _M_completion;

	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 3898. Possibly unintended preconditions for completion functions
	void _M_invoke_completion() noexcept { _M_completion(); }

	public:
	using arrival_token = __barrier_phase_t;

	constexpr
	__tree_barrier(ptrdiff_t __expected, _CompletionF __completion)
	: __tree_barrier_base(__expected), _M_completion(std::move(__completion))
	{ }

	[[nodiscard]] arrival_token
	arrive(ptrdiff_t __update)
	{
	__glibcxx_assert(__update > 0);
	// FIXME: Check that update is less than or equal to the expected count
	// for the current barrier phase.

	std::hash<std::thread::id> __hasher;
	size_t __current = __hasher(std::this_thread::get_id());
	__atomic_phase_ref_t __phase(_M_phase);
	const auto __old_phase = __phase.load(memory_order_relaxed);
	const auto __cur = static_cast<unsigned char>(__old_phase);

	if (__cur == 0 && !_M_state.load(memory_order_relaxed)) [[unlikely]]
	{
	auto __p = _M_alloc_state();
	__state_t* __val = nullptr;
	if (_M_state.compare_exchange_strong(__val, __p.get(),
	memory_order_seq_cst,
	memory_order_acquire))
	__p.release();
	}

	for (; __update; --__update)
	{
	if (_M_arrive(__old_phase, __current))
	{
	_M_invoke_completion();
	_M_expected += _M_expected_adjustment.load(memory_order_relaxed);
	_M_expected_adjustment.store(0, memory_order_relaxed);
	auto __new_phase = static_cast<__barrier_phase_t>(__cur + 2);
	__phase.store(__new_phase, memory_order_release);
	__phase.notify_all();
	}
	}
	return __old_phase;
	}

	void
	wait(arrival_token&& __old_phase) const
	{
	__atomic_phase_const_ref_t __phase(_M_phase);
	__phase.wait(__old_phase, memory_order_acquire);
	}

	void
	arrive_and_drop()
	{
	_M_expected_adjustment.fetch_sub(1, memory_order_relaxed);
	(void)arrive(1);
	}
	};

	template<typename _CompletionF = __empty_completion>
	class barrier
	{
	static_assert(is_invocable_v<_CompletionF&>);

	// Note, we may introduce a "central" barrier algorithm at some point
	// for more space constrained targets
	using __algorithm_t = __tree_barrier<_CompletionF>;
	__algorithm_t _M_b;

	public:
	class arrival_token final
	{
	public:
	arrival_token(arrival_token&&) = default;
	arrival_token& operator=(arrival_token&&) = default;
	~arrival_token() = default;

	private:
	friend class barrier;
	using __token = typename __algorithm_t::arrival_token;
	explicit arrival_token(__token __tok) noexcept : _M_tok(__tok) { }
	__token _M_tok;
	};

	static constexpr ptrdiff_t
	max() noexcept
	{ return __algorithm_t::max(); }

	constexpr explicit
	barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
	: _M_b(__count, std::move(__completion))
	{ }

	barrier(barrier const&) = delete;
	barrier& operator=(barrier const&) = delete;

	[[nodiscard]] arrival_token
	arrive(ptrdiff_t __update = 1)
	{ return arrival_token{_M_b.arrive(__update)}; }

	void
	wait(arrival_token&& __phase) const
	{ _M_b.wait(std::move(__phase._M_tok)); }

	void
	arrive_and_wait()
	{ wait(arrive()); }

	void
	arrive_and_drop()
	{ _M_b.arrive_and_drop(); }
	};

	_GLIBCXX_END_NAMESPACE_VERSION
	} // namespace
	#endif // __cpp_lib_barrier
	#endif // _GLIBCXX_BARRIER