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#ifndef _LIBCPP_HAS_NO_THREADS
11
12#include <atomic>
13#include <climits>
14#include <functional>
15#include <thread>
16
17#ifdef __linux__
18
19#include <unistd.h>
20#include <linux/futex.h>
21#include <sys/syscall.h>
22
23// libc++ uses SYS_futex as a universal syscall name. However, on 32 bit architectures
24// with a 64 bit time_t, we need to specify SYS_futex_time64.
25#if !defined(SYS_futex) && defined(SYS_futex_time64)
26# define SYS_futex SYS_futex_time64
27#endif
28
29#elif defined(__FreeBSD__)
30
31#include <sys/types.h>
32#include <sys/umtx.h>
33
34#else // <- Add other operating systems here
35
36// Baseline needs no new headers
37
38#endif
39
40_LIBCPP_BEGIN_NAMESPACE_STD
41
42#ifdef __linux__
43
44static void __libcpp_platform_wait_on_address(__cxx_atomic_contention_t const volatile* __ptr,
45                                              __cxx_contention_t __val)
46{
47    static constexpr timespec __timeout = { 2, 0 };
48    syscall(SYS_futex, __ptr, FUTEX_WAIT_PRIVATE, __val, &__timeout, 0, 0);
49}
50
51static void __libcpp_platform_wake_by_address(__cxx_atomic_contention_t const volatile* __ptr,
52                                              bool __notify_one)
53{
54    syscall(SYS_futex, __ptr, FUTEX_WAKE_PRIVATE, __notify_one ? 1 : INT_MAX, 0, 0, 0);
55}
56
57#elif defined(__APPLE__) && defined(_LIBCPP_USE_ULOCK)
58
59extern "C" int __ulock_wait(uint32_t operation, void *addr, uint64_t value,
60                            uint32_t timeout); /* timeout is specified in microseconds */
61extern "C" int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value);
62
63#define UL_COMPARE_AND_WAIT 1
64#define ULF_WAKE_ALL        0x00000100
65
66static void __libcpp_platform_wait_on_address(__cxx_atomic_contention_t const volatile* __ptr,
67                                              __cxx_contention_t __val)
68{
69    __ulock_wait(UL_COMPARE_AND_WAIT,
70                 const_cast<__cxx_atomic_contention_t*>(__ptr), __val, 0);
71}
72
73static void __libcpp_platform_wake_by_address(__cxx_atomic_contention_t const volatile* __ptr,
74                                              bool __notify_one)
75{
76    __ulock_wake(UL_COMPARE_AND_WAIT | (__notify_one ? 0 : ULF_WAKE_ALL),
77                 const_cast<__cxx_atomic_contention_t*>(__ptr), 0);
78}
79
80#elif defined(__FreeBSD__)
81
82static void __libcpp_platform_wait_on_address(__cxx_atomic_contention_t const volatile* __ptr,
83                                              __cxx_contention_t __val)
84{
85    _umtx_op(const_cast<__cxx_atomic_contention_t*>(__ptr),
86             UMTX_OP_WAIT_UINT_PRIVATE, __val, NULL, NULL);
87}
88
89static void __libcpp_platform_wake_by_address(__cxx_atomic_contention_t const volatile* __ptr,
90                                              bool __notify_one)
91{
92    _umtx_op(const_cast<__cxx_atomic_contention_t*>(__ptr),
93             UMTX_OP_WAKE_PRIVATE, __notify_one ? 1 : INT_MAX, NULL, NULL);
94}
95
96#else // <- Add other operating systems here
97
98// Baseline is just a timed backoff
99
100static void __libcpp_platform_wait_on_address(__cxx_atomic_contention_t const volatile* __ptr,
101                                              __cxx_contention_t __val)
102{
103    __libcpp_thread_poll_with_backoff([=]() -> bool {
104        return !__cxx_nonatomic_compare_equal(__cxx_atomic_load(__ptr, memory_order_relaxed), __val);
105    }, __libcpp_timed_backoff_policy());
106}
107
108static void __libcpp_platform_wake_by_address(__cxx_atomic_contention_t const volatile*, bool) { }
109
110#endif // __linux__
111
112static constexpr size_t __libcpp_contention_table_size = (1 << 8);  /* < there's no magic in this number */
113
114struct alignas(64) /*  aim to avoid false sharing */ __libcpp_contention_table_entry
115{
116    __cxx_atomic_contention_t __contention_state;
117    __cxx_atomic_contention_t __platform_state;
118    inline constexpr __libcpp_contention_table_entry() :
119        __contention_state(0), __platform_state(0) { }
120};
121
122static __libcpp_contention_table_entry __libcpp_contention_table[ __libcpp_contention_table_size ];
123
124static hash<void const volatile*> __libcpp_contention_hasher;
125
126static __libcpp_contention_table_entry* __libcpp_contention_state(void const volatile * p)
127{
128    return &__libcpp_contention_table[__libcpp_contention_hasher(p) & (__libcpp_contention_table_size - 1)];
129}
130
131/* Given an atomic to track contention and an atomic to actually wait on, which may be
132   the same atomic, we try to detect contention to avoid spuriously calling the platform. */
133
134static void __libcpp_contention_notify(__cxx_atomic_contention_t volatile* __contention_state,
135                                       __cxx_atomic_contention_t const volatile* __platform_state,
136                                       bool __notify_one)
137{
138    if(0 != __cxx_atomic_load(__contention_state, memory_order_seq_cst))
139        // We only call 'wake' if we consumed a contention bit here.
140        __libcpp_platform_wake_by_address(__platform_state, __notify_one);
141}
142static __cxx_contention_t __libcpp_contention_monitor_for_wait(__cxx_atomic_contention_t volatile* __contention_state,
143                                                               __cxx_atomic_contention_t const volatile* __platform_state)
144{
145    // We will monitor this value.
146    return __cxx_atomic_load(__platform_state, memory_order_acquire);
147}
148static void __libcpp_contention_wait(__cxx_atomic_contention_t volatile* __contention_state,
149                                     __cxx_atomic_contention_t const volatile* __platform_state,
150                                     __cxx_contention_t __old_value)
151{
152    __cxx_atomic_fetch_add(__contention_state, __cxx_contention_t(1), memory_order_seq_cst);
153    // We sleep as long as the monitored value hasn't changed.
154    __libcpp_platform_wait_on_address(__platform_state, __old_value);
155    __cxx_atomic_fetch_sub(__contention_state, __cxx_contention_t(1), memory_order_release);
156}
157
158/* When the incoming atomic is the wrong size for the platform wait size, need to
159   launder the value sequence through an atomic from our table. */
160
161static void __libcpp_atomic_notify(void const volatile* __location)
162{
163    auto const __entry = __libcpp_contention_state(__location);
164    // The value sequence laundering happens on the next line below.
165    __cxx_atomic_fetch_add(&__entry->__platform_state, __cxx_contention_t(1), memory_order_release);
166    __libcpp_contention_notify(&__entry->__contention_state,
167                               &__entry->__platform_state,
168                               false /* when laundering, we can't handle notify_one */);
169}
170_LIBCPP_EXPORTED_FROM_ABI
171void __cxx_atomic_notify_one(void const volatile* __location)
172    { __libcpp_atomic_notify(__location); }
173_LIBCPP_EXPORTED_FROM_ABI
174void __cxx_atomic_notify_all(void const volatile* __location)
175    { __libcpp_atomic_notify(__location); }
176_LIBCPP_EXPORTED_FROM_ABI
177__cxx_contention_t __libcpp_atomic_monitor(void const volatile* __location)
178{
179    auto const __entry = __libcpp_contention_state(__location);
180    return __libcpp_contention_monitor_for_wait(&__entry->__contention_state, &__entry->__platform_state);
181}
182_LIBCPP_EXPORTED_FROM_ABI
183void __libcpp_atomic_wait(void const volatile* __location, __cxx_contention_t __old_value)
184{
185    auto const __entry = __libcpp_contention_state(__location);
186    __libcpp_contention_wait(&__entry->__contention_state, &__entry->__platform_state, __old_value);
187}
188
189/* When the incoming atomic happens to be the platform wait size, we still need to use the
190   table for the contention detection, but we can use the atomic directly for the wait. */
191
192_LIBCPP_EXPORTED_FROM_ABI
193void __cxx_atomic_notify_one(__cxx_atomic_contention_t const volatile* __location)
194{
195    __libcpp_contention_notify(&__libcpp_contention_state(__location)->__contention_state, __location, true);
196}
197_LIBCPP_EXPORTED_FROM_ABI
198void __cxx_atomic_notify_all(__cxx_atomic_contention_t const volatile* __location)
199{
200    __libcpp_contention_notify(&__libcpp_contention_state(__location)->__contention_state, __location, false);
201}
202_LIBCPP_EXPORTED_FROM_ABI
203__cxx_contention_t __libcpp_atomic_monitor(__cxx_atomic_contention_t const volatile* __location)
204{
205    return __libcpp_contention_monitor_for_wait(&__libcpp_contention_state(__location)->__contention_state, __location);
206}
207_LIBCPP_EXPORTED_FROM_ABI
208void __libcpp_atomic_wait(__cxx_atomic_contention_t const volatile* __location, __cxx_contention_t __old_value)
209{
210    __libcpp_contention_wait(&__libcpp_contention_state(__location)->__contention_state, __location, __old_value);
211}
212
213_LIBCPP_END_NAMESPACE_STD
214
215#endif //_LIBCPP_HAS_NO_THREADS
216