frogtd / rose_bloom

A concurrent growing element size linked list with stable pointers.

rose_bloom

rose_bloom is a crate for passing out references that won't move when you push to it. It is also thread-safe, so you can use it as a concurrent queue if you don't care about freeing memory as you go along. It is lock-free.

Many operations are O(lg n). This will still be extremely fast.

Example

use rose_bloom::Rose;

let rose = Rose::new();
let out1 = rose.push(1);
rose.push(2);
rose.push(3);
println!("{out1}"); // 1

Installation

Add this to your Cargo.toml:

[dependencies]
rose_bloom = "0.1"

#![no_std]

This crate is #![no_std] but does require alloc.

Licenses

• MIT
• Unlicense

rose_bloom's Issues

Miri data race test failure

With the following test:

#[test]
fn concurrent() {
    extern crate std;
    use alloc::boxed::Box;
    use std::thread;
    let rose = Rose::new();
    rose.push(Box::new(1));
                                    
    thread::scope(|s| {
        let t1 = s.spawn(|| {
            rose.push(Box::new(1));
        });
        let t2 = s.spawn(|| {
            rose.push(Box::new(1));
        });
    });
}

Miri fails with the following error

running 2 tests
test tests::concurrent ... error: Undefined Behavior: Data race detected between Read on thread `<unnamed>` and Write on thread `<unnamed>` at alloc78244
   --> src/lib.rs:135:37
    |
135 |             let capacity = unsafe { (*last).capacity };
    |                                     ^^^^^^^^^^^^^^^^ Data race detected between Read on thread `<unnamed>` and Write on thread `<unnamed>` at alloc78244
    |
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
    = note: backtrace:
    = note: inside `Rose::<alloc::boxed::Box<i32>>::push` at src/lib.rs:135:37
note: inside closure at src/lib.rs:266:17
   --> src/lib.rs:266:17
    |
266 |                 rose.push(Box::new(1));
    |                 ^^^^^^^^^^^^^^^^^^^^^^

Also, this happens even if weak memory emulation is disabled, so it's not weak memory. Orderings presumably need to be stronger, somewhere.

`rose.first()` can return None even for lists that must have an item in it

(Fails under miri)

#[test]
fn first_works() {
    extern crate std;
    use std::thread;
    let rose = Rose::new();
    rose.push(1);
    thread::scope(|s| {
        s.spawn(|| {
            for _ in 0..10 {
                rose.push(1);
            }
        });
        s.spawn(|| {
            // This should work because we pushed 1 item earlier
            // so no matter how many items we have, there's always *a* first
            for _ in 0..10 {
                rose.first().unwrap();
            }
        });
    });
}

Looks like an atomic memory ordering issue, where the total length and the sum total of the length of each item disagree.

It would be worth adding a promise that "after getting some value n from rose.len(), it is promised that rose.get(x) for any value x inside 0..n will return Some". (And add a test for that)

Since that's what the current first code relies on anyways.