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, riscv32, riscv64, 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 | #[cfg_attr ( |
80 | any( |
81 | target_arch = "x86_64" , |
82 | target_arch = "aarch64" , |
83 | target_arch = "powerpc64" , |
84 | ), |
85 | repr(align(128)) |
86 | )] |
87 | // arm, mips, mips64, riscv64, sparc, and hexagon have 32-byte cache line size. |
88 | // |
89 | // Sources: |
90 | // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_arm.go#L7 |
91 | // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips.go#L7 |
92 | // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mipsle.go#L7 |
93 | // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_mips64x.go#L9 |
94 | // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_riscv64.go#L7 |
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 | // |
98 | // riscv32 is assumed not to exceed the cache line size of riscv64. |
99 | #[cfg_attr ( |
100 | any( |
101 | target_arch = "arm" , |
102 | target_arch = "mips" , |
103 | target_arch = "mips64" , |
104 | target_arch = "riscv32" , |
105 | target_arch = "riscv64" , |
106 | target_arch = "sparc" , |
107 | target_arch = "hexagon" , |
108 | ), |
109 | repr(align(32)) |
110 | )] |
111 | // m68k has 16-byte cache line size. |
112 | // |
113 | // Sources: |
114 | // - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/m68k/include/asm/cache.h#L9 |
115 | #[cfg_attr (target_arch = "m68k" , repr(align(16)))] |
116 | // s390x has 256-byte cache line size. |
117 | // |
118 | // Sources: |
119 | // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_s390x.go#L7 |
120 | // - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/s390/include/asm/cache.h#L13 |
121 | #[cfg_attr (target_arch = "s390x" , repr(align(256)))] |
122 | // x86, wasm, and sparc64 have 64-byte cache line size. |
123 | // |
124 | // Sources: |
125 | // - https://github.com/golang/go/blob/dda2991c2ea0c5914714469c4defc2562a907230/src/internal/cpu/cpu_x86.go#L9 |
126 | // - https://github.com/golang/go/blob/3dd58676054223962cd915bb0934d1f9f489d4d2/src/internal/cpu/cpu_wasm.go#L7 |
127 | // - https://github.com/torvalds/linux/blob/3516bd729358a2a9b090c1905bd2a3fa926e24c6/arch/sparc/include/asm/cache.h#L19 |
128 | // |
129 | // All others are assumed to have 64-byte cache line size. |
130 | #[cfg_attr ( |
131 | not(any( |
132 | target_arch = "x86_64" , |
133 | target_arch = "aarch64" , |
134 | target_arch = "powerpc64" , |
135 | target_arch = "arm" , |
136 | target_arch = "mips" , |
137 | target_arch = "mips64" , |
138 | target_arch = "riscv32" , |
139 | target_arch = "riscv64" , |
140 | target_arch = "sparc" , |
141 | target_arch = "hexagon" , |
142 | target_arch = "m68k" , |
143 | target_arch = "s390x" , |
144 | )), |
145 | repr(align(64)) |
146 | )] |
147 | pub struct CachePadded<T> { |
148 | value: T, |
149 | } |
150 | |
151 | unsafe impl<T: Send> Send for CachePadded<T> {} |
152 | unsafe impl<T: Sync> Sync for CachePadded<T> {} |
153 | |
154 | impl<T> CachePadded<T> { |
155 | /// Pads and aligns a value to the length of a cache line. |
156 | /// |
157 | /// # Examples |
158 | /// |
159 | /// ``` |
160 | /// use crossbeam_utils::CachePadded; |
161 | /// |
162 | /// let padded_value = CachePadded::new(1); |
163 | /// ``` |
164 | pub const fn new(t: T) -> CachePadded<T> { |
165 | CachePadded::<T> { value: t } |
166 | } |
167 | |
168 | /// Returns the inner value. |
169 | /// |
170 | /// # Examples |
171 | /// |
172 | /// ``` |
173 | /// use crossbeam_utils::CachePadded; |
174 | /// |
175 | /// let padded_value = CachePadded::new(7); |
176 | /// let value = padded_value.into_inner(); |
177 | /// assert_eq!(value, 7); |
178 | /// ``` |
179 | pub fn into_inner(self) -> T { |
180 | self.value |
181 | } |
182 | } |
183 | |
184 | impl<T> Deref for CachePadded<T> { |
185 | type Target = T; |
186 | |
187 | fn deref(&self) -> &T { |
188 | &self.value |
189 | } |
190 | } |
191 | |
192 | impl<T> DerefMut for CachePadded<T> { |
193 | fn deref_mut(&mut self) -> &mut T { |
194 | &mut self.value |
195 | } |
196 | } |
197 | |
198 | impl<T: fmt::Debug> fmt::Debug for CachePadded<T> { |
199 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
200 | f&mut DebugStruct<'_, '_>.debug_struct("CachePadded" ) |
201 | .field(name:"value" , &self.value) |
202 | .finish() |
203 | } |
204 | } |
205 | |
206 | impl<T> From<T> for CachePadded<T> { |
207 | fn from(t: T) -> Self { |
208 | CachePadded::new(t) |
209 | } |
210 | } |
211 | |