Java > Open Source Codes > org > apache > derby > impl > services > locks > LockControl


1 /*
2
3    Derby - Class org.apache.derby.impl.services.locks.LockControl
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.services.locks;
23
24 import org.apache.derby.iapi.services.locks.Lockable;
25 import org.apache.derby.iapi.services.locks.Latch;
26
27 import org.apache.derby.iapi.services.sanity.SanityManager;
28
29 import java.util.Dictionary ;
30 import java.util.Stack ;
31 import java.util.List ;
32 import java.util.ListIterator ;
33
34 /**
35     A LockControl contains a reference to the item being locked
36     and doubly linked lists for the granted locks and the waiting
37     locks.
38
39     <P>
40     MT - Mutable - Container object : single thread required
41
42 */
43
44 public class LockControl implements Control {
45
46     private final Lockable ref;
47
48     /**
49         This lock control uses an optimistic locking scheme.
50         When the first lock on an object is granted it
51         simply sets firstGrant to be that object, removing the
52         need to allocate a list if no other locks are granted
53         before the first lock is release. If a second lock
54         is granted then a list is allocated and the
55         firstGrant lock is moved into the list. Once a list
56         has been created it is always used.
57     */
58     private Lock firstGrant;
59     private List granted;
60     private List waiting;
61     private Lock lastPossibleSkip;
62
63     protected LockControl(Lock firstLock, Lockable ref) {
64         super();
65         this.ref = ref;
66
67         // System.out.println("new lockcontrol");
68
69         firstGrant = firstLock;
70     }
71
72     // make a copy by cloning the granted and waiting lists
73 private LockControl(LockControl copyFrom)
74     {
75         super();
76
77         this.ref = copyFrom.ref;
78         this.firstGrant = copyFrom.firstGrant;
79
80         if (copyFrom.granted != null)
81             this.granted = new java.util.LinkedList (copyFrom.granted);
82
83         if (copyFrom.waiting != null)
84             this.waiting = new java.util.LinkedList (copyFrom.waiting);
85
86         this.lastPossibleSkip = copyFrom.lastPossibleSkip;
87     }
88     
89     public LockControl getLockControl() {
90         return this;
91     }
92
93     /**
94     */
95     public boolean isEmpty() {
96
97         // if we are locked then we are not empty
98 if (!isUnlocked())
99             return false;
100
101         return (waiting == null) || waiting.isEmpty();
102     }
103
104     /**
105         Grant this lock.
106     */
107     void grant(Lock lockItem) {
108
109         lockItem.grant();
110
111         List lgranted = granted;
112         
113         if (lgranted == null) {
114             if (firstGrant == null) {
115                 // first ever lock on this item
116 firstGrant = lockItem;
117             } else {
118                 // second ever lock on this item
119 lgranted = granted = new java.util.LinkedList ();
120                 lgranted.add(firstGrant);
121                 lgranted.add(lockItem);
122                 firstGrant = null;
123             }
124         } else {
125             // this grants the lock
126 lgranted.add(lockItem);
127         }
128     }
129
130     /**
131     */
132     public boolean unlock(Latch lockInGroup, int unlockCount) {
133
134         // note that lockInGroup is not the actual Lock object held in the lock set.
135
136         if (unlockCount == 0)
137             unlockCount = lockInGroup.getCount();
138
139         List lgranted = granted;
140             
141         // start at the begining of the list when there is one
142 for (int index = 0; unlockCount > 0; ) {
143
144             Lock lockInSet;
145
146             if (firstGrant != null) {
147                 if (SanityManager.DEBUG) {
148                     SanityManager.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.THROWASSERT("locked item didn't reduce unlock count to zero " + unlockCount);
167                 }
168                 continue;
169             }
170
171             if (firstGrant == lockInSet) {
172                 if (SanityManager.DEBUG) {
173                     if (unlockCount != 0)
174                         SanityManager.THROWASSERT("item is still locked! " + unlockCount);
175                 }
176                 firstGrant = null;
177             }
178             else {
179                 lgranted.remove(index);
180             }
181         }
182
183         return true;
184     }
185
186     /**
187         This routine can be called to see if a lock currently on the wait
188         list could be granted. If this lock has waiters ahead of it
189         then we do not jump over the waiter(s) even if we can be granted.
190          This avoids the first waiter being starved out.
191     */
192
193     public boolean isGrantable(
194     boolean noWaitersBeforeMe,
195     Object compatabilitySpace,
196     Object qualifier)
197     {
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.get(index) : firstGrant;
216
217                 boolean sameSpace =
218                     (gl.getCompatabilitySpace().equals(compatabilitySpace));
219
220                 if (sameSpace && selfCompatible)
221                 {
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                 }
228                 else if (!lref.requestCompatible(qualifier, gl.getQualifier()))
229                 {
230                     // If we are not compatible with some already granted lock
231 // then we can't be granted, give up right away.
232
233                     grantLock = false;
234                     break;
235                 }
236                 else
237                 {
238                     // We are compatible with this lock, if it's our own or
239 // there are no other waiters then we can be granted.
240
241                     if (sameSpace || noWaitersBeforeMe)
242                     {
243                         grantLock = true;
244                     }
245                 }
246             } while (++index < endIndex);
247         }
248
249         return(grantLock);
250     }
251
252     /**
253         Add a lock into this control, granted it if possible.
254
255         This can be entered in several states.
256
257         </OL>
258         <LI>The Lockable is locked (granted queue not empty), and there are no waiters (waiting queue is empty)
259         <LI>The Lockable is locked and there are waiters
260         <LI>The Lockable is locked and there are waiters and the first is potentially granted
261         <LI>The Lockable is unlocked and there are waiters and the first is potentially granted. Logically the item is
262             still locked, it's just that the lock has just been released and the first waker has not woken up yet.
263         </OL>
264         This call is never entered when the object is unlocked and there are no waiters.
265
266     
267         1) The Lockable has just been unlocked,
268     */
269
270     public Lock addLock(LockSet ls, Object compatabilitySpace, Object qualifier) {
271
272         if (SanityManager.DEBUG) {
273
274             if (!(!isUnlocked() || (firstWaiter() != null)))
275                 SanityManager.THROWASSERT("entered in totally unlocked mode " + isUnlocked() + " " + (firstWaiter() != null));
276         }
277
278         // If there are other waiters for this lock then we
279 // will only grant this lock if we already hold a lock.
280 // This stops a lock being frozen out while compatible locks
281 // jump past it.
282 boolean grantLock = false;
283         boolean otherWaiters = (firstWaiter() != null);
284
285         Lock lockItem = null;
286         Lockable lref = ref;
287
288         // If we haven't been able to grant the lock yet then see if we hold a
289 // lock already that we are compatible with and there are no granted
290 // incompatible locks. If the object appears unlocked (due to a just
291 // released lock, but the first waiter hasn't woken yet)
292 // then we obviously don't hold a lock, so just join the wait queue.
293 boolean spaceHasALock = false;
294         boolean noGrantAtAll = false;
295         if (!grantLock && !isUnlocked()) {
296
297             boolean selfCompatible = lref.lockerAlwaysCompatible();
298             
299             int index = 0;
300             int endIndex = firstGrant == null ? granted.size() : 0;
301             do {
302
303                 Lock gl = firstGrant == null ? (Lock) granted.get(index) : firstGrant;
304
305
306                 boolean sameSpace = (gl.getCompatabilitySpace().equals(compatabilitySpace));
307
308                 // if it's one of our locks and we are always compatible with
309 // our own locks then yes, we can be granted.
310 if (sameSpace && selfCompatible) {
311
312                     spaceHasALock = true;
313
314                     if (noGrantAtAll)
315                         break;
316
317                     if (qualifier == gl.getQualifier())
318                         lockItem = gl;
319
320                     grantLock = true;
321                     continue;
322                 }
323                 
324                 // If we are not compatible with some already granted lock
325 // then we can't be granted, give up right away.
326 if (!lref.requestCompatible(qualifier, gl.getQualifier())) {
327                     grantLock = false;
328                     lockItem = null;
329
330                     // we can't give up rightaway if spaceHasALock is false
331 // because we need to ensure that canSkip is set correctly
332 if (spaceHasALock)
333                         break;
334
335                     noGrantAtAll = true;
336                 }
337
338                 // We are compatible with this lock, if it's our own or there
339 // are no other waiters then yes we can still be granted ...
340
341                 if (!noGrantAtAll && (sameSpace || !otherWaiters)) {
342                     grantLock = true;
343                 }
344             } while (++index < endIndex);
345         }
346
347         if (lockItem != null) {
348             if (SanityManager.DEBUG) {
349                 if (!grantLock) {
350                     SanityManager.THROWASSERT("lock is not granted !" + lockItem);
351                 }
352             }
353
354             // we already held a lock of this type, just bump the lock count
355 lockItem.count++;
356             return lockItem;
357         }
358
359         if (grantLock) {
360             lockItem = new Lock(compatabilitySpace, lref, qualifier);
361             grant(lockItem);
362             return lockItem;
363         }
364         
365         ActiveLock waitingLock = new ActiveLock(compatabilitySpace, lref, qualifier);
366
367         // If the object is already locked by this compatability space
368 // then this lock can be granted by skipping other waiters.
369 if (spaceHasALock) {
370             waitingLock.canSkip = true;
371         }
372
373         if (waiting == null)
374             waiting = new java.util.LinkedList ();
375
376         // Add lock to the waiting list
377 addWaiter(waiting, waitingLock, ls);
378
379         if (waitingLock.canSkip) {
380             lastPossibleSkip = waitingLock;
381         }
382
383         return waitingLock;
384     }
385
386     protected boolean isUnlocked() {
387
388         // If firstGrant is set then this object is locked
389 if (firstGrant != null)
390             return false;
391
392         List lgranted = granted;
393
394         return (lgranted == null) || lgranted.isEmpty();
395     }
396
397     /**
398         Return the first lock in the wait line, null if the
399         line is empty.
400     */
401     public ActiveLock firstWaiter() {
402         if ((waiting == null) || waiting.isEmpty())
403             return null;
404         return (ActiveLock) waiting.get(0);
405     }
406
407
408     /**
409         Get the next waiting lock (if any).
410     */
411     ActiveLock getNextWaiter(ActiveLock item, boolean remove, LockSet ls) {
412
413         ActiveLock nextWaitingLock = null;
414
415         if (remove && (waiting.get(0) == item))
416         {
417             // item is at the head of the list and being removed,
418 // always return the next waiter
419 popFrontWaiter(waiting, ls);
420
421             nextWaitingLock = firstWaiter();
422         }
423         else if ((lastPossibleSkip != null) && (lastPossibleSkip != item))
424         {
425             // there are potential locks that could be granted
426 // and the last one is not the lock we just looked at.
427
428             // need to find the first lock after the one passed
429 // in that has the canSkip flag set.
430
431             int itemIndex = waiting.indexOf(item);
432             int removeIndex = remove ? itemIndex : -1;
433
434
435
436             // skip the entry we just looked at.
437 /*List*/
438             // dli.advance();
439 // for (; !dli.atEnd(); dli.advance()) {
440
441             if (itemIndex != waiting.size() - 1) {
442
443             for (ListIterator li = waiting.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                     {
465                         SanityManager.THROWASSERT(
466                             "count = " + count + "item = " + item +
467                             "waiting = " + waiting);
468                     }
469                 }
470             }
471         }
472
473         if (remove && (item == lastPossibleSkip))
474             lastPossibleSkip = null;
475
476         if (nextWaitingLock != null) {
477             if (!nextWaitingLock.setPotentiallyGranted())
478                 nextWaitingLock = null;
479         }
480
481         return nextWaitingLock;
482     }
483
484     /**
485         Return the lockable object controlled by me.
486     */
487     public Lockable getLockable() {
488         return ref;
489     }
490     public Lock getFirstGrant() {
491         return firstGrant;
492     }
493     public List getGranted() {
494         return granted;
495     }
496     public List getWaiting() {
497         return waiting;
498     }
499
500     /**
501         Give up waiting up on a lock
502     */
503
504     protected void giveUpWait(Object item, LockSet ls) {
505
506         int count = removeWaiter(waiting, item, ls);
507         if (item == lastPossibleSkip)
508             lastPossibleSkip = null;
509
510         if (SanityManager.DEBUG) {
511             if (count != 1)
512             {
513                 SanityManager.THROWASSERT(
514                     "count = " + count + "item = " + item +
515                     "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         }
563         else
564         {
565             ret = new java.util.LinkedList (granted);
566         }
567
568         return ret;
569     }
570
571     /**
572         Find a granted lock matching this space and qualifier
573     */
574     public final Lock getLock(Object compatabilitySpace, Object qualifier) {
575
576         if (isUnlocked())
577             return null;
578
579         List lgranted = granted;
580
581
582         int index = 0;
583         int endIndex = firstGrant == null ? lgranted.size() : 0;
584         do {
585
586             Lock gl = firstGrant == null ? (Lock) lgranted.get(index) : firstGrant;
587
588             if (!gl.getCompatabilitySpace().equals(compatabilitySpace))
589                 continue;
590
591             if (gl.getQualifier() == qualifier)
592                 return gl;
593
594         } while (++index < endIndex);
595         return null;
596     }
597
598 //EXCLUDE-START-lockdiag-
599 /**
600      * make a shallow clone of myself
601      */
602     /* package */
603     public Control shallowClone()
604     {
605         return new LockControl(this);
606     }
607 //EXCLUDE-END-lockdiag-
608
609     /**
610      * Add a lock request to a list of waiters.
611      *
612      * @param waiting The list of waiters to add to
613      * @param lockItem The lock request
614      * @param ls The LockSet
615      */
616     private void addWaiter(List waiting,
617                         Lock lockItem,
618                         LockSet ls) {
619
620         // Add lock to the waiting list
621 waiting.add(lockItem);
622
623         // Maintain count of waiters
624 ls.oneMoreWaiter();
625     }
626
627     /**
628      * Remove and return the first lock request from a list of waiters.
629      *
630      * @param waiting The list of waiters to pop from
631      * @param ls The LockSet
632      *
633      * @return The removed lock request
634      */
635     private Object popFrontWaiter(List waiting, LockSet ls) {
636         // Maintain count of waiters
637 ls.oneLessWaiter();
638
639         // Remove and return the first lock request
640 return waiting.remove(0);
641     }
642
643
644     /**
645      * Remove and return the lock request at the given index
646      * from a list of waiters.
647      *
648      * @param waiting The list of waiters to pop from
649      * @param index The index at which to remove the lock request
650      * @param ls The LockSet
651      *
652      * @return The removed lock request
653      */
654     private Object removeWaiter(List waiting,
655                                 int index,
656                                 LockSet ls) {
657         // Maintain count of waiters
658 ls.oneLessWaiter();
659
660         // Remove and return the first lock request
661 return waiting.remove(index);
662     }
663
664     /**
665      * Remove and return the given lock request from a list of waiters.
666      *
667      * @param waiting The list of waiters to pop from
668      * @param item The item to remove
669      * @param ls The LockSet
670      *
671      * @return The number of items removed
672      */
673     private int removeWaiter(List waiting,
674                                 Object item,
675                                 LockSet ls) {
676         // Maintain count of waiters
677 ls.oneLessWaiter();
678
679         // Remove item and return number of items removed
680 return waiting.remove(item) ? 1 : 0;
681     }
682 }
683
684
685

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags