bomalloc 0.3.0

A fragmentation-aware experimental allocator built around address-span ownership
Documentation
use std::alloc::{GlobalAlloc, Layout, System};
use std::cell::Cell;
use std::ptr::NonNull;
use std::sync::OnceLock;

use crate::{
    BoAllocError, BoAllocator, Config, InvariantError, StatsSnapshot, TrimMode, TrimStats,
};

thread_local! {
    /// Allocator construction and internal metadata may themselves use Rust's
    /// global allocation entry points. A const, destructor-free TLS flag keeps
    /// those recursive calls on System without entering OnceLock recursively.
    static IN_GLOBAL_ALLOCATOR: Cell<bool> = const { Cell::new(false) };
}

struct GlobalCallGuard;

impl GlobalCallGuard {
    #[inline]
    fn enter() -> Option<Self> {
        IN_GLOBAL_ALLOCATOR
            .try_with(|active| {
                if active.replace(true) {
                    None
                } else {
                    Some(Self)
                }
            })
            .ok()
            .flatten()
    }
}

impl Drop for GlobalCallGuard {
    #[inline]
    fn drop(&mut self) {
        let _ = IN_GLOBAL_ALLOCATOR.try_with(|active| active.set(false));
    }
}

/// A stable [`GlobalAlloc`] adapter for using bomalloc as Rust's process allocator.
///
/// The adapter is const-constructible and lazily creates its [`BoAllocator`], so
/// it can be installed directly on a static:
///
/// ```
/// use bomalloc::BoGlobalAllocator;
///
/// #[global_allocator]
/// static GLOBAL: BoGlobalAllocator = BoGlobalAllocator::new();
///
/// fn main() {
///     let values = vec![1_u64, 2, 3];
///     assert_eq!(values.iter().sum::<u64>(), 6);
/// }
/// ```
///
/// Allocations made recursively while bomalloc is initializing or managing its
/// own metadata use [`System`]. Deallocation routes such pointers back to System
/// by checking whether the address belongs to a bomalloc reservation. If the
/// configured allocator cannot initialize, this adapter remains usable by
/// falling back to System; [`Self::initialize`] exposes the initialization error.
///
/// Rust's `Allocator` trait is still unstable on the crate's Rust 1.86 baseline;
/// `GlobalAlloc` is the stable interface for replacing Rust's global allocator.
pub struct BoGlobalAllocator {
    config: Config,
    allocator: OnceLock<Result<BoAllocator, BoAllocError>>,
}

impl BoGlobalAllocator {
    /// Creates a lazily initialized global allocator with [`Config::new`].
    pub const fn new() -> Self {
        Self::with_config(Config::new())
    }

    /// Creates a lazily initialized global allocator with a custom configuration.
    pub const fn with_config(config: Config) -> Self {
        Self {
            config,
            allocator: OnceLock::new(),
        }
    }

    /// Initializes the process allocator, if necessary.
    pub fn initialize(&self) -> Result<(), BoAllocError> {
        self.with_allocator(|_| ())
    }

    /// Returns a synchronized snapshot of the installed allocator's statistics.
    pub fn stats(&self) -> Result<StatsSnapshot, BoAllocError> {
        self.with_allocator(BoAllocator::stats)
    }

    /// Cooperatively trims the installed allocator.
    pub fn trim(&self, mode: TrimMode) -> Result<TrimStats, BoAllocError> {
        self.with_allocator(|allocator| allocator.trim(mode))
    }

    /// Validates the installed allocator's debug invariants.
    pub fn validate(&self) -> Result<(), InvariantError> {
        const MESSAGE_CAPACITY: usize = 1024;

        struct FixedMessage {
            bytes: [u8; MESSAGE_CAPACITY],
            len: usize,
        }

        impl FixedMessage {
            fn from_invariant(error: &InvariantError) -> Self {
                let source = error.0.as_bytes();
                let mut len = source.len().min(MESSAGE_CAPACITY);
                while !error.0.is_char_boundary(len) {
                    len -= 1;
                }
                let mut bytes = [0; MESSAGE_CAPACITY];
                bytes[..len].copy_from_slice(&source[..len]);
                Self { bytes, len }
            }
        }

        struct PendingError {
            initialization: Option<BoAllocError>,
            invariant: FixedMessage,
        }

        let validation = {
            let Some(_guard) = GlobalCallGuard::enter() else {
                return Err(InvariantError::new(
                    "global allocator validation was called re-entrantly",
                ));
            };
            match self.initialize_guarded() {
                Err(error) => Err(PendingError {
                    initialization: Some(error),
                    invariant: FixedMessage {
                        bytes: [0; MESSAGE_CAPACITY],
                        len: 0,
                    },
                }),
                Ok(allocator) => allocator.validate().map_err(|error| PendingError {
                    initialization: None,
                    invariant: FixedMessage::from_invariant(&error),
                }),
            }
        };

        match validation {
            Ok(()) => Ok(()),
            Err(error) if error.initialization.is_some() => {
                let error = error.initialization.expect("checked above");
                Err(InvariantError::new(format!(
                    "global allocator initialization failed: {error}"
                )))
            }
            Err(error) => {
                let text = std::str::from_utf8(&error.invariant.bytes[..error.invariant.len])
                    .expect("copied invariant message remains UTF-8");
                Err(InvariantError::new(text))
            }
        }
    }

    fn with_allocator<R>(
        &self,
        operation: impl FnOnce(&BoAllocator) -> R,
    ) -> Result<R, BoAllocError> {
        if let Some(result) = self.allocator.get() {
            let Some(_guard) = GlobalCallGuard::enter() else {
                return Err(BoAllocError::OutOfMemory);
            };
            return result.as_ref().map(operation).map_err(|error| *error);
        }

        let Some(_guard) = GlobalCallGuard::enter() else {
            return Err(BoAllocError::OutOfMemory);
        };
        self.initialize_guarded().map(operation)
    }

    #[inline]
    fn initialize_guarded(&self) -> Result<&BoAllocator, BoAllocError> {
        self.allocator
            .get_or_init(|| BoAllocator::new(self.config.clone()))
            .as_ref()
            .map_err(|error| *error)
    }

    #[inline]
    fn initialized_owner(&self, address: usize) -> Option<&BoAllocator> {
        match self.allocator.get() {
            // During normal execution, all user-visible allocations after a
            // successful initialization originate from bomalloc. Re-entrant
            // System allocations are created and destroyed under the active
            // recursion guard. Native TLS teardown is the one period where
            // both origins can escape that dynamic scope, so it uses the tree.
            Some(Ok(allocator))
                if !crate::tls::thread_exiting() || allocator.owns_address(address) =>
            {
                Some(allocator)
            }
            _ => None,
        }
    }

    #[inline]
    unsafe fn allocate_guarded(&self, layout: Layout, zeroed: bool) -> *mut u8 {
        if !crate::allocator::thread_cache_available() {
            if zeroed {
                // SAFETY: forwarded with GlobalAlloc's layout contract.
                return unsafe { System.alloc_zeroed(layout) };
            }
            // SAFETY: forwarded with GlobalAlloc's layout contract.
            return unsafe { System.alloc(layout) };
        }
        match self.initialize_guarded() {
            Ok(allocator) => match allocator.allocate(layout) {
                Ok(allocation) => {
                    let pointer = allocation.as_ptr() as *mut u8;
                    if zeroed && layout.size() != 0 {
                        // SAFETY: allocation contains at least layout.size() writable bytes.
                        unsafe { pointer.write_bytes(0, layout.size()) };
                    }
                    pointer
                }
                Err(_) => std::ptr::null_mut(),
            },
            Err(_) => {
                if zeroed {
                    // SAFETY: forwarded with GlobalAlloc's layout contract.
                    unsafe { System.alloc_zeroed(layout) }
                } else {
                    // SAFETY: forwarded with GlobalAlloc's layout contract.
                    unsafe { System.alloc(layout) }
                }
            }
        }
    }
}

impl Default for BoGlobalAllocator {
    fn default() -> Self {
        Self::new()
    }
}

// SAFETY: BoAllocator provides synchronized shared allocation, and recursive
// metadata allocations are isolated in System. Successful initialization fixes
// the ordinary user origin to bomalloc; initialization failure fixes it to System,
// and mixed-origin native TLS teardown performs an address-ownership check.
unsafe impl GlobalAlloc for BoGlobalAllocator {
    #[inline]
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        if layout.size() == 0 {
            return layout.align() as *mut u8;
        }
        let Some(_guard) = GlobalCallGuard::enter() else {
            // SAFETY: forwarded with GlobalAlloc's layout contract.
            return unsafe { System.alloc(layout) };
        };
        // SAFETY: caller supplied a valid non-zero Layout.
        unsafe { self.allocate_guarded(layout, false) }
    }

    #[inline]
    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
        if layout.size() == 0 {
            return layout.align() as *mut u8;
        }
        let Some(_guard) = GlobalCallGuard::enter() else {
            // SAFETY: forwarded with GlobalAlloc's layout contract.
            return unsafe { System.alloc_zeroed(layout) };
        };
        // SAFETY: caller supplied a valid non-zero Layout.
        unsafe { self.allocate_guarded(layout, true) }
    }

    #[inline]
    unsafe fn dealloc(&self, pointer: *mut u8, layout: Layout) {
        if pointer.is_null() || layout.size() == 0 {
            return;
        }
        let Some(_guard) = GlobalCallGuard::enter() else {
            // Re-entrant allocations originate from System.
            // SAFETY: forwarded with the original allocation's Layout.
            unsafe { System.dealloc(pointer, layout) };
            return;
        };

        if let Some(allocator) = self.initialized_owner(pointer as usize) {
            // SAFETY: GlobalAlloc requires the original pointer and Layout.
            unsafe { allocator.deallocate(NonNull::new_unchecked(pointer), layout) };
        } else {
            // SAFETY: non-bomalloc pointers produced by this adapter originate from System.
            unsafe { System.dealloc(pointer, layout) };
        }
    }

    #[inline]
    unsafe fn realloc(&self, pointer: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
        if pointer.is_null() {
            let Ok(new_layout) = Layout::from_size_align(new_size, layout.align()) else {
                return std::ptr::null_mut();
            };
            // SAFETY: this follows alloc's contract for the derived layout.
            return unsafe { self.alloc(new_layout) };
        }
        if new_size == 0 {
            // SAFETY: pointer and layout are the original allocation pair.
            unsafe { self.dealloc(pointer, layout) };
            return std::ptr::null_mut();
        }

        let Some(_guard) = GlobalCallGuard::enter() else {
            // Re-entrant allocations originate from System.
            // SAFETY: forwarded with GlobalAlloc's realloc contract.
            return unsafe { System.realloc(pointer, layout, new_size) };
        };

        if self.initialized_owner(pointer as usize).is_none() {
            // SAFETY: non-bomalloc pointers produced by this adapter originate from System.
            return unsafe { System.realloc(pointer, layout, new_size) };
        }
        // SAFETY: address ownership was checked above and the GlobalAlloc
        // pointer/layout/new-size contract is inherited from the caller.
        unsafe { self.reallocate_bomalloc(pointer, layout, new_size) }
    }
}

impl BoGlobalAllocator {
    #[inline]
    unsafe fn reallocate_bomalloc(
        &self,
        pointer: *mut u8,
        layout: Layout,
        new_size: usize,
    ) -> *mut u8 {
        let Some(allocator) = self.initialized_owner(pointer as usize) else {
            return std::ptr::null_mut();
        };
        let Ok(new_layout) = Layout::from_size_align(new_size, layout.align()) else {
            return std::ptr::null_mut();
        };
        let new_pointer = if crate::allocator::thread_cache_available() {
            let Ok(allocation) = allocator.allocate(new_layout) else {
                return std::ptr::null_mut();
            };
            allocation.as_ptr() as *mut u8
        } else {
            // A realloc from a late TLS destructor cannot re-enter bomalloc's
            // destroyed thread cache. Moving this one object to System keeps
            // the old bomalloc allocation valid until the copy succeeds.
            // SAFETY: new_layout is valid and non-zero.
            unsafe { System.alloc(new_layout) }
        };
        if new_pointer.is_null() {
            return std::ptr::null_mut();
        }
        // SAFETY: both allocations are live and disjoint; copy stays within the
        // smaller of the old and new requested sizes.
        unsafe {
            std::ptr::copy_nonoverlapping(pointer, new_pointer, layout.size().min(new_size));
            allocator.deallocate(NonNull::new_unchecked(pointer), layout);
        }
        new_pointer
    }
}