001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: package org.apache.commons.transaction.locking;
018:
019: import java.util.ArrayList;
020: import java.util.Collection;
021: import java.util.Collections;
022: import java.util.HashMap;
023: import java.util.HashSet;
024: import java.util.Iterator;
025: import java.util.Map;
026: import java.util.Set;
027:
028: import org.apache.commons.transaction.util.LoggerFacade;
029:
030: /**
031: * Manager for {@link GenericLock}s on resources. This implementation includes
032: * <ul>
033: * <li>deadlock detection, which is configurable to come into effect after an initial short waiting
034: * lock request; this is useful as it is somewhat expensive
035: * <li>global transaction timeouts that actively revoke granted rights from transactions
036: * </ul>
037: *
038: * @version $Id: GenericLockManager.java 493628 2007-01-07 01:42:48Z joerg $
039: */
040: public class GenericLockManager implements LockManager, LockManager2 {
041:
042: public static final long DEFAULT_TIMEOUT = 30000;
043: public static final long DEFAULT_CHECK_THRESHHOLD = 500;
044:
045: /** Maps onwerId to locks it (partially) owns. */
046: protected Map globalOwners = Collections
047: .synchronizedMap(new HashMap());
048:
049: /** Maps resourceId to lock. */
050: protected Map globalLocks = new HashMap();
051:
052: /** Maps onwerId to global effective time outs (i.e. the time the lock will time out). */
053: protected Map effectiveGlobalTimeouts = Collections
054: .synchronizedMap(new HashMap());
055:
056: protected Set timedOutOwners = Collections
057: .synchronizedSet(new HashSet());
058:
059: protected int maxLockLevel = -1;
060: protected LoggerFacade logger;
061: protected long globalTimeoutMSecs;
062: protected long checkThreshhold;
063:
064: /**
065: * Creates a new generic lock manager.
066: *
067: * @param maxLockLevel
068: * highest allowed lock level as described in {@link GenericLock}
069: * 's class intro
070: * @param logger
071: * generic logger used for all kind of debug logging
072: * @param timeoutMSecs
073: * specifies the maximum time to wait for a lock in milliseconds
074: * @param checkThreshholdMSecs
075: * specifies a special wait threshhold before deadlock and
076: * timeout detection come into play or <code>-1</code> switch
077: * it off and check for directly
078: * @throws IllegalArgumentException
079: * if maxLockLevel is less than 1
080: *
081: * @since 1.1
082: */
083: public GenericLockManager(int maxLockLevel, LoggerFacade logger,
084: long timeoutMSecs, long checkThreshholdMSecs)
085: throws IllegalArgumentException {
086: if (maxLockLevel < 1)
087: throw new IllegalArgumentException(
088: "The maximum lock level must be at least 1 ("
089: + maxLockLevel + " was specified)");
090: this .maxLockLevel = maxLockLevel;
091: this .logger = logger.createLogger("Locking");
092: this .globalTimeoutMSecs = timeoutMSecs;
093: this .checkThreshhold = checkThreshholdMSecs;
094: }
095:
096: public GenericLockManager(int maxLockLevel, LoggerFacade logger,
097: long timeoutMSecs) throws IllegalArgumentException {
098: this (maxLockLevel, logger, timeoutMSecs,
099: DEFAULT_CHECK_THRESHHOLD);
100: }
101:
102: public GenericLockManager(int maxLockLevel, LoggerFacade logger)
103: throws IllegalArgumentException {
104: this (maxLockLevel, logger, DEFAULT_TIMEOUT);
105: }
106:
107: /**
108: * @see LockManager2#startGlobalTimeout(Object, long)
109: * @since 1.1
110: */
111: public void startGlobalTimeout(Object ownerId, long timeoutMSecs) {
112: long now = System.currentTimeMillis();
113: long timeout = now + timeoutMSecs;
114: effectiveGlobalTimeouts.put(ownerId, new Long(timeout));
115: }
116:
117: /**
118: * @see LockManager2#tryLock(Object, Object, int, boolean)
119: * @since 1.1
120: */
121: public boolean tryLock(Object ownerId, Object resourceId,
122: int targetLockLevel, boolean reentrant) {
123: timeoutCheck(ownerId);
124:
125: GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
126: boolean acquired = lock.tryLock(ownerId, targetLockLevel,
127: reentrant ? GenericLock.COMPATIBILITY_REENTRANT
128: : GenericLock.COMPATIBILITY_NONE, false);
129:
130: if (acquired) {
131: addOwner(ownerId, lock);
132: }
133: return acquired;
134: }
135:
136: /**
137: * @see LockManager2#checkLock(Object, Object, int, boolean)
138: * @since 1.1
139: */
140: public boolean checkLock(Object ownerId, Object resourceId,
141: int targetLockLevel, boolean reentrant) {
142: timeoutCheck(ownerId);
143: boolean possible = true;
144:
145: GenericLock lock = (GenericLock) getLock(resourceId);
146: if (lock != null) {
147: possible = lock.test(ownerId, targetLockLevel,
148: reentrant ? GenericLock.COMPATIBILITY_REENTRANT
149: : GenericLock.COMPATIBILITY_NONE);
150: }
151: return possible;
152: }
153:
154: /**
155: * @see LockManager2#hasLock(Object, Object, int)
156: * @since 1.1
157: */
158: public boolean hasLock(Object ownerId, Object resourceId,
159: int lockLevel) {
160: timeoutCheck(ownerId);
161: boolean owned = false;
162:
163: GenericLock lock = (GenericLock) getLock(resourceId);
164: if (lock != null) {
165: owned = lock.has(ownerId, lockLevel);
166: }
167: return owned;
168: }
169:
170: /**
171: * @see LockManager2#lock(Object, Object, int, boolean)
172: * @since 1.1
173: */
174: public void lock(Object ownerId, Object resourceId,
175: int targetLockLevel, boolean reentrant)
176: throws LockException {
177: lock(ownerId, resourceId, targetLockLevel, reentrant,
178: globalTimeoutMSecs);
179: }
180:
181: /**
182: * @see LockManager2#lock(Object, Object, int, boolean, long)
183: * @since 1.1
184: */
185: public void lock(Object ownerId, Object resourceId,
186: int targetLockLevel, boolean reentrant, long timeoutMSecs)
187: throws LockException {
188: lock(ownerId, resourceId, targetLockLevel,
189: reentrant ? GenericLock.COMPATIBILITY_REENTRANT
190: : GenericLock.COMPATIBILITY_NONE, false,
191: timeoutMSecs);
192: }
193:
194: /**
195: * @see LockManager2#lock(Object, Object, int, int, boolean, long)
196: * @since 1.1
197: */
198: public void lock(Object ownerId, Object resourceId,
199: int targetLockLevel, int compatibility, boolean preferred,
200: long timeoutMSecs) throws LockException {
201: timeoutCheck(ownerId);
202: GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
203: doLock(lock, ownerId, resourceId, targetLockLevel,
204: compatibility, preferred, timeoutMSecs);
205: }
206:
207: protected void doLock(GenericLock lock, Object ownerId,
208: Object resourceId, int targetLockLevel, int compatibility,
209: boolean preferred, long timeoutMSecs) {
210: long now = System.currentTimeMillis();
211: long waitEnd = now + timeoutMSecs;
212:
213: timeoutCheck(ownerId);
214:
215: GenericLock.LockOwner lockWaiter = new GenericLock.LockOwner(
216: ownerId, targetLockLevel, compatibility, preferred);
217:
218: boolean acquired = false;
219: try {
220:
221: // detection for deadlocks and time outs is rather expensive,
222: // so we wait for the lock for a
223: // short time (<5 seconds) to see if we get it without checking;
224: // if not we still can check what the reason for this is
225: if (checkThreshhold != -1 && timeoutMSecs > checkThreshhold) {
226: acquired = lock.acquire(ownerId, targetLockLevel, true,
227: compatibility, preferred, checkThreshhold);
228: timeoutMSecs -= checkThreshhold;
229: } else {
230: acquired = lock.acquire(ownerId, targetLockLevel,
231: false, compatibility, preferred,
232: checkThreshhold);
233:
234: }
235: if (acquired) {
236: addOwner(ownerId, lock);
237: return;
238: }
239: } catch (InterruptedException e) {
240: throw new LockException("Interrupted",
241: LockException.CODE_INTERRUPTED, resourceId);
242: }
243: try {
244: lock.registerWaiter(lockWaiter);
245:
246: boolean deadlock = wouldDeadlock(ownerId, new HashSet());
247: if (deadlock) {
248: throw new LockException("Lock would cause deadlock",
249: LockException.CODE_DEADLOCK_VICTIM, resourceId);
250: }
251:
252: now = System.currentTimeMillis();
253: while (!acquired && waitEnd > now) {
254:
255: // first be sure all locks are stolen from owners that have already timed out
256: releaseTimedOutOwners();
257:
258: // if there are owners we conflict with lets see if one of them globally times
259: // out earlier than this lock, if so we will wake up then to check again
260: Set conflicts = lock.getConflictingOwners(ownerId,
261: targetLockLevel, compatibility);
262: long nextConflictTimeout = getNextGlobalConflictTimeout(conflicts);
263: if (nextConflictTimeout != -1
264: && nextConflictTimeout < waitEnd) {
265: timeoutMSecs = nextConflictTimeout - now;
266: // XXX add 10% to ensure the lock really is timed out
267: timeoutMSecs += timeoutMSecs / 10;
268: } else {
269: timeoutMSecs = waitEnd - now;
270: }
271:
272: // XXX acquire will remove us as a waiter, but it is important to remain us such
273: // to constantly indicate it to other owners, otherwise there might be undetected
274: // deadlocks
275: synchronized (lock) {
276: acquired = lock.acquire(ownerId, targetLockLevel,
277: true, compatibility, preferred,
278: timeoutMSecs);
279: lock.registerWaiter(lockWaiter);
280: }
281: now = System.currentTimeMillis();
282: }
283: if (!acquired) {
284: throw new LockException("Lock wait timed out",
285: LockException.CODE_TIMED_OUT, resourceId);
286: } else {
287: addOwner(ownerId, lock);
288: }
289: } catch (InterruptedException e) {
290: throw new LockException("Interrupted",
291: LockException.CODE_INTERRUPTED, resourceId);
292: } finally {
293: lock.unregisterWaiter(lockWaiter);
294: }
295: }
296:
297: /**
298: * @see LockManager2#getLevel(Object, Object)
299: * @since 1.1
300: */
301: public int getLevel(Object ownerId, Object resourceId) {
302: timeoutCheck(ownerId);
303: GenericLock lock = (GenericLock) getLock(resourceId);
304: if (lock != null) {
305: return lock.getLockLevel(ownerId);
306: } else {
307: return 0;
308: }
309: }
310:
311: /**
312: * @see LockManager2#release(Object, Object)
313: * @since 1.1
314: */
315: public boolean release(Object ownerId, Object resourceId) {
316: timeoutCheck(ownerId);
317: boolean released = false;
318:
319: GenericLock lock = (GenericLock) getLock(resourceId);
320: if (lock != null) {
321: released = lock.release(ownerId);
322: removeOwner(ownerId, lock);
323: }
324: return released;
325: }
326:
327: /**
328: * @see LockManager2#releaseAll(Object)
329: * @since 1.1
330: */
331: public void releaseAll(Object ownerId) {
332: releaseAllNoTimeOutReset(ownerId);
333: // reset time out status for this owner
334: timedOutOwners.remove(ownerId);
335: effectiveGlobalTimeouts.remove(ownerId);
336: }
337:
338: protected void releaseAllNoTimeOutReset(Object ownerId) {
339: Set locks = (Set) globalOwners.get(ownerId);
340: if (locks != null) {
341: Collection locksCopy;
342: // need to copy in order not to interfere with wouldDeadlock
343: // possibly called by
344: // other threads
345: synchronized (locks) {
346: locksCopy = new ArrayList(locks);
347: }
348: for (Iterator it = locksCopy.iterator(); it.hasNext();) {
349: GenericLock lock = (GenericLock) it.next();
350: lock.release(ownerId);
351: locks.remove(lock);
352: }
353: }
354: }
355:
356: /**
357: * @see LockManager2#getAll(Object)
358: * @since 1.1
359: */
360: public Set getAll(Object ownerId) {
361: Set locks = (Set) globalOwners.get(ownerId);
362: if (locks == null) {
363: return new HashSet();
364: } else {
365: return locks;
366: }
367: }
368:
369: protected void addOwner(Object ownerId, GenericLock lock) {
370: synchronized (globalOwners) {
371: Set locks = (Set) globalOwners.get(ownerId);
372: if (locks == null) {
373: locks = Collections.synchronizedSet(new HashSet());
374: globalOwners.put(ownerId, locks);
375: }
376: locks.add(lock);
377: }
378: }
379:
380: protected void removeOwner(Object ownerId, GenericLock lock) {
381: Set locks = (Set) globalOwners.get(ownerId);
382: if (locks != null) {
383: locks.remove(lock);
384: }
385: }
386:
387: /**
388: * Checks if an owner is deadlocked. <br>
389: * <br>
390: * We traverse the tree recursively formed by owners, locks held by them and
391: * then again owners waiting for the locks. If there is a cycle in one of
392: * the paths from the root to a leaf we have a deadlock. <br>
393: * <br>
394: * A more detailed discussion on deadlocks and definitions and how to detect
395: * them can be found in <a
396: * href="http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html?page=1">this
397: * nice article </a>. <br>
398: * <em>Caution:</em> This computation can be very expensive with many
399: * owners and locks. Worst (unlikely) case is exponential.
400: *
401: * @param ownerId
402: * the owner to check for being deadlocked
403: * @param path
404: * initially should be called with an empty set
405: * @return <code>true</code> if the owner is deadlocked,
406: * <code>false</code> otherwise
407: */
408: protected boolean wouldDeadlock(Object ownerId, Set path) {
409: path.add(ownerId);
410: // these are our locks
411: Set locks = (Set) globalOwners.get(ownerId);
412: if (locks != null) {
413: Collection locksCopy;
414: // need to copy in order not to interfere with releaseAll possibly called by
415: // other threads
416: synchronized (locks) {
417: locksCopy = new ArrayList(locks);
418: }
419: for (Iterator i = locksCopy.iterator(); i.hasNext();) {
420: GenericLock mylock = (GenericLock) i.next();
421: // these are the ones waiting for one of our locks
422: Collection conflicts = mylock
423: .getConflictingWaiters(ownerId);
424: if (conflicts != null) {
425: for (Iterator j = conflicts.iterator(); j.hasNext();) {
426: Object waitingOwnerId = j.next();
427: if (path.contains(waitingOwnerId)) {
428: return true;
429: } else if (wouldDeadlock(waitingOwnerId, path)) {
430: return true;
431: }
432: }
433: }
434: }
435: }
436: path.remove(ownerId);
437: return false;
438: }
439:
440: protected boolean releaseTimedOutOwners() {
441: boolean released = false;
442: synchronized (effectiveGlobalTimeouts) {
443: for (Iterator it = effectiveGlobalTimeouts.entrySet()
444: .iterator(); it.hasNext();) {
445: Map.Entry entry = (Map.Entry) it.next();
446: Object ownerId = entry.getKey();
447: long timeout = ((Long) entry.getValue()).longValue();
448: long now = System.currentTimeMillis();
449: if (timeout < now) {
450: releaseAllNoTimeOutReset(ownerId);
451: timedOutOwners.add(ownerId);
452: released = true;
453: }
454: }
455: }
456: return released;
457: }
458:
459: protected boolean timeOut(Object ownerId) {
460: Long timeout = (Long) effectiveGlobalTimeouts.get(ownerId);
461: long now = System.currentTimeMillis();
462: if (timeout != null && timeout.longValue() < now) {
463: releaseAll(ownerId);
464: timedOutOwners.add(ownerId);
465: return true;
466: } else {
467: return false;
468: }
469: }
470:
471: protected long getNextGlobalConflictTimeout(Set conflicts) {
472: long minTimeout = -1;
473: long now = System.currentTimeMillis();
474: if (conflicts != null) {
475: synchronized (effectiveGlobalTimeouts) {
476: for (Iterator it = effectiveGlobalTimeouts.entrySet()
477: .iterator(); it.hasNext();) {
478: Map.Entry entry = (Map.Entry) it.next();
479: Object ownerId = entry.getKey();
480: if (conflicts.contains(ownerId)) {
481: long timeout = ((Long) entry.getValue())
482: .longValue();
483: if (minTimeout == -1 || timeout < minTimeout) {
484: minTimeout = timeout;
485: }
486: }
487: }
488: }
489: }
490: return minTimeout;
491: }
492:
493: public MultiLevelLock getLock(Object resourceId) {
494: synchronized (globalLocks) {
495: return (MultiLevelLock) globalLocks.get(resourceId);
496: }
497: }
498:
499: public MultiLevelLock atomicGetOrCreateLock(Object resourceId) {
500: synchronized (globalLocks) {
501: MultiLevelLock lock = getLock(resourceId);
502: if (lock == null) {
503: lock = createLock(resourceId);
504: }
505: return lock;
506: }
507: }
508:
509: public void removeLock(MultiLevelLock lock) {
510: synchronized (globalLocks) {
511: globalLocks.remove(lock);
512: }
513: }
514:
515: /**
516: * Gets all locks as orignials, <em>no copies</em>.
517: *
518: * @return collection holding all locks.
519: */
520: public Collection getLocks() {
521: synchronized (globalLocks) {
522: return globalLocks.values();
523: }
524: }
525:
526: public synchronized String toString() {
527: StringBuffer buf = new StringBuffer(1000);
528: for (Iterator it = globalLocks.values().iterator(); it
529: .hasNext();) {
530: GenericLock lock = (GenericLock) it.next();
531: buf.append(lock.toString()).append('\n');
532: }
533: return buf.toString();
534: }
535:
536: protected GenericLock createLock(Object resourceId) {
537: synchronized (globalLocks) {
538: GenericLock lock = new GenericLock(resourceId,
539: maxLockLevel, logger);
540: globalLocks.put(resourceId, lock);
541: return lock;
542: }
543: }
544:
545: protected void timeoutCheck(Object ownerId) throws LockException {
546: timeOut(ownerId);
547: if (timedOutOwners.contains(ownerId)) {
548: throw new LockException(
549: "All locks of owner "
550: + ownerId
551: + " have globally timed out."
552: + " You will not be able to to continue with this owner until you call releaseAll.",
553: LockException.CODE_TIMED_OUT, null);
554: }
555: }
556:
557: }
|