Crate tokenlock[−][src]

This crate provides a cell type, TokenLock, whose contents can only be accessed by an unforgeable token.

Examples

Basics

let mut token = ArcToken::new();

let lock = TokenLock::new(token.id(), 1);
assert_eq!(*lock.read(&token), 1);

let mut guard = lock.write(&mut token);
assert_eq!(*guard, 1);
*guard = 2;

Only the original Token's owner can access its contents. Token cannot be cloned:

let lock = Arc::new(TokenLock::new(token.id(), 1));

let lock_1 = Arc::clone(&lock);
thread::Builder::new().spawn(move || {
    let lock_1 = lock_1;
    let mut token_1 = token;

    // I have `Token` so I can get a mutable reference to the contents
    lock_1.write(&mut token_1);
}).unwrap();

// can't access the contents; I no longer have `Token`
// lock.write(&mut token);

Lifetimes

The lifetime of the returned reference is limited by both of the TokenLock and Token.

let mut token = ArcToken::new();
let lock = TokenLock::new(token.id(), 1);
let guard = lock.write(&mut token);
drop(lock); // compile error: `guard` cannot outlive `TokenLock`
drop(guard);

drop(token); // compile error: `guard` cannot outlive `Token`
drop(guard);

It also prevents from forming a reference to the contained value when there already is a mutable reference to it:

let write_guard = lock.write(&mut token);
let read_guard = lock.read(&token); // compile error
drop(write_guard);

While allowing multiple immutable references:

let read_guard1 = lock.read(&token);
let read_guard2 = lock.read(&token);

An operating system kernel often needs to store the global state in a global variable. Linked lists are a common data structure used in a kernel, but Rust's ownership does not allow forming 'static references into values protected by a mutex. Common work-arounds, such as smart pointers and index references, take a heavy toll on a small microcontroller with a single-issue in-order pipeline and no hardware multiplier.

struct Process {
    prev: Option<& /* what lifetime? */ Process>,
    next: Option<& /* what lifetime? */ Process>,
    state: u8,
    /* ... */
}
struct SystemState {
    first_process: Option<& /* what lifetime? */ Process>,
    process_pool: [Process; 64],
}
static STATE: Mutex<SystemState> = todo!();

tokenlock makes the 'static reference approach possible by detaching the lock granularity from the protected data's granularity.

use tokenlock::*;
use std::cell::Cell;
struct Tag;
impl_singleton_token_factory!(Tag);

type KLock<T> = UnsyncTokenLock<T, SingletonTokenId<Tag>>;
type KLockToken = UnsyncSingletonToken<Tag>;
type KLockTokenId = SingletonTokenId<Tag>;

struct Process {
    prev: KLock<Option<&'static Process>>,
    next: KLock<Option<&'static Process>>,
    state: KLock<u8>,
    /* ... */
}
struct SystemState {
    first_process: KLock<Option<&'static Process>>,
    process_pool: [Process; 1],
}
static STATE: SystemState = SystemState {
    first_process: KLock::new(KLockTokenId::new(), None),
    process_pool: [
        Process {
            prev: KLock::new(KLockTokenId::new(), None),
            next: KLock::new(KLockTokenId::new(), None),
            state: KLock::new(KLockTokenId::new(), 0),
        }
    ],
};

Token types

This crate provides the following types implementing Token.

(std only) RcToken and ArcToken ensure their uniqueness by reference-counted memory allocations.

SingletonToken<Tag> is a singleton token, meaning only one of such instance can exist at any point of time during the program's execution. impl_singleton_token_factory! instantiates a static flag to indicate SingletonToken's liveness and allows you to construct it safely by SingletonToken::new. Alternatively, you can use SingletonToken::new_unchecked, but this is unsafe if misused.

`!Sync` tokens

UnsyncTokenLock is similar to TokenLock but designed for non-Sync tokens and has relaxed requirements on the inner type for thread safety. Specifically, it can be Sync even if the inner type is not Sync. This allows for storing non-Sync cells such as Cell and reading and writing them using shared references (all of which must be on the same thread because the token is !Sync) to the token.

use std::cell::Cell;
let mut token = ArcToken::new();
let lock = Arc::new(UnsyncTokenLock::new(token.id(), Cell::new(1)));

let lock_1 = Arc::clone(&lock);
thread::Builder::new().spawn(move || {
    // "Lock" the token to the current thread using
    // `ArcToken::borrow_as_unsync`
    let token = token.borrow_as_unsync();

    // Shared references can alias
    let (token_1, token_2) = (&token, &token);

    lock_1.read(token_1).set(2);
    lock_1.read(token_2).set(4);
}).unwrap();

!Sync tokens, of course, cannot be shared between threads:

let mut token = ArcToken::new();
let token = token.borrow_as_unsync();
let (token_1, token_2) = (&token, &token);

// compile error: `&ArcTokenUnsyncRef` is not `Send` because
//                `ArcTokenUnsyncRef` is not `Sync`
thread::Builder::new().spawn(move || {
    let _ = token_2;
});

let _ = token_1;

Macros

impl_singleton_token_factory

Implement SingletonTokenFactory on a given type.

Structs

ArcToken	An `Arc`-based unforgeable token used to access the contents of a `TokenLock`.
ArcTokenId	Token that cannot be used to access the contents of a `TokenLock`, but can be used to create a new `TokenLock`.
ArcTokenUnsyncRef	Represents a borrow of `ArcToken` constrained to a single thread.
BadTokenError	Error type returned when a key (`Token`) doesn't fit in a keyhole (`TokenLock::keyhole`).
RcToken	An `Rc`-based unforgeable token used to access the contents of a `TokenLock`.
RcTokenId	Token that cannot be used to access the contents of a `TokenLock`, but can be used to create a new `TokenLock`.
SingletonToken	A singleton unforgeable token used to access the contents of a `TokenLock`.
SingletonTokenExhaustedError	Error type returned when `SingletonToken::new` was called, but a token has already been issued, and a new one cannot be issued until the old one is returned to the factory by dropping `SingletonTokenGuard`.
SingletonTokenGuard	The RAII guard for a `SingletonToken` obtained through `SingletonToken::new`. Returns the token to the factory automatically when dropped.
SingletonTokenId	Token that cannot be used to access the contents of a `TokenLock`, but can be used to create a new `TokenLock`.
SingletonTokenRef	Zero-sized logical equivalent of `&'a` `SingletonToken<Tag>`.
SingletonTokenRefMut	Zero-sized logical equivalent of `&'a mut` `SingletonToken<Tag>`.
TokenLock	A mutual exclusive primitive that can be accessed using a `Token<Keyhole>` with a very low overhead.
UnsyncTokenLock	Like `TokenLock`, but the usable `Token`s are constrained by `Unsync`. This subtle difference allows it to be `Sync` even if `T` is not.

Traits

SingletonTokenFactory	Associates a type with a flag indicating whether an instance of `SingletonToken<Self>` is present.
Token	Trait for an unforgeable token used to access the contents of a `TokenLock<_, Keyhole>`.
Unsync	Asserts the types implementing this trait are `!Sync`. (Negative bounds are not supported by the compiler at the point of writing, so this trait must be implemented manually.)

Type Definitions

UnsyncSingletonToken	The `!Sync` variant of `SingletonToken`.
UnsyncSingletonTokenGuard	The `!Sync` variant of `SingletonTokenGuard`.
UnsyncSingletonTokenRef	Zero-sized logical equivalent of `&'a` `UnsyncSingletonToken<Tag>`. The `!Sync` variant of `SingletonTokenRef`.
UnsyncSingletonTokenRefMut	Zero-sized logical equivalent of `&'a mut` `UnsyncSingletonToken<Tag>`. The `!Sync` variant of `SingletonTokenRefMut`.