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.synchronizedList(new ArrayList());
131 private int maxLockLevel;
132 protected LoggerFacade logger;
133 protected int waiters = 0;
134
135 /**
136 * Creates a new lock.
137 *
138 * @param resourceId identifier for the resource associated to this lock
139 * @param maxLockLevel highest allowed lock level as described in class intro
140 * @param logger generic logger used for all kind of debug logging
141 */
142 public GenericLock(Object resourceId, int maxLockLevel, LoggerFacade logger) {
143 if (maxLockLevel < 1)
144 throw new IllegalArgumentException(
145 "The maximum lock level must be at least 1 (" + maxLockLevel + " was specified)");
146 this.resourceId = resourceId;
147 this.maxLockLevel = maxLockLevel;
148 this.logger = logger;
149 }
150
151 public boolean equals(Object o) {
152 if (o instanceof GenericLock) {
153 return ((GenericLock)o).resourceId.equals(resourceId);
154 }
155 return false;
156 }
157
158 public int hashCode() {
159 return resourceId.hashCode();
160 }
161
162 /**
163 * @see MultiLevelLock2#test(Object, int, int)
164 */
165 public boolean test(Object ownerId, int targetLockLevel, int compatibility) {
166 boolean success = tryLock(ownerId, targetLockLevel, compatibility, false, true);
167 return success;
168 }
169
170 /**
171 * @see MultiLevelLock2#has(Object, int)
172 */
173 public boolean has(Object ownerId, int lockLevel) {
174 int level = getLockLevel(ownerId);
175 return (lockLevel <= level);
176 }
177
178 /**
179 * @see org.apache.commons.transaction.locking.MultiLevelLock#acquire(java.lang.Object,
180 * int, boolean, boolean, long)
181 */
182 public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
183 boolean reentrant, long timeoutMSecs) throws InterruptedException {
184 return acquire(ownerId, targetLockLevel, wait, reentrant ? COMPATIBILITY_REENTRANT
185 : COMPATIBILITY_NONE, timeoutMSecs);
186 }
187
188 /**
189 * @see #acquire(Object, int, boolean, int, boolean, long)
190 */
191 public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean wait,
192 int compatibility, long timeoutMSecs) throws InterruptedException {
193 return acquire(ownerId, targetLockLevel, wait, compatibility, false, timeoutMSecs);
194 }
195
196 /**
197 * Tries to blockingly acquire a lock which can be preferred.
198 *
199 * @see #acquire(Object, int, boolean, int, boolean, long)
200 * @since 1.1
201 */
202 public synchronized boolean acquire(Object ownerId, int targetLockLevel, boolean preferred,
203 long timeoutMSecs) throws InterruptedException {
204 return acquire(ownerId, targetLockLevel, true, COMPATIBILITY_REENTRANT, preferred,
205 timeoutMSecs);
206 }
207
208 /**
209 * @see org.apache.commons.transaction.locking.MultiLevelLock2#acquire(Object,
210 * int, boolean, int, boolean, long)
211 * @since 1.1
212 */
213 public synchronized boolean acquire(
214 Object ownerId,
215 int targetLockLevel,
216 boolean wait,
217 int compatibility,
218 boolean preferred,
219 long timeoutMSecs)
220 throws InterruptedException {
221
222 if (logger.isFinerEnabled()) {
223 logger.logFiner(
224 ownerId.toString()
225 + " trying to acquire lock for "
226 + resourceId.toString()
227 + " at level "
228 + targetLockLevel
229 + " at "
230 + System.currentTimeMillis());
231 }
232
233 if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
234
235 if (logger.isFinerEnabled()) {
236 logger.logFiner(
237 ownerId.toString()
238 + " actually acquired lock for "
239 + resourceId.toString()
240 + " at "
241 + System.currentTimeMillis());
242 }
243
244 return true;
245 } else {
246 if (!wait) {
247 return false;
248 } else {
249 long started = System.currentTimeMillis();
250 for (long remaining = timeoutMSecs;
251 remaining > 0;
252 remaining = timeoutMSecs - (System.currentTimeMillis() - started)) {
253
254 if (logger.isFinerEnabled()) {
255 logger.logFiner(
256 ownerId.toString()
257 + " waiting on "
258 + resourceId.toString()
259 + " for msecs "
260 + timeoutMSecs
261 + " at "
262 + System.currentTimeMillis());
263 }
264
265 LockOwner waitingOwner = new LockOwner(ownerId, targetLockLevel, compatibility,
266 preferred);
267 try {
268 registerWaiter(waitingOwner);
269 if (preferred) {
270 // while waiting we already make our claim we are next
271 LockOwner oldLock = null;
272 try {
273 // we need to remember it to restore it after waiting
274 oldLock = (LockOwner) owners.get(ownerId);
275 // this creates a new owner, so we do not need to
276 // copy the old one
277 setLockLevel(ownerId, null, targetLockLevel, compatibility,
278 preferred);
279
280 // finally wait
281 wait(remaining);
282
283 } finally {
284 // we need to restore the old lock in order not to
285 // interfere with the intention lock in the
286 // following check
287 // and not to have it in case of success either
288 // as there will be an ordinary lock then
289 if (oldLock != null) {
290 owners.put(ownerId, oldLock);
291 } else {
292 owners.remove(ownerId);
293 }
294 }
295
296 } else {
297 wait(remaining);
298 }
299 } finally {
300 unregisterWaiter(waitingOwner);
301 }
302
303 if (tryLock(ownerId, targetLockLevel, compatibility, preferred)) {
304
305 if (logger.isFinerEnabled()) {
306 logger.logFiner(
307 ownerId.toString()
308 + " waiting on "
309 + resourceId.toString()
310 + " eventually got the lock at "
311 + System.currentTimeMillis());
312 }
313
314 return true;
315 }
316 }
317 return false;
318 }
319 }
320 }
321
322 protected void registerWaiter(LockOwner waitingOwner) {
323 synchronized (waitingOwners) {
324 unregisterWaiter(waitingOwner);
325 waiters++;
326 waitingOwners.add(waitingOwner);
327 }
328 }
329
330 protected void unregisterWaiter(LockOwner waitingOwner) {
331 synchronized (waitingOwners) {
332 if (waitingOwners.remove(waitingOwner))
333 waiters--;
334 }
335 }
336
337 /**
338 * @see org.apache.commons.transaction.locking.MultiLevelLock#release(Object)
339 */
340 public synchronized boolean release(Object ownerId) {
341 if (owners.remove(ownerId) != null) {
342 if (logger.isFinerEnabled()) {
343 logger.logFiner(
344 ownerId.toString()
345 + " releasing lock for "
346 + resourceId.toString()
347 + " at "
348 + System.currentTimeMillis());
349 }
350 notifyAll();
351 return true;
352 }
353 return false;
354 }
355
356 /**
357 * @see org.apache.commons.transaction.locking.MultiLevelLock#getLockLevel(Object)
358 */
359 public int getLockLevel(Object ownerId) {
360 LockOwner owner = (LockOwner) owners.get(ownerId);
361 if (owner == null) {
362 return 0;
363 } else {
364 return owner.lockLevel;
365 }
366 }
367
368 /**
369 * Gets the resource assotiated to this lock.
370 *
371 * @return identifier for the resource associated to this lock
372 */
373 public Object getResourceId() {
374 return resourceId;
375 }
376
377 /**
378 * Gets the lowest lock level possible.
379 *
380 * @return minimum lock level
381 */
382 public int getLevelMinLock() {
383 return 0;
384 }
385
386 /**
387 * Gets the highst lock level possible.
388 *
389 * @return maximum lock level
390 */
391 public int getLevelMaxLock() {
392 return maxLockLevel;
393 }
394
395 public Object getOwner() {
396 LockOwner owner = getMaxLevelOwner();
397 if (owner == null)
398 return null;
399 return owner.ownerId;
400 }
401
402 public synchronized String toString() {
403 StringBuffer buf = new StringBuffer();
404 buf.append(resourceId.toString()).append(":\n");
405
406 for (Iterator it = owners.values().iterator(); it.hasNext();) {
407 LockOwner owner = (LockOwner) it.next();
408 buf.append("- ").append(owner.toString()).append("\n");
409 }
410
411 if (waiters != 0) {
412 buf.append(waiters).append(" waiting:\n");
413 for (Iterator it = waitingOwners.iterator(); it.hasNext();) {
414 LockOwner owner = (LockOwner) it.next();
415 buf.append("- ").append(owner.toString()).append("\n");
416 }
417 }
418
419 return buf.toString();
420 }
421
422 protected synchronized LockOwner getMaxLevelOwner() {
423 return getMaxLevelOwner(null, -1, false);
424 }
425
426 protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner, boolean preferred) {
427 return getMaxLevelOwner(reentrantOwner, -1, preferred);
428 }
429
430 protected synchronized LockOwner getMaxLevelOwner(int supportLockLevel, boolean preferred) {
431 return getMaxLevelOwner(null, supportLockLevel, preferred);
432 }
433
434 protected synchronized LockOwner getMaxLevelOwner(LockOwner reentrantOwner,
435 int supportLockLevel, 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 && !owner.equals(reentrantOwner)
440 && (maxOwner == null || maxOwner.lockLevel < owner.lockLevel)
441 // if we are a preferred lock we must not interfere with other intention
442 // locks as we otherwise might mututally lock without resolvation
443 && !(preferred && owner.intention)) {
444 maxOwner = owner;
445 }
446 }
447 return maxOwner;
448 }
449
450 protected synchronized void setLockLevel(Object ownerId, LockOwner lock, int targetLockLevel,
451 int compatibility, boolean intention) {
452 // be sure there exists at most one lock per owner
453 if (lock != null) {
454 if (logger.isFinestEnabled()) {
455 logger.logFinest(
456 ownerId.toString()
457 + " upgrading lock for "
458 + resourceId.toString()
459 + " to level "
460 + targetLockLevel
461 + " at "
462 + System.currentTimeMillis());
463 }
464 } else {
465 if (logger.isFinestEnabled()) {
466 logger.logFinest(
467 ownerId.toString()
468 + " getting new lock for "
469 + resourceId.toString()
470 + " at level "
471 + targetLockLevel
472 + " at "
473 + System.currentTimeMillis());
474 }
475 }
476 owners.put(ownerId, new LockOwner(ownerId, targetLockLevel, compatibility, intention));
477 }
478
479 protected boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
480 boolean preferred) {
481 return tryLock(ownerId, targetLockLevel, compatibility, preferred, false);
482 }
483
484 protected synchronized boolean tryLock(Object ownerId, int targetLockLevel, int compatibility,
485 boolean preferred, boolean tryOnly) {
486
487 LockOwner myLock = (LockOwner) owners.get(ownerId);
488
489 // determine highest owner
490 LockOwner highestOwner;
491 if (compatibility == COMPATIBILITY_REENTRANT) {
492 if (myLock != null && targetLockLevel <= myLock.lockLevel) {
493 // we already have it
494 return true;
495 } else {
496 // our own lock will not be compromised by ourself
497 highestOwner = getMaxLevelOwner(myLock, preferred);
498 }
499 } else if (compatibility == COMPATIBILITY_SUPPORT) {
500 // we are compatible with any other lock owner holding
501 // the same lock level
502 highestOwner = getMaxLevelOwner(targetLockLevel, preferred);
503
504 } else if (compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT) {
505 if (myLock != null && targetLockLevel <= myLock.lockLevel) {
506 // we already have it
507 return true;
508 } else {
509 // our own lock will not be compromised by ourself and same lock level
510 highestOwner = getMaxLevelOwner(myLock, 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, compatibility, false);
530 }
531 return true;
532 } else {
533 return false;
534 }
535 }
536
537 protected boolean isCompatible(int targetLockLevel, int currentLockLevel) {
538 return (targetLockLevel <= getLevelMaxLock() - currentLockLevel);
539 }
540
541 protected Set getConflictingOwners(Object ownerId, int targetLockLevel, int compatibility) {
542
543 LockOwner myLock = (LockOwner) owners.get(ownerId);
544 if (myLock != null && targetLockLevel <= myLock.lockLevel) {
545 // shortcut as we already have the lock
546 return null;
547 }
548
549 LockOwner testLock = new LockOwner(ownerId, targetLockLevel, compatibility, false);
550 List ownersCopy;
551 synchronized (owners) {
552 ownersCopy = new ArrayList(owners.values());
553 }
554 return getConflictingOwners(testLock, ownersCopy);
555
556 }
557
558 protected Collection getConflictingWaiters(Object ownerId) {
559 LockOwner owner = (LockOwner) owners.get(ownerId);
560 if (owner != null) {
561 List waiterCopy;
562 synchronized (waitingOwners) {
563 waiterCopy = new ArrayList(waitingOwners);
564 }
565 Collection conflicts = getConflictingOwners(owner, waiterCopy);
566 return conflicts;
567 }
568 return null;
569 }
570
571 protected Set getConflictingOwners(LockOwner myOwner, Collection ownersToTest) {
572
573 if (myOwner == null) return null;
574
575 Set conflicts = new HashSet();
576
577 // check if any locks conflict with ours
578 for (Iterator it = ownersToTest.iterator(); it.hasNext();) {
579 LockOwner owner = (LockOwner) it.next();
580
581 // we do not interfere with ourselves, except when explicitely said so
582 if ((myOwner.compatibility == COMPATIBILITY_REENTRANT || myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT)
583 && owner.ownerId.equals(myOwner.ownerId))
584 continue;
585
586 // otherwise find out the lock level of the owner and see if we conflict with it
587 int onwerLockLevel = owner.lockLevel;
588
589 if (myOwner.compatibility == COMPATIBILITY_SUPPORT
590 || myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT
591 && myOwner.lockLevel == onwerLockLevel)
592 continue;
593
594 if (!isCompatible(myOwner.lockLevel, onwerLockLevel)) {
595 conflicts.add(owner.ownerId);
596 }
597 }
598 return (conflicts.isEmpty() ? null : conflicts);
599 }
600
601 protected static class LockOwner {
602 public final Object ownerId;
603 public final int lockLevel;
604 public final boolean intention;
605 public final int compatibility;
606
607 public LockOwner(Object ownerId, int lockLevel, int compatibility, boolean intention) {
608 this.ownerId = ownerId;
609 this.lockLevel = lockLevel;
610 this.intention = intention;
611 this.compatibility = compatibility;
612 }
613
614 public String toString() {
615 StringBuffer buf = new StringBuffer();
616 buf.append(ownerId.toString()).append(": level ").append(lockLevel).append(", complevel ")
617 .append(compatibility).append(intention ? ", intention/preferred" : "");
618 return buf.toString();
619 }
620
621 public boolean equals(Object o) {
622 if (o instanceof LockOwner) {
623 return ((LockOwner)o).ownerId.equals(ownerId);
624 }
625 return false;
626 }
627
628 public int hashCode() {
629 return ownerId.hashCode();
630 }
631 }
632
633 }