Coverage Report

Coverage Report - org.apache.commons.transaction.locking.GenericLock

Classes in this File

Line Coverage

Branch Coverage

Complexity

GenericLock

83%

137/164

72%

81/112

3.152

GenericLock$LockOwner

92%

12/13

75%

3/4

3.152

 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.apache.commons.transaction.locking;
 
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 import org.apache.commons.transaction.util.LoggerFacade;
 
 /**
  * A generic implementain of a simple multi level lock.
  * 
  * <p>
  * The idea is to have an ascending number of lock levels ranging from
  * <code>0</code> to <code>maxLockLevel</code> as specified in
  * {@link #GenericLock(Object, int, LoggerFacade)}: the higher the lock level
  * the stronger and more restrictive the lock. To determine which lock may
  * coexist with other locks you have to imagine matching pairs of lock levels.
  * For each pair both parts allow for all lock levels less than or equal to the
  * matching other part. Pairs are composed by the lowest and highest level not
  * yet part of a pair and successively applying this method until no lock level
  * is left. For an even amount of levels each level is part of exactly one pair.
  * For an odd amount the middle level is paired with itself. The highst lock
  * level may coexist with the lowest one (<code>0</code>) which by
  * definition means <code>NO LOCK</code>. This implies that you will have to
  * specify at least one other lock level and thus set <code>maxLockLevel</code>
  * to at least <code>1</code>.
  * </p>
  * 
  * <p>
  * Although this may sound complicated, in practice this is quite simple. Let us
  * imagine you have three lock levels:
  * <ul>
  * <li><code>0</code>:<code>NO LOCK</code> (always needed by the
  * implementation of this lock)
  * <li><code>1</code>:<code>SHARED</code>
  * <li><code>2</code>:<code>EXCLUSIVE</code>
  * </ul>
  * Accordingly, you will have to set <code>maxLockLevel</code> to
  * <code>2</code>. Now, there are two pairs of levels
  * <ul>
  * <li><code>NO LOCK</code> with <code>EXCLUSIVE</code>
  * <li><code>SHARED</code> with <code>SHARED</code>
  * </ul>
  * This means when the current highest lock level is <code>NO LOCK</code>
  * everything less or equal to <code>EXCLUSIVE</code> is allowed - which means
  * every other lock level. On the other side <code>EXCLUSIVE</code> allows
  * exacly for <code>NO LOCK</code>- which means nothing else. In conclusion,
  * <code>SHARED</code> allows for <code>SHARED</code> or <code>NO
  * LOCK</code>,
  * but not for <code>EXCLUSIVE</code>. To make this very clear have a look at
  * this table, where <code>o</code> means compatible or can coexist and
  * <code>x</code> means incompatible or can not coexist:
  * </p>
  * <table><tbody>
  * <tr>
  * <td align="center"></td>
  * <td align="center">NO LOCK</td>
  * <td align="center">SHARED</td>
  * <td align="center">EXCLUSIVE</td>
  * </tr>
  * <tr>
  * <td align="center">NO LOCK</td>
  * <td align="center">o</td>
  * <td align="center">o</td>
  * <td align="center">o</td>
  * </tr>
  * <tr>
  * <td align="center">SHARED</td>
  * <td align="center">o</td>
  * <td align="center">o</td>
  * <td align="center">x</td>
  * </tr>
  * <tr>
  * <td align="center">EXCLUSIVE</td>
  * <td align="center" align="center">o</td>
  * <td align="center">x</td>
  * <td align="center">x</td>
  * </tr>
  * </tbody> </table>
  * 
  * </p>
  * <p>
  * Additionally, there are preferences for specific locks you can pass to
  * {@link #acquire(Object, int, boolean, int, boolean, long)}. 
  * This means whenever more thanone party
  * waits for a lock you can specify which one is to be preferred. This gives you
  * every freedom you might need to specifcy e.g. 
  * <ul>
  * <li>priority to parties either applying for higher or lower lock levels
  * <li>priority not only to higher or lower locks, but to a specific level
  * <li>completely random preferences
  * </ul>
  * </p>
  * 
  * @version $Id: GenericLock.java 493628 2007-01-07 01:42:48Z joerg $
  */
 public class GenericLock implements MultiLevelLock2 {
 
     protected Object resourceId;
     // XXX needs to be synchronized to allow for unsynchronized access for deadlock detection
     // in getConflictingOwners to avoid deadlocks between lock to acquire and lock to check for
     // deadlocks
     protected Map owners = Collections.synchronizedMap(new HashMap());
     // XXX needs to be synchronized to allow for unsynchronized access for deadlock detection
     // in getConflictingWaiters to avoid deadlocks between lock to acquire and lock to check for
     // deadlocks
     // Note: having this as a list allows for fair mechanisms in sub classes
     protected List waitingOwners = Collections.synchronizedList(new ArrayList());
     private int maxLockLevel;
     protected LoggerFacade logger;
     protected int waiters = 0;
     
     /**
      * Creates a new lock.
      * 
      * @param resourceId identifier for the resource associated to this lock
      * @param maxLockLevel highest allowed lock level as described in class intro 
      * @param logger generic logger used for all kind of debug logging
      */
     public GenericLock(Object resourceId, int maxLockLevel, LoggerFacade logger) {
         if (maxLockLevel < 1)
             throw new IllegalArgumentException(
                 "The maximum lock level must be at least 1 (" + maxLockLevel + " was specified)");
         this.resourceId = resourceId;
         this.maxLockLevel = maxLockLevel;
         this.logger = logger;
     }
 
     public boolean equals(Object o) {
         if (o instanceof GenericLock) {
             return ((GenericLock)o).resourceId.equals(resourceId);
         }
         return false;
     }
 
     public int hashCode() {
         return resourceId.hashCode();
     }
 
     /**
      * @see MultiLevelLock2#test(Object, int, int)
      */
     public boolean test(Object ownerId, int targetLockLevel, int compatibility) {
         boolean success = tryLock(ownerId, targetLockLevel, compatibility, false, true);
         return success;
     }
     
     /**
      * @see MultiLevelLock2#has(Object, int)
      */
     public boolean has(Object ownerId, int lockLevel) {
         int level = getLockLevel(ownerId);
         return (lockLevel <= level);
     }
     
     /**
      * @see org.apache.commons.transaction.locking.MultiLevelLock#acquire(java.lang.Object,
      *      int, boolean, boolean, long)
      */
     public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
             boolean reentrant, long timeoutMSecs) throws InterruptedException {
         return acquire(ownerId, targetLockLevel, wait, reentrant ? COMPATIBILITY_REENTRANT
                 : COMPATIBILITY_NONE, timeoutMSecs);
     }
 
     /**
      * @see #acquire(Object, int, boolean, int, boolean, long)
      */
     public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
             int compatibility, long timeoutMSecs) throws InterruptedException {
         return acquire(ownerId, targetLockLevel, wait, compatibility, false, timeoutMSecs);
     }
     
     /**
      * Tries to blockingly acquire a lock which can be preferred.
      * 
      * @see #acquire(Object, int, boolean, int, boolean, long) 
      * @since 1.1 
      */
     public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean preferred,
             long timeoutMSecs) throws InterruptedException {
         return acquire(ownerId, targetLockLevel, true, COMPATIBILITY_REENTRANT, preferred,
                 timeoutMSecs);
     }
     
     /**
      * @see org.apache.commons.transaction.locking.MultiLevelLock2#acquire(Object,
      *      int, boolean, int, boolean, long)
      * @since 1.1 
      */
     public synchronized boolean acquire(
         Object ownerId,
         int targetLockLevel,
         boolean wait,
         int compatibility,
         boolean preferred,
         long timeoutMSecs)
         throws InterruptedException {
 
         if (logger.isFinerEnabled()) {
                 logger.logFiner(
                     ownerId.toString()
                         + " trying to acquire lock for "
                         + resourceId.toString()
                         + " at level "
                         + targetLockLevel
                         + " at "
                         + System.currentTimeMillis());
         }
 
         if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
             
             if (logger.isFinerEnabled()) {
                     logger.logFiner(
                         ownerId.toString()
                             + " actually acquired lock for "
                             + resourceId.toString()
                             + " at "
                             + System.currentTimeMillis());
             }
 
             return true;
         } else {
             if (!wait) {
                 return false;
             } else {
                 long started = System.currentTimeMillis();
                 for (long remaining = timeoutMSecs;
                     remaining > 0;
                     remaining = timeoutMSecs - (System.currentTimeMillis() - started)) {
 
                     if (logger.isFinerEnabled()) {
                             logger.logFiner(
                                 ownerId.toString()
                                     + " waiting on "
                                     + resourceId.toString()
                                     + " for msecs "
                                     + timeoutMSecs
                                     + " at "
                                     + System.currentTimeMillis());
                     }
 
                     LockOwner waitingOwner = new LockOwner(ownerId, targetLockLevel, compatibility,
                             preferred);
                     try {
                         registerWaiter(waitingOwner);
                         if (preferred) {
                             // while waiting we already make our claim we are next
                             LockOwner oldLock = null;
                             try {
                                 // we need to remember it to restore it after waiting
                                 oldLock = (LockOwner) owners.get(ownerId);
                                 // this creates a new owner, so we do not need to
                                 // copy the old one
                                 setLockLevel(ownerId, null, targetLockLevel, compatibility,
                                         preferred);
     
                                 // finally wait
                                 wait(remaining);
                                 
                             } finally {
                                 // we need to restore the old lock in order not to
                                 // interfere with the intention lock in the
                                 // following check
                                 // and not to have it in case of success either
                                 // as there will be an ordinary lock then
                                 if (oldLock != null) {
                                     owners.put(ownerId, oldLock);
                                 } else {
                                     owners.remove(ownerId);
                                 }
                             }
     
                         } else {
                             wait(remaining);
                         }
                     } finally {
                         unregisterWaiter(waitingOwner);
                     }
                     
                     if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
 
                         if (logger.isFinerEnabled()) {
                                 logger.logFiner(
                                     ownerId.toString()
                                         + " waiting on "
                                         + resourceId.toString()
                                         + " eventually got the lock at "
                                         + System.currentTimeMillis());
                         }
 
                         return true;
                     }
                 }
                 return false;
             }
         }
     }
 
     protected void registerWaiter(LockOwner waitingOwner) {
         synchronized (waitingOwners) {
             unregisterWaiter(waitingOwner);
             waiters++;
             waitingOwners.add(waitingOwner);
         }
     }
 
     protected void unregisterWaiter(LockOwner waitingOwner) {
         synchronized (waitingOwners) {
             if (waitingOwners.remove(waitingOwner))
                 waiters--;
         }
     }
     
     /**
      * @see org.apache.commons.transaction.locking.MultiLevelLock#release(Object)
      */
     public synchronized boolean release(Object ownerId) {
         if (owners.remove(ownerId) != null) {
             if (logger.isFinerEnabled()) {
                     logger.logFiner(
                         ownerId.toString()
                             + " releasing lock for "
                             + resourceId.toString()
                             + " at "
                             + System.currentTimeMillis());
             }
             notifyAll();
             return true;
         }
         return false;
     }
 
     /**
      * @see org.apache.commons.transaction.locking.MultiLevelLock#getLockLevel(Object)
      */
     public int getLockLevel(Object ownerId) {
         LockOwner owner = (LockOwner) owners.get(ownerId);
         if (owner == null) {
             return 0;
         } else {
             return owner.lockLevel;
         }
     }
 
     /**
      * Gets the resource assotiated to this lock. 
      * 
      * @return identifier for the resource associated to this lock 
      */
     public Object getResourceId() {
         return resourceId;
     }
 
     /**
      * Gets the lowest lock level possible.
      * 
      * @return minimum lock level
      */
     public int getLevelMinLock() {
         return 0;
     }
 
     /**
      * Gets the highst lock level possible.
      * 
      * @return maximum lock level
      */
     public int getLevelMaxLock() {
         return maxLockLevel;
     }
 
     public Object getOwner() {
         LockOwner owner = getMaxLevelOwner();
         if (owner == null)
             return null;
         return owner.ownerId;
     }
 
     public synchronized String toString() {
         StringBuffer buf = new StringBuffer();
         buf.append(resourceId.toString()).append(":\n");
 
         for (Iterator it = owners.values().iterator(); it.hasNext();) {
             LockOwner owner = (LockOwner) it.next();
             buf.append("- ").append(owner.toString()).append("\n");
         }
 
         if (waiters != 0) {
             buf.append(waiters).append(" waiting:\n");
             for (Iterator it = waitingOwners.iterator(); it.hasNext();) {
                 LockOwner owner = (LockOwner) it.next();
                 buf.append("- ").append(owner.toString()).append("\n");
             }
         }
         
         return buf.toString();
     }
 
     protected synchronized LockOwner getMaxLevelOwner() {
         return getMaxLevelOwner(null, -1, false);
     }
 
     protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner, boolean preferred) {
         return getMaxLevelOwner(reentrantOwner, -1, preferred);
     }
 
     protected synchronized LockOwner getMaxLevelOwner(int supportLockLevel, boolean preferred) {
         return getMaxLevelOwner(null, supportLockLevel, preferred);
     }
 
     protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner,
             int supportLockLevel, boolean preferred) {
         LockOwner maxOwner = null;
         for (Iterator it = owners.values().iterator(); it.hasNext();) {
             LockOwner owner = (LockOwner) it.next();
             if (owner.lockLevel != supportLockLevel && !owner.equals(reentrantOwner)
                     && (maxOwner == null || maxOwner.lockLevel < owner.lockLevel)
                     // if we are a preferred lock we must not interfere with other intention
                     // locks as we otherwise might mututally lock without resolvation
                     && !(preferred && owner.intention)) {
                 maxOwner = owner;
             }
         }
         return maxOwner;
     }
     
     protected synchronized void setLockLevel(Object ownerId, LockOwner lock, int targetLockLevel,
             int compatibility, boolean intention) {
         // be sure there exists at most one lock per owner
         if (lock != null) {
             if (logger.isFinestEnabled()) {
                     logger.logFinest(
                         ownerId.toString()
                             + " upgrading lock for "
                             + resourceId.toString()
                             + " to level "
                             + targetLockLevel
                             + " at "
                             + System.currentTimeMillis());
             }
         } else {
             if (logger.isFinestEnabled()) {
                     logger.logFinest(
                         ownerId.toString()
                             + " getting new lock for "
                             + resourceId.toString()
                             + " at level "
                             + targetLockLevel
                             + " at "
                             + System.currentTimeMillis());
             }
         }
         owners.put(ownerId, new LockOwner(ownerId, targetLockLevel, compatibility, intention));
     }
 
     protected boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
             boolean preferred) {
         return tryLock(ownerId, targetLockLevel, compatibility, preferred, false);
     }
 
     protected synchronized boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
             boolean preferred, boolean tryOnly) {
 
         LockOwner myLock = (LockOwner) owners.get(ownerId);
 
         // determine highest owner        
         LockOwner highestOwner;
         if (compatibility == COMPATIBILITY_REENTRANT) {
             if (myLock != null && targetLockLevel <= myLock.lockLevel) {
                 // we already have it
                 return true;
             } else {
                 // our own lock will not be compromised by ourself
                 highestOwner = getMaxLevelOwner(myLock, preferred);
             }
         } else if (compatibility == COMPATIBILITY_SUPPORT) {
             // we are compatible with any other lock owner holding
             // the same lock level
             highestOwner = getMaxLevelOwner(targetLockLevel, preferred);
 
         } else if (compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT) {
             if (myLock != null && targetLockLevel <= myLock.lockLevel) {
                 // we already have it
                 return true;
             } else {
                 // our own lock will not be compromised by ourself and same lock level 
                 highestOwner = getMaxLevelOwner(myLock, targetLockLevel, preferred);
             }
         } else {
             highestOwner = getMaxLevelOwner();
         }
 
         int i;
         // what is our current lock level?
         int currentLockLevel;
         if (highestOwner != null) {
             currentLockLevel = highestOwner.lockLevel;
         } else {
             currentLockLevel = getLevelMinLock();
         }
 
         // we are only allowed to acquire our locks if we do not compromise locks of any other lock owner
         if (isCompatible(targetLockLevel, currentLockLevel)) {
             if (!tryOnly) {
                 // if we really have the lock, it no longer is an intention
                 setLockLevel(ownerId, myLock, targetLockLevel, compatibility, false);
             }
             return true;
         } else {
             return false;
         }
     }
 
     protected boolean isCompatible(int targetLockLevel, int currentLockLevel) {
         return (targetLockLevel <= getLevelMaxLock() - currentLockLevel);
     }
     
     protected Set getConflictingOwners(Object ownerId, int targetLockLevel, int compatibility) {
 
         LockOwner myLock = (LockOwner) owners.get(ownerId);
         if (myLock != null && targetLockLevel <= myLock.lockLevel) {
             // shortcut as we already have the lock
             return null;
         }
         
         LockOwner testLock = new LockOwner(ownerId, targetLockLevel, compatibility, false);
         List ownersCopy;
         synchronized (owners) {
             ownersCopy = new ArrayList(owners.values());
         }
         return getConflictingOwners(testLock, ownersCopy);
         
     }
 
     protected Collection getConflictingWaiters(Object ownerId) {
         LockOwner owner = (LockOwner) owners.get(ownerId);
         if (owner != null) {
             List waiterCopy;
             synchronized (waitingOwners) {
                 waiterCopy = new ArrayList(waitingOwners);
             }
             Collection conflicts = getConflictingOwners(owner, waiterCopy);
             return conflicts;
         }
         return null;
     }
     
     protected Set getConflictingOwners(LockOwner myOwner, Collection ownersToTest) {
 
         if (myOwner == null) return null;
         
         Set conflicts = new HashSet();
 
         // check if any locks conflict with ours
         for (Iterator it = ownersToTest.iterator(); it.hasNext();) {
             LockOwner owner = (LockOwner) it.next();
             
             // we do not interfere with ourselves, except when explicitely said so
             if ((myOwner.compatibility == COMPATIBILITY_REENTRANT || myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT)
                     && owner.ownerId.equals(myOwner.ownerId))
                 continue;
             
             // otherwise find out the lock level of the owner and see if we conflict with it
             int onwerLockLevel = owner.lockLevel;
            
             if (myOwner.compatibility == COMPATIBILITY_SUPPORT
                     || myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT
                     && myOwner.lockLevel == onwerLockLevel)
                 continue;
             
             if (!isCompatible(myOwner.lockLevel, onwerLockLevel)) {
                 conflicts.add(owner.ownerId);
             }
         }
         return (conflicts.isEmpty() ? null : conflicts);
     }
 
     protected static class LockOwner {
         public final Object ownerId;
         public final int lockLevel;
         public final boolean intention;
         public final int compatibility;
 
         public LockOwner(Object ownerId, int lockLevel, int compatibility, boolean intention) {
             this.ownerId = ownerId;
             this.lockLevel = lockLevel;
             this.intention = intention;
             this.compatibility = compatibility;
         }
 
         public String toString() {
             StringBuffer buf = new StringBuffer();
             buf.append(ownerId.toString()).append(": level ").append(lockLevel).append(", complevel ")
                     .append(compatibility).append(intention ? ", intention/preferred" : "");
             return buf.toString();
         }
         
         public boolean equals(Object o) {
             if (o instanceof LockOwner) {
                 return ((LockOwner)o).ownerId.equals(ownerId);
             }
             return false;
         }
         
         public int hashCode() {
             return ownerId.hashCode();
         }
     }
 
 }

1		/*
2		* Licensed to the Apache Software Foundation (ASF) under one or more
3		* contributor license agreements. See the NOTICE file distributed with
4		* this work for additional information regarding copyright ownership.
5		* The ASF licenses this file to You under the Apache License, Version 2.0
6		* (the "License"); you may not use this file except in compliance with
7		* the License. You may obtain a copy of the License at
8		*
9		* http://www.apache.org/licenses/LICENSE-2.0
10		*
11		* Unless required by applicable law or agreed to in writing, software
12		* distributed under the License is distributed on an "AS IS" BASIS,
13		* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14		* See the License for the specific language governing permissions and
15		* limitations under the License.
16		*/
17		package org.apache.commons.transaction.locking;
18
19		import java.util.ArrayList;
20		import java.util.Collection;
21		import java.util.Collections;
22		import java.util.HashMap;
23		import java.util.HashSet;
24		import java.util.Iterator;
25		import java.util.List;
26		import java.util.Map;
27		import java.util.Set;
28
29		import org.apache.commons.transaction.util.LoggerFacade;
30
31		/**
32		* A generic implementain of a simple multi level lock.
33		*
34		* <p>
35		* The idea is to have an ascending number of lock levels ranging from
36		* <code>0</code> to <code>maxLockLevel</code> as specified in
37		* {@link #GenericLock(Object, int, LoggerFacade)}: the higher the lock level
38		* the stronger and more restrictive the lock. To determine which lock may
39		* coexist with other locks you have to imagine matching pairs of lock levels.
40		* For each pair both parts allow for all lock levels less than or equal to the
41		* matching other part. Pairs are composed by the lowest and highest level not
42		* yet part of a pair and successively applying this method until no lock level
43		* is left. For an even amount of levels each level is part of exactly one pair.
44		* For an odd amount the middle level is paired with itself. The highst lock
45		* level may coexist with the lowest one (<code>0</code>) which by
46		* definition means <code>NO LOCK</code>. This implies that you will have to
47		* specify at least one other lock level and thus set <code>maxLockLevel</code>
48		* to at least <code>1</code>.
49		* </p>
50		*
51		* <p>
52		* Although this may sound complicated, in practice this is quite simple. Let us
53		* imagine you have three lock levels:
54		* <ul>
55		* <li><code>0</code>:<code>NO LOCK</code> (always needed by the
56		* implementation of this lock)
57		* <li><code>1</code>:<code>SHARED</code>
58		* <li><code>2</code>:<code>EXCLUSIVE</code>
59		* </ul>
60		* Accordingly, you will have to set <code>maxLockLevel</code> to
61		* <code>2</code>. Now, there are two pairs of levels
62		* <ul>
63		* <li><code>NO LOCK</code> with <code>EXCLUSIVE</code>
64		* <li><code>SHARED</code> with <code>SHARED</code>
65		* </ul>
66		* This means when the current highest lock level is <code>NO LOCK</code>
67		* everything less or equal to <code>EXCLUSIVE</code> is allowed - which means
68		* every other lock level. On the other side <code>EXCLUSIVE</code> allows
69		* exacly for <code>NO LOCK</code>- which means nothing else. In conclusion,
70		* <code>SHARED</code> allows for <code>SHARED</code> or <code>NO
71		* LOCK</code>,
72		* but not for <code>EXCLUSIVE</code>. To make this very clear have a look at
73		* this table, where <code>o</code> means compatible or can coexist and
74		* <code>x</code> means incompatible or can not coexist:
75		* </p>
76		* <table><tbody>
77		* <tr>
78		* <td align="center"></td>
79		* <td align="center">NO LOCK</td>
80		* <td align="center">SHARED</td>
81		* <td align="center">EXCLUSIVE</td>
82		* </tr>
83		* <tr>
84		* <td align="center">NO LOCK</td>
85		* <td align="center">o</td>
86		* <td align="center">o</td>
87		* <td align="center">o</td>
88		* </tr>
89		* <tr>
90		* <td align="center">SHARED</td>
91		* <td align="center">o</td>
92		* <td align="center">o</td>
93		* <td align="center">x</td>
94		* </tr>
95		* <tr>
96		* <td align="center">EXCLUSIVE</td>
97		* <td align="center" align="center">o</td>
98		* <td align="center">x</td>
99		* <td align="center">x</td>
100		* </tr>
101		* </tbody> </table>
102		*
103		* </p>
104		* <p>
105		* Additionally, there are preferences for specific locks you can pass to
106		* {@link #acquire(Object, int, boolean, int, boolean, long)}.
107		* This means whenever more thanone party
108		* waits for a lock you can specify which one is to be preferred. This gives you
109		* every freedom you might need to specifcy e.g.
110		* <ul>
111		* <li>priority to parties either applying for higher or lower lock levels
112		* <li>priority not only to higher or lower locks, but to a specific level
113		* <li>completely random preferences
114		* </ul>
115		* </p>
116		*
117		* @version $Id: GenericLock.java 493628 2007-01-07 01:42:48Z joerg $
118		*/
119		public class GenericLock implements MultiLevelLock2 {
120
121		protected Object resourceId;
122		// XXX needs to be synchronized to allow for unsynchronized access for deadlock detection
123		// in getConflictingOwners to avoid deadlocks between lock to acquire and lock to check for
124		// deadlocks
125	62	protected Map owners = Collections.synchronizedMap(new HashMap());
126		// XXX needs to be synchronized to allow for unsynchronized access for deadlock detection
127		// in getConflictingWaiters to avoid deadlocks between lock to acquire and lock to check for
128		// deadlocks
129		// Note: having this as a list allows for fair mechanisms in sub classes
130	62	protected List waitingOwners = Collections.synchronizedList(new ArrayList());
131		private int maxLockLevel;
132		protected LoggerFacade logger;
133	62	protected int waiters = 0;
134
135		/**
136		* Creates a new lock.
137		*
138		* @param resourceId identifier for the resource associated to this lock
139		* @param maxLockLevel highest allowed lock level as described in class intro
140		* @param logger generic logger used for all kind of debug logging
141		*/
142	62	public GenericLock(Object resourceId, int maxLockLevel, LoggerFacade logger) {
143	62	if (maxLockLevel < 1)
144	0	throw new IllegalArgumentException(
145		"The maximum lock level must be at least 1 (" + maxLockLevel + " was specified)");
146	62	this.resourceId = resourceId;
147	62	this.maxLockLevel = maxLockLevel;
148	62	this.logger = logger;
149	62	}
150
151		public boolean equals(Object o) {
152	0	if (o instanceof GenericLock) {
153	0	return ((GenericLock)o).resourceId.equals(resourceId);
154		}
155	0	return false;
156		}
157
158		public int hashCode() {
159	5312	return resourceId.hashCode();
160		}
161
162		/**
163		* @see MultiLevelLock2#test(Object, int, int)
164		*/
165		public boolean test(Object ownerId, int targetLockLevel, int compatibility) {
166	0	boolean success = tryLock(ownerId, targetLockLevel, compatibility, false, true);
167	0	return success;
168		}
169
170		/**
171		* @see MultiLevelLock2#has(Object, int)
172		*/
173		public boolean has(Object ownerId, int lockLevel) {
174	0	int level = getLockLevel(ownerId);
175	0	return (lockLevel <= level);
176		}
177
178		/**
179		* @see org.apache.commons.transaction.locking.MultiLevelLock#acquire(java.lang.Object,
180		* int, boolean, boolean, long)
181		*/
182		public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
183		boolean reentrant, long timeoutMSecs) throws InterruptedException {
184	31	return acquire(ownerId, targetLockLevel, wait, reentrant ? COMPATIBILITY_REENTRANT
185		: COMPATIBILITY_NONE, timeoutMSecs);
186		}
187
188		/**
189		* @see #acquire(Object, int, boolean, int, boolean, long)
190		*/
191		public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
192		int compatibility, long timeoutMSecs) throws InterruptedException {
193	34	return acquire(ownerId, targetLockLevel, wait, compatibility, false, timeoutMSecs);
194		}
195
196		/**
197		* Tries to blockingly acquire a lock which can be preferred.
198		*
199		* @see #acquire(Object, int, boolean, int, boolean, long)
200		* @since 1.1
201		*/
202		public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean preferred,
203		long timeoutMSecs) throws InterruptedException {
204	180	return acquire(ownerId, targetLockLevel, true, COMPATIBILITY_REENTRANT, preferred,
205		timeoutMSecs);
206		}
207
208		/**
209		* @see org.apache.commons.transaction.locking.MultiLevelLock2#acquire(Object,
210		* int, boolean, int, boolean, long)
211		* @since 1.1
212		*/
213		public synchronized boolean acquire(
214		Object ownerId,
215		int targetLockLevel,
216		boolean wait,
217		int compatibility,
218		boolean preferred,
219		long timeoutMSecs)
220		throws InterruptedException {
221
222	3653	if (logger.isFinerEnabled()) {
223	0	logger.logFiner(
224		ownerId.toString()
225		+ " trying to acquire lock for "
226		+ resourceId.toString()
227		+ " at level "
228		+ targetLockLevel
229		+ " at "
230		+ System.currentTimeMillis());
231		}
232
233	3653	if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
234
235	2475	if (logger.isFinerEnabled()) {
236	0	logger.logFiner(
237		ownerId.toString()
238		+ " actually acquired lock for "
239		+ resourceId.toString()
240		+ " at "
241		+ System.currentTimeMillis());
242		}
243
244	2475	return true;
245		} else {
246	1178	if (!wait) {
247	169	return false;
248		} else {
249	1009	long started = System.currentTimeMillis();
250	1009	for (long remaining = timeoutMSecs;
251	1467	remaining > 0;
252	458	remaining = timeoutMSecs - (System.currentTimeMillis() - started)) {
253
254	1194	if (logger.isFinerEnabled()) {
255	0	logger.logFiner(
256		ownerId.toString()
257		+ " waiting on "
258		+ resourceId.toString()
259		+ " for msecs "
260		+ timeoutMSecs
261		+ " at "
262		+ System.currentTimeMillis());
263		}
264
265	1194	LockOwner waitingOwner = new LockOwner(ownerId, targetLockLevel, compatibility,
266		preferred);
267		try {
268	1194	registerWaiter(waitingOwner);
269	1194	if (preferred) {
270		// while waiting we already make our claim we are next
271	585	LockOwner oldLock = null;
272		try {
273		// we need to remember it to restore it after waiting
274	585	oldLock = (LockOwner) owners.get(ownerId);
275		// this creates a new owner, so we do not need to
276		// copy the old one
277	585	setLockLevel(ownerId, null, targetLockLevel, compatibility,
278		preferred);
279
280		// finally wait
281	585	wait(remaining);
282
283		} finally {
284		// we need to restore the old lock in order not to
285		// interfere with the intention lock in the
286		// following check
287		// and not to have it in case of success either
288		// as there will be an ordinary lock then
289	585	if (oldLock != null) {
290	27	owners.put(ownerId, oldLock);
291		} else {
292	558	owners.remove(ownerId);
293		}
294	558	}
295
296	585	} else {
297	609	wait(remaining);
298		}
299		} finally {
300	1194	unregisterWaiter(waitingOwner);
301	1194	}
302
303	1194	if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
304
305	736	if (logger.isFinerEnabled()) {
306	0	logger.logFiner(
307		ownerId.toString()
308		+ " waiting on "
309		+ resourceId.toString()
310		+ " eventually got the lock at "
311		+ System.currentTimeMillis());
312		}
313
314	736	return true;
315		}
316		}
317	273	return false;
318		}
319		}
320		}
321
322		protected void registerWaiter(LockOwner waitingOwner) {
323	1859	synchronized (waitingOwners) {
324	1859	unregisterWaiter(waitingOwner);
325	1859	waiters++;
326	1859	waitingOwners.add(waitingOwner);
327	1859	}
328	1859	}
329
330		protected void unregisterWaiter(LockOwner waitingOwner) {
331	3461	synchronized (waitingOwners) {
332	3461	if (waitingOwners.remove(waitingOwner))
333	1859	waiters--;
334	3461	}
335	3461	}
336
337		/**
338		* @see org.apache.commons.transaction.locking.MultiLevelLock#release(Object)
339		*/
340		public synchronized boolean release(Object ownerId) {
341	2570	if (owners.remove(ownerId) != null) {
342	2543	if (logger.isFinerEnabled()) {
343	0	logger.logFiner(
344		ownerId.toString()
345		+ " releasing lock for "
346		+ resourceId.toString()
347		+ " at "
348		+ System.currentTimeMillis());
349		}
350	2543	notifyAll();
351	2543	return true;
352		}
353	27	return false;
354		}
355
356		/**
357		* @see org.apache.commons.transaction.locking.MultiLevelLock#getLockLevel(Object)
358		*/
359		public int getLockLevel(Object ownerId) {
360	324	LockOwner owner = (LockOwner) owners.get(ownerId);
361	324	if (owner == null) {
362	63	return 0;
363		} else {
364	261	return owner.lockLevel;
365		}
366		}
367
368		/**
369		* Gets the resource assotiated to this lock.
370		*
371		* @return identifier for the resource associated to this lock
372		*/
373		public Object getResourceId() {
374	0	return resourceId;
375		}
376
377		/**
378		* Gets the lowest lock level possible.
379		*
380		* @return minimum lock level
381		*/
382		public int getLevelMinLock() {
383	2206	return 0;
384		}
385
386		/**
387		* Gets the highst lock level possible.
388		*
389		* @return maximum lock level
390		*/
391		public int getLevelMaxLock() {
392	5207	return maxLockLevel;
393		}
394
395		public Object getOwner() {
396	0	LockOwner owner = getMaxLevelOwner();
397	0	if (owner == null)
398	0	return null;
399	0	return owner.ownerId;
400		}
401
402		public synchronized String toString() {
403	68	StringBuffer buf = new StringBuffer();
404	68	buf.append(resourceId.toString()).append(":\n");
405
406	68	for (Iterator it = owners.values().iterator(); it.hasNext();) {
407	68	LockOwner owner = (LockOwner) it.next();
408	68	buf.append("- ").append(owner.toString()).append("\n");
409	68	}
410
411	68	if (waiters != 0) {
412	4	buf.append(waiters).append(" waiting:\n");
413	4	for (Iterator it = waitingOwners.iterator(); it.hasNext();) {
414	4	LockOwner owner = (LockOwner) it.next();
415	4	buf.append("- ").append(owner.toString()).append("\n");
416	4	}
417		}
418
419	68	return buf.toString();
420		}
421
422		protected synchronized LockOwner getMaxLevelOwner() {
423	0	return getMaxLevelOwner(null, -1, false);
424		}
425
426		protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner, boolean preferred) {
427	4415	return getMaxLevelOwner(reentrantOwner, -1, preferred);
428		}
429
430		protected synchronized LockOwner getMaxLevelOwner(int supportLockLevel, boolean preferred) {
431	3	return getMaxLevelOwner(null, supportLockLevel, preferred);
432		}
433
434		protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner,
435		int supportLockLevel, boolean preferred) {
436	4418	LockOwner maxOwner = null;
437	4418	for (Iterator it = owners.values().iterator(); it.hasNext();) {
438	3006	LockOwner owner = (LockOwner) it.next();
439	3006	if (owner.lockLevel != supportLockLevel && !owner.equals(reentrantOwner)
440		&& (maxOwner == null \|\| maxOwner.lockLevel < owner.lockLevel)
441		// if we are a preferred lock we must not interfere with other intention
442		// locks as we otherwise might mututally lock without resolvation
443		&& !(preferred && owner.intention)) {
444	2236	maxOwner = owner;
445		}
446	3006	}
447	4418	return maxOwner;
448		}
449
450		protected synchronized void setLockLevel(Object ownerId, LockOwner lock, int targetLockLevel,
451		int compatibility, boolean intention) {
452		// be sure there exists at most one lock per owner
453	3367	if (lock != null) {
454	236	if (logger.isFinestEnabled()) {
455	0	logger.logFinest(
456		ownerId.toString()
457		+ " upgrading lock for "
458		+ resourceId.toString()
459		+ " to level "
460		+ targetLockLevel
461		+ " at "
462		+ System.currentTimeMillis());
463		}
464		} else {
465	3131	if (logger.isFinestEnabled()) {
466	0	logger.logFinest(
467		ownerId.toString()
468		+ " getting new lock for "
469		+ resourceId.toString()
470		+ " at level "
471		+ targetLockLevel
472		+ " at "
473		+ System.currentTimeMillis());
474		}
475		}
476	3367	owners.put(ownerId, new LockOwner(ownerId, targetLockLevel, compatibility, intention));
477	3367	}
478
479		protected boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
480		boolean preferred) {
481	4872	return tryLock(ownerId, targetLockLevel, compatibility, preferred, false);
482		}
483
484		protected synchronized boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
485		boolean preferred, boolean tryOnly) {
486
487	4872	LockOwner myLock = (LockOwner) owners.get(ownerId);
488
489		// determine highest owner
490		LockOwner highestOwner;
491	4872	if (compatibility == COMPATIBILITY_REENTRANT) {
492	4869	if (myLock != null && targetLockLevel <= myLock.lockLevel) {
493		// we already have it
494	454	return true;
495		} else {
496		// our own lock will not be compromised by ourself
497	4415	highestOwner = getMaxLevelOwner(myLock, preferred);
498		}
499	3	} else if (compatibility == COMPATIBILITY_SUPPORT) {
500		// we are compatible with any other lock owner holding
501		// the same lock level
502	3	highestOwner = getMaxLevelOwner(targetLockLevel, preferred);
503
504	0	} else if (compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT) {
505	0	if (myLock != null && targetLockLevel <= myLock.lockLevel) {
506		// we already have it
507	0	return true;
508		} else {
509		// our own lock will not be compromised by ourself and same lock level
510	0	highestOwner = getMaxLevelOwner(myLock, targetLockLevel, preferred);
511		}
512		} else {
513	0	highestOwner = getMaxLevelOwner();
514		}
515
516		int i;
517		// what is our current lock level?
518		int currentLockLevel;
519	4418	if (highestOwner != null) {
520	2212	currentLockLevel = highestOwner.lockLevel;
521		} else {
522	2206	currentLockLevel = getLevelMinLock();
523		}
524
525		// we are only allowed to acquire our locks if we do not compromise locks of any other lock owner
526	4418	if (isCompatible(targetLockLevel, currentLockLevel)) {
527	2782	if (!tryOnly) {
528		// if we really have the lock, it no longer is an intention
529	2782	setLockLevel(ownerId, myLock, targetLockLevel, compatibility, false);
530		}
531	2782	return true;
532		} else {
533	1636	return false;
534		}
535		}
536
537		protected boolean isCompatible(int targetLockLevel, int currentLockLevel) {
538	5207	return (targetLockLevel <= getLevelMaxLock() - currentLockLevel);
539		}
540
541		protected Set getConflictingOwners(Object ownerId, int targetLockLevel, int compatibility) {
542
543	257	LockOwner myLock = (LockOwner) owners.get(ownerId);
544	257	if (myLock != null && targetLockLevel <= myLock.lockLevel) {
545		// shortcut as we already have the lock
546	10	return null;
547		}
548
549	247	LockOwner testLock = new LockOwner(ownerId, targetLockLevel, compatibility, false);
550		List ownersCopy;
551	247	synchronized (owners) {
552	247	ownersCopy = new ArrayList(owners.values());
553	247	}
554	247	return getConflictingOwners(testLock, ownersCopy);
555
556		}
557
558		protected Collection getConflictingWaiters(Object ownerId) {
559	650	LockOwner owner = (LockOwner) owners.get(ownerId);
560	650	if (owner != null) {
561		List waiterCopy;
562	649	synchronized (waitingOwners) {
563	649	waiterCopy = new ArrayList(waitingOwners);
564	649	}
565	649	Collection conflicts = getConflictingOwners(owner, waiterCopy);
566	649	return conflicts;
567		}
568	1	return null;
569		}
570
571		protected Set getConflictingOwners(LockOwner myOwner, Collection ownersToTest) {
572
573	896	if (myOwner == null) return null;
574
575	896	Set conflicts = new HashSet();
576
577		// check if any locks conflict with ours
578	896	for (Iterator it = ownersToTest.iterator(); it.hasNext();) {
579	821	LockOwner owner = (LockOwner) it.next();
580
581		// we do not interfere with ourselves, except when explicitely said so
582	821	if ((myOwner.compatibility == COMPATIBILITY_REENTRANT \|\| myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT)
583		&& owner.ownerId.equals(myOwner.ownerId))
584	32	continue;
585
586		// otherwise find out the lock level of the owner and see if we conflict with it
587	789	int onwerLockLevel = owner.lockLevel;
588
589	789	if (myOwner.compatibility == COMPATIBILITY_SUPPORT
590		\|\| myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT
591		&& myOwner.lockLevel == onwerLockLevel)
592	0	continue;
593
594	789	if (!isCompatible(myOwner.lockLevel, onwerLockLevel)) {
595	679	conflicts.add(owner.ownerId);
596		}
597	789	}
598	896	return (conflicts.isEmpty() ? null : conflicts);
599		}
600
601		protected static class LockOwner {
602		public final Object ownerId;
603		public final int lockLevel;
604		public final boolean intention;
605		public final int compatibility;
606
607	7940	public LockOwner(Object ownerId, int lockLevel, int compatibility, boolean intention) {
608	7940	this.ownerId = ownerId;
609	7940	this.lockLevel = lockLevel;
610	7940	this.intention = intention;
611	7940	this.compatibility = compatibility;
612	7940	}
613
614		public String toString() {
615	72	StringBuffer buf = new StringBuffer();
616	72	buf.append(ownerId.toString()).append(": level ").append(lockLevel).append(", complevel ")
617		.append(compatibility).append(intention ? ", intention/preferred" : "");
618	72	return buf.toString();
619		}
620
621		public boolean equals(Object o) {
622	5945	if (o instanceof LockOwner) {
623	3258	return ((LockOwner)o).ownerId.equals(ownerId);
624		}
625	2687	return false;
626		}
627
628		public int hashCode() {
629	0	return ownerId.hashCode();
630		}
631		}
632
633		}