GenericLock


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