Bug 116593

Summary: Path#get(String) may deadlock as of //core-platform/dev/src/com/redhat/persistence/common/Path.java#6
Product: [Retired] Red Hat Web Application Framework Reporter: Vadim Nasardinov <vnasardinov>
Component: persistenceAssignee: Vadim Nasardinov <vnasardinov>
Status: CLOSED CURRENTRELEASE QA Contact: Jon Orris <jorris>
Severity: medium Docs Contact:
Priority: medium    
Version: nightly   
Target Milestone: ---   
Target Release: ---   
Hardware: All   
OS: Linux   
URL: http://post-office.corp.redhat.com/archives/ccm-engineering-list/2004-February/msg00068.html
Whiteboard:
Fixed In Version: Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2004-02-23 22:20:46 UTC Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: --- Target Upstream Version:
Embargoed:
Attachments:
Description Flags
hopefully eliminates the possibility of deadlocking none

Description Vadim Nasardinov 2004-02-23 16:24:31 UTC 
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.
Comment 1 Vadim Nasardinov 2004-02-23 16:49:56 UTC 
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.
Comment 2 Bryan Che 2004-02-23 21:00:47 UTC 
That looks fine to me.  And, it still significantly reduces lock
contention.
Comment 3 Vadim Nasardinov 2004-02-23 21:39:57 UTC 
Thanks.

Applied on the trunk in change 40731.