Coverage Report

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

Classes in this File

Line Coverage

Branch Coverage

Complexity

GenericLockManager

84%

192/226

77%

67/86

2.9

 /*
  * 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.Map;
 import java.util.Set;
 
 import org.apache.commons.transaction.util.LoggerFacade;
 
 /**
  * Manager for {@link GenericLock}s on resources. This implementation includes 
  * <ul>
  * <li>deadlock detection, which is configurable to come into effect after an initial short waiting
  * lock request; this is useful as it is somewhat expensive
  * <li>global transaction timeouts that actively revoke granted rights from transactions
  * </ul>
  * 
  * @version $Id: GenericLockManager.java 545634 2007-06-08 21:36:59Z ozeigermann $
  */
 public class GenericLockManager implements LockManager, LockManager2 {
 
     public static final long DEFAULT_TIMEOUT = 30000;
     public static final long DEFAULT_CHECK_THRESHHOLD = 500;
     
     /** Maps onwerId to locks it (partially) owns. */
     protected Map globalOwners = Collections.synchronizedMap(new HashMap());
 
     /** Maps resourceId to lock. */
     protected Map globalLocks = new HashMap();
     
     /** Maps onwerId to global effective time outs (i.e. the time the lock will time out). */
     protected Map effectiveGlobalTimeouts = Collections.synchronizedMap(new HashMap());
 
     protected Set timedOutOwners = Collections.synchronizedSet(new HashSet());
     
     protected int maxLockLevel = -1;
     protected LoggerFacade logger;
     protected long globalTimeoutMSecs;
     protected long checkThreshhold;
     
     /**
      * Creates a new generic lock manager.
      * 
      * @param maxLockLevel
      *            highest allowed lock level as described in {@link GenericLock}
      *            's class intro
      * @param logger
      *            generic logger used for all kind of debug logging
      * @param timeoutMSecs
      *            specifies the maximum time to wait for a lock in milliseconds
      * @param checkThreshholdMSecs
      *            specifies a special wait threshhold before deadlock and
      *            timeout detection come into play or <code>-1</code> switch
      *            it off and check for directly
      * @throws IllegalArgumentException
      *             if maxLockLevel is less than 1
      * 
      * @since 1.1
      */
     public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs,
             long checkThreshholdMSecs) throws IllegalArgumentException {
         if (maxLockLevel < 1)
             throw new IllegalArgumentException("The maximum lock level must be at least 1 ("
                     + maxLockLevel + " was specified)");
         this.maxLockLevel = maxLockLevel;
         this.logger = logger.createLogger("Locking");
         this.globalTimeoutMSecs = timeoutMSecs;
         this.checkThreshhold = checkThreshholdMSecs;
     }
 
     public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs)
             throws IllegalArgumentException {
         this(maxLockLevel, logger, timeoutMSecs, DEFAULT_CHECK_THRESHHOLD);
     }
 
     public GenericLockManager(int maxLockLevel, LoggerFacade logger)
             throws IllegalArgumentException {
         this(maxLockLevel, logger, DEFAULT_TIMEOUT);
     }
 
     /**
      * @see LockManager2#startGlobalTimeout(Object, long)
      * @since 1.1
      */
     public void startGlobalTimeout(Object ownerId, long timeoutMSecs) {
         long now = System.currentTimeMillis();
         long timeout = now + timeoutMSecs;
         effectiveGlobalTimeouts.put(ownerId, new Long(timeout));
     }
     
     /**
      * @see LockManager2#tryLock(Object, Object, int, boolean)
      * @since 1.1
      */
     public boolean tryLock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant) {
         timeoutCheck(ownerId);
 
         GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
         boolean acquired = lock.tryLock(ownerId, targetLockLevel,
                 reentrant ? GenericLock.COMPATIBILITY_REENTRANT : GenericLock.COMPATIBILITY_NONE,
                 false);
         
         if (acquired) {
             addOwner(ownerId, lock);
         }
         return acquired;
     }
 
     /**
      * @see LockManager2#checkLock(Object, Object, int, boolean)
      * @since 1.1
      */
     public boolean checkLock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant) {
         timeoutCheck(ownerId);
         boolean possible = true;
 
         GenericLock lock = (GenericLock) getLock(resourceId);
         if (lock != null) {
             possible = lock.test(ownerId, targetLockLevel,
                     reentrant ? GenericLock.COMPATIBILITY_REENTRANT
                             : GenericLock.COMPATIBILITY_NONE);
         }
         return possible;
     }
 
     /**
      * @see LockManager2#hasLock(Object, Object, int)
      * @since 1.1
      */
     public boolean hasLock(Object ownerId, Object resourceId, int lockLevel) {
         timeoutCheck(ownerId);
         boolean owned = false;
 
         GenericLock lock = (GenericLock) getLock(resourceId);
         if (lock != null) {
             owned = lock.has(ownerId, lockLevel);
         }
         return owned;
     }
 
     /**
      * @see LockManager2#lock(Object, Object, int, boolean)
      * @since 1.1
      */
     public void lock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant)
             throws LockException {
         lock(ownerId, resourceId, targetLockLevel, reentrant, globalTimeoutMSecs);
     }
 
     /**
      * @see LockManager2#lock(Object, Object, int, boolean, long)
      * @since 1.1
      */
     public void lock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant,
             long timeoutMSecs) throws LockException {
         lock(ownerId, resourceId, targetLockLevel, reentrant ? GenericLock.COMPATIBILITY_REENTRANT
                 : GenericLock.COMPATIBILITY_NONE, false, timeoutMSecs);
     }
 
     /**
      * @see LockManager2#lock(Object, Object, int, int, boolean, long)
      * @since 1.1
      */
     public void lock(Object ownerId, Object resourceId, int targetLockLevel, int compatibility,
             boolean preferred, long timeoutMSecs) throws LockException {
         timeoutCheck(ownerId);
         GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
         doLock(lock, ownerId, resourceId, targetLockLevel, compatibility, preferred, timeoutMSecs);
     }
 
     protected void doLock(GenericLock lock, Object ownerId, Object resourceId, int targetLockLevel,
                           int compatibility, boolean preferred, long timeoutMSecs)
     {
         long now = System.currentTimeMillis();
         long waitEnd = now + timeoutMSecs;
 
         timeoutCheck(ownerId);
         
         GenericLock.LockOwner lockWaiter = new GenericLock.LockOwner(ownerId, targetLockLevel,
                 compatibility, preferred);
         
         boolean acquired = false;
         try {
             
             // detection for deadlocks and time outs is rather expensive, 
             // so we wait for the lock for a  
             // short time (<5 seconds) to see if we get it without checking;
             // if not we still can check what the reason for this is
             if (checkThreshhold != -1 && timeoutMSecs > checkThreshhold) {
                 acquired = lock
                         .acquire(ownerId, targetLockLevel, true, compatibility,
                                 preferred, checkThreshhold);
                 timeoutMSecs -= checkThreshhold;
             } else {
                 acquired = lock
                 .acquire(ownerId, targetLockLevel, false, compatibility,
                         preferred, checkThreshhold);
                 
             }
             if (acquired) {
                 addOwner(ownerId, lock);
                 return;
             }
         } catch (InterruptedException e) {
             throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
         }
         try {
             lock.registerWaiter(lockWaiter);
             
             boolean deadlock = wouldDeadlock(ownerId, new HashSet());
             if (deadlock) {
                 throw new LockException("Lock would cause deadlock",
                         LockException.CODE_DEADLOCK_VICTIM, resourceId);
             }
 
             now = System.currentTimeMillis();
             while (!acquired && waitEnd > now) {
             
                 // first be sure all locks are stolen from owners that have already timed out
                 releaseTimedOutOwners();
 
                 // if there are owners we conflict with lets see if one of them globally times
                 // out earlier than this lock, if so we will wake up then to check again
                 Set conflicts = lock.getConflictingOwners(ownerId, targetLockLevel, compatibility);
                 long nextConflictTimeout = getNextGlobalConflictTimeout(conflicts);
                 if (nextConflictTimeout != -1 && nextConflictTimeout < waitEnd) {
                     timeoutMSecs = nextConflictTimeout - now;
                     // XXX add 10% to ensure the lock really is timed out
                     timeoutMSecs += timeoutMSecs / 10;
                 } else {
                     timeoutMSecs = waitEnd - now;
                 }
 
                 // XXX acquire will remove us as a waiter, but it is important to remain us such
                 // to constantly indicate it to other owners, otherwise there might be undetected
                 // deadlocks
                 synchronized (lock) {
                     acquired = lock.acquire(ownerId, targetLockLevel, true, compatibility,
                             preferred, timeoutMSecs);
                     lock.registerWaiter(lockWaiter);
                 }
                 now = System.currentTimeMillis();
             }
             if (!acquired) {
                 throw new LockException("Lock wait timed out", LockException.CODE_TIMED_OUT,
                         resourceId);
             } else {
                 addOwner(ownerId, lock);
             }
         } catch (InterruptedException e) {
             throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
         } finally {
             lock.unregisterWaiter(lockWaiter);
         }
     }
 
     /**
      * @see LockManager2#getLevel(Object, Object)
      * @since 1.1
      */
     public int getLevel(Object ownerId, Object resourceId) {
         timeoutCheck(ownerId);
         GenericLock lock = (GenericLock) getLock(resourceId);
         if (lock != null) {
             return lock.getLockLevel(ownerId);
         } else {
             return 0;
         }
     }
 
     /**
      * @see LockManager2#release(Object, Object)
      * @since 1.1
      */
     public boolean release(Object ownerId, Object resourceId) {
         timeoutCheck(ownerId);
         boolean released = false;
 
         GenericLock lock = (GenericLock) getLock(resourceId);
         if (lock != null) {
             released = lock.release(ownerId);
             removeOwner(ownerId, lock);
         }
         return released;
     }
 
     /**
      * @see LockManager2#releaseAll(Object)
      * @since 1.1
      */
     public void releaseAll(Object ownerId) {
         releaseAllNoTimeOutReset(ownerId);
         // reset time out status for this owner
         timedOutOwners.remove(ownerId);
         effectiveGlobalTimeouts.remove(ownerId);
     }
 
     protected void releaseAllNoTimeOutReset(Object ownerId) {
         Set locks = (Set) globalOwners.get(ownerId);
         if (locks != null) {
             Collection locksCopy;
             // need to copy in order not to interfere with wouldDeadlock
             // possibly called by
             // other threads
             synchronized (locks) {
                 locksCopy = new ArrayList(locks);
             }
             for (Iterator it = locksCopy.iterator(); it.hasNext();) {
                 GenericLock lock = (GenericLock) it.next();
                 lock.release(ownerId);
                 locks.remove(lock);
             }
         }
         removeOwnerWithoutLocks(ownerId);
     }
     
     /**
      * @see LockManager2#getAll(Object)
      * @since 1.1
      */
     public Set getAll(Object ownerId) {
         Set locks = (Set) globalOwners.get(ownerId);
         if (locks == null) {
             return new HashSet();
         } else {
             return locks;
         }
     }
 
     protected void addOwner(Object ownerId, GenericLock lock) {
         synchronized (globalOwners) {
             Set locks = (Set) globalOwners.get(ownerId);
             if (locks == null) {
                 locks = Collections.synchronizedSet(new HashSet());
                 globalOwners.put(ownerId, locks);
             }
             locks.add(lock);
         }
     }
 
     protected void removeOwner(Object ownerId, GenericLock lock) {
         Set locks = (Set) globalOwners.get(ownerId);
         if (locks != null) {
             locks.remove(lock);
         }
         removeOwnerWithoutLocks(ownerId);
     }
 
     /**
      * Checks if an owner is deadlocked. <br>
      * <br>
      * We traverse the tree recursively formed by owners, locks held by them and
      * then again owners waiting for the locks. If there is a cycle in one of
      * the paths from the root to a leaf we have a deadlock. <br>
      * <br>
      * A more detailed discussion on deadlocks and definitions and how to detect
      * them can be found in <a
      * href="http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html?page=1">this
      * nice article </a>. <br>
      * <em>Caution:</em> This computation can be very expensive with many
      * owners and locks. Worst (unlikely) case is exponential.
      * 
      * @param ownerId
      *            the owner to check for being deadlocked
      * @param path
      *            initially should be called with an empty set
      * @return <code>true</code> if the owner is deadlocked,
      *         <code>false</code> otherwise
      */
     protected boolean wouldDeadlock(Object ownerId, Set path) {
         path.add(ownerId);
         // these are our locks
         Set locks = (Set) globalOwners.get(ownerId);
         if (locks != null) {
             Collection locksCopy;
             // need to copy in order not to interfere with releaseAll possibly called by
             // other threads
             synchronized (locks) {
                 locksCopy = new ArrayList(locks);
             }
             for (Iterator i = locksCopy.iterator(); i.hasNext();) {
                 GenericLock mylock = (GenericLock) i.next();
                 // these are the ones waiting for one of our locks
                 Collection conflicts = mylock.getConflictingWaiters(ownerId);
                 if (conflicts != null) {
                     for (Iterator j = conflicts.iterator(); j.hasNext();) {
                         Object waitingOwnerId = j.next();
                         if (path.contains(waitingOwnerId)) {
                             return true;
                         } else if (wouldDeadlock(waitingOwnerId, path)) {
                             return true;
                         }
                     }
                 }
             }
         }
         path.remove(ownerId);
         return false;
     }
 
     protected boolean releaseTimedOutOwners() {
         boolean released = false;
         synchronized (effectiveGlobalTimeouts) {
             for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
                 Map.Entry entry = (Map.Entry) it.next();
                 Object ownerId = entry.getKey();
                 long timeout = ((Long) entry.getValue()).longValue();
                 long now = System.currentTimeMillis();
                 if (timeout < now) {
                     releaseAllNoTimeOutReset(ownerId);
                     timedOutOwners.add(ownerId);
                     released = true;
                 }
             }
         }
         return released;
     }
     
     protected boolean timeOut(Object ownerId) {
         Long timeout = (Long)effectiveGlobalTimeouts.get(ownerId);
         long now = System.currentTimeMillis();
         if (timeout != null && timeout.longValue() < now) {
             releaseAll(ownerId);
             timedOutOwners.add(ownerId);
             return true;
         } else {
             return false;
         }
     }
     
     protected long getNextGlobalConflictTimeout(Set conflicts) {
         long minTimeout = -1;
         long now = System.currentTimeMillis();
         if (conflicts != null) {
             synchronized (effectiveGlobalTimeouts) {
                 for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
                     Map.Entry entry = (Map.Entry) it.next();
                     Object ownerId = entry.getKey();
                     if (conflicts.contains(ownerId)) {
                         long timeout = ((Long) entry.getValue()).longValue();
                         if (minTimeout == -1 || timeout < minTimeout) {
                             minTimeout = timeout;
                         }
                     }
                 }
             }
         }
         return minTimeout;
     }
     
     public MultiLevelLock getLock(Object resourceId) {
         synchronized (globalLocks) {
             return (MultiLevelLock) globalLocks.get(resourceId);
         }
     }
 
     public MultiLevelLock atomicGetOrCreateLock(Object resourceId) {
         synchronized (globalLocks) {
             MultiLevelLock lock = getLock(resourceId);
             if (lock == null) {
                 lock = createLock(resourceId);
             }
             return lock;
         }
     }
 
     public void removeLock(MultiLevelLock lock) {
         synchronized (globalLocks) {
             globalLocks.remove(lock);
         }
     }
     
     /**
      * Gets all locks as orignials, <em>no copies</em>.
      * 
      * @return collection holding all locks.
      */
     public Collection getLocks() {
         synchronized (globalLocks) {
            return globalLocks.values();
         }
     }
 
     public synchronized String toString() {
         StringBuffer buf = new StringBuffer(1000);
         for (Iterator it = globalLocks.values().iterator(); it.hasNext();) {
             GenericLock lock = (GenericLock) it.next();
             buf.append(lock.toString()).append('\n');
         }
         return buf.toString();
     }
 
     protected GenericLock createLock(Object resourceId) {
         synchronized (globalLocks) {
             GenericLock lock = new GenericLock(resourceId, maxLockLevel, logger);
             globalLocks.put(resourceId, lock);
             return lock;
         }
     }
     
     protected void timeoutCheck(Object ownerId) throws LockException {
         timeOut(ownerId);
         if (timedOutOwners.contains(ownerId)) {
             throw new LockException(
                     "All locks of owner "
                             + ownerId
                             + " have globally timed out."
                             + " You will not be able to to continue with this owner until you call releaseAll.",
                     LockException.CODE_TIMED_OUT, null);
         }
     }
 
     protected void removeOwnerWithoutLocks(Object ownerId) {
         synchronized (globalOwners) {
             Set locks = (Set) globalOwners.get(ownerId);
             if (locks == null || locks.isEmpty()) {
                 globalOwners.remove(ownerId);
             }
         }
     }
 }

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.Map;
26		import java.util.Set;
27
28		import org.apache.commons.transaction.util.LoggerFacade;
29
30		/**
31		* Manager for {@link GenericLock}s on resources. This implementation includes
32		* <ul>
33		* <li>deadlock detection, which is configurable to come into effect after an initial short waiting
34		* lock request; this is useful as it is somewhat expensive
35		* <li>global transaction timeouts that actively revoke granted rights from transactions
36		* </ul>
37		*
38		* @version $Id: GenericLockManager.java 545634 2007-06-08 21:36:59Z ozeigermann $
39		*/
40		public class GenericLockManager implements LockManager, LockManager2 {
41
42		public static final long DEFAULT_TIMEOUT = 30000;
43		public static final long DEFAULT_CHECK_THRESHHOLD = 500;
44
45		/** Maps onwerId to locks it (partially) owns. */
46	26	protected Map globalOwners = Collections.synchronizedMap(new HashMap());
47
48		/** Maps resourceId to lock. */
49	26	protected Map globalLocks = new HashMap();
50
51		/** Maps onwerId to global effective time outs (i.e. the time the lock will time out). */
52	26	protected Map effectiveGlobalTimeouts = Collections.synchronizedMap(new HashMap());
53
54	26	protected Set timedOutOwners = Collections.synchronizedSet(new HashSet());
55
56	26	protected int maxLockLevel = -1;
57		protected LoggerFacade logger;
58		protected long globalTimeoutMSecs;
59		protected long checkThreshhold;
60
61		/**
62		* Creates a new generic lock manager.
63		*
64		* @param maxLockLevel
65		* highest allowed lock level as described in {@link GenericLock}
66		* 's class intro
67		* @param logger
68		* generic logger used for all kind of debug logging
69		* @param timeoutMSecs
70		* specifies the maximum time to wait for a lock in milliseconds
71		* @param checkThreshholdMSecs
72		* specifies a special wait threshhold before deadlock and
73		* timeout detection come into play or <code>-1</code> switch
74		* it off and check for directly
75		* @throws IllegalArgumentException
76		* if maxLockLevel is less than 1
77		*
78		* @since 1.1
79		*/
80		public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs,
81	26	long checkThreshholdMSecs) throws IllegalArgumentException {
82	26	if (maxLockLevel < 1)
83	0	throw new IllegalArgumentException("The maximum lock level must be at least 1 ("
84		+ maxLockLevel + " was specified)");
85	26	this.maxLockLevel = maxLockLevel;
86	26	this.logger = logger.createLogger("Locking");
87	26	this.globalTimeoutMSecs = timeoutMSecs;
88	26	this.checkThreshhold = checkThreshholdMSecs;
89	26	}
90
91		public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs)
92		throws IllegalArgumentException {
93	25	this(maxLockLevel, logger, timeoutMSecs, DEFAULT_CHECK_THRESHHOLD);
94	25	}
95
96		public GenericLockManager(int maxLockLevel, LoggerFacade logger)
97		throws IllegalArgumentException {
98	10	this(maxLockLevel, logger, DEFAULT_TIMEOUT);
99	10	}
100
101		/**
102		* @see LockManager2#startGlobalTimeout(Object, long)
103		* @since 1.1
104		*/
105		public void startGlobalTimeout(Object ownerId, long timeoutMSecs) {
106	50	long now = System.currentTimeMillis();
107	50	long timeout = now + timeoutMSecs;
108	50	effectiveGlobalTimeouts.put(ownerId, new Long(timeout));
109	50	}
110
111		/**
112		* @see LockManager2#tryLock(Object, Object, int, boolean)
113		* @since 1.1
114		*/
115		public boolean tryLock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant) {
116	50	timeoutCheck(ownerId);
117
118	25	GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
119	25	boolean acquired = lock.tryLock(ownerId, targetLockLevel,
120		reentrant ? GenericLock.COMPATIBILITY_REENTRANT : GenericLock.COMPATIBILITY_NONE,
121		false);
122
123	25	if (acquired) {
124	25	addOwner(ownerId, lock);
125		}
126	25	return acquired;
127		}
128
129		/**
130		* @see LockManager2#checkLock(Object, Object, int, boolean)
131		* @since 1.1
132		*/
133		public boolean checkLock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant) {
134	0	timeoutCheck(ownerId);
135	0	boolean possible = true;
136
137	0	GenericLock lock = (GenericLock) getLock(resourceId);
138	0	if (lock != null) {
139	0	possible = lock.test(ownerId, targetLockLevel,
140		reentrant ? GenericLock.COMPATIBILITY_REENTRANT
141		: GenericLock.COMPATIBILITY_NONE);
142		}
143	0	return possible;
144		}
145
146		/**
147		* @see LockManager2#hasLock(Object, Object, int)
148		* @since 1.1
149		*/
150		public boolean hasLock(Object ownerId, Object resourceId, int lockLevel) {
151	0	timeoutCheck(ownerId);
152	0	boolean owned = false;
153
154	0	GenericLock lock = (GenericLock) getLock(resourceId);
155	0	if (lock != null) {
156	0	owned = lock.has(ownerId, lockLevel);
157		}
158	0	return owned;
159		}
160
161		/**
162		* @see LockManager2#lock(Object, Object, int, boolean)
163		* @since 1.1
164		*/
165		public void lock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant)
166		throws LockException {
167	542	lock(ownerId, resourceId, targetLockLevel, reentrant, globalTimeoutMSecs);
168	538	}
169
170		/**
171		* @see LockManager2#lock(Object, Object, int, boolean, long)
172		* @since 1.1
173		*/
174		public void lock(Object ownerId, Object resourceId, int targetLockLevel, boolean reentrant,
175		long timeoutMSecs) throws LockException {
176	663	lock(ownerId, resourceId, targetLockLevel, reentrant ? GenericLock.COMPATIBILITY_REENTRANT
177		: GenericLock.COMPATIBILITY_NONE, false, timeoutMSecs);
178	614	}
179
180		/**
181		* @see LockManager2#lock(Object, Object, int, int, boolean, long)
182		* @since 1.1
183		*/
184		public void lock(Object ownerId, Object resourceId, int targetLockLevel, int compatibility,
185		boolean preferred, long timeoutMSecs) throws LockException {
186	3134	timeoutCheck(ownerId);
187	3132	GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
188	3132	doLock(lock, ownerId, resourceId, targetLockLevel, compatibility, preferred, timeoutMSecs);
189	2953	}
190
191		protected void doLock(GenericLock lock, Object ownerId, Object resourceId, int targetLockLevel,
192		int compatibility, boolean preferred, long timeoutMSecs)
193		{
194	3132	long now = System.currentTimeMillis();
195	3132	long waitEnd = now + timeoutMSecs;
196
197	3132	timeoutCheck(ownerId);
198
199	3132	GenericLock.LockOwner lockWaiter = new GenericLock.LockOwner(ownerId, targetLockLevel,
200		compatibility, preferred);
201
202	3132	boolean acquired = false;
203		try {
204
205		// detection for deadlocks and time outs is rather expensive,
206		// so we wait for the lock for a
207		// short time (<5 seconds) to see if we get it without checking;
208		// if not we still can check what the reason for this is
209	3132	if (checkThreshhold != -1 && timeoutMSecs > checkThreshhold) {
210	2040	acquired = lock
211		.acquire(ownerId, targetLockLevel, true, compatibility,
212		preferred, checkThreshhold);
213	2040	timeoutMSecs -= checkThreshhold;
214		} else {
215	1092	acquired = lock
216		.acquire(ownerId, targetLockLevel, false, compatibility,
217		preferred, checkThreshhold);
218
219		}
220	3132	if (acquired) {
221	2724	addOwner(ownerId, lock);
222	2724	return;
223		}
224	0	} catch (InterruptedException e) {
225	0	throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
226	408	}
227		try {
228	408	lock.registerWaiter(lockWaiter);
229
230	408	boolean deadlock = wouldDeadlock(ownerId, new HashSet());
231	408	if (deadlock) {
232	176	throw new LockException("Lock would cause deadlock",
233		LockException.CODE_DEADLOCK_VICTIM, resourceId);
234		}
235
236	232	now = System.currentTimeMillis();
237	489	while (!acquired && waitEnd > now) {
238
239		// first be sure all locks are stolen from owners that have already timed out
240	257	releaseTimedOutOwners();
241
242		// if there are owners we conflict with lets see if one of them globally times
243		// out earlier than this lock, if so we will wake up then to check again
244	257	Set conflicts = lock.getConflictingOwners(ownerId, targetLockLevel, compatibility);
245	257	long nextConflictTimeout = getNextGlobalConflictTimeout(conflicts);
246	257	if (nextConflictTimeout != -1 && nextConflictTimeout < waitEnd) {
247	30	timeoutMSecs = nextConflictTimeout - now;
248		// XXX add 10% to ensure the lock really is timed out
249	30	timeoutMSecs += timeoutMSecs / 10;
250		} else {
251	227	timeoutMSecs = waitEnd - now;
252		}
253
254		// XXX acquire will remove us as a waiter, but it is important to remain us such
255		// to constantly indicate it to other owners, otherwise there might be undetected
256		// deadlocks
257	257	synchronized (lock) {
258	257	acquired = lock.acquire(ownerId, targetLockLevel, true, compatibility,
259		preferred, timeoutMSecs);
260	257	lock.registerWaiter(lockWaiter);
261	257	}
262	257	now = System.currentTimeMillis();
263	257	}
264	232	if (!acquired) {
265	3	throw new LockException("Lock wait timed out", LockException.CODE_TIMED_OUT,
266		resourceId);
267		} else {
268	229	addOwner(ownerId, lock);
269		}
270	0	} catch (InterruptedException e) {
271	0	throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
272		} finally {
273	408	lock.unregisterWaiter(lockWaiter);
274	229	}
275	229	}
276
277		/**
278		* @see LockManager2#getLevel(Object, Object)
279		* @since 1.1
280		*/
281		public int getLevel(Object ownerId, Object resourceId) {
282	2	timeoutCheck(ownerId);
283	2	GenericLock lock = (GenericLock) getLock(resourceId);
284	2	if (lock != null) {
285	2	return lock.getLockLevel(ownerId);
286		} else {
287	0	return 0;
288		}
289		}
290
291		/**
292		* @see LockManager2#release(Object, Object)
293		* @since 1.1
294		*/
295		public boolean release(Object ownerId, Object resourceId) {
296	26	timeoutCheck(ownerId);
297	26	boolean released = false;
298
299	26	GenericLock lock = (GenericLock) getLock(resourceId);
300	26	if (lock != null) {
301	26	released = lock.release(ownerId);
302	26	removeOwner(ownerId, lock);
303		}
304	26	return released;
305		}
306
307		/**
308		* @see LockManager2#releaseAll(Object)
309		* @since 1.1
310		*/
311		public void releaseAll(Object ownerId) {
312	1894	releaseAllNoTimeOutReset(ownerId);
313		// reset time out status for this owner
314	1894	timedOutOwners.remove(ownerId);
315	1894	effectiveGlobalTimeouts.remove(ownerId);
316	1894	}
317
318		protected void releaseAllNoTimeOutReset(Object ownerId) {
319	1919	Set locks = (Set) globalOwners.get(ownerId);
320	1919	if (locks != null) {
321		Collection locksCopy;
322		// need to copy in order not to interfere with wouldDeadlock
323		// possibly called by
324		// other threads
325	1689	synchronized (locks) {
326	1689	locksCopy = new ArrayList(locks);
327	1689	}
328	1689	for (Iterator it = locksCopy.iterator(); it.hasNext();) {
329	2308	GenericLock lock = (GenericLock) it.next();
330	2308	lock.release(ownerId);
331	2308	locks.remove(lock);
332	2308	}
333		}
334	1919	removeOwnerWithoutLocks(ownerId);
335	1919	}
336
337		/**
338		* @see LockManager2#getAll(Object)
339		* @since 1.1
340		*/
341		public Set getAll(Object ownerId) {
342	187	Set locks = (Set) globalOwners.get(ownerId);
343	187	if (locks == null) {
344	124	return new HashSet();
345		} else {
346	63	return locks;
347		}
348		}
349
350		protected void addOwner(Object ownerId, GenericLock lock) {
351	2978	synchronized (globalOwners) {
352	2978	Set locks = (Set) globalOwners.get(ownerId);
353	2978	if (locks == null) {
354	1709	locks = Collections.synchronizedSet(new HashSet());
355	1709	globalOwners.put(ownerId, locks);
356		}
357	2978	locks.add(lock);
358	2978	}
359	2978	}
360
361		protected void removeOwner(Object ownerId, GenericLock lock) {
362	26	Set locks = (Set) globalOwners.get(ownerId);
363	26	if (locks != null) {
364	26	locks.remove(lock);
365		}
366	26	removeOwnerWithoutLocks(ownerId);
367	26	}
368
369		/**
370		* Checks if an owner is deadlocked. <br>
371		* <br>
372		* We traverse the tree recursively formed by owners, locks held by them and
373		* then again owners waiting for the locks. If there is a cycle in one of
374		* the paths from the root to a leaf we have a deadlock. <br>
375		* <br>
376		* A more detailed discussion on deadlocks and definitions and how to detect
377		* them can be found in <a
378		* href="http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html?page=1">this
379		* nice article </a>. <br>
380		* <em>Caution:</em> This computation can be very expensive with many
381		* owners and locks. Worst (unlikely) case is exponential.
382		*
383		* @param ownerId
384		* the owner to check for being deadlocked
385		* @param path
386		* initially should be called with an empty set
387		* @return <code>true</code> if the owner is deadlocked,
388		* <code>false</code> otherwise
389		*/
390		protected boolean wouldDeadlock(Object ownerId, Set path) {
391	698	path.add(ownerId);
392		// these are our locks
393	698	Set locks = (Set) globalOwners.get(ownerId);
394	698	if (locks != null) {
395		Collection locksCopy;
396		// need to copy in order not to interfere with releaseAll possibly called by
397		// other threads
398	555	synchronized (locks) {
399	555	locksCopy = new ArrayList(locks);
400	555	}
401	555	for (Iterator i = locksCopy.iterator(); i.hasNext();) {
402	650	GenericLock mylock = (GenericLock) i.next();
403		// these are the ones waiting for one of our locks
404	650	Collection conflicts = mylock.getConflictingWaiters(ownerId);
405	650	if (conflicts != null) {
406	453	for (Iterator j = conflicts.iterator(); j.hasNext();) {
407	466	Object waitingOwnerId = j.next();
408	466	if (path.contains(waitingOwnerId)) {
409	176	return true;
410	290	} else if (wouldDeadlock(waitingOwnerId, path)) {
411	211	return true;
412		}
413	79	}
414		}
415	263	}
416		}
417	311	path.remove(ownerId);
418	311	return false;
419		}
420
421		protected boolean releaseTimedOutOwners() {
422	257	boolean released = false;
423	257	synchronized (effectiveGlobalTimeouts) {
424	257	for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
425	106	Map.Entry entry = (Map.Entry) it.next();
426	106	Object ownerId = entry.getKey();
427	106	long timeout = ((Long) entry.getValue()).longValue();
428	106	long now = System.currentTimeMillis();
429	106	if (timeout < now) {
430	25	releaseAllNoTimeOutReset(ownerId);
431	25	timedOutOwners.add(ownerId);
432	25	released = true;
433		}
434	106	}
435	257	}
436	257	return released;
437		}
438
439		protected boolean timeOut(Object ownerId) {
440	6344	Long timeout = (Long)effectiveGlobalTimeouts.get(ownerId);
441	6344	long now = System.currentTimeMillis();
442	6344	if (timeout != null && timeout.longValue() < now) {
443	27	releaseAll(ownerId);
444	27	timedOutOwners.add(ownerId);
445	27	return true;
446		} else {
447	6317	return false;
448		}
449		}
450
451		protected long getNextGlobalConflictTimeout(Set conflicts) {
452	257	long minTimeout = -1;
453	257	long now = System.currentTimeMillis();
454	257	if (conflicts != null) {
455	133	synchronized (effectiveGlobalTimeouts) {
456	133	for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
457	41	Map.Entry entry = (Map.Entry) it.next();
458	41	Object ownerId = entry.getKey();
459	41	if (conflicts.contains(ownerId)) {
460	30	long timeout = ((Long) entry.getValue()).longValue();
461	30	if (minTimeout == -1 \|\| timeout < minTimeout) {
462	30	minTimeout = timeout;
463		}
464		}
465	41	}
466	133	}
467		}
468	257	return minTimeout;
469		}
470
471		public MultiLevelLock getLock(Object resourceId) {
472	3310	synchronized (globalLocks) {
473	3310	return (MultiLevelLock) globalLocks.get(resourceId);
474	0	}
475		}
476
477		public MultiLevelLock atomicGetOrCreateLock(Object resourceId) {
478	3157	synchronized (globalLocks) {
479	3157	MultiLevelLock lock = getLock(resourceId);
480	3157	if (lock == null) {
481	53	lock = createLock(resourceId);
482		}
483	3157	return lock;
484	0	}
485		}
486
487		public void removeLock(MultiLevelLock lock) {
488	0	synchronized (globalLocks) {
489	0	globalLocks.remove(lock);
490	0	}
491	0	}
492
493		/**
494		* Gets all locks as orignials, <em>no copies</em>.
495		*
496		* @return collection holding all locks.
497		*/
498		public Collection getLocks() {
499	0	synchronized (globalLocks) {
500	0	return globalLocks.values();
501	0	}
502		}
503
504		public synchronized String toString() {
505	0	StringBuffer buf = new StringBuffer(1000);
506	0	for (Iterator it = globalLocks.values().iterator(); it.hasNext();) {
507	0	GenericLock lock = (GenericLock) it.next();
508	0	buf.append(lock.toString()).append('\n');
509	0	}
510	0	return buf.toString();
511		}
512
513		protected GenericLock createLock(Object resourceId) {
514	13	synchronized (globalLocks) {
515	13	GenericLock lock = new GenericLock(resourceId, maxLockLevel, logger);
516	13	globalLocks.put(resourceId, lock);
517	13	return lock;
518	0	}
519		}
520
521		protected void timeoutCheck(Object ownerId) throws LockException {
522	6344	timeOut(ownerId);
523	6344	if (timedOutOwners.contains(ownerId)) {
524	27	throw new LockException(
525		"All locks of owner "
526		+ ownerId
527		+ " have globally timed out."
528		+ " You will not be able to to continue with this owner until you call releaseAll.",
529		LockException.CODE_TIMED_OUT, null);
530		}
531	6317	}
532
533		protected void removeOwnerWithoutLocks(Object ownerId) {
534	1945	synchronized (globalOwners) {
535	1945	Set locks = (Set) globalOwners.get(ownerId);
536	1945	if (locks == null \|\| locks.isEmpty()) {
537	1944	globalOwners.remove(ownerId);
538		}
539	1945	}
540	1945	}
541		}