bomalloc 0.3.0

A fragmentation-aware experimental allocator built around address-span ownership
Documentation
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};

const COUNTER_STRIPES: usize = 64;

#[repr(align(64))]
#[derive(Default)]
struct CounterStripe(AtomicU64);

pub(crate) struct StripedCounter {
    stripes: [CounterStripe; COUNTER_STRIPES],
}

impl Default for StripedCounter {
    fn default() -> Self {
        Self {
            stripes: std::array::from_fn(|_| CounterStripe::default()),
        }
    }
}

impl StripedCounter {
    #[inline]
    pub(crate) fn add(&self, owner: u64, value: u64) {
        self.stripes[owner as usize % COUNTER_STRIPES]
            .0
            .fetch_add(value, Ordering::Relaxed);
    }

    fn load(&self) -> u64 {
        self.stripes
            .iter()
            .map(|stripe| stripe.0.load(Ordering::Relaxed))
            .sum()
    }
}

#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct StatsSnapshot {
    pub reserved_bytes: usize,
    pub committed_bytes: usize,
    /// Committed bytes in empty dedicated reservations retained for fast reuse.
    pub empty_dedicated_committed_bytes: usize,
    /// Bytes whose obsolete contents were offered back to the OS while their
    /// committed virtual address ranges remain retained for reuse.
    pub discarded_bytes: usize,
    pub requested_live_bytes: usize,
    pub usable_live_bytes: usize,
    pub metadata_bytes: usize,
    pub green_spans: usize,
    pub white_spans: usize,
    pub red_spans: usize,
    pub black_spans: usize,
    /// Empty Small spans that are still owned and therefore appear Black to a
    /// foreign allocator until a slow-path transfer succeeds.
    pub empty_black_spans: usize,
    pub young_spans: usize,
    pub sealed_black_spans: usize,
    pub sealed_hole_bytes: usize,
    pub local_free_spans: usize,
    pub splits: u64,
    pub merges: u64,
    pub steals: u64,
    /// Cross-owner transfers of completely empty active Small spans.
    pub empty_black_reclaims: u64,
    pub cas_failures: u64,
    pub random_jumps: u64,
    pub cohort_promotions: u64,
    pub cohort_recycles: u64,
    /// Number of class-matching descriptors inspected by whole-class searches.
    pub global_candidate_probes: u64,
    /// Searches that obtained an allocation after taking at least one random jump.
    pub jump_successes: u64,
    /// Candidate probes performed after a jump changed the scan origin.
    pub post_jump_probes: u64,
    pub locality_probes: u64,
    pub locality_hits: u64,
    pub global_searches: u64,
    pub topology_snapshot_publishes: u64,
    pub reserved_span_activations: u64,
    pub territory_extensions: u64,
    pub territory_extension_spans: u64,
    pub reserved_run_activations: u64,
    pub run_territory_extensions: u64,
    pub run_territory_extension_extents: u64,
    pub run_local_window_refills: u64,
    pub run_local_window_hits: u64,
    pub run_local_window_releases: u64,
    pub tree_root_replacements: u64,
    pub tree_root_collapses: u64,
    pub tree_leaf_splits: u64,
    pub tree_parent_inserts: u64,
    pub tree_internal_splits: u64,
    pub tree_logical_removes: u64,
    pub tree_leaf_upserts: u64,
    pub tree_redirects: u64,
    pub tree_cross_parent_redirects: u64,
    pub tree_internal_redirects: u64,
    pub tree_internal_redistributions: u64,
    pub tree_parent_cleanups: u64,
    pub tree_batch_replacements: u64,
    pub tree_help_calls: u64,
    pub tree_operation_aborts: u64,
    pub tree_candidate_discards: u64,
    pub tree_node_slots: usize,
    pub tree_live_nodes: usize,
    pub tree_retired_nodes: u64,
    pub tree_reused_nodes: u64,
    pub tree_node_object_slots: usize,
    pub tree_live_node_objects: usize,
    pub tree_reused_node_objects: u64,
    pub span_descriptor_slots: usize,
    pub live_span_descriptors: usize,
    pub reused_span_descriptors: u64,
    pub bitmap_slots: usize,
    pub live_bitmaps: usize,
    pub reused_bitmaps: u64,
    pub payload_vector_slots: usize,
    pub live_payload_vectors: usize,
    pub reused_payload_vectors: u64,
    pub tree_metadata_blocks: usize,
    pub tree_metadata_reserved_bytes: usize,
    pub remote_batches_drained: u64,
    pub remote_blocks_drained: u64,
    pub decommits: u64,
    pub discards: u64,
    pub chunk_releases: u64,
}

#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct TrimStats {
    pub spans_reclaimed: usize,
    pub bytes_decommitted: usize,
    pub chunks_released: usize,
    pub bytes_released: usize,
}

#[derive(Default)]
pub(crate) struct AtomicStats {
    pub reserved: AtomicUsize,
    pub committed: AtomicUsize,
    pub splits: AtomicU64,
    pub merges: AtomicU64,
    pub steals: AtomicU64,
    pub empty_black_reclaims: AtomicU64,
    pub cas_failures: AtomicU64,
    pub random_jumps: AtomicU64,
    pub cohort_promotions: AtomicU64,
    pub cohort_recycles: AtomicU64,
    pub(crate) global_candidate_probes: StripedCounter,
    pub(crate) jump_successes: StripedCounter,
    pub(crate) post_jump_probes: StripedCounter,
    pub(crate) locality_probes: StripedCounter,
    pub(crate) locality_hits: StripedCounter,
    pub(crate) global_searches: StripedCounter,
    pub topology_snapshot_publishes: AtomicU64,
    pub reserved_span_activations: AtomicU64,
    pub territory_extensions: AtomicU64,
    pub territory_extension_spans: AtomicU64,
    pub reserved_run_activations: AtomicU64,
    pub run_territory_extensions: AtomicU64,
    pub run_territory_extension_extents: AtomicU64,
    pub run_local_window_refills: AtomicU64,
    pub(crate) run_local_window_hits: StripedCounter,
    pub run_local_window_releases: AtomicU64,
    pub remote_batches_drained: AtomicU64,
    pub remote_blocks_drained: AtomicU64,
    pub decommits: AtomicU64,
    pub discards: AtomicU64,
    pub chunk_releases: AtomicU64,
}

impl AtomicStats {
    pub fn snapshot(&self) -> StatsSnapshot {
        StatsSnapshot {
            reserved_bytes: self.reserved.load(Ordering::Relaxed),
            committed_bytes: self.committed.load(Ordering::Relaxed),
            splits: self.splits.load(Ordering::Relaxed),
            merges: self.merges.load(Ordering::Relaxed),
            steals: self.steals.load(Ordering::Relaxed),
            empty_black_reclaims: self.empty_black_reclaims.load(Ordering::Relaxed),
            cas_failures: self.cas_failures.load(Ordering::Relaxed),
            random_jumps: self.random_jumps.load(Ordering::Relaxed),
            cohort_promotions: self.cohort_promotions.load(Ordering::Relaxed),
            cohort_recycles: self.cohort_recycles.load(Ordering::Relaxed),
            global_candidate_probes: self.global_candidate_probes.load(),
            jump_successes: self.jump_successes.load(),
            post_jump_probes: self.post_jump_probes.load(),
            locality_probes: self.locality_probes.load(),
            locality_hits: self.locality_hits.load(),
            global_searches: self.global_searches.load(),
            topology_snapshot_publishes: self.topology_snapshot_publishes.load(Ordering::Relaxed),
            reserved_span_activations: self.reserved_span_activations.load(Ordering::Relaxed),
            territory_extensions: self.territory_extensions.load(Ordering::Relaxed),
            territory_extension_spans: self.territory_extension_spans.load(Ordering::Relaxed),
            reserved_run_activations: self.reserved_run_activations.load(Ordering::Relaxed),
            run_territory_extensions: self.run_territory_extensions.load(Ordering::Relaxed),
            run_territory_extension_extents: self
                .run_territory_extension_extents
                .load(Ordering::Relaxed),
            run_local_window_refills: self.run_local_window_refills.load(Ordering::Relaxed),
            run_local_window_hits: self.run_local_window_hits.load(),
            run_local_window_releases: self.run_local_window_releases.load(Ordering::Relaxed),
            remote_batches_drained: self.remote_batches_drained.load(Ordering::Relaxed),
            remote_blocks_drained: self.remote_blocks_drained.load(Ordering::Relaxed),
            decommits: self.decommits.load(Ordering::Relaxed),
            discards: self.discards.load(Ordering::Relaxed),
            chunk_releases: self.chunk_releases.load(Ordering::Relaxed),
            ..StatsSnapshot::default()
        }
    }
}