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 | } |
210 | |