Skip to main content

uqa_execution/row_locks/
waits.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Row-lock waits, cross-process claims, and deadlock detection.
8
9use super::{
10    lock_strengths_conflict, remove_inactive_versions, rollback_grant, row_byte_claims, try_grant,
11    ByteClaim, CrossAttachment, FileLockCoordinator, GrantAttempt, HashSet, LockAcquire,
12    LockRequest, LockStrength, LockTable, MutexGuard, RelationLockMode, RowLockAcquisition,
13    RowLockKey, RowLockManager, SQLError, WAIT_SLICE,
14};
15
16impl RowLockManager {
17    /// Release the cross-process claims of `rows` in one coordinator release, which clears their holder slots under one slot metadata lock.
18    pub(super) fn release_row_claims(&self, session_id: u64, rows: &[(RowLockKey, LockStrength)]) {
19        if let Some(CrossAttachment::Active(coordinator)) = self.cross.as_ref() {
20            let mut claims = Vec::with_capacity(rows.len() * 2);
21            for (key, strength) in rows {
22                let relation = self.relation_bytes(key.table);
23                if let Some(identity) = coordinator.retained_row_identity(&relation, key.doc_id) {
24                    claims.extend(row_byte_claims(identity, *strength));
25                }
26            }
27            coordinator.release(session_id, &claims);
28            for (key, _) in rows {
29                coordinator.release_row_identity(&self.relation_bytes(key.table));
30            }
31        }
32    }
33
34    /// Whether the cross-process wait-for graph from `wanted` closes back on `session_id`. Bytes held by other local sessions are followed through those sessions' own foreign waits.
35    pub(super) fn cross_wait_cycle(
36        state: &LockTable,
37        coordinator: &FileLockCoordinator,
38        session_id: u64,
39        wanted: ByteClaim,
40    ) -> bool {
41        let local_wait = |session: u64| state.advertised_waits.get(&session).copied();
42        coordinator.wait_cycle_reaches_session(session_id, wanted, &local_wait)
43    }
44
45    fn finish_row_wait(&self, mut state: MutexGuard<'_, LockTable>, session_id: u64) {
46        state.waiting.remove(&session_id);
47        state.advertised_waits.remove(&session_id);
48        remove_inactive_versions(&mut state);
49        drop(state);
50        self.wake.notify_all();
51    }
52
53    pub fn acquire(&self, request: &LockRequest<'_>) -> Result<LockAcquire, SQLError> {
54        let coordinator = self.coordinator()?;
55        let retained = self.identities.retain(request.key.table);
56        let relation = self.relation_bytes(request.key.table);
57        let mut identity = coordinator
58            .map(|coordinator| coordinator.pin_row(&relation, request.key.doc_id, request.cancel))
59            .transpose()?;
60        let claims = identity
61            .as_ref()
62            .map(|identity| row_byte_claims(identity.identity(), request.strength))
63            .unwrap_or_default();
64        let cross_wait = CrossWaitGuard::new(self, coordinator, request.session_id);
65        let mut waited = false;
66        let mut foreign_waited = false;
67        let mut wait_started = None;
68        loop {
69            let mut state = self.state.lock();
70            let checked = wait_started.map_or_else(
71                || request.cancel.check(),
72                |started| request.cancel.check_lock_wait(started),
73            );
74            if let Err(error) = checked {
75                self.finish_row_wait(state, request.session_id);
76                return Err(error.into());
77            }
78            let attempt = try_grant(
79                &mut state,
80                request,
81                &self.next_acquisition,
82                retained.as_ref(),
83            );
84            let contended_claim = match attempt {
85                GrantAttempt::Granted(acquisition) => {
86                    match claim_cross_process_bytes(&mut state, coordinator, &claims, acquisition) {
87                        Ok(None) => {
88                            state.waiting.remove(&request.session_id);
89                            remove_inactive_versions(&mut state);
90                            if acquisition.is_some() {
91                                if let Some(identity) = &mut identity {
92                                    identity.retain();
93                                }
94                            }
95                            return Ok(LockAcquire::Granted {
96                                waited,
97                                foreign_waited,
98                                acquisition,
99                            });
100                        }
101                        Ok(Some(contended)) => {
102                            foreign_waited = true;
103                            Some(contended)
104                        }
105                        Err(error) => {
106                            self.finish_row_wait(state, request.session_id);
107                            return Err(error);
108                        }
109                    }
110                }
111                GrantAttempt::Conflict => coordinator.and_then(|_| {
112                    locally_contended_row_claim(&state, request.session_id, request.key, &claims)
113                }),
114            };
115            match request.wait {
116                uqa_sql::ast::LockWait::SkipLocked => {
117                    self.finish_row_wait(state, request.session_id);
118                    return Ok(LockAcquire::Skipped);
119                }
120                uqa_sql::ast::LockWait::NoWait => {
121                    self.finish_row_wait(state, request.session_id);
122                    return Err(lock_unavailable(request.relation));
123                }
124                uqa_sql::ast::LockWait::Block => {
125                    if deadlock_exists(&state, request.session_id, request.key, request.strength) {
126                        self.finish_row_wait(state, request.session_id);
127                        return Err(deadlock_detected());
128                    }
129                    if let (Some(coordinator), Some(contended)) = (coordinator, contended_claim) {
130                        cross_wait.register(&mut state, contended);
131                        if Self::cross_wait_cycle(
132                            &state,
133                            coordinator,
134                            request.session_id,
135                            contended,
136                        ) {
137                            self.finish_row_wait(state, request.session_id);
138                            return Err(deadlock_detected());
139                        }
140                    }
141                    state
142                        .waiting
143                        .entry(request.session_id)
144                        .or_default()
145                        .insert(request.key, request.strength);
146                    waited = true;
147                    let started = *wait_started.get_or_insert_with(std::time::Instant::now);
148                    let slice = request.cancel.lock_wait_slice(started, WAIT_SLICE);
149                    self.wake.wait_for(&mut state, slice);
150                }
151            }
152        }
153    }
154}
155
156pub(super) fn deadlock_detected() -> SQLError {
157    SQLError::Routine {
158        sqlstate: "40P01".into(),
159        message: "deadlock detected".into(),
160    }
161}
162
163/// Advertises one session's cross-process wait for the duration of an acquisition and clears it on every exit path.
164pub(super) struct CrossWaitGuard<'a> {
165    manager: &'a RowLockManager,
166    coordinator: Option<&'a FileLockCoordinator>,
167    session_id: u64,
168    registered: std::cell::Cell<bool>,
169}
170
171impl<'a> CrossWaitGuard<'a> {
172    pub(super) fn new(
173        manager: &'a RowLockManager,
174        coordinator: Option<&'a FileLockCoordinator>,
175        session_id: u64,
176    ) -> Self {
177        Self {
178            manager,
179            coordinator,
180            session_id,
181            registered: std::cell::Cell::new(false),
182        }
183    }
184
185    pub(super) fn register(&self, state: &mut LockTable, claim: ByteClaim) {
186        if let Some(coordinator) = self.coordinator {
187            coordinator.register_wait(self.session_id, claim);
188            state.advertised_waits.insert(self.session_id, claim);
189            self.registered.set(true);
190        }
191    }
192
193    pub(super) fn clear(&self, state: &mut LockTable) {
194        if self.registered.replace(false) {
195            if let Some(coordinator) = self.coordinator {
196                coordinator.clear_wait(self.session_id);
197            }
198            state.advertised_waits.remove(&self.session_id);
199        }
200    }
201}
202
203impl Drop for CrossWaitGuard<'_> {
204    fn drop(&mut self) {
205        if self.registered.get() {
206            if let Some(coordinator) = self.coordinator {
207                coordinator.clear_wait(self.session_id);
208            }
209            self.manager
210                .state
211                .lock()
212                .advertised_waits
213                .remove(&self.session_id);
214        }
215    }
216}
217
218/// Add the cross-process record-lock claims for one just-granted row acquisition. Only a new acquisition adds claims: re-acquiring an equal-or-weaker strength changes nothing another process could observe. A contended claim rolls the in-process grant back and reports the byte to wait on; an infrastructure failure rolls back and surfaces the error.
219fn claim_cross_process_bytes(
220    state: &mut LockTable,
221    coordinator: Option<&FileLockCoordinator>,
222    claims: &[ByteClaim],
223    acquisition: Option<RowLockAcquisition>,
224) -> Result<Option<ByteClaim>, SQLError> {
225    let (Some(coordinator), Some(new_acquisition)) = (coordinator, acquisition) else {
226        return Ok(None);
227    };
228    match coordinator.try_claim(new_acquisition.session_id, claims) {
229        Ok(Ok(())) => Ok(None),
230        Ok(Err(contended)) => {
231            rollback_grant(state, new_acquisition);
232            Ok(Some(contended))
233        }
234        Err(error) => {
235            rollback_grant(state, new_acquisition);
236            Err(SQLError::Internal(error))
237        }
238    }
239}
240
241fn locally_contended_row_claim(
242    state: &LockTable,
243    session_id: u64,
244    key: RowLockKey,
245    wanted_claims: &[ByteClaim],
246) -> Option<ByteClaim> {
247    state.rows.get(&key)?.iter().find_map(|grant| {
248        if grant.session_id == session_id {
249            return None;
250        }
251        row_byte_claims(wanted_claims.first()?.row?, grant.effective_strength())
252            .into_iter()
253            .find_map(|held| {
254                wanted_claims
255                    .iter()
256                    .copied()
257                    .find(|wanted| byte_claims_conflict(*wanted, held))
258            })
259    })
260}
261
262fn byte_claims_conflict(wanted: ByteClaim, held: ByteClaim) -> bool {
263    wanted.row == held.row && wanted.offset == held.offset && (wanted.write || held.write)
264}
265
266pub(super) fn deadlock_exists(
267    state: &LockTable,
268    waiter: u64,
269    wanted: RowLockKey,
270    wanted_strength: LockStrength,
271) -> bool {
272    wait_cycle_reaches(
273        state,
274        waiter,
275        holders_of(state, wanted, waiter, wanted_strength),
276    )
277}
278
279pub(super) fn relation_deadlock_exists(
280    state: &LockTable,
281    waiter: u64,
282    table: u64,
283    mode: RelationLockMode,
284) -> bool {
285    wait_cycle_reaches(
286        state,
287        waiter,
288        relation_holders_of(state, table, waiter, mode),
289    )
290}
291
292fn wait_cycle_reaches(state: &LockTable, waiter: u64, mut stack: Vec<u64>) -> bool {
293    let mut seen = HashSet::from([waiter]);
294    while let Some(session) = stack.pop() {
295        if !seen.insert(session) {
296            continue;
297        }
298        if let Some(waiting_for) = state.waiting.get(&session) {
299            for (key, strength) in waiting_for {
300                for holder in holders_of(state, *key, session, *strength) {
301                    if holder == waiter {
302                        return true;
303                    }
304                    stack.push(holder);
305                }
306            }
307        }
308        if let Some(waiting_for) = state.waiting_relations.get(&session) {
309            for (table, mode) in waiting_for {
310                for holder in relation_holders_of(state, *table, session, *mode) {
311                    if holder == waiter {
312                        return true;
313                    }
314                    stack.push(holder);
315                }
316            }
317        }
318    }
319    false
320}
321
322fn relation_holders_of(
323    state: &LockTable,
324    table: u64,
325    except: u64,
326    wanted_mode: RelationLockMode,
327) -> Vec<u64> {
328    state
329        .relations
330        .get(&table)
331        .into_iter()
332        .flatten()
333        .filter(|grant| grant.session_id != except && grant.conflicting_mode(wanted_mode).is_some())
334        .map(|grant| grant.session_id)
335        .collect()
336}
337
338fn holders_of(
339    state: &LockTable,
340    key: RowLockKey,
341    except: u64,
342    wanted_strength: LockStrength,
343) -> Vec<u64> {
344    state
345        .rows
346        .get(&key)
347        .into_iter()
348        .flatten()
349        .filter(|grant| {
350            grant.session_id != except
351                && lock_strengths_conflict(grant.effective_strength(), wanted_strength)
352        })
353        .map(|grant| grant.session_id)
354        .collect()
355}
356
357pub fn lock_unavailable(relation: &str) -> SQLError {
358    SQLError::Routine {
359        sqlstate: "55P03".into(),
360        message: format!("could not obtain lock on row in relation \"{relation}\""),
361    }
362}