Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Properly testing concurrent data structures

matklad.github.io

Post reply on HN
Print view View original

1–10 of 33 posts

Re: Properly testing concurrent data structures

#3

Post by reitzensteinm »

I've been building a library in Rust with a very similar approach called Temper [1], although in order to model the bizarre implications of the full Rust memory model you have to go quite a bit further, with bookkeeping tracking which writes each thread has perceived. Based on atomic memory ordering, read and write fences etc, perceiving write X may guarantee that write Y must be perceived.

It contains what I believe to be the largest set of test cases of the C++/Rust memory model, which is essentially everything I could find in books, the C++ standard, Stack Overflow, blogs, etc. E.g. this is the file for Rust Atomics and Locks by Mara Bos [2]

Loom [3], referenced in the article, is a similar and much more complete library, which enables you to exhaustively test higher level constructs like mutexes and queues. Although it doesn't model the memory model as exhaustively as Temper (I've been meaning to port my test cases over to it).

I was inspired by a Foundation DB testing talk by Will Wilson [4], who is now over at Antithesis [5], building a hypervisor based solution to perform this style of testing on arbitrary Docker containers.

I strongly believe we're going to see much more in this domain in the coming decade. WebAssembly is at the perfect intersection of being a platform that's complete enough to be able to compile arbitrary software to, but simple enough that building something like Antithesis isn't a half decade long project from an elite team that's already shipped a database.

[1] https://github.com/reitzensteinm/temper/tree/main [2] https://github.com/reitzensteinm/temper/blob/main/memlog/tes... [3] https://github.com/tokio-rs/loom [4] https://www.youtube.com/watch?v=4fFDFbi3toc [5] https://antithesis.com/

Re: Properly testing concurrent data structures

#4

Post by kaymanb »

Very cool! I implemented some shared-memory atomic snapshots in Rust [0] and also did my best to take automated testing very seriously. I started out using loom [1], the library mentioned in the article, but latter switched to shuttle [2].

Shuttle's approach is to be randomized, instead of exhaustive like loom. However, the scheduler does still give probabilistic guarantees about finding bugs. I found that shuttle was faster and scaled to more complicated test scenarios.

Similar to the article, shuttle also lets you save the random seed if a particular schedule causes the test suite to fail. Being able to quickly reproduce failing tests is really important and enables you write explicit test cases for bugs that were previously caught and fixed [3].

[0] https://github.com/kaymanb/todc/tree/main/todc-mem [1] https://github.com/tokio-rs/loom [2] https://github.com/awslabs/shuttle [3] https://github.com/kaymanb/todc/blob/0e2874a70ec8beed8fae773...

Re: Properly testing concurrent data structures

#8

Post by skybrian »

It looks like you need to use conditional compilation to use Loom, which probably works okay for testing one library, but is pretty intrusive:

    #[cfg(loom)]
    pub(crate) use loom::sync::atomic::AtomicUsize;

    #[cfg(not(loom))]
    pub(crate) use std::sync::atomic::AtomicUsize;
I wonder if there are any languages that do a better job of letting you use your own scheduler?

Re: Properly testing concurrent data structures

#9

Post by kriper »

skybrian wrote: post #8

It looks like you need to use conditional compilation to use Loom, which probably works okay for testing one library, but is pretty intrusive: #[cfg(loom)] pub(crate) use loom::sync::atomic::AtomicUsize; #[cfg(not(loom))] pub(crate) use std::sync::atomic::AtomicUsize; I wonder if there are any languages that do a better job of letting you use your own scheduler?

in C# it's basically automatic https://github.com/microsoft/coyote/
Post reply on HN