View Javadoc

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