A safe `Pin`-based intrusive doubly-linked list in Rust

Last update: Jun 4, 2022

pin-list

This crate provides PinList, a safe Pin-based intrusive doubly linked list.

Example

A thread-safe unfair async mutex.

use pin_project_lite::pin_project;
use std::cell::UnsafeCell;
use std::future::Future;
use std::ops::Deref;
use std::ops::DerefMut;
use std::pin::Pin;
use std::task;
use std::task::Poll;
use pin_list::PinList;

type PinListTypes = dyn pin_list::Types<
    Id = pin_list::id::Checked,
    Protected = task::Waker,
    Removed = (),
    Unprotected = (),
>;

pub struct Mutex<T> {
    data: UnsafeCell<T>,
    inner: std::sync::Mutex<Inner>,
}

struct Inner {
    locked: bool,
    waiters: PinList<PinListTypes>,
}

unsafe impl<T> Sync for Mutex<T> {}

impl<T> Mutex<T> {
    pub fn new(data: T) -> Self {
        Self {
            data: UnsafeCell::new(data),
            inner: std::sync::Mutex::new(Inner {
                locked: false,
                waiters: PinList::new(pin_list::id::Checked::new()),
            }),
        }
    }
    pub fn lock(&self) -> Lock<'_, T> {
        Lock {
            mutex: self,
            node: pin_list::Node::new(),
        }
    }
}

pin_project! {
    pub struct Lock<'mutex, T> {
        mutex: &'mutex Mutex<T>,
        #[pin]
        node: pin_list::Node<PinListTypes>,
    }

    impl<T> PinnedDrop for Lock<'_, T> {
        fn drop(this: Pin<&mut Self>) {
            let this = this.project();
            let node = match this.node.initialized_mut() {
                // The future was cancelled before it could complete.
                Some(initialized) => initialized,
                // The future has completed already (or hasn't started); we don't have to do
                // anything.
                None => return,
            };

            let mut inner = this.mutex.inner.lock().unwrap();

            match node.reset(&mut inner.waiters) {
                // If we've cancelled the future like usual, just do that.
                (pin_list::NodeData::Linked(_waker), ()) => {}

                // Otherwise, we have been woken but aren't around to take the lock. To
                // prevent deadlocks, pass the notification on to someone else.
                (pin_list::NodeData::Removed(()), ()) => {
                    if let Ok(waker) = inner.waiters.cursor_front_mut().remove_current(()) {
                        drop(inner);
                        waker.wake();
                    }
                }
            }
        }
    }
}

impl<'mutex, T> Future for Lock<'mutex, T> {
    type Output = Guard<'mutex, T>;
    fn poll(self: Pin<&mut Self>, cx: &mut task::Context<'_>) -> Poll<Self::Output> {
        let mut this = self.project();

        let mut inner = this.mutex.inner.lock().unwrap();

        if let Some(mut node) = this.node.as_mut().initialized_mut() {
            // Check whether we've been woken up, only continuing if so.
            if let Err(node) = node.take_removed(&inner.waiters) {
                // If we haven't been woken, re-register our waker and pend.
                *node.protected_mut(&mut inner.waiters).unwrap() = cx.waker().clone();
                return Poll::Pending;
            }
        }

        // If the mutex is unlocked, mark it as locked and return the guard
        if !inner.locked {
            inner.locked = true;
            return Poll::Ready(Guard { mutex: this.mutex });
        }

        // Otherwise, re-register ourselves to be woken when the mutex is unlocked again
        inner.waiters.push_back(this.node, cx.waker().clone(), ());

        Poll::Pending
    }
}

pub struct Guard<'mutex, T> {
    mutex: &'mutex Mutex<T>,
}

impl<T> Deref for Guard<'_, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        unsafe { &*self.mutex.data.get() }
    }
}
impl<T> DerefMut for Guard<'_, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { &mut *self.mutex.data.get() }
    }
}

impl<T> Drop for Guard<'_, T> {
    fn drop(&mut self) {
        let mut inner = self.mutex.inner.lock().unwrap();
        inner.locked = false;

        if let Ok(waker) = inner.waiters.cursor_front_mut().remove_current(()) {
            drop(inner);
            waker.wake();
        }
    }
}
#

License: MIT

GitHub

https://github.com/SabrinaJewson/pin-list.rs
You might also like...

Easy to use Rust i18n library based on code generation

rosetta-i18n rosetta-i18n is an easy-to-use and opinionated Rust internationalization (i18n) library powered by code generation. rosetta_i18n::include

May 7, 2022

A Rust-based tool to analyze an application's heap.

Heap analysis tool for Rust Heap analysis is a pure-Rust implementation to track memory allocations on the heap. Usage Heap analysis provides a custom

May 9, 2022

CBOR (binary JSON) for Rust with automatic type based decoding and encoding.

THIS PROJECT IS UNMAINTAINED. USE serde_cbor INSTEAD. This crate provides an implementation of RFC 7049, which specifies Concise Binary Object Represe

May 22, 2022

A rust-based version of the popular dnsgen python utility

ripgen A rust-based version of the popular dnsgen python utility. ripgen is split into two main parts: ripgen: A CLI utility that calls into ripgen_li

Jun 19, 2022

tracing - a framework for instrumenting Rust programs to collect structured, event-based diagnostic information

tracing-appender Writers for logging events and spans Documentation | Chat Overview tracing is a framework for instrumenting Rust programs to collect

Mar 9, 2022

Rust Kubernetes runtime helpers. Based on kube-rs.

Rust Kubernetes runtime helpers. Based on kube-rs.

kubert Rust Kubernetes runtime helpers. Based on kube-rs. Features clap command-line interface support; A basic admin server with /ready and /live pro

May 21, 2022

A simple quote-based code generator for Rust

flexgen A flexible, yet simple quote-based code generator for creating beautiful Rust code Why? Rust has two types of macros, and they are both very p

May 28, 2022

Utilities and tools based around Amazon S3 to provide convenience APIs in a CLI

s3-utils Utilities and tools based around Amazon S3 to provide convenience APIs in a CLI. This tool contains a small set of command line utilities for

Mar 17, 2022

A DIY, IMU-based skateboard activity tracker

A DIY, IMU-based skateboard activity tracker

tracksb A DIY, IMU-based skateboard activity tracker. The idea is to come up with algorithms to track activity during skateboarding sessions. A compan

May 5, 2022
List of Persian Colors and hex colors for CSS, SCSS, PHP, JS, Python, and Ruby.

Persian Colors (Iranian colors) List of Persian Colors and hex colors for CSS, SCSS, PHP, C++, QML, JS, Python, Ruby and CSharp. Persian colors Name H

Feb 22, 2022
A list of publicly available STUN servers, refreshed every hour.

Always Online: STUN servers Have you ever thought: Gosh, why isn't there a regularly updated, comprehensive list of publicly available STUN servers? W

Jun 16, 2022
This crate allows you to safely initialize Dynamically Sized Types (DST) using only safe Rust.

This crate allows you to safely initialize Dynamically Sized Types (DST) using only safe Rust.

Feb 12, 2022
Fast, initializable, and thread safe static variables

tagged_cell Fast, initializable, and thread safe static variables Overview Borrows the excellent ZST based tagging implementation (linked below) to gu

Mar 13, 2022
✨ Safe, global singletons initialized at program start

✨ magic_static Safe, global singletons initialized at program start. Usage Simply add magic_static as a dependency in your Cargo.toml to get started:

Jun 11, 2022
untyped-arena provides an Arena allocator implementation that is safe and untyped with minimal complexity

untyped-arena untyped-arena provides an Arena allocator implementation that is safe and untyped with minimal complexity Usage let arena = Arena::new()

Jan 9, 2022
Type-safe IPC for Tauri using GraphQL

Tauri Plugin graphql A plugin for Tauri that enables type-safe IPC through GraphQL. Install Rust [dependencies] tauri-plugin-graphql = "0.2" JavaScrip

Jun 5, 2022
A high level diffing library for rust based on diffs
A high level diffing library for rust based on diffs

Similar: A Diffing Library Similar is a dependency free crate for Rust that implements different diffing algorithms and high level interfaces for it.

Jun 16, 2022
Nannou/Rust tutorial based on Schotter by Georg Nees
Nannou/Rust tutorial based on Schotter by Georg Nees

Schotter (German for gravel) is a piece by computer art pioneer Georg Nees. It consists of a grid of squares 12 across and 22 down with random rotation and displacement that increases towards the bottom.

Jun 17, 2022
🦀 Rust-based implementation of a Snowflake Generator which communicates using gRPC

Clawflake Clawflake is a Rust application which implements Twitter Snowflakes and communicates using gRPC. Snowflake ID numbers are 63 bits integers s

Jun 12, 2022