Support for no_std

[ghost]

As a first step, I'm thinking we should publicly expose base::SkipList and present it as the 'advanced' skip list implementation targeted at expert users who want to use the skip list in no_std, control garbage collection more precisely, pass Guards to methods, squeeze out every ounce of performance, and so on.

Secondly, in no_std we don't have access to epoch::pin() so one should use Handle::pin() instead and pass a guard to methods that work with the SkipList.

When passing a guard to a skip list method, we must make sure that the guard belongs to the same Collector the skip list is using. In other words, every method taking a &Guard should have a check at the beginning like in the following snippet:

fn insert(&self, key: K, value: V, guard: &Guard) {
    assert!(
        self.collector == guard.collector(),
        "the guard doesn't belong to this collector used by this skip list",
    );

    // ...
}

In order to be able to make such checks, we'll have to first implement fn Guard::collector(&self) -> &Collector in crossbeam-epoch.

In addition to that, SkipList would probably need a similar method returning a reference to its own Collector.

With such an interface, I envision the skip list might be used like this:

let s = SkipList::new();
let handle = s.collector().handle();

let guard = &handle.pin();
s.insert("foo", 42, guard);

@Amanieu What do you think about all this - would this interface work for you? Any better ideas for supporting no_std?

[Amanieu]

SkipList::new should take a Collector as a parameter. This allows reusing the global collector, since a Collector can be cloned to create a new reference to the same collector (like Arc). Or maybe allow this using a secondary constructor SkipList::with_collector.

Guard::collector can't really return a &Collector, so we'll need a different API. I would also like to avoid messing with the collector's reference count on every lookout. How about Guard::is_from_collector(&Collector) -> bool?

[Amanieu]

We also need to expose a way to get a Collector which points to the global collector in crossbeam-epoch. This will be used in the normal skiplist constructors.

[ghost]

Or maybe allow this using a secondary constructor SkipList::with_collector.

Good idea. Just something to keep in mind: this method must be marked as unsafe because you can cause use-after-free with it (assuming that we get rid of the K: 'static, V: 'static bounds):

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Key<'a>(&'a i32);
impl<'a> Drop for Key<'a> {
    fn drop(&mut self) {
        println!("dropping: {}", self.0);
    }
}

let c = Collector::new();
{
    let boxed = Box::new(7);
    let s = SkipList::with_collector(c.clone());
    s.insert(Key(&*boxed), ());
    s.remove(Key(&7));
}
drop(c); // Oops, the key is now getting dropped and printing `boxed`.

Guard::collector can't really return a &Collector, so we'll need a different API. I would also like to avoid messing with the collector's reference count on every lookout.

Actually, it's not hard to do - I already did that in one of my local branches. :) Each Guard is holding a pointer to a Local, and each Local has an Arc<Global>, which is actually equivalent to Collector.

And note that returning a &Collector doesn't mess with the refcount in the Arc - it's just a reference. Guard::collector would be really cheap.

[Amanieu]

Is there much demand for non-'static objects? You're generally going to use EBR for long-lived data which is accessed by multiple threads. Lifetimes aren't really necessary in that context. I feel that it would be OK to leave the bounds in and avoid dealing with local collectors.

The problem with returning a &Collector is that you would need to create a Collector object to return a reference to. Which you don't have since all we have is a &Global from the Arc<Global>.

[ghost]

Is there much demand for non-'static objects?

I imagine keys might often be of type &'a str. For example, suppose you read a file into a big String. Then you create a crossbeam::scope and spawn threads inside the scope. Those threads parse the String or whatever and insert slices of it into a SkipMap<&'big_string str, Foo>.

An alternative to removing K: 'static, V: 'static bounds might be to just very slightly relax the bounds and have K: LateDropSafe, V: DeferredDropSafe, where DeferredDropSafe is a trait defined as:

pub unsafe trait DeferredDropSafe {}
unsafe impl<T: Copy> DeferredDropSafe for T {}
unsafe impl<T: 'static> DeferredDropSafe for T {}

This way we can have 'static and Copy types, which includes &'a str.

I feel that it would be OK to leave the bounds in and avoid dealing with local collectors.

SkipSet and SkipMap definitely have to support &'str types, one way or another. I don't have strong opinions on SkipList, however.

The problem with returning a &Collector is that you would need to create a Collector object to return a reference to. Which you don't have since all we have is a &Global from the Arc.

Note that Collector is equivalent to Arc<Global>:

struct Collector {
    global: Arc<Global>,
}

The idea is to simply replace the UnsafeCell<ManuallyDrop<Arc<Global>>> inside Local with UnsafeCell<ManuallyDrop<Collector>> and that's all - now it's easy to return a &Collector from it.

[Amanieu]

pub unsafe trait DeferredDropSafe {}
unsafe impl<T: Copy> DeferredDropSafe for T {}
unsafe impl<T: 'static> DeferredDropSafe for T {}

I don't think this will work: the 2 trait impls conflict with each other.

[ghost]

That is, unfortunately, true at the moment. FWIW, it compiles with #![feature(specialization)]

[joshlf]

If I'm not mistaken, epoch can't currently support no_std because it performs allocation which relies on the global allocator. There is no global allocator in a no_std environment.

[Amanieu]

The intention is to support it running in a no_std + alloc environment, where you have memory allocation but none of the other features from libstd. A kernel is one example of such an environment.

[joshlf]

Gotcha. An alternative that would be useful for us (and honestly maybe not too many other users) would be to have Collector and friends be parametric on an Alloc which is, by default, alloc::allocator::Heap except on no_std, where there's no default.