library/std/src/sync/mpmc/utils.rs

   1 use crate::cell::Cell;
   2 use crate::ops::{Deref, DerefMut};
   3
   4 /// Pads and aligns a value to the length of a cache line.
   5 #[derive(Clone, Copy, Default, Hash, PartialEq, Eq)]
   6 // Starting from Intel's Sandy Bridge, spatial prefetcher is now pulling pairs of 64-byte cache
   7 // lines at a time, so we have to align to 128 bytes rather than 64.
   8 //
   9 // Sources:
  10 // - https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf
  11 // - https://github.com/facebook/folly/blob/1b5288e6eea6df074758f877c849b6e73bbb9fbb/folly/lang/Align.h#L107
  12 //
  13 // ARM's big.LITTLE architecture has asymmetric cores and "big" cores have 128-byte cache line size.
  14 //
  15 // Sources:
  16 // - https://www.mono-project.com/news/2016/09/12/arm64-icache/
  17 //
  18 // powerpc64 has 128-byte cache line size.
  19 //
  20 // Sources:
  21 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_ppc64x.go#L9
  22 #[cfg_attr(
  23     any(target_arch = "x86_64", target_arch = "aarch64", target_arch = "powerpc64",),
  24     repr(align(128))
  25 )]
  26 // arm, mips, mips64, and riscv64 have 32-byte cache line size.
  27 //
  28 // Sources:
  29 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_arm.go#L7
  30 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips.go#L7
  31 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mipsle.go#L7
  32 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips64x.go#L9
  33 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_riscv64.go#L7
  34 #[cfg_attr(
  35     any(
  36         target_arch = "arm",
  37         target_arch = "mips",
  38         target_arch = "mips64",
  39         target_arch = "riscv64",
  40     ),
  41     repr(align(32))
  42 )]
  43 // s390x has 256-byte cache line size.
  44 //
  45 // Sources:
  46 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_s390x.go#L7
  47 #[cfg_attr(target_arch = "s390x", repr(align(256)))]
  48 // x86 and wasm have 64-byte cache line size.
  49 //
  50 // Sources:
  51 // - https://github.com/golang/go/blob/dda2991c2ea0c5914714469c4defc2562a907230/src/internal/cpu/cpu_x86.go#L9
  52 // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_wasm.go#L7
  53 //
  54 // All others are assumed to have 64-byte cache line size.
  55 #[cfg_attr(
  56     not(any(
  57         target_arch = "x86_64",
  58         target_arch = "aarch64",
  59         target_arch = "powerpc64",
  60         target_arch = "arm",
  61         target_arch = "mips",
  62         target_arch = "mips64",
  63         target_arch = "riscv64",
  64         target_arch = "s390x",
  65     )),
  66     repr(align(64))
  67 )]
  68 pub struct CachePadded<T> {
  69     value: T,
  70 }
  71
  72 impl<T> CachePadded<T> {
  73     /// Pads and aligns a value to the length of a cache line.
  74     pub fn new(value: T) -> CachePadded<T> {
  75         CachePadded::<T> { value }
  76     }
  77 }
  78
  79 impl<T> Deref for CachePadded<T> {
  80     type Target = T;
  81
  82     fn deref(&self) -> &T {
  83         &self.value
  84     }
  85 }
  86
  87 impl<T> DerefMut for CachePadded<T> {
  88     fn deref_mut(&mut self) -> &mut T {
  89         &mut self.value
  90     }
  91 }
  92
  93 const SPIN_LIMIT: u32 = 6;
  94 const YIELD_LIMIT: u32 = 10;
  95
  96 /// Performs exponential backoff in spin loops.
  97 pub struct Backoff {
  98     step: Cell<u32>,
  99 }
 100
 101 impl Backoff {
 102     /// Creates a new `Backoff`.
 103     pub fn new() -> Self {
 104         Backoff { step: Cell::new(0) }
 105     }
 106
 107     /// Backs off in a lock-free loop.
 108     ///
 109     /// This method should be used when we need to retry an operation because another thread made
 110     /// progress.
 111     #[inline]
 112     pub fn spin(&self) {
 113         let step = self.step.get().min(SPIN_LIMIT);
 114         for _ in 0..step.pow(2) {
 115             crate::hint::spin_loop();
 116         }
 117
 118         if self.step.get() <= SPIN_LIMIT {
 119             self.step.set(self.step.get() + 1);
 120         }
 121     }
 122
 123     /// Backs off in a blocking loop.
 124     #[inline]
 125     pub fn snooze(&self) {
 126         if self.step.get() <= SPIN_LIMIT {
 127             for _ in 0..self.step.get().pow(2) {
 128                 crate::hint::spin_loop()
 129             }
 130         } else {
 131             crate::thread::yield_now();
 132         }
 133
 134         if self.step.get() <= YIELD_LIMIT {
 135             self.step.set(self.step.get() + 1);
 136         }
 137     }
 138
 139     /// Returns `true` if quadratic backoff has completed and blocking the thread is advised.
 140     #[inline]
 141     pub fn is_completed(&self) -> bool {
 142         self.step.get() > YIELD_LIMIT
 143     }
 144 }