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

Bug in reader/writer locks in Windows API

old.reddit.com

Post reply on HN
Print view View original

71–80 of 142 posts

Re: Bug in reader/writer locks in Windows API

#71

Post by ww520 »

ot wrote: post #70
ww520 wrote: post #63

The program has a bug. It's mixing atomic and non-atomic variables in the yield() checking loop. Non-atomic variables have no guarantee on cache consistency for different threads. This can cause the loop to run forever. struct ThreadTestData { int32_t numThreads = 0; std::shared_mutex sharedMutex = {}; std::atomic readCounter = 0; }; // child thread DoStuff() { data->readCounter.fetch_add(1); while (data->readCounter…

`numThreads` is written before the child threads that read it are started, so there is an explicit happens-before relationship and no data race. Before `numThreads` is reset, the child thread are joined. There is no bug in the program, it is legal to use non-atomic variables across threads as long as they're correctly sequenced.

See my last paragraph above.

Re: Bug in reader/writer locks in Windows API

#72

Post by zozbot234 »

ww520 wrote: post #68
nemothekid wrote: post #67

Earlier quoted context omitted.

> Its memory address is then passed to the child threads to be checked in the yielding loop. Since it's non-atomic, there's no memory barrier instruction to force its new value (5) to propagate to all CPU's running the threads. Each core would have to fetch the value from main memory, where it will be undoubtedly 5. There is no valid reordering (at least under x86) that would cause the thread to read 0.

The main thread is running the child thread creation in an endless loop, repeatedly setting numThreads to 0 and to 5, back to 0 and to 5 again. Can the caches of the CPU's consistently keep up with the changes?

> repeatedly setting numThreads to 0 and to 5, back to 0 and to 5 again.

The reset to 0 and to 5 happens at the start of the loop. There's a happens-before relationship between it and the threads being created, and then again between the threads being joined and the loop cycling back. So there shouldn't be any data race here.

Re: Bug in reader/writer locks in Windows API

#73

Post by forrestthewoods »

ww520 wrote: post #63

The program has a bug. It's mixing atomic and non-atomic variables in the yield() checking loop. Non-atomic variables have no guarantee on cache consistency for different threads. This can cause the loop to run forever. struct ThreadTestData { int32_t numThreads = 0; std::shared_mutex sharedMutex = {}; std::atomic readCounter = 0; }; // child thread DoStuff() { data->readCounter.fetch_add(1); while (data->readCounter…

Your assessment is completely, totally, and verifiably wrong. It's obnoxious, but not surprising, how many commenters have chimed in with "program has bug BLAH" when they provably did not try to run the program themselves.

Because if you did attempt to run the program you'd find that changing numThreads to a constexpr makes no difference.

Re: Bug in reader/writer locks in Windows API

#74

Post by forrestthewoods »

ww520 wrote: post #69
userbinator wrote: post #65

Earlier quoted context omitted.

You seem to have missed the part where an actual MS employee confirmed it was a bug in their API.

He just read OP's code, the C++/STL Standard, and the Microsoft Learn document and made that conclusion. That's a rather haste determination. Unless he read the actual Windows lock implementation and found a bug there, I don't think his conclusion is correct.

> That's a rather haste determination.

I hope you realize how deeply ironic this statement is. If you read the comments you'll find he even produced a slightly reduced repro. And in other comments he tried minor tweaks like the one you suggested.

You have a thesis that the program has a bug. (It doesn't.) Go ahead and test your thesis and report back.

Re: Bug in reader/writer locks in Windows API

#75

Post by ww520 »

zozbot234 wrote: post #72
ww520 wrote: post #68

Earlier quoted context omitted.

The main thread is running the child thread creation in an endless loop, repeatedly setting numThreads to 0 and to 5, back to 0 and to 5 again. Can the caches of the CPU's consistently keep up with the changes?

> repeatedly setting numThreads to 0 and to 5, back to 0 and to 5 again. The reset to 0 and to 5 happens at the start of the loop. There's a happens-before relationship between it and the threads being created, and then again between the threads being joined and the loop cycling back. So there shouldn't be any data race here.

CPU’s not running the main thread don’t care about the execution order of the instructions of the main thread. They only see their local caches of the same memory location got changed from 0 to 5, 5 to 0, and back to 5 repeatedly. When a new thread lands on a CPU with the old 0 cache value, it will hang.

Re: Bug in reader/writer locks in Windows API

#76

Post by TillE »

loeg wrote: post #26

Some reddit comments mention it reproduces back to Vista (2008). I am kind of shocked no one has noticed this bug in that time. I guess under typical rwlock usage you just get random instances of shared lockers unable to acquire the lock and no deadlock, but still.

Vista is when that API was first implemented.

It's doing a pretty weird thing with the locks, I wonder what the actual use case was. Readers should almost never care about other readers. Typically you just grab the lock, read the thing, and release it. You always have to be super careful about deadlocks if you're holding a lock and also waiting around for something else to happen.

Re: Bug in reader/writer locks in Windows API

#77

Post by cesarb »

ww520 wrote: post #63

The program has a bug. It's mixing atomic and non-atomic variables in the yield() checking loop. Non-atomic variables have no guarantee on cache consistency for different threads. This can cause the loop to run forever. struct ThreadTestData { int32_t numThreads = 0; std::shared_mutex sharedMutex = {}; std::atomic readCounter = 0; }; // child thread DoStuff() { data->readCounter.fetch_add(1); while (data->readCounter…

> there's no memory barrier instruction to force its new value (5) to propagate to all CPU's running the threads.

The equivalent of the memory barrier instructions is there, but it's hidden within the operating system code which creates and initializes a new thread. That is, the operating system ensures that the value in the current CPU (in this case, 5) is propagated to the CPU running the newly started thread, before the thread start routine (in this case, DoStuff) is called. The value is not modified while the child threads are running (it waits for the child threads to exit before clearing the value), so there's no chance of the child threads seeing the value being set back to zero.

Re: Bug in reader/writer locks in Windows API

#78

Post by zozbot234 »

ww520 wrote: post #75
zozbot234 wrote: post #72

Earlier quoted context omitted.

> repeatedly setting numThreads to 0 and to 5, back to 0 and to 5 again. The reset to 0 and to 5 happens at the start of the loop. There's a happens-before relationship between it and the threads being created, and then again between the threads being joined and the loop cycling back. So there shouldn't be any data race here.

CPU’s not running the main thread don’t care about the execution order of the instructions of the main thread. They only see their local caches of the same memory location got changed from 0 to 5, 5 to 0, and back to 5 repeatedly. When a new thread lands on a CPU with the old 0 cache value, it will hang.

The code runs in what's effectively a single-threaded context. CPUs running other threads will be involved when joining and launching threads, this should suffice as synchronization.

Re: Bug in reader/writer locks in Windows API

#79

Post by zozbot234 »

userbinator wrote: post #54

I'm curious if this also occurs in WINE's implementation. I also want to test this on my highly customised XP install which has been patched to add the SRW API among other extensions, and where I had also patched the kernel to fix a race condition causing a deadlock in the keyed event API that the SRW implementation is based on (maybe it's this same one, although in Vista+ they changed it significantly; but the same…

The code is here https://source.winehq.org/source/dlls/ntdll/sync.c#0474 and it uses compare exchange operations throughout, so it should be unaffected.

The ReactOS implementation is more involved https://doxygen.reactos.org/d1/db8/srw_8c_source.html but still, it uses mostly CAS operations both for the shared and the exclusive case. So it should be largely free from issues.

Re: Bug in reader/writer locks in Windows API

#80

Post by userbinator »

davekilian wrote: post #28

I was wondering how something so basic could go unnoticed for so long. Halfway down the page on OP's link, a user u/rbmm provides a compelling answer: that there are (possibly expected?) cases where a thread trying to acquire the lock in shared mode can accidentally get it in exclusive mode instead. This is due to interleaving of atomic bit test-and-[re]set operations between the (shared mode acquire) thread and the…

If that "rbmm" is the same person as I've seen on other sites, and the characteristic non-native English is a clue that it is, he certainly knows his stuff.

threads holding the lock don't wait for each other

Unless you're doing nested locking.

Post reply on HN