diff --git a/libc/include/__llvm-libc-common.h b/libc/include/__llvm-libc-common.h --- a/libc/include/__llvm-libc-common.h +++ b/libc/include/__llvm-libc-common.h @@ -20,6 +20,12 @@ #undef _Noreturn #define _Noreturn [[noreturn]] +#undef _Alignas +#define _Alignas alignas + +#undef _Alignof +#define _Alignof alignof + #else // not __cplusplus #undef __BEGIN_C_DECLS diff --git a/libc/include/llvm-libc-types/cnd_t.h b/libc/include/llvm-libc-types/cnd_t.h --- a/libc/include/llvm-libc-types/cnd_t.h +++ b/libc/include/llvm-libc-types/cnd_t.h @@ -9,13 +9,12 @@ #ifndef __LLVM_LIBC_TYPES_CND_T_H__ #define __LLVM_LIBC_TYPES_CND_T_H__ +#include "mtx_t.h" + typedef struct { void *__qfront; void *__qback; - struct { - unsigned char __w[4]; - int __t; - } __qmtx; + mtx_t __qmtx; } cnd_t; #endif // __LLVM_LIBC_TYPES_CND_T_H__ diff --git a/libc/include/llvm-libc-types/mtx_t.h b/libc/include/llvm-libc-types/mtx_t.h --- a/libc/include/llvm-libc-types/mtx_t.h +++ b/libc/include/llvm-libc-types/mtx_t.h @@ -10,7 +10,17 @@ #define __LLVM_LIBC_TYPES_MTX_T_H__ typedef struct { - unsigned char __internal_data[4]; +#if defined(__x86_64__) || defined(__arch64__) + // Futex word should be aligned appropriately to allow target atomic + // instructions. This declaration mimics the internal setup. + struct { + _Alignas(sizeof(unsigned int) > _Alignof(unsigned int) + ? sizeof(unsigned int) + : _Alignof(unsigned int)) unsigned int __word; + } __futex_word; +#else +#error "Mutex type mtx_t is not available for the target architecture." +#endif int __mtx_type; } mtx_t; diff --git a/libc/src/__support/CPP/CMakeLists.txt b/libc/src/__support/CPP/CMakeLists.txt --- a/libc/src/__support/CPP/CMakeLists.txt +++ b/libc/src/__support/CPP/CMakeLists.txt @@ -20,3 +20,9 @@ DEPENDS libc.include.stdlib ) + +add_header_library( + atomic + HDRS + atomic.h +) diff --git a/libc/src/__support/CPP/atomic.h b/libc/src/__support/CPP/atomic.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/CPP/atomic.h @@ -0,0 +1,84 @@ +//===-- A simple equivalent of std::atomic ----------------------*- 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 LLVM_LIBC_SRC_SUPPORT_CPP_ATOMIC_H +#define LLVM_LIBC_SRC_SUPPORT_CPP_ATOMIC_H + +#include "TypeTraits.h" + +namespace __llvm_libc { +namespace cpp { + +enum class MemoryOrder : int { + RELAXED = __ATOMIC_RELAXED, + CONSUME = __ATOMIC_CONSUME, + ACQUIRE = __ATOMIC_ACQUIRE, + RELEASE = __ATOMIC_RELEASE, + ACQ_REL = __ATOMIC_ACQ_REL, + SEQ_CST = __ATOMIC_SEQ_CST +}; + +template struct Atomic { + // For now, we will restrict to only arithmetic types. + static_assert(IsArithmetic::Value, "Only arithmetic types can be atomic."); + +private: + // The value stored should be appropriately aligned so that + // hardware instructions used to perform atomic operations work + // correctly. + static constexpr int ALIGNMENT = sizeof(T) > alignof(T) ? sizeof(T) + : alignof(T); + +public: + using value_type = T; + + // We keep the internal value public so that it can be addressable. + // This is useful in places like the Linux futex operations where + // we need pointers to the memory of the atomic values. Load and store + // operations should be performed using the atomic methods however. + alignas(ALIGNMENT) value_type val; + + // Intializes the value without using atomic operations. + constexpr Atomic(value_type v) : val(v) {} + + Atomic(const Atomic &) = delete; + Atomic &operator=(const Atomic &) = delete; + + // Atomic load + operator T() { return __atomic_load_n(&val, int(MemoryOrder::SEQ_CST)); } + + T load(MemoryOrder mem_ord = MemoryOrder::SEQ_CST) { + return __atomic_load_n(&val, int(mem_ord)); + } + + // Atomic store + T operator=(T rhs) { + __atomic_store_n(&val, rhs, int(MemoryOrder::SEQ_CST)); + return rhs; + } + + void store(T rhs, MemoryOrder mem_ord = MemoryOrder::SEQ_CST) { + __atomic_store_n(&val, rhs, int(mem_ord)); + } + + // Atomic compare exchange + bool compare_exchange_strong(T &expected, T desired, + MemoryOrder mem_ord = MemoryOrder::SEQ_CST) { + return __atomic_compare_exchange_n(&val, &expected, desired, false, + int(mem_ord), int(mem_ord)); + } + + // Set the value without using an atomic operation. This is useful + // in initializing atomic values without a constructor. + void set(T rhs) { val = rhs; } +}; + +} // namespace cpp +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_SUPPORT_CPP_ATOMIC_H diff --git a/libc/src/threads/linux/CMakeLists.txt b/libc/src/threads/linux/CMakeLists.txt --- a/libc/src/threads/linux/CMakeLists.txt +++ b/libc/src/threads/linux/CMakeLists.txt @@ -32,6 +32,7 @@ .thread_start_args_h libc.include.sys_syscall libc.include.threads + libc.src.__support.CPP.atomic libc.src.__support.OSUtil.osutil ) diff --git a/libc/src/threads/linux/CndVar.h b/libc/src/threads/linux/CndVar.h --- a/libc/src/threads/linux/CndVar.h +++ b/libc/src/threads/linux/CndVar.h @@ -9,15 +9,15 @@ #ifndef LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H #define LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H -#include "Futex.h" #include "Mutex.h" -#include "include/sys/syscall.h" // For syscall numbers. -#include "include/threads.h" // For values like thrd_success etc. +#include "include/sys/syscall.h" // For syscall numbers. +#include "include/threads.h" // For values like thrd_success etc. +#include "src/__support/CPP/atomic.h" #include "src/__support/OSUtil/syscall.h" // For syscall functions. #include // For futex operations. -#include // For atomic operations +#include namespace __llvm_libc { @@ -28,7 +28,7 @@ }; struct CndWaiter { - FutexWord futex_word = WS_Waiting; + cpp::Atomic futex_word = WS_Waiting; CndWaiter *next = nullptr; }; @@ -83,8 +83,8 @@ } } - __llvm_libc::syscall(SYS_futex, &waiter.futex_word, FUTEX_WAIT, WS_Waiting, - 0, 0, 0); + __llvm_libc::syscall(SYS_futex, &waiter.futex_word.val, FUTEX_WAIT, + WS_Waiting, 0, 0, 0); // At this point, if locking |m| fails, we can simply return as the // queued up waiter would have been removed from the queue. @@ -105,17 +105,18 @@ if (waitq_front == nullptr) waitq_back = nullptr; - atomic_store(&qmtx.futex_word, Mutex::MS_Free); + qmtx.futex_word = Mutex::MS_Free; __llvm_libc::syscall( - SYS_futex, &qmtx.futex_word, FUTEX_WAKE_OP, 1, 1, &first->futex_word, + SYS_futex, &qmtx.futex_word.val, FUTEX_WAKE_OP, 1, 1, + &first->futex_word.val, FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting)); return thrd_success; } int broadcast() { MutexLock ml(&qmtx); - FutexWord dummy_futex_word; + uint32_t dummy_futex_word; CndWaiter *waiter = waitq_front; waitq_front = waitq_back = nullptr; while (waiter != nullptr) { @@ -125,7 +126,7 @@ // FUTEX_WAKE_OP. __llvm_libc::syscall( SYS_futex, &dummy_futex_word, FUTEX_WAKE_OP, 1, 1, - &waiter->futex_word, + &waiter->futex_word.val, FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting)); waiter = waiter->next; } diff --git a/libc/src/threads/linux/Mutex.h b/libc/src/threads/linux/Mutex.h --- a/libc/src/threads/linux/Mutex.h +++ b/libc/src/threads/linux/Mutex.h @@ -9,26 +9,31 @@ #ifndef LLVM_LIBC_SRC_THREADS_LINUX_MUTEX_H #define LLVM_LIBC_SRC_THREADS_LINUX_MUTEX_H -#include "Futex.h" - #include "include/sys/syscall.h" // For syscall numbers. #include "include/threads.h" // For values like thrd_success etc. +#include "src/__support/CPP/atomic.h" // For atomics support #include "src/__support/OSUtil/syscall.h" // For syscall functions. #include // For futex operations. -#include -#include namespace __llvm_libc { +#if (defined(LLVM_LIBC_ARCH_AARCH64) || defined(LLVM_LIBC_ARCH_X86_64)) +static_assert(sizeof(unsigned int) == 4, + "Unexpected size of unsigned int type."); +typedef unsigned int FutexWordType; +#else +#error "Futex word base type not defined for the target architecture." +#endif + struct Mutex { - enum Status : uint32_t { + enum Status : FutexWordType { MS_Free, MS_Locked, MS_Waiting, }; - FutexWord futex_word; + cpp::Atomic futex_word; int type; static int init(Mutex *mutex, int type) { @@ -40,13 +45,12 @@ int lock() { bool was_waiting = false; while (true) { - uint32_t mutex_status = MS_Free; - uint32_t locked_status = MS_Locked; + FutexWordType mutex_status = MS_Free; + FutexWordType locked_status = MS_Locked; - if (atomic_compare_exchange_strong(&futex_word, &mutex_status, - MS_Locked)) { + if (futex_word.compare_exchange_strong(mutex_status, MS_Locked)) { if (was_waiting) - atomic_store(&futex_word, MS_Waiting); + futex_word = MS_Waiting; return thrd_success; } @@ -55,7 +59,7 @@ // If other threads are waiting already, then join them. Note that the // futex syscall will block if the futex data is still `MS_Waiting` (the // 4th argument to the syscall function below.) - __llvm_libc::syscall(SYS_futex, &futex_word, FUTEX_WAIT_PRIVATE, + __llvm_libc::syscall(SYS_futex, &futex_word.val, FUTEX_WAIT_PRIVATE, MS_Waiting, 0, 0, 0); was_waiting = true; // Once woken up/unblocked, try everything all over. @@ -63,12 +67,11 @@ case MS_Locked: // Mutex has been locked by another thread so set the status to // MS_Waiting. - if (atomic_compare_exchange_strong(&futex_word, &locked_status, - MS_Waiting)) { + if (futex_word.compare_exchange_strong(locked_status, MS_Waiting)) { // If we are able to set the futex data to `MS_Waiting`, then we will // wait for the futex to be woken up. Note again that the following // syscall will block only if the futex data is still `MS_Waiting`. - __llvm_libc::syscall(SYS_futex, &futex_word, FUTEX_WAIT_PRIVATE, + __llvm_libc::syscall(SYS_futex, &futex_word.val, FUTEX_WAIT_PRIVATE, MS_Waiting, 0, 0, 0); was_waiting = true; } @@ -86,17 +89,17 @@ int unlock() { while (true) { - uint32_t mutex_status = MS_Waiting; - if (atomic_compare_exchange_strong(&futex_word, &mutex_status, MS_Free)) { + FutexWordType mutex_status = MS_Waiting; + if (futex_word.compare_exchange_strong(mutex_status, MS_Free)) { // If any thread is waiting to be woken up, then do it. - __llvm_libc::syscall(SYS_futex, &futex_word, FUTEX_WAKE_PRIVATE, 1, 0, - 0, 0); + __llvm_libc::syscall(SYS_futex, &futex_word.val, FUTEX_WAKE_PRIVATE, 1, + 0, 0, 0); return thrd_success; } if (mutex_status == MS_Locked) { // If nobody was waiting at this point, just free it. - if (atomic_compare_exchange_strong(&futex_word, &mutex_status, MS_Free)) + if (futex_word.compare_exchange_strong(mutex_status, MS_Free)) return thrd_success; } else { // This can happen, for example if some thread tries to unlock an diff --git a/libc/test/src/__support/CPP/CMakeLists.txt b/libc/test/src/__support/CPP/CMakeLists.txt --- a/libc/test/src/__support/CPP/CMakeLists.txt +++ b/libc/test/src/__support/CPP/CMakeLists.txt @@ -59,3 +59,13 @@ DEPENDS libc.src.__support.CPP.standalone_cpp ) + +add_libc_unittest( + atomic_test + SUITE + libc_cpp_utils_unittests + SRCS + atomic_test.cpp + DEPENDS + libc.src.__support.CPP.atomic +) diff --git a/libc/test/src/__support/CPP/atomic_test.cpp b/libc/test/src/__support/CPP/atomic_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/__support/CPP/atomic_test.cpp @@ -0,0 +1,34 @@ +//===-- Unittests for Atomic ----------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "src/__support/CPP/atomic.h" +#include "utils/UnitTest/Test.h" + +// Tests in this file do not test atomicity as it would require using +// threads, at which point it becomes a chicken and egg problem. + +TEST(LlvmLibcAtomicTest, LoadStore) { + __llvm_libc::cpp::Atomic aint(123); + ASSERT_EQ(aint.load(), 123); + + aint.store(100); + ASSERT_EQ(aint.load(), 100); + + aint = 1234; // Equivalent of store + ASSERT_EQ(aint.load(), 1234); +} + +TEST(LlvmLibcAtomicTest, CompareExchangeStrong) { + int desired = 123; + __llvm_libc::cpp::Atomic aint(desired); + ASSERT_TRUE(aint.compare_exchange_strong(desired, 100)); + ASSERT_EQ(aint.load(), 100); + + ASSERT_FALSE(aint.compare_exchange_strong(desired, 100)); + ASSERT_EQ(aint.load(), 100); +}