notes

bump_allocator.txt (2901B)

---

 ===============================================================================
 Bump Allocator
 ===============================================================================
 
 A bump allocator (also called an arena or region allocator) is about the
 simplest allocator you can build:
 
 1. You grab one big block of memory up front
 2. hold a pointer into it
 3. and every allocation just aligns that pointer and advances it past the
    requested size
 
 struct Bump {
     start: *mut u8,
     end: *mut u8,
     ptr: Cell<*mut u8>, // the "bump pointer"
 }
 
 fn alloc(&self, layout: Layout) -> Option<*mut u8> {
     let cur = self.ptr.get() as usize;
     let aligned = (cur + layout.align() - 1) & !(layout.align() - 1);
     let new = aligned.checked_add(layout.size())?;
     if new > self.end as usize { return None; }
     self.ptr.set(new as *mut u8);
     Some(aligned as *mut u8)
 }
 
 ---------------
 
 /// Round `addr` up to the next multiple of `align`.
 /// `align` must be a power of two.
 fn align_up(addr: usize, align: usize) -> usize {
     debug_assert!(align.is_power_of_two());
 
     // For a power of two, `align - 1` is a mask of the low bits:
     //   align = 8  ->  low_bits = 0b111
     // An address is aligned exactly when those low bits are all zero.
     let low_bits = align - 1;
 
     // Clearing the low bits rounds DOWN to a multiple of align.
     // Adding `low_bits` first turns that into rounding UP,
     // while leaving already-aligned addresses untouched.
     (addr + low_bits) & !low_bits
 }
 
 impl Bump {
     fn alloc(&self, layout: Layout) -> Option<*mut u8> {
         // Where the next allocation would start, as a plain integer.
         // (Integers, not pointers, so the arithmetic below has no UB rules
         // about staying inside one allocated object.)
         let cursor = self.ptr.get() as usize;
 
         // Step 1: move the cursor forward until it satisfies the
         // alignment this type requires. Any bytes skipped are padding.
         let object_start = align_up(cursor, layout.align());
 
         // Step 2: work out where the object ends.
         // `checked_add` guards against a huge `size` wrapping usize around
         // to a small number, which would sneak past the bounds check below.
         let object_end = object_start.checked_add(layout.size())?;
 
         // Step 3: does it actually fit in what's left of the chunk?
         // `end` is one-past-the-last byte, so landing exactly on it is fine.
         let chunk_end = self.end as usize;
         if object_end > chunk_end {
             return None; // chunk exhausted — caller can grab a new one
         }
 
         // Step 4: commit. This is the only mutation; everything above
         // was just arithmetic that we could still walk away from.
         self.ptr.set(object_end as *mut u8);
 
         // The caller's data lives in [object_start, object_end).
         Some(object_start as *mut u8)
     }
 }