Bug 116593 - Path#get(String) may deadlock as of //core-platform/dev/src/com/redhat/persistence/common/Path.java#6
Path#get(String) may deadlock as of //core-platform/dev/src/com/redhat/persis...
Status: CLOSED CURRENTRELEASE
Product: Red Hat Web Application Framework
Classification: Retired
Component: persistence (Show other bugs)
nightly
All Linux
medium Severity medium
: ---
: ---
Assigned To: Vadim Nasardinov
Jon Orris
http://post-office.corp.redhat.com/ar...
:
Depends On:
Blocks:
  Show dependency treegraph
 
Reported: 2004-02-23 11:24 EST by Vadim Nasardinov
Modified: 2007-04-18 13:03 EDT (History)
0 users

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2004-02-23 17:20:46 EST
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---


Attachments (Terms of Use)
hopefully eliminates the possibility of deadlocking (3.62 KB, patch)
2004-02-23 11:49 EST, Vadim Nasardinov
no flags Details | Diff

  None (edit)
Description Vadim Nasardinov 2004-02-23 11:24:31 EST
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 11:49:56 EST
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 16:00:47 EST
That looks fine to me.  And, it still significantly reduces lock
contention.
Comment 3 Vadim Nasardinov 2004-02-23 16:39:57 EST
Thanks.

Applied on the trunk in change 40731.

Note You need to log in before you can comment on or make changes to this bug.