tag:blogger.com,1999:blog-8231772264325864647.post3534363989551529847..comments2024-03-22T19:05:00.088+01:00Comments on Concurrency Freaks: Implementing a Reader-Writer Lock using RCUPedro Ramalhetehttp://www.blogger.com/profile/01340437958052998917noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-8231772264325864647.post-14627428560498920562015-10-26T10:46:26.949+01:002015-10-26T10:46:26.949+01:00Dope... you're absolutely right about needing ...Dope... you're absolutely right about needing memory_order_release on exclusiveLock(). Without the release, it could re-odered into the critical section.<br />Good catch!<br /><br />Regarding the PS, yes you're right, same logic. It needs a memory_order_acquire.<br /><br /><br />The deadlock, yes I get it, you're talking about the kernel implementation.<br />If it's a userspace implementation of RCU like the one we have inside the Classic Left-Right technique (or your own implementation?), then the deadlock issue doesn't occur. And I think SRCU doesn't suffer from this issue either because we can have more than one of those... I'll have to dig into it a bit more to be certain.<br />Even for the kernel implementation, I think that synchronize_rcu() has a mechanism to detect whether rcu_read_lock() has been called from the same thread (I'm not certain this is true, and certainly not for all implementations), and anyways, it would still give inconsistent results if more than one rw-lock instance is used.<br /><br />Great code review, thanks David!Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-64381089275921262482015-10-26T06:06:57.115+01:002015-10-26T06:06:57.115+01:00Hi Pedro,
Regarding memory order:
The issue is, y...Hi Pedro,<br /><br />Regarding memory order:<br />The issue is, you need something like a release fence *before* the writerWaiting store in exclusiveUnlock. An example reordering that could cause a problem is if the writerWaiting store moves up inside the critical section (say, to a point when half the protected data has been updated but not the other half): then a call to sharedLock() might finish while a writer is still making modifications to protected data. (I believe that a similar analysis will show the optimization you mention in your PS to be unsafe; the acquire fence has to be *after* the relevant load, not before it. I'm not sure enough about the ordering semantics of (U)RCU to speak to the PPS.).<br /><br />Regarding deadlock:<br />Consider:<br />void t1() {<br /> rwlock1.sharedLock();<br /> A:<br /> rwlock2.exclusiveLock();<br />}<br /><br />void t2() {<br /> rwlock3.sharedLock();<br /> B:<br /> rwlock4.exclusiveLock();<br />}<br /><br />Suppose thread t1 runs to label A and then thread t2 runs to label B. At that point, neither of the threads can successfully enter their exclusive lock critical sections, since they will be stuck in a synchronize_rcu() call that will never return, since it's blocked by the other thread's presence in a rcu read-side critical section. (In fact, either thread by itself will deadlock; but this example works even if synchronize_rcu is modified to not require a quiescent state from the calling thread to occur).David Goldblatthttp://dgoldblatt.comnoreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-76102475078758926462015-10-25T23:37:44.133+01:002015-10-25T23:37:44.133+01:00Hi David,
Not a typo. We don't need to use me...Hi David,<br /><br />Not a typo. We don't need to use memory_order_release on exclusiveUnlock() because the writersMutex.unlock() has release semantics and will guarantee visibility of the change to writerWaiting.<br />Theoretically, there is no "synchronizes with" of writersMutex.unlock() with the writerWaiting.load() in sharedLock(), but in practice there must be some fence in the unlock() method, and even if there wasn't, then at most we could have some Readers waiting "too long" on sharedLock(), but they would eventually see writerWaiting changing to false.<br /><br /><br />I don't understand the second comment. Can you go into more details?<br />Is it because synchronize_rcu() can not be called from multiple threads on kernel space?<br />Notice that the call to synchronize_rcu() is protected by the std::mutex, so I don't see any possibility of deadlock in userspace.<br /><br /><br />PS: To optimize even further, in sharedLock(), the second load on writerWaiting() can be std::memory_order_relaxed. This is possible because rcu_read_lock() has "acquire semantics".<br /><br />PPS: ... and in exclusiveLock() we can replace the seq-cst store with a relaxed store:<br /> writerWaiting.store(true, std::memory_order_relaxed)<br />;)Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-7577567527759569952015-10-25T23:10:32.792+01:002015-10-25T23:10:32.792+01:00Minor Typo: you need at least std::memory_order_re...Minor Typo: you need at least std::memory_order_release in exclusiveUnlock.<br /><br />Also worth noting is that this can deadlock if multiple of these locks are used; only one RW is possible per RCU domain.David Goldblatthttp://dgoldblatt.comnoreply@blogger.com