GenericLockManager


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