diff --git a/libc/config/linux/api.td b/libc/config/linux/api.td
--- a/libc/config/linux/api.td
+++ b/libc/config/linux/api.td
@@ -144,12 +144,22 @@
   ];
 }
 
+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,
   ];
 
@@ -165,6 +175,9 @@
   ];
 
   let Functions = [
+    "mtx_init",
+    "mtx_lock",
+    "mtx_unlock",
     "thrd_create",
     "thrd_join",
   ];
diff --git a/libc/lib/CMakeLists.txt b/libc/lib/CMakeLists.txt
--- a/libc/lib/CMakeLists.txt
+++ b/libc/lib/CMakeLists.txt
@@ -19,6 +19,9 @@
     # threads.h entrypoints
     thrd_create
     thrd_join
+    mtx_init
+    mtx_lock
+    mtx_unlock
 )
 
 add_entrypoint_library(
diff --git a/libc/src/threads/linux/CMakeLists.txt b/libc/src/threads/linux/CMakeLists.txt
--- a/libc/src/threads/linux/CMakeLists.txt
+++ b/libc/src/threads/linux/CMakeLists.txt
@@ -35,3 +35,44 @@
     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
+)
diff --git a/libc/src/threads/linux/mtx_init.cpp b/libc/src/threads/linux/mtx_init.cpp
new file mode 100644
--- /dev/null
+++ b/libc/src/threads/linux/mtx_init.cpp
@@ -0,0 +1,21 @@
+//===----------- 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
diff --git a/libc/src/threads/linux/mtx_lock.cpp b/libc/src/threads/linux/mtx_lock.cpp
new file mode 100644
--- /dev/null
+++ b/libc/src/threads/linux/mtx_lock.cpp
@@ -0,0 +1,62 @@
+//===----------- 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
diff --git a/libc/src/threads/linux/mtx_unlock.cpp b/libc/src/threads/linux/mtx_unlock.cpp
new file mode 100644
--- /dev/null
+++ b/libc/src/threads/linux/mtx_unlock.cpp
@@ -0,0 +1,44 @@
+//===---------- 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
diff --git a/libc/src/threads/linux/thread_utils.h b/libc/src/threads/linux/thread_utils.h
--- a/libc/src/threads/linux/thread_utils.h
+++ b/libc/src/threads/linux/thread_utils.h
@@ -11,6 +11,11 @@
 
 #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
diff --git a/libc/src/threads/mtx_init.h b/libc/src/threads/mtx_init.h
new file mode 100644
--- /dev/null
+++ b/libc/src/threads/mtx_init.h
@@ -0,0 +1,20 @@
+//===---------- 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
diff --git a/libc/src/threads/mtx_lock.h b/libc/src/threads/mtx_lock.h
new file mode 100644
--- /dev/null
+++ b/libc/src/threads/mtx_lock.h
@@ -0,0 +1,20 @@
+//===---------- 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
diff --git a/libc/src/threads/mtx_unlock.h b/libc/src/threads/mtx_unlock.h
new file mode 100644
--- /dev/null
+++ b/libc/src/threads/mtx_unlock.h
@@ -0,0 +1,20 @@
+//===-------- 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
diff --git a/libc/test/src/threads/linux/CMakeLists.txt b/libc/test/src/threads/linux/CMakeLists.txt
--- a/libc/test/src/threads/linux/CMakeLists.txt
+++ b/libc/test/src/threads/linux/CMakeLists.txt
@@ -14,3 +14,23 @@
     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)
diff --git a/libc/test/src/threads/linux/mtx_test.cpp b/libc/test/src/threads/linux/mtx_test.cpp
new file mode 100644
--- /dev/null
+++ b/libc/test/src/threads/linux/mtx_test.cpp
@@ -0,0 +1,116 @@
+//===---------------------- 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);
+}