diff --git a/libc/config/linux/api.td b/libc/config/linux/api.td --- a/libc/config/linux/api.td +++ b/libc/config/linux/api.td @@ -133,3 +133,35 @@ "munmap", ]; } + +def MtxT : TypeDecl<"mtx_t"> { + let Decl = [{ + struct mtx_t { + unsigned char __internal_data[4]; + int __mtx_type; + }; + }]; +} + +def ThreadsAPI : PublicAPI<"threads.h"> { + let TypeDeclarations = [ + MtxT, + ]; + + let Enumerations = [ + "mtx_plain", + "mtx_recursive", + "mtx_timed", + "thrd_timedout", + "thrd_success", + "thrd_busy", + "thrd_error", + "thrd_nomem", + ]; + + let Functions = [ + "mtx_init", + "mtx_lock", + "mtx_unlock", + ]; +} diff --git a/libc/config/public_api.td b/libc/config/public_api.td --- a/libc/config/public_api.td +++ b/libc/config/public_api.td @@ -24,6 +24,7 @@ string HeaderName = name; list Macros = []; list TypeDeclarations = []; + list Enumerations = []; list Structs = []; list Functions = []; } diff --git a/libc/include/CMakeLists.txt b/libc/include/CMakeLists.txt --- a/libc/include/CMakeLists.txt +++ b/libc/include/CMakeLists.txt @@ -35,6 +35,14 @@ llvm_libc_common_h ) +add_gen_header( + threads_h + DEF_FILE threads.h.def + GEN_HDR threads.h + DEPENDS + llvm_libc_common_h +) + add_gen_header( errno_h DEF_FILE errno.h.def diff --git a/libc/include/threads.h.def b/libc/include/threads.h.def new file mode 100644 --- /dev/null +++ b/libc/include/threads.h.def @@ -0,0 +1,16 @@ +//===---------------- C standard library header threads.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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIBC_STRING_H +#define LLVM_LIBC_STRING_H + +#include <__llvm-libc-common.h> + +%%public_api() + +#endif // LLVM_LIBC_STRING_H diff --git a/libc/lib/CMakeLists.txt b/libc/lib/CMakeLists.txt --- a/libc/lib/CMakeLists.txt +++ b/libc/lib/CMakeLists.txt @@ -12,6 +12,10 @@ # sys/mman.h entrypoints mmap munmap + + mtx_init + mtx_lock + mtx_unlock ) add_entrypoint_library( diff --git a/libc/spec/linux.td b/libc/spec/linux.td --- a/libc/spec/linux.td +++ b/libc/spec/linux.td @@ -57,6 +57,7 @@ Macro<"ECOMM">, ], [], // Types + [], // Enumerations [] // Functions >; @@ -64,6 +65,7 @@ "sys/mman.h", [Macro<"MAP_ANONYMOUS">], [], // Types + [], // Enumerations [] // Functions >; diff --git a/libc/spec/posix.td b/libc/spec/posix.td --- a/libc/spec/posix.td +++ b/libc/spec/posix.td @@ -84,6 +84,7 @@ Macro<"EXDEV">, ], [], // Types + [], // Enumerations [] // Functions >; @@ -107,6 +108,7 @@ SizeTType, OffTType, ], + [], // Enumerations [ FunctionSpec< "mmap", diff --git a/libc/spec/spec.td b/libc/spec/spec.td --- a/libc/spec/spec.td +++ b/libc/spec/spec.td @@ -14,6 +14,15 @@ list Fields; } +class EnumNameValue { + string Name = name; + string Value = value; +} + +class Enum enumerations> : NamedType { + list Enumerations = enumerations; +} + class PtrType : Type { Type PointeeType = type; } @@ -43,6 +52,11 @@ string Name = name; } +class EnumeratedNameValue { + string Name = name; + string Value = value; +} + class Annotation {} class RetValSpec annotations = []> { @@ -65,11 +79,13 @@ class HeaderSpec macros, list types, + list enumerations, list functions> { string Name = name; list Functions = functions; list Types = types; list Macros = macros; + list Enumerations = enumerations; } class StandardSpec { diff --git a/libc/spec/stdc.td b/libc/spec/stdc.td --- a/libc/spec/stdc.td +++ b/libc/spec/stdc.td @@ -8,6 +8,9 @@ RestrictedPtrType CharRestrictedPtr = RestrictedPtrType; ConstType ConstCharRestrictedPtr = ConstType; + NamedType MtxTType = NamedType<"mtx_t">; + PtrType MtxTTypePtr = PtrType; + HeaderSpec String = HeaderSpec< "string.h", [ @@ -16,6 +19,7 @@ [ SizeTType, ], + [], // Enumerations [ FunctionSpec< "memcpy", @@ -143,6 +147,7 @@ NamedType<"float_t">, NamedType<"double_t">, ], + [], // Enumerations [ FunctionSpec<"acos", RetValSpec, [ArgSpec]>, FunctionSpec<"acosl", RetValSpec, [ArgSpec]>, @@ -155,6 +160,7 @@ [ // Types SizeTType, ], + [], // Enumerations [ FunctionSpec< "snprintf", @@ -176,13 +182,57 @@ Macro<"ERANGE">, ], [], // Types + [], // Enumerations [] // Functions >; + HeaderSpec Threads = HeaderSpec< + "threads.h", + [], // Macros + [ + MtxTType, + ], + [ + EnumeratedNameValue<"mtx_plain">, + EnumeratedNameValue<"mtx_recursive">, + EnumeratedNameValue<"mtx_timed">, + EnumeratedNameValue<"thrd_timedout">, + EnumeratedNameValue<"thrd_success">, + EnumeratedNameValue<"thrd_busy">, + EnumeratedNameValue<"thrd_error">, + EnumeratedNameValue<"thrd_nomem">, + ], + [ + FunctionSpec< + "mtx_init", + RetValSpec, + [ + ArgSpec, + ArgSpec, + ] + >, + FunctionSpec< + "mtx_lock", + RetValSpec, + [ + ArgSpec, + ] + >, + FunctionSpec< + "mtx_unlock", + RetValSpec, + [ + ArgSpec, + ] + >, + ] + >; + let Headers = [ Errno, Math, String, StdIO, + Threads, ]; } diff --git a/libc/src/CMakeLists.txt b/libc/src/CMakeLists.txt --- a/libc/src/CMakeLists.txt +++ b/libc/src/CMakeLists.txt @@ -1,7 +1,7 @@ add_subdirectory(errno) add_subdirectory(math) add_subdirectory(string) -# TODO: Add this target conditional to the target OS. add_subdirectory(sys) +add_subdirectory(threads) add_subdirectory(__support) diff --git a/libc/src/threads/CMakeLists.txt b/libc/src/threads/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/libc/src/threads/CMakeLists.txt @@ -0,0 +1,3 @@ +if(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/${LIBC_TARGET_OS}) + add_subdirectory(${LIBC_TARGET_OS}) +endif() diff --git a/libc/src/threads/linux/CMakeLists.txt b/libc/src/threads/linux/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/libc/src/threads/linux/CMakeLists.txt @@ -0,0 +1,45 @@ +add_header_library( + mutex + HDRS + mutex.h +) + +add_entrypoint_object( + mtx_init + SRCS + mtx_init.cpp + HDRS + ../mtx_init.h + DEPENDS + mutex + support_common_h + threads_h +) + +add_entrypoint_object( + mtx_lock + SRCS + mtx_lock.cpp + HDRS + ../mtx_lock.h + DEPENDS + linux_syscall_h + mutex + support_common_h + sys_syscall_h + threads_h +) + +add_entrypoint_object( + mtx_unlock + SRCS + mtx_unlock.cpp + HDRS + ../mtx_unlock.h + DEPENDS + linux_syscall_h + mutex + support_common_h + sys_syscall_h + threads_h +) diff --git a/libc/src/threads/linux/mtx_init.cpp b/libc/src/threads/linux/mtx_init.cpp new file mode 100644 --- /dev/null +++ b/libc/src/threads/linux/mtx_init.cpp @@ -0,0 +1,21 @@ +//===----------- Linux implementation of the mtx_init function ------------===// +// +// 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 "include/threads.h" // For mtx_t definition. +#include "src/__support/common.h" +#include "src/threads/linux/mutex.h" + +namespace __llvm_libc { + +int LLVM_LIBC_ENTRYPOINT(mtx_init)(mtx_t *mutex, int type) { + *(reinterpret_cast(mutex->__internal_data)) = MS_Free; + mutex->__mtx_type = type; + return thrd_success; +} + +} // namespace __llvm_libc diff --git a/libc/src/threads/linux/mtx_lock.cpp b/libc/src/threads/linux/mtx_lock.cpp new file mode 100644 --- /dev/null +++ b/libc/src/threads/linux/mtx_lock.cpp @@ -0,0 +1,63 @@ +//===----------- Linux implementation of the mtx_lock function ------------===// +// +// 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 "config/linux/syscall.h" // For syscall functions. +#include "include/sys/syscall.h" // For syscall numbers. +#include "include/threads.h" // For mtx_t definition. +#include "src/__support/common.h" +#include "src/threads/linux/mutex.h" + +#include // For futex operations. +#include // For atomic_compare_exchange_strong. + +namespace __llvm_libc { + +// The implementation currently handles only plain mutexes. +int LLVM_LIBC_ENTRYPOINT(mtx_lock)(mtx_t *mutex) { + FutexData *futex_data = reinterpret_cast(mutex->__internal_data); + while (true) { + uint32_t mutex_status = MS_Free; + uint32_t locked_status = MS_Locked; + + if (!atomic_compare_exchange_strong(futex_data, &mutex_status, MS_Locked)) { + switch (mutex_status) { + case MS_Waiting: + // 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, (long)futex_data, FUTEX_WAIT, + MS_Waiting, 0, 0, 0); + // Once woken up/unblocked, try everything all over. + continue; + case MS_Locked: + // Mutex has been locked by another thread so set the status to + // MS_Waiting. + if (atomic_compare_exchange_strong(futex_data, &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, (long)futex_data, FUTEX_WAIT, + MS_Waiting, 0, 0, 0); + } + continue; + case MS_Free: + // If it was MS_Free, we shouldn't be here at all. + [[clang::fallthrough]]; + default: + // Mutex status cannot be anything else. So control should not reach + // here at all. + return thrd_error; + } + } else { + return thrd_success; + } + } +} + +} // namespace __llvm_libc diff --git a/libc/src/threads/linux/mtx_unlock.cpp b/libc/src/threads/linux/mtx_unlock.cpp new file mode 100644 --- /dev/null +++ b/libc/src/threads/linux/mtx_unlock.cpp @@ -0,0 +1,43 @@ +//===---------- Linux implementation of the mtx_unlock function -----------===// +// +// 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 "config/linux/syscall.h" // For syscall functions. +#include "include/sys/syscall.h" // For syscall numbers. +#include "include/threads.h" // For mtx_t definition. +#include "src/__support/common.h" +#include "src/threads/linux/mutex.h" + +#include // For futex operations. +#include // for atomic_compare_exchange_strong. + +namespace __llvm_libc { + +// The implementation currently handles only plain mutexes. +int LLVM_LIBC_ENTRYPOINT(mtx_unlock)(mtx_t *mutex) { + FutexData *futex_word = reinterpret_cast(mutex->__internal_data); + while (true) { + uint32_t mutex_status = MS_Waiting; + if (atomic_compare_exchange_strong(futex_word, &mutex_status, MS_Free)) { + // If any thread is waiting to be woken up, then do it. + __llvm_libc::syscall(SYS_futex, (long)futex_word, FUTEX_WAKE, 1, 0, 0, 0); + return thrd_success; + } + + if (mutex_status == MS_Locked) { + // If no body was waiting at this point, just free it. + if (atomic_compare_exchange_strong(futex_word, &mutex_status, MS_Free)) + return thrd_success; + } else { + // This can happen, for example if some thread tries to unlock an already + // free mutex. + return thrd_error; + } + } +} + +} // namespace __llvm_libc diff --git a/libc/src/threads/linux/mutex.h b/libc/src/threads/linux/mutex.h new file mode 100644 --- /dev/null +++ b/libc/src/threads/linux/mutex.h @@ -0,0 +1,21 @@ +//===--- Linux specific definitions to support mutex operations --*- 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_THREADS_LINUX_H +#define LLVM_LIBC_SRC_THREADS_LINUX_H + +#include + +// We use a tri-state mutex because we want to avoid making syscalls +// as much as possible. In `mtx_unlock` a syscall to wake waiting threads is +// made only if the mutex status is `MS_Waiting`. +enum MutexStatus : uint32_t { MS_Free, MS_Locked, MS_Waiting }; + +typedef _Atomic uint32_t FutexData; + +#endif // LLVM_LIBC_SRC_THREADS_LINUX_H diff --git a/libc/src/threads/mtx_init.h b/libc/src/threads/mtx_init.h new file mode 100644 --- /dev/null +++ b/libc/src/threads/mtx_init.h @@ -0,0 +1,15 @@ +//===---------- Implementation header for mtx_init function ------ *-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 +// +//===----------------------------------------------------------------------===// + +#include "include/threads.h" + +namespace __llvm_libc { + +int mtx_int(mtx_t *mutex, int type); + +} // namespace __llvm_libc diff --git a/libc/src/threads/mtx_lock.h b/libc/src/threads/mtx_lock.h new file mode 100644 --- /dev/null +++ b/libc/src/threads/mtx_lock.h @@ -0,0 +1,15 @@ +//===---------- Implementation header for mtx_lock function ------ *-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 +// +//===----------------------------------------------------------------------===// + +#include "include/threads.h" + +namespace __llvm_libc { + +int mtx_lock(mtx_t *mutex); + +} // namespace __llvm_libc diff --git a/libc/src/threads/mtx_unlock.h b/libc/src/threads/mtx_unlock.h new file mode 100644 --- /dev/null +++ b/libc/src/threads/mtx_unlock.h @@ -0,0 +1,15 @@ +//===-------- Implementation header for mtx_unlock function ------ *-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 +// +//===----------------------------------------------------------------------===// + +#include "include/threads.h" + +namespace __llvm_libc { + +int mtx_unlock(mtx_t *mutex); + +} // namespace __llvm_libc diff --git a/libc/test/src/CMakeLists.txt b/libc/test/src/CMakeLists.txt --- a/libc/test/src/CMakeLists.txt +++ b/libc/test/src/CMakeLists.txt @@ -1,3 +1,4 @@ add_subdirectory(errno) add_subdirectory(string) add_subdirectory(sys) +add_subdirectory(threads) diff --git a/libc/test/src/threads/CMakeLists.txt b/libc/test/src/threads/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/libc/test/src/threads/CMakeLists.txt @@ -0,0 +1 @@ +add_subdirectory(linux) diff --git a/libc/test/src/threads/linux/CMakeLists.txt b/libc/test/src/threads/linux/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/libc/test/src/threads/linux/CMakeLists.txt @@ -0,0 +1,17 @@ +add_libc_testsuite(libc_threads_unittests) + +add_libc_unittest( + mtx_test + SUITE + libc_threads_unittests + SRCS + mtx_test.cpp + DEPENDS + sys_syscall_h + threads_h + mtx_init + mtx_lock + mtx_unlock +) + +target_link_libraries(mtx_test PRIVATE -lpthread) diff --git a/libc/test/src/threads/linux/mtx_test.cpp b/libc/test/src/threads/linux/mtx_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/threads/linux/mtx_test.cpp @@ -0,0 +1,110 @@ +//===---------------------- Unittests for mtx_t ---------------------------===// +// +// 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 "include/threads.h" +#include "src/threads/mtx_init.h" +#include "src/threads/mtx_lock.h" +#include "src/threads/mtx_unlock.h" +#include "utils/UnitTest/Test.h" +#include "utils/testutils/Support.h" +#include "utils/testutils/Thread.h" + +int START = 0; +int MAX = 10000; + +mtx_t mutex; +static int shared_int = START; + +void counter(void) { + int last_count = START; + while (true) { + __llvm_libc::mtx_lock(&mutex); + if (shared_int == last_count + 1) { + shared_int++; + last_count = shared_int; + } + __llvm_libc::mtx_unlock(&mutex); + if (last_count >= MAX) + break; + } +} + +TEST(MutexTest, RelayCounter) { + // The idea of this test is that two competing threads will update + // a counter only if the other thread has updated it. + __llvm_libc::testutils::Thread th(counter); + + int last_count = START; + while (true) { + ASSERT_EQ(__llvm_libc::mtx_lock(&mutex), (int)thrd_success); + if (shared_int == START) { + ++shared_int; + last_count = shared_int; + } else if (shared_int != last_count) { + ASSERT_EQ(shared_int, last_count + 1); + ++shared_int; + last_count = shared_int; + } + ASSERT_EQ(__llvm_libc::mtx_unlock(&mutex), (int)thrd_success); + if (last_count > MAX) + break; + } + + th.join(); +} + +mtx_t start_lock, step_lock; +bool start, step; + +void stepper(void) { + __llvm_libc::mtx_lock(&start_lock); + start = true; + __llvm_libc::mtx_unlock(&start_lock); + + __llvm_libc::mtx_lock(&step_lock); + step = true; + __llvm_libc::mtx_unlock(&step_lock); +} + +TEST(MutexTest, WaitAndStep) { + // In this test, we start a new thread but block it before it can make a + // step. Once we ensure that the thread is blocked, we unblock it. + // After unblocking, we then verify that the thread was indeed unblocked. + step = false; + start = false; + ASSERT_EQ(__llvm_libc::mtx_lock(&step_lock), (int)thrd_success); + + // The new thread will immediately start. + __llvm_libc::testutils::Thread th(stepper); + + while (true) { + // Make sure the thread actually started. + ASSERT_EQ(__llvm_libc::mtx_lock(&start_lock), (int)thrd_success); + bool s = start; + ASSERT_EQ(__llvm_libc::mtx_unlock(&start_lock), (int)thrd_success); + if (s) + break; + } + + // Sleep for 10 seconds and check that the step was not made. + // This could be flaky if the other thread is not scheduled for 10 + // seconds, but in practice it never happens. + __llvm_libc::testutils::sleep(10); + ASSERT_FALSE(step); + + // Unlock the step lock and wait for 10 seconds again. This should + // give enough time for the other thread to make the step. + ASSERT_EQ(__llvm_libc::mtx_unlock(&step_lock), (int)thrd_success); + __llvm_libc::testutils::sleep(10); + + ASSERT_EQ(__llvm_libc::mtx_lock(&step_lock), (int)thrd_success); + ASSERT_TRUE(step); + ASSERT_EQ(__llvm_libc::mtx_unlock(&step_lock), (int)thrd_success); + + th.join(); +} diff --git a/libc/utils/HdrGen/PublicAPICommand.cpp b/libc/utils/HdrGen/PublicAPICommand.cpp --- a/libc/utils/HdrGen/PublicAPICommand.cpp +++ b/libc/utils/HdrGen/PublicAPICommand.cpp @@ -75,11 +75,13 @@ // Mapping from names to records defining them. NameToRecordMapping MacroSpecMap; NameToRecordMapping TypeSpecMap; + NameToRecordMapping EnumerationSpecMap; NameToRecordMapping FunctionSpecMap; NameToRecordMapping MacroDefsMap; NameToRecordMapping TypeDeclsMap; NameSet Structs; + NameSet Enumerations; NameSet Functions; bool isaNamedType(llvm::Record *Def) { return isa(Def, NamedTypeClass); } @@ -136,6 +138,13 @@ FunctionSpecMap[std::string(FunctionSpec->getValueAsString("Name"))] = FunctionSpec; } + + auto EnumerationSpecList = + HeaderSpec->getValueAsListOfDefs("Enumerations"); + for (llvm::Record *EnumerationSpec : EnumerationSpecList) { + EnumerationSpecMap[std::string( + EnumerationSpec->getValueAsString("Name"))] = EnumerationSpec; + } } } } @@ -159,6 +168,10 @@ auto FunctionList = PublicAPI->getValueAsListOfStrings("Functions"); for (llvm::StringRef FunctionName : FunctionList) Functions.insert(std::string(FunctionName)); + + auto EnumerationList = PublicAPI->getValueAsListOfStrings("Enumerations"); + for (llvm::StringRef EnumerationName : EnumerationList) + Enumerations.insert(std::string(EnumerationName)); } void index(llvm::RecordKeeper &Records) { @@ -211,6 +224,25 @@ OS << '\n'; } + if (Enumerations.size() != 0) + OS << "enum {" << '\n'; + for (auto &Name : Enumerations) { + if (EnumerationSpecMap.find(Name) == EnumerationSpecMap.end()) + llvm::PrintFatalError( + Name + " is not listed as an enumeration in any standard spec.\n"); + + llvm::Record *EnumerationSpec = EnumerationSpecMap[Name]; + OS << " " << EnumerationSpec->getValueAsString("Name"); + auto Value = EnumerationSpec->getValueAsString("Value"); + if (Value == "__default__") { + OS << ",\n"; + } else { + OS << " = " << Value << ",\n"; + } + } + if (Enumerations.size() != 0) + OS << "};\n\n"; + OS << "__BEGIN_C_DECLS\n\n"; for (auto &Name : Functions) { if (FunctionSpecMap.find(Name) == FunctionSpecMap.end())