1#include <stdbool.h>
2#include <sync/rwlock.h>
3
4struct thread; /* forward def */
5
6enum rwlock_bits : uintptr_t {
7 RWLOCK_WRITER_HELD_BIT = 1ULL << 0,
8 RWLOCK_WAITER_BIT = 1ULL << 3ULL,
9 RWLOCK_WRITER_WANT_BIT = 1ULL << 4ULL,
10};
11
12#define RWLOCK_BACKOFF_DEFAULT 8
13#define RWLOCK_BACKOFF_MAX 16384
14#define RWLOCK_BACKOFF_SHIFT 1
15#define RWLOCK_BACKOFF_JITTER_PCT 10 /* 10% variation of base backoff */
16
17#define RWLOCK_PRIO_CEIL_MASK (0x6)
18#define RWLOCK_GET_PRIO_CEIL(lword) \
19 (((lword) & RWLOCK_PRIO_CEIL_MASK) >> RWLOCK_PRIO_CEIL_SHIFT)
20#define RWLOCK_READER_COUNT_MASK (~0ULL << 5)
21#define RWLOCK_OWNER_MASK (~0x1FULL)
22#define RWLOCK_READER_COUNT_ONE (1 << 5)
23
24#define RWLOCK_READ_LOCK_WORD(rw) \
25 (atomic_load_explicit(&rw->lock_word, memory_order_acquire))
26#define RWLOCK_WRITE_LOCK_WORD(rw, w) \
27 atomic_store_explicit(&rw->lock_word, w, memory_order_release)
28
29#define RWLOCK_GET_OWNER(rw) \
30 (RWLOCK_READ_LOCK_WORD(rw) & RWLOCK_OWNER_MASK) /* mask out metadata */
31#define RWLOCK_GET_OWNER_FROM_WORD(word) ((word) & RWLOCK_OWNER_MASK)
32#define RWLOCK_BUSY(lock_word, mask) (((lock_word) & (mask)))
33
34static inline uintptr_t rwlock_make_write_word(struct rwlock *lock,
35 struct thread *thread) {
36 return (uintptr_t) (RWLOCK_READ_LOCK_WORD(lock) & RWLOCK_PRIO_CEIL_MASK) |
37 (uintptr_t) RWLOCK_WRITER_HELD_BIT | (uintptr_t) thread;
38}
39
40static inline bool rwlock_try_lock_read(struct rwlock *lock) {
41 uintptr_t old_state = RWLOCK_READ_LOCK_WORD(lock);
42 while (true) {
43 if (old_state & (RWLOCK_WRITER_HELD_BIT | RWLOCK_WRITER_WANT_BIT))
44 return false;
45
46 uintptr_t new_state = old_state + RWLOCK_READER_COUNT_ONE;
47
48 if (atomic_compare_exchange_weak_explicit(
49 &lock->lock_word, &old_state, new_state, memory_order_acquire,
50 memory_order_relaxed))
51 return true;
52 }
53}
54
55static inline bool rwlock_try_lock_write(struct rwlock *lock,
56 struct thread *thread) {
57 uintptr_t desired = rwlock_make_write_word(lock, thread);
58 uintptr_t old =
59 atomic_load_explicit(&lock->lock_word, memory_order_acquire);
60
61 while (true) {
62 /* If there's a writer held or any readers, we cannot acquire now */
63 if (old & (RWLOCK_WRITER_HELD_BIT | RWLOCK_READER_COUNT_MASK))
64 return false;
65
66 /* No owner - try to become the writer. This will replace any
67 * WANT/WAITER bits that were present with the writer word. */
68
69 if (atomic_compare_exchange_weak_explicit(&lock->lock_word, &old,
70 desired, memory_order_acquire,
71 memory_order_relaxed))
72 return true;
73
74 /* CAS failed: reload old and loop - but if the new old indicates busy,
75 * bail out quickly to avoid wasting cycles. */
76 if (old & (RWLOCK_WRITER_HELD_BIT | RWLOCK_READER_COUNT_MASK))
77 return false;
78
79 /* otherwise retry (someone cleared the wait bits or raced us) */
80 }
81}
82
83static inline bool rwlock_try_lock(struct rwlock *lock, struct thread *thread,
84 enum rwlock_acquire_type type) {
85 if (type == RWLOCK_ACQUIRE_READ)
86 return rwlock_try_lock_read(lock);
87
88 return rwlock_try_lock_write(lock, thread);
89}
90