diff options
Diffstat (limited to '')
| -rw-r--r-- | vendor/sharded-slab/src/implementation.rs | 138 |
1 files changed, 138 insertions, 0 deletions
diff --git a/vendor/sharded-slab/src/implementation.rs b/vendor/sharded-slab/src/implementation.rs new file mode 100644 index 000000000..01f08a582 --- /dev/null +++ b/vendor/sharded-slab/src/implementation.rs @@ -0,0 +1,138 @@ +// This module exists only to provide a separate page for the implementation +// documentation. + +//! Notes on `sharded-slab`'s implementation and design. +//! +//! # Design +//! +//! The sharded slab's design is strongly inspired by the ideas presented by +//! Leijen, Zorn, and de Moura in [Mimalloc: Free List Sharding in +//! Action][mimalloc]. In this report, the authors present a novel design for a +//! memory allocator based on a concept of _free list sharding_. +//! +//! Memory allocators must keep track of what memory regions are not currently +//! allocated ("free") in order to provide them to future allocation requests. +//! The term [_free list_][freelist] refers to a technique for performing this +//! bookkeeping, where each free block stores a pointer to the next free block, +//! forming a linked list. The memory allocator keeps a pointer to the most +//! recently freed block, the _head_ of the free list. To allocate more memory, +//! the allocator pops from the free list by setting the head pointer to the +//! next free block of the current head block, and returning the previous head. +//! To deallocate a block, the block is pushed to the free list by setting its +//! first word to the current head pointer, and the head pointer is set to point +//! to the deallocated block. Most implementations of slab allocators backed by +//! arrays or vectors use a similar technique, where pointers are replaced by +//! indices into the backing array. +//! +//! When allocations and deallocations can occur concurrently across threads, +//! they must synchronize accesses to the free list; either by putting the +//! entire allocator state inside of a lock, or by using atomic operations to +//! treat the free list as a lock-free structure (such as a [Treiber stack]). In +//! both cases, there is a significant performance cost — even when the free +//! list is lock-free, it is likely that a noticeable amount of time will be +//! spent in compare-and-swap loops. Ideally, the global synchronzation point +//! created by the single global free list could be avoided as much as possible. +//! +//! The approach presented by Leijen, Zorn, and de Moura is to introduce +//! sharding and thus increase the granularity of synchronization significantly. +//! In mimalloc, the heap is _sharded_ so that each thread has its own +//! thread-local heap. Objects are always allocated from the local heap of the +//! thread where the allocation is performed. Because allocations are always +//! done from a thread's local heap, they need not be synchronized. +//! +//! However, since objects can move between threads before being deallocated, +//! _deallocations_ may still occur concurrently. Therefore, Leijen et al. +//! introduce a concept of _local_ and _global_ free lists. When an object is +//! deallocated on the same thread it was originally allocated on, it is placed +//! on the local free list; if it is deallocated on another thread, it goes on +//! the global free list for the heap of the thread from which it originated. To +//! allocate, the local free list is used first; if it is empty, the entire +//! global free list is popped onto the local free list. Since the local free +//! list is only ever accessed by the thread it belongs to, it does not require +//! synchronization at all, and because the global free list is popped from +//! infrequently, the cost of synchronization has a reduced impact. A majority +//! of allocations can occur without any synchronization at all; and +//! deallocations only require synchronization when an object has left its +//! parent thread (a relatively uncommon case). +//! +//! [mimalloc]: https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf +//! [freelist]: https://en.wikipedia.org/wiki/Free_list +//! [Treiber stack]: https://en.wikipedia.org/wiki/Treiber_stack +//! +//! # Implementation +//! +//! A slab is represented as an array of [`MAX_THREADS`] _shards_. A shard +//! consists of a vector of one or more _pages_ plus associated metadata. +//! Finally, a page consists of an array of _slots_, head indices for the local +//! and remote free lists. +//! +//! ```text +//! ┌─────────────┐ +//! │ shard 1 │ +//! │ │ ┌─────────────┐ ┌────────┐ +//! │ pages───────┼───▶│ page 1 │ │ │ +//! ├─────────────┤ ├─────────────┤ ┌────▶│ next──┼─┐ +//! │ shard 2 │ │ page 2 │ │ ├────────┤ │ +//! ├─────────────┤ │ │ │ │XXXXXXXX│ │ +//! │ shard 3 │ │ local_head──┼──┘ ├────────┤ │ +//! └─────────────┘ │ remote_head─┼──┐ │ │◀┘ +//! ... ├─────────────┤ │ │ next──┼─┐ +//! ┌─────────────┐ │ page 3 │ │ ├────────┤ │ +//! │ shard n │ └─────────────┘ │ │XXXXXXXX│ │ +//! └─────────────┘ ... │ ├────────┤ │ +//! ┌─────────────┐ │ │XXXXXXXX│ │ +//! │ page n │ │ ├────────┤ │ +//! └─────────────┘ │ │ │◀┘ +//! └────▶│ next──┼───▶ ... +//! ├────────┤ +//! │XXXXXXXX│ +//! └────────┘ +//! ``` +//! +//! +//! The size of the first page in a shard is always a power of two, and every +//! subsequent page added after the first is twice as large as the page that +//! preceeds it. +//! +//! ```text +//! +//! pg. +//! ┌───┐ ┌─┬─┐ +//! │ 0 │───▶ │ │ +//! ├───┤ ├─┼─┼─┬─┐ +//! │ 1 │───▶ │ │ │ │ +//! ├───┤ ├─┼─┼─┼─┼─┬─┬─┬─┐ +//! │ 2 │───▶ │ │ │ │ │ │ │ │ +//! ├───┤ ├─┼─┼─┼─┼─┼─┼─┼─┼─┬─┬─┬─┬─┬─┬─┬─┐ +//! │ 3 │───▶ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ +//! └───┘ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ +//! ``` +//! +//! When searching for a free slot, the smallest page is searched first, and if +//! it is full, the search proceeds to the next page until either a free slot is +//! found or all available pages have been searched. If all available pages have +//! been searched and the maximum number of pages has not yet been reached, a +//! new page is then allocated. +//! +//! Since every page is twice as large as the previous page, and all page sizes +//! are powers of two, we can determine the page index that contains a given +//! address by shifting the address down by the smallest page size and +//! looking at how many twos places necessary to represent that number, +//! telling us what power of two page size it fits inside of. We can +//! determine the number of twos places by counting the number of leading +//! zeros (unused twos places) in the number's binary representation, and +//! subtracting that count from the total number of bits in a word. +//! +//! The formula for determining the page number that contains an offset is thus: +//! +//! ```rust,ignore +//! WIDTH - ((offset + INITIAL_PAGE_SIZE) >> INDEX_SHIFT).leading_zeros() +//! ``` +//! +//! where `WIDTH` is the number of bits in a `usize`, and `INDEX_SHIFT` is +//! +//! ```rust,ignore +//! INITIAL_PAGE_SIZE.trailing_zeros() + 1; +//! ``` +//! +//! [`MAX_THREADS`]: https://docs.rs/sharded-slab/latest/sharded_slab/trait.Config.html#associatedconstant.MAX_THREADS |