[libc] Add implementation of call_once from threads.h.

[abrachet]

libc/src/threads/call_once.cpp

21 ↗

(On Diff #263572)

Should we use ONCE_FLAG_INIT instead of 0?

libc/test/src/threads/call_once_test.cpp

28

This and the mtx_* functions are not prefaced with __llvm_libc::

30–32

Maybe we could just make thread_count an atomic type so we're only testing call_once and not mtx_*?

Are there some architectures don't have support for locking instructions and must call into libc to support atomic types?

[sivachandra]

Address comments.

libc/test/src/threads/call_once_test.cpp

28

That was a blunder! Thanks for catching.

30–32

About the various architectures, like how we require the compiler provide freestanding headers, I think we should require that the compiler provide stdatomic.h. It isn't unreasonable: atomics library should be provided by the compiler or by the libc. We want the compiler to do it as they already have knowledge of the target architecture.

[abrachet]

libc/test/src/threads/call_once_test.cpp

28

I believe the _Atomic types let you just do += 1 and let the compiler call atomic_fetch_add4 if needed

[MaskRay]

This is incorrect.

Completion of an effective call to the call_once function synchronizes with all subsequent calls to the call_once function with the same value of flag.

Before the completion, the subsequent call should wait.

[sivachandra]

In D79828#2034708, @MaskRay wrote:

This is incorrect.

Completion of an effective call to the call_once function synchronizes with all subsequent calls to the call_once function with the same value of flag.

Before the completion, the subsequent call should wait.

Thanks for catching this. Will fix it soon.

[sivachandra]

Synchronize callers to the return from the called function.

[abrachet]

This looks good to me but it might be worth waiting for @MaskRay if he has anything to say because I missed this the first time.

libc/test/src/threads/call_once_test.cpp

61

Maybe we could assert that done_count is 0 before unlocking?

[MaskRay]

This is correct but slow, because there is always a futex syscall. A better approach is to add at least another state "initialization has finished". If the cas returns that state, don't bother calling wait. (It may also make sense to optimize the initial cas with an acquire load.)

This may also be a good example demonstrating that implementing pthread with C11 threads can cause duplication. In reality few applications use call_once. They all call pthread_once. For pthread_once, you need to think of pthread cancelling, which has to use more mechanism.

[sivachandra]

Make syscall only if required.

[MaskRay]

I think the logic is correct now, but my pthread_once argument persists. pthread_once provides strictly more features (pthread cancel) and people don't care about the performance of C11 call_once (nobody/few use it).
Piggybacking call_once on top of pthread_once is fine and likely favorable because this makes the code/binary sizes smaller.

libc/src/threads/linux/call_once.cpp

22

I don't think we need such special magic numbers instead of sequential 0, 1, 2, 3..

Larger immediates are slower (may require more than one insn) to load on some RISC architectures.

[MaskRay]

libc/src/threads/linux/call_once.cpp

22

Also, unsigned int -> unsigned

[sivachandra]

I have now submitted this after addressing all comments. Thanks a lot @MaskRay for helping me understand the wording in the standard.

libc/config/linux/api.td

let Functions = [
     "sigprocmask",
     "sigemptyset",
     "sigaddset",
     "sigfillset",
     "signal",
   ];
 }
 
+def OnceFlag : TypeDecl<"once_flag"> {
+  let Decl = [{
+    typedef unsigned int once_flag;
+  }];
+}
+
 def MtxT : TypeDecl<"mtx_t"> {
   let Decl = [{
     typedef struct {
       unsigned char __internal_data[4];
       int __mtx_type;
     } mtx_t;
   }];
 }
 
 def ThreadStartT : TypeDecl<"thrd_start_t"> {
   let Decl = "typedef int (*thrd_start_t)(void *);";
 }
 
+def CallOnceFuncT : TypeDecl<"__call_once_func_t"> {
+  let Decl = [{
+    typedef void(*__call_once_func_t)(void);
+  }];
+}
+
 def ThreadsAPI : PublicAPI<"threads.h"> {
+  let Macros = [
+    SimpleMacroDef<"ONCE_FLAG_INIT", "0">,
+  ];
+
   let TypeDeclarations = [
+    OnceFlag,
+    CallOnceFuncT,
     MtxT,
     ThreadStartT,
   ];
 
   let Enumerations = [
     "mtx_plain",
     "mtx_recursive",
     "mtx_timed",
     "thrd_timedout",
     "thrd_success",
     "thrd_busy",
     "thrd_error",
     "thrd_nomem",
   ];
 
   let Functions = [
+    "call_once",
     "mtx_init",
     "mtx_lock",
     "mtx_unlock",
     "thrd_create",
     "thrd_join",
   ];
 }
 

libc/lib/CMakeLists.txt

DEPENDS
     libc.src.string.strcpy
     libc.src.string.strlen
 
     # sys/mman.h entrypoints
     libc.src.sys.mman.mmap
     libc.src.sys.mman.munmap
 
     # threads.h entrypoints
+    libc.src.threads.call_once
     libc.src.threads.mtx_init
     libc.src.threads.mtx_lock
     libc.src.threads.mtx_unlock
     libc.src.threads.thrd_create
     libc.src.threads.thrd_join
 
     # unistd.h entrypoints
     libc.src.unistd.write

libc/spec/stdc.td

 def StdC : StandardSpec<"stdc"> {
   ConstType ConstVoidPtr = ConstType<VoidPtr>;
   RestrictedPtrType VoidRestrictedPtr = RestrictedPtrType<VoidType>;
   ConstType ConstVoidRestrictedPtr = ConstType<VoidRestrictedPtr>;
 
   PtrType CharPtr = PtrType<CharType>;
   ConstType ConstCharPtr = ConstType<CharPtr>;
   RestrictedPtrType CharRestrictedPtr = RestrictedPtrType<CharType>;
   ConstType ConstCharRestrictedPtr = ConstType<CharRestrictedPtr>;
 
+  NamedType OnceFlagType = NamedType<"once_flag">;
+  PtrType OnceFlagTypePtr = PtrType<OnceFlagType>;
+  // TODO(sivachandra): Remove this non-standard type when a formal
+  // way to describe callable types is available.
+  NamedType CallOnceFuncType = NamedType<"__call_once_func_t">;
   NamedType MtxTType = NamedType<"mtx_t">;
   PtrType MtxTTypePtr = PtrType<MtxTType>;
   NamedType ThrdStartTType = NamedType<"thrd_start_t">;
   NamedType ThrdTType = NamedType<"thrd_t">;
   PtrType ThrdTTypePtr = PtrType<ThrdTType>;
 
   PtrType IntPtr = PtrType<IntType>;
 
HeaderSpec Signal = HeaderSpec<
           RetValSpec<SigHandlerT>,
           [ArgSpec<IntType>, ArgSpec<SigHandlerT>]
         >,
       ]
   >;
 
   HeaderSpec Threads = HeaderSpec<
       "threads.h",
-      [], // Macros
       [
+          Macro<"ONCE_FLAG_INIT">,
+      ],
+      [
+          OnceFlagType,
+          CallOnceFuncType,
           MtxTType,
           ThrdStartTType,
           ThrdTType,
       ],
       [
           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<
+              "call_once",
+              RetValSpec<VoidType>,
+              [
+                  ArgSpec<OnceFlagTypePtr>,
+                  ArgSpec<CallOnceFuncType>,
+              ]
+          >,
+          FunctionSpec<
               "mtx_init",
               RetValSpec<IntType>,
               [
                   ArgSpec<MtxTTypePtr>,
                   ArgSpec<IntType>,
               ]
           >,
           FunctionSpec<

libc/src/threads/CMakeLists.txt

 if(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/${LIBC_TARGET_OS})
   add_subdirectory(${LIBC_TARGET_OS})
 endif()
 
 add_entrypoint_object(
+  call_once
+  ALIAS
+  DEPENDS
+    .${LIBC_TARGET_OS}.call_once
+)
+
+add_entrypoint_object(
   thrd_create
   ALIAS
   DEPENDS
     .${LIBC_TARGET_OS}.thrd_create
 )
 
 add_entrypoint_object(
   thrd_join

libc/src/threads/call_once.h

+//===-- Implementation header for call_once 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_CALL_ONCE_H
+#define LLVM_LIBC_SRC_THREADS_CALL_ONCE_H
+
+#include "include/threads.h"
+
+namespace __llvm_libc {
+
+void call_once(once_flag *flag, __call_once_func_t func);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_THREADS_CALL_ONCE_H

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_entrypoint_object(
+  call_once
+  SRCS
+    call_once.cpp
+  HDRS
+    ../call_once.h
+  DEPENDS
+    .threads_utils
+    libc.config.linux.linux_syscall_h
+    libc.include.sys_syscall
+    libc.include.threads
+)
+
 add_header_library(
   threads_utils
   HDRS
     thread_utils.h
   DEPENDS
     .thread_start_args_h
 )
 

libc/src/threads/linux/call_once.cpp

+//===-- Linux implementation of the call_once 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 call_once related type definition.
+#include "src/__support/common.h"
+#include "src/threads/linux/thread_utils.h"
+
+#include <limits.h>
+#include <linux/futex.h>
+#include <stdatomic.h>
+
+namespace __llvm_libc {
+
+static constexpr unsigned START = 0x11;
+static constexpr unsigned WAITING = 0x22;
+static constexpr unsigned FINISH = 0x33;
+
+void LLVM_LIBC_ENTRYPOINT(call_once)(once_flag *flag, __call_once_func_t func) {
+  FutexData *futex_word = reinterpret_cast<FutexData *>(flag);
+  unsigned int not_called = ONCE_FLAG_INIT;
+
+  // The C standard wording says:
+  //
+  //     The completion of the function func synchronizes with all
+  //     previous or subsequent calls to call_once with the same
+  //     flag variable.
+  //
+  // What this means is that, the call_once call can return only after
+  // the called function |func| returns. So, we use futexes to synchronize
+  // calls with the same flag value.
+  if (::atomic_compare_exchange_strong(futex_word, &not_called, START)) {
+    func();
+    auto status = ::atomic_exchange(futex_word, FINISH);
+    if (status == WAITING) {
+      __llvm_libc::syscall(SYS_futex, futex_word, FUTEX_WAKE_PRIVATE,
+                           INT_MAX, // Wake all waiters.
+                           0, 0, 0);
+    }
+    return;
+  }
+
+  unsigned int status = START;
+  if (::atomic_compare_exchange_strong(futex_word, &status, WAITING) ||
+      status == WAITING) {
+    __llvm_libc::syscall(SYS_futex, futex_word, FUTEX_WAIT_PRIVATE,
+                         WAITING, // Block only if status is still |WAITING|.
+                         0, 0, 0);
+  }
+}
+
+} // namespace __llvm_libc

libc/test/src/threads/CMakeLists.txt

 add_libc_testsuite(libc_threads_unittests)
 
 add_libc_unittest(
+  call_once_test
+  SUITE
+    libc_threads_unittests
+  SRCS
+    call_once_test.cpp
+  DEPENDS
+    libc.include.threads
+    libc.src.threads.call_once
+    libc.src.threads.mtx_init
+    libc.src.threads.mtx_lock
+    libc.src.threads.mtx_unlock
+    libc.src.threads.thrd_create
+    libc.src.threads.thrd_join
+)
+
+add_libc_unittest(
   thrd_test
   SUITE
     libc_threads_unittests
   SRCS
     thrd_test.cpp
   DEPENDS
     libc.include.threads
     libc.src.errno.__errno_location

libc/test/src/threads/call_once_test.cpp

+//===-- Unittests for call_once -------------------------------------------===//
+//
+// 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/call_once.h"
+#include "src/threads/mtx_init.h"
+#include "src/threads/mtx_lock.h"
+#include "src/threads/mtx_unlock.h"
+#include "src/threads/thrd_create.h"
+#include "src/threads/thrd_join.h"
+#include "utils/UnitTest/Test.h"
+
+#include <stdatomic.h>
+
+static constexpr unsigned int num_threads = 5;
+static atomic_uint thread_count;
+
+static unsigned int call_count;
+static void call_once_func() { ++call_count; }
+
+static int func(void *) {
+  static once_flag flag = ONCE_FLAG_INIT;
+  __llvm_libc::call_once(&flag, call_once_func);
+
+  ++thread_count; // This is a an atomic update.
+
+  return 0;
+}
+
+TEST(CallOnceTest, CallFrom5Threads) {
+  // Ensure the call count and thread count are 0 to begin with.
+  call_count = 0;
+  thread_count = 0;
+
+  thrd_t threads[num_threads];
+  for (unsigned int i = 0; i < num_threads; ++i) {
+    ASSERT_EQ(__llvm_libc::thrd_create(threads + i, func, nullptr),
+              static_cast<int>(thrd_success));
+  }
+
+  for (unsigned int i = 0; i < num_threads; ++i) {
+    int retval;
+    ASSERT_EQ(__llvm_libc::thrd_join(threads + i, &retval),
+              static_cast<int>(thrd_success));
+    ASSERT_EQ(retval, 0);
+  }
+
+  EXPECT_EQ(static_cast<unsigned int>(thread_count), 5U);
+  EXPECT_EQ(call_count, 1U);
+}
+
+static mtx_t once_func_blocker;
+static void blocking_once_func() {
+  __llvm_libc::mtx_lock(&once_func_blocker);
+  __llvm_libc::mtx_unlock(&once_func_blocker);
+}
+
+static atomic_uint start_count;
+static atomic_uint done_count;
+static int once_func_caller(void *) {
+  static once_flag flag;
+  ++start_count;
+  __llvm_libc::call_once(&flag, blocking_once_func);
+  ++done_count;
+  return 0;
+}
+
+// Test the synchronization aspect of the call_once function.
+// This is not a fool proof test, but something which might be
+// useful when we add a flakiness detection scheme to UnitTest.
+TEST(CallOnceTest, TestSynchronization) {
+  start_count = 0;
+  done_count = 0;
+
+  ASSERT_EQ(__llvm_libc::mtx_init(&once_func_blocker, mtx_plain),
+            static_cast<int>(thrd_success));
+  // Lock the blocking mutex so that the once func blocks.
+  ASSERT_EQ(__llvm_libc::mtx_lock(&once_func_blocker),
+            static_cast<int>(thrd_success));
+
+  thrd_t t1, t2;
+  ASSERT_EQ(__llvm_libc::thrd_create(&t1, once_func_caller, nullptr),
+            static_cast<int>(thrd_success));
+  ASSERT_EQ(__llvm_libc::thrd_create(&t2, once_func_caller, nullptr),
+            static_cast<int>(thrd_success));
+
+  while (start_count != 2)
+    ; // Spin until both threads start.
+
+  // Since the once func is blocked, the threads should not be done yet.
+  EXPECT_EQ(static_cast<unsigned int>(done_count), 0U);
+
+  // Unlock the blocking mutex so that the once func blocks.
+  ASSERT_EQ(__llvm_libc::mtx_unlock(&once_func_blocker),
+            static_cast<int>(thrd_success));
+
+  int retval;
+  ASSERT_EQ(__llvm_libc::thrd_join(&t1, &retval),
+            static_cast<int>(thrd_success));
+  ASSERT_EQ(retval, 0);
+  ASSERT_EQ(__llvm_libc::thrd_join(&t2, &retval),
+            static_cast<int>(thrd_success));
+  ASSERT_EQ(retval, 0);
+
+  ASSERT_EQ(static_cast<unsigned int>(done_count), 2U);
+}