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