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 545634 2007-06-08 21:36:59Z ozeigermann $
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.synchronizedMap(new HashMap());
047
048 /** Maps resourceId to lock. */
049 protected Map globalLocks = new HashMap();
050
051 /** Maps onwerId to global effective time outs (i.e. the time the lock will time out). */
052 protected Map effectiveGlobalTimeouts = Collections.synchronizedMap(new HashMap());
053
054 protected Set timedOutOwners = Collections.synchronizedSet(new HashSet());
055
056 protected int maxLockLevel = -1;
057 protected LoggerFacade logger;
058 protected long globalTimeoutMSecs;
059 protected long checkThreshhold;
060
061 /**
062 * Creates a new generic lock manager.
063 *
064 * @param maxLockLevel
065 * highest allowed lock level as described in {@link GenericLock}
066 * 's class intro
067 * @param logger
068 * generic logger used for all kind of debug logging
069 * @param timeoutMSecs
070 * specifies the maximum time to wait for a lock in milliseconds
071 * @param checkThreshholdMSecs
072 * specifies a special wait threshhold before deadlock and
073 * timeout detection come into play or <code>-1</code> switch
074 * it off and check for directly
075 * @throws IllegalArgumentException
076 * if maxLockLevel is less than 1
077 *
078 * @since 1.1
079 */
080 public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs,
081 long checkThreshholdMSecs) throws IllegalArgumentException {
082 if (maxLockLevel < 1)
083 throw new IllegalArgumentException("The maximum lock level must be at least 1 ("
084 + maxLockLevel + " was specified)");
085 this.maxLockLevel = maxLockLevel;
086 this.logger = logger.createLogger("Locking");
087 this.globalTimeoutMSecs = timeoutMSecs;
088 this.checkThreshhold = checkThreshholdMSecs;
089 }
090
091 public GenericLockManager(int maxLockLevel, LoggerFacade logger, long timeoutMSecs)
092 throws IllegalArgumentException {
093 this(maxLockLevel, logger, timeoutMSecs, DEFAULT_CHECK_THRESHHOLD);
094 }
095
096 public GenericLockManager(int maxLockLevel, LoggerFacade logger)
097 throws IllegalArgumentException {
098 this(maxLockLevel, logger, DEFAULT_TIMEOUT);
099 }
100
101 /**
102 * @see LockManager2#startGlobalTimeout(Object, long)
103 * @since 1.1
104 */
105 public void startGlobalTimeout(Object ownerId, long timeoutMSecs) {
106 long now = System.currentTimeMillis();
107 long timeout = now + timeoutMSecs;
108 effectiveGlobalTimeouts.put(ownerId, new Long(timeout));
109 }
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 timeoutCheck(ownerId);
117
118 GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
119 boolean acquired = lock.tryLock(ownerId, targetLockLevel,
120 reentrant ? GenericLock.COMPATIBILITY_REENTRANT : GenericLock.COMPATIBILITY_NONE,
121 false);
122
123 if (acquired) {
124 addOwner(ownerId, lock);
125 }
126 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 timeoutCheck(ownerId);
135 boolean possible = true;
136
137 GenericLock lock = (GenericLock) getLock(resourceId);
138 if (lock != null) {
139 possible = lock.test(ownerId, targetLockLevel,
140 reentrant ? GenericLock.COMPATIBILITY_REENTRANT
141 : GenericLock.COMPATIBILITY_NONE);
142 }
143 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 timeoutCheck(ownerId);
152 boolean owned = false;
153
154 GenericLock lock = (GenericLock) getLock(resourceId);
155 if (lock != null) {
156 owned = lock.has(ownerId, lockLevel);
157 }
158 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 lock(ownerId, resourceId, targetLockLevel, reentrant, globalTimeoutMSecs);
168 }
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 lock(ownerId, resourceId, targetLockLevel, reentrant ? GenericLock.COMPATIBILITY_REENTRANT
177 : GenericLock.COMPATIBILITY_NONE, false, timeoutMSecs);
178 }
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 timeoutCheck(ownerId);
187 GenericLock lock = (GenericLock) atomicGetOrCreateLock(resourceId);
188 doLock(lock, ownerId, resourceId, targetLockLevel, compatibility, preferred, timeoutMSecs);
189 }
190
191 protected void doLock(GenericLock lock, Object ownerId, Object resourceId, int targetLockLevel,
192 int compatibility, boolean preferred, long timeoutMSecs)
193 {
194 long now = System.currentTimeMillis();
195 long waitEnd = now + timeoutMSecs;
196
197 timeoutCheck(ownerId);
198
199 GenericLock.LockOwner lockWaiter = new GenericLock.LockOwner(ownerId, targetLockLevel,
200 compatibility, preferred);
201
202 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 if (checkThreshhold != -1 && timeoutMSecs > checkThreshhold) {
210 acquired = lock
211 .acquire(ownerId, targetLockLevel, true, compatibility,
212 preferred, checkThreshhold);
213 timeoutMSecs -= checkThreshhold;
214 } else {
215 acquired = lock
216 .acquire(ownerId, targetLockLevel, false, compatibility,
217 preferred, checkThreshhold);
218
219 }
220 if (acquired) {
221 addOwner(ownerId, lock);
222 return;
223 }
224 } catch (InterruptedException e) {
225 throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
226 }
227 try {
228 lock.registerWaiter(lockWaiter);
229
230 boolean deadlock = wouldDeadlock(ownerId, new HashSet());
231 if (deadlock) {
232 throw new LockException("Lock would cause deadlock",
233 LockException.CODE_DEADLOCK_VICTIM, resourceId);
234 }
235
236 now = System.currentTimeMillis();
237 while (!acquired && waitEnd > now) {
238
239 // first be sure all locks are stolen from owners that have already timed out
240 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 Set conflicts = lock.getConflictingOwners(ownerId, targetLockLevel, compatibility);
245 long nextConflictTimeout = getNextGlobalConflictTimeout(conflicts);
246 if (nextConflictTimeout != -1 && nextConflictTimeout < waitEnd) {
247 timeoutMSecs = nextConflictTimeout - now;
248 // XXX add 10% to ensure the lock really is timed out
249 timeoutMSecs += timeoutMSecs / 10;
250 } else {
251 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 synchronized (lock) {
258 acquired = lock.acquire(ownerId, targetLockLevel, true, compatibility,
259 preferred, timeoutMSecs);
260 lock.registerWaiter(lockWaiter);
261 }
262 now = System.currentTimeMillis();
263 }
264 if (!acquired) {
265 throw new LockException("Lock wait timed out", LockException.CODE_TIMED_OUT,
266 resourceId);
267 } else {
268 addOwner(ownerId, lock);
269 }
270 } catch (InterruptedException e) {
271 throw new LockException("Interrupted", LockException.CODE_INTERRUPTED, resourceId);
272 } finally {
273 lock.unregisterWaiter(lockWaiter);
274 }
275 }
276
277 /**
278 * @see LockManager2#getLevel(Object, Object)
279 * @since 1.1
280 */
281 public int getLevel(Object ownerId, Object resourceId) {
282 timeoutCheck(ownerId);
283 GenericLock lock = (GenericLock) getLock(resourceId);
284 if (lock != null) {
285 return lock.getLockLevel(ownerId);
286 } else {
287 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 timeoutCheck(ownerId);
297 boolean released = false;
298
299 GenericLock lock = (GenericLock) getLock(resourceId);
300 if (lock != null) {
301 released = lock.release(ownerId);
302 removeOwner(ownerId, lock);
303 }
304 return released;
305 }
306
307 /**
308 * @see LockManager2#releaseAll(Object)
309 * @since 1.1
310 */
311 public void releaseAll(Object ownerId) {
312 releaseAllNoTimeOutReset(ownerId);
313 // reset time out status for this owner
314 timedOutOwners.remove(ownerId);
315 effectiveGlobalTimeouts.remove(ownerId);
316 }
317
318 protected void releaseAllNoTimeOutReset(Object ownerId) {
319 Set locks = (Set) globalOwners.get(ownerId);
320 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 synchronized (locks) {
326 locksCopy = new ArrayList(locks);
327 }
328 for (Iterator it = locksCopy.iterator(); it.hasNext();) {
329 GenericLock lock = (GenericLock) it.next();
330 lock.release(ownerId);
331 locks.remove(lock);
332 }
333 }
334 removeOwnerWithoutLocks(ownerId);
335 }
336
337 /**
338 * @see LockManager2#getAll(Object)
339 * @since 1.1
340 */
341 public Set getAll(Object ownerId) {
342 Set locks = (Set) globalOwners.get(ownerId);
343 if (locks == null) {
344 return new HashSet();
345 } else {
346 return locks;
347 }
348 }
349
350 protected void addOwner(Object ownerId, GenericLock lock) {
351 synchronized (globalOwners) {
352 Set locks = (Set) globalOwners.get(ownerId);
353 if (locks == null) {
354 locks = Collections.synchronizedSet(new HashSet());
355 globalOwners.put(ownerId, locks);
356 }
357 locks.add(lock);
358 }
359 }
360
361 protected void removeOwner(Object ownerId, GenericLock lock) {
362 Set locks = (Set) globalOwners.get(ownerId);
363 if (locks != null) {
364 locks.remove(lock);
365 }
366 removeOwnerWithoutLocks(ownerId);
367 }
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 path.add(ownerId);
392 // these are our locks
393 Set locks = (Set) globalOwners.get(ownerId);
394 if (locks != null) {
395 Collection locksCopy;
396 // need to copy in order not to interfere with releaseAll possibly called by
397 // other threads
398 synchronized (locks) {
399 locksCopy = new ArrayList(locks);
400 }
401 for (Iterator i = locksCopy.iterator(); i.hasNext();) {
402 GenericLock mylock = (GenericLock) i.next();
403 // these are the ones waiting for one of our locks
404 Collection conflicts = mylock.getConflictingWaiters(ownerId);
405 if (conflicts != null) {
406 for (Iterator j = conflicts.iterator(); j.hasNext();) {
407 Object waitingOwnerId = j.next();
408 if (path.contains(waitingOwnerId)) {
409 return true;
410 } else if (wouldDeadlock(waitingOwnerId, path)) {
411 return true;
412 }
413 }
414 }
415 }
416 }
417 path.remove(ownerId);
418 return false;
419 }
420
421 protected boolean releaseTimedOutOwners() {
422 boolean released = false;
423 synchronized (effectiveGlobalTimeouts) {
424 for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
425 Map.Entry entry = (Map.Entry) it.next();
426 Object ownerId = entry.getKey();
427 long timeout = ((Long) entry.getValue()).longValue();
428 long now = System.currentTimeMillis();
429 if (timeout < now) {
430 releaseAllNoTimeOutReset(ownerId);
431 timedOutOwners.add(ownerId);
432 released = true;
433 }
434 }
435 }
436 return released;
437 }
438
439 protected boolean timeOut(Object ownerId) {
440 Long timeout = (Long)effectiveGlobalTimeouts.get(ownerId);
441 long now = System.currentTimeMillis();
442 if (timeout != null && timeout.longValue() < now) {
443 releaseAll(ownerId);
444 timedOutOwners.add(ownerId);
445 return true;
446 } else {
447 return false;
448 }
449 }
450
451 protected long getNextGlobalConflictTimeout(Set conflicts) {
452 long minTimeout = -1;
453 long now = System.currentTimeMillis();
454 if (conflicts != null) {
455 synchronized (effectiveGlobalTimeouts) {
456 for (Iterator it = effectiveGlobalTimeouts.entrySet().iterator(); it.hasNext();) {
457 Map.Entry entry = (Map.Entry) it.next();
458 Object ownerId = entry.getKey();
459 if (conflicts.contains(ownerId)) {
460 long timeout = ((Long) entry.getValue()).longValue();
461 if (minTimeout == -1 || timeout < minTimeout) {
462 minTimeout = timeout;
463 }
464 }
465 }
466 }
467 }
468 return minTimeout;
469 }
470
471 public MultiLevelLock getLock(Object resourceId) {
472 synchronized (globalLocks) {
473 return (MultiLevelLock) globalLocks.get(resourceId);
474 }
475 }
476
477 public MultiLevelLock atomicGetOrCreateLock(Object resourceId) {
478 synchronized (globalLocks) {
479 MultiLevelLock lock = getLock(resourceId);
480 if (lock == null) {
481 lock = createLock(resourceId);
482 }
483 return lock;
484 }
485 }
486
487 public void removeLock(MultiLevelLock lock) {
488 synchronized (globalLocks) {
489 globalLocks.remove(lock);
490 }
491 }
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 synchronized (globalLocks) {
500 return globalLocks.values();
501 }
502 }
503
504 public synchronized String toString() {
505 StringBuffer buf = new StringBuffer(1000);
506 for (Iterator it = globalLocks.values().iterator(); it.hasNext();) {
507 GenericLock lock = (GenericLock) it.next();
508 buf.append(lock.toString()).append('\n');
509 }
510 return buf.toString();
511 }
512
513 protected GenericLock createLock(Object resourceId) {
514 synchronized (globalLocks) {
515 GenericLock lock = new GenericLock(resourceId, maxLockLevel, logger);
516 globalLocks.put(resourceId, lock);
517 return lock;
518 }
519 }
520
521 protected void timeoutCheck(Object ownerId) throws LockException {
522 timeOut(ownerId);
523 if (timedOutOwners.contains(ownerId)) {
524 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 }
532
533 protected void removeOwnerWithoutLocks(Object ownerId) {
534 synchronized (globalOwners) {
535 Set locks = (Set) globalOwners.get(ownerId);
536 if (locks == null || locks.isEmpty()) {
537 globalOwners.remove(ownerId);
538 }
539 }
540 }
541 }