As of change 40595, Path#get(String) may deadlock. To lift a quote from http://post-office.corp.redhat.com/archives/ccm-engineering-list/2004-February/msg00068.html The problem is that Path#get(String) is recursive. +------------------------------------------------------------------------+ | Thread A | Thread B | |----------------------------------+-------------------------------------| | Call Path.get("foo.bar") for the | | | first time. Suppose "foo.bar" | preempted | | hashes to 0, so we grab Lock #0. | | |----------------------------------+-------------------------------------| | | Call Path.get("grob.frobnicator") | | preempted | for the first time. Suppose | | | "grob.frobnicator" hashes to 1, so | | | we grab Lock #1. | |----------------------------------+-------------------------------------| | Since "foo.bar" has not been | | | interned yet, we call | | | Path.get("foo") to get the | | | parent path. Suppose the "foo" | | | path has not been interned yet, | preempted | | either. Suppose further that | | | "foo" hashes to 1. So, this | | | thread blocks waiting for Thread | | | B to release Lock #1. | | |----------------------------------+-------------------------------------| | | Since "grob.frobnicator" has not | | | been interned yet, we call | | | Path.get("grob") to compute the | | | parent first. Suppose the "grob" | | | path has not been interned yet. | | blocked | Suppose further that "grob" hashes | | | to 0, so this thread needs to | | | obtain Lock #0 in order to proceed. | | | | | | The thread blocks waiting for | | | Thread A to release Lock #0. | |------------------------------------------------------------------------| | deadlock | +------------------------------------------------------------------------+ I have a patch for this that I will post in a minute. I want someone to take a look at it, before the patch is applied.
Created attachment 97952 [details] hopefully eliminates the possibility of deadlocking The fundamental reason why the current implementation of Path#get(String) may deadlock is because this method may needs to obtain two or more locks in order to succeed. This is because (b) This method may recurse. (c) Different invocations of this method may require different locks. So, if an invocation of Path#get(String) requires locks #1 and #2 when performed from thread A, while a concurrent invocation from thread B requires locks #2 and #1 (in that order), the method may deadlock. The attached patch makes Path#get(String) non-recursive. This is essentially achieved by deferring the initialization of the m_parent field until it is really needed. The only place where m_parent is needed in the new implementation is in Path#getParent(). Note that the new implementation of Path#getParent() may require up to two locks in order to succeed. So, why doesn't this lead to the same problems as Path#get(String)? Here are the differences between locking strategies of the old implementation of Path#get(String) and the proposed new implementation of Path#getParent(). 1. Path#get(String) may require two or more locks. These locks come from the pre-allocated pool of 64 objects. It is possible that one thread may require locks #1 and #2, while the other requires number #2 and #1, in that order. In other words, there is no ordering among locks. 2. Path#getParent() draws its locks from two distinct pools. The first pool is the set of all Path objects (which typically measures in the thousands). The getParent() method synchronizes on the "this" object. The second pool is the same as above -- it's the array of 64 pre-allocated maps. The getParent() method always synchronizes on the Path object, before optionally synchronizing on one of the 64 maps. This imposes an ordering on the entire set of locks. The first pool always comes before the second. It is impossible for one thread to require locks P and M, while for another thread to require locks M and P, in that order. We always synchronize on a Path object, before potentially synchronizing on the Map object. I think this eliminates the possibility of deadlocking.
That looks fine to me. And, it still significantly reduces lock contention.
Thanks. Applied on the trunk in change 40731.