001: /*
002:
003: Derby - Class org.apache.derby.impl.services.locks.LockSet
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.services.locks;
023:
024: import org.apache.derby.iapi.services.locks.Latch;
025: import org.apache.derby.iapi.services.locks.Lockable;
026: import org.apache.derby.iapi.services.locks.C_LockFactory;
027: import org.apache.derby.iapi.services.monitor.Monitor;
028:
029: import org.apache.derby.iapi.error.StandardException;
030:
031: import org.apache.derby.iapi.services.sanity.SanityManager;
032: import org.apache.derby.iapi.services.diag.DiagnosticUtil;
033:
034: import org.apache.derby.iapi.reference.Property;
035: import org.apache.derby.iapi.reference.SQLState;
036:
037: import java.util.Hashtable;
038: import java.util.Enumeration;
039:
040: /**
041: A LockSet is a complete lock table. A lock table is a hash table
042: keyed by a Lockable and with a LockControl as the data element.
043:
044: <P>
045: A LockControl contains information about the locks held on a Lockable.
046:
047: <BR>
048: MT - Mutable - Container Object : Thread Safe
049:
050: <BR>
051: The Hashtable we extend is synchronized on this, all addition, searching of
052: the hashtable is performed using java synchroization(this).
053: <BR>
054: The class creates ActiveLock and LockControl objects.
055:
056: LockControl objects are never passed out of this class, All the methods of
057: LockControl are called while being synchronized on this, thus providing the
058: single threading that LockControl required.
059:
060: Methods of Lockables are only called by this class or LockControl, and
061: always while being synchronized on this, thus providing the single
062: threading that Lockable requires.
063:
064: @see LockControl
065: */
066:
067: public final class LockSet extends Hashtable {
068: /*
069: ** Fields
070: */
071: private final SinglePool factory;
072:
073: /**
074: Timeout for deadlocks, in ms.
075: <BR>
076: MT - immutable
077: */
078: protected int deadlockTimeout = Property.DEADLOCK_TIMEOUT_DEFAULT * 1000;
079: protected int waitTimeout = Property.WAIT_TIMEOUT_DEFAULT * 1000;
080:
081: //EXCLUDE-START-lockdiag-
082:
083: // this varible is set and get without synchronization.
084: // Only one thread should be setting it at one time.
085: private boolean deadlockTrace;
086:
087: private Hashtable lockTraces; // rather than burden each lock with
088: // its stack trace, keep a look aside table
089: // that maps a lock to a stack trace
090: //EXCLUDE-END-lockdiag-
091:
092: // The number of waiters for locks
093: protected int blockCount;
094:
095: /*
096: ** Constructor
097: */
098:
099: protected LockSet(SinglePool factory) {
100: super ();
101: this .factory = factory;
102: }
103:
104: /*
105: ** Public Methods
106: */
107:
108: /**
109: * Lock an object within a specific compatibility space.
110: *
111: * @param compatabilitySpace Compatibility space.
112: * @param ref Lockable reference.
113: * @param qualifier Qualifier.
114: * @param timeout Timeout in milli-seconds
115: *
116: * @return Object that represents the lock.
117: *
118: * @exception StandardException Standard Cloudscape policy.
119:
120: */
121: public Lock lockObject(Object compatabilitySpace, Lockable ref,
122: Object qualifier, int timeout, Latch latch)
123: throws StandardException {
124: if (SanityManager.DEBUG) {
125:
126: if (SanityManager.DEBUG_ON("memoryLeakTrace")) {
127:
128: if (size() > 1000)
129: System.out.println("memoryLeakTrace:LockSet: "
130: + size());
131: }
132: }
133:
134: Control gc;
135: LockControl control;
136: Lock lockItem;
137: String lockDebug = null;
138:
139: synchronized (this ) {
140:
141: gc = getControl(ref);
142:
143: if (gc == null) {
144:
145: // object is not locked, can be granted
146: Lock gl = new Lock(compatabilitySpace, ref, qualifier);
147:
148: gl.grant();
149:
150: put(ref, gl);
151:
152: return gl;
153: }
154:
155: control = gc.getLockControl();
156: if (control != gc) {
157: put(ref, control);
158: }
159:
160: if (SanityManager.DEBUG) {
161: SanityManager.ASSERT(ref.equals(control.getLockable()));
162:
163: // ASSERT item is in the list
164: if (getControl(control.getLockable()) != control) {
165: SanityManager
166: .THROWASSERT("lockObject mismatched lock items "
167: + getControl(control.getLockable())
168: + " " + control);
169: }
170: }
171:
172: lockItem = control.addLock(this , compatabilitySpace,
173: qualifier);
174:
175: if (lockItem.getCount() != 0) {
176: return lockItem;
177: }
178:
179: if (timeout == C_LockFactory.NO_WAIT) {
180:
181: // remove all trace of lock
182: control.giveUpWait(lockItem, this );
183:
184: if (SanityManager.DEBUG) {
185: if (SanityManager.DEBUG_ON("DeadlockTrace")) {
186:
187: SanityManager.showTrace(new Throwable());
188:
189: // The following dumps the lock table as it
190: // exists at the time a timeout is about to
191: // cause a deadlock exception to be thrown.
192:
193: lockDebug = DiagnosticUtil
194: .toDiagString(lockItem)
195: + "\nCould not grant lock with zero timeout, here's the table"
196: + this .toDebugString();
197: }
198: }
199:
200: return null;
201: }
202:
203: // this is where we need to release the latch
204: if (latch != null)
205: unlock(latch, 1);
206:
207: } // synchronized block
208:
209: boolean deadlockWait = false;
210: int actualTimeout;
211:
212: if (timeout == C_LockFactory.WAIT_FOREVER) {
213: // always check for deadlocks as there should not be any
214: deadlockWait = true;
215: if ((actualTimeout = deadlockTimeout) == C_LockFactory.WAIT_FOREVER)
216: actualTimeout = Property.DEADLOCK_TIMEOUT_DEFAULT * 1000;
217: } else {
218:
219: if (timeout == C_LockFactory.TIMED_WAIT)
220: timeout = actualTimeout = waitTimeout;
221: else
222: actualTimeout = timeout;
223:
224: // five posible cases
225: // i) timeout -1, deadlock -1 ->
226: // just wait forever, no deadlock check
227: // ii) timeout >= 0, deadlock -1 ->
228: // just wait for timeout, no deadlock check
229: // iii) timeout -1, deadlock >= 0 ->
230: // wait for deadlock, then deadlock check,
231: // then infinite timeout
232: // iv) timeout >=0, deadlock < timeout ->
233: // wait for deadlock, then deadlock check,
234: // then wait for (timeout - deadlock)
235: // v) timeout >=0, deadlock >= timeout ->
236: // just wait for timeout, no deadlock check
237:
238: if (deadlockTimeout >= 0) {
239:
240: if (actualTimeout < 0) {
241: // infinite wait but perform a deadlock check first
242: deadlockWait = true;
243: actualTimeout = deadlockTimeout;
244: } else if (deadlockTimeout < actualTimeout) {
245:
246: // deadlock wait followed by a timeout wait
247:
248: deadlockWait = true;
249: actualTimeout = deadlockTimeout;
250:
251: // leave timeout as the remaining time
252: timeout -= deadlockTimeout;
253: }
254: }
255: }
256:
257: ActiveLock waitingLock = (ActiveLock) lockItem;
258: lockItem = null;
259:
260: if (deadlockTrace) {
261: // we want to keep a stack trace of this thread just before it goes
262: // into wait state, no need to synchronized because Hashtable.put
263: // is synchronized and the new throwable is local to this thread.
264: lockTraces.put(waitingLock, new Throwable());
265: }
266:
267: int earlyWakeupCount = 0;
268: long startWaitTime = 0;
269:
270: try {
271: forever: for (;;) {
272:
273: byte wakeupReason = waitingLock
274: .waitForGrant(actualTimeout);
275:
276: ActiveLock nextWaitingLock = null;
277: Object[] deadlockData = null;
278:
279: try {
280: boolean willQuitWait;
281: Enumeration timeoutLockTable = null;
282: long currentTime = 0;
283:
284: synchronized (this ) {
285:
286: if (control.isGrantable(
287: control.firstWaiter() == waitingLock,
288: compatabilitySpace, qualifier)) {
289:
290: // Yes, we are granted, put us on the granted queue.
291: control.grant(waitingLock);
292:
293: // Remove from the waiting queue & get next waiter
294: nextWaitingLock = control.getNextWaiter(
295: waitingLock, true, this );
296:
297: // this is where we need to re-obtain the latch,
298: // it's safe to call this lockObject() which will
299: // get the synchronization we already hold, because
300: // java allows nested synchronization and it will
301: // be released automatically if we have to wait
302:
303: if (latch != null) {
304: lockObject(compatabilitySpace, latch
305: .getLockable(), latch
306: .getQualifier(),
307: C_LockFactory.WAIT_FOREVER,
308: (Latch) null);
309: }
310: return waitingLock;
311: }
312:
313: // try again later
314: waitingLock.clearPotentiallyGranted();
315:
316: willQuitWait = (wakeupReason != Constants.WAITING_LOCK_GRANT);
317:
318: StandardException deadlockException = null;
319:
320: if (((wakeupReason == Constants.WAITING_LOCK_IN_WAIT) && deadlockWait)
321: || (wakeupReason == Constants.WAITING_LOCK_DEADLOCK)) {
322:
323: // check for a deadlock, even if we were woken up
324: // because we were selected as a victim we still
325: // check because the situation may have changed.
326: deadlockData = Deadlock.look(factory, this ,
327: control, waitingLock, wakeupReason);
328:
329: if (deadlockData == null) {
330: // we don't have a deadlock
331: deadlockWait = false;
332:
333: actualTimeout = timeout;
334: startWaitTime = 0;
335: willQuitWait = false;
336: } else {
337: willQuitWait = true;
338: }
339: }
340:
341: nextWaitingLock = control.getNextWaiter(
342: waitingLock, willQuitWait, this );
343:
344: // If we were not woken by another then we have
345: // timed out. Either deadlock out or timeout
346: if (willQuitWait) {
347:
348: // Even if we deadlocked trying to get the lock,
349: // still reget the latch so that client's need not
350: // know latch was released.
351:
352: if (latch != null) {
353: lockObject(compatabilitySpace, latch
354: .getLockable(), latch
355: .getQualifier(),
356: C_LockFactory.WAIT_FOREVER,
357: (Latch) null);
358: }
359:
360: if (SanityManager.DEBUG) {
361: if (SanityManager
362: .DEBUG_ON("DeadlockTrace")) {
363:
364: SanityManager
365: .showTrace(new Throwable());
366:
367: // The following dumps the lock table as it
368: // exists at the time a timeout is about to
369: // cause a deadlock exception to be thrown.
370:
371: lockDebug = DiagnosticUtil
372: .toDiagString(waitingLock)
373: + "\nGot deadlock/timeout, here's the table"
374: + this .toDebugString();
375: }
376: }
377:
378: if (deadlockTrace && (deadlockData == null)) {
379: // if ending lock request due to lock timeout
380: // want a copy of the LockTable and the time,
381: // in case of deadlock deadlockData has the
382: // info we need.
383: currentTime = System
384: .currentTimeMillis();
385: timeoutLockTable = factory
386: .makeVirtualLockTable();
387: }
388: }
389:
390: } // synchronized block
391:
392: // need to do this outside of the synchronized block as the
393: // message text building (timeouts and deadlocks) may
394: // involve getting locks to look up table names from
395: // identifiers.
396:
397: if (willQuitWait) {
398: if (SanityManager.DEBUG) {
399: if (lockDebug != null) {
400: String type = ((deadlockData != null) ? "deadlock:"
401: : "timeout:");
402:
403: SanityManager.DEBUG_PRINT(type,
404: "wait on lockitem caused "
405: + type + lockDebug);
406: }
407:
408: }
409:
410: if (deadlockData == null) {
411: // ending wait because of lock timeout.
412:
413: if (deadlockTrace) {
414: // Turn ON derby.locks.deadlockTrace to build
415: // the lockTable.
416:
417: throw Timeout.buildException(
418: waitingLock, timeoutLockTable,
419: currentTime);
420: } else {
421: StandardException se = StandardException
422: .newException(SQLState.LOCK_TIMEOUT);
423:
424: throw se;
425: }
426: } else {
427: // ending wait because of lock deadlock.
428:
429: throw Deadlock.buildException(factory,
430: deadlockData);
431: }
432: }
433: } finally {
434: if (nextWaitingLock != null) {
435: nextWaitingLock
436: .wakeUp(Constants.WAITING_LOCK_GRANT);
437: nextWaitingLock = null;
438: }
439: }
440:
441: if (actualTimeout != C_LockFactory.WAIT_FOREVER) {
442:
443: if (wakeupReason != Constants.WAITING_LOCK_IN_WAIT)
444: earlyWakeupCount++;
445:
446: if (earlyWakeupCount > 5) {
447:
448: long now = System.currentTimeMillis();
449:
450: if (startWaitTime != 0) {
451:
452: long sleepTime = now - startWaitTime;
453:
454: actualTimeout -= sleepTime;
455: }
456:
457: startWaitTime = now;
458: }
459: }
460:
461: } // for(;;)
462: } finally {
463: if (deadlockTrace) {
464: // I am out of the wait state, either I got my lock or I
465: // am the one who is going to detect the deadlock, don't
466: // need the stack trace anymore.
467: lockTraces.remove(waitingLock);
468: }
469: }
470: }
471:
472: /**
473: Unlock an object, previously locked by lockObject().
474:
475: If unlockCOunt is not zero then the lock will be unlocked
476: that many times, otherwise the unlock count is taken from
477: item.
478:
479: */
480: void unlock(Latch item, int unlockCount) {
481:
482: if (SanityManager.DEBUG) {
483: if (SanityManager.DEBUG_ON(Constants.LOCK_TRACE)) {
484: /*
485: ** I don't like checking the trace flag twice, but SanityManager
486: ** doesn't provide a way to get to the debug trace stream
487: ** directly.
488: */
489: SanityManager.DEBUG(Constants.LOCK_TRACE,
490: "Release lock: "
491: + DiagnosticUtil.toDiagString(item));
492: }
493: }
494:
495: boolean tryGrant = false;
496: ActiveLock nextGrant = null;
497:
498: synchronized (this ) {
499:
500: Control control = getControl(item.getLockable());
501:
502: if (SanityManager.DEBUG) {
503:
504: // only valid Lock's expected
505: if (item.getLockable() == null) {
506: SanityManager
507: .THROWASSERT("item.getLockable() = null."
508: + "unlockCount " + unlockCount
509: + "item = "
510: + DiagnosticUtil.toDiagString(item));
511: }
512:
513: // only valid Lock's expected
514: if (control == null) {
515: SanityManager.THROWASSERT("control = null."
516: + "unlockCount " + unlockCount + "item = "
517: + DiagnosticUtil.toDiagString(item));
518: }
519:
520: if (getControl(control.getLockable()) != control) {
521: SanityManager
522: .THROWASSERT("unlock mismatched lock items "
523: + getControl(control.getLockable())
524: + " " + control);
525: }
526:
527: if ((unlockCount != 0)
528: && (unlockCount > item.getCount()))
529: SanityManager.THROWASSERT("unlockCount "
530: + unlockCount
531: + " larger than actual lock count "
532: + item.getCount() + " item " + item);
533: }
534:
535: tryGrant = control.unlock(item, unlockCount);
536: item = null;
537:
538: boolean mayBeEmpty = true;
539: if (tryGrant) {
540: nextGrant = control.firstWaiter();
541: if (nextGrant != null) {
542: mayBeEmpty = false;
543: if (!nextGrant.setPotentiallyGranted())
544: nextGrant = null;
545: }
546: }
547:
548: if (mayBeEmpty) {
549: if (control.isEmpty()) {
550: // no-one granted, no-one waiting, remove lock control
551: remove(control.getLockable());
552: }
553: return;
554: }
555: } // synchronized (this)
556:
557: if (tryGrant && (nextGrant != null)) {
558: nextGrant.wakeUp(Constants.WAITING_LOCK_GRANT);
559: }
560: }
561:
562: /*
563: ** Non public methods
564: */
565: //EXCLUDE-START-lockdiag-
566: void setDeadlockTrace(boolean val) {
567: // set this without synchronization
568: deadlockTrace = val;
569:
570: if (val && lockTraces == null) {
571: lockTraces = new Hashtable();
572: } else if (!val && lockTraces != null) {
573: lockTraces = null;
574: }
575: }
576:
577: //EXCLUDE-END-lockdiag-
578:
579: public String toDebugString() {
580: if (SanityManager.DEBUG) {
581: String str = new String();
582:
583: int i = 0;
584: for (Enumeration e = this .elements(); e.hasMoreElements(); i++) {
585: str += "\n lock[" + i + "]: "
586: + DiagnosticUtil.toDiagString(e.nextElement());
587: }
588:
589: return (str);
590: } else {
591: return (null);
592: }
593: }
594:
595: //EXCLUDE-START-lockdiag-
596: /*
597: * make a shallow clone of myself and my lock controls
598: */
599: /* package */
600: synchronized LockSet shallowClone() {
601: LockSet clone = new LockSet(factory);
602:
603: for (Enumeration e = keys(); e.hasMoreElements();) {
604: Lockable lockable = (Lockable) e.nextElement();
605: Control control = getControl(lockable);
606:
607: clone.put(lockable, control.shallowClone());
608: }
609:
610: return clone;
611: }
612:
613: //EXCLUDE-END-lockdiag-
614:
615: /*
616: ** Support for anyoneBlocked(). These methods assume that caller
617: ** is synchronized on this LockSet object.
618: */
619: void oneMoreWaiter() {
620: blockCount++;
621: }
622:
623: void oneLessWaiter() {
624: blockCount--;
625: }
626:
627: boolean anyoneBlocked() {
628: if (SanityManager.DEBUG) {
629: SanityManager.ASSERT(blockCount >= 0,
630: "blockCount should not be negative");
631: }
632:
633: // no synchronization needed because reads of ints are atomic
634: return blockCount != 0;
635: }
636:
637: public final Control getControl(Lockable ref) {
638: return (Control) get(ref);
639: }
640: }
|