starnix_sync/
lock_sequence.rs

1// Copyright 2023 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! Tools for describing and enforcing lock acquisition order.
6//!
7//! To use these tools:
8//! 1. A lock level must be defined for each type of lock. This can be a simple enum.
9//! 2. Then a relation `LockedAfter` between these levels must be described,
10//! forming a graph. This graph must be acyclic, since a cycle would indicate
11//! a potential deadlock.
12//! 3. Each time a lock is acquired, it must be done using an object of a `Locked<P>`
13//! type, where `P` is any lock level that comes before the level `L` that is
14//! associated with this lock. Doing so yields a new object of type `Locked<L>`
15//! that can be used to acquire subsequent locks.
16//! 3. Each place where a lock is used must be marked with the maximum lock level
17//! that can be already acquired before attempting to acquire this lock. To do this,
18//! it takes a special marker object `Locked<P>` where `P` is a lock level that
19//! must come before the level associated in this lock in the graph. This object
20//! is then used to acquire the lock, and a new object `Locked<L>` is returned, with
21//! a new lock level `L` that comes after `P` in the lock ordering graph.
22//!
23//! ## Example
24//! See also tests for this crate.
25//!
26//! ```
27//! use std::sync::Mutex;
28//! use starnix_sync::{lock_ordering, lock::LockFor, relation::LockAfter, Unlocked};
29//!
30//! #[derive(Default)]
31//! struct HoldsLocks {
32//!    a: Mutex<u8>,
33//!    b: Mutex<u32>,
34//! }
35//!
36//! lock_ordering! {
37//!    // LockA is the top of the lock hierarchy.
38//!    Unlocked => LevelA,
39//!    // LockA can be acquired before LockB.
40//!    LevelA => LevelB,
41//! }
42//!
43//! impl LockFor<LockA> for HoldsLocks {
44//!    type Data = u8;
45//!    type Guard<'l> = std::sync::MutexGuard<'l, u8>
46//!        where Self: 'l;
47//!    fn lock(&self) -> Self::Guard<'_> {
48//!        self.a.lock().unwrap()
49//!    }
50//! }
51//!
52//! impl LockFor<LockB> for HoldsLocks {
53//!    type Data = u32;
54//!    type Guard<'l> = std::sync::MutexGuard<'l, u32>
55//!        where Self: 'l;
56//!    fn lock(&self) -> Self::Guard<'_> {
57//!        self.b.lock().unwrap()
58//!    }
59//! }
60//!
61//! // Accessing locked state looks like this:
62//!
63//! let state = HoldsLocks::default();
64//! // Create a new lock session with the "root" lock level (empty tuple).
65//! let locked = Unlocked::new();
66//! // Access locked state.
67//! let (a, locked_a) = locked.lock_and::<LockA, _>(&state);
68//! let b = locked_a.lock::<LockB, _>(&state);
69//! ```
70//!
71//! The [lock_ordering] macro provides definitions for lock levels and
72//! implementations of [LockAfter] for all the locks that are connected
73//! in the graph (one can be locked after another). It also prevents
74//! accidental lock ordering inversion introduced while defining the graph
75//! by detecting cycles in it.
76//!
77//! This won't compile:
78//! ```compile_fail
79//! lock_ordering!{
80//!     Unlocked => A,
81//!     A => B,
82//!     B => A,
83//! }
84//! ```
85//!
86//! The methods on [Locked] prevent out-of-order locking according to the
87//! specified lock relationships.
88//!
89//! This won't compile because `LockB` does not implement `LockBefore<LockA>`:
90//! ```compile_fail
91//! # use std::sync::Mutex;
92//! # use starnix_sync::{lock_ordering, lock::LockFor, Locked, Unlocked};
93//! #
94//! # #[derive(Default)]
95//! # struct HoldsLocks {
96//! #    a: Mutex<u8>,
97//! #    b: Mutex<u32>,
98//! # }
99//! #
100//! # lock_ordering! {
101//! #    // LockA is the top of the lock hierarchy.
102//! #    Unlocked => LockA,
103//! #    // LockA can be acquired before LockB.
104//! #    LockA => LockB,
105//! # }
106//! #
107//! # impl LockFor<LockA> for HoldsLocks {
108//! #    type Data = u8;
109//! #    type Guard<'l> = std::sync::MutexGuard<'l, u8>
110//! #        where Self: 'l;
111//! #    fn lock(&self) -> Self::Guard<'_> {
112//! #        self.a.lock().unwrap()
113//! #    }
114//! # }
115//! #
116//! # impl LockFor<LockB> for HoldsLocks {
117//! #     type Data = u32;
118//! #     type Guard<'l> = std::sync::MutexGuard<'l, u32>
119//! #         where Self: 'l;
120//! #     fn lock(&self) -> Self::Guard<'_> {
121//! #         self.b.lock().unwrap()
122//! #     }
123//! # }
124//! #
125//!
126//! let state = HoldsLocks::default();
127//! let locked = Unlocked::new();
128//!
129//! // Locking B without A is fine, but locking A after B is not.
130//! let (b, locked_b) = locked.lock_and::<LockB, _>(&state);
131//! // compile error: LockB does not implement LockBefore<LockA>
132//! let a = locked_b.lock::<LockA, _>(&state);
133//! ```
134//!
135//! Even if the lock guard goes out of scope, the new `Locked` instance returned
136//! by [Locked::lock_and] will prevent the original one from being used to
137//! access state. This doesn't work:
138//!
139//! ```compile_fail
140//! # use std::sync::Mutex;
141//! # use starnix_sync::{lock_ordering, lock::LockFor, Locked, Unlocked};
142//! #
143//! # #[derive(Default)]
144//! # struct HoldsLocks {
145//! #     a: Mutex<u8>,
146//! #     b: Mutex<u32>,
147//! # }
148//! #
149//! # lock_ordering! {
150//! #    // LockA is the top of the lock hierarchy.
151//! #    Unlocked => LockA,
152//! #    // LockA can be acquired before LockB.
153//! #    LockA => LockB,
154//! # }
155//! #
156//! # impl LockFor<LockA> for HoldsLocks {
157//! #     type Data = u8;
158//! #     type Guard<'l> = std::sync::MutexGuard<'l, u8>
159//! #         where Self: 'l;
160//! #     fn lock(&self) -> Self::Guard<'_> {
161//! #         self.a.lock().unwrap()
162//! #     }
163//! # }
164//! #
165//! # impl LockFor<LockB> for HoldsLocks {
166//! #     type Data = u32;
167//! #     type Guard<'l> = std::sync::MutexGuard<'l, u32>
168//! #         where Self: 'l;
169//! #     fn lock(&self) -> Self::Guard<'_> {
170//! #         self.b.lock().unwrap()
171//! #     }
172//! # }
173//!
174//! let state = HoldsLocks::default();
175//! let locked = Unlocked::new();
176//!
177//! let (b, locked_b) = locked.lock_and::<LockB, _>();
178//! drop(b);
179//! let b = locked_b.lock::<LockB, _>(&state);
180//! // Won't work; `locked` is mutably borrowed by `locked_b`.
181//! let a = locked.lock::<LockA, _>(&state);
182//! ```
183
184use core::marker::PhantomData;
185use static_assertions::const_assert_eq;
186
187pub use crate::{LockBefore, LockEqualOrBefore, LockFor, RwLockFor};
188
189/// Enforcement mechanism for lock ordering.
190///
191/// `Locked` is a context that holds the lock level marker. Any state that
192/// requires a lock to access should acquire this lock by calling `lock_and`
193/// on a `Locked` object that is of an appropriate lock level. Acquiring
194/// a lock in this way produces the guard and a new `Locked` instance
195/// (with a different lock level) that mutably borrows from the original
196/// instance. This means the original instance can't be used to acquire
197/// new locks until the new instance leaves scope.
198pub struct Locked<L>(PhantomData<L>);
199
200impl<L> std::fmt::Debug for Locked<L> {
201    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
202        f.debug_struct(std::any::type_name::<Self>()).finish()
203    }
204}
205
206/// "Highest" lock level
207///
208/// The lock level for the thing returned by `Locked::new`. Users of this crate
209/// should implement `LockAfter<Unlocked>` for the root of any lock ordering
210/// trees.
211pub enum Unlocked {}
212
213const_assert_eq!(std::mem::size_of::<Locked<Unlocked>>(), 0);
214
215impl Unlocked {
216    /// Entry point for locked access.
217    ///
218    /// `Unlocked` is the "root" lock level and can be acquired before any lock.
219    ///
220    /// # Safety
221    /// `Unlocked` should only be used before any lock in the program has been acquired.
222    #[inline(always)]
223    pub unsafe fn new() -> &'static mut Locked<Unlocked> {
224        Locked::fabricate()
225    }
226
227    /// Entry point for locked access.
228    ///
229    /// `Unlocked` is the "root" lock level and can be acquired before any lock.
230    ///
231    /// # Safety
232    /// `Unlocked` should only be used before any lock in the program has been acquired.
233    #[inline(always)]
234    pub unsafe fn new_instance() -> Locked<Unlocked> {
235        Locked::<Unlocked>(Default::default())
236    }
237}
238impl LockEqualOrBefore<Unlocked> for Unlocked {}
239
240impl<L> Locked<L> {
241    /// Acquire the given lock.
242    ///
243    /// This requires that `M` can be locked after `L`.
244    #[inline(always)]
245    pub fn lock<'a, M, S>(&'a mut self, source: &'a S) -> S::Guard<'a>
246    where
247        M: 'a,
248        S: LockFor<M>,
249        L: LockBefore<M>,
250    {
251        let (data, _) = self.lock_and::<M, S>(source);
252        data
253    }
254
255    /// Acquire the given lock and a new locked context.
256    ///
257    /// This requires that `M` can be locked after `L`.
258    #[inline(always)]
259    pub fn lock_and<'a, M, S>(&'a mut self, source: &'a S) -> (S::Guard<'a>, &'a mut Locked<M>)
260    where
261        M: 'a,
262        S: LockFor<M>,
263        L: LockBefore<M>,
264    {
265        let data = S::lock(source);
266        (data, Locked::fabricate())
267    }
268
269    /// Acquire two locks that are on the same level, in a consistent order (sorted by memory address) and return both guards
270    /// as well as the new locked context.
271    ///
272    /// This requires that `M` can be locked after `L`.
273    #[inline(always)]
274    pub fn lock_both_and<'a, M, S>(
275        &'a mut self,
276        source1: &'a S,
277        source2: &'a S,
278    ) -> (S::Guard<'a>, S::Guard<'a>, &mut Locked<M>)
279    where
280        M: 'a,
281        S: LockFor<M>,
282        L: LockBefore<M>,
283    {
284        let ptr1: *const S = source1;
285        let ptr2: *const S = source2;
286        if ptr1 < ptr2 {
287            let data1 = S::lock(source1);
288            let data2 = S::lock(source2);
289            (data1, data2, Locked::fabricate())
290        } else {
291            let data2 = S::lock(source2);
292            let data1 = S::lock(source1);
293            (data1, data2, Locked::fabricate())
294        }
295    }
296    /// Acquire two locks that are on the same level, in a consistent order (sorted by memory address) and return both guards.
297    ///
298    /// This requires that `M` can be locked after `L`.
299    #[inline(always)]
300    pub fn lock_both<'a, M, S>(
301        &'a mut self,
302        source1: &'a S,
303        source2: &'a S,
304    ) -> (S::Guard<'a>, S::Guard<'a>)
305    where
306        M: 'a,
307        S: LockFor<M>,
308        L: LockBefore<M>,
309    {
310        let (data1, data2, _) = self.lock_both_and(source1, source2);
311        (data1, data2)
312    }
313
314    /// Attempt to acquire the given read lock and a new locked context.
315    ///
316    /// For accessing state via reader/writer locks. This requires that `M` can
317    /// be locked after `L`.
318    #[inline(always)]
319    pub fn read_lock_and<'a, M, S>(
320        &'a mut self,
321        source: &'a S,
322    ) -> (S::ReadGuard<'a>, &mut Locked<M>)
323    where
324        M: 'a,
325        S: RwLockFor<M>,
326        L: LockBefore<M>,
327    {
328        let data = S::read_lock(source);
329        (data, Locked::fabricate())
330    }
331
332    /// Attempt to acquire the given read lock.
333    ///
334    /// For accessing state via reader/writer locks. This requires that `M` can
335    /// be locked after `L`.
336    #[inline(always)]
337    pub fn read_lock<'a, M, S>(&'a mut self, source: &'a S) -> S::ReadGuard<'a>
338    where
339        M: 'a,
340        S: RwLockFor<M>,
341        L: LockBefore<M>,
342    {
343        let (data, _) = self.read_lock_and::<M, S>(source);
344        data
345    }
346
347    /// Attempt to acquire the given write lock and a new locked context.
348    ///
349    /// For accessing state via reader/writer locks. This requires that `M` can
350    /// be locked after `L`.
351    #[inline(always)]
352    pub fn write_lock_and<'a, M, S>(
353        &'a mut self,
354        source: &'a S,
355    ) -> (S::WriteGuard<'a>, &mut Locked<M>)
356    where
357        M: 'a,
358        S: RwLockFor<M>,
359        L: LockBefore<M>,
360    {
361        let data = S::write_lock(source);
362        (data, Locked::fabricate())
363    }
364
365    /// Attempt to acquire the given write lock.
366    ///
367    /// For accessing state via reader/writer locks. This requires that `M` can
368    /// be locked after `L`.
369    #[inline(always)]
370    pub fn write_lock<'a, M, S>(&'a mut self, source: &'a S) -> S::WriteGuard<'a>
371    where
372        M: 'a,
373        S: RwLockFor<M>,
374        L: LockBefore<M>,
375    {
376        let (data, _) = self.write_lock_and::<M, S>(source);
377        data
378    }
379
380    /// Restrict locking as if a lock was acquired.
381    ///
382    /// Like `lock_and` but doesn't actually acquire the lock `M`. This is
383    /// safe because any locks that could be acquired with the lock `M` held can
384    /// also be acquired without `M` being held.
385    #[inline(always)]
386    pub fn cast_locked<M>(&mut self) -> &mut Locked<M>
387    where
388        L: LockEqualOrBefore<M>,
389    {
390        Locked::fabricate()
391    }
392
393    const CHECK_ZST: () = assert!(std::mem::size_of::<Self>() == 0, "Locked<T> must be a ZST");
394    fn fabricate<'a>() -> &'a mut Self {
395        let _ = Self::CHECK_ZST;
396        // SAFETY: As confirmed by the preceding assert, `Self`
397        // is a ZST. `NonNull::as_mut` requires that the pointer is convertible
398        // to a reference [1], which in turn requires the following [2]:
399        // - The pointer is properly aligned (guaranteed by `NonNull::dangling`)
400        // - Non-null (guaranteed by invariant on `NonNull`)
401        // - Dereferenceable (guaranteed for all zero-sized pointers [3])
402        // - Points to a valid referent (trivially true for any zero-sized referent)
403        // - Satisfies Rust's aliasing rules (trivially true for any zero-sized referent)
404        //
405        // [1] https://doc.rust-lang.org/1.87.0/std/ptr/struct.NonNull.html#method.as_mut
406        // [2] https://doc.rust-lang.org/1.87.0/std/ptr/index.html#pointer-to-reference-conversion
407        // [3] https://doc.rust-lang.org/1.87.0/std/ptr/index.html#safety
408        unsafe { std::ptr::NonNull::dangling().as_mut() }
409    }
410}
411
412#[cfg(test)]
413mod test {
414    use std::sync::{Mutex, MutexGuard, RwLock, RwLockReadGuard, RwLockWriteGuard};
415
416    #[test]
417    fn example() {
418        use crate::{lock_ordering, Unlocked};
419
420        #[derive(Default)]
421        pub struct HoldsLocks {
422            a: Mutex<u8>,
423            b: Mutex<u32>,
424        }
425
426        lock_ordering! {
427            // LockA is the top of the lock hierarchy.
428            Unlocked => LockA,
429            // LockA can be acquired before LockB.
430            LockA => LockB,
431        }
432
433        impl LockFor<LockA> for HoldsLocks {
434            type Data = u8;
435            type Guard<'l>
436                = std::sync::MutexGuard<'l, u8>
437            where
438                Self: 'l;
439            fn lock(&self) -> Self::Guard<'_> {
440                self.a.lock().unwrap()
441            }
442        }
443
444        impl LockFor<LockB> for HoldsLocks {
445            type Data = u32;
446            type Guard<'l>
447                = std::sync::MutexGuard<'l, u32>
448            where
449                Self: 'l;
450            fn lock(&self) -> Self::Guard<'_> {
451                self.b.lock().unwrap()
452            }
453        }
454
455        // Accessing locked state looks like this:
456
457        let state = HoldsLocks::default();
458        // Create a new lock session with the "root" lock level (empty tuple).
459        let locked = unsafe { Unlocked::new() };
460        // Access locked state.
461        let (_a, locked_a) = locked.lock_and::<LockA, _>(&state);
462        let _b = locked_a.lock::<LockB, _>(&state);
463    }
464
465    mod lock_levels {
466        use crate::Unlocked;
467        use lock_ordering_macro::lock_ordering;
468        // Lock ordering tree:
469        // A -> B -> {C, D, E -> F, G -> H}
470        lock_ordering! {
471            Unlocked => A,
472            A => B,
473            B => C,
474            B => D,
475            B => E,
476            E => F,
477            B => G,
478            G => H,
479        }
480    }
481
482    use crate::{LockFor, RwLockFor, Unlocked};
483    use lock_levels::{A, B, C, D, E, F, G, H};
484
485    /// Data type with multiple locked fields.
486    #[derive(Default)]
487    pub struct Data {
488        a: Mutex<u8>,
489        b: Mutex<u16>,
490        c: Mutex<u64>,
491        d: RwLock<u128>,
492        e: Mutex<Mutex<u8>>,
493        g: Mutex<Vec<Mutex<u8>>>,
494        u: usize,
495    }
496
497    impl LockFor<A> for Data {
498        type Data = u8;
499        type Guard<'l> = MutexGuard<'l, u8>;
500        fn lock(&self) -> Self::Guard<'_> {
501            self.a.lock().unwrap()
502        }
503    }
504
505    impl LockFor<B> for Data {
506        type Data = u16;
507        type Guard<'l> = MutexGuard<'l, u16>;
508        fn lock(&self) -> Self::Guard<'_> {
509            self.b.lock().unwrap()
510        }
511    }
512
513    impl LockFor<C> for Data {
514        type Data = u64;
515        type Guard<'l> = MutexGuard<'l, u64>;
516        fn lock(&self) -> Self::Guard<'_> {
517            self.c.lock().unwrap()
518        }
519    }
520
521    impl RwLockFor<D> for Data {
522        type Data = u128;
523        type ReadGuard<'l> = RwLockReadGuard<'l, u128>;
524        type WriteGuard<'l> = RwLockWriteGuard<'l, u128>;
525        fn read_lock(&self) -> Self::ReadGuard<'_> {
526            self.d.read().unwrap()
527        }
528        fn write_lock(&self) -> Self::WriteGuard<'_> {
529            self.d.write().unwrap()
530        }
531    }
532
533    impl LockFor<E> for Data {
534        type Data = Mutex<u8>;
535        type Guard<'l> = MutexGuard<'l, Mutex<u8>>;
536        fn lock(&self) -> Self::Guard<'_> {
537            self.e.lock().unwrap()
538        }
539    }
540
541    impl LockFor<F> for Mutex<u8> {
542        type Data = u8;
543        type Guard<'l> = MutexGuard<'l, u8>;
544        fn lock(&self) -> Self::Guard<'_> {
545            self.lock().unwrap()
546        }
547    }
548
549    impl LockFor<G> for Data {
550        type Data = Vec<Mutex<u8>>;
551        type Guard<'l> = MutexGuard<'l, Vec<Mutex<u8>>>;
552        fn lock(&self) -> Self::Guard<'_> {
553            self.g.lock().unwrap()
554        }
555    }
556
557    impl LockFor<H> for Mutex<u8> {
558        type Data = u8;
559        type Guard<'l> = MutexGuard<'l, u8>;
560        fn lock(&self) -> Self::Guard<'_> {
561            self.lock().unwrap()
562        }
563    }
564
565    #[derive(Debug)]
566    #[allow(dead_code)]
567    struct NotPresent;
568
569    #[test]
570    fn lock_a_then_c() {
571        let data = Data::default();
572
573        let w = unsafe { Unlocked::new() };
574        let (_a, wa) = w.lock_and::<A, _>(&data);
575        let (_c, _wc) = wa.lock_and::<C, _>(&data);
576        // This won't compile!
577        // let _b = _wc.lock::<B, _>(&data);
578    }
579
580    #[test]
581    fn cast_a_then_c() {
582        let data = Data::default();
583
584        let w = unsafe { Unlocked::new() };
585        let wa = w.cast_locked::<A>();
586        let (_c, _wc) = wa.lock_and::<C, _>(&data);
587        // This should not compile:
588        // let _b = w.lock::<B, _>(&data);
589    }
590
591    #[test]
592    fn unlocked_access_does_not_prevent_locking() {
593        let data = Data { a: Mutex::new(15), u: 34, ..Data::default() };
594
595        let locked = unsafe { Unlocked::new() };
596        let u = &data.u;
597
598        // Prove that `u` does not prevent locked state from being accessed.
599        let a = locked.lock::<A, _>(&data);
600
601        assert_eq!(u, &34);
602        assert_eq!(&*a, &15);
603    }
604
605    #[test]
606    fn nested_locks() {
607        let data = Data { e: Mutex::new(Mutex::new(1)), ..Data::default() };
608
609        let locked = unsafe { Unlocked::new() };
610        let (e, next_locked) = locked.lock_and::<E, _>(&data);
611        let v = next_locked.lock::<F, _>(&*e);
612        assert_eq!(*v, 1);
613    }
614
615    #[test]
616    fn rw_lock() {
617        let data = Data { d: RwLock::new(1), ..Data::default() };
618
619        let locked = unsafe { Unlocked::new() };
620        {
621            let mut d = locked.write_lock::<D, _>(&data);
622            *d = 10;
623        }
624        let d = locked.read_lock::<D, _>(&data);
625        assert_eq!(*d, 10);
626    }
627
628    #[test]
629    fn collections() {
630        let data = Data { g: Mutex::new(vec![Mutex::new(0), Mutex::new(1)]), ..Data::default() };
631
632        let locked = unsafe { Unlocked::new() };
633        let (g, next_locked) = locked.lock_and::<G, _>(&data);
634        let v = next_locked.lock::<H, _>(&g[1]);
635        assert_eq!(*v, 1);
636    }
637
638    #[test]
639    fn lock_same_level() {
640        let data1 = Data { a: Mutex::new(5), b: Mutex::new(15), ..Data::default() };
641        let data2 = Data { a: Mutex::new(10), b: Mutex::new(20), ..Data::default() };
642        let locked = unsafe { Unlocked::new() };
643        {
644            let (a1, a2, new_locked) = locked.lock_both_and::<A, _>(&data1, &data2);
645            assert_eq!(*a1, 5);
646            assert_eq!(*a2, 10);
647            let (b1, b2) = new_locked.lock_both::<B, _>(&data1, &data2);
648            assert_eq!(*b1, 15);
649            assert_eq!(*b2, 20);
650        }
651        {
652            let (a2, a1) = locked.lock_both::<A, _>(&data2, &data1);
653            assert_eq!(*a1, 5);
654            assert_eq!(*a2, 10);
655        }
656    }
657}
starnix_sync/lock_sequence.rs

starnix_sync/
lock_sequence.rs
