Thread-safe way to either take or borrow

I have some value T that is not Clone. I want to design a thread-safe API to either take or borrow this value, first-come-first-serve. If the value has been taken first, an attempt to borrow it later must error. If the value has been borrowed first, an attempt to take it later must error.

I have to use interior mutability, and I'm trying to express this in safe code, wrapped in some API like:

impl<T> SomeThreadSafeContainer<T> {
    fn try_take(&self) -> Result<T, E>;
    fn try_borrow(&self) -> Result<&T, E>;
}

I'm unsure if there are any synchronization primitives suitable for this problem. Both Mutex and RwLock won't let a the borrow escape the guard, but in theory this read guard will be created within try_borrow and then live as long as &self. Any tips?

edit: If the value has been borrowed before it has been taken, then it should be OK to borrow it again any number of times.

You can't return a reference without the guard or you won't be able to run the code to release the lock.

This sounds like a wrapper around a RwLock<Option<T>>. In the take case you try and lock for writing, and take the optional value and can return the value without a guard. In the read case you just lock for reading normally and return a guard. You'll probably need to create a wrapper type around RwLock's guard that can unwrap the optional value in it's Deref impl. (Panicking in Deref is bad, but you should have a pretty strong guarantee that unwrap won't panic)

2 Likes

I think it should be sufficient to have AtomicU8 that tracks if it's been taken, borrowed, or neither (with compare-exchange to prevent races), and ManuallyDrop<T> to be able to do with the type whatever you want. You don't need any UnsafeCell here, since the type won't be shared mutably.

1 Like

This may be the part that's tripping you up. A read guard that isn't returned will unlock when try_borrow returns, so it won't live as long as self. That's why returning a guard is needed as @semicoleon described.

I know I can do this with a guard, what I am trying to do is abstract away the guard. Once the value is in the "borrowed" state, it will never leave this state. After it has been borrowed it cannot ever be mutated again.

Ahh so you have three states:

  • Ready
  • Taken
  • Borrowed

And the only allowed transitions are

  • Ready -> Borrowed
  • Ready -> Taken

Is that correct?

Yes, when the container is initialized, I don't know whether the value will be taken or borrowed. Whoever reaches try_take or try_borrow first determines the fate of what state it will end up in :slight_smile:

Then what @kornel said should work. Sorry for the misunderstanding in my reply, I didn't read what you wrote closely enough.

1 Like

I'll do some experiment with atomics, but surely this cannot be done without unsafe? Or I am misunderstanding something.

Briefly ignoring the "thread-safe" requirement, RefCell has Ref::leak on nightly. Using this, you could implement try_take and try_borrow safely on a struct containing a RefCell<Option<T>>.

Neither MutexGuard nor RwLock{Read,Write}Guard has such a leak function. I'm not sure whether this is because there's any fundamental problem with it, or it's just not as useful, or for some other reason; but perhaps you could find some discussion about that on Github. If there's nothing fundamentally wrong about it, RwLockReadGuard::leak is the only unsafe code you need to write.

1 Like

I threw together an example with a Mutex and one line of unsafe as well. Miri doesn't flag anything as UB but that obviously doesn't mean it's perfectly sound either

Playground

#![allow(dead_code)]

use std::sync::{Mutex, MutexGuard};

enum State {
    Ready,
    Borrowed,
    Taken,
}

#[derive(Debug, PartialEq)]
enum TryLockError {
    Borrowed,
    Taken,
    Poisoned,
    WouldBlock,
}

impl<T> From<std::sync::TryLockError<T>> for TryLockError {
    fn from(from: std::sync::TryLockError<T>) -> Self {
        match from {
            std::sync::TryLockError::Poisoned(_) => Self::Poisoned,
            std::sync::TryLockError::WouldBlock => Self::WouldBlock,
        }
    }
}

struct Container<T>(Mutex<(State, Option<T>)>);

impl<T> Container<T> {
    pub fn new(value: T) -> Self {
        Self(Mutex::new((State::Ready, Some(value))))
    }

    pub fn try_take(&self) -> Result<T, TryLockError> {
        let mut guard = self.0.try_lock()?;
        Ok(match guard.0 {
            State::Ready => {
                guard.0 = State::Taken;
                guard.1.take().unwrap()
            }
            State::Borrowed => return Err(TryLockError::Borrowed),
            State::Taken => return Err(TryLockError::Taken),
        })
    }

    pub fn try_borrow(&self) -> Result<&T, TryLockError> {
        let mut guard = self.0.try_lock()?;
        Ok(match guard.0 {
            State::Ready => {
                guard.0 = State::Borrowed;
                self.borrow_mutex_guard(&mut guard)
            }
            State::Borrowed => self.borrow_mutex_guard(&mut guard),
            State::Taken => return Err(TryLockError::Taken),
        })
    }

    // Tie the lifetime of the reference to self here as well.
    fn borrow_mutex_guard<'a>(&'a self, guard: &mut MutexGuard<(State, Option<T>)>) -> &'a T {
        // Once this is run once we can never mutate the optional in the mutex again.
        unsafe { &*(guard.1.as_ref().unwrap() as *const T) }
    }
}

#[test]
fn take() {
    let container = Container::new("Hello".to_string());

    assert_eq!("Hello".to_string(), container.try_take().unwrap());
}

#[test]
fn after_take() {
    let container = Container::new("Hello".to_string());
    assert_eq!("Hello".to_string(), container.try_take().unwrap());

    assert_eq!(Err(TryLockError::Taken), container.try_take());
    assert_eq!(Err(TryLockError::Taken), container.try_borrow());
}

#[test]
fn borrow() {
    let container = Container::new("Hello".to_string());

    assert_eq!("Hello", container.try_borrow().unwrap().as_str());
}

#[test]
fn after_borrow() {
    let container = Container::new("Hello".to_string());
    assert_eq!("Hello", container.try_borrow().unwrap().as_str());

    assert_eq!(Err(TryLockError::Borrowed), container.try_take());
    assert_eq!("Hello", container.try_borrow().unwrap().as_str());
}
3 Likes

Nice!

I also found the crate spin which has a RwLockGuard with a leak method.

Might have to be careful with that, I think you would keep increasing the reader count every time you called leak which would (eventually) cause an error based on a quick skim of the code

I would really like to avoid fumbling with unsafe code myself as I think my crate is not situated at a low enough abstraction level to justify it. So I'll continue my search for crates.

Yeah, relying on leak repeatedly will eventually wrap around some refcount or similar. So this is not optimal.

Without unsafe your only option is to find a type or a crate that already does it… using unsafe internally.

RwLock<Option<T>> is your best bet for safe-only version, and you'll have to return a lock guard instead of a bare reference.

1 Like

fused-lock looks quite close to what I'm looking for!

That has no tests, has unsafe code, and hasn't gotten much use if the stars are any indication.

I noticed that, but at least this means I'm not the only person ever who has this use case :slight_smile:

yeah at least there's that! :slight_smile:

I am very suspicious of the implementation because two atomics are used, making it difficult to verify. Without very extensive tests I wouldn't use it.

If you don't find a good crate, I think @semicoleon 's implementation is as good as can be done short of implementing a custom mutex.

1 Like

I just realized this should definitely be lock not try_lock. It matters less in the take case because one of them was going to error anyway if there's contention on the Mutex. For the borrow case you definitely don't want that to fail spuriously due to contention