Fast, efficient, and robust memory reclamation for concurrent data structures

Overview

Seize

Crate Github Docs

Fast, efficient, and robust memory reclamation for concurrent data structures.

Introduction

Concurrent data structures are faced with the problem of deciding when it is safe to free memory. Although an object might have been logically removed, other threads that previously loaded it may still have access to it, and thus it is not safe to free immediately. Over the years, many algorithms have been devised to solve this problem. However, most traditional memory reclamation schemes make the tradeoff between performance, efficiency, and robustness. For example, Epoch Based Reclamation is fast and lightweight but lacks robustness in that a stalled thread can prevent the reclamation of all retired objects. Hazard Pointers, another popular scheme, tracks individual pointers, making it efficient and robust but generally much slower.

Another problem that is often not considered is workload balancing. In most reclamation schemes, the thread that retires an object is the one that reclaims it. This leads to unbalanced reclamation in read-dominated workloads; parallelism is degraded when only a fraction of threads are writing. This is especially prevalent with the use of M:N threading models as provided by asynchronous runtimes like Tokio.

Details

Seize is based on the Hyaline reclamation scheme. It uses reference counting to determine when it is safe to free memory. However, counters are only used per batch of retired objects, allowing it to avoid the high overhead incurred by traditional reference counting schemes. Performance is typically on par or better than epoch based schemes, while memory efficiency is similar to hazard pointers. Reclamation is naturally balanced as the thread with the last reference to a batch is the one that frees memory. Epochs are also tracked to protect against stalled threads, making reclamation truly lock-free.

Seize is compatible with all modern hardware that supports common atomic operations such as FAA and CAS.

Guide

Seize tries to stay out of your way as much as possible. It works with raw pointers directly instead of creating safe wrapper types that end up being a hassle to work with in practice. Below is a step-by-step guide on how to get started.

Creating Collectors

Seize avoids the use of global state and encourages creating a designated collector per data structure. Collectors allow you to allocate, protect, and retire objects:

use seize::Collector;

struct Stack
    {
    collector: Collector,
    
   // ...
}


   impl
    
    Stack
    
      {
    
     pub 
     fn 
     new() -> 
     Self {
        
     Self {
            collector: Collector
     ::
     new(),
        }
    }
}
    
   
  

Allocating Objects

Seize requires storing some metadata about the global epoch for each object that is allocated. It also needs to reserve a couple words for retirement lists. Because of this, values in a concurrent data structure must take the form of AtomicPtr > , as opposed to just AtomicPtr .

You can link a value to a collector with the link method. link_boxed is also provided as a quick way to link an object to a collector, and allocate it:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::mem::ManuallyDrop;
use seize::{Collector, Linked};

pub struct Stack
    {
    head: AtomicPtr
   <Linked
   <Node
   <T
   >>
   >, 
   // <===
    collector: Collector,
}


   struct 
   Node
   
     {
    next: AtomicPtr
    <Linked
    <Node
    <T
    >>
    >, 
    // <===
    value: ManuallyDrop
    <T
    >,
}


    impl
     
     Stack
     
       {
    
      pub 
      fn 
      push(
      &
      self, value: T) {
        
      let node 
      = 
      self.collector.
      link_boxed(Node { 
      // <===
            value: ManuallyDrop
      ::
      new(value),
            next: AtomicPtr
      ::
      new(std
      ::ptr
      ::
      null_mut()),
        });

        
      // ...
    }
}
     
    
   
  

Beginning Operations

To begin a concurrent operation, you must mark the thread as active by calling the enter method.

impl Stack {
    pub fn push(&self, value: T) {
        // ...

        let guard = self.collector.enter(); // <===

        // ...
    }
}

Protecting Pointers

enter returns a guard that allows you to safely load an atomic pointer. Any valid pointer loaded through a guard is guaranteed to stay valid until the guard is dropped, or it is retired by the current thread. Importantly, if a different thread retires an object while we you hold the guard, the collector knows not to reclaim the object until the guard is dropped.

impl Stack {
    pub fn push(&self, value: T) {
        let node = self.collector.link_boxed(Node {
            value: ManuallyDrop::new(value),
            next: AtomicPtr::new(ptr::null_mut()),
        });

        let guard = self.collector.enter();

        loop {
            let head = guard.protect(&self.head); // <===
            unsafe { (*node).next.store(head, Ordering::SeqCst) }

            if self
                .head
                .compare_exchange(head, node, Ordering::SeqCst, Ordering::SeqCst)
                .is_ok()
            {
                break;
            }
        }

        // drop(guard);
    }
}

Note that the lifetime of a guarded pointer is logically tied to that of the guard -- when the guard is dropped the pointer is invalidated -- but a raw pointer is returned for convenience.

Retiring Objects

Objects that have been removed from a data structure can be safely retired through the collector. When no thread holds a reference to it, it's memory will be reclaimed:

impl 
   Stack
   
     {
    
    pub 
    fn 
    pop(
    &
    self) -> 
    Option
    
      {
        
     let guard 
     = 
     self.collector.
     enter(); 
     // <===

        
     loop {
            
     let head 
     = guard.
     protect(
     &
     self.head); 
     // <===

            
     if head.
     is_null() {
                
     return 
     None;
            }

            
     let next 
     = guard.
     protect(
     &(
     *head).next); 
     // <===

            
     if 
     self
                .head
                .
     compare_exchange(head, next, Ordering
     ::SeqCst, Ordering
     ::SeqCst)
                .
     is_ok()
            {
                
     unsafe {
                    
     let data 
     = ptr
     ::
     read(
     &(
     *head).data);
                    
     self.collector.
     retire(head, 
     |_
     | {}); 
     // <===
                    
     return 
     Some(ManuallyDrop
     ::
     into_inner(data));
                }
            }
        }
    }
}
    
   
  

There are a couple important things to note about retiring an object:

1. Retired objects must be logically removed

An object can only be retired if it is no longer accessible to any thread that comes after. In the above code example this was ensured by swapping out the node before retiring it. Threads that loaded a value before it was retired are safe, but threads that come after are not.

2. Retired objects cannot be accessed by the current thread

Unlike in schemes like EBR, a guard does not protect objects retired by the current thread. If no other thread holds a reference to an object it may be reclaimed immediately. This makes the following code unsound:

<===== unsound!">
let ptr = guard.protect(&node);
collector.retire(ptr, |_| {});
println!("{}", (*ptr).value); // <===== unsound!

Retirement can be delayed until the guard is dropped by calling reclaim on the guard, instead of on the collector directly:

<===== ok! drop(guard); // <===== ptr is invalidated!">
let ptr = guard.protect(&node);
guard.retire(ptr, |_| {});
println!("{}", (*ptr).value); // <===== ok!
drop(guard); // <===== ptr is invalidated!

3. Custom Reclaimers

You probably noticed that retire takes a function as a second parameter. This function is known as a reclaimer, and is run when the collector decides it is safe to free the retired object. Typically you will pass in a function from the reclaim module. For example, values allocated with Box can use reclaim::boxed:

use seize::reclaim;

impl 
   Stack
   
     {
    
    pub 
    fn 
    pop(
    &
    self) -> 
    Option
    
      {
        
     // ...
        
     self.collector.
     retire(head, reclaim
     ::boxed
     ::
     <Node
     <T
     >>); 
     // <===
        
     // ...
    }
}
    
   
  

The type annotation there is important. It is unsound to pass a reclaimer of a different type than the object being retired.

If you need to run custom reclamation code, you can write a custom reclaimer. Functions passed to retire are called with a type-erased Link. This is because retired values are connected to thread-local batches via linked lists, losing any information. To extract the underlying value from a link, you can call the cast method.

collector.reclaim(value, |link: Link| unsafe {
    // SAFETY: the value passed to reclaim was of type
    // `*mut Linked
   
    `
   
    let ptr: *mut Linked<Value> = link.cast::
   ();

    
   // SAFETY: the value was allocated with `link_boxed`
    
   let value 
   = 
   Box
   ::
   from_raw(ptr);

    
   println!(
   "dropping {}", value);

    
   drop(value);
});
  
You might also like...
A proof of concept implementation of cyclic data structures in stable, safe, Rust.

A proof of concept implementation of cyclic data structures in stable, safe, Rust. This demonstrates the combined power of the static-rc crate and the

Rust library for string parsing of basic data structures.

afmt Simple rust library for parsing basic data structures from strings. Usage You can specify string formats to any strucute, via the use of the fmt

Library containing various Data Structures implemented using Rust.

rust-data-structures Library containing various Data Structures implemented using Rust. Running You can test the library by running cargo test, an exa

A library for comparing data structures in Rust, oriented toward testing

Delta: Structural differencing in Rust The delta crate defines the trait Delta, along with a derive macro for auto-generating instances of this trait

A library for comparing data structures in Rust, oriented toward testing

The comparable crate defines the trait [Comparable], along with a derive macro for auto-generating instances of this trait for most data types. Primar

Collection of Data Structures in Rust

cds - Collection of Data Structures !!! UNDER CONSTRUCTION !!! The version v0.0.1 is a crates.io placeholder. License Licensed under either of Apache

Succinct data structures in Rust

sucds: Succinct data structures in Rust sucds contains some succinct data structures written in Rust. Data structures So far, the following data struc

Library containing implementations of various sequential data-structures.

Library containing implementations of various sequential data-structures.

Dade is data definition for Rust structures.

dade dade is data definition for Rust structures. For the easy handle of data, the following will support it. Data validation. Data schema conforms Js

Comments
  • TLS optimizations

    TLS optimizations

    • Keep track of number of threads, adds fast path to retire
    • Zero initialize all TLS entries
    • Experimented with a fast path [T; ~16], but did find a noticeable difference.
    opened by ibraheemdev 1
  • QSBR

    QSBR

    Applications that are constantly entering and leaving are marking threads as active/inactive for no reason; there is little benefit if threads are active 99% of the time. We could instead make enter a no-op (a big win) and have leave not mark threads as inactive (effectively become flush), acting more like QSBR.

    opened by ibraheemdev 0
  • `flush` and `repin`

    `flush` and `repin`

    Rename flush to repin (or a better name?) and add a real flush operation that tries to retire the local batch to be more consistent with crossbeam-epoch's API.

    opened by ibraheemdev 0
Releases(v0.2.0)
  • v0.2.0(Feb 20, 2022)

    • Added seize::AtomicPtr<T>, a type alias for std::AtomicPtr<Linked<T>>.
    • Epoch tracking is now optional.
    • Added Guard::flush.
    • Retirement can now be delayed for the lifetime of a guard (Guard::retire).
    • Added Linked::eq, Linked::into_inner.
    • Added Collector::ptr_eq.
    • Guard::unprotected is now const.
    Source code(tar.gz)
    Source code(zip)
  • v0.1.0(Feb 4, 2022)

Owner
Ibraheem Ahmed
Freelance software developer interested in concurrency, systems programming, and web servers.
Ibraheem Ahmed
NixEl is a Rust library that turns Nix code into a variety of correct, typed, memory-safe data-structures

?? NixEL Lexer, Parser, Abstract Syntax Tree and Concrete Syntax Tree for the Nix Expressions Language. NixEl is a Rust library that turns Nix code in

Kevin Amado 56 Dec 29, 2022
Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

null 6.5k Dec 31, 2022
Coding-challenge - Algorithms and Data-structures, problems and solutions in Rust language using cargo-workspaces

Coding Challenge LeetCode/Hackerrank e.t.c Using this as an opportunity to improve my knowledge of rust lang If you found this repo useful to you, add

Tolumide Shopein 17 Apr 24, 2022
Algorithms and Data Structures of all kinds written in Rust.

Classic Algorithms in Rust This repo contains the implementation of various classic algorithms for educational purposes in Rust. Right now, it is in i

Alexander González 49 Dec 14, 2022
Obake is a procedural macro for declaring and maintaining versioned data-structures.

Obake is a procedural macro for declaring and maintaining versioned data-structures. The name 'obake' is taken from the Japanese 'お化け (おばけ)', a class of supernatural beings in Japanese folklore that shapeshift.

Nathan Corbyn 174 Dec 26, 2022
Rust-algorithm-club - Learn algorithms and data structures with Rust

Rust Algorithm Club ?? ?? This repo is under construction. Most materials are written in Chinese. Check it out here if you are able to read Chinese. W

Weihang Lo 360 Dec 28, 2022
Common data structures and algorithms in Rust

Contest Algorithms in Rust A collection of classic data structures and algorithms, emphasizing usability, beauty and clarity over full generality. As

Aram Ebtekar 3.3k Dec 27, 2022
Rust data structures and client for the PubChem REST API

pubchem.rs Rust data structures and client for the PubChem REST API. ?? Usage ?? Compound Create a Compound to query the PubChem API for a single comp

Martin Larralde 2 Jan 18, 2022
rust_aads - Rust Algorithms And Data Structures

rust_aads - Rust Algorithms And Data Structures rust_aads is an open repository with algorithms and data structures, used in computer science and comp

stepa 2 Dec 15, 2022
Rust Persistent Data Structures

Rust Persistent Data Structures Rust Persistent Data Structures provides fully persistent data structures with structural sharing. Setup To use rpds a

Diogo Sousa 883 Dec 31, 2022