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

[abrachet]

libc/src/threads/call_once.cpp

22

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

27

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

21 ↗

(On Diff #265647)

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

21 ↗

(On Diff #265647)

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.strcat
     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
+  SRCS
+    call_once.cpp
+  HDRS
+    call_once.h
+  DEPENDS
+    libc.include.threads
+)
+
+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/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 "include/threads.h" // For call_once related type definition.
+#include "src/__support/common.h"
+
+#include <stdatomic.h>
+#include <stdint.h>
+
+namespace __llvm_libc {
+
+static constexpr unsigned int CALLED = 0xCA11ED;
+
+void LLVM_LIBC_ENTRYPOINT(call_once)(once_flag *flag, __call_once_func_t func) {
+  atomic_uint *atomic_flag = reinterpret_cast<atomic_uint *>(flag);
+  unsigned int not_called = ONCE_FLAG_INIT;
+
+  if (::atomic_compare_exchange_strong(atomic_flag, &not_called, CALLED))
+    func();
+}
+
+} // 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/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 unsigned int call_count = 0;
+static void call_once_func() { ++call_count; }
+
+static atomic_uint thread_count = 0;
+static int func(void *) {
+  static once_flag flag = ONCE_FLAG_INIT;
+  __llvm_libc::call_once(&flag, call_once_func);
+
+  ::atomic_fetch_add(&thread_count, 1);
+
+  return 0;
+}
+
+TEST(CallOnceTest, CallFrom5Threads) {
+  // Ensure the call count and thread count are 0 to begin with.
+  EXPECT_EQ(call_count, 0U);
+  EXPECT_EQ(static_cast<unsigned int>(thread_count), 0U);
+
+  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);
+}