libcxx/src/barrier.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include <__config>
  10
  11 #ifndef _LIBCPP_HAS_NO_THREADS
  12
  13 #include <barrier>
  14 #include <thread>
  15
  16 _LIBCPP_BEGIN_NAMESPACE_STD
  17
  18 #if !defined(_LIBCPP_HAS_NO_TREE_BARRIER)
  19
  20 class __barrier_algorithm_base {
  21 public:
  22     struct alignas(64) /* naturally-align the heap state */ __state_t
  23     {
  24         struct {
  25           __atomic_base<__barrier_phase_t> __phase{0};
  26         } __tickets[64];
  27     };
  28
  29     ptrdiff_t&              __expected;
  30     unique_ptr<__state_t[]> __state;
  31
  32     _LIBCPP_HIDDEN
  33     __barrier_algorithm_base(ptrdiff_t& __expected)
  34         : __expected(__expected)
  35     {
  36         size_t const __count = (__expected + 1) >> 1;
  37         __state = unique_ptr<__state_t[]>(new __state_t[__count]);
  38     }
  39     _LIBCPP_HIDDEN
  40     bool __arrive(__barrier_phase_t __old_phase)
  41     {
  42         __barrier_phase_t const __half_step = __old_phase + 1,
  43                                 __full_step = __old_phase + 2;
  44         size_t __current_expected = __expected,
  45             __current = hash<thread::id>()(this_thread::get_id()) % ((__expected + 1) >> 1);
  46         for(int __round = 0;; ++__round) {
  47             if(__current_expected <= 1)
  48                 return true;
  49             size_t const __end_node = ((__current_expected + 1) >> 1),
  50                          __last_node = __end_node - 1;
  51             for(;;++__current) {
  52                 if(__current == __end_node)
  53                 __current = 0;
  54                 __barrier_phase_t expect = __old_phase;
  55                 if(__current == __last_node && (__current_expected & 1))
  56                 {
  57                     if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
  58                         break;    // I'm 1 in 1, go to next __round
  59                 }
  60                 else if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __half_step, memory_order_acq_rel))
  61                 {
  62                     return false; // I'm 1 in 2, done with arrival
  63                 }
  64                 else if(expect == __half_step)
  65                 {
  66                     if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
  67                         break;    // I'm 2 in 2, go to next __round
  68                 }
  69             }
  70             __current_expected = __last_node + 1;
  71             __current >>= 1;
  72         }
  73     }
  74 };
  75
  76 _LIBCPP_EXPORTED_FROM_ABI
  77 __barrier_algorithm_base * __construct_barrier_algorithm_base(ptrdiff_t& __expected)
  78 {
  79     return new __barrier_algorithm_base(__expected);
  80 }
  81 _LIBCPP_EXPORTED_FROM_ABI
  82 bool __arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier,
  83                                      __barrier_phase_t __old_phase)
  84 {
  85     return __barrier->__arrive(__old_phase);
  86 }
  87 _LIBCPP_EXPORTED_FROM_ABI
  88 void __destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier)
  89 {
  90     delete __barrier;
  91 }
  92
  93 #endif // !defined(_LIBCPP_HAS_NO_TREE_BARRIER)
  94
  95 _LIBCPP_END_NAMESPACE_STD
  96
  97 #endif //_LIBCPP_HAS_NO_THREADS