| 1 |
use core::fmt; |
| 2 |
use core::ops::{Deref, DerefMut}; |
| 3 |
|
| 4 |
/// Pads and aligns a value to the length of a cache line. |
| 5 |
/// |
| 6 |
/// In concurrent programming, sometimes it is desirable to make sure commonly accessed pieces of |
| 7 |
/// data are not placed into the same cache line. Updating an atomic value invalidates the whole |
| 8 |
/// cache line it belongs to, which makes the next access to the same cache line slower for other |
| 9 |
/// CPU cores. Use `CachePadded` to ensure updating one piece of data doesn't invalidate other |
| 10 |
/// cached data. |
| 11 |
/// |
| 12 |
/// # Size and alignment |
| 13 |
/// |
| 14 |
/// Cache lines are assumed to be N bytes long, depending on the architecture: |
| 15 |
/// |
| 16 |
/// * On x86-64, aarch64, and powerpc64, N = 128. |
| 17 |
/// * On arm, mips, mips64, sparc, and hexagon, N = 32. |
| 18 |
/// * On m68k, N = 16. |
| 19 |
/// * On s390x, N = 256. |
| 20 |
/// * On all others, N = 64. |
| 21 |
/// |
| 22 |
/// Note that N is just a reasonable guess and is not guaranteed to match the actual cache line |
| 23 |
/// length of the machine the program is running on. On modern Intel architectures, spatial |
| 24 |
/// prefetcher is pulling pairs of 64-byte cache lines at a time, so we pessimistically assume that |
| 25 |
/// cache lines are 128 bytes long. |
| 26 |
/// |
| 27 |
/// The size of `CachePadded<T>` is the smallest multiple of N bytes large enough to accommodate |
| 28 |
/// a value of type `T`. |
| 29 |
/// |
| 30 |
/// The alignment of `CachePadded<T>` is the maximum of N bytes and the alignment of `T`. |
| 31 |
/// |
| 32 |
/// # Examples |
| 33 |
/// |
| 34 |
/// Alignment and padding: |
| 35 |
/// |
| 36 |
/// ``` |
| 37 |
/// use crossbeam_utils::CachePadded; |
| 38 |
/// |
| 39 |
/// let array = [CachePadded::new(1i8), CachePadded::new(2i8)]; |
| 40 |
/// let addr1 = &*array[0] as *const i8 as usize; |
| 41 |
/// let addr2 = &*array[1] as *const i8 as usize; |
| 42 |
/// |
| 43 |
/// assert!(addr2 - addr1 >= 32); |
| 44 |
/// assert_eq!(addr1 % 32, 0); |
| 45 |
/// assert_eq!(addr2 % 32, 0); |
| 46 |
/// ``` |
| 47 |
/// |
| 48 |
/// When building a concurrent queue with a head and a tail index, it is wise to place them in |
| 49 |
/// different cache lines so that concurrent threads pushing and popping elements don't invalidate |
| 50 |
/// each other's cache lines: |
| 51 |
/// |
| 52 |
/// ``` |
| 53 |
/// use crossbeam_utils::CachePadded; |
| 54 |
/// use std::sync::atomic::AtomicUsize; |
| 55 |
/// |
| 56 |
/// struct Queue<T> { |
| 57 |
/// head: CachePadded<AtomicUsize>, |
| 58 |
/// tail: CachePadded<AtomicUsize>, |
| 59 |
/// buffer: *mut T, |
| 60 |
/// } |
| 61 |
/// ``` |
| 62 |
#[derive(Clone, Copy, Default, Hash, PartialEq, Eq)] |
| 63 |
// Starting from Intel's Sandy Bridge, spatial prefetcher is now pulling pairs of 64-byte cache |
| 64 |
// lines at a time, so we have to align to 128 bytes rather than 64. |
| 65 |
// |
| 66 |
// Sources: |
| 67 |
// - https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf |
| 68 |
// - https://github.com/facebook/folly/blob/1b5288e6eea6df074758f877c849b6e73bbb9fbb/folly/lang/Align.h#L107 |
| 69 |
// |
| 70 |
// ARM's big.LITTLE architecture has asymmetric cores and "big" cores have 128-byte cache line size. |
| 71 |
// |
| 72 |
// Sources: |
| 73 |
// - https://www.mono-project.com/news/2016/09/12/arm64-icache/ |
| 74 |
// |
| 75 |
// powerpc64 has 128-byte cache line size. |
| 76 |
// |
| 77 |
// Sources: |
| 78 |
// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_ppc64x.go#L9 |
| 79 |
// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/powerpc/include/asm/cache.h#L26 |
| 80 |
#[cfg_attr( |
| 81 |
any( |
| 82 |
target_arch = "x86_64", |
| 83 |
target_arch = "aarch64", |
| 84 |
target_arch = "powerpc64", |
| 85 |
), |
| 86 |
repr(align(128)) |
| 87 |
)] |
| 88 |
// arm, mips, mips64, sparc, and hexagon have 32-byte cache line size. |
| 89 |
// |
| 90 |
// Sources: |
| 91 |
// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_arm.go#L7 |
| 92 |
// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips.go#L7 |
| 93 |
// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mipsle.go#L7 |
| 94 |
// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips64x.go#L9 |
| 95 |
// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/sparc/include/asm/cache.h#L17 |
| 96 |
// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/hexagon/include/asm/cache.h#L12 |
| 97 |
#[cfg_attr( |
| 98 |
any( |
| 99 |
target_arch = "arm", |
| 100 |
target_arch = "mips", |
| 101 |
target_arch = "mips32r6", |
| 102 |
target_arch = "mips64", |
| 103 |
target_arch = "mips64r6", |
| 104 |
target_arch = "sparc", |
| 105 |
target_arch = "hexagon", |
| 106 |
), |
| 107 |
repr(align(32)) |
| 108 |
)] |
| 109 |
// m68k has 16-byte cache line size. |
| 110 |
// |
| 111 |
// Sources: |
| 112 |
// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/m68k/include/asm/cache.h#L9 |
| 113 |
#[cfg_attr(target_arch = "m68k", repr(align(16)))] |
| 114 |
// s390x has 256-byte cache line size. |
| 115 |
// |
| 116 |
// Sources: |
| 117 |
// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_s390x.go#L7 |
| 118 |
// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/s390/include/asm/cache.h#L13 |
| 119 |
#[cfg_attr(target_arch = "s390x", repr(align(256)))] |
| 120 |
// x86, wasm, riscv, and sparc64 have 64-byte cache line size. |
| 121 |
// |
| 122 |
// Sources: |
| 123 |
// - https://github.com/golang/go/blob/dda2991c2ea0c5914714469c4defc2562a907230/src/internal/cpu/cpu_x86.go#L9 |
| 124 |
// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_wasm.go#L7 |
| 125 |
// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/riscv/include/asm/cache.h#L10 |
| 126 |
// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/sparc/include/asm/cache.h#L19 |
| 127 |
// |
| 128 |
// All others are assumed to have 64-byte cache line size. |
| 129 |
#[cfg_attr( |
| 130 |
not(any( |
| 131 |
target_arch = "x86_64", |
| 132 |
target_arch = "aarch64", |
| 133 |
target_arch = "powerpc64", |
| 134 |
target_arch = "arm", |
| 135 |
target_arch = "mips", |
| 136 |
target_arch = "mips32r6", |
| 137 |
target_arch = "mips64", |
| 138 |
target_arch = "mips64r6", |
| 139 |
target_arch = "sparc", |
| 140 |
target_arch = "hexagon", |
| 141 |
target_arch = "m68k", |
| 142 |
target_arch = "s390x", |
| 143 |
)), |
| 144 |
repr(align(64)) |
| 145 |
)] |
| 146 |
pub struct CachePadded<T> { |
| 147 |
value: T, |
| 148 |
} |
| 149 |
|
| 150 |
unsafe impl<T: Send> Send for CachePadded<T> {} |
| 151 |
unsafe impl<T: Sync> Sync for CachePadded<T> {} |
| 152 |
|
| 153 |
impl<T> CachePadded<T> { |
| 154 |
/// Pads and aligns a value to the length of a cache line. |
| 155 |
/// |
| 156 |
/// # Examples |
| 157 |
/// |
| 158 |
/// ``` |
| 159 |
/// use crossbeam_utils::CachePadded; |
| 160 |
/// |
| 161 |
/// let padded_value = CachePadded::new(1); |
| 162 |
/// ``` |
| 163 |
pub const fn new(t: T) -> CachePadded<T> { |
| 164 |
CachePadded::<T> { value: t } |
| 165 |
} |
| 166 |
|
| 167 |
/// Returns the inner value. |
| 168 |
/// |
| 169 |
/// # Examples |
| 170 |
/// |
| 171 |
/// ``` |
| 172 |
/// use crossbeam_utils::CachePadded; |
| 173 |
/// |
| 174 |
/// let padded_value = CachePadded::new(7); |
| 175 |
/// let value = padded_value.into_inner(); |
| 176 |
/// assert_eq!(value, 7); |
| 177 |
/// ``` |
| 178 |
pub fn into_inner(self) -> T { |
| 179 |
self.value |
| 180 |
} |
| 181 |
} |
| 182 |
|
| 183 |
impl<T> Deref for CachePadded<T> { |
| 184 |
type Target = T; |
| 185 |
|
| 186 |
fn deref(&self) -> &T { |
| 187 |
&self.value |
| 188 |
} |
| 189 |
} |
| 190 |
|
| 191 |
impl<T> DerefMut for CachePadded<T> { |
| 192 |
fn deref_mut(&mut self) -> &mut T { |
| 193 |
&mut self.value |
| 194 |
} |
| 195 |
} |
| 196 |
|
| 197 |
impl<T: fmt::Debug> fmt::Debug for CachePadded<T> { |
| 198 |
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 199 |
f.debug_struct("CachePadded") |
| 200 |
.field("value", &self.value) |
| 201 |
.finish() |
| 202 |
} |
| 203 |
} |
| 204 |
|
| 205 |
impl<T> From<T> for CachePadded<T> { |
| 206 |
fn from(t: T) -> Self { |
| 207 |
CachePadded::new(t) |
| 208 |
} |
| 209 |
} |