src/libextra/arena.rs

   1 // Copyright 2012-2013 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 // Dynamic arenas.
  12
  13 // Arenas are used to quickly allocate objects that share a
  14 // lifetime. The arena uses ~[u8] vectors as a backing store to
  15 // allocate objects from. For each allocated object, the arena stores
  16 // a pointer to the type descriptor followed by the
  17 // object. (Potentially with alignment padding after each of them.)
  18 // When the arena is destroyed, it iterates through all of its chunks,
  19 // and uses the tydesc information to trace through the objects,
  20 // calling the destructors on them.
  21 // One subtle point that needs to be addressed is how to handle
  22 // failures while running the user provided initializer function. It
  23 // is important to not run the destructor on uninitialized objects, but
  24 // how to detect them is somewhat subtle. Since alloc() can be invoked
  25 // recursively, it is not sufficient to simply exclude the most recent
  26 // object. To solve this without requiring extra space, we use the low
  27 // order bit of the tydesc pointer to encode whether the object it
  28 // describes has been fully initialized.
  29
  30 // As an optimization, objects with destructors are stored in
  31 // different chunks than objects without destructors. This reduces
  32 // overhead when initializing plain-old-data and means we don't need
  33 // to waste time running the destructors of POD.
  34
  35 #[allow(missing_doc)];
  36
  37
  38 use list::{MutList, MutCons, MutNil};
  39
  40 use std::at_vec;
  41 use std::cast::{transmute, transmute_mut, transmute_mut_region};
  42 use std::cast;
  43 use std::num;
  44 use std::ptr;
  45 use std::sys;
  46 use std::uint;
  47 use std::vec;
  48 use std::unstable::intrinsics;
  49 use std::unstable::intrinsics::{TyDesc, get_tydesc};
  50
  51 // The way arena uses arrays is really deeply awful. The arrays are
  52 // allocated, and have capacities reserved, but the fill for the array
  53 // will always stay at 0.
  54 struct Chunk {
  55     data: @[u8],
  56     fill: uint,
  57     is_pod: bool,
  58 }
  59
  60 #[no_freeze]
  61 pub struct Arena {
  62     // The head is separated out from the list as a unbenchmarked
  63     // microoptimization, to avoid needing to case on the list to
  64     // access the head.
  65     priv head: Chunk,
  66     priv pod_head: Chunk,
  67     priv chunks: @mut MutList<Chunk>,
  68 }
  69
  70 impl Arena {
  71     pub fn new() -> Arena {
  72         Arena::new_with_size(32u)
  73     }
  74
  75     pub fn new_with_size(initial_size: uint) -> Arena {
  76         Arena {
  77             head: chunk(initial_size, false),
  78             pod_head: chunk(initial_size, true),
  79             chunks: @mut MutNil,
  80         }
  81     }
  82 }
  83
  84 fn chunk(size: uint, is_pod: bool) -> Chunk {
  85     let mut v: @[u8] = @[];
  86     unsafe { at_vec::raw::reserve(&mut v, size); }
  87     Chunk {
  88         data: unsafe { cast::transmute(v) },
  89         fill: 0u,
  90         is_pod: is_pod,
  91     }
  92 }
  93
  94 #[unsafe_destructor]
  95 impl Drop for Arena {
  96     fn drop(&self) {
  97         unsafe {
  98             destroy_chunk(&self.head);
  99             do self.chunks.each |chunk| {
 100                 if !chunk.is_pod {
 101                     destroy_chunk(chunk);
 102                 }
 103                 true
 104             };
 105         }
 106     }
 107 }
 108
 109 #[inline]
 110 fn round_up_to(base: uint, align: uint) -> uint {
 111     (base + (align - 1)) & !(align - 1)
 112 }
 113
 114 // Walk down a chunk, running the destructors for any objects stored
 115 // in it.
 116 unsafe fn destroy_chunk(chunk: &Chunk) {
 117     let mut idx = 0;
 118     let buf = vec::raw::to_ptr(chunk.data);
 119     let fill = chunk.fill;
 120
 121     while idx < fill {
 122         let tydesc_data: *uint = transmute(ptr::offset(buf, idx as int));
 123         let (tydesc, is_done) = un_bitpack_tydesc_ptr(*tydesc_data);
 124         let (size, align) = ((*tydesc).size, (*tydesc).align);
 125
 126         let after_tydesc = idx + sys::size_of::<*TyDesc>();
 127
 128         let start = round_up_to(after_tydesc, align);
 129
 130         //debug!("freeing object: idx = %u, size = %u, align = %u, done = %b",
 131         //       start, size, align, is_done);
 132         if is_done {
 133             ((*tydesc).drop_glue)(ptr::offset(buf, start as int) as *i8);
 134         }
 135
 136         // Find where the next tydesc lives
 137         idx = round_up_to(start + size, sys::pref_align_of::<*TyDesc>());
 138     }
 139 }
 140
 141 // We encode whether the object a tydesc describes has been
 142 // initialized in the arena in the low bit of the tydesc pointer. This
 143 // is necessary in order to properly do cleanup if a failure occurs
 144 // during an initializer.
 145 #[inline]
 146 unsafe fn bitpack_tydesc_ptr(p: *TyDesc, is_done: bool) -> uint {
 147     let p_bits: uint = transmute(p);
 148     p_bits | (is_done as uint)
 149 }
 150 #[inline]
 151 unsafe fn un_bitpack_tydesc_ptr(p: uint) -> (*TyDesc, bool) {
 152     (transmute(p & !1), p & 1 == 1)
 153 }
 154
 155 impl Arena {
 156     // Functions for the POD part of the arena
 157     fn alloc_pod_grow(&mut self, n_bytes: uint, align: uint) -> *u8 {
 158         // Allocate a new chunk.
 159         let chunk_size = at_vec::capacity(self.pod_head.data);
 160         let new_min_chunk_size = num::max(n_bytes, chunk_size);
 161         self.chunks = @mut MutCons(self.pod_head, self.chunks);
 162         self.pod_head =
 163             chunk(uint::next_power_of_two(new_min_chunk_size + 1u), true);
 164
 165         return self.alloc_pod_inner(n_bytes, align);
 166     }
 167
 168     #[inline]
 169     fn alloc_pod_inner(&mut self, n_bytes: uint, align: uint) -> *u8 {
 170         unsafe {
 171             let this = transmute_mut_region(self);
 172             let start = round_up_to(this.pod_head.fill, align);
 173             let end = start + n_bytes;
 174             if end > at_vec::capacity(this.pod_head.data) {
 175                 return this.alloc_pod_grow(n_bytes, align);
 176             }
 177             this.pod_head.fill = end;
 178
 179             //debug!("idx = %u, size = %u, align = %u, fill = %u",
 180             //       start, n_bytes, align, head.fill);
 181
 182             ptr::offset(vec::raw::to_ptr(this.pod_head.data), start as int)
 183         }
 184     }
 185
 186     #[inline]
 187     fn alloc_pod<'a, T>(&'a mut self, op: &fn() -> T) -> &'a T {
 188         unsafe {
 189             let tydesc = get_tydesc::<T>();
 190             let ptr = self.alloc_pod_inner((*tydesc).size, (*tydesc).align);
 191             let ptr: *mut T = transmute(ptr);
 192             intrinsics::move_val_init(&mut (*ptr), op());
 193             return transmute(ptr);
 194         }
 195     }
 196
 197     // Functions for the non-POD part of the arena
 198     fn alloc_nonpod_grow(&mut self, n_bytes: uint, align: uint)
 199                          -> (*u8, *u8) {
 200         // Allocate a new chunk.
 201         let chunk_size = at_vec::capacity(self.head.data);
 202         let new_min_chunk_size = num::max(n_bytes, chunk_size);
 203         self.chunks = @mut MutCons(self.head, self.chunks);
 204         self.head =
 205             chunk(uint::next_power_of_two(new_min_chunk_size + 1u), false);
 206
 207         return self.alloc_nonpod_inner(n_bytes, align);
 208     }
 209
 210     #[inline]
 211     fn alloc_nonpod_inner(&mut self, n_bytes: uint, align: uint)
 212                           -> (*u8, *u8) {
 213         unsafe {
 214             let start;
 215             let end;
 216             let tydesc_start;
 217             let after_tydesc;
 218
 219             {
 220                 let head = transmute_mut_region(&mut self.head);
 221
 222                 tydesc_start = head.fill;
 223                 after_tydesc = head.fill + sys::size_of::<*TyDesc>();
 224                 start = round_up_to(after_tydesc, align);
 225                 end = start + n_bytes;
 226             }
 227
 228             if end > at_vec::capacity(self.head.data) {
 229                 return self.alloc_nonpod_grow(n_bytes, align);
 230             }
 231
 232             let head = transmute_mut_region(&mut self.head);
 233             head.fill = round_up_to(end, sys::pref_align_of::<*TyDesc>());
 234
 235             //debug!("idx = %u, size = %u, align = %u, fill = %u",
 236             //       start, n_bytes, align, head.fill);
 237
 238             let buf = vec::raw::to_ptr(self.head.data);
 239             return (ptr::offset(buf, tydesc_start as int), ptr::offset(buf, start as int));
 240         }
 241     }
 242
 243     #[inline]
 244     fn alloc_nonpod<'a, T>(&'a mut self, op: &fn() -> T) -> &'a T {
 245         unsafe {
 246             let tydesc = get_tydesc::<T>();
 247             let (ty_ptr, ptr) =
 248                 self.alloc_nonpod_inner((*tydesc).size, (*tydesc).align);
 249             let ty_ptr: *mut uint = transmute(ty_ptr);
 250             let ptr: *mut T = transmute(ptr);
 251             // Write in our tydesc along with a bit indicating that it
 252             // has *not* been initialized yet.
 253             *ty_ptr = transmute(tydesc);
 254             // Actually initialize it
 255             intrinsics::move_val_init(&mut(*ptr), op());
 256             // Now that we are done, update the tydesc to indicate that
 257             // the object is there.
 258             *ty_ptr = bitpack_tydesc_ptr(tydesc, true);
 259
 260             return transmute(ptr);
 261         }
 262     }
 263
 264     // The external interface
 265     #[inline]
 266     pub fn alloc<'a, T>(&'a self, op: &fn() -> T) -> &'a T {
 267         unsafe {
 268             // XXX: Borrow check
 269             let this = transmute_mut(self);
 270             if intrinsics::needs_drop::<T>() {
 271                 this.alloc_nonpod(op)
 272             } else {
 273                 this.alloc_pod(op)
 274             }
 275         }
 276     }
 277 }
 278
 279 #[test]
 280 fn test_arena_destructors() {
 281     let arena = Arena::new();
 282     for i in range(0u, 10) {
 283         // Arena allocate something with drop glue to make sure it
 284         // doesn't leak.
 285         do arena.alloc { @i };
 286         // Allocate something with funny size and alignment, to keep
 287         // things interesting.
 288         do arena.alloc { [0u8, 1u8, 2u8] };
 289     }
 290 }
 291
 292 #[test]
 293 #[should_fail]
 294 fn test_arena_destructors_fail() {
 295     let arena = Arena::new();
 296     // Put some stuff in the arena.
 297     for i in range(0u, 10) {
 298         // Arena allocate something with drop glue to make sure it
 299         // doesn't leak.
 300         do arena.alloc { @i };
 301         // Allocate something with funny size and alignment, to keep
 302         // things interesting.
 303         do arena.alloc { [0u8, 1u8, 2u8] };
 304     }
 305     // Now, fail while allocating
 306     do arena.alloc::<@int> {
 307         // Now fail.
 308         fail!();
 309     };
 310 }