multitude 0.4.0

// Copyright (c) Microsoft Corporation.
// Licensed under the MIT License.

//! Intrusive singly-linked list of retired chunks pending drop replay.
//!
//! The arena keeps a LIFO list of [`Chunk`]s it has rotated out of
//! `current` but cannot recycle yet, because they carry arena-reference
//! drop entries (`&mut T` / [`crate::vec::Vec`] / [`crate::strings::String`]
//! backing bytes) whose destructors must run at reset / arena drop. Each
//! chunk on the list holds one strong reference — the same `+1` that the
//! originally-retiring [`ChunkMutator`] held — plus, possibly, additional
//! references owned by escaped `Arc`/`Box` handles living in the same chunk.
//!
//! Linkage is **intrusive**: each `Chunk` carries a [`next`](Chunk::next)
//! field used to thread chunks together without per-retirement heap
//! allocation. The list head holds a thin `*mut u8` to the topmost chunk's
//! header (`null` for empty); the fat DST pointer is reconstructed via
//! [`Chunk::header_to_fat`] when the list is drained.
//!
//! Only two writers ever touch this structure:
//! * [`Arena::refill`](crate::Arena) pushes a rotated-out chunk that still
//!   carries drop entries.
//! * [`Arena::reset`](crate::Arena), `Arena::drop`, and the
//!   oversized-Vec-grow path drain (or splice from) the list.
//!
//! The drain is iterative *and* re-checks `head` on each pass so that
//! reentrant pushes performed by user-supplied chunk-teardown destructors
//! (drop shims invoked from `Chunk::teardown_and_release`) never leak.

use core::cell::Cell;
use core::marker::PhantomData;
use core::ptr::{self, NonNull};

use allocator_api2::alloc::Allocator;

use crate::internal::chunk::Chunk;
use crate::internal::chunk_mutator::ChunkMutator;

/// LIFO list of retired chunks linked through each chunk's own
/// [`next`](Chunk::next) field.
///
/// `head` is a thin `*mut u8` header pointer (or `null`). Carrying the
/// metadata-less form keeps the head field 8 bytes and matches the encoding
/// the cache freelist uses elsewhere in the chunk provider; the fat pointer
/// is rebuilt via `header_to_fat` when chunks are popped.
pub(in crate::arena) struct RetiredLocalChunks<A: Allocator + Clone> {
    head: Cell<*mut u8>,
    /// `Chunk<A>` is only referenced via raw pointers from this list; this
    /// marker propagates `A`'s `Send` / auto-traits to the list type.
    _marker: PhantomData<ChunkMutator<A>>,
}

// SAFETY: when `ChunkMutator<A>` is `Send`, so is this list — every node
// logically holds the same `+1` a mutator does and is single-owner; moving
// the arena between threads moves every node with it. `!Sync` is inherited
// from `Cell`, matching the bound `Arena` needs.
unsafe impl<A: Allocator + Clone + Send> Send for RetiredLocalChunks<A> {}

impl<A: Allocator + Clone> RetiredLocalChunks<A> {
    #[inline]
    pub(in crate::arena) const fn new() -> Self {
        Self {
            head: Cell::new(ptr::null_mut()),
            _marker: PhantomData,
        }
    }

    /// Retire `mutator`'s chunk by linking its header onto the list head.
    /// Empty mutators are a no-op (nothing to retire).
    ///
    /// The mutator's `+1` becomes the list's; its `Drop` is bypassed (via
    /// [`ChunkMutator::forget_into_chunk`], which publishes the drop count
    /// but does *not* replay it) so the reference destructors are deferred
    /// to reset / arena drop.
    #[inline]
    pub(in crate::arena) fn push(&self, mutator: ChunkMutator<A>) {
        let Some(chunk) = mutator.forget_into_chunk() else {
            return;
        };
        // SAFETY: we just took ownership of the +1 on `chunk`, so it is live
        // and the owning thread has exclusive access to its `next` link.
        unsafe {
            let prev_head = self.head.replace(chunk.cast::<u8>().as_ptr());
            Chunk::set_next(chunk, prev_head);
        }
    }

    /// Drop every retained chunk. Iterative on two levels:
    /// * The inner `while` walks the chain one node at a time (re-using the
    ///   chunk's own `next` link to advance), so a long list never overflows
    ///   the stack via recursive `Drop`.
    /// * The outer `loop` re-checks `self.head` after each chain drain so
    ///   reentrant pushes performed by chunk-teardown drop shims are
    ///   captured rather than leaked.
    pub(in crate::arena) fn clear(&self) {
        loop {
            let mut cur = self.head.replace(ptr::null_mut());
            if cur.is_null() {
                return;
            }
            while !cur.is_null() {
                // SAFETY: while a node sits in this list we own its `+1`, so
                // the chunk allocation is live. `header_to_fat` reads the
                // header's `capacity` field through the live allocation.
                unsafe {
                    let fat = Chunk::<A>::header_to_fat(cur);
                    let chunk = NonNull::new_unchecked(fat);
                    // Detach the node *before* releasing its refcount: a
                    // panicking drop shim invoked from `teardown_and_release`
                    // must not see this chunk re-entrantly through the list.
                    // We also clear the field so the chunk, if recycled into
                    // the provider cache, starts in a clean state.
                    let next = Chunk::next(chunk);
                    Chunk::set_next(chunk, ptr::null_mut());
                    Self::release_retired_chunk(chunk);
                    cur = next;
                }
            }
        }
    }

    /// Release the list's `+1` on a chunk that has been unlinked.
    ///
    /// The reference destructors are replayed *eagerly* here (before the
    /// `+1` is released) so they run even when escaped `Arc`/`Box` handles
    /// in the same chunk keep its refcount above zero. After replay the
    /// count is `0`, so the subsequent `teardown_and_release` (taken only
    /// when this `+1` was the last reference) does not run them again.
    ///
    /// # Safety
    ///
    /// Caller must have just removed `chunk` from this list and must not
    /// retain any further references to it.
    #[inline]
    unsafe fn release_retired_chunk(chunk: NonNull<Chunk<A>>) {
        // SAFETY: caller hands over the list's `+1`. Replay any pending
        // arena-reference drops on the owning thread, then release the `+1`;
        // if it was the last reference, route through teardown to recycle.
        unsafe {
            Chunk::replay_pending_drops(chunk);
            if chunk.as_ref().dec_ref() {
                Chunk::teardown_and_release(chunk);
            }
        }
    }
}

impl<A: Allocator + Clone> Drop for RetiredLocalChunks<A> {
    fn drop(&mut self) {
        self.clear();
    }
}

#[cfg(test)]
mod tests {
    use allocator_api2::alloc::Global;

    use super::*;

    /// Pushing a chunkless (empty) mutator is a no-op: `forget_into_chunk`
    /// yields `None`, so `push` early-returns without retaining anything.
    #[test]
    fn push_chunkless_mutator_is_noop() {
        let retired = RetiredLocalChunks::<Global>::new();
        retired.push(ChunkMutator::<Global>::empty());
        // Nothing was retained; the list drops cleanly.
    }
}