maitake_sync/util/
backoff.rs

1/// An [exponential backoff] for spin loops.
2///
3/// This is a helper struct for spinning in a busy loop, with an exponentially
4/// increasing number of spins up to a maximum value.
5///
6/// [exponential backoff]: https://en.wikipedia.org/wiki/Exponential_backoff
7#[derive(Debug, Copy, Clone)]
8pub struct Backoff {
9    exp: u8,
10    max: u8,
11}
12
13// === impl Backoff ===
14
15impl Backoff {
16    /// The default maximum exponent (2^8).
17    ///
18    /// This is the maximum exponent returned by [`Backoff::new()`] and
19    /// [`Backoff::default()`]. To override the maximum exponent, use
20    /// [`Backoff::with_max_exponent()`].
21    pub const DEFAULT_MAX_EXPONENT: u8 = 8;
22
23    /// Returns a new exponential backoff with the maximum exponent set to
24    /// [`Self::DEFAULT_MAX_EXPONENT`].
25    #[must_use]
26    pub const fn new() -> Self {
27        Self {
28            exp: 0,
29            max: Self::DEFAULT_MAX_EXPONENT,
30        }
31    }
32
33    /// Returns a new exponential backoff with the provided max exponent.
34    #[must_use]
35    pub fn with_max_exponent(max: u8) -> Self {
36        assert!(max <= Self::DEFAULT_MAX_EXPONENT);
37        Self { exp: 0, max }
38    }
39
40    /// Backs off in a spin loop.
41    ///
42    /// This should be used when an operation needs to be retried because
43    /// another thread or core made progress. Depending on the target
44    /// architecture, this will generally issue a sequence of `yield` or `pause`
45    /// instructions.
46    ///
47    /// Each time this function is called, it will issue `2^exp` [spin loop
48    /// hints], where `exp` is the current exponent value (starting at 0). If
49    /// `exp` is less than the configured maximum exponent, the exponent is
50    /// incremented once the spin is complete.
51    #[inline(always)]
52    pub fn spin(&mut self) {
53        // Issue 2^exp pause instructions.
54        #[cfg_attr(loom, allow(unused_variables))]
55        let spins = 1 << self.exp;
56
57        #[cfg(not(loom))]
58        for _ in 0..spins {
59            crate::loom::hint::spin_loop();
60        }
61
62        #[cfg(loom)]
63        {
64            test_debug!("would back off for {spins} spins");
65            loom::thread::yield_now();
66        }
67
68        if self.exp < self.max {
69            self.exp += 1
70        }
71    }
72}
73
74impl Default for Backoff {
75    fn default() -> Self {
76        Self::new()
77    }
78}
maitake_sync/util/backoff.rs

maitake_sync/util/
backoff.rs
