Always Bump Downwards: The Arena Allocator rustc Uses for Everything

// compiler/rustc_arena/src/lib.rs:344-362

/// An arena that can hold objects of multiple different types that impl `Copy`
/// and/or satisfy `!mem::needs_drop`.
pub struct DroplessArena {
    /// A pointer to the start of the free space.
    start: Cell<*mut u8>,

    /// A pointer to the end of free space.
    ///
    /// The allocation proceeds downwards from the end of the chunk towards the
    /// start. (This is slightly simpler and faster than allocating upwards,
    /// see <https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html>.)
    /// When this pointer crosses the start pointer, a new chunk is allocated.
    ///
    /// This is kept aligned to DROPLESS_ALIGNMENT.
    end: Cell<*mut u8>,

    /// A vector of arena chunks.
    chunks: RefCell<Vec<ArenaChunk>>,
}

// compiler/rustc_arena/src/lib.rs:419-453

#[inline]
pub fn alloc_raw(&self, layout: Layout) -> *mut u8 {
    assert!(layout.size() != 0);

    // This loop executes once or twice: if allocation fails the first
    // time, the `grow` ensures it will succeed the second time.
    loop {
        let start = self.start.get().addr();
        let old_end = self.end.get();
        let end = old_end.addr();

        // Align allocated bytes so that `self.end` stays aligned to
        // DROPLESS_ALIGNMENT.
        let bytes = align_up(layout.size(), DROPLESS_ALIGNMENT);

        // Tell LLVM that `end` is aligned to DROPLESS_ALIGNMENT.
        unsafe { hint::assert_unchecked(end == align_down(end, DROPLESS_ALIGNMENT)) };

        if let Some(sub) = end.checked_sub(bytes) {
            let new_end = align_down(sub, layout.align());
            if start <= new_end {
                let new_end = old_end.with_addr(new_end);
                // `new_end` is aligned to DROPLESS_ALIGNMENT as `align_down`
                // preserves alignment as both `end` and `bytes` are already
                // aligned to DROPLESS_ALIGNMENT.
                self.end.set(new_end);
                return new_end;
            }
        }

        // No free space left. Allocate a new chunk to satisfy the request.
        // On failure the grow will panic or abort.
        self.grow(layout);
    }
}

// compiler/rustc_arena/src/lib.rs:96-102

// The arenas start with PAGE-sized chunks, and then each new chunk is twice as
// big as its predecessor, up until we reach HUGE_PAGE-sized chunks, whereupon
// we stop growing. This scales well, from arenas that are barely used up to
// arenas that are used for 100s of MiBs. Note also that the chosen sizes match
// the usual sizes of pages and huge pages on Linux.
const PAGE: usize = 4096;
const HUGE_PAGE: usize = 2 * 1024 * 1024;

// compiler/rustc_arena/src/lib.rs:380-417

#[inline(never)]
#[cold]
fn grow(&self, layout: Layout) {
    // Add some padding so we can align `self.end` while
    // still fitting in a `layout` allocation.
    let additional = layout.size() + cmp::max(DROPLESS_ALIGNMENT, layout.align()) - 1;

    unsafe {
        let mut chunks = self.chunks.borrow_mut();
        let mut new_cap;
        if let Some(last_chunk) = chunks.last_mut() {
            // There is no need to update `last_chunk.entries` because that
            // field isn't used by `DroplessArena`.

            // If the previous chunk's len is less than HUGE_PAGE
            // bytes, then this chunk will be least double the previous
            // chunk's size.
            new_cap = last_chunk.storage.len().min(HUGE_PAGE / 2);
            new_cap *= 2;
        } else {
            new_cap = PAGE;
        }
        // Also ensure that this chunk can fit `additional`.
        new_cap = cmp::max(additional, new_cap);

        let chunk = chunks.push_mut(ArenaChunk::new(align_up(new_cap, PAGE)));
        self.start.set(chunk.start());

        // Align the end to DROPLESS_ALIGNMENT.
        let end = align_down(chunk.end().addr(), DROPLESS_ALIGNMENT);
        ...

// compiler/rustc_arena/src/lib.rs:597-627

/// Declares an `Arena` that can allocate values of a variety of `Copy`, `needs_drop` and
/// `!needs_drop` types.
///
/// The declared arena actually contains a single [`DroplessArena`], plus a separate
/// [`TypedArena`] for each of the types listed in the body of the macro invocation.
///
/// Any type that is `Copy` can be allocated in the arena without needing to be listed
/// explicitly. Those values will be stored in the [`DroplessArena`].
///
/// Types that are `!Copy` can only be allocated if they are listed in the macro invocation.
/// For types that are `!Copy + needs_drop`, values will be stored in the corresponding
/// [`TypedArena`] and will be dropped when the arena is dropped.
///
/// As an optimization, types that are `!Copy + !needs_drop` will actually be stored in the
/// `DroplessArena`, and the corresponding [`TypedArena`] will remain empty. This makes
/// better use of the dropless arena's storage blocks, while the overhead of having a few
/// unused typed-arenas is negligible.
#[rustc_macro_transparency = "semiopaque"]
pub macro declare_arena!(
    // Each of these entries becomes a `$name: TypedArena<$ty>` field in the arena.
    // This allows values of non-copy type $ty to be allocated in the arena.
    // The field names must be distinct, but have no further significance.
    $(
        $name:ident: $ty:ty,
    )*
) {

// compiler/rustc_arena/src/lib.rs:639-679

    // Any type that impls `Copy` can be arena-allocated in the `DroplessArena`.
    impl<'tcx, T: Copy> ArenaAllocitable<'tcx, rustc_arena::IsCopy> for T {
        #[inline]
        #[allow(clippy::mut_from_ref)]
        fn allocate_on(self, arena: &'tcx Arena<'tcx>) -> &'tcx mut Self {
            arena.dropless.alloc(self)
        }
        ...
    }
    $(
        impl<'tcx> ArenaAllocitable<'tcx, rustc_arena::IsNotCopy> for $ty {
            #[inline]
            fn allocate_on(self, arena: &'tcx Arena<'tcx>) -> &'tcx mut Self {
                if !::std::mem::needs_drop::<Self>() {
                    arena.dropless.alloc(self)
                } else {
                    arena.$name.alloc(self)
                }
            }