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

11–20 of 33 posts

Re: Properly testing concurrent data structures

#11

Post by ahepp »

> Well, if I am being honest, there is a bit of up-front knowledge here. I don’t think we can avoid spawning real threads here, unless we do something really cursed with inline assembly. When something calls that pause() function, and we want it to stay paused until further notice, that just has to happen in a thread which maintains a stack separate from the stack of our test.

Is there a reason we couldn't use some kind of async runtime? It seems like you're instrumenting atomic operations to achieve cooperative multitasking. Maybe I need to drink more coffee, but it seems simpler without threads.

Re: Properly testing concurrent data structures

#12

Post by ot »

idle_cycles wrote: post #2

This is great, is there a "loom" like library for C++? I have a set of lock-free data structures that I would like to test.

Folly has DeterministicSchedule, which also wraps atomics and it is used to test its core synchronization primitives, but I don't think it's as sophisticated as loom.

https://github.com/facebook/folly/blob/main/folly/test/Deter...

Re: Properly testing concurrent data structures

#13

Post by claytonwramsey »

ahepp wrote: post #11

> Well, if I am being honest, there is a bit of up-front knowledge here. I don’t think we can avoid spawning real threads here, unless we do something really cursed with inline assembly. When something calls that pause() function, and we want it to stay paused until further notice, that just has to happen in a thread which maintains a stack separate from the stack of our test. Is there a reason we couldn't use some k…

It would be convenient to use async, but the other requirement is that we don’t want to change the outwardly-observable API of the software under test. Since async is “infectious,” we have to use sync implementations for sync APIs.

Re: Properly testing concurrent data structures

#14

Post by o11c »

If I understand this correctly, this approach has limitations regarding soft forward-progress guarantees.

Consider a cmpxchg loop where the body computation is not quite trivial, but on real hardware (and with real schedulers) is exceedingly unlikely to be interrupted on a given CPU. Thus, if `n` is the number of CPUs, it has a worst-case `1/n` chance of making progress. But with this testing approach, it instead has a `1/t^p` chance, where `t` is the number of tasks (which may be far larger than the number of CPUs) and `p` is the number of pauses (easily at least 3) within the not-quite-trivial loop body; this is sufficient to turn a working algorithm into a broken one.

OTOH, if you do want the tester to detect soft forward-progress as a bug (because you want hard forward-progress), this doesn't seem to provide useful tools either.

(Regardless this is certainly useful for a lot of concurrency problems).

Re: Properly testing concurrent data structures

#16

Post by int08h »

idle_cycles wrote: post #2

This is great, is there a "loom" like library for C++? I have a set of lock-free data structures that I would like to test.

Yes, the (IMHO) the easiest one to use is the Relacy Race Detector (https://github.com/dvyukov/relacy and https://www.1024cores.net/home/relacy-race-detector)

It's been around a while and is easy to work with. Written by Dmitry Vyukov, an expert in the concurrency world.

Re: Properly testing concurrent data structures

#17

Post by kibwen »

clearprop wrote: post #5

I thought Rust was thread-safe and I don't see any "unsafe" blocks. What am I missing?

From https://doc.rust-lang.org/nomicon/races.html :

"Safe Rust guarantees an absence of data races, which are defined as: two or more threads concurrently accessing a location of memory, where one or more of them is a write, and one or more of them is unsynchronized. A data race has Undefined Behavior, and is therefore impossible to perform in Safe Rust. [...] However Rust does not prevent general race conditions. This is mathematically impossible in situations where you do not control the scheduler, which is true for the normal OS environment. [...] For this reason, it is considered "safe" for Rust to get deadlocked or do something nonsensical with incorrect synchronization: this is known as a general race condition or resource race. Obviously such a program isn't very good, but Rust of course cannot prevent all logic errors. In any case, a race condition cannot violate memory safety in a Rust program on its own. Only in conjunction with some other unsafe code can a race condition actually violate memory safety."

Re: Properly testing concurrent data structures

#18

Post by oasisaimlessly »

claytonwramsey wrote: post #13
ahepp wrote: post #11

> Well, if I am being honest, there is a bit of up-front knowledge here. I don’t think we can avoid spawning real threads here, unless we do something really cursed with inline assembly. When something calls that pause() function, and we want it to stay paused until further notice, that just has to happen in a thread which maintains a stack separate from the stack of our test. Is there a reason we couldn't use some k…

It would be convenient to use async, but the other requirement is that we don’t want to change the outwardly-observable API of the software under test. Since async is “infectious,” we have to use sync implementations for sync APIs.

What about stackful coroutines? They don't necessarily change the API.

Re: Properly testing concurrent data structures

#19

Post by kibwen »

chc4 wrote: post #6
clearprop wrote: post #5

I thought Rust was thread-safe and I don't see any "unsafe" blocks. What am I missing?

Losing updates to the atomic counter is thread safe behavior, it's just a logic bug.

Specifically, one thread reads the counter with proper synchronization, then another thread writes an incremented value to the counter with proper synchronization, then the first thread writes its own incremented value to the counter with proper synchronization. At every step the use of an AtomicU32 guarantees proper synchronization to the underlying memory, which is what Rust is concerned with.

The fix for the logic bug in this case would be to indicate that you want the increment itself to be an atomic operation, using the fetch_add method: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicU32.h...

Re: Properly testing concurrent data structures

#20

Post by [deleted] »

o11c wrote: post #14

If I understand this correctly, this approach has limitations regarding soft forward-progress guarantees. Consider a cmpxchg loop where the body computation is not quite trivial, but on real hardware (and with real schedulers) is exceedingly unlikely to be interrupted on a given CPU. Thus, if `n` is the number of CPUs, it has a worst-case `1/n` chance of making progress. But with this testing approach, it instead has…

[deleted]
Post reply on HN