Community
Participate
Working Groups
Build Identifier: These index lock related functions are in WritableCIndex class: public synchronized void acquireReadLock() throws InterruptedException; public synchronized void releaseReadLock(); public synchronized void acquireWriteLock(int giveupReadlockCount) throws InterruptedException; We found out that a deadlock could happen in the following sequence: let see a WritableCIndex called cindex, cindex.acquireReadLock(); cindex.acquireWriteLock(0); cindex.releaseReadLock(); I know if giveupReadlockCount is given as 1, the deadlock won't be hit. But my point here is that the deadlock should not happen in any case. This is actually a real case happens in RDT, in which call hierarchy function first acquired a read lock from an CIndex, and reindex function (which is not aware of call hierarchy has gained a read lock) tries to acquire a write lock from the cIndex after, when the call hierarchy function completes job and tries to release its read lock, it won't do so since the reindex functions has not acquired the write lock yet. Then the deadlock happens. Please refer another RDT bugzilla for details, https://bugs.eclipse.org/bugs/show_bug.cgi?id=330505 Reproducible: Always
In CDT itself only the indexer obtains write-locks and it keeps track of whether it holds read-locks on the index or not. Therefore we can avoid a more complex implementation of the locking that would need to count read-locks per thread. The method works as expected and is internal. If you use it you need to count your read-locks and give them up when obtaining the write lock.
(In reply to comment #1) > In CDT itself only the indexer obtains write-locks and it keeps track of > whether it holds read-locks on the index or not. Therefore we can avoid a more > complex implementation of the locking that would need to count read-locks per > thread. > The method works as expected and is internal. If you use it you need to count > your read-locks and give them up when obtaining the write lock. I am not sure why acquiring write-lock function needs to know a certain number of read-locks to give up? Another way to ask this question, in which situation we don't want acquiring write-lock function to give up some read-locks? I guess we would never want this situation happen since it will lead a deadlock for sure, just like what we got in RDT. Actually our problem happens in StandaloneIndexer which is also a CDT class. I am just thinking two options for this problem: 1, Make a precedence rule to make write-lock taking precedence over all read-locks? So whenever an indexer needs to acquire a write-lock, it will give up all of active read-locks. 2, Keep the current implementation and adding a special case to let acquireWriteLock function to give up all read-locks when it is given a "-1" to its argument "giveupReadlockCount", like cindex.acquireWriteLock(-1); Please let me know if any of these two options would be reasonable to fix this problem?
(In reply to comment #2) > I am not sure why acquiring write-lock function needs to know a certain number > of read-locks to give up? Another way to ask this question, in which situation > we don't want acquiring write-lock function to give up some read-locks? I guess > we would never want this situation happen since it will lead a deadlock for > sure, just like what we got in RDT. The indexer itself tries to keep write-locks as short as possible, therefore it switches forth and back between read-lock and write-lock. The only read-locks it needs to give up are the ones aquired by the indexer in the same thread. Apparently the indexer has to make sure not to access outdated objects from the index after a write operation. There are no other clients that need to obtain write locks. The sequence described in comment 0 looks like the actual bug: Call Hierarchy aquiring a read-lock and then either reindexing in the same thread or issuing a reindex and waiting until the reindexing completes. How should that ever work, the indexer will need to wait until the read-locks are released. > ... > I am just thinking two options for this problem: > 1, Make a precedence rule to make write-lock taking precedence over all > read-locks? So whenever an indexer needs to acquire a write-lock, it will give > up all of active read-locks. This is not an option, the read-lock is a guarantee, that the index will not change. This is critical because using outdated objects from the index can cause accessing invalid or overwritten areas of the index. > 2, Keep the current implementation and adding a special case to let > acquireWriteLock function to give up all read-locks when it is given a > "-1" to its argument "giveupReadlockCount", like cindex.acquireWriteLock(-1); > Please let me know if any of these two options would be reasonable to fix this > problem? Again, for the same reason this is not an option.
(In reply to comment #3) > (In reply to comment #2) > > I am not sure why acquiring write-lock function needs to know a certain number > > of read-locks to give up? Another way to ask this question, in which situation > > we don't want acquiring write-lock function to give up some read-locks? I guess > > we would never want this situation happen since it will lead a deadlock for > > sure, just like what we got in RDT. > The indexer itself tries to keep write-locks as short as possible, therefore it > switches forth and back between read-lock and write-lock. The only read-locks > it needs to give up are the ones aquired by the indexer in the same thread. > Apparently the indexer has to make sure not to access outdated objects from the > index after a write operation. There are no other clients that need to obtain > write locks. > The sequence described in comment 0 looks like the actual bug: Call Hierarchy > aquiring a read-lock and then either reindexing in the same thread or issuing a > reindex and waiting until the reindexing completes. How should that ever work, > the indexer will need to wait until the read-locks are released. The scenario is Call hierarchy and reindex requests are called from two different threads, but they both get a same index from StandaloneIndexer, then the sequence described in comment 0 may happen depends on how fast of call hierarchy searching. I see CDT handles this situation by using two different Cindexes (for different threads) to handle a same pdom fragment. So I currently fix RDT in this way too. Another way to fix it is making StandaloneIndexer keeps track of number of read lock (could be acquired from different threads) to its index, then give up these read locks when index acquires write lock. Both either way seems also break the read lock guarantee, that the index will not change. Please let me know if you have a better suggestion. > > ... > > I am just thinking two options for this problem: > > 1, Make a precedence rule to make write-lock taking precedence over all > > read-locks? So whenever an indexer needs to acquire a write-lock, it will give > > up all of active read-locks. > This is not an option, the read-lock is a guarantee, that the index will not > change. This is critical because using outdated objects from the index can > cause accessing invalid or overwritten areas of the index. > > 2, Keep the current implementation and adding a special case to let > > acquireWriteLock function to give up all read-locks when it is given a > > "-1" to its argument "giveupReadlockCount", like cindex.acquireWriteLock(-1); > > Please let me know if any of these two options would be reasonable to fix this > > problem? > Again, for the same reason this is not an option.
(In reply to comment #4) > ... > The scenario is Call hierarchy and reindex requests are called from two > different threads, but they both get a same index from StandaloneIndexer, then > the sequence described in comment 0 may happen depends on how fast of call > hierarchy searching. > .... That should be ok: As long as the call-hierarchy holds a read-lock, the indexer cannot proceed. The question is, what keeps the call-hierarchy from releasing its read-lock?
(In reply to comment #5) > (In reply to comment #4) > > ... > > The scenario is Call hierarchy and reindex requests are called from two > > different threads, but they both get a same index from StandaloneIndexer, then > > the sequence described in comment 0 may happen depends on how fast of call > > hierarchy searching. > > .... > That should be ok: As long as the call-hierarchy holds a read-lock, the indexer > cannot proceed. The question is, what keeps the call-hierarchy from releasing > its read-lock? That is the bug I am talking about in CIndex and WritableCIndex, the resaon why the CIndex is unable to release the read lock is because these lock releasing and acquiring functions are synchronized, so releaseReadLock() is waiting for acquireWriteLock() to be completed, but acquireWriteLock() is waiting for the readlock to be released. That is the place that deadlock occurs.
(In reply to comment #6) > That is the bug I am talking about in CIndex and WritableCIndex, the resaon > why > the CIndex is unable to release the read lock is because these lock releasing > and acquiring functions are synchronized, so releaseReadLock() is waiting for > acquireWriteLock() to be completed, but acquireWriteLock() is waiting for the > readlock to be released. That is the place that deadlock occurs. I finally got you. The WritableCIndex object does not work when used from multiple threads. Since no client other than the indexer should use a writable index, this is not a problem. The fix should make sure that the call-hierarchy operates on a (non-writable) CIndex. The CIndex class itself should be thread-safe. I think in CDT itself, every client obtains a private copy of a CIndex. So it is probably not tested whether the CIndex itself is really thread-safe.
(In reply to comment #7) > (In reply to comment #6) > > That is the bug I am talking about in CIndex and WritableCIndex, the resaon > > why > > the CIndex is unable to release the read lock is because these lock releasing > > and acquiring functions are synchronized, so releaseReadLock() is waiting for > > acquireWriteLock() to be completed, but acquireWriteLock() is waiting for the > > readlock to be released. That is the place that deadlock occurs. > I finally got you. The WritableCIndex object does not work when used from > multiple threads. Since no client other than the indexer should use a writable > index, this is not a problem. The fix should make sure that the call-hierarchy > operates on a (non-writable) CIndex. The CIndex class itself should be > thread-safe. I think in CDT itself, every client obtains a private copy of a > CIndex. So it is probably not tested whether the CIndex itself is really > thread-safe. I fixed this problem in RDT exactly as the way you described, like indexer uses a WritableCIndex to handle index updating and each client uses a private copy of a CIndex to do the query. But I still think there is something incorrect in the CIndex locking mechanism, I believe CIndex has the same deadlock problem if clients don't use a private copy of the index in separate threads. Let's see 2 clients use a same CIndex object and have the following function-call sequence, A deadlock will happen here as well. cindex.acquireReadLock(); //by client 1 cindex.acquireReadLock(); //by client 2 cindex.releaseReadLock(); //by client 1 cindex.releaseReadLock(); //by client 2 Sharing a CIndex instance may always be the first choice in a developer's intuition. So this problem is very easy to hit in an external index implementation by a developer who is not aware of this trick, and the thing is even worse that the deadlock happens intermittently and very hard to reproduce (depends on execution timing) and debug it (for me, I have to use a debug point to help to reproduce it). So it may be wroth to fixing it in CDT index class, at least there should be no deadlock happen in any scenario. I guess the problem is because CIndex has two layers of lock synchronization, the first layer is the CIndex synchronized locking functions and the 2nd layer is controlled by synchronizing an object "mutex" in PDOM. 1st layer: public synchronized void acquireReadLock(); public synchronized void releaseReadLock(); public synchronized void acquireWriteLock(int giveupReadlockCount); public synchronized void releaseWriteLock(int establishReadlockCount); public synchronized void releaseWriteLock(int establishReadlockCount, boolean flush); 2nd layer: synchronized (mutex) //in PDOM lock handling functions It maybe unnecessary to make the CIndex locking functions synchronized, removing the first layer synchronization in CIndex may be the way to fix. What do you think?
(In reply to comment #8) > (In reply to comment #7) > > (In reply to comment #6) > > > That is the bug I am talking about in CIndex and WritableCIndex, the resaon > > > why > > > the CIndex is unable to release the read lock is because these lock releasing > > > and acquiring functions are synchronized, so releaseReadLock() is waiting for > > > acquireWriteLock() to be completed, but acquireWriteLock() is waiting for the > > > readlock to be released. That is the place that deadlock occurs. > > I finally got you. The WritableCIndex object does not work when used from > > multiple threads. Since no client other than the indexer should use a writable > > index, this is not a problem. The fix should make sure that the call-hierarchy > > operates on a (non-writable) CIndex. The CIndex class itself should be > > thread-safe. I think in CDT itself, every client obtains a private copy of a > > CIndex. So it is probably not tested whether the CIndex itself is really > > thread-safe. > I fixed this problem in RDT exactly as the way you described, like indexer uses > a WritableCIndex to handle index updating and each client uses a private copy > of a CIndex to do the query. > But I still think there is something incorrect in the CIndex locking mechanism, > I believe CIndex has the same deadlock problem if clients don't use a private > copy of the index in separate threads. Let's see 2 clients use a same CIndex > object and have the following function-call sequence, A deadlock will happen > here as well. > cindex.acquireReadLock(); //by client 1 > cindex.acquireReadLock(); //by client 2 > cindex.releaseReadLock(); //by client 1 > cindex.releaseReadLock(); //by client 2 I don't think so, because when the index object holds a read-lock, neither acquireReadLock nor releaseReadLock can block. Multiple clients can simultaneously hold a read-lock. > Sharing a CIndex instance may always be the first choice in a developer's > intuition. So this problem is very easy to hit in an external index > implementation by a developer who is not aware of this trick, and the thing is > even worse that the deadlock happens intermittently and very hard to reproduce > (depends on execution timing) and debug it (for me, I have to use a debug point > to help to reproduce it). The writable index is internal, no one should be able to access it. If the stand-alone indexer exposes the writable index, then this should be changed. > So it may be wroth to fixing it in CDT index class, at least there should be > no deadlock happen in any scenario. I could add assertions that make sure that a writable index is not used from multiple threads. > I guess the problem is because CIndex has two layers of lock synchronization, > the first layer is the CIndex synchronized locking functions and the 2nd layer > is controlled by synchronizing an object "mutex" in PDOM. > 1st layer: > public synchronized void acquireReadLock(); > public synchronized void releaseReadLock(); > public synchronized void acquireWriteLock(int giveupReadlockCount); > public synchronized void releaseWriteLock(int establishReadlockCount); > public synchronized void releaseWriteLock(int establishReadlockCount, > boolean flush); > 2nd layer: > synchronized (mutex) //in PDOM lock handling functions > It maybe unnecessary to make the CIndex locking functions synchronized, > removing the first layer synchronization in CIndex may be the way to fix. What > do you think? When removing the synchronized from CIndex the class is no longer thread-safe (it protects the lock-counter). They are sort of useless for WritableCIndex.acquireWriteLock(..) because the class is not thread-safe anyways.
(In reply to comment #9) > (In reply to comment #8) > > (In reply to comment #7) > > > (In reply to comment #6) > > > > That is the bug I am talking about in CIndex and WritableCIndex, the resaon > > > > why > > > > the CIndex is unable to release the read lock is because these lock releasing > > > > and acquiring functions are synchronized, so releaseReadLock() is waiting for > > > > acquireWriteLock() to be completed, but acquireWriteLock() is waiting for the > > > > readlock to be released. That is the place that deadlock occurs. > > > I finally got you. The WritableCIndex object does not work when used from > > > multiple threads. Since no client other than the indexer should use a writable > > > index, this is not a problem. The fix should make sure that the call-hierarchy > > > operates on a (non-writable) CIndex. The CIndex class itself should be > > > thread-safe. I think in CDT itself, every client obtains a private copy of a > > > CIndex. So it is probably not tested whether the CIndex itself is really > > > thread-safe. > > I fixed this problem in RDT exactly as the way you described, like indexer uses > > a WritableCIndex to handle index updating and each client uses a private copy > > of a CIndex to do the query. > > But I still think there is something incorrect in the CIndex locking mechanism, > > I believe CIndex has the same deadlock problem if clients don't use a private > > copy of the index in separate threads. Let's see 2 clients use a same CIndex > > object and have the following function-call sequence, A deadlock will happen > > here as well. > > cindex.acquireReadLock(); //by client 1 > > cindex.acquireReadLock(); //by client 2 > > cindex.releaseReadLock(); //by client 1 > > cindex.releaseReadLock(); //by client 2 > I don't think so, because when the index object holds a read-lock, neither > acquireReadLock nor releaseReadLock can block. Multiple clients can > simultaneously hold a read-lock. Ah I see, PDOM can grant multiple read locks simultaneously, so the client 2 can get another readlock too while client holds a read lock. > > Sharing a CIndex instance may always be the first choice in a developer's > > intuition. So this problem is very easy to hit in an external index > > implementation by a developer who is not aware of this trick, and the thing is > > even worse that the deadlock happens intermittently and very hard to reproduce > > (depends on execution timing) and debug it (for me, I have to use a debug point > > to help to reproduce it). > The writable index is internal, no one should be able to access it. If the > stand-alone indexer exposes the writable index, then this should be changed. stand-alone indexer uses IWritableIndex from the internal package, is there a public interface for a writable index? > > So it may be wroth to fixing it in CDT index class, at least there should be > no deadlock happen in any scenario. > I could add assertions that make sure that a writable index is not used from > multiple threads. That would be very helpful. Thanks. > > I guess the problem is because CIndex has two layers of lock synchronization, > > the first layer is the CIndex synchronized locking functions and the 2nd layer > > is controlled by synchronizing an object "mutex" in PDOM. > > 1st layer: > > public synchronized void acquireReadLock(); > > public synchronized void releaseReadLock(); > > public synchronized void acquireWriteLock(int giveupReadlockCount); > > public synchronized void releaseWriteLock(int establishReadlockCount); > > public synchronized void releaseWriteLock(int establishReadlockCount, > > boolean flush); > > 2nd layer: > > synchronized (mutex) //in PDOM lock handling functions > > It maybe unnecessary to make the CIndex locking functions synchronized, > > removing the first layer synchronization in CIndex may be the way to fix. What > > do you think? > When removing the synchronized from CIndex the class is no longer thread-safe > (it protects the lock-counter). They are sort of useless for > WritableCIndex.acquireWriteLock(..) because the class is not thread-safe > anyways. Since CIndex doesn't have this problem, it is fine keeping "sychronized" keywaord. There is no problem in CIndex at all. For writableCIndex, maybe we can ignore the giveupReadlockCount and always grant a lock to write operation to make it thread safe. Or we can remove read lock acquiring and releasing functions from writableCIndex, so separate the read and write operations to different index classes, like CIndex handles read only and writable index handles write only.
(In reply to comment #10) > For writableCIndex, maybe we > can ignore the giveupReadlockCount and always grant a lock to write operation > to make it thread safe. Allowing a write lock while someone holds a read-lock is not an option. > Or we can remove read lock acquiring and releasing > functions from writableCIndex, so separate the read and write operations to > different index classes, like CIndex handles read only and writable index > handles write only. The indexer uses the combination of read and write locks. That has the advantage that the PDOM can hold some of the caches accross multiple files during indexing. I am not saying that there is no other solution. However, I don't see the need for changing the current implementation. I'll add checks about accessing the writable index from different threads and add some documentation.
*** cdt cvs genie on behalf of mschorn *** Bug 330838: Protect writable index against usage in multiple threads. [*] WritableCIndex.java 1.23 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/index/WritableCIndex.java?root=Tools_Project&r1=1.22&r2=1.23 [*] IWritableIndex.java 1.20 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/index/IWritableIndex.java?root=Tools_Project&r1=1.19&r2=1.20
