[libc] Add simple implementations of mtx_lock and mtx_unlock.

[sivachandra]

Summary

These functions only support locking and unlocking of plain mutexes.
They will be extended in future changes to handled recursive and timed
mutexes.

Depends on D75380.

[sivachandra]

libc/src/threads/linux/mtx_lock.cpp

17

Though stdatomic.h is not a free standing header, we will use the one provided by the compilers. LLVM-libc will not provide it.

[MaskRay]

A mutex implementation will need congestion counts. If only a shim is needed, a bi-state mutex is sufficient.

I think pthread_mutex_timedlock and pthread_mutex_unlock can be implemented first, then rebase mtx_lock and mtx_unlock on pthread. A libc eventually has to implement pthread to be usable on a POSIX platform. It can be a shim, with just the basic functionality. Even if you don't want to think of pthread initially, mtx_lock should be based on mtx_timedlock.

We can assume Linux>=2.6.22 and use FUTEX_PRIVATE_FLAG.

[sivachandra]

In D74653#1877328, @MaskRay wrote:

A mutex implementation will need congestion counts. If only a shim is needed, a bi-state mutex is sufficient.

A tri-state mutex helps us avoid an unnecessary futext syscall.

I think pthread_mutex_timedlock and pthread_mutex_unlock can be implemented first, then rebase mtx_lock and mtx_unlock on pthread. A libc eventually has to implement pthread to be usable on a POSIX platform. It can be a shim, with just the basic functionality. Even if you don't want to think of pthread initially, mtx_lock should be based on mtx_timedlock.

In LLVM libc, we want to take the opposite approach of implementing pthread as an extension over standard C thread library.

Agree mtx_lock could be a specialization of mtx_timedlock. As I said in the description, this patch is only a simple implementation of a plain mutex. It allows me to avoid worrying about he timespec API for now. Having a plain mutex available paves way for adding and testing other parts of the libc system.

We can assume Linux>=2.6.22 and use FUTEX_PRIVATE_FLAG.

Agreed. I was not sure, but since you also bring it up, I can go ahead with that change. I will update in the next round.

[abrachet]

In D74653#1877381, @sivachandra wrote:

In D74653#1877328, @MaskRay wrote:

I think pthread_mutex_timedlock and pthread_mutex_unlock can be implemented first, then rebase mtx_lock and mtx_unlock on pthread. A libc eventually has to implement pthread to be usable on a POSIX platform. It can be a shim, with just the basic functionality. Even if you don't want to think of pthread initially, mtx_lock should be based on mtx_timedlock.

In LLVM libc, we want to take the opposite approach of implementing pthread as an extension over standard C thread library.

My intuition (I've never really used <threads.h>) is that it will be more difficult than the opposite because pthread provides many more options than C11's thread library. I think this patch is good and it'll be useful to have mutex's but my guess is when we implement pthread it will become untenable to use what we currently have.

libc/include/threads.h.def

9–10 ↗

(On Diff #244775)

LIBC_THREADS_H

libc/lib/CMakeLists.txt

15

You could add a comment here like the rest of them have, but I don't think its needed, its just more cohesive.

libc/src/threads/linux/mtx_lock.cpp

28

I think it would be more readable if this looked like

if (atomic_compare_exchange_strong(futex_data, &mutex_status, MS_Locked))
  return thrd_success;
switch(mutex_status) {
...
}

libc/src/threads/linux/mtx_unlock.cpp

28

The cast should no longer be necessary.

33

no body -> nobody

libc/src/threads/linux/mutex.h

17 ↗

(On Diff #244775)

We could make this enum class MutexStatus and drop the MS_ prefix and refer to these as MutexStatus::Free perhaps.

19 ↗

(On Diff #244775)

Prefer using.

[sivachandra]

Address comments.

[sivachandra]

libc/src/threads/linux/mutex.h

17 ↗

(On Diff #244775)

That would be nice, but then we will need casts to integer types as stdatomic.h API wants integer types.

[phosek]

Would it be possible to land the enumeration support separately? These are separate changes and I think it'd be cleaner to land them as two commits.

libc/config/linux/api.td

146

Do you plan to graduate these eventually to a common file (and layer Linux on top)? These API aren't Linux specific and we would like to provide these definitions on other platforms like Fuchsia.

libc/test/src/threads/linux/mtx_test.cpp

18

Can you make these constexpr?

[sivachandra]

• Seperate enum generation to a different patch
• Use threads from LLVM libc to construct mutex tests
• Remove use of sleep from tests

[sivachandra]

In D74653#1892046, @phosek wrote:

Would it be possible to land the enumeration support separately? These are separate changes and I think it'd be cleaner to land them as two commits.

Done now: https://reviews.llvm.org/D75379

libc/config/linux/api.td

146

Yes. When we have another platform file, we will put the common parts in a common file.

[phosek]

LGTM

libc/config/linux/api.td

def SignalAPI : PublicAPI<"signal.h"> {
   let TypeDeclarations = [
     SizeT, // This is needed by <linux/signal.h>.
   ];
 
   let Functions = [
     "raise",
   ];
 }
 
+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 ThreadsAPI : PublicAPI<"threads.h"> {
   let TypeDeclarations = [
+    MtxT,
     ThreadStartT,
   ];
 
   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",
     "thrd_create",
     "thrd_join",
   ];
 }

libc/lib/CMakeLists.txt

 
 add_entrypoint_library(
   llvmlibc
   DEPENDS
     # errno.h entrypoints
     __errno_location
 
     # string.h entrypoints
     strcpy
     strcat
 
     # sys/mman.h entrypoints
     mmap
     munmap
 
     # signal.h entrypoints
     raise
 
     # threads.h entrypoints
     thrd_create
     thrd_join
+    mtx_init
+    mtx_lock
+    mtx_unlock
 )
 
 add_entrypoint_library(
   llvmlibm
   DEPENDS
     # math.h entrypoints
     round
 )
 
 add_redirector_library(
   llvmlibc_redirectors
   DEPENDS
     round_redirector
 )

libc/src/threads/linux/CMakeLists.txt

add_entrypoint_object(
   DEPENDS
     linux_syscall_h
     munmap
     support_common_h
     sys_syscall_h
     threads_h
     threads_utils
 )
+
+add_entrypoint_object(
+  mtx_init
+  SRCS
+    mtx_init.cpp
+  HDRS
+    ../mtx_init.h
+  DEPENDS
+    support_common_h
+    threads_h
+    threads_utils
+)
+
+add_entrypoint_object(
+  mtx_lock
+  SRCS
+    mtx_lock.cpp
+  HDRS
+    ../mtx_lock.h
+  DEPENDS
+    __errno_location
+    linux_syscall_h
+    support_common_h
+    sys_syscall_h
+    threads_h
+    threads_utils
+)
+
+add_entrypoint_object(
+  mtx_unlock
+  SRCS
+    mtx_unlock.cpp
+  HDRS
+    ../mtx_unlock.h
+  DEPENDS
+    linux_syscall_h
+    support_common_h
+    sys_syscall_h
+    threads_h
+    threads_utils
+)

libc/src/threads/linux/mtx_init.cpp

+//===----------- 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/thread_utils.h"
+
+namespace __llvm_libc {
+
+int LLVM_LIBC_ENTRYPOINT(mtx_init)(mtx_t *mutex, int type) {
+  *(reinterpret_cast<uint32_t *>(mutex->__internal_data)) = MS_Free;
+  mutex->__mtx_type = type;
+  return thrd_success;
+}
+
+} // namespace __llvm_libc

libc/src/threads/linux/mtx_lock.cpp

+//===----------- 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/thread_utils.h"
+
+#include <linux/futex.h> // For futex operations.
+#include <stdatomic.h>   // 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<FutexData *>(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))
+      return thrd_success;
+
+    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, futex_data, FUTEX_WAIT_PRIVATE,
+                           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, futex_data, FUTEX_WAIT_PRIVATE,
+                             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;
+    }
+  }
+}
+
+} // namespace __llvm_libc

libc/src/threads/linux/mtx_unlock.cpp

+//===---------- 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/thread_utils.h"
+
+#include <linux/futex.h> // For futex operations.
+#include <stdatomic.h>   // 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<FutexData *>(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, futex_word, 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))
+        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

libc/src/threads/linux/thread_utils.h

 //===--- 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_THREAD_UTILS_H
 #define LLVM_LIBC_SRC_THREADS_LINUX_THREAD_UTILS_H
 
 #include <stdint.h>
 
+// 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 `MutexStatus::Waiting`.
+enum MutexStatus : uint32_t { MS_Free, MS_Locked, MS_Waiting };
+
 using FutexData = _Atomic uint32_t;
 
 #define DEFAULT_STACK_SIZE (1 << 15) // 32 KB
 
 #define CLEAR_TID_VALUE 0xABCD1234
 
 #endif // LLVM_LIBC_SRC_THREADS_LINUX_THREAD_UTILS_H

libc/src/threads/mtx_init.h

+//===---------- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_THREADS_LINUX_MTX_INIT_H
+#define LLVM_LIBC_SRC_THREADS_LINUX_MTX_INIT_H
+
+#include "include/threads.h"
+
+namespace __llvm_libc {
+
+int mtx_int(mtx_t *mutex, int type);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_THREADS_LINUX_MTX_INIT_H

libc/src/threads/mtx_lock.h

+//===---------- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_THREADS_LINUX_MTX_LOCK_H
+#define LLVM_LIBC_SRC_THREADS_LINUX_MTX_LOCK_H
+
+#include "include/threads.h"
+
+namespace __llvm_libc {
+
+int mtx_lock(mtx_t *mutex);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_THREADS_LINUX_MTX_LOCK_H

libc/src/threads/mtx_unlock.h

+//===-------- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_THREADS_LINUX_MTX_UNLOCK_H
+#define LLVM_LIBC_SRC_THREADS_LINUX_MTX_UNLOCK_H
+
+#include "include/threads.h"
+
+namespace __llvm_libc {
+
+int mtx_unlock(mtx_t *mutex);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_THREADS_LINUX_MTX_UNLOCK_H

libc/test/src/threads/linux/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
 )
+
+add_libc_unittest(
+  mtx_test
+  SUITE
+    libc_threads_unittests
+  SRCS
+    mtx_test.cpp
+  DEPENDS
+    __errno_location
+    mmap
+    munmap
+    mtx_init
+    mtx_lock
+    mtx_unlock
+    thrd_create
+    thrd_join
+    threads_h
+)
+
+target_link_libraries(mtx_test PRIVATE -lpthread)

libc/test/src/threads/linux/mtx_test.cpp

+//===---------------------- 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 "src/threads/thrd_create.h"
+#include "src/threads/thrd_join.h"
+#include "utils/UnitTest/Test.h"
+
+constexpr int START = 0;
+constexpr int MAX = 10000;
+
+mtx_t mutex;
+static int shared_int = START;
+
+int counter(void *arg) {
+  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;
+  }
+  return 0;
+}
+
+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.
+  thrd_t thread;
+  __llvm_libc::thrd_create(&thread, counter, nullptr);
+
+  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;
+  }
+
+  int retval = 123;
+  __llvm_libc::thrd_join(&thread, &retval);
+  ASSERT_EQ(retval, 0);
+}
+
+mtx_t start_lock, step_lock;
+bool start, step;
+
+int stepper(void *arg) {
+  __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);
+  return 0;
+}
+
+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);
+
+  thrd_t thread;
+  __llvm_libc::thrd_create(&thread, stepper, nullptr);
+
+  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;
+  }
+
+  // Since |step_lock| is still locked, |step| should be false.
+  ASSERT_FALSE(step);
+
+  // Unlock the step lock and wait until the step is made.
+  ASSERT_EQ(__llvm_libc::mtx_unlock(&step_lock), (int)thrd_success);
+
+  while (true) {
+    ASSERT_EQ(__llvm_libc::mtx_lock(&step_lock), (int)thrd_success);
+    bool current_step_value = step;
+    ASSERT_EQ(__llvm_libc::mtx_unlock(&step_lock), (int)thrd_success);
+    if (current_step_value)
+      break;
+  }
+
+  int retval = 123;
+  __llvm_libc::thrd_join(&thread, &retval);
+  ASSERT_EQ(retval, 0);
+}