bomalloc 0.3.0

A fragmentation-aware experimental allocator built around address-span ownership
Documentation
use core::ffi::c_void;

use libc::{
    madvise, mmap, munmap, sysconf, MADV_DONTNEED, MAP_ANONYMOUS, MAP_FAILED, MAP_NORESERVE,
    MAP_PRIVATE, PROT_READ, PROT_WRITE, _SC_PAGESIZE,
};

use crate::os::BackingStore;
use crate::BoAllocError;

const ALLOCATION_GRANULARITY: usize = 64 * 1024;
const METADATA_BLOCK_BYTES: usize = 64 * 1024;

pub(crate) struct PlatformBacking {
    page_size: usize,
}

impl PlatformBacking {
    pub(crate) fn new() -> Result<Self, BoAllocError> {
        // SAFETY: sysconf has no pointer preconditions and only queries process state.
        let page_size = unsafe { sysconf(_SC_PAGESIZE) };
        if page_size <= 0 {
            return Err(BoAllocError::UnsupportedPlatform);
        }
        let page_size = page_size as usize;
        if page_size > ALLOCATION_GRANULARITY
            || !page_size.is_power_of_two()
            || ALLOCATION_GRANULARITY % page_size != 0
        {
            return Err(BoAllocError::UnsupportedPlatform);
        }
        Ok(Self { page_size })
    }
}

impl BackingStore for PlatformBacking {
    fn page_size(&self) -> usize {
        self.page_size
    }

    fn allocation_granularity(&self) -> usize {
        ALLOCATION_GRANULARITY
    }

    unsafe fn reserve(&self, size: usize) -> Result<usize, BoAllocError> {
        debug_assert_ne!(size, 0);
        debug_assert_eq!(size % self.page_size, 0);
        let mapped_size = size
            .checked_add(ALLOCATION_GRANULARITY)
            .ok_or(BoAllocError::AddressSpaceExhausted)?;
        // Linux anonymous mappings are demand-paged. Keeping the reservation
        // read/write and using MAP_NORESERVE lets activation remain a logical
        // commit with no per-span mprotect syscall; physical pages are still
        // supplied only on first touch. No address in an inactive range is ever
        // returned to the caller.
        // SAFETY: a null hint requests a fresh private anonymous mapping.
        let raw = unsafe {
            mmap(
                std::ptr::null_mut(),
                mapped_size,
                PROT_READ | PROT_WRITE,
                MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE,
                -1,
                0,
            )
        };
        if raw == MAP_FAILED {
            return Err(BoAllocError::AddressSpaceExhausted);
        }
        let raw = raw as usize;
        let aligned = raw
            .checked_add(ALLOCATION_GRANULARITY - 1)
            .map(|value| value & !(ALLOCATION_GRANULARITY - 1))
            .ok_or(BoAllocError::AddressSpaceExhausted)?;
        let prefix = aligned - raw;
        let suffix = mapped_size - prefix - size;
        if prefix != 0 {
            // SAFETY: prefix is a page-aligned leading subrange of this new mapping.
            if unsafe { munmap(raw as *mut c_void, prefix) } != 0 {
                // SAFETY: best-effort cleanup of the still-private mapping.
                let _ = unsafe { munmap(raw as *mut c_void, mapped_size) };
                return Err(BoAllocError::OutOfMemory);
            }
        }
        if suffix != 0 {
            // SAFETY: suffix is the page-aligned trailing subrange after the result.
            if unsafe { munmap((aligned + size) as *mut c_void, suffix) } != 0 {
                // SAFETY: prefix was already removed; this range owns the remainder.
                let _ = unsafe { munmap(aligned as *mut c_void, size + suffix) };
                return Err(BoAllocError::OutOfMemory);
            }
        }
        Ok(aligned)
    }

    unsafe fn commit(&self, address: usize, size: usize) -> Result<(), BoAllocError> {
        debug_assert_eq!(address % self.page_size, 0);
        debug_assert_eq!(size % self.page_size, 0);
        // reserve() deliberately keeps Linux reservations read/write. Anonymous
        // MAP_NORESERVE pages do not consume physical memory until first touch,
        // so logical commit needs no kernel transition. Keeping the method makes
        // the allocator's cross-platform committed-byte accounting unchanged.
        Ok(())
    }

    unsafe fn decommit(&self, address: usize, size: usize) -> Result<(), BoAllocError> {
        debug_assert_eq!(address % self.page_size, 0);
        debug_assert_eq!(size % self.page_size, 0);
        // MADV_DONTNEED immediately discards resident anonymous pages while
        // preserving the mapping and its read/write protection. A later access
        // observes zero-filled demand pages, so reactivation remains syscall-free.
        // The caller freezes this exact range before entering the backend.
        // SAFETY: address and size identify an owned page-aligned mapping range.
        if unsafe { madvise(address as *mut c_void, size, MADV_DONTNEED) } != 0 {
            Err(BoAllocError::OutOfMemory)
        } else {
            Ok(())
        }
    }

    unsafe fn discard(&self, address: usize, size: usize) -> Result<(), BoAllocError> {
        debug_assert_eq!(address % self.page_size, 0);
        debug_assert_eq!(size % self.page_size, 0);
        // Linux reservations remain read/write, so MADV_DONTNEED is both the
        // logical decommit and the cheaper discard-with-address-retention path.
        // SAFETY: address and size identify an owned page-aligned mapping range.
        if unsafe { madvise(address as *mut c_void, size, MADV_DONTNEED) } != 0 {
            Err(BoAllocError::OutOfMemory)
        } else {
            Ok(())
        }
    }

    unsafe fn release(&self, address: usize, size: usize) -> Result<(), BoAllocError> {
        debug_assert_eq!(address % ALLOCATION_GRANULARITY, 0);
        debug_assert_eq!(size % self.page_size, 0);
        // SAFETY: caller supplies the exact base and length returned by reserve.
        if unsafe { munmap(address as *mut c_void, size) } != 0 {
            Err(BoAllocError::OutOfMemory)
        } else {
            Ok(())
        }
    }
}

pub(crate) unsafe fn reserve_commit_metadata_block(size: usize) -> Result<usize, BoAllocError> {
    debug_assert_eq!(size, METADATA_BLOCK_BYTES);
    // SAFETY: request a private read/write mapping used only by allocator metadata.
    let pointer = unsafe {
        mmap(
            std::ptr::null_mut(),
            size,
            PROT_READ | PROT_WRITE,
            MAP_PRIVATE | MAP_ANONYMOUS,
            -1,
            0,
        )
    };
    if pointer == MAP_FAILED {
        Err(BoAllocError::OutOfMemory)
    } else {
        Ok(pointer as usize)
    }
}

pub(crate) unsafe fn release_metadata_block(address: usize) -> Result<(), BoAllocError> {
    // Every typed metadata slab uses one fixed 64 KiB mapping per block.
    // SAFETY: caller passes the original base of a metadata block.
    if unsafe { munmap(address as *mut c_void, METADATA_BLOCK_BYTES) } != 0 {
        Err(BoAllocError::OutOfMemory)
    } else {
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn reservation_round_trips_commit_and_decommit() {
        let backing = PlatformBacking::new().unwrap();
        let size = 2 * ALLOCATION_GRANULARITY;
        // SAFETY: the test owns the complete reservation until the final release.
        let address = unsafe { backing.reserve(size).unwrap() };
        assert_eq!(address % ALLOCATION_GRANULARITY, 0);

        // SAFETY: the first page is an owned page-aligned reservation subrange.
        unsafe { backing.commit(address, backing.page_size()).unwrap() };
        // SAFETY: commit made this byte writable.
        unsafe { (address as *mut u8).write(0xa5) };
        // SAFETY: no access overlaps replacement of the committed test page.
        unsafe { backing.decommit(address, backing.page_size()).unwrap() };
        // SAFETY: recommit restores read/write access to the same reserved page.
        unsafe { backing.commit(address, backing.page_size()).unwrap() };
        // MADV_DONTNEED must provide zero-filled contents on the next access.
        assert_eq!(unsafe { (address as *const u8).read() }, 0);

        // SAFETY: address and size exactly match the live reservation.
        unsafe { backing.release(address, size).unwrap() };
    }

    #[test]
    fn metadata_block_round_trips() {
        // SAFETY: this test exclusively owns the returned metadata mapping.
        let address = unsafe { reserve_commit_metadata_block(METADATA_BLOCK_BYTES).unwrap() };
        // SAFETY: metadata mappings are returned read/write.
        unsafe { (address as *mut u64).write(0xfeed_face_cafe_beef) };
        assert_eq!(
            unsafe { (address as *const u64).read() },
            0xfeed_face_cafe_beef
        );
        // SAFETY: address is the original base and remains live.
        unsafe { release_metadata_block(address).unwrap() };
    }
}