kernel/sync/
cache_padded.rs

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

kernel/sync/
cache_padded.rs
