[libc] Fix mtx_unlock to handle multiple waiters on a single mutex.

[grandinj]

But now you have a "thundering herd" problem?

[sivachandra]

In D80398#2051957, @grandinj wrote:

But now you have a "thundering herd" problem?

Yes, I am aware of this. Sorry for not being more descriptive about what I have in mind. My goal was to implement a self-contained mutex. As in, a mutex which can be used with any threading library. Most other libc implementations use a higher level futex locking facility (FUTEX_LOCK_PI and friends). We can take the same route here, but it has some shortcomings:

1. The "fastest" implementation will tie us to a specific threading library (which for us will/should be LLVM libc's threading library) as it will use thread local storage.
2. The slowest implementation can avoid using TLS but will require one additional syscall each in the lock and unlock functions.

We have two alternates:

1. This patch. But, obviously it leads to the thundering herd problem.
2. Use a counter to keep track of the current set of waiters. This counter has to be an atomic object so will not match the performance of #1 from above.

I am now beginning to feel that going the route of #1 from the first list is probably the right approach. FWIW, the infrastructure we build is required anyway to implement other pieces like recursive locks.

[sivachandra]

Just a note: I will update this patch shortly with a more optimal solution.

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 <limits.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);
+      // If any thread is waiting to be woken up, then do it. We wake up all
+      // waiters as this will ensure that the correct mutex status gets set.
+      // If we wake up only one waiter, then that waiter will lock the mutex
+      // with status MS_Locked and never realize that there are other waiters.
+      // But waking up all waiters, we make sure that the waiters which do not
+      // get the lock set the status back to MS_Waiting.
+      __llvm_libc::syscall(SYS_futex, futex_word, FUTEX_WAKE_PRIVATE, INT_MAX,
+                           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/test/src/threads/mtx_test.cpp

while (true) {
     if (current_step_value)
       break;
   }
 
   int retval = 123;
   __llvm_libc::thrd_join(&thread, &retval);
   ASSERT_EQ(retval, 0);
 }
+
+static constexpr int THREAD_COUNT = 10;
+static mtx_t multiple_waiter_lock;
+static mtx_t counter_lock;
+static int wait_count = 0;
+
+int waiter_func(void *) {
+  __llvm_libc::mtx_lock(&counter_lock);
+  ++wait_count;
+  __llvm_libc::mtx_unlock(&counter_lock);
+
+  // Block on the waiter lock until the main
+  // thread unblocks.
+  __llvm_libc::mtx_lock(&multiple_waiter_lock);
+  __llvm_libc::mtx_unlock(&multiple_waiter_lock);
+
+  __llvm_libc::mtx_lock(&counter_lock);
+  --wait_count;
+  __llvm_libc::mtx_unlock(&counter_lock);
+
+  return 0;
+}
+
+TEST(MutexTest, MultipleWaiters) {
+  __llvm_libc::mtx_init(&multiple_waiter_lock, mtx_plain);
+  __llvm_libc::mtx_init(&counter_lock, mtx_plain);
+
+  __llvm_libc::mtx_lock(&multiple_waiter_lock);
+  thrd_t waiters[THREAD_COUNT];
+  for (int i = 0; i < THREAD_COUNT; ++i) {
+    __llvm_libc::thrd_create(waiters + i, waiter_func, nullptr);
+  }
+
+  // Spin until the counter is incremented to the desired
+  // value.
+  while (true) {
+    __llvm_libc::mtx_lock(&counter_lock);
+    if (wait_count == THREAD_COUNT) {
+      __llvm_libc::mtx_unlock(&counter_lock);
+      break;
+    }
+    __llvm_libc::mtx_unlock(&counter_lock);
+  }
+
+  __llvm_libc::mtx_unlock(&multiple_waiter_lock);
+
+  int retval;
+  for (int i = 0; i < THREAD_COUNT; ++i) {
+    __llvm_libc::thrd_join(waiters + i, &retval);
+  }
+
+  ASSERT_EQ(wait_count, 0);
+}