1 // Copyright 2016-2017 The Servo Project Developers. See the COPYRIGHT 2 // file at the top-level directory of this distribution and at 3 // http://rust-lang.org/COPYRIGHT. 4 // 5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or 6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license 7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your 8 // option. This file may not be copied, modified, or distributed 9 // except according to those terms. 10 11 //! A reduced fork of Firefox's malloc_size_of crate, for bundling with WebRender. 12 13 extern crate app_units; 14 extern crate euclid; 15 16 use std::hash::{BuildHasher, Hash}; 17 use std::mem::size_of; 18 use std::ops::Range; 19 use std::os::raw::c_void; 20 21 /// A C function that takes a pointer to a heap allocation and returns its size. 22 type VoidPtrToSizeFn = unsafe extern "C" fn(ptr: *const c_void) -> usize; 23 24 /// Operations used when measuring heap usage of data structures. 25 pub struct MallocSizeOfOps { 26 /// A function that returns the size of a heap allocation. 27 pub size_of_op: VoidPtrToSizeFn, 28 29 /// Like `size_of_op`, but can take an interior pointer. Optional because 30 /// not all allocators support this operation. If it's not provided, some 31 /// memory measurements will actually be computed estimates rather than 32 /// real and accurate measurements. 33 pub enclosing_size_of_op: Option<VoidPtrToSizeFn>, 34 } 35 36 impl MallocSizeOfOps { new( size_of: VoidPtrToSizeFn, malloc_enclosing_size_of: Option<VoidPtrToSizeFn>, ) -> Self37 pub fn new( 38 size_of: VoidPtrToSizeFn, 39 malloc_enclosing_size_of: Option<VoidPtrToSizeFn>, 40 ) -> Self { 41 MallocSizeOfOps { 42 size_of_op: size_of, 43 enclosing_size_of_op: malloc_enclosing_size_of, 44 } 45 } 46 47 /// Check if an allocation is empty. This relies on knowledge of how Rust 48 /// handles empty allocations, which may change in the future. is_empty<T: ?Sized>(ptr: *const T) -> bool49 fn is_empty<T: ?Sized>(ptr: *const T) -> bool { 50 // The correct condition is this: 51 // `ptr as usize <= ::std::mem::align_of::<T>()` 52 // But we can't call align_of() on a ?Sized T. So we approximate it 53 // with the following. 256 is large enough that it should always be 54 // larger than the required alignment, but small enough that it is 55 // always in the first page of memory and therefore not a legitimate 56 // address. 57 return ptr as *const usize as usize <= 256; 58 } 59 60 /// Call `size_of_op` on `ptr`, first checking that the allocation isn't 61 /// empty, because some types (such as `Vec`) utilize empty allocations. malloc_size_of<T: ?Sized>(&self, ptr: *const T) -> usize62 pub unsafe fn malloc_size_of<T: ?Sized>(&self, ptr: *const T) -> usize { 63 if MallocSizeOfOps::is_empty(ptr) { 64 0 65 } else { 66 (self.size_of_op)(ptr as *const c_void) 67 } 68 } 69 70 /// Is an `enclosing_size_of_op` available? has_malloc_enclosing_size_of(&self) -> bool71 pub fn has_malloc_enclosing_size_of(&self) -> bool { 72 self.enclosing_size_of_op.is_some() 73 } 74 75 /// Call `enclosing_size_of_op`, which must be available, on `ptr`, which 76 /// must not be empty. malloc_enclosing_size_of<T>(&self, ptr: *const T) -> usize77 pub unsafe fn malloc_enclosing_size_of<T>(&self, ptr: *const T) -> usize { 78 assert!(!MallocSizeOfOps::is_empty(ptr)); 79 (self.enclosing_size_of_op.unwrap())(ptr as *const c_void) 80 } 81 } 82 83 /// Trait for measuring the "deep" heap usage of a data structure. This is the 84 /// most commonly-used of the traits. 85 pub trait MallocSizeOf { 86 /// Measure the heap usage of all descendant heap-allocated structures, but 87 /// not the space taken up by the value itself. size_of(&self, ops: &mut MallocSizeOfOps) -> usize88 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize; 89 } 90 91 /// Trait for measuring the "shallow" heap usage of a container. 92 pub trait MallocShallowSizeOf { 93 /// Measure the heap usage of immediate heap-allocated descendant 94 /// structures, but not the space taken up by the value itself. Anything 95 /// beyond the immediate descendants must be measured separately, using 96 /// iteration. shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize97 fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize; 98 } 99 100 impl MallocSizeOf for String { size_of(&self, ops: &mut MallocSizeOfOps) -> usize101 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 102 unsafe { ops.malloc_size_of(self.as_ptr()) } 103 } 104 } 105 106 impl<T: ?Sized> MallocShallowSizeOf for Box<T> { shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize107 fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 108 unsafe { ops.malloc_size_of(&**self) } 109 } 110 } 111 112 impl<T: MallocSizeOf + ?Sized> MallocSizeOf for Box<T> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize113 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 114 self.shallow_size_of(ops) + (**self).size_of(ops) 115 } 116 } 117 118 impl MallocSizeOf for () { size_of(&self, _ops: &mut MallocSizeOfOps) -> usize119 fn size_of(&self, _ops: &mut MallocSizeOfOps) -> usize { 120 0 121 } 122 } 123 124 impl<T1, T2> MallocSizeOf for (T1, T2) 125 where 126 T1: MallocSizeOf, 127 T2: MallocSizeOf, 128 { size_of(&self, ops: &mut MallocSizeOfOps) -> usize129 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 130 self.0.size_of(ops) + self.1.size_of(ops) 131 } 132 } 133 134 impl<T1, T2, T3> MallocSizeOf for (T1, T2, T3) 135 where 136 T1: MallocSizeOf, 137 T2: MallocSizeOf, 138 T3: MallocSizeOf, 139 { size_of(&self, ops: &mut MallocSizeOfOps) -> usize140 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 141 self.0.size_of(ops) + self.1.size_of(ops) + self.2.size_of(ops) 142 } 143 } 144 145 impl<T1, T2, T3, T4> MallocSizeOf for (T1, T2, T3, T4) 146 where 147 T1: MallocSizeOf, 148 T2: MallocSizeOf, 149 T3: MallocSizeOf, 150 T4: MallocSizeOf, 151 { size_of(&self, ops: &mut MallocSizeOfOps) -> usize152 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 153 self.0.size_of(ops) + self.1.size_of(ops) + self.2.size_of(ops) + self.3.size_of(ops) 154 } 155 } 156 157 impl<T: MallocSizeOf> MallocSizeOf for Option<T> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize158 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 159 if let Some(val) = self.as_ref() { 160 val.size_of(ops) 161 } else { 162 0 163 } 164 } 165 } 166 167 impl<T: MallocSizeOf, E: MallocSizeOf> MallocSizeOf for Result<T, E> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize168 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 169 match *self { 170 Ok(ref x) => x.size_of(ops), 171 Err(ref e) => e.size_of(ops), 172 } 173 } 174 } 175 176 impl<T: MallocSizeOf + Copy> MallocSizeOf for std::cell::Cell<T> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize177 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 178 self.get().size_of(ops) 179 } 180 } 181 182 impl<T: MallocSizeOf> MallocSizeOf for std::cell::RefCell<T> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize183 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 184 self.borrow().size_of(ops) 185 } 186 } 187 188 impl<'a, B: ?Sized + ToOwned> MallocSizeOf for std::borrow::Cow<'a, B> 189 where 190 B::Owned: MallocSizeOf, 191 { size_of(&self, ops: &mut MallocSizeOfOps) -> usize192 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 193 match *self { 194 std::borrow::Cow::Borrowed(_) => 0, 195 std::borrow::Cow::Owned(ref b) => b.size_of(ops), 196 } 197 } 198 } 199 200 impl<T: MallocSizeOf> MallocSizeOf for [T] { size_of(&self, ops: &mut MallocSizeOfOps) -> usize201 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 202 let mut n = 0; 203 for elem in self.iter() { 204 n += elem.size_of(ops); 205 } 206 n 207 } 208 } 209 210 impl<T> MallocShallowSizeOf for Vec<T> { shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize211 fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 212 unsafe { ops.malloc_size_of(self.as_ptr()) } 213 } 214 } 215 216 impl<T: MallocSizeOf> MallocSizeOf for Vec<T> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize217 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 218 let mut n = self.shallow_size_of(ops); 219 for elem in self.iter() { 220 n += elem.size_of(ops); 221 } 222 n 223 } 224 } 225 226 macro_rules! malloc_size_of_hash_set { 227 ($ty:ty) => { 228 impl<T, S> MallocShallowSizeOf for $ty 229 where 230 T: Eq + Hash, 231 S: BuildHasher, 232 { 233 fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 234 if ops.has_malloc_enclosing_size_of() { 235 // The first value from the iterator gives us an interior pointer. 236 // `ops.malloc_enclosing_size_of()` then gives us the storage size. 237 // This assumes that the `HashSet`'s contents (values and hashes) 238 // are all stored in a single contiguous heap allocation. 239 self.iter() 240 .next() 241 .map_or(0, |t| unsafe { ops.malloc_enclosing_size_of(t) }) 242 } else { 243 // An estimate. 244 self.capacity() * (size_of::<T>() + size_of::<usize>()) 245 } 246 } 247 } 248 249 impl<T, S> MallocSizeOf for $ty 250 where 251 T: Eq + Hash + MallocSizeOf, 252 S: BuildHasher, 253 { 254 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 255 let mut n = self.shallow_size_of(ops); 256 for t in self.iter() { 257 n += t.size_of(ops); 258 } 259 n 260 } 261 } 262 }; 263 } 264 265 malloc_size_of_hash_set!(std::collections::HashSet<T, S>); 266 267 macro_rules! malloc_size_of_hash_map { 268 ($ty:ty) => { 269 impl<K, V, S> MallocShallowSizeOf for $ty 270 where 271 K: Eq + Hash, 272 S: BuildHasher, 273 { 274 fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 275 // See the implementation for std::collections::HashSet for details. 276 if ops.has_malloc_enclosing_size_of() { 277 self.values() 278 .next() 279 .map_or(0, |v| unsafe { ops.malloc_enclosing_size_of(v) }) 280 } else { 281 self.capacity() * (size_of::<V>() + size_of::<K>() + size_of::<usize>()) 282 } 283 } 284 } 285 286 impl<K, V, S> MallocSizeOf for $ty 287 where 288 K: Eq + Hash + MallocSizeOf, 289 V: MallocSizeOf, 290 S: BuildHasher, 291 { 292 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 293 let mut n = self.shallow_size_of(ops); 294 for (k, v) in self.iter() { 295 n += k.size_of(ops); 296 n += v.size_of(ops); 297 } 298 n 299 } 300 } 301 }; 302 } 303 304 malloc_size_of_hash_map!(std::collections::HashMap<K, V, S>); 305 306 // PhantomData is always 0. 307 impl<T> MallocSizeOf for std::marker::PhantomData<T> { size_of(&self, _ops: &mut MallocSizeOfOps) -> usize308 fn size_of(&self, _ops: &mut MallocSizeOfOps) -> usize { 309 0 310 } 311 } 312 313 impl<T: MallocSizeOf, Unit> MallocSizeOf for euclid::Length<T, Unit> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize314 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 315 self.0.size_of(ops) 316 } 317 } 318 319 impl<T: MallocSizeOf, Src, Dst> MallocSizeOf for euclid::TypedScale<T, Src, Dst> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize320 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 321 self.0.size_of(ops) 322 } 323 } 324 325 impl<T: MallocSizeOf, U> MallocSizeOf for euclid::TypedPoint2D<T, U> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize326 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 327 self.x.size_of(ops) + self.y.size_of(ops) 328 } 329 } 330 331 impl<T: MallocSizeOf, U> MallocSizeOf for euclid::TypedRect<T, U> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize332 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 333 self.origin.size_of(ops) + self.size.size_of(ops) 334 } 335 } 336 337 impl<T: MallocSizeOf, U> MallocSizeOf for euclid::TypedSideOffsets2D<T, U> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize338 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 339 self.top.size_of(ops) + 340 self.right.size_of(ops) + 341 self.bottom.size_of(ops) + 342 self.left.size_of(ops) 343 } 344 } 345 346 impl<T: MallocSizeOf, U> MallocSizeOf for euclid::TypedSize2D<T, U> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize347 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 348 self.width.size_of(ops) + self.height.size_of(ops) 349 } 350 } 351 352 impl<T: MallocSizeOf, Src, Dst> MallocSizeOf for euclid::TypedTransform2D<T, Src, Dst> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize353 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 354 self.m11.size_of(ops) + 355 self.m12.size_of(ops) + 356 self.m21.size_of(ops) + 357 self.m22.size_of(ops) + 358 self.m31.size_of(ops) + 359 self.m32.size_of(ops) 360 } 361 } 362 363 impl<T: MallocSizeOf, Src, Dst> MallocSizeOf for euclid::TypedTransform3D<T, Src, Dst> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize364 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 365 self.m11.size_of(ops) + 366 self.m12.size_of(ops) + 367 self.m13.size_of(ops) + 368 self.m14.size_of(ops) + 369 self.m21.size_of(ops) + 370 self.m22.size_of(ops) + 371 self.m23.size_of(ops) + 372 self.m24.size_of(ops) + 373 self.m31.size_of(ops) + 374 self.m32.size_of(ops) + 375 self.m33.size_of(ops) + 376 self.m34.size_of(ops) + 377 self.m41.size_of(ops) + 378 self.m42.size_of(ops) + 379 self.m43.size_of(ops) + 380 self.m44.size_of(ops) 381 } 382 } 383 384 impl<T: MallocSizeOf, U> MallocSizeOf for euclid::TypedVector2D<T, U> { size_of(&self, ops: &mut MallocSizeOfOps) -> usize385 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize { 386 self.x.size_of(ops) + self.y.size_of(ops) 387 } 388 } 389 390 /// For use on types where size_of() returns 0. 391 #[macro_export] 392 macro_rules! malloc_size_of_is_0( 393 ($($ty:ty),+) => ( 394 $( 395 impl $crate::MallocSizeOf for $ty { 396 #[inline(always)] 397 fn size_of(&self, _: &mut $crate::MallocSizeOfOps) -> usize { 398 0 399 } 400 } 401 )+ 402 ); 403 ($($ty:ident<$($gen:ident),+>),+) => ( 404 $( 405 impl<$($gen: $crate::MallocSizeOf),+> $crate::MallocSizeOf for $ty<$($gen),+> { 406 #[inline(always)] 407 fn size_of(&self, _: &mut $crate::MallocSizeOfOps) -> usize { 408 0 409 } 410 } 411 )+ 412 ); 413 ); 414 415 malloc_size_of_is_0!(bool, char, str); 416 malloc_size_of_is_0!(u8, u16, u32, u64, u128, usize); 417 malloc_size_of_is_0!(i8, i16, i32, i64, i128, isize); 418 malloc_size_of_is_0!(f32, f64); 419 420 malloc_size_of_is_0!(std::sync::atomic::AtomicBool); 421 malloc_size_of_is_0!(std::sync::atomic::AtomicIsize); 422 malloc_size_of_is_0!(std::sync::atomic::AtomicUsize); 423 424 malloc_size_of_is_0!(std::num::NonZeroUsize); 425 malloc_size_of_is_0!(std::num::NonZeroU32); 426 427 malloc_size_of_is_0!(std::time::Duration); 428 malloc_size_of_is_0!(std::time::Instant); 429 malloc_size_of_is_0!(std::time::SystemTime); 430 431 malloc_size_of_is_0!(Range<u8>, Range<u16>, Range<u32>, Range<u64>, Range<usize>); 432 malloc_size_of_is_0!(Range<i8>, Range<i16>, Range<i32>, Range<i64>, Range<isize>); 433 malloc_size_of_is_0!(Range<f32>, Range<f64>); 434 435 malloc_size_of_is_0!(app_units::Au); 436