crossbeam_utils/cache_padded.rs
1use core::fmt;
2use 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/// # Layout
33///
34/// Since crossbeam-utils 0.8.22, this type is `#[repr(C)]` and is guaranteed that the pointer to
35/// `CachePadded<T>` has the same address as the pointer to the underlying `T`.
36///
37/// # Examples
38///
39/// Alignment and padding:
40///
41/// ```
42/// use crossbeam_utils::CachePadded;
43///
44/// let array = [CachePadded::new(1i8), CachePadded::new(2i8)];
45/// let addr1 = &*array[0] as *const i8 as usize;
46/// let addr2 = &*array[1] as *const i8 as usize;
47///
48/// assert!(addr2 - addr1 >= 32);
49/// assert_eq!(addr1 % 32, 0);
50/// assert_eq!(addr2 % 32, 0);
51/// ```
52///
53/// When building a concurrent queue with a head and a tail index, it is wise to place them in
54/// different cache lines so that concurrent threads pushing and popping elements don't invalidate
55/// each other's cache lines:
56///
57/// ```
58/// use crossbeam_utils::CachePadded;
59/// use std::sync::atomic::AtomicUsize;
60///
61/// struct Queue<T> {
62/// head: CachePadded<AtomicUsize>,
63/// tail: CachePadded<AtomicUsize>,
64/// buffer: *mut T,
65/// }
66/// ```
67#[derive(Clone, Copy, Default, Hash, PartialEq, Eq)]
68// Starting from Intel's Sandy Bridge, spatial prefetcher is now pulling pairs of 64-byte cache
69// lines at a time, so we have to align to 128 bytes rather than 64.
70//
71// Sources:
72// - https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf
73// - https://github.com/facebook/folly/blob/1b5288e6eea6df074758f877c849b6e73bbb9fbb/folly/lang/Align.h#L107
74//
75// aarch64/arm64ec's big.LITTLE architecture has asymmetric cores and "big" cores have 128-byte cache line size.
76//
77// Sources:
78// - https://www.mono-project.com/news/2016/09/12/arm64-icache/
79//
80// powerpc64 has 128-byte cache line size.
81//
82// Sources:
83// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_ppc64x.go#L9
84// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/powerpc/include/asm/cache.h#L26
85#[cfg_attr(
86 any(
87 target_arch = "x86_64",
88 target_arch = "aarch64",
89 target_arch = "arm64ec",
90 target_arch = "powerpc64",
91 ),
92 repr(align(128))
93)]
94// arm, mips, mips64, sparc, and hexagon have 32-byte cache line size.
95//
96// Sources:
97// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_arm.go#L7
98// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips.go#L7
99// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mipsle.go#L7
100// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips64x.go#L9
101// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/sparc/include/asm/cache.h#L17
102// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/hexagon/include/asm/cache.h#L12
103#[cfg_attr(
104 any(
105 target_arch = "arm",
106 target_arch = "mips",
107 target_arch = "mips32r6",
108 target_arch = "mips64",
109 target_arch = "mips64r6",
110 target_arch = "sparc",
111 target_arch = "hexagon",
112 ),
113 repr(align(32))
114)]
115// m68k has 16-byte cache line size.
116//
117// Sources:
118// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/m68k/include/asm/cache.h#L9
119#[cfg_attr(target_arch = "m68k", repr(align(16)))]
120// s390x has 256-byte cache line size.
121//
122// Sources:
123// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_s390x.go#L7
124// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/s390/include/asm/cache.h#L13
125#[cfg_attr(target_arch = "s390x", repr(align(256)))]
126// x86, wasm, riscv, and sparc64 have 64-byte cache line size.
127//
128// Sources:
129// - https://github.com/golang/go/blob/dda2991c2ea0c5914714469c4defc2562a907230/src/internal/cpu/cpu_x86.go#L9
130// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_wasm.go#L7
131// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/riscv/include/asm/cache.h#L10
132// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/sparc/include/asm/cache.h#L19
133//
134// All others are assumed to have 64-byte cache line size.
135#[cfg_attr(
136 not(any(
137 target_arch = "x86_64",
138 target_arch = "aarch64",
139 target_arch = "arm64ec",
140 target_arch = "powerpc64",
141 target_arch = "arm",
142 target_arch = "mips",
143 target_arch = "mips32r6",
144 target_arch = "mips64",
145 target_arch = "mips64r6",
146 target_arch = "sparc",
147 target_arch = "hexagon",
148 target_arch = "m68k",
149 target_arch = "s390x",
150 )),
151 repr(align(64))
152)]
153#[repr(C)]
154pub struct CachePadded<T> {
155 value: T,
156}
157
158unsafe impl<T: Send> Send for CachePadded<T> {}
159unsafe impl<T: Sync> Sync for CachePadded<T> {}
160
161impl<T> CachePadded<T> {
162 /// Pads and aligns a value to the length of a cache line.
163 ///
164 /// # Examples
165 ///
166 /// ```
167 /// use crossbeam_utils::CachePadded;
168 ///
169 /// let padded_value = CachePadded::new(1);
170 /// ```
171 pub const fn new(t: T) -> CachePadded<T> {
172 CachePadded::<T> { value: t }
173 }
174
175 /// Returns the inner value.
176 ///
177 /// # Examples
178 ///
179 /// ```
180 /// use crossbeam_utils::CachePadded;
181 ///
182 /// let padded_value = CachePadded::new(7);
183 /// let value = padded_value.into_inner();
184 /// assert_eq!(value, 7);
185 /// ```
186 pub fn into_inner(self) -> T {
187 self.value
188 }
189}
190
191impl<T> Deref for CachePadded<T> {
192 type Target = T;
193
194 fn deref(&self) -> &T {
195 &self.value
196 }
197}
198
199impl<T> DerefMut for CachePadded<T> {
200 fn deref_mut(&mut self) -> &mut T {
201 &mut self.value
202 }
203}
204
205impl<T: fmt::Debug> fmt::Debug for CachePadded<T> {
206 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
207 f.debug_struct("CachePadded")
208 .field("value", &self.value)
209 .finish()
210 }
211}
212
213impl<T> From<T> for CachePadded<T> {
214 fn from(t: T) -> Self {
215 CachePadded::new(t)
216 }
217}
218
219impl<T: fmt::Display> fmt::Display for CachePadded<T> {
220 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
221 fmt::Display::fmt(&self.value, f)
222 }
223}