Lazy init in PSI classes and multi-threaded access

Hi,

I'm uncertain about PSI caching rules and would love some help here.

A user reported a dead-lock at https://github.com/jansorg/BashSupport/issues/467 .

Basically this is the UI thread waiting for a write action which waits for read actions to finish. The two active read actions dead-lock one another. The lock is caused by a synchronized block in an instance of a PSI class. The block guards lazy-initialized data. One read action is updating stub data and waits for the custom monitor and the other action has acquired the monitor and waits for the stub index.

Two threads access the PSI concurrently (wrapped in read actions): 1) is running the general highlighting and 2) is running a local inspection.

My lazy-init synchronized code is at https://github.com/jansorg/BashSupport/blob/idea-162.x/src/com/ansorgit/plugins/bash/lang/psi/impl/vars/BashVarDefImpl.java#L104 .

I know about subtreeChanged() and the general rules at http://www.jetbrains.org/intellij/sdk/docs/basics/architectural_overview/general_threading_rules.html .

What is the recommended way to do lazy-init in PSI classes? 
IntelliJ seems to do this without synchronization. This is not thread-safe and PSI seems to be used concurrently. Are the two examples below correct?


For example https://github.com/JetBrains/intellij-community/blob/9a0a04451e2332ff6a94f17a441c2a4f41ae83b5/python/src/com/jetbrains/python/psi/impl/PyAssignmentStatementImpl.java or https://github.com/JetBrains/intellij-community/blob/accf7523f985547336ed2c0f068c0132f6dcf786/plugins/groovy/groovy-psi/src/org/jetbrains/plugins/groovy/lang/psi/impl/auxiliary/GrListOrMapImpl.java .

 

Thanks a lot!

Joachim

5 comments
Official comment

Calling custom code inside a "synchronized" section can indeed lead to a deadlock, if that code inside can require other locks. I know of only one way of preventing that: don't. You can do the entire calculation outside of the "synchronized", and only assign the fields inside of it (if still needed). If only one field needs to be assigned, and the cached value identity doesn't matter (e.g. several threads can observe different array instances with the same content without any adverse semantic effects), then volatile field can be used instead of "synchronized". That way multiple threads might do the same job, but it's better than the deadlock. That's how most of our caches inside PSI are working, be it caching fields or CachedValue-s.

I'd also avoid synchronizing on PsiClass instance, because it's visible to outside world, and someone else might want to synchronize on it as well, leading to another deadlock. The usual practice is to use some private field for synchronization, maybe even create one solely for this purpose.

GrListOrMapImpl fields look correct (because they're volatile), but PyAssignmentStatementImpl doesn't, thanks for noticing!

Thanks, Peter!

Updating just the references in a synchronized block is a good idea, I didn't think of that.

I ended up to mark all fields which are part of the internal state of a PSI element as volatile. If there's more than one field it has to be updated in a synchronized block to avoid a corrupted state (multiple volatile fields updated concurrently might end up in an invalid combination in a worst-case scenario). I'm using volatile to avoid the synchronize on read access.

I didn't spot the volatile flag in the first sample, sorry.

For later readers, this is what I'm using now:

private final Object stateLock = new Object();
private volatile X x; //volatile to avoid synchronize on read-access

public X getX() {
if (x == null) {
X newX = ... //compute new value;

synchronized (stateLock) {
//you could check for x==null here if you prefer
x = newX;
}
}

return x;
}

public void subtreeChanged() {
synchronized (stateLock) {
x = null;
//reset all fields which are part of the internal state
}
}

 

0

Unless you really check for x==null inside the first "synchronized", I'd just drop it as it seems to add no value.

BTW if you modify several fields together (in a "synchronized"), then reading them should probably be also done in a "synchronized", otherwise other threads might still observe partially updated state.

0

Thanks for the reply! The first synchronize could be removed here, right.

I thought a bit more about this and wrote it down at https://www.plugin-dev.com/intellij/custom-language/psi-element-caching/ .

I'm not totally sure about partially updated state. I (currently) think that there shouldn't be a partially updated state under the assumption that reading data doesn't overlap with a call to subtreeChanged(). Parallel reads in different threads are all based on the same PSI (with no parallel write action). (If subtreeChanged() was called at any time then everything in a method had to be in a single synchronized block, I think.)

After some analysis my assumptions are that

- subtreeChanged() is always called in a write action

- methods which update the PSI element's cache are wrapped in a read or write action, i.e. parallel reads or one writer at a time

- accessing a PsiElement's or ASTNode's properties doesn't involve further locking

Further questions if you have the time for that:

- Would you recommend to always do access to PSI / ASTNode properties outside of a synchronized block or is it usually safe to do so if no stub index, etc. is used?

- Is it safe in general to access a StubIndex in a PsiElement (this, of course, outside of a synchronized block)? I couldn't find out.

Thanks a lot!

0

Your assumptions are correct for physical PSI. There can also be non-physical PSI not corresponding to any file in project (e.g. created on the fly from text). It can be modified in any thread, and clients take full responsibility for synchronizing it themselves.

Yes, I'd recommend to call any nontrivial code outside of "synchronized", unless you really want that computation to be run on not more than one thread. In that case, you should be very careful about potential deadlock. But luckily, this need seems to be extremely rare.

Accessing StubIndex from PsiElement should be safe (unless you do it during a write operation on that PSI, which could lead to inconsistencies). But most of the PSI doesn't do that: it's mostly concerned with local stuff, i.e. the surrounding AST nodes. Index is usually needed for a higher-level functionality, like completion, goto popups etc. But also for reference.resolve(), which you might consider part of PSI (or might not).

0

Please sign in to leave a comment.