001: /*
002:
003: Derby - Class org.apache.derby.impl.services.locks.LockControl
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.Lockable;
025: import org.apache.derby.iapi.services.locks.Latch;
026:
027: import org.apache.derby.iapi.services.sanity.SanityManager;
028:
029: import java.util.Dictionary;
030: import java.util.Stack;
031: import java.util.List;
032: import java.util.ListIterator;
033:
034: /**
035: A LockControl contains a reference to the item being locked
036: and doubly linked lists for the granted locks and the waiting
037: locks.
038:
039: <P>
040: MT - Mutable - Container object : single thread required
041:
042: */
043:
044: public class LockControl implements Control {
045:
046: private final Lockable ref;
047:
048: /**
049: This lock control uses an optimistic locking scheme.
050: When the first lock on an object is granted it
051: simply sets firstGrant to be that object, removing the
052: need to allocate a list if no other locks are granted
053: before the first lock is release. If a second lock
054: is granted then a list is allocated and the
055: firstGrant lock is moved into the list. Once a list
056: has been created it is always used.
057: */
058: private Lock firstGrant;
059: private List granted;
060: private List waiting;
061: private Lock lastPossibleSkip;
062:
063: protected LockControl(Lock firstLock, Lockable ref) {
064: super ();
065: this .ref = ref;
066:
067: // System.out.println("new lockcontrol");
068:
069: firstGrant = firstLock;
070: }
071:
072: // make a copy by cloning the granted and waiting lists
073: private LockControl(LockControl copyFrom) {
074: super ();
075:
076: this .ref = copyFrom.ref;
077: this .firstGrant = copyFrom.firstGrant;
078:
079: if (copyFrom.granted != null)
080: this .granted = new java.util.LinkedList(copyFrom.granted);
081:
082: if (copyFrom.waiting != null)
083: this .waiting = new java.util.LinkedList(copyFrom.waiting);
084:
085: this .lastPossibleSkip = copyFrom.lastPossibleSkip;
086: }
087:
088: public LockControl getLockControl() {
089: return this ;
090: }
091:
092: /**
093: */
094: public boolean isEmpty() {
095:
096: // if we are locked then we are not empty
097: if (!isUnlocked())
098: return false;
099:
100: return (waiting == null) || waiting.isEmpty();
101: }
102:
103: /**
104: Grant this lock.
105: */
106: void grant(Lock lockItem) {
107:
108: lockItem.grant();
109:
110: List lgranted = granted;
111:
112: if (lgranted == null) {
113: if (firstGrant == null) {
114: // first ever lock on this item
115: firstGrant = lockItem;
116: } else {
117: // second ever lock on this item
118: lgranted = granted = new java.util.LinkedList();
119: lgranted.add(firstGrant);
120: lgranted.add(lockItem);
121: firstGrant = null;
122: }
123: } else {
124: // this grants the lock
125: lgranted.add(lockItem);
126: }
127: }
128:
129: /**
130: */
131: public boolean unlock(Latch lockInGroup, int unlockCount) {
132:
133: // note that lockInGroup is not the actual Lock object held in the lock set.
134:
135: if (unlockCount == 0)
136: unlockCount = lockInGroup.getCount();
137:
138: List lgranted = granted;
139:
140: // start at the begining of the list when there is one
141: for (int index = 0; unlockCount > 0;) {
142:
143: Lock lockInSet;
144:
145: if (firstGrant != null) {
146: if (SanityManager.DEBUG) {
147: SanityManager
148: .ASSERT(lockInGroup.equals(firstGrant));
149: }
150: lockInSet = firstGrant;
151: } else {
152: // index = lgranted.indexOf(index, lgranted.size() - 1, lockInGroup);
153: /*List*/index = lgranted.indexOf(lockInGroup);
154:
155: if (SanityManager.DEBUG) {
156: SanityManager.ASSERT(index != -1);
157: }
158: lockInSet = (Lock) lgranted.get(index);
159: }
160:
161: unlockCount -= lockInSet.unlock(unlockCount);
162:
163: if (lockInSet.getCount() != 0) {
164: if (SanityManager.DEBUG) {
165: if (unlockCount != 0)
166: SanityManager
167: .THROWASSERT("locked item didn't reduce unlock count to zero "
168: + unlockCount);
169: }
170: continue;
171: }
172:
173: if (firstGrant == lockInSet) {
174: if (SanityManager.DEBUG) {
175: if (unlockCount != 0)
176: SanityManager
177: .THROWASSERT("item is still locked! "
178: + unlockCount);
179: }
180: firstGrant = null;
181: } else {
182: lgranted.remove(index);
183: }
184: }
185:
186: return true;
187: }
188:
189: /**
190: This routine can be called to see if a lock currently on the wait
191: list could be granted. If this lock has waiters ahead of it
192: then we do not jump over the waiter(s) even if we can be granted.
193: This avoids the first waiter being starved out.
194: */
195:
196: public boolean isGrantable(boolean noWaitersBeforeMe,
197: Object compatabilitySpace, Object qualifier) {
198: if (isUnlocked())
199: return true;
200:
201: boolean grantLock = false;
202:
203: Lockable lref = ref;
204: List lgranted = granted;
205:
206: {
207: // Check to see if the only locks on the granted queue that
208: // we are incompatible with are locks we own.
209: boolean selfCompatible = lref.lockerAlwaysCompatible();
210:
211: int index = 0;
212: int endIndex = firstGrant == null ? lgranted.size() : 0;
213: do {
214:
215: Lock gl = firstGrant == null ? (Lock) lgranted
216: .get(index) : firstGrant;
217:
218: boolean sameSpace = (gl.getCompatabilitySpace()
219: .equals(compatabilitySpace));
220:
221: if (sameSpace && selfCompatible) {
222: // if it's one of our locks and we are always compatible
223: // with our own locks then yes, we can be granted.
224:
225: grantLock = true;
226: continue;
227: } else if (!lref.requestCompatible(qualifier, gl
228: .getQualifier())) {
229: // If we are not compatible with some already granted lock
230: // then we can't be granted, give up right away.
231:
232: grantLock = false;
233: break;
234: } else {
235: // We are compatible with this lock, if it's our own or
236: // there are no other waiters then we can be granted.
237:
238: if (sameSpace || noWaitersBeforeMe) {
239: grantLock = true;
240: }
241: }
242: } while (++index < endIndex);
243: }
244:
245: return (grantLock);
246: }
247:
248: /**
249: Add a lock into this control, granted it if possible.
250:
251: This can be entered in several states.
252:
253: </OL>
254: <LI>The Lockable is locked (granted queue not empty), and there are no waiters (waiting queue is empty)
255: <LI>The Lockable is locked and there are waiters
256: <LI>The Lockable is locked and there are waiters and the first is potentially granted
257: <LI>The Lockable is unlocked and there are waiters and the first is potentially granted. Logically the item is
258: still locked, it's just that the lock has just been released and the first waker has not woken up yet.
259: </OL>
260: This call is never entered when the object is unlocked and there are no waiters.
261:
262:
263: 1) The Lockable has just been unlocked,
264: */
265:
266: public Lock addLock(LockSet ls, Object compatabilitySpace,
267: Object qualifier) {
268:
269: if (SanityManager.DEBUG) {
270:
271: if (!(!isUnlocked() || (firstWaiter() != null)))
272: SanityManager
273: .THROWASSERT("entered in totally unlocked mode "
274: + isUnlocked()
275: + " "
276: + (firstWaiter() != null));
277: }
278:
279: // If there are other waiters for this lock then we
280: // will only grant this lock if we already hold a lock.
281: // This stops a lock being frozen out while compatible locks
282: // jump past it.
283: boolean grantLock = false;
284: boolean otherWaiters = (firstWaiter() != null);
285:
286: Lock lockItem = null;
287: Lockable lref = ref;
288:
289: // If we haven't been able to grant the lock yet then see if we hold a
290: // lock already that we are compatible with and there are no granted
291: // incompatible locks. If the object appears unlocked (due to a just
292: // released lock, but the first waiter hasn't woken yet)
293: // then we obviously don't hold a lock, so just join the wait queue.
294: boolean spaceHasALock = false;
295: boolean noGrantAtAll = false;
296: if (!grantLock && !isUnlocked()) {
297:
298: boolean selfCompatible = lref.lockerAlwaysCompatible();
299:
300: int index = 0;
301: int endIndex = firstGrant == null ? granted.size() : 0;
302: do {
303:
304: Lock gl = firstGrant == null ? (Lock) granted
305: .get(index) : firstGrant;
306:
307: boolean sameSpace = (gl.getCompatabilitySpace()
308: .equals(compatabilitySpace));
309:
310: // if it's one of our locks and we are always compatible with
311: // our own locks then yes, we can be granted.
312: if (sameSpace && selfCompatible) {
313:
314: spaceHasALock = true;
315:
316: if (noGrantAtAll)
317: break;
318:
319: if (qualifier == gl.getQualifier())
320: lockItem = gl;
321:
322: grantLock = true;
323: continue;
324: }
325:
326: // If we are not compatible with some already granted lock
327: // then we can't be granted, give up right away.
328: if (!lref.requestCompatible(qualifier, gl
329: .getQualifier())) {
330: grantLock = false;
331: lockItem = null;
332:
333: // we can't give up rightaway if spaceHasALock is false
334: // because we need to ensure that canSkip is set correctly
335: if (spaceHasALock)
336: break;
337:
338: noGrantAtAll = true;
339: }
340:
341: // We are compatible with this lock, if it's our own or there
342: // are no other waiters then yes we can still be granted ...
343:
344: if (!noGrantAtAll && (sameSpace || !otherWaiters)) {
345: grantLock = true;
346: }
347: } while (++index < endIndex);
348: }
349:
350: if (lockItem != null) {
351: if (SanityManager.DEBUG) {
352: if (!grantLock) {
353: SanityManager.THROWASSERT("lock is not granted !"
354: + lockItem);
355: }
356: }
357:
358: // we already held a lock of this type, just bump the lock count
359: lockItem.count++;
360: return lockItem;
361: }
362:
363: if (grantLock) {
364: lockItem = new Lock(compatabilitySpace, lref, qualifier);
365: grant(lockItem);
366: return lockItem;
367: }
368:
369: ActiveLock waitingLock = new ActiveLock(compatabilitySpace,
370: lref, qualifier);
371:
372: // If the object is already locked by this compatability space
373: // then this lock can be granted by skipping other waiters.
374: if (spaceHasALock) {
375: waitingLock.canSkip = true;
376: }
377:
378: if (waiting == null)
379: waiting = new java.util.LinkedList();
380:
381: // Add lock to the waiting list
382: addWaiter(waiting, waitingLock, ls);
383:
384: if (waitingLock.canSkip) {
385: lastPossibleSkip = waitingLock;
386: }
387:
388: return waitingLock;
389: }
390:
391: protected boolean isUnlocked() {
392:
393: // If firstGrant is set then this object is locked
394: if (firstGrant != null)
395: return false;
396:
397: List lgranted = granted;
398:
399: return (lgranted == null) || lgranted.isEmpty();
400: }
401:
402: /**
403: Return the first lock in the wait line, null if the
404: line is empty.
405: */
406: public ActiveLock firstWaiter() {
407: if ((waiting == null) || waiting.isEmpty())
408: return null;
409: return (ActiveLock) waiting.get(0);
410: }
411:
412: /**
413: Get the next waiting lock (if any).
414: */
415: ActiveLock getNextWaiter(ActiveLock item, boolean remove, LockSet ls) {
416:
417: ActiveLock nextWaitingLock = null;
418:
419: if (remove && (waiting.get(0) == item)) {
420: // item is at the head of the list and being removed,
421: // always return the next waiter
422: popFrontWaiter(waiting, ls);
423:
424: nextWaitingLock = firstWaiter();
425: } else if ((lastPossibleSkip != null)
426: && (lastPossibleSkip != item)) {
427: // there are potential locks that could be granted
428: // and the last one is not the lock we just looked at.
429:
430: // need to find the first lock after the one passed
431: // in that has the canSkip flag set.
432:
433: int itemIndex = waiting.indexOf(item);
434: int removeIndex = remove ? itemIndex : -1;
435:
436: // skip the entry we just looked at.
437: /*List*/
438: // dli.advance();
439: // for (; !dli.atEnd(); dli.advance()) {
440: if (itemIndex != waiting.size() - 1) {
441:
442: for (ListIterator li = waiting
443: .listIterator(itemIndex + 1); li.hasNext();) {
444: //ActiveLock al = (ActiveLock) dli.get();
445: ActiveLock al = (ActiveLock) li.next();
446:
447: if (al.canSkip) {
448: nextWaitingLock = al;
449: break;
450: }
451: }
452: }
453:
454: if (remove) {
455: removeWaiter(waiting, removeIndex, ls);
456: }
457:
458: } else {
459: if (remove) {
460: int count = removeWaiter(waiting, item, ls);
461:
462: if (SanityManager.DEBUG) {
463: if (count != 1) {
464: SanityManager.THROWASSERT("count = " + count
465: + "item = " + item + "waiting = "
466: + waiting);
467: }
468: }
469: }
470: }
471:
472: if (remove && (item == lastPossibleSkip))
473: lastPossibleSkip = null;
474:
475: if (nextWaitingLock != null) {
476: if (!nextWaitingLock.setPotentiallyGranted())
477: nextWaitingLock = null;
478: }
479:
480: return nextWaitingLock;
481: }
482:
483: /**
484: Return the lockable object controlled by me.
485: */
486: public Lockable getLockable() {
487: return ref;
488: }
489:
490: public Lock getFirstGrant() {
491: return firstGrant;
492: }
493:
494: public List getGranted() {
495: return granted;
496: }
497:
498: public List getWaiting() {
499: return waiting;
500: }
501:
502: /**
503: Give up waiting up on a lock
504: */
505:
506: protected void giveUpWait(Object item, LockSet ls) {
507:
508: int count = removeWaiter(waiting, item, ls);
509: if (item == lastPossibleSkip)
510: lastPossibleSkip = null;
511:
512: if (SanityManager.DEBUG) {
513: if (count != 1) {
514: SanityManager.THROWASSERT("count = " + count
515: + "item = " + item + "waiting = " + waiting);
516: }
517: }
518: }
519:
520: /*
521: ** Deadlock support.
522: */
523:
524: /**
525: Add the waiters of this lock into this Dictionary object.
526: <BR>
527: Each waiting thread gets two entries in the hashtable
528: <OL>
529: <LI>key=compatibility space - value=ActiveLock
530: <LI>key=ActiveLock - value={LockControl for first waiter|ActiveLock of previosue waiter}
531: </OL>
532: */
533: public void addWaiters(Dictionary waiters) {
534:
535: if ((waiting == null) || waiting.isEmpty())
536: return;
537:
538: Object previous = this ;
539: for (ListIterator li = waiting.listIterator(); li.hasNext();) {
540:
541: ActiveLock waitingLock = ((ActiveLock) li.next());
542:
543: Object waiter = waitingLock.getCompatabilitySpace();
544:
545: waiters.put(waiter, waitingLock);
546: waiters.put(waitingLock, previous);
547: previous = waitingLock;
548: }
549: }
550:
551: /**
552: Return a Stack of the
553: held locks (Lock objects) on this Lockable.
554: */
555: List getGrants() {
556:
557: List ret;
558:
559: if (firstGrant != null) {
560: ret = new java.util.LinkedList();
561: ret.add(firstGrant);
562: } else {
563: ret = new java.util.LinkedList(granted);
564: }
565:
566: return ret;
567: }
568:
569: /**
570: Find a granted lock matching this space and qualifier
571: */
572: public final Lock getLock(Object compatabilitySpace,
573: Object qualifier) {
574:
575: if (isUnlocked())
576: return null;
577:
578: List lgranted = granted;
579:
580: int index = 0;
581: int endIndex = firstGrant == null ? lgranted.size() : 0;
582: do {
583:
584: Lock gl = firstGrant == null ? (Lock) lgranted.get(index)
585: : firstGrant;
586:
587: if (!gl.getCompatabilitySpace().equals(compatabilitySpace))
588: continue;
589:
590: if (gl.getQualifier() == qualifier)
591: return gl;
592:
593: } while (++index < endIndex);
594: return null;
595: }
596:
597: //EXCLUDE-START-lockdiag-
598: /**
599: * make a shallow clone of myself
600: */
601: /* package */
602: public Control shallowClone() {
603: return new LockControl(this );
604: }
605:
606: //EXCLUDE-END-lockdiag-
607:
608: /**
609: * Add a lock request to a list of waiters.
610: *
611: * @param waiting The list of waiters to add to
612: * @param lockItem The lock request
613: * @param ls The LockSet
614: */
615: private void addWaiter(List waiting, Lock lockItem, LockSet ls) {
616:
617: // Add lock to the waiting list
618: waiting.add(lockItem);
619:
620: // Maintain count of waiters
621: ls.oneMoreWaiter();
622: }
623:
624: /**
625: * Remove and return the first lock request from a list of waiters.
626: *
627: * @param waiting The list of waiters to pop from
628: * @param ls The LockSet
629: *
630: * @return The removed lock request
631: */
632: private Object popFrontWaiter(List waiting, LockSet ls) {
633: // Maintain count of waiters
634: ls.oneLessWaiter();
635:
636: // Remove and return the first lock request
637: return waiting.remove(0);
638: }
639:
640: /**
641: * Remove and return the lock request at the given index
642: * from a list of waiters.
643: *
644: * @param waiting The list of waiters to pop from
645: * @param index The index at which to remove the lock request
646: * @param ls The LockSet
647: *
648: * @return The removed lock request
649: */
650: private Object removeWaiter(List waiting, int index, LockSet ls) {
651: // Maintain count of waiters
652: ls.oneLessWaiter();
653:
654: // Remove and return the first lock request
655: return waiting.remove(index);
656: }
657:
658: /**
659: * Remove and return the given lock request from a list of waiters.
660: *
661: * @param waiting The list of waiters to pop from
662: * @param item The item to remove
663: * @param ls The LockSet
664: *
665: * @return The number of items removed
666: */
667: private int removeWaiter(List waiting, Object item, LockSet ls) {
668: // Maintain count of waiters
669: ls.oneLessWaiter();
670:
671: // Remove item and return number of items removed
672: return waiting.remove(item) ? 1 : 0;
673: }
674: }
|