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 #![unstable(feature = "rustc_private", issue = "27812")]
  24 #![crate_type = "rlib"]
  25 #![crate_type = "dylib"]
  26 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  27        html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
  28        html_root_url = "https://doc.rust-lang.org/nightly/",
  29        test(no_crate_inject, attr(deny(warnings))))]
  30 #![cfg_attr(not(stage0), deny(warnings))]
  31
  32 #![feature(alloc)]
  33 #![feature(core_intrinsics)]
  34 #![feature(heap_api)]
  35 #![feature(heap_api)]
  36 #![feature(staged_api)]
  37 #![feature(dropck_parametricity)]
  38 #![cfg_attr(test, feature(test))]
  39
  40 #![allow(deprecated)]
  41
  42 extern crate alloc;
  43
  44 use std::cell::{Cell, RefCell};
  45 use std::cmp;
  46 use std::intrinsics;
  47 use std::marker::{PhantomData, Send};
  48 use std::mem;
  49 use std::ptr;
  50
  51 use alloc::heap;
  52 use alloc::raw_vec::RawVec;
  53
  54 /// A faster arena that can hold objects of only one type.
  55 pub struct TypedArena<T> {
  56     /// A pointer to the next object to be allocated.
  57     ptr: Cell<*mut T>,
  58
  59     /// A pointer to the end of the allocated area. When this pointer is
  60     /// reached, a new chunk is allocated.
  61     end: Cell<*mut T>,
  62
  63     /// A vector arena segments.
  64     chunks: RefCell<Vec<TypedArenaChunk<T>>>,
  65
  66     /// Marker indicating that dropping the arena causes its owned
  67     /// instances of `T` to be dropped.
  68     _own: PhantomData<T>,
  69 }
  70
  71 struct TypedArenaChunk<T> {
  72     /// Pointer to the next arena segment.
  73     storage: RawVec<T>,
  74 }
  75
  76 impl<T> TypedArenaChunk<T> {
  77     #[inline]
  78     unsafe fn new(capacity: usize) -> TypedArenaChunk<T> {
  79         TypedArenaChunk { storage: RawVec::with_capacity(capacity) }
  80     }
  81
  82     /// Destroys this arena chunk.
  83     #[inline]
  84     unsafe fn destroy(&mut self, len: usize) {
  85         // The branch on needs_drop() is an -O1 performance optimization.
  86         // Without the branch, dropping TypedArena<u8> takes linear time.
  87         if intrinsics::needs_drop::<T>() {
  88             let mut start = self.start();
  89             // Destroy all allocated objects.
  90             for _ in 0..len {
  91                 ptr::drop_in_place(start);
  92                 start = start.offset(1);
  93             }
  94         }
  95     }
  96
  97     // Returns a pointer to the first allocated object.
  98     #[inline]
  99     fn start(&self) -> *mut T {
 100         self.storage.ptr()
 101     }
 102
 103     // Returns a pointer to the end of the allocated space.
 104     #[inline]
 105     fn end(&self) -> *mut T {
 106         unsafe {
 107             if mem::size_of::<T>() == 0 {
 108                 // A pointer as large as possible for zero-sized elements.
 109                 !0 as *mut T
 110             } else {
 111                 self.start().offset(self.storage.cap() as isize)
 112             }
 113         }
 114     }
 115 }
 116
 117 const PAGE: usize = 4096;
 118
 119 impl<T> TypedArena<T> {
 120     /// Creates a new `TypedArena` with preallocated space for many objects.
 121     #[inline]
 122     pub fn new() -> TypedArena<T> {
 123         // Reserve at least one page.
 124         let elem_size = cmp::max(1, mem::size_of::<T>());
 125         TypedArena::with_capacity(PAGE / elem_size)
 126     }
 127
 128     /// Creates a new `TypedArena` with preallocated space for the given number of
 129     /// objects.
 130     #[inline]
 131     pub fn with_capacity(capacity: usize) -> TypedArena<T> {
 132         unsafe {
 133             let chunk = TypedArenaChunk::<T>::new(cmp::max(1, capacity));
 134             TypedArena {
 135                 ptr: Cell::new(chunk.start()),
 136                 end: Cell::new(chunk.end()),
 137                 chunks: RefCell::new(vec![chunk]),
 138                 _own: PhantomData,
 139             }
 140         }
 141     }
 142
 143     /// Allocates an object in the `TypedArena`, returning a reference to it.
 144     #[inline]
 145     pub fn alloc(&self, object: T) -> &mut T {
 146         if self.ptr == self.end {
 147             self.grow()
 148         }
 149
 150         unsafe {
 151             if mem::size_of::<T>() == 0 {
 152                 self.ptr.set(intrinsics::arith_offset(self.ptr.get() as *mut u8, 1) as *mut T);
 153                 let ptr = heap::EMPTY as *mut T;
 154                 // Don't drop the object. This `write` is equivalent to `forget`.
 155                 ptr::write(ptr, object);
 156                 &mut *ptr
 157             } else {
 158                 let ptr = self.ptr.get();
 159                 // Advance the pointer.
 160                 self.ptr.set(self.ptr.get().offset(1));
 161                 // Write into uninitialized memory.
 162                 ptr::write(ptr, object);
 163                 &mut *ptr
 164             }
 165         }
 166     }
 167
 168     /// Grows the arena.
 169     #[inline(never)]
 170     #[cold]
 171     fn grow(&self) {
 172         unsafe {
 173             let mut chunks = self.chunks.borrow_mut();
 174             let prev_capacity = chunks.last().unwrap().storage.cap();
 175             let new_capacity = prev_capacity.checked_mul(2).unwrap();
 176             if chunks.last_mut().unwrap().storage.double_in_place() {
 177                 self.end.set(chunks.last().unwrap().end());
 178             } else {
 179                 let chunk = TypedArenaChunk::<T>::new(new_capacity);
 180                 self.ptr.set(chunk.start());
 181                 self.end.set(chunk.end());
 182                 chunks.push(chunk);
 183             }
 184         }
 185     }
 186     /// Clears the arena. Deallocates all but the longest chunk which may be reused.
 187     pub fn clear(&mut self) {
 188         unsafe {
 189             // Clear the last chunk, which is partially filled.
 190             let mut chunks_borrow = self.chunks.borrow_mut();
 191             let last_idx = chunks_borrow.len() - 1;
 192             self.clear_last_chunk(&mut chunks_borrow[last_idx]);
 193             // If `T` is ZST, code below has no effect.
 194             for mut chunk in chunks_borrow.drain(..last_idx) {
 195                 let cap = chunk.storage.cap();
 196                 chunk.destroy(cap);
 197             }
 198         }
 199     }
 200
 201     // Drops the contents of the last chunk. The last chunk is partially empty, unlike all other
 202     // chunks.
 203     fn clear_last_chunk(&self, last_chunk: &mut TypedArenaChunk<T>) {
 204         // Determine how much was filled.
 205         let start = last_chunk.start() as usize;
 206         // We obtain the value of the pointer to the first uninitialized element.
 207         let end = self.ptr.get() as usize;
 208         // We then calculate the number of elements to be dropped in the last chunk,
 209         // which is the filled area's length.
 210         let diff = if mem::size_of::<T>() == 0 {
 211             // `T` is ZST. It can't have a drop flag, so the value here doesn't matter. We get
 212             // the number of zero-sized values in the last and only chunk, just out of caution.
 213             // Recall that `end` was incremented for each allocated value.
 214             end - start
 215         } else {
 216             (end - start) / mem::size_of::<T>()
 217         };
 218         // Pass that to the `destroy` method.
 219         unsafe {
 220             last_chunk.destroy(diff);
 221         }
 222         // Reset the chunk.
 223         self.ptr.set(last_chunk.start());
 224     }
 225 }
 226
 227 impl<T> Drop for TypedArena<T> {
 228     #[unsafe_destructor_blind_to_params]
 229     fn drop(&mut self) {
 230         unsafe {
 231             // Determine how much was filled.
 232             let mut chunks_borrow = self.chunks.borrow_mut();
 233             let mut last_chunk = chunks_borrow.pop().unwrap();
 234             // Drop the contents of the last chunk.
 235             self.clear_last_chunk(&mut last_chunk);
 236             // The last chunk will be dropped. Destroy all other chunks.
 237             for chunk in chunks_borrow.iter_mut() {
 238                 let cap = chunk.storage.cap();
 239                 chunk.destroy(cap);
 240             }
 241             // RawVec handles deallocation of `last_chunk` and `self.chunks`.
 242         }
 243     }
 244 }
 245
 246 unsafe impl<T: Send> Send for TypedArena<T> {}
 247
 248 #[cfg(test)]
 249 mod tests {
 250     extern crate test;
 251     use self::test::Bencher;
 252     use super::TypedArena;
 253     use std::cell::Cell;
 254
 255     #[allow(dead_code)]
 256     #[derive(Debug, Eq, PartialEq)]
 257     struct Point {
 258         x: i32,
 259         y: i32,
 260         z: i32,
 261     }
 262
 263     #[test]
 264     fn test_arena_alloc_nested() {
 265         struct Inner {
 266             value: u8,
 267         }
 268         struct Outer<'a> {
 269             inner: &'a Inner,
 270         }
 271         enum EI<'e> {
 272             I(Inner),
 273             O(Outer<'e>),
 274         }
 275
 276         struct Wrap<'a>(TypedArena<EI<'a>>);
 277
 278         impl<'a> Wrap<'a> {
 279             fn alloc_inner<F: Fn() -> Inner>(&self, f: F) -> &Inner {
 280                 let r: &EI = self.0.alloc(EI::I(f()));
 281                 if let &EI::I(ref i) = r {
 282                     i
 283                 } else {
 284                     panic!("mismatch");
 285                 }
 286             }
 287             fn alloc_outer<F: Fn() -> Outer<'a>>(&self, f: F) -> &Outer {
 288                 let r: &EI = self.0.alloc(EI::O(f()));
 289                 if let &EI::O(ref o) = r {
 290                     o
 291                 } else {
 292                     panic!("mismatch");
 293                 }
 294             }
 295         }
 296
 297         let arena = Wrap(TypedArena::new());
 298
 299         let result = arena.alloc_outer(|| {
 300             Outer { inner: arena.alloc_inner(|| Inner { value: 10 }) }
 301         });
 302
 303         assert_eq!(result.inner.value, 10);
 304     }
 305
 306     #[test]
 307     pub fn test_copy() {
 308         let arena = TypedArena::new();
 309         for _ in 0..100000 {
 310             arena.alloc(Point { x: 1, y: 2, z: 3 });
 311         }
 312     }
 313
 314     #[bench]
 315     pub fn bench_copy(b: &mut Bencher) {
 316         let arena = TypedArena::new();
 317         b.iter(|| arena.alloc(Point { x: 1, y: 2, z: 3 }))
 318     }
 319
 320     #[bench]
 321     pub fn bench_copy_nonarena(b: &mut Bencher) {
 322         b.iter(|| {
 323             let _: Box<_> = Box::new(Point { x: 1, y: 2, z: 3 });
 324         })
 325     }
 326
 327     #[allow(dead_code)]
 328     struct Noncopy {
 329         string: String,
 330         array: Vec<i32>,
 331     }
 332
 333     #[test]
 334     pub fn test_noncopy() {
 335         let arena = TypedArena::new();
 336         for _ in 0..100000 {
 337             arena.alloc(Noncopy {
 338                 string: "hello world".to_string(),
 339                 array: vec![1, 2, 3, 4, 5],
 340             });
 341         }
 342     }
 343
 344     #[test]
 345     pub fn test_typed_arena_zero_sized() {
 346         let arena = TypedArena::new();
 347         for _ in 0..100000 {
 348             arena.alloc(());
 349         }
 350     }
 351
 352     #[test]
 353     pub fn test_typed_arena_clear() {
 354         let mut arena = TypedArena::new();
 355         for _ in 0..10 {
 356             arena.clear();
 357             for _ in 0..10000 {
 358                 arena.alloc(Point { x: 1, y: 2, z: 3 });
 359             }
 360         }
 361     }
 362
 363     // Drop tests
 364
 365     struct DropCounter<'a> {
 366         count: &'a Cell<u32>,
 367     }
 368
 369     impl<'a> Drop for DropCounter<'a> {
 370         fn drop(&mut self) {
 371             self.count.set(self.count.get() + 1);
 372         }
 373     }
 374
 375     #[test]
 376     fn test_typed_arena_drop_count() {
 377         let counter = Cell::new(0);
 378         {
 379             let arena: TypedArena<DropCounter> = TypedArena::new();
 380             for _ in 0..100 {
 381                 // Allocate something with drop glue to make sure it doesn't leak.
 382                 arena.alloc(DropCounter { count: &counter });
 383             }
 384         };
 385         assert_eq!(counter.get(), 100);
 386     }
 387
 388     #[test]
 389     fn test_typed_arena_drop_on_clear() {
 390         let counter = Cell::new(0);
 391         let mut arena: TypedArena<DropCounter> = TypedArena::new();
 392         for i in 0..10 {
 393             for _ in 0..100 {
 394                 // Allocate something with drop glue to make sure it doesn't leak.
 395                 arena.alloc(DropCounter { count: &counter });
 396             }
 397             arena.clear();
 398             assert_eq!(counter.get(), i * 100 + 100);
 399         }
 400     }
 401
 402     thread_local! {
 403         static DROP_COUNTER: Cell<u32> = Cell::new(0)
 404     }
 405
 406     struct SmallDroppable;
 407
 408     impl Drop for SmallDroppable {
 409         fn drop(&mut self) {
 410             DROP_COUNTER.with(|c| c.set(c.get() + 1));
 411         }
 412     }
 413
 414     #[test]
 415     fn test_typed_arena_drop_small_count() {
 416         DROP_COUNTER.with(|c| c.set(0));
 417         {
 418             let arena: TypedArena<SmallDroppable> = TypedArena::new();
 419             for _ in 0..100 {
 420                 // Allocate something with drop glue to make sure it doesn't leak.
 421                 arena.alloc(SmallDroppable);
 422             }
 423             // dropping
 424         };
 425         assert_eq!(DROP_COUNTER.with(|c| c.get()), 100);
 426     }
 427
 428     #[bench]
 429     pub fn bench_noncopy(b: &mut Bencher) {
 430         let arena = TypedArena::new();
 431         b.iter(|| {
 432             arena.alloc(Noncopy {
 433                 string: "hello world".to_string(),
 434                 array: vec![1, 2, 3, 4, 5],
 435             })
 436         })
 437     }
 438
 439     #[bench]
 440     pub fn bench_noncopy_nonarena(b: &mut Bencher) {
 441         b.iter(|| {
 442             let _: Box<_> = Box::new(Noncopy {
 443                 string: "hello world".to_string(),
 444                 array: vec![1, 2, 3, 4, 5],
 445             });
 446         })
 447     }
 448 }