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

131–140 of 142 posts

Re: Bug in reader/writer locks in Windows API

#131

Post by quotemstr »

NeillC wrote: post #120
quotemstr wrote: post #118

Earlier quoted context omitted.

> My overall rule of thumb is that in the presence of any exclusive acquires you can never assume a shared acquire is compatible with any other shared acquire. Contract #1: In reader writer locks in general, after I share-acquire a lock, I know that there are no active exclusive owners of that lock and won't be until I release my shared lock. I can also expect that as long as I hold this shared lock, other threads ca…

It's typical not to allow a second share acquire to proceed if we have an exclusive waiter: t1: share t2: exclusive so waits t3: share also waits Thats how we arrive at the rule that shared acquires in anything, but a trivial system (no exclusive acquires) may not be compatible. So, contract #1 is typically not satisfied. Of course, this particular case is slightly different and so you might decide to support it.

I meant that contract #1 is that when I, thread A, already have a lock held in shared mode, I can expect shared-acquires on thread B to succeed without my first giving up my shared lock. The problem that we're discussing here is that I, A, can ask for a shared lock but actually and unknowingly get an exclusive lock. There's no exclusive-acquire involved.

Re: Bug in reader/writer locks in Windows API

#132

Post by rbmm »

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…

what is shared mode ? this is by fact optimization for speed, if we need read-only access to data, we allow to system let another thread into the section that requests shared access also

allow but NOT DEMAND this. If one thread has acquired the shared lock , other thread can acquire the shared lock too. but only CAN. in some case system not let another thread enter to lock, despite it also request share access. one case: if another rthread request exclusive acess - he begin wait and after this - any thread which acquire even shared access to lock - also begin wait

If lock_shared is called by a thread that already owns the mutex in any mode (exclusive or shared), the behavior is undefined.

and

Shared mode SRW locks should not be acquired recursively as this can lead to deadlocks when combined with exclusive acquisition.

why is this ? because if between 2 calls to lock_shared ( AcquireSRWLockShared ) another thread call AcquireSRWLockExclusive - the second call is block.

the code in example make assumption that ALL threads can enter to lock at once. that if one thread enter to lock in shared mode, another thread also ALWAYS can enter to lock in shared mode (if no exclusive requests). but i not view clear formalization of such requirement. and we must not based on this.

i be will add next rule:

thread inside lock must not wait on another thread to enter this lock

this is obvivius for exlusive access, but not obvivous to shared. but must be cleare stated along with the recursive rule ( should not be acquired recursively as this can lead to deadlocks, even in shared mode)

Re: Bug in reader/writer locks in Windows API

#133

Post by rbmm »

quotemstr wrote: post #131
NeillC wrote: post #120

Earlier quoted context omitted.

It's typical not to allow a second share acquire to proceed if we have an exclusive waiter: t1: share t2: exclusive so waits t3: share also waits Thats how we arrive at the rule that shared acquires in anything, but a trivial system (no exclusive acquires) may not be compatible. So, contract #1 is typically not satisfied. Of course, this particular case is slightly different and so you might decide to support it.

I meant that contract #1 is that when I, thread A, already have a lock held in shared mode, I can expect shared-acquires on thread B to succeed without my first giving up my shared lock. The problem that we're discussing here is that I, A, can ask for a shared lock but actually and unknowingly get an exclusive lock. There's no exclusive-acquire involved.

"other threads can share-acquire the same lock without waiting." can but not always and mandatory. you really allow to system enter another shared requestor. but only allow,not demand. system not let shared requestor enter to lock, if before it the exclusive request will be. after first exclusive request - all next shared request will block, util this exclusive request not acquire and then release lock. can be and some another reason, in the end - this is only optimization - you only *allow* multiple shared enter at once. so i be not say that this is implementation bug

Re: Bug in reader/writer locks in Windows API

#134

Post by tialaramex »

Const-me wrote: post #109
tialaramex wrote: post #39

Earlier quoted context omitted.

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…

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.

> C++ std::mutex provided in Microsoft's STL uses SRWLocks underneath, same size as a pointer.

The SRWLocks are indeed the size of a pointer, the std::mutex is not for ABI reasons.

Re: Bug in reader/writer locks in Windows API

#135

Post by netcruiser »

rbmm wrote: post #132
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…

what is shared mode ? this is by fact optimization for speed, if we need read-only access to data, we allow to system let another thread into the section that requests shared access also allow but NOT DEMAND this. If one thread has acquired the shared lock , other thread can acquire the shared lock too. but only CAN. in some case system not let another thread enter to lock, despite it also request share access. one c…

The read threads block because the ReadWriteLock algorithm tries to prevent thread starvation (i.e. when the exclusive lock never gets acquired). Most ReadWriteLock implementation alternate between giving the read locks then the exclusive locks access to the lock.

Re: Bug in reader/writer locks in Windows API

#136

Post by rbmm »

netcruiser wrote: post #135
rbmm wrote: post #132

Earlier quoted context omitted.

what is shared mode ? this is by fact optimization for speed, if we need read-only access to data, we allow to system let another thread into the section that requests shared access also allow but NOT DEMAND this. If one thread has acquired the shared lock , other thread can acquire the shared lock too. but only CAN. in some case system not let another thread enter to lock, despite it also request share access. one c…

The read threads block because the ReadWriteLock algorithm tries to prevent thread starvation (i.e. when the exclusive lock never gets acquired). Most ReadWriteLock implementation alternate between giving the read locks then the exclusive locks access to the lock.

of course - SRW lock allow shared access only if no waiters ( request to exclusive access) on lock. so even if lock in shared mode, new shared request can block, if was waiter(exclusive) already. in case OP no exactly this, but anyway - i be say that shared access is only hint to system, that it can optimize access - and allow multiple shared threads inside lock. but this was not always

Re: Bug in reader/writer locks in Windows API

#137

Post by quotemstr »

rbmm wrote: post #133
quotemstr wrote: post #131

Earlier quoted context omitted.

I meant that contract #1 is that when I, thread A, already have a lock held in shared mode, I can expect shared-acquires on thread B to succeed without my first giving up my shared lock. The problem that we're discussing here is that I, A, can ask for a shared lock but actually and unknowingly get an exclusive lock. There's no exclusive-acquire involved.

"other threads can share-acquire the same lock without waiting." can but not always and mandatory. you really allow to system enter another shared requestor. but only allow,not demand. system not let shared requestor enter to lock, if before it the exclusive request will be. after first exclusive request - all next shared request will block, util this exclusive request not acquire and then release lock. can be and so…

So we have to treat shared acquires as exclusive ones just in case an exclusive acquire comes along? What if I know that my program doesn't do that?

Re: Bug in reader/writer locks in Windows API

#138

Post by rbmm »

quotemstr wrote: post #137
rbmm wrote: post #133

Earlier quoted context omitted.

"other threads can share-acquire the same lock without waiting." can but not always and mandatory. you really allow to system enter another shared requestor. but only allow,not demand. system not let shared requestor enter to lock, if before it the exclusive request will be. after first exclusive request - all next shared request will block, util this exclusive request not acquire and then release lock. can be and so…

So we have to treat shared acquires as exclusive ones just in case an exclusive acquire comes along? What if I know that my program doesn't do that?

yes. after any thread request exclusive access to lock, the sequential shared acquire request will block. this iswell known fact, i hope. this is example when shared request will be blocked, despite shared owner(s) now inside lock

also look my 2 comments on reddit: https://www.reddit.com/r/cpp/comments/1b55686/comment/ktfhjs... and https://www.reddit.com/r/cpp/comments/1b55686/comment/ktfggu...

if say true - i here in very strange position. i am by self under debugger research exacly what happens in concrete case and create repro code. i think that implementation of the RtlReleaseSRWLockExclusive is not the best and may be really containing "bug" as i in more details describe in comment on reddit. but from another side, if you want pure formal c++ rules - can you explain - in what exactly was bug in concre case ? what rule/guarantee is violated ? why demo code decide that ALL shared waiters can at once acquire the lock. formal documentation not state this. this intuitive must be true, because no exclusive request more. but.. i really dont know. and i also for fun create own implementation of SRW lock ( if someone interested to look -https://github.com/rbmm/PushLock ) which free from this roblem - i always ( hope) do only single atomic change to lock state during api call. and finally - sorry for my english and too long answer

Re: Bug in reader/writer locks in Windows API

#139

Post by account42 »

charcircuit wrote: post #46
dieortin wrote: post #41

Earlier quoted context omitted.

And how would you know what email to contact in a case like this one? It’s not about “having email”

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.

> 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.

Re: Bug in reader/writer locks in Windows API

#140

Post by account42 »

amluto wrote: post #91
Avamander wrote: post #38

Earlier quoted context omitted.

There are multiple providers out there that have their own stacks (Google, Microsoft, Tutanota, Protonmail to some extent and others) and there are those that use more common combinations (basically just managed mail-in-a-box). Nothing perfect though, so pick your poison. Some issues are also due to the ecosystem itself. Avoiding POP3 goes a long way for example.

Avoiding POP3 is great. Some people like to say the future is JMAP, but those same people provide such a weak mobile email app that I find it hard to believe. Maybe the protocol can do better than the app by the same vendor?

IMAP, as horrible as it is on a technical level, does the job just fine.
Post reply on HN