23 ms·

Bug in reader/writer locks in Windows API

287 points by Georgelemental 3y ago

mastax 3y ago
I understand why this is the case but it’s also extremely frustrating: > It is extremely difficult for programmer-users to report bugs against the Windows API (we're supposed to direct you to Feedback Hub, but you may as well transmit your message into deep space). I've filed OS-49268777 "SRWLOCK can deadlock after an exclusive owner has released ownership and several reader threads are attempting to acquire shared ownership together" with a slightly reduced repro. > Thanks for doing your homework and creating a self-contained repro, plus pre-emptively exonerating the STL. I've filed this OS bug as a special favor - bug reports are usually off-topic for r/cpp. The microsoft/STL GitHub repo is the proper channel for reporting STL misbehavior; it would have been acceptable here even though the root cause is in the Windows API because this situation is so rare. If you see STL misbehavior but it's clearly due to a compiler bug, reporting compiler bugs directly to VS Developer Community is the proper thing to do.
- adgjlsfhk1 3y ago
  The best way I know of to report bugs to windows is report them as documentation bugs. see for example https://github.com/MicrosoftDocs/cpp-docs/pull/3526 https://github.com/MicrosoftDocs/cpp-docs/pull/3526.
  - IshKebab 3y ago
    Clever!
    - kazinator 3y ago
      Clever until they just fix the documentation to match what the implementation is doing.
  - ddlsmurf 3y ago
    It looks like it was declared in Nov 21, and in May 23 they merged in the "fix" by adding "it's approximate" to the docs ( https://github.com/MicrosoftDocs/cpp-docs/commit/447b5d8a78111f3c3e820fc085a10640ed28d4a5 https://github.com/MicrosoftDocs/cpp-docs/commit/447b5d8a781... ), so not sure this is the best approach for actual bugs.
- 1over137 3y ago
  Nice to know that it's not just Apple to whom reporting bugs in hopeless. :)
  - masklinn 3y ago
    I generally assume that's the case for any large company. Sometimes I get pleasantly surprised, but generally speaking the internal incentives are skewed against, the primary focus is whatever the roadmap is followed by tickets from paying clients, public bugs generally have a very low hit ratio so they're unrewarding, unless you manage to snipe one of the company's employees (either nerd-snipe or interest / shock them enough to raise the issue internally) it's like playing the lottery.
    - jansan 3y ago
      > I generally assume that's the case for any large company. Despite Google partly losing its marbles recently, reporting bugs to Chromium still works very well.
      - bee_rider 3y ago
        I wonder if the open source element of the project keeps them “honest” to some extent?
      - GrumpySloth 3y ago
        Not my experience. When I report a bug in Chromium, it’s usually quickly verified as legit, and then left for dead forever.
    - generic92034 3y ago
      > I generally assume that's the case for any large company. What works to some degree are dedicated maintenance teams providing development support. If their main task is fixing bugs and they are evaluated on this basis, support tickets reporting real bugs have a good chance to receive the required attention. However, there is always the temptation for management to redirect resources from those teams. But at least in the B2B area costly customer escalations can remind management of the importance of good maintenance.
- jcalvinowens 3y ago
  > It is extremely difficult for programmer-users to report bugs against the Windows API I can't imagine living in this hell. When I find bugs in Linux, I E-mail the actual engineers directly and get responses in under 24 hours: https://lore.kernel.org/lkml/Zcb3_fdyJWUlZQci@gmail.com/ https://lore.kernel.org/lkml/Zcb3_fdyJWUlZQci@gmail.com/
  - charcircuit 3y ago
    Microsoft engineers have emails too.
    - dieortin 3y ago
      And how would you know what email to contact in a case like this one? It’s not about “having email”
      - charcircuit 3y ago
        You can either go down the route of finding the team that owns the code and then contacting someone on that team, or by contacting someone you know from the company to look it up for you or report the bug on your behalf.
        account42 3y ago
        > the route of finding the team that owns the code and then contacting someone on that team Nice circle, now the reader will only hav to fill in the rest of the owl. The benefit of the open open development model of Linux is that you don't have to have "someone you know" on the inside or essentially spam whatever contacts you can dig up until you find someone who has pity on you. You have actually publicly available developers (from many different companies, including hardware manufacturers) as well as real bug trackers where you can find if other users have had the same issue.
    - Tringi 3y ago
      And Twitter/X accounts. I have had a lot more things fixed in Windows or MSVC from nagging devs on there than from reporting through any official channel.
- TillE 3y ago
  Like the comment says, filing an issue on GitHub would've also eventually led to a proper internal report, so the system isn't wholly reliant on one guy trawling Reddit. I have many complaints about Win32 (having half a dozen different error code types, for one), but outright bugs are really rare.
deleted 3y ago
[deleted]
bingo3131 3y ago
Misleading title? This is a Windows API bug with the slim reader/writer (SRW) locks. It's just that the bug was discovered via std::shared_mutex as that is implemented using SRW locks. SRW locks: https://learn.microsoft.com/en-us/windows/win32/sync/slim-reader-writer--srw--locks https://learn.microsoft.com/en-us/windows/win32/sync/slim-re... Confirmation from a Microsoft employee that the bug has been raised internally with the Windows API team: https://old.reddit.com/r/cpp/comments/1b55686/maybe_possible_bug_in_stdshared_mutex_on_windows/kt3cndw/ https://old.reddit.com/r/cpp/comments/1b55686/maybe_possible...
- dang 3y ago
  Ok, I've changed the title to say that. Thanks!
- tialaramex 3y ago
  Yes, for example if you make a Rust std::sync:RWLock on Windows, it will literally be SRWLock because Microsoft advertises this API as having exactly the behaviour Rust wants so why would you build something worse instead ? Rust's Mutex on Windows is also an SRWLock but it can't hit this bug because it deliberately only uses the exclusive locking.
  - iknowstuff 3y ago
    So it doesn't use a shared lock when .read() is used?
    - zozbot234 3y ago
      Rust has both Mutex and RWLock. The Mutex only uses exclusive locks, there's no distinction between "read" and "write".
      - iknowstuff 3y ago
        Oh sorry my morning brain thought the comment was all about RWLock
amluto 3y ago
Once upon a time, you could buy various things from MS that came with support incidents. I had an MSDN subscription that came with two per year. Using an incident got you an actual support engineer who would be helpful and escalate issues if necessary. And, if your issue turned out to be a real bug of any significance in an MS product, your support incident would be credited back. This was great for developers (real support was available, and spam was discouraged), and it was great for MS (they found real issues that affected paying customers and they got feedback to improve their documentation). I wonder whether this program still exists. I have the impression the overall quality of MS documentation has declined.
- twisteriffic 3y ago
  That's Premier support, though now with a bunch of extra layers of contractors who can't do anything other than follow a script, capture traces and wait on the next level. In my experience it's been a time consuming waste of effort. I've had a lot better luck harvesting names and business cards from the teams at conferences and demo days, then going direct to the source.
- sebazzz 3y ago
  Generally as far as first line support goes, everything is outsourced to India. Cheaper, on paper. Anectodically, I tried to get support for something unrelated: I’m trying to use IMAP sync support in Outlook.com, but it refuses to work properly with iCloud-IMAP but doesn’t give any error message either. As a paying M365 subscriber I expect proper support. I tried over five times to get support, and every time it ended in frustration. Every time I got someone who either doesn’t understand to product, says IMAP support is not available and deprecated (it is not! I was able to set-up a different IMAP provider just fine), or I got redirected to the Windows or Office support team, who then couldn’t help me and closed my ticket.
  - Someone1234 3y ago
    Often times it just feels like they try to extend the ticket out as long as possible asking irrelevant questions, then as you said redirect you or close the ticket after wasting an appropriate amount of time. I cannot prove it, but I bet there is an internal number of replies before they can close without penalty.
AndrewStephens 3y ago
Subtle bugs in Reader/Writer locks do not surprise me. I worked on an in-house implementation based on Win32 (before C++11 and std::shared_mutex) and my recollection is that although the implementation sounds simple it is exceedingly easy to make subtle mistakes. The experience left me with such a bad feeling for shared locks that I tend to avoid them unless absolutely required. When I last tested std::shared_mutex, performance was so poor compared to std::mutex that double-buffering the data protected by a simple mutex was much faster. This was a great post by the original Redditor.
- convivialdingo 3y ago
  I did some work with testing a cross platform in-house library for read-write locking. We tested cmpxchg16b and found the performance was terrible with more than 4 cores. Ended up using spin-locks similar to Linux kernel RCU.
- tialaramex 3y ago
  SRWLock seems like a situation where it's small enough for you to construct proofs that what you did is correct, and important enough that the enormous expense of such proof is justified. The C++ std::mutex provided in Microsoft's STL is ludicrously big, whereas SRWLocks are the same size as a pointer. In one sense being ludicrously big is great - less risk the std::mutex will mistakenly share a cache line with your unrelated data, but for most people this makes std::mutex annoyingly expensive.
  - NeillC 3y ago
    Maybe my memory is faulty but I believe it was analyzed by Leslie Lamports stuff. Ofcourse your building a model of how it should work and you might have faults in that.
  - Const-me 3y ago
    C++ std::mutex provided in Microsoft's STL uses SRWLocks underneath, same size as a pointer. Sadly, SRWLocks have yet another bug, they are very unfair. Write a loop which locks std::mutex inside the body, and no other thread will be able to grab the mutex despite the loop repeatedly releases then re-acquires the mutex. Critical sections are way more fair.
chrisjj 3y ago
> Bug in reader/writer locks in Windows API Correction: Bug in reader/writer locks in Windows Not in API.
- valleyer 3y ago
  Thank you. Blaming the API is like saying there's a problem with your gas pedal after you blew a head gasket.
loeg 3y ago
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.
- Diggsey 3y ago
  I think part of the reason is that there's a very similar code pattern which is user error, and avoiding that pattern tends to avoid this pattern as well. The similar case occurs when you have: - 1+ threads holding a shared lock (Readers) - 1+ threads waiting to acquire an exclusive lock (Pending Writers) - 1+ threads trying to acquire the shared lock (Pending Readers) - 1+ Reader is waiting on a Pending Reader In this case the Pending Readers will be unable to acquire the shared lock even though it is still in "read mode" because in a fair RW lock Pending Writers are prioritised above Pending Readers so as not to starve the writer side of the lock.
- TillE 3y ago
  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.
davekilian 3y ago
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 (exclusive mode release) thread running simultaneously. The repro code holds the shared lock while waiting for all other threads to acquire the shared lock, and thus deadlocks if any of the worker threads accidentally gets an exclusive lock. In "normal" use cases where the lock is used to protect some shared resource, threads holding the lock don't wait for each other, so there is no deadlock. Interesting stuff!
- zozbot234 3y ago
  Why does it have to use bit test and set and interleave with other threads, though. AIUI you can use a CAS loop to implement any RMW atomically over word-sized (or double word sized, on many platforms) data. That seems like a no-brainer. For comparison, the Rust implementation for lightweight RWLocks on futex-capable *nix platforms is here: https://doc.rust-lang.org/stable/src/std/sys/unix/locks/futex_rwlock.rs.html https://doc.rust-lang.org/stable/src/std/sys/unix/locks/fute... It sets the "reader counter" in the underlying atomic to a special value to signal that the lock is set for exclusive access. So a reader thread acquiring the lock as shared can never result in this kind of bug. Bits are used to signal whether readers or writers are currently waiting on a lock, but this just cannot turn a lock that's acquired for shared access into exclusive, or vice versa.
  - NeillC 3y ago
    We use bit test and set as it causes us to get the cache line exclusive. This avoids using the prefetch write before fetching if we were to use CompareExchange. somebody was trying to talk to me about this stuff this morning but I didn't understand him. You can't expect a reader to always be compatible with other readers otherwise you livelock with a constant stream of readers. So we become incompatible. I am unsure if there is something beyond this.
Nition 3y ago
> It is extremely difficult for programmer-users to report bugs against the Windows API (we're supposed to direct you to Feedback Hub, but you may as well transmit your message into deep space). :'‑(
- Avamander 3y ago
  This is an issue with a lot of MS products. I honestly have no clue how much money one would have to throw at MS to get a bug fixed. For example Microsoft's *own* Pluton-enabled platforms fail Windows' Device Health Attestation checks due to an incomplete chain (https://call4cloud.nl/2023/04/are-you-there-intune-its-me-hac/ https://call4cloud.nl/2023/04/are-you-there-intune-its-me-ha...).
  - Nition 3y ago
    I've noticed a lot of big products have a user feedback cycle that goes something like this: - Create new feedback tracker - Direct feedback to tracker - Stop paying any attention to tracker - Tracker is hundreds of pages of users shouting into the void, and much of it out-of-date - Delete everything - Create new feedback tracker...
    - Nition 3y ago
      There's nothing worse than having a problem with a product, finding 250 other people on the feedback tracker that have had the same problem over the last three years, and the only official response is some support person on the first page who's saying your feedback is very important to us, and have you tried [troubleshooting that won't work]?
      - Avamander 3y ago
        At that scale they have 250 000 people that didn't try the obvious troubleshooting first though. But yes, it's annoying.
        3y ago
userbinator 3y ago
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 edge case could occur.)
- nightowl_games 3y ago
  How did you patch the kernel? Like how is that possible?
  - userbinator 3y ago
    With a hex editor, debugger, and skills that most developers these days seem to lack. I patched the kernel in memory first, using a kernel debugger, to verify my fix worked before editing the file on disk.
    - mangamadaiyan 3y ago
      Windbg or SoftICE? :)
      - userbinator 3y ago
        Windbg; it's free and doesn't require any setup to do this: https://learn.microsoft.com/en-us/windows-hardware/drivers/debugger/performing-local-kernel-debugging https://learn.microsoft.com/en-us/windows-hardware/drivers/d... (Working out how to patch such that I wouldn't crash the system if a process happens to call that API while it was in a half-modified state was also a fun problem...) I dug out the details on the bug I patched, and it isn't the same as this one; it's a race condition with timeouts on waiting for keyed events, which I believe isn't applicable in this situation as there are no timeouts.
    - Iwan-Zotow 3y ago
ww520 3y ago
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<int32_t> readCounter = 0; }; // child thread DoStuff() { data->readCounter.fetch_add(1); while (data->readCounter.load() != data->numThreads) { std::this_thread::yield(); } } The numThreads field is not an atomic variable. It's initialized to 0 and set to 5 in the main thread. 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. A child thread might get the old value 0. The logic of the yield checking loop using it would never exit. Since the main thread runs the code in an endless loop, the same numThreads memory allocated on the stack is being set to 0 and 5 repeatedly. Some of the child threads can get the old value in one pass of the loop. Thus the hanging.
- userbinator 3y ago
  You seem to have missed the part where an actual MS employee confirmed it was a bug in their API.
  - ww520 3y ago
    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.
    - forrestthewoods 3y ago
      > 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.

I understand why this is the case but it’s also extremely frustrating: > It is extremely difficult for programmer-users to report bugs against the Windows API (we're supposed to direct you to Feedback Hub, but you may as well transmit your message into deep space). I've filed OS-49268777 "SRWLOCK can deadlock after an exclusive owner has released ownership and several reader threads are attempting to acquire shared ownership together" with a slightly reduced repro. > Thanks for doing your homework and creating a self-contained repro, plus pre-emptively exonerating the STL. I've filed this OS bug as a special favor - bug reports are usually off-topic for r/cpp. The microsoft/STL GitHub repo is the proper channel for reporting STL misbehavior; it would have been acceptable here even though the root cause is in the Windows API because this situation is so rare. If you see STL misbehavior but it's clearly due to a compiler bug, reporting compiler bugs directly to VS Developer Community is the proper thing to do.

adgjlsfhk1 3y ago
The best way I know of to report bugs to windows is report them as documentation bugs. see for example https://github.com/MicrosoftDocs/cpp-docs/pull/3526 https://github.com/MicrosoftDocs/cpp-docs/pull/3526.
- IshKebab 3y ago
  Clever!
  - kazinator 3y ago
    Clever until they just fix the documentation to match what the implementation is doing.
- ddlsmurf 3y ago
  It looks like it was declared in Nov 21, and in May 23 they merged in the "fix" by adding "it's approximate" to the docs ( https://github.com/MicrosoftDocs/cpp-docs/commit/447b5d8a78111f3c3e820fc085a10640ed28d4a5 https://github.com/MicrosoftDocs/cpp-docs/commit/447b5d8a781... ), so not sure this is the best approach for actual bugs.
1over137 3y ago
Nice to know that it's not just Apple to whom reporting bugs in hopeless. :)
- masklinn 3y ago
  I generally assume that's the case for any large company. Sometimes I get pleasantly surprised, but generally speaking the internal incentives are skewed against, the primary focus is whatever the roadmap is followed by tickets from paying clients, public bugs generally have a very low hit ratio so they're unrewarding, unless you manage to snipe one of the company's employees (either nerd-snipe or interest / shock them enough to raise the issue internally) it's like playing the lottery.
  - jansan 3y ago
    > I generally assume that's the case for any large company. Despite Google partly losing its marbles recently, reporting bugs to Chromium still works very well.
    - bee_rider 3y ago
      I wonder if the open source element of the project keeps them “honest” to some extent?
    - GrumpySloth 3y ago
      Not my experience. When I report a bug in Chromium, it’s usually quickly verified as legit, and then left for dead forever.
  - generic92034 3y ago
    > I generally assume that's the case for any large company. What works to some degree are dedicated maintenance teams providing development support. If their main task is fixing bugs and they are evaluated on this basis, support tickets reporting real bugs have a good chance to receive the required attention. However, there is always the temptation for management to redirect resources from those teams. But at least in the B2B area costly customer escalations can remind management of the importance of good maintenance.
jcalvinowens 3y ago
> It is extremely difficult for programmer-users to report bugs against the Windows API I can't imagine living in this hell. When I find bugs in Linux, I E-mail the actual engineers directly and get responses in under 24 hours: https://lore.kernel.org/lkml/Zcb3_fdyJWUlZQci@gmail.com/ https://lore.kernel.org/lkml/Zcb3_fdyJWUlZQci@gmail.com/
- charcircuit 3y ago
  Microsoft engineers have emails too.
  - dieortin 3y ago
    And how would you know what email to contact in a case like this one? It’s not about “having email”
    - charcircuit 3y ago
      You can either go down the route of finding the team that owns the code and then contacting someone on that team, or by contacting someone you know from the company to look it up for you or report the bug on your behalf.
      - account42 3y ago
        > the route of finding the team that owns the code and then contacting someone on that team Nice circle, now the reader will only hav to fill in the rest of the owl. The benefit of the open open development model of Linux is that you don't have to have "someone you know" on the inside or essentially spam whatever contacts you can dig up until you find someone who has pity on you. You have actually publicly available developers (from many different companies, including hardware manufacturers) as well as real bug trackers where you can find if other users have had the same issue.
  - Tringi 3y ago
    And Twitter/X accounts. I have had a lot more things fixed in Windows or MSVC from nagging devs on there than from reporting through any official channel.
TillE 3y ago
Like the comment says, filing an issue on GitHub would've also eventually led to a proper internal report, so the system isn't wholly reliant on one guy trawling Reddit. I have many complaints about Win32 (having half a dozen different error code types, for one), but outright bugs are really rare.

deleted 3y ago

[deleted]

bingo3131 3y ago

Misleading title? This is a Windows API bug with the slim reader/writer (SRW) locks. It's just that the bug was discovered via std::shared_mutex as that is implemented using SRW locks. SRW locks: https://learn.microsoft.com/en-us/windows/win32/sync/slim-reader-writer--srw--locks https://learn.microsoft.com/en-us/windows/win32/sync/slim-re... Confirmation from a Microsoft employee that the bug has been raised internally with the Windows API team: https://old.reddit.com/r/cpp/comments/1b55686/maybe_possible_bug_in_stdshared_mutex_on_windows/kt3cndw/ https://old.reddit.com/r/cpp/comments/1b55686/maybe_possible...

dang 3y ago
Ok, I've changed the title to say that. Thanks!
tialaramex 3y ago
Yes, for example if you make a Rust std::sync:RWLock on Windows, it will literally be SRWLock because Microsoft advertises this API as having exactly the behaviour Rust wants so why would you build something worse instead ? Rust's Mutex on Windows is also an SRWLock but it can't hit this bug because it deliberately only uses the exclusive locking.
- iknowstuff 3y ago
  So it doesn't use a shared lock when .read() is used?
  - zozbot234 3y ago
    Rust has both Mutex and RWLock. The Mutex only uses exclusive locks, there's no distinction between "read" and "write".
    - iknowstuff 3y ago
      Oh sorry my morning brain thought the comment was all about RWLock

amluto 3y ago

Once upon a time, you could buy various things from MS that came with support incidents. I had an MSDN subscription that came with two per year. Using an incident got you an actual support engineer who would be helpful and escalate issues if necessary. And, if your issue turned out to be a real bug of any significance in an MS product, your support incident would be credited back. This was great for developers (real support was available, and spam was discouraged), and it was great for MS (they found real issues that affected paying customers and they got feedback to improve their documentation). I wonder whether this program still exists. I have the impression the overall quality of MS documentation has declined.

twisteriffic 3y ago
That's Premier support, though now with a bunch of extra layers of contractors who can't do anything other than follow a script, capture traces and wait on the next level. In my experience it's been a time consuming waste of effort. I've had a lot better luck harvesting names and business cards from the teams at conferences and demo days, then going direct to the source.
sebazzz 3y ago
Generally as far as first line support goes, everything is outsourced to India. Cheaper, on paper. Anectodically, I tried to get support for something unrelated: I’m trying to use IMAP sync support in Outlook.com, but it refuses to work properly with iCloud-IMAP but doesn’t give any error message either. As a paying M365 subscriber I expect proper support. I tried over five times to get support, and every time it ended in frustration. Every time I got someone who either doesn’t understand to product, says IMAP support is not available and deprecated (it is not! I was able to set-up a different IMAP provider just fine), or I got redirected to the Windows or Office support team, who then couldn’t help me and closed my ticket.
- Someone1234 3y ago
  Often times it just feels like they try to extend the ticket out as long as possible asking irrelevant questions, then as you said redirect you or close the ticket after wasting an appropriate amount of time. I cannot prove it, but I bet there is an internal number of replies before they can close without penalty.

AndrewStephens 3y ago

Subtle bugs in Reader/Writer locks do not surprise me. I worked on an in-house implementation based on Win32 (before C++11 and std::shared_mutex) and my recollection is that although the implementation sounds simple it is exceedingly easy to make subtle mistakes. The experience left me with such a bad feeling for shared locks that I tend to avoid them unless absolutely required. When I last tested std::shared_mutex, performance was so poor compared to std::mutex that double-buffering the data protected by a simple mutex was much faster. This was a great post by the original Redditor.

convivialdingo 3y ago
I did some work with testing a cross platform in-house library for read-write locking. We tested cmpxchg16b and found the performance was terrible with more than 4 cores. Ended up using spin-locks similar to Linux kernel RCU.
tialaramex 3y ago
SRWLock seems like a situation where it's small enough for you to construct proofs that what you did is correct, and important enough that the enormous expense of such proof is justified. The C++ std::mutex provided in Microsoft's STL is ludicrously big, whereas SRWLocks are the same size as a pointer. In one sense being ludicrously big is great - less risk the std::mutex will mistakenly share a cache line with your unrelated data, but for most people this makes std::mutex annoyingly expensive.
- NeillC 3y ago
  Maybe my memory is faulty but I believe it was analyzed by Leslie Lamports stuff. Ofcourse your building a model of how it should work and you might have faults in that.
- Const-me 3y ago
  C++ std::mutex provided in Microsoft's STL uses SRWLocks underneath, same size as a pointer. Sadly, SRWLocks have yet another bug, they are very unfair. Write a loop which locks std::mutex inside the body, and no other thread will be able to grab the mutex despite the loop repeatedly releases then re-acquires the mutex. Critical sections are way more fair.

chrisjj 3y ago

> Bug in reader/writer locks in Windows API Correction: Bug in reader/writer locks in Windows Not in API.

valleyer 3y ago
Thank you. Blaming the API is like saying there's a problem with your gas pedal after you blew a head gasket.

loeg 3y ago

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.

Diggsey 3y ago
I think part of the reason is that there's a very similar code pattern which is user error, and avoiding that pattern tends to avoid this pattern as well. The similar case occurs when you have: - 1+ threads holding a shared lock (Readers) - 1+ threads waiting to acquire an exclusive lock (Pending Writers) - 1+ threads trying to acquire the shared lock (Pending Readers) - 1+ Reader is waiting on a Pending Reader In this case the Pending Readers will be unable to acquire the shared lock even though it is still in "read mode" because in a fair RW lock Pending Writers are prioritised above Pending Readers so as not to starve the writer side of the lock.
TillE 3y ago
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.

davekilian 3y ago

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 (exclusive mode release) thread running simultaneously. The repro code holds the shared lock while waiting for all other threads to acquire the shared lock, and thus deadlocks if any of the worker threads accidentally gets an exclusive lock. In "normal" use cases where the lock is used to protect some shared resource, threads holding the lock don't wait for each other, so there is no deadlock. Interesting stuff!

zozbot234 3y ago
Why does it have to use bit test and set and interleave with other threads, though. AIUI you can use a CAS loop to implement any RMW atomically over word-sized (or double word sized, on many platforms) data. That seems like a no-brainer. For comparison, the Rust implementation for lightweight RWLocks on futex-capable *nix platforms is here: https://doc.rust-lang.org/stable/src/std/sys/unix/locks/futex_rwlock.rs.html https://doc.rust-lang.org/stable/src/std/sys/unix/locks/fute... It sets the "reader counter" in the underlying atomic to a special value to signal that the lock is set for exclusive access. So a reader thread acquiring the lock as shared can never result in this kind of bug. Bits are used to signal whether readers or writers are currently waiting on a lock, but this just cannot turn a lock that's acquired for shared access into exclusive, or vice versa.
- NeillC 3y ago
  We use bit test and set as it causes us to get the cache line exclusive. This avoids using the prefetch write before fetching if we were to use CompareExchange. somebody was trying to talk to me about this stuff this morning but I didn't understand him. You can't expect a reader to always be compatible with other readers otherwise you livelock with a constant stream of readers. So we become incompatible. I am unsure if there is something beyond this.

Nition 3y ago

> It is extremely difficult for programmer-users to report bugs against the Windows API (we're supposed to direct you to Feedback Hub, but you may as well transmit your message into deep space). :'‑(

Avamander 3y ago
This is an issue with a lot of MS products. I honestly have no clue how much money one would have to throw at MS to get a bug fixed. For example Microsoft's *own* Pluton-enabled platforms fail Windows' Device Health Attestation checks due to an incomplete chain (https://call4cloud.nl/2023/04/are-you-there-intune-its-me-hac/ https://call4cloud.nl/2023/04/are-you-there-intune-its-me-ha...).
- Nition 3y ago
  I've noticed a lot of big products have a user feedback cycle that goes something like this: - Create new feedback tracker - Direct feedback to tracker - Stop paying any attention to tracker - Tracker is hundreds of pages of users shouting into the void, and much of it out-of-date - Delete everything - Create new feedback tracker...
  - Nition 3y ago
    There's nothing worse than having a problem with a product, finding 250 other people on the feedback tracker that have had the same problem over the last three years, and the only official response is some support person on the first page who's saying your feedback is very important to us, and have you tried [troubleshooting that won't work]?
    - Avamander 3y ago
      At that scale they have 250 000 people that didn't try the obvious troubleshooting first though. But yes, it's annoying.
      - 3y ago

userbinator 3y ago

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 edge case could occur.)

nightowl_games 3y ago
How did you patch the kernel? Like how is that possible?
- userbinator 3y ago
  With a hex editor, debugger, and skills that most developers these days seem to lack. I patched the kernel in memory first, using a kernel debugger, to verify my fix worked before editing the file on disk.
  - mangamadaiyan 3y ago
    Windbg or SoftICE? :)
    - userbinator 3y ago
      Windbg; it's free and doesn't require any setup to do this: https://learn.microsoft.com/en-us/windows-hardware/drivers/debugger/performing-local-kernel-debugging https://learn.microsoft.com/en-us/windows-hardware/drivers/d... (Working out how to patch such that I wouldn't crash the system if a process happens to call that API while it was in a half-modified state was also a fun problem...) I dug out the details on the bug I patched, and it isn't the same as this one; it's a race condition with timeouts on waiting for keyed events, which I believe isn't applicable in this situation as there are no timeouts.
  - Iwan-Zotow 3y ago

ww520 3y ago

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<int32_t> readCounter = 0; }; // child thread DoStuff() { data->readCounter.fetch_add(1); while (data->readCounter.load() != data->numThreads) { std::this_thread::yield(); } } The numThreads field is not an atomic variable. It's initialized to 0 and set to 5 in the main thread. 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. A child thread might get the old value 0. The logic of the yield checking loop using it would never exit. Since the main thread runs the code in an endless loop, the same numThreads memory allocated on the stack is being set to 0 and 5 repeatedly. Some of the child threads can get the old value in one pass of the loop. Thus the hanging.

userbinator 3y ago
You seem to have missed the part where an actual MS employee confirmed it was a bug in their API.
- ww520 3y ago
  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.
  - forrestthewoods 3y ago
    > 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.