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