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