src/liballoc/heap.rs

   1 // Copyright 2014-2015 The Rust 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 // FIXME: #13996: mark the `allocate` and `reallocate` return value as `noalias`
  12
  13 /// Return a pointer to `size` bytes of memory aligned to `align`.
  14 ///
  15 /// On failure, return a null pointer.
  16 ///
  17 /// Behavior is undefined if the requested size is 0 or the alignment is not a
  18 /// power of 2. The alignment must be no larger than the largest supported page
  19 /// size on the platform.
  20 #[inline]
  21 pub unsafe fn allocate(size: usize, align: usize) -> *mut u8 {
  22     imp::allocate(size, align)
  23 }
  24
  25 /// Resize the allocation referenced by `ptr` to `size` bytes.
  26 ///
  27 /// On failure, return a null pointer and leave the original allocation intact.
  28 ///
  29 /// If the allocation was relocated, the memory at the passed-in pointer is
  30 /// undefined after the call.
  31 ///
  32 /// Behavior is undefined if the requested size is 0 or the alignment is not a
  33 /// power of 2. The alignment must be no larger than the largest supported page
  34 /// size on the platform.
  35 ///
  36 /// The `old_size` and `align` parameters are the parameters that were used to
  37 /// create the allocation referenced by `ptr`. The `old_size` parameter may be
  38 /// any value in range_inclusive(requested_size, usable_size).
  39 #[inline]
  40 pub unsafe fn reallocate(ptr: *mut u8, old_size: usize, size: usize, align: usize) -> *mut u8 {
  41     imp::reallocate(ptr, old_size, size, align)
  42 }
  43
  44 /// Resize the allocation referenced by `ptr` to `size` bytes.
  45 ///
  46 /// If the operation succeeds, it returns `usable_size(size, align)` and if it
  47 /// fails (or is a no-op) it returns `usable_size(old_size, align)`.
  48 ///
  49 /// Behavior is undefined if the requested size is 0 or the alignment is not a
  50 /// power of 2. The alignment must be no larger than the largest supported page
  51 /// size on the platform.
  52 ///
  53 /// The `old_size` and `align` parameters are the parameters that were used to
  54 /// create the allocation referenced by `ptr`. The `old_size` parameter may be
  55 /// any value in range_inclusive(requested_size, usable_size).
  56 #[inline]
  57 pub unsafe fn reallocate_inplace(ptr: *mut u8, old_size: usize, size: usize,
  58                                  align: usize) -> usize {
  59     imp::reallocate_inplace(ptr, old_size, size, align)
  60 }
  61
  62 /// Deallocates the memory referenced by `ptr`.
  63 ///
  64 /// The `ptr` parameter must not be null.
  65 ///
  66 /// The `old_size` and `align` parameters are the parameters that were used to
  67 /// create the allocation referenced by `ptr`. The `old_size` parameter may be
  68 /// any value in range_inclusive(requested_size, usable_size).
  69 #[inline]
  70 pub unsafe fn deallocate(ptr: *mut u8, old_size: usize, align: usize) {
  71     imp::deallocate(ptr, old_size, align)
  72 }
  73
  74 /// Returns the usable size of an allocation created with the specified the
  75 /// `size` and `align`.
  76 #[inline]
  77 pub fn usable_size(size: usize, align: usize) -> usize {
  78     imp::usable_size(size, align)
  79 }
  80
  81 /// Prints implementation-defined allocator statistics.
  82 ///
  83 /// These statistics may be inconsistent if other threads use the allocator
  84 /// during the call.
  85 #[unstable(feature = "alloc")]
  86 pub fn stats_print() {
  87     imp::stats_print();
  88 }
  89
  90 /// An arbitrary non-null address to represent zero-size allocations.
  91 ///
  92 /// This preserves the non-null invariant for types like `Box<T>`. The address may overlap with
  93 /// non-zero-size memory allocations.
  94 pub const EMPTY: *mut () = 0x1 as *mut ();
  95
  96 /// The allocator for unique pointers.
  97 #[cfg(not(test))]
  98 #[lang="exchange_malloc"]
  99 #[inline]
 100 unsafe fn exchange_malloc(size: usize, align: usize) -> *mut u8 {
 101     if size == 0 {
 102         EMPTY as *mut u8
 103     } else {
 104         let ptr = allocate(size, align);
 105         if ptr.is_null() { ::oom() }
 106         ptr
 107     }
 108 }
 109
 110 #[cfg(not(test))]
 111 #[lang="exchange_free"]
 112 #[inline]
 113 unsafe fn exchange_free(ptr: *mut u8, old_size: usize, align: usize) {
 114     deallocate(ptr, old_size, align);
 115 }
 116
 117 // The minimum alignment guaranteed by the architecture. This value is used to
 118 // add fast paths for low alignment values. In practice, the alignment is a
 119 // constant at the call site and the branch will be optimized out.
 120 #[cfg(all(not(feature = "external_funcs"),
 121           not(feature = "external_crate"),
 122           any(target_arch = "arm",
 123               target_arch = "mips",
 124               target_arch = "mipsel",
 125               target_arch = "powerpc")))]
 126 const MIN_ALIGN: usize = 8;
 127 #[cfg(all(not(feature = "external_funcs"),
 128           not(feature = "external_crate"),
 129           any(target_arch = "x86",
 130               target_arch = "x86_64",
 131               target_arch = "aarch64")))]
 132 const MIN_ALIGN: usize = 16;
 133
 134 #[cfg(feature = "external_funcs")]
 135 mod imp {
 136     extern {
 137         fn rust_allocate(size: usize, align: usize) -> *mut u8;
 138         fn rust_deallocate(ptr: *mut u8, old_size: usize, align: usize);
 139         fn rust_reallocate(ptr: *mut u8, old_size: usize, size: usize, align: usize) -> *mut u8;
 140         fn rust_reallocate_inplace(ptr: *mut u8, old_size: usize, size: usize,
 141                                    align: usize) -> usize;
 142         fn rust_usable_size(size: usize, align: usize) -> usize;
 143         fn rust_stats_print();
 144     }
 145
 146     #[inline]
 147     pub unsafe fn allocate(size: usize, align: usize) -> *mut u8 {
 148         rust_allocate(size, align)
 149     }
 150
 151     #[inline]
 152     pub unsafe fn deallocate(ptr: *mut u8, old_size: usize, align: usize) {
 153         rust_deallocate(ptr, old_size, align)
 154     }
 155
 156     #[inline]
 157     pub unsafe fn reallocate(ptr: *mut u8, old_size: usize, size: usize, align: usize) -> *mut u8 {
 158         rust_reallocate(ptr, old_size, size, align)
 159     }
 160
 161     #[inline]
 162     pub unsafe fn reallocate_inplace(ptr: *mut u8, old_size: usize, size: usize,
 163                                      align: usize) -> usize {
 164         rust_reallocate_inplace(ptr, old_size, size, align)
 165     }
 166
 167     #[inline]
 168     pub fn usable_size(size: usize, align: usize) -> usize {
 169         unsafe { rust_usable_size(size, align) }
 170     }
 171
 172     #[inline]
 173     pub fn stats_print() {
 174         unsafe { rust_stats_print() }
 175     }
 176 }
 177
 178 #[cfg(feature = "external_crate")]
 179 mod imp {
 180     extern crate external;
 181     pub use self::external::{allocate, deallocate, reallocate_inplace, reallocate};
 182     pub use self::external::{usable_size, stats_print};
 183 }
 184
 185 #[cfg(all(not(feature = "external_funcs"),
 186           not(feature = "external_crate"),
 187           jemalloc))]
 188 mod imp {
 189     use core::option::Option;
 190     use core::option::Option::None;
 191     use core::ptr::{null_mut, null};
 192     use core::num::Int;
 193     use libc::{c_char, c_int, c_void, size_t};
 194     use super::MIN_ALIGN;
 195
 196     #[link(name = "jemalloc", kind = "static")]
 197     #[cfg(not(test))]
 198     extern {}
 199
 200     extern {
 201         #[allocator]
 202         fn je_mallocx(size: size_t, flags: c_int) -> *mut c_void;
 203         fn je_rallocx(ptr: *mut c_void, size: size_t, flags: c_int) -> *mut c_void;
 204         fn je_xallocx(ptr: *mut c_void, size: size_t, extra: size_t, flags: c_int) -> size_t;
 205         fn je_sdallocx(ptr: *mut c_void, size: size_t, flags: c_int);
 206         fn je_nallocx(size: size_t, flags: c_int) -> size_t;
 207         fn je_malloc_stats_print(write_cb: Option<extern "C" fn(cbopaque: *mut c_void,
 208                                                                 *const c_char)>,
 209                                  cbopaque: *mut c_void,
 210                                  opts: *const c_char);
 211     }
 212
 213     // -lpthread needs to occur after -ljemalloc, the earlier argument isn't enough
 214     #[cfg(all(not(windows), not(target_os = "android")))]
 215     #[link(name = "pthread")]
 216     extern {}
 217
 218     // MALLOCX_ALIGN(a) macro
 219     #[inline(always)]
 220     fn mallocx_align(a: usize) -> c_int { a.trailing_zeros() as c_int }
 221
 222     #[inline(always)]
 223     fn align_to_flags(align: usize) -> c_int {
 224         if align <= MIN_ALIGN { 0 } else { mallocx_align(align) }
 225     }
 226
 227     #[inline]
 228     pub unsafe fn allocate(size: usize, align: usize) -> *mut u8 {
 229         let flags = align_to_flags(align);
 230         je_mallocx(size as size_t, flags) as *mut u8
 231     }
 232
 233     #[inline]
 234     pub unsafe fn reallocate(ptr: *mut u8, _old_size: usize, size: usize, align: usize) -> *mut u8 {
 235         let flags = align_to_flags(align);
 236         je_rallocx(ptr as *mut c_void, size as size_t, flags) as *mut u8
 237     }
 238
 239     #[inline]
 240     pub unsafe fn reallocate_inplace(ptr: *mut u8, _old_size: usize, size: usize,
 241                                      align: usize) -> usize {
 242         let flags = align_to_flags(align);
 243         je_xallocx(ptr as *mut c_void, size as size_t, 0, flags) as usize
 244     }
 245
 246     #[inline]
 247     pub unsafe fn deallocate(ptr: *mut u8, old_size: usize, align: usize) {
 248         let flags = align_to_flags(align);
 249         je_sdallocx(ptr as *mut c_void, old_size as size_t, flags)
 250     }
 251
 252     #[inline]
 253     pub fn usable_size(size: usize, align: usize) -> usize {
 254         let flags = align_to_flags(align);
 255         unsafe { je_nallocx(size as size_t, flags) as usize }
 256     }
 257
 258     pub fn stats_print() {
 259         unsafe {
 260             je_malloc_stats_print(None, null_mut(), null())
 261         }
 262     }
 263 }
 264
 265 #[cfg(all(not(feature = "external_funcs"),
 266           not(feature = "external_crate"),
 267           not(jemalloc),
 268           unix))]
 269 mod imp {
 270     use core::cmp;
 271     use core::ptr;
 272     use libc;
 273     use super::MIN_ALIGN;
 274
 275     extern {
 276         fn posix_memalign(memptr: *mut *mut libc::c_void,
 277                           align: libc::size_t,
 278                           size: libc::size_t) -> libc::c_int;
 279     }
 280
 281     #[inline]
 282     pub unsafe fn allocate(size: usize, align: usize) -> *mut u8 {
 283         if align <= MIN_ALIGN {
 284             libc::malloc(size as libc::size_t) as *mut u8
 285         } else {
 286             let mut out = ptr::null_mut();
 287             let ret = posix_memalign(&mut out,
 288                                      align as libc::size_t,
 289                                      size as libc::size_t);
 290             if ret != 0 {
 291                 ptr::null_mut()
 292             } else {
 293                 out as *mut u8
 294             }
 295         }
 296     }
 297
 298     #[inline]
 299     pub unsafe fn reallocate(ptr: *mut u8, old_size: usize, size: usize, align: usize) -> *mut u8 {
 300         if align <= MIN_ALIGN {
 301             libc::realloc(ptr as *mut libc::c_void, size as libc::size_t) as *mut u8
 302         } else {
 303             let new_ptr = allocate(size, align);
 304             ptr::copy(new_ptr, ptr, cmp::min(size, old_size));
 305             deallocate(ptr, old_size, align);
 306             new_ptr
 307         }
 308     }
 309
 310     #[inline]
 311     pub unsafe fn reallocate_inplace(_ptr: *mut u8, old_size: usize, _size: usize,
 312                                      _align: usize) -> usize {
 313         old_size
 314     }
 315
 316     #[inline]
 317     pub unsafe fn deallocate(ptr: *mut u8, _old_size: usize, _align: usize) {
 318         libc::free(ptr as *mut libc::c_void)
 319     }
 320
 321     #[inline]
 322     pub fn usable_size(size: usize, _align: usize) -> usize {
 323         size
 324     }
 325
 326     pub fn stats_print() {}
 327 }
 328
 329 #[cfg(all(not(feature = "external_funcs"),
 330           not(feature = "external_crate"),
 331           not(jemalloc),
 332           windows))]
 333 mod imp {
 334     use libc::{c_void, size_t};
 335     use libc;
 336     use super::MIN_ALIGN;
 337
 338     extern {
 339         fn _aligned_malloc(size: size_t, align: size_t) -> *mut c_void;
 340         fn _aligned_realloc(block: *mut c_void, size: size_t,
 341                             align: size_t) -> *mut c_void;
 342         fn _aligned_free(ptr: *mut c_void);
 343     }
 344
 345     #[inline]
 346     pub unsafe fn allocate(size: usize, align: usize) -> *mut u8 {
 347         if align <= MIN_ALIGN {
 348             libc::malloc(size as size_t) as *mut u8
 349         } else {
 350             _aligned_malloc(size as size_t, align as size_t) as *mut u8
 351         }
 352     }
 353
 354     #[inline]
 355     pub unsafe fn reallocate(ptr: *mut u8, _old_size: usize, size: usize, align: usize) -> *mut u8 {
 356         if align <= MIN_ALIGN {
 357             libc::realloc(ptr as *mut c_void, size as size_t) as *mut u8
 358         } else {
 359             _aligned_realloc(ptr as *mut c_void, size as size_t, align as size_t) as *mut u8
 360         }
 361     }
 362
 363     #[inline]
 364     pub unsafe fn reallocate_inplace(_ptr: *mut u8, old_size: usize, _size: usize,
 365                                      _align: usize) -> usize {
 366         old_size
 367     }
 368
 369     #[inline]
 370     pub unsafe fn deallocate(ptr: *mut u8, _old_size: usize, align: usize) {
 371         if align <= MIN_ALIGN {
 372             libc::free(ptr as *mut libc::c_void)
 373         } else {
 374             _aligned_free(ptr as *mut c_void)
 375         }
 376     }
 377
 378     #[inline]
 379     pub fn usable_size(size: usize, _align: usize) -> usize {
 380         size
 381     }
 382
 383     pub fn stats_print() {}
 384 }
 385
 386 #[cfg(test)]
 387 mod test {
 388     extern crate test;
 389     use self::test::Bencher;
 390     use boxed::Box;
 391     use heap;
 392
 393     #[test]
 394     fn basic_reallocate_inplace_noop() {
 395         unsafe {
 396             let size = 4000;
 397             let ptr = heap::allocate(size, 8);
 398             if ptr.is_null() { ::oom() }
 399             let ret = heap::reallocate_inplace(ptr, size, size, 8);
 400             heap::deallocate(ptr, size, 8);
 401             assert_eq!(ret, heap::usable_size(size, 8));
 402         }
 403     }
 404
 405     #[bench]
 406     fn alloc_owned_small(b: &mut Bencher) {
 407         b.iter(|| {
 408             let _: Box<_> = box 10;
 409         })
 410     }
 411 }