1#include "sync/tests/test_internal.h"
2
3union collision_lock {
4 struct mutex lock;
5 uint8_t stride[TURNSTILE_HASH_SIZE * 8];
6};
7
8static union collision_lock collision_locks[2];
9
10static_assert(sizeof(union collision_lock) == TURNSTILE_HASH_SIZE * 8,
11 "collision fixture must preserve the hash stride");
12
13static void collision_waiter(void *arg) {
14 struct mutex *lock = arg;
15 mutex_lock(lock);
16 mutex_unlock(lock);
17}
18
19TEST_DEFINE_INTEGRATION(turnstile, lookup_collision_miss) {
20 struct mutex *occupied = &collision_locks[0].lock;
21 struct mutex *missing = &collision_locks[1].lock;
22 TEST_ASSERT_EQ(TURNSTILE_OBJECT_HASH(occupied),
23 TURNSTILE_OBJECT_HASH(missing));
24 mutex_init(occupied);
25 mutex_init(missing);
26
27 mutex_lock(occupied);
28 struct thread *waiter = thread_spawn("ts_collision", collision_waiter,
29 .arg = occupied, .joinable = true);
30 if (!waiter) {
31 mutex_unlock(occupied);
32 return TEST_FAIL("cannot create collision waiter");
33 }
34
35 time_ms_t deadline = time_get_ms() + 1000;
36 while (!atomic_load(&waiter->blocked_ts) && time_get_ms() < deadline)
37 thread_sleep_for_ms(ms: 1);
38
39 struct turnstile *found;
40 enum irql irql = turnstile_lookup(obj: occupied, out_ts: &found);
41 bool blocked = found && found->lock_obj == occupied && found->waiters == 1;
42 size_t occupied_count = turnstile_get_waiter_count(lock_obj: occupied);
43 size_t missing_count = turnstile_get_waiter_count(lock_obj: missing);
44 turnstile_unlock(obj: occupied, irql);
45
46 struct turnstile *miss;
47 irql = turnstile_lookup(obj: missing, out_ts: &miss);
48 bool missed = miss == NULL;
49 turnstile_unlock(obj: missing, irql);
50
51 mutex_unlock(occupied);
52 thread_join(t: waiter);
53
54 TEST_ASSERT(blocked);
55 TEST_ASSERT_EQ(occupied_count, 1);
56 TEST_ASSERT_MSG(missed, "lookup returned another lock's turnstile");
57 TEST_ASSERT_EQ(missing_count, 0);
58 return TEST_SUCCESS;
59}
60
61TEST_DEFINE_INTEGRATION(turnstile, lookup_collision_chain) {
62 struct thread *waiters[2];
63 bool blocked[2] = {false, false};
64 bool found[2] = {false, false};
65 bool joined[2];
66
67 TEST_ASSERT_EQ(TURNSTILE_OBJECT_HASH(&collision_locks[0].lock),
68 TURNSTILE_OBJECT_HASH(&collision_locks[1].lock));
69
70 struct mutex *lock0 = &collision_locks[0].lock;
71 struct mutex *lock1 = &collision_locks[1].lock;
72 mutex_init(lock0);
73 mutex_init(lock1);
74
75 mutex_lock_subclass(lock0, 0);
76 waiters[0] = thread_spawn("ts_chain", collision_waiter, .arg = lock0,
77 .joinable = true);
78
79 time_ms_t deadline = time_get_ms() + 1000;
80 while (!atomic_load(&waiters[0]->blocked_ts) && time_get_ms() < deadline)
81 thread_sleep_for_ms(ms: 1);
82 blocked[0] = atomic_load(&waiters[0]->blocked_ts) != NULL;
83
84 mutex_lock_subclass(lock1, 1);
85 waiters[1] = thread_spawn("ts_chain", collision_waiter, .arg = lock1,
86 .joinable = true);
87
88 deadline = time_get_ms() + 1000;
89 while (!atomic_load(&waiters[1]->blocked_ts) && time_get_ms() < deadline)
90 thread_sleep_for_ms(ms: 1);
91 blocked[1] = atomic_load(&waiters[1]->blocked_ts) != NULL;
92
93 for (size_t i = 0; i < 2; i++) {
94 struct mutex *lock = &collision_locks[i].lock;
95 struct turnstile *ts;
96 enum irql irql = turnstile_lookup(obj: lock, out_ts: &ts);
97 found[i] = ts && ts->lock_obj == lock && ts->waiters == 1;
98 turnstile_unlock(obj: lock, irql);
99 }
100
101 mutex_unlock(lock1);
102 mutex_unlock(lock0);
103
104 TEST_ASSERT_NONNULL(waiters[0]);
105 TEST_ASSERT_NONNULL(waiters[1]);
106
107 for (size_t i = 0; i < 2; i++) {
108 joined[i] = thread_join_timeout(t: waiters[i], timeout_ms: 1000, NULL);
109 if (!joined[i])
110 thread_detach(t: waiters[i]);
111 }
112
113 TEST_ASSERT(blocked[0] && blocked[1]);
114 TEST_ASSERT_MSG(found[0] && found[1],
115 "inserting a colliding lock lost an existing turnstile");
116 TEST_ASSERT(joined[0] && joined[1]);
117 return TEST_SUCCESS;
118}
119