559 lines · c
1//===--- Implementation of a Linux RwLock class ---------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8#ifndef LLVM_LIBC_SRC_SUPPORT_THREADS_LINUX_RWLOCK_H9#define LLVM_LIBC_SRC_SUPPORT_THREADS_LINUX_RWLOCK_H10 11#include "hdr/errno_macros.h"12#include "hdr/types/pid_t.h"13#include "src/__support/CPP/atomic.h"14#include "src/__support/CPP/limits.h"15#include "src/__support/CPP/optional.h"16#include "src/__support/OSUtil/syscall.h"17#include "src/__support/common.h"18#include "src/__support/libc_assert.h"19#include "src/__support/macros/attributes.h"20#include "src/__support/macros/config.h"21#include "src/__support/macros/optimization.h"22#include "src/__support/threads/identifier.h"23#include "src/__support/threads/linux/futex_utils.h"24#include "src/__support/threads/linux/futex_word.h"25#include "src/__support/threads/linux/raw_mutex.h"26#include "src/__support/threads/sleep.h"27 28#ifndef LIBC_COPT_RWLOCK_DEFAULT_SPIN_COUNT29#define LIBC_COPT_RWLOCK_DEFAULT_SPIN_COUNT 10030#endif31 32#ifndef LIBC_COPT_TIMEOUT_ENSURE_MONOTONICITY33#define LIBC_COPT_TIMEOUT_ENSURE_MONOTONICITY 134#warning "LIBC_COPT_TIMEOUT_ENSURE_MONOTONICITY is not defined, defaulting to 1"35#endif36 37#if LIBC_COPT_TIMEOUT_ENSURE_MONOTONICITY38#include "src/__support/time/linux/monotonicity.h"39#endif40 41namespace LIBC_NAMESPACE_DECL {42// Forward declaration of the RwLock class.43class RwLock;44// A namespace to rwlock specific utilities.45namespace rwlock {46// The role of the thread in the RwLock.47enum class Role { Reader = 0, Writer = 1 };48 49// A waiting queue to keep track of the pending readers and writers.50class WaitingQueue final : private RawMutex {51 /* FutexWordType raw_mutex; (from base class) */52 53 // Pending reader count (protected by the mutex)54 FutexWordType pending_readers;55 // Pending writer count (protected by the mutex)56 FutexWordType pending_writers;57 // Reader serialization (increases on each reader-waking operation)58 Futex reader_serialization;59 // Writer serialization (increases on each writer-waking operation)60 Futex writer_serialization;61 62public:63 // RAII guard to lock and unlock the waiting queue.64 class Guard {65 WaitingQueue &queue;66 bool is_pshared;67 68 LIBC_INLINE Guard(WaitingQueue &queue, bool is_pshared)69 : queue(queue), is_pshared(is_pshared) {70 queue.lock(cpp::nullopt, is_pshared);71 }72 73 public:74 LIBC_INLINE ~Guard() { queue.unlock(is_pshared); }75 template <Role role> LIBC_INLINE FutexWordType &pending_count() {76 if constexpr (role == Role::Reader)77 return queue.pending_readers;78 else79 return queue.pending_writers;80 }81 template <Role role> LIBC_INLINE FutexWordType &serialization() {82 if constexpr (role == Role::Reader)83 return queue.reader_serialization.val;84 else85 return queue.writer_serialization.val;86 }87 friend WaitingQueue;88 };89 90public:91 LIBC_INLINE constexpr WaitingQueue()92 : RawMutex(), pending_readers(0), pending_writers(0),93 reader_serialization(0), writer_serialization(0) {}94 95 LIBC_INLINE Guard acquire(bool is_pshared) {96 return Guard(*this, is_pshared);97 }98 99 template <Role role>100 LIBC_INLINE long wait(FutexWordType expected,101 cpp::optional<Futex::Timeout> timeout,102 bool is_pshared) {103 if constexpr (role == Role::Reader)104 return reader_serialization.wait(expected, timeout, is_pshared);105 else106 return writer_serialization.wait(expected, timeout, is_pshared);107 }108 109 template <Role role> LIBC_INLINE long notify(bool is_pshared) {110 if constexpr (role == Role::Reader)111 return reader_serialization.notify_all(is_pshared);112 else113 return writer_serialization.notify_one(is_pshared);114 }115};116 117// The RwState of the RwLock is stored in an integer word, consisting of the118// following components:119// -----------------------------------------------120// | Range | Description |121// ===============================================122// | 0 | Pending Reader Bit |123// -----------------------------------------------124// | 1 | Pending Writer Bit |125// -----------------------------------------------126// | [2, MSB) | Active Reader Count |127// -----------------------------------------------128// | MSB | Active Writer Bit |129// -----------------------------------------------130class RwState {131 // Shift amounts to access the components of the state.132 LIBC_INLINE_VAR static constexpr int PENDING_READER_SHIFT = 0;133 LIBC_INLINE_VAR static constexpr int PENDING_WRITER_SHIFT = 1;134 LIBC_INLINE_VAR static constexpr int ACTIVE_READER_SHIFT = 2;135 LIBC_INLINE_VAR static constexpr int ACTIVE_WRITER_SHIFT =136 cpp::numeric_limits<int>::digits;137 138 // Bitmasks to access the components of the state.139 LIBC_INLINE_VAR static constexpr int PENDING_READER_BIT =140 1 << PENDING_READER_SHIFT;141 LIBC_INLINE_VAR static constexpr int PENDING_WRITER_BIT =142 1 << PENDING_WRITER_SHIFT;143 LIBC_INLINE_VAR static constexpr int ACTIVE_READER_COUNT_UNIT =144 1 << ACTIVE_READER_SHIFT;145 LIBC_INLINE_VAR static constexpr int ACTIVE_WRITER_BIT =146 1 << ACTIVE_WRITER_SHIFT;147 LIBC_INLINE_VAR static constexpr int PENDING_MASK =148 PENDING_READER_BIT | PENDING_WRITER_BIT;149 150private:151 // We use the signed integer as the state type. It is easier152 // to reason about the state transitions using signness.153 int state;154 155public:156 // Construction and conversion functions.157 LIBC_INLINE constexpr RwState(int state = 0) : state(state) {}158 LIBC_INLINE constexpr operator int() const { return state; }159 160 // Utilities to check the state of the RwLock.161 LIBC_INLINE constexpr bool has_active_writer() const { return state < 0; }162 LIBC_INLINE constexpr bool has_active_reader() const {163 return state >= ACTIVE_READER_COUNT_UNIT;164 }165 LIBC_INLINE constexpr bool has_active_owner() const {166 return has_active_reader() || has_active_writer();167 }168 LIBC_INLINE constexpr bool has_last_reader() const {169 return (state >> ACTIVE_READER_SHIFT) == 1;170 }171 LIBC_INLINE constexpr bool has_pending_writer() const {172 return state & PENDING_WRITER_BIT;173 }174 LIBC_INLINE constexpr bool has_pending() const {175 return state & PENDING_MASK;176 }177 178 LIBC_INLINE constexpr RwState set_writer_bit() const {179 return RwState(state | ACTIVE_WRITER_BIT);180 }181 182 // The preference parameter changes the behavior of the lock acquisition183 // if there are both readers and writers waiting for the lock. If writers184 // are preferred, reader acquisition will be blocked until all pending185 // writers are served.186 template <Role role> LIBC_INLINE bool can_acquire(Role preference) const {187 if constexpr (role == Role::Reader) {188 switch (preference) {189 case Role::Reader:190 return !has_active_writer();191 case Role::Writer:192 return !has_active_writer() && !has_pending_writer();193 }194 __builtin_unreachable();195 } else196 return !has_active_owner();197 }198 199 // This function check if it is possible to grow the reader count without200 // overflowing the state.201 LIBC_INLINE cpp::optional<RwState> try_increase_reader_count() const {202 LIBC_ASSERT(!has_active_writer() &&203 "try_increase_reader_count shall only be called when there "204 "is no active writer.");205 RwState res;206 if (LIBC_UNLIKELY(__builtin_sadd_overflow(state, ACTIVE_READER_COUNT_UNIT,207 &res.state)))208 return cpp::nullopt;209 return res;210 }211 212 // Utilities to do atomic operations on the state.213 LIBC_INLINE static RwState fetch_sub_reader_count(cpp::Atomic<int> &target,214 cpp::MemoryOrder order) {215 return RwState(target.fetch_sub(ACTIVE_READER_COUNT_UNIT, order));216 }217 218 LIBC_INLINE static RwState load(cpp::Atomic<int> &target,219 cpp::MemoryOrder order) {220 return RwState(target.load(order));221 }222 223 template <Role role>224 LIBC_INLINE static RwState fetch_set_pending_bit(cpp::Atomic<int> &target,225 cpp::MemoryOrder order) {226 if constexpr (role == Role::Reader)227 return RwState(target.fetch_or(PENDING_READER_BIT, order));228 else229 return RwState(target.fetch_or(PENDING_WRITER_BIT, order));230 }231 template <Role role>232 LIBC_INLINE static RwState fetch_clear_pending_bit(cpp::Atomic<int> &target,233 cpp::MemoryOrder order) {234 if constexpr (role == Role::Reader)235 return RwState(target.fetch_and(~PENDING_READER_BIT, order));236 else237 return RwState(target.fetch_and(~PENDING_WRITER_BIT, order));238 }239 240 LIBC_INLINE static RwState fetch_clear_active_writer(cpp::Atomic<int> &target,241 cpp::MemoryOrder order) {242 return RwState(target.fetch_and(~ACTIVE_WRITER_BIT, order));243 }244 245 LIBC_INLINE bool compare_exchange_weak_with(cpp::Atomic<int> &target,246 RwState desired,247 cpp::MemoryOrder success_order,248 cpp::MemoryOrder failure_order) {249 return target.compare_exchange_weak(state, desired, success_order,250 failure_order);251 }252 253 // Utilities to spin and reload the state.254private:255 template <class F>256 LIBC_INLINE static RwState spin_reload_until(cpp::Atomic<int> &target,257 F &&func, unsigned spin_count) {258 for (;;) {259 auto state = RwState::load(target, cpp::MemoryOrder::RELAXED);260 if (func(state) || spin_count == 0)261 return state;262 sleep_briefly();263 spin_count--;264 }265 }266 267public:268 template <Role role>269 LIBC_INLINE static RwState spin_reload(cpp::Atomic<int> &target,270 Role preference, unsigned spin_count) {271 if constexpr (role == Role::Reader) {272 // Return the reader state if either the lock is available or there is273 // any ongoing contention.274 return spin_reload_until(275 target,276 [=](RwState state) {277 return state.can_acquire<Role::Reader>(preference) ||278 state.has_pending();279 },280 spin_count);281 } else {282 // Return the writer state if either the lock is available or there is283 // any contention *between writers*. Since writers can be way less than284 // readers, we allow them to spin more to improve the fairness.285 return spin_reload_until(286 target,287 [=](RwState state) {288 return state.can_acquire<Role::Writer>(preference) ||289 state.has_pending_writer();290 },291 spin_count);292 }293 }294 295 friend class RwLockTester;296};297} // namespace rwlock298 299class RwLock {300 using RwState = rwlock::RwState;301 using Role = rwlock::Role;302 using WaitingQueue = rwlock::WaitingQueue;303 304public:305 // Return types for the lock functions.306 // All the locking routines returning this type are marked as [[nodiscard]]307 // because it is a common error to assume the lock success without checking308 // the return value, which can lead to undefined behaviors or other subtle309 // bugs that are hard to reason about.310 enum class LockResult : int {311 Success = 0,312 TimedOut = ETIMEDOUT,313 Overflow = EAGAIN, /* EAGAIN is specified in the standard for overflow. */314 Busy = EBUSY,315 Deadlock = EDEADLOCK,316 PermissionDenied = EPERM,317 };318 319private:320 // Whether the RwLock is shared between processes.321 LIBC_PREFERED_TYPE(bool)322 unsigned is_pshared : 1;323 // Reader/Writer preference.324 LIBC_PREFERED_TYPE(Role)325 unsigned preference : 1;326 // RwState to keep track of the RwLock.327 cpp::Atomic<int> state;328 // writer_tid is used to keep track of the thread id of the writer. Notice329 // that TLS address is not a good idea here since it may remains the same330 // across forked processes.331 cpp::Atomic<pid_t> writer_tid;332 // Waiting queue to keep track of the readers and writers.333 WaitingQueue queue;334 335private:336 // Load the bitfield preference.337 LIBC_INLINE Role get_preference() const {338 return static_cast<Role>(preference);339 }340 341 template <Role role> LIBC_INLINE LockResult try_lock(RwState &old) {342 if constexpr (role == Role::Reader) {343 while (LIBC_LIKELY(old.can_acquire<Role::Reader>(get_preference()))) {344 cpp::optional<RwState> next = old.try_increase_reader_count();345 if (!next)346 return LockResult::Overflow;347 if (LIBC_LIKELY(old.compare_exchange_weak_with(348 state, *next, cpp::MemoryOrder::ACQUIRE,349 cpp::MemoryOrder::RELAXED)))350 return LockResult::Success;351 // Notice that old is updated by the compare_exchange_weak_with352 // function.353 }354 return LockResult::Busy;355 } else {356 // This while loop should terminate quickly357 while (LIBC_LIKELY(old.can_acquire<Role::Writer>(get_preference()))) {358 if (LIBC_LIKELY(old.compare_exchange_weak_with(359 state, old.set_writer_bit(), cpp::MemoryOrder::ACQUIRE,360 cpp::MemoryOrder::RELAXED))) {361 writer_tid.store(internal::gettid(), cpp::MemoryOrder::RELAXED);362 return LockResult::Success;363 }364 // Notice that old is updated by the compare_exchange_weak_with365 // function.366 }367 return LockResult::Busy;368 }369 }370 371public:372 LIBC_INLINE constexpr RwLock(Role preference = Role::Reader,373 bool is_pshared = false)374 : is_pshared(is_pshared),375 preference(static_cast<unsigned>(preference) & 1u), state(0),376 writer_tid(0), queue() {}377 378 [[nodiscard]]379 LIBC_INLINE LockResult try_read_lock() {380 RwState old = RwState::load(state, cpp::MemoryOrder::RELAXED);381 return try_lock<Role::Reader>(old);382 }383 [[nodiscard]]384 LIBC_INLINE LockResult try_write_lock() {385 RwState old = RwState::load(state, cpp::MemoryOrder::RELAXED);386 return try_lock<Role::Writer>(old);387 }388 389private:390 template <Role role>391 LIBC_INLINE LockResult392 lock_slow(cpp::optional<Futex::Timeout> timeout = cpp::nullopt,393 unsigned spin_count = LIBC_COPT_RWLOCK_DEFAULT_SPIN_COUNT) {394 // Phase 1: deadlock detection.395 // A deadlock happens if this is a RAW/WAW lock in the same thread.396 if (writer_tid.load(cpp::MemoryOrder::RELAXED) == internal::gettid())397 return LockResult::Deadlock;398 399#if LIBC_COPT_TIMEOUT_ENSURE_MONOTONICITY400 // Phase 2: convert the timeout if necessary.401 if (timeout)402 ensure_monotonicity(*timeout);403#endif404 405 // Phase 3: spin to get the initial state. We ignore the timing due to406 // spin since it should end quickly.407 RwState old =408 RwState::spin_reload<role>(state, get_preference(), spin_count);409 410 // Enter the main acquisition loop.411 for (;;) {412 // Phase 4: if the lock can be acquired, try to acquire it.413 LockResult result = try_lock<role>(old);414 if (result != LockResult::Busy)415 return result;416 417 // Phase 5: register ourselves as a reader.418 int serial_number;419 {420 // The queue need to be protected by a mutex since the operations in421 // this block must be executed as a whole transaction. It is possible422 // that this lock will make the timeout imprecise, but this is the423 // best we can do. The transaction is small and everyone should make424 // progress rather quickly.425 WaitingQueue::Guard guard = queue.acquire(is_pshared);426 guard.template pending_count<role>()++;427 428 // Use atomic operation to guarantee the total order of the operations429 // on the state. The pending flag update should be visible to any430 // succeeding unlock events. Or, if a unlock does happen before we431 // sleep on the futex, we can avoid such waiting.432 old = RwState::fetch_set_pending_bit<role>(state,433 cpp::MemoryOrder::RELAXED);434 // no need to use atomic since it is already protected by the mutex.435 serial_number = guard.serialization<role>();436 }437 438 // Phase 6: do futex wait until the lock is available or timeout is439 // reached.440 bool timeout_flag = false;441 if (!old.can_acquire<role>(get_preference()))442 timeout_flag = (queue.wait<role>(serial_number, timeout, is_pshared) ==443 -ETIMEDOUT);444 445 // Phase 7: unregister ourselves as a pending reader/writer.446 {447 // Similarly, the unregister operation should also be an atomic448 // transaction.449 WaitingQueue::Guard guard = queue.acquire(is_pshared);450 guard.pending_count<role>()--;451 // Clear the flag if we are the last reader. The flag must be452 // cleared otherwise operations like trylock may fail even though453 // there is no competitors.454 if (guard.pending_count<role>() == 0)455 RwState::fetch_clear_pending_bit<role>(state,456 cpp::MemoryOrder::RELAXED);457 }458 459 // Phase 8: exit the loop is timeout is reached.460 if (timeout_flag)461 return LockResult::TimedOut;462 463 // Phase 9: reload the state and retry the acquisition.464 old = RwState::spin_reload<role>(state, get_preference(), spin_count);465 }466 }467 468public:469 [[nodiscard]]470 LIBC_INLINE LockResult471 read_lock(cpp::optional<Futex::Timeout> timeout = cpp::nullopt,472 unsigned spin_count = LIBC_COPT_RWLOCK_DEFAULT_SPIN_COUNT) {473 LockResult result = try_read_lock();474 if (LIBC_LIKELY(result != LockResult::Busy))475 return result;476 return lock_slow<Role::Reader>(timeout, spin_count);477 }478 [[nodiscard]]479 LIBC_INLINE LockResult480 write_lock(cpp::optional<Futex::Timeout> timeout = cpp::nullopt,481 unsigned spin_count = LIBC_COPT_RWLOCK_DEFAULT_SPIN_COUNT) {482 LockResult result = try_write_lock();483 if (LIBC_LIKELY(result != LockResult::Busy))484 return result;485 return lock_slow<Role::Writer>(timeout, spin_count);486 }487 488private:489 // Compiler (clang 19.0) somehow decides that this function may be inlined,490 // which leads to a larger unlock function that is infeasible to be inlined.491 // Since notifcation routine is colder we mark it as noinline explicitly.492 [[gnu::noinline]]493 LIBC_INLINE void notify_pending_threads() {494 enum class WakeTarget { Readers, Writers, None };495 WakeTarget status;496 497 {498 WaitingQueue::Guard guard = queue.acquire(is_pshared);499 if (guard.pending_count<Role::Writer>() != 0) {500 guard.serialization<Role::Writer>()++;501 status = WakeTarget::Writers;502 } else if (guard.pending_count<Role::Reader>() != 0) {503 guard.serialization<Role::Reader>()++;504 status = WakeTarget::Readers;505 } else506 status = WakeTarget::None;507 }508 509 if (status == WakeTarget::Readers)510 queue.notify<Role::Reader>(is_pshared);511 else if (status == WakeTarget::Writers)512 queue.notify<Role::Writer>(is_pshared);513 }514 515public:516 [[nodiscard]]517 LIBC_INLINE LockResult unlock() {518 RwState old = RwState::load(state, cpp::MemoryOrder::RELAXED);519 if (old.has_active_writer()) {520 // The lock is held by a writer.521 // Check if we are the owner of the lock.522 if (writer_tid.load(cpp::MemoryOrder::RELAXED) != internal::gettid())523 return LockResult::PermissionDenied;524 // clear writer tid.525 writer_tid.store(0, cpp::MemoryOrder::RELAXED);526 // clear the writer bit.527 old =528 RwState::fetch_clear_active_writer(state, cpp::MemoryOrder::RELEASE);529 // If there is no pending readers or writers, we are done.530 if (!old.has_pending())531 return LockResult::Success;532 } else if (old.has_active_reader()) {533 // The lock is held by readers.534 // Decrease the reader count.535 old = RwState::fetch_sub_reader_count(state, cpp::MemoryOrder::RELEASE);536 // If there is no pending readers or writers, we are done.537 if (!old.has_last_reader() || !old.has_pending())538 return LockResult::Success;539 } else540 return LockResult::PermissionDenied;541 542 notify_pending_threads();543 return LockResult::Success;544 }545 546 // We do not allocate any special resources for the RwLock, so this function547 // will only check if the lock is currently held by any thread.548 [[nodiscard]]549 LIBC_INLINE LockResult check_for_destroy() {550 RwState old = RwState::load(state, cpp::MemoryOrder::RELAXED);551 if (old.has_active_owner())552 return LockResult::Busy;553 return LockResult::Success;554 }555};556} // namespace LIBC_NAMESPACE_DECL557 558#endif // LLVM_LIBC_SRC_SUPPORT_THREADS_LINUX_RWLOCK_H559