maitake_sync/util/
backoff.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
use crate::loom::hint;

/// An [exponential backoff] for spin loops.
///
/// This is a helper struct for spinning in a busy loop, with an exponentially
/// increasing number of spins up to a maximum value.
///
/// [exponential backoff]: https://en.wikipedia.org/wiki/Exponential_backoff
#[derive(Debug, Copy, Clone)]
pub struct Backoff {
    exp: u8,
    max: u8,
}

// === impl Backoff ===

impl Backoff {
    /// The default maximum exponent (2^8).
    ///
    /// This is the maximum exponent returned by [`Backoff::new()`] and
    /// [`Backoff::default()`]. To override the maximum exponent, use
    /// [`Backoff::with_max_exponent()`].
    pub const DEFAULT_MAX_EXPONENT: u8 = 8;

    /// Returns a new exponential backoff with the maximum exponent set to
    /// [`Self::DEFAULT_MAX_EXPONENT`].
    #[must_use]
    pub const fn new() -> Self {
        Self {
            exp: 0,
            max: Self::DEFAULT_MAX_EXPONENT,
        }
    }

    /// Returns a new exponential backoff with the provided max exponent.
    #[must_use]
    pub fn with_max_exponent(max: u8) -> Self {
        assert!(max <= Self::DEFAULT_MAX_EXPONENT);
        Self { exp: 0, max }
    }

    /// Backs off in a spin loop.
    ///
    /// This should be used when an operation needs to be retried because
    /// another thread or core made progress. Depending on the target
    /// architecture, this will generally issue a sequence of `yield` or `pause`
    /// instructions.
    ///
    /// Each time this function is called, it will issue `2^exp` [spin loop
    /// hints], where `exp` is the current exponent value (starting at 0). If
    /// `exp` is less than the configured maximum exponent, the exponent is
    /// incremented once the spin is complete.
    #[inline(always)]
    pub fn spin(&mut self) {
        // Issue 2^exp pause instructions.
        for _ in 0..1 << self.exp {
            hint::spin_loop();
        }

        if self.exp < self.max {
            self.exp += 1
        }
    }
}

impl Default for Backoff {
    fn default() -> Self {
        Self::new()
    }
}