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               target_arch = "powerpc")))]
 124 const MIN_ALIGN: uint = 8;
 125 #[cfg(all(not(feature = "external_funcs"),
 126           not(feature = "external_crate"),
 127           any(target_arch = "x86",
 128               target_arch = "x86_64",
 129               target_arch = "aarch64")))]
 130 const MIN_ALIGN: uint = 16;
 131
 132 #[cfg(feature = "external_funcs")]
 133 mod imp {
 134     extern {
 135         fn rust_allocate(size: uint, align: uint) -> *mut u8;
 136         fn rust_deallocate(ptr: *mut u8, old_size: uint, align: uint);
 137         fn rust_reallocate(ptr: *mut u8, old_size: uint, size: uint, align: uint) -> *mut u8;
 138         fn rust_reallocate_inplace(ptr: *mut u8, old_size: uint, size: uint,
 139                                    align: uint) -> uint;
 140         fn rust_usable_size(size: uint, align: uint) -> uint;
 141         fn rust_stats_print();
 142     }
 143
 144     #[inline]
 145     pub unsafe fn allocate(size: uint, align: uint) -> *mut u8 {
 146         rust_allocate(size, align)
 147     }
 148
 149     #[inline]
 150     pub unsafe fn deallocate(ptr: *mut u8, old_size: uint, align: uint) {
 151         rust_deallocate(ptr, old_size, align)
 152     }
 153
 154     #[inline]
 155     pub unsafe fn reallocate(ptr: *mut u8, old_size: uint, size: uint, align: uint) -> *mut u8 {
 156         rust_reallocate(ptr, old_size, size, align)
 157     }
 158
 159     #[inline]
 160     pub unsafe fn reallocate_inplace(ptr: *mut u8, old_size: uint, size: uint,
 161                                      align: uint) -> uint {
 162         rust_reallocate_inplace(ptr, old_size, size, align)
 163     }
 164
 165     #[inline]
 166     pub fn usable_size(size: uint, align: uint) -> uint {
 167         unsafe { rust_usable_size(size, align) }
 168     }
 169
 170     #[inline]
 171     pub fn stats_print() {
 172         unsafe { rust_stats_print() }
 173     }
 174 }
 175
 176 #[cfg(feature = "external_crate")]
 177 mod imp {
 178     extern crate external;
 179     pub use self::external::{allocate, deallocate, reallocate_inplace, reallocate};
 180     pub use self::external::{usable_size, stats_print};
 181 }
 182
 183 #[cfg(all(not(feature = "external_funcs"),
 184           not(feature = "external_crate"),
 185           jemalloc))]
 186 mod imp {
 187     use core::option::Option;
 188     use core::option::Option::None;
 189     use core::ptr::{null_mut, null};
 190     use core::num::Int;
 191     use libc::{c_char, c_int, c_void, size_t};
 192     use super::MIN_ALIGN;
 193
 194     #[link(name = "jemalloc", kind = "static")]
 195     #[cfg(not(test))]
 196     extern {}
 197
 198     extern {
 199         fn je_mallocx(size: size_t, flags: c_int) -> *mut c_void;
 200         fn je_rallocx(ptr: *mut c_void, size: size_t, flags: c_int) -> *mut c_void;
 201         fn je_xallocx(ptr: *mut c_void, size: size_t, extra: size_t, flags: c_int) -> size_t;
 202         fn je_sdallocx(ptr: *mut c_void, size: size_t, flags: c_int);
 203         fn je_nallocx(size: size_t, flags: c_int) -> size_t;
 204         fn je_malloc_stats_print(write_cb: Option<extern "C" fn(cbopaque: *mut c_void,
 205                                                                 *const c_char)>,
 206                                  cbopaque: *mut c_void,
 207                                  opts: *const c_char);
 208     }
 209
 210     // -lpthread needs to occur after -ljemalloc, the earlier argument isn't enough
 211     #[cfg(all(not(windows), not(target_os = "android")))]
 212     #[link(name = "pthread")]
 213     extern {}
 214
 215     // MALLOCX_ALIGN(a) macro
 216     #[inline(always)]
 217     fn mallocx_align(a: uint) -> c_int { a.trailing_zeros() as c_int }
 218
 219     #[inline(always)]
 220     fn align_to_flags(align: uint) -> c_int {
 221         if align <= MIN_ALIGN { 0 } else { mallocx_align(align) }
 222     }
 223
 224     #[inline]
 225     pub unsafe fn allocate(size: uint, align: uint) -> *mut u8 {
 226         let flags = align_to_flags(align);
 227         je_mallocx(size as size_t, flags) as *mut u8
 228     }
 229
 230     #[inline]
 231     pub unsafe fn reallocate(ptr: *mut u8, _old_size: uint, size: uint, align: uint) -> *mut u8 {
 232         let flags = align_to_flags(align);
 233         je_rallocx(ptr as *mut c_void, size as size_t, flags) as *mut u8
 234     }
 235
 236     #[inline]
 237     pub unsafe fn reallocate_inplace(ptr: *mut u8, _old_size: uint, size: uint,
 238                                      align: uint) -> uint {
 239         let flags = align_to_flags(align);
 240         je_xallocx(ptr as *mut c_void, size as size_t, 0, flags) as uint
 241     }
 242
 243     #[inline]
 244     pub unsafe fn deallocate(ptr: *mut u8, old_size: uint, align: uint) {
 245         let flags = align_to_flags(align);
 246         je_sdallocx(ptr as *mut c_void, old_size as size_t, flags)
 247     }
 248
 249     #[inline]
 250     pub fn usable_size(size: uint, align: uint) -> uint {
 251         let flags = align_to_flags(align);
 252         unsafe { je_nallocx(size as size_t, flags) as uint }
 253     }
 254
 255     pub fn stats_print() {
 256         unsafe {
 257             je_malloc_stats_print(None, null_mut(), null())
 258         }
 259     }
 260 }
 261
 262 #[cfg(all(not(feature = "external_funcs"),
 263           not(feature = "external_crate"),
 264           not(jemalloc),
 265           unix))]
 266 mod imp {
 267     use core::cmp;
 268     use core::ptr;
 269     use libc;
 270     use super::MIN_ALIGN;
 271
 272     extern {
 273         fn posix_memalign(memptr: *mut *mut libc::c_void,
 274                           align: libc::size_t,
 275                           size: libc::size_t) -> libc::c_int;
 276     }
 277
 278     #[inline]
 279     pub unsafe fn allocate(size: uint, align: uint) -> *mut u8 {
 280         if align <= MIN_ALIGN {
 281             libc::malloc(size as libc::size_t) as *mut u8
 282         } else {
 283             let mut out = 0 as *mut libc::c_void;
 284             let ret = posix_memalign(&mut out,
 285                                      align as libc::size_t,
 286                                      size as libc::size_t);
 287             if ret != 0 {
 288                 ptr::null_mut()
 289             } else {
 290                 out as *mut u8
 291             }
 292         }
 293     }
 294
 295     #[inline]
 296     pub unsafe fn reallocate(ptr: *mut u8, old_size: uint, size: uint, align: uint) -> *mut u8 {
 297         if align <= MIN_ALIGN {
 298             libc::realloc(ptr as *mut libc::c_void, size as libc::size_t) as *mut u8
 299         } else {
 300             let new_ptr = allocate(size, align);
 301             ptr::copy_memory(new_ptr, ptr, cmp::min(size, old_size));
 302             deallocate(ptr, old_size, align);
 303             new_ptr
 304         }
 305     }
 306
 307     #[inline]
 308     pub unsafe fn reallocate_inplace(_ptr: *mut u8, old_size: uint, _size: uint,
 309                                      _align: uint) -> uint {
 310         old_size
 311     }
 312
 313     #[inline]
 314     pub unsafe fn deallocate(ptr: *mut u8, _old_size: uint, _align: uint) {
 315         libc::free(ptr as *mut libc::c_void)
 316     }
 317
 318     #[inline]
 319     pub fn usable_size(size: uint, _align: uint) -> uint {
 320         size
 321     }
 322
 323     pub fn stats_print() {}
 324 }
 325
 326 #[cfg(all(not(feature = "external_funcs"),
 327           not(feature = "external_crate"),
 328           not(jemalloc),
 329           windows))]
 330 mod imp {
 331     use libc::{c_void, size_t};
 332     use libc;
 333     use super::MIN_ALIGN;
 334
 335     extern {
 336         fn _aligned_malloc(size: size_t, align: size_t) -> *mut c_void;
 337         fn _aligned_realloc(block: *mut c_void, size: size_t,
 338                             align: size_t) -> *mut c_void;
 339         fn _aligned_free(ptr: *mut c_void);
 340     }
 341
 342     #[inline]
 343     pub unsafe fn allocate(size: uint, align: uint) -> *mut u8 {
 344         if align <= MIN_ALIGN {
 345             libc::malloc(size as size_t) as *mut u8
 346         } else {
 347             _aligned_malloc(size as size_t, align as size_t) as *mut u8
 348         }
 349     }
 350
 351     #[inline]
 352     pub unsafe fn reallocate(ptr: *mut u8, _old_size: uint, size: uint, align: uint) -> *mut u8 {
 353         if align <= MIN_ALIGN {
 354             libc::realloc(ptr as *mut c_void, size as size_t) as *mut u8
 355         } else {
 356             _aligned_realloc(ptr as *mut c_void, size as size_t, align as size_t) as *mut u8
 357         }
 358     }
 359
 360     #[inline]
 361     pub unsafe fn reallocate_inplace(_ptr: *mut u8, old_size: uint, _size: uint,
 362                                      _align: uint) -> uint {
 363         old_size
 364     }
 365
 366     #[inline]
 367     pub unsafe fn deallocate(ptr: *mut u8, _old_size: uint, align: uint) {
 368         if align <= MIN_ALIGN {
 369             libc::free(ptr as *mut libc::c_void)
 370         } else {
 371             _aligned_free(ptr as *mut c_void)
 372         }
 373     }
 374
 375     #[inline]
 376     pub fn usable_size(size: uint, _align: uint) -> uint {
 377         size
 378     }
 379
 380     pub fn stats_print() {}
 381 }
 382
 383 #[cfg(test)]
 384 mod test {
 385     extern crate test;
 386     use self::test::Bencher;
 387     use core::ptr::PtrExt;
 388     use heap;
 389
 390     #[test]
 391     fn basic_reallocate_inplace_noop() {
 392         unsafe {
 393             let size = 4000;
 394             let ptr = heap::allocate(size, 8);
 395             if ptr.is_null() { ::oom() }
 396             let ret = heap::reallocate_inplace(ptr, size, size, 8);
 397             heap::deallocate(ptr, size, 8);
 398             assert_eq!(ret, heap::usable_size(size, 8));
 399         }
 400     }
 401
 402     #[bench]
 403     fn alloc_owned_small(b: &mut Bencher) {
 404         b.iter(|| {
 405             box 10i
 406         })
 407     }
 408 }