// Copyright 2017 the authors. See the 'Copyright and license' section of the
// README.md file at the top-level directory of this repository.
//
// Licensed under the Apache License, Version 2.0 (the LICENSE file). This file
// may not be copied, modified, or distributed except according to those terms.

// So clippy doesn't complain that SunOS isn't in tick marks
#![cfg_attr(feature = "cargo-clippy", allow(doc_markdown))]
//! An `ObjectAlloc` which allocates objects in contiguous slabs and caches constructed objects.
//!
//! # Design
//!
//! The `SlabAlloc` is based largely on the slab allocator design originally inroduced in the
//! SunOS 5.4 kernel and described in depth in [The Slab Allocator: An Object-Caching Kernel Memory
//! Allocator][1]. This implementation stays somewhat true to the original design, although it
//! includes a number of performance improvements and modifications for user-land.
//!
//! The `SlabAlloc` provides a number of performance benefits:
//!
//! * As with any `ObjectAlloc`, object caching reduces the overhead of object initialization in
//!   many cases.
//! * As with any `ObjectAlloc`, only needing to allocate objects of a particular size and
//!   alignment allows for optimizations not available to general-purpose allocators.
//! * Internal and external fragmentation are kept to a minimum.
//! * A "coloring" scheme described in Section 4 of the original paper improves cache utilization.
//!
//! [1]: http://www.usenix.org/publications/library/proceedings/bos94/full_papers/bonwick.ps

// TODO:
// - Sort partially-full slabs so that the emptiest slabs come first. This makes it more likely
//   that almost-full slabs will become completely full and eligible to be freed back to the system.
//   NOTE: Consider using a simplified heap like the one used in SuperMalloc.
// - Find a fitting algorithm slabs that trades off space usage with ability to perform coloring
//   (rather than always prioritizing space usage)
// - Would it be worth it to special-case 64-byte allocations to ensure that they are 64-byte
//   aligned so that each object gets its own cache line? It should be sufficient to artificially
//   override the align parameter to be 64 bytes when the size is 64 bytes.
// - Add a feature flag to disable using aligned slabs for backing sizes larger than a page (to
//   enable benchmarking aligned vs large slabs)
// - Consider improvements to the slab size selection algorithm. For example, might we be willing
//   to take sub-optimal space utilization in order to use an aligned slab with fewer than the
//   number of objects per slab, and thus reap the performance benefits of aligned slabs?
// - Make sure everything is exception-safe.

// Guarantees made by Rust about the memory layout (see https://doc.rust-lang.org/nomicon/repr-rust.html):
// - Addresses of type T must be a multiple of T's alignment
// - All alignments must be powers of two
// - T's size must be a multiple of its alignment
//   - Corrollary: given an array of T, the offset of the ith element is just i * sizeof(T)

#![cfg_attr(not(feature = "std"), no_std)]
#![feature(alloc, allocator_api)]
#![feature(plugin)]
#![cfg_attr(test, feature(test))]

#![plugin(interpolate_idents)]

mod aligned;
mod backing;
mod init;
mod large;
mod ptr_map;
mod stack;
#[cfg(test)]
mod tests;
mod util;

extern crate alloc;
#[cfg(feature = "std")]
extern crate core;
#[macro_use]
extern crate lazy_static;
extern crate object_alloc;
#[cfg(test)]
#[macro_use]
extern crate object_alloc_test;
extern crate sysconf;

use core::marker::PhantomData;
use core::default::Default;
use core::mem;
use self::util::list::*;
use util::workingset::WorkingSet;
use init::*;
use self::init::InitSystem;
use self::object_alloc::{Exhausted, ObjectAlloc, UntypedObjectAlloc};
use self::alloc::allocator::Layout;

pub use backing::BackingAlloc;
#[cfg(feature = "std")]
use backing::heap::HeapBackingAlloc;
#[cfg(feature = "os")]
use backing::mmap::MmapBackingAlloc;

use init::NopInitSystem;
type DefaultInitSystem<T> = init::InitInitSystem<T, init::DefaultInitializer<T>>;
type FnInitSystem<T, F> = init::InitInitSystem<T, init::FnInitializer<T, F>>;
type UnsafeFnInitSystem<T, F> = init::InitInitSystem<T, init::UnsafeFnInitializer<T, F>>;

lazy_static!{
    static ref PAGE_SIZE: usize = self::sysconf::page::pagesize();
    static ref PAGE_ALIGN_MASK: usize = !(*PAGE_SIZE - 1);
}

const WORKING_PERIOD_SECONDS: u64 = 15;
const OBJECTS_PER_SLAB: usize = 8;

/// A typed slab allocator.
pub struct SlabAlloc<T, I: InitSystem, B: BackingAlloc> {
    alloc: PrivateSlabAlloc<I, B>,
    _marker: PhantomData<T>,
}

/// An untyped slab allocator.
pub struct UntypedSlabAlloc<I: InitSystem, B: BackingAlloc> {
    alloc: PrivateUntypedSlabAlloc<I, B>,
}

enum PrivateSlabAlloc<I: InitSystem, B: BackingAlloc> {
    Aligned(SizedSlabAlloc<I, aligned::System<B::Aligned>>),
    Large(SizedSlabAlloc<I, large::System<B::Large>>),
}

enum PrivateUntypedSlabAlloc<I: InitSystem, B: BackingAlloc> {
    Aligned(SizedSlabAlloc<I, aligned::System<B::Aligned>>),
    Large(SizedSlabAlloc<I, large::System<B::Large>>),
}

/// A builder for `SlabAlloc`s.
pub struct SlabAllocBuilder<T, I: InitSystem> {
    init: I,
    layout: Layout,
    _marker: PhantomData<T>,
}

impl<T, I: InitSystem> SlabAllocBuilder<T, I> {
    /// Updates the alignment guaranteed by the allocator.
    ///
    /// `align` must not be greater than the size of `T` (that is, `core::mem::size_of::<T>()`),
    /// must not be greater than the system's page size, and must be a power of two. The size of
    /// `T` must be a multiple of `align`.
    ///
    /// If `align` is called multiple times, then the largest specified alignment will be used.
    /// Since all alignments must be powers of two, allocations which satisfy the largest specified
    /// alignment will also satisfy all smaller alignments.
    pub fn align(mut self, align: usize) -> SlabAllocBuilder<T, I> {
        assert!(align.is_power_of_two());
        assert!(align <= mem::size_of::<T>());
        assert_eq!(mem::size_of::<T>() % align, 0);
        assert!(align <= *PAGE_SIZE);
        self.layout = self.layout.align_to(align);
        self
    }

    /// Builds a `SlabAlloc` whose memory is backed by the heap.
    #[cfg(feature = "std")]
    pub fn build(self) -> SlabAlloc<T, I, HeapBackingAlloc> {
        use backing::heap::{get_aligned, get_large};
        self.build_backing(get_aligned, get_large)
    }

    /// Builds a `SlabAlloc` whose memory is backed by mmap.
    ///
    /// On Unix and Linux, `mmap` is used. On Windows, `VirtualAlloc` is used.
    #[cfg(feature = "os")]
    pub fn build_mmap(self) -> SlabAlloc<T, I, MmapBackingAlloc> {
        use backing::mmap::{get_aligned, get_large};
        self.build_backing(get_aligned, get_large)
    }

    /// Builds an `UntypedSlabAlloc` whose memory is backed by the heap.
    #[cfg(feature = "std")]
    pub fn build_untyped(self) -> UntypedSlabAlloc<I, HeapBackingAlloc> {
        use backing::heap::{get_aligned, get_large};
        self.build_untyped_backing(get_aligned, get_large)
    }

    /// Builds an `UntypedSlabAlloc` whose memory is backed by mmap.
    ///
    /// On Unix and Linux, `mmap` is used. On Windows, `VirtualAlloc` is used.
    #[cfg(feature = "os")]
    pub fn build_untyped_mmap(self) -> UntypedSlabAlloc<I, MmapBackingAlloc> {
        use backing::mmap::{get_aligned, get_large};
        self.build_untyped_backing(get_aligned, get_large)
    }

    /// Builds a new `SlabAlloc` with a custom memory provider.
    ///
    /// `build_backing` builds a new `SlabAlloc` from the configuration `self`. `SlabAlloc`s get
    /// their memory from `UntypedObjectAlloc`s which allocate the memory necessary to back a
    /// single slab. Under the hood, slab allocators use two types of slabs - "aligned" slabs and
    /// "large" slabs. Aligned slabs perform better, but are not always supported for all slab
    /// sizes. Large slabs do not perform as well, but are supported for all slab sizes. In
    /// particular, aligned slabs require that the memory used to back them is aligned to its own
    /// size (ie, a 16K slab has alignment 16K, etc), while large slabs only require page alignment
    /// regardless of the slab size. All slabs are always at least one page in size and are always
    /// page-aligned at a minimum.
    ///
    /// Because support for a particular slab size may not be knowable until runtime (e.g., it may
    /// depend on the page size, which can vary by system), which slab type will be used cannot be
    /// known at compile time. Instead, `build_backing` computes the ideal aligned slab size, and
    /// calls `get_aligned` with a `Layout` describing that size. `get_aligned` returns an `Option`
    ///  - `None` if the requested size is not supported, and `Some` if the size is supported. If
    /// the size is not supported, `build_backing` will fall back to using large slabs, and will
    /// call `get_large` to get an allocator. It will only call `get_large` with a `Layout` that is
    /// required to be supported (at least a page in size and page-aligned), so `get_large` returns
    /// an allocator directly rather than an `Option`.
    pub fn build_backing<B, A, L>(self, get_aligned: A, get_large: L) -> SlabAlloc<T, I, B>
        where B: BackingAlloc,
              A: Fn(Layout) -> Option<B::Aligned>,
              L: Fn(Layout) -> B::Large
    {
        let layout = util::misc::satisfy_min_align(self.layout.clone(), I::min_align());
        let aligned_backing_size = aligned::backing_size_for::<I>(&layout);
        let aligned_slab_layout =
            Layout::from_size_align(aligned_backing_size, aligned_backing_size).unwrap();
        SlabAlloc {
            alloc: if let Some(alloc) = get_aligned(aligned_slab_layout) {
                let data = aligned::System::new(layout, alloc).unwrap();
                PrivateSlabAlloc::Aligned(SizedSlabAlloc::new(self.init, self.layout, data))
            } else {
                let backing_size = large::backing_size_for::<I>(&layout);
                let slab_layout = Layout::from_size_align(backing_size, *PAGE_SIZE).unwrap();
                let data = large::System::new(layout, get_large(slab_layout)).unwrap();
                PrivateSlabAlloc::Large(SizedSlabAlloc::new(self.init, self.layout, data))
            },
            _marker: PhantomData,
        }
    }

    /// Builds a new `UntypedSlabAlloc` with a custom memory provider.
    ///
    /// `build_untyped_backing` is like `build_backing`, except that it builds an
    /// `UntypedSlabAlloc` instead of a `SlabAlloc`.
    pub fn build_untyped_backing<B, A, L>(self,
                                          get_aligned: A,
                                          get_large: L)
                                          -> UntypedSlabAlloc<I, B>
        where B: BackingAlloc,
              A: Fn(Layout) -> Option<B::Aligned>,
              L: Fn(Layout) -> B::Large
    {
        let layout = util::misc::satisfy_min_align(self.layout.clone(), I::min_align());
        let aligned_backing_size = aligned::backing_size_for::<I>(&layout);
        let aligned_slab_layout =
            Layout::from_size_align(aligned_backing_size, aligned_backing_size).unwrap();
        UntypedSlabAlloc {
            alloc: if let Some(alloc) = get_aligned(aligned_slab_layout) {
                let data = aligned::System::new(layout, alloc).unwrap();
                PrivateUntypedSlabAlloc::Aligned(SizedSlabAlloc::new(self.init, self.layout, data))
            } else {
                let backing_size = large::backing_size_for::<I>(&layout);
                let slab_layout = Layout::from_size_align(backing_size, *PAGE_SIZE).unwrap();
                let data = large::System::new(layout, get_large(slab_layout)).unwrap();
                PrivateUntypedSlabAlloc::Large(SizedSlabAlloc::new(self.init, self.layout, data))
            },
        }
    }
}

impl<T: Default> SlabAllocBuilder<T, DefaultInitSystem<T>> {
    /// Constructs a new builder for an allocator which uses `T::default` to initialize allocated
    /// objects.
    ///
    /// The constructed allocator will call `T::default` whenever a new object needs to be
    /// initialized.
    pub fn default() -> SlabAllocBuilder<T, DefaultInitSystem<T>> {
        SlabAllocBuilder {
            init: DefaultInitSystem::new(DefaultInitializer::new()),
            layout: Layout::new::<T>(),
            _marker: PhantomData,
        }
    }
}

impl<T, F: Fn() -> T> SlabAllocBuilder<T, FnInitSystem<T, F>> {
    /// Constructs a new builder for an allocator which uses `f` to initialize allocated objects.
    ///
    /// The constructed allocator will call `f` whenever a new object needs to be initialized.
    pub fn func(f: F) -> SlabAllocBuilder<T, FnInitSystem<T, F>> {
        SlabAllocBuilder {
            init: FnInitSystem::new(FnInitializer::new(f)),
            layout: Layout::new::<T>(),
            _marker: PhantomData,
        }
    }
}

impl<T, F: Fn(*mut T)> SlabAllocBuilder<T, UnsafeFnInitSystem<T, F>> {
    /// Constructs a new builder for an allocator which uses `f` to initialize allocated objects.
    ///
    /// The constructed allocator will call `f` whenever a new object needs to be initialized.
    /// A pointer to the uninitialized memory will be passed, and it is `f`'s responsibility to
    /// initialize this memory to a valid instance of `T`.
    ///
    /// # Safety
    /// This function is `unsafe` because passing a function which does not abide by the documented
    /// contract could result in an allocator handing out uninitialized or invalid memory.
    pub unsafe fn unsafe_func(f: F) -> SlabAllocBuilder<T, UnsafeFnInitSystem<T, F>> {
        SlabAllocBuilder {
            init: UnsafeFnInitSystem::new(UnsafeFnInitializer::new(f)),
            layout: Layout::new::<T>(),
            _marker: PhantomData,
        }
    }
}

impl<T> SlabAllocBuilder<T, NopInitSystem> {
    /// Constructs a new builder for an allocator which does not initialize allocated objects.
    /// Objects returned by `alloc` are not guaranteed to be valid instances of `T`.
    ///
    /// # Safety
    /// This function is `unsafe` because it constructs an allocator which will hand out
    /// uninitialized memory.
    pub unsafe fn no_initialize() -> SlabAllocBuilder<T, NopInitSystem> {
        SlabAllocBuilder {
            init: NopInitSystem,
            layout: Layout::new::<T>(),
            _marker: PhantomData,
        }
    }
}

/// A builder for `UntypedSlabAlloc`s.
pub struct UntypedSlabAllocBuilder<I: InitSystem> {
    init: I,
    layout: Layout,
}

impl<I: InitSystem> UntypedSlabAllocBuilder<I> {
    /// Updates the alignment guaranteed by the allocator.
    ///
    /// `align` must not be greater than the size of allocated objects, must not be greater than
    /// the system's page size, and must be a power of two. The size of allocated objects must be a
    /// multiple of `align`.
    ///
    /// If `align` is called multiple times, then the largest specified alignment will be used.
    /// Since all alignments must be powers of two, allocations which satisfy the largest specified
    /// alignment will also satisfy all smaller alignments.
    pub fn align(mut self, align: usize) -> UntypedSlabAllocBuilder<I> {
        assert!(align.is_power_of_two());
        assert!(align <= self.layout.size());
        assert_eq!(self.layout.size() % align, 0);
        assert!(align <= *PAGE_SIZE);
        self.layout = self.layout.align_to(align);
        self
    }

    /// Builds an `UntypedSlabAlloc` whose memory is backed by the heap.
    #[cfg(feature = "std")]
    pub fn build(self) -> UntypedSlabAlloc<I, HeapBackingAlloc> {
        use backing::heap::{get_aligned, get_large};
        self.build_backing(get_aligned, get_large)
    }

    /// Builds an `UntypedSlabAlloc` whose memory is backed by mmap.
    ///
    /// On Unix and Linux, `mmap` is used. On Windows, `VirtualAlloc` is used.
    #[cfg(feature = "os")]
    pub fn build_mmap(self) -> UntypedSlabAlloc<I, MmapBackingAlloc> {
        use backing::mmap::{get_aligned, get_large};
        self.build_backing(get_aligned, get_large)
    }

    /// Builds a new `UntypedSlabAlloc` with a custom memory provider.
    ///
    /// `build_backing` builds a new `UntypedSlabAlloc` from the configuration `self`.
    /// `UntypedSlabAlloc`s get their memory from `UntypedObjectAlloc`s which allocate the memory
    /// necessary to back a single slab. Under the hood, slab allocators use two types of slabs -
    /// "aligned" slabs and "large" slabs. Aligned slabs perform better, but are not always
    /// supported for all slab sizes. Large slabs do not perform as well, but are supported for all
    /// slab sizes. In particular, aligned slabs require that the memory used to back them is
    /// aligned to its own size (ie, a 16K slab has alignment 16K, etc), while large slabs only
    /// require page alignment regardless of the slab size. All slabs are always at least one page
    /// in size and are always page-aligned at a minimum.
    ///
    /// Because support for a particular slab size may not be knowable until runtime (e.g., it may
    /// depend on the page size, which can vary by system), which slab type will be used cannot be
    /// known at compile time. Instead, `build_backing` computes the ideal aligned slab size, and
    /// calls `get_aligned` with a `Layout` describing that size. `get_aligned` returns an `Option`
    ///  - `None` if the requested size is not supported, and `Some` if the size is supported. If
    /// the size is not supported, `build_backing` will fall back to using large slabs, and will
    /// call `get_large` to get an allocator. It will only call `get_large` with a `Layout` that is
    /// required to be supported (at least a page in size and page-aligned), so `get_large` returns
    /// an allocator directly rather than an `Option`.
    pub fn build_backing<B, A, L>(self, get_aligned: A, get_large: L) -> UntypedSlabAlloc<I, B>
        where B: BackingAlloc,
              A: Fn(Layout) -> Option<B::Aligned>,
              L: Fn(Layout) -> B::Large
    {
        let layout = util::misc::satisfy_min_align(self.layout.clone(), I::min_align());
        let aligned_backing_size = aligned::backing_size_for::<I>(&layout);
        let aligned_slab_layout =
            Layout::from_size_align(aligned_backing_size, aligned_backing_size).unwrap();
        UntypedSlabAlloc {
            alloc: if let Some(alloc) = get_aligned(aligned_slab_layout) {
                let data = aligned::System::new(layout, alloc).unwrap();
                PrivateUntypedSlabAlloc::Aligned(SizedSlabAlloc::new(self.init, self.layout, data))
            } else {
                let backing_size = large::backing_size_for::<I>(&layout);
                let slab_layout = Layout::from_size_align(backing_size, *PAGE_SIZE).unwrap();
                let data = large::System::new(layout, get_large(slab_layout)).unwrap();
                PrivateUntypedSlabAlloc::Large(SizedSlabAlloc::new(self.init, self.layout, data))
            },
        }
    }
}

impl<F: Fn(*mut u8)> UntypedSlabAllocBuilder<UnsafeFnInitSystem<u8, F>> {
    pub fn func(layout: Layout, f: F) -> UntypedSlabAllocBuilder<UnsafeFnInitSystem<u8, F>> {
        UntypedSlabAllocBuilder {
            init: UnsafeFnInitSystem::new(UnsafeFnInitializer::new(f)),
            layout: layout,
        }
    }
}

impl UntypedSlabAllocBuilder<NopInitSystem> {
    pub fn new(layout: Layout) -> UntypedSlabAllocBuilder<NopInitSystem> {
        UntypedSlabAllocBuilder {
            init: NopInitSystem,
            layout: layout,
        }
    }
}

unsafe impl<T, I: InitSystem, B: BackingAlloc> ObjectAlloc<T> for SlabAlloc<T, I, B> {
    unsafe fn alloc(&mut self) -> Result<*mut T, Exhausted> {
        match self.alloc {
                PrivateSlabAlloc::Aligned(ref mut alloc) => alloc.alloc(),
                PrivateSlabAlloc::Large(ref mut alloc) => alloc.alloc(),
            }
            .map(|ptr| ptr as *mut T)
    }

    unsafe fn dealloc(&mut self, x: *mut T) {
        match self.alloc {
            PrivateSlabAlloc::Aligned(ref mut alloc) => alloc.dealloc(x as *mut u8),
            PrivateSlabAlloc::Large(ref mut alloc) => alloc.dealloc(x as *mut u8),
        }
    }
}

unsafe impl<T, I: InitSystem, B: BackingAlloc> UntypedObjectAlloc for SlabAlloc<T, I, B> {
    fn layout(&self) -> Layout {
        match self.alloc {
            PrivateSlabAlloc::Aligned(ref alloc) => alloc.layout.clone(),
            PrivateSlabAlloc::Large(ref alloc) => alloc.layout.clone(),
        }
    }

    unsafe fn alloc(&mut self) -> Result<*mut u8, Exhausted> {
        match self.alloc {
            PrivateSlabAlloc::Aligned(ref mut alloc) => alloc.alloc(),
            PrivateSlabAlloc::Large(ref mut alloc) => alloc.alloc(),
        }
    }

    unsafe fn dealloc(&mut self, x: *mut u8) {
        match self.alloc {
            PrivateSlabAlloc::Aligned(ref mut alloc) => alloc.dealloc(x),
            PrivateSlabAlloc::Large(ref mut alloc) => alloc.dealloc(x),
        }
    }
}

unsafe impl<I: InitSystem, B: BackingAlloc> UntypedObjectAlloc for UntypedSlabAlloc<I, B> {
    fn layout(&self) -> Layout {
        match self.alloc {
            PrivateUntypedSlabAlloc::Aligned(ref alloc) => alloc.layout.clone(),
            PrivateUntypedSlabAlloc::Large(ref alloc) => alloc.layout.clone(),
        }
    }

    unsafe fn alloc(&mut self) -> Result<*mut u8, Exhausted> {
        match self.alloc {
            PrivateUntypedSlabAlloc::Aligned(ref mut alloc) => alloc.alloc(),
            PrivateUntypedSlabAlloc::Large(ref mut alloc) => alloc.alloc(),
        }
    }

    unsafe fn dealloc(&mut self, x: *mut u8) {
        match self.alloc {
            PrivateUntypedSlabAlloc::Aligned(ref mut alloc) => alloc.dealloc(x),
            PrivateUntypedSlabAlloc::Large(ref mut alloc) => alloc.dealloc(x),
        }
    }
}

struct SizedSlabAlloc<I: InitSystem, S: SlabSystem<I>> {
    freelist: LinkedList<S::Slab>, // partial slabs first, followed by full slabs
    total_slabs: usize,
    num_full: usize, // number of full slabs
    refcnt: usize,
    full_slab_working_set: WorkingSet<usize>, /* minimum number of slabs full at every moment during this working period */

    slab_system: S,
    init_system: I,

    layout: Layout,
}

impl<I: InitSystem, S: SlabSystem<I>> SizedSlabAlloc<I, S> {
    fn new(init: I, layout: Layout, slabs: S) -> SizedSlabAlloc<I, S> {
        SizedSlabAlloc {
            freelist: LinkedList::new(),
            total_slabs: 0,
            num_full: 0,
            refcnt: 0,
            full_slab_working_set: WorkingSet::new(0),
            slab_system: slabs,
            init_system: init,
            layout: layout,
        }
    }

    fn alloc(&mut self) -> Result<*mut u8, Exhausted> {
        if self.freelist.size() == 0 {
            let ok = self.alloc_slab();
            if !ok {
                return Err(Exhausted);
            }
        }

        let slab = self.freelist.peek_front();
        if self.slab_system.is_full(slab) {
            self.num_full -= 1;
            self.full_slab_working_set.update_min(self.num_full);
        }

        let (obj, init_status) = self.slab_system.alloc(slab);
        if self.slab_system.is_empty(slab) {
            self.freelist.remove_front();
        }
        self.refcnt += 1;
        debug_assert_eq!(obj as usize % self.layout.align(), 0);
        self.init_system.init(obj, init_status);
        Ok(obj)
    }

    /// Allocate a new slab.
    ///
    /// Allocates a new slab and inserts it onto the back of the freelist. Returns `true` upon
    /// success and `false` upon failure.
    fn alloc_slab(&mut self) -> bool {
        let new = self.slab_system.alloc_slab();
        if new.is_null() {
            return false;
        }

        // technically it doesn't matter whether it's back or front since this is only called when
        // the list is currently empty
        self.freelist.insert_back(new);
        self.total_slabs += 1;
        self.num_full += 1;
        true
    }

    fn dealloc(&mut self, ptr: *mut u8) {
        debug_assert_eq!(ptr as usize % self.layout.align(), 0);
        let (slab, was_empty) = self.slab_system.dealloc(ptr, I::status_initialized());
        let is_full = self.slab_system.is_full(slab);

        match (was_empty, is_full) {
            // !was_empty implies it's already in the freelist; is_full implies it should be
            // moved to the back of the freelist
            (false, true) => {
                self.freelist.move_to_back(slab);
                self.num_full += 1;
            }
            // was_empty implies it's not already in the freelist; is_full implies it should be
            // added to the back of the freelist (note: only possible if slabs have size 1 -
            // they go from empty to full in a single free)
            (true, true) => {
                self.freelist.insert_back(slab);
                self.num_full += 1;
            }
            // was_empty implies it's not already in the freelist; !is_full implies it should
            // be added to the front since it's now partially-full
            (true, false) => self.freelist.insert_front(slab),
            // !was_empty implies it's already in the front section of the freelist; !is_full
            // implies it should stay there
            (false, false) => {}
        }

        if is_full {
            // TODO: document the logic behind only doing this when a slab becomes full
            self.garbage_collect_slabs();
        }

        self.refcnt -= 1;
    }

    fn garbage_collect_slabs(&mut self) {
        if let Some(min_full) = self.full_slab_working_set
               .refresh(WORKING_PERIOD_SECONDS) {
            for _ in 0..min_full {
                let slab = self.freelist.remove_back();
                self.slab_system.dealloc_slab(slab);
                self.total_slabs -= 1;
                self.num_full -= 1;
            }
            self.full_slab_working_set.set(self.num_full);
        }
    }
}

impl<I: InitSystem, S: SlabSystem<I>> Drop for SizedSlabAlloc<I, S> {
    fn drop(&mut self) {
        if self.refcnt != 0 {
            if std::thread::panicking() {
                // TODO: We shouldn't panic here because then we'd panic while panicking, and just
                // abort without printing a useful message. We should figure out an alternative
                // that allows us to properly print a diagnostic.
            } else {
                panic!("non-zero refcount when dropping slab allocator");
            }
        }

        while self.freelist.size() > 0 {
            let slab = self.freelist.remove_front();
            self.slab_system.dealloc_slab(slab);
        }
    }
}

trait SlabSystem<I: InitSystem> {
    type Slab: Linkable;

    /// Allocate a new `Slab`.
    ///
    /// The returned `Slab` has its next and previous pointers initialized to null.
    fn alloc_slab(&mut self) -> *mut Self::Slab;
    fn dealloc_slab(&mut self, slab: *mut Self::Slab);

    /// `is_full` returns true if all objects are available for allocation.
    fn is_full(&self, slab: *mut Self::Slab) -> bool;
    /// `is_empty` returns true if no objects are available for allocation.
    fn is_empty(&self, slab: *mut Self::Slab) -> bool;
    /// `alloc` allocates a new object from the given `Slab`.
    fn alloc(&self, slab: *mut Self::Slab) -> (*mut u8, I::Status);
    /// `dealloc` deallocates the given object. It is `dealloc`'s responsibility to find the
    /// object's parent `Slab` and return it. It also returns whether the `Slab` was empty prior to
    /// deallocation.
    fn dealloc(&self, obj: *mut u8, init_status: I::Status) -> (*mut Self::Slab, bool);
}