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