[libc] Take 2: Add linux implementations of thrd_create and thrd_join functions.

[sivachandra]

Summary

The following are the differences from the first version:

1. The kernel does not copy the stack for the new thread (it cannot).

The previous version missed this fact. In this new version, the new
thread's start args are copied on to the new stack in a known location
so that the new thread can sniff them out.

2. A start args sniffer for x86_64 has been added.
3. Default stack size has been increased to 64KB.

[sivachandra]

Use atomic_uint_least32_t type for FutexData.

[sivachandra]

Actually use atomic_uchar for the FutexData type.

[abrachet]

This looks good to me. Maybe worth waiting for @phosek.

FWIW the tests works fine on my machine but the last patch did as well. Also, exceptions can properly unwind the threads stack which I thought might have been an issue with calling clone in C and not being able to emit the correct cfi directives. Which is to say I'm fairly confident everything is set up properly now :)

libc/src/threads/linux/thrd_create.cpp

81–82

Maybe put a TODO here because clone's arguments are different on other architectures. Perhaps we should just use the libc wrapper for clone here later?

libc/src/threads/linux/thrd_join.cpp

31–33

Maybe this comment should be moved up to the while loops condition

libc/src/threads/linux/x86_64/thread_start_args.h.in

12

workd -> work

[MaskRay]

I think implementing pthread on top of C11 threads is plausible on Fuchsia because it just provides POSIX lite. However, the same idea copying over to Linux may not be practical. For one thing, the performance of pthread_mutex_lock matters. Implementing it on top of mtx_lock costs an extra function call, not to say that some features are not available in C11 mutex. mtx_* and thrd_* are usely so rarely in practice. Implementing them on top of pthread will have an infinitesimal cost.

[sivachandra]

Address comments.

[sivachandra]

In D75818#1911513, @abrachet wrote:

FWIW the tests works fine on my machine but the last patch did as well. Also, exceptions can properly unwind the threads stack which I thought might have been an issue with calling clone in C and not being able to emit the correct cfi directives. Which is to say I'm fairly confident everything is set up properly now :)

I have access to a machine on which it was failing previously but passing now :)

[phosek]

In D75818#1911540, @MaskRay wrote:

I think implementing pthread on top of C11 threads is plausible on Fuchsia because it just provides POSIX lite. However, the same idea copying over to Linux may not be practical. For one thing, the performance of pthread_mutex_lock matters. Implementing it on top of mtx_lock costs an extra function call, not to say that some features are not available in C11 mutex. mtx_* and thrd_* are usely so rarely in practice. Implementing them on top of pthread will have an infinitesimal cost.

I don't think that either of these is practical, that is neither implementing pthreads on top C11 threads nor C11 threads on top of pthreads. In the former case, pthreads provide richer more complex API that's difficult to implement solely on top of the C11 threads one. In the latter case, you're forcing all platforms, even the non-POSIX ones, to implement enough of POSIX to allow the implementation of pthreads which is unnecessarily restrictive.

The solution we've adopted in Fuchsia is to implement a set of lower-level libraries, e.g. libsync which provide basic primitives, and then implement mtx_t and pthread_mutex_t separately on top of these rather than layering one on top of the other or vice versa.

libc/cmake/modules/LLVMLibCRules.cmake

 # Usage:
 #     add_entrypoint_object(
 #       <target_name>
 #       [REDIRECTED] # Specified if the entrypoint is redirected.
 #       [NAME] <the C name of the entrypoint if different from target_name>
 #       SRCS <list of .cpp files>
 #       HDRS <list of .h files>
 #       DEPENDS <list of dependencies>
+#       COMPILE_OPTIONS <list of special compile options for this target>
 #     )
 function(add_entrypoint_object target_name)
   cmake_parse_arguments(
     "ADD_ENTRYPOINT_OBJ"
     "REDIRECTED" # Optional argument
     "NAME" # Single value arguments
-    "SRCS;HDRS;DEPENDS"  # Multi value arguments
+    "SRCS;HDRS;DEPENDS;COMPILE_OPTIONS"  # Multi value arguments
     ${ARGN}
   )
   if(NOT ADD_ENTRYPOINT_OBJ_SRCS)
     message(FATAL_ERROR "`add_entrypoint_object` rule requires SRCS to be specified.")
   endif()
   if(NOT ADD_ENTRYPOINT_OBJ_HDRS)
     message(FATAL_ERROR "`add_entrypoint_object` rule requires HDRS to be specified.")
   endif()
add_dependencies(
     support_common_h
   )
   if(ADD_ENTRYPOINT_OBJ_DEPENDS)
     add_dependencies(
       ${target_name}_objects
       ${ADD_ENTRYPOINT_OBJ_DEPENDS}
     )
   endif()
+  if(ADD_ENTRYPOINT_OBJ_COMPILE_OPTIONS)
+    target_compile_options(
+      ${target_name}_objects
+      PRIVATE ${ADD_ENTRYPOINT_OBJ_COMPILE_OPTIONS}
+    )
+  endif()
 
   set(object_file_raw "${CMAKE_CURRENT_BINARY_DIR}/${target_name}_raw.o")
   set(object_file "${CMAKE_CURRENT_BINARY_DIR}/${target_name}.o")
 
   add_custom_command(
     OUTPUT ${object_file_raw}
     DEPENDS $<TARGET_OBJECTS:${target_name}_objects>
     COMMAND ${CMAKE_LINKER} -r $<TARGET_OBJECTS:${target_name}_objects> -o ${object_file_raw}

libc/config/linux/api.td

def SignalAPI : PublicAPI<"signal.h"> {
   let Functions = [
     "raise",
     "sigprocmask",
     "sigemptyset",
     "sigaddset",
   ];
 }
 
+def ThreadStartT : TypeDecl<"thrd_start_t"> {
+  let Decl = "typedef int (*thrd_start_t)(void *);";
+}
+
 def ThreadsAPI : PublicAPI<"threads.h"> {
+  let TypeDeclarations = [
+    ThreadStartT,
+  ];
+
   let Enumerations = [
     "mtx_plain",
     "mtx_recursive",
     "mtx_timed",
     "thrd_timedout",
     "thrd_success",
     "thrd_busy",
     "thrd_error",
     "thrd_nomem",
   ];
+
+  let Functions = [
+    "thrd_create",
+    "thrd_join",
+  ];
 }

libc/config/linux/threads.h.in

-//===---------------- C standard library header threads.h -----------------===//
+//===--------- Linux specific definitions of types from 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_THREADS_H
-#define LLVM_LIBC_THREADS_H
+%%begin()
 
-#include <__llvm-libc-common.h>
-
-%%public_api()
-
-#endif // LLVM_LIBC_THREADS_H
+typedef struct {
+  unsigned char __clear_tid[4];
+  int __tid;
+  void *__stack;
+  int __stack_size;
+  int __retval;
+} thrd_t;

libc/include/CMakeLists.txt

add_gen_header(
   DEPENDS
     llvm_libc_common_h
 )
 
 add_gen_header(
   threads_h
   DEF_FILE threads.h.def
   GEN_HDR threads.h
+  PARAMS
+    platform_threads=../config/${LIBC_TARGET_OS}/threads.h.in
   DEPENDS
     llvm_libc_common_h
+  DATA_FILES
+    ../config/${LIBC_TARGET_OS}/threads.h.in
 )
 
 add_gen_header(
   errno_h
   DEF_FILE errno.h.def
   PARAMS
     platform_errno=../config/${LIBC_TARGET_OS}/errno.h.in
   GEN_HDR errno.h

libc/include/threads.h.def

 //===---------------- 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_THREADS_H
 #define LLVM_LIBC_THREADS_H
 
 #include <__llvm-libc-common.h>
 
+%%include_file(${platform_threads})
+
 %%public_api()
 
 #endif // LLVM_LIBC_THREADS_H

libc/lib/CMakeLists.txt

DEPENDS
     raise
     sigaddset
     sigemptyset
     sigprocmask
 
     # stdlib.h entrypoints
     _Exit
     abort
+
+    # threads.h entrypoints
+    thrd_create
+    thrd_join
 )
 
 add_entrypoint_library(
   llvmlibm
   DEPENDS
     # math.h entrypoints
     round
 )
 
 add_redirector_library(
   llvmlibc_redirectors
   DEPENDS
     round_redirector
 )

libc/src/CMakeLists.txt

 add_subdirectory(errno)
 add_subdirectory(math)
 add_subdirectory(signal)
 add_subdirectory(stdlib)
 add_subdirectory(string)
 # TODO: Add this target conditional to the target OS.
 add_subdirectory(sys)
+add_subdirectory(threads)
 
 add_subdirectory(__support)

libc/src/threads/CMakeLists.txt

+if(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/${LIBC_TARGET_OS})
+  add_subdirectory(${LIBC_TARGET_OS})
+endif()

libc/src/threads/linux/CMakeLists.txt

+add_gen_header(
+  thread_start_args_h
+  DEF_FILE thread_start_args.h.def
+  GEN_HDR thread_start_args.h
+  PARAMS
+    thread_start_args=${LIBC_TARGET_MACHINE}/thread_start_args.h.in
+  DATA_FILES
+    ${LIBC_TARGET_MACHINE}/thread_start_args.h.in
+)
+
+add_header_library(
+  threads_utils
+  HDRS
+    thread_utils.h
+  DEPENDS
+    thread_start_args_h
+)
+
+add_entrypoint_object(
+  thrd_create
+  SRCS
+    thrd_create.cpp
+  HDRS
+    ../thrd_create.h
+  DEPENDS
+    errno_h
+    linux_syscall_h
+    mmap
+    support_common_h
+    sys_syscall_h
+    threads_h
+    threads_utils
+    __errno_location
+  COMPILE_OPTIONS
+    -fno-omit-frame-pointer # This allows us to sniff out the thread args from
+                            # the new thread's stack reliably.
+)
+
+add_entrypoint_object(
+  thrd_join
+  SRCS
+    thrd_join.cpp
+  HDRS
+    ../thrd_join.h
+  DEPENDS
+    linux_syscall_h
+    munmap
+    support_common_h
+    sys_syscall_h
+    threads_h
+    threads_utils
+)

libc/src/threads/linux/thrd_create.cpp

+//===---------- Linux implementation of the thrd_create 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 function.
+#include "include/errno.h"        // For E* error values.
+#include "include/sys/mman.h"     // For PROT_* and MAP_* definitions.
+#include "include/sys/syscall.h"  // For syscall numbers.
+#include "include/threads.h"      // For thrd_* type definitions.
+#include "src/__support/common.h"
+#include "src/errno/llvmlibc_errno.h"
+#include "src/sys/mman/mmap.h"
+#include "src/sys/mman/munmap.h"
+#include "src/threads/linux/thread_utils.h"
+
+#include <linux/futex.h> // For futex operations.
+#include <linux/sched.h> // For CLONE_* flags.
+#include <stdint.h>
+
+namespace __llvm_libc {
+
+struct StartArgs {
+  thrd_t *thread;
+  thrd_start_t func;
+  void *arg;
+};
+
+static __attribute__((noinline)) void start_thread() {
+  StartArgs *start_args = reinterpret_cast<StartArgs *>(get_start_args_addr());
+  __llvm_libc::syscall(SYS_exit, start_args->thread->__retval =
+                                     start_args->func(start_args->arg));
+}
+
+int LLVM_LIBC_ENTRYPOINT(thrd_create)(thrd_t *thread, thrd_start_t func,
+                                      void *arg) {
+  unsigned clone_flags =
+      CLONE_VM        // Share the memory space with the parent.
+      | CLONE_FS      // Share the file system with the parent.
+      | CLONE_FILES   // Share the files with the parent.
+      | CLONE_SIGHAND // Share the signal handlers with the parent.
+      | CLONE_THREAD  // Same thread group as the parent.
+      | CLONE_SYSVSEM // Share a single list of System V semaphore adjustment
+                      // values
+      | CLONE_PARENT_SETTID   // Set child thread ID in |ptid| of the parent.
+      | CLONE_CHILD_CLEARTID; // Let the kernel clear the tid address and futex
+                              // wake the joining thread.
+  // TODO: Add the CLONE_SETTLS flag and setup the TLS area correctly when
+  // making the clone syscall.
+
+  void *stack = __llvm_libc::mmap(nullptr, ThreadParams::DefaultStackSize,
+                                  PROT_READ | PROT_WRITE,
+                                  MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
+  if (stack == MAP_FAILED)
+    return llvmlibc_errno == ENOMEM ? thrd_nomem : thrd_error;
+
+  thread->__stack = stack;
+  thread->__stack_size = ThreadParams::DefaultStackSize;
+  thread->__retval = -1;
+  FutexData *clear_tid_address =
+      reinterpret_cast<FutexData *>(thread->__clear_tid);
+  *clear_tid_address = ThreadParams::ClearTIDValue;
+
+  // When the new thread is spawned by the kernel, the new thread gets the
+  // stack we pass to the clone syscall. However, this stack is empty and does
+  // not have any local vars present in this function. Hence, one cannot
+  // pass arguments to the thread start function, or use any local vars from
+  // here. So, we pack them into the new stack from where the thread can sniff
+  // them out.
+  uintptr_t adjusted_stack = reinterpret_cast<uintptr_t>(stack) +
+                             ThreadParams::DefaultStackSize - sizeof(StartArgs);
+  StartArgs *start_args = reinterpret_cast<StartArgs *>(adjusted_stack);
+  start_args->thread = thread;
+  start_args->func = func;
+  start_args->arg = arg;
+
+  long clone_result =
+      __llvm_libc::syscall(SYS_clone, clone_flags, adjusted_stack,
+                           &thread->__tid, clear_tid_address, 0);
+
+  if (clone_result == 0) {
+    start_thread();
+  } else if (clone_result < 0) {
+    int error_val = -clone_result;
+    return error_val == ENOMEM ? thrd_nomem : thrd_error;
+  }
+
+  return thrd_success;
+}
+
+} // namespace __llvm_libc

libc/src/threads/linux/thrd_join.cpp

+//===----------- Linux implementation of the thrd_join 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 function.
+#include "include/sys/syscall.h"  // For syscall numbers.
+#include "include/threads.h"      // For thrd_* type definitions.
+#include "src/__support/common.h"
+#include "src/sys/mman/munmap.h"
+#include "src/threads/linux/thread_utils.h"
+
+#include <linux/futex.h> // For futex operations.
+#include <stdatomic.h>   // For atomic_load.
+
+namespace __llvm_libc {
+
+int LLVM_LIBC_ENTRYPOINT(thrd_join)(thrd_t *thread, int *retval) {
+  FutexData *clear_tid_address =
+      reinterpret_cast<FutexData *>(thread->__clear_tid);
+
+  while (atomic_load(clear_tid_address) != 0) {
+    // We cannot do a FUTEX_WAIT_PRIVATE here as the kernel does a
+    // FUTEX_WAKE and not a FUTEX_WAKE_PRIVATE.
+    __llvm_libc::syscall(SYS_futex, clear_tid_address, FUTEX_WAIT,
+                         ThreadParams::ClearTIDValue, nullptr);
+
+    // The kernel should set the value at the clear tid address to zero.
+    // If not, it is a spurious wake and we should continue to wait on
+    // the futex.
+  }
+
+  *retval = thread->__retval;
+
+  if (__llvm_libc::munmap(thread->__stack, thread->__stack_size) == -1)
+    return thrd_error;
+
+  return thrd_success;
+}
+
+} // namespace __llvm_libc

libc/src/threads/linux/thread_start_args.h.def

-//===---------------- C standard library header threads.h -----------------===//
+//===---- Implementation of the get_start_args_addr 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
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_LIBC_THREADS_H
-#define LLVM_LIBC_THREADS_H
+#include <stdint.h>
 
-#include <__llvm-libc-common.h>
-
-%%public_api()
-
-#endif // LLVM_LIBC_THREADS_H
+%%include_file(${thread_start_args})

libc/src/threads/linux/thread_utils.h

+//===-- Linux specific definitions for threads implementations. --*- 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_THREAD_UTILS_H
+#define LLVM_LIBC_SRC_THREADS_LINUX_THREAD_UTILS_H
+
+#include "thread_start_args.h"
+
+#include <stdatomic.h>
+#include <stdint.h>
+
+// The futex data has to be exactly 4 bytes long. However, we use a uchar type
+// here as we do not want to use the _Atomic keyword which is C only. The header
+// stdatomic.h does not define an atomic type which is exaclty 4 bytes wide.
+// Using a narrower type here is OK as long we ensure that the values we read
+// and write fit in a byte.
+using FutexData = atomic_uchar;
+
+struct ThreadParams {
+  static constexpr uintptr_t DefaultStackSize = 1 << 16; // 64 KB
+  static constexpr uint32_t ClearTIDValue = 0xAB;
+};
+
+#endif // LLVM_LIBC_SRC_THREADS_LINUX_THREAD_UTILS_H

libc/src/threads/linux/x86_64/thread_start_args.h.in

+//===- x86_64 implementation of the get_start_args_addr 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
+//
+//===----------------------------------------------------------------------===//
+
+%%begin()
+
+__attribute__((always_inline)) inline uintptr_t get_start_args_addr() {
+  // NOTE: For __builtin_frame_address to workd reliably across compilers,
+  // architectures and various optimization levels, the TU including this file
+  // should be compiled with -fno-omit-frame-pointer.
+  return reinterpret_cast<uintptr_t>(__builtin_frame_address(0)) +
+         // The x86_64 call instruction pushes resume address on to the stack.
+         // Next, The x86_64 SysV ABI also pushes the frame pointer on the
+         // stack. Hence, we look past these items to get to the start args.
+         sizeof(uintptr_t) * 2;
+}
+

libc/src/threads/thrd_create.h

+//===------- Implementation header for thrd_create 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_THREADS_LINUX_THRD_CREATE_H
+#define LLVM_LIBC_SRC_THREADS_LINUX_THRD_CREATE_H
+
+#include "include/threads.h"
+
+namespace __llvm_libc {
+
+int thrd_create(thrd_t *thread, thrd_start_t func, void *arg);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_THREADS_LINUX_THRD_CREATE_H

libc/src/threads/thrd_join.h

+//===-------- Implementation header for thrd_join 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_THREADS_LINUX_THRD_JOIN_H
+#define LLVM_LIBC_SRC_THREADS_LINUX_THRD_JOIN_H
+
+#include "include/threads.h"
+
+namespace __llvm_libc {
+
+int thrd_join(thrd_t *thread, int *retval);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_THREADS_LINUX_THRD_JOIN_H

libc/test/src/CMakeLists.txt

 add_subdirectory(errno)
 add_subdirectory(signal)
 add_subdirectory(stdlib)
 add_subdirectory(string)
 add_subdirectory(sys)
+add_subdirectory(threads)

libc/test/src/threads/CMakeLists.txt

+add_libc_testsuite(libc_threads_unittests)
+
+add_libc_unittest(
+  thrd_test
+  SUITE
+    libc_threads_unittests
+  SRCS
+    thrd_test.cpp
+  DEPENDS
+    __errno_location
+    mmap
+    munmap
+    threads_h
+    thrd_create
+    thrd_join
+)

libc/test/src/threads/thrd_test.cpp

+//===---------------------- Unittests for thrd_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/thrd_create.h"
+#include "src/threads/thrd_join.h"
+#include "utils/UnitTest/Test.h"
+
+static constexpr int thread_count = 1000;
+static int counter = 0;
+static int thread_func(void *) {
+  ++counter;
+  return 0;
+}
+
+TEST(ThreadTest, CreateAndJoin) {
+  for (counter = 0; counter <= thread_count;) {
+    thrd_t thread;
+    int old_counter_val = counter;
+    ASSERT_EQ(__llvm_libc::thrd_create(&thread, thread_func, nullptr),
+              (int)thrd_success);
+    int retval = thread_count + 1; // Start with a retval we dont expect.
+    ASSERT_EQ(__llvm_libc::thrd_join(&thread, &retval), (int)thrd_success);
+    ASSERT_EQ(retval, 0);
+    ASSERT_EQ(counter, old_counter_val + 1);
+  }
+}
+
+static int return_arg(void *arg) { return *reinterpret_cast<int *>(arg); }
+
+TEST(ThreadTest, SpawnAndJoin) {
+  thrd_t thread_list[thread_count];
+  int args[thread_count];
+
+  for (int i = 0; i < thread_count; ++i) {
+    args[i] = i;
+    ASSERT_EQ(__llvm_libc::thrd_create(thread_list + i, return_arg, args + i),
+              (int)thrd_success);
+  }
+
+  for (int i = 0; i < thread_count; ++i) {
+    int retval = thread_count + 1; // Start with a retval we dont expect.
+    ASSERT_EQ(__llvm_libc::thrd_join(&thread_list[i], &retval),
+              (int)thrd_success);
+    ASSERT_EQ(retval, i);
+  }
+}