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