src/libarena/lib.rs

   1 // Copyright 2012-2014 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 //! The arena, a fast but limited type of allocator.
  12 //!
  13 //! Arenas are a type of allocator that destroy the objects within, all at
  14 //! once, once the arena itself is destroyed. They do not support deallocation
  15 //! of individual objects while the arena itself is still alive. The benefit
  16 //! of an arena is very fast allocation; just a pointer bump.
  17 //!
  18 //! This crate has two arenas implemented: `TypedArena`, which is a simpler
  19 //! arena but can only hold objects of a single type, and `Arena`, which is a
  20 //! more complex, slower arena which can hold objects of any type.
  21
  22 #![crate_name = "arena"]
  23 #![experimental]
  24 #![crate_type = "rlib"]
  25 #![crate_type = "dylib"]
  26 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  27        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  28        html_root_url = "http://doc.rust-lang.org/nightly/")]
  29
  30 #![feature(unsafe_destructor)]
  31 #![feature(unboxed_closures)]
  32 #![allow(missing_docs)]
  33
  34 extern crate alloc;
  35
  36 use std::cell::{Cell, RefCell};
  37 use std::cmp;
  38 use std::intrinsics::{TyDesc, get_tydesc};
  39 use std::intrinsics;
  40 use std::mem;
  41 use std::num::{Int, UnsignedInt};
  42 use std::ptr;
  43 use std::rc::Rc;
  44 use std::rt::heap::{allocate, deallocate};
  45
  46 // The way arena uses arrays is really deeply awful. The arrays are
  47 // allocated, and have capacities reserved, but the fill for the array
  48 // will always stay at 0.
  49 #[deriving(Clone, PartialEq)]
  50 struct Chunk {
  51     data: Rc<RefCell<Vec<u8>>>,
  52     fill: Cell<uint>,
  53     is_copy: Cell<bool>,
  54 }
  55
  56 impl Chunk {
  57     fn capacity(&self) -> uint {
  58         self.data.borrow().capacity()
  59     }
  60
  61     unsafe fn as_ptr(&self) -> *const u8 {
  62         self.data.borrow().as_ptr()
  63     }
  64 }
  65
  66 /// A slower reflection-based arena that can allocate objects of any type.
  67 ///
  68 /// This arena uses `Vec<u8>` as a backing store to allocate objects from. For
  69 /// each allocated object, the arena stores a pointer to the type descriptor
  70 /// followed by the object (potentially with alignment padding after each
  71 /// element). When the arena is destroyed, it iterates through all of its
  72 /// chunks, and uses the tydesc information to trace through the objects,
  73 /// calling the destructors on them. One subtle point that needs to be
  74 /// addressed is how to handle panics while running the user provided
  75 /// initializer function. It is important to not run the destructor on
  76 /// uninitialized objects, but how to detect them is somewhat subtle. Since
  77 /// `alloc()` can be invoked recursively, it is not sufficient to simply exclude
  78 /// the most recent object. To solve this without requiring extra space, we
  79 /// use the low order bit of the tydesc pointer to encode whether the object
  80 /// it describes has been fully initialized.
  81 ///
  82 /// As an optimization, objects with destructors are stored in different chunks
  83 /// than objects without destructors. This reduces overhead when initializing
  84 /// plain-old-data (`Copy` types) and means we don't need to waste time running
  85 /// their destructors.
  86 pub struct Arena {
  87     // The head is separated out from the list as a unbenchmarked
  88     // microoptimization, to avoid needing to case on the list to access the
  89     // head.
  90     head: RefCell<Chunk>,
  91     copy_head: RefCell<Chunk>,
  92     chunks: RefCell<Vec<Chunk>>,
  93 }
  94
  95 impl Arena {
  96     /// Allocates a new Arena with 32 bytes preallocated.
  97     pub fn new() -> Arena {
  98         Arena::new_with_size(32u)
  99     }
 100
 101     /// Allocates a new Arena with `initial_size` bytes preallocated.
 102     pub fn new_with_size(initial_size: uint) -> Arena {
 103         Arena {
 104             head: RefCell::new(chunk(initial_size, false)),
 105             copy_head: RefCell::new(chunk(initial_size, true)),
 106             chunks: RefCell::new(Vec::new()),
 107         }
 108     }
 109 }
 110
 111 fn chunk(size: uint, is_copy: bool) -> Chunk {
 112     Chunk {
 113         data: Rc::new(RefCell::new(Vec::with_capacity(size))),
 114         fill: Cell::new(0u),
 115         is_copy: Cell::new(is_copy),
 116     }
 117 }
 118
 119 #[unsafe_destructor]
 120 impl Drop for Arena {
 121     fn drop(&mut self) {
 122         unsafe {
 123             destroy_chunk(&*self.head.borrow());
 124             for chunk in self.chunks.borrow().iter() {
 125                 if !chunk.is_copy.get() {
 126                     destroy_chunk(chunk);
 127                 }
 128             }
 129         }
 130     }
 131 }
 132
 133 #[inline]
 134 fn round_up(base: uint, align: uint) -> uint {
 135     (base.checked_add(align - 1)).unwrap() & !(align - 1)
 136 }
 137
 138 // Walk down a chunk, running the destructors for any objects stored
 139 // in it.
 140 unsafe fn destroy_chunk(chunk: &Chunk) {
 141     let mut idx = 0;
 142     let buf = chunk.as_ptr();
 143     let fill = chunk.fill.get();
 144
 145     while idx < fill {
 146         let tydesc_data: *const uint = mem::transmute(buf.offset(idx as int));
 147         let (tydesc, is_done) = un_bitpack_tydesc_ptr(*tydesc_data);
 148         let (size, align) = ((*tydesc).size, (*tydesc).align);
 149
 150         let after_tydesc = idx + mem::size_of::<*const TyDesc>();
 151
 152         let start = round_up(after_tydesc, align);
 153
 154         //debug!("freeing object: idx = {}, size = {}, align = {}, done = {}",
 155         //       start, size, align, is_done);
 156         if is_done {
 157             ((*tydesc).drop_glue)(buf.offset(start as int) as *const i8);
 158         }
 159
 160         // Find where the next tydesc lives
 161         idx = round_up(start + size, mem::align_of::<*const TyDesc>());
 162     }
 163 }
 164
 165 // We encode whether the object a tydesc describes has been
 166 // initialized in the arena in the low bit of the tydesc pointer. This
 167 // is necessary in order to properly do cleanup if a panic occurs
 168 // during an initializer.
 169 #[inline]
 170 fn bitpack_tydesc_ptr(p: *const TyDesc, is_done: bool) -> uint {
 171     p as uint | (is_done as uint)
 172 }
 173 #[inline]
 174 fn un_bitpack_tydesc_ptr(p: uint) -> (*const TyDesc, bool) {
 175     ((p & !1) as *const TyDesc, p & 1 == 1)
 176 }
 177
 178 impl Arena {
 179     fn chunk_size(&self) -> uint {
 180         self.copy_head.borrow().capacity()
 181     }
 182
 183     // Functions for the POD part of the arena
 184     fn alloc_copy_grow(&self, n_bytes: uint, align: uint) -> *const u8 {
 185         // Allocate a new chunk.
 186         let new_min_chunk_size = cmp::max(n_bytes, self.chunk_size());
 187         self.chunks.borrow_mut().push(self.copy_head.borrow().clone());
 188
 189         *self.copy_head.borrow_mut() =
 190             chunk((new_min_chunk_size + 1u).next_power_of_two(), true);
 191
 192         return self.alloc_copy_inner(n_bytes, align);
 193     }
 194
 195     #[inline]
 196     fn alloc_copy_inner(&self, n_bytes: uint, align: uint) -> *const u8 {
 197         let start = round_up(self.copy_head.borrow().fill.get(), align);
 198
 199         let end = start + n_bytes;
 200         if end > self.chunk_size() {
 201             return self.alloc_copy_grow(n_bytes, align);
 202         }
 203
 204         let copy_head = self.copy_head.borrow();
 205         copy_head.fill.set(end);
 206
 207         unsafe {
 208             copy_head.as_ptr().offset(start as int)
 209         }
 210     }
 211
 212     #[inline]
 213     fn alloc_copy<T, F>(&self, op: F) -> &mut T where F: FnOnce() -> T {
 214         unsafe {
 215             let ptr = self.alloc_copy_inner(mem::size_of::<T>(),
 216                                             mem::min_align_of::<T>());
 217             let ptr = ptr as *mut T;
 218             ptr::write(&mut (*ptr), op());
 219             return &mut *ptr;
 220         }
 221     }
 222
 223     // Functions for the non-POD part of the arena
 224     fn alloc_noncopy_grow(&self, n_bytes: uint,
 225                           align: uint) -> (*const u8, *const u8) {
 226         // Allocate a new chunk.
 227         let new_min_chunk_size = cmp::max(n_bytes, self.chunk_size());
 228         self.chunks.borrow_mut().push(self.head.borrow().clone());
 229
 230         *self.head.borrow_mut() =
 231             chunk((new_min_chunk_size + 1u).next_power_of_two(), false);
 232
 233         return self.alloc_noncopy_inner(n_bytes, align);
 234     }
 235
 236     #[inline]
 237     fn alloc_noncopy_inner(&self, n_bytes: uint,
 238                            align: uint) -> (*const u8, *const u8) {
 239         // Be careful to not maintain any `head` borrows active, because
 240         // `alloc_noncopy_grow` borrows it mutably.
 241         let (start, end, tydesc_start, head_capacity) = {
 242             let head = self.head.borrow();
 243             let fill = head.fill.get();
 244
 245             let tydesc_start = fill;
 246             let after_tydesc = fill + mem::size_of::<*const TyDesc>();
 247             let start = round_up(after_tydesc, align);
 248             let end = start + n_bytes;
 249
 250             (start, end, tydesc_start, head.capacity())
 251         };
 252
 253         if end > head_capacity {
 254             return self.alloc_noncopy_grow(n_bytes, align);
 255         }
 256
 257         let head = self.head.borrow();
 258         head.fill.set(round_up(end, mem::align_of::<*const TyDesc>()));
 259
 260         unsafe {
 261             let buf = head.as_ptr();
 262             return (buf.offset(tydesc_start as int), buf.offset(start as int));
 263         }
 264     }
 265
 266     #[inline]
 267     fn alloc_noncopy<T, F>(&self, op: F) -> &mut T where F: FnOnce() -> T {
 268         unsafe {
 269             let tydesc = get_tydesc::<T>();
 270             let (ty_ptr, ptr) =
 271                 self.alloc_noncopy_inner(mem::size_of::<T>(),
 272                                          mem::min_align_of::<T>());
 273             let ty_ptr = ty_ptr as *mut uint;
 274             let ptr = ptr as *mut T;
 275             // Write in our tydesc along with a bit indicating that it
 276             // has *not* been initialized yet.
 277             *ty_ptr = mem::transmute(tydesc);
 278             // Actually initialize it
 279             ptr::write(&mut(*ptr), op());
 280             // Now that we are done, update the tydesc to indicate that
 281             // the object is there.
 282             *ty_ptr = bitpack_tydesc_ptr(tydesc, true);
 283
 284             return &mut *ptr;
 285         }
 286     }
 287
 288     /// Allocates a new item in the arena, using `op` to initialize the value,
 289     /// and returns a reference to it.
 290     #[inline]
 291     pub fn alloc<T, F>(&self, op: F) -> &mut T where F: FnOnce() -> T {
 292         unsafe {
 293             if intrinsics::needs_drop::<T>() {
 294                 self.alloc_noncopy(op)
 295             } else {
 296                 self.alloc_copy(op)
 297             }
 298         }
 299     }
 300 }
 301
 302 #[test]
 303 fn test_arena_destructors() {
 304     let arena = Arena::new();
 305     for i in range(0u, 10) {
 306         // Arena allocate something with drop glue to make sure it
 307         // doesn't leak.
 308         arena.alloc(|| Rc::new(i));
 309         // Allocate something with funny size and alignment, to keep
 310         // things interesting.
 311         arena.alloc(|| [0u8, 1u8, 2u8]);
 312     }
 313 }
 314
 315 #[test]
 316 fn test_arena_alloc_nested() {
 317     struct Inner { value: uint }
 318     struct Outer<'a> { inner: &'a Inner }
 319
 320     let arena = Arena::new();
 321
 322     let result = arena.alloc(|| Outer {
 323         inner: arena.alloc(|| Inner { value: 10 })
 324     });
 325
 326     assert_eq!(result.inner.value, 10);
 327 }
 328
 329 #[test]
 330 #[should_fail]
 331 fn test_arena_destructors_fail() {
 332     let arena = Arena::new();
 333     // Put some stuff in the arena.
 334     for i in range(0u, 10) {
 335         // Arena allocate something with drop glue to make sure it
 336         // doesn't leak.
 337         arena.alloc(|| { Rc::new(i) });
 338         // Allocate something with funny size and alignment, to keep
 339         // things interesting.
 340         arena.alloc(|| { [0u8, 1u8, 2u8] });
 341     }
 342     // Now, panic while allocating
 343     arena.alloc::<Rc<int>, _>(|| {
 344         panic!();
 345     });
 346 }
 347
 348 /// A faster arena that can hold objects of only one type.
 349 ///
 350 /// Safety note: Modifying objects in the arena that have already had their
 351 /// `drop` destructors run can cause leaks, because the destructor will not
 352 /// run again for these objects.
 353 pub struct TypedArena<T> {
 354     /// A pointer to the next object to be allocated.
 355     ptr: Cell<*const T>,
 356
 357     /// A pointer to the end of the allocated area. When this pointer is
 358     /// reached, a new chunk is allocated.
 359     end: Cell<*const T>,
 360
 361     /// A pointer to the first arena segment.
 362     first: RefCell<*mut TypedArenaChunk<T>>,
 363 }
 364
 365 struct TypedArenaChunk<T> {
 366     /// Pointer to the next arena segment.
 367     next: *mut TypedArenaChunk<T>,
 368
 369     /// The number of elements that this chunk can hold.
 370     capacity: uint,
 371
 372     // Objects follow here, suitably aligned.
 373 }
 374
 375 fn calculate_size<T>(capacity: uint) -> uint {
 376     let mut size = mem::size_of::<TypedArenaChunk<T>>();
 377     size = round_up(size, mem::min_align_of::<T>());
 378     let elem_size = mem::size_of::<T>();
 379     let elems_size = elem_size.checked_mul(capacity).unwrap();
 380     size = size.checked_add(elems_size).unwrap();
 381     size
 382 }
 383
 384 impl<T> TypedArenaChunk<T> {
 385     #[inline]
 386     unsafe fn new(next: *mut TypedArenaChunk<T>, capacity: uint)
 387            -> *mut TypedArenaChunk<T> {
 388         let size = calculate_size::<T>(capacity);
 389         let chunk = allocate(size, mem::min_align_of::<TypedArenaChunk<T>>())
 390                     as *mut TypedArenaChunk<T>;
 391         if chunk.is_null() { alloc::oom() }
 392         (*chunk).next = next;
 393         (*chunk).capacity = capacity;
 394         chunk
 395     }
 396
 397     /// Destroys this arena chunk. If the type descriptor is supplied, the
 398     /// drop glue is called; otherwise, drop glue is not called.
 399     #[inline]
 400     unsafe fn destroy(&mut self, len: uint) {
 401         // Destroy all the allocated objects.
 402         if intrinsics::needs_drop::<T>() {
 403             let mut start = self.start();
 404             for _ in range(0, len) {
 405                 ptr::read(start as *const T); // run the destructor on the pointer
 406                 start = start.offset(mem::size_of::<T>() as int)
 407             }
 408         }
 409
 410         // Destroy the next chunk.
 411         let next = self.next;
 412         let size = calculate_size::<T>(self.capacity);
 413         deallocate(self as *mut TypedArenaChunk<T> as *mut u8, size,
 414                    mem::min_align_of::<TypedArenaChunk<T>>());
 415         if !next.is_null() {
 416             let capacity = (*next).capacity;
 417             (*next).destroy(capacity);
 418         }
 419     }
 420
 421     // Returns a pointer to the first allocated object.
 422     #[inline]
 423     fn start(&self) -> *const u8 {
 424         let this: *const TypedArenaChunk<T> = self;
 425         unsafe {
 426             mem::transmute(round_up(this.offset(1) as uint,
 427                                     mem::min_align_of::<T>()))
 428         }
 429     }
 430
 431     // Returns a pointer to the end of the allocated space.
 432     #[inline]
 433     fn end(&self) -> *const u8 {
 434         unsafe {
 435             let size = mem::size_of::<T>().checked_mul(self.capacity).unwrap();
 436             self.start().offset(size as int)
 437         }
 438     }
 439 }
 440
 441 impl<T> TypedArena<T> {
 442     /// Creates a new `TypedArena` with preallocated space for eight objects.
 443     #[inline]
 444     pub fn new() -> TypedArena<T> {
 445         TypedArena::with_capacity(8)
 446     }
 447
 448     /// Creates a new `TypedArena` with preallocated space for the given number of
 449     /// objects.
 450     #[inline]
 451     pub fn with_capacity(capacity: uint) -> TypedArena<T> {
 452         unsafe {
 453             let chunk = TypedArenaChunk::<T>::new(ptr::null_mut(), capacity);
 454             TypedArena {
 455                 ptr: Cell::new((*chunk).start() as *const T),
 456                 end: Cell::new((*chunk).end() as *const T),
 457                 first: RefCell::new(chunk),
 458             }
 459         }
 460     }
 461
 462     /// Allocates an object in the `TypedArena`, returning a reference to it.
 463     #[inline]
 464     pub fn alloc(&self, object: T) -> &mut T {
 465         if self.ptr == self.end {
 466             self.grow()
 467         }
 468
 469         let ptr: &mut T = unsafe {
 470             let ptr: &mut T = mem::transmute(self.ptr.clone());
 471             ptr::write(ptr, object);
 472             self.ptr.set(self.ptr.get().offset(1));
 473             ptr
 474         };
 475
 476         ptr
 477     }
 478
 479     /// Grows the arena.
 480     #[inline(never)]
 481     fn grow(&self) {
 482         unsafe {
 483             let chunk = *self.first.borrow_mut();
 484             let new_capacity = (*chunk).capacity.checked_mul(2).unwrap();
 485             let chunk = TypedArenaChunk::<T>::new(chunk, new_capacity);
 486             self.ptr.set((*chunk).start() as *const T);
 487             self.end.set((*chunk).end() as *const T);
 488             *self.first.borrow_mut() = chunk
 489         }
 490     }
 491 }
 492
 493 #[unsafe_destructor]
 494 impl<T> Drop for TypedArena<T> {
 495     fn drop(&mut self) {
 496         unsafe {
 497             // Determine how much was filled.
 498             let start = self.first.borrow().as_ref().unwrap().start() as uint;
 499             let end = self.ptr.get() as uint;
 500             let diff = (end - start) / mem::size_of::<T>();
 501
 502             // Pass that to the `destroy` method.
 503             (**self.first.borrow_mut()).destroy(diff)
 504         }
 505     }
 506 }
 507
 508 #[cfg(test)]
 509 mod tests {
 510     extern crate test;
 511     use self::test::Bencher;
 512     use super::{Arena, TypedArena};
 513
 514     #[allow(dead_code)]
 515     struct Point {
 516         x: int,
 517         y: int,
 518         z: int,
 519     }
 520
 521     #[test]
 522     pub fn test_copy() {
 523         let arena = TypedArena::new();
 524         for _ in range(0u, 100000) {
 525             arena.alloc(Point {
 526                 x: 1,
 527                 y: 2,
 528                 z: 3,
 529             });
 530         }
 531     }
 532
 533     #[bench]
 534     pub fn bench_copy(b: &mut Bencher) {
 535         let arena = TypedArena::new();
 536         b.iter(|| {
 537             arena.alloc(Point {
 538                 x: 1,
 539                 y: 2,
 540                 z: 3,
 541             })
 542         })
 543     }
 544
 545     #[bench]
 546     pub fn bench_copy_nonarena(b: &mut Bencher) {
 547         b.iter(|| {
 548             box Point {
 549                 x: 1,
 550                 y: 2,
 551                 z: 3,
 552             }
 553         })
 554     }
 555
 556     #[bench]
 557     pub fn bench_copy_old_arena(b: &mut Bencher) {
 558         let arena = Arena::new();
 559         b.iter(|| {
 560             arena.alloc(|| {
 561                 Point {
 562                     x: 1,
 563                     y: 2,
 564                     z: 3,
 565                 }
 566             })
 567         })
 568     }
 569
 570     #[allow(dead_code)]
 571     struct Noncopy {
 572         string: String,
 573         array: Vec<int>,
 574     }
 575
 576     #[test]
 577     pub fn test_noncopy() {
 578         let arena = TypedArena::new();
 579         for _ in range(0u, 100000) {
 580             arena.alloc(Noncopy {
 581                 string: "hello world".to_string(),
 582                 array: vec!( 1, 2, 3, 4, 5 ),
 583             });
 584         }
 585     }
 586
 587     #[bench]
 588     pub fn bench_noncopy(b: &mut Bencher) {
 589         let arena = TypedArena::new();
 590         b.iter(|| {
 591             arena.alloc(Noncopy {
 592                 string: "hello world".to_string(),
 593                 array: vec!( 1, 2, 3, 4, 5 ),
 594             })
 595         })
 596     }
 597
 598     #[bench]
 599     pub fn bench_noncopy_nonarena(b: &mut Bencher) {
 600         b.iter(|| {
 601             box Noncopy {
 602                 string: "hello world".to_string(),
 603                 array: vec!( 1, 2, 3, 4, 5 ),
 604             }
 605         })
 606     }
 607
 608     #[bench]
 609     pub fn bench_noncopy_old_arena(b: &mut Bencher) {
 610         let arena = Arena::new();
 611         b.iter(|| {
 612             arena.alloc(|| Noncopy {
 613                 string: "hello world".to_string(),
 614                 array: vec!( 1, 2, 3, 4, 5 ),
 615             })
 616         })
 617     }
 618 }