crossfire_utils/
cache_padded.rs

1//! Fork from crossbeam-utils crate commit 5a154def002304814d50f3c7658bd30eb46b2fad
2//!
3//! The MIT License (MIT)
4//!
5//! Copyright (c) 2019 The Crossbeam Project Developers
6//!
7//! Permission is hereby granted, free of charge, to any
8//! person obtaining a copy of this software and associated
9//! documentation files (the "Software"), to deal in the
10//! Software without restriction, including without
11//! limitation the rights to use, copy, modify, merge,
12//! publish, distribute, sublicense, and/or sell copies of
13//! the Software, and to permit persons to whom the Software
14//! is furnished to do so, subject to the following
15//! conditions:
16//!
17//! The above copyright notice and this permission notice
18//! shall be included in all copies or substantial portions
19//! of the Software.
20//!
21//! THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
22//! ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
23//! TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
24//! PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
25//! SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
26//! CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
27//! OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
28//! IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
29//! DEALINGS IN THE SOFTWARE.
30
31use core::{
32    fmt,
33    ops::{Deref, DerefMut},
34};
35
36/// Pads and aligns a value to the length of a cache line.
37///
38/// In concurrent programming, sometimes it is desirable to make sure commonly accessed pieces of
39/// data are not placed into the same cache line. Updating an atomic value invalidates the whole
40/// cache line it belongs to, which makes the next access to the same cache line slower for other
41/// CPU cores. Use `CachePadded` to ensure updating one piece of data doesn't invalidate other
42/// cached data.
43///
44/// # Size and alignment
45///
46/// Cache lines are assumed to be N bytes long, depending on the architecture:
47///
48/// * On x86-64, aarch64, and powerpc64, N = 128.
49/// * On arm, mips, mips64, sparc, and hexagon, N = 32.
50/// * On m68k, N = 16.
51/// * On s390x, N = 256.
52/// * On all others, N = 64.
53///
54/// Note that N is just a reasonable guess and is not guaranteed to match the actual cache line
55/// length of the machine the program is running on. On modern Intel architectures, spatial
56/// prefetcher is pulling pairs of 64-byte cache lines at a time, so we pessimistically assume that
57/// cache lines are 128 bytes long.
58///
59/// The size of `CachePadded<T>` is the smallest multiple of N bytes large enough to accommodate
60/// a value of type `T`.
61///
62/// The alignment of `CachePadded<T>` is the maximum of N bytes and the alignment of `T`.
63///
64/// # Layout
65///
66/// Since crossbeam-utils 0.8.22, this type is `#[repr(C)]` and is guaranteed that the pointer to
67/// `CachePadded<T>` has the same address as the pointer to the underlying `T`.
68///
69/// # Examples
70///
71/// Alignment and padding:
72///
73/// ```
74/// use crossfire_utils::CachePadded;
75///
76/// let array = [CachePadded::new(1i8), CachePadded::new(2i8)];
77/// let addr1 = &*array[0] as *const i8 as usize;
78/// let addr2 = &*array[1] as *const i8 as usize;
79///
80/// assert!(addr2 - addr1 >= 16);
81/// assert_eq!(addr1 % 16, 0);
82/// assert_eq!(addr2 % 16, 0);
83/// ```
84///
85/// When building a concurrent queue with a head and a tail index, it is wise to place them in
86/// different cache lines so that concurrent threads pushing and popping elements don't invalidate
87/// each other's cache lines:
88///
89/// ```
90/// use crossfire_utils::CachePadded;
91/// use core::sync::atomic::AtomicUsize;
92///
93/// struct Queue<T> {
94///     head: CachePadded<AtomicUsize>,
95///     tail: CachePadded<AtomicUsize>,
96///     buffer: *mut T,
97/// }
98/// ```
99#[derive(Clone, Copy, Default, Hash, PartialEq, Eq)]
100// Starting from Intel's Sandy Bridge, spatial prefetcher is now pulling pairs of 64-byte cache
101// lines at a time, so we have to align to 128 bytes rather than 64.
102//
103// Sources:
104// - https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf
105// - https://github.com/facebook/folly/blob/1b5288e6eea6df074758f877c849b6e73bbb9fbb/folly/lang/Align.h#L107
106//
107// aarch64/arm64ec's big.LITTLE architecture has asymmetric cores and "big" cores have 128-byte cache line size.
108//
109// Sources:
110// - https://www.mono-project.com/news/2016/09/12/arm64-icache/
111//
112// powerpc64 has 128-byte cache line size.
113//
114// Sources:
115// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_ppc64x.go#L9
116// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/powerpc/include/asm/cache.h#L26
117#[cfg_attr(
118    any(
119        target_arch = "x86_64",
120        target_arch = "aarch64",
121        target_arch = "arm64ec",
122        target_arch = "powerpc64",
123    ),
124    repr(align(128))
125)]
126// arm, mips, mips64, sparc, and hexagon have 32-byte cache line size.
127//
128// Sources:
129// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_arm.go#L7
130// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips.go#L7
131// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mipsle.go#L7
132// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips64x.go#L9
133// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/sparc/include/asm/cache.h#L17
134// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/hexagon/include/asm/cache.h#L12
135#[cfg_attr(
136    any(
137        target_arch = "arm",
138        target_arch = "mips",
139        target_arch = "mips32r6",
140        target_arch = "mips64",
141        target_arch = "mips64r6",
142        target_arch = "sparc",
143        target_arch = "hexagon",
144    ),
145    repr(align(32))
146)]
147// m68k has 16-byte cache line size.
148//
149// Sources:
150// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/m68k/include/asm/cache.h#L9
151#[cfg_attr(target_arch = "m68k", repr(align(16)))]
152// s390x has 256-byte cache line size.
153//
154// Sources:
155// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_s390x.go#L7
156// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/s390/include/asm/cache.h#L13
157#[cfg_attr(target_arch = "s390x", repr(align(256)))]
158// x86, wasm, riscv, and sparc64 have 64-byte cache line size.
159//
160// Sources:
161// - https://github.com/golang/go/blob/dda2991c2ea0c5914714469c4defc2562a907230/src/internal/cpu/cpu_x86.go#L9
162// - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_wasm.go#L7
163// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/riscv/include/asm/cache.h#L10
164// - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/sparc/include/asm/cache.h#L19
165//
166// All others are assumed to have 64-byte cache line size.
167#[cfg_attr(
168    not(any(
169        target_arch = "x86_64",
170        target_arch = "aarch64",
171        target_arch = "arm64ec",
172        target_arch = "powerpc64",
173        target_arch = "arm",
174        target_arch = "mips",
175        target_arch = "mips32r6",
176        target_arch = "mips64",
177        target_arch = "mips64r6",
178        target_arch = "sparc",
179        target_arch = "hexagon",
180        target_arch = "m68k",
181        target_arch = "s390x",
182    )),
183    repr(align(64))
184)]
185#[repr(C)]
186pub struct CachePadded<T> {
187    value: T,
188}
189
190unsafe impl<T: Send> Send for CachePadded<T> {}
191unsafe impl<T: Sync> Sync for CachePadded<T> {}
192
193impl<T> CachePadded<T> {
194    /// Pads and aligns a value to the length of a cache line.
195    ///
196    /// # Examples
197    ///
198    /// ```
199    /// use crossfire_utils::CachePadded;
200    ///
201    /// let padded_value = CachePadded::new(1);
202    /// ```
203    pub const fn new(t: T) -> Self {
204        Self { value: t }
205    }
206
207    /// Returns the inner value.
208    ///
209    /// # Examples
210    ///
211    /// ```
212    /// use crossfire_utils::CachePadded;
213    ///
214    /// let padded_value = CachePadded::new(7);
215    /// let value = padded_value.into_inner();
216    /// assert_eq!(value, 7);
217    /// ```
218    pub fn into_inner(self) -> T {
219        self.value
220    }
221}
222
223impl<T> Deref for CachePadded<T> {
224    type Target = T;
225
226    fn deref(&self) -> &T {
227        &self.value
228    }
229}
230
231impl<T> DerefMut for CachePadded<T> {
232    fn deref_mut(&mut self) -> &mut T {
233        &mut self.value
234    }
235}
236
237impl<T: fmt::Debug> fmt::Debug for CachePadded<T> {
238    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
239        f.debug_struct("CachePadded").field("value", &self.value).finish()
240    }
241}
242
243impl<T> From<T> for CachePadded<T> {
244    fn from(t: T) -> Self {
245        Self::new(t)
246    }
247}
248
249impl<T: fmt::Display> fmt::Display for CachePadded<T> {
250    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
251        fmt::Display::fmt(&self.value, f)
252    }
253}
crossfire_utils/cache_padded.rs

crossfire_utils/
cache_padded.rs
