1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
126
127
128 protected Map owners = Collections.synchronizedMap(new HashMap());
129
130
131
132
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
274 LockOwner oldLock = null;
275 try {
276
277 oldLock = (LockOwner) owners.get(ownerId);
278
279
280 setLockLevel(ownerId, null, targetLockLevel, compatibility,
281 preferred);
282
283
284 wait(remaining);
285
286 } finally {
287
288
289
290
291
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
445
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
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
493 LockOwner highestOwner;
494 if (compatibility == COMPATIBILITY_REENTRANT) {
495 if (myLock != null && targetLockLevel <= myLock.lockLevel) {
496
497 return true;
498 } else {
499
500 highestOwner = getMaxLevelOwner(myLock, preferred);
501 }
502 } else if (compatibility == COMPATIBILITY_SUPPORT) {
503
504
505 highestOwner = getMaxLevelOwner(targetLockLevel, preferred);
506
507 } else if (compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT) {
508 if (myLock != null && targetLockLevel <= myLock.lockLevel) {
509
510 return true;
511 } else {
512
513 highestOwner = getMaxLevelOwner(myLock, targetLockLevel, preferred);
514 }
515 } else {
516 highestOwner = getMaxLevelOwner();
517 }
518
519
520 int currentLockLevel;
521 if (highestOwner != null) {
522 currentLockLevel = highestOwner.lockLevel;
523 } else {
524 currentLockLevel = getLevelMinLock();
525 }
526
527
528 if (isCompatible(targetLockLevel, currentLockLevel)) {
529 if (!tryOnly) {
530
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
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
580 for (Iterator it = ownersToTest.iterator(); it.hasNext();) {
581 LockOwner owner = (LockOwner) it.next();
582
583
584 if ((myOwner.compatibility == COMPATIBILITY_REENTRANT || myOwner.compatibility == COMPATIBILITY_REENTRANT_AND_SUPPORT)
585 && owner.ownerId.equals(myOwner.ownerId))
586 continue;
587
588
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 }